1. P?rzgjedhja natyrore n? natyr?

Teoria evolucionare pretendon se t? gjith? specie biologjike me q?llim zhvillohet dhe ndryshon n? m?nyr? q? t? menyra me e mire p?rshtatu me mjedisi. N? procesin e evolucionit, shum? lloje insektesh dhe peshqish fituan ngjyra mbrojt?se, iriq u b? i papreksh?m fal? gjilp?rave, njeriu u b? pronar i m? komplekseve. sistemi nervor. Mund t? themi se evolucioni ?sht? procesi i optimizimit t? t? gjith? organizmave t? gjall?. Le t? shqyrtojm? se si e zgjidh natyra k?t? problem optimizimi.

Mekanizmi kryesor i evolucionit ?sht? seleksionimi natyror.

Thelbi i saj ?sht? se individ?t m? t? p?rshtatur kan? m? shum? mund?si p?r mbijetes? dhe riprodhim dhe, p?r rrjedhoj?, prodhojn? m? shum? pasardh?s sesa individ? t? p?rshtatur dob?t. P?r m? tep?r, fal? transferimit t? informacionit gjenetik ( trash?gimia gjenetike) pasardh?sit trash?gojn? cil?sit? e tyre themelore nga prind?rit e tyre. K?shtu, pasardh?sit e individ?ve t? fort? do t? jen? gjithashtu relativisht t? p?rshtatur, dhe pjesa e tyre do t? jet? mas? totale individ?t do t? rriten. Pas nj? ndryshimi prej disa dhjet?ra ose qindra brezash, fitnesi mesatar i individ?ve t? nj? specie t? caktuar rritet ndjesh?m.

P?r t'i b?r? t? qarta parimet e funksionimit t? algoritmeve gjenetike, do t? shpjegojm? gjithashtu se si funksionojn? mekanizmat e trash?gimis? gjenetike n? natyr?. ?do qeliz? e ?do kafshe p?rmban t? gjitha informacion gjenetik k?tij individi. Ky informacion ?sht? shkruar n? form?n e nj? grupi molekulash shum? t? gjata t? ADN-s? (Acidi DeoksiriboNukleik). ?do molekul? e ADN-s? ?sht? nj? zinxhir i p?rb?r? nga molekula nukleotide kat?r lloje, t? p?rcaktuara A, T, C dhe G. N? fakt, informacioni bartet sipas rendit t? nukleotideve n? ADN. K?shtu, kodi gjenetik nj? individ ?sht? vet?m nj? varg shum? i gjat? karakteresh q? p?rdorin vet?m 4 shkronja. N? nj? qeliz? shtazore, ?do molekul? e ADN-s? ?sht? e rrethuar nga nj? membran? - ky formim quhet kromozomi.

?do cil?si e lindur e nj? individi (ngjyra e syve, s?mundjet trash?gimore, lloji i flok?ve, etj.) kodohet nga nj? pjes? specifike e kromozomit t? quajtur gjenomi k?t? pron?. P?r shembull, gjeni i ngjyr?s s? syve p?rmban informacione q? kodojn? ngjyr? specifike syri. Kuptime t? ndryshme gjen quhet ai alelet.

Kur kafsh?t riprodhohen, dy qeliza germinale prind?rore bashkohen dhe ADN-ja e tyre nd?rvepron p?r t? formuar ADN-n? e pasardh?sve. M?nyra kryesore e nd?rveprimit ?sht? kryq?zim (kalim, kalim). N? nj? kryq?zim, ADN-ja e paraardh?sve ndahet n? dy pjes?, dhe m? pas gjysmat e tyre shk?mbehen.

Gjat? trash?gimis?, mutacionet jan? t? mundshme p?r shkak t? radioaktivitetit ose ndikimeve t? tjera, si rezultat i t? cilave disa gjene n? qelizat germinale t? nj?rit prej prind?rve mund t? ndryshojn?. Gjenet e ndryshuara kalojn? tek pasardh?sit dhe i japin atij veti t? reja. N?se k?to jan? t? reja vetit? jan? t? dobishme, me shum? mund?si do t? ruhen n? k?t? form? - n? k?t? rast, do t? ket? nj? rritje t? papritur t? p?rshtatshm?ris? s? specieve.

2. ?far? ?sht? nj? algorit?m gjenetik

L?reni disa funksione komplekse ( funksion objektiv), n? var?si t? disa variablave, dhe k?rkohet t? gjenden vlera t? tilla t? variablave n? t? cilat vlera e funksionit ?sht? maksimale. Problemet e k?tij lloji quhen problemet e optimizimit dhe ndodhin shum? shpesh n? praktik?.

Nj? nga m? shembuj ilustrues- problemi i shp?rndarjes s? investimeve t? p?rshkruar m? par?. N? k?t? problem, variablat jan? v?llimi i investimit n? ?do projekt (10 variabla), dhe funksioni q? duhet t? maksimizohet ?sht? t? ardhurat totale t? investitorit. Jan? dh?n? edhe vlerat e investimit minimal dhe maksimal n? secilin prej projekteve, t? cilat p?rcaktojn? zon?n e ndryshimit p?r secilin prej variablave.

Le t? p?rpiqemi ta zgjidhim k?t? problem duke p?rdorur t? njohurat m?nyra natyrale optimizimi. Ne do t? konsiderojm? ?do opsion investimi (nj? grup vlerash t? ndryshueshme) si nj? individ, dhe p?rfitimin e k?tij opsioni si p?rshtatshm?rin? e k?tij individi. M? pas, n? procesin e evolucionit (n?se arrijm? ta organizojm?), fitnesi i individ?ve do t? rritet, ?ka do t? thot? se do t? shfaqen gjithnj? e m? shum? opsione investimi fitimprur?se. Duke ndaluar evolucionin n? nj? moment dhe duke zgjedhur individin m? t? mir?, ne marrim mjaftuesh?m vendim i mir? detyrat.

