Algoritmi Genetici

Algoritmi Genetici

Metoda este inspurată din teoria evoluţionistă a lui Darwin. Lucrează cu o populaţie de soluţii candidat, care evoluează şi se adaptează unui mediu (în cazul de faţă, mediul este funcţia de optimizat). Genotipul suferă modificări:

• în urma mutaţiei (modificarea unei gene din codificarea unui individ)
• în urma recombinării codului genetic a doi indivizi)

După principiul evoluţionist survival of the fittest, de la o generaţie la alta se va favoriza supravieţuirea celor mai buni (bine adaptaţi) indivizi.

Terminologie

• individ (cromozom) = soluţie candidat, codificată ca la laboratorul 2
• cromozomii sunt compuşi din gene (trăsături)
• fiecare genă se găseşte în cromozom la o poziţie (locus / loci)
• diferitele valori pe care le poate lua o gena se numesc allele

Pseudocod

begin
  t :=  0
  initialize the population P(t)
  evaluate P(t)
  while (not termination-condition) do
  begin
    t :=  t + 1
    select P(t) from P(t -1)
    alter P(t)
    evaluate P(t)
  end
end

Componente

Trebuie definite:

• reprezentarea solutiilor problemei
• o metoda de a genera populatia initiala
• metoda de selectie
• functia de evaluare
• operatorii genetici
• valorile parametrilor algoritmului genetic (dimensiunea populatiei, probabilitatile de aplicare a operatorilor, etc.)
• criteriul de oprire

Funcţia fitness

Măsoară cât de bine adaptat (fit) la mediu este un individ. Aceasta se bazează pe funcţia de optimizat. Trebuie să fie pozitivă şi cu atât mai mare cu cât individul este mai bun (motiv: vezi procedura de selecţie).

Indicii pentru obţinerea unei funcţii fitness cu proprietăţile precizate, pe baza unei funcţii de test oarecare:

• o problemă de minimizare a unei funcţii f(x) este echivalentă cu problema de maximizare a funcţiei -f(x) sau a funcţiei 1/f(x)
• o funcţie f(x) care are şi valori negative poate fi "translată" cu o constantă C, astfel încât f(x)+C sa fie mereu pozitiv (trebuie ca: C >= abs(min(f(x))))

Iniţializarea populaţiei

Se generează un număr pop_size de soluţii candidat, reprezentate ca la laboratorul 2. Generarea poate fi aleatoare, sau poate folosi o altă metodă (de exemplu Hill Climbing) pentru asigurarea unei calităţi mai ridicate a candidaţilor iniţiali.

Evaluarea populaţiei

Fiecare soluţie candidat este decodificată şi se va calcula pentru ea funcţia fitness (care poate fi diferită de funcţia obiectiv!)

Selecţia noii generaţii din cea anterioară

Selecţia se face în funcţie de fitness, favorizându-se supravieţuirea celor mai buni indivizi. Exemple de selecţie:

• Roata norocului

  Indivizii sunt selectaţi în noua populaţie cu o probabilitate proporţională cu fitness-ul.

  Prepare the "fortune wheel":
  for (i := 0; i < pop_size; i++)
    compute the fitness of the individual  vi 
  compute the total fitness of the population:
  F := sum(fitness(vi))
  for (i := 0; i < pop_size; i++)
    compute the probability of selecting the individual vi:
    pi = fitness(vi)/F
    compute the cumulative probability:
    qi+1 = sum(pj), 0 <= j <= i 
  q0 := 0
  
  The actual selection:
  for (i := 0; i < pop_size; i++)
    fortune := random(0,1)
    select the vj for which qj <= fortune < qj+1
    new_population[i] := vj
  

  Unii indivizi pot avea mai multe copii în noua populaţie, alţii pot avea 0.
• Turneu

  Indivizii "se luptă" în grupuri de câte m, alese aleator. Cei mai buni n din fiecare grup sunt selectaţi.

• Bazată pe ierarhie

  Este asemănătoare selecţiei de tip roata norocului, cu diferenţa că probabilitatea de selecţie nu este proporţională cu fitness-ul, ci depinde de poziţia individului în lista ordonată a indivizilor din populaţie. Această variantă reduce şansa ca indivizii slabi să fie "sufocaţi" de cei cu fitness foarte mare.

Alterarea indivizilor

Se face prin intermediul operatorilor genetici, de încrucişare şi mutaţie.

• Încrucişarea

  Combină trăsăturile a doi cromozomi părinţi, rezultând urmaşi care moştenesc parţial aceste trăsături. Afectează cromozomii cu o probabilitate pc. Numărul de indivizi care participă la încrucişări într-o generaţie este estimat de pc * pop_size.

  Selectarea indivizilor care vor suferi incrucisare:

  for each individual vi
    if (rand(0,1) < pc)
      select vi for crossover
  

  Variante:

  • Încrucişarea cu un punct de tăiere, ales aleator. Exemplu:

    01 001011    _\    01 111100
    10 111100     /    10 001011
    

  • Încrucişarea cu n puncte de tăiere, generate aleator. Exemplu (n=3):

    01 0 010 11    _\    01 1 010 00
    10 1 111 00     /    10 0 111 11
    

  • Încrucişare uniformă: pentru fiecare locus, se selectează probabilist gena unuia dintre părinţi.
• Mutaţia

  Alterează una sau mai multe gene alese arbitrar dintr-un cromozom. Probabilitatea de mutaţie este dată de parametrul pm. Numărul de gene care suferă mutaţie este estimat de pm * chromosome_length * pop_size. Aplicarea mutaţiei:

  for each individual vi
    for each locus l
      if (rand(0,1) < pm)
        mutate gene vi[l] 
  

  Dacă se foloseşte reprezentarea ca şir de biţi, mutaţia constă în schimbarea valorii bitului respectiv din 0 în 1 sau invers.

  Exemplu:

  00100100
  00100000
  

Parametrii "standard"

pop_size = 50 indivizi

probabilitatea de mutaţie pm = 0.01

probabilitatea de încrucişare pc = 0.25

Criterii de oprire

atingerea unui număr TMAX de iteraţii

nici o îmbunătăţire a soluţiei în ultimele TW (sau TW(t)) iteraţii

...

Temă