Analiza Convergentei Algoritmilor Genetici

UNIVERSITATEA DIN CRAIOVA

FACULTATEA DE ȘTIINȚE

SPECIALIZAREA INFORMATICĂ

LUCRARE DE LICENȚĂ

Îndrumător științific: Absolvent:

Prof.univ.dr. Iancu Ion Vasilică Mircea Ionuț

CRAIOVA

2016UNIVERSITATEA DIN CRAIOVA

FACULTATEA DE STIINTE EXACTE

SPECIALIZAREA INFORMATICA

Analiza convergenței algoritmilor genetici

Îndrumător științific: Absolvent:

Prof.univ.dr. Iancu Ion Vasilică Mircea Ionuț

CRAIOVA

2016

Noțiuni introductive

Structura lucrării

Motivație

Introducere algoritmi genetici

Principalele noțiuni care permit analogia între rezolvarea problemelor de căutare și evoluția naturală sunt următoarele:

Cromozomul este o mulțime ordonată de elemente, numite gene ale căror valori determină caracteristicile unui individ. În genetică, pozițiile pe care se află genele în cadrul cromozomului se numesc loci, iar valorile pe care le pot lua se numesc alele. În calculul evolutiv cromozomii sunt vectori ce conțin codificarea unei soluții potențiale și sunt numiți indivizi. Astfel, genele nu sunt altceva decât elementele acestor vectori.

Populația. O populație este constituită din indivizi care trăiesc într-un mediu la care trebuie să se adapteze. În calculul evolutiv, un individ este de cele mai multe ori identificat cu un cromozom și reprezintă un element din spațiul de căutare asociat problemei de rezolvat.

Genotipul este ansamblul tuturor genelor unui individ sau chiar a întregii populații. În calculul evolutiv genotipul reprezintă codificările corespunzătoare tuturor elementelor populației.

Fenotipul este ansamblul trăsăturilor determinate de către un anumit genotip. În calculul evolutiv fenotipul reprezintă valorile obținute prin decodificare, adică valori din spațiul de căutare.

Generația este o etapă în evoluția unei populații. Dacă vedem evoluția ca un proces iterativ în care o populație se transformă în altă populație atunci generația este o iterație în cadrul acestui proces.

Selecția. Procesul de selecție naturală are ca efect supraviețuirea indivizilor cu grad ridicat de adecvare la mediu (fitness mare). Același scop îl are și mecanismul de selecție de la algoritmii genetici și anume de a favoriza supraviețuirea elementelor cu grad mare de adecvare. Aceasta asigură apropierea de soluția problemei întrucât se exploatează informațiile furnizate de către cele mai bune elemente ale populației. Unul dintre principiile teoriei evoluționiste este acela că selecția este un proces aleator și nu unul determinist. Acest lucru este întâlnit în majoritatea mecanismelor de selecție utilizate de către algoritmii evolutivi.

Fitness-ul. În evoluția naturală fiecare individ al populației este adaptat mai mult sau mai puțin mediului iar unul dintre principiile teoriei evoluționiste este acela că supraviețuiesc doar cei mai buni indivizi. Fitness-ul (adecvarea) este o măsură a gradului de adaptare a individului la mediu. Scopul evoluției este ca toți indivizii să ajungă la o adecvare cât mai bună la mediu, ceea ce sugerează legătura între un proces de evoluție și unul de optimizare. În calculul evolutiv, gradul de adecvare al unui element al populației este o măsură a calității acestuia în raport cu problema care trebuie rezolvată. Dacă este vorba de o problemă de maximizare atunci gradul de adecvare va fi direct proporțional cu valoarea funcției obiectiv (un element este cu atât mai bun cu cât valoarea acestei funcții este mai mare).

Noțiunile de adecvare și evaluare sunt folosite în general cu același sens; totuși se poate face o distincție între ele. Funcția de evaluare, sau funcția obiectiv, reprezintă o măsură a performanței în raport cu o mulțime de parametri, în timp ce funcția de adecvare transformă această măsură a performanței în alocare de facilități reproductive. Evaluarea unui șir reprezentând o mulțime de parametri este independentă de evaluarea altor șiruri. Adecvarea unui șir este, însă, definită în raport cu alți membri ai populației curente.Funcția de evaluare și codificarea sunt, de obicei, singurele componente ale algoritmilor genetici care depind de problema de rezolvat. Un algoritm genetic, folosit pentru rezolvarea unei probleme de optimizare, poate fi privit ca o ''cutie neagră'' cu o serie de butoane de control reprezentând diverși parametri. Ieșirea cutiei negre este valoarea unei funcții indicând în ce măsură o anumită distribuție a parametrilor rezolvă problema dată.

Structura unui algoritm evolutiv este următoarea :

Procedure AE

Begin

t := 0

inițialiyare P(t)

evaluare P(t)

while (not condiție terminare) do

begin

t := t +1

selectare P(t) din P(t-1)

modificare P(t)

evaluare P(t)

end

end

Ce sunt algoritmii genetici?

Algoritmii genetici sunt tehnici adaptive de căutare euristică, bazate pe principiile geneticii și ale selecției naturale, enunțate de Darwin (supraviețuiește cel mai bine adaptat). Mecanismul este similar procesului biologic al evoluției. Acest proces posedă o trăsătură prin care numai speciile care se adaptează mai bine la mediu sunt capabile să supraviețuiască și să evolueze peste generații, în timp ce acelea mai puțin adaptate nu reușesc să supraviețuiască și cu timpul dispar, ca urmare a selecției naturale. Probabilitatea ca specia să supraviețuiască și să evolueze peste generații devine cu atât mai mare cu cât gradul de adaptare crește, ceea ce în termeni de optimizare înseamnă că soluția se apropie de optim. Ca și aplicații practice, algoritmii genetici sunt cel mai adesea utilizați în rezolvarea problemelor de optimizare, planificare ori căutare. Condiția esențială pentru succesul unei aplicații cu agenți inteligenți este ca problema de rezolvat să nu ceară obținerea soluției optime, ci să fie suficientă și o soluție apropiată de optim.

Analizând un AG este complicat in funcție de domeniul de aplicare și lipsa noastră de înțelegere a cartografiei între punctul nostru de vedere al domeniului de aplicare și punctul de vedere al AG privind același domeniu. Punctul de vedere AG al domeniului este implicit în codificarea aleasa. Cu toate acestea, comportamentul general este previzibil și poate fi dedus din prelevarea de probe din sistemul adecvat de măsurare.

Analiza informațiilor sintactice din codificare, ne oferă o cantitate surprinzătoare de cunoștințe. Am derivat o limită superioară a complexității timpului de la luarea în considerare a efectelor de derivă pe frecvența alelă. Aceasta a condus la sugestii promițătoare pentru atenuarea problemelor de convergență prematură și de înșelăciune. Apoi, de la un model de efect de selecție și mutație asupra comportamentului algoritmilor genetici, noi am fost capabili de a aproxima cele două soluții caracteristice convergenței pentru spațiile de căutare statice.Bariere cu privire la o limită superioară a distanței hamming medii a unei populații la convergența. În plus față de furnizarea termenelor, distanța hamming medie a populației denotă, de asemenea, cantitatea de muncă rămasă.

Cantitatea de muncă posibilă prin GA, indică media fitness-ului la convergență.

În cadrul modelului nostru, combinând predicția fittnes-ului cu predicția medie Hamming ne dă o idee despre cât de mult este posibil un progres cu un AG, împreună cu limite cu privire la cât de multă muncă din cea rămasă se poate face. Acesta din urmă este deosebit de important atunci când includem mutația. Media fitness-ului previzibilă indică cât progres este posibil, dar media hamming este cea care denotă munca rămasă.

În prezent, lucrăm la o analiză mai aprofundată a varianței care să conducă la o mai bună încredere estimată pe previziunile noastre. Plănuim extinderea modelului nostru la funcțiile multimodale dinamice și operatori genetici speciali. Noi presupunem că operatorii de încrucișare care nu păstrează distanța Hamming pot fi modelați ca o perturbare a procesului de selecție și așa încorporați în modelul nostru.

În cele din urmă, am dori să sugerăm utilizarea proprietăților sintactice ale spațiului hamming în rafinarea noțiunii noastre a traiectoriei algoritmului genetic prin spațiu de căutare. Acest lucru ar trebui să conducă la comparații mai ușoare cu alte metode de căutare.

