Подход к построению параллельного генетического алгоритма

Автор: Л.Г. Комарцова

Источник: [Ссылка]

Введение

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

Этот способ позволяет повысить генетическое разнообразие популяции и приводит к улучшению окончательного решения. Мотивом создания этого подхода является известный из генетики факт: гены формируют генотипы особей и определяют их свойства, из особей создаются популяции, а из популяций – биоценозы, являющиеся итогом прогрессивного развития нескольких популяций [7].

Существует ряд работ [1, 6], в которых предлагается использование параллельных ГА (ПГА) для повышения эффективности поиска оптимальных или близких к ним решений. Однако при использовании параллельных многопопуляционных ГА имеется ряд проблем, связанных с организацией поиска. В известных многопопуляционных ГА одновременно создается N начальных популяций P₁⁰, P₂⁰, P₃⁰,...,P_N⁰ которые развиваются независимо друг от друга, обмениваются хромосомами (мигрантами), затем снова развиваются независимо. Норма взаимодействия (количество обменных хромосом) регулируется с тем, чтобы каждая из популяций могла также создать «свои» уникальные хромосомы.

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

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

1. Модифицированный многопопуляционный алгоритм

Для повышения эффективности многопопуляционного алгоритма предлагается следующее решение. Первая проблема, связанная с определением момента взаимодействия хромосом разных популяций, может быть решена следующим образом. Вводится условие наступления события t_ν если сумма отклонений функции фитнесса Fit^max в текущем поколении и Fit^max за последние c поколений не превосходит некоторого заданного положительного числа δ, то развитие популяции не приводит к появлению лучших решений и наступает период взаимодействия. Параметр δ является одним из вспомогательных параметров ГА и задается пользователем перед началом его инициализации.

Пусть c – количество поколений, за которое производится оценка развития популяции (задается пользователем); δ_max – уровень улучшения решений устанавливается в пределах [0.1-0.2], а текущее отклонение определяется как усредненное за c поколений отношение:

Тогда процесс определения момента t_ν описывается следующим алгоритмом:

Если условие наступления события t_ν выполняется хотя бы для одной популяции, то происходит обмен хромосомами между этой популяцией и другой, выбранной случайным способом.

Для решения второй проблемы после наступления момента t_ν происходит ранжирование всех хромосом по функции Fit (по возрастанию). Из каждой популяции удаляется q⋅r худших хромосом (q – процент исключения; 0< q <1; r – количество хромосом в популяции), и на их место включается q⋅r лучших хромосом из другой популяции. Выбор обменных хромосом из каждой популяции осуществляется с вероятностью:

Условие останова многопопуляционного алгоритма ПГА – сумма разностей функций фитнесса разных популяций, участвующих в обмене, за c последних популяций меньше δ.

Так, если развиваются только две популяции, то условие останова за последние c может быть записано следующим образом:

Основной недостаток такого подхода – подбор параметров c, δ и других для каждой конкретной практической задачи.

2. Нечеткий параллельный генетический алгоритм

В предлагаемом нечетком ПГА вначале вся популяция разбивается на n подпопуляций (островов) случайным образом. Вычисляется значение функции Fit для каждой хромосомы острова. Определяется Fit^max и Fit^ср. всех островов. В качестве лигвистических переменных используются: Fit^ср. (столбцы табл.1) и разность Fit^max − Fit^ср. (строки табл.1). Вероятность кроссинговера – rc_i; вероятность мутации – rm_i; степень миграции в каждом острове – g_i, определяются на основе нечетких правил. Фрагмент нечетких правил для определения этих переменных может быть представлен, например, в табл.1.

Из представленной таблицы 1 можно извлечь, например следующее правило: IF Fit^ср. есть малое число (S) и разность Fit^max − Fit^ср. есть большое число (L), то получим следующий вывод: 1) вероятность кроссинговера – очень малая величина (СVS – Crossingover Very Small); 2) вероятность мутации – довольно большая величина (MLL – Mutation Large Large); 3) степень миграции – довольно большая величина (GLL). Далее по правилам нечеткой логики, зная вид функции принадлежности выходных нечетких переменных (в простейшем случае это может быть синглетон) и используя дефаззификацию, извлекаем числовое значение переменных rc_i, rm_i, g_i.

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

где k – постоянная величина. Миграция не выполняется, если g_i = 0. Выбор кандидатов – мигрантов может выполняться на основе турнирной селекции или другого оператора селекции. Количество мигрантов в i-ом поколении в этом случае вычисляется по формуле:

где P_o – начальная популяция острова.

Особенностью алгоритма является возможность объединения островов для убыстрения поиска элитной хромосомы [6]. Объединение островов осуществляется, когда средняя величина Fit^ср. некоторого острова превысила заданное начальное значение Fit^start, при этом число островов не должно стать меньше заданного значения. Объединяются в одну популяцию острова, имеющие первое и второе по значению Fit популяции. Предложенный алгоритм может быть представлен в виде следующей последовательности шагов.

3. Исследование эффективности нечеткого параллельного ГА

Тестирование разработанного алгоритма и многопопуляционного ГА (при числе популяций = 3) проводилось на функциях, минимум которых известен:

1. Функция Химмельблау [3]:
   F(x₁, x₂) = (x₁² + x₂ - 11)² + (x₁ + x₂² - 7)²
   Ограничения: −6 ⩽ x_i ⩽ 6, i=1,2.
   Минимум: F(X*) = 0, четыре глобальных экстремума.
2. Функция N переменных [4]:
   F(x₁,...,x_N) = exp(0.029U - (sin U)/(U²) sin U - 2U), где U = 2.25 ∑_n=1^N (x_n - x_n*)
   Ограничения: 0 ⩽ x_i ⩽ 10, i=1,2,...,10.
   Минимум: F(X*) = 0, для которого U = 0, x_n = x_n*, n = 1,2,...,N.
3. Функция Растригина N=10 [5]:
   F(x₁,...,x₁₀) = ∑_i=1¹⁰ (10 cos(2π x_i) - x_i² - 100)
   Ограничения: −5.12 ⩽ x_i ⩽ 5.12, i=1,2,...,10.
   Максимум: F(X*) = 0, функция имеет 1 глобальный и (10¹⁰−1) локальных экстремумов.
4. Функция Розенброка [5]:
   F(x₁,...,x₄) = 100(x₂ - x₁²)² + (1 - x₁)²
   Ограничения: −10 ⩽ x_i ⩽ 10, i=1,2.
   Минимум: F(X*) = 0.

В список функций, на которых проводилось исследование ГА, включена функция Розенброка, имеющая один локальный экстремум, функция Химмельблау, имеющая несколько глобальных экстремумов, а также сложные многоэкстремальные функции высокой размерности: Растригина (N = 10), функция N переменных, имеющие как локальные, так и глобальные экстремумы и практически не решаемые классическими методами оптимизации. Результаты экспериментов, усредненные по 10 запускам, представлены в табл. 2.

Результаты экспериментов показали, что разработанный алгоритм ГА-неч. позволяет в большей степени, чем ПГА, приблизиться к глобальному экстремуму, за счет подстройки параметров миграции на каждой стадии работы алгоритма оптимизации на основе нечетких правил.

Заключение

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