Algoritmi gjenetik ?sht? model i thjesht? evolucioni n? natyr?, i zbatuar n? form?n e nj? programi kompjuterik. Ai p?rdor si nj? analog t? mekanizmit t? trash?gimis? gjenetike ashtu edhe nj? analog t? p?rzgjedhjes natyrore. N? t? nj?jt?n koh?, terminologjia biologjike ruhet n? nj? form? t? thjeshtuar.

K?shtu modelohet trash?gimia gjenetike

P?r t? simuluar procesin evolucionar, ne fillimisht gjenerojm? nj? popullsi t? rast?sishme - disa individ? me nj? grup t? rast?sish?m kromozomesh (vektor? numerik?). Algoritmi gjenetik simulon evolucionin e k?saj popullate si nj? proces ciklik i kryq?zimit t? individ?ve dhe ndryshimit t? brezave.

Cikli jet?sor i nj? popullate p?rb?het nga disa kryq?zime t? rast?sishme (n?p?rmjet kryq?zimit) dhe mutacione, si rezultat i t? cilave nj? num?r i caktuar individ?sh t? rinj i shtohen popullsis?. P?rzgjedhja n? nj? algorit?m gjenetik ?sht? procesi i formimit t? nj? popullate t? re nga nj? e vjet?r, pas s? cil?s popullata e vjet?r vdes. Pas p?rzgjedhjes, operacionet e kryq?zimit dhe t? mutacionit aplikohen p?rs?ri n? popullat?n e re, m? pas p?rzgjedhja ndodh p?rs?ri, e k?shtu me radh?.

P?rzgjedhja n? nj? algorit?m gjenetik ?sht? e lidhur ngusht? me parimet e p?rzgjedhjes natyrore n? natyr? si m? posht?:

K?shtu, modeli i p?rzgjedhjes p?rcakton se si duhet t? nd?rtohet popullsia e gjenerat?s s? ardhshme. Si rregull, probabiliteti q? nj? individ t? marr? pjes? n? nj? kryq merret n? proporcion me p?rshtatshm?rin? e tij. Shpesh p?rdoret e ashtuquajtura strategji elitare, n? t? cil?n disa nga individ?t m? t? mir? i kalojn? brezit t? ardhsh?m t? pandryshuar, pa marr? pjes? n? kryq?zim dhe p?rzgjedhje. N? ?do rast, ?do brez i ardhsh?m do t? jet? mesatarisht m? i mir? se ai i m?parshmi. Kur aft?sia fizike e individ?ve pushon s? rrituri duksh?m, procesi ndalet dhe m? e mira nga individ?t e gjetur merret si zgjidhje p?r problemin e optimizimit.

Duke iu rikthyer problemit t? shp?rndarjes optimale t? investimeve, le t? shpjegojm? ve?orit? e zbatimit t? algoritmit gjenetik n? k?t? rast.

• Individual = zgjidhje e problemit = grup prej 10 kromozomesh X j
• Kromozomi X j = v?llimi i investimit n? projekt j = sh?nimi 16-bit i k?tij numri
• Meqen?se v?llimet e investimeve jan? t? kufizuara, jo t? gjitha vlerat e kromozomeve jan? t? vlefshme. Kjo merret parasysh kur krijohen popullata.
• Meqen?se shuma totale e investimit ?sht? fikse, vet?m 9 kromozome ndryshojn? n? t? v?rtet? dhe vlera e 10-t?s p?rcaktohet n? m?nyr? unike prej tyre.

M? posht? jan? rezultatet e algoritmit gjenetik p?r tre vlera t? ndryshme t? v?llimit total t? investimit K.

Sheshet me ngjyra n? grafik?t e fitimit tregojn? se sa investim n? nj? projekt t? caktuar rekomandohet nga algoritmi gjenetik.     Mund t? shihet se me nj? vler? t? vog?l t? K investohen vet?m ato projekte q? jan? fitimprur?se me investime minimale.

N?se rritni v?llimin total t? investimeve, b?het fitimprur?se t? investoni n? projekte m? t? shtrenjta.

Me nj? rritje t? m?tejshme t? K, arrihet pragu i investimit maksimal n? projekte fitimprur?se dhe investimi n? projekte me fitim t? ul?t p?rs?ri ka kuptim.

3. Ve?orit? e algoritmeve gjenetike

Algoritmi gjenetik ?sht? m?nyra m? e re, por jo e vetmja e mundshme p?r t? zgjidhur problemet e optimizimit. P?r nj? koh? t? gjat?, jan? njohur dy m?nyra kryesore p?r zgjidhjen e problemeve t? tilla - k?rkimi shterues dhe gradienti lokal. K?to metoda kan? avantazhet dhe disavantazhet e tyre, dhe n? ?do rast duhet t? mendoni se cil?n t? zgjidhni.

Le t? shqyrtojm? avantazhet dhe disavantazhet e standardit dhe metodat gjenetike duke p?rdorur shembullin e problemit klasik t? shit?sit udh?tues (TSP). Thelbi i problemit ?sht? gjetja e shtegut m? t? shkurt?r t? mbyllur rreth disa qyteteve t? dh?na nga koordinatat e tyre. Rezulton se tashm? p?r 30 qytete k?rkimi p?r rrug?n optimale ?sht? detyr? e v?shtir?, e cila nxiti zhvillimin e metodave t? ndryshme t? reja (p?rfshir? rrjetet nervore dhe algoritme gjenetike).

