Optymalizacja roju cząstek

Rój cząstek poszukujący globalnego minimum funkcji
Część serii o
algorytmie ewolucyjnym
Algorytm genetyczny
Programowanie genetyczne

W naukach obliczeniowych optymalizacja roju cząstek ( PSO ) to metoda obliczeniowa, która optymalizuje problem poprzez iteracyjne próby ulepszenia kandydata na rozwiązanie w odniesieniu do danej miary jakości . Rozwiązuje problem, mając populację kandydujących rozwiązań, tutaj nazwanych cząstkami , i przesuwając te cząstki w przestrzeni poszukiwań zgodnie z prostym wzorem matematycznym na położenie cząstki i prędkość . Na ruch każdej cząstki wpływa jej najlepiej znana lokalna pozycja, ale jest on również prowadzony w kierunku najbardziej znanych pozycji w przestrzeni poszukiwań, które są aktualizowane w miarę znajdowania lepszych pozycji przez inne cząstki. Oczekuje się, że przesunie to rój w kierunku najlepszych rozwiązań.

PSO jest pierwotnie przypisywane Kennedy'emu , Eberhartowi i Shi i początkowo było przeznaczone do symulacji zachowań społecznych , jako stylizowana reprezentacja ruchu organizmów w stadzie ptaków lub ławicy ryb . Algorytm został uproszczony i zaobserwowano, że wykonuje optymalizację. Książka Kennedy'ego i Eberharta opisuje wiele filozoficznych aspektów PSO i inteligencji roju . Obszerne badanie wniosków PSO przeprowadza Poli . Niedawno Bonyadi i Michalewicz opublikowali obszerny przegląd prac teoretycznych i eksperymentalnych nad PSO.

PSO jest metaheurystyką , ponieważ przyjmuje niewiele lub nie przyjmuje żadnych założeń dotyczących optymalizowanego problemu i może przeszukiwać bardzo duże przestrzenie potencjalnych rozwiązań. Ponadto PSO nie wykorzystuje gradientu optymalizowanego problemu, co oznacza, że ​​PSO nie wymaga, aby problem optymalizacji był różniczkowalny , jak jest to wymagane w przypadku klasycznych metod optymalizacyjnych, takich jak metoda opadania gradientu i metody quasi-niutonowe . Jednak metaheurystyki, takie jak PSO, nie gwarantują znalezienia optymalnego rozwiązania.

Algorytm

Podstawowy wariant algorytmu PSO działa na zasadzie posiadania populacji (zwanej rojem) rozwiązań kandydujących (zwanych cząstkami). Cząsteczki te poruszają się w przestrzeni poszukiwań według kilku prostych wzorów. Ruchy cząstek są kierowane przez ich własną najlepiej znaną pozycję w przestrzeni poszukiwań, jak również przez najbardziej znaną pozycję całego roju. Gdy zostaną odkryte ulepszone pozycje, przyjdą one kierować ruchami roju. Proces jest powtarzany i ma się nadzieję, ale nie gwarantuje, że ostatecznie zostanie odkryte zadowalające rozwiązanie.

Formalnie niech f : ℝ n → ℝ będzie funkcją kosztu, którą należy zminimalizować. Funkcja przyjmuje rozwiązanie kandydujące jako argument w postaci wektora liczb rzeczywistych i generuje jako wynik liczbę rzeczywistą, która wskazuje wartość funkcji celu danego rozwiązania kandydującego. Gradient f nie jest znany . Celem jest znalezienie rozwiązania a , dla którego f ( a ) ≤ f ( b ) dla wszystkich b w przestrzeni poszukiwań, co oznaczałoby, że a jest minimum globalnym.

