Particle Swarm Optimization - Modelul ansamblului de particule

Particle Swarm Optimization - Modelul ansamblului de particule

Studiul si evaluarea diverselor tipare de comportament emergent

In ultimii ani, interesul pentru colectivele mari compuse din roboti mici, relativi ieftini a crescut foarte mult. Evolutia echipamentului ce prelucreaza informatii precum si noua tendinta de miniaturizare a dispozitivelor electronice a condus la faptul ca sistemele distribuite emergente sunt acum o alternativa viabila pentru o abordare clasica mai centralizata. Majoritatea colectivelor robotice au mai multe parti componente, fiecare implementand o anumita functionalitate, dar impreuna rezolvand probleme foarte complexe, care, probabil, nici nu ar putea fi solutionate de o singura componenta a unui astfel de sistem din diverse motive, cum ar fi capacitatea de procesare sau cea de stocare a datelor.

Inteligenta roiurilor

Societatile de insecte sociale-furnici, albine, termite si viespi-sunt sisteme distribuite in care comportamentul general al coloniei reiese din interactiunile dintre indivizii acesteia. Care sunt secretele ce ghideaza comportamentul furnicilor, al albinelor sau al altor insecte sociale? Considerand exemplul termitelor, la nivel individual, ele au un nivel scazut de inteligenta. Lucreaza fara supraveghere si totusi la nivel de colonie au rezultate spectaculoase. Construiesc musuroaie care sunt adevarate minuni ale naturii, capabile sa pastreze in interior un nivel optim de oxigen si dioxid de carbon, caldura si umiditate chiar in conditiile in care musuroiul se modifica. Oamenii de stiinta au descoperit ca la nivelul unei colonii cooperarea este auto-organizata: in majoritatea situatiilor se realizeaza prin interactiunile dintre indivizi. Desi aceste interactiuni pot parea simple (o furnica urmand calea altei furnici), ele pot rezolva probleme complexe (gasirea celui mai scurt drum spre o sursa de hrana). Cu referire la insectele sociale, acest comportament colectiv emergent este numit "inteligenta roiurilor" (swarm intelligence).

Swarm Intelligence este o forma de inteligenta artificiala bazata pe comportamentul colectiv al sistemelor distribuite, auto-organizate si fara control centralizat. Aceasta expresie a fost introdusa pentru prima data de catre Gerardo Beni si Jing Wang in 1989 in contextul sistemelor celulare de roboti. O alta definitie, data de catre Bonabeau, Dorigo, Theraulaz este: "orice incercare de a proiecta algoritmi sau echipamente distribuite inspirate din comportamentul colectiv al coloniilor de insecte sociale sau alte societati de animale" .

Sistemele bazate pe SI sunt formate din agenti ce interactioneaza local unii cu altii si cu mediul inconjurator. Agentii urmeaza reguli foarte simple si chiar daca nu exista o structura de control care sa dicteze comportamentul fiecarui agent, interactiunile locale conduc la emergenta comportamentului global, complex.

Exemplele naturale de SI includ coloniile de furnici, stolurile de pasari, bancurile de pesti, roiurile de albine, turmele de animale.

PSO a fost descoperita (Kennedy si Eberhart, 1995) prin simulari ale deplasarii indivizilor intr-un stol de pasari sau intr-un banc de pesti. A fost initial conceputa pentru ca o metoda de optimizare a functiilor neliniare continue dar ulterior a fost adaptata pentru a rezolva probleme de permutare, programare cu numere intregi, probleme cu constrangeri, optimizare in medii dinamice sau multi-obiectiv.

Schema generala

Are multe lucruri in comun cu metodele din calculul evolutiv:

mentin o populatie de reprezentari de solutii candidat

care evolueaza de-a lungul unor iteratii aplicand o serie de operatori

in functie de informatia data de o functie fitness care masoara meritul individual.

Daca in hard-computing pasii necesari rezolvarii unei probleme sunt:

intelege problema;

construieste un model matematic si studiaza teoretic acel model;

modeleaza un algoritm de rezolvare a problemei pe baza rezultatelor teoretice;

implementeaza metoda si executa programul;

obtine solutia.

in cazul calculului evolutiv aceasta paradigma devine:

intelege problema;

costruieste reprezentarea; functia fitness;

modeleaza un algoritm de calcul evolutiv pentru rezolvarea ei;

implementeaza metoda si executa experimente;

obtine mai multe solutii;

ceea ce inseamna ca rezolvarea unei probleme nu mai trebuie sa fie precedata neaparat de obtinerea unor rezultate teoretice asupra modelului matematic corespunzator.

