Genetik Algoritmalar - İleri Konular

Bu bölümde, Genetik Algoritmalarla ilgili bazı gelişmiş konuları tanıtıyoruz. GA'lara giriş yapmak isteyen bir okuyucu bu bölümü atlamayı seçebilir.

Kısıtlı Optimizasyon Sorunları

Kısıtlı Optimizasyon Problemleri, belirli kısıtlamalara tabi olan belirli bir amaç fonksiyon değerini maksimize etmemiz veya minimize etmemiz gereken optimizasyon problemleridir. Bu nedenle, çözüm uzayındaki tüm sonuçlar uygulanabilir değildir ve çözüm alanı aşağıdaki resimde gösterildiği gibi uygulanabilir bölgeler içerir.

Böyle bir senaryoda, çaprazlama ve mutasyon operatörleri bize mümkün olmayan çözümler sunabilir. Bu nedenle, kısıtlı Optimizasyon Sorunları ile uğraşırken GA'da ek mekanizmaların kullanılması gerekir.

En yaygın yöntemlerden bazıları -

• Kullanma penalty functions Bu, uygulanabilir olmayan çözümlerin uygunluğunu azaltır, böylece uygunluk, ihlal edilen kısıtlamaların sayısı veya uygulanabilir bölgeden olan mesafe ile orantılı olarak azaltılır.

• Kullanma repair functions uygulanabilir olmayan bir çözümü alır ve ihlal edilen kısıtlamaların karşılanması için onu değiştirir.

• Not allowing infeasible solutions nüfusa hiç girmek için.

• Kullanın special representation or decoder functions çözümlerin uygulanabilirliğini sağlayan.

Temel Teorik Arka Plan

Bu bölümde, Şema ve NFL teoremini, yapı taşı hipotezi ile birlikte tartışacağız.

Şema Teoremi

Araştırmacılar, genetik algoritmaların çalışmasının arkasındaki matematiği anlamaya çalışıyorlar ve Holland'ın Şema Teoremi bu yönde bir adımdır. Yıl boyunca Şema Teoremi için daha genel hale getirmek için çeşitli iyileştirmeler ve öneriler yapılmıştır.

Bu bölümde, Şema Teoreminin matematiğine girmiyoruz, bunun yerine Şema Teoreminin ne olduğuna dair temel bir anlayış geliştirmeye çalışıyoruz. Bilinmesi gereken temel terminoloji aşağıdaki gibidir -

• Bir Schemabir "şablondur". Resmi olarak, alfabenin üzerinde bir dizedir = {0,1, *},

  burada * umursamıyor ve herhangi bir değer alabilir.

  Bu nedenle, * 10 * 1, 01001, 01011, 11001 veya 11011 anlamına gelebilir

  Geometrik olarak bir şema, çözüm arama uzayındaki bir hiper düzlemdir.

• Order Bir şemanın sayısı, bir gendeki belirli sabit konumların sayısıdır.

• Defining length gendeki en uzaktaki iki sabit sembol arasındaki mesafedir.

Şema teoremi, ortalamanın üzerinde uygunluğa, kısa tanımlayıcı uzunluğa ve daha düşük sıraya sahip bu şemanın, geçiş ve mutasyondan sağ çıkma olasılığının daha yüksek olduğunu belirtir.

Yapı Taşı Hipotezi

Yapı Taşları, yukarıda verilen ortalama uygunluğa sahip düşük dereceli, düşük tanımlı uzunluk şemalarıdır. Yapı taşı hipotezi, bu tür yapı taşlarının, bu tür "yapı taşlarını" art arda tanımlayarak ve yeniden birleştirerek ilerledikçe GA'ların başarısı ve GA'lardaki adaptasyonu için bir temel oluşturduğunu söylüyor.

Bedava Öğle Yemeği Yok (NFL) Teoremi

Wolpert ve Macready 1997'de "Optimizasyon İçin Ücretsiz Öğle Yemeği Teoremleri Yok" başlıklı bir makale yayınladılar. Esasen, olası tüm problemlerin uzayının ortalamasını alırsak, tekrar gözden geçirilmeyen tüm kara kutu algoritmalarının aynı performansı göstereceğini belirtir.

Bu, bir sorunu ne kadar çok anlarsak, GA'mızın daha soruna özgü hale geldiği ve daha iyi performans sağladığı anlamına gelir, ancak diğer sorunlar için düşük performans göstererek bunu telafi eder.

GA Tabanlı Makine Öğrenimi

Genetik Algoritmalar, Makine Öğreniminde de uygulama bulur. Classifier systems bir çeşit genetics-based machine learningMakine öğrenimi alanında sıklıkla kullanılan (GBML) sistemi. GBML yöntemleri, makine öğrenimi için niş bir yaklaşımdır.

GBML sistemlerinin iki kategorisi vardır -

• The Pittsburg Approach - Bu yaklaşımda, bir kromozom bir çözümü kodladı ve böylece çözümlere uygunluk atandı.

• The Michigan Approach - bir çözüm tipik olarak birçok kromozomla temsil edilir ve bu nedenle uygunluk kısmi çözümlere atanır.

Crossover, mutasyon, Lamarckian veya Darwinci gibi standart konuların GBML sistemlerinde de mevcut olduğu unutulmamalıdır.