遗传算法及优化问题(重要_有代码)

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

一、问题背景与实验目的

遗传算法（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进制数：

21

212019102100()(2)'i i i b b b b b b x =?=?=∑

2）'x 对应的区间[1,2]-内的实数：

12)1(2'122---?

+-=x x

例如，一个二进制串a=<1>表示实数．

'x =(1)2=2288967

637197.0123

2288967122=-?

+-=x

二进制串<0000000000000000000000>，<1>，则分别表示区间的两个端点值-1和2．

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

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

<001000010>， %% a2 <000000000>， %% a3

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

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

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

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

min min (), ()0

()0,f x F f x F 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 ，

则其入选概率为

1

()

(),1,2,3,,()

i s i n

i

i g a P a i n 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），具体内容将在后面给出介绍．

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

newpop(1)={

<0>， %% a1

<001000010>， %% a2

<001000010>， %% a2

<0>} %% a4

（5）交叉

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

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

<0 >， <001000010>

交叉得：

<0 >， <0>

<0 01000010>， <0>

交叉得：

<0 >， <001000010>

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

jchpop(1)={

<001000010>，

<0>，

<0>，

<001000010>}

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

（6）变异

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

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

pop(2)= {

<001000010>，

<0>，

<0>，

<001000010> }

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

（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

f x x x

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

()3

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时，Max () 1.5000

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

我们也可以编制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

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

()41

f x x x

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

五、附录

附录1：主程序

function

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

Population=PopulationInitialize(MumberLength,MemberNumber);

global Count;

global CurrentBest;

Count=1;

PopulationCode=Population;

PopulationFitness=Fitness(PopulationCode,FunctionFitness,MinX,Max X,MumberLength);

PopulationFitnessF=FitnessF(PopulationFitness,Fmin);

PopulationProbability=Probability(PopulationFitnessF);

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

EachMaxFitness(Count)=EachGenMaxFitness;

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

while Count

NewPopulation=Select(Population,PopulationProbability,MemberNumber);

Population=NewPopulation;

NewPopulation=Crossing(Population,FunctionFitness,MinX,MaxX,MumberLen gth);

Population=NewPopulation;

NewPopulation=Mutation(Population,MutationProbability);

Population=NewPopulation;

PopulationFitness=Fitness(Population,FunctionFitness,MinX,MaxX,Mumber Length);

PopulationFitnessF=FitnessF(PopulationFitness,Fmin);

PopulationProbability=Probability(PopulationFitnessF);

Count=Count+1;

[NewPopulation,CurrentBest,EachGenMaxFitness]=Elitist(Population,Popu lationFitness,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,M umberLength);

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

=-++）

f x x x

()20.5

(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));

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(PopulationD ata)));

【程序说明】子程序 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

【程序说明】子程序是用于计算每个染色体的适应函数值的．其输入参数如下：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,:);

【程序说明】子程序根据入选概率（计算累计概率）在群体中按比例选择部分染色体组成种群，该子程序的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

遗传算法与组合优化.

第四章 遗传算法与组合优化 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 问题等有着多方面的重要意义。

遗传算法在多目标优化的应用：公式,讨论,概述总括

