Муравьиный алгоритм задача коммивояжера python

Русские Блоги

Пример алгоритма оптимизации муравьиной колонии (код на Python)

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

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

Для реализации алгоритма ACO необходимо проанализировать несколько элементов, а именно:Построить график、ограничение、Феромон и эвристическая информация、Построение решения、Обновление феромоновПодождите.

По вопросам TSP:
Построить графикВ соответствии с описанием проблемы, то есть каждая сторона имеет вес, который представляет расстояние между точками.Состояние проблемы — это набор всех возможных состояний, которые появляются во время путешествия коммивояжера.
ограничение: Единственное ограничение в TSP — это то, что все города должны быть посещены, и каждый город может быть посещен только один раз во время путешествия коммивояжера.
Феромон и эвристическая информация: Феромон в TSP представляет ожидание посещения города j сразу после посещения города i. Эвристическая информация представляет собой вероятность того, что муравей случайным образом выберет следующий город. Значение следует выбирать в соответствии с реальной ситуацией. Как правило, непосредственно берется величина, обратная расстоянию между двумя городами.
Построение решения: Каждый муравей изначально начинается со случайно выбранного начального города. После каждой итерации муравей добавляет к решению город, который еще не был посещен. Когда все города были посещены муравьями, построение решения заканчивается. При построении решения муравьи используют феромон и эвристическую информацию для выбора городов-кандидатов с определенной вероятностью P.

Функция в параметрах α и β следующая: если α = 0, наиболее вероятно будет выбран ближайший город, что эквивалентно классическому случайному жадному алгоритму; если β = 0, то работает только коэффициент усиления феромона.Иными словами, алгоритм использует только феромон без смещения, вызванного какой-либо эвристической информацией, особенно когда α> 1, алгоритм быстро перейдет в состояние застоя.
Обновление феромонов: После того, как все муравьи построят путь, феромоны на каждой стороне будут обновлены. Сначала феромон со всех сторон будет уменьшен на постоянный коэффициент, а затем феромон будет добавлен со стороны, по которой проходит муравей. Испарение феромона осуществляется по следующей формуле:

где ρ — скорость испарения феромона, причем 0 После стадии испарения феромона все муравьи выделяют феромон на той стороне, мимо которой они проходят:
где C представляет длину пути, установленного k-м муравьем.

Согласно приведенной выше формуле, мы можем видеть, что чем лучше путь, построенный муравьями, тем больше феромона будет получено с каждой стороны пути. Вообще говоря, если край выбирается большим количеством муравьев, а общая длина пути, на котором расположен край, короче, тем больше феромона будет получено на этом краю, и с большей вероятностью он будет выбран муравьями в будущие итерации.
Ниже приведен код Python для решения проблемы TSP с ACO.

