Odată cu evoluția tehnică provocările actuale, specifice sistemelor informatice [626959]

Abstract

Odată cu evoluția tehnică provocările actuale, specifice sistemelor informatice
distribuite, se adresează spre soluționare mai mult tehnicilor probabilistice decât celor
deterministe.
Volumul din ce în ce mai mare de date, într -o formă brută, nei ndexate, neclasificate,
rețelele din ce în ce mai complexe și mai dinamice, necesită noi tehnici de căutare a soluțiilor
pentru probleme complicate, tehnici care să fie capabile să ofere soluții într -un orizont de timp
bine definit și acceptabil de către b eneficiar. Mai mult decât atât, există probleme care sunt
imposibil de descris ca aparat matematic și neabordabile prin metode clasice de rezolvare. Toate
acestea se constituie ca premise valide în încercarea de dezvoltare și utilizare de tehnici
specifice inteligenței artificiale în scopul identificării soluțiilor.
Această teză propune utilizarea tehnicilor evolutive ca alternativă la cele clasice, bazate
pe algoritmi determiniști, pentru optimizarea sistemelor informatice, ținând cont că aceste
tehnici s unt capabile să abordeze probleme complexe de optimizare multicriterială și să ofere un
set de soluții Pareto optimale. În acest sens sunt prezentate studii referitoare la utilizarea
algoritmilor genetici pentru construcția de seturi de configurații care r espectă constrângerile
impuse, studii referitoare la utilizarea căutării evolutive în managementul și optimizarea
rețelelor în general și în mod particularizat pentru cele de tip SDN sau Internet of Things.
În plus, teza abordează și optimizarea funcționăr ii algoritmilor genetici, prin asigurarea
funcției de adaptare a operatorilor genetici atât prin utilizarea valorii fitness -ului cromozomilor
cât și prin evaluarea distribuției acestora în spațiul de căutare.

Introducere

Un sistem informatic distribui t este un sistem de prelucrare a informației format dintr -o colecție de
elemente dotate cu capacități de calcul și comunicații, independente, care fac schimb de mesaje și își
coordonează activitatea între ele utilizând o infrastructură de comunicații pentr u a îndeplini un număr
de obiective specifice. Motivele principale al dezvoltării sistemelor distribuite este partajarea și
virtualizarea resurselor, scalabilitatea, reducerea costurilor precum și toleranța la erori.
Serviciile din ce în ce mai diversifi cate de comunicații și creșterea capacității de transport
disponibilă au transformat sistemele distribuite într -o regulă și nu o excepție. Mai mult decât atât,
miniaturizarea elementelor cu capacitate de calcul, portabilitatea lor și interacțiunea din ce î n ce mai
strânsă cu utilizatorul a generat apariția și dezvoltarea unor sisteme distribuite heterogene și dinamice.
În paralel cu componenta hardware și componenta software a suferit modificări pentru a răspunde
noilor cerințe ale utilizatorilor, în aceas tă direcție, tehnologia evoluând atât din punct de vedere al
algoritmilor, fiind dezvoltate noi tehnici de prelucrare a volumului din ce în ce mai mare de date cât și
din punct de vedere al limbajelor de programare (prin necesitatea de a fi disponibile pen tru un număr
mare si foarte eterogen de platforme hardware) cât și din punct de vedere al aplicațiilor. Conceptul
„mobile computing” împreună cu spațiul de adrese practic nelimitat disponibile oferite prin standardul
IPv6 facilitează dezvoltarea sistemelo r distribuite și apariția de noi tehnici și metode pentru
managementul acestora.
Conceptele de virtualizare și de cloud computing sunt elemente care permit dezvoltarea de
sisteme informatice evolutive, de mari dimensiuni, răspândite pe o arie geografică ma re, cu parametrii
heterogeni, atât din punct de vedere al sistemului de comunicație cât si al capacității de calcul și de
stocare. Proiectarea, dezvoltarea și realizarea managementului unor astfel de sisteme informatice, cu
respectarea specificațiilor de c alitate a serviciilor sunt o provocare majoră pentru posibilitățile actuale
de management (atât din punct de vedere al comunicațiilor cât și din punct al realizării sarcinilor) bazate
pe deciziile administratorului care au fost dezvoltate în contextul exis tenței sistemelor clasice, relativ
statice.
Totodată, marea cantitate de date disponibilă din care doar o mică parte este structurată
precum și constrângerile referitoare la timpul de calcul orientează tendința de abordare deterministă
orientând -o spre cal culul probabilistic, atât în cazul abordării problemelor de optimizare, cât și de
căutare și control.
Complexitatea sistemului implică complexitatea controlului acestuia și necesitatea optimizării
alocării resurselor necesare în îndeplinirea sarcinilor. Dată fiind direcția de dezvoltare ale sistemelor
distribuite spre o creștere a complexității și spre o dinamică mare, instrumentele clasice sunt în mod
necesar completate cu tehnici noi de prelucrare a datelor, de management și de optimizare a
funcționării .
Lucrarea de față își propune să prezinte aplicarea tehnicilor specifice calculului evolutiv în
optimizarea funcționării sistemelor informatice distribuite actuale.

1.1 Formularea problemei

Direcțiile de evoluție ale domeniului IT sunt orientate spre de zvoltarea spațiului virtual, tendință
susținută de mobilitate și de marea varietate de servicii de comunicații disponibile atât în spațiul public
cât și în cel privat. Conceptul Internet of Things (IoT) nu mai este o noțiune abstractă, posibilă doar din
punct de vedere teoretic, fiind în curs de implementare și în continuă extindere, până la nivelul anului
2021 fiind preconizată apariția de standarde care să suporte implementarea de infrastructuri dense IoT,
în conformitate cu [1].
Tehnologiile Machine -to-Machine communication, virtualizarea (atât din punct de vedere al
software -ului cât și al hardware -ului și comunicațiilor), arhitectura cloud, platformele web scalabile
beneficiază de suportul infrastructurii de comunicații care oferă servicii cu acoperir e geografică aproape
totală și prezintă o creștere accentuată (Fig.1 ).

Comunicațiile wireless și depășirea limitărilor impuse de numărul finit de adrese oferite de IPv4
prin implementarea standardului IPv6 oferă premisele creșterii spectaculoase a num ărului de
echipamente cu capacități de prelucrare/stocare date conectate în diverse rețele (Fig.2).

Noile noțiuni de calcul ubicuu, de realitate augmentată, au cerințe specifice referitoare la
mobilitate , miniaturizare și capacitate de calcul. Toate a cestea implică dezvoltarea unor sisteme
informatice cu un mare grad de dinamicitate, complexitate și heterogenitate. Din acest punct de vedere,
dezvoltarea și managementul lor clasic, prin intervenția factorului uman este imposibilă, fiind necesară
dezvolt area unor tehnici automate, adaptabile, scalabile.
Prin multitudinea de cerințe care trebuie îndeplinite pentru a asigura furnizarea în parametrii a
serviciilor, problema managementului unor astfel de sisteme este o problemă de optimizare
multicriterială. Ca urmare a existenței mai multor funcții obiectiv, de multe ori cu tendințe de evoluție
opuse, noțiunea de optim presupune identificarea mulțimii soluțiilor de compromis care îndeplinesc
toate obiectivele. Astfel, dificultatea majoră a problemelor multio biectiv constă în necomparabilitatea
diferitelor soluții identificate.
Dinamicitatea mare a sistemelor necesită adoptarea în timp util a deciziilor care afectează
parametrii de funcționare, operațiunile de configurare/reconfigurare trebuind să fie realizat e
transparent pentru utilizatorul final. Fiind vorba de decizii multiobiectiv este nevoie de o nouă abordare
a conceptelor de optimizare și management a acestor sisteme de calcul pentru a realiza furnizarea

serviciilor în parametrii impuși, variantele cla sice, relativ statice sau cu dinamicitate redusă, bazate pe
intervențiile administratorilor neputând oferi soluții viabile în timp rezonabil.

1.2 Scopul tezei

Scopul acestei teze este de a prezenta soluții noi de optimizare și management a sistemelor
informatice moderne, în concordanță cu evoluția tehnologică. Întrucât nivelul de integrare a tehnologiei
în societate (definită în prezent ca societate informațională) este în continuă creștere iar solicitarea de
servicii are un caracter dinamic, sunt necesare tehnologii care să le completeze pe cele clasice pentru a
asigura un nivel de autoadaptare și de asistare activă sau chiar de înlocuire a factorului uman în
configurarea/reconfigurarea echipamentelor.
Dinamicitatea este un atribut relativ nou al sisteme lor informatice, apărut ca urmare a
dezvoltării la scara largă a comunicațiilor radio și de creșterea capacității de transport disponibile iar
miniaturizarea dispozitivelor hardware a accelerat această caracteristică. Ca urmare, instrumentele
clasice de m anagement și protocoalele existente nu mai sunt instrumente eficiente pentru controlul
sistemelor informatice evolutive și de mari dimensiuni. Lucrarea de față prezintă un set de probleme
generate de dinamicitate, homogenitate și scalabilitate, propunând o abordare bazată pe algoritmi
genetici pentru optimizarea funcționarii unor astfel de sisteme.
Numărul mare de dispozitive mobile, cu capacitate de calcul, conceptul Internet of Things,
virtualizarea atât a componentei software cât și a managementului re țelei determină dezvoltarea
accelerată a sistemelor de mari dimensiuni dotate cu un anumit grad de autonomie și cu o dezvoltare
puțin predictibilă. În aceasta lucrare este propusa o abordare genetica a controlului acestor tipuri de
sisteme, în concordanță cu cerințele de calitate a serviciilor.
Tehnicile genetice sunt o modalitate probabilistică de generare a unui set de rezultate în
abordarea unei probleme multicriteriale. Inspirate din teoria evoluționistă a lui Darwin, acestea
realizează căutarea în spa țiul soluțiilor prin utilizarea unor operatori genetici care sunt aplicați asupra
unor populații de cromozomi care codează problema. Teza propune atât un algoritm genetic care are ca
date de intrare inclusiv istoricul sistemului informatic cât și o variant ă adaptivă a acestor operatori
pentru a accelera timpul de convergenta al algoritmului.
Totodată, în teză se are în vedere dezvoltarea unui set de funcții necesare pentru a simula un
sistem informatic de mari dimensiuni și de testare/validare a soluțiilor propuse.

1.3 Contribuții ale lucrării

Luând în considerare scopul tezei enunțat anterior, autorul, în studiile și testele efectuate atât în
teza prezentă cât și prin articolele susținute în cadrul conferințelor și prezentate în diverse publicații de
special itate a propus:

a. În cadrul optimizării sistemelor informatice:
– Abordarea genetică a diverselor concepte și tehnologii de actualitate prezente în cadrul
sistemelor distribuite care poate înlocui în mod performant abordările clasice, bazate pe
algoritmi dete rminiști
– Adordarea unitară, multicriterială, a managementului infrastructurii de comunicații a unui
sistem distribuit, luând în considerare cerințele de servicii, resursele disponibile,
tendința de evoluție a parametrilor precum și evoluția din punct de ve dere istoric a
acestora
b. În cadrul optimizării funcționării algoritmilor genetici propuși a fi utilizați în sistemele
informatice distribuite:
– Conceptul de ”cromozom central” bazat pe distribuția în spațiul de căutare a
cromozomilor și nu pe fitness -ul aces tora
– O nouă măsură a diversității care are ca repere distanțele dintre componentele populației
și cromozomul central
– O formă adaptivă a operatorilor de mutație și crossover care au ca parametrii atât fitness –
uil cât și noua măsură a diversității.
c. Dezvolta rea unei structuri de date și a unui set de funcții pentru realizarea testării
soluțiilor propuse.

1.4 Organizarea tezei

Lucrarea este structurată în 6 capitole, în care se urmărește introducerea în domeniul de studiu,
prezentarea conceptelor și direcțiilor de evoluție a sistemelor informatice distribuite, a metodelor de
optimizare multicriterială, cu accent pe cele care vor fi utilizate precum și contribuțiile aduse de autor în
domeniul de studiu.
Primul capitol conține o scurtă prezentare a problemelor s pecifice domeniului studiat și a
scopului tezei, a organizării și a contribuțiilor aduse de autor în optimizarea multicriterială a sistemelor
informatice distribuite.
Capitolul al doilea este o prezentare a stării domeniului studiat și a conceptelor teor etice
componente ale tezei. Luându -se în considerare că noile tehnologii reprezintă motorul evoluției
sistemelor informatice atât ca arhitectură cât și din punct de vedere hardware și software, sunt

abordate succint elemente referitoare la machine -to-mach ine communication, Internet of Things, calcul
ubicuu, calcul raportat la context, rețele de senzori wireless, smart -dust, inteligența ambientală,
elemente referitoare la virtualizare și la cloud -computing, toate aceste componente existând cu
precădere în c adrul unor sisteme informatice distribuite.
În capitolul 3 sunt prezentate elemente teoretice referitoare la optimizarea multicriterială, cu o
dezvoltare mai pronunțată a metodelor evolutive de optimizare multicriterială a sistemelor informatice,
în cadru l cărora fiind detaliate algoritmii genetici (care vor fi tehnici de bază utilizate în metodele
propuse în capitolul 4), programarea genetică, programarea evolutivă și strategiile evolutive.
Capitolul 4 este dedicat prezentării unor metodelor genetice de o ptimizare/generare a soluțiilor
apărute în cadrul sistemelor distribuite incluzând în două subcapitole distincte metodele propuse si
rezultatele obținute de către autor. În primul subcapitol sunt prezentate abordări evolutive ale
optimizării funcționării i nfrastructurii de comunicații a unor sisteme informatice, cel de -al doilea
subcapitol fiind rezervat prezentării studiilor referitoare la optimizarea funcționării algoritmilor genetici
utilizați, cu accent pe autoadaptarea operatorilor genetici.
Capitolul 5 prezintă concluziile referitoare la elementele abordate în cadrul tezei, limitările
studiilor și perspectivele de cercetare în domeniu.
Capitolul 6 conține lista de publicații ale autorului și detalii de implementare pentru tipurile de
date și funcțiile dezvoltate pentru testarea soluțiilor de optimizare propuse.

2 Starea domeniului

Proporțional cu creșterea acoperirii geografice și a capacității de transport din punct de vedere al
comunicațiilor, s -au dezvoltat și sistemele informatice distribuite. Tol eranța la erori, partajarea
resurselor, nevoia de a oferi servicii pe o arie geografică întinsă sunt principalele motive pentru care
sistemele distribuite se vor dezvolta accelerat în următoarea perioadă.
Inițial, noțiunea de sistem distribuit s -a referit la un număr de echipamente dotate cu capacitate de
calcul, conectate în rețea, care, prin schimb de mesaje, îndeplinesc o anumită sarcină. Noile tehnologii
(virtualizarea) au lărgit noțiunea de sistem distribuit, în acest domeniu fiind inclusă și colecția de procese
autonome de pe același calculator, care îndeplinesc o anumită sarcină comunicând între ele.
Luând în considerare aceste premise, elementele definitorii ale unui sistem distribuit sunt:
– O modalitate de comunicare între componentele sistemului prin schimb de mesaje,
– Existența unor entități de calcul autonome (hardware sau software) care utilizează
propriul spațiu de memorie,
– Lipsa unui ceas global,
– Sistemul se prezintă utilizatorului prin rezultatele generate, fiind transparentă
componenta hardw are sau software a acestuia.

Dacă la apariție sistemele distribuite erau caracterizate prin stabilitate, atât din punct de
vedere al nodurilor cât și din punct de vedere al comunicațiilor, cerințele actuale conduc spre sisteme
distribuite în care instab ilitatea (atât ca elemente de calcul cât și din punct de vedere al comunicațiilor)
este o stare de normalitate. Mai mult decât atât, ele necesită și un anumit grad de autonomie. Dacă
aplicațiile și dispozitivele de calcul sunt configurate de utilizator, me nținerea conexiunii în cadrul
sistemului trebuie să fie efectuată fără a fi necesară intervenția factorului uman.
Dezvoltarea terminalelor „inteligente”, atât din punct de vedere al numărului, cât și al capacității
de calcul, al autonomiei și al comunica țiilor a condus la apariția unor concepte noi, Machine to machine
(M2M) comunication, Internet of Things (IoT), ubiquitous computing, mobile computing, context -aware
computing, Smart Dust, Utility Fog, realitatea augmentată, rețelele de senzori depășind f aza de concept,
de cercetare și fiind din ce în ce mai prezente în viața de zi cu zi.
În contextul unui sistem dinamic, tehnicile evolutive oferă un cadru optim din punct de vedere al
resurselor utilizate/ timpului de furnizare a rezultatelor/calității soluțiilor pentru asigurarea unei
autonomii funcționale având în vedere cerințele de fiabilitate, dispoinibilitate și scalabilitate .
Algoritmii genetici sunt o variantă pentru a furniza soluții de reconfigurare a elementelor în cadrul
sistemelor dinamice , de mari dimensiuni iar pentru operații cu volume mari de date, tehnicile
probabilistice oferă rezultate superioare tehnicilor clasice, deterministe.

