5.8.  Генетический поиск с миграцией особей

Генетические алгоритмы, в которых используется одна популяция особей для поиска решения, не всегда оказываются эффективными. Основной их недостаток — попадание в локальный оптимум. В § 4.2 уже была представлена модифицированная схема миграции с искусственной селекцией (рис. 4.8), основанная на механизмах макроэволюции. В данном разделе рассмотрим еще одну модифицированную схему генетического поиска с миграции особей. В этой схеме на макроуровне параллельно эволюционируют две идентичных популяции, между которыми существует миграция особей (рис. 5.40). Обе популяции осуществляют поиск наилучшеш решения для одной и той же задачи. Миграция особей призвана «взбалтывать» популяции и выводить их из локальных оптимумов.

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

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

Миграция особей может происходить по разным законам. По аналогии с человеческим обществом это может быть может «утечка мозгов», когда популяцию покидают особи с наилучшими значениями ФП, или миграция «низкоквалифицированной дешевой рабочей силы», когда мигрируют особи с наименьшим значением ФП. Помимо качественного состава мигрантов (значения ФП) на эффективность миграции может оказывать влияние и его количественный состав (какой процент популяции участвует в обмене). Таким образом, в данной схеме процесс миграции определяется двумя величинами — числом мигрирующих особей и их ФП:

1.   к — число мигрантов. Данный параметр определяет число мигрантов, которое переходит из популяции в популяцию на каждом шаге работы алгоритма.

2.   ДФП — способ миграции. Данный параметр определяет, какие особи будут использоваться для миграции, и рассчитывается на основе ФП мигрирующих особей:

где ФПі — значение ФП особи из популяции 1; ФП2 — значение ФП особи из популяции 2.

В гибридных системах выбор оптимальных значений этих переменных должна обеспечивать ЭС, основываясь на анализе работы схемы при решении оптимизационной задачи конкретной проблемной области. Мы же исследуем свойства рассматриваемой схемы на примере решения простой оптимизационной задачи (см. пп. 5.2.1). Задача оптимизации заключается в нахождении переменных Х\ и Х^ на которых достигается максимум

значения функции:

Область определения перемен

ных — [0,1]. Как следует из вида функции, максимальное значение достигается в точке с координатами (1,1) и оно равно 1.

При решении задачи с помощью ПГА переменные Х\ и Х2 кодируются в виде битовой строки длинной I битов каждая. Значения переменных определяются следующим образом: битовая строка рассматривается как двоичное целое без знака в диапазоне [0, 21 — 1], это число делится на 21. Следовательно, получаемое при этом значение лежит в диапазоне [0,1 — 2—г], а пространство оптимизации становится дискретным с шагом сетки 2~1.

Исследования проводились на имитационной модели, моделирующей развитие популяций и миграцию особей между ними.

Количество поколений работы алгоритма модифицированной схемы с миграцией зависит от момента остановки алгоритма, который, в свою очередь, в данной схеме определяется из условия:

где ФПтах — максимальное значение функции пригодности для особи

в пределах обеих популяций; ФПср — среднее значение функции пригодности по популяции, в которой существует особь с ФПтах.

Количество особей в каждой популяции модифицированной схемы определяется в зависимости от доверительного интервала разброса значений ФП для особей, который определяется по формуле

с доверительной вероятностью Р = 90%; где ФПтіп — минимальное значение функции пригодности по популяции, в которой существует особь с ФПпіах.

Для данной задачи была получена зависимость доверительного интервала в установившемся режиме от числа особей в популяции, которая позволяет выбрать наиболее рациональное число особей в популяции с учетом времени работы алгоритма. Данная зависимость приведена на рис. 5.41.

Так как время работы алгоритма пропорционально числу особей в популяции, то необходимо выбрать такое число особей в популяции, при котором достигается достаточ ная точность работы алгоритма, это зависит от величины доверительного интервала и относительно небольшого времени работы алгоритма. Учитывая это, окончательно выбираем по зависимости, изображенной на рис. 5.41, число особей в популяции, равное 20. При этом значение доверительного интервала L = 0,07, с доверительной вероятностью Р = 0,9. Вероятность скрещивания в ПГА принимаем равной 0,6, вероятность мутации равна 0,1.

На рис 5.42 и 5.43 приводятся зависимости скорости сходимости алгоритма (модифицированной схемы) и эффективности использования модифицированной схемы от числа мигрантов (т. е. первого параметра процесса миграции).

Эффективность модифицированной схемы оценивается в сравнении с ПГА и рассчитывается по формуле:

где ФПм — среднее (по результатам 10 экспериментов) значение максимальных ФП при использовании модифицированной схемы генетического поиска; ФПпгл — среднее (по результатам 10 экспериментов) значение максимальной ФП при использовании ПГА.

Из приведенных зависимостей видно, что при числе мигрантов, равном 5, достигается наибольший эффект. Количество особей в популяции равно 20, поэтому наибольший эффект достигается при числе мигрантов, равном 25% от числа особей в популяции.

На рис 5.44 изображены графики изменения ФП по поколениям для различных случаев миграции, т. е. в зависимости от значения ДФП. Кривая «С миграцией 1» имеет значение АФПі, а кривая «С миграцией 2» — значение АФП2, причем АФПі > ДФП2. Анализируя данные зависимости, можно сделать вывод о том, что при ДФП = max достигается наибольший эффект от миграции особей. То есть, чем больше разница ФП у особей мигрирующих из разных популяций, тем эффективнее работает схема.

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