遗传算法在多目标优化的应用：公式，讨论，概述/总括 概述 本文主要以适合度函数为基础的分配方法来阐述多目标遗传算法。传统的群落形成方法（niche formation method）在此也有适当的延伸,并提供了群落大小界定的理论根据。适合度分配方法可将外部决策者直接纳入问题研究范围，最终通过多目标遗传算法进行进一步总结：遗传算法在多目标优化圈中为是最优的解决方法，而且它还将决策者纳入在问题讨论范围内。适合度分配方法通过遗传算法和外部决策者的相互作用以找到问题最优的解决方案，并且详细解释遗传算法和外部决策者如何通过相互作用以得出最终结果。 1.简介 求非劣解集是多目标决策的基本手段。已有成熟的非劣解生成技术本质上都是以标量优化的手段通过多次计算得到非劣解集。目前遗传算法在多目标问题中的应用方法多数是根据决策偏好信息，先将多目标问题标量化处理为单目标问题后再以遗传算法求解，仍然没有脱离传统的多目标问题分步解决的方式。在没有偏好信息条件下直接使用遗传算法推求多目标非劣解的解集的研究尚不多见。 本文根据遗传算法每代均产生大量可行解和隐含的并行性这一特点，设计了一种基于排序的表现矩阵测度可行解对所有目标总体表现好坏的向量比较方法，并通过在个体适应度定标中引入该方法，控制优解替换和保持种群多样性，采用自适应变化的方式确定交叉和变异概率，设计了多目标遗传算法(Multi Objective Genetic Algorithm, MOGA)。该算法通过一次计算就可以得到问题的非劣解集， 简化了多目标问题的优化求解步骤。 多目标问题中在没有给出决策偏好信息的前提下，难以直接衡量解的优劣，这是遗传算法应用到多目标问题中的最大困难。根据遗传算法中每一代都有大量的可行解产生这一特点，我们考虑通过可行解之间相互比较淘汰劣解的办法来达到最 后对非劣解集的逼近。 考虑一个n维的多目标规划问题，且均为目标函数最大化， 其劣解可以定义为： f i (x * )≤f i (x t ) i=1，2，??，n (1) 且式(1)至少对一个i取“＜”。即至少劣于一个可行解的x必为劣解。 对于遗传算法中产生大量的可行解，我们考虑对同一代中的个体基于目标函数相互比较，淘汰掉确定的劣解，并以生成的新解予以替换。经过数量足够大的种群一定次数的进化计算，可以得到一个接近非劣解集前沿面的解集，在一定精度要求下，可以近似的将其作为非劣解集。 个体的适应度计算方法确定后，为保证能得到非劣解集，算法设计中必须处理好以下问题：(1)保持种群的多样性及进化方向的控制。算法需要求出的是一组不同的非劣解，所以计算中要防止种群收敛到某一个解。与一般遗传算法进化到

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

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

多目标遗传算法代码

. % function nsga_2(pro) %% Main Function % Main program to run the NSGA-II MOEA. % Read the corresponding documentation to learn more about multiobjective % optimization using evolutionary algorithms. % initialize_variables has two arguments; First being the population size % and the second the problem number. '1' corresponds to MOP1 and '2' % corresponds to MOP2. %inp_para_definition=input_parameters_definition; %% Initialize the variables % Declare the variables and initialize their values % pop - population % gen - generations % pro - problem number %clear;clc;tic; pop = 100; % 每一代的种群数 gen = 100; % 总共的代数 pro = 2; % 问题选择1或者2，见switch switch pro case 1 % M is the number of objectives. M = 2; % V is the number of decision variables. In this case it is % difficult to visualize the decision variables space while the % objective space is just two dimensional. V = 6; case 2 M = 3; V = 12; case 3 % case 1和case 2 用来对整个算法进行常规验证，作为调试之用；case 3 为本工程所需； M = 2; %(output parameters 个数) V = 8; %(input parameters 个数) K = 10; end % Initialize the population chromosome = initialize_variables(pop,pro); %% Sort the initialized population % Sort the population using non-domination-sort. This returns two columns % for each individual which are the rank and the crowding distance

遗传算法在多目标优化中的作用 调研报告

遗传算法在多目标优化中的作用调研报告 姓名: 学院: 班级: 学号: 完成时间:20 年月日 目录 1 .课题分析................................................................................................................................ 0 2 .检索策略................................................................................................................................ 0 2.1 检索工具的选择................................................................................................................................ ......... 0 2.2 检索词的选择................................................................................................................................ ............. 0 2.3 通用检索式................................................................................................................................ .. 0 3.检索步骤及检索结果 0 3.1 维普中文科技期刊数据库 0 3.2 中国国家知识产权局数据

基于遗传算法的库位优化问题

