遗传算法和粒子群算法的现状及发展策略研究

鲁欣欣，王淮冬

（1.吉林工商学院基础教研部，吉林 长春 130507；2.长春工业大学 电气与电子工程学院，吉林 长春 130012）

0 引言

近几年，智能算法已经广泛应用于电力、医疗、农业、汽车等领域，部分替代了传统的人工控制，并已研究出较为成熟的智能算法和基于智能算法智能化的解决方案。本文主要介绍智能算法中具有代表性的两种智能算法—遗传算法和粒子群算法。

1 智能算法的发展

智能算法又被称为“软计算”，是人们通过对已发现的自然规律和一些自然现象进行总结，根据其原理，模仿求解实际需要的问题的计算方法。简单来说，智能算法是仿生学的一个方面，通过仿生原理进行设计，例如遗传算法、粒子群算法、神经网络算法等，都是利用仿生原理设计的智能算法。

2 遗传算法的发展历程

遗传算法（GA）最早于20世纪70年代提出，该算法是根据自然规律中生物的优胜劣汰进化演变来的[1]，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法主要是用数学中概率论的知识解决问题。通过计算机模拟运算，将求最优解问题转换成染色体基因的交叉、变异的过程[2]；利用优胜劣汰的规则筛选所需的适应值，将不合格的数据返还，再次经历交叉、变异的过程。在求解较为复杂的组合优化问题时，相对一些常规的优化算法，通常能够较快地获得较好的优化结果。遗传算法已广泛地应用于车间调度、机器仿真、信号处理等领域。

2.1 遗传算法特点

在解决优化和搜索问题上，遗传算法和传统算法最大的不同就是利用概率理论对数据进行处理。所以遗传算法在结果上具有猜测性，并不是确定的值。该算法利用遗传学中的交叉变异原则对解决问题的算子重新编码，筛选合适的算子迭代出最优解。遗传算法能在众多的智能算法中脱颖而出是因为该算法搜索解的方式。遗传算法是以集合的方式将数据迭进行代求解的，解决多解最优的问题效率极高[3]，降低了陷入局部最优解的风险，并且算法更容易被编码运行。

2.2 遗传算法的不足

编码的不规范会对其准确性造成极大影响。单一的遗传算法编码不能全面地将优化问题的约束表示出来。若增加约束条件，必然需要对编码重新进行筛选，这样一来，大大增加了计算时间。虽然遗传算法更容易得出全局最优解，但是其算法的运算效率特别低，运算过程相对复杂。在计算过程中时常发生收敛过早的情况影响计算结果。目前针对遗传算法的计算精度，收敛速度还没有成熟可靠的设计方案。

2.3 遗传算法的改进与应用

遗传算法的缺点主要是运算效率低和收敛精度差。所以遗传算法的改进方向很明显，一是改进算法结构，提高运算效率，二是改进遗传操作，提高算法的收敛精度。

以应用在调度规划上的改进方式为例。标准的遗传算法是按选择、交叉、变异的顺序结构进行运算，所以执行操作的效率很低。改进的遗传算法在结构上将变异操作从交叉操作环节分离出来，与交叉操作并列运行，大大提高了算法的寻优速度。在操作上首先对交叉操作进行改进，以“门当户对”的原则对个体进行配对，以单点交叉的方式代替原有的交叉方式，这样可以削弱遗传算法在寻优过程中出现抖动的概率。其次对变异操作进行改进，在变异的操作中利用调度规划中出现的混沌序列进行适当次数的迭代，得到变异的新染色体。变异操作的改进是弥补对交叉改进出现的收敛早熟的漏洞，降低算法陷入局部最优解的风险。从遗传算法的改进方式可以看出，改进的方式还是较为单一，并且仅限应用于对调度规划中遗传算法的改进。

3 粒子群算法的发展历程

