首页 » 文章 » 文章详细信息
Computational Intelligence and Neuroscience Volume 2019 ,2019-09-16
A Db-Scan Binarization Algorithm Applied to Matrix Covering Problems
Research Article
José García 1 Paola Moraga 1 Matias Valenzuela 1 Broderick Crawford 1 Ricardo Soto 1 Hernan Pinto 1 Alvaro Peña 1 Francisco Altimiras 1 Gino Astorga 2
Show affiliations
DOI:10.1155/2019/3238574
Received 2019-06-17, accepted for publication 2019-08-04, Published 2019-08-04
PDF
摘要

The integration of machine learning techniques and metaheuristic algorithms is an area of interest due to the great potential for applications. In particular, using these hybrid techniques to solve combinatorial optimization problems (COPs) to improve the quality of the solutions and convergence times is of great interest in operations research. In this article, the db-scan unsupervised learning technique is explored with the goal of using it in the binarization process of continuous swarm intelligence metaheuristic algorithms. The contribution of the db-scan operator to the binarization process is analyzed systematically through the design of random operators. Additionally, the behavior of this algorithm is studied and compared with other binarization methods based on clusters and transfer functions (TFs). To verify the results, the well-known set covering problem is addressed, and a real-world problem is solved. The results show that the integration of the db-scan technique produces consistently better results in terms of computation time and quality of the solutions when compared with TFs and random operators. Furthermore, when it is compared with other clustering techniques, we see that it achieves significantly improved convergence times.

授权许可

Copyright © 2019 José García et al. 2019
This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

通讯作者

José García.Pontificia Universidad Católica de Valparíso, 2362807 Valparaíso, Chile, pucv.cl.jose.garcia@pucv.cl

推荐引用方式

José García,Paola Moraga,Matias Valenzuela,Broderick Crawford,Ricardo Soto,Hernan Pinto,Alvaro Peña,Francisco Altimiras,Gino Astorga. A Db-Scan Binarization Algorithm Applied to Matrix Covering Problems. Computational Intelligence and Neuroscience ,Vol.2019(2019)

您觉得这篇文章对您有帮助吗?
分享和收藏
0

是否收藏?

