Implementarea algoritmilor evolutivi

Conceptul de evoluţie a fost propus de savantul englez Charles Darwin în 1859 în celebra sa carte “Originea speciilor prin selecţie naturală”. Principala sa teză este:

“Speciile evoluează prin variaţii aleatoare urmate de selecţie naturală în care cel mai potrivit supravieţuieşte”

Calculul Evolutiv (“Evolutionary computation”) reprezintă o direcţie de cercetare nouă şi de mare importanţă atât din punct de vedere teoretic, cât mai ales, din punctul de vedere al aplicaţiilor. Putem considera Calculul Evolutiv ca fiind un domeniu de sine stătător al Inteligenţei Artificiale.

Din punctul de vedere al ideilor de pornire şi aplicaţiilor Calculul Evolutiv (sau adaptiv) evidenţiază două aspecte:

-utilizează idei şi concepte referitoare la sistemele adaptive complexe pentru a rezolva probleme computaţionale (în special de optimizare şi căutare)

-utilizează calculatoarele şi metodele computaţionale pentru a modela sisteme adaptive complexe.

Tehnicile calcului evolutiv au fost iniţial dezvoltate pentru rezolvarea unor probleme de optimizare complicate, a căror abordare prin mijloace tradiţionale era imposibilă.

Calculul Evolutiv s-a dezvoltat în mai multe direcţii, cele mai cunoscute fiind:

- Algoritmii Genetici

- Strategiile Evolutive

- Programarea Evolutivă

- Programarea Genetică

- Sistemele de Clasificare Instruibile

Metodele dezvoltate în Calculul Evolutiv sunt generale, independente de problemă şi de funcţia ce se doreşte a fi optimizată (funcţia criteriu). Proprietăţile de continuitate, convexitate, derivabilitate sau de netezime ale funcţiei criteriu nu mai influenţează alegerea metodei de optimizare. Aceste metode au o comportare bună, sunt robuste şi, contrar unei păreri răspândite, nu sunt mari consumatoare de timp. Multe probleme care nu pot fi abordate cu tehnici tradiţionale au putut fi soluţionate utilizând metodele Calcului Evolutiv.

De regulă algoritmii genetici, strategiile evolutive şi celelalte tehnici ale Calculului Evolutiv sunt utilizate pentru a optimiza o funcţie criteriu. Există însă probleme pentru care nu este simplă formularea explicită (analitică) a unei funcţii criteriu. Însă, de regulă, şi în aceste cazuri se poate ataşa un anumit scor fiecărei soluţii găsite. Scorul măsoara calitatea soluţiei respective.

Calculul Evolutiv foloseşte concepte şi metode care au punct de plecare o metaforă biologică. O populaţie (aleatoare) de soluţii iniţiale (cromozomi sau indivizi) este modificată prin operatori de tip biologic (selecţie, încrucişare, mutaţie). Procesul de modificare favorizează soluţiile cele mai bune. Cei mai buni indivizi (cromozomi) vor fi selectaţi ca părinţi ai unei noi generaţii de soluţii. În felul acesta calitatea soluţiilor obţinute se îmbunătăţeşte. Cel mai bun individ obţinut într-un număr fixat de generaţii va constitui soluţia finală a problemei.

Lucrarea este structurată în patru capitole.

Capitolul 1 - “Algoritmi Evolutivi” - prezentare generală” - prezintă ideile de bază ale algoritmilor evolutivi, se evidenţiază principiile evoluţiei şi a selecţiei naturale, se prezintă structura generală a unui algoritm evolutiv.

Capitolul 2 - ”Algoritmi Genetici” - prezintă ideile fundamentale referitoare la algoritmii genetici. Se descriu operatorii genetici utilizati de un algoritm genetic (selecţie, încrucişare, mutaţie). În finalul capitolului se prezintă algoritmul genetic fundamental.

Capitolul 3 - “ Strategii Evolutive” - prezintă ideile de bază referitoare la strategiile evolutive. Se descriu diferite modele de strategii evolutive. Sunt prezentaţi principalii operatori din cadrul unei strategii evolutive (selecţie, recombinare, mutaţie).În finalul capitolului se prezintă structura generală a unei strategii evolutive.

Capitolul 4 - “Descrierea aplicaţiei” - este consacrat prezentării aplicaţiei.

CAP.1 Algoritmi evolutivi - prezentare generală

În acest capitol se prezintă principiile de bază ale algoritmilor evolutivi.Se evidenţiază ideile evoluţiei şi selecţiei naturale care au condus la clase importante de algoritmi de căutare şi optimizare. Se prezintă structura generală a unui algoritm evolutiv.

1.1.Evoluţia

Punctul de vedere acceptat in Inteligenţa Artificială este că îndeplinirea oricărei sarcini poate fi privită ca rezolvarea unei probleme. La rândul său, rezolvarea unei probleme poate fi gandită ca o căutare în spaţiul soluţiilor posibile (spaţiul starilor problemei). Această căutare poate fi ghidată de o funcţie de performanţă. Procesul de căutare este în acest caz însoţit de un proces de optimizare: dintre soluţiile posibile suntem interesaţi de cea mai bună. Uneori ne putem mulţumi cu o soluţie suficient de bună (aproximativ optimă).

Pentru probleme de mare complexitate, găsirea soluţiei optime, sau chiar a uneia acceptabile, este dificil de realizat. Tehnicile clasice fie nu sunt aplicabile, fie necesită un timp de lucru prohibitiv. Algorimii evolutivi sunt adecvaţi tocmai pentru soluţionarea unor astfel de probleme dificile.

Algoritmii evolutivi reprezintă tehnici de căutare şi optimizare având ca punct de pornire o metaforă biologică. Această metaforă biologică este cea a moştenirii genetice şi a evoluţiei naturale.

În cursul evoluţiei, toate fiinţele sunt confruntate cu problema adaptării la un mediu complicat, in continuă schimbare. In acest proces fiecare specie “invaţă”, iar cunoaşterea pe care a caştigat-o este codificată in cromozomii speciei. Evoluţia este aşadar un proces care are loc la nivelul cromozomilor.

Din perspectiva care ne intereseaza aici reţinem doar câteva caracteristici esenţiale ale procesului de evoluţie genetică:

1. Cromozomii sunt purtătorii informaţiei genetice.

2. Fiecare individ al unei specii posedă un număr determinat de cromozomi.Totalitatea cromozomilor unui individ reprezintă genotipul său.

3. Cromozomii sunt structuri liniare alcătuite din gene. Genele poartă caracteristicile ereditare. Genele ocupă locuri determinate , numite loci , în cromozom.

4. Evoluţia este un proces ce operează la nivelul cromozomilor.

5. Selecţia naturală reprezintă legatura dintre cromozomi şi performanşele indivizilor.

6. Evoluţia se realizează în procesul reproducerii. In evoluţie acţionează procese de selecţie, recombinare şi mutaţie.