?do opsion zgjidhje (p?r 30 qytete) ?sht? nj? vij? numerike, ku n? vendin e j-t? ?sht? numri i qytetit t? j-t? sipas rendit t? anashkalimit. K?shtu, ka 30 parametra n? k?t? problem, dhe jo t? gjitha kombinimet e vlerave jan? t? vlefshme. Natyrisht, ideja e par? ?sht? nj? k?rkim i plot? i t? gjitha opsioneve t? zgjidhjes.

Metoda shteruese ?sht? m? e thjeshta n? natyr? dhe e par?nd?sishme n? programim. P?r k?rkim zgjidhje optimale(pikat maksimale t? funksionit objektiv) k?rkohet t? llogariten n? m?nyr? sekuenciale vlerat e funksionit objektiv n? t? gjitha pikat e mundshme, duke kujtuar maksimumin e tyre. Disavantazhi i k?saj metode ?sht? kostoja e lart? llogarit?se. N? ve?anti, n? problemin e shit?sit udh?tues do t? jet? e nevojshme t? llogaritet gjat?sia e m? shum? se 10 30 opsioneve t? rrug?s, gj? q? ?sht? krejt?sisht joreale. Megjithat?, n?se ?sht? e mundur t? k?rkosh t? gjitha opsionet n? nj? koh? t? arsyeshme, at?her? mund t? jesh absolutisht i sigurt se zgjidhja e gjetur ?sht? v?rtet optimale.

Metoda e dyt? popullore bazohet n? metod?n e zbritjes me gradient. N? k?t? rast, s? pari disa t? rast?sishme vlerat e parametrave, dhe m? pas k?to vlera ndryshohen gradualisht, duke arritur norm?n m? t? lart? t? rritjes s? funksionit objektiv. Pasi t? ket? arritur nj? maksimum lokal, nj? algorit?m i till? ndalon, k?shtu q? do t? k?rkohen p?rpjekje shtes? p?r t? gjetur optimumin global. Metodat e gradientit funksionojn? shum? shpejt, por nuk garantojn? optimalitetin e zgjidhjes s? gjetur.

Ato jan? ideale p?r p?rdorim n? t? ashtuquajturat nj?modale problemet ku funksioni objektiv ka nj? maksimum t? vet?m lokal (i njohur edhe si global). ?sht? e leht? t? shihet se problemi i shit?sit udh?tues nuk ?sht? unimodal.

Nj? problem tipik praktik ?sht? zakonisht multimodale  dhe shum?dimensionale, dometh?n? p?rmban shum? parametra. Nuk ka njeri p?r pun? t? tilla metod? universale, e cila do t? lejonte q? dikush t? gjente shpejt nj? zgjidhje absolutisht t? sakt?.

Megjithat?, duke kombinuar metoda shteruese dhe gradient, mund t? shpresohet t? merret t? pakt?n nj? zgjidhje e p?raf?rt, sakt?sia e s? cil?s do t? rritet me rritjen e koh?s s? llogaritjes.

Algoritmi gjenetik ?sht? vet?m nj? metod? e till? e kombinuar. Mekanizmat e kryq?zimit dhe mutacionit, n? nj? far? kuptimi, zbatojn? pjes?n e k?rkimit t? metod?s dhe p?rzgjedhjen zgjidhjet m? t? mira- zbritje gradient. Figura tregon se ky kombinim lejon nj? performanc? t? mir? t? k?rkimit gjenetik p?r t? gjitha llojet e problemeve.

Pra, n?se nj? funksion kompleks i disa ndryshoreve jepet n? nj? grup t? caktuar, at?her? nj? algorit?m gjenetik ?sht? nj? program q?, n? nj? koh? t? arsyeshme, gjen pik?n ku vlera e funksionit ?sht? mjaft af?r maksimumit t? mundsh?m. Duke zgjedhur nj? koh? t? pranueshme llogarit?se, do t? marrim nj? nga zgjidhjet m? t? mira q? p?rgjith?sisht mund t? merren n? k?t? koh?.

Ward Systems Group ka p?rgatitur nj? shembull t? qart? t? zgjidhjes s? problemit t? shit?sit udh?tues duke p?rdorur nj? algorit?m gjenetik. P?r k?t? q?llim ?sht? p?rdorur biblioteka e funksionit t? produktit GeneHunter.

Nj? tipar dallues i algoritmit gjenetik ?sht? theksi n? p?rdorimin e operatorit "kryq?zimi", i cili kryen funksionin e rikombinimit t? zgjidhjeve kandidate, roli i t? cilit ?sht? i ngjash?m me rolin e kryq?zimit n? natyr?n e gjall?.

YouTube Enciklopedike

1 / 5

? Algoritmi gjenetik

? 20: Hyrje n? Algoritmet Gjenetike (1 nga 2)

? C# - Beteja e Detit- Algoritmi m? i mir? i AI

? 15.09.2018 Leksion "Algoritmet gjenetike p?r k?rkimin e strukturave optimale" Ulyantsev V.I.

? Algoritmi gjenetik. Vendosja e grafikut n? vizore

Titra

Histori

