Grile PEAG full PDF

Preview

Summary

. __ _,.7() 7 {7~ r;-~TE /Iv er;-R. cr 1 (~ST€ 8UA/Partea I:@ ln algoritmii genetici, reprezentarea prin ,1ruri de numere intregl a. Este preferabila pentru probleme de optimizare b. Este doar un exercitiu de implementare, nefiind necesara -- E_preferabila_atunci_pentru fiecar gen.a..? P,Osibile_maU...

Description

2E-8.5-25.5 Partea I: un singur raspuns corect 1. Tipurile de probleme care pot fi rezolvate pe baza calcului evolutiv sunt: Probleme de optimizare (1), Probleme de modelare (4), Probleme de simulare (6) -> 1,4,6 (B). 2. Care din urmatorii operatori pot fi utilizati intr-un algoritm genetic care foloseste reprezentarea prin siruri reale? Mutatia uniforma (5), Mutatia neuniforma cu -distributie fixata (6), Aritmetica simpla (18), Aritmetica singulara (19), Aritmetica totala (20), Unipunct (14), Multipunct(15), Uniforma(16) -> (A) 3. In algoritmii genetici, reprezentarea prin siruri de numere intregi: e preferabila atunci cand pentru fiecare gena sunt posibile mai mult de doua valori distincte (D). 4. In algoritmii genetici, reprezentarea prin permutari: necesita operatori de variatie special definiti (D). 5. Calculul evolutiv este inspirat de: evolutia naturala biologica (A). 6. Algoritmul Hillclimbing: se aplica asupra unui singur punct din spatiul de cautare (1), Aplicarea de poate repeta pentru mai multe puncte pentru a creste performantele (2), De obicei gaseste un punct de optim local (7), Gaseste uneori solutia optima (5) Later edit: nu gaseste mereu solutia optima.(closed) - Cezar 7. In algoritmii genetici, reprezentarea binara: (B) A fost primul tip de reprezentare a cromozomilor in algoritmii genetici 8. Caracteristicile unui algoritm genetic clasic: (E)1,3,5,8 --1.Reprezentarea populatiei este realizata prin intermediul sirurilor binare, 3.Probabilitatea de selectie a unui individ in multisetul parintilor este proportionala cu valoarea functiei de evaluare pentru el; 5. Probabilitatea efectuarii unei mutatii este mica; 8.Probabilitatea efectuarii recombinarii este mare 9. Intr-un algoritm evolutiv, functia de tip calitate: Evalueaza calitatea fiecarui candidat (2), Trebuie maximizata(4) (B) 10. Componentele algoritmilor evolutivi sunt: reprezentarea, functia de evaluare, populatia, mecanismul de selectare a parintilor, operatorii de variatie, mecanismul de selectare a membrilor generatiei urmatoare, definirea modului de initializare(populatia initiala) si definirea conditiei terminale => raspuns corect: (B)

PARTEA II - variante multiple(gen)

GALBEN = SIGUR VERDE = INCERT

a. b. c. d. e. f. g. h. i. j.

1. In cadrul unui algoritm din clasa strategiilor evolutive, operatia de mutatie: Este utilizata doar in probleme cu constringeri Este realizata cu probabilitate mica Utilizeaza populatia curenta Utilizeaza populatia de copii Determina structura cromozomiala Este de tip neuniform Alege pentru mutatie in medie jumatate de indivizi Este efectuata o singura data pe parcursul unui algoritm Este efectuata iterativ Este efectuata imediat ce este disponibila o populatie de copii 2.

In cadrul unui algoritm genetic operatia de recombinare:

a. Este efectuata o singura data dupa prima etapa de selectie a parintilor b. Este utilizata cu probabilitate mica c. In general probabilitatea de recombinare nu conteaza in rezolvarea problemelor prin algoritmi genetici d. Este efectuata o singura data pe parcursul unui algoritm genetic e. Este efectuata imediat inaintea fiecare proceduri de mutatie f. Este efectuata imediat dupa fiecare etapa de selectie a parintilor g. Este utilizata cu probabilitate mare (intre 0.5 si 1, pag. 79) h. Este efectuata iterativ i. Este utilizata doar in probleme fara constrangeri j. Utilizeaza populatia de parinti (recombinarea celor doi parinti) 3. In cadrul unui algoritm evolutiv populatia initiala a. Este generata la inceputul fiecarui ciclu evolutiv-nu, pentru ca ciclu evolutiv inseamna fiecare generatie si nu e adevarat. b. Este generata utilizand distributia pe probabilitate normala c. Este generata inaintea inceperii evolutiei propriu-zise d. Este generata dupa fiecare ciclu evolutiv e.  Este generata utilizant distributia de probabilitate uniforma f. Este generata aleator (setul initial de candidati este generat aleator, curs 1) g. Este setata pe multimea vida

4. Fie urmatorii doi cromozomi de tip permutare {6, 3, 11,7, 14, 8, 5, 15, 1, 2, 4, 13, 9 ,10 ,12 } si {7, 1, 15,13,2, 14,6,10,12,11,4,8,3,9, 5}. Aplicand operatorul de recombinare PMX, cu pozitile 4 si 8 se obtin descendentii. .  a. 5 3 15 13 2 14 6 10 12 8 4 7 9 11 1 b. 5 3 11 13 2 14 6 15 1 8 4 7 9 10 12 c. 5 3 11 13 2 14 6 15 1 8 4 7 9 15 12 - al doilea copil d.13 1 10 7  14 8 5 15 12  11 4 2 3 9 6 - primul copil e. 5 3 15 13 2 14 6 10 1 8 4 7 9 11 12 f. 13 1 15 7 14 8 5 10 12 11 4 2 3 9 6 g. 13 12 11 7  14 8 5 15 1 10 4 2 3 9 6 h. 13 1 11 7 14 8 5 15 12  10 4 2 3 9 6 i. 13 12 11 7  14 8 5 15 1 10 4 2 3 9 6 j. 5 3 15 13 2 14 6 10 12 8 4 7 9 11 1

5.

In cadrul unui algoritm din clasa strategiilor evolutive, operatia de recombinare:

a. Este de tip local sau global b. Este efectuata o singura data pe parcursul unui algoritm c. Alege pentru recombinare in medie jumatate de indivizi d. Este realizata cu probabilitate mica e. Determina structura cromozomiala f. Utilizeaza poplatia curenta g. Este efectuata o singura data, dupa prima etapa de generare a unei populatii h. Determina obtinerea unui multiset de copii in general de dimensiuni mai mari comparativ cu populatia curenta. i. Este utilizata doar in probleme cu constrangeri j. Este efectuata iterativ 6. In cadrul unui algoritm din clasa strategiilor evolutive, reprezentarea cromozomilor

a. Influenteaza tipul de recombinare folosit b. Se alege in functie de problema care se rezolva c. Poate fi numai de tip siruri de numere intregi sau reale d. Poate fi oricare dintre: siruri binare, siruri de numere intregi, siruri de numere reale, permutari e. Are influenta asupra mecanismului de selectie a generatiei urmatoare f.  Nu influenteaza tipul de mutatie folosit(discreta/ nediscreta) g. Poate fi numai de siruri de numere reale h. Contine atat descrierea individului candidat cat si parametrii care controleaza evolutia sa. 7.

a. b. c.

In cadrul unui algoritm genetic operatia de selectie a parintilor

Intotdeauna este bazata pe o distributie de probabilitate de selectie Utilizeaza populatia curenta Este efectuata o singura data pe parcursul unui algoritm genetic

d. Este utilizata doar in probleme cu constringeri e. Este efectuata imediat inaintea fiecarei proceduri de mutatie f. Este efectuata imediat ce este disponibila o populatie curenta eva luata g. Este efectuata o singura data dupa prima etapa de generare a unei populatii h. Alege in general indivizi pe baza factorului varsta i. Utilizeaza populatia de copii mutati j. Utilizeaza populatia de copii k. Este efectuata iterativ l. Poate fi realizata prin utilizarea unei distributii de probabilitate de selectie 8. Fie urmatorul cromozom de tip permutare {7, 6, 12, 14, 3, 10, 8, 15, 11, 5, 4, 1, 13, 2, 9} In urma aplicarii operatorului de mutatie prin amestec s-a obitnut cromozomul {7, 14, 13, 12, 1, 15, 2, 8, 6, 3, 11, 5, 10, 4, 9 }. Cele doua pozitii utilizate pentru amestesc sunt: 7, 6, 12, 14, 3, 10, 8, 15, 11, 5, 4, 1, 13, 2, 9 7, 14, 13, 12, 1, 15, 2, 8, 6, 3, 11, 5, 10, 4, 9

a. 3 si 13 b. 1 si 15 c. 1 si 14 d. 4 si 8 e. 1 si 12 f. 4 si 15 g. 3 si 15 h. 2 si 13 i. 2 si 14 j. 2 si 15 k. 1 si 13 (Ori e doar I, ori e E,G,H,I-Cezar) - eu as zice b/c/i/j pentru ca se aplica mutatia o singura data 9. In cadrul unui algoritm genetic operatia de mutatie

a.  b. c. d. e. f. g. h. i. face era)

 re probabilitate mica A Se aplica doar daca divesitatea genetica scade sub un prag x dat Intotdeauna produce indivizi fezabili Se aplica asupra descendentilor produsi de operatia de recombinare Se aplica asupra mutlisetului de parinti Se aplica asupra populatiei curente Se utilizeaza doar in probleme cu constrangeri Poate sa produca indivizi nefezabili Se efectueaza o singura data, dupa generarea populatiei initiale (mutatia se de mai multe ori; in cazul unui algoritm genetic, mutatia se face in fiecare

j. Se aplica imediat inaintea fiecarei etape de selectie a generatiei urmatoare (cred ca dupa mutatie urmeaza evaluare si dupa aceea selectia.- deci asta nu ar fi) k. Se utilizeaza doar in problemele fara constrangeri l. Nu foloseste factori aleatori. 10.

In cadrul unui algoritm genetic operatia de selectie a supravietuitorilor

a. Utilizeaza intotdeauna factori aleatori b. In unele variante necesita calcularea unei distributii de probabilitate de selectie c. Indivizii alesi sunt intotdeauna fezabili d.  Duce la cresterea calitatii medii a populatiei curente e. Se aplica la inceputul fiecarei iteratii f. Uneori utilizeaza factori aleatori g. Se aplica asupra populatiei curente si asupra descendentilor obtinuti h. Garanteaza obtinerea unei generatii cu calitate medie superioara. Daca foloseste selectia bazata pe varsta. (ASTA ESTE GENITOR, NU VARSTA) i. Se aplica asupra descendentilor. Asigura perpetuarea individului cu calitate maxima din populatia curenta j. Alege generatia urmatoare dintre indivizii disponibili dupa operatia de mutatie k. Se aplica asupra descendentilor obtinuti din populatia curenta

Structura EA

Structura GA...