求解非线性规划问题的遗传算法设计与实现(33页).doc

《求解非线性规划问题的遗传算法设计与实现(33页).doc》由会员分享，可在线阅读，更多相关《求解非线性规划问题的遗传算法设计与实现(33页).doc（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-求解非线性规划问题的遗传算法设计与实现-第 28 页摘 要非线性规划在工程、管理、经济、科研、军事等方面都有广泛的应用。传统的解决非线性规划问题的方法，如梯度法、罚函数法、拉格朗日乘子法等，稳定性差，对函数初值和函数性态要求较高，且容易陷入局部最优解。遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。遗传算法是一种全局搜索算法，简单、通用、鲁棒性强，对目标函数既不要求连续，也不要求可导，适用于并行分布处理，应用范围广。本文在分析传统的非线性规划算法的不足和遗传算法的优越性的基础上，将遗传算法应用于非线性规划。算法引进惩罚函数的概念，构造带有惩罚项的适应度函数；通过实数编码，转

2、轮法选择，双点交叉，均匀变异，形成了求解非线性规划问题的遗传算法。与传统的非线性规划算法外点罚函数法的比较结果表明该算法在一定程度上有效地克服了传统的非线性规划算法稳定性差，对函数初值和函数性态要求较高，且容易陷入局部最优解的缺陷，收敛更合理，性能更稳定。关键词：非线性规划；遗传算法；罚函数法ABSTRACTNon-linear programming has a wide range of applications in engineering, management, economic, scientific, and military aspects. Traditional metho

3、ds to solve the non-linear programming problem, such as the gradient method, penalty method, Lagrange multiplier method, have poor stability. They are sensitive to the function initial value and request the objective function to be continuous and differential. The results are also easily trapped int

4、o local optimal solution.Genetic algorithm is a kind of calculate model which simulates Darwins genetic selection and biological evolution of natural selection. Genetic algorithm is a global search algorithm. It has simple, universal, robust features, and does not request the objective function to b

5、e continuous and differential, and is suitable in parallel distribution processing. Genetic algorithm is widely applied in many areas.Based on the analysis of the disadvantage of traditional non-linear programming algorithm and the advantage of genetic algorithm, genetic algorithm is applied to non-

6、linear programming in this paper. The introduction of the concept of penalty function is used to construct the fitness function with punishment. By using real-coded, Roulette Wheel selection method, two-point crossover, uniform mutation, we formed a genetic algorithm to solve the non-linear programm

7、ing problem. Compared with the most classical and widely used traditional non-linear programming problem algorithm SUMT algorithm, the results show that the new algorithm could effectively overcome the defect of the traditional algorithm in a certain extent. The new algorithm is more stable, less se

8、nsitive to the function initial value and conditions, and always could receive the optimal solution or approximate optimal solution. Its convergence results are more reasonable, the performance is more stable.Key Words: Non-linear Programming; Genetic Algorithm; SUMT Algorithm 目 录1 概论11.1 背景介绍11.1.1

9、 非线性规划简介11.1.2 遗传算法简介11.2 研究内容22 非线性规划32.1 非线性规划的概念32.2 非线性规划的数学模型32.3 非线性规划的求解方法42.3.1 一维最优化方法42.3.2 无约束最优化方法42.3.3 约束最优化方法52.4 非线性规划的应用53 传统非线性规划算法外点罚函数法63.1 算法概述63.2 算法描述63.3 算法性能分析73.4 外点罚函数法的程序设计8程序步骤8程序流程图84 遗传算法104.1 遗传算法概述104.1.1 遗传算法的生物学基础104.1.2 遗传算法的一般结构104.1.3 遗传算法的特点124.1.4 遗传算法的应用124.2

