Set-based discrete particle swarm optimization and its applications: a survey

doi:10.1007/s11704-018-7155-4

Front. Comput. Sci.

2018, Vol. 12

Issue (2) : 203-216 https://doi.org/10.1007/s11704-018-7155-4

REVIEW ARTICLE

Set-based discrete particle swarm optimization and its applications: a survey

Wei-Neng CHEN(

), Da-Zhao TAN

School of Computer Science and Engineering, South China University of Technology, Guangzhou 510006, China

Download: PDF(487 KB)
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract

Particle swarm optimization (PSO) is one of the most popular population-based stochastic algorithms for solving complex optimization problems. While PSO is simple and effective, it is originally defined in continuous space. In order to take advantage of PSO to solve combinatorial optimization problems in discrete space, the set-based PSO (SPSO) framework extends PSO for discrete optimization by redefining the operations in PSO utilizing the set operations. Since its proposal, S-PSO has attracted increasing research attention and has become a promising approach for discrete optimization problems. In this paper, we intend to provide a comprehensive survey on the concepts, development and applications of S-PSO. First, the classification of discrete PSO algorithms is presented. Then the S-PSO framework is given. In particular, we will give an insight into the solution construction strategies, constraint handling strategies, and alternative reinforcement strategies in S-PSO together with its different variants. Furthermore, the extensions and applications of S-PSO are also discussed systemically. Some potential directions for the research of S-PSO are also discussed in this paper.

Keywords particle swarm optimization combinatorial optimization discrete optimization swarm intelligence setbased

Corresponding Author(s): Wei-Neng CHEN

Just Accepted Date: 20 December 2017 Online First Date: 06 March 2018 Issue Date: 22 March 2018

Cite this article:

Wei-Neng CHEN,Da-Zhao TAN. Set-based discrete particle swarm optimization and its applications: a survey[J]. Front. Comput. Sci., 2018, 12(2): 203-216.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-018-7155-4
https://academic.hep.com.cn/fcs/EN/Y2018/V12/I2/203