Niech S będzie liczbą cząstek w roju, z których każda ma pozycję x i ∈ ℝ n w przestrzeni poszukiwań i prędkość v i ∈ ℝ n . Niech pi będzie najlepiej znaną pozycją cząstki i i niech g będzie najlepiej znaną pozycją całego roju. Podstawowym algorytmem PSO minimalizującym funkcję kosztu jest zatem: 

 
      dla  każdej cząstki  i  = 1, ...,  S  do  Zainicjuj pozycję cząstki za pomocą  równomiernie rozłożonego  wektora losowego:  x  i  ~  U  (  b  lo  ,  b  up  ) Zainicjuj najbardziej znaną pozycję cząstki do jej początkowej pozycji:  p  i  ←  x  ja  jeśli  fa  (  pi  ja  ) <  fa  (  g  )  wtedy  
         zaktualizuj najlepiej znaną pozycję roju:  g  ←  p  i  Zainicjuj prędkość cząstki:  v  i  ~  U  (-|  b  up  -  b  lo  |, |  b  up  -  b  lo  |)  gdy  kryterium zakończenia nie jest spełnione  wykonaj  :  dla  każdej cząstki  i  = 1, ...,  S  zrobić  dla  każdego wymiaru  d  = 1, ...,     n  do  Wybierz liczby losowe:  r  p  ,  r  g  ~  U  (0,1) Zaktualizuj prędkość cząstki:  v  i,d  ← w  v  i,d  + φ  p  r  p  (  p  i,d  -  x  i,d  ) + φ  g  r  g  (  g  d  -  x  i,d  ) Zaktualizuj położenie cząstki:  x  i  ←  x 
         
              i  +  v  i  jeśli  f  (  x  i  ) <  f  (  p  i  )  następnie  Zaktualizuj najlepiej znaną pozycję cząstki:  p  i  ←  x  i  jeśli  f  (  pi  )  <  f  (  g  )  następnie  Zaktualizuj najlepiej znaną pozycję roju:  g  ←  p  ja

Wartości b lo i b up reprezentują odpowiednio dolną i górną granicę przestrzeni poszukiwań. Parametr w to masa bezwładności. Parametry φ p i φ g są często nazywane współczynnikiem poznawczym i współczynnikiem społecznym.

Kryterium zakończenia może być liczba wykonanych iteracji lub rozwiązanie, w którym zostanie znaleziona odpowiednia wartość funkcji celu. Parametry w, φ p i φ g są wybierane przez praktyka i kontrolują zachowanie i skuteczność metody PSO ( poniżej ).

Wybór parametrów

Krajobraz wydajności przedstawiający łączną skuteczność prostego wariantu PSO w kilku testach porównawczych przy zmianie dwóch parametrów PSO.

Wybór parametrów PSO może mieć duży wpływ na wydajność optymalizacji. Wybór parametrów PSO, które zapewniają dobre wyniki, był zatem przedmiotem wielu badań.

Aby zapobiec rozbieżności („eksplozji”), ciężar bezwładności musi być mniejszy niż 1. Dwa pozostałe parametry można następnie wyprowadzić dzięki podejściu zwężenia lub dowolnie wybrać, ale analizy sugerują domeny zbieżności, aby je ograniczyć. Typowe wartości są w .

Parametry PSO można również dostroić za pomocą innego nakładającego się optymalizatora, koncepcji znanej jako meta-optymalizacja , lub nawet dostroić podczas optymalizacji, np. za pomocą logiki rozmytej.

Parametry zostały również dostrojone pod kątem różnych scenariuszy optymalizacji.

Sąsiedztwa i topologie

Topologia roju określa podzbiór cząstek, z którymi każda cząstka może wymieniać informacje. Podstawowa wersja algorytmu wykorzystuje topologię globalną jako strukturę komunikacji roju. Ta topologia pozwala wszystkim cząstkom komunikować się ze wszystkimi innymi cząstkami, dzięki czemu cały rój ma tę samą najlepszą pozycję g z pojedynczej cząstki. Jednak takie podejście może doprowadzić do uwięzienia roju w lokalnym minimum, dlatego do kontrolowania przepływu informacji między cząstkami zastosowano różne topologie. Na przykład w lokalnych topologiach cząstki dzielą się informacjami tylko z podzbiorem cząstek. Ten podzbiór może być podzbiorem geometrycznym – na przykład „ m najbliższych cząstek” – lub częściej społecznym, czyli zbiorem cząstek, który nie zależy od żadnej odległości. W takich przypadkach mówi się, że wariant PSO jest najlepszy lokalnie (w porównaniu z najlepszym globalnym dla podstawowego PSO).

