14/07/2022
Algoritmii Genetici (AG) sunt metode de optimizare puternice, inspirate de procesul fascinant al selecției naturale. Asemenea naturii, unde doar cei mai puternici și mai adaptați supraviețuiesc și își transmit trăsăturile, AG-urile simulează acest principiu pentru a găsi soluții optime la probleme complexe. Un component crucial al acestor algoritmi este procesul de selecție, faza în care se decide care indivizi din populația curentă vor avea șansa de a contribui la crearea generației următoare. Această decizie nu este arbitrară; ea se bazează pe "fitness-ul" fiecărui individ, o măsură a cât de bine se potrivește o soluție dată cu problema pe care încercăm să o rezolvăm. Practic, scopul este să favorizăm acele soluții care performează cel mai bine în domeniul problemei specifice, imitând principiul supraviețuirii celor mai apți.
Într-un context de Algoritmi Genetici, o populație "foarte aptă" este o populație în care majoritatea indivizilor au scoruri de fitness ridicate. Acest lucru indică faptul că algoritmul progresează eficient către găsirea unor soluții optime sau aproape optime. O populație cu fitness ridicat sugerează o convergență bună, dar este esențial să se mențină un echilibru între exploatarea celor mai buni indivizi și explorarea spațiului de căutare pentru a evita convergența prematură către un optim local. Metodele de selecție sunt mecanismele prin care se asigură că indivizii cu fitness superior au o probabilitate mai mare de a fi selectați ca "părinți" pentru următoarea generație, perpetuând astfel trăsăturile favorabile.
Selecția Turneu: O Metodă Robustă și Simplă
Selecția Turneu este una dintre cele mai populare și utilizate metode de selecție în Algoritmii Genetici, recunoscută pentru simplitatea sa și controlul eficient asupra presiunii de selecție. Este o abordare intuitivă: se organizează "turnee" între un subset de indivizi din populație, iar "câștigătorul" (cel mai apt) este ales pentru a fi un părinte. Acest proces se repetă până când se obține numărul dorit de părinți pentru reproducere.
Conceptul de Bază
Principiul este simplu: se selectează aleatoriu un anumit număr de indivizi din populația generală. Dintre acești indivizi, cel cu cel mai mare scor de fitness este ales și adăugat la "pool-ul" de părinți. Această procedură este repetată până când se adună un număr suficient de indivizi pentru a forma noua generație. Flexibilitatea acestei metode rezidă în capacitatea de a ajusta dimensiunea turneului, ceea ce influențează direct gradul de presiune de selecție.
Algoritmul de Selecție Turneu
Să analizăm pașii implicați în algoritmul de Selecție Turneu:
- Specifică dimensiunea turneului (k): Acesta este numărul de indivizi care vor concura în fiecare turneu.
- Specifică numărul total de indivizi de selectat (n): Acesta este numărul de părinți pe care dorim să-i obținem pentru următoarea generație.
- Alege aleatoriu un subset de indivizi: Din populația existentă, se selectează la întâmplare k indivizi, fiecare având o șansă egală de a fi ales. Selecția poate fi făcută cu sau fără înlocuire.
- Evaluează fitness-ul: Se calculează sau se verifică scorul de fitness pentru fiecare individ din subsetul selectat.
- Selectează individul cu cel mai mare fitness: Dintre cei k indivizi, cel cu cel mai bun scor de fitness este declarat "câștigător" și este adăugat la lista părinților.
- Repetă procesul: Pașii 3-5 se repetă până când numărul dorit de indivizi (n) a fost selectat.
Pseudocod pentru Selecția Turneu
Pentru a înțelege mai bine, să examinăm pseudocodul pentru un singur turneu și apoi pentru procesul complet de selecție:
Algoritmul Turneu(T, k) - Selectează cel mai apt dintr-o listă dată:
/* Selectează individul (sau cromozomul) cel mai apt dintr-o listă de indivizi T selectați aleatoriu */ algoritm Turneu(T, k): // INTRARE // T = o listă de indivizi selectați aleatoriu dintr-o populație. // k = dimensiunea turneului, adică numărul de elemente din T. // IEȘIRE // individul cel mai apt. CelMaiBun <- T[1]; // Presupunem că primul este cel mai bun inițial pentru i de la 2 la k do Urmatorul <- T[i]; dacă Fitness(Urmatorul) > Fitness(CelMaiBun) atunci CelMaiBun <- Urmatorul; return CelMaiBun;
Acest algoritm începe prin a considera primul individ din lista selectată aleatoriu (T) ca fiind cel mai bun. Apoi, iterează prin restul listei, comparând fitness-ul individului curent cu cel al "CelMaiBun"-ului de până acum. Dacă individul curent are un fitness mai mare, devine noul "CelMaiBun". La finalul iterației, "CelMaiBun" va fi individul cu cel mai mare scor de fitness din turneul respectiv.
Algoritmul SelectieTurneu(P, k, n) - Procesul complet de selecție:
/* Presupunem că dorim să selectăm n indivizi din populația P */ algoritm SelectieTurneu(P, k, n): // INTRARE // P = populația. // k = dimensiunea turneului, astfel încât 1 ≤ k ≤ numărul de indivizi din P. // n = numărul total de indivizi pe care dorim să-i selectăm. // IEȘIRE // pool-ul de indivizi selectați în turnee. T <- o secvență goală; // Pentru stocarea indivizilor din turneul curent B <- o secvență goală; // Pentru stocarea "câștigătorilor" turneelor pentru i de la 1 la n do Alege k indivizi din P la întâmplare, cu sau fără înlocuire, și adaugă-i în T; B[i] <- Turneu(T, k); // Apelează algoritmul de turneu pentru a găsi cel mai bun T <- [ ]; // Golește lista T pentru următorul turneu return B;
Acest algoritm principal `SelectieTurneu` repetă procesul de selecție a unui câștigător de `n` ori. La fiecare pas, el selectează aleatoriu `k` indivizi din populația totală `P`, îi trimite funcției `Turneu` pentru a identifica cel mai apt, iar individul rezultat este adăugat în lista `B` (lista părinților selectați). Lista temporară `T` este golită după fiecare turneu pentru a pregăti următorul. La final, lista `B` va conține cei `n` indivizi care vor servi ca părinți pentru următoarea generație.
Exemplu Ilustrativ
Să luăm un exemplu pentru a clarifica. Imaginați-vă o populație de 13 indivizi, fiecare reprezentat printr-un cromozom (o literă). Să spunem că setăm dimensiunea turneului, `k`, la 3. Algoritmul va alege aleatoriu 3 cromozomi din populație, de exemplu A, L și E. Apoi, va compara fitness-ul acestor trei. Dacă A are cel mai mare scor de fitness dintre A, L și E, atunci A este selectat ca părinte. Acest proces se repetă de mai multe ori până când se adună numărul necesar de părinți pentru a forma noua generație. Simplitatea și eficacitatea sa îl fac o alegere populară.
Analiza Selecției Turneu
Complexitatea Algoritmului
În fiecare turneu, este necesar să se compare scorurile de fitness ale tuturor celor k indivizi. Deoarece se rulează n turnee pentru a obține numărul total de indivizi, complexitatea algoritmului de Selecție Turneu este de ordinul O(n * k). Această complexitate liniară îl face eficient pentru majoritatea aplicațiilor.
Efectele Dimensiunii Turneului (k)
Dimensiunea turneului, k, nu influențează doar timpul de execuție, ci are și un impact major asupra presiunii de selecție. O valoare mai mare a lui k înseamnă că în fiecare turneu concurează mai mulți indivizi. Acest lucru crește probabilitatea ca lista de câștigători (B) să conțină membri cu fitness peste medie, deoarece este mai puțin probabil ca toți cei k indivizi aleși aleatoriu să fie slabi. Pe măsură ce k crește, probabilitatea de a selecta un membru cu fitness ridicat crește, iar probabilitatea de a selecta un membru cu fitness scăzut scade. Prin urmare, o valoare mai mare a lui k duce la o presiune de selecție mai mare, favorizând mai puternic indivizii superiori și accelerând convergența.
Selecția pe Bază de Rang (Linear Ranking Selection): O Abordare Proporțională
Selecția pe bază de rang, adesea numită și "Selecția de Rang" sau "Linear Ranking Selection", este o altă metodă populară de selecție care abordează o problemă potențială a metodelor de selecție bazate exclusiv pe fitness-ul absolut: indivizii cu fitness extrem de ridicat pot domina rapid întreaga populație, reducând diversitatea și riscând convergența prematură. Selecția pe bază de rang rezolvă această problemă prin utilizarea rangului relativ al unui individ în locul valorii sale absolute de fitness. Schema de selecție proporțională se bazează pe rangul atribuit fiecărui individ.
Conceptul și Calculul Probabilităților
În această metodă, indivizii sunt mai întâi sortați în funcție de scorurile lor de fitness, iar apoi li se atribuie un rang. Cel mai puțin apt individ primește rangul 1, al doilea cel mai puțin apt primește rangul 2, și așa mai departe. Important este că doi sau mai mulți indivizi cu aceleași valori de fitness ar trebui să aibă același rang. Odată ce rangurile sunt atribuite, probabilitatea de selecție a fiecărui individ este calculată pe baza rangului său, nu a fitness-ului său brut.
Să luăm un exemplu concret pentru a înțelege cum se calculează aceste probabilități. Presupunem că avem următoarele valori de fitness pentru câțiva indivizi dintr-o populație: 10, 9, 3, 15, 85, 7.
Pasul 1: Sortarea și Atribuirea Rangurilor
Sortăm valorile de fitness în ordine crescătoare și atribuim ranguri, începând cu 1 pentru cel mai mic fitness:
| Valoare Fitness | Rang (în ordine crescătoare a fitness-ului) |
|---|---|
| 3 | 1 |
| 7 | 2 |
| 9 | 3 |
| 10 | 4 |
| 15 | 5 |
| 85 | 6 |
Pasul 2: Calculul Suma Rangurilor
Suma tuturor rangurilor este esențială pentru calcularea probabilităților. Pentru o populație de N indivizi, suma rangurilor poate fi calculată folosind formula lui Gauss pentru suma primelor N numere naturale: Suma = N * (N + 1) / 2.
În exemplul nostru, avem N = 6 indivizi. Deci, suma rangurilor este:
Suma = 1 + 2 + 3 + 4 + 5 + 6 = 21
Sau folosind formula: (6 * (6 + 1)) / 2 = (6 * 7) / 2 = 42 / 2 = 21.
if Fitness(Next) > Fitness(Best) then Best <- Next; return Best; According to the algorithm above, we initially need to select the first individual in the list as the best one (the most fit). Then, we need to compare the fitness of the currently selected individual with the fitness of the next one in the list.[/caption]
Pasul 3: Calculul Probabilităților de Selecție
Probabilitatea de selecție pentru fiecare individ este pur și simplu rangul său împărțit la suma totală a rangurilor. Astfel, obținem următoarele probabilități:
| Fitness | Rang | Probabilitate de Selecție (Rang / Suma Totală a Rangurilor) |
|---|---|---|
| 3 | 1 | 1/21 |
| 7 | 2 | 2/21 |
| 9 | 3 | 3/21 |
| 10 | 4 | 4/21 |
| 15 | 5 | 5/21 |
| 85 | 6 | 6/21 |
Aceste probabilități pot fi apoi exprimate ca procente. Deși acest calcul este adesea folosit pentru a oferi o intuiție mai bună despre modul în care funcționează Selecția pe Bază de Rang, implementările reale ale algoritmilor genetici pot folosi variante sau optimizări ale acestei metode.
Întrebări Frecvente (FAQ)
Pentru a clarifica și mai mult conceptele, iată câteva întrebări frecvente legate de metodele de selecție în algoritmii genetici:
Ce este presiunea de selecție în Algoritmii Genetici?
Presiunea de selecție se referă la măsura în care indivizii cu fitness superior sunt favorizați în procesul de selecție. O presiune de selecție ridicată înseamnă că doar cei mai buni indivizi au o șansă semnificativă de a se reproduce, ceea ce poate accelera convergerea algoritmului, dar riscă să ducă la pierderea diversității genetice și la blocarea într-un optim local. O presiune de selecție scăzută menține diversitatea, dar poate încetini procesul de convergență. În Selecția Turneu, dimensiunea turneului (k) este un mijloc direct de control al presiunii de selecție.
De ce sunt metodele de selecție atât de importante în Algoritmii Genetici?
Metodele de selecție sunt fundamentale deoarece ele direcționează evoluția populației către soluții mai bune. Fără o selecție eficientă, algoritmul ar rătăci la întâmplare, fără a progresa către găsirea unor soluții optime. Ele asigură că trăsăturile pozitive sunt transmise generațiilor viitoare, ghidând algoritmul spre convergență, în timp ce mențin un echilibru necesar între exploatarea soluțiilor existente și explorarea unor noi părți ale spațiului de căutare.
Pot avea doi indivizi același rang în selecția pe bază de rang?
Da, absolut. Dacă doi sau mai mulți indivizi au exact aceeași valoare de fitness, ei ar trebui să primească același rang. Ordinea lor relativă în listă după sortare nu contează, atâta timp cât rangul atribuit reflectă corect poziția lor relativă în comparație cu ceilalți indivizi.
Care metodă de selecție este "cea mai bună"?
Nu există o singură metodă de selecție "cea mai bună" universal valabilă. Alegerea depinde de specificul problemei, de dimensiunea populației, de distribuția fitness-ului și de obiectivele algoritmului (de exemplu, viteză de convergență versus menținerea diversității). Selecția Turneu este adesea preferată datorită robusteții, simplității și controlului direct asupra presiunii de selecție, în timp ce Selecția pe Bază de Rang este utilă pentru a preveni dominarea rapidă a super-indivizilor și pentru a menține o diversitate genetică mai bună pe parcursul evoluției.
Concluzie
În acest articol, am explorat în detaliu două dintre cele mai importante metode de selecție utilizate în Algoritmii Genetici: Selecția Turneu și Selecția pe Bază de Rang. Am învățat că selecția este o fază critică, determinând care indivizi vor contribui la crearea următoarei generații, simulând principiul supraviețuirii celor mai apți. Selecția Turneu se remarcă prin simplitatea sa și capacitatea de a controla presiunea de selecție prin ajustarea dimensiunii turneului (k), în timp ce Selecția pe Bază de Rang oferă o abordare proporțională bazată pe rangurile relative ale indivizilor, ajutând la menținerea diversității. Înțelegerea profundă a acestor mecanisme este esențială pentru oricine dorește să optimizeze și să implementeze eficient Algoritmi Genetici pentru rezolvarea problemelor din lumea reală.
Dacă vrei să descoperi și alte articole similare cu Selecția în Algoritmii Genetici: Ghid Complet, poți vizita categoria Fitness.