基于粒子群算法的改进遗传算法

摘要 本文假设优化问题的最优解在整个解空间中服从均匀分布,并在此基础上,按照最大熵原则,最优解应该更加趋向于较优解。为了能够更快地搜索到最优解,用粒子群算法[1]代替了遗传算法的交叉算子。得到了一个应用更加广泛的改进遗传算法。最后的数值实验结果表明,改进后的算法不管是在收敛速度还是精度上都明显优于原有的算法,说明改进后的算法确实是有效可行的。

关键词 遗传算法;交叉算子;变异算子

中图分类号 TP391.4 文献标识码 A 文章编号1674-6708(16)-0005-02

Abstract This article assumes that the optimal solutions are uniform distributed in the whole solution space, and thereby, in accordance with the principle of maximum entropy, the optimal solution tend to be better. To search the optimal solution more quickly, we employ Particle Swarm Optimization[1] instead of the crossing operator of genetic algorithm, and get a improved genetic algorithm

Which will extensively applied. Finally, the results of numerical experiment show that the improved algorithm is obviously better than the original algorithm whether in convergence speed or accuracy, indicating the improved algorithm is indeed feasible and effective.

KeywordsGenetic Algorithm; Crossover Operator; Mutation Operator

0 引言

遗传算法是根据自然界的“物竞天择,适者生存”现象二提出的一种随机搜索算法。1975年,Holland教授在他的专著《Adaptation in Natural and Artificial Systems》[2]中,首次系统地提出了遗传算法(GA or Genetic Algorithm)的基本原理,标志着遗传算法的诞生。该算法将优化问题看作是自然界中生物进化过程,通过模拟大自然中生物进化过程中的遗传规律,来达到寻优的目的。

进入90年代,遗传算法作为一种新的全局优化搜索方法,适用于处理传统搜索方法难以解决的复杂的和非线性的问题、组合优化、机器学习、自适应控制和人工生命等方面,都得到了极为广泛的应用[3-8],是21世纪有关智能计算的关键技术之一。

1995 年Eberhart 博士和Kennedy 博士提出了粒子群优化算法。 这种算法以其实现容易、精度高、收敛快等优点引起了学术界的响应,并且在解决某些实际问题时,展示了其优越性。粒子群优化算法是一种新的进化算法,与遗传算法相似,它也是从随机解出发,通过迭代寻找最优解,它也是通过适应度来评价解的优劣。但是它比遗传算法规则更为简单,它没有遗传算法的“交叉”和“变异”操作,它通过追随当前搜索到的最优值来寻找全局最优。

根据坐标的可平移性,从整体上看,我们可以假设优化问题的最优解在整个解空间服从均匀分布。按照最大熵原则,最优解应该更加趋向于较优解。为了能够更快地搜索到最优解,本文将粒子群算法和遗传算法相结合。得到了一个应用更加广泛的改进遗传算法。

1 初始化染色体

在遗传算法中,初始染色体是随机产生的,最优化问题的解转换成染色体一般有两种表示方法:二进制向量或浮点向量。使用二进制向量作为一个染色体来表示决策变量的真实值,向量的长度依赖于要求的精度,但使用二进制代码的必要性已经受到了一些批评。在求解复杂优化问题时,二进制向量表示结构有时不太方便。

另一种表示方法是用浮点向量,每一个染色体有一个浮点向量表示,其长度与解向量相同。用向量表示最优解问题的解,其中是维数。则相应的染色体是。

对于每一个染色体,我们选取已知的可行解做随机的扰动,这样便得到一个染色体。如果如此得到的染色体可行,即说明满足约束条件。对于每一个染色体在约束条件中,我们可以得出可行集中的一个内点,记为。我们定义一个足够大的数,以保证遗传操作遍及整个可行集。当然的选取依赖于不同的决策问题。在中,首先随机选择一个方向,如果满足不等式约束,则将作为一个染色体,否则,置为0到之间的随机数,直到可行为止。由于是内点,所以在有限步内,总是可以找到满足不等式约束的可行解。重复以上过程次,从而产生个初始染色体,其中为种群规模。

2 适应函数

比较常用的评价函数是基于序的评价函数,我们将一代种群的染色体按照从好到差的顺序排列成。在极大化问题中,这个顺序就是指对应目标函数值由大到小排列染色体,在极小化问题中则正好相反。为了得到每个染色体的适应度,我们根据这个顺序给出如下的评价函数,

其中是一个事先给定的数。可以看到,机会越大的解适应值也越大。

3 选择过程

选择过程是以个扇区的旋转赌轮为基础的。赌轮上的刻度是按各染色体的适应值来划分的,染色体的适应值越大,则其在赌轮上所占的面积就越大,该染色体被选中的概率也就越大,每旋转一次都会为新的种群选择一个染色体。但是为了避免早熟现象,在这里,我们结合粒子群算法的优越性,首先选出最佳染色体。然后,令,对于各染色体,令其累次概率为

