Zeki Optimizasyon Teknikleri - 3 (Genetik Algoritma)

   Zeki Optimizasyon Teknikleri yazı dizimizin en son konusu olan Genetik Algoritma, diğer algoritmaların iyi yönlerini birleştiren modern ve etkili bir optimizasyon tekniğidir. Probleme göre en başarılı optimizasyon yöntemi değişmekle beraber Genetik algoritma günümüzde hemen her tür probleme başarı ile uygulanmaktadır. Hill Climbing gibi popülasyon tabanlı bir algoritmadır. Algoritmanın en önemli kısmı üretilen çözümü değerlendiren, fitness function olarak bilinen kısımdır.

   Genetik algoritma doğal seçilimden esinlenmiştir. Bu nedenle genetik algoritmada kullanılan terminoloji genetik ile alakalıdır. Algoritma ile alakalı yayınları ve çözümleri okurken kolaylık olması açısından genetik algoritma terminolojisini verelim.

•  Popülasyon: Çözüm adaylarından oluşan kümedir. Her birey geçerli bir çözüm olmakla birlikte değişik seviyeye sahiptir. Popülasyondaki tüm bireyler aynı şekilde kodlanmış olmalıdır. Probleme göre popülasyondaki birey sayısı büyük veya küçük tutulabilir. Her ikisinin de avantajları ve dezavantajları vardır. Genellikle popülasyondaki birey sayısına tecrübe ve/veya deneme yanılma yoluyla karar verilir.

Genetik algoritmada ileride anlatılacak tüm işlemler bir sonraki popülasyonu daha iyiye taşımaya yöneliktir.

• Kromozom: Popülasyon içerisindeki bireylerin(çözümlerin) her birine kromozom denir. Gerçek hayat problemlerinde genellikle çok sayıda değişkenin optimizasyonu yapılmak istenir. Bu durumda bir kromozom(çözüm) içerisinde pek çok değişken kodlanmış şekilde bulunur. 
•  Gen: Kromozom içerisindeki anlamlı en küçük bilgidir. Çok değişkenli optimizasyon problemlerimizde değişkenlerin her biri gen olarak adlandırılır. (Binary olarak kodlanmış kromozomlarda bir bit gen değildir. Bir kaç bitin oluşturduğu bir değişken bir gen dir.) 
•  Locus: Kromozom içinde genin bulunduğu konuma locus denir. Jenerasyon(nesil): Popülasyonun bir andaki durumudur. Bir iterasyon sonrasında daha iyi bir popülasyon(jenerasyon) oluşturulması amaçlanmaktadır. 
•  Eşleşme(Mating): Popülasyon içerisindeki kromozomların eşleşerek yeni bireyler(çözümler) oluşturma işlemidir. Yeni jenerasyona yeni oluşturulan çözümler aktarılır.

 Genetik algoritmada temel işlemler şu şekildedir.

1. Bir kromozomda tüm çözümü gösterecek şekilde uygun kodlamaya karar verilmesi. 
2. Başlangıç popülasyonunun oluşturulması. Rastgele veya tecrübe yardımıyla yapılabilir.
3. Popülasyon içerisindeki kromozomların fitness function yardımıyla değerlendirilerek her birine kalite etiketi atanması. 
4. Popülasyon içerisinde daha kaliteli kromozomlara daha çok şans vermek suretiyle rastgeleliği yönlendirerek eşleşme, mutasyon, elitizm gibi operatörler ile yeni bir jenerasyon oluşturulması.
5. Bu işlemlere belirlenen iterasyon sayısına ulaşana kadar ve yahut çözüm istenen kalite ölçüsüne erişinceye kadar devam edilir. Yukarıdaki her adımın pek çok değişik uygulama yöntemi bulunmaktadır.

   Genetik algoritma uygulaması kolay bir yöntem olmakla birlikte yukarıdaki adımları detaylıca açıklamayacağız. Genetik algoritmayı detaylarıyla öğrenmek istiyorsanız Zekai Şen hocamızın dilimizde çok güzel bir kitabı var.(Genetik Algoritmalar ve En İyileme Yöntemleri) Buradan ulaşabilirsiniz. 

   Bluekid abimizin iki adet çalışması var. Bunlardan bir tanesi bir-kelime bir-işlem yarışmasındaki bir işlem sorusun genetik algoritma ile çözülmesine yönelik. Bir diğeri ise 4 bilinmeyenli bir denklemin genetik algoritma ile sezgisel çözümü şeklinde.

 Linklerini verelim:

  Genetik metodla 4 Bilinmiyenli Denklem Çözümü

  Genetik Programlamayla Bir işlem

   Linklerdeki projelerde genetik algoritma için FGA -Fast Genetic Algorithm kullanılmıştır. Kullanımı oldukça kolay ve etkili bir kütüphane olmasına rağmen kütüphane kullanmaya aşina değilseniz veya genetik algoritma kısmını kendiniz yazmak istiyorsanız:

   http://www.generation5.org/content/2003/gahelloworld.asp adresinden aldığım aşağıdaki kod ile başlayabilirsiniz. Bu örnekte çözüm olarak "Hello world!" stringine ulaşılmaya çalışılıyor. Operatörler ve genetik algoritmanın kullanımı çok iyi. Bu kod üzerinden istediğiniz probleme yönelik değişiklikler yapabilirsiniz.

