Volume 19, Issue 2 (9-2022)                   JSDP 2022, 19(2): 87-106 | Back to browse issues page


XML Persian Abstract Print


Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:

Omidvar M, Nejatian S, Parvin H, Bagherifard K, Rezaie V. Providing an algorithm for solving general optimization problems based on Domino theory. JSDP 2022; 19 (2) : 7
URL: http://jsdp.rcisp.ac.ir/article-1-1094-en.html
Abstract:   (934 Views)
Optimization is a very important process in engineering. Engineers can create better production only if they make use of optimization tools in reduction of its costs including consumption time. Many of the engineering real-word problems are of course non-solvable mathematically (by mathematical programming solvers). Therefore, meta-heuristic optimization algorithms are needed to solve these problems. Based on this assumption, many new meta-heuristic optimization algorithms have been proposed inspired by natural phenomena, such as IWO [58], BBO [59], WWO [61], and so on. Inspired by domino toppling theory, we proposed an optimization algorithm. Using domino pieces, we can create countless complex structures. To simulate the domino movement in the search space of a problem, we consider the particles in the search space as the domino pieces and, by creating an optimal path, we will try to direct the dominoes to the optimal path. The optimal paths will be updated in each iteration. After initializing the dominoes randomly at the beginning of each evaluation, the picking piece or the first moving piece will be identified and then the particles will be selected by the optimal path. Applying a motion equation to each domino will move the dominoes forward in that direction. At first, a predefined dominoes will be randomly distributed in the problem space. Choosing the optimal path will accelerate the convergence of the domino particles towards the target. After choosing the path in current iteration, we now have to do the domino movement. The particles will move to a new location by applying the new location equation. By applying this equation, each domino piece will sit on the track ahead of itself. The front piece will also move to a new location by applying an equation separate from the rest. After moving the dominoes to the new location, the worst iteration of the previous iteration will be removed from the problem space. In the new iteration, the optimal domino path, the new locations of domino pieces and the global optimum will be updated. At the end of the algorithm, the global optimum will be determined as the optimal solution. This method is implemented in a simulator environment.
To evaluate the performance of the Domino Optimization algorithm, we use a complete benchmark including 30 objective functions called CEC 2014 [67] that are single-objective numerical functions. In all cases, we set the population size to 50, the dimension size to 30, and the number of fitness function evaluation to 150,000. We compare the proposed Domino Optimization algorithm (DO) with the algorithms LOA [57], ICS [62], NPSO [63], MOHS [64], BCSO [65] and FFFA [66]. The results obtained from the 3 unimodal functions show that the proposed method is able to achieve a better solution than any of the state of the art algorithms at the equal resources. Results in the multimodal functions show that the proposed method has the best performance in finding the optimal solution in all of the available 13 functions in this section. In all of 6 functions in the hybrid section, the quality of the proposed method is better than all of the state of the art algorithms at the equal resources. The standard deviation values ​​of the proposed method, which are often small numbers, indicate algorithm convergence around the optimal solution. Also among the available methods, two algorithms, named NPSO and LOA, have good results after the proposed method. In the convergence analysis of dominoes, the diversity of objective functions in 100 distinct iterations shows a big value at the beginning of the algorithm, and a low value at the end of the algorithm.
Article number: 7
Full-Text [PDF 3653 kb]   (521 Downloads)    
Type of Study: Research | Subject: Paper
Received: 2019/12/4 | Accepted: 2020/08/18 | Published: 2022/09/30 | ePublished: 2022/09/30

