ГА – это метод оптимизации, в которых моделирование биологической эволюции рассматривается как способ решения математической проблемы.
1975 – Джон Холланд – идея формирования процесса эволюции.
Популяция – это конечное множество особей.
Особь – это отдельное решение задачи, представленное хромосомой.
Хромосома – это упорядоченная последовательность генов.
Ген – это атомарный элемент хромосом.
Генетический алгоритм.
1 этап – инициализация – это создание начальной популяции путем случайной генерации хромосом. Важное условие – начальная популяция должна быть разнообразной.
2 этап – оценка – это дает возможность определить насколько каждая хромосома «приспособлена» к решению данной задачи. Для этого используется функция приспособленности – fitness fanction.
3 этап – отбор (селекция) – здесь хромосомы выбираются для участия в этапе рекомбинации. Наиболее часто используется метод «рулетка».
Каждой хромосоме сопоставляется сектор рулетки, причем его площадь пропорциональна значению функции оценки данной хромосомы – процесс отбора является одновременно случайным и детерминированным (определенным).
4 этап – рекомбинация. На этом этапе части хромосом перемещаются или изменяются, а получившиеся новые хромосомы формируют следующую популяцию.
Существуют 2 оператора рекомбинации:
— оператор скрещивания (crossover). Вероятность скрещивания= 0,5..1,0
— оператор мутации (mutation). Мутация – изменение знаний отдельных генов в одной хромосоме. Вероятность мутации=0..0,1
5 этап – проверка условия окончания алгоритма. Достигнуто ожидаемое оптимальное значение функции оценки. 4 вида условий:
— решение получено с заданной степенью точности
— выполнение алгоритма не приводит к улучшению решения
— достигнуто максимально возможное количество поколений.
Области применения: задачи оптимизации; задача Комишвояжера; составление расписания (задачи планирования); составление компьютерных программ ; обучение нейронных сетей
Пример: найти максимум функции.
Спонсор статьи — Сервис продвижения сайтов «VIPRO» — предлагает вашему вниманию услуги по продвижению сайтов, раскрутке и оптимизацию ваших интернет-ресурсов с гарантями качества выполненной работы.
