1637人阅读
matlab图像处理
遗传算法（4）
最近在学习遗传算法，刚刚掌握了基本遗传算法的一些东西，所以记录下来以便后续学习，也方便刚刚入门的同学学习。根据我学习的编写的程序，我将按照程序的步骤，来写这篇博客。并且借鉴前人经验，完善结构。
2、遗传算法的组成
2.1初始种群的产生
2.2适应度函数及停止准则
2.3遗传算子的组成
2.3.4运行参数
2.4基本的遗传算法的优点与不足
2.5遗传算法的改进
2.6遗传算法的应用
遗传算法(Genetic Algorithms, GA)是一类借鉴生物界自然选择和自然遗传机制的随机化搜索最优解的算法。
它模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。
下面是一些基本的生物学概念，简单了解一下即可。
种群(Population)：生物的进化以群体的形式进行，这样的一个群体称为种群。
个体：组成种群的单个生物。
基因 ( Gene ) ：一个遗传因子。
染色体 ( Chromosome ) ：包含一组的基因。
生存竞争，适者生存：对环境适应度高的、牛B的个体参与繁殖的机会比较多，后代就会越来越多。适应度低的个体参与繁殖的机会比较少，后代就会越来越少。
遗传与变异：新个体会遗传父母双方各一部分的基因，同时有一定的概率发生基因变异。
2、遗传算法的组成:
（1）初始种群的产生（编码）
（2）适应度函数的确定
（3）遗传算子（选择、交叉、变异）
2.1初始种群的产生（编码）
& & 要进行后面的操作，首先要产生初始种群，也就是进化的第一代，种群大小,一般取为100~200，当然也要视问题而定。初始种群的选择很重要，会影响收敛速度和结果。本程序采用的随机产生的方式。产生了初始种群后要进行编码，也可以直接在产生种群的时候就是用编码的方式产生的。基因的编码方式有很多，这也取决于要解决的问题本身。常见的编码方式有：
（1）&&&&&& 二进制编码，基因用0或1表示（常用于解决01背包问题）
如：基因A： (代表一个个体的染色体)
（2）&&&&&& 互换编码（用于解决排序问题，如旅行商问题和调度问题）
如旅行商问题中，一串基因编码用来表示遍历的城市顺序，如：，表示九个城市中，先经过城市2，再经过城市3，依此类推。
（3）&&&&&& 树形编码（用于遗传规划中的演化编程或者表示）
如,问题：给定了很多组输入和输出。请你为这些输入输出选择一个函数，使得这个函数把每个输入尽可能近地映射为输出。
编码方法：基因就是树形结构中的一些函数。
（4）&&&&&& 值编码 （二进制编码不好用时，解决复杂的数值问题）
在值编码中，每个基因就是一串取值。这些取值可以是与问题有关任何值：整数，实数，字符或者其他一些更复杂的东西。
程序中使用的是二进制编码的方式，程序的应用背景是图像分割，所以数值是0-255之间，所以，二进制编码的位数是8，这里的计算就是十进制与二进制转换的方式，例如：要在[-1,2]之间产生最优解，小数点后面保留3位小数，那么就是区间长度2-（-1）=3，3/10^(-3)=次方是次方是2048，所以，二进制编码的位数应该是12.
2.2适应度函数及停止准则
遗传算法对一个个体（解）的好坏用适应度函数值来评价，适应度函数选择的越好，解的质量越高。适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。
在图像分割中，根据大于阈值部分和小于阈值部分的差异性来确定的适应度函数，差异性越大的阈值，适应度越好，也就是说适应度函数值越大，越容易遗传到下一代。也就是说下面的精英选择依据就是适应度的大小。
停止准则有两个，一个是最大迭代次数，一个就是适应度变化的大小，当然你也可以自己设定其他的停止准则，在本程序中是采用的这两个停止准则。最大代数,一般取为500~100，这是为了防止出现迭代次数过多，或者不收敛的情况，所设定的最大的执行次数。当适应度值变化小于某个值时，进化停止，如果始终达不到这个条件，就达到最大迭代次数时停止进化迭代。
2.3遗传算子的组成
遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。选择操作的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。
SGA（基本遗传算法）中采用轮盘赌选择方法。
轮盘赌选择又称比例选择算子，基本思想：各个个体被选中的概率与其适应度函数值大小成正比。设群体大小为n ，个体i 的适应度为 Fi，则个体i 被选中遗传到下一代群体的概率为：
在本程序的算法实现中，为了加速优化，没有采用这种方式，而是用的计算上一代各个个体的适应度并排序，如果上一代的个体的适应度比当前代的最大适应度值大，就采用一定的方式遗传到下一代，替换当前代的个体。否则就不进行选择遗传。
所谓交叉运算，是指对两个相互配对的染色体依据交叉概率按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算在GA中起关键作用，是产生新个体的主要方法。
遗传算法中，交叉因其全局搜索能力而作为主要算子，变异算子因其局部搜索能力而作为辅助算子。遗传算法通过交叉和变异这对相互配合又相互竞争的操作而使其具备兼顾全局和局部的均衡搜索能力。所谓相互配合.是指当群体在进化中陷于搜索空间中某个超而仅靠交叉不能摆脱时，通过变异操作可有助于这种摆脱。所谓相互竞争，是指当通过交叉已形成所期望的积木块时，变异操作有可能破坏这些积木块。如何有效地配合使用交叉和变异操作，是目前遗传算法的一个重要研究内容。
由于交叉是产生新个体的主要方法，所以一般情况下交叉概率比较大，交叉概率,一般取为0.4~0.6。
交叉算子从两个双亲子串中通过复制选定位产生两个新的后代，每个后代的第i位，是从它的某个双亲的第i位复制得来的，至于双亲中的哪一个在第i位起作用，这是由另外一个被称为交叉掩码的位串决定的。
1.&&&&单交叉点法 （用于二进制编码）
选择一个交叉点,子代在交叉点前面的基因从一个父代基因那里得到,后面的部分从另外一个父代基因那里得到。在单点交叉中交叉掩码总是这样组成的，它以连续的n个1开始。
如：交叉前：
2.&双交叉点法 （用于二进制编码）
选择两个交叉点,子代基因在两个交叉点间部分来自一个父代基因,其余部分来自于另外一个父代基因.
如：交叉前：
01 |0010| 11
11 |0111| 01
11 |0010| 01
01 |0111| 11
3.&基于“ 与/或 ”交叉法 （用于二进制编码）&
对父代按位&与”逻辑运算产生一子代A;按位”或”逻辑运算产生另一子代B。该交叉策略在解背包问题中效果较好&.
如：交叉前：
4.&单交叉点法 （用于互换编码）
选择一个交叉点，子代的从初始位置出发的部分从一个基因复制，然后在另一个基因中扫描，如果某个位点在子代中没有，就把它添加进去。
如：交叉前：
&&& 87213 | 09546
& &&98356 | 71420
&& &87213 | 95640
&&& 98356 | 72104
5.&部分匹配交叉（PMX）法（用于互换编码）
先随机产生两个交叉点，定义这两点间的区域为匹配区域，并用交换两个父代的匹配区域。
父代A：872 | 130 | 9546
父代B：983 | 567 | 1420&&& 变为：
TEMP A: 872 | 567 | 9546
TEMP B: 983 | 130 | 1420
对于 TEMP A、TEMP Ｂ中匹配区域以外出现的数码重复，要依据匹配区域内的位置逐一进行替换。匹配关系：1&——&５　３&——&６　７&——&０
子代Ａ：802 | 567 | 9143
子代Ｂ：986 | 130 | 5427
6.&顺序交叉法(OX) （用于互换编码）
从父代Ａ随机选一个编码子串，放到子代Ａ的对应位置；子代Ａ空余的位置从父代Ｂ中按Ｂ的顺序选取（与己有编码不重复）。同理可得子代Ｂ。
父代A: 872 | 139 | 0546
父代B: 983 | 567 | 1420
子代A: 856 | 139&|&7420
子代B: 821 | 567 | 3904
7.&循环交叉（CX）法（用于互换编码）
CX同OX交叉都是从一个亲代中取一些城市，而其它城市来自另外一个亲代，但是二者不同之处在于：OX中来自第一个亲代的编码子串是随机产生的，而CX却不是，它是根据两个双亲相应位置的编码而确定的。
父代Ａ：1 2 3 4 5 6 7 8 9
&&&&&&&&&& | &|&& |& |&&&& &&&|
父代Ａ：5 4 6 9 2 3 7 8 1
可得循环基因：1-&5-&2-&4-&9-&1
用循环的基因构成子代Ａ，顺序与父代Ａ一样
1 2& &4 5 &&&&&& &&9
用父代Ｂ剩余的基因填满子代Ａ：
1 2 6 4 5 3 7 8 9
子代Ｂ的编码同理。（循环基因 5-&1-&9-&4-&2-&5）
变异是指依据变异概率将个体编码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。GA中的变异运算是产生新个体的辅助方法，它决定了GA的局部搜索能力，同时保持种群的多样性。交叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。
注：变异概率Pm不能太小，这样降低全局搜索能力；也不能太大，Pm & 0.5，这时GA退化为随机搜索。变异概率,一般取为0.001~0.1
1.&基本位变异算子 （用于二进制编码）
基本位变异算子是指对个体编码串随机指定的某一位或某几位基因作变异运算。对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则变异操作将其变为1；反之，若原有基因值为1，则变异操作将其变为0。
如：变异前：
2.&逆转变异算子（用于互换编码）
在个体中随机挑选两个逆转点，再将两个逆转点间的基因交换。
如：变异前：
1346798205
1246798305
2.3.4&运行参数
GA运行时选择的参数应该视解决的具体问题而定，到目前为止，还没有一个适用于GA所有应用领域的关于算法参数的理论。下面是一般情况下使用GA时推荐的参数：
交叉率一般来说应该比较大，推荐使用80％-95％。
变异率一般来说应该比较小，一般使用0.5％-1％最好。
3)&种群的规模
种群规模指的是群体中个体的个数。实验发现，比较大的种群的规模并不能优化遗传算法的结果。种群的大小推荐使用20-30，一些研究表明，种群规模 的大小取决于编码的方法，具体的说就是编码串（Encoded String）的大小。也就是说，如果说采用32位为基因编码的时候种群的规模大小最好为32的话，那么当采用16位为基因编码时种群的规模相应应变为原 来的两倍。
4)&遗传运算的终止进化代数
个人的想法是，设定一个计数器，如果连续N代出现的最优个体的适应度都一样时，（严格的说应该是，连续N代子代种群的最优个体适应度都&=父代最优个性的适应度）可以终止运算。
也可以简单的根据经验固定进化的代数。
II&运算流程
&图中的“是否满足停止准则”便可参照上节中“遗传运算的终止进化代数”
下面是补充内容，于本算法没有太多的关系。
灾变与精英主义
遗传算法的局部搜索能力较强，但是很容易陷入局部极值。引用网上的一段原话:
“那么如何解决遗传算法容易陷入局部极值的问题呢？让我们来看看大自然提供的方案。六千五百万年以前，恐龙和灵长类动物并存，恐龙在地球上占绝对统 治地位，如果恐龙没有灭绝灵长类动物是绝没有可能统治地球的。正是恐龙的灭绝才使灵长类动物有了充分进化的余地，事实上地球至少经历了5次物种大灭绝，每 次物种灭绝都给更加高级的生物提供了充分进化的余地。所以要跳出局部极值就必须杀死当前所有的优秀个体，从而让远离当前极值的点有充分的进化余地。这就是灾变的思想。”
灾变就是杀掉最优秀的个体，这样才可能产生更优秀的物种。那何时进行灾变，灾变次数又如何设定？
何时进行灾变，可以采用灾变倒计数的方式。如果n代还没有出现比之前更优秀的个体时，可以发生灾变。灾变次数可以这样来确定，如果若干次灾变后产生的个体的适应度与没灾变前的一样，可停止灾变。
当利用交叉和变异产生新的一代时，我们有很大的可能把在某个中间步骤中得到的最优解丢失。
精英主义的思想是,在每一次产生新的一代时，首先把当前最优解原封不动的复制到新的一代中。然后按照前面所说的那样做就行。精英主义方法可以大幅提高运算速度，因为它可以防止丢失掉找到的最好的解。
由上面看来,灾变与精英主义之间似乎存在着矛盾.前者是将产生的最优个体杀掉,而后者是将最优秀个体基因直接保存到下一代.
应该辩证地看待它们之间的矛盾,两者其实是可以共存的.我们在每一代进行交叉运算时,均直接把最优秀的个体复制到下一代;但当连续N代,都没有更优 秀的个体出现时,便可以猜想可能陷入局部最优解了,这样可以采用灾变的手段.可以说,精英主义是伴随的每一代的,但灾变却不需要经常发生,否则算法可能下 降为随机搜索了.
当然,每个算法中不一定要用精英主义和灾变的手段,应该根据具体的问题而定.
2.4基本的遗传算法的优点与不足
遗传算法的优点:
（1）群体搜索，易于并行化处理；
（2）不是盲目穷举，而是启发式搜索；
（3）适应度函数不受连续、可微等条件的约束，适用范围很广。
（4）容易实现。一旦有了一个遗传算法的程序，如果想解决一个新的问题，只需针对新的问题重新进行基因编码就行；如果编码方法也相同，那只需要改变一下适应度函数就可以了。
遗传算法的不足:
1、早熟。这是最大的缺点，即算法对新空间的探索能力是有限的，也容易收敛到局部最优解。
2、大量计算。涉及到大量个体的计算，当问题复杂时，计算时间是个问题。
3、处理规模小。目前对于维数较高的问题，还是很难处理和优化的。
4、难于处理非线性约束。对非线性约束的处理，大部分算法都是添加惩罚因子，这是一笔不小的开支。
5、稳定性差。因为算法属于随机类算法，需要多次运算，结果的可靠性差，不能稳定的得到解。
2.5遗传算法的改进尽管遗传算法有许多优点，也有许多专家学者对遗传算法进行不断研究，但目前存在的问题依然很多，如：（1）适应度值标定方式多种多样，没有一个简洁、通用的方法，不利于对遗传算法的使用。&&&& （2）遗传算法的早熟现象即很快收敛到局部最优解而不是全局最优解是迄今为止最难处理的关键问题。（3）快要接近最优解时在最优解附近左右摆动，收敛较慢。&本节根据遗传算法所存在的这些问题分别从适应度值函数标定和增加群体多样性两方面着手解决。遗传算法通常需要解决以下问题，如确定编码方案，适应度函数标定，选择遗传操作方式及相关控制参数，停止准则确定等。相应地，为改进简单遗传算法的实际计算性能，很多学者的改进工作也是分别从参数编码、初始群体设定、适应度函数标定、遗传操作算子、控制参数的选择以及遗传算法的结构等方面提出的。自从1975年J.H.Holland系统提出遗传算法的完整结构和理论以来，众多学者一直致力于推动遗传算法的发展，对编码方式、控制参数的确定和交叉机理等进行了深入的研究，提出了各种变形的遗传算法。其基本途径概括起来主要有下面几个方面：(1)改进遗传算法的组成成分或使用技术，如选用优化控制参数、适合问题特性的编码技术等。(2)采用混合遗传算法(Hybrid Genetic Algorithm)。(3)采用动态自适应技术，在进化过程中调整算法控制参数和编码精度。(4)采用非标准的遗传操作算子。(5)采用并行算法。在许多资料中都介绍了七种改进遗传算法：(1)分层遗传算法(Hierarchic Genetic Algorithm)；(2)& CHC算法；(3)& Messy 遗传算法；(4)自适应遗传算法(Adaptive Genetic Algorithm)；(5)基于小生境技术的遗传算法(Niched Genetic Algorithm，NGA)；(6)并行遗传算法(Parallel Genetic Algorithm)；(7)混合遗传算法：①遗传算法与最速下降法相结合的混合遗传算法。②遗传算法与模拟退火法(Simulated Annealing)相结合的混合遗传算法
2.6遗传算法的应用
遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性。所以，广泛应用于很多学科。下面是遗传算法的一此主要应用领域。
2.6.1函数优化
函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用算例。很多人构造出了各种各样的复杂形式的测试函数。有连续函数也有离散函数，有凸函数也有凹函数，有低维函数也有高维函数，有确定函数也有随机函数，有单峰值函数也有多峰值函数等。用这些几何特性各具特色的函数来评价遗传算法的性能，更能反映算法的本质效果而对于一些非线性、多模型、多目标的函数优化问题，用其他优化方法较难求解。而遗传算法却可以方便地得到较好的结果。
2.6.2组合优化
&随着问题规模的增大，组合优化问题的搜索空间也急剧扩大。有时在目前的计算机上用枚举法很难或甚至不可能求出其精确最优解。对这类复杂问题，人们已意识到应把主要精力放在寻求其满意解上，而遗传算法是寻求这种满意解的最佳工具之一。实践证明，遗传算法已经在求解旅行商问题、背包问题、装箱问题、布局优化、图形划分问题等各种具有NP难度的问题得到成功的应用。
2.6.3生产调度问题
生产调度问题在很多情况下建立起来的数学模难以精确求解，即使经过一些简化之后可以进行求解.也会因简化得太多而使得求解结果与实际相差甚远。目前在现实生产中主要是靠一些经验来进行调度。现在遗传算法已成为解决复杂调度问题的有效下具。在单件生产车间调度、流水线生产间调度、生产规划、任务分配等方面遗传算法都得到了有效的应用。
2.6.4自动控制
在自动控制领域中有很多与优化相关的问题需要求解。遗传算法已在其中得到了初步的应用，并显示出良好的效果。例如用遗传算法进行航空控制系统的优化、使用遗传算法设计空间交会控制器、基于遗传算法的模糊控制器的优化设计、基于遗传算法的参数辨识、基于遗传算法的模糊控制规则的学习、利用遗传算法进行人工神经网络的结构优化设计和权值学习等。都显出了遗传算法在这此领域中应用的可能性。
2.6.5&机器人学
机器人是一类复杂的难以精确建模的人工系统，而遗传算法的起源就来自于人工自适应系统的研究。所以，机器人学理所当然地成为遗传算法的一个重要应用领域。例如，遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行为协调等方而得到研究和应用。&&
2.6.6 图像处理
图像处理是计算机视觉中的一个重要研究领域。在图像处理过程中，如扫描、特征提取、图像分割等不可避免地会存在一此误差，从而影响图像的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求。遗传算法在这些图像处理中的优化计算方面找到了用武之地。目前已在模式识别(包括汉字识别)、图像恢复、图像边缘特征提取等方而得到了应用。
2.6.7 人工生命
人下生命是用计算机、机械等人下媒体模拟或构造出的具有自然生物系统特有行为的人造系统。自组织能力和自学习能力是人下生命的两大主要特征。人下生命与遗传算法有着密切的关系。基于遗传算法的进化模型是研究人下生命现象的重要基础理论。虽然人下生命的研究尚处于启蒙阶段，但遗传算法已在其进化模型、学习模型、行为模型、自组织模型等方面显示出了初步的应用能力，并且必将得到更为深入的应用和发展。人工生命与遗传算法相辅相成，遗传算法为人下生命的研究提供一个有效的下具，人下生命的研究也必将促进遗传算法的进一步发展。
2.6.8 遗传编程
1989年，美国Standford大学的Koza教授发展了遗传编程的概念,其基木思想是:采用树型结构表示计算机程序,运用遗传算法的思想,通过自动生成计算机程序来解决问题。虽然遗传编程的理论尚米成热,应用也有一此限制,但它已成功地应用于人工智能、机器学习等领域。目前公开的遗传编程实验系统有十多个。例如，Koza开发的ADF系统，While开发的GPELST系统等。
2.6.9 机器学习
学习能力是高级自适应系统所具备的能力之一，基于遗传算法的机器学习，特别是分类器系统，在很多领域中都得到了应用。例如，遗传算法被用于学习模糊控制规则，利用遗传算法来学习隶属度函数，从而更好地改进了模糊系统的性能；基于遗传算法的机器学习可用来调整人工神经网络的连接权，也可用于人工神经网络结构优化设计；分类器系统也在学习式多机器人路径规划系统中得到了成功的应用。
2.6.10 数据挖掘
数据挖掘是近几年出现的数据库技术，它能够从大型数据库中提取隐含的、先前未知的、有潜在应用价值的知识和规则。许多数据挖掘问题可看成是搜索问题，数据库看作是搜索空间，挖掘算法看作是搜索策略。因此，应用遗传算法在数据库中进行搜索，对随机产生的一组规则进行进化.直到数据库能被该组规则覆盖，从而挖掘出隐含在数据库中的规则。Sunil已成功地开发了一个基于遗传算法的数据挖掘下具。利用该工具对两个飞机失事的真实数据库进行了数据挖掘实验，结果表明遗传算法是进行数据挖掘的有效方法之一。
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：37427次
排名：千里之外
原创：24篇
转载：34篇
评论：21条
(1)(7)(1)(1)(2)(13)(9)(22)(4)第21卷第1期；2005年2月大学数学COLLEGEMATHEM；遗传算法求解约束非线性规划及Matlab实现；倪金林；(合肥工业大学理学院应用数学系,合肥230009；[摘要]对于约束非线性规划问题,传统的方法:、.；[];交叉;变异；[[]A[文章编号]05；1引言；约束非线性规划问题是运筹学中的一个重要分支,现实；2遗传算法；遗
第21卷第1期
2005年2月大　学　数　学COLLEGEMATHEMATICSVol.21,№.1Feb.2005
遗传算法求解约束非线性规划及Matlab实现
(合肥工业大学理学院应用数学系,合肥230009)
　　[摘　要]对于约束非线性规划问题,传统的方法:、.用新兴的遗传算法来解决约束非线性规划,.,有的过于复杂.,提出了一种解决.
[];交叉;变异
[[]A　　[文章编号]05)
1　引　　言
约束非线性规划问题是运筹学中的一个重要分支,现实生活中许多实际问题都不能表达为容易解决的线性模型,如地下水调整系统和地下水污染来源识别问题中就不可避免非线性规划问题.解决约束非线性问题的方法也很多.一般方法,如可行方向法,惩罚函数法[1]都计算复杂且精度不高.遗传算法是一个新兴的方法,1975年Holland在他的著作《AdaptationinNaturalandArtificalSystems》中首次提出遗传算法,很快就用遗传算法来解决非线性最优问题.而用遗传算法解决非线性等式与不等式约束最优化问题的核心问题是如何满足约束问题.如今用遗传算法解决非线性等式与不等式约束最优化有几种满足约束的策略:拒绝策略、改进策略、算子策略和惩罚策略[2].前三种策略不会产生不可行解,无法考虑可行域外的解,对于约束严的问题不可行解在种群中占的比例很大,因此将搜索限制在可行域内就很难找到可行解.惩罚策略不拒绝每代中的不可行解,其中一些个体可能提供关于最优解的更有用的信息,通过对不可行解的惩罚来将约束问题转换为无约束问题,任何对约束的违反都要在目标函数中添加惩罚项.因此,允许在搜索空间里的不可行域中进行搜索能实现更快更好的最终解.惩罚函数就是在遗传搜索中考虑不可行解的技术,给不可行解根据具体情况给予惩罚.如何设计一个好的惩罚函数就是关键.设计惩罚函数没有一般的指导性原则.Homaifar,Qi和Lai方法构造的惩罚函数简单,但不够精确.Joines和Houck设计的惩罚函数对参数太敏感.本文在两个定义基础上构造一个新的惩罚函数,并用两个例子说明该方法是有效可行的.
2　遗传算法
遗传算法是一种从适者生存概念和自然中抽象出来的基因运算,是基于自然选择机制和自然基因的相对较新的联合搜索方法.基因算法与其他的最优化方法相比有4点不同:
1)遗传算法运算的是解集的编码,而不是解集本身
　[收稿日期]
　[基金项目]安徽省重点教学研究项目(2001011)
92大　学　数　学　　　　　　　　　　　　　　第21卷2)遗传算法的搜索始于解的一种群,而不是单个解.
3)遗传算法用的是目标函数本身,而不使用目标函数和约束函数的导数.
4)遗传算法采用概率的,而不是确定的状态转移规则.遗传算法第一次是由Holland提出,自从提出以后,由于遗传算法不同于传统的最优化方法,有其灵活性和易变性.在基本的遗传算法中,许多文学中的变异,选择,交叉,平行计算被改进发展来加速方法的收敛和方法的有效性[4].遗传操作主要有三种:
1)选择算子(Selection/reproduction):选择算子从群体中按某一概率成对选择个体,某个体x被选择的概率Pi与其适应度值成正比.最通常的实现方法是轮盘赌(roulettewheel)模型.
21交叉算子(Crossover):交叉算子将被选中的两个个体的基因链按概率Pc进行交叉,生成两个新的个体,交叉位置是随机的.其中Pc是一个系统参数.
31变异算子(Mutation):变异算子将新个体的基因链的各位按概率(0,1编码)来说即是取反.
h证明了一般的遗传算法不一定收敛,).
,,或者叫满意解.从数,而计算过程是一个有限自动机,因此通过遗传算法程序求得的解总是一个近似解.近似解与问题真正的最优解的差是一个统计意义下的量,也就是说每次程序运行得到的解的质量可能是有较大的差别的.遗传算法一般采用二进制编码与实数编码.
3　惩罚函数的改进及Matlab实现
现在定义点x与可行域之间的距离d(x,Q)及非可行点可行度FD(x),在这两个定义的基础上提出了一种新的惩罚函数.
一般形式的约束非线性规划问题为
maxf(x)=f(x1,x2,…,xn)
s.t.　x∈Q={x∈En|gi(x)≤0,i=1,2,…,m1;hj(x)=0,j=1,2,…,m2}.
d(x,Q)=max{0,gmax(x),hmax(x)},
gmax(x)=max{gi(x),i=1,2,…,m1},　hmax(x)=max{|hj(x)|,j=1,2,…,m2}[5],
d(x,Q)是点x与可行域Q之间为点超出约束的最大值,且反映了点x与可行域Q的关系.若d(x,Q)=0,则x∈Q;若d(x,Q)&0,则x|Q.d(x,Q)越大,表明x离可行域Q越远.定义
FD(x)=γλ∑i(x)+∑j(x)m2
1,gi(x)≤0,1,hj(x)=0,
,γi(x)=1-,gmax(x)0&gi(x)≤gmax(x),λ　　i(x)=1-hmax(x)其它.
FD(x)也反映了x与可行域之间的关系.如果FD(x)=1,则x∈Q,若FD(x)=0,即gi(x)=gmax(x),i=1,2,…,m1;hj(x)=hmax(x),j=1,2,…,m2,则点完全不属于可行域.如果0&FD(x)&1,
x|Q(记FD(x)为FD),且FD越大,突破约束越小.由上面的两个定义,可构造一个新的惩罚函数来处理x在不可行域的适值函数.
第1期　　　　　　　　　　倪金林:遗传算法求解约束非线性规划及Matlab实现
f(x),x∈Q,
f(x)≥0,x|Q,
f(x)&0,x|Q,93eval(x)=,(d(x,Q)+1/(FD+α))pf(x)3(d(x,Q)+1/(FD+α))p,
其中p,α为参数,满足p≥1,α&0.根据不同的情形,选择p,α的值.上面的惩罚函数在处理极大化的问题时,若x在可行域之内,等于目标函数值;不在可行域内,根据x突破约束的程度来改变适值,脱离约
))p在p≥1,α&0时也越大(d(x,Q)+1/束越大,d(x,Q),1/FD越大,(d(x,Q)+1/(FD+α
(FD+α))p.在p≥1,α&0时恒大于1,所以求得的eval(x)越小于目标函数值.在遗传算法中被选取的概率越小,这也就达到了惩罚的目的.下面通过具体的例子来说明.先计算一个求约束非线性规划最小化问题
2例1　minF=x31+2x2x3+2x3,
2s.t.　x21+x2+x3=4,
x1-x2+2x3≤2,
x1,x2,x3≥0.2
(SQP)方法及新的惩罚函数遗传算法(p=115,α=013)表1
F一般GA算法(α=10)5一般GA算法(α=100)4SQPe-009新算法
　　应用上面的惩罚函数在p=115,α=013时,得到的解为
x1=010000,　x2=410000,　x3=010000,　f1(x1,x2,x3)=010000,
且满足约束条件.上例用新惩罚函数的遗传算法的算法跟踪结果为图1.
上面的例子说明在解非线性规划问题时,新构造的惩罚函数在遗传算法中可以得到更好的解.新的构造方法对于每代中根据具体的个体重新计算d(x,Q),1/FD,让d(x,Q),1/FD随着迭代进行而一直处于动态变化中.
再举一个求最大化最优解的例子.
94大　学　数　学　　　　　　　　　　　　　　第21卷
2例2　maxf(x)=-2x21+2x1x2-2x2+4x1+6x2,
s.t.　2x1-x2≤0,
x1+5x2≤5,
对这个问题,应用可行方向法、惩罚函数法和上面新惩罚函数的遗传算法(p=115,α=011)的解对比结果如表2.
F可行方向法544惩罚函数法566基于权重GA6129Homairfar的GA1新的算法0165896　　
1,x,6130.根据上表说明传统GA差,Homaifar的GA(r1=02),而新的惩罚函数的遗传算法(p=115,α=011)的结果[6].但是新的惩罚函数的遗传算法比基于权重的遗传算法简单.例2新惩罚函数的遗传算法的算法跟踪结果为图2.因为初始种群是随机产生,每次曲线可能不同,但最后的目标函数基本相同.
新的惩罚函数的遗传算法应用在上面的两个例子:一个求最大化,一个求最小化得到的最优解比传统的解决约束非线性规划问题的方法、一般的遗传算法得到的结果都好,非常接近实际最优解.通过上述两个例子,参数p在[1,6],α在[]内取值,容易得到比较好的解.由于遗传算法的初始的解是通过随机生成的,
所以程序每次运行的结果可能不完全一样,但每次的结果误差都控制在一定的范围之内.可见,新的惩罚函数的遗传算法对于解决约束非线性规划问题是完全可行的,并且得到的结果优于传统的解决约束非线性规划问题的方法:可行方向法,惩罚函数法.比一般的遗传算法也要好.4　结　　论
解约束非线性规划问题一直是运筹学的一个难点.对于这个问题,已经有很多常规传统的解法,如可行方向法,惩罚函数法等.但这些方法计算复杂且结果不精确.遗传算法兴起以后,很快就应用到解决约束非线性规划问题.惩罚函数的选取一直是遗传算法的核心.本文根据两种脱离可行域程度函数d(x,Q),FD来构造一种新的惩罚函数对突破可行域的x进行惩罚.d(x,Q),FD都是随着x的变化而
第1期　　　　　　　　　　倪金林:遗传算法求解约束非线性规划及Matlab
实现95动态地改变,因此能够更好地对每个具体的x进行处理.用两种度量函数d(x,Q),FD联合处理,互相补充,用两个参数调节解,能较好地得到最优解.通过两个实例,应用Matlab进一步论证了这种方法的可操作性.
[参　考　文　献]
[1]　运筹学教材编写组.运筹学[M].北京:清华大学出版社,.
[2]　[日]玄光男,程润伟.遗传算法与工程设计[M].北京:科学出版社,.
[3]　[日]玄光男,程润伟.遗传算法与工程设计[M].北京:科学出版社,.
[4]　GuanJiabao,MustafaMAral.Progressivegeneticalgorithmforsolutionofoptimizationproblemswithnonlinear
equalityandinequalityconstraints[J].AppliedMathematicalModelling,-343.
[5]　唐加福,汪定伟,许宝栋,李露.基于评价函数的遗传算法解性规[J决策,2000,15
(5):573-576.
[6]　唐加福,汪定伟.(5):490-493.
ThewithNonliearConstraintsProgramming
GeneticAlgorithmandDemonstrationbyMatlab
(HefeiUniversityofTechnology,Hefei230009,China)
Abstract:Tooptimizationwithnonlinearconstraintsprogramming,traditionalmethod,suchasfeasibledirection,penaltyfunction,iscomplicatedandimprecise.Solvingoptimizationwithnonlinearconstraintsprogrammingbygeneticalgorithm,penaltyfunctioniscore.Theformergeneticalgorithmwithpenaltyfunctionisnotperfect,impreciseandcomplicated.Basedontwodefinition,thenewpenaltyfunctionisfound.Throughtnewpenaltyfunction,thearticledevelopsthenewmethodofsolutionofoptimizationwithnonliearconstraintsprogramming.Twoexamplesshowthattheimprovedmethodiseffective.
Keywords:genetic
optimizationwithnonliearco
包含各类专业文献、行业资料、中学教育、各类资格考试、专业论文、文学作品欣赏、幼儿教育、小学教育、高等教育、生活休闲娱乐、遗传算法求解约束非线性规划及Matlab实现_图文29等内容。