Logistics Sci-Tech 2010.5 收稿日期：2010－02－07 作者简介：周兴建（1979-），男，湖北黄冈人，武汉科技学院经济管理学院，讲师，武汉理工大学交通学院博士研究生，研究方向：物流价值链、物流系统规划；刘元奇（1988-），男，甘肃天水人，武汉科技学院经济管理学院；李泉（1989-），男，湖北 武汉人，武汉科技学院经济管理学院。 文章编号：1002-3100(2010)05-0038-03 物流科技2010年第5期Logistics Sci-Tech No.5,2010 摘 要：应用遗传算法对邯运集团仓库库位进行优化。在充分考虑邯运集团仓库所存放的货物种类、货物数量、出入库频 率等因素的基础上进行库位预分区规划，建立了二次指派问题的数学模型。利用遗传算法对其求解，结合MATLAB 进行编程计算并得出最优划分方案。 关键词：遗传算法；预分区规划；库位优化中图分类号：F253.4 文献标识码：A Abstract:The paper optimize the storage position in warehouse of Hanyun Group based on genetic algorithm.With thinking of the factors such as goods categories,quantities and frequencies of I/O,etc,firstly,the storage district is planned.Then the model of quadratic assignment problems is build,and genetic algorithm is utilized to resolve the problem.The software MATLAB is used to program and figure out the best alternatives. Key words:genetic algorithm;district planning;storage position optimization 1 库位优化的提出 邯郸交通运输集团有限公司（简称“邯运集团”）是一家集多种业务为一体的大型综合性物流企业。邯运集团的主要业务板块有原料采购（天信运业及天昊、天诚、天恒等）、快递服务（飞马快运）、汽贸业务（天诚汽贸）及仓储配送（河北快运）等。其中，邯运集团的仓储配送业务由河北快运经营，现有仓库面积总共40000㎡，主要的业务范围为医药、日用百货、卷烟、陶瓷、化工产品的配送，其中以医药为主。邯运集团库存货物主要涉及两个方面：一个是大宗的供应商货物，如医药，化工产品等；另一方面主要是大规模的小件快递货物，如日用百货等[1]。经分析，邯运集团在仓储运作方面存在如下问题： （1）存储货物繁多而分拣速度低下。仓库每天到货近400箱，有近200多种规格，缺乏一套行之有效的仓储管理系统。（2）货架高度不当而货位分配混乱。现在采用的货架高度在2米以上，而且将整箱货物直接码垛在货架上，不严格按货位摆放。当需要往货架最上层码放货物需要借助梯子，增加操作难度且操作效率较低。货物在拣货区货架摆放是以件为单位的，分拣和搬运速度较慢。 （3）拣货货架设计不当而仓储效率低下。发货前装箱工作主要由人工协同完成，出库效率低，出错率难以控制。 （4）存储能力和分拣能力不能满足需求。根据邯运集团的业务发展现状及趋势，现有的仓库储存和分拣能力远远达不到集团公司对配送业务量的需求。 当前邯运集团的货位分配主要采用物理地址编码的方式，很少考虑货位分配对仓储管理员工作效率的影响。对其进行库位优化设计不仅直接影响到其库存量的大小、出入库的效率，还间接影响到邯运集团的整体经营效益。本文对邯运集团的仓库货位进行优化时，结合考虑仓库所存放的货物种类、货物数量、出入库频率等因素，对仓库货位进行规划，以提高仓储效率。 2库位预分区规划 在进行仓库货位规划时，作如下假设： （1）货物的存放种类已知； （2）货物每种类的单位时间内存放的数量己知； （3） 每一种货物的存取频率已知。 在仓库货位优化中一个重要的环节即预分区。所谓预分区，是指没有存放货物时的分区，分区时只考虑仓储作业人员的速基于遗传算法的库位优化问题 Optimization of Storage Position in Warehouse Based on Genetic Algorithm 周兴建1,2，刘元奇1，李泉1 ZHOU Xing-jian 1,2,LIU Yuan-qi 1,LI Quan 1 （1.武汉科技学院经济管理学院，湖北武汉430073；2.武汉理工大学交通学院，湖北武汉430063） (1.College of Economics &Management,Wuhan University of Science &Engineering,Wuhan 430073,China; 2.School of Transportation,Wuhan University of Technology,Wuhan 430063,China) !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 38

遗传算法多目标函数优化

多目标遗传算法优化 铣削正交试验结果 说明： 1.建立切削力和表面粗糙度模型 如： 3.190.08360.8250.5640.45410c e p z F v f a a -=（1） a R =此模型你们来拟合（上面有实验数据，剩下的两个方程已经是我帮你们拟合好的了）（2） R a =10?0.92146v c 0.14365f z 0.16065a e 0.047691a p 0.38457 10002/c z p e Q v f a a D π=-????（3） 变量约束范围：401000.020.080.25 1.0210c z e p v f a a ≤≤??≤≤??≤≤? ?≤≤? 公式（1）和（2）值越小越好，公式（3）值越大越好。π=3.14 D=8 2.请将多目标优化操作过程录像（同时考虑三个方程，优化出最优的自变量数值），方便我后续进行修改；将能保存的所有图片及源文件发给我；将最优解多组发给我，类似于下图（黄色部分为达到的要求）

