遗传算法的发展现状与应用实例.htm

Matlab遗传算法工具箱: Matlab遗传算法工具箱

  <LI><A id=SingleColumn1_Categories_CatList__ctl11_LinkList__ctl22_Link 
  href="http://bingle.pku.edu.cn/" target=_blank>搜索7 天网搜索</A> 
  <LI><A id=SingleColumn1_Categories_CatList__ctl11_LinkList__ctl23_Link 
  href="http://www.smth.org/bbsxsearch.php" target=_blank>搜索8 令狐冲搜索</A> 
  <LI><A id=SingleColumn1_Categories_CatList__ctl11_LinkList__ctl24_Link 
  href="http://www.souke.net/" target=_blank>搜索9 BBS搜客</A> 
  <LI><A id=SingleColumn1_Categories_CatList__ctl11_LinkList__ctl25_Link 
  href="http://cho.icxo.com/worldrichlist.jsp" target=_blank>生活 财富排名</A> 
  <LI><A id=SingleColumn1_Categories_CatList__ctl11_LinkList__ctl26_Link 
  href="http://www.k3.cn/index.htm" target=_blank>生活网站0 火车时刻表</A> 
  <LI><A id=SingleColumn1_Categories_CatList__ctl11_LinkList__ctl27_Link 
  href="http://www.51ting.com/ziminglm/xiaofengzbs/xiaofengzhibo-g.htm" 
  target=_blank>生活网站1 小凤直播室</A> 
  <LI><A id=SingleColumn1_Categories_CatList__ctl11_LinkList__ctl28_Link 
  href="http://www.xlgt.com/Boards.asp" target=_blank>生活网站2 心灵沟通</A> 
  <LI><A id=SingleColumn1_Categories_CatList__ctl11_LinkList__ctl29_Link 
  href="http://www.eefoo.com/fortune/grsds.asp" target=_blank>生活网站8 易富理财</A> 
  <LI><A id=SingleColumn1_Categories_CatList__ctl11_LinkList__ctl30_Link 
  href="http://www.kaifulee.com/" target=_blank>生活网站9 李开复</A> 
  <LI><A id=SingleColumn1_Categories_CatList__ctl11_LinkList__ctl31_Link 
  href="http://www.95599.cn/" target=_blank>银行1 中国农业银行</A> 
  <LI><A id=SingleColumn1_Categories_CatList__ctl11_LinkList__ctl32_Link 
  href="https://www.sz1.cmbchina.com/script/BaseHttp.dll?HbLoadLoginPage?pageno=1&amp;date=0FriJul2044625UTC+08002004&amp;area=0021" 
  target=_blank>银行2 招商银行</A> </LI></UL>
<H3>Matlab</H3>
<UL>
  <LI><A id=SingleColumn1_Categories_CatList__ctl12_LinkList__ctl1_Link 
  href="http://www.matlab-world.com/" target=_blank>Matlab网站1 Matlab大观园</A> 
  <LI><A id=SingleColumn1_Categories_CatList__ctl12_LinkList__ctl2_Link 
  href="http://www.mathworks.com/matlabcentral/" target=_blank>Matlab网站2 
  matlabcentral</A> 
  <LI><A id=SingleColumn1_Categories_CatList__ctl12_LinkList__ctl3_Link 
  href="http://www.mathtools.net/" target=_blank>Matlab网站3 MathTools</A> 
  <LI><A id=SingleColumn1_Categories_CatList__ctl12_LinkList__ctl4_Link 
  href="http://perso.club-internet.fr/yazdiet/toolbox.html" 
  target=_blank>Matlab网站4 第三方工具箱</A> 
  <LI><A id=SingleColumn1_Categories_CatList__ctl12_LinkList__ctl5_Link 
  href="http://www.simwe.com/cgi-bin/ut/board_show.cgi?id=19&amp;age=30" 
  target=_blank>Matlab论坛2 仿真科技论坛</A> 
  <LI><A id=SingleColumn1_Categories_CatList__ctl12_LinkList__ctl6_Link 
  href="http://bbs.matwav.com/index.jsp" target=_blank>Matlab论坛3（研学论坛）</A> 
