Естественные алгоритмы. Алгоритм поведения роя пчёл

На Хабрахабре неоднократно обсуждался генетический алгоритм, его преимущества и недостатки. Но генетический алгоритм (а точнее целая плеяда различных его подвидов) не является единственным в своём роде. Его относят к так называемым естественным алгоритмам. К ним также принадлежат алгоритм «имитации отжига», алгоритм «поведения роя пчёл» и алгоритм «поведения колонии муравьёв» и ещё несколько почти неизвестных алгоритмов.

Я хотел бы остановиться на втором, менее популярном но не менее интересном алгоритме синтеза и оптимизации — алгоритме поведения роя пчёл — и объяснить его принцип.

Для рассмотрения принципов работы алгоритма поведения роя пчёл, или метода роя пчёл (МРП) прибегнем к аналогии с реальным роем пчел. Представим себе рой пчел на поле. Их цель – найти на поле область с наивысшей плотностью цветов. Без какого-либо представления о поле априори, пчелы начинают поиск цветов со случайных позиций со случайными векторами скорости. Каждая пчела может помнить позиции, где она нашла наибольшее количество цветов и каким-то образом знать области, где другие пчелы обнаружили наибольшую плотность цветов. Выбирая между возвращением к месту, где пчела сама обнаружила наибольшее количество цветов, или исследованием места, определенного другими, как место с наибольшим количеством цветов, пчела устремляется в направлении между двумя точками в зависимости от того, что окажет большее влияние на ее решение – персональное воспоминание или социальный рефлекс. По пути пчела может найти место с более высокой концентрацией цветов, чем было найдено ранее. В дальнейшем оно может быть обозначено как новое место с наибольшей концентрацией цветов, а также как место наибольшего скопления цветов, найденное всем роем. Случайно пчела может пролететь мимо места, с большим количеством цветов, чем было найдено любой другой пчелой роя. Весь рой, затем будет стремиться навстречу этому месту в дополнении к собственным наблюдениям каждой пчелы. Таким образом, пчелы исследуют поле: перелетая места с наибольшей концентрацией, они замедляются в их направлении. Непрерывно они проверяют места, которые пролетели, сравнивая с найденными ранее местами с наибольшей концентрацией цветов надеясь найти абсолютную наибольшую концентрацию цветов. В конечном итоге, пчела заканчивает движение на месте поля с наибольшей концентрацией цветов. Вскоре весь рой сосредотачивается в окрестностях этой позиции. Не имея возможности обнаружить места с большей концентрацией цветов, пчелы непрерывно роятся в районе наибольшей плотности цветов. Это поведение пчёл и было положено в основу этого метода оптимизации.

Язык метода

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

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

Пригодность — по аналогии с примером пчелиного роя функция пригодности будет плотностью цветов: чем больше плотность, тем лучше позиция. Функция пригодности служит средством связи между физической проблемой и алгоритмом оптимизации.

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

Глобальная наилучшая позиция – каждая пчела также каким-то образом узнает область наибольшей концентрации цветов, определенную всем роем. Эта позиция наибольшей пригодности известна как глобальная наилучшая позиция (ГНП). Для всего роя это одна ГНП, к которой стремится каждая пчела. В каждой точке на протяжении всего пути каждая пчела сравнивает пригодность ее текущей позиции с ГНП. В случае если какая-либо пчела обнаружит позицию с более высокой пригодностью, ГНП заменяется текущей позицией этой пчелы.

Алгоритм

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

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

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


где:
— это скорость частицы в n-том измерении на предыдущем шаге,
— это координата частицы в n-том измерении,
— ПНП,
— ГНП.
Расчет производится для каждого из N. Из этого уравнения видно, что новая скорость получается из старой скорости путем простого масштабирования на , и прибавления направления ГНП и ПНП для этого конкретного направления. и — это масштабные коэффициенты, которые определяют относительное взаимное «притяжение» к ПНП и ГНП. Они иногда рассматриваются как познавательный и социальный факторы. — это коэффициент, определяющий какое влияние на частицу оказывает ее память о ПНП, и — коэффициент, определяющий какое влияние на частицу оказывают остальные члены роя. Увеличение предполагает исследование пространства решений путем движения каждой частицы в направлении своего ПНП; увеличение предполагает исследование предполагаемого глобального максимума. Функция случайных чисел rand() возвращает число в интервале между -1 и 1. В общем случае два появления функции rand() представляет собой два различных вызова функции. Большинство реализаций используют две независимые случайные величины для стохастического изменения относительного притяжения ГНП и ПНП. Это введение случайного элемента в оптимизацию предназначено для моделирования незначительного непредсказуемого компонента реального поведения роя. называют «инерционным весом» и это число (выбранное в интервале между 0 и 1) отражает в какой мере частица остается верной своему первоначальному курсу, не подвергшемуся влиянию ГНП и ПНП.

