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

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

一、问题背景与实验目的

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

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

1．遗传算法的基本原理

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

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

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

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

（2）遗传算法的步骤

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

遗传算法基本步骤主要是：先把问题的解表示成“染色体”，在算法中也就是以二进制

编码的串，在执行遗传算法之前，给出一群“染色体”，也就是假设的可行解．然后，把这些假设的可行解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉、变异过程产生更适应环境的新一代“染色体”群．经过这样的一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解．

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

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

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

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

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

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

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

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

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

2．遗传算法的实际应用

例1：设2

f x x∈-．

()20.5

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

f x 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]-内的实数：

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

'x=(1000101110110101000111)2=2288967

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

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

首先我们来随机的产生一个个体数为4个的初始群体如下：

pop(1)={

<1101011101001100011110>， %% a1

<1000011001010001000010>， %% a2

<0001100111010110000000>， %% a3

<0110101001101110010101>} %% a4（Matlab程序参见附录2）

化成十进制的数分别为：

pop(1)={ 1.523032，0.574022 ，-0.697235 ，0.247238 }

接下来我们就要解决每个染色体个体的适应值问题了．

（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)]={ 1.226437 , 1.318543 , -1.380607 , 0.933350 }

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

取min 1F =-，

g[pop(1)]= { 2.226437 , 2.318543 , 0 , 1.933350 }

（3）确定选择标准

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

对于给定的规模为n 的群体pop={123,,,,n a a a a L }，个体i a 的适应值为()i g a ，则其入选概率为

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

首先可得 4

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

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

1()i i g a =∑，得：

P (a 1)=2.226437 / 6.478330 = 0.343675 %% a 1

P (a 2)=2.318543 / 6.478330 = 0.357892 %% a 2

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

P (a 4)=1.933350 / 6.478330 = 0.298433 %% a 4（Matlab 程序参见附录7）

（4）产生种群

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

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

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

newpop(1)={

<1101011101001100011110>， %% a1

<1000011001010001000010>， %% a2

<1000011001010001000010>， %% a2

<0110101001101110010101>} %% a4

（5）交叉

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

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

<110101110 1001100011110>， <1101011101010001000010>

交叉得：

<100001100 1010001000010>， <1000011001001100011110>

<10000110010100 01000010>， <1000011001010010010101>

交叉得：

<01101010011011 10010101>， <0110101001101101000010>

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

jchpop(1)={

<1101011101010001000010>，

<1000011001010010010101>，

<0110101001101101000010>}

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

（6）变异

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

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

