Sosyal örümcek algoritmasının sürekli ve ayrık optimizasyon problemlerinde performans iyileştirmeleri
Performance improvements of social spider algorithm in continuous and discrete optimization problems
Yazar: EMİNE BAŞ
Danışman: PROF. DR. ERKAN ÜLKER
Konya Teknik Üniversitesi / Lisansüstü Eğitim Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı / Bilgisayar Mühendisliği Bilim Dalı
Derece: Doktora, 2020
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control

Özet:
Doğa olguları temelli evrimsel hesaplama iki önemli gruba ayrılabilir. Bunlar evrimsel algoritmalar ve akıllı sürü temelli algoritmalardır. Evrimsel algoritmalar doğadan ilham alınarak üretilmiş algoritmalardır. Evrimsel algoritmalar optimizasyon problemlerinde ve gerçek dünya problemlerinde başarılı sonuçlar elde edebilmektedir. Bu tip algoritmalara genetik algoritma (GA), genetik programlama (GP), evrimsel stratejiler (ES) ve diferansiyel evrim (DE) örnek verilebilir. Akıllı sürü temelli algoritmalar ise son yıllarda oldukça ilgi çekmektedir. Bu tip algoritmalara Parçacık Sürü Optimizasyon algoritması (PSO), Yapay Arı Kolonisi algoritması (ABC), Karınca Kolonisi Optimizasyon algoritması (ACO) ve Yarasa Algoritması (BA) örnek verilebilir. Sürü terimi birbirleri ile iletişim halinde olan bireylerden oluşan topluluğu ifade etmektedir. Akıllı sürü temelli algoritmalar doğada var olan kuş, karınca, arı, bakteri, kelebek, örümcek v.b. gibi canlıların davranışlarını taklit ederler. Akıllı sürü temelli algoritmalar sürekli, ayrık ve ikili optimizasyon problemleri gibi pek çok farklı tip problemleri başarılı bir şekilde çözebilmektedirler. Çözülmesi çok zor olan NP-hard türü problem tiplerini çözmekte yüksek başarı göstermektedirler. 
Sosyal Örümcek Algoritması (SSA), son yıllarda yeni geliştirilmiş sürü temelli bir algoritmadır. Doğada birlikte yaşayan örümcek türlerinin taklit edilmesi ile oluşturulmuştur. Bu tez kapsamında SSA'nın sürekli, ayrık ve ikili optimizasyon problemleri üzerindeki başarısı incelenmiş ve başarısını arttırmak için yeni yöntemler eklenerek SSA geliştirilmiştir. 
SSA nın ilk önerildiği orijinal algoritması küçük boyutlu (10, 20 ve 30) sürekli optimizasyon problemlerinde test edilmiştir. Bu tezde SSA'nın orijinal haline Örümcek patlaması ve kaşif örümcek belleği özellikleri eklenerek geliştirilmiştir ve Sosyal Örümcek Algoritması (ISSA) önerilmiştir. SSA'nın eklenen tekniklerle yerel ve global arama yeteneği artmıştır. ISSA'nın düşük, orta ve yüksek boyutlu (10, 20, 30, 100, 500 ve 1000) sürekli optimizasyon problemlerinde başarısı test edilmiştir. Sürekli optimizasyon görevleri için gerçekleştirilen farklı ikinci bir çalışmada orijinal SSA'ya çaprazlama, mutasyon, Gbest yakınsaması ve sessiz örümcek şeklinde dört özellik eklenerek MPEF üzerinde ISSA'nın başarısı incelenmiştir. MPEF, ölçeklenebilir, basitleştirilmiş Moleküler Potansiyel Enerji Fonksiyonudur. Üçüncü çalışmada sürekli optimizasyon problemleri odaklı önerilen SSA, birbirinden bağımsız ayrık değerler alan problem türleri olarak bilinen ayrık optimizasyon problemlerini çözebilmesi için ayrık bir şekle getirilmiş ve Ayrık Sosyal Örümcek Algoritması  (DSSA) önerilmiştir. DSSA ile literatürde sıklıkla tercih edilen bir ayrık optimizasyon problemi olan Gezgin Satıcı Problemi (TSP) çözülmüştür. DSSA da, yetenekli örümcek ve acemi örümcek özellikleri eklenerek keşif ve sömürü yeteneği geliştirilmiştir. 
Tez kapsamında ayrık optimizasyonun bir alt grubu olan ikili optimizasyon problemleri de çözülmüştür. Bu çalışmada önerilen İkili Sosyal Örümcek Algoritması (BinSSA) ile dört farklı ikili optimizasyon problemi (özellik seçme problemi, kapasitesiz tesis yerleşim problemi, rüzgar türbinleri yerleşim problemi ve sürekli optimizasyon problemleri) çözülmüştür. Bu çalışmada, sürekli arama uzayı ikili arama uzayına çevrilirken S-şekilli, V-şekilli ve mod tabanlı transfer fonksiyonları kullanılmıştır. İkili optimizasyonda transfer fonksiyonlarının başarısını desteklemek için son yıllarda sıklıkla kullanılan lojik kapılar (xor lojik kapısı), benzerlik ölçme teknikleri (Jaccard ve Dice) ve çaprazlama operatörü yeni aday çözümler elde etmek için tercih edilmiştir. Bu yöntemler sayesinde BinSSA ikili arama uzayında yeni noktalar keşfedebilmekte veya yerel noktalar etrafında yeni noktalar bulabilmektedir.  Böylece BinSSA'nın başarısı geliştirilmiştir.

