inteligenta artificiala: metode de optimizare. algoritmi evolutivi

Click here to load reader

Post on 26-Jun-2015

1.028 views

Category:

Documents

3 download

Embed Size (px)

DESCRIPTION

InteligenŃă artificială4. Metode de optimizareFlorin LeonUniversitatea Tehnică „Gh. Asachi” Iaşi Facultatea de Automatică şi Calculatoare http://florinleon.byethost24.com/curs_ia.htmFlorin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htmMetode de optimizare1. Algoritmi evolutivi1.1. 1.2. 1.3. 1.4. Întâmplare şi scop Codarea problemei Operatori: selecŃia, încrucişarea, mutaŃia Optimizări multiobiectiv: NSGA-II2. Gradientul descendent şi călirea simulată 3. C

TRANSCRIPT

Inteligen artificial 4. Metode de optimizare Florin Leon Universitatea Tehnic Gheorghe Asachi din Iai Facultatea de Automatic i Calculatoare http://florinleon.byethost24.com/curs_ia.htm Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm2 Metode de optimizare 1. Algoritmi evolutivi 1.1. ntmplare i scop 1.2. Codarea problemei 1.3. Operatori: selecia, ncruciarea, mutaia 1.4. Optimizri multiobiectiv: NSGA-II 2. Gradientul descendent i clirea simulat 3. Concluzii Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm3 Metode de optimizare 1. Algoritmi evolutivi 1.1. ntmplare i scop 1.2. Codarea problemei 1.3. Operatori: selecia, ncruciarea, mutaia 1.4. Optimizri multiobiectiv: NSGA-II 2. Gradientul descendent i clirea simulat 3. Concluzii Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm4 ntmplarea poate genera lucruri interesante Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm5 ntmplarea poate genera lucruri interesante Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm6 Prezentare general Un algoritm evolutiv este o metod de cutare prin analogie cu selecia natural biologic Un AE are o populaie de soluii poteniale care evolueaz prin aplicarea iterativ a unor operatori stohastici Evoluia soluiilor mai bune se realizeaz pe baza presiunii evolutive (favorizarea soluiilor mai adaptate) Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm7 Metafora evolutiv NaturAlgoritm evolutiv MediuProblema de optimizare Indivizii care triesc n mediu Soluii poteniale fezabile Gradul de adaptare al individului la mediu Calitatea soluiei (funcia de adaptare / fitness) Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm8 Evoluia natural Speciile nu au ca scop evoluia Evoluia este doar un efect, o consecin Organismele neadaptate mor sau mor fr s se reproduc Cele care supravieuiesc suficient ca s se reproduc reuesc acest lucru tocmai fiindc sunt mai adaptate la mediu Selecia natural i selecia sexual Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm9 Operatori genetici Selecia (engl. selection) Alege un individ cu o probabilitate definit de calitatea relativ a acestuia ncruciarea (engl. crossover) Combin aleatoriu fragmente din 2 indivizi pentru a forma unii noi Mutaia (engl. mutation) Modific aleatoriu un individ nou creat Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm10 Componentele i fazele unui algoritm evolutiv Problema de rezolvat Principii de codare: gene, cromozomi Procedura de iniializare Selecia prinilor, reproducere Operatorii genetici: ncruciare, mutaie Funcia de adaptare Condiia de terminare Iniializare populaie Selecie prini pentru reproducere ncruciare Introducere copil n populaie Rezultat Mutaie da nu Stop? Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm11 Algoritmii evolutivi ialgoritmii specializai Algoritm evolutivAlgoritm specializat Vitez Efort Aplicabilitate Performan n general lent n general rapid Foarte mic De obicei mare GeneralRedus la o clas de probleme Bun,crete n timp De obicei foarte bun Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm12 Teorema No Free Lunch Oricare dou euristici sunt echivalente cnd performanele lor medii sunt considerate pe mulimea tuturor problemelor posibile Nicio euristic nu este mai bun n medie dect cutarea oarb Consecine Performane excelente, robustee mic Performane slabe, robustee mare Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm13 Teorema No Free Lunch Robustee x Eficien = Constant Generalitate x Adncime = Constant Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm14 Tipuri de algoritmi evolutivi Algoritmi genetici Codarea soluiei cu iruri de numere, de obicei binare Strategii evolutive Codarea soluiei cu vectori de numere reale Programare genetic Soluiile sunt programe (de obicei Lisp) Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm15 Metode de optimizare 1. Algoritmi evolutivi 1.1. ntmplare i scop 1.2. Codarea problemei 1.3. Operatori: selecia, ncruciarea, mutaia 1.4. Optimizri multiobiectiv: NSGA-II 2. Gradientul descendent i clirea simulat 3. Concluzii Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm16 Codarea Depinde de problem Cele mai utilizate tipuri de codare: Binar Real Cu permutri Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm17 Exemplu de codare binar Problema rucsacului: umplerea unui rucsac cu o mulime de obiecte astfel nct valoarea total a articolelor incluse s fie maximizat Constrngere: capacitatea rucsacului este limitat Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm18 Problema rucsacului wi greutatea articolului i pi profitul cnd articolul i este inclus C capacitatea rucsacului xi 1 dac articolul i este inclus, 0 altfel Obiectiv: maximizarea Constrngere:Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm19 Codarea binar De exemplu 6 articole incluse sau nu O gen = un bit (xi) Alle = valori posibile ale genei (0 i 1) Un cromozom un ir de gene (bii) Cromozomul este o soluie potenial 011001 articolele 2, 3 i 6 incluse Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm20 Decodarea:funcia de adaptare / fitness Funcia de adaptare definete problema Spune ct este de bun o soluie (ct este de adaptat un cromozom) Cromozom: 011001 Constrngere: w = 50 + 45 + 5 = 100 s C = 100 (ok) Funcia de adaptare: p = 35 + 18 + 2 = 55 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm21 Satisfacerea constrngerilor Cromozom: 111001 Constrngere: w = 100 + 50 + 45 + 5 = 200 > C = 100 Constrngerea nu este satisfcut Modaliti posibile de rezolvare: Respingerea soluiei: funcia de adaptare F = -1000000 Reduce diversitatea genetic Repararea soluiei: cte o gen 1 devine 0 pn este satisfcut constrngerea Optimizarea hibrid: nti dup greutate (-w) apoi dup profit Funcia de adaptare F = -200 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm22 Reprezentareantreag / real Multe probleme de optimizare implic numere ntregi sau reale De exemplu minimizarea funciei f(x,y) = x2 + y2 Valorile ntregi sau reale pot fi codate binar n = 6 110 r = 3.14 n domeniul [1, 10], pe 8 bii, reprezentare n virgul fix 1 0000 0000 (0) 10 1111 1111 (255) r = 3.14 (3.14 1) 255 / (10 1) = 60 0011 1100 0011 1100 3.12 (precizia crete cu numrul de bii) Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm23 Faleza Hamming O problem a codrii binare este aa-numita falez Hamming (engl. Hamming cliff) 01111111 127 10000000 128 Exist o bre n reprezentare care nu exist n problema originar Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm24 Codul Gray reflectat 00 0 0 0 10 0 0 1 20 0 1 1 30 0 1 0 40 1 1 0 50 1 1 1 60 1 0 1 70 1 0 0 81 1 0 0 91 1 0 1 101 1 1 1 111 1 1 0 121 0 1 0 131 0 1 1 141 0 0 1 151 0 0 0 00 0 10 1 21 1 31 0 00 0 0 10 0 1 20 1 1 30 1 0 41 1 0 51 1 1 61 0 1 71 0 0 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm25 Conversia Gray binar unsigned short binaryToGray(unsigned short num){return (num>>1) ^ num;} unsigned short grayToBinary(unsigned short num){unsigned short temp = num ^ (num>>8);temp ^= (temp>>4);temp ^= (temp>>2);temp ^= (temp>>1);return temp;}Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm26 Faleza Hamming engl. Hamming cliff Codare binar standard 127 01111111 128 10000000 Codarea Gray 127 01000000 128 11000000 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm27 Reprezentareantreag / real Este mai bine s codm variabilele numerice direct ca: ntregi Variabile n virgul mobil De exemplu: f(x,y) = x2 + y2 Un cromozom poate fi o pereche (x, y) = (0.12, 0.51) Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htmExemple: funcii reale de test Funcia sfer 28 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htmExemple: funcii reale de test Funcia Rastrigin generalizat 29 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htmExemple: funcii reale de test Funcia Ackley generalizat Alte funcii sunt prezentate n suportul de curs sau la adresa: http://en.wikipedia.org/wiki/Test_functions_for_optimization 30 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htmExemple: funcii reale de test Funcia Ackley generalizat 31 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm32 Reprezentarea prin permutri Unele probleme necesit ca obiectele s fie aranjate ntr-o anumit ordine Exemple: Algoritmii de sortare: ce elemente apar naintea altora Ordinea Problema comis-voiajorului (engl. Travelling Salesman Problem, TSP): ce elemente apar unul lng altul Adiacena Aceste probleme sunt reprezentate mai bine cu ajutorul permutrilor Dac avem n variabile, reprezentarea este o list de n ntregi, fiecare aprnd o singur dat Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm33 Exemplu: TSP Problema Se dau n orae S se gseasc un tur complet de lungime minim Codarea Oraele sunt numerotate 1, 2, , n Un tur complet este o permutare De ex. dac n = 5, atunci [1,2,3,4,5] i [3,4,5,2,1] sunt valide Spaiul de cutare este foarte mare Pentru 30 de orae exist30! ~ 1032 tururi posibile Florin Leon, Inteligenta artificiala, http://florinleon.bye