Sayfalar

Cumartesi, Mart 03, 2007

Genetik metodla 4 Bilinmiyenli Denklem Çözümü

Genetik metoda epey bir ilgi var. Şu an itibarıyla Örnek Programlarım arasında ençok indirilen bu oldu. Genetik Programlamayla Bir İşlem = 395 (windows) + 72 (Linux) olmak üzere toplam 467 kere indirildi. Hatta Java versiyonunu da yazıldı.

Neyse biz konumuza geçelim geçenlerde bana bir mesaj geldi
... sizden genetik algoritma ile ilgili yardınızı istiyorum.Mezuniyet projem için genetik algoritma kullanilarak c veya c++ dort bilinmeyen denklemi cözen program yazmam gerekiyor ama nasil yapilacagi konusunda hic fikrim yok...
- Ahh Şöhreti kazibe -
Ben de yardımcı olmaya çalışacağımı bildirip konuyla ilgili detaylı bir mail atmasını istemiştim. cevap gecikmedi.
... o projeden vazgectim beni cok fazla zorlayacak. ... kare bulmaca (puzzle creator)yapmam daha dogru olucak ...
Bunun üzerine aslında korkulacak bir şey olmadığını göstermek ve bizim Fatih Presta'nın FGA
kütüphanesinin kullanımını anlatmak için basit bir örnek yazmaya karar verdim.

y=KatSayı1*x1+KatSayı2*x2+KatSayı3*x3+KatSayı4*x4+Sabit

denklemi 1 dereceden 4 bilinmeyenli bir denklemdir.
y=0 için x1,x2,x3,x4 değerlerinin bulunması lazım.

İşin teorik kısmını başkalarına bırakıp ben uygulamaya geçeceğim.

1) Bulmamız gereken 4 değer var. Kromozom uzunluğumuz 4 . Çözüm tamsayı olmaya bileceğine göre değişken tipi olarak da float seçiyoruz.
2) Olası çözümlerin kodlandığı bir çözüm gurubu oluşturmamız lazım - Population -

PopulationMT my_population(
number_of_threads, // Thread sayısı
number_of_chromosomes, // Kromozom Sayısı
length_of_chromosomes, // Kromozom Uzunluğu
my_fitness, // Uygunluk Fonksiyonu
NULL,
NULL,
my_crossover_operator, // Çaprazlama Fonksiyonu
my_mutate_chromosome, // Mutasyon Fonksiyonu
my_random_chromosome // Rasgele Kromozom Oluşturma Fonksiyonu
);


Göreceğiniz gibi Uygunluk Fonksiyonu, Çaprazlama Fonksiyonu, Mutasyon Fonksiyonu ve Rasgele Kromozom Oluşturma Fonksiyonu yazmamız lazım.

