ALGORITMI GENETICI - · PDF file2 ALGORITMI GENETICI Vol.I CERCETARE ȘTIINȚIFICĂ CAPITOLUL...

0

ALGORITMI GENETICI Vol.I

S L A T I N A 2 0 1 4

VOL.I

ISBN 978-973-0-16089-5

ALGORITMI GENETICI

LUȚĂ COSTINA CLAUDIA

1


Tehnoredactare : Luță Costina Claudia

Referent ştiinţific:

Profesor gradul I ~ Gabriela Raluca Ionică ~

Inspector şcolar de specialitate I.S.J. Olt

Autor:

Profesor gradul I ~Luță Costina Claudia ~

Colegiul Tehnic “Alexe Marin” Slatina

2


CERCETARE ȘTIINȚIFICĂ

CAPITOLUL I

Noțiuni introductive

1.1 Istoric

Rezolvarea problemelor care implică folosirea unor expresii matematice a

fost intens studiată în ultimele decenii. In matematică optimizarea este înțeleasă

ca însemnând găsirea unei soluții optime. In acest scop s-au obținut rezultate

importante în calculul diferențial, calculul variațional, controlul optimal,

cercetări operaționale. Drumul de la rezultatele teoretice, referitoare la

teoreme de existență, unicitate, caracterizare a soluției, etc., la optimizarea

efectivă este de multe ori prea lung, fie datorită complexității prea mari a

problemelor reale față de modelul matematic utilizat, fie datorită complexității

(timp, memorie) algoritmilor utilizați.

La mijlocul anilor ’70, odată cu creșterea performanțelor calculatoarelor

și, implicit, a complexității problemelor reale ce se puteau rezolva cu

ajutorul calculatorului, au devenit frecvente situațiile în care modelele clasice

de optimizare nu mai conduceau la soluții acceptabile pentru probleme

modelabile pe calculator. Tot mai frecvent, probleme din biologie, climatologie,

chimie, mecanica, analiza datelor, etc., probleme ale căror modele includ sute

sau mii de variabile, ale căror funcții de optimizat prezintă multiple optime

locale și neregularități nestudiate din punct de vedere numeric, rămâneau

nerezolvate sau cu soluții aproximate grosier.

3


Studiindu-se excelenta adaptare a ființelor vii, în ceea ce privește forma,

structura, funcțiile și stilul de viața, numeroși cercetători au ajuns la concluzia că

natura oferă soluții optimale la problemele sale, soluții superioare oricăror

performanțe tehnologice. S-a demonstrat chiar matematic optimalitatea unor

sisteme biologice: raportul diametrelor ramificațiilor arterelor, poziția punctelor

de ramificare a vaselor de sânge, valoarea hematocritului (procentul volumului

particulelor solide din sânge). În consecință au apărut primele încercări de

imitare a procesului de evoluție naturală.

In anul 1970 profesorii Hans-Paul Schwefel (Dortmund) și Ingo

Rechenberg (Berlin) având de rezolvat o problemă de mecanica fluidelor,

referitoare la optimizarea formei unui corp ce se deplasează într-un fluid, au

căutat o noua tehnica de optimizare deoarece metodele cunoscute până în acel

moment nu conduceau la o soluție acceptabilă. Ideea lor a întruchipat conjectura

lui Rechenberg, ramasă până azi justificarea fundamentală a aplicării

tehnicilor evolutive: ”Evoluția naturală este, sau cuprinde, un proces de

optimizare foarte eficient, care, prin simulare, poate duce la rezolvarea de

probleme dificil de optimizat”. Modelul de simulare propus de Rechenberg și

Schwefel este cunoscut azi sub numele de ”strategii evolutive” și inițial se

aplica doar problemelor de optimizare de variabila continua. Soluțiile candidat x

se reprezintă în virgulă mobilă iar individul i căruia i se aplica procesul evolutiv

consta din aceasta reprezentare și dintr-un parametru al evoluției, notat s,

reprezentat tot în virgula mobila: i = (x, s). La fiecare pas soluția curentă este

modificată pe fiecare componentă conform lui s și în cazul unei îmbunătățiri

este înlocuită cu cea nou obținută. Parametrul s joaca rolul pasului din

metodele iterative clasice și este astfel folosit încât să fie respectat principiul

”mutațiilor mici”.

A doua direcție de studiu s-a conturat la Universitatea San Diego;

punctul de pornire a fost tot simularea evoluției biologice iar structura de

date aleasă a fost mașina cu număr finit de stări. Urmând aceasta abordare,

4


Fogel generează programe simple, anticipând ”programarea genetica”.

După mai mulți ani de studiere a simulării evoluției, John Holland de la

Universitatea Michigan a propus in 1973 conceptul de ”algoritm genetic”.

Au fost abordate probleme de optimizare discretă iar structura de date aleasa a

fost șirul de biți. Într-o accepțiune strictă, noțiunea de algoritm genetic se

refera la modelul studiat de Holland si de studentul sau De Jong. Într-un

sens mai larg, algoritm genetic este orice model bazat pe ideea de

populație și care folosește operatori de selecție și recombinare pentru a genera

noi puncte în spațiul de căutare.

5


1.2 Importanta temei in actualitate

În acesta car te am prezentat principalele direcţii ale algoritmilor

evolutivi, în special al algoritmilor genetici. Aplicaţiile practice ale acestor

algoritmi sunt nenumărate.

Principalele caracteristici ale algoritmilor genetici, comparativ cu cei

tradiționali sunt:

- sunt algoritmi probabiliști ce îmbină căutarea dirijată cu cea aleatoare;

- realizează un echilibru aproape perfect între explorarea spațiului stărilor și

găsirea celor mai bune soluții;

- în timp ce metodele clasice de căutare acționează la un moment dat asupra

unui singur punct din spațiul de căutare, algoritmii genetici mențin o mulțime (=

populație) de soluții posibile;

- algoritmii genetici nu acționează direct asupra spațiului de căutare ci asupra

unei codificări a lui;

- sunt mai robuști decât algoritmii clasici de optimizare și decât metodele de

cautare dirijată;

- sunt simplu de utilizat și nu cer proprietăți importante ale funcției obiectiv,

precum continuitate, derivabilitate, convexitate, ca in cazul algoritmilor clasici;

- pot găsi soluții optime sau aproape optime cu o mare probabilitate.

Caracteristicile lor au făcut ca algoritmii genetici să fie utilizați în cele

mai diverse domenii:

- optimizare:

- optimizare numerică și combinatorică,

- proiectarea circuitelor, a sistemelor de conducte și a liniilor

de comunicație,

- proiectarea avioanelor;

- planificarea proceselor de producție;

- programare automata;

6


- scrierea programului LISP pentru o problema data;

- obținerea de algoritmi de sortare;

- instruirea mașinilor = machine learning;

- deplasarea într-un labirint,

- controlul deplasării unui robot;

- proiectarea rețelelor neuronale;

- deducerea regulilor pentru rezolvarea diferitelor

probleme;

- rezolvarea unor probleme dificile de tip joc;

- proiectarea controlorilor inteligenți;

- probleme de predicție a sistemelor haotice, vremii,

evoluției pieței financiare;

- modelarea unor procese complexe din: economie,

politica, ecologie, etc.

Ei sunt folosiţi în domenii tot mai neaşteptate cum ar fi proiectarea

aripilor de avion sau la proiectarea formei staţiilor orbitale. Dacă aţi ales să

rezolvaţi o problemă genetic, trebuie să ţineţi cont de câteva sfaturi.

Pentru a rezolva o problemă cu algoritmi genetici trebuie să o

transformaţi mai întâi într-o problemă de optimizare, adică să se

minimizeze sau să se maximizeze o valoare (cel mai scurt lanţ

hamiltonian, cea mai mare componentă intern stabilă etc.).

Algoritmii genetici sunt algoritmi euristici, adică soluţia găsită de ei