10、 遗传算法实现的关键技术135 求解非线性规划问题的遗传算法设计165.1 实用遗传算法设计165.2 求解非线性规划问题的遗传算法程序设计215.2.1 算法过程描述215.2.2 遗传算法程序流程图225.2.3 遗传算法中所设计的辅助算法的设计226 算法的结果分析246.1 概述246.2 结果比较247 总结28致谢29参考文献301 概 论1.1 背景介绍 非线性规划简介具有非线性约束条件或目标函数的数学规划，称为非线性规划。非线性规划是20世纪50年代才开始形成的一门新兴学科。1951年H.W.库恩和A.W.塔克发表的关于最优性条件(后来称为库恩塔克条件)的论文是非线性规划正式诞

11、生的一个重要标志。在50年代还得出了可分离规划和二次规划的n种解法，它们大都是以G.B.丹齐克提出的解线性规划的单纯形法为基础的。50年代末到60年代末出现了许多解非线性规划问题的有效的算法，70年代又得到进一步的发展。非线性规划在工程、管理、经济、科研、军事等方面都有广泛的应用，为最优化设计提供了有力的工具。随着计算机的产生与发展，非线性规划作为一门独立的学科越来越受到人们的重视。在非线性规划理论研究的基础上，人们日益重视非线性规划问题求解方法的研究。传统的解决非线性规划问题的方法有多种，如搜索法、梯度法、变尺度法、罚函数法、拉格朗日乘子法、可行方向法等，虽然解法很多，非线性规划目前还没有能

12、适用于各种问题的算法，各个方法都有自己特定的适用范围。 遗传算法简介遗传算法（Genetic Algorithm），是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它是由美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著Adaptation in Natural and Artificial Systems，GA这个名称才逐渐为人所知，J.Holland教授所提出的GA通常为简单遗传算法（SGA）。遗传算法是一种特别有效的算法，它能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过

13、程，从而得到最优解或准最优解。它的主要特点是简单、通用、鲁棒性强，对目标函数既不要求连续，也不要求可导，适用于并行分布处理，应用范围广。遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于很多领域，如函数优化、组合优化、生产调度问题、自动控制、机器人智能控制、图像处理，人工生命、遗传编程、机器学习等。并且取得了令人瞩目的成果。1.2 研究内容传统的非线性规划算法的缺陷是计算烦琐且精度不高，稳定性差，对函数初值和函数性态要求较高，且容易陷入局部最优解。而遗传算法是一种鲁棒性很强的种全局搜索算法，理论上可以克服传统非线性规划算法的缺

14、陷。本文的主要内容就是应用遗传算法的基本思想，结合本次实验的实际情况，对基本遗传算法加以改进，将遗传算法应用于求解非线性规划问题，形成求解非线性规划问题的遗传算法。具体内容包括编码方法设计，适应度函数设计，选择算子、交叉算子、变异算子等遗传算子设计，算法流程设计，并在设计的基础上用MATLAB语言实现该算法的程序，运行并调试程序，直至得到正确的结果。并对实验所得结果进行分析，比较求解非线性规划问题的遗传算法与传统的非线性规划算法的优缺点。2 非线性规划2.1 非线性规划的概念具有非线性约束条件或目标函数的数学规划，称为非线性规划。非线性规划研究一个n元实函数在一组等式或不等式的约束条件下的极值

15、问题，且目标函数和约束条件至少有一个是未知量的非线性函数。目标函数和约束条件都是线性函数的情形则属于线性规划。2.2 非线性规划的数学模型对实际规划问题作定量分析，必须建立数学模型。建立数学模型首先要选定适当的目标变量和决策变量，并建立起目标变量与决策变量之间的函数关系，称之为目标函数。然后将各种限制条件加以抽象，得出决策变量应满足的一些等式或不等式，称之为约束条件4。非线性规划问题的一般数学模型可表述为求未知量，使满足约束条件：并使目标函数达到最小值(或最大值)。其中，诸和诸都是定义在n维向量空间的某子集(定义域)上的实值函数，且至少有一个是非线性函数。 上述模型可简记为： （2.2） （2

