Nástroje pro kartézské genetické programování Tools4CGP

1. Úvod

1. Všeobecné informace

Tools4CGP je sada nástrojů pro práci s kartézským genetickým programováním (CGP), která obsahuje implementaci CGP, modul pro načítání vstupních dat a prohlížeč chromozomů (cgpviewer). Tools4CGP jsou vytvořeny v jazyce C. Prohlížeč chromozomů cgpviewer umožňuje zobrazit chromozom CGP, simulovat ho a exportovat do různých formátů (VHDL, bmp).

Informace o způsobu licencování, autorech a další informace je možné nalézt zde: Produkty - Tools4CGP

1.1. Kartézské genetické programování

Kartézské genetické programování (CGP) lze chápat jako variantu genetického programování, která se od genetického programování liší v reprezentaci řešeného problému. Zatímco v GP je hledané řešení reprezentováno pomocí stromu, CGP reprezentuje problém pomocí grafu s pevným počtem uzlů. Každý z uzlů může realizovat jednu z několika pevně daných funkcí a může být spojen na výstup některého z předešlých uzlů. Konektivitu ovlivňuje tzv. l-back parametr. Chromozom je určitá posloupnost celočíselných hodnot mající fixní délku. Algoritmus používaný v CGP odpovídá evoluční strategii (1+L), kde hodnota L se pohybuje řádově v jednotkách. Používá se pouze operátor mutace.

Struktura rekonfigurovatelného obvodu
Obrázek 1.1: Struktura rekonfigurovatelného obvodu

Základní informace o CGP je možné nalézt např.:

  • Vašíček, Z., Sekanina, L.: Evoluční návrh kombinačních obvodů. Elektrorevue 43/2004. Článek v PDF verzi si můžete stáhnout zde.

  • Miller, J., Job, D., Vassilev, V. K.: Principles in the Evolutionary Design of Digital Circuits -- Part I. Journal of Genetic Programming and Evolvable Machines, Vol. 1, No. 1, 2000, pp. 8-35. Dostupné zde.

1.1.1. Kódování řešeného problému

Chromozom je složen z mxn trojic (m - počet sloupců, n - počet řad) celočíselných hodnot, kde první dvě hodnoty udávají číslo výstupu, na který je připojen první a druhý vstup trojici příslušejícího elementu, třetí hodnota udává jakou logickou funkci element realizuje. Na konci chromozomu je l-tice o velikosti shodné s počtem výstupů hledaného obvodu. Každý prvek l-tice určuje index elementu (jeho výstupu), na který bude primární výstup obvodu připojen.

Uvažujme následující tvar chromozomu: (3,1,3) (2,3,3) (2,0,3) (4,6,2) (4,4,3) (5,6,2) (9,8,0) (9,0,3) (7,1,2) (11,7,5) (7,11,1) (11,12,3) (14,13,15). Tento chromozom kóduje dvouvstupový rozšířený komparátor v rekonfigurovatelném poli 4x3 elementů. Chromozomu odpovídá propojení elementů matice a přiřazení funkcí, které je zobrazeno na následujícím obrázku.

Dvouvstupový rozšířený komparátor
Obrázek 1.2: Dvouvstupový rozšířený komparátor

1.1.2. Fitness funkce

Výpočet fitness hodnoty pro konkrétní chromozom se provede tak, že se vyhodnotí funkčnost zapojení postupným předkládáním všech možných vstupních kombinací daných pravdivostní tabulkou. Fitness hodnota určitého kandidátního řešení v zásadě odpovídá buď počtu chybných (v případě minimalizace) nebo počtu správných (v případě maximalizace) odezev.

Výpočet fitness funkce
Obrázek 1.3: Výpočet fitness funkce

Počet vstupních kombinací závisí na řešené úloze. V případě návrhu kombinačních obvodů a úplné definice se jedná o 2^k vstupních vektorů, kde k je počet vstupů kombinačního obvodu. Pro každou vstupní kombinaci a dané propojení jednotlivých elementů se vypočítá hodnota na výstupu. Tzn. simuluje se funkce předloženého kombinačního obvodu a porovnává se výstupní kombinace z dané pravdivostní tabulky s odsimulovanou výstupní kombinací. Hodnota fitness pak odpovídá počtu shod s předem zadanými výstupními hodnotami pro všechny vstupní kombinace. Pokud máme např. k=4 vstupy a l=2 výstupy, pak počet vstupních kombinací je 2^k = 2^4 = 16. Maximální fitness hodnota tedy může být l 2^k = 2 16 = 32.

V praxi lze simulaci urychlit tím, že se počítá nikoliv v bitech, ale v 32 bitové aritmetice, čímž se vyhodnocování 32x urychlí a tím sníží řád složitosti o 2^5. Fitness funkce může zohledňovat i jiné důležité aspekty - např. počet použitých elementů, spotřebu, zpoždění, atd.

1.1.3. Evoluční algoritmus

