ALGORITMI GENETICI - · PDF fileTehnoredactare : Luță Costina Claudia Referent...

0

ALGORITMI GENETICI Vol.II

S L A T I N A 2 0 1 4

VOL.II

ISBN 978-973-0-16090-1

ALGORITMI GENETICI

LUȚĂ COSTINA CLAUDIA

1


Tehnoredactare : Luță Costina Claudia

Referent ştiinţific:

Profesor gradul I ~ Gabriela Raluca Ionică~

Inspector şcolar de specialitate I.S.J. Olt

Autor:

Profesor gradul I ~Luță Costina Claudia ~

Colegiul Tehnic “Alexe Marin” Slatina

2


CERCETARE PEDAGOGICĂ

CAPITOLUL III

3.1 Ipoteza de lucru

Descentralizarea economiei, trecerea la economia de piaţă, restrângerea

numărului locurilor de muncă, noile exigenţe, determină o responsabilitate

sporită a liceelor în formarea şi perfecţionarea specialiştilor în informatică.

Formarea competenţei profesionale a tinerilor este asigurată prin

instruirea lor competentă şi progresivă, în timpul şcolarizării, procesul de

învăţământ fiind organizat astfel ca elevii să fie sprijiniţi în dobândirea

competenţei corespunzătoare obiectivelor generale ale disciplinelor de

informatică pentru care se pregătesc.

Consider că cerinţele progresului tehnico-economic şi condiţiile

concurenţei pe piaţa muncii, impun desfăşurarea unui proces de învăţământ care

să asigure o cultură generală, pe fondul căreia să se dezvolte gândirea

informatică, înţelegerea principiilor care au stat la baza descoperirilor si

creaţiilor ştiinţei, care să promoveze o reacţie pozitivă faţă de mediul informatic

şi să formeze premisele teoretice, tehnice şi practice ale însuşirii în condiţii bune

a disciplinelor care asigură o calificare si o specializare înaltă.

Din experienţa didactică, am constatat că, prin însuşirea disciplinelor de

informatică se asigură, în afara competenţei profesionale şi dobândirea valorilor

ştiinţifice, tehnice si psiho-socio-morale, care au ca finalităţi nu numai

profesionalizarea ci şi formarea unor personalităţi complete, bazate pe o cultură

generală corespunzătoare, dar şi a celor de ordin social.

3


Cred că, formarea elevilor ar fi mai bună dacă i-aş antrena în realizarea

de aplicaţii mai eficiente, cu un grad de complexitate mai ridicat.

Am urmărit ca metoda folosită să conducă la cercetare şi creaţie, la

dorinţa elevilor de a cunoaşte şi a investiga în acest scop , dincolo de limitele

programelor de informatică. Doresc ca lecţiile astfel realizate să conducă la :

Însuşirea suportului noţional de bază al teoriei algoritmilor genetici,

precum şi a deprinderilor esenţiale necesare aplicării acestora în

diverse implementări simple sau de complexitate medie ;

Formarea gândirii logice, care să permită elevului să aprecieze corect

situaţiile concrete specifice, cu scopul de a desprinde soluţii optime;

Formarea deprinderilor de aplicare corectă a soluţiilor alese;

Formarea deprinderilor de a realiza comparaţii între soluţiile obţinute

folosind programarea clasică şi cele obţinute prin aplicarea

algoritmilor genetici;

4


3.2 Obiectivele cercetării

Stabilind scopurile studierii disciplinelor de informatică, este de dorit să

se înceapă procesul de atingere a unor obiective precis stabilite. Obiectivele

vizează ce va şti elevul după lecţie, deci nişte finalităţi ale procesului de predare-

învăţare.

A operaţionaliza un obiectiv pedagogic înseamnă a transpune în termeni

de operaţii şi acţiuni sau alte manifestări observabile şi măsurabile, rezultate în

urma unei instruiri, a ceea ce trebuie să cunoască şi ce vor fi capabili elevii să

facă la încheierea procesului de predare-învăţare.

Literatura pedagogică evidenţiază patru timpi ai tehnicii de elaborare ai

unui obiectiv, redaţi în figura următoare :

Acţiunea

observabilă

prin care se

va

exterioriza

comporta-

mentul

+

+

Obiectul

(conţinutul

acţiunii)

+

+

Condiţiile

în care

elevul va

putea

proba

formarea

comporta-

mentului

+

+

Criteriile

după care

se vor

aprecia

perfor-

manţele

Comportamentul dorit să se formeze

prin învăţare

Precizează modalităţile în care se

va proba şi evalua nivelul de

formare a comportamentului

Obiectivele generale ale predării informaticii în şcoală sunt determinate de

următoarele aspecte :

5


importanţa informaticii şi calculatorului în lumea contemporană şi

rolul acestora în dezvoltarea ştiinţifică şi tehnico-economică a

societăţii umane ;

necesităţile învăţământului privind formarea unei culturi generale şi

de specialitate a absolvenţilor, în vederea integrării lor rapide în

societate ;

necesitatea de a dezvolta capacităţi intelectuale, estetice şi moral

umane.

Obiectivele cercetării metodice în temă urmăresc:

Proiectarea pedagogică, având la bază un demers complex care

presupune o conlucrare permanentă a competenţei pedagogice cu

competenţa informatică;

Implementarea informatică, care se valorizează numai în conexiune

cu cerinţele pedagogice în afara cărora produsul final n-ar mai fi

eficient

Validarea experimentală atât a lucrării cât şi a demersului cercetării

pedagogice

În legătură cu primul obiectiv, un minim de competenţe informatice

asigură preluarea, de la adresele www.edu.ro, www.portal.edu.ro,

www.didactic.ro a programei analitice şcolare şi sugestiilor metodologice pentru

elaborarea planificărilor anuale şi semestriale. Întocmirea fişelor de lucru pentru

elevi, a testelor de evaluare, a temelor pentru atestat profesional în meseria de

ajutor analist programator-operator tehnică de calcul, a subiectelor popuse

pentru lucrările scrise, lucrări practice şi simularea examenului de bacalaureat

constituie de asemenea puncte de reper realizabile.

Al doilea obiectiv, oferă posibilitatea de a pune în lucru o metodologie

experimentală foarte riguroasă şi constă în rularea programelor ce folosesc în

http://www.edu.ro/

http://www.portal.edu.ro/

http://www.didactic.ro/

6


implementare algoritmi genetici, eventual cu întreaga clasă sau cu un grup

restrâns de elevi.

Validarea experimentală se constituie ca produs final şi oferă o viziune de

ansamblu asupra unităţii de instruire. El reprezintă o oportunitate de a constata

care sunt aspectele insuficient de bine puse la punct şi care creează dificultăţi

celui care învaţă, adică de a obţine o realizare formativă. Evident, că ulterior se

poate studia eficienţa lui ca mediu de instruire în raport cu alte procedee folosite

de utilizatorul-elev.

7


3.3 Metodologia verificării ipotezei

3.3.1. Tipologia cercetării

Direcţiile abordării cercetării s-au ramificat astfel:

Direcţia abordării cercetării este longitudinală prelucrând o experienţă

pozitivă acumulată în timp longitudinal, pe altă structură a programei,

a manualelor, a orelor alocate disciplinelor informatice;

Rolul abordării este descriptiv, analitic, explicativ, acţional dar şi

operaţional

Gradul de organizare este sistematic, planificând etapele ce se

desfăşoară în contextul real al unei clase urmărită un timp stabilit, pe

parcursul unui an şcolar.

Organizarea a permis între anumite limite şi o abordare spontană şi nu

a perturbat procesul de învăţământ.

Cercetarea s-a extins de la nivelul clasei, deci de la relaţia profesor-elevi

până la relaţia profesor-profesor prin conlucrarea la nivelul catedrei de

informatică din şcoală

Scopul urmărit este ameliorativ, de perfecţionare şi optimizare a unor

aspecte ale procesului de învăţământ

Esenţa cercetării este de îmbinare a teoriei cu practica pozitivă

acumulată prin punerea în practică a unor idei teoretice, pedagogice şi

metodice în condiţiile concrete specifice.

Metodologia utilizată este experimentală prin faptul că se introduc

explicit măsuri ameliorative într-un mod anume organizat.

Am îmbinat teoria cu practica pozitivă acumulată şi am aplicat

propriu-zis idei teoretice, pedagogice şi metodice în condiţiile concrete

specifice, de cunoaştere şi explicare a fenomenelor semnificative din

practica proprie, de construire şi verificare a unor modele proprii de

8


optimizare metodică, de formulare a soluţiilor pentru situaţii variate şi

reale din practică, de dezvoltare a unor contribuţii anterioare.

Tipul de cercetare folosit, în final este de tip combinat ( mixt ).

Finalitatea urmărită de cercetare este de tip constatativ, cunoscând

situaţiile de reuşită=succes sau eşec=insucces şcolar, cu aspecte

ameliorative vizând activitatea de perfecţionare şi optimizare a

metodelor centrate pe adaptarea la particularităţile de vârstă şi

individuale, de performanţă, respectiv de recuperare

3.3.2 Organizarea cercetării

Am optat, după modul de abordare a tematicii, pentru o cercetare

experimentală, abordând atât trunchiul comun cât şi curriculum la decizia şcolii,

fiind antrenată clasa a XI a de la profilul matematică-informatică cu predare

intensiv informatică. Am urmărit efectele măsurilor luate, raportându-mă la

evaluarea iniţială şi finală a clasei pe aceleaşi obiective. Ipoteza cercetării a

rezultat din acelaşi context al clasei şi este evident că, tot în clasă trebuie să se

rezolve, implicându-mă alături de elevi la verificarea ipotezei şi a obiectivelor.

Perioada propusă este parcursul anului şcolar 2005-2006, o oră pe

săptămână.

Etapele parcurse sunt :

s-au realizat fişierele document cu conţinutul informativ al

sistemului de lecţii

s-au realizat fişiere Power Point cu diverse facilităţi de imagine,

sunet şi animaţie

am aplicat cercetarea pe 2 eşantioane de elevi, cu nivele de

pregătire diferită: mediu şi performant;

9


ca măsură experimentală, am utilizat ca variabilă independentă

evaluarea iniţială în urma căreia s-au format cele 2 eşantioane de

elevi;

am antrenat 3 categorii de variabile:

variabile independente, de intrare: scopuri, mijloace, condiţii,

măsuri care determină stabilirea strategiei de cercetare,

clasificate după importanţă, volum, prioritate, frecvenţă,

urmate de verificarea ipotezei;

variabile dependente, de ieşire, ca răspuns la acţiunea celor

independente, care au fost consemnate în "grila de

observaţie", cu efecte pozitive şi negative, aşteptate şi

neaşteptate, principale sau secundare. Raportându-mă la

