毕业设计（论文）-不可行染色体转换算法VB语言设计与实现.doc

烟台大学毕业论文(设计)分类号 编号烟 台 大 学毕 业 论 文（设 计）不可行染色体转换算法设计与实现infeasible chromosome conversion algorithm design and implementation申请学位： 学士学位 院 系：机电汽车工程学院 专 业：测控技术与仪器 姓 名： 学 号： 指导老师： 2010年6月10日烟台大学不可行染色体转换算法设计与实现姓 名： 导 师： 2010年6月10日烟台大学 摘要： 本文介绍了遗传算法、生产调度、不可行染色体等相关知识。在已存在的不可行染色体转换方法中，筛选出两种方法，利用vb6.0软件开发平台来实现不可行染色体的转换，并且对转换结果进行了对比。关键词：遗传算法; 不可行染色体; 转换方法; 综合作业调度问题abstract：this article describes the knowledge of genetic algorithm, production scheduling,infeasible chromosomes. in the methods of infeasible chromosome conversion already exists, the selected two methods, using vb6.0 software development platform to implement the conversion of infeasible chromosome, and compared the conversion results . keyword: genetic algorithm; infeasible chromosome;conversion method ;complete job shop scheduling problem 目录目录4第一章 绪 论51.1遗传算法51.2生产调度的概念61.3生产调度问题的研究意义61.4生产调度的性能指标71.5生产调度问题的特点71.6 cjssp概念8第二章 不可行染色体转换概念及方法92.1不可行解与转换的概念92.2对转换方法的要求92.3基于路径表的扫描换位102.4基于根右移的子树归位12第三章 不可性染色体转换算法实现软件设计143.1界面设计143.2程序设计153.2.1定义变量163.2.2算法共用程序设计163.2.3基于路径表的扫描换位的程序设计203.2.4基于根右移的子树归位的程序设计21第四章 实验结果234.1实验结果23毕业设计总结26致 谢27参考文献28附录1 程序29附录2 软件界面33第一章 绪 论随着经济的发展，车间生产调度问题是当今科学研究的热点，近十几年来，面向用户个性化需求的定制生产模式开始成为制造的主流，对市场需求的快速反应能力开始成为企业能否在激烈的市场竞争中占得一席之地的重要，因此，柔性快速的生产调度就显得格外重要。然而，现今国内的大部分企业主要依靠经验丰富的工人手工安排调度计划。在调度任务规模较大且动态多变的环境中，单纯的手工调度已无法满足市场的需求。因此，利用科学理论手段进行车间作业调度是十分必要的。遗传算法作为解决生产调度问题的工具，起着不可替代的作用。本文以综合作业调度问题(complete job shop scheduling problem , cjssp) 遗传算法中不可行染色体为对象,针对了2 种不同转换方法,利用vb6.0软件开发平台进行了转换实现，并对结果进行了分析。1.1遗传算法遗传算法（ga：genetic algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。它是由美国的j.holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。算法（algorithm）是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。 算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤。或者看成按照要求设计好的有限的确切的计算序列，并且这样的步骤和序列可以解决一类问题。 一个算法应该具有以下五个重要的特征： 算法可以使用自然语言、伪代码、流程图等多种不同的方法来描述。 1、有穷性一个算法必须保证执行有限步之后结束； 2、确切性算法的每一步骤必须有确切的定义； 3、输入一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件； 4、输出一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的； 5、可行性算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。 计算机科学家尼克劳斯-沃思曾著过一本著名的书数据结构十算法= 程序，可见算法在计算机科学界与计算机应用界的地位。遗传算法ga的基本原理是，产生若干代表问题候选解的成员，并组成一个群体，按照某一评价函数或算法对群体中的每个成员进行评估，评估结果代表解的良好性。按照适者生存、优胜劣汰的原则，群体中的某一成员愈适合，则愈有可能产生后代。利用遗传操作对群体中的成员进行遗传操作，产生新的后代，这种后代能继承双亲的特征。对后代进行评估，并将其放入群体，代替上一代中较弱的成员(非良好解)。此过程反复执行，这构成一代一代的群体。随着遗传过程的不断进行，越来越良好的解就可以得到。一些学者经过研究发现，遗传算法比经典的启发式算法好，同时遗传算法比传统的搜索技术优更强的鲁棒性，因为它不仅能解决某一特定问题，而且可以适应不同的问题形式。遗传算法的优越性归功于它与传统搜索方法不同的特定结构：(1)ga的工作问题是编码，对搜索问题的限制极少，对函数的一些约束条件象连续性、可导性等不作要求，减少了要解决的问题的复杂性。(2)ga是同时搜索解空间内的许多点，因而可以有效地防止搜索过程中收敛到局部最优解，并获得全局最优解，与其它单点搜索的方法相比，在计算时间上也有较大的优势。(3)ga使用遗传操作时是按概率在解空间进行搜索，因而既不同于随机查找，也不同于枚举查找那样盲目的穷举，而是一种有目标、有方向的启发式搜索1.2生产调度的概念生产调度就是组织执行生产进度计划的工作。具体来说是在满足某些约束(作业的先后关系、预定的完成时间、最早开始时间和资源能力等)的条件下对操作(作业)的排序，按照排序的次序给它们分配资源和时间，并且使某个执行目标达到最优(如总的执行时间、拖期时间和生产费用等)。生产调度问题一般可以描述为：针对某项可分解的工作，在一定约束条件下，如何安排其组成部分(操作)所占有的资源、加工时间、先后顺序，以获得产品制造时间或成本等最优。影响调度问题的因素很多，正常情况下有：产品的投产期，交货期(完成期)，生产能力，加工顺序，加工设备和原料的可用性，批量大小，加工路径，成本限制等，这些都是所谓的约束条件。有些约束条件是必须要满足的，如交货期，生产能力等，而有些达到一定满意度就行，如生产成本等，这些约束在进行调度时可以作为确定性因素考虑。而对于设备故障，原料供应变化，生产任务变化等非正常情况，都是事先不能预见的，在进行调度时大都作为非确定性因素考虑。生产调度中涉及的工厂资源包括：原料、设备(加工、存储、运输)、人力、资金、能源等。生产调度的性能指标可以是成本最低、库存费最少、生产周期最短、生产切换最少、设备利用率最高、三废(废气、废水、废渣)最少等。生产调度以生产进度计划为依据，生产进度计划要通过生产调度来实现。生产调度的必要性是由工业企业生产活动的性质决定的。现代工业企业，生产环节多，协作关系复杂，生产连续性强，情况变化快，某一局部发生故障，或某一措施没有按期实现，往往会波及整个生产系统的运行。因此，加强生产调度工作，对于及时了解、掌握生产进度，研究分析影响生产的各种因素，根据不同情况采取相应对策，使差距缩小或恢复正常是非常重要的。1.3生产调度问题的研究意义企业为了适应激烈的市场竞争，相对灵活的生产方式逐渐成为主流，这对企业的生产管理的要求更加苛刻。为了获得最大的经济效益，原来的生产计划及仅凭经验的管理方式已经不能满足现代生产的要求了，必须采用科学的方法对生产过程进行优化。生产管理者所面临的问题是：如何最优的根据已经具备的条件去安排生产以满足市场上对产品的需求。有限资源的合理配置是人类社会所面临的最基本经济学问题。学者们从不同的角度对于这方面进行研究，产生了许多这类问题的不同的学科和理论，其中在生产领域产生了重要的生产调度理论。生产调度理论是针对制造车间生产计划与控制的研究，关于它的研究涉及运筹学、管理科学和应用数学等，经过近几十年的发展，已经形成了许多理论。在企业当中得到了广泛的应用。这个理论体系应用范围广泛，在一定程度上促进了社会经济的发展。生产调度主要用于解决工件在机器上的调度和资源分配问题，可以大大提高生产效率和资源利用率，进而增加企业的竞争能力。因此生产调度对制造企业车间作业调度问题进行研究具有重要的现实意义，它是实现有限资源在车间作业当中优化配置的重要工具。但是目前在我国许多多企业生产管理技术及手段落后，缺乏系统科学的生产调度方法，生产计划和调度安排仍然依靠经验，资源利用不合理，对市场反映不够灵敏，严重影响了企业的经济效益。从国外引进了的一些较为先进的生产管理技术和信息系统只在一定范围内得到了应用，大多数制造企业的车间生产计划和调度还处在依赖车间管理人员工作经验的人工安排阶段。1.4生产调度的性能指标实际生产调度的性能指标大致可以归结为三类：(1) 最大能力指标包括最大生产率、最短生产周期等，它们都可以归结为在固定或者无限的产品需求的前提下，最大化生产能力以提高经济效益。 在执行着一条指标时还要考虑到质量，不能把最大生产(2)最低(高)成本指标包括最大利润、最小运行费用、最小投资、最大收益等，其中收益指产品销售收入，运行费用包括库存成本，生产成本和缺货损失。(3)客户满意度指标包括最短的延迟，最小的提前或者拖期惩罚等。在传统的调度中，一般以平均流通时间最小、制造周期最短、满足交货期为调度目标，而在实际生产中，由于提前完成的产品必须保存到交货期，而拖期产品必须交付违约金，因此，在实际调度中经常考虑“提前”或者“拖后”的惩罚。1.5生产调度问题的特点实际的调度问题有以下特点：1复杂性由于装卸作业、装卸设备、库场、搬运系统之间相互影响、相互作用，每个作业又要考虑它的到达时间、装卸时间、准备时间、操作顺序、交货期等，因而相当复杂。而且调度问题是在等式或不等式约束下求性能指标的优化，在计算量上往往是np(nondeterministic polynomia，多项式非确定性问题)完全问题，即随着问题规模的增大，对于求解最优化的计算量呈指数增长，使得一些常规的最优化方法往往无能为力。即使对于单台机床加工问题，如果有n个工件而每个工件只考虑加工时间以及与操作序列有关的安装时间，则这个问题就和n个城市的tsp(traveling salesman problem，旅行商问题)问题等价。对于一般加工系统，问题更加复杂。2动态随机性在实际的生产调度系统中存在很多随机的和不确定的因素，比如作业到达时间的不确定性、作业的加工时间也有一定的随机性，而且生产系统中常出现一些突发偶然事件，如设备的损坏或修复、作业交货期的改变等。3多目标性实际的计划调度往往是多目标的，是一个多目标决策问题，有时候这些目标间可能发生冲突。kiran等人将调度目标分三类：基于作业交货期的目标、基于作业完成时间的目标、基于生产成本的目标。这种多目标性导致调度的复杂性和计算量急剧增加。基于时间和作业交货期的目标，主要包括任务的生产周期最短，完成日期与交货期最接近，任务在制造系统中的总等待时间最短等；基于成本的目标主要考虑如何减少生产过程中的资金占用和怎样合理利用资源，使各个生产环节负荷均匀，保证生产的稳定性。1.6 cjssp概念综合作业调度问题(complete job shop scheduling problem , cjssp）是生产调度问题的问题之一。基本可定义为：个产品，每个产品有不相等的个装配体，每个装配体有不相等的个工序，在台不同的机器上加工，已知个产品的结构、各工序的制造时间和各装配体在各机器上的制造次序约束，要求确定与产品结构和工艺条件相容的各机器上所有装配体的制造开始时间或完成时间或制造次序，使制造性能达到最优。它作为生产调度问题之一，可以应用到很多领域，在交通运输方面，可以用于车辆或者船、飞机等交通工具，货物，司机等方面的优化配置。在人力资源管理方面分配根据人的特点、时间等因素分配任务。在市场营销方面可用于优化配置资金、人员、广播电视传媒方面的配置。本文的主要内容就是针对cjssp问题中的一个环节进行讨论。第二章 不可行染色体转换概念及方法遗传算法是解决生产调度问题的重要方法之一，为了实现资源优化配置，以基因代表工序，用染色体代表产品的工序组成。2.1不可行解与转换的概念在产品的生产过程中，会遇到工序之间的加工时间前后的要求，在产品所需的零件没有被加工出来之前，产品不允许组装、再加工；同一零件的各个工序之间加工时间前后往往也有要求。对于加工这些都是约束。简单举例来讲：以一条染色体代表一辆汽车的加工过程，基因代表产品所需的零件工序，只有零件工序符合加工要求的顺序，才能够派工，否则要进行转换，使染色体内基因顺序符合约束条件。根据以上内容，学者做出了以下定义：1.不可行染色体：染色体没有基因冗余或缺损,但是违反了约束,表示的是一个不可行解,称为不可行染色体。通常简称为不可行解,也即染色体解码出来的解在给定问题的可行区域之外。就是例子中加工顺序错误。2.非法染色体：染色体存在基因缺损或冗余,不能表示一个解,称为非法染色体。通常简称为非法解,也即某个染色体不能代表给定问题的解。在例子中表现为缺少零件工序。3.染色体转换：使不可行染色体转化为正常的可行染色体,即纠正染色体中所有违反工艺约束的情况,称为染色体转换。转换只纠正违反工艺约束的情况,尽量不改变染色体中的其余信息。2.2对转换方法的要求理想的转换方法应该做到,在保证纠正所有违反的约束情况下,要尽可能少地改变转换前的染色体,使不可行染色体中包含的信息丢失最小。因此,转换方法应该具有下述性能: 第一，只转换不可行染色体,对可行染色体不进行转换。换句话说,可行染色体转换前后完全相同。第二，只对染色体进行纯粹的消除违反约束所必需的改变。第三，转换前后的种群要具备同样的多样性,即多样性等效转换。本来多样性高的种群,转换后仍然高;原来低的转换后仍然低,类似于修旧如旧的原则。第四，快速高效。因为这是对所有染色体都要应用的过程,尤其当问题规模比较大时,时间开销是必须要考虑的一个问题。当然,解决组合优化问题时,要根据实际需要进行选择或设计。考虑到遗传算法中时间花费与性能的关联,要综合考虑质量与效率要求。至于转换方法本身的复杂性,可计入时间开销中。 不可性染色体转换算法的设计已经存在，经过筛选，以下两种算法是比较简单地算法思想，在第五章中将对两种算法进行软件实现，下面介绍一下这两种算法的思路。2.3基于路径表的扫描换位基于路径表的扫描换位（cip: circulatory interchanging based on pathway）以图2.3.1所示产品为例说明总的转换思想。首先建立对每一个基因的“直系关系”表，也可称为“父子关系”表，来说明装配路径，4的父项是2，2的父项是1，1是4的顶级父项，建立的关系就为：1-2-4。在不可行染色体中，对每一基因建立完整“直系关系”表，从左至右进行扫描，用第一个基因依次对后面的每一个基因进行比较，如果等于后面的基因的顶级父项，就交换位置，并且把交换到前面的基因的顶级父项删除，因为下次比较时不需要在对该父项进行比较，而是对删除后出现的顶级父项进行比较。删除之后，针对第二个基因进行下一轮的比较，如此循环，如果产品结构的为n层，从左至右进行扫描n-1遍后即可把不可行染色体转换为可性染色体。12534图2.3.1 产品结构图流程图如下：选择染色体基因bu（i）寻找其后面的子项判断该项基因是否是其子项yn交换位置删除顶父项扫描是否n-1遍yn输出可行染色体图2.3.2图2.3.1为产品结构图，举例来说：需要转换的染色体为：1，5，3，2，4，2建立父项表后： 1，1-2-5，1-3，1-2，1-2-4，1-2进行扫描第i个基因依次与后面基因比较，根据比较结果在进行处理： 1-2-5，1，1-3，1-2，1-2-4，1-2 2-5，1，1-3，1-2，1-2-4，1-2 2-5，1-3，1，1-2，1-2-4，1-2 2-5，3，1，1-2，1-2-4，1-2 2-5，3，1-2，1，1-2-4，1-2 2-5，3，2，1，1-2-4，1-2 2-5，3，2，1-2-4，1，1-2 2-5，3，2，2-4，1，1-2 2-5，3，2，2-4，1-2，1 2-5，3，2，2-4，2，1 2-5，3，2，2-4，2，1第一遍扫描完成，下面第二遍扫描： 2-5，3，2-4，2，2，1 5，3，4，2，2，1以上最后一条数据就是符合装配约束的派工序列，即可性染色体。在扫描过程中，所比较的基因不仅要与后面进行比较，也要与前面进行比较，例如上面得例子中2与前面的2-5进行比较，处理结果是删除2-5前面的2-，而不交换位置，这样才能得出正确的结果。2.4基于根右移的子树归位再次以产品装配图4.1.1为例进行说明：父串：1，1，2，2子串：2，3，4，5对于不可性染色体： 1，5，4，2，5，3，3，1，2，4同样建立“父子关系”表，之后为： 1，1-2-5，1-2-4，1-2，1-2-5，1-3，1-3，1，1-2，1-2-4提取根为1的树枝（即全部基因，为了实现第五章的循环程序，把树也作为一树枝处理）： 1，1-2-5，1-2-4，1-2，1-2-5，1-3，1-3，1，1-2，1-2-4将根全部右移之后： 1-2，1-2-5，1-2-4，1-2，1-2-5，1-3，1-3，1-2-4，1，1把非根基因处理，删除右移后非根基因与根基因的关系，处理后如下： 2，2-5，2-4，2，2-5，3，3，2-4，1，1提取树枝根为2的基因：2，2-5，2-4，2，2-5，2-4根右移后： 2-5，2-4，2-5，2-4，2，2把非根基因处理，删除右移后非根基因与根基因的关系，处理后如下： 5，4，5，4，2，2放回原来提取时的位置后： 5，4，5，4，2，3，3，2，1，1以上最后一条数据就是符合装配约束的派工序列，即可性染色体。流程图如下：在不可行染色体中依次提出树枝根向右移转换后依次放回原染色体父项染色体扫描完ny输出转换后染色体 图2.4.1第三章 不可性染色体转换算法实现软件设计在进行软件设计中，使用应用程序开发工具vb6.0设计。首先设计出操作界面，定义各个控件的属性，然后编写出程序。在做算法实现的过程中，先做出手动输入不可行染色体、判断转换后输出结果是否正确来调试程序，等调试成功后，进行连接文本，输入输出都是以文本的形式进行，这样对于软件操作者来说简单易行，可以对大量的不可行染色体进行转换。3.1界面设计 用vb6.0 设计出操作界面如下图所示： 图3.1.1界面的设计：界面从上至下输入父项染色体、子项染色体和被转换对象不可行染色体，然后选择算法，点击转换按钮，转换结束后可以点击退出按钮退出程序，也可更换输入的染色体或者算法进行下一次的转换。从上至下的布局符合人的一般操作习惯。各个控件的属性设置如下表：对象控件名属性名属性值功能commandbuttoncommand1caption转换command2caption退出textboxtext1text空输入父项染色体text2text空输入子项染色体text3text空输入被转换染色体text4text空显示转换后染色体text5text空显示转换时间labellabel1caption输入父项染色体label2caption输入子项染色体label3caption输入被转换染色体label4caption选择算法label5caption输出可行染色体label6caption输出所用时间frameframe1caption输入frame2caption输出timertimer1enabledtrueoptionbuttonoption1captioncipoption2captionslrrls3.2程序设计程序的主干如下图所示：把需要转换的不可性染色体复制于acip slrrls判断选择算法输出结果a，结束程序 图3.2.1 对于多条染色体的转换，利用循环多次运行程序，即可完成转换。3.2.1定义变量 对程序中用到的变量进行定义，定义如下：dim a as string 不可行染色体串定义dim b as string 父串染色体串dim c as string 字串染色体串定义字符串。dim bu(1 to 110) as string 不可性染色体基因dim fu(1 to 11) as string 父串染色体基因dim zi(1 to 11) as string 字串染色体基因dim buk(1 to 100) as string定义数组。dim n as integer 不可性染色体基因数目dim m as integer 父串染色体基因数目dim z as integer 字串染色体基因数目dim i as integer 定义变量dim j as integer 定义变量dim k as integer 定义变量dim x as string 定义变量dim y as string 定义变量dim l as integer 定义变量dim e as integer 定义变量dim zh(1 to 100) as string 定义变量，用于记住提取位置dim st, et, pt 定义变量，用于时间计算dim nextline as string 定义变量3.2.2算法共用程序设计 经过程序调试成功后，连接文件，以文件的形式进行输入、输出，这时可以将界面内输入不可性染色体、输出转换后染色体的控件删除，做成如下形式： 图3.2.2 当单击按钮转换时，时间开始计时，把父子串染色体赋值给b、c两个字符串。具体程序，编写如下：private sub command1_click() st = now 计时开始b = text1.textc = text2.text以输出入的形式打开f盘中的文件/不可行染色体。open f:不可行染色体.txt for input as #1循环程序，每次由文件向程序内变量a输入一条不可性染色体，直到文件内不可性染色体输出结束。do until eof(1) line input #1, nextline a = nextline 在转换过程中，父子基因关系是转换的唯一依据。必须使父子基因之间关系用数据的形式连接在一起。利用vb内的函数mid$（a,b,c）来提取每一个基因，a表示从字符串a中提取；b表示从第b个基因提取；c表示提取的数量为c个基因。使用for to next 语句来循环提取，直到被提取对象最后一个基因被提出。程序如下： n = len(a) 提取不可行染色体基因 for i = 1 to n bu(i) = mid$(a, i, 1) next i如果a的第5个基因是3，那么bu(5)=3。 m = len(b) 提取父串基因 for j = 1 to m fu(j) = mid$(b, j, 1) next j z = len(c) 提取子串基因 for k = 1 to z zi(k) = mid$(c, k, 1) next k 在提取基因后，再对其进行“父子关系”的确认。这段确认程序成为组串程序，它将完成新的字符串，装配关系（父子关系）如下：12534 图3.2.3 对于子串来说，如果原来是zi(7)=5，经过组串程序后zi(7)=125，将它的父基因依次排在前面。程序如下：for l = 1 to z 组串程序 zi(l) = fu(l) & zi(l) next l j = 1 while j = 10 for k = 1 to z l = z - k + 1 for i = 1 to l - 1 if left$(zi(l), 1) = right$(zi(i), 1) then zi(l) = zi(i) & mid$(zi(l), 2, len(zi(l) - 1) next i next k j = j + 1 wend 经过组串后，把“父子关系”应用到不可行染色体的基因里面去。 for i = 1 to n for k = 1 to z if bu(i) = right$(zi(k), 1) then bu(i) = zi(k) next k next i调用选择程序，选择程序内调用算法程序，所以经过调用选择程序之后，结果已经出来了，打开文件，进行结果输出。没有的文件时，系统自动建立一个名为可性染色体的txt文件，进行结果输出。append的输出形式是在原来文本的末尾输出，不会覆盖原来的文本。chr(13)+c(10) 则表示每输出一条染色体则回车换行。 call xuan open f:可行染色体.txt for append as #2 print #2, a + chr(13) + chr(10) 输出可行染色体a close #2 关闭文件loopclose #1 关闭原文件et = now 计时停止pt = et st 计算运行所用时间text5 = format(pt, hh:mm:ss) 输出时间end sub 程序结束 选择程序的编程如下，当有方法被选中时select case true，判断是哪一种方法，如果case option1.value，则调用算法cip的运算程序；case option2.value，则调用算法slrrls的运算程序。 sub xuan()select case true case option1.value call cip 选择第一个算法。 case option2.value call slrrls选择第二个算法。 end selectend sub定义第二个按钮的作用，当单击此按钮时，将结束程序。private sub command2_click()endend sub3.2.3基于路径表的扫描换位的程序设计基于路径表的扫描换位( cip: circulatory interchanging based on pathway）运算程序，把不可性染色体每一个基因与与后面的每一个基因比较，如果后面的基因是它的子项，二者交换位置，并且子项内要删除表示该基因的字符，以便于下一次扫描。这种扫描方法原本不必和前面的基因进行比较，但是在本程序中，如下图表示基因5的字符串125，在1的前面的话，“125”中的“1”不会被删除，当与“125”前面的“2”进行比较时，就会出现错误。所以程序设计时，是对每一项都进行比较的，对于一个基因，子项在前面，就删除子项中该基因关系；子项在后面，交换位置后，再删除子项中该基因关系，进入下一个基因扫描。1 2534 图3.2.4sub cip() cip运算程序j = 0 换位及删除程序while j = 2 and l = 2 and l i theny = bu(i) bu(i) = bu(l)bu(l) = ybu(i) = mid$(bu(i), 2, len(bu(i) - 1)exit for end if next l next i j = j + 1wend经过扫描，每个基因都恢复到一个字符的状态，符合条件的基因对经过交换位置，数组bu(i)按照i的递增方向已经成为一条可行染色体。将每一个基因进行重新连接，赋值于a。 a = bu(1) 重整程序 for i = 2 to n bu(i) = bu(i) a = a & bu(i)next i end sub程序结束。3.2.4基于根右移的子树归位的程序设计 基于根右移的子树归位（slrrls: subtree locus reversion based on root left shift）的转换思想是：在父项中依次提取代表每一个基因的字符m，经过组串程序后的染色体已经把“父子关系”明确了，从左端查，对每一个代表不可行染色体基因的字符串进行筛选，如果该字符串左端的字符等于字符m，说明该项是m的子项或则m本身，提取出来。将m所有子项及其本身依次赋值给一个数组buk()，不是m本身的字符串用函数mid$(buk(i),2,len(buk(i)-1)删除第一个字符，len(a)是计算字符串a中字符个数的函数。sub slrrls() slrrls主程序st = now for j = 1 to m 对于每一父项基因都要进行扫描 k = 0: l = 0 for i = 1 to n 提取该基因下所有子项基因 if left$(bu(i), 1) = fu(j) then k = k + 1buk(k) = bu(i) l = l + 1 zh(l) = i next i 函数left$(bu(i),1)提取字符串bu(i)的左端第一个字符，zh(l)的作用是记住原来提取不可性染色体中基因时的位置。 y = 0 计算每一父项基因在不可性染色体里的数目y for i = 1 to n if bu(i) = fu(j) then y = y + 1 next i if y = 0 then for i = 1 to n buk(i) = mid$(buk(i), 2, len(buk(i) - 1) next i else for e = 1 to k if buk(e) fu(j) then buk(e) = mid$(buk(e), 2, len(buk(e) - 1) next e扫描y次，把buk(i)中的y个父项基因移动到最右端。l = 1 do while l = y 扫描y次 for e = 1 to k - 1 if buk(e) = fu(j) and buk(e + 1) fu(j) then x = buk(e)buk(e) = buk(e + 1) buk(e + 1) = x end if next e l = l + 1 loop k表示针对父项染色体中一个基因在不可行染色体中提取的字符串的个数。 for l = 1 to k e = l 把数组zh(l)转化为数字类型 zh(l) = val(zh(l) 把提取的基因按照新的顺序，放回原来的位置。 bu(zh(l) = buk(e) next l end ifnext j 针对下一父项基因，在不可性染色体中寻找其子基因经过扫描，每个基因都恢复到一个字符的状态，符合条件的基因对经过交换位置，数组bu(i)按照i的递增方向已经成为一条可行染色体。将每一个基因进行重新连接，赋值于a。a = bu(1) for i = 2 to n a = a & bu(i) next iend sub第四章 实验结果进行转换实验, 针对同一不可性染色体集合，用相同的父子串染色体，一是直接对两种算法进行计时实验,二是将两种算法的输出结果进行比较。为了便于计时,集合规模为300 条染色体, 300 条初始随机非法染色体无一重复。4.1实验结果取3对父子串进行试验，每对实验每种方法进行两次。通过以下的实验结果，进行分析。父串为：112223335子串为：23456789a两种方法运行时间：cip ：13秒 slrrls：7秒cip ：14秒 slrrls：6秒父串为：123456789 子串为：23456789a 两种方法运行时间：cip ：12秒 slrrls：6秒 cip ：12秒 slrrls：6秒父串为：112233445 子串为：23456789a 两种方法运行时间：cip ：14秒 slrrls：6秒cip ：14秒 slrrls：7秒以上结果表明slrrls方法明显比cip方法快。这是因为cip程序在扫描过程中需要对非“直系亲属”进行比较，例如：2和3都是1的子项，在cip中当扫描至父项为2时，需要和3的及其子项们进行比较，这样就增加了比较工作量。而slrrls方法与cip方法相比，只是多了提取基因的过程和放回过程，提取一个父项基因及其子项基因之后，对于父项2，与其相比较的只有2及其子项，省去了和“旁系”的比较，减少了工作量，缩短了工作时间。对于同一条不可行染色体来说，两种算法转换的结果一样，是因为在cip中只对符合条件“直系亲属”进行交换位置，扫描方式是对不可性染色体从左向右依次提取基因，再和前后基因比较，后面有它的子项，就与子项交换位置；而slrrls是依次提取一个父项基因及其子项，扫描方式也是对不可性染色体从左向右依次提取基因，如果等于父项，后面基因比较，后面基因不等于父项时，就是该基因的子项，便与其交换位置；这两种交换位置的方式是一样的，只不过为了提高效率，slrrls是提取之后在进行扫描，避免了对非“直系亲属”的扫描比较。举个例子来说，1是2和3的父项，而且1只这两个子项，对于算法cip来说，经过n次（n是1的个数）扫描之后，1全部右移（除了1右移之外，其它染色体相对位置不变，在左面的还是在左边），然后再对下一级进行扫描，在扫描的过程中，对于2及其子项，只会在2及其子项的位置上进行作用：互换位置、删除顶级父项。不会去占用3及其子项的位置；对于3及其子项也是这样。而算法slrrls是提取一个树进行作用，把1全部右移（这种右移也是只对1进行，其它染色体的相对位置不变，所以右移之后排列方式是唯一的）后，提取2及其子项进行2的右移，右移完毕后，再将其新的排列按照提取时的位置放回。对于3也是这样。两种算法的方式不一样，但同级及其子项之间的位置不会发生互换，即只有“直系关系”的基因发生互换，这样每个基因的位置最终就是固定的，所以这两种算法结果是一样的。两种算法，只