Генетические алгоритмы являются универсальным методом оптимизации многопараметрических функций, что позволяет решать широкий спектр задач, имеют множество модификаций и сильно зависят от параметров. Зачастую небольшое изменение одного из них может привести к неожиданному улучшению результата. Применение генетических алгоритмов полезно лишь в тех случаях, когда для данной задачи нет подходящего специального алгоритма решения.
Формально генетический алгоритм — это алгоритм, который позволяет найти удовлетворительное решение к аналитически неразрешимым проблемам через последовательный подбор и комбинирование искомых параметров с использованием механизмов, напоминающих биологическую эволюцию [1].
Генетические алгоритмы применяются для решения следующих задач:
- Оптимизация функций
- Разнообразные задачи на графах (задача коммивояжера, раскраска, нахождение паросочетаний)
- Настройка и обучение искусственной нейронной сети
- Составление расписаний
- Игровые стратегии
- Аппроксимация функций
- Искусственная жизнь
- Биоинформатика
Генетические алгоритмы это стохастические эвристические оптимизационные методы, основная идея которых взята из теории эволюционного развития видов. Основным механизмом эволюции является естественный отбор, суть которого состоит в том, что более приспособленные особи имеют больше шансов на выживание и размножение и, следовательно, приносят больше потомства, чем менее приспособленные особи. При этом благодаря передаче генетической информации потомки наследуют от родителей основные их качества. Носителями генетической информации индивидуума выступают молекулы ДНК. При размножении животных происходит слияние двух родительских половых клеток. Их ДНК взаимодействуют, образуя ДНК потомка. Основной способ взаимодействия кроссинговер. При кроссинговере ДНК предков делятся на две части, а затем обмениваются своими половинками. При наследовании возможны мутации из-за радиоактивности или других влияний, в результате которых могут измениться некоторые гены в половых клетках одного из родителей. Измененные гены передаются потомку и придают ему новые свойства. Если эти новые свойства полезны, они, скорее всего, сохранятся в данном виде и при этом произойдёт скачкообразное повышение приспособленности вида [2].
Первым шагом при разработке математической модели, основанной на генетическом алгоритме, является разработка структуры хромосомы, в которой будет храниться решение. Выбранная структура должна учитывать все особенности и ограничения, предъявляемые к искомому решению, а также то, что от её выбора напрямую зависят реализации алгоритмов кроссинговера и мутации. В конечном счёте, выбор хромосомы влияет не только на скорость, но и на сходимость алгоритма вообще.
Структура хромосомы удобна тем, что уже на этапе задания начальных данных можно исключить заведомо неудачные решения, заблокировав соответствующие ячейки.
На следующем шаге алгоритма создаётся начальная популяция, размер которой зависит от размерности задачи и составляет обычно несколько сотен решений.
Для организации оптимизирующего процесса необходимо создать направляющую силу развития популяции. В качестве такой силы выступает требование минимизации целевой функции или, в терминах генетических алгоритмов, фитнес функции. Обычно в качестве её используется аддитивный показатель оптимальности, основанный на штрафах, устанавливаемых каждому решению за какой либо неудобный. Преимуществом такого выбора является возможность настройки алгоритма под конкретную задачу путём варьирования коэффициентов и, тем самым, изменения приоритетов при поиске оптимального решения.
Таким образом, поместив начальную популяцию в созданную нами искусственную среду и реализовав процессы селекции, кроссинговера и мутации, мы получим итерационный алгоритм поиска оптимального решения, на каждой итерации которого выполняются следующие действия:
1. Каждая особь популяции оценивается с помощью фитнес функции.
2. Лучшие решения копируются в новую популяцию без изменения. Такой принцип (принцип элитизма) предотвращает потери лучших решений и обеспечивает повышенную сходимость алгоритма.
3. На основе пропорционального отбора из текущей популяции выбираются два решения, которые подвергаются рекомбинации. Для этого хромосомы родителей обмениваются соответствующими участками.
4. Если новая популяция сформирована, то старая удаляется, после чего переходим к этапу 1. В противном случае переходим к этапу 3.
Рассмотренный алгоритм является не только устойчивым к локальным минимумам, но и благодаря внутреннему параллелизму, выраженному в работе не с отдельными решениями, а с целыми классами решений, обеспечивает относительно быстрый поиск оптимального решения.
Методы исследования в своей основе используют итерационную технику улучшения результатов. В течение одной итерации они ищут решение, лучшее в окрестностях данного. Если такое решение найдено, оно становится текущим и начинается новая итерация. Это продолжается до тех пор, пока прирост целевой функции не уменьшится практически до нуля или не выполнится заданное количество итераций. Очевидно, что такие методы ориентированы на поиск только локальных оптимумов, причём положение найденного оптимума зависит от стартовой точки. Глобальный же оптимум может быть найден только случайно. Для повышения вероятности нахождения глобального оптимума используется множественный эксперимент с различными начальными точками, что существенно увеличивает время поиска.
В связи с этим представляет интерес разработка алгоритмов, сохраняющих преимущества описанных методов и свободных от указанного недостатка. К таким алгоритмам относятся генетические алгоритмы.
Литература:
1. Емельянов В. В., Курейчик В. В., Курейчик В. М. Теория и практика эволюционного моделирования. — М: Физматлит, 2003. — С. 432.
2. Гладков Л. А., Курейчик В. В., Курейчик В. М. Генетические алгоритмы: Учебное пособие. — 2-е изд. — М: Физматлит, 2006. — С. 320.
