Názory k článku Potíže s genetickým programováním

Clanek predstavuje zajimavou uvahu, ale (jak autor sam zminil) pouze z hlavy "svatecniho programatora". Jsem sice studentem, ale i presto mne programovani zivi a troufam si tvrdit, ze technika genetickeho programovani je tak trochu zcestna. Pokud vyvstane nejaky problem (potrebuji program na prohlizeni webu), presne je specifikovan vysledek a jakozto programator se mohu vydat tou nejkratsi cestou k jeho splneni. Proc mutovat programy, kdyz vim, jak ma vysledek vypadat a soucasne presne vim, jak toho dosahnout? Prijde mi to jako mit recept na bajecny kolac, ale snazit se upeci vysledny produkt experimentovanim. Proc proboha? Kromtoho, ktery programator ma chut (nadsenci mozna ano) a hlavne cas psat programy-zdroje mutace + program, ktery bude mutace provadet, jen proto, aby vznikl program uplne jiny? Ja tedy ne... :-)

myslet si, ze vim nejlepe, jak neceho dosahnout, je docela prehnane sebevedome... ostatne, je docela velka skupina problemu, kde docela presne vime, ze nevime, jak je resit - napr. spolehlive rozpoznavani mluvene reci, analyza bezne mluveneho (a nikoliv programovaciho) jazyka, apod. Pokud v tehle pripadech selhala napr. UI na bazi neuronovych siti, proc nezkusit geneticke programovani ?

spousta problemu realneho zivota neni jednoduse algoritmizovatelnych, a pycha programatoru casto neni adekvatni tomu, co doopravdy dokazi predvest...

Existuje druh problemu, ktere lze resit jedine geneticky, jde o typ uloh kdy "zprvu nic nevime", teprve pak se jaksi "samo" zacne objevovat reseni.

To skutecne odpovida biologicke evoluci, nebot v jejim prubehu vznikaly uplne nove biologicke druhy.

Vyvoj napriklad technickych objevu ma mozna take podobny charakter - postupnym "tapanim" se odkryva fungujici reseni.

Naproti tomu webovy prohlizec lze evidentne naprogramovat snaze "klasicky" - zname pozadavky a cestu, jak je realizovat. Stoji ovsem za uvahu, zdali nemame pri programovani toho weboveho prohlizece tak jasno prave diky tomu, ze (technicka) "evoluce" jiz nasla dostatek vhodnych reseni.

Aneb otazka zni: lze vubec ze sveta "tezit" reseni jinak, nez geneticky? Naprogramoval byste webovy prohlizec aniz byste nejaky nekdy videl? Aniz byste vedel, co je programovaci jazyk?

Vse i my sami jsme soucasti velke, pozoruhodne evoluce, jejiz rozsah nam neni dano rozumem uchopit... Vzrusujici predstava, ze?

S podivem, některé věci i v osvědčených produktech se řeší genetickými algoritmy, protože je to výhodnější než tradiční postupy, nebo dokonce nikdo neví, jak na to. Příkladem budiž způsob, jakým se spojují tabulky v PostgreSQL. Při spojování většího počtu tabulek PostgreSQL prostě zkouší a zkouší...

Takovy drobny dodatek - GA (geneticky algoritmus) je neco trochu jineho, nez GP (gen. programovani), protoze GP generuje primo programy resici ulohu, kdezto GA hleda optimalni reseni, napr. bod, kde funkce nabyva maxima.

Jinak k tomu prohlizeci - samozrejme by to slo udelat, ale problem je v ohodnoceni kvality programu. GA i GP pouzivaji ohodnocovaci funkci, ktera priradi kazdemu retezci (nebo programku) pocet bodu rikajici, jak je to kvalitni. Zkuste napsat program, ktery ohodnoti kvalitu weboveho prohlizece ...
Zatimco pro reseni optima s hodne slozitymi funkcemi to tezko udelate jinak. Zvlast, kdyz umime spocist hodnotu funkce v urcitem bode, ale nezname treba vsechny derivace a jine dodatecne informace potrebne pro jine postupy. V tomle jsou GA i GP strasne skromne.
Ja treba pouzivam GA k uceni RRWW automatu podle prikladu spravnych a nespravnych slov (RRWW automaty jsou automaty prijmajici neco vic nez kontextove jazyky, zalezi na typu automatu)