nu este întotdeauna cea mai bună, dar se află într-o vecinătate a

soluţiei optime. Deci, dacă aveţi de ales între un algoritm

polinomial care rezolvă sigur problema şi un algoritm genetic, ar fi de

preferat să folosiţi algoritmul polinomial.

Algoritmii genetici, de obicei, au complexitate polinomială. De aceea ei

7


sunt foarte des utilizaţi pentru a rezolva problemele dificile (NP-

complete). Rezultatele obţinute sunt foarte apropiate de cele obţinute de

algoritmii siguri, dar care au rulat mii de ore.

Dacă problema este complexă folosiţi un algoritm genetic şi nu o

strategie evolutivă. De obicei mutaţia este un operator de căutare

slab, deci, dacă se foloseşte doar acesta, există şanse mari să se

obţină o soluţii locale şi nu globale.

Concluzie - Puterea algoritmilor genetici constă în uşurinţa cu care sunt

implementaţi şi în faptul că dau de multe ori rezultate bune, chiar dacă nu

găsesc întotdeauna optimul global.

8


CAPITOLUL II

Aspecte teoretice de baza

2.1 Calcul evolutiv

În general, orice sarcină abstractă care trebuie îndeplinită, poate fi privită

ca fiind rezolvarea unei probleme, care, la rândul ei, poate fi percepută ca o

căutare în spaţiul soluţiilor potenţiale. Deoarece, de obicei, căutăm cea mai bună

soluţie, putem privi acest proces ca fiind unul de optimizare. Pentru spaţii mici,

metodele clasice exhaustive sunt suficiente; pentru spaţii mari, pot fi folosite

tehnicile speciale ale inteligenţei artificiale.

Rezolvarea problemelor folosind metode evolutive este un domeniu de

tradiție. El își are rădăcinile în anii '50, când mai mulți cercetători au preluat

metafora evolutivă din natură, aplicând-o la rezolvarea problemelor din diverse

domenii. Metafora evolutivă este transpusă, informatic, într-un număr foarte

mare de algoritmi. Totuși, câteva considerente generale pot fi indicate.

Se lucrează cu o populație (vector, listă) de posibile soluții. Acestea se

mai numesc uneori și indivizi, cromozomi etc. Indivizii populației inițiale sunt

generați aleator. Cu ajutorul selecției și al operatorilor genetici indivizii

evoluează și, eventual, vor converge către soluție.

Indivizii sunt evaluați pe baza unei așa-zise funcții de fitness (calitate).

Fitness înseamnă speranță de viață. Cu cât un individ este mai performant, cu

atât speranța lui de viață este mai mare.

Asupra indivizilor din populație se aplică operatori genetici. Acești

operatori sunt dependenți de reprezentare. Dintre cei mai răspândiți operatori

genetici amintim încrucișarea și mutația. Prin încrucișare, de obicei, doi părinți

9


dau naștere a doi fii. Prin mutație se aplică o mică "perturbație" a valorii unui

individ. De obicei, nu toți indivizii sunt aleși pentru aplicarea operatorilor

genetici. Modul și ordinea în care se aplică operatorii genetici asupra indivizilor

variază foarte mult. De exemplu, într-un algoritm genetic din populație sunt

selectați indivizi în funcție de fitness-ul lor. Indivizii selectați sunt introduși

într-o populație intermediară. Indivizii din această populație intermediară sunt

supuși operatorilor genetici de încrucișare și mutație. Indivizii rezultați în urma

acestor operații constituie "următoarea generație", adică o nouă populație care va

fi din nou supusă selecției și anumit număr de generații.

Metodele calculului evolutiv se numără printre aceste tehnici; ele folosesc

algoritmi ale căror metode de căutare au ca model câteva fenomene

naturale: moştenirea genetică şi lupta pentru supravieţuire. Cele mai

cunoscute tehnici din clasa calculului evolutiv sunt algoritmii genetici,

strategiile evolutive, programarea genetică şi programarea evolutivă. Există şi

alte sisteme hibride care încorporează diferite proprietăţi ale paradigmelor de

mai sus; mai mult, structura oricărui algoritm de calcul evolutiv este, în mare

măsură, aceeaşi.

Ín ultimii 30 de ani, s-a manifestat un mare interes în rezolvarea

problemelor de sistem bazate pe principiile evoluţiei şi eredității. Astfel de

sisteme menţin o populaţie de soluţii potenţiale, ele au unele procese de selecţie

bazate pe fitness individual, şi câţiva operatori genetici. Un astfel de sistem este

o clasa a evoluţiei strategice i.e, algoritmi care imita principiile evoluţiei

naturale pentru problemele de optimizare de parametru(Rechemberg,

Schwefel). Evoluţia programării lui Fogel este o tehnica de căutare într-un

spaţiu finit, mic de maşini. Tehnologiile de căutare a maşinii lui Glover Scatter

menţin o populaţie de puncte de referinţă, generând o stare speciala

prin greutatea combinaţiilor liniare.

10


Alte tipuri de sisteme evoluţionare sunt Holland‘s Genetic Algorithms. În

1990 Koza a propus un astfel de sistem evoluţional, genetic programming,

pentru a căuta cel mai potrivit program de computer sa rezolve o

problema particulara . Folosind un termen comun E.P pentru toate

sistemele(incluzând sistemele descrise mai sus). Structura evoluţiei

programului este arătat astfel:

procedura

algoritm_evolutiv

t 0 creare P(t) evaluare P(t) cât timp nu condiţia de terminare

t t + 1 selectare P(t) din P(t-1) modificare P(t) evaluare P(t)

sfârşit sfârşit procedura

În cele ce urmează voi explica algoritmul general propus mai sus.

Evoluţia programului este un algoritm probabilistic ce conține

elemente distincte, P(t)={x1t, x2t, ...xnt}. Algoritmii evolutivi menţin o

populaţie de indivizi la fiecare iteraţie t. O populaţie poate fi privită ca fiind

un vector de valori. Fiecare element distinct reprezintă o soluție potenţială a

problemei în cauza și în orice program, este interpretat ca S structura de date.

Fiecare solutie x1t, x2t,.., xnt este evaluata pentru a da o oarecare măsura a

„fitness-ului“ său.

Fiecare individ (element al vectorului) reprezintă o soluţie

potenţială a problemei şi este implementată sub forma unei structuri de

date S. Un individ este uneori numit şi cromozom. Fiecare soluţie este

evaluată ca fiind o măsură a "fitness-ului" său (speranţei de viaţă). Acest

fitness reprezintă calitatea individului. De obicei, cu cât individul este mai

11


promiţător, cu atât fitness-ul său este mai mare.

Există unele probleme în cazul cărora fitness-ul trebuie să fie minimizat.

O nouă populaţie (iteraţia t + 1) se formează prin selectarea mai multor

potriviri individuale, alegând cei mai promiţători indivizi (pasul de selecţie)

din populaţia curentă. O parte din membri populaţiei nou formate suferă

transformări (pasul de modificare) prin „operarea —genetica“ a noilor soluții.

Vorbim despre o transformare unica e evoluţiei programului.

12


2.1.2 Operatori genetici - calculul evolutiv

Operatorii genetici sunt, de fapt, proceduri care operează asupra

elementelor vectorului populaţie. Există doi operatori genetici principali:

un operator unar mi de transformare numit mutaţie, care creează un nou

individ printr-o mică modificare a unui individ ales (mi: S S);

un operator mai puternic cj numit încrucişare, care creează noi indivizi

combinând părţi din doi sau mai mulţi indivizi (cj: S ... SS) (de

cele mai multe ori se folosesc doi părinţi).

După un anumit număr de generaţii algoritmul converge: se speră că cel

mai promiţător individ ajunge la o valoare cât mai apropiată de soluţia

optimă. În ciuda similarităţilor puternice între diferitele tehnici de calcul

evolutiv, există şi multe diferenţe. Acestea sunt date, în principal, de