参考文献
[1] J. García, B. Crawford, R. Soto, C. Castro. et al.(2018). A k-means binarization framework applied to multidimensional knapsack problem. Applied Intelligence.48(2):357-380. DOI: 10.1016/j.swevo.2018.08.006.
[2] J. García, C. Pope, F. Altimiras. (2017). A distributed-means segmentation algorithm applied to lobesia botrana recognition. Complexity.2017-14. DOI: 10.1016/j.swevo.2018.08.006.
[3] N. Vecek, M. Mernik, B. Filipic, M. Xrepinsek. et al.(2016). Parameter tuning with chess rating system (crs-tuning) for meta-heuristic algorithms. Information Sciences.372:446-469. DOI: 10.1016/j.swevo.2018.08.006.
[4] J. Ries, P. Beullens. (2015). A semi-automated design of instance-based fuzzy parameter tuning for metaheuristics based on decision tree induction. Journal of the Operational Research Society.66(5):782-793. DOI: 10.1016/j.swevo.2018.08.006.
[5] Y. Zhou, N. Wang, W. Xiang. (2017). Clustering hierarchy protocol in wireless sensor networks using an improved pso algorithm. IEEE Access.5:2241-2253. DOI: 10.1016/j.swevo.2018.08.006.
[6] M. Jiang, J. Luo, D. Jiang, J. Xiong. et al.(2016). A cuckoo search-support vector machine model for predicting dynamic measurement errors of sensors. IEEE Access.4:5030-5037. DOI: 10.1016/j.swevo.2018.08.006.
[7] E. Boros, P. L. Hammer, T. Ibaraki, A. Kogan. et al.(1997). Logical analysis of numerical data. Mathematical Programming.79(1–3):163-190. DOI: 10.1016/j.swevo.2018.08.006.
[8] J. García, B. Crawford, R. Soto, G. Astorga. et al.(2019). A clustering algorithm applied to the binarization of swarm intelligence continuous metaheuristics. Swarm and Evolutionary Computation.44:646-664. DOI: 10.1016/j.swevo.2018.08.006.
[9] C. Mao, R. Lin, C. Xu, Q. He. et al.(2017). Towards a trust prediction framework for cloud services based on pso-driven neural network. IEEE Access.5:2187-2199. DOI: 10.1016/j.swevo.2018.08.006.
[10] R. Munoz, R. Olivares, C. Taramasco. (2018). Using black hole algorithm to improve eeg-based emotion recognition. Computational Intelligence and Neuroscience.2018-21. DOI: 10.1016/j.swevo.2018.08.006.
[11] X.-S. He, F. Wang, Y. Wang, X.-S. Yang. et al.(2018). Global convergence analysis of cuckoo search using markov theory. Nature-Inspired Algorithms and Applied Optimization. DOI: 10.1016/j.swevo.2018.08.006.
[12] R. S. Garfinkel, G. L. Nemhauser. (1972). Integer Programming. DOI: 10.1016/j.swevo.2018.08.006.
[13] B. Crawford, R. Soto, G. Astorga, J. García. et al.(2017). Putting continuous metaheuristics to work in binary search spaces. Complexity.2017-19. DOI: 10.1016/j.swevo.2018.08.006.
[14] H. Faris, I. Aljarah, S. Mirjalili. (2018). Improved monarch butterfly optimization for unconstrained global search and neural network training. Applied Intelligence.48(2):445-464. DOI: 10.1016/j.swevo.2018.08.006.
[15] M. R. Gary, D. S. Johnson. (1979). Computers and intractability. A Guide to the Theory of NP-Completeness. DOI: 10.1016/j.swevo.2018.08.006.
[16] H. Faris, M. A. Hassonah, A. M. Al-Zoubi, S. Mirjalili. et al.(2018). A multi-verse optimizer approach for feature selection and optimizing svm parameters based on a robust system architecture. Neural Computing and Applications.30(8):2355-2369. DOI: 10.1016/j.swevo.2018.08.006.
[17] P. S. Mann, S. Singh. (2017). Energy efficient clustering protocol based on improved metaheuristic in wireless sensor networks. Journal of Network and Computer Applications.83:40-52. DOI: 10.1016/j.swevo.2018.08.006.
[18] E. Balas, M. C. Carrera. (1996). A dynamic subgradient-based branch-and-bound procedure for set covering. Operations Research.44(6):875-890. DOI: 10.1016/j.swevo.2018.08.006.
[19] H. Kaur, J. Virmani, Kriti, S. Thakur. et al.(2019). Chapter 10—a genetic algorithm-based metaheuristic approach to customize a computer-aided classification system for enhanced screen film mammograms. U-Healthcare Monitoring Systems, Advances in Ubiquitous Sensing Applications for Healthcare:217-259. DOI: 10.1016/j.swevo.2018.08.006.
[20] R. d. A. Rosa, A. M. Machado, G. M. Ribeiro, G. R. Mauri. et al.(2016). A mathematical model and a clustering search metaheuristic for planning the helicopter transportation of employees to the production platforms of oil and gas. Computers & Industrial Engineering.101:303-312. DOI: 10.1016/j.swevo.2018.08.006.
[21] J. Kennedy, R. C. Eberhart. A discrete binary version of the particle swarm algorithm. :4104-4108. DOI: 10.1016/j.swevo.2018.08.006.
[22] A. D. de León, E. Lalla-Ruiz, B. Melián-Batista, J. Marcos Moreno-Vega. et al.(2017). A machine learning-based system for berth scheduling at bulk terminals. Expert Systems with Applications.87:170-182. DOI: 10.1016/j.swevo.2018.08.006.
[23] M. Neshat, G. Sepidnam, M. Sargolzaei, A. N. Toosi. et al.(2014). Artificial fish swarm algorithm: a survey of the state-of-the-art, hybridization, combinatorial and indicative applications. Artificial Intelligence Review.42(4):965-997. DOI: 10.1016/j.swevo.2018.08.006.
[24] T. Yalcinoz, H. Altun. (2001). Power economic dispatch using a hybrid genetic algorithm. IEEE Power Engineering Review.21(3):59-60. DOI: 10.1016/j.swevo.2018.08.006.
[25] X.-S. Yang, S. Deb. Cuckoo search via lévy flights. :210-214. DOI: 10.1016/j.swevo.2018.08.006.
[26] S. Asta, E. Ö.tae, T. Curtois. (2016). A tensor based hyper-heuristic for nurse rostering. Knowledge-based Systems.98:185-199. DOI: 10.1016/j.swevo.2018.08.006.
[27] L. Calvet, J. de Armas, D. Masip, A. A. Juan. et al.(2017). Learnheuristics: hybridizing metaheuristics with machine learning for optimization with dynamic inputs. Open Mathematics.15(1):261-280. DOI: 10.1016/j.swevo.2018.08.006.
[28] S. J. Nanda, G. Panda. (2014). A survey on nature inspired metaheuristic algorithms for partitional clustering. Swarm and Evolutionary Computation.16:1-18. DOI: 10.1016/j.swevo.2018.08.006.
[29] S. Martin, D. Ouelhadj, P. Beullens, E. Ozcan. et al.(2016). A multi-agent based cooperative approach to scheduling and routing. European Journal of Operational Research.254(1):169-178. DOI: 10.1016/j.swevo.2018.08.006.
[30] M. Ester, H.-P. Kriegel, J. Sander, X. Xu. et al.(1996). A density-based algorithm for discovering clusters in large spatial databases with noise. Kdd Knowledge Discovery and Data Mining.96:226-231. DOI: 10.1016/j.swevo.2018.08.006.
[31] R. Eberhart, J. Kennedy. A new optimizer using particle swarm theory. :39-43. DOI: 10.1016/j.swevo.2018.08.006.
[32] B. Crawford, R. Soto, N. Berríos. (2015). A binary cat swarm optimization algorithm for the non-unicost set covering problem. Mathematical Problems in Engineering.2015-8. DOI: 10.1016/j.swevo.2018.08.006.
[33] J. Borneman, M. Chrobak, G. Della Vedova, A. Figueroa. et al.(2001). Probe selection algorithms with applications in the analysis of microbial communities. Bioinformatics.17(1):S39-S48. DOI: 10.1016/j.swevo.2018.08.006.
[34] C. M. Bishop. (2006). Pattern Recognition and Machine Learning. DOI: 10.1016/j.swevo.2018.08.006.
[35] E. Balas, M. W. Padberg. (1976). Set partitioning: a survey. SIAM Review.18(4):710-760. DOI: 10.1016/j.swevo.2018.08.006.
[36] E. Chen, J. Li, X. Liu. (2011). In search of the essential binary discrete particle swarm. Applied Soft Computing.11(3):3260-3269. DOI: 10.1016/j.swevo.2018.08.006.
[37] J. García, B. Crawford, R. Soto, P. García. et al.A multi dynamic binary black hole algorithm applied to set covering problem. :42-51. DOI: 10.1016/j.swevo.2018.08.006.
[38] J. García, F. Altimiras, A. Peña, G. Astorga. et al.(2018). A binary cuckoo search big data algorithm applied to large-scale crew scheduling problems. Complexity.2018-15. DOI: 10.1016/j.swevo.2018.08.006.
[39] J. García, B. Crawford, R. Soto, G. Astorga. et al.A percentile transition ranking algorithm applied to binarization of continuous swarm intelligence metaheuristics. :3-13. DOI: 10.1016/j.swevo.2018.08.006.
[40] Z.-q. Li, H.-l. Zhang, J.-h. Zheng, M.-j. Dong. et al.Heuristic evolutionary approach for weighted circles layout. :324-331. DOI: 10.1016/j.swevo.2018.08.006.
[41] G. Pampara. (2012). Angle modulated population based algorithms to solve binary problems. . DOI: 10.1016/j.swevo.2018.08.006.
[42] B. Yelbay, Ş. İ. Birbil, K. Bülbül. (2015). The set covering problem revisited: an empirical study of the value of dual information. Journal of Industrial & Management Optimization.11(2):575-594. DOI: 10.1016/j.swevo.2018.08.006.
[43] D. Karaboga. (2005). An Idea Based on Honey Bee Swarm for Numerical Optimization. DOI: 10.1016/j.swevo.2018.08.006.
[44] Z. W. Geem, J. H. Kim, G. V. Loganathan. (2001). A new heuristic optimization algorithm: harmony search. Simulation.76(2):60-68. DOI: 10.1016/j.swevo.2018.08.006.
[45] D. E. Golberg. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. DOI: 10.1016/j.swevo.2018.08.006.
[46] J.-S. Chou, T.-K. Nguyen. (2018). Forward forecast of stock price using sliding-window metaheuristic-optimized machine-learning regression. IEEE Transactions on Industrial Informatics.14(7):3132-3142. DOI: 10.1016/j.swevo.2018.08.006.
[47] A. Caprara, M. Fischetti, P. Toth. (1999). A heuristic method for the set covering problem. Operations Research.47(5):730-743. DOI: 10.1016/j.swevo.2018.08.006.
[48] G. Zhang. (2011). Quantum-inspired evolutionary algorithms: a survey and empirical study. Journal of Heuristics.17(3):303-351. DOI: 10.1016/j.swevo.2018.08.006.
[49] B. J. Leonard, A. P. Engelbrecht, C. W. Cleghorn. (2015). Critical considerations on angle modulated particle swarm optimisers. Swarm Intelligence.9(4):291-314. DOI: 10.1016/j.swevo.2018.08.006.
[50] S. Saremi, S. Mirjalili, A. Lewis. (2015). How important is a transfer function in discrete heuristic algorithms. Neural Computing and Applications.26(3):625-640. DOI: 10.1016/j.swevo.2018.08.006.
[51] J.-S. Chou, A.-D. Pham. (2017). Nature-inspired metaheuristic optimization in least squares support vector regression for obtaining bridge scour information. Information Sciences.399:64-80. DOI: 10.1016/j.swevo.2018.08.006.
[52] S. Ceria, P. Nobili, A. Sassano. (1998). A Lagrangian-based heuristic for large-scale set covering problems. Mathematical Programming.81(2):215-228. DOI: 10.1016/j.swevo.2018.08.006.
[53] R. J. Kuo, T. C. Lin, F. E. Zulvia, C. Y. Tsai. et al.(2018). A hybrid metaheuristic and kernel intuitionistic fuzzy c-means algorithm for cluster analysis. Applied Soft Computing.67:299-308. DOI: 10.1016/j.swevo.2018.08.006.
[54] M. J. Brusco, L. W. Jacobs, G. M. Thompson. (1999). A morphing procedure to supplement a simulated annealing heuristic for cost-andcoverage-correlated set-covering problems. Annals of Operations Research.86:611-627. DOI: 10.1016/j.swevo.2018.08.006.
[55] O. Ö. Özener, M. Örmeci Matoğlu, G. Erdoğan, M. Haouari. et al.(2017). Solving a large-scale integrated fleet assignment and crew pairing problem. Annals of Operations Research.253(1):477-500. DOI: 10.1016/j.swevo.2018.08.006.
[56] C. Valenzuela, B. Crawford, R. Soto, E. Monfroy. et al.(2014). A 2-level metaheuristic for the set covering problem. International Journal of Computers Communications & Control.7(2):377-387. DOI: 10.1016/j.swevo.2018.08.006.
[57] J. E. Beasley. (1990). A Lagrangian heuristic for set-covering problems. Naval Research Logistics.37(1):151-164. DOI: 10.1016/j.swevo.2018.08.006.
[58] E.-G. Talbi. (2016). Combining metaheuristics with mathematical programming, constraint programming and machine learning. Annals of Operations Research.240(1):171-215. DOI: 10.1016/j.swevo.2018.08.006.
[59] J. E. Beasley. (1987). An algorithm for set covering problem. European Journal of Operational Research.31(1):85-93. DOI: 10.1016/j.swevo.2018.08.006.
[60] A. A. Juan, J. Faulin, S. E. Grasman, M. Rabe. et al.(2015). A review of simheuristics: extending metaheuristics to deal with stochastic combinatorial optimization problems. Operations Research Perspectives.2:62-72. DOI: 10.1016/j.swevo.2018.08.006.
[61] Y. Yang, Y. Mao, P. Yang, Y. Jiang. et al.The unit commitment problem based on an improved firefly and particle swarm optimization hybrid algorithm. :718-722. DOI: 10.1016/j.swevo.2018.08.006.
[62] S. Jütte, D. Müller, U. W. Thonemann. (2017). Optimizing railway crew schedules with fairness preferences. Journal of Scheduling.20(1):43-55. DOI: 10.1016/j.swevo.2018.08.006.
[63] W. Liu, L. Liu, D. Cartes. Angle Modulated Particle Swarm Optimization Based Defensive Islanding of Large Scale Power Systems. :1-8. DOI: 10.1016/j.swevo.2018.08.006.
[64] M. Horváth, T. Kis. (2019). Computing strong lower and upper bounds for the integrated multiple-depot vehicle and crew scheduling problem with branch-and-price. Central European Journal of Operations Research.27(1):39-67. DOI: 10.1016/j.swevo.2018.08.006.
[65] D. Swagatam, M. Rohan, K. Rupam. Multi-user detection in multi-carrier cdma wireless broadband system using a binary adaptive differential evolution algorithm. :1245-1252. DOI: 10.1016/j.swevo.2018.08.006.
[66] A.-D. Pham, N.-D. Hoang, Q.-T. Nguyen. (2015). Predicting compressive strength of high-performance concrete using metaheuristic-optimized least squares support vector regression. Journal of Computing in Civil Engineering.30(3). DOI: 10.1016/j.swevo.2018.08.006.
[67] K. Hoffmann, U. Buscher. (2019). Valid inequalities for the arc flow formulation of the railway crew scheduling problem with attendance rates. Computers & Industrial Engineering.127:1143-1152. DOI: 10.1016/j.swevo.2018.08.006.
[68] J.-S. Chou, J. P. P. Thedja. (2016). Metaheuristic optimization within machine learning-based classification system for early warnings related to geotechnical problems. Automation in Construction.68:65-80. DOI: 10.1016/j.swevo.2018.08.006.
[69] D. Zakaria, D. A. Cartes. (2015). Angle Modulated Particle Swarm Optimization Based Defensive Islanding of Large Scale Power Systems. Computer Science and Its Applications.456:3-14. DOI: 10.1016/j.swevo.2018.08.006.
[70] M. Göçken, M. Özçalıcı, A. Boru, A. T. Dosdoğru. et al.(2016). Integrating metaheuristics and artificial neural networks for improved stock price prediction. Expert Systems with Applications.44:320-331. DOI: 10.1016/j.swevo.2018.08.006.
[71] J. E. Beasley, P. C. Chu. (1996). A genetic algorithm for the set covering problem. European Journal of Operational Research.94(2):392-404. DOI: 10.1016/j.swevo.2018.08.006.
[72] M. Caserta, S. Voß. (2009). Matheuristics: hybridizing metaheuristics and mathematical programming. Metaheuristics: Intelligent Problem Solving. DOI: 10.1016/j.swevo.2018.08.006.
文献评价指标
浏览 750次
下载全文 12次
评分次数 0次
用户评分 0.0分
分享 0次