遗传算法修复基因并解决大搜索空间约束优化问题

© 2013由Elsevier B.V.发布。信息工程研究院负责评选和同行评议可在www.sciencedirect.com上在线获取ScienceDirectIERI Procedia 4（2013）268 - 2742013年电子工程与计算机科学利用遗传算法Jayanthi Manicassamya，*，Dhavachelvan. Pba印度本地治里本地治里大学计算机科学系b印度本地治里，本地治里大学计算机科学系摘要目前，遗传算法在解决大搜索空间约束优化问题中发挥着重要作用。这部作品以适者生存为原则，涉及自然进化过程中的达尔文理论。遗传算法不能直接求解基于严格约束的优化问题，而必须通过修改经典遗传算法中已有的操作来实现。大量的算子及其运算存在，使得许多研究者面临着各种各样的设计问题。在这些问题中，一个隐藏在研究中的主要问题是，对有缺陷的基因进行修复。本文提出了两种生物启发基因功能基因转化和基因转染相结合的方法来解决获得最优解的问题。这通过毫不费力的方式修复进一步增强了基因功能。所提出的工作进行了测试0/1背包问题，其结果与经典的遗传算法相比，产生提供更好的结果时，经典的遗传算法。© 2013作者。由Elsevier B. V.在CC BY-NC-ND许可下开放获取。信息工程研究院负责评选和同行评议关键词：仿生算法;进化计算;基因修复;遗传算法;基因;优化;转感染; 0/1背包问题。1. 介绍今天，基于进化的自然处理在解决大型约束问题中起着重要的作用，以确定最优的解决方案，遗传算法属于这一类。遗传算法2212-6678 © 2013作者由Elsevier B. V.在CC BY-NC-ND许可下开放获取。信息工程研究所负责的选择和同行评审doi：10.1016/j.ieri.2013.11.038Jayanthi Manicassamy和P.Dhavachelvan/IERI Procedia 4（2013）268269CB.G.在达尔文理论的运作过程中，奠定了其“适者生存”的基础[11-13]。一般来说，基于约束的问题很难被认为是普遍的，因为它们在不同的问题之间是不同的。在遗传算法中进行了各种操作和措施，以克服在解决基于约束的问题时所面临的问题，以获得仅在一定程度上可以获得的最优解[4-7]。基于对遗传算法在每个阶段及其中间处理层次进行的深入分析，已经认识到问题在于查看和定位它[1-3，8-10]。在经典遗传算法中，许多措施的解决方案已被认为是忽略对考虑每个阶段之间的中间水平是一个最重要的原因背后没有完全获得解决方案的约束为基础的优化问题的大搜索空间。本文的重点是提供解决方案，以获得最佳的解决方案，通过基因增强调整交叉过程中获得的结果，根据某些约束的发生。在第二节中，讨论了基因转化和转基因功能的背景及其在使用遗传算法获得最优解中的作用。第三节通过结果分析说明了0/1背包问题的适用性。在第4节中，讨论了未来改进的结论。2. 基因转染和转化以获得最优解基因是DNA的操作子组件，它包含特定的指令集，这些指令编码特定的蛋白质或特定的功能[14]。这些基因存在于染色体中。并不是所有的基因都被发现是功能性的，一些基因可能通过各种手段或各种原因被抑制其产生蛋白质合成的功能部分[15]。通常，基因转化是DNA转移中的适应，其取决于功能建立所要执行的活性[13，14]。这种转化和转感染可以通过提高基因表达频率来适应DNA损伤的特异性修复。这也可以用于规范系统的功能，目前正在遗传学领域进行各种研究[18]。这篇论文是在将转化和转感染活性纳入标准化基因功能以获得最佳优化结果的想法背后。3.1. 遗传算法在经典遗传算法中，采用了上述的基因转化和基因转染的概念来获得最优解。该基因函数被表示为交叉后进行的处理步骤，以获得比GA中进行的其他操作更好的结果。这种操作是在基因水平上对交叉后产生的后代进行操作定义1. 假设GAn 伊季（一）在下列情况下，‘GA’ is ‘n’ is the set of chromosome generated for a specific‘C’定义2. 设GT是对与约束违反有关的基因“G ij”进行的转化和转感染作用这可以定义为270Jayanthi Manicassamy和P.Dhavachelvan/IERI Procedia 4（2013）268伊季选择初始化交叉基因转化&转感染终止检查突变CGTCS（二）在下列情况下，‘C’‘G‘CS’ constrain hold for the specific图1.具有转化和转染的图1.作为对经典遗传算法的一种改进，提出了一种带有基因转换和基因转染的遗传算法。基于适应度值，染色体被选择用于交叉以产生后代1.1.1. 遗传算法与基因转化和转感染阶段1：生成初始种群。第二阶段：繁殖a)生成一组具有不同可能结果b)评估每个染色体的适应度函数。c)选择任何一种选择技术，并根据适应度函数对染色体进行操作。阶段3：通过交叉操作生成后代第四阶段：评估后代是否违反约束。由于过度或过小的表达而违反约束。a)对产生的两个后代进行基因转化，以获得其亲本染色体结构。b)对修饰后的子代进行转感染操作。阶段5：如果需要，执行突变，这是可选的。第六阶段：选择最好的后代并将其传给下一代。阶段6：转到阶段2。Jayanthi Manicassamy和P.Dhavachelvan/IERI Procedia 4（2013）268271除第4阶段为快速获得最优解而在经典遗传算法中增加了一个新的操作步骤外，其余阶段均遵循经典遗传算法。2.2 0/1背包问题本文以带约束的0/1背包问题为例，证明了带基因转换和感染的经典遗传算法在求解最优解方面的有效性。设C是背包的总容量。目标是在背包的容量范围内最大化利润，包括或排除对象。本文提出了二进制表示形式的实现过程. 1表示包含对象，0表示排除对象。对于具有3个目标的0/1背包问题，必须在最小代内获得最优解。下面显示了从样本染色体生成的后代的基因转化和转染。产生的后代后代1011后代2010图2. 产生的后代基于超重时最大利润和最小重量时最小利润的约束违反，对不同比特执行基因转换。这与父母的染色体结构有关。后代1010后代2011图3. 基因突变尚未发生假设后代2给出具有超容量的最大利润，并且基于对利润和权重的功能性分析的频率水平的差异，后代给出具有最小权重的最小利润。在这里，对产生的后代进行基因转化，以保持其父母的染色体结构。使用方程5在不同的比特对上进行进一步的基因转染，以在一定程度上增强染色体结构，以获得最佳结构。图3、图4和图5表示对增强后代进行的基因转化和转感染。将最优世代的后代作为下一代，进行n代。所产生的基因转化表现出后代后代1只010后代2只011图4. 基因转化对不同的比特对进行基因转染，转染速率选择。272Jayanthi Manicassamy和P.Dhavachelvan/IERI Procedia 4（2013）268后代1只011100后代2只图5. 基因转染在错配位置上随机选择的输血率是n第一章12（三）其中，R是修复率，E是1/2，1/23. 实验分析多次，每个实验执行已在各种数据集上进行。使用单点交叉和两点交叉进行测试，最小变异率。人口规模因问题而异。在图8中，已经表示了用于生成具有转化和转感染的经典GA（CGA）和增强GA（EGA）的最优解的最佳、最差和平均情况。3.1. 评估方案1：具有固定对象的背包容量可变在第一次评估中，只有背包的容量会改变，但对象将是固定的。该测试针对多个数据集进行，并进行了多次测试。图6.下面所示的描述了CGA和EGA用于获得具有不同背包容量的固定对象的最优解的性能。3.2. 评估方案2：固定背包容量，对象在第二次评估中，只有背包的容量是固定的，但对象的数量将发生变化。该测试针对多个数据集进行，并进行了多次测试。图7.下面表示的描述了CGA和EGA的性能，用于获得针对固定背包容量而变化的对象集合的最优解。Jayanthi Manicassamy和P.Dhavachelvan/IERI Procedia 4（2013）268273图6. 具有固定目标的图7. 可变目标图8. 生成最优解最佳情况、最坏情况和平均情况274Jayanthi Manicassamy和P.Dhavachelvan/IERI Procedia 4（2013）2684. 结论和未来的改进本文讨论了遗传算法中两种生物启发基因的功能：转换和感染。实验结果表明，该算法在求解约束优化问题时具有较好的效果。这种转换和传递对于本文未讨论的补充问题也同样有效。在未来，为了解决实时生物学基础上的问题，如缺陷基因的有效识别，可以通过转化和转感染来证明。目前的工作是通过所提出的方法来解决基于生物的问题。确认这项工作是印度UGC重大项目计划下研究项目的一部分参考编号：F.第40-258/2011（SR）号，2011年6月29日。作者谨对赞助机构提供的财政支持表示感谢。引用[1]V. K. Koumousis和C. P. Katsaras，“一种结合可变种群大小和重新初始化效果以提高性能的锯齿遗传算法”，IEEE进化计算学报，第10卷，第1期，第10 - 14页。2006年19[2]David W. Coit和Alice E.史密斯，“使用遗传算法优化组合可靠性设计问题”，2000年。[3]林志玲，[4]Heikki Maaranen，Kaisa M iettinen和Antti Pe nttinen，“关于连续优化问题的遗传算法的初始种群”，J G lob Optim.，Springer，pp. 405[5]王文，[6]A.S. Anagun和T.林志玲，[7]Arild Hoff et. 0/1多维背包问题的[8]Richardson，J.，Palmer，R.，Liepins，G.和Hilliard，M.，“Some Guidelines for Genetic Algorithms with PenaltyFunctions”, Proceedings of the Third International Conference on Genetic Algorithms, pp[9]Weingartner，H.M.Ness，D.N，“多维0/1背包问题的求解方法”，运筹学15，第83-103页，1993年[10]Domingo，Cesar Hervaz，[11]JC Vidal，[12]Claudio Mattiussi，Markus Waibel和Dario Floreano，“具有高度可重组基因组的个体之间的种群多样性和距离的测量”，进化计算，第12卷，第4页。495-515，2004年。[13]乔治·GDavid和Mark，[14]Amy FitzGerald和Diarmuid，[15]Jayanthi Manicassamy和P. Dhavachelvan，“人类疾病诊断自动化：时间序列分析”，ICWET 2010 -技术新兴趋势国际会议和研讨会，第100页。798-800，2010年。[16]Jayanthi Manicassamy，“基于Web的生物信息学工具检索能力的质量评估”，第二届计算机科学、工程和应用国际会议，ICCSEA，第10页。947-958，2012年。[17]C. Gondro和B.P.Kinghorn，“A simple genetic algorithm for multiple sequence alignment”，Journal of genetics andmolecular research evolution and technology，vol 6 no.4，pp. 964-984，2007年。[18]Jayanthi Manicassamy和P. Dhavachelvan，“基于文本挖掘工具的性能控制在生物信息学中”，计算，通信和控制进展国际会议论文集，ICAC3'09，pp. 171-176，2009年。