Разработка и исследование генетических алгоритмов обучения в моделях вычисления оценок

• Автор: Ковшов, Николай Вадимович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Долгопрудный
• Количество страниц: 131 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ.

ГЛАВА 1. ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ И МЕТОД

КОДИРОВАНИЯ ПРЕДИКАТОВ

1.1.Общая постановка задачи

1.1.1. Общая формулировка.

1.1.2. Структура алгоритма распознавания

1.2.0бщий принцип кодирования предикатов.

ГЗ.Создание покрытия класса и критерий оптимальности.

1.4.0бработка неизвестных значений признаков.

1.4.1. Осторожный подход

1.4.2. Жадный подход
1.5.Расширение границ предиката
1.6.0сновные результаты и выводы по главе 1
ГЛАВА 2. СТРУКТУРА ГЕНЕТИЧЕСКОГО АЛГОРИТМА И ЕГО АДАПТАЦИЯ К ОСОБЕННОСТЯМ ЗАДАЧИ.
2.1.Введение в теорию генетических алгоритмов
2.1.1. Оператор селекции
2.1.2. Оператор кроссовера
2.1.3. Оператор мутации.
2.1.4. Оператор отбора
2.1.5. Старт и завершение ГА
2.1.6. Типы генетических алгоритмов.
2.2.Применение ГА к решению поставленной задачи
2.3.Фундаментальная теорема ГА.
2.4.Исследование характерных особенностей задачи.
2.4.1. Оценка количества локальных экстремумов задачи.
2.5.Исследование операторов ГА и их применимости при решении поставленной задачи
2.5.1. Оператор кроссовера
2.5.1.1. Вероятность сохранения шаблона.
2.5.1.2. Метод кроссовера, учитывающий взаимное расположение объектов обучающей выборки
2.5.1.3. Экспериментальное сравнение различных механизмов кроссовера
2.5.2. Размер популяции.
2.5.3. Вероятность мутации
2.5.4. Критерий остановки ГА
2.5.4.1. ЭССкритерий остановки ГА.
2.5.4.2. Экспериментальное подтверждение адекватности авторского критерия остановки
2.6.0сновные результаты и выводы по главе 2.
ГЛАВА 3. ОПИСАНИЕ АЛГОРИТМА РАСПОЗНАВАНИЯ
3.1.Вычисление оценок за классы.
3.1.1. Вычисление оценок по принадлежности снаружи
3.1.2. Вычисление оценок по частичной принадлежности.
3.1.2.1. Роль порогового значения
3.2.Решающее правило
3.2.1. Решающее правило 1.
3.2.2. Решающее правило 2.
3.2.3. Тестирование РП1 на задачах распознавания
3.2.4. Тестирование РП2 на задачах распознавания
3.2.5. Сравнительный анчиз РП1 и РП2.
З.З.Основные результаты и выводы по главе 3.
ГЛАВА 4. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМОВ И ОПТИМИЗАЦИЯ ЗАТРАТ МАШИННОГО ВРЕМЕНИ. ОЦЕНКА СЛОЖНОСТИ АЛГОРИТМОВ.
4.1. Программная реализация.
4.2. Оценка сложности алгоритмов
4.2.1. Оценка вычислительной сложности обучения.
4.2.1.1. Экспериментальное подтверждение оценки сложности обучения.
4.2.2. Оценка вычислительной сложности распознавания.
4.3.Метод дробления выборки
4.4. Основные результаты и выводы по главе 4.
ГЛАВА 5. ТЕСТИРОВАНИЕ РАЗРАБОТАННЫХ МЕТОДОВ НА ПРИКЛАДНЫХ ЗАДАЧАХ ИЗ ОБЛАСТИ РАСПОЗНАВАНИЯ ОБРАЗОВ.
5.1.Тестовые задачи
5.1.1. Модельная задача 1
5.1.2. Модельная задача 2
5.1.3. Модельная задача 3
5.1.4. Опознавание кредитных карт
5.1.5. Распознавание радиосигналов.
5.1.6. Распознавание фоновых изображений.
5.1.7. Диагностика космической техники.
5.1.8. Распознавание сортов вин
5.1.9. Распознавание изображений автомобилей.
5.1 Диагностика рака груди.
5.2.Сравнение с другими методами.
5.2.1. Перечень методов для сравнения
5.2.2. Результаты вычислений.
5.2.3. Модельная задача 2
5.2.4. Модельная задача 3
5.2.5. Прочие прикладные задачи.
5.2.6. Прогнозирование типа кристаллической решетки неорганических соединений
5.3.Основные результаты и выводы по главе 5
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ


