Ayrık optimizasyon problemlerinin çözümü için Jaya algoritması tabanlı yeni yaklaşımlar
Jaya algorithm based new approaches for solving discrete optimization problems
Yazar: MURAT ASLAN
Danışman: DOÇ. DR. MESUT GÜNDÜZ
Konya Teknik Üniversitesi / Lisansüstü Eğitim Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Doktora, 2020
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control

Özet:
Jaya algoritması, kısıtlı ve kısıtsız sürekli optimizasyon problemlerinin çözümü için Rao (2016) tarafından literatüre kazandırılan popülasyon tabanlı, stokastik bir metasezgisel algoritmadır. Bu tez kapsamında ikili ve ayrık tam sayı optimizasyon problemlerinin çözümü için Jaya algoritması tabanlı yeni yaklaşımlar geliştirilmiştir. Temel Jaya algoritması sürekli optimizasyon problemlerinin çözümü için geliştirildiğinden dolayı, karar değişilenleri '0' ya da '1' değerlerini alabilen ikili optimizasyon problemlerinin üzerine doğrudan uygulanamaz. Bu kapsamda temel Jaya algoritmasının konum güncelleme mekanizmasında bazı değişiklikler yapılmış olup, ikili optimizasyon problemlerinin çözümü için Jaya algoritması tabanlı yeni yaklaşımlar geliştirilmiştir. Geliştirilen ilk yaklaşım JayaX olarak adlandırılan; temelini Jaya algoritması ve 'özel veya' (XOR) lojik fonksiyonundan alan yaklaşımdır. Diğer yaklaşım ise JayaX algoritmasının yerel arama yönünü iyileştirmek için JayaX-LSM olarak adlandırılan, önerilen JayaX algoritmasının ve LSM olarak adlandırılan yerel arama modülünün birlikte kullanılması ile geliştirilen yaklaşımdır. İkili optimizasyon problemlerinin çözümü için önerilen algoritmaların performans analizi için deney aşamasında: Kapasitesiz tesis yerleştirme problemi (KTYP), CEC 2015 nümerik fonksiyonları ve rüzgâr türbini yerleştirme problemi kullanılmıştır. İlk deneysel analiz KTYP problemi için yapılmıştır. Önerilen algoritmaların performansını analiz etmek ve doğrulamak için deneylerde 15 farklı KTYP kullanılmıştır. Önerilen algoritmalar yakın zamanda literatüre kazandırılmış PSO, ABC, TSA, DE ve GA tabanlı başarılı ikili optimizasyon algoritmalarının sonuçları ile karşılaştırılmıştır. Elde edilen deneysel sonuçlara göre, önerilen algoritmalar, KTYP'yi çözme konusunda, karşılaştırılan diğer algoritmalar ile eşit ya da daha iyi sonuçlar elde etmiştir. İkinci deneysel analiz ise 15 kıyas probleminden oluşan CEC 2015 nümerik veri seti üzerine olmuştur. Bu analizde, JayaX-LSM algoritması SabDE, BQIGSA, GBABC, BHTPSO-QI, BLDE ve SBHS algoritmalarının sonuçları ile karşılaştırılmıştır ve elde edilen deneysel sonuçlar dikkate alındığında JayaX-LSM algoritması, karşılaştırılan algoritmalar ile rekabetçi ya da daha iyi çözümler elde etmiştir. Bu bölümde yapılan son deneysel analiz ise rüzgâr türbini yerleştirme problemi için yapılmıştır. Deneylerde 10×10 ve 20×20'lik olmak üzere iki farklı ızgara yapısı kullanılmıştır. Deneysel sonuçlara göre, JayaX-LSM algoritması karşılaştırmalarda kullanılan GA tabanlı ikili yöntemler, BIWO, BPSO-TVAC, EA, NGHS, DGHS ve binAAA algoritmalarına benzer ya da daha iyi çözümler üretmiştir.
Geliştirilen bir diğer yöntem ise ayrık tam sayı optimizasyon problemlerinin çözümü için Jaya algoritması tabanlı DJaya olarak adlandırılan Ayrık Jaya algoritmasıdır. Temel Jaya algoritmasının ayrıklaştırma işlemi için güncelleme mekanizmasında takas, öteleme ve simetri olarak adlandırılan komşuluk operatörleri kullanılmıştır. DJaya'da başlangıç popülasyonu oluşturulurken (N-1) tane aday çözüm rastgele permütasyon ile oluşturulurken, ilk aday çözüm en yakın komşu turu sezgiseli ile oluşturulmaktadır. Ayrıca DJaya'nın elde ettiği çözümlerin kalitesinin arttırılması amacıyla 2-opt yerel arama algoritması da kullanılmıştır. DJaya algoritmasının başarısını ve etkinliğini göstermek amacıyla,  deneylerde 14 farklı gezgin satıcı problemi (GSP) kullanılmıştır.  Elde edilen deneysel sonuçlar yakın zamanda literatüre kazandırılan başarılı algoritmaların sonuçları ile karşılaştırılmıştır. Deneysel bulgulara göre, DJaya algoritması gezgin satıcı probleminin çözümü için karşılaştırılan algoritmalardan daha başarılı ya da rekabetçi çözümler elde etmiştir.

