Algoritmi Genetici — Laboratorul 2

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10

Cuprins

Metode:

Hill Climbing
Simulated Annealing

Temă:

Implementare: Hill Climbing şi Simulated Annealing pentru optimizare numerică

Hill-Climbing

begin
  t := 0
  initialize best
  repeat
    local := FALSE
    select a candidate solution (bitstring) v_c at random
    evaluate v_c
    repeat
      generate all (or some) of the Hamming neighbors of v_c
      select the v_n among these 
        with the best value of the function eval
      if eval(v_n) is better than eval(v_c)
        then v_c := v_n
        else local := TRUE
    until local
    t := t + 1
    if v_c is better than best
      then best := v_c
  until t = MAX
end

Reprezentare:

Spaţiul de căutare se va disctretiza până la o anumită precizie 10^-d. Un interval [a, b] va fi împărţit în N = (b-a)*10^d subintervale egale. Pentru a putea reprezenta cele (b-a)*10^d valori, este nevoie de un număr n = parte_intreaga_superioara(log₂(N)) de biţi. Lungimea şirului de biţi care reprezintă o soluţie candidat va fi suma lungimilor reprezentărilor pentru fiecare interval din domeniul de definiţie al funcţiei de optimizat.

Prin vecin Hamming al unui şir de biţi v se înţelege un şir de aceeaşi lungime, care diferă printr-un singur bit de v.

Simulated Annealing

begin
  t := 0
  initialize the temperature T
  select a current candidate solution (bitstring) v_c at random
  evaluate v_c
  repeat
    repeat
      select at random v_n - a Hamming neighbor of v_c
      if eval(v_n) is better than eval(v_c)
        then v_c := v_n
        else if random[0,1) < exp(-|eval(v_n)-eval(v_c)|/T)
          then v_c := v_n
    until (termination-condition)
    T := g(T; t) 
    t := t + 1
  until (halting-criterion)
end

Se va folosi acelaşi mod de reprezentare ca mai sus.

Funcţia g(T; t) de modificare a "temperaturii" T va asigura o scădere treptată a acesteia cu fiecare iteraţie (de exemplu, prin înmulţirea cu o valoare subunitară).

Exemple de condiţii de ieşire din bucle:

pentru bucla interioară (termination-condition): verificarea unui număr stabilit de vecini;
pentru bucla exterioară (halting-criterion): atingerea unei anumite temperaturi, atingerea unui număr de iteraţii.

Temă

Implementaţi cele două metode de mai sus pentru a găsi punctele de extrem ale funcţiilor propuse la laboratorul 1.

Ilustraţi prin grafice modul în care evoluează soluţiile. Pentru Hill Climbing, graficul trebuie să exprime valoarea functiei de optimizat în punctul reprezentat de v_c în cadrul buclei din fiecare iteraţie, respectiv în punctul reprezentat de best în funcţie de iteraţii. Pentru Simulated Annealing se vor trasa evoluţia valorii functiei de optimizat în punctul reprezentat de v_c şi modul de scădere a "temperaturii de călire".

Realizaţi un scurt raport (format text) care să precizeze, pentru fiecare dintre metode:

timpul minim, mediu şi maxim de execuţie
cea mai buna şi cea mai slaba soluţie, precum si media soluţiilor obţinute după un număr de rulări.