Prezicerea timpului de convergență a Algoritmilor Genetici

Abstract

Optimizarea prin algoritmi genetici aduce , de cele mai multe ori, convergența prematură, în special în cazul problemelor multimodale. În această lucrare, propunem și testăm două mecanisme de evitare a convergenței premature a algoritmilor genetici prin prezentarea diversității populației în două feluri diferite. Acestea reprezintă aplicația dinamică a mai multor operatori genetici, bazați pe media progresului și reinițializarea parțială a populației. Mecanismele au fost testate prin implementarea acestora în algoritmul NSAG_II, aplicat unuia dintre cele mai dificile probleme de test a job shop scheduling-ului, ft10. Analiza comparativă între noul algoritm și NSAG_II în absența mecanismelor prezentate, alături de un elitist și canonic algoritm genetic, demonstrează gradul de utilizare a ambelor mecanisme propuse.

Cuvinte cheie: algoritmi genetici, optimizare, progresul operatorilor genetici, job shop scheduling.

Scurt istoric

În ultimii treizeci de ani, algoritmii genetici și hibrzii acestora au fost aplicate în diferite probleme de optimizare, datorită avantajelor multiple: caracteristici derivate gratuit, prepararea fără dificultate a modelului de optimizare, natura paralelă a căutării etc.

O problemă crucială pentru succesul algoritmilor genetici, în special pentru probleme dificile, este evitarea convergenței premature a algoritmului pentru regiunile suboptimale.

Convergența prematură a algoritmilor genetici ia naștere atunci când genele unor indivizii cu potențial ridicat ajung să domine populația, fiind constrânse să ajungă la un optim local. În acest caz, operatorii genetici nu pot produce mai mulți descendenți decât părinții (Fogel, 1994); abilitatea algoritmului de a continua căutarea pentru soluții mai bune este redusă substanțial.

Pentru a evita convergența prematură într-un algoritm genetic este negesară apărarea diversității populației pe durata evaluării. Cu alte cuvinte, diversitatea populației asigură evitarea convergenței premature. Printre metodele folositele amintim: selecție restrictivă, aplicarea dinamică a mutației, constrângeri pentru probabilitatea mutațiilor, prelevarea de probe universale stocastice, valabilitatea fittnes-ului, reinitializarea parțială a populației, gruparea metodică a indivizilor, cuplarea restrictivă, elitism, simbiogenetica, tehnici de conservare a speciilor, clasament bazat pe dominația lui Pareto, studiu local de diversitate.

Toate aceste metode sunt euterice prin definiție și efectele acestora variază pentru diferite probleme.În viață de zi cu zi, aceste metode nu sunt adecvate și dificil de aplicat.

Un alt aspect cheie este caracterul dublu al diversității populației:

-diversitatea în spațiul obietivului

-diversitatea în parametrii spațiului.

Pentru anumite probleme nu este suficient prezervarea diversității într-un anumit spațiu, pentru altele, un algoritm genetic bun trebuie să mențină diversitatea populației în ambele spații.

Două imperative sunt legate de convergența prematură:

-Identificarea întâmplării problemei de convergență prematură prin diferite măsurători.

-Evaluarea măsurii.

Măsurătorile pentru detectarea convergenței premature sunt de fapt, măsurători pentru nivelul de degenerație a populației. Srinivas și Patnaik(1994) folosesc că și măsurător, diferența dintre media condiției fizice și condiția fizică optimă. În funcție de diferență, ei variază adaptiv probabilitățile mutației și încrucisării. Autorii propun că și măsurătoare statică, distanță medie Hamming dintre indivizi și variația distanței Hamming, ambele fiind independente de numărul genelor și dimensiunea populației.

În această lucrare, propunem două mecanisme pentru păstrarea diversității populației, ambele bazate pe progresul mediu al operatorilor genetici pe durata evaluării.

Mecanisme folosite pentru evitarea convergenței algoritmilor genetici

Mecanismele prezentate sunt:

-Aplicația dinamică a încrucisării și operatorilor mutaționali

-reinițializarea parțială a populației

Scopul acestora este urmărit prin două metode diferite. Prima metodă acționează încet, de la începutul evoluției până la sfârșitul acesteia. Mai precis, două seturi de operatori ( pentru stagiul încrucisării și pentru stagiul mutației) sunt folosite în loc de doi operatori pentru încrucișare și mutație. La fiecare generație, un operator din fiecare set este aplicat dinamic, bazat pe probabilitatea selecției care depinde de media progresului.

Reinițializarea parțială a populației este aplicată doar atunci când riscul convergenței premature apare. Anterior, reinițializarea a fost aplicatată pentru segmentele populației, după o perioadă limitată de timp sau atunci când căutarea stagna.Pentru prima dată, Fonseca și Fleming inserează în populație, la fiecare generație, un număr mic de imigranți, generați aleator.

Aplicarea dinamică a operatorilor de incrucișare și mutație

Aplicarea dinamică a Operatorilor de Încrucișare și Mutație

Această ideea a fost implementată deoarece fiecare operator genetic are un comportament inerent, prin cosecință o rată de progres inerentă. În plus, caracteristicile diferite ale problemelor determină nivelul de adecvare al opetorilor.

Pentru o codare genetică, unii opeatori funcționează mai bine la începutul evoluției, iar alții după ce găsesc regiuni optime.Cu alte cuvinte, unii operatori au capacitatea de a explora sau de a exploata mai bine problema spațiului. În funcție de distanță, complexitatea instanței, putem impune un anumit raport explorare/exploatare.

Pentru opeatorii de încrucișare, autorul a proiectat o formulă pentru progres, folosind raportul explorație/exploatare precis. Această formulă fucționează pentru atât obiectivele unice cât și pentru obiectivele multiple ale problemelor, luând în considerare relația de dominanță între părinți și descendenți.

Pentru a muta progresul unui operator × de încrucișare aplicat la cuplul părinților(P1,P2) pentru care descendetul D este produs, vom folosi următoarea formulă:

Unde t este generația curentă, G este numărul maxim de generații, iar k1,k2 sunt parametrii care aplică vitezăa de reducere a progresului pe timpul evoluției (de la 1 până la 0.5 dacă D domină un părinte, respectiv de la 0.5 la 0 dacă D este dominat de cel puțin un părinte). În consecință, valorile mici ale k1 respectiv k2 aduc o explorare mai largă a spațiului de căutare la începutul evoluției. Motivul este acela că algoritmul interzice o marire masivă a indivizilor de calitate ridicată.

A treia condiție în formula(1) este întrunită atunci când D este dominat de ambii părinți sau D este dominat de unul dintre părinți și nu există o relație de dominație cu celălalt părinte, sau atunci când D este dominat de către unul dintre părinți iar D domină celălalt părinte.

Filiala „altfel” a acestui caz cu referire la D nu este validă, dacă utilizatorul nu permite o astfel de aplicație pentru operator.

În figura1 prezentăm spațiul de căutare a obiectivelor duale în problema minimalizării, structurată de relația dominantă dintre D și părinții P1 , P2 atunci când între cei doi părinții nu se manifestă relație de dominație. Formulă(1) este deasemenea valida dacă unul dintre părinți domină celălalt părinte.

Daca un operator de incrucișare produce doi descendenți, formula (1) se aplica de două ori, pentru fiecare descendent.

Valoarea parametrilor k1 si k2 este legată de ½ și G/2.

Pe durata evoluției, pentru fiecare aplicare a operatorului × unde descendentul corespondent domină un parinte, valoarea π(×) se reduce in mod constant, k1/G, pană când ajunge la generația G/(2k1). După aceea , progresul devine invariabil 0.5. Așadar, cu cât k1 este redus, cu atât progresul converge la valoarea de 0.5. În caz extrem, dacă k1= ½ atunci π(×) se reduce in mod constant pană la ultima generație, cand aceasta va fi 0.5. Dacă k1 = G/2, incepând cu a doua generație, π(×) va avea constant valoare de 0.5 .

Aceleași comentarii sunt valabile pentru parametrii k2. Pe durata evoluției, pentru fiecare aplicare a operatorului × unde descendentul corespondent acestuia, este dominat de cel puțin unul dintre părinți, progresul operatorului se reduce în mod constant, k2/G, până când se ajunge la generația G/(2k2). După ce acesta ajunge invariabil 0.