Podle me je GP podmnozinou GA. GP prece taky "hleda optimalni reseni, napr. bod, kde funkce nabyva maxima".
Tim bodem v prostoru je program v prostoru programu. Proste je to cele o optimalizaci, akorat ze GP optimalizuje konkretne programy.

Zkuste napsat program, ktery ohodnoti kvalitu weboveho prohlizece ...

Tak to bych pak chtel videt ty vysledky MSIE vs. Mozilla atd... ;-) To by byl konec flamewars a zabavy mnoha lidi.
Sorry, nedalo mi to. ;-)

Necht si autor predchoziho prispevku uvedomi, ze on sam je vysledkem genetickeho algoritmu beziciho jiz mnoho generaci na opravdu velke populaci. To ze je schopen naprogramovat webovy prohlizec je velmi chvalihodne.

Tam kde presne vim, jak dosahnout vysledku je naprosto neopodstatnene nasazovat GA, to je pravda, ale to snad autor clanku ani nedela, nebo snad ano ?

Preju Vam hodne stesti pri psani www prohlizecu a doufejne, ze Vas to uzivi az do konce zivota ;-)

Good luck
HK

I kdyz netvrdim, ze bych to nedokazal, internetovy prohlizej jsem nikdy nepsal. Byl to pouze priklad... :-(

No napriklad, jak si autor predchoziho prispevku predstavuje jak naprogramovat robota aby chodil. Clovek je taky vlastne naprogramovan zkusenosti. Videl jsem moc pekny program, ktery ucil panacka chodit. Po asi 5 generacich uz chodil docela dobre.

ja len upozonim, ze myslienka GA nie je v ziadnom pripade zcestna a ma mnoho praktickych uplatneni, jeden priklad za vsetky napr. program SpamAssassin.

Dobre, dobre, omlouvam se, nemyslel jsem to presne tak, jak jsem napsal :-)

Zcestneho neni samozrejme nic, jen jsem chtel poukazat na to, ze pro drtivou vetsinu programovacich uloh je tato technika zbytecna.

SpamAssassin je prave podle meho (doufam, ze mam spravne informace) spatnym prikladem. Pokud jsou spammeri cim dal tim "chytrejsi" a SpamAssassin dokaze inteligentne menit filtry posty, aby tuto "chytrost" kompenzoval, nejedna se o geneticke programovani. Na zmenu filtru je sice potreba jista davka umele inteligence, ale vse je pevne napsano uvnitr programu. SpamAssassin sam sebe nemeni nebo nevytvari jine mutace sama sebe, ktere by byly zalozeny na jinem zdrojovem kodu (tedy obsahujici modifikovane algoritmy). Doufam, ze se nemylim... Pokud ano, omlouvam se a prosim neflamovat... :-)

neee, SpamAssassin ma rozsahly seznam regularnich vyrazu a jejich bodoveho ohodnoceni (plus i minus). Spam se urci tak, ze celkove body mailu presahnou nejaky prah. A prave to bodove ohodnoceni reg. vyrazu je vypocitano pomoci GA.

pomocou GA sa navrhoval napr. tvar vrtule lietadla. vznikla strasna vec, ale malo to (kupodivu) skvelu ucinnost.
dalsie priklady skvelej ucinnosti a podivneho tvaru citatel ziska pohladom z okna. priklady podivnej ucinnosti ziska navstevou lubovolneho sanatoria.

Když už zde padla zmínka o AI. Je docela dobře možné, že genetickým programováním se dostanete k něčemu, co se bude chovat inteligentně. Problém naší inteligence (či vědomí, duše etc.) tím však moc nevyřešíme - těžko říct, co vlastně bude program "dělat inteligentním".
Když pomocí GP najdete závislost mezi dvěma proměnnými funkce, a bude tam pět cosinů, polynom a tři logaritmy, co nám to řekne o vztahu těchto veličin?
GP zkrátka tvoří tak trochu černé skřínky. Tedy jako výpočetní procedura se to jistě hodí, pokud vám ale jde o nějaké hlubší pochopení problému, můžete narazit (mimochodem mě napadá, že tady se GP snad trochu podobá kvantové fyzice). Samozřejmě ale i výsledkem GP může být jednoduchý, křišťálově čistý vztah, jehož smysl odvodit dokážeme.

http://www.realai.net/engine.htm

Dalsi info muzu poskytnout.

