Валеева Аида Фаритовна. Лекции по комбинаторной оптимизации - файл n2.rtf

Валеева Аида Фаритовна. Лекции по комбинаторной оптимизации
скачать (7855.7 kb.)
Доступные файлы (5):
n1.exe
n2.rtf72042kb.28.10.2009 16:52скачать
n3.pdf115kb.10.11.2009 22:30скачать
n4.doc2803kb.04.10.2010 13:35скачать
n5.doc9504kb.11.11.2009 01:03скачать

n2.rtf








Общая схема конструктивной эвристики
S – множество допустимых решений задачи комбинаторной оптимизации , –целевая функция, которая должна быть минимизирована (максимизирована).

Общая схема
1. Упорядочить компоненты решения ki

2. Положить s=Ж (s S) и i=1

3. Повторять

Если sU{ki} допустимое частично построенное решение,

то s= sU{ki}

i=i+1

пока s S.

Характеристики элементов алгоритма муравьиной колонии


Элемент алгоритма

Описание элемента алгоритма

Компонент (фрагмент)

Составной элемент решения задачи

Агент

Рандомизированный жадный алгоритм, который итеративно строит из множества компонент допустимое решение задачи

Эвристическая информация

Число, не зависящее от решений, найденных на предыдущих итерациях, отражает желательность принятия той или иной компоненты решения

Уровень феромона

Положительное число, показывающее, насколько часто агентами использовались компоненты решения на предыдущих итерациях алгоритма


Модель, описывающая «движение» агентов

V, i=1,…,n, – вершины, соответствуют компонентам решения;

E, j=1,…,n – ребра, соответствуют связям между компонентами решениями.

  1. уровнем феромона (или для связей между вершинами i и j);

  2. эвристической информацией (или ).

Эти характеристики необходимы агентам для выбора с некоторой вероятностью направления движения по графу G.

  1. привлекательности перехода (эвристической информации) из вершины в ;

  2. уровня феромона перехода из вершины в .


Алгоритм Ant System (AS)

Общая схема алгоритма AS

Инициализация_уровня феромона;

Пока не достигнуты условия остановки

выполнить

для всех агентов выполнить

Построить_Решение( );

Конец_для;

Модифицировать_феромон;

Конец_пока;

Конец алгоритма АS.
Применялся для решения задачи коммивояжера и квадратичной задачи о назначениях.


А – множество из искусственных агентов;

– решение, построенное агентом ;

Построить_Решение( ):

  1. ?, ? – параметры алгоритма (важность феромона и эвристической информации соответственно);

  2. – множество компонент решения, которые должны быть добавлены агентом к частично построенному решению ,

– последняя компонента решения;

  1. Выбор компоненты для добавления в решение осуществляется по следующему вероятностному правилу:

,


Алгоритм Ant System (AS)

Общая схема алгоритма AS

Инициализация_уровня феромона;

Пока не достигнуты условия остановки

выполнить

для всех агентов выполнить

Построить_Решение( );

Конец_для;

Модифицировать_феромон;

Конец_пока;

Конец алгоритма АS.
Применялся для решения задачи коммивояжера и квадратичной задачи о назначениях.


А – множество состоит из искусственных агентов;

– решение, построенное агентом ;

Модифицировать_феромон:

  1. Применяется правило «изменение феромона с задержкой»:

(),

где

если компонента была использована в решении ,

  1. – значение целевой функции,

, - параметры, , ;
Введение данного правила способствовало тому, что значение феромона увеличивалось на компонентах лучших решений, при этом на компонентах решений худшего качества его значение уменьшалось.


Модификации алгоритма AS:

(отличаются правилами определения феромона).

Выводы:

  1. с помощью алгоритма Ant-Cycle получены лучшие решения по сравнению с алгоритмами Ant-Density, Ant-Quantity.

  2. правило определения феромона в алгоритме Ant-Cycle стало применяться в и других версиях алгоритмов AC.

  3. в алгоритмах Ant-Density, Ant-Quantity и Ant-Cycle были определены наилучшие значения управляющих параметров a, b алгоритмов.

  4. Ant-Cycle по сравнению с другими эвристиками находил лучшие решения на задачах небольшой размерности и плохо работал на больших задачах.

Значения управляющих параметров алгоритмов AS

Алгоритмы AS

a

b

Ant-Density

1

5-10

Ant-Quantity

0,5-1

5-20

Ant-Cycle

1

2-5


Алгоритм Ant Colony Optimization (АСО)


Общая схема алгоритма АСО

Инициализация феромона;

Повторять

Для всех агентов выполнить

Построить_Решение()

КонецДля

Для всех значений феромона выполнить

Испарение_Феромона()

КонецДля

Для всех значений феромона, соответствующих хорошим решениям, выполнить

Увеличение _Феромона()

КонецДля

До тех пор, пока не достигнуты условия остановки


  1. Построить_Решение() подобна процедуре в AS

  2. Испарение_Феромона() моделирует процесс испарения феромона (интенсивность феромона на компонентах решения уменьшается).

  3. Увеличение_Феромона():

количество феромона добавляется на компоненты только хороших решений.




Алгоритм Ant Colony System (АСS)
1. Новое правило моделирует локальное (пошаговое) испарение феромона на компонентах решения:

(),

где x – это параметр, задаваемый при инициализации алгоритма,

(1-x) –локальное испарение феромона на компоненте (на парах компонент), xО(0,1);

>0 – наименьший возможный уровень феромона, задаваемый при инициализации алгоритма.

2. Феромон наносится на пары компонент (на компоненты) лучших решений итерации:

