Investete n oameni !

FONDUL SOCIAL EUROPEAN

Proiect cofinanat din Fondul Social European prin Programul Operaional Sectorial pentru Dezvoltarea Resurselor Umane

2007 2013

Axa prioritar 1: Educaia i formarea profesional n sprijinul creterii economice i dezvoltrii societii bazate pe

cunoatere

Domeniul major de intervenie 1.5 "Programe doctorale i post-doctorale n sprijinul cercetrii"

Titlul proiectului: Q-DOC- Creterea calitii studiilor doctorale n tiine inginereti pentru sprijinirea dezvoltrii societii

bazate pe cunoatere

Contract : POSDRU/107/1.5/S/78534

Beneficiar: Universitatea Tehnic din Cluj-Napoca

FACULTATEA DE CONSTRUCII

Ing. Ioana D. Balea (Krucke)

TEZ DE DOCTORAT

STRATEGII DE OPTIMIZARE A STRUCTURILOR

METALICE BAZATE PE ALGORITMI GENETICI

Conductor tiinific,

Prof.Univ.Dr.Ing. George M. Brsan

______________________________2015____________________________

CUPRINS

1 Introducere ............................................................................................................ 0

1.1 Motivaia alegerii temei .................................................................................... 0

1.2 Obiective ........................................................................................................ 2

1.3 Structura lucrrii .............................................................................................. 4

2 Optimizare global vs. optimizare structural ............................................................ 8

3 Formularea matematic a problemelor de optim ...................................................... 12

3.1 Evaluarea modelului ...................................................................................... 13

3.1.1 Spaiul i subspaiul de proiectare ............................................................. 13

3.1.2 Subspaiul admisibil ................................................................................ 14

3.2 Metode de optimizare ..................................................................................... 19

4 Forme de optimizare structural ............................................................................. 25

4.1.1 Optimizarea topologic ............................................................................ 25

4.1.2 Optimizarea formei ................................................................................. 27

4.1.3 Optimizarea dimensional ........................................................................ 28

4.1.4 Optimizarea topografic ........................................................................... 29

5 Algoritmii stocastici ............................................................................................. 30

5.1 Algoritmii evoluioniti .................................................................................. 32

5.1.1 Algoritmii genetici .................................................................................. 32

5.1.2 Optimizarea structural evolutiv (ESO) .................................................... 44

5.1.3 Optimizare de tip PSO (particle swarm optimization) .................................. 46

5.1.4 Optimizare de tip Simulated Annealing ..................................................... 46

6 Strategii de optimizare .......................................................................................... 49

6.1 Direcii de cercetare ....................................................................................... 49

6.2 Optimizare Multi-Modal ............................................................................... 50

6.3 Eficien i incertitudine n procesul de optimizare ............................................ 52

6.4 Utilizarea unor forme naturale ......................................................................... 54

7 Variabile de proiectare i variabile de optimizare ..................................................... 58

8 Restriciile de proiectare i funcia obiectiv ............................................................. 62

8.1 Funcii-obiectiv globale .................................................................................. 63

8.2 Metode de transformare i pseudo-obiective ..................................................... 65

9 Modelare Parametric ........................................................................................... 68

9.1 Modelarea datelor n Grasshopper ................................................................... 70

1

9.1.1 Formularea obiectual n procesul de calcul ............................................... 72

9.1.2 Crearea funciei fitness ............................................................................ 76

10 Implementarea strategiilor de optimizare structural cu algoritmi genetici ............... 83

10.1 Programul elaborat n platforma Matlab ........................................................... 83

10.1.1 Probleme testate ...................................................................................... 83

10.2 Programe cu formulare parametric ................................................................. 92

10.2.1 Probleme testate ...................................................................................... 94

Concluzii i direcii de cercetare viitoare ..................................................................... 114

Bibliografie .............................................................................................................. 117

ANEXA 1 ................................................................................................................ 125

ANEXA 2 ................................................................................................................ 126

1 INTRODUCERE

1.1 MOTIVAIA ALEGERII TEMEI

Motivaia acestei lucrri a fost dat de observaia prevalenei studiilor de analiz i unei

insuficiente atenii acordate dezvoltrii proiectrii capabile s foloseasc eficient noile metode

dezvoltate de designul conceptual i optimizare. n domeniul mecanicii structurilor este

posibil analiza unei structuri aflate sub aciunea unei solicitri date, pentru a se obine valorile

exacte ale tensiunilor, deformaiilor i frecvenelor naturale. Nu este ns evident cum structura

poate fi configurat geometric i proporionat pentru a ne asigura c ea este cea mai eficient

n satisfacerea cerinelor de rezisten, serviceabilitate, estetic, etc, impuse.

Economia de cost, de for de munc, aplicarea de metode noi, simplificate, utilizarea de

materiale inovative i tehnologii ecologice, forme i design remarcabile; toate acestea sunt

trsturi fundamentale ale optimizrii structurale. Noile tendine i cercetarea n acest domeniu

au fost conduse, n ultimele decenii, de aplicarea cunotinelor i observaiilor obinute din

studiul proceselor naturale, a organismelor, a structurilor i materialelor, de la nivelul

particulelor subatomice la comportamentul insectelor i animalelor, a anatomiei, a relaiilor

ecologice din habitate naturale, i apoi aplicarea acestor cunotine la designul structurilor i

mediului construit. Rezultatele sunt extrase din analiza atent i sistematic a modurilor n care

natura a proiectat structuri. Pe aceast baz putem dezvolta criterii i strategii pentru a evolua

construciile ntr-o manier asemntoare, n mod eficient i sustenabil, gsind resurse noi, i

rspunznd la mediul dinamic n care structurile sunt plasate.

O structur uoar necesit mai puin material pentru construcie i astfel reuete s asigure

utilizarea maxim, raional a resurselor. Utiliznd geometrii optimale pentru structuri este

asigurat rezistena superioar a acestora i n acelai timp sunt reduse consumurile i pierderile.

n natur ntlnim nenumrate exemple de optimizare. Structura fagurelui este un exemplu de

aranjare compact eficient. n cazul metalelor i aliajelor, atomii iau poziiile care necesit

consumul minim de energie posibil prin formarea de celule unitare care definesc structura

cristalin a materialului. Pentru stlpi, optimizarea nu este o tendin nou. Tehnicile de

optimizare sunt n prezent utilizate n majoritatea domeniilor industriale, cum sunt: industria

aeronautic, industria constructoare de automobile, industria electric, industria chimic, etc.

1

Cteva exemple de aplicaii industriale diversificate ale tehnicii de optimizare sunt enumerate

mai jos:

1. greutate, vibraii, zgomot i optimizarea consumului de combustibil la automobile, reducerea

costurilor de fabricaie, precum i mbuntirea calitii;

2. proiectarea aeronavelor i a structurilor aerospaiale de greutatea minim;

3. proiectarea de structuri, cum ar fi poduri, turnuri, baraje pentru un cost minim;

4. proiectarea optim a diferitelor componente mecanice cum ar fi legturi, came, maini-unelte,

etc;

5. proiectarea optim a reelelor electrice;

6. optimizarea produciei, a planificrii, i a controlului, etc.

Cnd optimizarea topologic este realizat fr a ine cont de restricii de fabricaie, structuri

foarte atractive sunt adesea produse, ns acestea nu pot fi realizate prea uor. Figura 1.2 este

un astfel de exemplu, unde peste un milion de variabile de proiectare au fost utilizate. Aceast

structur a fost optimizat pentru a minimiza energia de deformare sub ncrcri. Este de

remarcat faptul c optimizarea topologic produce rareori designul final, chiar dac sunt

utilizate restricii de fabricaie. Acest lucru se datoreaz faptului c optimizarea topologic, n

mod normal, nu include restricii de tensiuni. Cu toate acestea, ajut la identificarea cilor de

descrcare a forelor aplicate i ofer un punct foarte bun de plecare pentru optimizarea formei

i optimizarea dimensional.

Figura 1.2 Exemplu de optimizare topologic a unei grinzi.

Figura 1.1 Aceasta este o fotografie aerian a unui ru care curge printr-un deert, n Baja California, Mexic. Se poate observa similaritatea dintre acesta i ramurile copacilor. Acest tip de ramificare se regsete n numeroase locuri diferite din natur, vasele de snge fiind un alt exemplu unde se observ modelul de ramificare. Tiparele n natur sunt relaii care apar att pentru forma structurii ct i a proceselor. Atunci cnd procesele naturale ntlnesc forme care funcioneaz bine, tiparele par s se imite reciproc.

2

Pornind de la aceast premiz, n lucrarea de fa, sunt realizate studii numerice care utilizeaz

forme obinute prin optimizare topologic care folosesc mai departe la cautarea unui optim

structural prim optimizare dimensional cu variabile discrete.

n general n cazul n care se pretinde ca s-a optimizat o structur, n fapt, doar cteva pri

structurale alese sunt optimizate. Proiectanii caut, pentru dimensiunea minim a seciunii

transversale, satisfacerea codului de proiectare, ncearc s gseasc numrul minim de

uruburi necesare ntr-o anumit conexiune de oel, caut aria minim necesar de oel pentru

armarea unei grinzi de beton, etc. Toate prile structurale sunt proiectate optim, dar aceasta nu

nseamn c ntreaga structur este optimizat pentru, spre exemplu, costurile materialelor,

timpul de construcie, preul forei de munc, etc. Am ncercat n aceast lucrare s testez cele

mai des utilizate tipuri de algoritmi evoluioniti i s realizez o analiz critic a modului n

care acetia pot fi aplicai ct mai eficient n domeniul optimizrii structurilor metalice.

1.2 OBIECTIVE

Obiectivul optimizrii structurale este maximizarea performanei unei structuri sau a unei

componente structurale. Aceasta este motivat de resursele limitate, impactul asupra mediului

i de concurena tehnologic, care cere structuri uoare, ieftine i de nalt performan.

Designul optim reprezint cel mai bun proiect fezabil care satisface criteriile de performan

prescrise prin norme i tipologia particular proiectului (Muller, 2002). Proiectarea optimal a

structurilor are ca scop realizarea unor construcii la preuri mici i consum mic de materiale,

respectnd cerinele de siguran, funcionalitate i exploatare (Petrina, 1982) (Poterasu, i alii,

1984) (Hristache, i alii, 1981).

n cadrul lucrrii am vizat urmtoarele obiective:

Elaborarea unui studiu privind stadiul actual al cunoaterii n domeniul optimizrii

structurale evolutive.

Prezentarea analizei cercetrilor efectuate i sistematizarea cunotinelor ntr-o form