Fig.1. Etapele rezolvarii unei probleme in hard-computing si calcul evolutiv;

etapele hasurate reprezinta aproximari de la problema reala

Tehnicile calculului evolutiv sunt metode slabe de optimizare; ele nu sunt, in principiu, specializate ci sunt aplicabile unor clase largi de probleme.

Pentru a putea fi abordata cu aceste tehnici, problema de rezolvat trebuie pusa sub forma unei probleme de optimizare.

Deplasarea in grup nu este o caracteristica a unui individ, ci este o caracteristica a grupului din care face parte individul. Reynolds a identificat trei reguli simple pe care se bazeaza deplasarea in grup :

l       Separarea - daca o entitate este prea aproape de alta, atunci se departeaza de aceasta

l       Alinierea - deplasarea unei entitati in rand cu vecinii, daca se afla la o distanta optima de acestia

l       Coeziunea/Atractia - deplasarea catre vecini atunci cand este prea departe de acestia

In cadrul stolurilor de pasari nu exista un conducator. Fiecare pasare actioneaza tinand cont de aceste trei reguli, ca in Fig.2.

Fig.2. Regulile de deplasare a pasarilor

Terminologie

Algoritmii evolutivi utilizeaza un vocabular imprumutat din genetica. Un algoritm genetic simuleaza evolutia printr-o succesiune de generatii (proces iterativ) ale unei populatii (multime) de solutii candidat. O solutie candidat este reprezentata intern ca un sir de gene (genotip) si poarta numele de cromozom. Gena este informatia atomica dintr-un cromozom. Pozitia pe care o ocupa o gena se numeste locus iar toate valorile posibile pentru o gena formeaza setul de alele ale genei. Populatia mentinuta de algoritmul genetic evolueaza prin aplicarea unor operatori genetici care simuleaza elemente considerate de geneticieni ca fiind fundamentale: mutatia care consta in modificarea aleatoare a unei gene si incrucisarea (recombinarea) care are ca scop schimbul de informatie genetica intre doi sau mai multi cromozomi. Cromozomul asupra caruia se aplica un operator genetic poarta numele de parinte, iar cromozomul rezultat in urma acestui operator este numit descendent. Un proces (aleator) de selectie ofera indivizilor mai bine adaptati sanse mai mari pentru a supravietui in generatia urmatoare. Gradul de adaptare la mediu al indivizilor este masurat de functia fitness obtinuta pornind de la functia matematica de optimizat. Solutia returnata de un algoritm genetic este cel mai bun individ din ultima generatie.

'Boids'

'Boids', dezvoltat de Craig Reynolds in 1986, este un program de 'viata artificiala', care simuleaza comportamentul unui stol de pasari.

Ca si multe alte programe simulatoare de acest gen, Boids este un exemplu de comportament emergent; complexitatea lui ridicandu-se din momentul de interactiune a agentilor individuali care se supun unui set de reguli simple:

l       Apropierea de centrul de greutate al vecinilor

l       Evitarea coliziunilor cu vecinii

l       Potrivirea vitezei cu aceea a vecinilor

Pseudocod:

Apropierea:

Evitarea coliziunilor:

Potrivirea vitezei:

Comportament

Fig.3. Comportamentul de 'stol' este emergent

04. Auto-organizarea la albine

Un prim pas efectuat in procedura de auto-organizare in cazul roiurilor de albine este plasarea larvelor in celule alaturate celulelor cu polen si nectar.

Reguli:

l       Depoziteaza larvele in celule alaturate altor celule cu larve

l       Depoziteaza nectarul si polenul in celule aleatorii, dar goleste mai intai celulele cele mai apropiate de larve

l       Extrage mai mult polen decat nectar

Colectarea hranei depinde de timpul de asteptare la livrarea hranei in stup:

l       Daca stupul are deja multa hrana, albinele care o depoziteaza au nevoie de mai mult timp pentru a gasi celule goale

l       Timpul de asteptare mai mare determina albinele colectoare sa caute hrana de calitate mai buna, mai greu de gasit si care necesita deci mai mult timp

Miscarea bancurilor de pesti

Bancurile de pesti se caracterizeaza printr-o puternica coeziune si deplasare paralela fara sa aiba vreun lider. Cercetarile au aratat ca acestia se deplaseaza folosind in special vederea si anumite organe sensibile la miscarea si vibratia apei din jur. Acestea sunt folosite pentru a afla distanta si viteza vecinilor apropiati. Pestii sunt capabili sa stea impreuna pastrand o orientare paralela care dicteaza directia comuna de deplasare pentru intregul grup. Grupul poate astfel sa acopere o distanta mare intr-un timp scurt.