遗传算法的结果:

程序如下: clear; clc; % 遗传算法直接求解多目标优化 D=8; % Function handle to the fitness function F=@(X)[10^(3.19)*(X(1).^(-0.0836)).*(X(2).^0.825).*(X(3).^0.564).*(X(4).^0. 454)]; Ra=@(X)[10^(-0.92146)*(X(1).^0.14365).*(X(2).^0.16065).*(X(3).^0.047691).*( X(4).^0.38457)]; Q=@(X)[-1000*2*X(1).*X(2).*X(3).*X(4)/(pi*D)];

遗传算法程序代码--多目标优化--函数最值问题

函数最值问题：F=X2+Y2-Z2, clear clc %%初始化 pc=0.9; %交叉概率 pm=0.05; %变异概率 popsize=500; chromlength1=21; chromlength2=23; chromlength3=20; chromlength=chromlength1+chromlength2+chromlength3; pop=initpop(popsize,chromlength);% 产生初始种群 for i=1:500 [objvalue]=calobjvalue(pop); %计算目标函数值 [fitvalue]=calfitvalue(objvalue);%计算个体适应度 [newpop]=selection(pop,fitvalue);%选择 [newpop1]=crossover(newpop,pc) ; %交叉 [newpop2]=mutation(newpop1,pm) ;%变异 [newobjvalue]=newcalobjvalue(newpop2); %计算最新代目标函数值 [newfitvalue]=newcalfitvalue(newobjvalue); % 计算新种群适应度值[bestindividual,bestfit]=best(newpop2,newfitvalue); %求出群体中适应值最大的个体及其适应值 y(i)=max(bestfit); %储存最优个体适应值 pop5=bestindividual; %储存最优个体 n(i)=i; %记录最优代位置 %解码 x1(i)=0+decodechrom(pop5,1,21)*2/(pow2(21)-1); x2(i)=decodechrom(pop5,22,23)*6/(pow2(23)-1)-1; x3(i)=decodechrom(pop5,45,20)*1/(pow2(20)-1); pop=newpop2; end %%绘图 figure(1)%最优点变化趋势图 i=1:500; plot(y(i),'-b*') xlabel('迭代次数'); ylabel('最优个体适应值'); title('最优点变化趋势'); legend('最优点');

遗传算法及其在TSP问题中的应用

遗传算法及其在TSP问题中的应用 摘要：本文首先介绍了遗传算法的基本理论与方法，从应用的角度对遗传算法做了认真的分析和研究，总结了用遗传算法提出求解组合优化问题中的典型问题——TSP问题的最优近似解的算法。其次，本文在深入分析和研究了遗传算法基本理论与方法的基础上，针对旅行商问题的具体问题，设计了基于TSP的遗传算法的选择、交叉和变异算子等遗传算子，提出了求解旅行商问题的一种遗传算法，并用Matlab语言编程实现其算法，最后绘出算法的仿真结果，并对不同结果作出相应的分析。然后，本文还针对遗传算法求解TSP时存在的一些问题对该算法进行了适当的改进。如针对初始群体、遗传算子作出适当改进，或者将遗传算法与其他方法相结合，以及在编程过程中对算法流程的改进。本人在用计算机模拟遗传算法求解TSP问题时，首先分析了用Matlab语言设计遗传算法程序的优越性，接着以遗传算法求解TSP问题为例，深入讨论了各个遗传算子的程序实现，并通过分析实验数据，得到各个遗传算子在搜索寻优过程中所起的作用，最后指出了用Matlab语言编程同用其它高级程序语言编程的差异所在，以及运用Matlab编写遗传算法程序的一些注意事项。最后，本文提出将遗传算法与其它算法相结合来求解一般问题的想法；并将遗传算法的应用范围扩展，提出可以运用遗传算法求解由TSP衍生出的各类TSP扩展问题，如求解配送/收集旅行商问题的遗传算法（TSPD）、遗传算法在货物配送问题中的应用（ST－TSP）、多旅行商问题（MTSP）等。 引言：优化问题可以自然地分为两类：一类是连续变量的优化问题；另一类是离散变量的优化问题，即所谓组合优化问题。对于连续变量的优化问题，一般是求一组实数或一个函数；而在组合优化问题中，一般是从一个无限集或有限的几个无限集中寻找一个对象——它可以是一个整数，一个集合，一个排列或者一个图，也即是从可行解中求出最优解的问题。TSP问题就是其中的典型例子，就本质上而言它可抽象为数学上的组合优化，它描述的是旅行商经N个城市的最短路径问题，因而对TSP问题的求解是数学上，同时也是优化问题中普遍关注的。旅行商问题（Traveling Salesman Problem，简称TSP）也称为货担郎问题，是一个较古的问题，最早可以追溯到1759年Euler提出的骑士旅行问题[9]。旅行商问题可以解释为，一位推销员从自己所在城市出发，必须邀访所有城市且每个城市只能访问一次之后又返回到原来的城市，求使其旅行费用最小（和旅行距离最短）的路径。 TSP是一个典型的组合优化问题，并且是一个NP难题，所以一般很难精确地求出其最优解，因而寻找出其有效的近似求解算法就具有重要的理论意义。另一方面，很多实际应用问题，如公安执勤人员的最优巡回路线、流水作业生产线的顺序问题、车辆调度问题、网络问题、切割问题以至机组人员的轮班安排、教师任课班级负荷分配等问题，经过简化处理后，都可建模为TSP问题，因而对旅行商问题求解方法的研究也具有重要的应用价值。再者，在各种遗传算法应用实例中，其个体编码方法大多都是采用二进制编码方法或浮点数编码方法，而TSP问题是一种典型的需要使用符号编码方法的实际问题，所以，研究求解TSP问题的遗传算法，对促进遗传算法本身的发展也具有重要意义。在过去的20年里，在求解旅行商问题的最优解方面取得了极大的进展。尽管有这些成就，但旅行商问题还远未解决，问题的许多方面还要研究，很多问题还在期待满意的回答。 另外，遗传算法就其本质来说，主要是解决复杂问题的一种鲁棒性强的启发式随机

