Genetica - algoritmul CAL - TM
Funcția obiectiv (funcția de fitness, funcția de fitness)
Unele mod aleatoriu, în general, creează o multitudine de genotipuri ale populației inițiale. Acestea sunt evaluate folosind o „funcție de fitness“, astfel încât fiecare genotip este asociat cu o anumită valoare ( „fitness“), care determină cât de bine fenotipul, au descris, rezolvă problema.
Schema algoritmului genetic
Problema este formalizată în așa fel încât soluția poate fi codificată ca un vector ( „genotip“) gene care fiecare genă poate fi un pic, un număr sau un alt obiect. În implementările clasice GA presupune că genotipul are o lungime fixă. Cu toate acestea, există variații de HA libere a acestei limitări.
Crearea populația inițială
Înainte de primul pas este de a crea în mod aleatoriu o populație inițială; chiar dacă ar fi total necompetitivă este probabil ca algoritmul genetic este încă destul de repede traduce aceasta într-o populație viabilă. Astfel, primul pas poate fi mai ales nu încerca să facă prea celui mai adaptat, suficient pentru a se potrivi cu formatul indivizilor din populație, și să-i a fost posibil să se calculeze funcția de fitness (Fitness). Rezultatul primei etape este o populație H, formată din N indivizi.
Reproducerea în algoritmi genetici, de obicei, sexuale - pentru a produce urmasi, avem nevoie de cateva parinti, de obicei, două.
Reproducerea în diferite algoritmi definite în diferite moduri - este, desigur, depinde de reprezentarea datelor. Cerința principală de a reproduce - la un descendent sau descendenții au posibilitatea de a moșteni trăsăturile de ambii părinți, „amestec“ de ei în nici un fel.
De ce indivizii pentru reproducere sunt în mod tipic selectate din întreaga populație de H, iar supraviețuitorii nu sunt în elementele primul pas H0 (deși această din urmă opțiune are, de asemenea, dreptul de a exista)? Faptul că principala problemă a multor algoritmi genetici - lipsa de diversitate (diversitate) la indivizi. un singur genotip iese în evidență destul de repede, ceea ce este un maxim local, iar apoi toate elementele populației pierde alegerea sa, iar întreaga populație „cu ciocanul“ copii ale acestui individ. Există diferite modalități de a face cu acest efect nedorit; Unul dintre ei - alegerea de reproducere nu sunt mai puternici, dar, în general toți indivizii.
Mutațiile includ toate același lucru ca și de a reproduce: au o anumită cantitate de mutantă m, este parametrul de algoritm genetic, iar in mutatii pas pentru a alege indivizii mN, și apoi să le schimbe în funcție de operațiile de mutație predefinite
În etapa de selecție a necesității întregii populații de a alege un anumit procent din ea, care rămâne „viu“ în acest stadiu de evoluție. Există diferite moduri de a efectua selecția. h probabilitatea de supraviețuire individuală va depinde de valoarea funcției fitness (h). Însăși Raportul de supraviețuire s este, de obicei, parametrul de algoritm genetic, și tocmai stabilit în prealabil. Conform rezultatelor de selecție a N indivizi din populație ar trebui să rămână indivizi H Sn care urmează să fie incluse în populația finală H“. Păsările rămase ucis
La selectarea unui turneu (selecție turneu) dintr-o populație care conține N indivizi sunt selectate aleatoriu indivizi t, iar cel mai bun dintre ei este scris în individ matrice intermediar (Fig. 5). Această operație se repetă de N ori. Indivizii din matricea rezultată intermediar sunt apoi folosite pentru împerechere (ca la întâmplare). Mărimea grupului de selecție linie la turneu, de multe ori egal cu 2. În acest caz, vorbim de un binar (dublu) turneul. În general, numărul T se numește turneu. Avantajul acestei metode este că nu are nevoie de calcule suplimentare.
În metoda de ruleta (selecție ruleta roți) Eșantioane selectate prin intermediul N «ruleaza“ roulette unde N - mărimea populației. Roata ruletei conține un sector pentru fiecare membru al populației. Dimensiunea sectorului i-lea este proporțională cu probabilitatea de a cădea într-o nouă populație P (i),
calculat cu formula:
unde f (i) - adecvarea individului i-lea. Numărul estimat copie a cromozomului i-lea după ce operatorul de ruletă definit de Ni = P (i) cu formula N. Cu o astfel de selecție a membrilor populației cu adaptabilitate mai mare probabilitate mai mare de a fi selectate mai des decât persoanele cu fitness scazut (Tabel. 7). Alte tehnici de selecție pot fi derivate din modificările menționate mai sus. De exemplu, în selecția de ruleta, puteți schimba formula pentru probabilitatea unui individ de a introduce o nouă populație.