Лабораторная работа № 4 Решение оптимизационных задач с помощью генетических алгоритмов

Цель работы

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

1. Краткие теоретические сведения

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

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

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

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

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

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

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

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

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

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

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

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

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

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. Выбор наилучшей хромосомы. Лучшей считается хромосома с наилучшим значением функции приспособленности.