本科毕业论文-基于遗传算法的测试用例生成方法【精品毕业设计】(完整版)

软件测试中基于遗传算法的测试用例生成研究在软件开发过程中，测试是确保软件质量的重要环节之一。

在测试过程中，测试用例的生成是关键步骤之一，且在测试用例的生成过程中，覆盖率是评估测试用例质量的重要指标之一。

然而，在软件复杂度不断提高的背景下，传统的手工测试用例生成方法已经难以满足迅猛发展的软件行业对测试效率和测试质量的需求。

因此，基于遗传算法的测试用例生成方法应运而生。

遗传算法是模拟生物进化过程的一种优化算法，其核心思想是通过模拟自然选择和遗传机制，不断迭代生成更优解。

在测试用例生成中，可以将测试用例看作遗传算法中的个体，目标函数可以是代码的覆盖率等指标。

基于遗传算法的测试用例生成方法可以根据具体的测试目标和抽象的遗传算法的框架，生成更加高效和优质的测试用例。

基于遗传算法的测试用例生成方法主要包含以下几个步骤。

第一步是测试用例的表达和编码。

将测试用例表示为遗传算法中的个体，通常采用一种编码方式，如二进制编码。

根据具体测试任务和被测系统的特点，将测试用例的输入和操作转化为遗传算法可以处理的编码形式。

第二步是适应度函数的定义。

适应度函数是遗传算法中非常重要的一个概念，用于评价个体的适应程度。

在测试用例生成中，适应度函数可以根据测试目标来定义。

例如，在代码覆盖率的角度考虑，可以定义适应度函数为被测系统中被测试到的代码行数的比例。

第三步是选择操作。

在遗传算法中，选择操作是根据适应度函数的值来选择优秀个体的过程。

在测试用例生成中，选择操作旨在选择那些具有较高适应度值的测试用例，以保留其优秀性状。

第四步是交叉操作。

交叉操作是遗传算法中的进化过程，通过交换个体的某些部分以产生新的个体。

在测试用例生成中，交叉操作可以根据测试用例的编码方式来定义。

例如，对于二进制编码的测试用例，可以通过交换部分二进制位来生成新的测试用例。

第五步是变异操作。

变异操作是遗传算法中的一种随机变动操作，用于保持种群的多样性。

在测试用例生成中，变异操作可以根据具体的测试需求来定义。

设计题目：_____基于遗传算法的TSP问题研究_ 学院：_______计算机与信息学院 __ _____毕业设计（论文）原创性声明和使用授权说明原创性声明本人郑重承诺：所呈交的毕业设计（论文），是我个人在指导教师的指导下进行的研究工作及取得的成果。

尽我所知，除文中特别加以标注和致谢的地方外，不包含其他人或组织已经发表或公布过的研究成果，也不包含我为获得及其它教育机构的学位或学历而使用过的材料。

对本研究提供过帮助和做出过贡献的个人或集体，均已在文中作了明确的说明并表示了谢意。

作者签名：日期：指导教师签名：日期：使用授权说明本人完全了解大学关于收集、保存、使用毕业设计（论文）的规定，即：按照学校要求提交毕业设计（论文）的印刷本和电子版本；学校有权保存毕业设计（论文）的印刷本和电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部分或全部内容。

作者签名：日期：学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。

除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。

对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。

本人完全意识到本声明的法律后果由本人承担。

作者签名：日期：年月日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。

本人授权大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。

涉密论文按学校规定处理。

作者签名：日期：年月日导师签名：日期：年月日目录摘要 (I)Abstract (II)第1章绪论 ............................................................. - 1 -1.1旅行商问题........................................................ - 1 -1.2研究意义 ......................................................... - 1 -1.3 论文的组织结构................................................... - 1 - 第2章遗传算法理论概述.................................................. - 2 -2.1遗传算法的起源和发展.............................................. - 2 -2.2遗传算法基本原理.................................................. - 3 -2.3遗传算法的基本步骤................................................ - 4 -2.4 遗传算法的流程图................................................. - 4 -2.5遗传算法的特点.................................................... - 5 -2.6遗传算法的应用.................................................... - 6 - 第3章 TSP问题及研究的基本方法.......................................... - 8 -3.1 TSP问题概述...................................................... - 8 -3.2 TSP的应用与价值.................................................. - 8 -3.3 TSP问题的数学模型................................................ - 9 -3.4 TSP 问题的分类................................................... - 9 -3.5 现有的求解TSP问题的几种算法 .....................................- 10 - 第4章遗传算法在TSP的应用..............................................- 12 -4.1遗传算法在TSP上的应用............................................- 12 -4.2算法的实现........................................................- 12 -4.3编码 .............................................................- 12 -4.4初始化种群........................................................- 13 -4.5适应度函数........................................................- 13 -4.6选择操作 .........................................................- 13 -4.7交叉操作 .........................................................- 15 -4.8变异操作 .........................................................- 17 -4.9实验结果 .........................................................- 18 - 结论 ..................................................................- 20 - 展望 ....................................................................- 20 - 参考文献 .............................................................- 21 - 致谢 ..................................................................- 22 - 附录程序 ................................................................- 23 -摘要TSP问题(Traveling Salesman Problem)是已知有n个城市，现有一推销员必须遍访这n 个城市，且每个城市只能访问一次，最后又必须返回出发城市。

基本遗传算法【精品毕业设计】（完整版）遗传算法1、遗传算法⽣物学基础和基本理论达尔⽂⾃然选择学说认为，⽣物要⽣存下去，就必须进⾏⽣存⽃争。

⽣存⽃争包括种内⽃争、种间⽃争以及⽣物跟⽆机环境之间的⽃争三个⽅⾯。

在⽣存⽃争中，具有有利变异(mutation)的个体容易存活下来，并且有更多的机会将有利变异传给后代;具有不利变异的个体就容易被淘汰，产⽣后代的机会也少得多。

因此，凡是在⽣存⽃争中获胜的个体都是对环境适应性⽐较强的。

达尔⽂把这种在⽣存⽃争中适者⽣存，不适者淘汰的过程叫做⾃然选择。

达尔⽂的⾃然选择学说表明，遗传和变异是决定⽣物进化的内在因素。

遗传是指⽗代与⼦代之间，在性状上存在的相似现象。

变异是指⽗代与⼦代之间，以及⼦代的个体之间，在性状上或多或少地存在的差异现象。

在⽣物体内，遗传和变异的关系⼗分密切。

⼀个⽣物体的遗传性状往往会发⽣变异，⽽变异的性状有的可以遗传。

遗传能使⽣物的性状不断地传送给后代，因此保持了物种的特性，变异能够使⽣物的性状发⽣改变，从⽽适应新的环境⽽不断地向前发展。

⽣物的各项⽣命活动都有它的物质基础，⽣物的遗传与变异也是这样。

根据现代细胞学和遗传学的研究得知，遗传物质的主要载体是染⾊体(chromsome),染⾊体主要是由DNA(脱氧核糖核酸)和蛋⽩质组成，其中DNA⼜是最主要的遗传物质。

现代分⼦⽔平的遗传学的研究⼜进⼀步证明，基因(gene)是有遗传效应的⽚段，它储存着遗传信息，可以准确地复制，也能够发⽣突变，并可通过控制蛋⽩质的合成⽽控制⽣物的性状。

