Algoritmi Genetici

*****CUPRINS*****

INTRODUCERE………………………………………………………………………………..2

1. CE SUNT ALGORITMII GENETICI ?……………………………………………..12

1.1 OPTIMIZAREA UNEI FUNCTII SIMPLE……………………………………13

1.1.1 REPREZENTAREA………………………………………………………….15

1.1.2 POPULATIA INITIALA…………………………………………………….16

1.1.3 FUNCTIA DE EVALUARE………………………………………………..16

1.1.4 OPERATORI GENETICI…………………………………………………..17

1.1.5 PARAMETRII………………………………………………………………….18

1.1.6 REZULTATE EXPERIMENTALE………… ……………………………18

1.2 DILEMA PRIZONIERULUI……………………………………………………… 19

1.2.1 REPREZENTAREA STRATEGIEI……………………………………..20

1.2.2 SUBLINIEREA ALGORITMULUI GENETIC……………………… 21

1.2.3 REZULTATE EXPERIMENTALE……………………………………….21

1.3 PROBLEMA COMISULUI VOIAJOR…………………………………………22

1.4 URCAREA DEALULUI, INGREUNARE SIMULATA SI

ALGORITMI GENETICI…………………………………………………………..23

2. CUM FUNCTIONEAZA ALGORITMII GENETICI ?………………………….26

3. DE CE FUNCTIONEAZA ALGORITMII GENETICI ?……………………….40

4. PROBLEMA COMISULUI VOIAJOR………………………………………………49

5.IMPLEMENTAREA PRIN PROGRAM C A PROBLEMEI

COMISULUI VOIAJOR………………………………………………………………….69

BIBLIOGRAFIE………………………………………………………………………………80

=== BIBLIO ===

*****BIBLIOGRAFIE*****

1. DAVIS L, (1987) "Genetic Algorthms and Simulated Annealing"

2. DE JONG K.A, (1976) "Artificial Genetic Adaptive Sistems"

3. FOGEL L.J, (1966) "Artificial Intelligence through Simulated Evolution"

4. HOLLAND J.H, (1976) "Progress in Theoretical Biology"

5. HOLLAND J.H, (1981) "Genetic Algorithms and Adaptation"

=== CAP0 ===

*****INTRODUCERE*****

In ultimii treizeci de ani a avut loc o crestere a interesului in problema rezolvarii sistemelor bazate pe evolutie si ereditate: aceste sisteme mentin populatia de solutii potentiale,ele au un proces de selectie bazat pe potrivirea indivizilor si operatori de recombinare. Un astfel de tip de sisteme este o clasa de strategii de evolutie, de exemplu algoritmii care imita principiile evolutiei naturale pentru probleme de optimizare a parametrilor. Progamarea Evolutiva Fogel este o tehnica de cautare intr-un spatiu cu automate cu un numar redus de stari finite. Tehnicile de cautare prin imprastiere Glover mentin o populatie a punctelor de referinta si genereaza succesori prin combinatii liniare masurate. Un alt tip de sisteme bazate pe evolutie sunt algoritmii genetici Holland. In 1990, Koza a propus un sistem bazat pe evolutie pentru a cauta cel mai potrivit program pentru a rezolva o anumita problema.

Folosim un termen comun acela de programe evolutive, pentru toate sistemele bazate pe evolutie (incluzand sistemele descrise mai sus). Structura unui program evolutiv este urmatoarea:

procedure program evolutiv

begin

t0

initializare P(t)

evaluare P(t)

while (not conditie de terminare) do

begin

tt+1

selectare P(t) dintre P(t-1)

recombinare P(t)

evaluare P(t)

end

end

Programul evolutiv este un algoritm probabilistic care mentine o populatie de indivizi, pentru iteratia t. Fiecare individ reprezinta o solutie potentiala si, in orice program evolutiv, este implementata ca si o structura de date S (posibil complexa). Fiecare solutie este evaluata sa dea masura "potrivirii" ei. Apoi o noua populatie (iteratia t+1) este formata prin selectarea celor mai potriviti indivizi (pasul de selectie). Unii membri ai noii populatii sufera transformari (pasul recombinare) prin intermediul unor operatori "genetici" pentru a forma noi solutii. Exista transformari unare (tipul mutatie), care creeaza noi indivizi printr-o mica schimbare intr-un singur individ si transformari de ordin inalt (tipul incrucisare), care creeaza noi indivizi prin combinarea unor parti din mai multi indivizi . Dupa un numar de generatii programul converge – cei mai buni potentiali indivizi reprezinta solutia optima.