1	Wen X, Chen W-N, Lin Y, Gu T, Zhang H, Li Y, Yin Y, Zhang J. Amaximal clique based multiobjective evolutionary algorithm for overlapping community detection. IEEE Transactions on Evolutionary Computation, 2017, 21(3): 363–377
2	Chen W-N, Zhang J. An ant colony optimization approach to a grid workflow scheduling problem with various QoS requirements. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 2009, 39(1): 29–43 https://doi.org/10.1109/TSMCC.2008.2001722
3	Chen W-N, Zhang J. Ant colony optimization for software project scheduling and staffing with an event-based scheduler. IEEE Transactions on Software Engineering, 2013, 39(1): 1–17 https://doi.org/10.1109/TSE.2012.17
4	Chen W-N, Zhang J, Lin Y, Chen N, Zhan Z H, Chung H S-H, Li Y, Shi Y-H. Particle swarm optimization with an aging leader and challengers. IEEE Transactions on Evolutionary Computation, 2013,17(2): 241–258 https://doi.org/10.1109/TEVC.2011.2173577
5	Eberhart R, Kennedy J. A new optimizer using particle swarm theory. In: Proceedings of the 6th International Symposium on Micro Machine and Human Science. 1995, 39–43 https://doi.org/10.1109/MHS.1995.494215
6	Kulkarni R V, Venayagamoorthy G K. Particle swarm optimization in wireless-sensor networks: a brief survey. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 2011, 41(2): 262–267 https://doi.org/10.1109/TSMCC.2010.2054080
7	Wai R J, Lee J D, Chuang K L. Real-time PID control strategy for Maglev transportation system via particle swarm optimization. IEEE Transactions on Industrial Electronics, 2011, 58(2): 629–646 https://doi.org/10.1109/TIE.2010.2046004
8	Kennedy J, Mendes R. Population structure and particle swarm performance. In: Proceedings of IEEE Congress on Evolutionary Computation. 2002, 1671–1676 https://doi.org/10.1109/CEC.2002.1004493
9	Zhan Z-H, Zhang J, Li Y, Chung H S-H. Adaptive particle swarm optimization. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 2009, 39(6): 1362–1381 https://doi.org/10.1109/TSMCB.2009.2015956
10	Liang J J, Qin A K, Suganthan P N, Baskar S. Comprehensive learning particle swarm optimizer for global optimization of multimodal functions. IEEE Transactions on Evolutionary Computation, 2006, 10(3): 281–295 https://doi.org/10.1109/TEVC.2005.857610
11	Li X, Yao X. Cooperatively coevolving particle swarms for large scale optimization. IEEE Transactions on Evolutionary Computation, 2012, 16(2): 210–224 https://doi.org/10.1109/TEVC.2011.2112662
12	Cheng R, Jin Y. A competitive swarm optimizer for large scale optimization. IEEE Transactions on Cybernetics, 2015, 45(2): 191–204 https://doi.org/10.1109/TCYB.2014.2322602
13	Yang Q, Chen W-N, Gu T, Zhang H, Deng J D, Li Y, Zhang J. Segmentbased predominant learning swarm optimizer for large-scale optimization. IEEE Transactions on Cybernetics, 2017, 47(9): 2896–2910 https://doi.org/10.1109/TCYB.2016.2616170
14	Al-Kazemi B, Mohan C. Discrete multi-phase particle swarm optimization. Information Processing with Evolutionary Algorithms, 2005, 23(4): 305–327 https://doi.org/10.1007/1-84628-117-2_20
15	Kennedy J, Eberhart R C. A discrete binary version of the particle swarm algorithm. In: Proceedings of IEEE International Conference on Systems, Man, and Cybernetics. 1997, 4104–4108 https://doi.org/10.1109/ICSMC.1997.637339
16	Liu J, Mei Y, Li X. An analysis of the inertia weight parameter for binary particle swarm optimization. IEEE Transactions on Evolutionary Computation, 2016, 20(5): 666–681 https://doi.org/10.1109/TEVC.2015.2503422
17	Pampara G, Franken N, Engelbrecht A P. Combining particle swarm optimisation with angle modulation to solve binary problems. In: Proceedings of IEEE Congress on Evolutionary Computation. 2005, 89–96 https://doi.org/10.1109/CEC.2005.1554671
18	Shen M, Zhan Z-H, Chen W-N, Gong Y-J, Zhang J, Li Y. Bi-velocity discrete particle swarm optimization and its application to multicast routing problem in communication networks. IEEE Transactions on Industrial Electronics, 2014, 61(12): 7141–7151 https://doi.org/10.1109/TIE.2014.2314075
19	Gong M, Cai Q, Chen X, Ma L. Complex network clustering by multiobjective discrete particle swarm optimization based on decomposition. IEEE Transactions on Evolutionary Computation, 2014, 18(1): 82–97 https://doi.org/10.1109/TEVC.2013.2260862
20	Afshinmanesh F, Marandi A, Rahimi-Kian A. A novel binary particle swarm optimization method using artificial immune system. In: Proceedings of the International Conference on Computer as a Tool. 2005, 217–220 https://doi.org/10.1109/EURCON.2005.1629899
21	Clerc M. Discrete particle swarm optimization, illustrated by the traveling salesman problem. New Optimization Techniques in Engineering, 2004, 47(1): 219–239 https://doi.org/10.1007/978-3-540-39930-8_8
22	Wang K-P, Huang L, Zhou C-G, Pang W. Particle swarm optimization for traveling salesman problem. In: Proceedings of International Conference on Machine Learning and Cybernetics. 2003, 1583–1585
23	Huang J, Gong M, Ma L. A global network alignment method using discrete particle swarm optimization. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2017 (in press)
24	Rameshkumar K, Suresh R K, Mohanasundaram K M. Discrete particle swarm optimization (DPSO) algorithm for permutation flowshop scheduling to minimize makespan. In: Proceedings of International Conference on Natural Computation. 2005, 572–581 https://doi.org/10.1007/11539902_70
25	Pang W, Wang K-P, Zhou C-G, Dong L-J, Liu M, Zhang H-Y, Wang J-Y. Modified particle swarm optimization based on space transformation for solving traveling salesman problem. In: Proceedings of International Conference on Machine Learning and Cybernetics. 2004, 2342–2346
26	Salman A, Ahmad I, Al-Madani S. Particle swarm optimization for task assignment problem. Microprocessors and Microsystems, 2002, 26(8), 363–371 https://doi.org/10.1016/S0141-9331(02)00053-4
27	Sha D Y, Hsu C-Y. A hybrid particle swarm optimization for job shop scheduling problem. Computers & Industrial Engineering, 2006, 51(4): 791–808 https://doi.org/10.1016/j.cie.2006.09.002
28	Zhu H,Wang Y-P. Integration of security grid dependent tasks scheduling double-objective optimization model and algorithm. Ruanjian Xuebao/ Journal of Software, 2011, 22(11): 2729–2748 https://doi.org/10.3724/SP.J.1001.2011.03900
29	Jin Y-X, Cheng H-Z, Yan J Y, Zhang L. New discrete method for particle swarm optimization and its application in transmission network expansion planning. Electric Power Systems Research, 2007, 77(3): 227–233 https://doi.org/10.1016/j.epsr.2006.02.016
30	AlRashidi M R, El-Hawary M E. Hybrid particle swarm optimization approach for solving the discrete OPF problem considering the valve loading effects. IEEE Transactions on Power Systems, 2007, 22(4): 2030–2038 https://doi.org/10.1109/TPWRS.2007.907375
31	Chandrasekaran S, Ponnambalam S G, Suresh R K, Vijayakumar N. A hybrid discrete particle swarm optimization algorithm to solve flow shop scheduling problems. In: Proceedings of IEEE Conference on Cybernetics and Intelligent Systems. 2006, 1–6 https://doi.org/10.1109/ICCIS.2006.252316
32	Eajal A A, El-Hawary M E. Optimal capacitor placement and sizing in unbalanced distribution systems with harmonics consideration using particle swarm optimization. IEEE Transactions on Power Delivery, 2010, 25(3): 1734–1741 https://doi.org/10.1109/TPWRD.2009.2035425
33	Gao H, Kwong S, Fan B,Wang R. A hybrid particle-swarm tabu search algorithm for solving job shop scheduling problems. IEEE Transactions on Industrial Informatics, 2014, 10(4): 2044–2054 https://doi.org/10.1109/TII.2014.2342378
34	Goldbarg E F G, de Souza G R, Goldbarg M C. Particle swarm for the traveling salesman problem. In: Proceedings of European Conference on Evolutionary Computation in Combinatorial Optimization. 2006, 99–110 https://doi.org/10.1007/11730095_9
35	Lope H S, Coelho L S. Particle swarn optimization with fast local search for the blind traveling salesman problem. In: proceedings of the 5th International Conference on Hybrid Intelligent Systems. 2005, 245–250 https://doi.org/10.1109/ICHIS.2005.86
36	Marinakis Y, Marinaki M. A particle swarm optimization algorithm with path relinking for the location routing problem. Journal of Mathematical Modelling and Algorithms, 2008, 7(1): 59–78 https://doi.org/10.1007/s10852-007-9073-6
37	Rosendo M, Pozo A. A hybrid particle swarm optimization algorithm for combinatorial optimization problems. In: Proceedings of IEEE Congress on Evolutionary Computation. 2010, 1–8 https://doi.org/10.1109/CEC.2010.5586178
38	Shi X H, Liang Y C, Lee H P, Lu C, Wang Q X. Particle swarm optimization-based algorithms for TSP and generalized TSP. Information Processing Letters, 2007, 103(5): 169–176 https://doi.org/10.1016/j.ipl.2007.03.010
39	Strasser S, Goodman R, Sheppard J, Butcher S. A new discrete particle swarm optimization algorithm. In: Proceedings of the 18th International Conference on Genetic and Evolutionary Computation. 2016, 53–60 https://doi.org/10.1145/2908812.2908935
40	Wang Y, Feng X-Y, Huang Y-X, Pu D-B, Zhou W-G, Liang Y-C, Zhou C-G. A novel quantum swarm evolutionary algorithm and its applications. Neurocomputing, 2007, 70(4): 633–640 https://doi.org/10.1016/j.neucom.2006.10.001
41	Zhang G, Shao X, Li P, Gao L. An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem. Computers & Industrial Engineering, 2009, 56(4): 1309–1318 https://doi.org/10.1016/j.cie.2008.07.021
42	Chen W-N, Zhang J, Chung H S, Zhong W-L, Wu W-G, Shi Y-H. A novel set-based particle swarm optimization method for discrete optimization problems. IEEE Transactions on Evolutionary Computation, 2010, 14(2): 278–300 https://doi.org/10.1109/TEVC.2009.2030331
43	Gong Y-J, Zhang J, Liu O, Huang R-Z, Chung H S, Shi Y-H. Optimizing the vehicle routing problem with time windows: a discrete particle swarm optimization approach. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 2012, 42(2): 254–267 https://doi.org/10.1109/TSMCC.2011.2148712
44	Jia Y-H, Chen W-N, Gu T, Zhang H, Yuan H, Lin Y, Yu W-J, Zhang J. A dynamic logistic dispatching system with set-based particle swarm optimization. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2017 (in press) https://doi.org/10.1109/TSMC.2017.2682264
45	Wu H, Nie C, Kuo F-C, Leung H, Colbourn C J. A discrete particle swarm optimization for covering array generation. IEEE Transactions on Evolutionary Computation, 2015, 19(4): 575–591 https://doi.org/10.1109/TEVC.2014.2362532
46	Kaiwartya O, Kumar S, Lobiyal D K, Tiwari P K, Abdullah A H, Hassan A N. Multiobjective dynamic vehicle routing problem and time seed based solution using particle swarm optimization. Journal of Sensors, 2015 https://doi.org/10.1155/2015/189832
47	Chen W-N, Zhang J, Chung H S, Huang R-Z, Liu O. Optimizing discounted cash flows in project scheduling—an ant colony optimization approach. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 2010, 40(1): 64–77 https://doi.org/10.1109/TSMCC.2009.2027335
48	Jia Y-H, Chen W-N, Hu X-M. A PSO approach for software project planning. In: Proceedings of the 16th Annual Conference on Genetic and Evolutionary Computation. 2014, 7–8 https://doi.org/10.1145/2598394.2598422
49	Ma Y-Y, Gong Y-J, Chen W-N, Zhang J. A set-based locally informed discrete particle swarm optimization. In: Proceedings of the 15th Annual companion conference on Genetic and Evolutionary Computation. 2013, 71–72 https://doi.org/10.1145/2464576.2464614
50	Langeveld J, Engelbrecht A P. Set-based particle swarm optimization applied to the multidimensional knapsack problem. Swarm Intelligence, 2012, 6(4), 297–342 https://doi.org/10.1007/s11721-012-0073-4
51	Chou S-K, Jiau M-K, Huang S-C. Stochastic set-based particle swarm optimization based on local exploration for solving the carpool service problem. IEEE Transactions on Cybernetics, 2016, 46(8): 1771–1783 https://doi.org/10.1109/TCYB.2016.2522471
52	Hino T, Ito S, Liu T, Maeda M. Set-based particle swarm optimization with status memory for knapsack problem. Artificial Life and Robotics, 2016, 21(1): 98–105 https://doi.org/10.1007/s10015-015-0253-6
53	Liu Y, Chen W-N, Zhan Z-H, Lin Y, Gong Y-J, Zhang J. A set-based discrete differential evolution algorithm. In: Proceedings of IEEE International Conference on Systems, Man, and Cybernetics (SMC). 2013, 1347–1352 https://doi.org/10.1109/SMC.2013.233
54	Yu X, Chen W-N, Hu X M, Zhang J. A set-based comprehensive learning particle swarm optimization with decomposition for multiobjective traveling salesman problem. In: Proceedings of the 17th Annual Conference on Genetic and Evolutionary Computation. 2015, 89–96 https://doi.org/10.1145/2739480.2754672
55	Zhang Q, Li H. MOEA/D: a multiobjective evolutionary algorithm based on decomposition. IEEE Transactions on Evolutionary Computation, 2007, 11(6): 712–731 https://doi.org/10.1109/TEVC.2007.892759
56	Liao T, Socha K, de OcaMA M, Stützle T, Dorigo M. Ant colony optimization for mixed-variable optimization problems. IEEE Transactions on Evolutionary Computation, 2014, 18(4): 503–518 https://doi.org/10.1109/TEVC.2013.2281531
57	Yang Q, Chen W-N, Li Y, Chen C L P, Xu X-M, Zhang J. Multimodal estimation of distribution algorithms. IEEE Transactions on Cybernetics, 2017, 47(3): 636–650 https://doi.org/10.1109/TCYB.2016.2523000
58	Yang Q, Chen W-N, Yu Z, Gu T, Li Y, Zhang H, Zhang J. Adaptive multimodal continuous ant colony optimization. IEEE Transactions on Evolutionary Computation, 2017, 21(2): 191–205 https://doi.org/10.1109/TEVC.2016.2591064
59	Hafiz F, Abdennour A. Particle swarm algorithm variants for the quadratic assignment problems—a probabilistic learning approach. Expert Systems with Applications, 2016, 44: 413–431 https://doi.org/10.1016/j.eswa.2015.09.032
60	Xu X-X, Hu X-M, Chen W-N, Li Y. Set-based particle swarm optimization for mapping and scheduling tasks on heterogeneous embedded systems. In: Proceedings of the 8th International Conference on Advanced Computational Intelligence. 2016, 318–325 https://doi.org/10.1109/ICACI.2016.7449845
61	Xia X, Wang X, Li J, Zhou X. Multi-objective mobile app recommendation: a system-level collaboration approach. Computers & Electrical Engineering, 2014, 40(1): 203–215 https://doi.org/10.1016/j.compeleceng.2013.11.012
62	Kumar T V V, Kumar A, Singh R. Distributed query plan generation using particle swarm optimization. International Journal of Swarm Intelligence Research (IJSIR), 2013, 4(3): 58–82 https://doi.org/10.4018/ijsir.2013070104
63	Toth P, Vigo D. The Vehicle Routing Problem. Philadelphia: Society for Industrial and Applied Mathematics, 2002 https://doi.org/10.1137/1.9780898718515

