Analiza Algoritmilor Genetici Si a Posibilitatilor Implementarii Lor In Diferite Domenii

Introducere 6

I. Analiza algoritmilor genetici 7

1.1. Algoritmi evoluționiști 7

1.2. Evoluția computațională 7

1.3. Principalele paradigme ale evoluției computaționale 10

1.3.1. Strategii evolutive 10

1.3.2. Programarea evoluționistă 10

1.3.3. Programarea genetică 10

1.3.4. Alte tehnici 11

1.4. Algoritmii genetici 12

1.4.1. Originea atgoritmilor genetici 12

1.4.2. Noțiune de algoritm genetic 13

1.4.3. Termeni biologici 15

1.5. Algoritmul general 16

1.5.1. Genetică 17

1.5.2. Analiza teoretică a atgoritmilor genetici 19

1.5.3. Teoria schemelor 20

1.6. Codificarea cromozomilor 22

1.6.1. Populația inițială 23

1.6.2. Fitness-ul unui cromozom 23

1.6.3. Selectarea cromozomilor părinți 23

1.6.3.1. Selecție aleatoare 23

1.6.3.2. Selecția cu ajutorul ruletei 24

1.5.3.3. Selecția aranjată 24

1.6.3.4. Selecție cu starea consolidată 24

1.6.3.5. Elitism 25

1.7. Încrucișarea (crossover) 26

1.7.1. Codificare binară 28

1.7.2 Codificarea sub formă de permutare 29

1.7.3 Codificarea sub formă de valoare: 30

1.8. Operația mutație 31

1.9. Recombinarea 32

1.10. Părinți unici 32

1.11. Încrucișarea genelor 33

1.11.1. Încrucișarea succesiunilor de gene 33

1.12. Alipirea genelor 33

1.13. Selecția 34

1.14. Deschiderea “cutiei negre” 35

1.15. Optimizarea 36

1.15.1. Paralelismul 36

1.15.2. Căutatea operatorilor genetici efectivi 37

1.15.3. Divizarea domeniului problematic 37

1.15.3.1. Exemplu 37

1.15.4. Devierea nereușitelor 38

1.15.5. Corectarea greșelilor 38

1.15.6. Soluțiile incomplete și schimbarea restricțiilor către resurse 38

1.15.7. Utilizarea metaforelor 39

Rezumat 39

II. Posibilitățile de implimentare a algoritmilor genetici în diferite domenii 40

2.1. Exemplu de aplicație: consultantul de bursă genetică 40

2.1.1. Analiza problemei 40

2.1.2. Structura genetică 41

2.1.3. Evaluarea utilității 42

2.1.4. Procesul alegerii 43

2.1.5. Inițializarea populației 44

2.1.6. Strategia mutației 45

2.1.7. Strategia recombinării 46

2.1.8. Rezultate și concluzii 48

Rezumat 49

2.2. Implementare 49

2.2.1. Problema 1 49

2.2.2. Problema 2 50

2.2.3. Problema 3 50

Rezumat 52

III. Aprecierea cheltuielilor economice ale proiectului de diplomă 53

3.1. Construirea grafului rețea și calcularea parametrilor principali. 58

3.2. Aprecierea cheltuielilor 61

Tab.3.10 65

IV. Protecția muncii 66

4.1. Prezentarea funcțiilor în formă de sistem. 66

4.2. Securitatea muncii 67

4.3.Analiza condițiilor protecției muncii 67

4.3.1. Indicii stării condițiilor de muncă 67

4.3.2. Metode de analiză a condițiilor de muncă 68

4.5. Unitățile luminiscente de bază și corelațiile folosite în protecția muncii. 69

4.5.1. Acțiunea luminii asupra organismului uman. Rolul iluminatului la crearea condițiilor de muncă sănătoase. 69

4.5.2. Feluri și sisteme de iluminare 70

4.5.3. Calcularea iluminatului artificial în încăpere. 71

4.6. Aprecierea pericolului la monitor. 72

4.7. Analiza condițiilor de muncă. Factorii dăunători și periculoși la locul de lucru. 75

4.8. Cerințele ergonomice privind locul de muncă. 78

4.9. Condiționarea aerului. 80

4.10. Cerințele securității tehnice la începutul lucrului 81

4.11.Cerințele securității tehnice în timpul de lucru. 81

4.12.Acțiuni în cazuri fatale. 81

4.13. Securitatea antiincendiară. 82

4.13.1. Cauzele apariției incendiilor. 83

4.13.2. Securitatea antiincendiară în sălile de calcul. 84

Concluzii 86

Bibliografie 87

Anexa 1 88

Anexa 2 93

Anexa 3 96

Anexa4 98

Anexa 5 99

Anexa 6 101

Anexa 7 102

Anexa 8 105

=== ANPRINT ===

Anexa 5

Anexa 8

Tab.3.10

Efectul social

Anexa 6

=== DIPLOM_ALG_GEN ===

Introducere

Algoritmii genetici sunt o parte a calculului evolutiv care la rândul său este o parte în rapida dezvoltare a inteligenței artificiale. Algoritmii genetici sunt un tip de algoritmi stocastici relativ noi.Ei au fost inspirați din teoriile lui Ch.Darwin despre evoluție. Simplu spus, soluția unei probleme rezolvate de către un algoritm genetic evoluiază.

Începuturile algoritmilor genetici se regăsesc în anii 1950 când o echipă de biologi a folosit computerele pentru a simula sisteme biologice. Ideea calculuilui evolutiv a fost introdusă în 1960 de către I. Rechenberg în lucrarea sa “Evolution strategies”. Ideea lui a fost dezvoltată de către alți cercetători. Algoritmii genetici au fost inventați de către John Holland. Acesta și-a expus ideile în cartea “Adaptation în Natural and Artificial Systems”, publicată în 1975.

În 1992 John Koza a folosit algoritmii genetici pentru a dezvolta programe destinate anumitor scopuri precise. Metoda folosită de el a primit denumirea de programare genetică.

Algoritmul genetic rezolvă probleme pe calea aplicării principiilor teoriei evoluției firești (naturale) a organismelor vii. Mediul programului imită natura, permițând submulțimii de a avea organisme mult mai adaptate la viață și înmulțirea pe contul organismlor mai slabe. În locul organismelor adevărate populația programului constă din soluții genetic codate. O soluție mai bună crează o altă soluție puțin diferită de precedenta, pe când cele mult mai slabe “mor” și sunt înlocuite cu urmașii soluțiilor rămase în viață.

Algorilmii genetici caută să simuleze evoluția speciilor și se bazează pe principiile supraviețuirii celor mai adaptați, adică simulează așa numitul proces de selecție naturată. Cu alte cuvinte, algoritmii imit selecția naturată, făcând să concureze indivizii dintr-o populație pentru a se reproduce. O funcție de evaluare pune în corespondența oricărui individ o valoare de adaptare. În populație apar indivizi noi atunci când indivizii exisienți își schimbă bagajul genetic în timpul reproducerii sau când bagajul genetic a unor indivizi este transformat în urma mutațiilor.

I. Analiza algoritmilor genetici

1.1. Algoritmi evoluționiști

Algoritmii evoluționiști au la bază câteva principii ale evoluției: supraviețuirea celor mai buni și modelează câteva fenomene naturale cum ar fi transmiterea informației genetice și combinarea acesteia între mai mulți indivizi, constituie una din categoriile moderne de căutare a soluțiilor.

Aici sunt prezentate principalele paradigme ale algoritmilor evoluționiști (algoritmi genetici, strategii evolutive, programare evolutivă și programarea genetică). Algoritmi evoluționiști au fost larg utilizați în ultima vreme în știință și inginerie pentru rezolvarea unor probleme complexe.

În ultimele două decenii interesul în algoritmi bazați pe pricipiile evoluției a crescut. Un termen acceptat recent ca definitoriu pentru acest tip de tehnici este metoda evoluției computaționale ( EC ). În această clasă pe lângă algoritmii genetici, strategiile evoluțive, programarea evolutivă și programarea genetica sunt incluși și o mulțime de algoritmi și sisteme hibride care împrumută tehnici și operatori ale acestei paradigme și ca urmare sunt greu de clasificat.

1.2. Evoluția computațională

În general orice metodă de rezolvare a unei probleme poate fi privită în ultima instanță ca o căutare în mulțimea potențialelor soluții. Mai mult, această căutare urmăreste găsirea soluției optime în contextul problemei și ca urmare căutarea poate fi văzută ca o problemă de optimizare. Pentru probleme ale căror soluții se afla într-un spațiu, mic metodele exhaustive clasice sunt mulțumitoare, dar pentru spații largi de cautare sunt necesare tehnici de inteligență artificiala. Printre acestea se afla și metodele evoluției computaționale și care folosesc drept model câteva fenomene naturale: moștenirea genetică și "Darwinian strife for survival". Cele mai bune metode de evoluție computațională sunt algoritmii genetici și ca urmare de foarte multe ori termenii sunt utilizați interschimbați.Structura programelor bazate pe această tehnică este foarte asemănătoare. În continuare sunt prezentate în comparație structurile a trei algoritmi: "hillclimber", "simulated annealing" și "evolutionary algorithm".

procedure iterated hillclimber
begin

t <- 0
repeat

local <- FALSE
selecteaza Vc aleator
evalueaza Vc
repeat

selecteaza N noi posibile solutii în vecinatatea lui Vc prin modificarea unui singur bit al lui Vc
selecteaza din aceste N valori Vn cu valoarea cea mai "buna" a lui f în conditiile problemei
if f ( Vc ) < f ( Vn ) then Vc <- Vn

else local <- TRUE

until local t <- t + 1

until t = MAX

end

Exista mai multe tipuri de "hillclimber", diferențiate de metoda alegerii noii populații. Găsirea soluției într-un pas în acestă metodă depinde foarte mult de punctul de pornire. Se poate întampla ca algoritmul în cautarea să să ajungă într-un punct de optim local și care este returnat ca soluție a problemei, caz în care algoritmul esuează.

Structura algoritmului "simulated annealing" este urmatoarea:

procedure simulated annealing
begin

t <- 0
initializarea temperaturii T
selectarea unui element Vc aleator evalueaza Vc
repeat

repeat

selecteaza o noua solutie in vecinatatea lui Vc prin modificarea unui singur bit al lui Vc
if f ( Vc ) < f ( Vn ) then Vc <- Vn
else

if random [ 0, 1 ) < exp ( ( f ( Vn ) – f ( Vc ) ) / T ) then Vc <- Vn

until ( termination-condition )
T <- g ( T, t )
t <- t + 1

until ( stop-criterion )

end

"Termination-condition" verifică dacă "echilibrul termic" s-a stabilit, dar poate fi și un simplu test dacă ciclul s-a executat de un număr k ori dorit. Cu ajutorul lui T se urmărește dacă în sistem mai au loc schimbări sau acesta a "înghetat", caz în care algoritmul se încheie. Algoritmul chiar dacă ajunge într-un maxim local poate avea șansa de a părăsi acest punct și de a găsi maximul global datorită funcției random. Teoretic pare posibil, dar practic algoritmul poate esua în anumite situatii.

Structura unui algoritm evoluționist este în mare următoarea:

procedure evolutionary algorithm
begin

t <- 0
initializare P ( t )
evaluare P ( t )
while ( not termination-condition ) do

t <- t + 1
selecteaza P ( t ) din P ( t – 1 )
efectuaza transformari aupra lui P ( t )
evalueaza P ( t )

end

end

