Programarea genetică este o metodă automată inspirată de mecanismul de selecție naturală așa cum a fost stabilit de Charles Darwin pentru a explica adaptarea mai mult sau mai puțin optime organismelor la mediul lor. Scopul său este de a găsi, prin aproximări succesive, programe care îndeplinesc cel mai bine o sarcină dată.
Numim programarea genetică o tehnică care permite unui program de calculator să învețe, printr-un algoritm evolutiv, să optimizeze încetul cu încetul o populație de alte programe pentru a-și crește gradul de adaptare (fitness) pentru a îndeplini o sarcină solicitată de un utilizator.
Pentru a înțelege pe deplin de unde vine programarea genetică, vom identifica mai întâi câteva date importante pentru această cercetare:
• 1958 - Friedberg: mutație de instrucție aleatorie într-un program genetic
• 1963 - Samuel: Utilizarea termenului „învățare automată” în sensul programării automate.
• 1966 - Fogel, Owen & Walsh: Automate de stare finită pentru sarcini de predicție, obținute prin selectarea părinților eficienți cărora li se aplică mutații: „programare evolutivă”
• 1985 - Cramer: Utilizarea expresiei sub formă de copac. Trecere între sub-copaci.
• 1986 - Hicklin: Evoluția programelor de joc în LISP. Selecția părinților eficienți, combinații de sub-arbori comuni sau prezenți la unul dintre părinți și sub-arbori aleatori.
• 1989/1992 - Koza: sistematizarea și demonstrarea interesului acestei abordări pentru multe probleme. Definițiile unei paradigme standard în cartea „Programare genetică. Despre programarea computerelor prin selecție naturală ”[Koza, 1992]. Această paradigmă include mai multe concepte: programare structurată în expresii arborescente, definirea unei gramatici a limbajului, tip unic de returnare pentru fiecare funcție, definirea proporțiilor de mutație și încrucișare pentru fiecare generație etc.
Programarea genetică este costisitoare în ceea ce privește calculul mașinii, deoarece pune în paralel un număr mare de algoritmi vecini. În primii săi ani, în anii 1980, se rezuma, așadar, la rezolvarea unor probleme simple. Pe măsură ce puterea procesoarelor s-a înmulțit, programarea genetică a început să dea rezultate mai puternice: la sfârșitul anului 2004, de exemplu, au existat aproximativ 40 de rezultate semnificative în următoarele domenii:
Aceste rezultate includ, de asemenea, reinventarea sau inversarea multor invenții recente și producerea a două invenții brevetabile.
Până în anii 1990, programarea genetică a fost doar o euristică și nu o disciplină în sine. După unele progrese din anii 2000, s-a dezvoltat o teorie completă pe măsură ce tehnica a devenit mai răspândită. Chiar și până la punctul în care este posibil să se realizeze modele probabilistice exacte de programare genetică și algoritmi genetici .
Astăzi, pe lângă software, programarea genetică se aplică și evoluției hardware.
Programarea meta genetică este tehnica de a evolua un sistem de programare genetică folosind programarea genetică în sine.
Fazele programării genetice
Principiul programării genetice prezentat pentru a reprezenta programe care răspund la problema dată. Iată un algoritm sintetic pentru programarea genetică:
1. Generarea aleatorie a populației (1 individ = 1 program)
2. Evaluarea adecvării fiecărui individ în populație (evaluarea adecvării programelor la problema de rezolvat)
3. Aplicarea operatorilor de încrucișare, mutație, reproducere asupra populației pentru a crea o nouă populație (în contextul programării genetice, acest proces corespunde schimburilor de coduri „subtile” între două programe)
4. Selectarea persoanelor cele mai potrivite mediului lor (în contextul programării genetice, aceasta corespunde programelor care răspund cel mai bine problemei ridicate)
5. Repetați pașii 2, 3 și 4 de mai multe ori