structurile de date folosite pentru a reprezenta un individ şi de ordinea în

care se aplică operatorii genetici. De exemplu, cele două linii din algoritmul

de mai sus:

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

pot apărea în ordine inversă: (în strategiile evolutive, întâi se modifică

populaţia şi apoi este formată o nouă populaţie prin procesul de selecţie, in

timp ce într-un algoritm genetic întâi se aplică selecţia, iar apoi intră în

acţiune operatorii genetici de transformare). Decembrie 2001

31Există, de asemenea, şi alte diferenţe între metode. Una dintre

acestea ar fi cea referitoare la metodele de selecţie care includ:

selecţia proporţională, unde şansa (probabilitatea) ca un individ să fie

selectat este proporţională cu fitness-ul lui;

metoda rangului, în care toţi indivizii din populaţie sunt sortaţi în funcţie de

fitness, iar probabilitatea

13


(şansa) ca ei să fie selectaţi este fixată de întreg procesul de evoluţie(de

exemplu, probabilitatea de selecţie a celui mai promiţător individ este 0.15, a

individului următor este 0.14, etc.; cel mai promiţător individ are cea mai

mare probabilitate şi suma totală a probabilităţilor indivizilor este1);

selecţia prin turnir (prin concurs) unde un anumit număr de indivizi (de

obicei doi) luptă pentru a fi selectaţi în noua generaţie.

Această competiţie (turnir) este repetată până sunt selectaţi un

număr de indivizi egal cu dimensiunea populaţiei. Pentru fiecare dintre

aceste categorii de selecţie există şi alte detalii importante. Câteva

exemple sunt:

selecţia proporţională poate necesita folosirea unor metode de trunchiere;

există diferite moduri pentru stabilirea probabilităţii în metoda rangului;

dimensiunea mulţimii alese pentru concurs poate juca un rol semnificativ

în metoda selecţiei prin turnir.

Trecerea de la o generaţie la alta poate fi efectuată în două variante:

algoritm generaţional (noua populaţie este formată doar din descendenţi ai

vechii generaţii);

algoritm non-generaţional (în noua populaţie sunt introduşi, de obicei, cei

mai promiţători indivizi din cele două populaţii, cea a părinţilor şi cea a

descendenţilor).

Este posibil, de asemenea, să creăm puţini (în particular, unul

singur) descendenţi, care înlocuiesc câţiva (cei mai puţin promiţători)

indivizi. Ca o regulă generală trebuie reţinut faptul că, în majoritatea

cazurilor, este de preferat să se utilizeze un model elitist, care păstrează cei

mai promiţători indivizi dintr-o generaţie şi îi adaugă automat generaţiei

următoare (aceasta înseamnă că, dacă cel mai promiţător individ din generaţia

curentă este pierdut datorită selecţiei sau operatorilor genetici, sistemul

forţează apariţia lui într-o generaţie următoare). Un astfel de model este

14


foarte folositor pentru rezolvarea multor probleme de optimizare. Totuşi,

structurile de date folosite pentru probleme particulare, împreună cu o

mulţime de operatori genetici, constituie componenta esenţială a oricărui

algoritm evolutiv. Acestea sunt elementele cheie care ne permit să distingem

între variatele paradigme ale metodelor evolutive.

15


2.2. Algoritmi genetici paradigme ale calculului evolutiv

Algoritmii genetici utilizează un vocabular împrumutat din genetica

naturala. Mulțimea punctelor de căutare păstrate de algoritm la un moment

dat se numește populație, iar indivizii unei populații se numesc cromozomi.

Cromozomii sunt alcatuiți din unități numite gene, aranjate într-o

succesiune liniară; fiecare genă controlează moștenirea a una sau mai multe

caractere. Unele gene pot fi plasate în anumite locuri ale cromozomului, numite

locus iar valorile posibile pentru o gena formează setul de alele ale genei.

Odată populația inițială creată, fiecare șir este evaluat și i se atribuie un

fitness dat de o funcție f , numită funcția fitness=funcția de evaluare.

Noțiunile de fitness ș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 fitness transformă aceasta 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. Fitness-ul unui șir

este, însă, definit în raport cu alți membri ai populației curente. Fitness-ul

poate fi definit, de exemplu, prin fi/f unde fi este evaluarea asociata șirului i

iar f este evaluarea medie a tuturor șirurilor populației.

Funcția de evaluare si 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 neagra” 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 rezolva problema

dată. In termeni tradiționali dorim să minimizăm (maximizam) o funcție F (x1,

x2, ..., xn ). De cele mai multe ori este imposibil de tratat independent fiecare

parametru. Apariția interacțiunilor face necesara considerarea efectelor

combinate ale parametrilor in vederea optimizării cutiei negre.

16


In limbajul algoritmilor genetici, interacțiunea dintre variabile este

numita epistasis.

Variabilele reprezentând parametrii sunt, de obicei, codificate prin

șiruri binare, dar există si alte codificări: numere întregi, numere reale, codul

Gray, codificare alfabetica, arbori. Condițiile pe care trebuie să le

îndeplinească o reprezentare buna sunt: independenta relativa a genelor,

includerea a cat mai multe restricții ale problemei direct în reprezentare,

complexitate scăzută a decodificări/codificării cromozomilor.

Rezolvarea problemelor de codificare este considerata, de obicei, ca

parte a construcției funcției de evaluare. Funcția de evaluare este parte a

descrierii problemei. Precizarea funcției de evaluare poate implica o

simulare si poate fi aproximativa sau parțială. De exemplu, sa consideram

o problema de control optimal, în care mulțimea stărilor în care se poate afla

sistemul poate fi exponențial de mare.

Folosirea unui algoritm genetic pentru găsirea unei strategii optime

de control presupune reducerea spațiului stărilor (prin eșantionare) și, astfel,

evaluarea realizată este aproximativă și afectata de perturbații. Funcția de

evaluare trebuie sa fie ușor de calculat având in vedere ca fiecare generație

trebuie evaluata; deci funcția de evaluare este apelata de foarte multe ori.

Exista o mare clasa a problemelor interesante pentru care încă nu au

fost dezvoltați algoritmi rapizi. Multe dintre acestea sunt probleme sunt

probleme optimizate care intervin frecvent în aplicații. Dându-se o problema

prost optimizată este posibil mereu sa găsim un algoritm eficient a cărui

soluţie este aproximativ optimala. Pentru unele probleme prost optimizate

putem folosi algoritmi probabilistici:

-acești algoritmi nu garantează valoarea optima, dar prin alegeri

aleatoare, suficient de multe

—slăbiciuni a erorilor pot fi făcute astfel încât sa putem trece peste ele.

Exista multe probleme importante practic optimizate pentru care

asemenea algoritmi, de o înalta calitate, devenind disponibili. În orice caz

17


putem aplica simultan rularea mai multe fire de execuţie si competenta

amplasării problemelor VLSI design pentru problemele gen agent

comercial. In plus multe alte probleme aparținând unei game largi de

probleme optimizate combinatorial pot fi rezolvate aproximativ în ziua de

astăzi prin computer de genul tehnicilor Monte Carlo.

Ín general, orice proces abstract pentru a fi îndeplinit poate fi gândit ca

o rezolvare a problemei, care , in schimb, poate fi perceputa ca o căutare

prin spațiul soluțiilor potențiale. Cum suntem in căutarea celei mai bune

soluții, putem privi aceasta sarcina ca un proces optimizat. Pentru spatiile

mici, metodele clasice executive sunt suficiente; pentru spaţiile largi

tehnica speciala a inteligenţei artificiale trebuie sa fie luata in vedere.

Algoritmii genetici sunt printre aceste tehnici; ei sunt algoritmi stohastici a

căror metode de căutare modelează unele fenomene naturale. Ideea in spatele

algoritmilor genetici este de a face ceea ce natura face.

Începuturile algoritmilor genetici se situează undeva în jurul anului

