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

реферат

1. Идея алгоритма

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

Рис. 1.

При прочих равных каждый муравей выберет свой путь. Первый муравей выбирает верхний путь, а второй - нижний. Так как нижний путь в два раза короче верхнего, второй муравей достигнет цели за время t1. Первый муравей в этот момент пройдет только половину пути (рис. 2).

Когда один муравей достигает пищи, он берет один из объектов и возвращается к муравейнику по тому же пути. За время t2 второй муравей вернулся в муравейник с пищей, а первый муравей достиг пищи (рис. 3).

При перемещении каждого муравья на пути остается немного феромона. Для первого муравья за время t0t2 путь был покрыт феромонами только один раз. В то же самое время второй муравей покрыл путь феромонами дважды. За время t4 первый муравей вернулся в муравейник, а второй муравей уже успел еще раз сходить к еде и вернуться. При этом концентрация феромона на нижнем пути будет в два раза выше, чем на верхнем. Поэтому первый муравей в следующий раз выберет нижний путь, поскольку там концентрация феромона выше.

Рис. 2. Рис. 3.

В этом и состоит базовая идея алгоритма муравья - оптимизация путем непрямой связи между автономными агентами.

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