Contribuții în optimizarea multicriterială a sistemelor informatice distribuite COMISIA DE DOCTORAT București – 2017 Abstract Odată cu evoluția… [311599]

Academia Tehnică Militară

Facultatea de Inginerie Electronică și Telecomunicații

Nr. Decizie Senat ___din_____

TEZĂ DE DOCTORAT

Contribuții în optimizarea multicriterială

a sistemelor informatice distribuite

COMISIA DE DOCTORAT

București

– 2017

[anonimizat], se adresează spre soluționare mai mult tehnicilor probabilistice decât celor deterministe.

[anonimizat]-o [anonimizat], neclasificate, [anonimizat] a [anonimizat]-un orizont de timp bine definit și acceptabil de către beneficiar. [anonimizat]. 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.

[anonimizat], [anonimizat]. [anonimizat].

[anonimizat], prin asigurarea funcției de adaptare a [anonimizat].

Cuprins

Introducere

Un sistem informatic distribuit este un sistem de prelucrare a informației format dintr-o [anonimizat], care fac schimb de mesaje și își coordonează activitatea între ele utilizând o infrastructură de comunicații pentru a îndeplini un număr de obiective specifice. [anonimizat], reducerea costurilor precum și toleranța la erori.

Serviciile din ce în ce mai diversificate de comunicații și creșterea capacității de transport disponibilă au transformat sistemele distribuite într-o regulă și nu o excepție. [anonimizat], 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 [anonimizat], [anonimizat] 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 pentru 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 sistemelor 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ă mare, 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 calitate 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 existenț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 calculul 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.

Formularea problemei

Direcțiile de evoluție ale domeniului IT sunt orientate spre dezvoltarea 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 acoperire geografică aproape totală și prezintă o creștere accentuată (Fig.1 ).

Figura 1Evoluția conexiunilor M2M [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).

Figura 2 Evoluția numărului de echipamente conectate în rețea prin standard IPv6

Noile noțiuni de calcul ubicuu, de realitate augmentată, au cerințe specifice referitoare la mobilitate , miniaturizare și capacitate de calcul. Toate acestea 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ă dezvoltarea 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 multiobiectiv 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 realizate 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 clasice, relativ statice sau cu dinamicitate redusă, bazate pe intervențiile administratorilor neputând oferi soluții viabile în timp rezonabil.

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 sistemelor 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 management ș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.

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 specialitate a propus:

Î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 determiniș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 vedere istoric a acestora

Î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 acestora

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.

Dezvoltarea unei structuri de date și a unui set de funcții pentru realizarea testării soluțiilor propuse.

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 specifice 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 teoretice 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-machine 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 cadrul 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 cadrul 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 optimizare/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 infrastructurii 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.

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. Toleranț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 hardware 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 instabilitatea (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, menț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 faza 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.

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 de 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 dezvoltare 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.

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ă dezvoltare 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 mesaje, 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, interferenț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 standardizare 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ă arhitectură, î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.):

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 identificat, 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 communication, 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 al 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 diferenț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 posibilitatea de comunicare a oricărui lucru, pe lângă posibilitatea de a comunica în orice moment de timp și în orice loc.

Figure 3 Dimensiunile IoT (ITU-T, 06.2012)

Un obiect fizic IoT poate fi reprezentat prin unul sau mai multe obiecte virtuale. Un obiect virtual poate sau nu sa aibă corespondență î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.).

Figure 4 Obiecte din IoT (ITU-T, 06.2012)

Din punct de vedere al schimbului de informație între elemente, rețeaua în care sunt conectate oferă serviciile 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 modelul 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.

Figure 5 Modelul de referință pentru IoT (ITU-T, 06.2012)

Î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 transport 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 economisire 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 integritate 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 elementelor, controlul accesului. Pe lângă aceste elemente generale sunt prezente și elemente particulare, determinate de funcțiile sistemului.

Calculul ubicuu

Calculul ubicuu (pervaziv, care este prezent peste tot) definește conceptul prin care orice dispozitiv, 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 lucrarea „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 circumstanț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ă asigure 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

integrarea

mediul de programare

robustețea

securitatea.

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 timp 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 predictibile.

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.

Adaptarea

Într-un mediu ubicuu, există 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

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.

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ă între 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.

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ăstrarea caracteristicilor funcționale.

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 cazul 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 limitate, 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ă interoperabilitatea 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.

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 computing 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 utilizatorul

Proliferarea platformelor

Tranzacțiile active

Figure 6 Dimensiunile calculului mobil (B'Far, 2005)

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 locaț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 poziția relativă față de un anumit punct, fiind utilizate tehnici de triangulație, de analiză a proximității, etc.

Calitatea serviciilor

Mobilitatea presupune pierderea conectivității permanente la rețea, cu implicații importante

asupra calității serviciilor. 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 provider 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 moment dat.

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 hardware 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.

Resursele energetice limitate

Constrângerile referitoare 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 de 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.

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 utilizatorul 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.

Proliferarea 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 actual 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.

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 sincrone, cât și asincrone.

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 informaț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, execuț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, localizare 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 secundare 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, contextele 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 sistemul 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.).

Figure 7 Arhitectura unui sistem raportat la context

La nivel de senzori (atât biologici cât și non-biologici), datele sunt achiziționate din mediu, acestea fiind transmise 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 pentru 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.

Rețele de senzori wireless

Conceptul se referă la o sumă de elemente de calcul utilizate pentru monitorizarea 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 constructiv, 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 mici 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 vedere al structurii unei rețele wireless, ea este concepută după modelul O.S.I. [7]:

Figure 8 Nivelele WSN

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 precum ș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 cu 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 aplicaț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 implementate î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 management 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 prelungirea 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 implementare, 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 transmiterii 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ționă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 instabilitatea 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 referitoare 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 aplicabilitatea 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 informaț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 .

Smart-dust

Conceptul „smart-dust” presupune 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, elemente 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 hardware 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 cele 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 senzor 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 device-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. Mesajul 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 este 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 specializate, î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.

Ambient intelligence

Conceptul se refera la mediul electronic ce interacționează activ omul fiind 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 9 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.

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 abstractizare î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 manipulat, 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, impactul este major, sunt necesare resurse hardware și software suplimentare, crește complexitatea în cazul depanării, sunt introduse noi instrumente de management.

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 10 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 fizice 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 completă 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 de 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.

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 11 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 obicei sunt necesare mai multe resurse (atât cele pentru aplicație cât și cele pentru serviciul de virtualizare).

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 controlate 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, fiecare 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) iar 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.

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 acestora 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 12 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 resursele 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 responsabil 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 administrată 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 13 Arhitectura tradițională a rețelei

Figure 14 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 dinamică 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 managementului – 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 normală 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 presupune 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 abstractizarea 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 15 Arhitectura SDN

Cloud computing

Cloud computing reprezintă un ansamblu distribuit de servicii de calcul, aplicații, stocare 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 16 Nivelele oferite de cloud-computing

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 serviciilor 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 oferă 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 software-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.

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, resursele 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 administrarea 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 implementat pe un serviciu Infrastructure as a Service.

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 utilizatorul 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ția 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 aplicaț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 cloud 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 serviciilor.

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 acestor 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ă de 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 heterogene, 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, toleranț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ă partajarea 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 energie – 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 din cel al consumului de energie, întrucât minimizarea acesteia nu poate fi efectuată prin simpla oprire a unor elemente fizice din cloud.

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ă existenț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 soluț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 considerare 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 considerare 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 beneficiari. 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 dinamicitate 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 algoritmi 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, care 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. Scopul 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 multiobiectiv 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 trei 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 slab 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 nedominat 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 dominare 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, care 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 mari 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 problemelor 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, obiectivele 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 presupune 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 rezultatul 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 de 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, analiza 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ângeri. 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 obiectiv, 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 necesită 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 calculul 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 dimensiuni 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 problemelor

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

evaluarea 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:

dimensiunea populației – o populație de mici dimensiuni are ca efect rularea rapidă a algoritmului dar influențează negativ 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ărul de indivizi poate fi atât fix cât ți variabil.

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 necesară 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 generată de alegerea de indivizi puțin adecvați are ca efect timpul lung de convergență a algoritmului sau chiar imposibilitatea atingerii convergenței.

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.

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.

Metode evolutive de optimizare multicriterială a sistemelor informatice. Concepte

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, reproducerea.

