Algoritmii genetici in aplicatii medico-farmaceutice
S.L. M.V. Todor1, Prep. dr. A. Robotin2, As. dr. C. Todor3,
S.L. O. Florea1
Disciplina Informatica Medicala, FMF, Universitatea din Oradea
Catedra Propedeutica, FMF, Universitatea din Oradea
Catedra de Pediatrie, FMF, Universitatea din Oradea
INTRODUCERE
În Inteligenta Artificiala îndeplinirea oricarei sarcini poate fi privita ca rezolvarea unei probleme iar aceasta poate fi gândita ca o cautare în spatiul solutiilor posibile. Aceasta cautare poate fi ghidata de o functie de performanta. Procesul de cautare este în acest caz însotit de un proces de optimizare : dintre solutiile posibile suntem interesati de cea mai buna.
Uneori ne putem multumi cu o solutie suficient de bun 616f56g 59; (aproximativ optima). Pentru probleme de mare complexitate, gasirea solutiei optime, sau chiar a uneia acceptabile, este dificil de realizat. Tehnicile clasice fie nu sunt aplicabile fie necesita un timp prea mare de lucru. Solutionarea unor astfel de probleme se face cu ajutorul Algoritmilor genetici. Algoritmii genetici reprezinta tehnici de cautare si optimizare având ca punct de plecare un model biologic si anume acela al mostenirii genetice si a evolutiei naturale (Holland, 1975).
În cursul evolutiei, toate fiintele sunt confruntate cu problema adaptarii la un mediu complicat, în continua schimbare, sau ostil. În acest proces fiecare specie "învata", iar cunoasterea pe care a câstigat-o este codificata în cromozomii speciei. Evolutia este asadar un proces care are loc la nivelul cromozomilor. Caracterisiticile unei fiinte vii sunt stabilite printr-un proces de decodificare a cromozomilor sai. Codificarea si decodificarea informatiei genetice la nivelul cromozomilor nu este pe deplin elucidata.
In general, orice sarcina abstracta care trebuie îndeplinita, poate fi privita ca fiind rezolvarea unei probleme, care, la rândul ei, poate fi perceputa ca o cautare în spatiul solutiilor potentiale. Deoarece, de obicei, cautam cea mai buna solutie, putem privi acest proces ca fiind unul de optimizare. Pentru spatii mici, metodele clasice exhaustive sunt suficiente; pentru spatii mari, pot fi folosite tehnicile speciale ale inteligentei artificiale.
Metodele calculului evolutiv se numara printre aceste tehnici; ele folosesc algoritmi ale caror metode de cautare au ca model câteva fenomene naturale: mostenirea genetica si lupta pentru supravietuire. Cele mai cunoscute tehnici din clasa calculului evolutiv sunt algoritmii genetici, strategiile evolutive, programarea genetica si programarea evolutiva. Exista si alte sisteme hibride care încorporeaza diferite proprietati ale paradigmelor de mai sus; mai mult, structura oricarui algoritm de calcul evolutiv este, în mare masura, aceeasi. Ín ultimii 30 de ani, s-a manifestat un mare interes în rezolvarea problemelor de sistem bazate pe principiile evolutiei si ereditatii. Astfel de sisteme mentin o populatie de solutii potentiale, ele au unele procese de selectie bazate pe fitness individual, si cativa operatori genetici.
MATERIAL SI METODA
Algoritmii Genetici sunt o familie de modele inspirate de teoria evolutiei, sunt programe inteligente capabile sa solutioneze probleme folosind un conceptul al evolutiei speciilor. Acesti algoritmi codifica solutiile posibile ale unor probleme specifice într-o structura de date de tip cromozom si aplica acestor structuri operatori de recombinare, pentru a pastra informatia utila.
Un cromozom este un vector sau un sir de gene. Pozitia unei gene este numita locusul ei. Valorile pe care le poate lua o gena sunt numite alele, sunt multimi finite de numere întregi, intervale de numere reale, sau chiar structuri complexe de date. Alele variaza de la un locus la altul.
Implementarea unui algoritm genetic începe cu o populatie de cromozomi (aleasa aleator). Se evalueaza, apoi, aceste structuri si se aloca facilitati reproductive astfel încât acei cromozomi, care reprezinta o solutie mai buna pentru problema tinta, sa aiba mai multe sanse de a se reproduce decât acei cromozomi care sunt solutii mai putin bune. Definirea unei solutii bune se face în raport cu populatia curenta.
Într-un sens mai larg, algoritm genetic este orice model bazat pe ideea de populatie si care foloseste selectie si operatori de recombinare pentru a genera noi puncte într-un spatiu de cautare. Multe modele au fost introduse de cercetatori dintr-o perspectiva experimentala. Cercetatorii sunt orientati spre aplicatii, fiind interesati de algoritmii genetici doar ca mijloace de optimizare.
Structura unui algoritm genetic este identica, în esenta, cu cea a unei proceduri evolutive. Cromozomii utilizati au lungime constanta. Populatia (generatia) P(t + 1) la momentul (t+1) se obtine retinând toti descendentii populatiei P(t) si stergând apoi complet cromozomii generatiei precedente (P(t-1)). Numarul cromozomilor în fiecare generatie este constant.
STRUCTURA ALGORITMUL GENETIC FUNDAMENTAL
P1 Se pune t = 0.
P2 Se initializeaza aleator populatia P (t)
P3 Se evalueaza cromozomii populatiei P (t)
În acest scop se utilizeaza o functie de performanta ce depinde de problema data.
P4 Cât timp (non C) executa P4.1. Selecteaza cromozomii din P(t) care vor contribui la formarea noii generatii. Fie P1 multimea cromozomilor selectati.
P1 reprezinta o populatie intermediara.
P4. 2 Se aplica cromozomilor din P 1 operatorii genetici.
Cei mai utilizati sunt operatorii de mutatie si încrucisare. În functie de problema se pot alege si alti operatori (invesiune, reordonare, operatori speciali).
Fie P2 populatia astfel obtinuta (descendentii populatiei P(t)).
Se sterg din P1 parintii noilor indivizi obtinuti.
Cromozomii ramasi în P1 sunt atribuiti populatiei P2.
Se construieste noua generatie, punând :
P(t + 1) = P2.
Se sterg toti cromozomii din P(t).
Se pune t = t + 1.
Se evalueaza P(t).
Sfârsit Cât timp.
MODULELE UNUI ALGORITM GENETIC
Implementarea unui algoritm genetic se poate face utilizând modulele POPULAŢIE, EVALUARE si RECOMBINARE si MODIFICARE specifice algoritmilor evoluti.
MODULUL POPULAŢIE
Metoda de reprezentare : codificare binara sau
codificare reala.
Lungimea cromozomului : r.
Metoda de initializare : initializare aleatoare.
Metoda de stergere : sterge vechea populatie în întregime
(sau alta metoda).
Metoda de înlocuire : înlocuire cu noua generatie.
Metoda de selectie : metoda probabilista (de exemplu selectia uniforma cu metoda Monte Carlo).
Metoda de apreciere a adecvarii : evaluarea cu o functie de evaluare.
Dimensiunea populatiei : n 1
Numarul maxim de generatii : n2.
MODULUL EVALUARE
Functia de evaluare :
MODULUL RECOMBINARE sI MODIFICARE
Operatorii genetici utilizati:
Mutatia
Încrucisarea
Inversiunea
Parametrii algoritmului :
Probabilitatea de mutatie : Pm.
Probabilitatea de încrucisare : Pc.
Probabilitatea de inversiune : Pi.
REZULTATE sI DISCUŢII
Vom considera ca problema de rezolvat alegerea unui antibiotic dintr-o lista de 3 antibiotice la dispozitie si vom lua ca date ale problemei PENICILINA, TETRACICLINA si AMPICILINA. Ca si criterii de alegere vom considera pretul, spectru de actiune, viteza de actiune, reactii ale organismului. Pentru fiecare criteriu vom stabili nivele carora le vom asocia valori numerice astfel :
1-Viteza de reactie
- foarte mica - 0,2
- mica - 0,4
- buna - 0,5
- mare - 0,7
- foarte mare - 0,9
2- Pretul
- foarte mic - 0,9
- mic - 0,7
- bun - 0,5
- mare - 0,4
- foarte mare - 0,2
3 -Reactii ale organismului
-foarte slabe - 0,9
- slabe - 0,7
- ponderate - 0,5
- puternice - 0,4
- foarte puternice - 0,2
4 - Spectru de actiune
- foarte redus - 0,2
- redus - 0,4
- mediu - 0,5
- larg - 0,7
- foarte larg - 0,9
Calculatorul face codificarea binara a acestor valori, cu cât codificarea are mai putine cifre ea este mai exacta, de precizia codificarii depinde si acuratetea solutiei la problema data. Noi vom continua exemplificarea fara a mai face operatiunile de codificare si decodificare pe care le executa calculatorul respectiv inteligenta artificiala. Vom lua pe rând fiecare antibiotic si conform cu datele de fabricatie îl vom analiza functie de criteriile stabilite. În mod real aceste date sunt oferite inteligentei artificiale dupa care are loc operatiunea de optimizare si alegerea unei solutii optime astfel :
PENICILINA
Viteza de reactie - deoarece se administreaza injectabil are o viteza de reactie de 15-20 minute.
Pretul 5 lei doza.
Reactii ale organismului - necesita testare prealabila deoarece un numar mare de persoane sunt alergice.
Spectru de actiune larg.
TETRACICLINA
Viteza de reactie - are o viteza de reactie de 1 - 2 ore.
Pretul 3 lei pastila.
Reactii ale organismului - risc ponderat de alergii.
Spectru de actiune mediu.
AMPICILINA
Viteza de reactie - are o viteza de reactie de 1 - 2 ore.
Pretul 4 lei pastila.
Reactii ale organismului - risc slab de alergii.
Spectru de actiune redus.
Daca ar trebui sa alegem moto groso care din aceste medicamente este mai bun fara ca sa tinem cont de bolnavul caruia trebuie sa-l administram, datele ar fi suficiente, inteligenta artificiala ar atribui valori pentru fiecare criteriu si ar rezolva problema dând o solutie ideala astfel :
PENICILINA 1 - 0,7 ; 2 - 0,5 ;3 - 0,4; 4 - 0,7 total = 2,7
TETRACICLINA 1 - 0,2 ; 2 - 0,7 ; 3 - 0,5 ; 4 - 0,5 total = 1,9
AMPICILINA 1- 0,2 ; 2 - 0,7 ; 3 - 0,9 ; 4 - 0,4 total = 2,2
Solutia optima în acest caz va fi PENICILINA, dar trebuie sa aratam ca acest exemplu este unul foarte simplu, cum în realitate rar se întâmpla.
Am ales intentionat o problema simplificata la maxim pentru a face exemplul numeric cat mai usor de urmarit. Sa ne gândim daca mai existau si alte conditii, respectiv bolnavul caruia trebuia sa i se administrze unul din aceste antibiotice si daca acesta are diferite afectiuni pentru care unele antibiotice sunt contraindicate, o lista mai mare de antibiotice cu caracteristicile lor, problema se complica iar gasirea unei solutii chiar daca nu optima, dar macar acceptabila, necesita metode de optimizare mai compelxe în care se defineste o relatie de dominare între solutii.
CONCLUZII
Algoritmii genetici reprezinta un instrument al inteligentei artificiale care tinde sa se apropie din ce în ce mai mult de inteligenta umana în ajutorul careia vine, degrevând-o de operatii care ar aduce rutina si care ar ocupa un spatiu mare de timp.
Gasirea unei solutii optime într-un timp scurt mai mic de o secunda de multe ori este o necesitate a acestui secol în care viteza este conditia succesului. Sa ne gândim doar la pilotul automat al unor avioane care zboara cu viteze supersonice si care trebuie sa solutioneze probleme complicate într-un timp foarte scurt, sa ne gândim la procese tehnologice conduse de inteligenta artificiala unde sunt necesare decizii rapide, solutii optime care sa mentina buna functionare a sistemelor.
Putem sa ne dam seama de importanta inteligentei artificiale si a capacitatii acesteia de a solutiona probleme gândindu-ne la unele accidente când aceasta a dat solutii eronate si când racheta plecata în spatiu s-a frânt ca o surcica aducând moarte cosmonautilor, lacrimi celor ramasi si ambitie cercetatorilor de a merge înainte. Într-un timp relativ scurt aceasta inteligenta a patruns peste tot si s-a ajuns ca acum sa nu mai putem concepe dezvoltarea civilizatiei umane în absenta ei.
În orice domeniu sunt probleme si aplicatii pe care aceasta le solutioneaza înlocuindu-ne cu succes chiar si în probleme delicate prin înlaturarea subiectivismului care pe noi oamenii ne caracterizeaza si care nu întotdeauna este benefic în gasirea unei solutii optime.
Precum cercetarile din genetica au revolutionat cunoasterea despre lumea vie la fel si algoritmii genetici au revolutionat inteligenta artificiala deschizând calea înspre alegerea dintr-o multime de solutii a celei mai optime problema deosebit de importanta în zilele noastre.
Prezentarea realizata în acest proiect este simpla si are ca scop aducerea la cunostinta audi-toriului asupra celor mai sus aratate spre o întelegere cât de cât a fenomenului. În realitate complexitatea problemelor este mult mai mare si necesita un spatiu de studiu evoluat si cunostinte în domeniul matematicii, geneticii si informaticii mult mai avansate.
Lucrarea aceasta are ca scop sa aduca la cunostinta ca exista asemenea tehnici si care sunt principiile care au stat la baza lor, cunoasterea lor necesitând studii mult mai aprofundate si care nu ni le-am propus cu ocazia acestei lucrari. Sarcina unui algoritm genetic e sa descopere cromozomi din ce în ce mai buni, pâna la atingerea unei valori a raportului dintre evaluarea asociata unui sir si evaluarea medie a tuturor sirurilor populatiei (fitness) despre care se stie ca este optimala, sau pâna când algoritmul genetic nu mai poate aduce îmbunatatiri.
Ei sunt recomandati pentru aflarea solutiilor neliniare ale unor probleme atunci când nu este posibila modelarea matematica si nici euristica în domeniu.
Adevaratii profesionisti combina adesea cele mai variate tehnologii inteligente în scopul exploatarii avantajelor fiecareia, obtinând asa-numitele sisteme hibride. Sunt posibile combinari de genul:
folosirea retelelor neuronale la ajustarea parametrilor în sistemele expert fuzzy,
extragerea cunoasterii din retele neuronale pentru a fi utilizata în sistemele expert,
folosirea algoritmilor genetici la crearea unor retele neuronale mai compacte si mai eficiente,
folosirea unei retele neuronale pentru asistarea functionarii unui algoritm genetic,
folosirea algoritmilor genetici la reglarea parametrilor unui sistem expert fuzzy pentru controlul proceselor,
îmbunatatirea performantei unui sistem expert prin încorporarea rationamentului bazat pe cazuri, etc. Asemenea cercetari sunt în prezent în mare voga în cele mai specializate laboratoare ale lumii stiintifice.
probleme de optimizare - doar doua componente principale sunt dependente de problema de rezolvat : codificarea si functia de evaluare. Scopul este de a fixa parametrii în asa fel încât iesirea sa fie optima.Variabilele desemnând parametrii sunt reprezentati prin siruri binare iar functia de evaluare este parte a descrierii problemei.
algoritmul genetic canonic - consta în generarea populatiei initiale. Se aplica acestei populatii selectia pentru a obtine o populatie intermediara. Apoi se aplica recombinarea si mutatii pentru a crea o populatie urmatoare (next population). Acest proces de trecere de la populatia curenta la populatia urmatoare reprezinta o generatie în executia unui algoritm genetic.
alfabetele binare - utilizarea lor va rezulta în urma unor calcule simple. Un alfabet minimal maximizeaza numarul de hiperplane utilizabile pentru codificarea procesarii
Algoritmi genetici sunt algoritmi euristici, adica solutia gasita de ei nu este intotdeauna cea mai buna, dar se afla intr-o vecinatate a solutiei optime. Daca problema este complexa este indicata folosirea unui algoritm genetic.
Avantajul deosebit al algoritmilor genetici este dat de faptul ca solicita doar valorile functiei obiectiv.
Algoritmi genetici sunt robustii, gratie numarului mare de puncte pe care le considera la fiecare etapa.
Bibliografie
Abraham A. Grosan C. Ramos V. Stigmergic Optimization, 2006
Davis, L. (1989), Adapting operator probalities in genetic algorithms, in J. Schaffer (editor), Proceedings of the Third International Conference of Genetic Algorithms, Morgan Kaufmann Publishers, Los Altos, California.
Dumitrescu, D. (1995), Inteligenta Artificiala, Universitatea " Babes - Bolyai '', Cluj Napoca.
Fogel, L. J., Owens, A. J.,Walsh, M.J. (1966), Artificial Intelligence Through Simulated Evolution, Wiley, New York.
Fourman, M. P. (1985), Compaction of symbolic layout using genetic algorithms, in J. J. Grefenstette (editor), Proceeding of the First International Conference on Algorithms, Lawrena Erlbourn Associates.
Grefensette, J. J. (1991), Strategy acquisition with genetic algorithms, in L. Davis (ed) Handbok of Genetic Algorithms, Van Nostrand Rainhold, New York.
Holland, J. (1975), Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor.
Kaufman, S. A., Johnsen, S. (1991), Co-evolution at the edge of chaos: coupled fitness landcapes, poised states and co-evolutionary avalanches, in Artificial Life, II, C. G. Langton, C. Taylor, J. D. Farmer, S. Rasmussen (editori), Addison Wesley, Redwood City.
Kursawe, F. (1995), Towards self - adapting evolution strategies, in Proceedings of the Second IEEE Conference on Evolutionary Computation, IEEE Press, Piscataway.
Packard, N. H. (1988), Intrinsic adaption in a simple model for evolution, in Artificial Life, I., C. G. Langton (editor), Addison Wesley, Redwood City.
|
