显隐性二倍体编码在moga中的应用及其可行性证明

《显隐性二倍体编码在moga中的应用及其可行性证明》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2010年9月内蒙古大学学报(自然科学版)Sept．2010第41卷第5期JournalofInnerMongoliaUniversityVoI．41NO．5文章编号：1000—1638(2010)05-0551—05显隐性二倍体编码在MOGA中的应用及其可行性证明李娜，仁庆道尔吉，曹军。(1．内蒙古工业大学理学院，呼和浩特010051；2．西安电子科技大学理学院，西安710071；3．内蒙古大学数学科学学院，呼和浩特010021)摘要：遗传算法是一种以种群进化为基础的全局优化搜索算法，并且自然界的高等

2、生物的染色体结构形式是二倍体或多倍体，即有显隐性之分．结合以上两种理念，引进一种显隐性二倍体编码方法，并应用于多目标遗传算法(MOGA)中，通过分析在一般的锦标赛选择、两点交叉、基本位变异三种最基本的遗传操作作用下，模式在下一代的样本数，证明了显隐性二倍体编码的模式定理．从理论上说明这种编码在多目标遗传算法中是可行的，为进一步数值实验提供基础．关键词：显隐性二倍体编码；多目标遗传算法；解群；模式定理中图分类号：TP301．6文献标志码：A二倍体结构中的各个基因有显、隐性之分，并通过以下规则使个体呈现某种

3、表现型：当两个同源染色体其中一个是显性基因时，则该基因对应的性状表现为显性，仅当两个同源染色体都为隐性基因时，该基因对应的性状表现才为隐性．最早提出考虑多倍体和显性的遗传算法是Bagley的博士论文，1967年Rosenberg的以生物学为导向的研究中也包括了一个多倍染色体模型，1971年，Hollstien的研究中提出了二倍体与显性操作的双基因座显性映射方法．Hollstien将这种映射关系简化为单基因座显性映射方法，Holland对这种单基因座的显性映射方法进行了改进，1987年，Smith和Gol

4、dberg比较了单倍体和二倍体技术在“非稳定背包问题”优化方面的性能差异．研究表明基于人工生命的遗传进化模型。非常适合求解多目标优化问题，这一算法即为多目标遗传算法，它能使得进化群体并行搜索多个目标，并逐渐找到问题的最优解“，已有的比较典型的多目标遗传算法主要有以下几种：1)向量评估遗传算法；2)多目标遗传算法；3)非劣分层遗传算法；4)小组决胜遗传算法；5)改进的非劣分层遗传算法．考虑一种多目标进化算法，主要的问题就是确定它的编码、遗传操作算子以及初始化和终止条件．而以上算法用的都是二进制或十进制编码

5、，本文第一次将显隐性二倍体编码应用于多目标遗传算法中，并通过模式定理证明其理论上的可行性．1显隐性二倍体编码介绍1．1映射关系Hollstien研究的单位点三进制二倍体编码中，基因1有显性和隐性之分，而0只有显性．在自然界中每个基因都会有显隐性之分，本文引入的这种显隐性二倍体编码，基因1和0都有显隐性之分，*收稿日期：2009一l1—20：修回日期：2010—05—20作者简介：李娜(1982一)，内蒙古包头市人，讲师，硕士内蒙古大学学报(自然科学版)用1、0分别表示显性1、0，用1、0分别表示隐性1、

6、0，映射关系如表1所示．OO11表1+编一码映T射关系表2单基因座显隐性映射表Table1MappingofcodesTable2Dominantandrecessivemapofsinglegenes基因座0OO01O11基因座1234OOlO为便于书写，本}文将0、I0一、1、1分别对应写为1、2、3、4，这样就可以得到单基因座显隐性映射表，如表2所示．1．2编码与解码OO1l设二倍体编码基因长度为L，参数取值范围是[x⋯，X]，要求精度为prec，则L一2×ceil『log2](1)L“J其中，函

7、数ceil[x]表示取大于x的最小整数．显隐性二倍体编码的基因型为1、2、3、4，与二进制编码比较，可以看出二倍体编码长度是二进制GA编码长度的二倍．解码时，先将二1倍体2编3码4转换为二进制，再由二进制转换为十进制，然后对应于参数空间[x⋯，X⋯]即可．假设某个体的基O因O串为1XO：alan。⋯a，依据表2，转换为二进制编码串为：b_L。bb⋯b，22』，2转换为十进制数为：X一bX2一，转换为区间Ex⋯，x]的数为：0O1Ot一1X一X+X×蔷．(2)}l与二进制GA解码相比，显隐性二倍体编码只是

8、多了将基因串映射为二进制基因串这一步．2显隐性二倍体编码多目标遗传算法的可行性证明OO11模式定理是遗传算法的理论基础．它保证了较优的模式(GA的较优解)的数目呈指数增长，为解释GA的机理提供了一种数学工具，它是目前影响最广、研究最多的一种GA理论．当前，已经证明的模式定理及相关理论都是关于二进制编码和十进制编码的．为了证明显隐性二倍体编码的可行性，本文借鉴以上两种编码模式定理的推导思路和过程，证明了显隐性二倍体编码方法的模式定理，从而给这