Değişen ortamlar için genetik algoritmalar: Diploid gösterilimler ve baskınlık mekanizmaları

Tez (Doktora) -- İstanbul Teknik Üniversitesi, Fen Bilimleri Enstitüsü, 2002Thesis (Ph.D.) -- İstanbul Technical University, Institute of Science and Technology, 2002Genetik Algoritmalar, Darwin'in evrim teorisini ve Mendel'in kalıtım ile ilgili prensiplerini modelleme yaklaşımına dayanan stokastik, global optimizasyon yöntemleridir. Evrim teorisinin temelinde doğal seçim kavramı yatmaktadır. Bu teoriye göre, doğal seçim sonucunda diğerlerine göre bazı avantajları olan bireylerin yaşama ve sonraki kuşaklara yavru bırakma olasılıkları daha yüksektir. Bu avantajı sağlayan özellikler kalıtımsal ise bu özelliğe sahip bireylerden doğan yavruların da bir kısmı bu özelliği taşıyacak ve dolayısıyla aynı avantajlara sahip olacaklardır. Birkaç kuşak sonucunda bu iyi özelliği sağlayan bireylerin sayısı toplumda artacaktır. Klasik genetik bilimi kalıtımsal özelliklerin kuşaklar arası aktarım mekanizmaları ile ilgilenir. Bir optimizasyon probleminde temel amaç en iyi çözümü bulmaktır. Ancak bu her durumda mümkün olmayabilir, bu durumlarda bulunabilen en iyi çözümler de yeterli olur. Biyolojik evrim, bir ortamda yaşamaya ve üremeye en uygun bireylerin aranması şeklinde bir optimizasyon süreci olarak görülebilir. Bu bağlamda doğada bulunan bazı mekanizmaların modellenmesi yoluyla yapay optimizasyon problemlerinin çözülmesi uygun olur. Genetik algoritmalar bu prensibe dayanırlar. Ancak her zaman tüm mekanizmaları modellemek gerekmemektedir. Problemin taşıdığı özelliklere göre kimi zaman bunların bir alt kümesinin modellenmesi yeterli olacaktır, ancak kimi zaman da daha fazla mekanizmanın modellenmesi gerekecektir. Doğada çoğu karmaşık organizmanın diploid kromozom yapılan vardır. Diploid yapıda her özellik iki homolog kromozom üzerinde yer alan iki gen ile temsil edilir. Bu gösterilim gereğinden fazla bilgi içeriyor gibi görünse de, bu doğanın bir anlamda genetik bir bellek tutma yöntemidir. Bu şekilde şu anda faydalı olmayan ama ileride gerekli olabilecek bilgiler kaybedilmemiş, seçim aşamasının bozucu etkilerinden korunmuş olur. Bu özellikleri korumak amacıyla var olan en etkin mekanizma baskınlık mekanizmasıdır. Organizmanın aynı özellik için iki bilgisi olmasına rağmen bunlardan sadece birisi dışarıdan görülebilir. Baskın olan alel fenotipte görünen aleldir. Ancak çekinik alel ileride gerekli olabileceği bir zamana kadar maskelenmiş olur. Bu durumu ortaya koyan doğal bir örnek bir cins güve olan Biston Betularia'dır. Genetik algoritmalarda diploid gösterilimler kullanımı da literatürde yer alan ve incelenmekte olan bir konudur. Dünya üzerinde yaşam sürekli değişen bir süreçtir ve hayatta kalabilmeleri için organizmaların bu değişimlere uyum sağlamaları gerekmektedir. Uyum sağlayamayanlar yok olurken sağlayabilenler gelişerek daha çok yavru yapacaklardır. Ancak zaman içinde çevre koşulları yeniden değişecek ve eski koşullarda yaşamayı başarabilenler yeni duruma uyum gösteremezlerse yok olacaklar ve yerlerine yenileri gelecektir. Yapay ortamda çözülmek istenen problem dinamik olarak değişiyorsa, seçilen çözüm yöntemi de bu değişime uyum sağlayıp izleyebilmelidir. Bu amaçla doğada bunu sağlayan mekanizmaların modellenmesi uygundur. Doğal sistemlerde uyum sağlamanın itici güçlerinin başında diploid kromozom yapısı ve baskınlık mekanizması gelmektedir. Diploid yapı, genetik bir bellek mekanizması sağladığı gibi, çeşitlilik de katmaktadır. Bellek özelliği, baskınlık mekanizmasının sağladığı maskeleme etkisi sonucunda eski iyi çözümlerin hatırlanması ile oluşmaktadır. Her xi özellik farklı değerlere sahip olabilen iki adet gen tarafından temsil edildiğinden dolayı, her anne birey haploid yapılara göre iki katı daha fazla genetik bilgi taşımaktadır ve bunun sonucunda da üreme aşamasında çocuklara aktarılacak özelliklerde çeşitliliği sağlanmaktadır. Çoğu gerçek dünya optimizasyon problemi de dinamik bir yapıya sahiptir ve değişen ortamlara uyum sağlayan çözüm yöntemleri kullanılmasını gerektirmektedir. Bu ise, optimize edilen fonksiyonun veya bazı kısıtlamaların zaman içinde değişmesi ve dolayısıyla optimumun da yer değiştirmesi şeklinde olabilir. Bu problemi çözmenin en basit yöntemlerinden biri her değişiklik olduğunda çözüme en baştan başlamaktır. Ancak çoğu durumda yeni oluşan çözümler eskilerden çok farklı olmayacaklardır. Bu yüzden, o ana kadar kazanılan bilginin tamamen kaybedilmesi uygun olmayacaktır. Bu durumda genetik algoritmanın o ana kadar elde edilen bilgiler üzerine yeni çözümleri değişime uyum sağlayarak bulması daha doğrudur. Klasik genetik algoritmalar kısa bir sürede yakınsadıklarından toplumun gen havuzu çeşitliliğini kaybeder ve dolayısıyla değişikliklere uyum sağlaması zorlaşır. Genetik algoritmaları dinamik ortamlarda da çalışmaya uygun hale getirmek için araştırmalar yapılmaktadır. Bu çalışmaların bir kısmı diploid gösterilimler üzerine yoğunlaşmıştır. Ancak bazı çalışmalarda da incelendiği gibi, değişimi izlemeye yeter düzeyde çeşitliliğin toplumda korunması için sadece diploid gösterilim kullanımı yeterli değildir. Bu çalışmanın temel amacı, yukarıda verilen hedefi gerçekleştirmek amacıyla, diploid yapılan, baskınlık mekanizmalarını ve bazı ek iyileştirme yaklaşımlarım incelemek ve genetik algoritmalara yeni bir diploid yaklaşım ve baskınlık mekanizması eklemektir. Eklenen yenilikler üreme aşamasında miyoz bölünme benzeri bir yöntem, örtüşen toplumlar ve yaşa dayalı birey yenilemedir. Önerilen algoritma, basit genetik algoritma ile ve geliştirilen baskınlık yöntemi de literatürde yaygın yer alan bir baskınlık mekanizması ile karşılaştırılmıştır. Karşılaştırma amacıyla kullanılan problemler yine literatürde sıkça bu amaçla kullanılanlar arasından seçilmiştir. En son olarak da önerilen yaklaşım dağıtılmış sistemlerde karşılaşılan dinamik yük dengeleme problemine uygulanmıştır. Test aşamasının birinci adımının sonucunda, basit genetik algoritma için de kolay olan, stasyoner problemlerde önerilen algoritmanın da eş derecede başarılı olduğu görülmüştür. Ancak diploid algoritmanın getirdiği ek karmaşıklık nedeniyle bu durumlarda basit genetik algoritmanın kullanılması daha uygundur. Tüm dinamik test problemlerinde, önerilen yaklaşımın basit genetik algoritmadan çok daha iyi sonuçlar verdiği görülmüştür. Bunun başlıca nedenleri de, diploid yapının getirdiği bellek ve miyoz hücre bölünmesi ile yaşlanma mekanizmasının sağladıkları çeşitliliktir. Ayrıca dikkat edilmelidir ki, önerilen algoritma aranan optimumların iki değer arasında salınım yaptıkları durumlarda iyi bir başarım göstermektedir; ancak optimumların rasgele değiştikleri durumda bile getirdiği genotipteki çeşitlilik sayesinde önerilen algoritma basit genetik algoritmadan ve diğer diploid yaklaşımlardan daha iyi sonuçlar vermektedir. ikinci test aşaması da olumlu olmuştur. Önerilen yaklaşım, karşılaştırma yapılan diğer baskınlık mekanizmasından çok daha iyi sonuçlar vermiştir. Bunun başlıca nedeni de, önerilen yaklaşımda baskınlık değerlerinin toplumla birlikte değişmesi ve değişen ortama uyum sağlamasıdır. Dinamik optimizasyon problemlerinde amaç fonksiyon zaman içinde değiştiğinden bu değişimi en iyi şekilde izleyen ve uyum sağlayabilen bir yaklaşım, genetik algoritmanın başaranım artırır ve bu tip problemlerin çözümünde kullanılmaya elverişli kılar. Önerilen yöntemi diğer yöntemlerle karşılaştırma aşamasından sonra, yöntemin sağladığı çeşitlilik ve her ek özelliğin bu çeşitliliğe katkısı, bir dizi kontrollü test problemi aracılığıyla incelenmiştir. x damGA'nın yük dengeleme problemine uygulanması sonucunda da olumlu sonuçlar elde edilmiştir. Yük dengeleme birimi olarak SGA kullanan benzer bir yapıyla gerçekleştirilen karşılaştırmalar sonucunda damGA'nın önemli iyileştirmeler getirdiği görülmüştür. damGA'nın getirdiği dezavantajların başında işlem yükü gelmektedir. Yapılan ölçümler sonucunda damGA'nın SGA ile kıyasla ortalama üç ila dört kat daha fazla işlem zamanı gerektirdiği gözlemlenmiştir. Bu sonuç ise damGA'nın, diğer yaklaşımların başarısız olduğu durumlarda kullanılmaya uygun olduğu gerçeğini vurgular. Diğer, daha basit yaklaşımların iyi sonuçlar verdiği durumlarda onların kullanılması daha doğru olur. Bu çalışmanın getirdiği temel katkı çeşitliliğin korunması ve baskınlık değerlerinin değişime otomatik olarak adapte olmalarında yatmaktadır. Çeşitlilik ve değişimi izleyebilme değişen ortamlarda çalışırken büyük önem taşıdığından, bu çalışmada önerilen yaklaşımın bu durumlarda kullanılmaya uygun olduğu görülmektedir.Genetic Algorithms are a class of stochastic, global optimization algorithms which model the biological principles of Darwin's theory of evolution and Mendel's principles of classical genetics. The theory of evolution centers around the principle of natural selection which mainly states that those individuals that have a certain characteristic which gives them some advantage above the others are more likely to survive and reproduce. If this characteristic is inheritable, then some of these individuals' offspring will be born with it and thus have the advantage over the others. After a few generations, the number of individuals with the favorable trait will increase in the population. Classical genetics deals mainly with the transmission of hereditary material from one generation to the next. In an optimization problem, the aim is to find the best solution. This may not be possible in all cases, so usually a near-best solution is acceptable. Biological evolution may be seen as an ongoing global optimization process which keeps on searching for the optimal individual for a certain environment. In that sense, some mechanisms found in nature that lead to this natural global optimization process can be modeled to solve the artificial optimization problems. Genetic algorithms act on this principle. However, it is not always necessary to model all the natural mechanisms. While for certain classes of problems a simple subset of these would work well, for some others a more complicated algorithm that models more natural operators may lead to better solutions. In nature, most complex organisms have a diploid chromosome structure. This means that the organism has two genes for each characteristic, located on two chromosomes. Even though this seems like redundant information, it is nature's way of keeping a genetic memory. This way, genetic information which may be useful in the future is not lost but is shielded from the harmful short-term effects of selection. The main mechanism which aids in shielding these characteristics is domination. While the organism has two alleles for the same characteristic, only one of them is expressed. The allele that is dominant over the other appears in the phenotype. However, the recessive allele is not lost but is simply masked until a future time when it may become useful. A well known example of this in nature is the Biston Betularia, the peppered moth. Diploid representations for genetic algorithms have been discussed and summarized in literature. Life on earth is an ever-changing process and the organisms must adapt to this change in order to survive. Those who cannot adapt will perish while those who can will thrive and produce more offspring. However, there will come a time when environmental conditions change again and those who thrived may no longer be able to survive under the current conditions, thus new organisms which adapt better will take their place. In the artificial case, when the problem to be solved occurs in a dynamically changing vui environment, the chosen approach for the solution must be able to adapt to and track this change. It seems appropriate to model natural mechanisms to achieve this. In natural systems, one of the driving forces of this adaptation is diploidy and dominance. Diploidy in nature both acts as a genetic memory and as a means of introducing diversity. Genetic memory occurs because old good solutions are remembered due to the masking effect of dominance. Since every characteristic is represented by two genes which may have different allele values, each parent individual may contain double the amount of genetic information its haploid counterpart would have and thus during reproduction this introduces diversity in the characteristics to be passed onto the offspring. Many real world optimization problems are also dynamic in nature and they require solution approaches that can adapt to this changing environment. The change may occur in the optimization function itself, or in some of the restrictions, causing the optimum to change too. One way to deal with this is to regard the problem as new after the change and start from scratch. However, not using the information that has already been gained is not feasible because in some cases, the new optimum may not differ too much from the old one. Hence it would be better if the optimization algorithm adapts to the change and builds on the current information. Classical genetic algorithms converge to an optimum after several generations, so the population loses its diversity and hence its ability to adapt to change. There has been some studies geared towards making genetic algorithms suitable to work in dynamic environments. A subset of these, deal with using diploid representations. However as shown in further studies, diploidy alone is not sufficient to preserve the required amount of diversity to follow the change in an environment. The main aim of this study is to investigate the use of diploidy and an adaptive dominance mechanisms with added features to achieve this desired objective and to introduce a new approach for applying diploidy and dominance to genetic algorithms. The added features are a meiosis-like cell division process during reproduction and overlapping populations with replacement of individuals based on an aging scheme. The proposed algorithm is tested against the simple genetic algorithm and also the adaptive dominance mechanism used in this study is tested against a common dominance scheme. The problem cases used in the testbed are commonly used in literature to compare different approaches. And finally the proposed approach is applied to the dynamic load balancing problem encountered in distributed computing systems. The results of the first part of the testing phase show that for stationary problems which are considered easy for the simple genetic algorithm, the proposed approach performs equally well. However, due to its complexity, in such cases it would be better to use the simple genetic algorithm. In all the dynamic cases, it is seen that the proposed approach outperforms the simple genetic algorithm. This is mainly due to the memory introduced by the diploid structure of the individuals and to the amount of diversity introduced by the aging mechanism and the meiotic cell division. It should also be noted that when the optima are oscillating between two peaks, the proposed approach performs well; however when the optima change in a random fashion, the proposed approach outperforms the simple genetic algorithm and other diploid representations, this time mainly due to the diversity maintained in the genotype. Also the results of the second test phase give promising conclusions. The proposed approach is seen to be much better than the tested dominance scheme, the main IX reason being the fact that the domination values in the proposed approach evolve along with the population, adapting to the changing environment. And since in dynamic optimization problems the fitness function changes in time, a method that also follows this change and adapts to it quickly improves the performance of the genetic algorithm, making it more suitable for this class of problems. In addition to the tests for comparisons, the diversity introduced by the approach and the contribution of each of its features in achieving this diversity is explored in greater detail through a set of controlled tests. Application of damGA to the load balancing problem also gives promising results. Comparisons with a similar setup, using a simple genetic algorithm for the load balancing unit are performed and results give improvements in favor of damGA. One of the main drawbacks of damGA presents in the form of added computational load. Tests show that on the average, damGA requires about three to four times more computational time than the SGA. This emphasizes the fact that it is better to use damGA in the cases where the other approaches fail and use the simpler ones whenever they work and give good results. The main contribution of this study lies in the way diversity is achieved and the way the domination values adapt to the changes in the environment. Since diversity and the ability to track change are the most important issues in dynamic environments, the approach taken in this study proves itself a very suitable method for use in such cases.DoktoraPh.D