Yeni Bir Metahuristik Yaklaşımla Alt Küme Toplamı Probleminin Çözümü Ve Performans Analizi

Year 2020, Volume: 7 Issue: 2, 503 - 512, 31.05.2020

Mustafa Furkan Keskenler Eyüp Fahri Keskenler

https://doi.org/10.31202/ecjse.660382

Abstract

Araştırmada iki farklı metaheuristik yaklaşımla alt küme toplamı problemi çözümüne odaklanılmıştır. Benzetilmiş Tavlama ve Genetik Algoritma yaklaşımlardan sonra bu iki metottan oluşan hibrit bir model geliştirilmiş ve daha iyi sonuçlar elde edilmiştir. Gözlemlenen sonuçlar literatürdeki diğer yöntemlerle kıyaslanmış ve çalışmada geliştirilen hibrit algoritma ile en iyi zaman maliyetine sahip sonuçların elde edildiği bulunmuştur. Kullanılan algoritmalar Cost değerleri yönüyle de başarılı sonuçlar vermiştir. Bilgisayar bilimlerinde NP-Complate problem olarak tanımlanan Alt küme toplamı problemi kullanılarak bu yöntemlerde kullanılan farklı fonksiyonlarla performans analizleri yapılmıştır. Böylece yaygın olarak kullanılan Simulated Annealing and Genetic Algorithm yöntemlerine ait alt fonksiyonların başarısı kıyaslanmış ve araştırmacılar için diğer çalışmalarda yol gösterebilecek bulgular elde edilmiştir.

Keywords

alt küme toplamı, benzetilmiş tavlama, genetic algoritma, hibrit model, sezgi üstü

Solution And Performance Analysis Of Subset Sum Problem With A New Metaheuristic Approach

Abstract

Subset sum problem was solved with two different metaheuristic approaches in the study. After these approaches, which are simulated annealing and genetic algorithms, a hybrid model of two methods was created and better results were obtained. The observed results were compared with other methods in the literature and the best time cost results were yielded owing to the hybrid algorithm developed in the study. The algorithms used gave successful results in terms of Cost values too. Performance analyses were measured on the Subset Sum Problem, defined as NP-Complete problem in computer science, with different functions used in these methods. Thus, the success of the sub-functions of the commonly used Simulated Annealing and Genetic Algorithm methods were compared and the findings were yield that could guide the researchers in other studies.

Keywords

subset sum, simulated annealing, genetic algorithm, hybrid model, metaheuristics

References

• B.L. Dietrich, L.F. Escudero, F. Chance, Efficient reformulation for 0–1 programs: methods and computational results, Discrete Appl. Math., 42 147-175.
• N. Mamano, W.B. Hayes, SANA: simulated annealing far outperforms many other search algorithms for biological network alignment, Bioinformatics, 33 (2017) 2156-2164.
• T. Zhu, S. Chen, W. Zhu, Y. Wang, Optimization of sound absorption property for polyurethanefoam using adaptive simulated annealing algorithm, JOURNAL OF APPLIED POLYMER SCIENCE, 135 (2018) 46426.
• Y. Ren, C. Zhang, F. Zhao, H. Xiao, G. Tian, An asynchronous parallel disassembly planning based on genetic algorithm, EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 269 (2018) 647-660.
• J.R. Fernándeza, J.A. López-Camposb, A. Segadeb, J.A. Vilánb, A genetic algorithm for the characterization of hyperelastic materials, APPLIED MATHEMATICS AND COMPUTATION, 329 (2018) 239-250.
• R.L. Wang, Agenetic algorithm for subset sum problem, Neurocomputing, 57 (2004) 463-468.