Dacă descendenții mai slabi decât părinții sunt descurajați, k2 trebuie să aibă o valoare mare (de exemplu G/3 ) Dar acest lucru va micșora căutarea, deoarece progresul lui × se reduce pe timpului evoluției și operatorul va avea șanse mai mici de a fi folosit pe viitor.

Valorile parametrilor k1 și k2 sunt reglate din perspectiva gradului si a calității spațiului de explorare. Pentru o explorare maximală, prin urmare, o diversitate maximală, ambii parametrii sunt setați la o valoare mică (având tendința spre ½). Desigur, valoarea lui k1 nu trebuie să fie mai mare decât valoarea lui k2, deoarece nu vrem să pierdem descendenții care domină unul dintre părinți, și să păstram descendenții dominați de cel puțin un părinte.

Pentru operatorul mutațional, am modificat formula [1] pentru atribuirea progresului. În [1], Basseur a luat în considerare progresul constant (1/2) dacă soluția anterioară și soluția posterioară operatorului aplicat nu se domina una pe alta [1]:

unde M(s) este candidatul-soluție care rezultă după aplicarea lui ×.

În această lucrare vom atribui o valoare de progres operatorului mutațional dacă s și M(s) nu pot fi comparați. Această valoare depinde de parametrul k3 care impune viteză de convergență a progresului lui × până la valoarea de 0.5.

Așadar, progresul operatorului mutațional ×, aplicat candidatului-soluție s, este determinat de formula:

Pe durata evoluției, la fiecare aplicare a operatorului ×, unde M(s) este valid și s , respectiv M(s) nu se domină unul pe celălalt, valoarea π(x) se reduce constant cu valoare k3/G, până la generația G/(2 k3). După aceea, devine invariabilă cu valoarea de 0.5. Ca și în cazul altor parametrii (k1 și k2), o valoare redusă a k3 permite o exploatare mai vastă a spațiului de căutare. Motivul este că permitem să intre în populație mai mulți indivizi cu aceeași etichetă cu cea a indivizilor asupra cărora a fost aplicat operatorul.

Procedura de selecție pentru aplicarea operatorilor genetici

La fiecare stagiu a încrucișării și mutației, în fiecare generației, operatorul care urmează a fi aplicat este selectat în funcție de probabilitatea selecției tuturor operatorilor. Pentru această, vom comuta pentru fiecare operator media progresului, pentru fiecare aplicare, de la începutul evoluției, folosind formula [1]:

Unde πi(×) este progresul lui × la aplicarea i și ||x|| este numărul de aplicare a operatorului ×.

După fiecare aplicare a operatorilor, probabilitatea selecției este actualizată, folosind formulă [1]:

Unde Opi, este un operator genetic din clasa x, având n elemente, și Ox ϵ (0,1) este valoarea minimă pentru probabilitatea selecției a fiecărui operator. Acest lucru permite păstrarea tuturor operatorilor, dar nu și pe aceia cu rezultate slabe.

Inițial, fiecare operator de încrucișare și mutațional este atribuit unei probabilități de selecție, egală cu valoarea 1/n. De exemplu, dacă lucrăm cu doi operatori de încrucișare, la prima generație, probabilitatea selecției este 0.5. În [1], autorii au folosit ca și probabilitatea selecției valoarea 1/(n*P mutație) , unde P mutație este raportul mutațiilor.

Ținând cont de probabilitatea selecției la ultima generație, putem conclude care operator mutațional și de încrucișare este cel mai benefic pentru aplicația dorită.

Pentru implementarea dinamică a operatorilor genetici, vom folosi varianta actualizată a probabilității într-o schemă tip ruletă. Vom sorta probabilitățile operatorilor mutaționali și de încrucișare și, în funcție de o valoare aleatorie, vom selecta operatorul a cărui probabilitate este plasată în regiunea selectată. În consecință, cu cât progresul operatorului este mai înaintat, cu atât șansele de selectare ale operatorului sunt mai mari. Acest algoritm va fi folosi cei mai buni operatori mai des.

Vom adopta principiul ruletei deoarece este o schemă elitistă, unde vom selecta operatorul cu cea mai mare probabilitate de selecție, va elimina din ecuație operatorii mai slabi, păstrându-i pe cei mai buni.

Avantajele aplicării dinamice a operatorilor genetici sunt:

-detectarea celui mai bun operator genetic pentru o instanța specifică

-promovarea rezultatelor benefice a operatorilor disponibili

-lărgirea căutării genetice fără a pierde direcția operatorilor, deoarece aceștia au tendința de a oferi rezultate diferite.

-posibilitatea de a influență explorarea spațiului (cu ajutorul valorilor k1,k2,k3).

Chiar dacă, în această lucrare, au fost folosiți doi operatori de încrucișare (UX,PPX) și trei operatori mutaționali (frame-shift, translocation și inversion), mecanismele prezentate pot fi aplicate pentru un număr nedefinit de operatori genetici.

Reinițializarea partial a populației

Acest mecanism a fost propus că un mecanism de diversificare aplicat de fiecare dată când

riscul convergenței premature ajunge la un nivel critic. Această condiție este îndeplinită atunci când, în generația curentă, media progresului fiecărui operator este mai mică decât un prag cu valoarea pMin ϵ [0,1], stabilită înainte de startul evoluției. Valoarea plin este aplicată în relație cu valorile lui Ox.

Reinițializarea constă în înlocuirea unei părți a noii populații cu indivizi generați aleatoriu, într-o proporție setată după algoritmul pReinit.

În plus, dacă reinițializarea este efectuată de 300 de ori într-un ciclu, evoluția va fi oprită, datorită criteriului stop, stabilit inițial. Motivul fiind, un număr mare de reinițializări semnifică șanse minimale de a identifica soluții mai bune decât cele curente.

Implementarea a două mecanisme în algoritmul NSGA_II

Aceste două mecanisme au fost implementate în algoritmul NSGA_II (Algiritmi Genetici de sortare nedominanti) [5], unul dintre cei mai buni algoritmi genetici creat pentru probleme complexe. Noul algoritm a fost numit NSGA_II DAR( Dynamic Application of genetic operators and population parțial Reinitialization).

Pentru a valida mecanismele propuse, comparăm rezultat obținut de algoritmul NSGA_ÎI și algoritmul NSGA_II DAR într-o problemă cunoscută din clasa JSSP( Job Shop Scheduling Problem).

Algoritmul NSGA_II, proiectat de către Debetal. în anul 2000 pentru problemele dificile cu obiective multiple, sortează populația în funcție de nivelul non-dominator, fiecare soluție fiind comparată cu toate celelalte soluții dacă acestea sunt dominate.

În acest fel sunt construite una câte una , fiecare având în compoziția lor indivizi care nu sunt dominați.

NSGA_II folosește că mecanism de prezervare al diversității un operator de comparare al aglomerării de distanță, care ghidează procesul selecției către un adevărat optimizat Pareto-scop, prin favorizarea soluției în regiunile mai puțin dense din fiecare obiectiv.

Acest algoritm folosește o selecție binară tip turneu (campionat), unde criteriul selecției este bazat pe acest operator.

Pseudocodul algoritmului NSGA_II DAR este următorul :

Soluția finală pentru toți algoritmii reprezintă toți indivizii, structurați diferit, având valoarea cea mai bună.

Rezultatele simularii

În acestă lucrare, aceste mecanisme, implementate în algoritmul NSGA_II DAR, au fost testate în testul ft10, una dintre cele mai dificile JSSP, fiind definită astfel:

Aici sunt declarate constrângerile cumulative a JSSP: constrângerea non-preemțiune, constrângerea precedentului, și constrângerea de capacitate (O mașinărie procesează un operator pe rând). Ultima este înțeleasă din Imput Dată.

Obiectivul: minimalizarea programului, numit:

C*max = min(Cmax)

Formulă pentru program implică descrierea detaliată a encodării genetice pentru JSSP. Scopul acestei lucrări fiind alalizarea comparativă a perforației soluției. Am ales să nu prezentăm structura soluției, această fiind disponibilă la cerere.

Experiență arată că JSSP nu este numai dificil pentru aplicarea NP, dar este foarte dificil pentru a rezolva probleme euristice cu acesta. În aceste circumstanțe, evitând convergență prematură a algoritmului în regiunile suboptimale este o cerință de bază a JSSP.

