Вопрос 46: Обезьяний алгоритм

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

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

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

Указанные выше действия повторяются заданное число раз. Решением задачи объявляется самая высокая из вершин, найденных данной популяцией обезьян.

Схему M-алгоритма можно представить в следующем виде:

Инициализацию популяции обезьян $s_i, i \in [1:|S|]$ выполняют по общим правилам путем равномерного случайного распределения агентов в поисковом пространстве.

Процесс движения вверх (climb process) представляет собой процесс локального поиска и может быть реализован многими способами. В оригинальном алгоритме авторы предлагают использовать алгоритм на основе процедуры стохастической аппроксимации.

Локальные прыжки (watch-jump process). Схема процесса локальных прыжков для агента $s_i,i \in [1:|S|]$ имеет следующий вид:

1. Исходя из текущего положения агента $X_i$, генерируем его новое возможное положение $X^\prime_i$ по формуле

$x^\prime_{ i,j }=U_1( ( x_{ i,j } - b ); ( x_{ i,j } + b ) ), i \in [1:|S|],j \in [1:|X|],$

то есть полагаем, что по каждой из координат новое положение агента представляет собой случайную величину, равномерно распределенную в интервале $[(x_{ i,j } - b); (x_{ i,j } + b )]$. Здесь $b > 0$ - максимально возможная длина прыжка (свободный параметр алгоритма).

1. Если точка $X^\prime_i$ является допустимой (принадлежит области допустимых значений $D$ ) и $\varphi( X^\prime_i ) \geq \varphi( X_i )$, то полагаем $X_i= X^\prime_i$ и завершаем для данного агента локальные прыжки, в противном случае заданное число раз возвращаемся к шагу 1.

Глобальные прыжки (somersault process) агенты выполняют из своего текущего положения в направлении текущего центра тяжести их координат по следующей схеме.

1. Генерируем случайное вещественное число $v = U_1 ( v^-; v^+ )$, имеющее смысл величины шага глобального прыжка. Здесь $v^-$, $v^+$ - нижняя и верхняя границы этой величины, имеющие в общем случае разные знаки, так что величина $v$ может быть как положительной, так и отрицательной.
2. Находим новое возможное положение $X^\prime_i$ агента $s^\prime_i$ по формуле:

$x^\prime_{ i,j } = x_{ i,j } + v( x_j^c - x_{ i,j }), i \in [1:|S|], j \in [1:|X|],$

где $x^c_j = \frac{1}{|S|} \sum_{ i=1 }^{ |S| } x_{ i,j }$ - текущее положение центра тяжести агентов популяции по j-му координатному направлению.

1. Если положение $X^\prime_i$ является допустимым, то полагаем $X_i = X^\prime_i$ и завершаем для данного агента глобальные прыжки, иначе заданное число раз возвращаемся к шагу 1.

Отметим, что если величина шага глобального прыжка $v$ принимает положительное значение, то агент совершает прыжок в сторону центра тяжести $X^c$, а если отрицательное значение - в противоположную сторону.

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

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