2.1 Concepte și direcții de evoluție a sistemelor distribuite

Apariția posibilității de a transmite date la distanță a determinat trecerea de la sistemele
informatice centralizate (de la tehnologia mainframe) la cele distribuite. Dezvoltarea rețelelor de
transmisii de date a fost determinată și în același timp a determinat evoluția domeniului IT.
Din punct de vedere istoric perioada anilor 90 a fost perioada apariției și dezvoltării sistemelor
de tip client -server. A fost continuată de perioada anilor 2000 influențată de dezvoltarea tehnologiilor
World -Wide -Web și a Internetului. Anii 2010 au foat marcați d e ideea de mobilitate (anywhere, anytime,
anyuser) și au fost continuați de perioada actuală, a calculului pervaziv/ubicuu și de virtualizare a
resurselor (hardware, software și de comunicații)
În paralel cu evoluția și dezvoltarea din punct de vedere al infrastructurii, au apărut noi
concepte care definesc palierele principale de evoluție tehnologică. În prezent, Internet of Things,
Machine to Machine Communication, virtualizarea, realitatea virtuală, realitatea augmentată, big data
imprimă direcții de de zvoltare hardware și software și includ atât palierul determinist cât și cel
probabilist pentru o integrare naturală a elementelor dotate cu capacități de procesare și comunicații în
viața de zi cu zi.

2.1.1 Machine to machine communication (M2M communication)

Conceptul M2M communication are ca element central comunicația directă, cu o minimă
intervenție umană între echipamente, ceea ce presupune ca toate elementele trebuie sa fie conectate
într-o rețea.
Aplicațiile M2M sunt diverse și într -o continuă dezvolt are iar elementele componente ale unor astfel
de sisteme sunt heterogene, incluzând senzori, echipamente medicale, vehicule, echipamente de
divertisment, echipamente industriale, etc., practic, orice obiect care poate fi adresat, autentificat,
localizat si controlat utilizând servicii de comunica ții poate fi integrat într -un sistem M2M.
Date fiind tipurile de dispozitive componente, apar o serie de constrângeri:
– Interoperabilitatea, dat fiind numărul mare de producători, a modalităților de conectare la
diverse tipuri de rețele
– capacitatea limitată de calcul
– eficiența din punct de vedere energetic, datorită faptului că unele componente sunt
autonome din punct de vedere al sursei de energie
– autoorganizarea
– autonomia din punct de vedere al managementului și al funcționarii.
Referitor la schimbul de me saje, deoarece un astfel de sistem este caracterizat de mobilitate și
dispunere pe o arie geografica a elementelor componente, sistemele M2M sunt puternic dependente de
comunicațiile wireless. Puterea limitată de emisie, necesitatea unei antene, interfere nțele,
numărullimitat de canale de emisie disponibile sunt caracteristici care determină deciziile din punct de
vedere ar arhitecturii funcționale.
Caracteristicile și provocările domeniului M2M sunt:
– numărul mare de dispozitive
– aplicațiile diverse, ceea ce conduce la diferite tipuri de trafic de date și la diverse cerințe
din punct de vedere al serviciilor oferite de rețeaua de comunicații
– existența unui număr mare de producători ceea ce implică standarde diferite și
incompatibile între servicii, interfe țe, aplicații
– heterogenitatea comunicațiilor, atât cu fir cât și cele wireless.
Ca urmare a dezvoltării acestui tip de sisteme ( se estimează că la nivelul anilor 2020 vor
exista 50 miliarde de dispozitive) și a maturizării tehnologiei, este necesara o st andardizare a domeniului
pentru a realiza un cadru de dezvoltare stabil, public, agreat, cu implicații pozitive din punct de vedere al
interoperabilității/interschimbabilității/conformității elementelor, din punct de vedere al
caracteristicilor tehnice și al transferului de tehnologie și al unificării produselor, proceselor și serviciilor.

În [2], este tratata arhitectura funcțională a unui sistem M2M, descrierea entităților
componente, a serviciilor ce pot fi oferite, modalitatea de identificare în rețea, managementul,
securitatea, noțiuni de implementare.
Descrierea arhitecturală este împărțită în doua domenii, cel al rețelei de comunicații și cel al
elementelor componente și al gateway -ului, conform Fig.1.:

În conformitate cu această arh itectură, în domeniul elementelor M2M și al gateway -ului, se află
dispozitivele care rulează aplicațiile specifice. Acestea pot accesa domeniul rețelei atât direct, cât și
printr -un gateway care conectează rețeaua elementelor M2M cu rețeaua în care se afl ă aplicațiile.
Domeniul rețelei de comunicații include rețeaua de acces (cu conexiune prin cablu sau wireless),
rețeaua specifica sistemului (care poate fi o rețea publica sau o rețea privata), nivelul serviciilor
disponibile si cel al aplicațiilor care utilizează datele generate de elementele M2M si le oferă
utilizatorului. Tot la acest nivel se află serviciile de management ale rețelei și ale dispozitivelor M2M.
Conexiunea între doua domenii M2M se face, în conformitate cu standardizarea propusa de ETSI
la nivelul unor interfețe din domeniul rețea (mIm – M2M to M2M interface) (Fig.2.):

2.1.2 Internet of Things (IoT)

Conceptul IoT presupune la o rețea formata din elemente fizice dotate cu capacitate de calcul,
obiectele putând fi adresate și controlate, putând efectua diverse acțiuni daca sunt dotate cu elemente
efectoare, având capacitatea de a achiziționa date din mediu cu ajutorul senzorilor sau având funcții de
transport, prelucrare sau stocare de informație.
Fiecare element este unic i dentificat, fiind posibilă interacțiunea cu alte obiecte prin utilizarea
rețelei de comunicații.
Din punct de vedere al dezvoltării, este un sistem într -o expansiune puternică această dezvoltare
fiind susținută atât de miniaturizarea elementelor de calcul cât și de creșterea capacității de calcul și
dezvoltarea serviciilor de rețea.
Prin caracteristicile sale, IoT este o particularizare la scară mare (bazată preponderent pe
Internet ca modalitate de conectare a elementelor) a conceptului M2M communicatio n, unde
elementele sunt distribuite pe o arie geografică limitată iar modalitatea preponderentă deconectarea a
lor este o rețea privată (existentă sau dezvoltată ad -hoc).

Elementele componente fac parte din domenii foarte variate, din industrie, medicina ,
divertisment, monitorizare a mediului, transport, elemente ale casei inteligente, ale orașului inteligent ,
etc.
Caracteristicile de baza ale elementelor IoT sunt:
– heterogenitatea – din punct de vedere al modalităților de comunicație, al parametrilor
hardware și software
– interconectivitatea – orice obiect IoT poate să comunica cu alte obiecte IoT utilizând
infrastructura de comunicații
– dinamicitatea – atât din punct de vedere al funcționarii (periodic, permanent, intermitent)
cât și din punct de vedere a l localizării (unele sunt fixe, altele mobile)
– numărul mare de echipamente.
Din punct de vedere al tehnologiilor și protocoalelor utilizate, majoritatea acestora sunt propuse
și dezvoltate de producătorii de echipamente. Uneori acestea sunt incomplete sau dezvoltate doar
parțial, uneori sunt soluții complete dar necesită resurse indisponibile pentru echipamente furnizate de
alți producători, fiind de multe ori dificil sau chiar imposibil de integrat un număr mare de echipamente
diferite (ca urmare a difere nțelor constructive, a caracteristicilor funcționale, etc.).
Pentru a se realiza o dezvoltare unitară a conceptului, în vederea impunerii unui standard și
pentru respectării unui set de caracteristici, ITU -T a elaborat recomandarea ITU -T Y.2060 prin care se
definește IoT ca o infrastructură la nivel global a societății informaționale care oferă servicii prin
interconectarea fizică sau virtuală a elementelor, pe baza tehnologiilor de comunicații și a capacității de
interoperabilitate.
Conceptul introduce p osibilitatea de comunicare a oricărui lucru, pe lângă posibilitatea de a
comunica în orice moment de timp și în orice loc.

Un obiect fizic IoT poate fi reprezentat prin unul sau mai multe obiecte virtuale. Un obiect virtual
poate sau nu sa aibă coresp ondență în lumea fizică. Comunicarea între obiecte poate fi prin intermediul
unui gateway și a rețelei, direct prin rețea sau punct la punct (Fig.4.).

Din punct de vedere al schimbului de informație între elemente, rețeaua în care sunt conectate
oferă s erviciile necesare atât pentru transmiterea informațiilor colectate cât și pentru comanda

elementelor componente. Infrastructura necesară poate fi reprezentată atât de rețele existente cât și de
rețele dezvoltate ulterior.
În ITU -T Y.2060 este definit m odelul de referință IoT pe 4 nivele (Fig.5.):
– nivelul fizic
– nivelul de rețea
– nivelul de suport pentru aplicații și servicii
– nivelul aplicațiilor.

În cadrul nivelului aplicațiilor, se află aplicațiile care rulează și oferă servicii caracteristice IoT.
Nivelul de suport pentru servicii și aplicații oferă atât suport general pentru prelucrare și stocare de
date cât și servicii specifice. Acestea sunt determinate de cerințele aplicațiilor și de dotările elementelor
IoT.
Nivelul rețea oferă servicii de trans port pentru datele achiziționate de senzori, pentru cele
prelucrate cât și pentru comenzile transmise elementelor, fiind oferite și servicii conexe de autentificare,
autorizare, management al rețelei, a mobilității.
Din punct de vedere al nivelului fizic, acesta se referă la interacțiunea directă cu rețeaua de
comunicații (achiziție sau transmitere directă de date direct, fără utilizarea unui gateway) cât și cea
indirectă. Nivelul include și facilități de dezvoltare de rețele ad -hoc și mecanisme de economis ire a
energiei (funcții „sleeping” și „wake -up”).
Referitor la elementele gateway, acestea trebuie să suporte multiple interfețe de comunicație, cu
sau fără fir (CAN, Bluetooth, WiFi, etc.) și să comunice utilizând tehnologii diverse (PSTN, 2G, 3G, 4G,
LTE, DSL, etc.). Pe lângă acestea, trebuie să suporte realizarea de conversii de protocol în cazul în care
sunt utilizate protocoale diferite.
Din punct de vedere al managementului și al securității, elemente ale acestor funcții sunt prezente
în toate cele 4 nivele ale modelului de referință. Funcțiile de management sunt implementate în
elementele componente IoT, în topologia rețelei și în managementul benzii de comunicație(trafic,
congestii, rezervare de resurse, etc.). Pe lângă aceste funcții de bază sunt prezente și elemente
specifice, direct dependente de serviciile oferite de sistem.
Securitatea are atât componente generale cât și componente particulare. La nivelul aplicațiilor sunt
prezente servicii de autentificare, autorizare, confidențialitate și int egritate a datelor, antivirus, audit de
securitate iar la nivelul rețelei securitatea se referă la autorizare, autentificare, protecție a datelor,
comenzilor și semnalizărilor iar la nivelul fizic la autorizare, autentificare, controlul integrității
eleme ntelor, controlul accesului. Pe lângă aceste elemente generale sunt prezente și elemente
particulare, determinate de funcțiile sistemului.

2.1.3 Calculul ubicuu

Calculul ubicuu (pervaziv, care este prezent peste tot) definește conceptul prin care orice
dispoz itiv, din orice loc sau în orice format poate fi dotat cu capacitate de calcul, permițând o
interacțiune naturală a omului cu sistemele de calcul. Principalele caracteristici ale calculului pervaziv au
fost sintetizate de către T. Kimberg și A. Foxx în luc rarea „System software for ubiquitous computing”
[3], fiind considerate ca puncte de referință integrarea fizică și interacțiunea spontană.
Integrarea fizică presupune integrarea dintre elementele de calcul și elementele fizice ale
mediului înconjurător
Din punct de vedere al interacțiunii spontane, aceasta vizează schimbul de informații dintre
componentele sistemului ubicuu în cazul modificării parametrilor de mediu. Componentele pot să își
modifice identitatea și funcționalitatea în funcție de circumsta nțe sau își pot schimba partenerii de
comunicație, fără a fi nevoie de componente software sau parametrii noi.
Dezideratele de integrare fizică și interacțiune spontană au implicații majore în infrastructura
software. Această componentă trebuie să asigur e adaptabilitatea la mediu, scalabilitatea,
interoperabilitatea, toleranța la erori, securitatea. Toate aceste caracteristici trebuie realizate ținând
cont de resursele disponibile care pot fi în multe cazuri foarte limitate și foarte dinamice. Condițiile de
mediu care pot fi inclusiv greu predictibile au o influență importantă asupra componentei software a
sistemului ubicuu.
Caracteristicile principale ale calculului ubicuu, așa cum sunt definite în [3] sunt:
– descoperirea și interacțiunea
– adaptarea
– integr area
– mediul de programare
– robustețea
– securitatea.
a. Descoperirea și interacțiunea
Calculul pervaziv tinde să se dezvolte spontan, într -un anumit interval de timp, pe măsură
ce
în mediul respectiv sunt introduse noi elemente posibil de a fi integrate, în tim p adoptându -se diverse
moduri de utilizare a componentelor. Extensibilitatea este o caracteristică importantă a unui astfel se
sistem.
Interacțiunea spontană asigură interacțiunea obiectelor pe termen scurt și contribuie la
realizarea unor obiective pred ictibile.

Descoperirea și interacțiunea presupune stabilirea parametrilor de comunicații, descoperirea
serviciilor și interacțiunea. Stabilirea parametrilor de comunicație are ca rol asigurarea elementelor
necesare pentru ca un obiect să poată comunica în cadrul unui sistem pervaziv. Descoperirea serviciilor
implică localizarea unui serviciu care necesită o nouă componentă iar interacțiunea asigură schimbul de
informații pentru a contribui la realizarea scopului propus.

b. Adaptarea
Într-un mediu ubicuu, exi stă o mare varietate de dispozitive hardware, cu resurse de
calcul
limitate sau dinamice. Elementele tind să fie de dimensiuni mici și să fie autonome energetic, ceea ce
adaugă noi constrângeri din punct de vedere al resurselor. Adaptarea în aceste condi ții se referă la
modul de realizare a sarcinilor sistemului luând în considerare toate aceste date, fără intervenție umană.
Adaptarea trebuie să aibă loc atât din punct de vedere al conținutului cât și din punct de vedere al
interfeței cu utilizatorul

c. Integrarea
Pentru a se putea realiza integrarea dintre mediul de calcul (virtual) cu cel fizic sunt
necesare
atât interfețe de nivel scăzut care permit interacțiunea software -ului cu senzorii și elementele efectoare
cât și medii de programare de nivel înalt care permit interacțiunea cu mediul real într -un mod natural.

d. Mediul de dezvoltare
Un mediu de dezvoltare pentru calculul pervaziv trebuie să aibă în vedere caracteristicile
domeniului din punct de vedere al aplicațiilor, al sistemelor de operare și al limbajelor de programare.
Ca urmare a evoluției permanente și accelerate a tehnologiilor este nevoie de dezvoltarea de
mecanisme de integrare a software -ului și hardware -ului de diferite generații, ceea ce conduce la o
interconectare mai puțin strânsă înt re componente dar la o mai ușoară integrare a lor și o scalare simplă
a sistemului. Din punct de vedere al implementării suportului pentru calcul ubicuu, acesta poate fi la
nivel de sistem de operare, la nivel middleware (nivelul dintre sistemul de operare și aplicații) sau la
nivel de aplicații.

e. Robustețea și toleranța la erori
Sistemele pervazive, datorită caracteristicilor (heterogenitate, comunicații cu/fără fir, mediu
variabil, etc.) sunt expuse erorilor, cauzele acestora putând fi atât hardware cât și software.
Într-un sistem ubicuu, existența numeroaselor erori tranzitorii este o stare de funcționare
normală (comunicațiile wireless pot fi afectate de interferențe, autonomie energetica limitată produce

nefuncționarea sau funcționarea parțială a unor elemente, erorile de implementare a diferitelor
componente software afectează starea de funcționare). Această stare de fapt conduce la necesitatea de
a fi dezvoltate mecanisme prin care în orice moment sistemul să poată recupera resursele pierdute cu
păst rarea caracteristicilor funcționale.