Puna e par? mbi simulimin e evolucionit u krye n? vitin 1954 nga Nils Baricelli n? nj? kompjuter t? instaluar n? Universitetin Princeton. Puna e tij, e botuar po at? vit, t?rhoqi v?mendjen e gjer? t? publikut. Q? nga viti 1957, gjenetisti australian Alex Fraser ka botuar nj? seri punimesh mbi simulimin e p?rzgjedhjes artificiale midis organizmave me kontrolle t? shumta mbi karakteristikat e matshme. Ky zhvillim lejoi q? simulimet kompjuterike t? proceseve evolucionare dhe metodat e p?rshkruara n? librat e Fraser dhe Barnell (1970) dhe Crosby (1973) t? b?hen nj? aktivitet m? i zakonsh?m midis biolog?ve nga vitet 1960. Simulimet e Fraser p?rfshinin gjith?ka elementet thelb?sore algoritme moderne gjenetike. P?rve? k?saj, Hans-Joachim Bremermann botoi nj? seri punimesh n? vitet 1960 q? miratuan gjithashtu qasjen e p?rdorimit t? nj? popullate zgjidhje q? i n?nshtrohet rikombinimit, mutacionit dhe p?rzgjedhjes n? problemet e optimizimit. Hulumtimi i Bremermann p?rfshinte gjithashtu elemente t? algoritmeve moderne gjenetike. Pionier? t? tjer? p?rfshijn? Ri?ard Fridbergun, Xhorxh Fridmanin dhe Majk?ll Konradin. Nj? tuf? me veprat e hershme u ribotuan nga David B. Vogel (1998).

Edhe pse Baricelli, n? pun?n e tij t? vitit 1963, simuloi aft?sin? e makin?s p?r t? luajtur loj? e thjesht? Evolucioni artificial u b? nj? metod? optimizimi e pranuar p?rgjith?sisht pas pun?s s? Ingo Rechenberg dhe Hans-Paul Schwefel n? vitet 1960 dhe fillim t? viteve 1970 t? shekullit t? nj?zet? - grupi i Rechensberg ishte n? gjendje t? zgjidhte probleme komplekse inxhinierike sipas strategjive evolucionare. Nj? tjet?r qasje ishte teknika e programimit evolucionar e Lawrence J. Vogel, e cila u propozua t? krijohej inteligjence artificiale. Programimi evolucionar fillimisht p?rdori makina t? gjendjes s? fundme p?r t? parashikuar rrethanat dhe p?rdori diversitetin dhe p?rzgjedhjen p?r t? optimizuar logjik?n parashikuese. Algoritmet gjenetike u b?n? ve?an?risht t? njohura fal? pun?s s? John Holland n? fillim t? viteve 70 dhe librit t? tij Adaptimi n? mjediset natyrore. sistemet artificiale"(1975). Hulumtimi i tij u bazua n? eksperimentet me automata celulare t? kryera nga Holland dhe n? shkrimet e tij n? Universitetin e Mi?iganit. Holland prezantoi nj? qasje t? zyrtarizuar p?r parashikimin e cil?sis? s? gjenerat?s s? ardhshme t? njohur si Teorema e Qarkut. K?rkimet n? fush?n e algoritmeve gjenetike mbet?n kryesisht teorike deri n? mesin e viteve 1980, kur m? n? fund u mbajt Konferenca e Par? Nd?rkomb?tare mbi Algoritmet Gjenetike n? Pittsburgh, Pensilvani (SHBA).

Me rritjen e interesit k?rkimor, fuqia kompjuterike e kompjuter?ve desktop ?sht? rritur gjithashtu ndjesh?m, kjo ka b?r? t? mundur p?rdorimin e teknologjis? s? re informatike n? praktik?. N? fund t? viteve 1980, General Electric filloi t? shes? produktin e par? t? algoritmit gjenetik n? bot?. Ai u b? nj? grup mjetesh informatike industriale. N? vitin 1989, nj? kompani tjet?r, Axcelis, Inc. l?shoi Evolver, produktin e par? komercial t? algoritmit gjenetik n? bot? p?r kompjuter?t desktop. Gazetari i teknologjis? i New York Times, John Markoff, shkroi p?r Evolver n? 1990.

P?rshkrimi i algoritmit

Problemi ?sht? formalizuar n? at? m?nyr? q? zgjidhja e tij mund t? kodohet si nj? vektor (“gjenotip”) gjenesh, ku ?do gjen mund t? jet? nj? bit, nj? num?r ose ndonj? objekt tjet?r. Zbatimet klasike t? nj? algoritmi gjenetik (GA) supozojn? se gjenotipi ka nj? gjat?si fikse. Megjithat?, ka variacione t? GA q? jan? t? lira nga ky kufizim.

N? disa m?nyra, zakonisht t? rast?sishme, krijohen shum? gjenotipe t? popullsis? fillestare. Ato vler?sohen duke p?rdorur nj? "funksion fitnesi", ku ?do gjenotip lidhet me nj? vler? specifike ("p?rshtatshm?ri") q? p?rcakton se sa mir? fenotipi q? p?rshkruan e zgjidh problemin n? fjal?.

Zbatimi i algoritmeve gjenetike

Algoritmet gjenetike p?rdoren p?r t? zgjidhur problemet e m?poshtme:

1. Optimizimi i funksionit
2. Probleme t? ndryshme n? grafik? (problemi i shit?sit udh?tues, ngjyrosja, gjetja e p?rputhjeve)
3. Ngritja dhe trajnimi i nj? rrjeti nervor artificial
4. Detyrat e paraqitjes
5. Strategjit? e loj?rave
6. Bioinformatika (palosja e proteinave)
7. Sinteza e makinave me gjendje t? fundme
8. Vendosja e kontrollor?ve PID

Shembull i nj? implementimi t? thjesht? n? C++

