Systemy stadne



Pobieranie 21.19 Kb.
Data19.06.2016
Rozmiar21.19 Kb.
PARTICLE SWARM OPTIMISATION

Optymalizacja wielocząsteczkowa

SYSTEMY STADNE
W szeregu problemów optymalizacyjnych wymienianych w przeróżnych dziedzinach nauki, szukanie rozwiązania jest identyfikowane przez odkrywanie/odszukanie globalnego minimizera funkcji celu o wartościach rzeczywistych, , tj. poszukiwaniu takiego punktu , że

gdzie jest niepustym zbiorem.

Optymalizacja wielocząsteczkowa (PSO) należy do szerokiej kategorii Metod Inteligencji Stadnej (zbiorowej) (Kennedy, Eberhart, 2001) dla rozwiązywania problemów optymalizacji globalnej. Początkowo Kennedy zaproponował ją (PSO) jako symulację zachowań zbiorowych i była ona początkowo wprowadzona jako metoda optymalizacyjna w 1995r. PSO jest związana za sztucznym życiem, a szczególnie z teorią roju/stada, ale również z EC (ES i GA).

PSO jest łatwa do zaimplementowania i obliczeniowo niezbyt wymagająca, jako że jej pamięć i prędkość obliczeń z punktu widzenia wymagań są niskie. Co więcej, nie wymaga informacji o kierunku zmian funkcji celu, lecz tylko jej wartości i wykorzystuje bardzo proste operatory matematyczne. Udowodniono, że PSO jest wystarczającą metodą dla wielu problemów optymalizacji globalnej (GO) i w pewnych przypadkach nie wymaga tych skomplikowanych metod modyfikujących rozwiązania, stosowanych przy innych technikach ewolucyjnych (EC) (Kennedy, Eberhart, 1995).



Tło historyczne PSO.
Reguły (w czystej postaci) stosowane przez członków ptasich stad, czy ławic ryb, które umożliwiają im ruch wykorzystywany synchronicznie, bez kolizji, tworzący zadziwiający układ choreograficzny były studiowane i symulowane przez kilku naukowców (Heppnera, Grenandera 1990 i Reynoldsa 1987). W symulacjach poruszanie się ptaków, czy ryb było spowodowane indywidualnymi wynikami w celu osiągnięcia minimalnego odstępu (odległości) od swojego najbliższego (sąsiedniego) indywiduum (Eberhart i inni 1996).

Zachowania zbiorowe zwierząt, jak również w pewnych przypadkach ludzi są zarządzane przez podobne reguły (Wilson, 1975). Jednakże ludzkie zachowania są bardziej złożone niż zachowania stadne. Poza fizycznym ruchem, ludzie dopasowują swoje przekonania, więc ruch ma miejsce w przestrzeni przekonań, chociaż dwie osoby nie mogą zajmować tej samej przestrzeni fizycznej bez kolizji, mogą mieć te same przekonania zajmując bez kolizji to samo stanowisko w przestrzeni przekonań.

Abstrakcyjność społecznego zachowania ludzi jest intrygująca i staje się motywacją do opracowania jego symulacji. Panuje ogólne przekonanie oraz wiele uzasadniających je przykładów z natury potwierdzających pogląd, że społeczne dzielenie się informacją między osobnikami danej społeczności może stanowić wagę ewolucyjną. Hipoteza ta stanowiła podstawę powstania PSO (Eberhart i inni 1996).

Pierwotnym zamierzeniem była graficzna symulacja choreografii grup ptaków lub ławice ryb. Okazało się, że model taki może być również wykorzystany jako model obliczeniowy. Autorami tej stochastycznej techniki optymalizacji bazującej na populacji jest Eberhart i Kennedy. Powstało i rozwijało się kilka wizji symulacji wcielających koncepcje dopasowania przez odległość (Eberhart 1996, K. i E. 1995).

Gdy wcielono to podejście do optymalizacji, opuszczono kilka parametrów, począwszy od śladu (atraktory chemiczne w biomimetyźmie) i procesu błędu skończywszy, dając przez to I wersję uproszczoną PSO (Eberhart, 1996).

PSO przypomina EC w tym, że wykorzystuje się populację składającą się z potencjalnych rozwiązań problemu w celu zbadania przestrzeni przeszukiwań. Jednakże w PSO, każde indywiduum z populacji ma swoją szybkość adaptacyjną (zmianę pozycji) zgodnie z którą porusza się w przestrzeni poszukiwań. Co więcej, każde z indywiduum ma swoją pamięć, pamiętającą swoje najlepsze położenie w przestrzeni przeszukiwań, jakie kiedykolwiek odwiedził (Eberhart i inni 1996). W ten sposób jego ruch/przemieszczanie jest zagregowanym przyspieszeniem wzdłuż/w stosunku do najlepszego odwiedzanego wcześniej miejsca topologicznego sąsiedztwa. Ponieważ termin przyspieszenie było głównie używane w systemach wielocząsteczkowych w fizyce cząsteczek (Reeves, 1983), więc pionierzy tej techniki zdecydowali się używać tej nazwy – ławica/grupa cząstek dla ich algorytmu (Kennedy, Eberhart, 1995).

