Муравьиный алгоритм: MMAS(Max-Min муравьиная система)

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

ВОЛГОГРАДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

(ВолгГТУ)

ФАКУЛЬТЕТ ЭЛЕКТРОНИКИ И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ

Кафедра «Системы автоматизированного проектирования и поискового конструирования»

Реферат по дисциплине «Методы оптимизации»

Тема: «Муравьиный алгоритм: MMAS(Max-Min муравьиная система)»

Выполнил:

Студент группы ---------

---------------

Проверила:

----------------

Волгоград 2021 г.

Оглавление

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

2. Задача коммиваяжёра        4

3. Вариация алгоритма муравьев - MMAS (Max-Min муравьиная система)        5

4. Код        5

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

Муравьиный алгоритм — один из эффективных полиномиальных алгоритмов для нахождения приближённых решений задачи коммивояжёра, а также решения аналогичных задач поиска маршрутов на графах. Суть подхода заключается в анализе и использовании модели поведения муравьёв, ищущих пути от колонии к источнику питания. Первая версия алгоритма, предложенная доктором наук Марко Дориго в 1992 году, была направлена на поиск оптимального пути в графе.

В основе алгоритма лежит поведение муравьиной колонии — маркировка более удачных путей большим количеством феромона. Работа начинается с размещения муравьёв в вершинах графа (городах), затем начинается движение муравьёв — направление определяется вероятностным методом, на основании формулы вида:

[pic 1]

где:

 – вероятность перехода по пути i,[pic 2]

 – величина, обратная весу (длине) i-го перехода,[pic 3]

 – количество феромона на i-м переходе,[pic 4]

q – величина, определяющая «жадность» алгоритма,

p – величина, определяющая «стадность» алгоритма.

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

2. Задача коммиваяжёра

Задача коммивояжёра — одна из самых известных задач комбинаторной оптимизации, заключающаяся в поиске самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и тому подобное) и соответствующие матрицы расстояний, стоимости и тому подобного. Как правило, указывается, что маршрут должен проходить через каждый город только один раз — в таком случае выбор осуществляется среди гамильтоновых циклов (замкнутый путь). Также существует обобщение задачи, так называемая обобщённая задача коммивояжёра.