Powszechnie stosowaną topologią roju jest pierścień, w którym każda cząstka ma tylko dwóch sąsiadów, ale jest ich znacznie więcej. Topologia niekoniecznie jest statyczna. W rzeczywistości, ponieważ topologia jest związana z różnorodnością komunikacji cząstek, podjęto pewne wysiłki w celu stworzenia topologii adaptacyjnych (SPSO, APSO, gwiazda stochastyczna, TRIBES, Cyber ​​Swarm i C-PSO)

Wewnętrzne funkcjonowanie

Istnieje kilka szkół myślenia, dlaczego i jak algorytm PSO może przeprowadzać optymalizację.

Powszechnym przekonaniem wśród badaczy jest to, że zachowanie roju waha się między zachowaniem eksploracyjnym, czyli przeszukiwaniem szerszego obszaru przestrzeni poszukiwań, a zachowaniem eksploatacyjnym, czyli lokalnie zorientowanym poszukiwaniem, aby zbliżyć się do (prawdopodobnie lokalnego) optymalny. Ta szkoła myślenia była powszechna od początku PSO. Ta szkoła myślenia twierdzi, że algorytm PSO i jego parametry muszą być tak dobrane, aby odpowiednio zrównoważyć eksplorację i eksploatację, aby uniknąć przedwczesnej konwergencji do lokalnego optimum , ale nadal zapewniać dobre tempo konwergencji do optymalnego. To przekonanie jest prekursorem wielu wariantów PSO, patrz poniżej .

Inną szkołą myślenia jest to, że zachowanie roju PSO nie jest dobrze rozumiane pod względem tego, jak wpływa na rzeczywistą wydajność optymalizacji, zwłaszcza w przypadku wielowymiarowych przestrzeni wyszukiwania i problemów optymalizacyjnych, które mogą być nieciągłe, hałaśliwe i zmienne w czasie. Ta szkoła myślenia jedynie próbuje znaleźć algorytmy i parametry PSO, które powodują dobrą wydajność, niezależnie od tego, jak można interpretować zachowanie roju w odniesieniu np. do eksploracji i eksploatacji. Takie badania doprowadziły do ​​uproszczenia algorytmu PSO, patrz poniżej .

Konwergencja

W odniesieniu do PSO słowo konwergencja zwykle odnosi się do dwóch różnych definicji:

  • Zbieżność sekwencji rozwiązań (inaczej analiza stabilności, zbieżność ), w której wszystkie cząstki zbiegły się do punktu w przestrzeni poszukiwań, który może być optymalny lub nie,
  • Konwergencja do lokalnego optimum, gdzie wszystkie rekordy życiowe p lub, alternatywnie, najlepiej znana pozycja roju g zbliża się do lokalnego optimum problemu, niezależnie od tego, jak zachowuje się rój.

Zbadano zbieżność sekwencji rozwiązań dla PSO. Analizy te zaowocowały wytycznymi dotyczącymi wyboru parametrów PSO, które, jak się uważa, powodują zbieżność do punktu i zapobiegają rozbieżności cząstek roju (cząsteczki nie poruszają się w nieskończoność i gdzieś się zbiegają). Jednak analizy zostały skrytykowane przez Pedersena za nadmierne uproszczenie, ponieważ zakładają, że rój ma tylko jedną cząstkę, że nie wykorzystuje zmiennych stochastycznych i że punkty przyciągania, czyli najlepiej znana pozycja cząstki p i najlepiej znana pozycja roju G pozostają stałe przez cały proces optymalizacji. Wykazano jednak, że te uproszczenia nie wpływają na granice znalezione w tych badaniach dla parametru, w którym rój jest zbieżny. W ostatnich latach podjęto znaczne wysiłki w celu osłabienia założeń modelowania zastosowanych podczas analizy stabilności PSO, przy czym najnowszy uogólniony wynik dotyczył wielu wariantów PSO i wykorzystano to, co okazało się minimalnym niezbędnym założeniem modelowania.