În testul ft10 [2], 10 joburi, toate formate din 10 operațiuni, trebuie programate pe 10 mașinării. Soluțiile candidatului sunt formate de doar 100 de gene, dar nivelul de complexitate a acestuia este destul de ridicat. Este una dintre cele mai dificile probleme JSSP. Cea mai bună soluție este aceea de makespan 930.

Algoritmul a fost efectuat de 5 ori pentru fiecare valoare a parametrilor, prezentat în tabelul 1.

Tabelul 1.Valorile parametrilor folosiți pentru simulări.

Calitatea soluției este interpretată din mai multe puncte de vedere: cea mai bună performanță (C*max) obținută în 30 de teste, media performanței, ce mai nesatisfăcătoare performanță, variația C*max și timpul de funcționare pe generație.

Pentru a evalua utilitatea a noilor mecanisme, vom compara rezultate obținute de noul algoritm, NSGA_II DAR, și alți trei algoritmi genetici: algoritmi genetici canonici, un algoritm genetic elitist și NSGA_II folosit în absența acestor mecanisme.

Studiul comparativ (vezi tabelul 2) arată algoritmul NSGA_II DAR este cel mai eficient, luând în considerare primii trei indici de performanță. Acesta a obținut soluția cu cel mai bun scor – makespan 1013.

Tabelul 2. Măsuri de performanță pentru testul ft10 de instanță

Variația duratei de viață, care este un alt măsurător al diversității soluției, este gândit mai bine pentru NSGA_ÎI. Cel mai bun timp de funcționare este obținut de către algoritmi genetici canonici, cel mai simplu dintre aceștia, dar această informație are sens dacă avem nevoie de un timp rapid de funcționare și acceptăm calitatea slabă a soluției.

Concluzii

În această lucrare am prezentat două mecanisme de evitare a convergenței premature a algoritmilor genetici. Acestea reprezintă aplicări dinamice a operatorilor mutaționali și de încrucișare și reinițializarea parțială a populației. Teste numeroase efectuate pentru a evalua calitatea dovedesc rolul benefic al ambelor mecanisme folosite pentru diversificarea populației.

Aplicarea dinamică a operatorilor genetici își atinge scopul pe durata evaluării, producând avantaje suplementare simultan: identificarea operatorilor adecvați și promovarea efectelor benefice tutoror operatorilor disponibili.

Reinițializarea parțială a populației, își atinge scopul numai în momentele cruciale, atunci când riscul convergenței premature este ridicat. De aceea, într-o problemă cu grad de dificultate mai puțin dificil, dacă riscul nu apare, indivizii nu pot fi înlocuiți de către noi indivizi generați aleatoriu dacă nu este necesar.

Îmbunătățirea adusă algoritmilor genetici de către aceste două mecanisme este validată de către rezultatul analizei comparative în problema ft10 JSSP; noul algoritm (NSGA_II cu cele două mecanisme, NSGA_II DAR) este pus împotriva a altor trei algoritmi genetici: algoritmi genetici canonici, un algoritm genetic elitist, și NSGA_II în absența celor 2 mecanisme. Din perspectiva celor mai importante puncte – cel mai bun rezultat obținut în 30 de teste, media performanței și ce mai mai slabă performanță a soluției – noul algoritm fiind cel mai eficient. Ținând cont de durata de viață per generație, și variația dintre începutul și sfârșitul programului, celelalte algoritme sunt mai eficiente decât noul algoritm. Că o concluzie finală, algoritmul propus, NSGA_II DAR, este capabil să obțină rezultate mai bune pentru probleme dificile.

Aceste rezultate indică spre ideea a unei influențe benefice mutual a operatorilor genetici în NSGA_II DAR.

Evoluția acestui subiect este posibil. S-ar putea să fim nevoiți să folosim mai mulți operatori genetici și să modificăm formulele pentru progresul operatorilor în scopul obținerii instanțelor dorite sau s-ar putea să adaptăm valorile parametrilor independenți.

Mecanisme folosite pentru evitarea convergenței algoritmilor genetici

Abstract

Este dificilă prezicerea comportamentului unui algoritm genetic pentru o problemă arbitrară. Combinând teoria algoritmului genetic cu practica folosim distanța medie hamming ca un mijloc de diversificare sintactic pentru a dobândi limite in convergența temporală din algoritmii genetici. Analiza unei funcții plate oferă complexitate de timp pentru funcții statice pentru cel mai rău caz posibil. Cu atât mai mult, introducerea informației executabile linear calculabilă, putem furniza limite ale timpului dincolo de progresul care este mai puțin probabil la fuctiile arbitrare statice. Ca și produs al acestei analize, limitele calitative sunt obținute prin predicția mediei fitness-ului.

Scrut istoric

Un algoritm genetic(AG) este o metodă de căutare aleatorie modelată de selecția naturală (Holland 1975). AG-urile sunt aplicate unei varietăți de probleme și devin o unealtă importantă în familiarizarea mecanică a studentului și optimizarea funcției ( Goldberg 1989). Frumusețea acestora constă în abilitatea lor de a modela rezistența, flexibilitatea și degradarea grațioasă a sistemelor biologice.

Selecția naturală folosește diversitatea în populație pentru a produce adaptare. Ignorarea efectelor de mutație pentru prezent, dacă nu există diversitate, selecția naturală nu poate acționa. Din moment ce AG-urile imită selecția naturală, vom aplica aceleași principii și vom folosi un măsurător al diversității pentru estimarea timpului ,pentru stagnare sau convergență. Un AG converge atunci când majoritatea populației este identică, cu alte cuvinte, diversitatea este minimală. Folosind distanță medie hamming că și măsurător al diversității populației vom deriva limite pentru timpul diversității minimale, atunci când algoritmul genetic este așteptat să nu mai facă niciun progres ( convergența hamming). Astfel de limite sunt foarte folosite pentru a prescrie timpul de acționare al unui AG pentru o problemă. Munca depusă în trecut în domeniul convergenței AG-urilor de către Ankebrandt, Goldberg și Deb se focusează pe timpul de convergență al unei alele particulare ( Ankenbrandt, 1991; Goldberg și Deb, 1991) folosind rația fitness-ului pentru a obține limitele complexității de timp. Din moment ce AG folosesc informație sintactică pentru a-și ghida căutarea, pare firesc să folosescă metrica sintactică în analiza lor. Analiza noastră, folosind media hamming, poate prezice timpul dincolo de care soluțiile îmbunătățite calititativ sunt improbabile. Din moment ce teoria aceasta unește la nivel intim schema proporției cu fiziologia, vom obține, de asemenea, media fitness-ului.

Următoarea secțiune definește modelul nostru de algoritm genetic și identifică efectul operatorilor genetici asupra diversității metrice, numită medie hamming. Ulterior am trecut la o limită superioară a timpului estimat al convergenței. Acest lucru sugerează remediul sintactic al problemei convergenței premature și ca efect, atenuarea erorilor în AG. Din moment ce încrucișarea nu afectează direct media hamming, vom aplica prin analogie schimbarea în media hamming pe durata primei generații cu scopul de a prezice media hamming pentru generațiile următoare. Rezultatele prezentate în secția 6 pentru un test indică o acuratețe surprinzătoare a predicțiilor. Ultima secțiune vorbește despre viitoarele direcții ale cercetării și concluzia lucrării prezentate.

Algoritmii genetici și distanța hamming

Un algoritm genetic se folosește de populație pentru a decoda o problemă parametrică într-un șir binar. Populația ințială este formată dintr-un set de șiruri generat aleatoriu. Modelul nostru de algoritm genetic are în componența sa selecția proporțională, încrucișări de tip n-point și operatorul mutațional obișnuit. Acum fiind definiți algoritmii genetici, putem analiza efectele distanței mediei hamming asupra populației.

Distanța medie hamming a unei populații este media distanței dintre toate perechiile de șiruri într-o populație de mărimea N. Din moment ce fiecare membru al populației este implicat în N-1 perechi, mărimea eșantionului cu care vom calcula media este:

Lungimea șirurilor în populație este l. Media hamming a populației inițiale este aproximată corect de către distribuția normală unde h0 :

Și deviația standard S0 este dată de formula:

Ignorând efectul mutației, media hamming a convergenței populației este zero (mutațiile cresc media hamming a convergenței populației cu valoarea ϵ > 0, în funcție de probabilitatea mutației). Dat fiind faptul că media hamming inițială este ½ și media hamming finală este 0, efectele selecției și încrucisării determină comportamentul algoritmului genetic pe durata timpului alocat.

