Detail publikace

Semantically-oriented mutation operator in cartesian genetic programming for evolutionary circuit design

HODAŇ David, MRÁZEK Vojtěch a VAŠÍČEK Zdeněk. Semantically-oriented mutation operator in cartesian genetic programming for evolutionary circuit design. Genetic Programming and Evolvable Machines, roč. 22, č. 4, 2021, s. 539-572. ISSN 1389-2576. Dostupné z: https://link.springer.com/article/10.1007%2Fs10710-021-09416-6
Název česky
Sémanticky orientovaný mutační operátor pro evoluční návrh obvodů s využitím kartézského genetického programování
Typ
článek v časopise
Jazyk
angličtina
Autoři
Hodaň David, Ing. (UPSY FIT VUT)
Mrázek Vojtěch, Ing., Ph.D. (UPSY FIT VUT)
Vašíček Zdeněk, doc. Ing., Ph.D. (UPSY FIT VUT)
URL
Klíčová slova

kartézské genetické programování, sémantický genetický operátor, sémantická mutace, evoluční návrh obvodů

Abstrakt

Kartézské genetické programování (CGP) představuje jednu z velmi efektivních metod evolučního návrhu číslicových obvodů. Navzdory mnoha úspěšným aplikacím CGP v této oblasti však tato metoda trpí omezenou škálovatelností, zejména pokud jde o evoluční návrh obvodů z náhodně inicializované populace. Uvážíme-li například problém návrhu násobičky, představuje 5×5bitová násobička nejsložitější obvod navržený evolucí. Účinnost CGP velmi závisí na výkonnosti operátoru bodové mutace, který je však v běžném CGP ryze stochastický. To je v kontrastu s trendem v oblasti využití genetického programování (GP), kde byly v poslední době integrovány různé sémanticky orientované operátoru vylepšující účinnost algoritmu, tj. schopnost GP procházet efektivně vyhledávací prostor. V tomto článku navrhujeme sémanticky orientovaný mutační operátor (SOMOk) vhodný pro evoluční návrh kombinačních obvodů pomocí CGP. Na rozdíl od standardní bodové mutace modifikující hodnoty mutovaných genů náhodně, navrhovaný operátor využívá sémantiku k určení nejlepší hodnoty pro každý mutovaný gen. Ve srovnání s běžným CGP a jeho variantami konverguje navrhovaná metoda na běžných booleovských benchmarcích podstatně rychleji při zachování relativně malé velikosti fenotypu. Pomocí přístupu se podařilo nalézt např. 10-bitovou paritu, 10 + 10 bitovou sčítačku a 5×5 bitovou násobičku. Nejsložitější obvody byly nalezeny za méně než jednu hodinu a to s jednovláknovou implementací běžící na běžném procesoru.

Rok
2021
Strany
539-572
Časopis
Genetic Programming and Evolvable Machines, roč. 22, č. 4, ISSN 1389-2576
Vydavatel
Springer International Publishing
DOI
10.1007/s10710-021-09416-6
UT WoS
000702806100001
EID Scopus
2-s2.0-85116194943
BibTeX 
@ARTICLE{FITPUB12569,
   author = "David Hoda\v{n} and Vojt\v{e}ch Mr\'{a}zek and Zden\v{e}k Va\v{s}\'{i}\v{c}ek",
   title = "Semantically-oriented mutation operator in cartesian genetic programming for evolutionary circuit design",
   pages = "539--572",
   journal = "Genetic Programming and Evolvable Machines",
   volume = 22,
   number = 4,
   year = 2021,
   ISSN = "1389-2576",
   doi = "10.1007/s10710-021-09416-6",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/12569"
}
Nahoru