Вероятностные и компактные генетические алгоритмы

8.1. Вероятностные генетические алгоритмы

Рассмотрим представление популяции вектором вероятностей на следующем примере для трех различных популяций состоящих из четырех хромосом дан ниже:

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

Впервые такое представление было введено в [1] (Equilibrium Genetic Algorithm) и взято за основу в последующих работах [2,3,4,5,6]. В [1] на этой основе проведены теоретические исследования вопросов сходимости ГА и показано, что для ряда классических задач вероятностный ГА дает результаты, не уступающие стандартному ГА с однородным кроссинговером и стратегией элитизма при отборе родителей.

В этом случае эволюция популяции соответствует траектории в гиперкубе пространства $$(p_1,p_2,\dots ,p_N)$$. Траектория начинается в середине единичного гиперкуба ($$p_i=0,5$$ для всех $$1\le i\le N$$) и заканчивается в одной из его вершин, которая соответствует найденному решению (двоичному коду), как это показано на рис.8.1.

В классическом ГА популяция представляется множеством двоичных векторов и изменяется путем применения операторов репродукции, кроссинговера и мутации. "Вероятностный" ГА работает не с исходной популяцией (множеством двоичных векторов), а непосредственно с ее вероятностным представлением – вектором вероятностей $$P=(p_1,p_2,\dots ,p_N)$$. В этом случае [1] генетические операторы выполняются следующим образом.

Репродукция. В соответствии с текущим распределением вероятностей $$P$$ генерируется некоторое (относительно небольшое) множество двоичных векторов – особей. Для каждой из построенных особей вычисляется значение фитнесс-функции. Затем вектор вероятностей $$P$$ сдвигается в сторону особи $$v$$ (вершины гиперкуба), имеющей лучшее значение фитнесс-функции: $$P'=(1-\theta)P+\theta v$$. Здесь $$\theta\in(0;1)$$– фиксированное вещественное число. Если несколько особей имеют наилучшее значение, то случайным образом выбирается одна из них.

Мутация. Каждая координата вектора $$P$$ корректируется случайным образом с вероятностью $$p'_i=(1-\mu)p_i+\mu z_i$$, где $$\mu\in(0;1)$$– вещественный параметр, а $$z_i$$ принимает значения и с равной вероятностью. Таким образом, $$p_i$$ сдвигается на небольшое расстояние в направлении или в соответствии со случайным значением $$z_i$$. В [1] показано, что оператор кроссинговера в этом случае не является необходимым.

Очевидно, что из построенного вектора вероятностей $$P$$ легко получить двоичный вектор, представляющий решение задачи. Если $$p_i=1$$ (или близко к 1), то значение гена $$x_i=1$$, в противном случае $$x_i=0$$. Эксперименты показали, что для некоторых задач этот подход дает результаты, сравнимые с классическим ГА при меньших затратах вычислительных ресурсов.

8.2. Пошаговое обучение на основе виртуальной популяции

Следующим рассмотрим подход, предложенный в [2] – PBIL (Population-Based Incremental Learning). На основе представления популяции вектором вероятности $$P=(p_1,p_2,\dots ,p_N)$$ вместо стандартного ГА используется следующий алгоритм поиска оптимального решения:

Как видно из псевдокода, виртуальная популяция каждый раз случайным образом генерируется согласно текущему вектору вероятностей, который корректируется в сторону лучшей особи. Метод корректировки вектора вероятностей, по сути, взят из конкурирующего метода обучения нейронных сетей без учителя. Таким образом, здесь "эволюционирует" вектор вероятностей. Этот подход развит многими авторами и некоторые его модификации допускают достаточно простую аппаратную реализацию.

8.3. Компактный генетический алгоритм

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

Критерием остановки работы алгоритма выступает следующее условие: $$(p_i>0)\(p_i<1)$$ для всех $$1\le i\le N$$.

8.4. Генетический алгоритм SELFISH

