Генети́ческий алгори́тм (англ. genetic algorithm) — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путем последовательного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию. Является разновидностью эволюционных вычислений (англ. evolutionary computation). Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе. «Отцом-основателем» генетических алгоритмов считается Джон Холланд (англ. John Holland), книга которого «Адаптация в естественных и искусственных системах» (англ. Adaptation in Natural and Artificial Systems) является основополагающим трудом в этой области исследований.
Алгоритм генетического поиска:
- создание популяции геномов
- цикл по эпохам
- - цикл по элементам популяции
- - - расшифровка текущего генома
- - - создание элемента из расшифрованного генома
- - - тестирование элемента и расчет его качества
- - - сравнение и отбор лучшего элемента по качеству
- - конец цикла
- - трансформация популяции согласно рассчитанному качеству
- конец цикла
Алгоритм трансформации популяции:
- деление популяции геномов на плохую и хорошую
- случайное перемешивание порядка геномов в этих частях
- цикл по половинам популяции
- - скрещивание двух хороших в два новых
- - мутация двух новых геномов
- - замена двух плохих новыми геномами
- конец цикла
Алгоритм скрещивания геномов:
- копирование двух хороших геномов в два новые генома
- цикл вдоль новых геномов по генам
- - запрос случайного с вероятностью 0,5
- - если сработало, то меняем местами текущие гены геномов
- конец цикла
Алгоритм мутации генома:
- цикл вдоль генома по генам
- - запрос случайного с вероятностью равной шоку
- - если сработало, то увеличиваем мутацию в 10 раз
- - добавляем к текущему гену случайное помноженное на мутацию
- - ограничиваем ген по максимуму и минимуму (если выскочил за диапазон)
- конец цикла
Ссылки:
- Материал из Википедии — свободной энциклопедии
Комментариев нет:
Отправить комментарий