Názory k článku Biologické algoritmy (1) - Evoluční algoritmy

tesime sa na druhy diel

Zajímavý článek, s netrpělivostí čekám na další díl.
Jenom bych měl malou poznámku, nijak se k počítačům nevztahující:

Fitness v přírodě znamená schopnost organismu šířit dál své vlastní geny. Organismus může být svému okolí nepřizpůsobený, nepřizpůsobitelný či nepřizpůsobivý, prostě hodně daleko od jakéhokoliv optima, přesto může být jeho populace životaschopnější, než normální populace.

Fitness v programování či v matematice pak vystihuje kvalitu jedince - míru, s jakou se přiblížil k optimálnímu řešení.

V souvislosti s optimálním řešením bych měl ještě druhou poznámku:

Některé z úloh, k jejichž řešení bych použil genetické algoritmy, možná ani nemají žádné optimální řešení. V praxi by mi stačilo pro takové úlohy najít alespoň přibližně fungující řešení.

K tomu optimalnimu reseni, ono se taky neda tvrdit ze gen. algoritmy najdou vzdy optimalni reseni, spis se jedna o sub-optimalni reseni.

"Fitness v přírodě znamená schopnost organismu šířit dál své vlastní geny."

Však to taky znamená že se daný organismus blíží optimu. V přírodě je fitness fnc = přežití. V algoritmu to bývá pohyb ve stavovém prostoru k řešení.

Fitness znamena hlavne schopnost se rozmnozit.

Však když se říká přežití, myslí se obvykle přežití genů, ne konkrétního zvířátka.

To samozřejmě není pravda, vždyť právě posun od důrazu na přežívání konkrétních jedinců k pohledu na evoluci jako na šíření samotných genů, je ještě dodnes něco, co si většina lidí (leckdy i biologů) neuvědomuje.

Genocentrický pohled na evoluci může být sice současným paradigmatem evoluční biologie, ale to ještě neznamená, že se můžeme vyjadřovat nepřesně.

Fitness nemusí vůbec vypovídat o životaschopnosti daného organismu, jde čistě o co největší schopnost rozšíření vlastní genetické výbavy v populaci prostřednictvím potomstva.

Organismus může klidně bez problému přežívat a přesto může být (např. díky parazitární nákaze, vývojové poruše atd.) zcela neplodný a tedy mít nulový fitness.

Toto je neprosta klasika. Kazdy, kdo se dneska zivi fyzikou prakticky nedela nic jineho, nez ze pocita nejake optimalizace. Akorat ted se tomu rika evolucni algoritmy, coz je sice cool, ale porad je to ta stara minimalizacni/ma­ximalizacni klasika. Sranda zacina, kdyz se optimalizuje nejaka treba sedmidimenzionalni funkce, ktera ma plno lokalnich maxim/minim. A taky je potreba dobre trefit pocatecni podminky. Celkove je to ale mocny nastroj, ktery lze jedine doporucit. :)

To se mýlíte. Existuje více algoritmů pro řešení optimalizačních úloh. Genetický je jen jedním z nich. Vedlo toho exsituje třeba simulované žíhání (ochlazování) nebo monte carlo, které nejsou inspirované biologií.

Fyzika je v podstate len neprípustne zjednodušená biológia.

sedm rozmeru, to je na tuzku a papir...
kdyz resim zrovna prtavy problemek, ktery je jen v 3000 rozmernem prostoru, tak si rikam, ze bych to nemel tolik sidit a mel pouzit nejaky realnejsi model... (ten se 50000 parametry trosku crashoval na vypocetnim serveru, tak to zas nesmim prehanet)

Díky za článek, hlavně jsem zvědav na další díl.

Jen bych měl výtku k jednomu tvrzení v článku:

V přírodě se tento problém řeší tak, že při křížení geneticky blízkých jedinců je zvýšena pravděpodobnost mutace. Jsou-li rodiče vzájemně příbuzní, míra mutace potomků je vyšší.

Možná to tak myšleno nebylo, ale vypadá to, jako byste věřil ve stokrát omletý a již dávno vyvrácený blud, laicky popsaný jako: "Když mají dítě bratr se sestrou, narodí se jim dítě bez ručičky." To není pravda.

Ano, pokud budou mít oba z rodičů mutaci, která způsobuje nějakou chorobu (tj. geneticky přenosnou chorobu), tak se to na jejich potomkovi projeví. Pokud se jim ale narodí např. ono dítě bez ručičky, tak je to nová mutace, která nesouvisí s genetickým kódem rodičů a mohla se stát komukoliv.

