Posted on: 24 Ağustos 2019 Posted by: alidemirkaya Comments: 0

Genetik Algoritmalar-Nasıl Kullanırız

Herkese merhabalar. Sizlerden kısa bir zamanınızı isteyerek şu ana kadar duyduğunuz genetik algoritmaların aslında sandığınızdan daha kolay bir kullanım olduğunu anlatmaya çalışacağım.

Genetik algoritma 1970 ‘li yıllarda Darwin ‘in doğal seçilim ve evrim teorisine dayanan ilkelerine dayanan bir algoritma olarak ortaya çıkmıştır. En çok kullanım alanı ise yöneylem araştırmasında gördüğümüz Gezgin Satıcı Problemi ‘dir. Biraz inceleyelim, bir gezgin satıcı bir noktadan başlayarak belirli noktaları gezip tekrardan başa dönmesi gerekmektedir. Gezdiği bu noktaları öyle bir sırada dolaşması gerekir ki en kısa mesafe yolu bulabilsin.

Bu problemin çözümü için bir algoritma geliştirilememiştir. Ancak sezgisel ve metasezgisel algoritmalar, gezgin satıcı gibi sonsuz çözümlerin bulunduğu problemlerin çözümlerinde iyi bir rol oynamışlardır. Genetik algoritma da sezgisel algoritmalardan bir tanesidir.

Buraya kadar hiç uzatmadan kısaca anlatmaya çalıştım. Neredeyse sonsuz bir çözüm kümesi içerisinden en iyiyi bulma yöntemidir. Ancak her bir algoritmanın işleyişinin dayandırıldığı veya benzetildiği bir yöntem vardır. Genetik algoritma ise doğal seçilime dayandırılmaktadır. Canlılar, doğada yaşamlarını sürdürmek için
savaşırlar ve güçlü olanlar savaşı kazanır. Yeni bir nesil için iyi bireyler seçilir ve bunlardan çocuklar üretilir. Asıl amaç ise iyi bir kuşak oluşturmaktır.

Çözdüğünüz veya çözdüreceğiniz problemlerde de amacınız en iyi kuşağı, en iyi çözümü bulmaktır. Şimdi bir problem üzerinde anlatmaya çalışacağım. En çok kullanılan problemlerden biri de bin packing problemidir. Elimizde belirli bir parça veya malzemeler var. Bu malzemeleri kutuların içerisine yerleştireceğiz. Öyle bir yerleşim yapmalıyız ki en düşük sayıda kutu kullanalım. Örneğin ;

Yukarıda bir yerleşim sunulmuştur. Belki bundan daha iyi bir yerleşim de mevcut olabilir. Genetik algoritmayı biz nasıl uygularız. Öncelik bu malzemeleri yerleştirebilmek için bize bir sıra lazım. Yani algoritma bu sırayı kendine göre yazmıyor. Siz onun bir sıra üretmesini sağlıyorsunuz. Mesela fotoğrafa bakacak olursak soldan başlayarak [10-1-6-5-3-9-8-7-4-2] sırası uygulanmıştır diyebiliriz. Algoritmanın çalışma prensibi ise bu sıra üzerinden gerçekleşmektedir (Binary olarak da yapabilirsiniz). Sırayı geliştirdiğiniz algoritmaya gönderirsiniz o size kaç koli kullanıldığını söyler. Tüm olay bu şekilde gerçekleşir. Nasıl çalışır ona bakalım.

Yazının başında dediğim gibi belirli bir aileden çocuklar meydana gelecek ve en iyilerini seçeceğiz. Başlangıç aşamasında algoritmaya bir aile vermek zorundayız. O yüzden başlangıç aşamasında rastgele sıralar üretiriz. Ürettiğimiz bu sıraların adedine biz popülasyon büyüklüğü diyoruz. Sonrasında her bir sırayı geliştirdiğimiz algoritmaya gönderiyoruz ve buradan bir sonuç elde ediyoruz. Bu sonuçlar yukarıda ki görselde koli sayısı, GSP probleminde mesafe miktarı gibi değerlerdir. Bu değerlere ise fitness value diyoruz.

Fitness değerleri hesaplanan sıraları bir yerde toplayalım şimdi. Ne demiştik iyi bir kuşak oluşturmaktı amacımız. Bu kuşakları oluştururken öncelikle bir seçilim yöntemi uyguluyoruz. Genel olarak seçme yöntemi rulet tekeri yöntemi ile sağlanıyor. Oluşturduğumuz fitness tablosundan kromozomları (her bir sıra kromozom olarak tanımlanmaktadır) seçerek bunları çaprazlama ve mutasyon işlemlerine tabi tutuyoruz. Bu işlemler aşağıdaki gibidir.

Bu 2 yöntem sonucunda oluşan yeni kromozomları eski kromozomlarla karşılaştırarak kötü olanlarla yerlerini değiştiriyoruz. Bu işlemler bittikten sonra. Bir sonraki aşamaya geçiyor. Çünkü kötüleri değiştirdik yeni kromozomlar meydana geldi ve o kromozomları tekrar çözdürmek için aynı işlemleri tekrar ediyoruz. Her bir tekrara ise iterasyon denilmektedir.

İşte genetik algoritma ve genel işleyişi bu şekildedir. Matlab ortamında bir genetik algoritma için aşağıdaki videoyu izleyebilirsiniz. Bir başka yazıda görüşmek dileğiyle esen kalın.

 

 

 

Leave a Comment