Из книги:
Кирсанов М.Н. Графы в Maple - М.:ФИЗМАТЛИТ, 2007.
Графы в Maple
Способ 3. Одним из методов искусственного интеллекта является муравьиный алгоритм Марко Дориго1. Основная идея алгоритма подсмотрена в природе и имитирует движение колонии муравьев. По форме этот алгоритм похож на жадный Nva (способ 1) и в некоторой степени является его обобщением. Если в алгоритме ближайшего соседа выбор дальнейшего пути производится, исходя из минимального расстояния до очередной вершины, то здесь выбором управляет случайная функция, направляющая движение от текущего положения с большей вероятностью в вершину j, в которой наибольшее значение некоторой функции Pij,k (где i - номер вершины, в которой производится выбор, k - номер муравья, движущегося по дугам графа). Как и в Nva, во время движения создается список пройденных вершин, что позволяет избежать преждевременного зацикливания. Приведем вид функции, управляющей переходом из данной вершины i в вершину j:
Pij,k = tija hijb

е
m 
 tima himb
,
(0.1)
где tij - количество феромона (pheromon), оставленного муравьями на дуге [i,j]; hij - величина, обратная весу (длине) дуги [i,j]; a, b - эмпирические коэффициенты. Функция Pij,k подсказывает муравью номер вершины j, в которую он должен направиться. В знаменателе (1) стоит нормирующий коэффициент, такой, что 0 Ј Pij,k Ј 1. Индекс m в сумме пробегает по всем непройденным вершинам, смежным с i. В реальности муравей оставляет след (феромон) во время прохождения пути, и чем чаще он возвращается в исходную точку (а это возможно, если он выбирает оптимальные пути), тем четче след. В математической же модели функция tij увеличивается только по завершении маршрута на величину, обратно пропорциональную длине маршрута. При a = 0 алгоритм совпадает с Nva - муравей руководствуется только длиной пути. При b = 0 основой для выбора пути является только опыт (количество феромона, или <<глубина следа>>) предыдущих муравьев-исследователей. Важно отметить еще одно отличие от алгоритма Nva. Выбор пути производится не по максимуму функции Pij,k, а случайным образом, но на случай, конечно, влияет значение Pij,k. Поясним это на примере. Пусть муравей k подошел к некоторой вершине 8 и обнаружил, что перед ним 7 возможных путей к семи вершинам (на уже пройденные он внимания не обращает). Куда идти? Муравей доверяется случаю. Он <<пускает рулетку>> (рис. 4.). В какой


сектор <<шарик>>  закатится, туда и идти. Однако рулетка, размеченная функцией P8 j,k, j=1,...,7, имеет неравные сектора. Чем ближе вершина и чем глубже туда след, тем больше сектор. Таким образом, муравей использует и опыт предшественников (tij), и здравый смысл (hij ), и случайный фактор, т.е. все как в жизни.
Для того чтобы не пропустить оптимальное решение, в муравьином алгоритме предусмотрено <<испарение>> следа. Это достигается введением коэффициента p в итеративной формуле tij = (1 - p)tij, применяющейся после каждого цикла обхода графа.
В алгоритме действует целая колония муравьев. Математически это означает, что в каждом цикле обхода движение производится из разных вершин независимым образом.
Здесь приведен самый простой вариант алгоритма. Алгоритм может быть улучшен. Для ускорения сходимости иногда вводят так называемых элитных муравьев [33]. В [7] приведены наилучшие комбинации параметров a и b.

Bibliography

[1]
Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. - М.: Мир, 1979.
[2]
Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. - Ижевск: НИЦ <<Регулярная и хаотическая динамика>>, 2001.
[3]
Белоусов А.И., Ткачев С.Б. Дискретная математика. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2001.
[4]
Берж К. Теория графов и ее применения. - М.: Изд-во иностранной литературы, 1962.
[5]
Говорухин В.Н., Цибулин В.Г. Компьютер в математическом исследовании. Учебный курс. - СПб.: Питер, 2001.
[6]
Горбатов В.А., Горбатов А.В., Горбатова М.В. Дискретная математика. - М.: АСТ, 2003.
[7]
Джонс М.Т. Программирование искусственного интеллекта в приложениях. - М.: ДМК Пресс, 2004.
[8]
Дьяконов В.П. MAPLE 6: учебный курс. - СПб.: Питер, 2001.
[9]
Дьяконов В.П. MATLAB: учебный курс. - СПб.: Питер, 2001.
[10]
Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. - М.: Наука, 1990.
[11]
Зубов В.С., Шевченко И.В. Структуры и методы обработки данных. Практикум в среде Delphi. - М.: Филинъ, 2004.
[12]
Иглин С.П. Решение некоторых задач теории графов в MATLAB// Exponenta Pro. Математика в приложениях. 2004. 4(4).
[13]
Иванов Б.Н. Дискретная математика. Алгоритмы и программы.- М.: Лаборатория базовых знаний, 2002.
[14]
Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. - СПб.: БХВ-Петербург, 2003.
[15]
Кирсанов М.Н. Решебник. Теоретическая механика/ Под ред. А.И. Кириллова. - М.: Физматлит, 2002.
[16]
Кнут Д.Э. Искусство программирования. - М.: Издательский дом <<Вильямс>>, 2003. Т 1, 3.
[17]
Кристофидес Н. Теория графов. Алгоритмический подход. - М.: Мир, 1978.
[18]
Круг П.Г. Нейронные сети и нейрокомпьютеры. - М.: Изд-во МЭИ, 2002.
[19]
Липский В. Комбинаторика для программистов. - М.: Мир, 1988.
[20]
Макконнелл Дж. Основы современных алгоритмов. - М.: Техносфера, 2004.
[21]
Манзон Б.М. Maple V Power Edition. - М.: ИИД <<Филинъ>>, 1998.
[22]
Матросов А. Maple 6. Решение задач высшей математики и механики. - СПб.: БХВ-Петербург, 2001.
[23]
Москинова Г.И. Дискретная математика. Математика для менеджера. - М.: Логос, 2000.
[24]
Носов В.А. Комбинаторика и теория графов. - М.: МГУ, 1999.
[25]
Оре О. Теория графов. - М.: Наука, 1980.
[26]
Очков В.Ф. Mathcad 12 для студентов и инженеров. - СПб.: БХВ-Петербург, 2005.
[27]
Показеев В.В., Матяш В.И., Черкесова Г.В., Кирсанов М.Н. Элементы дискретной математики. Курс лекций. - М.: МГТУ <<МАМИ>>, 2004.
[28]
Редькин Н.П. Дискретная математика. - СПб.: <<Лань>>, 2003.
[29]
Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики. - М.: ИНФРА-М, Новосибирск: Изд-во НГТУ, 2002.
[30]
Фляйшнер Г. Эйлеровы графы и смежные вопросы. - М.: Мир, 2002.
[31]
Хаггарти Р. Дискретная математика для программистов. - М.: Техносфера, 2003.
[32]
Харари Ф. Теория графов. - М.: Едиториал УРСС, 2003.
[33]
Штовба С.Д. Муравьиные алгоритмы// Exponenta Pro. Математика в приложениях. 2004. 4(4)