⽣物体⾃⾝通过对基因的复制(reproduction)和交叉(crossover)，即基因分离、基因⾃由组合和基因连锁互换)的操作使其性状的遗传得到选择和控制。

同时，通过基因重组、基因变异和染⾊体在结构和数⽬上的变异产⽣丰富多采的变异现象。

需要指出的是，根据达尔⽂进化论，多种多样的⽣物之所以能够适应环境⽽得以⽣存进化，是和上述的遗传和变异⽣命现象分不开的。

基于遗传算法的优化设计论文[5篇]第一篇：基于遗传算法的优化设计论文1数学模型的建立影响抄板落料特性的主要因素有:抄板的几何尺寸a和b、圆筒半径Ｒ、圆筒的转速n、抄板安装角β以及折弯抄板间的夹角θ等［4，9］。

在不同的参数a、β、θ下，抄板的安装会出现如图1所示的情况。

图1描述了不同参数组合下抄板的落料特性横截面示意图。

其中，图1(a)与图1(b)、图1(c)、图1(d)的区别在于其安装角为钝角。

当安装角不为钝角且OB与OC的夹角σ不小于OD与OC夹角ψ时(即σ≥ψ)，会出现图1(b)所示的安装情况;当σ＜ψ时，又会出现图1(c)与图1(d)所示的情况，而两者区别在于，η+θ是否超过180°，若不超过，则为图1(c)情况，反之则为图1(d)情况。

其中，点A为抄板上物料表面与筒壁的接触点或为物料表面与抄板横向长度b边的交点;点B为抄板的顶点;点C为抄板折弯点;点D为抄板边与筒壁的交点;点E为OB连线与圆筒内壁面的交点;点F为OC连线与圆筒内壁面的交点。

1．1动力学休止角(γ)［4，10］抄板上的物料表面在初始状态时保持稳定，直到物料表面与水平面的夹角大于物料的休止角(最大稳定角)时才发生落料情况。

随着转筒的转动，抄板上物料的坡度会一直发生改变。

当物料的坡度大于最大稳定角时，物料开始掉落。

此时，由于物料的下落，物料表面重新达到最大稳定角开始停止掉落。

然而，抄板一直随着转筒转动，使得抄板内物料的坡度一直发生改变，物料坡度又超过最大休止角。

这个过程一直持续到抄板转动到一定位置(即抄板位置处于最大落料角δL时)，此时抄板内的物料落空。

通常，在计算抄板持有量时，会采用动力学休止角来作为物料发生掉落的依据，即抄板内的物料坡度超过γ时，物料开始掉落。

该角主要与抄板在滚筒中的位置δ、动摩擦因数μ和弗劳德数Fr等有关。

1．2抄板持有量的计算随着抄板的转动，一般可以将落料过程划分为3部分(Ｒ－1，Ｒ－2，Ｒ－3)，如图1(a)所示。

利用遗传算法进行数据流分析下的测试用例自动生成摘要：软件测试越来越受到重视，但是软件测试是一个复杂、工作量很大的过程。

测试用例的自动生成在一定程度上能够减小软件测试的工作量，但是测试用例自动生成技术是一个难点。

本文通过借鉴遗传算法，基于数据流分析，在def-use路径覆盖的测试准则上，提出了一个测试用例自动生成的算法。

并通过实验比较了遗传算法和随机选择法在测试用例自动生成上的优劣。

关键词：软件测试；数据流测试；遗传算法；GA；测试用例自动生成中图分类号：TP311Automatic Test Data Generation for Data Flow Testing Usinga Genetic AlgorithmAbstract: Software testing is more and more important, but the software testing is plex and has heavy workload. The automatic generation of test cases can reduce the workload of software testing, but the automatic generation of test cases is a difficult problem. This paper introduces an automatic test case generation algorithm which uses genetic algorithm and is based on data flow analysis and is under the test criterion of the def-use path coverage. And pares the advantages and disadvantages between genetic algorithm and random selection method in the automatic generation of test cases.Key words:software testing; data flow testing; genetic algorithms;automatic test data generation1 引言软件测试描述一种用来促进鉴定软件的正确性、完整性和质量的过程，是一种实际输出与预期输出间的比较过程。

基于遗传算法的测试用例生成技术宋倩【摘要】在计算机软件的生命周期中，由于各种各样的原因，留给软件测试的时间往往不够执行全面而充分的测试。

覆盖率和数量作为测试用例质量的主要影响因子，一直受到人们的关注。

然而测试用例的执行顺序作为影响测试效率的重要因素，却一直未引起足够的重视。

提出了一种基于遗传算法的测试用例生成技术，综合考虑覆盖率、数量和用例的执行顺序三个因子，生成高效的测试用例集。

使测试人员能够按照既定的顺序执行用例集，在最短的时间内，完成最重要的软件功能测试。