rezultatele măsurilor introduse în predarea la orele de

informatică, am luat în calcul ca variabile dependente cu

valoare activă interesul manifestat de elevi pentru o metodă

sau alta ;

variabile perturbatoare, neprogramate ca elemente de

interacţiune între celelalte variabile, care produc efecte

diferenţiate în aplicare: experienţe individuale, factori

extraşcolari. Factorii perturbatori au mai fost de natură

tehnică şi anume variaţii ale tensiunii şi frecvenţei curentului

electric, incompatibilităţi soft legate de versiunea pachetelor

de aplicaţii, ştergeri accidentale ale fişierelor.

Ca limite, am sesizat dificultatea delimitării variabilelor şi a relaţiilor lor,

imposibilitatea cuprinderii tuturor variabilelor necesare, irepetabilitatea

experimentului datorată unicităţii situaţiilor în structurarea, desfăşurarea şi

evoluţia lor. S-a impus, în baza propriei experienţe, utilizarea eficientă a

metodelor de comunicare didactică variate cu acţiuni ameliorative pe diverse

laturi: strategii, resurse, organizare, rezultând o paletă extinsă de calităţi

10


manageriale ale profesorului de astăzi care trebuie să fie pregătit să identifice, să

combată, să prevină diferite situaţii problematice. Rolul de coordonator ce-i

revine profesorului în folosirea metodelor active este major. Reuşita lecţiei

depinde şi de modul în care profesorul ştie să organizeze activitatea liberă a

elevilor.

Metodele activ-participative pot fi folosite în orice moment al lecţiei, iar

alegerea lor este rezultatul unei pregătiri prealabile riguroase, dar şi al

ingeniozităţii provenită din situaţiile concrete şi imprevizibile apărute la clasă.

Unii elevi au întâmpinat dificultăţi chiar şi în luarea notiţelor, de aceea,

transpunerea teoriei în itemi accesibili elevilor a fost absolut necesară. Mai întâi,

am folosit cu tact şi măiestrie, metode cum sunt conversaţia şi explicaţia,

exerciţiul şi dialogul euristic şi apoi gradat, trecând la metode ca

problematizarea, munca independentă, descoperirea, algoritmizarea etc.

Metodele activ-participative se pot folosi atât la orele de curs şi, în

special, în orele de laborator, în care elevul, pus în faţa propriului calculator are

posibilitatea de a lua decizii referitor la modul de rezolvare a diverselor situaţii

problematice create, poate să-şi clarifice unele nelămuriri, pe loc, fără a adânci

latura critică a necunoaşterii.

Experimentul s-a desfăşurat la Grupul Şcolar Agricol „Constantin

Dobrescu” Curtea de Arges, precum şi toate testele şi statisticile prezentate.

11


3.3.3 Metodele de cercetare utilizate

În cercetarea pe care am realizat-o am folosit următoarele metode de

investigare:

Observaţia

La clasa antrenată în cercetare, am recurs la construirea unui plan criterial,

pentru acumularea de materiale şi date, concomitent cu desfăşurarea

experimentului.

În plus am stabilit modul de utilizare a unui sistem de decizii tactice şi

operative pornind de la o decizie strategică globală, pentru a indica modul

concret de realizare a ei, prin sarcini, situaţii delimitate, înlănţuite într-o anumită

succesiune în timpul desfăşurării activităţii. Am îmbinat strategiile didactice

clasice cu metodele moderne, activ-participative în diferite lecţii, şi am observat

efectul produs asupra unui subiect independent, asupra unui grup restrâns de

subiecţi şi, în final asupra întregii clase de elevi.

Studiul documentelor şcolare

Am folosit programa de informatică, manualele, notiţele elevilor, lucrările

de laborator, cataloagele, tezele, produse-program, teste şi fişe de evaluare,

portofoliile elevilor.

Metoda bibliografică

Pentru documentarea ştiinţifică am studiat materialului bibliografic de

specialitate şi de pedagogie, iar pentru aceasta am făcut apel la biblioteca

proprie, biblioteca şcolii şi, nu în ultimul rând, la Internet. De asemenea pentru

culegerea materialului am colaborat şi cu profesorii din catedra de informatică

care mi-au pus la dispoziţie diverse planuri de lecţii .

Pentru obţinerea datelor referitoare la caracterizarea metodelor în general,

a metodelor activ-participative, în special, la o taxonomie a acestora din

12


perspectiva obţinerii de performanţe la clasă, în procesul de predare-învăţare-

evaluare, metoda bibliografică a reprezentat un instrument de bază al cercetării.

Materialul bibliografic studiat a fost organizat şi sistematizat pe capitole

şi subcapitole fiind integrat în lucrare.

Modul de acumulare a informaţiilor reprezentative pentru verificarea

ipotezei pe obiective a fost stocarea acestora pe CD-uri, realizarea de fişe de

lucru pentru elevi, organizarea datelor de evaluare: note, calificative în tabele,

diagrame, scale de valori.

Metoda chestionarelor şi a convorbirilor cu cadrele didactice şi elevii

despre tema cercetată, a fost utilizată pentru culegerea de informaţii cu privire la

tema respectivă cât şi pentru verificarea ipotezei de lucru.

Am folosit această metodă şi pentru a cunoaşte nivelul de pregătire al

subiecţilor pe de o parte, şi modul cum şi-ar dori să li se predea o anumită

disciplină, de către ”profesorul ideal”, pe de altă parte. Am realizat un dialog

firesc, democratic, individual, sau colectiv, care a confirmat adeziunea elevilor

la metodele de predare moderne, în comparţie cu cele clasice, pasive, precum şi

apetenţa pentru noi achiziţii cognitive, in afara programei şcolare.

Metoda experimentului pedagogic s-a concretizat în elaborarea şi

experimentarea la clasa de control a unui soft educaţional referitor la un set de

lecţii. În acest fel, se încearcă punerea la dispoziţie a unui nou instrument de

predare şi evaluare pentru o masă largă de utilizatori, deschizând perspectivele

completării atât cu teme de la aceeaşi disciplină cât şi cu subiecte de la alte

discipline În mod sigur, această metodă a reprezentat metoda cea mai

edificatoare în ceea ce priveşte descoperirea strategiilor care duc la obţinerea de

succese, a performanţei, şi a celor care ar putea fi îmbunătăţite.

13


Metoda testelor de cunoştinţe ( eseu, teste grilă ) a fost folosită pentru a

constata rezultatele obţinute în urma acestui tip de lecţii, a introducerii noului

conţinut informaţional si practic pe lângă conţinutul programei şcolare clasice.

Pentru interpretarea parţială sau finală a rezultatelor am utilizat metode de

interpretare cantitativă şi calitativă, tehnici statistice, metode deductive.

Metoda statistică

Mi-a permis să raportez rezultatele obţinute în cazul aplicării rigide a unor

metode clasice, la cele obţinute, în cazul utilizării în mod creativ a unor metode.

În urma consultării unor materiale de specialitate am avut posibilitatea să

cunosc diverse statistici obţinute de alţi cercetători, dar şi să stabilesc eventuale

alte rezultate, prin investigaţii proprii.

14


CAPITOLUL IV

PREZENTAREA ŞI INTERPRETAREA REZULTATELOR OBŢINUTE

În viaţa de zi cu zi întâlnim aplicaţii care se rezolvă prin diverse metode,

acest fapt fiind o consecinţă a necesitaţii creării unor prioritaţi pentru obiecte,

fenomene sau chiar noţiuni abstracte.

În general, orice sarcină abstractă care trebuie îndeplinită, poate fi

privită ca fiind rezolvarea unei probleme, care, la rândul ei, poate fi

percepută ca o căutare în spaţiul soluţiilor potenţiale. Deoarece, de obicei,

căutăm cea mai bună soluţie, putem privi acest proces ca fiind unul de

optimizare. Pentru spaţii mici, metodele clasice exhaustive sunt suficiente,

pentru spaţii mari, pot fi folosite tehnicile speciale ale algoritmilor genetici.

Metodele calculului evolutiv se numără printre aceste tehnici. Ele folosesc

algoritmi ale cãror metode de căutare au ca model câteva fenomene naturale:

moştenirea genetică şi lupta pentru supravieţuire. Cele mai cunoscute

tehnici din clasa calculului evolutiv sunt algoritmii genetici, strategiile

evolutive, programarea genetică şi programarea evolutivă. Există şi alte sisteme

hibride care încorporează diferite proprietăţi ale paradigmelor de mai sus; mai

mult, structura oricărui algoritm de calcul evolutiv este, în mare mãsurã, aceeaşi.

În ultimii 30 de ani, s-a manifestat un mare interes în rezolvarea

problemelor de sistem bazate pe principiile evoluţiei şi ereditătii. Astfel de

sisteme menţin o populaţie de soluţii potenţiale, ele au unele procese de selecţie

bazate pe fitness individual, şi caţiva operatori genetici. Un astfel de sistem este

o clasa a evoluţiei strategice i.e, algoritmi care imită principiile evoluţiei

naturale pentru problemele de optimizare de parametru(Rechemberg,

Schwefel). Evoluţia programării lui Fogel este o tehnică de căutare într-un

15


spaţiu finit, mic de maşini. Tehnologiile de cautare a maşinii lui Glover

Scatter menţin o populaţie de puncte de referinţă, generând o stare

speciala prin greutatea combinaţiilor liniare.

Teoria algoritmilor genetici este relativ nouă şi este aplicabilă cu succes

problemelor NP-complete, pentru care nu se cunosc algoritmi de complexitate

polinomială dar şi problemelor pentru care, deşi există metode polinomiale de

rezolvare, acestea nu sunt cunoscute de către rezolvitor ( de exemplu, cazul

problemelor mai dificile de la concursuri ).

4.1 Experiment privind aplicarea algoritmilor genetici

La predarea algoritmilor genetici mi-am propus realizarea următoarelor

obiective:

găsirea unei modalităţi cât mai simple, cât mai acceptabile şi mai

uşor de înţeles pentru toţi elevii, de transmitere a cunoştinţelor

teoretice de bază privind algoritmii genetici;

identificarea problemelor care se rezolvă folosind algoritmi

genetici;

familiarizarea cu metodele de lucru specifice algoritmilor genetici;

formarea unor deprinderi elementare, necesare în analiza unor

probleme ce le vom rezolva evolutiv ;

dezvoltarea deprinderilor de rezolvare a aplicaţiilor ce folosesc

algoritmi genetici;

Pentru realizarea acestor obiective în predarea teoriei algoritmilor

genetici, am căutat să folosesc acele metode active care să-i ajute pe elevi să

descifreze, după posibilităţile lor, condiţiile necesare pentru rezolvarea unei

aplicaţii ce foloseşte algoritmi genetici şi să scrie programele în limbajul C.

16