# Оптимизация колонии Ant для решения проблемы TSP import numpy as np import random as rd def lengthCal(antPath,distmat): # Рассчитать расстояние length =[] dis = 0 for i in range(len(antPath)): for j in range(len(antPath[i]) - 1): dis += distmat[antPath[i][j]][antPath[i][j + 1]] dis += distmat[antPath[i][-1]][antPath[i][0]] length.append(dis) dis = 0 return length distmat = np.array([[0,35,29,67,60,50,66,44,72,41,48,97], [35,0,34,36,28,37,55,49,78,76,70,110], [29,34,0,58,41,63,79,68,103,69,78,130], [67,36,58,0,26,38,61,80,87,110,100,110], [60,28,41,26,0,61,78,73,103,100,96,130], [50,37,63,38,61,0,16,64,50,95,81,95], [66,55,79,61,78,16,0,49,34,82,68,83], [44,49,68,80,73,64,49,0,35,43,30,62], [72,78,103,87,103,50,34,35,0,47,32,48], [41,76,69,110,100,95,82,43,47,0,26,74], [48,70,78,100,96,81,68,30,32,26,0,58], [97,110,130,110,130,95,83,62,48,74,58,0]]) antNum = 12 # Не номер alpha = 1 # Фактор важности феромона beta = 3 # Фактор важности эвристической функции pheEvaRate = 0.3 # Скорость испарения феромона cityNum = distmat.shape[0] pheromone = np.ones((cityNum,cityNum)) # Феромоновая матрица heuristic = 1 / (np.eye(cityNum) + distmat) - np.eye(cityNum) # Матрица эвристической информации, дубль 1 / дизмат iter,itermax = 1,100 # Итерации while iter  itermax: antPath = np.zeros((antNum, cityNum)).astype(int) - 1 # Путь муравья firstCity = [i for i in range(12)] rd.shuffle(firstCity) # Случайно назначьте начальный город для каждого муравья unvisted = [] p = [] pAccum = 0 for i in range(len(antPath)): antPath[i][0] = firstCity[i] for i in range(len(antPath[0]) - 1): # Постепенно обновляйте следующий город, в который собирается каждый муравей for j in range(len(antPath)): for k in range(cityNum): if k not in antPath[j]: unvisted.append(k) for m in unvisted: pAccum += pheromone[antPath[j][i]][m] ** alpha * heuristic[antPath[j][i]][m] ** beta for n in unvisted: p.append(pheromone[antPath[j][i]][n] ** alpha * heuristic[antPath[j][i]][n] ** beta / pAccum) roulette = np.array(p).cumsum() # Создать рулетку r = rd.uniform(min(roulette), max(roulette)) for x in range(len(roulette)): if roulette[x] >= r: # Используйте метод рулетки, чтобы выбрать следующий город antPath[j][i + 1] = unvisted[x] break unvisted = [] p = [] pAccum = 0 pheromone = (1 - pheEvaRate) * pheromone # Феромон летучий length = lengthCal(antPath,distmat) for i in range(len(antPath)): for j in range(len(antPath[i]) - 1): pheromone[antPath[i][j]][antPath[i][j + 1]] += 1 / length[i] # Обновление феромона pheromone[antPath[i][-1]][antPath[i][0]] += 1 / length[i] iter += 1 print(«Кратчайшее расстояние:») print(min(length)) print(«Самый короткий путь:») print(antPath[length.index(min(length))]) 

Источник

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

SinVl/Ant_algorithm

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

Муравьиный алгоритм для задачи коммивояжера

Для задачи коммивояжера был применен муравьиный алгоритм обхода графа. Решений заключается в итеррационном обходе графа колонией муравьев. Каждый муравей строит свой путь по графу, выбор следующей вершины зависит от величины феромона и веса дуги, эти параметры контролируются коэффициентами «a» и «b (при большом «a» решение сходится в локальный минимум, при большом «b» алгоритм становится жадным и выбирает ближайщие вершины). После обхода муравьями проверяется минимальный полученный путь. Феромоны на всех дугах испараются с коэффициентом (1-p) после каждой итерации и так же обновляются феромоны на дугах которые посетили муравьи.

Источник

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

Муравьиный алгоритм для задачи коммивояжера

plushchaynikolay/ant_algorithm

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

Муравьиный алгоритм для задачи коммивояжера Решение задачи коммивояжера муравьиным алгоритмом.

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

В решении присутствует эффект высыхания феромона. В решении не используются «элитные» муравьи, хотя блок кода присутствует и закомментирован. Возможны три варианта начального расположения муравьев в графе. Используется равномерное расположение, но случайное и «все-из-одного» присутствуют в коде и закомментированы. В решении используется глобальное распределение феромона (после прохождения всех муравьев). Присутствует эффект локального распределения феромона (после прохождения каждого муравья) в коде, но он закомментирован. Есть возможность вывода графика зависимости полученного решения от числа итераций, присутствует в коде и закомментировано.

About

Муравьиный алгоритм для задачи коммивояжера

Источник