%In the actual life cycle of software, due to various reasons, the time that spending on software testing is often not enough to perform the comprehensive test. Coverage ratio and the number of test cases as the main quality factors, have been payed more attention to. However, the execution order of test case as one of the important factors that affect test efficiency, has not caused enough attention. This paper presents a test case generation technology based on genetic algorithm, which considering Coverage ratio, the number of test cases and the execution order. Testing personnel can execute test case in the established order and accomplish the most important software function test in the time as shorter as possible according to the method referred in this paper.【期刊名称】《计算机系统应用》【年(卷),期】2014(000)011【总页数】4页(P264-267)【关键词】软件测试;覆盖率;遗传算法;用例执行顺序;用例生成技术【作者】宋倩【作者单位】江苏自动化研究所，连云港 222006【正文语种】中文随着计算机技术的普及以及在一些重要领域的应用，软件测试逐渐受到重视，但在实际的产品生命周期中，由于各种各样的原因，留给软件测试的时间往往不够执行全面而充分的测试. 高覆盖率和低数量的测试用例可以有效地减少测试时间，提高测试效率，如何设计高效的测试用例，使得软件测试工作在有限的时间内执行最充分的测试是现阶段软件测试工作的难点[1]. 本文综合考虑了测试用例的覆盖率、数量以及执行顺序三方面的因素，采用遗传算法，对相关算子和运行参数进行改进，利用遗传算法的特点设计了一种新的测试用例生成模型，以达到进一步提高测试效率的目的.1 基于遗传算法的测试用例生成1.1 测试用例生成模型本文将遗传算法用作核心算法来进行测试用例自动生成的研究，首先要建立测试用例自动生成模型，并对影响求解效率的相关算子进行研究设计. 围绕遗传算法的主要设计思想为: 根据相关被测软件的文档确定被测软件的运行状态因素的初始化状态可用编码;对各状态之间的转换所需时间进行代价估算; 种群规模确定; 适应度函数选择.具体应用到测试用例的自动生成按照以下步骤进行:1) 分析被测软件的需求规格说明，提取其所有的输入数据和工作条件;2) 将输入数据按照等价类划分的方法进行分类，并将工作条件按照枚举的方法列出;3) 根据输入和工作条件确定软件的初始工作状态;4) 计算初始种群中每一条染色的适应度值，从而确定种群的优劣度;运用初始的测试用例集合执行遗传操作，获得相应的适应度值，如果遗传代数达到要求，则转向步骤7)，否则转向步骤6);的评价、运算，引导种群向目标值靠近，找到最终合适的解或者达到预期限定的迭代次数; 测试仿真运行环境，对种群的优劣进行评价，返回一个适应度值供核心算法包使用[2].1.2 模型算子设计1.2.1 染色体编码方案和初始种群构造根据种群的优劣度，执行改进后的遗传算法包，生成新的测试用例集合，并转向步骤5);运行结束，输出合适的测试用例.根据上述步骤，将遗传算法的测试用例自动生成模型分为三部分: 测试环境的构造，根据对软件相关文档和具体软件执行情况的分析，确定一个稳定的被测试软件的初始运行状态; 遗传算法包，按照前面步骤生成初始的种群，通过对种群中的染色体进行反复遗传算法的编码方法可以分为三大类: 最小字符集编码方法、浮点数编码方法、符号编码方法. 本文选择用最小字符集编码方法[3].1.2.2 适应度函数设计假设某系统软件各状态之间的切换代价表如表2所示. 一条染色体基因序列为 i 的编码为(0，0，0，0，0，0，0，0)，基因序列为 i+1 的编码为(1，1，1，1，1，1，1，1)，按照表1 中所列时间代价值i 和i+1之间进行切换的时间值为:Ti=t1+ t2+ t31+ t4+ t5+ t6+t71+ t81. 则该染色体的适度函数值为:表1 时间代价表工作模式系统时间运行状态系统当前坐标当前方位目标距离目标属性目标种类时间代价t1 t2 0-1 0-2 1-2 0-1 0-2 0-3 1-2 1-3 2-3 0-1 0-2 1-2 t4 t5 t6 t31 t32 t33 t71 t72 t73 t74 t75 t76 t81 t82 t83其中n 为一条染色体的基因数量.1.2.3 遗传操作算子设计1)选择采用适应度比例和最佳个体保存相结合的方法进行选择: ①根据式(1)计算各个个体的适应度比例值将适应度比例值最高的个体保存到缓冲区中; ②根据选择概率Ps 选择的个体进入交配池作为待交叉的个体. 其中， Ps 为种群规模N 的倒数; ③设P(t+1)为经过交叉和变异操作形成的新种群，用缓冲区中的个体和子代种群P(t+1)中的个体一一进行比较. 若存在相同的，则选择操作结束. 若不存在则转入下一步.④用缓冲区中的个体去替代种群P(t+1)中适应度函数值最低的个体，构成新的规模为N 的群体P(t+1).2)交叉为了保证交叉操作的正确性，对染色体中存在互为逆序基因的个体进行交叉，把互为逆序的基因对在进行交叉的个体中进行互换. 假设染色体i 的基因数量为6，父体P1 和P2 中存在互为逆序的基因. P1 和P2 的交叉过程如图1 所示.3)变异图1 交叉操作示意图依据个体编码表示方法的不同，采用逆转变异算子. 具体操作步骤如下: ①产生一组随机数，随机数的数目为种群规模的0.1 倍，随机数的范围为[0， N-1](N 为种群规模)，随机数的值即为产生变异的个体编号. ②对于每一个被选中的个体，随机地选取两个基因座的位置i， j 然后将i， j 之间的基因进行逆转. 变异的操作过程如图2 所示.图2 变异过程示意图1.2.4 运行参数设计1)种群大小N将群体规模设计成一个公式(2)所示的分段函数， n为全部软件状态的逻辑组合数. 文中软件的n=2*2*3*2*2*2*4*3=1152，其中N＜n!.2)选择概率选择概率为适应度比例的平均值，高于平均值的个体进入交配池，保证每次都有个体被选中，同时被选中的个体不至于很多[4].3)交叉概率本文摒弃交叉概率的概念，设计一种符合具体情况的交叉规则，将交配池中的个体放入一个二维数组中，设此二维数组一共有n 行，则行下标之和等于n 的两行进行交叉操作.4)变异概率本文的变异概率Pm 也是由一组随机数决定的，首先根据种群的规模N 产生个范围在闭区间[0，N-1]中的随机数置于数组a 中，组范围在[0， n-1]中的随机数置于数组b 中. 其中a[0]=k， b[0]={i，j}，且i＜j，表示要进行变异的第一条染色体为当前群体中下标为k 的染色体，变异部分为编号为i 和j 之间的所有基因，随后将基因编号i 和j 之间的所有基因逆序排列.1.2.5 算法终止条件由于实际应用遗传算法时不允许让其无停止地进行搜索，同时问题的最优解也通常未知，因此必须设计一些近似收敛准则来终止算法进程[4]. 即给定一个最大进化步数为终止条件，如公式(3)所示，这里最大进化步数和种群的初始规模是相等的.2 实验与分析本文采用算法模型生成测试用例，在覆盖率相同的情况下，对比传统测试过程的时间代价和基于遗传算法生成的测试用例的时间代价，验证生成的测试用例是否提高了测试效率.传统测试过程的时间代价取经验值的平均值，单位为人分，即当1 人执行该测试过程时，执行完该测试所需的分钟数. 为兼顾实验的普遍性，分别选取了软件状态因素为6、10、20、50、100 和1000 时进行实验分析. 两者的时间代价对比结果如表2 所示，当软件状态因素越多时，基于遗传算法生成的测试用例在执行过程中节省的时间代价越明显.表2 时间代价对比表6 10 20 50 100 1000传统测试 8134 42144 90678 114689 389076 5876442基于遗传算法生成的用例 7818 39848 80074 98769 289048 3979889时间代价缩减 316(3.9%) 2296(5.4%) 10604(11.7%) 15920(13.9%) 100028(25.7%) 1896553(32.3%)3 结语本文从提高测试效率的角度提出一种基于遗传算法的测试用例生成模型，并对相关算子和算法运行参数进行设计. 与传统的测试用例生成算法相比，本文的算法不仅在保证覆盖率的前提下使生成的测试用例数量尽可能地少，而且兼顾到优化测试用例的执行顺序，从而进一步缩短测试执行过程的时间，提高测试效率.参考文献【相关文献】1 李欣.基于贝叶斯网络和遗传算法的测试用例生成模型[硕士学位论文].重庆:重庆交通大学，2012.2 刘瑞. 基于改进PSO 算法的测试用例生成方法研究[硕士学位论文].郑州:河南大学，2011.3 费雯悦.基于改进遗传算法的测试用例自动生成及质量评价研究[硕士学位论文].北京:北京化工大学，2012.4 李柱.用于测试用例生成的遗传算法改进[硕士学位论文].成都:西南大学，2011.。

学校代码 10126 学号 00708037 分类号密级本科毕业论文基于遗传算法的图像阈值分割学院、系数学科学学院计算数学系专业名称信息与计算科学年级 2007级学生姓名刘家祥指导教师曹军2011年 5月 20 日内容摘要图像分割就是指把图像分成各具特性的区域并提取出感兴趣目标的技术和过程。

图像的分割是以灰度值作为分割的依据,通过各个像素的灰度值和事先确定的阈值的比较来分割图像。

如何确定最合适的阈值是处理好图像分割的关键,这自然成为一直以来分割算法研究的焦点。

遗传算法是对生物进化论中自然选择和遗传学机理中生物进化过程的模拟来计算最优解的方法。

