Nové přístupy k návrhu adaptivních elektronických obvodů s využitím evoluce

Počítačoví inženýři se často při konstrukci počítačů a algoritmů inspirují v biologii. Typickým příkladem jsou evoluční algoritmy inspirované Darwinovou evoluční teorií, které se objevily v 60. letech, ale velké popularity se jim dostalo až začátkem 90. let minulého století. Evoluční algoritmus pracuje s populací bitových řetězců reprezentujících kandidátní řešení problému. Počáteční populaci počítač vygeneruje náhodně, další populace jsou generovány s využitím operátorů, jako jsou např. křížení a mutace, pracujících s těmito řetězci. Do dalších populací se s větší pravděpodobností dostanou ty řetězce, které představují lepší řešení zadaného problému. Kvalitu řetězců určuje tzv. účelová funkce, ve které je zakódována specifikace řešeného problému.

Například když hledáme optimální tvar křídla letounu, tak bitový řetězec obsahuje sadu koeficientů křivek, kterými je popsán tvar křídla. Účelová funkce pak vysoce ohodnocuje ty sady koeficientů (ty tvary křídel), která zajišťují rychlejší a levnější let. Necháme-li evoluční algoritmus vytvořit pár tisíc populací, můžeme získat na konci evoluce velice zajímavý tvar křídel, který třeba vůbec nelze získat konvenční metodou. V posledních letech se evoluční algoritmy stále častěji používají pro návrh. Novému odvětví se říká kreativní evoluční design. Pomocí evoluce byly navrženy různé unikátní mechanické konstrukce, stavby, počítačové programy, elektronické obvody, molekuly nebo umělé živé systémy. Existuje evoluční umění – evoluční návrh obrazů a hudby. Cílem je dosáhnout automatického návrhu. Návrhář pouze specifikuje, co se má udělat, a ne jak se to má udělat. Řešení poskytne evoluce. Bylo prokázáno, že evoluce automaticky (sama od sebe) dokáže navrhnout vysoce efektivní produkty, které není možné známými inženýrskými metodami vytvořit. Příkladem jsou elektronické obvody. Počítačoví inženýři používají pro realizaci hardware tzv. rekonfigurovatelné obvody. Tyto obvody mají tu vlastnost, že se jejich fyzické zapojení vytvoří pouhým zápisem vhodné informace (konfiguračního řetězce) do tzv. konfigurační paměti. V průběhu činnosti se může tato konfigurační informace měnit a obvod tak může měnit svoje fyzické propojení a tím i svoji funkci. V novém oboru, který se nazývá vyvíjející se obvody (evolvable hardware), se konfigurační informace vytváří pomocí evolučního algoritmu. Lze tak automaticky navrhovat unikátní elektronické obvody. Navíc je možné vytvořit hardware, který se umí adaptovat na měnící se prostředí. Při změně požadavku na funkci obvodu teoreticky stačí pouze spustit evoluční algoritmus a ten najde vhodný obvod automaticky. Toto je důležité např. pro systémy pracující ve vesmíru, kde potřebujeme provádět změny zařízení za provozu a bez přímého zásahu člověka. Problémem je, že evoluční algoritmus nezaručuje, že se nějaké vhodné řešení vždy najde. Zatím se popsaným způsobem podařilo navrhnout jen relativně jednoduché obvody. Jeden typický evoluční design může trvat několik hodin, dní i týdnů.

Projekt

Ve svém projektu jsem se zabýval návrhem metody pro evoluční (tedy automatický a autonomní) návrh relativně složitých číslicových obvodů, což je důležité pro praxi. Dále bylo požadováno, aby doba návrhu byla přijatelně dlouhá. Pokud by byla evoluce schopna najít požadovaný obvod např. za minutu, potom by bylo možné postavit stroj (hardware), který je schopen adaptovat svoji fyzickou strukturu (a tedy i chování) na prostředí měnící jednou za minutu. To je např. důležité pro rozpoznávání obrazu snímaného kamerou v reálném čase. Najít nějakou informaci v měnícím se obraze jen pomocí běžného počítače bez speciálního hardware je časově téměř nezvládnutelné. Navržená metoda vychází z originální implementace kartézského genetického programování v rekonfigurovatelném obvodu. Metoda byla úspěšně vyzkoušena pro návrh adaptivních obrazových filtrů pracujících v multimediálních nebo vestavěných systémech. Tyto obvody mají za úkol odstranit šum z obrazu nebo zvýraznit některé části obrazu. Evolucí byly navrženy unikátní obvody vykazující vyšší kvalitu a někdy i nižší implementační cenu v porovnání s doposud nejlepšími známými obvody, které inženýři běžně používají pro řešení dané úlohy. Zajímavé je, že ač tyto obvody skvěle pracují, nerozumíme jejich vnitřní funkci. Evoluce zkrátka konstruuje tyto obvody jinak, než se to učíme ve škole. Rovněž jsme potvrdili, že v této třídě úloh může evoluční návrh (stroj) zastoupit kreativního konstruktéra (člověka).

