A new selection strategy for multi objective genetic algorithm: MultiMoora Rank Selection

Öz

Genetic algorithms are metaheuristic methods that provide satisfactory solutions for complex problems within acceptable time periods. In genetic algorithms, the selection strategy considerably affects the quality of the solution. In the study, the MultiMoora Rank Selection (MMRS) strategy based on the MultiMoora method, a multi-criteria decision-making method, was developed to improve the performance of the Multi Objective Genetic Algorithms (MOGA). The performance of the method was tested using flow-shop scheduling problems. The results obtained with the MultiMoora Rank Selection were evaluated by comparing with the results obtained using the same problem with the selection methods that are widely used for genetic algorithms, such as the Roulette Wheel Selection, Linear Rank Selection and Tournament Selection methods. The results showed that the proposed MultiMoora Rank Selection method outperformed the compared methods.

Anahtar Kelimeler

• Multi objective optimization,flow shop scheduling,genetic algorithm,MultiMoora,selection methods

Proje Numarası

2017-50-01-073

Çok amaçlı genetik algoritma için yeni bir seçim stratejisi önerisi: MultiMoora Rank seçimi

Öz

Genetik algoritmalar çözümü zor problemler için kabul edilebilir süre ve kalitede çözüm bulan metasezgisel bir tekniktir. Genetik algoritma uygulamalarında tercih edilen seçim stratejileri, çözüm kalitesini önemli ölçüde etkilemektedir. Bu çalışmada, Çok Amaçlı Genetik Algoritmalar (ÇAGA)’ın performansını arttırmak amacıyla, çok kriterli karar verme yöntemlerinden biri olan MultiMoora metoduna dayalı MultiMoora Rank Seçimi (MMRS) seçim stratejisi geliştirilmiştir. Geliştirilen metodun performansı çok amaçlı akış tipi çizelgeleme problemlerinde test edilmiştir. MultiMoora Rank Seçimi ile elde edilen sonuçlar, genetik algoritmada yaygın olarak kullanılan Rulet Tekerleği Seçimi, Lineer Rank Seçimi ve Turnuva Seçimi metotlarının aynı problem üzerindeki sonuçları ile karşılaştırılarak değerlendirilmiştir. Elde edilen sonuçlar, önerilen MultiMoora Rank Seçimi metodunun karşılaştırılan diğer metotlara üstünlük sağladığını göstermektedir.

Anahtar Kelimeler

• Çok amaçlı optimizasyon,akış tipi çizelgeleme,genetik algoritma,MultiMoora,seçim metotları

Destekleyen Kurum

SAÜ Bilimsel Araştırma Projeleri Komisyonu

Proje Numarası

2017-50-01-073

Teşekkür

Bu çalışma SAÜ Bilimsel Araştırma Projeleri Komisyonu tarafından desteklenmiştir. (Proje no: 2017-50-01-073)

Kaynakça

1. Çalışkan F., Yüksel H., Dayık M., Genetik Algoritmaların Tasarım Sürecinde Kullanılması, SDU Teknik Bilimler Dergisi, 6(2), 2016.
2. Goldberg D. E., Deb K., A comparative analysis of selection schemes used in genetic algorithms, Foundations of genetic algorithms, 1, 69-93, 1991.
3. Chakraborty U. K., Deb K., Chakraborty M., Analysis of selection algorithms: A Markov chain approach, Evolutionary Computation, 4(2), 133-167, 1996.
4. Chakraborty M., Chakraborty U. K., An analysis of linear ranking and binary tournament selection in genetic algorithms, Information. Communications and Signal Processing. ICICS, Proceedings of 1997 International Conference, 1, 407-411, 1997.
5. Alfonso H., Cesan P., Fernandez N., Minetti G. F., Salto C., Velazco L., Gallard R. H., Contrasting main selection methods in genetic algorithms, IV Congreso Argentina de Ciencias de la Computación, 1998.
6. Wiese K., Goodwin S. D., Keep-best reproduction: a selection strategy for genetic algorithms, Proceedings of the 1998 ACM symposium on Applied Computing, 343-348, 1998.
7. Wiese K., Goodwin S. D., The effect of genetic operator probabilities and selection strategies on the performance of a genetic algorithm, Conference of the Canadian Society for Computational Studies of Intelligence, Springer, 139-153, 1998.
8. Andrade A. V., Errico L. D., Aquino A. L. L. D., Assis L. P. D., Barbosa C. H. N. D. R., Analysis of selection and crossover methods used by genetic algorithm-based heuristic to solve the lsp allocation problem in mpls networks under capacity constraints, International Conference on Engineering Optimization, 2008.

