2580

Муравьиные системы: Оптимизация при помощи колонии взаимодействуюих агентов.

Реферат

Информатика, кибернетика и программирование

Муравьиные системы: Оптимизация при помощи колонии взаимодействующих агентов Marco Dorigo, Member, IEEE,Vittorio Maniezzo and Alberto Colorni Введение В этой статье описан новый эвристический алгоритм общего назначения, который может быть использован...

Русский

2012-10-22

106 KB

4 чел.

Муравьиные системы: Оптимизация при помощи колонии взаимодействуюих агентов

Marco Dorigo, Member, IEEE,Vittorio Maniezzo and Alberto Colorni

Введение

В этой статье описан новый эвристический алгоритм общего назначения, который может быть использован для решения различных комбинаторно-оптимизационных проблем. Этот алгоритм имеет несколько превосходных характеристик.

  Многогранность - может применяться для похожих интерпретаций одной и той же проблемы. К примеру, может применяться для решения прямой (симметричной) задачи коммивояжера(TSP), так и для решения ассиметричной задачи(ATSP).

  Устойчивость - может применяться с минимальными изменениями для других комбинаторно-оптимизационных проблем, таких как квадратичная задача о назначениях (QAP) и задача календарного планирования (JSP).

  Близость к алгоритмам основанных на популяциях - позволяет использовать положительные обратные связи, как механизм поиска, что будет описано в дальнейшем. Также делает систему податливой для параллельного внедрения.

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

Рассмотрим пример, показанный на рис.1. Здесь изображен путь, по которому прогуливаются муравьи (например от источника пищи А к гнезду Е, и наоборот рис 1а). Внезапно препятствие появляется и преграждает путь. Таким образом, в месте В муравьи, идущие от А к Е (или в месте D от Е к А) должны решить повернуть направо или налево рис.1b. На выбор влияет интенсивность феромонового следа, оставленного предшествующими муравьями. Поэтому большее количество феромона справа, стимулирует муравьев поворачивать направо. Первый муравей, достигший точки B (или D) с равной вероятность может повернуть как направо, так и налево (т.к. на альтернативных путях еще нет феромона). В следствие того, что путь BCD короче чем BHD, первый муравей идущий этим путем достигнет точки D быстрее муравья, шедшего путем BHD (рис. 1c). Таким образом, муравей возвращающийся из Е в D найдет более сильным след на пути DCB, появившийся из-за того, что половина муравьев решила обойти препятствие путем DCBA и некоторые достигли цели через BCD: в дальнейшем вероятно они предпочтут путь DCB пути DHB. Как следствие, количество муравьев последовавших путем BCD за единицу времени будет больше, чем количество на пути BHD. Это приводит к тому, что отложение феромона на коротком пути происходит быстрее, чем на длинном и вероятность выбора короткого пути муравьем также возрастает. В результате вскоре все муравьи выбирают короткий путь.


Рисунок 1 - Пример с настоящими муравьями

a) Муравьи идут по пути между точками А и Е.
b) Появление препятствия; муравьи с равной вероятностью выбирают один из путей обхода препятствия
c) На коротком пути отложено большее количество феромона

Тем не менее, мы полагаем, что пример с муравьями может быть полезен для объяснения нашей модели. Рассмотрим граф на рисунке 2а, который является возможной интерпретацией с помощью муравьиной системы ситуации на рисунке 1b.

Предположим, что расстояние между D и H, между B и H, и между B и D- через C-равны 1, и пусть C располагается на полпути между D и B (смотри рис 2a. Теперь рассмотрим, что будет проистходить в интервалы времени t=0, 1, 2.

Предполагается, что 30 новых муравьев идут в точку В из точки А, и 30 в D из E в каждый момент времени, который каждый муравей проходит со скоростью 1 за каждый момент времени. Пока муравей идет, он откладывает в момент времени t феромон с интенсивностью 1, и , чтобы сделать пример проще, испаряется полностью и мгновенно во временной интервал (t+1, t+2). В момент времени t=0 следа еще нет, но 30 муравьев в точке В и 30 в D. Их выбор каким путем пойти полностью случаен. Вследствие этого, в среднем 15 муравьев из каждого узла будут двигаться по направлению к H, и 15 по направлению к C (рис. 2b) В момент времени t=1 30 новых муравьев, которые шли в В из А обнаружат след с интенсивностью 15 на пути, который ведет к Н, оставленный 15 муравьями, которые шли этим путем из точки В, и след с интенсивностью 30 на пути С, полученный как сумма следа отложенного 15 муравьями которые шли из В и 15, которые пришли в В из D через С (рис. 2c)

Этот процесс продолжается пока все муравьи случайным образом выберут короткий путь.

Рисунок 2 - Пример с искусственными муравьями

a) Начальный граф с расстояниями
b) В момент времени t=0 нет никакого следа на ребрах графа; далее муравьи выбирают повернуть налево или направо с равной вероятностью
c) В момент времени t=1 след сильнее на коротком ребре, потому как он был предпочтительней для муравьев

