по теме лабораторной работы

Генетические алгоритмы (ГА) - это адаптивные методы поиска, построенные с использованием принципов теории биологической эволюции Ч. Дарвина. По аналогии с эволюционным механизмом, ГА работают с популяцией, в которой каждая из входящих в нес хромосом представляет собой возможное решение данной задачи. Каждая хромосома оценивается мерой её приспособленности (fill ness function), которую называют также функцией пригодности. Наиболее приспособленные особи получают возможность «воспроизвести» потомство с помощью перекрестного скрещивания (crossingover) с другими особями (индивидуумами) популяции. В результате появляются новые особи, сочетающие в себе характеристики, наследуемые от родителей.

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

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

Пример хромосомы, кодирующей четыре параметра (х₁, х₂, х₃, х₄) представлен на рисунке 1.

_ x₁_____ x₂_____ x₃____ _ x₄____

Рис. 1 - Пример хромосомы для четырех параметров

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

В ходе выполнения ГА осуществляется последовательное выполнение следующих генетических операций:

1) отбор (селекция). В общем случае, отбор производится на основе вероятностей P_i(s_i), вычисленных для каждого из индивидуумов.s', популяции, i = 1,2,..., М). Наиболее часто применяются следующие схемы отбора:

-пропорциональный отбор:

(1)

-линейное ранжирование:

(2)

где =2- и 1

-равномерное ранжирование:

(3)

где - некоторое фиксированное число первых членов популяции.

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

2) кроссовер (кроссинговер). Одноточечный кроссовер (скрещивание) представляет собой оператор рекомбинации и применяется по отношению к паре хромосом из популяции S(t), прошедших отбор. Назначается вероятность выполнения кроссовера Р_кр. Далее, для случайно выбранной пары хромосом определяется случайное число k {1, 2,..., n - 1}, называемое местом (или позицией) кроссовера, и затем биты из двух выбранных хромосом меняются местами после k-го бита с вероятностью Р_кр (см. рис. 2). Этот процесс повторяется для других выбранных хромосом до тех пор, пока популяция S(t) не окажется пустой. Обычно, Р_кр [0,6; 0,99].

В общем случае, ГА с рекомбинацией (m,k) использует оператор кроссовера по схеме m:k (m родителей, k потомков).

Рис. 2 - Операция кроссовера

Существуют также схемы двухточечного, трехточечного и т.д. кроссовера. Предельным случаем является равномерный кроссовер, когда каждая пара бит внутри хромосом-родителей обмениваются битами в соответствии с определенной вероятностью;

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

Обычно мутация представляет собой случайное изменение бита, ве­роятность которого довольно низкая (Р_мут [0,001; 0,01]) (см. рис. 3).

Рис. 3 - Операция мутации

Постановка задачи размещения разногабаритных элементов в пространстве обычно формулируется следующим образом:

-заданы ограничения на объем размещения (например - габариты конкретного корпуса);

-заданы габариты (размеры) элементов размещения;

На практике широкое распространение получила задача размещения элементов на установочной площади, которую называют монтажным полем. Каждый элемент, предназначенный для размещения, в этом случае представляется своей установочной площадью, которая упрощенно представляется прямоугольником с двумя габаритами: длиной и шириной.

Исходными данными задачи являются: а, b - габариты монтажного поля; {(а₁, Ь₁),...,(а_i, 6_i),…, (а_n, 6_n)} - множество габаритов элементов размещения; С - матрица связей элементов, представляющая собой матрицу связности. Необходимо найти такой вариант размещения элементов на монтажном поле: Z= {(x₁, y₁), …,(x_i,y_i), …,(x_n,y_n)},где (x_i,y_i) - координаты центра тяжести установочной площади i-го элемента размещения, при котором площадь перекрытия размещения элементов была бы равна нулю.

Решение задачи размещения сводится к решению задачи оптимизации целевой функции, представляющей собой сумму штрафа за перекрытие площадей размещаемых элементов.

Пример:

1. Ввести исходные данные габаритов элементов согласно табл. 1. Выбрать в качестве критерия останова ГА достижение числа поколений заданной величины, число поколений принять равным 300.

Таблица 1 - Исходные данные задачи

Исходные данные	Вариант 1	Вариант 2	Вариант 3	Вариант 4
Габариты монтажного пространства	100x100	100x100	100x100	100x100
Элемент 1	24x10	12x28	10x10	25x45
Элемент 2	32x40	31x40	20x18	22x14
Элемент 3	32x15	15x25	11x24	11x10
Элемент 4	20x22	12x50	30x45	31x16
Элемент 5	10x48	21x19	31x18	20x24
Элемент 6	17x20	20x22	45x19	Г 16x22
Элемент 7	41x33	39x33	35x32	40x35
Элемент 8	25x47	49x17	28x20	24x50
Элемент 9	20x20	15x29	20x19	25x27
Элемент 10	9x10	10x10	10x50	13x13
Вероятность кроссовера	0,6	0,6	0,6	0,6
Вероятность мутации	0,05	0,05	0,05	0,05
Размер популяции (М)

Ввод числа и габаритов элементов осуществляется в диалоговом окне «Входные параметры» (меню «Алгоритм —> Входные параметры») см.рис.3). Параметры матрицы связности в данной работе не используются.

Настройка параметров генетического алгоритма осуществляется в диалоговом окне «Параметры эволюции» (меню «Алгоритм→Параметры эволюции») (см. рис. 4).

2.Сгенерировать начальное размещение элементов на монтажном пространстве, используя пункт меню «Алгорим→Генерация исходной популяции».

3.Запустить алгоритм на выполнение с помощью кнопки «Запуск» на панели инструментов, либо пункта меню «Алгоритм → Эволюция».

Рис. 4 - Диалоговое окно ввода входных параметров

4.Занести в отчет график зависимости значения целевой функции от времени эволюции (числа поколений) (пункт меню «Просмотр —> Статистика»), количество мутаций и площадь пересечения элементов.

5.Уменьшить значение размера популяции с 200 на 100. Повторить работу, начиная с пункта 2.

6.Увеличить значение размера популяции со 100 на 200, значение вероятности кроссовера на 0,99. Повторить работу, начиная с пункта 2.

7.Изменить значение вероятности кроссовера на 0,6, значение вероятности мутации на 0,1. Повторить работу, начиная с пункта 2.

8.Изменить значение вероятности мутации на 0,05. В основном окне программы выбрать алгоритм «стратегия с рекомбинацией (т. к)». В окне параметров эволюции (см. рис. 4) задать соотношение числа родителей к потомкам (4, 1). Повторить работу, начиная с пункта 2.

9.Повторить пункт 8, последовательно изменяя соотношение числа родителей к потомкам (т, к). Сопоставить результаты работы алгоритма.

Рис. 5 - Параметры генетического алгоритма

Задания для лабораторной работы:

1. Начальное размещение элементов на монтажном пространстве для каждого пункта задания, графики зависимости целевой функции от времени эволюции, количество мутаций за время работы алгоритма;

2. Сравнительный анализ результатов, полученных по каждому из пунктов;

3. Выводы о качественном и количественном влиянии параметров эволюции на работу генетического алгоритма.

Контрольные вопросы:

1. Дайте определение генетического алгоритма.

2. Что понимается под стандартным генетическим алгоритмом?

3. В чем отличие стандартного генетического алгоритма от стандартных алгоритмов оптимизации?

4. Какие основные параметры используются в стандартном генетическом алгоритме?

5. Каковы отличия стандартного генетического алгоритма от алгоритма с рекомбинацией?