Încrucișarea și distanța medie hamming

Presupunând că urmașii înlocuiesc părinții pe durata încrucisării, toți operatorii de încrucișare pot fi împărțiți în două grupe în fuctie de capacitatea acestora de a putea, sau nu, schimba media hamming. Dacă un părinte contribuie la aceleași alele la ambii urmași, distanță hamming dintre copil este mai mică decât distanță hamming dintre părinții acestora. Acest lucru aduce o pierdere a materialului genetic, reducând media hamming a populației, prin urmare se ajunge la o convergență hamming mai rapidă. Noi nu vom lua în cosiderare astfel de operatori în această lucrare. Marea majoritate a operatorilor tradiționali, că cei one-point,two-point, … l-point, incrcucișările uniforme și punctate ( De John și Spears 1991; Schafler și Morishima 1987, 1988; Syswerda 1989),nu afectează media hamming a populației. Pentru acești operatori de încrucișare vom dovedi următoarea teorie:

Axioma 1: Operatorii de încrucișare tradiționali nu schimbă distanța medie hamming a unei populații date.

Demonstrația: Vom dovedii că media hamming pentru o generație t+1 are aceeași valoare cu valoarea mediei hamming pentru generația t sub acțiunea solitară a unei încrucișări. Presupunând că alfabetul binar {a,b}, putem spune că media hamming a populației în generația t ca și suma mediei hamming cu l, unde l este lungimea cromozomului :

Media hamming pentru generația viitoare este :

În absența selecției și mutației, încrucișările schimbă doar ordinea în care vom aduna contribuțiile la fiecare loc, această fiind :

Prin urmare,

Eliminând încrucișările din considerentul nostru, din moment ce nu aducea nicio schimbare a mediei hamming, ne vom îndrepta atenția asupra selecției că fiind reponsabilă de convergența hamming.

Selecția și distanța medie hamming

Selecția reprezintă partea dependentă de domeniu a algoritmului genetic. Însă, independent de domeniu, am vrea să demonstrăm că selecția cu probabilitate mai mare de ½ reduce media hamming a generațiilor succesive, astfel obținând o limită superioară a timpului de convergență. Acest lurcu este echivalentul presupunerii că spațiul și timpul estimat al căutării pentru găsirea unui punct în acel loc are cele mai slabe probabilități. Pentru o fuctie statică, spațiul în care un algoritm este mai eficient decât căutările aleatorii satisface criteriul menționat anterior.

Funcția plană este definită că:

Nu conține nici o informație folositoare pentru căutarea unui algoritm cu privire la un punct în spațiu. Prin urmare, niciun algoritm nu poate fi mai eficient decât o căutare aleatorie pentru această funcție. Deși, un AG fără mutații pierde diversitate și eventual va converge. O expresie a timpului de convergență pentru o asemenea funcție dă naștere unei limite superioare a complexității timpului unui algoritm genetic pentru orice funcție statică. Convergența algoritmului genetic pentru o funcție plată este cauzată de deviația genetică aleatorie spre variații aleatorii cu valoare redusă a distribuției alelelor cauzând la rândul ei deviația algoritmului genetic și eventuală convergență a acestuia. Pentru a dobândii o limită superioară începem cu setarea timpului unei anumite alele la o valoare stabilită datorită deviatiei aleatorie genetică.

Dacă o populație de mărimea N conține o parte pi, a unei alele binare i, atunci probabilitatea ca k copiază alele lui i și sunt produse în generația următoare este dată de către distribuția probabilității binominale.

Folosind această distribuție, va trebui să calculăm probabilitatea apariției unei frecvențe aparte a alelei i în generațiile ulterioare. Aceasta este o problemă clasică în genetica populației. Chiar dacă soluția exactă este complexă, putem aproxima probabilitatea că frecvența alelei va lua valoarea p pentru generația t.

Aproximarea lui Wright cu privire la frecvențele intermediare ale alelelor și mărimea populației, cum ne este dat în Gayle ( Gayle 1990), ne este suficientă scopurilor noastre.

Dacă f(p,t) reprezintă probabilitatea că acea frecvență a alelei ia valoarea p în generația t, unde 0 < p < 1 , atunci:

Probabilitatea ca o alelă sa fie fixă la generatia t este:

Aplicând acest lucru unui algortim genetic și presupunând o populație inițiată aleatorie la t = 0, avem :

Dacă presupun că alelele se însoțesc independent, afirmația este adevărată pentru o funcție plană, atunci expresia probabilității că toate alele sunt fixe la generația t pentru un cromozom cu lungimea l este dată de:

Ecuația 1 ne alocă timp pentru a converge un algoritm genetic asupra unei funcții plate, prin urmare se stabilește limita superioară pentru orice funcție statică. De exemplu, pentru un cromozom de 50 de biți și o populație de 30 avem o limita superioară de 92% probabilitate de convergență în 50 de generații. Experimentând, avem între 92% și 73% convergență începând cu o medie hamming ințială de 50/2 = 25. În cercetările anterioare asupra deviatiei genetice, avem o expresie de taxare mai exact a timpului de convergență(Goldverg și Segrest 1987). Aceștia includ în analiză lor efectul mutației, care, din nou, este aplicabil direct în problema noastră. În final, algoritmii genetici converg atât de rapid datorită deviatiei genetice încât acest lucru ne oferă o baza teoretică a des întâlnitei probleme a convergenței premature.

Convergența prematură și înșelăciunea

Mama Natură folosește mărimi mari ale populației pentru a rezolva problema convergenței mature. Acest lucru este costisitor, cu atât mai mult cu cât nu trebuie să fim limitați de metodele naturii, ci trebuie să creăm inginerie genetică. Mutația pare a fi un candidat posibil, și în practică, este modul principal de a păstra diversitatea. Însă, ratele ridicate de mutație pot crește diversitatea, natura aleatorie a acesteia ridicând probleme. Mutația are șanse la fel de egale de a distruge schemele bune cât și rele, de aceea, selecția elitistă este necesară pentru a păstra cei mai buni indivizi dintr-o populație. Acest lucru functioază destul de bine în practică, dar este nestructurată și nu poate asigura că toate alelele sunt prezente în populație.

În loc să creștem ratele mutației, vom alege un individ și vom aduce complementul bit al acestei populații. Această metodă asigură prezența tutuor alelelor și populația va rezolva tot spațiul codat al problemei. Putem alege ca individul să fie completat în moduri variate în fuctie de ipotezele pe care le facem asupra spațiului de căutare. Selectarea în mod aleatoriu a individului care urmează a fi completat creează un număr de ipoteze și poate fi cea mai bună strategie în absența altor informații. De asemenea, putem alege cel mai bun, sau cel mai slab individ, ori putem folosii metode probabilistice în alegerea completării acestuia. În loc să completăm un individ, putem alege să completăm un set de indivizi, mărind spațiul codat în mai multe direcții. Abordarea în general folosită este aceea de a menține completarea fiecărui individ din populație, dublând astfel mărimea populației.

Prezența indivizilor completați face algoritmul genetic mai eficient în fața înșelăciunii. Intuitiv, din moment ce schema optimă este completată de schema optimă falsă, va fi creată în mod repetat cu prabilitați mari de convergență a AG cu optimul fals ( Goldberg et al. 1989). În experimentele noastre am înlocuit fitness-ul cel mai slab cu un individ completat ales aleatoriu din populația curentă, sau cu individul completat cel mai bun.

Dacă li reprezintă număr de biți necesari pentru a reprezenta variabila i într-o problemă de înșelăciune, atunci funcțiile folosite pot fi descrise astfel:

Am folosit Dec1 si Dec2 (Inșelăciunea 1 si Inșelăciunea 2) care sunt probleme de inșelăciune de 10 si 20 de biti. Dacă superscript-urile afiseaza numarul de biți necesari pentru fiecare variabilă, atunci Dec1 poate fi descris ca:

Deceptive(x12, x28)

Si Dec2:

Deceptive(x12,x28,x35,x45)

Figura 1 compară media fizionomiei după 100 de generatii al unui AG clasic si (AGC)

