analiza comparativa a algoritmilor de optimizare multicriteriala vs algoritmi bazati pe tehnici de...

7/27/2019 Analiza comparativa a algoritmilor de optimizare multicriteriala vs algoritmi bazati pe tehnici de inteligenta artificiala

1/14

Dumitrescu Sorin Alexandru, 314AC

Analiza comparativa a algoritmilor de optimizare multicriteriala (OM)

vs

algoritmi bazati pe tehnici de inteligenta artificiala (TIA)

Introducere

Viata este plina de alegeri si decizii. (Phil Rich)

Luarea de decizii inseama mai mult decat a inchide ochii si a selecta o varianta,

sau a lasa alegerea in voia unui joc al sortii. Aceasta presupune a avea in vedere a

numerosi factori care vor influenta din prima instanta, sau in viitor, cursul evenimentului

radacina si/sau a unuia sau mai multor evenimente declansate de precedentul.

Inca din cele mai vechi timpuri, omul a aspirat sa isi automatizeze viata, din nevoia

de a evita munca repetitiva. Inevitabil, s-a nascut conceptul de optimizare.

Ce inseamna optimizarea?

Optimizarea reprezinta procesul de selectare, din multimea solutiilor posibile ale

unei probleme, a acelei solutii care este cea mai satisfacatoare in raport cu unul sau maimulte criterii predefinite. Acest proces implica existenta a 3 componente:

O problema tehnica;

Existenta mai multor solutii pentru aceeasi problema;

Unul sau mai multe criterii de selectare a solutiei optime.

7/27/2019 Analiza comparativa a algoritmilor de optimizare multicriteriala vs algoritmi bazati pe tehnici de inteligenta artificiala

2/14

Dumitrescu Sorin Alexandru, 314AC

Prin optimizare, se doreste obtinerea de rezultate cel putin similar calitative, insa

se impune ca procesul sa fie mai optim din punct de vedere financiar, al timpului, al

complexitatii, sau al oricarui alt factor relevant pentru procesul in cauza.

Desigur, optimizarea fara niciun efect negativ advers, este dificil de obtinut. Ca

exemplu, putem aminti de strategia chineza a procesului de productie:

calitate sub media internationala;

costuri substantial scazute;

care, in final, conduc catre beneficii financiare, surprinzator sau nu, extrem de

avantajoase.

Orice proces presupune existenta unul algoritm dupa care va functiona.

Ce reprezinta un algoritm?

Un algoritm este o metoda de calcul alcatuita din pasii necesari solutionarii unei

probleme. Implicit, procesul de optimizare se bazeaza pe algoritmi, fiecare oferind o

alta abordare asupra subiectului.

Chiar si luarea unei decizii se face dupa un algoritm:

1. definirea problemei;2. determinarea cerintelor;3. stabilirea obiectivelor;4. identificarea alternativelor;5. definirea criteriului pe baza caruia se face alegerea;

6. selectarea unei decizii;7. evaluarea alternativelor;8. validarea solutiei.

In paginile care urmeaza, vom prezenta doua tipuri de algoritmi de optimizare:

multicriteriala (OM)

si

bazati pe tehnici de Inteligenta Artificiala (TIA).

7/27/2019 Analiza comparativa a algoritmilor de optimizare multicriteriala vs algoritmi bazati pe tehnici de inteligenta artificiala

3/14

Dumitrescu Sorin Alexandru, 314AC

Algoritmi de optimizare multicriteriala

Optimizarea multicriteriala se ocupa cu functii matematice de optimizare, care

implica eficientizarea simultana a mai mult decat a unei functii. Este o tehnica folosita

vaste domenii de activitate ca: inginerie aplicata, economie, finante si productie.

Pentru a lamuri conceptul multicriterial, vom apela la un exemplu elocvent si

anume, eficientizarea procesului de procesare a deseurilor.

Printr-o mai buna sortare a deseurilor, se poate obtine o rata mai mare a reciclarii

materialelor si in acelasi timp cresterea cantitatii de energie alternativa obtinuta prin

transformarea gunoiului nereciclabil, printre altele, in gaz metan. In linii mari, putem

compara procesul cu marirea unei fractiia

b, crescand numaratorul (a), si in acelasi

timp scazand si numitorul (b). Astfel avem de-a face cu o situatie win-win.

7/27/2019 Analiza comparativa a algoritmilor de optimizare multicriteriala vs algoritmi bazati pe tehnici de inteligenta artificiala

4/14

Dumitrescu Sorin Alexandru, 314AC

Avantaje

timp de executie redus;

precizie mare a rezultatelor;

rezultate imbunatatite.

Dezavantaje

complexitatea sporita a

algoritmului.

Ce instrumente foloseste?

Prin instrument intelegem un algoritm propriu-zis, dupa care se face

optimizarea.

7/27/2019 Analiza comparativa a algoritmilor de optimizare multicriteriala vs algoritmi bazati pe tehnici de inteligenta artificiala

5/14

Dumitrescu Sorin Alexandru, 314AC

Algoritmi multi attribute si multi-objective

