Назад в библиотеку

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

Автор: Л.Г. Комарцова
Источник: [Ссылка]

Аннотация

Предложен нечеткий адаптивный подход подстройки параметров параллельного генетического алгоритма для повышения вероятности нахождения лучшего решения на основе динамического объединения подпопуляций.

Введение

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

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

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

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

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

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

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

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

Fit max t i Fit max t i 1 Fit max t i ,   i = 1,..., c.             (1)

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

  1. Установление значений c и δ; t – текущая итерация ГА .
  2. Fit max t i = 0 ; максимальное значение Fit в предыдущем поколении;
  3. Запоминание t; счетчик номера поколения;
  4. S=0; усредненное отклонение;
  5. k=с; счетчик числа поколений для рассматриваемой популяции;
  6. Если k>0, то переход к ш.7, иначе к ш.12;
  7. Fit max t = max Fit H t ; определение max Fit в текущем поколении;
  8. S = S + Fit max t i Fit max t i 1 Fit max t i
  9. Fit max t i 1 = Fit max t i
  10. k = k 1;   t = t + 1;
  11. Переход к ш.6.
  12. Если S c > δ , то переход к ш.4, иначе к ш.13.
  13. t ν = t
  14. Останов.

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

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

p i = Fit H i t ν j = 1 n Fit H j t ν             (2)

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

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

Fit max I Fit max II c × max Fit max I ,  Fit max II < δ

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

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

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

Переменная S M L
S CLS
MVL
GVL
CLL
MLL
GLL
CVL
MM
EM
M CS
ML
GL
CM
MLL
GLL
CL
MS
GS
L CVS
MLL
GLL
CLS
MLS
GLS
CLL
MVS
GVS

Таблица 1

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

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

r g i = k g i ,            (3)

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

M i = r g i P o ,            (4)

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

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

Предложенный алгоритм может быть представлен в виде следующей последовательности шагов.

  1. Формирование начальной популяции.
  2. Селекция хромосом.
  3. Вычисление функции Fit островов.
  4. Проверка возможности объединения островов.
  5. Если да, то объединение островов и переход к ш. 6
  6. Эволюция островов. Вычисление степени миграции по формуле (3).
  7. Вычисление вероятности и применение кроссинговера и мутации.
  8. Вычисление Fitср. и Fitmax островов.
  9. Вычисление элитной хромосомы.
  10. Проверка критерия останова.
  11. Если да, то Останов, иначе переход к 2.

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

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

  1. Функция Химмельблау [3]:
    F x 1 , x 2 = x 1 2 + x 2 11 2
    Ограничения: −6⩽xi⩽6, i=1,2.
    Минимум: F(X*) = 0, четыре глобальных экстремума.
  2. Функция N переменных [4]:
    F x 1 ,..., x N = exp 0.029 U sin U U 2 sin U 2 U ,  где   U = 2.25 n = 1 N x n x n *
    Ограничения: 0⩽xi⩽10, i=1,2,...,10.
    Минимум: F(X*) = 0, для которого U = 0, xn = xn*, n = 1,2,...,N.
  3. Функция Растригина N=10 [5]:
    F x 1 ,..., x 10 = i = 1 10 10 cos 2 π x i x i 2 100
    Ограничения: −5.12⩽xi⩽5.12, i=1,2,...,10.
    Максимум: F(X*) = 0, функция имеет 1 глобальный и (1010−1) локальных экстремумов.
  4. Функция Розенброка [5]:
    F x 1 ,..., x 4 = 100 x 2 x 1 2 2 + 100 1 x 1 2
    Ограничения: −10⩽xi⩽10, i=1,2.
    Минимум: F(X*) = 0.

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

Химмельблау Растригина N переменных Розенброка
ПГА ГА-неч. ПГА ГА-неч. ПГА ГА-неч. ПГА ГА-неч.
Мат. ожид. 0,1901 0,2061 -13,42 -6,992 1,189 1,107 0,232 0,175
Дисперсия 0,0154 0,0281 4,6370 3,271 0,156 0,153 0,356 0.2752
Min знач. 0,0001 0 -28,17 -16,09 0,445 0,445 0,001 0
Max знач. 0,9973 0,2094 -4,821 -1,151 1,441 1,440 2,488 1,422

Таблица 2

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

Заключение

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

Список использованной литературы

  1. Курейчик В.М., Курейчик В.В. Эволюционные, синергетические и гомеостатические стратегии в искусственном интеллекте: сосотояние и перспективы // Новости искусственного интеллекта. – №3. – 2000. – С.39-65.
  2. Комарцова Л.Г., Голубин А.В. Адаптация параметров генетических алгоритмов при поиске решений // Сборник научных трудов. Научная сессия МИФИ-2003. – М.:МИФИ. – 2003. Том.3. С.124-125.
  3. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация // Пер. с англ. – М.: Мир. – 1985.
  4. Реклейтис А., Рейвиндран А. и др. Оптимизация в технике. – В 2-х кн.– М.:Мир. – 1988.
  5. Батищев Д.И. Поисковые методы оптимального проектирования. – М.:Советское радио. – 1975.
  6. Y. Maeda Fuzzy Adaptive Search Method for Genetic Programming. – Int. Journal of Advanced Computational Intelligence. – vol.3. – No.2, pp. 131-135 (1999).
  7. Комарцова Л.Г. Проблемы построения генетических алгоритмов с динамическими параметрами. – Сб. научных трудов IV Межд. научно-практ. конф. Интегрированные модели и мягкие вычисления в искусственном интеллекте. – М.: Физматлит. – 2007. – С. 391-396.