AGC () este mult mai performant decât AG-ul clasic, atât în media fizionomiei cât și în numărul de indivizi optimi găsiți. În majoritatea experimentelor, AG-ul clasic nu găsește optimul în 11 încercări, având o populație de 30 de indivizi în 100 de generații. Din moment ce media convergentă hamming pentru AGC este foarte mică, nu ne așteptăm să fie vreodată posibilă găsirea optimului global. Pe de altă parte, AGC-ul găsește cu ușurință optimul pentru Dec1 în 100 de generații și deobicei găsește optimul pentru Dec2 în câte sute de generații.

Figura 2 arată de câte ori optimul a fost găsit în Dec1 și Dec2 pentru 100, respectiv 1000 de generații. În ambele figuri, AGC(max) înlocuiește cel mai slab individ cu individul completat cel mai bun, în timp ce AGC(random) înlocuiește cel mai slab individ cu individul completat ales aleatoriu din populație.

Deși acest algoritm proietat genetic poate diminua anumite forme de înșelăciune, nu este panaceu (adica nu vindeca orice), deci nu poate garanta soluția optimă în cazul tuturor problemelor. Algoritmii genetici ‘murdari’ (Goldverg et al. 1989) pot aduce garanții dar complexitatea acestora este ridicată. În mod nesurprinzător AGC-urile, se descurcă mai bine decât AG-urile în One Max a lui Ackley și se descurcă la fel în testul lui De Jong ( Ackley 1987; De Jong 1975). Cu privire la problemele cu înșelăciune multiplă și subproblemele ușoare, AGC-urile sunt mai performante decât AG-urile clasice. În încheiere, probleme dificile AG, care sunt atât înșelătoare cât și epistatice, s-ar putea să aibă nevoie de un incrucișator ascuns sau alt operator recombinat independent , independenți de lungime pentru a rezolva problema folosind indivizi completați cu succes. ( Louis și Rawlins 1991).

Analiza convergenței

Avem acum o limită superioară a timpului de convergență a unei funcții statice, dar prezicerea performanței unei funcții arbitrare este mai dificilă datorită introducerii a intensității selecției. Cu toate acestea, ca urmare a scăderii mediei hamming atata timp cât AG-ul lucrează la o anumita problemă, ne permite prezicerea aproximativă a timpului de convergență hamming.

Fără mutație, AG-ul reduce media hamming de la ½ la 0. Prin urmare, prezice timpul de convergență al unei probleme prin găsirea ratei de reducere a mediei hamming. Vom începe cum un model general pentru schimbarea mediei hamming per generație:

ht+1 = F (ht)

Se raționalizeaza astfel media hamming ht din generația t cu media hamming în generația următoare. Găsirea lui F și rezolvarea recurenței sunt suficiente pentru a putea prezice timpul de convergență. Putem aloca mediei hamming din generația t ca și suma medie hamming a lui l, unde l este lungimea cromozomului.

Dacă hi,t reprezintă media hamming a lui in atunci avem:

Presupunând un alfabet binar {a,b} și o populație mare, media hamming a unui locus în populația curentă este aproximată corect de către rezultatul unui număr din a și a unui număr din b împărțit la un eșantion N( N – 1 )/2, unde N reprezintă mărimea populației. În mod formal, dacă m(ai,t) și m(bi,t) sunt numerele de a și b în locus, atunci:

Din moment ce a și b sunt schema de prim ordin concurența pentru locusul i, rata de creștere este data de teoria schemei. Rata de creștere pentru o schemă s cu fizionomia f(s) datorată selecției este:

Aici ft reprezintă media fitness-ului populației din generația t. Din moment ce luăm în considerare doar prima schemă, nu este necesară nicio modificare încorporată în efectul încrucișării. Ignorând mutația pentru prezent, putem astfel calcula media hamming în generația t+1 cu locusul i cum urmează. În primul rând:

Apoi, folosind teorema schemei exprimăm hi,t+1 că hi,t ,

Substitutia folosind ecuația 4:

Soluția acestei recurențe este:

Trebuie să calculăm numitorul. Aceasta este o problemă interesantă nu doar datorită faptului că ajută în prezicerea mediei hamming, ci și pentru că implică posibilitatea prezicerii fizionomiei. Din nou, concentrându-ne pe prima schemă, considerăm media fitness-ului in generația t la locusul i.

Dar fi,t deasemenea aproximează media fitness-ului populației în problemele cu epistaxis scăzut. Aproximarea devine mai corect în măsură ce epistaxisul scade iar estimarea noastră din prima schemă a fizionomiei devine mai bună. Având în vedere aceste considerențe, vom lansa primul subscript și vom scrie:

Folosind teoria schemei (ecuația 5), vom înlocui termenii t din partea dreaptă.

Multiplicând ambele parți cu ft-1

Dar ținând cont de teoria schemă (ecuația 5)

Prin urmare

Înmulțind cu ft-2

Ajungem la:

care este formula care ne trebuie. Această ecuație reprezintă posibilitatea de prezicere a fitness-ului este discutată în secțiunea următoare. Pentru scopul prezent, înlocuirea ecuației 9 cu 7 rezultă hi,t ca și termen al mediei hamming inițiale.

Pentru o populației inițializată aleatoriu:

Prin urmare:

Rearanjând termenii obținem:

Aici, hi,0 este media hamming inițiala din locusul i. Pentru o populație inițializată aleatoriu, media hamming pentru fiecare locus este ½ . Înlocuind hi cu ½ :

Însumarea i de la 0 la t – 1 rezultă media hamming a populației din generația t.

Formula pentru media hamming din generația t depinde doar de fitness-ul alelelor din cromozomi.

Această analiză indică faptul că prima schemă a fitness-ului prezice timpul de convergență. Deși calcularea exactă a fitness-ului nu este un lucru realizabil, putem folosi estimari. La urma urmei, AG-ul funcționează cu estimări ale fitness-uli. Epistatul de asemenea aduce probleme deoarece fitness-ul depinde de contextul în care este evaluată. În secțiunea 7 vom discuta predicția practică în detaliu. În ultimul rând, limitarea la prima schemă ne oferă șansa de a ignora încrucișările în siguranță și astfel putem lua în considerarea doar mutația în analiza noastră.

Manipularea mutației

Din moment ce ne interesează media hamming, vom lua în considerare efectul mutației asupra lui a și b. Mutația suferă schimbări, în funcție de probabilitatea pm, modificând numărul de copii a generațiilor următoare a și b.

Fără selecție

Din moment ce a devine b și vice-versa. Încorporând selecția obținem:

Ecuația distanței hamming pentru generația t este:

Pentru a rezolva această ecuație avem nevoie de m(ai,t) în loc de m(ai,0). Înlocuind m(bi,t) = N – m(ai,t) în ecuația 11 obținem:

Colecționând termenii:

De formă:

Unde:

Soluția recurenței este:

Înainte de a calcula rezultatul fitness-ului, vom rescrie al doilea termen ca:

În mod similar:

Vom obține:

Putem înlocuii valorile direct în ecuația 12:

Ca în secțiunea antecedentă vom calcula rezultatul fitness-ului. Începând cu:

Vom înlocuii pentru t + 1 în partea dreaptă (RHS) folosind ecuația 11:

Astfel vom obține:

Unde am înlocuit numărul inițial a , respectiv b cu valoarea N/2. Media fitness-ului pentru o generație aparte derivă doar din:

Acum putem înlocuii valorile pentru constantele c,d,u,w și rezultatul fitness-ului pentru a găsi media hamming pentru fiecare generație. Însă, calculele dificile din ecuația 15 ridică posibilitatea de aproximare a acesteia. Practic, media hamming a lui x, având o deviere standard y unde x + y ̴ z este suficient de precisă pentru noi, atâta timp cât noi căutăm punctele 2z în spațiul de căutare. Acest lucru implică ignorarea multor termeni din ecuația 15, rezultând un model mai simplu. Pentru a folosi simularea pe computer, folosim ecuațiile 11 și 8, repetând numărul de generații necesare, prezicând atât fitness-ul cât și media hamming.

Predicția practică

Pentru ca precedenta să ne fie folositoare, trebuie să cunoaștem prima schemă a fitness-ului. Acest lucru nu este fezabil computațional. Putem aproxima fitness-ului prin luarea în considerare a reprezentanților schemei din populația curentă. Dar acest lucru nu rezolvă problema legăturilor epistatice. Elementul cheie a intuiției necesare pentru a rezolva această problemă este realizarea ca teoria schema funcționează în ambele feluri. Dacă ținem cont de proporții, putem calcula fizionomia. Putem rescrie ecuația 5 ca:

