Evoluční elektronika Lukáš Sekanina Vysoké učení technické v Brně, Fakulta informačních technologií Božetěchova 2, 612 66 Brno
[email protected]
Bratislava 18. 10. 2010
Obsah • Úvod do evoluční elektroniky
evoluční návrh rekonfigurovatelná zařízení
• Kartézské genetické programování (CGP) • Evoluční návrh hardware (na FIT)
evoluční syntéza kombinačních obvodů evoluce obrazových filtrů
• Důsledky pro inženýrský návrh
2
Evoluční algoritmus řešení
•
Evoluční algoritmus (EA)
•
•
vytvoř nová řešení
přímo nepřímo
mutace, křížení, …
Fitness funkce
•
ohodnoť populaci
Fenotyp - kandidátní řešení problému Genetické operátory
•
populačně orientovaný prohledávací algoritmus
Genotyp (chromozom) - datová struktura reprezentující kandidátní řešení
•
vytvoř počáteční populaci
ohodnocuje kandidátní řešení reflektuje specifikaci
Hlavní varianty
genetický algoritmus (GA) genetické programování (GP) evoluční strategie (ES) NASA AMES
3
Evoluční optimalizace a evoluční návrh • Evoluční optimalizace
EA je využit pro nalezení co nejvýhodnějších hodnot předem definovaných parametrů systému v oblasti HW velmi populární desítky let
• Evoluční návrh
EA je využit pro návrh struktury (včetně parametrů) cílového systému. V oblasti hardware od počátku 90. let.
• Aplikace evolučního návrhu
analogové a číslicové obvody, kvantové obvody, antény, optické systémy, robotika, molekuly, MEMS, software (symbolická regrese, klasifikace, predikce, …), umělecké artefakty, …
4
Rekonfigurovatelná zařízení Rekonfigurovatelné zařízení konfigurace
spínané kapacitory http://www.anadigm.com/
NanoCell http://www.jmtour.com/
Rekonfigurovatelné zrcadlo: www.okotech.com Operační transkonduktanční zesilovač – OTA FPTA, http://ehw.jpl.nasa.gov
FPGA, www.xilinx.com LCD displej http://www.evolutioninmaterio.com/
antény, http://www.lindenir.com
5 5
Field Programmable Gate Array (FPGA) •
Konfigurovatelné části
•
logické bloky (LUT) propojení I/O
Vestavěné bloky
paměti násobičky DSP PowerPC IO rockets ports řadič PCI
1 slice = 4x 6-LUT + 4x FF + pomocná logika
FX200T obsahuje 122880 6-vst. LUT Zpoždění 6-LUT je 0.9 ns
Více než 109 tranzistorů na čipu 23 x 23 mm! 6
Evoluční hardware (evolvable hardware) •
Evoluční hardware = EA + rekonfigurovatelné zařízení [Higuchi et al, 1993]
generátor kandidátních řešení
Evoluční algoritmus
rekonfigurovatelné zařízení (RZ) genotyp
konfigurace
dekódování
(genetické operace)
I/O hodnota fitness
fitness funkce (zahrnuje specifikaci)
- generuj vstupní hodnoty pro RZ - získej odezvu RZ - porovnej získané hodnoty s požadovanými - vyjádři hodnotu fitness
(simulátor)
7
Proč evoluční hardware? • Umožňuje zvýšit úroveň automatizace návrhu.
Problém návrhu systému je transformován na problém prohledávaní prostoru možných systémů. Automatizované generování vynálezů
• Mohou vzniknout úplně nová řešení, která jsou nedosažitelná konvenčním přístupem, který nepoužívá evoluční metodu „generuj a testuj řešení”.
Anténa pro misi NASA ST5. „Číslicové obvody“ využívající „konvenčním“ návrhem nepoužívané interakce komponent s materiálem a prostředím [Thompson, 1996].
8
Proč evoluční hardware? •
EA je použit během nasazení systému, aby zajistil adaptaci a/nebo opravu, pokud dojde ke změně specifikace, prostředí nebo k poruše.
•
Příklady aplikací
samoopravující se obvody v extrémním prostředí [Stoica et al., 2007] adaptivní kontrolér pro umělou končetinu [Kajitani et al., 1999] čip pro adaptivní bezeztrátovou kompresi obrazu [Salami et al., 1997] adaptivní výběr položky rychlé vyrovnávací paměti [Kaufmann et al, 2009]
9
Kartézské genetické programování (CGP)
[Miller, Thompson, 1999]
fenotyp
Specifikace (1b sčítačka)
genotyp Definice CGP:
počet řádků, u počet sloupců, v počet vstupů, ni počet výstupů, no počet vstupů uzlu, na L-back parametr, L množina funkcí, F
Příklad na obrázku:
u=3 v=3 ni = 3 no = 2 na = 2 L=3 F = {NAND (0), NOR (1), XOR (2), AND (3), OR (4), NOT (5)}
10
CGP: Fitness funkce Cílová tabulka
•
Fitness hodnota: F = počet správně určených bitů na výstupu pro všechny zadané vstupní kombinace (max. 16)
•
Pokud dosáhne F maxima, je možné optimalizovat např. počet hradel (popř. zpoždění apod.): F’ = F + N – U
kde N je celkový počet uzlů kde U je počet použitých uzlů
11
CGP: Mutace •
Náhodně vyber h integerů a nahraď je náhodně generovanými (ale legálními) hodnotami. Př. pro h = 1.
mutace
12
CGP: Prohledávací algoritmus • •
ES (1 + λ) Pokud existuje více nejlepších jedinců se stejnou fitness hodnotou, použije se jako rodič ten, který nebyl rodičem v předchozí generaci (viz obrázek).
Fitness 13
Fitness 13
Fitness 13
Fitness 06
Fitness 10
Fitness 10
Fitness 10
Fitness 09
Fitness 08
Fitness 11
Fitness 13
Fitness 15
Fitness 10
Fitness 13
Fitness 11
Vývoj fitness hodnot populace 5 jedinců.
13
CGP: Neutrální mutace
• •
Úloha: Evoluční návrh 3b násobičky [Vassilev, Miller: ICES 2000] Na obrázku je normalizovaná fitness hodnota pro 100 nezávislých běhů (10 mil. generací).
ON – algoritmus CGP OFF – jako nový rodič brán jedině ten, který má vyšší fitness hodnotu než stávající rodič 14
Evoluční návrh násobiček
[Vassilev, Miller EH 2000, GENP 1(1), 2000]
Dosaženo významného snížení počtu 2-vst. hradel v porovnání s konvenční syntézou. Počet 2-vst. hradel Array
ES(1+4), h=3,
Evolučně navržená násobička 3b x 3b
Uvedená metoda je účinná pro syntézu kombinačních obvodů s max. 10-20 vstupy. 15
CGP jako “minimalizátor” počtu hradel • Inicializace CGP konvenčním řešením a minimalizace počtu hradel – Best conv. = nejlepší výsledek z programu ABC (SIS) – CGP: λ = 14, h = 7, max. generací = 100M, pole 1 x ‘počet hradel z ABC’ Počet hradel
počet hradel
359 hradel 0,0 s
8b M/S circuit
260 hradel 211 s
235 hradel 0,6 hod. 205 hradel 5,8 hod.
LGSynth91 benchmarks
generace (Athlon64 3200+)
16
Škálovatelnost – ústřední problém návrhu s EA • EA výborně řeší „malé“ instance problémů, ale selhává na „velkých“ instancích. • Škálovatelnost reprezentace obvodu v chromozomu
Řešení: dodat znalost o problému do metody řešení • vyšší úroveň abstrakce, • inkrementální evoluce, • modularita, • nepřímé zobrazení genotyp-fenotyp
• Škálovatelnost doby evaluace kandidátních řešení
Řešení • omezit se na aplikace, kde problém nenastává • zavést úplně jiný pohled na evaluaci
17
Evoluční návrh na FIT •
Aplikace evolučního návrhu
•
Akcelerace EA
•
rekonfigurovatelný polymorfní ASIC (UMEL FEKT) aplikace v různých oblastech
Evoluce s FPTA-2 v extrémním prostředí (v NASA JPL, 2004) Nové přístupy k evolučnímu návrhu
• •
FPGA, výpočetní svazek, GPU
Polymorfní elektronika
• •
syntéza číslicových obvodů (FIT ČVUT v Praze) násobičky s násobnými konstantními koeficienty testovací obvody se zadanou úrovní testovatelnosti obrazové operátory (Univ. of Oslo) adaptivní vlnková komprese obrazu (Universidad Politécnica de Madrid) protokoly pro amplifikaci tajemství v bezdrátových senzorových sítích (FI MU v Brně) programy konstruující libovolně velké řadicí sítě syntéza polymorfních obvodů prediktory
ALPS, selekce, development, …
Plánování skupinových komunikací pro paralelní architektury (Jaroš, Dvořák) Interpretace evolučního návrhu z různých pohledů
18
CGP pro vylepšení konvenční syntézy log. obvodů [Vašíček, Sekanina, 2009-2010]
• Zavedena nová metoda pro evaluaci kandidátních logických obvodů. •
MINISAT (nástroj pro řešení SAT problému) je použit k rozhodnutí, zda jsou kandidátní obvod Ci a referenční obvod C1 funkčně ekvivalentní.
• Pokud jsou ekvivalentní, potom fitness(Ci) = počet hradel v Ci; • jinak fitness(Ci) = MAXVAL (cílem je minimalizovat). • Funkční ekvivalenci je obvykle možné pro reálné obvody zjistit v rozumném čase.
Konvenční syntéza (ABC, SIS…)
obvod C1 (referenční obvod; slouží k inicializaci počáteční populace)
CGP
optimalizovaný C1
BLIF (popis obvodu) 19
Konstrukce obvodu pro evaluaci C2:
C1:
? ≡ G:
Pokud se C1 a C2 funkčně liší, tak existuje alespoň jedna vstupní kombinace, pro kterou bude na výstupu 1. 20
CGP pro vylepšení konvenční syntézy log. obvodů • ES(1+1), 1 mut/chrom, Množina hradel: {AND, OR, NOT, NAND, NOR, XOR}, 100 běhů • Na sadě testovacích obvodů LGSynth93 došlo k redukci v průměru o 37,8% hradel. • Pracuje dobře i pro obvody obtížně syntetizovatelné konvenčními metodami [Fišer, Schmidt, Vašíček, Sekanina: DDECS 2010]. • Za cenu „času“ získáme pomocí CGP kvalitnější řešení než pomocí konvenčních metod.
21
Evoluční návrh obrazového filtru
[Sekanina, EvoIASP 2002]
CGP pro potlačení výstřelového šumu, dávkového šumu, pro detekci hran v obraze apod. CGP na úrovni funkčních bloků Filtr
s parametry ES(1+7), 5% mutace, pole 4x8, 100 běhů/30000 generací.
22
Fitness funkce Kandidátní řešení ohodnoceno pomocí trénovacího obrazu 128 x 128 pixelů. Fitness = střední absolutní chyba (výstup filtru, požadovaný obraz) K −2 K −2
fitness value = ∑∑ v (i, j ) − w(i, j ) fitness požadovaný obraz
i =1 j =1
Kandidátní filtr
fitness
poškozený obraz 23
Příklad nalezeného řešení
[Vašíček, Sekanina: FPL 2007]
a) Obraz poškozený 5% šumem „sůl a pepř“ PSNR: 18,43 dB (peak signal to noise ratio)
b) Původní obraz c) Mediánový filtr (okno 3x3 pixely) PSNR: 27,92 dB 268 FPGA slices; 305 MHz
d) Výsledek evoluce (okno 3x3) PSNR: 37,50 dB 200 FPGA slices; 308 MHz
d)
a)
c)
b) 24
Porovnání různých filtrů pro šum typu „sůl a pepř“ Průměr PSNR pro 25 testovacích obrázků
• • • •
MF – Mediánový filtr AMF – Adaptivní mediánový filtr EF - Evolučně navržený filtr SW filtr [Dong, Xu: A new directional weighted median filter for removal of randomvalued impulse noise. Signal Processing Letters. vol. 14, no. 3, p. 193–196, 2007] 25
Další příklady Impluzní dávkový šum [Vašíček, Sekanina, Bidlo: DATE 2010]
5%, N(255, 30)
Výstup evolučně navrženého filtru
Výstřelový šum + detekce hran [Vašíček, Sekanina: AHS 2007]
26
Šum “sůl a pepř” s vyšší intenzitou
268 slices
1506 slices
2024 slices
6567 slices
27
Banka filtrů
[Vašíček, Sekanina: FPL 2007]
• Jednotlivé běhy CGP poskytly mnoho různých a současně kvalitních implementací filtrů s filtrovacím oknem 3 x 3 pixely. • Banka filtrů
vybrané různé implementace filtru pracují paralelně nad oknem 3x3 Prefiltrace: if pixel [i] = 255 then pixel [i] := 0 Selekce: např. medián
28
Banka filtrů 3x3 (843 slices) vs adaptivní medián 7x7 (6567 slices)
29
Porovnání různých filtrů Průměr PSNR pro 25 testovacích obrázků
• • • • •
MF – Mediánový filtr AMF – Adaptivní mediánový filtr EF - Evolučně navržený filtr Banka filtrů SW filtr [Dong, Xu: A new directional weighted median filter for removal of random-valued impulse noise. Signal Processing Letters. vol. 14, no. 3, p. 193–196, 2007] 30
Banka filtrů – užitný vzor UV20017
[Sekanina, Vašíček 2009]
31
Akcelerace CGP v hradlovém poli Xilinx Virtex II Pro FPGA [Vašíček, Sekanina: IJICA 1(1), 2007 a C&I 2010 – v tisku]
32
Akcelerátor pro evoluční návrh obrazových filtrů • Platforma: Combo6X • CGP
4 x 8 procesních elementů trénovací obraz: 128 x 128
• Zrychlení (100 MHz)
1 VRC: 44x vs Celeron 2,4 GHz • ohodnocuje 6 tisíc kandidátních filtrů za sekundu • 10 sekund trvá evoluce jednoho filtru (~30 tis. generací) 4 VRC: Zrychlení je 170 vs Celeron 2,4 GHz
Výsledky syntézy pro Virtex II Pro 2VP50FF1517 (Nc je počet VRC)
33
Důsledky pro inženýrský návrh - patenty • Evoluční návrh umožňuje automatizovaně vytvářet patentovatelné vynálezy.
V USA patentovány evolučně vytvořené vynálezy, evoluční algoritmy i rekonfigurovatelné platformy. Existují desítky patentovaných vynálezů, které byly automatizovaně znovuobjeveny pomocí EA.
2010: • evoluce funkcí pro predikci struktury proteinu (U. of Nottingham)
• Soutěž Humies od r. 2004.
2004: • anténa (NASA AMES) • kvantové obvody (Hampshire College Amherst)
2005: 2006: • 2D fotonické • oscilátory s OZ krystaly (Cornell (MIT) U.) • optimalizace pulsu laseru (Colorado State U.)
Courtesy of John Koza’s team
2007: • polymerová optická vlákna (UCL)
2009: 2008: • aut. oprava SW • GP pro konečné algebry (U. New Mexico) (Hampshire College Amherst)
34
Důsledky pro inženýrský návrh – patenty (2) • Pokud je evoluční návrh úspěšný, potom výsledek většinou snadno splní požadavky novosti, nezřejmosti a využitelnosti.
Má smysl patentovat, pokud další běh EA vygeneruje jiné (ale stejně dobré) řešení? Je pro společnost užitečné, že (téměř) každý může automaticky generovat patentovatelné vynálezy? • Hrozí „patentová záplava“
• R. Plotkin: Genie in the machine (2009)
Je třeba nově interpretovat patentové právo, zejména požadavek na nezřejmost. Specifikace pro EA by měly být patentovatelné, ne vlastní vynálezy! Patentové právo by určovalo, kdo má právo vytvářet vynálezy a ne kdo vlastní vynález.
35
Důsledky pro inženýrský návrh • Pokud je evoluční návrh prováděn s rekonfigurovatelným zařízením, může vzniknout řešení, které pracuje jen v použitém rekonfigurovatelném zařízení [Thompson, 1996].
EA je schopen využít pro řešení problému i ty fyzikální vlastnosti platformy a prostředí, které člověk neuvažuje. Vzniká třída výpočetních zařízení, které nemohou existovat bez fyzikální podstaty [Sekanina: Minds and machines 17(3), 2007]. Můžeme zadat i získat požadované chování, ale nevíme, jak je realizováno.
• Výpočetní stroje, které interagují s prostředím, přizpůsobují funkci prostředí a neukončují výpočet, nesdílí výpočetní scénář Turingova stroje [van Leeuwen, Wiedermann, 2001].
36
Shrnutí • Evoluční návrh proniká z konferencí o evolučních algoritmech do konferencí o hardware, software, počítačových sítích…
Začíná být „běžnou metodou“.
• Evoluční návrh nemůže úplně nahradit inženýra, stává se ale jeho čím dál výkonnějším pomocníkem.
Umožňuje automatizovat činnosti, které byly doposud výlučně v kompetenci člověka-návrháře.
• Adaptivní a samoopravující se hardware inspirující se biologickým fenoménem evoluce zatím v aplikacích není vidět.
Existuje málo reálně použitelných aplikací. Komerčně nezajímavé?
• Bylo prokázáno, že evoluční design umí něco, co člověk jako designér nedokáže. A to je velmi zajímavé pro další výzkum. • Potřebujeme ověřit a klasifikovat co nejvíce různých aplikací a vytvořit bázi znalostí, které pomohou určit, kdy je EA vhodnou metodou pro konkrétní aplikaci.
37
Děkuji za pozornost!
38
