Tema 3 Metode de optimizare inspirate de natură

Laura Dioşan 1 Inteligenţă artificială, 2016-2017

Rezolvarea problemelor cu ajutorul algoritmilor inspiraţi de natură

Obiective Formularea problemelor ca probleme de optimizare a unei funcţii obiectiv numerice şi identificare modalităţilor inspirate de natură utile în rezolvarea lor. Specificarea, proiectarea şi implementarea metodelor de optimizare inspirate de natură

Aspecte teoretice

Rezolvarea problemelor ca proces de optimizare Tipuri de probleme de optimizare. Modalităţi de rezolvare a problemelor de căutare Identificarea soluţiei potenţiale optime: - Stabilirea componentelor problemei

o Condiţii (constrângeri) pe care trebuie să le satisfacă (parţial sau total) soluţia o Funcţie de evaluare a unei soluţii potenţiale identificareaa optimului

- Definirea spaţiul de căutare - Stabilirea strategiei de identificare a soluţiei optime în spaţiul de căutare

Termen de predare

Cerința C1 - pe loc (in cadrul laboratorului 3)

Cerința C2 - laborator 4 (Algoritmul evolutiv) și laborator 5 (PSO/ACO)

Cerinţe C1. Subalgoritmi de căutare Implementați un subalgoritm pentru un operator de căutare specific algoritmilor evolutivi. Sub-

algoritmii trebuie să respecte specificarea dată și vor fi evaluați cu ajutorul a 5 aserțiuni.

C2. Probleme de căutare Specificaţi, proiectaţi şi implementaţi o aplicaţie care să rezolve una dintre problemele de mai jos. Fiecare dintre probleme trebuie rezolvate cu cele 2 tipuri de metode precizate (un algoritm evolutiv şi un algoritm inspirat de coloniile de furnici (ACO)/inteligenţa de grup (PSO)). Aplicaţia trebuie să respecte diagrama din Figura 1 şi trebuie să permită:

- Încărcarea datelor problemei (probleme cu date deja definite de către programator, probleme cu date definite de utilizator)

- Alegerea şi parametrizarea metodei de rezolvare a problemei o alegerea parametrilor necesari algoritmului

pentru algoritmul evolutiv

dimensiunea populatiei

numarul de generatii

dimensiunea cromozomului

parametri ai selectiei

probabilitatea de incrucisare și cea de mutație

alţi parametri

Tema 3 Metode de optimizare inspirate de natură

Laura Dioşan 2 Inteligenţă artificială, 2016-2017

pentru algoritmul de tip ACO

numărul de furnici

alpha, beta

coeficientul de degradare/evaporare a feromonului

alţi parametri

pentru algoritmul de tip PSO

dimesniunea grupului de particule

viteza iniţială

tipul de vecinătate

factorul de inerţie

factorii de învăţare

- Afişarea soluţiei identificate o ilustrarea prin grafice a modului în care evoluează soluţiile de la o

generaţie/iteraţie la alta. - Precizarea performanţelor metodei de rezolvare alese

Figura 1 Diagrama de clase

Cele 2 metode de căutare vor putea fi dezvoltate astfel:

varianta 1. pe baza unui tool deja existent. Punctaj: 25p pentru cod, 10p pentru interfață și 5x5p pentru aserțiuni

varianta 2. pe baza codului complet scris de către student. Punctaj: 50p pentru cod, 10p pentru interfață și 5x10p pentru aserțiuni

Studenţii pot alege care variantă de aplicaţie doresc să o realizeze.

Sisteme disponibile care implementează algoritmi evolutivi, ACO si PSO:

Tema 3 Metode de optimizare inspirate de natură

Laura Dioşan 3 Inteligenţă artificială, 2016-2017

1. AIMA http://code.google.com/p/aima-java/

2. FAIF http://faif.sourceforge.net/index.html

3. GAUL http://gaul.sourceforge.net/

4. KanGAL code: http://www.iitk.ac.in/kangal/codes.shtml

5. PSO http://clerc.maurice.free.fr/pso/

6. PSO toolbox http://psotoolbox.sourceforge.net/

7. ACO http://iridia.ulb.ac.be/~mdorigo/ACO/aco-code/public-software.html

1. Expozitie bijuterii – AE şi PSO

Un bijutier trebuie sa participle la o expozitie cu vanzare in strainatate. Fiecare bijuterie pe care vrea sa o vanda are un anumit gramaj de metal pretios si un anumit pret. Bijuteriul trebuie sa calatoreasca cu avionul, asa ca limita maxima de bagaj este de 20 kg. Ajutati-l pe bijutier sa aleaga acele bijuterii care ii vor aduce un castig cat mai mare (in ipoteza ca el va vinde toate exponatele).

2. Zvonuri – AE şi PSO