coerent uor aplicabil n rezolvarea problemelor de optimizare cu algoritmi genetici.

Prezentarea sistematic a procesului de calcul iterativ de optimizare i analiza sub form

de funcii multi-nivel (nested), alturi de folosirea celor mai utili algoritmi evoluioniti n

domeniul structurilor.

3

Descrierea unei proceduri de realizare a analizei structurale n MATLAB, a

posibilitilor oferite de Global Optimization Toolbox i a metodelor de utilizare a algoritmilor

de optimizare n mediul de programare vizual parametric Grasshopper (McNeel Rhinoceros).

Realizarea unui program de optimizare care implementeaz un algoritm genetic simplu

n MATLAB.

Realizarea unui program de optimizare care implementeaz o strategie multi-nivel prin

utilizarea a trei tipuri de algoritmi ntr-un program capabil de parametrizare a structurilor

(Rhino Grasshopper). Etapa de evaluare a indivizilor s-a realizat printr-o modelare numeric,

folosind funcii fitness dar am prezentat i posibilitatea alegerii unor soluii bune, chiar dac

nu optime global, pe criterii estetice, utilizatorul avnd astfel ultimul cuvnt de spus n alegerea

soluiei finale.

4

1.3 STRUCTURA LUCRRII

Capitolul 1 Introducere Primul capitol const n prezentarea motivaiei alegerii temei, a

obiectivelor i a structurii lucrrii de fa.

Capitolul 2 Optimizare global vs. optimizare structural Am introdus acest capitol

pentru a sublinia, de la nceput, legtura dintre optimizarea global i optimizarea structural,

pentru a putea pregti terenul descrierii diferitelor metode de optimizare global ce pot fi

aplicate, n diferite faze ale proiectrii, n domeniul ingineriei structurale.

Capitolul 3 Formularea matematic a problemelor de optim n acest capitol am realizat

o introducere n optimizarea structural. Se arat c, prin descompunerea problemelor n trei

componente, i anume, model structural, model de optimizare i algoritm de optimizare,

dificultatea rezolvrii acestora poate fi redus considerabil. Am discutat modul n care sunt

generate coordonatele punctelor ce reprezint soluiile candidat n spaiul de proiectare i cum

se poate determina apartenena acestora la subspaiul admisibil prin formularea de restricii.

Am prezentat formularea matematic direct i variaional a problemelor de optim i am trecut

n revist metodele tradiionale de optimizare dup cum urmeaz: metode unidirecionale,

metode bazate pe gradientul funciei, metode de programare liniar, metoda de penalizare,

metode de liniarizare i metode de programare geometric i stocastic.

Capitolul 4 Forme de optimizare structural Acest capitol prezint formele optimizrii

structurale cel mai des ntlnite n literatura de specialitate, caracteristicile fiecrei formulri

i tipul de structuri la care se preteaz fiecare. Pentru fiecare form de optimizare (topologic,

a formei, dimensional, topografic i diferite combinaii ntre acestea) sunt menionai i cei

mai des utilizai algoritmi de cutare a soluiilor optime.

Capitolul 5 Algoritmii stocastici Capitolul cuprinde documentaia sintetizat, i o analiz

critic a celor mai frecvent utilizate metode evolutive de optimizare. Sunt descrii algoritmii

genetici (GA), optimizarea cu colonie de furnici (ant colony optimization), clirea simulat

(simulated annealing SA), cutarea tabu (tabu search), optimizare cu roiuri de particule

(particle swarm optimization PSO), harmony search i metode hibride. Accentul este pus pe

GA, ESO i SA, acetia fiind algoritmii utilizai n lucrarea de fa pentru propunerea

hibridizrii ntre o metod de optimizare bazat pe tehnici de descompunere a obiectivelor i

un algoritm de adaptare a parametrilor.

5

Capitolul 6 Strategii de optimizare Este dat o definiie a strategiilor de optimizare i

sunt descrise direciile identificate de autoare n care domeniul optimizrii structurale

evoluioniste poate fi extins i dezvoltat - design structural specializat, mbuntiri aduse

algoritmilor i formularea obiectivelor optimizrii. Sunt prezentate dificultile ntlnite n

cazul aplicrii algoritmilor evoluioniti la rezolvarea problemelor de optimizare multi-

modal, este discutat eficiena i necesitatea unei precizii sporite a analizei structurale n

condiiile n care, cel puin n faza conceptual a designului, exist multiple incertitudini

legate de variabilele structurii i mai apoi sunt prezentate exemple de utilizare a inspiraiei

formelor naturale pentru designul unor construcii structural superioare i eficiente

(argumentul pro bio-mimetism)..

Capitolul 7 Variabile de proiectare i variabile de optimizare n acest capitol am dorit s

subliniez importana deosebit pe care o au cele dou categorii de variabile n cadrul

procesului de optimizare structural. ntr-o etap timpurie a procesului de proiectare

(conceptual i faza de definire a proiectului), este de o mare importan gsirea celei mai

bune topologii structurale posibile, n contextul obiectivelor de proiectare i a restriciilor.

Identificarea parametrilor structurali eseniali i apoi a criteriilor de alegere a formei structurii

depind de condiiile care trebuie satisfcute de structur i au o importan decisiv asupra

rezultatului optimizrii. Merit menionat aici faptul c criterii absolute de optimizare nu

exist i nici nu par a fi de dorit. Dup alegerea acestor variabile de proiectare si a unui

algoritm de optimizare, deoarece majoritatea algoritmilor au un set de parametri care le

controleaz comportarea, aceast alegere devine i mai dificil. Alegerile referitoare la

valorile acestor parametrii pot avea un impact major asupra performanei algoritmului.

Capitolul 8 Restriciile de proiectare i funcia obiectiv Capitolul continu descrierea unor

alte componente eseniale ale unei strategii de optimizare structurale eficiente traducerea

restriciilor de proiectare i a formulrii funciei obiectiv ntr-un hiperspaiu de cutare pe

care algoritmul de optimizare s l poate explora. Aici am discutat posibilitatea transformrii

formulrii problemei de optimizare cu restricii ntr-o problem fr restricii prin

ncorporarea acestora n funcia obiectiv, prin diverse metode.

Capitolul 9 Modelare Parametric Capitolul cuprinde descrierea modului n care

modelarea parametrica poate oferi o soluie, n contextul descris, la problema numrului mare

de variabile necesare descrierii unei structuri. Modelele parametrice sunt capabile sa descrie

geometrii complexe utiliznd un numr relativ redus de variabile, lsnd totodat loc pentru o

6

marj mare de variaie. Aceste soluii care pot fi explorate cu ajutorul modelrii parametrice

pot fi ns n numr foarte mare, iar problema devine gsirea n rndul acestora a celor mai

bune din punct de vedere al performanelor dorite. Pentru acest tip de cutare, algoritmii

genetici sunt foarte potrivii, datorit capacitii modelului parametric de a utiliza un numr

relativ mic de variabile. Pornind de la aceast premiz, este descris modul n care autoarea a

realizat formularea parametric a problemelor de optimizare i diferenele cele mai

fundamentale rezultate din aceast formulare a problemei n Grasshopper fa de un mediu de

programare tradiional cum este Matlab. Sunt discutate toate cele trei componente ale strategiei

de optimizare modelarea variabilelor (parametric), definirea problemei de optimizare prin

crearea unei funcii fitness specifice problemei i alegerea i implementarea algoritmului de

optimizare.

Capitolul 10 Implementarea strategiilor de optimizare structural cu algoritmi genetici

Este descris programul elaborat n platforma Matlab, modul n care au fost alese variabilele

de optimizare i restriciile incluse n funcia fitness prin metoda penalizrilor. Este ales un

algoritm genetic simplu pentru cutarea soluiilor iar parametrii algoritmului sunt fici,

stabilii nainte de nceperea optimizrii. Se observ convergena algoritmului i sunt obinute

rezultate comparabile cu cele din literatur pentru problemele cu 8, 9 i respectiv 120 de

variabile, constnd n dimensiunile secionale ale elementelor.

Am trecut apoi la prezentarea formulrii parametrice n Grasshopper. Structura a fost

analizat cu ajutorul unor componente din Karamba, o bibliotec FEM ncorporat n mediul

parametric al Grasshopper. Acest fapt face uoar combinarea modelelor parametrice,

calculului cu element finit i a algoritmilor de optimizare, comunicarea ntre aceste

componente i biblioteci fiind fcut prin programare vizual (descris n capitolul 9). Se

propune hibridizarea ntre o metod de optimizare bazat pe tehnici de descompunere a

obiectivelor i un algoritm de adaptare a parametrilor. Includerea n funcia fitness a unor

valori care lucreaz una mpotriva celeilalte nu trebuie neaprat s constituie o problem

insurmontabil. Cheia este atribuirea unor greuti n funcie de importan, care s poat

ghida algoritmul spre soluiile preferate de proiectant. Noua abordare este validat pe

probleme de test i apoi aplicat la structuri mai complexe. Rezultatele sunt comparate cu

cele obinute de algoritmi din literatur. Rezultatele au fost obinute prin utilizarea SA (clirii

simulate) pentru gsirea unei soluii suficient de bune, care mai apoi este preluat ca punct de

plecare pentru GA.

7

Capitolul 11 prezint concluziile care ncheie aceast tez i ofer cteva direcii de cercetare viitoare.

8

2 OPTIMIZARE GLOBAL VS. OPTIMIZARE STRUCTURAL

Optimizarea structural implic determinarea variabilelor de proiectare, care controleaz forma,

proprietile materialului sau dimensiunile unei structuri, astfel nct s respecte anumite

restricii i s mbunteasc anumite proprieti pentru a obine structuri optime (Valery,

1999).

Atunci cnd ne ocupm de probleme de inginerie, se pot discuta dou domenii diferite de

optimizare:

- Primul este numit optimizare global (Global optimization). Prin acest termen se va nelege

optimizarea uneia sau mai multor funcii, fr o cunoatere a-priori a problemei exprimate prin

aceste funcii (numite uneori funcii "black-box").

- Al doilea domeniu, numit optimizare structural, poate fi descris ca o tiin aplicat, unde

metodele din domeniul optimizrii globale sunt aplicate la un model al unei structuri sau al

unui material.

n procesul proiectrii structurilor, n diverse domenii inginereti, proiectanii aleg cea mai

bun variant decizional, la fiecare pas, legat de aspecte structurale i non-structurale, cum

ar fi rigiditatea, rezistena, serviceabilitatea, proprietile estetice. Cu alte cuvinte, acetia iau