Dintre acestea, o metodă foarte eficace este învăţarea prin descoperire.

După cum o să vedem în rândurile următoare, ea prezintă multe avantaje, dacă

este folosită cu mult tact, ţinând cont de vârsta şi puţina experienţă a elevilor de

clasa a XI-a.

Astfel, plecând de la acest considerent, în lecţiile de predare a noţiunilor

de bază despre algoritmii genetici şi de rezolvare a aplicaţiilor ce folosesc aceast

tip de algoritmi, am început cu o introducere despre teoria algoritmilor genetici

în general însoţită de exemple de probleme ce folosesc aceast tip de algoritmi şi

în final am propus spre rezolvare aplicaţii de dificultate gradată. Folosind

metoda conversaţiei îmbinată cu explicaţia şi punând accent pe luarea notiţelor,

elevii au înţeles în ce tip de aplicaţii putem aplica algoritmii genetici precum şi

rolul acestor algoritmi.

Considerând că elevii au câştigat o cât de mică experienţă în însuşirea

cunoştinţelor despre teoria algoritmilor genetici, mi-am propus să folosesc

metoda descoperirii urmărind cum se descurcă elevii în rezolvarea problemelor,

cum îşi notează în caiete şi mai puţin dacă este mai eficace aceasta, decât

explicaţia pe care aş fi făcut-o eu pe parcursul orei.

Lecţiile acestea au fost făcute împreună cu elevii care au fost solicitaţi

foarte mult, lăsând impresia unei lecţii de consolidare, şi nu de dobândire de

cunoştinţe.

Pentru a înţelege mecanismul de funcţionare al algoritmilor genetici, am

început cu exemple de probleme în care se aplică aceşti algoritmi, după care am

continuat cu descrierea schemei de bază a acestora.

Am reamintit mai întâi noţiunile teoretice introductive din teoria

algoritmilor genetici pentru a avea un limbaj comun şi riguros ştiinţific.

Algoritmul genetic propus pentru rezolvare a fost "Maximizarea unei

functii”

17


Exemplu: Maximizarea unei functii

• Dorim sa optimizam o functie simpla:

f(x)=x*sin(10π*x)+1.0 unde x[-1,2]

• Este usor sa descoperim maximul folosind prima derivata. Valoare maxima

va fi f(1.85) = 2.85

Vom construi in continuare un algoritm genetic care sa maximize functia f.

Reprezentare: Vom folosi v un vector binar.

1. Lungimea vectorului depinde de precizie, care in acest exemplu va fi

6 zecimale.

2. Domeniul lui x are lungime 3([-1,2]).

• (1) + (2) => valoare lui v in baza 10 trebuie sa fie cel putin 3*1000000 =>

avem nevoie de 22 de biti:

2097152=221

<3000000≤222

=4194304

• Vom transforma valoarea lui v=(v21…v0) intr- un numar real x din

intervalul [-1,2] in doi pasi:

1. Convertim vectorul binar (v21…v0) din baza 2 in baza 10 si il

notam cu v1.

2. x corespunzator este: x=-1.0+v1[3/(222

-1)]

Initializarea populatiei. Este un proces foarte simplu vom crea o populatie de

cromozomi unde fiecare cromozom este un vector binar alcatuit din 22 biti.

Fiecare cromozom este initializat aleator.

Functia de adecvare. In acest caz o vom nota cu eval(v)=f(x). Cel mai bun

18


cromozom va fi acela care are cea mai mare valoare.

Selectia

1. Calculam eval(vi) pentru fiecare cromozom i=(1…pop_size).

2. Calculam F=suma(eval(vi)).

3. Calculam probabilitatea pi=eval(v

i)/F.

4. Calculam o probabilitate cumulata:

qi=suma(p

j) , j=(1,…,i)

5. Generam un numar r in intervalul [0,1].

6. Daca r<q1

selectam pe q1

daca nu selectam pe qi

astfel incat qi<r<q

i

Incrucisarea

1. Se alege un pc acesta reprezinta probabilitatea incrucisarii.

2. Pentru fiecare cromozom se genereaza un r din [0,1].

3. Daca pc> r atunci se selecteaza pentru incrucisare.

Mutatia

1. Se alege un pm acesta reprezinta probabilitatea

incrucisarii.

2. Pentru fiecare bit din cromozom se genereaza un r din [0,1].

3. Daca pm> r atunci se aplica mutatia

(daca este 0 =>1, daca este 1=>0).

După ce le-am lăsat 30 minute pentru a desfăşura activitatea independentă

de a scrie programele C, dar urmărindu-i cum rezolvă problema şi cum îşi

19


notează, am trecut la sistematizarea cunoştinţelor, în sensul că elevii au înţeles

scrierea programului folosind noţiuni de teoria algoritmilor genetici.

După implementarea şi corectarea eventualelor erori de sintaxă am

înregistrat rezultatele.

La începutul orei următoare, timp de 15 minute am dat o scurtă lucrare de

control (să descrie care sunt modalităţile de reprezentare în memorie a

cromozomilor, cum se poate face selecţia cromozomilor, care este rolul funcţiei

de adecvare), pentru a vedea cum şi-au însuşit cunoştinţele, obţinându-se

următoarele rezultate:

Note 9,

10

7,8 6, 5 4

Nr.elevi 7 3 2 2

Clasa a XI-a C

Deşi notele de 4 au fost multe, acest insucces nu m-a descurajat, căutând

cauzele, făcându-mă să înţeleg că trebuie să-mi îndrept atenţia către elevii care

înţeleg mai greu.

La următoarele aplicaţii, elevii au fost antrenaţi în însuşirea noilor

informaţii. Această implicare a elevilor a fost făcută folosind metode ca:

conversaţia, observaţia, exerciţiul, descoperirea, problematizarea.

Rezolvarea celorlalte aplicaţii şi scrierea programelor pentru problemele

care impun folosirea algoritmilor genetici, a fost o învăţare dirijată, elevii

îmbinând efortul propriu cu îndrumările primite din partea mea.

Am continuat cu aplicaţia Expresia aritmetica parcurgând aceleaşi etape

ca şi la problema anterioară.

Astfel de învăţare a dinamizat întreaga clasă spre o rezolvare corectă, şi cei

mai mulţi elevi, au reuşit prin munca independentă scrierea programului cerut.

20


Următoarea oră a fost destinată scrierii programului pentru Expresia

aritmetica.

Exemplu:

Sa se implementeze algoritmul de creare a arborelui unei expresii aritmetice

care contine ca operatori binari pe + si -, iar operanzii sunt litere sau cifre.

# include <stdio.h>

# include <alloc.h>

# include <ctype.h>

typedef struct node {

char inf;

struct node *left, *right;

}tnode;

tnode *root;

tnode*E(void);

tnode*F(void){

tnode *q;

if(isalnum(c) {

q=(tnode*) malloc (sizeof(tnode));

q->left=q->right =NULL;

q->inf=c;

c=getchar();

}

else if (c==’)’) c=getchar();

else printf(„\n Lipseste paranteza dreapta”);

}

else printf(„\n Expresie eronata”);

return q;

}

tnode *T(void) {

tnode *f,*q, *t;

t=F();

21


while (c==’*’) {

c=getchar();

f=F();

q=(tnode *) malloc (sizeof(tnode));

q->inf=’*’;

q->left=t;

q->right =f;

t=q;

}

return t;

}

tnode *E(void) {

tnode *t,*q, *e;

e=T();

while (c==’+’) {

c=getchar();

t=T();

q=(tnode *) malloc (sizeof(tnode));

q->inf=’+’;

q->left=e;

q->right =t;

e=q;

}

return e;

}

tnode *CREATE (void) {

printf („\n Introduceti expresia\n);

c=getchar();

return E();

}

void LIST(tnode * root, int 1) {

22


int i;

if (root!=NULL) {

LIST (root->left, l+1);

for (i=0;i<1; i++) printf(„ „);

printf („%c\n”,root ->inf);

LIST(root->right, l+1);

}

}

void main (void) {

root=CREATE();

LIST (root, 0);

}

Următoarea lecţie a fost o lecţie de verificare, obţinându-se următoarele

rezultate:

Note 9,10 7,8 5, 6 4

Nr.ele

vi 7 4 2 1

Proce

nt 50%

21,5

%

21,5

% 7%

Clasa a XI-a C

Deşi la această verificare rezultatele au fost mai bune, am observat că încă

nu toţi elevii ştiu să folosească instrumentele specifice algoritmilor genetici, că

încă nu fac legătura între noţiunile teoretice şi interpretarea problemelor din

realitate, nu sistematizează cunoştinţele. De aceea, am pornit de la prezentarea

principiului de funcţionare, după care am trecut la aplicarea sa în probleme.

23


Următoarea aplicaţie pe care le-am propus-o foloseşte nu numai noţiuni

de bază din teoria algoritmilor genetici ci şi cunoştinţe temeinice de programare

în limbajul C.

Am recapitulat noţiunile şi principiile necesare şi am făcut diverse

interpretări asupra lor. Noţiunile de bază precum şi principiile de funcţionare ale

unui algoritm genetic au fost prezentate în capitolul 2.

După implementerea de către elevi sub observarea mea a programelor şi

înregistrarea progreselor am mai propus spre studiu problema ONEMAX.

Exemplu:

Să se maximizeze numărul de cifre egale cu 1 dintr-un şir de L cifre

binare.

Se consideră {0,1}L

mulţimea şirurilor binare de lungime L. Pentru un şir s din

această mulţime notăm cu s1 numărul de componente egale cu 1 ale şirului. Fie

N un număr natural nenul mai mic decât L, şi f o funcţie care asociază fiecărui

şir s o valoare egală cu s1 dacă s1 nu este multiplu de N, şi 2s1 în caz contrar. Să

se găsească un şir s* care maximizează f. Se va lua valorile L=10 şi N=3.

Exemplu de utilizare :

Program ce constă în maximizarea unei funcţii definite f(s)=s1 Se deschide

fişierul ex1.prj din Borland şi se modifică fişierul ex1.c. Fişierul rezultat va avea

forma :

#include<stdio.h>

#include”sugar.h”

int evaluate(SuChromosome*chrom,double*fitness);

main( int argc,char*arvg[] )

{

SuaEvaluationFunction=evaluate;

SuRun( “ex1.cfg”,argc,argv );

24


}

int evaluate (SuChromosome*chrom,double*fitness);

{

int i;

int N=3;

int count=0;

double result=0.0;

for( i=0; i<chrom->length;++i )

count+=SuGetBit( chrom->string,i );

if(count%N==0)result=2*count;

else result =count;

*fitness=result

return 0;

}

Modificările au fost făcute în funcţia de evaluare. Pentru a seta

parametrii algoritmului genetic am schimbat liniile fişierului ex1.cfg după cum