遗传算法具有众多的优点,如鲁棒性、并行性、自适应性和快速收敛,可以应用在图像处理技术领域中图像分割技术来确定分割阈值。

本文主要介绍基于遗传算法的最小误差阈值法、最大类间方差法（Otsu法）以及最佳直方图熵法(KSW熵法)等三种方法分割图像。

关键词：图像分割，遗传算法，阈值分割AbstractImage segmentation refers to the image into regions each with characteristics and goals of the technology to extract and process of interest. Segmentation is a segmentation based on gray value, gray value of each pixel through the predetermined threshold value and comparing the image segmentation. How to determine the most appropriate threshold is the key to handling image segmentation, which has naturally become the focus of segmentation algorithms.Genetic algorithm is a biological theory of evolution and genetic mechanism of natural selection in biological evolution simulation method to calculate the optimal solution. Genetic algorithm has many advantages, such as robustness, parallel, adaptive, and fast convergence, can be used in the field of image processing image segmentation technique to determine the split threshold.In this paper, genetic algorithm based on minimum error threshold, the largest class variance (Otsu method) and the best histogram entropy (KSW entropy method) are three ways to split the image.Keywords : Image segmentation, genetic algorithms, threshold目录第一章绪论 .................................................. - 1 - 第二章遗传算法概述 ........................................ . - 2 -2.1遗传算法的研究历史....................................... - 2 -2.2生物背景................................................. - 2 -2.3遗传算法的基本思想....................................... - 3 -2.4遗传算法的几个概念....................................... - 4 -2.4.1适应度函数......................................... - 4 -2.4.2遗传算法最常用的算子............................... - 4 -2.5遗传算法运算的基本流程................................... - 5 - 第三章图像分割的现状 ........................................ - 7 -3.1图像分割简介............................................. - 7 -3.2图像分割方法............................................. - 8 -3.2.1基于边缘检测的分割................................. - 8 -3.2.2基于区域的分割..................................... - 8 -3.2.3边缘与区域相结合的分割............................. - 9 -3.3阈值选取................................................. - 9 - 第四章基于遗传算法的图像阈值分割 ........................... - 10 -4.1图像阈值................................................ - 10 -4.2阈值分割的原理.......................................... - 10 -4.3最小误差阈值法.......................................... - 11 -4.3.1最小误差法图像阈值分割............................ - 11 -4.3.2 利用遗传算法来改进最小误差法...................... - 12 -4.4 最大类间方差法（Otsu法）............................... - 13 -4.4.1最大类间方差法（Otsu法）阈值分割.................. - 13 -4.4.2 Otsu阈值分割的遗传算法设计........................ - 15 -4.5 KSW熵法................................................ - 17 -4.5.1 KSW熵阈值分割................................... - 17 -4.5.2 KSW单阈值分割的遗传算法设计..................... - 18 -4.5.3 KSW双阈值分割的遗传算法设计..................... - 19 - 第五章基于新的遗传算法的图像分割 ........................... - 25 -5.1混沌遗传算法............................................ - 25 -5.2量子遗传算法............................................ - 25 -5.3免疫遗传算法............................................ - 25 - 结论 .......................................................... - 26 - 致谢 .......................................................... - 27 - 参考文献: ..................................................... - 28 -内蒙古大学本科学年论文第- 1 - 页基于遗传算法的图像阈值分割第一章绪论图像分割是图像处理与计算机视觉的基本问题之一，是图像处理到图像分析的关键步骤。

