遗传算法求解约束非线性规划及Matlab实现

第21卷第1期大　学　数　学Vol.21,№.1 2005年2月COLL EGE MA T H EMA TICS Feb.2005遗传算法求解约束非线性规划及Matlab实现

倪金林

(合肥工业大学理学院应用数学系,合肥230009)

[摘　要]对于约束非线性规划问题,传统的方法:可行方向法、惩罚函数法计算烦琐且精度不高.用新兴的遗传算法来解决约束非线性规划,核心是惩罚函数的构造.以前的惩罚函数遗传算法有的精度较低,有的过于复杂.本文在两个定义的基础上构造了新的惩罚函数,并在新的惩罚函数的基础上,提出了一种解决约束非线性最优化问题的方法.通过两个例子应用Matlab说明了这个算法的可行性.

[关键词]遗传算法;约束非线性规划;惩罚函数;交叉;变异

[中图分类号]O22112 [文献标识码]A [文章编号]167221454(2005)0120091205

1　引 言

约束非线性规划问题是运筹学中的一个重要分支,现实生活中许多实际问题都不能表达为容易解决的线性模型,如地下水调整系统和地下水污染来源识别问题中就不可避免非线性规划问题.解决约束非线性问题的方法也很多.一般方法,如可行方向法,惩罚函数法[1]都计算复杂且精度不高.遗传算法是一个新兴的方法,1975年Holland在他的著作《Adaptation in Nat ural and Artifical Systems》中首次提出遗传算法,很快就用遗传算法来解决非线性最优问题.而用遗传算法解决非线性等式与不等式约束最优化问题的核心问题是如何满足约束问题.如今用遗传算法解决非线性等式与不等式约束最优化有几种满足约束的策略:拒绝策略、改进策略、算子策略和惩罚策略[2].前三种策略不会产生不可行解,无法考虑可行域外的解,对于约束严的问题不可行解在种群中占的比例很大,因此将搜索限制在可行域内就很难找到可行解.惩罚策略不拒绝每代中的不可行解,其中一些个体可能提供关于最优解的更有用的信息,通过对不可行解的惩罚来将约束问题转换为无约束问题,任何对约束的违反都要在目标函数中添加惩罚项.因此,允许在搜索空间里的不可行域中进行搜索能实现更快更好的最终解.惩罚函数就是在遗传搜索中考虑不可行解的技术,给不可行解根据具体情况给予惩罚.如何设计一个好的惩罚函数就是关键.设计惩罚函数没有一般的指导性原则.Homaifar,Qi和Lai方法构造的惩罚函数简单,但不够精确. Joines和Houck设计的惩罚函数对参数太敏感.本文在两个定义基础上构造一个新的惩罚函数,并用两个例子说明该方法是有效可行的.

2　遗传算法

遗传算法是一种从适者生存概念和自然中抽象出来的基因运算,是基于自然选择机制和自然基因的相对较新的联合搜索方法.基因算法与其他的最优化方法相比有4点不同:

1)遗传算法运算的是解集的编码,而不是解集本身.

　[收稿日期]2004201225

　[基金项目]安徽省重点教学研究项目(2001011)

2)遗传算法的搜索始于解的一种群,而不是单个解.

3)遗传算法用的是目标函数本身,而不使用目标函数和约束函数的导数.

4)遗传算法采用概率的,而不是确定的状态转移规则.

遗传算法第一次是由Holland提出,自从提出以后,由于遗传算法不同于传统的最优化方法,有其灵活性和易变性.在基本的遗传算法中,许多文学中的变异,选择,交叉,平行计算被改进发展来加速方法的收敛和方法的有效性[4].遗传操作主要有三种:

1)选择算子(Selection/rep roduction):选择算子从群体中按某一概率成对选择个体,某个体x被选择的概率Pi与其适应度值成正比.最通常的实现方法是轮盘赌(roulette wheel)模型.

21交叉算子(Crossover):交叉算子将被选中的两个个体的基因链按概率Pc进行交叉,生成两个新的个体,交叉位置是随机的.其中Pc是一个系统参数.

31变异算子(Mutation):变异算子将新个体的基因链的各位按概率Pm进行变异,对二值基因链(0,1编码)来说即是取反.

对于遗传算法的收敛性一些研究人员对进化算法的运行机理进行过研究,Radolp h证明了一般的遗传算法不一定收敛,只有每代保存了最优个体时才收敛.对保存最优个体时遗传算法是收敛的结论的证明是通过对遗传算法构造马尔柯夫(Markov)链,因为遗传算法的进行过程是一个马尔柯夫过程.

当遗传算法收敛时,求到的解通常只是所要解决问题的最优解的一个近似解,或者叫满意解.从数学分析的角度看,收敛过程是一个无限逼近过程,而计算过程是一个有限自动机,因此通过遗传算法程序求得的解总是一个近似解.近似解与问题真正的最优解的差是一个统计意义下的量,也就是说每次程序运行得到的解的质量可能是有较大的差别的.遗传算法一般采用二进制编码与实数编码.

3　惩罚函数的改进及Matlab实现

现在定义点x与可行域之间的距离d(x,Q)及非可行点可行度FD(x),在这两个定义的基础上提出了一种新的惩罚函数.

一般形式的约束非线性规划问题为

max f(x)=f(x1,x2,…,x n)

s.t.　x∈Q={x∈E n|g i(x)≤0,i=1,2,…,m1;h j(x)=0,j=1,2,…,m2}.

定义

d(x,Q)=max{0,g max(x),h max(x)},

其中