Multiple attribute utility theory (MAUT)

Aceasta metoda consta in 7 pasi:

1. Identificarea entitatii care va lua decizia;

2. Identificarea problemei;

3. Identificarea optiunilor;

4. Identificarea valorilor relevante in cazul respectiv;

5. Clasarea valorilor relevante in functie de importanta;

6. Determinarea probabilitatii fiecarei optiuni de a maximiza fiecare valoare

relevanta in parte;

7. Calcului statistic.

Analytic hierarchy process (AHP)

Metoda se aplica dupa urmatorul algoritm:

1. Modelarea problemei sub forma ierarhica;

2. Stabilirea prioritatilor in cadrul ierarhiei;

7/27/2019 Analiza comparativa a algoritmilor de optimizare multicriteriala vs algoritmi bazati pe tehnici de inteligenta artificiala

6/14

Dumitrescu Sorin Alexandru, 314AC

3. Intocmirea unei ierarhii care contine principalele elemente (prioritatile);

4. Verificarea consistentei deciziilor;

5. Luarea unei decizii finale.

ELimination Et Choix Traduisant la REalit (ELECTRE)

Este o metoda folosita pentru a elimina solutii inacceptabile. Consta in doua

parti:

1. Construirea unor relatii de surclasare intre diferite actiuni, luate doua cate doua;

2. Implementarea actiunilor recomandate dupa primul pas.

Preference ranking organization method for enrichment of evaluations

(PROMETHEE)

Este o metoda care se bazeaza pe clasament. Se foloseste pentru a gasi o solutie

de compromis intre mai multi factori caracteristici problemei. Dupa compararea

criteriilor si cuantificarea lor, daca exista alternative cu valori similare, perechea de

solutii este declarata incomparabila. Prin urmare, se construiesc noi criterii care vor

ajuta la luarea unei decizii optime.

7/27/2019 Analiza comparativa a algoritmilor de optimizare multicriteriala vs algoritmi bazati pe tehnici de inteligenta artificiala

7/14

Dumitrescu Sorin Alexandru, 314AC

Algoritmi de optimizare bazati pe tehnici de inteligenta artificiala

Pentru a putea intelege aceste tehnici, vom discuta intai despre inteligenta

artificiala.

Ce este inteligenta artificiala?

Inteligenta artificiala este un domeniu de cercetare in cadrul informaticii, sau

produsul rezultat in urma acesteia.

Cea mai uzuala definitie este cea data de John McCarthy, in 1955:

[] o masina care se comporta intr-un mod care poate fi considerat inteligent, daca ar fi

vorba de un om

Cum functioneaza algoritmii bazati pe inteligenta artificiala?

Acesti algoritmi se bazeaza pe tehnici de invatare (self-learning sau external

learning), ducand astfel catre o auto-optimizare.

HAL 9000, Artificial Intelligence Entity

7/27/2019 Analiza comparativa a algoritmilor de optimizare multicriteriala vs algoritmi bazati pe tehnici de inteligenta artificiala

8/14

Dumitrescu Sorin Alexandru, 314AC

Un exemplu concret de optimizare prin AI este bijuteria industriei automotive

japoneze, automobilul creat de NISSAN, GT-R. Tehnologia care se afla in spatele

acestuia, permite atingerea unor performante inegalabile pentru aceasta categorie.

Algoritmul inteligent scaneaza carosabilul in prealabil, schimband activ

setarile suspensiei, cutiei de viteze, mecanismului de directie si programelor de

asistenta la condus, asigurand coeficienti maximi de aderenta, care permit eficientizarea

transmiterii puterii efective la roti, fara compromiterea altor factori ca masa, pret,

consum, aerodinamicitate, s.a.

Avantaje

versatilitate ridicata;

functionare autonoma;

capacitatea de invatare;

Dezavantaje

posibilitatea obtinerii de rezultate

neasteptate/nedorite

complexitate foarte ridicata a

algoritmilor.

7/27/2019 Analiza comparativa a algoritmilor de optimizare multicriteriala vs algoritmi bazati pe tehnici de inteligenta artificiala

9/14

Dumitrescu Sorin Alexandru, 314AC

Ce tipuri de algoritmi bazati pe inteligenta artificiala exista?

In continuare vom prezenta urmatoarele patru tipuri de algoritmi de optimizare:

Retea neuronala aritificiala

Logica Fuzzy

Algoritmi evolutivi

Algoritmi genetici

Reteaua neuronala artificiala

Aceasta idee porneste de la conceptul celulei specifice a sistemului nervos,

neuronul. Neuronii sunt celule individuale care comunica intre ele prin sinapse prin

impulsuri electrice. Aceasta conglomeratie de celule interconectate formeaza o retea

neuronala.

Reteaua neuronala a fost luata ca exemplu in incercarile de formare pe cale

artificiala a unei inteligente cat mai apropiata de cea naturala. Astfel s-au creat retele

neuronale artificiale, capabile sa imite procesele naturale.

Aceste retele poseda capacitatea de invatare in urma interactiunii cu mediu