Линейная алгебра и мат. Статистика
жүктеу/скачать 294.26 Kb.
|
- Бұл бет үшін навигация:
- Метод имитации отжига
| Задача коммивояжёра (коммивояжёр — бродячий торговец) заключается в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и т. п.) и соответствующие матрицы расстояний, стоимости и т. п. Как правило указывается, что маршрут должен проходить через каждый город только один раз, в таком случае выбор осуществляется среди гамильтоновых циклов.
Существует масса разновидностей обобщённой постановки задачи, в частности геометрическая задача коммивояжёра (когда матрица расстояний отражает расстояния между точками на плоскости), треугольная задача коммивояжёра (когда на матрице стоимостей выполняется неравенство треугольника), симметричная и асимметричная задачи коммивояжёра. Простейшие методы решения задачи коммивояжёра: полный лексический перебор, жадные алгоритмы (метод ближайшего соседа, метод включения ближайшего города, метод самого дешёвого включения), метод минимального остовного дерева. На практике применяются различные модификации более эффективных методов: метод ветвей и границ и метод генетических алгоритмов, а так же алгоритм муравьиной колонии. Метод имитации отжига Один из численных методов Монте-Карло. Пусть имеется некоторая функция от состояния , которую мы хотим минимизировать. В данном случае это перестановка вершин (городов) в том порядке, в котором мы будем их посещать, а это длина соответствующего пути. Возьмём в качестве базового решения какое-то состояние (например, случайную перестановку) и будем пытаться его улучшать. Введём температуру — какое-то действительное число (изначально равное единице), которое будет изменяться в течение оптимизации и влиять на вероятность перейти в соседнее состояние. Пока не придём к оптимальному решению или пока не закончится время, будем повторять следующие шаги: Уменьшим температуру Выберем случайного соседа — то есть какое-то состояние , которое может быть получено из каким-то минимальным изменением. С вероятностью сделаем присвоение В каждом шаге есть много свободы при реализации. Основные эвристические соображения следующие: В начале оптимизации наше решение и так плохое, и мы можем позволить себе высокую температуру и риск перейти в состояние хуже. В конце наоборот — наше решение почти оптимальное, и мы не хотим терять прогресс. Температура должна быть высокой в начале и медленно уменьшаться к концу. Алгоритм будет работать лучше, если функция «гладкая» относительно этого изменения, то есть изменяется не сильно. Вероятность должна быть меньше, если новое состояние хуже, чем старое. Также вероятность должна быть больше при высокой температуре. жүктеу/скачать 294.26 Kb. Достарыңызбен бөлісу:
|