Genetik Algoritma

Utku Kubilay ÇINAR 21 Temmuz 2019 Genel bir bakış, R, Teknik, Uygulama, Veri Bilimi 3 22335 1317 kelime - 9 dakika190

---

Bu yazıya puan ver

(5 votes, average: 4,80 out of 5)

Loading...

---

GENETİK ALGORİTMA İLE TESLİMAT ROTASI OLUŞTURMA (Delivery Route using Genetic Algorithm) Utku Kubilay ÇINAR

Yapay Zeka alanında kullanılan Genetik Algoritma, bir tür en iyi noktayı arayan algoritmadır. Bir probleme çözüm aramakla ilgilenir. Gerçek hayatta karşılaştığımız bir problemi (kuru yük gemisine konteynerler nasıl yerleştirilmeli, bir noktadan başka bir noktaya nasıl gidilebilir ya da en uygun teslimat rotası oluşturma gibi), biz bir arama problemine dönüştürebilirsek, bu problemi Genetik Algoritma ile çözebiliriz.

Genetik Algoritma (GA), permütasyon tabanlı bir optimizasyon yapar ve olasılıklar üzerinden yakınsama kriterleri altında arama yapan bir fonksiyondur. Doğada gözlemlenen evrimsel sürece benzer bir şekilde çalışan, arama ve eniyileme yöntemidir. Genetik Algoritma literatürde şöyle açıklanmıştır: Genetik Algoritma, biyolojik evrimin temel prensiplerinden ilham alan güçlü bir evrimsel stratejidir. Araştırmacı öncelikle değişken tipini ve ele aldığı problemi doğru tanımlamalı ve kodlamasını bu tanımlamaya göre yapmalıdır. Ardından algoritmanın girdilerinden olan uygunluk fonksiyonu (fitness) tanımlanır ve optimize edilmesi gereken amaç fonksiyonu bu fonksiyondur. Geçiş ve Mutasyon gibi genetik operatörler, evrim sürecinin birçok aşamasında stokastik olarak uygulanmaktadır, bu yüzden gerçekleşme olasılıkları belirlenmelidir. Son olarak yakınsama kriterleri sağlanmalıdır ve optimal maliyet ile problem çözülmelidir. GA, problemin çözülebilmesi için lokal değil, global bir araştırma yapar. Problemi etkileyen çok fazla etken varsa, çözümde Genetik Algoritma kullanılması literatürce önerilmektedir.

Kısaca Genetik Algoritma çalışma prensibi aşağıdaki görsel gibidir.

Amaç fonksiyonu optimizasyonu, yapay sinir ağlarının eğitimi, bulanık sistemlerde üyelik fonksiyonlarının belirlenmesi, sistem kimliklendirme ya da sistem kontrolü gibi alanlarda bu algoritmalar başarılı şekilde kullanılabilmektedir.

Algoritma toplum adı verilen ve kromozomlarla temsil edilen bir çözüm kümesi ile başlamaktadır. Bir toplumdaki çözümler yeni toplumların üretilmesinde kullanılmaktadır. Bu işlem, yeni toplumun (popülasyon) eskisinden daha iyi olacağı umuduyla yapılmaktadır. Yeni çözümler (yavru) üretmek için alınan çözümler uygunluklarına (fitness) göre seçilmektedir. Daha uygun olan tekrar üretim için daha fazla şansa sahiptir. Bu süreç belli bir durum (örneğin belli sayıda toplum veya en iyi çözümün gelişmesi) karşılanana kadar tekrar edilmektedir (Sarıkaynak, E.).

Genetik Algoritma ve Makine Öğrenmesi Yöntemiyle bilgisayara oynatılmış Mario Oyun Görseli;

UYGULAMA

Genetik Algoritma konusunu daha iyi anlayabilmek için yazının uygulama kısmında 2 farklı örnekle uygulama yapılmıştır.

Örnek-1

İlk uygulamada, Sınırlandırılmış Optimizasyon ile konuyu ele alalım. Genetik Algoritma yukarıda da belirttiğim gibi permütasyon tabanlı olup, kısıtlar altında (yakınsama kriteri) olasılıklar üzerinden arama yaparak global minimum noktası, çözüm noktası/noktaları aranır ve problem çözülür.

İlk örnekte bir askeri ya da bir dağcıyı düşünelim. Bu kişi sırt çantasında bazı eşyaları/aletleri taşıyor olsun. Bazı aletler çok ağırken, bazıları çok hafif ama her aletin önemi bir değil. Her insanın taşıyabileceği bir ağırlık var. Bu ağırlık kısıtı altında, çok sayıda ve önemli aletleri yanına almak zorunda. Bir dağcı yanına önemli aletleri almak istiyor fakat o kişi en fazla çantasında 15 kilogram taşıyabiliyor. İlk örneğimiz böyle bir problem olsun. Bu problemi Genetik Algoritma (GA) kullanarak permütasyonlarla R programına kodlayalım ve çözelim.

Sırt çantamıza koyabileceğimiz toplamda 7 farklı çeşit aletimiz var. Bunların önemi ve ağırlıkları farklı. Aşağıdaki tablodan aletlerin önem düzeyini ve ağırlıklarını görebilirsiniz.