1950, când mai mulţi biologi au folosit calculatoarele pentru simularea

sistemelor biologice. Rezultatele muncii au început să apară după 1960, când

la Universitatea din Michigan, sub directa îndrumare a lui John Holland,

algoritmii genetici au apărut în forma în care sunt cunoscuţi astăzi.

După cum sugerează şi numele, algoritmii genetici folosesc principii

din genetica naturală. Câteva principii fundamentale ale geneticii sunt

împrumutate şi folosite artificial pentru a construi algoritmi de căutare care

sunt robuşti şi cer informaţii minime despre problemă.

Algoritmii genetici au fost inventaţi folosind modelul procesului de

adaptare. Ei operează, în principal, cu şiruri binare şi folosesc un operator

de recombinare şi unul de mutaţie. Prin mutaţie se schimbă un element

(genă) dintr-un cromozom, iar prin încrucişare se schimbă material genetic

între doi părinţi; dacă părinţii sunt reprezentaţi prin şiruri de cinci biţi, de

exemplu (0, 0, 0, 0, 0) şi (1, 1, 1, 1,1), încrucişarea celor doi vectori poate

18


duce la obţinerea descendenţilor (0, 0, 1, 1, 1) şi (1, 1, 0, 0, 0)(acesta este un

exemplu al aşa-numitei încrucişări cu un punct de tăietură).

Fitness-ul unui individ este atribuit proporţional cu valoarea

funcţiei criteriu corespunzătoare individului; indivizii sunt selectaţi pentru

generaţia următoare pe baza fitness-ului lor.

Vom ilustra modul de lucru al algoritmilor genetici cu ajutorul unei

probleme simple: proiectarea unei cutii de conserve. Considerăm o cutie de

conserve cilindrică, cu numai doi parametri: diametrul d şi înălţimea h

(evident, pot fi consideraţi şi alţi parametri, cum ar fi grosimea,

proprietăţi ale materialului, forma, dar sunt suficienţi doar cei doi

parametri pentru a ilustra lucrul cu algoritmii genetici).

Să considerăm că această conservă trebuie să aibă un volum de

cel puţin 300 ml şi obiectivul proiectului este de a minimiza costul

materialului folosit la fabricarea conservei. Putem formula problema

noastră astfel:

să se minimizeze valoarea funcţiei unde c reprezintă costul materialului

conservei per cm2, iar expresia din paranteză reprezintă suprafaţa conservei.

Funcţia f se mai numeşte şi funcţie criteriu (sau funcţie obiectiv). Mai

trebuie îndeplinită şi condiţia ca volumul cutiei să fie cel puţin 300 ml şi

vom formula aceasta astfel:

Parametrii d şi h pot varia între anumite limite:

dmin d dmax şi hmin h hmax.

19


Reprezentarea soluţiei

Primul pas în utilizarea unui algoritm genetic este stabilirea unei

codificări a problemei. Codificarea binară este cea mai obişnuită dintre

tehnicile de codificare; ea este simplu de manipulat şi conferă robusteţe

problemei.

Reprezentarea binară poate codifica aproape orice situaţie, iar

operatorii nu includ cunoştinţe despre domeniul problemei. Este motivul

pentru care un algoritm genetic se poate aplica unor probleme foarte diferite.

Ín cazul codificării binare, fiecare valoare se reprezintă printr-un şir de

lungime specificată care conţine valorile 0 şi 1. Ín anumite situaţii este

necesar să utilizăm codificarea "naturală" a problemei, în locul

reprezentării binare. Un exemplu de codificare naturală ar fi codificarea reală,

care utilizează numere reale pentru reprezentare. Pentru a folosi algoritmii

genetici la găsirea unor valori optime pentru parametri d şi h, care să

satisfacă condiţia prezentată sub forma funcţiei g şi care să minimizeze

funcţia f, vom avea în primul rând nevoie de reprezentarea valorilor

parametrilor în şiruri binare (vom folosi, aşadar, o codificare binară a

problemei).

Algoritmii genetici nu ne impun numai valori întregi dintr-un anumit

inteval; în general, putem folosi orice altă valoare întreagă sau reală, prin

schimbarea lungimii şirului binar

20


2.2.1 Atribuirea fitness-ului

Am afirmat anterior că algoritmii genetici lucrează cu şiruri de

biţi reprezentând valorile parametrilor şi nu cu parametrii înşişi. După ce a

fost creat un nou şir (o nouă soluţie) prin operatori genetici, trebuie să-l

evaluăm. În majoritatea cazurilor, fitness-ul este chiar valoarea funcţiei

criteriu pentru soluţia respectivă. Dacă obiectivul nostru este de a minimiza

funcţia criteriu, atunci vom spune că o soluţie este mai bună decât alta, dacă

fitness-ul celei de-a doua este mai mare.

2.2.2 Structura unui algoritm genetic

Vom descrie în continuare structura

algoritmilor genetici. Pentru început vom

stabili următoarele:

cromozomii utilizaţi au lungime constantă;

populaţia (generaţia) P(t + 1) de la momentul t + 1 se obţine reţinând toţi

descendenţii populaţiei P(t)

şi ştergând ulterior cromozomii generaţiei precedente (P(t));

numărul cromozomilor este constant.

Putem prezenta acum structura algoritmului genetic fundamental:

Pasul 1: t 0.

Pasul 2: Se iniţializează aleator populaţia P(t).

Pasul 3: Se evaluează cromozomii populaţiei P(t).

Ín acest scop se utilizează o funcţie de performanţă ce depinde de

problemă.

Pasul 4: Cât timp nu este îndeplinită condiţia de terminare se execută paşii

21


următori:

Pasul 4.1: Se selectează cromozomii din P(t) care vor contribui la formarea

noii generaţii. Fie P1 mulţimea cromozomilor selectaţi (P1 reprezintă

o populaţie intermediară).

Pasul 4.2: Se aplică cromozomilor din P1 operatorii genetici. Cei mai utilizaţi

sunt operatorii de mutaţie şi încrucişare.

În funcţie de problemă se pot alege şi alţi operatori (inversiune,

reordonare, operatori speciali). Fie P2 populaţia astfel obţinută (descendenţii

populaţiei P(t)). Se şterg din P1 părinţii descendenţilor obţinuţi. Cromozomii

rămaşi în P1 sunt incluşi în populaţia P2. Se construieşte noua generaţie,

astfel: P(t + 1) P2; se şterg toţi cromozomii din P(t); se execută

atribuirea t t + 1; se evaluează P(t). Condiţia de terminare se referă,

de regulă, la atingerea numărului de generaţii specificate. Dacă numărul

maxim admis de generaţii este N, atunci condiţia de oprire este t > N. Se

admite că rezultatul algoritmului este dat de cel mai promiţător individ din

ultima generaţie. Ín realitate, nimic nu ne garantează că un individ mai

performant nu a fost obţinut într-o generaţie anterioară. De aceea, este

normal ca la fiecare pas (la fiecare generaţie t) să reţinem cel mai promiţător

individ care a fost generat până atunci. Acest proces se numeşte elitism.

22


2.2.3 Selecţia

Un rol important în cadrul unui algoritm genetic îl ocupă operatorul de

selecţie. Acest operator decide care dintre indivizii unei populaţii vor putea

participa la formarea populaţiei următoare. Scopul selecţiei este de a asigura

mai multe şanse de reproducere celor mai performanţi indivizi dintr-o

populaţie dată.

Prin selecţie se urmăreşte maximizarea performanţei indivizilor.

În continuare vom prezenta succint cele mai importante mecanisme de

selecţie.

Selecţia proporţională

În cazul selecţiei proporţionale, probabilitatea de selecţie a unui

individ depinde de valoarea performanţei acestuia. Să presupunem că avem o

mulţime de cromozomi x1, x2, …, xn. Pentru fiecare cromozom xi vom

calcula performanţa sa f(xi). Se impune condiţia ca f(xi) 0. Suma

