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