Многомерный случай?

А насколько хорошо применим этот алгоритм в случае чрезвычайно высокой размерности? Тысячи - десятки тысяч. Укладка графов, например. Когда особо много пчел себе позволить нельзя.

Алгоритм действительно новый, его предложили в 2005 году: http://en.wikipedia.org/wiki/Artificial_Bee_Colony_Algorithm http://mf.erciyes.edu.tr/abc

И статья получилась интересной, спасибо.

jkff

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

hmax

Спасибо за отзыв. Википедия почти дословно повторяет статьи из ссылок :)

графики

Вы только не обижайтесь, но кто блин так графики делает? (Это я про "Рост целевой функции при одном запуске алгоритма" и следующий, "Рост целевой функции, усредненный по 10 запускам алгоритма"). Смотришь на этот график и видишь один белый квадрат, у которого что-то в уголке накорябано. Вы там отрежьте кусочек слева, чтоб он начинался не с 1-й итерации, а с 10-й, а ещё лучше --- сделайте по вертикальной оси логарифмическую систему координат. Там же явно какой-то экспоненциальный или степенной рост идёт.

Булат,

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

Спасибо за идею.

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

Отличная статья, да и сайт вообще.Спасибо! Было бы интересно сравнить возможности и эффективность пчелиного алгоритма и генетического, например.

DmB

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

не сходится :(

Сделал я программу, потестировал на одной функции (средней сложности, зато от 18 переменных.

По моим наблюдениям алгоритм пчел более капризный, чем ГА

короткое описание эксперимента и 2 графика: http://lit999.narod.ru/soft/ga/index.html

Вообще какой алгоритм лучше зависит от функции. Мне попадались функции, где однозначно лучше был ГА, а где-то пчелы.

Statja ochen' interesnaja, no rech' idet tolko ob analiticheskih funkzijah... A esli funkzyja - ksi-kvadrat ili max pravdopodobija? To est' esli funkzija diskretnaja, kak po-vashemu, podhodit etot algoritm?

bim, конкретно с этими функциями я дела не имел, да и вообще трудно заранее сказать какой алгоритм выбрать для данной функции, надо пробовать. Из своего опыта могу сказать, что как правило генетический алгоритм быстрее сходится для большинства функций по сравнению с пчелами, но пчелы как-то лучше находят острые глобальные экстремумы, которые ГА часто пропускает.

пчелы это интересно, но результаты плохие сравните своих пчел с cma-es, pso или eda на наборе задач размерности от 10 + за популяризацию

ошибки в тексте

Аналогично рассчитываются интервалы для выбранных участков: [15; 32] [-41; 21]

И размер квадрата у Вас 20, не 10.

Владимир, спасибо, сейчас исправлю.

The Bees Algorithm

[1] Pham DT, Ghanbarzadeh A, Koc E, Otri S, Rahim S and Zaidi M. The Bees Algorithm. Technical Note, Manufacturing Engineering Centre, Cardiff University, UK, 2005 Поделитесь пожалуйста ссылкой на публикацию. Нигде нимогу найти...

Re: The Bees Algorithm

Что-то я тоже уже не найду эту статью. Но, в принципе, в третьей статье, на которую я дал ссылку, все довольно понятно написано.

а кто-нибудь занимался многокитериальной задачей оптимизации алгоритмом пчел?

Полезная статья.Думаю вклчючить часть информации в свою курсовую, как на вас лучше сослаться?

sad, как Вам удобнее, можете просто ссылку на сайт поставить.

Такое не очень-то приветствуется. А у вас есть печатные издания?

sad, печатные издания есть, но не по самому алгоритму, а только с описанием того, где мы его использовали. Поэтому тогда проще не ссылаться на меня, все-таки не я алгоритм придумал.

ink, я занимался

Ограничения

Начал реализовывать данный алгоритм для своей задачи и наткнулся на проблему с ограничениями координат. Мне необходимо ввести ограничение вида: summ(Xn/summ(X))=1 т.е. координаты могут плавать(каждая в своих рамках) но их сумма постоянна. При этом 0,8*X'n<Xn<1,2*X'n Т.к. метод основан на случайном выборе координат, не получается их ограничить.

Так а в чем все-таки новизна?

А чем он в принципе выигрышней того же простейшего "метода случайной стрельбы"?

В основном в том, что на каждой итерации мы изменяем области, куда "стреляем" больше, куда меньше.

А что если мы не знаем правильный ответ ?

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

Мы знаем, что мы ищем максимум или минимум. Поэтому, там, где значение меньше (или больше), там ответ лучше.