Bu yazının hazırlanmasında hocam Doç.Dr. M.Ali Akcayol' un Zeki Optimizasyon Teknikleri Dersi ders notları kullanılmıştır.

	#pragma warning(disable:4786) // disable debug warning
	#include <iostream> // for cout etc.
	#include <vector> // for vector class
	#include <string> // for string class
	#include <algorithm> // for sort algorithm
	#include <time.h> // for random seed
	#include <math.h> // for abs()
	#define GA_POPSIZE 2048 // ga population size
	#define GA_MAXITER 16384 // maximum iterations
	#define GA_ELITRATE 0.10f // elitism rate
	#define GA_MUTATIONRATE 0.25f // mutation rate
	#define GA_MUTATION RAND_MAX * GA_MUTATIONRATE
	#define GA_TARGET std::string("Hello world!")
	using namespace std; // polluting global namespace, but hey...
	struct ga_struct
	{
	string str; // the string
	unsigned int fitness; // its fitness
	};
	typedef vector<ga_struct> ga_vector;// for brevity
	void init_population(ga_vector &population,
	ga_vector &buffer )
	{
	int tsize = GA_TARGET.size();
	for (int i=0; i<GA_POPSIZE; i++) {
	ga_struct citizen;
	citizen.fitness = 0;
	citizen.str.erase();
	for (int j=0; j<tsize; j++)
	citizen.str += (rand() % 90) + 32;
	population.push_back(citizen);
	}
	buffer.resize(GA_POPSIZE);
	}
	void calc_fitness(ga_vector &population)
	{
	string target = GA_TARGET;
	int tsize = target.size();
	unsigned int fitness;
	for (int i=0; i<GA_POPSIZE; i++) {
	fitness = 0;
	for (int j=0; j<tsize; j++) {
	fitness += abs(int(population[i].str[j] - target[j]));
	}
	population[i].fitness = fitness;
	}
	}
	bool fitness_sort(ga_struct x, ga_struct y)
	{ return (x.fitness < y.fitness); }
	inline void sort_by_fitness(ga_vector &population)
	{ sort(population.begin(), population.end(), fitness_sort); }
	void elitism(ga_vector &population,
	ga_vector &buffer, int esize )
	{
	for (int i=0; i<esize; i++) {
	buffer[i].str = population[i].str;
	buffer[i].fitness = population[i].fitness;
	}
	}
	void mutate(ga_struct &member)
	{
	int tsize = GA_TARGET.size();
	int ipos = rand() % tsize;
	int delta = (rand() % 90) + 32;
	member.str[ipos] = ((member.str[ipos] + delta) % 122);
	}
	void mate(ga_vector &population, ga_vector &buffer)
	{
	int esize = GA_POPSIZE * GA_ELITRATE;
	int tsize = GA_TARGET.size(), spos, i1, i2;
	elitism(population, buffer, esize);
	// Mate the rest
	for (int i=esize; i<GA_POPSIZE; i++) {
	i1 = rand() % (GA_POPSIZE / 2);
	i2 = rand() % (GA_POPSIZE / 2);
	spos = rand() % tsize;
	buffer[i].str = population[i1].str.substr(0, spos) +
	population[i2].str.substr(spos, esize - spos);
	if (rand() < GA_MUTATION) mutate(buffer[i]);
	}
	}
	inline void print_best(ga_vector &gav)
	{
	cout<<"Best: "<<gav[0].str <<"("<<gav[0].fitness <<")"
	<<endl;
	}
	inline void swap(ga_vector *&population,
	ga_vector *&buffer)
	{
	ga_vector *temp = population;
	population = buffer;
	buffer = temp;
	}
	int main()
	{
	srand(unsigned(time(NULL)));
	ga_vector pop_alpha, pop_beta;
	ga_vector *population, *buffer;
	init_population(pop_alpha, pop_beta);
	population = &pop_alpha;
	buffer = &pop_beta;
	for (int i=0; i<GA_MAXITER; i++) {
	calc_fitness(*population); // calculate fitness
	sort_by_fitness(*population); // sort them
	print_best(*population); // print the best one
	if ((*population)[0].fitness == 0) break;
	mate(*population, *buffer); // mate the population together
	swap(population, buffer); // swap buffers
	}
	return 0;
	}

view raw genetikAlgoritma.cpp hosted with ❤ by GitHub

Kod