Pentru a explica miscarea acestora s-au creat numeroase modele. Una dintre teorii propune folosirea interactiunii dintre fortele de atractie si cele de respingere cu ajutorul carora se dirijeaza miscarea indivizilor. [1]

O alta teorie a fost propusa de Aoki si mai tarziu revizuita de Huth si Wissel. Acest model pleaca de la mai multe premise [2-4]:

fiecare membru al grupului foloseste aceleasi reguli pentru deplasare, astfel ca nu este nevoie de nici un lider

bancul de pesti se deplaseaza independent de stimuli externi

miscarea fiecarui peste este influentata doar de vecinii sai cei mai apropiati.

Fig.4. Deplasarea pestilor in functie de localizarea vecinului

Aoki a considerat ca in jurul fiecarui peste exista patru zone cu ajutorul carora se masoara apropierea sau departarea de cel mai apropiat vecin. In functie de posibila localizare a vecinului, acesta are patru alternative: respingere, orientare paralela, atractie si cautare. Alternativa aleasa ofera unghiul de influenta si modalitatea de comportare fata de acest vecin.[3]

Daca vecinul este la o distanta mai mica decat R1 in raport cu pestele, atunci pestele va arata un comportament de respingere si va inota perpendicular pe directia de deplasare a vecinului pentru a evita o coliziune. Astfel, unghiul de influenta este ± 90°.

Daca vecinul este intre R1 si R2 atunci pestele va inota in aceeasi directie cu vecinul, unghiul de influenta fiind cel al vecinului.

Daca este localizat intre R2 si R3, pestele va incerca sa se apropie de vecin, aratand un comportament de atractie. Pestele va inota in directia vecinului.

Huth si Wissel au adaugat ultimul tipar modelului. Daca vecinul este la o distanta mai mare ca R3, pestele nu poate percepe vecinul deoarece simturile sale sunt limitate. Astfel ca pestele va manifesta un comportament de cautare, mergand aleator.

Atat Aoki, cat si Huth si Wissel au folosit distributiile de probabilitate pentru a determina unghiul de intoarcere pe care pestele il va lua in considerare in functie de gradul de incertitudine legat de detectarea pozitiei si orientarii vecinului. [1-5]

Ultimul element al modelului este modul in care pestii raspund influentelor exercitate de ceilalti vecini. Aoki a folosit un concept decizional cu ajutorul caruia pestele alege care este vecinul pe care il va urma. Fiecare vecin primeste un anumit factor in functie de importanta pentru pestele respectiv, iar unghiul de intoarcere se calculeaza din doua sau mai multe distributii ponderate. Daca vecinul 1 este mai in fata decat vecinul 2, importanta distributiei sale va fi de doua ori mai mare decat a vecinului 1, astfel ca pestele va urma vecinul numarul 1. Huth si Wissel au propus un concept in care pestele face o combinatie intre influentele vecinilor sai luand media unghiului de influenta al fiecarui vecin, iar probabilitatea de distributie este doar una si consta in distributia normala fata de unghiul mediu.

Conform modelului prezentat in [1] si revizuit mai tarziu in [2], bancurile de pesti nu au un lider. Fiecare membru al grupului se misca dupa aceleasi reguli ca si ceilalti.

De asemenea, miscarile pestelui sunt influentate numai de cei mai apropiati vecini. Fiecare peste poate aproxima vizual distanta dintre el si vecinii sai, iar inaintarea vecinilor si viteza printr-un senzor natural pe care il are un peste, numit linia laterala care poate sesiza miscarea curentilor de apa din apropierea pestelui.

Fig.5. Miscarea de baza a bancului de pesti

Conform cu [1], fiecare peste este inconjurat de patru zone distincte, asa cum se arata in Fig. 1. In functie de pozitia relativa a pestilor vecini fata de pestele principal, exista patru cazuri, dupa cum urmeaza:

Daca un peste vecin este situat in cercul cel mai apropiat din jurul pestelui principal, urmatoarea lor miscare va fi de repulsie deoarece sunt prea aproape si exista posibilitatea unei coliziuni.

Daca vecinul pestelui este situat in cel de-al doilea cerc, atunci se considera ca distanta dintre el si pestele principal este optima; pestele principal va urma directia vecinului descriind o directie paralela.

In cel de-al treilea caz, pestele vecin este in cel mai indepartat cerc; pestele principal, care calculeaza urmatoarea miscare, va incerca sa se deplaseze in functie de pozitia vecinului sau.

