Archive for the ‘ aplikace evolučních algoritmů ’ Category

návrh antény pro NASA pomocí evolučních algoritmů

Možná cesta pro budoucí vynálezy je jejich detailní popis a následné počítačové řešení problému tak, jako to udělal Gregor Hornby z NASA při návrhu antény pro družice. Velice zajímavé pdfko ukazuje čeho všeho jsou schopné evoluční algoritmy (zde je popsán první návrh hardwaru pomocí evolučních algoritmů) a naznačuje jejich široké uplatnění v průmyslu a designu produktů.

EAM – stavový prostor a výpočet fitness funkce verze 2

V minulých článcích jsem psal o stavovém prostoru mého prográmku na rozpoznávání vzorů.Nyní je čas tento problém vyřešit a vysvětlit (-:

Příklad:

V Bitmapě máme za úkol najít bunky, o kterých víme

  1. mají kruhový tvar
  2. mají očekávaný poloměr ro
  3. můžou být v jejich středu prosvětlené
  4. v bitmapě jich je omezené množství, většinou je jich víc než 1

Jako fitness funkci můžeme použít: (Obsah kružnice o středu S a poloměru r= ro) -( Obsah kružnice o středu S a poloměru  r < ro).

Získáme tak obsah jakéhosi prstence okolo středu, kterým je x,y hodnota chromosomu.

Výpočet stavového prostoru: Počet možných řešení získáme jako podíl obsahu prohledávané bitmapy a obsahu útvaru, který označuje toleranci středu, na obrázku označený černou barvou.

pro bitmapu o rozměrech 100×100 pixelů a toleranci středu 5 pixelů je tedy stavový prostor 100000/25 = 400

EAM – kombinace evolučních algoritmů a gradientních metod

Z testů mého prográmku jsem zjistil že nejlepší výsledky přináší kombinace evolučních algoritmů, prohledávající velký stavový prostor v kombinaci s gradientními metodami, které  „doladí“ řešení – jsou jemnějším nástrojem a dokážou lépe vyhledat lokální extrém.Mě se osvědčilo použití tzv Hill climbingu do 4 základních směrů

EAM – stavový prostor ?

Při hledání globálního extrému fce je určení stavového prostoru celkem jednoduché, je to interval ve kterém hledáme vynásobený „vzorkovacím intervalem“ – hledáme od nuly do sta  s krokem 1.V případě, kdy prohledáváme 2D prostor – bitmapu a  fitness funkce je definována jako obsah čtverce (pro zjednodušení) by měl být stavový prostor definovaný jako obsah bitmapy/obsah „fitness čtverce“ ? Co překrývání těchto čtverců ?

EAM – fitness funkce

Fitness funkce obecně

Fitness funkce je přiřazení, které každému jednomu řešení gentického algoritmu (Chromosomu) přiřadí ohodnocení.Čím je jeho hodnota vyšší, tím je chromosom kvalitnější (Blížíme se k hledanému řešení).

Fitness funkce v případě EAM

Protože se snažíme najít souřadnice bodu, který je přesně uprostřed bunky na bitmapě, musíme nějakým způsobem spojit Chromosmy, které obsahují pouze zakodované XY hodnoty s prozkoumávanou bitmapou.Jediným pojítkem algoritmu s prostředím (bitmapou) je Fitness funkce.Potřebujemě nějakým způsobem zjistit,  jestli bod na pozici XY leží uprostřed buňky nebo vedle,  nejlépe s určitou tolerancí.

Prvním návrhem bylo zavést fitness funkci jako součet všech pixelů, které měli barvu přibližně stejnou jako hledaná buňka a to ve čtverci o délce strany shodné s hodnotou R chromosomu a XY souřadnicemi středu odpovídajícimi X a Y hodnotám chromosomu.

protože jsou ale buňky  občas uprostřed prosvětlené, zavedl jsem zatím fitness funkci  jako „rám“ okolo středu – počítá se tak pouze se čtvercem bez vnitřního čtverce  menším půměru – případné středové prosvětlení nám nezkreslí fitness ohodnocení

Na obrázku je takový rám znázorněný bílou barvou a je u něj uvedena jeho fitness hodnota.

EAM – zakodování chromozomů

Základní jednotkou genetického algoritmu je gen, což je nějakým způsobem zakodovaná informace.Může to být XY souřadnice bodu,X souřadnice v grafu nebo hrana grafu.Druhou důležitou entitou je chromosom, který se skládá z několika genů.V našem případě je architektura nastavená tak, že jeden Chromosom představuje hledané řešení (každý chromosom představuje tím kvalitnější řešení, čím je jeho fitness hodnota větší).

Chromosom se skládá ze 3 devítibitových hodnot (genů) a to

  • X souřadnice
  • Y souřadnice
  • R – délka strany čtverce

náš chromosom má tedy 3*9 =27 bitů a maximální velikost zpracovávané bitmapy je tedy 2 na devatou *2  = 1024bitů tzn maximální velikost bitmapy krevního rozboru je 1024 x 1024.

EAM – znázornění algoritmu

BPMN diagram popisující genetický algoritmus vytváření nových generací.Algoritmus zatím neobsahuje stop podmínky v případě, že bude nalezeno řešení brzy, tudíž algoritmus proběhne tolikrát, kolikrát mu to určíme v konfiguraci aplikace.