Algoritmi Genetici

Calculul cognitiv denotă o familie de metode de rezolvare a problemelor care imită inteligenţa “găsită” în natură. Obiectivul comun al acestor metode este de a soluţiona situaţiile ce au rezistat abordărilor de tip analitic. Din această categorie fac parte reţelele neuronale, logica fuzzy, automatele celulare, algoritmii genetici, fractalii, teoria haosului. Fiecare din aceste metode încercă să “simuleze soft” lumea reală şi să proceseze datele de o manieră “cât mai naturală”.[1]

Este binecunoscut faptul că organismele vii evoluează de mii de ani, şi atunci când se vorbeşte despre evoluţie din punct de vedere al biologiei lucrurile sunt bine înţelese. Privind în jurul nostru se poate observa că organismele vii conlucrează unele cu altele pentru a supravieţui. Peste timp prin mutaţii şi evoluţie, organismele s-au adaptat pentru a câştiga avantaje în mediul în care trăiesc.

Transmiterea unor caracteristici generaţiilor următoare prin intermediul genelor reprezintă un mod simplu de supravieţuire şi în acelaşi timp de evoluţie. Rezultatele acestei strategii relativ simple sunt imprevizibile.

Algoritmii Genetici sunt strategii de rezolvare a problemelor cu ajutorul computerelor bazate pe teorii evoluţioniste. Soluţiile potenţiale sunt forţate să conlucreze într-un anumit mediu, având ca rezultat soluţiile cele mai bune în timp. Unul din principalele beneficii ale algoritmilor genetici este acela că pentru a rezolva o anumită problemă este nevoie de o cunoaştere a evoluţiei soluţiilor potenţiale şi nu construirea dinainte a uneia optime. Acest lucru devine evident cu cât complexitatea unei probleme se măreşte, soluţia optima în cazul acest caz este mult mai greu de determinat, o astfel de abordare fiind mult mai bună. În plus metodele utilizate de algoritmii genetici sunt utilizate şi în rezolvarea problemelor de către oameni.[2]

Un algoritm genetic poate căuta foarte eficient soluţia în spaţiul soluţiilor unei probleme date şi ajunge la o soluţie bună folosind o strategie inteligentă de căutare.

Algoritmii genetici reprezintă o modalitate de a căuta, în mod aleator, răspunsuri la probleme curente.

Se poate spune că algoritmii genetici sunt proceduri de căutare bazate pe mecanisme naturale de selecţie naturală şi genetică. Algoritmii genetici au fost dezvoltaţi de John Holland în 1960 pentru a permite contemporanilor săi să găsească soluţii pentru probleme dificile, cum ar fi funcţiile de optimizare şi inteligenţa artificială.

Algoritmi genetici şi programare genetică

Organismele vii pot fi privite ca rezolvatoare de probleme şi prezintă o versalitate care nu poate fi încă demonstrată de cel mai bun calculator existent (Holland, 1992). Astfel apare evident că emularea puterii deosebite a evoluţiei aşa cum are ea loc în lumea animală şi ca proiectarea de sisteme artificiale capabile de evoluţie şi adaptare ar duce la rezultate spectaculoase, un astfel de calculator fiind capabil să înveţe să se programeze singur. Trei decenii de cercetări teoretice şi aplicaţii practice au arătat că imitarea procesului de selecţie naturală poate duce la programe de calcul foarte robuste şi eficiente, deşi această imitaţie este o simplificare destul de depărtată de realitatea biologică.

Algoritmii genetici (AG) au fost dezvoltaţi iniţial de John Holland în anii '60 ca o formă de tehnică de căutare modelată după principiile evoluţiei Darwiniste. Astăzi, AG reprezintă cel mai popular model evoluţionist. În continuare ne propunem să prezentăm pe scurt structura şi caracteristicile unui AG simplu (AGS).

Vom începe cu prezentarea punctelor principale prin care un AG diferă de tehnicile convenţionale de căutare şi optimizare. Acestea sunt:

1. AG sunt "orbi"

