×

Improved particle swarm optimization and neighborhood field optimization by introducing the re-sampling step of particle filter. (English) Zbl 1415.90151

Summary: A technique of introducing the re-sampling step of particle filter is proposed to improve the particle swarm optimization (PSO) algorithm, a typical global search algorithm. The re-sampling step can decrease particles with low weights and duplicate particles with high weights, given that we define a type of suitable weights for the particles. To prevent the identity of particles, the re-sampling step is followed by the existing method of particle variation. Through this technique, the local search capability is enhanced greatly in the later searching stage of PSO algorithm. More interesting, this technique can also be employed to improve another algorithm of which the philosophy is “learning from neighbors”, i.e., the neighborhood field optimization (NFO) algorithm. The improved algorithms (PSO-resample and NFO-resample) are compared with other metaheuristic algorithms through extensive simulations. The experiments show that the improved algorithms are superior in terms of convergence rate, search accuracy and robustness. Our results also suggest that the proposed technique can be general in the sense that it can probably improve other particle-based intelligent algorithms.

MSC:

90C59 Approximation methods and heuristics in mathematical programming
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
65K05 Numerical mathematical programming methods
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] K. Amin; M. Guerrero-Zapata, A hybrid multiobjective RBF-PSO method for mitigating dos attacks in named data networking, Neurocomputing, 151, 1262-1282 (2015)
[2] K. Amin; M. Guerrero-Zapata, A fuzzy anomaly detection system based on hybrid PSO-Kmeans algorithm in content-centric networks, Neurocomputing, 149, 1253-1269 (2015)
[3] M. S. Arulampalam; S. Maskell; N. Gordon; T. clapp, A tutorial on particle filters for online nonlinear/non-Gaussian Bayesian tracking, IEEE Transactions on Signal Processing, 50, 174-188 (2002) · doi:10.1109/78.978374
[4] T. M. Blackwell; P. Bentley, Don’T push me! Collision-avoiding swarms, Proceedings of the 2002 Congress on Evolutionary Computation, 2, 1691-1696 (2002) · doi:10.1109/CEC.2002.1004497
[5] J. Carpenter; P. Clifford; F. Fearnhead, An improved particle filter for non-linear problems, IEE Proceedings-Radar, Sonar and Navigation, 146, 2-7 (1999)
[6] M. Clerc; J. Kennedy, The particle swarm-explosion, stability, and convergence in a multidimensional complex space, IEEE Transactions on Evolutionary Computation, 6, 58-73 (2002) · doi:10.1109/4235.985692
[7] D. Crisan; A. Doucet, A survey of convergence result on particle filtering methods for practitioners, IEEE Transactions on Signal Processing, 50, 736-746 (2002) · Zbl 1369.60015 · doi:10.1109/78.984773
[8] A. Doucet; S. Godsill; C. Andrieu, On sequential Monte Carlo sampling method for Bayesian filtering, Statistics and Computing, 10, 197-208 (2000)
[9] R. C. Eberhart; J. Kennedy, A new optimizer using particle swarm theory, Proceedings of the 6th International Symposium on Micro machine and Human Science, 39-43 (1995) · doi:10.1109/MHS.1995.494215
[10] F. Glover, Tabu search-part Ⅱ, ORSA Journal on Computing, 2, 4-32 (1990) · Zbl 0771.90084 · doi:10.1287/ijoc.2.1.4
[11] N. J. Gordon; D. J. Salmond; A. F. M. Smith, Novel approach to nonlinear/non-Gaussian Bayesian state estimation, Radar and Signal Processing, IEE Proceedings F, 140, 107-113 (1993) · doi:10.1049/ip-f-2.1993.0015
[12] R. Greiner, POLO: A probabilistic hill-climbing algorithm, Artificial Intelligence, 84, 177-208 (1996) · Zbl 1506.68093 · doi:10.1016/0004-3702(95)00040-2
[13] J. Grobler; A. P. Engelbrecht; G. Kendall; S. Yadavalli, Heuristic space diversity control for improved meta-hyper-heuristic performance, Information Sciences, 300, 49-62 (2015)
[14] J. Grobler and A. P. Engelbrecht, Headless chicken particle swarm optimization algorithms, Tan Y., Shi Y., Niu B. (eds) Advances in Swarm Intelligence. ICSI 2016. Lecture Notes in Computer Science, 9712 (2016), 350-357.
[15] J. Grobler; A. P. Engelbrecht, A scalability analysis of particle swarm optimization roaming behaviour, Advances in Swarm Intelligence. ICSI 2017. Lecture Notes in Computer Science, 10385, 119-130 (2017) · doi:10.1007/978-3-319-61824-1_13
[16] J. D. Hol; T. B. Schon; F. Gustafsson, On resampling algorithms for particle filters, IEEE Nonlinear Statistical Signal Processing Workshop, 79-82 (2006) · doi:10.1109/NSSPW.2006.4378824
[17] B. J. Jain; H. Pohlheim; W. Joachim, On termination criteria of evolutionary algorithms, Proceedings of the 3rd Annual Conference on Genetic and Evolutionary Computation, 768-775 (2001)
[18] J. Kennedy; R. C. Eberhart, Particle swarm optimization, Proceedings of the IEEE International Conference on Neural Networks, 1942-1948 (1995) · doi:10.1109/ICNN.1995.488968
[19] J. Kennedy; R. Mendes, Population structure and particle swarm performance, Proceedings of the 2002 Congress on Evolutionary Computation, 2, 1671-1676 (2002) · doi:10.1109/CEC.2002.1004493
[20] S. Kirkpatrick; C. D. Gelatt; M. P. Vecchi, Optimization by simulated annealing, Science, 220, 671-680 (1983) · Zbl 1225.90162 · doi:10.1126/science.220.4598.671
[21] G. Kitagawa, Monte Carlo filter and smoother for non-Gaussian nonlinear state space models, Journal of Computational and Graphical Statistics, 5, 1-25 (1996)
[22] J. Lampinen and R. Storn, Differential evolution, Onwubolu G, Babu BV (eds) New Optimization Techniques in Engineering, (2004), 123-166.
[23] J. J. Liang; A. K. Qin; P. N. Suganthan; S. Baskar, Comprehensive learning particle swarm optimizer for global optimization of multimodal functions, IEEE Transactions on Evolutionary Computation, 10, 281-295 (2006) · doi:10.1109/TEVC.2005.857610
[24] J. S. Liu; R. Chen, Sequential Monte Carlo methods for dynamic systems, Journal of the American Statistical Association, 93, 1032-1044 (1998) · Zbl 1064.65500 · doi:10.1080/01621459.1998.10473765
[25] R. Mendes; J. Kennedy; J. Neves, The fully informed particle swarm: simpler, maybe better, IEEE Transactions on Evolutionary Computation, 8, 204-210 (2004) · doi:10.1109/TEVC.2004.826074
[26] K. E. Parsopoulos; M. N. Vrahatis, UPSO-A unified particle swarm optimization scheme, Lecture Series on Computational Sciences, 1, 868-873 (2004)
[27] T. Peram; K. Veeramachaneni; C. K. Mohan, Fitness-distance-ratio based particle swarm optimization, Proceedings of the 2003 IEEE on Swarm Intelligence Symposium, 174-181 (2003) · doi:10.1109/SIS.2003.1202264
[28] Y. Shi; R. C. Eberhart, A modified particle swarm optimizer, IEEE International Conference on Evolutionary Computation Proceedings. IEEE World Congress on Computational Intelligence, 69-73 (1998) · doi:10.1109/ICEC.1998.699146
[29] R. Storn; K. Price, Differential evolutional simple and efficient heuristic for global optimization over continuous space, Journal of Global Optimization, 11, 341-359 (1997) · Zbl 0888.90135 · doi:10.1023/A:1008202821328
[30] P. N. Suganthan, Particle swarm optimiser with neighborhood operator, Proceedings of the 1999 Congress on Evolutionary Computation, 3, 1958-1962 (1999)
[31] Z. Wu; T. W. S. Chow, A local multiobjective optimization algorithm using neighborhood field, Structural and Multidisciplinary Optimization, 46, 853-870 (2012) · Zbl 1274.90364 · doi:10.1007/s00158-012-0800-x
[32] Z. Wu; T. W. S. Chow, Neighborhood field for cooperative optimization, Soft Computing, 17, 819-834 (2013) · doi:10.1007/s00500-012-0955-9
[33] Z. Wu; T. W. S. Chow, Binary neighborhood field optimization for unit commitment problems, IET Generation Transmission and Distribution, 7, 299-308 (2013)
[34] C. Yang; L. Gu; W. Gui, Particle swarm optimization algorithm with adaptive mutation, Computer Engineering, 34, 188-190 (2008)
[35] X. Yao; Y. Liu; G. M. Lin, Evolutionary programming made faster, IEEE Transactions on Evolutionary Computation, 3, 82-102 (1999)
[36] B. Yao; B. Yu; P. Hu; J. Gao; M. H. Zhang, An improved particle swarm optimization for carton heterogeneous vehicle routing problem with a collection depot, Annals of Operations Research, 242, 303-320 (2016) · Zbl 1350.90014 · doi:10.1007/s10479-015-1792-x
[37] T. T. Zhao; Q. F. Cheng; Z. F. Wang, Nonlinear model predictive control optimization with improved particle swarm algorithm, Liaoning Gongcheng Jishu Daxue Xuebao (Ziran Kexue Ban)/Journal of Liaoning Technical University (Natural Science Edition), 34, 517-522 (2015)
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.