ВВЕДЕНИЕ 4
Глава 1 Введение в генетический алгоритм 9
1.1 Назначение генетического алгоритма 9
1.2 Понятие генетического алгоритма 10
1.3 Представление данных в генетическом алгоритме 11
1.4 Генерация начальной популяции 12
1.5 Оценка индивидов функцией приспособленности 13
1.6 Оператор выбора родителей и оператор селекции 14
1.7 Оператор скрещивания 15
1.8 Оператор мутации 16
1.9 Остановка генетического алгоритма 17
1.10 Трудности разработки генетического алгоритма 18
Глава 2 Математическая модель элементов генетического алгоритма 20
2.1 Популяция 20
2.2 Генератор начальной популяции 21
2.3 Операторы выбора родителей и жертв 23
2.3.1 Панмиксия и метод ранжирования 23
2.3.2 Метод рулетки 24
2.3.3 Турнирный отбор 26
2.3.4 Инбридинг и аутбридинг 27
2.4 Оператор скрещивания 28
2.4.1 Кроссинговер 28
2.4.2 Дискретная рекомбинация 30
2.5 Оператор мутации 31
2.6 Моделирование случайной величины 33
2.7 Проблемы поиска конфигурации генетического алгоритма 34
Глава 3 Реализация системы испытания генетического алгоритма 35
3.1 Описание системы испытания генетического алгоритма 35
3.2 Абстрактный генетический алгоритм 38
3.3 Элементы генетического алгоритма и его операторы 40
3.4 Проектирование базы данных 43
3.5 Реализация операций с данными 47
3.6 Средство составления сводных таблиц 50
3.7 Исполнитель задач с большой нагрузкой 52
3.8 Пользовательский интерфейс 54
3.9 Применение системы испытания генетического алгоритма 55
Глава 4 Тестовые задачи для методов оптимизации 56
4.1 Задача поиска минимума тестовой функции 56
4.2 Задача упаковки рюкзака. 59
4.3 Испытание генетического алгоритма 63
Глава 5 Варианты улучшения характеристик генетического алгоритма 65
5.1 Способы оценки генетического алгоритма 65
5.2 Подбор размера популяции 66
5.3 Подбор мощности мутации 69
5.4 Подбор оператора выбор родителей 72
5.5 Приближение эволюционной траектории математической моделью ... 77
5.6 Адаптивные генетические операторы 84
5.7 Рекомендации по разработке генетических алгоритмов 87
ЗАКЛЮЧЕНИЕ 89
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ 91
Купить