performanţelor tuturor cromozomilor din populaţie va constitui performanţa

totală şi o vom nota cu F.

Selecţia bazată pe ordonare

Această modalitate de selecţie constă în a calcula (pentru fiecare

generaţie) valorile funcţiei de fitness şi de a aranja indivizii în ordinea

descrescătoare a acestor valori. Se va atribui fiecărui individ i o probabilitate

de selecţie pi care depinde de rangul său în şirul stabilit. Probabilităţile

depind acum doar de poziţia cromozomului. Cel mai promiţător individ are

probabilitatea 1.

23


Selecţia prin concurs

Selecţia prin concurs sau selecţia turnir se bazează pe compararea directă a

câte doi cromozomi şi selectarea celui mai performant.

Operaţiile implicate sunt următoarele:

se aleg în mod aleator doi cromozomi;

se calculează performanţele cromozomilor selectaţi;

cromozomul mai performant este selectat (copiat în populaţia intermediară

asupra căreia se aplică operatorii genetici).

Alte mecanisme de selecţie

Un alt tip de selecţie este selecţia elitistă. În acest caz, la fiecare

generaţie se păstrează cel mai promiţător sau cei mai promiţători indivizi. O

altă idee ar fi ca, la fiecare generaţie, să fie înlocuită doar o parte restrânsă a

populaţiei.

2.2.4 Operatorii genetici

Descriu în continuare operatorii genetici folosiţi, de obicei, într-un algoritm

genetic.

Operatorul de reproducere

Rolul operatorului de reproducere este de a menţine soluţiile

promiţătoare din populaţie şi de a le elimina pe cele mai puţin promiţătoare,

păstrând constantă dimensiunea populaţiei.

Aceasta se realizează astfel:

24


se identifică soluţiile promiţătoare din populaţie;

se creează mai multe copii ale soluţiilor promiţătoare;

se elimină soluţiile mai puţin promiţătoare din populaţie astfel încât

multiplele copii ale soluţiilor promiţătoare să poată fi plasate în populaţie.

Există mai multe moduri de a realiza acest lucru. Cele mai

uzuale metode sunt selecţia proporţională, selecţia prin turnir şi selecţia

prin ordonare. Este uşor de observat că soluţiile promiţătoare au mai

mult de o copie în populaţia intermediară

Operatorul de încrucişare

Operatorul de încrucişare este aplicat asupra indivizilor din populaţia

intermediară.

Ín exemplul nostru, va fi aplicat asupra reprezentării binare a celor şase

elemente pe care le avem în populaţia intermediară. Operatorul de

încrucişare acţionează în felul următor: sunt aleşi aleator doi indivizi din

populaţia intermediară (care se mai numeşte şi

piscină de încrucişare) şi anumite porţiuni din cei doi indivizi sunt

interschimbate. Operatorul imită încrucişarea intercromozomială naturală.De

regulă, se utilizează operatori de încrucişare de tipul (2, 2), adică doi părinţi

dau naştere la doi descendenţi.

Încrucişarea realizează un schimb de informaţie între cei doi

părinţi. Descendenţii obţinuţi prin încrucişare vor avea caracteristici ale

ambilor părinţi.

Dată fiind importanţa majoră a încrucişării, au fost propuse mai multe modele

de încrucişare. Vom enumera aici câteva dintre cele utilizate atunci când se

foloseşte codificarea binară.

25


Încrucişarea cu un punct de tăietură

Fie r lungimea cromozomilor. Un punct de tăietură este un număr

întreg k {1, 2,..., r - 1}. Numărul k indică poziţia din interiorul

cromozomului unde secvenţa cromozomială se rupe pentru ca segmentele

obţinute să se recombine cu alte segmente provenite de la alţi cromozomi.

Considerăm doi cromozomi:

x=x1x2...xkxk+1...xr şi

y = y1y2...ykyk+1...yr.

Ín urma recombinării se schimbă între cei doi cromozomi secvenţele

aflate în dreapta punctului de tăietură k.

Cromozomii fii vor fi:

x' = x1x2...xkyk+1...yr şi

y' = y1y2...ykxk+1...xr.

De exemplu, dacă avem o reprezentare mai sugestivă a celor doi

cromozomi:

descendenţii vor fi:

26


Încrucişarea cu mai multe puncte de tăietură

Ín cazul utilizării mai multor puncte de tăietură, segmentele obţinute se

combină după o regulă dată. Considerăm încrucişarea cu două puncte de

tăietură. Acest tip de încrucişare se realizează conform schemei de mai jos.

Din cromozomii:

vor rezulta doi descendenţi de tipul:

În cazul a trei puncte de tăietură, descendenţii vor fi de forma :

Revenind la exemplul nostru, vom considera încrucişarea cu un singur punct

de tăietură. De exemplu, din încrucişarea a două soluţii reprezentate prin

cutia care are fitness-ul 23, h = 8 şi d = 10, respectiv cutia cu fitness-ul 26, h

= 14 şi d = 6, vor rezulta doi descendenţi care vor avea fitness-ul 22, h = 10 şi

d= 6, respectiv fitness-ul 38, h = 12 şi d = 10 după modelul de mai jos:

Trebuie reţinut faptul că încrucişarea nu generează descendenţi aleatori. Deşi

27


este improbabil ca fiecare încrucişare între două soluţii din populaţie să

genereze soluţii fii mai promiţătoare decât soluţiile părinte, totuşi în scurt

timp devine clar că şansa de a crea soluţii mai promiţătoare este mai mare

decât în cazul căutării aleatoare. Din încrucişarea cu un singur punct de

tăietură a unei perechi de şiruri binare, se pot crea doar două şiruri pereche

diferite care vor avea în componenţă biţi combinaţi din ambii părinţi;

soluţiile fiu create sunt, probabil, şiruri cel puţin la fel de promiţătoare. Prin

urmare, nu fiecare încrucişare poate crea soluţii la fel de promiţătoare, dar nu

vor fi mai puţin promiţătoare decât părinţii. Dacă a fost obţinută o soluţie

mai puţin promiţătoare, atunci aceasta nu va mai apărea când se va aplica

următorul operator de reproducere şi astfel va avea o viaţă scurtă.

Dacă este creată o soluţie mai promiţătoare, atunci este probabil ca ea să

aibă mai multe copii la următoarea aplicare a operatorului de reproducere.

Pentru a păstra o astfel de selecţie a şirurilor promiţătoare în timpul

aplicării operatorului de reproducere, nu toate şirurile din populaţie sunt

folosite pentru încrucişare.

Operatorul de mutaţie

Operatorul de încrucişare este, în principal, responsabil cu aspectul de

căutare al algoritmilor genetici, în timp ce operatorul de mutaţie este folosit

pentru alte scopuri. Mutaţia este cel de-al doilea operator genetic în ordinea

importanţei şi folosirii sale. Efectul acestui operator este schimbarea valorii

unei singure poziţii dintr-un cromozom.

Prin mutaţie se introduc în populaţie indivizi care nu ar fi putut fi

obţinuţi prin alte mecanisme. Operatorul de mutaţie acţionează asupra biţilor

indiferent de poziţia lor în cromozom. Fiecare bit al cromozomului poate

suferi o mutaţie. Într-un cromozom pot exista, aşadar, mai multe poziţii care

suferă o mutaţie. Mutaţia este un operator probabilist (adică nu se aplică cu

28


siguranţă). Considerăm o populaţie de n indivizi (cromozomi), fiecare având

lungimea r. Fiecare bit are aceeaşi probabilitate pm de a suferi mutaţia.

Există mai multe variante ale operatorului de mutaţie. Una dintre ele ar

fi mutaţia în forma tare. În această situaţie se procedează în felul următor: se

generează un număr aleator q în intervalul [0, 1). Dacă q < pm, atunci se

execută mutaţia poziţiei respective schimbând 0 în 1 sau 1 în 0. Ín caz

contrar, poziţia respectivă nu se schimbă.