f. Securitatea
Calculul ubicuu implică cerințe de securitate specifice din punct de vedere al resurselor și
utilizatorilor. Dacă calculul mobil este expus vulnerabilităților inerente utilizării rețelelor fără fir, în caz ul
integrării și interoperabilității spontane sunt necesare noi modele de asigurare a securității.
Nivelul de încrederea este o provocare atunci când este vorba de sisteme pervazive ca urmare a
asocierii spontane de elemente pentru care nu există informaț ii apriori. Utilizatorul trebuie să își
stabilească propriul nivel de încredere, existând mecanisme de asigurare a securității în acest sens (chei
criptografice, canale de comunicații pe distanțe foarte scurte, etc.).
În cazul componentelor cu resurse lim itate, protocoalele de securitate sunt dificil sau imposibil
de implementat pentru că resursele de calcul sunt minime iar cantitatea de date transmisă trebuie
limitată pentru a se asigura un consum minim de energie. Orice protocol de securitate presupune
introducerea unei cantități de date suplimentare necesară operațiunilor de autentificare și calcule și
date suplimentare pentru o eventuală criptare/decriptare.
Autentificarea utilizatorilor este altă problemă în cazul sistemelor pervazive pentru că
interop erabilitatea simultană presupune un flux de utilizatori și dispozitive care apar și dispar în mod
continuu, ceea ce necesită autentificare dependentă de sistem.
Integrarea fizică are implicații inclusiv asupra securității, localizarea utilizatorului având implicații
asupra intimității în cazul autentificării bazate pe locație, sistemul stabilind localizarea unei componente
fizice ca și criteriu pentru oferirea de servicii.

2.1.4 Calculul mobil

Conceptul de calcul mobil se referă la interacțiunea om -calculator, în care elementul de calcul
este transportat în mod natural, oferind în același timp diverse servicii )transmisii de date, voce, video,
autentificare, etc.)
Dimensiunile calculului mobil au fost reprezentate (Fig.6.) de Reza B’Far în lucrarea „Mobile
com puting principles. Designing and DevelopingMobile Application using UML and XML”:
– Aria geografică
– Calitatea serviciilor conexiunii la rețea
– Resursele limitate ale dispozitivelor

– Resurse energetice limitate
– Suportul pentru o mare varietate de interfețe cu u tilizatorul
– Proliferarea platformelor
– Tranzacțiile active

a. Aria geografică

Schimbarea ariei geografice este o caracteristică de bază a calculului mobil cu implicații
importante asupra hardware -ului și software -ului utilizat, localizarea și detectarea l ocației fiind
caracteristici care intervin în funcționarea echipamentelor mobile.
Din punct de vedere al localizării, aceasta se referă la abilitatea aplicațiilor de a oferi facilități
diferite în funcție de zona geografică în care se află echipamentul.
Detectarea locației este caracteristica echipamentului de a obține informații de localizare în
timpul utilizării și de a modifica parametrii de funcționare hardware/software în funcție de datele
obținute și se referă atât la localizarea efectivă cât și la p oziția relativă față de un anumit punct, fiind
utilizate tehnici de triangulație, de analiză a proximității, etc.

b. Calitatea serviciilor
Mobilitatea presupune pierderea conectivității permanente la rețea, cu implicații
importante
asupra calității servicii lor. Aplicațiile care rulează în acest mediu trebuie să funcționeze normal atât în
cazul deconectării de la rețea cât și în cazul conectării/deconectării frecvente și cum să își continue
activitatea după restabilirea conexiunii.
Datele oferite de provide r referitoare la calitatea serviciilor (lățime de bandă disponibilă, risc de
pierdere a conexiunii, diverse statistici) pot fi utilizate de aplicații pentru a -și modifica dinamic
parametrii de funcționare prin autoadaptarea la condițiile existente la un mo ment dat.

c. Resursele limitate ale dispozitivelor
Dimensiunile fizice limitate impun constrângeri din punct de vedere al resurselor
echipamentelor mobile, care se reflectă direct asupra aplicațiilor. Pentru a putea fi utilizate pe mai
multe platforme hardw are cu diferite configurații, software -ul utilizat va trebui să minimizeze resursele
de care are nevoie și să fie capabil să ruleze pe maimulte tipuri de platforme, de firmware -uri sau de
sisteme de operare.

d. Resursele energetice limitate
Constrângerile re feritoare la cantitatea de energie disponibilă sunt importante în cazul
echipamentelor mobile, unde, de obicei, sursa de energie este cea mai voluminoasă componentă a
acestora. Resursele limitate din acest punct de vedere au determinat atât dezvoltarea d e funcții de
management a energiei incluse în sistemul de operare sau în componentele hardware, cât și
minimizarea resurselor utilizate de aplicații și optimizarea componentelor hardware (procesoare cu
consum mic, pierderi minime prin căldură, etc.).
Întrucât conexiunea radio este un mare consumator de energie, sistemul de operare are incluse
facilități de optimizare a transmisiilor de date în funcție de utilizarea dispozitivului.

e. Suportul pentru o mare varietate de interfețe cu utilizatorul
Tipul de interfață este influențat în mod direct de suportul hardware oferit de elementul mobil, de
modul și de condițiile în care este utilizat. Proiectarea și implementarea aplicațiilor pentru calculul mobil
este dependentă de găsirea unei interfețe cu utilizato rul optime, de stabilire a arhitecturii sistemului în
funcție de aceasta și de a o implementa și modifica dinamic, în funcție de cerințe.
Ca urmare a dezvoltării de noi tehnologii și de apariție a noi cerințe din partea utilizatorilor,
interfețele au mai mult o dezvoltare speculativă, bazată pe elemente de noutate și de ergonomie. Este
dificilă stabilirea de predicții pe termen lung referitoare la mecanismele de intrare/ieșire ale unui sistem,
atât din punct de vedere hardware cât și software.

f. Proliferare a platformelor
Apariția unei mari varietăți de platforme software a avut un impact important în
arhitectura,
design -ul și dezvoltarea aplicațiilor mobile. Dacă inițial platformele proprietare au avut o pondere
importantă în calculul mobil, în momentul act ual platformele open -source sunt din ce în ce mai utilizate.
Aplicațiile tind spre o independență față de sistemul de operare și componenta hardware
(aplicații cross -platform, multiplatform, independente față de platforme), prin utilizarea unui nivel
intermediar între sistemul de operare și aplicație, oferit de diverse mașini virtuale.

g. Tranzacțiile active
Calculul mobil, ca urmare a interacțiunii om -calculator este caracterizat prin tranzacții
active,
acele tranzacții care sunt inițiate de sistem. Dacă î n cazul unui sistem de calcul clasic, interacțiunea cu
utilizatorul este cu precădere inițiată de utilizator, în cazul calculului mobil interacțiunea poate fi inițiată,

ca urmare a producerii unor evenimente, de către sistem. Tranzacțiile pot fi atât sincr one, cât și
asincrone.

2.1.5 Calculul raportat la context (Context aware computing)
Calculul raportat la context este caracterizat de proprietatea dispozitivelor mobile de realiza
anumite procese în funcție de contextul existent la un moment dat.
Defini ția raportării la context a fost analizată și sintetizată de A.Dey și G.Abowd în
„Towards a Better Understanding of Context and Context -Awareness” [4]. Astfel,
„un sistem este raportat la context dacă utilizează contextul pentru a oferi utilizatorului in formații
relevante și/sau servicii, unde relevanța este raportată șa cerințele utilizatorului.” [4].
Contextul este definit ca „orice informație care poate fi utilizată pentru a caracteriza o situație
sau o entitate. O entitate este o persoană, un loc sau un obiect, relevantă pentru interacțiunea dintre un
utilizator și o aplicație, incluzând utilizatorul și aplicația în sine”. [4].
Ca și caracteristici, din punct de vedere al autorilor, aplicațiile raportate la context trebuie să
suporte prezentare, exe cuție și etichetarea.
Referitor la prezentare, contextul poate fi utilizat pentru a decide când o informație sau un
serviciu sunt prezentate utilizatorilor.
Execuția se referă la faptul că anumite activități efectuate sunt raportate la evenimente,
local izare geografică, informații relevante, etc., fiind raportate practic la context.
Etichetarea presupune ca informațiile (generate de software, colectate de senzori, introduse de
utilizator) trebuie să fie completate cu informații referitoare la contextul în care au fost obținute pentru
a putea fi utilizate în cadrul context -aware computing.
Din punct de vedere al tipului, există contexte primare și secundare. Cele primare sunt timpul,
locația, identitatea, activitatea (când, unde, cine și ce) iar cele se cundare sunt cele care pot fi identificate
cu ajutorul celor primare, mai precis, un context primar este acela care generează informații fără a
utiliza un alt context și fără a efectua vreo operație asupra datelor achiziționate de senzori. Implicit,
contex tele secundare sunt acelea care pot fi generate efectuând diverse operații asupra contextelor
primare.
Calculul contextual asigură o interactivitate naturală a tehnologiei cu utilizatorul. Această
interacțiune a fost stabilită în [5] a fi de trei tipuri:
– Personalizarea, în cadrul căreia utilizatorul își setează singur preferințele
– Raportarea pasivă la context în cadrul căreia sistemul monitorizează mediul și oferă
utilizatorului opțiuni care pot fi sau nu validate

– Raportarea activă la context, în care sist emul monitorizează în permanență mediul și
efectuează în mod autonom anumite sarcini.
Din punct de vedere arhitectural, un sistem de calcul raportat la context conține
etapele de achiziție a informațiilor, de prelucrare a acestora și de efectuare de opera ții în funcție de
datele obținute și de condițiile de mediu existente. În [6] aceste etape sunt descrise ca formate din 5
nivele(Fig.7.).

La nivel de senzori (atât biologici cât și non -biologici), datele sunt achiziționate din mediu,
acestea fiind trans mise prin diverse medii de comunicații sub formă brută. La nivelul de prelucrare,
aceste date sunt preluate de la senzori, prelucrate, sunt eliminate erorile și sunt atașate informații
referitoare la context. Nivelul aplicațiilor utilizează aceste date pen tru a efectua diferite operații sau
pentru a la transfera în vederea valorificării unitare, prin completare cu alte date obținute din alte surse.

2.1.6 Rețele de senzori wireless

Conceptul se referă la o sumă de elemente de calcul utilizate pentru monitorizar ea parametrilor
unei anumite arii geografice.
Oricare ar fi aplicațiile acestora, majoritatea senzorilor au un număr de caracteristici comune:
autonomie în funcționare, dimensiuni minime, consum mic de energie, cost scăzut.
Din punct de vedere constructi v, rețelele de senzori (WSN) sunt formate din senzori/elemente
efectoare, elemente de prelucrare a datelor, de stocare, modalități de alimentare cu energie electrică.
Ca obiective de dezvoltare, rețelele de senzori trebuie să fie formate din elemente de mi ci dimensiuni,
cu consum mic de energie, să funcționeze în o are varietate de condiții, să fie flexibile din punct de
vedere funcțional) reconfigurabile, reprogramabile), să accepte elemente heterogene și să ofere
elemente de securitate.
Din punct de vede re al structurii unei rețele wireless, ea este concepută după modelul O.S.I. [7]:

Nivelul fizic asigură interfața de transmisie a datelor în mediul fizic.
La nivelul legătură de date are loc detecția și corecția erorilor prec um și managementul fluxului
de date
Nivelul de rețea asigură rutarea datelor în cadrul rețelei de senzori. Întrucât senzorii prezintă o
mulțime de limitări hardware, acest nivel își realizează funcțiile în condițiile unei cantități limitate de
memorie și c u constrângeri referitoare la energia consumată.
Nivelul transport asigură controlul congestiilor și fiabilitatea transmisiunilor. Are o importanță
mare în cazul în care sistemul este nevoit să acceseze alte rețele, asigurând funcții de gateway.
Nivelul a plicație are implementate mecanisme de management al traficului și asigură interfața
cu aplicații cu ajutorul unei mari varietăți de protocoale, majoritatea adaptate pentru consum minim de
energie.
În afară de acestea, mai există 3 nivele care au funcții i mplementate în cele prezentate anterior,
de management al energiei, al conexiunilor și al proceselor.
Nivelul de management al energiei asigură consumarea unei cantități minime de energie pentru
achiziția, prelucrarea și transmiterea datelor.
Nivelul de ma nagement al conexiunilor are ca scop configurarea -reconfigurarea senzorilor
pentru a stabili sau a menține funcționarea rețelei.
Nivelul de management al proceselor este responsabil cu distribuția sarcinilor pentru a asigura
eficiența energetică și prelung irea duratei de funcționare a senzorilor.
Din punct de vedere structural, componenta principală a unei WSN este nodul. Acesta este
format dintr -o interfață radio, senzor/senzori, sursă de energie și un element dotat cu capacitate de
calcul (microprocesor, microcontroller, DSP, etc.)

Referitor la tehnologiile de acces la infrastructura de comunicații, ele sunt direct determinate de
aplicațiile rețelei de senzori, putând avea dimensiuni de la de ordinul metrilor la mai mulți kilometri, pe
baza funcțiilor care trebuie îndeplinite de rețea și de dimensiunile zonei supuse monitorizării.
Ca topologie, o rețea wireless de senzori este formata dintr -un număr de noduri cu capacitate
de autoorganizate, conectate printr -un gateway la o rețea de comunicații. La impleme ntare, inițial, după
se senzorii au fost distribuiți în mediu, aceștia își comunică starea și recepționează același fel de
informații de la senzorii adiacenți. Urmează faza de conectare într -o rețea și, în final de calculare a
rutelor în vederea transmiter ii informațiilor achiziționate. Fiecare nod are capacitatea de transmitere și
recepție de date. Întrucât senzorii sunt de cele mai multe ori autonomi din punct de vedere energetic,
rețeaua și rutele nu sunt fixe, ele suferind transformări în timpul funcțio nării, ca urmare a apariției și
dispariției unor noduri componente și pentru minimizarea energiei consumate.
Datorită acestor caracteristici, rețelele WAN sunt caracterizate prin autoorganizare,
autoadaptare, existența resurselor limitate de energie și in stabilitatea structurii de comunicații.
Modalitatea de realizare a comunicației în cadrul unei WSN reprezintă una din principalele
constrângeri care apar în cadrul acestor aplicații. În funcție de dimensiune și necesarul de bandă de
comunicații, se pot înt âlni rețele WLAN(wireless local area network), WMAN(wireless metropolitan area
network ), WPAN(wireless personal area network ) sau WWAN(wireless wide area network ).
Din punct de vedere al tehnologiilor noi de comunicație care oferă o lățime extinsă de bandă de
comunicații, ele nu reprezintă o soluție care să asigure funcționarea unei rețele WSN datorită condițiilor
de mediu (interferențe electromagnetice, resurse radio minime), datorită necesității de operare în timp
real și a constrângerilor referitoar e la cantitatea de energie disponibila.
Numărul mare de noduri, cantitatea de date achiziționate și transmise, scalabilitatea, mediul
înconjurător, tipul aplicațiilor, eterogenitatea componentelor sunt provocări care direcționează evoluția
și aplicabilitat ea rețelelor WSN.
Aplicațiile WSN se adresează atât domeniilor în care timpul real este o cerință majoră cât și
domeniilor care necesită inclusiv funcționare offline. În marea majoritate, WSN sunt utilizate pentru
achiziția, prelucrarea și transmiterea inf ormațiilor atât pentru analiza online cât ți pentru cea offline.
Dimensiunea este de obicei limitată iar cerințele referitoare la întârzieri sunt minime, sistemul fiind
optimizat pentru fiabilitate și consum minim de energie. Necesitatea de monitorizare și analiză în timp
real și aria geografică mare modifică constrângerile din punct de vedere al parametrilor comunicațiilor și
al modului de realizare a conexiunilor, implicând adoptarea și dezvoltarea de noi tehnologii în acest
domeniu.
Ca urmare a posibilit ății de a monitoriza medii, procese, activități, rețelele de senzori wireless
sunt în continuă dezvoltare și, ca urmare, și cantitatea de date achiziționate, care necesită prelucrare,
stocare și analizare. Heterogenitatea echipamentelor, atât senzori, cât și elemente de prelucrare a
datelor și de comunicații implică stabilirea și respectarea standardelor pentru a asigura o funcționare
corectă și predictibilă.
Arhitectura este determinată atât de tipul de mediu în care este implementată rețeaua, cât și de
cerința de a funcționa în timp real, de numărul de noduri și de parametrii radio existenți (distanța dintre
noduri, interferențe electromagnetice) .