[1]

Download

[1]	Yihui LIANG, Han HUANG, Zhaoquan CAI. PSO-ACSC: a large-scale evolutionary algorithm for image matting[J]. Front. Comput. Sci., 2020, 14(6): 146321-.
[2]	Geng ZHANG, Yangmin LI, Yuhui SHI. Distributed learning particle swarm optimizer for global optimization of multimodal problems[J]. Front. Comput. Sci., 2018, 12(1): 122-134.
[3]	Cui HUANG, Dakun ZHANG, Guozhi SONG. A novel mapping algorithm for three-dimensional network on chip based on quantum-behaved particle swarm optimization[J]. Front. Comput. Sci., 2017, 11(4): 622-631.
[4]	Genggeng LIU,Wenzhong GUO,Rongrong LI,Yuzhen NIU,Guolong CHEN. XGRouter: high-quality global router in X-architecture with particle swarm optimization[J]. Front. Comput. Sci., 2015, 9(4): 576-594.
[5]	Priyanka CHAWLA,Inderveer CHANA,Ajay RANA. A novel strategy for automatic test data generation using soft computing technique[J]. Front. Comput. Sci., 2015, 9(3): 346-363.
[6]	Peng ZHANG. Unbalanced graph cuts with minimum capacity[J]. Front. Comput. Sci., 2014, 8(4): 676-683.
[7]	Wenzhong GUO,Genggeng LIU,Guolong CHEN,Shaojun PENG. A hybrid multi-objective PSO algorithm with local search strategy for VLSI partitioning[J]. Front. Comput. Sci., 2014, 8(2): 203-216.
[8]	Wei ZHAO, Ye SAN. RBF neural network based on q-Gaussian function in function approximation[J]. Front Comput Sci Chin, 2011, 5(4): 381-386.
[9]	Yong FENG, Zhongfu WU, Jiang ZHONG, Chunxiao YE, Kaigui WU, . An enhanced swarm intelligence clustering-based RBFNN classifier and its application in deep Web sources classification[J]. Front. Comput. Sci., 2010, 4(4): 560-570.
[10]	Yong WANG, Zixing CAI. A hybrid multi-swarm particle swarm optimization to solve constrained optimization problems[J]. Front Comput Sci Chin, 2009, 3(1): 38-52.
[11]	Yuhui SHI, Russ EBERHART. Monitoring of particle swarm optimization[J]. Front Comput Sci Chin, 2009, 3(1): 31-37.

Viewed

Full text

Abstract

Cited

Shared

Discussed