下载文档原格式
1 遗传算法1.1 遗传算法的定义遗传算法(GeneticAlgorithm，GA)是近多年来发展起来的一种全新的全局优化算法，它是基于了生物遗传学的观点，是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。
它通过自然选择、遗传、复制、变异等作用机制，实现各个个体的适应性的提高，从而达到全局优化。
遗传算法151解决一个实际问题通常都是从一个种群开始，而这个种群通常都是含有问题的一个集合。
这个种群是由一定数目的个体所构成的，利用生物遗传的知识我们可以知道这些个体正好组成了我们知道的染色体，也就是说染色体是由一个个有特征的个体组成的。
另外我们还知道，遗传算法是由染色体组成，而染色体是由基因组成，可以这么说，基因就决定了个体的特性，所以对于遗传算法的最开始的工作就需要进行编码工作。
然后形成初始的种群，最后进行选择、交叉和变异的操作。
1.2遗传算法的重要应用在现实应用中，遗传算法在很多领域得到很好的应用，特别是在解决多维并且相当困难的优化问题中时表现出了很大的优势。
在遗传算法的优化问题的应用中，其中最为经典的应用就是我们所熟悉的函数优化问题，它也是对遗传算法的性能进行评价的最普遍的一种算法;另外的一个最重要的应用，也就是我们本文所研究的应用—组合优化问题，一般的算法很难解决组合优化问题的搜索空间不断扩大的局面，而组合优化问题正好是解决这种问题的最有效的方法之一，在本文的研究中，比如求解TSP问题、VRP问题等方面都得到了很好的应用;另外遗传算法在航空控制系统中的应用、在图像处理和模式识别的应用、在生产调度方面的应用以及在工人智能、人工生命和机器学习方面都得到了很好的应用。
其实在当今的社会中，有关于优化方面的问题应用于各行各业中，因此有关于优化问题已经变得非常重要，它对于整个社会的发展来说都是一个不可改变的发展方向，也是社会发展的一个非常重要的需要。
1.3 遗传算法的特点遗传算法不同于传统的搜索与优化方法，它是随着问题种类的不同以及问题规模的扩大，能以有限的代价来很好的解决搜索和优化的方法。
什么是遗传算法遗传算法的基本意思就是说象人的遗传一样，有一批种子程序，它们通过运算得到一些结果，有好有坏，把好的一批取出来，做为下一轮计算的初值进行运算，反复如此，最终得到满意的结果。
举个例子，假如有一个动物群体，如果你能让他们当中越强壮的越能优先交配和产籽，那么千万年后，这个动物群体肯定会变得更加强壮，这是很容易理解的。
同样，对于许多算法问题，特别是NP问题，比如说最短路径，如果有400个城市，让你找出最短的旅游路线，采用穷举比较，复杂度为O（n！），这时，你可以先随机产生100种路径，然后让他们之中路程越短的那些越能优先互相交换信息(比如每条里面随机取出10个位置互相交换一下),那么循环几千次后，算出来的路径就跟最短路径非常接近了（即求出一个近似最优解）。
遗传算法的应用还有很多，基本思想都一样，但实现上可能差别非常大。
现在有许多搞算法的人不喜欢遗传算法，因为，它只给出了一种“有用”的方法，却不能保证有用的程度，与此相反，能保证接近最优程度的概率算法更受青睐。
遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。
它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。
遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。
它是现代有关智能计算中的关键技术之一。
1.遗传算法与自然选择 达尔文的自然选择学说是一种被人们广泛接受的生物进化学说。
这种学说认为，生物要生存下去，就必须进行生存斗争。
生存斗争包括种内斗争、种间斗争以及生物跟无机环境之间的斗争三个方面。
在生存斗争中，具有有利变异的个体容易存活下来，并且有更多的机会将有利变异传给后代；具有不利变异的个体就容易被淘汰，产生后代的机会也少的多。
二、遗传算法的特点（1）遗传算法是对参数的编码进行操作，而非对参数本身，这就是使得我们在优化计算过程中可以借鉴生物学中染色体和基因等概念，模仿自然界中生物的遗传和进化等机理；（2）遗传算法同时使用多个搜索点的搜索信息。
传统的优化方法往往是从解空间的单个初始点开始最优解的迭代搜索过程，单个搜索点所提供的信息不多，搜索效率不高，有时甚至使搜索过程局限于局部最优解而停滞不前。
遗传算法从由很多个体组成的一个初始群体开始最优解的搜索过程，而不是从一个单一的个体开始搜索，这是遗传算法所特有的一种隐含并行性，因此遗传算法的搜索效率较高。
（3）遗传算法直接以目标函数作为搜索信息。
传统的优化算法不仅需要利用目标函数值，而且需要目标函数的导数值等辅助信息才能确定搜索方向。
而遗传算法仅使用由目标函数值变换来的适应度函数值，就可以确定进一步的搜索方向和搜索范围，无需目标函数的导数值等其他一些辅助信息。
遗传算法可应用于目标函数无法求导数或导数不存在的函数的优化问题，以及组合优化问题等。
（4）遗传算法使用概率搜索技术。
遗传算法的选择、交叉、变异等运算都是以一种概率的方式来进行的，因而遗传算法的搜索过程具有很好的灵活性。
随着进化过程的进行，遗传算法新的群体会更多地产生出许多新的优良的个体。
（5）遗传算法在解空间进行高效启发式搜索，而非盲目地穷举或完全随机搜索；（6）遗传算法对于待寻优的函数基本无限制，它既不要求函数连续，也不要求函数可微，既可以是数学解析式所表示的显函数，又可以是映射矩阵甚至是神经网络的隐函数，因而应用范围较广；（7）遗传算法具有并行计算的特点，因而可通过大规模并行计算来提高计算速度，适合大规模复杂问题的优化。
三、遗传算法的应用领域（1）函数优化。
函数优化是遗传算法的经典应用领域，也是遗传算法进行性能评价的常用算例。
尤其是对非线性、多模型、多目标的函数优化问题，采用其他优化方法较难求解，而遗传算法却可以得到较好的结果。
（2）组合优化。
随着问题的增大，组合优化问题的搜索空间也急剧扩大，采用传统的优化方法很难得到最优解。
遗传算法是寻求这种满意解的最佳工具。
例如，遗传算法已经在求解旅行商问题、背包问题、装箱问题、图形划分问题等方面得到成功的应用。
（3）生产调度问题在很多情况下，采用建立数学模型的方法难以对生产调度问题进行精确求解。
在现实生产中多采用一些经验进行调度。
遗传算法是解决复杂调度问题的有效工具，在单件生产车间调度、流水线生产车间调度、生产规划、任务分配等方面遗传算法都得到了有效的应用。
（4）自动控制。
在自动控制领域中有很多与优化相关的问题需要求解，遗传算法已经在其中得到了初步的应用。
例如，利用遗传算法进行控制器参数的优化、基于遗传算法的模糊控制规则的学习、基于遗传算法的参数辨识、基于遗传算法的神经网络结构的优化和权值学习等。
（5）机器人例如，遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人结构优化和行为协调等方面得到研究和应用。
（6）图像处理遗传算法可用于图像处理过程中的扫描、特征提取、图像分割等的优化计算。
目前遗传算法已经在模式识别、图像恢复、图像边缘特征提取等方面得到了应用。
（3）遗传算子：基本遗传算法使用下述三种遗传算子：①选择运算: 使用比例选择算子；②交叉运算: 使用单点交叉算子；③变异运算: 使用基本位变异算子或均匀变异算子。
（4）基本遗传算法的运行参数有下述4个运行参数需要提前设定：M：群体大小，即群体中所含个体的数量，一般取为20~100；G ：遗传算法的终止进化代数，一般取为100~500； Pc ：交叉概率，一般取为0.4~0.99； Pm ：变异概率，一般取为0.0001~0.1。
4.2 遗传算法的应用步骤对于一个需要进行优化的实际问题，一般可按下述步骤构造遗传算法：第一步：确定决策变量及各种约束条件，即确定出个体的表现型X 和问题的解空间；第二步：建立优化模型，即确定出目标函数的类型及数学描述形式或量化方法；第三步：确定表示可行解的染色体编码方法，即确定出个体的基因型x 及遗传算法的搜索空间； 第四步：确定解码方法，即确定出由个体基因型x 到个体表现型X 的对应关系或转换方法； 第五步：确定个体适应度的量化评价方法，即确定出由目标函数值到个体适应度的转换规则； 第六步：设计遗传算子，即确定选择运算、交叉运算、变异运算等遗传算子的具体操作方法。
第七步：确定遗传算法的有关运行参数，即M, G, Pc, Pm 等参数。
以上操作过程可以用图1来表示。
五、 遗传算法求函数极值利用遗传算法求Rosenbrock 函数的极大值5.1 二进制编码遗传算法求函数极大值 求解该问题遗传算法的构造过程： （1）确定决策变量和约束条件； （2）建立优化模型；（3）确定编码方法用长度为10位的二进制编码串来分别表示两个决策变量x1,x2。
10位二进制编码串可以表示从0到1023之间的1024个不同的数，故将x 1,x 2的定义域离散化为1023个均等的区域，包括两个端点在内共有1024个不同的离散点。
从离散点-2.048到离散点2.048 ，分别对应于从0000000000(0)到1111111111(1023)之间的二进制编码。
将x1,x2分别表示的两个10位长的二进制编码串连接在一起，组成一个20位长的二进制编码串，它就构成了这个函数优化问题的染色体编码方法。
使用这种编码方法，解空间和遗传算法的搜索空间就具有一一对应的关系。
例如： 表示一个个体的基因型，其中前10位表示x1，后10位表示x2。
（4）确定解码方法：解码时需要将20位长的二进制编码串切断为两个10位长的二进制编码串，然后分别将它们转换为对应的十进制整数代码，分别记为y 1和y 2。
依据个体编码方法和对定义域的离散化方法可知，将代码y 转换为变量x 的解码公式为⎩⎨⎧=≤≤--+-=)2,1(048.2048.2)1()(100),(212221212i x x x x x x f i )2,1(048.21023096.4=-⨯=i y x ii例如，对个体 它由两个代码所组成上述两个代码经过解码后，可得到两个实际的值（5）确定个体评价方法：由于Rosenbrock 函数的值域总是非负的，并且优化目标是求函数的最大值，故可将个体的适应度直接取为对应的目标函数值，即 选个体适应度的倒数作为目标函数（6）设计遗传算子：选择运算使用比例选择算子，交叉运算使用单点交叉算子，变异运算使用基本位变异算子。
（7）确定遗传算法的运行参数：群体大小M=80，终止进化代数G=100，交叉概率Pc=0.60，变异概率Pm=0.10。
上述七个步骤构成了用于求函数极大值的优化计算基本遗传算法。
采用上述方法进行仿真，经过100步迭代，最佳样本为 即当 时，Rosenbrock 函数具有极大值，极大值为3905.9。
遗传算法的优化过程是目标函数J 和适应度函数F 的变化过程。
由仿真结果可知，随着进化过程的进行，群体中适应度较低的一些个体被逐渐淘汰掉，而适应度较高的一些个体会越来越多，并且它们都集中在所求问题的最优点附近，从而搜索到问题的最优解。
5.2 实数编码遗传算法求函数极大值 求解该问题遗传算法的构造过程： （1）确定决策变量和约束条件；（2）建立优化模型；（3）确定编码方法：用2个实数分别表示两个决策变量，分别将的定义域离散化为从离散点-2.048到离散点2.048的Size 个实数。
（4）确定个体评价方法：个体的适应度直接取为对应的目标函数值，即 选个体适应度的倒数作为目标函数 （5）设计遗传算子：选择运算使用比例选择算子，交叉运算使用单点交叉算子，变异运算使用基本位变异算子。
（6）确定遗传算法的运行参数：群体大小M=500，终止进化代数G=200，交叉概率P c =0.90，采用自适应变异概率 即变异概率与适应度有关，适应度越小，变异概率越大。
上述六个步骤构成了用于求函数Rosenbrock 极大值的优化计算的实数编码遗传算法。
十进制编码求函数Rosenbrock 极大值。
仿真程序经过200步迭代，最佳样本为 即当 ， 时，函数具有极大值，极大值为3880.3。
某实验室有一台自动检验机器性能的仪器，要求检机器的顾客按普阿松分布到达，每小时平均4个顾客，检验每台机器所需时间为6分钟。
1) 在检验室内机器台数Ls （期望值，2) 等候检验的机器台数Lq ，3)每台机器在室内消耗时间Ws ，4)每台机器平均等待检验的时间Wq某单人裁缝店做西服,每套需经过4个不同的工序,4个工序完成后才开始做另一套.每一工序的时间服从普阿松分布,期望值为2小时.顾客到达服从普阿松分布,平均订货率为5.5套/周(设一周为6天,每天8小时).问一顾客为等到做好一套西服的期望时间为多长？λ=5.5套/周 设μ为平均服务率（单位时间做完的套数）1/μ为平均每套所需要的时间 1/4μ为平均每工序所需要的时间 μ=1/8套/小时=6套/周μk T E i 1][=221]var[μkT i =μ1][=T E1101110001 0000110111:x 881,5521==y y 476.1,828.121=-=x x ),()(21x x f x F =)(1)(x F x J =0]0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 [0 B est =S 2.0480 2.0480 21-=-=,x x ),()(21x x f x F =)(1)(x F x J =0.01/Size Size]:1:[1-0.10m ⨯=P 2.044]- [-2.0438 B est =S 2.044 2-=x 2.0438 1-=x21]var[μk T =ρ=5.5/6)1(2)1()1(212222ρρρρμλρρ-++=-++=k k k L s = 7.2188注意】matlab 工具箱函数必须放在工作目录下【问题】求f(x)=x+10*sin(5x)+7*cos(4x) 的最大值，其中0<=x<=9【分析】选择二进制编码，种群中的个体数目为10，二进制编码长度为20，交叉概率为0.95,变异概率为0.08 【程序清单】% 编写目标函数function[sol,eval]=fitness(sol,options) x=sol(1);eval=x+10*sin(5*x)+7*cos(4*x);% 把上述函数存储为fitness.m 文件并放在工作目录下initPop=initializega(10,[0 9],'fitness');% 生成初始种群，大小为10[x endPop,bPop,trace]=ga([0 9],'fitness',[],init Pop,[1e-6 1 1],'maxGenTerm',25,'normGeomSelect',... [0.08],['arithXover'],[2 ],'nonUnifMutation',[2 25 3]) %25 次遗传迭代运算借过为：x =页码，2/4 matlab 遗传算法工具箱函数及实例讲解（转引） 2005-6-23 /Article_Show.asp?ArticleID=422 7.8562 24.8553(当x 为7.8562时，f （x ）取最大值24.8553) 注：遗传算法一般用来取得近似最优解，而不是最优解。