nemusi to vubec byt zdlouhave. ja jsem pri programovani jednoho algoritmu PATRNE pouzil neco podobneho - jakysi slepenec. Existovala uloha, jenz mela pro vetsinu pripadu jednoduche reseni, ale zaroven tam byla i pocetna skupina, pro kterou jsem pravidla neznal. Vytvoril jsem proto velmi rozsahle prostredi, v nemz program sam testuje svoji uspesnost. Pokud se stane, ze je v prostredi neco jineho, nez jake jsou predpoklady algoritmu, tak mutuje tu vlastnost, ktera nesedi, az jsou jeho vlasnosti v rovnovaze s prostredim. Potom se sam prekomiluje - a to je pro me hotovy program. Jakmile se zmeni prostredi, meni se i chovani algoritmu.

Neni to sice nic prevratneho, ale jak jsem to pochopil, tak je to alespon trochu podobne.

Na uvod jen poznamku: zda se, ze mnoho prispevatelu si plete geneticke algoritmy (GA) a geneticke programovani (GP). Nikoliv prekvapive prave ti, kteri maji nejvetsi chut poucovat :-)

A GP vlastne v podani autora by melo delat to, co dela samovolne komunita uzivatelu. Pokud totiz chcete pouzivat program pro napriklad IRC, vite, ze jich na internetu naleznete dost (uvodni populace). Jejich uzivanost je kriterium (optimalizacni funkce). Obcas autor nektereho dila prevezme zajimave myslenky z jineho konkurencniho programu, o ktere si mysli, ze bude zajem (krizeni). Obcas nekdo dodela uplne novou funkci, kterou jeste zadna konkurence nema (mutace) - pokud se neuchyti, casem sama zanikne.

Vyse zmineny proces funguje, protoze je mnohem obecnejsi nez autorem naznacene GP. A pokud se na to zadivate z dostatecneho nadhledu, zjistite, ze proces je opravdu vice-mene nahodny.

Co si o tom myslite ?

Ano, ne, co z toho? Ma tato uvaha nejaky vyznam?

Krásný případ (v zásadě) úspěšného použití GP je okřídlený robot, který se naučil "létat". Viz http://www.google.com/search?hl=en&lr=&ie=ISO-8859-1&q=winged+robot+learns+to+fly&btnG=Google+Search

Programem byla v tomto případě sekvence instrukcí provádějících různé pohyby (nahoru, dolů, rotace) křídly.

.... tak nejak byly napsany Widle, ne? ;)

.... tak nejak byly napsany Widle, ne? ;)

.... tak nejak byly napsany Widle, ne? ;)

Ne. Tady se uvažuje o mutacích, které mají výsledný program zkvalitnit :)

Ked som uvidel nadpis, bol som nadseny ze sa nieco take na roote objavilo. So zaujmom som si clanok precital.

Clanok je celkom v poriadku, ak bol mysleny ako popularno-naucny a mal roznietit zaujem o problemy genetickeho programovania. Tento ciel sa autorovi splnit podarilo, ako vyplyva z burlivej diskusie. Ak vsak bol clanok mysleny ako odborny, je nutne mu vytknut povrchnost a mnohe nepresnosti.

Autor na zaciatok vybral dost nevhodny priklad rovno z navrhovanim programov pomocou GP. V praxi je toto cesta zatial neschodna na riesenie problemov o malo zlozitejsich ako trivialne. V popredi stoji najma tzv. regresia, kde ide o navrhnutie funkcie y=f(x_i), i=1,2,...,N. Ide o aproximaciu neznamej funkcie, pri ktorej su zname vstupy a vystupy, ale samotna funkcia sa modeluje ako tzv. black box alebo tzv. grey box. Rozdiel je ten, ze ak je tvar regresnej funkcie znamy a navrhuju sa iba jej koeficienty, ide o GENETICKE programovanie (pripad gray box), ale ak sa v ramci algoritmu navrhuje tvar regresnej funkcie aj jej koeficienty, ide o EVOLUCNE programovanie (pripad black box). Este co sa tyka autorovho prikladu s navrhovanim programov riesiacich urcity specificky problem, excelenty priklad uviedol v diskusii "vlk": OpenSource.

