Тема: Исследование вариантов улучшения конфигурации генетического алгоритма

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

В рамках данной работы было проведено исследование способов и особенностей получения производительных конфигураций генетического алгоритма, основанное на анализе эволюционных траекторий. Изучение классического генетического алгоритма и составление математических моделей генетических операторов позволило выявить трудности, связанные с поисковым характером составления качественной конфигурации. С целью автоматизации процесса подбора генетических операторов был реализован генетический алгоритм с каркасной архитектурой, способный также собирать данные о динамике состояния популяции.
Процесс испытания конфигурации генетического алгоритма включает в себя реализацию генетического алгоритма при данной конфигурации, его запуск и одновременный сбор данных о ходе работы алгоритма. Стохастическая природа генетического алгоритма усложняет подобные испытания тем, что пусков необходимо делать много, а собранные данные усреднять. Для упрощения такого способа исследования разработана и описана система испытания генетических алгоритмов, принимающая в качестве входных данных конфигурации генетического алгоритма и форматы сводных таблиц, а выдающая в качестве результата сводные таблицы с данными о ходе работы алгоритма при некоторой конфигурации. Реализована возможность импорта в виде таблиц и в виде графиков.
Решение основной проблемы, связанной с высокой сложностью разработки генетических алгоритмов из -за поискового характера данного процесса, представлено в виде правил по настройке генетического алгоритма, основанных на сложности решаемой задачи: разработаны две стратегии по выбору размера популяции, оператора выбора родителей и мощности оператора мутации для простых и сложных задач. Обозначена обратная зависимость между точностью найденного решения и скоростью его получения. Описан способ борьбы с данной зависимостью при помощи адаптивного оператора мутации, применение которого позволило быстро получить точное решение простой задачи. Разработана функция, способная аппроксимировать эволюционную траекторию показателя наилучшей степени приспособленности в поколении. Также предоставлены результаты попыток прогнозирования формы эволюционной траектории при помощи данной функции. Полученные результаты позволят сократить время поиска качественной конфигурации за счет уменьшения как числа пробуемых конфигураций (применение правил выбора генетических операторов), так и за счет сокращения времени моделирования генетического алгоритма (применение формы аппроксимирующей функции вместо реальной работы алгоритма).

Купить