Algoritmul evoluționist mentine o populație de indivizi, P ( t ) = { xt1, …, xtn }pentru iterația t. Fiecare individ reprezintă o potențială soluție și fiecare xti este evaluat pentru a măsura capacitatea sa de generare a altor indivizi. O nouă populație este formată din unii indivizi selectați din pasul anterior. Dupa crearea noii populații o parte o să sufere o serie de transformări (mutații = modificarea unui singur bit ( m: S -> S ) sau încrucișări = formarea unui nou individ din doi sau mai mulți părinți ( c:S x … x S -> S ). După un număr oarecare de iterații algoritmul converge către o soluție optimă. Pe această schemă generală se pot implementa o gamă variată de algoritmi în care fiecare îmbină altfel diferitele date ale problemei. Ei pot îngloba sau nu anumite informații pentru controlul procesului de căutare a indivizilor. Sau poate fi schimbată ordinea în care au loc operațiile:

selectează P ( t ) din P ( t – 1 )
efectuază transformări aupra lui P ( t )

O altă variantă este menținerea celui mai bun individ în decursul întregului proces de căutare. Astfel soluția va fi reprezentată de acest individ și nu de cel mai bun din ultimul pas al algoritmului; acest model este foarte folositor pentru rezolvarea multor probleme de optimizare. În concluzie structura de date și setul de operatori "genetici" constituie partea cea mai importantă a oricărui program evoluționist, parte care îl diferențiază de alte programe de același tip. O idee destul de recentă întâlnită în diferite materiale o constituie folosirea rezultatelor furnizate de un algoritm precum "simulated annealing" drept date de start pentru prima populație a unui algoritm evolutiv. Astfel se poate înlătura neajunsul primului de a nu găsi optimul global și ar reduce din timpul de calcul al celui de al doilea.

1.3. Principalele paradigme ale evoluției computaționale

În cadrul evoluției computaționale există câteva tehnici de abordare a problemelor. Acestea vor fi descrise în continuare.

1.3.1. Strategii evolutive

Strategiile evolutive ( ESs ) au fost dezvoltate ca metode pentru rezolvarea problemei de optimizare parametrizate; în consecință, un cromozom este reprezentat ca o pereche de vectori ( de valori de tip flotant ), spre exemplu: v = ( x, s ). Primele strategii erau bazate pe populații formate dintr-un singur individ. Ca urmare nu există decât un singur operator genetic și anume mutația. O idee importantă este reprezentarea indivizilor ca o pereche de vectori flotanți, unde primul reprezintă un punct în spatiul de căutare, iar al doilea este deviația standard. Procesul de mutație este realizat prin înlocuirea vectorului xt din ( xt, s ) cu xt+1 = xt + N ( 0, s ), unde N ( 0, s ) este un vector de numere Gaussiene generate aleator ( în acord cu observațiile biologice că schimbări mici apar mult mai des decat cele mari ). Noul individ este acceptat ca un membru al noii populații dacă valoarea sa este superioară și satisface toate condițiile impuse ( dacă există ). De exemplu dăca f este funcția de maximizat, fara constrângeri, atunci ( xt+1, s ) înlocuiește părintele sau ( xt, s ) dacă f ( xt+1 ) > f ( xt ). Altfel populația rămâne neschimbată, noul individ fiind eliminat. În timpul procesului de evoluție vectorul standard de deviație rămâne neschimbat. Dacă toate componentele vectorului sunt identice și problema de optimizat este regulată, atunci poate fi verificată următoarea teoremă de convergență:

Teorema de convergență: Pentru s > 0 și o problemă regulată de optimizat cu fopt > -inf. ( minimizare ) sau fopt < inf. ( maximizare ), atunci

p { lim (t->inf.) f ( xt ) = fopt } = 1.

Mai târziu au apărut strategii care permiteau parametrilor de control să se adapteze singuri în timpul evoluției. Aceasta permite ca algoritmul să se apropie mai repede în timp de optimul problemei. Operatorii folosiți în aceste strategii ( notate ( m + l )-ESs și ( m + l )-ESs ) folosesc două nivele de învățare: parametrii de control ai indivizilor ( s ) nu mai sunt constanți, sunt introduși în structura lor și participă la procesul evolutiv. Pentru producerea unui descendent se aplică:

încrucișarea:

Se selectează doi indivizi:
( x1, s1 ) = ( ( x11, …, x1n ), ( s11, …, s1n ) ) și
( x2, s2 ) = ( ( x21, …, x2n ), ( s21, …, s2n ) )
și se aplică operatorul de încrucisare. Acesta poate fi de două tipuri:
discret :
( x, s ) = ( ( xq11, …, xqnn ), ( sq11, …, sqnn ) ),
unde qi = sau qi = 2 în funcție de unde provine componenta respectivă.

intermediar:
( x, s ) = ( ( (x11+ x21)/2,…, (x1n +x2n)/2), ( (x11+ x21)/2,…, (x1n +x2n)/2) )

mutația:

Se aplică noului individ obținut; rezultatul ( x', s' ) este:
s' = s · exp ( N ( 0, Ds ) ) și
x' = x + N ( 0, s ),
unde Ds este un parametru al metodei.

1.3.2. Programarea evoluționistă

Tehnicile de programare evoluționista, folosind metode de inteligenta artificiala, dezvoltă abilitatea de prezicere a schimbărilor într-un mediu. Mediul este descris ca o secvență de simboli ( dintr-un alfabet finit ) și algoritmul de rezolvare presupune să producă un nou simbol, care să maximizeze rezultatele funcției. Un exemplu ar fi găsirea ( prezicerea ) următorului simbol an+1 într-o secvență a1a2 … an, pe baza simbolurilor anterioare. Tehnica programării evoluționiste menține o populație finita de stări, reprezentând potențiale soluții ale problemei. Ca și strategiile evolutive această tehnică întâi crează noii indivizi și apoi selectează pe aceia care fac parte din urmatoarea generație. Fiecare parinte produce un singur individ, asa că populația intermediară se dubleaza ca număr. În continuare cei mai buni pop_size indivizi sunt reținuți pentru a crea noua populație (cele mai probabile soluții). În versiunea originală a exemplului dat acest proces este reluat de mai multe ori înainte de a alege următorul simbol, considerat ca fiind cel mai probabil. Odată adaugat simbolul, procesul este reluat. Programarea evoluționistă a fost recent generalizată pentru rezolvarea problemelor numerice de optimizare.

1.3.3. Programarea genetică

O altă modalitate a fost dezvoltată destul de recent de Koza. Acesta a sugerat că programul dorit trebuie el însuși să se schimbe pe parcursul procesului evolutiv. Cu alte cuvinte pe langă rezolvarea problemei și a creării programului de rezolvare trebuie cercetat și spațiul programelor pe calculator pentru a alege cel mai bun dintre ele. Astfel a apărut o nouă tehnologie numită Programarea Genetică ( GP ). În acest scop sunt cinci pași importanți de urmat în folosirea programării genetice pentru o problemă particulară: · selecția terminatorilor; · selecția funcției; · identificarea funcției de evaluare; · selectarea parametrilor sistemului; · selectarea condiției de terminare. Este important de notat că structura care susține evoluția este un program structurat ierarhic. Spațiul de căutare este un superspațiu de programe valide, care poate fi văzut ca spațiu de rădăcini arborescente. Fiecare arbore este compus din funcții și terminale apropiate de particularitatea domeniului problemei. Funcția de evaluare acordă o anumită șansă fiecărui arbore ( program ); în general această funcție returnează distanța dintre rezultatul corect și rezultatul obținut în toate cazurile testării. Selectarea unui arbore este proporțională cu valoarea acestei funcții de evaluare. Principalul operator este încrucișarea care produce doi indivizi noi prin combinarea a doi parinți și care realizeaza schimbarea unor subarbori între cei doi parinți. Mai pot fi definiți și alți operatori precum: mutația, permutarea, editarea sau construirea definită a subarborilor. Spre exemplu mutația poate fi definită ca înlocuirea unui subarbore cu unul nou generat aleator. În plus Koza a considerat adăugarea unui nou pas în abordarea unei probleme cu ajutorul programării genetice: un set de proceduri ( Funcții Definite Automat ), utile în cazul reutilizării codului și care descoperă și exploatează: regularități, simetrii, similarităti și modularităti ale problemei și în final programul obținut poate folosi aceste proceduri la diferite nivele ale rulării sale. Mai mult operatorii pot fi priviți de asemenea ca programe, iar setul de funcții poate fi constituit din mai multe programe, care evoluează pe parcursul utilizării.

1.3.4. Alte tehnici

Mulți cercetători au modificat diferiți algoritmi evoluționiști prin adăugarea unor cunoștințe particulare specifice problemei de rezolvat. Există articole despre inițializarea problemei, diferite reprezentari, tehnici de decodificare ( maparea între reprezentarea genetică și reprezentarea spațiului de căutare al problemei ) și utilizarea diferiților operatori. Un exemplu cunoscut este Genetic-2N realizat pentru rezolvarea unor probleme neliniare folosind matrici ca reprezentare a indivizilor. Este greu de clasificat un algoritm genetic, datorită particularităților sale, dar totuși este considerat o tehnică evoluționistă pentru rezolvarea unei probleme particulare. Rezolvarea problemelor cu ajutorul algoritmilor evoluționiști se poate face și pe arhitecturi paralele de calcul. În acest caz apar caracteristici noi ( exemplu speedup ), diferite metode de tratare a populațiilor și a comunicațiilor între subpopulații aflate pe diferite calculatoare. În continuare sunt prezentate soluții de utilizare asupra a două topologii utilizate: inel și de tip injectie. În primul caz pe fiecare calculator ( NC ) se află o populație ( pop_size ), în total NC · pop_size indivizi ca o populație mare. La fiecare M generații sunt schimbate între "lumi" cei mai buni NP indivizi ( 1-> 2 ->3 -> … -> NC ->1 ).

Fig.1.1. Topologia “inel”

În al doilea caz subpopulațiile sunt repartizate la fel, dar comunicația se face diferit. NC 1 din cele NC sunt așezate ca frunze ale arborelui în care a NC populație este rădăcina. Cele NC – 1 injecteaza cei mai buni M indivizi în populația rădăcinii ( deci în total ( NC – 1 ) · M indivizi ) la fiecare 10 generații. Această injecție e de tip "one-way" a informatiei ( mai slabă ca rezultate ). Indivizii injectați înlocuiesc cei mai slabi indivizi ai populației rerespective.

Fig.1.2. Topologia de tip “injecție”

1.4. Algoritmii genetici

Algoritmii genetici sunt o parte a calculului evolutiv care la rândul său este o parte în rapida dezvoltare a inteligenței artificiale. Algoritmii genetici sunt un tip de algoritmi stocastici relativ noi.Ei au fost inspirați din teoriile lui Ch.Darwin despre evoluție. Simplu spus, soluția unei probleme rezolvate de către un algoritm genetic evoluiază.

Începuturile algoritmilor genetici se regăsesc în anii 1950 când o echipă de biologi a folosit computerele pentru a simula sisteme biologice. Ideea calculuilui evolutiv a fost introdusă în 1960 de către I. Rechenberg în lucrarea sa Evolution strategies. Ideea lui a fost dezvoltată de către alți cercetător. Algoritmii genetici au fost inventați de către John Holland. Acesta și-a expus ideile în cartea Adaptation în Natural and Artificial Systems, publicată în 1975.

În 1992 John Koza a folosit algoritmii genetici pentru a dezvolta programe destinate anumitor scopuri precise. Metoda folosită de el a primit denumirea de programare genetică.

1.4.1. Originea atgoritmilor genetici

Algorilmii genetici caută să simuleze evoluția speciilor și se bazează pe principiile supraviețuirii celor mai adaptați. Adică simulează așa numitul proces de selecție naturată. Cu alte cuvinte, algoritmii imit selecția naturată, făcând să concureze indivizi dintr-o populație pentru a se reproduce. O funcție de evatuare pune în corespondența oricărui individ o vatoare de adaptare. În populație apar indivizi noi atunci când indivizi exisienți își schimbă bagajul genetic în timpul reproducerii sau când bagajul genetic a unor indivizi este transformat în urma mutațiilor.

Aceste principii de supraviețuire și reproducere sunt bine descrise în cunoscuta lucrare "Originea speciilor prin selecția naturată" a lui Charles Darwin publicată în 1859. Să ne referim puțin la aceste principii.

Evoluția în natură survine atunci când există indivizi cu capacitate de a se reproduce, când există o populație de acești indivizi, când există o varietate (diversitate) în mijlocul acestei populații și când supraviețuirea indivizilor depinde de diferența dintre ei. Toți indivizii în viață posedă un genotip și un fenotip. Genotipul e constituit din gene situate pe cromozomi stocați în nucleul celulelor sub formă de lanțuri lungi de acid dezoxyribonucleic (ADN). În natură ADN este un biopolimer format dintr-o înlănțuire de patru molecule, nucleolidele: adenina (A). citozina (C), guanina (G) și timina(T). Adică putem spune că ADN e reprezentat de lanțuri de patru caractere ACGT. Mulțimea de cromozomi a unui organism formeaza genomul. De exemplu genomul uman conține între trei și cinci miliarde de nucleotide. Acidul ribonucleic (ARN) copie din ADN informația despre structura proteinelor, care la nivel de ribozomi se traduce în lanțuri de aminoacizi formând proteinele și enzimele (traducerea se face, urmând regulile codului genetic). În generat, se consideră că mulțimea de proteine formează genotipul. Proteinele și enzimele dictează structura și comportamentul celulei. Aceste siructuri și comportamente permit indiviziior să-și reatizeze sarcinile în mediul său, să supraviețuiască și să se reproducă în proporții diferite. Cromozomii progeniturilor (urmașilor) sunt formați dintr-un lanț de nucleotide ce provin de la părinții lor în așa fel ca să păstreze genii cei pot îndrepta spre performanțe “mai superioare” (de fapt mai bine adaptate) în generațiile viitoare. Ocazionat, în procesul naturat, mutațiile genetice introduc de asemenea variații în cromozomi.

Variațiile influiențează comportamentul și reproducerea indivizilor. Individul mai bine adaptat, adică mai capabil să efectueze sarcinile necesare pentru supraviețuire se reproduce în proporții mai mari. Indivizii mai puțin adaptați se reproduc în proporții mai mici. Peste o perioadă de timp și mai multe generații, o populație constă din indivizi mai bine adaptați pentru a supraviețui. Structura și comportamentul indivizilor se schimbă în timp din cauza selecției naturate. Când schimbările sunt însemnate se spune că populația evoluează.

1.4.2. Noțiune de algoritm genetic

Algoritmul genetic rezolvă probleme pe calea aplicării principiilor teoriei evoluției firești(naturale) a organismelor vii. Mediul programului imită natura, permițând submulțimii de a avea organisme mult mai adaptate la viață și înmulțirea pe contul organismlor mai slabe. În locul organismelor adevărate populația programului constă din soluții genetic codate. O soluție mai bună crează o altă soluție puțin diferită de precedenta, pe când cele mult mai slabe “mor” și sunt înlocuite cu urmașii soluțiilor rămase în viață.

La fel ca în natură, urmașii celor “rămași în viață” seamănă cu precedenții și deseori moștenesc prioritățile lor, iar existența de mai departe și-o bazează anume pe ele. După apariția fiecărei generații, selecția naturală devine din ce în ce mai aspră, dură. Indivizii primiți în rezultatul a astfel de selecție devin din ce în ce mai puternici.

Algoritmii genetici permite următoarele priorități , unice în felul lor, de întrebuințare a modelului genetic:

Sistemul de moștenire este destul de flexibil. Aceasta dă posibilitate de a întrebuința codul predestinat unui anume scop, în alte scopuri. Marea parte a prelucrării datelor și logicii poate fi aplicată pentru orice problemă. Înr-adevăr, dacă au apărut complicații, limitele problemei deseori pot fi modificate, cu atât mai mult că nu este nevoie de a porni din nou procesul de evoluție.

Dacă succesiunea dată seîntrerupe sau durata ei de lucru este necunoscută,atunci pentru rezolvarea acestor problemesunt o mulțime de metode. Din când în când putem aprecia populația pentru o mai bună căutare a generației actuale.

Procesele evoluției se reglează foarte bine în sisteme paralele mari. Cu cât populația este mai mare, cu atât mai repede ea se dezvoltă. Submulțimile indivizilor se pot dezvolta independent unele de altele, apoi ele se împart, se dublează și, cu foarte puține restricții, se unesc din nou.

Soluțiile primite pot fi foarte deosebite de cele așteptate. Pot exista o mulțime de soluții de bază și, câteodată,pentru a le găsi, se face o căutare la întâmplare. Când programul găsește soluția cea mai bună, absoluț nouă, atunciaceasta duce la metode evoluționiste noi. Cu ajutorul algoritmilor genetici se modelează foarte bine procesele creatorii în care sunt folosite etapele asemănătoare, întrebuințarea rezultatului repetat, calificativele și îmbunătățirea lui (în terminologia evoluționistă ele se numesc mutație, recombinare și selecție).

Mai jos este dată lista termenilor, care deseori sunt întâlniți în structuri și algoritmi genetici.

Genă – secțiune a codului gentic, care oferă unicul parametru pentru soluția potențială.

Alelă – caracteristica ce se conține în genă

Cromozom- complet de gene care sunt deajuns pentru descrierea completă a posibilelor soluții pentru program. Arată un singur punct în domeniul soluțiilor.

Genom – toți cromoyomii organismului individual

Genotip – valoarea genomului

Domeniul soluțiilor – este asemănător cu domeniul problemei însă dată de parametrii soluțiilor și nu a problemei. Orice punct în domeniul soluțiilor prezintă o soluție admisibilă, dar mai întâi de toate – o soluție relativ optimală a problemei date.

1.4.3. Termeni biologici

Toate organismele vii sunt alcătuite din celule. În nucleul fiecărei celule există aceeași mulțime de cromozomi . Cromozomii sunt șiruri de AND și servesc ca model pentru întreg organism. Un cromozom este alcătuit din gene, care sunt fragmente de AND. Fiecare genă codifică o caracteristică (spre exemplu culoarea ochilor). Gena are o poziție fixă în cromozom. Acceastă poziție se numește locus.

Întregul material genetic (toți cromozomii) poartă numele de genom.

În timpul reproducerii în primul apare încrucișarea (engl. crossover). Aceasta înseamnă că gene din doi părinți (doi cromozomi) formează într-un fel un nou cromozom. Acesta la rândul său poate fi schimbat. Schimbarea sau mutația (engl. mutation) înseamnă căelementele din cromozom au fost modificate. Mutația apare de obicei din cauza erorii copierii de gene de la părinți.

Într-o pupulație de indivizi variabilitatea este inevitabilă. Ea induce în rezultat diferențe în capacitățile de supraviețuire a îndivizilor. În practică, capacitatea de autoreproducere a unei populații este o condiție necesară pentru demararea unui proces evolutiv. John Holland în cartea sa “Adaptarea în sisteme naturate și artificiate”, editată în 1975 a propus un cadru generat pentru sistemele adaptive și a arătat cum procesul de evoluție poate fi aplicat în sistemele atificiate. Toate problemele de adaptare pot să se definească în termeni genetici și să se rezolve cu ceea ce acum se numește atgoritmul genetic.

Dar mai întâi să explicăm unii termeni împrumutați din genetică. Cromozomii sunt elementelele, pornind de la care sunt elaborate soluluțiile. Populația este o mulțime de cromozomi. Populațiile sunt numite și generații. Reproducerea este faza de combinare a cromozomilor. Mutația și încrucișarea sunt metode de reproducere.

Alte noțiuni sunt proprii domeniului atgoritmilor genetici. Gradul de adaptare sau indicele de catitate numit de asemenea și indicele de performanță, este o metodă abstractă ce permite sortarea cromozomilor în ordine descrescătoare a calității de a fi soluție a problemei. De exemplu, să ne imaginăm că se caută minimul parabolei f(x)=x2 și că -1.0 și 2 sunt candidații la soluție. Atgoritmul genetic va evalua fîecare candidat la rolul de minimum și îi va sorta în ordinea descreșterii performanței. 0 apare drept cel mai bun candidat. El atinge cel mai mare indice (acesta de fapt este și minimul teoretic, dar algoritmii geneticii pot ignora acest fapt). Dacă din careva motive 0 nu este candidat, atunci –1 va fi următorul candidat. El va atinge un indice mai puțin bun decât 0, dar mai bun decât 2.

Precum s-a menționat, atgoritmul genetic simulează procesul evolutiv Darwinian. Evident că el este un proces paralel. El poate transforma un ansamblu de obiecte matematice, unde obiectele (indivizii) deseori sunt reprezentate de secvențe de caractere, imitând, astfel, lanțurile de ADN, fiecare secvență având un grad de adaptare. Atgoritmul constă din patru module: evaluarea în care se stabilește gradul de adaptare at fiecărui individ; populația în care se stabilesc metodele de menținere a populatici curente; reproducerea în care indivizii unei generaiii sunt selectați (pentru a obține generația imediat următoare), apoi încrucișați după care bagajul genetic al noilor indivizi este schimbat; și mutația în care bagajul genetic este modificat. Toate aceste module se bazează pe hazard.

1.5. Algoritmul general

Soluția pentru o problemă prin algoritmii genetici evoluiază. Algoritmul începe cu o mulțime de soluții (fiecare soluție este reprezentată de către un cromozom) numită populație. Soluțiile dintr-o populație sunt luate și folosite pentru a forma o nouă populație. Acest lucru este motivat de faptul că noua populație ar pute fi maibună decâtcea veche.combinarea soluțiilor se face prin crssover și mutation. Prin crossoverdoi cromozomi sunt desfăcuți și combinațipentrua forma alți doi noi cromozomi numiți și urmași (engl. offspring). Fiecare cromozom are atașată o valoare numită speranță de viață (engl. fitness). Cu cât fitness-ul unui cromozom este mai mare, cu atât șansa ca acesta să supraviețuiască în populația umătoare este mai mare. Totodată, la încrucișare, cea mai mare șansă de a fi aleși ca părinți, sunt cromozomii cu fitness-ul cel mai mare.

Algoritmul de mai sus este repetat până când o condiție este satisfăcută. Condiția poate fi executarea de un număr de ori a ciclului, îmbunătățirea soluției cu un anumit grad etc.

Algoritmul genetic poate fi implementat, aplicând următorii pași.

1.[Start] Se creează populația inițiala de cromozomi. Se generează aleator o populație de n cromozomi (care reprezintă soluțiile posibile pentru problemă);

2.[Adaptarea] Se evaluează fiecare cromozom, se determină gradule de adaptare, se calculează fitness-ului fiecărui cromozom;

3.[Populație nouă] Se crează populația nouă pe baza celei vechi. Următorii pași se repetă până când noua populație este completată:

3.1.[Selecția] Se selectează doi părinți din populație în acord cu gradele de adaptare.

3.2.[Încrucișarea](Crossover) Se încrucișează cei doi cromozomi pentru a forma doi cromozomi noi;

3.3.[Mutația] Se obțin noi cromozomi modificați prin mutație

3.4.[Acceptarea] Se introduc cei doi cromozomi noi în populație și se exclud cromozomii vechi.

4. Noua populație formată o va înlocui pe cea veche;

5.[Testarea] Se repetă pasul 3 până este întâlnită o condiție de terminare.

6.[Stop] Cel mai bun cromozom se consideră drept soluție a problemei.

.Dacă se îndeplinește condiția de final , atuncise afișează cel mai bun cromozom din populație și stop;

Acesta este algoritmul de bază, dar el poate fi afectat de mulți parametri precum vom vedea mai jos.

Precum se poate observa,algoritmul de mai sus este foarte general. Pentru fiecare problemă particulară în parte trebuie să se răspundăla următoarele întrebări:

Cum modificăm cromozomii și cum este reprezentată o soluție într-un cromozom?

Cum inițializăm cromozomii? Care este populația inițială? Cât de mare este ea?

Cine este fitness-ul unui cromozom?

Cum selectăm părinții pentru încrucișare?

Cum se face încrucișarea?

Cum se face mutația?

Dacă noua populație este formată numai prin crossover, atunci este posibil să se piardăsoluțiile cele mai bune din actuala populație. Cum evităm acest lucru?

Cât de des apare mutația? Dacă apare prea des , ar însemna că facem o căutare aleatoare în spațiul soluțiilor.

Când se termină algoritmul?

1.5.1. Genetică

Gena reprezintă structura fundamentală a datelor genetice. Gena este pur și simplu o parte a codului genetic care oferă unicul parametru pentru soluția potențială. Genele pot avea mărimi diferite, dar deobicei au lungimea nu mai mare de 1 bit.

Sfat: în codul genetic trebuie să se prezinte doar parametrii soluției. Alte variabile, inclusiv și parametrii domeniului problemei, nu trebuiesc prezentați.

Pentru prezentarea alelelor în gene poate fi întrebuințată orice schemă. Mai generală este întrebuințarea codului dublu Gray, deoarece operatorii evoluționiști care sunt destinați anume mutației, par a fi mai efectivi în codul Gray decât în codurile consecutive. Codul Gray, numit în cinstea lui Frank Gray, prezintă orice sisteme numerice reglamentate, în care toate cifreleîntregi vecine se deosebesc strict cu o cifră. O astfel de prezentare este utilă în aplicările genetice, deoarece schimbările mici, spre exemplu, la mutație, de obicei sunt destinate pentru primirea unor schimbări mici în soluție. În tabelul 1.1 sunt aduse exemple ale codului Gray cu 3 biți, spre deosebire de succesiunea standardă.

Tabelul 1.1.

Codul Gray cu 3 biți

Deși codul Gray are multe calități interesante, cea mai atrăgătoare pentru sistemele genetice este apropierea lor numerică. Pentru a reduce la minim efectele întâmplătoare nedorite, este nevoie de a susține soluțiile schimbătoare apropiate una alteia. Schimbările mari sunt mai puțin dorite decât niște schimbări numerice mici.

Transformarea directă și inversă a codurilor Gray simple este evidentă (listingul 1.1).

unsigned int bin_to_Gray(unsigned int n)

{

return n ^ (n >> 1);

}

unsigned int Gray_to_bin(unsigned int n)

{

int i;

for(i=0; (1 << i) < sizeof(n) * CHAR_BIT;i++)

{

n ^=n >> (1 << i);

}

return n;

}

Listingul 1.5.1.1. Transformarea codului Gray în prezentarea dublă simplă.

Genele în cromozomi sunt grupate. Cromozomul conține o cantitate suficientă de gene pentru descrierea deplină a soluției și a calificativului independent din p.d.v. a foloslui soluției. În majoritate cazurilor, orice populație aparte conține numai un singur cromozom. Cromozomii secundari pot fi utilizați pentru păstrarea posibilităților ce nu sunt încă utilizate și a altor date care nu țin direct de problemă. Structurile cromozomilor se pot distinge considerabil. Plați, de mărime constantă, unidimensionali, masive de biți sau simbolice – acestea sunt cele mai simple structuri cromozomiale, în plus ele sunt bune pentru majoritatea aplicațiilor. Cromozomii puțin mai complicați pot fi construiți cu ajutorul masivelor multidimensionale, a arborilor și chir a hash-tabelelor. Astfel de structuri sunt predestinate, de obicei, pentru conducere, dacă ele reflectă mai bine domeniul soluțiilor.

Totalitatea cromozomilor indivizilor alcătuiește genomul organismului. Genomii folosesc liber structuri foarte simple, foarte compuse, sau ceva intermediar pentru organizarea cromozomilor pe care-i conțin. Natura utilizează o metodă foarte bună și simplă: leagă totul împreună într-un masiv lung (sau două masive duble pentru ADN). Cum să determinăm ce trebuie pentru organizarea datelor genetice? În primul rând trebuie să examinăm operațiile, care trebuiesc neapărat îndeplinite. Genomul se copie, se combină cu alți genomi, are loc mutația, împreunarea ți își apreciază starea pentru a vedea cât de bine este rezolvată problema dată. Este posibil ca genomul să nu trbuiască căutat sau demonstrat. Este necesar de a cerceta datele pe care le va păstra genomul. Ele sunt distincte pentru diferite realizări și scopuri. Câteodată codarea particulară (amănunțită) nu este tocmai bună pentru anumite structuri. Însă altădată, un număr întrg scalar este deajuns pentru codarea întregului genom. Pentru o eficiență mai mare, fiecare genă, fiecare cromozom și fiecare genom trbuie să fie prelucrate în așa mod, ca fiecare ordine și poziție posibilă să stea într-un punct unic al domeniului soluțiilor și nu în oarecare altul. Lichidarea intenționată a “soluțiilor incorecte” din domeniul soluțiilor, deasemenea poate simplifica simțitor îndeplinirea sarcinii. Dacă valoarea X poate fi optimală numai în diapazonul de la 0 la 10, atunci nu trebuie să dăm nun diapazon de la 0 la 100. Pentru aceasta, bineînțeles, trebuie să fim siguri că-l știm bine pe X, deoarece, întâmplător putem să excludem unele soluții bune, însă neevidente. Punctul terminus al revizuirii este procesul evoluționist. Trebuie să ne convingem că structura genetică în procesul de evoluție poate fi recombinată foarte efectiv. Cromozomii precedenți trebuie să moștenească cât mai multe priorități de la părinții săi. Dacă structura genetică face asta cu mare greu sau deloc, atunci algoritmii genetici foarte ușor emită degradarea și încep rătăcirea întâmplătoare în domeniul de soluții. În unele cazuri, însăși problema face nedorită moștenirea genetică. La apariția a astfel de probleme, calea dată nu ne permite de a obține soluția totală.

1.5.2. Analiza teoretică a atgoritmilor genetici

De ce algoritmii genetici funcționează? Care sunt fundamentele lor teoretice? Există criterii de convergență? Iată doar unele întrebări ce pot apărea în urma lecturii secțiunilor de mai sus.

Este evident că algortmii genetici preziintă efectiv mai multe calități remarcabile

O eficacitate excepțională (verificată de multiple aplicații practice ca optimizarea numerică. Învățarea automată. etc.)

O mare robustețe

Un model valid atât pentru problemele de optimizare numerică (maximizarea funcțiilor) cât și de optimizare combinatorică (de exemplu, problema comis-voiajorului)

O implimentare simplă

Un proces paralel intrasec

Această listă este departe de a fi exhaustivă și deci ramânem la aceeași întrebare: De ce aceasta este posibil ?

Un timp, algoritmii genetici se utilizau larg fără ca un studiu aprofundat să vină să vizitaze funcționarea lor. Pînă nu demull doar rezultatele permiteau din punct de vedere statistic, studierea comportamentelor lor. Efectiv, atgoritmii genetici se prezintă sub o formă dificilă de analizat, cu excepția din punct de vedere a complexității atgoritmice. Să notăm că timpul de calcul este proporțional mărimii populației. Dar această tratare nu poate răspunde la întrebarea în ce privește, de exemplu, problema convergenței.

Scopul acestei secțiuni este întroducerea unor elemente de bază asupra formalizării matematice a algoritmilor genetici și funcționării lor. Aceasta nu este decât o abordare simplă a unui domeniu pasionat , în care multe întrebări încă rămân deschise.

Să intrăm acum în esența problemei. Atgoritmii genetici se ocupă de o populație de indivizi care sunt elementele unui spațiu de căutare (în sens matematic). Adaptarea fiecărui individ este apreciată de o funcție de adaptare. Mecanismul de reproducere și operatorii genetici permit de a tinde spre o populație ai cărei indivizi maximizează această funcție. Aceasta este de fapt ceea ce trebuie de verifîcat.

Pentru a studia în mod formal acest fenomen, primul lucru ce trebuie făcut este ridicarea metaforei biologice ce acoperă algoritmii genetici. Teoria schemelor este primul pas de studiu în relația algoritmilor genetici cu procesele stocastice. Aceasta esle baza teoretică pentru a răspunde la întrebarea fundamentală de convergență.

În practică, precum s-a vizut, operatorii de încrucișare și mutație, ca și metodele de selecție, sunt foarte variate. Analiza algoritmilor genetici este deci o problemă complexă. Ne vom limita în studiul nostru la cazul secvențelor de biți. În plus, ne vom limita la încrucișrea într-un punct și mutația uniformă. Algoritmul genetic astfel definit este canonic.

1.5.3. Teoria schemelor

Teoria schemelor ne asigură un cadru util pentru determinarea proprietăților interesante ale algoritmilor genetici. Vom aduce la început unele definiții necesare pentru construirea raționamentelor.

Vom numi x secvența de lungimea l(x) un șir x=a1a2..al, unde aiV={0,1}. De exemplu, x=0111011. Aici V este alfabetul binar.

În practică, secvențele de biți utilizate sunt de lungime fixă. Spațiul de căutare (mulțimea tuturor secvențelor de o lungime dată) este de cardinalitate finită. O secvență este deci un șir finit de biți.

Vom defini un alfabet auxiliar V*={*,0,1}. Atunci vom numi schema S de lungime l(S) un șir S=a1a2..al, unde aiV*={*,0,1}. De exemplu, S=*0**1**10.

Biții marcați cu «*» pot fi 0 sau 1. Schema S=10*1, de exemplu, admite două secvențe 1011 și 1001. Aceste două secvențe se mai numesc instanțe ale schemei S. Deci vom spune că secvența x=a1a2..al este o instanță a schemei S, dacă pentru toți bi* are loc ai=bi.

Vom numi i poziție fixă (poziție liberă) a unei scheme S, dacă ai=1 sau ai=0 (respectiv, ai=*).

Pornind de la aceste definiții, se poate defini ordinea unei scheme S, notată o(S), care corespunde numărului de poziții fixe în S.

Lungime fundamentală a schemei S, notată d(S), este egală cu distanța dintre prima poziție fixă și ultima poziție fixă ale schemei S. De exemplu,

d(**10****)=4-3=1

d(*1**1**0)=8-2=6

Introducem următoarele notații:

Fie P(t) este populația (numărul de secvențe) în generația t

Fie M=|P(t)|, adică mărimea populației

Fie n(S,t) numărul de secvențe din P(t) ce corespund schemei S

Fie Z(S,t)={xjP(t) | xj se potrivește schemei S}, adică Z(S,t) este mulțimea de secvențe din generația t ce se potrivesc cu schema S

Din aceste notații se vede că |Z(S,t)|= n(S,t). În afară de aceasta numărul de secvențe diferite din generația t ce se potrivesc schemei S este n(S,t)=2(l(S)-o(S)).

Vom nota cu fx(t) adaptarea secvenței x în generația t. Atunci se poate defini adaptarea schemei S în generația t egală cu media adaptării secvențelor ce se potrivesc schemei S

Adaptarea medie a populației în momentul de timp t se exprimă prin formula

Acest formalism ne va permite studierea efectelor reproducerii, încrucișării și mutației. Vom face aceasta cu sprijinul calculului probabilităților, deoarece realmente operațiile reproducerii și operatorii de încrucișare și mutație presupun un model probabilistic. Generatoarele de numere aliatoare utilizate în algoritmi ne confirmă acest lucru. Să ne amintim că chiar populația inițială este definită în mod aliator.

1.6. Codificarea cromozomilor

Există multe variantede codificare, totul depinzând numai de problema pe care dorim s-o rezolvăm. Trebuie avută mare grijă în această etapă, deoarece o codificare bună poate duce la o implementare ușoară a operațiilor de încrucișare și mutație. Exemple:

Codificarea binară

Fiecare cromozom este reprezentat ca un șir de 1și 0:

Tab.1.2

Odificarea binară

Problema clasică care folosește acest tip de codare este problema rucsacului: se dau N obiecte și se cere să se umple cât mai mult rucsacul de capacitate C . Aici fiecare obiect este codificat cu 1 dacă este în sac și cu 0 dacă nu este.

Codificare sub formă de permutare

Fiecare cromozom este reprezentat sub forma unei permutări:

Tab. 1.3

Codificare sub formă de permutare

Această codificare se folosește în cazul problemei comis-voiajorului. O permutare reprezintă ordinea în care comis-voiajorul vizitează orașele.

Codificare sub formă de valori

Fiecare cromozom este un șir de valori:

Tab.1.4

Codificare sub formă de valori

1.6.1. Populația inițială

Populația este o mulțime de cromozomi care trebuie să fie suficient de mare pentru a se putea realiza un număr mulțumitor de combinații între cromozomii componenți, dar nu prea mare, deoarece acest lucru va înceteni lucrul.

Populația inițială este una aleatoare. Spre exemplu, pentru determinarea unui drum hamiltonian de cost minim se poate începe cu generarea aleatoare a câtorva permutări. Pentru determinarea unei componente intern stabile maximale se poate începe cu generarea aleatoare a câtorva componente intern stabile. Acestea pot fi formate și doar dintr-un singur nod.

De obicei, populația inițială este aleatoare. Dar pentru o mai bună performanță, o parte din cromozomi ar putea fi generați prin metode euristice. În acest fel, s-ar putea ajunge la soluție mai repede.

1.6.2. Fitness-ul unui cromozom

Fitness-ul unui cromozom este speranța lui de viață. Pe noi ne interesează să obținem cromozomi cu fitness-ul cât mai mare, sau cât mai mic, în orice caz, cu un fitness la o extremă.

În cazul problemei determinării unei componente intern stabile maximale, fitness-ul unui cromozom este cardinalul mulțimii de noduri pe care o codifică acel cromozom. Aici ne interesează să obținem un fitness cât mai mare.

În cazul problemei problemei comis-voiajorului, fitness-ul este lungimea drumului codificat de respectivul cromozom. Aici ne interesează să obținem un cromozom cu un fitness cât mai mic.

În cele ce urmează presupunem că dorim să realizăm cromozomi cu fitness-ul cât mai mare.

1.6.3. Selectarea cromozomilor părinți

Cromozomii sunt selectați din populație pentru a fi părinți într-o încrucișare. Conform teoriei lui Darwin, cei mai buni părinți supraviețuiesc și se înmulțesc creând noi urmași.

Dintre metodele cel mai des întâlnite de selecție sunt:

1.6.3.1. Selecție aleatoare

Doi părinți sunt aleși aleator din populație. Acest lucru se face generând două numere aleatoare între 1 și dimensiunea populației.

1.6.3.2. Selecția cu ajutorul ruletei

Părinții sunt selectați în conformitate cu fitness-ul lor. Cu cât sunt mai buni, cu atât șansa lor de a fi aleși este mai mare. Să ne imaginăm o ruletă în care sunt dispuși toți cromozomii din populație. Fiecărui cromozom îi corespunde un sector al ruletei, direct proporțional, ca mărime, cu fitness-ul cromozomului respectiv. În acest fel cromozomii cu fitnes mai mare au atașate sectoare mai mari, iar cei cu fitness mai mic au atașate sectoare mai mici. La aruncarea bilei pe ruletă există mai multe șanse de alegere pentru cromozomii cu fitness mai mare.

Stimularea roții de ruletă se face în felul următor:

se calculează suma tuturor fitness-urilor cromozomilor. Fie aceasta S.

Se genereză un număr aleator între 1 și S. Fie acesta r.

Parcurgem populația și calculăm suma fitness-urilor cromozomilor până ajungem la valoarea r. Acel cromozom îl alegem.

1.5.3.3. Selecția aranjată

Selecția anterioară nu este recomandată în cazul în care fitness-urile cromozomilor diferă foarte mult. De exemplu, dacă unul din cromozomi are fitness-ul de 100 de ori mai mare decât suma fitness-urilor celorlalți cromozomi este clar care sunt șanselecromozomilor cu fitness mic de a fi aleși. Apoi se renumerotează cu numere întregi din intervalul [1,…,dimensiunea populației]. Cromozomulcel mai mic are număril 1 etc., iar cel mai maire (cu fitness-ul cel mai mare) are numărul egal cu fâdimensiunea populației. Aceste numere sunt considerate fitness-uri și pe ele se aplică selecția roții de ruletă. Observăm că cormozomii cu fitness mai mare au tot cele mai mari șanse de a fi aleși, dar de data aceasta nu mai sunt atât de mari în comparație cu șansele celorlalți.

1.6.3.4. Selecție cu starea consolidată

Aceasta nu este o metodă particulară. Ideea esențială este că cromozomii nou generați vor înlocui, dacă sunt mai buni, o parte din cromozomii vechii populații. În acest caz numai este necesar să se lucreze cu mai multe populații deodată, ci doar cu una singură.

1.6.3.5. Elitism

Când creăm o nouă populație prin încrucișare și mutații, există o șansă mare de a pierde cei mai buni cromozomi. De aceea ar trebui să copiem cei mai mulți cromozomi în noua populație, fără să schimbăm nimic la ei. Elitismul va crește repede performanțele algoritmilor genetici.

Ne vom interesa mai întâi de operația reproducerea, sau mai degrabă de selecție. Indivizii care au o adaptare mai mare au mai multe șanse de a se reproduce. Pentru a pune în lucru acest sistem, majoritatea implementărilor fac referință la ruleta de cazino. Avem de fapt de afacere cu o variabilă aliatoare discretă, numită și variabilă de alternativă generalizată.

Aceste realizări furnizează indivizi aleși, iar densitatea lor depinde și e catracterizată de funcția de adaptare a fiecărei secvențe.

Probabilitatea că secvența xj din populația P(t) va fi selectată pentru reproducere este

iar probabilitatea selectării din generația t a unei secvențe xj ce se potrivește cu schema S este

Atunci

va fi numărul de secvențe din generația t+1 ce se potrivesc schemei S.

Formula de mai sus poate fi transformată în

Atunci

Astfel numărul de secvențe ce se potrivesc unei scheme date crește (se micșorează) de la o generație la alta proporțional cu . Presupunem că fS(t)>fMed(t), de exemplu fS(t)=(1+)fMed(t), unde >0. Atunci

.

Din aceste formule se poate trage concluzia că dacă o schemă S dispune de o bună adaptare fS(t), atunci numărul de secvențe în generația următoare ce corespunde schemei S crește. Să din contra, schema eșuează dacă toate schimbările dispar

1.7. Încrucișarea (crossover)

Primul operator elaborat pentru atgoritmii genetici a fost încrucișarea într-un punct. Pe parcurs au fost propuși și alți operatori. de asemenea au fost elaborați și operatori pentru rezolvarea unor probleme specifice.

Încrucișarea într-un punct. Acest operator ia doi parinti și creează doi copii (fig.1.3.). El lucrează astfel (a se ignora biții italici):

Tab.1.5

Încrucișarea într-un punct

Sunt selectați doi părinți

Prin randomizare se ia un punct de încrucișare (în fig.1 e notat prin linie segmentată)

Copilul l este creat prin concatenarea genelor din partea stângă a punctului de încrucișare a părintetui 1 cu partea dreaptă a părintelui 2

Copilul 2 este creat prin concatenarea genelor din partea dreaptă a punctului de încrucișare a părintelui 1 cu partea stângă a părintelui 2

Încrucișarea în două puncte. Acest operator de încrucișare este similar celui cu un punct de încrucișare numai că sunt selectate două puncte. E posibilă și încrucișarea în n puncte. Se poate considera, de exemplu, soluția în care biții italici urmează unul după altul. În realitate, pentru a obține soluții potrivite se utilizează o schemă. Aceasta nu se poate atinge dacă se utilizează doar încrucișarea într-un punct.

Încrucișarea uniformă. Pentru orice poziție a biților a doi copii se poate determina, aliator, care doi parinți au putut contribui la creșterea acestor copii. Algoritmul poate fi reprezentat astfel:

Tab.1.6.

Încrucișarea uniformă

Sunt selectați doi părinți.

Este creat modelul ce constă din biți formați aliator

Copilul 1 obține biții de la parintete 1 indicați cu unu în model și biții de la

părintele 2 indicați cu zero în model .

Copilul 2 obține biții de la părintele 1 indicați cu zero în model și biții de la părintele 2 indicați cu unu în model.

Încrucișarea ordonată. Nu pentru toate problemele mododele de încrucișare de mai sus pot aduce soluția. Fie de exemplu problema comis-voiajorului. Pentru această problemă cromozomii se reprezintă ca o secvență de orașe. Dacă se utilizează încrucișarea într-un punct, atunci soluția se poate pierde (ceea ce deseori se întâmplă cu acest operator) deoarece pot apărea orașe duplicate sau pot dispărea orașe în general.

Sunt două metode de depășire a acestui neajuns. Una ține de implementarea funcției de reparației care ia o soluție potențială și o examinează. Dacă se determină că soluția este ilegală, atunci se repară și se examinează din nou. Evident că funcția de reparatiție depinde de problema considerată.

Altă metodă presupune elaborarea unor operatori ce nu produc soluții ilegale. Aceasta se poate de facut utilizând informația din domeniul de interes, dar se pot etabora și operatori ce lucrează pentru toate problemele.

Încrucișarea ordonată. asigură că în cazul problemei comis-voiajorului nici un oraș nu va avea duplicate sau va dispărea. Ea lucrează astfel:

Tab1.7.

Încrucișarea ordonată

Sunt selectați doi părinți

Este creat modelul ce constă din biți formați aliator

Copilul 1 se completează cu biții de la părintele 1 indicați cu unu în model. Astfel, copilul 1 poate fi parțial complelat, rămânând unele goluri.

Se formează o listă de gene ale părintelui 1 ce corespund zerourilor din model.

Se sortează acaste gene ca să apară în aceeași ordine ca și în părintele 2.

Se completează copilul 1 cu gene din lista sortată.

Copilul 2 se crește în mod similar.

Încrucișarea depinde de tipul de codificare a cromozomilor și de problema particulară pe care o rezolvăm. Să luăm câtrva exemple:

1.7.1. Codificare binară

a) Inversarea biților

