Prírodou inšpirované algoritmy

Primárne operácie modifikujúce štruktúru jedinca

(Koza, 1992) uvádza dva primárne operátory modifikujúce štruktúru jedinca :

• Reprodukcia, táto operácia je základným hnacím motorom Darwinovskej selekcie a prežitia najschopnejších. Reprodukcia je asexuálna, pracuje iba s jedným rodičovským jedincom a jej výsledkom je jeden potomok. Pozostáva z dvoch krokov :
1. V prvom kroku je z populácie vybraný jeden jedinec. Existuje viacero spôsobov výberu :
• Fitness proportionate selection, jedinec je vybraný na základe pomeru jeho vhodnosti ku vhodnosti všetkých jedincov populácie (na základe hodnoty Normalized fitness)
• Tournament selection, náhodne je z populácie vybraná množina jedincov, vhodnosť ktorých je porovnávaná. Jedinec s najväčšou hodnotou Adjusted fitness je napokon výsledkom selekcie.
• Random selection, náhodný výber jedného jedinca z populácie
2. V druhom kroku je vybraný jedinec bez zmeny skopírovaný do novej populácie
• Kríženie, sexuálna rekombinácia. Je zdrojom rôznorodosti v populácii. Kríženie pracuje s dvoma rodičovskými jedincami a jeho výsledkom sú dvaja potomkovia. Obaja rodičovskí jedinci sú vyberaní z populácie rovnakým druhom selekcie ako v Reprodukcii. Operácia začína náhodným výberom uzla stromu každého rodiča. Zvyčajne sa medziľahlé uzly stromu predstavujúce funkcie vyberajú s väčšou pravdepodobnosťou ako listové-terminálové uzly. Tak je zabezpečená výmena väčších funkčných blokov a tým aj vytvorenie odlišnejších potomkov. Nasledujúcim krokom je výmena podstromov, koreňmi ktorých sú náhodne vybrané body. Takto vzniknú dvaja noví jedinci, ktorí sú, v prípade, že hĺbka ich stromu nepresiahne maximálnu povolenú hodnotu, skopírovaní do novej populácie. Namiesto nevhodného potomka je do novej populácie skopírovaný jeho rodič. Kríženie spĺňa v GP rovnakú funkciu ako v konvenčných Genetických algoritmoch, lepšie však bojujú proti predčasnej konvergencii populácie. Ak by totiž boli obaja rodičia identický, v GA by z nich nemohli vzniknúť odlišní jedinci. V GP by naopak vznikli jedinci zhodní s rodičmi len v prípade, že boli v oboch vybrané rovnaké uzly ako korene vymieňaných podstromov. Príklad kríženia môžete vidieť na nasledujúcom obrázku

Príklad kríženia