Vlákno názorů k článku Potíže s genetickým programováním od cronin - Ked som uvidel nadpis, bol som nadseny ze...

  • Článek je starý, nové názory již nelze přidávat.
  • 15. 10. 2002 20:02

    cronin (neregistrovaný)

    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.

  • 16. 10. 2002 11:12

    Pavel Houser (neregistrovaný)

    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 :-).

  • 16. 10. 2002 12:40

    cronin (neregistrovaný)

    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.

  • 18. 10. 2002 12:36

    sejda (neregistrovaný)

    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 ??

  • 2. 7. 2004 9:10

    Juraj Perkácz (neregistrovaný)

    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.