S mravencem ve Fukuoce
na astronautickém kongresu
IAF 2005Japonsko
Fakulta aplikované informatiky
Univerzita Tomáše Bati ve Zlíně
Ing. Zuzana Oplatková[email protected]
23. února 2006
Planetárium, Praha
Jak to celé začalo...• Byla mi doporučena web stránkahttp://www.estec.esa.nl/outreach/iaf• Následovalo napsání abstraktu• Čekání na výsledek předvýběru ESA• Poslání abstraktu přímo k výběru na kongres IAF• A výsledek se dostavil• Byla jste vybrána k ústní prezentaci• Poslat článek
• Huráááááááá!!!! jede se do Japonska, teda letííí
Můj projekt• Nastavení optimální trajektorie
robota s využitím symbolické regrese
• komparativní studie Analytického programování s Genetickým, kde robot byl definován jako umělý mravenec, který má sníst všechno jídlo na vyznačené cestě
0 5 10 15 20 25 30
0
5
10
15
20
25
30
Symbolická regrese s použitím evolučních algoritmů
• Genetické Programování – John Kozawww.genetic-programming.com
• Gramatická Evoluce – Conor Ryanwww.grammatical-evolution.org
• Analytické Programování – Ivan Zelinkawww.ft.utb.cz/people/zelinka/ap
Evoluční algoritmy
• nástroj umělé inteligence pro optimalizaci
• nalezení optimálních (nejlepších možných) hodnot nějaké zadané úlohy
• příklad – obchodní cestující má seznam měst, které objet, nejlépe co nejrychleji a nejkratší cestou, aby se co nejvíce ušetřilo – času i financí
• úlohu popisuje tzv. účelová funkce
Evoluční algoritmy– účelová funkce
• optimální hodnoty jsou v extrému (minimu) účelové funkce
• příklady jednoduché jednoextrémové a složitějších víceextrémových funkcí
Evoluční algoritmy – jak fungují• populace jedinců, kteří obsahují numerické
hodnoty argumentů účelové funkce• v první populaci jsou hodnoty vygenerované
náhodně• každý jedinec je ohodnocen kvalitou – jak moc se
blíží k extrému – hodnota účelové funkce (CFE)• CFE je hlavním kriteriem pro vývoj populace na
základě operací typu křížení jedinců, mutace jedinců a podobné operátory, které jsou různé pro různé evoluční algoritmy
• cílem je vyšlechtit jedince, který (kteří) dosáhnou extrému
Symbolická regrese – Analytické programování
• nadstavba evolučních algoritmů• cílem je najít symbolický zápis, který proloží změřená data
co nejlépe• Analytické programování zajišťuje generování symbolického
zápisu a evoluční algoritmy hledají nejlepší zápis• účelová funkce je tedy rozdíl právě vygenerované funkce a
dodaných ( změřených) dat• nejlepší řešení je takové, kde účelová funkce je nulová
Fcost = |DataSet – FAP(t )|
Analytické programování II
• princip generování symbolického zápisu• funkční předpis je generován z
jednoduchých funkcí• jedinec obsahuje číselné indexy• jednoduché funkce se seskládají do
složitého až před ohodnocením kvality• operace evolučních algoritmů probíhají
na číselném indexu
GFSall = {+, -, /, ^, d/dt, Sin, Cos, Tan, t, C1, Mod, ...}GFS3arg= {BetaRegularized, ...}GFS2arg= {+, -, /, ^, Log, Mod, GammaRegularized...}GFS1arg= {Sin, Cos, Tan, Abs, Re, Im, ...}GFS0arg= {t, x, y, z, C1, C2, Kinchin, ...}
^ / -
z / x
{1, 6, 7, 8, 9, 9}
GFSall = {+, -, /, ^, d/dt, Sin, Cos, Tan, t, C1, Mod, ...}
Sin(Tan(t))+Cos(t)
Individual in population =
Resulting function by AP =
Mapping by AP
Analytické programování III
• Analytické programování pracuje nejen s klasickými matematickými funkcemi typu plus, minus, proměnné x, konstant, ale také
• s textovými výrazy typu And, Nand – pro design elektronických obvodů
• nebo s příkazy typu Jdi rovně, zahni vprava, zahni vlevo, jako je v případě umělého mravence
Robot alias umělý mravenec
0 5 10 15 20 25 30
0
5
10
15
20
25
30
Stezka Santa FeSada jednoduchých funkcí
GFS0 = {Left, Right, Move}GFS2 = {IfFoodAhead, Prog2}GFS3 = {Prog3}
Účelová funkce
CV = 89 – NumberFood
černá – jídlo, něco, co se dá sebrat
šedá = bílá – volné políčko
Použité evoluční algoritmy
SamoOrganizující se Migrační Algoritmus (SOMA)
Diferenciální Evoluce (DE)
Parametr Hodnota
PathLength 3
Step 0.22
PRT 0.21
PopSize 200
Migrations 50
MinDiv -0.1
Délka jedince 50
Parametr Hodnota
NP 2000
F 2
CR 0.2
Generations
1000
Délka jedince
50
Výsledky simulací - DEDE simulací - 1
Počet ohodnocení účelové funkce = 9493
IfFoodAheadMove,Prog2IfFoodAheadIfFoodAheadProg3Prog2
Prog3Prog2Left, Right, Prog2Right, Right,Right, IfFoodAheadLeft, Prog2Left, Right,
Prog3Right, Right, Right, Prog2Right,IfFoodAheadIfFoodAheadLeft, Left,Prog3Move, Move, Left, Left,
Right, Prog3Prog2IfFoodAheadLeft,IfFoodAheadProg2Move, Left, Right, Right,
IfFoodAheadMove, Right, Move
Potřebné kroky k sebrání veškerého jídla = 409
Výsledky simulací II - SOMA
Počet příkazů
Počet kroků
Počet kroků
Počet příkazů
396 49532 50544 16548 50551 43551 50562 50574 27577 15589 21594 11594 14601 50606 16
11 59414 59415 57716 54416 60621 58927 57443 55149 39650 53250 54850 55150 56250 601
Počet příkazů
Maximum 50
Minimum 11
Průměr 33
Počet ohodnocení
účelové funkce u SOMA
Minimum 3 396
Maximum 116 715
Průměr 49 703
2 4 6 8 10 12 14Hit
0
20000
40000
60000
80000
100000
tsoCnoitcnuFsnoitaulavE
Počet kroků
Maximum 606
Minimum 396
Průměr 559
Výsledky simulací IIIIfFoodAheadMove,IfFoodAheadIfFoodAheadLeft, Prog3
IfFoodAheadProg2IfFoodAheadProg2Move,Prog2Prog2Left, Right, Left, Move,
Move, Prog3Prog2Move, Move, Move,Prog2Move, Prog2IfFoodAheadProg2Left,
Left, Right, Prog2Move, Left,Move, Right, Prog2Left, IfFoodAheadMove, Prog2Prog2Right, Prog2Right,
IfFoodAheadMove, Left, MoveNejrychlejší cesta z pohledupočtu kroků, ale jeden z nejdelších zápisů
Prog3Move, Right,IfFoodAheadMove, Prog3Left,Left, IfFoodAheadMove, Right
Nejkratší zápis, ale jednaz nejdelších cest, co se kroků týká
396 kroků 594 kroků
Závěry• Analytické programování je schopné řešit
problémy symbolické regrese
• V porovnání s Genetickým programováním rychlejší (menší počet ohodnocení účelové funkce a menší počet jedinců v populaci)
GP – (GA) AP – (SOMA,DE)
počet jedinců 4000 200
počet ohodnocení 1 000 000 130 000
• AP umožňuje použít jakýkoli evoluční algoritmus, GP pouze Genetické algoritmy
Závěry II – použití AP
• matematická regrese – fitování neznámých dat vhodnou křivkou
• design elektronických obvodů• nastavení optimální trajektorie robota• identifikace soustav v řízení
• další aplikace typu řízení chaosu• vhodné posloupnosti příkazů pro činnost robota• ....
A po práci legrace...
• Cestě do Japonska předcházela návštěva centra ESTEC (Evropský vesmírný výzkum a technologické centrum) v Noordwijcku v Holandsku
• prezentace o navigaci, vesmírné stanici, prohlídka centra – výzkumníci a kosmonauti v akci
• Následovala sada fotek, které je možné vidět i na
www.japan2005.ic.czAby prezentace nenabírala na své objemnosti
ESTEC - foto
Zamávali jsme ESTECu a čekal nás dlouhý let do Japonska...
Typický japonský hotel - ryokan
Japonské jídloJaponské jídlo
Kongres IAF 2005
Kongres IAF 2005 II
A to je vše
Děkuji za pozornost a někdy zase nashledanou
Dotazy ráda zodpovím hned
popř. na emailu [email protected]