urmează :

generation 10

population 10

length 10

în generation 100

population 50

length 10

(întâmplător, lungimea şirului binar era predefinită ca 10, în general ea va

trebui modificată)

Rularea algoritmului se face prin comanda ex1.exe. În urma rulării

programul obţine valoarea 1101111111, una dintre cele care maximizează f.

25


Considerând că de-a lungul mai multor lecţii, elevii şi-au format cât de cât

deprinderea de cercetare şi interpretare a observaţiilor, am făcut o recapitulare a

noţiunilor de bază ale algoritmilor genetici. Am făcut această recapitulare cu o

oarecare îndoială crezând că poate n-o să obţin rezultate mulţumitoare, dar totul

a fost invers – rezultatele obţinute m-au bucurat nu numai prin notele bune

obţinute, ci şi prin felul cum elevii au reuşit să analizeze problemele şi să scrie

programul respectiv.

În urma evaluării am înregistrat următoarele rezultate:

Note 9,10 7,8 5, 6 4

Nr.elevi 7 4 3 -

Procent 50% 28,5% 21,5% -

Clasa a XI- a C

Experimentul a continuat cu aplicaţia „Hello World!”, unde alături de metoda

descoperirii am folosit metoda problematizării şi brainstorming-ul.

Această schemă a lecţiei se obţine prin multe întrebări, angajând elevii la

răspunsuri şi observaţii. Pentru fiecare problemă elevii au trebuit să scrie

algoritmul şi după aceea programul. În timpul lucrului independent, observându-

i cum se descurcă m-am bucurat pentru că n-a fost nevoie să intervin în

rezolvarea problemelor. De altfel, notele obţinute reflectă corectitudinea

răspunsurilor.

Rezultatele au fost:

Note 9,10 7,8 5, 6 4

Nr.ele

vi 8 4 2 -

Proce 57,1 28,5 14,4 -

26


nt % % %

Clasa a XI-a C

La clasa experiment, a XI-a C, unde predarea s-a făcut apelând cât mai

mult la eforturile proprii ale elevilor şi unde am încercat introducerea unui nou

set de cunoştinţe în programare, suplimentar programei şcolare în curs, teoria

algoritmilor genetici, rezultatele obţinute au fost satisfăcătoare.

Până aici materia parcursă le-a dat posibilitatea de a avea cunoştinţe

despre teoria algoritmilor genetici, despre principalele instrumente cu care

operează această teorie cât şi despre unele exemple de transpunere în practică a

acestora.

Predarea acestei metode a fost însoţită de multe exemple de la simplu la

complex, elevii înţelegând utilizarea metodelor de lucru ale algoritmilor

genetici, în problemele care cer acest lucru. Fişa de lucru a fost în sistem grilă şi

rezultatele s-au prezentat astfel:

Note 10,

9

8,7 6,5 4

medi

a

Nr.el

evi 6 4 3 1

7.8

Clasa a XI-a C

Se observă cu uşurinţă că introducerea unor cunoştinţe suplimentare în

predarea informaticii la clasa a XI-a, dublată de aplicarea unor strategii didactice

moderne este cât se poate de oportună.

27


Am constatat nu numai că elevii sunt fascinaţi de teoria algoritmilor

genetici şi de posibilităţile sale de aplicare, dar ei chiar reuşesc să asimileze

noţiunile de bază şi deprinderile de utilizare a acestora în programare.

Extrapolând şi privind în ansamblu problema oportunităţii introducerii

teoriei algoritmilor genetici în liceu, ca extindere a curriculumului curent, pot

afirma că o deosebită eficienţă ar avea predarea acestora la clasele de excelenţă

de la nivel judeţean, unde elevii au un nivel ridicat de cunoştinţe de programare

şi le-ar fi de un real folos în concursurile şi olimpiadele şcolare.

Deducem că nu este de ajuns ca elevii să lucreze singuri pentru asimilarea

cunoştinţelor noi şi trebuie ca profesorul să fie bine pregătit, să acorde cât mai

mult timp de observaţie şi gândire elevilor, să-i îndrume în special pe cei mai

„greoi” în însuşirea cunoştinţelor, ţinând cont în acelaşi timp şi de elevii capabili

de performanţă.

Dacă facem o analiză comparativă vis a vis de stilurile de predare ( clasic

şi inovator ) aplicate clasei experiment de-a lungul lecţiilor, deducem că

rezultatele mult mai bune s-au obţinut aplicând metoda descoperirii, iar dacă

privim lucrurile mai profund, putem afirma că rezultatele mai bune s-au obţinut

printr-o contribuţie mai mare a elevilor (în cazul experimentului) şi mai mică din

partea profesorului, acesta fiind scopul ce se urmăreşte prin noua optică a

învăţământului.

Rezultatele clasei unde s-a făcut experimentul sunt:

Note

Aplicaţia

10,9

8,7

6,5

4

Media

“Maximizarea

unei functii” 7 3 2 2 7,64

“Expresia 7 4 2 1 7,71

28


aritmetica”

„OneMax” 8 3 3 - 7,85

Total 22 10 8 2 7,73

Procent 52,38% 23,8% 19,04% 4,78%

Metoda descoperirii nu am folosit-o numai în lecţiile de comunicare şi

recapitulare ci m-am gândit s-o folosesc şi în lecţiile de laborator, în aşa fel ca

elevii să fie puşi să lucreze singuri după discutarea problemelor şi în acelaşi

timp să poată să se autoevalueze. În acest scop am experimentat în continuare o

lecţie de laborator cu aplicaţia: „Ecuaţii diofantice”;

În desfăşurarea acestuia am avut în vedere ca premiza de la care trebuie să

pornim să fie delimitarea a ceea ce este util şi oportun să-i dăm elevului de-a

gata şi ce putem să-l lăsăm să descopere.

Folosind metoda descoperirii, elevii au raportat continuu cunoştinţele

teoretice referitoare la algoritmii genetici. Realizând transferul cunoştinţelor

rezultatul descoperirii a fost o nouă achiziţie informaţională şi operaţională. În

acest fel, ce s-a obţinut prin efort propriu nu a fost simpla întipărire în memorie,

ci a fost favorizată dezvoltarea aptitudinilor, deprinderilor de investigare,

explorative şi experimentale.

Prin realizarea lucrărilor, elevii au fost puşi în situaţia de a acţiona şi

gândi independent, rolul profesorului fiind acela de a îndruma activitatea

elevilor.

În acest sens, profesorul nu mai apare ca transmiţător de cunoştinţe, ci ca

organizator, îndrumător al învăţării.

29


Înainte de a prezenta elevilor problemele de care urmează să se ocupe am

pus la punct noţiunile utile în rezolvare. Astfel folosind metoda conversaţiei am

pus în evidenţă principiul de funcţionare al aplicaţiilor.

Am propus elevilor o alta problema care foloseste algoritmul genetic

clasic.

Problema:” Submulţimii de sumă dată”

Fiind dat un şir de N numere şi o sumă S, să se determine, folosind algoritmi

genetici, o submulţime din numerele date a căror sumă este S.

Datele de intrare ( N, S, şirul de numere ) se vor citi dintr-un fişier.

Rezolvare

Determinarea unei submulţimi de sumă dată este o problemă NP-

completă

Aceasta înseamnă că nu se ştie dacă există sau nu un algoritm de

complexitate polinomială pentru rezolvarea acestei probleme. Până în

prezent, algoritmii folosiţi au complexitate exponenţială, iar pentru anumite

cazuri particulare au complexitate pseudopolinomială. De exemplu, putem

rezolva rezonabil această problemă, dacă datele de intrare îndeplinesc

următoarele condiţii:

sunt cel mult 100 de numere naturale;

suma numerelor nu depăşeşte 500 (mai exact, produsul dintre numărul

numerelor şi suma acestora nu trebuie să depăşească dimensiunea maximă

admisă pentru alocarea

unei matrice (presupunem că aceasta este alocată static).

Dacă aceste condiţii ar fi îndeplinite am putea rezolva uşor această

problemă prin metoda programării dinamice, folosind un algoritm de

30


complexitate O(n ‡ S) ). Ínsă, dacă numerele nu ar fi întregi ci reale, sau

suma lor ar fi mai mare decât 500, sau diferenţele între ele ar fi mari etc.,

atunci algoritmul prin programare dinamică nu mai poate fi folosit.

Am enumerat aici doar cazurile importante, dar pot fi imaginate şi alte

dificultăţi.

Din aceste motive vom rezolva această problemă cu ajutorul unui

algoritm genetic. Va trebui să găsim o reprezentare a soluţiei şi, de

asemenea, o funcţie de fitness. Modul în care vom reprezenta soluţia ne este

dat chiar în enunţul problemei: se cere o submulţime a unei mulţimi M cu n

elemente. Deci, o soluţie a problemei este o submulţime. Vom codifica o

submulţime printr-un şir de lungime n care conţine doar valorile 0 şi 1. Dacă

o poziţie k va avea valoarea 1, atunci submulţimea respectivă va conţine

