Optymalizacja roju cząstek - Particle swarm optimization

Rój cząstek poszukujący globalnego minimum funkcji

W informatyce , optymalizacji rojem cząstek ( PSO ) to metoda obliczeniowa, która optymalizuje problem przez iteracyjnie próbując poprawić rozwiązanie kandydata w odniesieniu do danego środka jakości. Rozwiązuje problem poprzez posiadanie populacji możliwych rozwiązań, tutaj nazwanych cząstkami , i przemieszczanie tych cząstek w przestrzeni poszukiwań zgodnie z prostym wzorem matematycznym nad położeniem i prędkością cząstki . Na ruch każdej cząstki wpływa jej najlepiej znana lokalna pozycja, ale jest ona również kierowana 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 przypisywana Kennedy'emu , Eberhartowi i Shi i była początkowo przeznaczona do symulowania zachowań społecznych , jako stylizowana reprezentacja ruchu organizmów w ptasim stadzie lub ławicy ryb . Algorytm został uproszczony i zaobserwowano, że przeprowadza optymalizację. Książka Kennedy'ego i Eberharta opisuje wiele filozoficznych aspektów PSO i inteligencji roju . Poli przeprowadza obszerny przegląd aplikacji PSO . Niedawno Bonyadi i Michalewicz opublikowali obszerny przegląd prac teoretycznych i eksperymentalnych dotyczących PSO.

PSO to metaheurystyka, 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 optymalizacji, takich jak metody gradientu i quasi-niutona . Jednak metaheurystyki, takie jak PSO, nie gwarantują znalezienia optymalnego rozwiązania.

Algorytm

Podstawowy wariant algorytmu PSO działa na podstawie populacji (nazywanej rojem) rozwiązań kandydujących (nazywanych cząstkami). Cząstki te poruszają się w przestrzeni poszukiwań według kilku prostych wzorów. Ruchami cząstek kieruje ich najbardziej znana pozycja w przestrzeni poszukiwań, jak również najbardziej znana pozycja całego roju. Kiedy odkryte zostaną ulepszone pozycje, zaczną one kierować ruchami roju. Proces jest powtarzany i dzięki temu ma się nadzieję, ale nie gwarantuje się, że ostatecznie zostanie odkryte satysfakcjonujące rozwiązanie.

Formalnie niech f : ℝ n  → ℝ będzie funkcją kosztu, którą należy zminimalizować. Funkcja przyjmuje roztworu kandydującego jako argumentu w postaci wektora z liczb rzeczywistych i tworzy liczbę rzeczywistą jako wyjście, który wskazuje cel wartości funkcji danego roztworu kandydującego. Gradientu od f nie jest znana. 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 p i będzie najbardziej znaną pozycją cząstki i, a g najlepiej znaną pozycją całego roju. Podstawowym algorytmem PSO jest wtedy:

for each particle i = 1, ..., S do
    Initialize the particle's position with a uniformly distributed random vector: xi ~ U(blobup)
    Initialize the particle's best known position to its initial position: pi ← xi
    if f(pi) < f(g) then
        update the swarm's best known position: g ← pi
    Initialize the particle's velocity: vi ~ U(-|bup-blo|, |bup-blo|)
while a termination criterion is not met do:
    for each particle i = 1, ..., S do
        for each dimension d = 1, ..., n do
            Pick random numbers: rp, rg ~ U(0,1)
            Update the particle's velocity: vi,d ← w vi,d + φp rp (pi,d-xi,d) + φg rg (gd-xi,d)
        Update the particle's position: xi ← xi + vi
        if f(xi) < f(pi) then
            Update the particle's best known position: pi ← xi
            if f(pi) < f(g) then
                Update the swarm's best known position: g ← pi

Wartości b lo i b up reprezentują odpowiednio dolną i górną granicę przestrzeni poszukiwań. Parametr w to ciężar 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 wybierane są przez lekarza i kontrolować działanie i skuteczność sposobu PSO ( poniżej ).

Wybór parametrów

Krajobraz wydajności pokazujący, jak prosty wariant PSO sprawdza się łącznie w kilku testach porównawczych, gdy różnią się dwa parametry PSO.

