Pull to refresh

Comments 7

Спасибо за статью! Интересные результаты.

Я использую отжиг для обора информативных переменных. Размерность например 10 из 100. Но не могу сказать, что на больших задачах получаю глобальный максимум. Скорее, приближение.

Даже были неоднократные примеры, когда жадный поиск перещеголял стохастический. А времени в 100 раз меньше тратил.
Сравним и с жадными тогда. Думаю будет интересно)
Писал курсовую по этим двум алгоритмам на базе задачи коммивояжера. Муравьи намного состоятельнее оказались на больших графах(больше сотни вершин).Вот так выглядит график сходимости(длина найденного цикла от количества итераций) отжига на графе в 1655 вершин:
image
Вот так для муравьёв:
image
Тут время работы по параметрам я примерно одинаковое подбирал. И отжиг слабенько себя показал(может я настроить не смог толково). Вот муравьи показались интереснее. Много всякого смог оптимизировать.

Когда-то думал статью впилить об оптимизациях этого алгоритма, но и так пруд пруди на хабре уже подообного и лень взяла верх
Про муравьиные алгоритмы на Хабре совсем мало статей) Какая была модификация муравьиного алгоритма? Может скорость отжига была небольшой?) Конечно сложно судить по одному графику, но вроде бы у муравьиного алгоритма был высокий коэффициент обновления феромонов, что сильно сокращает время алгоритма, также как и вероятность нахождения глобального оптимума. В данной статье алгоритм настраивал на глобальный путь, поэтому по времени пока проиграл. Если будет желание и время, то, конечно, напишите статью, будет интересно)
Сомтрел что там на 50 итерации такого происходит. Выводил процент от всех феромонов, которые лежат на наилучшем найденном пути. Было вроде такого:
0.2
0.2
0.2
0.2
0.3
4.2 < — 50-ая итерация
19.1
24.8
26.0
28.6
31.3
На 50-ой итерации видимочень резкий скачокю Тут уровень испарения 0.2. Сравните с P=0.1:
0.2
0.2
0.2
0.2
0.2
0.2
0.2
0.2
0.3
0.8
3.9
Очень медленно сходится, а результат в итоге тот же самый был.

Чуть позже может отдельно по муравьиному запилю пост. Я там всякие интересности наблюдал. По отжигу ничего интересного не получилось
Все таки 350 итераций для 1655 вершин очень мало, может у Вас собственная какая-то разработка. Конечно, напишите, я же тогда еще реализую различные модификации в следующих статьях. Может сойдемся на каких-либо результатах)
Так а толку дальше гонять, если там почти нет улучшений? Ну и медленно работает, да. Я позже находил места где можно было мой код на джава ускорить, но не до того было. У меня 40 муравьёв бегало(если говорить о представленном графике). Хотя это до улучшений(запустил на большом наборе данных и дорабатывал). Вот таблица для сравнения на этом графе после всех моих оптимизаций:
image
То есть примерно в 35 раз ускорил работу=)
Постараюсь на выходных выложить подробнее о том, как процесс оптимизации проходил.
Sign up to leave a comment.

Articles