Zbieżność do lokalnego optimum została przeanalizowana dla PSO w i . Udowodniono, że PSO wymaga pewnej modyfikacji, aby zagwarantować znalezienie lokalnego optimum.

Oznacza to, że określenie możliwości konwergencji różnych algorytmów i parametrów PSO nadal zależy od wyników empirycznych . Jedną z prób rozwiązania tego problemu jest opracowanie strategii „ortogonalnego uczenia się” w celu lepszego wykorzystania informacji już istniejących w relacji między p i g , aby utworzyć wiodący zbieżny model i być skutecznym z dowolną topologią PSO. Celem jest ogólna poprawa wydajności PSO, w tym szybsza globalna konwergencja, wyższa jakość rozwiązań i większa niezawodność. Jednak takie badania nie dostarczają teoretycznych dowodów na faktyczne udowodnienie ich twierdzeń.

Mechanizmy adaptacyjne

Bez potrzeby kompromisu między konwergencją („eksploatacja”) a dywergencją („eksploracja”) można wprowadzić mechanizm adaptacyjny. Adaptacyjna optymalizacja roju cząstek (APSO) zapewnia lepszą wydajność wyszukiwania niż standardowe PSO. APSO może przeprowadzać globalne wyszukiwanie w całej przestrzeni wyszukiwania z większą szybkością konwergencji. Umożliwia automatyczną kontrolę masy bezwładności, współczynników przyspieszenia i innych parametrów algorytmu w czasie pracy, poprawiając jednocześnie skuteczność i wydajność wyszukiwania. Ponadto APSO może działać na globalnie najlepszej cząstce, aby wyskoczyć z prawdopodobnych lokalnych optimów. APSO wprowadzi jednak nowe parametry algorytmu, nie wprowadza jednak dodatkowej złożoności projektowej ani implementacyjnej.

Warianty

Możliwe są liczne warianty nawet podstawowego algorytmu PSO. Na przykład istnieją różne sposoby inicjalizacji cząstek i prędkości ( np . zamiast tego zacząć od prędkości zerowych), jak tłumić prędkość, aktualizować pi i g dopiero po aktualizacji całego roju itp. Niektóre z tych wyborów i ich możliwy wpływ na wydajność zostały omówione w literaturze.

Wiodący badacze stworzyli szereg standardowych implementacji „przeznaczonych zarówno jako podstawa do testowania wydajności ulepszeń techniki, jak i do reprezentowania PSO w szerszej społeczności zajmującej się optymalizacją. Posiadanie dobrze znanego, ściśle zdefiniowanego standardowy algorytm zapewnia cenny punkt porównawczy, który można wykorzystać w całej dziedzinie badań, aby lepiej przetestować nowe postępy”. Najnowszy to Standard PSO 2011 (SPSO-2011).

Hybrydyzacja

Nowe i bardziej wyrafinowane warianty PSO są również stale wprowadzane w celu poprawy wydajności optymalizacji. Istnieją pewne trendy w tych badaniach; jednym z nich jest stworzenie hybrydowej metody optymalizacji przy użyciu PSO w połączeniu z innymi optymalizatorami, np. połączonego PSO z optymalizacją opartą na biogeografii oraz włączenie efektywnej metody uczenia się.

Złagodzić przedwczesną konwergencję

Innym trendem badawczym jest próba złagodzenia przedwczesnej konwergencji (czyli stagnacji optymalizacji), np. poprzez odwrócenie lub zakłócenie ruchu cząstek PSO, innym podejściem do radzenia sobie z przedwczesną konwergencją jest użycie wielu rojów (optymalizacja wielorojowa ) . Podejście wielorojowe można również wykorzystać do wdrożenia optymalizacji wielokryterialnej. Wreszcie, istnieją zmiany w dostosowywaniu parametrów behawioralnych PSO podczas optymalizacji.