decizii pentru a realiza cel mai bun design, astfel nct procesul proiectrii structurale poate fi

privit ca design optimal chiar dac nu urmrete expres gsirea unui optim. Optimizarea

structural este privit ca aplicarea metodelor de optimizare n proiectarea structural.

Problema tipic de optimizare structural este formulat ca minimizarea unei funcii obiectiv

(funcii de cost), de obicei reprezentnd greutatea structurii sau volumul acesteia. Lund n

considerare modul n care se poate rezolva aceast problem de optimizare general, o abordare

ar fi alegerea unor multiple combinaii de variabile de proiectare i apelarea la un program de

analiz pentru a evalua fiecare dintre acestea, spre a alege una cu cele mai bune valori ale

funciei obiectiv i care, de asemenea, ndeplinete toate restriciile. Aceasta ar fi o abordare

clasic de cutare aleatorie sau versiunea modern cunoscut sub numele de cutare genetic

(Hajela, 1990).

O alt abordare ar fi perturbarea fiecrei variabile de proiectare i evaluarea funciei obiectiv

i a restriciilor. Astfel se poate determina sensibilitatea (gradientul) designului n raport cu

variabilele. Cu ajutorul acestor informaii, putem matematic (numeric) determina modul n care

9

se pot modifica variabilele de proiectare spre a mbunti modelul n timp ce obiectivul

satisface restriciile. Exist o multitudine de astfel de metode "pe baz de gradient" i un numr

considerabil de software-uri disponibile n prezent (Vanderplaats, 2004).

Proprietile mecanice, ce includ deplasrile de noduri, tensiunile n elemente, frecvene de

vibraie, ncrcri de flambaj sunt luate drept variabile de proiectare. Problema de optimizare

structural poate fi formulat, ca alternativ, pentru a urmri maximizarea unei proprieti

mecanice, supus unor restricii de cost. Dei exist multiple formulri ale problemei de

optimizare, ex. design pentru greutate minim, design pentru rigiditate maxim, termenul de

optimizare structural sau design optimal se refer la toate tipurile de probleme de optimizare

asociate designului structural.

Designul1 optim se realizeaz n mai multe faze consecutive:

Proiectarea conceptual este faza n care are loc identificarea configuraiei de baz a

sistemului structural mpreun cu ansamblul obiectivelor. Este important, de asemenea, s se

identifice domeniile de variaie ale valorilor parametrilor ce descriu sistemul, astfel nct pentru

orice parametru cu valori din domeniul corespunztor, sistemul s satisfac funciile

identificate n pasul precedent. Prin urmare, se identific mulimea parametrilor ce descriu

diverse sisteme admisibile.

Proiectarea optim are ca obiectiv alegerea parametrilor rmai nedeterminai n pasul

precedent. Aceti parametri trebuie s aib valori n domeniile definite de restriciile tehnolo-

gice i de funciile sistemului. Criteriul pentru alegerea parametrilor sistemului este, de cele

mai multe ori, minimizarea costului, a greutii, a consumului anumitor materiale, maximizarea

eficienei etc.

Mai trebuie specificat faptul c proiectarea unui sistem structural este un proces caracterizat de

proprietatea c parcurgerea etapelor sale poate declana contrareacii (feedback). Asta

nseamn c dup parcurgerea unei etape este posibil s nu se treac la etapa urmtoare, ci s

se reia procesul de proiectare de la o anumit etap anterioar, sau chiar de la nceput, de attea

ori pn cnd sunt ndeplinite anumite restricii, impuse n etapa curent. Acest proces iterativ

de proiectare se oprete doar atunci cnd se consider c structura simulat poate fi aplicat n

