Tez No	İndirme	Tez Künye	Durumu
769355		Dinamik ortamlar için istatiksel metotlar kullanan çoklu evrimsel algoritmalar / Multiploid evolutionary algorithms with statistical methods for dynamic environments Yazar:EMRULLAH GAZİOĞLU Danışman: PROF. DR. AYŞE ŞİMA UYAR Yer Bilgisi: İstanbul Teknik Üniversitesi / Lisansüstü Eğitim Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı / Bilgisayar Mühendisliği Bilim Dalı Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control Dizin:	Onaylandı Doktora Türkçe 2022 106 s.
Gerçek dünyada karşılaştığımız birleşimsel (ing: combinatorial) optimizasyon problemleri doğası gereği dinamik bir yapıya sahiptir. Dinamik ortamlarda bulunması gereken optimum nokta zamanla değişeceğinden, sezgisel yaklaşımlar ancak bu ortamlara iyi adapte edilirse başarılı olabilir. Çevresel değişiklik, optimizasyon algoritmalarının her iki tarafında da (kısıtlar ve/veya amaç fonksiyonu) meydana gelebilir. Değişikliği ele almanın en basit yolu, algoritmayı yeniden başlatmaktır. Ancak, yeni optimal çözüm öncekinden çok uzak olmayabilir. Bu nedenle, yeniden başlatma fikri kullanışlı değildir. Bunun yerine, şimdiye kadar edinilen bilgiler mevcut ortama uyum sağlamak için faydalı olabilir. Bu uyarlamayı gerçekleştirmek için bazı dinamik ortam kriterleri dikkate alınmalıdır: (i): değişim sıklığı, (ii): değişikliğin şiddeti, (iii): döngü uzunluğu/döngü doğruluğu, (iv): değişimin öngörülebilirliği. Yukarıda bahsedilen problemleri ele alabilmek için literatürde hem deterministik hem de sezgisel yöntemler kullanılmıştır. Bu yöntemler yetersiz kalınca Metasezgisel algoritmalar kullanılmaya başlanmıştır. Genetik Algoritmalar, Metasezgisel algoritmaların, Evrimsel Algoritmalar alt sınıfına düşen ve türlerin doğadaki biyolojik evriminden ilham alan çok popüler optimizasyon algoritmalarıdır. GA'lar, literatürdeki büyük başarılarına rağmen, değişen ortamlarda genetik çeşitliliklerini kaybederler. Bunun nedenleri olarak şunları söyleyebiliriz: (i): faydalı çözümleri kaybetmek ve (ii): problemin değişkenleri arasındaki ilişkileri kullanamamak. Bu tezde, birinci sorun için, bir çoklu kromozom yapısı uygulanarak bir örtük bellek şeması geliştirilmiştir. İkinci sorun için, problemin değişkenleri (bir kromozomdaki genler olarak da bilinir) arasındaki ilişkilerden yararlanmak için bir Bayes Ağı kullanımıştır. Epistasis, gerçek biyolojik hayatta bir kromozomdaki genlerin etkileşimi anlamına gelir. Daha açık olarak, bir genin etkisi, başka bir genin/genlerin varlığına veya yokluğuna bağlıdır. Bu tezde, genlerin etkileşimlerinden faydalanmak için, çoklu gösterilimin yanı sıra, iyi bilinen bir Dağıtım Tahmini Algoritması olan Bayesçi Optimizasyon Algoritması, önerilen algoritmaya enjekte edilmiştir. Bu tezde, dinamik ortam optimizasyon problemleri ile baş edebilmek için GA tabanlı istatistiksel metotlar kullanan çok kromozomlu bir algoritma önerilmiştir. İlk olarak, örtük bir bellek şeması elde etmek için GA'ya çoklu gösterilim eklenmiştir. Genetik operatörler örtük bellek üzerinde icra edilirken uygunluk değeri hesaplamaları çözüm adaylarının fenotipleri üzerinden yürütülmüştür. Ayrıca, önerilen algoritmanın varyantları literatürde önceden tanıtılmış olan bazı göçmenlik yöntemleri kullanılarak oluşturulmuş, farklı parametre değerleri ile nasıl davrandıkları gözlenmiştir. Önerilen algoritmayı test etmek için üç farklı problem çözülmüştür: Ayrıştırılabilir Birleşim Tabanlı Fonksiyonlar, Dinamik Sırt Çantası Problemi ve Çok boyutlu Sırt Çantası Problemi. Ayrıştırılabilir Birleşim Tabanlı Fonksiyonlar, çeşitli karmaşıklık düzeyleri içerdikleri için dinamik optimizasyon problemlerinde sıkça kullanılan kıyaslama problemleridirler. Bu fonksiyonlarda her bir çözüm adayı dört bitlik bölümlere ayrılır ve her bölümün uygunluk değerleri ayrı ayrı hesaplandıktan sonra bulunan değerler toplanıp çözüm adayının genel uygunluk değeri bulunur. Sırt Çantası Problemi, bilgisayar bilimlerinde sıkça karşılaşılan bir problem formatıdır. Bu problemde, pahada (getirisi) ağır, yükte hafif nesnelerin toplanması hedeflenmekte ve bunu yaparken getiriyi maksimuma çıkarırken yükü minimumda tutmaya çalışılır. Gerçek dünya problemleri üzerindeki etkilerini görmek için bu problemin dinamik versiyonu çözüldü. Finansal yönetim ve endüstride, birçok gerçek dünya sorunu bu problem ile ilgilidir. Örneğin, kargo yükleme, üretim planlaması, sermaye bütçelemesi, proje seçimi ve portföy yönetimi bu problem ile çözülebilen örneklerdir. Çok boyutlu Sırt Çantası Problemi, normal versiyonundan farklı olarak, birden fazla kaynak içeren ve her bir kaynağın kendine ait kısıtları olan versiyonudur. Bu problem, tek bir kısıt yerine kaynak sayısı kadar kısıt olduğundan çözülmesi daha zordur. Yukarıda bahsedilen problemleri çözmek için iki farklı dinamik ortam yöntemi kullanılmıştır. Bunlardan birincisi XOR jeneratörü, diğer ise Normal Dağılım metotu ile yeni veri setleri oluşturmaktır. Sonuç olarak, bu tezde, dinamik optimizasyon problemlerini çözmek için hem istatistiksel bir yöntem hem de örtük bir bellek şeması kullanan bir GA önerilmiştir. Önerilen yöntemin dinamik ortamlardaki davranışını izlemek için üç farklı problem çözülmüştür. Daha sonra performansı literatürdeki en yeni bir yöntem ile karşılaştırılmıştır. Sonuçlar, önerilen yöntemin dinamik optimizasyon problemlerini çözmede oldukça etkili olduğunu göstermiştir.
Because of their nature, combinatorial optimization problems like the University Time-tabling Problem, the Traveling Salesman Problem (TSP), and social networks have a complex structure. Since the optimal point in dynamic environments changes with time, intuitive methods will only succeed if they are well suited to these environments. Otherwise, these algorithms appear to adhere to the local optimum, which ensures they can't guarantee solution success. Only where the environment and transition are thoroughly analyzed and a suitable solution is taken will success be achieved. The environment can change on both sides of the optimization algorithms (constraints and/or objective function). The most straightforward solution is to restart the algorithm. The new optimal solution, on the other hand, may not be that different from the previous one. As a result, restarting might not be a good idea. Instead, the knowledge collected so far may be useful in adjusting to the current environment. There are some dynamic environment parameters should be considered in order to achieve this adaptation: (i): frequency of change, (ii): severity of the change, (iii): cycle length/cycle accuracy, (iv): predictability of change. Genetic Algorithms are widely used optimization algorithms that are inspired by natural organisms' biological evolution. Despite their immense success in the literature, GAs lose their genetic diversity as environments change. There are various reasons for this, but we will concentrate on two of them in this study: (i): losing usable solutions, and (ii): not being able to use relationships between problem variables. To fix the first problem, a multiploid chromosome structure is used to create an implicit memory scheme. To fix the second problem, we used a Bayes Network to find relationships between the problem variables. Epistasis is a term used in biology to describe the association of genes on a chromosome. To put it another way, one gene's effect can be influenced by the presence or absence of another gene(s). For example, one individual may have a blond hair gene, while another may have a black hair gene. If both of them have a baldness gene, though, there is no reason to say what color their hair is and they will both go bald in time. In this paper, in addition to multiploidy, the Bayesian Optimization Algorithm, a well-known Estimation of Distribution Algorithm, will be injected into the proposed Genetic Algorithm variants to take advantage of gene interactions. Among the many of them, the main issue in the dynamic environments is keep tracking the changing optimum. Another problem is to catch to change as quickly as possible and adapt to the current environment. Some strategies are proposed for these issues: (i) Generating diversity when a change occurs, (ii) Maintaining diversity continuously, (iii) Using multipopulation (iv) Using Memory-based techniques. In order to increase or generate diversity when a change occurs, variable local search and hypermutation approaches can be used. They increase the mutation probability for a pre-determined number of generations when a change occurs. Working with multiple populations is another approach to handle the tracking down the moving optima in dynamic environments. In this approach, the population divided into more than one part and each part searches different parts of the search space. There is another type of multi-population approach which is called sentinels, which are fixed at the beginning, not reproduced during the search. They also can be selected for mating. Since they are fixed, the system can heal itself quickly when a change occurs. Random Immigrant scheme is proposed to maintain diversity at all times. In this approach, at each generation, a little number of the individuals in the population are replaced with randomly generated new individuals. This kind of technique may be problematic during the stationary periods, however, shows good performance where the frequency and severity of the change are relatively high. In order to address problems for stationary periods case, Elitism Immigrant scheme is proposed which replaces a portion of the population nearly mutated versions of the elite individual of the previous generation. However, its performance dramatically drops when the severity of the change is high since the individuals in the population start to become similar to each other. In order to handle this problem, the Hybrid Immigrant scheme is proposed which merges Random Immigrant schemes and Elitism Immigrant scheme in order to maintain a balance between exploration and exploitation. Using memory schemes is another solution method for dynamic environments. Memory scheme can be applied in two ways: (i) Implicitly by implementing redundant representation, or (ii) Explicitly by implementing extra memory area in order to save old but good solutions. In this thesis, as a novel approach, the Bayesian Optimization Algorithm is injected into Multiploid Genetic Algorithm in order to find and use relationships between the problem variables. The Bayesian Optimization Algorithm constructs a Bayesian Network to evolve a population and sample new individuals. A Bayesian Network is a directed acyclic graph that shows relationships between variables (nodes). In Bayesian Optimization Algorithm, first, a population is created randomly. The population then is evaluated in order to select high-quality solutions via a selection method. Next, a Bayeaian Network is constructed by using selected candidate solutions. After that, by using the Bayesian Network, new candidate solutions are sampled. Last, some or all of the existing population are replaced by new candidate solutions. Finally, a new Genetic Algorithm based optimization algorithm is proposed for dynamic environments. First, multiploid representation is introduced into Genetic Algorithm in order to get an implicit memory scheme: In the proposed algorithm, each candidate solution has four genotypes and one phenotype. Thus, we have the ability of reuse old but good solutions. For comparison, also a diploid version of the algorithm is implemented. Second, the Bayesian Optimization Algorithm is embedded into the structure to exploit interactions between variables (members of the candidate solutions) by constructing a Bayesian Network. This Bayesian Network is used for two purposes: (i): Deermining phenotype values of the candidate solutions according to their corresponding genotype values, and, (ii): sampling new candidate solutions as a whole for introducing Bayesian Immigrant scheme. Last, a random immigrant scheme is implemented in order to maintain diversity. In this dissertation, three problems are solved. First, Decompsaple Unitation-based Functions (DUF) are solved. These problems have different complexity levels, such as DUF1, DUF2, DUF3, and DUF4. The fitness calculation of each problem has different equations, like each solution candidate divided into 4-bits blocks and the fitness value of each block is calculated seperately. After that, each block's fitness values are summed up in order to get the total fitness value. As the second problem, we solved the well-known Dynamic Knapsack Problem (Dynamic KP) after solving the DUFs to test the algorithm we proposed in our study's effects on real-world problems. Many real-world issues like financial management and business are related to the KP. For example, the KP domain includes freight loading, cutting stock, production scheduling, capital budgeting, project selection, and portfolio management. Last, as the third problem, we solved the Multidimensional Knapsack Problem (MKP) in order to test the proposed algorithm. The MKP differs from the traditional KP in the number of resources. In this form of the problem, each dataset has more than one resources so problem gets harder. In order to see the effectiveness of the mechanisms implemented, we created eight variants of the algorithm by switching on and off these particular mechanisms, namely, random immigrant scheme (on/off), Bayesian immigrant scheme (on/off), and diploid or multiploid. With these eight variants, first, four DUF problems are solved. In order to observe the performances of the algorithms, a dynamic environment generator is used. By using this generator, three different dynamic environments is constructed, namely, cyclic, cyclic with noise, and random. After solving DUFs, the DKP and the MKP are solved by using only the multiploid variants of the proposed algorithm. For DKP, same dynamic environment generator is used as used for DUFs. On the other hand, for MKP, a different type of dynamic environment model is used. By observing the test results, several conclusions can be drawn: First, the proposed algorithm's structure improved simple Genetic Algorithm's performance for dynamic environments. Second, the Genetic Algorithms with Random Immigrant schemes perform better than the Genetic Algorithms with Bayesian Immigrant schemes in most cases, since Bayesian Immigrant scheme causes stucking in local optima. After comparing all variants to each other, one of them is selected by its performances, for comparing to a Genetic Algorithm based algorithm proposed by a recent study by solving the a Dynamic Knapsack Problem with 100 items. Results show that our algorithm has a huge advantage over the recently proposed one and it is easy to understand that the proposed algorithm is one of the best algorithms for solving dynamic optimization problems.