Genetik algoritma, evrimsel fikirlerden esinlenilerek ortaya çıkan bir sezgisel arama algoritmasıdır. Doğal seçilim, mutasyon gibi evrimsel kavramları kullanarak optimizasyon problemlerini çözmeye çalışır.
Genetik algoritmanın nasıl çalıştığını anlayabilmek için basit bir problemin üstünde duracağız. Problemi şöyle tanımlayabiliriz; ekrana "genetik algoritma" yazdırmak. Elbette bunu daha basit yollarla halledebilirdik fakat amacımız genetik algoritmanın nasıl çalıştığını kavramak.
Genetik algoritmaların temel olarak 5 aşamadan oluştuğunu söyleyebiliriz. Bunlar aşağıdaki gibidir:
- Popülasyonun Oluşturulması
- Uygunluk Fonksiyonu (Fitness Function)
- Seçim (Selection)
- Çaprazlama (Crossover)
- Mutasyon (Mutation)
Popülasyonun Oluşturulması
Genetik algoritmanın ilk aşaması bir popülasyon oluşturulmasıdır. Bu popülasyonun içinde bizi çözüme götürecek aday bireyler olacaktır. Her bir bireye kromozom adını vereceğiz. Kromozomlar ise kendi içinde genleri bulunduracak.
Popülasyonun oluşturulmasında en önemli nokta genlerin nasıl temsil edildiğidir. Temsil biçimleri problemden probleme değişiklik gösterir. İkili, sayısal, permütasyon sık kullanılan temsil biçimleridir. Bizim problemimizde temsil biçimi belli bir uzunluğa sahip karakter dizisi olacaktır çünkü amacımız ekrana bir karakter dizisi yazdırmak.
Uygunluk Fonksiyonu (Fitness Function)
Uygunluk fonksiyonu bir kromozomun istenen şartlara ne kadar uygun olduğunu ölçmemizi sağlar. Her kromozom için bir uygunluk skoru (fitness score) hesaplanır. Bu skorlar en iyi kromozomun seçilmesinde kullanılır. Peki uygunluk fonksiyonunu kendi problemimize nasıl uyarlayabiliriz? Genler, karakter dizilerinden oluşmaktaydı ve bizim bu dizilerin hedef karakter dizisine ne kadar yakın olduğunu ölçmemiz gerek. Her iki dizide de i. karakterin ascii kodlarını karşılaştırarak bunu kolayca yapabiliriz.
getFitness() {
let target = GeneticAlgorithm.target;
let fitness = 0;
for(let i = 0; i < target.length; ++i) {
fitness += Math.abs(target.charCodeAt(i) - this.gene.charCodeAt(i));
}
return fitness;
}
Bir kromozomun genlerinin "genatig olgarikma" ve hedefinde "genetik algoritma" olduğunu düşünürsek, iki dizide de i. karakterlerin farkını alıp daha sonra mutlak değerini alabiliriz. En sonunda hepsini toplarız ve bu değer 0'a ne kadar yakınsa genlerimiz o kadar uygun olacaktır. Örneğin, yukarıdaki genler ve hedef dizisine göre uygunluk skorunu hesaplarsak sonuç 45 olacaktır.
Seçim (Selection)
Hesaplanan uygunluk skorlarına göre en iyi kromozomlar seçilir ve genlerinin bir sonraki nesile aktarılması sağlanır. Seçimi yapabilmek için bir çok yöntem vardır. Biz bu yazımızda oldukça basit bir yöntem kullanacağız. En iyi iki kromozomu alacağız.
getBestTwo() {
let fitness = [];
for(let i = 0; i < this.populationSize; ++i) {
fitness[i] = this.population[i].getFitness();
}
let fittest1 = 0;
let fittest2 = 1;
for(let i = 0; i < this.populationSize; ++i) {
if(fitness[i] < fitness[fittest2]) {
fittest2 = i;
}
if(fitness[fittest2] < fitness[fittest1]) {
let temp = fittest1;
fittest1 = fittest2;
fittest2 = temp;
}
}
return [fittest1, fittest2];
}
Çaprazlama (Crossover)
Seçim işleminden sonra artık elimizde iki kromozom bulunmakta, bu kromozomların genlerinden rastgele seçerek çaprazlama yapacağız. Çaprazlama işleminin amacı iki kromozomun genleri karıştırarak, ikisininde özelliklerini taşıyan bir kromozom elde etmektir. Aşağıda C1 ve C2 kromozomlarının nasıl çaprazlandığını şekil üzerinde inceleyebilirsiniz.
Çaprazlama noktası rastgele seçilir. O noktanın solundakiler ilk kromozomdan, sağında kalanlar ise diğer kromozomdan alınır. Bu sayede iki kromozomunda özelliklerini taşıyan yeni bir birey ortaya çıkar.
crossover(other) {
let crossoverGene = '';
let rnd = Math.floor(Math.random() * this.gene.length);
for(let i = 0; i < this.gene.length; ++i) {
if(i < rnd) {
crossoverGene += this.gene[i];
} else {
crossoverGene += other.gene[i];
}
}
let crossover = new Chromosome();
crossover.gene = crossoverGene;
return crossover;
}
Mutasyon (Mutation)
Mutasyon adından da anlaşılacağı gibi bazı genlerin mutasyonlar geçirmesi ile oluşur. Mutasyonun olup olmayacağına mutasyon oranı (mutation rate) adını verdiğimiz bir parametreye göre karar veririz. Mutasyon oranı 0 ile 1 aralığında değer alabilir. Örneğin; 0.25, genin %25 mutasyon geçirme ihtimalinin olduğunu belirtir.
Aşağıda ufak bir uygulama bulunmakta. Buradan mutasyon oranıyla oynayarak, problemin kaç nesilde çözüldüğünü inceleyebilirsiniz. İlerle butonuna basıldığında maksimum 5000 nesil ileri gidilecektir. Eğer 5000. nesile gelmeden çözüme ulaşılırsa program sonlanacaktır. Sıfırla butonuna basıldığında tüm popülasyon yeniden oluşturulur.
Yukarıdaki uygulama için kullanılan mutasyon fonksiyonu aşağıdaki gibidir:
mutate() {
let chars = GeneticAlgorithm.chars;
let mutationRate = GeneticAlgorithm.mutationRate;
let mutatedGene = '';
for(let i = 0; i < this.gene.length; ++i) {
if(Math.random() < mutationRate) {
let rnd = Math.floor(Math.random() * chars.length);
mutatedGene += chars[rnd];
} else {
mutatedGene += this.gene[i];
}
}
let mutated = new Chromosome();
mutated.gene = mutatedGene;
return mutated;
}
Sonuç
Genetik algoritmalar çok güçlü arama algoritmalarıdır fakat bir probleme uyarlayabilmek için temsil biçimi ve uygunluk fonksiyonu iyi tanımlanmalıdır. Gezgin satıcı (travelling salesman), sırt çantası (knapsack) genetik algoritmayla çözülebilen popüler problemlerdir. Burada öğrendiklerinizi bu tarz problemlere uygulayarak kendinizi geliştirebilirsiniz.
Kodların tamamını github'da bulabilirsiniz.