粒子群算法的改进及其在基因表达数据聚类中的应用
|
摘要
粒子群优化算法是一种模拟鸟类群体行为的智能优化算法,现已成为进化算法的一个新的重要分支。粒子群算法思想直观、实现简单而且具有很高的执行效率,自提出以来,受到国内外众多学者的关注。但是,粒子群算法发展历史尚短,理论研究不深,在处理特定问题及应用中还存在一些问题。于是,粒子群优化算法的改进和为其开拓新的应用领域成为目前优化算法研究的热点。
首先,本文提出了一种基于粒子成长阶段的粒子群改进算法。该算法采用变异机制使得粒子群能有效地跳出局部极值;采用人在社会中扮演的角色以及人的成长过程来定义粒子,通过划分粒子的成长阶段,使得处于不同阶段的粒子采用不同的学习因子。利用一组具有代表性的基准优化测试函数对该算法进行测试,以此来验证该算法的有效性。
其次,本文提出了一种基于双重变异的粒子群改进算法。避免粒子群早熟收敛的主要措施是保持种群多样性或者引入跳出局部极值点的机制。该算法采用非线性动态调整惯性权值和自适应双重变异机制,使得算法利于平衡粒子的开发和探测能力并且能有效的跳出局部极值。利用一组具有代表性的Benchmark测试函数对该算法进行测试,以此来验证该算法的有效性。
最后,本文探讨了粒子群算法在基因表达数据聚类分析上的应用。将改进后的粒子群算法与K-means聚类算法相结合,提出一种基于粒子群和K-means的混合聚类算法,以期在一定程度上克服K-means聚类算法的缺点。利用酵母菌基因表达数据聚类分析验证了该混合算法的有效性。
As a new branch of evolution algorithm, particle swarm optimization algorithm is an intelligence algorithm, which simulates the swarm behavior of birds. It is simple and can be carried out easily, so it has been widely concerned since proposed. However, as the shorter development history and the less theoretical researching, particle swarm optimization algorithm still has some problems in dealing with some issues. As a result, the improvement of particle swarm optimization algorithm and new areas of its application become central issues during optimization field.
Firstly, an improved particle swarm optimization algorithm based on particles’growth stages is propsed. This algorithm uses mutation mechanism to make particles jump out of the local optimal effectively, and uses the growth process of human to define the particles. Division of growth stages can make particles have different learning factors at different stages. The improved algorithm is tested by a group of Benchmark functions to verify its validity.
Secondly, another improved particle swarm optimization algorithm based on double mutation is proposed. The main measures of avoiding premature convergence are keeping the population diversity or introducing mechanisms to jump out of local optima. So the improved algorithm adopts two strategies to improve the original PSO, one is adjusting inertia weight dynamically and the other is introducing mutations. The adaptive mutations make particles jump out of local optima effectively, and adjusting to the inertia weight dynamically and nonlinearly is beneficial to balance particles’ability of exploitation and exploration. This improved algorithm is tested by a group of Benchmark functions to verify its validity.
Finally, the application of particle swarm optimization algorithm in gene expression data clustering is discussed. And then a hybrid clustering algorithm is proposed, which integrates the particle swarm optimization algorithm into K-means algorithm, to overcome the disadvantage of K-means algorithm. The wide-known yeast-cells gene datas are used to test the validity of the hybrid clustering algorithm.
首先,本文提出了一种基于粒子成长阶段的粒子群改进算法。该算法采用变异机制使得粒子群能有效地跳出局部极值;采用人在社会中扮演的角色以及人的成长过程来定义粒子,通过划分粒子的成长阶段,使得处于不同阶段的粒子采用不同的学习因子。利用一组具有代表性的基准优化测试函数对该算法进行测试,以此来验证该算法的有效性。
其次,本文提出了一种基于双重变异的粒子群改进算法。避免粒子群早熟收敛的主要措施是保持种群多样性或者引入跳出局部极值点的机制。该算法采用非线性动态调整惯性权值和自适应双重变异机制,使得算法利于平衡粒子的开发和探测能力并且能有效的跳出局部极值。利用一组具有代表性的Benchmark测试函数对该算法进行测试,以此来验证该算法的有效性。
最后,本文探讨了粒子群算法在基因表达数据聚类分析上的应用。将改进后的粒子群算法与K-means聚类算法相结合,提出一种基于粒子群和K-means的混合聚类算法,以期在一定程度上克服K-means聚类算法的缺点。利用酵母菌基因表达数据聚类分析验证了该混合算法的有效性。
As a new branch of evolution algorithm, particle swarm optimization algorithm is an intelligence algorithm, which simulates the swarm behavior of birds. It is simple and can be carried out easily, so it has been widely concerned since proposed. However, as the shorter development history and the less theoretical researching, particle swarm optimization algorithm still has some problems in dealing with some issues. As a result, the improvement of particle swarm optimization algorithm and new areas of its application become central issues during optimization field.
Firstly, an improved particle swarm optimization algorithm based on particles’growth stages is propsed. This algorithm uses mutation mechanism to make particles jump out of the local optimal effectively, and uses the growth process of human to define the particles. Division of growth stages can make particles have different learning factors at different stages. The improved algorithm is tested by a group of Benchmark functions to verify its validity.
Secondly, another improved particle swarm optimization algorithm based on double mutation is proposed. The main measures of avoiding premature convergence are keeping the population diversity or introducing mechanisms to jump out of local optima. So the improved algorithm adopts two strategies to improve the original PSO, one is adjusting inertia weight dynamically and the other is introducing mutations. The adaptive mutations make particles jump out of local optima effectively, and adjusting to the inertia weight dynamically and nonlinearly is beneficial to balance particles’ability of exploitation and exploration. This improved algorithm is tested by a group of Benchmark functions to verify its validity.
Finally, the application of particle swarm optimization algorithm in gene expression data clustering is discussed. And then a hybrid clustering algorithm is proposed, which integrates the particle swarm optimization algorithm into K-means algorithm, to overcome the disadvantage of K-means algorithm. The wide-known yeast-cells gene datas are used to test the validity of the hybrid clustering algorithm.
引文
1 J. J. Hopfield, D. W. Tank. Neural computation of decision in optimization problems. Biological Cybernetics, 1985,52:141-152
2 J. J. Hopfield, D. W. Tank. Computing with neural circuits: A model. Science,1986, 233:625-633
3 S. Abe. Solving inequality constrained combinational optimization problems by the Hopfield neural network. Neural Network, 1992,5:633-670
4 S. Kirkpatrick, J.C.D. Gelatt, M. P. Vecchi. Optimization by simulated annealing. Science, 1983,220:671-680
5 S. Kirkpatrick. Optimization by simulated annealing: quantitative studies. Journal of Statistical Physics, 1984,34:975-986
6 F. Glover. Future paths for integer programming and links to artificial intelligence. Computers and Operators Research, 1986,5:533-549
7 K. Y. Lee, M. A. Sharkaei. Modern Heuristic optimization techniques with applications to power systems. IEEE Power Engineering Society, 2002:45-51
8 F. Glober. Tabu search-Part 1. ORSA Journal on Computing, 1989,1(3):190-206
9 F. Glober. Tabu search-Part 2. ORSA Journal on Computing, 1990,2(1): 4-32
10 R. C. Eberhart, J. Kennedy. Particle swarm optimization. Proceedings of IEEE International Conference on Neural Networks, 1995:1942-1948
11 R. C. Eberhart and J. Kennedy. A new optimizer using particle swarm theory. Proceedings of the Sixth International Symposium on Micro Machine and Human Science, Nagoya, Japan, 1995:39-43
12 J. Kennedy, R. C. Eberhart. A discrete binary version of the Particle swarm algorithm. Proceedings of the World Multi- conference on systemic. Cybernetics and Informatics, Piscataway, NJ, 1997:4104-4109
13 Y. Shi and R. C. Eberhart. A modified particle swarm optimizer. Proceedings of the IEEE International Conference Evolutionary Computation, 1998:69-73
14 Y. Shi and R. C. Eberhart. Empirical study of Particle swarm optimization. Proceedings of World Multi-conference on systemic, Cybernetics and Informatics, Orlando, FL, 2000:1945-1950
15 Y. Shi and R. C. Eberhart. Fuzzy adaptive particle swarm optimization. Proceedings of the 2001 Congress on Evolutionary Computation,Seoul,South Korea, 2001:101-106
16 M. Clerc. The swarm and the queen: towards a deterministic and adaptive particle swarm optimization, Proceedings of the Congress on Evolutionary Computation, Picsaatway: IEE Service Center, 1999:1591- 1597
17 T. A. A. Victoier and A. E.Jeyakumar. Hybrid PSO-SQP for economic dispatch with valve-point effect. Electric Power Systems Research, 2004,71(1):51-59
18 T. K. Rasmussen and T. Krink. Improved Hidden Markov Model training for multiple sequence alignment by a particle swarm optimization-evolutionary algorithm hybrid. Biosystems, 2003,72(12):5-17
19 K. E. Parsopoulos and M. N. Vrahatis. Initializing the particle optimizer using the nonlinear simplex Method .In Grmela, A. and Mastorakis, N.E.(eds.) Advances in Intelligent Systems, Fuzzy System, Evolutionary Computation, WSEAS Press, 2002:216-221
20 C. F. Juang. A hybrid of genetic algorithm and particle swarm optimization for recurrent network design. IEEE Transactions on systems, Man, and Cubernetics-PartB Cybernetics, 2004,34(2):997-1006
21 R. K. Ursem and P. Vadstrup. Parameter identification of induction motors using stochastic optimization algorithms. Applied Soft Computing, 2004:449-644
22 J. J. Xu and Z. H. Xin. An extended particle swarm optimizer. Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium(IPDPS’05), USA, 2005:1-5
23王芳.粒子群算法的研究. [西南大学博士论文]. 2006:25-46
24刘金洋,郭茂祖,邓超.基于雁群启示的粒子群优化算法.计算机科学, 2006,33 (11):166-168
25张世勇,熊忠阳.基于禁忌搜索的混合粒子群优化算法.计算机研究与发展, 2007,44(l):339-343
26周雅兰,王甲海,印鉴.一种基于分布估计的离散粒子群优化算法.电子学报, 2008, 36(6):1242-1248
27 Leandro dos Santos Coelho, Cezar Augusto Sierakowski. A software tool for teaching of particle swarm optimization fundamentals. Advances in Engineering Software, 2008, 39:877-887
28 E. Ozcan, C. K. Mohan. Analysis of a simple particle swarm optimization system. Intelligent Engineering Systems through Artificial Neural Networks, 1998:253-258
29 R. Boyd, P. Recharson. Culture and the evolutionary process. Chicago: University of Chicago Press, 1985:45-72
30 K. E. Parsopoulos, M. N. Vrahatis. Recent approaches to global optimization problems through particle swarm optimization. Natural Computing, 2002:235-306
31李宁,孙德宝,绉彤.基于差分方程的PSO算法粒子运动轨迹分析.计算机学报, 2006, 29(11):2052-2061
32张丽平,胡上旭.粒子群优化算法的理论及实践. [浙江大学博士学位论文]. 2005:25-43
33王凌.智能优化算法及其应用.北京:清华大学出版社, 2001:48 - 49
34王小平,曹立明.遗传算法—理论、算法与软件实现.陕西西安:西安交通大学出版社,2002:105-107
35纪震,廖惠连,吴青华.粒子群算法及应用.科学出版社. 2009:2-87
36吕振肃,侯志荣.自适应变异的粒子群优化算法.电子学报, 2004, 32(3):416-420
37李宁,刘飞,孙德宝.基于带变异算子粒子群优化算法的约束布局优化研究.计算机学报, 2004,27(7):897-903
38 K. E. Parsopoulos, M. N. Vrahatis. Parameter selection and adaptation in unified particle swarm optimization. Mathematical and Computer Modelling, 2007:198-213
39付国江,王少梅,刘舒燕等.含边界变异的粒子群算法.武汉理工大学学报, 2005, 27(9):101-104
40李勇冈,桂卫华,阳春华等.一种弹性粒子群优化算法.控制与决策, 2008,23 (1):95-98
41罗辞勇,陈民铀.克服恋食行为的PSO算法改进研究.控制与决策, 2008,23 (7):776-780
42 J. J. Liang, P. N. Suganthan. Dynamic multi-swarm particle swarm optimizer. Proceedings of the 2005 IEEE Swarm Intelligence Symposium, Pasadena, 2005:127-132
43王巧灵,高晓智,王常虹等.基于克隆选择和粒子群思想的动态多群体优化算法.控制与决策, 2008,23(9):1073-107
44 I. Belitskaya. Finding multiple clustering structures in data, with applications to DNA micrroarraya. The department of statistics and the committee on graduate studies of Stanford University, 2002:12-40
45 S. Seal, S. Komarina, S. Aluru. An optimal hierarchical clustering algorithm for gene expression data. Information Processing Letters, 2005,93:143-147
46 E. A. Femandez, M. Balzarini. Improving cluster visualization in self-organization maps: Application in gene expression data analysis. Computer in Biology and Medicine, 2007,4(3):1-13
47陈黎飞,姜青山.基于层次划分的最佳局类数确定方法.软件学报, 2008,19 (1):62-72
48 K. Y. Yeung, D.R. Haynor and W. L. Ruzzo. Validating clustering for gene expression data. Bioinfornatics, 2001,17(4):309-318
49 S. Marco and F. Francois. The parincipal components analysis of a graph. Dupont Information Systems Research Unit, 2004,13(5):32-36
50 Mauricio Aalvarez and Ricardo Hhenao. Probabilistic kernel principal component analysis through time. Lecture Notes in Computer Science, 2006,42(32):747-754
51 A. Kou and N. Hidemitsu. Self-organizing clustering: A novel non-hierarchical method for clustering large amount of DNA sequences. Genome Informatics, 2003,23(14): 575-576
52 J. B. Mac Queen. Some methods for classification and analysis of multivariate observations. Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability, Berkeley: University of California Press, 1967:281-297
53 S. Tavazoie, J. D. Huges and M. J. Campbell. Systematic determination of genetic network architecture. Nature Genetics, 1999,22(3):281-285
54 S. T. Spellman. Comprehensive identification of cell cyclo-regulated genes of the yeast saccharomyces cerevisiae by microarray hybridization. Molecular Biology of the Cell. 1998,9:3273-3297
2 J. J. Hopfield, D. W. Tank. Computing with neural circuits: A model. Science,1986, 233:625-633
3 S. Abe. Solving inequality constrained combinational optimization problems by the Hopfield neural network. Neural Network, 1992,5:633-670
4 S. Kirkpatrick, J.C.D. Gelatt, M. P. Vecchi. Optimization by simulated annealing. Science, 1983,220:671-680
5 S. Kirkpatrick. Optimization by simulated annealing: quantitative studies. Journal of Statistical Physics, 1984,34:975-986
6 F. Glover. Future paths for integer programming and links to artificial intelligence. Computers and Operators Research, 1986,5:533-549
7 K. Y. Lee, M. A. Sharkaei. Modern Heuristic optimization techniques with applications to power systems. IEEE Power Engineering Society, 2002:45-51
8 F. Glober. Tabu search-Part 1. ORSA Journal on Computing, 1989,1(3):190-206
9 F. Glober. Tabu search-Part 2. ORSA Journal on Computing, 1990,2(1): 4-32
10 R. C. Eberhart, J. Kennedy. Particle swarm optimization. Proceedings of IEEE International Conference on Neural Networks, 1995:1942-1948
11 R. C. Eberhart and J. Kennedy. A new optimizer using particle swarm theory. Proceedings of the Sixth International Symposium on Micro Machine and Human Science, Nagoya, Japan, 1995:39-43
12 J. Kennedy, R. C. Eberhart. A discrete binary version of the Particle swarm algorithm. Proceedings of the World Multi- conference on systemic. Cybernetics and Informatics, Piscataway, NJ, 1997:4104-4109
13 Y. Shi and R. C. Eberhart. A modified particle swarm optimizer. Proceedings of the IEEE International Conference Evolutionary Computation, 1998:69-73
14 Y. Shi and R. C. Eberhart. Empirical study of Particle swarm optimization. Proceedings of World Multi-conference on systemic, Cybernetics and Informatics, Orlando, FL, 2000:1945-1950
15 Y. Shi and R. C. Eberhart. Fuzzy adaptive particle swarm optimization. Proceedings of the 2001 Congress on Evolutionary Computation,Seoul,South Korea, 2001:101-106
16 M. Clerc. The swarm and the queen: towards a deterministic and adaptive particle swarm optimization, Proceedings of the Congress on Evolutionary Computation, Picsaatway: IEE Service Center, 1999:1591- 1597
17 T. A. A. Victoier and A. E.Jeyakumar. Hybrid PSO-SQP for economic dispatch with valve-point effect. Electric Power Systems Research, 2004,71(1):51-59
18 T. K. Rasmussen and T. Krink. Improved Hidden Markov Model training for multiple sequence alignment by a particle swarm optimization-evolutionary algorithm hybrid. Biosystems, 2003,72(12):5-17
19 K. E. Parsopoulos and M. N. Vrahatis. Initializing the particle optimizer using the nonlinear simplex Method .In Grmela, A. and Mastorakis, N.E.(eds.) Advances in Intelligent Systems, Fuzzy System, Evolutionary Computation, WSEAS Press, 2002:216-221
20 C. F. Juang. A hybrid of genetic algorithm and particle swarm optimization for recurrent network design. IEEE Transactions on systems, Man, and Cubernetics-PartB Cybernetics, 2004,34(2):997-1006
21 R. K. Ursem and P. Vadstrup. Parameter identification of induction motors using stochastic optimization algorithms. Applied Soft Computing, 2004:449-644
22 J. J. Xu and Z. H. Xin. An extended particle swarm optimizer. Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium(IPDPS’05), USA, 2005:1-5
23王芳.粒子群算法的研究. [西南大学博士论文]. 2006:25-46
24刘金洋,郭茂祖,邓超.基于雁群启示的粒子群优化算法.计算机科学, 2006,33 (11):166-168
25张世勇,熊忠阳.基于禁忌搜索的混合粒子群优化算法.计算机研究与发展, 2007,44(l):339-343
26周雅兰,王甲海,印鉴.一种基于分布估计的离散粒子群优化算法.电子学报, 2008, 36(6):1242-1248
27 Leandro dos Santos Coelho, Cezar Augusto Sierakowski. A software tool for teaching of particle swarm optimization fundamentals. Advances in Engineering Software, 2008, 39:877-887
28 E. Ozcan, C. K. Mohan. Analysis of a simple particle swarm optimization system. Intelligent Engineering Systems through Artificial Neural Networks, 1998:253-258
29 R. Boyd, P. Recharson. Culture and the evolutionary process. Chicago: University of Chicago Press, 1985:45-72
30 K. E. Parsopoulos, M. N. Vrahatis. Recent approaches to global optimization problems through particle swarm optimization. Natural Computing, 2002:235-306
31李宁,孙德宝,绉彤.基于差分方程的PSO算法粒子运动轨迹分析.计算机学报, 2006, 29(11):2052-2061
32张丽平,胡上旭.粒子群优化算法的理论及实践. [浙江大学博士学位论文]. 2005:25-43
33王凌.智能优化算法及其应用.北京:清华大学出版社, 2001:48 - 49
34王小平,曹立明.遗传算法—理论、算法与软件实现.陕西西安:西安交通大学出版社,2002:105-107
35纪震,廖惠连,吴青华.粒子群算法及应用.科学出版社. 2009:2-87
36吕振肃,侯志荣.自适应变异的粒子群优化算法.电子学报, 2004, 32(3):416-420
37李宁,刘飞,孙德宝.基于带变异算子粒子群优化算法的约束布局优化研究.计算机学报, 2004,27(7):897-903
38 K. E. Parsopoulos, M. N. Vrahatis. Parameter selection and adaptation in unified particle swarm optimization. Mathematical and Computer Modelling, 2007:198-213
39付国江,王少梅,刘舒燕等.含边界变异的粒子群算法.武汉理工大学学报, 2005, 27(9):101-104
40李勇冈,桂卫华,阳春华等.一种弹性粒子群优化算法.控制与决策, 2008,23 (1):95-98
41罗辞勇,陈民铀.克服恋食行为的PSO算法改进研究.控制与决策, 2008,23 (7):776-780
42 J. J. Liang, P. N. Suganthan. Dynamic multi-swarm particle swarm optimizer. Proceedings of the 2005 IEEE Swarm Intelligence Symposium, Pasadena, 2005:127-132
43王巧灵,高晓智,王常虹等.基于克隆选择和粒子群思想的动态多群体优化算法.控制与决策, 2008,23(9):1073-107
44 I. Belitskaya. Finding multiple clustering structures in data, with applications to DNA micrroarraya. The department of statistics and the committee on graduate studies of Stanford University, 2002:12-40
45 S. Seal, S. Komarina, S. Aluru. An optimal hierarchical clustering algorithm for gene expression data. Information Processing Letters, 2005,93:143-147
46 E. A. Femandez, M. Balzarini. Improving cluster visualization in self-organization maps: Application in gene expression data analysis. Computer in Biology and Medicine, 2007,4(3):1-13
47陈黎飞,姜青山.基于层次划分的最佳局类数确定方法.软件学报, 2008,19 (1):62-72
48 K. Y. Yeung, D.R. Haynor and W. L. Ruzzo. Validating clustering for gene expression data. Bioinfornatics, 2001,17(4):309-318
49 S. Marco and F. Francois. The parincipal components analysis of a graph. Dupont Information Systems Research Unit, 2004,13(5):32-36
50 Mauricio Aalvarez and Ricardo Hhenao. Probabilistic kernel principal component analysis through time. Lecture Notes in Computer Science, 2006,42(32):747-754
51 A. Kou and N. Hidemitsu. Self-organizing clustering: A novel non-hierarchical method for clustering large amount of DNA sequences. Genome Informatics, 2003,23(14): 575-576
52 J. B. Mac Queen. Some methods for classification and analysis of multivariate observations. Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability, Berkeley: University of California Press, 1967:281-297
53 S. Tavazoie, J. D. Huges and M. J. Campbell. Systematic determination of genetic network architecture. Nature Genetics, 1999,22(3):281-285
54 S. T. Spellman. Comprehensive identification of cell cyclo-regulated genes of the yeast saccharomyces cerevisiae by microarray hybridization. Molecular Biology of the Cell. 1998,9:3273-3297