g max(x)=max{g i(x),i=1,2,…,m1},　h max(x)=max{|h j(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)=∑

m1

i=1

γ

i

(x)+∑

m2

j=1

λ

j

(x)

m1+m2

,

其中

γ

i (x)=

1,g i(x)≤0,

1-

g i(x)

g max(x)

,0

λi(x)=

1,h j(x)=0,

1-

|h j(x)|

h max(x)

,其它.

FD(x)也反映了x与可行域之间的关系.如果FD(x)=1,则x∈Q,若FD(x)=0,即g i(x)=g max(x), i=1,2,…,m1;h j(x)=h max(x),j=1,2,…,m2,则点完全不属于可行域.如果0

29大　学　数　学 第21卷

eval (x )=f (x ),x ∈Q ,

f (x )(d (x ,Q )+1/(FD +α))p ,f (x )≥0,x |Q ,

f (x )3(d (x ,Q )+1/(FD +α))p ,

f (x )<0,x |Q ,其中p ,α为参数,满足p ≥1,α>0.根据不同的情形,选择p ,α的值.上面的惩罚函数在处理极大化的问题时,若x 在可行域之内,等于目标函数值;不在可行域内,根据x 突破约束的程度来改变适值,脱离约

束越大,d (x ,Q ),1/FD 越大,(d (x ,Q )+1/(FD +α

))p 在p ≥1,α>0时也越大(d (x ,Q )+1/(FD +α))p .在p ≥1,α>0时恒大于1,所以求得的eval (x )越小于目标函数值.在遗传算法中被选取的概率越小,这也就达到了惩罚的目的.下面通过具体的例子来说明.先计算一个求约束非线性规划最小化问题

例1　min F =x 31+2x 22x 3+2x 3,

s.t.　x 21+x 2+x 23=4,

x 2

1-x 2+2x 3≤2,

x 1,x 2,x 3≥0.对于上面的实例应用一般的遗传算法,

序列二次规划(S Q P )方法及新的惩罚函数遗传算法(p =115,α=013)的结果如表1.

表1

变量

一般GA 算法(α=10)一般GA 算法(α=100)SQ P 新算法精确解x 1

015647011098010016010000010000x 2

316549319849410000410000410000x 3

010000010000010000010000010000F 0118035010026441194e -009010000010000

应用上面的惩罚函数在p =115,α=013时,得到的解为

x 1=010000,　x 2=410000,　x 3=010000,　f 1(x 1,x 2,x 3)=010000,

且满足约束条件.上例用新惩罚函数的遗传算法的算法跟踪结果为图1.

图1

上面的例子说明在解非线性规划问题时,新构造的惩罚函数在遗传算法中可以得到更好的解.新的构造方法对于每代中根据具体的个体重新计算d (x ,Q ),1/FD ,让d (x ,Q ),1/FD 随着迭代进行而一直处于动态变化中.

再举一个求最大化最优解的例子.

39第1期 倪金林:遗传算法求解约束非线性规划及Matlab 实现

例2　max f (x )=-2x 21+2x 1x 2-2x 22+4x 1+6x 2,

s.t.　2x 1-x 2≤0,

x 1+5x 2≤5,

x 1,x 2≥0.

对这个问题,应用可行方向法、惩罚函数法和上面新惩罚函数的遗传算法(p =115,α=011)的解对比结果如表2.

表2变量

可行方向法惩罚函数法基于权重GA Homairfar 的GA 新的算法x 1

016300164501658016205016589x 2

018740186901868017701018682F 6154461566616129616312616130

上面的约束非线性最优化的实际最优解是x 1=01658,x 2=01868,F =616130.根据上表说明传统的解决约束非线性规划问题的方法可行方向法、惩罚函数法的方法的解比基于权重GA 差,Homaifar 的GA (r 1=019,r 2=1)得到的解结果也不是很好,而新的惩罚函数的遗传算法(p =115,α=011)的结果与基于权重的遗传算法[6]都相当于最优解.但是新的惩罚函数的遗传算法比基于权重的遗传算法简单.例2新惩罚函数的遗传算法的算法跟踪结果为图2.因为初始种群是随机产生,每次曲线可能不同,但最后的目标函数基本相同.

图2

新的惩罚函数的遗传算法应用在上面的两个例子:一个求最大化,一个求最小化得到的最优解比传统的解决约束非线性规划问题的方法、一般的遗传算法得到的结果都好,非常接近实际最优解.通过上述两个例子,参数p 在[1,6],α在[0101,015]内取值,容易得到比较好的解.由于遗传算法的初始的解是通过随机生成的,所以程序每次运行的结果可能不完全一样,但每次的结果误差都控制在一定的范围之内.可见,新的惩罚函数的遗传算法对于解决约束非线性规划问题是完全可行的,并且得到的结果优于传统的解决约束非线性规划问题的方法:可行方向法,惩罚函数法.比一般的遗传算法也要好.4　结 论

解约束非线性规划问题一直是运筹学的一个难点.对于这个问题,已经有很多常规传统的解法,如可行方向法,惩罚函数法等.但这些方法计算复杂且结果不精确.遗传算法兴起以后,很快就应用到解决约束非线性规划问题.惩罚函数的选取一直是遗传算法的核心.本文根据两种脱离可行域程度函数d (x ,Q ),FD 来构造一种新的惩罚函数对突破可行域的x 进行惩罚.d (x ,Q ),FD 都是随着x 的变化而

49大　学　数　学 第21卷

动态地改变,因此能够更好地对每个具体的x 进行处理.用两种度量函数d (x ,Q ),FD 联合处理,互相补充,用两个参数调节解,能较好地得到最优解.通过两个实例,应用Matlab 进一步论证了这种方法的可操作性.

[参　考　文　献]

[1]　运筹学教材编写组.运筹学[M ].北京:清华大学出版社,2000.180-189.

[2]　[日]玄光男,程润伟.遗传算法与工程设计[M ].北京:科学出版社,2000.36-38.

[3]　[日]玄光男,程润伟.遗传算法与工程设计[M ].北京:科学出版社,2000.39-40.

[4]　Guan Jiabao ,Mustafa M Aral.Progressive genetic algorithm for solution of optimization problems with nonlinear

equality and inequality constraints[J ].Applied Mathematical Modelling ,1999,23:324-343.

[5]　唐加福,汪定伟,许宝栋,李露.基于评价函数的遗传算法求解非线性规划问题[J ].控制与决策,2000,15

(5):573-576.

[6]　唐加福,汪定伟.一种求解非线性规划问题的改进遗传算法[J ].东北大学学报,1997,18(5):490-493.

The Solution of Optimization with Nonliear Constraints Programming

with G enetic Algorithm and Demonstration by Matlab

N I J i n 2li n

(Hefei University of Technology ,Hefei 230009,China )

Abstract :To optimization with nonlinear constraints programming ,traditional method ,such as feasible direction ,penalty f unction ,is complicated and imprecise.Solving optimization with nonlinear constraints programming by genetic algorithm ,penalty f unction is core.The former genetic algorithm with penalty f unction is not perfect ,imprecise and complicated.Based on two definition ,the new penalty f unction is found.Throught new penalty f unction ,the article develops the new method of solution of optimization with nonliear constraints programming.Two examples show that the improved method is effective.

K ey w ords :genetic

algorithm ;optimization with nonliear constraints programming ;penalty f unction ;mutation ;crossover 59第1期 倪金林:遗传算法求解约束非线性规划及Matlab 实现

实例matlab-非线性规划-作业

实例matlab-非线性规划-作业

现代设计方法-工程优化理论、方法与设计 姓名 学号 班级 研 问题 ： 某厂向用户提供发动机，合同规定，第一、二、三季度末分别交货40台、60台、80台。每季度的生产费用为 （元），其中x 是该季生产的台数。若交货后有剩余，可用于下季度交货，但需支付存储费，每台每季度c 元。已知工厂每季度最大生产能力为100台，第一季度开始时无存货，设a=50、b=0.2、c=4，问工厂应如何安排生产计划，才能既满足合同又使总费用最低。讨论a 、b 、c 变化对计划的影响，并作出合理的解释。 问题的分析和假设： 问题分析：本题是一个有约束条件的二次规划问题。决策变量是工厂每季度生产的台数，目标函数是总费用（包括生产费用和存储费）。约束条件是生产合同，生产能力的限制。在这些条件下需要如何安排生产计划，才能既满足合同又使总费用最低。 问题假设： 1、工厂最大生产能力不会发生变化； 2、合同不会发生变更； 3、第一季度开始时工厂无存货； 4、生产总量达到180台时，不在进行生产； 5、工厂生产处的发动机质量有保证，不考虑退货等因素； 6、不考虑产品运输费用是否有厂家承担等和生产无关的因素。 符号规定： x1——第一季度生产的台数； x2——第二季度生产的台数； 180-x1-x2——第三季度生产的台数； y1——第一季度总费用； y2——第二季度总费用； y3——第三季度总费用； y ——总费用（包括生产费用和存储费）。 ()2bx ax x f +=

建模： 1、第一、二、三季度末分别交货40台、60台、80台； 2、每季度的生产费用为 （元）； 3、每季度生产数量满足40 ≤x1≤100，0≤x2≤100，100≤x1+x2 ≤180； 4、要求总费用最低，这是一个目标规划模型。 目标函数: y1 2111x b x a Z ?+?= y2()4012222-?+?+?=x c x b x a Z y3()()()10018018021221213 -+?+--?+--?=x x c x x b x x a Z y x x x x x x Z Z Z Z 68644.04.04.0149201 212221321--+++=++= 40≤x1≤100 0≤x2≤100 100≤x1+x2≤180 ()2 bx ax x f +=

遗传算法MATLAB完整代码(不用工具箱)

遗传算法解决简单问题 %主程序：用遗传算法求解y=200*exp(-0.05*x).*sin(x)在区间[-2,2]上的最大值clc; clear all; close all; global BitLength global boundsbegin global boundsend bounds=[-2,2]; precision=0.0001; boundsbegin=bounds(:,1); boundsend=bounds(:,2); %计算如果满足求解精度至少需要多长的染色体 BitLength=ceil(log2((boundsend-boundsbegin)'./precision)); popsize=50; %初始种群大小 Generationmax=12; %最大代数 pcrossover=0.90; %交配概率 pmutation=0.09; %变异概率 %产生初始种群 population=round(rand(popsize,BitLength)); %计算适应度，返回适应度Fitvalue和累计概率cumsump [Fitvalue,cumsump]=fitnessfun(population); Generation=1; while Generation

运用Matlab进行线性规划求解(实例)

线性规划 线性规划是处理线性目标函数和线性约束的一种较为成熟的方法，目前已经广泛应用于军事、经济、工业、农业、教育、商业和社会科学等许多方面。 8.2.1 基本数学原理 线性规划问题的标准形式是： ????? ??????≥=+++=+++=++++++=0,,,min 21221122222121112 121112211n m n mn m m n n n n n n x x x b x a x a x a b x a x a x a b x a x a x a x c x c x c z 或 ???? ?????=≥===∑∑==n j x m i b x a x c z j n j i j ij n j j j ,,2,1,0,,2,1,min 1 1 写成矩阵形式为： ?? ???≥==O X b AX CX z min 线性规划的标准形式要求使目标函数最小化，约束条件取等式，变量b 非负。不符合这几个条件的线性模型可以转化成标准形式。 MATLAB 采用投影法求解线性规划问题，该方法是单纯形法的变种。 8.2.2 有关函数介绍 在MATLAB 工具箱中，可用linprog 函数求解线性规划问题。 linprog 函数的调用格式如下： ●x=linprog(f,A,b)：求解问题minf'*x ，约束条件为A*x<=b 。 ●x=linprog(f,A,b,Aeq,beq)：求解上面的问题，但增加等式约束，即Aeq*x=beq 。若没有不等式约束，则令A=[ ],b=[ ]。 ●x=linprog(f,A,b,Aeq,beq,lb,ub)：定义设计x 的下界lb 和上界ub ，使得x 始终在该范围内。若没有等式约束，令Aeq=[ ],beq=[ ]。 ●x=linprog(f,A,b,Aeq,beq,lb,ub,x0)：设置初值为x0。该选项只适用于中型问题，默认时大型算法将忽略初值。 ●x=linprog(f,A,b,Aeq,beq,lb,ub,x0,options)：用options 指定的优化参数进行最小化。 ●[x,fval]=linprog(…)：返回解x 处的目标函数值fval 。 ●[x,lambda,exitflag]=linprog(…)：返回exitflag 值，描述函数计算的退出条件。 ●[x,lambda,exitflag,output]=linprog(…)：返回包含优化信息的输出参数output 。 ●[x,fval,exitflag,output,lambda]=linprog(…)：将解x 处的拉格朗日乘子返回到lambda 参数中。

MATLAB课程遗传算法实验报告及源代码

硕士生考查课程考试试卷 考试科目： 考生姓名：考生学号： 学院：专业： 考生成绩： 任课老师(签名) 考试日期：年月日午时至时

《MATLAB 教程》试题： A 、利用MATLA B 设计遗传算法程序，寻找下图11个端点最短路径，其中没有连接端点表示没有路径。要求设计遗传算法对该问题求解。 a e h k B 、设计遗传算法求解f (x)极小值，具体表达式如下： 321231(,,)5.12 5.12,1,2,3i i i f x x x x x i =?=???-≤≤=? ∑ 要求必须使用m 函数方式设计程序。 C 、利用MATLAB 编程实现：三名商人各带一个随从乘船渡河，一只小船只能容纳二人，由他们自己划行，随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货，但是如何乘船渡河的大权掌握在商人手中，商人们怎样才能安全渡河？ D 、结合自己的研究方向选择合适的问题，利用MATLAB 进行实验。 以上四题任选一题进行实验，并写出实验报告。

选择题目： B 、设计遗传算法求解f (x)极小值，具体表达式如下： 321231(,,)5.12 5.12,1,2,3i i i f x x x x x i =?=???-≤≤=? ∑ 要求必须使用m 函数方式设计程序。 一、问题分析（10分） 这是一个简单的三元函数求最小值的函数优化问题，可以利用遗传算法来指导性搜索最小值。实验要求必须以matlab 为工具，利用遗传算法对问题进行求解。 在本实验中，要求我们用M 函数自行设计遗传算法，通过遗传算法基本原理，选择、交叉、变异等操作进行指导性邻域搜索，得到最优解。 二、实验原理与数学模型（20分） （1）试验原理： 用遗传算法求解函数优化问题，遗传算法是模拟生物在自然环境下的遗传和进化过程而形成的一种自适应全局优化概率搜索方法。其采纳了自然进化模型，从代表问题可能潜在解集的一个种群开始，种群由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体；初始种群产生后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的解：在每一代，概据问题域中个体的适应度大小挑选个体；并借助遗传算子进行组合交叉和主客观变异，产生出代表新的解集的种群。这一过程循环执行，直到满足优化准则为止。最后，末代个体经解码，生成近似最优解。基于种群进化机制的遗传算法如同自然界进化一样，后生代种群比前生代更加适应于环境，通过逐代进化，逼近最优解。 遗传算法是一种现代智能算法，实际上它的功能十分强大，能够用于求解一些难以用常规数学手段进行求解的问题，尤其适用于求解多目标、多约束，且目标函数形式非常复杂的优化问题。但是遗传算法也有一些缺点，最为关键的一点，即没有任何理论能够证明遗传算法一定能够找到最优解，算法主要是根据概率论的思想来寻找最优解。因此，遗传算法所得到的解只是一个近似解，而不一定是最优解。 （2）数学模型 对于求解该问题遗传算法的构造过程： （1）确定决策变量和约束条件；

基于遗传算法的matlab源代码

function youhuafun D=code; N=50;%Tunable maxgen=50;%Tunable crossrate=0.5;%Tunable muterate=0.08;%Tunable generation=1; num=length(D); fatherrand=randint(num,N,3); score=zeros(maxgen,N); while generation<=maxgen ind=randperm(N-2)+2;%随机配对交叉 A=fatherrand(:,ind(1:(N-2)/2)); B=fatherrand(:,ind((N-2)/2+1:end)); %多点交叉 rnd=rand(num,(N-2)/2); ind=rnd tmp=A(ind); A(ind)=B(ind); B(ind)=tmp; %%两点交叉 %for kk=1:(N-2)/2 %rndtmp=randint(1,1,num)+1; %tmp=A(1:rndtmp,kk); %A(1:rndtmp,kk)=B(1:rndtmp,kk); %B(1:rndtmp,kk)=tmp; %end fatherrand=[fatherrand(:,1:2),A,B]; %变异 rnd=rand(num,N); ind=rnd[m,n]=size(ind); tmp=randint(m,n,2)+1; tmp(:,1:2)=0; fatherrand=tmp+fatherrand; fatherrand=mod(fatherrand,3); %fatherrand(ind)=tmp; %评价、选择 scoreN=scorefun(fatherrand,D);%求得N个个体的评价函数 score(generation,:)=scoreN; [scoreSort,scoreind]=sort(scoreN); sumscore=cumsum(scoreSort); sumscore=sumscore./sumscore(end); childind(1:2)=scoreind(end-1:end); for k=3:N tmprnd=rand; tmpind=tmprnd difind=[0,diff(t mpind)]; if~any(difind) difind(1)=1; end childind(k)=scoreind(logical(difind)); end fatherrand=fatherrand(:,childind); generation=generation+1; end %score maxV=max(score,[],2); minV=11*300-maxV; plot(minV,'*');title('各代的目标函数值'); F4=D(:,4); FF4=F4-fatherrand(:,1); FF4=max(FF4,1); D(:,5)=FF4; save DData D function D=code load youhua.mat %properties F2and F3 F1=A(:,1); F2=A(:,2); F3=A(:,3); if(max(F2)>1450)||(min(F2)<=900) error('DATA property F2exceed it''s range (900,1450]') end %get group property F1of data,according to F2value F4=zeros(size(F1)); for ite=11:-1:1 index=find(F2<=900+ite*50); F4(index)=ite; end D=[F1,F2,F3,F4]; function ScoreN=scorefun(fatherrand,D) F3=D(:,3); F4=D(:,4); N=size(fatherrand,2); FF4=F4*ones(1,N); FF4rnd=FF4-fatherrand; FF4rnd=max(FF4rnd,1); ScoreN=ones(1,N)*300*11; %这里有待优化

遗传算法Matlab程序

% f(x)=11*sin(6x)+7*cos(5x),0<=x<=2*pi; %%初始化参数 L=16;%编码为16位二进制数 N=32;%初始种群规模 M=48;%M个中间体，运用算子选择出M/2对母体，进行交叉；对M个中间体进行变异 T=100;%进化代数 Pc=0.8;%交叉概率 Pm=0.03;%%变异概率 %%将十进制编码成16位的二进制，再将16位的二进制转成格雷码 for i=1:1:N x1(1,i)= rand()*2*pi; x2(1,i)= uint16(x1(1,i)/(2*pi)*65535); grayCode(i,:)=num2gray(x2(1,i),L); end %% 开始遗传算子操作 for t=1:1:T y1=11*sin(6*x1)+7*cos(5*x1); for i=1:1:M/2 [a,b]=min(y1);%找到y1中的最小值a，及其对应的编号b grayCodeNew(i,:)=grayCode(b,:);%将找到的最小数放到grayCodeNew中grayCodeNew(i+M/2,:)=grayCode(b,:);%与上面相同就可以有M/2对格雷码可以作为母体y1(1,b)=inf;%用来排除已找到的最小值 end for i=1:1:M/2 p=unidrnd(L);%生成一个大于零小于L的数，用于下面进行交叉的位置if rand()

遗传算法经典MATLAB代码资料讲解

遗传算法经典学习Matlab代码 遗传算法实例: 也是自己找来的，原代码有少许错误，本人都已更正了，调试运行都通过了的。 对于初学者，尤其是还没有编程经验的非常有用的一个文件 遗传算法实例 % 下面举例说明遗传算法% % 求下列函数的最大值% % f(x)=10*sin(5x)+7*cos(4x) x∈[0,10]% % 将x 的值用一个10位的二值形式表示为二值问题，一个10位的二值数提供的分辨率是每为(10-0)/(2^10-1)≈0.01。% % 将变量域[0,10] 离散化为二值域[0,1023], x=0+10*b/1023, 其 中 b 是[0,1023] 中的一个二值数。% % % %--------------------------------------------------------------------------------------------------------------% %--------------------------------------------------------------------------------------------------------------% % 编程 %----------------------------------------------- % 2.1初始化(编码) % initpop.m函数的功能是实现群体的初始化，popsize表示群体的大小，chromlength表示染色体的长度(二值数的长度)，

% 长度大小取决于变量的二进制编码的长度(在本例中取10位)。 %遗传算法子程序 %Name: initpop.m %初始化 function pop=initpop(popsize,chromlength) pop=round(rand(popsize,chromlength)); % rand随机产生每个单元 为{0,1} 行数为popsize，列数为chromlength的矩阵， % roud对矩阵的每个单元进行圆整。这样产生的初始种群。 % 2.2 计算目标函数值 % 2.2.1 将二进制数转化为十进制数(1) %遗传算法子程序 %Name: decodebinary.m %产生[2^n 2^(n-1) ... 1] 的行向量，然后求和，将二进制转化为十进制 function pop2=decodebinary(pop) [px,py]=size(pop); %求pop行和列数 for i=1:py pop1(:,i)=2.^(py-i).*pop(:,i); end pop2=sum(pop1,2); %求pop1的每行之和 % 2.2.2 将二进制编码转化为十进制数(2) % decodechrom.m函数的功能是将染色体(或二进制编码)转换为十进制，参数spoint表示待解码的二进制串的起始位置

Matlab非线性规划

一般非线性规划 标准型为： min F(X) s.t AX<=b b e q X A e q =? G(X)0≤ Ceq(X)=0 VLB ≤X ≤VUB 其中X 为n 维变元向量，G(X)与Ceq(X)均为非线性函数组成的向量，其它变量的含义与线性规划、二次规划中相同.用Matlab 求解上述问题，基本步骤分三步： 1. 首先建立M 文件fun.m,定义目标函数F （X ）: function f=fun(X); f=F(X); 2. 若约束条件中有非线性约束:G(X)0≤或Ceq(X)=0,则建立M 文件nonlcon.m 定义函数G(X)与Ceq(X): function [G,Ceq]=nonlcon(X) G=... Ceq=... 3. 建立主程序.非线性规划求解的函数是fmincon,命令的基本格式如下： (1) x=fmincon (‘fun’,X0,A,b) (2) x=fmincon (‘fun’,X0,A,b,Aeq,beq) (3) x=fmincon (‘fun’,X0,A,b, Aeq,beq,VLB,VUB) (4) x=fmincon (‘fun’,X0,A,b,Aeq,beq,VLB,VUB,’nonlcon’) (5)x=fmincon (‘fun’,X0,A,b,Aeq,beq,VLB,VUB,’nonlcon’,options) (6) [x,fval]= fmincon(...) (7) [x,fval,exitflag]= fmincon(...) (8)[x,fval,exitflag,output]= fmincon(...) 注意： [1] fmincon 函数提供了大型优化算法和中型优化算法。默认时，若在

遗传算法解决非线性规划问题的Matlab程序

通常，非线性整数规划是一个具有指数复杂度的NP问题，如果约束较为复杂，Matlab优 化工具箱和一些优化软件比如lingo等，常常无法应用，即使能应用也不能给出一个较为令 人满意的解。这时就需要针对问题设计专门的优化算法。下面举一个遗传算法应用于非线性整数规划的编程实例，供大家参考! 模型的形式和适应度函数定义如下: nun ￡ =迟叼匸［（1_冏）督 i-1 /-I J=K乙员-??严丿=12 M…严 ▼ 0 或1* 适应度函数为3 Fi tn叱O）=》〔?巾1口｛＞?（卡（￡）一/；0?门））转幷亠 Z j'-i 50 4 S0 其中比=2、即士￡ = ￡ =瓦％■，口（1-务），马；j^ = s = ■ x v' y- to.8,02）., /-I i-L i-1 E 这是一个具有200个01决策变量的多目标非线性整数规划，编写优化的目标函数如下，其 中将多目标转化为单目标采用简单的加权处理。 fun ctio n Fit ness=FITNESS(x,FARM,e,q,w) %%适应度函数 %输入参数列表 % x 决策变量构成的 4X50的0-1矩阵 % FARM 细胞结构存储的当前种群，它包含了个体x

% e 4 X50的系数矩阵 % q 4 X50的系数矩阵 % w 1 X50的系数矩阵 %% gamma=0.98; N=length(FARM);% 种群规模 F1=zeros(1,N); F2=zeros(1,N); for i=1:N xx=FARM{i}; ppp=(1-xx)+(1-q).*xx; F1(i)=sum(w.*prod(ppp)); F2(i)=sum(sum(e.*xx)); end ppp=(1-x)+(1-q).*x; f1=sum(w.*prod(ppp)); f2=sum(sum(e.*x)); Fitness=gamma*sum(min([sign(f1-F1);zeros(1,N)]))+(1-gamma)*sum(min([sign(f2- F2);zeros(1,N)])); 针对问题设计的遗传算法如下，其中对模型约束的处理是重点考虑的地方 function [Xp,LC1,LC2,LC3,LC4]=MYGA(M,N,Pm) %% 求解 01 整数规划的遗传算法 %% 输入参数列表

遗传算法的MATLAB程序实例

遗传算法的程序实例 如求下列函数的最大值 f(x)=10*sin(5x)+7*cos(4x) x∈[0,10] 一、初始化(编码) initpop.m函数的功能是实现群体的初始化，popsize表示群体的大小，chromlength表示染色体的长度(二值数的长度)， 长度大小取决于变量的二进制编码的长度(在本例中取10位)。 代码: %Name: initpop.m %初始化 function pop=initpop(popsize,chromlength) pop=round(rand(popsize,chromlength)); % rand随机产生每个单元为 {0,1} 行数为popsize，列数为chromlength的矩阵， % roud对矩阵的每个单元进行圆整。这样产生的初始种群。 二、计算目标函数值 1、将二进制数转化为十进制数(1) 代码: %Name: decodebinary.m %产生 [2^n 2^(n-1) ... 1] 的行向量，然后求和，将二进制转化为十进制 function pop2=decodebinary(pop) [px,py]=size(pop); %求pop行和例数 for i=1:py pop1(:,i)=2.^(py-1).*pop(:,i); py=py-1; end pop2=sum(pop1,2); %求pop1的每行之和 2、将二进制编码转化为十进制数(2) decodechrom.m函数的功能是将染色体(或二进制编码)转换为十进制，参数spoint表示待解码的二进制串的起始位置。(对于多个变量而言，如有两个变量，采用20为表示，每个变量10为，则第一个变量从1开始，另一个变量从11开始。本例为1)，参数1ength表示所截取的长度（本例为10）。 代码: %Name: decodechrom.m %将二进制编码转换成十进制 function pop2=decodechrom(pop,spoint,length) pop1=pop(:,spoint:spoint+length-1); pop2=decodebinary(pop1); 3、计算目标函数值 calobjvalue.m函数的功能是实现目标函数的计算，其公式采用本文示例仿真，可根据不同优化问题予以修改。

遗传算法的原理及MATLAB程序实现

1 遗传算法的原理 1.1 遗传算法的基本思想 遗传算法（genetic algorithms，GA）是一种基于自然选择和基因遗传学原理，借鉴了生物进化优胜劣汰的自然选择机理和生物界繁衍进化的基因重组、突变的遗传机制的全局自适应概率搜索算法。 遗传算法是从一组随机产生的初始解（种群）开始，这个种群由经过基因编码的一定数量的个体组成，每个个体实际上是染色体带有特征的实体。染色体作为遗传物质的主要载体，其内部表现（即基因型）是某种基因组合，它决定了个体的外部表现。因此，从一开始就需要实现从表现型到基因型的映射，即编码工作。初始种群产生后，按照优胜劣汰的原理，逐代演化产生出越来越好的近似解。在每一代，根据问题域中个体的适应度大小选择个体，并借助于自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集的种群。这个过程将导致种群像自然进化一样，后代种群比前代更加适应环境，末代种群中的最优个体经过解码，可以作为问题近似最优解。 计算开始时，将实际问题的变量进行编码形成染色体，随机产生一定数目的个体，即种群，并计算每个个体的适应度值，然后通过终止条件判断该初始解是否是最优解，若是则停止计算输出结果，若不是则通过遗传算子操作产生新的一代种群，回到计算群体中每个个体的适应度值的部分，然后转到终止条件判断。这一过程循环执行，直到满足优化准则，最终产生问题的最优解。图1-1给出了遗传算法的基本过程。 1.2 遗传算法的特点 1.2.1 遗传算法的优点 遗传算法具有十分强的鲁棒性，比起传统优化方法，遗传算法有如下优点： 1. 遗传算法以控制变量的编码作为运算对象。传统的优化算法往往直接利用控制变量的实际值的本身来进行优化运算，但遗传算法不是直接以控制变量的值，而是以控制变量的特定形式的编码为运算对象。这种对控制变量的编码处理方式，可以模仿自然界中生物的遗传和进化等机理，也使得我们可以方便地处理各种变量和应用遗传操作算子。 2. 遗传算法具有内在的本质并行性。它的并行性表现在两个方面，一是遗传

基于遗传算法的BP神经网络MATLAB代码

用遗传算法优化BP神经网络的Matlab编程实例（转） 由于BP网络的权值优化是一个无约束优化问题，而且权值要采用实数编码，所以直接利用Matlab遗传算法工具箱。以下贴出的代码是为一个19输入变量，1个输出变量情况下的非线性回归而设计的，如果要应用于其它情况，只需改动编解码函数即可。 程序一：GA训练BP权值的主函数 function net=GABPNET(XX,YY) %-------------------------------------------------------------------------- % GABPNET.m % 使用遗传算法对BP网络权值阈值进行优化，再用BP算法训练网络 %-------------------------------------------------------------------------- %数据归一化预处理 nntwarn off XX=[1:19;2:20;3:21;4:22]'; YY=[1:4]; XX=premnmx(XX); YY=premnmx(YY); YY %创建网络 net=newff(minmax(XX),[19,25,1],{'tansig','tansig','purelin'},'tra inlm'); %下面使用遗传算法对网络进行优化 P=XX; T=YY; R=size(P,1); S2=size(T,1); S1=25;%隐含层节点数 S=R*S1+S1*S2+S1+S2;%遗传算法编码长度 aa=ones(S,1)*[-1,1]; popu=50;%种群规模 save data2 XX YY % 是将 xx,yy 二个变数的数值存入 data2 这个MAT-file，initPpp=initializega(popu,aa,'gabpEval');%初始化种群 gen=100;%遗传代数

遗传算法的MATLAB程序实例讲解学习

遗传算法的M A T L A B 程序实例

遗传算法的程序实例 如求下列函数的最大值 f(x)=10*sin(5x)+7*cos(4x) x∈[0,10] 一、初始化(编码) initpop.m函数的功能是实现群体的初始化，popsize表示群体的大小，chromlength表示染色体的长度(二值数的长度)， 长度大小取决于变量的二进制编码的长度(在本例中取10位)。 代码: %Name: initpop.m %初始化 function pop=initpop(popsize,chromlength) pop=round(rand(popsize,chromlength)); % rand随机产生每个单元为 {0,1} 行数为popsize，列数为chromlength的矩阵， % roud对矩阵的每个单元进行圆整。这样产生的初始种群。 二、计算目标函数值 1、将二进制数转化为十进制数(1) 代码: %Name: decodebinary.m %产生 [2^n 2^(n-1) ... 1] 的行向量，然后求和，将二进制转化为十进制 function pop2=decodebinary(pop) [px,py]=size(pop); %求pop行和例数 for i=1:py pop1(:,i)=2.^(py-1).*pop(:,i); py=py-1; end pop2=sum(pop1,2); %求pop1的每行之和 2、将二进制编码转化为十进制数(2) decodechrom.m函数的功能是将染色体(或二进制编码)转换为十进制，参数spoint表示待解码的二进制串的起始位置。(对于多个变量而言，如有两个变量，采用20为表示，每个变量10为，则第一个变量从1开始，另一个变量从11开始。本例为1)，参数1ength表示所截取的长度（本例为10）。 代码: %Name: decodechrom.m %将二进制编码转换成十进制 function pop2=decodechrom(pop,spoint,length) pop1=pop(:,spoint:spoint+length-1); pop2=decodebinary(pop1); 3、计算目标函数值 calobjvalue.m函数的功能是实现目标函数的计算，其公式采用本文示例仿真，可根据不同优化问题予以修改。

完整word版matlab解非线性规划例题

关于非线性规划问题 背景： 线性规划问题，即目标函数和约束条件都是线性函数的规划问题，但在实际工作中，还常常会遇到另一类更一般的规划问题，即目标函数和约束条件中至少有一个是非线性函数问题，即非线性规划问题。 求解方法：Matlab软件 问题： 某厂向用户提供发动机，合同规定，第一、二、三季度末分别f(x)?ax?bx^2（元）交货50台、70台、90台。，每季度的生产费用为x是该季度生产的台数，若交货有剩余可用于下季度交货，但需其中c元。已知工厂每季度最大生产能力为100支付存储费，每季度每台bca=4,问工厂如何安排每台，第一季度开始时无存货，设=0.2,=50,月生产计划，才能既满足合同又使总费用最低（包括生产费用和库存费用）。 问题分析与假设： F(x)。目标函数是总费用，记为约束条件是生产合同和生产能力的限制。 x1x2台，则第三季度生产台，第二季度生产设第一季度生产(210?x1?x2)台。则： 120?x1?x2?210 50?x1?1000?x2?100 bca=4,

=0.2,=50,由． T1?50x1?0.2x1^2，第一季度生产费用 k1?4(x1?50)，剩余品存储到下一季度的费用 T2?50x2?0.2x2^2同理可得： k2?4(x1?x2?120) T3?50(210?x1?x2)?0.2(210?x1?x2)^2 建模 总费用 F(x)?T1?T2?T3?k1?k2?10300?0.2(x1^2?x2^2)?0.2(210?x1?x2)^2?4(2x1?x2?120)先建立M-文件: a=50;b=0.2;c=4; H=diag(2*b*ones(1,3));C=[a+2*c,a+c,a]; A1=[-1,0,0;-1,-1,0];b1=[-50,-120]'; A2=[1 1 1];b2=210; v1=[0 0 0]';v2=[100 100 100]'; [x,faval,exitflag,output,lambada]=quadprog(H,C,A1,b1,A2,b2,v1,v2,[]) X2=x'*H*x/2+C*x-140*c 再建立主程序: a=50;b=0.2;c=4; H=diag(2*b*ones(1,3));C=[a+2*c,a+c,a]; A1=[-1,0,0;-1,-1,0];b1=[-50,-100]'; A2=[1 1 1];b2=210; v1=[0 0 0]';v2=[100 100 100]'; [x,faval,exitflag,output,lambada]=quadprog(H,C,A1,b1,A2,b2,v1,v2,[]) X2=x'*H*x/2+C*x-140*c 运算结果： x =

简单的遗传算法MATLAB实现

遗传算法是对达尔文生物进化理论的简单模拟，其遵循“适者生存”、“优胜略汰”的原理。遗传算法模拟一个人工种群的进化过程，并且通过选择、杂交以及变异等机制，种群经过若干代以后，总是达到最优（或近最优）的状态。 自从遗传算法被提出以来，其得到了广泛的应用，特别是在函数优化、生产调度、模式识别、神经网络、自适应控制等领域，遗传算法更是发挥了重大的作用，大大提高了问题求解的效率。遗传算法也是当前“软计算”领域的重要研究课题。 本文首先结合MATLAB对遗传算法实现过程进行详细的分析，然后通过1个实际的函数优化案例对其应用进行探讨。 1. 遗传算法实现过程 现实生活中很多问题都可以转换为函数优化问题，所以本文将以函数优化问题作为背景，对GA的实现过程进行探讨。大部分函数优化问题都可以写成求最大值或者最小值的形式，为了不是一般性，我们可以将所有求最优值的情况都转换成求最大值的形式，例如，求函数f(x)的最大值，

若是求函数f(x)的最小值，可以将其转换成 g(x)=-f(x)，然后求g(x)的最大值， 这里x可以是一个变量，也可是是一个由k个变量组成的向量,x=(x1, x2, …, x k)。每个x i,i=1,2,…,k, 其定义域为D i，D i=[a i, b i]。 一般规定f(x)在其定义域内只取正值，若不满足，可以将其转换成以下形式， 其中C是一个正常数。 1.1 编码与解码 要实现遗传算法首先需要弄清楚如何对求解问题进行编码和解码。对于函数优化问题，一般来说，有两种编码方式，一是实数编码，一是二进制编码，两者各有优缺点，二进制编码具有稳定性高、种群多样性大等优点，但是需要的存储空间大，需要解码过程并且难以理解；而实数编码直接用实数表示基因，容易理解并且不要解码过程，但是容易过早收敛，从而陷入局部最优。本文以最常用的二进制编码为例，说明遗传编码的过程。

MATLAB非线性优化fmincon

active-set and sqp algorithms 不接受用户提供的海塞矩阵，对拉格朗日的海塞矩阵提供一个拟牛顿的近似值； 目标函数估值次数与迭代次数？ 优化成功或失败 一、求解失败 1、在到达迭代次数阈值或目标函数估值次数阈值时，求解器没有最小化目标到要求的精度，此时求解器停止。接下来，可以尝试以下方法： （1）设置‘Display’为‘iter’，查看每步的迭代信息，这些信息包括：目标函数（Fval or f(x) or Resnorm）是否是下降的；检查约束越界（Max constraint）是否是递减趋向于0；查看一阶优化是否是递减趋向于0；查看置信域半径(Trust-region radius)是否下降趋向于一个小的值。若其中至少一种情况为是，就表示结果是不断改善的。如果结果是不断改善的，可以采取下边的措施：设置MaxIter、MaxFunEvals比默认值大的值，默认值可以在优化工具箱或求解器的函数参考页的优化表中查看；从最后计算出的点开始重新求解。如果结果没有改善，尝试以下其他的方法。（2）放松精度 如果TolX或TolFun太小，当求解器达到一个最小值时可能也不会识别到，这就会导致无限次徒劳的迭代。DiffMaxChange和DiffMinChange选项能影响求解器的改善，它们控制求导估计中有限差分的步长。 （3）从不同的初始点重新开始求解

（4）检查目标函数和约束函数的定义 举个例子，可以检查目标函数和非线性约束函数在某些特定点处返回正确的值。不可行的点不一定导致函数的错误。 （5）对问题进行中心化和标准化 当每个坐标轴对目标函数和约束函数有相同的影响时，求解器更能可靠的运行，对每个坐标轴方向乘以合适的量使得每个坐标轴的影响相同，在特定的坐标轴上加上合适的值使得它们长度一致。 （6）提供解析的梯度和雅可比矩阵 如果用户不提供解析的梯度或雅可比矩阵，求解器会用有限差分来估计这些值，因此提供这些导数可以减少运算时间，提高计算准确度。 对于约束问题，提供梯度还有另一个好处----求解器到达一个点x 时能满足该点是可行的，但有限差分在x点周围可能会导致不可行的点，在这种情况下，求解器可能会失败或突然中断。（7）提供海塞矩阵 当提供海塞矩阵时，求解器能运行的更可靠，而且运行的次数比较少。 2、无可行点 在TolCon约束精度内，求解器不能找到一个满足所有约束条件的点，此时，可以尝试以下方法： （1）检查线性约束

遗传算法求函数极大值(matlab实现)

遗传算法求函数最大值(matlab实现) 一、题目： 寻找f(x)=x2,,当x在0~31区间的最大值。 二、源程序： %遗传算法求解函数最大值 %本程序用到了英国谢菲尔德大学(Sheffield)开发的工具箱GATBX，该工具箱比matlab自带的GATOOL使用更加灵活，但在编写程序方面稍微复杂一些 Close all; Clear all; figure(1); fplot('variable*variable',[0,31]); %画出函数曲线 %以下定义遗传算法参数 GTSM=40; %定义个体数目 ZDYCDS=20; %定义最大遗传代数 EJZWS=5; %定义变量的二进制位数 DG=0.9; %定义代沟 trace=zeros(2, ZDYCDS); %最优结果的初始值

FieldD=[5;-1;2;1;0;1;1]; %定义区域描述器的各个参数%以下为遗传算法基本操作部分，包括创建初始种群、复制、交叉和变异 Chrom=crtbp(GTSM, EJZWS); %创建初始种群，即生成给定 规模的二进制种群和结构gen=0; %定义代数计数器初始值variable=bs2rv(Chrom, FieldD); %对生成的初始种群进行十进制转换 ObjV=variable*variable; %计算目标函数值f(x)=x2 while gen