Revenind la exemplul nostru, dacă aplicăm operatorul de mutaţie unei

soluţii obţinute în urma procesului de încrucişare, şi anume soluţiei care are

fitness-ul 22, vom obţine o altă soluţie care va avea fitness-ul 16.

Soluţia obţinută este mai promiţătoare decât soluţia originală. Ín

consecinţă, operatorul de reproducere selectează cele mai promiţătoare

şiruri, operatorul de încrucişare combină subşiruri din două şiruri

promiţătoare pentru a forma şiruri mai promiţătoare, iar operatorul de

mutaţie schimbă şirurile local, de asemenea, pentru a îmbunătăţi soluţia.

29


2.3. Strategii evolutive

Strategiile evolutive au fost dezvoltate ca metode de rezolvare pentru

problemele de optimizare a parametrilor. Prima strategie evolutivă a fost

bazată pe o populaţie constând dintr-un singur individ. De asemenea, este

folosit un singur operator în procesul de evoluţie: mutaţia. Aceasta este

în concordanţă cu conceptul biologic potrivit căruia modificări mici au

loc mai frecvent decât o modificare mare. De obicei această strategie

conform căreia un părinte dă naştere prin mutaţie unui singur descendent

este cunoscută sub numele de strategie evolutivă 1 + 1. Felul în care se aplică

practic acest algoritm este simplu: se generează o soluţie aleatoare pe

domeniul de căutare şi se efectuează mutaţii asupra ei. Este acceptat cel

mai bun dintre părinte şi descendent. Operatorul de mutaţie se aplică

repetat până când se ajunge la soluţie.

Un alt tip de strategie este strategia ( + ): părinţi produc

descendenţi. Noua populaţie (temporară) de (+ ) indivizi este redusă din

nou - printr-un proces de selecţie - la indivizi. Pe de altă parte, in strategia

(, ), indivizi produc descendenţi ( > ) şi prin procesul de selecţie

se alege o nouă populaţie de indivizi numai din mulţimea celor

descendenţi. Astfel, viaţa fiecărui individ este limitată la o generaţie.

30


2.3.1 Programare evolutivă

Tehnicile programării evolutive originale au fost dezvoltate de

Lawrence Fogel. El urmărea o dezvoltare a inteligenţei artificiale în sensul

dezvoltării abilităţii de a prezice schimbările într-un mediu înconjurător.

Mediul înconjurător a fost descris ca o secvenţă de simboluri, iar

evoluarea algoritmului presupunea obţinerea unui nou produs, şi anume a

unui nou simbol. Simbolul obţinut va maximiza funcţia finală care măsoară

acurateţea predicţiei.

De exemplu, putem considera o serie de evenimente notate a1, a2,

..., an; un algoritm va determina următorul simbol (an+1), bazându-se pe

simbolurile cunoscute a1, a2,..., an.

Ideea care stă la baza programării evolutive este de a evolua un algoritm. Ca

şi în strategiile evolutive, şi în tehnica programării evolutive se creează mai

întâi descendenţii şi apoi se vor selecta indivizii pentru generaţia următoare.

Fiecare părinte produce un singur descendent; deci dimensiunea

populaţiei intermediare se dublează (ca în strategia evolutivă (n, n), unde n

este dimensiunea populaţiei). Descendentul este creat printr-o mutaţie

aleatoare a părintelui (este posibil să se aplice mai mult de o mutaţie unui

individ). Un număr de indivizi (cei mai promiţători) egal cu dimensiunea

populaţiei sunt reţinuţi pentru noua generaţie.

Ín versiunea originală acest proces este repetat până se obţine un

nou simbol care este disponibil. După ce s-a obţinut un nou simbol,

acesta este adăugat listei simbolurilor cunoscute şi întregul proces se

repetă. Recent, tehnicile de programare evolutivă au fost folosite pentru

rezolvarea problemelor de optimizare numerică precum şi în numeroase alte

scopuri.

31


2.3.2 Programarea genetică

O altă abordare interesantă a fost descoperită relativ recent de John Koza.

Koza sugerează că programul dorit va evolua el însuşi pe parcursul

unui proces de evoluţie. Cu alte cuvinte, în loc de a rezolva o problemă şi în

loc de a construi un program evolutiv care să rezolve problema, vom încerca

să găsim un cod sursă care să o rezolve.

Koza a dezvoltat o nouă metodologie care furnizează un mod de a

efectua această căutare. De exemplu, se doreşte obţinerea unui program

Pascal sau C++ care să rezolve problema drumului hamiltonian sau

problema ieşirii dintr-un labirint. Deci, nu ne interesează să obţinem o

soluţie pentru un set oarecare de date, ci, mai degrabă, ne interesează să

obţinem un program sursă care să genereze o soluţie corectă pentru orice

intrare dată. Cu alte cuvinte, ne interesează să obţinem ca rezultat un

program asemănător cu cel pe care l-am fi putut scrie noi dacă am fi ştiut să

rezolvăm problema.

Din punct de vedere evolutiv abordarea unor astfel de probleme se

face generând o mulţime (populaţie) aleatoare de coduri sursă care apoi sunt

selectate pe baza funcţiei de fitness şi evoluate cu ajutorul unor operatori

genetici specifici. Ín primul rând trebuie să atribuim o funcţie de calitate

(funcţia fitness) fiecărui program generat. Această funcţie de fitness trebuie să

reflecte performanţele programului căruia îi este ataşată.

De obicei ataşarea unei funcţii de fitness se face rulând programul

respectiv şi măsurând calitatea soluţiei în raport cu o soluţie care se cunoaşte

a fi optimă. Un program va avea o calitate mai mare dacă soluţia generată va

fi mai asemănătoare cu cea a soluţiei corecte. Nu este grav dacă o soluţie

optimă nu se cunoaşte anterior, deoarece noi dorim să obţinem soluţii cu un

fitness cât mai mare (sau cât mai mic).

32


Evoluarea programelor sursă se realizează prin operatori genetici

specifici. De exemplu, un operator de recombinare poate însemna alipirea

secvenţelor dintr-un cod sursă cu secvenţe din alt cod sursă. Un operator de

mutaţie ar putea însemna inserarea de noi instrucţiuni în codul sursă, ştergerea

de instrucţiuni, transformarea de instrucţiuni. Evident, în urma aplicării

acestor operatori genetici se generează cod sursă care conţine greşeli de

sintaxă. De asemenea, sunt generate secvenţe de cod sursă nefolositoare.

Exemple în acest sens sunt secvenţa de instrucţiuni:

i := i + 1;

i := i - 1;

sau secvenţa:

a := 0;

b := c / a;

De obicei, se evoluează reprezentări mai simple ale programelor

de calculator şi anume reprezentările arborescente. Există limbaje de

programare (de exemplu LISP) în care programele sunt scrise sub forma unor

liste uşor transformabile în arbori.

33


Aplicatie

În cele ce urmează voi prezenta rezolvarea unei probleme folosind algoritmii

genetici:

Enunţ: (Submulţime de sumă dată)

Se consideră o mulţime M de n numere şi un număr S. Să se determine o

submulţime a mulţimii.

M care are suma elementelor cât mai apropiată de numărul S.

Rezolvare

Determinarea unei submulţimi de sumă dată este o problemă NP-completă

Aceasta înseamnă că nu se ştie dacă există sau nu un algoritm de

complexitate polinomială pentru rezolvarea acestei probleme. Până în

prezent, algoritmii folosiţi au complexitate exponenţială, iar pentru anumite

cazuri particulare au complexitate pseudopolinomială. De exemplu, putem

rezolva rezonabil această problemă, dacă datele de intrare îndeplinesc

următoarele condiţii:

sunt cel mult 100 de numere naturale;