Biții selectați sunt înversați din în 1 în 0 și invers.

1100100110001001

b) Interschimbarea biților

Se aleg doi biți și se schimbă valorile între ei.

1100100110001101

încrucișare într-un singur punct

Un punct punct de încrucișare este ales. Din primul părinte este copiată secven’a de la început până la punctul de încrucișare, iar din al doilea părinte este copiatăsecvența de la punctul de încrucișare până la final.

11001011 + 11011111 = 11001111

încrucișarea în două puncte:

Sunt alese două puncte de încrucișare. Secvența dintre cele două puncte aleasă dintr-unul din părinți, iar ceea ce a rămas din celălalt părinte:

11001011 + 11011111 = 11011111

încrucișarea uniformă

Biții sunt copiați aleator din primul și al doilea părinte:

11001011 + 11011101 = 11011111

încrucișarea aritmetică

Operații aritmetice sunt efectuate pentru a crea noii urmași:

11001011 + 11011111 = 11001001(AND)

1.7.2 Codificarea sub formă de permutare

Metodele folosite aici sunt asemănătoare cu cele de la codificarea binară. Trebuie de avut grijă să se păstreze consistența prmutării, adică să nu apară un număr de două ori, iar altele nici o dată.

a)Transpoziție

Este efectuată o transpoziție asupra permutării respective. Acest lucru este echivalent cu interschimbarea biților de la codificarea binară.

(1 2 3 4 5 6 8 9 7) => (1 8 3 4 5 6 2 9 7)

1.7.3 Codificarea sub formă de valoare:

Metodele de la codificarea binară pot fi întrebuițate și aici.

Considerăm acum efectul de încrucișare.

Precum s-a spus mai sus, aici vom considera încrucișarea într-un punct. În condițiile ei vom studia probabilitatea de supraviețuire a unei scheme S din momentul încrucișării. Este imposibil de determinat probabilitatea în mod direct, adică probabilitatea că la sfârșitul încrucișării o secvență ce se potrivește cu S continue să rămână o secvență ce se potrivește cu S.

Revenim la definiția de lungime fundamentală care exprimă distanța dintre prima și ultima poziție fixă. De exemplu, pentru schema S=**100** lungimea fundamentală este d(S)=5-3=2. Să remarcăm aici că toate instanțele lui S rămân instanțe ale lui S dacă locul încrucișării nu e mai mare decât 2 și nu e mai mic decât 5. Linia de încrucișare este aleasă în mod aleator conform unei legi uniforme.

Probabilitatea de a pierde un membru al populației ce se potrivește schemei S este aproximativ egală cu . Probabilitatea de încrucișare (în practică procentul de încrucișare se indică de utilizator) o notăm pc. Atunci probabilitatea pS de supraviețuire a unei scheme S va fi .

Luând în considerație încrucișarea, numărul secvențelor în următoarea generație ce se potrivesc cu schema S este

Observații

Probabilitatea de încrucișare indică cât de des trebuie să apară această operație într-o populație. De obicei are valoarea mare, cuprinsă între 60% și 90%.

Metodele de încrucișare prezentate mai sus, sunt destul de generale. De obicei sunt alese metode specifice problemei care se dorește a fi rezolvată și care generează o populație mai bună. Spre exemplu, în cazul problemei componentei stabile maximale se aleg doi cromozomi care codifică două componente stabile. Aceste componente sunt de fapt mulțimi, reprezentate ca un șir de biți. În acest caz se poate stabili, de exemplu, încrucișarea cu un singur punct, sau cu două puncte, dar s-ar putea ca în acest caz componentele nou formate să fie mai mici decât părinții lor. Deaceea putem lua unul din părinți și îi vom adăuga noduri din al doilea părinte, rezultând în acest fel un cromozom cu fitness-ul mai mare sau egal cu al unuia dintre părinți. Este repetată aceeași operație și pentru celălalt părinte. Acest tip de încrucișare se numește încrucișarea inteligentă.

1.8. Operația mutație

Dacă se utilizează încrucișarea într-un punct, atunci se pot obține tot mai buni și mai buni cromozomi. Dar poate să se întâmple că ambii părinți (sau mai rău – toată populația) au aceeași valoare în anumită poziție atunci nu se mai schimbă nimic. Mutația este procedura ce poate înfrunta această problemă și aduce o diversitate în populație.

Cea mai obișnuită cale de implementare a mutației constă în selectarea unui bit pentru schimbarea valorii sale în mod aliator. Notăm că bitul se poate schimba în aceeași valoare. Alte metode pot schimba părți de cromozomi sau pot fi elaborate mutații specifice domeniului de interes.

Algoritmul genetic are un parametru numit rata mutației. Ea definește cât de des mutația poate fi aplicată. 0 valoare tipică este 0.008. Adică un cromozom poate fi supus mutației odată la 8000. Spre deosebire – rata încrucișării este de obicei 0.6.

Dar pot fi definite rate ale mutației și încrucișării în mod dinamic. De menționat ca la primii pași ale algoritmului genetic încrucișarea este mai importantă, iar la ultimii pași ale algoritmului mai importantă este mutația. Ținând cont de acest fenomen, pe parcur ratele pot fi schimbate.

În legătură cu faptul că materialul genetic înoit nu se amestecă nici acum, nici mai târziu, populația într-adevăr poate suferi din cauza stagnării. Treptat, populația se completează cu o mulțime de genotipi foarte simpli. Menținerea unei anumite relații între câteva populații și mulțimea indivizilor, micșoreză stagnarea, însă aceasta nu este o soluție comună suficientă. Deriva genetică a populației ajunge la stagnare, deoarece, în organisme, din generație în generație, se amestecă unele și aceleași aranjări de gene. Chiar și selecția naturală poate duce la stagnare, întrucât cele mai adaptate organisme au scopul de a le înlocui pe cele ma puțin adaptate. În condiții extremale, de exemplu, când doar un mic procent al populației supraviețuiește și generează fiecare populație, aceasta poate duce la un caracter unitar și va rămâne numai un singur genotip superior.