Данный алгоритм был разработан в [4] на основании современной интерпретации Дарвиновской теории механизмов естественного отбора, предложенной биологом Ричардом Доукинзом. Ключевым моментом нового подхода стала гипотеза о том, что базовым элементом эволюции является ген, а не особь. В связи с этим рассматриваются хромосомы, гены которых могут принимать различное количество значений в зависимости от своего расположения внутри хромосомы. Поэтому вектор вероятностей трансформируется в более сложную структуру: $$P=(P_1,P_2,\dots ,P_N)$$, где $$P_i=(p_{i1},p_{i2},\dots ,p_{in_i})$$

Отметим, что здесь $$P_i$$ могут иметь различную мощность $$n_i$$, поскольку разные гены могут принимать различное число значений. Псевдокод предложенного алгоритма SELFISH имеет следующий вид:

Здесь функция "поощрение" увеличивает, а функция "наказание" уменьшает текущие вероятности для соответствующих значений всех генов в хромосоме на $$\varepsilon_i$$. То есть $$p_{iH_i}=p_{iH_i}\pm\varepsilon_i$$ для всех $$1\le i\le N$$,где $$H$$– некоторая хромосома.

Функция "выбор_особи" выполняется следующим образом:

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

В заключение добавим, что критерий останова работы алгоритма определяется как состояние, в котором для каждого гена (локуса) $$L_i$$ существует аллель (одно из возможных значений гена) $$a_{ij}$$, чья вероятность больше заданного $$p_i$$(обычно принимает значение ).

8.5. Сравнение простых и вероятностных генетических алгоритмов

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

Задачи численной оптимизации (нахождение наибольшего либо наименьшего значения функции многих переменных). Для тестирования использовались функции De Jong $$(F_1,\dots,F_5)$$. Графическое сравнение эффективности алгоритмов представлено на рис.8.2, из которого видно, что классический и вероятностный ГА дают очень близкие результаты для этого задач численной оптимизации. Однако следует заметить, что вероятностные ГА существенно проще в реализации.

Задачи комбинаторной оптимизации.

Задача коммивояжера (Traveling salesman problem).(рис 8.3) Сравнение простого (GA) и вероятностного(IGA) ГА.

Задача упаковки рюкзака (Bin packing).(рис 8.4) Сравнение простого (GA) и вероятностного(IGA) ГА.

Задача календарного планирования (Job-shop scheduling problem).(рис 8.5) Сравнение простого ГА и различных модификаций PBIL

Аналогично на рис.8.3,рис.8.4,рис.8.5 представлены результаты компьютерных экспериментов, которые показывают близкие характеристики классических и вероятностных ГА для задач комбинаторной оптимизации. Здесь по осям абсцисс отложены число поколений (итераций), а по осям ординат значения фитнесс-функций.

Итак, представленное в графической форме сравнение эффективности работы простого (или классического) ГА с вероятностными и компактными ГА практически однозначно свидетельствует в пользу последних. Более подробное освещение данного вопроса можно найти в первоисточниках [2,3,4]. Генетические алгоритмы в последние годы широко и довольно успешно используются при решении задач численной и комбинаторной оптимизации. Их популярность, в первую очередь, связана с той универсальностью, которая заложена в них теорией эволюции Ч. Дарвина.

Однако, несмотря на значительные преимущества ГА перед остальными метода поиска, приходится констатировать и ряд недостатков. Так, до сих пор не решена проблема преждевременной сходимости ГА к локальным экстремумам. Очередной попыткой, сделанной исследователями в этом направлении, стали вероятностные и компактные ГА. По сравнению с традиционными ГА они имеют ряд преимуществ. Во-первых, это контроль и управление скоростью сходимости генетического поиска. Во-вторых, это поддержка и сохранение разнородности генетической информации в популяции. И, в-третьих, это экономия вычислительных ресурсов. Пока рано говорить о том, что такие ГА полностью решили проблему преждевременной сходимости, однако они существенно сгладили тот негативный эффект, который она создавала. Таким образом, дальнейшие исследования в этой области являются перспективными и вероятностные и компактные ГА при решении практических задач могут быть весьма полезными. Особо следует отметить компактные ГА, которые вследствие своей простоты допускают эффективную аппаратную реализацию. Более полно вероятностные метаэвристики представлены, например, в монографии[7].

Контрольные вопросы

Краткие итоги: