Prírodou inšpirované algoritmy

Reprezentácia jedincov

Pretože na jedincov populácie (riešenia problému) chceme uplatňovať genetické operátory, potrebujeme ich mať reprezentované v nejakej vhodnej podobe. V praxi sa pritom veľmi často používajú reťazce. Kódovanie reťazcami má tiež svoju analógiu v genetike, kde v podstate reťazce odpovedajú chromozómom, jednotlivé pozície v reťazci jednotlivým génom a konkrétne hodnoty na týchto pozíciách potom alelám. Takáto reprezentácia (kód) predstavuje genotyp jedinca a jeho interpretácia v rámci riešeného problému, výsledok interakcie všetkých génov sa nazýva fenotyp.

Každému jedincovi je okrem toho priradené konkrétne číslo predstavujúce jeho vhodnosť (ohodnotenie). Pre riešený problém je vždy potrebné špeciálne definovať funkciu vhodnosti, ktorá dekóduje genotyp jedinca a vyhodnotí kvalitu riešenia (fenotyp) daného problému.

Vo všeobecnosti možno reprezentácie rozdeliť na niekoľko typov:

• podľa dĺžky reťazca na reprezentácie:
• s pevnou dĺžkou
• s premenlivou dĺžkou

• resp. podľa toho, či zložky riešenia majú pevné miesto v reťazci, na reprezentácie:
• s pevným poradím
• s premenlivým poradím

• podľa toho, aké hodnoty môžu jednotlivé gény nadobúdať:
• binárny reťazec, v praxi pre GA najpoužívanejší (možné hodnoty génov sú 0,1)
• viacznaková reprezentácia (možné hodnoty génov predstavuje abeceda s konečným počtom znakov)
• reálne kódovanie (možné hodnoty génov sú reálne čísla)
• štruktúry (napr. matica)
• stromová reprezentácia (najmä pre genetické programovanie)

Voľba reprezentácie je jedným z kľúčových problémov návrhu GA. Ovplyvňuje napr. ktoré genetické operátory možno použiť pri zvolenej reprezentácii, resp. potrebu nadefinovania si vlastných operátorov. Ďalším ťažiskovým problémom je definovanie funkcie vhodnosti, ktorá by jednak nemala mať príliš veľa lokálnych extrémov a jednak globálny extrém by nemal byť veľmi izolovaný. Body nachádzajúce sa v priestore riešení blízko seba by mali mať aj blízke hodnoty vhodností.