Муравьиный алгоритм

Здравствуйте. Хотел уточнить у знающих несколько моментов в данном алгоритме. Везде, где я смотрел, данный алгоритм используется для решения задачи коммивояжера. Я же хотел просто найти кратчайший путь. Что я сделал:
1) Задал матрицу смежности
2) Расставил на ребрах некоторое начальное значение феромонов
3) Расположил всех муравьев в начальное точке
4) Муравьи по очереди начинают искать путь до конечного пункта
5) Чтобы сделать выбор, куда идти, вычисляется вероятность перехода по формуле p = (t * 1 / l) / sum, t - феромоны, l - длина данного ребра, sum - cумма (t * 1/l) для всех смежных ребер
6) Выбор делается "случайно". То есть производится генерация случайного числа. Если вероятность перехода по ребру равна 64%(умножил на 100), то, если генерированное число меньше 64, то идем по нему и так далее
7) По пути оставляют за собой феромоны(по формуле t(new) = (1-p)*t(old) + delta, где t - феромон на ребре, а delta = 1/D(D-длина путь текущего муравья, который прошел по данному ребру)
8) Это повторяется для всех муравьев, затем обновляются все феромоны и вероятности перехода

Теперь вопросы. Правильный ли алгоритм? Я тестировал его на простом графе. Он выдавал не оптимальное решение. Вне зависимости от параметров, которые я задавал.

0

Сообщение от Not a number Я же хотел просто найти кратчайший путь.

Какой сложный алгоритм Вы выбрали для решения такой простой задачи.

Сообщение от Not a number Правильный ли алгоритм?

Полагаю, что нет.

Сообщение от Not a number t(new) = (1-p)*t(old) + delta

Почему на более привлекательных путях феромоны испаряются быстрее?

0

Shamil1,

Сообщение от Shamil1 Какой сложный алгоритм Вы выбрали для решения такой простой задачи

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

Сообщение от Shamil1 Полагаю, что нет.

Эм, я, конечно, рад, что Вы ответили, но разрешите более развернуто. Алгоритм не я выдумал, читал разные источники. Может быть что-то и упустил.

Сообщение от Shamil1 Почему на более привлекательных путях феромоны испаряются быстрее?

"Испаряются быстрее"? Что Вы имеете в виду? Эта формула действует для тех ребер, по которым прошел муравей, те ребра, которые муравей обделил своим вниманием, только теряют активность феромона.

0

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

Сообщение от Shamil1 Почему на более привлекательных путях феромоны испаряются быстрее?

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

Добавлено через 7 минут
Я надеюсь ты муравьям запретил повторное посещение узлов?

По возможности попробуй сделать визуализацию чтобы тебе показывалась карта распределения феромонов поверх рисунка графа.
Обычно в качестве демонстрации берут граф в виде 2D массива (можно с лабиринтом) и отрисовывают его в виде картинки.

1