Краткие теоретические сведения. Появление генетических алгоритмов (ГА) можно отнести к концу шестидесятых – началу семидесятых годов

Появление генетических алгоритмов (ГА) можно отнести к концу шестидесятых – началу семидесятых годов, когда они были впервые описаны в работе Дж. Холланда "Адаптация в природе и искусственных системах". Их общий смысл сводится к моделированию процесса эволюции. Как и в природе, задача алгоритма - отбор наиболее пригодных особей для дальнейшего участия в процессе воспроизводства и, таким образом, нахождение наиболее пригодного индивидуума-решения. Методы ГА эффективны при решении задач оптимизации, задач управления сложными динамическими объектами в условиях неопределенности.

При описании ГА используются определения заимствованные из генетики:

Популяция – конечное множество особей (индивидуумов), каждый индивидуум - эквивалент решения задачи.

Особи, входящие в популяцию, в генетических алгоритмах представляются хромосомами с закодированным в них множеством параметров задачи.

Хромосомы – упорядоченные последовательности генов.

Ген – атомарный элемент хромосомы, в ГА представлен в виде двоичных цифр (единица и нуль).

Генотип (структура) – набор хромосом данной особи.

Фенотип – набор значений, соответствующих данному генотипу.

Аллель – значение конкретного гена.

Локус (позиция) – место размещения данного гена в хромосоме. Множество позиций генов - Локи.

Следующее важное понятие ГА функция приспособленности (функция оценки). Она представляет собой меру приспособленности данной особи в популяции, позволяет оценить степень приспособленности конкретных особей в популяции и выбрать из них наиболее приспособленные (т. е. имеющие наибольшие значения функции приспособленности) в соответствии с эволюционным принципом выживания “сильнейших”. В задачах оптимизации функция приспособленности, как правило, максимизируется и называют ее в этом случае целевой функцией.

На каждой итерации ГА приспособленность каждой особи данной популяции оценивается при помощи функции приспособленности, и на этой основе создается следующая популяция особей, которая представляет собой множество потенциальных решений задачи. Очередная популяция в ГА называется поколением, а к вновь создаваемой популяции особей применяется термин “новое поколение” или “поколение потомков”.

Классический генетический алгоритм состоит из следующих этапов:

1) Инициализация – формирование исходной популяции, заключается в случайном выборе заданного количества хромосом (особей), представляемых в виде последовательности двоичных чисел.

2) Оценка приспособленности хромосом. Заключается в расчете функции приспособленности для каждой хромосомы популяции.

3) Проверка условия остановки алгоритма. Определяются условия завершения выполнения алгоритма. Алгоритм может быть остановлен по истечении определенного времени выполнения, либо после завершения заданного количества итераций. Остановка может произойти также в том случае, если работа алгоритма не приводит к улучшению уже достигнутого результата.

4) Селекция хромосом – заключается в выборе тех хромосом, которые будут участвовать в создании потомков для следующей популяции.

Среди методов селекции наиболее популярным является метод Рулетки. Метод Рулетки позволяет отбирать особей с помощью "запусков" рулетки. Колесо рулетки содержит по одному сектору для каждого члена популяции. В целом вся окружность колеса рулетки соответствует интервалу [0, 100]. Каждой хромосоме, обозначаемой для i=1,2,…, N (где N обозначает численность популяции) соответствует сектор колеса , выраженный в процентах согласно формулам (4.1) и (4.2)

(4.1)

(4.2)

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

5) Применение генетических операторов. Этот этап позволяет сформировать следующую популяцию потомков от уже созданной родительской популяции. Различают два генетических оператора: оператор скрещивания и оператор мутации.

Оператор скрещивания состоит из следующих шагов:

1. из родительской популяции случайным способом выбираются хромосомы и объединяются в пары.

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

Оператор мутации с вероятностью изменяет значение гена на противоположное (с 0 на 1 или обратно на позиции m).

6) Хромосомы, полученные в результате применения указанных генетических операторов, образуют новую популяцию, и вся предшествующая популяция хромосом заменяется полученной.

7) Выбор наилучшей хромосомы. Лучшей считается хромосома с наибольшим значением функции принадлежности.

Классический ГА можно представить следующим образом:

Начало /* генетический алгоритм */

Создать начальную популяцию

Оценить приспособленность каждой особи

Останов = FALSE

ПОКА НЕ останов ВЫПОЛНЯТЬ

НАЧАЛО /* создать популяцию нового поколения */

ПОВТОРИТЬ (размер популяции/2) РАЗ

НАЧАЛО /* цикл воспроизводства */

Выбрать две особи с высокой приспособленностью

из популяции

Скрестить выбранные особи и получить двух потомков

Поместить потомков в новое поколение

КОНЕЦ

ЕСЛИ популяция сошлась, ТО останов = TRUE

КОНЕЦ

КОНЕЦ

На рисунке 4.1 представлена блок – схема классического ГА.

Создание новой популяции

Рис. 4.1 - Блок – схема классического ГА