Abstract:
Jaya algorithm is a stochastic population-based heuristic optimization algorithm proposed by Rao (2016) for solving constrained and unconstrained continuous optimization problems. In this study, Jaya algorithm based new approaches have been proposed for solving binary and discrete integer optimization problems. Because of the basic Jaya algorithm proposed for solving continuous optimization problems, it cannot be directly applied to binary optimization problems, because the solution space is discretely structured for this type of optimization problems and the decision variables of the binary optimization problems can be element of set [0,1]. In this context, some modifications have been made in update mechanism of the basic Jaya algorithm, and Jaya algorithm based new approaches have been proposed for solving binary optimization problems. The first proposed approach is JayaX; It is based on Jaya algorithm and the 'exclusive or' (XOR) logic function. The second approach is proposed in order to improve the local search capability of the JayaX algorithm, and it is called JayaX-LSM. JayaX-LSM is based on JayaX algorithm and local search module (LSM). For the performance analysis of the proposed algorithms to solve binary optimization problems, in the experimental phase:  Uncapacitated facility location problem (UFLP), CEC 2015 numerical functions and wind turbine placement problem are used. The first experimental analysis is made for UFLP problems. In order to examine and approve the performance of the proposed algorithms, 15 different UFLPs are used in the experiments. The proposed algorithms have been compared with the state-of-art binary optimization algorithms based on PSO, ABC, TSA, DE and GA which have been recently proposed into the literature. According to the experimental results, the proposed algorithms obtained equal or better performance than the compared algorithms in solving UFLP. The second experimental analysis is performed on the CEC 2015 numerical benchmark set consisting of 15 problems. In this analysis, the JayaX-LSM algorithm is compared with the experimental results of the SabDE, BQIGSA, GBABC, BHTPSO-QI, BLDE and SBHS algorithms, and considering the experiments, the JayaX-LSM algorithm obtained competitive or better solutions with the compared algorithms. The last experimental analysis in this section is made for the wind turbine placement problem. Two different grid structures, 10×10 and 20×20 are used in the experiments. According to the experimental results, the JayaX-LSM algorithm get equal or better solutions than GA-based binary methods, BIWO, BPSO-TVAC, EA, NGHS, DGHS and binAAA algorithms used in comparisons.
Another proposed method is a Jaya based discrete algorithm called as DJaya for the solution of discrete integer optimization problems.  Swap, shift and symmetry transformation operators are being used for discretization process of the update mechanism of basic Jaya. While creating the initial population in DJaya, (N-1) candidate solution is created by random permutation, and one candidate solution is created with the nearest neighbor tour heuristic. Furthermore, 2-opt local search algorithm has been used for improve the quality of solutions in DJaya. In order to examine and confirm the performance of the proposed algorithms, 14 different travelling salesman problems (TSP) are used in the experiments. The proposed algorithm has been compared with the state-of-art optimization algorithms. According to the experimental result, the DJaya algorithm has obtained better or competitive solutions than the compared algorithms for solving the traveling salesman problem.