Urmărind m(ai,t) pe de-a cursul a câtorva generații, ar trebuii să avem o estimare a fitness-ului pentru ai. Mutația poate fii descoperită în același fel.

Dacă presupunem similaritatea corzii implică similaritatea fitness-ului , atunci variația lui poate fii o unealtă de măsurare a non linearităților în genom, prin urmare o metodă de măsurare a epistatului. Din fericire, schemele competitive având o variantă mare a fizionomiei aduc selecții multe și rapide și pierd diversitate, pierzând efectele epistatice. Din moment un AG reduce exponențial variațiile ridicate, Generațiile O(logN) ar fi suficiente pentru a mitiga efectele non lineare.

Sugerăm următoarea metodă:

În loc de a prezice f(ai) sau f(bi) prin a face media contribuțiilor tuturor indivizilor care conțin ai sau bi; putem folosii ecuația 5 și 11 pentru a rezolva f(ai) și f(bi) pentru un mic număr de generații pentru a obține valoarea fitness-ului epistatică ajustata pentru fiecare schemă în parte.

Vom începe cu alele eșantion din generațiile O(log N):

Folosind o variantă computată a fitness-ului ajustate, putem prezice rata de creștere a primei scheme, deci media fitness-ului populației și media hamming a populației generațiilor următoare. Luați în considerare efectul noi scheme descoperite asupra prezicerilor. Noile scheme care scad f fitness-ului au efect minor, datorită eliminării rapidă a acestora din selecție. Când o schemă a fitness-ului cu caracter ridicat este identificată, alele lui participă în aceste scheme. Din acest lucru denotă ca media hamming prezisă va fi mai mare sau egală cu valoarea observată anterior dându-ne o limită superioară a timpului de convergență. Prin urmare, predicțiile noastre furnizează limite superioare ale medie hamming și tipului de convergență. O astfel de estimare este mai dezirabilă decât o estimare mult prea optimistă. Este mai bine ca AG să funcționeze pentru o perioadă mai lungă de timp decât să fie oprit prea devreme.

Variația în fitness ajustată pentru alele limitează numărul de generații eșantion pentru a obține o estimare precisă a fitness-ului alelelor. Analizând variația poate aduce încredere din punct de vedere statistic asupra predicțiilor noastre. Această variație limitează schemele fitness-ului la care participă alelele.

Pentru un anumit locus, folosind alele cu cea mai mică variație pentru a prezice creșterea oferă o estimare conservativă a mediei hamming. Variațiile reduse implică o aproximare corectă a nivelului fitness-ului la momentul curent a alelelor și oferă o limită superioară a prezicerii mediei hamming. În mod similar, folosind alele cu o variație mai mare oferă o estimare optimistă sau o limită inferioară. Aceste limite ar trebui să facă referire la valoarea prezisă a mediei hamming. Rezultatele prezentate mai jos sprijină analiza preliminară.

Funcțiile zgomotoase și zgomotul indus de mutații poate cauza un comportament impredictibil. Putem rezolva această problemă având un spațiu eșantion mai mare și folosind mai multe generații pentru a calcula fitness-ul ajustat.

Din aceleași metode menționate anterior, calcularea fitness-ului ajustat ne permite prezicerea unei limite inferioare al mediei fitness-ului deoarece el încorporează efectele schemei prezente. Toate noile scheme ( create prin încrucișare) care cresc fitness-ul ajustat unei alele pot aduce predicții ridicate ale mediei fitness-ului. Total opusul se poate întâmpla în cazul funcțiilor mulți modale. AG-ul se poate concentra în mod inițial asupra unui singur optim, ulterior schimbându-se asupra altuia. Din moment ce fitness-ul calculat nu mai poate fi corectă și AG-ului îi necesită timp pentru a învinge inerția creată de către primul optim, media fitness-ului prezisă poate fi mai mare decât media fitness-ului corectă.

Prezicerea mediei hamming

Din moment ce prezicerea mediei hamming este destul de robustă, putem folosi o aproximare lineară a lui F în ecuația 2. Presupunând un model rapid și ușor în cazul în care nu întâlnim mutații obținem:

A cărei soluție generală este:

Tabelul 1 compară media hamming corectă și cea prezisă (fără mutații)

Din moment ce nu au fost alte încercări pentru prezicere, folosim ecuații simple tip curve fitting pentru a obține un caz de bază pentru comparația cu modelul nostru. Obiectivul este acela de a prezice media hamming pentru generația numărul 50 cu funcțiile următoare:

Plata : f(x1,x2) = 10 , cu un cromozom de 50 de biți

Cele 5 funcții ale lui DeJong : F1…F5 (De Jong, 1975).

OneMax: f(X) = |X| unde |X| reprezintă coarda-bit X atât pentru un cromozom de 50 de biți (OneMax I) cât și pentru un cromozom de 200 de biți (OneMax II).

Toate probleme au fost redusă la probleme de maximizare. Populația AG-ului în experimente a fost 30, folosind selecția tip ruleta și selecția încrucișării de tip two-point. Vom introduce a în generația 0-10 folosind media hamming succesivă. Tabelul 1 arată rezultatele fără mutații. Ultimele 2 coloane prezic limitele inferioare și superioare a ecuației 11 folosind datele obținute de la generațiile [log30] = 5->10 inclusiv. Din moment ce codarea pentru funcțiile DeJong folosesc un semnal bit, vom alege 5 eșantioane, fiind suficiente pentru scopul nostru. Valorile observate reprezintă media a 11 încercări de rulare fără mutații. Deviațiile standard în 11 încercări sunt afișate în paranteze.

În mod surprinzător, valorile prezise folosind aproximări brute (ecuația 18) sunt destul de bune și sunt în limitele acceptate a deviației valorilor observate. Din moment ce rezultatele bune vin și în cazul unui model simplu arată validitatea abordării noastre. Limitele superioare și inferioare prezise folosind ecuația 11 includ valorile observate exceptând OneMaxI a cărei limită infoara este mai mare decât media hamming. Acest lucru implică o variație largă a eșantionului fizionomiei alelelor. În mod intuitiv, putem spune ca, fizionomia ajustată a unei alele depinde de numărul de numărul acestora în cromozomi, ajungând astfel la estimarea conservativă observată în absența zgomotului mutațional. Ne putem aștepta la OneMax să creeze probleme grave la introducerea mutației.

În continuare, realizând ca mutația schimbă media hamming la o valoare mai mare ca 0, vom folosii din nou un model timp curve fitting pentru a compara modelul nostru și pentru a prezice media hamming la convergentă pentru același set de probleme, dar cu rata mutației egală cu 0.01

Din moment ce mutația face AG-ul conveargă cu media hamming mai mare cu 0,pentru a modela comportamentul algoritmului genetic cu mutația.

Ecuația generală este:

În aceste experimente, algoritmul genetic a rulat până când s-a întâlnit convergența hamming. 500 de generații au fost suficiente pentru setul de probleme prezentate. Calculând valorile lui a și b din ecuația 19 folosind metoda celor mai puțini pătrați, putem prezice media hamming la convergentă. Acest lucru se poate realiza prin modificarea ϵ = ht = ht+1 și rezolvarea ht, din acesta rezultă:

Tabelul 2 compară media hamming identificată la generația 500 împreună cu valorile prezise. În coloana 3 întâlnim media hamming identificată la convergență și standardul acesteia la 11 rulări. Coloana 4 și 5 reprezintă valorile medii hamming prezise folosind ecuația 19 și datele de la generația 5 până la generația 20 respectiv de la generația 5 până la generația 45. Modelul mai simplu (curve fitting) se descurcă slab atunci când mutația este încorporată. Aceasta are nevoie de mai multe eșantioane și chiar rezultatul acesteia este negativ la convergența hamming. Cu toate acestea, modelul nostru folosind ecuația 11 nu are nevoie de informații în plus și, ca și în cazurile precedente, folosește doar eșantioane de la generația 5 până la generația 10 pentru a produce ultimele 2 coloane.

