An ensemble of differential evolution algorithm for real-parameter optimization and its application to multidimensional knapsack problem

Abstract

Bu tez, kısıtlanmış tek amaçlı test fonksiyonları aracılığı ile son dönemlerdeki gerçek parametre optimizasyon metotlarını incelenmiştir. Bu deneyimden esinlenerek, bu tür yöntemlerin aynı zamanda en zor ayrık problemlerden birisi olarak bilinen çok boyutlu sırt çantası problemine uygulanabilirliğini de ortaya koymuştur.Bu çalışmanın ilk bölümünde, CEC 2006'da ortaya konulan kıyaslama problemleri çözülmek üzere ele alınmıştır. Bu kıyaslama problemleri doğrusal olmayan amaç fonksiyonlarına sahip, çok boyutlu ve kısıtlanmış gerçek parametreli optimizasyon problemleridir. Bundan dolayı, sezgisel ve meta sezgisel yaklaşımları kullanmadan bu problemleri çözmek oldukça zordur. En iyi çözümler elde etmek için, önerilen algoritma (EDE-VNS) bu test fonksiyonlarına uygulanmıştır ve literatürdeki en iyi performansı gösteren algoritmalar ile karşılaştırılmış, rekabetçi sonuçlar elde edilmiştir. DE algoritmasının performansı çoğunlukla mutasyon stratejilerine, çaprazlama operatörlerine ve seçilmiş kontrol parametrelerine bağlıdır. Sonuç olarak, birden fazla mutasyon operatörleri ve kontrol parametrelerini kendi VNS döngüleri içerisinde bulundurabilen bir EDE-VNS algoritması çözümün kalitesini arttırabilmek amacıyla geliştirilmiştir. VNS döngüleri içindeki değişken mutasyon stratejilerinin toplu halde çalışmaları sayesinde, DE algoritmasının performansı o kadar olumlu etkilenmiştir ki çoğu kıyaslama problemleri sıfır standart sapma ile optimal olarak çözülmüştür. Mutasyon stratejilerinin toplu halde çalışmalarını etkisi göstermek için, bu test fonksiyonları bütün mutasyon stratejileri teker teker kullanılarak da çözülmüştür. Bireysel mutasyon stratejileri teker teker kullanıldığında, hepsi test fonksiyonlarında optimum çözümler bulma konusunda başarısız olduğu, oysaki bu mutasyon stratejileri toplu halde uygulandığında algoritma mutasyon stratejilerinin farklı özellikleri sayesinde optimal sonuçları kolaylıkla bulabildiği sonucuna varılmıştır. Bunun üzerine, bu algoritma aynı zamanda 240,000 ve 500,000 fonksiyon değerlendirilmesi ile çalıştırılmıştır. . Bu apaçık ortadadır ki, EDE-VNS algoritması ile daha çok optimal çözümler bulmak, daha fazla fonksiyon değerlendirilmesine ihtiyaç duyulmaktadır. Buna ek olarak, hedef bireylerin evrimini ve popülasyon içinde umut vadeden alanlardan alınan bazı iyi boyutlu değenlerin enjeksiyonunu temel alan çeşitlendirme yöntemi de, iki boyutlu turnuva seçilim yöntemi kullanılarak uygulanmıştır. Gelişmiş popülasyon içerisindeki uygun olmayan çözümlerden faydalanabilmek için, çözümü daha da geliştirmek amacıyla bazı kısıtlama işleme kuralları kullanılmıştır. Hesaplanan sonuçlar göstermektedir ki basit bir EDE-VNS algoritması literatürdeki bazı en iyi performansı gösteren algoritmalarla oldukça rekabetçidir.Bu tezin ikinci bölümünde, gerçek hayat problemlerinde geniş ölçüde uygulamaları olan 0-1 çok boyutlu sırt çantası probleminin, önerilen EDE-VNS algoritması ile çözülebileceği öngörülmüştür. Literatürde, çok boyutlu sırt çantası problemine uygulanan sezgisel yöntemlerin birçoğu, çözümleri geliştirmek için kontrol ve onarım operatörlerini kullanmıştır. Literatürde ortaya çıkan çalışmaların aksine, popülasyon çeşitliliğini zenginleştirmek için bazı gelişmiş kısıtlama işleme yöntemleri kullanılmıştır. Çeşitli toplu mutasyon stratejilerini kullanan değişken komşu aramalı diferansiyel evrim algoritması, deneme popülasyonunu oluşturmak için ortaya atılmıştır. Aslında önerilen bu EDE-VNS algoritması sürekli alanda çalıştığı için, gerçek değer kromozomları S-şeklindeki ve V-şeklindeki transfer fonksiyonlar kullanılarak 0-1 ikili değerlerine dönüştürülmüştür. Çözümleri geliştirmek için, EDE-VNS algoritmasıyla ikili takas yerel arama algoritması birleştirilmiş, önerilen algoritma OR-kütüphanesinden alınan karşılaştırma örnekleri üzerinde test edilmiştir.

