Geri Dön

Genetik algoritmalarda mutasyon çaprazlama ve bellek mekanizmalarının etkileri ve iyileştirilmesi

Effects and improvement of mutation crossover and memory mechanisms in genetic algorithms

PDF İndir

  1. Tez No: 202237
  2. Yazar: HANİFE USTA
  3. Danışmanlar: YRD. DOÇ. DR. İLYAS EMİNOĞLU
  4. Tez Türü: Yüksek Lisans
  5. Konular: Elektrik ve Elektronik Mühendisliği, Electrical and Electronics Engineering
  6. Anahtar Kelimeler: Genetik algoritma, optimizasyon, seçme, çaprazlama, mutasyon, elitizm
  7. Yıl: 2007
  8. Dil: İngilizce
  9. Üniversite: Ondokuz Mayıs Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Elektrik-Elektronik Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 124

Özet

Bu tez çalışmasında; çaprazlama ve mutasyon işlemcilerinden esinlenerek ortaya çıkmış, biyolojik kökenli optimizasyon yöntemi olan genetik algoritma (GA) incelenmiştir. Çalışmada ilk olarak genetik algoritmanın tanımı, çalışma şekli ele alınmış ve kullanılan çaprazlama, mutasyon işlemcilerinin etkileri ayrıntılı olarak incelenmiştir. Ayrıca fonksiyon optimizasyonu için kaynaklarda sık kullanılan tek ve çok amaçlı yapay test fonksiyonlarına yer verilmiştir. Genetik algoritmalar topluluk tabanlı ve çok adımlı olmakla birlikte, kullandıkları matematiksel araçlar/işlemciler açısından bakıldığında yapısı karmaşık değildir. Temel itibariyle GA da en az bir amaç fonksiyonu, seçme mekanizması, çaprazlama ve mutasyon işlemcileri bulunur. Genetik algoritmada genelde ilk topluluk rasgele oluşturulur. En iyiyi bulmak ve iyi bir yakınsama elde etmek için topluluk üzerinde genetik işlemler uygulanır. Önceden belirlenen adım sayısına ulaşınca veya hata belli bir ön tanımdan küçükse işlem sona erdirilir. Bu çalışmada GA'nın hesapsal olarak adım adım nasıl çalıştığı ve nasıl çözüm üretebildiği, karmaşık olmayan bir optimizasyon problemi üzerinde gösterilmiştir. GA da kullanılan işlemcilerin (mutasyon/çaprazlama) algoritma üzerindeki etkileri işlemcilerin olasılık değerleri değiştirilerek irdelenmiştir. Genetik algoritmalar çok değişkenli problemlerin optimizasyonu amacıyla kullanılan sezgisel yöntemdir. Rasgele sayı üretimine dayalı olarak çözümler üreten genetik algoritmalar N defa çalıştırıldıklarında aynı sonucu üretmeyebilirler. GA da seçilen bireylerin bir nesilden diğer nesile nasıl aktarıldığını belirleyen çaprazlama ve mutasyon işlemcilerinin olasılık güdümlü çalışması; topluluğun bir nesilden bir sonraki nesile olan değişiminin izlenmesini zorlaştırmaktadır. Bu tez çalışmasında topluluğun dinamik davranışlarını incelemek amacıyla eldeki problem izlenebilir boyuta düşürülmektedir. Bu tezde amaçlanan bir birey çiftinin çaprazlama ve mutasyon işlemcileri altında nasıl davrandığını modellemek ve bu modelden elde edilecek veriler ışığında topluluğun genel davranışı hakkında geçerli bir modele/yaklaşıma ulaşmak istenmektedir. GA da mevcut sıralama yöntemleri bireylerin sayısal gövdelerinin farklılığını dikkate almadan sıralama yapmaktadır. Klasik GA da yüksek puanlı bireylerin seçilme olasılığı yüksektir, bu da yüksek puanlı ve nispeten benzer sayısal gövdeli bireylerin seçilmesiyle sonuçlanmaktadır. Elde edilen benzetim sonuçlarında; yüksek puanlı ve sayısal gövde itibariyle birbirine benzemeyen bireylerin, bir başka deyişle yüksek puanlı, farklı bireylerin yeni çözümler üretme olasılığının fazla olduğu gözlenmiştir Genetik algoritmada bellek (elitizm) mekanizması, üretilen iyi çözümlerin saklanması ve bir sonraki nesle aktarılması işlevini yerine getirdiğinden GA'nın çözüm üretme kabiliyetini arttırmaktadır. Klasik GA'daki bellek mekanizması topluluktaki en iyi bireylerin bir kısmını veya tamamını bir sonraki topluluğa aktarmaktadır. Bu çalışmada genetik algoritmanın performansını arttırmak amacıyla bellek mekanizmasında değişikliğe gidilmiştir. Her adımda elde edilen en iyi birey/bireyler genetik işlemciler (çaprazlama/mutasyon) ile uyarılarak bir sonraki topluluğa aktarılır. Yapılan benzetim çalışmalarında her adımda elde edilen en iyi bireylerden daha iyi bireylerin elde edilebileceği gösterilmiştir. Bellek mekanizmasında önerilen ve denenen iyileştirme yöntemi kaynaklarda mevcut bellek mekanizmalı tüm genetik algoritmalara rahatlıkla uygulanabilir ve bu tezin önemli bir çıktısıdır.