基于自适应遗传算法的软件测试用例自动生成李柱【摘要】在软件测试中,测试成功的关键是快速、高效的生成测试用例.遗传算法是一种通过模拟自然界生物进化过程搜寻最优解的一种算法,算法通过选择、交叉和变异操作引导算法搜索方向,逐步接近全局最优解.传统遗传算法由于具有较好的全局搜索能力,因此被很多科研人员应用于测试用例生成.但遗传算法的固有缺陷"早熟收敛",容易导致算法收敛于局部最优.针对这种情况.提出一种自适应遗传算法,该算法交叉算子和变异算子可根据程序变化自动调整,随后,将改进后的算法应用于一程序的测试用例生成中.测试结果表明该算法在测试用例生成的效率和效果方面优于传统搜索算法和普通改进算法.【期刊名称】《计算机系统应用》【年(卷),期】2016(025)001【总页数】5页(P192-196)【关键词】自适应遗传算法;自适应交叉算子;自适应变异算子;测试用例生成【作者】李柱【作者单位】重庆交通大学,重庆400074【正文语种】中文随着计算机的普及和发展,各类软件和程序迅猛发展,人们对软件的需求和要求越来越高,造成软件规模和复杂度大幅增加,从而给软件测试带来了巨大困难.因此,如何有效快速的实现软件的测试就变得十分必要.遗传算法是一种模拟自然界生物进化过程寻求最优解的一种算法.因为遗传算法具有较好的全局搜索能力和较高的运转效率,近年来,一些研究人员尝试将遗传算法作为软件测试用例生成算法.上海交通大学姚尧在其论文“一种基于遗传算法的软件测试用例生成新方法”中构造了一种遗传算法生成测试用例模型,将遗传算法与软件测试用例生成有机结合起来,提高了测试用例生成的效率;王者思等3人提出了软件程序中的评价函数构造及插装方法,进一步遗传算法应用于测试用例生成提供了依据.然而,遗传算法存在的“早熟收敛”[1]缺陷,极易造成算法收敛于局部最优解,而无法得到全局最优解(若是用于测试用例生成,则为理想的测试用例).本文对通过对遗传算法交叉算子和变异算子的改进,使算法搜索方向可以根据适应度纸的变化进行自动调整,可在一定程度上克服传统遗传算法全局搜索能力差、效率低下的问题.将改进后算法应用到程序测试用例生成及优化中,实验结果表明该算法在生成效率方面比传统搜索优化算法和非自适应的遗传算法改进方法更优. 2.1 传统遗传算法遗传算法是一种模拟生物进化过程[2],通过指导种群进化方向得到最优种群的过程.遗传算法中种群是由一系列染色体组成,染色体是由一组数字表示,该组数字中的每一位成为基因,遗传算法就是通过基因的变化来指导种群的进化方向.传统遗传算法描述[3]如下:(1)根据问题需求,将产生第一代种群.(2)计算种群中个体的适应度值(适应度函数应根据问题需求产生).(3)根据问题需求设置迭代次数和适应度阈值,若迭代次数低于设定值或该种群中最高适应度值低于设定值,进入循环操作:①产生子代种群,然后进行遗传算子(选择算子、交叉算子和变异算子)操作②计算新种群的适应度值.(4)当新种群染色体适应度值或迭代次数达到设定值,停止算法.2.2 基于遗传算法生成测试用例的系统模型为方便说明遗传算法如何生成测试用例,文中给出该模型[4](图1).从图中可以看出算法分两个部分:算法执行部分和评价部分:①执行部分:初始化种群,对染色体进行编码,此时被测试的程序接收参数并运行评价部分;算法执行部分根据评价部分参数适应度值的高低进行遗传算子操作,产生子代种群,循环往复,直至覆盖路径的目标参数值被发现.②评价部分:在被测程序中插入评价函数,实现对参数的评价.该模型的重点就是将遗传算法与软件测试用例生成有机结合起来,关键是在被测程序中插入被测评价函数,形成对测试用例(被测程序)的评价体系,利用评价函数(插桩程序)形成遗传算法适应度函数,完成对被测程序的适应性评价.该模型存在的主要问题是在算法运行后期,由于遗传算法的早熟收敛的存在,容易导致算法收敛于局部最优解,无法得到全局最优解(理想的测试用例).本文提出的自适应遗传算法就是在算法的后期,通过对交叉算子和变异算子的自适应设计,自动调整算法前进方向,从而得到全局最优解.遗传算子是模拟自然界自然选择、杂交和基因突变等操作保证种群多样性而进行的,包括:选择、交叉和变异,用以指导算法的前进方向.传统遗传算法(又称基本遗传算法)和非自适应遗传算法遗传算子设计介绍如下.3.1 传统遗传算法遗传算子设计3.1.1选择算子的设计选择算子是根据自然界“优胜劣汰”理论总结得出的,是遗传算法中起着重要的作用,选择就是将种群中的优秀(适应度高)个体保留下来,遗传到下一代;适应度低的个体被保留下来的几率较低.常用的个体选择方法有:最优保存策略、排序选择、随机联赛选择和轮盘赌选择,本文采用轮盘赌选择法.轮盘赌选择法[5]是一种常用的随机选择法,又称比例选择法,个体被选中的概率与其适应度值(亦称优秀程度)的大小成正比.假若M为种群大小,iF为第i个个体的适应度,那么个体i被选中的概率表示为:通过观察上面的式子可以发现,个体适应度越低,选中它的几率就越小,反之,就越大.3.1.2交叉算子的设计基因的重新组合是自然界生物进化的核心流程,因此,交叉算子也就成为遗传算法的核心算子.交叉就是对父代染色体中的部门基因互相替换重组,然后产生两个不同的新染色体,产生下一代.这样极大的增加了染色体的多样性,为遗传算法产生最优解,提供了充分的样本.传统遗传算法采用的交叉方式为单点交叉:单点交叉[6](又称简单交叉),是指在染色体位串中随机设置一交叉点,将本染色体交叉点右侧的部分与另一染色体同一交叉点右侧部分进行交换,左侧部分保持不变,从而行成两个新的染色体位串.3.1.3变异算子的设计在算法的后期,种群的适应度高度接近,通过交叉已不能有效改变种群的多样性,此时,变异算子就变的尤其重要.所谓变异是指改变群体中个体串上的某些基因位上的基因值,正式由于变异算子的存在,算法后期才可以顺利地朝最优解靠近,收敛加速.通过交叉算子和变异算子的有效结合,遗传算法在全局和局部空间都具有良好的搜索能力.传统遗传算法采用的是基本位变异.基本位变异算子[7]就是指随机指定个体基因串的某几个基因(大于等于1的整数)以变异概率pm进行变换.对于二进制编码个体,若基因值为 1,则变为0;若基因值为0,则变为1.3.2 非自适应遗传算法生成测试用例3.2.1选择算子设计此处采用的选择算子与传统遗传算法相同.3.2.2交叉算子的设计在遗传算法进化了一段时间后,群体往往会向搜索空间中包含较优解的区域收敛,这时群体中会存在较多相同的染色体,而传统的交叉算子在两个染色体相同时将失效,从而降低了算法的搜索能力,容易形成“早熟”.为解决这一问题,我们在前面讨论的基础上给出自交叉算子这一新算子,其操作步骤如下:(1)设染色体X被选中参与交叉,则生成该染色体的伴随染色体Y,染色体Y的每一位都与X不同;(2)染色体X和Y利用一般的一点交叉算子进行交叉运算,生成新染色体X´和Y´;(3)任取新染色体X´和Y´中的一个取代原染色体X.3.2.3变异算子的设计此处,非自适应遗传算法采用的变异方式为均匀变异[7].均匀变异是一种以较小概率,用某范围内的随机产生的均匀分布的数来替换个体编码串中被选中的基因.例如:其中mk为变异点,其所在范围为那么在此变异点进行均匀变异后得到的新个体为:其中,r为随机数,满足[0,1]范围内的均匀概率分布.在整个搜索空间,均匀变异使搜索点可以自由移动,使得种群多样性增加,快速的向算法最优解靠近.本文所述自适应遗传算法,就是通过对交叉算子和变异算子的设计,使其根据程序变化自动调整两种算子的大小,尽量使得算法跳出局部最优解找到全局最优解的一种算法.4.1 适应度函数的构造适应度函数的构造是遗传算法能够得到全局最优解的关键,本文采用TRACEY提出的“分支函数插桩法”[8]得到适应度函数形式为:其中,fi为插入在被测程序中的实值函数(实值函数插桩方法,将在下文予以说明).F 为所有实值函数fi的连加形式:亦即4.2 遗传算子的选择与改进4.2.1选择算子的设计选择算子的设计,本文采用Whitley、Kuo等专家提出的一种非单调适应值标度变换方法[9].设群体数量为n的群体其中各个个体适应值分别为为平均适应度值.该适应值的非单调标度变换设置为:其中值越大,个体适应值偏离fave的染色体具更容易被选择.4.2.2 自适应交叉算子和变异算子设计为避免遗传算法“早熟收敛”缺陷,本文提出自适应交叉算子(pc)和自适应变异算子(pm)概念,采用适应度均值fave、最大适应度fmax、最小适应度fmin三个参数表示种群适应度的集中与否.pc和pm的调整方式如下:①当fmin与fmax的值越接近说明遗传算法限于“早熟收敛”的可能性越高.在此处,我们设定一参数时,视为种群较为集中.b值越小,表明集中程度越高.②设定参数a(0.5<a<1),当时,认为种群集中.a接近0.5,判断为“集中”的可能性越高.③当且时,认为种群“集中”,使pc和pm随着种群的集中程度的变化而自适应改变;否则,认为种群“分散”,此时,保持和pm初始阶段较小值.④其中设定是为确保交叉和变异概率小于1.本文参数设定a=0.78,b=0.24.为验证该算法在测试用例生成方面的时效性,本文通过下列程序段对被测程序分支函数和适应度函数构造、程序插桩过程[10]予以说明,:void main(int input)// L1(表明为程序的第一行){ int i; // L2for(i=0;i<N;i++) // L3if(a[i]<0) // L4break; // L5if(i<N) // L6{ a[i]=input; // L7return True; // L8} // L9else // L10return false; // L11} // L12本文通过Eclipse7 环境下采用java语言编程.上述程序共12行,分为2条路径:“L1-L3,L6,L10,L11,L12”和“L1-L3,L4,L5,L6-L9,L12”.其中路径“L1-L3,L6,L10,L11,L12”包含三个分支语句:L4,L6,L10,在该三条语句前插桩分支函数f.根据Tracy“分支函数插桩”的要求,L3语句运算符是“<”,要保证该语句为真,则分支函数fi的值须为零,f1=i-N;L4为f2=a[i]-0;L6为F3=i-N;因此,适应度函数构造为三个分支函数相加的形式,即:F=f1+f2+f3(fi的值要根据分支判断的真假来选取).上述程序段分支函数插桩及评价函数具体情况如下:表1中的数据是在程序段中插入桩程序,i为循环次数,a[i]为设定的程序运行次数,然后根据i和a[i]的取值计算出桩程序的取值,为求适应度函数值(评价函数)做准备.在算法执行部分中只要F的值为零;各变量取值就可满足测试路径L1-L3,L4,L5,L6-L10,L12.取值见下表(设定N=6,i和a[i]的值任意):表1中f1和f3值为负,因此由程序f1和f3的值应为零.此时,若F=0,满足测试路径,系统可以很快生成该实例上的测试用例,且拥有良好的收敛性.在图2中将本文设计的基于自适应遗传算法的生成测试用例的方法与传统搜索优化算法生成测试用例的方法、非自适应遗传算法生成测试用例方法[11]在时间效率进行对比,可以看出,随着被测程序分支数增加,本文提出的算法在时延上表现为线性增加,而传统搜索优化算法则表现为指数增加的趋势;相比非自适应遗传算法生成测试用例,自适应遗传算法生成测试用例虽在初始阶段表现不够优秀,但随着分支数的增加,自适应遗传算法在时间效率上仍具有明显的优势,收敛性更优秀[12].本文对传统遗传算法交叉算子和变异算子方面进行了改进,并将改进后的算法应用于一测试用例生成实例.通过本文研究发现,自适应交叉和变异算子可以较好地指导算法前进的方向,并可在一定程度上避免算法限于“早熟收敛”,提高了测试用例生成的效率,效果明显优于传统搜索算法和非自适应改进型遗传算法.当然我们也可以看到被测程序函数插桩是手工完成,一旦程序复杂性过高,会带来极大不便,如何有效实现程序自动插桩是下一步急需解决的问题.【相关文献】1 付旭辉,康玲.遗传算法的早熟问题探究.华中科技大学学报(自然科学版),2003,31(1):53-55.2 陈有青,徐蔡星,钟文亮,等.一种改进选择算子的遗传算法.计算机工程与应用,2008,44(2):44-45.3 李敏强,寇纪淞,林丹等.遗传算法的基本原理及应用.北京:科学出版社,2002.4 姚尧.一种基于遗传算法的软件测试用例生成新方法.计算机与数字工程,2009,37(1):18-21.5 夏佳梅,曾建潮.一种基于轮盘赌选择遗传算法的随机微粒群算法.计算机工程与科学,2007,26(9):51-53.6 Holland JH.Adaptation in Nature and Artificial Systems.MIT Press,1992.7 李延梅.一种改进的遗传算法及应用[硕士学位论文].广州:华南理工大学,2012.8 Tracey N,Clark J,Mander K.The way forward for unifying test case generation:The optimization-based approach.International Workshop on Dependable Computing and its Applications.Johannesburg,South Africa.1998.169-180.9 Kuo T,Hwang S.A genetic algorithm with disruptive selection,IEEE Trans.on Systems,Man and Cybernetics Cybernetics Part B:Cybernetics,1996,26(2):65-69.10 李柱,丁晓明.用于测试用例生成的遗传算法改进.科学技术与工程,2011,11(5):990-991.11 荚伟,高仲仪.用遗传算法实现软件结构测试数据的自动生成.计算机与数字工程,1996.24(1):7-13.12 梁艳春,王在申,周春光.选择和变异操作下遗传算法的收敛性研究.计算机研究与发展,1998,35(7):657-662.。