K?rkoni n? hap?sir? nj?dimensionale, pa kryq?zim.

#p?rfshi #p?rfshi #p?rfshi #p?rfshi #p?rfshi int main () ( srand ((int e pan?nshkruar ) koha (NULL )); madh?sia konst_t N = 1000 ; int a [ N ] = ( 0 ); p?r ( ; ; ) ( //mutacion n? nj? drejtim t? rast?sish?m t? secilit element: p?r (madh?sia_t i = 0; i< N ; ++ i ) a [ i ] += ((rand () % 2 == 1 ) ? 1 : - 1 ); //tani zgjidhni m? t? mirat, duke i renditur n? rend rrit?s std:: sort (a, a + N); //dhe pastaj m? t? mirat do t? jen? n? gjysm?n e dyt? t? grupit. //kopjoni m? t? mir?n n? pjes?n e par?, ku lan? pasardh?s dhe i pari vdiq: std:: kopje (a + N / 2, a + N, a); //Tani le t? shohim gjendjen mesatare t? popullsis?. Si? mund ta shihni, po b?het gjithnj? e m? mir?. std::cout<< std :: accumulate (a , a + N , 0 ) / N << std :: endl ; } }

Shembull i nj? zbatimi t? thjesht? n? Delphi

K?rkoni n? hap?sir? nj?dimensionale me probabilitet mbijetese, pa kryq?zim. (testuar n? Delphi XE)

Programi Programi1 ; ($APPTYPE CONSOLE) ($R *.res) p?rdor Sistemin . Gjenerik?t. Parazgjedhjet, Sistemi. Gjenerik?t. Koleksionet, Sistemi. SysUtils; konst N = 1000 ; Nh = N div 2; MaxPopulation = Lart? (Num?r i plot?); var A: vargu [1.. N] i numrit t? plot?; I, R, C, Pikat, Norma e Lindshm?ris?: Integer; Iptr: ^ Integer; filloni Randomize; // Popullsi e pjesshme sepse I := 1 deri n? N b?j A [I] := E rast?sishme (2); p?rs?rit // Mutacioni p?r I := 1 n? N b?j A [I ] := A [I ] + (- Random (2) ose 1); // P?rzgjedhja, m? e mira n? fund Tabaka. Rendit< Integer >(A, TComparer< Integer >. e paracaktuar); // Paracaktuar Iptr := Adr (A [Nh + 1 ]); Pik?t := 0 ; Nataliteti := 0 ; // Rezultatet e kryq?zimit sepse I := 1 deri n? Nh do t? filloj? Inc (Points, Iptr ^); // Suksesi i kryq?zimit t? rast?sish?m R := E rast?sishme(2); Inc(BirthRate, R); A[I]:=Iptr^*R; Iptr ^ := 0 ; Inc(Iptr, 1); fundi ; // N?ntotali Inc(C); deri n? (Points / N >= 1 ) ose (C >= MaxPopulation ) ; Writeln(Format( "Popullsia %d (norma:%f) rezultati:%f", [ C , Nataliteti / Nh , Pikat / N ])) ; fund.

N? kultur?

• N? filmin e vitit 1995 Virtuosity, truri i zuzarit kryesor ?sht? rritur nga nj? algorit?m gjenetik duke p?rdorur kujtimet dhe tipare t? sjelljes kriminel?t.

Ky seksion p?rshkruan konceptin e nj? algoritmi t? thjesht? gjenetik (GA) q? synon zgjidhjen e problemeve t? ndryshme t? optimizimit. Konceptet e p?rdorura n? teorin? dhe aplikimet e GA jan? prezantuar dhe p?rshkruar n? m?nyr? kuptimplote. Prezantohet teorema themelore e GA dhe paraqitet teoria e qarqeve q? p?rb?jn? baz?n teorike t? GA. Diskutohen ??shtje konceptuale n? lidhje me avantazhet dhe disavantazhet e GA.

1.1. Algorit?m i thjesht? gjenetik

Bazat e teoris? s? algoritmeve gjenetike u formuluan nga J. G. Holland n? pun?n e tij kryesore dhe u zhvilluan m? pas nga nj? num?r studiuesish t? tjer?. Monografia m? e famshme dhe e cituar shpesh nga D. Goldberg, e cila paraqet n? m?nyr? sistematike rezultatet dhe fushat kryesore aplikim praktik GA.

GA p?rdorin parime dhe terminologji t? huazuar nga shkenca biologjike e gjenetik?s. N? nj? GA, ?do individ p?rfaq?son nj? zgjidhje t? mundshme p?r nj? problem. N? nj? GA klasike, nj? individ kodohet nga nj? varg karakteresh binare - nj? kromozom, ?do pjes? e t? cilit quhet gjen. Nj? grup individ?sh – zgjidhje t? mundshme – p?rb?jn? nj? popullsi. K?rkimi p?r nj? zgjidhje optimale ose n?noptimale t? nj? problemi kryhet n? procesin e evolucionit t? popullsis?, d.m.th. transformimi sekuencial i nj? grupi t? fund?m zgjidhjesh n? nj? tjet?r duke p?rdorur operator?t gjenetik? t? riprodhimit, kryq?zimit dhe mutacionit. EV-t? p?rdorin mekanizma natyror? t? evolucionit bazuar n? parimet e m?poshtme:

