Genetik Algoritmalar - Hızlı Kılavuz

Genetik Algoritma (GA), şu ilkelere dayanan arama tabanlı bir optimizasyon tekniğidir. Genetics and Natural Selection. Aksi takdirde çözülmesi ömür boyu sürecek olan zor problemlere optimal veya optimal yakın çözümler bulmak için sıklıkla kullanılır. Optimizasyon problemlerini çözmek için, araştırmada ve makine öğreniminde sıklıkla kullanılır.

Optimizasyona Giriş

Optimizasyon şu süreçtir: making something better. Herhangi bir işlemde, aşağıdaki şekilde gösterildiği gibi bir dizi girişimiz ve bir dizi çıkışımız vardır.

Optimizasyon, girdilerin değerlerini, "en iyi" çıktı değerlerini elde edecek şekilde bulmayı ifade eder. "En iyi" tanımı, sorundan soruna değişir, ancak matematiksel terimlerle, girdi parametrelerini değiştirerek bir veya daha fazla nesnel işlevi maksimize etmeyi veya en aza indirmeyi ifade eder.

Girişlerin alabileceği tüm olası çözümler veya değerler kümesi arama alanını oluşturur. Bu arama alanında, en uygun çözümü veren bir nokta veya bir dizi nokta bulunur. Optimizasyonun amacı, arama alanında o noktayı veya noktaları bulmaktır.

Genetik Algoritmalar nedir?