pop(2)= {

<1101011101010001000010>，

<1000011001001100011110>，

<1000011011010010010101>，

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

（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∈，编码长度为5，采用上述定理4所

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

()3

f x x x

述的“在选择前保留当前最优解的遗传算法”进行．

此略，留作练习．

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

本实验的程序中用到如下一些基本的Matlab函数：ones, zeros, sum, size, length,

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

三、实验内容

上述例1的求解过程为：

群体中包含六个染色体，每个染色体用22位0—1码，变异概率为0.01，变量区间为-，取Fmin=2-，遗传代数为50代，则运用第一种终止条件（指定遗传代数）的Matlab [1,2]

程序为：

[Count,Result,BestMember]=Genetic1(22,6,'-x*x+2*x+0.5',-1,2,-2,0.01,50)执行结果为：

Count =

50

Result =

1.0316 1.0316 1.0316 1.0316 1.0316 1.0316

1.4990 1.4990 1.4990 1.4990 1.4990 1.4990

BestMember =

1.0316

1.4990

图2 例1的计算结果

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

而下图为目前为止的个体最大适应度——单调递增）

我们通过Matlab软件实现了遗传算法，得到了这题在第一种终止条件下的最优解：当

f x=．

x取1.0316时，Max () 1.4990

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

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

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

四、自己动手

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

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

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

13

Result =

1.0392 1.0392 1.0392 1.0392 1.0392 1.0392

1.4985 1.4985 1.4985 1.4985 1.4985 1.4985

BestMember =

1.0392

1.4985

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

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

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

4．附录9子程序 Crossing.m中的第8行至第13行的程序表明，当Dim(1)>=3时，将交换数组Population的最后两行，即交换最后面的两个个体．其目的是什么？

5．仿照附录10子程序Mutation.m，修改附录9子程序 Crossing.m，使得交叉过程也有一个概率值（一般取0.65~0.90）；同时适当修改主程序Genetic1.m或主程序Genetic2.m，以便代入交叉概率．

6．设2

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

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

()41

f x x x

五、附录

附录1：主程序Genetic1.m

function

[Count,Result,BestMember]=Genetic1(MumberLength,MemberNumber,FunctionFitness,M inX,MaxX,Fmin,MutationProbability,Gen)

Population=PopulationInitialize(MumberLength,MemberNumber);

global Count;

global CurrentBest;

Count=1;

PopulationCode=Population;

PopulationFitness=Fitness(PopulationCode,FunctionFitness,MinX,MaxX,MumberL ength);

PopulationFitnessF=FitnessF(PopulationFitness,Fmin);

PopulationProbability=Probability(PopulationFitnessF);

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

EachMaxFitness(Count)=EachGenMaxFitness;

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

while Count

使用遗传算法求解函数最大值

使用遗传算法求解函数最大值 题目 使用遗传算法求解函数 在及y的最大值。 解答 算法 使用遗传算法进行求解，篇末所附源代码中带有算法的详细注释。算法中涉及不同的参数，参数的取值需要根据实际情况进行设定，下面运行时将给出不同参数的结果对比。 定义整体算法的结束条件为，当种群进化次数达到maxGeneration时停止，此时种群中的最优解即作为算法的最终输出。 设种群规模为N，首先是随机产生N个个体，实验中定义了类型Chromosome表示一个个体，并且在默认构造函数中即进行了随机的操作。 然后程序进行若干次的迭代，在每次迭代过程中，进行选择、交叉及变异三个操作。 一选择操作 首先计算当前每个个体的适应度函数值，这里的适应度函数即为所要求的优化函数，然后归一化求得每个个体选中的概率，然后用轮盘赌的方法以允许重复的方式选择选择N个个体，即为选择之后的群体。

但实验时发现结果不好，经过仔细研究之后发现，这里在x、y取某些值的时候，目标函数计算出来的适应值可能会出现负值，这时如果按照把每个个体的适应值除以适应值的总和的进行归一化的话会出现问题，因为个体可能出现负值，总和也可能出现负值，如果归一化的时候除以了一个负值，选择时就会选择一些不良的个体，对实验结果造成影响。对于这个问题，我把适应度函数定为目标函数的函数值加一个正数，保证得到的适应值为正数，然后再进行一般的归一化和选择的操作。实验结果表明，之前的实验结果很不稳定，修正后的结果比较稳定，趋于最大值。 二交叉操作 首先是根据交叉概率probCross选择要交叉的个体进行交叉。

这里根据交叉参数crossnum进行多点交叉，首先随机生成交叉点位置，允许交叉点重合，两个重合的交叉点效果互相抵消，相当于没有交叉点，然后根据交叉点进行交叉操作，得到新的个体。 三变异操作 首先是根据变异概率probMutation选择要变异的个体。 变异时先随机生成变异的位置，然后把改位的01值翻转。

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 问题等有着多方面的重要意义。

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

遗传算法在多目标优化的应用：公式，讨论，概述/总括 概述 本文主要以适合度函数为基础的分配方法来阐述多目标遗传算法。传统的群落形成方法（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)保持种群的多样性及进化方向的控制。算法需要求出的是一组不同的非劣解，所以计算中要防止种群收敛到某一个解。与一般遗传算法进化到

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

实验十遗传算法与优化问题 一、问题背景与实验目的 遗传算法（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 变异染色体水平上基因变化编码的某些元素被改变

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

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

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

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

4遗传算法与函数优化