1. Parimi i par? bazohet n? konceptin e mbijetes?s s? seleksionimit m? t? fort? dhe natyror sipas Darvinit, i cili u formulua prej tij n? vitin 1859 n? librin "Origjina e specieve me an? t? p?rzgjedhjes natyrore". Sipas Darvinit, individ?t q? jan? m? t? aft? t? zgjidhin problemet n? mjedisin e tyre kan? m? shum? gjasa t? mbijetojn? dhe t? riprodhohen (riprodhohen) m? shpesh. N? algoritmet gjenetike, ?do individ p?rfaq?son nj? zgjidhje p?r nj? problem. N? analogji me k?t? parim, individ?t me vlerat m? t? mira Funksionet e objektivit (fitnesit) kan? nj? shans t? lart? p?r t? mbijetuar dhe riprodhuar. Formalizimi i k?tij parimi, si? do t? shohim m? von?, zbatohet nga operatori i riprodhimit.
2. Parimi i dyt? buron nga fakti se kromozomi i pasardh?sve p?rb?het nga pjes? q? rrjedhin nga kromozomet e prind?rve. Ky parim u zbulua n? 1865 nga G. Mendel. Formalizimi i tij ofron baz?n p?r operatorin e kalimit.
3. Parimi i tret? bazohet n? konceptin e mutacionit, i zbuluar n? vitin 1900 nga de Vres. Fillimisht, ky term u p?rdor p?r t? p?rshkruar ndryshime t? r?nd?sishme (t? mprehta) n? pronat e pasardh?sve dhe p?rvet?simin e tyre t? pronave q? mungonin tek prind?rit e tyre. N? analogji me k?t? parim, algoritmet gjenetike p?rdorin nj? mekaniz?m t? ngjash?m p?r t? ndryshuar n? m?nyr? dramatike vetit? e pasardh?sve dhe, n? k?t? m?nyr?, p?r t? rritur diversitetin (ndryshueshm?rin?) e individ?ve n? nj? popullsi (bashk?si zgjidhjesh).

K?to tre parime p?rb?jn? thelbin e EV. Duke i p?rdorur ato, popullsia (shum? zgjidhje p?r nj? problem t? caktuar) evoluon nga brezi n? brez.

Evolucioni i nj? popullate artificiale - k?rkimi p?r zgjidhje t? shum?fishta p?r nj? problem t? caktuar - mund t? p?rshkruhet zyrtarisht n? form?n e nj? algoritmi, i cili ?sht? paraqitur n? Fig. 1.1.

GA merr nj? grup parametrash t? problemit t? optimizimit dhe i kodon ato n? sekuenca me gjat?si t? fundme n? nj? alfabet t? fund?m (n? rastin m? t? thjesht? n? alfabetin binar "0" dhe "1").

Nj? GA para e thjesht? gjeneron rast?sisht nj? popullat? fillestare t? kromozomeve (vargjeve). M? pas, algoritmi gjeneron gjenerat?n e ardhshme (popullimin) duke p?rdorur tre baz?n e m?poshtme operator?t gjenetik?:

1. operatori i riprodhimit (OR);
2. operatori i kalimit (crossover, OK);
3. operatori i mutacionit (OM).

Algoritmet gjenetike nuk jan? thjesht nj? k?rkim i rast?sish?m, ato p?rdorin n? m?nyr? efektive informacionin e grumbulluar n? procesin e evolucionit.

N? procesin e k?rkimit t? nj? zgjidhjeje, ?sht? e nevojshme t? ruhet nj? ekuilib?r midis "shfryt?zimit" t? zgjidhjeve m? t? mira t? marra n? k?t? moment dhe zgjerimit t? hap?sir?s s? k?rkimit. Metoda t? ndryshme motor?t e k?rkimit e zgjidhin k?t? problem n? m?nyra t? ndryshme.

P?r shembull, metodat e gradientit bazohen praktikisht vet?m n? p?rdorimin e zgjidhjeve m? t? mira aktuale, gj? q? rrit shpejt?sin? e konvergjenc?s nga nj?ra an?, por lind problemin e ekstremeve lokale nga ana tjet?r. N? qasjen polare, metodat e k?rkimit t? rast?sish?m p?rdoren nga t? gjith?

N? Koh?t e fundit Gjithnj? e m? shum? flitet p?r algoritme t? reja, si? jan? rrjetet nervore dhe algoritmet gjenetike. Sot do t? flas p?r algoritmet gjenetike, por k?t? her? le t? p?rpiqemi t? shmangim p?rkufizimet abstruktive dhe termat komplekse.
Si? tha nj? nga shkenc?tar?t e m?dhenj: "N?se nuk mund t'ia shpjegoni teorin? tuaj gruas suaj, teoria juaj ?sht? e pavler?!" Pra, le t? p?rpiqemi t? kuptojm? gjith?ka n? rregull.

Nj? maj? historie

Si? thot? Wikipedia: "Babai themelues i algoritmeve gjenetike ishte John Holland, i cili lindi me iden? e p?rdorimit t? gjenetik?s p?r q?llimet e tij n? vitin 1975." P?r referenc?, Altair 8800 u shfaq n? t? nj?jtin vit, dhe jo, ky nuk ?sht? nj? terrorist, por i pari Kompjuter personal. N? at? koh?, Gjoni ishte tashm? 46 vje?.

Ku p?rdoret?

Meqen?se algoritmi ?sht? vet?-m?sues, gama e aplikacioneve ?sht? jasht?zakonisht e gjer?:

• Probleme me grafikun
• Detyrat e paraqitjes
• Planifikimi
• Krijimi i "Inteligjenc?s Artificiale"

Parimi i funksionimit

