粒子群优化算法及其应用
|
摘要
粒子群优化算法是一种基于群体的智能优化算法,它是通过模拟鸟群的行为来解决最优化问题。粒子群优化在电子、通信、控制等诸多领域中有着广泛的应用和发展。其利用群体的优势为许多复杂问题的求解提供了新的手段,所以研究和掌握它的特性与规律,是一个具有重要意义的课题。
对于人类来说,识别字体,数字,声音等等都是比较容易的。但是让计算机解决这一类的问题却是一个非常困难的事情。模式识别就是把目标对象分成不同的种类的学科,它是人工智能和计算机视觉的基本组成部分。聚类分析是模式识别范畴中的一个重要分支,是一种无监督的模式识别方法,在许多领域被广泛地应用。随着计算机技术的发展,将传统的聚类技术与现代优化方法相结合成为一种新趋势。
近几十年来,面对信息时代海量数据的出现,数据挖掘技术应运而生并得到迅猛发展,其中关联规则挖掘作为数据挖掘的重要模式之一,它所得到的知识能为支持决策提供依据,有着极其重要的研究价值。在基本离散粒子群算法的基础上,给出了一种改进的算法,并将其应用到关联规则挖掘领域。
给出了一种基于PSO(Particle Swarm Optimization)的聚类算法,通过在Iris等数据集的实验结果表明,PSO算法相比传统的K-means算法,能有效提高聚类的质量,同时也降低了聚类错误率。给出一种基于粒子群算法的混合优化关联规则挖掘技术,包括粒子的编码,群体的初始化,适应度的计算以及位置的更新。接着又对算法进行了改进,引入多群体及遗传算法中的选择机制,形成一种新的多群体混合粒子群算法。通过在微软数据库mushroom上进行了一个挖掘试验,将MHPSO算法和遗传算法进行比较,结果表明,该算法具有良好的性能和表现。
Particle Swarm Optimization (PSO) is a swarm based intelligence optimization method, it solves optimization problems by simulating the social behavior of bird flocks. PSO has been widely applied and developed in the field of electrical, communication, control and so on. It takes advantage of colony to find new avenue for the solution of complex problems. Therefore, to study and master the characteristics and rule of PSO is a significant task.
As humans, it is easy to recognize letters, numbers, voices, etc. However, making a computer solve these types of problems is a very difficult task. Pattern recognition is the science with the objective to classify objects into different categories and classes. It is a fundamental component of artificial intelligence and computer vision. Clustering analysis is an important branch of pattern recognition, it is an unsupervised pattern recognition method, and was widely used in many fields. With the development of computer technology, traditional clustering technology in combination with modern optimization methods becomes available.
In recent decades, in the face of massive data in the information age, data mining is arose and rapidly developed. As one of the most important models of data mining, this technology by which the knowledge discovered can be used to offer decision support, has the most significant application value. This thesis researches on the basic theory of discrete particle swarm optimization, and then presents an improved algorithm, which is introduced into data mining.
Introduces a new algorithm based on PSO to the field of clustering. The algorithm is successfully applied to clustering problems including Iris, etc. The experimental results show that this algorithm can obtain good clustering results compared with K-means algorithm, it can improve the clustering accuracy with lower error rate. Then a new technology , combined with genetic algorithms, is presented based on particle swarm optimizer, including particle coding, population initializing, fitness computing and position updating. At the same time, multi-populations and selection operator of genetic algorithm are introduced into it, which forms a new algorithm, naming Multi-Populations Hybrid Particle Swarm Optimization. Then, an experiment is tried out on a MS database–mushroom, and experimental results show that particle swarm optimizer has better quality and performance compared with genetic algorithm.
对于人类来说,识别字体,数字,声音等等都是比较容易的。但是让计算机解决这一类的问题却是一个非常困难的事情。模式识别就是把目标对象分成不同的种类的学科,它是人工智能和计算机视觉的基本组成部分。聚类分析是模式识别范畴中的一个重要分支,是一种无监督的模式识别方法,在许多领域被广泛地应用。随着计算机技术的发展,将传统的聚类技术与现代优化方法相结合成为一种新趋势。
近几十年来,面对信息时代海量数据的出现,数据挖掘技术应运而生并得到迅猛发展,其中关联规则挖掘作为数据挖掘的重要模式之一,它所得到的知识能为支持决策提供依据,有着极其重要的研究价值。在基本离散粒子群算法的基础上,给出了一种改进的算法,并将其应用到关联规则挖掘领域。
给出了一种基于PSO(Particle Swarm Optimization)的聚类算法,通过在Iris等数据集的实验结果表明,PSO算法相比传统的K-means算法,能有效提高聚类的质量,同时也降低了聚类错误率。给出一种基于粒子群算法的混合优化关联规则挖掘技术,包括粒子的编码,群体的初始化,适应度的计算以及位置的更新。接着又对算法进行了改进,引入多群体及遗传算法中的选择机制,形成一种新的多群体混合粒子群算法。通过在微软数据库mushroom上进行了一个挖掘试验,将MHPSO算法和遗传算法进行比较,结果表明,该算法具有良好的性能和表现。
Particle Swarm Optimization (PSO) is a swarm based intelligence optimization method, it solves optimization problems by simulating the social behavior of bird flocks. PSO has been widely applied and developed in the field of electrical, communication, control and so on. It takes advantage of colony to find new avenue for the solution of complex problems. Therefore, to study and master the characteristics and rule of PSO is a significant task.
As humans, it is easy to recognize letters, numbers, voices, etc. However, making a computer solve these types of problems is a very difficult task. Pattern recognition is the science with the objective to classify objects into different categories and classes. It is a fundamental component of artificial intelligence and computer vision. Clustering analysis is an important branch of pattern recognition, it is an unsupervised pattern recognition method, and was widely used in many fields. With the development of computer technology, traditional clustering technology in combination with modern optimization methods becomes available.
In recent decades, in the face of massive data in the information age, data mining is arose and rapidly developed. As one of the most important models of data mining, this technology by which the knowledge discovered can be used to offer decision support, has the most significant application value. This thesis researches on the basic theory of discrete particle swarm optimization, and then presents an improved algorithm, which is introduced into data mining.
Introduces a new algorithm based on PSO to the field of clustering. The algorithm is successfully applied to clustering problems including Iris, etc. The experimental results show that this algorithm can obtain good clustering results compared with K-means algorithm, it can improve the clustering accuracy with lower error rate. Then a new technology , combined with genetic algorithms, is presented based on particle swarm optimizer, including particle coding, population initializing, fitness computing and position updating. At the same time, multi-populations and selection operator of genetic algorithm are introduced into it, which forms a new algorithm, naming Multi-Populations Hybrid Particle Swarm Optimization. Then, an experiment is tried out on a MS database–mushroom, and experimental results show that particle swarm optimizer has better quality and performance compared with genetic algorithm.
引文
[1] J.Kennedy, R.Eberhart. Particle Swarm Optimization. In Proceedings of IEEE International conference on Neural Networks, 1995: 1942-1948
[2] R.Eberhart, J.Kennedy. A New Optimizer Using Particle Swarm Theory. In Proceedings of 6th International Symposium on Micro Machine and Human Science, 1995: 39-43
[3] R.Eberhart, Y.Shi. Comparison between genetic algorithms and particle swarm optimization. Lecture Notes in Computer Science, In Proceedings of the 7th international Conference on Evolutionary Programming VII, 1998: 611-616
[4] F.Van den Bergh. An Analysis of Particle Swarm Optimizers. Ph.D. thesis, University of Pretoria, 2002
[5] M.Clerc, J.Kennedy. The particle swarm: Explosion stability and convergence in a multi-dimensional complex space. IEEE Trans Evolution Compute, 2002, 6(1): 58-73
[6] I.C.Trelea. The particle swarm optimization algorithm: convergence analysis and parameter selection. Information Processing Letters, 2003, 85 (6): 317-325
[7] Y.Shi, R.C.Eberhart. A modified particle swarm optimizer. Institute of Electrical and Electronics Engineers. 1998(5): 69-73
[8] Y.Shi, R.C.Eberhart. Parameter selection in particle swarm optimization. Lecture Notes In Computer Science; Vo1. 1447, In Proceedings of the 7th International Conference on Evolutionary Programming VII, Springer-Verlag London, UK, 1998: 591-600
[9] Y.Shi, R.C.Eberhart. Empirical study of particle swarm optimization. Institute of Electrical and Engineers, 1999(7): 1945-1950
[10] M.Clerc. The swarm and queen: Towards a deterministic and adaptive particle swarm optimization. Institute of Electrical and Electronics Engineers, 1999(7): 1951-1957
[11] R.C.Eberhart, Y.Shi. Comparing inertia weights and constriction factors in particle swarm optimization. Institute of Electrical Engineers, 2000(7): 84-88
[12] Y.Shi, R.C. Eberhart. Fuzzy adaptive particle swarm optimization. Institute of Electrical and Electronics Engineers, 2001(5): 101-106
[13]张丽军,俞欢军,陈德钊等.粒子群优化算法的分析与改进.信息与控制, 2004, 33(5): 513-517
[14] I.C.Siarry. Nonlinear inertia weight variation for dynamic adaptation in particle swarm optimization. Computers and Operations Research, 2006, 33(3): 859-871
[15] M.Lovbierg, T.K.Rasmussen, and T.Krink. Hybrid particle swarm optimizer with breeding and subpopulations. Institute of Electrical and Electronics Engineers, 2001(7): 115-118
[16] N.Higashi, H.Iba. Particle swarm optimization with Gaussian mutation. Institute of Electrical and Electronics Engineers, 2003(4): 72-79
[17]吕振肃,侯志荣.自适应变异的粒子群优化算法.电子学报, 2004, 32(3): 416-420
[18]李宁,孙德宝,岑翼刚等.带变异算子的粒子群优化算法.计算机工程与应用, 2004, 40(17): 12-14, 35
[19] P.J.Angeline. Using selection to improve particle swarm optimization. Institute of Electrical and Electronics Engineers, 1998(5): 84-89
[20]吴晓军,薛惠锋,李憋等. GA-PSO混合规划算法.西北大学学报(自然科学版), 2005, 35(1): 39-43
[21]高鹰,谢胜利.基于模拟退火的粒子群优化算法.计算机工程与应用, 2004, 40(1): 47-50
[22]高尚,杨静宇,吴小俊等.基于模拟退火算法思想的粒子群优化算法.计算机应用与软件, 2005, 22(1): 103-104
[23]窦全胜,周春光,马铭.粒子群优化算法的两种改进策略.计算机研究与发展, 2005, 42(5): 897-904
[24]高鹰,谢胜利.混沌粒子群优化算法.计算机科学, 2004, 31(8): 13-15
[25]杨俊杰,周建中,喻菁等.基于混沌搜索的粒子群优化算法.计算机工程与应用, 2005, 41(16): 69-71
[26] C.W.Jiang, B.Etorre. A self-adaptive chaotic particle swarm algorithm for short term hydroelectric system scheduling in deregulated environment. Energy Conversion and Management, 2005, 46(17): 2689-2696
[27] J.Kennedy, R.Eberhart. A discrete binary version of particle swarm optimizationalgorithm. In Proceedings of the 1997 conference on Systems, Man, and Cybernetics (SMC’97), 1997: 4104-4109
[28] C.K.Mohan, B.Al-kazemi. Discrete particle swarm optimization. In Proceedings of the Workshop on Particle Swarm Optimization 2001, Indianapolis, 2001
[29] R.C.Dubes and A.K.jain, Algorithms for clustering data. Englewood Cliffs, NJ: Prentice Hall, 1988
[30] R.O.Duda and P.E.hart, Pattern classification and sence analysis, John Wiley and Sons, New York, 1973
[31] J.T.tou and R.C.Gonzales, Pattern recognition principles, Readind. MA: Addision- Welsey, 1974
[32] J.C.Bezdek, Pattern recognition with fuzzy objective function algorithms, Plenum Press, New York, 1981
[33] R.Krishnapuram and J.M.Kell, The possilistic c-means algorithm: insights and recommendation, IEEE Trans. FS, 1996, 4(3): 385-393
[34] R.Krishnapuram and J.M.Kell, A possilistic approach to clustering, IEEE Trans. FS, 1993, 1(2): 98-110
[35] S.Grossberg, Adaptive pattern classification and universal recoding: II. Feedback, oscillation, olfaction, and illusions, Biol.Cybern, 1976(23): 187-207
[36] T.Kohonen, Self-organization and associative memory, Berlin: Spring-Verlag, 1984
[37] G.A.Carpenter, S.Grossberg and D.B.Rosen, Fuzzy ART: Fast stable learning and categorization of analog patterns by an adaptive resonance system. NN, 1991(4): 759-771
[38] N.R.Pal, J.C.Bezdek and E.C.K.Tsao, Generalized clustering networks and Kohonen’s self-organization, IEEE Trans. NN, 1993, 4(4): 549-557
[39] E.C.K.Tsao, J.C.Bezdek and N.R.Pal, Fuzzy Kohonen clustering networks. PR, 1994, 27(5): 757-767
[40] K.S.Asultan and S.Z.Selim, A global algorithm for the fuzzy clustering problem, PR, 1993, 26(9): 1357-1361
[41] K.Rose, A deterministic annealing approach to clustering, PRL. 1990(11): 589-594
[42]高新波.基于进化计算和神经网络的模糊聚类新算法研究: [硕士论文].西安:西安电子科技大学, 1996
[43]李文化,模糊聚类新算法与模糊聚类神经网络: [博士论文].西安:西安电子科技大学, 1995
[44] G.P.Babu and M.N.Murty. Clustering with evolution strategies, PR, 1994, 2(27): 321-329
[45] A.M.Bensaid, L.O.Hall, and J.C.Bezdek. Partially supervised clustering for image segmentation, PR, 1996, 29(5): 859-871
[46] E.Y.Shin. A new art-based neural architecture for pattern classification and image enhancement without prior knowledge, PR, 1992, 25(5): 533-542
[47] Zezzhen Huang and A.Kuh. A combined self-organizing feature map and multi-layed perception for isolated word recognition. IEEE Trans.SP, 1992, 40: 2651-2657
[48]许俊刚,柯有安.自组织神经网络雷达目标识别的研究.北京理工大学学报, 1992, 12: 162-167
[49] J.I.Minnix. A multilayered self-organizing artificial neural network for invariant pattern recognition. IEEE Trans, Knowledge and Data Enginerring, 1992, 4(2):162-167
[50]毛国君,段立娟,王石等.数据挖掘原理与算法.北京:清华大学出版社, 2005: 1-1
[51]袁玉波.数据挖掘与最优化技术及其应用.北京:科学出版社, 2007: 2-3
[52] Pan Q K, Tasgetiren M F, Liang Y Ch. A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem. Computers and Operations Research, 2008, 35(9): 2807-2839
[2] R.Eberhart, J.Kennedy. A New Optimizer Using Particle Swarm Theory. In Proceedings of 6th International Symposium on Micro Machine and Human Science, 1995: 39-43
[3] R.Eberhart, Y.Shi. Comparison between genetic algorithms and particle swarm optimization. Lecture Notes in Computer Science, In Proceedings of the 7th international Conference on Evolutionary Programming VII, 1998: 611-616
[4] F.Van den Bergh. An Analysis of Particle Swarm Optimizers. Ph.D. thesis, University of Pretoria, 2002
[5] M.Clerc, J.Kennedy. The particle swarm: Explosion stability and convergence in a multi-dimensional complex space. IEEE Trans Evolution Compute, 2002, 6(1): 58-73
[6] I.C.Trelea. The particle swarm optimization algorithm: convergence analysis and parameter selection. Information Processing Letters, 2003, 85 (6): 317-325
[7] Y.Shi, R.C.Eberhart. A modified particle swarm optimizer. Institute of Electrical and Electronics Engineers. 1998(5): 69-73
[8] Y.Shi, R.C.Eberhart. Parameter selection in particle swarm optimization. Lecture Notes In Computer Science; Vo1. 1447, In Proceedings of the 7th International Conference on Evolutionary Programming VII, Springer-Verlag London, UK, 1998: 591-600
[9] Y.Shi, R.C.Eberhart. Empirical study of particle swarm optimization. Institute of Electrical and Engineers, 1999(7): 1945-1950
[10] M.Clerc. The swarm and queen: Towards a deterministic and adaptive particle swarm optimization. Institute of Electrical and Electronics Engineers, 1999(7): 1951-1957
[11] R.C.Eberhart, Y.Shi. Comparing inertia weights and constriction factors in particle swarm optimization. Institute of Electrical Engineers, 2000(7): 84-88
[12] Y.Shi, R.C. Eberhart. Fuzzy adaptive particle swarm optimization. Institute of Electrical and Electronics Engineers, 2001(5): 101-106
[13]张丽军,俞欢军,陈德钊等.粒子群优化算法的分析与改进.信息与控制, 2004, 33(5): 513-517
[14] I.C.Siarry. Nonlinear inertia weight variation for dynamic adaptation in particle swarm optimization. Computers and Operations Research, 2006, 33(3): 859-871
[15] M.Lovbierg, T.K.Rasmussen, and T.Krink. Hybrid particle swarm optimizer with breeding and subpopulations. Institute of Electrical and Electronics Engineers, 2001(7): 115-118
[16] N.Higashi, H.Iba. Particle swarm optimization with Gaussian mutation. Institute of Electrical and Electronics Engineers, 2003(4): 72-79
[17]吕振肃,侯志荣.自适应变异的粒子群优化算法.电子学报, 2004, 32(3): 416-420
[18]李宁,孙德宝,岑翼刚等.带变异算子的粒子群优化算法.计算机工程与应用, 2004, 40(17): 12-14, 35
[19] P.J.Angeline. Using selection to improve particle swarm optimization. Institute of Electrical and Electronics Engineers, 1998(5): 84-89
[20]吴晓军,薛惠锋,李憋等. GA-PSO混合规划算法.西北大学学报(自然科学版), 2005, 35(1): 39-43
[21]高鹰,谢胜利.基于模拟退火的粒子群优化算法.计算机工程与应用, 2004, 40(1): 47-50
[22]高尚,杨静宇,吴小俊等.基于模拟退火算法思想的粒子群优化算法.计算机应用与软件, 2005, 22(1): 103-104
[23]窦全胜,周春光,马铭.粒子群优化算法的两种改进策略.计算机研究与发展, 2005, 42(5): 897-904
[24]高鹰,谢胜利.混沌粒子群优化算法.计算机科学, 2004, 31(8): 13-15
[25]杨俊杰,周建中,喻菁等.基于混沌搜索的粒子群优化算法.计算机工程与应用, 2005, 41(16): 69-71
[26] C.W.Jiang, B.Etorre. A self-adaptive chaotic particle swarm algorithm for short term hydroelectric system scheduling in deregulated environment. Energy Conversion and Management, 2005, 46(17): 2689-2696
[27] J.Kennedy, R.Eberhart. A discrete binary version of particle swarm optimizationalgorithm. In Proceedings of the 1997 conference on Systems, Man, and Cybernetics (SMC’97), 1997: 4104-4109
[28] C.K.Mohan, B.Al-kazemi. Discrete particle swarm optimization. In Proceedings of the Workshop on Particle Swarm Optimization 2001, Indianapolis, 2001
[29] R.C.Dubes and A.K.jain, Algorithms for clustering data. Englewood Cliffs, NJ: Prentice Hall, 1988
[30] R.O.Duda and P.E.hart, Pattern classification and sence analysis, John Wiley and Sons, New York, 1973
[31] J.T.tou and R.C.Gonzales, Pattern recognition principles, Readind. MA: Addision- Welsey, 1974
[32] J.C.Bezdek, Pattern recognition with fuzzy objective function algorithms, Plenum Press, New York, 1981
[33] R.Krishnapuram and J.M.Kell, The possilistic c-means algorithm: insights and recommendation, IEEE Trans. FS, 1996, 4(3): 385-393
[34] R.Krishnapuram and J.M.Kell, A possilistic approach to clustering, IEEE Trans. FS, 1993, 1(2): 98-110
[35] S.Grossberg, Adaptive pattern classification and universal recoding: II. Feedback, oscillation, olfaction, and illusions, Biol.Cybern, 1976(23): 187-207
[36] T.Kohonen, Self-organization and associative memory, Berlin: Spring-Verlag, 1984
[37] G.A.Carpenter, S.Grossberg and D.B.Rosen, Fuzzy ART: Fast stable learning and categorization of analog patterns by an adaptive resonance system. NN, 1991(4): 759-771
[38] N.R.Pal, J.C.Bezdek and E.C.K.Tsao, Generalized clustering networks and Kohonen’s self-organization, IEEE Trans. NN, 1993, 4(4): 549-557
[39] E.C.K.Tsao, J.C.Bezdek and N.R.Pal, Fuzzy Kohonen clustering networks. PR, 1994, 27(5): 757-767
[40] K.S.Asultan and S.Z.Selim, A global algorithm for the fuzzy clustering problem, PR, 1993, 26(9): 1357-1361
[41] K.Rose, A deterministic annealing approach to clustering, PRL. 1990(11): 589-594
[42]高新波.基于进化计算和神经网络的模糊聚类新算法研究: [硕士论文].西安:西安电子科技大学, 1996
[43]李文化,模糊聚类新算法与模糊聚类神经网络: [博士论文].西安:西安电子科技大学, 1995
[44] G.P.Babu and M.N.Murty. Clustering with evolution strategies, PR, 1994, 2(27): 321-329
[45] A.M.Bensaid, L.O.Hall, and J.C.Bezdek. Partially supervised clustering for image segmentation, PR, 1996, 29(5): 859-871
[46] E.Y.Shin. A new art-based neural architecture for pattern classification and image enhancement without prior knowledge, PR, 1992, 25(5): 533-542
[47] Zezzhen Huang and A.Kuh. A combined self-organizing feature map and multi-layed perception for isolated word recognition. IEEE Trans.SP, 1992, 40: 2651-2657
[48]许俊刚,柯有安.自组织神经网络雷达目标识别的研究.北京理工大学学报, 1992, 12: 162-167
[49] J.I.Minnix. A multilayered self-organizing artificial neural network for invariant pattern recognition. IEEE Trans, Knowledge and Data Enginerring, 1992, 4(2):162-167
[50]毛国君,段立娟,王石等.数据挖掘原理与算法.北京:清华大学出版社, 2005: 1-1
[51]袁玉波.数据挖掘与最优化技术及其应用.北京:科学出版社, 2007: 2-3
[52] Pan Q K, Tasgetiren M F, Liang Y Ch. A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem. Computers and Operations Research, 2008, 35(9): 2807-2839