Takoví Habsburkové se brali v příbuzenské linii skoro pořád a neřekl bych, že trpěli na nějaké nové mutace. Naopak postupně degenerovali.

Nejsem biolog, pokud je někdo schopen mě ještě více upřesnit, nechť to prosím udělá.

Nóóó... v naší politice se vyskytuje jistý politik na kterém se mutace vyřádily jedna radost. Taky šlechtic ;o) Tak nevím nevím... No a když zavítáte do jistých částí Brna, tak vás také jistě zarazí podezřelé množství jedinců jímž odstávají uši, šilhají, nebo mají křivá záda či dokonce hrb...

Při mém štěstí mi genetické algoritmy budou produkovat právě ty ušaté, šilhavé opálené jedince :))

Ale díky autorovi za článek, těším se na další.

Oja

Myslim, ze v prirode to funguje tak, ze kazdy organismus si nese spoustu zmutovanych genu, ktere jsou recesivni. Pokud je genofond dostatecny, tak je nepravdepodobne, ze se takovy gen projevi (a ovlivni selekci). V pripade zmenseni genofondu se zvysi pravdepodobnost, ze se tyto geny projevi (odstranily se dominantni geny/vzniklo vic jedincu, kteri dominantni gen nemaji).

Vetsina mutaci (ktere vznikly nekdy davno, ale nemely se moznost projevit) bude neprakticka (lokalni populace musi byt z nejakeho duvodu nevhodna, pokud se snizil jeji genofond a globalne je mozna vhodne se ji zbavit), na druhou stranu je mozne, ze se objevi mutace, ktera fitness podstatne zvysi. Staci prihodit par milionu generaci a globalne to asi funguje ...

Prekvapive se podobne zmeny daji pozorovat jiz po 30-50 generacich ;-)

To je skutočne tenký ľad… Biologická evolúcia (ale aj evolúcia mémov), tak ako ju poznáme, prebieha v disipatívnom prostredí relatívne stáleho prietoku energie zo Slnka a zvnútra Zeme. Poznáme síce termodynamický rámec vnútorného preusporiadavanie systému povrchu tejto planéty, ktorý sa neustále nachádza v steve veľmi vzdialenom rovnováhe, ale stále nepoznáme dôvod, prečo sa tak deje, nejaký ten štvrtý zákon termodynamiky. Bolo viacero pokusov ho definovať (napr. Stuart Kauffman), ale faktom zostáva, že evolúcii nerozumieme. Preto je veľmi odvážne vidieť nejakú teleológiu, alebo teleonómiu evolúcie. Ale rovnako odvážne je vylučovať ju.

Takovehle veci uz se resi i na root.cz, menim disertacku. Musim si najit neco, co neni desne provarene.

... som tiez pouzil evolucny algoritmus. Potreboval som vypocitat koeficienty cislicoveho FIR filtra, ktore boli iba mocniny 2 (hlavnou temou mojej diplomovky bol navrh a realizacia takehoto tzv. beznasobickoveho filtra vo forme cipu). Klasicky postup - urobit inverznu Fourierovu transformaciu a potom pouzit "okno" nefungoval, pretoze pri zaokruhlovani na najblizsiu mocninu 2 dochadzalo vo vyslednej frekvencnej charakteristike k obrovskym chybam. Evolucny algoritmus fungoval perfektne a rychlo.

Pekne pouziti evolucniho algoritmu :)

Mimochodem, existuji algoritmy na Fourierku, ktere nepotrebuji zaokrouhlovat na nejblizsi vyssi mocninu dvojky -- http://en.wikipedia.org/wiki/Prime-factor_FFT_algorithm a http://en.wikipedia.org/wiki/Cooley-Tukey_FFT_algorithm#General_factorizations . Pokud dokazete zfaktorizovat pocet vzorku, dokazete spocitat FFT rychle a presne.

Já myslím, že ty mocniny dvou se netýkaly velikosti bloku na FFT. Jestli jsem to pochopil správně, tak byl cílem FIR fltr jen ze sčítaček a posunů. FFT bylo zmíněné jen jako obvyklý způsob, jak je možné získat koeficienty pro filtr.

Presne tak, samotna Fourierova transformacia mala len 32 vzoriek, neriesil som ju dokonca ako FFT ale len ako DFT.
Mocniny 2 boli tie koeficienty, aby bolo mozne filter realizovat len pomocou scitaciek a "barrel shiftera" (nenapada ma vhodny slovensky/cesky vyraz).

posuvný registr

Operaci se česky říká bitový posun/rotace. Jak se říká součástce, nevím. Po vzoru sčítačka/násobička bych se odhodlal k rotačce.

to vyzera na velmi zaujimavy serial, tesim sa na dalsie casti, good work