Securitatea unei rețele de senzori wireless este un compromis între funcționarea sigură și
vulnerabilitățile implicate de comunicațiile radio, de capacitatea de calcul și resursele finite de energie.
Mai mult, rețelele WSN sunt implementate inclusiv în zone accesibile, cu implicații importante din punct
de vedere al securității. Pentru a asigura dezvoltarea unui sistem sigur, elementele de securitate sunt
integrate în fiecare componentă a sistemului și în fiecare etapă de dezvoltare, deciziile în acest send
fiind de obicei adoptate după o etapă de analiză a riscurilor .

2.1.7 Smart -dust

Conceptul „smart -dust” presupu ne un sistem distribuit de elemente microelectromecanice
(MEMS) care detectează anumite condiții din mediul înconjurător, fiind practic o particularizare a
rețelelor de senzori wireless.
Această tehnologie este o combinație miniaturală de senzori, element e de calcul, elemente de
comunicație și sursă de energie. Componentele se doresc a fi atât de ușoare si cu dimensiuni atât de
reduse astfel încât să poată rămâne suspendata în mediu. Particulele respective poartă și denumirea de
„motes”.
Concepția hardwar e a elementelor este o provocare datorită dimensiunilor, fiind necesară
integrarea tehnologiilor care să permită miniaturizarea și consumul foarte redus de energie. Este
imposibil să fie implementate elemente radio care să fie compatibile cu tehnologiile c ele mai răspândite
datorită consumului mare de energie și a necesității de a utiliza antene de mari dimensiuni.Ca urmare,
este nevoie ca senzorii să conțină tehnologii adaptate pentru a respecta constrângerile.
Cea mai mare componentă a unui astfel de se nzor inteligent este sursa de energie. Din acest
motiv, este important ca energia consumată să fie minimă pentru a putea respecta cerințele de
autonomie și miniaturizare, dezideratul fiind de a alătura senzori, elemente de calcul și de comunicație
în devic e-uri de ordinul milimetrilor care să formeze baza unei rețele masive de senzori.
În mod uzual, componentele rețelei folosesc comunicații radio pe distanțe scurte pentru a
transmite datele, ceea ce favorizează minimizarea și consumul redus de energie. Mes ajul este transmis
între elemente adiacente, până la destinație.
Din punct de vedere al fiabilității, datorită numărului mare de senzori, o rețea astfel construită
își îndeplinește sarcinile chiar și în condițiile dispariției unor rute.
Când un senzor es te adăugat în rețea, acesta se adaptează pentru a interacționa cu ceilalți iar
când un senzor nu mai funcționează, cei adiacenți îi preiau funcția.
Elementele software incluse în mots sunt responsabile de activitatea acestuia, de management
al energiei și de comunicații în rețeaua astfel construită.

Limitările și tendințele de evoluție ale tehnologiei în acest domeniu sunt:

– Deoarece bateriile nu sunt de obicei reîncărcabile, nodurile devin nefuncționale după
epuizarea resursei energetice
– Datorită duratei de viață finite, nodurile nu pot fi unic adresate prin identificatori globali
– Datorită resurselor energetice și a constrângerilor referitoare la dimensiuni, resursele de
calcul, de achiziție de date și comunicații sunt minime
– Elementele smart -dust sunt sp ecializate, în consecință vor oferi rezultate bune în
condițiile pentru care au fost proiectate
– Rețelele formate sunt dinamice, funcționarea acestora nefiind uniformă
– Pentru a fi eficiente energetic, noile tehnologii trebuie adaptate pentru funcționare cu
astfel de constrângeri.
– Dimensiunile reduse ale nodului implică dimensiuni reduse ale componentelor acestuia,
inclusiv a senzorilor. Capacitatea de detectare a unui senzor este direct proporțională cu
dimensiunea acestuia, deci cu cât sunt mai mici, cu atâ t este necesară creșterea
sensibilității. Totodată, dimensiunile sunt date de limitările tehnologice existente la
momentul producerii elementelor componente.

2.1.8 Ambient intelligence

Conceptul se refera la mediul electronic ce interacționează activ omul fii nd prezent în activitățile
zilnice ale utilizatorului în mod natural. Inteligența ambientală este o combinație de calcul pervaziv,
calcul raportat la context, internet of things, toate raportate la comportamentul uman.
Caracteristicile acestui concept au fost identificate în [8] ca fiind:
– Integrarea – prin plasarea la scară largă de elemente de calcul dedicate în mediul
înconjurător
– Raportarea la context – prin identificarea utilizatorului, locației și contextului pentru a
desfășura activități adaptate la acestea
– Adaptarea – prin învățare
– Anticiparea – prin urmărirea scopului.
Din punct de vedere al arhitecturii, în [9] autorul propune o arhitectură generică pentru un
sistem de inteligență ambientală:

Figure 1 Arhitectura generică pentru un sistem de inteligență ambientală [9]

Caracteristica de bază a inteligenței ambientale este capacitatea de a acționa în favoarea
utilizatorului, în mod autonom. Pentru aceasta, sistemul trebuie să fie capabil să învețe și să recunoască
activităț i din analiza datelor achiziționate din mediu și prin gruparea acestora (clusterizare) în funcție de
tipul de activitate descris.
Deoarece elementele de inteligență ambientală sunt plasate în mediu, datele achiziționate și
prelucrate de acestea trebuie să fie raportate la context, iar sistemul trebuie să fie capabil să îl detecteze
și să îi anticipeze dinamica.
Acest model de funcționare plasează inteligența ambientală la intersecția mai multor domenii:
inteligența artificială, interacțiunea om -calculator, calcul pervaziv, comunicații, senzori/elemente
efectoare și are la bază etape de învățare/validare, de adaptare la factorul uman.

2.1.9 Virtualizarea

Virtualizarea are ca scop crearea unei versiuni virtuale a unei resurse. Aceasta poate fi element
hardware, element software(aplicație sau sistem de operare), spațiu de stocare, rețea de comunicații.
Interacțiunea cu resursele virtuale trebuie să fie identică cu interacțiunea resurselor respective reale. În
toate tehnologiile de virtualizare există un nivel de a bstractizare între resursele reale și utilizator, care
are rolul de a realiza toate rolurile entității fizice fără ca aceasta să fie prezentă.
Din punct de vedere al avantajelor, virtualizarea oferă flexibilitate întrucât resursele virtuale sunt
ușor de ma nipulat, consolidarea infrastructurii (pe același suport hardware pot exista mai multe
componente virtuale) precum și securitate. Ca dezavantaje, în cazul defectării componentelor hardware
sau software care susțin funcționarea elementelor virtuale, impactu l este major, sunt necesare resurse
hardware și software suplimentare, crește complexitatea în cazul depanării, sunt introduse noi
instrumente de management.

a. Virtualizarea hardware

Virtualizarea hardware se referă la abstractizarea resurselor hardware de cele software. Dacă
în
cadrul unui mediu fizic tradițional resursele software au acces direct la cele hardware, în mediul virtual
resursele software accesează resursele hardware printr -un nivel intermediar, numit hypervisor.

Figure 2 Virtualizarea hardware
Avantajele virtualizării hardware constau în faptul că se pot crea mai multe entități numite
mașini virtuale cu diverse sisteme de operare pe aceeași platformă fizică, poate fi realizat

managementul mai multor servere fizic e cu o singură aplicație, asigură optimizarea funcționării
hardware prin distribuirea dinamică a resurselor.
Virtualizarea hardware poate fi completă (Full virtualization), poate fi paravirtualizare, sau
virtualizare asistată hardware.
Virtualizarea comp letă este tipul de virtualizare în care sistemul de operare rulează nemodificat
utilizând hardware -ul virtual. La nivel de utilizator, este transparent hardware -ul fizic, fiind prezentat cel
virtual. O astfel de virtualizare permite partajarea sistemului d e calcul între mai mulți utilizatori,
realizează izolarea între aceștia și optimizează funcționarea componentelor fizice.
Paravirtualizarea este tipul de virtualizare în care sistemul de operare utilizează componente
software specifice pentru a putea rula pe hardware -ul virtual. Sunt utilizate mai puține resurse hardware
decât im cazul virtualizării complete.
Virtualizarea asistată hardware este tipul de virtualizare în care sistemul de operare utilizează
funcții specifice implementate la nivel hardware, acestea oferind o funcționare performantă a
aplicațiilor.

b. Virtualizarea aplicațiilor

Virtualizarea aplicațiilor presupune izolarea programelor de sistemul de operare pe care sunt
executate, prin existența unui nivel intermediar, nivelul de virtualizare , între sistemul de operare și
aplicație.
Din punct de vedere al implementării, virtualizarea aplicațiilor poate de tipul:
– Application streaming – în care componentele necesare aplicației (date, parametrii de
funcționare, etc.) sunt furnizate în momentul în care sunt necesare
– Remote desktop – este de fapt virtualizarea prezentării, aplicația rulând pe o altă resursă
hardware decât pe cea pe care este prezentată
– Desktop virtualization – în care întreg desktopul sau părți din acesta este separat de
elementul de calcul fizic care este utilizat pentru a -l accesa.

Figure 3 Virtualizarea aplicațiilor

Ca avantaje, virtualizarea aplicațiilor permite rularea acestora în alte medii decât în cele în care
sunt native, reduce complexitatea în cazul migrării la alte sisteme de operare, folosește mai puține
resurse decât în cazul folosirii mașinilor virtuale, reduce complexitatea administrării și integrării.
Din punct de vedere al limitărilor, nu orice aplicație poate fi virtualizată și de obice i sunt necesare
mai multe resurse (atât cele pentru aplicație cât și cele pentru serviciul de virtualizare).

c. Virtualizarea spațiului de stocare

Virtualizarea spațiului de stocare presupune gruparea mai multor resurse de stocare din
cadrul unei rețele î ntr-o singură entitate care este prezentată ca un spațiu de stocare continuu. Această
virtualizare poate fi realizată la nivel de bloc de date sau la nivel de sistem de fișiere.
În cadrul virtualizării la nivel de bloc de date, aceste blocuri pot fi contr olate ca și volum de date,
făcând abstracție de sistemul de fișiere, fiecare dintre aceste blocuri putând fi formatat cu propriul
sistem de fișiere. Acest mod de virtualizare oferă performanțe mai bune decât virtualizarea la nivel de
sistem de fișiere, fie care bloc de date poate fi tratat ca un element hardware de stocare de sine stătător
și formatat în consecință, este ușor scalabil.
În cazul virtualizării la nivel de sistem de fișiere, spațiul de stocare este configurat cu un protocol
(de exemplu NFS) i ar fișierele sunt stocate și accesate din acest loc.
Avantajele virtualizării la nivel de sistem de fișiere sunt constituite din faptul că este ușor de
implementat, fișierele sunt vizibile, putând fi accesate din mai multe sisteme de operare, costurile
implementării și întreținerii sunt mici.

d. Virtualizarea rețelei

Virtualizarea rețelei implică crearea unei infrastructuri logice de comunicații, separată
de infrastructura hardware de bază a rețelei, dar utilizând echipamentele fizice componente ale
acesteia.
Virtualizarea rețelei se poate realiza prin tehnologii SDN (Software Defined Networking) sau prin
tehnologii NFV(Network Functions Virtualization).
NFV oferă un mod de dezvoltare și management al serviciilor de rețea având ca scop
optimizarea aces tora prin decuplarea dintre hardware și software, flexibilizarea implementării funcțiilor
de rețea și operarea în mod dinamic, în funcție de dinamica rețelei.
ETSI, prin „Network Functions Virtualisation(NFV) – Architectural Framework” (ETSI GV NFV 002
V1.1.1 (2013 -10)) a sintetizat un set de directive de standardizare pentru implementarea NFV.
Arhitectura de referință propusă este prezentată în figura următoare:

Figure 4 Arhitectura de referință NFV [10]

În cadrul arhitecturii de referință, VNF(Virtual Network Functions) sunt funcțiile virtuale
implementate în cadrul rețelei reale existente. EMS (Element Management System) efectuează
managementul funcționat pentru unul sau mai multe VNF -uri.
Infrastructura VNF este formată din elementele hardware și software care compun mediul în
care VNF este implementat și poate fi distribuită, în funcție de întinderea geografică a rețelei.
Virtualizarea realizează decuplarea software -ului VNF de hardware, asigurând independența
față de resur sele fizice. Nivelul de virtualizare asigură:
– abstractizarea și partiționarea logică a resurselor fizice
– permite VNF să utilizeze resursele virtuale
– oferă resursele virtuale în funcție de necesități.
Managerii infrastructurii virtuale (VND Managers) asigură administrarea resurselor existente și
operații de colectare de informații referitoare la utilizarea resurselor, la starea elementelor
componente, precum și analiza performanțelor NFV din punct de vedere al infrastructurii.
Orchestratorul este respo nsabil cu sincronizarea funcționării și managementul infrastructurii
NFV și a resurselor software pentru funcționarea optimă a serviciilor de rețea.
Managerii VNF (VNF Managers) asigură administrarea elementelor VNF (adresare, update,
distrugere, etc.)
SDN (Software Defined Networking) presupune abordarea administrării rețelei prin decuplarea
nivelului care decide unde este rutat traficul(Control Plane) de nivelul care se ocupă de trimiterea
traficului spre destinație(Data Plane), în acest fel fiind adminis trată rețeaua prin funcții de nivel înalt.
Dacă în cazul abordării tradiționale, Control Plane și Data Plane coincid, în cazul SDN cele două niveluri
sunt independente.

Figure 5 Arhitectura tradițională a rețelei

Figure 6 Arhitectura unei rețelei SDN

O arhitectură SDN este:
– direct programabilă – controlul rețelei este programabil pentru că este decuplat de funcția
de rutare

– agilă – decuplarea nivelului de control de nivelul de date permite ajustarea din amică a
parametrilor rețelei în funcție de cerințe
– bazată pe standarde publice – ceea ce simplifică administrarea și permite integrarea
simplă a diverselor elemente hardware dezvoltate de diverși producători
– centralizată din punct de vedere al managementul ui – controller -ul SDN menține o
imagine de ansamblu a rețelei la un moment de timp dat
– configurabilă software – permite administrarea, configurarea, optimizarea în mod direct
prin componente software de cătra administratori.
SDN a apărut ca o evoluție nor mală a rețelelor clasice, ca urmare a direcțiilor de dezvoltare a
sistemelor informatice și a noilor cerințe din punct de vedere al traficului de date. Schimbarea pattern –
ului de trafic, ca urmare a rețelelor dinamice, a conceptului „big data” ce presupun e lățimi de bandă din
ce în ce mai mari, a serviciilor cloud au favorizat apariție și dezvoltarea tehnologiei SDN.
Elementul central al acestei arhitecturi este controller -ul SDN, un nivel intermediar între cel fizic și
cel al aplicațiilor, el realizând a bstractizarea nivelului fizic si oferind un set de funcții de nivel înalt pentru
administrare. La interfața dintre nivelul de control și nivelul infrastructurii hardware se află protocolul
care oferă acces la nivelul de rutare al echipamentelor de rețea, î n acest moment cel mai cunoscut fiind
protocolul OpenFlow dezvoltat de Open Networking Foundation

Figure 7 Arhitectura SDN

2.1.10 Cloud computing

Cloud computing reprezintă un ansamblu distribuit de servicii de calcul, aplicații, s tocare de
date, oferite utilizatorului fără ca să fie nevoit să cunoască amplasarea și configurația fizică a
echipamentelor care furnizează aceste servicii. Serviciile sunt organizate ca stivă fiind formată din:
– Software ca serviciu (Software as a Service) (SaaS)
– Platforma ca serviciu (Platform as a Service) (PaaS)
– Infrastructura ca serviciu (Infrastructure as a Service) (IaaS)
Caracteristicile principale ale serviciile oferite în cloud sunt disponibilitatea și scalabilitatea.

Figure 8 Nivelele oferite de cloud -computing

a. Software ca serviciu

Software -ul ca serviciu reprezintă un model de distribuție de software de către un furnizor care
deține aplicația și o pune la dispoziție utilizatorilor printr -o interfață cu ajutorul servici ilor de rețea. În
acest fel utilizatorii nu mai sunt nevoiți să își instaleze aplicația pe propriile echipamente de calcul.
Acest tip de serviciu are o disponibilitate ridicata, deoarece fiind online poate fi accesat de oriunde
și în orice moment.
SaaS ofe ră o bună scalabilitate, actualizările sunt efectuate centralizat, în cloud de către providerul
serviciului, utilizatorii nu mai sunt nevoiți să își achiziționeze propriile licențe, plata efectuându -se sub
formă de abonament, în funcție de utilizarea soft ware -ului.
În general aplicațiile sunt distribuite prin intermediul Internet -ului cu ajutorul unui browser sau
printr -un client dedicat, în funcție de implementare și drepturile utilizatorului.