uproszczenia

Inna szkoła myślenia jest taka, że ​​obowiązek użyteczności publicznej powinien zostać maksymalnie uproszczony bez uszczerbku dla jego wykonania; ogólna koncepcja często nazywana brzytwą Ockhama . Uproszczenie PSO zostało pierwotnie zaproponowane przez Kennedy'ego i zostało dokładniej zbadane, gdzie okazało się, że wydajność optymalizacji została poprawiona, a parametry były łatwiejsze do dostrojenia i działały bardziej konsekwentnie w różnych problemach optymalizacyjnych.

Innym argumentem przemawiającym za uproszczeniem PSO jest to, że skuteczność metaheurystyk można wykazać empirycznie jedynie poprzez przeprowadzenie eksperymentów obliczeniowych na skończonej liczbie problemów optymalizacyjnych. Oznacza to, że nie można udowodnić poprawności metaheurystyki takiej jak PSO , a to zwiększa ryzyko popełnienia błędów w jej opisie i implementacji. Dobrym tego przykładem jest obiecujący wariant algorytmu genetycznego (kolejna popularna metaheurystyka), ale później okazało się, że jest wadliwa, ponieważ była silnie obciążona w poszukiwaniu optymalizacji w kierunku podobnych wartości dla różnych wymiarów w przestrzeni wyszukiwania, co okazało się optymalne z rozważanych problemów wzorcowych. To odchylenie było spowodowane błędem programistycznym i zostało już naprawione.

Inicjalizacja prędkości może wymagać dodatkowych danych wejściowych. Wariant Bare Bones PSO został zaproponowany w 2003 roku przez Jamesa Kennedy'ego i w ogóle nie musi wykorzystywać prędkości.

Innym prostszym wariantem jest przyspieszona optymalizacja roju cząstek (APSO), która również nie musi wykorzystywać prędkości i może przyspieszyć konwergencję w wielu zastosowaniach. Dostępny jest prosty kod demonstracyjny APSO.

Optymalizacja wielocelowa

PSO zastosowano również do problemów wielokryterialnych , w których porównanie funkcji celu uwzględnia dominację Pareto podczas przemieszczania cząstek PSO, a niezdominowane rozwiązania są przechowywane tak, aby przybliżać przód Pareto.

Binarne, dyskretne i kombinatoryczne

Ponieważ podane powyżej równania PSO działają na liczbach rzeczywistych, powszechnie stosowaną metodą rozwiązywania problemów dyskretnych jest mapowanie dyskretnej przestrzeni poszukiwań na domenę ciągłą, zastosowanie klasycznego PSO, a następnie odwzorowywanie wyniku. Takie odwzorowanie może być bardzo proste (na przykład przy użyciu zaokrąglonych wartości) lub bardziej wyrafinowane.

Można jednak zauważyć, że równania ruchu wykorzystują operatory realizujące cztery akcje:

  • obliczanie różnicy dwóch pozycji. Wynikiem jest prędkość (dokładniej przemieszczenie)
  • mnożenie prędkości przez współczynnik liczbowy
  • dodając dwie prędkości
  • przyłożenie prędkości do pozycji

Zwykle pozycja i prędkość są reprezentowane przez n liczb rzeczywistych, a tymi operatorami są po prostu -, *, + i znowu +. Ale wszystkie te obiekty matematyczne można zdefiniować w zupełnie inny sposób, aby poradzić sobie z problemami binarnymi (lub bardziej ogólnie dyskretnymi), a nawet kombinatorycznymi. Jednym ze sposobów jest przedefiniowanie operatorów na podstawie zbiorów.

Zobacz też

Linki zewnętrzne

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Particle_swarm_optimization&oldid=1141867412 ”