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

[saboteur_kiev]

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

[QtRoS]

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

[daiver19]

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

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

[Grossmend]

Если бы метода отжига не существовало и мне бы предложили написать данный алгоритм, то я бы даже не брался. Как-то сложно поверить в него. Однако, он выдает отличные результаты. Вы правильно подметили что он универсален.

[daiver19]

Да, я понимаю. Чтобы прочувствовать это стоит попробовать простой hill climbing (случайно меняем решение и если оно улучшилось, то оставляем его), который показывает весьма неплохие результаты. Отжиг кажется логичным развитием этого алгоритма.

[Grossmend]

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

[zartdinov]

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

[Grossmend]

Здравствуйте, можно чуть подробней.

[daiver19]

Когда мы меняем две вершины местами остальные вершины остаются на прежнем месте. Поэтому операция перемены мест двух вершин эквивалентна удалению 3-4 ребер из пути и добавлению новых 3-4 ребер. Значит мы можем пересчитывать только эти ребра, итого модификация занимает константное время. Собственно этот подход используют как раз из-за скорости вычисления. Если пересчитывать весь маршрут, то можно делать очень сложные модификации, но обычно это не нужно. Хотя добавление более сложных операций вроде вставки вершины из одного места в другое может несколько ускорить сходимость (ценой усложнения реализации эффективного рассчета пути).

[Grossmend]

Да, спасибо! Так эффективнее. Выйдет во второй части статьи.

[janvaljanichceria]

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

[Asker1987]

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

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

[Grossmend]

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

[Siegurd]

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