Существует множество задач, решение которых связано с перебором всех возможных вариантов решения. При решении такой задачи каждый сгенерированный вариант решения оценивается, а после завершения перебора из полученного множества решений выбирается самое пригодное в качестве ответа. Особенностью таких задач является то, что имеющихся знаний для ее решения хватает только на генерацию очередного варианта решения и его оценку. Под оценкой в данном случае понимается некоторая величина, позволяющая сравнить два варианта между собой, чтобы затем объявить один из них лучшим (или оба равносильными). При этом из оценки не может следовать вариант решения, равно как ответ на задачу не может следовать из условия рассматриваемой задачи.
Одной из математических моделей для решения таких задач является генетический алгоритм. Данный алгоритм относится к алгоритмам направленного поиска. Как правило, в его реализации участвуют случайные величины, поэтому его можно также называть стохастическим алгоритмом направленного поиска. Генетический алгоритм моделирует естественный процесс эволюции. Данный алгоритм является эффективным способом оптимизации решений с большим числом параметров. Наиболее частым промышленным применением генетического алгоритма является составление расписаний, так как данный алгоритм успешно справляется с задачами планирования и составления расписаний.
Помимо составления расписаний, генетический алгоритм может быть использован для решения различных комбинаторных задач, к которым относятся задачи компоновки, задачи на графах и прочие. В связи с ростом производительности вычислительных устройств и последующим увеличением популярности алгоритмов искусственного интеллекта вообще, генетический алгоритм теперь применяется и для ускорения настройки нейронных сетей.
Исследования, связанные с повышением эффективности генетического алгоритма, являются крайне актуальными по двум причинам. Во-первых, генетический алгоритм можно легко реализовать для решения той или иной оптимизационной задачи. Например, для обнаружения экстремума некоторой функции, алгоритму понадобятся только сама функция, область поиска и тип экстремума (минимум или максимум). Во -вторых, на текущем этапе развития теории данный вариант генетического алгоритма способен эффективно решать только конкретную задачу, под которую он приспособлен. То есть не существует единого варианта генетического алгоритма, способного одинаково эффективно решать любую задачу поиска.
Научная проблема заключается в том, что получение качественного генетического алгоритма является долгим и трудоемким процессом, обращающим обыкновенную разработку в научную работу с применением эвристик. Разработки, позволяющие упростить процесс создания качественного вариант генетического алгоритма, могут быть полезны во всех областях, связанных с применением данного алгоритма. Расширение знаний о работе генетического алгоритма позволит проще и быстрее решать поисковые задачи с большим числом параметров.
Объект исследования - генетический алгоритм и ход его работы.
Предмет исследования - высокая сложность разработки генетических алгоритмов.
Цель исследования - выявить закономерности между различными настройками генетического алгоритма и качеством его работы, найти способы модификации генетического алгоритма, приводящие к повышению качества его работы, найти способы оптимизации процесса разработки генетического алгоритма.
Гипотеза - подробный анализ хода работы различных генетических алгоритмов на различных задачах позволит выявить полезные закономерности, на которые можно будет опереться при разработке генетического алгоритма для некоторой задачи.
Задачи исследования:
1. Изучить классический генетический алгоритм и его операторы, составить необходимые математические модели.
2. Выявить трудности практического применения классического генетического алгоритма и определить критерии, оценивающие качество работы генетического алгоритма.
3. Реализовать такой вариант генетического алгоритма, который бы позволял легко и быстро тестировать различные конфигурации генетического алгоритма.
4. Реализовать инструмент для испытания и исследования конфигураций генетического алгоритма, позволяющий хранить ход работы алгоритма при данной конфигурации, предоставлять данные, полученные в ходе испытания конфигураций генетического алгоритма, в удобном для последующего анализа виде.
5. Разработать и испытать различные варианты генетических операторов путем составления из них конфигураций генетического алгоритма, найти закономерности между настройками данных операторов и качеством получаемого результата.
6. Провести анализ собранных данных, выявить наиболее успешные варианты конфигурации генетического алгоритма, найти закономерности между конфигурациями генетического алгоритма и качеством получаемого результата, разработать рекомендации по созданию генетического алгоритма с качественной конфигурацией.
7. Оформить выводы и результаты исследования.
Текущий процесс разработки генетических алгоритмов строится на верном и подтвержденном практикой предположении, что алгоритм следует приспосабливать к конкретной задачи. Независимая разработка нового генетического алгоритма при помощи перебора различных конфигураций была единственным доступным способом получения эффективных алгоритмов на
заре развития генетических алгоритмов. Сейчас, когда уже разработано множество генетических алгоритмов для решения широкого спектра задач и есть возможность использования ранее полученных достижений, поэтому необходимо развивать знания о процессе получения производительных конфигураций. Источники [3-6,10-17] акцентируют внимание на готовых конфигурациях, игнорируя процесс их получения. Из -за такого взгляда на генетические алгоритмы возникает недостаток знаний о способах получения производительных конфигураций.
В данной работе предлагается подход к решению возникшей проблемы, основанный на проведении абстрактных (от реально возникающих на практике) испытаний генетического алгоритма на тестовых задачах для методов оптимизации. Полученные эмпирические выборки, описывающие ход работы алгоритма, позволят выявить полезные опорные явления, на которые может ориентироваться разработчик генетических алгоритмов. В основу данного исследования положена визуализация полученных данных в виде эволюционных траекторий, подробно описывающих состояние алгоритма в различные моменты времени.
Научная новизна данной работы заключается в уточнении данных о разработке новых генетических алгоритмов. Предлагаются правила выбора генетических операторов, позволяющие сократить время подбора эффективной конфигурации. Предлагается способ прогнозирования работы генетического алгоритма, также позволяющий существенно сократить время подбора качественной конфигурации генетического алгоритма.
Установлено, что размер популяции следует подбирать в зависимости от сложности задачи. Разработано правило выбора размера популяции в зависимости от сложности решаемой задачи. Установлено, что оператор выбора родителей следует подбирать в зависимости от сложности задачи. Разработано правило выбора оператора выбора родителей в зависимости от сложности решаемой задачи, разработан вариант оператора выбора родителей. Установлено, что мощность мутации следует подбирать в зависимости от сложности задачи. Разработано правило выбора мощности мутации в зависимости от сложности задачи. Установлена обратная зависимость между скоростью получения решения и его точностью, для борьбы с данной особенностью разработан адаптивный вариант оператора мутации. Разработана функция, чья форма схожа с эволюционной траекторией, разработан способ ее получения по первоначальному участку эволюционной траектории.
Объем и структура диссертации: диссертационное исследование состоит из введения, 5 глав, заключения, библиографии (30 наименований). Работа изложена на 94 страницах, содержит 26 рисунков.
Купить