algoritm genetic

[ralu.21188]

am de programat in java sau c# un algoritm genetic. nu sunt incepatoare in ale programarii, dar nu am avut timp de studiu pe partea de ia. ma poate ajuta cineva cu codul?
mersi fain.

[lightuniverse]

Da,

Am dat un search pe google code si am gasit urmatorul exemplu in java:

http://code.google.com/p/wevo2/source/b ... s/SGA.java

Daca te intereseaza cred ca mai am niste coduri scrise in Matlab dar nu e cine stie ce.

Mult succes si sper sa ne mai vedem pe aici.

[lightuniverse]

Ca si idee genrala structura unui algoritm genetic poate fi reprezentata de urmatorii pasi:

1.Generarea populaţiei iniţiale şi iniţierea contorului de timp şi/sau de iteraţii dacă este cazul
2.Evaluarea tuturor cromozomilor populaţiei
3.Testarea criteriului de oprire (limite de timp, limita de iteraţii, satisfacerea condiţiilor de optimizare, etc...)
4.Selecţia indivizilor pentru modificare cu ajutorul operatorilor genetici (reproducere, mutaţie, etc...)
5.Aplicarea operatorilor genetici asupra populaţiei iniţiale (aceasta va rezulta în generarea de noi indivizi)
6.Se evalueaza noii indivizi generaţi
7.Se generează noua populaţie
8.Salt la pasul 2

[ralu.21188]

de fapt e natural - de la o populatie initiala, prin mutatie sau diferite metode, se ajunge la o populatie mai mare ... dar ca si logica :
care ar putea fi o conditie de oprire a algoritmului? se ajunge la un anumit numar de indivizi?
care pot fi conditiile de incrucisare? cati indivizi incrucisezi? sau aplici pe unu o anumita operatie?

intrebarile astea le pun nefiind in tema deloc, dar cu o discutie ma gandesc ca pricep mai bine ideea de baza.

[lightuniverse]

1. Populatia poate avea marime fixa sau variabila.
Daca populatia are marime variabila atunci la populatia initiala se adauga mabrii noi generati. Dezavantajul acestei metode ar fi ca la fiecare generatie creste timul de procesare necesar din cauza mai multor operatii care trebuie efectuate in timp ce avantajul ar fi ca nici o solutie explorata nu este pierduta.
Daca populatia este de marime variabila atunci indivizii mai putin performanti sunt inlocuiti de indivizii noi generati; astfel populatia noua va fi formata din indivizii performanti ai generatiei anterioare si din indivizii noi generati. Dezavantajul este ca solutii explorate ar putea fi din nou explorate prin operatia de mutatie in cazul in care numarul de indivizi raportat la spatiul de cautare este prea mare. Avantajul este ca intrega populatie va converge catre punctul de optim global al functiei. (Eu recomand populatii cu un numar fix de indivizi).
În alegerea numărului de indivizi ai algoritmului genetic un rol important îl are dimensiunea
spaţiului de căutare. Pentru generarea populaţiei iniţiale se doreşte o distribuţie cât mai uniformă a membrilor populaţiei pe întreg spaţiul de căutare pentru a evita blocarea procesului de căutare într-un eventual minim local. De regulă, populaţia iniţială se construieşte prin generarea aleatoare a unor puncte ale spaţiului de căutare.Asta bineinteles daca nu exista informatii apriori care sa indice vecinatatea punctului de optim global.
Prin inbunatatirea treptata (apropierea de optimul global) a indivizilor populatiei algoritmul genetic va ajunge in final in punctul de optim global sau cel putin in vecinatatea acestuia.

[lightuniverse]

2 Nu există o regula generală pentru stabilirea criteriului de oprire în cazul tuturor
problemelor acesta depinde mai degraba de restrictiile problemei si de precizia cu care se doreste identificarea minimului global.
Unul din posibilele criterii de oprire folosite este cel al atingerii unui număr prestabilit de
generaţii sau trecerea unei durate de timp prea mari.
Un alt criteriu de oprire folosit este cel de convergenţă a populaţiei. În general algoritmii
genetici vor forţa majoritatea indivizilor la convergenţă către aceeaşi soluţie. Astfel când distanţa dintre indivizi devine mai mică decât un prag prestabilit algoritmul genetic poate fi oprit
Algoritmul poate fi de asemenea oprit în cazul în care nu se detectează o îmbunătăţire
semnificativă a indivizilor cei mai performanţi pentru un număr relevant de generaţii (cel mai des utilizat de mine)
De asemenea se poate opri algoritmul de căutare pe baza atingerii unui prag sau a unei valori
prestabilite a performanţei cromozomilor populaţiei.
Pentru majoritatea problemelor se pot folosi multiple criterii de oprire astfel încât cel care este
îndeplinit primul va determina încetarea operaţiei de căutare.

[lightuniverse]

3 În anul 1990 Ken DeJong şi William Spears sugerează că pentru o populaţie mare de m=100 de indivizi probabilitatea pentru încrucişare ar trebui să fie de Pîncrucişare=0.6 iar cea pentru mutaţie de Pmutatie=0.001 în timp ce pentru o populaţie mică de m=30 de indivizi probabilitatea pentru încrucişare ar trebui sa fie de Pîncrucişare=0.9 iar cea de mutaţie de Pmutatie=0.01.