Nj? algorit?m gjenetik ?sht? kryesisht nj? algorit?m evolucionar, me fjal? t? tjera, tipari kryesor i algoritmit ?sht? kryq?zimi (kombinimi). Si? mund ta merrni me mend, ideja e algoritmit u mor pafytyr? nga natyra, p?r fat t? mir? ajo nuk do t? padis? p?r t?. Pra, p?rmes num?rimit dhe, m? e r?nd?sishmja, p?rzgjedhjes, fitohet "kombinimi" i sakt?.
Algoritmi ?sht? i ndar? n? tre faza:

• Ciftezim i kryqezuar
• Mbar?shtimi (p?rzgjedhja)
• Formimi i nj? brezi t? ri

N?se rezultati nuk na p?rshtatet, k?to hapa p?rs?riten derisa rezultati t? filloj? t? na k?naq? ose t? ndodh? nj? nga kushtet e m?poshtme:

• Numri i gjeneratave (cikleve) do t? arrij? nj? maksimum t? paracaktuar
• Koha p?r mutacion ka skaduar

M? shum? detaje rreth hapave

Krijimi i nj? popullsie t? re. N? k?t? hap, krijohet nj? popullsi fillestare, e cila, me shum? mund?si, nuk do t? jet? kosher, por ka nj? probabilitet t? lart? q? algoritmi ta korrigjoj? k?t? problem. Gj?ja kryesore ?sht? se ato korrespondojn? me "formatin" dhe jan? "p?rshtatur p?r riprodhim".
Riprodhimi. Epo, k?tu gjith?ka ?sht? si me njer?zit, k?rkohen dy prind?r p?r t? marr? nj? pasardh?s. Gj?ja kryesore ?sht? q? pasardh?si (f?mija) mund t? trash?goj? tiparet e tyre nga prind?rit e tyre. N? k?t? rast, t? gjith? riprodhohen, jo vet?m t? mbijetuarit (kjo fraz? ?sht? ve?an?risht absurde, por duke qen? se ne kemi gjith?ka n? nj? vakum sferik, gjith?ka ?sht? e mundur), p?rndryshe do t? bie n? sy nj? mashkull alfa, gjenet e t? cilit do t? mbivendosen me t? gjith? t? tjer?t, dhe kjo ?sht? thelb?sisht e papranueshme p?r ne.
Mutacionet. Mutacionet jan? t? ngjashme me riprodhimin, nj? num?r i caktuar individ?sh zgjidhen nga mutant?t dhe ndryshohen n? p?rputhje me operacionet e paracaktuara.
P?rzgjedhja. K?tu fillon pjesa m? e ?mb?l, ne fillojm? t? zgjedhim nga popullsia pjes?n e atyre q? "do t? shkojn? m? tej". N? t? nj?jt?n koh?, ne p?rcaktojm? paraprakisht me dor? pjes?n e "t? mbijetuarve" pas p?rzgjedhjes son?, duke e treguar at? si nj? paramet?r. Mjerisht, individ?t e mbetur duhet t? vdesin.

Praktikoni

Ju e keni d?gjuar me sukses "p?rrall?n" p?r algoritmin e mrekullis? dhe me siguri keni pritur q? m? n? fund t? fillojm? ta p?rdorim at?, dua t'ju b?j t? lumtur, ka ardhur koha.
Le t? shohim shembullin e ekuacioneve t? mia t? preferuara Diophantine (Ekuacionet me rr?nj? t? plota).
Ekuacioni yn?: a+2b+3c+4d=30
Ju ndoshta dyshoni tashm? se rr?nj?t e k?tij ekuacioni q?ndrojn? n? segmentin , k?shtu q? marrim 5
e rastit vlerat a,b,c,d. (Kufiri prej 30 u mor posa??risht p?r t? thjeshtuar detyr?n)
Dhe k?shtu, ne kemi gjenerat?n e par?:

1. (1,28,15,3)
2. (14,9,2,4)
3. (13,5,7,3)
4. (23,8,16,19)
5. (9,13,5,2)

P?r t? llogaritur shkall?t e mbijetes?s, ne z?vend?sojm? secil?n zgjidhje n? shprehje. Distanca nga vlera e fituar deri n? 30 do t? jet? vler?n e d?shiruar.

1. |114-30|=84
2. |54-30|=24
3. |56-30|=26
4. |163-30|=133
5. |58-30|=28

Vlerat m? t? ul?ta jan? m? af?r 30, q? do t? thot? se ato jan? m? t? d?shirueshme. Rezulton se vlera t? m?dha do t? ket? nj? shkall? m? t? ul?t t? mbijetes?s. P?r t? krijuar sistemin, le t? llogarisim probabilitetin e zgjedhjes s? secilit (kromozomi). Por zgjidhja ?sht? t? marrim shum?n e vlerave reciproke t? koeficient?ve dhe nga kjo t? llogarisim p?rqindjet. ( P.S. 0,135266 - shuma e gjasave t? anasjellta)

1. (1/84)/0.135266 = 8.80%
2. (1/24)/0.135266 = 30.8%
3. (1/26)/0.135266 = 28.4%
4. (1/133)/0.135266 = 5.56%
5. (1/28)/0.135266 = 26.4%

M? pas, ne do t? zgjedhim pes? ?ifte prind?rish q? do t? ken? sakt?sisht nj? f?mij?. Ne do t? japim shansin sakt?sisht pes? her?, ?do her? mund?sia p?r t'u b?r? prind do t? jet? e nj?jt? dhe do t? jet? e barabart? me mund?sin? e mbijetes?s.
3-1, 5-2, 3-5, 2-5, 5-3
Si? u tha m? her?t, pasardh?sit p?rmbajn? informacione p?r gjenet e babait dhe n?n?s. Kjo mund t? sigurohet menyra te ndryshme, por n? k?t? rast do t? p?rdoret "crossover". (| = vij? ndar?se)

