İkili optimizasyon problemlerinin çözümü için yapay alg algoritması tabanlı yeni yaklaşımlar

Abstract

Son yıllarda optimizasyon problemlerinin çözümü için birçok yeni algoritma önerilmiştir. Bu algoritmalar genellikle doğadaki canlıların bireysel davranış şekillerinden, içgüdüsel hareketlerinden ve birbirleri ile aralarındaki akıllı etkileşimlerinden esinlenilerek geliştirilmişlerdir. Önerilen algoritmalar genellikle belirli bir problem çeşidine veya karakteristiğine sahip problemleri çözecek şekilde tasarlanmaktadır. Daha sonra yapılan çeşitli iyileştirmeler ve geliştirmeler neticesinde yönteme farklı karakteristikteki problemleri de çözebilme yeteneği kazandırılmaktadır. Örneğin, sürekli optimizasyon problemlerini (karar değişkenleri belirli bir aralıktaki tüm değerleri alabilen problemler) çözmek için önerilmiş bir algoritma, ikili optimizasyon problemlerini (karar değişkenleri sadece 0 yada 1 değerlerini alabilen problemler) çözecek şekilde geliştirilebilir. Bu tez kapsamında, karar değişkenleri sürekli değerler alan problemler için, doğada var olan mikroalglerin davranışlarından ilham alınarak geliştirilen Yapay Alg Algoritması (AAA) yeni ve özgün yöntemler geliştirilerek ikili optimizasyon problemlerini çözebilecek şekilde iyileştirilmiştir. Bu bağlamda 3 (üç) adet yeni ve özgün yöntem geliştirilmiştir.Önerilen ilk yöntemde, popülasyondaki alg kolonileri ikili değerler ile ilklendirilerek yeni aday çözümlerin elde edilebilmesi için helisel hareket fazı, ikili değerler ile çalışabilecek şekilde yeniden uyarlanmıştır. Helisel hareket fazında, seçilen komşu çözümün rastgele belirlenmiş üç adet boyutunun değerleri, belirli bir olasılığa bağlı olarak mantıksal değil (not) işlemine tabi tutularak aday çözüme kopyalanmaktadır. Geliştirilen binAAA yönteminde adaptasyon parametresi hem adaptasyon sürecinin işletilip işletilmemesine karar vermek için, hem de bu süreçte etkilenecek boyutların belirlenmesi için kullanılmıştır. Önerilen binAAA yöntemi Kapasitesiz Tesis Yerleşim Problemleri (Uncapacitated Facility Location Problems-UFLP) üzerinde çalıştırılmış ve elde edilen sonuçlar binABC, BPSO, GA, DisABC, IBPSO ve ABCbin algoritmalarının sonuçlarıyla karşılaştırılmıştır. binAAA yöntemi, ayrık çözüm uzayında çalışması, hem yerel (local) hem de küresel (global) aramada yetenekli bir arama stratejisine sahip olması nedeni ile ikili optimizasyon problemlerini çözme konusunda, karşılaştırılan diğer yöntemler ile eşit veya daha iyi sonuçlar üretmektedir.Önerilen ikinci yöntem, yeni aday çözümler üretebilmek için iki farklı güncelleme mekanizması barındırmaktadır. Bu mekanizmanın ilki, lojik özel veya (xor) operatörü kullanarak aday çözümler üretirken, ikinci mekanizmada ise ilk mekanizmadan edinilen bilgi kullanılarak stigmerjik (stigmergic) davranış temelinde yeni çözümler üretilmektedir. Önerilen SAAA (Stigmerjik AAA) yönteminde başlangıç çözümleri ikili değerler ile ilklendirilmekte, adaptasyon parametresi hem adaptasyon sürecinin işletilip işletilmemesine karar vermek için, hem de bu süreçte etkilenecek boyutların belirlenmesi için kullanılmıştır. SAAA yönteminin performansı hem UFLP hem de nümerik fonksiyonlar üzerinde araştırılmıştır. UFLP seti üzerinde, BAAA yönteminin 2 farklı versiyonu, GA yöntemin 3 farklı versiyonu ve BPSO yöntemi ile kıyaslanmıştır. İkinci karşılaştırma için ise CEC2015 (bound constrained single-objective computationally expensive numerical optimization problems) test seti kullanılmış ve önerilen yöntemin performansının değerlendirilebilmesi için SBHS, HS, BLDE, BHTPSO-QI, GBABC, BQIGSA ve SabDE yöntemleri ile kıyaslanmıştır. Bütün sonuçlar genel olarak incelendiğinde, önerilen algoritma sadece düşük boyutlu problemlerde değil, aynı zamanda yüksek boyutlu problemler için de dengeli bir keşif ve sömürü kabiliyeti sunmaktadır. Ayrıca önerilen algoritmanın, çözüm kalitesi, yakınsama özellikleri ve sağlamlık açısından araştırmada ele alınan ikili optimizasyon problemlerini çözmede etkili ve verimli bir algoritma olduğu görülmektedir.Tez çalışmasında PI-AAA (Popülasyon Etkili AAA) ismi ile önerilen üçüncü yöntemde de ilklendirme ikili değerler ile yapılmaktadır. Yeni ikili aday çözümlerin üretilebilmesi için popülasyon etkisi (population influence) yaklaşımı sunulmuş ve bu yaklaşım AAA'nın çalışmasıyla bütünleştirilmiştir. PI-AAA yönteminde, aday çözümler üretebilmek için, mevcut çözüm, en iyi çözüm ve alg kolonilerinden rastgele seçilen komşu çözümler kullanılmaktadır. Bu çözümler ile yapılan olasılık hesaplamaları neticesinde yeni aday çözümler üretilmektedir. Olasılık değerleri PI-AAA algoritmasına yönteme özgü kontrol parametresi olarak tanımlanmıştır. Önerilen yöntemin performansı için kontrol parametrelerinin değerlerinin önemli olması nedeniyle, parametrelerin etkileri analiz edilmiş ve bu parametreler için en uygun değerin belirlenmesi amaçlanmıştır. Temel AAA'daki adaptasyon aşaması, karar değişkenleri ikili değerler alan bireyler ile çalışabilmesi için yeniden uyarlanmıştır. Önerilen PI-AAA yönteminin performansı, ilk olarak UFLP seti üzerinde ABC, GA, PSO, EDA algoritmaları ile karşılaştırılmıştır. PI-AAA yönteminin etkinliğini kanıtlamak adına yapılan ikinci karşılaştırma CEC2015 problem seti üzerinde gerçekleştirilmiştir. Elde edilen sonuçlar, önerilen PI-AAA'nın karşılaştırmalarda daha iyi veya eşit performans gösterdiğini ve önerilen yaklaşımın rekabetçi bir ikili optimizasyon algoritması olduğunu göstermektedir.Sonuç olarak bu tez kapsamında, ikili optimizasyon problemlerini çözmek için AAA yöntemi temel alınarak binAAA, SAAA ve PI-AAA isimleri ile 3 (üç) adet yeni ikili optimizasyon algoritması geliştirilmiştir. Deneysel çalışmalardan elde edilen sonuçlar incelendiğinde, önerilen yöntemler çözüm kalitesi, standart sapma ve yakınsama özellikleri açısından ikili optimizasyon problemlerini çözmede alternatif, rekabetçi ve sağlam oldukları görülmektedir. Bu bağlamda bu tez ile literatüre ikili optimizasyon alanında bir katkı sağlanmıştır.