基于遗传算法的自动化测试用例生成研究随着软件开发的发展，自动化测试在软件质量保证中的重要性日益凸显。

传统的手工测试无法满足快速迭代和高质量要求，而自动化测试则可以更快、更准确地发现软件中的问题。

然而，自动化测试的一个重要挑战是如何生成高效且全面的测试用例，以覆盖软件的各个功能和路径。

为了克服这个挑战，一种被广泛应用的方法是利用遗传算法来生成测试用例。

遗传算法是一种模拟自然选择和遗传机制的优化算法，它可以通过对测试用例进行适应度评估和演化，自动地搜索出最优的测试用例解决方案。

首先，基于遗传算法的自动化测试用例生成需要一个适应度函数来评估每个测试用例的质量。

适应度函数可以根据测试用例的覆盖率、错误检测率等指标来进行评估。

通过分析代码的结构和逻辑，可以设计出一系列判断条件，用于判断测试用例是否符合预期行为。

然后，利用遗传算法的搜索过程可以自动地演化出更好的测试用例。

首先，需要初始化一个种群，其中包含多个初始测试用例。

然后，通过交叉、变异和选择等遗传操作，不断迭代地生成新的测试用例。

交叉操作可以将两个测试用例的某些部分进行组合，生成具有不同特征的新测试用例。

变异操作可以对测试用例进行随机改变，引入新的测试情况。

选择操作则根据适应度函数对测试用例进行筛选，选择出适应度更高的个体参与下一轮遗传操作。

在遗传算法的迭代过程中，可以采用一些启发式搜索策略，以加速测试用例的生成过程。

例如，可以选择性地引入一些启发式规则，根据已有的测试用例和代码的结构特点，通过优先考虑代码关键路径等方式来指导遗传算法的搜索方向。

此外，针对自动化测试用例生成的研究还可以结合其他技术，进一步提高测试用例的质量和效率。

例如，可以结合模型检测、符号执行等技术，扩大测试空间和增强测试用例的覆盖率。

还可以利用机器学习算法，对已有的测试用例和代码特征进行学习，从而进一步优化遗传算法的搜索过程。

最后，基于遗传算法的自动化测试用例生成不仅可以应用于单个软件的测试，还可以用于多个软件的兼容性测试。

基于遗传算法的测试用例自动生成及其改进方法胡文欢;钱越英【期刊名称】《计算机与现代化》【年(卷),期】2012(000)001【摘要】遗传算法是一种通用的自适应搜索算法.它给测试用例自动生成问题带来了新的解决思路.但是传统的遗传算法应用于测试用例自动生成,重组、突变的随机性容易使种群中多样性遭到破坏,使得算法搜索空间减小,从而导致算法错误地收敛到局部最优值.而且盲目的随机重组和突变又使得搜索的效率非常低.本文介绍一种改进方法,引进突变控制策略和优化解控制策略,可有效提高遗传算法的搜索能力和获取最优解的性能.%Genetic algorithm is currently an adaptive searching algorithm which gives a new solution to generate test cases. However, when it is used to generate test cases, the randomness of recombination and mutation makes the diversity of the population easily destroyed and leads to the search space getting smaller, finally results in the algorithm finding a wrong local optimum. Moreover, recombining and mutating freely makes the searching efficiency very low. This paper introduces an improved method, with a mutation control strategy and an optimal control strategy added, which effectively improves the searching capability and gets optimal solution capability of the algorithm.【总页数】4页(P49-52)【作者】胡文欢;钱越英【作者单位】北京应用气象研究所,北京100029;北京应用气象研究所,北京100029【正文语种】中文【中图分类】TP301.6【相关文献】1.基于遗传算法的软件测试用例自动生成研究 [J], 刘东旭;吴昊2.基于遗传算法与XML的测试用例自动生成执行系统研究与实现 [J], 刘慰;应新洋3.基于特征模型和遗传算法的测试用例自动生成 [J], 江志强; 王金波; 王晓华4.基于遗传算法的测试用例自动生成方法综述 [J], 赫彦文;刘紫阳;李建义;彭新宇5.基于混沌遗传算法的测试用例自动生成研究 [J], 黄陈辉;吴海涛;阮江涛;钱程因版权原因，仅展示原文概要，查看原文内容请购买。

