遗传算法的编码理论与应用new

《遗传算法的编码理论与应用new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、万方数据遗传算法的编码理论与应用余有明1’2刘玉树1阎光伟3(北京理工大学计算机科学工程系，北京100081)2(北京石油化工学院计算机系，北京102617)3(华北电力大学计算机系，北京102206)E-mail：yuyouming@biptedu．cn摘要编码是遗传算法求解问题的前擐．文章分析了二进制编码、格雷码编码、实数编码、符号编码、排列编码、二倍体编码、DNA编码、混合编码、二堆染色体编码或矩阵编码等编码的实质内容．在树编码和可变长编码基础上阐述了自适应编码的基本理论．提出了基于相似度的可变长编码和基于结构的

2、agent编码方式．给出了函数优化、TSP、KP、JsP、机器人路径规划、囤的划分和倒立摆等典型优化问题的鳊码方案。关键词遗传算法遗传编码智能体编码文章编号l002—8331-(2005)35—0086—04文献标识码A中图分类号TN919．81；TP301．6EncodingTheoryandApplicationofGeneticAlgorithmYuYoumin912LiuYushulYanGuangweP1(ComputerScienceandEngineeringDept．，BeringInstituteof

3、Technology，Bering100081)2(ComputerDept．，BeringInstituteofPetrochemicalTechnology，Bering102617)3(ComputerDept．，NorthChinaElectricPowerUniversity，Beijing102206)Abs”act：EncodingisGeneticalgorithm'spremisetosolveproblemsThispaperanalvzesbinaryencodingmechanismofbina

4、rycoding，Graycoding，realcoding，symbolcodmg，rankcoding，diploidcoding，DNAcoding，hybridcoding，2一Dclktolno$onlecodingormatrixcodingandothers，expatiatesbasictheoryofadaptiveencodingbasedontreecodingandlen昏hchangeablecoding，putsforwardencodingmethod8oflenuhchangeablec

5、odingbasedonsimilaritydegreeandagentcodingbasedonsfftlCtoredescription，andpresentssomeencodingplansfortypicaloptimizationpmblemsoffunctionsoptimizatloa，TSP，KP，JSP，robotroutelayout，graphpartitionandheadstandpendulumKeywords：geneticatgonthm，geneticencoding，agenten

6、coding1引言遗传算法(GeneticAIgorithm，GA)自20世纪70年代初提出以来，在许多领域的理论与T程实践中都有成功的应用。其编码方法也在不断地改进，最基本的是二进制编码，其它的编码方法有格雷码、实数编码、符号编码、多参数编码和DNA编码等，并在相关领域的优化应用中取得了很好的效果口I。本文系统地分析了月前比较成熟的编码方法。并提出基于自适应思想的编码方案，论述了不同问题应该采用的编码类型．为智能化求解复杂问题的编码提供了参考方案。2遗传算法的编码原则关于遗传编码的原则．Balakrishman等比较

7、全面地讨论了不同编码方法的特性，针对不同的应用，为设汁和选择编码方法提供了指南，主要有以下的9个特性：完备性(complete—Bess)、封闭性(closure)、紧致性(compactness)、可扩展性(scala—bility)、多重性(multiplicity)、个体町塑性(flexibility)、模块性(modularity)、冗余性(redundancv)与非冗余性(noredundancy)和复杂性(coinplexi竹)。。3遗传算法的基本编码理论3．1二进制编码遗传算法中常用的编码方法是二进制编码

8、，它将问题空问的参数用字符集f0，11构成染色体位串，符台最小字符集原则，便于用模式定理分析，但存在映射误差。对于rt(n≥1)维连续函数f(x)，*=(她，z2，·，*。)，z．Eh，”d，(i=1，2，⋯，^)采用定长二进制编码，建立位串空间。各维变量的二进制编长为l。耶么*的编码从左到右依次构成总长度为L=∑1．的二进制编码