我们在区间 中随机产生一个实数。如果满足,则选择。重复上述过程,直至生成个新的染色体终止,于是我们得到一个新的种群。

4 交叉算子

首先给定交叉概率,则每次种群中平均有个染色体进行交叉操作。对各染色体我们随机产生[0,1]上的一个随机数p,若p

其中随机数。经过上述交叉操作,我们可以得到一个子代染色体。最后,我们可以用约束条件对它进行可行性检验。若该子代染色体满足约束条件,则用子代染色体替代原染色体,否则,

,

重新检验该子代染色体的可行性,若还是不满足越深条件,则重新产生新的随机数,再次进行交叉操作,直到新的可行染色体出现或者达到最大交叉上限,则停止。这样,我们几可以得到个新的染色体,。

5 变异算子

变异操作是产生新染色体的辅助方法,但它决定了遗传算法的全局搜索能力,可以保证群体的多样性,防止早熟现象。同样给定一个变异概率,并从区间上随机产生,若,则该染色体被选中作为父代,进行变异操作。对于各需要变异的父代染色体,在空间中随机选取一个变异方向和步长(足够大),其中向量与染色体维数相同,则变异后的染色体。同理,我们对进行可行性和优越性检验。如果通过检验则用替换掉,否则,,继续进行变异操作,直到用替换掉或者达到最大变异次数,则停止变异并保留。这样,我们通过变异可以得到新的种群。

6 遗传算法步骤

步骤1:根据约束条件随机产生个染色体,即种群。

步骤2:按照转盘赌原则,随机选取一个最佳父代染色体和其它个父代染色体作为交叉种群(交叉种群不能包含最佳父代染色体)。

步骤3:对于每个父代染色体都以概率与最佳染色体进行交叉运算,即随机生成,若,则对应的染色体将与最佳染色体进行交叉运算,否则不进行交叉运算。

步骤4:将所新得到的各子代染色体以概率进行变异操作,即随机生成,若,则对应的染色体进行变异运算,否则不进行变异运算。

步骤5:更新父代染色体,即在子代染色体中,择优选取较好的染色体代替原来的父代染色体,作为下次交叉变异的父代染色体,并计算各自相应的适应值。

步骤6: 重复步骤2―步骤5知道达到精度要求,或者达到约定的最大循环次数。

7 数值实验

7.1 实验模型

例1 现运用遗传算法求解以下最大值问题,

对于这个问题,我们可以直接将解是为遗传迭代的染色体。显然染色体属于集合内

。

7.2 Matlab实验结果

运用Matlab软件来实现遗传算法,并设定相应的各参数如下:

最大交叉、最大变异次数、最大变异半径以及最大遗传迭代次数均设为1 000。利用Matlab7.6得到结果如下:

遗传迭代次数:

最佳染色体:

最优值:1.9805

显然这一结果要优于Liu[9]给出的遗传迭代400次的结果:

最佳染色体:

最优值:1.980

结果误差曲线图:

图1 结果误差曲线图

其中横坐标为遗传迭代次数,纵坐标为每次迭代的误差取值。

8 结论

本文按照最大熵原理,用粒子群算法代替了遗传算法的交叉算子,得到了一个应用更加广泛的改进遗传算法。最后的数值实验结果也表明,改进后的算法不管是在收敛速度还是精度上都明显优于原有的算法,说明该算法确实是有效可行的。实际上本文给出了一种判断算法优越性的新思路。

参考文献

[1]胡辉.粒子群优化算法的Visual C++实现研究[J].科技广场,2008(5).

[2]Goldberg D E.Genetic Algorithms in Search, Optimization and Machine Learning[M]. MA:Addison-Wesley, 1989.

[3]Koza J R.Genetic Programming[M].Cambridge,MA:MIT Press,1992.

[4]Koza J R.Genetic Programming II[M].Cambridge,MA: MIT Press,1994.

[5]Michalewicz Z.Genetic Algorithms+ Data Structures=Evolution Programs[M]. New York:Springer-Verlag,1996.

[6]Yoshitomi Y,Ikemoue H,Takaba T.Genetic algorithm in uncertain environments for solving stochastic programming problem[J].Journal of the Operations Research Society of Japan,2000,43(2):266-290.

[7]邢文训,谢金星.现代优化计算方法[M].北京:清华大学出版社,1999.

[8] Zadeh L A. Fuzzy sets as a basis for a theory of possibility[J]. Fuzzy Sets and Systems, 1978, 1: 3-28.

[9]Liu B,Theory and Practice of Uncertain Programming,2nd ed.,Springer-Verlag,Berlin,2009.