16、.3）其中属于定义域，符号min表示“求最小值”“受约束于”。定义域中满足约束条件的点称为问题的可行解。全体可行解所成的集合称为问题的可行集。对于一个可行解，如果存在的一个邻域，使目标函数在处的值优于(指不大于或不小于)该邻域中任何其他可行解处的函数值，则称为问题的局部最优解（简称局部解）。如果优于一切可行解处的目标函数值，则称x*为问题的整体最优解（简称整体解）。实用非线性规划问题要求整体解，而现有解法大多只是求出局部解。2.3 非线性规划的求解方法 一维最优化方法指寻求一元函数在某区间上的最优值点的方法。这类方法不仅有实用价值，而且大量多维最优化方法都依赖于一系列的一维最优化。常用的一维最

17、优化方法有黄金分割法、切线法和插值法1。黄金分割法，又称0.618法。它适用于单峰函数。其基本思想是：在初始寻查区间中设计一列点，通过逐次比较其函数值，逐步缩小寻查区间，以得出近似最优值点。 切线法，又称牛顿法。它也是针对单峰函数的。其基本思想是：在一个猜测点附近将目标函数的导函数线性化，用此线性函数的零点作为新的猜测点，逐步迭代去逼近最优点。插值法，又称多项式逼近法。其基本思想是用多项式（通常用二次或三次多项式）去拟合目标函数。 此外，还有斐波那契法、割线法、有理插值法、分批搜索法等。 无约束最优化方法指寻求n元实函数在整个n维向量空间上的最优值点的方法。这类方法的意义在于：虽然实用规划问题

18、大多是有约束的，但许多约束最优化方法可将有约束问题转化为若干无约束问题来求解1。 无约束最优化方法大多是逐次一维搜索的迭代算法。这类迭代算法可分为两类。一类需要用目标函数的导函数，称为解析法。另一类不涉及导数，只用到函数值，称为直接法。这些迭代算法的基本思想是：在一个近似点处选定一个有利搜索方向，沿这个方向进行一维寻查，得出新的近似点。然后对新点施行同样手续，如此反复迭代，直到满足预定的精度要求为止。根据搜索方向的取法不同，可以有各种算法。属于解析型的算法有：梯度法：又称最速下降法。这是早期的解析法，收敛速度较慢。牛顿法：收敛速度快，但不稳定，计算也较困难。共轭梯度法：收敛较快，效果较好。变尺

19、度法：这是一类效率较高的方法。其中达维登-弗莱彻-鲍威尔变尺度法，简称DFP法，是最常用的方法。属于直接型的算法有交替方向法（又称坐标轮换法）、模式搜索法、旋转方向法、鲍威尔共轭方向法和单纯形加速法等。 约束最优化方法指前述一般非线性规划模型的求解方法。常用的约束最优化方法有4种1：拉格朗日乘子法：它是将原问题转化为求拉格朗日函数的驻点。制约函数法：又称系列无约束最小化方法，简称SUMT法。它又分两类，一类叫惩罚函数法，或称外点法；另一类叫障碍函数法，或称内点法。它们都是将原问题转化为一系列无约束问题来求解。可行方向法：这是一类通过逐次选取可行下降方向去逼近最优点的迭代算法。如佐坦迪克法、弗兰

20、克沃尔夫法、投影梯度法和简约梯度法都属于此类算法。近似型算法：这类算法包括序贯线性规划法和序贯二次规划法。前者将原问题化为一系列线性规划问题求解，后者将原问题化为一系列二次规划问题求解。2.4 非线性规划的应用在经营管理、工程设计、科学研究、军事指挥等方面普遍地存在着最优化问题。例如：如何在现有人力、物力、财力条件下合理安排产品生产，以取得最高的利润；如何设计某种产品，在满足规格、性能要求的前提下，达到最低的成本；如何确定一个自动控制系统的某些参数，使系统的工作状态最佳；如何分配一个动力系统中各电站的负荷，在保证一定指标要求的前提下，使总耗费最小；如何安排库存储量，既能保证供应，又使储存费用最

