Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 54
В упор не вижу практической пользы.
зато для мозгов полезно
Ты прав, это бесполезная фигня.
Оптимальную форму самолета, кроссовка или гоночного болида заставить комп придумать еще сгодится… А что-то серьезное и интересное — уже нет.
Оптимальную форму самолета, кроссовка или гоночного болида заставить комп придумать еще сгодится… А что-то серьезное и интересное — уже нет.
Что-то серьёзное и интересное — это что?
Подозреваю, puffofsmoke иронизирует :)
Я еще могу себе представить как этот алгоритм можно использовать в Eve для нахождения точек с самым толстым количеством ресурсов, методом методичного тыка «а ля пчелиный рой», или чего-то в таком духе. Но вот как численный метод поиска глобальных экстремумов может помочь в расчете оптимальной формы фюзеляжа или кузова болида, представляю с трудом. Думается, самая сложная часть в таком деле будет заключаться в составлении многомерной функции, экстремумы которой и надо будет найти, а потом еще и интерпретировать.
Допустим у нас есть базовая форма фюзеляжа. Мы разбиваем форму на участки. В центре каждого участка ставится точка, координаты которой можно изменять, подбирая аэродинамические характеристики. Перебрать все возможные варианты задача слабоосуществимая. Тогда мы берём и координаты каждой точки закладываем в алгоритм оптимизации. На каждом шаге алгоритм будет выдавать несколько решений, которые мы должны оценить. Решением является набор координат точек, построенный по которым фюзеляж будет иметь требуемые характеристики. Оцениваются выдаваеммые алгоритмом варианты решения при помощи программ анализа, которые по геометрическим характеристикам объекта могут посчитать аэродинамические. Допустим нам нужно минимальное сопротивление воздуху. Тогда параметром оценивания будет число пропорциональное сопротивлению воздуха. Таким образом мы имеем схему, по которой можно синтезировать форму фюзеляжа с минимальным сопротивлением воздуху.
Интересно, а таким образом мы сможем получить форму капли?)Если я не ошибаюсь, в природе у нее минимальное сопротивление воздуху.
Генетическим алгоритмом проверялось решение известной задачи синтеза антенн. Условия задачи: имеется множество коротких проводников, концы которых соединены переключателями. Требуется отбросить максимальное количество переключателей, чтобы антенна могла работать в двух режимах (на разных частотах). Решение просто — вибратор с одним выключателем, который подключает дополнительный элемент антенны. И это решение было получено при помощи генетического алгоритма.
Не факт что минимальное. Она формируется за счёт сопротивления, но это вовсе не значит что она лучший вариант: ведь почему-то не делают же самолёты/дерижабли в виде сплющенных шаров?
(да-да, капли более менее сфирические, еще и сплюснутые если очень большие)
(да-да, капли более менее сфирические, еще и сплюснутые если очень большие)
ОО… мы тоже на 3тьем курсе писали подобное в курсе методы оптимизации…
Практическая польза, в том что функция может иметь например под собой производственный процесс… И небольшой расчет поможет его оптимизировать, а это опять же деньги
Практическая польза, в том что функция может иметь например под собой производственный процесс… И небольшой расчет поможет его оптимизировать, а это опять же деньги
Если кому интересно, более подробно про Artificial Bee Colony Algorithm можно почитать тут
Поясните пожалуйста что такое J0 в тестовых функциях?
что такое ПНП и ГНП, абырвалг?
Бред какой-то… О чем статья?..
Все х… ня кроме пчел?
Все х… ня кроме пчел?
Гм… Шутка не удалалсь…
Тогда по полочкам: статья написана в совершенно непонятной форме, без объяснения даже предметной области (что такое коэффициэнт J0 в формулах, расшифровки сокращений и пр.). Так же совершенно непонятен переход от визуализации движения роя пчел к методам оптимизации.
Итого возникает вопрос — о чем статья? Об алгоритме движения пчел, его визуализации или об оптимизации какого-то процесса?
В чем полезность данного произведения, кроме как в красивых картинках? К сожалению, ответа на эти вопросы в содержании статьи нет.
Остаются пчелы :)
Тогда по полочкам: статья написана в совершенно непонятной форме, без объяснения даже предметной области (что такое коэффициэнт J0 в формулах, расшифровки сокращений и пр.). Так же совершенно непонятен переход от визуализации движения роя пчел к методам оптимизации.
Итого возникает вопрос — о чем статья? Об алгоритме движения пчел, его визуализации или об оптимизации какого-то процесса?
В чем полезность данного произведения, кроме как в красивых картинках? К сожалению, ответа на эти вопросы в содержании статьи нет.
Остаются пчелы :)
Читайте предыдущую часть. Там все доступным языком описано. А здесь конкретные примеры как алгоритм ведет себя на разных часных случаях.
Про J0 тут уже сказали.
Про J0 тут уже сказали.
Не очень понимаю, как задержка в полсекунды может помочь с наглядностью поведения пчелиного роя :) Мне наоборот казалось, что чем больше FPS, тем нагляднее.
А сколько раз была вычислена функция для каждого из примеров? В случае практического применения данного алгоритма каждое измерение объекта будет стоить денег.
если б мишки были пчелами…
Спасибо огромное. Прошлую статью пропустил, но эта оказалась очень в тему. Пойду искать минимум у очень неприятной функции.
Казалось бы, при чем здесь Лужков? :)
Кстати, а ведь метод роя (пчёл в названии, кстати нет ;) ), применим не только для координат. Есть проекты, где он может применяться для поиска любого универсального решения (например, программы, которая удовлетворяет заданным тестам).
Фактически, оптимизация роем — это некий аналог генетического алгоритма. Если откинуть лишнее, то он очень близки. Отличаются они двумя вещами:
1. В оптимизации роем самое лучшее решение не подавляет остальные. Всегда остаётся место для какой-то оппозиции. Так что оптимизация роем меньше застревает на локальных минимумах.
2. В генетическом алгоритме, популяция постоянно пересоздаётся — в итоге сильно увеличивается нагрузка на память. В оптимизации роем мы не клонируем «пчёл», а просто применяем мутацию (и слияние) на каждую из них.
В итоге, мне кажется, что надо оптимизацией роем заменять генетический алгоритм во многих задачах, потому что он гораздо лучше подходит к архитектуре наших процессоров.
Фактически, оптимизация роем — это некий аналог генетического алгоритма. Если откинуть лишнее, то он очень близки. Отличаются они двумя вещами:
1. В оптимизации роем самое лучшее решение не подавляет остальные. Всегда остаётся место для какой-то оппозиции. Так что оптимизация роем меньше застревает на локальных минимумах.
2. В генетическом алгоритме, популяция постоянно пересоздаётся — в итоге сильно увеличивается нагрузка на память. В оптимизации роем мы не клонируем «пчёл», а просто применяем мутацию (и слияние) на каждую из них.
В итоге, мне кажется, что надо оптимизацией роем заменять генетический алгоритм во многих задачах, потому что он гораздо лучше подходит к архитектуре наших процессоров.
Кстати, а ведь метод роя (пчёл в названии, кстати нет ;) ), применим не только для координат
Любой параметр в этом контексте можно назвать координатой.
Мне, например, нужно найти оптимальную толщину и показатель преломления стекла.
Фактически, оптимизация роем — это некий аналог генетического алгоритма
Да в общем-то он обобщается до генетического алгоритма со смертью = 0 и, как вы написали, особой функцией мутации. Поэтому их можно комбинировать — например, уничтожать совсем далеких пчел и на их место генерировать новых.
Для программы будет очень сложно, потому что программа на ассемблере из 10 строк — это уже десятимерное пространство. Рой рулит, когда переменных мало, а экстремум нужен глобальный.
Генетический алгоритм рулит, когда переменных много, а подойдет любой экстремум рядом с начальными условиями. Т.е. для программы он более подходит.
В том-то и дело, что не обязательно в оптимизации роем делать «пространство». Пространство вообще ограничение метафоры :). На самом деле нам нужно только три оператора: расстояние между двумя точками, случайное изменение точки и сдвигание одной точки в сторону другой. Всё это можно легко сделать для любого представления алгоритма (например, расстояние Левенштейна, случайная мутация и кроссовер). В статье ребята более подробно объясняют, как это они сделали: julian.togelius.com/Togelius2008Geometric.pdf
За статью спасибо, надо почитать.
Ну мы же не о кубике с пчелами говорим. Если в «чем-то» есть точки, это уже можно назвать пространством. А если задано расстояние с несколькими свойствами — то оно даже метрическое. Хотя для генетического алгоритма в общем-то расстояние с его правильным треугольником не обязательно нужно, но, тем не менее, о пространстве говорить можно.
А метафора плоскости/кубика хороша, на ней хорошо смотреть свойства любого оптимизирующего алгоритма.
В генетическом алгоритме с одной популяцией, например, все тусят в одной области, пока перец с мутацией не перевалит за холм, а потом и остальные подтянутся. Пчелы же носятся по карте.
Но это по карте им хорошо носиться, а если пространство трехмерное, то нужно минимум 4 пчелы, а то у трех пчел ускорения в итоге будут в итоге стремиться находиться в одной плоскости с точностью до рандома в функции скорости. Для 100-мерного пространства нужно еще больше пчел, а если вычисление каждой функции затратно, может получиться все не очень хорошо. Генетический алгоритм же с 20-ю особями может весьма хорошо заоптимизировать. Достаточно много выводов для простой метафоры.
Ну мы же не о кубике с пчелами говорим. Если в «чем-то» есть точки, это уже можно назвать пространством. А если задано расстояние с несколькими свойствами — то оно даже метрическое. Хотя для генетического алгоритма в общем-то расстояние с его правильным треугольником не обязательно нужно, но, тем не менее, о пространстве говорить можно.
А метафора плоскости/кубика хороша, на ней хорошо смотреть свойства любого оптимизирующего алгоритма.
В генетическом алгоритме с одной популяцией, например, все тусят в одной области, пока перец с мутацией не перевалит за холм, а потом и остальные подтянутся. Пчелы же носятся по карте.
Но это по карте им хорошо носиться, а если пространство трехмерное, то нужно минимум 4 пчелы, а то у трех пчел ускорения в итоге будут в итоге стремиться находиться в одной плоскости с точностью до рандома в функции скорости. Для 100-мерного пространства нужно еще больше пчел, а если вычисление каждой функции затратно, может получиться все не очень хорошо. Генетический алгоритм же с 20-ю особями может весьма хорошо заоптимизировать. Достаточно много выводов для простой метафоры.
Но у того метода нет «пространства», поскольку нет измерений, есть только расстояния. Нет, конечно же всё можно свести к пространству с нужным кол-вом измерений, но тут пространство неправильно задавать, поскольку оно будет кодироваться неявно, не будет помогать нам понять и решить задачу.
Ведь любое множество решений можно закодировать с помощью 1-мерного пространства, поэтому связь измерения → кол-во пчёл не очень хороша :).
Ведь любое множество решений можно закодировать с помощью 1-мерного пространства, поэтому связь измерения → кол-во пчёл не очень хороша :).
Вот хороший пример — мы же не используем метафору «пространства решений» для генетического алгоритма? (ну используем только в очень простых случаях, чтобы строить красивые графики и объяснять) И для PSO пространство решений (а тем более кол-во измерений) не обязательно (раз мы можем PSO свести к модификации ГА).
Как не используем? Это часть любого формального описания.
Задача любой оптимизации — найти минимум некоторой вещественной функции fitness(x1, x2… xn).
[x1, x2… xn] — координата точки этого пространства.
Градиентный спуск, кстати, тоже можно свести к модификации ГА =)
Особь — одна, оператор мутации: точка + градиент в точке.
Задача любой оптимизации — найти минимум некоторой вещественной функции fitness(x1, x2… xn).
[x1, x2… xn] — координата точки этого пространства.
Градиентный спуск, кстати, тоже можно свести к модификации ГА =)
Особь — одна, оператор мутации: точка + градиент в точке.
Пространство решений в математике — это просто символ, а не n-мерное пространство в нашей голове. В голове оно мешает. Проще представить PSO для программы в виде графа связанных между собой программ. Хорошая программа отдаёт свои куски в более плохую (на основе того, насколько они отличаются между собой). В итоге и нет зависимости кол-ва пчёл от измерений (если оно вообще было), хотя, конечно, пчёл мало не бывает :).
Ну а плюс, нам для PSO желательно не любое пространство решений. То есть мы не можем просто случайно раздать всем возможным алгоритмам свои координаты. Чтобы PSO нормально работал:
Если у нас есть алгоритмы A (с координатами x1, y2) и B (x2, y2), то алгоритм C, который расположен посредине между (x1, y1) и (x2, y2) должен иметь свойства частично присущие A, частично B.
Иначе у нас будет случайный перебор — близость между двумя пчёлами не будет означать близости значений fitness’а → следовательно понятие расстояния уже не имеет смысла и пчеле не имеет смысла лететь к более успешной пчеле.
Ну а распределить всё (бесконечное) множество алгоритмов по n-координатам так, чтобы это свойство соблюдалось будет очень сложно ;).
Если у нас есть алгоритмы A (с координатами x1, y2) и B (x2, y2), то алгоритм C, который расположен посредине между (x1, y1) и (x2, y2) должен иметь свойства частично присущие A, частично B.
Иначе у нас будет случайный перебор — близость между двумя пчёлами не будет означать близости значений fitness’а → следовательно понятие расстояния уже не имеет смысла и пчеле не имеет смысла лететь к более успешной пчеле.
Ну а распределить всё (бесконечное) множество алгоритмов по n-координатам так, чтобы это свойство соблюдалось будет очень сложно ;).
близость между двумя пчёлами не будет означать близости значений 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. Ну и так далее.
Пространство, понятное дело, евклидовым не будет.
Кстати, если использовать ГА или PSO для генерации программ, то возникает ещё более интересный вопрос, как кодировать алгоритм, чтобы операция мутации и кроссовера была простой и лёгкой. Сейчас в основном используют нейронные сети или иерархические языки, но мне кажется, что это неправильный путь заимствования и я разрабатываю специальный язык, чтобы кодировать программы в для ГА — evolu.org
Как я понял, язык императивный?
Да. Главный смысл — отсутствие вложенности [операторов if и т. д.] и прямое и простое кодирование в байты. Чтобы со строкой байт можно было делать всё что угодно и результат откомпилируется и будет отличаться от родителя, в зависимости от того, какие сильные были мутации. Можно скопировать кусок байт из алгоритма A и вставить в любое место алгоритма B, который в итоге приобретёт какие-то свойства алгоритма A.
Язык вообще на ДНК немного похож :).
Язык вообще на ДНК немного похож :).
Вполне применимо для систем видео наблюдения с использованием множества видеокамер, если говорить о практической пользе.
Необходимо только доработать сам алгоритм, в том смысле как идут сообщения между «пчелами». Это должно быть не «как-то» а более конкретно. В жизни кажется каждая пчела сообщает о своей находке более энергичным движением.
Необходимо только доработать сам алгоритм, в том смысле как идут сообщения между «пчелами». Это должно быть не «как-то» а более конкретно. В жизни кажется каждая пчела сообщает о своей находке более энергичным движением.
Кстати, автор, совершенно странно, что ты не используешь оригинальное английское название алгоритма (Particle Swarm Optimization), хотя бы для поиска статьи.
алгоритм неплохо показал себя, когда экстремум периодически меняет свою позицию каждый раз появляясь в случайном месте и тогда весь рой как-бы летает за этим неуловимым экстремумом
Большинству теорий не хватает как раз вот таких вот картинок, демонстрирующих работу моделей.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Естественные алгоритмы. Реализация алгоритма поведения роя пчёл