Laborator de inteligență artificială în evoluție a afilierii, Universitatea din Wyoming, Laramie, Wyoming, Statele Unite ale Americii

îmbunătățirea

Laborator de inteligență artificială în evoluție a afilierii, Universitatea din Wyoming, Laramie, Wyoming, Statele Unite ale Americii

Cifre

Abstract

Citare: Helms L, Clune J (2017) Îmbunătățirea hibridului: Cum se combină cel mai bine codarea indirectă și directă în algoritmi evolutivi. PLoS ONE 12 (3): e0174635. https://doi.org/10.1371/journal.pone.0174635

Editor: Yongtang Shi, Universitatea Nankai, CHINA

Primit: 19 iulie 2016; Admis: 12 martie 2017; Publicat: 23 martie 2017

Disponibilitatea datelor: Genomii campioni, datele de fitness și fișierele de configurare utilizate pentru a genera populațiile sunt disponibile din Dryad Digital Repository, doi: 10.5061/dryad.7c4g3.

Finanțarea: JC a fost susținut de un premiu CAREER al National Science Foundation (CAREER: 1453549) (http://www.nsf.gov/funding/pgm_summ.jsp?pims_id=503214). Finanțatorii nu au avut niciun rol în proiectarea studiului, colectarea și analiza datelor, decizia de publicare sau pregătirea manuscrisului.

Interese concurente: Autorii au declarat că nu există interese concurente.

Introducere

Algoritmii evolutivi (EA) caută automat un spațiu de soluții posibile pentru a returna soluții performante [1]. Acestea produc în mod obișnuit soluții noi și eficiente la multe probleme provocatoare și depășesc deseori inginerii umani [2-12]. Un domeniu important îl constituie rețelele neuronale artificiale (ANN) în evoluție, care sunt modele de calcul inspirate de capacitățile de procesare a informațiilor din creierele naturale [1]. ANN-urile sunt de obicei complicate de construit manual, dar sunt capabile să rezolve probleme de calcul dificile, inclusiv recunoașterea obiectelor și a simbolurilor pentru sarcini de viziune pe computer și controlul locomoției pentru roboți [13-15]. EA-urile pot optimiza greutățile și arhitectura ANN-urilor și au proiectat cu succes ANN-urile pentru o varietate de aplicații, inclusiv controlere de roboți [4, 6, 15-18] și recunoașterea modelelor [5, 19-21].

Principiul de proiectare al regularității este esențial pentru succesul EA în problemele obișnuite [22]. Regularitatea se referă la compresibilitatea informațiilor care descriu o structură și implică de obicei simetriile și repetarea temelor de proiectare, cu și fără variație [23, 24]. Multe organisme naturale prezintă regularitate prin simetrie stânga-dreapta și repetarea motivelor de proiectare rezultate din reutilizarea informațiilor genetice atunci când se produce un fenotip, ceea ce permite descrierea fenotipurilor complexe de către genomii compacti.

Problemele de inginerie conțin regularități în grade diferite. De exemplu, încercarea de a memora un flux de numere aleatorii este o problemă complet neregulată, în timp ce memorarea unei valori într-un flux de numere ieșite dintr-o funcție sinusoidală este regulată. Spre deosebire de exemplul obișnuit, numerele dintr-un flux aleatoriu nu au relații cu alte numere din flux de exploatat în soluție. Problemele din lumea reală nu sunt în întregime obișnuite, iar algoritmii eficienți trebuie să exploateze atât regularitățile, cât și să gestioneze neregulile pentru a se comporta bine [24]. Codificările indirecte au dificultăți în generarea de fenotipuri cu elemente neregulate, ceea ce afectează negativ performanța lor asupra problemelor neregulate. [24, 31].

Lucrările anterioare au arătat că performanța EA la problemele cu o anumită regularitate și o anumită neregulă poate fi îmbunătățită prin evoluția genomilor care combină codificări indirecte și directe, deoarece codificarea indirectă poate capta regularitățile, iar codificarea directă poate gestiona neregulile [24, 32]. Alte lucrări au introdus o codificare indirectă bazată pe celule numită urmărire epigenetică capabilă să se adapteze atât la probleme regulate, cât și la probleme neregulate, incluzând reguli de dezvoltare care pot viza celule individuale [33, 34]. În timp ce experimentele arată că urmărirea epigenetică poate rezolva nereguli și, în principiu, poate exploata regularitatea, nu a fost încă investigat experimental dacă funcționează mai bine decât o codificare directă a problemelor cu o anumită regularitate.

O modalitate de combinare a codificărilor indirecte și directe este algoritmul HybrID [24, 32], care evoluează genomuri codificate indirect până la un punct de comutare predefinit în care genomii sunt convertiți într-o codificare directă și au evoluat în continuare pentru a produce caracteristici neregulate. În timp ce HybrID poate rezolva în mod eficient probleme regulate și neregulate, un punct de comutare trebuie să fie predefinit de utilizator, ceea ce reprezintă un dezavantaj, deoarece punctul de comutare optim pentru diferite probleme nu este cunoscut din timp și necesită eforturi de calcul substanțiale pentru a determina empiric. De asemenea, genomii HybrID evoluați finali sunt codificați direct și, prin urmare, nu pot exploata noi regularități care pot apărea dacă mediul se schimbă sau soluțiile sunt transferate către o problemă diferită [28, 29]. Punctele tari și punctele slabe ale HybrID ridică problema cum să combinăm cel mai bine codurile indirecte și directe pentru a exploata pe deplin beneficiile fiecărei codificări, pe care le investigăm introducând două noi codificări HybrID care abordează limitările specifice ale metodei HybrID originale. Raportăm că aceste noi codificări sunt capabile să depășească HybrID-ul original pentru anumite clase de probleme și să arate cum pot fi utilizate pe deplin punctele forte ale fiecărei codificări.

HyperNEAT și HybrID

Toți algoritmii din această secțiune au fost descriși anterior în profunzime, așa că aici îi descriem doar pe scurt.

Rețele producătoare de modele compoziționale

Procesul natural de dezvoltare a organismelor biologice de la schema genetică la fenotip este un exemplu de codificare indirectă la scară masivă. Fiecare celulă dintr-un organism are același cod genetic și suferă un proces de diferențiere celulară pentru a produce diferite tipuri de celule cu funcții specializate. Diferențierea celulară are loc în funcție de gradienții chimici localizați care permit celulei să se localizeze în cadrul fenotipului. Genomul poate fi abstractizat ca o funcție complexă care ia ca intrare o locație și produce ca ieșire descrierea fenotipului în acea locație.

Rețelele compoziționale de producere a modelelor (CPPN) sunt o codificare indirectă care abstractizează procesele naturale de dezvoltare [35]. Un CPPN este o rețea de noduri care funcționează la fel ca o rețea neuronală, cu excepția faptului că în loc ca fiecare nod să fie același, CPPN-urile au un set mic de funcții de activare diferite (de exemplu, sine, Gaussian). Funcțiile geometrice complexe pot fi codate în CPPN prin compoziția acestor funcții, care este definită de conectivitatea și greutățile rețelei.

Pentru a genera un fenotip, locația geometrică a fiecărui element fenotipic este introdusă iterativ în CPPN, care generează proprietățile acelui element. Proiectul Picbreeder [36], care dezvoltă imagini bidimensionale, este un exemplu al modului în care un CPPN poate codifica fenotipuri (Fig. 1). Pentru a genera un fenotip Picbreeder din genom, coordonatele x și y ale unui pixel din imagine sunt introduse în CPPN, care produce o valoare a culorii. Procesul se repetă pentru toți pixelii din imagine, producând fenotipul complet. CPPN-urile sunt apoi dezvoltate pentru a produce imagini noi și interesante.