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

andrey_hse Apr 29 2013 at 19:56

Не совсем понятен вопрос по поводу сравнения роевых алгоритмов. По сути, все они являются некой реализацией цельной системы (рыбы, птицы, муравьи, пчелы и т.п.), которая перемещается благодаря роевому интеллекту. Да, может быть, на каких-то функциях некоторые методы поиска будут иметь преимущества, но, опять же, нельзя сказать с уверенностью тоже самое о всем алгоритме в целом.
Популяционные алгоритмы имеют тот же круг задач, что и генетические, о которых уже много писалось на Хабре. Среди них можно выделить такие вещи, как: аппроксимация изображений , довольно-таки интересный музыкальный проект, генерация дизайнерских идей, поиск лучшей стратегии игры и еще много чего интересного.

kenoma Apr 29 2013 at 21:17

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

andrey_hse Apr 29 2013 at 21:53

Безусловно, многое зависит от самой исследуемой функции. Извините, но мне проще дать ссылку на статью про методы оптимизации, чем расписывать о них здесь.

-1

kenoma Apr 29 2013 at 23:05

Как-то странно, что вы привели ссылку на википедию, в которой ни коим образом не проливается свет на предмет моего интереса)

nagimov Apr 29 2013 at 20:25

Разрешите вопрос от дилетанта.
Я не очень силен в математике и алгоритмах, посему оптимизацию обычно доверяю спец. пакетам, либо (если позволяет машинное время) перебираю «в лоб».
В последняя время приходится часто сталкиваться проблемами многопараметрической оптимизации, которые не удается решить прямым перебором значений по сетке (занимает много времени). Особенность исследумых функций заключается в том, что зачастую не получается «взять» значение функции в произвольной точке (это связано с использованием функций свойств реальных веществ, которые зачастую известны лишь в некоторой окрестности). В подобных задачах генетические алгоритмы часто работают много дольше чем метод прямого поиска и variable metric method (метод переменной метрики?). Существует ли способ «заточить» генетический алгоритм под вышеприведенные условия?

andrey_hse Apr 29 2013 at 21:06

Как уже было сказано в статье, время работы алгоритма зависит напрямую от введенных параметров его работы. Рекомендации по выбору этих параметров для конкретной функции, как правило, отсутствуют. Для решения этой проблемы используются так называемые метаэвристические самоадаптирующиеся алгоритмы (к сожалению, провести исследования в этой области пока не удалось). А вообще, генетические алгоритмы хорошо параллелятся, что и позволяет использовать кластеризацию. Вопрос только в том, что высчитывать функцию приспособленности все равно приходится на каждой итерации, поэтому для ресурсоемких вычислений можно применить данных алгоритм с каким-нибудь методом аппроксимации.

nagimov Apr 30 2013 at 02:33

Иными словами, вы не сможете объяснить «быстро и на пальцах» как лучше расставить ползунки? i.imgur.com/VYYneUy.png

andrey_hse Apr 30 2013 at 07:50

Нет

HomoLuden Apr 30 2013 at 09:18

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

kirias Apr 29 2013 at 23:38

кукушкин поиск

Ничего не нашел, что это?

andrey_hse Apr 30 2013 at 07:58

Алгоритм «Кукушкин поиск» основан на том, что некоторые виды кукушек любят подбрасывать свои яйца в чужие гнезда, при этом иногда вымещая уже имеющиеся в них яйца. Также и те, к кому подкладывают яйцо, могут обнаружить подмену и избавиться от него. Более подробно данный алгоритм описан в статье Карпенко (2 ссылка в Источниках).

MrEsp Apr 30 2013 at 13:01

Алгоритм понравился, а если добавить в статью сравнение с более классической реализацией GA, то было бы интереснее. Также позволю себе высказать основанное на опыте использования GA мнение, что конструкция гиперкуба значений (а в данном случае это вообще R^2 (-100;-100) до (100; 100) ) слишком проста, как и вид целевой функции. На таких простых примерах едва ли можно что-либо предположить о том, какие же оптимальные условия применимости данного алгоритма, и вообще есть ли приемущество его использования, например, в пространстве поиска R^10 при большем диаметре множества пространства значений.

Show the best of all time