遗传算法机理的研究

《遗传算法机理的研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、!""#$%%%&’()*+,-./01,2",2340.5软件学报)%%%7$$89:;’<*=’*)66666666666666666666666666666666666666666666666666666666666遗传算法机理的研究>张铃$7?张钹)7?$8安徽大学人工智能研究所合肥)?%%?’:)8清华大学计算机科学与技术系北京$%%%(<:?8清华大学智能技术与系统国家重点实验室北京$%%%(<:@&A0B1;C1B/DE0F-G5H-GI/摘要众所周知7J模式定理K和J隐性并行性K是遗传算

2、法8D5/53BI01D,.B3FAL7简称MN算法:的两大理论基础G该文对这两个原理进行分析7指出这两个原理存在有不严格和不足之处7即作为MN算法的基础7这两个原理尚欠完善G为加深对MN的理解7文章提出遗传算法的一个新的改进模型OO理想浓度模型G通过对此模型的分析7得出遗传算法本质上是一个具有定向制导的随机搜索技术G其定向制导原则是7导向以适应度高的模式为祖先的染色体J家族K方向G最后给出两个典型的函数求最大值的模拟例子G从模拟结果看7改进后的MN算法大大提高了算法的速度7解的精度也有所提高G这说明新

3、算法具有应用的潜力G关键词遗传算法7模式定理7隐性并行性7遗传算法的理想浓度模型G中图法分类号PQ$(遗传算法由于其简单易行7在各个领域都得到了广泛应用7但是7MN8D5/53BI01D,.B3FAL:算法的运行机理并不十分清楚G对于MN算法的运行机理7也有一些研究者进行过研究GR0H,1SF在文献T$U中证明一般的MN算法不收敛7只有每次保存最优个体时才收敛GQ5.5V在文献T)U中就一类特殊的MN算法7给出收敛的充要条件GT

4、证明7当群体的容量无限大时7算法是收敛的GX,D01算法的收敛性G另一方面7人们普遍认为7MN算法之所以高效且具有强鲁棒性7是因为遗传算法中有J模式定理K和J隐性并行性K性质成立之故TZUG于是到目前为止7这两个性质被看作是遗传算法理论的两大基石G本文将对这两个性质进行分析研究7指出其不足之处7并在此基础上提出遗传算法的一个新的改进模型OO理想浓度模型G通过对此模型的分析7得出结论;遗传算法本质上是一个具有定向制导的随机搜索技术7其定向制导原则是7导向以适应度高的模式为祖先的染色体J家族K方向G最后7给

5、出两个典型的函数求最大值的模拟例子7从模拟结果看7改进后的MN算法大大提高了算法的速度7解的精度也有所提高G新算法具有应用的潜力G[模式定理的分析在文献T9U中7我们曾对模式定理进行过分析7指出模式定理的推论J结构块8即高适应度低阶短确定长的模式:在遗传过程中其个数将随代数按指数律增加K在一般情况下是不成立的7这里不再重复7详见文献T9UG关于结构块是否存在的问题也是很值得商讨的7因为从统计上来看7低阶一般就不会是高适应度G下面给出有关模式之间关系的简单的性质G定义[G设]$7])是两个给定的模式7

6、若]$的确定分量的集合是])确定分量集合的子集7则记为]$^])7称])是]$的子模式G>本文研究得到国家自然科学基金8#,GZ’Z9*%$$:国家(Z?高科技项目基金8#,G(Z?&?%Z&%*&%(&?:和国家’9?高科技项目基金8#,GM$’’(%?%*%’:资助G作者张铃7$’?9年生7教授7博士生导师7主要研究领域为人工智能理论7人工神经网络理论G张钹7$’?*年生7教授7博士生导师7中国科学院院士7主要研究领域为人工智能理论及应用7计算机应用G本文通万方数据讯联系人;张铃7合肥)?%%?’

7、7安徽大学人工智能研究所本文$’’(&$)&)’收到原稿7$’’’&%Z&$9收到修改稿X

8、遗传算法中6隐性并行性质7的分析让我们再来分析作为现有遗传算法理论的另一基石0遗传算法的隐性并行性质"89:*;*<=6隐性并行性质7的大意是0遗传算法有效处理的模式总数正比于群体规模3的立方*即其阶为#$3’"在进行分析之前*先作几个约定0染色体>*记为>($>其中>&*>,*"""*>)’*?-@A*&B"模式%*记为%($C其中C&*C,*"""*C)’*?-@A*&*DB"称染色体>属于模式%*若对一切C有>成立"这样*模式%就可理