Skip to content

Genetik algoritmalar: Değişime uyum sağlamanın önemi – Ahmet Tuğrul Bayrak

Yazar : Ahmet Tuğrul Bayrak

ATP ArGe Kıdemli Yazılım Geliştirme Uzmanı

Bilim, mühendislik, sosyal bilimler gibi pek çok alanda optimizasyon ve arama problemlerinin çözümünde kullanılan genetik algoritmalarda en önemli adım, ulaşılmak istenen uygunluk değerinin ve bu değerin hesaplanma yönteminin belirlenmesidir.

”Ne en güçlü olan tür hayatta kalır, ne de en zeki olan… Değişime en çok adapte olabilendir, hayatta kalan!” Charles Darwin’e atfedilen bu söz, değişime uyum sağlamanın önemini vurgular. Ulaşılmak istenen hedefe adapte olmak, bir evrimsel algoritma çeşidi olan genetik algoritmanın da temelini oluşturur.

Doğadaki evrimsel süreçleri temel alarak çalışan genetik algoritmaların temel ilkesi, ulaşılmak istenen hedefe götürecek adaylardan zayıf olanların elenerek en güçlü olanların kalmasıdır. Genetik algoritmalar; bilim, mühendislik, sosyal bilimler gibi pek çok alanda, optimizasyon ve arama problemlerinde kullanılmakta.

Hedefe erişmek adına zayıf olanın elenmesi

Genetik algoritmaların çalışma prensibinde aday çözümlerden her biri, bir kromozom ile temsil edilirken, kromozomu oluşturan genler ise çözümün sahip olduğu değerlere karşılık gelir. Popülasyonda bulunan kromozomların birbirleriyle etkileşime geçerek yeni nesiller üretmesi (“cross-over”) ve hedefe yaklaşmaya çalışmasıyla, doğal evrim sürecine benzer olarak, topluluktaki bireyler de değişikliğe uğrar (“mutation”). Bu sürecin sonucunda oluşan yeni bireyler, güçlü olmaları halinde toplulukta yer almaya devam ederken, zayıf olmaları halinde ise topluluğun kalitesini düşürmemek adına elenir. Belirlenmiş olan hedefe erişildiğinde ya da yaklaşıldığında, veya önceden tanımlanmış bir iterasyon sayısında ulaşıldığında genetik algoritma sonlanır.

Söz konusu kavram ve adımları daha iyi açıklamak üzere, basit bir örnek üzerinden ilerleyelim. Amacımız, rastgele beş sayıdan oluşan ve toplamı 100 yapan bir sayı dizisi oluşturmak olsun.

Bireylerin kromozom olarak temsili

Genetik algoritmada popülasyondaki bireylerin, biyolojideki kromozom kavramıyla, birey özelliklerinin ise kromozomu oluşturan genler ile temsil edildiğini belirtmiştik. Bu kavramları problemimize uyarladığımızda [1, 23, 67, 12, 52] değerlerinden oluşan bir kromozom, aşağıdaki gibi gösterilebilir.

Kromozom temsili

Doğru popülasyon üretimi, algoritmanın başarısı için önemli

Genetik algoritmanın verimli ve başarılı olması için, kromozom temsilinin doğru ve etkili bir şekilde yapılması yaşamsal öneme sahiptir. Problemin çözümüne ulaştıracak kromozomların genleri başlangıçta rastgele oluşturulabileceği gibi, probleme özgü mantıkla daha akıllı bir şekilde de oluşturulabilir. Model, N sayıda kromozom ile oluşturulan popülasyon ile iterasyona hazır hale gelir.

Uygunluk değerinin belirlenmesi (“Fitness value”)

Hedefimize ne kadar yaklaştığımızı anlayabilmek için, popülasyondaki kromozomların (bireylerin) ne kadar güçlü (başarılı) olduğu ölçülmeli. Bu sayede zayıf kromozomlar elenecek ve popülasyonun kalitesiyle beraber hedefe ulaşma ihtimali de arttırılacaktır.

Genetik algoritma problemlerinde en önemli adım, ulaşılmak istenen uygunluk değerinin ve bu değerin nasıl hesaplandığının belirlenmesidir. Örneğimizde, bir kromozomun uygunluk değeri, genlerin ([1, 23, 67, 12, 52]) sayı değerleri toplamının 155 olmasından hareketle, mutlak değer ile,

|100 – 155 | = 55

olarak hesaplanabilir. Aradaki fark sıfıra ne kadar yakınsa o kromozom bizim için o kadar güçlüdür.

Çaprazlama (“Cross-over”)

Popülasyonu oluşturduktan sonra seçilen iki kromozom, kendi aralarında etkileşime geçerek yeni kromozomlar üretir. Bu etkileşim gen alışverişi şeklinde gerçekleşir. Örnek ikinci kromozomumuz [45, 12, 8 ,6, 11] iken bu iki kromozom, genlerinin (sayıların) bir kısmını değiştirerek yeni kromozomlar oluşturacaktır. Alttaki şekillerde örneğimizdeki iki kromozomun etkileşimi görülüyor.

Çaprazlanacak iki kromozom

Çaprazlama sonrası oluşan yeni kromozomlar

Üstteki şekillerde göründüğü gibi, birinci kromozomun ilk iki geninin ikinci kromozomun son iki geniyle değiştirilmesi sonucu, uygunluk değerleri 55 ve 18 olan iki kromozomdan, 41 ve 11 olan iki yeni kromozom elde edildi. Üstelik bu yeni kromozomlardan biri, bahsedilen dört kromozom arasında en güçlü olanı.