21、低；如何组织货源，既能满足顾客需要，又使资金周转最快等。对于静态的最优化问题，当目标函数或约束条件出现未知量的非线性函数，且不便于线性化，或勉强线性化后会招致较大误差时，就可应用非线性规划的方法去处理。3 传统非线性规划算法外点罚函数法3.1 算法概述罚函数法求解非线性规划问题的思想是，利用问题中的约束函数做出适当的罚函数，由此构造出带参数的增广目标函数，把问题转化为无约束非线性规划问题。利用罚函数法，可将非线性规划问题的求解，转化为求解一系列无约束极值问题，因而也称这种方法为序列无约束最小化技术，简记为SUMT(Sequential Unconstrained Minimization Te

22、chnique)。主要有两种形式，一种叫外点罚函数法，另一种叫内点罚函数法。外点罚函数法是从非可行解出发逐渐移动到可行区域的方法。内点罚函数法也称为障碍罚函数法，这种方法是在可行域内部进行搜索，约束边界起到类似围墙的作用，如果当前解远离约束边界时，则罚函数值是非常小的，否则罚函数值接近无穷大的方法。3.2 算法描述对于问题（2.2），本文所述的基本策略是，根据约束特点（等式或不等式）构造某种“罚函数”，然后把它加到目标函数中去，使得对约束最优化问题的求解转化为一系列无约束问题。极小点或者无限地向可行域靠近，或者一直保持在可行集内移动，直到收敛于原来约束最优化问题极小点。对于问题（2.2），构造

23、一函数为 （3.1）其中， （3.2）在（）中，又称为惩罚函数， （3.3） （3.4）是一个逐渐增大的参数，称为惩罚因子。又称为问题（2.2）的增广目标函数。显然，增广目标函数是定义在上的一个无约束函数。由增广目标函数的构造知当时 （3.5）此时的最优解就是问题（2.2）的最优解；而当时，的最优解就不一定是问题（2.2）的最优解。但是研究时，的最优解不是我们所需要的。为此规定，当时，在点处的函数值迅速变大，换而言之，可行域外的任一点处的函数值都相当大。此时要求在中的最优解，只能让点回到内才有可能，然而一旦点回到内，即，此时就与问题（2.2）有相同的最优解。当时，迅速变大的原因是通过惩罚因子来

24、实现。简言之，外点罚函数法的思想是：当点时，设法加大不可行点处的函数值，使不可行点不能成为在中的最优解。在用外点罚函数法求解问题（2.2）时，首先构造增广目标函数，然后按照无约束优化方法求解。如果求出的最优解为，则判断是否属于。如果，则是问题（2.2）的最优解；如果，则不是问题（2.2）的最优解，此时说明原来的惩罚因子给的太小了，需要加大惩罚因子，使得，然后再重新计算的最优值。3.3 算法性能分析通过长期的理论研究和实验结果，人们总结出惩罚函数的优点有：（1）罚函数法是解决非线性规划问题的一种经典算法，这种算法简单易行、熟练数度快，在很多实际问题的求解中得到了应用。（2）计算效率高，稳定性较好

25、。缺点有：（1）罚函数法对于有些问题只能求出局部最优解，而不能求出全局最优。（2）对函数初值和函数性态要求较高。（3）罚函数法在实际计算中的缺点是罚因子的取值难于把握，太小起不到惩罚作用；太大则由于误差的影响会导致错误。在搜索过程开始的时候，一个较大的罚因子将会阻碍非可行域的搜索。另一方面，如果罚因子太小，这样相对于目标函数罚函数项是可以忽略的，则大量的搜索时间将花费在非可行域。这对于进化算法来说非常致命的。3.4 外点罚函数法的程序设计为了能和求解非线性规划问题的遗传算法进行比较，我们同时实现最经典的，也是得到最广泛应用的传统的非线性规划算法外点罚函数法，通过对二者的结果，比较二者性能的差别

26、。3.4.1程序步骤对于问题（），构造一函数为 （3.6）其中，惩罚函数按照式（）构造，给定终止限（可取）。具体过程描述如下：（1）选定初始点，初始惩罚因子（可取）。惩罚因子放大系数，置。（2）假设已获得迭代点，以为初始点，求解无约束问题 （3.7）设其最优点为。（3）若，则就是所要求问题的最优解，打印，结束；否则转（4）。（4）置，转（2）。3.4.2程序流程图外点罚函数法程序流程图如图3-1所示。图3-1 外点罚函数法程序流程图4 遗传算法4.1 遗传算法概述 遗传算法的生物学基础遗传算法的生物学基础是达尔文的自然选择学说。自然选择学说认为，生物要生存下去，就必须进行生存斗争。在生存斗争中