粒子群优化算法（PSO）是通过模拟鸟群觅食行为而发展起来的一种基于群体协作的随机搜索算法。PSO可以和其他优化算法进行结合且连通性特别好。PSO中，每一只鸟都代表一个需要搜索解决的问题[4]。一般将这样的鸟称之为搜索空间中的“粒子”。所有的粒子都有一个由被优化的函数决定的适应值，每个粒子还有一个速度决定他们飞翔的方向和距离，粒子们追随当前的最优粒子在解空间中搜索。

3.1 粒子群算法特点

粒子群算法和遗传算法有很多共同之处，但粒子算法运算结构十分简单且运算效率高。因为PSO不需要对数据进行交叉和变异操作，所以PSO算法的运算效率特别高，能更快速地收敛到适应值。PSO是通过更新迭代每个粒子在空间中的位置和速度来搜索最优解的，所以粒子群算法的精确度迭代次数和粒子的位置以及速度有关。粒子群算法能得到广泛应用也和算法特有的信息共享以及单项信息流动的属性有关。在全局中，所有粒子共享自己的位置，跟随整个搜索范围内最佳位置求取最优解，大大缩短了运算时间，提高了运算效率。

3.2 粒子群算法的不足

粒子群算法处理多解问题的表现不是很好，特别是处理多样性最优解的问题上所得到的优解值略显单一。对于复杂函数的算子的选择比较麻烦。对于以上问题，目前通过改进多目标粒子群算法和改进权重PSO算法等实用性更强地改进PSO算法[5]。很多改进后的PSO算法针对不同优化问题表现的更有针对性，收敛速度更快，优解精度更高，还解决了遗传算法处理不了的问题。

3.3 粒子群算法的改进与应用

粒子群算法的优化比起其他智能算法的改进升级更容易。主要是因为其实现起来非常简单，而且需要设置的参数较少；待优化问题的维数对算法本身的影响不大，所以更容易被改进升级，实现多目标问题的优化。

以多目标优化的粒子群算法的改进方式为例。正常所提到的粒子群算法是单目标算法，由于其收敛快速，也容易陷入局部最优解的险境；同样地，多目标的寻优也有这样的问题，因此采用二者相结合的改进方式解决算法容易陷入局部最优解的问题。主要从以下4个方面对算法进行改进。

（1）在优化过程中，将原有的从整个空间中对局部搜索的方式改变为从多个相邻的小集合的方式加强对局部的搜索，保持解的多样性，使解在空间中分布得更加均匀，提高对领导粒子选择的质量，从而提高收敛速度。

（2）在保持解的多样性的过程中，改进的方式就比较多。可以将空间分解成多个子空间，有利于保持粒子的多样性；也可以和量子理论结合，辅助粒子迭代到全局最优位置，在保持种群多样的同时，加快收敛到全局最优解的时间；还可以基于博弈机制，筛选出优质的粒子，有利于保持种群的多样性。

（3）从收敛性上提高精确度及速度。在进行单目标优化时收敛速度很快，但由于目标数和空间维度的增加，收敛速度也会随之降低。可通过改进惯性权重系数和学习因子加快多目标的收敛速度；也可以引入新的策略和其他智能算法结合提高算法在整个空间的搜索速度，减少种群多样性的流失；还可以利用粒子群算法信息共享的特点对种群进行划分，通过各个子种群的信息共享保持多样性的同时提高收敛速度。

（4）对迭代公式和运算结构进行改进。这一方面的改进主要针对优化问题的需要，制定一套有针对性的迭代公式、参数、扩展运算结构。

4 结语

本文介绍了智能算法的由来，重点介绍了遗传算法和粒子群算法的优缺点。针对粒子群算法存在的不足总结出了几种优化改进的PSO算法。

目前的智能算法研究水平还很难使机器设备达到真正的人工智能，只是对各种行为进行模仿，但智能计算将在未来处于一个快速发展的阶段。算法不仅限于对自然规律的仿生，还需要与人的思维逻辑结合来实现真正的人工智能。智能算法将会逐步改变人们的生活和生产方式。