Partea A III-A Algoritmi Genetici [PDF]

Zitiervorschau

3.8.Aplicaţii În continuare sunt prezentate câteva probleme rezolvate cu ajutorul GA, pentru diferite alegeri ale tipului de populaţie, operatorilor de variaţie şi parametrilor asociaţi acestora, mecanisme de selectare a părinţilor şi respectiv metode de schimbare a generaţiilor. 3.8.1. Rezolvarea problemei One-Max Problema One-Max este printre primele prezentate în literatura de specialitate, datorită pe de o parte simplităţii ei şi, pe de altă parte, multiplelor modalităţi de rezolvare permise, care oferă posibilitatea efectuării de comparaţii între diversele opţiuni de rezolvare (Eiben, Smith, 2003). Funcţia corespunzătoare problemei One-Max este definită pe mulţimea şirurilor binare de lungime L prin: ( )

∑

(

)

*

+

Problema este de a maximiza funcţia f. Evident optimul global este L şi este atins pentru ). În continuare sunt prezentate două implementări GA, pentru . În ambele implementări sunt considerate următoarele setări:  spaţiul genotipurilor este identic cu spaţiul fenotipurilor: * + ;  populaţia iniţială este generată aleator, dimensiunea populaţiei este 100;  operatorul de recombinare: încrucişare uni-punct, cu probabilitatea ;  operatorul mutaţie: inversarea valorii biţilor, cu probabilitatea ;  schimbul de generaţii: strict generaţional, pe baza vârstei, cu înlocuirea completă a populaţiei curente cu multisetul progeniturilor;  condiţia de oprire: maxim 100 de iteraţii sau atingerea valorii maxime, L. (

În prima variantă de implementare, selecţia părinţilor este realizată prin algoritmul SUS cu probabilitatea de selecţie din modelul FPS standard, în cea de-a doua prin metoda turneu cu dimensiune 2. La fiecare generaţie se reprezintă într-un grafic cu axa timpului următorele valori: calitatea celui mai slab membru al populaţiei, calitate celui mai bun membru al populaţiei şi calitatea medie. Următoarele funcţii MATLAB implementează prima metodă: function []=GA_SUS(dim,L,pc,pm,MNrIt); [pop]=genereaza_ini(L,dim); maxc=0;i=0; Mmax=[]; Mmed=[]; Mmin=[]; while((maxc