第四章遗传算法与函数优化 4.1 研究函数优化的必要性： 首先，对很多实际问题进行数学建模后，可将其抽象为一个数值函数的优化问题。由于问题种类的繁多，影响因素的复杂，这些数学函数会呈现出不同的数学特征。除了在函数是连续、可求导、低阶的简单情况下可解析地求出其最优解外，大部分情况下需要通过数值计算的方法来进行近似优化计算。 其次，如何评价一个遗传算法的性能优劣程度一直是一个比较难的问题。这主要是因为现实问题种类繁多，影响因素复杂，若对各种情况都加以考虑进行试算，其计算工作量势必太大。由于纯数值函数优化问题不包含有某一具体应用领域中的专门知识，它们便于不同应用领域中的研究人员能够进行相互理解和相互交流，并且能够较好地反映算法本身所具有的本质特征和实际应用能力。所以人们专门设计了一些具有复杂数学特征的纯数学函数，通过遗传算法对这些函数的优化计算情况来测试各种遗传算法的性能。 4.2 评价遗传算法性能的常用测试函数 在设计用于评价遗传算法性能的测试函数时，必须考虑实际应用问题的数学模型中所可能呈现出的各种数学特性，以及可能遇到的各种情况和影响因素。这里所说的数学特性主要包括： ●连续函数或离散函数； ●凹函数或凸函数； ●二次函数或非二次函数； ●低维函数或高维函数； ●确定性函数或随机性函数； ●单峰值函数或多峰值函数，等等。 下面是一些在评价遗传算法性能时经常用到的测试函数： (1)De Jong函数F1： 这是一个简单的平方和函数，只有一个极小点f1(0, 0, 0)＝0。

(2)De Jong 函数F2： 这是一个二维函数，它具有一个全局极小点f 2(1，1) = 0。该函数虽然是单峰值的函数，但它却是病态的，难以进行全局极小化。 (3)De Jong 函数F3： 这是一个不连续函数，对于]0.5,12.5[--∈i x 区域内的每一个点，它都取全局极小值 30),,,,(543213-=x x x x x f 。

遗传算法多目标函数优化

多目标遗传算法优化 铣削正交试验结果 说明： 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)];

各种优化算法求解函数优化问题

各种优化算法求解函数优化问题 1.遗传算法的简单介绍及流程 1.1遗传算法的基本原理 遗传算法 ( Genetic Algorithm ,简称 GA) 是近年来迅速发展起来的一种全新的随机搜索优化算法。与传统搜索算法不同 ,遗传算法从一组随机产生的初始解 (称为群体 )开始搜索。群体中的每个个体是问题的一个解 ,称为染色体。这些染色体在后续迭代中不断进化 , 称为遗传。遗传算法主要通过交叉、变异、选择运算实现。交叉或变异运算生成下一代染色体,称为后 代。染色体的好坏用适应度来衡量。根据适应度的大小从上一代和后代中选择一定数量的个 体 ,作为下一代群体 ,再继续进化 ,这样经过若干代之后 ,算法收敛于最好的染色体 ,它很可能就是问题的最优解或次优解。遗传算法中使用适应度这个概念来度量群体中的各个个体在优化计算中有可能达到最优解的优良程度。度量个体适应度的函数称为适应度函数。适应度函数的定义一般与具体求解问题有关。 1.2遗传算法的流程 第一步：确定决策变量及各种约束条件，即确定出个体的表现型X和问题的解空间； 第二步：确定出目标函数的类型，即求目标函数的最大值还是最小值，以及其数学描述形式或量化方法，建立其优化模型； 第三步：确定表示可行解的染色体编码方法，即确定出个体的基因型X和遗传算法的搜 索空间。 第四步：确定解码方法，即确定出个体的基因型 X和个体的表现型 X的对应关系或转换方法； 第五步：确定个体时候适应度的量化评价方法，即确定出由目标函数 f(X) 值到个体适应度F(X) 的转换规则； 第六步：设计遗传算子，即确定出选择运算、交叉运算、变异运算等遗传算子的具体操作方法； 第七步：确定出遗传算法的运行参数，即确定出遗传算法的M、 T、 Pc、 Pm等参数。1.3 遗传算法求解函数优化问题中的参数分析 目前，函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用范 例。对于函数优化中求解实数型变量的问题，一般采用动态编码和实数编码的方法来提高其搜

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

函数最值问题：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问题（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问题。

遗传算法及其在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年里，在求解旅行商问题的最优解方面取得了极大的进展。尽管有这些成就，但旅行商问题还远未解决，问题的许多方面还要研究，很多问题还在期待满意的回答。 另外，遗传算法就其本质来说，主要是解决复杂问题的一种鲁棒性强的启发式随机

