Evaluation of Surrogate Assisted Differential Evolution Algorithm for Single-Objective Numerical Optimization

Abstract

Hard optimization problems are solved successfully using nature inspired metaheuristics. However, in many cases of practical optimization problems, also called black-box problems, the evaluation of the objective function is main cause of high demand of computational resources. In the solution of these problems, objective function landscape is modeled mathematically, called a surrogate model which consist of replacing the objective function by an equivalent mathematical model, to reduce the computational evaluation time of the fitness function. The differential evolution (DE) algorithm is implemented with 4 strategies called rand/1, rand/2, best/2 and rand to best/1 to optimize the benchmark functions listed CEC2017 competition with dimensions D=10 and D=30. CEC2017 benchmark set is composed of 30 different functions with different degree of complexities. Locations of optimal solutions for these functions is supposed to be unknown and that’s why they are called black box functions. A surrogate model called the quadratic response surface model (QRSM) is used with Latin hyper square sampling strategy to replace objective function evaluations of benchmark functions. QRMS is used with DE for the solution of CEC2017 benchmark problems for the purpose of evaluating the performance of the surrogate assisted DE algorithm in terms of solution quality and runtime complexity. Experimental results obtained from the 4 different DE and DE+QRSM strategies illustrated that the rand/1 DE strategy was generally the best strategy in speed and accuracy for both dimensions D=10 and D=30. Also, the results generated by DE and DE+QRSM are compared with each other. As illustrated in tables of experimental evaluations, DE is found more accurate in majority of benchmark functions but it is slower generally. Also, a comparative study is done with other published algorithms such as L-SHADE, JSO, DISH, L-SHADE-LBR, JSO-LBR and DISH-LBR. Results obtained by these competitors are compared to only the best DE strategy, which is rand/1, employed within DE and DE+QRSM. The rand/1 strategy implemented within DE function was quit robust and performed better than other algorithms in many cases for D=10, but when implemented within DE+QRSM it becomes the worst one. For D=30 the rand/1 strategy loosed of its performance and was classified before the last position. Its rank is around of 80% when implemented within DE but it stays in last position with DE+QRSM algorithm.

ÖZ: Zor optimizasyon problemleri, doğadan ilham alan meta-sezgisel yöntemler kullanılarak başarılı bir şekilde çözülür. Bununla birlikte, kara kutu problemleri olarak da adlandırılan birçok pratik optimizasyon probleminde, amaç fonksiyonunun değerlendirilmesi, hesaplama kaynaklarının yüksek talebinin ana nedenidir. Bu problemlerin çözümünde, amaç fonksiyonunun hesaplamalı değerlendirme süresini azaltmak için amaç fonksiyonuna eşdeğer bir matematiksel model kullanılır. Amaç fonksiyonunun vekil model olarak adlandırılan bir matematiksel model ile değiştirilmesi sonucunda hesaplama süresinin kısaltılması amaçlanır. Diferansiyel evrim (DE) algoritması, CEC2017 optimizasyon yarışmasında listelenen D=10 ve D=30 boyutlarındaki kıyaslama fonksiyonlarını optimize etmek için rand/1, rand/2, best/2 ve rand to best/1 olarak adlandırılan 4 strateji ile uygulanmıştır. CEC2017 kıyaslama seti, farklı karmaşıklık derecelerine sahip 30 farklı fonksiyondan oluşmaktadır. Bu fonksiyonlar için optimal çözümlerin yerleri bilinmez ve bu nedenle kara kutu fonksiyonları olarak adlandırılırlar. İkinci dereceden yanıt yüzeyi modeli (QRSM) olarak adlandırılan bir vekil model, kıyaslama işlevlerinin amaç işlevi değerlendirmelerinin yerini almak için Latin hiper kare örnekleme stratejisiyle birlikte kullanılır. QRMS, vekil destekli DE algoritmasının performansını çözüm kalitesi ve çalışma zamanı karmaşıklığı açısından değerlendirmek amacıyla CEC2017 kıyaslama problemlerinin çözümü için DE ile birlikte kullanılmıştır. Dört farklı DE ve DE+QRSM stratejisinden elde edilen deneysel sonuçlar, Rand/1 DE stratejisinin hem D=10 hem de D=30 boyutları için genellikle hız ve doğruluk açısından en iyi strateji olduğunu göstermiştir. Ayrıca DE ve DE+QRSM tarafından üretilen sonuçlar birbirleriyle karşılaştırılmıştır. Deneysel değerlendirme tablolarında gösterildiği gibi, DE kıyaslama fonksiyonlarının çoğunda daha başarılı bulunmuştur, ancak genel olarak daha yavaştır. Ayrıca L-SHADE, JSO, DISH, L-SHADE-LBR, JSO-LBR ve DISH-LBR gibi yayınlanmış diğer algoritmalarla karşılaştırmalı bir çalışma yapılmıştır. Bu rakipler tarafından elde edilen sonuçlar, yalnızca DE ve DE+QRSM içinde kullanılan en iyi DE stratejisiyle, rand/1, karşılaştırılmıştır. DE algoritması içinde uygulanan rand/1 stratejisi, D=10 için birçok durumda güvenilir çıktı ve diğer algoritmalardan daha iyi performans gösterdi, ancak DE+QRSM içinde uygulandığında en kötüsü sıralamada yer aldı. D=30 için rand/1 stratejisi başarımını kaybetti ve son pozisyondan önce sınıflandırıldı. DE içinde uygulandığında rankı %80 civarındadır ancak DE+QRSM algoritması ile son pozisyonda kalmaktadır.