Algoritm Genetic Aplicat unei Probleme Uniobiectiv

Se caută o soluţie optimă a structurii producţiei de medicamente (structură formată din 3 tipuri de medicamente: Plantusin sub formă de flacoane, Fenilbutazonă sub formă de blistere şi Augmentin sub formă de blistere) într-o perioadă de producţie, de exemplu, un schimb al unei zile.

Realizarea unei unităţi (flacon sau blister) din fiecare tip de medicament implică un cost şi aduce un profit unităţii producătoare.

Criteriul după care se alege o soluţie (o structură) ca fiind mai bună decât altele este realizarea maximului de profit aferent structurii respective – suma profiturilor aferente unităţilor din cele 3 tipuri de medicamente.

Restricţia impusă structurii este una singură: costul maxim permis pentru producerea medicamentelor într-un schimb.

Datele de intrare sunt

- numărul de tipuri de medicamente ce pot fi produse (3):

o flacoane de Plantusin,

o blistere de Fenilbutazonă,

o blistere de Augmentin,

- costurile impuse de producerea unei unităţi de tip de medicament (c):

o pentru un flacon de Plantusin (c[0] = 60 de mii de lei),

o pentru un blister de Fenilbutazonă (c[1] = 100 de mii de lei),

o pentru un blister de Augmentin (c[2] = 200 de mii de lei),

- profiturile aferente producerii unei unităţi de tip de medicament (pr):

o pentru un flacon de Plantusin (pr[0] = 50 de mii de lei),

o pentru un blister de Fenilbutazonă (pr[1] = 30 de mii de lei),

o pentru un blister de Augmentin (pr[2] = 100 de mii de lei),

- capacităţile de producţie pentru fiecare tip de medicament, într-un schimb:

o pentru Plantusin 200 de flacoane,

o pentru Fenilbutazonă 250 de blistere,

o pentru Augmentin 100 de blistere,

- costul maxim permis pentru producţia dintr-un schimb (cmax = 40 000 de mii de lei),

- numărul maxim de indivizi acceptaţi în populaţie - nmax,

- rata de mutaţie genetică - 0.02,

- numărul de indivizi din prima generaţie – nr.

Modelul matematic

Structura producţiei (deci forma soluţiei) rezultă din matricea bidimensională:

q[nr_maxim_indivizi_in populatie][3].

Individul i este q[i][j] cu 3 componente (q[i][0], q[i][1], q[i][2]),

unde i0, , nr_maxim_indivizi_in populatie - 1 şi j0,1,2 - 3 tipuri de medicamente.

Interpretarea unui individ i (a structurii i), dat sub forma (q[i][0], q[i][1], q[i][2]) este următoarea: cantitatea (în număr de unităţi – flacoane sau blistere) din fiecare tip de medicament.

Exemple de structuri de producţie (de indivizi în populaţie), care se pot dovedi a fi structuri posibile (optime sau nu) sau imposibile (care nu respectă restricţia), sunt:

- (156, 35, 98), ceea ce se traduce prin: 156 de flacoane de Plantusin plus 35 de blistere de Fenilbutazonă plus 98 de blistere de Augmentin,

- (166, 196, 52), ceea ce se traduce prin: 166 de flacoane de Plantusin plus 196 de blistere de Fenilbutazonă plus 52 de blistere de Augmentin,

- (200, 200, 65), ceea ce se traduce prin: 200 de flacoane de Plantusin plus 200 de blistere de Fenilbutazonă plus 65 de blistere de Augmentin,

- (200, 71, 98), ceea ce se traduce prin: 200 de flacoane de Plantusin plus 71 de blistere de Fenilbutazonă plus 98 de blistere de Augmentin.

Funcţia obiectiv, f - profitul aferent structurii respective de producţie, este:

,

unde f[i] este profitul aferent structurii (individului) i,

q[i][j] este numărul de unităţi de tipul de medicament j din structura (individul) i,

pr[j] este profitul aferent unei unităţi de tipul j de medicament.

Restricţia ce trebuie respectată este dată de relaţia:

cost[i]  cmax,

unde este costul aferent structurii de producţie, iar cmax costul maxim pe care şi-l poate permite centrul de producţie.

Descrierea algoritmului

Se generează o populaţie iniţială de nr indivizi (de structuri de producţie de forma (q[i][0], q[i][1], q[i][2])), i0, , nr, în mod aleator. Determinarea aleatorie a acestei populaţii constă din folosirea generatorului de numere aleatoare pentru generarea unor numere reprezentând unităţi din fiecare tip de medicament pentru toţi cei nr indivizi, ţinând seama de capacităţile de producţie pentru fiecare tip de medicament într-un schimb (lucru ilustrat de codul funcţiei init_pop(n)). În această funcţie, q[i][j] = rand() % (capacitate_de_producţie_tip_j + 1), j0, 1, 2,

deci se generează numere între 0 şi capacitate_de_producţie_tip_j; rezultă că:

q[i][0] 0, , 200,

q[i][1] 0, , 250,

q[i][2] 0, , 100.

Populaţia iniţială este evaluată prin funcţia de adecvare (identică celei obiectiv) la fiecare generaţie (t). Din populaţia existentă la fiecare generaţie se extrag cei mai buni 2 indivizi care au cea mai mare valoare a funcţiei de adecvare. Aceştia îşi combină informaţia pentru a da naştere la doi descendenţi. Combinarea celor doi indivizi părinţi se realizează prin preluarea de către unul dintre descendenţi a unei informaţii parţiale din primul părinte şi a altei informaţii parţiale din cel de al doilea părinte şi preluarea de către celălalt descendent a restului de informaţie a părinţilor. O exemplificare a combinării: presupunem că cei 2 indivizi părinţi sunt (156, 35, 98) şi (166, 196, 52). Se generează aleator o poziţie – 0 sau 1 (pos = rand() % 2) – pentru stabilirea punctului de diviziune (individul având 3 componente, pot exista 2 puncte de diviziune pentru generarea de descendenţi diferiţi).

Dacă pos = 0, punctul de diviziune este între primele 2 componente: (q[][0] - q[][1] q[][2]) şi în acest caz descendenţii sunt: (156, 196, 52) şi (166, 35, 98).

Dacă pos = 1, punctul de diviziune este între ultimele 2 componente: (q[][0] q[][1] - q[][2]) şi în acest caz descendenţii sunt: (156, 35, 52) şi (166, 196, 98).