АННОТАЦИЯ 2
ВВЕДЕНИЕ 6
1 ОБЗОР ЛИТЕРАТУРЫ 7
1.1 Основные определения 7
1.2 Стандартные методы решения задачи о назначениях 8
1.3 Эвристические алгоритмы 9
1.3.1 Методы локального поиска 9
1.3.2 Моделирование процесса отжига 12
1.3.3 Генетические алгоритмы 13
1.4 Модифицированные алгоритмы 16
1.4.2 Решение квадратичной задачи о назначениях с использованием генетического алгоритма 16
1.4.2 Метаэвристическое моделирование поведения муравьиных колоний .. 19
1.4.3 Использование растущей нейронной сети 21
1.5 Выводы по главе 1 23
2 ИССЛЕДОВАНИЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА 24
2.1. Постановка задачи 24
2.2 Разнообразие генетических алгоритмов 24
2.2.1 Операторы выбора родителей 24
2.2.2 Рекомбинация 25
2.2.3 Мутация 27
2.2.4 Операторы отбора 27
2.2.5 Некоторые виды генетических алгоритмов 28
2.3 Реализация алгоритма и численные эксперименты 30
2.3.1 Классический генетический алгоритм 30
2.3.2 Модификация алгоритма путем изменения операторов 33
2.3.3 Применение улучшенных модифицированных операторов 35
2.4 Эффективность алгоритма 42
2.5 Выводы по главе 2 44
ЗАКЛЮЧЕНИЕ 46
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
Существуют задачи оптимизации, обладающие свойством
многоэкстремальности, т.е. наличием большого числа решений, на которых целевая функция достигает значения, близкие к оптимальному. В таких случаях многие методы и даже их модификации становятся неэффективным. Поэтому оказывается актуальным создание новых специфических операторов и модификаций широко применяемых алгоритмов.
Примером многоэкстремальной задачи является NP-полная квадратичная задача о назначениях. Многие практические задачи, например, задачи транспортной логистики или задача проектирования микросхем, сводятся к квадратичной задаче о назначениях. В связи с этим в настоящее время остается актуальным построение эффективных алгоритмов для таких задач, как квадратичная задача о назначениях.
Оптимальное решение в квадратичной задаче о назначениях с помощью классических методов, в общем случае, удается найти лишь тогда, когда параметр, определяющий задачу, принимает очень небольшие значения (т.е. задача имеет размерность примерно до 10-15). Именно поэтому для исследования выбран один из классов эвристических алгоритмов, называемых генетическими алгоритмами.
Целью данной работы является исследование генетических алгоритмов и их модификаций, а также разработка эффективного генетического алгоритма для решения квадратичной задачи о назначениях путем подбора параметров, комбинирования различных операторов и использования специфических подходов.
Задачи, решаемые для достижения поставленных целей:
• обзор генетических алгоритмов;
• сравнение эффективности разных модификаций;
• реализация генетического алгоритма решения квадратичной задачи о
назначениях;
• проведение вычислительных экспериментов для определения наилучших комбинаций операторов и подбора параметров алгоритма.
В ходе выполнения выпускной квалификационной работы исследовались параметры генетического алгоритма, используемого для решения квадратичной задачи о назначениях.
Рассмотрены стандартные и эвристические методы решения квадратичной задачи о назначениях. Для задач больших размерностей стандартные алгоритмы имеют большую вычислительную сложность, поэтому широкое применение для решения квадратичной задачи о назначениях, а также других NP-сложных задач, получили эвристические алгоритмы. Лучшим образом показали себя следующие подходы: муравьиный алгоритм, применение нейронных сетей и генетические алгоритмы.
Подробно исследован генетический алгоритм. Анализ исследований, посвященных разработке генетического алгоритма показал, что существуют различные модификации стандартных операторов выбора родительских пар, скрещивания, мутации, а также разные виды генетических алгоритмов.
Основная трудность в решении квадратичной задачи о назначениях с использованием генетического алгоритма состоит в преодолении их преждевременной сходимости к локальному экстремуму. Данная проблема была решена за счет введения мутации специального вида.