b. Platforma ca serviciu
PaaS este un serviciu din cadrul cloud prin care se oferă utilizatorului o platforma pe care acesta
să își poată dezvolta și rula propria aplicație.
Pe o astfel de platforma utilizatorul nu are date referitoare la arhitectura hardware pe care aplicația
va rula, sistemului de operare, resursel e de stocare sau alte detalii ce țin de infrastructură.
PaaS este o soluție de middleware ce abstractizează toate aceste elemente, oferind utilizatorului o
interfață prin care să își creeze propriile aplicații fără a avea nevoie de dezvoltarea și administ rarea unei
infrastructuri.
PaaS poate fi oferit ca serviciu public în infrastructura cloud, unde utilizatorul are un set redus de
instrumente de administrare, această activitate fiind efectuată de provider, ca serviciu privat, sau sub
formă de software imp lementat pe un serviciu Infrastructure as a Service.

c. Infrastructura ca serviciu
IaaS este cel mai de jos nivel din stiva de servicii de tip cloud. Daca la SaaS si PaaS
elementele de infrastructură nu erau disponibile utilizatorului, în cazul IaaS utiliz atorul are acces la toate
acestea. Un serviciu de tip IaaS este o aplicație de gestiune a unor mașini virtuale, a unei infrastructuri
virtualizate.
Utilizatorului i se oferă la cerere resurse virtual de procesare, de stocare, de rețea, de securitate
precum si aplicații pe baza unei partajări dinamice a resurselor.

Caracteristicile sistemelor cloud:

Un sistem cloud trebuie să fie definit de următoarele caracteristici:

– Mobilitatea – accesul la resursele din cloud poate fi făcut de oriunde, cu condiți a
existenței accesului la rețea
– Sistemul de „mulți -închiriere” permite partajarea resurselor.
– Fiabilitatea este îmbunătățită întrucât se utilizează o resursă virtuală
– Scalabilitate prin modificarea dinamica (la cerere) a resurselor.
– Mentenanta ușoară a apl icațiilor de cloud computing – deoarece aplicațiile nu trebuie sa
fie instalate pe computerul fiecărui utilizator.

Avantajele unei structuri de tip cloud

Scalabilitate

Mediul virtualizat ce operează pe infrastructura sistemelor hardware existente în cl oud asigură
aplicațiilor resursele necesara într -un mod eficient prin modelarea instanțelor de procesare pe baza
necesităaților acestora. Un sistem cloud asigura faptul ca echipamentul hardware existent funcționează
la randament maxim.

Flexibilitate

Resursele oferite trebuie sa se poată scala cu ușurința în mod automat, la cerere, fără a fi necesară
intervenția utilizatorului și într -un mod transparent pentru beneficiarii serviciilor oferite. Este urmărită
eficiența maximă a utilizării de beneficiarii se rviciilor.

Disponibilitate temporală

Caracteristica permite utilizatorului de aplicații obținerea resursele necesare de calcul, sau cel
puțin potențialul de a utiliza anumite resurse de calcul, printr -o solicitare înainte de necesitatea utilizării
aces tor resurse și punerea la dispoziție a lor conform datelor din solicitare.

Mobilitatea

Accesul ubicuu se refera la caracteristica cloud computing de a putea accesa orice resursă

componentă a cloud -ului, de oriunde, cu condiția existenței accesului la rețea.

Virtualizare completă

Indiferent de mărimea scalării modul de utilizare a resurselor oferite trebuie să rămână constant și
uniform.

Dezavantajele unei structuri de tip cloud

Asigurarea securității

Daca într -o abordare convenționala, elementele de calcul sunt separate fizic, într -un sistem
cloud acest avantaj dispare. Separarea logica a entităților virtuale și mai puțin din punct de vedere fizic
ce stau la baza sistemului are implicații din punct de vedere al securității, la nivelul software -ul de
virtualizare nivelurile de acces trebuie sa fie clar definite și administrate. Vulnerabilitățile clasice sunt
combinate cu vulnerabilități specifice sistemelor ce sunt distribuite și pun în comun resurse, fiind
prezente riscuri ca datele private sa ajung ă în zone publice, ca datele să fie alterate sau pierdute, riscuri
referitoare la managementul informațiilor de autentificare, referitoare la interfețe și API -uri puse la
dispoziție de furnizorul de servicii, riscuri referitoare la atacuri sau la abuzul de servicii disponibile când
infrastructura nu asigură un cadru bine definit al drepturilor și provizionarea ineficientă a resurselor.

Asigurarea resurselor de calcul promise

Deoarece în sistemul cloud, noțiunea de server fizic dispare, fiind înlocuită d e entitatea virtuală,
de obicei providerul va trebui să specifice puterea de calcul a unei entități raportate la soluțiile fizice
existente în acel moment. Dezavantajul în acest caz provine din existența a numeroase echipamente cu
caracteristici heterogen e, ceea ce generează dificultăți în efectuarea comparațiilor.
Ca urmare a virtualizării, resursele fiind partajate între utilizatori, este necesară existența și
asigurarea unui mecanism funcțional care să asigure oferirea de servicii la un nivel cel putin minim
stabilit iar creșterea numărului de beneficiari ai cloud -ului, cu implicații asupra resurselor utilizate, va
trebui să se regăsească și în dezvoltarea din punct de vedere tehnic.

Toleranța la defecte – Integritate, Redundanta

În sistemul cloud, to leranța la defecte, atât din punct de vedere al resurselor hardware cât și al
comunicațiilor este efectuată cu ajutorul elementelor software, dispariția anumitor entități fizice având
implicații asupra entităților virtual găzduite pe acestea. Chiar dacă pa rtajarea implică o redundanță
intrinsecă prin alocarea dinamică, existența și funcționarea mecanismelor de recuperare a datelor ca
urmare a evenimentelor hardware/software reprezintă o caracteristică importantă a sistemelor de tip
cloud.

Consumul de energ ie – Minimizarea pierderilor

Întrucât infrastructura cloud este caracterizată de o disponibilitate ridicată, consumul de energie
este relativ constant. Un software de virtualizare trebuie sa fie eficient atât din punct de vedere al
performantei, cât și di n cel al consumului de energie, întrucât minimizarea acesteia nu poate fi efectuată
prin simpla oprire a unor elemente fizice din cloud .

3 Optimizarea multicriterială

Optimizarea reprezintă activitatea de selectare din mulțimea soluțiilor posibile ale unei
probleme a acelei soluții care este cea mai bună în raport cu un criteriu predefinit. Dacă o problemă de
optimizare cu un singur obiectiv, presupune identificarea unui vector X care minimizează/maximizează
funcția F(x), cu respectarea unor constrângeri ( de inegalitate, de egalitate, de mărginire), o problemă de
optimizare multiobiectiv este necesar a fi abordată în mod diferit. În cazul existenței unui singur obiectiv
scopul este de a găsi o soluție care de obicei este optim global.
În cazul obiectivelor multiple, există un set de soluții care îndeplinesc cerințele impuse, iar din
acest set, selecția se face după anumite criterii. Mai precis, problemele multiobiectiv sunt acelea în care
scopul este de a optimiza k funcții obiectiv, simultan.
Datorită exi stenței mai multor deziderate, de multe ori cu tendințe de evoluție opuse, noțiunea
de optim presupune identificarea unei mulțimi a soluțiilor de compromis, dificultatea majoră legată de
problemele multiobiectiv constând în necomparabilitatea diferitelor s oluții identificate. Pentru a stabili o
relație de ordine în această mulțime, se utilizează optimizarea Pareto.
Soluțiile optime în sens Pareto sunt optime în sens general, deoarece în spațiul soluțiilor nu
există soluții mai bune dacă sunt luate în consid erare toate obiectivele. Optimul Pareto presupune o
relație de dominare în grupul de soluții ale problemei de optimizare multiobiectiv.
Conceptul central al optimizării Pareto este cel de soluție nedominantă. Aceasta este o soluție
care:
– nu este mai puț in bună decât celelalte soluții

– este mai bună decât orice altă soluție în raport cu cel puțin una din funcțiile multiobiectiv.
Un sistem informatic este un sistem complex, format din o sumă de elemente de calcul
interconectate printr -o rețea de comunica ții iar de cele mai multe ori, atât elementele de calcul, cât și
rețeaua sunt caracterizate de o mare diversitate. Optimizarea unui astfel de sistem presupune o
abordare multicriterială, determinată de mulțimea de parametrii impuși cât și de constrângerile
existente referitoare la parametrii de funcționare. Din punct de vedere al elementelor de calcul,
optimizarea presupune abordarea atât a fluxului de prelucrare a datelor cât și a managementului
alocării resurselor de calcul și de memorie luând în consider are faptul că structura sistemului este de
multe ori dinamică.
Din punct de vedere al comunicațiilor, funcționarea rețelei este determinată de combinația de
protocoale și strategii de rutare, folosite pentru a asigura transportul informației între benefic iari. Ca
urmare a dinamici parametrilor rețelelor moderne, o soluție de rutare care este optimă pentru un set
de parametrii, nu mai este o soluție fezabilă pentru alt set de parametrii. Mai mult decât atât, în cazul
rețelelor cu un grad mare de dinamicita te algoritmii clasici de rutare prezintă dificultăți în a găsi soluții în
timp util și cu respectarea calității serviciilor.
Pe lângă acestea, optimizarea presupune nu numai managementul inteligent al capacităților
sistemului, cât și implementarea unor a lgoritmi performanți, adecvați resurselor și cerințelor pe care vor
trebui să le îndeplinească.
Este ușor de observat că în sistemele de calcul moderne, majoritatea problemelor implică
obiective multiple, de multe ori opuse din diverse puncte de vedere, c are trebuie îndeplinite ținând cont
de un număr de condiții.
În general, o problema de optimizate multiobiectiv este formată dintr -un număr de parametrii n
care sunt parametrii de decizie, un set de k funcții obiectiv și un număr de m constrângeri. Scopu l
optimizării este să găsească maximul funcției

referitor la

Unde

Iar
x=vectorul de decizie
z=vectorul obiectiv

X=spațiul de decizie
Z=spațiul obiectiv

Constrângerea
determină setul de soluț ii fezabile. Acesta este reprezentat de
mulțimea de vectori de decizie x care satisfac constrângerile e(x):

Imaginea lui
reprezintă regiunea fezabilă în spațiul obiectivelor, fiind descrisă de:

Problemele de optimizare multicriterială devin complicate când obiectivele nu pot fi îndeplinite
simultan. În acest caz, soluție este de fapt un compromis.
Dacă pentru o funcție cu un singur obiectiv setul de soluții fezabile este ordonat raportat la funcția
obiectiv, pentru o funcție multiobiect iv setul soluțiilor fezabile este doar parțial ordonat, fiind necesară
specificarea operatorilor
. Astfel,

Astfel fiind definiți acești operatori, pentru doi vectori de decizie m si n, referitor la relația de
dominare, exista tre i posibilități:

sau

Fiind luate în considerare aceste proprietăți ale relației de dominare, pentru doi vectori de decizie
m si n, se poate defini dominația în sens Pareto astfel:
– m domina n (m
) presupuna ca

– m domina s lab n (m
) presupuna ca

– m este indiferent fata de n (m
) presupuna ca

– m este dominat de n (m
) presupuna ca

– m este dominat slab n (m
) presupuna ca

Pe baza dominației Pareto se poate introduce un criteriu de optimalitate pentru problemele
multiobiectiv. Din acest punct de vedere, vectorul m este optim daca el nu mai poate fi îmbunătățit din
punct de vedere al nici unui obiectiv fără sa se producă o degradare din punct de vedere al altui/altor
obiective, soluția fiind Pareto optimala. Formal, un vector de decizie
este nedominant referitor
la un set
daca
. În acest context, m este optim Pareto daca m este
nedomi nat in raport cu
iar toate solutiile Pareto optimale existente referitor la o problema de
optimizare multiobiectiv formează setul Pareto optimal corespunzător vectorilor obiectiv din
frontul/suprafața Pareto optimala.
Pe baza relației de domi nare se pot defini seturile(fronturile)nedominate. Funcția
genereaza
setul de vectori de decizie nedominați în A, unde
:

Setul
este setul nedominat referitor la A iar setul de vectori obiectiv corespunzatori
)
este frontul nedominat referitor la A. Mai mult decât atât, setul
) este numit setul Pareto
optim iar setul
) este frontul Pareto optim.
Setul Pareto optim conține și soluțiile optime global dar si optimele locale, car e sunt nedominate în
raport cu o anumita vecinătate a lor. Aceasta corespunde optimelor Pareto locale si globale.
Formal, pentru un set de vectori de decizie
, setul Pareto este optim local daca

pentru
si
mai mar i decat 0 iar ||.|| este distanta.
Setul A este optim global Pareto daca

În rezolvarea unei probleme de optimizare multicriterială, pot fi identificate două etape: etapa
de căutare și etapa de luare a deciziilor.
Etapa de căutare a soluției este cea î n care setul fezabil este verificat pentru identificarea soluțiilor
Pareto optime. Spatiile de căutare largi și complexe fac procesul de căutare dificil si exclud utilizarea
metodelor de optimizare specifice programării liniare.
Al doilea aspect se referă la selectarea soluției de compromis din setul Pareto optim, fiind necesară
intervenția operatorului pentru a stabili prioritățile între obiectivele în conflict.
În funcție de modul în care sunt adoptate deciziile și este realizată căutarea în cadrul proble melor
de optimizare multiobiectiv, acestea pot fi împărțite în patru categorii [11]:
– luarea deciziei fără a exista preferințe din partea utilizatorului, soluția este identificata
fără a exista preferințe exprimate
– adoptarea deciziei înaintea căutării, obie ctivele problemei de optimizare multicriteriala
sunt grupate, ceea ce presupune furnizarea apriori de către operator a unui număr de
informații suplimentare referitoare la preferințe; gruparea mai multor obiective intr -un
singur criteriu de optimizare pres upune ca se pot utiliza fără modificări strategii de
optimizare pentru optimizare cu un singur obiectiv
– căutarea înaintea adoptării deciziei, in cadrul căreia optimizarea este efectuata fără a
exista informații prealabile referitoare la soluție iar rezulta tul căutării este setul de soluții
(ideal optime Preto) din care operatorul trebuie sa selecteze una. Luarea deciziei după
realizarea căutării presupune imposibilitatea realizării unei căutări controlate si implicit
imposibilitatea restrângerii spațiului d e căutare, cu implicații negative asupra timpului de
calcul.
– adoptarea deciziei in timpul căutării, operatorul impunând preferințe in timpul procesului
de optimizare, realizând o căutare controlata. In cadrul problemelor de optimizare
multiobiectiv, analiz a in timp real a rezultatelor poate fi problematica din punct de vedere
al operatorului.
În principiu, o metodă de optimizare multiobiectiv trebuie să funcționeze pentru spații de
căutare mari și complexe, și să genereze un set de rezultate optime Pareto sau o buna aproximare a
lor. Abordările tradiționale de rezolvare a problemelor de optimizare multiobiectiv presupun
transformarea problemei într -una cu un singur obiectiv, fiind des întâlnite și simplu de implementat
metoda scalarizării liniare și metoda constrângerilor.

În metoda scalarizării liniare problema de optimizare multicriteriala originala este convertită
într-una cu un singur obiectiv, prin formarea de combinații liniare a celorlalte obiective. Se
urmărește maximizarea/minimizarea funcției

pentru

unde
sunt ponderi cu
.
Rezolvarea problemei de optimizare pentru un [12] număr de combinații de ponderi oferă un set
de soluții. În condițiile în care este utilizat un algoritm de optimizare exacta și toate ponderile sunt
pozitive, metoda va genera doar soluțiile optime Pareto.
Dezavantajul acestei metode constaă în imposibilitatea generării tuturor soluțiilor Pareto
optimale.
Prin metoda constrângerilor se transforma k -1 din cele k obiective în constrânger i. Obiectivul
rămas(ales aleator) este obiectivul pentru o funcție de optimizare cu un singur obiectiv. Astfel,
trebuie maximizata/minimizata

, unde
.

