Yapay Sinir Ağı - Genetik Algoritma
Doğa her zaman tüm insanlık için büyük bir ilham kaynağı olmuştur. Genetik Algoritmalar (GA), 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 Üniversitesindeki öğrencileri ve meslektaşları, özellikle David E. Goldberg tarafından geliştirildi ve o zamandan beri çeşitli optimizasyon problemlerinde yüksek derecede başarı ile denendi.
GA'larda, verilen probleme yönelik bir havuzumuz veya olası çözümlerden oluşan bir popülasyonumuz var. 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 bağlı 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 şunları içerir -
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 ç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 büyük olduğunda ve çok sayıda parametre söz konusu olduğunda kullanışlıdır.
GA sınırlamaları
Herhangi bir teknik gibi, GA'lar da birkaç sınırlamadan muzdariptir. Bunlar şunları içerir -
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, optimizasyon problemlerinin çözümünde Gas'ı ç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ıtlamıştır: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. Bununla birlikte, gerçek dünya durumlarının çoğunda, manzara olarak adlandırılan, birçok tepe ve vadiden oluşan çok karmaşık bir problemimiz var ve bu tür yöntemlerin, gösterildiği gibi yerel optimada sıkışıp kalma eğiliminden muzdarip oldukları için başarısız olmasına neden oluyor. aşağıdaki şekilde.
Hızlı Bir Çözüm Bulmak
Traveling Salesman Problem (TSP) gibi bazı zor problemler, yol bulma ve VLSI Design 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 edilebilir değildir ve bu nedenle gerekli olan "hızlı" teslim edilen "yeterince iyi" bir çözümdür.
Optimizasyon Sorunları için GA Nasıl Kullanılır?
Optimizasyonun tasarım, durum, kaynak ve sistem gibi bir şeyi olabildiğince etkili hale getirme eylemi olduğunu zaten biliyoruz. Optimizasyon süreci aşağıdaki diyagramda gösterilmektedir.
Optimizasyon Süreci için GA Mekanizmasının Aşamaları
Problemlerin optimizasyonu için kullanıldığında GA mekanizmasının aşamaları aşağıdadır.
İlk popülasyonu rastgele oluşturun.
En iyi uygunluk değerlerine sahip ilk çözümü seçin.
Mutasyon ve çaprazlama operatörlerini kullanarak seçilen çözümleri yeniden birleştirin.
Yavruları popülasyona ekleyin.
Şimdi, durdurma koşulu karşılanırsa, çözümü en iyi uygunluk değeriyle iade edin. Aksi takdirde, 2. adıma gidin.