elementul k (al k-lea element din mulţimea N, iar dacă pe poziţia k este

valoarea 0, atunci elementul respectiv nu aparţine submulţimii. Această

reprezentare a unei submulţimi este specifică tipului set din Turbo Pascal.

Modul de calcul al fitness-ului (calităţii) unei soluţii (submulţimi) este

simplu. Calculăm suma elementelor submulţimii, iar fitness-ul va fi

diferenţa (în valoare absolută) dintre suma obţinută şi numărul dat S. Ín

aceste condiţii fitness-ul va trebui minimizat, deoarece noi dorim să

determinăm o submulţime pentru care suma elementelor este cât mai apropiată

de valoarea dată S.

Structura algoritmului genetic propus pentru rezolvarea acestei

probleme a fost prezentată mai sus. Vom folosi selecţia turnir pentru

obţinerea populaţiei intermediare. Operatorii genetici folosiţi sunt specifici

codificării binare (încrucişare cu un singur punct de tăietură, mutaţie cu

probabilitate pm=0.1).

31


Programul C corespunzător aplicaţiei propuse este următorul:

#include <stdio.h>

#include <stdlib>

#include <conio>

int a[50],n,s,dif,sol[50],k,temp[50];

void citire()

{

int i;

printf(“\n N=”);scanf(“%d”,&n)

printf(“\n s=”);scanf(“%d”,&s)

for(i=0;i<n;i++)

printf(“\n a[%d]=”,I);scanf(“%d”,&a[i]);

}

void calcul(int k;int t)

{

if (t==n-1){

if(k+a[n-1]<=s) {

k=k+a[n-1];

temp[n-1]=1;

}

if(s-k<dif){

dif=k;

for(i=0;i<n;i++)sol[i]=temp[i];

}

}

32


else{

if(k+a[t]<=s){

k=k+a[t];

temp[t]=1 ;

for(i=0 ;i<n;i++)calcul(k,I);

k=k-a[t] ;

}

}

void main()

{

citire();

dif=1000000 ;

k=0 ;

calcul(k,0);

printf(“\n submultimea este:”);

for(i=0;i<n;i++)

if(sol[i]=1) printf(“%d ”,a[i]);

printf(“\n diferenta minima este:%d”,dif);

}

33


Pentru aplicaţia Submulţime de sumă dată, rezultatele au fost destul de

mulţumitoare:

Note 10,9 8,7 6,5 medi

a

Nr.el

evi 7 4 3

8,57

Clasa a XI-a C

În continuare, la următoarele ore de laborator am ales o probleme cu un

grad de dificultate mai ridicat pentru a testa care sunt elevii capabili de

performanţă dar şi pentru a le da posibilitatea celor de nivel mediu să se

antreneze în condiţii similare cu cei care dispun de un potenţial de inteligenţă

mai ridicat. Este vorba de o problemă celebră, „Problema comis-voiajorului” pe

care ei au putut-o rezolva în clasa a X-a folosind metoda backtracking. Le-am

prezentat scripturile scrise în Matlab pentru o mai bună vizualizare a rezultatului

execuţiei şi pentru o mai bună discuţie asupra implementării acestei probleme

folosind algoritmi genetici.

Pe marginea programului prezentat am discutat cu elevii, antrenând întreg

colectivul, atât suportul teoretic al problemei, notiunile legate de teoria

grafurilor şi algoritmi genetici, dar şi principalele aspecte ce trebuie luate în

considerare atunci când se doreşte implementarea folosind algoritmi genetici.

Problema comis-voiajorului

Problema comis-voiajorului este o binecunoscută problemă NP-completă.

Comis-voiajorul trebuie să viziteze n oraşe şi încearcă să găsească drumul cel

mai scurt trecând prin fiecare oraş o singură dată şi revenind la punctul de

plecare. Problema are echivalentul matematic de găsire într-un graf a unui

34


circuit hamiltonian de cost minim. S-a demonstrat că o soluţie în timp

polinomial pentru această problemă sau pentru orice altă problemă NP-

completă, ar conduce la soluţii în timp polinomial pentru toate celelalte

probleme NP-complete. Cea mai importantă problemă nerezolvată din teoria

complexităţii este problema echivalenţei dintre clasele P şi NP. Opinia unanimă

a cercetătorilor este că rezolvarea unei probleme NP-complete în timp

polinomial este imposibilă şi în consecinţă P şi NP sunt diferite, dar acest lucru

nu a putut fi demonstrat deocamdată.

O problemă NP-completă nu poate fi aşadar rezolvată într-un timp

rezonabil decât prin folosirea unor algoritmi nedeterminişti. Există şi aici din

păcate riscul de a găsi un minim local, apropiat mai mult sau mai puţin ca

valoare de minimul global. De multe ori soluţia găsită este considerată

acceptabilă şi declarăm problema rezolvată. În alte situaţii însă, incertitudinea

asupra soluţiei corecte poate constitui un motiv serios de îngrijorare.

Problema a fost rezolvată folosind algoritmi genetici iar soluţiile obţinute

depăşesc în cel mai rău caz cu 7% lungimea drumului optim, după unii autori,

deşi după alţii eroarea poate ajunge chiar până la 25%.

Specificul problemei a dus la crearea unor noi modalităţi de reprezentare a

cromozomilor şi a operatorilor de încrucişare. Cele n oraşe se numerotează într-

o anumită ordine folosind primele n numere naturale. Un cromozom sau o

soluţie a problemei reprezintă un drum închis care trece prin toate oraşele date.

Dacă n=10 de exemplu, o soluţie posibilă ar putea fi S1=(5, 7, 8, 2, 4, 10, 9, 6, 3,

1 ).

Există mai mulţi operatori de încrucişare. Unul dintre cei mai cunoscuţi

este operatorul PMX (Partially matched crossover ). Se foloseşte de fapt o

încrucişare în două puncte, dar în acest caz, spre deosebire de codificarea binară,

este interzisă repetarea unui oraş de două ori în structura cromozomului. Ca

atare, atunci când apare o astfel de situaţie, oraşul respectiv este înlocuit cu

35


oraşul care se găseşte pe aceeaşi poziţie din cromozomul celuilalt părinte. Dacă

acceptăm că oraşele sunt nodurile unui graf, atunci etapele parcurse de acest

operator sunt următoarele:

Se generează o listă de drumuri, în care se trec toate legăturile existente

dintre nodurile cromozomilor părinţi, luate două câte două. Pentru fiecare

nod se construieşte câte o sublistă care conţine nodurile adiacente lui.

Se alege aleator ca nod de plecare primul nod al unuia din cei doi părinţi.

Nodul de plecare este considerat nod actual şi se marchează în toate

sublistele construite pentru a evita alegerea lui din nou în etapele

următoare.

Se stabileşte care din nodurile următoare din sublista nodului actual au

mai puţine noduri distincte în sublistele lor şi nodul respectiv se alege ca

nod actual. Dacă există mai multe alternative, se alege aleator una dintre

ele şi se face marcajul nodului actual în toate sublistele construite.

Dacă în sublista nodului actual nu mai există noduri disponibile, atunci se

alege aleator din mulţimea nodurilor, unul care nu este marcat.

Selecţia celor mai adaptaţi cromozomi din populaţie în vederea

încrucişării se face proporţional, cu un algoritm de tip ruletă. Mutaţia este şi aici

foarte importantă. Există două metode folosite: o mutaţie mai slabă, prin

interschimbarea poziţiei a două oraşe şi o mutaţie mai dură, prin interschimbarea

sensului de parcurgere a unui număr de oraşe alese aleator.

În continuare este prezentat codul sursă în limbajul C care implementează

algoritmul descris mai sus.

#include <stdio.h>

/* Numarul maxim de orase. */

#define N_MAX 30

/* Constanta care se foloseste ca valoare

36


de initializare la cautarea minimului. */

#define MINIM 10000

/* Numarul de orase. */

int n;

/* Matricea distantelor dintre orase. */

int d[N_MAX][N_MAX];

/* Drumul comis voiajorului. Contine

indicii oraselor in ordinea in care

sunt ele parcurse. */

int drum[N_MAX];

/* Vector care memoreaza care orase au

fost vizitate. vizitat[k] va fi 1 daca

orasul k a fost vizitat, 0 altfel. */

int vizitat[N_MAX];

/* Functie care alege urmatorul element care

sa fie prelucrat din multimea oraselor.

Primeste ca parametru ultimul oras care

a fost vizitat, si returneaza urmatorul

oras care sa fie vizitat precum si lungimea

drumului catre acesta. */

void alege(int ultimul, int *min, int *j_min)

{

int j;

/* Cautam drumul minim de la ultimul

oras pana la orasele neparcurse inca. */

*min = MINIM;

*j_min = -1;

for (j=0; j<n; j++)

if (!vizitat[j])

{

if (d[ultimul][j] < *min)

{

*min = d[ultimul][j];

*j_min = j;

}

}

}

int main(void)

{

FILE *fin;

int i, j;

int count, cost, min, j_min;

37


/* Deschidem fisierul pentru citire in mod text. */

fin = fopen("comis.in", "rt");

if (!fin)

{

printf("Eroare: nu pot deschide fisierul.\n");

return -1;

}

/* Citim datele din fisier. */

fscanf(fin, "%d", &n);

for (i=0; i<n; i++)

for (j=0; j<n; j++)

fscanf(fin, "%d", &(d[i][j]));

/* Afisam pe ecran datele preluate din fisier. */

printf("Avem %d orase.\n", n);

printf("Distantele dintre orase sunt:\n");

for (i=0; i<n; i++)

{

for (j=0; j<n; j++)

printf("%d ", d[i][j]);

printf("\n");

}

printf("\n");

/* Initial nici un oras nu este vizitat. */

for (i=0; i<n; i++)

vizitat[i] = 0;

/* Primul oras vizitat este cel cu numarul "0".

Costul total este zero deocamdata. */

drum[0] = 0;

vizitat[0] = 1;

count = 1;

cost = 0;

/* Parcurgem restul de n-1 orase. */

for (i=0; i<n-1; i++)

{

/* Alegem urmatorul oras care sa fie vizitat. */

alege(drum[count-1], &min, &j_min);

/* Parcurgem drumul minim gasit si vizitam

un nou oras. */

printf("Am ales drumul (%d, %d) de cost %d.\n",

drum[count-1], j_min, min);

drum[count] = j_min;

vizitat[j_min] = 1;

count++;

cost += min;

38


}

/* Parcurgem drumul de la ultimul oras vizitat

catre primul oras si actualizam costul

total. */

cost += d[drum[n-1]][0];

/* Afisam drumul parcurs. */

printf("\nDrumul are costul %d si este:\n", cost);

for (i=0; i<n; i++)

printf("%d ", drum[i]);

printf("0\n");

return 0;

}

Figura 1: Reţea de oraşe pentru problema comis-voiajorului

Fişierul cu date de intrare pentru reţeaua de oraşe din figura 1 este următorul:

4

0 4 2 7

4 0 2 1

2 2 0 1

7 1 1 0

Pentru această aplicaţie, rezultatele au fost destul de mulţumitoare, ţinând

cont de gradul de dificultate mai ridicat al aplicaţiei.:

Note 10,9 8,7 6,5 medi

a

39


Nr.el

evi 6 5 3

8,28

Clasa a XI-a C

Din experimentarea lecţiilor de laborator prin metoda descoperirii, pot să

afirm că se obţin rezultate mult mai bune decât printr-o predare clasică şi în

acest fel elevii sunt familiarizaţi cu munca independentă, de cercetare şi

generalizarea cunoştinţelor.

În lecţiile de predare – învăţare am folosit multe metode, dar am pus

accent în acest experiment pe metoda descoperirii. Alături de aceasta am folosit

metoda problematizării, mai ales după ce elevii au prins puţină experienţă.

Metoda problematizării a fost acceptată cu uşurinţă de elevi deoarece ea

foloseşte experienţa anterioară în rezolvarea problemelor şi situaţiilor problemă,

prin aceasta elevii şi-au completat fondul de cunoştinţe, prin efort personal de

rezolvare.

Instruirea problematizată au desfăşurat-o dirijat şi acest model având

următoarele caracteristici împărţind activitatea în două profesor – elev:

Profesor Elevi

oferă probleme de rezolvare;

oferă elemente de sprijin pentru

rezolvare;

oferă elemente pentru alcătuirea

unui plan de rezolvare;

dirijează activitatea de

rezolvare;

dirijează interpretarea

rezultatelor;

consemnează datele problemei;

identifică elementele de sprijin

oferite;

alcătuiesc planul de rezolvare;

efectuează investigaţii;

interpretează rezultatele;

formulează concluziile;

formulează noile cunoştinţe

obţinute.

40


dirijează formularea

concluziilor;

stimulează identificarea

elementelor noi prezentate în

concluzie.

Măsuri :

Metodele activ-participative, să fie utilizate intens, mai ales la orele de

“Aplicaţii practice”.

În afara manualului elevii mai au nevoie şi de cărţi de specialitate, cu

aplicaţii practice.

Conştientizarea faptului că lucrul cu calculatorul trebuie suplimentat acasă

sau în alte împrejurări (colegi, firme, etc.).

41


CAPITOLUL V

CONCLUZII. PROPUNERI METODICE

Funcţia principală a proiectului de tehnologie didactică este de a orienta

desfăşurarea lecţiei astfel încât învăţarea să se realizeze în condiţiile cele mai

adecvate iar resursele didactice să fie valorificate corespunzător în funcţie de

potenţialul de care dispun elevii.

Proiectarea instruirii se poate desfăşura într-un număr mare de variante. În

desfăşurarea unei lecţii profesorul se poate întâlni cu diverse evenimente de

instruire pentru care trebuie să găseasca soluţii imediate, adaptând schema cadru

a proiectului de tehnologie didactică propus la noile condiţii cu care se

confruntă.

Aceste situaţii pot fi generate de reacţiile elevilor în procesul de instruire,

de condiţiile tehnice necesare pentru aplicarea proiectului şi de eventuale

modificări ale timpului de desfăşurare.

În urma experimentării acestor lecţii de predare-învăţare-evaluare folosind

metodele activ-participative: problematizarea, algoritmizarea, descoperirea,

brainstorming-ul la disciplina informatică se desprind următoarele concluzii şi

propuneri metodice:

La aplicaţia Convergenţa către un model, la clasa a XI-a D, deşi la

începutul experimentului rezultatele au fost mai puţin îmbucurătoare, pe

parcursul experimentului s-a observat o creştere a notelor de 7, 8, 9 şi

scăderea celor sub limită şi mediocre, datorită creşterii ponderii predării

formative în detrimentul celei clasice

La obiectul aplicaţii practice de laborator, rezultatele au fost mai bune,

majoritatea notelor fiind între 7 – 10;

42


Şi mai bune rezultate au fost obţinute în rezolvarea aplicaţiilor

Maximizarea unei functii, Expesia aritmetica, ONEMAX, „Hello World”,

Submulţime de sumă dată unde la aproape toate lecţiile experimentale

media pe clasă a fost peste 7;

Rezultatele bune obţinute, mă îndreptăţesc să afirm că, privind în

profunzime avantajele acestei metode, în ceea ce priveşte raportul dintre

învăţământ şi predare, majoritatea elevilor participanţi la experiment au

devenit participanţi activi în acest proces, au reuşit să realizeze informaţia

şi nu s-o imagineze de-a gata, au ajuns să poată observa esenţialul, să facă

analize şi sinteze, comparaţii, ridicându-se pe această cale la generalizări

şi achiziţionări de noi cunoştinţe prin eforturi proprii;

Pentru obţinerea rezultatelor dorite, am dedus că aplicarea acestei metode

cere din partea profesorului o bună pregătire atât ştiinţifică cât şi

metodică, o urmărire sistematică a rezultatelor obţinute;

Alegerea lecţiilor pentru a fi predate prin metode active să nu se facă în

mod pripit, ci încă de la începutul semestrului pentru a avea timp de

pregătire a lor;

Metodele active se pot folosi atât la lecţiile de comunicare, cât şi la lecţiile

de fixare şi consolidare, de sistematizare, de evaluare şi nu în ultimul rând

la lecţiile de laborator;

Metodele active trebuie folosite în mod gradat – progresiv: începute de

profesor la clasa a IX-a, dar nu chiar de la primele lecţii, ci numai după ce

elevul a fost iniţiat asupra modului de lucru, continuate în clasele a X-a, a

XI-a, a XII-a, dar pe fiecare treaptă de clasă, pretenţiile care stau în faţa

elevilor sunt mai mari, în sensul că observaţiile lor trebuie să ducă la

generalizări şi abstractizări;

Folosirea acestei metode cere un bogat material didactic pentru a-i da

posibilitatea elevului să-l prelucreze şi să afle adevărurile cerute de noi;

43


Oricărei lecţii predate prin metoda descoperirii, trebuie să i se rezerve 5 –

10 –12 minute pentru clarificarea răspunsurilor eronate, notarea corectă în

caiete a schiţei lecţiei, concluziilor. Omiterea acestei etape de încheiere

duce la nesistematizarea cunoştinţelor elevilor şi rezultatele lor vor fi

nedorite;

După părerea mea trebuie să dăm elevilor să „descopere” numai ce pot ei

din lecţie, nicidecum o întreagă lecţie, numai partea din lecţie care se

pretează pentru descoperire. Supraaprecierea folosirii aceste metode duce

la insuccese în munca elevului şi a noastră ca profesori;

Metodele active se pot folosi în orice etapă a lecţiei. Rezultatele sunt bune

când acestea se folosesc îmbinate cu alte metode, fie formative, fie

clasice, niciodată singure;

O latură importantă de care trebuie să ţinem seama prin folosirea acestor

metode este şi raportul (relaţiile) dintre profesori şi elevi, raport care se

modifică în sensul că devin relaţii de colaborare, de cooperare, mai

deschise, sincere, mai apreciate. Aceste relaţii noi îi fac pe elevi să capete

încredere în ei, în forţele lor, în special elevii timizi, să iubească obiectul

informatică. Deci, din aceste relaţii au de câştigat atât elevii, cât şi

profesorul;

O lecţie bună este cea în care noi profesorii antrenăm la activitate pe toţi

elevii clasei. Particularităţile individuale ale elevilor fac ca aceştia să nu

lucreze în acelaşi ritm, să nu obţină aceleaşi rezultate. Trebuie să găsim

mijloacele potrivite de a stimula pe elevii care rămân în urmă iar munca

îndrumată direct să fie alternată cu cea independentă. Astfel, într-o parte a

lecţiei aceasta se poate desfăşura frontal, iar în alta se obţin rezultate mai

bune când este organizată pe echipe (grupe). A acorda fiecăruia dintre

aceste moduri de activitate locul potrivit în organizarea lecţiei înseamnă a

asigura o eficienţă sporită a lecţiilor, întrucât fiecare dintre aceste moduri

de activitate îşi aduce contribuţia sa specifică la educarea elevilor;

44


Reuşita unei lecţii depinde şi de modul cum este organizată din punct de

vedere metodic. Folosirea la timp a materialului didactic, trecerea de la un

moment la altul al ei după cerinţele desfăşurării logice şi după

posibilităţile de asimilare ale elevilor, respectarea principiilor didactice în

raport cu vârsta elevilor şi cu conţinutul materialului didactic pot asigura

realizarea unei lecţii valoroase. Pentru a obţine rezultate mai bune în

organizarea metodică a lecţiei, este necesar ca fiecărei etape să i se

rezerve o durată potrivită. Chestionarea elevilor, de exemplu, să nu

răpească prea mult timp, încât tema nouă să fie expediată. O lecţie bine

organizată are densitate, pe tot parcursul ei elevii fiind activi. Într-o

asemenea lecţie nimic nu se face la întâmplare. După o astfel de lecţie,

elevii îşi dau seama că au realizat un progres; au dobândit cunoştinţe noi,

şi-au consolidat unele priceperi deprinderi, înţeleg mai corect şi mai

profund fenomenele respective. O lecţie bine organizată din punct de

vedere metodic este o verigă dintr-un lanţ, este deci o continuare a

lecţiilor anterioare şi o pregătire pentru cele care se vor preda ulterior;

Ţinând cont de aceste observaţii (concluzii), menţionate, deduse din

experimentul pe care l-am efectuat, afirm încă o dată că folosirea acestei

metode prin avantajele pe care le pun la dispoziţia elevilor trebuie extinsă

în predarea lecţiilor de informatică, contribuind alături de celelalte metode

la formarea unor oameni care să facă faţă cerinţelor de viitor;

Tot pe baza observaţiilor deduse din experiment, pot afirma că teoria

algoritmilor genetici poate fi inclusă cu succes în predarea informaticii la

clasa a XI-a, ca modalitate de extindere a curriculumului deja existent. O

şi mai mare oportunitate apare atunci când aceasta este oferită, împreună

cu depinderile de lucru necesare, elevilor capabili de performanţă;

45


ANEXE

PROIECT DIDACTIC

Disciplina : Informatică ;

Clasa : a XI-a;

Profesor :

Unitatea de învăţare : Algoritmi genetici;

Tema : Algoritmi genetici. Metode de selecţie

Durata: 3 ore;

Tip de lecţie: comunicare şi însuşire de noi cunoştiinţe;

Locul de desfăşurare : Laborator;

Obiective educaţionale :

Obiective cognitive :

- să dovedească trăinicia noţiunilor dobândite la disciplina respectivă, în

capitolul “Algoritmi genetici” ;

- să utilizeze corect metodele de selecţie a cromozomilor în programele

scrise folosind algoritmi genetici;

- să identifice problemele care se rezolvă cu algoritmi genetici.

Obiective afective :

- să argumenteze corect alegerea unei variante;

- să aprecieze corect soluţiile oferite de ceilalţi membri ai grupei;

- să se autoevalueze în raport cu obiectivele şi cu clasa;

Obiective psihomotorii :

- să utilizeze corect noţiunile teoretice însuşite

- să implementeze algoritmi de selecţie utilizând limbajul C++ în

programe ce utilizează algoritmi genetici.

46


Obiective operaţionale:

O1 : Să-şi însuşească modul de funcţionare al metodelor se selecţie a

cromozomilor în algoritmii genetici şi să simuleze algoritmi pentru diverse

exemple;

O2: Să analizeze corect fiecare problemă şi să aplice corect metoda.

Strategii didactice :

Principii didactice :

principiul participării şi învăţării active ;

principiul asigurării progresului gradat al performanţei ;

principiul conexiunii inverse.

Metode de învăţământ :

metode de comunicare orală : expunere, conversaţie, problematizare

metode de acţiune : exerciţiul, învăţare prin descoperire

Procedee de instruire :

explicaţia în etapa de comunicare

învăţarea prin descoperire, prin rezolvarea de probleme;

problematizarea prin crearea situaţiilor problemă;

conversaţia de consolidare în etapa de fixare a cunoştiinţelor ;

Forme de organizare : frontală şi individuală ;

Forme de dirijare a învăţării : dirijată de profesor sau independentă ;

Resurse materiale :

material bibliografic : Michalewicz, Z. « Genetic Algorithms+Data

Structures =Evolution Programs «. Springer-Verlag, Berlin, 1994

(second edition).

fişe de lucru

planşe

calculator

47


Metode de evaluare :

evaluare iniţială : întrebări orale

set de aplicaţii

Desfăşurarea lecţiei :

Moment organizatoric :

pregătirea lecţei :

întocmirea proiectului didactic

pregătirea setului de întrebări

pregătirea setului de aplicaţii

pregătirea temei

organizarea şi pregătirea clasei :

verificarea frecvenţei

captarea atenţiei clasei :

anunţarea subiectului pentru tema respectivă

anunţarea obiectivelor urmărite

anunţarea modului de desfăşurare a activităţii

Reactualizarea cunoştinţelor :

Se realizează un set de întrebări pentru reactualizarea cunoştinţelor

teoretice, ca mai jos, ţinând cont de faptul că până acum am studiat metode de

codificare şi construcţie a funcţiei de adecvare pe diferite exemple.

Tabel nr. 1

Întrebare Răspuns aşteptat

Daţi câteva exemple

de codificare a

cromozomilor în

cadrul unui algoritm

Codificare binară, codificare Gray,

codificare reală, codificare specifică

48


genetic

Care este funcţia de

adecvare pentru

problema

submulţimii?

admisibilă estenu s dacă

admisibilă este s dacă

)(

1

1n

i

ii

n

i

ii

sw

sw

sF

Dintre două soluţii

admisibile, care este

mai bună vis a vis de

funcţia de adecvare?

Dintre două soluţii admisibile este mai bună

cea care are adecvarea mai mare

Evaluarea în etapa de reactualizare se realizează frontal.

Comunicarea noilor cunoştinţe :

Exemple de probleme în care se aplică algoritmi genetici şi implicit metode de

selecţie a cromozomilor

Elevii cunosc deja modalităţile de reprezentare a cromozomilor precum şi

noţiuni de construire a funcţiei de adecvare în problemele rezolvate cu algoritmi

genetici.

Exemplul 1:

Folosind un algoritm genetic sa se maximizeze o functie data.

Exemplul 2:


binare.

49


Prezentarea metodelor de selecţie a cromozomilor într-un algoritm genetic.

Dirijarea învăţării pentru obţinerea performanţei :

Tabel nr. 1

ITEM Răspuns aşteptat

Interpretarea corectă a semnificaţiei

utilizării unei metode de selecţie adecvate

în cadrul unui algoritm genetic

Prin discuţii elevii realizează acest

obiectiv

Asimilarea principiilor de funcţionare a

principalelor metode de selecţie prezentate

şi identificare metodei de selecţie optime

rezolvării problemei.

Elevii implementează metoda de

selecţie corespunzătoare rezolvării

problemei şi identifică celelalte

componente ale algoritmului

genetic implementat de problemă

Fişa după care se desfăşoară lecţia:

Tabel nr. 2

Funcţii exercitate de

evenimentul

instrucţional

Activităţi ale lecţiei Metode

Reactualizarea

cunoştinţelor

Se face prin chestionarul

cu întrebări conform

tabelului nr. 1

Conversaţia de fixare

Intensificarea reţinerii

şi asigurării

transferului de

informaţii

Se face cu testul propus

conform tabelului nr. 1

Exerciţiul introductiv;

conversaţia de

consolidare.

Obţinerea performanţei Se realizează cu setul de

exemple introductive,

prin care se urmăreşte

Problematizarea,

exerciţiul de consolidare.

50


tipul problemelor pentru

care se aplică fiecare din

metodele de selecţie

prezentate apoi se

continuă cu

implementarea specifică

metodei de selecţie alese.

Evaluarea

performanţei

Se propune o aplicaţie

care se rezolvă cu

algoritmi genetici şi care

utilizează una din

metodele de selecţie

studiate, urmărindu-se

scrierea corectă a

programului

Problematizarea,

brainstorming

În prima etapă le-am prezentat noţiunile teoretice introductive legate de

metodele de selecţie în algoritmii genetici, continuând cu descrierea principiilor

si a modului de funcţionare a fiecărei metode în parte.

Selecţia are ca scop determinarea populaţiei intermediare ce conţine

părinţii care vor fi supuşi operatorilor genetici de încrucişare şi mutaţie precum

şi determinarea elementelor ce vor face parte din generaţia următoare. Criteriul

de selecţie se bazează pe gradul de adecvare al configuraţiei la mediu, exprimat

prin valoarea funcţiei de adecvare ( fitness-ului ).

Nu este obligatoriu ca atât părinţii cât şi supravieţuitorii să fie determinaţi

prin selecţie, fiind posibil ca aceasta să fie folosită într-o singură etapă. De

exemplu, toţi indivizii populaţiei curente sunt potenţiali părinţi dar după

încrucişare şi mutaţie doar cei determinaţi prin procesul de selecţie vor

supravieţui. Pe de altă parte este posibil ca părinţi să fie doar indivizii selectaţi

51


iar totţi cei generaţi prin încrucişare şi mutaţie să fie transferaţi în noua

generaţie.

Procesul de selecţie nu depinde de modul de codificare a elementelor

populaţiei fiind însă legat de funcţia de adecvare.

Există două clase principale de metode de selecţie:

Metode deterministe. Se caracterizează prin faptul că elementele cu grad

mai mare de adecvare sunt întotdeauna selectate în defavoarea celor cu un

grad mai mic de adecvare. Un exemplu de această metodă este selecţia

prin trunchiere.

Metode aleatoare. Se caracterizează prin faptul că în procesul de selecţie

intervin elemente aleatoare. Variantele cel mai frecvent întâlnite se

bazează pe stabilirea unor probabilităţi de selecţie care depind de gradul

de adecvare. În felul acesta elementele cu grad mai mare de adecvare au

şanse mai mari de a fi selectate, astfel că numărul de copii ale acestora

este mai mare decât al celor cu grad mai mic de adecvare. Metodele cele

mai reprezentative sunt selecţia proporţională, selecţia pe baza

rangurilor şi selecţia de tip turneu.

Primul pas este atribuirea fitnesss-ului

Fiecare individ din fondul de selecţie primeşte o probabilitate de

reproducere în funcţie de propria valoare obiectiv cât şi de valoarea

obiectiv a celorlalţi indivizi din câmpul de selecţie

Acest fitness este utilizat ulterior pentru pasul actual de selecţie

Pentru asigurarea feedback-ului şi evaluarea performanţei se

propune spre rezolvare problema ONEMAX.


binare.

52


Se consideră {0,1}L

mulţimea şirurilor binare de lungime L. Pentru un şir s din

această mulţime notăm cu s1 numărul de componente egale cu 1 ale şirului. Fie

N un număr natural nenul mai mic decât L, şi f o funcţie care asociază fiecărui

şir s o valoare egală cu s1 dacă s1 nu este multiplu de N, şi 2s1 în caz contrar. Să

se găsească un şir s* care maximizează f. Se va lua valorile L=10 şi N=3.

Exemplu de utilizare :

Program ce constă în maximizarea unei funcţii definite f(s)=s1 Se deschide

fişierul ex1.prj din Borland şi se modifică fişierul ex1.c. Fişierul rezultat va avea

forma :

#include<stdio.h>

#include”sugar.h”

int evaluate(SuChromosome*chrom,double*fitness);

main( int argc,char*arvg[] )

{

SuaEvaluationFunction=evaluate;

SuRun( “ex1.cfg”,argc,argv );

}

int evaluate (SuChromosome*chrom,double*fitness);

{

int i;

int N=3;

int count=0;

double result=0.0;

for( i=0; i<chrom->length;++i )

count+=SuGetBit( chrom->string,i );

if(count%N==0)result=2*count;

else result =count;

*fitness=result

return 0;

}

53


Modificările au fost făcute în funcţia de evaluare. Pentru a seta

parametrii algoritmului genetic am schimbat liniile fişierului ex1.cfg după cum

urmează :

generation 10

population 10

length 10

în

generation 100

population 50

length 10

(întâmplător, lungimea şirului binar era predefinită ca 10, în general ea va trebui

modificată).

Rularea algoritmului se face prin comanda ex1.exe. În urma rulării

programul obţine valoarea 1101111111, una dintre cele care maximizează f.

Problema „Maximizarea functiei” va rămâne ca tema de studiu pentru ora

următoare.

54


PROIECT DIDACTIC

Disciplina : Informatică ;

Clasa : a XI-a;

Profesor :

Unitatea de învăţare : Algoritmi genetici;

Tema : Aplicaţia Submulţime de sumă dată – impementare folosind algoritmi

genetici

Tip de lecţie: formare şi consolidare a deprinderilor şi priceperilor

Locul de desfăşurare : Laboratorul de informatică;

Nivelul iniţial al clasei

Elevii şi-au însuşit toate noţiunile teoretice legate de algoritmii genetici,

Elevii utilizează corect noţiunile învăţate în scrierea programelor ;

Elevii au un nivel de cunoştinţe corespunzător programei şi de utilizare a

calculatorului ;

Obiectiv cadru : realizarea de programe utilizând principiile de funcţionare ale

algoritmilor genetici ;

Obiective de referinţă :

Să recunoască situaţiile care impun folosirea algoritmilor genetici precum

şi alegerea adecvată a principalilor operatori genetici, a metodelor de

reprezentare optime;

Să urmărească etepele de realizarea a unei aplicaţii ;

Să depaneze programele în cazul unor eventuale erori;

Obiective educaţionale :

Obiective cognitive :

- să dovedească trăinicia noţiunilor dobândite la disciplina respectivă, în

capitolul “Algoritmi genetici” ;

55


- să utilizeze corect definiţiile teoretice însuşite referitoare la aceast tip

de algoritmi;

- să identifice corect situaţiile în care alegerea unei metode de

reprezentare prezintă avantaje în raport cu alta ;

- să analizeze modul de funcţionare al programelor ;

Obiective afective :

- să aleagă corect situaţiile în care se folosesc algoritmi genetici;

- să argumenteze avantajele utilizării algoritmilor genetici în rezolvarea

problemelor propuse;

- să aprecieze corect soluţiile oferite de colegi;

- să se implice cu plăcere şi interes la toate etapele lecţiei;

- să se bucure de rezultatele muncii depuse;

Obiective psihomotorii :

- Să-şi formeze deprinderi de lucru specifice temei de studiu;

- Să-şi dezvolte gândirea logică, capacitatea de generalizare şi

problematizare;

Obiective operaţionale:

Să-şi însuşească modul de funcţionare al algoritmilor genetici şi să

simuleze pentru diverse exemple;

Să analizeze corect fiecare problemă şi să aplice corespunzător metodele

de reprezentare a cromozomilor şi operatorii genetici .

Strategii didactice :

Principii didactice :

principiul participării şi învăţării active ;

principiul asigurării progresului gradat al performanţei ;

principiul conexiunii inverse.

Metode de învăţământ :

Conversaţia ;

56


Explicaţia ;

Exerciţiul ;

Problematizarea ;

Algoritmizarea ;

Procedee de instruire :

conversaţia de consolidare ;

problematizarea prin crearea situaţiilor problemă;

exerciţii de consolidare ;

Forme de organizare :

frontală ;

individuală ;

pe grupe ;

Forme de dirijare a învăţării : dirijată de profesor sau prin materiale

didactice şi independentă ;

Resurse materiale :

material bibliografic : Davis, L. « Handbook of Genetic Algorithms

« , Van Nostrand Reinhold, 1991

fişe de lucru ;

set de aplicaţii ;

calculator ;

Metode de evaluare :

evaluare sumativă ;

evaluare continuă pe parcursul lecţiei (fişă de lucru şi calculator) ;

evaluare formativă ;

Desfăşurarea lecţiei :

Moment organizatoric :

pregătirea lecţei :

întocmirea proiectului didactic

57


pregătirea setului de întrebări

pregătirea setului de aplicaţii

pregătirea temei

organizarea şi pregătirea clasei :

verificarea frecvenţei

verificarea cantitativă şi calitativă a temei

verificarea existenţei şi operaţionalităţii resurselor

materiale

captarea atenţiei clasei :

anunţarea subiectului pentru tema respectivă

anunţarea obiectivelor urmărite

anunţarea modului de desfăşurare a activităţii

Reactualizarea cunoştinţelor :

Se realizează un set de întrebări pentru reactualizarea

cunoştinţelor teoretice, ca mai jos:

Tabel nr. 1

Întrebare

Răspuns aşteptat

Definiţi noţiunea de

cromozom

Este o mulţime ordonată de elemente, numite gene ale

căror valori determină caracteristicile unui individ. În

genetică, poziţiile pe care se afla genele în cadrul

cromozomului se numesc loci, iar valorile pe care le

poate lua se numesc alele. În calculul evolutiv

cromozomii sunt vectori ce conţin codificarea unei soluţii

potenţiale şi sunt numiţi indivizi sau configuraţii. Astfel,

genele nu sunt altceva decât elementele acestor vectori.

Definiţi noţiunea de O populaţie este constituită din indivizi care trăiesc intr-

58


populaţie un mediu la care trebuie să se adapteze. În calculul

evolutiv, un individ este de cele mai multe ori identificat

cu un cromozom şi reprezintă un element din spaţiul de

căutare asociat problemei de rezolvat.

Ce presupune si

care este rolul

reproducerii în

cadrul unui

algoritm genetic?

Este procesul prin care, pornind de la populaţia curentă se

construieşte o nouă populaţie. Indivizii noii populaţii (

generaţii ) moştenesc caracteristici de la precursorii lor (

părinţi ) dar pot dobândi şi caracteristici noi ca urmare a

unor procese de mutaţie care au un caracter întâmplător.

În cazul în care în procesul de reproducere intervin cel

puţin doi părinţi caracteristicile moştenite ale urmaşului (

fiu ) se obţin prin combinarea ( încrucişarea )

caracteristicilor părinţilor. În calculul evolutiv acest

proces este simulat prin mecanismele de încrucişare (

recombinare ) şi mutaţie. Aceste mecanisme asigură

explorarea spaţiului soluţiilor prin descoperirea de noi

configuraţii.

59


Fişa după care se desfăşoară lecţia:

Tabel nr. 2

Funcţii exercitate de

evenimentul

instrucţional

Activităţi ale lecţiei Metode

Reactualizarea

cunoştinţelor

Se face prin chestionarul

cu întrebări conform

tabelului nr. 1

Conversaţia de fixare

Evaluarea performanţei Se propune o aplicaţie

care se rezolvă prin

algoritmi genetici,

urmărindu-se scrierea

corectă a programului

Problematizarea,

brainstorming

Pentru asigurarea feedback-ului şi evaluarea performanţei se propune

spre rezolvare problema Submulţimii de sumă dată.

„Problema Submulţimii de sumă dată” - Enunţ

Fiind dat un şir de N numere şi o sumă S, să se determine, folosind

algoritmi genetici, o submulţime din numerele date a căror sumă este S.

Datele de intrare ( N, S, şirul de numere ) se vor citi dintr-un fişier.

Rezolvare

Determinarea unei submulţimi de sumă dată este o problemă NP-

completă

Aceasta înseamnă că nu se ştie dacă există sau nu un algoritm de

complexitate polinomială pentru rezolvarea acestei probleme. Până în

60


prezent, algoritmii folosiţi au complexitate exponenţială, iar pentru anumite

cazuri particulare au complexitate pseudopolinomială. De exemplu, putem

rezolva rezonabil această problemă, dacă datele de intrare îndeplinesc

următoarele condiţii:

sunt cel mult 100 de numere naturale;

suma numerelor nu depăşeşte 500 (mai exact, produsul dintre numărul

numerelor şi suma acestora nu trebuie să depăşească dimensiunea maximă

admisă pentru alocarea

unei matrice (presupunem că aceasta este alocată static).

Dacă aceste condiţii ar fi îndeplinite am putea rezolva uşor această

problemă prin metoda programării dinamice, folosind un algoritm de

complexitate O(n ‡ S) ). Ínsă, dacă numerele nu ar fi întregi ci reale, sau

suma lor ar fi mai mare decât 500, sau diferenţele între ele ar fi mari etc.,

atunci algoritmul prin programare dinamică nu mai poate fi folosit.

Am enumerat aici doar cazurile importante, dar pot fi imaginate şi alte

dificultăţi.

Din aceste motive vom rezolva această problemă cu ajutorul unui

algoritm genetic. Va trebui să găsim o reprezentare a soluţiei şi, de

asemenea, o funcţie de fitness. Modul în care vom reprezenta soluţia ne este

dat chiar în enunţul problemei: se cere o submulţime a unei mulţimi M cu n

elemente. Deci, o soluţie a problemei este o submulţime. Vom codifica o

submulţime printr-un şir de lungime n care conţine doar valorile 0 şi 1. Dacă

o poziţie k va avea valoarea 1, atunci submulţimea respectivă va conţine

elementul Mk (al k-lea element din mulţimea M), iar dacă pe poziţia k este

valoarea 0, atunci elementul respectiv nu aparţine submulţimii. Această

reprezentare a unei submulţimi este specifică tipului set din Turbo Pascal.

Modul de calcul al fitness-ului (calităţii) unei soluţii (submulţimi) este

61


simplu. Calculăm suma elementelor submulţimii, iar fitness-ul va fi

diferenţa (în valoare absolută) dintre suma obţinută şi numărul dat S. Ín

aceste condiţii fitness-ul va trebui minimizat, deoarece noi dorim să

determinăm o submulţime pentru care suma elementelor este cât mai apropiată

de valoarea dată S.

Structura algoritmului genetic propus pentru rezolvarea acestei

probleme a fost prezentată mai sus. Vom folosi selecţia turnir pentru

obţinerea populaţiei intermediare. Operatorii genetici folosiţi sunt specifici

codificării binare (încrucişare cu un singur punct de tăietură, mutaţie cu

probabilitate pm=0.1).

Programul C corespunzător aplicaţiei propuse este următorul:

#include <stdio.h>

#include <stdlib>

#include <conio>

int a[50],n,s,dif,sol[50],k,temp[50];

void citire()

{

int i;

printf(“\n N=”);scanf(“%d”,&n)

printf(“\n s=”);scanf(“%d”,&s)

for(i=0;i<n;i++)

printf(“\n a[%d]=”,I);scanf(“%d”,&a[i]);

}

void calcul(int k;int t)

{

if (t==n-1){

if(k+a[n-1]<=s) {

k=k+a[n-1];

temp[n-1]=1;

}

if(s-k<dif){

dif=k;

for(i=0;i<n;i++)sol[i]=temp[i];

}

}

else{

if(k+a[t]<=s){

k=k+a[t];

temp[t]=1 ;

for(i=0 ;i<n;i++)calcul(k,I);

k=k-a[t] ;

}

62


}

void main()

{

citire();

dif=1000000 ;

k=0 ;

calcul(k,0);

printf(“\n submultimea este:”);

for(i=0;i<n;i++)

if(sol[i]=1) printf(“%d ”,a[i]);

printf(“\n diferenta minima este:%d”,dif);

}

Realizarea conexiunii inverse:

Astfel de învăţare a dinamizat întreaga clasă spre o rezolvare corectă, şi cei

mai mulţi elevi, au reuşit prin munca independentă scrierea programului cerut.

Concluzii:

Se vor face aprecieri individuale şi colective asupra activităţii desfăşurate.

63


BIBLIOGRAFIE:

1. Ion Iancu, Algoritmi genetici, Craiova 2004

2. Dumitrescu D., Algoritmi genetici şi strategii evolutive - Aplicaţii în

inteligenţa artificială şi în domenii conexe, Editura Albastră, Cluj-

Napoca, 2000;

3. Oltean M., Proiectarea şi implementarea algoritmilor, Computer Libris

Agora, Cluj-Napoca, 2000.

4. Genetic Algorithms + Data Structures = Evolution Programs, Zbigniew

Michalewicsz, Second, Extended Edition

5. Beasley D., Bull D.R., Martin R.R., An Overview of Genetic

Algorithms, Part 1, Foundations, University Computing, Vol.15, No.4,

pp. 170-181, 1993;

6. Goldberg D.E., Genetic Algorithms in Search, Optimization and

Machine Learning, Addison - Wesley, Reading,MA,1989;

7. Garey M.R., Johnson D.S., Computers and Intractability:A Guide to NP-

completeness, W.H. Freeman and Company, New York, 1978.

8. Koza J.R., Genetic Programming, MIT Press, Cambridge, MA, 1992;

64


CUPRINS:

CAPITOLUL III

CERCETAREA PEDAGOGICA

3.1 Ipoteza de lucru

3.2 Obiectivele cercetării

3.3 Metodologia verificării ipotezei

3.3.1. Tipologia cercetării

3.3.2 Organizarea cercetării

3.3.3 Metodele de cercetare utilizate

CAPITOLUL IV

PREZENTAREA ŞI INTERPRETAREA REZULTATELOR OBŢINUTE

4.1 Experiment privind aplicarea algoritmilor genetici

CAPITOLUL V

CONCLUZII. PROPUNERI METODICE

ANEXE

BIBLIOGRAFIE

ALGORITMI GENETICI - · PDF fileTehnoredactare : Luță Costina Claudia Referent...

Documents

Transcript of ALGORITMI GENETICI - · PDF fileTehnoredactare : Luță Costina Claudia Referent...