Prírodou inšpirované algoritmy

Symbolická regresia

Pri symbolickej regresii je našim cieľom objaviť funkciu, ktorá by popísala vzťahy medzi konečnou skupinou dátových bodov. Ide teda o identifikáciu funkcií, v našom prípade pomocou odchýlkou riadenej evolúcie. Hľadaná funkcia často obsahuje i numerické konštanty, ktoré nezvyknú byť zahrnuté v množine terminálov použitej pri vytváraní stromových štruktúr. Vo väčšine prípadov totiž nemáme explicitnú znalosť o ich hodnote a prítomnosti v hľadanej funkcii. Genetické programovanie má však schopnosť vytvárať viaceré konštanty samé od seba. Napríklad konštanta 1.0 môže byť vytvorená výrazom (/ X X) alebo (cos (- X X)). Pri výbere primitívnych matematických funkcií je nutné ošetriť ich prípadné neakceptovateľné vstupy aby sme zachovali uzavretosť množín funkcií a terminálov (napr. ošetrenie vstupu 0 ako deliteľa vo funkcii /).

Znovuobjavenie Tretieho Keplerovho zákona

Keplerov Tretí zákon pohybu planét popisuje vzťah vzdialenosti planét od Slnka a rýchlosti ich obehu. Podľa neho pomer tretej mocniny vzdialenosti planéty od Slnka a kvadrátu periódy jej obehu je konštantný :
D^3 / p^2 = c

Vo svojej knihe popísal (Koza, 1992) nasledovné riešenie tohto problému pomocou GP :
Hľadanou funkciou je závislosť rýchlosti obehu p od vzdialenosti D planéty od Slnka. Množina terminálov sa skladá iba z jednej premennej : vzdialenosti D. Množina primitívnych funkcií obsahuje základné matematické funkcie : +,-,*,% (funkcia / ošetrená nasledovne: ak je menovateľom 0 funkcia vráti 1), srt (funkcia sqrt ošetrená nasledovne : srt(X) = sqrt(abs(X))), sin, cos. Vhodnosťou "raw fitness" jedinca - matematického výrazu je súčet absolútnych hodnôt odchýlok periódy vyprodukovanej daným jedincom a periódy získanej pozorovaním, cez deväť planét slnečnej sústavy : Merkúr, Venušu, Zem, Mars, Jupiter, Saturn, Urán, Neptún a Pluto. Hodnoty vzdialenosti a periódy získané pozorovaním sú normalizované periódou a vzdialenosťou Zeme. Vhodnosťou "adjusted fitness" jedinca je prevrátená hodnota "raw fitness" + 1, čo zabezpečí, že hodnoty vhodnosti jedincov budú ležať v intervale <0,1>, pričom vhodnosť najlepšieho jedinca bude najväčšia (na rozdiel od raw fitness). Jedinec je taktiež ohodnotený počtom zásahov -hits počtom prípadov, v ktorých sa ním vyprodukovaná hodnota periódy tej ktorej planéty nelíšila od hodnoty získanej pozorovaním o viac ako 10%.
V priebehu genetického programovania sú použité štandardné operátory :

• half-and-half metóda počiatočnej inicializácie populácie
• reprodukcia s fitness proportionate selection, v ktorej je kritériom výberu jedinca jeho normalizovaná vhodnosť - pomer adjusted fitness jedinca a sumy všetkých adjusted fitnesses celej populácie
• kríženie s fitness proportionate selection oboch rodičov a štandardnými pravdepodobnosťami

Riadiace parametre použité pri tomto experimente

1. Veľkosť populácie M=500
2. Maximálny počet generácií G=51 (generácie 0 až 50)
3. Pravdepodobnosť kríženia Pc = 0.9
4. Pravdepodobnosť reprodukcie Pr = 0.1
5. Pri výbere bodu prekríženia pri krížení pravdepodobnosť výberu vnútorného bodu 90% a pravdepodobnosť výberu vonkajšieho bodu 10%
6. Maximálna hĺbka vytváraných jedincov Dcreated = 17
7. Maximálna hĺbka iniciovaných jedincov Dinitial = 6
8. Mutácia, permutácia, editácia a decimácia nepoužité

Ukončenie behu algoritmu nastane v prípade, že prebehlo 51 cyklov - generácií, alebo v prípade, že bol nájdený jedinec, ktorý dosiahol deväť zásahov. Ako riešenie je priebežne ukladaný jedinec, ktorý dosiahol najvyššie ohodnotenie fitness. Pri viacerých behoch algoritmu bolo korektné riešenie (* (srt D) D) objavené už v ranných generáciách. Okrem neho sa objavili i zložitejšie, ale tiež prípustné riešenia tvarov : (* (srt (* D D)) (srt D)), (/ (* D D) (srt D)), či (+ (- D D) (* (srt D) D)). Za zmienku stojí i fakt, že ako priebežne najlepšie riešenie bola v počiatočných objavená i matematická formula (* D D), ktorú Kepler publikoval v roku 1608, 10 rokov pred objavom vzťahu (srt (* D (* D D))), ako (čiastočne prijateľné) riešenie.

Pri zopakovaní tohto experimetu (s jedinou úpravou - počet planét, vzdialenosti ktorých boli použité ako jednotlivé fitness-cases, bol znížený na šesť : Venušu, Zem, Mars, Jupiter, Saturn, Urán) boli dosiahnuté rovnaké výsledky ako tie, ktoré (Koza, 1992).
Zdrojové súbory s lisp-ovskými programami riešiacimi túto úlohu pri použití vzdialenosti šiestich planét.