Муравьиная система

В этой части представлена муравьиная система (AS). Было решено использовать известную задачу коммивояжера, чтобы сравнить с другими вероятностными методами.

Дано множество из n городов, задача коммивояжера представляет собой проблему нахождения самого короткого пути, при условии, что каждый город был посещен лишь раз. Обозначим dij - длина пути между городами i и j; в случае эвклидовой задачи коммивояжера dij - эвклидово расстояние между i и j; (т.е. ). В данной задаче дан граф (N,E), где N множество городов и Е множество граней между городами is the (полносвязный граф в эвклидовой задаче коммивояжера).

Пусть количеств муравьев в городе i в момент времени t - общее количество муравьев. Kаждый муравей это простой агент со следующими характеристиками:

  он выбирает город, в который следует с вероятностью, зависящей от удаленности города и количества следа феромона, отложенного на ребре;

  посещенные города становятся недоступными для повторного посещения, пока не закончен маршрут. (Это контролируется при помощи специального списка городов);

  как только маршрут закончен, агент откладывает вещество, называемое следом на каждом посещенном ребре (i,j). Пусть интенсивность следа на ребре (i,j) в момент времени t. Kаждый муравей в момент времени t выбирает следующий город, в котором он будет в момент времени t+1. таким образом, если мы назовем итерацией m передвижений, произведенных m муравьями в интервале времени (t, t+1), тогда каждые n итераций алгоритма (так называемого цикла) каждый муравей закончит маршрут. Таким образом, интенсивность следа обновляется по формуле
(1)
Где это коэффициент такой, что (1 - ) представляет собой испарение следа между временем t и t+n,
(2)
where is the quantity per unit of length of trail substance (pheromone in real ants) laid on количество феромона отложенного на ребре (i,j) k-м муравьем в момент времени t и t+n;
(3)
где Q константа и Lk - это длина маршрута к-ого муравья.

Коэффициент must be set to a value < 1 to avoid unlimited accumulation of trail (see note 1). должен быть установлен в значение <1 для избегания безграничного отложения следа. В нашем эксперименте мы устанавливаем интенсивность отложения следа в момент 0, , как малую положительную константу c.

Чтобы было выполнено условие посещения муравьем n разных городов, к каждому муравью привязывается специальная структура данных, называемая tabu list2. Этот список содержит посещенные города к времени t и запрещает муравьям посещать их снова, пока не пройдено n итераций (т.е не был окончен маршрут). Когда маршрут закончен tabu list используется для определения решения, найденного данным муравьем (т.е расстояния пройденного муравьем), затем список опустошается и муравей может делать выбор снова. Пусть tabuk динамически растущий вектор, связанный со списком k-м муравьем, tabuk - множество полученное из элементов tabuk, и tabuk(s), s-й элемент списка (т.е s-й город, посещенный k-м муравьем в текущем маршруте).

Назовем видимостью количество 1/dij. Это количество неизменно на протяжении всего алгоритма, в отличие от следа, который изменяется в соответствии с формулой (1). Вычислим вероятность перехода из города i в город j k-м муравьем

где allowedk = {N - tabuk}, и - параметры, задающие веса следа феромона.

Алгоритм

1. Инициализация:

Устанавливаем t:=0 {t счетчик времени}

Устанавливаем NC:=0 {NC is the cycles counter}

Для каждого ребра (i,j) устанавливаем начальное значение  ij(t)=c для интенсивности следа и   ij= 0

Размещаем m муравьев в n узлах

