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


 

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

41801. Архивация данных 650.56 KB
  Запустите архиватор RR.Создайте распределенный архив выделенных файлов.Просмотрите содержимое одного их созданных архивов.
41802. Вычисляемые поля в запросах СУБД MS Access 85.01 KB
  Изучение основных принципов создания и использования сложных запросов в СУБД MS Access. Изучение запросов на выборку данных из нескольких таблиц при помощи языка без данных SQL. Изучение запросов с вычисляемыми полями на выборку данных. Применение итоговых функций в запросах[Код заказа]=Клиенты.[Код заказа] INNER JOIN Товары INNER JOIN Поставщики ON Товары.[Код товара]=Поставщики.[Код товара]=Товары.
41803. Adobe Photoshop: Анимация 583.59 KB
  Поэтому прежде чем приступить к анимации вам необходимо вызвать палитру Слои. задайте инструменту этот размер в панели опций инструмента рис.1 Рис. Сделайте дубликат слоя и дайте команду Фильтр Пластика и в панели инструментов выберите инструмент Вздутие рис.
41804. Проверка выполнения внутренних соединений обмоток электрических машин 53.42 KB
  Укладку в пазы секций обмоток и соединение их а также изоляцию соединений производят по инструкции предприятия изготовителя. Проверку выполнения внутренних соединений обмоток приходится производить в следующих случаях: после капитального ремонта электрических машин если по каким-либо причинам отсутствует или перепутана маркировка выводов а также когда нарушен нормальный режим работы машины выявленный при пуске и испытаниях. Проверка правильно выполненных внутренних соединений обмоток и выводов машин Постоянного тока производится указанными...
41805. Настройка зубодолбёжного станка 5А12 на нарезание зубчатого колеса 531.85 KB
  Зацепление сопровождается следующими рабочими движениями: Возвратнопоступательных движением долбяка главное движение осуществляющим процесс резания. Вращением долбяка являющимся круговым движением подачи. Вращением заготовки согласованным с вращением долбяка движение обкатки. Радикальным врезанием долбяка в заготовку на полную высоту зуба если колесо обрабатывается за один проход или на часть высоты если колесо обрабатывается в несколько проходов.
41806. Система питания бензинового двигателя 231.95 KB
  Система питания автомобилей ВАЗ-21213 включает приборы подачи топлива и воздуха, приготовления горючей смеси и выпуска отработавших газов. Система питания состоит из топливного бака 34, топливного насоса 27, топливопроводов, воздушного фильтра, карбюратора 26, глушителей и трубопроводов. Система с обратным сливом части топлива от карбюратора 26 через калиброванное отверстие патрубка карбюратора в топливный бак. Ось рычага механической подкачки топлива; 2. Рычаг механической подкачки топлива; 3. Рычаг ручной подкачки топлива; 15. Фильтр тонкой очистки топлива; 29.
41808. Статистические функции MS Excel 2010. Построение рядов данных 495.52 KB
  Формат записи функции: МИН число1; число2; Количество допустимых аргументов среди которых находится минимальное значение равно 255. Формат записи функции: МАКС число1; число2; Количество допустимых аргументов среди которых находится максимальное значение равно 255. Формат записи функции: СРЗНАЧчисло1; число2; Количество допустимых аргументов среди которых находится среднее значение равно 255. Формат записи функции: СЧЕТчисло1; число2; Количество допустимых аргументов среди которых находится среднее значение равно 255.