Динамична оптимизация по метода на мравките


Категория на документа: Други


- Трудност да се очаква решение на проблема с нарастването на производителността,
- Проблем формулиране, и проблем конвергенция,
- Необходимостта от използването на голям брой агенти, което предизвиква рискове от конфликти,
- Възможни колебания или блокиране на поведение,
- Не умишлено местно сътрудничество, което означава, че няма доброволна кооперация (в случай на поява).

Един от най-големите предимства на алгоритми, вдъхновени от природата, като мравчената колония, е гъвкавост в динамичните среди.

3. Техники, насочени към динамичната оптимизация.

Еволюционните алгоритми се прилагат до голяма степен при динамични пейзажи, в конкретни случаи. Класификацията на динамичните методи намерени в
литературата са:

1. Реактивните методи (Grefenstette & Ramsey (1992), Тинос & де Карвальо (2004)),
които реагират на промени (т.е. чрез задействане на разнообразието). Основната идея на тези методи е да се направи външно действие, когато настъпи промяна. Целта на това действие е да се увеличи разнообразието. Като цяло реактивните методи, основаващи се на популации, губят своето разнообразие, когато решението стигне близо до оптимум-а. Чрез увеличаване на разнообразието, процеса на търсене може да се регенерира.

2. Методите, които поддържат разнообразието (Cobb & Grefenstette (1993), Nanayakkara и др. (1999)). Тези методи запазват многообразието на населението, с надеждата, че когато обективната функция се промени, разпределят се средства в рамките на пространството на търсените разрешения, за да се намери бързо новият оптимум (Garrett & Walker (2002) и Сим ~ OES & Costa (2001)).

3. Методите, които пазят в паметта си "старите" оптимуми. Тези методи пазят в паметта си еволюцията на различни оптимуми, за да ги използват по-късно. Тези методи са особено ефективни, когато еволюцията е периодична (Bendtsen & Krink (2002), Trojanowski & Michalewicz(2000) и Bendtsen (2001)).

4. Методите, които използват група от под-популации, разпределени на различни оптимуми (Oppacher и Wineberg (1999), и Cedeno Vemuri (1997) и Ursem (2000)), като по този начин се увеличава вероятността да се намери нова Optima.

Michael Guntsch и Martin Middendorf решени в Guntsch & Middendorf (2002). Това са два
динамично дискретни комбинаторни проблема, проблем на динамичния пътуващ търговец(TSP), и проблема на динамичната квадратна задача,решени с алгоритъм модифициран на метода на мравка колония. Основната идея се състои в прехвърлянето на целия набор от решения, открити в една итерация към следващата, след това се изчислява количеството феромони необходимо за следващата итерация.
Същите автори предлагат в Guntsch и Мидендорф (по-късно през 2002) промяна на начина, по които феромоните се обновява, за да се позволи следенето на добрите решения до определен срок, след което изрично да се премахне влиянието им от матрицата на феромоните. Методът е тестван на динамичен TSP. Guntsch и Middendorf разработват три стратегии; Първата стратегия позволява повторна инициализация на една и съща стойност на феромон матрица, когато засече промяна. Вторият подход се състои в изчисляване на стойността на матрицата в зависимост от разстоянието между градовете (този метод се прилага към динамичния TSP, където един град може да бъде отстранен или добавян). Третият подход използва стойността на феромон при всеки град.

Последните три стратегии бяха променени, чрез въвеждане на една елитарна
концепция: на най-добрите мравките е позволено да променят феромона при всяка итерация, и когато е открита промяна. Предишните добри решения не са забравени, но са модифицирани по най-добрия възможен начин, така че те могат да станат нови разумни решения.

4. От природата до дискретна оптимизация.

Изкуствени мравки, идващи от гнездото преминават през различни пътеки, докато се посетят всички пътища (фигура 1). Първоначално феромоните имат еднаква стойност. Когато се завърнат от източника на храна, мравките 'складират' феромон. Стойностите на феромоните се обновяват по следното уравнение:

Като Q е константа, а L(i) дължината на пътя, което означава, че новата стойност е феромон обратно пропорционален на дължината на пътя. Една траектория от гнездото до източника на храна

Процесът от фигура 3 е цялостно изградено решение. Процесът е повтарящ се. Изборът на път се извършва според вероятностната формула:

Нека разгледаме примерът на фигура 3; мравката ще избере своя път според три вероятности:

Ако предположим, че l1 < l2 < L3, тогава τ1 > τ2 > τ3, което предполага, че PE1> рЕ2> PE3. Избраният път ще бъде e1. За да се предотврати стойността на феромона от безкрайно увеличаване и да се намали значението на някои решения, стойностите на феромоните са намалени с течение на времето според следното уравнение:

където ρ е параметъра регулиращ феромона; този параметър ще отрази скоростта на приближаване към едно единствено решение.

Алгоритмите на мравчените колонии първоначално бяха посветени на отделни проблеми (броят на променливите е ограничен), в този случай можем да определим набор от решени компоненти; оптималното решение за даден проблем, ще бъде организиран набор от тези компоненти. Разглеждайки проблемът на пътуващия търговец "TSP": продавачът трябва да посети всички градове N и не трябва да посетите град повече от един път, като целта е да се намери най-краткия път. На практика, TSP може да бъде представен от свързания граф (граф, където са свързани възли). Възлите представляват градовете N с I = {1, ..., N} и М - общия брой възли. A пътят между двата възела (т.е. Ni и Nj) е обозначен с eij. Така конструкцията на решението се състои в избора на изходния възел (град), добавяне към настоящото частично решение нов възел в съответствие с определена вероятност и повтаряне на
процес, докато броят на компонентите е равн на N. В отделни проблеми, решенията не са известни предварително, което означава, че феромоните не могат да бъдат приписани на цялостно решение, а на отделни компоненти на решението.

5 Cando: Таксуване на мравки за продължително динамична оптимизация

За проблеми с дискретни променливи, проблемните компоненти са ограничени, следователно стойностите на феромона могат да бъдат отнесени директно към компонентите на решението. Съществува проблем при детерминираното решение на дискретите, дори тяхното търсене може да бъде време емко за изчислението. Но за продължителните проблеми, феромонни стойности не могат да бъдат отнесени директно към компонентите на решението. Подходът, който ние използваме е диверсификационна техника, която се състои в предоставянето на електростатичен заряд на всяка,

където Qi и Q 'са първоначалните заряди на мравките i и l съответно, | Xi - Xl | е евклидовото разстояние, Rp и Rc са "възприятие" и "ядро".



Сподели линка с приятел:





Яндекс.Метрика
Динамична оптимизация по метода на мравките 9 out of 10 based on 2 ratings. 2 user reviews.