最优化理论与算法

最优化理论与算法

-

遗传算法研究综述

罗九晖统计学132111059

优化是科学研究、工程技术以及经济管理等等领域的重要研究对

象。优化问题广泛存在于各个领域中，学者对该问题的求解研究从未

停止。

一、优化算法概述

优化问题是个古老的课题，目前，对优化问题的求解研究主要有

三个方向：

（1）经典精确优化算法（数值最优化）

该算法主要用来处理目标函数以及约束条件有具体的解析

表达式且存在导数的情况。它是先利用求导或者变分法得到极值点存

在的必要条件（通常是一组方程或不等式），然后再求解细方程或不

等式。

（2）经典近似优化算法（解析最优化）

通过最优解的性质建立迭代公式求最优解。

（3）智能算法（仿生算法、演化算法、进化算法）

数值优化算法和解析优化算法必须建立在目标函数存在导

数的性质条件下进行，而在实际中碰到的很多优化问题的目标函数并

不存在导数。因此，近年来，学者们以模拟物质变化过程或模拟生命

体而设计的搜索方式为基础，提出各种算法，这类算法就是智能算法。

二、智能算法概述

智能是在任意给定的环境和目标条件下，正确制定决策和实现目

标的能力。智能优化算法则是将生物行为与计算机科学相结合，解决

优化问题，制定最优化决策。目前，智能算法有以下几类：

（1）模拟退火算法

模拟退火算法是基于蒙特卡洛迭代求解策略的一种随机寻

优算法,其出发点是基于物理中固体物质的退火过程与一般组合优化

问题之间的相似性(即:退火过程中,固体最终达到能量最小的状态,对

应于优化算法最终找到了最优解)而设计的一种智能优化算法,该算法

将固体的退火过程与优化问题的求解过程有机的结合起来,因此该算

法被称为模拟退火算法。

（2）禁忌搜索算法

所谓禁忌就是禁止重复前面的工作。为了回避局部邻域搜

索陷入局部最优的主要不足,禁忌搜索算法用一个禁忌表来记录已经

达到过的局部最优点,在下一次的搜索中,利用禁忌表中的信息不再或

有选择地搜索这些点,以此来跳出局部最优点。

（3）蚁群算法

蚂蚁在运动过程中,能够在它所经过的路径上留下该种物

质,而且能够感知这种物质的存在及其强度,并以此指导自己的运动

方向。蚂蚁倾向于朝着该物质强度高的方向移动。因此,由大量蚂蚁

组成的蚁群的集体行为便表现出一种信息正反馈现象:某一路径上走

过的蚂蚁越多,则后来者选择该路径的概率就越大。蚂蚁个体之间就

是通过这种信息的交流达到搜索食物的目的。蚁群算法就是基于这样

启发而设计出来的一种智能优化算法。

（4）粒子群优化算法

群体搜寻最优目标时,每个个体将参照当前群体中曾有的最

优个体,和自身曾经达到的最优位置调整下一步的搜寻方向,这就是粒

子群优化算法。

（5）人工神经网络

人工神经网络是对人脑的模拟。

（6）遗传算法

遗传算法是一种通过模拟生物界自然选择和遗传机制的随

机搜索算法。

三、遗传算法概述

遗传算法是模拟自然界生物进化过程与机制，求解极值问题的

一类自组织、自适应的人工智能技术，其基本思想是模拟自然界遗传

机制和生物进化论而形成的一种过程搜索最优解的算法。

1.遗传算法执行过程

遗传算法是一种自适应全局优化搜索算法，使用二进制遗传编

码，繁殖分为交叉和变异两个独立的步骤进行。其基本执行过程如下：

（1）初始化。确定种群规模N、交叉概率Pc、变异概率Pm

和置终止进化准则;随机生成N个个体作为初始种群X(0);置进

化代数计数器t←0。

（2）个体评价。计算或估价X(t)中各个体的适应度。

（3）种群进化。

①选择(母体)。从X(t)中运用选择算子选择出M/2对母

体(M≥N)。

②交叉。对所选择的M/2对母体,依概率Pc执行交叉形成

M个中间个体。

③变异。对M个中间个体分别独立依概率Pm执行变异,形

成M个候选个体。

④选择(子代)。从上述所形成的M个候选个体中依适应

度选择出N个个体组成新一代种群X(t+1)。

