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

Download Analiza comparativa a algoritmilor de optimizare multicriteriala vs algoritmi bazati pe tehnici de inteligenta artificiala

Post on 14-Apr-2018

239 views

Category:

Documents

1 download

Embed Size (px)

TRANSCRIPT

  • 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