Operațiile mutație sunt predestinate pentr oprirea populației de la stagnare, adăugând cu atenție careva elemente întâmplătoare în unii cromozomi. Uneori, când are loc deriva genetică sau selecția naturală, alelele critice, necesare pentru a primi organisme mai puternice. Mutația dă posibilitate populației să experimentezecu alelele întrgi, în loc ca pur și simplu să încerce să creeze mai multe combinații de alele din genotipii existenți.

Să tratăm acum efectul mutației.

Fie schema S. Modificarea unei poziții fixe de către mutație distruge schema S. Notăm prin pm probabilitatea mutației unui bit (se propune de utilizator) în secvența dată. Probabilitatea că un bit dat nu-și schimba valoarea este (1-pm). Atunci probabilitatea că o secvență de ordinul o(S) nu va pierde vre-un membru (va supraviețui) în urma mutației este (1-pm)o(S) care aproximativ este egală cu 1-pmo(S) în cazul când pm<<1, condiție respectată în practică (în general, pm<0.1). Atunci, luând în considerație mutația, obținem rezultatul final

Concluzia generală ce poate fi făcută din această formulă e cunoscută sub numele Teorema schemelor: schemele de lungime fundamentală și ordine mai mici decât altele sunt favorizate în generarea unei noi populații.

Acest rezultat teoretic are o evidentă aplicare practică. Concluzia de mai sus poate fi folosită la ameliorarea alegerii indivizilor. Este preferabil de ales secvențe de ordini și lungime fundamentală redusă. Așadar cunoașterea apriori a formei soluției poate fi luată în socoteală, ca o euristică, in alegerea reprezentanților populației.

Avertizare

Mutațiile trebuiesc făcute

înlimitele cerute. Prea multe mutații înlătură prioritățile primite în urma evoluției și moștenirii. Mutațiile sunt, am putea spune, otravă pentru algritmii genetici doar dacă ele nu sunt în doze mici.

Mutația apare în principal pentru a evita căderea soluțiilor problemei într-un optim local. Efectuarea de prea multe ori a acestei operații va transforma algoritmul într-o căutare aleatoare în spațiul soluțiilor posibile. Deaceea probabilitatea de mutație trebuie să fie mică, circa 0.5%.

1.9. Recombinarea

Recombinarea este procesul întemeierii unei noi generații dintr-o generație veche. Există o mulțime de posibilități care ne permit acest lucru. Unica cerință este aceea că trebuie trbuie să se construiască noi cromozomi și că în cromozomii precedenți se schimbă unele caracteristici moștenite de ei de la părinți.

1.10. Părinți unici

Schimbarea unei alele înăuntrul unuia și aceluiași cromozom are același efect ca și în cazul mutației. Acest fel de recombinare include doar schimbarea poziției genelor alelelor, spre exemplu schimbarea ABC în ACB. Variațiile precedente rar își mențin prioritatea având astfel de moștenire. Tehnologia recominării, care include mai mult decât un singur părinte, este mai efectivă la primirea genotipilor superiori.

1.11. Încrucișarea genelor

Încrucișarea geelor este o tehnologie simplă de recombinare. Copiii iau alelele numai dintr-un cromozom al părintelui, alegându-și întâmplător părintele care va ăntreține următoarea alelă. Genele precedente, în cntinuare redau unu la unu genele părinților (alelele nu-și schimbă poziția), însă combinația prezintă un amestec al alelelor fiecăruia din părinți. De exemplu, combinând în acest fel succesiunile părinților ABC și XYZ, pot fi create opt combinații precedente diferite: ABZ, AYC, AYZ, XBC, XBZ, XYC și două succesiuni părintești originale.

Pentru amestec pot fi puse limite. De exemplu, poate fi cerută ca cea mai mare parte a alelei să vină de la un părinte mai prosper. Dacă vom uni împreună un cromozom puternic și doi slabi, atunci este mai bine să obținem alelele necesare de la un singur părinte puternic decât de la doi slabi. Altă posibilitate este cerința ca fiecare părinte să aducă o cantitate egală de alele.

Încrucișarea genelor este mai efectivă, dacă ea este îndeplinită cu ajutorul genelor relativ independente.

1.11.1. Încrucișarea succesiunilor de gene

Aceasta este o tehnologie mai comună de copiere succesiunilor alelelor mult mai de preț de la fiecare părinte. Punctele de împreunare se aleg pe baza cromozomului precedent și se împart între părinți. ABCDse intersecteză cu WXYZ și în rezultat se obțin opt combinații posibile în dependență de aceeaccare punct de împreunare este ales și care parte i se oferăpărintelui: ABYZ, AXYZ, WXYD, WXCD, WBCD și două sccesiuni originale părintești. Această metodă de recombinare este mult mai stabilă , deoarece caracteristicile trec cu mult mai bine în generația următoare și astfel de urmași în mare măsură seamănă cu părinții lor. Însă încrucișarea succesiunilor lasă mai puține variante decât încrucișarea genelor aparte.

Avertizare

Punctele de împreunare trbuie alese în așa mod, ca ele să fie la granițele genelor. Tăind alelele în două, putem lichida caracteristicile utile.

1.12. Alipirea genelor

Cromozomii precedenți pot moșteni alelele care nu au fost într-un oarecare părinte, însă care se întemeiază (crează) pe calea combinării însăși a alelelor. Pentru alipirea alelelor pot fi folosite câteva operații. Pentru genele care prezintă parametri continui, alipirea lărgește simțitor căutarea soluției optimale.

Observație: alipirea genelor nu se face pentru valori discrete. Dacă combinarea a două alele, pentru obținerea unei alele unicale, nu are sens pentru o genă concretă, atunci trebuie să excludem această genă din proces. Unii cromozomi se perfecționează astfel, încât conțin numai valori discrete și în acest caz alipirea este fără sens (inutilă).

1.13. Selecția

Deoarece orice generație nouă trebuie să conțină genomi care să întreacă genomii analogi din generațiile precedente, cromozomii mai utili trebuie să se introducă mai des decât cei mai puțin utili. O simplă metodă include doar câteva organisme bune și permite celui mai inferior genom să moară. Astfel de selecție o putem numi severă, cu întrebuințarea așa zisei alegeri dure, care ne permite de a ne convinge că organismele inferioare mor întotdeauna, iar cele superioare supraviețuiesc întotdeauna. Selecția o putem face aproximativă cu întrebuințarea “selecției lejere”. În rezultatul acestei selecții, câțiva cromozomi mai prioritari pot să moară, cu speranța că părinții mai slabi neapărat vor avea urmași.

Avertizare: dacă vom permite prea multor genomi să supraviețuiască și să participe la crearea viitoarei generații, atunci aceasta poate duce la o stagnare rapidă.

Fiecare genom-membru al populației trebuie mai întâi clasificat în funcție de folosință. Aceasta ne permite doar de a determina cât de bine satisface scopul fiecare soluție codată genetic. Din necesitatea comparării câtorva candidați între ei, funcția de utilitate trebuie să întoarcă rezultatele precise ale soluțiilor, plus la aceasta să le aranjeze ușor și să le compare unul cu altul. Întotdeauna este mai ușor de lucrat doar cu o variabilă, însă, totuși, unele probleme pot dispărea doar având mai multe variabile. De exemplu, programul care alege cele mai bune locuri de muncă din toate posibile ne va da mai multe variante de lucru bine plătit, pe lângă toate acestea, într-un caz ne va părea mai bun locul unde se află oficiul, iar în al doilea – însăși lucrul. Mai întâi de toate, va fi incomod să avem un program care va lua decizia cum să convertezi toate aceste criterii în unul singur, care se va numi “locul de muncă ideal”. În aceste cazuri funcția de utilitate ia o mulțime de valori, care sunt aproape egale, de exemplu, când un cromozom găsește o muncă bine plătită, iar altul găsește mediul în care este cel mai bine de lucrat. Doar atunci când toate valorile de utilitate sunt valori de ordin superior, putem fără frică să spunem că astfel de cromozom este mai prioritar decât ceilalți.

Elaboratorul trebuie să determine cum să lucreze cu părinții superiori a fiecărei generații. Generația trebuie sau să slujească drept punctuație activă care regenerează complect populația în fiecare ciclu, sau să aleagă indivizii care vor putea supraviețui în generațiile următoare. Aceste strategii se numesc respectiv strategia virgulei și strategia plusului. Lipsa posibilității concurării părintelui cu urmașul său deseori se înscrie ca (părinte, urmaș) ceea ce înseamnă moartea părintelui și înlucuirea lui cu urmașul său, în timp ce (părinte + urmaș) indică alipirea părintelui cu urmașul în aceeași populație în calitate de oponenți egali și perechi potențiale. Strategia plusului de obicei se execută mai bine, însă rezultatele utilizării strategiei virgulă sunt mult mai utile pentru aprecierea eficienței tehnologiei de selecție și recombinare.

Uneori, genele înăuntrul populației se reduc la o singură valoare. Toți sau o mare parte din cromozomi au una și aceeași valoare a genelor și alelelor. Deseori aceasta este foarte util, deoarece indică alelele cele mai bune pentru aceste gene, însă uneori se realizează o optimalitate puternică dar greșită. Mutația întradevăr menține populația în limitele stabilității dorite, însă după aceasta evoluția nu poate continua îmbunătățirea populației prin metode obișnuite. Reproducerea speciei fără pierderea priorităților necesare a stabilității și fără pierderea îmbunătățirii progresive se numește formarea speciilor.

Împărțirea populației în submulțimi în care genele emigrează rar sau deloc, duce la dezvoltarea speciilor. O submulțime își poate pierde vitalitatea, iar alta poate continua evoluția. Producerea întâmplătoare a unuia sau mai multor organisme străine permite de a înfrunta stagnarea și populația se va dezvolta în continuare. Uneori două submulțimi se dezvoltă în două relații diferite și o genă străină, dintr-o submulțime îmbunătățită, se poate înmulți și domina foarte repede pe cele mai slabe, creând pe neașteptate doi indivizi foarte asemănători. Cea mai slabă metodă de prezentare a genelor străine este încrucișarea organismelor străine cu unul sau cel mai stabil locuitor. Aceasta micșorează influența pe care o au noi-veniții.

Speciile pot fi izolate cu ajutorul semenilor, însă nu cu cei din domenii identice. Uneori cromozomii evoluționează foarte repede când se întâlnesc cu o problemă care se deosebește puțin de cea reală. După soluționarea problemei schimbate, de obicei este nevoie de o mică evoluție pentru schimbarea soluției în problema asemănătoare. Astfel de schimbări genetice mici sunt necesare pentru ca mica concretizare din problema schimbată să se moștenească din populația existentă, care lucrează tot timpul la problema de bază pentru mai multe generații.

1.14. Deschiderea “cutiei negre”

Algoritmii genetici se realizează foarte ușor. Intuitiv, ei au sens. Programatorii care înțeleg cum se face aceasta știu, totuși, numai câteva detalii ale teoriei de bază menționate mai sus. Matematica, pe care se bazează algoritmii genetici nu este simplă și este greu de înțeles. Deoarece majoritatea programatorilor au grijă doar de executarea algoritmului pentru a primi un folos maximal și nu se gândesc la o confirmare sau la o înțelegere deplină a principiilor, există o tendință foarte răspândită în rezultatul căreia selectarea soluțiilor se face în mod empiric. Cu alte cuvinte, dacă programul lucrează, atunci rezultatele lui le putem folosi. În principiu, aceasta este just, însă că programul se comportă altfel decât ar trebui, neajunsul înțelegerii depline a algoritmului poate deveni o problemă foarte mare. Analizați funcțiile gfenetice din program ca doar niște funcții experimentale. Faceți în așa fel ca variabilele de determinare să poată fi ușor de schimbat, în plus la aceasta încercați să folosiți diferite strategii. Descrieți masivul de date statistice ca date experimentale. Descrieți starea populației, succesul recombinării, numărul indivizilor unicali, numărul generațiilor și altele. Încercați să descrieți privirile generale și concluziile la fel ca câteva exemple de indivizi apropiați care se supun diferitor operații. Dacă se poate, încercați să faceți din programul Dvs experimental unul interactiv pentru a fi mai ușor de studiat influența fiecărui parametru asupra derulării programului.

Rețineți: este mult mai ușor să primim un lucru concret al unei funcții simple, decât a întregului program. Îndeplinirea corectă a algoritmilor genetici depinde de câteva operații reciproce. Este foarte rău faptul că cauza comportării greșite poate fi găsită doar după cercetarea rezultatului final. Spre exemplu, mesajul “populația mea este foarte haotică ” – nu este o simptomă tocmai corectă. Clarificați pantru ce este elaborată fiecare funcție, mai apoi controlați dacă într-adevăr ea își îndeplinește lucrul său.

Pentru scopurile de dezerminare faceți un cod inițial atât de simplu, cât este posibil. Folosiți identificatori lungi și cu un conținut bogat. Metaforele le veți folosi succesiv. Denumirile de tipul și nu vă vor ajuta atât de mult ca ”părinți ” și “urmași”. Dacă metafora mai mult nu ajută, lăsați-o. Poate vă este mai convenabil să folosiți termenul “ADN” în loc de “genom” – poftim. Dacă vă închipuiți mutația ca o furtună, puteți ușor să redenumiți variabila “mutation-factor” în “inches_of_precipitaton”. În comunitatea științei calculatoarelor, sunt prferate metafore genetice și evoluționiste, însă pot fi folosite și altele. Dacă nu vă este pe plac să întrebuințați așa cuvinte ca “alelă” și “genotip”, nu le întrbuințați. Stăruiți-vă, totuși, să întrebuințați câteva tipuri de metafore, fiindcă aceasta simplifică metoda de atribuire fiecărui element a unui nume unic și nelipsit de sens. Dacă aveți de afacere cu mai multe operații diferite, încercați să-i dați fiecăreia din ele un nume al său, propriu. Nu le enumerați și nu le denumiți, de exemplu, “RepOp27”, deoarece le puteți confunda una cu alta și asta îl va face pe cineva să revadă întregul cod pentru a înțelege însemnătatea acestor operații. Și principalul – întroduceți un număr mare de comentarii pentru lămurirea lucrului care-l faceți, pentru ce-l faceți , bazându-vă des pe metafore.

1.15. Optimizarea

Căutările întâmplătoare sunt destul de încete. Cu cât ele sunt mai întâmplătoare, cu atât mai încet îndeplinesc căutarea. Algoritmii genetici sunt excelența căutării întâmplătoare. Spre marea fericire, algoritmii genetici au câteva calități teobișnuite, care sunt bine adaptate pentruanumite forme de optimizare.

1.15.1. Paralelismul

Algoritmii genetici lucrează bine în paralel. Una din metodele a astfel de lucru se reduce la aceea, ca fiecare proces să dezvolte o submulțime independentă. Periodic, între submulțimi are loc schimbul de genomi, pentru ca prioritățiledescoperite ale unui proces să poată fi folosite pentru accelerarea dezvoltării altui proces. Aceasta crează o mulțime de specii paralele, toate având unul și același scop final.

Există de asemenea metode care permit de a dezvolta paralel unele și aceleași specii. Procesul evoluției care, potențial constă din câteva operații de mutație, recombinare și selecție, poate fi împărțit în lungime, fiecare proces fiind destinat unei singure operații îndeplinită de-a lungul conveerului. Procesul poate fi împărțit și în lățime, adică să se împărțească populațiile în segmente îndependentepentru mulțimea de operații, de exemplu, pentru verificarea mutației și utilității. După aceasta , fiecare generație se unește.

1.15.2. Căutatea operatorilor genetici efectivi

Fiecare problemă și relizare au o aranjare diferită a operatorilor optimali. Uneori, folosirea a doi părinți într-o încrucișare succesivă este o variantă optimă, pe când în alte cazuri este mai bine de întrbuințat mutația căutării extrmului. Testând populațiile cu ajutorul diferitor operații, se poate stabili ce este mai convenabil pentru lucrul asupra problemei date.

Rețineți și faptulcă algoritmii genetici crează optimizatori universali foaret buni. În calitate de alternativă a căutării optimizăriistatistice pentru dezvoltarea strategiei evoluționiste se pot utiliza funcții meta-evoluționiste. Conformitatea strategiei determinată de faptul cât de repede se perfecționează populația. Genotipul prezintă soluția operațiilor accesibile. Acaesta se face tot atât de simplu, cum un bit pentru fiecare genă poate să conecteze și deconecteze operațiile.

1.15.3. Divizarea domeniului problematic

Algoritmii genetici lucrează mult mai repede la căutarea domeniilorlor mici de soluții. Nu uniți câteva domenii ale soluțiilor în unul singur. Aceasta poate părea atrăgător, însă neapărat va cere mai mult timp pentru rezolvarea mulțimii de probleme dintr-o singură dată, decât dacă aceasta s-ar face îndependent.

1.15.3.1. Exemplu

Mister Reach vrea să primească cel mai luxos automobil pentru deplasarea prin oraș. Pentru aceasta, el trebuie să angajeze cel mai bun șofer și să-și procure un automobil foarte scump. Deoarece noi putem lua în vedere oricare șofer care poate conduce orice mașină, atunci, aceste două probleme trebuiesc separate una de alta. Una și aceeași populație nu trebuie să complice căutarea combinației cei mai buni șoferi și cele mai bune automobile. Trebuie indicată fiecare populație: una –pentru căutarea șoferului și alta – pentru căutarea mașinii.

În majoritatea situațiilor extremale, astfel de separare a problemei îngustează domeniul soluțiilor până la rădăcinaa pătrată îndoită din problema unită. În locul a 1mln de posibilități, se cere de căutat doar 2000. Problema trebuie împărțită în cât mai multe probleme. Însă, dacă problemele într-adevăr sunt în relații reciproce, de exemplu, când fiecare șofer conduce automobilul în felul său și aceasta indică utilizarea soluției, atunci problema nu poate fi împărțită în probleme mai mici.

1.15.4. Devierea nereușitelor

Programul poate să conțină note (însemnări) ale fiecărui cromozom suboptimal următor, deaceea unul și același cromozom generează din nou întodeauna, atunci el trebuie distrus imediat . aceasta poate păstra (economisi) puțin timp, căci algoritmii genetici nu au garanția faptului că una și aceeași cale evoluționistă nu va fi parcursă de mai multe ori. În acest caz trebuie să fim atenți pentru a nu exclude căile bune de dezvoltare a combinațiilor superioare. De obicei, un cromozom foarte slab nu aduce la rezultate la care poate aduce unul mai pternic. Bineînțeles că cromozomii buni sunt mai prioritari pentru crearea unei generații mai productive, decât cei slabi.

1.15.5. Corectarea greșelilor

Unele aplicații indică o mare parte a resurselor către găsirea și/sau corectarea greșelilor. Programele de legătură îndeosebi au deaface cu greșeli în timpul unirii (legăturii) cu probleme de trafic și greșeli de organizare. Întrebuințarea repetată a algoritmilor grnrtici micșorează necesitatea acestor precauții, deoarece mijloacele de corectare a greșelilor sunt deja incluse în ei. Programele genetice sunt indiferente față de câțiva genomi greșiți, către genomii pierduți sau întârziați, către copiile repetate ale genomilor ș.a. dacă acești genomi “sunt normali”, atunci problemele practic nici nu se observă. Chiar dacă o parte din program, care nu este legată de dezvoltare, este puțin deteriorată (de exemplu, când evaluarea utilității nu este chiar corectă sau când se ignoră o parte a codului recombinării), atuncialgoritmul va continua să funcționeze aproape la fel de bine caîn cazul când n-ar fi greșeli. Spre deosebire de majoritatea operațiilor, algoritmii genetici sunt destul de flexibili și greșelile devin doar un mic obstacol și nu un factor critic al sistemului. Greșelile ce apar au tendința de a scădea paralel cu construirea soluțiilor suboptimale.

1.15.6. Soluțiile incomplete și schimbarea restricțiilor către resurse

Uneori viteza de lucru a programului devine factor critic. La sistemele ce lucrează în timp real, problemele trebuie rezolvate în intervale de timp date, în caz contrar pot apărea situații neprevăzute. Pe calea măririi vitezei de căutare a soluțiilor mai favorabile, algoritmii genetici asigură răspunsul corect la întrebarea dată. Ei nu garantează că soluția primită va fi bună, însă propun cea mai bună soluție din cele găsite în timpul dat. Dacă se cere un răspuns imediat, atunci va merge și cel mai bun care a fost găsit. Dacă mai târziu va apărea vreo metodă care dă posibilitatea schimbării acestei soluții, atunci va fi gata și altă soluție, mult mai bună. Populația curentă poate fi chiar “înghețată” și păstrată, pentru ca mai târziu să fie întrebuințată pentru următoarea evoluție.

Se poate întâmpla ca să fie nevoie de a rezolva problema, iar resursele accesibile pentru îndeplinirea acestei probleme se schimbă neîncetat. Algoritmii genetici se adaptează ușor la mărimea populației pentru completarea regiunii accesibile de memorie. Cu cât memoria devine mai accesibilă, cu atât mai multe populații pot fi întrebuințate. Chiar dacă memoria care este utilizată de algoritmii genetici în procesul de evoluție se supraîncarcă, atunci pierderea genomilor nu este o problemă fatală. Dacă timpul de lucru al CPU se micșorează, atunci cu soluția care prezintă cele mai bune rezultate se poate lucra tot timpul. Chiar cu o memorie foarte limitată și cu limite temporare, algoritmii genetici pot da rezultate destul de bune, deși este evident că ei lucrează mult mai bine când resursele sunt mai bogate.