（4）终止检验。如已满足终止准则,则输出X(t+1)中具有最大

适应度的个体作为最优解,终止计算;否则转（3）。

2.遗传算法理论研究

遗传算法追求的是当前群体产生比现有个体更好个体的能力，

即遗传算法的可进化性，因此，遗传算法的理论和方法研究主要是围

绕这一目标展开：

①编码

二进制编码用于多维、高精度数值优化问题时，不能很好地克

服连续函数离散化时的映射误差，不能直接反映问题的固有结构，精

度不高，并且个体长度大、占用内存多，学者们提出的改进方法主要

有：a.格雷码编码；b.实数编码；c.十进制编码；d.非数值编码。

②适应度函数

在遗传算法中,适应度是描述个体性能的主要指标,根据适应

度的大小对个体进行优胜劣汰。将目标函数转换成适应度函数一般应

遵循两个原则:适应度必须非负;优化过程中目标函数的变化方向应

与群体进化过程中适应度函数变化方向一致。在使用遗传算法求解具

体问题时，适应度函数的选择对算法的收敛性以及收敛速度的影响较

大，针对不同的问题需要根据经验或算法来确定相应的参数。

③遗传算子

遗传算子主要包括三个方面：选择算子、交叉算子以及变异算

子。常见的选择算子有：轮盘赌选择、排序选择、最有个体保存、随

机联赛选择。交叉算子主要有：单点交叉、两点交叉、均匀交叉、算

术交叉。变异操作主要有：基本位变异、均匀变异、二元变异以及高

斯变异。

④参数选择

遗传遗传算法的参数选择一般包括群体规模、收敛判据、杂交

概率和变异概率等。参数选择关系到遗传算法的精度、可靠性和计算

时间等诸多因素,并且影响到结果的质量和系统性能。因此,在遗传

算法中参数选择的研究非常重要。

⑤收敛性分析

遗传算法的收敛性通常是指遗传算法所生成的迭代种群收敛到

某一稳定状态或其适应值函数的最大或平均值随迭代趋于优化问题

的最优值。依不同的研究方法及所应用的数学工具,收敛性分析可分

为Vose-Liepins模型、Markov链模型和公理化模型等。

⑥欺骗问题

欺骗问题是遗传算法研究中的一个热点。根据模式定理可知,

低阶、短距的优模式在遗传子代中将以指数级增长,最终,不同的最

优模式相互组合,从而得到最优解。但是,对于欺骗问题,复制算子

受欺骗条件的迷惑,使最优低阶模式在组合后形成非最优高阶模式,

从而使遗传算法偏离最优解。由于欺骗问题的存在,许多问题被归结

为遗传算法难题,使遗传算法的应用受到一定的局限。目前遗传算法

的欺骗问题研究主要集中在三个方面:a.设计欺骗函数；b.修改遗传

算法以解决欺骗函数的影响；c.理解欺骗函数对遗传算法的影响。

⑦并行遗传算法

并行算法的基本思想是将一个复杂的任务分解为多个较简单的

子任务,然后将各子任务分别分配给多个处理器并行执行求解。并行

遗传算法可以分为四大类,即全局并行遗传算法、粗粒度并行遗传算

法、细粒度并行遗传算法和混合并行遗传算法。

3.遗传算法的应用

遗传遗传算法提供了一种求解复杂系统优化问题的通用框架,

它不依赖于问题的具体领域,广泛应用于多种学科领域。

其主要领域有：函数优化、组合优化、生产调度、自动控制、

机器人学、图像处理、人工生命、遗传编程、机器学习以及数据挖掘

等。

4.总结

遗传算法作为一种非确定性的拟自然算法，为复杂系统的优化

提供了一种新的方法，在许多学科领域具有广泛的应用价值。但有关

算法的研究对已经研究较为深入的热点关注度较高，而对潜在研究热

点和迅速发展起来的研究热点关注度不足。综观遗传算法在算法改进

及应用方面的研究现状，它已经成为目前计算智能领域的热点之一。

但是还有一些不足，总体而言，以下几方面的工作尤其值得进一步探

讨:

a.遗传算法与优化技术的融合。

b.算法的改进以及新型算法的提出。

c.混合遗传算法。

d.算法的并行化研究。

e.加强遗传算法与应用的结合。

f.面向多目标优化约束优化问题的算法及理论研究。