Cand pestele vecin este situat in afara cercului cel mai indepartat, atunci nu va fi luat in considerare (ca in viata reala, nu poate fi vazut).

Cand nu este nici un peste in apropiere, pestele principal va adopta o strategie de cautare pentru a gasi grupul pierdut. Cand un peste are mai multi vecini, el poate sa i-a in considerare doar unul dintre ei (pe baza factorului distanta si greutate primiti de la inceput de fiecare peste) [1, 2], sau i-a in considerare toti vecinii sai [3].

'Particle Swarm Optimization'

'Particle Swarm Optimization' este o metoda de optimizare bazata pe indivizi care imita comportamentul stolurilor de pasari sau roiurilor de insecte (Kennedy & Eberhart, 1995)

Caracteristici:

Indivizii din PSO au functii obiectiv

l       Ajustarile sunt asemanatoare cu incrucisarile

l       PSO este inspirat de comportamentul social, nu de selectia naturala

l       Indivizii din PSO au "memorie"

Algoritmul PSO

Fiecare particula are o pozitie curenta ( x_i ), viteza curenta ( v_i ), pozitie personala cea mai buna ( y_i ) si cea mai buna pozitie a vacinatatii ( y^_i ).

n       x_i: pozitia curenta

n       v_i: viteza curenta

n       y_i: pozitia cea mai buna personala

n       y _i: pozitia cea mai buna a vecinatatii

Initializarea:

Pentru fiecare particula, se initializeaza aleatoriu pozitiile x_i si vitezele v_i. Initial, vitezele pot fi setate la 0.

Ajustari:

l       Se evalueaza functia obiectiv a particulei, f(x_i)

l       Se actualizeaza optimul personal

l       Se calculeaza optimul social (al vecinatatii)

l       Pentru fiecare dimensiune, se actualizeaza viteza

l       Se acualizeaza pozitia curenta

l       Se repeta pasii pana este satisfacut un criteriu de convergenta

Variante:

Varianta prezentata este globala: gbest.

In varianta locala, lbest, se considera mai multe vecinatati posibil suprapuse :

y^_i se calculeaza pentru fiecare vecinatate

Abordarea lbest conduce la o diversitate mai mare, dar este mai lenta decat abordarea gbest

Parametrii:

Ponderea inertiei w defineste compromisul intre explorare si exploatare; o valoare mai mica scade viteza particulelor, de unde rezulta mai multa exploatare, iar o valoare mai mare creste viteza particulelor, de unde rezulta mai multa explorare.

Pentru a asigura convergenta algoritmului:

Viteza poate fi limitata la un V_max

Vecinatatea poate fi definita de indicii particulelor sau de pozitiile lor

Avantaje

l       PSO este un algoritm continuu, AE sunt discreti

- PSO este mai bun decat AE pe unele probleme continue de optimizare si in special pe probleme de dimensiuni mari

l       Performantele PSO nu depind de numarul de particule (trebuie doar sa nu fie prea mic)

l       PSO cu un numar redus de particule are performante comparabile cu AE cu populatii mai mari

Dezavantaje

l       Convergenta prematura

PSO gaseste solutiile mai rapid decat alti algoritmi evolutivi, dar de obicei solutia nu se mai imbunatateste in timp

particula PSO converge la un punct dintre optimul personal si optimul social

Acest punct poate sa nu fie nici macar optim local al problemei

l       Performantele depind de problema

Parametrii trebuie alesi pentru fiecare problema in parte

Bibliografie

01. Tim Hendtlass; The Particle Swarm Algorithm, Centre for Information Technology Research, Swinburne University of Technology, Australia

02. Yann Cooren, Maurice Clerc, Patrick Siarry; Initialization and Displacement of the Particles in TRIBES, a Parameter-Free Particle Swarm Optimization Algorithm, Laboratoire Images Signaux et Systeme Intelligents, LiSSi, Universite de Paris

03.Henri Luchian&Mihaela Breaban; Algoritmi genetici, Universitatea 'Alexandru Ioan Cuza' Iasi, 2006

04. Razvan-Dorel CIOARGA ; Comportament emergent in medii colaborative robotizate , Timisoara, 2006

Florin Leon,    Inteligenta artificiala. Viata artificiala, Universitatea Tehnica "Gh. Asachi" Iasi, 2005

06.Henri Luchian&Mihaela Breaban; Algoritmi genetici, Universitatea 'Alexandru Ioan Cuza' Iasi, 2006