This thesis examines the recent real-parameter optimization methods through constrained single objective test functions. Inspired from this experience, it also presents the applicability of such methods to Multidimensional Knapsack Problem known as one of the most difficult discrete problems.In the first part of this study, benchmark functions presented in CEC 2006 have been taken into consideration to solve. These benchmark problems are multi- dimensioned and constrained real-parameter optimization problems with non-linear objective functions. Hence, it is quite difficult to solve them without using heuristic and metaheuristic approaches. In order to obtain optimal solutions, proposed algorithm (EDE-VNS) has been applied to these test functions and competitive results have been collected to compare with the best performing algorithms from the literature. The performance of DE algorithm heavily depends on the mutation strategies, crossover operators and control parameters selected. As a result, an EDE-VNS algorithm that is possible to employ multiple mutation operators and control parameters in its VNS loops is proposed so as to be able further enhance the quality of the solution. By means of ensemble of variable mutation strategies in VNS loops, the performance of DE algorithm is affected so positively that most of benchmark functions could be optimally solved with zero standard deviations. In order to show the power of ensemble of mutation strategies, these test functions have also been solved by using all mutation strategies alone. It has been concluded that when using individual mutation strategies one by one, all of them fail to find the optimal solutions for test functions whereas when applying ensemble of these mutation strategies, algorithm could find optimal solutions easily by means of different properties of mutation strategies. Moreover, this algorithm was run for both 240,000 and 500,000 function evolutions. It is overly clear that EDE-VNS algorithm requires more function evolutions to find more optimal solutions with zero standard deviations. In addition, a diversification procedure which is based on the inversion of the target individual and the injection of some good dimensional values from promising areas in the population is also applied by using tournament selection with size 2. In order to take advantage of infeasible solutions in the evolved population, some constraint handling methods are also utilized to further improve the solution. The computational results show that the simple EDE-VNS algorithm was very competitive to the some of the best performing algorithms from the literature.In the second part of this thesis, the 0-1 multidimensional knapsack problem which has a great range of applications in real-life problems is considered to be solved by proposed EDE-VNS algorithm. In the literature, most of the heuristic methods applied to multidimensional knapsack problem use and check and repair operator to improve solutions. Unlike the studies appearing in literature, some sophisticated constraint handling methods in order to enrich the population diversity are used. Differential evolution algorithm with variable neighbourhood search employing ensemble of mutation strategies to generate the trial population is proposed. Since the proposed DE-VNS algorithm in fact works on a continuous domain, the real-values of the chromosomes are converted to 0-1 binary values by using S-shaped and V-shaped transfer functions. The effects of these transfer functions are tested by using them one by one in each mutation strategies of ensemble. So as to qualify the solutions, a binary swap local search algorithm is combined with proposed EDE-VNS algorithm and the proposed algorithm is tested on a benchmark instances from the OR-library.