Wybór parametrów PSO może mieć duży wpływ na wydajność optymalizacji. Wybór parametrów PSO dających dobre osiągi był więc przedmiotem wielu badań.

Aby zapobiec rozbieżności („wybuch”), masa bezwładności musi być mniejsza niż 1. Dwa pozostałe parametry można następnie wyprowadzić dzięki podejściu zwężającemu lub dowolnie wybrać, ale analizy sugerują domeny zbieżności, które je ograniczają. Typowe wartości to .

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.

Okolice 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ąsteczkom komunikować się ze wszystkimi innymi cząsteczkami, dzięki czemu cały rój dzieli tę samą najlepszą pozycję g od pojedynczej cząsteczki. Takie podejście może jednak prowadzić 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. Może to być podzbiór geometryczny – na przykład „ cząstki najbliższe m ” – lub częściej społeczny, czyli zbiór cząstek, który nie jest zależny od żadnej odległości. W takich przypadkach wariant PSO jest uważany za najlepszy lokalny (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 wielu. 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 adaptacyjnych topologii (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ę.

Wśród badaczy panuje powszechne przekonanie, że zachowanie roju różni się między zachowaniem eksploracyjnym, to znaczy przeszukiwaniem szerszego obszaru przestrzeni poszukiwań, a zachowaniem eksploatacyjnym, czyli wyszukiwaniem zorientowanym lokalnie, aby zbliżyć się do (prawdopodobnie lokalnego) optymalny. Ta szkoła myślenia jest powszechna od początku istnienia PSO. Zgodnie z tą szkołą myślenia algorytm PSO i jego parametry muszą być tak dobrane, aby odpowiednio zrównoważyć eksplorację i eksploatację, aby uniknąć przedwczesnej zbieżności do lokalnego optimum, a jednocześnie zapewnić dobre tempo zbieżności do optimum. To przekonanie jest prekursorem wielu wariantów PSO, patrz poniżej .

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

Konwergencja

W odniesieniu do PSO słowo konwergencja zazwyczaj 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ć lub nie być optymalny,
  • Konwergencja do lokalnego optimum, gdzie wszystkie rekordy osobiste p lub, alternatywnie, najlepiej znana pozycja roju g , zbliżają się do lokalnego optimum problemu, niezależnie od tego, jak zachowuje się rój.

Zbieżność sekwencji rozwiązań została zbadana 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ąstki nie poruszają się bez ograniczeń i będą się gdzieś zbiegać). 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 stwierdzone w tych badaniach dla parametru, w którym rój jest zbieżny. W ostatnich latach poczyniono znaczne wysiłki w celu osłabienia założenia modelowania wykorzystywanego podczas analizy stabilności PSO, przy czym najnowszy uogólniony wynik miał zastosowanie do wielu wariantów PSO i wykorzystano to, co okazało się minimalnymi niezbędnymi założeniami modelowania.

Zbieżność do lokalnego optimum została przeanalizowana dla PSO w i. Udowodniono, że PSO wymaga pewnych 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 „uczenia ortogonalnego” w celu lepszego wykorzystania informacji już istniejących w relacji między p i g , tak aby utworzyć wiodący, zbieżny przykład i być skutecznym w dowolnej topologii PSO. Celem jest poprawa ogólnej wydajności PSO, w tym szybsza globalna konwergencja, wyższa jakość rozwiązania i większa niezawodność. Jednak takie badania nie dostarczają teoretycznych dowodów, aby faktycznie udowodnić ich twierdzenia.

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 poszukiwań z większą szybkością zbieżności. Umożliwia automatyczną kontrolę masy bezwładności, współczynników przyspieszenia i innych parametrów algorytmicznych w czasie wykonywania, poprawiając jednocześnie skuteczność i wydajność wyszukiwania. Ponadto APSO może oddziaływać na najlepszą na świecie cząsteczkę, aby wyskoczyć z prawdopodobnego lokalnego optima. Jednak APSO wprowadzi nowe parametry algorytmu, nie wprowadzi to jednak dodatkowej złożoności projektowania ani implementacji.

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ć tylko p i i g po zaktualizowaniu całego roju itp. Niektóre z tych wyborów i ich możliwy wpływ na wydajność został omówiony w literaturze.

Wiodący badacze stworzyli szereg standardowych wdrożeń, „przeznaczonych do wykorzystania zarówno jako punkt odniesienia do testowania wydajności ulepszeń techniki, jak i do reprezentowania PSO w szerszej społeczności optymalizacji. Posiadanie dobrze znanej, ściśle określonej Standardowy algorytm zapewnia cenny punkt porównawczy, który można wykorzystać w całej dziedzinie badań, aby lepiej testować nowe osiągnięcia." 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. W tych badaniach są pewne trendy; jednym z nich jest stworzenie hybrydowej metody optymalizacji przy użyciu PSO połączonej z innymi optymalizatorami, np. połączonego PSO z optymalizacją opartą na biogeografii, oraz wprowadzenie efektywnej metody uczenia się.

Gradientowe algorytmy PSO

Zdolność algorytmu PSO do wydajnego badania wielu lokalnych minimum może być połączona ze zdolnością algorytmów wyszukiwania lokalnego opartego na gradiencie do skutecznego obliczania dokładnego minimum lokalnego w celu uzyskania algorytmów PSO opartych na gradiencie. W algorytmach PSO opartych na gradiencie algorytm PSO jest używany do badania wielu lokalnych minimów i lokalizowania punktu w basenie przyciągania o głębokim lokalnym minimum. Następnie stosuje się wydajne algorytmy wyszukiwania lokalnego oparte na gradiencie, aby dokładnie zlokalizować głębokie minimum lokalne. Obliczanie gradientów i hesjanów złożonych, wysokowymiarowych funkcji kosztu jest często kosztowne obliczeniowo i w wielu przypadkach niemożliwe ręcznie, co uniemożliwia powszechne przyjęcie algorytmów PSO opartych na gradientach. Jednak w ostatnich latach dostępność wysokiej jakości oprogramowania do automatycznego różnicowania symbolicznego (AD) doprowadziła do ponownego zainteresowania algorytmami PSO opartymi na gradientach.

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że być również wykorzystane do wdrożenia optymalizacji wielokryterialnej. Wreszcie nastąpił postęp w dostosowywaniu parametrów behawioralnych PSO podczas optymalizacji.

Uproszczenia

Inną szkołą myślenia jest to, że PSO należy uprościć tak bardzo, jak to możliwe, bez pogarszania jego wydajności; ogólna koncepcja często określana jako brzytwa Ockhama . Uproszczenie PSO zostało pierwotnie zasugerowane przez Kennedy'ego i zostało zbadane szerzej, 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 metaheurystyki można udowodnić jedynie empirycznie , przeprowadzając eksperymenty obliczeniowe na skończonej liczbie problemów optymalizacyjnych. Oznacza to, że nie można udowodnić poprawności metaheurystyki takiej jak PSO, co zwiększa ryzyko popełnienia błędów w jej opisie i implementacji. Dobrym tego przykładem był obiecujący wariant algorytmu genetycznego (kolejna popularna metaheurystyka), ale później okazało się, że jest on wadliwy, ponieważ był silnie stronniczy w wyszukiwaniu optymalizacyjnym w kierunku podobnych wartości dla różnych wymiarów w przestrzeni wyszukiwania, co okazało się optimum rozważanych problemów wzorcowych. To nastawienie było spowodowane błędem programowania i zostało teraz 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 wymaga użycia 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ż w problemach wielokryterialnych , w których porównanie funkcji celu uwzględnia dominację pareto podczas przemieszczania cząstek PSO, a rozwiązania niezdominowane są przechowywane tak, aby przybliżyć front pareto.

Binarny, dyskretny i kombinatoryczny

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

Można jednak zauważyć, że równania ruchu wykorzystują operatory wykonujące cztery czynności:

  • obliczenie różnicy dwóch pozycji. Wynikiem jest prędkość (a dokładniej przemieszczenie)
  • pomnożenie prędkości przez współczynnik liczbowy
  • dodanie dwóch 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 ogólniej dyskretnymi), a nawet kombinatorycznymi. Jednym z podejść jest przedefiniowanie operatorów na podstawie zbiorów.

Zobacz też

Bibliografia

Zewnętrzne linki