1.15.7. Utilizarea metaforelor

Metaforele ajută foarte mult la înțelegerea și pot chiar să indice cercetarea într-un nou domeniu. Modelul mamei-natură deseori lucrează bine. Unele din cele mai fundamentale baze sunt universale și lucrează la fel de bine atât pentru bacterii, cât și pentru programele de calculator. Alte aspecte nu sunt universale. Așa cum în construcția de avioane modernă se utilizează metal în loc de pene, așa și programistul trebuie să se dezică de elementele geneticii și evoluției naturale, căci tehnologiile perfecționate sunt mult mai accesibile. Natura ar fi putut fi un început bun ce ar fi asigurat demonstrația viabilității, însă aceasta nu înseamnă că metodele naturale sunt cele mai bune sau mai interesante. Avionul reactiv poate zbura mai sus și mai repede decât orice pasăre sau insectă. Cercetările făcute în domeniul algoritmilor evoluționiști s-au desprins deja de la modelul natural și utilizează idei mult mai puternice și mai noi.

Rezumat

În acest capitol am adus noțiuni generale despre algoritmii genetici: cromozom, genă, genom, structură genetică, mutație, selecție, codificare, optimizare, ș.a. am aflat că ei rezolvă probleme de diferit grad de dificultate pe calea aplicării principiilor teoriei evoluției firești a organismelor vii. Acești algoritmi au o mulțime de priorități, unice în felul lor, așa cum ar fi,de exemplu, faptul că problemele greu de motivat se rezolvă după algoritmii genetici cu o eficacitate deosebită.

Algoritmii genetici sunt bine adaptați pentru diferite forme de organizare și crează optimizatori universali foarte buni. Algoritmii genetici sunt destul de flexibili și greșelile nu devin un factor critic al sistemului. Se poate întâmpla ca să fie nevoie de a rezolva o problemă, iar resursele accesibile pentru îndeplinirea ei se schimbă neîncetat. Algoritmii genetici se adaptează ușor la schimbările ce parvin și completează regiuni accesibile de memorie. Chiar cu o memorie foarte limitate și cu limite temporare, algoritmii genetici pot da rezultate destul de bune, deși este evident că ei lucrează mult mai bine când resursele sunt mai bogate.

II. Posibilitățile de implimentare a algoritmilor genetici în diferite domenii

2.1. Exemplu de aplicație: consultantul de bursă genetică

În acest capitol este descris modelul netradițional de programare pe baza geneticii și evoluției și nu pe baza matematicii clasice.mai întâi de toate toate să analizăm prioritățile și neajunsurile acestei căi. Algoritmii genetici rezolvă excelent o mulțime de probleme, cu care algorintmii tradiționali se descurscă rău.

Mai apoi trecem la descrierea componentelor a astfel de programe și organizarea lor. Vom cerceta deasemenea diferite posibilități de codare a datelor la nivel genetic, apoi operațiile evoluționiste de bază, incluzând mutația, recombinarea și selecția.

După o analiză amănunțită a algoritmilor genetici aleși se va povesti cum este mai bine de îndeplinit aceste programe. Precizia și optimalitatea – iată cele mai importante ale succesului.

Și în sfârșit, cunoștințele acumulate le vom putea aplica în sarcina realizării unei aplicări a conceptului genetic real. Dezvoltarea de mai departe a generației consultantului la birjă genetic va da posibilitate programului de a arăta niște propuneri foarte bune în privința acțiilor cele mai de preferințăale consultantului și care mai puțin.

Agentul de bursă aduce folos vânzând o parte din acțiuni cu un preț mai mare decât cel de cumpărare. La un nivel mai general, agentul de bursă trebuie să decidă când trebuie de cumpărat pachetul de acțiuni, când trebuie să-l vândă, când trebuie să rețină acțiunile cumpărate recent.

Analiza bursei este un exemplu bun de utilizare a algoritmului genetic, deoarece foarte des se întâmplă că este greu de decis concret care factori sunt mai utili pentru prevederea viitoarelor prețuri la acțiuni și, probabil, există multe soluții bune asemănătoare, însă neevidente. Uneori prețurile bursei par destul de adevărate pentru o aranjare concretă, iar uneori se pare că ele sunt alese la întâmplare. Utilizând algoritmii genetici, se poate de elaborat o soluție optimală aproximativă și de a determina când este mai bine de cumpărat acțiuni și când este mai bine de a le vinde.

2.1.1. Analiza problemei

Datele de intrare prezintă un masiv bidimensional al istoriei schibării prețurilor timp de un an. Fiecare coloană corespunde simbolului unical al denumirii acțiunilor, iar fiecare rând – zilei ulterioare. Rezultatul lucrului programului va fi recomandarea pentru fiecare coloană – a cumpăra, a reține sau a vinde. În listingul de mai jos se indică aceste structuri (listing 2).

Listing 2. Tipuri de date I/O ale consultantului de bursă genetic

{

unsigned int price[NUM_STOKS][HISTORY_LENGHT];

}history_t;

{SELL = -1,

HOLD=0

BUY=1

}recommendation_t;

2.1.2. Structura genetică

Rezolvarea necesită doar recomandare, însă funcția de utilitate cere ca fiecare cromozom să fie codat înăuntrul planului ei de elaborare a recomandărilor reieșind din istoria schimbării prețurilor. Nu avem nevoie doar de recomandarea de a cumpăra, vinde sau reține ceva – trebuie să facem acea operație care a primit cea mai bună recomandare. Tot de ce este nevoie – să proiectăm cromozomul care ar fi generatorul recomandării.

Cromozomii de o lungime fixată se realizează cel mai simplu și noi, probabil, nu vom avea nevoie nici de schimbul numerelor genelor, deaceea trebuie să ne convingem numai de faptul că avem o cantitate fixă de gene.

Recomandările pot fi primite pe calea comparării prețului curent cu prețul mediu curent pentru o acțiune cu utilizarea vânzărilor și cumpărărilor codate genetic. Fiecare cromozom conține doar două gene: una care descrie prețul (care este proporțional cu prețul mediu curent) atunci când merge recomandarea despre cumpărare și al doilea, care pur și simplu descrie prețul când merge recomandarea despre vânzare. Atunci când nu merge recomandarea cumparării sau vânzării, se generează recomandarea despre reținerea acțiunilor.

Deoarece fiecare genă este pur și simplu o valoare întreagă, pentru ele se poate efectua codarea Gray.

Listing 3. Structurile genetice și structurile de inițiere pentru consultantul de bursă genetic

typedef unsigned int gene_t;

typedef struct

{gene_t buy_price;

gene_t sell_price;

}

chromosom_t

individual[SPECIES_POPULATION];

}species_t;

typedef struct

{species_t species[NUM_STOKS];

}population_t;

2.1.3. Evaluarea utilității

Avem nevoie să primim cele mai bune recomandări, care ar fi permis să câștigăm o sumă mare de bani. Această cerință poate fi stabilită ca un sistem de generare a recomandărilor care ar permite un venit maxim la întrebuințarea cu istoriile accesibile a schimbării prețurilor. Deci, genotipul se consideră mult mai util când crează un plan al recomandărilor care, dacă să fie urmat zilnic, va aduce la un rezultat mult mai rentabil. După aceasta, există toate motivele de a crede sistemul genotipic în aceea că recomandările efectuate de dânsul sunt într-adevăr fără preț. Noi vom întrebuința unicul genotip care aduce venit și care se aplică în fiecare zi asupra datelor despre istoria schimbării prețului.

Listing 4. Funcția care răspunde de faptul cât de bine fiecare organism participă la comerțul de bursă

long fitness(chromosome_t* c,

unsigned int* history

)

{long total_price=0;

long avg_price;

long price;

long shares=0;

long cash=0;

unsigned int t;

for(t=0; t<HISTORY_LENGHT; t++)

{

price=history[t];

total_price +=price;

avg_price= total_price /(t+1);

price-=avg_price;

price=price * 100/avg_price;

if(-price>=(long)Gray_to_bin(c->buy_price))

{

++shares;

cash-=(long)history[t];

}

else if( price >= (long)Gray_to_bin(c->sell_price))

{–shares;

cash += (long)history[t];

}

}

cash += shares * (long)history[t-1];

return cash;

}

2.1.4. Procesul alegerii

Deoarece fiecare acțiune are factori asemănători, însă potențial diferiți, care influiențează asupra prețului ei, atunci este nevoie de a stabili tipul pentru fiecare simbol al acțiunii. Migrațiunea va permite să descoperim orice priorități esnțiale și se va extinde mai departe până când se vor putea menține prioritățile individuale necesare. Orice simbol al tickerului acțiunii va primi o recomandare de la un organism expert special care se dezvoltă doar pentru acest simbol și totuși, aceste organisme vor conlucra făcând schimb de idei cu subpopulațiile vecine.

Fiecare submulțime a populației va avea o mărime fixă. În fiecare generație noii genptipi îi înlocuiesc pe cei vechi. În listingul de mai jos se utilizează “strategia plusului”, care permite genotipilor părinților să supraviețuiască necontenit din generație în generație.

Listing 5. Funcția simplă de alegere pentru luarea deciziei cine “să trăiască” și cine “să moară”

unsigned int select_survivors(

species_t const* befor,

species_t* after,

long* fit

)

{

unsigned int i;

ansigned int j;

long record;

long temp;

for(i=0; i<SPECION_POPULATION; j++)

{

record=i;

for(j=i+1; j<SPECIES_POPULATOIN; j++)

{

if(fit[j] > fit[record])

{

record=j;

}

}

temp=fit[record];

fit[record]= fit[i];

fit[i]=temp;

after->individual[i] = befor->individual[record];

}

return i;

}

2.1.5. Inițializarea populației

Să începem cu populația întâmplătoare internă din fiecare sesiune. Listingul 6 conține funcții de inițializare.

Listingul 6. Ambele gene ale cromozomului primesc mărimi întâmplătoare.

void initialize_chromosome(chromosome_t* c)

{

c->buy_price= bin_to_Gray(rand() % MAX_PRICE);

C->sell_price= bin-to_Gray(rand() % MAX_PRICE);

}

vcoid initialize_species(species_t* s)

{

int i;

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

{

initialize_chromosome(&s->individual[i]);

}

}

void initialize_population(population_t* p)

{

int i:

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

{

initialize_species(&p->species[i]);

}

}

2.1.6. Strategia mutației

Pentru această problemă vom folosi o mutație facilă.

Listing 7. Transferarea biților între cele mai simple funcții ale mutației

void mutate_gene(gene_t* g)

{

*g ^= 1 << rand() % (sizeof (gene_t) * CHAR_BIT);

}

void mutate_chromosome(chromosome_t* c)

{

switch(rand() & 1)

{

case 0:

mutate_gene(&c->buy_price);

break;

case 1:

mutate_gene(&c->sell_price);

break;

}

}

void mutate_species(species_t* s)

{

unsigned int i;

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

{

if(rand() % MUTATION_FACTOR==0)

{

mutate_chromosome(&s->individual[i]);

}

}

}

Deoarece acum sunt câteva gene, pentru producerea populației trebuie să combinăm în același timp doar doi părinți. Alegerea părinților poate fi întâmplătoare (listing 8).

2.1.7. Strategia recombinării

Fiecare genă poate fi unită logic cu o genă asemenea din alt cromozom, deaceea trebuie să ne folosim aceasta și de făcut în așa mod ca genele să se întâlnească undeva la mijloc. În acest caz are sens și încrucișarea simplă.

Listing 8. Funcția de recombinare, care răspunde ed formarea organismelor noi din cele vechi.

void mate_gene(

gene-t* parent_1,

gene_t* parent_2,

gene_t* child

)

{

switch(rand() % 3)

{

case 0:

*child= *parent_1;

break;

case 1:

*child= *parent_2;

break;

case 2:

*child= *parent_1 + *parent_2 >>1;

break;

}

}

void mate_chromosomes(

chromosome_t* parent_1,

chromosome_t* parent_2,

chromosome_t* child

)

{

mate_genes(

&parent_1->buy_price,

&parent_2->buy_price,

&child->buy_price

);

}

void recombine(

species_t* s,

unsigned int num_survivors

)

{

unsigned int i;

unsigned int parent_1;

unsigned int parent_2;

for(i = num_survivors; i<SPECIES_POPULATION; i++)

{

parent_1= rand() % num_survivors;

parent_2= rand() % num_survivors;

mate_chromosomes(

&s->individual[parent_1],

&s->individual[parent_2],

&s->individual[i]

);

}

}

2.1.8. Rezultate și concluzii

Populația, alcătuită din sute de organisme, găsește succesiv valorile posibile cele mai bune în mai puțin de 50 de generații. Din cauza simplității cromozomilor, toate (în afară de cele mai mari) schimbările în recombinarenu au efecte vizibile.

Acest algoritm, foarte simplu, pare a fi destul de adecvat pentru căutarea portofoliilor bune de acțiuni în comerțul de bursă. El permite de a găsi repede valoarea cea mai bună și el poate fi utiliza pentru cercetarea domeniilor foarte mari de valori, în afara simplelor operații de vânzare-cumpărare. Utilizarea strategiilor mai complexe de avaluare a utilității așa ca coincidența cu șablonul, va lua mai mult timp, însă la rezultat se vor primi recomandări mult mai optimale

Rezumat

În acest capitol este adus un concept minunat de utilizare a geneticii și evoluției pentru rezolvarea problemelor de diferit grad de dificultate. Am văzut că, necătând la faptul că algoritmii genetici nu rezolvă probleme începând de la zero, așa cum ar fi sortarea numerelor întregi, ei sunt foarte comozi pentru rezolvarea situațiilor grele care apar în lumea reală. Datele de intrare greșite, limitele variabile ale resurselor, scopurile ce se schimbă și însăși scopurile, care sunt foarte greu de determinat, nu încalcă (întrerup) evoluția atât de dramatic cum ar fi în algoritmii simpli.

Metaforele cele mai neordinare deseori aduc la cele mai înteresante soluții, rezolvări. Necătând la faptul că evoluția lumii animale nu se rsferă la programele computaționale, noi putem lua de aici niște lecții bune. De exemplu, un simplu algoritm genetic se descurcă excelent cu o problemă atât de dificilă cum ar fi analiza bursei.

2.2. Implementare

Algoritmii genetici se termină, de obicei, după ce s-au creat un număr predefinit de populații noi. În alte cazuri se poate determina dacă soluția s-a îmbunătățit de la o populație la alta. În cazul afirmativ se continuă cu crearea de noi populații, iar în caz negativ se afișează cel mai bun cromozom din populația curentă.

Algoritmii genetici au o structură foarte generală, care permite folosirea lor pentru majoritatea problemelor. Ceea ce se chimbă sunt următoarele:

codificarea cromozomilor

inițializarea populației

încrucișarea

mutația.

Comentariile la nivel de sursă sunt suficiente pentru a înțelege ce se întâmplă.(anexa…)

2.2.1. Problema 1

Componenta intern stabilă maximală

Se dă un graf neorientat cu N noduri. Se cere să se determine o componentă intern stabilă maximală, adică o submulțime maximală de noduri cu proprietatea că oricare două noduri din submulțime nu sunt legate printr-un arc.

Soluție

Datele de intrare se citesc sub forma unei matrice, în matricea cunoscută.

Fitness-ul unui cromozom este egal cu cardinalul mulțimii de noduri pe care o codifică.

Inițializarea unui cromozom din populație se face prin urmștorul algoritm euristic: se pune în cromozom un nod de start. Populația trebuie să fie suficient de mare pentru ca fiecare nod să să fie în câțiva cromozomi. Apoi se tot încearcă adăugarea de noi noduri la componența curentă. După ce s-au introdus în ea toate nodurile posibile, se trece la construirea unui nou cromozom.

Inițializarea cromozomilor se face și doar cu un singur nod. În acest caz însă vom avea nevoie de mai mulți pași pentru aobține soluția, în timp ce algoritmul euristic prezantat mai sus, poate ajunge la soluția dorită chiar după etapa de inițializare.

Pentru a realiza încrucișarea, primul cromozom fiu va fi considerat primul cromozom părinte la care se adaugă noduri din al doilea părinte.al doilea cromozom pui va fi al doilea părintela care se adaugă noduri din primul părinte.

Mutația constă din eliminarea unui nod oarecare dintr-un cromozom ales la întâmplare. În continuare sunt prezentate procedurile care se vor adăuga la algoritmul geneti general de mai sus.(anexa 3)

2.2.2. Problema 2

Drum de lungime maximă

Se dă un graf neorientat cu N noduri. Se cere să se determine un drum elementar care conține cât mai multe noduri.

Soliție

Un cromozom codifică un drum sub forma unui șir de noduri. Fitness-ul unui cromozom este egal cu lungimea drumului (numărul de noduri din componența lui).

Pentru utilizare se folosește următorul algoritm euristic: se pleacă dintr-un vârf oarecare și se adaugă noduri cât timp mai există legături între ele.

Încrucișarea se face în următorul mod: primul urmaș este primul părinte, căruia i se adaugă la un capăt un lanț ce există în al doilea părinte. Al doilea urmaș este al doilea părinte la care i se adaugă un lanț din primul părinte.

În final obținem cel mai lung drum elementar. Acesta ar putea fi chiar hamiltonian.(anexa 1)

2.2.3. Problema 3

Rezolvarea ecuației de gradul doi

Fie ecuația ax2 +bx+c= 0. Se cere de determinat rădăcinile.

Soluție

Putem, bineînțeles să aplicăm formulele cunoscute. Însă programul care urmează demonstrează cum această tehnică poate fi folosită și la ecuații de grad mai mare.

Inițțial generăm o mulțime aleatoare de perechi (x1 ,x2). Pentru ca soluția să fie găsită mai rapid, se presupune că rădăcinile se află în intervalul -50,…,50.

Prin mutație se schimbă puțin valoarea uneia dintre rădăcini. Probabilitatea de mutație este mare.

Prin încrucișare, noii cromozomi preiau o rădăcină de la fiecare din părinți. (anexa 4)

Rezumat

În acest capitol este descris modelul netradițional de programare pe baza geneticii și evoluției și nu pe baza matematicii clasice. În comparație cu algoritmii tradiționali, algoritmii genetici rezolvă o mulțime de probleme dificile la care primii întâmpină greutăți. Anume datorită structurii lor foarte generale, ei permit rezolvarea acestor probleme.

În capitolul doi au fost aduse câteva exemple de aplicare a algoritmilor genetici în diferite domenii: economie, matematică, ș.a

Necătând la faptul că algoritmii genetici nu rezolvă probleme începând de la zero, așa cum ar fi sortarea numerelor întrgi, ei sunt foarte comozi pentru rezolvarea situațiilor grele ce apar în lumea reală. Datele de intrare greșite,limitele variabile ale resurselor, scopurile ce se schimbă și însăși scopurile care sunt foarte greu de determinat, nu încalcă evoluția atât de dramatic cum ar fi în cazul algoritmilor simpli.

Metaforele cele mai neordinare aduc la cele mai interesante soluții și rezolvări. Necătând la faptul că evoluția lumii animale nu se referă la soft, noi putem lua de aici niște lecții bune. De exemplu, un algoritm genetic simplu se descurcă excelent cu o problemă atât de deficilă cum ar fi analiza bursei de valori.

III. Aprecierea cheltuielilor economice ale proiectului de diplomă

Graful rețea este un model informativ, în care se arată legăturile între lucrări și evenimente ale lucrărilor date, necesare pentru obținerea scopului final. Graful rețea nu este altceva decât un complex de graf orientat. El conține două elemente principale: lucrarea și evenimentul. Arcele prezintă luacarea, iar vârful – evenumentul. Lucrarea este orice proces, care duce la atingerea rezultatului concret. Evenimentul (în afară de primul) este rezultatul lucrării efectuate. Evenimentul i, după care nemijlocit se începe lucrarea dată, este pentru lucrarea primară; evenimentul j, înaintea căruia nemijlocit a fost efectuată lucrarea, este final. Între evenimentele i și j poate fi efectuată numai o lucrare. Primul eveniment în rețea, care nu are înaintea sa evenimente și lucrări și arată începerea îndeplinirii complexului de lucrări – este primar. Evenumentul, după care nu urmează alte evenimente și lucrări și arată încheierea complexului – este final.

. În desenul 1 este prezentată schema reprezentării grafice a grafului-rețea :

Fig.3.1. Structura grafului-rețea.

unde: cercul – un eveniment;

săgeata – o lucrare;

tij – durata lucrului ij;

Rlij – rezerva liberă de timp a lucrului ij;

Rdij – rezerva deplină de timp a lucrului ij;

Tdi – timpul devreme de începere a evenimentului i;

Tti – timpul târziu de terminare a evenimentului i;