论文名称：遗传算法姓名：***学号：***********班级：计算机科学与技术1班院系：信息与电气工程学院日期：2014年6月18日摘要 (2)第一章引言 (3)1．1搜索法 (3)1.2遗传算法 (3)第二章遗传算法(Genetic Algorithms，GA) (4)2.1遗传算法的基本概念 (4)2.2遗传算法的实现步骤 (6)第三章遗传算法的特点及应用 (9)3.1遗传算法的特点 (9)3.2遗传算法的应用 (9)第四章遗传算法的缺点及发展 (12)4.1遗传算法的缺点 (12)第五章遗传算法代码实现 (13)附录遗传算法代码（GA Code） (14)摘要智能搜索算法包括遗传算法、禁忌算法、模拟退火算法等。

其中遗传算法（GA）是人类从基因遗传的生物进化思想的启发下提出的，它是一种进化计算，进化计算实质上是自适应的机器学习方法，遗传算法根据基因遗传时候的变化，它在运算的时候也分为选择、交叉、变异三种行为。

它比盲目的搜索效率高的多，又比专门的针对特定问题的算法通用性强，它是一种于问题无关的求解模式。

但是遗传算法又有很大的不确定性，以及过早的收敛性，所以可以和其他算法一起使用来对问题求解。

关键词：遗传算法；GA；实现；应用；改进第一章引言1．1搜索法人工智能问题广义地说，都可以看作是一个问题求解问题，在问题的求解过程中，人们所面临的大多数现实问题往往没有确定性的算法，通常需要用搜索算法来解决。

搜索法是人工智能中问题的求解的基本方法，搜索法可大致分为有信息搜索和无信息搜索，约束满足问题和博弈问题的求解均可表述为搜索过程。

搜索法的本质是再状态空间中从问题的初始状态搜索到通向目标状态的路径。

当前的智能搜索算法本质上也是搜索法，如遗传算法、蚁群算法、神经网络等。

一般搜索可以根据是否使用启发式信息分为盲目搜素和启发式搜索，也可以根据问题的表示方式分为状态空间搜索和与/或树搜索。

盲目搜索一般是指从当前状态到目标状态需要走多少步或者并不知道每条路径的花费，所能做的只是可以区分出哪个是目标状态。

本科毕业论文-基于遗传算法的测试用例生成方法摘要软件测试是保证软件质量和可靠性重要手段，在这方面发挥着其它方法不可替代的作用。

然而，软件测试是一个复杂的过程，需要耗费巨大的人力、物力和时间，约占整个软件开发成本的40%～50%。

因此，提高软件测试工具的自动化程度对于确保软件开发质量、降低软件开发成本非常重要。

而提高测试用例生成的自动化程度又是提高测试工具乃至整个测试过程自动化程度的关键所在，本文主要针对这一问题进行了研究和设计。

本文在分析软件测试和遗传算法基本概念的基础上，提出软件测试用例的设计是软件测试的难点之一。

论文提出了基于遗传算法的测试用例生成的内含是应用遗传算法来求解一组优化的测试用例，其框架包括了测试环境构造、遗传算法及测试运行环境三部分，论文给出了基于遗传算法的测试用例生成的模型。

最后以三角形分类程序为例应用遗传算法进行测试用例生成的模拟，结果显示，应用遗传算法进行测试用例生成可行。

关键词：软件测试测试用例遗传算法ABSTRACTSoftware test is the important means that guarantee software quality and reliability，and in this respect，it plays the role that other method cannot replace. However software test is a complex process , it needs to consume huge manpower，material resources and time，which takes the 40%~50% of entire software development cost approximately . Therefore，raising the automation level of software test tool is very important for ensure software development quality and reduction software development cost . And then，the most important is raising the automation level of thetest case generation for raising the automation level of test tool and even entire test process，so this paper study and design mainly according to this problem.Based on the analysis of basic concepts of software testing and genetic algorithm, this article proposes that software test case design is one of the difficulties of software testing. Paper presents the inherent in software test case designing based on genetic algorithm is using genetic algorithm to solve a set of optimization test cases, and the framework includes three parts which are test environment construction, genetic algorithm and the environment for test . Paper presentsthe model of software test case generation based on genetic algorithm. Finally, we take the triangle categorizer as an example, simulate software test case generation based on genetic algorithm. The results display that software test case generation basing on genetic algorithm is possible.KEY WORDS: software test , test case , genetic algorithm目录摘要 (2)ABSTRACT (3)目录 (5)第一章绪论 (8)1.1 问题的提出 (8)1.2 国内外研究现状 (9)1.3 论文研究内容 (11)第二章软件测试及遗传算法基本概念 (12)2.1 软件测试基本概念 (12)2.1.1 软件测试的目的 (12)2.1.2 软件测试的原则 (12)2.2 软件测试的难点 (13)2.3 遗传算法 (14)2.3.1 遗传算法的思想及流程 (14)2.3.2 遗传算法的特点 (16)2.4本章小结 (17)第三章基于遗传算法的测试用例生成 (18)3.1基于遗传算法的测试用例生成基本内涵 (18)3.1.1 软件测试用例的基本内涵 (18)3.1.2 基于遗传算法的测试用例生成的基本内涵 (19)3.2 基于遗传算法的测试用例生成框架 (19)3.3 基于遗传算法的测试用例生成算法实现 (21)3.3.1 编码策略 (21)3.3.2 适应度函数及程序插桩 (22)3.3.3 遗传策略 (23)3.3.4 参数控制 (25)3.4 本章小结 (25)第四章实验及结果分析 (26)4.1 待测程序分析 (26)4.1.1 待测程序引入 (26)4.1.2 程序流程分析 (27)4.1.3 路径分析 (27)4.2 程序插桩 (28)4.3 参数设定及程序实现 (29)4.3.1 参数设定 (29)4.3.2 部分程序实现 (29)4.4 结果分析 (35)4.5 本章小结 (37)第五章总结与展望 (38)致谢语 (39)参考文献 (40)第一章绪论1.1 问题的提出在信息化普及的今天，计算机在人们的生活和工作中占据着重要地位，使人们的工作效率提高，也使生活更丰富多彩。

目录1 引言 (1)2 问题描述 (2)3 基于遗传算法TSP算法 (2)3.1 基于遗传算法的TSP算法总体框架 (2)3.2算法的详细设计 (3)3.2.1 解空间的表示方式 (3)3.2.2 种群初始化 (4)3.2.3适应度函数 (4)3.2.4选择操作 (4)3.2.5交叉操作 (5)3.2.6变异操作 (6)3.2.7进化逆转操作 (6)3.3 实验结果分析 (7)4 基于模拟退火算法的TSP算法 (10)4.1 SA算法的实现过程 (10)4.2 算法流程图 (10)4.3模拟退火算法的实现过程 (10)4.4实验结果 (11)5 对两种算法的评价 (14)5.1遗传算法优缺点 (14)5.2 模拟退火算法的优缺点 (15)6结语 (15)参考文献 (17)附录： ............................................................................................................ 错误！未定义书签。

