遗传算法论文范文第1篇
概念
遗传算法是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法，它借鉴了达尔文的进化论和孟德尔的遗传学说。其本质是一种高效、并行、全局搜索的方法，它既能在搜索中自动获取和积累有关空间知识，并自适应地控制搜索过程以求得最优解遗传算法操作使用适者生存的原则，在潜在的解决方案种群中逐次产生一个近视最优方案。在遗传算法的每一代中，根据个体在问题域中的适应度值和从自然遗传学中借鉴来的再造方法进行个体选择，产生一个新的近视解。这个过程导致种群中个体的进化，得到的新个体比原个体更适应环境，就像自然界中的改造一样。
应用
遗传算法在人工智能的众多领域具有广泛应用。例如，机器学习、聚类、控制(如煤气管道控制)、规划(如生产任务规划)、设计(如通信网络设计、布局设计)、调度(如作业车间调度、机器调度、运输问题)、配置(机器配置、分配问题)、组合优化(如tsp、背包问题)、函数的最大值以及图像处理和信号处理等等。遗传算法多用应与复杂函数的优化问题中。 原理
遗传算法模拟了自然选择和遗传中发生的复制、交叉、和变异等现象，从任一初始种群出发，通过随机选择、交叉、变异操作，产生一群更适合环境的个体，使群体进行到搜索空间中越来越好的区域，这样一代一代地不断繁衍进化，最后收敛到一群最适合环境的个体求得问题的最优解。
算法流程 1. 编码：解空间中的解数据x，作为作为遗传算法的表现型形式。从表现
型到基本型的映射称为编码。遗传算法在进行搜索之前先将解空间的解数据表示成遗传空间的基本型串结构数据，这些串结构数据的不同的组合就构成了不同的点。 2. 初始种群的形成：随机产生n个初始串数据，每个串数据称为一个个体， n个串数据构成了一个群体。遗传算法以这n个串结构作为初始点开始迭代。设置进化代数计数器t 0;设置最大进行代数t;随机生成m个个体作为初始群体p(0)。 3. 适应度检测：适应度就是借鉴生物个体对环境的适应程度,适应度函数 就是对问题中的个体对象所设计的表征其优劣的一种测度。根据具体问题计算p(t)的适应度。
4. 选择：将选择算子作用于群体。选择的目的是把优化的个体直接遗传到
下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。
5. 交叉：将交叉算子作用于群体。所谓交叉是指把两个父代个体的部分结
构加以替换重组而生成新个体的操作。遗传算法中起核心作用的就是交叉算子。 6. 变异：将变异算子作用于群体。即是对群体中的个体串的某些基因座上
的基因值作变动。
群体p(t)经过选择、交叉、变异运算之后得到下一代群体p(t+1)。 7. 终止条件判断:若t<=t,则t=t+1，转到第3步，否则以进化过程中所得
到的具有最大适应度个体作为最优解输出，终止计算。
遗传算法流程图如下图所示： 遗传算法
下几种：适应度比例方法、随机遍历抽样法、局部选择法。
其中轮盘赌选择法是最简单也是最常用的选择方法。在该方法中，各个个体的选择概率和其适应度值成比例。设群体大小为n，其中个体i的适应度为，则i 被选择的概率，为遗传算法
2、交叉：在自然界生物进化过程中起核心作用的是生物遗传基因的重组(加上变异)。同样，遗传算法中起核心作用的是遗传操作的交叉算子。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。通过交叉，遗传算法的搜索能力得以飞跃提高。
交叉算子根据交叉率将种群中的两个个体随机地交换某些基因，能够产生新的基因组合，期望将有益基因组合在一起。根据编码表示方法的不同，可以有以下的算法： b)二进制交叉(binary valued crossover) 1)单点交叉(single-point crossover) 2)多点交叉(multiple-point crossover) 3)均匀交叉(uniform crossover) 4)洗牌交叉(shuffle crossover) 5)缩小代理交叉(crossover with reduced surrogate)。
3、变异
变异算子的基本内容是对群体中的个体串的某些基因座上的基因值作变动。依据个体编码表示方法的不同，可以有以下的算法： a)实值变异 b)二进制变异。
一般来说，变异算子操作的基本步骤如下： a)对群中所有个体以事先设定的编译概率判断是否进行变异 b)对进行变异的个体随机选择变异位进行变异。
例：简单一元函数优化
求下面函数的最大值：
f(x)=xsin(10*pi*x)+2.0, -1<=x<=2; 程序： figure(1); fplot(variable.*sin(10*pi*variable)+2.0,[-1,2]); %画出函数曲线 %定义遗传算法参数
nind=40; %个体数目(number of individuals) maxgen=25; %最大遗传代数(maximum number of generations) preci=20; %变量的二进制位数(precision of variables) ggap=0.9; %代沟(generation gap) trace=zeros(2, maxgen); %寻优结果的初始值 fieldd=[20;-1;2;1;0;1;1]; %区域描述器(build field descriptor) chrom=crtbp(nind, preci); %初始种群 gen=0; %代计数器 variable=bs2rv(chrom, fieldd);
%计算初始种群的十进制转换
objv=variable.*sin(10*pi*variable)+2.0; %计算目标函数值 while gen
基本概念
遗传算法(genetic algorithms, ga)是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。
它模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。 ga的组成: (1)编码(产生初始种群)
(2)适应度函数
(3)遗传算子(选择、交叉、变异)
(4)运行参数
编码
基因在一定能够意义上包含了它所代表的问题的解。基因的编码方式有很多，这也取决于要解决的问题本身。常见的编码方式有：
(1) 二进制编码，基因用0或1表示(常用于解决01背包问题) 如：基因a：00100011010 (代表一个个体的染色体) (2) 互换编码(用于解决排序问题，如旅行商问题和调度问题)
如旅行商问题中，一串基因编码用来表示遍历的城市顺序，如：234517986，表示九个城市中，先经过城市2，再经过城市3，依此类推。
(3) 树形编码(用于遗传规划中的演化编程或者表示)
如,问题：给定了很多组输入和输出。请你为这些输入输出选择一个函数，使得这个函数把每个输入尽可能近地映射为输出。
编码方法：基因就是树形结构中的一些函数。
(4) 值编码 (二进制编码不好用时，解决复杂的数值问题)
在值编码中，每个基因就是一串取值。这些取值可以是与问题有关任何值：整数，实数，字符或者其他一些更复杂的东西。
适应度函数
遗传算法对一个个体(解)的好坏用适应度函数值来评价，适应度函数值越大，解的质量越好。适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。
如tsp问题，遍历各城市路径之和越小越好，这样可以用可能的最大路径长度减去实际经过的路径长度，作为该问题的适应度函数。
遗传算子——选择
遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：适应度高的个体被遗传到下一代群体中的概率大;适应度低的个体，被遗传到下一代群体中的概率小。选择操作的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。 sga(基本遗传算法)中采用轮盘赌选择方法。
轮盘赌选择又称比例选择算子，基本思想：各个个体被选中的概率与其适应度函数值大小成正比。设群体大小为n ，个体i 的适应度为 fi，则个体i 被选中遗传到下一代群体的概率为：
遗传算子——交叉
所谓交叉运算，是指对两个相互配对的染色体依据交叉概率按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算在ga中起关键作用，是产生新个体的主要方法。 1. 单交叉点法 (用于二进制编码)
选择一个交叉点,子代在交叉点前面的基因从一个父代基因那里得到,后面的部分从另外一个父代基因那里得到。
如：交叉前：
00000|01110000000010000 11100|00000111111000101 交叉后：
00000|00000111111000101 11100|01110000000010000 2. 双交叉点法 (用于二进制编码)
选择两个交叉点,子代基因在两个交叉点间部分来自一个父代基因,其余部分来自于另外一个父代基因. 如：交叉前： 01 |0010| 11 11 |0111| 01 交叉后： 11 |0010| 01 01 |0111| 11 3. 基于“ 与/或 ”交叉法 (用于二进制编码) 对父代按位与”逻辑运算产生一子代a;按位”或”逻辑运算产生另一子代b。该交叉策略在解背包问题中效果较好 . 如：交叉前： 01001011 11011101 交叉后： 01001001 11011111 4. 单交叉点法 (用于互换编码)
选择一个交叉点，子代的从初始位置出发的部分从一个基因复制，然后在另一个基因中扫描，如果某个位点在子代中没有，就把它添加进去。 如：交叉前： 87213 | 09546 98356 | 71420 交叉后：
87213 | 95640 98356 | 72104 5. 部分匹配交叉(pmx)法(用于互换编码) 先随机产生两个交叉点，定义这两点间的区域为匹配区域，并用交换两个父代的匹配区域。
父代a：872 | 130 | 9546 父代b：983 | 567 | 1420 变为： temp a: 872 | 567 | 9546 temp b: 983 | 130 | 1420 对于 temp a、temp b中匹配区域以外出现的数码重复，要依据匹配区域内的位置逐一进行替换。匹配关系：1<——>5 3<——>6 7<——>0 子代a：802 | 567 | 9143 子代b：986 | 130 | 5427 6. 顺序交叉法(ox) (用于互换编码)
从父代a随机选一个编码子串，放到子代a的对应位置;子代a空余的位置从父代b中按b的顺序选取(与己有编码不重复)。同理可得子代b。 父代a: 872 | 139 | 0546 父代b: 983 | 567 | 1420 交叉后：
子代a: 856 | 139 | 7420 子代b: 821 | 567 | 3904 7. 循环交叉(cx)法(用于互换编码) cx同ox交叉都是从一个亲代中取一些城市，而其它城市来自另外一个亲代，但是二者不同之处在于：ox中来自第一个亲代的编码子串是随机产生的，而cx却不是，它是根据两个双亲相应位置的编码而确定的。
父代a：1 2 3 4 5 6 7 8 9 | | | | | 父代a：5 4 6 9 2 3 7 8 1 可得循环基因：1->5->2->4->9->1 用循环的基因构成子代a，顺序与父代a一样 1 2 4 5 9 用父代b剩余的基因填满子代a： 1 2 6 4 5 3 7 8 9 子代b的编码同理。(循环基因 5->1->9->4->2->5)
遗传算子——变异 变异是指依据变异概率将个体编码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。ga中的变异运算是产生新个体的辅助方法，它决定了ga的局部搜索能力，同时保持种群的多样性。交叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。
注：变异概率pm不能太小，这样降低全局搜索能力;也不能太大，pm > 0.5，这时ga退化为随机搜索。篇三：计算智能学习心得体会
计算智能学习心得体会
本学期我们水利水电专业开了“计算智能概论”这门课，有我们学院的金菊良教授给我们授课，据说这门课相当难理解，我们课下做了充分的准备，借了计算智能和人工智能相关方面的书籍，并提前了解了一点相关知识，我感觉看着有点先进，给我们以往学的课程有很大区别，是一种全新的概念和理论，里面的遗传算法、模糊集理论、神经网络更是闻所未闻，由于课前读了一些书籍，我以为课堂上应该能容易理解一点，想不到课堂上听着还是相当玄奥，遗传算法还好一点，因为高中学过生物遗传，遗传算法还能理解一点。像模糊集理论神经网络便不知所云了。虽然金老师讲课生动形象，幽默风趣，而且举了好多实际的例子，但有一些理论有点偏难。
多关于ci的解释。
虽然有好多计算智能理论还不太清楚，但是我对新知识还是相当渴望的，因为我本身比较爱学习，且喜欢读书。我感觉学到了许多知识：计算智能是一门经验科学，它研究自然的或人工的智能行为形成之原理以“推理即计算”为基本假设，开发某种理论、说明某项智能可以算法化，从而可以用机器模拟和实现;寻求和接受自然智能之启迪，但不企图完全仿制人类智能，其中心工程目标是研究设计和建立智能计算系统的方法。
由于我们只有16课时，所以我们学的面并不广，金老师主要教了一些计算智能方面的经典理论，我们所学的计算智能所涉及的领域主要包括以下三方面：遗传算法、人工神经网络方法和模糊集理论。
遗传算法最早由美国michigan大学john h. holland教授提出，
按照生物进化过程中的自然选择(selection)、父代杂交(crossover)和子代变异(mutation)的自然进化(natural evolution)方式，编制的计算机程序，能够解决许多复杂的优化问题，这类新的优化方法称之为遗传算法(genetic algorithm，ga)[7]。ga模拟生物进化过程中的主要特征有：(1)生物个体的染色体(chromosomes)的结构特征，即基因码序列(series of genetic code)决定了该个体对其生存环境的适应能力。(2)自然选择在生物群体(population)进化过程中起着主导作用，它决定了群体中那些适应能力(adaptability)强的个体能够生存下来并传宗接代，体现了“优胜劣汰”的进化规律。(3)个体繁殖(杂交)是通过父代个体间交换基因材料来实现的，生成的子代个体的染色体特征可能与父代的相似，也可能与父代的有显著差异，从而有可能改变个体适应环境的能力。
(4)变异使子代个体的染色体有别于其父代个体的染色体，从而也改变了子代个体对其环境的适应能力。(5)生物的进化过程，从微观上看是生物个体的染色体特征不断改善的过程，从宏观上看则是生物个体的适应能力不断提高的过程。 作为利用自然选择和群体遗传机制进行高维非线性空间寻优的一类通用方法，遗传算法(ga)不一定能寻得最优(optimal)点，但是它可以找到更优(superior)点，这种思路与人类行为中成功的标志是相似的。例如不必要求某个围棋高手是最优的，要战胜对手只需他(她)比其对手更强即可。因此，ga可能会暂时停留在某些非最优点上，直到变异发生使它迁移到另一更优点上。遗传算法随编码
方式、遗传操作算子的不同而表现为不同形式，因此难以象传统的共轭梯度法那样从形式上给以明确定义，它的识别标志在于它是否具有模拟生物的自然选择和群体遗传机理这一内在特征。目前国内外普遍应用的实施方案是标准遗传算法(simple genetic algorithm，sga)。 bp神经网络 bp神经网络是用反向传播学习算法(back-propagation algorithm，bp算法)训练的一种多层前馈型非线性映射网络，网络中各神经元接受前一级的输入，并输出到下一级，网络中没有反馈联接。bp神经网络通常可以分为不同的层(级)，第j层的输入仅与第j–1层的输出联接。由于输入层节点和输出层节点可与外界相连，直接接受环境的影响，所以称为可见层，而其它中间层则称为隐层(hidden layer)。决定一个bp神经网络性质的要素有三个：网络结构、神经元作用函数和学习算法，对这三个要素的研究构成了丰富多彩的内容，尤其是后者被研究得最多。bp算法是目前应用最为广泛且较成功的一种算法，它解决了多层前馈网络的学习问题，从而使该网络在各方面获得了广泛应用。它利用梯度搜索技术(gradient search technique)使代价函数(cost function)最小化。 bp算法把一组样本的输入输出问题归纳为一非线性优化问题，它使用了最优化方法中最常用的负梯度下降算法。用迭代运算求解网络权重和阈值对应于网络的学习记忆过程，加入隐层节点使得优化问题的可调参数增加，从而可得到更精确的解。
模糊集理论
模糊集理论(又称模糊数学，fuzzy mathematics)就是应用模糊集这一模拟人脑模糊思维的数学工具，来描述、分析、识别、分类、判断、推理、决策和控制各种模糊事物所形成的一门现代应用数学分支学科。经典数学仅考虑现实世界的数量而抛弃现实世界的质量，而模糊集理论则反映了现实世界数量与质量的统一性，是对经典数学的一种补充和完善。定义模糊集、模糊关系的不同运算(目前主要是代数运算)，就可得到相应的不同模糊数学方法。目前已研究成熟并广为应用的模糊数学方法主要有模糊模式识别、模糊聚类分析、模糊综合评价、模糊推理、模糊控制等方法。在现代科学技术体系中定性因素和主观因素定量化处理的方法至今仍很少，而模糊数学方法正是其中的典型代表，目前已在各科学和工程领域得到了广泛的成功应用，其主要原因在于它异于其它方法的一些显著特点：(1)模糊集的引入改善了二值逻辑中硬性的分类方法，是普通集合的推广，使模糊数学方法更加接近于广泛存在模糊性和不精确性的现实世界，也更加接近于人类思维方式。这些真实性使得模糊数学方法能很好地平衡系统的复杂性与描述系统的精确性，也有助于模糊数学方法充分提取各种专家经验信息和其它人类语言信息。(2)当系统为多输入多输出、强非线性、定性信息与定量信息混杂的动态系统时，系统的数学模型非常复杂或根本就不存在确定性数学模型，常规方法难以或不能有效处理这样的复杂系统，而模糊数学方法可以用建立在语言型经验之上的模糊集及其运算就可以简便有效地处理，有时甚至不需要辅以确定的数学模型。(3)模糊数学方法可以直接利用人类语言型概念及其运算，篇四：遗传算法总结
遗传算法总结
遗传算法是借鉴生物的自然选择和遗传进化机制而开发出的一种全局自适应概率搜索算法。
一、遗传算法流程图
图1 遗传算法流程图
二、遗传算法的原理和方法 1) 染色体编码
把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法就称为编码。 de jong曾提出了两条操作性较强的实用编码原则：编码原则一：应使用能易于产生与所求问题相关的且具有低阶、短定义长度模式的编码方案;编码原则二：应使用能使问题得到自然表示或描述的具有最小编码字符集的编码方案。
编码方法主要有以下几种：二进制编码方法、格雷码编码方法、浮点数编码方法、符号编码方法、参数级联编码方法、多参数交叉编码方法。 2) 适应值计算
由解空间中某一点的目标函数值f(x)到搜索空间中对应个体的适应度函数值 fit(f(x))的转换方法基本上有一下三种： a. 直接以待解的目标函数值f(x)转化为适应度函数值fit(f(x))，令 ?f(x) 目标函数为最大化函数 fit(fx())= ? ??f(x)目标函数为最小化函数 ?cmax?f(x) f(x)?cmax b. 对于最小值的问题，做下列转化fit(f(x))??，其中cmax是 0 其他? f(x)的最大输入值。
c. 若目标函数为最小值问题，fit(f(x))? 1 , c?0, c?f(x)?0 1?c?f(x) 1 , c?0, c?f(x)?0 1?c?f(x) 若目标函数为最大值问题，fit(f(x))?3) 选择、交叉、变异
遗传算法使用选择算子来对群体中的个体进行优胜劣汰操作：根据每个个体的适应度值大小选择。适应度较高的个体被遗传到下一代群体中的概率较大;适应度较低的个体的被遗传到下一代群体中的概率较小。其中选择的方法有：轮盘赌选择、随机竞争选择、最佳保留选择、无回放随机选择、确定式选择等。
遗传算法中的所谓交叉运算，是指对两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体。交叉操作主要有单点交叉、两点交叉与多点交叉、均匀交叉和算数交叉四种。
遗传算法中的变异运算，是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其他基因来替换，从而形成一个新的个体。主要有基本位变异、均匀变异、边界变异等几种变异操作方法。 4) 控制参数选择
交叉概率pcpm
三、算例
min f(x1,x2)?(x1?3)2?(x2?2)2 2 ?g1(x1,x2)?x12?x2?5? s.t.?h1(x1,x2)?x1?2x2?4?0?x,x?10，x?n 121? (1) 1)三种不同的遗传方法
方法一：原模型中x
1、x2均为决策变量，操作如下。 a. 采用混合整数编码，对x1进行十进制编码，x2进行二进制编码; b. 适应度函数值采用fit(f(x1,x2))? 1 计算，其中 c?f(x1,x2) c???max{0,g1(x1,x2)?5}???max{0,|h1(x1,x2)?4|}，?=?=10000; c. 采用赌轮盘选择、单点交叉和基本位变异; d. pc=0.8，pm=0.1，遗传代数为200，种群中个体数100; e. 终止条件为连续十次最优个体保持不变或遗传代数到达200。 方法二：已知等式约束h1(x1,x2)，可得x2?(4?x1)/2，则原问题可化为 min f(x1)?(x1?3)2?(( 4?x1 )?2)22 (2) 4?x12?2 g(x)?x?()?5111? 2?s..t?0?x1?10，x1?n?4?x1?0??10 2? x min f(x1)?(x1?3)2?(1)2 2 即等式约束简化后的模型为 4?x12?2 g(x)?x?()?5?1 s..t?112??0?x1?4，x1?n 其中a~b的操作如下，而c~e的操作同方法一。 a. 对x1进行十进制编码; b. 适应度函数值采用fit(f(x1,x2))? (3) 1 计算，其中 c?f(x1,x2) c???max{0,g1(x1,x2)?5}，?=10000 方法三：在方法二的基础上，改变x1的编码方法，对x1进行二进制编码。由于0?x1?4，且为自然数，则二进制编码至少为3位，但3位的二进制可以表示0~7的整数，所以存在冗余编码。则通过惩罚来排除冗余编码，即适应度函数值采用 fit(f(x1,x2))? 1 计算。 c?f(x1,x2) 其中c???max{0,g1(x1,x2)?5}???max{0,x1(i)?4}，?=10000。x1(i)表示个体解码后的x1。
2)三种方法的计算结果
方法一可得到三个不同的解：
解1：x1?2,x2?1, fit(f(x1,x2))?0.4646, f(x)?2.0000，适应度趋势图如下： 图2 方法一解1的适应度趋势图
解2：x1?0,x2?2, fit(f(x1,x2))?0.1075, f(x)?9.0000，适应度趋势图如下： 篇五：遗传算法学习作业
遗传算法学习总结 1.1 概述 遗传算法是一类借鉴生物界的进化规律(适者生存，优胜劣汰遗传机制)演化而来的自适应概率性随机化迭代搜索算法。1962年霍兰德(holland)教授首次提出了ga算法的思想，它的基本思想是基于darwin进化论和mendel的遗传演说。darwin进化论最重要的是适者生存的原理，它认为每一代种群总是向着前进方向发展，越来越适应环境。每一个个体都有继承前代的特性，但不是完全继承，会产生一些新特性。最终只有适应环境的特征才能被保留下来。mendel遗传学说最重要的是基因遗传原理，它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。一条染色体中存在很多基因，每个基因有自己的位置并控制着外部特征;基因的产生和变异直接影响到个体的特性是否能适应环境。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。
遗传算法正是借用了仿真生物遗传学和自然选择机理，通过自然选择、遗传、变异等作用机制，实现各个个体的适应性的提高。
与自然界相似，遗传算法对求解问题的本身一无所知，从代表问题可能潜在解集的一个种群(population)开始，每一个种群则由经过基因(gene)编码(coding)的一定数目的个体 (individual)构成。每个个体实际上是染色体(chromosome)带有特征的实体。把问题的解表示成染色体，并基于适应值来选择染色体，遗传算法所需要的仅是对算法所产生的每个染色体进行评价，使适应性好的染色体有更多的繁殖机会。在算法中也就是以二进制编码的串。并且，在执行遗传算法之前，给出一群染色体，也就是假设解。然后，把这些假设解置于问题的“环境”中，也即在一个适应度函数中来评价。并按适者生存的原则，从中选择出较适应环境的染色体进行复制，淘汰低适应度的个体，再通过交叉，变异过程产生更适应环境的新一代染色体群。对这个新种群进行下一轮进化，直到最适合环境的值。 1.2遗传算法的基本原理和特点 1.2.1 算法原理
在遗传算法中，通过随机方式产生若干个所求解问题的数字编码，即染色体，形成初始种群;通过适应度函数给每个个体一个数值评价，淘汰低适应度的个体，选择高适应度的个体参加遗传操作，经过遗传操作后的个体集合形成下一代新的种群，再对这个新种群进行下一轮进化，这就是遗传算法的基本原理。
遗传算法的主要步骤如下： 1)随机产生一个由确定长度的特征串组成的初始群体; 2)对串群体迭代地执行步骤(1)和(2)，直到满足停止准则： (1)计算群体中每个个体的适应值。 (2)应用复制、杂交和变异算子产生下一代群体。 3)把在任一代中出现的最好的个体串指定为遗传算法的执行结果。这个结果可以表示问题的一个解(或近似解)。 基本遗传算法的流程图如图 1-1，其中gen是当前代数，m为每代种群中最大个体数。
图1-1 基本遗传算法的流程图 1.2.2 算法特点
遗传算法的特点如下： 1) 遗传算法中不包含待解决问题所持有的形态。它是从改变基因的配置来实现问题的整体优化的，因而属于自下而上的优化方法; 2) 类似于生物的进化过程，遗传算法处理的是变量集合的编码而非变量本身。它直接 对结构对象进行操作，不存在求导和函数连续性的限定; 3) 遗传算法具有内在的隐并行性和更好的全局寻优能力; 4) 遗传算法采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。
遗传算法的这些特点已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术之一。 1.3 基本遗传算法的步骤
1.3.1 染色体编码(chromosome coding)与解码(decode) 基本遗传算法使用固定长度的二进制符号串来表示群体中的个体，其等位基因由二值{0，1}所组成。初始群体中各个个体的基因可用均匀分布的随机数来生成。例如：x=100111001000101101就可表示一个个体，该个体的染色体长度是n=18。 (1)编码：变量x作为实数，可以视为遗传算法的表现型形式。从表现型到基因型的映射称为编码。设某一参数的取值范围为[u1，u2]，我们用长度为k的
二进制编码符号来表示该参数，则它总共产生2k种不同的编码，可使参数编码时的对应关系为：
000000?0000=0→u1 000000?0001=1→u1+? 000000?0010=2→u1+2? ? 111111?1111=2k-1→u2 u?u其中，?=2 k1。 2?1 (2)解码：假设某一个体的编码为bkbk-1bk-2?b2b1,则对应的解码公式为 x?u1?(?bi?2i?1)? i?1ku2?u1 ① k2?1 例如：设有参数x∈[2，4]，现用5位二进制编码对x进行编码，得25=32个二进制串(染色体)：
00000,00001,00010,00011,00100,00101,00110,00111 01000,01001,01010,01011,01100,01101,01110,01111 10000,10001,10010,10011,10100,10101,10110,10111 11000,11001,11010,11011,11100,11101,11110,11111 对于任一个二进制串，只要代入公式①，就可得到相应的解码，如x22=10101,它对应的十进制为?bi?2i?1=1+0*2+1*22+0*23+1*24=21,则对应参数 i?15 x的值为2+21*(4-2)/(25-1)=3.3548。 1.3.2 个体适应度的检测评估
基本遗传算法按与个体适应度成正比的概率来决定当前群体中各个个体遗传到下一代群体中的机会多少。为了正确估计这个概率，要求所有个体的适应度
必须为非负数。所以，根据不同种类的问题，需要预先确定好由目标函数值到个体适应度之间的转换规律，特别是要预先确定好当目标函数值为负数时的处理方法。例如，可选取一个适当大的正数c，使个体的适应度为目标函数值加上正数c。 1.3.3 遗传算子
基本遗传算法使用下列三种遗传算子：
(1)选择运算使用比例选择算子。比例选择因子是利用比例于各个个体适应度的概率决定其子孙的遗传可能性。若设种群数为m，个体i的适应度为fi,则个体i被选取的概率为 pi?fi/?fk k?1m 当个体选择的概率给定后，产生[0，1]之间的均匀随机数来决定哪个个体参加交配。若个体的选择概率大，则能被多次选中，它的遗传基因就会在种群中扩大;若个体的选择概率小，则被淘汰。
我们经常采用的是轮盘赌的原理，个体的选择概率是基于它们的性能进行的一些计算。实值范围——总和是所有个体期望的选择概率的总和或当前种群中所有个体原始适应度值的总和。个体采用一对一方式
映像到范围[0，sum]的一连续区间，每一个体区间的 大小与对应个体的适应度值相匹配。如图1所示，轮
盘赌轮的周长是6个个体适应度值的总和，个体5 是最大适应度个体，它占有最大的区间。选择一个个
体，用在[0，sum]间产生随机数，看此随机数在哪个
个体的区间上，则此个体被选中。重复此过程，直到
所需数量个体被选中为止。
(2)交叉运算使用单点交叉算子。只有一个交叉点位置，任意挑选经过选择操作后种群中两个个体作为交叉对象，随机产生一个交叉点位置，两个个体在交叉点位置互换部分基因码，形成两个子个体，如图2所示。
父个体1 父个体2 110 11 011 00 单点交叉 子个体1 子个体2 图2 单点交叉示意图
(3)变异运算使用基本位变异算子或均匀变异算子。为了避免问题 过早收敛，对于二进制的基因码组成的个体种群，实现基因码的小概率翻转，即0变为1，而1变为0，如图3所示。
变异
图3 变异操作示意图 1.3.4 基本遗传算法的运行参数 基本遗传算法有下列4个运行参数需要预先设定，即m,t,pc,pm。 m为群体大小，即群体中所含个体的数量，一般取为20~100; t为遗传算法的终止进化代数，一般取为100~500; pc为交叉概率，一般取为0.4~0.99; pm为变异概率，一般取为0.0001~0.1。 1.4遗传算法的应用 进入90年代后，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。尤其是遗传算法的应用研究显得格外活跃，不但它的应用领域扩大，而且利用遗传进行优化和规则学习的能力也显著提高，同时产业应用方面的研究也在摸索之中。
遗传算法提供了一种求解复杂系统问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于很多学科。如工程结构优化、计算数学、制造系统、航空航天、交通、计算机科学、通信、电子学、材料科学等。 1)ga在数值优化上的应用
最优化问题是遗传算法经典应用领域，但采用常规方法对于大规模、多峰态函数、含离散变量等问题的有效解决往往存在许多障碍。对全局变化问题，目前存在确定性和非确定性两类方法。前者以brianin的下降轨线法、levy的隧道法和r.ge的填充函数为代表。该类方法虽然收敛快、计算效率高，但算法复杂，求得全局极值的概率不大。 遗传算法作为现代最优化的手段，实践证明，它应用于大规模、多峰多态函数、含离散变量等情况下的全局优化问题是合适的，在求解速度和质量上远远超过常规方法。 2)ga 在组合优化中的应用
3)遗传算法在机器学习中的应用
遗传算法论文范文第2篇
一、问题描述
混合流水车间调度问题可以描述为:
一批n个工件需要经过c道工序进行加工, 已知工件j在第k道工序的加工时间为 (k, j) (k∈c, j∈n) , 同一阶段中所有机器都相同, 每个工件可以在某道加工工序中任意一台机器加工, 每台机器同一时间只能够加工一个工件, 工件在加工过程中不允许中断。为第k道工序的机器数量, 为工件j在第k道工序在机器i上的完工时间。
(1) 式表示工件j在阶段k的完工时间等于工件j紧前工序的完工时间或同一机器紧前工件j-1的完工时间中的最大值加上工件j在阶段k的加工时间。
因此目标函数可表示如下:, 此时工作效率最高。
二、遗传算法求解
由于混合流水车间调度问题具有离散性、多约束、多目标等特征, 因此本文采用多分组多目标遗传优化算法求解, 以便提高遗传算法求解速度。
(一) 数据编码与解码
数据编码方式采用工件编号随机排列方式, 数字大小代表待加工工件被加工优先等级, 数据编码顺序靠前, 优先处理, 当有空闲机器且满足加工条件时, 优先加工数据编码靠前工件。
解码规则是根据已知的数据编码顺序, 对所有工件的处理顺序进行安排, 假设有3个工件, 2道工序, 每道工序2台并行机加工, 各工件各工序加工时间为:
根据解码规则, 首先工件2在工序1中1号机器进行加工, 同时将工件1送至工序1中2号机器加工, 由于2号机器先完成, 故3号工件将由1道工序中2号机器加工, 以此类推, 求得该问题的最短完成时间为。
(二) 适应度函数
设适应度函数为:F=1/T, 则适应度越高, 则个体排序越接近最优解, 反之, 若适应度越低, 说明个体排序越差。
(三) 选择
设种群的总数为M, 个体i的适应度为, 适应度高的个体被选中进入下一代的概率较大, 反之同理, 那么个体i被选中的概率为:
(四) 交叉与变异
对于目标种群中的所有个体随机进行配对, 配对成功的两个个体作为父代进行交叉排序。其次, 在父代中随机生成两个不同点位, 作为变异基因, 子代继承父代交叉点位之间基因, 即变异基因, 其余基因依次按照父代未重复的父代基因顺序继承。
三、仿真实验
为验证算法准确可行性, 设本批次工件数量n=6, 每个工件需经过的工序数量c=3, 每道工序加工机器数量m=2, 每个工件在各阶段加工时间如图所示。在双交叉多分组遗传算法中, 设种群个数N=200, 交叉概率0.6, 变异概率0.05, 种群迭代次数G=100来模拟本题情况。图1为工件加工流程示意图;图2为遗传算法模拟加工过程, 迭代3次即找到最优解25。
仿真实验结果表明, 本文所采用的双交叉多分组遗传算法提高了工作效率, 算法收敛速度较快。
摘要：针对混合流水车间调度及离散优化、最优解问题, 提出基于遗传算法的改进优化算法, 由于二进制编码和浮点数编码会存在精度误差, 故而本算法使用符号编码进行求解, 对具有不同适应度值的分组个体采用不同交叉算法, 提高算法搜索能力, 并利用甘特图验证其可行性及有效性。
关键词：遗传算法,混合调度,符号编码,双交叉,最优解
参考文献
[1] 陈宁, 梁承姬.基于混合流水车间调度的自动化码头调度研究[J].计算机技术与发展, 2018 (04) :373-380.
[2] 张平华, 胡俊, 李敬明, 孙震.车间调度问题的遗传算法的求解研究[J].景德镇学院学报.2017 (03) :13-16.
[3] 田云娜, 李冬妮, 郑丹, 赵俊清.一种基于时间窗的多阶段混合流水车间调度方法[J].机械工程学报.2016 (16) :185-196.
[4] 陈通, 秦远辉, 万家宁, 王东军, 刘波.可重入柔性调度问题研究:模型、算法与应用[J].系统工程理论与实践.2015 (05) :1187-1201.
遗传算法论文范文第3篇
AGV的导航控制是AGV的核心技术, 而路径规划是AGV导航的重要环节之一。AGV的路径规划是按照某一性能指标搜索一条从起始状态到目标状态的最优或近似最优的无碰路径[3]。根据对环境信息知道程度的不同, 可分为环境信息完全知道的全局路径规划和环境信息完全未知或部分未知的局部路径规划及混合路径规划[4]。
传统的解决路径规划问题的方法有可视图法、自由空间法、人工势场法等[5,6]。随着智能方法的发展, 许多研究者把目光放在了基于智能方法的路径规划研究上。遗传 (算X1法-X是s) 2智+能 (Y1方-Y法s) 2的+一种 (, Xi它-具Xi-其1) 2不+ (要Yi-求Yi-1) 2适应度函数是可导或连续的、并行性、对问题的依赖程度小、在解空间进行高效启发式搜索等优点。本文以路径长短作为评判路径好坏的指标, 利用遗传算法对静态已知环境下的全局路径规划进行研究。
1 问题描述
在物流系统中应用AGV完成搬运任务, 任务中规定了AGV的起始点S, 和目标点E, 要求提前规划一条可行的无碰撞的路径, 且该条路径的总长度尽量短。该路径由起点、终点以及4个中间点Ai (0
本文就是在已知当前的物流系统布局情况和AGV小车的起始点和目标点坐标的条件下, 求解中间点的坐标, 使得路径尽量最短。
假设物流系统为一个平面仓库, 它的形状为长为18, 宽为18的矩形, 仓库的当前布局中, 存在三个矩形障碍物, 需要移动的物体起始位置为 (0, 0) , 终止位置为 (16, 16) 。
本文以路径长短作为评判路径好坏的指标, 故性能指标函数为:
基本的约束条件为:
2 环境建模
路径规划分为两个步骤, 第一步是环境建模, 第二步是求解路径。环境建模是求解路径的基础, 合理的环境表示有利于建立规划方法和选择合适的搜索算法, 最终实现较少的时间和内存开销而规划出较为满意的路径。在当前的研究中, 环境建模的方法有很多种, 如顶点法、栅格法、广义锥法、链路可视图法。
本文考虑二维空间, 采用的是直角坐标系对物流系统当前布局进行建模, 以平面仓库的一个顶点为起始点, 用 (x, y) 坐标对AGV在平面仓库中的位置进行定位, 同时把要移动的AGV等同与一个质点。
3 基于遗传算法的AGV路径规划
3.1 算法流程
遗传算法是一种基于自然选择和基因遗传学原理的优化搜索方法, 使得我们可以在计算机上模拟生物的进化过程和基因的操作。它一般包括初始种群的产 (X生E, -X交4) 2叉+, (Y变E-异Y4) 等2过程。本文的算法流程如图1所示。
3.2 初始种群的产生
本文采用典型的二进制编码方式, 这样的编码方式直接简洁。每个染色体是由4个中间点连接而成的, 其所表示的是一条可行或者不可行的路径。染色体的结构可表示为: (x1, y1) → (x2, y2) →……→ (x4, y4) 。其中, 染色体的长度是固定的, 每个中间节点由两个坐标, 每个坐标用一个4位二进制串表示, 则染色体的长度为32。通过随机函数产生初始化种群。
3.3 适应度函数的确定
路径规划, 就是要规划出一条最短的可行路径, 约束条件是路径不与障碍物碰撞。对路径优劣程度的评估就作为遗传算法中染色体的适应值。本文考虑简单的一种情况。只用路径的长短来判断路径的优劣程度。所以, 求适应度函数就是求线路的长度。另外还需判断可行路径和不可行路径, 不可行路径就是与障碍物的轮廓线有交点的路径。则适应度函数:Fitness=
显然, 适应度越小越好。
3.4 遗传算子的确定
选择算子, 采用轮盘赌选择法, 由上可知, 适应度越小被选择的概率越大。从种群中选出父体, 个体的数量保持不变。
交叉算子, 交叉是以一定的概率, 在父染色体中随机选择一个除起始点与目标点以外的转向点, 这个转向点就作为交叉点, 把整个路径分成了两个路径段。然后选择两个父代染色体, 相互交换交叉点后面的路径段, 这样就产生了两个子代染色体。在不同父代中选择不同的交叉点, 可以增加染色体长度的差异性, 并且有利于扩大解空间的范围和最优解的产生。
变异算子, 变异是以一定的概率, 除去起始点和目标点, 在路径的中间转向点中任意选取一个位置, 将该转向点的位置坐标作一次非一致性变异, 然后把当前的转向点移至新产生的转向点上, 经过变异之后就产生了一条新的路径。
然后, 把新的路径当作新的种群进行下一步的遗传操作, 依次循环往复。
4 仿真和实验结果
本文设计并实现了仿真实验, 实验的环境是visual studio2005软件开发平台, 用c#语言编写, 为一个窗体程序。如图2所示, 输入AGV的其实位置坐标和终止位置坐标, 点击“计算线路”按钮, 系统开始计算, 用红线画出每次迭代过程中计算得出的可行路径, 并用绿线表示最终计算的最优路径。
初始参数的设置为:种群的代数:500种群大小:500, 交叉概率:0.9, 变异概率:02。起点坐标为 (0, 0) , 终点坐标为 (16, 16) 运行以上代码, 得出结果如Fig.3 (b) 所示。中间点坐标中间点的坐标 (1, 2) , (2, 5) , (5, 7) (7, 6) , 最优路径长度为2 4.69。
5 结语
综合分析, 本文采用遗传算法解决了物流系统中单个AGV的路径规划问题。随机的产生初始种群, 在遗传算法的过程中考虑了选择算子, 交叉算子和变异算子。仿真实验也证实了该方法的有效性。合理的路径规划不但能够提高AGV的作业效率缩短单个作业的完成时间, 同时也能减少能耗, 从而提升整个物流系统的运作效率减少物流运作成本。
摘要：随着物流系统自动化、智能化水平的提高, AGV在物流系统的应用越来越普遍。AGV的导航是AGV的核心技术, 而路径规划是AGV导航的重要环节之一。本文应用遗传算法求解单个AGV的路径规划问题, 最后给出该算法实现的路径规划仿真和实验结果, 实验结果证实了该方法的有效性。
关键词：遗传算法,路径规划,AGV
参考文献
[1] 马幼捷, 张海涛, 邵保福, 等.电子智能化立体车库的研究现状与走向[J].电气自动化, 2008 (5) :3～6.
[2] 张辰贝西, 黄志球.自动导航车发展综述[J].中国制造业信息化, 2010 (1) :53～5 9.
[3] 范九荣, 应浩, 曾素娣.混合遗传算法的AGV路径规划的应用[J].科技信息, 2006 (8) :266～267.
[4] 王菁华, 崔世钢, 罗云林.基于Matlab的智能机器人路径规划仿真[C].2008系统仿真技术及应用学术会议论文集, 2008:298～301.
[5] L.Guibas, J.Hershberger.Computingthe visibility graph of n line segmentsin O (n2) time[J].Theoret Comput Sc., 1985, 26:13～20.
遗传算法论文范文第4篇
一、物流路径优化数学模型建立
假设在已知情况下, 送配送中心出发为用户配送货物, K最大车辆数, 汽车载重为Q (k) 汽车最大行使距离为kD顾客货物配送数量L, 顾客货物需求量iq配送点运送距离从i-j, 配送中心到各个分配点之间的距离, 第k条行使线路kn, 线路次序i, 车辆最优配送线路、最短配送路径计算式为:
物流路径优化要求:1.每条线路货物总配送量不得超过车辆最大载重量。2.顾客需求只能有一辆车提供服务。3.每条线路总距离不可超过车辆行驶距离上限值。
二、混合遗传算法建构
混合遗传算法主要是将模拟退火引入到遗传算法内, 并开展交叉操作, 不断优化遗传算法, 整合计算过程中的劣质解, 逐步提升混合遗传算法的求解效率。
(一) 算法流程
(1) 种群大小为n, 交叉概率使用cP表示, 变异概率使用mP表示, 初始温度为0T。 (2) 个体编码需要借助随机法开展, 计算个体的适应度。 (3) 选择个体开展操作。 (4) 个体交叉操作、模拟退火操作。 (5) 变异操作。 (6) 降温表达式:T=T0*θKθ代表的是数值之间的常熟, k代表代数。 (7) 判断个体进化代数, 达到代数G后则停止运算, 未达到则继续从步骤3重新计算。
(二) 算法构造
(1) 采取自然数编码, 包括:0、1、2、3、...N。 (2) 就其中的某个个体, 应当配备最佳的路径条数、总车辆数目之差 (M) , 适应值为 (Z) , 不可行路径的惩罚权重为∂, 物流配送路径适应度为F, 其代表式为:F=1/ (Z+M*∂) 。在算子选择过程中, 保留最佳个体。 (3) 模拟OX交叉算法, 合理应用交叉算子。 (4) 模拟退火算法, 交叉前为父代, 其表达方式为f1, f2, 交叉后为子代, 其表达式为c, 1c2,
父代与子代之间的适应度表达式为F (fi) , F (c i) , i=1, 2。接着开展退货操作模拟, 子代接收以概率exp (F (F (fi) -F (ci) ) /T) 为准, T代表的是温度。6.为确保群体内个体的多样化, 凸显出个体排列的多样化, 要采取连续多次变异方式。
三、真实案例应用
(一) 实验一
某配送中心需要为6名顾客提供配送服务, 物流中心只有2辆车, A车载重8t,
B车载重7t, 两车最大行使距离为60km, 计算出最短的配送距离。在本文实验中应用MATLAB 2017基础上开展程序编制, 群体规模设置45, 惩罚权重305km, 交叉率0.80, 变异率0.08, 代数为36。计算结果如下表1所示。
在实验一的10次求解中, 1、5、9的计算结果最佳, 为确保实验结果的精准性, 笔者对比标准遗传算法与混合遗传算法计算结果精准性, 最终结果显示, 混合遗传算法计算结果更优、效率更高。
(二) 实验二
以某物流中心为例, 配送30名顾客, 物流中心总计6辆车, 车辆最大载重量为8t, 最大行使距离为65km, 计算出最短的配送距离。在本实验求解过程中, 群体规模设置75, 惩罚权重605km, 交叉率0.85, 变异率0.08, 代数为36, 前后开展10次解, 如下表2所示。
由此可见, 采取混合遗传算法, 求解出来的10个解, 质量优良, 求解效果显著, 为保障后期应用效果, 本文在标准遗传算法基础上开展了1万次求解, 最终结果显示与混合遗传算法效率与质量优于标准遗传算法。
四、结束语
综上所述, 在本文研究中, 单一性的遗传算法应用优势不足, 想要解决其中的问题, 就必须要强化混合遗传算法的应用, 构建针对性的物流路径优化数学模型, 逐步强化混合遗传算法的局部搜索能力, 凸显出混合遗传算法在物流路径优化内的应用价值。
摘要：在当前时代背景下, 为改善物流配送路径问题, 必须要全面提升物流路径运算优化, 强化混合遗传算法的应用。本文首先从物流路径优化数学模型建立入手, 同时阐述了混合遗传算法构建, 最后总结了真实案例的应用。
关键词：混合遗传算法,物流路径,优化方法
参考文献
[1] 傅勉, 王世贵, 王丹丹.用混合遗传算法求解物流配送路径优化问题[J].西昌学院学报 (自然科学版) , 2018 (2) :56.
[2] 范文兵, 冯文.混合遗传算法的带时间窗卷烟物流车辆路径优化[J].现代电子技术, 2018, 41 (11) :119-123+128.
[3] 申艳光, 张玲玉, 刘永红.基于混合遗传算法的物流路径优化方法研究[J].计算机技术与发展, 2018 (3) :192-196.
遗传算法论文范文第5篇
Ad hoc网络是由一组带有无线收发装置的移动终端所组成的多跳的临时性自治系统。网络中所有的节点地位平等, 因而无需设置任何中心控制节点。每个节点兼有主机和路由器2种功能:作为主机, 终端上运行面向用户的应用程序;作为路由器, 终端上运行相应的路由协议, 具有路由和报文转发功能。网络中, 由于终端的无线传输范围有限, 2个无法直接通信的节点借助于若干个中间节点的转发来实现信息交互。因此, 它又被称为多跳无线网、自组织网络、无固定设施的网络或对等网络。一般情况下, 各节点的信号辐射半径被设置为相同的值, 且不可调节。这样处理较为简单, 生成的链路都是对称的, 对拓扑结构的控制通常是根据实际需要, 从图论的角度入手进行分析, 通过调节节点间相对距离来进行;缺点是形成的拓扑结构常常不合理, 浪费能量, 缩短了节点生命周期。目前已有将节点辐射半径视为可调节的网络拓扑结构控制方面的研究。本文提出了基于量子遗传算法的传感器网络拓扑结构控制解决方案。仿真实验表明量子遗传算法在求解性能上优于常规遗传算法, 可实现高连通性、低耗能的目标。
量子遗传算法的发展:
量子遗传算法是量子计算与遗传算法相结合的产物。目前, 这一领域的研究主要集中在两类棋型上:一类是基于量子
多宇宙特征的多宇宙量子衍生遗传算法 (Quantum Inspired Genetic Algorithm) , 另一类是基于量子比特和量子态登加特性的遗传量子算法ftl (Genetic Quantum Algorithm, GQA) 。前者的贡献在于将量子多宇宙的概念引入遗传算法, 利用多个宇宙的并行搜索, 增大搜索范围, 利用宇宙之间的联合交叉, 实现信息的交流, 从而整体上提高了算法的搜索效率。但算法中的多宇宙是通过分别产生多个种群获得的并没有利用量子态, 因而仍属于常规遗传算法.后者将量子的态矢量表达引入遗传编码, 利用量子旋转门实现染色体的演化, 实现了比常规遗传算法更好的效果.但该算法主要用来解决0-1背包问题.编码方案和t子旋转门的演化策略不具有通用性尤其是由于所有个体都朝一个目标演化, 如果没有交叉操作, 极有可能陷入局部最优。文献Yang Junan, ZhuangZhenquan.Research of Quantum Genetic Algorithm and Its Applicationin Blind Source Separation.对QGA进行了改进提出量子遗传算法 (Quantum GeneticA lgorithm, QGA) 。QGA采用多状态基因量子比特编码方式和通用的量子旋转门操作。引入动态调整旋转角机制和量子交叉, 比文献Han K-H.Genetic Quantum Algorithm and its Application to Combinatorial Optimization Problem的方法更具有通用性, 且效率更高, 但该方法仍是一个群体独自演化没有利用盈子信息的多宇宙和宇宙间的纠缠特性效率有待进一步提高。文献Yang Junan.Zhuang Zhenquan.MultiUniverse Parallel Quantum Genetic Algorithm and Its Application in Blind Source Separation提出一种多宇宙并行量子遗传算法 (MultiuniverseParallelQ uantum GeneticA lgorithm, MPQGA) , 算法中将所有的个体按照一定的拓扑结构分成一个个独立的子群体, 称为宇宙;采用多状态基因量子比特编码方式来表达宇宙中的个体;采用通用的量子旋转门策略和动态调整旋转角机制对个体进行演化;各宇宙独立演化, 这样可扩大搜索空间, 宇宙之间采用最佳移民、量子交叉和量子变异操作来交换信息使算法的适应性更强, 效率更高。
量子遗传算法流程
算法的具体流程如下:
一、初始化种群, 种群中全部染色体的基因都被初始化, 意味着一个染色体所表达的是其所有可能状态的等概率叠加。
二、对种群中的所有个体进行初次测量, 获得一组解。测量的步骤是生成一个[0, 1]之间的随机数, 若其大于概率幅的平方, 则测量结果值取1, 否则取0。然后对这一组解分别做适应度评估, 并记录下最佳适应度个体作为下一步演化的目标值。
三、算法进入循环。首先判断是否满足算法终止条件, 如果满足, 则程序运行结束;否则对种群中的个体实施一次测量, 获得一组解及其相应的适应度。
四、根据当前的演化目标, 运用量子旋转门进行调整更新, 获得子代种群。调整的过程为先测量个体, 并计算其适应度f, 然后与当前目标值的适应度fb进行比较, 根据比较结果调整个体中相应位量子比特。f
五、将父代种群中的最优解与当前的目标值进行比较, 取适应度高的个体作为下一次演化的目标值, 并返回3) 。
算法实现
算法实现采用面向对象的方法, 设计了3个实体类与一个操作类, 分别如下所述。界面类则由开发环境生成。
一、实体类。染色体 (chromosome) 类:每一个可行解就是一个染色体个体。所以染色体里面主要的数据成员是一个二维数组, 用来存放多量子比特编码。成员函数Observe () , 功能是对染色体进行测量, 以获得该染色体对应的解。群体 (population) 类:若干个染色体个体组成一个群体。其主要的成员函数有MakePt () 、StorBestSolution () 与Update () 。网络 (network) 类:每一个具体的传感器网络都是一个网络类的实例。主要的数据成员是节点位置信息矩阵, 是一个用来存储所有节点坐标值 (x, y) 的二维数组。
二、操作类。量子遗传算法 (quantum GA) 类:定义了用量子遗传算法来解决问题的全过程。主要的功能就是实现前述的算法流程。
结束语
遗传算法论文范文第6篇
在现代软件项目管理过程中, 软件估算是一项极具有挑战性的工作, 在众多的软件项目管理活动中, 占据着十分重要的地位。软件估算的准确程度对后续的开发计划和进度控制有决定性的影响, 甚至影响到软件项目的成败。在软件开发过程中不同的专家, 不同的项目, 不同的技术人员估算结果不尽相同。而在项目开始的早期阶段, 是进行准确可信估算的重要时期。传统的估算技术模型, 比如说“传统的线性回归模型和形式技术”, 其处理定性指标能力不足, 只能使用类比法或者专家经验法, 参照以前的数据进行估算;与此同时, 这些模型还不能处理当确切数据未知而一般常识已知的情况。
目前在软件估算方面已经研究了很多的方法, 比如说, COCOMO等数学方式的软件估算模型, 需要利用历史数据对其中的因子参数进行校正调整;基于类比的估算是对新项目和历史项目进行比较, 以此找出和新项目特征最匹配的历史项目, 进而对新项目进行估算。在已有的研究中, 遗传算法和模糊决策树算法都有运用在软件估算中的研究, 但两者的结合较少。
决策树技术是一种以实例为基础的归纳学习算法, 其所形成的决策树形象易于理解, 而且把模糊逻辑技术对不精确、不确定信息的处理能力融合于其中对其进行优化, 形成模糊决策树, 再利用遗传算法的优化, 从而进一步得出最好的结果数据, 把遗传算法和模糊决策树法结合的算法应用于软件过程, 引历史数据进行归纳学习, 可高效地形成能够反映软件开发本质的决策树, 进而对新的软件项目进行估算, 最后可产生解释性更强的估算结果。
决策树的典型算法中, C4.5算法排名第一, C4.5算法是机器学习算法中的一种分类决策树算法, 其核心算法是ID3算法, 决策树示意图如图1所示。
ID3算法是一种著名的决策树算法, 该算法是以信息论为基础, 以信息熵和信息增益度为衡量标准, 以自顶向下递归划分训练样本的方式来构造决策树。在构造决策树过程中, 每个节点上判定属性的选择标准是最大信息增益。
模糊决策数树是模糊逻辑和决策树算法相结合的产物, 基于ID3算法的模糊决策树是模糊逻辑和ID3算法相结合的产物。模糊逻辑是源于模糊集合论的一种近似推理型的多值逻辑, 是基于模糊集合理论上对经典逻辑的延伸。对于模糊决策树的使用, 同经典决策树一样, 分为两个步骤:第一步使用历史数据对模糊决策树算法进行训练, 产生能够描述特定数据集内在规律的本地化模糊决策树;第二步使用上步所形成的模糊决策树对新样本的目标属性进行预测。遗传算法的基本思想是从初始种群出发, 采用优胜劣汰、适者生存的自然法则选择个体, 并通过杂交、变异来产生新一代种群, 如此逐代进化, 直到满足目标为止[1]。
基于决策树的软件项目估算方法首先需要根据已有的基准数据建立决策树。软件项目估算决策树的叶节点是目标项目的预测属性, 中间节点是软件项目估算活动中可以收集的项目属性。软件项目属性通常包括开发周期、开发团队规模、开发团队的能力成熟度水平、业务类型、应用类型、基础设施平台、开发工作量等[2]。
基于遗传算法的模糊决策树的软件估算研究大体上可分为以下几个步骤:
1) 数据预处理。
收集整理历史项目数据, 由于实际项目中缺失数据和噪音数据的存在, 需要我们在处理数据时补充和剔除, 同一个数据集中标致方法有多种, 在建模前需要对这些不同的表达方式进行一致化, 得到统一、清晰的数据表示。历史数据经过模糊化处理后作为模糊决策树的输入数据。
2) 构建决策树模型。
使用ID3算法的模糊决策树算法构建模糊决策树, 然后用遗传算法优化模糊决策树的α、β两个参数 (这两个参数的选择目前需要经验, 也是我们后续研究的方向) , 构建软件估算模型后为我们新项目估算提供依据。
3) 新项目估算。
估算新项目的过程, 就是决策推理和去模糊化的过程。在这个过程中我们要处理好叶节点, 还应考虑估算结果如果表示。
4) 改进与评估。
基于遗传算法的模糊决策树的软件估算研究其目的是提高软件可靠性, 对于软件的可靠性评价主要采用定量评价方法, 即选择合适的可靠性度量因子 (可靠性参数) , 然后分析可靠性数据而得到参数具体值, 最后进行评价, 我们可以使用平均相对误差来进行评价。
按照以上步骤, 我们将以目前正准备开发的实习实训管理系统为实例, 建立估算模型, 形成评价体系, 提高软件可靠性。
摘要：本文以软件估算为核心, 运用模糊决策树和遗传算法, 设计估算步骤, 建立评估模型, 利用历史数据对其中的因子参数进行校正调整, 基于ID3算法的模糊决策树, 确定遗传算法优化模糊决策树的α、β两个参数, 进而对新项目进行估算, 对提高软件可靠性提供了有效方法, 值得参考。
关键词：模糊决策树,遗传算法,软件估算
参考文献
[1] 张朝杰.一种基于模糊决策树的软件工作量估算方法[D].国防科学技术大学, 2010.
[2] 阎魏.基于决策树的软件工作量估算方法[J].计算机工程与科学, 2009 (08) .