多目标遗传算法中文【精品毕业设计】(完整版)

一种在复杂网络中发现社区的多目标遗传算法 Clara Pizzuti 摘要——本文提出了一种揭示复杂网络社区结构的多目标遗传算法。该算法优化了两个目标函数，这些函数能够识别出组内节点密集连接，而组间连接稀疏。该方法能产生一系列不同等级的网络社区，其中解的等级越高，由更多的社区组成，被包含在社区较少的解中。社区的数量是通过目标函数更佳的折衷值自动确定的。对合成和真实网络的实验，结果表明算法成功地检测到了网络结构，并且能与最先进的方法相比较。 关键词：复杂网络，多目标聚类，多目标进化算法 1、简介 复杂网络构成了表示组成许多真实世界系统的对象之间关系的有效形式。协作网络、因特网、万维网、生物网络、通信传输网络，社交网络只是一些例子。将网络建模为图，节点代表个体，边代表这些个体之间的联系。 复杂网络研究中的一个重要问题是社区结构[25]的检测，也被称作为聚类[21]，即将一个网络划分为节点组，称作社区或簇或模块，组内连接紧密，组间连接稀疏。这个问题，如[21]指出，只有在建模网络的图是稀疏的时候才有意义，即边的数量远低于可能的边数，否则就类似于数据簇[31]。图的聚类不同于数据聚类，因为图中的簇是基于边的密度，而在数据聚类中，它们是与距离或相似度量紧密相关的组点。然而，网络中社区的概念并未严格定义，因为它的定义受应用领域的影响。因此，直观的理解是同一社区内部边的数量应该远多于连接图中剩余节点的边的数量，这构成了社区定义的一般建议。这个直观定义追求两个不同的目标：最大化内部连接和最小化外部连接。 多目标优化是一种解决问题的技术，当多个相互冲突的目标被优化时，成功地找到一组解。通过利用帕累托最优理论[15]获得这些解，构成了尽可能满足所有目标的全局最优解。解决多目标优化问题的进化算法取得成功，是因为它们基于种群的特性，同时产生多个最优解和一个帕累托前沿[5]的优良近似。 因此，社区检测能够被表述为多目标优化问题，并且帕累托最优性的框架可以提供一组解对应于目标之间的最佳妥协以达到最优化。事实上，在上述两个目标之间有一个折衷，因为当整个网络社区结构的外部连接数量为空时，那它就是最小的，然而簇密度不够高。 在过去的几年里，已经提出了许多方法采用多目标技术进行数据聚类。这些方法大部分在度量空间[14], [17],[18], [28], [38], [39], [49], [51]聚集目标，虽然[8]中给出了分割图的一个方法，并且在[12]中描述了网络用户会议的一个图聚类算法。 本文中，一个多目标方法，名为用于网络的多目标遗传算法(MOGA-Net)，通过利用提出的遗传算法发现网络中的社区。该方法优化了[32]和[44]中介绍的两个目标函数，它们已被证实在检测复杂网络中模块的有效性。第一个目标函数利用了community score的概念来衡量对一个网络进行社区划分的质量。community score值越高，聚类密度越高。第二个目标函数定义了模块中节点fitness的概念，并且反复迭代找到节点fitness总和最大的模块，以下将这个目标函数称为community fitness。当总和达到最大时，外部连接是最小。两个目标函数都有一个正实数参数控制社区的规模。参数值越大，找到的社区规模越小。MOGA-Net利用这两个函数的优点，通过有选择地探索搜寻空间获得网络中存在的社区，而不需要提前知道确切的社区数目。这个数目是通过两个目标之间的最佳折衷自动确定的。 多目标方法的一个有趣结果是它提供的不是一个单独的网络划分，而是一组解。这些解中的每一个都对应两个目标之间不同的折衷，并对应多种网络划分方式，即由许多不同簇组成。对合成网络和真实网络的实验表明，这一系列帕累托最优解揭示了网络的分层结构，其中簇的数目较多的解包含在社区数目较少的解中。多目标方法的这个特性提供了一个很好的机会分析不同层级