遗传算法

遗传算法 开放分类：编程、程序、数学、计算机、算法 目录 ? 遗传算法定义 ? 遗传算法特点 ? 遗传算法的应用 ? 遗传算法的现状 ? 遗传算法的一般算法 ? 遗传算法实例 遗传算法定义 [编辑本段] 遗传算法（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、遗传算法使用概率搜索技术，而非确定性规则。 遗传算法的应用 [编辑本段] 由于遗传算法的整体搜索策略和优化搜索方法在计算是不依赖于梯度信息或其它辅助知识，而只需要影响

遗传算法与优化问题

遗传算法与优化问题 （摘自：华东师范大学数学系；https://www.wendangku.net/doc/6814174928.html,/） 一、问题背景与实验目的 二、相关函数（命令）及简介 三、实验内容 四、自己动手 一、问题背景与实验目的 遗传算法（Genetic Algorithm—GA），是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，它是由美国Michigan大学的J.Holland教授于1975年首先提出的．遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、适于并行处理及应用范围广等显著特点，奠定了它作为21世纪关键智能计算之一的地位． 本实验将首先介绍一下遗传算法的基本理论，然后用其解决几个简单的函数最值问题，使读者能够学会利用遗传算法进行初步的优化计算． 1．遗传算法的基本原理 遗传算法的基本思想正是基于模仿生物界遗传学的遗传过程．它把问题的参数用基因代表，把问题的解用染色体代表（在计算机里用二进制码表示），从而得到一个由具有不同染色体的个体组成的群体．这个群体在问题特定的环境里生存竞争，适者有最好的机会生存和产生后代．后代随机化地继承了父代的最好特征，并也在生存环境的控制支配下继续这一过程．群体的染色体都将逐渐适应环境，不断进化，最后收敛到一族最适应环境的类似个体，即得到问题最优的解．值得注意的一点是，现在的遗传算法是受生物进化论学说的启发提出的，这种学说对我们用计算机解决复杂问题很有用，而它本身是否完全正确并不重要（目前生物界对此学说尚有争议）．

（1）遗传算法中的生物遗传学概念 由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算法中要用到各种进化和遗传学的概念． 首先给出遗传学概念、遗传算法概念和相应的数学概念三者之间的对应关系．这些概念如下： （2）遗传算法的步骤 遗传算法计算优化的操作过程就如同生物学上生物遗传进化的过程，主要有三个基本操作（或称为算子）：选择（Selection）、交叉（Crossover）、变异（Mutation）． 遗传算法基本步骤主要是：先把问题的解表示成“染色体”，在算法中也就是以二进制编码的串，在执行遗传算法之前，给出一群“染色体”，也就是假设的可行解．然后，把这些假设的可行解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉、变异过

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 )。

基本遗传算法及其在函数优化中的作用

《人工智能及其应用大作业（一）》 题目：基本遗传算法及其在函数优化中的作用 学号： 姓名：

