Genetik algoritma, 'Darwin'in Doğadaki evrim teorisinden esinlenen uyarlanabilir bir sezgisel arama algoritmasıdır. .' Makine öğreniminde optimizasyon problemlerini çözmek için kullanılır. Çözülmesi uzun zaman alacak karmaşık problemlerin çözümüne yardımcı olduğu için önemli algoritmalardan biridir.
Java'da dizeye tam sayı
Genetik Algoritmalar farklı gerçek dünya uygulamalarında yaygın olarak kullanılmaktadır; örneğin, Elektronik devreler tasarlama, kod kırma, görüntü işleme ve yapay yaratıcılık.
Bu konu başlığımızda Genetik algoritmada kullanılan temel terminolojiler, nasıl çalıştığı, genetik algoritmanın avantajları ve sınırlamaları vb. dahil olmak üzere Genetik algoritmayı detaylı olarak açıklayacağız.
Genetik Algoritma Nedir?
Genetik algoritmayı anlamadan önce, bu algoritmayı daha iyi anlayabilmek için öncelikle temel terminolojileri anlayalım:
Popülasyondaki her varlığın uygunluğu hesaplandıktan sonra, popülasyondaki hangi bireylerin çoğalıp gelecek nesli oluşturacak tohumu üreteceğini belirlemek için bir seçim süreci kullanılır.
Mevcut seçim stili türleri
Artık genetik algoritmayı optimizasyon problemlerini çözmeye yönelik sezgisel arama algoritması olarak tanımlayabiliriz. Hesaplamada kullanılan evrimsel algoritmaların bir alt kümesidir. Genetik algoritma, optimizasyon problemlerini çözmek için genetik ve doğal seçilim kavramlarını kullanır.
Genetik Algoritma Nasıl Çalışır?
Genetik algoritma, yüksek kaliteli çözümler üretmek için evrimsel nesil döngüsü üzerinde çalışır. Bu algoritmalar, gelişmiş bir uyum çözümü sağlamak için popülasyonu geliştiren veya değiştiren farklı işlemleri kullanır.
Aşağıda verilen karmaşık optimizasyon problemlerini çözmek temel olarak beş aşamadan oluşur:
1. Başlatma
Genetik algoritmanın süreci, popülasyon adı verilen bireyler kümesinin oluşturulmasıyla başlar. Burada her birey verilen problemin çözümüdür. Bir birey, Genler adı verilen bir dizi parametreyi içerir veya bu parametrelerle karakterize edilir. Genler bir dizi halinde birleştirilir ve kromozomlar üretilir; bu da sorunun çözümüdür. Başlatma için en popüler tekniklerden biri rastgele ikili dizilerin kullanılmasıdır.
2. Kondisyon Ödevi
Fitness fonksiyonu bir bireyin ne kadar formda olduğunu belirlemek için kullanılır? Bir bireyin diğer bireylerle rekabet edebilme yeteneği anlamına gelir. Her yinelemede bireyler uygunluk fonksiyonlarına göre değerlendirilir. Uygunluk fonksiyonu her bireye bir uygunluk puanı sağlar. Bu puan ayrıca üreme için seçilme olasılığını da belirler. Uygunluk puanı ne kadar yüksek olursa üreme için seçilme şansı da o kadar artar.
Java ana yöntemi
3. Seçim
Seçim aşaması, yavruların çoğaltılması için bireylerin seçimini içerir. Seçilen tüm bireyler daha sonra üremeyi artırmak için ikili bir çift halinde düzenlenir. Daha sonra bu bireyler genlerini bir sonraki nesle aktarırlar.
Üç tür Seçim yöntemi mevcuttur:
- Rulet çarkı seçimi
- Turnuva seçimi
- Sıralamaya dayalı seçim
4. Üreme
Seçme işleminden sonra üreme adımında çocuğun yaratılması gerçekleşir. Bu adımda genetik algoritma ana popülasyona uygulanan iki varyasyon operatörünü kullanır. Çoğaltma aşamasında yer alan iki operatör aşağıda verilmiştir:
- Tek nokta geçişi
- İki noktalı geçiş
- Görünüm geçişi
- Kalıtsal Algoritmalar geçişi
Ebeveynlerin genleri çapraz geçiş noktasına ulaşılıncaya kadar kendi aralarında değiştirilir. Bu yeni oluşan yavrular popülasyona eklenir. Bu işleme çaprazlama da denir. Mevcut çapraz stil türleri:
Mutasyon operatörü, popülasyondaki çeşitliliği korumak için yavrulara (yeni çocuk) rastgele genler ekler. Kromozomlardaki bazı bitlerin çevrilmesiyle yapılabilir.
Mutasyon, erken yakınsama sorununu çözmeye yardımcı olur ve çeşitliliği artırır. Aşağıdaki resim mutasyon sürecini göstermektedir:
Mevcut mutasyon stillerinin türleri,
5. Fesih
Yeniden üretim aşamasından sonra sonlandırma için bir temel olarak bir durdurma kriteri uygulanır. Algoritma eşik uygunluk çözümüne ulaşıldığında sonlandırılır. Nihai çözümü popülasyondaki en iyi çözüm olarak tanımlayacaktır.
Basit Bir Genetik Algoritmanın Genel İş Akışı
Genetik Algoritmanın Avantajları
- Genetik algoritmaların paralel yetenekleri en iyisidir.
- Ayrık fonksiyonlar, çok amaçlı problemler ve sürekli fonksiyonlar gibi çeşitli problemlerin optimize edilmesine yardımcı olur.
- Zamanla düzelen bir soruna çözüm sağlar.
- Genetik algoritmanın türev bilgiye ihtiyacı yoktur.
Genetik Algoritmaların Sınırlamaları
- Genetik algoritmalar basit problemlerin çözümünde etkili algoritmalar değildir.
- Bir soruna nihai çözümün kalitesini garanti etmez.
- Uygunluk değerlerinin tekrar tekrar hesaplanması bazı hesaplama zorlukları yaratabilir.
Genetik Algoritmalar ile Geleneksel Algoritmalar Arasındaki Fark
- Arama uzayı problemin olası tüm çözümlerinin kümesidir. Geleneksel algoritmada yalnızca bir çözüm kümesi korunurken, genetik algoritmada arama uzayında birden fazla çözüm kümesi kullanılabilir.
- Geleneksel algoritmalar bir aramayı gerçekleştirmek için daha fazla bilgiye ihtiyaç duyarken, genetik algoritmalar bir bireyin uygunluğunu hesaplamak için yalnızca bir amaç fonksiyonuna ihtiyaç duyar.
- Geleneksel Algoritmalar paralel çalışamazken genetik Algoritmalar paralel çalışabilir (bireyselliklerin uygunluğunun hesaplanması bağımsızdır).
- Genetik Algoritmalardaki büyük bir fark, kalıtsal algoritmaların doğrudan arayıcı sonuçları üzerinde çalışmak yerine, sıklıkla kromozom olarak adlandırılan temsilleri (veya oluşturmaları) üzerinde çalışmasıdır.
- Geleneksel algoritma ile genetik algoritma arasındaki en büyük farklardan biri doğrudan aday çözümler üzerinde işlem yapmamasıdır.
- Geleneksel Algoritmalar sonuçta yalnızca bir sonuç üretebilirken, Genetik Algoritmalar farklı nesillerden birden fazla optimal sonuç üretebilir.
- Geleneksel algoritmanın en iyi sonuçları üretme olasılığı daha fazla değildir, oysa Genetik algoritmalar en iyi küresel sonuçları üretmeyi garanti etmez, ancak aynı zamanda Çaprazlama ve Mutasyon gibi genetik operatörleri kullandığından bir problem için en iyi sonucu alma olasılığı da yüksektir.
- Geleneksel algoritmalar doğası gereği deterministiktir, oysa Genetik algoritmalar doğası gereği olasılıksal ve stokastiktir.