References
1. [1] Haupt R. L.; Haupt S. E, "Practical Genetic Algorithms," 2nd Edition, John Wiley & Sons Inc, 2004. [DOI:10.1002/0471671746]
2. [2] S. B. L. Vandenberghe, "Convex Optimization," Cambridge University Press, 2004.
3. [3] W. Sun, Y. Yuan, "Optimization Theory and Methods: Nonlinear Programming," Springer Science + Business Media, LLC Press, 2006.
4. [4] J. Nocedal, S. J. Wright, "Numerical Optimization," 2nd Edition, Springer Science + Business Media, LLC Press,2006.
5. [5] J. Holland," Genetic algorithms and the optimal allocation of trials", SIAM J. Comput, Vol.2 , pp. 88-105, 1979. [DOI:10.1137/0202009]
6. [6] J. Kennedy, R. Eberhart, "Particle Swarm Optimization" , Proceedings of IEEE International Conference on Neural Networks, 1995, pp. 1942-1948.
7. [7] D. Karaboga, B. Basturk, "A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm", Journal of Global Optimization, vol. 39 , pp. 459-471, 2007. [DOI:10.1007/s10898-007-9149-x]
8. [8] M. Dorigo, V. Maniezzo, A. Colorni, "Ant System: Optimization by a colony of cooperating agents", IEEE Transactions on Systems, Man, and Cybernetics - Part B, vol.26, pp. 29-41, 1996. [DOI:10.1109/3477.484436] [PMID]
9. [9] S. Kirkpatrick, C.D. Gelatt, M.P. Vecchi, "Optimization by simulated annealing", Science vol.220, pp. 671-680 ,1983. [DOI:10.1126/science.220.4598.671] [PMID]
10. [10] F.W. Glover, "Tabu search: A tutorial", Interfaces, vol. 20, pp.74-94, 1990. [DOI:10.1287/inte.20.4.74]
11. [11] D. T. Pham, S. Otri, A. Afify, M. Mahmuddin, , H. Al-Jabbouli, "Data clustering using the bees algorithm", 40th CIRP International Seminar on Manufacturing Systems, p. p. s.p., 2007.
12. [12] X. Miao, J. Chu, , L. Zhang, J. Qiao, "An Evolutionary Neural Network Approach to Simple Prediction of Dam Deformation", Journal of Information & Computational Science, vol.10 , pp.315-1324, 2013. [DOI:10.12733/jics20101559]
13. [13] Z.W. Geem, J. H. Kim, and G. V. Loganathan, "A new heuristic optimization algorithm: harmony search," Simulation, vol. 76, no. 2, pp. 60-68, 2001. [DOI:10.1177/003754970107600201]
14. [14] R. P. Feynman, "Simulating physics with computers," International Journal of Theoretical Physics, vol. 21, no. 6-7, pp. 467-488, 1982. [DOI:10.1007/BF02650179]
15. [15] R. P. Feynman, "Quantummechanical computers," Foundations of Physics, vol. 16, no. 6, pp. 507-531, 1986. [DOI:10.1007/BF01886518]
16. [16] A. Narayanan and M.Moore, "Quantum-inspired genetic algorithms," in Proceedings of the IEEE International Conference on Evolutionary Computation (ICEC '96), May 1996, pp. 61-66.
17. [17] J. Sun,W.Xu, and B. Feng, "Aglobal search strategy of quantumbehaved particle swarm optimization," in Proceedings of the 2004 IEEE Conference on Cybernetics and Intelligent Systems, vol. 1, December 2004, pp. 111-116.
18. [18] Y. Wang, X. Feng, Y. Huang et al., "A novel quantum swarm evolutionary algorithm and its applications," Neurocomputing, vol. 70, no. 4-6, pp. 633-640, 2007. [DOI:10.1016/j.neucom.2006.10.001]
19. [19] S. I. Birbil and S. Fang, "An electromagnetism-like mechanism for global optimization," Journal of Global Optimization, vol. 25, no. 3, pp. 263-282, 2003. [DOI:10.1023/A:1022452626305]
20. [20] O. K. Erol and I. Eksin, "A new optimizationmethod: Big Bang-Big Crunch," Advances in Engineering Software, vol. 37, no. 2, pp.106-111, 2006. [DOI:10.1016/j.advengsoft.2005.04.005]
21. [21] R. A. Formato, "Central force optimization: a new metaheuristic with applications in applied electromagnetics," Progress in Electromagnetics Research, vol. 77, pp. 425-491, 2007. [DOI:10.2528/PIER07082403]
22. [22] E. Rashedi, H. Nezamabadi-Pour, and S. Saryazdi, "GSA: a gravitational search algorithm," Information Sciences, vol. 179, no. 13, pp. 2232-2248, 2009. [DOI:10.1016/j.ins.2009.03.004]
23. [23] L. Xie, J. Zeng, and Z. Cui, "General framework of artificial physics optimization algorithm," in Proceedings of the World Congress on Nature and Biologically Inspired Computing (NaBIC '09), IEEE, December 2009, pp. 1321-1326.
24. [24] J. Flores, R. L'opez, and J. Barrera, "Gravitational interactions optimization," in Learning and Intelligent Optimization, pp. 226-237, Springer, Berlin, Germany, 2011. [DOI:10.1007/978-3-642-25566-3_17]
25. [25] K. F. P'al, "Hysteretic optimization for the Sherrington-Kirkpatrick spin glass," Physica A, vol. 367, pp. 261-268, 2006. [DOI:10.1016/j.physa.2005.11.013]
26. [26] A. Kaveh and S. Talatahari, "A novel heuristic optimization method: charged system search," Acta Mechanica, vol. 213, no.3, pp. 267-289, 2010. [DOI:10.1007/s00707-009-0270-4]
27. [27] H. Shah-Hosseini, "Principal components analysis by the galaxy-based search algorithm: a novel metaheuristic for continuous optimisation," International Journal of Computational Science and Engineering, vol. 6, no. 1-2, pp. 132-140, 2011. [DOI:10.1504/IJCSE.2011.041221]
28. [28] L. Jiao, Y. Li, M. Gong, and X. Zhang, "Quantum-inspired immune clonal algorithm for global optimization," IEEE Transactions on Systems, Man, and Cybernetics B, vol. 38, no. 5, pp. 1234-1253, 2008. [DOI:10.1109/TSMCB.2008.927271] [PMID]
29. [29] W. Li, Q. Yin, and X. Zhang, "Continuous quantum ant colony optimization and its application to optimization and analysis of induction motor structure," in Proceedings of the IEEE 5th International Conference on Bio-Inspired Computing: Theories and Applications (BIC-TA '10), September 2010, pp. 313-317.
30. [30] Y. Zhang, L.Wu, Y. Zhang, and J.Wang, "Immune gravitation inspired optimization algorithm," in Advanced Intelligent Computing, pp. 178-185, Springer, Berlin,Germany, 2012. [DOI:10.1007/978-3-642-24728-6_24]
31. [31] A. Layeb, S. Meshoul, and M. Batouche, "quantum genetic algorithm for multiple RNA structural alignment," in Proceedings of the 2nd Asia International Conference on Modelling and Simulation (AIMS '08), May 2008, pp. 873-878. [DOI:10.1109/AMS.2008.151]
32. [32] D. Chang and Y. Zhao, "A dynamic niching quantum genetic algorithm for automatic evolution of clusters," in Proceedings of the 14th International Conference on Computer Analysis of Images and Patterns, vol. 22011, pp. 308-315. [DOI:10.1007/978-3-642-23678-5_36]
33. [33] J. Xiao, Y. Yan, Y. Lin, L. Yuan, and J. Zhang, "A quantuminspired genetic algorithm for data clustering," in Proceedings of the IEEE Congress on Evolutionary Computation (CEC '08), June 2008, pp. 1513-1519.
34. [34] H. Talbi, A. Draa, and M. Batouche, "A new quantum-inspired genetic algorithm for solving the travelling salesman problem," in Proceedings of the IEEE International Conference on Industrial Technology (ICIT '04), vol. 3, December 2004 , pp. 1192-1197.
35. [35] K.-H. Han, K.-H. Park, C.-H. Lee, and J.-H. Kim, "Parallel quantum-inspired genetic algorithm for combinatorial optimization problem," in Proceedings of the 2001 Congress on Evolutionary Computation, vol. 2, IEEE, May 2001, pp. 1422-1429.
36. [36] L. Yan, H. Chen, W. Ji, Y. Lu, and J. Li, "Optimal VSM model and multi-object quantum-inspired genetic algorithm for web information retrieval," in Proceedings of the 1st International Symposium on Computer Network and Multimedia Technology (CNMT '09), IEEE, December 2009, pp. 1-4. [DOI:10.1109/CNMT.2009.5374788]
37. [37] Z.Mo, G. Wu, Y. He, and H. Liu, "quantum genetic algorithm for scheduling jobs on computational grids," in Proceedings of the International Conference on Measuring Technology and Mechatronics Automation (ICMTMA '10), March 2010, pp. 964-967. [DOI:10.1109/ICMTMA.2010.505] [PMID]
38. [38] Y. Zhang, J. Liu, Y. Cui, X. Hei, and M. Zhang, "An improved quantumgenetic algorithmfor test suite reduction," in Proceedings of the IEEE International Conference on Computer Science and Automation Engineering (CSAE '11), June 2011, pp. 149-153. [DOI:10.1109/CSAE.2011.5952443]
39. [39] J. Lee,W. Lin, G. Liao, and T. Tsao, "quantum genetic algorithm for dynamic economic dispatch with valve-point effects and including wind power system," International Journal of Electrical Power and Energy Systems, vol. 33, no. 2, pp. 189-197, 2011. [DOI:10.1016/j.ijepes.2010.08.014]
40. [40] J. Dai and H. Zhang, "A novel quantum genetic algorithm for area optimization of FPRM circuits," in Proceedings of the 3rd International Symposium on Intelligent Information Technology Application (IITA 09), November 2009, pp. 408-411. [DOI:10.1109/IITA.2009.454] [PMID]
41. [41] L. Chuang, Y. Chiang, and C. Yang, "A quantum genetic algorithm for operon prediction," in Proceedings of the IEEE 26th International Conference on Advanced Information Networking and Applications (AINA '12 ), March 2012, pp. 269-275. [DOI:10.1109/AINA.2012.117]
42. [42] H. Xing, X. Liu, X. Jin, L. Bai, and Y. Ji, "A multi-granularity evolution based quantum genetic algorithm for QoS multicast routing problem in WDM networks," Computer Communications, vol. 32, no. 2, pp. 386-393, 2009. [DOI:10.1016/j.comcom.2008.11.009]
43. [43] W. Luo, "A quantum genetic algorithm based QoS routing protocol for wireless sensor networks," in Proceedings of the IEEE International Conference on Software Engineering and Service Sciences (ICSESS '10), IEEE, July 2010, pp. 37-40. [DOI:10.1109/ICSESS.2010.5552333]
44. [44] J. Wang and R. Zhou, "A novel quantum genetic algorithm for PID controller," in Proceedings of the 6th International Conference on Advanced Intelligent Computing Theories and Applications: Intelligent Computing, 2010, pp. 72-77. [DOI:10.1007/978-3-642-14922-1_10]
45. [45] B.Han, J. Jiang, Y.Gao, and J.Ma, "Aquantumgenetic algorithm to solve the problem of multivariate," Communications in Computer and Information Science, vol. 243, no. 1, pp. 308-314, 2011. [DOI:10.1007/978-3-642-27503-6_42]
46. [46] Y. Zheng, J. Liu, W. Geng, and J. Yang, "Quantum-inspired genetic evolutionary algorithm for course timetabling," in Proceedings of the 3rd International Conference on Genetic and Evolutionary Computing (WGEC '09), October 2009, pp. 750-753. [DOI:10.1109/WGEC.2009.164] [PMID]
47. [47] X. J. Zhang, S. Li, Y. Shen, and S. M. Song, "Evaluation of several quantum genetic algorithms in medical image registration applications," in Proceedings of the IEEE International Conference on Computer Science and Automation Engineering (CSAE '12), vol. 2, IEEE, 2012, pp. 710-713. [DOI:10.1109/CSAE.2012.6272866]
48. [48] H. Talbi, A. Draa, and M. Batouche, "A new quantum-inspired genetic algorithm for solving the travelling salesman problem," in Proceedings of the IEEE International Conference on Industrial Technology (ICIT '04), December 2004, pp. 1192-1197.
49. [49] S. Bhattacharyya and S. Dey, "An efficient quantum inspired genetic algorithm with chaotic map model based interference and fuzzy objective function for gray level image thresholding," in Proceedings of the International Conference on Computational Intelligence and Communication Systems (CICN '11), IEEE, October 2011, pp. 121-125. [DOI:10.1109/CICN.2011.24] [PMID]
50. [50] K. Benatchba, M. Koudil, Y. Boukir, and N. Benkhelat, "Image segmentation using quantum genetic algorithms," in Proceedings of the 32nd Annual Conference on IEEE Industrial Electronics (IECON '06), IEEE, November 2006, pp. 3556-3562. [DOI:10.1109/IECON.2006.347758]
51. [51] M. Liu, C. Yuan, and T. Huang, "A novel real-coded quantum genetic algorithm in radiation pattern synthesis for smart antenna," in Proceedings of the IEEE International Conference on Robotics and Biomimetics (ROBIO '07), IEEE, December 2007, pp. 2023-2026. [DOI:10.1109/ROBIO.2007.4522478]
52. [52] R. Popa, V. Nicolau, and S. Epure, "A new quantum inspired genetic algorithm for evolvable hardware," in Proceedings of the 3rd International Symposium on Electrical and Electronics Engineering (ISEEE '10), September 2010, pp. 64-69. [DOI:10.1109/ISEEE.2010.5628539] [PMID]
53. [53] H. Yu and J. Fan, "Parameter optimization based on quantum genetic algorithm for generalized fuzzy entropy thresholding segmentation method," in Proceedings of the 5th International Conference on Fuzzy Systems and Knowledge Discovery (FSKD '08), vol. 1, IEEE, October 2008. pp. 530-534. [DOI:10.1109/FSKD.2008.454] [PMCID]
54. [54] P. C. Shill,M. F. Amin, M. A. H. Akhand, and K.Murase, "Optimization of interval type-2 fuzzy logic controller using quantum genetic algorithms," in Proceedings of the IEEE International Conference on Fuzzy Systems (FUZZ-IEEE '12), June 2012, pp. 1-8. [DOI:10.1109/FUZZ-IEEE.2012.6251207]
55. [55] M. Cao and F. Shang, "Training of process neural networks based on improved quantum genetic algorithm," in Proceedings of the WRI World Congress on Software Engineering (WCSE'09), vol. 2, May 2009, pp. 160-165. [DOI:10.1109/WCSE.2009.127]
56. [56] Y. Sun and M. Ding, "quantum genetic algorithm for mobile robot path planning," in Proceedings of the 4th International Conference on Genetic and Evolutionary Computing (ICGEC'10), December 2010, pp. 206-209.
57. [57] M. Yazdani, F. Jolaei, "Lion Optimization Algorithm (LOA) : Anature-inspired meta heuristic algorithm," Journal of Computational Designand Engineering, pp.24-36, 2016. [DOI:10.1016/j.jcde.2015.06.003]
58. [58] A.R. Mehrabian, C. Lucas, "A novel numerical optimization algorithm inspired from weed colonization", Ecol. Inform, vol.1(4), pp.355-66, 2006. [DOI:10.1016/j.ecoinf.2006.07.003]
59. [59] D. Simon "Biogeography-based optimization," Evolut, Comput.IEEE, Trans, vol.12(6), pp.702-13, 2008. [DOI:10.1109/TEVC.2008.919004]
60. [60] Yang X-S. "A new meta heuristicbat-inspired algorithm. Nature Inspired Cooperative Strategies for Optimization", NICSO 2010, Springer; pp. 65-74, 2010. [DOI:10.1007/978-3-642-12538-6_6]
61. [61] Y-J. Zheng,"Water wave optimization :a new nature-inspired meta heuristic," Comput. Oper.Res, pp. 55:1-11, 2014. [DOI:10.1016/j.cor.2014.10.008]
62. [62] J. Wang, B. Zhou, Sh. Zhou, "An Improved Cuckoo Search Optimization Algorithm for the Problem of Chaotic Systems Parameter Estimation," Hindawi Publishing Corporation Computational Intelligence and Neuroscience, Vol. 2016, pp. 8, 2016. [DOI:10.1155/2016/2959370] [PMID] [PMCID]
63. [63] Ch-F. Wang, K. Liu, "A Novel Particle Swarm Optimization Algorithm for Global Optimization," Hindawi Publishing Corporation Computational Intelligence and Neuroscience, V. 2016, pp. 9, 2016. [DOI:10.1155/2016/9482073] [PMID] [PMCID]
64. [64] C. Cubukcuoglu, I. Chatzikonstantinou, M. Fatih Tasgetiren, S. Sariyildiz, Q-K. Pan, "A Multi-Objective Harmony Search Algorithm for Sustainable Design of Floating Settlements," Algorithms 2016, 9, 51; doi:10.3390/a9030051, 2016. [DOI:10.3390/a9030051]
65. [65] I. Obagbuwa, A. Philips Abidoye, "Binary Cockroach Swarm Optimization for Combinatorial Optimization Problem," Algorithms 2016, 9, 59; doi:10.3390/a9030059, 2016. [DOI:10.3390/a9030059]
66. [66] R M. Rizk Allah, "Hybridization of Fruit Fly Optimization Algorithm and Firefly Algorithm for Solving Nonlinear Programming Problems," International Journal of Swarm Intelligence and Evolutionary Computation, http://dx.doi.org/10.4172/2090-4908.1000134, 2016. [DOI:10.4172/2090-4908.1000134]
67. [67] J., Liang, B. Qu, and P. Suganthan Problem definitions and evaluation criteria for the CEC 2014 special session and competition on single objective real-parameter numerical optimization, Computational Intelligence Laboratory,2013.
68. [68] M., Yasrebi, A., Eskandar-Baghban, H., Parvin, M., Mohammadpour, "Optimization inspiring from behavior of raining in nature: droplet optimization algorithm," International Journal of Bio-Inspired Computation, Vol.12, no.3, pp. 152-163, 2018. [DOI:10.1504/IJBIC.2018.094616]
69. [69] K., Pytel, "Hybrid Multi-Evolutionary Algorithm to Solve Optimization Problems," Applied Artificial Intelligence, Published online: 24 Feb 2020, Pages, 550-563, DOI: 10.1080/08839514.2020.1730631 [DOI:10.1080/08839514.2020.1730631]
70. [70] H., Parvin, S., Nejatian M., Mohammadpour, "Explicit memory based ABC with a clustering strategy for updating and retrieval of memory in dynamic environments," Applied Intelligence, Volume 48 , V, 11., pages, 4317-4337, doi: https://doi.org/10.1007/s10489-018-1197-z [DOI:10.1007/s10489-018-1197-z, 2018.]
71. [71] X., Qian, X., Wang, Y., Su and L., He, 2018. An effective hybrid evolutionary algorithm for solving the numerical optimization problems. Journal of Physics: Conference Series 1004 (1): article id. 012020. doi:10.1088/1742-6596/1004/1/012020. [DOI:10.1088/1742-6596/1004/1/012020]
72. [72] X., Donga, Yongle., C, "A novel genetic algorithm for large scale colored balanced traveling salesman problem," [DOI:10.1016/j.future.2018.12.06.]
73. [73] C., HyukGeun, K., Jinhyun, Y,. Yourim., M., Byung-Ro, "Investigation of incremental hybrid genetic algorithm with subgraph isomorphism problem, " Swarm and Evolutionary Computation, vol.49, pp.75-86, 2019. [DOI:10.1016/j.swevo.2019.05.004]
75. [75] M. moradi, S. nejatian , H. parvin , K. A. Bagherifard and V.rezaie , "Clustering and Memory-based Parent-Child Swarm Meta-heuristic Algorithm for Dynamic Optimization", JSDP, vol. 18, no. 3, pp. 127-146,2021.

Add your comments about this article : Your username or Email:
CAPTCHA

Send email to the article author


Rights and permissions
Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

© 2015 All Rights Reserved | Signal and Data Processing