Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по одному разу в неизвестном порядке города 2,3,4..n и вернуться в первый город. Расстояния между городами известны. В каком порядке следует обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?
Алгоритм решения задачи коммивояжера
Код: Выделить всё
Жадный алгоритм
Жадный алгоритм – алгоритм нахождения наикратчайшего расстояния путём выбора самого короткого, ещё не выбранного ребра, при условии, что оно не образует цикла с уже выбранными рёбрами. «Жадным» этот алгоритм назван потому, что на последних шагах приходится жестоко расплачиваться за жадность.
Посмотрим, как поведет себя при решении ЗК жадный алгоритм. Здесь он превратится в стратегию «иди в ближайший (в который еще не входил) город». Жадный алгоритм, очевидно, бессилен в этой задаче. Рассмотрим для примера сеть на рис. 2, представляющую узкий ромб. Пусть коммивояжер стартует из города 1. Алгоритм «иди в ближайший город» выведет его в город 2, затем 3, затем 4; на последнем шаге придется платить за жадность, возвращаясь по длинной диагонали ромба. В результате получится не кратчайший, а длиннейший тур. Однако в некоторых ситуациях «жадный» алгоритм определяет-таки кратчайший путь.
Полный перебор
Метод полного перебора заключается в том, что выполняется перебор всех возможных комбинаций точек (пунктов назначения). Как известно из математики, число таких перестановок равно n!, где n – количество точек. Так как в задаче коммивояжера исходный пункт обычно принимается одним и тем же (первая точка), то нам достаточно перебрать оставшиеся, т.е. количество перестановок будет равно (n–1)!. Этот алгоритм почти всегда дает точное решение задачи коммивояжера, однако продолжительность таких вычислений может занять непозволительно много времени. Известно, что при значениях n > 12, современный компьютер не смог бы решить задачу коммивояжера даже за все время существования вселенной.
Как уже упоминалось, существуют и другие алгоритмы для решения задачи коммивояжера, которые значительно точнее жадного алгоритма и значительно быстрее метода полного перебора. Однако дисциплина называется «Программирование и основы алгоритмизации», из чего следует, что на первом месте у нас все-таки программирование, а уж потом можно и с алгоритмами разбираться. Поэтому в данной курсовой работе другие алгоритмы не рассматриваются в виду относительной сложности. Да и пора бы нам уже написать какую-нибудь программу в любимой нами Delphi.Муравьиный алгоритм.
http://ru.wikipedia.org/wiki/Муравьиный_алгоритм
http://en.wikipedia.org/wiki/Ant_colony_optimization
http://www.masters.donntu.edu.ua/2011/fknt/semenuta/library/article3.htm
http://ru.convdocs.org/docs/index-105814.html
http://www.masters.donntu.edu.ua/2011/fknt/murzin/library/docs/3.htm
Код: Выделить всё
Муравей - это программный агент, который является членом большой колонии. Муравей снабжается набором простых правил, которые позволяют ему выбирать путь в графе. Он поддерживает список узлов, которые он уже посетил. Таким образом, муравей должен проходить через каждый узел только один раз. Путь между двумя узлами графа, по которому муравей посетил каждый узел только один раз, называется путем Гамильтона.
Узлы в списке "текущего путешествия" располагаются в том порядке, в котором муравей посещал их. Позже список используется для определения протяженности пути между узлами. Настоящий муравей во время перемещения по пути будет оставлять за собой феромоны. В алгоритме муравья агент оставляет феромоны на ребрах графа после завершения путешествия.
Метод роя пчёл
http://en.wikipedia.org/wiki/Bees_algorithm
http://habrahabr.ru/post/104055/
http://uef.me/content/алгоритм-пчёл
http://msdn.microsoft.com/ru-ru/magazine/gg983491.aspx
Код: Выделить всё
Для рассмотрения принципов работы алгоритма поведения роя пчёл, или метода роя пчёл (МРП) прибегнем к аналогии с реальным роем пчел. Представим себе рой пчел на поле. Их цель – найти на поле область с наивысшей плотностью цветов. Без какого-либо представления о поле априори, пчелы начинают поиск цветов со случайных позиций со случайными векторами скорости. Каждая пчела может помнить позиции, где она нашла наибольшее количество цветов и каким-то образом знать области, где другие пчелы обнаружили наибольшую плотность цветов. Выбирая между возвращением к месту, где пчела сама обнаружила наибольшее количество цветов, или исследованием места, определенного другими, как место с наибольшим количеством цветов, пчела устремляется в направлении между двумя точками в зависимости от того, что окажет большее влияние на ее решение – персональное воспоминание или социальный рефлекс. По пути пчела может найти место с более высокой концентрацией цветов, чем было найдено ранее. В дальнейшем оно может быть обозначено как новое место с наибольшей концентрацией цветов, а также как место наибольшего скопления цветов, найденное всем роем. Случайно пчела может пролететь мимо места, с большим количеством цветов, чем было найдено любой другой пчелой роя. Весь рой, затем будет стремиться навстречу этому месту в дополнении к собственным наблюдениям каждой пчелы. Таким образом, пчелы исследуют поле: перелетая места с наибольшей концентрацией, они замедляются в их направлении. Непрерывно они проверяют места, которые пролетели, сравнивая с найденными ранее местами с наибольшей концентрацией цветов надеясь найти абсолютную наибольшую концентрацию цветов. В конечном итоге, пчела заканчивает движение на месте поля с наибольшей концентрацией цветов. Вскоре весь рой сосредотачивается в окрестностях этой позиции. Не имея возможности обнаружить места с большей концентрацией цветов, пчелы непрерывно роятся в районе наибольшей плотности цветов. Это поведение пчёл и было положено в основу этого метода оптимизации.
Язык метода
Частица или Агент – каждая пчела в рое рассматривается как частица или агент. Все частицы роя действуют индивидуально в соответствии с одним управляющим принципом: ускоряться в направлении наилучшей персональной и наилучшей общей позиции, постоянно проверяя значение текущей позиции.
Позиция – аналогично местоположению пчелы на поле представляется координатами на плоскости x-y. Однако, в общем случае можно расширить эту идею в любое N-мерное пространство в соответствии с поставленной задачей. Это N-мерное пространство является областью решений для оптимизируемой задачи, где каждый набор координат представляет решение.
Пригодность — по аналогии с примером пчелиного роя функция пригодности будет плотностью цветов: чем больше плотность, тем лучше позиция. Функция пригодности служит средством связи между физической проблемой и алгоритмом оптимизации.
Персональная наилучшая позиция – по аналогии с пчелиным роем, каждая пчела помнит позицию, где она сама обнаружила наибольшее количество цветов. Эта позиция с наибольшим значением пригодности обнаруженная пчелой известна как персональная наилучшая позиция (ПНП). Каждая пчела имеет собственное ПНП, определяемое путем, который она пролетела. В каждой точке вдоль пути движения пчела сравнивает значение пригодности текущей позиции со значением ПНП. Если текущая позиция имеет значение пригодности выше, значение ПНП заменяется на значение текущей позиции.
Глобальная наилучшая позиция – каждая пчела также каким-то образом узнает область наибольшей концентрации цветов, определенную всем роем. Эта позиция наибольшей пригодности известна как глобальная наилучшая позиция (ГНП). Для всего роя это одна ГНП, к которой стремится каждая пчела. В каждой точке на протяжении всего пути каждая пчела сравнивает пригодность ее текущей позиции с ГНП. В случае если какая-либо пчела обнаружит позицию с более высокой пригодностью, ГНП заменяется текущей позицией этой пчелы.
Алгоритм
Первым шагом в реализации МРП является выбор параметров, которые необходимо оптимизировать, и определение допустимого интервала для поиска оптимальных значений. Затем в допустимой области случайным образом располагаются пчёл, а также задаются векторы и скорости их движения. Затем каждая частица должна перемещаться через пространство решений, как если бы она была пчелой в рое. Алгоритм действует на каждую частицу отдельно, перемещая ее на небольшую величину, циклично двигая ее через весь рой. Следующие шаги выполняются для каждой частицы:
Оценка пригодности для частицы, сравнение с ПНП и ГНП. Функция пригодности, используя координаты частицы в пространстве решений, возвращает значение пригодности для текущей позиции. Если это значение больше, чем значение ПНП, соответствующее этой частице, или ГНП, тогда соответствующие позиции заменяются текущей позицией.
Корректировка скорости частицы. Манипуляции со скоростью частицы являются основным элементом всей оптимизации. Точное понимание уравнения, используемого для определения скорости, является ключом к пониманию всего процесса оптимизации. Скорость частицы меняется в соответствии с взаимным расположением позиций ПНП и ГНП. Она стремится в направлении этих позиций наибольшей пригодности в соответствии со следующим уравнением
где:
— это скорость частицы в n-том измерении на предыдущем шаге,
— это координата частицы в n-том измерении,
— ПНП,
— ГНП.
Расчет производится для каждого из N. Из этого уравнения видно, что новая скорость получается из старой скорости путем простого масштабирования на , и прибавления направления ГНП и ПНП для этого конкретного направления. и — это масштабные коэффициенты, которые определяют относительное взаимное «притяжение» к ПНП и ГНП. Они иногда рассматриваются как познавательный и социальный факторы. — это коэффициент, определяющий какое влияние на частицу оказывает ее память о ПНП, и — коэффициент, определяющий какое влияние на частицу оказывают остальные члены роя. Увеличение предполагает исследование пространства решений путем движения каждой частицы в направлении своего ПНП; увеличение предполагает исследование предполагаемого глобального максимума. Функция случайных чисел rand() возвращает число в интервале между -1 и 1. В общем случае два появления функции rand() представляет собой два различных вызова функции. Большинство реализаций используют две независимые случайные величины для стохастического изменения относительного притяжения ГНП и ПНП. Это введение случайного элемента в оптимизацию предназначено для моделирования незначительного непредсказуемого компонента реального поведения роя. называют «инерционным весом» и это число (выбранное в интервале между 0 и 1) отражает в какой мере частица остается верной своему первоначальному курсу, не подвергшемуся влиянию ГНП и ПНП.
Граничные условия
Границы мы задали изначально, но нигде в формулах и методах о них не упоминалось. Так как же всётаки их учитывать? Существует несколько ответов на этот вопрос.
Например, можно сделать стены поглощающими. Когда частица ударяется об границу пространства решений в одном из измерений, скорость в этом измерении обнуляется, и частица в конечном итоге будет возвращена в заданное пространство решений. Это означает, что границы — «стены» поглощают энергию частиц, пытающихся разрешённую область. Или же отражать скорость частицы, когда та подлетает к «стене». Но самым эффективным решением оказались «невидимые стены». Частица может спокойно вылетать за их пределы, но находясь вне разрешённой области, значения, полученые ею значения просто не учитываются, до тех пор, пока она не вернётся обратно.
Заключение
В итоге хочу заметить, что метод роя пчёл можно эффективно распределить на несколько паралельных процессов, за счёт чего значительно увеличится его скорость.
По сравнению с генетическим алгоритмом, операторы которого могут быть реализованы различным образом, имеет лишь один оператор — вычисление скорости, что делает его более простым в использовании.
В методе роя пчёл можно легко определить достижение точки глобального минимума, в то время как в генетических алгоритмах это значительно осложнено.
Концепция этих методов основывается на двух совершенно разных природных процессах: МРП основывается на социальном поведении роя, а генетический алгоритм имитирует процесс эволюции и естественного отбора. За счёт этого есть возможность объединить два этих метода.Про все сразу
http://www.masters.donntu.edu.ua/2013/fknt/dobrov/library/article9.htm
Добавлено спустя 12 часов 48 минут 49 секунд:
пчелный
http://dis.podelise.ru/text/index-33831.html?page=23