International Conference on Pattern Recognition and Image Analysis PRIA-7 (St. WSEAS Int. Conf. Научные семинары отдела математических проблем распознавания и методов комбинаторного анализа Вычислительного центра РАН (Москва, -). По теме диссертации опубликовано 8 работ, в том числе одна из списка изданий, рекомендованного ВАК РФ. Кратко изложим основное содержание работы. В первой главе приводится общая постановка задачи распознавания образов по прецедентам. Вводятся понятия логической закономерности, критерия оптимальности, допустимого предиката. Описывается общая схема процесса классификации с учителем. В п. Показано, что при некоторых ограничениях на вид критерия оптимальности, данное сужение области поиска не ведет к потере оптимальных решений. В п. Суть модификации заключается в том, что критерий оптимальности предиката приравнивается к нулю, если предикат не содержит ни одного объекта, не вошедшего в ранее найденные предикаты. В п. Считается, что точка с неизвестным значением признака принадлежит любому отрезку либо интервалу. Во второй главе дается обзор генетических операторов и наиболее известных современных имплементаций ГЛ. Представлена схема работы генетического алгоритма. Представлены функции кодирования и декодирования, связывающие пространство предикатов с бинарным пространством размерности Лг, где N - число объектов в рассматриваемом классе. Данные функции позволяют проводить поиск оптимальных предикатов посредством генетического поиска глобального экстремума целевой функции, определенной в бинарном пространстве. В п. Приводится сравнение экспериментальных результатов и теорегической оценки количества локальных экстремумов. В п. Предложены механизмы автоматического выбора размера популяции и коэффициента мутации в зависимости от параметров задачи. В п. ГА. В отличие от «стандартных» критериев остановки, завершающих работу ГА после выполнения определенного количества итераций либо после выполнения некоторого числа итераций без улучшения лучшей ЦФ популяции, предложенный критерий адаптируется к конкретной задаче. Это позволяет сократить количество итераций для простых, малоэкстремальных задач и повысить при решении сложных. Третья глава посвящена описанию процедуры распознавания. Описан процесс вычисления оценок за классы и голосования по оценкам. Предложено 2 новых метода вычисления оценок за классы. Согласно первому из предложенных методов, при проверке вхождения объекта в предикат некоторого класса, следует создать на основе данного объекта и предиката расширенный предикат и проверить, является ли он допустимым. Второй предложенный метод оценки производит расчет общего количества признаковых интервалов предиката, которым удовлетворяет распознаваемый объект. Данное число учитывается в расчете общей оценки, если оно превышает некоторое пороговое значение. Предложено два новых решающих правила, учитывающих сразу три оценки за классы - «традиционную» оценку, учитывающую количество вхождений распознаваемого объекта в предикаты, а также две предложенные в работе оценки. Тестирование на прикладных задачах показало, что каждое из решающих правил работает существенно лучше, чем метод простого голосования по любой отдельно взятой оценке за класс. Кроме того, представленные решающие правила обладают некоторым набором достоинств и недостатков друг относительно друга, определяющимися условиями задачи. Четвертая глава содержит детали программной реализации предложенных алгоритмов. Алгоритмы реализованы автором в программе «Genesis» на языке Фортран-, а также в качестве модуля в программном комплексе «Recognition» на языке Visual C++ 6. Программа «Genesis» позволяет пользователю строить генетический алгоритм, варьируя типы генетических операторов, а также все значимые параметры ГА. Кроме того, включена возможность построения новых решающих правил на основе оценок за классы. Дана спецификация форматов входных данных. Также в четвертой главе проведен теоретический анализ вычислительной сложности алгоритмов обучения и распознавания. Полученные оценки сравнивались с экспериментальными данными.