Un AG tratează problema de rezolvat ca pe o "cutie neagră", necesitând foarte puţine informaţii despre aceasta. Din acest punct de vedere, un AG reprezintă o metodă slabă de căutare. Dar se observă în practică o foarte mare eficienţă, putere de rezolvare a problemei, ceea ce este o caracteristică a metodelor puternice de căutare. Deci la acest punct apare un aparent paradox: AG sunt metode slabe de căutare cu eficienţă foarte ridicată. După cum este argumentat în lucrările de specialitate, AG sunt metode slabe evoluţioniste ce reprezintă proprietatea de inteligenţă emergentă, puterea lor venind dintr-o exploatare sofisticată a informaţiilor obţinute cu un efort de căutare relativ limitat (Grefenstette, 1987).

2. AG folosesc codificări ale variabilei problemei

Fiind dat un spaţiu de căutare, cu un spaţiu multidimensional al soluţiilor posibile, o reprezentare "cod genetic" este aleasă astfel încât fiecare punct din spaţiul de căutare e reprezentat de un şir de simboluri numit genotip. În mod uzual, variabilele sunt codificate într-un genotip de lungime fixă.

3. AG folosesc populaţii de soluţii potenţiale

Aici apare o diferenţă importantă faţă de alte tehnici adaptive de căutare care lucrează de la punct la punct, folosind informaţii locale. Un AG explorează spaţiul de căutare în mai multe puncte simultan. Aceste puncte explorate la un moment dat formează o populaţie de soluţii potenţiale. Această explorare a spaţiului de căutare e făcută simultan cu exploatarea celor mai bune soluţii la pasul curent.

4. AG folosesc operatori probabilistici

Populaţia de la pasul următor de căutare este dedusă prin aplicarea unor operatori de tip probabilistic. Această caracteristică face ca AG să fie o metodă de tip Monte-Carlo, dar trebuie să facem observaţia că această căutare realizată nu e pur aleatoare, ci o explorare "inteligentă" a spaţiului de căutare.

Având prezentate aceste caracteristici dominante ale AG în raport cu tehnicile de căutare convenţionale, să privim mai detaliat modul de funcţionare al unui AGS.

Înainte de a începe o discuţie despre algoritmii genetici iată o scurtă descriere a termenilor cei mai importanţi.

• Cromozom – utilizat pentru a referi o soluţie potenţială, şi constă în toate informaţiile necesare pentru a descrie o soluţie;

• Clonă – apare atunci când se realizează o duplicare a unui cromozom. Aceasta este de obicei utilizată pentru a crea un fel de mutaţie care poate fi făcută fără a strica cromozomul iniţial;

• Crossover (încrucisare) – apare atunci când doi cromozomi creează unul sau mai mulţi cromozomi prin amestecarea soluţiilor lor;

• Fitness (potrivire) – o măsură a calităţii unui anumit cromozom. Cromozomul care dă cea mai bună soluţie va avea cea mai bună potrivire(fitness);

• Genaraţie – se referă la un ciclu complet al algoritmului genetic. Noi cromozomi sunt creaţi iar cai mai vechi sunt îndepărtaţi pentru a face loc celor noi.

• Mutaţie – sunt utilizate în 2 contexte diferite

1. Descrie orice modificare apărută la o populaţie;

2. Modificare apărută la un singur cromozom;

• Penalty (pedeapsă) – este o parte a potrivirii(fitness). Aceasta penalizează acţiunile ilegale sau nedorite ale unui cromozom în spaţiul soluţiilor.

• Populaţie – o colecţie de cromozomi disponibili. În mod normal există un număr limitat de cromozomi şi acei cromozomi care sunt defecţi sunt eliminaţi pentru a face loc altora cu performanţe mai bune;[7]

• Genotip – individ dintr-o populaţie. Reprezentarea internă a acestui tip poate fi un şir de biţi;

• Fenotip – obiectul corespunzător genotipului în problema dată. Acesta este obiectul matematic.

• Genă – atom de informaţie. De obicei se reprezintă ca un bit şi poate reprezenta mai multe caractere ale unui individ.