Лабораторная работа 4
Тема: Решение задач с помощью генетических алгоритмов.
Цель работы: Ознакомиться с подходом к решению оптимизационных задач с помощью генетических алгоритмов (ГА).
Задачи работы:
Ознакомиться с основными понятиями ГА.
Научиться применять метод ГА для решения задачи о коммивояжере.
Изучить программное средство для решения оптимизационных задач с помощью ГА GeneHunter (на примере задачи о коммивояжере).
4.1 Теоретические сведения. Основные понятия
Генетический алгоритм – это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путем последовательного подбора, комбинирования и вариации искомых параметров. ГА можно рассматривать как одну из разновидностей случайного поиска, которая основана на механизмах, напоминающих естественный отбор и размножение.
ГА начинает работу с некоторого случайного набора исходных решений, который называется популяцией. Каждый элемент из популяции называется хромосомой и представляет некоторое решение проблемы в первом приближении. Хромосомы эволюционируют на протяжении множества итераций, носящих название поколений (или генераций).
Для создания следующего поколения новые хромосомы, называемые отпрысками, формируются либо путем скрещивания двух хромосом-родителей из текущей популяции, либо путем случайного изменения (мутации) одной хромосомы.
Операция скрещивания (кроссовер). Скрещивание является главной генетической операцией. Эта операция выполняется над двумя хромосомами-родителями и создает отпрыск путем комбинирования особенностей обоих родителей. Приведем простейший пример скрещивания – одноточечный (см. рис. 4.1). В начале выберем некоторую случайную точку (точка скрещивания Ts), после чего создадим хромосому-отпрыск (см. рис. 4.1в) путем комбинирования сегмента первого родителя (рис. 4.1а), стоящего слева от выбранной точки скрещивания, с сегментом второго родителя (см. рис. 4.1б), стоящего по правую сторону от точки скрещивания.
Рис. 4.1– Операция скрещивания
Операция мутации. Мутация – операция, производящая случайное изменение в различных хромосомах. Наипростейший вариант мутации состоит в случайном изменении одной (см. рис. 4.2) или более хромосом. В генетических алгоритмах мутация играет важную роль для восстановления генов, выпавших из популяции в ходе операции выбора. Интенсивность мутации определяется коэффициентом мутации.
Рис. 4.2 – Операция мутации
Кроме того, используется так называемый оператор инверсии, суть применения которого состоит в том, что хромосома делится на две части, после чего эти части меняются местами (см. рис. 4.3).
Рис. 4.3 – Оператор инверсии
В общем случае для функционирования генетического алгоритма достаточно трех рассмотренных генетических операторов, но на практике применяют еще и некоторые дополнительные или модификации представленных операторов. Например, кроссовер может быть многоточечным, когда формируется несколько точек разрыва (чаще всего две).
4.1.1 Программные средства реализации генетических алгоритмов
1. MatLab (открытие инструментария ГА осуществляется выполнением команды gatool в командной строке пакета).
2. RawData Analyzer (исследование данных с помощью нескольких видов нейросетей и генетических алгоритмов).
3. NeuroShell GeneHunter (комплекс мощных программных средств для решения оптимизационных задач).
4. Auto2Fit (инструмент, предназначенный для решения оптимизационных задач и проведения сложных инженерных расчетов).