27、，具有有利变异（mutation）的个体容易存活下来，并且有更多的机会将有利的变异传给后代；具有不利变异的个体就容易被淘汰，产生后代的机会也少得多。达尔文把这种在生存斗争中适者生存，不适者淘汰的过程叫做自然选择。达尔文的自然选择学说表明，遗传和变异是决定生物进化的内在因素。遗传能使生物的性状不断地传递给后代，因而保持了物种的特性，变异能够使生物的性状发生改变，从而适应新的环境而不断地向前发展2。.2 遗传算法的一般结构遗传算法是一种基于生物自然选择与遗传机理的随机搜索算法。和传统算法不同，遗传算法从一组随机产生的初始解，称为“种群”，开始搜索过程。种群中的每个个体是问题的一个解，称为“染色体”

28、。染色体是一串符号，比如一个二进制字符串。这些染色体在后续迭代中不断进化，称为遗传。在每一代中用“适值”来测量染色体的好坏。生成的下一代染色体称为后代。后代是由前一代染色体通过交叉或变异运算形成的。新一代形成中，根据适值的大小选择部分后代，淘汰部分之后，从而保持种群大小是常数。适值高的染色体被选中的概率较高。这样，经过若干代之后，算法收敛于最好的染色体，它很可能就是问题的最优解或者次优解。设和分别表示第t代的双亲和后代，遗传算法的一般结构可描述如下3：遗传算法过程：begin初始化；评估；while不满足终止条件dobegin重组获得； 评估；从和中选择；endend图4-1 遗传算法的一般结

29、构通常初始化是随机产生的。重组包括交叉和变异来获得后代。实际上，遗传算法中有两类运算：（1）遗传运算：交叉和变异；（2）进化运算：选择。遗传运算模拟了基因在每一代中创造新后代的繁殖过程，进化运算则是种群逐代更新的过程。4.1.3 遗传算法的特点遗传算法是一类可用于复杂系统优化的具有鲁棒性的搜索算法，与传统的优化算法相比，主要有以下特点3：（1）遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接决策变量的实际植本身，而遗传算法处理决策变量的某种编码形式，使得我们可以借鉴生物学中的染色体和基因的概念，可以模仿自然界生物的遗传和进化机理，也使得我们能够方便的应用遗传操作算子。（2）遗传算法

30、直接以适应度作为搜索信息，无需导数等其它辅助信息。（3）遗传算法使用多个点的搜索信息，具有隐含并行性。（4）遗传算法使用概率搜索技术，而非确定性规则。4.1.4 遗传算法的应用遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于很多学科。下面是遗传算法的一些主要应用领域25：（1）函数优化。函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用算例。（2）组合优化。随着问题规模的增大，组合优化问题的搜索空间也急剧扩大，有时在目前的计算机上用枚举法很难或甚至不可能求出其精确最优解。遗传算法是解决这类问题的最佳工具之一。

31、实践证明，遗传算法对于组合优化中的NP完全问题非常有效。（3）生产调度问题。生产调度问题在许多情况下所建立起来的数学模型难以精确求解，即使经过一些简化之后可以进行求解，也会因简化得太多而使得求解结果与实际相差甚远。现在遗传算法已成为解决复杂调度问题的有效工具，在单件生产车间调度、流水线生产车间调度、生产规划、任务分配等方面遗传算法都得到了有效的应用。（4）自动控制。在自动控制领域中有许多与优化相关的问题需要求解，遗传算法已在其中得到了初步的应用，并显示出了良好的效果。（5）机器人智能控制。机器人是一类复杂的难以精确建模的人工系统，而遗传算法的起源就来自于对人工自适应系统的研究，所以机器人智能控

