Program inutil.

[Patrunjel]

Salut. Acu ceva timp am dat de boxcar2d si de-atunci am fost cumva fixat pe ideea de algoritm genetic. Bineinteles, n-am nici de departe cunostintele necesare ca sa fac ceva calumea, dar dupa vreo 5 ore de munca, 3 de debugging si vreo 10 tigari a iesit asta : Ideone.com | Online C++ Compiler & Debugging Tool

O descriere simpla o gasiti in sursa. Vroiam sa organizez tot pe headere, da nici nu-i prea mult, mi-am si futut interfata la IDE, si nu prea am avut cum, insa eu cred ca e destul de bine comentat .

Functia o_generatie() nu merge. Pe ea am stat azi-noapte si n-am facut nicio pula, +umpic azi dimineata. Am reusit sa-mi dau seama ca problema e in functia care combina genomurile (genoamele, genomii, pula mea), dar nu pot sa ma prind unde dracu e. Cica fut heapu pe undeva, dar habar nu am unde. In fine, daca se prinde vreunu ce ar putea sa fie, lasati un comentariu.

In rest, sugestii, opinii, reclamatii, injuraturi de mama, bagati la reply.

A, da, programul e scris pentru linux, daca rulati pe win si vreti sa cititi din fisier modificati numele fisierului de care se leaga ifstream-u ala. (linia 51, bagati un .txt la urma)

Edited August 10, 2011 by Patrunjel

[gigaevil]

Mi se pare ca am vazut si eu, din cate tin minte era facut in flash.

Algoritmi genetici sunt un capitol foarte slab ca notiuni in AI. Trebuie sa intelegi de ce converge intr-o solutie, de ce se foloseste mutatia, cu ce te ajuta algoritmi gen: Elitism, Roata norocului.... Crossver si in special mutatia, de ce sunt folositi.

Daca este la ceea ce ma refeream eu(Sa contruesti o masina folosind GA) atunci iti pot explica cum era conceput aloritmul evolutiv:

Fiecare model de masina era un cromozom. Populatia continea mai multi cromozomi. Initial au fost random alesi, si dupa aceea se aplica algoritmi de evolutie astfel incat sa gaseste o solutie cat de cat acceptabila si fara sa cauti toate posibilitatile(pentru acest lucru ar complexitatatea tinde spre un polinomial mare). La functia de fitness care presupune sa simulezi cat se plimba masina aplicand legile fizicii, si dupa aceea poti sa-ti dai seama care sunt cele mai bune modele si dupa aceea se merge pe ideea ca poate am 2 masini cat de cat bune, si poate daca voi face un crossover poate voi obtine ceva mai bun. Sau daca am 2 cromozomi una buna si una proasta poate dupa ce voi face crossover voi obtine ceva mai bun. Iar mutatia este folosita aici pentru a nu se face o parte stabilia... un grup.. astfel daca populatia de acuma este si peste 10.000 de evolutii nu e convenabil deoarece se repeta, iar mutatia incearca sa elimine acest lucru. Posibil in flash exista 2 functii fitness: sa simulezi cromozomul cu se plimba pe harta fara sa desenezi si cum se plimba cromozomul(masina) pe harta si sa il desenezi. Posibil el are o populatie mai mare face 10,15 evolutii folosind functia de fitness fara sa iti deseneze si dupa aceea iti afiseaza cel mai bun cromozom.

Informatia genetica ar fi cate roti, configuratia rotilor, configuratia masini(width,height, greutate) etc...

Ca sugestie ar trebui sa faci ceva vizual sa vezi daca algoritmul tau chiar functioneaza

[Patrunjel]

Programul imi verifica daca am acelasi text ca textul sursa. Pentru un singur individ care evolueaza merge.

[gigaevil]

Adica face un diff de surse cu algoritmi genetici? Nu faceai jocul cu masinute?

Nu stiu la ce te referi prin "Program care ajunge la un text dat pe baza unei tentative (ieftine) de algoritm genetic."

[Patrunjel]

Adica ii dai un text. El la inceput initializeaza o serie de caractere cu valori random. Dupa aia verifica cate dintre alea sunt bune (aceeasi litera, pe aceeasi pozitie ca in textul sursa). Daca caracterul e bun, il lasa acolo, daca nu baga alt caracter random in loc.Deci practic o generatie arata asa :

Compar cu textul la care vreau sa ajung.

Daca elementul i e ok, il las asa.

Altfel generez un caracter random si il pun pe pozitia i.

Si tot asa pana termin genomul (sau cum s-o chema). Asta e o generatie. Si intr-un final programul ajunge la textul la care vreau eu sa ajunga. Tocmai de-aia e destul de inutil

[pr00f]

Deci, s? în?eleag? tot omu'. Avem string-ul „M-am c?cat”. Programul lui P?trunjel ia fiecare liter? în parte la index-ul n ?i o verific? dac? este corect? cu fiecare liter? din string-ul dat la indexul n. Ceva-n genul ...

M-am cacat

aaaaaaaaaa

b-//-b

cccccccccc

Etc.

[gigaevil]

Ceea ce ai facut tu e inpropriu zis in literatura de specialitate, algoritm genetic.

O posibila solutie(ar putea sa existe mai multe dar converg diferit) ar fi populatia sa fie formata din mai multi cromozomi(fiecare cromozom sa fie un text[o fraza]). Functia de fitness este distanta metrica de a transforma textul din cromozomul initial in textul target. A se folosi o metrica care reuseste sa gaseasca numarul minim de operatii de stergere/inserare.

Ideea este sa se gaseasca textul corect(fara a pune toate caracterele[fara a face backtraking], si sa gaseasca lungima corecta), adica sa se caute doar o suprafata din intregul spatiu de cautare si a gasi solutia. Se pot folosi algoritmi clasici pentru algoritmi: gen elitism, roata norocului. De exempli in ideea daca ai 2 cuvinte bune, poate vei obtine un cuvant mai bun facand crossover. Deasemenea se pot introduce si texte noi random, in ideea de a scoate solutii pe parcurs.

Pentru distante metrice se poate folosi Hamming, Levensthein. Sa nu conteze valoarea operatiei de stergere si inserare(adica sa fie egale cu 1).

Algoritmi genetici nu sunt intotdeauna solutii si ceea mai buna solutie(cu mici modificari) pentru asta ar fi trebui sa se caute in tot spatiul de cautare care ar fi un polinomial mare. Algoritmul prezentat de mine ar gasi si lungimea.

Edited August 10, 2011 by gigaevil

[gigaevil]

Nu orice algoritm care foloseste random se numeste in literatura algoritm genetic. De exemplu algoritmul Monte Carlo se bazeaza numai pe random si scoate o solutie dar nu e considerat algoritm evolutiv.

PS: Scuze pentru double post.