Doğa her zaman tüm insanlık için büyük bir ilham kaynağı olmuştur. Genetik Algoritmalar (GA'lar), doğal seçilim ve genetik kavramlarına dayanan arama tabanlı algoritmalardır. GA'lar olarak bilinen çok daha büyük bir hesaplama dalının bir alt kümesidir.Evolutionary Computation.

GA'lar, John Holland ve Michigan Üniversitesi'ndeki öğrencileri ve meslektaşları, özellikle de David E. Goldberg tarafından geliştirildi ve o zamandan beri çeşitli optimizasyon problemlerinde yüksek derecede başarı ile denendi.

GA'larda, bir pool or a population of possible solutionsverilen soruna. Bu çözümler daha sonra rekombinasyon ve mutasyona uğrar (doğal genetikte olduğu gibi), yeni çocuklar üretir ve süreç çeşitli nesiller boyunca tekrarlanır. Her bir bireye (veya aday çözüme) bir uygunluk değeri (hedef işlev değerine dayalı olarak) atanır ve daha fit olan kişilere çiftleşme ve daha "fit" bireyler üretme şansı verilir. Bu, Darwin'in "En Güçlü Olanın Hayatta Kalması" Teorisi ile uyumludur.

Bu şekilde, bir durdurma kriterine ulaşana kadar nesiller boyunca daha iyi bireyler veya çözümler "geliştirmeye" devam ediyoruz.

Genetik Algoritmalar, doğaları gereği yeterince rasgeleleştirilmiştir, ancak tarihsel bilgileri de kullandıkları için rasgele yerel aramadan çok daha iyi performans gösterirler (burada sadece çeşitli rasgele çözümler deniyoruz, şimdiye kadarki en iyiyi takip ediyoruz).

GA'ların Avantajları

GA'ların, onları son derece popüler kılan çeşitli avantajları vardır. Bunlar arasında -

Herhangi bir türev bilgisi gerektirmez (gerçek dünyadaki birçok problem için mevcut olmayabilir).
Geleneksel yöntemlere göre daha hızlı ve daha verimlidir.
Çok iyi paralel yeteneklere sahiptir.
Hem sürekli hem de ayrık fonksiyonları ve ayrıca çok amaçlı problemleri optimize eder.
Tek bir çözüm değil, "iyi" çözümlerin bir listesini sağlar.
Her zaman soruna bir yanıt alır ve bu zamanla düzelir.
Arama alanı çok geniş olduğunda ve ilgili çok sayıda parametre olduğunda kullanışlıdır.

GA sınırlamaları

Herhangi bir teknik gibi, GA'lar da birkaç sınırlamadan muzdariptir. Bunlar arasında -

GA'lar tüm problemler için uygun değildir, özellikle de basit olan ve türevi bilgilerin mevcut olduğu problemler.
Uygunluk değeri tekrar tekrar hesaplanır ve bu, bazı problemler için hesaplama açısından pahalı olabilir.
Stokastik olduğundan, çözümün optimalliği veya kalitesi konusunda hiçbir garanti yoktur.
Doğru bir şekilde uygulanmazsa, GA en uygun çözüme yakınlaşmayabilir.

GA - Motivasyon

Genetik Algoritmalar, "yeterince iyi" bir çözümü "yeterince hızlı" sunma yeteneğine sahiptir. Bu, genetik algoritmaları optimizasyon problemlerini çözmede kullanım için çekici kılar. GA'lara neden ihtiyaç duyulduğunun nedenleri aşağıdaki gibidir -

Zor Sorunları Çözme

Bilgisayar biliminde, çok sayıda sorun vardır. NP-Hard. Bunun esasen anlamı, en güçlü bilgi işlem sistemlerinin bile bu sorunu çözmesinin çok uzun bir süre (hatta yıllar!) Almasıdır. Böyle bir senaryoda, GA'lar, aşağıdakileri sağlamak için verimli bir araç olduğunu kanıtladıusable near-optimal solutions kısa sürede.

Gradyan Bazlı Yöntemlerin Başarısızlığı

Geleneksel analiz tabanlı yöntemler, rastgele bir noktadan başlayarak ve yokuşun tepesine ulaşana kadar eğim yönünde hareket ederek çalışır. Bu teknik etkilidir ve doğrusal regresyondaki maliyet işlevi gibi tek tepeli hedef işlevler için çok iyi çalışır. Ancak, gerçek dünya durumlarının çoğunda, birçok zirveden ve birçok vadiden oluşan, manzara olarak adlandırılan çok karmaşık bir sorunumuz var ve bu tür yöntemlerin, yerel optimada sıkışıp kalma eğiliminden muzdarip oldukları için başarısız olmasına neden oluyor. aşağıdaki şekilde gösterildiği gibi.

Hızlı Bir Çözüm Bulmak

Seyahat Eden Satış Elemanı Problemi (TSP) gibi bazı zor problemler, yol bulma ve VLSI Tasarımı gibi gerçek dünya uygulamalarına sahiptir. Şimdi, GPS Navigasyon sisteminizi kullandığınızı ve kaynaktan hedefe "en uygun" yolu hesaplamanın birkaç dakika (hatta birkaç saat) aldığını hayal edin. Bu tür gerçek dünya uygulamalarında gecikme kabul edilemez ve bu nedenle gerekli olan "hızlı" teslim edilen "yeterince iyi" bir çözümdür.

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 x^thöğ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

Genetik bir algoritma uygularken alınacak en önemli kararlardan biri, çözümlerimizi temsil etmek için kullanacağımız temsile karar vermektir. Uygun olmayan sunumun GA'nın düşük performansına yol açabileceği gözlenmiştir.

Bu nedenle, uygun bir temsil seçimi, fenotip ve genotip boşlukları arasındaki eşleşmelerin uygun bir tanımına sahip olmak, bir GA'nın başarısı için çok önemlidir.

Bu bölümde, genetik algoritmalar için en sık kullanılan temsillerden bazılarını sunuyoruz. Bununla birlikte, temsil oldukça soruna özgüdür ve okuyucu, burada bahsedilen başka bir temsilin veya temsillerin bir karışımının problemine daha iyi uyabileceğini görebilir.

İkili Temsil

Bu, GA'larda en basit ve en yaygın kullanılan temsillerden biridir. Bu tür bir temsilde, genotip bit dizilerinden oluşur.

Çözüm uzayının Boole karar değişkenlerinden oluştuğu bazı problemler için - evet ya da hayır, ikili gösterim doğaldır. Örneğin 0/1 Sırt Çantası Problemini ele alalım. Eğer n öğe varsa, bir çözümü n öğeden oluşan bir ikili dizi ile temsil edebiliriz, burada ^x'inci öğe x öğesinin seçilip seçilmediğini (1) söyler (0).

Diğer problemler için, özellikle sayılarla ilgili olanlar için, sayıları ikili gösterimiyle temsil edebiliriz. Bu tür kodlamayla ilgili sorun, farklı bitlerin farklı anlamlara sahip olmaları ve dolayısıyla mutasyon ve çaprazlama operatörlerinin istenmeyen sonuçlara sahip olabilmesidir. Bu, kullanılarak bir dereceye kadar çözülebilirGray Coding, çünkü bir bitteki değişimin çözüm üzerinde büyük bir etkisi yoktur.

Gerçek Değerli Temsil

Genleri ayrık değişkenler yerine sürekli değişkenler kullanarak tanımlamak istediğimiz problemler için, gerçek değerli temsil en doğal olanıdır. Ancak bu gerçek değerli veya kayan noktalı sayıların kesinliği bilgisayarla sınırlıdır.

Tamsayı Gösterimi

Ayrık değerli genler için, çözüm alanını her zaman ikili 'evet' veya 'hayır' ile sınırlayamayız. Örneğin, dört mesafeyi - Kuzey, Güney, Doğu ve Batı - kodlamak istiyorsak, bunları şu şekilde kodlayabiliriz:{0,1,2,3}. Bu tür durumlarda, tamsayı gösterimi arzu edilir.

Permütasyon Temsili

Birçok problemde çözüm, bir unsurlar sırası ile temsil edilir. Bu gibi durumlarda permütasyon temsili en uygun olanıdır.

Bu temsilin klasik bir örneği, seyyar satıcı problemidir (TSP). Bunda, satıcı tüm şehirleri gezmeli, her şehri tam olarak bir kez ziyaret etmeli ve başlangıç şehrine geri dönmelidir. Turun toplam mesafesi en aza indirilmelidir. Bu TSP'nin çözümü doğal olarak tüm şehirlerin bir sıralaması veya permütasyonudur ve bu nedenle bir permütasyon temsilinin kullanılması bu problem için mantıklıdır.

Nüfus, mevcut nesildeki çözümlerin bir alt kümesidir. Aynı zamanda bir dizi kromozom olarak da tanımlanabilir. GA popülasyonuyla uğraşırken akılda tutulması gereken birkaç nokta vardır -

Nüfusun çeşitliliği korunmalıdır, aksi takdirde erken yakınsamaya yol açabilir.
Bir GA'nın yavaşlamasına neden olabileceğinden, popülasyon boyutu çok büyük tutulmamalıdır, ancak daha küçük bir popülasyon iyi bir çiftleşme havuzu için yeterli olmayabilir. Bu nedenle, optimum popülasyon büyüklüğüne deneme yanılma yoluyla karar verilmesi gerekir.

Popülasyon genellikle iki boyutlu bir dizi olarak tanımlanır - size population, size x, chromosome size.

Nüfus Başlatma

Bir GA'da bir popülasyonu başlatmak için iki temel yöntem vardır. Onlar -

Random Initialization - İlk popülasyonu tamamen rastgele çözümlerle doldurun.
Heuristic initialization - Sorun için bilinen bir buluşsal yöntem kullanarak ilk popülasyonu doldurun.

Popülasyonun benzer çözümlere ve çok az çeşitliliğe sahip olmasına neden olabileceğinden, popülasyonun tamamının bir buluşsal yöntem kullanılarak başlatılmaması gerektiği gözlemlenmiştir. Rastgele çözümlerin, popülasyonu en iyiye götüren çözümler olduğu deneysel olarak gözlemlenmiştir. Bu nedenle, sezgisel başlatma ile, popülasyonun tamamını sezgisel tabanlı çözümlerle doldurmak yerine, geri kalanını rastgele çözümlerle doldurarak, yalnızca birkaç iyi çözümle tohumlandırıyoruz.

Bazı durumlarda sezgisel başlatmanın yalnızca popülasyonun başlangıçtaki uygunluğunu etkilediği, ancak sonuçta iyimserliğe yol açan çözümlerin çeşitliliği olduğu da gözlemlenmiştir.

Nüfus Modelleri

Yaygın olarak kullanılan iki popülasyon modeli vardır -

Denge durumu

Kararlı durum GA'da, her yinelemede bir veya iki yay üretiyoruz ve bunlar popülasyondaki bir veya iki kişinin yerini alıyor. Kararlı durum GA, aynı zamandaIncremental GA.

Nesil

Kuşak modelinde, n popülasyon boyutu olduğu ve tüm popülasyonun yinelemenin sonunda yenisiyle değiştirildiği 'n' yay dışı kaynaklar oluşturuyoruz.

Basitçe tanımlanan uygunluk işlevi, bir candidate solution to the problem as input and produces as output dikkate alınan soruna göre çözümün ne kadar "iyi" olduğu.

Uygunluk değerinin hesaplanması bir GA'da tekrar tekrar yapılır ve bu nedenle yeterince hızlı olmalıdır. Uygunluk değerinin yavaş hesaplanması, bir GA'yı olumsuz yönde etkileyebilir ve son derece yavaş hale getirebilir.

Çoğu durumda, uygunluk işlevi ve amaç işlevi, amaç verilen amaç işlevi maksimize etmek veya en aza indirmek olduğu gibi aynıdır. Ancak, birden çok hedef ve kısıtlamaya sahip daha karmaşık sorunlar için, birAlgorithm Designer farklı bir uygunluk işlevine sahip olmayı seçebilir.

Bir uygunluk işlevi aşağıdaki özelliklere sahip olmalıdır -

Uygunluk işlevi hesaplamak için yeterince hızlı olmalıdır.
Belirli bir çözümün ne kadar uygun olduğunu veya bireylerin verilen çözümden ne kadar uygun olduğunu nicel olarak ölçmelidir.

Bazı durumlarda, eldeki problemin doğasında olan karmaşıklıklar nedeniyle uygunluk işlevinin doğrudan hesaplanması mümkün olmayabilir. Bu gibi durumlarda, ihtiyaçlarımıza uyacak şekilde uygunluk tahmini yaparız.

Aşağıdaki resim, 0/1 Sırt Çantasının bir çözümü için uygunluk hesaplamasını göstermektedir. Bu, sırt çantası dolana kadar öğeleri soldan sağa tarayan, toplanan öğelerin (1 olan) kâr değerlerini toplayan basit bir uygunluk işlevidir.

Ebeveyn Seçimi, gelecek nesil için yaylar yaratmak için çiftleşen ve yeniden birleşen ebeveynleri seçme sürecidir. Ebeveyn seçimi, iyi ebeveynler bireyleri daha iyi ve daha uygun çözümlere yönlendirdiği için GA'nın yakınsama oranı için çok önemlidir.

Bununla birlikte, son derece uygun bir çözümün birkaç kuşakta tüm nüfusu ele geçirmesini önlemek için özen gösterilmelidir çünkü bu, çözüm alanında çözümlerin birbirine yakın olmasına ve dolayısıyla çeşitlilik kaybına neden olur. Maintaining good diversitybir GA'nın başarısı için popülasyonda son derece önemlidir. Nüfusun tamamının son derece uygun bir çözüm tarafından ele geçirilmesi olarak bilinir.premature convergence ve bir GA'da istenmeyen bir durumdur.

Fitness Orantılı Seçim

Uygunluk Orantılı Seçim, ebeveyn seçiminin en popüler yollarından biridir. Bunda her birey, uygunluğuyla orantılı bir olasılıkla ebeveyn olabilir. Bu nedenle, uygun bireylerin çiftleşme ve özelliklerini bir sonraki nesle yayma şansı daha yüksektir. Bu nedenle, böyle bir seçim stratejisi, popülasyondaki daha uygun bireylere bir seçim baskısı uygular ve zamanla daha iyi bireyler geliştirir.

Dairesel bir tekerlek düşünün. Tekerlek ayrılmıştırn pies, burada n, popülasyondaki birey sayısıdır. Her birey, çemberin uygunluk değeriyle orantılı bir bölümünü alır.

Uygun orantılı seçimin iki uygulaması mümkündür -

Rulet Çarkı Seçimi

Bir rulet çarkı seçiminde, dairesel çark daha önce anlatıldığı gibi bölünür. Tekerlek çevresinde gösterildiği gibi sabit bir nokta seçilir ve tekerlek döndürülür. Sabit noktanın önüne gelen çark bölgesi ebeveyn olarak seçilir. İkinci ebeveyn için aynı süreç tekrarlanır.

Daha uygun olan bir bireyin, tekerlek üzerinde daha büyük bir pastaya sahip olduğu ve bu nedenle, tekerlek döndürüldüğünde sabit noktanın önüne inme şansının daha yüksek olduğu açıktır. Bu nedenle, bir bireyi seçme olasılığı doğrudan onun uygunluğuna bağlıdır.

Uygulama bilge, aşağıdaki adımları kullanıyoruz -

S = bir inceliğin toplamını hesaplayın.
0 ile S arasında rastgele bir sayı oluşturun.
Nüfusun en tepesinden başlayarak, P <S olana kadar kısmi toplam P'ye incelikleri eklemeye devam edin.
P'nin S'yi aştığı birey, seçilen bireydir.

Stokastik Evrensel Örnekleme (SUS)

Stokastik Evrensel Örnekleme, Rulet çarkı seçimine oldukça benzer, ancak tek bir sabit noktaya sahip olmak yerine, aşağıdaki resimde gösterildiği gibi birden fazla sabit noktaya sahibiz. Bu nedenle, tüm ebeveynler çarkın sadece bir dönüşünde seçilir. Ayrıca, böyle bir kurulum, son derece uygun bireyleri en az bir kez seçilmeye teşvik eder.

Uygunluk orantılı seçim yöntemlerinin, uygunluğun negatif bir değer alabileceği durumlarda işe yaramadığına dikkat edilmelidir.

Turnuva Seçimi

K-Way turnuva seçiminde, popülasyondan rastgele K kişiyi seçiyoruz ve ebeveyn olmak için bunlardan en iyisini seçiyoruz. Aynı işlem bir sonraki ebeveyni seçmek için tekrarlanır. Turnuva Seçimi, negatif fitness değerleriyle bile çalışabildiği için literatürde son derece popülerdir.

Sıra Seçimi

Derece Seçimi ayrıca negatif kondisyon değerleriyle çalışır ve çoğunlukla popülasyondaki bireylerin çok yakın kondisyon değerlerine sahip olduğu durumlarda kullanılır (bu genellikle çalışmanın sonunda olur). Bu, her bireyin aşağıdaki resimde gösterildiği gibi (uygun orantılı seçim durumunda olduğu gibi) pastadan neredeyse eşit bir paya sahip olmasına yol açar ve bu nedenle, her bireyin birbirine göre ne kadar uygun olursa olsun, yaklaşık olarak aynı seçilme olasılığı vardır. ebeveyn. Bu da daha uygun bireylere yönelik seçim baskısında bir kayba yol açarak, GA'nın bu gibi durumlarda kötü ebeveyn seçimleri yapmasına neden olur.

Bunda, bir ebeveyn seçerken bir uygunluk değeri kavramını kaldırıyoruz. Bununla birlikte, popülasyondaki her birey uygunluğuna göre sıralanır. Ebeveynlerin seçimi kondisyona değil, her bir bireyin derecesine bağlıdır. Üst sıradaki kişiler, alt sıradaki kişilere göre daha çok tercih edilir.

Kromozom	Fitness Değeri	Sıra
Bir	8.1	1
B	8.0	4
C	8.05	2
D	7,95	6
E	8.02	3
F	7,99	5

Rastgele Seçim

Bu stratejide, mevcut popülasyondan rastgele ebeveynler seçiyoruz. Zinde bireylere yönelik seçim baskısı yoktur ve bu nedenle bu stratejiden genellikle kaçınılır.

Bu bölümde, bir Crossover Operatörünün diğer modülleriyle birlikte ne olduğunu, kullanımlarını ve faydalarını tartışacağız.

Crossover'a Giriş

Geçiş operatörü, üreme ve biyolojik geçişe benzer. Bunda birden fazla ebeveyn seçilir ve ebeveynlerin genetik materyali kullanılarak bir veya daha fazla yay üretilir. Crossover genellikle yüksek olasılıkla bir GA'da uygulanır -p_c .

Crossover Operatörleri

Bu bölümde en popüler olarak kullanılan geçiş operatörlerinden bazılarını tartışacağız. Bu geçiş operatörlerinin çok genel olduğu ve GA Tasarımcısının probleme özel bir geçiş operatörü uygulamayı da seçebileceği unutulmamalıdır.

Tek Noktalı Geçiş

Bu tek noktalı geçişte, rastgele bir geçiş noktası seçilir ve yeni yaylar elde etmek için iki üst öğesinin kuyrukları değiştirilir.

Çok Noktalı Geçiş

Çok noktalı geçiş, yeni yaylar elde etmek için değişen bölümlerin değiştirildiği tek noktalı geçişin bir genellemesidir.

Üniforma Crossover

Tek tip bir çaprazlamada, kromozomu parçalara ayırmayız, bunun yerine her geni ayrı ayrı tedavi ederiz. Bunda, aslında her kromozom için bir bozuk para atarak, baharın çıkışına dahil edilip edilmeyeceğine karar veriyoruz. Ayrıca, çocukta o ebeveynden daha fazla genetik materyal olması için madeni parayı bir ebeveyne yönlendirebiliriz.

Tam Aritmetik Rekombinasyon

Bu, genellikle tamsayı gösterimleri için kullanılır ve aşağıdaki formülleri kullanarak iki üst öğenin ağırlıklı ortalamasını alarak çalışır -

Çocuk1 = α.x + (1-α) .y
Çocuk2 = α.x + (1-α) .y

Açıktır ki, eğer α = 0.5 ise, o zaman her iki çocuk da aşağıdaki görüntüde gösterildiği gibi aynı olacaktır.

Davis'in Sipariş Crossover'ı (OX1)

OX1, yaylara göreceli sıralama hakkında bilgi iletmek amacıyla permütasyon bazlı geçitler için kullanılır. Aşağıdaki gibi çalışır -

Ebeveynde iki rastgele geçiş noktası oluşturun ve bunlar arasındaki segmenti ilk ebeveynden ilk çocuğa kopyalayın.
Şimdi, ikinci ebeveyndeki ikinci geçiş noktasından başlayarak, kalan kullanılmayan sayıları ikinci ebeveynden birinci çocuğa, listeyi sararak kopyalayın.
Ebeveynin rolü tersine çevrilmiş ikinci çocuk için tekrarlayın.

Kısmen Haritalanmış Geçit (PMX), Sipariş tabanlı geçiş (OX2), Karıştırma Geçişi, Halka Geçişi, vb. Gibi birçok başka geçiş var.

Mutasyona Giriş

Basit bir ifadeyle, mutasyon, yeni bir çözüm elde etmek için kromozomda küçük bir rastgele ince ayar olarak tanımlanabilir. Genetik popülasyondaki çeşitliliği sürdürmek ve tanıtmak için kullanılır ve genellikle düşük bir olasılıkla uygulanır -p_m. Olasılık çok yüksekse, GA rastgele aramaya indirgenir.

Mutasyon, GA'nın arama uzayının "keşfi" ile ilgili olan kısmıdır. Geçiş olmadığı halde mutasyonun GA'nın yakınsaması için gerekli olduğu gözlenmiştir.

Mutasyon Operatörleri

Bu bölümde, en sık kullanılan mutasyon operatörlerinden bazılarını açıklıyoruz. Çaprazlama operatörleri gibi, bu ayrıntılı bir liste değildir ve GA tasarımcısı bu yaklaşımların bir kombinasyonunu veya probleme özgü bir mutasyon operatörünü daha yararlı bulabilir.

Bit Çevirme Mutasyonu

Bu bit çevirme mutasyonunda, bir veya daha fazla rastgele bit seçip çeviriyoruz. Bu, ikili kodlanmış GA'lar için kullanılır.

Rastgele Sıfırlama

Rastgele Sıfırlama, tamsayı gösterimi için bit çevirmenin bir uzantısıdır. Bunda, izin verilebilir değerler kümesinden rastgele bir değer, rastgele seçilen bir gene atanır.

Değişim Mutasyonu

Takas mutasyonunda, kromozom üzerinde rastgele iki konum seçer ve değerleri değiştiririz. Bu, permütasyon tabanlı kodlamalarda yaygındır.

Scramble Mutation

Karışım mutasyonu, permütasyon temsillerinde de popülerdir. Bunda, tüm kromozomdan, genlerin bir alt kümesi seçilir ve değerleri rastgele karıştırılır veya karıştırılır.

İnversiyon Mutasyonu

Tersine çevirme mutasyonunda, karıştırma mutasyonunda olduğu gibi bir gen alt kümesi seçeriz, ancak alt kümeyi karıştırmak yerine, yalnızca alt kümedeki tüm dizeyi tersine çeviririz.

Survivor Seçim Politikası, hangi bireylerin atılacağını ve hangilerinin gelecek nesilde tutulacağını belirler. Zinde olan bireylerin popülasyondan atılmamasını sağlaması ve aynı zamanda popülasyonda çeşitliliğin sürdürülmesi gerektiği için çok önemlidir.

Bazı GA'lar kullanır Elitism. Basit bir ifadeyle, nüfusun şu andaki en uygun üyesinin daima bir sonraki nesle yayıldığı anlamına gelir. Bu nedenle, hiçbir koşulda mevcut nüfusun en uygun üyesi değiştirilemez.

En kolay politika, rastgele üyeleri popülasyondan atmaktır, ancak böyle bir yaklaşımda sıklıkla yakınsama sorunları vardır, bu nedenle aşağıdaki stratejiler yaygın olarak kullanılmaktadır.

Yaş Bazında Seçim

Yaşa Dayalı Seçimde, bir uygunluk kavramına sahip değiliz. Her bireyin popülasyonda çoğalmasına izin verilen sınırlı bir nesil için izin verildiği, daha sonra uygunluğu ne kadar iyi olursa olsun popülasyondan atıldığı öncülüne dayanmaktadır.

Örneğin, aşağıdaki örnekte yaş, bireyin nüfusta bulunduğu nesillerin sayısıdır. Nüfusun en yaşlı üyeleri, yani P4 ve P7, popülasyondan atılır ve geri kalan üyelerin yaşları bir artar.

Kondisyona Dayalı Seçim

Bu uygunluğa dayalı seçimde, çocuklar popülasyondaki en az uygun bireylerin yerini alma eğilimindedir. En az uygun olan kişilerin seçimi, daha önce açıklanan seçim politikalarının herhangi birinin bir varyasyonu kullanılarak yapılabilir - turnuva seçimi, uygunluk orantılı seçim, vb.

Örneğin, aşağıdaki resimde çocuklar, popülasyondaki en az uyum sağlayan bireyler P1 ve P10'un yerini almaktadır. P1 ve P9 aynı uygunluk değerine sahip olduğundan, popülasyondan hangi bireyin çıkarılması kararının keyfi olduğuna dikkat edilmelidir.

Genetik Algoritmanın sonlandırma koşulu, bir GA çalışmasının ne zaman biteceğini belirlemede önemlidir. Başlangıçta, GA'nın birkaç yinelemede bir gelen daha iyi çözümlerle çok hızlı ilerlediği gözlemlenmiştir, ancak bu, iyileştirmelerin çok küçük olduğu sonraki aşamalarda doyma eğilimindedir. Genellikle, çalışmanın sonunda çözümümüzün en iyiye yakın olmasını sağlayacak bir sonlandırma koşulu isteriz.

Genellikle, aşağıdaki sonlandırma koşullarından birini uygularız -

X iterasyonları için popülasyonda herhangi bir gelişme olmadığında.
Mutlak bir nesil sayısına ulaştığımızda.
Amaç fonksiyonu değeri önceden tanımlanmış belirli bir değere ulaştığında.

Örneğin, bir genetik algoritmada, popülasyonda hiçbir iyileşme olmayan nesillerin kaydını tutan bir sayaç tutuyoruz. Başlangıçta bu sayacı sıfıra ayarladık. Nüfustaki bireylerden daha iyi olan yaylar üretmediğimiz her seferinde, sayacı artırıyoruz.

Bununla birlikte, yaylardan herhangi birinin uygunluğu daha iyiyse, sayacı sıfıra sıfırlarız. Sayaç önceden belirlenmiş bir değere ulaştığında algoritma sona erer.

Bir GA'nın diğer parametreleri gibi, sonlandırma koşulu da son derece soruna özgüdür ve GA tasarımcısı, kendi sorununa en uygun olanı görmek için çeşitli seçenekleri denemelidir.

Şimdiye kadar bu eğitimde tartıştığımız her şey, Darwin'in evrim modeline karşılık geliyor - doğal seçilim ve rekombinasyon ve mutasyon yoluyla genetik çeşitlilik. Doğası gereği, yalnızca bireyin genotipinde yer alan bilgiler bir sonraki nesle aktarılabilir. Şimdiye kadar öğreticide takip ettiğimiz yaklaşım budur.

Bununla birlikte, diğer ömür boyu adaptasyon modelleri - Lamarckian Model ve Baldwinian Modelayrıca var. Hangi modelin en iyisi olduğuna dikkat edilmelidir, tartışmaya açıktır ve araştırmacılar tarafından elde edilen sonuçlar, yaşam boyu adaptasyon seçiminin oldukça probleme özgü olduğunu göstermektedir.

Genellikle, bir GA'yı Memetik Algoritmalar'daki gibi yerel arama ile melezleştiririz. Bu gibi durumlarda, yerel aramadan sonra oluşturulan bireylerle ne yapılacağına karar vermek için Lamarckian veya Baldwinian Modeli ile gitmek seçilebilir.

Lamarkçı Modeli

Lamarckian Model esasen bir bireyin yaşamı boyunca edindiği özelliklerin yavrularına aktarılabileceğini söyler. Fransız biyolog Jean-Baptiste Lamarck'ın adını almıştır.

Doğal biyoloji Lamarkizmi tamamen göz ardı etse de, hepimiz sadece genotipteki bilginin iletilebileceğini biliyoruz. Bununla birlikte, hesaplama bakış açısından, Lamarckian modelini benimsemenin bazı problemler için iyi sonuçlar verdiği gösterilmiştir.

Lamarckian modelinde, yerel bir arama operatörü mahalleyi inceler (yeni özellikler edinir) ve daha iyi bir kromozom bulunursa bu, yavru olur.

Baldwinian Modeli

Baldwinian modeli, James Mark Baldwin (1896) adını taşıyan bir ara fikirdir. Baldwin modelinde, kromozomlar faydalı davranışları öğrenme eğilimini kodlayabilir. Bu, Lamarckçı modelden farklı olarak, edinilen özellikleri bir sonraki nesle aktarmadığımız ve Darwin Modelinde olduğu gibi edinilen özellikleri de tamamen görmezden gelmediğimiz anlamına gelir.

Baldwin Modeli, bu iki uç noktanın ortasındadır, burada bir bireyin belirli özellikleri edinme eğilimi, özelliklerin kendisinden çok kodlanmıştır.

Bu Baldwinian Modelinde, yerel bir arama operatörü mahalleyi inceler (yeni özellikler edinerek) ve daha iyi bir kromozom bulunursa, yalnızca kromozoma gelişmiş uygunluğu atar ve kromozomun kendisini değiştirmez. Uygunluktaki değişiklik, doğrudan gelecek nesillere aktarılmasa bile, kromozomların "özelliği edinme" yeteneğini ifade eder.

GA'lar doğaları gereği çok geneldir ve bunları herhangi bir optimizasyon problemine uygulamak iyi sonuçlar vermez. Bu bölümde, bir GA tasarımcısına veya GA uygulayıcısına çalışmalarında yardımcı olacak ve yardımcı olacak birkaç noktayı açıklıyoruz.

Probleme özgü alan bilgisini tanıtın

GA'ya daha fazla probleme özgü alan bilgisini dahil ettiğimiz; elde ettiğimiz daha iyi objektif değerler. Soruna özel bilgi eklemek, soruna özel çaprazlama veya mutasyon operatörleri, özel temsiller vb. Kullanılarak yapılabilir.

Aşağıdaki görüntü Michalewicz'in (1990) EA görüşünü göstermektedir -

Kalabalığı Azaltın

Kalabalık, son derece uygun bir kromozom çok fazla çoğaldığında ve birkaç nesil içinde tüm popülasyon benzer uygunluğa sahip benzer çözümlerle dolduğunda meydana gelir. Bu, bir GA'nın başarısını sağlamak için çok önemli bir unsur olan çeşitliliği azaltır. Kalabalığı sınırlamanın birçok yolu vardır. Bazıları -

Mutation çeşitliliği tanıtmak için.
Geçiş yapılıyor rank selection ve tournament selection benzer uygunluğa sahip bireyler için uygunluk orantılı seçimden daha fazla seçim baskısına sahip olanlar.
Fitness Sharing - Bunda, popülasyon zaten benzer bireyler içeriyorsa, bir bireyin zindeliği azalır.

Randomizasyon Yardımcı Olur!

En iyi çözümlerin, popülasyona çeşitlilik kazandırdıklarından rastgele kromozomlar tarafından yönlendirildiği deneysel olarak gözlemlenmiştir. GA uygulayıcısı, en iyi sonuçlar için popülasyonda yeterli miktarda randomizasyon ve çeşitlilik bulundurmaya dikkat etmelidir.

GA'yı Yerel Arama ile melezleyin

Yerel arama, daha iyi objektif değerler aramak için belirli bir çözümün çevresindeki çözümleri kontrol etmeyi ifade eder.

GA'yı yerel arama ile melezlemek bazen yararlı olabilir. Aşağıdaki resim, yerel aramanın bir GA'da tanıtılabileceği çeşitli yerleri göstermektedir.

Parametrelerin ve tekniklerin çeşitliliği

Genetik algoritmalarda, “herkese uyan tek bir boyut” veya tüm problemler için çalışan sihirli bir formül yoktur. İlk GA hazır olduktan sonra bile, belirli probleme uygun olanları bulmak için popülasyon boyutu, mutasyon ve geçiş olasılığı gibi parametrelerle oynamak çok zaman ve çaba gerektirir.

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 görüntüde 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 verebilir. 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 onu değiştirerek ihlal edilen kısıtlamaların yerine getirilmesini sağlar.
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 çapraz geçiş ve mutasyona dayanma 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ı bloklarını" art arda tanımlayıp 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.

Genetik Algoritmalar öncelikle çeşitli türlerdeki optimizasyon problemlerinde kullanılır, ancak diğer uygulama alanlarında da sıklıkla kullanılırlar.

Bu bölümde Genetik Algoritmaların sıklıkla kullanıldığı alanlardan bazılarını listeliyoruz. Bunlar -

Optimization- Genetik Algoritmalar, en yaygın olarak, belirli bir kısıtlama kümesi altında belirli bir amaç fonksiyon değerini maksimize etmemiz veya en aza indirmemiz gereken optimizasyon problemlerinde kullanılır. Optimizasyon problemlerini çözme yaklaşımı eğitim boyunca vurgulanmıştır.
Economics - GA'lar ayrıca örümcek ağı modeli, oyun teorisi denge çözünürlüğü, varlık fiyatlandırması vb. Gibi çeşitli ekonomik modelleri karakterize etmek için kullanılır.
Neural Networks - GA'lar ayrıca sinir ağlarını, özellikle tekrarlayan sinir ağlarını eğitmek için kullanılır.
Parallelization - GA'lar ayrıca çok iyi paralel yeteneklere sahiptir ve belirli problemleri çözmede çok etkili araçlar olduklarını ve ayrıca araştırma için iyi bir alan sağladıklarını kanıtlamaktadır.
Image Processing - GA'lar, çeşitli dijital görüntü işleme (DIP) görevlerinin yanı sıra yoğun piksel eşleştirmesi için kullanılır.
Vehicle routing problems - Birden çok esnek zaman aralığı, birden çok depo ve heterojen bir filo ile.
Scheduling applications - GA'lar, özellikle zaman çizelgesi problemi olmak üzere çeşitli programlama problemlerini çözmek için kullanılır.
Machine Learning - daha önce tartışıldığı gibi, genetik tabanlı makine öğrenimi (GBML), makine öğreniminde niş bir alandır.
Robot Trajectory Generation - GA'lar, bir robot kolunun bir noktadan diğerine hareket ederek izlediği yolu planlamak için kullanılmıştır.
Parametric Design of Aircraft - GA'lar, parametreleri değiştirerek ve daha iyi çözümler geliştirerek uçakları tasarlamak için kullanılmıştır.
DNA Analysis - Örnekle ilgili spektrometrik veriler kullanılarak DNA yapısını belirlemek için GA'lar kullanılmıştır.
Multimodal Optimization - GA'lar, birden fazla optimum çözüm bulmamız gereken çok modlu optimizasyon için açıkça çok iyi yaklaşımlardır.
Traveling salesman problem and its applications - GA'lar, iyi bilinen bir kombinatoryal problem olan TSP'yi, yeni çaprazlama ve paketleme stratejileri kullanarak çözmek için kullanılmıştır.

Aşağıdaki kitaplara, okuyucunun Genetik Algoritmalar ve genel olarak Evrimsel Hesaplama hakkındaki bilgilerini daha da geliştirmek için başvurulabilir:

Arama, Optimizasyon ve Makine Öğreniminde Genetik Algoritmalar David E. Goldberg.
Genetik Algoritmalar + Veri Yapıları = Evrimsel Programlar Zbigniew Michalewicz.
Pratik Genetik Algoritmalar Randy L. Haupt ve Sue Ellen Haupt.
Evrimsel Algoritmalar kullanarak Çok Amaçlı Optimizasyon Kalyanmoy Deb.