Ri – rezerva liberă de timp a evenimentului i;

Ni – numărul evenimentului i;

Tdj – timpul devreme de începere a evenimentului j;

Ttj – timpul târziu de terminare a evenimentului j;

Rj – rezerva liberă de timp a evenimentului j;

Nj – numărul evenimentului j.

Datele inițiale pentru construirea rețelei sunt:

Biblioteca lucrărilor și evenimentelor în procesul de planificare în rețea, unde se arată timpul efectuării lucrărilor (tab.3.1).

Determinarea numărului de executanți și repartizarea lor în lucru (tab.3.2 și 3.3).

Tab.3.1

Biblioteca lucrărilor și evenimentelor în procesul de planificare în rețea

Pentru elaborarea proiectului de diplomă se crează grupul de executanți. Asupra componenței lui influiențează mulți factori printre care: volumul de lucru a PD, resursele financiare alocate, noutatea și complexitatea temei, experiența executanților, nivelul lor profesional și general teoretic etc. Adică, luând în considerație clasa de complexitate a problemelor, se formează grupul de executanți capabili să asigure îndeplinirea tuturor lucrărilor planificate în termenul indicat și se repartizează pe lucrări concrete. Componența grupului de executanți se introduce în tabelul 2.

Tab. 3.2

Componența grupului de executanți

Tab.3.3

Repartizarea executanților pe lucrări

Se construiește graful rețea și se calculează cheltuielile în timp pentru efectuarea lucrărilor în rețea. Datele se introduc în tabelele 3.4 și 3.5.

3.1. Construirea grafului rețea și calcularea parametrilor principali.

La parametrii de bază a rețelei se referă: calea critică, rezervele de timp a evenimentelor și lucrărilor. Rezerva de timp a evenimentului R se determină ca diferența dintre timpul târziu și timpul devreme.

R = Tt – Td

Tdj = max(Tdi + tij)

unde

tij – timpul parcurgerii lucrării.

În evenimentul finit, timpul devreme este egal cu timpul târziu, sensul economic al căruia este că nu suntem cointeresați în lungirea evenimentului.

Tti = min(Ttj – tij)

Pentru lucrări se calculează următorii parametri:

Rezerva deplină a lucrărilor

Rdij = Ttj – Tdi – tij

Rezerva deplină a lucrării înregistrează durata în timp, cu cât mai târziu poate fi îndeplinită lucrarea dată ce nu schimbă durata totală a căii critice.

2. Rezerva liberă a lucrărilor

Rlij = Tdj – Tdi – tij

Rezerva liberă a lucrării este timpul maximal de lungire a lucrării date, care nu schimbă timpul târziu de îndeplinire a evenimentului următor și timpul devreme a evenimentului precedent.

Se numește cale critică drumul maximal de la evenimentul inițial până la cel final în calea rețelei.

Calea critică are două condiții:

Rezervele evenimentelor Ri = Rj = 0

Rezervele depline Rdij = 0

Parametrii de bază ai rețelei sunt arătați în tabelele 3.4 și 3.5, iar rețeaua – în anexa 9.

Tab.3. 4

Parametrii de bază ai rețelei

Tab.3. 5

Parametrii de bază ai rețelei

Cum se vede din graful rețea, lucrările pentru proiectul de diplomă au ținut 50 de zile, adică 10 săptămâni cu 5 zile lucrătoare de 8 ore lucrătoare.

3.2. Aprecierea cheltuielilor

Tab.3. 6

Costul materialelor utilizaze la elaborarea proiectului

Dacă la lucrarea de diplomă utilizăm aparataj ce a fost utilizat și va mai fi în viitor la alte lucrări, se calculează amortizarea lui pe timpul lucrat.

A = C * N * t, (3.1)

unde

C – costul inițial al dispozitivului;

N – norma amortizării;

t – timpul de lucru al utilajului la lucrarea dată.

Tab.3. 7

Calculul defalcărilor pentru amortizare din costul utilajului

Cheltuielile pentru salariul de bază a proiectanților se calculează pe baza datelor despre componența de calificare a colaboratorilor, salariile de post a lor și gradul de ocupare a lor pe temă.

Salariul suplimentar prezintă 20% din suma salariului de bază și cel suplimentar. Defalcările la asigurarea socială au fost luate din tabelul 7. Cheltuielile de regie constituie 30% din salariul de bază. Datele se introduc în tabelul 8.

Tab.3. 8

Cheltuielile pentru salariu

Defalcări pentru asigurarea socială(29% de la suma salariului de bază și cel suplimentar) = 602 lei.

Tab.3.9

Cheltuieli totale pentru realizarea proiectului de diplomă

Tab.3.10

Efectul social

IV. Protecția muncii

Conform legii Republicii Moldova, protecția muncii reprezintă un sistem de măsuri și mijloace social- economice, organizatorice, tehnice și profilactorice care acționează în baza actelor legislative și a altor acte normative.

Mărirea eficacității producției, intensificarea ei, sunt în legătură cu crearea condițiilor de muncă sănătoase și sigure. Protecția muncii poate fi privită ca un sistem care asigură, în sfera de producție, o păstrare optimă a sănătății și a interacțiunii oamenilor cu mijloacele tehnice și cu mediul înconjurător.

Protecția muncii se bazează pe acumularea cunoștințelor în diferite ramuri: igiena muncii, fiziplogia și psihilogia muncii, estetica, economia, sociologia. Ea rezolvă probleme psihofiziologice, inginero-tehnice, economice și sociale.

Condițiile de muncă sănătoase și sigure măresc atracția către muncă, asigură o productivitate mai mare, ajută la menținerea unei stări psihofiziologice normale a lucrătorilor, la activitatea lor socială și la transformarea lucrului într-o necesitate vitală. În afară de aceasta, de condițiile de muncă depind productivitatea și calitatea lucrului, eficacitatea utilizării resurselor muncii.

În acest fel, protecția muncii este un sistem de acte legislative și de manifestări social economice, organizatorice, tehnice, igienice și sanitaro-profilactorice, care asigură sănătatea lucrătorului la locul de muncă.

La rezolvarea problemelor tehnice este neapărat să atragem atenția la problemele de interacțiune a mediului de productivitate și mediul natural înconjurător. Urmările activității omului se manifestă deja nu numai în plan local, dar și regional și în unele cazuri chiar global. Protecția mediului ambiant este cea mai importantă problemă social-economică.

4.1. Prezentarea funcțiilor în formă de sistem.

Munca prezintă una din cele mai importante categorii social-economice. Protecția muncii cercetează procesul de muncă din p.d.v. al întreținerii și securității muncii, păstrarea sănătății și proprietăților de muncă ale omului. Procesul de muncă este o activitate a omului , orientată spre schimbarea și adaptarea obiectelor naturii pentru satisfacerea cerințelor omului.

În procesul muncii omul se află în anumite condiții. El folosește diferite unelte, se află în relații cu alți muncitori, se expune acțiunii multori factori de producție care sunt de origine și acțiune diferită. Acțiunea unor factori de producție poate fi nefavorabilă și să acționeze negativ asupra sănătății omului. Totalitatea factorilor mediului de producție care influiențează asupra sănătății și activității muncitorești a omului se numesc condiții de muncă.

Mediul de producție pe lângă elementele cu caracter tehnic și natural (materiale, instrumente, utilaj, procese tehnologice, clădiri, ș.a.) include și elemente sociale (sănătatea lucrătorilor, dezvoltarea individului, interesul față de muncă, ș.a.), care se formează sub influiența forței și relațiilor de producție. În așa fel, condițiile de muncă sunt un fenomen social complicat, care se formează sub influiența factorilor social-economici, naturali și tehnico-organizatorici care influiențează asupra sănătății, nivelului de trai și dezvoltării multilaterale a omului.

4.2. Securitatea muncii

Securitatea muncii – starea condițiilor de muncă în prezența căreea, asupra omului este exclusă acțiunea factorilor dăunători.

Cercetarea activității de muncă din p.d.v. al securității ei pentru om este o problemă științifică complexă, legată cu prelucrarea totalității problemelor metodologice, științifice. Ca sistem, adică un complex de elemente aflate în legătura receprocă, care au o anumită structură și interacționează cu mediul înconjurător, protecția muncii este deschisă. Dintr-un punct de vedere ia este doar o componentă al unui sistem mult mai mare, care include în sine elemente ce caracterizează formațiunea social-economică dată, iar din alt punct de vedere, proteția muncii este o parte a sistemului resurselor comunității. De aceea, baza metodologică a protecției muncii trebuie să fie o abordare de sistem care permite să îndeplinească cercetarea sistemului ca un tot întreg.

Analiza de sistem ca una din metode de cercetare, se caracterezează prin proprietăți și relații greu de observat, presupune prezentarea obiectelor în calitate de sisteme cu un scop bine determinat, cercetarea proprietăților și a relațiilor de receprocitate între scopuri și mijloacele lor de realizare. În general, etapele analizei de sistem se reduc la următoarele: la prima etapa are loc descrierea abstractă a sistemului, adică se indică scopurile, parametrii de întrare și ieșire. Mai departe se face o analiză. După datele primite se sintetizează variantele alternative de construire a sistemului.

Factorii ce influențează condițiile de muncă se află într-o dependență reciprocă foarte complicată. Protecția muncii rezolvă problemele de asigurare a securității, a păstrării sănătății în procesul de muncă, prin metoda utilizării actelor legislative, mijloacelor social-economice, organizaționale, tehnice, igienice.

4.3.Analiza condițiilor protecției muncii

4.3.1. Indicii stării condițiilor de muncă

Analiza condițiilor protecției muncii permite să stabilim factorii de producție dăunători și periculoși și contribuie la preîntîmpinarea traumelor de producție și a bolilor prefesionale. Metodele de analiză a condițiilor de muncă prezintă totalitatea metodelor folosite pentru stabilirea și aprecierea factorilor de producție dăunători și periculoși cu scopul studierii măsurilor care asigură neutralizării lor.

Evaluarea cantitativă a nivelului siguranței utilajelor se caracterizează de nivelul traumatismului de producție și bolilor profesionale ale lucrătorilor.

Condițiilor protecției muncii ne permite să apriciem condițiile existente ale muncii la locul de lucru, să stabilim ordinea petrecerii măsurilor de însănătoșire.

Diferențierea condițiilor și caracterului muncii preîntâmpină granițele abaterii parametrelor mediului de producție și procesului de muncă de la normativele igienice existente, dar și influiența lor asupra stării și sănătății lucrătorilor. După acești indici se evidențiază trei clase de condiții și caracter al muncii.

Condiții optimale și caracter al muncii, în prezența cărora este exclusă influența neprielnică asupra lucrătorilor.

Condiții accesibile și caracterul muncii, în prezența cărora nivelul factorilor periculoși nu întrece normele igienice de la locul de muncă, iar schimbările funcțiilor posibile se regenerează în timpul odihnei reglementate în timpul zilei de lucru și nu prezintă nici un risc pentru sănătate în timpul apropiat sau îndepărtat.

Caracterul muncii și condiții dăunătoare și periculoase în prezența cărora, la nerespectarea normelor și regililor sanitare, este posibilă influiența factorilor dăunători și periculoși ale mediului de producție care întrec limitele igienice și psihofiziologice ale activității. Aceasta duce la schimbări funcționale ale organismului în urma cărora scade capacitatea de muncă și se dereglează atarea sănătății.

4.3.2. Metode de analiză a condițiilor de muncă

Perfecționarea condițiilor de muncă este una din problemele de bază ale administrației întreprinderii și organizațiilor. Condițiile de muncă în mare măsură stabilesc sănătatea și capacitatea de muncă a lucrătorului. Starea lor este determinată de prezența factorilor dăunători care se împart în patru grupe: fizici, chimici, biologici și psihofiziologici.

La factorii fizici se referă mașinele și mecanismele în mișcare, părțile mobile ale echipamentelor, materialele; poziția locului de muncă la o distanță impunătoare de la pământ (podea); imponderabilitatea; construcții ce se risipesc; temperatura ridicată sau scăzută a suprafeței utilajelor, materialelor, aerului; umiditatea mare sau mică; gălăgia, vibrația, ultrasunetul mari; presiune mare sau mică și schimbarea bruscă a ei; valoarea ridicată a tensiunii în rețeaua electrică, scurtcircuitele care pot avea loc; nivelurile ridicate ale curentului static și a iradierilor electromagnetice; neajunsul sau lipsa totală de lumină naturală; iluminatul insuficient al zonei de lucru, luminozitatea înaltă.

Factorii chimici includ substanțe ce acționează toxic, iritant, cancerogen asupra omului și influiențează asupra funcției reproductive. Aceste substanțe pot pătrunde în organism prin organele respiratorii, porii pielii și altele.

La factorii biologici se referă microorganismele patogene (bacterii, viruși, ș.a.) și microorganismele plantelor și animalelor.

La cei psihofiziologici se referă supraîncărcarea fizică și neuropsihică.

Analiza condițiilor de muncă presupune cercetarea întregului complex de factori dăunători cu ajutorul analizei obiective a condițiilor de muncă prin metoda aprecierii de expertiză.

Analiza obiectivă a condițiilor de muncă se aplică doar la schimbarea posibilă a parametrilor ce acționează nefavorabil asupra factorilor de producție (de exemplu, temperatura aerului, iluminarea suprafeței de lucru). Un astfel de control se face periodic, factorii mai periculoși se controlează mai des, iar pentru anumite tipuri de acțiuni controlul se face permanent.

Odată cu dezvoltarea tehnicii, apare necesitatea rezolvării noilor probleme în domeniul protecției muncii – crearea aparatelor noi de control, noilor metode de măsurare.

Metodele de expertiză permit de a cerceta condițiile de muncă cu o exactitate admisibilă, folosind date reprezentate prin baluri (de exemplu, așa se cercetează supraîncărcarea neuropsihică). Fiecare element al condițiilor de muncă se apreciază cu un oarecare număr de baluri în dependență de tipul și timpul de acțiune asupra lucrătorului.

4.5. Unitățile luminiscente de bază și corelațiile folosite în protecția muncii.

Unitățile luminiscente tehnice caracterizează cantitativ acțiunea iradierii luminii asupra ochilor omului. Iradierea vizibilă este partea iradierii electromagnetice în diapazonul de lungimi de undă de la 380 la 770 nm. De obicei, se folosesc astfel de indici ca: fluxul de lumină, iluminatul, coeficienții de reflectare ș.a.

4.5.1. Acțiunea luminii asupra organismului uman. Rolul iluminatului la crearea condițiilor de muncă sănătoase.

Lumina este unul din principalii factori ai existenții omului. Ea influiențează asupra stării organismului, organizarea corectă a iluminatului stimulează petrecerea proceselor activității nervoase superiore și ridică capacitatea de muncă. La iluminarea insuficientă omul lucrează mai puțin productiv, obosește repede, crește riscul greșelilor în acțiuni, ceea ce poate duce la traume. Se consideră că 5% din traume pot fi din cauza a astfel de boli profesionale cum ar fi miopia.

În dependență de lungimea undelor, lumina poate acționa iritant (roșu-portocaliu) sau liniștitor (verde-gălbui). Componența spectrală la fel acționează asupra productivității muncii. Cercetările arată că, dacă productivitatea omului la lumina naturală o putem considera ca 100%, atunci la lumina roșie și portocalie ea va fi doar de 76%. Oamenii, care din anumite motive sunt lipsiți total sau parțial de lumina naturală, au riscul de a fi “flămânzi de lumină ”.

Iluminatul încăperilor trebuie să satisfacă următoarele condiții:

nivelul iluminatului suprafețelor de lucru trebuie să corespundă normelor igienice pentru tipul de lucru dat;

trebuie sa fie asigurate uniformitatea și stabilitatea nivelului de iluminare în încăpere, lipsa contrastului brusc între iluminarea suprafeței de lucru și mediul înconjurător;

în orizontul de vedere nu trebuie să se creeze străluciri de către sursă sau alte obiecte;

lumina artificială folosită la întreprinderi, după componența sa spectrală trebuie să se apropie de cea naturală.

4.5.2. Feluri și sisteme de iluminare

Iluminarea întreprinderilor poate fi naturală, artificială sau combinată.

Iluminatul natural se face prin ferestre (lateral), luminator (de sus) sau concomitent. Normarea iluminatului natural se face cu ajutorul coeficientului de iluminare naturală (CIN), exprimat în %:

CIN =Eint*100 / Eext

unde Eint – iluminarea punctului înăuntrul încăperii, iar Eext – iluminarea externă concomitentă a suprafeței orizontale cu lumină împrăștiată.

Distribuirea CIN înăuntrul încăperii este neuniformă și depinde de poziția “deschizăturilor luminoase”.

La iluminarea combinată, lumina naturală care nu ajunge, este completată cu cea artificială.

Iluminatul artificial, după destinație se împarte în iluminat de lucru, de serviciu, avariat, de evacuare și de pază.

Iluminatul de lucru crează condiții necesare pentru o activitate de lucru normală a omului.

Iluminatul de serviciu se aprinde în timpul lucrului.

Iluminatul de avariere se aprinde în cazul stingerii luminii de serviciu. Lămpile iluminatului de avariere se alimentează de la o sursă autonomă și trebuie să asigure o iluminare nu mai puțin de 5% din mărimea iluminatului de serviciu, însă nu mai puțin de 2 lc pe suprafețele de lucru și nu mai puțin de 1 lc pe teritoriul întreprinderii.

Iluminatul de evacuare se aprinde pentru evacuarea oamenilor din încăpere în caz de pericol. El se instalează în încăperile de producție cu un număr de lucrători mai mare de 50, dar și în încăperile clădirilor colective, sociale și în cele auxiliare, de ajutor întreprinderilor de producție, dacă în ele pot să se găsească concomitent mai mult de 100 de oameni.

Iluminatul de pază este de-a lungul granițelor teritoriilor păzite și trebuie să asigure o lumină de 0.5 lc.

Cerințele protecției muncii față de iluminatul artificial: tensiunea de alimentare a surselor de iluminare nu trebuie să depășească 220 V, pentru instalații(strunguri) – i<42V, pentru instalații de iluminare portative – 12V.

4.5.3. Calcularea iluminatului artificial în încăpere.

Calculul iluminatului artificial în încăpere se efectuiază după formula:

Fl = 1674,4 lm

unde:

E n- iluminarea minimă;

En = 500 lc

Sp – aria podelei;

Sp = 24 m2

Z – coeficientul iluminării neuniforme;

Z = 0.9

K – coeficientul de rezervă care ține cont de preluarea și învechirea becurilor;

K = 1.2

N – numărul de instalații de iluminat;

N = 6

n – numărul becurilor la o instalație;

n = 3

– coeficientul de randament al instalației de iluminat, se găsește în dependență de indiciile încăperii;

= 0.43*100%, care se calculează după formula.

i = 1.2

unde:

A,B – lungimea și lățimea încăperii, m;

A = 6m, B = 4m

Hl – înălțimea instalației de iluminat până la suprafața de lucru; Hl = 2m

Deoarece F = 1674.4lm – tipul de becuri luminiscente ЛДЦ cu fluxul de lumină 1520lm și puterea 40Wt.

4.6. Aprecierea pericolului la monitor.

Odată cu dezvoltarea tehnicii de calcul tot mai mult se atrage atenția asupra problemelor protecției utilizatorilor, în special acelor care lucrează la calculator, adică lângă monitor. Principalii factori dăunători, care influențează asupra sănătății omului, când acesta lucrează lângă monitor sunt:

radiația sau iradieri ionizate;

câmpul electrostatic;

câmpul electromagnetic, etc.

Iradieri ionizate reprezintă iradierea electro-magnetică cu o capacitate de ionizare a moleculelor. Dacă se provoacă ionizarea moleculelor organismului uman, atunci legăturile între molecule se distruge și ca rezultat apar diferite boli. Capacitatea de ionizare o au următoarele particule: X- iradieri, fluxul de electroni, substanțele radioactive.

În cazul monitoarelor cel mai semnificativ tip de iradiere ionizată este – iradiere, care însă este foarte mică, de obicei nu depășește normele biologice. Celelalte tipuri de iradieri pot fi neglijate deoarece greu pot fi depistate.

– iradierea apare în urma ciocnirii electronilor cu atomii substanței luminofore sau cu atomii ecranului din sticlă.

Pentru a micșora iradierea ionizată a monitoarelor moderne, pe suprafața lor se aplică o foaie metalică străvezie, care atenuează fluxul de iradiere. O altă cale de apărare împotriva iradierii ionizate este procurarea unui ecran protector, care se instalează pe monitor.

În genere iradierea ionizată asupra omului poate provoca următoarele acțiuni:

locale – acțiuni de scurtă durată cu doze mari, care aduce la traume locale: îmbolnăvirea pieii, pierderea pieii, pierderea unghiilor, defectarea oaselor, cancer;

totale – reprezintă iradieri îndelungate cu doze mici, aduce la îmbolnăvirea sângelui (leucemie).

