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

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

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

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

Обозначим вероятность того, что ген до мутации был равен единице, как p. Необходимо определить, чему рав- на вероятность того, что этот ген будет равен единице после мутации. Обозначим искомую вероятность какp', а вероятность мутации - какp .

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

P { у = 1 } = P { Х= 1 } (1 - P m ) + P { x = 0 } P m = = P ^{(1 -} P m ^{) + (1 -} P ) P m = P m ⁺ P ^{(1 - 2} P m )-Используя введенные выше обозначения для вероятностей значений генов и вероятности мутации, получим P' = P m ⁺ P ^{(1 - 2} P m )-              ⁽¹⁾

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

Можно сказать, что традиционная реализация мутации в ВГА есть вычисление распределения генов после мутации с помощью метода Монте-Карло, которое сводится к стохастической аппроксимации результатов вычисления по формуле (1). Название асимптотическая мутация обусловлено тем, что данная процедура является предельным случаем традиционного оператора мутации при размере популяции, стремящемся к бесконечности.

Рассмотрим некоторые свойства предложенной процедуры мутации. Преобразование, которое она задает, является линейным, сжимающим отрезок [0; 1] до отрезка [ p m ; 1 - p m ]. Действительно, линейность следует непосредственно из формулы (1), а границы интервала можно получить, подставив вместо p значения 0 и 1 соответственно. Так как линейная функция является монотонной, то значения из интервала [0; 1] будут отображаться в интервал [ P_m ; 1 - P_m ]. Таким образом, мутация не позволяет вероятности p приближаться к 0 или 1 более чем на величину P_m . Это исключает вырождение распределения, а значит и преждевременную сходимость по отдельным компонентам бинарного представления решения.

Легко проверить, что p = 0,5 является неподвижной точкой данного отображения, т. е. если значения гена были равновероятны до мутации, то это свойство сохранится и после мутации. Таким образом, предложенная выше процедура корректировки распределения делает его более близким к равномерному распределению.

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

При использовании традиционной процедуры мутации на каждой итерации алгоритма для каждого гена каждого решения необходимо генерировать случайное действительное число, равномерно распределенное на ин- тервале [0; 1], и если оно попадает в интервал [0; pm], где Pm - вероятность мутации, то ген необходимо инвертировать. Таким образом, при использовании стандартной реализации оператора мутации на каждой итерации необходимо выполнить O(N; M) действий, где N - размер популяции; M - число генов. При этом большая часть генов не будет инвертирована, так как вероятность мутации обычно выбирается очень малой.

Но какова вероятность того, что решение вообще не изменится в ходе мутации? Решение не изменится, если ни один из его генов не будет изменен. Вероятность того, что данный ген не будет изменен, не зависит от того, были ли изменены другие гены, и равна 1 - p m = q m . По правилу вычисления вероятности одновременного наступления независимых событий получаем, что искомая вероятность Q = (1 - p m ) M . Для выбора вероятности мутации часто используется следующее правило: p_m = 1/ M , тогда Q « e ^-1. Данное соотношение выполняется довольно точно уже при M , равном 10. Это значит, что более трети решений в ходе мутации вообще не изменятся, т. е. все вычисления, связанные с реализацией оператора мутации, действующего на решения, более чем в трети случаев проводятся только для того, чтобы установить, что никаких действий выполнять не нужно.

Разработанный авторами подход к реализации мутации лишен этих недостатков. Его алгоритмическая сложность для одной итерации равна O ( M ), т. е. время проработки этого этапа не зависит от размера популяции. На практике это означает, что временные затраты на проработку мутации становятся исчезающе малыми по сравнению с этапами, сложность которых зависит от размера популяции (в вероятностном генетическом алгоритме таким этапом является селекция).

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

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

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

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

pB =

np + C n +2 C ’

где p_B - байесовская оценка вероятности по частоте; p -классическая оценка вероятности по частоте (отношение числа опытов, в которых событие произошло, к общему числу опытов); n - общее число проведенных опытов; C - параметр, который обычно выбирают равным 1.

Проведя элементарные преобразования, получим, что байесовская оценка вероятности эквивалентна мутировавшей классической оценке вероятности мутации, если выбрать вероятность мутации равной С /( n + 2 C ).

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

Пусть популяция состоит из особей x 1 ,..., x n , каждой из которых назначена вероятность быть отобранной в одном испытании g 1 ,..., g n . Подсчитаем математическое ожидание вероятности того, что i -й ген окажется равным единице в одном испытании:

n

Р (i) = £ x ki g k .

k= 1

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

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

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

Пусть размер турнирной группы равен S. Предполо- жим сначала для простоты, что все решения имеют различную пригодность. Подсчитаем вероятность того, что особь с к-м значением пригодности пройдет отбор. В турнирную группу каждое решение может попасть с равной вероятностью, т. е. распределение равномерное. Победителем турнира будет особь с наибольшим рангом, т. е . ранг победителя турнира распределен как максимум S равномерно распределенных случайных величин [3]:

gk =

k^S - ( к - 1) S