In recent years, many novel algorithms have been proposed for solving optimization problems. These algorithms are usually developed by inspiring from intelligent interactions with each other, behavioral patterns and instinctual movements of living in nature. The proposed algorithms are usually designed to solve problems with a particular type of problem or characteristic. As a consequence of various enhancements and improvements made later on, the method is also able to solve the problems of different characteristics additionally. For instance, an algorithm proposed to solve continuous optimization problems (decision variables that can take all values in a given range) can be developed to solve binary optimization problems (decision variables that can only take values of 0 or 1). In this thesis study, Artificial Algae Algorithm (AAA) that developed for solving continuous optimization problems by inspiring behavior of microalgae that already exists in nature has been improved in order to solve binary optimization problems by establishing novel and unique methods. In this context, 3 (three) novel and unique methods have been developed.In the first proposed method, in order to obtain new candidate solutions, the helical movement phase is re-adapted to work with binary values by initializing algae colonies in the population with binary values. In the helical movement phase, randomly determined three dimension values of selected neighbor solution are copied to the candidate solution and processing logical NOT function by depending on a particular probability. In the developed binAAA method, the adaptation parameter was used to make a decision whether the adaptation process should be operated or not and also to determine the dimensions to be affected in this process. The proposed binAAA method was investigated on Uncapacitated Facility Location Problems (UFLP) and the results were compared with the results of binABC, BPSO, GA, DisABC, IBPSO and ABCbin algorithms. The binAAA method produces equal or better results compared with other methods about solving binary optimization problems. This is because, the binAAA method works in discrete solution space and also it has a capable search strategy on both local and global search.The second proposed method includes two different update mechanisms to produce new candidate solutions. The first of these mechanisms is to produce candidate solutions by using the logical XOR operator, while in the second mechanism, new solutions are produced based on the stigmergic behavior by using the information obtained from the first mechanism. In the proposed SAAA (Stigmergic AAA) method, initial solutions are initialized with binary values, and the adaptation parameter is used to make a decision whether the adaptation process should be operated or not, and also to determine the dimensions to be affected in this process. The performance of the SAAA method was investigated on both UFLPs and numeric benchmark problems. The SAAA method was compared on the UFLP set with 2 different versions of the BAAA method, 3 different versions of the GA method and the BPSO method. For the second comparison, the CEC2015 (bound constrained single-objective computationally expensive numerical optimization problems) test set was used and it is compared with SBHS, HS, BLDE, BHTPSO-QI, GBABC, BQIGSA and SabDE methods in order to evaluate the performance of the proposed method. When all the results are examined in general, the proposed algorithm offers a balanced exploration and exploitation capability for not only low-dimensional problems and also for high-dimensional problems. Furthermore, it is seen that the proposed algorithm is an effective and efficient algorithm for solving the binary optimization problems covered in the research in terms of solution quality, convergence characteristics and robustness.The initialization is been processed with binary values as well in the proposed third method that named PI-AAA (Population Influenced AAA) in the thesis study. A population influence approach was introduced and this approach was integrated into the work of AAA in order to produce new binary candidate solutions. In the PI-AAA method, the randomly selected neighbor solutions from the algae colonies, the current solution and the best solution are used in order to produce candidate solutions. New candidate solutions are produced as a result of the probability calculations made with these solutions. Probability values were defined as peculiar control parameters to PI-AAA algorithm. Due to importance of control parameters' values for the performance of the proposed method, the effects of the parameters are analyzed and it is aimed to determine the most suitable value for these parameters. The adaptation phase in the basic AAA is re-adapted in order to work with binary decision variable values. The proposed PI-AAA method's performance is first compared with the ABC, GA, PSO, EDA algorithms on the UFLP set. The second comparison is performed on the CEC2015 problem set in order to prove the effectiveness of PI-AAA method. The obtained results show that the proposed PI-AAA indicates better or equal performance in comparisons and also those results point out that this proposed approach is a competitive binary optimization algorithm.In conclusion, in this thesis study, 3 (three) novel binary optimization algorithms have been developed with the name of binAAA, SAAA and PI-AAA based on AAA method in order to solve the binary optimization problems. When the results from experimental studies are examined, it is observed that the proposed methods are alternative, competitive and robust for solving binary optimization problems in terms of solution quality, standard deviation and convergence characteristics. In this context, a contribution has been made to the literature in the area of binary optimization with this thesis.