Semantically-Oriented Mutation Operator in Cartesian Genetic Programming for Evolutionary Circuit Design

• http://arxiv.org/abs/2004.11018

Cartesian genetic programming, semantic operator, semantic mutation, evolutionary circuit design

Navzdory mnoha úspěšným aplikacím trpí kartézské genetické programování (CGP) omezenou škálovatelností, zejména pokud se používá pro návrh evolučních obvodů. Například při návrhu násobičky představuje 5-bitová násobička nejsložitější obvod vyvinutý z náhodně vytvořené počáteční populace. Účinnost CGP do značné míry závisí na výkonu operátoru bodové mutace, což je čistě stochastický operátor. Tako přístup se rozchází oproti poslednímu vývoji v oblasti využívající genetické programování (GP), kde v poslední době dochází k integraci pokročilých informovaných přístupů, jako jsou sémantické operátory, které dovolují GP zefektivnit prohledávání stavového prostoru. V tomto článku navrhujeme sémanticky orientovaný mutační operátor (SOMO) vhodný pro evoluční návrh kombinačních obvodů. SOMO používá sémantiku k určení nejlepší hodnoty pro každý mutovaný gen. Ve srovnání s běžným CGP a jeho variantami, stejně jako s nedávnými verzemi sémantického GP, navrhovaná metoda konverguje u známých booleovským problémů podstatně rychleji, přičemž velikost fenotypu zůstává relativně malá. Úspěšně navržené instance prezentované v tomto článku zahrnují 10-bitovou paritu, 10 + 10-bitovou sčítačku a 5 × 5-bitovou násobičku. Nejsložitější obvody byly vyvinuty za méně než jednu hodinu s implementací s jedním vláknem běžící na jednom jádru CPU.