Genetik Algoritmalar - Temel Bilgiler

Bu bölüm, GA'ları anlamak için gereken temel terminolojiyi tanıtır. Ayrıca, GA'ların genel yapısı her ikisinde de sunulmuştur.pseudo-code and graphical forms. Okuyucunun, bu bölümde tanıtılan tüm kavramları doğru bir şekilde anlaması ve bu eğitimin diğer bölümlerini de okurken bunları akılda tutması önerilir.

Temel Terminoloji

Genetik Algoritmalar üzerine bir tartışmaya başlamadan önce, bu eğitimde kullanılacak bazı temel terminolojilere aşina olmak önemlidir.

  • Population- Verilen problemin tüm olası (kodlanmış) çözümlerinin bir alt kümesidir. Bir GA'nın popülasyonu, insanlar yerine insanları temsil eden Aday Çözümlerimiz olması dışında, insan popülasyonuna benzer.

  • Chromosomes - Bir kromozom, verilen soruna böyle bir çözümdür.

  • Gene - Gen, bir kromozomun bir element pozisyonudur.

  • Allele - Belirli bir kromozom için bir genin aldığı değerdir.

  • Genotype- Genotip, hesaplama uzayındaki popülasyondur. Hesaplama alanında çözümler, bir bilgisayar sistemi kullanılarak kolayca anlaşılabilecek ve manipüle edilebilecek bir şekilde temsil edilmektedir.

  • Phenotype - Fenotip, çözümlerin gerçek dünya durumlarında temsil edildikleri şekilde temsil edildiği gerçek gerçek dünya çözüm alanındaki popülasyondur.

  • Decoding and Encoding - Basit sorunlar için phenotype and genotypeboşluklar aynıdır. Bununla birlikte, çoğu durumda, fenotip ve genotip boşlukları farklıdır. Kod çözme, bir çözümü genotipten fenotip boşluğuna dönüştürme sürecidir, kodlama ise fenotipten genotip uzayına dönüştürme işlemidir. Uygunluk değeri hesaplaması sırasında bir GA'da tekrar tekrar yapıldığından kod çözme hızlı olmalıdır.

    Örneğin, 0/1 Sırt Çantası Problemini ele alalım. Fenotip alanı, seçilecek öğelerin yalnızca öğe numaralarını içeren çözümlerden oluşur.

    Bununla birlikte, genotip uzayında, n uzunluğunda ikili bir dizi olarak temsil edilebilir (burada n, öğelerin sayısıdır). Bir0 at position x bunu temsil ediyor xthöğe seçilirken 1 tersi temsil eder. Bu, genotip ve fenotip boşluklarının farklı olduğu bir durumdur.

  • Fitness Function- Basitçe tanımlanan bir uygunluk işlevi, çözümü girdi olarak alan ve çıktı olarak çözümün uygunluğunu üreten bir işlevdir. Bazı durumlarda, uygunluk işlevi ve amaç işlevi aynı olabilirken, diğerlerinde soruna bağlı olarak farklı olabilir.

  • Genetic Operators- Bunlar yavruların genetik yapısını değiştirir. Bunlar arasında çapraz geçiş, mutasyon, seçim vb.

Basit yapı

Bir GA'nın temel yapısı aşağıdaki gibidir -

İlk popülasyonla başlıyoruz (rastgele oluşturulabilir veya başka sezgisel yöntemlerle tohumlanabilir), çiftleşme için bu popülasyondan ebeveynleri seçeriz. Yeni yaylar oluşturmak için ebeveynlere çapraz geçiş ve mutasyon operatörleri uygulayın. Ve nihayet bu yaylar, popülasyondaki mevcut bireylerin yerini alır ve süreç tekrar eder. Bu şekilde genetik algoritmalar aslında insanın evrimini bir dereceye kadar taklit etmeye çalışır.

Aşağıdaki adımların her biri, bu öğreticide daha sonra ayrı bir bölüm olarak ele alınmaktadır.

Bir GA için genelleştirilmiş bir sözde kod aşağıdaki programda açıklanmıştır -

GA()
   initialize population
   find fitness of population
   
   while (termination criteria is reached) do
      parent selection
      crossover with probability pc
      mutation with probability pm
      decode and fitness calculation
      survivor selection
      find best
   return best