Obiectivul pentru care trebuie maximizata/minimizata problema este
iar
sunt parametrii
care se modifică pentru a obține diferite soluții Pareto optime.
Avantajul acestor abordări tradiționale se rezuma la faptul ca ele transforma funcția de
optimizare multiobiectiv în una de maximizare cu un singur obie ctiv, pentru care există o varietate
mare de soluții de rezolvare. Cu toate acestea, unele tehnici prezintă dificultăți la calcularea si
aproximarea fronturilor Pareto, în general sunt necesare cunoștințe suplimentare pentru
transformarea obiectivelor și n ecesită mai multe etape de optimizare pentru a obține o aproximare
a setului Pareto, ceea ce implică resurse de calcul suplimentare.
O alternativă la abordarea clasică a problemelor de optimizare multicriterială care evită
dezavantajele acestora este calcu lul evolutiv. Acesta este o metodă de rezolvare a problemelor ce
realizează căutarea în spații de soluții potențiale. Funcționează pe baza principiului selecției naturale
a unei populații de indivizi generați aleatoriu. Petru spații de căutare de dimensiun i mici, metodele
clasice, exhaustive, generează rezultate corecte în timp rezonabil. Pentru spații de căutare mari,
complexe, timpul de calcul necesar metodelor clasice pentru a genera rezultate este mare, în acest
caz abordarea evolutivă a problemei fiind o alternativă de luat în considerare.

Tehnicile principale ale calculului evolutiv sunt:
– algoritmii genetici
– programarea genetică
– programarea evolutivă
– strategiile evolutive.
În general, EC are ca scop rezolvarea cu ajutorul algoritmilor evolutivi a pr oblemelor
clasificate ca fiind dificile din punct de vedere computațional. Toți acești algoritmi au ca si caracteristici
de baza:
– existența unei populații de indivizi
– dinamica acestei populații
– propagarea de caracteristici de la părinți la urmași
– evaluare a adecvării indivizilor la problemă cu ajutorul unei funcții fitness.
Funcționarea corectă a acestor algoritmi presupune capacitatea indivizilor bine adaptați de a avea
o influență puternică în cadrul populației prin timpul îndelungat de supraviețuire și capacitatea de a
produce urmași care să propage caracteristicile pozitive în cadrul populației. Această funcționare este
influențată de:
a. dimensiunea populației – o populație de mici dimensiuni are ca efect rularea rapidă a
algoritmului dar influențează neg ativ parcurgerea spațiului soluțiilor și ca urmare de a
exista un risc mare de a genera soluții locale în locul celor globale. Dimensiunea optimă a
populației este determinată atât de capacitatea de calcul disponibilă cât și de problema de
rezolvat. Număr ul de indivizi poate fi atât fix cât ți variabil.
b. Selecția părinților – există mai mulți algoritmi de selecție, în principal bazați pe valoarea
funcției fitness indivizilor. Pentru păstrarea capacității algoritmului de a explora spațiul
soluțiilor, este ne cesară păstrarea diversității. Astfel, alegerea exclusivă pentru
reproducere a unor indivizi cu valori maxime ale funcției fitness conduce la
uniformizarea populației, cu efecte negative asupra rezultatelor produse. Totodată, o
foarte mare diversitate gene rată de alegerea de indivizi puțin adecvați are ca efect timpul
lung de convergență a algoritmului sau chiar imposibilitatea atingerii convergenței.
c. Eliminarea indivizilor din populație – are ca scop evoluția fitness -ului total al populației.
Procesul este diferit, determinat atât de algoritmii evolutivi cât și de problemă, fiind
influențat de elitism. Eliminarea bazată pe acesta are ca influențe negativă uniformizarea
populației sau din contră, o prea mare diversitate, identificarea modalității optime
realizată apriori fiind dificilă. Selecția și eliminarea indivizilor reprezintă unul din
mecanismele de bază, pe baza cărora funcționează algoritmii evolutivi.
d. Reproducerea – mecanismele utilizate pentru reproducere afectează balanța
explorare/exploatare în cazul EA. Explorarea optimă a spațiului de căutare presupune

păstrarea capacitatea de a controla diversitatea, atât prin mutații, cât și prin reproducere
adaptivă sau prin utilizarea mai multor părinți.

3.1 Metode evolutive de optimizare multicriterială a sis temelor informatice.
Concepte

3.1.1 Algoritmii genetici

Algoritmii genetici fac parte din categoria algoritmilor de calcul probabilistic, inspirați de teoria
evoluționistă a lui Darwin, principalele coordonate fiind competiția, selecția, supraviețuirea,
reprod ucerea.

Figura 9. Coordonatele principale ale algoritmului genetic

Algoritmii genetici se referă la un model introdus și analizat de J. Holland în 1975 fiind definite ca
proceduri adaptive care identifică soluția problemei pe baza unui mecanism de selecție naturală și
evoluție genetică. Algoritmul este des folosit pentru probleme în care găsirea soluției optime nu este
ușoară sau timpul de rulare necesar în cazul calculului determinist este prohibitiv.
Algoritmii genetici codi fică o soluție posibilă la o problemă specifică într -o singură structură de
date numită „cromozom” și aplică operatori genetici la aceste structuri astfel încât să mențină
informațiile critice.
Algoritmii genetici pornesc de la o mulțime inițială de soluți i (de obicei aleasă aleator) numită
„populație”. În această populație fiecare individ este un „cromozom” și reprezintă o soluție posibilă a
problemei. În aproape toate cazurile cromozomul este un șir de simboluri (de obicei reprezentat ca un
șir de biți da r pot fi și reprezentări prin numere naturale). Acești cromozomi evoluează pe durata
iterațiilor succesive numite generații. În fiecare generație, cromozomii sunt evaluați utilizând funcții care
măsoară adecvarea soluțiilor la problema dată (fitness).
Din punct de vedere al evoluției genetice, cromozomii sunt purtătorii informației genetice,
numărul lor fiind determinat pentru fiecare individ al unei specii. Genotipul este format din totalitatea
cromozomilor unui individ, cromozomii fiind alcătuiți din gen e. Acestea controlează una sau mai multe
caracteristici ale individului, purtând caracteristicile ereditare și ocupă locuri determinate, numite loci. O
genă poate avea mai multe valori ale caracteristicilor, numite alele. Evoluția are loc la nivelul
cromoz omilor iar selecția naturală favorizează reproducerea cromozomilor care codifică structuri mai
bine adaptate.

Căutarea unei soluții într -un spațiu complex implică un compromis între două obiective
contradictorii, între exploatarea celei mai bune soluții de la momentul respectiv și exploatarea în
continuare a spațiului soluțiilor posibile. Cele două obiective corespund căutării locale, respectiv globale
în spațiul soluțiilor, explorarea presupunând parcurgerea diferitelor regiuni din spațiul soluțiilor și
colectarea de informații iar exploatarea fiind rafinarea soluției (exploatarea informațiilor colectate în
procesul de explorare).

Figure 10. Explorare -exploatare în căutarea genetică

Problema echilibrului între utilizarea soluții lor obținute până la momentul curent și parcurgerea
în continuare a spațiului de căutare pentru a obține soluții noi este specifică problemelor de optimizare.
O alegere prematură a unei soluții poate conduce la obținerea unui rezultat local și nu a unui ge neral,
deci o convergență prematură. Dacă accentul se pune pe explorare, este posibil ca informația obținută
să nu fie utilizată, crescând timpul de rulare a procedurii. Exploatarea și explorarea sunt caracteristici
care pot fi controlate în mod independen t, ceea ce conferă o flexibilitate sporită algoritmilor genetici,
operatorii implicați în acest proces fiind selecția, ca operator de convergență și crossover și mutația ca
operatori de divergență.
Pentru crearea următoarei populații cei mai buni cromozom i din generația (populația) curentă
sunt selectați și noii cromozomi sunt formații folosind unul dintre cei trei operatori genetici esențiali:
– selecția,
– crossover
– mutația.
Selecția asigură faptul că anumiți cromozomi din generația curentă sunt copia ți în acord cu
valoarea funcției lor de adecvare în noua generație ceea ce înseamnă că acei cromozomi cu o
importanță mare au o probabilitate mare să contribuie la formarea noii generații.
Crossover este un alt operator genetic, fiind procesul prin care p e baza a doi cromozomi din
populația curentă sunt formați maxim doi cromozomi pentru populația următoare.
Mutația este procesul prin care un cromozom din populația curentă este modificat și salvat în
noua populație.
Din punct de vedere conceptual, funcțio narea algoritmului genetic respectă schema logică din
figura următoare:

Figure 11. Schema logică a unui algoritm genetic

Etapele algoritmului genetic:
Din punct de vedere funcțional, algoritmul genetic parcurge următoarele etap e:
1. Se codifică datele problemei într -un cromozom.
2. Se generează aleator o populație. Se recomandă ca populația să aibă un număr suficient de mare de
cromozomi (număr variabil, nefiind stabilit un algoritm de calcul a numărului e cromozomi pentru o
problemă; ei fiind soluții aleatoare). Fiecare genă din cromozom este inițializată cu o valoare aleatoare.
3. Pentru fiecare cromozom din populație se calculează adecvarea acestuia ca soluție, folosind funcția de
evaluare (fitness).
4. Dacă s -a găsit un cromo zom pentru care se obține valoarea dorită se termină algoritmul iar acel
cromozom reprezintă soluția problemei (în cazul în care se știe unde dorim să ajungem). O altă condiție
de terminare a algoritmului ar putea fi cazul în care după un număr specificat de pași nu s -au mai
obținut îmbunătățiri (în cazul în care nu știm exact valoarea unde vom ajunge).
5. Folosind rezultatele funcției de evaluare se generează următoare populație astfel:
a. Se vor selecta primii cei mai buni cromozomi din prima populație și se vor copia în noua
populație;
b. Pentru restul din noua populație se vor folosii operatorii de mutație și crossover
6. Se revine la pasul 3.

Codificarea cromozomilor și problema de optimizare
În cazul algoritmilor genetici, două componente principale sunt determinate de problema
abordată: codificarea problemei și funcția de evaluare (de fitness). Cromozomii care reprezintă
codificarea problemei trebuie într -o oarecare măsură să conțină informațiile despre soluția problemei.
Există mai multe codificări, principalele metode care au fost utilizate cu succes fiind codificarea binară
(cromozomul este format din șiruri de 0 sau 1 care reprezintă binar soluția problemei) sau codificarea
prin valoare (cromozomul este format dintr -un șir de valori vector întregi sau reale care pe ansamblu
reprezintă soluția problemei). De asemenea, în funcție de problemă, cromozomii pot avea o dimensiune
fixă sau variabilă. În [12], pentru [13] dezvoltarea unui algoritm adaptiv de rutare în rețea, autorii au
utilizat codarea prob lemei într -un cromozom cu lungime fixă (egală cu numărul de noduri din rețea),
valoarea genelor reprezentând nodurile componente ale rutei, fiind, deci, numere naturale. Dacă ruta
este mai mică decât numărul de noduri, genele rămase vor avea valoarea 0.

Figure 12. Codificarea rutei pentru o rețea (codificare utilizând numere natural)

Cromozomul (4,5,6,7,0,0,0,0,0) reprezintă ruta 4 ->5->6->7

În [13], autorii propun o codificare binară, sub formă de matrice a rutei. Elementele matr icei
sunt 0, dacă între nodurile reprezentate de numărul liniei și al coloanei nu exista legătură direct și 1 dacă
există legătură.
În [14], pentru codarea rutei se utilizează o codificare cu numere natural, fiecare genă
reprezentând un nod al rutei iar cr omozomii sunt de lungime variabilă.
Funcția de evaluare numită și funcția de „fitness” (potrivire) este funcția care ne permite să
evaluăm adecvarea ca soluție pentru fiecare cromozom din populație. Această funcție este de obicei
funcția care reprezintă de scrierea problemei.
12
1n
k
k=d c ,c = dist
(1)
Pentru rețeaua prezentată în Fig.1., în articolul [12], funcția fitness pentru o ruta valida este
determinată de suma costurilor link -urilor dintre 2 noduri adiacente din rută, in conformitate cu for mula
nr. (1).
În timpul rulării algoritmului, intervalele valorilor funcțiilor fitness ale populațiilor de cromozomi
sunt dinamice. Dacă intervalul dintre cea mai mare valoare a fitness -ului și ce mai mică este prea mare,
efectul obținut este convergența p rematură spre o soluție locală, ca urmare a existenței unor indivizi cu
valori ale funcției de adecvare atât de mare în comparație cu ceilalți, încât au o prezență sigur în
generațiile următoare. Dacă, în schimb, diferența dintre cea mai mare valoare a fi tness -ului și cea mai
mică este prea mic, convergența algoritmului este dificilă, necesitând durate mari de timp pentru a oferi
o soluție globală sau, după un număr de generații, fitness -ul mediu este convergent, dar nu a fost găsită
o soluție globală. Pen tru a evita aceste efecte nedorite, se poate ajusta intervalul de valori prin scalarea
fitness -ului, ferestruirea sau prin atribuirea fitness -ului pe baza unui clasament.
Prin scalarea fitness -ului, valorile adecvării sunt modificate pentru a obține o dist ribuție într -un
interval de valori optim pentru problema dată.

Figura 13. Modificarea distribuției funcțiilor fitness

Ferestruirea valorilor de adecvare este similară scalării, dar valorile cu care se modifică
adecvările sunt al ese luându -se în considerare istoricul dintr -un număr de generații anterioare.
Stabilirea fitness -ului pe baza unui clasament presupune numerotarea cromozomilor pe baza
valorii adecvării și selecția în funcție de clasament.

Problema abordată pentru a fi re zolvată prin tehnici genetice poate fi o problemă descrisă de o
funcție cu un singur criteriu sau poate fi o problemă multicriterială. În cazul problemelor multicriteriale
există mai multe combinații de valori care îndeplinesc obiectivele funcției. Acestea reprezintă un set de
soluții optime Pareto.
Pentru optimizări multicriteriale, funcția fitness poate fi o combinație a diverșilor parametrii care
sunt implicați în constrângerile asupra soluției. Aceștia sunt ponderați ca valoare, în funcție de
importanță , ponderile putând fi fixe sau variabile, funcție fiind de forma:
1 1 2 2 12( ) ( ) ( ) … ( )nn nFx f f fw x w x w x   
,
unde w reprezintă ponderile fiecărui criteriu în soluție generală. Stabilirea acestora necesită
cunoștințe apriori.
În [12], autorii propun o funcție fitness (2) care include mai multe subfuncții, unele dintre ele
fiind ponderate, care sunt implicate în alegerea soluției problemei:


  
   
11rt
N
i=
hsFit C = Current C,Cf (
W SubFit Realtime C ,Cf +
N + i SubFit History C,i ,Cf
W)N

 

[15]
(2)

Spațiul tuturor soluțiilor fezabile existente este numit spațiul de căutare sau spațiul stărilo r.
Problemele abordate folosind algoritmi genetici sunt de obicei probleme pentru care căutarea în spațiul
soluțiilor este o problemă complicată sau chiar NP -completă. Soluțiile obținute folosind algoritmi
genetici sunt de obicei considerate ca soluții bun e, care respectă cerințele impuse, nefiind întotdeauna
posibil să se cunoască optimul real

Componentele algoritmilor genetici

Populația

Pe perioada funcționării, un algoritm genetic utilizează o multime de soluții potențiale (o
populație de cromozomi) , împreună cu evaluarea fiecăreia dintre ele (valoarea fitness -ului). Pentru ca
aceste soluții să poată fi utilizate, este necesar ca ele să fie reprezentate (codate) într -o formă care să

permită efectuarea de operații asupra lor. Această codare este sub f orma unui șir de parametrii care
descriu soluția la problema dată, putând fi atât binară, cât și sub forma unui alfabet cu n caractere sau
sub formă de numere naturale. Modul de reprezentare a soluțiilor este direct dependent de problema
de rezolvat si de operatorii genetici, neexistând rezultate concludente care sa stabilească faptul că o
anumită codare garantează o funcționare mai eficientă.
Dimensiunea populației este un parametru important al algoritmului genetic, în cele mai multe
cazuri fiind utiliza tă o valoare fixă. Dacă populația este prea mică, se va atinge mai rapid convergența,
dar căutarea va fi insuficientă, existând riscul detectării unei soluții locale în locul celei generale. O
populație prea numeroasă va parcurge mai ușor spațiul de căutar e dar va necesita resurse de calcul
consistente, cu îmbunătățiri minime din punct de vedere al rezultatelor furnizate. Ca urmare,
dimensiunea populației este determinată de resursele de calcul disponibile.
După stabilirea tipului de reprezentare și dimens iunea populației, prima generație va fi populată
cu cromozomi generați aleator care, ulterior vor parcurge etapa de evaluare.

Evaluarea

Evaluarea indivizilor dintr -o populație este efectuată prin utilizarea unei funcții fintess, rezultatul
fiind o val oare care arată adecvarea soluției la problema dată. Funcția fitness este o parte componentă a
problemei ce se dorește a fi rezolvată și definește în mod măsurabil caractersiticile impuse pentru ca o
soluție să fie validă.

Selecția