</LI></UL>
<H3>Open Source</H3>
<UL>
  <LI><A id=SingleColumn1_Categories_CatList__ctl13_LinkList__ctl1_Link 
  href="http://eclipse-plugins.2y.net/eclipse/index.jsp" 
  target=_blank>Eclipse－plugin1 </A>
  <LI><A id=SingleColumn1_Categories_CatList__ctl13_LinkList__ctl2_Link 
  href="http://www.eclipseplugincentral.com/" target=_blank>Eclipse－plugin2 
  central</A> 
  <LI><A id=SingleColumn1_Categories_CatList__ctl13_LinkList__ctl3_Link 
  href="http://www.sentom.net/index.asp?classid=3" target=_blank>Java开源1 
  sentom</A> 
  <LI><A id=SingleColumn1_Categories_CatList__ctl13_LinkList__ctl4_Link 
  href="http://jedit.sf.net/" target=_blank>Java开源2 Jedit </A>
  <LI><A id=SingleColumn1_Categories_CatList__ctl13_LinkList__ctl5_Link 
  href="http://viva.sourceforge.net/" target=_blank>Java开源3 Viva </A>
  <LI><A id=SingleColumn1_Categories_CatList__ctl13_LinkList__ctl6_Link 
  href="http://java-source.net/" target=_blank>Java开源4 JSN </A>
  <LI><A id=SingleColumn1_Categories_CatList__ctl13_LinkList__ctl7_Link 
  href="http://launch4j.sourceforge.net/" target=_blank>Java开源5 launch4j</A> 
  <LI><A id=SingleColumn1_Categories_CatList__ctl13_LinkList__ctl8_Link 
  href="http://sourceforge.net/projects/jedit-plugins/" 
  target=_blank>Jedit－plugin </A>
  <LI><A id=SingleColumn1_Categories_CatList__ctl13_LinkList__ctl9_Link 
  href="http://jython.sf.net/" target=_blank>Jython 官方主站</A> 
  <LI><A id=SingleColumn1_Categories_CatList__ctl13_LinkList__ctl10_Link 
  href="http://www.pycs.net/users/0000177/categories/jython/" 
  target=_blank>Jython网站1 Jythonic </A>
  <LI><A id=SingleColumn1_Categories_CatList__ctl13_LinkList__ctl11_Link 
  href="http://www.newsforge.com/" target=_blank>Linux网站1 Newsforge</A> 
  <LI><A id=SingleColumn1_Categories_CatList__ctl13_LinkList__ctl12_Link 
  href="http://www.devlib.org/Programming/Languages/Lisp/index.php" 
  target=_blank>Lisp网站1 Lisp资源</A> 
  <LI><A id=SingleColumn1_Categories_CatList__ctl13_LinkList__ctl13_Link 
  href="http://python.cn/" target=_blank>Python网站1 中文社区</A> 
  <LI><A id=SingleColumn1_Categories_CatList__ctl13_LinkList__ctl14_Link 
  href="http://www.scipy.org/" target=_blank>Python网站2 SciPy</A> 
  <LI><A id=SingleColumn1_Categories_CatList__ctl13_LinkList__ctl15_Link 
  href="http://psyco.sourceforge.net/" target=_blank>Python网站3 Psyco</A> 
  <LI><A id=SingleColumn1_Categories_CatList__ctl13_LinkList__ctl16_Link 
  href="http://www.planetpython.org/" target=_blank>Python网站4 Planet Python</A> 
  <LI><A id=SingleColumn1_Categories_CatList__ctl13_LinkList__ctl17_Link 
  href="http://www.devlib.org/Programming/Languages/Python/index.php" 
  target=_blank>Python网站6 Python资源</A> </LI></UL>
<H3>UI</H3>
<UL>
  <LI><A id=SingleColumn1_Categories_CatList__ctl14_LinkList__ctl1_Link 
  href="http://bbs.flasher123.com/" target=_blank>Flash论坛1 闪客启航</A> 
  <LI><A id=SingleColumn1_Categories_CatList__ctl14_LinkList__ctl2_Link 
  href="http://www.flasherclub.com/bbs/board.asp" target=_blank>Flash论坛2 
  闪客俱乐部</A> 
  <LI><A id=SingleColumn1_Categories_CatList__ctl14_LinkList__ctl3_Link 
  href="http://www.chinaui.com/bbs/index.asp" target=_blank>UI论坛1 中国UI</A> 
  <LI><A id=SingleColumn1_Categories_CatList__ctl14_LinkList__ctl4_Link 
  href="http://www.blueidea.com/bbs/" target=_blank>UI论坛2 BlueIdea</A> 
  <LI><A id=SingleColumn1_Categories_CatList__ctl14_LinkList__ctl5_Link 
  href="http://www.cnsxml.com/" target=_blank>UI论坛3 CNXML</A> 
  <LI><A id=SingleColumn1_Categories_CatList__ctl14_LinkList__ctl6_Link 
  href="http://xulnews.com/" target=_blank>XULNEWS</A> </LI></UL>