多目标优化实例和matlab程序

NSGA-II 算法实例 目前的多目标优化算法有很多, Kalyanmoy Deb 的带精英策略的快速非支配排序遗传算法(NSGA-II) 无疑是其中应用最为广泛也是最为成功的一种。本文用的算法是MATLAB 自带的函数gamultiobj ，该函数是基于NSGA-II 改进的一种多目标优化算法。 一、 数值例子 多目标优化问题 424221********* 4224212212112 12min (,)10min (,)55..55 f x x x x x x x x x f x x x x x x x x x s t x =-++-=-++-≤≤??-≤≤? 二、 Matlab 文件 1． 适应值函数m 文件： function y=f(x) y(1)=x(1)^4-10*x(1)^2+x(1)*x(2)+x(2)^4-x(1)^2*x(2)^2; y(2)=x(2)^4-x(1)^2*x(2)^2+x(1)^4+x(1)*x(2); 2． 调用gamultiobj 函数，及参数设置： clear clc fitnessfcn=@f; %适应度函数句柄 nvars=2; %变量个数 lb=[-5,-5]; %下限 ub=[5,5]; %上限 A=[];b=[]; %线性不等式约束 Aeq=[];beq=[]; %线性等式约束 options=gaoptimset('paretoFraction',0.3,'populationsize',100,'generations', 200,'stallGenLimit',200,'TolFun',1e-100,'PlotFcns',@gaplotpareto); % 最优个体系数paretoFraction 为0.3；种群大小populationsize 为100，最大进化代数generations 为200， % 停止代数stallGenLimit 为200， 适应度函数偏差TolFun 设为1e-100，函数gaplotpareto ：绘制Pareto 前端 [x,fval]=gamultiobj(fitnessfcn,nvars,A,b,Aeq,beq,lb,ub,options)

遗传算法

遗传算法 开放分类：编程、程序、数学、计算机、算法 目录 ? 遗传算法定义 ? 遗传算法特点 ? 遗传算法的应用 ? 遗传算法的现状 ? 遗传算法的一般算法 ? 遗传算法实例 遗传算法定义 [编辑本段] 遗传算法（Genetic Algorithm）是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它是有美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著《Adaptation in Natural and Artificial Systems》，GA这个名称才逐渐为人所知，J.Hilland教授所提出的GA通常为简单遗传算法（SGA）。 遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小挑选（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。 遗传算法特点 [编辑本段] 遗传算法是一类可用于复杂系统优化的具有鲁棒性的搜索算法，与传统的优化算法相比，主要有以下特点：1、遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接决策变量的实际植本身，而遗传算法处理决策变量的某种编码形式，使得我们可以借鉴生物学中的染色体和基因的概念，可以模仿自然界生物的遗传和进化机理，也使得我们能够方便的应用遗传操作算子。 2、遗传算法直接以适应度作为搜索信息，无需导数等其它辅助信息。 3、遗传算法使用多个点的搜索信息，具有隐含并行性。 4、遗传算法使用概率搜索技术，而非确定性规则。 遗传算法的应用 [编辑本段] 由于遗传算法的整体搜索策略和优化搜索方法在计算是不依赖于梯度信息或其它辅助知识，而只需要影响

