数学建模遗传算法与优化问题

数学建模遗传算法与优

化问题

Document number：NOCG-YUNOO-BUYTT-UU986-1986UT

实验十遗传算法与优化问题

一、问题背景与实验目的

遗传算法（Genetic Algorithm—GA），是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，它是由美国Michigan大学的教授于1975年首先提出的．遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、适于并行处理及应用范围广等显着特点，奠定了它作为21世纪关键智能计算之一的地位．

本实验将首先介绍一下遗传算法的基本理论，然后用其解决几个简单的函数最值问题，使读者能够学会利用遗传算法进行初步的优化计算．1．遗传算法的基本原理

遗传算法的基本思想正是基于模仿生物界遗传学的遗传过程．它把问题的参数用基因代表，把问题的解用染色体代表（在计算机里用二进制码表示），从而得到一个由具有不同染色体的个体组成的群体．这个群体在问题特定的环境里生存竞争，适者有最好的机会生存和产生后代．后代随机化地继承了父代的最好特征，并也在生存环境的控制支配下继续这一过程．群体的染色体都将逐渐适应环境，不断进化，最后收敛到一族最适应环境的类似个体，即得到问题最优的解．值得注意的一点是，现在的遗传算法是受生物进化论学说的启发提出的，这种学说对我们用计算机解决复杂问题很有用，而它本身是否完全正确并不重要（目前生物界对此学说尚有争议）．

（1）遗传算法中的生物遗传学概念

由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算法中要用到各种进化和遗传学的概念．

首先给出遗传学概念、遗传算法概念和相应的数学概念三者之间的对应关系．这些概念如下：

遗传算法计算优化的操作过程就如同生物学上生物遗传进化的过程，主要有三个基本操作（或称为算子）：选择（Selection）、交叉（Crossover）、变异（Mutation）．

遗传算法基本步骤主要是：先把问题的解表示成“染色体”，在算法中也就是以二进制编码的串，在执行遗传算法之前，给出一群“染色体”，也就是假设的可行解．然后，把这些假设的可行解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉、变异过程产生

更适应环境的新一代“染色体”群．经过这样的一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解．

下面给出遗传算法的具体步骤，流程图参见图1：

第一步：选择编码策略，把参数集合（可行解集合）转换染色体结构空间；

第二步：定义适应函数，便于计算适应值；

第三步：确定遗传策略，包括选择群体大小，选择、交叉、变异方法以及确定交叉概率、变异概率等遗传参数；

第四步：随机产生初始化群体；

第五步：计算群体中的个体或染色体解码后的适应值；

第六步：按照遗传策略，运用选择、交叉和变异算子作用于群体，形成下一代群体；

第七步：判断群体性能是否满足某一指标、或者是否已完成预定的迭代次数，不满足则返回第五步、或者修改遗传策略再返回第六步．

图1 一个遗传算法的具体步骤

遗传算法有很多种具体的不同实现过程，以上介绍的是标准遗传算法的主要步骤，此算法会一直运行直到找到满足条件的最优解为止．

2．遗传算法的实际应用

例1：设2()20.5f x x x =-++，求 max (), [1,2]f x x ∈-．

注：这是一个非常简单的二次函数求极值的问题，相信大家都会做．在此我们要研究的不是问题本身，而是借此来说明如何通过遗传算法分析和解决问题．

在此将细化地给出遗传算法的整个过程． （1）编码和产生初始群体

首先第一步要确定编码的策略，也就是说如何把1-到2这个区间内的数用计算机语言表示出来．

编码就是表现型到基因型的映射，编码时要注意以下三个原则： 完备性：问题空间中所有点（潜在解）都能成为GA 编码空间中的点（染色体位串）的表现型；

健全性：GA 编码空间中的染色体位串必须对应问题空间中的某一潜在解； 非冗余性：染色体和潜在解必须一一对应．

这里我们通过采用二进制的形式来解决编码问题，将某个变量值代表的个体表示为一个{0，1}二进制串．当然，串长取决于求解的精度．如果要设定求解精度到六位小数，由于区间长度为2(1)3--=，则必须将闭区间 [1,2]-分为6310?等分．因为216222097152231024194304=

将一个二进制串（b 21b 20b 19…b 1b 0）转化为区间[1,2]-内对应的实数值很简单，只需采取以下两步（Matlab 程序参见附录4）：

1）将一个二进制串（b 21b 20b 19…b 1b 0）代表的二进制数化为10进制数： 2）'x 对应的区间[1,2]-内的实数： 'x 2=2288967

利用这种方法我们就完成了遗传算法的第一步——编码，这种二进制编码的方法完全符合上述的编码的三个原则．

首先我们来随机的产生一个个体数为4个的初始群体如下： pop(1)={ <>， %% a1 <>， %% a2 <>， %% a3

<>} %% a4（Matlab 程序参见附录2） 化成十进制的数分别为： pop(1)={ ， ， ， }

接下来我们就要解决每个染色体个体的适应值问题了． （2）定义适应函数和适应值

由于给定的目标函数2()20.5f x x x =-++在[1,2]-内的值有正有负，所以必须通过建立适应函数与目标函数的映射关系，保证映射后的适应值非负，而且目标函数的优化方向应对应于适应值增大的方向，也为以后计算各个体的入选概率打下基础．

对于本题中的最大化问题，定义适应函数()g x ，采用下述方法：

式中min F 既可以是特定的输入值，也可以是当前所有代或最近K 代中()f x 的最小值，这里为了便于计算，将采用了一个特定的输入值．

若取min 1F =-，则当()1f x =时适应函数()2g x =；当() 1.1f x =-时适应函数()0g x =．

由上述所随机产生的初始群体，我们可以先计算出目标函数值分别如下（Matlab 程序参见附录3）：

f [pop(1)]={ , , , }

然后通过适应函数计算出适应值分别如下（Matlab 程序参见附录5、附录6）：

取min 1F =-， g[pop(1)]= { , , 0 , } （3）确定选择标准

这里我们用到了适应值的比例来作为选择的标准，得到的每个个体的适应值比例叫作入选概率．其计算公式如下：

对于给定的规模为n 的群体pop={123,,,

,n a a a a }，个体i a 的适应值为

()i g a ，则其入选概率为

由上述给出的群体，我们可以计算出各个个体的入选概率． 首先可得 4

1() 6.478330i i g a ==∑，

然后分别用四个个体的适应值去除以4

1

()i i g a =∑，得：

P (a 1)= / = %% a 1 P (a 2)= / = %% a 2

P (a 3)= 0 / = 0 %% a 3

P (a 4)= / = %% a 4（Matlab 程序参见附录7） （4）产生种群

计算完了入选概率后，就将入选概率大的个体选入种群，淘汰概率小的个体，并用入选概率最大的个体补入种群，得到与原群体大小同样的种群（Matlab 程序参见附录8、附录11）．

要说明的是：附录11的算法与这里不完全相同．为保证收敛性，附录11的算法作了修正，采用了最佳个体保存方法（elitist model ），具体内容将在后面给出介绍．

由初始群体的入选概率我们淘汰掉a 3，再加入a 2补足成与群体同样大小的种群得到newpop(1)如下：

newpop(1)={ <>， %% a 1 <>， %% a 2

<>， %% a2

<>} %% a4

（5）交叉

交叉也就是将一组染色体上对应基因段的交换得到新的染色体，然后得到新的染色体组，组成新的群体（Matlab程序参见附录9）．

我们把之前得到的newpop(1)的四个个体两两组成一对，重复的不配对，进行交叉．（可以在任一位进行交叉）

< >， <>

交叉得：

< >， <>

< 01000010>， <1000011>

交叉得：

< >， <>

通过交叉得到了四个新个体，得到新的群体jchpop (1)如下：

jchpop(1)={

<>，

<>，

<>，

<01101010>}

这里采用的是单点交叉的方法，当然还有多点交叉的方法，不过有些烦琐，这里就不着重介绍了．

（6）变异

变异也就是通过一个小概率改变染色体位串上的某个基因（Matlab程序参见附录10）．

现把刚得到的jchpop(1)中第3个个体中的第9位改变，就产生了变异，得到了新的群体pop(2)如下：

pop(2)= { <>， <>， <1>， <0110> }

然后重复上述的选择、交叉、变异直到满足终止条件为止． （7）终止条件

遗传算法的终止条件有两类常见条件：（1）采用设定最大（遗传）代数的方法，一般可设定为50代，此时就可能得出最优解．此种方法简单易行，但可能不是很精确（Matlab 程序参见附录1）；（2）根据个体的差异来判断，通过计算种群中基因多样性测度，即所有基因位相似程度来进行控制．

3．遗传算法的收敛性

前面我们已经就遗传算法中的编码、适应度函数、选择、交叉和变异等主要操作的基本内容及设计进行了详细的介绍．作为一种搜索算法，遗传算法通过对这些操作的适当设计和运行，可以实现兼顾全局搜索和局部搜索的所谓均衡搜索，具体实现见下图2所示．

