Genetik algoritmaları öğrenmek için çözdüğüm ilk problem “diophantine denklemleri”dir. O zamanlar Java’da bu uygulamayı gerçekleştirmiştim.
Bu aralar Python’a merak sardım. Bari şu diophantine’yi bir de GA ile Python’da çözeyim dedim. Çok basit bir çözüm ama GA’nın da mantığını yansıtan bir örnek oldu.
Problemimiz: a+2*b+3*c+4*d=30 denklemini sağlayan a,b,c,d doğal sayılar nelerdir?
Tasarımız ise şu şekilde oldu: Her bir kromozom aday bir çözümdür. O halde kromozomumuz 4 tane gen içerir ve her bir gen, denklemde bir bilinmeyene karşılık gelir. Uygunluk fonksiyonumuz zaten denklemin kendisidir. Çaprazlama fonksiyonumuz anneden ilk iki gen, babadan ise son iki geni alıp yavru bir kromozom oluşturur. Seçme fonksiyonu ise son derece ilkeldir. Populasyondaki tüm kromozomları uygunluk değerine göre sıralar ve belli aralıktaki kromozomlardan anne ve baba kromozomu seçer. Mutasyon işleminde ise sadece bie kromozomun ilk genine yeniden değer ataması yapılır.
Afiyet olsun.
import random #kromozom uretilir. #her kromozom 4 genden olusur. #ve her gen bir bilinmeyeni temsil eder. def kromozomUret(): kromozom=[random.randint(0,(30/x)) for x in range(1,5)] return kromozom #populasyon uretilir. #bu populasyon popSay kadar kromozom icerir. def populasyonUret(popSay): populasyon=[] while popSay>0: kromozom=kromozomUret() uygunlukHesap(kromozom) populasyon.append(kromozom) popSay-=1 return populasyon #populasyondaki kromzomlar uygunluk degerine gore siralanir. #ilk iki siradaki kromozomlar ata kromozomlar olarak secilir def anneVebabaKromozomlariGetir(populasyon): popBoyut=len(populasyon) for i in range(0,popBoyut-1): if (populasyon[i][4]>populasyon[i+1][4]): geciciKr=populasyon[i+1] populasyon[i+1]=populasyon[i] populasyon[i]=geciciKr anneIndex=random.randint(0,popBoyut/4) babaIndex=random.randint(0,popBoyut/4) return populasyon[anneIndex],populasyon[babaIndex] def sonuclariYazdir(populasyon): for kr in populasyon: if kr[4]==0: print "1*",kr[0],"+ 2*",kr[1]," + 3*",kr[2]," + 4*",kr[3]," =30" #iterasyon sayisi, ilgili populasyonun ne kadar evrilecegini belirler. #populasyon sayisi, kac tane kromozom olacagini belirler. #caprazlama sayisi, her bir iterasyonda kac defa caprazlama olacagini belirler. #mutasyon olasiligi ise caprazlama dongusunde ne kadar sayida mutasyon olacagini belirler. def havuz(iterasyonSay,populasyonSay,caprazlamaOlasilik,mutasyonOlasilik): populasyon=populasyonUret(populasyonSay) while iterasyonSay>0: caprazlamaSay=caprazlamaOlasilik mutasyonSay=mutasyonOlasilik cocukIndex=populasyonSay-1 while caprazlamaSay>0: anneKr,babaKr= anneVebabaKromozomlariGetir(populasyon) cocuk=caprazlamaYap(anneKr, babaKr) populasyon[cocukIndex]=cocuk caprazlamaSay-=1 if mutasyonSay>0: mutasyon(populasyon[cocukIndex]) mutasyonSay-=1 cocukIndex-=1 iterasyonSay-=1 sonuclariYazdir(populasyon) #kromzom denklemi ne derecede sagliyor, bunu hesaplar. #kromozoma uygunluk degeri olarak, 30'a olan uzakligi atanir. #bu durumda cozumu saglayan kromozom 0 degerini alir. def uygunlukHesap(liste): uygunlukDeger=liste[0]+liste[1]*2+liste[2]*3+liste[3]*4 liste.append(uygunlukDeger-30)
#anne kromozomun ilk 2 geni, # baba kromozomun ise son 2 geni alinarak yavru birey olusturulur. def caprazlamaYap(krAnne,krBaba): cocuk=[0,0,0,0] cocuk[0:2],cocuk[2:]=krAnne[0:2],krBaba[2:] uygunlukHesap(cocuk) return cocuk #mutasyon olarak kromozomun ilk genine yeniden deger atamasi yapilir def mutasyon(kromozom): kromozom[0]=random.randint(0,20) uygunlukHesap(kromozom) #main havuz(100, 2000, 50, 5)
Etiketler: diophantine denklemleri, genetik algoritma