W tej chwili rozwijane i używane są dwa warianty PSO. Jeden z nich z globalnym sąsiedztwem a drugi z lokalnym.

Zgodnie z wariantem globalnym, każda cząsteczka przemieszcza się według najlepszej, poprzedniej pozycji dla całej ławicy/grupy. Z drugiej strony, zgodnie z wariantem lokalnym, każda cząsteczka przemieszcza się w kierunku poprzedniej najlepszej pozycji i według najlepszej cząsteczki w jego rozważanym sąsiedztwie (Eberhart 1996). W dalszym opisie będziemy analizowali wersję globalną.

Przypuśćmy, że przestrzeń przeszukiwań jest D-wymiarowa, wówczas i-ta cząsteczka stada może być reprezentowana jako D-wymiarowy wektor:

Najlepsza poprzednio odwiedzona pozycja i-tej cząsteczki jest oznaczona jako . Oznaczając indeksem g najlepszą cząsteczkę i niech indeks górny wskazuje na numer iteracji, wówczas całe stado jest sterowane według następujących dwóch równań (Eberhart 1996).

gdzie:

d = 1, 2, …, D,

i = 1, 2, …, N,

N – rozmiar stada,

C – stała dodatnia, zwana stałą przypuszczenia,

r1, r2 – liczby losowe z rozkładu jednorodnego w przedziale [0, 1],

n1, 2, …, - określa numer iteracji.
Równania (2) i (3) definiują wersję inicjalną algorytmu PSO. Ponieważ nie istnieje właściwy mechanizm kontroli szybkości cząsteczki, było koniecznym wskazanie wartości maksymalnej Vmax.

Jeżeli szybkość przekroczy ten próg, wówczas zostaje ustawiona na Vmax. Ten parametr wydaje się być kluczowym, ponieważ duże wartości mogą doprowadzić do tego, że cząsteczki mogą minąć dobre rozwiązania, podczas gdy małe wartości doprowadzają do niewystarczających eksploracji tej przestrzeni przeszukiwań. Brak mechanizmu kontroli szybkości spowodował niską efektywność PSO w porównaniu z technikami EC (Angeline, 1998). Mówiąc dokładniej – PSO lokował obszar optimum szybciej niż techniki EC, ale będąc już w regionie optimum, nie dało się dostosować kroku zmian szybkości tak, aby kontynuować przeszukiwanie drobnoziarniste.

Problem ten skierował uwagę twórców na to, aby wcielić we wzory (2) i (3) parametry wag dla szybkości cząsteczki. W ten sposób w ostatniej wersji PSO równania (2) i (3) zostały zmienione (Eberhart, Ski 1998):


(4)
gdzie:

w – waga inercji,

c1, c2 – stałe dodatnie zwane odpowiednio parametrem poznawczym (kognitywnym) i p. zbiorowym (socjalnym),

χ – współczynnik ścisku, który jest używany zamiennie z w, w celu ograniczenia szybkości.
W lokalnym wariancie PSO, każda cząsteczka przemieszcza się zgodnie z pozycją najlepszej cząsteczki w sąsiedztwie. Np. jeżeli rozmiar sąsiedztwa wynosi 2, wówczas i-ta cząsteczka przemieszcza się według najlepszej cząsteczki w obszarze (i - 1) i (i +1) odpowiednio.

Metoda PSO stosuje się do 5 podstawowych zasad inteligencji zbiorowej, które zdefiniował (Eberhart, 1996, Millanis 1994):




  1. Bliskość – stado działa na prostej strukturze przestrzeni, którą może szybko przeszukiwać,

  2. Jakość – stado powinno mieć możliwość reagowania na jakościowe zmiany współczynników otoczenia/środowiska,

  3. Różnorodność (odpowiedzi) – stado nie powinno dokonywać pewnych ruchów wzdłuż szczególnie wąskich kanałów,

  4. Stabilność – stado nie powinno zmieniać swego zachowania w każdej jednostce czasu, gdy zmienia się środowisko,

  5. Adaptacyjność – stado musi mieć możliwość zmian zachowania, gdy koszt obliczeń tego nie zabrania.