(),

где

- значение целевой функции лучшего решения итерации;

r – параметр, задаваемый при инициализации алгоритма, величина (1-r) представляет собой испарение феромона на компоненте (на парах компонент) в конце итерации, rО(0,1).


Алгоритм Ant Colony System (АСS)
3. Применяется псевдо-случайно–пропорциональное правило при выборе компонента для добавления его в частично построенное решение. По этому правилу некоторые компоненты решения выбираются детерминировано («жадным» образом), другие - с некоторой вероятностью.

Пусть - равномерно распределенная случайная величина.

,

где - выражение для общей оценки компонент решения.

.

Выводы: Алгоритм ACS был протестирован на задачах большой размерности (решалась задача коммивояжера) и проводилось его сравнение с другими метаэвристиками. Во всех случаях ACS показал лучшие результаты.


Алгоритм Max-Min Ant System (MMAS)
Алгоритм MMAS является модификацией алгоритма Ant System (AS):

(),


Алгоритм муравьиной колонии, основанный на популяции (P-ACO)!
1. Модификация алгоритма АСО

2. В основу P-ACO была положена идея генетического алгоритма (GA), а именно: происходит построение популяции решений, которая передается от одной итерации в другую вместо информации о феромоне:



Стратегии для обновления популяции
1. Стратегия Age. Из популяции удаляется самое старое решение, и вместо него вводится новое лучшее решение.

2. Стратегия Quality. Из популяции, состоящей из объединения k решений и решения , полученного на k+1–ой итерации, удаляется худшее решение.

3. Стратегия Prob. Из популяции предлагается удалять решение с некоторой вероятностью pi.

4. Стратегия Age&Prob. Эта стратегия объединяет две вышеперечисленные - Age и Prob. При этом в новую популяцию всегда включается самое лучшее решение итерации, а удаляется решение из популяции так, как в стратегии Prob.

5. Стратегия Elitism. Водится понятие «элитного» решения, т.е. решения являющееся лучшим решением в популяции. При этом обновление решений касается всех решений популяций, кроме «элитного».


Изменения феромона в алгоритме P-ACO

1.Феромон изменяется только для решений популяции следующим образом:

,



2. Приращение определяется:



где k– размер популяции; – начальное значение феромона, – максимальное значение феромона.
Алгоритм ACP-DSR для задачи упаковки прямоугольников

Дано: прямоугольная полоса шириной W=5, прямоугольники заданных размеров (табл. 1)

Таблица 1 – Размеры исходных прямоугольников


i

1

2

3

4

5

6

7

wi

2

1

3

4

3

2

1

li

5

5

3

2

2

2

1

Таблица 2 – Кортежи, полученные алгоритмом DSR



Результаты работы предлагаемого алгоритма ACP-DSR





Упаковка прямоугольников и кругов



Элементы алгоритма
Фрагмент: окружность/ прямоугольник;
Эвристическая информация: площадь фигуры.

Параметры:

k размер популяции;

m количество агентов;

?, ? константы;

, – значения феромона;

x,rкоэффициенты испарения феромона
Входные данные:

W - ширина полосы;

n - количество прямоугольников;

m- количество окружностей;

wj, lj - ширина и длина прямоугольников соответственно;

ri- радиус окружности,

i = 1,…,m, j=1,..,.n


АГЕНТ№2

АГЕНТ№1

L = 70

КРА =81,36% 81,36%

ПРИМЕР РАБОТЫ АЛГОРИТМА

Параметры алгоритма: число агентов m =2;?=0,1; ?=1,2; ?=0,9; W=80

L=87, 32

КРА =65,22% 655565,22%65,22%65,22%65,22%





ЧИСЛЕННЫЙ ЭКСПЕРИМЕНТ

Для анализа алгоритма был проведен численный эксперимент на тестовых наборах:

Тестовые наборы были взяты с http://people.brunel.ac.uk/~mastjjb/jeb/info.html.

лучшие результаты были получены при ? = 1,8; ? = 0,9. Количество фигур n = 850; количество агентов m = 5; количество итераций t = 200 (время работы 80 мин.)


Задача о коммивояжере (TSP)




Применение алгоритма P-ACO к задаче о коммивояжере (TSP)

P:=

Инициализация значений феромона

Повторять

Для каждого муравья {построение решения}

S:=[1,…,n] {множество заданных городов}

Выбрать города i с вероятностью p0j

Для i:=1 to n выполнить

Выбрать город j с вероятностью pij

S:=S-{j}

i:=j

КонецДля

КонецДля

Если |P|=k, то удалить самое «старое» решение из популяции:

P:=P

Определить самое лучшее решение итерации и добавить

его в популяцию:

P:=P+?*

Вычислить новую матрицу феромона из P

До тех пор, пока не выполнено условие останова


  • Дана матрица (dij) попарных расстояний между городами, 1 Ј i, j Ј n; решение – (перестановка чисел)

  • Эвристическая информация:

  • Популяция P =[pij] – матрица размерности

n x k, содержит k лучших решений; каждый столбец P содержит одно решение.

  • Обновление матрицы популяций происходит с помощью применения различных стратегий (Age, Prob, Quality, Age&Prob, Elitism).

  • Длина пути для решения: =. Самое лучшее решение – наименьшее значение.

  • В матрице феромона размерности n x n при инициализации все диагональные элементы приравниваются к 0.


Обновление матрицы феромона для TSP






.
Значение выбирается произвольным образом.
Должно выполняться условие: сумма по столбцу или строке в матрице феромона должна равняться 1, т.е. .




0



Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации