ВВЕДЕНИЕ 5
1 АНАЛИЗ СОСТОЯНИЯ ВОПРОСА 7
2 ВЫБОР КОНФИГУРАЦИИ ГЕНЕТИЧЕСКОГО АЛГОРИТМА 13
2.1 Описание конфигурации генетического алгоритма 13
2.2 Функции для тестирования работы генетических алгоритмов 17
2.3 Вычислительный эксперимент для тестирования конфигурации
генетического алгоритма 24
3 ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ДЛЯ МОДЕЛИРОВАНИЯ
ГЕНЕТИЧЕСКОГО АЛГОРИТМА 28
3.1 Описание программного обеспечения 28
3.2 Результаты апробации генетического алгоритма на тестовых функциях. 31
ЗАКЛЮЧЕНИЕ 35
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ 37
Данное исследование посвящено изучению эвристических алгоритмов оптимизации, основанных на эволюционных вычислениях.
Решение задач оптимизации заключается в нахождении входных параметров, при которых функция принимает либо максимальное, либо минимальное значение. В задачах оптимизации данную исследуемую функцию называют целевой.
Для решения задач оптимизации существует множество математических методов, которые можно разделить 2 группы:
• градиентные методы, основанные на понятии производной;
• стохастические методы (в качестве примера можно привести метод Монте-Карло).
Данные методы позволяют находить экстремумы функции , но не всегда можно быть уверенным, что они глобальные. Нахождение локального решения вместо глобального называется проблемой преждевременной сходимости. При использовании точных методов оптимизации из-за сложности математического аппарата резко возрастают временные затраты на поиск решения.
Для преодоления данных недостатков методов оптимизации исследователи ищут пути по совершенствованию старых и поиску новых подходов к решению оптимизационных задач.
Одним из новых подходов для решения оптимизационных задач, предложенных Джонном Холландом, является метаэвристический генетический алгоритм. Генетические алгоритмы основаны на принципах естественного отбора Дарвина и относятся к стохастическим методам оптимизации.
Используемые в генетическом алгоритме подходы стремительно развиваются: появляются новые вариации операторов скрещивания, отбора особей в новую популяцию, отбора родителей и т.д. При этом все существующие операторы могут сочетаться в разных комбинациях, порождая все новые и новые конфигурации генетических алгоритмов. Также у каждого оператора есть свои параметры, например у оператора мутации - вероятность мутации и т.д. Это еще больше увеличивает количество возможных конфигураций генетического алгоритма.
Поэтому актуальной задачей является разработка программного средства для сравнения различных конфигураций генетического алгоритма.
Цель данной работы - разработать программное обеспечение для сравнения разных конфигураций генетического алгоритма при решении задачи оптимизации функции нескольких переменных.
Поставленная цель достигается путем решения следующих задач:
- анализ принципов работы генетического алгоритма;
- выбор тестовых функций, на которых будет оцениваться работа различных конфигураций генетического алгоритма;
- разработка программного обеспечения для визуализации процесса поиска глобальных экстремумов функции;
- тестирование разработанного программного обеспечения.
В ходе выполнения бакалаврской работы были получены следующие результаты.
1. Обзор литературных источников показал, что перспективным методом решения задач оптимизации является генетический алгоритм. Данный алгоритм относится к стохастическим методам поиска решений. Генетический алгоритм является метаэвристическим, это значит, что он является основой для создания конкретных конфигураций эвристических алгоритмов. Поэтому актуальной задачей остается исследование свойств различных конфигураций генетических алгоритмов.
2. В ходе исследования проанализированы принципы действия генетического алгоритма.
3. Предложена конфигурации генетического алгоритма, включающая в себя случайное генерирование решений на первой итерации, остановку поиска решений при локализации особей в отдельной окрестности, использование панмиксии в качестве оператора выбора родителей, получение новых решений задачи оптимизации за счет вещественной рекомбинации генов, мутацию вещественных генов особей-потомков, элитарный отбор особей в новую популяцию.
4. Разработано и протестировано программное обеспечение для визуализации процесса поиска решения генетическим алгоритмом путем отображения особей текущей популяции на трехмерном графике исследуемой функции.
5. Проведен вычислительный эксперимент, направленный на тестирование предложенной конфигурации генетического алгоритма в задачах поиска глобальных минимумов функций Растрыгина, Швефеля и Грайвенка.
6. При тестировании предложенной конфигурации генетического алгоритма на функции Растрыгина от двух переменных глобальный минимум находится за 12 итераций, на функции Швефеля от двух переменных - за 10 итераций, на функции Грайвенка - за 42 итерации.
