Очевидно, что эффективность генетического поиска зависит от типов используемых в ГА операторов и других параметров алгоритма. К числу таких параметров можно отнести вероятности кроссовера и мутаций, вероятности выбора тех или иных эвристик в методе комбинирования эвристик, число точек разрыва хромосом при кроссовере и др. Как правило, генетические операторы и параметры определяются пользователем априорно, однако при этом велика опасность использования неудачных вариантов и, как следствие, значительное снижение эффективности генетического поиска. Кроме того, на разных этапах генетического поиска те или иные операторы могут быть эффективными в различной степени. Выход из ситеации — применение адаптивных генетических алгоритмов.
Известен ряд работ, посвященных адаптивным ГА. Идея адаптации применительно к ГА высказывалась в тработе [1]. Наибольшее внимание уделялось алгоритмам с использованием адаптации к такому параметру, как вероятность мутации. Так, в работе [2] рассмотрена стратегия, при которой вероятность мутации изменяется с ходом эволюции и для каждой хромосомы вероятность мутации настраивается индивидуально.
Метагенетический алгоритм с использованием генетического поиска для решения как основной задачи, так и вспмомогательной задачи настройки параметров адаптации предложен в [3]. Ниже приведено его описание в виде псевдокода.
GENETIC ALGORITHM STEP()
begin
for i = 1 to n {
select parent1 and parent2 from population P1;
offspring = crossover(parent1, parent2)
mutation(offspring)
if suited(offspring) then
replace(P1, offspring);
}
end
META-GENETIC ALGORITHM
begin
create initial population P1;
create initial population P2;
do{
for i = 1 to n {
select parent1 and parent2 from P2;
offspring = crossover(parent1, parent2)
mutation(offspring)
evaluate(offspring)
add offspring tmpPop
}
meta-population = tmpPop;
}
GENETIC ALGORITHM STEP(select answer from P2)
} until stopping condition
//report the best answer;
end.
Рассматриваются два множества хромосом. В генах хромосом первого множества (P1) хранятся номера эвристик для выполнения очередного шага синтеза решения. Вторая популяция (P2) состоит из хромосом, в генах которого хранятся конфигурационные параметры для основного генетического алгоритма.
Каждая хромосома из популяции P2 оценивается следующим образом:
SIMPLE_STEP ( P2(ti) )
begin
P2(ti)->select parent1 and parent2 from population P1;
offspring = P2(ti)->crossover(parent1, parent2)
P2(ti)->mutation(offspring)
return P2(ti)->evaluate(offspring)
end
Для каждой конфигурации (для каждой хромосомы популяции P2(ti)) выполняется процедура SIMPLE_STEP, в которой из популяции P1 выбираются (P2(ti)->select) родители. В результате их скрещивания (P2(ti)->crossover) появляется потомок (offspring) – новая хромосома, которая впоследствии мутируется (P2(ti)->mutation). Оценка потомка также является оценкой для данной конфигурации P2(ti).
После очередной генерации метагенетического алгоритма с помощью метода турнирной селекции из популяции P2 выбирается хромосома, и с данной конфигурацией формируется очередное поколение с помощью основного генетического алгоритма.
В Simple GA начальная популяция генерируется случайным образом. Впоследствии, сгенерированная популяция оценивается, и из нее n раз выбираются два решения, от скрещивания которых генерируются два потомка. Созданные индивидуумы подвергаются мутации с заданной вероятностью.
Этот цикл повторяется до тех пор, пока новая популяция не заполнится. Когда новая популяция заполняется, старая может быть удалена с сохранением наилучших решений.
Список литературы
1. Батищев Д.И., Исаев С.А. Оптимизация многоэкстремальных функций с помощью генетических алгоритмов. — http://www.algo.4u.ru/
2. Back T. Self-Adaptation in Genetic Algorithms. In Toward a Practice of Autonomous Systems: Proceedings of the First European Coneference on Artificial Life, 1992.
3. Норенков И.П., Арутюнян Н.М. Адаптивные генетические алгоритмы // Информационные технологии, 2007, N 3