5遗传算法与组合优化

第五章 遗传算法与组合优化 5.1 背包问题（knapsack problem ） 5.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 满足 ,1 C 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 满足 ,1 C X S n i i i ≤∑= n i X i ≤≤∈1},1,0{ 背包问题在计算理论中属于NP —完全问题，其计算复杂度为O (2n )，若允许物件可以部分地装入背包，即允许X ，可取从0.00到1.00闭区间上的实数，则背包问题就简化为极简单的P 类问题，此时计算复杂度为O (n )。

多目标遗传算法代码

% function nsga_2(pro) %% Main Function % Main program to run the NSGA-II MOEA. % Read the corresponding documentation to learn more about multiobjective % optimization using evolutionary algorithms. % initialize_variables has two arguments; First being the population size % and the second the problem number. '1' corresponds to MOP1 and '2' % corresponds to MOP2. %inp_para_definition=input_parameters_definition; %% Initialize the variables % Declare the variables and initialize their values % pop - population % gen - generations % pro - problem number %clear;clc;tic; pop = 100; % 每一代的种群数 gen = 100; % 总共的代数 pro = 2; % 问题选择1或者2，见switch switch pro case 1 % M is the number of objectives. M = 2; % V is the number of decision variables. In this case it is % difficult to visualize the decision variables space while the % objective space is just two dimensional. V = 6; case 2 M = 3; V = 12; case 3 % case 1和case 2 用来对整个算法进行常规验证，作为调试之用；case 3 为本工程所需； M = 2; %(output parameters 个数) V = 8; %(input parameters 个数) K = 10; end % Initialize the population chromosome = initialize_variables(pop,pro); %% Sort the initialized population % Sort the population using non-domination-sort. This returns two columns % for each individual which are the rank and the crowding distance % corresponding to their position in the front they belong. 真是牛X了。 chromosome = non_domination_sort_mod(chromosome,pro); %% Start the evolution process

多目标规划遗传算法

%遗传算法解决多目标函数规划 clear clc syms x; %Function f1=f(x) f1=x(:,1).*x(:,1)/4+x(:,2).*x(:,2)/4; %function f2=f(x) f2=x(:,1).*(1-x(:,2))+10; NIND=100; MAXGEN=50; NV AR=2; PRECI=20; GGPA=0.9; trace1=[]; trace2=[]; trace3=[]; FielD=[rep([PRECI],[1,NV AR]);[1,1;4,2];rep([1;0;1;1],[NV AR])]; Chrom=crtbp(NIND,NV AR*PRECI); v=bs2rv(Chrom,FielD); gen=1; while gen

多变量多目标的遗传算法程序

这是我在解决电梯动力学参数写的简单遗传算法（程序带目标函数值、适应度值计算，但是我的适应度函数因为目标函数的计算很特殊，一起放在了程序外面计算,在此不提供）。 头文件： // CMVSOGA.h : main header file for the CMVSOGA.cpp // 本来想使用链表里面套链表的，程序调试比较麻烦，改为种群用链表表示 //染色体固定为16的方法。 #if !defined(AFX_CMVSOGA_H__45BECA_61EB_4A0E_9746_9A94D1CCF767_ _INCLUDED_) #define AFX_CMVSOGA_H__45BECA_61EB_4A0E_9746_9A94D1CCF767__INCLUDED _ #if _MSC_VER > 1000 #pragma once #endif // _MSC_VER > 1000 #include "Afxtempl.h" #define variablenum 16 class CMVSOGA { public: CMVSOGA(); void selectionoperator(); void crossoveroperator(); void mutationoperator(); void initialpopulation(int, int ,double ,double,double *,double *); //种群初始化 void generatenextpopulation(); //生成下一代种群 void evaluatepopulation(); //评价个体，求最佳个体 void calculateobjectvalue(); //计算目标函数值 void calculatefitnessvalue(); //计算适应度函数值 void findbestandworstindividual(); //寻找最佳个体和最差个体 void performevolution(); void GetResult(double *); void GetPopData(double **); void SetValueData(double *); void maxandexpectation(); private: struct individual { double chromosome[variablenum]; //染色体编码长度应该为变量的个数 double value; double fitness; //适应度 };