Çaprazlanacak kromozomların ve değiştirilecek genlerin seçiminde farklı yöntemler uygulanabilir. En Güçlü kromozomların çaprazlanma ihtimalinin yüksek olduğu bir sistem kurulabileceği gibi, seçim tamamen rastgele de yapılabilir.

Mutasyon (“Mutation”)

Kendi aralarında gen alışverişi yapan kromozomların yeni bireyler oluşturması sırasında gen çeşitliliğinin az olması, belirli bir süre sonra popülasyonun lokal minimum ile sınırlı kalmasına ve daha güçlü kromozomların oluşmamasına neden olabilir. Bu durumda popülasyonun çeşitliliğini arttırmak için kromozomlar, genlerinin bir kısmı değiştirilerek mutasyona uğratılır. Çaprazlama ile benzer şekilde, mutasyon sonucunda daha güçlü bireyler kadar, daha zayıf bireyler de oluşabilir. Her iterasyon için zorunlu olmayan mutasyon, belirli bir olasılık değeri ile veya popülasyonun lokal minimum ile sınırlı kaldığı durumlarda da uygulanabilir.

Mutasyon sonrası oluşan kromozom

Eleme

Çaprazlama ve mutasyon sonucunda oluşan yeni bireylerin uygunluk değerleri hesaplandıktan sonra en zayıf adaylar (eskiden popülasyonda olan ya da yeni üretilen), popülasyon sayısını sabit tutacak şekilde elenir. Bu sayede popülasyonun toplam başarı ihtimali arttırılır ve daha önemlisi, başarı ihtimalinin azalmayacağı garanti altına alınmış olur.

Aşağıdaki akışta yapılan tüm işlemleri toparlayalım.

Genetik algoritma akış şeması

Örnek uygulamalar

Bahsettiğimiz problemdeki rastgele beş farklı sayıdan oluşan kromozomlardan, sayı değerleri toplamı 100 yapan bir kromozom oluşturmaya çalışalım. Aşağıdaki üç farklı çıktıda sırasıyla; çaprazlama ve mutasyon, sadece çaprazlama ve sadece mutasyon uygulanmakta. Grafiklerdeki “en küçük”, “en büyük” ve “ortalama” değerleri ise sırasıyla; popülasyondaki en başarılı, en başarısız ve ortalama uygunluk değerlerini gösteriyor.

Birinci yaklaşım, 48. iterasyonda istenen değere ulaşan sayıları ([39, 11, 12, 30, 8]) üretirken, ikinci yaklaşımda 248. iterasyonda gerekli değere ([8, 9, 37, 9, 37]) ulaşılıyor. Üçüncü yaklaşım ise 1000. iterasyon sonucu ulaşılmak istenen değere yaklaşsa da, ulaşamamakta ([22, 1, 10, 14, 55]).

Çaprazlama ve mutasyonun etkileri

Deney bize, çaprazlama ve mutasyonun beraber kullanıldığı durumun en başarılı yöntem olduğunu gösteriyor. Sadece çaprazlamanın kullanıldığı ikinci yöntemde, gen alışverişi sonrasında çeşitliliğin gittikçe azalması, çözümün lokal minimumda takılmasına ve en düşük, en yüksek ve ortalama uygunluk değerlerinin birbirine yaklaşmasına sebep oluyor. Oysa birinci yöntemde, kullanılan mutasyon sayesinde çeşitlilik artıyor ve en güçlü uygunluk değeri ikinci yöntemdeki gibi sabit kalmıyor. Sadece mutasyon uygulanan üçüncü yöntem ise rastgele arama (“random search”) yöntemi şeklinde davranıyor ve sonuca ulaşamıyor.

Genetik algoritmayı farklı bir alanda uygulamak için ikinci bir deneme daha yapalım. Bu örnekteki amacımız da, rastgele piksel değerlerinden oluşan kromozomlardan, istediğimiz bir görsele ulaşmak olsun.

Oluşturmak istenen hedef görsel

Bu problemde uygunluk değeri olarak, kromozomlarla orijinal görseldeki piksellerin farkını alalım. Fark ne kadar küçükse, orijinal görsele o kadar yakınız demektir. Önceki probleme benzer bir mantıkla yaklaşılan bu problemde de farklı iterasyonlardaki en güçlü kromozomlar ve modeldeki iyileşme aşağıdaki şekilde görülüyor.

Uyguladığımız iki örnek de genetik algoritmanın çalışma mantığını en basit şekilde aktarıyor. İlk uygulama, genetik algoritmaların çalışma mantığının rahat takibi için açık bir şekilde ve bir genetik algoritma kütüphanesi kullanılmadan yazıldı. İkinci uygulamanın kodu ise hazır bir kütüphanenin nasıl kullanıldığı göstermek için, PyGAD kütüphanesi kullanılarak geliştirildi. Bu kodlara GitHub üzerinden erişebilirsiniz.*

Faydalı olması dileğiyle…

 

* Örnek 1: https://github.com/tbayrak/genetic-algorithms/blob/main/basic_ga.py

*Örnek 2: https://github.com/tbayrak/genetic-algorithms/blob/main/image_generator_ga.py

 

 

Diğer Blog Yazılarımıza Göz Atın