Selecția are un rol im portant în cadrul algoritmului genetic. Aceasta decide care dintre indivizii
unei populații vor putea participa la formarea generației următoare.
Scopul selecției este de a asigura mai multe șanse de reproducere celor mai bine adaptați
indivizi dintr -o pop ulație. Procedura urmărește maximizarea performanței cromozomilor dar, în același
timp reduce capacitatea de explorare a spațiului de către algoritmul genetic prin pierderea de material
genetic ca urmare a eliminării de cromozomi. Este operațiunea care asi gură evoluția algoritmului spre
convergență.
Între diversitatea populației și presiunea de selecție există o legătură strânsă. Creșterea
presiunii de selecție conduce explorarea spațiului spre cei mai bine adecvați indivizi, producând o
scădere a diversit ății populației. Ca urmare, o presiune de selecție mare va conduce la o pierdere rapidă
a diversității și implicit la o convergență prematură a algoritmului spre soluții posibil optime locale, nu
globale. O presiune de selecție mică va crește capacitatea d e explorare a spațiului, întrucât în procesul
de căutare vor fi prezenți mai mulți cromozomi diferiți, dar poate conduce la uniformizarea selecției și la
o căutare puțin eficientă.

Metode de selecție a cromozomilor

Un element important în funcționarea a lgoritmul genetic este procedura de selecția a părinților
din populația curentă și generarea noii populații. Aceasta poate fi abordată în mai multe feluri, dar
scopul este de a selecta cei mai buni părinți (în speranța că aceștia vor produce cei mai buni copii).
Pentru realizarea selecției este necesară introducerea unui criteriu de performanță a individului,
urmărindu -se maximizarea performanței. În acest fel, căutarea se desfășoară în regiuni din spațiul
soluțiilor în care soluțiile corespund adecvări i maxime.
Funcția fitness pe baza căreia se face selecția indivizilor trebuie să îndeplinească următoarele
cerințe:
– Să reflecte calitatea cromozomilor ca soluții ale problemei
– Să fie pozitivă.
În rularea algoritmului, ca urmare a selecției performanța tot ală a populației (suma
performanțelor individuale ale cromozomilor din populație) va crește până la o anumită valoare , în
continuare rămâmând constantă, ceea ce semnifică atingerea convergenței algoritmului.
Există mai multe modalități de selecție, cea m ai utilizată fiind selecția proporțională, care
depinde de valoarea fitness -ului cromozomului.

a. Metoda „Roulette Wheel” (metoda ruletei)

Această metodă folosește algoritmul Monte Carlo de selecție. Fiecare individ din populația
curentă este reprezentat p rintr -un spațiu proporțional cu valoarea funcției lui de evaluare. Prin
eșantionări aleatoare succesive din acest spațiu de reprezentare a cromozomilor se asigură faptul că cei
mai buni cromozomi au șanse mai mari să fie selectați la un anumit pas decât c ei cu mai slabi.
Ca dezavantaj, dacă populația este foarte neomogenă, existând un individ cu un fitness mult
superior mediei, el va fi selectat de mai multe ori, fiind prezent aproape exclusiv în populația următoare.
Această caracteristică va conduce la p ierderea diversității populației și la explorarea incompletă a
spațiului soluțiilor, ceea ce conduce la convergența prematură a algoritmului.
Dacă există diferențe mici între valoarea fitness -ului indivizilor, probabilitatea de selecție va fi
relativ egală , producându -se stagnarea evoluției populației iar selecția va fi aleatoare.
Cele două situații trebuie evitate pentru a realiza o procedură de selecție funcțională. O soluție
este scalarea valorilor fitness -ului indivizilor din populație. Această scalare poate fi fixă sau variabilă, în
funcție de evoluția valorii funcției de performanță.

b. Metoda bazată pe ordonare

Prin această metodă, pentru fiecare generație se calculează valoarea fitness -ului pentru fiecare
cromozom. Cromozomii vor fi ordonați în func ție de adecvarea lor iar fiecare va avea o probabilitate de
selecție bazată pe poziția lor în șir și pe o constantă a metodei, numită presiune de selecție.
Întrucât probabilitatea de selecție depinde de poziția relativă în șir a cromozomului și nu de
valo area funcției de adecvare, sunt evitate inconvenientele selecției proporționale.

c. Metoda bazată pe concurs (tournament selection)

Metoda este bazată pe compararea directă a valorilor de adecvare a unui număr de cromozomi
și selectarea celui mai performa nt. Pentru a genera o populație de n cromozomi, este necesară aplicarea
mecanismului de n ori. Selecția prin concurs implementează presiunea de selecție prin concursul a t
cromozomi, unde t fiind mărimea concursului. Creșterea presiunii de selecție se face prin creșterea
numărului de indivizi care iau parte la concurs. Câștigătorul din cadrul unui număr mai mare de indivizi,
în medie, va avea valoarea fitness -ului mai mare decât ăn cazul concursului între un număr mai mic de
indivizi.

d. Elitismul

Metoda a fost introdusă de De Jong și este o formă de selecție care se utilizează în combinație
cu alte metode. Prin aceasta se asigură faptul că cel mai performant individ este păstrat dela o generație
la alta, fără a fi alterat de recombinare și mutație. Prin a ceasta se garantează ca fitness -ul maxim nu va
scădea de la o generație la alta.

Mutația

Mutația este acel operator genetic prin care, dintr -un singur părinte este obținut un singur copil
prin aplicarea unei modificări aleatoare a reprezentării (genotipu lui). Operatorul mutație depinde de
modalitatea de reprezentare cromozomială și are asociat un parametru, pm, care reprezintă rata de
mutație.
Cel mai utilizat operator de mutație în reprezentarea binară consideră fiecare genă a fiecărui
cromozom pentru i nversarea valorii asociate (din 0 în 1, respectiv din 1 în 0) cu o probabilitate pm în

general mică. Numărul valorilor modificate nu este fixat, dar, în medie, dacă populația conține dim
cromozomi cu câte n gene, este egal cu
.
De exemplu, da că în cromozomul părinte

este aplicat operatorul de mutație genelor 2, 3 și 7, rezultă cromozomul modificat:

Setarea ratei de mutație depinde în general de rezultatul dorit, în sensul în care aplicația trebuie
să conducă fie la obținerea unei populați i în care toți indivizii sunt buni (valoare mare a funcției de
evaluare), fie la obținerea unei populații cu un singur individ cu adaptare foarte bună la mediu. În
general, în cele mai multe dezvoltări GA care folosesc reprezentarea binară pentru construir ea spațiului
genotipurilor, parametrul pm este setat în următoarele limite: într -o generație, în medie, este
modificată o singură genă a unui singur cromozom din populație, respectiv în populația curentă este
modificată, în medie, câte o genă din fiecare c romozom.
În cazul reprezentării cromozomiale din mulțimea numerelor întregi sunt două modalități uzuale
de a defini mutația.
Prima dintre ele este resetarea aleatoare prin care, cu probabilitatea pm, valoarea fiecărei gene
este modificată prin generarea a leatoare a unei valori din mulțimea valorilor admisibile pentru gena
respectivă.
O altă variantă de definire este prin intermediul mutației de tip fluaj . Operatorul, cu o
probabilitate p, adaugă/scade o anumită cantitate (de obicei mică) la/din valoarea f iecărei gene a
fiecărui cromozom. În general valorile cu care sunt modificate alelele sunt generate aleator, astfel încât
probabilitatea apariției unei valori mici să fie mult mai mare decât probabilitatea generării unei valori
mari. Mutația de tip fluaj n ecesită setarea parametrilor ce caracterizează probabilitatea cu care sunt
generate valorile ce modifică alelele, deci a numărului de pași efectuați de operatorul mutație în spațiul
de căutare. Determinarea unei setări potrivite a acestor parametri este în general un proces dificil, în
general fiind preferată utilizarea în tandem a mai multor operatori de mutație de acest tip. De aceea, o
variantă alternativă este de a utiliza un operator mutație resetare aleatoare cu rată foarte mică
împreună cu un operato r fluaj care să efectueze modificări mici asupra alelelor.
În cazul reprezentării cromozomiale prin șiruri de numere reale, reprezentate în virgulă mobilă
sunt utilizați în general următorii operatori:
– Mutația uniformă;
– Mutația neuniformă, cu distribuție f ixată.
Mutația uniformă presupune modificarea fiecărei gene
din fiecare cromozom, cu
probabilitatea pm, prin generarea aleatoare uniformă a câte unui număr din
. Deci, dacă gena i,
a cromozomului x a fost selectată pentru mutație,
este generat aleator. Acest tip de

operator este corespondentul mutației prin resetare aleatoare în cazul reprezentării cromozomiale prin
șiruri de numere întregi.
Mutația neuniformă, cu distribuție fixată, este una dintre c ele mai des utilizate în reprezentările
cromozomiale în virgulă mobilă și este corespondentul operatorului de mutație fluaj. Operatorul este
proiectat astfel încât cantitatea de informație modificată să fie mică. Aplicarea lui asupra unei gene i,
, presupune modificarea valorii curente cu o valoare generată, rezultatul fiind apoi adus pe
intervalul
.
În cadrul algoritmilor genetici, mutația este operatorul care asigură diversitatea populației de
cromozomi și, implicit, parcurgerea întreg spațiului de căutare. Diversitatea este un parametru
important al algoritmilor genetici și este implicat direct în implementarea opartorului de mutație.
Diversitatea poate fi estimată atât în funcție de spațiul genotipic cât și în funcție de
spațiul fenotipic. În [15] DeJong a propus o estimare a diversită ții populației bazat pe măsurarea
variației pentru fiecare caracteristică fenotipică specific ă. În spațiul genotipic poate fi folosită
entropia ca o măsură a dezordinii în popula ția ca în [16] și distanța Hamming conform studiilor
prezentate în lucrarea [17]. În [18], Morrison și DeJong au introdus o măsură unitară a
diversității populației bazată pe conceptul de moment de iner ție pent ru a măsura distribu ția
masei în spa ții multidimensionale. De a semenea au explicat rela ția dintre măsurile fenotipice (
variație în valorile pentru elementele de fenotipice ) și genotipice obi șnuite ( Hamming distan ță )
și acest nou concept .
În [19] autorul propune o nouă procedură de mutație a cromozomilor din popul ație pentru a
asigura o căutare completă a spa țiului soluție. Pentru a evita găsirea unei solu ții locale , popula ția de
cromozomi trebuie să aibă genele distribuite în întreg spa țiul de căutare a problemei. Pentru a asigura
acest lucru , la fiecare itera ție , va fi calculat un "cromozom central" . Acesta nu va f i în mod necesar o
soluție pentru această problemă. Fiecare genă din acest cromozom va fi media aritmetică a tuturor
genelor de la aceea și poziție pentru toți cromozomii popula ției. Cromozomul centra l va fi de forma:
[ (0), (1),…, ( )]i i i in m m m m
(3)
unde
0( ) ( ) /N
ij
jk k Nmx

(4)

N este numărul de cromozomi din generație și x(k) este gena numărul k a cromozomului.
Când algoritmul este convergent, distan ța dintre acest cromozom central și majoritate a
cromozomilor are o valoare mică . Distanța este de forma:
0( , ) | ( ) ( ) |N
kk kkidist n n yyxx

(5)

unde
,k kyx sunt cromozomii generației k, N reprezintă lungimea cromozomilor și
( ), ( )k knnyx sunt
alelele cromozomilor x,y.
Pentru a asigu ra diversitatea fenotipică , într -o populație sunt mutanți cromozomii cei
mai apropiați de cromozomul central .
Un alt parametru important folosit de operatorul de muta ție este rata de muta ție. În
algoritmul genetic standard acest parametru rămâne constant și, din cauza aceasta, este aproape
imposibil de a echilibra divergen ța asigurată de crossover și muta ție și convergen ța asigurată de
selecție. Controlul adaptiv al diversității popula ției oferă o modalitate de a găsi soluția optimă
globală și de a echili bra divergen ța și convergen ța în popula ția de cromozomi. O popula ție
diversificată ajuta la evitarea convergen ței premature și să ofere un set soluții mai bune .
În [19], diversitatea popula ției este definită ca suma diferen țelor dintre fiecare
cromozom si cromozomul central :
( ) ( ( ), )kk
iD k dist i xm
(6)
unde
kx este cromozomul din generația k și
km este cromozomul central calculate pentru generația k.
O valoare mică a diversită ții înseamnă că aproape to ți membri i populației sunt grupați
într-o zonă din spa țiu în jurul cromozomul centr al. O valoare ridicată înseamnă o distribu ție
mare a cromozomilor în spa țiul de căutare .
Folosind această măsură a diversității în [4] ,valoarea procentului de muta ție va fi :
min11mut mut(x) (x )( ( (x)) (x))P P D D D   
(7)
unde
mut(x)P este procentul de mutație în generația x,
(x)D este măsura diversității în generația x și
minD
este valoarea minimă a.

Crossover

Operatorul crossover realizează recombinarea indivizilor selectați prin operatorul de selecție,
imitând încrucișarea intercromozomială naturală. De regulă, din doi părinți rezultă maxim doi urmași.
Acest operator asigură exploatarea spațiului de căutare, fiind unul din operatorii de o i mportanță mare
în funcționarea algoritmului genetic.
În marea majoritate a cazurilor, sunt utilizate două variante ale acestui operator:
– crossover în un punct de tăietură
– crossover în mai multe puncte de tăietură.

a. Crossover într -un un punct de tăiet ură

Prin acest operator, se face schimbul de informații între cromozomii părinți, prin combinarea
segmentelor de cromozomi, determinate ca dimensiune de un număr întreg k, mai mic decât lungimea
cromozomilor părinți, numit punct de tăietură. Sunt parcurse următoarelor etape: selectarea aleatoare a
unei gene, k, și obținerea urmașilor
astfel :
• copiază primele k elemente din
, respectiv
în
, respectiv

• copiază în ultimele m-k+1 poziții din
, respectiv
, ultimele m-k+1
elementele din
, respectiv
, unde m este lungimea cromozomului.

Figure 14. Crossover în un punct de tăietură

Punctul de tăietură poate avea o poziț ie fixă sau variabilă în cadrul operatorului crossover.
Ca urmare a aplicării operatorului, de cele mai multe ori urmașii obținuți nu sunt soluții fezabile
ale problemei. În aceste cazuri, operatorul este urmat de o procedură de modificare a urmașilor, pe ntru
a se asigura fezabilitatea lor sau pur si simplu urmașii care nu reprezintă soluții sunt eliminați.
În [19], algoritmul implementat utilizează operatorul crossover într -un punct de tăietură,
generat aleator. După crossover, se aplică o procedură de el iminare a buclelor din cadrul rutei. Dacă
după această procedură cromozomul nu reprezintă o soluție, el este eliminat.

b. Crossover în mai multe puncte de tăietură

Această încrucișare este o extensie naturală a operatorului de recombinare în un punct. În ca zul
crossover -ului în mai multe puncte de tăietură, segmentele care se obțin sunt combinate după o regulă
stabilită anterior.
Încrucișarea în mai multe puncte de tăietură este justificată deoarece pentru crossover într -un
singur punct, anumite combinații de gene nu se pot realiza. Totodată, prin încrucișarea în mai multe
puncte se poate realiza sensibilitatea operatorului la creșterea lungimii cromozomului.
Și în acest caz rezultă soluții nefezabile, fiind necesară dezvoltarea de mecanisme care să trate ze
excepțiile.

Figure 15. Crossover în mai multe puncte de tăietură

Față de aceste două categorii principale de mutație există și altele, derivate, construite pentru
optimizarea funcționării algoritmului genetic.
Crossover -ul adaptiv ține seama de calitatea descendenților rezultați prin crossover cu diverse
puncte de tăietură. Distribuția punctelor de tăiere se modifică în funcție de rezultatele obținute,
înregistrând pozițiile punctelor utilizate. Dacă un punct a generat un de scendent cu valoarea fitness -ului
mică, acest punct nu va mai fi utilizat. Dacă fitness -ul este bun, punctul va fi utilizat în continuare.
Această procedură asigură un proces de selecție a punctelor de încrucișare.
Crossover -ul cu amestec urmărește obțin erea unei diversități mai mari a urmașilor. Este un
mecanism suplimentar, fiind aplicat împreună cu alt operator de crossover.
În cazul crossover -ul uniform, pentru fiecare genă a unui descendent se utilizează un parametru
global care va indica probabilit atea ca această genă să fie componentă a primului sau al doilea părinte.
Astfel, fiecare poziție se calculează separat, crossover -ul uniform fiind de fapt o generalizare a
crossover -ului în mai multe puncte de tăiere. Ca modalitate de implementare, este ge nerată aleator o
mască binară ce determină care gene sunt copiate din unul dintre părinți și care din celălalt. Structura
măștii (densitatea ei) dictează cât material genetic este preluat din fiecare părinte pentru a fi transmis
către urmași.