Membrii unei asociatii culturale sunt organizati intr-o retea (unii membrii au relatii cu alti membrii, fiecare membru avand cel putin o relatie cu un alt mebru – altfel el neputand face parte din retea). Fiecare membru va trebui instiintat despre un anumit eveniment. Sa se identifice reteaua minimala de conexiuni utile intre mebrii asociatiei astfel incat orice mebru sa fie informat despre eveniment.

3. Turn – AE şi ACO

Se dau n cuburi care au fiecare fata colorata cu o anumita culoare (din 4 culori disponibile). Se cere sa se aranjeze cuburile pe o coloana (sa se formeze un turn cu cele n cuburi) astfel încât toate cele 4 fete ale coloanei (turnului) sa fie colorate cu cate o singura culoare.

4. Puzzle – AE şi PSO

Se da un set de cuvinte W={w1,...,w2n} astfel incat fiecare cuvant wi este o secventa de caractere (un string). Sa se construiasca un puzzle de cuvinte incucisate folosindu-se toate cele 2n cuvinte. Ex : Pt n=3 si W={AGE,AGO,BEG,CAB,CAD,DOG} puzzle-ul ar fi:

C A B

A G E

D O G

5. Triunghi monochromatic – AE şi PSO

Se da un graf neorientat G(V,E) cu V multimea nodurilor si E multimea muchiilor. Sa se gaseasca o partitionare a muchilor din E in doua submultimi disjuncte E1 si E2 astfel incat oricare din cele 2 grafe G1(V,E1) or G2(V,E2) sa nu contina un triunghi (o multime de 3 noduri diferite u,v,w astfel incat {u,v}, {u,w}, {v,w} sa fie toate muchii in acelasi graf). Ex.:

1

2

3

4

5 1

2

3

4

5 1

2

3

4

5

Tema 3 Metode de optimizare inspirate de natură

Laura Dioşan 4 Inteligenţă artificială, 2016-2017

Graful G(V,E) Graful G1(V,E1) Graful G2 (V,E2) V= {1,2,3,4,5}, E={(1,2), (1,3), (1,4), (1,5), (2,3), (3,4), (3,5), (4,5)} Pentru acest graf initial G, o solutie poate fi : E1 = {(1,2), (1, 4), (3,5), (4,5)} si E2 = {(1,3), (1,5), (2.3), (3,4)}.

Atentie E1 U E2 = E şi E1 ∩ E2 = !!! Dar E1 = {(1,2), (1, 4), (3,4), (3,5), (4,5)} si E2 = {(1,3), (1,5), (2.3)} nu poate fi solutie intrucat in graful G1 corespunzator lui E1 se formeaza un triunghi intre nodurile 3, 4 si 5.

6. Piramida – AE şi ACO

Se considera n cuburi de laturi si culori cunoscute. Sa se alcatuiasca turnurile din n cuburi astfel incat fiecare turn sa aiba stabilitate (sa nu fie asezat un cub mai mare peste unul mai mic) si sa nu existe doua cuburi consecutive de aceeasi culoare.

7. Rebus – AE şi ACO Se considera un rebus de dimensiuni p x q care trebuie completat cu n cuvinte pe orizontală. Se dau coordonatele pozitiilor negre. De asemenea se mai da un dictionar cu cele n cuvinte care trebuie amplasate corect în rebus, astfel încât fiecare cuvânt sa fie folosit o singura data. Se cere o solutie.

8. Submultimi disjuncte – AE şi PSO

Se considera o multime A cu n elemente si S1, S2, ..., Sn, n submultimi ale lui A. Se cere sa se pertitioneze A in doua submultimi disjuncte D1 si D2 astefel incat fiecare submultime Si (i = 1, n) sa nu fie inclusa nici in D1 nici in D2.

9. Subgrafe – AE şi PSO

Se considera un graf neorientat G(V,E) cu 2n noduri (V este multimea nodurilor si E multimea muchiilor). Sa se partitioneze nodurile grafului G in 2 multimi disjuncte V1,V2, fiecare continand exact n noduri cu conditia ca intre cele n noduri ale unui graf sa existe muchii (fiecare multime V1, respectiv V2 să fie un graf conex).

10. Procese – AE şi ACO Se dau p procese şi m procesoare pe care trebuie executate aceste procese (p>m). Se cunosc duratele d(i,j) fiecărui proces i (i=1,...,p) pe un procesor j (j=1,...,m). Să se planifice cele p procese pe cele m procesoare astfel încât timpul de terminare a proceselor să fie cât mai mic. Un procesor poate executa un singur proces o dată.

11. Problema transportului – AE şi ACO

Se dau 2 mulţimi F şi L (facilităţi şi locaţii) de mărimi egale, o funcţie pondere w: F × F → R şi o funcţie distanţă d : L × L → R. Să se identifice o atribuire a facilităţilor pe locaţii f: FL astfel

încât să se minimizeze funcţia de cost

Fba

bfafdbaw,

))(),((),( .