// Uygunluk Fonksiyonu
// Denklemin değerini hesaplıyoruz.
// Sonucun 0 olması kökün bulunması demektir.
// Sonucu biraz matematikle (0,1) arasına çekiyoruz
// 1'e ne kadar yakınsa çözüme o kadar uygun - sağlıklı -
float my_fitness(float *chromosome)
{
float *x=chromosome;
float y=kat[0]*x[0]+kat[1]*x[1]+kat[2]*x[2]+kat[3]*x[3]+Sabit;
if(y<0 br="br"> y=-1.0 *y;
y=1/(1+y);
return y;
}
// Çaprazlama Fonksiyonu
// FGA'nın Kendi sağladığı Fonksiyon da işimizi görebilir aslında
// Biz öğrenmek bakımından yazıyoruz
void my_crossover(float *chromosome1, float *chromosome2)
{
float tmp;
if(rand()%2){
// Tek Noktadan çaprazlama
//
1010 ----> 0110
//
0101 ----> 1001
tmp=chromosome1[0];
chromosome1[0]=chromosome2[0];
chromosome2[0]=tmp;
tmp=chromosome1[1];
chromosome1[1]=chromosome2[1];
chromosome2[1]=tmp;
}
else {
// İki Noktadan çaprazlama
//
1010 ----> 1111
//
0101 ----> 0000
tmp=chromosome1[1];
chromosome1[1]=chromosome2[1];
chromosome2[1]=tmp;
tmp=chromosome1[2];
chromosome1[2]=chromosome2[2];
chromosome2[2]=tmp;

}

}


// Mutasyon Fonksiyonu
void my_mutate_chromosome(float *chromosome)
{
int a;
int b;
float tmp;
a = rand() % 4;
do{
b = rand() % 4;
}while(a==b);

if(rand()%2)
tmp=1.001;
else
tmp=0.999;
chromosome[a]=chromosome[a]*tmp;

if(rand()%2)
tmp=1.001;
else
tmp=0.999;
chromosome[b]=chromosome[b]*tmp;
}

// Rasgele Kromozom Oluşturma Fonksiyonu
// Arama yapacağımız aralığı seçiyoruz ben (-20,20) aralığını seçtim.
// Bütün X değerleri bu aralıkta seçiliyor.
void my_random_chromosome(float *chromosome)
{
float *x=(float *)chromosome;
for(int i=0; i<4 i="i">


Artık Gurubumuzu oluştura biliriz.

PopulationMT my_population(10, 400, 4, my_fitness, NULL, NULL, my_crossover, my_mutate_chromosome, my_random_chromosome);
3) gerisi Bir döngü içinde yeterince iyi sonuca ulaşana kadar.
yada belli kuşak sayısına kadar, işleme devam etmek.
Bunun için önce cycle fonksiyonu çağrılıyor.
sonra ulaşılan en iyi sonucu almak için
get_all_time_best_score fonksiyonu çağrılıyor.


while ((1.0-score)>0.00001) {
my_population.cycle();
score = my_population.get_all_time_best_score();
}
hepsi bu kadar.
Gördüğünüz gibi çekinilecek hiç bir şey yok. Bence Kare Bulmaca hazırlamaktan daha kolay ;)
Indirmek için : Download Denklem

Not:
1) FGA'nın Threadlı versiyonunu kullanın düz olan kısmında problem var. POSIX thread konusu daha önceki yazımda anlatmıştım.

2) Konuyla ilgili sorularınız olursa, Biz buradayız bekleriz.

5 yorum:

Adsız dedi ki...

Elize sağlık çok güsel olmuşş

Unknown dedi ki...

iyi akşamlar arkadaşlar. hoca bize yapay zekayla ilgili bi proje yapmamızı istedi. bize fikir verebilcek ve yardım etcek bi arkadaş arıyorum. ilgilenirseniz sevinirim.

birol kuyumcu dedi ki...

iyi akşamlar
burda pek çok örnek bulabilirsin ötesi senin gayretine bağlı
profil sayfasında e-mail adresi var
oradan iletişime geçebilirsin

yetsin dedi ki...

Faydalı bir makale, paylaşım için teşekkürler. Örnek dosyayı verdiğiniz linkten indiremedim. Türkiye IP lerine izin vermiyor. Farklı yöntemlerle indirmeyi denediğimde sms atmamı istiyor. Verilen kodlar yardımcı olsa da anlamam için örneği görsem daha iyi olacak. Genetik programlama da çok yeniyim. Ödevim de bir o kadar zor sanırsam. Bir de ödevlerin çokluğu ve zaman aralığı yüzünden sıkışmış durumdayım. Yol göstermenizi rica ediyorum. Ödevim:
f(x,y)= 6.5x - 0.5x^2 - y1 - 2 y2 - 3 y3 -2 y4 - y5,
altta da 7 denklem sınır var...

birol kuyumcu dedi ki...

bir ara linki yeniden düzlerim ama aslında yazıda kodun çoğu var yetrliolması gerek diye düşünüyorum.
gerekirse profil kısmında e-mail adresim de var