Dále jsem navrhl metodu, pomocí které se dá celý evoluční systém realizovat v běžně dostupných a tudíž i relativně levných rekonfigurovatelných obvodech, což bylo předtím téměř nemožné. Řešení je založeno na konstrukci tzv. virtuálního rekonfigurovatelného obvodu, jedinečného pro každou aplikaci. To v důsledku vede k urychlení a zlevnění celého procesu návrhu a rovněž k zlevnění celé aplikace. Tyto praktické výsledky, o které již má zájem komerční sektor, byly získány na základě teorie vyvíjejících se komponent, kterou jsem rovněž zavedl. Součástí teorie je formální matematická definice tzv. vyvíjejícího se výpočetního stroje a mimo jiné i zjištění, že takový stroj vykazuje za jistých podmínek vyšší výpočetní sílu než standardní Turingův stroj používaný v teoretické informatice ke studiu vyčíslitelnosti a složitosti algoritmů.

Autor o sobě

Oproti Japonsku, Anglii, USA a několika zemím západní Evropy se v České republice a zemích střední Evropy problematikou biologií inspirovaného hardware doposud nikdo nezabýval. Proto jsem si tuto problematiku vybral již jako téma své diplomové práce, kterou jsem obhájil na Fakultě elektrotechniky a informatiky Vysokého učení technického v Brně v roce 1999. Ve výzkumu jsem pilně pokračoval i během svého doktorského studia na Fakultě informačních technologií VUT v Brně pod vedeném doc. Vladimíra Drábka. Za svůj největší úspěch považuji, že na základě doktorské práce, kterou jsem obhájil v roce 2002, vznikla monografie nazvaná Evolvable Components: From Theory to Hardware Implementations, která letos vyjde v prestižní edici Natural Computing Series nakladatelství Springer Verlag.

Výsledky výzkumu jsem průběžně publikoval na významných konferencích oboru jako jsou např. NASA/DoD Conference on Evolvable Hardware, Evolvable Systems: From Biology to Hardware, European Conference on Genetic Programming, Field Programmable Logic and Applications apod., celkem asi 25 článků. Zejména práce publikované bezprostředně po ukončení magisterského studia vedly k pozvání na Pennsylvania State University v USA (kde jsem působil v letním semestru 2001 jako hostující lektor) a k řešení výzkumného projektu na University of Oslo (2001). Byl jsem hlavním autorem článku, který získal cenu za nejlepší příspěvek na konferenci IEEE Design and Diagnostics of Electronic Circuits and Systems (Brno, 2002) a za jiný článek jsem získal cenu za nejlepší prezentaci na konferenci Evolvable Systems: From Biology to Hardware (Trondheim, 2003). Dvakrát jsem získal cenu Fóra průmyslu vysokých škol ČR a společnosti Siemens (1999 a 2000). Na základě dosažených výsledků jsem byl pozván mimo jiné do programového výboru nejvýznamnější konference v oboru: Evolvable Systems: From Biology to Hardware 2003. Problematiku vyvíjejících se obvodů jsem společně s doc. Drábkem popularizoval v časopise Vesmír. O výzkumu vyvíjejících se obvodů na Fakultě informačních technologií byl natočen dokument, který bude Česká televize vysílat v rámci magazínu Popularis. V současné době řeším výzkumný projekt Metody návrhu aplikací založených na vyvíjejících se obvodech, který financuje Grantová agentura ČR. Cílem je rozvíjet teorii vyvíjejících se obvodů a připravit průmyslové aplikace. Kromě informatiky a výpočetní techniky se zajímám o evoluční biologii a využití evolučního návrhu pro nanotechnologie.

Napsat komentář

Vaše e-mailová adresa nebude zveřejněna. Vyžadované informace jsou označeny *