Рассмотрим теперь случай повторяющихся значений пригодности. Пусть в популяции встречается K различных значений пригодности и к -е значение встречается n_k раз. Тогда имеет место равенство

£Х =” .

к= 1

В этом случае удобнее получить выражения не для вероятностей g_k , а для накопленных вероятностей G_k , которые задаются следующим образом:

G =g 1 ,

G k = G k - i + g k , к = 2,..., K .

Так как решения отбираются в турнирную группу независимо от их пригодности, то все возможные турнирные группы им еют одинаковую вероятность, а к- я накопленная вероятность равна количеству выборок, содержащих только решения со значением пригодности, меньше либо равной к , отнесенной к общему числу различных выборок:

1 f 1

Gfc = — ZX .

kSj n У j=1 у

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

Используя описанные выше методы реализации асимптотической мутации и селекции, получим модификацию ВГА со следующей схемой:

• 1.    Создать и оценить начальную популяцию с равномерным распределением генов.

• 2.    Если выполнен критерий останова, то прекратить работу.

• 3.    Построить распределение с помощью асимптотического метода селекции.

• 4.    Скорректировать распределение с помощью асимптотического оператора мутации.

• 5.    Создать новую популяцию с полученным распределением вероятностей генов. Оценить новую популяцию.

• 6.    Перейти к п. 2.

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

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

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

При сравнении алгоритмов использовались следующие настройки: размер популяции – 100, максимальное число итераций – 50, число запусков для определения характеристик качества – 1 000, мутация – слабая, метод кодирования – код Грея. Сравнение производилось отдельно для каждого метода селекции и тестовой функции, причем оценка характеристик выполнялась пять раз. Для тестирования были использованы те же стандартные тестовые функции, что и в работе [1].

Для проверки гипотез о значимости различий использовался непараметрический критерий согласия Уилкок-сона–Манна–Уитни [4] с объемом выборок 5. Результаты тестирования алгоритмов приведены в табл. 1, в которой указаны медианы усредненных по всем тестовым функциям значений. В столбце «Результат» приводится количество тестовых функций, на которых качество одного алгоритма статистически значимо отличается от другого (общее число тестовых функций – 16); значения для базового алгоритма и модификации приведены через косую черту.

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

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

Сравнение алгоритмов при решении задачи формирования кредитного портфеля банка. Проведем сравнение стандартного ВГА и его модификаций при решении задачи формирования кредитного портфеля банка (условия взяты из работы [5]). Данная задача относится к классу задач условной псевдобулевой оптимизации, т. е. оптимизации функций, отображающий булев гиперкуб на множество вещественных чисел. Размерность пространства поиска равна 50. Для учета ограничений использовался метод динамических штрафов [6]. Размер популяции был выбран равным 1 000, число итераций – 100, число запусков для усреднения – 100. Для каждого метода селекции производилась проверка равенства математических ожиданий доходности лучшего портфеля, найденного базовым алгоритмом и его модификациями. Для проверки значимости различия использовался критерий Стьюдента [4]. Размер выборок достаточно велик (100), поэтому можно использовать асимптотическое критическое значение статистики Стьюдента. Для уровня значимости 0,95 оно составляет примерно 1,97.

Таблица 1

Результаты тестирования

Вид с елекции	Базовый алгоритм		Модификация		Результат
	Надежность	Затр аты	Надежность	Затраты
Пропорциональная	0,44	2 100	0,52	2 100	0/7
Ранговая	0,46	2 200	0,62	2 300	0/7
Турнирная	0,48	2 100	0,65	2 300	0/8

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

Проверка гипотезы о равенстве математических ожиданий по критерию Стьюдента показывает, что эффективность алгоритмов с асимптотической мутацией или асимптотической селекцией (ВГА-М или ВГА-С) отличается от базового алгоритма статистически незначимо (на уровне значимости 0,95). Кроме того, эффективность этих двух алгоритмов также различается статистически незначимо. Различие же между алгоритмом, использующим и асимптотическую мутацию, и асимптотическое скрещивание (ВГА-МС), и остальными зависит от типа селекции: при использовании пропорциональной и ранговой селекции эффективность ВГА-МС статистически значимо превосходит эффективность трех остальных алгоритмов, а в случае использования турнирной селекции статистически значимых различий нет.

В заключение проанализируем время выполнения различных вариантов ВГА. Данные табл. 2 показывают, что во всех случаях базовый ВГА уступает его асимптотическим модификациям. Более того, алгоритм, использующий и асимптотическую мутацию, и асимптотическую селекцию, при использовании пропорциональной и ранговой селекции превосходит алгоритмы, у которых только один из этих этапов является асимптотическим. При использовании турнирной селекции самым быстрым является ВГА с асимптотической мутацией и обычной селекцией. Этот факт может быть объяснен следую- щим образом: асимптотический вариант турнирной селекции производит относительно дорогую операцию – сортировку популяции, которая отсутствует в обычной турнирной селекции (отбор в зависимости от рангов значений без их сортировки – одна из причин популярности данного метода селекции). Тем не менее использование асимптотических мутации и селекции не замедляет алгоритм по сравнению с базовым ВГА.

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