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



Скачать 95.36 Kb.
Дата16.10.2012
Размер95.36 Kb.
ТипДокументы
ПОДХОД К ПОСТРОЕНИЮ НЕЧЕТКОГО ПАРАЛЛЕЛЬНОГО ГЕНЕТИЧЕСКОГО АЛГОРИТМА

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

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

e-mail: komlg@bmstu-kaluga.ru
Предложен нечеткий адаптивный подход подстройки параметров параллельного генетического алгоритма для повышения вероятности нахождения лучшего решения на основе динамического объединения подпопуляций.
Введение
Генетическим алгоритмам изначально присущ внутренний параллелизм, и одним из способов распараллеливания ГА является одновременное развитие нескольких популяций. Взаимодействие между ними осуществляется с помощью механизма миграций.

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

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

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

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

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

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

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

Шаг 1. Установление значений c и ; 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 >, то переход ш.4, иначе ш.13.

Шаг 13. tv=t

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

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

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

(2)

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

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



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

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

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




S

M

L

S

CLS

MVL

GVL

CLL

ML

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 можно извлечь, например следующее правило:

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

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

, (3)

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

, (4)

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

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

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

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

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

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

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

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

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

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

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

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

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

Шаг 11. Если «да», то Останов, иначе переход к 2.
3. Исследование эффективности нечеткого параллельного ГА

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

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

.

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

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

,



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

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

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



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

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

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

.

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

Минимум: .

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




Химмельблау

Растригина

N=10

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


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

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

  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.

Похожие:

Подход к построению нечеткого параллельного генетического алгоритма iconМета-оптимизация на основе самоорганизующихся карт кохонена и генетического алгоритма
Метод использует кластеризацию множества задач рассматриваемого класса с помощью самоорганизующихся карт Кохонена и решение собственно...
Подход к построению нечеткого параллельного генетического алгоритма iconНейронных сетей на основе комбинирования информационных технологий
Предложена модификация комбинированного алгоритма обучения многослойного персептрона, позволяющая с помощью алгоритма имитации отжига...
Подход к построению нечеткого параллельного генетического алгоритма iconПодход к построению гидродинамических моделей на основе онтологии
В докладе предлагается подход к построению моделей, описывающих движение сплошной среды, на основе онтологии. Описываются основные...
Подход к построению нечеткого параллельного генетического алгоритма iconПрименение параллельного алгоритма Bicgstab для решения трёхмерной упругопластической задачи 1
Применение параллельного алгоритма Bicgstab для решения трёхмерной упругопластической задачи1
Подход к построению нечеткого параллельного генетического алгоритма iconМетод генетического программирования для решения задачи оптимального управления
Приведен метод поиска решения на основе генетического алгоритма в виде функциональной зависимости управления от времени и начальных...
Подход к построению нечеткого параллельного генетического алгоритма iconУдк 658. 512 011. 5 Нечеткий оператор кроссинговера для задачи трассировки коммутационного блока
Использование данной схемы дает преимущества по увеличению генетического разнообразия внутри популяции, что приводит к снижению вероятности...
Подход к построению нечеткого параллельного генетического алгоритма iconМетодология нечеткого управления автономной фотоветроэнергетической системой
Предлагается применение метода нечеткого управления, основанного на продукционных правилах. Приводится упрощенный пример нечеткого...
Подход к построению нечеткого параллельного генетического алгоритма iconНазвание «Оптимизация многоэкстремальных функций на основе кластерной модификации генетического алгоритма»

Подход к построению нечеткого параллельного генетического алгоритма iconО применении модифицированного генетического алгоритма для решения задачи контроля границ беспроводной локальной сети

Подход к построению нечеткого параллельного генетического алгоритма iconОценка эффективности работы генетического алгоритма в условиях цветного шума для разложения спектральных контуров

Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org