Abstract:
Evolutionary calculation based on natural phenomena can be divided into two important groups. These are evolutionary algorithms and intelligent swarm-based algorithms. Evolutionary algorithms are algorithms inspired by nature. It can achieve successful results in evolutionary optimization problems and real world problems. Such algorithms include genetic algorithm (GA), genetic programming (GP), evolutionary strategies (ES), and differential evolution (DE). Intelligent swarm based algorithms have attracted a lot of attention in recent years. Such algorithms include the Particle Swarm Optimization algorithm (PSO), the Artificial Bee Colony algorithm (ABC), the Ant Colony Optimization algorithm (ACO), and the Bat Algorithm (BA). The term swarm refers to the community of individuals who are in contact with each other. Intelligent swarm-based algorithms imitate the behavior of bird, ant, bee, bacteria, butterfly, spider etc. Intelligent swarm-based algorithms can successfully solve many different types of problems such as continuous, discrete and binary optimization problems. They are very successful in solving the problem types of NP-hard which are very difficult to solve. 
The newly developed Social Spider Algorithm (SSA) in recent years is a swarm-based algorithm. It is a swarm based algorithm created by imitating spider species living together in nature. Within the scope of this thesis, the success of SSA on continuous, discrete and binary optimization problems is examined and developed by adding new methods to increase its success.
Social Spider Algorithm (SSA) is a newly developed herd-based algorithm in recent years. It was created by imitating spider species that live together in nature. Within the scope of this thesis, the success of SSA on continuous, discrete and binary optimization problems has been examined and SSA has been developed by adding new methods to increase its success.
The SSA was tested in small size (10, 20, and 30) continuous optimization problems in the original algorithm for which SSA was proposed first. In this thesis, the original version of SSA was developed by adding spider explosion and explorer spider memory features and Social Spider Algorithm (ISSA) was proposed.  In addition, the ability to search locally and globally has increased. The success of ISSA in low, middle, and high dimensional (10, 20, 30, 100, 500, and 1000) continuous optimization problems has also been tested. In a second study performed for continuous optimization tasks, the success of ISSA on MPEF was examined by adding four features to the original SSA in the form of crossover, mutation, Gbest convergence and silent spider. MPEF is a scalable, simplified Molecular Potential Energy Function. In the third study, the proposed SSA focusing on continuous optimization problems was transformed into a discrete form in order to solve the discrete optimization problems known as the problem types that take independent discrete values, and the Discrete Social Spider Algorithm (DSSA) was proposed.  The Traveling Salesman Problem (TSP), which is a discrete optimization problem frequently preferred in the literature, has been solved with DSSA. In DSSA, exploration and exploitation capabilities are enhanced by adding skilled spider and novice spider features.
In this thesis, binary optimization problems, a subset of discrete optimization, are also solved. With the Binary Social Spider Algorithm (BinSSA) proposed in this study, four different binary optimization problems (feature selection problem, uncapacitated facility location problem, wind turbines placement problem and continuous tasks) are solved. In this study, S-shaped, V-shaped and mode-based transfer functions are used while converting the continuous search space to a binary search space. In order to support the success of transfer functions in binary optimization, logic gates (xor logic gate), similarity measurement techniques (Jaccard and Dice), and the crossover operator, which are frequently used in recent years, have been preferred to obtain new candidate solutions. Thanks to these methods, BinSSA can discover new points in the binary search space or find new points around local points. Thus, the success of BinSSA has been improved.