suma numerelor nu depăşeşte 500 (mai exact, produsul dintre numărul

numerelor şi suma acestora nu trebuie să depăşească dimensiunea maximă

admisă pentru alocarea unei matrice (presupunem că aceasta este alocată

static).

Dacă aceste condiţii ar fi îndeplinite am putea rezolva uşor această

problemă prin metoda programării dinamice, folosind un algoritm de

complexitate O(n ‡ S) ). Însă, dacă numerele nu ar fi întregi ci reale, sau

suma lor ar fi mai mare decât 500, sau diferenţele între ele ar fi mari etc.,

34


atunci algoritmul prin programare dinamică nu mai poate fi folosit.

Am enumerat aici doar cazurile importante, dar pot fi imaginate şi alte

dificultăţi.

Din aceste motive vom rezolva această problemă cu ajutorul unui

algoritm genetic. Va trebui să găsim o reprezentare a soluţiei şi, de

asemenea, o funcţie de fitness. Modul în care vom reprezenta soluţia ne este

dat chiar în enunţul problemei: se cere o submulţime a unei mulţimi M cu n

elemente. Deci, o soluţie a problemei este o submulţime. Vom codifica o

submulţime printr-un şir de lungime n care conţine doar valorile 0 şi 1. Dacă

o poziţie k va avea valoarea 1, atunci submulţimea respectivă va conţine

elementul Mk (al k-lea element din mulţimea M), iar dacă pe poziţia k este

valoarea 0, atunci elementul respectiv nu aparţine submulţimii. Această

reprezentare a unei submulţimi este specifică tipului set din Turbo Pascal.

Modul de calcul al fitness-ului (calităţii) unei soluţii (submulţimi) este

simplu. Calculăm suma elementelor submulţimii, iar fitness-ul va fi

diferenţa (în valoare absolută) dintre suma obţinută şi numărul dat S. Ín

aceste condiţii fitness-ul va trebui minimizat, deoarece noi dorim să

determinăm o submulţime pentru care suma elementelor este cât mai apropiată

de valoarea dată S.

Structura algoritmului genetic propus pentru rezolvarea acestei

probleme a fost prezentată mai sus. Vom folosi selecţia turnir pentru

obţinerea populaţiei intermediare. Operatorii genetici folosiţi sunt specifici

codificării binare (încrucişare cu un singur punct de tăietură, mutaţie cu

probabilitate pm=0.1).

35


2.4 Sisteme hibride

Așa cum am mai precizat, algoritmi genetici sunt o familie de modele

inspirate de teoria evoluţiei, sunt programe inteligente capabile să soluţioneze

probleme folosind un conceptul al evoluţiei speciilor. Aceşti algoritmi codifică

soluţiile posibile ale unor probleme specifice într-o structură de date de tip

cromozom şi aplică acestor structuri operatori de recombinare, pentru a păstra

informaţia utilă.

Un cromozom este un vector sau un şir de gene. Poziţia unei gene este

numită locusul ei. Valorile pe care le poate lua o genă sunt numite alele, sunt

mulţimi finite de numere întregi, intervale de numere reale, sau chiar structuri

complexe de date. Alele variază de la un locus la altul.

Sarcina unui algoritm genetic e să descopere cromozomi din ce în ce mai buni,

până la atingerea unei valori a raportului dintre evaluarea asociată unui şir şi

evaluarea medie a tuturor şirurilor populaţiei (fitness) despre care se ştie că este

optimală, sau până când algoritmul genetic nu mai poate aduce îmbunătăţiri.

Implementarea unui algoritm genetic începe cu o populaţie de cromozomi

(aleasă aleator). Se evaluează, apoi, aceste structuri şi se alocă facilităţi

reproductive astfel încât acei cromozomi, care reprezintă o soluţie mai bună

pentru problema ţintă, să aibă mai multe şanse de a se reproduce decât acei

cromozomi care sunt soluţii mai puţin bune. Definirea unei soluţii bune se face

în raport cu populaţia curentă.

Într-un sens mai larg, algoritm genetic este orice model bazat pe ideea de

populaţie şi care foloseşte selecţie şi operatori de recombinare pentru a genera

noi puncte într-un spaţiu de căutare. Multe modele au fost introduse de

cercetători dintr-o perspectivă experimentală. Cercetătorii sunt orientaţi spre

aplicaţii, fiind interesaţi de algoritmii genetici doar ca mijloace de optimizare.

36


Ei sunt recomandaţi pentru aflarea soluţiilor neliniare ale unor probleme

atunci când nu este posibilă modelarea matematică şi nici euristică în domeniu.

Adevăraţii profesionişti combină adesea cele mai variate tehnologii

inteligente în scopul exploatării avantajelor fiecăreia, obţinând aşa-numitele

sisteme hibride. Sunt posibile combinări de genul:

1. folosirea reţelelor neuronale la ajustarea parametrilor în sistemele

expert fuzzy,

2. extragerea cunoaşterii din reţele neuronale pentru a fi utilizată în

sistemele expert,

3. folosirea algoritmilor genetici la crearea unor reţele neuronale mai

compacte şi mai eficiente,

4. folosirea unei reţele neuronale pentru asistarea funcţionării unui

algoritm genetic,

5. folosirea algoritmilor genetici la reglarea parametrilor unui sistem

expert fuzzy pentru controlul proceselor,

6. îmbunătăţirea performanţei unui sistem expert prin încorporarea

raţionamentului bazat pe cazuri, etc.

Asemenea cercetări sunt în prezent în mare vogă în cele mai specializate

laboratoare ale lumii ştiinţifice.

Câteva subiecte ale conceptelor de bază :

probleme de optimizare - doar două componente principale sunt

dependente de

problema de rezolvat : codificarea şi funcţia de evaluare. Scopul este de a fixa

parametrii în aşa fel încât ieşirea să fie optimă.

Variabilele desemnând parametrii sunt reprezentaţi prin şiruri binare iar funcţia

de evaluare este parte a descrierii problemei.

algoritmul genetic canonic – constă în generarea populaţiei iniţiale. Se

aplică

37


acestei populaţii selecţia pentru a obţine o populaţie intermediară. Apoi se aplică

recombinarea şi mutaţii pentru a crea o populaţie următoare (next population).

Acest proces de trecere de la populaţia curentă la populaţia următoare reprezintă

o generaţie în execuţia unui algoritm genetic.

selecţia hiperplanelor – nu este afectată de extremele locale. Creşterea

ratei de selecţie a hiperplanelor peste medie nu garantează convergenţa

către un optim global, ce ar putea fi un vârf relativ izolat.

teorema schemei – furnizează o margine inferioară a schimbării ratei de

selecţie pentru un singur hiperplan de la generaţia t la generaţia t+1.

alfabetele binare – utilizarea lor va rezulta în urma unor calcule simple.

Un alfabet minimal maximizează numărul de hiperplane utilizabile pentru

codificarea procesării

critica teoremei schemei – inexactitatea inegalităţii face ca încercarea de a

prezice pe baza teoremei reprezentarea unui anumit hiperplan de-a lungul

generaţiilor, să fie fără succes.

2.4.1 Aplicaţii ale algoritmilor genetici

Algoritmii genetici reprezintă o metodă cu care pot fi atacate relativ uşor

probleme dificile de optimizare sau control, cu rezultate bune sau chiar

optimale.

Când se vorbeşte de aplicarea unei idei din software, se referă în general

la un prototip care arată cum ar putea fi folosită respectiva idee într-un domeniu

practic.

Un exemplu îl constituie sistemul care funcţionează la instalaţia de

maleabilizare a unui laminor de platbande de oţel, unde operatorul unei macarale

38


este ajutat să decidă unde să pună oţelul laminat înainte de maleabilizare, cum să

grupeze şarjele în cuptorul de maleabilizare şi cum să aranjeze oţelul laminat

maleabilizat pentru a fi expediat în funcţie de comenzile primite. Un alt exemplu

este aceea de a realiza optimizarea unor obiective variate în alcătuirea orarelor

pentru cursuri sau examene.

Aplicaţii ale algoritmilor genetici este de exemplu controlul curgerii de

