Имитация - отжиг
Cтраница 3
Разработан ряд стохастических методов решения поставленной оптимизационной задачи распараллеливания вычислений. В первом методе - стохастическом методе попарной оптимизации подграфов - поиск оптимального решения осуществляется за счет взаимного ( стохастического) переноса вершин между различными парами подграфов графа алгоритма. Второй метод - метод Монте-Карло случайного блуждания вершин графа алгоритма по подграфам - основан на отождествлении вершин графа алгоритма с некоторыми частицами, совершающими случайные блуждания по областям-подграфам в потенциальном силовом поле, роль потенциала которого играет минимизируемый функционал. Наиболее вероятное состояние подобной системы частиц соответствует минимуму потенциала - - и, следовательно, является искомым решением. Поиск такого состояния осуществляется методом Монте-Карло с использованием специальной процедуры имитации отжига. Третий метод - стохастический метод наискорейшего спуска - основан на использовании дискретного аналога градиента минимизируемого функционала. Все разработанные методы реализованы программно и являются частью системы программ PARALLAX. Проведено тестирование созданных программ и сравнение их работы на простейших примерах. [31]
 |
Муравьи находят новый кратчайший новый путь ( сверху от преграды который быстрее обогащается феромонами.| Результаты решения задачи коммивояжера ( длина маршрута. [32] |
Такие муравьи могут решить и нашу задачу коммивояжера. В этом случае они движутся от города к городу по ребрам соответствующего графа. При этом они выбирают направление движения, используя вероятностную функцию, зависящую как от предыдущих попыток движения по данному ребру, так и от эвристического значения, являющегося функцией длины ребра. ИМ с большей вероятностью будут предпочитать ближайшие города и города, связанные ребрами, наиболее богатыми феромонами. Первоначально N искусственных муравьев размещаются в случайно выбранных городах. В отличие от живых муравьев; ИМ обладают способностью определять расстояние до соседних городов и помнят, какие города они уже посетили. Оказывается, метод искусственных муравьиных колоний может давать результаты, лучшие чем при использовании имитации отжига, нейронных сетей, и генетических алгоритмов. [33]
Страницы: 1 2 3