Простой генетический алгоритм

Для применения ГА необходимо:

1. выделить совокупность свойств объекта, характеризуемых внутренними параметрами и влияющих на его полезность, т.е. выделить множество управляемых параметров среди могут быть величины различных типов (real, integer, Boolean, enumeration). Наличие нечисловых величин (enumeration) обусловливает возможность решения задач не только параметрической, но и структурной оптимизации;

2. сформулировать количественную оценку полезности вариантов объекта — функцию полезности . Если в исходном виде задача многокритериальна, то такая формулировка означает выбор скалярного (обобщенного) критерия;

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

4. представить вектор в форме хромосомы — записи следующего вида (см. рис. 1).

Рис. 1. Хромосома

В ГА используется такая терминология:

· ген — управляемый параметр ;

· аллель — значение гена;

· локус (позиция) — позиция, занимаемая геном в хромосоме;

· генотип — экземпляр хромосомы, генотип представляет совокупность внутренних параметров проектируемого с помощью ГА объекта;

· генофонд — множество всех возможных генотипов;

· функция полезности (приспособленности) — целевая функция;

· фенотип — совокупность значений критериев, получаемых после декодирования хромосомы, под фенотипом часто понимают совокупность выходных параметров синтезируемого с помощью ГА объекта.

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

Далее организуется циклический процесс смены поколений:

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

Рассмотрим алгоритмы выполнения операторов в простом генетическом алгоритме.

1. Выбор родителей.

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

(1)

где — наихудшее значение целевой функции среди экземпляров (членов) текущего поколения, — значение целевой функции -го экземпляра.

Правило (1) называют правилом колеса рулетки. Если в колесе рулетки выделить секторы, пропорциональные значениям , то вероятности попадания в них суть , определяемые в соответствии с (1).

Пример 1

Пусть , значения и приведены в табл. 1.

Таблица 1

			0,5
			0,1
			0,4

2. Кроссовер (скрещивание).

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

Таблица 2

3. Мутации.

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

4. Селекция.

После каждого акта генерации пары потомков в новое поколение включается лучший экземпляр пары.

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