1 Design este folosit in sensul complet din limba englez (plan, proiect, design (i industrial), desen, schi, schem, proiectare, construcie, sintez, concepie, tip, model, calcul; (TH) a proiecta, a executa un proiect / un plan, a desena, a calcula.

10

realitate. Se subliniaz c aceast ultim decizie este mai mult de natur uman dect de

programare matematic.

Condiii necesare pentru implementarea designului optimal al structurilor:

1. Existena unei funcii pentru proiectarea optim a elementelor structurale specifice, cum

ar fi grinzi de oel, grinzi de beton, prinderile din oel, blocuri de fundaie, etc. De obicei,

dimensiunile minime, mrimea sau numrul elementelor sunt valorile cutate.

Elementul trebuie s ndeplineasc criteriile corespunztoare codurilor de proiectare.

2. Trebuie s existe posibilitatea parametrizrii structurii. Proiectantul trebuie s decid,

ceea ce este fixat ca dimensiune n structur i ceea ce poate fi schimbat - deschideri,

adncimi, dimensiuni ale seciunilor transversale, grosimi de plci i perei, sarcini, etc.

Fiecare trstur care poate varia trebuie s poat fi descris de un parametru

independent. Alte dimensiuni pot fi dependente de parametri, crend un model

structural inteligent parametrizat.

3. Trebuie s fie posibil definirea funciei obiectiv. Ea poate fi: greutatea oelului

structural necesar, volumul de beton utilizat, greutatea armturii, dar poate fi, de

asemenea, deplasarea maxim sau oricare alt caracteristic structural sau estetic.

Situaia ideal este dac sistemul este capabil s calculeze o valoare global precum

costul total al construciei.

4. Trebuie s existe capacitatea evalurii funciei obiectiv pentru setul specific de

parametri. Aceasta nseamn c o funcie capabil s interpreteze setul de parametri i

s returneze o valoare obiectiv trebuie s fie disponibil.

5. Rezolvatorul optimizrii - un instrument care genereaz diferite seturi de parametri,

calculeaz funcia obiectiv i propune n cele din urm setul optim de parametri trebuie

s fie creat.

Metoda elementului finit poate fi folosit ca nucleu numeric pentru rezolvarea general a

problemelor de calcul pentru cele mai diverse tipuri de structuri i solicitri. Exist o

multitudine de programe de calcul care folosesc MEF, acestea furniznd toate datele necesare

pentru a fi procesate n algoritmul de optimizare. Pentru a lucra n regim integrat este necesar

folosirea unor automatisme software pentru definirea problemei i rezolvarea ei automat

folosind MEF. De asemenea, este necesar ca programul s poat prelua automat datele din

programul de element finit i s le foloseasc mai departe. Formularea problemei de optimizare

ar trebui fcut automat. ntruct rezolvarea problemelor folosind MEF este un proces costisitor

11

din punct de vedere al calculului, este necesar s se minimizeze numrul de rulri ale modelului

folosind MEF. Pentru a evita deteriorarea modelului structural modelat n urma ajustrii

geometriei sau topologiei n procesul de optimizare, este necesar definirea unui set de restricii

suplimentare fa de restriciile ce in de configuraia structurii (tensiuni, eforturi, deplasri).

Pentru o bun poziionare a procesului de cutare n spaiul soluiilor este foarte util analiza

senzitivitii. Folosind analiza senzitivitii, spaiul de cutare este redus la ablonul sugerat de

coeficienii de senzitivitate.

12

3 FORMULAREA MATEMATIC A PROBLEMELOR DE OPTIM

Problemele de optimizare pot fi rezolvate prin aplicarea "conceptului de trei coloane" (Three-

Columns Concept). Cele trei coloane sunt modelul structural, modelul de optimizare i

algoritmul de optimizare. Optimizarea automat a structurilor este o sarcin complex i

dificil de organizat. Conceptul prezentat a fost dezvoltat de Eschenauer [Eschenauer,2007].

Acesta pornete de la ideea descompunerii problemei n subprobleme care pot fi rezolvate

direct, iar conceptul a fost dezvoltat pentru a lucra cu algoritmi de programare matematic (dar

este valid i n cazul tehnicilor de soluionare de tipul algoritmilor genetici).

Modelul structural, necesar pentru traducerea structurii reale n vederea realizrii procesului

de optimizare computerizat, descrie matematic sau numeric comportamentul fizic al structurii,

adic rspunsul la ncrcri, sau proprieti structurale cum sunt frecvene proprii de vibraie

sau greutate. n cazul n care structura este modelat prin FEM variabilele de stare ale

problemei sunt deplasrile nodale (u). Alte valori care ne pot interesa, cum ar fi tensiunile, sunt

calculate din valorile deplasrilor n etapa de postprocesare.

Problemele de optimizare reale sunt n general neliniare i cu restricii, iar algoritmii care le

pot rezolva se bazeaz pe proceduri iterative care pornesc de la un design iniial (x0 ) i produc

vectori de variabile de design mbuntii (xk ). Procedura este oprit cnd un anumit criteriu

de convergen predefinit este satisfcut. Numeroase studii au artat c alegerea celui mai bun

algoritm de optimizare se face n strns legtur cu problema tratat.

Modelul de optimizare face legtura intre modelul structural i algoritmul de optimizare.

Modelul de evaluare are rolul de a evalua designul n funcie de obiectivul de optimizare i de

starea restriciilor (active sau nu) din valorile variabilelor de stare i alte informaii obinute din

modelul structural.

Obiectivul optimizrii este adesea formulat ca o funcie obiectiv scalar f, sau, n cazul

optimizrii multicriteriale, ca un vector f.

Restriciile designului sunt formulate sub form de funcii de restricie incluse n vectorii g

(inegaliti) i h (restricii de tip egalitate). Modelul de evaluare se poate baza pe variabilele de

stare u (cnd sunt luate n considerare tensiunile) sau alte variabile care influeneaz designul

(necesare calculrii greutii totale, de exemplu). Modelul de optimizare mai conine definiiile

13

variabilelor i transformrile acestora sub denumirea de parametrizare. Poziiile nodurilor

aflate la grania domeniului modelului structural definesc forma acestuia i se modific n

timpul unui proces de optimizare a formei. Forma unei structuri sau a unui design este definit

explicit n termeni de variabilele de design x. Modelul de design descrie relaia matematic

dintre variabilele de analiz y i variabilele de design x.

Adiional, acestea din urm pot fi transpuse n variabile de transformare z n scopul adaptrii

problemei de optimizare la unele cerine ale algoritmului de optimizare. Analiza senzitivitaii

demonstreaz susceptibilitatea obiectivului i restriciilor fa de mici schimbri ale

variabilelor de design. Aceast informaie e folosit la controlul algoritmului de optimizare i

la alegerea unui design.

Evaluarea designului. n optimizarea structurilor este folosit, n general, MEF pentru

obinerea rspunsului structural la ncrcri sub anumite condiii limit. Soluia sistemului de

ecuaii ofer soluia primar n termeni de grade de libertate nodale (n cazul structurilor acestea

se traduc prin deplasri), iar din acestea, alte valori pot fi obinute (tensiuni). Valorile

tensiunilor pot fi utilizate pentru a formula un obiectiv cnd se dorete maximizarea rezistenei

unui element, sau la formularea restriciilor cnd dorim minimizarea greutii unei structuri i

asigurarea rezistenei necesare acesteia. n cazul general, rspunsul structural e necesar att

pentru evaluarea obiectivului ct i a restriciilor.

3.1 EVALUAREA MODELULUI

3.1.1 Spaiul i subspaiul de proiectare

Prin convenie, se consider structura ca fiind un punct ntr-un spaiu de proiectare abstract. n

acest spaiu, coordonatele punctului corespunztor structurii sunt dimensiunile geometrice ale

acesteia i constantele de material. Aceste coordonate care vor fi denumite parametrii structurii,

pot fi numere reale, funcii sau vectori (mulimi total ordonate de numere reale). Pentru o n-

elegere mai profund a spaiului figurativ de proiectare, se prezint, mai jos, parametrii ce sunt

utilizai de proiectant pentru a specifica o structur.

Parametri geometrici:

geometria seciunii transversale a elementelor structurale unidimensionale;

forma axei longitudinale a elementelor structurale unidimensionale;

forma geometric a suprafeei mediane a plcii sau membranei;

14

legea de variaie a grosimii plcii;

forma conturului plcii sau membranei;

poziia spaial a nodurilor unei grinzi cu zbrele sau ale unui cadru;

localizarea spaial a elementelor componente ale structurii.

Constante de material:

modulul de elasticitate;

densitatea;

coeficientul de conductivitate i de dilatare termic;

coeficienii legilor constitutive care stabilesc legtura dintre tensiuni i deformaiile

elastice, elasto-plastice, vsco-elastice, etc.;

tensiunile de cedare ale materialului la diverse solicitri;

constantele de oboseal ale materialului;

constantele de anizotropie ale materialului.

Starea de pretensionare a unei structuri poate, de asemenea, fi considerat ca un parametru de

calcul. Evident, aceast trecere n revist a parametrilor structurii nu este complet, ns include

parametrii cei mai frecvent utilizai n proiectare.

O problem particular generat de optimizarea structurii este aa-numitul subspaiu de pro-

iectare.

n situaia concret n care se dorete proiectarea unei grinzi, pentru nceput, proiectantul decide

dinainte dac grinda va fi o grind cu seciune I, sau grind cu zbrele. Aceast alegere implic

restricii asupra parametrilor de proiectare ca, de exemplu, nlimea maxim a grinzii I. De

asemenea, dei nu este strict necesar, proiectantul i alege dinainte materialul folosit,

adugndu-se astfel noi restricii.

Constantele materialului pot fi introduse printre variabilele de proiectare ce vor fi determinate

n procesul de optimizare, ns trebuie subliniat c puini autori au abordat acest aspect,

existnd puine lucrri care abordeaz aceste probleme.

3.1.2 Subspaiul admisibil

Subspaiul de proiectare ce conine structura satisface un numr de cerine, necesar pentru

acceptabilitatea funcional a structurii, aflat sub aciunea solicitrilor ce decurg din

15

ndeplinirea rolului funcional. n general, condiiile impuse asupra rezistenei, rigiditii,

duratei de via, .a. limiteaz rspunsul structurii la solicitarea dat.

Aceste condiii pot fi, ns, concepute ca restricii ce mpart subspaiul de proiectare ntr-un

subspaiu admisibil i un subspaiu neadmisibil.

Printre restriciile cele mai frecvent ntlnite n literatur, menionez:

tensiuni maxime;

deformaie maxim;

coeficient de siguran maxim la pierderea stabilitii, sau la rupere;

minimum de senzitivitate la imperfeciuni de execuie, de montaj, etc.;

minimumul frecvenei fundamentale de oscilaie proprie;

maximul vitezei de deformare n curgerea plastic staionar;

maximul duratei de via sub solicitri ciclice;

greutate sau volum minim;

rigiditate maxim la diverse solicitri (ncovoiere, torsiune etc.);

moment de inerie maxim;

solicitri de stabilitate maxim;

ductilitate maxim la solicitri dinamice.

Am constatat c diferite teorii de rupere sunt luate n consideraie, n concordan i pe baza

unor indicatori de material, solicitare, etc., prin restricii adecvate din subspaiul de proiectare.

Restriciile sunt exprimate ca limite de funcii definite pe subspaiul de proiectare, acest

subspaiu fiind delimitat numai implicit. Am observat c dificulti de calcul apar atunci cnd

solicitrile sunt aleatoare sau dinamice, n cazul unor tipuri de solicitri diferite, restriciile

fiind diferite pentru fiecare dintre acestea. Acesta este, n mod obinuit, cazul cnd se consider

diferite suprasarcini, n condiii de exploatare.

Cel mai adesea, restriciile asupra limitelor rspunsului nu sunt de natur fizic ci rezult din

reglementri sau standarde. Cnd este cazul, o problem de proiectare optim este cea a

senzitivitii soluiei optime la mici modificri n aceste standarde. Privind lucrurile i prin

prisma acestui ultim aspect menionat, se pune i problema optimizrii standardelor sau a

reglementrilor.

n formularea matematic a problemei, restriciile apar n mod obinuit sub form de inegaliti.

16

Drept restricii se pot considera: ecuaiile de echilibru i de compatibilitate, (ecuaii difereniale

cu derivate pariale sau ecuaii difereniale ordinare), inegaliti algebrice de tip unilateral sau

bilateral (suprafee, dimensiuni, momente de inerie etc), tensiuni normale, tangeniale,

principale, echivalente, critice la stabilitate elastic, n regim static sau dinamic, deformaii

locale sau generale, viteza critic de deformare plastic etc., sau de tip izoparametric cum ar fi:

volum constant, deformare constant, potenial elastic constant etc.

Dup ce variabilele de proiectare au fost alese, problema de proiectare optim poate fi

formulat astfel:

S se gseasc S astfel nct:

( 3-1)

unde S este un punct n spaiul de proiectare, caracterizat de variabilele alese. n multe

probleme exist condiiile impuse funcionalelor k

f i jh , datorit restriciilor impuse rspun-

sului structurii la solicitri, ns unele dintre acestea pot s fie exprimate prin delimitri ale

subspaiului de proiectare. Funcia obiectiv este notat cu F .

Existena soluiei i a unicitii acesteia, cnd exist, pentru problema definit, la modul general,

prin (3-1), este o chestiune deschis la care numai n rare cazuri se poate rspunde pe baza

intuiiei. Din (3-1) rezult c, dac S este optim, pentru mici variaii S n domeniul subspa-

iului de proiectare, exist relaiile:

0F(S)

0(S)a care hindici j l, pt. 0(S)h

,...,m2,1, k0(S)f

jj

k

( 3-2)

Aceast formulare variaional d condiia necesar pentru existena unei soluii optime.

Condiiile din formularea variaional (3-2) pot fi exprimate printr-o alt form mult mai

folosit: Se presupune c variabilele de proiectare sunt p numere reale, astfel nct spaiul de

proiectare poate fi interpretat ca un spaiu euclidian p -dimensional.

Fie S o soluie admisibil i S o variaie arbitrar n domeniul subspaiului de proiectare.

Cum 0)S(fk

, variaia S este normal la toi vectorii )S(fk

( m,...,2,1k ). n mod similar,

F(S)

,...,n,, j(S)h

,...,m,, k(S)f

j

k

min

210

210

17

restriciile descrise prin inegalitile 0)S(hj

sugereaz c S nu are component n direcia

pozitiv a lui )S(hj

.

Prin urmare, se poate deduce c pentru orice numere reale k

i orice 0j , proiecia lui S

pe vectorul

n

1j

jj

*m

1k

kk)S(h)S(f

( 3-3)

este negativ. n relaia (3-3), simbolul

n

1j

* indic faptul c nsumarea este restricionat la

acele valori ale indicelui j valorile lui j pentru care 0)S(hj

. Cu alte cuvinte, orice vector

care are o component pozitiv pe direcia vectorului dat de relaia (3-3) se gsete n subspaiul

neadmisibil.

n scopul descreterii funciei obiectiv F , este necesar s se produc o micare din sens pozitiv

n sensul negativ al direciei F .

Dac aceast direcie (- F ) este direcia vectorului dat de relaia (3-3), o deplasare n

subspaiul admisibil va descrete funcia obiectiv. Prin urmare, la punctul de optim, - F are

direcia identic cu direcia vectorului (3-3). Utiliznd acest fapt, se deduce c dac S este

soluie optimal, atunci exist o mulime de numere reale k

i de numere pozitive 0j ,

astfel, nct are loc ecuaia:

n

1j

jj

*m

1k

kk)S(h)S(f)S(

( 3-4)

Relaia (3-4) este cunoscut sub numele de condiia Kuhn-Tucker. Se observ c, dac nu exist

restriciile inegaliti, k

poate fi interpretat ca multiplicator Lagrange.

Pentru o problem fr restricii, condiia (3-4) se reduce la 0 . Ca toate soluiile

staionare, ns, condiiile (3-2) i (3-4) nu pot asigura optimul global.

Utilizarea unor teste adiionale asigur ns optimul global. n particular, dac spaiul de

proiectare admisibil este convex i dac funcia obiectiv este fie convex, fie concav, atunci

unele teoreme ale programrii neliniare pot da informaii importante despre optimul global

i/sau poziiile soluiilor posibile.

18

Pot exista probleme care din punct de vedere matematic sunt total diferite de cea formulat prin

relaiile (3-1), dar care exprim acelai model fizic. n acest context, de exemplu, problema

determinrii celui mai nalt stlp posibil, de material i volum dat (considernd i flambajul sub

greutatea proprie), este, din punct de vedere principial, identic cu problema determinrii

volumului minim al stlpului, de material i nlime date. Dei problemele sunt, n fond,

identice, formularea lor cu ajutorul relaiilor (3-1) este diferit. Acest lucru prezint un interes

deosebit, deoarece, inevitabil, una din formulri conduce la o soluie mai uor de obinut.

Pentru unele modele speciale de structuri (ca de exemplu o grind elastic pentru care rigidi-

tatea la ncovoiere este proporional cu masa), cu una sau mai multe restricii ce sunt

caracterizate prin principiile de extrem ale teoriei structurilor (principiul lui Rayleigh i

principiul minimului energiei poteniale), condiiile necesare obinute prin metode variaionale

pot fi suplimentate cu condiii suficiente. Depinznd de principiul de minim al structurii cu

caracter global sau local, condiia rezultat este, de asemenea, suficient pentru un optim global

sau local.

Faptul c formularea direct, dat de relaia (3-1) i formularea variaional, dat de relaia (3-

2) a problemei de proiectare optim sunt esenial diferite, afecteaz alegerea metodelor folosite

la rezolvarea problemei.

Din punct de vedere principal, problemele formulate prin relaia (3-1) sunt rezolvate, prin

utilizarea unor procedee iterative n care, la fiecare iteraie se obine o soluie mai bun dect

cea obinut la iteraia anterioar.

Problemele formulate variaional conduc, pe de alt parte, la sisteme de ecuaii difereniale cu

condiii pe contur. Numai n cazuri cu totul excepionale (de regul, cnd problema prezint

suficiente simetrii), o soluie este dat sub form analitic cunoscut. De regul, se aplic

algoritmi pentru obinerea de soluii numerice.

Datorit faptului c ecuaiile difereniale sunt adesea neliniare i nu au soluii regulate (adesea

apar singulariti pe contur), aceste probleme prezint un grad sporit de dificultate.

n consecin, exist o diferen important ntre formularea variaional (3-2) i formularea

mai general (3-1). Formularea variaional poate da o soluie (presupunnd c ea exist)

optimal (sau mai curnd, staionar), funciile (3-1) fiind aplicate la orice proiectare

admisibil. Aceast diferen devine pregnant atunci cnd soluia este singular sau nu exist.

19

n sens larg, aceasta nseamn c o soluie bazat pe formularea (3-1) poate conduce la o

proiectare mai bun, chiar dac nu la cea mai bun.

Procedeele iterative menionate mai sus sunt metodele programrii matematice i cele

formulate de R.L. Fox. Trstura lor comun este generarea unui ir de puncte n subspaiul de

proiectare

,...S,...,S,Sq21

( 3-5)

ncepnd cu un punct arbitrar 1

S .

Pasulq

S din qq1q SSS este determinat folosind gradienii funciilor restricii kf , jh i

funcia obiectiv n punctul qS . Diferena ntre diferitele metode const n relaia dintre

gradieni i pasul q

S .

n cel mai simplu caz, problemele cu restricii liniare i funcie obiectiv liniar pot fi rezolvate

prin metode ale programrii liniare. Pentru restricii liniare i tipuri particulare de funcii

obiectiv neliniare exist metodele programrii ptratice.

Cazurile mult mai generale de probleme neliniare pot fi rezolvate fie cu metode directe, fie cu

metode indirecte.

3.2 METODE DE OPTIMIZARE

n procesul tipic de optimizare a structurilor finit dimensionale, proprietile secionale,

localizarea nodurilor i poziionarea elementelor structurale sunt alese ca variabile ale

problemei. Exist numeroase metode de optimizare, care pot fi clasificate n:

Metodele analitice de optimizare utilizeaz teorii matematice de calcul i metode

variaionale n studiul optimului pentru formele geometrice simple ale elementelor

structurale, cum ar fi grinzi, bare, plci. Aceste metode pot fi folosite cu succes pentru

componente structurale singulare, dar nu sunt posibil de utilizat la structuri complexe.

Cu acest tip de metode optimul este calculat foarte exact prin soluionarea unui sistem

de ecuaii i inecuaii ce exprim condiiile de optim.

Metodele numerice sunt reprezentate de metode de programare n cadrul aplicaiilor

matematice. Cele mai noi cercetri n domeniu [Murren,2011] sunt legate direct de

20

creterea aproape exponenial a capacitii de calcul a computerelor i au ca direcii de

dezvoltare:

programarea liniar;

programarea neliniar;

programarea dinamic;

proceduri neconvenionale.

Optimizarea cu aceast clas de metode se face printr-un proces iterativ, definindu-se o stare

iniial folosit ca punct de start pentru o cutare sistematic n scopul mbuntirii structurii.

Procesul iterativ este stopat cnd toate criteriile sunt satisfcute, astfel nct configuraia

curent obinut s fie ct mai aproape de optimul cutat.

Clase de metode de optimizare:

Metode directe;

Metode bazate pe optimalitatea Kuhn-Tucker;

Metode de penalizare;

Metode de punct interior de urmrire a traiectoriei centrale.

Principalele mrimi ce trebuie evaluate n cadrul metodelor de programare matematic ce

folosesc tehnici derivative sunt: Gradientul i Hessianul funciei obiectiv, coeficienii

Lagrange, Jacobianul restriciilor. Toate aceste mrimi joac un rol important n determinarea

admisibilitii soluiilor i a existenei acesteia. Punctul candidat la optim trebuie s se afle n

domeniul fezabil (gradientul restriciilor trebuie s fie liniar independente). Din studii ale

metodelor de mai sus se poate trage concluzia c optimul poate fi gsit prin rezolvarea unor

ecuaii difereniale cu o form clar precizat. Aceast observaie ne poate conduce la concluzia

parial adevrat c optimul ar putea fi gsit ntotdeauna cu ajutorul unui algoritm clar formulat.

Totui, trebuie precizat c ecuaiile ce definesc condiiile de optimalitate sunt supuse unor

condiii extrem de restrictive. Din acest motiv, o alternativ la aceste metode sunt cele de

cutare direct. Spre deosebire de metodele derivative ce presupun calculul unor mrimi

complexe, metodele de cutare directe folosesc cicluri de calcul cu un cost computaional mic.

Metodele directe de cutare permit optimizarea funciilor pentru care nu putem aplica metodele

derivative de optimizare. Metodele de cutare evalueaz funcia f n k puncte {x} urmrind

evoluia funciei n scopul gsirii punctului de optim.

21

Situaiile n care se recomand folosirea uneia dintre metodele directe de cutare sunt

urmtoarele:

funcia f nu este derivabil,

derivatele sunt foarte greu de evaluat sau sunt discontinue,

nu este necesar o soluie foarte precis a problemei.

Alegerea uneia dintre metodele prezentate se face n funcie de tipul de problem practic ce

trebuie rezolvat. O tehnic destul de des utilizat n rezolvarea problemelor simple este cea

care presupune c setul de restricii este activ n punctul de optim, caz n care acestea sunt

considerate ca egaliti, fiind utilizate pentru a elimina variabilele libere. n concluzie, numrul

de restricii active poate, n general, s fie cel mult egal cu numrul de variabile libere. n

general, n problemele mai complexe, numrul total de restricii este mai mare dect numrul

de variabile, fiind dificil de a cunoate care constante sunt active n punctul de optim.

O soluie optim x a problemei de optimizare structural este caracterizat prin proprietatea

c nu exist alte soluii fezabile ntr-o vecintate apropiat lui x, ce corespunde unei valori

minime a funciei obiectiv. Din punct de vedere matematic, acest concept se exprim prin

condiiile Kuhn-Tucker (Kuhn, Tucker, 1951):

1

( )0

mj

j

ji i

gf xu

x x

i = 1...m ( 3-6)

ujgj(x) = 0 j = 1...m

uj 0 j = 1...m

Este important de remarcat faptul c aceste condiii sunt valabile doar pentru problemele de

programare neliniare convexe.

Pentru a rezolva problema de optimizare structural au fost dezvoltate diferite tehnici, putnd

fi amintite trei abordri n modul de rezolvare.

Astfel, [Moses (1968)], i [Romstad i Wang (1978)] au construit aplicaii bazate pe metoda

Simplex de programare liniar. n lucrrile lor, aceti autori aproximeaz o problem de

programare neliniar cu o secven de probleme de programare liniar. [Gellatly i Gallagher

(1976)], i [Moses i Onoda (1979)] au utilizat metode de tip direcii posibile sau direcii

fezabile pentru a rezolva problema de optimizare structural.

22

O a treia categorie de metode de programare neliniar este bazat pe aa-numitele funcii de

penalizare. Acest tip de metod este utilizat de [Schmidt i Fox (1975)], folosind tehnici de

penalizare exterioare, n timp ce [Kavlie, Moe i Kowalik (1979)] aplic tehnici de penalizare

interioar. Ideea funciilor de penalizare const n transformarea problemei de optimizare

cu restricii, ntr-o problem fr restricii, prin adugarea la funcia obiectiv a unor termeni

suplimentari, care s nlocuiasc efectul restriciilor. Astfel o problem de minimizare fr

restricii poate fi rezolvat cu o funcie transformat, care are forma general:

1

( , ) ( ) ( ( ))m

k k i

i

P x f f x f G g x

( 3-7)

unde al doilea termen al ecuaiei este denumit termen de penalizare.

[Fiacco i McCormick (1969)] au adus o contribuie important la dezvoltarea acestei abordri

a problemei de optimizare, numind-o tehnic de minimizare secvenial fr restricii. Unul din

elementele comune pentru clasele de metode de programare neliniar amintite este faptul c

folosesc variabile continue.

n activitatea curent de proiectare, ns, multe variabile sunt limitate de valori discrete, cum

ar fi grosimile tablelor sau plcilor, diveri parametri geometrici (lungimi, diametre), .a., i n

lipsa unor metode eficiente de cuantificare a acestor mrimi discrete, este totui acceptat

formularea continu a problemelor de optimizare, a cror soluie este n final rotunjit. Acest

mod de lucru furnizeaz rezultate satisfctoare pentru problemele de optimizare de mici

dimensiuni, dar poate da soluii relativ deprtate de optim dac numrul de variabile crete

foarte mult.

O problem de optimizare cu variabile discrete este formulat asemntor cu problema

general, i anume:

S se determine minimul funciei: f (x)

cu restriciile: g j (x i ) =0 j=1,2,... m ( 3-8)

unde: inf supi i ix x x i=1,2,...n ( 3-9)

i ix D ( 3-10)

n care: f (x) este funcia obiectiv; g j (x) sunt restriciile; x i este vectorul variabilelor de

proiectare; infix i sup

ix reprezint limita superioar i inferioar a variabilelor; m este numrul

23

de restricii; D i este mulimea finit de variabile discrete.

Problema de optimizare formulat matematic prin relaiile (3-8)-(3-10) este, n general o

problem de programare neliniar, fiind studiate i folosite diverse tehnici de rezolvare.

Este important de subliniat c majoritatea algoritmilor au ca cerin o valoare iniial pentru

variabile, fiecare evaluare a funciei necesitnd de fapt o nou analiz a structurii. Din acest

motiv, dac se lucreaz cu structuri complexe, este necesar un numr mare de analize cu

elemente finite, deci un consum mare de timp i resurse, eficient numai n cazul folosirii unui

computer i a unui program rapid.

Deci pentru rezolvarea eficient a problemei ar fi necesare o aproximare de calitate a problemei,

precum i rezolvarea ntr-un numr redus de pai, existnd soluii, cum ar fi :

Reducerea numrului de variabile prin realizarea de legturi ntre acestea, abordare

rezonabil, deoarece n practic o serie de variabile au aceeai valoare (table i plci de

aceeai grosime, din motive constructive i tehnico-economice cum ar fi uurina n

aprovizionare,etc.), i reducerea restriciilor prin luarea n considerare doar a celor

critice la fiecare iteraie.

Utilizarea de funcii de aproximare pentru reprezentarea restriciilor, din punct de

vedere matematic fiind folosite serii Taylor. Aceast tehnic de rezolvare genereaz o

form de aproximare a restriciilor n funcie de variabile, bazndu-se pe constatarea c

vectorii de rspuns structural, cum ar fi tensiuni sau deplasri sunt cvasiliniari n raport

cu variabilele, dei n practic restriciile de proiectare sunt n general neliniare n raport

cu variabilele.

Utilizarea unei tehnici de generare aproximativ [Arora, 1997], la care rspunsul

structurii la ncrcarea exterioar, definit prin deplasri, frecvene, etc., devine n

problema de optimizare ca prim aproximare. n acest mod este creat o problem

explicit neliniar, a crei soluionare necesit mai puin de 10 pai.

n vederea creterii eficienei metodei este folosit o strategie dual, n care optimizarea cu

variabile discrete este realizat dup optimizarea cu variabile continue. Statistic a fost stabilit

c acest metod dual este cu cel puin un ordin de mrime mai eficient dect alte metode n

cazul problemelor de optimizare cu mai mult de 20 de variabile. Algoritmii clasici de

optimizare ofer posibilitatea optimizrii unei structuri prin urmtoarele clase de metode:

metoda Simplex, metoda direciilor fezabile sau metoda funciilor de penalizare.

24

Ca element de noutate n toate aceste metode este posibilitatea folosirii unei mulimi discrete

pentru variabilele de proiectare, lucru care reprezint o abordare pragmatic a procesului de

optimizare structural, prin posibilitatea obinerii de valori care au aplicabilitate in practic. De

asemenea, toi aceti algoritmi clasici au ca element de legtur utilizarea metodei elementului

finit ca procedur de calcul a tensiunilor i deformaiilor structurii analizate. Analiza acestor

metode, att prin prisma faptului c se folosete MEF pentru calculul deplasrilor i tensiunilor,

ct i n ceea ce privete uurina n aplicare, precum i necesitatea unei anumite accesibiliti

hardware i software, duce la concluzia c pot fi considerate dou variante de lucru n vederea

optimizrii structurale: fie utilizarea unui modul de optimizare cuplat cu un modul de analiz

structural cu MEF, fie crearea unui modul de optimizare propriu, cuplat cu un modul de

analiz structural cu MEF, care s rspund unor anumite cerine specifice.

25

4 FORME DE OPTIMIZARE STRUCTURAL

n conformitate cu Steven Grant

[Steven, 2003], patru forme diferite de

optimizare structural pot fi distinse.

Fiecare poate fi rezolvat cu o strategie

de optimizare distinct, dar rezolvarea

problemelor reale, de obicei, solicit o

combinaie a acestor forme.

4.1.1 Optimizarea topologic

Prin optimizarea topologiei nelegem

gsirea unei structuri fr a cunoate

forma sa final n prealabil [Bendse i

Sigmund, 2003].

Figura 4.1: Exemplu de design optimal pentru stlp

Doar condiiile externe, criteriile de optimalitate i restriciile sunt cunoscute. Acest tip de

probleme vin de obicei din domeniul ingineriei mecanice, unde conceperea unor piese pentru

maini sau avioane sunt temele de proiectare cele mai frecvente. Structurile reprezentative din

ingineria civil servesc drept instrument de decizie n alegerea unui sistem static adecvat al

unei structuri noi. Ele sunt aplicate mai ales la structurile articulate, n cazul n care

coordonatele nodale ale mbinrilor sunt variabilele de optimizare. Lund n considerare poziia

suporturilor i a funciilor obiectiv, sisteme istorice bine-cunoscute pot fi descoperite prin

optimizare topologic.

26

Figura 4.2: (a) Diagrama de calcul a problemei, (b) soluia optimal a problemei, (c) conguraia optimizat format prin concatenarea modulelor de baz i (d) First of Forth Bridge, construit 18831890 ca un exemplu de optimizare topologic prezentat n [Gil i Andreu, 2001].

Exemplul tipic pentru aceast form de optimizare n domeniul construciilor metalice este

plasarea elementelor din oel. Cu alte cuvinte, cutm cel mai potrivit model pentru o structur

n care poziia elementelor de oel nu este cunoscut n avans. n acest caz, obiectivul este, de

obicei, reducerea la minimum a cantitii de oel, supus cerinelor structurale. n primii ani de

optimizare numeric procedura tradiional pentru rezolvarea acestor probleme a fost

proiectarea pentru tensiune limita (fully stressed design), nsemnnd ca toate elementele

structurii sub ncrcri s fie ct mai aproape posibil de limitele materialului.

n primii ani de optimizare numeric procedura tradiional pentru rezolvarea acestor probleme

a fost design la tensiune limit (fully stressed design), astfel nct tensiunile n toate elementele

sunt menite s fie ct mai aproape posibil de limitele materialului. Dezavantajul este vizibil

pentru cazurile de ncrcare multiple sau mai multe cazuri de sprijinire. n prezent, metodele

cele mai frecvent utilizate pentru rezolvarea acestei categorii de probleme sunt criteriile de

optimalitate, abordare bazat pe teoria dualitii sau programare convex [Olhoff, 1996],

omogenizarea combinat cu metodele de programare matematic [Allaire, 2002] sau [Cherkaev,

2000], optimizare structural evolutiv (ESO) [Xie i Steven, 1997] - o alt metod bazat pe

eliminarea elementelor ineficiente din mesh-ul de elemente finite, automate celulare - o veche

metoda de simulare dinamic studiat nc din anii 1960 [von Neumann, 1966] bazat pe

construirea de sisteme bloc cu comportament predefinit [Wolfram, 2002] i, n cele din urm,

Algoritmii Evolutivi (EAs) bazai pe principiile seleciei naturale.

27

Figura 4.3: Guangzhou Opera House, Arhitect: Zaha Hadid, Structura: Shanghai Tongking (SHTK), China Sigurana fiind numrul unu ntre obiectivele noastre, dorim s reducem greutatea oelului pentru a ncerca s facem costul structurilor metalice apropiat de cel al cldirilor din beton, n condiii similare.

4.1.2 Optimizarea formei

n aceast form de optimizare, topologia structurii este cunoscut a-priori, dar poate exista o

parte i/sau un detaliu al structurii, n care, de exemplu, tensiuni mari pot produce probleme.

Prin urmare, obiectivul este, de obicei, gsirea celei mai bune forme, care va duce la distribuirea

tensiunilor ct mai eficient. Parametrii de form sunt dimensiuni ale pieselor optimizate sau un

set de variabile care descriu forma (de exemplu coeficienii de funcii spline). Din punct de

vedere matematic, dou reprezentri de variabile - continue i discrete - pot fi gsite n

domeniul optimizrii formei. Prezentarea general a primului caz poate fi gsit n [Sokolowski

i Zolesio, 1992], i al doilea caz rezumat n [Bauer i Gutkowski, 1995]. Algoritmii disponibili

pentru rezolvarea acestor probleme sunt programarea matematic [Haslinger i Neittaanmaki,

1996], din nou ESO; o nou metod n acest context, este creterea biologic simulat bazat

pe definiia de temperatur "fals", sau artificial [Mattheck i Burkhardt , 1990], i din nou

Algoritmii Evolutivi (EAs).

Denis Weare i Robert Phelan (RIBA Publishing, 2008) au calculat c modul cel mai eficient

de a mpri un spaiu n celule de volum egal minimiznd n acelai timp suprafaa specific

ntre ele a fost prin utilizarea unui aranjament suprapus compus din 75% forme cu 14 fee i

25% forme cu 12 fee. Dar din moment ce structura rezultat va avea 22.000 de elemente din

oel conectate la 12.000 de noduri, generarea unui model real bazat pe aceast idee depeste

posibilitile proiectrii convenionale.

28

Figura 4.4: Designul optimal al Water Cube (China) a fost determinat prin analizarea a multiple configuraii ale miilor de elemente structurale din oel i a conexiunilor (nodurilor).

n schimb, n conformitate cu aceti autori, pentru a manipula dinamic acest sistem geometric

complex, n cadrul biroului de design al firmei Arup a fost conceput i formulat parametric un

software care a automatizat procesul de desen i de analiz. Bazat pe restricii specifice de

proiectare i aproximativ 190 de scenarii de ncrcare, acest algoritm verific iterativ distribuia

forelor prin ntreaga structur pe baza dimensiunilor specifice ale elementelor, permind

echipei s testeze diferite configuraii de proiectare i s primeasc feedback-ul n 25 de minute.

Rezultatul a fost o cladire spectaculoas, cu o structur sofisticat, care este optimizat din

punct de vedere al raportului greutate de material - rezisten. n plus fa de avantajele

structurale, Arup a estimat c a economisit 10 milioane de dolari la costurile de proiectare,

comparativ cu metodele tradiionale de proiectare.

4.1.3 Optimizarea dimensional

Acestea sunt combinate pentru a atinge criteriile de optimalitate dorite. n cadrul acestui

domeniu dou grupe principale de structuri pot fi difereniate:

Structuri discrete. Aici pot aprea structuri articulate i structuri cu legturi rigide. n

cazul structurilor din oel, aproape toate problemele posibile de optimizare au fost

supuse unei anumite forme de investigaie. Pentru a enumera o serie de probleme

rezolvate cu succes, optimizarea structurilor cu legturi semi-rigide [Kameshki i Saka,

2001], optimizarea mpotriva flambajului [Rong et al, 2001.], sau gsirea unei greuti

minime n cazul folosirii unui numr minim de profile de oel ntr-un design [Greiner

et al, 2001.] i [Greiner et al, 2003.]. Multe exemple de probleme de dimensiuni mici

29

din acest domeniu servesc drept benchmarks pentru diferite tipuri de algoritmi de

optimizare, cum sunt grinda cu zbrele din 10 bare [Belegundu, 1982] i grinda cu

zbrele spaial din 25 de bare [Adeli i Kamal, 1986], acestea fiind cele mai des citate.

Aici, toate variabilele sunt selectate din setul discret de valori admisibile predefinite.

Structuri continue. Acest grup cuprinde structuri asemntoare grinzilor - definite de

variabile continue, care nu sunt cunoscute n avans, n contrast cu cazul anterior

exemplul de baz este o grinda cu momente de inerie definite ca variabile continue

[Lagaros et al, 2002.]. nc o dat, metodele disponibile de optimizare sunt programarea

matematic pe baz de gradient, criteriile de optimalitate, metode hard-kill, cum sunt

cele menionate anterior: ESO i din nou EA. Ca o consecin a definiiilor introduse

de mai sus, putem distinge o form suplimentar de optimizare structural. n cazul n

care o variabil de design - dimensiunea unui element sau valoarea unei proprieti

materiale - poate ajunge la valoarea zero, adic nu este necesar n structur i poate fi

eliminat, atunci acest tip de optimizare este adesea numit Optimizare de Configuraie,

de exemplu [Kirsch, 1995]. Piatra de temelie a acestei abordri este aa-numita

structur de baza (ground structure), care definete toate poziiile posibile ale nodurilor

i setul tuturor elementelor / conexiunilor posibile ntre aceste noduri [M. E. Stavroulaki,

1997]. Apoi, scopul este eliminarea de elemente ineficiente pentru a obine o structur

optim. n cazul n care coordonatele de noduri sunt de asemenea necunoscute, atunci

aceasta formulare devine parte din optimizarea topologiei, a se vedea seciunea 1.2.1.

Prin urmare, optimizarea configuraiei poate fi vzut ca punct de legtur ntre cele

dou tipuri menionate anterior, de optimizare.

4.1.4 Optimizarea topografic

Aceast form este cel mai puin investigat parte a optimizarii structurale. Aici se pot ntlni

cutarea de forme eficiente pentru structuri de tip shell, membran sau cort. Doar cteva lucrri

pe aceast tem pot fi gsite n literatura de specialitate, de exemplu [Goslingt i Lewist, 1996]

sau [Schwarz et al, 2001]. Metodele programrii matematice sunt cunoscute ca singurele soluii

eficiente pentru acest tip de probleme de optimizare.n calculele de optimizare a structurilor se

opereaz cu o serie de noiuni i concepte ale teoriei matematice a optimizrii, care capt

semnificaii specifice corespunztoare scopului urmrit i restriciilor impuse.

30

5 ALGORITMII STOCASTICI

Designul optim generat de aceste metode este dependent de mai muli factori: designul de la

care se pornete, numrul iteraiilor de optimizare i gradul de aleatoriu al metodei. n cazul

general, nu este cunoscut configuraia optim global, iar rezultatele obinute n cursul a dou

rulri al aceluiai algoritm stocastic pot fi diferite. De aceea este necesar executarea multipl

a optimizrii pentru a putea fi evaluat performana designului. Metodele stocastice pot fi

evaluate referitor la performan i eficacitate lund n considerare acurateea rezultatelor, ct

sunt acestea de robuste i care este costul computaional.

Dup mai multe rulri ale algoritmului poate fi msurat acurateea n funcie de greutatea

medie a cadrului optim obinut. Robusteea se va msura n funcie de deviaia standard a

greutilor structurilor, iar costul computaional se msoar n numrul de analize structurale

necesare obinerii rezultatelor. Un algoritm bun nu se remarc doar prin generarea de modele

structurale mai uoare, ci i prin generarea acestora n mod consecvent cu un cost

computaional rezonabil. Metodele stocastice utilizate n literatura de specialitate includ

algoritmii genetici (GA), optimizare cu colonie de furnici (ant colony optimization), clire

simulat (simulated annealing SA), cutarea tabu (tabu search), optimizare cu roiuri de

particule (particle swarm optimization PSO), harmony search i metode hibride. Dei acestea

au dovedit c au rezultate bune n obinerea de configuraii pentru cadre optime, niciuna dintre

aceste metode nu s-a dovedit a fi superioar celorlalte n termenii celor trei caracteristici

metrice: acuratee, robustee i eficien computaional.

Optimizarea structural poate fi formulat n mai multe moduri ntr-un spaiu de variabile

discrete sau continue, cu funcii obiectiv care calculeaz costurile n diferite moduri, i o

multitudine de posibile restricii. Pentru a genera un context pentru formularea problemei i a

algoritmilor utilizai n studiile de caz, am prezentat n continuare un studiu al literaturii i

avantajele i dezavantajele celor mai utilizate metode de formulare. Problemele de optimizare

alese pentru acest studiu au un numr semnificativ de variabile discrete alese din domenii care

variaz intre zeci i sute de posibiliti. Funcia obiectiv aleas este discontinu, ceea ce face

nepractic utilizarea metodelor de gradient. Algoritmii stocastici sunt recunoscui pentru

performana lor n optimizarea structural n spaii de cutare ample, cu variabile discrete.

Multiple metode stocastice au fost aplicate n optimizarea structurilor, ns fiecare algoritm are

aceeai form de baz n care soluia cea mai eficient este mbuntit gradual cu fiecare

31

generaie. La fiecare iteraie, un numr stabilit de vectori de design este generat i valoarea

fitness a fiecruia este evaluat cu ajutorul funciei obiectiv i a restriciilor.

Cele mai bune soluii sunt selectate i utilizate la crearea generaiei urmtoare de soluii

candidat. Procesul este repetat pn cnd un criteriu stabilit de convergen este ndeplinit.

Datorit acestor asemnri cu teoria darwinist - supravieuirea celor mai potrivite soluii

(numite fittest), reinerea celor dorite i nmulirea soluiilor optime din mulimea acestora -

a algoritmilor utilizai la optimizarea cu variabile discrete, metodele se numesc algoritmi

evoluioniti.

Acetia ofer numeroase avantaje: nu necesit calculul gradienilor i matricelor hessiene -

fcndu-i eficieni n identificarea soluiilor pentru funcii neliniare i cu "vrfuri" ascuite.

Generarea aleatorie, prin ncercri consecutive, a soluiilor candidat, permite algoritmilor s

realizeze o cutare eficient a spaiilor unor probleme cu multe posibile variabile de design.

Deoarece fiecare generaie de soluii iterative este stocastic derivat din precedenta, aceti

algoritmi sunt buni candidai pentru calculul paralel, unde multiple lanuri de soluii pot fi

calculate pe procesoare paralele.

Cel mai nsemnat punct slab al acestor algoritmi este costul computaional mare, dependena

lor de parametri specifici care controleaz nivelul variabilitii de la o generaie la alta, i -

deoarece optimalitatea i convexitatea funciei obiectiv nu pot fi verificate cu gradieni i

matrice hessiene - incapacitatea de a determina cu siguran dac soluia obinut este optimul

global [Murren,2011].

Algoritmii stocastici ncorporeaz restriciile, n mod tipic, sub forma funciilor de penalizare:

() = ()(1 + =1 );

( 5-1)

() = {0 () 0> 0 () > 0

( 5-2)

Unde este un vector de variabile de design reprezentnd locaia seciunilor disponibile

n lista de posibiliti. Astfel, fiecare variabil poate fi aleas din aceste posibiliti. Se

asigur satisfacerea restriciilor prin aplicarea factorului de penalizare (1 + )=1 la

funcia de cost (). Restriciile () sunt exprimate n termeni de funcia auxiliara ()

ntr-o manier n care () = 0 cnd restricia este satisfcut i >0 n caz contrar.

32

5.1 ALGORITMII EVOLUIONITI

Sunt o categorie de metode numerice stocastice bazate pe analogii cu genetica. Paradigmele

AE au fost dezvoltate de cercettori ncepnd cu 1960. Principiile evoluioniste au fost

implementate n algoritmi cu ajutorul crora se pot soluiona probleme de optimizare. Diferena

ntre algoritmii evoluioniti i algoritmii tradiionali const n crearea unei populaii de puncte.

Prin adaptarea de generaii succesive i a unui numr mare de indivizi, algoritmii evoluioniti

efectueaz o cutare direct i eficient (Sivanandam, i alii, 2008).

Metodele care sunt cel mai frecvent aplicate n arhitectur i inginerie sunt:

Algoritmi genetici (GAs)

Strategii evoluioniste (ESs)

Calcul evoluionist interactiv (IEC)

Aceste metode au punct comun n utilizarea unor generaii de populaii de soluii pentru

cutarea n spaiul de soluii a celor care corespund cel mai bine criteriilor funciilor obiectiv.

Performana unei soluii este msurat prin fitness. Populaia evolueaz gradual prin

ncruciare, mutaie i selecie spre soluii mai bune.

n lucrarea de fa, soluiile individuale descriu forme structurale, geometrice, i sunt

reprezentate prin variabile. Variabilele sunt reprezentate de un cromozom asupra cruia sunt

aplicai operatorii genetici pentru a crea indivizi noi mai performani.

Cu cat e nevoie de mai multe variabile pentru a descrie geometria structurii, cu att lungimea

irului cromozomului va fi mai mare. Mrimea populaiei este proporional cu lungimea

cromozomului iar numrul de generaii necesare pentru convergen depinde de ambii factori.

Aadar, cu ct e nevoie de mai multe variabile de proiectare cu att problema devine mai

intensiv computaional (Goldberg, Deb & Clark 1991).

5.1.1 Algoritmii genetici

Algoritmilor genetici li s-a acordat o atenie deosebit datorit potenialului de a reprezenta o

modalitate nou de optimizare (Mitsuo, i alii, 2008).

Primul cercettor al teoriei algoritmilor genetici a fost John Holland, care i-a descris n cartea

Adaptation n Natural and Artificial Systems n 1975. Domeniul algoritmilor evoluioniti

include strategii evoluioniste (ES), programare evoluionist (EP), via artificial (AL),

programare genetic (GP). n 1960 Ingo Rechenberg i Hans-Paul Schwefel au dezvoltat ideea

33

strategiilor evoluioniste. n acelai timp Lawrence Fogel i alii au pus bazele programrii

evoluioniste. Aceste teorii aveau n comun ideea procesului de mutaie i selecie. Inspirai din

teoria evoluionist a lui Darwin, Bremermann i Fraser au folosit teoria recombinrii

(crossover) [Hayalioglu, 2001].

Algoritmii genetici sunt construii pentru a putea efectua cutarea structurilor din ce n ce mai

bune, iar aceast procedur necesit o funcie obiectiv funcia fitness a crei valoare este

asociat unui ir numit individ.

GA utilizeaz trei operaii de baz pentru crearea unei noi generaii: selecie, ncruciare i

mutaie grupate sub denumirea de reproducere. Operaia de reproducere cuprinde copierea sau

modificarea unor indivizi dintr-o generaie n alta, n funcie de valoarea funciei fitness.

Funcia de selecie poate fi implementat ntr-un algoritm n diferite forme. Cea mai simpl

form a funciei se bazeaz pe teoria roulette wheel [Sivanandam, 2008].

GA sunt avantajoi i eficieni cnd:

spaiul de cutare este mare, complex sau dificil de definit,

domeniu de rspuns este redus sau condiiile sunt dificil de codat pentru a obine un

spaiu de rspuns concentrat,

metodele tradiionale de optimizare nu genereaz soluii satisfctoare.

Printre avantajele folosirii GA merit menionate uurina cu care se pot aplica tipuri de

restricii arbitrare i

varietatea mare a posibilelor

funcii obiectiv. Toate aceste

lucruri pot fi manipulate ca i

componente de penalizare a

funciei de fitness, fcnd

uoar adaptarea

algoritmului la cerinele

specifice ale unei varieti de

obiective generale

[Sivanandam,2008].

Figura 5.1 Schema unui algoritm genetic simplu

34

Mecanismele fundamentale care realizeaz legtura dintre algoritmul genetic i problema care

trebuie rezolvat sunt urmtoarele:

codificarea problemei n termeni de cromozomi,

funcia de evaluare, care furnizeaz o msur a calitii fiecrui cromozom n contextul

problemei respective.

Codificarea se realizeaz de obicei prin iruri de cifre binare. S-a demonstrat c acest mod de

codificare este robust, n sensul adaptrii lui la o mare varietate de probleme practice. Ceea ce

i se reproeaz uneori este precizia soluiei, limitat la numrul de bii, pe care se face

reprezentarea. Alegerea unui numr suficient de mare de bii pentru reprezentarea valorilor

reale din problem poate nltura ns acest dezavantaj.

Mai jos sunt prezentate programe scrise n MATLAB, care fac conversia zecimal-binar i

invers.

Figura 5.2 Exemplu de funcie de transcriere a soluiilor candidat din zecimal n binar si viceversa.

Funcia de evaluare primete la intrare irul de cromozomi i returneaz numere sau liste de

numere ce reprezint performana cromozomilor. Ea are rolul mediului nconjurtor pentru

evoluia natural.

function a = decbin(num, numbt)

% num numarul zecimal ce urmeaza sa fie transformat

%numbt numar de biti

i=0;

while num>=2

if rem(num,2)==0

a(1,numbt-i)=0;

else

a(1,numbt-i)=1;

end

i=i+1;

num=fix(num/2);

% fix face rotunjire spre zero

end

if num==1

a(1,numbt-i)=1;

end

for k=1:numbt-i-1

a(1,k)=0;

end

% Returneaza un vector binar

function y = bindec(a)

% a - vector ce contine numarul binar de intrare.

% Returneaza un numar zecimal, rezultat al conversiei.

num=0;

numbt=length(a);

for i=1:numbt

num=a(1,i)*2^(numbt-i)+num;

end

y=num;

35

Structura unui algoritm genetic fundamental este dat mai jos:

1. Se iniializeaz populaia de cromozomi.

2. Se evalueaz fiecare cromozom din populaie. Se selecteaz prinii noii populaii.

3. Se creeaz o nou generaie de cromozomi prin mperecherea cromozomilor selectai,

folosind operatori genetici.

4. Se terg membrii populaiei iniiale, pentru a fi nlocuii cu noua generaie.

5. Se evalueaz noii cromozomi i se insereaz n noua populaie.

6. Dac timpul de cutare nu s-a terminat, se merge la pasul 3. n caz contrar, se oprete

execuia algoritmului.

Modul de reprezentare a populaiei de cromozomi, modul de evaluare a cromozomilor i modul

de reproducere sunt componente eseniale ale algoritmului genetic i sunt prezentate n cele ce

urmeaz.

Valoarea fitness a unui individ, ntr-un algoritm genetic este dat de funcia obiectiv (funcia

fitness). n cazul optimizrii multicriteriale funcia obiectiv se determin destul de dificil.

Pentru problemele de optimizare multicriteriale exist o problem legat de evaluarea soluiei

optime. Cnd procesul GA de cutare ncepe, populaia este supus unei evaluri cu ajutorul

funciei fitness. n funcie de aceast evaluare se va alctui noua populaie. La acel moment, n

fiecare generaie, soluiile relativ bune sunt reproduse i soluiile cu valoare fitness mic sunt

abandonate. Pentru a distinge soluiile avem nevoie de o funcie de evaluare (funcia fitness),

aceasta avnd un rol important n procesul evoluionist alturi de mecanismele de scalare.

Atunci cnd se evalueaz funcia fitness a unor indivizi, avem nevoie de o procedur de

decodare [Bends, 1988].

O component necesar n aplicarea algoritmilor genetici este modul de manipulare a

restriciilor, deoarece operaiile algoritmilor genetici asupra indivizilor creeaz indivizi

nefezabili [Bends, 1988]. Algoritmii genetici genereaz indivizi care urmeaz s fie testai

cu ajutorul funciei fitness i a restriciilor.

Procesul de scalare are rolul de a evita o convergen prematur a algoritmului sau o terminare

nceat. De obicei la nceputul algoritmului variaia ntre indivizi este mare i doar o mic parte

dintre ei sunt mai buni dect restul indivizilor. Cu o selecie conform valorii fitness nescalate

36

acetia se vor multiplica repede i vor mpiedica algoritmul s exploreze spaiul soluiilor, acest

fenomen este cunoscut drept o convergen prematur [Melanie, 1996].

Scalarea liniara a valorii fitness se face cu relaia:

= +

Cu aceast metod valoarea fitness medie a indivizilor trebuie s se pstreze i dup scalare.

Pentru a nltura posibilitatea ca indivizii superiori s domine procesul de scalare trebuie

respectat egalitatea:

= `

Unde: C reprezint numrul indivizilor cu valoarea fitness optim.

Metoda de scalare sigma are rolul de a exercita o presiune constant asupra procesului.

Valoarea fitness a individului se recalculeaz n funcie de valoarea fitness medie a populaiei

i de deviaia standard [Arora, 1997].

(, ) = {1 +

()()

2() () 0

1 () = 0

(, ) reprezint valoarea scalat a individului , () reprezint valoarea fitness a

individului, iar () este valoarea medie a populaiei i () este deviaia standard a fitness-

ului populaiei [Arora, 1997].

Scalarea prin metoda puterii se aplic cu ajutorul relaiei:

=

Unde: k constant (1.005)

Aceast metod se folosete mpreun cu metoda de selectare roulette wheel .

Selecia este un operator genetic care stabilete irurile populaiei curente care vor fi alese

pentru a transmite materialul lor genetic generaiei urmtoare.

Exist trei tehnici de selecie:

cea mai utilizat este selecia proporional, care modeleaz mecanismul seleciei naturale,

n care cromozomii cu o evaluare mai mare au o ans mai mare de a fi alei. Cunoscut i sub

numele de principiul ruletei, aceast tehnic presupune parcurgerea urmtoarelor etape:

37

1. Se stabilete funcia de evaluare pentru fiecare cromozom din populaie feval(xi)

2. Se nsumeaz toate funciile de evaluare = ()

3. Cromozomilor li se atribuie aleator numerele naturale i.

Apoi, urmtorii pai se repet pn la crearea unui numr suficient de perechi de cromozomi:

4. Se genereaz numerele aleatoare n i m, astfel ca 1n, m feval ,

5. Se alege cromozomul xi, unde i este cel mai mic numr care satisface relaia:

()

6. Se alege cromozomul xj, ca la pasul 5, cu m n loc de n

7. Se stabilete perechea de cromozomi xi i xj.

Aceast modalitate de selecie ns poate genera serioase probleme dac un cromozom din

populaie are o funcie de evaluare de valoare mult mai mare dect a celorlali cromozomi,

aceasta fiind departe de optim, iar atunci selecia proporional va raspndi foarte repede

caracteristicile acestui cromozom n populaie. n cteva generaii populaia ar putea fi alctuit

numai din astfel de cromozomi i algoritmul genetic nu ar mai putea evolua, deci optimul nu

mai poate fi gsit. Acest fenomen este cunoscut sub numele de convergen prematur.

O alt problem o constituie gradientul sczut al funciei de evaluare spre sfritul cutrii.

Treptat soluia optim este preluat de ntreaga populaie. Efectul este cunoscut sub numele de

terminare lent (slow finishing).

O alt tehnic de selecie este selecia pe baza rangului, n care probabilitatea de a fi ales este

o funcie liniar de locul ocupat de individ (cromozom) n cadrul populaiei. Avantajul const

n faptul c nu mai este necesar interpolarea permanent a evalurii ca n cazul precedent. Un

caz special de selecie de acest tip este selecia prin trunchiere, prin care se elimin o parte din

cromozomii cu cea mai slab evaluare, iar n locul lor se genereaz alii, dup diferite scheme

posibile. Un exemplu de selecie prin trunchiere este prezentat n continuare:

1. Din populaia actual se elimin n cromozomi care au evaluarea cea mai slab.

2. Se genereaz un nou cromozom x, folosind principiul ruletei

38

3. Dac x difer de toi ceilali cromozomi ai populaiei actuale, atunci el este inclus n

populaie; n caz contrar, este supus operatorului de mutaie (explicat mai jos) pn ce devine

diferit de ceilali cromozomi i este inclus n populaie.

O alt metod euristic de selecie este selecia elitist, care reine ntotdeauna cei mai buni

cromozomi ai populaiei (de regul unul singur). Ea garanteaz convergena asimptotic spre

un minim global, dar rata de convergen este variabil n funcie de problem. Elita poate

introduce un efect de dominan asupra populaiei care s duc la o stagnare timpurie a

procesului de evoluie. Soluia const n utilizarea operatorului de mutaie pentru reducerea

acestui efect.

ncruciarea (crossover) este operatorul necesar pentru construcia noilor indivizi ai

populaiei.

Populaia intermediar, format din n cromozomi, este mprit n n/2 perechi i operatorul de

ncruciare este aplicat fiecrei perechi cu o anumit probabilitate . Valoarea lui este de

obicei mai mare de 0,6 i de cele mai multe or