图2 均衡搜索的具体实现图示

应该指出的是，遗传算法虽然可以实现均衡的搜索，并且在许多复杂问题的求解中往往能得到满意的结果，但是该算法的全局优化收敛性的理论分析尚待解决．目前普遍认为，标准遗传算法并不保证全局最优收敛．但是，在一定的约束条件下，遗传算法可以实现这一点．

下面我们不加证明地罗列几个定理或定义，供读者参考（在这些定理的证明中，要用到许多概率论知识，特别是有关马尔可夫链的理论，读者可参阅有关文献）．

定理1 如果变异概率为)1,0(∈m P ，交叉概率为]1,0[∈c P ，同时采用比例选择法（按个体适应度占群体适应度的比例进行复制），则标准遗传算法的变换矩阵P 是基本的．

定理2 标准遗传算法（参数如定理1）不能收敛至全局最优解．

由定理2可以知道，具有变异概率)1,0(∈m P ，交叉概率为]1,0[∈c P 以及按比例选择的标准遗传算法是不能收敛至全局最最优解．我们在前面求解例1时所

用的方法就是满足定理1的条件的方法．这无疑是一个令人沮丧的结论．

然而，庆幸的是，只要对标准遗传算法作一些改进，就能够保证其收敛性．具体如下：我们对标准遗传算法作一定改进，即不按比例进行选择，而是保留当前所得的最优解（称作超个体）．该超个体不参与遗传．

最佳个体保存方法（elitist model ）的思想是把群体中适应度最高的个体不进行配对交叉而直接复制到下一代中．此种选择操作又称复制（copy ）．De Jong 对此方法作了如下定义：

定义 设到时刻t （第t 代）时，群体中a *（t ）为最佳个体．又设A （t ＋1）为新一代群体，若A （t ＋1）中不存在a *（t ），则把a *(t )作为A （t ＋1）中的第n +1个个体（其中，n 为群体大小）（Matlab 程序参见附录11）．

采用此选择方法的优点是，进化过程中某一代的最优解可不被交叉和变异操作所破坏．但是，这也隐含了一种危机，即局部最优个体的遗传基因会急速增加而使进化有可能限于局部解．也就是说，该方法的全局搜索能力差，它更适合单峰性质的搜索空间搜索，而不是多峰性质的空间搜索．所以此方法一般都与其他选择方法结合使用．

定理3 具有定理1所示参数，且在选择后保留当前最优值的遗传算法最终能收敛到全局最优解．

当然，在选择算子作用后保留当前最优解是一项比较复杂的工作，因为该解在选择算子作用后可能丢失．但是定理3至少表明了这种改进的遗传算法能够收敛至全局最优解．有意思的是，实际上只要在选择前保留当前最优解，就可以保证收敛，定理4描述了这种情况．

定理4 具有定理1参数的，且在选择前保留当前最优解的遗传算法可收敛于全局最优解．

例2：设2()3f x x x =-+，求 max (), [0,2]f x x ∈，编码长度为5，采用上述定理4所述的“在选择前保留当前最优解的遗传算法”进行．

此略，留作练习．

二、相关函数（命令）及简介

本实验的程序中用到如下一些基本的Matlab 函数：ones, zeros, sum, size, length, subs, double 等，以及 for, while 等基本程序结构语句，读者可参考前面专门关于Matlab 的介绍，也可参考其他数学实验章节中的“相关函数（命令）及简介”内容，此略．

三、实验内容

上述例1的求解过程为：

群体中包含六个染色体，每个染色体用22位0—1码，变异概率为，变量区间为[1,2]

-，取Fmin=2

-，遗传代数为50代，则运用第一种终止条件（指定遗传代数）的Matlab程序为：

[Count,Result,BestMember]=Genetic1(22,6,'-x*x+2*x+',-1,2,-2,,50)

执行结果为：

Count =

50

Result =

BestMember =

图2 例1的计算结果

（注：上图为遗传进化过程中每一代的个体最大适应度；

而下图为目前为止的个体最大适应度——单调递增）我们通过Matlab软件实现了遗传算法，得到了这题在第一种终止条件下的最优解：当x取时，Max () 1.4990

f x=．

当然这个解和实际情况还有一点出入（应该是x取1时，

f x=），但对于一个计算机算法来说已经很不错了．

Max () 1.5000

我们也可以编制Matlab程序求在第二种终止条件下的最优解．此略，留作练习．实践表明，此时的遗传算法只要经过10代左右就可完成收敛，得到另一个“最优解”，与前面的最优解相差无几．

四、自己动手

1．用Matlab编制另一个主程序，求例1的在第二种终止条件下的最优解．

提示：一个可能的函数调用形式以及相应的结果为：

[Count,Result,BestMember]=Genetic2(22,6,'-x*x+2*x+',-1,2,-2,,

Count =

13

Result =

BestMember =

可以看到：两组解都已经很接近实际结果，对于两种方法所产生的最优解差异很小．可见这两种终止算法都是可行的，而且可以知道对于例1的问题，遗传算法只要经过10代左右就可以完成收敛，达到一个最优解．

2．按照例2的具体要求，用遗传算法求上述例2的最优解．

3．附录9子程序中的第3行到第7行为注解语句．若去掉前面的%号，则程序的算法思想有什么变化

4．附录9子程序中的第8行至第13行的程序表明，当Dim(1)>=3时，将交换数组Population的最后两行，即交换最后面的两个个体．其目的是什么5．仿照附录10子程序，修改附录9子程序，使得交叉过程也有一个概率值（一般取~）；同时适当修改主程序或主程序，以便代入交叉概率．

6．设2

f x x∈-，要设定求解精度到15位小

=--+，求max(),[2,2]

f x x x

()41

数．

五、附录

附录1：主程序

function

[Count,Result,BestMember]=Genetic1(MumberLength,MemberNumber,FunctionFitn ess,MinX,MaxX,Fmin,MutationProbability,Gen)

Population=PopulationInitialize(MumberLength,MemberNumber);

global Count;

global CurrentBest;

Count=1;

PopulationCode=Population;

PopulationFitness=Fitness(PopulationCode,FunctionFitness,MinX,MaxX,Mumbe rLength);

PopulationFitnessF=FitnessF(PopulationFitness,Fmin);

PopulationProbability=Probability(PopulationFitnessF);

[Population,CurrentBest,EachGenMaxFitness]=Elitist(PopulationCode,Populatio nFitness,MumberLength);

EachMaxFitness(Count)=EachGenMaxFitness;

MaxFitness(Count)=CurrentBest(length(CurrentBest));

while Count

NewPopulation=Select(Population,PopulationProbability,MemberNumber);

Population=NewPopulation;

NewPopulation=Crossing(Population,FunctionFitness,MinX,MaxX,MumberLength);

Population=NewPopulation;

NewPopulation=Mutation(Population,MutationProbability);

Population=NewPopulation;

PopulationFitness=Fitness(Population,FunctionFitness,MinX,MaxX,MumberLength);

PopulationFitnessF=FitnessF(PopulationFitness,Fmin);

PopulationProbability=Probability(PopulationFitnessF);

Count=Count+1;

[NewPopulation,CurrentBest,EachGenMaxFitness]=Elitist(Population,PopulationFitn ess,MumberLength);

EachMaxFitness(Count)=EachGenMaxFitness;;

MaxFitness(Count)=CurrentBest(length(CurrentBest));

Population=NewPopulation;

end

Dim=size(Population);

Result=ones(2,Dim(1));

for i=1:Dim(1)

Result(1,i)=Translate(Population(i,:),MinX,MaxX,MumberLength);

end

Result(2,:)=PopulationFitness;

BestMember(1,1)=Translate(CurrentBest(1:MumberLength),MinX,MaxX,Mumb erLength);

BestMember(2,1)=CurrentBest(MumberLength+1);

close all

subplot(211)

plot(EachMaxFitness)

subplot(212)

plot(MaxFitness)

【程序说明】主程序包含了8个输入参数：

(1) MumberLength：表示一个染色体位串的二进制长度．（例1中取22）

(2) MemberNumber：表示群体中染色体的个数．（例1中取6个）

(3) FunctionFitness ： 表示目标函数，是个字符串，因此用表达式时，用单引号括出．（例1中是2()20.5f x x x =-++）

(4) MinX ： 变量区间的下限．（例1中是[1,2]-中的） (5) MaxX ： 变量区间的上限．（例1中是[1,2]-中的 2）

(6) Fmin ： 定义适应函数过程中给出的一个目标函数的可能的最小值，由操作者自己给出．（例1中取Fmin=2-）

(7) MutationProbability ： 表示变异的概率，一般都很小．（例1中取） (8) Gen ： 表示遗传的代数，也就是终止程序时的代数．（例1中取50） 另外，主程序包含了3个输出值： Count 表示遗传的代数；Result 表示计算的结果，也就是最优解；BestMember 表示最优个体及其适应值． 附录2：子程序

function Population=PopulationInitialize(MumberLength,MemberNumber) Temporary=rand(MemberNumber,MumberLength); Population=(Temporary>=*ones(size(Temporary)));

【程序说明】子程序 用于产生一个初始群体．这个初始群体含有

MemberNumber 个染色体，每个染色体有MumberLength 个基因（二进制码）． 附录3：子程序

function PopulationFitness=

Fitness(PopulationCode,FunctionFitness,MinX,MaxX,MumberLength)

Dim=size(PopulationCode);

PopulationFitness=zeros(1,Dim(1)); for i=1:Dim(1)

PopulationFitness(i)=

Transfer(PopulationCode(i,:),FunctionFitness,MinX,MaxX,MumberLength);

end 【程序说明】子程序用于计算群体中每一个染色体的目标函数值．子程序中含有5个输入参数：PopulationCode 表示用0—1代码表示的群体，FunctionFitness 表示目标函数，它是一个字符串，因此写入调用程序时，应该用单引号括出，

MumberLength表示染色体位串的二进制长度．MinX和MaxX 分别指变量区间的上下限．

附录4：子程序

function PopulationData=Translate(PopulationCode,MinX,MaxX,MumberLength) PopulationData=0;

Dim=size(PopulationCode);

for i=1:Dim(2)

PopulationData=PopulationData+PopulationCode(i)*(2^(MumberLength-i));

end

PopulationData=MinX+PopulationData*(MaxX-MinX)/(2^Dim(2)-1);

【程序说明】子程序把编成码的群体翻译成变量的数值．含有4个输入参数，PopulationCode, MinX, MaxX, MumberLength．

附录5：子程序

function PopulationFitness=

Transfer(PopulationCode,FunctionFitness,MinX,MaxX,MumberLength) PopulationFitness=0;

PopulationData=Translate(PopulationCode,MinX,MaxX,MumberLength);

PopulationFitness=double(subs(FunctionFitness,'x',sym(PopulationData))); 【程序说明】子程序 Transfer 把群体中的染色体的目标函数值用数值表示出来，它是Fitness的重要子程序．其有5个输入参数分别为PopulationCode, FunctionFitness, MinX, MaxX，MumberLength．

附录6：子程序

function PopulationFitnessF=FitnessF(PopulationFitness,Fmin)

Dim=size(PopulationFitness);

PopulationFitnessF=zeros(1,Dim(2));

for i=1:Dim(2)

if PopulationFitness(i)>Fmin

PopulationFitnessF(i)=PopulationFitness(i)-Fmin;

end

if PopulationFitness(i)<=Fmin

PopulationFitnessF(i)=0;

end

end

【程序说明】子程序是用于计算每个染色体的适应函数值的．其输入参数如下：PopulationFitness 为群体中染色体的目标函数值，Fmin为定义适应函数过程中给出的一个目标函数的可能的最小值．

附录7：子程序

function PopulationProbability=Probability(PopulationFitness)

SumPopulationFitness=sum(PopulationFitness);

PopulationProbability=PopulationFitness/SumPopulationFitness;

【程序说明】子程序用于计算群体中每个染色体的入选概率，输入参数为群体中染色体的适应函数值PopulationFitness．

附录8：子程序

function NewPopulation=

Select(Population,PopulationProbability,MemberNumber)

CProbability(1)=PopulationProbability(1);

for i=2:MemberNumber

CProbability(i)=CProbability(i-1)+PopulationProbability(i);

end

for i=1:MemberNumber

r=rand(1);

Index=1;

while r>CProbability(Index)

Index=Index+1;

end

NewPopulation(i,:)=Population(Index,:);

end

【程序说明】子程序根据入选概率（计算累计概率）在群体中按比例选择部分染色体组成种群，该子程序的3个输入参数分别为：群体Population，入选概率PopulationProbability，群体中染色体的个数MemberNumber．

附录9：子程序

function NewPopulation=

Crossing(Population,FunctionFitness,MinX,MaxX,MumberLength)

%%PopulationFitness=

%% Fitness(Population,FunctionFitness,MinX,MaxX,MumberLength);

%%PopulationProbability=Probability(PopulationFitness);

%%[SortResult,SortSite]=sort(PopulationProbability);

%%Population=Population(SortSite,:);

Dim=size(Population);

if Dim(1)>=3

Temp=Population(Dim(1),:);

Population(Dim(1),:)=Population(Dim(1)-1,:);

Population(Dim(1)-1,:)=Temp;

end

for i=1:2:Dim(1)-1

SiteArray=randperm(Dim(2));

Site=SiteArray(1);

Temp=Population(i,1:Site);

Population(i,1:Site)=Population(i+1,1:Site);

Population(i+1,1:Site)=Temp;

end

NewPopulation=Population;

【程序说明】子程序用于群体中的交叉并产生新群体．其输入参数为：Population, FunctionFitness，MinX，MaxX，MumberLength．

附录10：子程序

function NewPopulation=Mutation(Population,MutationProbability)

Dim=size(Population);

for i=1:Dim(1)

Probability=rand(1);

Site=randperm(Dim(2));

if Probability

if Population(i,Site(1))==1

Population(i,Site(1))=0;

end

if Population(i,Site(1))==0

Population(i,Site(1))=1;

end

end

end

NewPopulation=Population;

【程序说明】子程序用于群体中少量个体变量并产生新的群体．输入参数为：群体Population和变异概率MutationProbability．

附录11：子程序

function [NewPopulationIncludeMax,CurrentBest,EachGenMaxFitness]= Elitist(Population,PopulationFitness,MumberLength)

global Count CurrentBest;

[MinFitness,MinSite]=min(PopulationFitness);

[MaxFitness,MaxSite]=max(PopulationFitness); EachGenMaxFitness=MaxFitness; if Count==1

CurrentBest(1:MumberLength)=Population(MaxSite,:);

CurrentBest(MumberLength+1)=PopulationFitness(MaxSite); else

if CurrentBest(MumberLength+1)

CurrentBest(MumberLength+1)=PopulationFitness(MaxSite); end

Population(MinSite,:)=CurrentBest(1:MumberLength); end

NewPopulationIncludeMax=Population;

【程序说明】子程序用到最佳个体保存方法（“优胜劣汰”思想）．输入参数为：群体Population, 目标函数值PopulationFitness 和染色体个数MumberLength ．

“遗传算法”专题

一、遗传算法的主要特征：

我们的目的是获得“最好解”，可以把这种任务看成是一个优化过程。对

于小空间，经典的穷举法就足够了；而对大空间，则需要使用特殊的人工智能技术。遗传算法(Genetic Algorithm)是这些技术中的一种，它是一类模拟生物进化过程而产生的由选择算子、杂交算子和变异算子三个基本算子组成的全局寻优算法。它从一个初始族出发，由选择算子选出性状好的父本，由杂交算子进行杂交运算，变异算子进行少许变异，在一定概率规则控制下随机搜索模型空间。一代代进化，直到最终解族对应的误差泛函值达到设定的要求。

遗传算法的结构：

图1. 遗传算法的结构

在第t 次迭代，遗传算法维持一个潜在解的群体},,,{)(2

1t

n t t x x x t p =。每个解t i x 用其“适应值”评价。然后通过选择更合适个体（1+t 次迭代）形成一个新的

群体。新的群体的成员通过杂交和变异进行变换，形成新的解。杂交组合了两

Procedure Genetic Algorithm

begin initialize )(t P evaluate )(t P

个亲体染色体（即待求参数的二进制编码串）的特征，通过交换父代相应的片断形成了两个相似的后代。例如父代染色体为),,,,(11111e d c b a 和

),,,,(22222e d c b a ，在第二个基因后杂交，产生的后代为),,,,(22211e d c b a 和

),,,,(11122e d c b a 。杂交算子的目的是在不同潜在解之间进行信息交换。变异是通过用一个等于变异率的概率随机地改变被选择染色体上的一个或多个基因（染色体中的一个二进制位）。变异算子的意图是向群体引入一些额外的变化性。

遗传算法的特点：

(1). 它不是直接作用于参变量集上，而是作用于参变量的某种编码形成的数字串上。

(2). 它不是从单个点，而是从一个解族开始搜索解空间，与传统的“点对点”式的

搜索方法不同。

(3). 它仅仅利用适应值信息评估个体的优劣，无须求导数或其它辅助信息。 (4). 它利用概率转移规则，而非确定性规则。

?优势：

(1). 不容易陷入局部极值，能以很大的概率找到全局最优解。 (2). 由于其固有的并行性，适合于大规模并行计算。

二、遗传算法的运行步骤：

1. 一般性描述：

不失一般性，考虑求最大值的问题。问题：

1） 编码和解码： 要达到要求的精度，每个域i D 应该被分割为610)(?-i i a b 个等尺寸的区间。用i m 表示使1210)(6-≤?-i

m i i a b 成立的最小整数。这样，对每个变量

i x ，由串长为i m 的二进制编码表达可以满足精度要求。以下的公式对应于每个串的自变量的值：

其中)(2string decimal 表示二进制串的十进制值。

代表一个潜在解的染色体被长度为∑==k i i m m 1的二进制串表达；前1m 位对应区间[11,b a ]里的一个值，随后的2m 位对应区间[22,b a ]里的一个值，等等；最后的k m 位对应区间[k k b a ,]里的一个值。

求一个有k 个变量的函数R R x x x f k k → :),,,(21 的f 的最大值。假设

每个变量i x 为域R b a D i i i ?=],[内的一个值，且对所有的i

i D x ∈，0),,(1>k x x f 。假定以某个要求的精度优化函数f ：这里取自变量

小数点后第6位。

2） 产生潜在解初始群体：

简单地以位的方式随机地设定size pop _个染色体。如果确实有一

些关于最优分布的知识，可以使用这些信息来设定初始潜在解的集合。 3） 根据适应值评价解的适应程度并据此生成新群体：

通常使用一个根据适应值调节刻度宽度的轮盘。按照如下方法构

造轮盘（假设这里的适应值时正值，否则可以使用一些比例机制调整）：

● 计算每个染色体)_,,1(size pop i i =v 的适应值)(i eval v ； ● 计算群体的总适应值：

● 计算每个染色体)_,,1(size pop i i =v 的选择概率i p ： ●

计算每个染色体)_,,1(size pop i i =v 的累计概率i q ：

对轮盘转动size pop _次，每次按照下面的方法为新群体选择一个单个的

染色体：

●

产生一个在区间[0，1]里的随机数；

● 如果1q r <，则选择第一个染色体1v ；否则选择使i i q r q ≤<-1成立的第i 个

染色体i v (size pop i _2<≤)。

这样做的效果是：好的染色体得到多个拷贝，中等染色体保持平稳，最差染色体死亡。

4） 杂交(crossover)和变异(mutation)——决定新群体的性状：

设杂交概率为c p ，此概率给出预计要进行杂交的染色体个数size pop p c _?。对于新群体中的每个染色体： ● 产生一个在区间[0，1]里的随机数r ；

● 如果c p r <，则选择给定的染色体进行杂交。

随机地对被选择的染色体配对：对染色体中的每一个，产生一个在区间[1, 1-m ]（m 为总长，即染色体位数）里的随机整数pos 。pos 表示杂交点的位置。两个染色体

)(121m pos pos b b b b b + 和 )(121m pos pos c c c c c +

被他们的子代

)(121m pos pos c c b b b + 和 )(121m pos pos b b c c c + 所替代。

下一步的变异，是在一位一位(bit-by-bit)的基础上进行的。另一个遗传系统参数，变异率m p ，给出了我们预计的变异位数：size pop m p m _??。整个群体中所有染色体的每一位都有均等的机会经历变异，即从0到1或者相反：

MATLAB实验遗传算法和优化设计

实验六 遗传算法与优化设计 一、实验目的 1. 了解遗传算法的基本原理和基本操作（选择、交叉、变异）； 2. 学习使用Matlab 中的遗传算法工具箱(gatool)来解决优化设计问题； 二、实验原理及遗传算法工具箱介绍 1. 一个优化设计例子 图1所示是用于传输微波信号的微带线(电极)的横截面结构示意图，上下两根黑条分别代表上电极和下电极，一般下电极接地，上电极接输入信号，电极之间是介质(如空气，陶瓷等)。微带电极的结构参数如图所示，W 、t 分别是上电极的宽度和厚度，D 是上下电极间距。当微波信号在微带线中传输时，由于趋肤效应，微带线中的电流集中在电极的表面，会产生较大的欧姆损耗。根据微带传输线理论，高频工作状态下（假定信号频率1GHz ），电极的欧姆损耗可以写成（简单起见，不考虑电极厚度造成电极宽度的增加）： 图1 微带线横截面结构以及场分布示意图 {} 28.6821ln 5020.942ln 20.942S W R W D D D t D W D D W W t D W W D e D D παπππ=+++-+++?????? ? ??? ??????????? ??????? (1) 其中πρμ0=S R 为金属的表面电阻率， ρ为电阻率。可见电极的结构参数影响着电极损耗，通过合理设计这些参数可以使电极的欧姆损耗做到最小，这就是所谓的最优化问题或者称为规划设计问题。此处设计变量有3个：W 、D 、t ，它们组成决策向量[W, D ,t ] T ，待优化函数(,,)W D t α称为目标函数。 上述优化设计问题可以抽象为数学描述： ()()min .. 0,1,2,...,j f X s t g X j p ????≤=? (2)

遗传算法与组合优化.

第四章 遗传算法与组合优化 4.1 背包问题（knapsack problem ） 4.1.1 问题描述 0/1背包问题：给出几个尺寸为S 1，S 2，…，S n 的物体和容量为C 的背包，此处S 1，S 2，…，S n 和C 都是正整数；要求找出n 个物件的一个子集使其尽可能多地填满容量为C 的背包。 数学形式： 最大化 ∑=n i i i X S 1 满足 ,1C X S n i i i ≤∑= n i X i ≤≤∈1},1,0{ 广义背包问题：输入由C 和两个向量C ＝(S 1，S 2，…，S n )和P ＝(P 1，P 2，…，P n )组成。设X 为一整数集合，即X ＝1，2，3，…，n ，T 为X 的子集，则问题就是找出满足约束条件∑∈≤T i i C X ，而使∑∈T i i P 获得最大的子集T ，即求S i 和P i 的下标子集。 在应用问题中，设S 的元素是n 项经营活动各自所需的资源消耗，C 是所能提供的资源总量，P 的元素是人们从每项经营活动中得到的利润或收益，则背包问题就是在资源有限的条件下，追求总的最大收益的资源有效分配问题。 广义背包问题可以数学形式更精确地描述如下： 最大化 ∑=n i i i X P 1 满足 ,1C X S n i i i ≤∑= n i X i ≤≤∈1},1,0{ 背包问题在计算理论中属于NP —完全问题，其计算复杂度为O (2n )，若允许物件可以部分地装入背包，即允许X ，可取从0.00到1.00闭区间上的实数，则背包问题就简化为极简单的P 类问题，此时计算复杂度为O (n )。

4.1.2 遗传编码 采用下标子集T 的二进制编码方案是常用的遗传编码方法。串T 的长度等于n(问题规模)，T i (1≤i ≤n )＝1表示该物件装入背包，T i ＝0表示不装入背包。基于背包问题有近似求解知识，以及考虑到遗传算法的特点（适合短定义距的、低阶的、高适应度的模式构成的积木块结构类问题），通常将P i ，S i 按P i /S i 值的大小依次排列，即P 1/S 1≥P 2/S 2≥…≥P n /S n 。 4.1.3 适应度函数 在上述编码情况下，背包问题的目标函数和约束条件可表示如下。 目标函数：∑==n i i i P T T J 1 )( 约束条件：C S T n i i i ≤∑=1 按照利用惩罚函数处理约束条件的方法，我们可构造背包问题的适应度函数f (T )如下式： f (T ) = J (T ) + g (T ) 式中g (T )为对T 超越约束条件的惩罚函数，惩罚函数可构造如下: 式中E m 为P i /S (1≤i ≤n )i 的最大值，β为合适的惩罚系数。 4.2 货郎担问题（Traveling Salesman Problem ——TSP ） 在遗传其法研究中，TSP 问题已被广泛地用于评价不同的遗传操作及选择机制的性能。之所以如此，主要有以下几个方面的原因： (1) TSP 问题是一个典型的、易于描述却难以处理的NP 完全（NP-complete ）问题。有效地 解决TSP 问题在可计算理论上有着重要的理论价值。 (2) TSP 问题是诸多领域内出现的多种复杂问题的集中概括和简化形式。因此，快速、有效 地解决TSP 问题有着极高的实际应用价值。 (3) TSP 问题因其典型性已成为各种启发式的搜索、优化算法的间接比较标准，而遗传算法 就其本质来说，主要是处理复杂问题的一种鲁棒性强的启发式随机搜索算法。因此遗传算法在TSP 问题求解方面的应用研究，对于构造合适的遗传算法框架、建立有效的遗传操作以及有效地解决TSP 问题等有着多方面的重要意义。

遗传算法与优化问题(重要,有代码)

实验十遗传算法与优化问题 一、问题背景与实验目的 遗传算法（Genetic Algorithm—GA），是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，它是由美国Michigan大学的J.Holland教授于1975年首先提出的．遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、适于并行处理及应用范围广等显著特点，奠定了它作为21世纪关键智能计算之一的地位． 本实验将首先介绍一下遗传算法的基本理论，然后用其解决几个简单的函数最值问题，使读者能够学会利用遗传算法进行初步的优化计算．1．遗传算法的基本原理 遗传算法的基本思想正是基于模仿生物界遗传学的遗传过程．它把问题的参数用基因代表，把问题的解用染色体代表（在计算机里用二进制码表示），从而得到一个由具有不同染色体的个体组成的群体．这个群体在问题特定的环境里生存竞争，适者有最好的机会生存和产生后代．后代随机化地继承了父代的最好特征，并也在生存环境的控制支配下继续这一过程．群体的染色体都将逐渐适应环境，不断进化，最后收敛到一族最适应环境的类似个体，即得到问题最优的解．值得注意的一点是，现在的遗传算法是受生物进化论学说的启发提出的，这种学说对我们用计算机解决复杂问题很有用，而它本身是否完全正确并不重要（目前生物界对此学说尚有争议）． （1）遗传算法中的生物遗传学概念 由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算法中要用到各种进化和遗传学的概念． 首先给出遗传学概念、遗传算法概念和相应的数学概念三者之间的对应关系．这些概念如下： 序号遗传学概念遗传算法概念数学概念 1 个体要处理的基本对象、结构也就是可行解 2 群体个体的集合被选定的一组可行解 3 染色体个体的表现形式可行解的编码 4 基因染色体中的元素编码中的元素 5 基因位某一基因在染色体中的位置元素在编码中的位置 6 适应值个体对于环境的适应程度， 或在环境压力下的生存能力可行解所对应的适应函数值 7 种群被选定的一组染色体或个体根据入选概率定出的一组 可行解 8 选择从群体中选择优胜的个体， 淘汰劣质个体的操作保留或复制适应值大的可行解，去掉小的可行解 9 交叉一组染色体上对应基因段的 交换根据交叉原则产生的一组新解 10 交叉概率染色体对应基因段交换的概 率（可能性大小）闭区间[0,1]上的一个值，一般为0.65~0.90 11 变异染色体水平上基因变化编码的某些元素被改变

数学建模的作用意义

数学建模的背景： 人们在观察、分析和研究一个现实对象时经常使用模型，如展览馆里的飞机模型、水坝模型，实际上，照片、玩具、地图、电路图等都是模型，它们能概括地、集中地反映现实对象的某些特征，从而帮助人们迅速、有效地了解并掌握那个对象。数学模型不过是更抽象些的模型。 当需要从定量的角度分析和研究一个实际问题时，人们就要在深入调查研究、了解对象信息、作出简化假设、分析内在规律等工作的基础上，用数学的符号和语言，把它表述为数学式子（称为数学模型），然后用通过计算得到的模型结果来解释实际问题，并接受实际的检验。这个全过程就称为数学建模。 近半个多世纪以来, 随着计算机技术的迅速发展，数学的应用不仅在工程技术、自然科学等领域发挥着越来越重要的作用, 而且以空前的广度和深度向经济、金融、生物、医学、环境、地质、人口、交通等新的领域渗透，所谓数学技术已经成为当代高新技术的重要组成部分。 不论是用数学方法在科技和生产领域解决哪类实际问题，还是与其它学科相结合形成交叉学科，首要的和关键的一步是建立研究对象的数学模型，并计算求解。人们常常把数学建模和计算机技术在知识经济时代的作用比喻为如虎添翼。 数学建模日益显示其重要作用，已成为现代应用数学的一个重要领域。为培养高质量、高层次人才，对理工、经济、金融、管理科学等各专业的大学生都提出“数学建模技能和素质方面的要求”。 数学建模在现代社会的一些作用 (1）在一般工程技术领域，数学建模仍然大有用武之地。在以声、光、热、力、电这些物理学科为基础的诸如机械、电机、土木、水利等工程技术领域中，数学建模的普遍性和重要性不言而喻，虽然这里的基本模型是已有的，但是由于新技术、新工艺的不断涌现，提出了许多需要用数学方法解决的新问题；高速、大型计算机的飞速发展，使得过去即便有了数学模型也无法求解的课题（如大型水坝的应力计算，中长期天气预报等）迎刃而解；建立在数学模型和计算机模拟基础上的CAD技术，以其快速、经济、方便等优势，大量地替代了传统工程设计中的现场实验、物理模拟等手段。 (2）在高新技术领域，数学建模几乎是必不可少的工具。无论是发展通讯、航天、微电子、自动化等高新技术本身，还是将高新技术用于传统工业去创造新工艺、开发新产品，计算机技术支持下的建模和模拟都是经常使用的有效手段。数学建模、数值计算和计算机图形学等相结合形成的计算机软件，已经被固化于产品中，在许多高新技术领域起着核心作用，被认为是高新技术的特征之一。在这个意义上，数学不再仅仅作为一门科学，它是许多技术的基础，而且直接走向了技术的前台。国际上一位学者提出了“高技术本质上是一种数学技术”的观点。 (3）数学迅速进入一些新领域，为数学建模开拓了许多新的处女地。随着数学向诸如经济、人口、生态、地质等所谓非物理领域的渗透，一些交叉学科如计量经济学、人口控制论、数学生态学、数学地质学等应运而生。一般地说，不存在作为支配关系的物理定律，当用数学方法研究这些领域中的定量关系时，数学建模就成为首要的、关键的步骤和这些学科发展与应用的基础。在这些领域里建立不同类型、不同方法、不同深浅程度模型的余地相当大，为数学建模提供了广阔的新天地。马克思说过，一门科学只有成功地运用数学时，才

基于遗传算法的多式联运组合优化

第四章基于遗传算法的集装箱多式联运运输组合优化模型 的求解 4.1 遗传算法简介 4.1.1 遗传算法 遗传算法(Genetic Algorithm,GA)是在20世纪六七十年代由美国密歇根大学的Holland J.H.教授及其学生和同事在研究人工自适应系统中发展起来的一种随机搜索方法,通过进一步的研究逐渐形成了一个完整的理论和方法体系取名为基本遗传算法(Simple Genetic Algorithm)。在接下来几年的研究过程中Holland在研究自然和人工系统的自适应行为的过程中采用了这个算法，并在他的著作《自然系统和人工系统的适配》中对基本遗传算法的理论和方法进行了系统的阐述与描写，同时提出了在遗传算法的理论研究和发展中具有极为重要的作用的模式理论，它的编码技术和遗传操作成为了遗传算法被广泛并成功的应用的基础，经过许多学者多年来的研究，遗传算法逐渐成熟起来，到现在已经成为了一个非常大的体系，广泛的应用于组合优化、系统优化、过程控制、经济预测、模式识别以及智能控制等多个领域。De Jong于1975年在他的博士论文中设计了一系列针对于各种函数优化问题的遗传算法的执行策略，详细分析了各项性能的评价指标。在此基础上，美国伊利诺大学的Goldberg于1989年系统全面的阐述了遗传算法理论，并通过例证对遗传算法的多领域应用进行了分析，为现代遗传算法的研究和发展奠定了基础。 遗传算法是一种模仿基于自然选择的生物进化过程的随机方法，它以类似于基因的编码作为种群的个体，首先，随机的产生初始种群的个体，从这个群体开始进行搜索，根据类似于生物适应能力的适应度函数值的大小，按照不同问题各自的特点，在当前的种群中运用适当的选择策略选择适应能力大的个体，其中所选择出来的个体经过遗传操作、交叉操作以及变异操作产生下一代种群个体。如此反复，像生物的进化过程一样逐代进化，直到满足期望的终止条件为止。

数学建模中常见的十大模型

数学建模常用的十大算法==转 (2011-07-24 16:13:14) 转载▼ 1. 蒙特卡罗算法。该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟来检验自己模型的正确性，几乎是比赛时必用的方法。 2. 数据拟合、参数估计、插值等数据处理算法。比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用MA TLAB 作为工具。 3. 线性规划、整数规划、多元规划、二次规划等规划类算法。建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo 软件求解。 4. 图论算法。这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备。 5. 动态规划、回溯搜索、分治算法、分支定界等计算机算法。这些算法是算法设计中比较常用的方法，竞赛中很多场合会用到。 6. 最优化理论的三大非经典算法：模拟退火算法、神经网络算法、遗传算法。这些问题是用来解决一些较困难的最优化问题的，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用。 7. 网格算法和穷举法。两者都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具。 8. 一些连续数据离散化方法。很多问题都是实际来的，数据可以是连续的，而计算机只能处理离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的。 9. 数值分析算法。如果在比赛中采用高级语言进行编程的话，那些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用。 10. 图象处理算法。赛题中有一类问题与图形有关，即使问题与图形无关，论文中也会需要图片来说明问题，这些图形如何展示以及如何处理就是需要解决的问题，通常使用MA TLAB 进行处理。 以下将结合历年的竞赛题，对这十类算法进行详细地说明。 以下将结合历年的竞赛题，对这十类算法进行详细地说明。 2 十类算法的详细说明 2.1 蒙特卡罗算法 大多数建模赛题中都离不开计算机仿真，随机性模拟是非常常见的算法之一。 举个例子就是97 年的A 题，每个零件都有自己的标定值，也都有自己的容差等级，而求解最优的组合方案将要面对着的是一个极其复杂的公式和108 种容差选取方案，根本不可能去求解析解，那如何去找到最优的方案呢？随机性模拟搜索最优方案就是其中的一种方法，在每个零件可行的区间中按照正态分布随机的选取一个标定值和选取一个容差值作为一种方案，然后通过蒙特卡罗算法仿真出大量的方案，从中选取一个最佳的。另一个例子就是去年的彩票第二问，要求设计一种更好的方案，首先方案的优劣取决于很多复杂的因素，同样不可能刻画出一个模型进行求解，只能靠随机仿真模拟。 2.2 数据拟合、参数估计、插值等算法 数据拟合在很多赛题中有应用，与图形处理有关的问题很多与拟合有关系，一个例子就是98 年美国赛A 题，生物组织切片的三维插值处理，94 年A 题逢山开路，山体海拔高度的插值计算，还有吵的沸沸扬扬可能会考的“非典”问题也要用到数据拟合算法，观察数据的

数学建模在经济学中的应用

数学建模在经济学中的应用 摘要：高校的经济学教学中经常会融入一些数学模型的思想，实际上数学模型的建立与经济学的教学和研究有着很大的内在联系，两者之间有着必然的关系，文本笔者将会从数学与经济学的关系出发，具体的介绍数学经济模型及其重要性，并对构建数学经济模型以及一些实例进行具体的论述。 关键词：数学模型；经济学；高校教学；应用 现如今的高校教学当中可以说数学建模与经济学之间有着密切的关系，任何一项经济学的研究和计算都离不开数学模型的建立，采用数学模型来辅助经济学的发展可以更加直观的让人们从中看出经济的发展形势。例如在经济学的宏观控制和价格控制中，都有数学建模的融入，利用数学建模可以有助于经济学实验的宏观经济分析，在一些实验和价格控制当中，都经常会涉及到数学问题在微观经济中数理统计的实验设计，这时候就体现出了数学建模对于经济学的促进性作用。下面笔者将会针对数学建模对于经济学的重要作用进行具体的分析。 1.数学经济模型对于经济学研究的重要性： 一般情况下，单独的依靠数学模型是不够解决所有的经济学问题，很多经济领域中的问题是需要从微观角度进行细致的分析才能够总结出其中的规律。要想利用数学知识来

解决经济学中所出现的问题，就一定要建立适当的经济学模型。运用数学建模来解决经济学中的问题并不是没有道理的，很多时候从经济学的角度仅仅能够知道问题的方向和目的，至于其中的过程并不能有着详细的分析，而利用数学模型就可以彻底的解决这一问题。数学建模可以通过自身在数字、图像以及框图等形式来更加真实地反映出现有经济的实际状况。 2.构建经济数学模型的一般步骤： 要想利用数学模型来更好的解决现有的经济学问题，主要分为两个步骤，第一先要分清楚问题发生的背景并且熟悉问题，然后要通过假设的形式来完善现有的经济学问题，通过抽象以及形象化的方式来构建一些合理的数学模型。运用数学知识和技巧来描述问题中变量参数之间的关系。这样可以得出一些有关经济类的数据，进而将建模中得到的数据与实际情况进行对比和分析，最终得出结果。 3.应用实例： 商品提价问题的数学模型： 3.1问题： 现如今经济学在很多的商场中都有所运用，例如同样的商品要想获得最大的经济效益，既要考虑到规定的售价，又要考虑到销售的数量，如果定价过低，则销售数量较多，如果定价较高，利润是大了，但是却影响了销售数量。怎样

TSP问题的遗传算法求解 优化设计小论文

TSP问题的遗传算法求解 摘要：遗传算法是模拟生物进化过程的一种新的全局优化搜索算法，本文简单介绍了遗传算法，并应用标准遗传算法对旅行包问题进行求解。 关键词：遗传算法、旅行包问题 一、旅行包问题描述： 旅行商问题，即TSP问题（Traveling Saleman Problem）是数学领域的一个著名问题，也称作货郎担问题，简单描述为：一个旅行商需要拜访n个城市（1，2，…，n），他必须选择所走的路径，每个城市只能拜访一次，最后回到原来出发的城市，使得所走的路径最短。其最早的描述是1759年欧拉研究的骑士周游问题，对于国际象棋棋盘中的64个方格，走访64个方格一次且最终返回起始点。 用图论解释为有一个图G=（V,E），其中V是顶点集，E是边集，设D=（d ij）是有顶点i和顶点j之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过所有顶点且每个顶点只能通过一次的具有最短距离的回路。若对于城市V={v1，v2，v3，...，vn}的一个访问顺序为T=(t1，t2，t3，…，ti，…，tn)，其中ti∈V(i=1，2，3，…，n)，且记tn+1= t1，则旅行商问题的数学模型为：min L=Σd(t(i),t(i+1)) （i=1，…，n） 旅行商问题是一个典型组合优化的问题，是一个NP难问题，其可能的路径数为（n-1）！，随着城市数目的增加，路径数急剧增加，对与小规模的旅行商问题，可以采取穷举法得到最优路径，但对于大型旅行商问题，则很难采用穷举法进行计算。 在生活中TSP有着广泛的应用，在交通方面，如何规划合理高效的道路交通，以减少拥堵；在物流方面，更好的规划物流，减少运营成本；在互联网中，如何设置节点，更好的让信息流动。许多实际工程问题属于大规模TSP，Korte于1988年提出的VLSI芯片加工问题可以对应于1.2e6的城市TSP，Bland于1989年提出X-ray衍射问题对应于14000城市TSP，Litke于1984年提出电路板设计中钻孔问题对应于17000城市TSP，以及Grotschel1991年提出的对应于442城市TSP的PCB442问题。

数学建模10种常用算法

数学建模10种常用算法 1、蒙特卡罗算法（该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟可以来检验自己模型的正确性，是比赛时必用的方法） 2、数据拟合、参数估计、插值等数据处理算法（比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用Matlab作为工具） 3、线性规划、整数规划、多元规划、二次规划等规划类问 题（建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo软件实现） 4、图论算法（这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备） 5、动态规划、回溯搜索、分治算法、分支定界等计算机算法（这些算法是算法设计中比较常用的方法，很多场合可以用到竞赛中） 6、最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法（这些问题是用来解决一些较困难的最优化问题的算法，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用） 7、网格算法和穷举法（网格算法和穷举法都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具） 8、一些连续离散化方法（很多问题都是实际来的，数据可以是连续的，而计算机只认的是离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的） 9、数值分析算法（如果在比赛中采用高级语言进行

编程的话，那一些数值分析中常用的算法比如方程组 求解、矩阵运算、函数积分等算法就需要额外编写库 函数进行调用） 10、图象处理算法（赛题中有一类问题与图形有关， 即使与图形无关，论文中也应该要不乏图片的，这些 图形如何展示以及如何处理就是需要解决的问题，通 常使用Matlab进行处 参数估计 C.F. 20世纪60年代,随着电子计算机的 。参数估计有多种方法，有最小二乘法、极大似然法、极大验后法、最小风险法和极小化极大熵法等。在一定条件下，后面三个方法都与极大似然法相同。最基本的方法是最小二乘法和极大似然法. 基本介绍 参数估计（parameter 尽可能接近的参数 误差 平方和　 θ,使已知数据Y 最大,这里P(Y│θ)是数据Y P(Y│θ)。在实践中这是困难的，一般可假设P（Y│θ

基于遗传算法的齿轮减速器优化设计

煤矿机械Coal Mine Machinery Vol.30No.12 Dec.2009 第30卷第12期2009年12月 0引言 工程机械中所用电动机的转速较高，为了满足工作机低转速的需要，一般在电动机和工作机之间安装减速器，用来降低电机的转速或增大转矩，减速器是一种机械传动装置，广泛地应用于运输机械、矿山机械和建筑机械等重型机械中。因此，减速器的设计非常重要。 遗传算法（GA）是模拟生物在自然界中优胜劣汰的自然进化过程而形成的一种具有全局范围内优化的启发式搜索算法。这种方法已在很多学科得到广泛的应用，为减速器的优化设计提供有力的保证。因此，本文采用遗传算法对两级齿轮减速器进行优化设计，并通过与惩罚函数法和模拟退火算法等优化方法计算结果进行比较，来探讨适合于减速器的优化设计方法。 1建立数学模型 两级齿轮传动减速器结构如图1所示。该减速器的总中心距 a∑＝［m n1z1（1＋i1）+m n2z3（1＋i2）］/2cosβ（1）式中m n1、m n2—— —高速级与低速级的齿轮法面模 数； i1、i2—— —高速级与低速级传动比； z1、z3—— —高速级与低速级的小齿轮齿数： β—— —2组齿轮组的螺旋角。 1.1设计变量的确定 在进行两级齿轮传动减速器设计时，一般选择齿轮传动独立的基本参数或性能参数，如齿轮的齿数、模数、传动比、螺旋角等为设计变量。两级齿轮传动由4个齿轮组成，分别用z1、z2、z3、z4表示，高速级的传动比由i1表示，低速级传动比由i2表示，两组齿轮组的法面模数分别由m n1和m n2表示，2组齿轮的螺旋角用β表示，由于两级齿轮传动减速器的总传动比i0，在设计时会给出具体数据，并且满足i0＝i1i2，可以得出i2＝i0/i1，可以确定独立的参数有z1、z3、m n1、m n2、i1和β。因此，可以确定该设计变量X＝［z1，z3，m n1，m n2，i1，β］T=［x1，x2，x3，x4，x5，x6］T。 图1减速器结构简图 1.2目标函数的建立 在对减速器进行优化设计时，首先要确定目标函数。确定目标函数的原则是在满足各种性能要求的前提下，使减速器的体积最小，这样设计的减速器既经济又实用，从而达到了优化的目的。要使减速器的体积最小，必须使减速器的总中心距最小。因此，以减速器的中心距最小建立目标函数为 a∑＝［x3x1（1＋x5）+x4x2(1+i0/x5)］ 6 （2）1.3约束条件的确定 为使两级齿轮传动减速器满足强度、设计变量 基于遗传算法的齿轮减速器优化设计* 吴婷，张礼兵，黄磊 （安徽建筑工业学院机电学院，合肥230601） 摘要：对两级齿轮减速器优化设计进行了分析，建立了其优化设计的数学模型，确定了优化设计的约束条件，采用遗传算法对两级齿轮减速器进行优化设计，并通过实例说明，采用遗传算法对减速器进行优化，可以得到更加优化的设计结果。 关键词：减速器；遗传算法；优化设计 中图分类号：TH132文献标志码：A文章编号：1003－0794（2009）12－0009－03 Gear Reducer Optimal Design Based on Genetic Algorithm WU Ting，ZHANG Li-bing，HUANG Lei （School of Mechanical and Electrical Engineering,Anhui University of Architecture,Hefei230601,China）Abstract:T he optimal design of a gear reducer was analyzed,the mathematic model was established, and the restriction condition was confirmed.Design of the gear reducer was optimized with genetic algorithm and the examples showed that design of the gear reducer based on genetic algorithm can gain more optimized result. Key words:reducer；genetic algorithm；optimal design *安徽省教育厅自然基金项目（2006KJ015C） 轴1轴2轴3 z1z2 z3z4 9

数学建模中常见的十大模型讲课稿

数学建模中常见的十 大模型

精品文档 数学建模常用的十大算法==转 (2011-07-24 16:13:14) 转载▼ 1. 蒙特卡罗算法。该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟来检验自己模型的正确性，几乎是比赛时必用的方法。 2. 数据拟合、参数估计、插值等数据处理算法。比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用MA TLAB 作为工具。 3. 线性规划、整数规划、多元规划、二次规划等规划类算法。建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo 软件求解。 4. 图论算法。这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备。 5. 动态规划、回溯搜索、分治算法、分支定界等计算机算法。这些算法是算法设计中比较常用的方法，竞赛中很多场合会用到。 6. 最优化理论的三大非经典算法：模拟退火算法、神经网络算法、遗传算法。这些问题是用来解决一些较困难的最优化问题的，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用。 7. 网格算法和穷举法。两者都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具。 8. 一些连续数据离散化方法。很多问题都是实际来的，数据可以是连续的，而计算机只能处理离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的。 9. 数值分析算法。如果在比赛中采用高级语言进行编程的话，那些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用。 10. 图象处理算法。赛题中有一类问题与图形有关，即使问题与图形无关，论文中也会需要图片来说明问题，这些图形如何展示以及如何处理就是需要解决的问题，通常使用MATLAB 进行处理。 以下将结合历年的竞赛题，对这十类算法进行详细地说明。 以下将结合历年的竞赛题，对这十类算法进行详细地说明。 2 十类算法的详细说明 2.1 蒙特卡罗算法 大多数建模赛题中都离不开计算机仿真，随机性模拟是非常常见的算法之一。 举个例子就是97 年的A 题，每个零件都有自己的标定值，也都有自己的容差等级，而求解最优的组合方案将要面对着的是一个极其复杂的公式和108 种容差选取方案，根本不可能去求解析解，那如何去找到最优的方案呢？随机性模拟搜索最优方案就是其中的一种方法，在每个零件可行的区间中按照正态分布随机的选取一个标定值和选取一个容差值作为一种方案，然后通过蒙特卡罗算法仿真出大量的方案，从中选取一个最佳的。另一个例子就是去年的彩票第二问，要求设计一种更好的方案，首先方案的优劣取决于很多复杂的因素，同样不可能刻画出一个模型进行求解，只能靠随机仿真模拟。 2.2 数据拟合、参数估计、插值等算法 数据拟合在很多赛题中有应用，与图形处理有关的问题很多与拟合有关系，一个例子就是98 年美国赛A 题，生物组织切片的三维插值处理，94 年A 题逢山开路，山体海拔高度的 收集于网络，如有侵权请联系管理员删除

数学建模背景

数学建模背景： 数学技术 近半个多世纪以来，随着计算机技术的迅速发展，数学的应用不仅在工程技术、自然科学等领域发挥着越来越重要的作用，而且以空前的广度和深度向经济、管理、金融、生物、医学、环境、地质、人口、交通等新的领域渗透，所谓数学技术已经成为当代高新技术的重要组成部分。 数学模型（Mathematical Model）是一种模拟，是用数学符号、数学式子、程序、图形等对实际课题本质属性的抽象而又简洁的刻划，它或能解释某些客观现象，或能预测未来的发展规律，或能为控制某一现象的发展提供某种意义下的最优策略或较好策略。数学模型一般并非现实问题的直接翻版，它的建立常常既需要人们对现实问题深入细微的观察和分析，又需要人们灵活巧妙地利用各种数学知识。这种应用知识从实际课题中抽象、提炼出数学模型的过程就称为数学建模（Mathematical Modeling）。[1] 不论是用数学方法在科技和生产领域解决哪类实际问题，还是与其它学科相结合形成交叉学科，首要的和关键的一步是建立研究对象的数学模型，并加以计算求解（通常借助计算机）。数学建模和计算机技术在知识经济时代的作用可谓是如虎添翼。 建模应用 数学是研究现实世界数量关系和空间形式的科学，在它产生和发展的历史长河中，一直是和各种各样的应用问题紧密相关的。数学的特点不仅在于概念的抽象性、逻辑的严密性，结论的明确性和体系的完整性，而且在于它应用的广泛性，自从20世纪以来，随着科学技术的迅速发展和计算机的日益普及，人们对各种问题的要求越来越精确，使得数学的应用越来越广泛和深入，特别是在21世纪这个知识经济时代，数学科学的地位会发生巨大的变化，它正在从国家经济和科技的后备走到了前沿。经济发展的全球化、计算机的迅猛发展，数理论与方法的不断扩充使得数学已经成为当代高科技的一个重要组成部分和思想库，数学已经成为一种能够普遍实施的技术。培养学生应用数学的意识和能力已经成为数学教学的一个重要方面。 2建模过程 模型准备 了解问题的实际背景，明确其实际意义，掌握对象的各种信息。以数学思想来包容问题的精髓，数学思路贯穿问题的全过程，进而用数学语言来描述问题。要求符合数学理论，符合数学习惯，清晰准确。 模型假设 根据实际对象的特征和建模的目的，对问题进行必要的简化，并用精确的语言提出一些恰当的假设。 模型建立 在假设的基础上，利用适当的数学工具来刻划各变量常量之间的数学关系，建立相应的数学结构（尽量用简单的数学工具）。 模型求解 利用获取的数据资料，对模型的所有参数做出计算（或近似计算）。 模型分析 对所要建立模型的思路进行阐述，对所得的结果进行数学上的分析。 模型检验 将模型分析结果与实际情形进行比较，以此来验证模型的准确性、合理性和适用性。如果模型与实际较吻合，则要对计算结果给出其实际含义，并进行解释。如果模型与实际吻合较差，则应该修改假设，再次重复建模过程。

从诺贝尔经济学奖看数学建模的价值

第23卷第1期大　学　数　学Vol.23,№.1 2007年2月COLL EGE MA T H EMA TICS Feb.2007从诺贝尔经济学奖看数学建模的价值 韩　明 (福建工程学院数理系,福州350014) [摘　要]分为三个部分,第一部分,诺贝尔经济学奖的概述;第二部分,数学建模在经济学中的应用情 况;最后一部分,展望经济科学的发展趋势. [关键词]诺贝尔奖;数学建模;经济学 [中图分类号]F224;O213 [文献标识码]C [文章编号]167221454(2007)0120181206 1　诺贝尔经济学奖的概述 1968年瑞典银行为庆祝建行300周年,决定从1969年起同样以诺贝尔的名义,颁发经济学奖.这一奖项的全称是:“瑞典银行为纪念阿尔弗雷德?诺贝尔的经济科学奖(The Central Bank of Sweden Prize of Nobel in Economic Sciences in Memory of Alfred Nobel)”.除了奖金来源不同外,诺贝尔经济学奖的整个程序与其他诺贝尔奖完全相同. 获得当今世界上最具影响力的经济学奖项———诺贝尔经济学奖,几乎是每个经济学家的梦想.诺贝尔经济学奖从1969年第一次颁奖到2004年,已经有55人获此殊荣(同时获奖的人数最多不超过3人).1969年首届授予计量经济学的奠基人Regnar Frisch(挪威,1895-1979)和J an Tinbergen(荷兰, 1903-1994). 正如著名经济学家、后来的瑞典皇家科学院院长Erik L undberg在首届颁奖仪式上的讲话所说:“过去四十年中,经济科学在经济行为的数学规范化和统计定量化的方向上已经越来越发展.沿着这样的路线的科学分析,通常用来解释诸如经济增长、商情周期波动以及为各种目的来对经济资源重新配置那样的复杂经济现象…….然而,经济学家对有关战略性的经济关系构造数学模型的企图,以至借助于时间序列的统计分析来定量地阐明它们,事实上已经被证实是成功的.经济研究的这条路线,也就是数理经济学和计量经济学,已经在最近几十年里刻画了这一宗旨的发展.……”“近二十年来,Frisch教授和Tinbergen教授正在沿着本质上是同样的路线在进行研究.他们的目的是对经济理论赋予数学上的严谨性,并使它具有允许经验定量和统计假设检验的形式.其本质目标之一是要使经济学摆脱模糊的、较为‘文学’的类型.例如在Frischt和Tinbergen的著作中,商情周期波动的原因的任意‘命名’已经被抛弃,代之以陈述经济变量之间相互关系的数学系统.”从Erik L undberg的这段讲话,我们能看出经济科学在1969年前四十年的发展概况. 我们从经济科学的发展概况中,似乎能感觉到数学所起的作用.那么诺贝尔经济学奖得主的工作中数学建模起什么作用呢?它对开展大学生数学建模竞赛活动和我国大学数学教育又有什么启发呢? 2　数学建模在经济学中的应用情况 本文简要地介绍诺贝尔经济学奖得主的主要工作,从中我们能看到数学建模的应用情况和数学建 　[收稿日期]2005208210 　[基金项目]福建工程学院教育科学基金项目(G B-06-20)

遗传算法电机优化设计简介

收稿日期:20001225 综 述 遗传算法电机优化设计简介 李鲲鹏,胡虔生 (东南大学,南京210096) B rief I ntroduction of Motor Optimizing Design B ased on G enetic Algorithms L I Kun -peng ,HU Qian -sheng (S outheast University ,Nanjing 210096,China ) 摘　要:介绍了遗传算法的基本思想及其特点,实现了基于遗传算法的电机优化设计,讨论了保证其全局收敛性的方法,最后给出了基于遗传算法的电机优化设计实例。 关键词:电机优化设计;遗传算法;全局收敛性中图分类号:T M302 文献标识码:A 文章编号:1004-7018(2001)04-0032-02 Abstract :In this paper ,the essence and a pplications of genetic alg orithms are friendly introduced.Based on com paris ons between ge 2netic alg orithms and conventional methods ,the a pplication of genetic alg orithm to motor design is im plemented.In this process ,the meth 2ods to improve the global convergence of genetic alg orithm are dis 2cussed.Finally ,the results of the optimization of three -phase electri 2cal machine design based on genetic alg orithms are presented. K eyw ords :motor optimal design ;genetic alg orithms (G A );glob 2al convergence 1遗传算法的基本思想及其特点 遗传算法是模拟生物进化机制的一种现代优化计算方法。其基本思想是:首先通过编码操作将问题空间映射到编码空间(如[0,1]L ),然后在编码空间内进行选择、交叉、变异三种遗传操作及其循环迭代操作,模拟生物遗传进化机制,搜索编码空间的最优解,最后逆映射到原问题空间,从而得到原问题的最优解。选择操作模拟了个体之间和个体与环境之间的生存竞争,优良个体有更多的生存繁殖机会。在这种选择压力作用下,个体之间通过交叉、变异遗传操作进行基因重组,期望得到更优秀的后代个体,在这场竞争中胜出。选择、交叉、变异遗传操作都是以概率值进行的。这些概率值与当时生存环境和个体适应能力密切相关。从这里可以看出遗传算法是一种随机性搜索算法,但是它不同于传统的随机搜索算法。遗传算法通过交叉算子(Cross over operator )和变异算子(Mutation Operator )的协同作用确保状态空间([0,1]L )各点的概 率可达性,在选择算子(Selection Operator )的作用下保证迭代进程的方向性。 2电机优化设计的数学模型和一般优化方法 电机优化设计的一般数学模型: min/max :f (x ) g i (X )≤0,i =1,2,3,…,m X j ∈[a j ,b j ],j =1,2,3,…,n (1) 其中:X =[x 1,x 2,x 3,…,x n ]为设计参量即电磁系统的参数,如冲片尺寸、绕组参量等。g i (X )(i =1,2,3,…,m )为约束条件,如性能约束和一般约束。由于目标函数f (X )和约束条件g i (X )都是X 的高度非线性函数,因此电机优化设计问题是求解约束非线性最优化问题。 由于电机设计的目标函数f (X )不是一个单纯的数学表达式,而是一段电机设计分析计算程序,在计算目标函数值的同时还计算各个性能指标值,即约束条件函数值,因此利用目标函数的梯度确定搜索方向的优化方法在电机优化设计中是相当繁琐,直接利用目标函数值的优化方法在电机优化设计中具有优势,遗传算法通过选择、交叉、变异算子的协同作用,既保证了搜索的方向性,又满足了状态空间各点的概率可达性,具有概率意义下的全局收敛性。遗传算法继承了传统确定性算法和一般随机算法的优点,是一种新的启发式随机搜索算法。 遗传算法对约束的处理有两种思路:增加修正算子将约束条件反映在遗传算子的设计中;利用惩罚函数法将有约束优化问题转化为无约束优化问题。在电机优化设计中常采取后者。基于遗传算法的惩罚函数主要分为静态惩罚函数、动态惩罚函数和自适应惩罚函数三种[4]。自适应惩罚函数法效果较好,但较复杂; 静态、动态惩罚函数相对较简单,经常使用。约束条件 23 微特电机　2001年第4期

浅论数学建模在经济学中的应用

浅论数学建模在经济学中的应用 摘要：当代西方经济认为,经济学的基本方法是分析 经济变量之间的函数关系,建立经济模型,从中引申出经济原则和理论进行决策和预测。 关键词:经济学数学模型应用 在经济决策科学化、定量化呼声日渐高涨的今天,数学经济建模更是无处不在。如生产厂家可根据客户提出的产品数量、质量、交货期、交货方式、交货地点等要求,根据快速报价系统(根据厂家各种资源、产品工艺流程、生产成本及客户需求等数据进行数学经济建模)与客户进行商业谈判。 一、数学经济模型及其重要性 数学经济模型可以按变量的性质分成两类,即概率型和确定型。概率型的模型处理具有随机性情况的模型,确定型的模型则能基于一定的假设和法则,精确地对一种特定情况的结果做出判断。由于数学分支很多,加之相互交叉渗透,又派生出许多分支,所以一个给定的经济问题有时能用一种以上的数学方法去对它进行描述和解释。具体建立什么类型的模型,既要视问题而定,又要因人而异。要看自己比较熟悉精通哪门学科,充分发挥自己的特长。 数学并不能直接处理经济领域的客观情况。为了能用数学解决经济领域中的问题,就必须建立数学模型。数学建模是为了解决经济领域中的问题而作的一个抽象的、简化的结构的数学刻划。或者说,数学经济建模就是为了经济目的,用字母、数字及其他数学符号建立起

来的等式或不等式以及图表、图象、框图等描述客观事物的特征及其内在联系的数学结构的刻划。而现代世界发展史证实其经济发展速度与数学经济建模的密切关系。数学经济建模促进经济学的发展;带来了现实的生产效率。在经济决策科学化、定量化呼声日渐高涨的今天,数学经济建模更是无处不在。如生产厂家可根据客户提出的产品数量、质量、交货期、交货方式、交货地点等要求,根据快速报价系统与客户进行商业谈判。 二、构建经济数学模型的一般步骤 1.了解熟悉实际问题,以及与问题有关的背景知识。 2.通过假设把所要研究的实际问题简化、抽象,明确模型中诸多的影响因素,用数量和参数来表示这些因素。运用数学知识和技巧来描述问题中变量参数之问的关系。一般情况下用数学表达式来表示,构架出一个初步的数学模型。然后,再通过不断地调整假设使建立的模型尽可能地接近实际,从而得到比较满意的结论。 3.使用已知数据,观测数据或者实际问题的有关背景知识对所建模型中的参数给出估计值。 4.运行所得到的模型。把模型的结果与实际观测进行分析比较。如果模型结果与实际情况基本一致,表明模型是符合实际问题的。我们可以将它用于对实际问题进一步的分析或者预测;如果模型的结果与实际观测不一致,不能将所得的模型应用于所研究的实际问题。此时需要回头检查模型的组建是否有问题。问题的假使是否恰当,是否忽略了不应该忽略的因