Генетические алгоритмы. Адаптивные методы поиска.

Генетические алгоритмы – адаптивные методы поиска, которые в последнее время часто используются для решения задач функциональной оптимизации. Они основаны на генетических процессах биологических организмов: биологические популяции развиваются в течении нескольких поколений, подчиняясь законам естественного отбора и по принципу «выживает наиболее приспособленный».

Задачи оптимизации - наиболее распространенный и важный для практики класс задач. Многие реальные задачи могут быть сформулированы как поиск оптимального значения, где значение – сложная функция, зависящая от некоторых параметров.

Работа ГА представляет собой итерационный процесс, который продолжается до тех пор, пока не выполняется заданное число поколений или какой-либо иной критерий остановки. Параметры задачи являются генетическим материалом – генами, совокупность которых составляет хромосому.

Каждая особь обладает своей хромосомой, а, следовательно, своим набором параметров. Подставив параметры в целевую функцию, будем получать значение характеристики особи – приспособленность.

На рис. 2 изображена блок-схема работы ГА, используемого для программной реализации. Вначале случайным образом генерируется начальная популяция «особей» (пары координат и ), затем моделируется размножение внутри этой популяции. После чего хромосомы новых «особей» с определенной заданной вероятностью могут мутировать (изменить некоторые гены). Следующим шагом является уничтожение старой популяции, и переход к рассмотрению следующего поколения. Теперь описанные процедуры отбора, скрещивания и мутации повторяются уже для новой популяции и т. д.

Отбор. На данном этапе оценивается приспособленность каждой особи. В лабораторной работе используется турнирный отбор. При данном виде отбора все особи из поколения делятся на пары, внутри которых происходит сравнение значений приспособленности. Особь с большим значением приспособленности допускается к скрещиванию, а с меньшим – отсеивается. Турнирный отбор может проходить в несколько стадий в зависимости от числа особей необходимых для осуществления скрещивания (в лабораторной работе используется отбор в один тур).

Скрещивание. В ГА за передачу потомкам признаков родителей отвечает оператор, который называется кроссинговер или кроссовер. Действует он следующим образом: из популяции выбираются две особи, которые будут родителями, определяется (случайным образом) точка разрыва родительской хромосомы, потомок определяется как конкатенация части первого и второго родителя.

По количеству точек разрыва родительских хромосом кроссинговер может быть одноточечным и n-точечным (одна и n точек разрыва соответственно). В реализации лабораторной работы используется одноточечный случай.

Мутация – это преобразование хромосом, случайно изменяющее одну или несколько её позиций (генов). Наиболее распространённый вид мутации – случайное изменение только одного из генов хромосомы (используется в работе). Этот генетический оператор предназначен для того, чтобы поддерживать разнообразие особей в популяции, а также способствует защите от преждевременной сходимости.