32、制理所当然地成为遗传算法的一个重要应用领域。（6）图像处理。在图像处理过程中，不可避免地会产生一些误差，这些误差会影响图像处理的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求。目前遗传算法已在模式识别、图像恢复、图像边缘特征提取等方面得到了应用。（7）人工生命。人工生命与遗传算法有着密切的关系，基于遗传算法的进化模型是研究人工生命现象的重要基础理论。遗传算法已在进化模型、学习模型、行为模型、自组织模型等方面显示出了初步的应用能力，并且必将得到更为深入的应用和发展。（8）遗传编程。Koza发展了遗传编程的概念，他使用了以LISP语言所表示的编码方法，基于对一种树型结构所进行的遗传操作

33、来自动生成计算机程序。（9）机器学习。基于遗传算法的机器学习，在很多领域中都得到了应用。4.2 遗传算法实现的关键技术1、编码方法在遗传算法的运行过程中，它不对所求解问题的实际决策变量直接进行操作，而是对表示可行解的个体编码施加选择、交叉、变异等遗传运算，通过这种遗传操作来达到优化的目的，这是遗传算法的特点之一。在遗传算法中把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法称为编码。常用的编码方法有：（1）二进制编码：使用由二进制符号0和1所组成的二值符号集0，1进行编码，它所构成的个体基因型是一个二进制编码符号串。它是将可行解用固定长度的二进制串表示，串的长度与问题所要求

34、的求解精度有关。（2）浮点数编码：个体的每个基因值用某一范围内的一个浮点数来表示，个体的编码长度等于其决策变量的个数。它所使用的是决策变量的真实值。（3）符号编码：个体染色体编码串中的基因值取自一个无数值含义、而只有代码含义的符号集。这个符号集可以是一个字母表，如A,B,C,D,；也可以是一个数字序号表，如1，2，3，4，5，；还可以是一个代码表，如A1,A2,A3,A4,等等。2、适应度函数适应度是度量群体中各个个体在优化计算中有可能达到或接近于或有助于找到最优解的优良程度2。遗传算法的一个特点是它仅使用所求问题的目标函数值就可得到下一步的有关搜索信息。而对目标函数值的使用是通过评价个体的适

35、应度来体现的。评价个体适应度的一般过程是：（1）对个体编码串进行解码处理后，可得到个体的表现型。（2）由个体的表现型可计算出对应个体的目标函数值。（3）根据最优化问题的类型，由目标函数值按一定的转换规则求出个体的适应度。3、选择算子遗传算法使用遗传算子（或称为复制算子，Reproduction Operator）来对群体中的个体进行优胜劣汰操作：适应度较高的个体被遗传到下一代群体中的概率较大；适应度较低的个体被遗传到下一代群体中的概率较小。遗传算法中的选择操作就是确定如何从父代群体中按某种方法选取哪些个体遗传到下一代群体中的一种遗传运算。遗传操作建立在对个体的适应度进行评价的基础之上。选择操作

36、的主要目的是为了避免基因缺失、提高全局收敛性和计算效率。常见选择算子：（1）比例选择：各个个体被选中的概率与其适应度大小成正比。设群体大小为pop_size，个体的适应度为，则个体被选中的概率为： （k=1，2，pop_size） （4.1）（2）随机联赛选择：每次选取几个个体之中适应度最高的一个个体遗传到下一代群体中。在联赛选择操作中，只有个体适应度之间的大小比较运算，而无个体适应度之间的算术运算，故它对个体适应度是取正值还是负值无特别要求。（3）排序选择：对群体中的所有个体按其适应度大小进行排序，基于这个排序来分配各个个体被选中的概率。4、交叉算子遗传算法中的交叉运算是指对两个相互配对的染