Câmpul electrostatic, care apare pe ecranul monitorului este rezultatul bombardării permanente a monitorului cu fascicolul de electroni emis de catod. Astfel sarcina electrică, care se acumulează pe suprafață monitorului, formează câmpul electrostatic. Fenomenul electrizării statice este legat și de starea aerului din mediu. În condiții normale aerul se caracterizează cu proprietăți izolatorii înalte, însă sub acțiunea razelor solare și celor cosmice, radiației materialelor radioactive a scoarței pământului și a altor factori ionizatori, moleculele neutrale a aerului se ionizează, formând ioni pozitivi și negativi – purtători ai sarcinii electrice. Dacă intensitatea câmpului electric, format de materialele, de dispozitivele de curent continuu și de obiectele, care ușor se electrizează, este mare, atunci ionii liberi obțin energie cinetică suficientă pentru a forma ioni noi la ciocnirea lor cu moleculele neutre. În urma ionizării aerul își pierde proprietatea sa de izolator (devine conductibil) și descărcarea electrică latentă se transformă într-o descărcare sferică, adică are loc o străpungere electrică a aerului.

Descărcarea electricității statice poate provoca o explozie, incendiu și alte accidente. La unele întreprinderi, care produc substanțe sintetice, polimeri și produse din aceste substanță, și care posedă proprietăți dielectrice înalte, electrizarea micșorează productivitatea muncii și este unul din motive care duc la scăderea calității producției.

Influența sistematică a câmpului electrostatic de intensitate înaltă asupra corpului omului poate duce la unele dereglări funcționale a sistemului central nervos, a sistemului cardio-vascular și a altor organe. Din aceste motive, intensitatea maxim-admisibilă a câmpului electric la locurile de muncă este normată:

Tab.4.1.

Intensitatea maxim-admisibilă a câmpului electric la locurile de muncă.

Intensitățile admisibile a câmpului electrostatic sânt indicate fără a lua în considerație influența asupra omului a descărcărilor electrice. Normele indicate pentru intensitatea câmpului electrostatic mai mare de 20 kW/m se utilizează numai cu condiția, restul timpului a zilei de lucru intensitatea nu întrece 20 kW/m. Dacă intensitatea câmpului electrostatic întrece valorile indicate, atunci se aplică unele măsuri de micșorare a ei.

Măsurile principale de micșorare a intensității câmpului electric în zona de lucru sunt:

îndepărtarea surselor a câmpurilor electrostatice din zona personalului care deservește aparatura;

ecranarea sursei câmpului sau a locului de muncă;

utilizarea neutralizatorilor de sarcini electrice statice;

umezirea materialului care se electrizează;

schimbarea materialelor, care ușor se electrizează cu materiale ce nu se electrizează;

alegerea suprafețelor care contactează conform condițiilor de electrizare minimă;

modificarea procesului tehnologic în așa mod ca să se micșoreze nivelul de electrizare;

alegerea materialelor și suprafețelor care greu electrizează alte corpuri sau le electrizează cu sarcini de polaritate diferită;

instalarea în toate încăperile, unde se află oameni, a podelelor care conduc curentul electric.

În calitate de măsură de protecție individuală a omului de la electricitatea electrostatică poate servi încălțămintea ce conduce curentul electric, albituri, halat, etc. adică tot ce asigură legătura electrică a corpului omului cu pământul.

În majoritatea monitoarelor moderne problema câmpului electrostatic este parțial rezolvată prin introducerea tehnologiei antistatice. Datorită acestei tehnologii câmpul electrostatic se micșorează până la 10% din intensitatea inițială a acestuia. În afară de această majoritatea ecranelor protectoare, care micșorează iradierea ionizată, mai sigură și atenuarea considerabilă a câmpului electrostatic.

Câmpul electromagnetic creat de monitor este de asemenea un factor dăunător sănătății.

Influența câmpurilor electromagnetice de mare intensitate asupra omului constă în absorbția de către țesuturile corpului uman a energiei, însă influența principală îi revine câmpului electric. Nivelul de influență a câmpurilor electromagnetice asupra omului depinde de frecvență, de puterea emisiei, de durata acțiunii, de regimul de emisie (prin impulsuri sau continuu), și de asemenea de proprietățile individuale ale organismului. Influența câmpului electric de frecvență joasă provoacă dereglări în activitatea funcțională a sistemului cardio-vascular, și chiar la schimbări privind componența sângelui.

Influența câmpului electromagnetic de frecvență înaltă se reflectă sub forma efectului termic, care duce la ridicarea temperaturii corpului, la supraîncălzirea locală a țesuturilor corpului și a organelor cu o termoreglare slabă. Ca rezultat unii lucrători suferă din cauză insomniei, simt dureri în regiunea inimii, dureri de cap, ușor obosesc.

Pentru a micșora puterea de emisie a sursei câmpului electromagnetic pot fi utilizate următoarele mijloace tehnice:

utilizarea unui astfel de regim de lucrul, în care dispozitivul lucrează cu o putere mai mică decât cea proiectată;

lichidarea locurilor de emisie suplimentară;

micșorarea undelor reflectate prin ajustarea sarcinilor, etc.

Alegerea corectă a regimului de lucru a personalului și a utilajului permite micșorarea prezenței omului în zona de acțiune a câmpurilor electromagnetice.

Utilizarea sistemelor de dirijare la distanță cu utilajul permite personalului să-și îndeplinească funcțiile în afara zonei de acțiune a câmpurilor electromagnetice.

Procesul de ecranare, des utilizat cu scopul de micșora influența câmpurilor electromagnetice, utilizează fenomenul de absorbție și reflectare a energiei câmpului electromagnetic. Pentru confecționarea ecranului se utilizează materiale cu o conductibilitate electrică înaltă (aluminiu, cupru, oțel), și cu proprietăți de absorbție și reflectare sub formă de foi și plasă. Ecranele obligatoriu se unesc la pământ.

Eficacitatea acțiunii de ecranare a materialului se caracterizează prin adâncimea infiltrării câmpului electromagnetic în ecran, care depinde de materialul de confecționare.

Adâncimea infiltrării a frecvențelor înalte și supraînalte în ecran de obicei nu întrece un milimetru, astfel grosimea ecranului se alege din considerente constructive.

7. Analiza condițiilor de muncă. Factorii dăunători și periculoși la locul de lucru.

Analiza condițiilor de lucru și aprecierea factorilor dăunători se efectuiază conform cerințelor și standardelor elaborate special de comisiile pentru Tehnica Securității care sunt ca criterii de bază pentru analiza condițiilor la locul de lucru. Analiza se efectuiază conform STAS 12.2.032-78

Acest standard stabilește cerințele ergonomice comune către locurile de muncă, unde lucrul se efectuează din poziția așezat. Standardul nu stabilește cerințe către locurile de muncă ale mijloacelor de transport, mașinilor, instalațiilor ce se mișcă în procesul de muncă, către studenți și elevi și slujitorii armatei.

Starea comună

Locul de muncă cu îndeplinirea lucrului în poziția așezat se organizează la un lucru ușor care nu cere deplasarea liberă a lucrătorului și la un lucru de greutate medie în cazul unor anumite caracteristici ale procesului tehnologic.

Construcția locului de muncă și aranjarea tuturor elementelor (scaun, mijloace de reflectare a informației ș.a.) trebuie să corespundă cerințelor fiziologice, psihologice, antroponometrice și caracterului muncii.

Locul de muncă trebuie să fie organizat conform cerințelor standardelor, condițiilor tehnice și (sau) indicațiilor metodice asupra protecției muncii.

Caracteristicile dimensionale a locului de muncă

Îndeplinirea operațiilor în limitele zonei accesibile câmpului motoric trebuie să fie asigurată de către construcția locului de muncă. Zonele accesibile ale câmpului motoric în plan orizontal și vertical, pentru un om de mărime medie sunt arătate în fig.4.1 și fig.4.2.

Îndeplinirea operațiilor “des” și “foarte des” trebuie să fie asigurată în limitele zonei de acces ușor și a zonei optimale a câmpului motoric (fig.3).

La proiectarea instalațiilor și organizarea locului de muncă trebuie luate în considerație indicii antroponometrici ai femeilor și bărbaților (în cazul când lucrează numai bărbați sau numai femei).

De către construcția instalațiilor și a locului de muncă trebuie să depindă poziția optimală a lucrătorului ce poate fi atinsă prin regularea:

înălțimii suprafeței de lucru, a scaunului și suportului pentru piciore;

înălțimii scaunului și suportului pentru piciore (când înălțimea suprafeței locului de muncă nu se regulează).

În cazul când reglarea suprafeței de lucru și suportului pentru piciore este imposibilă, atunci se permite proiectarea și confecționarea utilajului cu parametrii neflexibili ai locului de muncă. În acest caz, valorile numerice ale acestor parametri sunt:

Tab.4.1

Valorile numerice ale parametrilor neflexibili ai locului de muncă

.

Forma suprafeței de lucru trebuie aleasă conform caracterului muncii executate. Ea poate fi dreptunghiulară, poate avea tăietură pentru corpul lucrătorului sau adâncitură pentru mașinile de masă.

4.8. Cerințele ergonomice privind locul de muncă.

Ergonomia și estetica procesului de producere sunt părți componente ale culturii procesului de producere, adică complexului măsurilor de organizare a muncii îndreptate spre crearea condițiilor de lucru prielnice. La baza ridicării culturii de muncă stau cerințele organizării științifice a procesului de muncă. Cultura procesului de muncă poate fi atinsă prin organizarea corectă a procesului de muncă și a relațiilor între coloboratori, organizarea locurilor de muncă, transformarea estetică a mediului înconjurător. Pentru crearea condițiilor de muncă plăcute este necesar de a considera particularitățile psihofiziologice a omului și condițiile igienice generale.

Iluminarea rațională a încăperilor de lucru stă la baza ridicării eficacității de lucru, preîntâmpină oboseala generală și a văzului, crează condiții psihologice optimale și determină dispoziția bună. Iluminarea naturală suficientă creează simțul de legătură directă cu mediul înconjurător. Este necesar de subliniat acțiunea biologică binevenită a razelor solare. De aceea este necesar de amplasat locurile de muncă în așa mod încât ele să nimerească în zona atingerii razelor solare. În dependență de condițiile de muncă și particularitățile lucrului îndeplinit, pentru iluminarea artificială pot fi folosite instalațiile de iluminat, generale și locale, cu o anumită caracteristică de lumină. Lămpile de lumină directă au fost folosite limitate din cauza creării umbrelor abrupte. Lămpile de lumină reflectată pot fi folosite în cazuri când este necesitatea de o lumină omogenă și slabă. Lămpi de lumină semireflectată ce sunt echipate cu abajur din sticlă mată, care posedă proprietăți de a dispersa lumina se află pe masa de lucru. În calitate de instalație de iluminat general este recomandabil de folosit lămpi cu lumina dispersată. Lămpile de iluminare locală trebuie să fie mobile și la necesitate să asigure schimbarea direcției luminii. Fiecare loc de muncă, indiferent de amplasarea lui față de ferestre trebuie să aibă și instalație de lumină locală. Este recomandabil de folosit lămpi luminescente, spectrul luminii cărora aproape coincide cu cel al luminii naturale. Pentru a exclude reflectarea razelor directe ale luminii de pe ecranul monitorului instalațiile de iluminare se aranjează pe ambele părți de la locul de muncă, paralel cu direcția văzului operatorului, și peretele cu ferestre (fig.4.4).

1 – ferestre;

2 – instalațiile de iluminat;

3 – locul de muncă;

O astfel de amplasare a instalațiilor de iluminat permite de a le conecta consecutiv în dependență de mărimea iluminatului natural și exclude iritarea ochilor de către linii alterate de lumină și umbră, care apare la amplasarea lor paralelă.

Oformare cu culori a încăperilor și înverzirea lor nu numai micșorează tensiunea nervoasă dar și permanent susține buna dispoziție a lucratorilor și inspirația creativă în lucru.

Culoarea încăperilor de lucru influențează esențial asupra iluminării, stării psihofiziologice a omului, ansamblului arhitectural al încăperii. Este cunoscut că nuanțele întunecate au proprietatea de a consuma o parte mare a luminii și prin aceasta micșorează iluminarea încăperii. Pentru oformarea cu culori a încăperilor se propune de a folosi în primul rând acele culori care reflectă cel puțin 40-50% de lumină care cade pe o suprafață. Culorile pentru oformare a încăperilor trebuie să fie alese în conformitate cu condițiile climaterice. Culorile galben-verzi și verde-albastru influențează în mod liniștitor, pe când culorile albastru deschis, albastru, violet pot influența în mod depresiv. La oformare cu culori a încăperilor trebuie de luat seamă de amplasarea ferestrelor, particularitățile arhitecturale ale încăperilor. Pentru asigurarea condițiilor de lucru optimale, oformarea cu culoare trebuie să fie aleasă ținând cont de culorile monitorului. În cazul paletei monocrome, peretele înaintea operatorului trebuie să fie vopsite cu culoarea verde deschisă sau bej, iar în cazul paletei colorate – culoarea bej.

Un rol important îl joacă organizarea locului de muncă, care trebuie să satisfacă cerințele comodității a efectuării lucrului și economisirii energiei și a timpului operatorului și utilizării raționale ale suprafețelor de lucru. Este necesar de stabilit zonele de atingere a mâinilor operatorului de display, imprimantă și alte dispozitive periferice. Zonele date sunt stabilite pe baza datelor antropometrice ale corpului uman, permit de a amplasa corect elementele de dirijare.

Mișcările lucrătorului trebuie să fie de așa fel, ca grupurile de mușchi ale lui vor fi încărcate omogen, iar mișcările neproductive vor fi excluse.

Locurile de muncă trebuie să fie aranjate tot în conformitate cu cerințele comodității lucrului și optimizării mișcării. Locul de muncă de obicei este constituit dintr-un birou, scaun, o poliță pentru literatura profesională des folosită. Distanțele între componentele menționate trebuie să fie optimale, care nu limitează mișcările și în acelaș timp nu provoacă mișcări de prisos.

4.9. Condiționarea aerului.

Parametrii necesari al microclimei în încăperile de producție se asigură prin diferite metode. Pentru menținerea normelor aflării substanțelor dăunătoare în aer la locul de lucru se iau măsuri aspre: izolarea izvoarelor de substanțe dăunătoare, limitarea timpului de aflare a oamenilor în încăperile cu conținutul atmosferic dăunător, folosirea tehnologiilor avansate pentru micșorarea conținutului de substanțe dăunătoare în aer.

Una din tehnicile de folosire în procesul de producție pentru eliminarea substanțelor dăunătoare din aerul zonei de lucru este ventilarea. Sistemele de ventilare asigură parametrii necesari ai microclimei în aerul de lucru. Ventilarea este divizată în două categorii în dependență de natura acesteia: ventilarea naturală și ventilare artificială.

La ventilarea artificială schimbul de aer se efectuiază cu ajutorul ventilatorului prin sistemele de canale cu aer. Reieșind din principiul de lucru a ventilatorului, ventilarea artificială se clasifică în următoarele categorii: de tragere, de extragere, de tragere-extragere. În sistemele de ventilare artificială aerul tras în încăperea de lucru poate fi uscat, umezit, răcit. Adică parametrii aerului tras, la ventilarea artificială pot fi schimbați.

În prezent pentru asigurarea normativelor de ventilare a aerului zonei de lucru sunt folosite dispozitive de condiționare a aerului. Cu ajutorul dispozitivului de condiționare aerul poate fi uscat, umezim, ozonat, dezodorat, răcit sau încălzit.

Conform normativelor sanitar-igienice fiecărui lucrător trebuie de-i asigurat de la 20 m3/oră până la 30 m3/oră. Raportul între volumul încăperii și numărul de persoane care lucrează în această încăpere nu trebuie să fie mai mic decât 20 m3.

În lipsa substanțelor dăunătoare în încăpere, dacă volumul de aer pentru un lucrător e mai mare de 40 m3, normativele de ventilare nu sunt reglementate.

Deoarece sala laboratorului catedrei intră în categoria I – raportul volumului de aer din laborator și numărul de persoane care se află în laborator în timpul lucrărilor este mai mic decât 20 m3 pentru o persoană, aerul zonei laboratorului trebuie ventilat. Volumul de aer care trebuie să fie tras să fie în diapazonul de 20m3/oră pentru o persoană până la 30 m3/oră. Deci trebuie de ales un așa tip de dispozitiv de condiționare care ar asigura cerințele expuse mai sus.

4.10. Cerințele securității tehnice la începutul lucrului

Până la începutul propriu zis a lucrului practic în laborator, studenții sunt obligați să studieze locul său de lucru: dislocația dispozitivelor aflate sub tensiune, a întreprinderilor de curent, caracteristica tehnică a utilajului, instrucțiunile de exploatare a dispozitivelor folosite la efectuarea lucrărilor de laborator. Trebuie de studiat principiul de lucru a echipamentului și metodele de operare inofensive în timpul lucrului.

4.11.Cerințele securității tehnice în timpul de lucru.

Este interzisă cuplarea echipamentului la rețea fără permisiunea persoanei responsabile de lucrări; cuplarea în rețea a echipamentului care în timpul efectuării lucrării de laborator nu este folosit.

Studenții neatestați de lector nu sunt admiși la lucrări de laborator.

În procesul efectuării lucrării de laborator se interzice categoric:

abaterea de la subiect cât și atragerea altora;

părăsirea locului de lucru lăsând utilajul sub tensiune;

efectuarea lucrului de reparație a utilajului aflat sub tensiune.

Dacă în procesul de lucru apar cazuri ieșite din comun (miros de izolație arsă, fum) utilajul se decuplează, urgent de la rețea informând despre aceasta dirigintele de lucrări sau responsabilul de laborator.

4.12.Acțiuni în cazuri fatale.

Dacă vreo persoană nimerește sub tensiune, este necesar de urgență de decuplat tensiunea, despre ce se informează dirigintele de lucrări.

Dacă persoana în cauză a rămas în conștiință trebuie să-i creăm condiții de liniște și odihnă. Apoi în caz de necesitate chemăm medicul. Dacă individul a pierdut cunoștința și nu respiră este necesar de a-i face respirație artificială, chemând totodată salvarea. Respirația artificială se aplică până vine medicul sau până se restabilește respirația.

Pentru toate cazurile fatale se fac procese verbale conform regulamentului.

4.13. Securitatea antiincendiară.

Incendiu se numește procesul necontrolat de ardere în afara unui loc de ardere special amenajat, ce aduce daune materiale.

În cadrul oricărei organizații, sau întreprinderi trebuie să existe mijloace de anunțare, de apel rapid la serviciile orășenești antiincendiare în cazul apariției incendiului. Pentru obiectele de o importanță majoră sau periculoase, este recomandată posibilitatea legăturii telefonice directe cu secția antiincendiară orășenească. Semnalizarea antiincendiară se execută cu ajutorul diferitor sisteme. Pentru a anunța despre incendiu se utilizează legătura telefonică (901), legătura radio, sirena, semnalizarea cu ajutorul clopotelor etc. Mijloacele de anunțare despre incendiu trebuie să fie disponibile toate 24 ore.

Semnalizarea incendiului se execută de diferite sisteme. Cel mai simplu și mai des utilizat este semnalizatorul manual, care se activează prin apăsarea butonului. Așa semnalizatoare se instalează pe scări, în paliere și sânt vopsite în culoarea roșie.

În timpul de față larg se utilizează semnalizatoarele automate, care conform principiului de lucru se împart în cele termice, de fum, combinate și optice.

Semnalizatoarele termice de acțiune maximă acționează la deformarea unei plăci bimetalice, la încălzirea ei până la 60, 80, 100 °C în dependență de reglaj.

În semnalizatoarele termice semiconductoare, în calitate de elemente sensibile sânt termorezistențele, din cauza cărora se schimbă curentul în rețea la încălzirea lor.

Termosemnalizatoarele diferențiale reacționează la ridicarea rapidă a temperaturii (la 30°C timp de 7 secunde), iar în calitate de element sensibil se folosește elementul la încălzirea căruia apare termo-FEM.

În semnalizatoarele de fum în calitate de element sensibil se utilizează camera de ionizare, în care sub acțiunea izotopului radioactiv (plutoniu-239) apare un curent de ionizare. Apariția fumului în cameră mărește consumul de raze ceea ce cauzează micșorarea curentului de ionizare.

În semnalizatoarele combinate se folosește interconectarea semnalizatorului de fum cu cel termic. La camera de ionizare se mai conectează în plus încă o termorezistență.

Semnalizatoarele combinate reacționează atât la apariția fumului, cât și la schimbarea temperaturii. Semnalizatoarele optice reacționează la razele ultraviolete ale spectrului flăcării, deoarece elementul sensibil reprezintă contoarele de fotoni. Semnalizatoarele de diferite tipuri pot controla suprafețe de la 15 până la 100 m2.

Semnalizatoarele de fum și cele combinate nu se instalează în încăperi umede și prăfuite, sau în încăperi în care se conțin vapori de acizi, baze, sau unde temperatura este mai mare decât 80 °C, deoarece în așa locuri poate avea loc acționarea falsă ale semnalizatoarelor.

4.13.1. Cauzele apariției incendiilor.

