Должен ли алгоритм Ant Colony показывать лучший путь в 100% случаев?

Я разработал алгоритм колонии муравьев. Это работает довольно хорошо в данный момент.

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

Например, у меня есть этот график:

Матрица это:

    1   2   3   4   5   6   7
1   0   6   5   0   0   2   0
2   6   0   3   2   1   5   0
3   5   3   0   2   5   0   0
4   0   2   2   0   3   0   0
5   0   1   5   3   0   6   0
6   2   5   0   0   6   0   2
7   0   0   0   0   0   2   0

Первый столбец и первая строка являются именами вершин.

Итак, возможные пути (путь - длина пути):

1. 1-2-5 with length 7
2. 1-6-2-5 with length 8
3. 1-6-5 with length 8

Моя программа выбирает 1-й путь в 1/10 запусков, 2-й путь в 7/10 запусков и 3-й путь в 2/10 запусках программы.

Это работает правильно?

Объяснение этому заключается в том, что у муравьев есть свои глаза (зрение, они смотрят на длину ребер), а также они могут определять уровень феромонов. Их собственные глаза показывают, что край 1-2 довольно длинный и длинный, чем край 1-6, поэтому обычно они выбирают край 1-6 вместо выбора 1-2. То же самое для 6-5 и 6-2: 6-2 более привлекательно, потому что оно короче.

Я прав с моим предположением?

Источник

3 ответа

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

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

Локальная мера обычно связана с качеством определенного шага: стоимость ребра, в представленном примере.

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

Источник

В соответствии с этим: http://en.wikipedia.org/wiki/Ant_colony_optimization_algorithms, я вижу две проблемы в вашем подходе:

  1. муравьи (изначально) бродят случайным образом; это не имеет никакого отношения к зрению или длине соседнего края
  2. ты вообще моделируешь эти феромоновые трассы?

Отвечая на вопрос: должен ли алгоритм Ant Colony показывать лучший путь в 100% случаев? Нет, он не должен показывать лучший путь вообще.

Источник

Почему вы используете муравьиную колонию для кратчайшего пути? Если вы ищете кратчайший путь, вам не нужен алгоритм оптимизации, лучшее решение может быть достигнуто за полиномиальное время с алгоритмом A* (с оптимальной эвристической функцией). Муравьиная колония лучше, когда вы используете ее для решения проблемы TSP.

И ответ: нет - имейте в виду, что алгоритм вероятностный, поэтому он может привести не к лучшему решению, а к локальному минимуму

Источник
Другие вопросы по тегам