Chodil jsem na hodne prednasek z umele inteligence kdysi davno na MFF, ale dost me demotivovalo, ze jsme meli opravdu malo praktickych prikladu, kdy tyhle veci byly na neco prakticky pouzitelne. (A ono to bylo i tim, ze ty zakladni modely vetsinou byvaji nepouzitelne :-) ) Kdyz ma clovek nejaky priklad, ktery je na neco dobry (a nejde vyresit nejakym elementarnim algoritmem, ktery by napadl kazdeho), tak je to pak mnohem vetsi radost.

K (docela pěknému) článku bych měl několik výhrad:

1. Autor pracuje s pojmem optimum, což je u těchto algoritmů poněkud zavádějící. U takto složitých problémů se na hledání optima prostě rezignovalo. Najít to skutečné optimum (čili globální) by totiž znamenalo prohledat celý prostor řešení (kterých může být 2^n, n! apod.), což není možné. Co se hledá je nějaké "dost dobré" řešení, přičemž o jeho vztahu ke skutečnému optimu nemusíme vědět vůbec nic (existují problémy, kde o optimu nevíme vůbec nic).

2. Abychom křížením a mutacemi nepřišli o nejlepší dosud nalezená řešení, doplňuje se algoritmus o takzvané elitářství - prostě jednoho až několik nejlepších jedinců zkopírujeme do další generace beze změny.

3. Autor vůbec nezmínil nic o reprezentaci jedince. To je pro pochopení algoritmu (podle mě) docela důležitá informace. Zde se používá terminologie genetiky. Jeden jedinec je reprezentován genem. Gen se skládá z chromozomů, kde jeden chromozom představuje jeden parametr řešení. Gen pak je řetězec všech parametrů jednoho řešení (všechna řešení mají pochopitelně stejný počet parametrů, tedy chromozomů). Křížení se provádí tak, že se zvolí místo dělení genů a chromozomy za tímto místem si jedinci prohodí. Vůbec tedy nejde o průměrování. Po křížení můžou být výslední jedinci někde úplně jinde. Po křížení se na každého jednice aplikuje mutace (s nějakou pravděpodobností). Nakonec se provede výběr jedinců do další generace na základě fitness funkce.

3. Ještě shrnu parametry algoritmu: velikost populace, počet elit, funkce pro výběr jedinců ke křížení (které sama o sobě má nějaké parametry), funkce pro výběr místa pro křížení, pravděpodobnost mutace a fitness funkce.

napadne mi to pripomina obsah prednasek predmetu PAA z FELu:

http://www.fel.cvut.cz/education/bk/predmety/11/47/p11473704.html

http://service.felk.cvut.cz/courses/36PAA/

kazdopadne clanek a problematika sama je zajimava a opakovani je matka moudrosti :-)

Nechci sem tahat politiku, ale nápadně mně to připomíná chování se EU k dnešní evropské populaci a celkový globální vývoj.

Nestacilo by danu funkciu zderivovat.?

Stacilo, ale evolucne algoritmy sa pouzivaju hlavne vtedy, ked prislusnu funkciu nepozname.

No, to by ještě jako motivace nestačilo. Na vyšetření neznámé jednorozměrné funkce máme spolehlivější a levnější algoritmy než ty evoluční.

Evoluční algoritmy začínají být zajímavé až při vícerozměrných funkcích, které vyšetřit buď vůbec nejde (nekonečné), nebo to není rentabilní (spočetné nekonečno). Ono u storozměrné funkce klasická matematika selhává. Pro takové funkce se vyplatí vytvořit model, kde náhodně vygenerujete hodnotu pro každý ze 100 rozměrů a označíte to za "genetickou informaci". V článku popsanou metodou pak proběhnete zlomek celého stavového prostoru a doufáte, že z toho něco vypadne. Pokud genetická informace spočívá v jediném reálném čísle, tak toho opravdu moc "nenaevoluujete".

Na evoluční algoritmy a jejich použití se dá dívat jako na náhodné generování hodnot a ověření jejich výsledků. Evoluční složka algoritmu pak jen pomáhá generovat sadu dalších náhodných hodnot tak, aby se s vyšší pravděpodobností generovaly v zajímavých oblastech. V situaci, kdy hodnoty v bodě A a v bodě B nevypovídají nic spočitatelného o hodnotách bodů mezi nimi, a v situaci, kdy můžete ověřit jen zanedbatelný zlomek možných kombinací, to dává lepší výsledky než jen prostá náhoda.

Supr, těším se na další.

Ještě bych připomněl, že jen vytváříme model něčeho, čemu trošku rozumíme, a využíváme to pro své účely.