22:44 Задача коммивояжёра. Метод эластичной сети |
Метод эластичной сети - его использовали Дурбин (Durbin) и Уиллшоу (Willshaw), указавшие аналогию с механизмами установления упорядоченных нейронных связей. Каждый из маршрутов коммивояжёра рассматривался как отображение окружности на плоскость (в каждый город на плоскости отображается некоторая точка этой окружности). Соседние точки на окружности должны отображаться в точки, по возможности ближайшие и на плоскости. Алгоритм Начинается с установки на плоскость небольшой окружности. Она неравномерно расширяется, становясь кольцом, проходящим практически около всех городов и устанавливая таким образом искомый маршрут. На каждую движущуюся точку кольца оказывает действие две составляющие: перемещение точки в сторону ближайшего города и смещение в сторону соседей точки на кольце так, чтобы уменьшить его длину. Город в итоге связывается с определенным участком кольца по мере расширения. По мере расширения такой эластичной сети каждый город оказывается ассоциирован с определенным участком кольца. Вначале все города оказывают приблизительно одинаковое влияние на каждую точку маршрута. В последующем, большие расстояния становятся менее влиятельными и каждый город становится более специфичным для ближайших к нему точек кольца. Такое постепенное увеличение специфичности, которое напоминает метод обучения сети Кохонена, контролируется значением некоторого эффективного радиуса. Дурбин и Уиллшоу показали, что для задачи с 30 городами, рассмотренной Хопфилдом и Танком, метод эластичной сети генерирует наикратчайший маршрут примерно за 1000 итераций. Для 100 городов найденный этим методом маршрут лишь на 1 % превосходил оптимальный. Муравьиный алгоритм — один из эффективных полиномиальных алгоритмов для нахождения приближённых решений задачи коммивояжёра, а также решения аналогичных задач поиска маршрутов на графах. Суть подхода заключается в анализе и использовании модели поведения муравьёв, ищущих пути от колонии к источнику питания, и представляет собой метаэвристическую оптимизацию. Первая версия алгоритма, предложенная доктором наук Марко Дориго в 1992 году, была направлена на поиск оптимального пути в графе. Генетический алгоритм — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, аналогичных естественному отбору в природе. Генетические алгоритмы применяются для решения следующих задач:
По материалам сайта: |
|
|
| Всего комментариев: 0 | |