37、色体按某种方式相互交换其部分基因，从而形成两个新的个体。它是产生新个体的主要方法。遗传算法中，在交叉运算之前必须对群体中的个体进行配对。常用的配对策略是随机配对，即将群体中的M个个体以随机的方式组成对配对个体组，交叉操作是在这些配对个体组中的两个个体之间进行的。常见交叉算子：（1）单点交叉（One-point Crossover）：在个体编码串中只随机设置一个交叉点，实行交叉时，该点前或后的两个个体的部分结构进行互换，并生成两个新个体。（2）双点交叉（Two-point Crossover）：在个体编码串中随机设置了二个交叉点，进行交叉时，将两个交叉点之间的部分基因进行互换。（3）均匀交叉（U

38、niform Crossover）：两个配对个体的每一个基因座上的基因以相同的交叉概率进行交换，从而形成两个新的个体。5、变异算子遗传算法中的变异运算是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其他等位基因来替换，从而形成一个新的个体。遗传算法导入变异的目的有两个：一是使遗传算法具有局部的随机搜索能力。二是使遗传算法可维持群体多样性，以防止出现未成熟收敛现象。变异算子的操作步骤：在群体中所有个体的码串范围内随机地确定基因座。以事先设定的变异概率Pm来对这些基因座的基因值进行变异。常见变异算子：（1）基本位变异（Simple Mutation）是指对个体编码串中以变异概率Pm随机指

39、定的某一位基因座上的基因值作变异运算。（2）均匀变异（Uniform Mutation）是指分别用符合某一范围内均匀分布的随机数，以某一较小的概率来替换个体编码串中各个基因座上的原有基因值。（3）逆转算子（Inversion Operator）在个体码串中随机挑选二个逆转点，然后将两个逆转点间的基因值以逆转概率Pi逆向排序。6、遗传算法的运行参数（1）编码串长度L。使用二进制编码时，L与问题所要求的求解精度有关；使用浮点数编码时，L与决策变量的个数n相等；使用符号编码是，L由问题的编码方式确定。（2）群体大小pop_size。pop_size表示群体中所含个体的数量。当pop_size取值较小

40、时，可提高遗传算法的运算速度，却降低了群体的多样性，有可能会引起遗传算法的早熟现象；当pop_size取值较大时，又会使遗传算法的运行效率降低。（3）交叉概率Pc。交叉操作是遗传算法中产生新个体的主要方法，所以Pc取值较大。但若过大的话，又会破坏群体中的优良模式，对进化运算产生不利影响；若过小的话，产生新个体的速度又较慢。建议取值范围是0.40.99。（4）变异概率Pm。Pm取值过大，虽然能够产生较多的新个体，但也可能破坏掉很多较好的模式，使得遗传算法的性能近似于随机搜索算法的性能；若Pm过小，则变异操作产生新个体的能力和抑制早熟现象的能力就会较差。一般建议取值范围是0.00010.2。（5）

41、终止代数T。T表示遗传算法运行到指定的进化代数之后就停止运行，并将当前群体中的最佳个体作为所求问题的最优解输出。一般建议取值范围是1001000。5 求解非线性规划问题的遗传算法设计传统的非线性规划算法的缺陷是计算烦琐且精度不高，稳定性差，对函数初值和函数性态要求较高，且容易陷入局部最优解。而遗传算法是一种全局搜索算法，可以克服传统的非线性规划算法容易陷入局部最优解的缺陷。因此，将遗传算法应用于非线性规划，是改善收敛效果，提高最优化质量的有效途径。本章就是介绍遗传算法在非线性规划中的具体应用，设计并实现求解非线性规划问题的遗传算法。5.1 实用遗传算法设计1、编码方法设计非线性规划属于最优化设

42、计的一种，属于约束优化问题，其最终目的是选择一种方法，使目标函数在满足约束的条件下达到最优。从非线性规划的数学模型可知，我们最终要求解的是一组解，其满足约束条件，并使目标函数达到最小值(或最大值)。我们将这组解作为染色体，其中每个相当于染色体上的基因，这也就是编码对象。之后的选择，交叉，变异就是对编码后的染色体基因进行运算。我们最终所求的解是n维向量空间的某子集（定义域）上的一个实数，若采用传统的二进制编码，则编码串长度不固定。如果采用固定长度的二进制编码，不仅会造成存储空间的极大浪费，而且在进行交叉和变异等遗传操作时，由于实际值不等长而很难确定交叉点和变异点，而且很容易产生无效解，降低了算法

