Оптимизация на примере. Имитационный отжиг против муравьиного алгоритма. Часть 1

> А пока посмотрим на сегодняшнего победителя. 500 городов, 86 секунд оптимизации (и это далеко не предел).
> Очень круто!
да!

О, с удовольствием вспоминаю курс Discrete Optimization от Pascal van Hentenryck. Там в последнем задании были тысячи городов, и если кому-то интересно, могу выложить картинку, которая получилась. Одно из популярных решений (кстати, российского участника курсов) даже запечатлили на майке:

Мини-поправка: Имитация отжига, а не «имитационный отжиг».

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

Лично мне интуитивно кажется что ни первый ни второй алгоритм не работают оптимально.
Задача коммивояжера это оптимальный путь, значит, при наличие «скоплений» городов в определенных зонах, алгоритм должен в первую очередь искать оптимальные пути выбирая только из близлежащих городов, и не учитывать удаленные точки.
Что в одном что во втором примере проверяются маловероятные связки и это кажется мне не оптимальным. Поправьте если ошибаюсь.

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

Да, интересно сделано.

Отдавать «победу имитационному отжигу» (ИО) довольно смелый поступок, особенно, в задаче коммивояжера. Либо нужно оговорить, в каких условиях ИО выигрышна. При серьезных временных ограничениях многие алгоритмы «побеждают» муравьиный алгоритм(МА), но чаще важно найти именно оптимум. Можно говорить о конкретных реализациях алгоритмов, но если хотите сравнить, то возьмите научную литературу, статьи уважаемых зарубежных авторов, в открытых источниках приведены бенчмарки. На сколько мне известно, то в этой задаче правят балом генетический алгоритма и МА.
По статье и реализации МА:
1. Нет ссылок на работы других авторов. Конечно, эта статья не для научного журнала, но если делаете громкие заявления, то нужно делать и громкие исследования. Ведь МА и ИО не вчера разработаны, их давно сравнили, в т.ч. на задаче коммивояжера.
2. У Вас приведен пример простейшего МА. Нет смысла говорить о «победе» одного научного направления над другим. Существуют десятки, а то и больше модификаций МА. Простой МА лишь отражает основную идею использования «глобальной памяти» через феромоны.
3. С числом муравьев допущена типовая ошибка — в общем случае число муравьев не равно числу точек. Размер колонии может быть любой и муравьи рандомно располагаются. Иначе МА «моросит» при большом кол-ве точек. Число муравьев должно коррелировать с числом ребер(!), а не вершин. Сравним с естественной средой: чем больше муравьев, тем больше площадь они могут исслдеовать, НО площадь исследования в графе — это число ребер, а не вершин. Слишком вероятна стагнация.
4. Коэффициент бета очень не желательно делать дробной. Честно, не знаю, как устроен матлаб, в С++ всегда избегал дробного возведения в степень, т.к. это увеличивает время в МА, порой даже в разы.

PS. Код не смотрел, уверен там все филигранно)

Победу отдал на «сегодняшний день». Пункты 2-3, а также другие модификации предназначаются для следующих публикаций. 1 – учту. Спасибо.

Расстояние между городами задается по прямой или по реальному расстоянию дороги соединяющей пункты, например с Google Maps?
И если дорога из пунута А в пункт B лежит через пункт С и пункты A и B не связаны с собой отдельной дорогой, как алгоритму это задать?