Figure 16. Crossover uniform

În cazul în care cromozomii sunt șiruri de numere reale sunt folosite uzual două clase de
operatori de crossover, recombinarea de tip discret și recombinarea aritmetică.
Recombinarea de tip discret este simila ră reprezentării prin șiruri binare, cu mențiunea că, în
acest caz, o genă este un număr real, nu 0 sau 1. Acest tip de încrucișare are dezavantajul că nu sunt
obținute valori noi pentru genele cromozomilor urmași, singurul operator care poate extinde zona de
căutare rămânând cel de mutație.
Recombinarea aritmetică este clasa operatorilor prin aplicarea cărora sunt obținuți cromozomi
cu alele noi, rezultate prin combinarea aritmetică (prin medie ponderată) a genelor cromozomilor
părinți. În literatura de sp ecialitate sunt prezentate o serie de variante ale operatorilor aparținând
acestei clase.
Alegerea tipului de operator de crossover este determinată de problema pentru rezolvarea
căreia este dezvoltat algoritmul genetic. Fiecare operator este mai potrivit pentru anumite clase de
probleme, pentru altele prezentând rezultate mai slabe.

Convergenta algoritmilor genetici, teoria schemelor, ipoteza blocurilor constructive

Algoritmii genetici reprezintă o clasă de metode probabilistice de căutare eficientă în spațiul
soluțiilor problemei date. Pe parcursul rulării, valoarea fitness -ului suferă îmbunătățiri de la o generație
la alta.
Fundamentele teoretice ale algoritmilor genetici au fost prezentate de J.H.Holland în [20], prin
dezvoltarea teoriei schemel or, utilizând o codare binară pentru cromozomi. Aceasta introduce
conceptele de schemă și de blocuri constructive.
Pentru codificarea binară, o schemă este formată dintr -un șir de simboluri 0,1 și *, unde * are o
semnificație de ”don`t care”, putândlua or icare din valorile 0 și 1 iar o schemă de lungime r este element
component al mulțimii
{0,1,*}r .
Dată fiind S o schemă având lungime r, un cromozom
{0,1,*}rx este o instanță a schemei S
dacă oricărie din pozițiile diferite d e * ale lui S îi corespunde o poziție din x cu aceeași valoare.
Poziția specifică a schemei S este orice poziție din S cu altă valoare în afară de *.
Mai general, o schemă S reprezintă mulțimea de cromozomi x pentru care toate pozițiile
specifice din S soincid cu pozițiile din x, caz în care x este o instranță a schemei S.
Ordinul unei scheme este dat de numărul de poziții specifice din aceasta . Lungimea utilă a unei
scheme este diferența dintre ultima și prima poziție specifică.
Performanța unei sch eme este dată de adecvarea medie a instanțelor ei in cadrul unei populații.
Utilizând noțiunile prezentate, teorema schemelor a lui Hollande este următoarea:

-o schemă având o performanță peste medie, valori scăzute ale ordinului și lungimii utile, tinde să apară
mai frecvent în componența populației de cromozomi din generația următoare iar o schemă cu
performanță sub medie tinde să apară mai puțin frecvent în generațiile următoare.
Această teoremă furnizeaza o margine inferioară a schimbarii ratei de sele cție de la generația t la
generația t+1, în conformitate cu:

( , ) ( )[ ( , 1)] ( , )* *[1 * * ( )]1 ()cmf H t HE m H t m H t p p Hl ft    
[20]
Unde
cp
este probabilitatea de crossover
mp
este probabilitatea de mutație
()ft
este fitnessul mediu al populației la momentul t
( , )f H t
este fitnessul mediu al cromozomilor instanțe ale schemei H la momentul de timp t
( , )m H t
este numărul de șiruri din schema H în generația t
()H
este ordinal schem ei H
()H
este lungimea utilă a schemei H

În timpul funcționării, algoritmul genetic este caracterizat de un paralelism intrinsec datorită
faptului că menține simultan un număr mare de scheme. În conformitate cu teorema schemelor,
adecvarea va crește în generațiile succesive.
Blocurile constructive sunt o categorie de scheme cu o calitate peste medie și cu ordin și lungimi
mici. Operatorii genetici asigură combinarea blocurilor constructive, generându -se pe parcursul
generațiilor alte le din ce în ce mai bine adaptate, cu convergență spre soluția optimă.

3.1.2 Programarea genetică

Programarea genetică poate fi considerată ca o particularizare a algoritmilor genetici. În cadrul
acestei tehnici, rutinele de calcul sunt codate sub formă de gene. Setul de cromozomi format cu aceste
gene evoluează generând programe capabile să rezolve problema dată. Reprezentarea este de obicei
arborescentă, fiind utilizate limbaje pentru care această reprezentare este nativă. Există și alte feluri de
reprez entări care permit utilizarea unor limbaje de programare mai cunoscute (în cazul programării
genetice liniare).

Funcțional, în cadrul GP sunt prezente următoarele componente [21]:
– Un set de date terminale si de funcții primitive
– O funcție fitness
– Un crit eriu de terminare
– Un set de parametrii de funcționare a algoritmului.
Setul de date terminale este format din constante, date de intrare ale programelor și funcții fără
argument..
Setul de funcții primitive conține operatori matematici, instrucțiuni, oper atori booleeni, etc.
Întrucât setul de funcții și de date terminale determină mărimea spațiului de căutare este indicat
ca acestea să nu fie foarte dezvoltat și să se afle în concordanță cu problema de rezolvat. De asemenea,
este important ca funcțiile al ese să poată utiliza întregul set de constante și date de intrare disponibile
pentru a sigura o rulare fără erori a algoritmului.
Funcția fitness este cea care determină gradul în care un program își îndeplinește sarcinile. În
funcție de problema de rezo lvat, poate fi definită ca nivel al erorilor dintre ieșirea dorită și cea prezentă,
timp de rulare, acuratețe de clasificare, îndeplinirea criteriilor de programare impuse de utilizator, etc.
Scopul ei este de a măsura evoluția indivizilor componenți ai po pulației în mod continuu. Poate conține
mai multe criterii de evaluare, active simultan, caz în care este o funcție fitness multiobiectiv.
Algoritmul de selecție este o parte importantă în programarea genetică. După ce a fost măsurată
adecvarea fiecărui in divid, trebuie să se decidă asupra căruia se vor aplica operatorii genetici și care vor
fi înlocuiți sau păstrați. Există mai multe tipuri de operatori de selecție (proporțională cu fitnessul, pe
bază de turnir, prin trunchiere, etc.), metoda care va fi a plicată va avea o implicare directă în rularea
algoritmului. De asemenea, selecția influențează viteza de evoluție a populației și este responsabilă de
evitarea convergenței premature sau a uniformizării populației.
Criteriul de terminare poate fi timp de rulare (atât ca număr de iterații cât și ca unități de timp)
sau atingerea unei valori a funcției fitness.
Setul de parametrii de funcționare a algoritmului este constituit din dimensiunea populațiilor,
probabilități de aplicare a operatorilor genetici, număr de iterații și în principal orice parametru care
influențează rularea algoritmului.
Din punct de vedere al algoritmului, acesta este identic cu un algoritm genetic, fiind
particularizați operatorii genetici și reprezentarea cromozomilor în funcție d e limbajele de programare
utilizate. Astfel, în prima etapă este generată populația inițială de programe, din setul de funcții
primitive și terminale. În continuare sunt repetați următorii pași:
– Se execută fiecare program în parte și i se calculează valoar ea funcției fitness
– În conformitate cu această valoare sunt selectate programele asupra cărora se vor aplica
operatorii genetici
– Se generează noi indivizi în urma aplicării acestor operatori.

până când este identificată o soluție acceptabilă sau este îndep linită condiția de oprire a algoritmului.
Este returnat individul cel mai adaptat din populație.
Din punct de vedere al programării genetice multiobiectiv, întrucât tehnica este derivată din
algoritmi genetici, metodele sunt asemănătoare. Abordarea proble mei multiobiectiv în cadrul GP se
poate face atât prin combinarea ponderată a obiectivelor într -o singură funcție fitness, noua funcție
fiind de forma:

ii
iF a f

unde F este funcția fitness multiobiectiv,
if sunt funcți ile obiectiv particulare iar
ia ponderile,
cât și prin păstrarea separată a obiectivelor, caz care poate fi abordat cu ajutorul noțiunii de optimizare
Pareto.
Caracteristica principală care distinge programarea genetică de ceilalți al goritmi evolutivi este
capacitatea acesteia de a -și adapta complexitatea soluțiilor. Întrucât rezultatul programării genetice sunt
programe, această capacitate este importantă întrucât s -a demonstrat [22] că există o barieră inferioară
a complexității sub care algoritmii nu își mai pot realiza scopul.

3.1.3 Programarea evolutivă

În anii 1960, Lawrence J.Fogel (autorul bazelor programării evolutive) considera că
inteligența este caracterizată de adaptarea la condițiile de mediu, fiind o combinație de capacitat e de a
face o predicție a mediului ambiant și de posibilitate de a transforma această predicție într -un răspuns
adecvat în raport cu problema de rezolvat.
Mediul a fost definit ca o secvență de simboluri alese dintr -un alfabet finit. Din acest punct de
vedere, programarea evolutiva (EP) a fost definită ca și capacitate a unui program care are ca date de
intrare secvența de simboluri de a produce un simbol care maximizează performanțele programului atât
din punct de vedere al următorului simbol care va apă rea în mediu cât și al unei funcții obiectiv. Pentru
reprezentare au fost utilizate automate cu stări finite determinist de forma
0 ( , , , )X S S  unde

reprezintă mulțimea finită a simbolurilor de intrare, S este mulțimea st ărilor prin care poate trece
automatul,
0S este starea inițială iar
 este funcția de tranziție a automatului, de forma
,( , ) s s x
adică automatul va trece în starea
,s dacă fiin d în starea
s va citi simbolul x. Dacă acestui
automat i se adaugă o bandă de ieșite care înregistrează câte un simbol de ieșire de obține o mașină
Turing.

Figure 17 Automat cu stări finite

Din punct de ve dere al programării evolutive, simbolul de ieșire este predicția mașinii pentru
starea următoare a mediului. Valoarea acestei predicții este măsurată cu o funcție de câștig ce cuantifică
diferența dintre simbolul de ieșire și următorul simbol de intrare. P rogramarea evolutivă urmărește
obținerea unor automate care să îți modifice comportamentul pentru creșterea capacității de a face
previziuni corecte referitoare la simbolurile de intrare care descriu mediul.
Ca algoritm:
– Se generează aleatoriu populația de mașini Turing
– Membrilor acestei populații le este prezentată mulțimea de simboluri care reprezintă
mediul. Pentru fiecare simbol de intrare ( pentru fiecare mașină din populație),
simbolul de ieșire va fi comparat cu următorul simbol de intrare
– Se calcule ază funcția de câștig pentru fiecare predicție
– Se evaluează indivizii din populație
– Se aplică operatorul de mutație pentru un număr x de mașini din populația P, generând
populație
1P
– Se evaluează indivizii din
1P
– Din
1 PP se aleg în funcție de câștig μ indivizi care devin noua generație
– Se repetă etapele până când este detectată o mașină Turing ce realizează predicția corectă
iar simbolul respectiv este marcat ca fiind verificat și se repetă alg oritmul pentru toate
simbolurile de intrare.
Spre deosebire de ceilalți algoritmi evolutivi, în cazul programării evolutive principalul
operator este mutația. Din punct de vedere al unei mașini Turing, mutația se poate manifesta prin:
– Modificarea simbolul ui de ieșire
– Adăugarea sau modificarea unei stări a automatului
– Ștergerea unei stări
– Modificarea stării inițiale.
După ce este aplicată mutația, din totalul automatelor existente (atât cele inițiale cât și cele
modificate) sunt alese doar cele mai adecvat e mediului, până la formarea unei populații complete.
Deoarece valoarea simbolurilor de intrare se modifică după fiecare prezentare a unui simbol,
valoarea adecvării trebuie să se modifice pentru a reflecta evoluția față de starea anterioară. Această
modificare imprimă evoluția algoritmului și evitarea uniformizării populației.

3.1.4 Strategii evolutive
Strategiile evolutive sunt o ramură a algoritmilor evolutivi, fiind dezvoltate în anii 1970 de Ingo
Rechenberg și Hans -Paul Schwefel ca urmare a necesității de a aborda probleme de căutare cu
parametrii numere reale, variabili. De aceea, reprezentarea indivizilor din populație este de forma unor
vectori cu componente reale. Operatorul genetic de bază este mutația. În principal sunt destinate
pentru abordarea p roblemelor de optimizare caracterizate de funcții continue.
Algoritmul de optimizare al strategiei evolutive 1+1 ( – doi membrii ai populației sunt comparați și
este selectat cel cu valoarea funcției fitness mai mare – [23] consideră o populație formată din un
cromozom cu componente numere reale. Mutația modifică valoarea genelor din acest cromozom iar din
cei doi este ales cel mai adecvat.
Generalizarea strategiei evolutive 1+1 implică creșterea numărului de cromozomi părinți,
descendenți sau părinți și des cendenți, toate purtând denumirea generică de strategii evolutive (μ,λ)
unde, pornind de la μ componente ale populației curente, sunt generate λ componente noi din care
sunt selectate după adecvare cele μ componente ale populației următoare și (μ+λ) unde sunt generate
λ componente noi iar din cele μ+λ elemente sunt selectate după adecvare cele μ componente ale
populației următoare.

Algoritmul unei strategii evolutive este următorul:
– se generează populația inițială
– până se atinge condiția de oprire se ex ecută următoarele operații:
o se calculează funcția fitness pentru elementele din populația curentă
o se generează populația de urmași prin recombinare
o se aplică operatorul de mutație asupra populației de urmași și se evaluează rezultatele
o se aleg componentele pentru noua generație.
Operatorii specifici strategiilor evolutive sunt:
a. Mutația – produce modificări de amplitudine mică a componentelor populației.
Chiar dacă funcționarea algoritmului strategiei evolutive este asemănătoare cu
algoritmii genetici, din p unct de vedere al mutației diferența este că în cadrul ES
se favorizează mutații de amplitudine mică pe când in cazul GA nu există astfel de
condiții. Operatorul acționează prin introducerea unui vector de mutație în
vectorul care reprezintă individul car e va fi afectat. Valoarea medie a vectorului
de mutație este nulă pentru a nu introduce tendințe de deplasare spre regiuni
particulare ale spațiului de căutare. Din punct de vedere al repartiției, cele mai
frecvente tipuri utilizate sunt repartiția normală în care elementele vectorului de
mutație sunt independente, generate uniform aleatoriu într -un interval de valori

date și repartiția normală în care elementele vectorului de mutație sunt
independente fiind valori aleatoare cu media nulă.
b. Recombinarea este operatorul care produce schimbul și perpetuarea informației
între indivizii populației. Permite participarea unui număr variabil de părinți,
putând fi o recombinare discretă în care fiecare componentă a urmașului se
selectează din componentele corespunzăt oare ale părinților sau o recombinare
intermediară in care componentele urmașului sunt combinații ale componentelor
părinților. Ca modalități de recombinate, cele mai uzuale în cazul strategiilor
evolutive sunt recombinarea liniară în care componentele urm așul sunt combinații
liniară ale componentelor părinților, recombinarea discretă în care componentele
urmașului sunt componentele părinților alese cu o anumită probabilitate
dependentă sau nu de fitnessul părinților, recombinarea geometrică, recombinarea
euristică și recombinarea de tip simplex.
c. Selecția, care se aplică în vederea stabilirii componentelor populației următoare.
În funcție de participanții la această selecție putând fi:
a. selecție (μ,λ), cu condiția ca μ<λ, unde noua populație se formează prin
selecția a μ elemente din cele λ generate de operatorii de mutație și
recombinare;
b. selecție (μ+λ), unde noua populație se formează prin selecția a μ elemente
din cele generate de operatorii de mutație și recombinare împreună cu cele
componente ale popula ției inițiale.
Alegerea între variantele (μ,λ) și (μ+λ) este determinată de problema ce trebuie
Rezolvată, neexistând rezultate care să certifice superioritatea uneia din cele două
metode.
Metoda de selecția poate fi poate oricare din metodele folosite î n cazul algoritmilor
genetici, cele mai folosite fiind prin trunchiere în care se aleg cele mai bine adaptate n elemente
din populația urmașilor sau a urmașilor împreună cu a părinților sau selecția prin turneu.