Özet (Çeviri)

In this thesis study, genetic algorithm (GA) a biological based optimization method developed with an inspiration from cross-over and mutation is examined. In the first part of the study definition, operation principles of genetic algorithm are investigated and effects of used cross-over and mutation operators are examined in details. Furthermore single- and multi- objective artificial test functions which are frequently used in literature for function optimization are given. Although genetic algorithms are population based and multi step methods, from the side of used mathematical tools/operators the structures are not complex. As basis GA has at least one objective function, selection mechanism, cross-over and mutation operator. First in GA a random population is defined. To find the best and to have a sufficient convergence genetic operations are applied to the population. With a pre-defined step number or an error less than pre-defined error the operation is ended. In this study, according to the computations how GAs work and how GAs give solutions are shown step by step on a non-complex optimization problem. The effects of used GA operators (mutation/cross-over) on the algorithm are examined with changing probabilities of operators. GA is a heuristic method used in multi-variable optimization problems. As a method using random number generation for giving solutions genetic algorithms can?t give the same results for N times execution. The probability guided operation of cross-over and mutation defining how chosen individuals are transferred from one generation to another makes it hard to observe the change of population from one to another. To observe dynamic behaviours of the population the problems evaluated are decreased to an observable rate. The aim of this thesis is to model how an individual pair behave under cross-over and mutation operators and to reach a valid model/approximation on the general behaviour of the population using the datas obtained from this model. Available ordering methods of GA makes ordering without the consideration of difference of numerical body of individuals. In classical GA, possibility of selecting high point individuals is high and this causes selection of individuals with high points and relatively similar numerical bodies. With the obtained simulation results, it was observed that it is a high possibility to produce new solutions with individulas with high points and different numerical bodies, saying in a different way, with different individuals with high points. Because memory (elitism) mechanism in genetic algorithms preserves good solutions produced and passes to the next generation, they increase the ability of GA?s solution production. Memory mechanisms in classical GA passes the best individuals to the next population without any operation on them. In this study to increase the performance of the genetic algorithm memory mechanism is changed. In per-step the best/bests of individuals obtained are stimulated with genetic operators (crossover/mutation) and then passed to the next generation. With the simulation results it was shown that better individuals than best individuals obtained can be obtained. Suggested and tried improvement method in memory mechanism can be easily applied to all genetic algorithms with memory mechanism and it is an important output of this thesis. Keywords : Genetic algorithms, optimization, selection, cross-over, mutation, elitism

Benzer Tezler

  1. Tez No

    39286

    Yapay sinir ağlarında öğrenme algoritmalarının analizi

    Analysis of learning algorithms in neural networks

    SEVİNÇ BAKLAVACI

    Yüksek Lisans

    Türkçe

    Türkçe

    1994

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    DOÇ.DR. LEYLA GÖREN

  2. Tez No

    415548

    Scalable evolutionary algorithm for solving the one-dimensional bin packing problem on GPU using CUDA

    Tek boyutlu kutu paketleme probleminin grafik işlemci üzerinde CUDA kullanılarak ölçeklenebilir evrimsel algoritma ile çözümü

    ŞÜKRÜ ÖZER ÖZCAN

    Yüksek Lisans

    İngilizce

    İngilizce

    2015

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. AHMET COŞAR

    YRD. DOÇ. DR. YUSUF SAHİLLİOĞLU

  3. Tez No

    465041

    Tersanelerde gemi üretim yönetimi modeli: Marmara Bölgesinde bir uygulama

    Model of ship production management in shipyard: A case study in Marmara Region

    ERCAN AKAN

    Doktora

    Türkçe

    Türkçe

    2017

    Denizcilikİstanbul Üniversitesi

    Deniz Ulaştırma İşletme Mühendisliği Ana Bilim Dalı

    PROF. DR. GÜLER ALKAN

  4. Tez No

    341460

    Bayesci optimizasyon algoritmasının beslenme probleminde kullanımı

    The use of bayesian optimization algorithm for feeding problem

    SERPİL GÜMÜŞTEKİN

    Yüksek Lisans

    Türkçe

    Türkçe

    2013

    Beslenme ve DiyetetikOndokuz Mayıs Üniversitesi

    İstatistik Ana Bilim Dalı

    YRD. DOÇ. DR. TALAT ŞENEL

  5. Tez No

    104046

    Les applications des algorithmes genetiques dans les modüles d'Optimisation des prologiciels de Gestion integre

    İşletme kaynakları planlaması yazılımlarının optimizasyon modüllerinde genetik algoritma uygulamaları

    MELİKE ORHON

    Yüksek Lisans

    Fransızca

    Fransızca

    2001

    Endüstri ve Endüstri Mühendisliğiİstanbul Teknik Üniversitesi

    PROF. DR. ETHEM TOLGA

Geri Dön