ПОДХОД К ПОСТРОЕНИЮ НЕЧЕТКОГО ПАРАЛЛЕЛЬНОГО ГЕНЕТИЧЕСКОГО АЛГОРИТМА

Л.Г. Комарцова

МГТУ им. Н.Э. Баумана (Калужский филиал)

e-mail: komlg@bmstu-kaluga.ru

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

Введение

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

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

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

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

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

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

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

Пусть c – количество поколений, за которое производится оценка развития популяции (задается пользователем); d_max - уровень улучшения решений устанавливается в пределах [0,1- 0,2], а текущее отклонение определяется как усредненное за c поколений отношение

, i=1, …, c. (1)

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

Шаг 1. Установление значений c и d; t - текущая итерация ГА .

Шаг 2. максимальное значение Fit в предыдущем поколении;

Шаг 3. Запоминание t; счетчик номера поколения;

Шаг 4. S=0; усредненное отклонение;

Шаг 5. k=с; счетчик числа поколений для рассматриваемой популяции;

Шаг 6. Если k>0, то переход ш.7, иначе ш.12;

Шаг 7. ; определение max Fit в текущем поколении;

Шаг 8. ;

Шаг 9. ;

Шаг 10. k=k -1; t=t+1;

Шаг 11. Переход ш.6.

Шаг 12. Если S/c >d, то переход ш.4, иначе ш.13.

Шаг 13. t_v=t

Шаг 14. Останов.

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

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

(2)

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

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

за последние c поколений.

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

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

В предлагаемом нечетком ПГА вначале вся популяция разбивается на n подпопуляций («островов») случайным образом. Вычисляется значение функции Fit для каждой хромосомы острова. Определяется Fit_max и Fit_ср. всех островов. В качестве лигвистических переменных используются: Fit_cp. (столбцы табл.1) и разность Fit_max - Fit_cp (строки табл.1). Вероятность кроссинговера - ; вероятность мутации - ; степень миграции в каждом острове - определяются на основе нечетких правил. Фрагмент нечетких правил для определения этих переменных может быть представлен, например, в табл.1

Таблица 1

Из представленной таблицы 1 можно извлечь, например следующее правило:

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

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

, (3)

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

, (4)

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

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

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

Шаг 1 . Формирование начальной популяции.

Шаг 2. Селекция хромосом.

Шаг 3. Вычисление функции Fit островов.

Шаг 4 . Проверка возможности объединения островов.

Шаг 5. Если «да», то объединение островов и переход к ш. 6

Шаг 6. Эволюция островов. Вычисление степени миграции по формуле (3).

Шаг 7. Вычисление вероятности и применение кроссинговера и мутации.

Шаг 8. Вычисление Fit_ср. и Fit_max островов.

Шаг 9. Вычисление элитной хромосомы.

Шаг 10. Проверка критерия останова.

Шаг 11. Если «да», то Останов, иначе переход к 2.

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

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

1. Функция Химмельблау [3]:

.

Ограничения:. Минимум:четыре глобальных экстремума.

2. Функция N переменных [4]:

,

Ограничения:

Минимум: , для которой

3. Функция Растригина N=10 [5]:

Ограничения:

Максимум: функция имеет 1 глобальный и (10¹⁰-1) локальных экстремумов.

4. Функция Розенброка [5]:

.

Ограничения: .

Минимум: .

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

Сравнительный анализ результатов оптимизации Таблица 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.