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

    В моей предыдущей статье описывался алгоритм поведения роя пчёл и применение его для решения задач оптимизации и синтеза. Вооружившись С++ и OpenGL я написал программу, реализующую этот самы алгоритм в двухмерном пространстве, и отображающую роение «пчёл».

    В качестве испытательной функции была выбрана следующая функция:





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

    Немножко видео самого процесса для различных настроек:
    притяжение к ПНП(персональная наилучшая позиция) — 0.5. Притяжение к ГНП(глобальная наилучшая позиция) — 0.5. Инерционный вес — 0.5. Пчёл в рое — 60. Для наглядности я поставил задержку в 500мс перед каждым шагом.


    Притяжение к ПНП — 0.1. Притяжение к ГНП — 0.7. Инерционный вес — 0.3. Пчёл в рое — 60.


    Теперь задача посложнее.

    Функция сильно осциллирует.



    Притяжение к ПНП — 0.3. Притяжение к ГНП — 0.3. Инерционный вес — 0.3. Пчёл в рое — 60.


    И ещё сложнее задача.

    Границы расширены.


    Притяжение к ПНП — 0.3. Притяжение к ГНП — 0.3. Инерционный вес — 0.3. Пчёл в рое — 60.


    Критерий остановки


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

    И в заключение о задаче оптимизации


    Особым пунктом здесь стоит построение целевой функции. Мы должны грамотно оценить качество объекта оптимизации по заданным критериям. Можно создавать произведения искусства, если задать закон, который бы оценивал красоту.
    Вместо расчёта целевой функции также возможен опыт. Например. Нам нужно установить вайфай точку в комнате так, чтобы на диване и на кухне сигнал был максимальным. Мы задаём границы комнаты. После чего алгоритм нам говорит в каких точка нужно поставить и проверить сигнал. Замеряем сигнал на кухне и на диване и на основани этих данных присваиваем каждому положению значение целевой функции. Туда же можно включить и удалённость от стен (ведь не подвесишь же её под люстрой), а ещё удалённость от свича и розетки, фен-шуй,… И через пару часов беготни с ноутбуком и точкой мы будем знать куда стоит её крепить, а куда не нужно.
    Пример, конечно, дикий, но зато относится к реальной жизни. Подчеркиваю, что метод оптимизации на выбор целевой функции никак не влияет.

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

    P.P.S Код программы без комментариев можно посмотреть здесь.
    Поделиться публикацией

    Комментарии 54

      –3
      В упор не вижу практической пользы.
        +11
        зато для мозгов полезно
          +11
          Ты прав, это бесполезная фигня.
          Оптимальную форму самолета, кроссовка или гоночного болида заставить комп придумать еще сгодится… А что-то серьезное и интересное — уже нет.
            +1
            Что-то серьёзное и интересное — это что?
            0
            Я еще могу себе представить как этот алгоритм можно использовать в Eve для нахождения точек с самым толстым количеством ресурсов, методом методичного тыка «а ля пчелиный рой», или чего-то в таком духе. Но вот как численный метод поиска глобальных экстремумов может помочь в расчете оптимальной формы фюзеляжа или кузова болида, представляю с трудом. Думается, самая сложная часть в таком деле будет заключаться в составлении многомерной функции, экстремумы которой и надо будет найти, а потом еще и интерпретировать.
              +4
              Допустим у нас есть базовая форма фюзеляжа. Мы разбиваем форму на участки. В центре каждого участка ставится точка, координаты которой можно изменять, подбирая аэродинамические характеристики. Перебрать все возможные варианты задача слабоосуществимая. Тогда мы берём и координаты каждой точки закладываем в алгоритм оптимизации. На каждом шаге алгоритм будет выдавать несколько решений, которые мы должны оценить. Решением является набор координат точек, построенный по которым фюзеляж будет иметь требуемые характеристики. Оцениваются выдаваеммые алгоритмом варианты решения при помощи программ анализа, которые по геометрическим характеристикам объекта могут посчитать аэродинамические. Допустим нам нужно минимальное сопротивление воздуху. Тогда параметром оценивания будет число пропорциональное сопротивлению воздуха. Таким образом мы имеем схему, по которой можно синтезировать форму фюзеляжа с минимальным сопротивлением воздуху.
                0
                Интересно, а таким образом мы сможем получить форму капли?)Если я не ошибаюсь, в природе у нее минимальное сопротивление воздуху.
                  +1
                  Генетическим алгоритмом проверялось решение известной задачи синтеза антенн. Условия задачи: имеется множество коротких проводников, концы которых соединены переключателями. Требуется отбросить максимальное количество переключателей, чтобы антенна могла работать в двух режимах (на разных частотах). Решение просто — вибратор с одним выключателем, который подключает дополнительный элемент антенны. И это решение было получено при помощи генетического алгоритма.
                    0
                    Не факт что минимальное. Она формируется за счёт сопротивления, но это вовсе не значит что она лучший вариант: ведь почему-то не делают же самолёты/дерижабли в виде сплющенных шаров?

                    (да-да, капли более менее сфирические, еще и сплюснутые если очень большие)
            +2
            ОО… мы тоже на 3тьем курсе писали подобное в курсе методы оптимизации…

            Практическая польза, в том что функция может иметь например под собой производственный процесс… И небольшой расчет поможет его оптимизировать, а это опять же деньги
              0
              а насчет методов хорошо работает градиентный спуск с выбором длины шага (на каждой итерации решаем более простую задачу оптимизации для длинны) работает не слишком медленнее зато сходится быстрее (и в овраги меньше попадает )
                +1
                Градиентный спуск не очень хорошо, точнее практически не работает на функциях с множеством локальных экстремумов.
                А если ходить по градиенту, то хорошо его дополнить методом табу поиска.
              0
              Если кому интересно, более подробно про Artificial Bee Colony Algorithm можно почитать тут
                0
                Это, кстати, другой алгоритм. Ниже уже написали, что алгоритм, который описывает автор правильнее называть Particle Swarm Optimization.
                  0
                  Да, это действительно в англоязычной литературе называется particle swarm optimization. Но рускоязычных названий устоявшихся у него нет. В одних местах можно прочитать «Алгоритм поведения роя частиц» (что является дословным переводом), а в других «Алгоритм поведения роя пчёл».
                +1
                Поясните пожалуйста что такое J0 в тестовых функциях?
                  +4
                  Функция Бесселя нулевого порядка.
                  +1
                  что такое ПНП и ГНП, абырвалг?
                    0
                    ПНП — персональная наилучшая позиция
                    ГНП — глобальная наилучшая позиция
                    Я же писал в теге abbr. Допишу сейчас.
                    –17
                    Бред какой-то… О чем статья?..
                    Все х… ня кроме пчел?
                      +3
                      Гм… Шутка не удалалсь…
                      Тогда по полочкам: статья написана в совершенно непонятной форме, без объяснения даже предметной области (что такое коэффициэнт J0 в формулах, расшифровки сокращений и пр.). Так же совершенно непонятен переход от визуализации движения роя пчел к методам оптимизации.
                      Итого возникает вопрос — о чем статья? Об алгоритме движения пчел, его визуализации или об оптимизации какого-то процесса?
                      В чем полезность данного произведения, кроме как в красивых картинках? К сожалению, ответа на эти вопросы в содержании статьи нет.
                      Остаются пчелы :)
                        +4
                        Читайте предыдущую часть. Там все доступным языком описано. А здесь конкретные примеры как алгоритм ведет себя на разных часных случаях.
                        Про J0 тут уже сказали.
                          0
                          Кстати, предыдущую часть многие не видели (так как она из песочницы и не появлялась в RSS).
                      0
                      Не очень понимаю, как задержка в полсекунды может помочь с наглядностью поведения пчелиного роя :) Мне наоборот казалось, что чем больше FPS, тем нагляднее.
                        0
                        С большим фпс трудно разсмотреть начальную позицию пчёл и выпадают некоторые ключевые моменты.
                          0
                          Визуально — можно делать трассировку движения каждой пчелы (т.е. траектория будет залить градиентом с минимальной яркостью в точке i и максимальной — i+1). Должно неплохо смотреться)
                        +2
                        А сколько раз была вычислена функция для каждого из примеров? В случае практического применения данного алгоритма каждое измерение объекта будет стоить денег.
                          0
                          Я думаю тут имеет большее значение разница между этими показателями у данного алгоритма и у других. Так что этот вопрос я оставил на следующий раз.
                            0
                            Ну если вы укажите значения, другие смогут сравнить со своими алгоритмами, а не только вы ;)
                          0
                          если б мишки были пчелами…
                            0
                            Спасибо огромное. Прошлую статью пропустил, но эта оказалась очень в тему. Пойду искать минимум у очень неприятной функции.
                              +8
                              Казалось бы, при чем здесь Лужков? :)
                                0
                                Кстати, а ведь метод роя (пчёл в названии, кстати нет ;) ), применим не только для координат. Есть проекты, где он может применяться для поиска любого универсального решения (например, программы, которая удовлетворяет заданным тестам).
                                Фактически, оптимизация роем — это некий аналог генетического алгоритма. Если откинуть лишнее, то он очень близки. Отличаются они двумя вещами:
                                1. В оптимизации роем самое лучшее решение не подавляет остальные. Всегда остаётся место для какой-то оппозиции. Так что оптимизация роем меньше застревает на локальных минимумах.
                                2. В генетическом алгоритме, популяция постоянно пересоздаётся — в итоге сильно увеличивается нагрузка на память. В оптимизации роем мы не клонируем «пчёл», а просто применяем мутацию (и слияние) на каждую из них.
                                В итоге, мне кажется, что надо оптимизацией роем заменять генетический алгоритм во многих задачах, потому что он гораздо лучше подходит к архитектуре наших процессоров.
                                  0
                                  Кстати, а ведь метод роя (пчёл в названии, кстати нет ;) ), применим не только для координат

                                  Любой параметр в этом контексте можно назвать координатой.
                                  Мне, например, нужно найти оптимальную толщину и показатель преломления стекла.
                                  Фактически, оптимизация роем — это некий аналог генетического алгоритма

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

                                  Для программы будет очень сложно, потому что программа на ассемблере из 10 строк — это уже десятимерное пространство. Рой рулит, когда переменных мало, а экстремум нужен глобальный.
                                  Генетический алгоритм рулит, когда переменных много, а подойдет любой экстремум рядом с начальными условиями. Т.е. для программы он более подходит.
                                    +1
                                    В том-то и дело, что не обязательно в оптимизации роем делать «пространство». Пространство вообще ограничение метафоры :). На самом деле нам нужно только три оператора: расстояние между двумя точками, случайное изменение точки и сдвигание одной точки в сторону другой. Всё это можно легко сделать для любого представления алгоритма (например, расстояние Левенштейна, случайная мутация и кроссовер). В статье ребята более подробно объясняют, как это они сделали: julian.togelius.com/Togelius2008Geometric.pdf
                                      0
                                      За статью спасибо, надо почитать.

                                      Ну мы же не о кубике с пчелами говорим. Если в «чем-то» есть точки, это уже можно назвать пространством. А если задано расстояние с несколькими свойствами — то оно даже метрическое. Хотя для генетического алгоритма в общем-то расстояние с его правильным треугольником не обязательно нужно, но, тем не менее, о пространстве говорить можно.
                                      А метафора плоскости/кубика хороша, на ней хорошо смотреть свойства любого оптимизирующего алгоритма.
                                      В генетическом алгоритме с одной популяцией, например, все тусят в одной области, пока перец с мутацией не перевалит за холм, а потом и остальные подтянутся. Пчелы же носятся по карте.
                                      Но это по карте им хорошо носиться, а если пространство трехмерное, то нужно минимум 4 пчелы, а то у трех пчел ускорения в итоге будут в итоге стремиться находиться в одной плоскости с точностью до рандома в функции скорости. Для 100-мерного пространства нужно еще больше пчел, а если вычисление каждой функции затратно, может получиться все не очень хорошо. Генетический алгоритм же с 20-ю особями может весьма хорошо заоптимизировать. Достаточно много выводов для простой метафоры.
                                        0
                                        Но у того метода нет «пространства», поскольку нет измерений, есть только расстояния. Нет, конечно же всё можно свести к пространству с нужным кол-вом измерений, но тут пространство неправильно задавать, поскольку оно будет кодироваться неявно, не будет помогать нам понять и решить задачу.
                                        Ведь любое множество решений можно закодировать с помощью 1-мерного пространства, поэтому связь измерения → кол-во пчёл не очень хороша :).
                                          0
                                          Вот хороший пример — мы же не используем метафору «пространства решений» для генетического алгоритма? (ну используем только в очень простых случаях, чтобы строить красивые графики и объяснять) И для PSO пространство решений (а тем более кол-во измерений) не обязательно (раз мы можем PSO свести к модификации ГА).
                                            0
                                            Как не используем? Это часть любого формального описания.
                                            Задача любой оптимизации — найти минимум некоторой вещественной функции fitness(x1, x2… xn).
                                            [x1, x2… xn] — координата точки этого пространства.

                                            Градиентный спуск, кстати, тоже можно свести к модификации ГА =)
                                            Особь — одна, оператор мутации: точка + градиент в точке.
                                              0
                                              Пространство решений в математике — это просто символ, а не n-мерное пространство в нашей голове. В голове оно мешает. Проще представить PSO для программы в виде графа связанных между собой программ. Хорошая программа отдаёт свои куски в более плохую (на основе того, насколько они отличаются между собой). В итоге и нет зависимости кол-ва пчёл от измерений (если оно вообще было), хотя, конечно, пчёл мало не бывает :).
                                                +1
                                                Вы много знаете не-просто-символов в математике?)
                                                0
                                                Ну а плюс, нам для PSO желательно не любое пространство решений. То есть мы не можем просто случайно раздать всем возможным алгоритмам свои координаты. Чтобы PSO нормально работал:
                                                Если у нас есть алгоритмы A (с координатами x1, y2) и B (x2, y2), то алгоритм C, который расположен посредине между (x1, y1) и (x2, y2) должен иметь свойства частично присущие A, частично B.
                                                Иначе у нас будет случайный перебор — близость между двумя пчёлами не будет означать близости значений fitness’а → следовательно понятие расстояния уже не имеет смысла и пчеле не имеет смысла лететь к более успешной пчеле.
                                                Ну а распределить всё (бесконечное) множество алгоритмов по n-координатам так, чтобы это свойство соблюдалось будет очень сложно ;).
                                                  0
                                                  близость между двумя пчёлами не будет означать близости значений fitness’а

                                                  Похоже на определение непрерывности.
                                                  Ну а распределить всё (бесконечное) множество алгоритмов по n-координатам так, чтобы это свойство соблюдалось будет очень сложно ;).

                                                  Дискретное расстояние. d(a,b) = 0 если a = b. d(a,b) = 1 если a !=b. Это если в коде одна команда. Для кода из n-команд аналогично, только берется сумма.
                                                  d(abc, abc) = 0; d(abc, abb) = 1; d(acc, abb) = 2. Ну и так далее.
                                                  Пространство, понятное дело, евклидовым не будет.
                                                    0
                                                    Это не пространство, а оператор расстояния. В пространстве, каждому алгоритму должен быть присвоен уникальный номер (или уникальная группа номеров).
                                                      0
                                                      Это пространство с заданным оператором расстояния
                                                  0
                                                  Кстати, если использовать ГА или PSO для генерации программ, то возникает ещё более интересный вопрос, как кодировать алгоритм, чтобы операция мутации и кроссовера была простой и лёгкой. Сейчас в основном используют нейронные сети или иерархические языки, но мне кажется, что это неправильный путь заимствования и я разрабатываю специальный язык, чтобы кодировать программы в для ГА — evolu.org
                                                    0
                                                    Как я понял, язык императивный?
                                                      0
                                                      Да. Главный смысл — отсутствие вложенности [операторов if и т. д.] и прямое и простое кодирование в байты. Чтобы со строкой байт можно было делать всё что угодно и результат откомпилируется и будет отличаться от родителя, в зависимости от того, какие сильные были мутации. Можно скопировать кусок байт из алгоритма A и вставить в любое место алгоритма B, который в итоге приобретёт какие-то свойства алгоритма A.
                                                      Язык вообще на ДНК немного похож :).
                                        0
                                        Вполне применимо для систем видео наблюдения с использованием множества видеокамер, если говорить о практической пользе.
                                        Необходимо только доработать сам алгоритм, в том смысле как идут сообщения между «пчелами». Это должно быть не «как-то» а более конкретно. В жизни кажется каждая пчела сообщает о своей находке более энергичным движением.
                                          +1
                                          Кстати, автор, совершенно странно, что ты не используешь оригинальное английское название алгоритма (Particle Swarm Optimization), хотя бы для поиска статьи.
                                            –2
                                            Матрица…
                                            Сначала пчёлы, потом голуби и т.д.
                                              0
                                              алгоритм неплохо показал себя, когда экстремум периодически меняет свою позицию каждый раз появляясь в случайном месте и тогда весь рой как-бы летает за этим неуловимым экстремумом
                                                +1
                                                Большинству теорий не хватает как раз вот таких вот картинок, демонстрирующих работу моделей.

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

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