廊坊师范学院本科生毕业论文论文题目：基于遗传算法与模拟退火算法的TSP算法求解10大城市最短旅途论文摘要：TSP问题为组合优化中的经典的NP完全问题.本论文以某旅行社为中国十大旅游城市--珠海、西安、杭州、拉萨、北京、丽江、昆明、成都、洛阳、威海制定最短旅途为例，分别利用基于遗传算法的TSP算法与基于模拟退火算法的TSP算法求解10大城市旅游路线问题.本论文给出了遗传算法与模拟退火算法中各算子的实现方法，并展示出求解系统的结构和求解系统基于MATLAB的实现机制．利用MATLAB软件编程，运行出结果，并对基于遗传算法的TSP算法结果与基于模拟退火算法的TSP算法的结果进行比较，描述其优缺点，并选择最为恰当的TSP算法，实现最短旅途的最优解.关键词：遗传算法；模拟退火算法；TSP；最短路径；Title：TSP Algorithm Based on Genetic Algorithm or Simulated Annealing Algorithm for Solving the Shortest Journey of 10 CitiesAbstract：TSP problem is a classic NP problem about combinatorial optimization．This article takes a travel agency looking for the shortesttrip of ten tourist cities in China－Zhuhai，Xi'an，Hangzhou，Lhasa，Beijing，Lijiang，Kunming，Chengdu，Luoyang and Weihai forinstance，and solves this problem by TSP algorithm based on geneticalgorithm and simulated annealing algorithm．The article gives theimplementations of every operator of genetic algorithm and simulatedannealing algorithm and demonstrates the architecture and theimplementation mechanism of the solving system based on MATLAB．Iprogram and operate the results by MATLAB software，and compare theresults based on genetic algorithm and simulated annealingalgorithm．And describe their advantages and disadvantages so thatchoose the most appropriate TSP algorithm to achieve the optimalsolution for the shortest path．Keywords：genetic algorithm；simulated annealing algorithm；TSP；the shortest path1 引言TSP问题为组合优化中的经典问题，已经证明为一NP完全问题[1]，即其最坏情况下的时间复杂性随着问题规模的扩大，按指数方式增长[2]，到目前为止不能找到一个多项式时间的有效算法.TSP问题可描述为:已知n个城市相互之间的距离，某一旅行商从某个城市出发访问每个城市一次且仅一次，最后回到出发城市，如何安排才使其所走路线最短.TSP问题不仅仅是一个简单的组合优化问题，其他许多的NP完全问题可以归结为TSP问题，如邮路问题、装配线上的螺帽问题和产品的生产安排问题等，使得TSP问题的有效求解具有重要的意义.本文中的TSP算法主要采用遗传算法与模拟退火算法．遗传算法是一种进化算法，其基本原理是仿效生物界中的“物竞天择，适者生存”的演化法则[3]．遗传算法把问题参数编码为染色体，再按照所选择的适应度函数，利用迭代的方式进行选择、交叉、变异以及进化逆转等运算对个体进行筛选和进化，使适应值大的个体被保留，适应值小的个体被淘汰[4]，新的群体继承了上一代的信息，又优于上一代，这样反复循环，直至满足条件，最后留下来的个体集中分布在最优解的周围，筛选出最优个体作为问题的解．模拟退火算法的出发点是基于物理中固体物质的退火过程与一般的组合优化问题之间的相似性[5]，该算法是一种优化算法，其物理退火过程由三部分组成，分别为：加温过程、等温过程、冷却过程．其中，加温过程对应算法设定初温，等温过程对应算法的Metropolis[6]抽样过程，冷却过程对应控制参数的下降．这里能量的变化就是目标函数，要得到的最优解就是能量最低态[7]．Metropolis准则是SA算法收敛于全局最优解的关键所在，Metropolis 准则以一定的概率接受恶化解，这样就使算法跳离局部最优的陷阱．2 问题描述本案例为某旅行社为中国十大旅游城市，分别为珠海、西安、杭州、拉萨、北京、丽江、昆明、成都、洛阳、威海，根据全程路径最短为目的，制定最优的旅游顺序依次游玩这十个城市.这类问题就由TSP算法来解决，寻找出一条最短遍历这10个城市的路径.利用google地图找到城市坐标，下表为这十个城市的位置坐标如表2-1所示.表2-1 10个城市的位置坐标3 基于遗传算法TSP算法3.1 基于遗传算法的TSP算法总体框架TSP问题的遗传算法包括编码设计、种群初始化、适应度函数选择、终止条件设定、选择操作设定、交叉操作设定以及变异操作设定和进化逆转操作.为简化TSP问题的求解，假设每个城市和其它任意一个城市之间都以欧氏距离[8]直接相连.遗传算法TSP问题的流程图如图2-1所示.。

自然计算大作业一．二进制编码在遗传算法中，首先要将数据进行编码，这里采用二进制的方式进行编码。

第一步，我们根据题目的介绍可以得知该函数含有两个变量，以及各自的定义域。

在二进制编码中，我们首先要先计算它的编码长度。

计算公式如下: $${2^{{m_j} - 1}} < ({b_j} - {a_j})*precision \le {2^{{m_j}}} - 1$$其中precision为精度，如小数点后5位，则precision=10^5，mj为编码长度，${x_j} \in [{a_j},{b_j}]$二．二进制解码解码即编码的逆过程:$${x_j} = {a_j} + {\rm{decimal}}(substrin{g_j}) \times \frac{{{b_j} - {a_j}}}{{{2^{{m_j}}} - 1}}$$三．种群初始化编码完成后，开始对种群初始化，为了简便采用随机地方式进行初始化。

初始群体的生成：随机产生N个初始串结构数据，每个串结构数据称为一个个体，N个个体构成了一个群体。

GA以这N个串结构数据作为初始点开始进化。

def rand_init(self):for i in range(self.code_x1_length):self.code_x1 += str(random.randint(0, 1))for i in range(self.code_x2_length):self.code_x2 += str(random.randint(0, 1))四．适应度评估适应度表明个体或解的优劣性。

不同的问题，适应度函数的定义方式也不同。

def decoding(self, code_x1, code_x2):self.x1 = self.bounds[0][0] + int(code_x1, 2) * (self.bounds[0][1] - self.bounds[0][0]) / (2 ** self.code_x1_length - 1)self.x2 = self.bounds[1][0] + int(code_x2, 2) * (self.bounds[1][1] - self.bounds[1][0]) / (2 ** self.code_x2_length - 1)五．选择选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。

遗传算法定义遗传算法（Genetic Algorithm）是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它是有美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著《Adaptation in Natural and Artificial Systems》，GA这个名称才逐渐为人所知，J.Holland教授所提出的GA通常为简单遗传算法（SGA）。

遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。

每个个体实际上是染色体(chromosome)带有特征的实体。

染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。

因此，在一开始需要实现从表现型到基因型的映射即编码工作。

由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜务汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。

这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。

遗传算法特点遗传算法是一类可用于复杂系统优化的具有鲁棒性的搜索算法，与传统的优化算法相比，主要有以下特点：1、遗传算法以决策变量的编码作为运算对象。

传统的优化算法往往直接决策变量的实际植本身，而遗传算法处理决策变量的某种编码形式，使得我们可以借鉴生物学中的染色体和基因的概念，可以模仿自然界生物的遗传和进化机理，也使得我们能够方便的应用遗传操作算子。