• H.-babai: a1 | b1,c1,d1 H.-n?na: a2 | b2,c2,d2 X.-pasardh?s: a1,b2,c2,d2 ose a2,b1,c1,d1
• H.-babai: a1,b1 | c1, d1 H.-n?na: a2,b2 | c2,d2 X.-pasardh?s: a1,b1,c2,d2 ose a2,b2,c1,d1
• H.-babai: a1,b1,c1 | d1 H.-n?na: a2,b2,c2 | d2 X.-pasardh?s: a1,b1,c1,d2 ose a2,b2,c2,d1

Ka shum? m?nyra p?r t? transmetuar informacionin te nj? pasardh?s, dhe kryq?zimi ?sht? vet?m nj? nga shum?. Vendndodhja e ndar?sit mund t? jet? absolutisht arbitrare, si dhe n?se babai ose n?na do t? jen? n? t? majt? t? linj?s.
Tani le t? b?jm? t? nj?jt?n gj? me pasardh?sit:

• H.-babai: (13 | 5,7,3) H.-n?na:(1 | 28,15,3) X.-pasardh?s: (13,28,15,3)
• H.-babai: (9,13 | 5,2) H.-n?na: (14,9 | 2,4) X.-pasardh?s: (9,13,2,4)
• H.-babai: (13,5,7 | 3) H.-n?na: (9,13,5 | 2) X.-pasardh?s: (13,5,7,2)
• H.-babai: (14 | 9,2,4) H.-n?na: (9 | 13,5,2) X.-pasardh?s: (14,13,5,2)
• H.-babai: (13,5 | 7, 3) H.-n?na: (9,13 | 5, 2) X.-pasardh?s: (13,5,5,2)

Tani le t? llogarisim normat e mbijetes?s s? pasardh?sve.

• (13,28,15,3) - |126-30|=96(9,13,2,4) - |57-30|=27
  (13,5,7,2) - |57-30|=22
  (14,13,5,2) - |63-30|=33
  (13,5,5,2) - |46-30|=16

  ?sht? e trishtueshme sepse fitnesi mesatar i pasardh?sve doli t? ishte 38.8, dhe p?r prind?rit ky koeficient ishte 59.4. ?sht? n? k?t? moment q? ?sht? m? e k?shillueshme t? p?rdorim nj? mutacion p?r ta b?r? k?t?, ne z?vend?sojm? nj? ose m? shum? vlera me nj? num?r t? rast?sish?m nga 1 n? 30.
  Algoritmi do t? funksionoj? derisa shkalla e mbijetes?s t? jet? zero. Ato. do t? jet? nj? zgjidhje e ekuacionit.
  Sistemet me nj? popullsi m? t? madhe (p?r shembull, 50 n? vend t? 5) konvergojn? n? nivelin e d?shiruar (0) m? shpejt dhe m? t? q?ndruesh?m.

  Kodi

  K?tu p?rfundon thjesht?sia dhe fillon C++ e mrekullueshme...
  Nj? klas? C++ k?rkon 5 vlera pas inicializimit: 4 koeficient? dhe nj? rezultat. P?r shembullin e m?sip?rm do t? duket k?shtu: CDiofantine dp(1,2,3,4,30);

  Pastaj, p?r t? zgjidhur ekuacionin, thirrni funksionin Solve(), i cili do t? kthej? alelin q? p?rmban zgjidhjen. Telefononi GetGene() p?r t? marr? gjenin me t? vlerat e sakta a, b, c, d. Nj? procedur? standarde main.cpp duke p?rdorur k?t? klas? mund t? duket k?shtu:

  #p?rfshi" " #include "diophantine.h" void main() ( CDiophantine dp(1,2,3,4,30); int ans; ans = dp.Solve(); if (ans == -1) (cout<< "No solution found." << endl; } else { gene gn = dp.GetGene(ans); cout << "The solution set to a+2b+3c+4d=30 is:\n"; cout << "a = " << gn.alleles << "." << endl; cout << "b = " << gn.alleles << "." << endl; cout << "c = " << gn.alleles << "." << endl; cout << "d = " << gn.alleles << "." << endl; } }

  Vet? klasa CDiofantine:

  #p?rfshi #p?rfshi #define MAXPOP 25 struct genin ( int alele; int fitness; float proliability; // Test for barazi. operator==(gene gn) ( for (int i=0;i<4;i++) { if (gn.alleles[i] != alleles[i]) return false; } return true; } }; class CDiophantine { public: CDiophantine(int, int, int, int, int);// Constructor with coefficients for a,b,c,d. int Solve();// Solve the equation. // Returns a given gene. gene GetGene(int i) { return population[i];} protected: int ca,cb,cc,cd;// The coefficients. int result; gene population;// Population. int Fitness(gene &);// Fitness function. void GenerateLikelihoods(); // Generate likelihoods. float MultInv();// Creates the multiplicative inverse. int CreateFitnesses(); void CreateNewPopulation(); int GetIndex(float val); gene Breed(int p1, int p2); }; CDiophantine::CDiophantine(int a, int b, int c, int d, int res) : ca(a), cb(b), cc(c), cd(d), result(res) {} int CDiophantine::Solve() { int fitness = -1; // Generate initial population. srand((unsigned)time(NULL)); for(int i=0;i25) pushim; ) temppop[i] = Breed(prind1, prind2);// Krijo nj? f?mij?. ) p?r(i=0;i

  Artikulli bazohet n? materiale nga Wikipedia dhe faqja e internetit