Procesul de ardere este posibil în cazul când este prezentă substanța arzătoare, sursa de aprindere și oxidantul, care în cele mai dese cazuri este oxigenul, ce se conține în aer. La reducerea concentrației oxigenului din aer până la 12-14% arderea majorității substanțelor se oprește. Procesul de ardere este posibil și în lipsa oxigenului – deoarece hidrogenul, stibiul și unele metale ard în clor. Unele substanțe (turba, cărbunele, funinginea, cârpele uleioase), numite piriforme pot să se autoinflameze la contactul cu aerul. Auto-aprinderea acestor substanțe are loc în urma proceselor chimice, termice sau microbiologice. Substanțele se încălzesc sub acțiunea căldurii ce vine din afară, ce se elimină în timpul reacțiilor chimice, și de asemenea în rezultatul acțiunii micro-organismelor.

În procesul de producție, incendiul poate apare în urma unor cauze de ordin electric sau ne electric.

La cauzele de ordin ne electric se referă:

funcționarea proastă a instalațiilor de producție și dereglarea procesului tehnologic; comportarea iresponsabilă sau neatentă cu focul (fumatul, lăsarea fără supraveghere a dispozitivelor de încălzire);

construcția incorectă sau dereglarea sistemului de ventilare;

autoinflamarea materialelor.

La cauzele de ordin electric se referă:

scurtcircuitul;

supraîncărcarea conductoarelor;

rezistența mare de trecere;

scânteierea;

electricitatea statică și descărcarea fulgerului;

arcul electric ce apare în timpul sudării electrice și în timpul operațiilor greșite cu aparatajul de comutare;

instabilitatea tensiunii electrice din rețea – ca rezultat se aprind unele circuite integrate din calculator, sau monitor, etc.

4.13.2. Securitatea antiincendiară în sălile de calcul.

Pentru a analiza nivelul securității incendiare a locurilor de muncă, a zonelor de producție, a sălilor de calcul se folosește următoarea clasificare :

1.Clasificarea materialelor de construcție și construcțiilor după nivelul de inflamabilitate:

neinflamabile;

greu inflamabile;

inflamabile;

2. Clasificarea construcțiilor după nivelul rezistență la incendiu (limita nivelului de rezistența la incendiu – timpul în ore din momentul începerii incendiului până la momentul apariției crăpăturilor).

3. Clasificarea încăperilor după RCIE ("Regulile de Construcție a Instalațiilor Electrice"):

cu pericol de explozie;

cu pericol de inflamare.

Criteriile de apreciere:

Conținutul de substanțe inflamabile;

Regimul termic de prelucrare.

4. Clasificarea proceselor de producție după pericolul incendiar:

cu pericol de explozie;

cu pericol de explozie și inflamare;

cu pericol de inflamare;

fără pericol de inflamare;

Conform primei clasificări (clasificarea materialelor de construcție și construcțiilor după nivelul de inflamabilitate) sala de calcul este ne inflamabilă deoarece sunt prevăzute multe măsuri de prevenire a incendiului cum ar fi: sisteme de semnalizare, podele din metal, mese metalice, pereții în sala de calcul se acoperă cu substanțe nearzătoare.

După clasificarea a doua (clasificarea construcțiilor după nivelul rezistență la incendiu), de obicei sălile de calcul se află în clădiri construite sau din beton armat sau piatră (pentru instituțiile de învățământ). Ambele materiale de construcție au o rezistență la incendiu mare – pereții în sala de calcul se acoperă cu substanțe nearzătoare.

După clasificarea a treia (după Regulile de Construcție a Instalațiilor Electrice), luând în considerație conținutul mic de substanțe inflamabile și regimul termic de prelucrare, sălile de calcul pot fi caracterizate – cu pericol mic de inflamare.

Sălile de calcul după pericolul incendiar a proceselor de producție se referă la categoria celor cu pericol de inflamare ceea ce se explică prin faptul, că în încăpere se găsesc substanțe inflamabile: de obicei, aceste săli sunt echipate cu utilaj care conține masă plastică, care totuși arde. Trebuie însă de menționat, în ultimul timp masa plastică utilizată la fabricarea tehnicii de calcul are o astfel de componență chimică, care nu arde sau care se stinge după primele secunde de ardere. În sala de calcul de obicei lipsesc așa atribute cum ar fi: covoare, obiecte din lemn, dulapuri cu cărți, etc. Reiese că, cu toate că pericolul de inflamare există, el este foarte mic.

Securitatea antiincendiară poate fi asigurată prin măsuri de profilaxie antiincendiară și prin respectarea regulilor de prevenire a incendiului. Noțiunea de profilaxie antiincendiară include un complex întreg de măsuri, necesare pentru preîntâmpinarea apariției incendiului sau reducerea urmărilor lui.

Concluzii

Lucrarea dată are un conținut amplu în ceea ce privește algoritmii genetici și posibilitățile de implementare a lor în diferite domenii. Cele două capitole conțin informații noi și interesante despre algoritmii genetici, și pote fi de mare folos celor interesați în domeniul inteligenței artificiale.

Exemplul de utilizare a algoritmilor genetici pentru bursa de valori care este o aplicație de viitor (asupra programului se mai lucrează încă), va avea o mare importanță în dezvoltarea economiei și va ușura cu mult lucrul consultanților busei de valori.

Algoritmii genetici sunt bine adaptați pentru diferite forme de organizare și crează optimizatori universali foarte buni. O calitate deosebită a algoritmilor genetici este faptul că, unele aplicații indică o mare parte a resurselor către găsirea și/ sau corectarea greșelilor, iar întrebuințarea repetată a algoritmilor genetici micșorează necesitatea precauțiilor, deoarece mijloacele de corectare a greșelilor sunt deja incluse în ei. Chiar dacă o parte din program este puțin deteriorat, atunci algoritmul va continua să funcționeze la fel de bine ca și în cazul când n-ar fi greșeli. Algoritmii genetici sunt destul de flexibili și greșelile nu devin un factor critic al sistemului. Se poate întâmpla ca să fie nevoie de a rezolva o problemă, iar resursele accesibile pentru îndeplinirea ei se schimbă neîncetat. Algoritmii genetici se adaptează ușor la schimbările ce parvin și completează regiuni accesibile de memorie. Chiar cu o memorie foarte limitate și cu limite temporare, algoritmii genetici pot da rezultate destul de bune, deși este evident că ei lucrează mult mai bine când resursele sunt mai bogate.

Algoritmii genetici au și mici neajunsuri, așa ca lipsa garanției faptului că una și aceeași cale evoluționistă nu va fi parcursă de mai multe ori. În acest caz trebuie să fim doar puțin mai atenți pentru a nu exclude căile bune de dezvoltare.

După cum am văzut, algoritmii genetici prezintă efectiv o mulțime de calități remarcabile:

o eficacitate exepțională

o mare robustețe

un model valid atât pentru probleme de optimizare numerică, cât și de optimizare combinatorică

o implementare simplă

-un proces paralel.

Capitolul trei conține aprecierea economică a proiectului care include calcularea parametrilor grafului rețea și cheltuielile totale ale proiectului (în total 3843 lei).

În capitolul patru sunt analizate condițiile de muncă, factorii dăunători și periculoși la locul de muncă.

Bibliografie

1. Oltean Mihai „Culegere de probleme cu rezolvări în Pascal”, Editura Libris,Cluj – Napoca.1997

2. Tomescu Ioan „Probleme de combinatorică și teoria grafurilor”, Editura didactică și pedagogică, 1981

3. Tomescu Ioan „Întroducere în combinatorică”, Editura tehnică, 1972

4. Knuth D.E. „The art of computer programming” Vol. I : Fundamental Algorithms

Addison Wesley, Reading, Mass, 1968

5. Berge C. „Theorie des graphes et ses application”, Dunod, Paris, 1967

6. Mihai Oltean „Proiectarea și implementarea algoritmilor”, Computer Libris Agora, 1998

7. Conspect, semestrul VIII,”Bazele logice ale inteligenței artificiale”

8. Conspect, semestrul VI „Managementul firmei”

9.Князевский ,Б.А.”Охрана труда” ,Москва ,”Высшая школа” 1982

10. Баклашов В. „Охрана труда на предприятиях связи” , Москва, 1981

Anexa 1

Listingul programului algoritmului genetic natural

program AlgoritmGeneticGeneral;

const MaxPopulatie=100; {numarul de cromozomi in populatie}

MaxIteratii=100;{numarul de iteratii ale algoritmului}

MaxElitism=2; {cati cromozomi sunt copiati din elitism}

MaxCrossOver=20;

{de cate ori apare incrucisarea intr-o populatie}

maxmutatie=1;

type

{Tcromozom=record

de cate ori apare mutatia intr-o populatie

cromozom:Byte;

fitness:Byte;

end; }

tdrum=array[1..10] of 0..10;

Tcromozom=record

drum:tdrum;

fitness:Byte;

end;

TPopulatie=array[1..MaxPopulatie] of TCromozom;

arr=array[1..100,1..100]of byte;

var populatieVeche, populatieNoua:TPopulatie;

i,j,N,contor,co, r1, r2,k:Byte;

NrPop:Byte;f:file of arr;a:arr;

procedure Citire;

begin

assign(f,'graf.in');reset(f);{read(f,n);}

for i:=1 to n do

begin for j:=1 to n do read(f,a);end;

write(f,a)

close(f);

end;

function CalculFitness(G:TCromozom):Byte;

begin

end;

procedure InitializeazaPopulatie;

var ok:boolean;

begin

Anexa 1 (continuare)

for i:=1 to MaxPopulatie do

begin if n+1=0 then n:=n+1;

populatieveche[i].drum[1]:=round(i/(n+1));

populatieveche[i].fitness:=1;

ok:=true;

k:=1;

while ok do

begin

ok:=false;

for j:=populatieveche[i].drum[k]+1 to n do

if a[populatieveche[i].drum[k],j]=1

then

begin

inc(k);

populatieveche[i].drum[k]:=j;

inc(populatieveche[i].fitness);

ok:=true;

break

end

end;

end ;

end;

procedure Elitism(NrMutatii:byte);

begin

Inc(NrPop);

populatieNoua[NrPop]:=populatieVeche[MaxPopulatie-i+1]

end;

procedure Crossover(g1,g2:TCromozom; var rez1,rez2:TCromozom);

var ok:boolean;

function indrum(nr:byte;dindr,dr:tcromozom):boolean;

var c:byte;

begin

if (nr=0) or (nr>dindr.fitness)

then begin indrum:=true; exit end;

for c:=1 to dr.fitness do

if dr.drum[c]=dindr.drum[nr]

then begin indrum:=true; exit end;

indrum:=false

end;

begin

Anexa 1 (continuare)

rez1:=g1; ok:=true;

while ok do

begin

ok:=false;

for i:=1 to g2.fitness do

if g2.drum[i]=rez1.drum[rez1.fitness]

then

if not indrum(i-1,g2,rez1)

then

begin

inc(rez1.fitness); ok:=true;

rez1.drum[rez1.fitness]:=g2.drum[i-1];

exit

end

else

if not indrum(i+1,g2,rez1)

then

begin

inc(rez1.fitness); ok:=true;

rez1.drum[rez1.fitness]:=g2.drum[i+1];

exit

end

end;

rez2:=g2; ok:=true;

while ok do

begin

ok:=false;

for i:=1 to g1.fitness do

if g1.drum[i]=rez2.drum[rez2.fitness]

then

if not indrum(i-1,g1,rez2)

then

begin

inc(rez2.fitness); ok:=true;

rez2.drum[rez2.fitness]:=g1.drum[i-1];

exit

end

else

if not indrum(i+1,g1,rez2)

then

begin

inc(rez2.fitness);ok:=true;

rez2.drum[rez2.fitness]:=g1.drum[i+1];

Anexa 1(continuare)

exit

end

end;

end;

procedure mutatie (var mutant:TCromozom);

begin

end;

procedure MutaRestul (NrMutati:Byte);

begin

for i:=1 to NrMutati do

begin

Inc(NrPop);

populatieNoua[NrPop]:=populatieVeche[1+Random(MaxPopulatie-MaxElitism)]

end

end;

procedure OrdoneazaDupaFitness(l,r:byte);

var i,j,x:integer;

y:TCromozom;

begin

i:=l;

j:=r; x:=populatieVeche[(l+r) div 2].fitness;

repeat

while populatieVeche[i].fitness<x do i:=i+1;

while x<populatieVeche[j].fitness do j:=j-1;

if i<=j

then

begin

y:=populatieVeche[i];

populatieVeche[i]:=populatieVeche[j];

populatieVeche[j]:=y;

Inc(i);Dec(j)

end;

until i>j;

if l<j then OrdoneazaDupaFitness(l,j);

if i<j then OrdoneazaDupaFitness(i,r);

end;

procedure SelectieParinti(var r1,r2:Byte);

begin

end;

procedure Afiseaza;

Anexa 1 (continuare)

begin

end;

begin Citire;

Randomize;

InitializeazaPopulatie;

OrdoneazaDupaFitness(1,Maxpopulatie);

for contor:=1 to MaxIteratii do

begin

NrPop:=0;

Elitism(MaxElitism);

for co:=1 to MaxCrossover do

begin

SelectieParinti(r1,r2);

CrossOver(populatieVeche[r1],populatieVeche[r2],

populatieNoua[NrPop+1],populatieNoua[NrPop+2]);

Inc(NrPop,2)

end;

MutaRestul(MaxPopulatie-NrPop);

populatieVeche:=populatieNoua;

for co:=1 to maxMutatie do

Mutatie(PopulatieNoua[1+random(maxPopulatie)]);

OrdoneazaDupaFitness(1,MaxPopulatie)

end;

Afiseaza;

end.

Anexa 2

Listingul programului de calcul a drumului maxim

program AlgoritmGeneticGeneral;

const MaxPopulatie=100; {numarul de cromozomi in populatie}

MaxIteratii=100;{numarul de iteratii ale algoritmului}

MaxElitism=2; {cati cromozomi sunt copiati din elitism}

MaxCrossOver=20;

{de cate ori apare incrucisarea intr-o populatie}

maxmutatie=1;

type Tcromozom=record

{de cate ori apare mutatia intr-o populatie}

cromozom:Byte;

fitness:Byte;

end;

TPopulatie=array[1..MaxPopulatie] of TCromozom;

var populatieVeche, populatieNoua:TPopulatie;

i,j,N,contor,co, r1, r2,k:Byte;

NrPop:Byte;

procedure Citire;

begin

end;

function CalculFitness(G:TCromozom):Byte;

begin

end;

procedure InitializeazaPopulatie;

begin

for i:=1 to MaxPopulatie do

begin

end ;

end;

procedure Elitism(NrMutatii:byte);

begin

Inc(NrPop);

populatieNoua[NrPop]:=populatieVeche[MaxPopulatie-i+1]

end;

procedure Crossover(g1,g2:TCromozom; var rez1,rez2:TCromozom);

begin

end;

procedure mutatie (var mutant:TCromozom);

begin

end;

procedure MutaRestul (NrMutati:Byte);

begin

Anexa 2 (continuare)

for i:=1 to NrMutati do

begin

Inc(NrPop);

populatieNoua[NrPop]:=populatieVeche[1+Random(MaxPopulatie-MaxElitism)]

end

end;

procedure OrdoneazaDupaFitness(l,r:byte);

var i,j,x:integer;

y:TCromozom;

begin

i:=l;

j:=r; x:=populatieVeche[(l+r) div 2].fitness;

repeat

while populatieVeche[i].fitness<x do i:=i+1;

while x<populatieVeche[j].fitness do j:=j-1;

if i<=j

then

begin

y:=populatieVeche[i];

populatieVeche[i]:=populatieVeche[j];

populatieVeche[j]:=y;

Inc(i);Dec(j)

end;

until i>j;

if l<j then OrdoneazaDupaFitness(l,j);

if i<j then OrdoneazaDupaFitness(i,r);

end;

procedure SelectieParinti(var r1,r2:Byte);

begin

end;

procedure Afiseaza;

begin

end;

begin Citire;

Randomize;

InitializeazaPopulatie;

OrdoneazaDupaFitness(1,Maxpopulatie);

for contor:=1 to MaxIteratii do

begin

NrPop:=0;

Elitism(MaxElitism);

Anexa 2 (continuare)

for co:=1 to MaxCrossover do

begin

SelectieParinti(r1,r2);

CrossOver(populatieVeche[r1],populatieVeche[r2],

populatieNoua[NrPop+1],populatieNoua[NrPop+2]);

Inc(NrPop,2)

end;

MutaRestul(MaxPopulatie-NrPop);

populatieVeche:=populatieNoua;

for co:=1 to maxMutatie do

Mutatie(PopulatieNoua[1+random(maxPopulatie)]);

OrdoneazaDupaFitness(1,MaxPopulatie)

end;

Afiseaza;

end.

Anexa 3

Listingul programului procedural de calșcul a componentei intern stabile maximale

Type Tmultime= set of 1..MaxN;

Tcromozom= record

Multime: Tmultime;

Fitness: byte

End;

Procedure Citire;

Begin

Assign(f,’graf.in’); reset(f); readln(f,n);

For j:=1 to N do

begin

for j:=1 to N readln(f, a[i,j]);

Readln(f);

End

End;

Procedure IinitializeazaPopulatie;

Var ok: boolean;

Begin

For i:=1 to MaxPopulatie do

Begin

PopulatieVeche[i].multime:=

populatieVeche[i].multime+[i mod N+1];

populatieVeche[i].fitness:=1;

for j:=i mod N+2 to N do

begin

ok:=true;

for k:=1 to N do

if (k in populatieVeche [i].multime) and (a [k,j]=1)

then ok:=false;

if ok

then

begin

populatieVeche[i].multime:=populatieVeche[i]. Multime+[j];

inc (populatieVeche[i]. fitness);

end

end

end

end;

procedure crossover(g1,g2:Tcromozom; var rez1, rez2:TCromozom);

begin

rez1:=g1;

Anexa 3 (continuare)

for i:=1 toN do

if i in g2.multime

then

begin

j:=1;

while (j<=N) and not (( j in rez1.multime) and (a[i,j] =1) do

if j=N+1 then rez1.multime:=rez1.multime+[i];

Inc(rez1.fitness);

End;

Rez2:=g2;

For i:=1 to N do

If i in g1.multime

Then

Begin

J:=1;

While (j<=N) and not (( j in rez2.multime) and (a[i,j] =1) do

if j=N+1 then rez2.multime:=rez2.multime+[i];

Inc(rez2.fitness)

End

End;

Procedure Mutatie(mutant:TCromozom);

Var v, r:byte;

Begin

r:=1+random(maxPopulatie);

v:= 1+random(N);

mutant:=populatieVeche[r];

if v in mutant ‘.multime

then mutant.multime:=mutant.multime-[v]

end;

procedure afisare;

begin

for i:=1 to N do

if i in populatieVeche[MaxPpopulatie].multime

then writeln(i,’ ’)

end;

Anexa4

Listingul programului procedural de calcul al rădăcinilor ecuației de gradul doi

type Tsolutie=record

x1,x2:integer

end;

Tcromozom=record

Sol:Tsolutie;

Fitness:byte

End;

Tpopulatie=array[1..MaxPopulatie] of Tcromozom ;

Var populatieVeche, populatieNoua:Tpopulatie;

PopulatieIntermediara:Tpopulatie;

F:text;

I,j,contor,NrPop, co, r1, r2:byte;

A,b,c:integer;

procedure Citire;

begin

assign (f,’ec.in’); reset(f);

readln(f,a,b,c);

close(f);

end;

procedure InitializeazaPopulatie;

var ok:boolean;

begin

for i:=1 to MaxPopulatie do

with populatieVeche[i] do

begin

sol.x1:=random(101)- 50;

sol.x2:= random(101)- 50;

fitness:= -Abs (a*sol.x1 + b*sol.x1 + c)+

Abs ( a*sol.x2 + b*sol.x2 + c)

End

End;

Procedure Crossover(g1,g2:Tcromozom; var rez1,rez2:TCromozom);

Begin

Rez1:=g1; rez1.sol.x2:=g2.sol.x2;

Rez2:=g2; rez2.sol.x1:=g1.sol.x1;

With rez1 do

Fitness:= -Abs(a*sol.x1 * sol.x1+ b*sol.x1 + c)+

Abs ( a*sol.x2 * sol.x2+ b*sol.x2 + c)

End;

Procedure Mutatie (var mutant:TCromozom);

Anexa 4(continuare)

Var i:=byte;

Begin

Mutant:=populatieVeche[1+random(MaxPopulatie)];

With mutant do

Begin

I:=random(2);

If i=0

Then

Begin

I:=random(2);

If i=0 then sol.x1:=sol.x1-random(3)

Else sol.x2:=sol.x2-random(3)

End;

Fitness:= -Abs(a*sol.x1 * sol.x1+ b*sol.x1 + c)+

Abs ( a*sol.x2 * sol.x2+ b*sol.x2 + c)

End

End;

Procedure Afiseaza;

Begin

With populatieVeche[maxPopulatie].sol.do

Writeln(x1,x2)

End;

Anexa 5

Anexa 6

Anexa 8