Figura 17. 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 codifică 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ții (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 dar 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 gene. 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 cromozomilor 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 18. Explorare-exploatare în căutarea genetică

Problema echilibrului între utilizarea soluțiilor 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 general, 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 independent, 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 cromozomi 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 pe 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ționarea algoritmului genetic respectă schema logică din figura următoare:

Figure 19. Schema logică a unui algoritm genetic

Etapele algoritmului genetic:

Din punct de vedere funcțional, algoritmul genetic parcurge următoarele etape:

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 cromozom 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 problemei î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 20. 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 matricei 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 cromozomii 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ă descrierea problemei.

(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 formula 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 prematură 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 fitness-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ă. Pentru 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 distribuție într-un interval de valori optim pentru problema dată.

Figura 21. Modificarea distribuției funcțiilor fitness

Ferestruirea valorilor de adecvare este similară scalării, dar valorile cu care se modifică adecvările sunt alese 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 rezolvată 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:

,

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:

[15] (2)

Spațiul tuturor soluțiilor fezabile existente este numit spațiul de căutare sau spațiul stărilor. 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 bune, 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 forma 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 utilizată 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ăutare 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 dimensiunea 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 valoare 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 important î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 populaț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 asigură 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 de 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 algoritmul 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ării 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 totală 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 mai utilizată fiind selecția proporțională, care

depinde de valoarea fitness-ului cromozomului.

Metoda „Roulette Wheel” (metoda ruletei)

Această metodă folosește algoritmul Monte Carlo de selecție. Fiecare individ din populația curentă este reprezentat printr-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 cei 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 pierderea 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ță.

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 valoarea funcției de adecvare, sunt evitate inconvenientele selecției proporționale.

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 performant. 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.

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 aceasta 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 (genotipului). 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 inversarea 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, dacă î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ții î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 construirea 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 cromozom.

Î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 aleatoare 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 fiecă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 necesită 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 operator 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 fixată.

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 cele 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 pentru a măsura distribuția masei în spații multidimensionale. De asemenea 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 populaț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 fi î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 central va fi de forma:

(3)

unde

(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 majoritatea cromozomilor are o valoare mică. Distanța este de forma:

(5)

unde sunt cromozomii generației k, N reprezintă lungimea cromozomilor și sunt alelele cromozomilor x,y.

Pentru a asigura 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 echilibra 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:

(6)

unde este cromozomul din generația k și este cromozomul central calculate pentru generația k.

O valoare mică a diversității înseamnă că aproape toți membrii populației sunt grupați într-o zonă din spațiu în jurul cromozomul central. 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 :

(7)

unde este procentul de mutație în generația x, este măsura diversității în generația x și 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 importanță 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ă.

Crossover într-un un punct de tăietură

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 22. 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, pentru 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 eliminare a buclelor din cadrul rutei. Dacă după această procedură cromozomul nu reprezintă o soluție, el este eliminat.

Crossover în mai multe puncte de tăietură

Această încrucișare este o extensie naturală a operatorului de recombinare în un punct. În cazul

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ă trateze excepțiile.

Figure 23. 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 descendent 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ținerea 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 probabilitatea 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 generată 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 24. 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 similară 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 specialitate 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 schemelor, 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 oricare din valorile 0 și 1 iar o schemă de lungime r este element component al mulțimii .

Dată fiind S o schemă având lungime r, un cromozom este o instanță a schemei S dacă oricărie din pozițiile diferite de * 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 scheme 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 selecție de la generația t la generația t+1, în conformitate cu:

[20]

Unde

este probabilitatea de crossover

este probabilitatea de mutație

este fitnessul mediu al populației la momentul t

este fitnessul mediu al cromozomilor instanțe ale schemei H la momentul de timp t

este numărul de șiruri din schema H în generația t

este ordinal schemei 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 altele din ce în ce mai bine adaptate, cu convergență spre soluția optimă.

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 reprezentă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 criteriu 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, operatori 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 alese 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 rezolvat, 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 populaț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 individ, 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 aplicată 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 de 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ă valoarea 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 îndeplinită 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 problemei 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:

unde F este funcția fitness multiobiectiv, sunt funcțiile obiectiv particulare iar 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 algoritmi 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.

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 capacitate 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 unde reprezintă mulțimea finită a simbolurilor de intrare, S este mulțimea stărilor prin care poate trece automatul, este starea inițială iar este funcția de tranziție a automatului, de forma adică automatul va trece în starea dacă fiind în starea 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 25 Automat cu stări finite

Din punct de vedere 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. Programarea 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 calculează 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

Se evaluează indivizii din

Din 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ă algoritmul 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 simbolului 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 adecvate 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.

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 problemelor 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 descendenț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 execută următoarele operații:

se calculează funcția fitness pentru elementele din populația curentă

se generează populația de urmași prin recombinare

se aplică operatorul de mutație asupra populației de urmași și se evaluează rezultatele

se aleg componentele pentru noua generație.

Operatorii specifici strategiilor evolutive sunt:

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 punct 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 care 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ă.

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ătoare 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 urmaș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.

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:

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;

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.

Utilizarea algoritmilor genetici în optimizarea sistemelor informatice distribuite

Sistemele informatice distribuite, prin natura structurii, sunt caracterizate de un set de constrângeri, de multe ori având un caracter concurențial. Limitările pot fi atât din punct de vedere al resurselor de calcul, cât și al resurselor de comunicații, al parametrilor serviciilor furnizate/utilizate sau al alimentării cu energie electrică. Din acest punct de vedere, optimizarea acestor sisteme este o problemă de optimizare multicriterială, pretabil a fi abordată prin tehnici evolutive.

Acest capitol se bazează pe abordările și rezultatele publicate în lucrările [24], [25], [19], [26], [27], [28], [12], [29] de Maniu R. și Dumitru L. Acestea conțin atât abordări evolutive ale diverselor probleme de optimizare a funcționării sistemelor informatice cât și detalierea problemelor de adaptabilitate a operatorilor genetici.

În articolele [24], [25], [27], [12] au fost prezentate soluții evolutive pentru diverse probleme (dificil de abordat prin mijloace deterministe) cu care se confruntă sistemele informatice luând în considerare direcțiile de dezvoltare ale domeniului IT. Au fost propuse soluții care implică o abordare sistemică a solicitărilor din partea utilizatorilor și a resurselor hardware și software disponibile.

Studiile au fost direcționate cu precădere spre domeniul asigurării necesarului de comunicații, considerând ca un sistem distribuit are o structură heterogenă, atât din punct de vedere al elementelor de prelucrare a datelor cât și al infrastructurii de comunicații. Ținând cont de necesarul de mobilitate ceea ce presupune o structură dinamica a sistemului informatic, au fost propuse soluții genetice pentru a asigura configurarea/reconfigurarea dinamică a rețelei pentru asigurarea serviciilor solicitate.

Metode de optimizare a componentei de comunicații a sistemelor distribuite. Context. Aplicații

Context:

Noile tehnologii împreună cu creșterea accelerată a resurselor necesare pentru ca sistemele

informatice moderne să își poată îndeplini funcțiile sunt afectate de o serie de limitări existente ca o consecință a tehnologiilor anterioare. Furnizarea de servicii de comunicații cu respectarea cerintelor de calitate a serviciilor în condițiile sistemelor informatice distribuite actuale este dificilă, în general având ca bază stiva TCP/IP.

Limitările sunt reprezentate de :

Complexitatea managementului ca urmare a dezvoltării în timp a protocoalelor de rețea și a varietății acestora (există tehnologii distincte, multiple, heterogene aplicabile echipamentelor de comunicații, cu diverse instrumente de administrare, particularizate, în funcție de producători, echipamente, vessiuni software, etc.)

Dinamica scăzută a managementului configurărilor ca urmare a necesității ca administratorul să intervină pentru modificarea setărilor pe echipamente, cu riscurile potențiale prezente în aceste cazuri, fiind de preferat ca aceste intervenții să fie evitate.

Calcularea rutelor are un grad redus de libertate, fiind bazate pe un număr limitat de metrici, adăugarea altora fiind atribut al altor metode de management al traficului iar flexibilitatea rutării este practic inexistentă

Scalabilitatea implică creșterea dificultății administrării proporțional cu dimensiunea retelei, în rețelele de mari dimensiuni metodele clasice de administrare fiind ineficiente. Mai mult, dinamicitatea, atât din punct de vedere al traficului cât și a echipamentelor împiedică actualizarea în timp real a rutelor

Convergența politicilor aplicate în rețelele heterogene,fiind dificil de implementat un set de reguli generale (pentru securitate, calitate a serviciilor, acces, etc.) în condițiile existenței unui număr mare de echipamente și protocoale și de adoptare a unora noi

Dezvoltarea virtualizării care imprimă necesitatea dimensionării dinamice a capacităților de stocare, comunicații, procesare.

Abordarea prin instrumente de sine stătătoare a managementul comunicațiilor (rutarea, securitatea, controlul accesului și elementele de calitate a serviciilor nefiind elemente integrate) .

Algoritmii de rutare clasici prezintă la rândul lor limitări, nefiind adecvați dimanicității. În sisteme de comunicații standard, cu elemente bine definite și cu dinamică redusă, protocoalele de rutare, indiferent dacă sunt bazate pe vectori distanță sau pe calea cea mai scurtă, utilizează algoritmii lui Dijkstra, Bellman-Ford sau Ford-Fulkerson [30] . Aceștia au timp de rulare, în ordinul pătratului numărului de vârfuri respectiv a numărului de vârfuri inmulțit cu numărul de muchii sau numărului de muchii înmulțit cu debitul maxim prin graf (dacă rețeaua este reprezentată sub formă de graf), timp prea mare pentru calcularea rutei în condiții de dinamicitate structurală.

Nici în rețelele de tip MANET (Mobile AdHoc Networks) protocoalele de rutare nu sunt bazate pe algoritmi care oferă performanțe bune în condiții de dinamicitate și dimensiuni mari ale sistemului. Indiferent dacă sunt algoritmi proactivi (Optimized Link State Routing Protocol [31], BABEL [32], Destination Sequence Distance Vector [33], Distance Routing Effect Algorithm for Mobility [34]), reactivi(Associativity-Based Routing [35], Ad hoc On-demand Distance Vector [36]) sau hibrizi (Zone Routing Protocol), reacționează încet la modificări ale topologiei, au un consum mare de resurse pentru întreținerea rețelei, au convergență lentă și sunt influențați de modificări ale traficului.

Ca urmare a acestor limitări, este necesară apariția unor metode noi de rutare (mai dinamice,

dependente de mai multe metrici, eventual stabilite de administratori), de o modificare a metodelor de configurare a echipamentelor (dinamic, automat) și dezvoltarea de tehnologii care să susțină dinamicitatea sistemelor.

Lucrări conexe referitoare la metodele de optimizare a componentei de comunicații a sistemelor distribuite

În continuare sunt prezentate metode multicriteriale de generare a rutelor în sisteme informatice distribuite, metode bazate pe algoritmi evolutivi.

SAEN

Lucrarea [12] propune un model evolutiv de rețea de comunicații, SAEN (Self Adaptive Evolutionary Network) bazat de balansarea și analiza istoricului traficului în calcularea genetică a rutei optime.

Majoritatea rețelelor de comunicații clasice utililizează algoritmi de rutare bazați pe distanță, dinamica și comportamentul în timp al rețelei nefiind parametrii luați în considerare în acești algoritmi. Prioritizarea traficului, limitarea acestuia, balansarea sau setarea unor rute specifice sunt realizate în prezent de administratori. Deoarece noile modele de rețele sunt caracterizare de o mare heterogenitate și dinamism, caracteristici susținute de noile tehnologii (Internet of Things, calculul ubicuu, Smart Dust, etc.) intervenția operatorului uman va deveni practic imposibilă, fiind necesară apariția unor rețele intreligente, cu capacitate de autoorganizare.

SAEN propune o modalitate de rutare multilink, bazată pe analiza în timp real a traficului (în funcție de tip și de volum) precum și pe istoricul rețelei (din punct de vedere statistic ca model de trafic), soluția de rutare fiind generată utilizând tehnici evolutive.

Deoarece SAEN se referă la rețele dinamice, funcție fitness trebuie să conțină elemente care să se refere la starea curentă a cromozomilor (rutele din populație), la tendințele de evoluție a traficului cât și la istoric, fiind practic o sumă de componente:

Unde:

este funcția care verifică dacă cromozomul îndeplinește un minim de cerințe, specificate de clasificatorul , fiind o funcție discriminant

reprezintă un set de proprietăți care definesc traficul, impunând un set de cerințe pentru acesta împreună cu limitele tolerate, fiind de forma:

este componenta funcției fitness care include parametrii referitori la istoricul rețelei și la starea acesteia în timp real

este funcția care descrie tendința prezentp de evoluție a rețelei din punct de vedere al parametrilor acesteia

este parametrul responsabil cu descrierea comportamentului din punct de vedere istoric al link-urilor componente ale rutei descrise de cromozomul C

Parametrul i specifică adâncimea în trecut pentru care este calculată valoarea funcției

și sunt ponderi care determină influența tendinței prezente de evoluție a rețelei și influența istoricului. Întrucât valoarea și parametrii traficului, starea link-urilor și întârzierile sunt elemente importante care descriu funcționarea sistemului de comunicații, valoarea lui va fi mai mare decât valoarea lui .

Din punct de vedere al codării, cromozomii sunt reprezentați ca șir, semnificând ruta de la sursă la destinație. Întrucât lungimea șirului este egală cu numărul total de noduri din rețea iar ruta poate include un număr mai mic de noduri, spațiile rămase libere se completează cu valoarea 0.

Crossover-ul propus este într-un punct de tăiere, la mijlocul rutei, probabilitatea acestuia fiind adaptivă, descrisă de relația:

Unde:

A și B sunt valorile minime și maxime impuse pentru probabilitatea de crossover, ele fiind necesare pentru asigura convergența înspre valoarea optimă și evitarea blocării algoritmului într-un minim local

reprezintă valoarea fitness-ului pentru cromozomul curent

reprezintă valoarea maximă a fitness-ului în generație

reprezintă valoarea mainimă a fitness-ului în generație.

Din punct de vedere al operatorului de mutație, în lucrarea [12] este propusă o mutație adaptivă, mecesară pentru a asigura parcurgerea completă a spațiului soluțiilor dar a nu altera cromozomii cei mai bien adaptați. Ca urmare, probabilitatea de mutație va fi formată dintr-o componentă care este dependentă de adecvarea cromozomului și de o componentă care ține cont de diversitate, fiind de forma:

Componenta este dependentă de valoarea fitness-ului, având forma:

Unde C este valoarea maximă a mutației pentru parametrul dependent de fitness.

Componenta este determinată de diversitatea cromozomilor din populație, fiind descrisă de relația:

Unde:

I este momentul de inerție propus de Morrison și De Jong în lucrarea [18], fiind de forma:

P este numărul de cromozomi din generație

N este lungimea cromozomului

sunt coordonatele cromozomului în spațiul soluțiilor

K este valoarea maximă a mutației pentru parametrul dependent de diversitate.

Algoritmul trebuie să pornească în momentul apariției unii stimul (modificare a arhitecturii

rețelei, solicitări din partea utilizatorilor, etc.) să ruleze un timp limitat. Deoarece criteriul de oprire este atingerea unei valori a fitness-ului sau expirarea timpului de rulare, este posibil să existe cazuri în care aceste criterii nu pot fi îndeplinite. În aceste condiții, algoritmul va fi repornit fiind utilizată o altă populație inițială.

Prin abordarea prezentată anterior, SAEN oferă o modalitate automată de realizare a managementului unor rețele complexe, heterogene, dinamice cu implicare minimă a factorului uman. Propune o trecere de la metode deterministe de căutare a soluțiilor la metode bazate pe tehnici probabilistice, pe inteligență artificială.

Includerea istoricului în metoda de căutare a soluțiilor va conduce la evitarea rezultatelor care conțin rute ce este posibil să nu fie adecvate în diverse intervale de timp.

Tehnici genetice aplicate în managementul rețelelor moderne

Conceptul ”mobility for everyone” și implicit existența unui număr mare de elemente cu

capacitate de calcul conectate la sisteme de comunicații precum și scalabilitatea necontrolată, de conjunctură, condusă de evenimente transformă managementul rețelei într-o problemă de optimizare multicriterială.

Menținerea funcționării unui sistem de comunicații presupune stabilirea unui set de rute între surse și destinații.

Indiferent de tipul protocoalelor de rutare, indiferent dacă sunt bazate pe starea legăturilor sau pe vectori distanță, în momentul actual ele sunt bazate pe algoritmul lui Dijkstra pentru calcularea rutei minime. Deoarece determinarea rezultatului este în timp de cu variante, în funcție de reprezentarea grafului de , unde |E| reprezintă numărul de link-uri între două vârfuri adiacente iar |V| numărul de vârfuri, creșterea complexității rețelei va determina un timp de rulare crescut al algoritmului. O dinamică crescută și un sistem de comunicații complex poate conduce la imposibilitatea calculării deterministe a rutelor în timp util.

Articolul [29] propune o soluție bazată pe algoritmi genetici pentru a asigura funcționarea acestui tip de rețele, asigurând alocarea eficientă a resurselor și respectarea calității serviciilor, problema rutării fiind prezentată ca o minimizare a funcției:

Unde

S este sursa

D este destinația

este costul rutei dintre nodurile i și j

este un parametru boolean care specifică dacă între nodurile i și j există o rută directă, fiind de forma:

Din punct de vedere al reprezentării, un cromozom definește o rută, genele acestuia fiind

noduri intermediare între sursă și destinație.

Pe parcursul rulării algoritmului se urmărește minimizarea valorii fitness-ului cromozomilor pe parcursul generațiilor, funcția fitness fiind definită de ecuația:

Unde

este valoarea fitness-ului pentru cromozomul i

este lungimea cromozomului i

reprezintă costul legăturii dintre 2 noduri adiacente a și b

Întrucât algoritmul urmărește optimizarea funcționării rețelei, costul include parametrii

link-ului, fiind de forma:

.

Crossover-ul aplicat în articol este într-un punct de tăietură iar mutația este aleatoare, afectând 5% din populație.

Criteriul de oprire al algoritmului este o populație stabilă împreună cu un timp maxim de rulare.

Studiul a urmărit rezultatele produse de un algoritm genetic pentru identificarea drunului cu cost minim într-o graf, în funcție de numărul de muchii existente, pentru număr diferit de cromozomi în generații, luând ca o constantă timpul de rulare.

Din punct de vedere experimental, rețelele au fost reprezentate sub formă de graf, având un număr de 50 noduri.

Utilizând o rețea generată aleator, cu 50 de noduri și 1000 link-uri, care are ruta de cost minim între două noduri desemnate cu valoare 3 iar următoarea rută ca valoare dintre cele două noduri având valoarea 4, rulând un algoritm genetic cu 100 cromozomi atât pentru generația părinților cât și pentru generația urmașilor, timpul dintre 2 iterații este crescut datorită numărului de calcule. Pentru același interval de timp, la 10 rulări ale algoritmului, a fost generată ruta de cost 4 de 3 ori și de 7 ori ruta cu cost minim 5. Dacă numărul de cromozomi din generații a fost scăzut la 50, în 10 rulări pentru același interval de timp, a fost identificată ruta cu cost minim 3 de 2 ori, ruta cu cost minim 4 de 5 ori si de 2 ori ruta cu cost minim 5. Pentru generații de 30 cromozomi, în același timp a fost identificată ruta cu cost minim 3 de 5 ori, ruta cu cost minim 4 de 4 ori și ruta cu cost 5, o dată iar pentru 20 cromozomi în generație a fost identificată valoarea 3 ca minim de 5 ori și valoarea 4 de 5 ori.

În toate cazurile, ruta cu valoare 5 a fost identificată după aproximativ 10% din timpul de rulare.

Utilizând o rețea generată aleator, cu 50 de noduri și 200 link-uri, care are ruta de cost minim între două noduri desemnate cu valoare 4 iar următoarea rută ca valoare dintre cele două noduri având valoarea 5, rulând un algoritm genetic cu 100 cromozomi atât pentru generația părinților cât și pentru generația urmașilor, și în acest caz timpul dintre 2 iterații este crescut. Pentru același interval de timp, la 10 rulări ale algoritmului, a fost generată ruta de cost 6 o dată și de 9 ori ruta cu cost minim 8. Dacă numărul de cromozomi din generații a fost scăzut la 50, în 10 rulări pentru același interval de timp, a fost identificată ruta cu cost minim 6 o dată, ruta cu cost minim 6 de 5 ori si de 4 ori rute cu cost mai mare de8. Pentru generații de 30 cromozomi, în același timp a fost identificată ruta cu cost minim 5 o dată, ruta cu cost minim 8 de 9 ori iar pentru 20 cromozomi în generație a fost identificată valoarea 6 ca minim o dată și valoarea 8 de 9 ori. În toate cazurile, ruta cu valoare 8 a fost identificată după aproximativ 10-15% din timpul de rulare.

Așa cum se observă în teste și cum este prezentat și în articol, utilizarea algoritmilor evolutivi

pentru identificarea drumului de cost minim este eficientă pentru grafuri dens conectate, unde ruta optimă sau aproape de această valoare este detectată în timp scurt.

Un număr mare de cromozomi în populație implică un număr proporțional de calcule, cu

implicații în timpul necesar al unei iterații. Chiar dacă acoperirea spațiului de căutare este foarte bună, timpul de convergență este mare, ruta optimă fiind rar detectată.

Scăderea dimensiunii populațiilor accelerează funcționarea căutării, ruta de cost minim fiind

detectată mult mai des decât în cazul anterior, deci algoritmul se îndreaptă mai rapid spre convergență.

Situație este diferită în cazul unor grafuri cu număr scăzut de muchii. În același interval de

timp utilizat pentru grafurile dens conectate, ruta optimă a fost detectată mai rar, în acest caz, algoritmii determiniști fiind mai adecvați.

Explorarea posibilităților unui controller SDN adaptiv

Prin utilizarea capacității de a controla traficul de date, în controller-ul rețelelor SDN pot fi

implementate funcții de alocare dinamică a resurselor, bazate pe tehnici genetice.

În [25] autorii propun o soluție de rutare într-un mediu SDN, soluție bazată de o arhitectură SAEN. Chiar dacă aceast mediu este este un concept nou în managementul rețelelor, fiind dezvoltat pentru a răspunde cerințelor sistemelor de comunicații mari și cu dinamicitate ridicată, întrucât este bazat pe algoritmii de rutare clasici, nu oferă rezultate optime în medii cu dezvoltare exponențială, impredictibilă.

Întrucât la nivelul acestui tip de rețele sunt prezente date în timp real referitoare la starea și

parametrii întregii infrastructuri de comunicații și a necesarului de servicii, este posibilă implementarea unui algoritm genetic care să genereze soluții de configurare a elementelor de comunicații.

În vederea testării, a fost implementat un algoritm genetic cu o populație de 50 cromozomi, selecția bazată pe fitness, mutație aleatoare în proporție de 5% iar operatorul de crossover în un punct de tăietură. Rețeaua de test a fost generată având 2000 noduri și 15000 link-uri, costul link-ului fiind, aleator, în intervalul de valori 1-10.

Au fost executate 10 rulări ale algoritmului, utilizând 10 rețele generate aleator, pentru fiecare rețea fiind generată altă populație inițială. A fost urmărit numărul de generații după care algoritmul ajunge în starea de convergență și valoarea minimă a fitness-ului. Rezultatele sunt prezentate în tabelul următor:

Tabel 1 Rezultatele obținute în 10 rulări ale algoritmului genetic pentru 10 rețele generate aleator

Așa cum se observă din experimente și cum este specificat și în articol, rularea unui algoritm genetic utilizând o rețea cu un număr mare de noduri și link-uri va genera un set de soluții adecvate problemei după un număr relativ mic de generații. Rezultatul nu este neapărat cel mai bun dar îndeplinește cerințele impuse și este livrat în timp util, caracteristici care recomandă utilizarea acestori algoritmi în rețele dinamice.

Generarea genetică a unei rețele Internet of Thinks suprapuse

În prezent, Internet of Things reprezintă una din noile tendințe de evoluție a zonei IT. În astfel

de sisteme informatice, parametrii sistemului de comunicații sunt importanți, iar, pentru îmbunătățirea acestora una din soluții este utilizarea unei rețele suprapuse peste infrastructura de comunicații avută la dispoziție. În lucrarea [27] autorii propun generarea prin metode genetice a unei astfel de topologii de comunicații, bazându-se pe infrastructura existentă și pe cerințele se servicii impuse.

Ca funcționare, o rețea IoT implică un schimb de date între mai multe entități, utilizând o structură de comunicații care poate fi atât una publică cât și una dedicată. Este posibil ca în caziul unei rețele publice să existe momente cand aceasta nu este disponibilă sau nu oferă parametrii optimi pentru transferul de date. Mai mult decât atât, datorită heterogenității componentelor și a a serviciilor, comunicația între elementele IoT poate necesita o arhitectură specifică. Întrucât este dificil de construit și întreținut o rețea proprie unui sistem IoT, mai ales dacă este implementat pe o arie geografică mare, o soluție eficientă este construirea unei rețele suprapuse peste infrastructura de comunicații disponibilă în zonă. Arhitectura unui astfel de sistem de comunicații este prezentată în figura următoare.

Figure 26 Arhitectura unei rețele suprapuse [30]

Din punct de vedere al avantajelor, o astfel de rețea poate îmbunătăți disponibilitatea și întârzierile rețelelor gazdă dar prezintă o creștere a complexității și o scădere a benzii de transfer disponibile datorită informației suplimentare adăugate. Nodurile sunt plasate astfel încât să poată oferi o îmbunătățire a performanței, fiind noduri de tip releu între nodurile generatoare de date si destinație.

Figure 27 Exemplu de rețea pe două straturi [31]

Plasarea nodurilor într-o rețea stratificată poate fi descrisă prin utilizarea grafurilor, fiecare nod releu fiind un varf al unui graf iar legătura dintre acestea fiind muchiile. Fiecare muchie are un cost. Este necesară identificarea configurațiilor pentru care costul rutei dintre sursă și destinație să fie minim. Fiind vorba de un set de soluții, este oferită și redundanța, în fiecare moment putându-se opta pentru o rută alternativă.

Prin utilizarea tehnicilor genetice este posibilă generarea seturilor de soluții cu minimizarea costurilor, în [27] autorii implementând un algoritm genetic si testând funcționarea acestuia pe diferite tipuri de rețele.

În algoritmul genetic utilizat, cromozomii definesc rutele, genele reprezentând noduri intermediare între sursă și destinație.Scopul algoritmului este minimizarea costului rutei dintre sursă și destinație. Operatorul de selecție alege dintre 2 cromozomi pe cel mai adaptat și îl promovează spre generația următoare. Crossover-ul implementat este într-un punct de tăiere, la jumătatea rutei. Mutația este aleatoare, în proporție de 5%. Criteriul de oprire al algoritmului este numărul de iterații (100).

Testele au fost efectuate asupra a cinci rețele generate aleator, cu următorii parametrii:

100 noduri, 4000 link-uri între noduri, the link-uri costs între 0 and 10;

80 noduri, 28000 link-uri între noduri, costul link-uri fiind aleator între 0 și 10;

60 noduri, 1500 link-uri între noduri, costul link-uri fiind aleator între 0 și 10;

40 noduri, 650 link-uri între noduri, costul link-uri fiind aleator între 0 și 10;

20 noduri, 150 link-uri între nodes costul link-uri fiind aleator între 0 și 10.

Au fost efectuate testele cu un număr de 10, 20, 25, 30 și 40 cromozomi în generații. Fiecare algoritm a fost rulat de 10 ori cu același set de date.

Evoluția fitness-ului total este prezentată în figura 28, valorile reprezentate fiind mediile celor zece rulări ale algoritmului.

Figura 28 Valorile medii ale fitness-ului pentru cele 5 tipuri de rețele în cadrul generării rețelelor suprapuse.

Ca rezultate, pentru rețeaua cu 100 noduri au fost generate 23 rute distincte care conțin un total de 34 noduri, pentru rețeaua cu 80 noduri au rezultat 14 rute distincte cu 27 noduri, pentru cea cu 60 noduri, 12 rute care conțin 60 noduri. Pentru rețeaua cu 40 noduri au fost generate 10 rute distincte cu 11 noduri iar pentru cea cu 20 noduri au rezultat 6 rute separate cu 7 noduri.

Din rezultatele obținute rezultă că este posibilă aplicarea tehnicilor evolutive pentru generarea unei rețele suprapuse peste o rețea existentă. Cu cât rețeaua este mai complexă, cu atât numărul de soluții oferite este mai mare.

Metode de optimizare a algoritmilor genetici utilizați pentru managementul infrastructurii de comunicații a sistemelor distribuite.

Context

Lucrări conexe referitoare la optimizarea algoritmilor genetici utilizați pentru managementul infrastructurii de comunicații a sistemelor distribuite

Mutarea adaptivă în algoritmii genetici de calculare a rutei minime

În lucrarea [19] autorul propun un operator de mutație adaptiv pentru accelerarea convergenței

unui algoritm genetic utilizat pentru a calcula drumul cu cost minim într-un graf.

Implementarea operatorului de mutație asigură atât parcurgerea întregului spațiu al soluțiilor cât și evitarea alterării cromozomilor cei mai adecvați și implicit a evoluției algoritmului spre convergență.

Pentru evitarea convergenței spre o soluție locală în detrimentul celei globale, este necesar ca populația de cromozomi să fie distribuită în întreg spațiul soluțiilor. Măsura distribuției și implicit măsura diversității populației este un parametru pe baza căruia operatorul de mutație va acționa asupra populației de cromozomi. Pentru aceasta, autorul a definit un ”cromozom central” care nu va fi în mod necesar o soluție a problemei dar la care se vor raporta ceilalți cormozomi din populație pentru a evalua diversitatea. Fiecare componentă a cromozomului (alelă) central va fi definită ca medie aritmetică a alelelor din același locus al fiecărui cromozom al populației. Deci cromozomul central va fi de forma:

Fiecare alele fiind calculată conform formulei:

Unde:

N este numărul de cromozomi din generație

x(k) este alela numărul k din cromozom

este alela k din cromozomul central

Calcularea distanței dintre cromozomi este definită în lucrare de formula:

Unde:

sunt cromozomii din generația k

sunt alelele numărul n din cromozomii.

În momentul în care algoritmul e convergent distanța dintre cromozomul central și

cromozomii componenți ai generației are valoare mică. Dacă toți cromozomii din generație sunt identici, cromozomul central va fi identic cu ei, deci distanțava avea valoarea 0.

Pentru asigurarea diversității din punct de vedere al fenotipului, va fi mutat cromozomul cel

mai apropiat de cromozomul central.

Rata de mutație este un alt parametru important al operatorului de mutație. În algoritmul genetic standard rata este constantă, fiind greu de realizat echilibrul dintre divergența crossover-ului și mutației și convergența selecției.

O rată de mutație adaptivă asigură echilibrul divergență/convergență al algoritmului prevenind convergența prematură. Parametrul care determină probabilitatea de mutație este măsura diversității în populație, acesta fiind descris de formula:

Unde

este cromozomul din generația k

este cromozomul central din generația k.

O valoare mică a diversității relevă faptul că majoritatea cromozomilor sunt grupați într-o arie

restrânsă din spațiul soluțiilor, în jurul cromozomului central iar o valoare mare definește distribuirea acestora pe o suprafață mai mare. Întrucât populația centrală este generată aleator, inițial diversitatea are o valoare mare, care va scădea pe măsură ce algoritmul evoluează spre convergență. Pentru a asigura parcurgerea spațiului soluțiilor, diversitatea nu va trebui să scadă sub un anumit prag (pentru acest articol, pregul fiind stabilit de autor la 0,1 din valoarea calculată pentru generația inițială).

Utilizând această măsură a diversității, procentul de mutație va fi:

Unde:

este procentul de mutație în generația x

este măsura diversității în generația x

este valoarea minimă a diversității

Procentul de mutație maxim va fi cel din generația inițială. Dacă din calcule va

rezulta mai mare decât procentul maxim de mutație, atunci va fi acea valoare maximă.

În lucrare operatorul de crossover utilizat va fi într-un singur punct de tăietură, la mijlocul cromozomului.

Selecția va fi în funcție de valoarea fitness-ului cromozomilor, dintre o pereche fiind selectat cel mai bine adaptat.

Criteriul de oprire al algoritmului este stabilit pentru această implementare ca un număr maxim de generații.

Lucrarea urmărește evoluția valorii fitness-ului comparând valorile obținute la utilizarea mutației clasice și a celei adaptive. Rețeaua utilizato este formată din 100 noduri și 4000 muchii. Costul maxim al unei muchii are valoarea 10 : Populațiile utilizate sunt formate din câte 40 cromozomi, procentul de mutație pentru mutația clasică este de 10% iar fiecare algoritm rulează de 5 ori cu același set de date.

Rezultatul testelor este prezentat în figura 29 iar în figura 30 este prezentată evoluția probabilității de mutație în timpul rulării algoritmului.

Figure 29 Evoluția fitness-ului mediu pentru mutația adaptivă/neadaptivă

Figure 30 Evoluția probabilității de mutație pe parcursul a 100 generații

Din analiza rezultatelor obținute se observă o valoare mai mică a fitness-ului total pentru algoritmul genetic ce utilizează mutația adaptivă cât și o scădere mai abruptă a acestei valori în primele generații. Dacă în algoritmul genetic cu mutație clasică tendința de scădere a diversității poate afecta înclusiv cromozomii bine adaptați (mutația având loc aleator), prin utilizarea mutației adaptive, care afectează cromozomii cei mai apropiați de cromozomul central, se realizează atât parcurgerea mai riguroasă a spațiului soluțiilor iar soluțiile cele mai bine adaptate sunt neafectate.

Operatorul de crossover adaptiv bazat pe distribuția soluțiilor în spațiul de căutare

În [28] autorii analizează o variantă adaptivă a operatorului de crossover, care utilizează ca

parametrii atât fitness-ul cromozomilor cât și poziția relativă a acestora față de ceilalți cromozomi componenți ai populației, fiind urmărită o îmbunătățire a convergenței căutării.

La detectarea soluției, populația de cromozomi are o valoare minimă a fitness-ului iar aceștia sunt grupați într-o regiune limitată a spațiului de căutare, în jurul valorii optime.

Adaptabilitatea operatorului de crossover asigură atât evitarea convergenței premature și minimizarea timpului în care valoarea fitness-ului tinde spre minum, modificând cantitatea de informații schimbată între cei doi cromozomi supuși operatorului genetic.. Astfel, probabilitatea de crossover trebuie să fie ridicată când populația de soluții are o diversitate scăzută iar valoarea fitness-ului este mare (dacă se urmărește minimizarea acestuia) sau mică (dacă de urmărește maximizarea lui), fiind de forma:

Unde

este componenta care e dependentă de valoarea fitness-ului din probabilitatea totală

este componenta care e dependentă de distribuția în spațiu a cromozomilor din probabilitatea totală

A este un parametru întreg care exprimă influența altor condiții (de mediu, structură a populației, etc.) asupra probabilității totale de crossover

Așa cum este descrisă în [32], trebuie să fie mică pentru a nu altera cromozomii

bine adaptați și mai mare atunci când diversitatea scade, deci când diferența dintre fitness-ul curent și cel mediu este mic. Atunci:

Unde:

k este o constantă

este valoarea maximă a fitness-ului din populație

este valoarea fitness-ului cromozomului curent

este valoarea medie a cromozomilor din generație

Referitor la componenta dependentă de distribuția în spațiul de căutare, , aceasta

trebuie să fie direct proporțională cu distanța dintre cromozomul curent și cromozomul central și invers proporțională cu distanța dintre cromozomul cu fitness maxim din generație și cel central, noțiunile de distanță dintre cromozomi și cromozom central fiind descride în lucrarea [19].

Astfel:

Unde:

M este o constantă

este cromozomul curent

este cromozomul central

este cromozomul cel mai bine adaptat din generație

este distanța dintre cromozomii a și b

În articol se urmărește minimizarea fitness-ului, deci probabilitatea de crossover va fi definită

de formula:

.

Această valoare va determina numărul de gene care vor fi schimbate între cromozomi la rularea operatorului de crossover.

Pentru evaluarea influenței crossover-ului adaptiv a fost studiată evoluția valorii fitness-ului la utilizarea unui algoritm genetic clasic, a unuia cu crossover adaptiv și mutație clasică și la unul cu crossover și mutație adaptivă, operatorul de mutație adaptiv fiind descris în articolul [19].

Algoritmii au rulat 10 generații. Probabilitatea pentru mutația clasică a fost de 5%, crossover-ul clasic a fost într-un punct de tăietură la mijlocul cromozomului, graful a fost generat aleator, având 80 noduri și 1500 muchii, costul muchiei a fost generat aleator în intervalul 1-10. Parametrul adin probabilitatea de mutație a avut valoarea 1. Rezultatele obținute au fost prezentate în graficele ce urmează.

Au fost studiate rezultatele obținute pentru dimensiunea populaților de 20 și 30 de cromozomi. Fiecare algoritm a fost rulat de 9 ori.

Pentru o dimensiune a populațiilor de 20 cromozomi:

Figure 31 Evoluția mediei fitness-ului în 10 generații pentru cele trei variante de algoritm genetic implementate

Figure 32 Evoluția fitness-ului pentru algoritmul genetic clasic

Figure 33 Evoluția fitness-ului pentru algoritmul genetic cu mutație adaptivă și crossover clasic

Figure 34 Evoluția fitness-ului pentru algoritmul genetic cu mutație și crossover adaptiv

Pentru o populație de 30 de cromozomi:

Figure 35 Evoluția mediei fitness-ului în 10 generații pentru cele trei variante de algoritm genetic implementate

Figure 36 Evoluția fitness-ului pentru algoritmul genetic clasic

Figure 37 Evoluția fitness-ului pentru algoritmul genetic cu mutație adaptivă și crossover clasic

Figure 38 Evoluția fitness-ului pentru algoritmul genetic cu mutație și crossover adaptiv

Din analiza rezultatelor rezultă că utilizarea operatorilor genetici adaptivi descriși asigură o rulare spre convergență a algoritmului genetic îmbunătățită față de cei clasici.

Din punct de vedere al evoluției fitness-ului mediu se observă că operatorii adaptivi îmbunătățesc convergența. Crescând numărul de cromozomi din generație asigură o nposibilitate de parcurgere mai bună a spațiului soluțiilor, în final reducându-se influența operatorilor adaptivi, dar efectuându-se un număr mai mare de operații matematice în timpul rulării.

Din analiza rulărilor algoritmilor se observă că, indiferent dacă populațiile de cromozomi diferă ca număr, combinația de operatori adaptivi de crossover și mutație oferă rezultate superioare și cu o uniformitate mai mare. Scăderea fitness-ului total pe parcursul generațiilor este mai abruptă la utilizarea operatorilor adaptivi.

Influența condițiilor de mediu asupra crossover-ului adaptiv bazat pe distribuția cromozomilor în spațiul de căutare

În articolul [26] este studiată înfluența condițiilor de mediu (dinamica rețelei, gradul de

conectare al echipamentelor de comunicații, elemente dependente de timp, etc.) asupra crossover-ului adaptiv propus în lucrarea [28]. Luându-se în considerare operatorul crossover adaptiv descris în lucrarea [28], influența condițiilor de mediu este codată în parametrul a, o valoare optimă accelerând convergența.

Pentru a asigura o funcționare corectă a căutării evolutive, acest parametru trebuie să fie plasat într-o plajă de valori. O valoare mică diminuează schimbul de informații între cromozomi și implicit o convergență dificilă, spre soluții locale. O valoare prea mare transformă căutarea într-o parcurgere aleatoare a spațiului de căutare, algoritmul nemaifiind capabil de tranbsfer de informație între generații.

Testarea influenței parametrului a a fost efectuată utilizând un algoritm genetic cu operatorul crossover adaptiv, cu populații de 30 cromozomi. Operatorul de mutație a fost clasic, aleator, cu probabilitatea de mutație de 5%. Au fost utilizate două grafuri, primul cu 80 noduri și 1500 muchii iar al doilea cu 20 noduri și 2500 muchii. Parametrul a a avut valorile 0, 0,5, 1, 1,5, 2, 2,5, 3 și 10. Rezultatele sunt prezentate în figurile următoare:

Utilizând un graf cu 80 noduri și 1500 muchii

Figure 39 Evoluția fitess-ului pentru a=0

Figure 40 Evoluția fitness-ului pentru a=0,5

Figure 41 Evoluția fitness-ului pentru a=1

Figure 42 Evoluția fitness-ului pentru a=1,5

Figure 43 Evoluția fitness-ului pentru a=2

Figure 44 Evoluția fitness-ului pentru a=2,5

Figure 45 Evoluția fitness-ului pentru a=3

Figure 46 Evoluția fitness-ului pentru a=10

Figure 47 Evoluția fitness-ului mediu la utilizarea crossover-ului adaptiv și a celui clasic

Utilizând un graf cu 80 noduri și 2500 muchii

Figure 48 Evoluția fitness-ului pentru a=0

Figure 49 Evoluția fitness-ului pentru a=0,5

Figure 50 Evoluția fitness-ului pentru a=1

Figure 51 Evoluția fitness-ului pentru a=1,5

Figure 52 Evoluția fitness-ului pentru a=2

Figure 53 Evoluția fitness-ului pentru a=2,5

Figure 54 Evoluția fitness-ului pentru a=3

Figure 55 Evoluția fitness-ului pentru a=10

Figure 56 Evoluția fitness-ului mediu la utilizarea crossover-ului adaptiv și a celui clasic

Analizând rezultatele obținute se poate observa ca in toate cazurile algoritmul a evoluat spre convergență. În funcție de valorile atribuite parametrului a se pot observa diferențe referitoare la rezultatele obținute.

Pentru a=0 rezultatele generate au o dispersie mare, ceea ce este normal întrucât practic are loc o inversare a celor doi cromozomi (=0), nemaiavând loc crossover-ul, algoritmul genetic funcționând cu mutația și selecția ca operații principale.

Crescând valoarea atribuită lui a se observă în grafice faptul că dispersia rezultatelor scade, valoarea minimă obținându-se în intervalul de valori 1-1,5, atât pentru grafurile dense cât și pentru cele mai puțin dense. Tot pentru acest interval de valori se obțin valorile cele mai bune pentru fitness-ul cromozomilor la sfârșitul celor 10 iterații. Continuând creșterea valorii parametrului a practicscade cantitatea de material genetic schimbată între cromozomi, ceea ce produce creșterea dispersiei valorilor fitness-ului obținute. O valoare mare a parametrului (a=10) practic blochează funcționarea, algoritmul fiind o căutare aleatoare în spațiul soluțiilor.

Din punct de vedere al valorilor medii obținute, se observă vă evoluția spre convergență îm cazul crossover-ului adaptiv este mai abruptă și fitness-ul obținut este mai mic. Valorile minime sunt obținute în intervalul 1-1,5.

Analizând aceste observații, rezultă că, atât pentru grafuri mai slab conectate cat și pentru grafuri mai dens conectate, o codare corectă a diverșilor factori de mediu într-o valoare care parametrizează probabilitatea de crossover accelerează convergența algoritmului genetic.

Concluzii

Scopul acestei teze a fost identificarea de metode de optimizare multicriterială a sistemelor

informatice. Ca urmare, ținând cont de realitățile prezente și de direcțiile predictibile de evoluție, au fost propuși și implementați algoritmi evolutivi pentru optimizarea parametrilor de funcționare a acestor sisteme iar testele efectuate au confirmat eficienta acestei abordări. În completare, în lucrare au fost propuse metode de optimizare a funcționării acestor algoritmi.

Pe parcursul tezei s-a avut în vedere identificarea de soluții care să poată completa metodele clasice în condițiile în care complexitatea și dinamicitatea sistemelor distribuite sunt deja caracteristici prezente iar tendința este de accelerare a lor. Ca urmare, testele au fost efectuate luându-se în considerare modificări ale complexității problemei abordate.

Propunerile de metode de optimizare au fost direcționate spre zona de comunicații, ca element principal al unui sistem informatic distribuit.

Discuții și rezultate

Deoarece rețeaua are un rol determinant în existența unui sistem informatic distribuit, starea

de funcționare a acesteia este definită de un set de parametrii (rute, capacitate de transport, evoluție în timp, întârzieri, protocoale transportate, etc.) . În prezent acești parametrii sunt interpretați ca elemente de sine stătătoare iar modificarea acestora reprezintă activități independente (rutare, prioritizare a traficului, QoS,limitare a traficului, etc.), cu toate că între ei există o strânsă legătură. În lucrare a fost propusă o soluție evolutivă de stabilire a rutelor ținând cont de toți parametrii infrastructurii de comunicații, de cerințele utilizatorilor precum și de tendințele de evoluție a acestor parametrii și de istoricul lor.

În contextul managementului și optimizării rețelelor de mari dimensiuni, în teză a fost studiată posibilitatea de utilizare a tehnicilor genetice pentru identificarea rutelor de cost minim. Din testele efectuate pe grafuri cu parametrii diferiți din punct de vedere a densității muchiilor, a rezultat că algoritmii genetici sunt o soluție ce oferă rezultate bune pentru grafurile dense (caracteristică a rețelelor complexe), pentru grafurile mai puțin dense soluțiile clasice fiind favorizate.

Referitor la noile tendințe și concepte apărute în domeniul comunicațiilor, a fost studiată posibilitatea utilizării algoritmilor genetici în cadrul sistemelor IoT și în cadrul virtualizării rețelelor.

Ținând cont de faptul că internetul lucrurilor este definit de un număr mare de elemente conectate la Internet, ele funcționând ca o rețea virtuală, suprapusă peste o infrastructură de comunicații, au fost efectuate teste referitoare la posibilitatea generării genetice a arhitecturii rețelei IoT având ca suport infrastructura Internet. Testele au fost efectuate pe rețele de diferite dimensiuni (din punct de vedere al nodurilor și muchiilor) și au demonstrat că după un număr relativ redus de generații de cromozomi, algoritmul genetic a fost capabil să ofere un set de soluții (de arhitecturi de rețea suprapusă)cu o valoare bună a fitness-ului, deci adecvate scopului propus.

Tot în contextul noilor tehnologii a fost propusă utilizarea algoritmilor genetici în cadrul controller-ului SDN pentru a genera soluții de configurare a elementelor hardware componente a rețelei virtuale. Luându-se în considerare o rețea complexă (2000 noduri și 15000 de link-uri), au fost efectuate teste și a rezultat că pentru fiecare rulare a algoritmului genetic , acesta oferă în timp util (ca număr de generații) soluții valabile.

Din punct de vedere al optimizării căutării evolutive, în cadrul tezei s-au studiat metode de autoadaptare a operatorilor genetici.

Scopul autoadaptării este îmbunătățirea funcționării algoritmului genetic atât din punct de

vedere al timpului necesar pentru a ajunge în starea de convergență cât și din punct de vedere al calității soluțiilor generate (dispersie redusă a rezultatelor, prezentare de soluții optime generale, nu optime locale).

Deoarece operatorii de mutație și crossover realizează echilibrul convergență/divergență, mutația având un caracter divergent iar croossover-ul unul convergent, autoadaptarea urmărește păstrarea echilibrului în funcție de caracteristicile populației de cromozomi astfel încât algoritmul să fie caracterizat de o convergență rapidă și de o parcurgere adecvată a spațiului de căutare pentru identificarea celor mai bune soluții. Se urmărește atât favorizarea cromozomilor bine adaptați cât și păstrarea diversității populației.

Ca operator genetic, mutația păstrează diversitatea populației prin modificarea aleatoare a unui procent din cromozomi. În teză a fost propusă o variantă adaptivă a mutației, bazată pe distribuția în spațiu a acestora. Având în vedere că la convergență fitness-ul populației este minim/maxim (în funcție de problemă) iar mulțimea de cromozomi este distribuită într-o vecinătate a soluției optime, operatorul de mutație propus în teză îi va modifica pe cei mai apropiați de un ”cromozom central”, acesta fiind definit ca medie a cromozomilor componenți ai populației din punct de vedere al poziției acestora în spațiu. În cazul convergenței algoritmului, mutația afectând un procent din numărul de cromozomi, chiar dacă sunt afectați indivizi bine adaptați, starea de convergență asigură faptul că soluția optimă are mari șanse să fie păstrată în populație. În cazul în care cromozomii sunt distribuiți în întreg spațiul de căutare, probabilitatea ca cel mai bine adaptat individ din populație să fie și cel mai apropiat de cromozomul central (și să fie alterat de mutație) este mai mică decât în cazul mutației clasice, cu cromozomi alterați aleator.

Pentru a fi păstrată diversitatea, probabilitatea de mutație este adaptivă, fiind mai mare când populația este uniformă și mai mică în condițiile existenței diversității.

Din testele efectuate a rezultat că, în comparație cu cu un mutația clasică, utilizarea mutației adaptive propuse conduce la o accelerare a îmbunătățirii fitness-ului pe parcursul generațiilor (deci o creștere a vitezei de convergență) cât și obținerea de rezultate mai bune după un număr fix de generații.

Utilizând noua noțiune de ”cromozom central”, în teză a fost propus un operator de crossover adaptiv care are volumul de schimbare a materialului genetic variabil, dependent atât de fitness-ul cromozomilor cât și de diversitatea populației, urmărindu-se o modificare minimă a cromozomilor bine adaptați. Astfel, cu cât diferența dintre fitness-ul cromozomului cel mai bine adaptat și fitness-ul mediu al populației este mai mare, cu atât diversitatea este mai mare, deci schimbul de informație genetică prin crossover poate fi mai mic. Referitor la cromozomii supuși crossover-ului, cu cât diferența dintre fitness-ul acestora și fitness-ul maxim este mai mică, cu atât volumul informației schimbate trebuie să fie mai mic deoarece cromozomul este bine adaptat.

Similar, referitor la dispunerea populației în spațiul de căutare, cu cât diferența dintre cromozomul central și cel cu fitness-ul cel mai bun este mai mică, cu atât populație este mai uniformă deci schimbul de informație trebuie să fie mai mare iar cu cât diferența dintre cromozomul central și cel curent este mai mare, cu atât diversitatea este mai mare, deci schimbul de informație dintre cromozomi trebuie să fie mai mare pentru a fi identificate soluțiile problemei date iar algoritmul să evolueze spre convergență.

Testele efectuate au verificat evoluția unui algoritm genetic cu operatori adaptivi, în comparație cu un algoritm genetic clasic. A rezultat că algoritmul genetic cu cu operatori de crossover și mutație adaptivi a evoluat mai rapid spre convergență în comparație cu algoritmul genetic clasic, din punct de vedere al fitness-ului mediu obținut în urma mai multor rulări ale algoritmilor pe aceeași rețea.

Din punct de vedere al fitness-ului generat la fiecare rulare, a rezultat că se obține o dispersie mai mică a rezultatelor în cazul operatorilor adaptivi față de algoritmul genetic cu operatori clasici.

Adaptabilitatea algoritmilor genetici este determinată de capacitatea operatorilor genetici de a-și modifica parametrii, valorile optime fiind caracteristice fiecărui tip de problemă. Stabilirea valorilor optime este importantă deoarece influențează convergența căutării. Totodată, funcționarea mecanismului evolutiv este influențată de echilibrul convergență-divergență asigurat de mutație și crossover, el putând fi modificat prin ponderarea rezultatelor oferite de aceștia cu valori care reprezintă influența altor factor externi, generici, nereprezentați în funcția fitness (densitate a grafului, mărimea acestuia, etc.).

În teză s-a urmărit identificarea unui interval optim în care ar trebui să fie valoarea care ponderează crossover-ul adaptiv pentru ca algoritmul genetic să funcționeze corect. În acest sens au fost testate mai multe valori, inclusiv extreme (valoarea 0 ca margine inferioară valoare 10 ca margine superioară) pentru grafuri cu densități diferitre a muchiilor. Precum era de așteptat valorile extreme au produs efecte negative asupra rezultatelor generate de algoritm, atât ca valoare a fitness-ului cât și ca dispersie a rezultatelor, ținând cont că practic în aceste cazuri, crossover-ul devine nefuncțional, algoritmul fiind practic o căutare bazată pe gradient.

Din întregul set de teste efectuate, a rezultat că valoarea optimă a termenului de ponderare se află în intervalul 1-1,5, interval în care se poate observa că valoarea medie a fitness-ului este minimă (fiind efectuate un număr de teste pentru fiecare valoare propusă a ponderii).

Analizând rezultatele obținute la fiecare rulare a algoritmului, tot în intervalul menționat se obține o valoare minimă a dispersiei valorilor fitness-ului.

Luând în considerare studiile efectuate în cadrul tezei, metodele de optimizare s-au concentrat pe abordarea evolutivă a problemelor generate de dinamica și noile tehnologii apărute în evoluția sistemelor informatice distribuite. În plus, în teză au fost propuse variante de optimizare a algoritmilor genetici utilizați, variante care au avut ca scop îmbunătățirea rezultatelor generate și minimizarea dispersiei acestora. Rezultatele au demonstrat că metodele și variantele de operatori genetici sunt soluții ale problemelor apărute ca urmare implementării de noi concepte, a dinamicii, heterogenității și mărimii sistemelor informatice distribuite actuale.

Limitări ale tezei

Principalele limitări ale tezei sunt cele caracteristice ale domeniilor abordate: concepte noi

apărute și faptul că se adresează sistemelor distribuite din momentul actual.

Conceptele noi apărute au influențat cercetările din teză prin faptul că în acest moment sunt majoritatea în diverse stadii de dezvoltare, fără a fi aplicate la scară largă și într-o manieră standardizată. În consecință studiile au fost efectuate în condiții de simulare a unor astfel de sisteme, fiind posibilă existența de diferențe față de testele în condiții reale. Inclusiv lipsa de standardizare este o limitare, un standard ulterior care diferă de condițiile prezente putând influența major rezultatele.

Lipsa unui sistem informatic distribuit implementat fizic a necesitat conceperea de modele virtuale pentru testarea ipotezelor, de cele mai multe ori fiind modelat sub formă de graf. Rezultatele generate pe un astfel de model pot fi diferite față de rezultatele obținute într-un sistem real.

Testele s-au concentrat pe valorile rezultate din simulări în diverse condiții, majoritatea referitoare la dimensiunea și caracteristicile sistemului informatic sau la diverși tipuri de operatori și de parametrii ai algoritmilor genetici și mai puțin comparativ cu alte tehnici de căutare. În consecință datele obținute sunt caracteristice tehnicilor și metodelor cărora li se adresează teza.

Studii viitoare

Ținând cont de limitările prezentate anterior, continuarea studiilor de optimizare a sistemelor

informatice distribuite prin utilizarea de tehnici genetice ar trebui să se axeze pe implementarea și efectuarea de teste pe sisteme reale sau pe seturi de date oferite de acestea. Chiar dacă testarea pe modele virtuale, generate, este capabilă să ofere o relație cauză/efect sau o relație între diverse mărimi, în cazuri reale rezultatelepot fi diferite.

Pentru lărgirea bazei de comparație a rezultatelor obținute este necesară implementarea și a altor tehnici de căutare atât deterministe cât și probabilistice. Această comparație ar conduce da delimitarea domeniilor în care fiecare tehnică oferă cele mai bune rezultate. Deasemenea, pot fi identificate și alte implementări ale operatorilor genetici pretabile a fi abordate evolutiv.

Pentru accelerarea funcționării algoritmilor genetici studiile pot fi direcționate pe implementarea distribuită a acestora, datorită paralelismului intrinsec oferit de tehnicile evolutive. Combinația de accelerare hardware/ software poate fi distribuită atât pe elementele de calcul existente în sistem cât și pe echipamente dedicate acestui scop (matrici FPGA, conform studiului prezentat în [24]).

Anexe

Listă publicații

R. Maniu and L. A. Dumitru, "Self-adaptive networks with history extrapolation, evolutionary selection and realtime response," 2014 International Conference on Optimization of Electrical and Electronic Equipment (OPTIM), Bran, 2014, pp. 839-846.
doi: 10.1109/OPTIM.2014.6850973
keywords: {evolutionary computation;telecommunication network routing;SAEN architecture;adaptive operators;evolutionary selection;genetic algorithms;history behavior analysis;history extrapolation;holistic routing system;load-balancing technologies;optimal routing solution;realtime response;resource utilization;self adaptive evolutionary network;Biological cells;Genetic algorithms;Genetics;History;Routing;Sociology;Statistics},
URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6850973&isnumber=6850869

R. Maniu and L. A. Dumitru, “Genetic Algorithm – Adaptive Crossover Based on Solution Distribution in Search Space”, 2017 International Conference on Optimization of Electrical and Electronic Equipment (OPTIM), Bran, 2017 – IN CURS

L. A. Dumitru and R. Maniu,”A generic execution framework for shared FPGA-based accelerators”, 2017 International Conference on Optimization of Electrical and Electronic Equipment (OPTIM), Bran, 2017 – IN CURS

M. Rares, "Adaptive mutation in genetic algorithms for shortest path routing problem," 2015 7th International Conference on Electronics, Computers and Artificial Intelligence (ECAI), Bucharest, 2015, pp. S-69-S-74.
doi: 10.1109/ECAI.2015.7301163
keywords: {genetic algorithms;adaptive mutation operator;genotypic level;phenotypic level;shortest path routing problem;standard genetic algorithm;Biological cells;Convergence;Genetic algorithms;Genetics;Routing;Sociology;Statistics;adaptive mutation;evolving networks;genetic algorithms;routing},
URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=7301163&isnumber=7301133

M. Rares, " GENETIC TECHNIQUES APPLIED IN ACTUAL NETWORK MANAGEMENT" “Mircea cel Batran” Naval Academy Scientific Bulletin, Volume XVIII – 2015 – Issue 2 Published by “Mircea cel Batran” Naval Academy Press, Constanta, Romania, pp. 24-30.

L. A. Dumitru and R. Maniu, " EXPLORING THE POSSIBILITIES OF A SELF REGULATING SDN CONTROLLER" “Mircea cel Batran” Naval Academy Scientific Bulletin, Volume XVIII – 2015 – Issue 1 Published by “Mircea cel Batran” Naval Academy Press, Constanta, Romania, pp. 58-61

M. Rares, " GENETIC GENERATION OF INTERNET OF THINGS OVERLAY NETWORK INFRASTRUCTURE" “Mircea cel Batran” Naval Academy Scientific Bulletin, Volume XIX –2016 – Issue 2 Published by “Mircea cel Batran” Naval Academy Press, Constanta, Romania, pp. 446-450, DOI:10.21279/1454-864X-16-I2-067

M. Rares, " THE INFLUENCE OF ENVIRONMENTAL CONDITIONS OVER ADAPTIVE CROSSOVER BASED ON THE DISTRIBUTION OF CHROMOSOMES IN SEARCH SPACE" “Mircea cel Batran” Naval Academy Scientific Bulletin, 2017, Published by “Mircea cel Batran” Naval Academy Press, Constanta, Romania IN CURS DE APARITIE

Detalii de implementare

Testele au fost efectuate utilizând funcții implementate în limbajul de programare C++. A fost utilizat mediul de programare Eclipse Neon iar sistemul de operare a fost RedHat.

Declarațiile de clase și de funcțiile utilizate au fost următoarele:

class ruta

{

public:

int *r;

int dimensiune;

ruta(int nr)

{

r=new int[nr];

dimensiune=nr;

for(int i=0;i<nr;i++)

r[i]=0;

};

~ruta() {};

void set_elem(int pozitie, int valoare); //seteaza elem din pozitia cu valoarea

int ret_element(int pozitie); //returneaza elementul din pozitia

int ret_dimensiune(); //returneaza dimensiunea cromozomului

int lungime_ruta(); //calculeaza lungimea cromozomului

void mutatie(int procent, int nr_noduri_retea); //altereaza un nr de elemente ale rutei

void route_gen(int init, int final, int noduri); //genereaza ruta cu un nr de noduri, care incepe cu init si se termina cu fin

void print_route(); //afiseaza ruta

};

void net_gen(int net[][3]); //genereaza reteaua

void print_net(int net[][3]); //afiseaza reteaua

void reset_net(int net[][3]); //reseteaza toate elementele retelei

int valid_route(ruta a, int net[][3]); //testeaza daca ruta e valida

void crossover(ruta parinte1,ruta parinte2,ruta fiu1,ruta fiu2); // crossover la jumatatea cromozomilor

void crossover_adaptiv(ruta,ruta,ruta ,ruta, float, int, ruta **, int [][3]); // crossover la lung celui mai adaptat in fct de probabilitate

int cost_ruta(ruta a, int net[][3]); //calculeaza costul rutei

void net_to_file(int net[][3]); //scrie reteaua in fisier

int file_to_net(int net[][3]); //incarca reteaua din fisier

int elimina_bucle(ruta a);

int is_equal(ruta a, ruta b); //returneaza 1 daca rutele sunt egale si 0 daca nu

int entropie(int, ruta **, int [][3]); //calculeaza entropia dintr-o populatie

ruta centru(int, ruta **); //calculeaza centrul rutelor dintr-o populatie

int val_dif_cromozomi(ruta, ruta); //calculeaza dif dintre cromozomi dpdv al nodurilor

int cel_mai_aproape_de_mijloc(int, ruta **); //returneaza poz cromozomului cel mai apropiat de centrul cromozomilor

int Hamming(int, ruta **); //returneaza dist Hamming a populatiei

void mutatie_clasica(int,int, int, int, ruta **, int[][3]);

void mutatie_adaptiva(int, int, int, int, ruta **, int [][3]);

int fitness_minim_generatie(int, ruta **, int [][3]);

int fitness_mediu_generatie(int, ruta **, int [][3]);

int fitness_total_generatie(int, ruta **, int [][3]);

int cromozom_cu_fitness_minim(int, ruta **, int [][3]);

float probabilitate_crossover_adaptiv(float, int, ruta, ruta **, int [][3]);

float probabilitate_crossover_adaptiv_v1(float, int, ruta, ruta **, int [][3]);

Acronime

Listă de figuri

Figure 1 Arhitectura de nivel inalt a unui sistem M2M [2] 11

Figure 2 Interconectarea între doi provideri M2M 12

Figure 3 Dimensiunile IoT (ITU-T, 06.2012) 14

Figure 4 Obiecte din IoT (ITU-T, 06.2012) 14

Figure 5 Modelul de referință pentru IoT (ITU-T, 06.2012) 15

Figure 6 Dimensiunile calculului mobil (B'Far, 2005) 19

Figure 7 Arhitectura unui sistem raportat la context 22

Figure 8 Nivelele WSN 23

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

Figure 10 Virtualizarea hardware 27

Figure 11 Virtualizarea aplicațiilor 28

Figure 12 Arhitectura de referință NFV [10] 30

Figure 13 Arhitectura tradițională a rețelei 31

Figure 14 Arhitectura unei rețelei SDN 31

Figure 15 Arhitectura SDN 32

Figure 16 Nivelele oferite de cloud-computing 33

Figura 17. Coordonatele principale ale algoritmului genetic 42

Figure 18. Explorare-exploatare în căutarea genetică 43

Figure 19. Schema logică a unui algoritm genetic 44

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

Figura 21. Modificarea distribuției funcțiilor fitness 46

Figure 22. Crossover în un punct de tăietură 52

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

Figure 24. Crossover uniform 54

Figure 25 Automat cu stări finite 58

Figure 26 Arhitectura unei rețele suprapuse [30] 69

Figure 27 Exemplu de rețea pe două straturi [31] 69

Figura 28 Valorile medii ale fitness-ului pentru cele 5 tipuri de rețele în cadrul generării rețelelor suprapuse. 70

Figure 29 Evoluția fitness-ului mediu pentru mutația adaptivă/neadaptivă 73

Figure 30 Evoluția probabilității de mutație pe parcursul a 100 generații 74

Figure 31 Evoluția mediei fitness-ului în 10 generații pentru cele trei variante de algoritm genetic implementate 77

Figure 32 Evoluția fitness-ului pentru algoritmul genetic clasic 77

Figure 33 Evoluția fitness-ului pentru algoritmul genetic cu mutație adaptivă și crossover clasic 78

Figure 34 Evoluția fitness-ului pentru algoritmul genetic cu mutație și crossover adaptiv 78

Figure 35 Evoluția mediei fitness-ului în 10 generații pentru cele trei variante de algoritm genetic implementate 79

Figure 36 Evoluția fitness-ului pentru algoritmul genetic clasic 79

Figure 37 Evoluția fitness-ului pentru algoritmul genetic cu mutație adaptivă și crossover clasic 80

Figure 38 Evoluția fitness-ului pentru algoritmul genetic cu mutație și crossover adaptiv 80

Figure 39 Evoluția fitess-ului pentru a=0 82

Figure 40 Evoluția fitness-ului pentru a=0,5 82

Figure 41 Evoluția fitness-ului pentru a=1 82

Figure 42 Evoluția fitness-ului pentru a=1,5 83

Figure 43 Evoluția fitness-ului pentru a=2 83

Figure 44 Evoluția fitness-ului pentru a=2,5 83

Figure 45 Evoluția fitness-ului pentru a=3 84

Figure 46 Evoluția fitness-ului pentru a=10 84

Figure 47 Evoluția fitness-ului mediu la utilizarea crossover-ului adaptiv și a celui clasic 84

Figure 48 Evoluția fitness-ului pentru a=0 85

Figure 49 Evoluția fitness-ului pentru a=0,5 85

Figure 50 Evoluția fitness-ului pentru a=1 85

Figure 51 Evoluția fitness-ului pentru a=1,5 86

Figure 52 Evoluția fitness-ului pentru a=2 86

Figure 53 Evoluția fitness-ului pentru a=2,5 86

Figure 54 Evoluția fitness-ului pentru a=3 87

Figure 55 Evoluția fitness-ului pentru a=10 87

Figure 56 Evoluția fitness-ului mediu la utilizarea crossover-ului adaptiv și a celui clasic 87

Listă de tabele

Tabel 1 Rezultatele obținute în 10 rulări ale algrritmului genetic pentru 10 rețele generate aleator 68

Notații

Bibliografie