Алгоритм муравья

реферат

3. Муравей

Муравей - это программный агент, который является членом большой колонии и используется для решения какой-либо проблемы. Муравей снабжается набором простых правил, которые позволяют ему выбирать путь в графе. Он поддерживает список узлов, которые он уже посетил. Таким образом, муравей должен проходить через каждый узел только один раз. Путь между двумя узлами графа, по которому муравей посетил каждый узел только один раз, называется путем Гамильтона, по имени математика сэра Уильяма Гамильтона.

Узлы в списке "текущего путешествия" располагаются в том порядке, в котором муравей посещал их. Позже список используется для определения протяженности пути между узлами. Настоящий муравей во время перемещения по пути будет оставлять за собой феромоны. В алгоритме муравья агент оставляет феромоны на ребрах графа после завершения путешествия.

Стартовая точка, куда помещается муравей, зависит от ограничений, накладываемых условиями задачи, так как для каждой задачи способ размещения муравьев является определяющим. Либо все они помещаются в одну точку, либо в разные с повторениями, либо без повторений.

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

Делись добром ;)