Şimdi bu durumu programa kodlayalım.

Çıktıda da görüldüğü üzere Genetik Algoritmanın 221 döngüde bulduğu global çözüm noktalarımız şu şekilde: Dağcının ağırlık kısıtı altında yanına alabileceği ve maksimum fayda sağlayabileceği aletler; 1. Alet, 2. Alet, 4. Alet ve 5. Alettir.
İkinci örneğimize geçelim.

Örnek-2

Genetik Algoritmalar, lojistik ve taşımacılık optimizasyonlarında çok sık kullanılan eniyileme yöntemlerinden biridir. GA, en az benzin maliyeti ile zaman kaybını önleyecek, yol haritasını bizlere sunmaktadır. Bu 2. örnekte sizlerle beraber, bir tırın Avrupa şehirlerine uğrayarak yükünü boşaltabileceği bir yol haritası oluşturacağız. Buradaki kısıtımız en az maliyet ile başlangıç, bitiş ve sırayla hangi illere uğrayacağını belirlemektir.

Bu uygulama, GA çalışmalarında, bilimsel makalelerde ve uygulamalarda sıklıkla kullanılan R programında bulunan “Eurodist” veri seti ile yapılmıştır. Öncelikle veri setimizi tanıyalım.

Avrupa şehirlerinin birbirine olan uzaklıkları

Yol haritamızı şimdi harita üzerinde görselleştirelim. Bunun için şehirlerin Google Maps üzerinden Enlem ve Boylam bilgilerini çekmemiz gerekiyor (Yazının ilerleyen kısımlarında aşağıdaki görseli beraber oluşturacağız).

Öncelikle Genetik Algoritma modelimizi oluşturmadan önce verimizi, modelin istediği formata sokmamız ve fitness fonksiyonunu yazmamız gerekiyor. Tüm kodlara aşağıdaki görselden ulaşabilirsiniz.

2469 iterasyondan sonra Genetik Algoritmamızın bize önerdiği yol haritası Solutions kısmında yazmaktadır. Burada 21 Numaralı şehirden başlayıp, 1 numaralı şehir ile turu sonlandırmamız gerektiğini algoritma bize söylemektedir. Yani Viyana ile başlayıp, Atina ile lojistik taşıma ağımızı bitirmemiz gerektiğini öğrenmiş oluyoruz.

Yol haritamızı öğrendikten sonra R programı üzerinden Coğrafik Veri Görselleştirme ya da Coğrafik Bilgi Sistemi (GIS) kullanarak dünya haritası üzerinden şehirlerimi belirleyelim. Öncelikle bu işlem için şehirlerimizin enlem ve boylam bilgilerine yani koordinatlarına erişmemiz gerekiyor.

Şehirlerin enlem ve boylam bilgilerine ulaştık, ardından her şehrin birbirine olan uzaklığını da bulmuş olduk. Şimdi koordinatlarımızı harita üzerine yerleştirelim. Elde edeceğimiz görsel şu şekilde olacaktır:

Sonuç olarak; Genetik Algoritma, Kurt Sürüsü Algoritması (A Wolf Colony Algorithm) gibi algoritmalar biz veri bilimcilerin, veri ile uğraşan kişilerin, her türlü optimizasyondan sorumlu olan kişilerin sıklıkla kullandığı algoritmaların başında gelir. Genetik Algoritma, doğada gözlemlenen evrimsel sürece benzer bir şekilde çalışan, arama ve eniyileme yöntemidir. Ayrıca permütasyon tabanlı olması ve kısıtlar altında (yakınsama kriteri) olasılıklar üzerinden arama yaparak global minimum noktasını belirleyebilmesi bu algoritmayı önemli hale getirmiştir.

Varsayımlarınızın sağlanması dileğiyle,

Veri ile kalın, hoşça kalın…

KAYNAKÇA

• BAĞIŞ, A. ve ÖZÇELİK, Y., Gerçek Kodlu Genetik Algoritma Kullanarak Sistem Kimliklendirme, Erciyes Üniversitesi, Kayseri.
• Scrucca, L. (2013). GA: A Package for Genetic Algorithms in R. Journal of Statistical Software, 53(4), 1 – 37. doi:http://dx.doi.org/10.18637/jss.v053.i04
• Pham, D.T., Karaboga, D., (2000), “Intelligent Optimisation Techniques: Genetic Algorithms, Tabu Search, Simulated Annealing and Neural Networks”, SpringerVerlag
• https://kodveus.blogspot.com/2006/09/genetik-algoritmalar-blm-iv-seim.html
• https://ahmetcevahircinar.com.tr/2017/08/08/genetik-algoritma-nedir-genetik-algoritma-nasil-calisir/
• https://emresarikaynak.com.tr/genetik-algoritma-nedir.html
• http://rpubs.com/somasdhavala/GAeg
• https://www.youtube.com/watch?time_continue=114&v=qv6UVOQ0F44
• https://towardsdatascience.com/introduction-to-genetic-algorithms-including-example-code-e396e98d8bf3
• https://www.nature.com/articles/srep37616