×

Chunking and cooperation in particle swarm optimization for feature selection. (English) Zbl 07570859

Summary: Bio-inspired optimization aims at adapting observed natural behavioral patterns and social phenomena towards efficiently solving complex optimization problems, and is nowadays gaining much attention. However, researchers recently highlighted an inconsistency between the need in the field and the actual trend. Indeed, while nowadays it is important to design innovative contributions, an actual trend in bio-inspired optimization is to re-iterate the existing knowledge in a different form. The aim of this paper is to fill this gap. More precisely, we start first by highlighting new examples for this problem by considering and describing the concepts of chunking and cooperative learning. Second, by considering particle swarm optimization (PSO), we present a novel bridge between these two notions adapted to the problem of feature selection. In the experiments, we investigate the practical importance of our approach while exploring both its strength and limitations. The results indicate that the approach is mainly suitable for large datasets, and that further research is needed to improve the computational efficiency of the approach and to ensure the independence of the sub-problems defined using chunking.

MSC:

68Txx Artificial intelligence

Software:

MCPSO; WOA; PySwarms; POPMUSIC
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Kar, AK, Bio inspired computing – a review of algorithms and scope of applications, Expert Syst. Appl., 59, 20-32 (2016) · doi:10.1016/j.eswa.2016.04.018
[2] Dokeroglu, T.; Sevinc, E.; Kucukyilmaz, T.; Cosar, A., A survey on new generation metaheuristic algorithms, Computers & Industrial Engineering, 137, 106040 (2019) · doi:10.1016/j.cie.2019.106040
[3] Glover, F.; Sörensen, K., Metaheuristics, Scholarpedia, 10, 4, 6532 (2015) · doi:10.4249/scholarpedia.6532
[4] Yang, X-S, Recent advances in swarm intelligence and evolutionary computation (2015), Berlin: Springer International Publishing, Berlin
[5] Caserta, M., Voß, S: Metaheuristics: Intelligent problem solving. In: Matheuristics, pp. 1-38. Springer US. doi:10.1007/978-1-4419-1306-7_1 (2009)
[6] Abdelhafez, A.; Luque, G.; Alba, E., Parallel execution combinatorics with metaheuristics: Comparative study, Swarm and Evolutionary Computation, 55, 100692 (2020) · doi:10.1016/j.swevo.2020.100692
[7] Sörensen, K., Metaheuristics-the metaphor exposed, Int. Trans. Oper. Res., 22, 1, 3-18 (2013) · Zbl 1309.90127 · doi:10.1111/itor.12001
[8] Del Ser, J.; Osaba, E.; Molina, D.; Yang, X-S; Salcedo-Sanz, S.; Camacho, D.; Das, S.; Suganthan, PN; Coello, CAC; Herrera, F., Bio-inspired computation: Where we stand and what’s next, Swarm and Evolutionary Computation, 48, 220-250 (2019) · doi:10.1016/j.swevo.2019.04.008
[9] Villalón, C L C, Stützle, T., Dorigo, M.: Grey wolf, firefly and bat algorithms: Three widespread algorithms that do not contain any novelty. In: Lecture Notes in Computer Science, 12421, pp. 121-133, Springer International Publishing. doi:10.1007/978-3-030-60376-2_10 (2020)
[10] de Armas, J., Lalla-Ruiz, E., Tilahun, S.L., Voß, S: Similarity in metaheuristics: a gentle step towards a comparison methodology. Nat. Comput., pp. 1-23, doi:10.1007/s11047-020-09837-9 (2021)
[11] Reid, C.: Cooperation vs. competition in a technological environment. Ph.D. Thesis, University of Queensland Library. doi:10.14264/uql.2017.194 (2016)
[12] Kennedy, J., Eberhart, R.: Particle swarm optimization. In: Proceedings of ICNN’95 - International Conference on Neural Networks, IEEE. doi:10.1109/icnn.1995.488968 (1995)
[13] Kennedy, J., Eberhart, R.C.: A discrete binary version of the particle swarm algorithm. In: IEEE international conference on systems, man, and cybernetics. computational cybernetics and simulation, IEEE. doi:10.1109/icsmc.1997.637339 (1997)
[14] Guyon, I.; Elisseeff, A., An introduction to variable and feature selection, J. Mach. Learn. Res., 3, 1157-1182 (2003) · Zbl 1102.68556 · doi:10.1162/153244303322753616
[15] Hall, M.A.: Correlation-based feature selection for machine learning. Ph.D. Thesis, University of Waikato (1999)
[16] Bommert, A.; Sun, X.; Bischl, B.; Rahnenführer, J.; Lang, M., Benchmark for filter methods for feature selection in high-dimensional classification data, Computational Statistics & Data Analysis, 143, 106839 (2020) · Zbl 1510.62019 · doi:10.1016/j.csda.2019.106839
[17] Raza, M.S., Qamar, U.: Introduction to feature selection. In: Understanding and Using Rough Set Based Feature Selection: Concepts, Techniques and Applications, pp. 1-25, Springer Singapore. doi:10.1007/978-981-10-4965-1_1 (2019)
[18] Sarhani, M., Voß, S: PSO-based cooperative learning using chunking. In: Lecture Notes in Computer Science, 12096, pp. 278-288, Springer International Publishing. doi:10.1007/978-3-030-53552-0_26 (2020)
[19] Miller, GA, The magical number seven, plus or minus two: some limits on our capacity for processing information, Psychol. Rev., 63, 2, 81-97 (1956) · doi:10.1037/h0043158
[20] Nievergelt, J.: Information content of chess positions. ACM SIGART Bulletin, (62), pp. 13-15. doi:10.1145/1045398.1045400 (1977)
[21] Laird, JE; Rosenbloom, PS; Newell, A., Chunking in Soar: The anatomy of a general learning mechanism, Mach. Learn., 1, 1, 11-46 (1986) · doi:10.1007/bf00116249
[22] Woodruff, DL, Proposals for chunking and tabu search, Eur. J. Oper. Res., 106, 2-3, 585-598 (1998) · Zbl 0991.90136 · doi:10.1016/s0377-2217(97)00293-2
[23] Voß, S., Gutenschwager, K.: A chunking based genetic algorithm for the Steiner tree problem in graphs. In: Pardalos, P.M., Du, D.-Z. (eds.) Network Design: Connectivity and Facilities Location, 40, pp. 335-355, AMS, Princeton. doi:10.1090/dimacs/040/20 (1998) · Zbl 0902.90163
[24] Woodruff, D.L.: A chunking based selection strategy for integrating meta-heuristics with branch and bound. In: Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, pp. 499-511, Springer US. doi:10.1007/978-1-4615-5775-3_34 (1999) · Zbl 0970.90125
[25] Stringer, H., Wu, A.S.: Winnowing wheat from chaff: The chunking GA. In: Genetic and Evolutionary Computation - GECCO 2004, pp. 198-209, Springer Berlin Heidelberg. doi:10.1007/978-3-540-24855-2_18 (2004)
[26] Tran, B.; Xue, B.; Zhang, M., Variable-length particle swarm optimization for feature selection on high-dimensional classification, IEEE Transactions on Evolutionary Computation, 23, 3, 473-487 (2019) · doi:10.1109/tevc.2018.2869405
[27] Ramkumar, P., Acuna, D.E., Berniker, M., Grafton, S.T., Turner, R.S., Kording, K.P.: Chunking as the result of an efficiency computation trade-off. Nat. Commun., 7(12176). doi:10.1038/ncomms12176 (2016)
[28] Yoon, M., A constant-time chunking algorithm for packet-level deduplication, ICT Express, 5, 2, 131-135 (2019) · doi:10.1016/j.icte.2018.05.005
[29] Yang, S.; Li, C., A clustering particle swarm optimizer for locating and tracking multiple optima in dynamic environments, IEEE Transactions on Evolutionary Computation, 14, 6, 959-974 (2010) · doi:10.1109/tevc.2010.2046667
[30] Jovanovic, R., Tuba, M., Voß, S: Fixed set search applied to the traveling salesman problem. In: International Workshop on Hybrid Metaheuristics, pp. 63-77, Springer. doi:10.1007/978-3-030-05983-5_5 (2019)
[31] Maniezzo, V.; Stüzle, T.; Voß, S., Matheuristics: Hybridizing metaheuristics and mathematical programming (2010), Berlin: Springer Verlag, Berlin
[32] Taillard, E.D., Voß, S: POPMUSIC — Partial Optimization Metaheuristic under Special Intensification Conditions. In: Essays and surveys in metaheuristics. Operations Research/Computer Science Interfaces Series, 15, pp. 613-629, Springer US. doi:10.1007/978-1-4615-1507-4_27 (2002) · Zbl 1017.90132
[33] Kronfeldner, M., Divide and conquer (2018), Oxford: Oxford University Press, Oxford · doi:10.1093/oso/9780198823650.003.0011
[34] Liang, JJ; Qin, AK; Suganthan, PN; Baskar, S., Comprehensive learning particle swarm optimizer for global optimization of multimodal functions, IEEE Transactions on Evolutionary Computation, 10, 3, 281-295 (2006) · doi:10.1109/tevc.2005.857610
[35] Aoun, O.; Sarhani, M.; El Afia, A., Particle swarm optimisation with population size and acceleration coefficients adaptation using hidden Markov model state classification, International Journal of Metaheuristics, 7, 1, 1-29 (2018) · doi:10.1504/ijmheur.2018.091867
[36] van den Bergh, F.; Engelbrecht, A., A cooperative approach to particle swarm optimization, IEEE Trans. Evol. Comput., 8, 3, 225-239 (2004) · doi:10.1109/TEVC.2004.826069
[37] Niu, B.; Zhu, Y.; He, X.; Wu, H., MCPSO: A multi-swarm cooperative particle swarm optimizer, Appl. Math. Comput., 185, 2, 1050-1062 (2007) · Zbl 1112.65055 · doi:10.1016/j.amc.2006.07.026
[38] Aoun, O., El Afia, A, Talbi, E-G: A cooperative multi-swarm particle swarm optimizer based hidden Markov model. In: Heuristics for Optimization and Learning, Studies in Computational Intelligence, 906, pp. 315-334. Springer International Publishing. doi:10.1007/978-3-030-58930-1_21 (2020) · Zbl 1505.90143
[39] Sun, C.; Jin, Y.; Cheng, R.; Ding, J.; Zeng, J., Surrogate-assisted cooperative swarm optimization of high-dimensional expensive problems, IEEE Transactions on Evolutionary Computation, 21, 4, 644-660 (2017) · doi:10.1109/tevc.2017.2675628
[40] Cheng, R.; Jin, Y., A social learning particle swarm optimization algorithm for scalable optimization, Inform. Sci., 291, 43-60 (2015) · Zbl 1355.90108 · doi:10.1016/j.ins.2014.08.039
[41] Li, X.; Yao, X., Cooperatively coevolving particle swarms for large scale optimization, IEEE Transactions on Evolutionary Computation, 16, 2, 210-224 (2012) · doi:10.1109/tevc.2011.2112662
[42] Dorigo, M.; Gambardella, LM, Ant colony system: a cooperative learning approach to the traveling salesman problem, IEEE Transactions on Evolutionary Computation, 1, 1, 53-66 (1997) · doi:10.1109/4235.585892
[43] Sondergeld, L., Voß, S: Cooperative intelligent search using adaptive memory techniques. In: Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, pp. 297-312. Springer US. doi:10.1007/978-1-4615-5775-3_21(1999) · Zbl 0985.90078
[44] El-Abd, M.; Hassan, H.; Anis, M.; Kamel, MS; Elmasry, M., Discrete cooperative particle swarm optimization for FPGA placement, Appl. Soft Comput., 10, 1, 284-295 (2010) · doi:10.1016/j.asoc.2009.07.011
[45] Segredo, E.; Lalla-Ruiz, E.; Hart, E.; Voß, S., On the performance of the hybridisation between migrating birds optimisation variants and differential evolution for large scale continuous problems, Expert Syst. Appl., 102, 126-142 (2018) · doi:10.1016/j.eswa.2018.02.024
[46] Lalla-Ruiz, E., Segredo, E., Voß, S: A cooperative learning approach for the quadratic knapsack problem. In: Lecture Notes in Computer Science, 11353, pp. 31-35, Springer International Publishing. doi:10.1007/978-3-030-05348-2_3 (2018)
[47] Blackwell, T., Branke, J.: Multi-swarm optimization in dynamic environments. In: Lecture Notes in Computer Science, 3005, pp. 489-500. Springer Berlin Heidelberg. doi:10.1007/978-3-540-24653-4_50 (2004)
[48] Lessmann, S., Voß, S: Feature selection in marketing applications. In: Advanced Data Mining and Applications, pp. 200-208. Springer Berlin Heidelberg. doi:10.1007/978-3-642-03348-3_21 (2009)
[49] Unler, A.; Murat, A., A discrete particle swarm optimization method for feature selection in binary classification problems, Eur. J. Oper. Res., 206, 3, 528-539 (2010) · Zbl 1188.90280 · doi:10.1016/j.ejor.2010.02.032
[50] Xue, B.; Zhang, M.; Browne, WN, Particle swarm optimisation for feature selection in classification: Novel initialisation and updating mechanisms, Appl. Soft Comput., 18, 261-276 (2014) · doi:10.1016/j.asoc.2013.09.018
[51] Vieira, SM; Sousa, JMC; Runkler, TA, Two cooperative ant colonies for feature selection using fuzzy models, Expert Syst. Appl., 37, 4, 2714-2723 (2010) · doi:10.1016/j.eswa.2009.08.026
[52] Song, Q.; Ni, J.; Wang, G., A fast clustering-based feature subset selection algorithm for high-dimensional data, IEEE Transactions on Knowledge and Data Engineering, 25, 1, 1-14 (2013) · doi:10.1109/tkde.2011.181
[53] Moradi, P.; Rostami, M., Integration of graph clustering with ant colony optimization for feature selection, Knowl.-Based Syst., 84, 144-161 (2015) · doi:10.1016/j.knosys.2015.04.007
[54] Banka, H.; Dara, S., A hamming distance based binary particle swarm optimization (HDBPSO) algorithm for high dimensional feature selection, classification and validation, Pattern Recogn. Lett., 52, 94-100 (2015) · doi:10.1016/j.patrec.2014.10.007
[55] Sarhani, M., El Afia, A, Faizi, R.: Facing the feature selection problem with a binary PSO-GSA approach. In: Operations Research/Computer Science Interfaces Series, 62, pp. 447-462. Springer International Publishing. doi:10.1007/978-3-319-58253-5_26 (2017)
[56] Vieira, SM; Mendonça, LF; Farinha, GJ; Sousa, JMC, Modified binary PSO for feature selection using SVM applied to mortality prediction of septic patients, Appl. Soft Comput., 13, 8, 3494-3504 (2013) · doi:10.1016/j.asoc.2013.03.021
[57] Vignolo, LD; Milone, DH; Scharcanski, J., Feature selection for face recognition based on multi-objective evolutionary wrappers, Expert Syst. Appl., 40, 13, 5077-5084 (2013) · doi:10.1016/j.eswa.2013.03.032
[58] Mafarja, MM; Mirjalili, S., Hybrid whale optimization algorithm with simulated annealing for feature selection, Neurocomputing, 260, 302-312 (2017) · doi:10.1016/j.neucom.2017.04.053
[59] Boser, B.E., Guyon, I.M., Vapnik, V.N.: A training algorithm for optimal margin classifiers. In: Proceedings of the fifth annual workshop on Computational learning theory - COLT’92. ACM Press. doi:10.1145/130385.130401 (1992)
[60] Miranda, LJV, PySwarms: a research toolkit for particle swarm optimization in Python, The Journal of Open Source Software, 3, 21, 433 (2018) · doi:10.21105/joss.00433
[61] Liu, H., Setiono, R.: Chi2: feature selection and discretization of numeric attributes. In: Proceedings of 7th IEEE International Conference on Tools with Artificial Intelligence, pp. 388-391. IEEE. doi:10.1109/tai.1995.479783 (1995)
[62] Ross, BC, Mutual information between discrete and continuous data sets, PLoS ONE, 9, 2, e87357 (2014) · doi:10.1371/journal.pone.0087357
[63] Mao, KZ, Orthogonal forward selection and backward elimination algorithms for feature subset selection, IEEE Transactions on Systems, Man and Cybernetics, Part B (Cybernetics), 34, 1, 629-634 (2004) · doi:10.1109/tsmcb.2002.804363
[64] Srisukkham, W.; Zhang, L.; Neoh, SC; Todryk, S.; Lim, CP, Intelligent leukaemia diagnosis with bare-bones PSO based feature optimization, Appl. Soft Comput., 56, 405-419 (2017) · doi:10.1016/j.asoc.2017.03.024
[65] Dhillon, IS; Mallela, S.; Kumar, R., A divisive information-theoretic feature clustering algorithm for text classification, J. Mach. Learn. Res., 3, 1265-1287 (2003) · Zbl 1102.68545 · doi:10.1162/153244303322753661
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.