Sa consideram un exemplu general. Consideram un graf care trebuie sa satisfaca anumite cerinte (de exemplu cautarea topologiei optime a unei retele de comunicatii conform anumitor criterii:costul transmiterii mesajelor, fiabilitate, etc.). Fiecare individ din programul evolutiv reprezinta o posibila solutie, de exemplu fiecare individ reprezinta un graf. Populatia initiala de grafuri P(0) (generata aleator sau creata ca rezultat al unor procese aleatoare) este un punct de plecare (t=0) pentru programul evolutiv. Functia de evaluare este de obicei data, aceasta incorporand cerintele problemei. Functia de evaluare returneaza potrivirea fiecarui graf, impartind indivizii intre buni si rai. Pot fi proiectati mai multi operatori de mutatie care pot transforma un graf. Pot fi considerati unii operatori de incrucisare care sa combine structura mai multor grafuri intr-unul singur. Adesea asemenea operatori incorporeaza cunostinta problema- specific. De exemplu daca graful pe care il cautam este conectat si aciclic, un posibil operator de mutatie poate sterge marginea grafului si adauga o noua margine pentru a conecta doua subgrafuri disjuncte.Cealalta posibilitate este de a proiecta o mutatie independenta de problema si de a incorpora aceasta cerinta functie de evaluare, penalizand grafurile care nu sunt arbori. Evident multe programe evolutive pot fi formulate pentru o problema data. Astfel de programe pot diferi. Ele pot folosi diferite structuri de date pentru implementarea unui singur individ, operatori "genetici" de transformare a indivizilor, metode de creare a populatiilor intiale, metode de a lucra cu constrangerile problemei si parametrii (marimea populatie, probabilitatea aplicarii diferitilor operatori. Oricum ei impartasesc un principiu comun: o populatie de indivizi sufera anumite transformari si in timpul acestui proces de evolutie indivizii lupta pentru supravietuire.

Ideea programarii evolutive nu este noua si exista de cel putin treizeci de ani. Totusi conceptul nostru de programe evolutive este diferit de cele propuse anterior. Acesta se bazeaza in intregime pe notiunea de algoritmi genetici. Diferenta este ca noi admitem orice structura (de exemplu reprezentarea cromozomilor) potrivita pentru o problema cu un set de operatori "genetici", din moment ce algoritmii genetici folosesc siruri binare de lungime fixa (ca si cromozom, structura de date S) pentru indivizi ei si doi operatori: mutatia binara si incrucisarea binara. Cu alte cuvinte structura unui algoritm genetic este aceeasi cu cea a unui program evolutiv si diferentele sunt ascunse la un nivel inferior. Nu este nevoie ca fiecare cromozom sa fie reprezentat de un sir de biti si procesul de recombinare include alti operatori "genetici" potriviti pentru o structura si o problema data.

Aceasta este o directie relativ noua.De abia in 1985 De Jong scria:"Ce trebuie facut cind elementele din spatiul ce trebuie cercetat sunt atat de natural reprezentate prin structuri de date mai complexe ca tablouri, arbori, grafuri, etc ? Se impune o incercare de a le "liniariza" intr-o reprezentare de tip sir sau exista metode de a redefini creativ incrucisarea si mutatia pentru a opera direct asupra acestor structuri? Nu am cunostinta de vreun progres in acest domeniu."

Dupa cum am mentionat anterior, algoritmii genetici folosesc siruri binare de lungime fixa si numai doi operatori genetici de baza. Doua din primele publicatii importante despre algoritmii genetici descriu teoria si implementarea acestora.

"Importanta acestei lucrari consta in simplitatea si puternica ei abstractizare; De Jong a realizat ceva nu in ciuda simplitatii ci datorita ei. Cartea lui Holland a pus bazele teoretice pentru ca De Jong si lucrarile urmatoare despre algoritmi genetici sa identifice matematic rolul combinat al cercetarii genetice in subseturile de similitudine, al disruperii operatorului minimal si al selectiei reproductive. Mai apoi, cercetatorii au tins sa ia sugestiile teoretice in mod literal, revigorand astfel succesul implementarii codarii si al operatorilor simpli ai lui De Jong."

Desi implementarea De Jong a stabilit tehnici uzuale in concordanta cu simplificarile teoretice ale lui Holland, cercetatorii de dupa aceea au tins sa considere amandoua realizarile ca fiind inviolabile."

Se pare ca o reprezentare "naturala" a solutiei potentiale pentru o problema data plus o familie de operatori "genetici" aplicabili este folositoare in aproximarea solutiilor multor probleme si ca aceasta abordare a modelelor naturale (programarea evolutiva) este o directie de perspectiva in problema rezolvarii in general. Unii cercetatori au explorat deja folosirea altor reprezentari ca liste ordonate( pentru impachetarea binara), liste pentru elaborarea orarelor, liste de elemente variabile (pentru cablarea semiconductorilor). In ultimii zece ani au aparut diferite variatii specifice aplicatiei. Aceste variatii includ siruri de lungime variabila (incluzand siruri ale caror elemente sunt reguli if-then-else), structuri imbogatite fata de sirurile binare (de exemplu, matricile) si experimente cu operatori genetici modificati pentru a preintimpina dificultatile diferitelor probleme. In "Training Feedforward Neural Networks Using Genetic Algorithms", de D.J. Montana si L. Davis exista o descriere a unui algoritm genetic care foloseste propagarea inapoi (o tehnica de exploatare a retelei neuronale) ca si operator, impreuna cu mutatia si incrucisarea care au fost proiectate pentru domeniul retelelor neuronale. Acesti operatori sunt diferiti de incrucisarea si mutatia binara. Alti cercetatori in studiul lor despre elaborarea orarelor, au scris:

"Pentru a spori performantele algoritmului si pentru a extinde domeniul de cercetare s-a proiectat o reprezentare a unui cromozom care inmagazineaza informatia despre o problema specifica. S-au dezvoltat si operatorii de recombinare a unei probleme specifice care au avantajul informatiei aditionale."

Exista numeroase alte citate. Se pare ca cei mai multi cercetatori si-au "modificat" implementarile algoritmilor lor genetici fie prin utilizarea unor reprezentari non-sir de cromozomi fie prin proiectarea unor operatori genetici de probleme specifice pentru a se potrivi problemei de rezolvat. In "Genetic Programming: A Paradigm for Genetically Breeding Populations of Computer Programs to Solve Problems", J.R. Koza scrie:

"Reprezentarea este o problema cheie in operarea cu algoritmii genetici deoarece schemele de reprezentare pot limita drastic fereastra prin care sistemul isi observa propria lume. Totusi, asa cum Davis si Steenstrup au aratat, "in toate lucrarile lui Holland si in lucrarile multora din studentii lui, cromozomii sunt siruri de biti." Schemele bazate pe reprezentari de siruri sunt dificile si nenaturale pentru multe probleme si a fost recunoscuta nevoia de reprezentari mai puternice in ultimul timp."

Diferite reprezentari nestandard au fost create pentru probleme particulare -clasicii algoritmi genetici au fost dificil de aplicat direct problemei asa ca s-au impus modificari in structura cromozomilor. Noi vom considera structuri de date mai cuprinzatoare si operatori "genetici" aplicabili acestor structuri pentru varietatea problemei. Prin experiente asupra acestor structuri si operatori, noi am obtinut sisteme care nu mai sunt algoritmi genetici, sau, cel putin, nu din cei clasici. Titlurile mai multor rapoarte au inceput astfel: "Un algoritm genetic modificat…", "Algoritmi genetici specializati…", "Un algoritm genetic nestandard…". De asemenea exista parerea ca numele "algoritm genetic" poate fi impropriu vis-a-vis de dezvoltarea sistemelor. Davis a dezvoltat mai multe sisteme nestandard cu multi operatori pentru probleme specifice. El scria in "Adapting Operator Probabilities in Genetic Algorithms":

"Am vazut ca sistemele altor cercetatori le-au "dat multa bataie de cap" acestora in domeniul algoritmilor genetici, o sincera indoiala ca sistemul construit de noi a fost un algoritm genetic (din moment ce noi n-am folosit reprezentarea binara, mutatia binara si incrucisarea binara)."

In plus, ne putem intreba, de exemplu, daca o strategie evolutiva este un algoritm genetic. Este inversa adevarata? Pentru a evita toate chestiunile legate de clasificarea sistemelor evolutive, le vom numi simplu "programe evolutive".

De ce ne indepartam de algoritmii genetici, inspre programe evolutive mai flexibile? Desi elegant teoretizati, algoritmii genetici s-au dovedit a fi nefolositori in unele domenii. Se pare ca factorul major din spatele acestui esec este acelasi care a determinat si succesul lor: independenta de domeniu.

Una din consecintele simplitatii algoritmilor genetici (in sensul independentei lor de domeniu) este inabilitatea lor de a opera in conditii de restrangeri obisnuite. Dupa cum am mentionat anterior, in cele mai multe lucrari despre algoritmii genetici, cromozomii sunt siruri de biti -liste de 0 si 1. O problema importanta la proiectarea reprezentarii unei solutii a cromozomilor la o problema este implementarea restrangerii solutiilor (date specifice problemei). Dupa cum se spune L.Davis in "Genetic Algorithms and Simulated Annealing":

"Restrangerile care nu fi violate se pot implementa prin impunerea unor pedepse mari pentru indivizii care le violeaza, prin impunerea unor pedepse moderate sau prin crearea de decodoare de reprezentare (acestea evita crearea indivizilor care violeaza consemnul). Fiecare din aceste solutii are avantajele si dezavantajele ei. Daca una cuprinde o pedeapsa mare in rutina de evaluare si domeniul este unul in care productia de indivizi care violeaza consemnul este probabila, alta aduce riscul crearii unui algoritm genetic care isi petrece mult timp supraveghind indivizii ilegali. Mai mult, se poate intampla ca atunci cand un individ legal este gasit, aceasta ii elimina pe ceilalti si populatia converge catre acesta fara a gasi indivizi mai buni, din moment ce caile probabile spre ceilalti indivizi legali necesita productia unor indivizi ilegali ca si structuri intermediare si pedepsele pentru violarea consemnului fac putin probabila reproducerea unor asemenea structuri intermediare. Daca se impun pedepse moderate, sistemul va produce indivizi care violeaza consemnul, dar care sunt cotati mai bine decat acei ce nu o fac deoarece restul functiei de evaluare poate fi satisfacut mai degraba prin acceptarea pedepsei moderate decat prin evitarea ei. Daca se construieste un "decodor" pentru procedura de evaluare care in mod constient evita crearea unui individ ilegal din cromozom, rezultatul este un calcul intensiv frecvent derulat. Mai mult nu toate restrangerile pot fi usor implementate in acest fel".

In programarea evolutiva, problema satisfacerii constrangerii are o altfel de tenta. Nu este vorba de chestiunea selectarii functiei de selectie cu unele amendamente, ci de selectarea "celor mai bune" reprezentari ale solutiilor cromozomilor impreuna cu operatori genetici capabili sa satisfaca toate restrangerile impuse de problema. Orice operator genetic trebuie sa transmita o anumita structura caracteristica de la parinte la succesori, astfel incat structura de reprezentare joaca un rol important in definirea operatorilor genetici. Mai mult, diferite structuri de reprezentare au diferite caracteristici de potrivire relativ la reprezentarea restrangerii,ceea ce complica si mai mult problema. Aceste doua componente (operatorii si reprezentarea) se influenteaza reciproc; se pare ca orice problema va necesita o analiza atenta, aceasta ducand la o reprezentare optima pentru care operatorii genetici sunt potriviti. D.E. Glover in studiul sau despre rezolvarea problemei configuratiei unei tastaturi complexe, scria:

"Desi caracterul robust al paradigmei de cautare al algoritmilor genetici se potriveste cerintelor problemei configuratiei tastaturii, reprezentarea sirurilor de biti si operatorii idealizati nu sunt potriviti restrangerilor cerute. De exemplu daca trei biti sunt folositi pentru reprezentarea fiecarei componente a unei tastaturi simpe de numai 40 de taste, este usor de aratat ca numai una din cele structuri selectate arbitrar de 120 de biti reprezinta o configuratie legala."

Un alt citat este din lucrarea lui De Jong "Genetic Algorithm-Based Learning", unde problema comisului-voiajor este amintita:

"Folosind operatorii mutatie si incrucisare standard, un algoritm genetic va explora spatiul tuturor combinatiilor de nume de orase cand, de fapt, ne intereseaza spatiul tuturor permutarilor. Problema evidenta este ca pe masura ce N (numarul oraselor din graf) creste, spatiul permutarilor este un subset din ce in ce mai mic al spatiului combinatilor, iar puternica euristica simuland algoritmii genetici a devenit nefolositoare printr-o gresita alegere a reprezentarii."

In primele stadii ale algoritmilor genetici, problema generala a rezolvatorilor a fost faptul ca algoritmii genetici sunt proiectati ca si unelte generice pentru abordarea problemelor complexe. Totusi s-a dovedit ca este necesara incorporarea unor date specifice problemei datorita complexitatii acestor sisteme. Istoria s-a repetat: pana nu demult algoritmii genetici erau priviti ca unelte generice folositoare pentru optimizarea unor probleme complicate. Se pare ca algoritmii genetici sunt independenti de domeniu, de aceea nu pot fi folositi in unele aplicatii. Asa ca nu surprinde faptul ca programele evolutive, incorporand date specifice problemei in structurile de date ale cromozomilor si operatorii "genetici" specifici lucreaza mult mai bine.

Diferenta conceptuala de baza intre algoritmii genetici si programele evolutive este prezentata in figurile 0.1 si 0.2. Algoritmii genetici clasici, care opereaza cu siruri binare, necesita o modificare a problemei originale intr-o forma potrivita; aceasta include o distinctie clara intre solutiile potentiale si reprezentarea binara, neuitand de decodoare sau de algoritmii de reparare. De obicei, aceasta nu este usor de facut.

Problema Algoritm

genetic

Problema

modificata

FIGURA 0.1 Abordarea algoritmului genetic

Pe de alta parte, programele evolutive lasa problema neschimbata, modificand reprezentarea cromozomilor de solutii posibile (folosind structuri de date "naturale") si aplicand operatori "genetici" potriviti.

Problema Algoritm

genetic

Program

evolutiv

FIGURA 0.2 Abordarea programului evolutiv

Cu alte cuvinte a rezolva o problema specifica folosind un program evolutiv, putem fie transforma problema facand-o potrivita folosirii algoritmilor genetici (figura 0.1), fie transforma algoritmul genetic astfel incat sa se potriveasca problemei (figura 0.2). In mod vizibil, algoritmii genetici clasici folosesc prima abordare, iar programarea evolutiva pe cea de a doua. Ideea din spatele programelor evolutive este deci, destul de simpla si se bazeaza pe urmatorul motto:

"Daca muntele nu vine la Mohamed, atunci Mohamed va veni la munte." Aceasta nu este o idee foarte noua. In "Adapting Operator in Genetic Algorithms", Davis mentioneaza:

"Se parea adevarat ca pentru un timp nu putem opera cu probleme din lumea reala cu reprezentari binare si un set de operatori constand numai din mutatia si incrucisarea binara. Unul din motive este ca aproape toate domeniile lumii reale au asociat cunostinte specifice domeniului care se folosesc cand se considera transformarea unei solutii in domeniu. Cred ca algoritmii genetici sunt algoritmi potriviti de folosit in multe aplicatii ale lumii reale. De asemenea cred ca trebuie incorporate cunostinte din lumea reala in algoritm prin adaugarea acestea unui decodor sau prin extinderea setului de operatori".

Vom numi asemenea algoritmi genetici modificati "programe evolutive".

Este destul de greu de a delimita algoritmii genetici de programele evolutive. Care sunt cerintele pentru ca un program evolutiv sa devina algoritm genetic? Mentinand populatiile solutiilor potentiale? Reprezentari binare ale solutiilor potentiale? Operatori de recombinare? Existenta unei teoreme a schemei? Ipoteze bloc? Toate acestea? Este un program evolutiv pentru problema comisului-voiajor cu reprezentarea vectorilor intregi si operatori PMX un algoritm genetic? Este un program evolutiv pentru problema transportului cu matrice si opratori de incrucisare aritmetic un algoritm genetic?

In lucrarea de fata nu vom gasi raspunsuri la intrebarile de mai sus ci vom prezenta rezultate interesante ale utilizarii tehnicilor de programare evolutive asupra unei diversitati de probleme.

Dupa cum am mentionat anterior mai multi cercetatori au recunoscut potentialul din spatele diverselor modificari. In "Handbook of Genetic Algorithms "L.Davis a scris:

"Cand vorbesc unui utilizator, ii explic faptul ca planul meu este de a hibridiza tehnica algoritmilor genetici si algoritmul curent urmand urmatoarele trei principii:

* Folosirea codarii curente. Foloseste tehnica de codare a algoritmului curent in algoritmul hibrid.

* Hibridizarea unde este posibil. Incorporeaza calitatile pozitive ale algoritmului curent in algoritmul hibrid.

* Adaptarea operatorilor genetici.Creeaza operatori de mutatie si incrucisare pentru noul tip de codare prin analogia cu sirul de biti, operatorii mutatie si incrucisare. Incorporeza euristice legate de domeniu ca si operatori.

Folosim termenul "algoritm genetic hibrid" pentru algoritmi creati prin aplicarea acestor trei principii."

Se pare ca algoritmii genetici hibrizi si programele evolutive au un lucru in comun: indepartarea de clasicii, algoritmi genetici siruri de biti spre sisteme mai complexe, implicand structuri de date potrivite (folosirea codarii curente) si operatori genetici potriviti (adaptarea operatorilor genetici). Pe de alta parte, Davis a presupus existenta unuia sau mai multor algoritmi curenti (traditionali) potriviti pentru domeniul problema. Pe baza unor asemenea algoritmi poate intra in discutie constructia unor algoritmi genetici hibrizi.

Care sunt punctele tari si cele slabe ale programarii evolutive? Se pare ca un punct forte al acestei tehnici este larga ei aplicabilitate. Vom incerca sa descriem o varietate de probleme si sa discutam constructia unui program evolutiv pentru fiecare din ele. Adesea rezultatele sunt uimitoare: sistemele lucreza mult mai bine decat software-ul comercial disponibil. Un alt avantaj este legat de programele evolutive ca au un omolog in natura. Dupa cum se precizeaza in "Genetic Algorithms in Search":

"Intr-o lume in care algoritmii seriali sunt alcatuiti de obicei in mod paralel prin nenumarate artificii si trucuri, este o ironie ca algoritmii genetici sunt alcatuiti serial, prin trucuri si cotituri deopotriva."

Desigur, aceasta este adevarat pentru orice program evolutiv (bazat pe populatii). Pe de alta parte, trebuie sa recunoastem ca exista baze teoretice slabe ale programarii evolutive. Experientele cu diferite structuri de date si mutatie si incrucisare care se modifica necesita o analiza atenta, ceea ce va garanta performante rezonabile, lucru care nu s-a intamplat inca.

Totusi, unele programe evolutive au baze teoretice: pentru strategiile evolutive aplicate problemelor obisnuite se poate vedea o anumita convergenta. Algoritmii genetici au o teorema a schemei care explica modul lor de functionare. Pentru alte programe evolutive avem adesea numai rezultate interesante.

In general, metodologia strategiei de rezolvare a problemelor de inteligenta artificiala se clasifica in "robusta" si "firava". O metoda firava face putine presupuneri despre domeniul problemei; de aceea se bucura de obicei de o larga aplicabilitate. Pe de alta parte, poate suferi de combinatorica costurilor solutiilor explozive cand se extinde la probleme mai mari. Aceasta poate fi evitata prin exprimarea unor presupuneri forte legate de domeniul problemei, exploatand apoi aceste presupuneri in metoda de rezolvare a problemei. Dar un dezavantaj al acestor metode robuste este aplicabilitatea lor limitata: adesea ele necesita importante reproiectari cand sunt aplicate unor probleme conexe.

Programele evolutive se afla undeva intre metodele robuste si cele firave. Unele programe evolutive (ca si algoritmii genetici) sunt destul de neperformante daca nu se fac anumite presupuneri legate de domeniul problemei. Alte programe (GENOCOP, GAFOC, GENETIC-2) sunt probleme mai specifice cu un grad variabil de dependenta de problema. De exemplu, GENOCOP, ca toate strategiile evolutive a fost destinat rezolvarii problemelor cu optimizarea parametrilor. Sistemul poate lucra cu orice functie obiectiv cu un set de restrangeri liniare. GAFOC si GENETIC-2 lucreaza in probleme de control optimal si respectiv probleme de transport. Alte sisteme sunt potrivite pentru probleme de optimizare combinatorica (ca si elaborarea orarului, problema comisului-voiajor), sau pentru probleme de trasare a grafurilor.

Este un pic ironic: algoritmii genetici sunt priviti ca metode neperformante; totusi, in prezenta unor restrangeri specifice ei devin metode puternice. Daca am considera o functie de penalitate, un decodor sau un algoritm de reparare, acestia trebuie modelati conform aplicatiei. Pe de alta parte, programele noastre evolutive (vazute ca metode mult mai puternice si dependente de problema) par dintr-o data mult mai slabe. De exemplu, GENOCOP si GAFOC lucreaza pentru clase mari de probleme. Aceasta ne dezvaluie un imens potential in spatele abordarii programarii evolutive.

Toate aceste observatii ne-au starnit interesul in a investiga propritatile diversilor operatori genetici definiti pe structuri mai largi decat sirurile de biti. Mai mult, aceasta cercetare va duce la crearea unei noi metodologii de programare. Mai direct spus, un programator intr-un astfel de cadru va selecta structurile de date cu operatori genetici corespunzatori problemei date selectand totodata functia de evaluare si initializand populatia (ceilalti parametri se adapteaza prin alt proces genetic).

=== CAP1 ===

*****CAPITOLUL 1*****

CE SUNT ALGORITMII GENETICI ?

Stuctura unui algoritm genetic simplu este similara aceleia unui program evolutiv (vezi procedura din introducere). In timpul iteratiei t, algoritmul mentine o populatie de solutii potentiale (cromozomi, vectori), . Fiecare solutie este evaluata pentru a da masura "potrivrii" ei. Apoi, o noua populatie (iteratia t+1) este formata prin selectarea celor mai potriviti indivizi. Unii membri ai acestei noi populatii se reproduc cu ajutorul incrucisarii si al mutatiei pentru a forma noi solutii. Incrucisarea combina caracterele celor doi cromozomi parinti pentru a forma doi succesori similari prin interschimbarea segmentelor corespunzatoare ale parintilor. De exemplu, daca parintii sunt reprezentati prin vectori cu cinci dimensiuni si atunci incrucisarea cromozomilor dupa a doua gena va produce succesorii si . Intuitia din spatele aplicabilitatii operatorului de incrucisare este schimbul de informatie intre solutii potentiale diferite.

Mutatia schimba arbitrar una sau mai multe gene ale unui cromozom selectat prin schimbarea aleatoare cu o probabilitate egala cu rata mutatiei. Intuitia din spatele mutatiei este introducerea unei extravariabilitati in populatie.

Un algoritm genetic (ca si un program evolutiv) pentru o problema specifica trebuie sa aiba urmatoarele cinci componente:

* o reprezentare genetica pentru solutiile potentiale ale problemei,

* o modalitate de a crea o populatie initiala de solutii potentiale,

* o functie de evaluare care joaca rolul mediului, dand calificative solutiilor in sensul "potrivirii" lor,

* operatori genetici care schimba compozitia copiilor in timpul reproducerii,

* valori pentru diferiti parametri pe care algoritmul genetic ii foloseste (marimea populatiei, probabilitatea aplicarii diversilor operatori, etc.).

1.1 OPTIMIZAREA UNEI FUNCTII SIMPLE

In primul exemplu vom aplica un algoritm genetic pentru optimizarea unei functii simple de o variabila. Aceasta functie este :

si este trasata in figura 1.1. Problema este de a gasi x din intervalul [-1,2] care maximizeaza functia f, de exemplu, de a gasi astfel incat

pentru orice

Este relativ usor de a analiza functia f. Trebuie determinate zerourile primei derivate:

formula este echivalenta cu

Este evident faptul ca ecuatia are un numar infinit de solutii,

, pentru i=1,2…

, pentru i=1,2,…,

unde termenii reprezinta secvente descrescatoare ale numerelor reale (pentru i=1,2,…, si i=-1,-2,…) apropiate de zero.

Functia f atinge maximul ei local pentru daca i este un intreg impar, iar minimul pentru daca i este un intreg par (vezi figura 1.1).

Deoarece domeniul problemei este [-1,2], functia are un punct de maxim pentru

,

unde este putin mai mare decat

.

Presupunem ca vrem sa construim un algoritm genetic, de exemplu, care sa maximizeze functia f.

Figura 1.1 Graficul functiei

1.1.1 REPREZENTAREA

Folosim un vector binar ca si cromozom pentru a reprezenta valorile reale ale variabilei x. Lungimea vectorului depinde de precizia dorita, care, in acest exemplu, este de 6 zecimale.

Domeniul variabilei x are lungimea 3; precizia dorita implica impartirea intervalului [-1,2] in cel putin 3.000.000 de subunitati. Aceasta inseamna ca avem nevoie de un vector binar (cromozom) de 22 de biti:

.

Transformarea din sirul binar intr-un numar real x din intervalul

[-1,2] se face in doi pasi;

* convertirea sirului binar din baza 2 in baza 10:

,

* gasirea corespondentului real x:

,

unde -1 este prima valoare iar 3 lungimea intervalului.

De exemplu, un cromozom

(1000101110110101000111)

reprezinta numarul 0.637197, deoarece

si

Desigur cromozomii

(0000000000000000000000) si (1111111111111111111111)

reprezinta limitele intervalului.

1.1.2 POPULATIA INITIALA

Procesul de initializare este foarte simplu: cream o populatie de cromozomi, unde fiecare cromozom este un vector binar de 22 de biti. Toti cei 22 de biti pentru fiecare cromozom sunt initializati aleator.

1.1.3 FUNCTIA DE EVALUARE

Functia de evaluare eval pentru vectorii binari v este echivalenta cu functa f:

eval(v)=f(x), unde cromozomul v reprezinta numarul real x.

Dupa cum am mai spus, functia de evaluare joaca rolul mediului, clasificand solutiile potentiale conform potrivirii lor. De exemplu, trei cromozomi:

=(1000101110110101000111),

=(0000001110000000010000),

=(1110000000111111000101),

corespund valorilor =0.637197, =-0.958973 si =1.627888 respectiv. Deci, functia de evaluare ii va clasifica astfel:

eval()=f()=1.586345,

eval()=f()=0.078878,

eval()=f()=2.250650.

Evident, cromozomul este cel mai bun dintre cei trei, din moment ce evaluarea lui returneaza cea mai mare valoare.

1.1.4 OPERATORI GENETICI

In timpul fazei de reproducere a algoritmului genetic folosim doi operatori: mutatia si incrucisarea. Dupa cum am precizat, mutatia modifica una sau mai multe gene (pozitii in cromozomi) cu o probabilitate egala cu rata mutatiei. Presupunem ca a cincea gena a cromozomului a fost selectata pentru mutatie. Aceasta fiind 0, va trece in 1. Asa ca dupa mutatie va fi:

=(1110100000111111000101).

Aceasta reprezinta valoarea =1.721638 si f()=-0.082257. Aceasta inseamna ca mutatia a provocat o scadere importanta a valorii lui . Pe de alta parte, daca a zecea gena a fost selectata pentru mutatie in atunci

=(1110000001111111000101).

Valoarea corespunzatoare a lui este 1.630818 si f()=2.343555, o imbunatatire a valorii originale f()=2.250650.

Sa ilustram operatorul de incrucisare aplicat lui si . Presupunem ca punctul de incrucisare selectat (aleator) este dupa gena a cincea:

=(00000|01110000000010000),

=(11100|00000111111000101).

Cei doi succesori rezultati sunt:

=(00000|00000111111000101),

=(11100|01110000000010000).

Evaluand succesorii, rezulta:

f()=f(-0.998113)=0.940845,

f()=f(1.666028)=2.459245.

Observam ca succesorii au o evaluare mai buna decat fiecare din parintii sai.

1.1.5 PARAMETRII

Pentru aceasta problema am folosit urmatorii parametri: marimea populatiei pop_size = 50, probabilitatea de incrucisare pc = 0.25, probabilitatea de mutatie pm= 0.01. Prezentam in continuare cateva rezultate experimentale pentru un astfel de sistem genetic.

1.1.6 REZULTATE EXPERIMENTALE

In tabelul 1.1 se prezinta generatia pentru care am observat o imbunatatire in functia de evaluare, impreuna cu valoarea acesteia. Cel mai bun cromozom dupa 150 de generatii a fost

=(1111001101000100000101),

care corespunde valorii =1.850773.

Dupa cum era de asteptat, este mai mare decat 2.85

Tabelul 1.1 Rezultatele dupa 150 de generatii

1.2 DILEMA PRIZONIERULUI

In acest paragraf vom arata cum poate fi folosit un algoritm genetic pentru a gasi o solutie a unui joc simplu, cunoscut ca dilema prizonierului.Prezentam rezultatele obtinute de R.Axelrod in "Genetic Algorithm for the Prisoner Dilemma Problem".

Doi prizonieri stau in celule separate, fara sa poata comunica intre ei. Fiecaruia i se cere, independent, sa-l tradeze pe celalalt. Daca numai unul tradeaza, este rasplatit, iar celalalt, pedepsit. Daca o fac amandoi amandoi raman in inchisoare. Daca niciunul nu tradeaza, vor primi amandoi o rasplata moderata. Astfel, alegerea egoista a tradarii este urmata de o rasplata mai mare decat cea pentru cooperare – indiferent de ceea ce face celalalt – dar daca amandoi tradeaza, va fi mai rau pentru ei decat daca ar fi cooperat. Dilema este de a alege intre a trada si a coopera cu celalalt.

Dilema prizonierului poate fi un joc in doi, unde fiecare la rand, tradeaza sau coopereaza cu celalalt. Cei doi sunt punctati conform tabelului 1.2.

Tabelul 1.2. Scorul pentru jocul dilemei prizonierului.

O abordare cu ajutorul algoritmilor genetici este de a mentine o populatie de "jucatori", fiecare avand strategia sa proprie. La inceput, strategia fiecaruia este aleasa in mod aleator. Apoi, la fiecare pas, participantii joaca si li se noteaza punctajul. Unii sunt selectati pentru generatia urmatoare si unii din acestia sunt alesi pentru imperechere. Cand doi jucatori se imperecheaza, jucatorul nou creat are o strategie compusa din strategiile parintilor sai (incrucisare). Mutatia, ca de obicei, introduce o anumita variatie in strategiile jucatorilor prin schimbari aleatoare ale reprezentarilor acestor strategii.

1.2.1 REPREZENTAREA STRATEGIEI

Inainte de toate, avem nevoie de o metoda de a reprezenta o strategie (de exemplu, o solutie posibila). Pentru simplitate, vom considera strategii deterministe si care folosesc rezultatele celor trei mutari anterioare pentru a lua o decizie in mutarea curenta. Deoarece exista patru posibile rezultate pentru fiecare mutare, avem 4x4x4=64 posibile cazuri ale celor trei mutari anterioare. O strategie de acest fel se poate specifica prin indicarea mutarii ce trebuie facuta pentru fiecare caz posibil. Astfel, o strategie se poate reprezenta printr-un sir de 64 de biti (sau de A si C unde A reprezinta abandon, iar C reprezinta cooperare), indicand ce mutare trebuie facuta pentru fiecare din cele 64 cazuri posibile. Pentru a "porni" strategia la inceputul jocului, trebuie totodata sa specificam premisele legate de cele trei mutari ipotetice care preced inceputul jocului. Aceasta necesita inca 6 gene, rezultand 70 de gene in cromozomi.

Acest sir specifica ce va face jucatorul in orice situatie si defineste asfel o strategie particulara. Totodata, sirul serveste ca si cromozom al jucatorului in procesul evolutiv.

1.2.2 SUBLINIEREA ALGORITMULUI GENETIC

Algoritmul genetic Axelrod pentru aceasta problema are patru pasi:

1. Alegerea populatiei initiale. Fiecarui jucator ii este alocat un sir aleator de 70 de biti, reprezentand o strategie, dupa cum s-a aratat mai sus.

2. Testarea eficientei fiecarui jucator. Fiecare jucator foloseste strategia definita de cromozomul sau pentru a participa la joc. Scorul sau este valoarea medie a tuturor jocurilor sale.

3. Selectarea jucatorilor care se vor reproduce. Unui jucator cu un scor mediu i se da un calificativ.

4. Jucatorii castigatori sunt imperecheati aleatori pentru a produce doi urmasi. Strategia fiecarui urmas este determinata din strategiile parintilor sai. Aceasta se face prin folosirea incrucisarii si a mutatiei.

Dupa acesti patru pasi avem o noua populatie. Aceasta va arata modele de comportament care sunt mai asemanatoare indivizilor castigatori ai generatiei anterioare si mai putin celor necastigatori. Cu fiecare noua generatie, indivizii cu scor relativ mare este mai probabil sa transmita mai departe parti ale strategiilor lor, in timp ce pentru cei relativ necastigatori aceasta este mai putin probabila.

1.2.3 REZULTATE EXPERIMENTALE

Ruland acest program, R.Axelrod a obtinut rezultate incurajatoare. De la un inceput strict aleator, algoritmul produce populatii al caror membru mediu este la fel de castigator ca si cel mai bun algoritm euristic. Unele modele de comportament au evoluat la cei mai multi indivizi; acestea sunt:

1. Nu clatina barca: continua cooperarea dupa trei cooperari reciproce (de exemplu, C dupa (CC) (CC) (CC)). Cele trei perechi () () () reprezinta ultimile trei mutari.

a – pentru mutarile acestui jucator;

b – pentru mutarile celuilalt jucator.

2. Lasa-te provocat: renunta cand si celalalt renunta (de exemplu, A dupa (CC) (CC) (CA)).

3. Accepta scuzele: continua cooperarea dupa restabilirea acesteia ( de exemplu, C dupa (CA) (AC) (CC)).

4. Uita: coopereaza dupa restabilirea acesteia in urma unei exploatari (de exmplu, C dupa (AC) (CC) (CC)).

5. Accepta o intrerupere: renunta dupa trei abandonuri reciproce (de exemplu, A dupa (AA) (AA) (AA)).

1.3 PROBLEMA COMISULUI VOIAJOR

In aceasta sectiune, vom arata cum se pot folosi algoritmii genetici pentru rezolvarea problemei comisului voiajor.

Pe scurt, acesta trebuie sa traverseze fiecare oras din teritoriul sau, o singura data si sa se intoarca la punctul de plecare; fiind dat costul traversarii intre orase, cum ar trebui el sa-si planifice itinerariul astfel incat costul total sa fie minim?

Mai intai, trebuie sa ne punem o problema importanta legata de reprezentarea cromozomilor: lasam cromozomul reprezentat printr-un vector intreg, sau il transformam intr-un sir binar? Reprezentarea cromozomului printr-un vector binar a permis folosirea incrucisarii sau a mutatiei. Aplicandu-le, am obtinut succesori, de exemplu, succesori in spatiul de cautare. Nu este cazul la problema de fata. In reprezentarea binara a unei probleme cu n orase, fiecare oras trebuie reprezentat printr-un sir de [] biti; un cromozom e un sir de biti. O mutatie poate produce o secventa de orase care nu este un tur complet: putem trece printr-un oras de doua ori. Mai mult pentru o problema cu 20 de orase (avem nevie de 5 biti pentru reprezentarea unui oras), unele secvente de 5 biti (de exemplu, 10101) nu corespund nici unui oras. Probleme similare apar la aplicarea incrucisarii. Evident, daca folosim mutatia si incrucisarea in modul descris mai sus, vom avea nevoie de un fel de "algoritm de reparare"; un asemenea algoritm "repara" cromozomul, mutandu-l din nou in spatiul de cautare.

Se pare ca reprezentarea ca vector intreg este mai buna: in loc de a utiliza algoritmi de reparare, putem introduce date ale problemei in operatori: astfel ei vor evita "intentionat" producerea unui individ ilegal. In aceasta abordarenvom folosi reprezentarea ca intreg: un vector reprezinta un tur: de la , la , de la , la si inapoi la (v este o permutare a lui (1 2…n)).

Pentru procesul de initializare putem fie utiliza niste euristice (de exemplu putem accepta cateva iesiri dintr-un algoritm saturat pentru problema comisului voiajor, incepand din diferite orase), fie initializa populatia printr-o permutatie aleatoare a lui (1 2…n).

Este relativ usor de a gasi operatori unari care vor face ordonari mai bune ale sirurilor. Totusi, folosind numai operatori unari este mai greu de gasit aceste ordonari bune. Mai mult, forta algoritmului rezida in schimbul de informatie structurata al combinarii de incrucisare a celor mai buni indivizi. Asa ca avem nevoie de un operator asemanator incrucisarii care sa exploateze asemanarile importante dintre cromozomi. Asa ca vom folosi un fel de operator OX care, avand doi parinti, formeaza un succesor alegand o secventa dintr-un tur – parinte si pastrand ordinea relativa de la celalalt parinte. De exemplu, daca parintii sunt

(1 2 3 4 5 6 7 8 9 10 11 12) si

(7 3 1 11 4 12 5 2 10 9 6 8)

si partea aleasa este

(4 5 6 7),

succesorul rezultat este

(1 11 12 4 5 6 7 2 10 9 8 3).

Conform cerintelor, succesorul are o relatie structurala cu amandoi parintii. Rolul acestora se poate inversa la producerea urmatorului succesor.

1.4 URCAREA DEALULUI, INGREUNARE SIMULATA SI ALGORITMI GENETICI

In aceasta sectiune vom analiza trei algoritmi pentru optimizarea unei probleme simple. Acest exemplu sublineaza unicitatea abordarii algoritmilor genetici.

Spatiul de cautare sete un set de siruri binare v cu lungimea 30. Functia obiectiv f de maximizat este

,

unde functia one(v) ne da numarul bitilor pusi pe 1 din sirul v. De exemplu urmatoarele 3 siruri:

=(110110101110101111111011011011),

=(111000100100110111001010100011),

=(000010000011001000000010001000),

vor avea ca si corespondenti

unde one()=22, one()=15, one( )=6

Functia f este liniara si se foloseste pentru ilustrarea ideii din spatele acestor trei algoritmi. Totusi, caracteristica interesanta a lui f este ca are un maxim global pentru

=(111111111111111111111111111111),

, si un maxim local pentru

=(000000000000000000000000000000),

.

Variantele algoritmilor de tip urcarea dealului difera prin modul in care un nou sir este selectat pentru comparatie cu sirul curent. O varianta simpla (iterativa) cu MAX iteratii este reprezentata in procedura 1.2 (cu panta cea mai abrupta).

procedure urcare iterata

begin

t0

repeat

localFALSE

selectare sir curent aleator

evaluare

repeat

selectie 30 de noi siruri din vecinatatea lui prin comutarea unor biti din

selectarea sirului din noul set de siruri, avand cea mai mare valoare a functiei obiectiv f

if f()<f()

then

else localTRUE

until local

tt+1

until t=MAX

end

Procedura 1.2 Urcare iterata simpla

Initial, se considera toti cei 30 de vecini, iar vn care returneaza cea mai mare valoare f() este selectat pentru a fi comparat cu sirul curent. Daca f() < f(), noul sir devine sir curent. Alfel nu este posibila o imbunatatire locala: algoritmul a ajuns la un optim, local sau global, iar local are valoarea TRUE. In acest caz, urmatoarea iteratie se executa cu un sir curent ales aleator.

=== CAP2 ===

*****CAPITOLUL 2*****

CUM FUNCTIONEAZA ALGORITMII GENETICI ?

In acest capitol vom discuta pasii unui algoritm genetic pentru o problema de optimizare simpla cu parametri.

Daca problema de optimizare este minimizarea unei functii f, aceasta este echivalent cu maximizarea unei functii g, unde g=-f, de exemplu,

min f(x) = max g(x) = max{-f(x)}.

Mai mult, putem presupune ca functia obiectiv f ia valori pozitive; altfel adunam o constanta pozitiva C:

max g(x) = max{g(x)+C}.

Presupunem ca dorim sa maximizam o functie de k variabile, . Presupunem ca fiecare variabila ia valori pe domeniul si pentru orice . Vrem sa optimizam pe f cu o anumita precizie (de exemplu 6 zecimale).

Evident, pentru obtinerea acestei precizii, domeniul se divide in intervale. Definim ca si cel mai mic intreg astfel incat . O reprezentare a fiecarui de lungime satisface precizia dorita. Formula urmatoare interpreteaza fiecare asemenea sir:

,

unde zecimal () reprezinta valoarea zecimala a sirului binar.

Fiecare cromozom (ca si solutie potentiala) este reprezentat printr-un sir de lungime ; primii biti formeaza o valoare din intervalul , urmatorul grup de una din intervalul s.a.m.d.

Pentru initializarea populatiei, putem da o valoare pop_size numarului de cromozomi aleator la nivel de bit. Totusi, daca avem date despre distributia optimelor potentiale, o putem folosi la aranjarea setului initial de solutii potentiale.

Restul algoritmului este cu cautare inainte: in fiecare generatie evaluam fiecare cromozom (aplicand functia f secventelor decodate ale variabilelor), selectam noua populatie respectand distributia de probabilitate bazata pe valorile de potrivire si recombinam cromozomii din noua populatie folosind mutatia si incrucisarea. Dupa un numar de generatii, cand nu se mai observa imbunatatiri, cei mai buni cromozomi reprezinta o solutie optima (posibil globala).

Pentru procesul de selectie se foloseste o roata de ruleta cu marimea sloturilor depinzand de potrivire. Aceasta se construieste astfel:

calcularea valorii de potrivire eval() pentru fiecare cromozom (i=1,…,pop_size).

aflarea potrivirii totale a populatie:

calculul probabilitatii de selectare pi pentru fiecare cromozom (i=1,…,pop_size):

calculul probabilitatii cumulate pentru fiecare cromozom (i=1,…,pop_size):

Procesul de selectie se face invartind roata de pop_size ori; de fiecare data selectam un cromozom pentru o noua populatie astfel:

generarea unui numar aleator din intervalul [0,1].

daca r < se selecteza primul cromozom (); altfel se selecteaza cromozomul i astfel incat .

Evident, unii cromozomi vor fi selectati de mai multe ori. Aceasta este in concordanta cu teorema schemei: cei mai buni cromozomi se copiaza, cei medii raman cum sunt, iar cei mai neperformanti dispar.

Putem acum sa aplicam incrucisarea indivizilor din noua populatie. Unul din parametrii sistemului este probabilitatea de incrucisare . Aceasta ne da numarul de cromozomi care sufera incrucisare. Procedam astfel pentru fiecare cromozom din noua populatie:

generarea unui numar aleator din intervalul [0,1];

daca r < selectam cromozomul pentru incrucisare.

Incrucisam in mod aleator cromozomii selectati: pentru fiecare pereche de cromozomi cuplati generam un intreg aleator pos din intervalul [1,m-1]. Numarul pos indica pozitia punctului de incrucisare. Doi cromozomi :

sunt inlocuite cu o pereche de succesori:

.

Urmatorul operator, mutatia, opereaza la nivel de bit. Alt parametru al sistemului, , probabilitatea de mutatie, ne da numarul de biti mutati . Fiecare bit (din cromozomii intregii populatii) are aceeasi sansa de a suferi o mutatie, de exemplu trecerea din 0 in 1 sau invers. Procedam astfel pentru fiecare cromozom din populatia curenta si pentru fiecare bit din cromozom:

generarea unui numar aleator r din intervalul [0,1];

daca r < , bitul se modifica.

Astfel noua populatie este gata de o noua evaluare. Evaluarea se foloseste la gasirea distributiei de probabilitate (pentru urmatorul proces de selectie), de exemplu, constructia ruletei cu marimea sloturilor conform valorilor potrivirii curente. Restul evolutiei este o repetitie ciclica a pasilor de mai sus (vezi procedura din introducere).

Intregul proces este ilustrat printr-un exemplu. Rulam o simulare a algoritmului genetic pentru optimizarea unei functii. Presupunem marimea populatiei pop_size = 20 , iar probabilitatea operatorilor, si .

Consideram urmatoarea functie de optimizat:

,

unde

Presupunem ca precizia ceruta este de 4 zecimale pentru fiecare variabila. Domeniul variabilelei are lungimea 15.1; aceasta implica impartirea domeniului [-3.0, 12.1] in cel putin parti egale. Aceasta inseamna ca sunt necesari 18 biti ca prima parte a cromozomului:

Domeniul variabilei are lungimea 1.7; aceasta inseamna ca domeniul [4.1, 5.8] se imparte in cel putin parti egale. Aceasta inseamna ca sunt necesari 15 biti pentru a reprezenta a doua parte a cromozomului:

Lungimea totala a cromozomului (vectorul solutie) este atunci m=18+15=33 biti; sa consideram un cromozom ca exemplu:

(010001001011010000111110010100010).

Primii 18 biti 010001001011010000, reprezinta

Urmatorii 15 biti, 111110010100010, reprezinta

Deci cromozomul(010001001011010000111110010100010) corespunde intervalului (x1,x2)=(1.052426,5.755330). Potrivirea acestui cromozom este

f(1.052426, 5.755330)=20.252640.

Pentru a optimiza functia f folosind un algoritm genetic, cream o populatie de pop_size =20. Lungimea sirului este m=33 (si, implicit, a lungimii schemei template). Mai presupunem ca, la timpul t populatia este reprezentata prin sirurile urmatoare:

=(100110100000001111111010011011111)

=(111000100100110111001010100011010)

=(000010000011001000001010111011101)

=(100011000101101001111000001110010)

=(000111011001010011010111111000101)

=(000101000010010101001010111111011)

=(001000100000110101111011011111011)

=(100001100001110100010110101100111)

=(010000000101100010110000001111100)

=(000001111000110000011010000111011)

=(011001111110110101100001101111000)

=(110100010111101101000101010000000)

=(111011111010001000110000001000110)

=(010010011000001010100111100101001)

=(111011101101110000100011111011110)

=(110011110000011111100001101001011)

=(01101011111100111101000110111110)

=(011101000000001110100111110101101)

=(000101010011111111110000110001100)

=(101110010110011110011000101111110)

In timpul fazei de evolutie calculam valorile functiei de potrivire dintre valorile x1 si x2 obtinute. Rezulta:

Evident cromozomul v15 este cel mai puternic, iar cromozomul v2 este cel mai slab.

Sistemul construieste o ruleta pentru procesul de selectie. Potrivirea totala a populatiei este:

Probabilitatea selectarii pi pentru fiecare cromozom vi (i=1,…,20) este :

p1=eval(v1)/F=0.067099 p2=eval(v2)/F=0.019547

p3=eval(v3)/F=0.050355 p4=eval(v4)/F=0.044899

p5=eval(v5)/F=0.065350 p6=eval(v6)/F=0.046677

p7=eval(v7)/F=0.041315 p8=eval(v8)/F=0.043315

p9=eval(v9)/F=0.041590 p10=eval(v10)/F=0.054873

p11=eval(v11)/F=0.060372 p12=eval(v12)/F=0.038712

p13=eval(v13)/F=0.070444 p14=eval(v14)/F=0.051257

p15=eval(v15)/F=0.077519 p16=eval(v16)/F=0.061549

p17=eval(v17)/F=0.035320 p18=eval(v18)/F=0.097350

p19=eval(v19)/F=0.051823 p20=eval(v20)/F=0.035244

Probabilitatea cumulativa qi pentru fiecare cromozom vi (i=1,…,20) este:

q1=0.067099 q2=0.086647 q3=0.137001 q4=0.181890

q5=0.247240 q6=0.293917 q7=0.335232 q8=0.381546

q9=0.423137 q10=0.478009 q11=0.538381 q12=0.577093

q13=0.647537 q14=0.698794 q15=0.776314 q16=0.837863

q17=0.873182 q18=0.912932 q19=0.964756 q20=1.000000

Acum suntem gata de a invarti ruleta de 20 de ori; de fiecare data selectam un singur cromozom pentru noua populatie. Presupunem ca secventa aleatoare de 20 de numere din [0,1] este:

0.513870 0.175741 0.308652 0.534534

0.947628 0.171736 0.702231 0.226431

0.494773 0.424720 0.703899 0.389647

0.277226 0.368071 0.983437 0.005398

0.765682 0.646473 0.767139 0.780237

Primul numar r = 0.513870 este mai mare decat q10 si mai mic decat q11, deci cromozomul v11 este selectat pentru noua populatie; al doilea numar r =0.175741 este mai mare decat q3 si mai mic decat q4, deci cromozomul v4 este selectat pentru noua populatie, etc.

In final, noua populatie va consta din urmatorii cromozomi:

v1'=(011001111110110101100001101111000) (v11)

v2'=(100011000101101001111000001110010) (v4)

v3'=(001000100000110101111011011111011) (v7)

v4'=(011001111110110101100001101111000) (v11)

v5'=(000101010011111111110000110001100) (v19)

v6'=(100011000101101001111000001110010) (v4)

v7'=(111011101101110000100011111011110) (v15)

v8'=(000111011001010011010111111000101) (v5)

v9'=(011001111110110101100001101111000) (v11)

v10'=(000010000011001000001010111011101) (v3)

v11'=(111011101101110000100011111011110) (v15)

v12'=(010000000101100010110000001111100) (v9)

v13'=(000101000010010101001010111111011) (v6)

v14'=(100001100001110100010110101100111) (v8)

v15'=(101110010110011110011000101111110) (v20)

v16'=(100110100000001111111010011011111) (v1)

v17'=(000001111000110000011010000111011) (v10)

v18'=(111011111010001000110000001000110) (v13)

v19'=(111011101101110000100011111011110) (v15)

v20'=(110011110000011111100001101001011) (v16)

Acum putem aplica primul operator de recombinare, incrucisarea, indivizilor din noua populatie. Probabilitatea de incrucisare pc, asa ca ne asteptam ca (in medie) 25% din cromozomi sa sufere incrucisarea. Vom proceda astfel: pentru fiecare cromozom din noua populatie generam un numar aleator r din intervalul [0,1]; daca r<0.25, cromozomul este selectat pentru incrucisare.

Presupunem ca secventa de numere aleatoare este;

0.822951 0.151932 0.625477 0.314685

0.346901 0.917204 0.519760 0.401154

0.606758 0.785402 0.031523 0.869921

0.166525 0.674520 0.758400 0.581893

0.389248 0.200232 0.355635 0.826927

Aceasta inseamna ca cromozomii v2',v11',v13' si v18' sunt selectati pentru incrucisare. (Numarul cromozomilor selectati fiind par, ii putem imperechea usor.) Pe acestia ii imperechem aleator: de exemplu, primii doi si ultimii doi. Pentru fiecare din perechi, generam un intreg aleator, pos, din intervalul [1,32]. Acest numar indica pozitia punctului de incrucisare. Prima pereche de cromozomi este

v2'=(100011000|101101001111000001110010)

v11'=(111011101|101110000100011111011110)

iar numarul generat pos=9. Cromozomii sunt taiati dupa bitul 9 si inlocuiti cu o pereche a urmasilor lor:

v2"=(100011000|101110000100011111011110)

v11"=(111011101|101101001111000001110010)

Urmatoarea pereche este

v13'=(00010100001001010100|1010111111011)

v18'=(11101111101000100011|0000001000110)

iar pos=20

v13"=(00010100001001010100|0000001000110)

v18"=(11101111101000100011|1010111111011)

Populatia curenta este acum

v1'=(011001111110110101100001101111000)

v2"=(100011000101110000100011111011110)

v3'=(001000100000110101111011011111011)

v4'=(011001111110110101100001101111000)

v5'=(000101010011111111110000110001100)

v6'=(100011000101101001111000001110010)

v7'=(111011101101110000100011111011110)

v8'=(000111011001010011010111111000101)

v9'=(011001111110110101100001101111000)

v10'=(000010000011001000001010111011101)

v11"=(111011101101101001111000001110010)

v12'=(010000000101100010110000001111100)

v13"=(000101000010010101000000001000110)

v14'=(100001100001110100010110101100111)

v15'=(101110010110011110011000101111110)

v16'=(100110100000001111111010011011111)

v17'=(000001111000110000011010000111011)

v18"=(111011111010001000111010111111011)

v19'=(111011101101110000100011111011110)

v20'=(110011110000011111100001101001011)

Urmatorul operator de recombinare, mutatia, se face bit cu bit. Probabilitatea mutatiei este pm=0.01, asa ca ne asteptam ca 1% din biti sa sufere mutatii. Exista m x pop_size= 33×20= 660 biti in intreaga populatie; ne asteptam sa aiba loc 6.6 mutatii per generatie. Generam un numar aleator din intervalul [0,1]; daca r<0.01, va avea loc o mutatie.

Aceasta inseamna ca avem de generat 660 de numere aleatoare. In modelarea rularii cinci din aceste numere sunt mai mici decat 0.01; numarul bitului si numarul aleator este urmatorul:

Urmatorul tabel transforma pozitia bitului in numarul cromozomului si in pozitia din cadrul cromozomului:

Aceasta inseamna ca patru cromozomi sunt afectati de mutatie; unul din ei (al xiii-lea) va avea doi biti schimbati. Populatia finala este cea de mai jos:

v1=(011001111110110101100001101111000)

v2=(100011000101110000100011111011110)

v3=(001000100000110101111011011111011)

v4=(011001111110110101100001101111000)

v5=(000101010011111111110000110001100)

v6=(100011000101101001111000001110010)

v7=(111011101101110000100011111011110)

v8=(000111011001010011010111111000101)

v9=(011001111110110101100001101111000)

v10=(000010000011001000001010111011101)

v11=(111011101101101001111000001110010)

v12=(010000000101100010110000001111100)

v13=(000101000010010101000000001000110)

v14=(100001100001110100010110101100111)

v15=(101110010110011110011000101111110)

v16=(100110100000001111111010011011111)

v17=(000001111000110000011010000111011)

v18=(111011111010001000111010111111011)

v19=(111011101101110000100011111011110)

v20=(110011110000011111100001101001011)

Tocmai am parcurs o iteratie (o generatie) a buclei while din procedura din introducere. In timpul fazei evolutive "decodificam" fiecare cromozom si-i calculam valoarea functiei de potrivire dintre (x1,x2) valori tocmai decodificate. Obtinem:

Potrivirea totala a noii populatii F este 447.049688, mult mai mare decat cea a populatiei anterioare, 387.776822. De asemenea cel mai bun cromozom de acum v11 are o mai buna evaluare (33.351874) decat cel mai bun cromozom al populatiei anterioare, v15 (30.060205).

Observam ca potrivirea unor cromozomi din populatiile anterioare este mai buna decat valoarea 35.477938 a celor mai buni cromozomi dupa 1000 de generatii. De exemplu, cel mai bun cromozom din generatia 396 a avut valoarea 38.827553.

=== CAP3 ===

*****CAPITOLUL 3*****

DE CE FUNCTIONEAZA ALGORITMII GENETICI ?

Aspectele teoretice ale algoritmilor genetici se bazeaza pe reprezentarea binara a solutiilor si pe notiunea de schema, care permite explorarea similitudinilor dintre cromozomi. Schema este formata prin introducerea simbolului indiferent (*) in alfabetul genelor. Schema reprezinta toate sirurile (un hiperplan, un subset al spatiului de cautare), care au, in loc de simbolul *, 0 si 1.

De exemplu, sa consideram sirurile si schemata de lungime 10. Schema (*111100100) are ca echivalent doua siruri

{(0111100100) ,(1111100100) },

iar schema (*1*1100100) patru siruri:

{(0101100100) ,(0111100100) ,(1101100100) ,(1111100100) }.

Bineinteles, schema (0111100100) reprezinta un singur sir,(0111100100), iar schema (**********) reprezinta toate sirurile de lungime 10. Toata schema reprezinta siruri, unde r este numarul simbolurilor indiferent din schema template.

Pe de alta parte, fiecare sir de lungime m are ca echivalente schemate. Luam ca exemplu un sir , (1001110001). Sirului ii corespund urmatoarele schemate:

(1001110001)

(*001110001)

(1*01110001)

(10*1110001)

…

(100111000*)

(**01110001)

(*0*1110001)

…

(10011100**)

(***1110001)

…

(**********),

Considerand siruri de lungime m, exista schemate posibile. Intr-o populatie de marime n se pot reprezenta intre si schemate diferite.

Schemate diferite au caracteristici diferite. Exista doua importante proprietati ale schemei, ordinea si lungimea de definire. Teorema schemei va fi formulata pe baza acestor proprietati.

Ordinea schemei S (se noteaza o(S)) este un numar pozitiilor de 0 si 1; este vorba de pozitiile ne-indiferente. Ordinea defineste specificitatea schemei. De exemplu urmatoarele trei schemate, cu lungimea 10

=(***001*110),

=(****00**0*),

=(11101**001),

au urmatoarele ordini:

,

iar schema S3 este cea mai specifica.

Notiunea de ordine este folositoare in calculul probabilitatii de supravietuire a schemei relativ la mutatii.

Lungimea de definire a schemei S (notata ) este distanta dintre prima si ultima pozitie fixata a sirului. Ea defineste cat de compacta este informatia continuta in schema. De exemplu,

.

Schema cu o singura pozitie fixa are lungimea de definire 0. Aceasta notiune este folositoare in calculul probabilitatii de supravietuire relativ la incrucisare. Dupa cum s-a aratat in introducere, procesul evolutiv simulat consta in executia repetata a urmatorilor patru pasi:

tt+1

selectia lui P(t) din P(t-1)

recombinare P(t)

evaluare P(t)

Primul pas (tt+1) incrementeaza unitatea de timp; in timpul ultimului pas (evaluare P(t)) evaluam populatia curenta. Fenomenul principal al procesului evolutiv are loc in cadrul pasilor de selectie si recombinare. Vom discuta efectele acestor pasi asupra numarului schematelor reprezentate in populatie; demonstram toate formulele prin exemple.

Presupunem ca pop_size =20, lungimea sirului este m=33 (si, implicit, a lungimii schemei template). Mai presupunem ca, la timpul t populatia este reprezentata prin sirurile urmatoare:

=(100110100000001111111010011011111)

=(111000100100110111001010100011010)

=(000010000011001000001010111011101)

=(100011000101101001111000001110010)

=(000111011001010011010111111000101)

=(000101000010010101001010111111011)

=(001000100000110101111011011111011)

=(100001100001110100010110101100111)

=(010000000101100010110000001111100)

=(000001111000110000011010000111011)

=(011001111110110101100001101111000)

=(110100010111101101000101010000000)

=(111011111010001000110000001000110)

=(010010011000001010100111100101001)

=(111011101101110000100011111011110)

=(110011110000011111100001101001011)

=(01101011111100111101000110111110)

=(011101000000001110100111110101101)

=(000101010011111111110000110001100)

=(101110010110011110011000101111110)

Notam cu numarul sirurilor din populatie, la timpul t, care au ca echivalent schema S.De exemplu, pentru schema data

=(****111**************************)

=3, deoarece exista trei siruri, v13, v15 si v16 echivalente cu schema .Ordinea schemei S0 este 3, iar lungimea de definire este 2.

O alta proprietate a schemei este potrivirea la momentul t, eval (S,t). Este definita ca si media potrivirilor tuturor sirurilor in populatia echivalenta schemei S. Presupunem ca exista p siruri {} in populatia echivalenta schemei S la momentul t. Atunci

In timpul pasului de selectie este creata o populatie intermediara:pop_size=20, numarul sirurilor selectate. Fiecare sir este copiat o data, de mai multe ori sau deloc, in functie de potrivirea lui. Dupa cum am vazut in capitolul anterior, sirul este selectat cu probabilitatea(F(t) este potriviea totala a intregii populatii la momentul t,

Dupa pasul de selectie ne asteptam sa avem (S,t+1) siruri echivalente cu schema S. Deoarece pentru un sir oarecare echivalent cu schema S, probabilitatea selectiei lui este egala cu eval (S,t)/F(t), numarul sirurilor echivalente cu schema S este (S,t), iar numarul selectarilor este pop_size, in mod evident

(S,t+1) =

Putem rescrie formula de mai sus: tinand cont de potrivirea medie a populatiei

, putem scrie:

(S,t+1) = (3.1)

O schema “peste nivelul mediu” primeste un numar crescand de siruri in generatia urmatoare, una “sub nivelul mediu” -un numar in scadere , iar una de nivel mediu ramane la acelasi stadiu.

Efectul pe termen lung al regulii de mai sus este clar. Presupunand ca schema S ramane peste nivelul mediu cu

Aceasta este o ecuatie in progresie geometrica: putem spune nu numai ca o schema “peste medie” primeste un numar crescator de siruri in urmatoarea generatie, dar si ca primeste un numar exponential crescator de siruri in urmatoarea generatie.

Ecuatia (3.1) se numeste ecuatia de crestere reproductiva a schemei.

Intorcandu-ne la schema S0, avem trei siruri, v13 ,v15 si v16 (la timpul t) care sunt echivalente cu S0; potrivirea eval (S0) a schemei este

In acelasi timp, potrivirea medie a intregii populatii este

iar ratia potrivirii schemei S0 fata de potrivirea medie a populatiei este

Aceasta inseamna ca daca schema S0 ramane deasupra mediei prin factorul constant 1.396751, atunci, la momentul (t+1), ne asteptam sa avem siruri echivalente cu S0 (4 sau 5), iar la momentul asemenea siruri (foarte probabil, 6 siruri), etc.

Intuitia este ca schema S0 defineste o parte importanta a spatiului de cautare si este modelata exponential.

Sa verificam aceste predictii in cazul exemplului pentru schema S0. In populatia de la timpul t, schema S0 are ca echivalenti sirurile v13, v15 si v16. In capitolul anterior am simulat procesul de selectie folosind aceeasi populatie. Noua populatie este urmatoarea:

v1'=(011001111110110101100001101111000)

v2'=(100011000101101001111000001110010)

v3'=(001000100000110101111011011111011)

v4'=(011001111110110101100001101111000)

v5'=(000101010011111111110000110001100)

v6'=(100011000101101001111000001110010)

v7'=(111011101101110000100011111011110)

v8'=(000111011001010011010111111000101)

v9'=(011001111110110101100001101111000)

v10'=(000010000011001000001010111011101)

v11'=(111011101101110000100011111011110)

v12'=(010000000101100010110000001111100)

v13'=(000101000010010101001010111111011)

v14'=(100001100001110100010110101100111)

v15'=(101110010110011110011000101111110)

v16'=(111001100110000101000100010100001)

v17'=(111001100110000100000101010111011)

v18'=(111011111010001000110000001000110)

v19'=(111011101101110000100011111011110)

v20'=(110011110000011111100001101001011)

La momentul (t+1), schema S0 are ca echivalenti cinci siruri:

v7', v11', v18', v19' si v20'.

Totusi folosirea exclusiv a selectiei nu introduce alte solutii potentiale in spatiul de cautare; selectia numai copiaza niste siruri pentru formarea unei populatii ulterioare. Asa ca urmatorul pas al ciclului evolutiv, recombinarea, preia responsabilitatea introducerii unor noi indivizi in populatie. Aceasta se face prin doi operatori genetici: mutatia si incrucisarea. Vom discuta efectele efectul acestora asupra numarului probabil de schemate din populatia care urmeaza.

Sa incepem cu incrucisarea si sa consideram urmatorul exemplu. Dupa cum am vazut in capitolul anterior, un singur sir din populatie, sa spunem, v18'

(111011111010001000110000001000110),

este echivalentul a 230 schemate; in particular, sirul este echivalent schematelor

S0=(****111**************************) si

S1=(111****************************10).

Presupunem ca sirul de mai sus a fost selectat pentru incrucisare (ca si in cap.2). Mai presupunem (conform experimentelor din capitolul 2, unde v18' a fost incrucisat cu v13' ) ca pozitia de incrucisare este pos=20. In mod evident, schema S0 supravietuieste unei astfel de incrusari, adica unul din succesori este inca echivalent cu S0. Motivul este faptul ca punctul de incrucisare pastreaza secventa ‘111’ la a cincea, a sasea si a saptea pozitie in unul din succesori:

Perechea

v18'=(11101111101000100011|0000001000110)

v13'=(00010100001001010100|1010111111011),

va produce

v18"=(11101111101000100011|1010111111011),

v13"=(00010100001001010100|0000001000110).

Pe de alta parte, schema S1 se distruge: nici un urmas nu va fi echivalent cu ea. Motivul este faptul ca pozitiile fixe ‘111’ de la inceputul sirului si pozitiile fixe ‘10’ de la sfarsit se afla in succesori diferiti.

Evident, lungimea de definire a unei scheme joaca un rol important in probabilitatea distrugerii si supravietuirii ei. Lungimea de definire a schemei S0 a fost , iar cea a schemei S1 a fost .

In general, punctul de incrucisare este selectat uniform dintre m-1 posibile puncte. Aceasta implica o probabilitate de distrugere a schemei S

si, in consecinta, probabilitatea de supravietuire a schemei este

Intr-adevar, probabilitatile de distrugere si de supravietuire ale schematelor S0 si S1 sunt:

,

deci rezultatul a fost previzibil.

=== CAP4 ===

*****CAPiTOLUL 4*****

PROBLEMA COMISULUI VOIAJOR

Problema comisului este conceptual simpla: comisul trebuie sa viziteze fiecare oras din teritoriul sau o singura data si apoi sa se intoarca la punctul de plecare. Dandu-se costul trecerii dintr-un oras in altul, care trebuie sa fie itinerariul sau astfel incat costul total sa fie minim? Spatiul de cautare este un set de permutari a n orase. Orice permutare de n ne da o solutie (care este un tur complet al oraselor). Solutia optimala este o permutare care ne da costul minim al intregului tur. Spatiul de cautare este n!.

In ultimii ani, s-au discutat mai mult reprezentarile vectoriale (vis-a-vis de problema comisului): reprezentarea partial-maparii(PMX), cea ordinala(OX) si cea a caii(CX). Fiecare din ele are proprii sai operatori genetici. Deoarece este relativ usor de a gasi un operator de mutatie care sa introduca o mica schimbare in tur, ne vom focaliza asupra operatorilor de incrucisare. In toate cele trei reprezentari, un tur este o lista de orase.

REPREZENTAREA CAII

Aceasta este cea mai naturala reprezentare a turului. De exemplu, un tur

5 – 1 – 7 – 8 – 9 – 4 – 6 – 2 – 3

se reprezinta astfel

(5 1 7 8 9 4 6 2 3).

S-au definit trei operatori de incrucisare: incrucisare partial mapata, de ordine si de ciclu.

* PMX-creeaza succesori prin alegerea unui subgraf de la unul din parinti si pastrand ordinea si pozitia cator mai multe orase de la celalalt parinte. Un subgraf se selecteaza alegand doua puncte de taiere aleatoare, care vor fi margini pentru operatia de cautare. De exemplu, cei doi parinti

p1=(1 2 3 | 4 5 6 7 | 8 9)

p2=(4 5 2 | 1 8 7 6 | 9 3)

vor produce succesori astfel: mai intai segmentele dintre punctele de taiere se interschimba (simbolul 'x' se poate interpreta ca 'stare prezenta necunoscuta'):

o1=(x x x | 1 8 7 6 | x x)

o2=(x x x | 4 5 6 7 | x x).

Si interschimbarea defineste o serie de mapari:

1 <-> 4, 8 <-> 5, 7 <-> 6, 6 <-> 7.

Acum putem marca orase mai departe (plecand de la primii parinti), pentru care nu avem conflict:

o1=(x 2 3 | 1 8 7 6 | x 9)

o2=(x x 2 | 4 5 6 7 | 9 3).

In final, primul x din succesorul o1 (care ar trebui sa fie 1, dar a fost conflict) este inlocuit cu 4, din cauza maparii 1 <-> 4. In mod smilar, al doilea x din succesorul o1 este inlocuit cu 5, iar x si x din o2 sunt 1 si 8. Urmasii sunt

o1=(4 2 3 | 1 8 7 6 | 5 9)

o2=(1 8 2 | 4 5 6 7 | 9 3).

* OX-formeaza urmasi prin alegerea unui subgraf al turului de la un parinte si pastrand ordinea relativa a oraselor de la celalalt parinte. De exemplu, doi parinti

p1=(1 2 3 | 4 5 6 7 | 8 9) si

p2=(4 5 2 | 1 8 7 6 | 9 3)

se vor reproduce astfel: mai intai, segmentele dintre punctele de taiere sunt copiate in sirurile succesor:

o1=(x x x | 4 5 6 7 | x x)

o2=(x x x | 1 8 7 6 | x x)

Incepand cu urmatorul punct de taiere din parinte, orasele din celalalt parinte sunt copiate in aceeasi ordine, exceptand simbolurile deja prezente. Ajungand la sfarsitul sirului, continuam din primul loc al sirului. Secventa de orase din al doilea parinte (din al doilea punct de taiere) este

9 – 3 – 4 – 5 – 2 – 1 – 8 – 7 – 6;

dupa eliminarea oraselor 4, 5, 6 si 7, care sunt deja in primul succesor, obtinem

9 – 3 – 2 – 1 – 8.

Aceasta secventa este plasata in primul succesor(incepand cu al doilea punct de taiere)

o1=(2 1 8 | 4 5 6 7 | 9 3).

In mod similar obtinem celalalt succesor:

o2=(3 4 5 |1 8 7 6 | 9 2).

Operatorul OX exploateaza proprietatea reprezentarii caii, aceea ca ordinea oraselor (si nu pozitia lor) este importanta, astfel ca doua urmatoarele tururi

9 – 3 – 4 – 5 – 2 – 1 – 8 – 7 – 6 si

4 – 5 – 2 – 1 – 8 – 7 – 6 – 9 – 3

sunt de fapt identice.

*CX creeaza urmasi astfel incat fiecare oras (si pozitia lui) provine de la un parinte. Pentru parintii

p1=(1 2 3 4 5 6 7 8 9) si

p2=(4 1 2 8 7 6 9 3 5)

va produce primul succesor luand primul oras de la primul parinte:

o1=(1 x x x x x x x x).

Deoarece fiecare oras al succesorului trebuie luat de la parintii acestuia(din aseeasi pozitie), nu avem de ales acum: urmatorul oras considerat trebuie sa fie orasul 4, el fiind orasul de la parintele p2 imediat urmator orasului selectat 1. In p1 acest oras este in pozitia ‘4’, astfel ca

o1=(1 x x 4 x x x x x).

Urmeaza, la randul lui, orasul 8, ca si urmatorul oras de dupa cel selectat, 4, din parintele p2. Obtinem

o1=(1 x x 4 x x x 8 x);

Urmand aceasta regula, urmatoarele orase de inclus vor fi 3 si 2. Selectia lui 2 necesita selectia lui 1, care este deja pe lista; astfel am incheiat un ciclu:

o1=(1 2 3 4 x x x 8 x).

Urmatoarele orase se completeaza de la celalalt parinte:

o1=(1 2 3 4 7 6 9 8 5).

In mod similar,

o2=(4 1 2 8 5 6 7 3 9).

Operatorul CX pastreaza pozitia absoluta a elementelor din secventa parinte.

Printre operatorii de reordonare care au aparut il mai amintim pe cel de inversiune. Inversiunea simpla selecteaza doua puncte in cromozom, care este taiat in aceste puncte si subsirul dintre ele este inversat. De exemplu, cromozomul

(1 2 | 3 4 5 6 | 7 8 9)

devine

(1 2 | 6 5 4 3 |7 8 9).

Aceasta inversiune garanteaza ca succesorul rezultat este un tur legal; o crestere a numarului punctelor de taiere scade performanta sistemului.

Un alt operator de incrucisare este cel de recombinare marginala(ER), care transfera mai mult de 95% din marginile parintilor succesorului unic. Operatorul ER exploreaza informatiile despre marginile unui tur, de exemplu, pentru turul

(3 1 2 8 7 4 6 9 5),

marginile sunt (3,1), (1,2), (2,8), (8,7), (7,4), (4,6), (6,9), (9,5) si (5,3). In fond, marginile si nu orasele masoara distantele (valorile) in problema noastra. Functia obiectiv de minimizat este totalul marginilor, ceea ce constituie un tur legal. Pozitia unui oras in tur nu e importanta (turul este circular). De asemenea, directia marginii nu este importanta: ambele margini (3 1) si (1 3) ne spun faptul ca orasele 1 si 3 sunt direct conectate.

Ideea din spatele incrucisarii marginale este ca succesorul trebuie alcatuit exclusiv din marginile ambilor parinti. Aceasta se face cu ajutorul listei de margine formate din ambele tururi parinte. Aceasta lista ne da, pentru fiecare oras c, toate celelalte orase conectate cu acesta in cel putin unul din parinti. Evident, pentru fiecare oras c exista cel putin doua si cel mult patru orase in lista. De exemplu, pentru doi parinti

p1=(1 2 3 4 5 6 7 8 9) si

p2=(4 1 2 8 7 6 9 3 5),

lista de margine este

orasul 1: se margineste cu: 9 2 4

orasul 2: 1 3 8

orasul 3: 2 4 9 5

orasul 4: 3 5 1

orasul 5: 4 6 3

orasul 6: 5 7 9

orasul 7: 6 8

orasul 8: 7 9 2

orasul 9: 8 1 6 3

Formarea succesorului incepe cu selectarea unui oras initial din unul din parinti. Se selecteaza orasul cu cel mai mic numar de margini din lista de margine. Astfel creste sansa completarii unui tur cu toate marginile parintilor selectate. Presupunem ca am ales orasul 1. Urmatorul oras este unul dintre 9, 2, 4. Avem de ales intre 2 si 4 (deoarece au trei margini). Alegem orasul 4. Apoi avem de ales intre 3 si 5, deoarece sunt direct conectate cu 4. Il alegem pe 5. Continuand algoritmul, obtinem

(1 4 5 6 7 8 2 3 9)

care este obtinut numai din margini de la parinti.

Operatorul ER a fost testat pe probleme cu 30, 50 si 75 de orase, in toate cazurile gasind o solutie mai buna decat cea mai buna solutie gasita anterior.

Mai apoi, incrucisarea de recombinare marginala a fost amplificata. Ideea era ca “subsirurile obisnuite” nu erau pastrate in incrucisarea ER. De exemplu, daca lista de margine contine siruri cu trei margini, una din acestea se va repeta. Referitor la exemplu anterior, este vorba de marginea (4 5). Marginea apare la ambii parinti. Totusi, sunt considerate ca si alte margini, de exemplu (4 3) si (4 1) care apar la un singur parinte. Solutia propusa modifica lista de margine memorand orase – drapel:

orasul 4: se margineste cu alte orase: 3 -5 1;

Caracterul “-“ inseamna ca orasul – drapel 5 trebuie listat de 2 ori. In exemplul anterior

p1 = (1 2 3 4 5 6 7 8 9) si

p2 = (4 1 2 8 7 6 9 3 5),

lista amplificata este:

orasul 1: se margineste cu alte orase: 9 -2 4

orasul 2: -1 3 8

orasul 3: 2 4 9 5

orasul 4: 3 -5 1

orasul 5: -4 6 3

orasul 6: 5 -7 9

orasul 7: 6 -8

orasul 8: -7 9 2

orasul 9: 1 8 6 3.

Algoritmul pentru gasirea unui nou succesor acorda prioritate intrarilor drapel: aceasta are importanta numai cand sunt listate 3 margini, in celelalte cazuri fie nu exista orase – drapel, fie ambele sunt de acest tip. Aceatsa amplificare (impreuna cu o modificare pentru a alege mai bine cand e necesara o selectie aleatoare a marginilor) a imbunatatit performantele sistemului.

Operatorii ER ne indica in mod clar faptul ca reprezentarea caii este neperformanta cand e vorba de a reprezenta proprietati importante ale turului – acesta este motivul pentru care s-a introdus lista de margine.

In ultimii ani, au existat cel putin 3 incercari independente de a alcatui un program evolutiv folosind pentru cromozomi reprezentarea matriceala. Autorii au fost Fox si McMahon, Seniw si Homaifar si Guan. Ii vom discuta pe fiecare pe scurt.

Fox si McMahon au reprezentat un tur ca pe o matrice binara de precedenta binara M. Elementul mij este 1 daca si numai daca orasul I intervine inaintea orasului j in tur. De exemplu, turul

(3 1 2 8 7 4 6 9 5)

Fig.4.1.Matrice reprezentand un tur

este reprezentat matriceal in figura de mai sus. In aceasta reprezentare, matricea are urmatoarele proprietati:

numarul elementelor egale cu 1 este ,

mii=0 pentru si

daca mij=1 si mjk=1 atunci mik=1.

Daca numarul elementelor egale cu 1 este mai mic decat si celelalte cerinte sunt satisfacute atunci orasele sunt partial ordonate. Aceasta inseamna ca putem completa o astfel de matrice (in cel putin un mod) pentru a obtine un tur legal (ordinea totala a oraselor).

Cei 2 operatori noi introdusi in “Genetic Operators for Sequencing Problems” sunt intersectita si reuniunea. Ambii sunt operatori binari de incrucisare. Ei combina caracteristicile parintilor si pastreza cerintele – restrictii in acelasi timp. Operatorul de intresectie se bazeaza pe observatia ca intersectia bitilor din ambele matrice este o matrice in care (1) numarul elementelor egale cu 1 nu este mai mare decat si (2) celelalte doua cerinte sunt satisfacute. Astfel, putem completa o astfel de matrice pentru a obtine un tur legal (ordinea totala a oraselor).

De exemplu, doi parinti

p1 = (1 2 3 4 5 6 7 8 9) si

p2 = (4 1 2 8 7 6 9 3 5)

sunt reprezentati prin doua matrice(figura 4.2).

Intersectia acestor doua matrice ne da matricea din figura 4.3

Fig.4.2. Doi parinti

Fig.4.3. Prima faza a operatorului de intersectie

Ordinea partial impusa de rezultatul intersectiei implica faptul ca orasul 1 precede orasele 2, 3, 5, 6, 7, 8, 9; orasul 2 precede 3, 5, 6, 7, 8, 9; orasul 3 precede 5; orasul 4 precede 5, 6, 7, 8, 9; orasele 6, 7, 8 il preced pe 9.

In timpul secventei urmatoare a operatorului de intersectie se selecteaza un parinte; cateva elemente de 1 (care sunt unice pentru acest parinte) sunt "adunate", iar matricea este completata pentru o secventa in care se face analiza sumelor liniilor si coloanelor. De exemplu, matricea din figura urmatoare este un posibil rezultat dupa parcurgerea celei de-a doua faze; ea reprezinta turul

(1 2 4 8 7 6 3 5 9).

Operatorul reuniune se bazeaza pe observatia ca subsirul bitilor din o matrice se poate combina in siguranta cu un subsir de biti din cealalta matrice, gasit astfel incat intersectia lor sa fie 0. Operatorul imparte sirul oraselor in doua grupuri disjuncte. Pentru primul grup de orase, el copiaza bitii din prima matrice, iar pentru al doilea grup, pe cei din a doua matrice. La sfarsit, completeaza matricea printr-o secventa care face o analiza asupra sumelor liniilor si coloanelor.

De exemplu, cei doi parinti p1 si p2 si partitionarea oraselor in {1, 2, 3, 4} si {5, 6, 7, 8, 9} produc matricea (vezi figura), care se completeaza si pentru operatorul intersectie

Fig.4.5. Prima faza a operatorului de reuniune

A doua abordare in folosirea reprezentarii matriceale a fost descrisa de David Seniw. Elementul mij este 1 daca si numai daca dupa orasul i urmeaza imediat orasul j. De exemplu, cromozomul din figura urmatoare reprezinta un tur care parcurge orasele (1, 2, 4, 3, 8, 6, 5, 7, 9). Aceasta reprezentare evita problema specificarii orasului de plecare, astfel incat matricea mai poate reprezenta tururile (2, 4, 3, 8, 6, 5, 7, 9, 1), (4, 3, 8, 6, 5, 7, 9, 1, 2), etc.

(a)

(b)

Fig.4.6. Cromozomi matrice binare

Fiecare tur complet este reprezentat ca o matrice binara cu un singur bit pe linie si unul pe coloana egal cu 1. Totusi, nu fiecare matrice cu aceste proprietati va reprezenta un singur tur. Cromozomii matricei binare reprezinta siruri multiple. Fiecare subsir va face o bucla catre el insusi, fara sa se conecteze cu alt subsir din cromozom. De exemplu, un cromozom din figura anterioara reprezinta subsirurile (1, 2, 4, 5, 7) si (3, 8, 6, 9).

Subsirurile sunt permise in speranta ca va avea loc o aranjare naturala. Dupa terminarea programului evolutiv, cel mai bun cromozom este redus la un singur tur prin combinarea succesiva a perechilor de subsiruri folosind un algoritm determinist. Subsirurile unui oras ( un tur care porneste dintr-un oras pentru a se intoarce in acelasi loc), cu un cost al distantei egal cu 0, nu se permit. Limita de jos (q=3 orase in subsir) a fost stabilita pentru a impiedica algoritmul genetic sa reduca problema comisului voiajor la un mare numar de subsiruiri cu foarte putine orase (q este un parametru al metodei).

Figura urmatoare descrie subsirurile rezultate dintr-o simpla rulare a algoritmului in cazul unui numar de orase plasate intentionat in clustere(=locatii). Dupa cum era de asteptat, au rezultat subsiruri izolate.

Au fost definiti doi operatori genetici:mutatia si incrucisarea. Mutatia ia un cromozom, selecteaza aleator mai multe linii si coloane si inlocuieste bitii de la intersectia acestora cu alte valori (posibil).

De exemplu, sa consideram turul

(1, 2, 4, 3, 8, 6, 5, 7, 9).

Presupunem ca liniile 4 si 6 si coloanele 2, 3 si 5 sunt selectate pentru mutatie. Se calculeaza sumele marginale pentru acestea. Cromozomul rezultant va cuprinde doua subsiruri:

(1, 2, 4, 5, 7) si (3, 8, 6, 9)

si este reprezentat in figura 4.6(b).

Fig.4.8. Parte a cromozomului inainte (a) si dupa (b) mutatie

Operatorul de incrucisare incepe cu un cromozom fiu care are toti bitii resetati (deci zero). Operatorul examineaza intai cromozomii parinti si cand gaseste acelasi bit (linie si coloana identice) la ambii parinti, de exemplu, 1, seteaza un bit corespunzator in cromozomul fiu (faza 1). Operatorul copiaza apoi alternativ cate un bit setat de la fiecare parinte pana nu mai exista in nici un parinte biti care mai pot fi copiati fara incalcarea restrictiilor de baza ale constructiei cromozomului (faza 2). Apoi, daca sunt linii din cromozomul fiu care nu contin un bit setat, cromozomul va fi completat in mod aleator (faza finala). Deoarece operatorul produce de obicei doi cromozomi fiu, el va mai opera inca o data cu cromozomii parinte transpusi.

Consideram urmatorul exemplu de incrucisare (el incepe cu cromozomul parinte reprezentand doua subsiruri):

(1, 5, 3, 7, 8) si (2, 4, 9, 6),

in timp ce al doilea parinte este

(1, 5, 6, 2, 7, 8, 3, 4, 9)

– cromozomul este reprezentat in figura 4.9(b). Cele doua faze ale construirii primului succesor sunt cele din figura 4.10(b).

Primul succesor al incrucisarii, dupa ultima faza, este reprezentat de subsirul

(1, 5, 6, 2, 3, 4, 9, 7, 8).

Al doilea succesor este

(1, 5, 4, 3, 9) si (2, 7, 8, 6).

De observat ca exista segmente comune ale parintilor in ambii succesori.

(a)

(b)

Fig.4.9. Primul (a) si al doilea (b) parinte

(a)

(b)

Fig.4.10. Succesorii pentru incrucisare, dupa (a) faza 1 si (b) faza 2

Acest program evolutiv a demonstrat performante rezonabile pentru numarul oraselor cuprins intre 30 si 512. Totusi, nu este vizibila influenta parametrului q (minimul numarului oraselor din subsir) asupra "calitatii" solutiei. Algoritmul de combinare a mai multor subsiruri intr-unul singur este departe de a fi evident. Pe de alta parte, metoda prezinta similitudini cu algoritmul locatiilor recursive (al lui Litke), care inlocuieste in mod recursiv locatii de marimea B prin reprezentanti unici ai oraselor pana raman mai putin de B orase. Apoi, o problema mai mica este rezolvata optimal. Toate locatiile sunt extinse una cate una iar algoritmul secventiaza setul extins dintre doi vecini din sirul curent.

A treia abordare a fost propusa de Homaifar si Guan. Ca si in cazul anterior, elementul mij al matricii binare M este setat (valoare 1) daca si numai daca exista o margine din orasul i catre orasul j. De data aceasta se utilizeaza alti operatori de incrucisare si inversiunea euristica si ele vor fi discutate pe rand.

Fig.4.11. Succesorul dupa incrucisare, dupa faza finala

S-au definit doi operatori incrucisare de tip matrice (MX). Acesti operatori schimba toate intrarile celor doua matrici parinte fie dupa un singur punct de incrucisare (incrucisare dupa punct) fie intre doua puncte de incrucisare(incrucisare intre puncte). In plus, este rulat un algoritm "de reparare" pentru a inlatura dublurile, cum ar fi pentru a asigura existenta unui singur 1 pe fiecare linie si coloana si pentru "taierea" si conectarea buclelor (daca ele exista) pentru a rezulta un tur legal.

Incrucisarea intre puncte este ilustrata de urmatorul exemplu. Doua matrice parinte se dau in figura 4.12; ele reprezinta doua tururi legale:

(1 2 4 3 8 6 5 7 9) si (1 4 3 6 5 7 2 8 9)

S-au selectat doua puncte de incrucisare; acestea sunt intre coloanele 2 si 3 (primul punct) si intre coloanele 6 si 7. Punctele de incrucisare taie matricea vertical: pentru fiecare matrice, primele doua coloane constituie prima parte a diviziunii, coloanele 3, 4, 5, si 6 partea din mijloc iar ultimele trei coloane partea a treia.

Dupa primul pas al operatorului intre puncte MX, intrarile ambelor matrici sunt schimbate intre punctele de incrucisare (intrarile din coloanele 3, 4, 5 si 6). Rezultatul intermediar se da in figura 4.13.

Ambii succesori (a si b) sunt ilegali. Totusi numarul total de 1 din fiecare matrice intermediara este corect. Primul pas al algoritmului "de reparare" aduce 1 in matrice astfel incat fiecare linie si coloana sa aiba un 1. De exemplu, in succesorul din figura 5.13.a intervine de doua ori valoarea 1 (in liniile 1 si 3). Algoritmul poate muta intrarea m14=1 in m84, iar intrarea m38 in m28. In mod similar, in celelalt succesor (figura 4.13.b) avem doi de 1 pe coloana (liniile 2 si 8). Algoritmul poate muta pe m24=1 in m34, iar intrarea m86=1 in m16. Dupa parcurgerea primului pas al algoritmului de reparare, primul succesor este un tur legal,

(1 2 8 4 3 6 5 7 9),

(a)

(b)

Fig.4.12. Cromozomi matrice binare cu punctele de incrucisare marcate

iar al doilea este un tur ce consta din doua subsiruri,

(1 6 5 7 2 8 9) si (3 4).

(a)

(b)

Fig.4.13. Doi succesori intermediari dupa primul pas al operatorului MX

Al doilea pas al algoritmului de reparare se aplica numai succesorului secund. Pasul consta in taierea si conectarea subsirurilor pentru a forma un tur legal. Taierea si conectarea tin cont de marginile existente ale parintilor. De exemplu, marginea (2 4) este selectata pentru a conecta aceste doua subsiruri, deoarece marginea la unul din parinti. Astfel turul complet (un al doilea fiu legal) este

(1 6 5 7 2 4 3 8 9).

Al doilea operator folosit de Homaifar si Guan este inversiunea euristica. Operatorul inverseaza ordinea oraselor dintre doua puncte de taiere (intocmai ca inversiunea simpla). Daca distanta dintre cele doua puncte este mare (inversiune de ordin mare), operatorul executa o cautare locala. Exista totusi doua diferente intre operatorii clasici si cei propusi. Prima este ca succesorul rezultant este acceptat numai daca noul tur este mai bun decat cel original. A doua diferenta este procedura actuala selecteaza un singur oras din tur si verifica imbunatatiri pentru inversiunile de ordin 2 (cel mai mic posibil). Prima inversiune care are ca efect o imbunatatire este acceptata iar procedura de inversiune se incheie. In caz contrar se iau in considerare inversiuni de ordinul 3 samd.

Rezultatele obtinute indica o comportare foarte buna a programului evolutiv cu doua puncte MX si a operatorilor de inversiune in cazul unei probleme cu 30-100 orase.

La comparatii s-au folosit doua familii de teste:

* colectii aleatoare de orase.Avem o formula empirica a lungimii probabile L* a turului minim:

unde n este numarul oraselor, R este aria conturului oraselor, iar k este o constanta empirica (aproximativ 0.765).

* colectia publica de orase (partial cu solutii optimale) accesibila via ftp.

Algoritmii de optimizare locala, pentru un tur dat (curent), specifica un set de tururi vecine si inlocuiesc printr-un vecin (probabil) mai bun. Acest pas se aplica pana se ajunge la un optim local. De exemplu, algoritmul 2-opt defineste tururile vecine ca tururi ce se pot obtine unul din altul modificand numai doua margini.

Algoritmii de cautare locala sunt baza dezvoltarii algoritmilor genetici de cautare locala, care

* folosesc algoritmi de cautare locala pentru inlocuirea fiecarui tur in populatia curenta (de marime ) printr-un alt tur (optim local),

* extind populatia cu tururi – rezultate prin aplicarea operatorului de recombinare unor tururi din populatia curenta,

* folosesc (din nou) un algoritm de cautare locala pentru inlocuirea fiecarui succesor din in populatia extinsa printr-un tur optim local

* reduc populatia extinsa la marimea ei initiala (), conform unor reguli de selectie (supravietuirea celui mai bine adaptat),

* repeta ultimii trei pasi pana la intalnirea unei conditii de oprire (proces evolutiv).

De observat ca exista similitudini intre AG de cautare locala si strategia evolutiva . Ca si la aceasta, indivizi produc succesori iar noua populatie (extinsa) de indivizi este redusa din nou printr-un proces de selectie la indivizi.

Algoritmul genetic de mai sus este similar cu unul propus de Muhlenbein, care incurajeaza "evolutia inteligenta" a indivizilor. Algoritmul:

* foloseste un algoritm de cautare locala (opt-2) pentru inlocuirea fiecarui tur din populatia curenta printr-un tur optim local,

* selecteaza parteneri pentru imperechere (indivizii peste medie au mai multi succesori)

* se reproduce (incrucisarea si mutatia),

* cauta minimul fiecarui individ (reducere, rezolvare de probleme, extindere),

* repeta ultimii trei pasi pana la intalnirea unei conditii de oprire (proces de evolutie).

Incrucisarea folosita aici este o versiune a incrucisarii ordinale (OX). Aici, doi parinti

p1=(1 2 3 | 4 5 6 7 | 8 9) si

p2=(4 5 2 | 1 8 7 6 | 9 3)

vor produce succesori in felul urmator. Intai, segmentele dintre punctele de taiere se copiaza in succesori:

o1=(x x x | 4 5 6 7 | x x) si

o2=(2 3 4 | 1 8 7 6 | x x).

Rezultatele experimentale s-au dovedit a fi incurajatoare. Algoritmul a gasit un tur pentru o problema cu 532 orase si lungimea a fost la 0.06% de solutia optimala.

Se pare ca un bun program evolutiv pentru problema comisului voiajor incorporeaza operatori de imbunatatire locala (grupul de mutatie), bazati pe algoritmi de optimizare locala si operatori binari alesi cu atentie (grupul de incrucisare) care includ informatie euristica referitoare la problema.

=== CAP5 ===

*****CAPITOLUL 5*****

IMPLEMENTAREA PRIN PROGRAM C A PROBLEMEI COMISULUI VOIAJOR

Implementarea prin program C a problemei comisului voiajor in optimizarea functionarii celulelor flexibile de fabricatie.

//declararea headerului prot.h

#include<stdio.h>

struct cv{

int oex[8];

int mat[8][8];

int dist[8][8];

int costt;

int lung;

int tot;

};

//Functia afiseaza ordinea de parcurgere a tuturor oraselor ,precum si distanta //totala parcursa pentru incheierea unui tur complet.

#include<stdio.h>

#include"prot.h"

afis(struct cv *p){

int i,k;

printf("\n");

for(i=0;i<8;i++){

k=p->oex[i];

printf("%i\t",k);

}

printf("\nDistanta gasita este: %i",p->lung);

}

//Programul principal

#include<stdio.h>

#include<conio.h>

#include"prot.h"

void main(void){

int c;

struct cv *p;

clrscr();

init_mat(p);

init(p);

dist(p);

afis1(p);

getch();

if(intreg(p)!=1)

reface(p);

do{

if(mutatie(p)!=1)

printf("\n");t

afis1(p);

} while(p->lung>45);

dist(p);

printf("\n");

afis1(p);

getch();

}

//Functia afiseaza matricea mat in care se trece ordinea in care au fost parcurse //orasele

#include<stdio.h>

#include"prot.h"

afis1(struct cv *p){

int i,j;

printf("\n");

for(i=0;i<8;i++){

for(j=0;j<8;j++)

printf("%i\t",p->mat[i][j]);

printf("\n");

};

printf("\ndistanta este %i",p->lung);

}

//Functia de afisare a distantei unui tur complet

#include<stdio.h>

#include"prot.h"

afis2(struct cv *p){

int i,j;

printf("\n");

printf("distanta este %i\n",p->lung);

}

//Functia calculeaza distanta dupa parcurgerea unui tur complet

#include<stdio.h>

#include"prot.h"

int dist(struct cv *p){

int i,j,d=0;

for(i=0;i<8;i++)

for(j=0;j<8;j++)

if(p->mat[i][j]==1)

d+=p->dist[i][j];

p->lung=d;

return d;

}

//Functia initializeaza matricea mat

#include<stdio.h>

#include<stdlib.h>

#include<time.h>

#include"prot.h"

void init(struct cv *p){

int i,j,prima=1;

randomize();

for(i=0;i<8;i++)

for(j=0;j<8;j++)

p->mat[i][j]=0;

for(i=0;i<8;i++){

if(prima){

do j=random(8); while(j==0);

prima=0;

}

else

do{

j=random(8);

} while((i==j) || (sumac(p,j)==1));

p->mat[i][j]=1;

}

}

//Functia introduce distanta dintre orase

#include<stdio.h>

#include"prot.h"

void init_mat(struct cv *p){

int i,j;

int temp[8][8]={

{0,9,10,7,9,10,4,4},

{9,0,10,3,13,17,13,5},

{10,10,0,6,6,11,13,9},

{7,3,6,0,9,14,11,4},

{9,13,6,9,0,5,9,10},

{10,17,11,14,5,0,8,13},

{4,13,13,11,9,8,0,8},

{4,5,9,4,10,13,8,0}

};

for(i=0;i<8;i++)

for(j=0;j<8;j++)

p->dist[i][j]=temp[i][j];

}

//Functia verifica daca turul oraselor s-a fost facut prin parcurgerea tuturor //oraselelor

#include<stdio.h>

#include"prot.h"

int intreg(struct cv *p){

int i=0,k=0,j,nr=0;

int poz=0;

int tot=0;

int succes=0,inceput=0;

int sir[8];

p->tot=0;

for(i=0;i<8;i++)

p->oex[i]=-1;

do{

if ((nr=subsir(p,inceput,poz))==8) {

succes=1;

break;

}

if(p->tot==8)

break;

else{

inceput=minoex(p);

poz=0;

i=0;

while((p->oex[i]>-1) && (i<=7))

i++;//pozitia din oex

poz=i;

}

}

while(p->tot!=8);

if (succes) return 1;

else return 0;

}

//Functia initializeaza matricea mat cu valoarea 0

#include<stdio.h>

#include"prot.h"

void matzero(struct cv *p){

int i,j;

for(i=0;i<8;i++)

for(j=0;j<8;j++)

p->mat[i][j]=0;

}

//Functia gaseste orasul de ordine cea mai mica prin care nu s-a trecut

#include<stdio.h>

#include"prot.h"

int minoex(struct cv *p){

int i=0,min=0;

eticheta: while((min!=p->oex[i]) && (i<8)){

i++;

goto eticheta;

}

if(i<8){

min++;

i=0;

goto eticheta;

}

else return min;

}

//Functia aplica operatorul genetic mutatie schimband doua linii intre ele

#include<stdio.h>

#include<stdlib.h>

#include<time.h>

#include"prot.h"

int mutatie(struct cv *p){

int nr1,nr2,j1,j2,i;

int A,B,C,D,E,F,G,H;

struct cv copie;

copie=*p;

do{

nr1=random(8);

do

nr2=random(8);

while(nr1==nr2);

j1=0;

while(p->mat[nr1][j1]==0)

j1++;

j2=0;

while(p->mat[nr2][j2]==0)

j2++;

} while((nr1==j2) || (nr2==j1));

p->mat[nr1][j1]=0; p->mat[nr1][j2]=1;

p->mat[nr2][j1]=1; p->mat[nr2][j2]=0;

if(intreg(p)!=1)

reface(p);

if(dist(p)<copie.lung) return 1;

else {

p=&copie;

*p=copie;

return 0;

}

}

//Functia reface matricea mat

#include<stdio.h>//reface mat din oex

#include"prot.h"

void reface(struct cv *p){

int i,j,ioex,ilmat,lin,col;

for(i=0;i<8;i++)

for(j=0;j<8;j++)

p->mat[i][j]=0;

for(ioex=0;ioex<7;ioex++){

lin=p->oex[ioex];

col=p->oex[ioex+1];

p->mat[lin][col]=1;

}

col=p->oex[0];

lin=p->oex[7];

p->mat[lin][col]=1;

}

//Functia modifica turul astfel incat el sa fie complet

#include<stdio.h>

#include"prot.h"

int subsir(struct cv *p,int inceput,int tot){

int k=0;

int j,i,prima=1;

do{

if (prima){

j=inceput;

prima=0;

}

p->oex[tot]=j;

i=j;

j=urm(p,i);

tot++;

p->tot++;

k++;

}

while(j!=inceput);

return k;

}

//Functia verifica daca orasul a fost parcurs sau nu

#include<stdio.h>

#include"prot.h"

int sumac(struct cv *p,int j){

int i,suma=0;

for(i=0;i<8;i++)

suma+=p->mat[i][j];

return suma;

}

//Functia ne indica urmatorul oras care se va parcurge

#include<stdio.h>

#include"prot.h"

int urm(struct cv *p,int i){

int j=0;

while(p->mat[i][j]==0)

j++;

return j;

}

In functia init-mat() se initializeaza distantele dintre orase. Acestea vor ramane fixe pe toata durata rularii aplicatiei. Ele vor fi memorate intr-o matrice dist[i][j]. Urmatoarea functie, init(), genereaza o matrice pentru specificarea ordinii de parcurgere a oraselor. Ea este o matrice binara, notata mat[i][j], neavand voie sa contina decat un 1 pe linie si coloana. In urmatoarea linie se calculeaza distanta totala a parcurgerii turului. In functia intreg() se verifica daca turul este complet. Daca turul nu este complet prin intermediul functiei subsir() se cauta toate subtururile existente si construieste un singur tur cu toate orasele. Prin functia reface() se reface matricea binara mat[i][j] pentru specificarea noii ordini de parcurgere oraselor.

Urmatorul pas este cel de aplicare a operatorului genetic mutatie prin care se schimba doua linii ale matricei mat[i][j] intre ele. Dupa acest pas functia de evaluare, in acest caz dist(), compara distanta anterioara gasita cu cea curenta si daca este mai buna (mai mica) o retine. La fiecare pas se pastreaza numai cel mai bun rezultat, pana la urma ramanand numai cel optim.