Predicțiile făcute de noi ( ultimele 2 coloane) din tabelul 2 sunt foarte aproape de valorile observate. Deși media hamming după 500 de generații este crescută pentru F4 și OneMax II, nu prezintă nicio schimbare majoră după 2000 de generații. Acest lucru indică faptul ca odată ce AG-ul a ajuns la un echilibru al mediei hamming, putem încerca alte mijloace de căutare. Predicțiile noastre vis-a-vis de limitele superioare și inferioare sunt încă suficient de corecte, cu excepția OneMax II. Aici, zgomotul indus de mutații este vinovatul principal deviației. Variația mare a fiziologiei alelelor sugerează folosirea unui spațiu eșantion mai mare pentru a crește rația semnal/zgomot. Cu siguranță, folosind încă 15 generații pentru a crea eșantioane ale fizionomiei sunt suficiente pentru a corecta problema și a da limite corecte OneMax II.

Predicția fizionomiei medie

Deoarece un model de amenajare curbat a dat rezultate bune pe predicția meidei hamming, vom folosi ecuația 19 de predicție fitness, precum si prin substituirea mediei fitness-ului în generarea lui T pentru ht. Tabelul 3 prezice media fitness (F), la convergența fără mutație. Coloana doi arată media fitness-ului observată și coloana trei indică media fitness convergentă.

Tabelul 2: Comparând media hamming actuală și previzibilă cu probabilitatea mutației setată la 0:01, s-ul indică faptul că valorile negative prezise în anumite rânduri au fost respinse.

Tabelul 3: Comparând mediile fitness-ului actuale și prezise (fără mutații)

în generația 50. Următoarele două coloane reprezintă predicția mediei fitness-ului folosind ecuația 19 din monstrele din generația 5 până la 15 și respectiv generația 5 până la 25. Ultimele două coloane utilizează ecuația 16 pentru a furniza limite conservatoare și optimiste a mediei fitness-ului. Abaterile standard ale mediei fitness-ului observate și prezise în 11 rulări sunt în paranteze . Anterior am afirmat că așteptăm noi limite atât de a subestima media fitness-ului observată , cu excepția cazului în care funcția este multimodală și / sau are variație mare de fitness-ului. Având în vedere că media fitness-ului este un produs secundar al predicției medie hamming în modelul nostru , vom folosi date de la 5 la 10 generații de fitness pentru prezicerea noastră . Nu credem în funcția plata.

Predicțiile liniare ale modelului mediei fitness-ului are deasemenea o deviație standard, de valori observate. Este mai interesant să privim la limitele inferioare și superioare. Așa cum se aștepta, F2 și F5, care sunt multimodale, au o valoare a fitness-ului mai mare . Alte previziuni conservatoare și optimiste au servit ca limite inferioare.

Tabelul 4: Comparând media fitness-ului actuala si prezisa cu probabilitatea mutatiei arată setată la 0:01

0:01 Efectele forțelor de predicție ale mutației utilizează eșantioane foarte mari de date pentru modelul liniar simplu limitând utilitatea sa. Predicțiile cu mai puține eșantioane nu sunt comparabile. Pe de altă parte, folosing modelul nostru, limitele superioare si inferioare, rămân din nou fără date pentru generațiile de la 5 la 10 cu mutație.

Aceste rezultate susțin modelul nostru de comportament algoritm genetic. Deși curbele montate au utilizări în furnizarea unei aproximări foarte dure, nu pot prezice efectele schimbării în parametrii AG-urilor și este ineficient în prezența mutației. Modelul nostru, bazat pe schema teoremei, este capabil să prezică media hamming în prezența mutației și are nevoie de mult mai puține probe. Folosind analiza noastră este ușor de prezis timpul de convergență pe o problemă. Aceasta este doar momentul în care modificarea mediei hamming este nesemnificativă. Știind resurse de calcul disponibile mediei hamming de mai jos pe care le putem întreprinde în căutarea integrala a spațiului rămas, și, prin urmare timpul necesar pentru a distiribui cererea. Mai mult, cu modelul nostru, putem prezice efectul modificărilor în mărimea populației și rata de mutație. În practică, instrumentarea unui AG de a păstra estimările alelei fitness și proporțiile ar trebui să reducă timpul petrecut cu experimentarea diferitelor setări de parametri și să știe dezvoltatorul resurselor de calcul necesare.

3.8. Concluzie

Analizând un AG este complicat in funcție de domeniul de aplicare și lipsa noastră de înțelegere a cartografiei între punctul nostru de vedere al domeniului de aplicare și punctul de vedere al AG-urilor privind același domeniu. Punctul de vedere al AG-urilor al domeniului este implicit în codificarea aleasa. Cu toate acestea, comportamentul general este previzibil și poate fi dedus din prelevarea de probe din sistemul adecvat de măsurare.

Analiza informațiilor sintactice din codificare, ne oferă o cantitate surprinzătoare de cunoștințe. Am derivat o limită superioară a complexității timpului de la luarea în considerare a efectelor de derivă pe alela frecventa. Aceasta a condus la sugestii promițătoare pentru atenuarea problemelor de convergență prematură și de introducere in eroare. Apoi, de la un model de efect de selecție și mutație asupra comportamentului algoritmilor genetici, noi am fost capabili de a aproxima cele două soluții caracteristice convergenței pentru spațiile de căutare statice.

1 . Bariere cu privire la o limită superioară a distanței mediei hamming a unei populații la convergența. În plus față de furnizarea termenilor, distanța mediei hamming a populației denotă, de asemenea, cantitatea de muncă rămasă.

2. Cantitatea de muncă posibilă prin AG, indică media fitness-ului la convergență.

În cadrul modelului nostru, cre combina predicția fitness-ului cu predicția mediei hamming ne dă o idee despre cât de mult este posibil un progres cu un AG împreună cu limite ce sugereaza cât de multă muncă din cea rămasă se poate face. Acesta din urmă este deosebit de important atunci când include mutația. Media fitness-ului previzibilă indică cât progres este posibil, dar media hamming este cea care denotă munca rămasă.

În prezent, lucrăm la o analiză mai aprofundată a varianței care să conducă la o mai bună încredere estimată pe previziunile noastre. Plănuim extinderea modelului nostru la funcțiile multimodale dinamice și operatori genetici speciali. Noi presupunem că operatorii de încrucișare care nu păstrează distanța Hamming pot fi modelați ca o perturbare a procesului de selecție și așa încorporați în modelul nostru.

În cele din urmă, am dori să sugerăm utilizarea proprietăților sintactice ale spațiului hamming în rafinarea noțiunii noastre a traiectoriei algoritmului genetic prin spațiu de căutare. Acest lucru ar trebui să conducă la comparații mai ușoare cu alte metode de căutare.

Aplicație.

Descrierea funcțională a aplicației

Descrierea tehnologiilor folosite în dezvoltarea aplicației

Concluzii

Bibliografie

[1] Ackley, D. A. (1987) A Connectionist Machine for Genetic Hillclimbing. Kluwer Academic Publishers.

[2] Ankenbrandt, C. A. (1991) An Extension to the Theory of Convergence and a Proof of the Time Complexity of Genetic Algorithms. In G. J. E. Rawlins (ed.) Foundations of Genetic Algorithms (San Mateo: Morgan Kauman), 53-68.

[3] De Jong, K. A. (1975) An Analysis of the Behavior of a class of Genetic Adaptive Systems, Doctoral Dissertation, Dept. of Computer and Communication Sciences, University of Michigan, Ann Arbor.

[4] De Jong, K. A. and Spears, W. M. (1991) An Analysis of Multi-Point Crossover. In G. J. E. Rawlins (ed.) Foundations of Genetic Algorithms (San Mateo: Morgan Kauman), 301-315.

[5] Freund, J. E. (1981) Statistics A First Course. Prentice-Hall.

[6] Gayle, J. S. (1990) Theoretical Population Genetics. Unwin Hyman, 56-99.

[7] Goldberg, D. E. and Deb, K. (1991) A Comparative Analysis of Selection Schemes Used in Genetic Algorithms. In G. J. E. Rawlins (ed.) Foundations of Genetic Algorithms (San Mateo: Morgan Kauman), 69-93.

[8] Goldberg, D. E. (1989) Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley.

[9] Goldberg, D. E., Korb, B. and Deb, Kalyanmoy. (1989) Messy Genetic Algorithms: Motivation, Analysis, and First Results. TCGA Report No. 89002, (Tuscaloosa: University of Alabama, The Clearinghouse for Genetic Algorithms).

[10] Schaer, J. D. and Morishima, A. (1988) Adaptive Knowledge Representation: A Content Sensitive Recombination Mechanism for Genetic Algorithms, International Journal of Intel ligent Systems (John Wiley & Sons Inc.) 3:229-246.