<H3>wiki</H3>
<UL>
  <LI><A id=SingleColumn1_Categories_CatList__ctl15_LinkList__ctl1_Link 
  href="http://zh.wikipedia.org/wiki/首页" target=_blank>wiki网站2 中文wiki百科</A> 
  <LI><A id=SingleColumn1_Categories_CatList__ctl15_LinkList__ctl2_Link 
  href="http://en.wikipedia.org/wiki/Main_Page" target=_blank>wiki网站5 
  英文wikipendia</A> 
  <LI><A id=SingleColumn1_Categories_CatList__ctl15_LinkList__ctl3_Link 
  href="http://wikibooks.org/wiki/Main_Page" target=_blank>wiki网站6 wikiBook</A> 
  <LI><A id=SingleColumn1_Categories_CatList__ctl15_LinkList__ctl4_Link 
  href="http://bbs.dartmouth.edu/~fangq/wiki/?MathTools_FAQ" 
  target=_blank>wiki网站8 数学工具FAQ </A></LI></UL></DIV>
<DIV id=main>
<SCRIPT>document.write("<img src=http://count.csdn.net/count/pageview1.asp?columnid=22&itemid=67 border=0 width=0 height=0>");</SCRIPT>

<DIV class=post>
<H2><A id=viewpost.ascx_TitleUrl 
href="http://blog.csdn.net/yuanqingfei/articles/33203.aspx">遗传算法的发展现状与应用实例</A> 
</H2><SPAN class=javascript id=text57129><BR>.<BR>1&nbsp;&nbsp;引言<BR>近年来 ,遗传算法 
(GA)的卓越性能引起人们的关注 .对于以往难以解决的函数优化问题 ,复杂的多目标规划问题 ,工农业生产中的配管、配线问题 ,以及机器学习 ,图象识别 
,人工神经网络的权系数调整和网络构造等问题 ,GA是最有效的方法之一 .虽然GA在许多优化问题中都有成功的应用 ,但其本身也存在一些不足 
.例如局部搜索能力差、存在未成熟收敛和随机漫游等现象 ,从而导致算法的收敛性能差 ,需要很长时间才能找到最优解 ,这些不足阻碍了遗传算法的推广应用 
.如何改善遗传算法的搜索能力和提高算法的收敛速度 ,使其更好地应用于实际问题的解决中 
,是各国学者一直探索的一个主要课题.之后世界范围内掀起了关于遗传算法的研究与应用热潮 
<BR>2&nbsp;&nbsp;遗传算法存在的问题及相应的改进措施<BR>自然界早已显示出了基因的强大威力 ,通过这种机制 
,一系列的具有智能、自组织、自修整的器官产生了 .人们要在科学研究中效仿这些生物器官 ,那么就必须了解基因、进化的概念 
.GA就是这样一种利用自然选择和进化思想在高维空间中寻优的方法 ,它不一定能寻得最优点 ,但是它可以找到更优 点 ,这种思路与人类行为中成功的标准是很相似的 
.例如不必要求一支军队是最优的 ,要战胜对手只需它比对手更强即可 .因此 GA可能会暂时停留在某些非最优点上 ,直到变异发生使它跃居到另一个更优点上 . 
GA寻优过程的一个重要特点是它始终保持整个种群的进化 ,这样即使某个体在某时刻丧失了有用的特征 ,这种特征也会被其他个体所保留并延续发展下去 .由于 
GA仅需知道目标函数的信息 ,而不需要其连续可微等要求 ,因而具有广泛的适应性 .同时它又是一种采用启发性知识的智能搜索算法 
,所以往往能在搜索空间高度复杂的问题上取得比以往算法 (如梯度法 )更好的效果D. B. Fogel提出的进化即智能的概念[1 0 ],虽然还没有被普遍接受 
,但进化在人类生存进步过程中的重要性已可见一斑 ,因此遗传算法作为生物进化思想在工程计算中的一种体现 ,其前途是光明的 .目前 
GA在工程优化、信号处理、模式识别、管理决策、智能系统设计和人工生命等领域的成功利用正说明了这一点 .<BR>2. 1　编码表示<BR>　　 
Holland在运用模式定理分析编码机制时 ,建议使用二进制编码 ,但二进制编码不能直接反映问题的固有结构 ,精度不高 ,个体长度大 ,占用计算机内存多 . 
Gray编码是将二进制编码通过一个变换进行转换得到的编码 ,其目的就是克服 Hamming悬崖的缺点,动态编码 (dynamic 
encoding)GA是当算法收敛到某局部最优时增加搜索的精度 ,从而使得在全局最优点附近可以进行更精确的搜索 
,增加精度的办法是在保持串长不变的前提下减小搜索区域 .对于问题的变量是实向量的情形 ,可以直接采用实数进行编码 ,这样可以直接在解的表现型上进行遗传操作 
,从而便于引入与问题领域相关的启发式信息以增加算法的搜索能力.复数编码[5]的GA是为了描述和解决二维问题 ,基因用 x+yi 表示 
;其还可以推广到多维问题的描述中 .多维实数编码[6 ]GA,使无效交叉发生的可能性大大降低 ,同时其合理的编码长度也有助于算法在短时间内获得高精度的全局最优解 
.在组合优化中 ,可以使用有序串编码 ,例如在文献 [7]中用自然数编码巧妙地解决了VRP问题 .当问题的表示是树和图时 ,我们还可以使用结构式编码<BR>2. 
2　适应度函数<BR>适应度函数是用来区分群体中个体好坏的标准 ,是自然选择的唯一标准 ,选择的好坏直接影响算法的优劣 
.引入适应值调节和资源共享策略可以加快收敛速度和跳出局部最优点 .对适应值进行调节就是通过变换改变原适应值间的比例关系 
,常用的比例变换有线性变换、乘幂变换和指数变换等 .对于一个问题具体采用什么变换才能达到较优的效果 ,V. Kreinovich等在文献 
[8]中做了较详细的讨论 而在文献 [9]中则是采用共享的技术 ,对子群的形成和稳定起了一定作用 ,文中主要用子群消失时间的近似形式估计 Sharing的界 
.文献 [1 0 ]中采用了依据搜索进展可变的适应值函数 ,并应用于 CuttingProblem取得较好效果 .文献 [1 1 
]中设计了自适应选取遗传算法的适应值函数的方法 ,该方法的计算量要比排序选择操作的计算量小的多 ,而且有效的避免了算法的非成熟收敛 .<BR>2 . 
3　选择策略<BR>　　优胜劣汰的选择机制使得适应值大的个体有较大的存活机会 ,不同的选择策略对算法性能有较大的影响 .轮盘赌法是使用最多的选择策略 
,但这种策略可能会产生较大的抽样误差 ,于是对此提出了很多的改进方法 ,如繁殖池选择[1 2 ],Boltzmann选择[1 3 ]等等 
.但是这几种策略都是基于适应值比例的选择 ,常常会出现早熟收敛现象和停滞现象 .为此又提出了非线性排名选择[3 ],这种选择不仅避免了上述问题 
,而且可以直接使用原始适应值进行排名选择 ,而不需对适应值进行标准化 ;但这种选择在群体规模很大时 ,其额外计算量 (如计算总体适应值和排序 )也相当可观 
,甚至在进行并行实现时有时要带来一些同步限制 .基于局部竞争机制的选择如 (λ+μ)选择[1 4],它使双亲和后代有同样的生存竞争机会在一定程度上避免了这些问题 
.在 [1 5]中作者采用<BR>了类似梯度的方式来选择 ,不仅使较差的染色体比较好的染色体得到更大的改进 ,而且还不断产生新的个体 
,从而不断拓展了新的搜索空间 . [1 6 ]中作者<BR>引入了 Harvesting Strategies来分析遗传算法的性能 ,Harvesting 
Strategies是指在每一代交叉和突变后进行两次乃至多次筛选作为下面的群体 .采用了 Disruptive Selection,它吸收了优等和劣等个体 
,实验结果表明了两极分化有可能更容易找到最优解 .为了提高种群的多样性 ,提出一种基于免疫多样性的选择算子[1 8],该选择算子依赖于串的稠密度和适应值 
,串的稠密度越大 ,其保留下来的可能性越小 ,具体事例证明改进算法是有效的 .<BR>2 . 4　控制参数<BR>　　控制参数一般有群体大小 ,交换概率 
,变异概率等 ,这些参数对遗传算法性能影响较大 .在标准的遗传算法中采用经验进行估计 ,这将带来很大的盲目性 ,而影响算法的全局最优性和收敛性 
.目前许多学者意识到这些参数应该随着遗传进化而自适应变化 ,Davis提出自适应算子概率方法 [1 
9],即用自适应<BR>机制把算子概率与算子产生的个体适应性结合 ,高适应性值被分配高算子概率 . Whitley提出一种自适应突变策略与一对父串间的 
Hamming距离成反比 [2 0 ],结果显示能有效地保持基因的多样性 .张良杰等通过引入 i位改进子空间概念 
,采用模糊推理技术来确定选取突变概率的一般性原则 [2 1 ].在文献[2 2 ]中设计了一种群体规模可变的遗传算法