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

• Автор: Генералов, Константин Александрович
• Шифр специальности: 05.13.17, 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Пенза
• Количество страниц: 178 с.

Содержание
Введение

1 Генетические алгоритмы в задачах глобальной оптимизации

1.1 Формулировка задачи поиска экстремума.1

1.2 Обзор методов решения задач поиска глобального экстремума

1.3 Принцип работы простого генетического алгоритма

1.4 Отличия генетических алгоритмов от других методов

1.5 Анализ вариантов реализации генетических алгоритмов

1.5.1 Варианты представление генов и хромосом

1.5.2 Разработка классификации генетических алгоритмов.

1.6 Анализ основных направлений исследований в области генетических алгоритмов.

1.7 Проблемы практического применения генетических алгоритмов
1.8 Исследование методов, средства и технологии реализации генетических алгоритмов.
1.9 Выбор метода оценки эффективности языка программирования
генетических алгоритмов
Выводы по первой главе.
2 Обобщнная алгебраическая модель генетических алгоритмов.
2.1 Преобразование структур данных генетических алгоритмов.
2.2 Нумерация пар чисел.
2.3 Разработка алгоритма преобразования хромосом к унифицированному виду.
2.4 Пример преобразования хромосом к унифицированному виду.
2.5 Разработка обобщнной алгебраической модели генетического алгоритма
2.6 Интервальные вычисления над популяциями
2.7 Общая модель решения задачи
Выводы по второй главе.
3 Лингвистические средства разработки генетических алгоритмов
3.1 Концепция языка программирования генетических алгоритмов
3.2 Разработка грамматики языка программирования генетических алгоритмов
3.3 Структура среды реализации г енетических алгоритмов.
3.4 Характеристики Холстеда как инструмент оценки эффективности реализации программ.
3.5 Экспериментальное определение характеристик Холстеда
3.5.1 Постановка решаемой задачи
3.5.2 Решение задачи на различных языках программирования.
3.6 Анализ результатов эксперимента.
Выводы по третьей главе.
4 Применение языковых средств реализации генетических алгоритмов для решения задач оптимизации
4.1 Актуальность использования генетических алгоритмов в задачах оптимизации
4.2 Решение задачи об умном муравье
4.3 Аппроксимация функций с помощью генетических алгоритмов
4.4 Решение задачи разбиения графа
4.5 Решение задачи о коммивояжре.
4.6 Определение паросочетаний графа.
Выводы по четвртой главе.
Заключение
Список литературы


В-третьих, при использовании методов, основанных на вычислении первых и вторых производных, по сравнению с прямыми методами поиска, требуется довольно большое время на подготовку задачи к решению. К одномерному поиску относят пассивный и последовательный методы поиска. Пассивный поиск заключается в случайном выборе пар на заданном отрезке для нахождения оптимума целевой функции. Последовательный поиск выполняется путём перебора значений целевой функции для нахождения оптимального значения. Применения методов одномерного поиска возможно в случае функций одной переменной. На практике чаще используются функции многих переменных, поэтому методы одномерного поиска чаще применяют как вспомогательные методы. Все известные методы поиска глобального экстремума можно разделить на две категории: детерминированные и стохастические. Детерминированные методы получают глобальное решение с помощью исчерпывающего поиска на всем допустимом множестве решений. Поэтому большинство детерминированных методов теряют эффективность и надежность с возрастанием размерности задачи. Болсс того, чтобы гарантировать успех, такие методы требуют выполнения дополнительных предположений, наложенных на функцию цели [3-6]. Стохастические алгоритмы позволяют уйги от проблем детерминированных алгоритмов. Большинство стохастических методов оценивают значение функции цели в случайных точках допустимого множества с последующей обработкой выборки. Как следствие, стохастические методы не гарантируют успех. Первым методом глобальной оптимизации является метод Монге-Карло, на базе которого был создан метод мультистарта (multistart method). В методе мультистарта выбирается некоторое подмножество точек их множества. Последовательно из каждой точки запускается алгоритм локального спуска, и из полученного множества локальных решений выбирается наилучшее. Сам по себе метод мультисгарта не является эффективным, т. Методы группировок (clustering methods) являются одной из модификаций метода мультистарта. В них предпринята попытка устранения главного недостатка мультистарта путем тщательного отбора точек, из которых запускается локальный поиск. Методы деления пополам (bisection methods) и методы интервалов (interval methods) гарантируют, что решение будет получено с заданной точностью. Большинство методов интервалов используют стратегию ветвей и границ (branch-and-bound strategy) . Такие алгоритмы разделяют область поиска на набор многомерных кубов, на которых нижняя граница функции цели вычисляется с помощью интервальной техники. Используя интервальную арифметику на каждом шаге, получаем набор последовательно уменьшающихся интервалов, который содержит глобальное решение исходной задачи. Алгоритм останавливается, когда размер интервалов достигает заранее заданного значения. Основная идея метода моделирования отжига (simulated annealing), исходит из физики процесса замерзания жидкостей. Целевая функция является аналогом равновесия термодинамической системы и видоизменяется путем добавления случайных величин (условий температурного режима). Каждый шаг метода туннелей (tunneling method) состоит из двух фаз: фаза минимизации улучшает значение текущего рекорда; фаза туннелирования находит точку из допустимого множества, отличную от последней, где найдено значение минимума. Полученная на фазе туннелирования точка рассматривается как стартовая для очередного цикла. Главный недостаток этого алгоритма - необходимость решения сложных нелинейных дифференциальных уравнений. Траекторные методы (trajectory methods), в частности, метод продолжения (continuation method), занимают важное место в глобальной оптимизации. Траекторные методы на допустимом множестве исходной задачи строят множество кривых (траекторий). Основная идея траекторных методов заключается в том, что все решения исходной задачи лежат на этих кривых. Во многих случаях эти траектории являются решением систем обыкновенных дифференциальных уравнений первого или второго порядка. Алгоритм контролируемого случайного поиска (controlled random search algorithm) является методом прямого поиска.