Prírodou inšpirované algoritmy

Úvod do EHW

Evolučný hardware môžeme definovať ako aplikáciu evolučných metód a algoritmov do hardwaru. EHW je založený na idei kombinovania rekonfigurovateľných hardwarových zariadení s genetickým algoritmom. Štruktúra takého zariadenia može byť zmenená kedykoľvek privedením reťazca konfiguračných bitov. Typickými predstaviteľmi tohto hardwaru sú FPGA (Field Programmable Gate Array) a PLD (Programmable Logic Devices), aj keď ich rekonfigurácia sa musí prevádzať manuálne. Ich architektúra sa mení použitím genetických algoritmov (ďalej GA). To dáva EHW výhodu pracovať v reálnom čase a vlastnosť nezávisle meniť svoju vnútornú štruktúru on-line. Binárny reťazec, ktorým sa mení štruktúra sa nazýva architecture bits (A-bity). Tieto A-bity sú kompiláciou výsledkov z boolovských funkcií a pravdivostných tabuliek GA je robustný algoritmus, ktorý hľadá lepšie riešenia. Idea EHW spočíva v posudzovaní A-bitov konfigurovateľných zariadení ako chromozómov GA a hľadať lepšiu hardwarovú štruktúru pomocou GA.

Každý systém na báze EHW môžeme charakterizovať 4 vlastnosťami :

1. Biologická inšpirácia

• fylogenéza - s analógiou s prírodou použitie GA, ktoré sú matematicky dobre špecifikované algoritmy a zachytávajú podstatu evolúcie. Začínajú s náhodne generovanou populáciou riešení a k výsledku sa dopracujú náhodnou permutácoiu a krížením riešení, ktorých prežitie záleží od ich vhodnosti

• ontogenéza - s analógiou vývoja mnohobunkových organizmov. Ide o postupné delenie materskej bunky, prenos genetickej informácie. Špecializácia dcérskej bunky je podmienená pozíciou v množine. Tento prístup sa používa v bunkových automatoch (Cellular Automats)

• epigenéza - s analógiou učenia v prírode. Napodobnenie nervového systému, spojenie neurónových sietí s evolučným algoritmom

2. Proces vyhodnocovania

• on-line (intrinsic) - samotný evolučný proces je hardwarovo implementovaný

• off-line (extrinsic) - evolučný proces funguje na softwarovej báze a v určitých cykloch je aktualizovaný HW čip

3. Prístup programovania

• genetické algoritmy (GA) - napodobňujú evolúciu v prírode aplikovaním kríženia a mutácie na binárne kódovaný genotyp

• genetické programovanie (GP) - rozširuje ideu GA do sveta počítačov. Chromozómy sú reprezentované ako stromy s orientovanými vetvami, ktorých vnútorné uzly sú funkcie a listy sú premenné alebo konštanty

• evolučné programovanie (EP) - odlišuje sa od predchádzajúcich prístupov v kódovaní chromozómov ako aj v genetických operátoroch. Chromozóm je charakterizovaný celým alebo reálnym číslom

4. Oblasť využitia

EHW je vhodné využiť v aplikáciach, kde sa vyžaduje práca v reálnom čase a autonómna on-line adaptácia. Napríklad : rozpoznávanie obrazov, ovládanie robotov, digitálny návrh obvodov a VLSI, riešenie "fault tolerance" problému