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

石双龙，林 亮，李红菊

桂林理工大学理学院，广西 桂林 541004

0 引言

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

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

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

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

1 初始化染色体

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

另一种表示方法是用浮点向量，每一个染色体有一个浮点向量表示，其长度与解向量相同。用向量 x=(x1，x2，⋅⋅⋅,xn)表示最优解问题的解，其中是维数。则相应的染色体是 V=(x1，x2，⋅⋅⋅,xn)。

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

2 适应函数

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

其中a∈(0,1)是一个事先给定的数。可以看到，机会越大的解适应值也越大。

3 选择过程

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

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

4 交叉算子

首先给定交叉概率，则每次种群中平均有pc∗popsize个染色体进行交叉操作。对各染色体我们随机产生[0，1]上的一个随机数p，若p＜pc，则该染色体被选中作为父代可以进行交叉操作。将选中的染色体进行编组，。以第一个父代染色体为例，显然，两个子代染色体V1和V0是两个父代染色体的线性组合，写成向量形式即

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

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

5 变异算子

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

6 遗传算法步骤

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

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

步骤3：对于每个父代染色体都以概率pc与最佳染色体进行交叉运算，即随机生成r∈(0,1)，若 r＜pc，则对应的染色体将与最佳染色体进行交叉运算，否则不进行交叉运算。

步骤4：将所新得到的各子代染色体以概率Pm进行变异操作，即随机生成r∈(0,1)，若 r＜pm，则对应的染色体进行变异运算，否则不进行变异运算。

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

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

7 数值实验

7.1 实验模型

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

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

7.2 Matlab实验结果

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

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

遗传迭代次数：i=135

最佳染色体：( x1， x2， x3)=(0.6332,0.3990,0.3058)

最优值：1.9805

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

最佳染色体：( x1， x2， x3)=(0.636,0.395,0.307)

最优值：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.