Geneticke algoritmy sa vo najcastejsie pouzivaju ako jeden z optimalizacnych algoritmov. Ich vyhodou proti stochastickym algoritmom je cielenost smeru vyvoja riesenia selekciou lepsich jedincov (tzv. selekcny tlak), a vyhodou proti horolezeckym algoritmom je variabilita dosiahnuta krizenim a mutaciou, ktore zabezpecuju prehladavanie celeho stavoveho priestoru. Geneticke algoritmy su dost odolne voci uviaznutiu v lokalnom minime, aj ked nie su uplne imunne. Preto boli vyvinute metody urdziavania roznorodosti populacie, ako su crowding, sharing, koevolucia, koevolucny sharing/crowding, udrziavanie subpopulacii, Nitze techniky... Tym chcem zaroven poukazat na to, ze veci ktore autor nazval "problemami genetickeho programovania" su problemy ktore su velmi dobre preskumane a velmi dobre riesitelne a v sucasnosti aj riesene.

Autor uvadza, ze pomocou GP je mozne riesit problem, o ktoreho podstate nic nevieme. Ak o podstate problemu nic nevieme, je vhodnejsie ako optimalizacny algoritmus pouzit stochasticky alg. Existuje tzv. No Free Lunch Theorem, ktory (matematicky) hovori o tom, ze vzdy moze byt stochasticky optimalizacny alg. uspesnejsi ako deterministicky. Ak ma byt deterministicky alg. lepsi proti stochastickemu, musi obsahovat domenovo zavisle informacie, t.j. o podstate problemu musime nieco vediet. Sila deterministickeho optimalizacneho alg. je potom v objeme tejto domenovo zavislej informacie a sposobe jej pouzitia.

Evolucia v krajine vs. evolucia v programe: kym v programe ide zvacsa o hladanie globalneho extremu, evolucia v prirode spravidla neriesi problemy optimalnym sposobom a na ukor toho si nechava moznost adaptability na zmenene podmienky.

Linky v slovencine:
GP: http://alife.fei.tuke.sk/projekty/gen_prog/
GA: http://alife.fei.tuke.sk/projekty/gen_alg/
TSP problem pomocou GA: http://alife.fei.tuke.sk/~babjak/cestujuci/index.html

Dotazy ohladne podrobnosti GA mi mozete posielat mailom.

diky za doplnujici informace, predevsim za ten crowding, nitze apod.

jen mi neni jasna jedna vec: Pokud provadite regresi funkce a hledate jen koeficienty (tj. tvar mate, treba ze jde o polynom 5. stupne), to se prece da udelat mnohem jednoduseji, metodou nejmensich ctvercu a obdobou toho. dokonce i kdyz vite, ze jde treba o polynom maximalne 10. stupne, pak pro regresi potrebujete prece jen prohledat vicerozmerne pole. uplne nerozumim, k cemu by pak to GP vlastne bylo.

>evolucia v prirode spravidla neriesi problemy optimalnym sposobom a na ukor toho si nechava moznost adaptability na zmenene podmienky.
***
mno, tedy moc nesouhlasim, ale to by bylo na uplne jinou diskusi :-).

Ano, ak je ulohou najst koeficienty polynomu 5. radu aby bola dosiahnuta aproximacia alebo interpolacia funkcie, mame na to Lagranga, Newtona, Hermita, najmensie stvorce... Ale co ak tvar funkcie nie je zadany analyticky? Pracujem na simulacii zivota sladkovodnych rias. Je definovane prostredie s teplotou, osvetlenim, pH, obsahom organickych aj anorganickych latok, difuzia tychto latok, vyparovanie, etc. Potom je dane spravanie sa jednej bunky v takomto prostredi: odoberanie mineralnych latok, uvolnovanie metabolitu, fotosynteza, vyroba energie, pohyb, rozmnozovanie. Prostredie ma cca 20 parametrov ktore je potrebne nastavit, bunka riasy odhadujem okolo 50-70. Tieto parametre sa nastavuju vhodnym optimalizacnym alg. (GA, HCwL) tak, aby sa dosiahla rastova krivka populacie zhodna s krivkou dosiahnutou pri pokusoch "in vitro". Je teda jasne, ze tu ide o aproximaciu funkcie - analyticku funkciu treba nahradit black-boxom (resp. vzhladom na to co som uviedol v predchadzajucom prispevku skor gray-boxom), ktoreho parametre su vsak analytickou matematikou a/alebo algebrou vypocitatelne "dost tazko". Navyse v tomto gray-boxe je mnoho veci nahodnych, napr. nie je stanovena hodnota spotreby mineralov v jednom kroku simulacie na jednu hodnotu, ale je to interval, a kazdy jedinec ma "svoju" hodnotu z tohoto intervalu. To plati pre kazdy z tych 50-70 parametrov a navyse je dany pre kazdy s parametrov, ci sa ma zo svojho intervalu generovat uniformne alebo normalne (gaussovsky). Tak isto pri rozmnozovani funguje dedenie + mutacia... Je mozne nahliadnut, ze koeficienty takto zadanej funkcie nie je mozne vypocitat analyticky (alebo by to aspon bolo VELMI obtiazne).