基本遗传算法及其在函数优化中的应用 摘要： 从遗传算法的编码、遗传算子等方面剖析了遗传算法求解无约束函数优化问题的一般步骤,并以一个实例说明遗传算法能有效地解决函数优化问题。本文利用基本遗传算法求解函数优化问题，选用f(x)=xsin(10πx)+2.0，取值范围在]2,1 [ 中，利用基本遗传算法求解两个函数的最优值，遗传算法每次100代，一共执行10次，根据运算结果分析得到最优解。 关键字：遗传算法选择交叉变异函数优化 1.前言 1.1基本概念 遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。遗传算法是一种群体型操作，该操作以群体中的所有个体为对象。选择（Selection）、交叉（Crossover）和变异（Mutation）是遗传算法的3个主要操作算子，它们构成了所谓的遗传操作（genetic operation），使遗传算法具有了其它传统方法所没有的特性。 1.2 遗传算法的特点 其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。 1.3遗传算法的应用 函数优化，组合优化，机器人智能控制，及组合图像处理和模式识别等。 2.基本遗传算法 2.1简单遗传算法的求解步骤 Step1：参数设置及种群初始化； Step2：适应度评价； Step3：选择操作； Step4：交叉操作； Step5：变异操作； Step6：终止条件判断，若未达到终止条件，则转到Step3； Step7：输出结果。 2.2停机准则

Matlab环境下的遗传算法程序设计及优化问题求解

本栏目责任编辑：谢媛媛 开发研究与设计技术 遗传算法（ＧＡ）是借鉴生物界自然选择和群体进化机制而形成的一种全局寻优算法，其本质上是一种基于概率的随机搜索算法。与其它的优化算法相比较，遗传算法具有以下优点：（１）通用性；（２）并行性；（３）简单性和可操作性；（４）稳定性和全局性。 １遗传算法概述 在遗传算法中，首先将空间问题中的决策变量通过一定的编码表示成遗传空间的一个个体，它是一个基因型串结构数据；然后将目标函数转换成适应度值，用来评价每个个体的优劣，并将其作为遗传操作的依据。遗传操作包括三个算子：选择、重组和变异。选择是从当前群体中选择适应值高的个体以生成交配池的过程，交配池是当前代与下一代之间的中间群体。选择算子的作用是用来提高群体的平均适应度值。重组算子的作用是将原有的优良基因遗传给下一代个体，并生成包含更复杂基因的新个体，它先从交配池中的个体随机配对，然后将两两配对的个体按一定方式相互交换部分基因。变异算子是对个体的某一个或几位按某一较小的概率进行反转其二进制字符，模拟自然界的基因突变现象。 遗传算法的基本程序实现流程如下： （１）先确定待优化的参数大致范围，然后对搜索空间进行编码；（２）随机产生包含各个个体的初始种群； （３）将种群中各个个体解码成对应的参数值，用解码后的参数求代价函数和适应度函数，运用适应度函数评估检测各个个体适应度； （４）对收敛条件进行判断，如果已经找到最佳个体，则停止，否则继续进行遗传操作； （５）进行选择操作，让适应度大的个体在种群中占有较大的比例，一些适应度较小的个体将会被淘汰； （６）随机交叉，两个个体按一定的交叉概率进行交叉操作，并产生两个新的子个体； （７）按照一定的变异概率变异，使个体的某个或某些位的性质发生改变； （８）重复步骤（３）至（７），直至参数收敛达到预定的指标。使用遗传算法需要确定的运行参数有：编码串长度、交叉和变异概率、种群规模。编码串长度由问题的所要求的精度来决定。交叉概率控制着交叉操作的频率，交叉操作是遗传算法中产生新 个体的主要方法，所以交叉概率通常应取较大值，但如果交叉概率太大的话又可能反过来会破坏群体的优良模式，一般取０．４－ ０．９９。变异概率也是影响新个体产生的一个因素，如果变异概率 太小，则产生新个体较少；如果变异概率太大，则又会使遗传算法变成随机搜索，为保证个体变异后与其父体不会产生太大的差异，通常取变异概率为０．０００１－０．１以保证种群发展的稳定性。种群规模太大时，计算量会很大，使遗传算法的运行效率降低，种群规模太小时，可以提高遗传算法的运行速度，但却种群的多样性却降低了，有可能找不出最优解，通常取种群数目２０－１００。从理论上讲，不存在一组适用于所有问题的最佳参数值，随着问题参数的变化，有效问参数的差异往往是十分显著的。 ２用Ｍａｔｌａｂ语言来实现遗传算法 Ｍａｔｌａｂ是一个高性能的计算软件，配备有功能强大的数学函 数支持库，适用范围大，编程效率高，语句简单，功能齐备，是世界上顶级的计算与仿真程序软件。利用Ｍａｔｌａｂ来编写遗传算法程序简单而且易于操作。 ２．１编码 编码就是把一个问题的可行解从其解空间转换到遗传算法能够处理的搜索空间的转化方法，编码形式决定了重组算子的操作。遗传算法是对编码后的个体作选择与交叉运算，然后通过这些反复运算达到优化目标。遗传算法首要的问题是通过编码将决策变量表示成串结构数据。我们常用的是二进制编码，即用二进制数构成的符号串来表示每个个体。通常根据搜索精度（ｓｃａ＿ｖａｒ）、决策变量上界（ｒａｎｇｅ（２））的和下界（ｒａｎｇｅ（１））来确定各个二进制字符串的长度（ｂｉｔ＿ｎ）， 搜索精度为ｓｃａ＿ｖａｒ＝（ｒａｎｇｅ（２）－ｒａｎｇｅ（１））．／ （２＾ｂｉｔ＿ｎ—１），然后再随机产生一个的初始种群（ｂｅ＿ｇｅｎ），其规模为ｐｏｐｕｓｉｚｅ。下面用ｅｎｃｏｄｉｎｇ函数来实现编码和产生初始的种群： ｆｕｎｃｔｉｏｎ［ｂｅ＿ｇｅｎ，ｂｉｔ＿ｎ］＝ｅｎｃｏｄｉｎｇ（ｓｃａ＿ｖａｒ，ｒａｎｇｅ（１），ｒａｎｇｅ（２），ｐｏｐｕｓｉｚｅ） ｂｉｔ＿ｎ＝ｃｅｉｌ（ｌｏｇ２（（ｒａｎｇｅ（２）－ｒａｎｇｅ（１））．／ｓｃａ＿ｖａｒ））；ｂｅ＿ｇｅｎ＝ｒａｎｄｉｎｔ（ｐｏｐｕｓｉｚｅ，ｓｕｍ（ｂｉｔ＿ｎ））；２．２译码 决策变量经过编码之后，各个个体构成的种群ｂｅ＿ｇｅｎ要通过解码才能转换成原问题空间的决策变量构成的种群ｖｇｅｎ，这样才 收稿日期：２００６－０１－０５ 作者简介：梁科（１９８１－），硕士研究生，研究方向：智能计算与优化方法；夏定纯（１９６３－），教授，研究方向：人工智能，计算机在线检测。 Matlab 环境下的遗传算法程序设计及优化问题求解 梁科，夏定纯 （武汉科技学院计算机科学学院，湖北武汉４３００７３） 摘要：本文介绍了遗传算法的流程及几个算子，给出了在ｍａｔｌａｂ语言环境下实现编码、译码、选择、重组和变异各算子的编程方法，最后用一个实例来说明遗传算法在寻找全局最优解中的应用。 关键词：遗传算法；ｍａｔｌａｂ；程序设计中图分类号：ＴＰ３１２ 文献标识码：Ａ 文章编号：１００９－３０４４（２００７）０４－１１０４９－０３ ＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍＰｒｏｇｒａｍｍｉｎｇＢｙＭａｔｌａｂＡｎｄＯｐｔｉｍｉｚｉｎｇＰｒｏｂｌｅｍＳｏｌｖｉｎｇ ＬＩＡＮＧＫｅ，ＸＩＡＤｉｎｇ－ｃｈｕｎ （ＤｅｐａｒｔｍｅｎｔｏｆＣｏｍｐｕｔｅｒｓｃｉｅｎｃｅ，ＷｕｈａｎＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅ＆Ｅｎｇｉｎｅｅｒｉｎｇ，Ｗｕｈａｎ４３００７３，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅｓｅｖｅｒａｌｆａｃｔｏｒｓｏｆｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｈａｖｅｂｅｅｎｐｒｅｓｅｎｔｅｄｉｎｔｈｉｓｐａｐｅｒ，ａｎｄｔｈｅｐｒｏｇｒａｍｍｉｎｇｏｆｅｎｃｏｄｉｎｇ、ｄｅｃｏｄｉｎｇ、ｃｈｏｉｃｅ、ｃｒｏｓｓｏｖｅｒａｎｄｍｕｔａｔｉｏｎｏｆｍａｔｌａｂｈａｖｅｂｅｅｎｇｉｖｅｎ，ｆｉｎａｌｌｙ，ａｆｕｎｃｔｉｏｎｏｐｔｉｍｉｚｉｎｇｐｒｏｂｌｅｍｈａｓｂｅｅｎｐｒｅｓｅｎｔｅｄｔｏｄｅｍｏｎｓｔｒａｔｅｄｔｈｅａｐｐｌｉｃａｔｉｏｎａｂｏｕｔｇｌｏｂａｌｏｐｔｉｍｉｚｉｎｇｏｆｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ． Ｋｅｙｗｏｒｄｓ：ＧＡ；ｍａｔｌａｂ；ｐｒｏｇｒａｍｍｉｎｇ １０４９