43、的效率；如果采用不定长二进制编码，则在进行交叉和变异等遗传操作时很难确定交叉点和变异点，而且容易产生无效解。而且采用二进制编码，又要牵涉到十进制与二进制的转换，在实际操作过程中要频繁进行编码和解码操作，费时费力。所以我们直接采用实数编码，即染色体基因串中基因座的值直接是每组解中各分量的实数值，不再对其进行其他任何形式的编码。每个染色体编码为一个和解向量维数相同的实向量2。2、适应度函数设计1）满足约束由于对染色体作遗传运算时通常获得不可行的后代，因此运用遗传算法解非线性规划问题的核心问题是如何满足约束的问题。今年来，已经提出了几种运用遗传算法满足约束的技术，这些技术大致可以分为以下几类316：

44、（1）拒绝策略拒绝策略抛弃所有进化过程中产生的不可行的染色体。这是遗传算法中普遍的作法。当可行的搜索空间是凸的，且为整个搜索空间的适当的一部分时，这种方法应该是有效的。然而，这是很严格的限制。例如，对许多约束优化问题初始种群可能全由非可行染色体构成，这就需要对他们进行修补。对于某些系统（特别是可行搜索空间非凸时），允许跨过不可行域修复往往更容易达到最优解。（2）修复策略修补染色体是对不可行染色体采用修复程序使之变为可行的。对于许多组合优化问题，构造修复程序相对比较容易。Liepins和他的合作者通过对遗传算法的性能试验测试证明，对于一个有多个不连通可行集的约束组合优化问题，修复策略在速度和计算

45、性能上都远胜过其他策略。修复策略取决于是否存在一个可将不可行后代转化为可行的修复程序。该方法的缺点是它对问题本身的依赖性，对于每个具体问题必须设计专门的修复程序。对于某些问题，修复过程甚至比原问题的求解更复杂。修复后的染色体可以只用来作评估，也可用来替代原染色体进入种群。Liepins等采用永不替代法，即不让修复过的染色体进入种群；而Nakano和Yamada采用了始终替代法。最近，Orvosh和Davis提出了所谓的5%规则：该规则对于多数组合优化问题，若令5%的修复过的染色体替代原染色体，则带有修复程序的遗传算法可取得最好的效果。Michalewicz等则认为对有非线性约束的优化问题，15

46、%的替代率为最好。（3）改进遗传算子策略解决可行性问题的一个合理办法是设计针对问题的表达方式以及专门的遗传算子来维持染色体的可行性。Michalewicz等指出这种方法通常比基于惩罚的遗传算法更可靠。许多领域中的实际工作者采用专门的问题表达方式和遗传算子构造了非常成功的遗传算法，这已是一个普遍的趋势。但是，该方法的遗传搜索收到了可行域的限制。（4）惩罚策略上面三种策略的共同优点是都不会产生不可行解，缺点则是无法考虑可行域外的点。对于约束严的问题，不可行解在种群中的比例很大。这样，将搜索限制在可行域内就很难找到可行解。Glover和Greenberg建议的约束管理技术允许在搜索空间里的不可行域中

47、进行搜索，这比将搜索限制在可行域内的方法能更快地活的最优解或获得更好的最终解。惩罚策略就是这类在遗传搜索中考虑不可行解的技术。2）惩罚函数惩罚函数大概是用遗传算法解约束优化问题中最常用的技术。本质上它是通过惩罚不可行解将约束问题转化为无约束问题。在遗传算法中，惩罚技术用来在每代的种群中保持部分不可行解，使遗传搜索可以从可行域和不可行域两边来达到最优解。一般，解空间包含两部分：可行域和不可行域。我们不能对这些子空间作任何假设，特别是当它们是非凸或非连通时，如图5-1所示。控制非可行的染色体远不是一件容易事，从图5-1可知，不可行解b与最优解a的距离比不可行解d和可行解c都近。我们希望给b较小惩罚。可以