9. Xie H., Zhang M., Tuning Selection Pressure in Tournament Selection, School of Engineering and Computer Science, Victoria University of Wellington, 2009.
10. Chudasama C., Shah S. M., Panchal M., Comparison of parents selection methods of genetic algorithm for TSP, International Conference on Computer Communication and Networks CSI-COMNET-2011, Proceedings, 85-87, 2011.
11. Razali N. M., Geraghty J., Genetic algorithm performance with different selection strategies in solving TSP, Proceedings of the world congress on engineering, 2, 1134-1139, 2011.
12. Kumar R., Blending roulette wheel selection & rank selection in genetic algorithms, International Journal of Machine Learning and Computing, 2(4), 365, 2012.
13. Alabsi F., Naoum R., Comparison of selection methods and crossover operations using steady state genetic based intrusion detection system, Journal of Emerging Trends in Computing and Information Sciences, 3(7), 1053-1058, 2012.
14. Jebari K., Madiafi M., Selection methods for genetic algorithms, International Journal of Emerging Sciences, 3(4), 333-344, 2013.
15. Oladele R. O., Sadiku J. S., Genetic algorithm performance with different selection methods in solving multi-objective network design problem, International Journal of Computer Applications, 70(12), 2013.
16. Nazmul R., Chetty M., A priority based parental selection method for genetic algorithm, Proceedings of the 15th annual conference companion on Genetic and evolutionary computation, 125-126, 2013.
17. Mayilvaganan M., Geethamani G. S., Performance Comparison of Roulette Wheel Selection and Steady state Selection in Genetic Nucleotide Sequence, International Journal of Innovative Research in Computer and Communication Engineering, 3(4), 2015.
18. Long Q., Wu C., Wang X., Jiang L., Li J., A multiobjective genetic algorithm based on a discrete selection procedure, Mathematical Problems in Engineering, 2015.
19. Anand S., Afreen N., Yazdani S., A Novel and Efficient Selection Method in Genetic Algorithm, International Journal of Computer Applications, 129(15), 7-12, 2015.
20. Shukla A., Pandey H. M., Mehrotra D., Comparative review of selection techniques in genetic algorithm, Futuristic Trends on Computational Analysis and Knowledge Management (ABLAZE), 2015 International Conference on, 515-519, 2015.
21. Pandey H. M., Performance evaluation of selection methods of genetic algorithm and network security concerns, Procedia Computer Science, 78, 13-18, 2016.
22. Irfianti A. D., Wardoyo R., Hartati S., Sulistyoningsih E., Determination of Selection Method in Genetic Algorithm for Land Suitability, MATEC Web of Conferences, EDP Sciences, 58, 2016.
23. Abd Rahman R., Ramli R., Jamari Z., Ku-Mahamud K. R., Evolutionary Algorithm with Roulette-Tournament Selection for Solving Aquaculture Diet Formulation, Mathematical Problems in Engineering, 2016.
24. Beg A. H., Islam M. Z., Genetic Algorithm with Novel Crossover, Selection and Health Check for Clustering, The 24th European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning (ESANN), 575-580, 2016.
25. Alkhayri W. R., Owis S., Shkoukani M., A New Selection Operator-CSM in Genetic Algorithms for Solving the TSP, International Journal of Advanced Computer Science and Applications, 7(10), 2016.
26. Saini N., Review of Selection Methods in Genetic Algorithms, International Journal Of Engineering And Computer Science, 6(12), 22261-22263, 2017.
27. Yadav S. L., Sohal A., Comparative Study of Different Selection Techniques in Genetic Algorithm, International Journal of Engineering, Science and Mathematics, 6(3), 2017.
28. Chehouri A., Younes R., Khoder J., Perron J., Ilinca A., A Selection Process for Genetic Algorithm Using Clustering Analysis, Algorithms, 10(4), 123, 2017.
29. Gonçalves J. F., de Magalhães Mendes J. J., Resende M. G., A hybrid genetic algorithm for the job shop scheduling problem, European journal of operational research, 167(1), 77-95, 2005.
30. Della Croce F., Tadei R., Volta G., A genetic algorithm for the job shop problem, Computers & Operations Research, 22(1), 15-24, 1995.
31. Kalayci C. B., Ertenlice O., Akyer H., Aygoren H., A review on the current applications of genetic algorithms in mean-variance portfolio optimization, Pamukkale University Journal of Engineering Sciences, 23(4), 2017.
32. Pour N., Tavakkoli-Moghaddam R., Asadi H., Optimizing a multi-objectives flow shop scheduling problem by a novel genetic algorithm, International Journal of Industrial Engineering Computations, 4(3), 345-354, 2013.
33. Konak A., Coit D. W., Smith A. E., Multi-objective optimization using genetic algorithms: A tutorial, Reliability Engineering & System Safety, 91(9), 992-1007, 2006.
34. Blickle T., Thiele L., A comparison of selection schemes used in genetic algorithms, 1995.
35. Xie H., Zhang M., Andreae P., Johnston M., Is the not-sampled issue in tournament selection critical?, Evolutionary Computation, IEEE World Congress on Computational Intelligence, 3710-3717, 2008.
36. Brauers W. K. M., Zavadskas E. K., The MOORA method and its application to privatization in a transition economy, Control and Cybernetics, 35, 445-469, 2006.
37. Brauers W. K. M., Zavadskas E. K., Project management by MULTIMOORA as an instrument for transition economies, Technological and Economic Development of Economy, 16(1), 5-24, 2010.
38. Datta S., Sahu N., Mahapatra S., Robot selection based on grey-MULTIMOORA approach, Grey Systems: Theory and Application, 3(2), 201-232, 2013.
39. Kundakcı N., Combined multi-criteria decision making approach based on MACBETH and MULTI-MOORA methods, Alphanumeric Journal, 4(1), 17-26, 2016.
40. Brauers W. K. M., Zavadskas E. K., Robustness of MULTIMOORA: a method for multi-objective optimization, Informatica, 23(1), 1-25, 2012.
41. Brauers W. K. M., Kildienė S., Zavadskas E. K., Kaklauskas A., The construction sector in twenty European countries during the recession 2008–2009–country ranking by MULTIMOORA, International Journal of Strategic Property Management, 17(1), 58-78, 2013.
42. Brauers W. K. M., Zavadskas E. K., Kildienė S., Was the Construction Sector in 20 European Countries Anti-cyclical during the Recession Years 2008-2009 as Measured by Multicriteria Analysis (MULTIMOORA)?, Procedia Computer Science, 31, 949-956, 2014.
43. Veeraiah T., Pratapa Reddy Y., V S Mohan Kumar P., W D S Milton P., Optimization of Flow Shop Scheduling by MATLAB, SSRG International Journal of Mechanical Engineering (SSRG-IJME), 222-226, 2017.