NU EXISTA SOLUTII UNIC APLICABILE PENTRU TOATE PROBLEMELE. In cazul meu dupa cateva rulari am intuit in functie de tipul problemei care e combinatia optima pentru problemele tratate de mine.

Apropo mai sunt si alti operatori genetici dar acestia sunt cel mai des folositi.

[lightuniverse]

4 opeartorii genetici
Eu am facut in felul urmator:
a.) cei mai buni N indivizi i-am transferat automat in populatia noua pentru a nu pierde solutii bune. (in general am folosit N<=10%)
b.) cei mai buni M indivizi au fost supusi operatiei de incrucisare (fie intre ei astfel generand M indivizi ), (fie fiecare cu individul cel mai bun generand astfel 2xM indivizi )
c.) restul de indivizi au fost supusi operatiei de mutatie (fie regenerati de la 0, fie doar o parte din genele lor au fost regenerate)

Incrucisarea se face in general in 1 sau mai multe puncte.
Pentru încrucişarea într-un singur punct secvenţa cromozomului este împărţită în două iar una
din părţi va fi schimbată cu o parte care aparţine altui cromozom. De exemplu pentru doi cromozomi de forma c1=[ 0 1 1 0 0 0 1 1 1 ] si c2=[ 1 0 0 1 1 0 1 0 1 ], dacă punctul de tăiere este ales după a patra genă a cromozomului atunci cromozomii rezultaţi vor fi: c1n2=[ 0 1 1 0 1 0 1 0 1 ] iar c2n1=[ 1 0 0 1 0 0 1 1 1 ].
Pentru încrucişarea în n puncte cromozomul se împarte în mai multe componente care vor fi
schimbate sau nu cu componente ale celuilalt cromozom. Regula după care cei doi indivizi schimbă componentele între ei poate varia în funcţie de necesităţile problemei care trebuie rezolvate. Dacă considerăm cromozomii din exemplul anterior ( c1=[ 0 1 1 0 0 0 1 1 1 ] si c2=[ 1 0 0 1 1 0 1 0 1 ] ), iar asupra lor se aplicăm încrucişarea după genele trei şi şapte vom obţine următoarele componente: c11=[ 0 1 1 ], c12=[ 0 0 0 1 ], c13=[ 1 1 ] , c21=[ 1 0 0] , c22=[ 1 1 0 1 ], c23=[ 0 1 ] iar o doi posibili noi indivizi pot fi: c2n1n2=[ 1 0 0 0 0 0 1 0 1 ] şi c1n2n1=[ 0 1 1 1 1 0 1 1 1].

Mult succes si daca mai ai intrebari, argumente sau pareri te asteptam sa le imparti cu noi.

[lightuniverse]

Pentru cei interesati uite si ceva bibliografie utilizata de mine.

1. Algoritmi genetici. Principii fundamentale şi aplicaţii în automatică - Ion Dumitrache, Cătălin
Buiu - Mediamira, 2000
2. Representations for Genetic and Evolutionary Algorithms - Dr. Franz Rothlauf - Springer, 2006
3. Tehnici evolutive de optimizare. Optimizare multicriterială - Corina Rotar - Accent, 2008
4. Proiectare optimală cu Algoritmi Genetici - Tudose L., Pop D. - Mediamira, 2002
5. Neural Netowrks – Volumul 19 Numărul 5 – Elsevier, Iunie 2006
6. Algoritmi genetici - http://eureka.cs.tuiasi.ro/~fleon/BVIA/ ... netici.swf
7. Inteligenţă artificială - http://ro.wikipedia.org/wiki/Inteligenta_artificiala
8. Inteligenţă artificială - http://www.descopera.org/inteligenta-artificiala/
9. Algoritmi genetici - http://ro.wikipedia.org/wiki/Algoritm_genetic
10. Algoritmi genetici - http://en.wikipedia.org/wiki/Genetic_algorithm
11. Forum online algoritmi genetici - http://groups.google.ro/group/comp.ai.genetic/

[ioan]

Eu as putea sa-ti spun cum am facut jocurile alea. Am sa incerc sa-mi amintesc.
Primul, acela cu piramida de elemente, e chiar simplu, dar m-am bazat si pe faptul ca multimea partidelor posibile nu este foarte mare. Deci, am inregistrat fiecare partida jucata anterior intr-o tabela. Cand e la mutare, calculatorul alege mutarea optima (dintre cele posibile) facand raportul dintre numarul de jocuri castigate anterior si numarul de jocuri pierdute anterior cu aceea mutare in aceeasi situatie. Astfel alege mutarea convenabila, sigur ca printre mutarile posibile la un moment dat pot exista si mutari care nu s-au mai efectuat, aceste mutari trebuie folosite altfel programul poate intra in bucla (la antrenament). In cazul acestui joc am considerat aceste mutari ca fiind cele mai bune, punctaj maxim by default. Am facut asta bazandu-ma pe faptul ca totalitatea partidelor posibile si a mutarilor neefectuate anterior este destul de mica in cazul acestui joc. Dar intr-un joc cu multe variante e util - in afara de algoritmul genetic care selecteaza din tabela cu jocurile efectuate deja - un algoritm care sa aleaga dintre variantele care nu se afla in tabel.