Граничные условия

Границы мы задали изначально, но нигде в формулах и методах о них не упоминалось. Так как же всё таки их учитывать? Существует несколько ответов на этот вопрос.

Например, можно сделать стены поглощающими. Когда частица ударяется об границу пространства решений в одном из измерений, скорость в этом измерении обнуляется, и частица в конечном итоге будет возвращена в заданное пространство решений. Это означает, что границы — «стены» поглощают энергию частиц, пытающихся разрешённую область. Или же отражать скорость частицы, когда та подлетает к «стене». Но самым эффективным решением оказались «невидимые стены». Частица может спокойно вылетать за их пределы, но находясь вне разрешённой области, значения, полученные ею значения просто не учитываются, до тех пор, пока она не вернётся обратно.

Заключение

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

По сравнению с генетическим алгоритмом, операторы которого могут быть реализованы различным образом, имеет лишь один оператор — вычисление скорости, что делает его более простым в использовании.

В методе роя пчёл можно легко определить достижение точки глобального минимума, в то время как в генетических алгоритмах это значительно осложнено.

Концепция этих методов основывается на двух совершенно разных природных процессах: МРП основывается на социальном поведении роя, а генетический алгоритм имитирует процесс эволюции и естественного отбора. За счёт этого есть возможность объединить два этих метода.
Поделиться публикацией
Комментарии 27
    +2
    Не понял я вашего алгоритма, хоть и очень старался.
    Вы говорите то о цветах и частицах, то о «стенах», глобальных экстремумах и снова о пчелах. Трудно уследить за мыслью.
      +3
      Плотность цветов — значение целевой функции, частицы — те самые «пчелы», стены — границы допустимого множества задачи. Мысль вполне отслеживаема :)
      +4
      Эх, жаль, что не выбрали для описания алгоритм поведения колонии муравьев. Просто есть в нем — в алгоритме поведения реальных муравьев — одна странная (так и хочется назвать это багом, но как-то рука не поднимается написать такое про не человеком созданные алгоритмы, да к тому же каламбур ;) особенность. В определенных ситуациях огромный табун муравьев начинает ходить по кругу, превращаясь в черное кольцо, и не может остановиться, вследствие чего муравьи умирают от изнеможения. Просто вот очень хотелось бы почитать, как это формализуется, так сказать :)
        0
        > Просто вот очень хотелось бы почитать, как это формализуется, так сказать :)

        ru.wikipedia.org/wiki/Муравьиный_алгоритм
          +6
          Муравьи-кочевники никогда не производят индивидуальную фуражировку или разведку, но действуют большими группами (Schneirla, 1971; Gotwald, 1995; Rettenmeyer, 1963). Такая фундаментальная неспособность муравьев-кочевников к индивидуальной фуражировке приводит к необычному феномену бега по кругу (Schneirla, T. C. 1944. Am. Mus. Novit. 1253, 1–26), когда все муравьи бегут по феромонному следу друг за другом по кругу (хоть вокруг большой тарелки) и каждый буквально по рабски ступает след в след впереди бегущему муравью, вплоть до полного изнеможения и смерти!

          Нашел где-то в интернетах.
          0
          Немного промазал с ответом.
            +1
            Это недостаток алгоритма. Причем не только низшие насекомые ему подвержены :)
            У спелеологов есть известный «прикол»:
            Группу чайников, человек 15, не менее, заводят в сложный лабиринт, водят довольно долго, чтобы притупилось внимание, и они забыли кто за кем шел, и незаметно зацикливают хвост группы к ее голове, а сам ведущий скрытно отползает и наблюдает как толпа носится по кругу.
            +1
            Мне кажется, или это называется «метод градиентного спуска»?
              +2
              В методе градиентного спуска выбирается одна начальная точка, шаг и направление. После первого шага вычисляются производные, и в направлении, где производная больше, производится следующий шаг. Но это если говорить грубо. На самом деле вычисляется градиент, и по нему перемещают точку. А в этом алгоритме не вычисляются производные, и начальных точек выбирается много, что является характерной чертой всех естественных алгоритмов.
                +1
                Извините, но грубое значение производной: df/δk=Δf/δk. Т.е. мы берём различие между предыдущим шагом и новым, смотрим, куда было лучше, смещаемся в ту сторону. Если мы промахнулись, то новый вектор вычисляется как компромисс между новым и старым.
                  0
                  … δk — это обобщённое название частной производной по координате.
                    +1
                    В методе градиентного спуска огромное значение имеет выбор начальной точки направления и шага. Попав на втором шаге в локальный минимум градиентный метод никогда не выберется из него, в отличие от описанного метода, который найдёт глобальный минимум. Также, метод градиентного спуска относится к детерминированным алгоритмам, в то время как алгоритм поведения роя пчёл является стахостическим.
                    Что касается производной, то она основывается на ранее известных данных (предыдущий шаг и текущий). Этот алгоритм оперирует только с двумя известными точками: ПНП и ГНП и корректирует позицию каждой точки основываясь на них, но случайным образом.
                      +4
                      Собственно, вопрос, почему рой найдёт глобальный минимум? Ровно так же рой может застрять в локальном минимуме, так как любое отклонение приводит к ухудшению результатов.

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

                      Алгоритм роя очевидным образом не сможет покрыть бесконечность, так что его к бесконечным функциям и не применяют. А на конечной функции достаточно использовать метод научного тыка и метод градиентного спуска — на выходе будет ровно тот же результат. Мы будем иметь вероятность попасть в спуск в глобальный минимум и алгоритм, который этот минимум пройдёт.
                0
                Про муравьёв я собирался написать через пару постов. У них более специфический алгоритм. Он хорош для логистических, а также динамических систем.
                  +1
                  Странный какой-то алгоритм. Описанная система пчёл явно эргодическая. Это значит, что во-первых, можно рассматривать не рой пчёл, а одну пчелу, просто дольше (усреднение по ансамблю эквивалентно усреднению по времени); и во-вторых, что эту систему можно анализировать чисто статистическими методами, которые смогут или повысить эффективность алгоритма, или вообще выдать решение сразу, без всяких там роящихся пчёл.

                  Чем этот алгорим лучше обычного Монте-Карло?
                    0
                    Метод Монте-Карло основывается вероятностных характеристиках. Целью этого метода было получение алгоритма, имитирующего явление живой природы. Анализировать же эти естественные процессы можно и нужно. Я не берусь утверждать, что метод Монте-Карло однозначно хуже, просто есть такой алгоритм и для определённых задач он является эффективным. И мне интересно посмотреть на реализацию статистического анализа этой системы и посмотреть насколько увеличится эффективность алгоритма.
                    Хочу отметить, что существуют различные комбинации методов, например генетический алгоритм с методом градиентного спуска в каждом поколении, но опять же, производительность каждого из выбранных методов различна для разных задач.
                      +2
                      Так ваша цель решить задачу или поиграть в пчёл? У меня осталось ощущение, что поиграть; и к решению каких-либо задач это всё не имеет отношения.
                        +3
                        Есть такое :)
                        Но я думаю, это гораздо лучше, чем очередная статья про стартапы
                    0
                    Хорошая вводная статья. Очень хотелось бы, чтобы автор опубликовал несколько прикладных примеров использования алгоритма для решения как простых, так и более сложных задач.

                    Так же интересно сравнение с ГА — сравнение временной сложности, выбор целевой функции. Если автор больше не планирует продолжать писать про пчёл, возможно он сможет дать несколько ссылок, где об этом пишут поподробнее, и понятным языком. Это было бы замечательно.
                      +2
                      Было бы неплохо приложить визуализацию какую-нибудь…
                      0
                      Это Partical Swarm Optimization?
                        +1
                        видимо это вариант расширения стохастического поиска на паралельную обработку (использование знания о глобальном найденном оптимуме, умозрительно, ускоряет сходимость).
                        однако, у меня вопрос к автору

                        ИМХО, необходимо учитывать множитель инерции именно таким образом, т.к. исходя из вашей исходной формулы, скорость неограниченно растет на каждом шаге.
                        во-вторых, неясны размерности разностей p — x и g-x. p и g это же значение оптимизируемой функции в какой либо точке, а вычитаем из этого координату.
                          0
                          pn — n координата наилучшей персональной позиции, gn — n координата глобальной наилучшей позиции, а не значения целевоя функции в них. Значения в скобках есть расстояния от частицы до ПНП и ГНП соответсвенно. Скорость будет увеличиваться с удалением пчелы от ПНП и ГНП, что вполне нормально, ведь чем дальше улетает пчела, тем сильнее она стремится вернуться, и весовые коэффициенты там тоже имеют значение.
                          0
                          Когда то я ним занимался, запомнил, что генетический на неких данных легко сваливается в локальный минимум, а вот пчёлы почти не попадаются на уловку — всегда выдавали именно глобальный.
                          Спасибо, что освежили и добавили знаний :).
                            0
                            если генетический алгоритм «не правильно готовить» он почти всегда скатывается в локальный на негладкой функции. в любом случае, уверен, что генетический будет быстрее.

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

                          Самое читаемое