Algoritmus kartézského genetické programování je založen na evoluční strategii (1+L)-ES. Označení + znamená, že populace, ze které se bude vybírat nejlepší jedinec je tvořena nejen L nově vzniklými mutanty ale i jejich rodičem. Pro CGP se stejně jako u ES využívá pouze operátor mutace, který však pracuje na jiném principu. Tento operátor je řízen parametrem udávajícím procentuální počet mutovaných genů (jeden gen odpovídá jedné celočíselné hodnotě chromozomu). Operátor je definován tak, že změní hodnotu náhodně zvoleného genu na jinou opět náhodně zvolenou hodnotu (Pozn: Je nutné vzít v úvahu, že ne všechny celočíselné hodnoty jsou v konkrétním genu přípustné).

  1. Vygenerování L+1 náhodných jedinců (chromozomů) pro inicializaci populace

  2. Ohodnocení všech jedinců populace pomocí fitness funkce

  3. Nalezení nejlépe ohodnoceného jedince (nejvyšší/nejnižší fitness)

  4. Vygenerování L potomků pomocí operátoru mutace aplikovaného na nejlepšího nalezeného jedince

  5. Nejlepší nalezený jedinec společně s jeho L potomky tvoří novou populaci

  6. Není-li splněna podmínka ukončení, pokračuje se krokem 2

2. Příklad: Evoluční návrh obvodu - 5b parita

Nástroj určený pro evoluční návrh kombinačních obvodů se skládá z následujících částí: programu pro specifikaci problému ve formě pravdivostní tabulky (tab2h_convertor), vlastního CGP (cgp) a grafického rozhraní, které umožňuje zobrazení výsledku evoluce (cgpview).

Pouľití nástroje budeme demonstrovat na evolučním návrhu obvodu, který doplňuje k 5b číslu jeden bit tak, aby byl ve výsledku sudý počet jedniček.

2.1. Vytvoření pravdivostní tabulky a .h souboru

  • K usnadnění zadávání pravdivostních tabulek byl vytvořen nástroj tab2h, který lze stáhnout zde. Archiv kromě nástroje obsahuje i pravidvostní tabulku pro paritu (parita5.txt).

    # doplni na sudou paritu-5b
    # 5 vstupu, 1 vystup
    00000 : 0
    00001 : 1
    00010 : 1
    00011 : 0
    00100 : 1
    00101 : 0
    00110 : 0
    ....

    Formát vstupního souboru:

    1) komentář je uvozen znakem #

    2) ignorují se prázdné řádky a space znaky

    3) formát řádku: vstupní kombinace bitů : výstupní kombinace bitů

    4) počet vstupů a výstupů se odvodí od prvního řádku s daty a musí být dále shodný

    Pokud soubor obsahuje méně, než 2^počet vstupů vstupních kombinací, jsou tyto kombinace považovány za neurčité stavy.

  • Pomocí tab2h parita5.txt > parita5.h vytvoříme hlavičkový soubor parita5.h, ve kterém bude zakódován problém, který řeąíme pomocí CGP.

    #define POPIS "# doplni na sudou paritu-5b  5 vstupu, 1 vystup \n"
    //Pocet vstupu a vystupu
    #define PARAM_IN 5        //pocet vstupu komb. obvodu
    #define PARAM_OUT 1       //pocet vystupu komb. obvodu
    //Inicializace dat. pole
    #define init_data(a) \
      a[0]=0xffff0000;\
      a[1]=0xff00ff00;\
      ...
      a[5]=0x96696996;
    //Pocet prvku pole
    #define DATASIZE 6
    

2.2. Nastavení parametrů evoluce a vlastní evoluce

  • V archivu cgp.zip naleznete nástroj pro evolučn návrh zaloľený na CGP. Implementaci CGP naleznete v souboru cgp.cpp. V případě, ľe chcete provádět návrh s jinou sadou operací, je nutné ve funkci fitness změnit poľadované operace.

  • Hlavičkové soubory s popisem experimentu jsou brány z adresáře data. Abychom mohli pouľít paritu, zkopírujte do tohoto adresáře vygenerovaný soubor parita5.h

  • V hlavičkovém souboru cgp.h lze měnit parametry CGP a evoluce. V tomto souboru se také provádí linkování na soubor parita5.h pomocí direktivy #include.

    #define PARAM_M 5            //pocet sloupcu
    #define PARAM_N 5            //pocet radku
    #define L_BACK 1             //1 (pouze predchozi sloupec)  .. param_m (maximalni mozny rozsah);
    
    #define FUNCTIONS 4          //max. pocet pouzitych funkci bloku, viz fitness()
    
    ...
    
    #include "data/parita5.h"
    
  • Pomocí příkazu make provedeme kompilaci zdrojových kódů.

  • Evoluci spustníme zadáním příkazu cgp, který ganeruje řadu reportů.

2.3. Zobrazení výsledku evoluce - soubory .chr

V případě úspěchu nástroj cgp vygeneruje soubor s příponou .chr, který obsahuje chromozom. Odpovídající obvod je možné prohlédnout v programu cgpviewer (viewer.zip). Spusťte cgpviewer.exe (pouze windows) a otevřete si vygenerovaný soubor. Činnost chromozomu je možné i odsimulovat. Je však nejdříve nutné zadat použité číslování funkcí v rámci programu cgp.

Zobrazení nalezeného řešení
Obrázek 2.1: Zobrazení nalezeného řešení

3. Download

Stažením archívu uživatel vyjadřuje souhlas s BSD licencí pod kterou je tento software poskytován.
By downloading the user expresses agreement with The BSD License under which the software is provided.

CGP download

cgp.zip - nástroj pro evoluční návrh kombinačních obvodů pomocí kartézského genetického programování.

Pomocné nástroje

tab2h_convertor.zip - nástroj pro převod pravdivostní tabulky na hlavičkový soubor pro CGP.

viewer.zip - nástroj pro zobrazení nalezeného kombinačního obvodu zakódovaného v chromozomu.