Parametry PSO
Rola wagi inercji w równaniu (4) jest uważana za krytyczną w zachowaniu rozbieżności PSO. Waga inercji wykorzystywana do kontroli wpływu poprzedniej historii szybkości na bieżące wartości. Dokładniej – parametr w reguluje zależność między globalną (szeroko-zakresową) a lokalną (pobliską) zdolnością eksploracji stada. Duża wartość inercji wskazuje na globalna eksplorację (przeszukiwanie nowych obszarów), podczas gdy mała wartość ma tendencję do ułatwiania lokalnej eksploracji tj. dobre dostrajanie bieżącego obszaru przeszukiwania. Właściwa wartość współczynnika wagi inercji w zwykle zabezpiecza balansowanie pomiędzy globalną a lokalną eksploracją i w konsekwencji wpływa na redukcję liczby iteracji wymaganych w celu zlokalizowania optymalnego rozwiązania. Początkowo wartość inercji była stała. Jednakże wyniki eksperymentów wskazują, że jest lepiej wstawić wartość wagi inercji na dużą wartość w celu promowania eksploracji globalnej przestrzeni przeszukiwań i stopniowo należy zmniejszać ją w celu uzyskania doskonalszych rozwiązań (Ski, Eberhart, 1998). W ten sposób inicjalna wartość powinna być ustalona na około 1.2, a następnie stopniowo zmniejszana na ), co powinno być uważane za dobrą.

Parametry c1 i c2 w równaniu (4) nie są tak istotne dla zbieżności PSO. Jednakże właściwe dopasowanie może mieć wpływ na szybszą zbieżność i złagodzenie efektu lokalnych optimów. Rozszerzone studia dotyczące parametru przyspieszenia w I wersji PSO były przeprowadzone przez Kennedy’ego w 1998.

Przy braku jakichkolwiek danych, ustalono c1=c2=2 jako poprawne, ale wyniki eksperymentów wskazują że c1=c2=0,5 mogą dostarczać zdecydowanie lepsze wyniki. Ostatnie prace udowadniają, że może być lepiej, aby wybierać parametr kognitywny o większej wartości, niż parametr socjalny - c2, ale ogólnie c1 + c2 ≤ 4 (Carlisle i Dozier, 2001).

Parametry r1 i r2 są używane w celu utrzymania różnorodności populacji i są one zmiennymi losowymi rozkładu jednorodnego z przedziału [0, 1].

Współczynnik ścisku χ kontroluje ważność szybkości, wykorzystując metodę z parametrem Vmax, dającym kolejny wariant PSO, różniący się od metody ze współczynnikiem inercji.
Różnice między EC a PSO
W technikach ewolucyjnych wykorzystuje się trzy główne operacje: krzyżowania, mutacji i selekcji. PSO nie posiada bezpośrednio operatora krzyżowania. Jednakże losowe przyspieszenie cząsteczki w stadzie (lub według najlepszej cząsteczki w sąsiedztwie, sąsiedztwie wersji lokalnej) przypomina procedurę rekombinacji w EC (Eberhart, Ski 1998, Rechenberg 1994, Schwefel 1995). W PSO wymiana informacji ma miejsce tylko w obrębie własnych doświadczeń i doświadczeń najlepszej cząsteczki w stadzie, w przeciwieństwie do wybory rodziców, wymiany informacji i przekazywania ich swoim potomkom w EC.

Co więcej, w PSO operacja aktualizacji miejsca pozycji przypomina mutację w EC, z wbudowaną formą pamięci. Ta przypominająca mutację procedura jest wielokierunkowa w PSO i EC i kontroluje prostotę mutacji wykorzystując współczynniki Vmax i χ.



PSO jest właściwie jedynym algorytmem ewolucyjnym niewykorzystującym zasady „przeżywa najlepiej przystosowany”, bowiem nie wykorzystuje bezpośrednio funkcji selekcji. W ten sposób cząsteczki z niskim przystosowaniem mogą przeżyć w procesie optymalizacji i potencjalnie mogą odwiedzać dowolny punkt w przestrzeni przeszukiwań (Eberhart, Ski, 1998).




©snauka.pl 2019
wyślij wiadomość

    Strona główna
Komunikat prasowy
przedmiotu zamówienia
najkorzystniejszej oferty
Informacja prasowa
wyborze najkorzystniejszej
warunków zamówienia
istotnych warunków
sprawie powołania
Regulamin konkursu
udzielenie zamówienia
przetargu nieograniczonego
zamówienia publicznego
Nazwa przedmiotu
Specyfikacja istotnych
modułu kształcenia
Rozporządzenie komisji
studia stacjonarne
wyborze oferty
Zapytanie ofertowe
Szkolny zestaw
Ochrony rodowiska
ramach projektu
prasowy posiedzenie
trybie przetargu
obwodowych komisji
zagospodarowania przestrzennego
komisji wyborczych
komisji wyborczej
Program konferencji
Wymagania edukacyjne
Lista kandydatów
szkoły podstawowej
która odbyła
Województwa ląskiego
Decyzja komisji
przedmiotu modułu
poszczególne oceny
Sylabus przedmiotu
szkół podstawowych
semestr letni
Postanowienia ogólne
przedsi biorców
produktu leczniczego
Karta przedmiotu
Scenariusz lekcji
Lista uczestników
Program nauczania
Projekt współfinansowany
Informacje ogólne
biblioteka wojewódzka
semestr zimowy