A co sa tyka evolucia in vivo vs. evolucia in silico, napiste clanok na scienceworlde, podiskutujeme tam... :) To skutocne nie je tema na root-a.

Nechci odporovat, ale opensource je z hlediska evoluce spise slechteni.

A jeste neco, evolcni programovani je sice to co se tady diskutuje, ale je to bez zasahu nadrazene intelignece, tedy jde jen o to jak vytvorit vhodne podminky do zacatknu, nebo ne ??

Ja sa zaoberam Genetickymi Algoritmami (GP) a Genetickym Programovanim (GA), takze si ujasnime pojmy: GA optimalizuju hodnoty porametrov, GP optimalizuju topologiu a hodnoty parametrov topologie systemu (programov, struktur).
Takze Tvoje rozdelenie je nepresne:

"Rozdiel je ten, ze ak je tvar regresnej funkcie znamy a navrhuju sa iba jej koeficienty, ide o GENETICKE programovanie (pripad gray box), ale ak sa v ramci algoritmu navrhuje tvar regresnej funkcie aj jej koeficienty, ide o EVOLUCNE programovanie (pripad black box)."

Cize namiesto "GENETICKE programovanie" tam ma byt GA.

Tento clanek je peknym povidanim o genetickych algoritmech pro laiky, proto bych ho osobne nazval 'Povidani o genetickych algoritmech'. Protoze v nem nebylo ale skoro nic receno, hodil by se spise do revue na vikend.

v svojom prvom prispevku (Add: clanok aj diskusia) som uviedol linky v slovencine s podstatne obsirnejsimi informaciami.

OK, beru rekneme, ze nektere ulohy proste nejdou algoritmizovat (i kdyz by chtel videt dukaz), rekneme ze na nektere ulohy selhalo i sestaveni neuronove site (ale chtel bych to cist jako vedeckou praci o neuspechu, ne jako kecy), a rekneme ze jedina cesta je geneticke programovani.

Pak chci videt cloveka, ktery vymysli algoritmus, nebo sestavi neuronovou sit, ktera dokaze simulovat mutace, krizeni ... :o)

Nebo ze by tohle cele byly jen kecy ?? Geneticke programovani nemuze vzniknout -> protoze nemame vejce, ktere se samo nevytvori, nebo se pletu ??

Ano, niektore ulohy skutocne nejdu algoritmizovat. Dokazal to pan Ashby niekedy v 30.-40. rokoch minuleho storocia, potom je tu teorema o neuplnosti (tusim Hegel?). Pozrel som si vase stranky a podla nich posobite ako skuseny programator, takze taketo veci by ste mali vediet.

Dalej spominate vo svojom prispevku neuronove siete (dalej len NN). Z kontextu a/alebo stylizacie vasho prispevku mi vyplyva, ze ze povazujete NN za nejaku "zazracnu ciernu skrinku", ktora riesi lubovolne problemy. Pravda je vsak ovela prozaickejsia: su to prave specialne ulohy, na ktore sa da "nasit" NN (klasifikacia, predikcia, zhlukovanie, long/short term memory, ...). Nejaku tu NN som uz naprogramoval takze viem o com vravim.

A svoj nazor na GA/GP ste si utvorili iba na zaklade tohto clanku - to je dost malo informacii. Pozrite si dva clanky na http://alife.tuke.sk - jeden je ku GA, druhy ku GP a mozno pridete nato, ze pravda vobec nie je taka bombasticka, ako by sa na prvy pohlad zdalo, ze vytvorime nieco, co bude evolvovat, evolvovat, az vyevolvuje umely zivot (a to si nechcem predstavit tu diskusiu, keby tu bol clanok na temu "Artificial Life" - verim ze v tom pripade bys sa sem zatiahlo vsetko vcetne moralky a nabozenstva).

Teorem o neuplnosti - Goedel, nikoliv Hegel :))
petr.

Aj sa mi to nezdalo, ale som vedel, ze je to nejaky xxx-el. :-) A Hegelom som sa zaoberal nedavno, preto mi prisiel na um.