gaz printr-o conductă, în regim staţionar şi în regim tranzitoriu. De-a lungul

conductei, presiunea gazului descreşte în mod natural şi trebuie mărită cu

ajutorul unor compresoare. Obiectivul constă în menţinerea presiunii în punctele

de livrare la nivelul dorit, cu minimizarea energiei folosite în compresoare şi

îndeplinirea altor restricţii. De asemenea, este necesară detectarea, pe baza

măsurării presiunii, a scurgerilor probabile, evitând, pe cât posibil, alarmele

false.

Alţi cercetători descriu o aplicaţie în proiectarea reţelelor de comunicaţii

între staţii aflate la mare distanţă.

Optimizarea planificărilor - utilizarea algoritmilor pentru planificarea

examenelor – se dau un set de examene şi un număr fix de căsuţe libere în orar :

obiectivul e de a aşeza fiecare examen într-una dintre căsuţe, astfel încât nici un

student să nu aibă examene aflate în căsuţe consecutive, nici prea multe

examene în aceeaşi zi. De asemenea, anumite examene nu pot fi puse în anumite

căsuţe.

39


Reprezentarea folosită este naturală : există o genă pentru fiecare examen,

altele fiind date de mulţimea căsuţelor din orar. Evident, majoritatea

cromozomilor generaţi aleator vor încălca mai multe restricţii. Funcţia de fitness

conţine termini de penalizare pentru fiecare restricţie încălcată şi se dovedeşte

stabilă faţă de valorile efective ale acestor termeni. Algoritmul genetic are deci

o formă convenţională, cu excepţia unui operator de mutaţie mai deosebit.

Acesta exercită o uşoară presiune pentru îmbunătăţirea orarului. Implementarea

unui operator mai tare, care efectuează acea schimbare care duce la cea mai

bună îmbunătăţire a unui cromozom, se dovedeşte extrem de dăunătoare.

Algoritmul genetic a găsit o soluţie în care doar unul dintre studenţi a avut de

susţinut două examene consecutive. Algoritmul a obţinut o astfel de soluţie, nu

întotdeauna aceeaşi, în 50% din rulări.

S-au aplicat metode similare pentru a genera orarul cursurilor; aici un

cromozom reprezintă, pentru fiecare curs, ora de începere şi locul de

desfăşurare, existând penalizări pentru lipsa de spaţiu în sala de curs, pentru

distanţe prea mari între sălile unde se desfăşoară două cursuri consecutive.

Metodele tradiţionale de planificare, sun mai rapide dacă restricţiile sunt de tip

“aceste evenimente nu pot avea loc simultan”, dar algoritmii genetici reprezintă

o soluţie superioară dacă există şi alte restricţii mai complicate.

40


2.4.2 Sisteme inteligente bazate pe algoritmi genetici

Mecanismul specific acestor sisteme este inspirat din funcţionare

sistemelor biologice, în sensul că încurajează soluţiile candidat capabile să

rezolve o problemă şi penalizează soluţiile fără succes. În felul acesta se obţin,

după mai multe generaţii, soluţii foarte bune pentru probleme de optimizare

complexe, cu un mare număr de parametri.

Ideea de bază a unui algoritm genetic constă în a începe cu o populaţie de

soluţii, fiecare mai performantă decât precedentele. Fazele ciclului prin care

operează un asemenea algoritm sunt:

1. crearea unei populaţii de “membri”,(soluţii candidat la rezolvarea unei

probleme),

2. selecţia membrilor care s-au adaptat cel mai bine necesităţilor problemei

de soluţionat,

3. reproducerea (se folosesc operatorii genetici de încrucişare şi mutaţie,

pentru a obţine noi membri),

4. evaluarea gradului în care noii membri corespund mai bine soluţionării

problemei,

5. abandonarea populaţiei vechi prin înlocuirea ei cu populaţia nouă din

noua generaţie.

Un asemenea ciclu se repetă până când este identificată cea mai bună

soluţie la problema în cauză.

41


fazele ciclului algoritmilor genetici

Datorită structurii lor inerent paralele, sisteme inteligente bazate pe

algoritmi genetici s-au dovedit performante în problemele de căutare şi

identificare a structurilor şi relaţiilor specifice în cadrul bazelor de date şi

bazelor de cunoştinţe voluminoase (data mining). Un succes particular s-a

obţinut cu ele în problemele de optimizare referitoare la selectarea personalului

şi selectarea portofoliilor.

Şi aceste sisteme, deoarece pot învăţa relaţii şi structuri complexe în

cadrul seturilor de informaţii şi cunoştinţe incomplete, se pot adapta

schimbărilor survenite în mediile în care funcţionează, şi pot fi utilizate ca

instrumente pentru descoperirea unor cunoştinţe noi. Ele pot oferi explicaţii la

deciziile luate într-un format perceptibil de către om.

Abandonarea

Populaţia

Evaluarea

Reproducerea

Selecţia

42


Aplicaţiile acestor sisteme s-au diversificat rapid şi s-au dovedit utile

domeniul afacerilor financiare, comerţului cu titluri, evaluării creditelor,

detecţiei fraudelor şi predicţiei falimentului. De exemplu, unii cercetători au

folosit asemenea sisteme la inferarea unor reguli pentru predicţia falimentului

întreprinderilor, pe baza indicatorilor financiari obţinuţi din bilanţ (financial

ratios). Alţi cercetători descriu modul de utilizare a algoritmilor genetici în

alocarea bugetară, în vederea asistării guvernelor şi administraţiilor locale la

adoptarea celor mai bune decizii.

43


BIBLIOGRAFIE:

1. Ion Iancu, Algoritmi genetici, Craiova 2004

2. Dumitrescu D., Algoritmi genetici şi strategii evolutive - Aplicaţii în

inteligenţa artificială şi în domenii conexe, Editura Albastră, Cluj-

Napoca, 2000;

3. Oltean M., Proiectarea şi implementarea algoritmilor, Computer Libris

Agora, Cluj-Napoca, 2000.

4. Genetic Algorithms + Data Structures = Evolution Programs, Zbigniew

Michalewicsz, Second, Extended Edition

5. Beasley D., Bull D.R., Martin R.R., An Overview of Genetic

Algorithms, Part 1, Foundations, University Computing, Vol.15, No.4,

pp. 170-181, 1993;

6. Goldberg D.E., Genetic Algorithms in Search, Optimization and

Machine Learning, Addison - Wesley, Reading,MA,1989;

7. Garey M.R., Johnson D.S., Computers and Intractability:A Guide to NP-

completeness, W.H. Freeman and Company, New York, 1978.

8. Koza J.R., Genetic Programming, MIT Press, Cambridge, MA, 1992;

44


CUPRINS:

CAPITOLUL I

NOTIUNI INTRODUCTIVE

1.1 Istoric

1.2 Importanta temei in actualitate

CAPITOLUL II

ASPECTE TEORETICE DE BAZA

2.1 Calcul evolutiv

2.1.2 Operatori genetici - calculul evolutiv

2.2 Algoritmi genetici paradigme ale calculului evolutiv

2.2.1 Atribuirea fitness-ului

2.2.2 Structura unui algoritm genetic

2.2.3 Selecţia

2.2.4 Operatorii genetici

2.3 Strategii evolutive

2.3.1 Programare evolutivă

2.3.2 Programarea genetică

2.4 Sisteme hibride

2.4.1 Aplicatii ale algoritmilor genetici

2.4.2 Sisteme inteligente bazate pe algoritmi genetici

BIBLIOGRAFIE

ALGORITMI GENETICI - · PDF file2 ALGORITMI GENETICI Vol.I CERCETARE ȘTIINȚIFICĂ CAPITOLUL...

Documents

Transcript of ALGORITMI GENETICI - · PDF file2 ALGORITMI GENETICI Vol.I CERCETARE ȘTIINȚIFICĂ CAPITOLUL...