2. Set s:=1 {s - индекс tabu list}

For k:=1 to m do

Размещаем стартовый город k-го муравья в tabuk(s)

3. Repeat until tabu list заполнен {этот шаг будет повторяться (n-1) раз}

Устанавливаем s:=s+1

For k:=1 to m do

Выбор города j для дальнейшего движения, с вероятностью pijk (t) по формуле (4)

{в момент времени t  k-й муравей находится в городе i=tabuk(s-1)}

Движение k-го муравья в город j

Добавление города j в tabuk(s)

4. For k:=1 to m do

Перемещаем k-го муравья из tabuk(n) в tabuk(1)

Вычисляем длину маршрута Lk, проденного  k-м муравьем

Обновляем кратчайший найденный путь для каждого ребра (i,j)

For k:=1 to m do

5. Для каждого ребра (i,j) вычисляется  ij(t+n) в соответствии с формулой  

Устанавливаем t:=t+n

   Устанавливаем NC:=NC+1

   Для каждого ребра (i,j) устанавливаем   ij:=0

 

6. If (NC < NCMAX) and (not stagnation behavior)

 Очищаем все tabu lists

 Переход к шагу 2

   else

 Печать самого короткого пути

  Stop


 

А также другие работы, которые могут Вас заинтересовать

59666. Україно, незборима зроду - ти душа великого народу: Сценарій тематичного вечора, присвяченого 10-й річниці прийняття Декларації про державний суверенітет України 38.5 KB
  Прочитаймо давню й сиву Свою долю нещасливу. Кінець вісімдесятих початок дев’яностих років були позначені небувалим піднесенням національновизвольної боротьби. Ведуча 1: Василь Скрипка Незалежність Нарешті дочекалися і ми Своєї незалежної держави.
59667. Ясне-красне Купайло: Фольклорний вечір 46.5 KB
  Ведучий 1: Сьогодні ми хочемо розповісти про надзвичайно поетичне свято Івана Купала яке дійшло до нас ще з поганських часів. Ведучий 2: Купайло свято молодіжне саме звідси єднання молодих сердець на святі і оспівування в піснях хлопця і дівчини попарне стрибання через багаття.
59668. Свято закінчення початкової школи 49.5 KB
  Прийшла така вже пора Але не сумувати тут зібрались А пригадати як все починалось 1 клас Ведучі. Пісня Вчать у школі Ведучі. І виявилось ой нелегко Писати палички й гачки Каліграфія моя Веж мере замучила...
59669. Буду я природі другом 38 KB
  Природа дає все необхідне для життя людей, тварин, рослин — воду і повітря. Природа потребує постійної уваги, турботи. Ми повинні берегти природу, охороняти її багатства.
59670. Ми до тебе, казко, в гості завітали 47 KB
  І знову пісня радісно дзвенить І казка на екрані оживає. Сьогодні ми Казку сюди запросили Щоб бачити Казку слухать гуртом А Казка в завії десь там заблудила. Але Казка до нас прийде тоді коли ми покажемо як добре знаємо казки. Казка виходить на сцену.
59671. Найрозумніший. Конкурс 36 KB
  Хто знає відповідь той піднімає руку. Хто швидше підніме руку той отримує право відповіді. Хто з цих птахів не вміє літати а Кури; б Страуси; в Колібрі; 2. Хто має найдовший дзьоб а Чапля; б Гуска; в Лелека;
59672. Козацькі забави (для дитячого садка) 39 KB
  Дам подумать тільки трошки Звуть його КОТИГОРОШКО Вхід Котигорошка: Гей простелися дорого Біди всі обійди Мене до перемоги Славної доведи Хоч я з виду й невеличкий Але знає кожен: У двобої навіть Змія Я здолати зможу. Котигорошко ніби лякається:...
59673. Сценарій свята останнього дзвоника 42.5 KB
  На сьогоднішньому святі випускники з хвилюванням чекають останнього дзвоника в стінах рідної школи, бо саме сьогодні вони прощаються зі своїми щасливими дитячими шкільними роками.
59674. Посвята в козачата 40 KB
  Зал прикрашений рушниками, калиною, портретами гетьманів. Козаки (старші школярі) збираються на козацьку раду, Кошовий — учень обраний на цю посаду. Іде рада козаків.