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

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

,它提出每个个体应当有年龄及生命期的概念并淘汰年龄大于生命期的个体从而使遗传算法动态的控制了群体数目 ,这种方法可以找出一个接近最小代价的遗传算法 
,同时尽量将群体规模保持在现有水平 ,防止群体规模的指数级增长 ,以降低计算的开销 .丁承明等提出利用正交试验法去优化选取 GA控制参数 [2 3 
],这种方法利用正交试验的均衡分散性使得通过较少的试验次数就可搜索绝大部分参数组合空间 ,而且还可以确定哪个参数对 GA结果影响最显著 
,然后有针对性地进行精确搜索 ,从而使得 GA参数问题得到圆满解决 .为保证种群的有用多样性 ,提出动态群法[2 4],即当迭代到一定代数 ,若目标函数的值相同 
,则现存种群中的较差的 N个染色体被随机产生的 N个染色体代替 ,使进化过程中不断有新个体引入 . [2 5]中用模糊规则对选择概率和变异概率进行控制 
,在线改变其值 ,相应的算例表明 ,有较好的性能<BR>2. 5　遗传算子<BR>　　基本遗传算法中采用单点交叉算子和简单的变异算子 .它们操作比较简单 
,计算量小 ,但是在使用过程中有很大的局限性 ,例如 :由于单点交叉破坏模式的概率较小 ,至使搜索到的模式数也较少 ,使算法具有较低的搜索能力 . Feng 
etal.对多维连续空间的GA的杂交多样性进行了分析 ,通过建立相应的数学模型 ,Feng解释了在多维连续空间和大规模群体中使用均匀杂交算子[2 6 
]是如何探索新的解空间区域 .为了使得变异能够根据解的质量自适应的调整搜索区域 ,从而能较明显地提高搜索能力 ,提出自适应变异算子[2 
7].为了保护适应值较高的模式 ,提出自适应交叉和变异 [2 8],如果遇到适应值较高的模式 ,则通过随机引入模式外的位而进行保护 .为了克服早熟 ,引入多种群 
GA[2 9],不同种群赋以不同的控制参数 ,实现不同的搜索目的 ,通过移民算子联系各种群 ,通过人工选择算子保存各种群每个进化代中的最优个体 
.为了防止近亲繁殖 ,扩大种群的多样性 ,抑制超长个体的快速繁殖 ,引进近亲繁殖算子 ,两个个体是否为近亲可用基因片段的 Hamming距离来判断 ,距离越大 
,则为近亲的可能越小 ;为加强局部搜索能力 ,增加漂移算子 ,将染色体各基因片段的后二分之一的基因分别按一定的概率做 1的随机漂移 
,排位越后的基因漂移的概率越大 ,由此产生一定数量的新个体 ,用基因预选机制的小生境技术控制漂移方向 [3 0 ].因为格点法产生的点集能均匀地分布于搜索空间 
,并且佳点又是最好的格点 ,所以可以用数论中的佳点集理论设计交叉算子[3 1 ],结果表明它的搜索效果要比纯随机法好 ,而且有效的避免早熟现象 
.基于生物免疫性提出的免疫算子 [3 2 ],能够明显抑制进化过程中的退化现象 ,减轻 GA后期的波动 ,从而提高了搜索效率和收敛速度 . [3 3 ]中提出的 
SRM(self-reproduction)算子增强了种群的多样性 ,CM(crossove and mutation)算子促进了有利变异的增加 
,从而使算法大大节省了存贮空间和运行时间 .采用“尺度收缩”策略的混沌变异算子 [3 4]能明显的改善群体平均适应值 ,提高算法的性能 
,是解决优化问题的有效方法 .<BR>2 . 6　综合方面<BR>文献 [3 5]中提出了可分解 /可拼接 GA编码 
,并基于此编码分别在种群层次和基因层次发展了动态变异和动态选择操作 ,这种方法很大程度上避免了早熟问题 .增强型 GA[3 6 ]中 
,引入了几个新算子和新的种群迁移策略 ,并用其对模糊逻辑控制器进行设计 ,得到了便于理解的模糊集和模糊规则 .用小波分析中的多尺度分析对 
GA中的染色体进行多尺度分解 ,这样分解后的染色体的长度变短 ,基因交换、变异等遗传操作更为彻底 ,有效的克服了基因丢失引起的早熟问题 [3 
7].小生境技术不仅能够保证群体中解的多样性 ,而且具有很强的引导进化能力 ,所以小生境技术的引入 ,提高了 GA处理多峰函数优化问题的能力[3 
8].将模拟退火过程引入遗传算法[3 9],在优选交叉和变异个体的过程中加入一定的“扰动”,以达到保持种群内位串的多样性和位串之间的竞争机制 
,克服了算法易陷于极小点的问题 ,使得搜索沿着全局最优方向进行 .广义遗传算法[40 ],它以多点突变操作为主 ,以基因交叉操作为辅 
,实现了从一个局部最优状态到另一个局部最优状态的转移 ,使算法获得全局最优 .为了使 GA用于约束优化 ,提出一种非稳态罚函数 GA[41 
],非稳态罚函数是遗传代数的函数 ,当代数增加时 ,罚函数也随着增大 ,同时给GA带来更多的选择压力 ,促使 GA找到可行解 
.综合遗传算法的全局性和神经网络的并行快速性等特点 ,提出的遗传神经网络算法[42 ],可克服遗传算法最终进化至最优解较慢和神经网络易陷入局部解的缺陷 
,具有较好的全局性和收敛速度 .采用面向对象技术设计了面向对象遗传算法[43 ],这种方法改变了在传统的 GA中各个函数之间只有参数的传递 
,而没有代码的继承性的状况从概念上提高了软件的可重用性 ,用户可以更方便的设计和实现自己的编码方案和遗传算子 
.变异基遗传算法[44],采用变异算子进行局部优化搜索 ,并利用随机初始化技术使算法在局部搜索能力提高的同时仍有可能寻找到全局最优解 
.贪婪遗传算法[45]用在二次分配问题中取得了较好的效果 ,在该算法中引入了新的交叉算子和移民算子 ,保证了种群的多样性 ;并且通过比赛竞争使得各种群得到进化 
,很好的解决了种群多样性及对个别好个体偏爱之间的矛盾 .<BR>3　遗传算法的发展动向 (GA' s developmen-tal 
trends)<BR>GA在应用方面的丰硕成果 ,使人们对它的发展前景充满信心 .其主要应用领域在于函数优化 (非线性 ,多模型 ,多目标等 ),机器人学 
(移动机器人路径规划 ,关节机器人运动轨迹规划 ,细胞机器人的结构优化等 ),控制 (瓦斯管道控制 ,防避导弹控制 ,机器人控制等 ),规划 (生产规划 
,并行机任务分配等 ),设计 (VLSI布局 ,通信网络设计 ,喷气发动机设计等 ),组合优化 (TSP问题 ,背包问题 ,图分划问题等 ),图象处理 
(模式识别 ,特征提取 ,图象恢复等 ),信号处理 (滤波器设计等 ),人工生命 (生命的遗传进化等 ).此外遗传算法的研究出现了几个引人注目的新动向 
:<BR>3 . 
1　基于遗传算法的机器学习<BR>这一新的研究方向把遗传算法从历史离散的搜<BR>索空间的优化搜索算法扩展到具有独特的规则生成功能的崭新的机器学习算法 
.这一新的学习机制对于解决人工智能中知识获取和知识优化精炼的瓶颈难题带来了希望 .遗传算法作为一种搜索算法从一开始就与机器学习有着密切联系 .分类器系统 
CS-1是 GA的创立者 Holland教授等实现的第一个基于遗传算法的机器学习系统 .分类器系统在很多领域都得到了应用 .例如 
,分类器系统在学习式多机器人路径规划系统中得到的成功应用 ; Goldberg研究了用分类器系统来学习控制一个煤气管道仿真系统 
;Wilson研究了一种用于协调可移动式视频摄像机的感知—运动的分类器系统等 .分类器系统在基于遗传算法的机器学习研究中影响很大 
,但具体实现方法和要解决的具体问题有关 .基于遗传算法的概念学习是近几年来机器学习领域的一个较为引人注目的研究方向 ,由于概念学习隐含的搜索机制 
,使得遗传算法在概念学习中有用武之地 .目前也有一些嵌入领域知识的基于遗传算法的机器学习的研究 ,如将概念学习中特有的操作遗传操作化 ,并显示出一定的优点 
.此外 ,学习分类系统的并行实现在基于遗传算法的机器学习研究中也占有相当的分量 .<BR>3 . 
2　遗传算法与其他计算智能方法的相互渗透和结合<BR>遗传算法正日益和神经网络、模糊推理以及混沌理论等其他智能计算方法相互渗透和结合 ,必能达到取长补短的作用 
.近年来在这方面已经取得不少研究成果 ,并形成了“计算智能”的研究领域 ,这对开拓 2 1世纪中新的智能计算技术将具有重要的意义 . GA的出现使神经网络的训练 
(包括连接权系数的优化、网络空间结构的优化和网络的学习规则优化 )有了一个崭新的面貌 ,目标函数既不要求连续 ,也不要求可微 ,仅要求该问题可计算 
,而且它的搜索始终遍及整个解空间 ,因此容易得到全局最优解 .GA与神经网络的结合正成功的被用于从时间序列的分析来进行财政预算 ,在这些系统中 
,训练信号是模糊的 ,数据是有噪声的 ,一般很难正确的给出每个执行的定量评价 ,如采用 GA来学习 ,就能克服这个困难 ,显著提高了系统的性能 . 
Muhlenbein分析了多层感知机网络的局限性 ,并猜想下一代神经网络将会是遗传神经网络 .遗传算法还可以用于学习模糊控制规则和隶属度函数 
,从而更好地改善模糊系统的性能 .文献 [46 ]中将模糊逻辑、神经网络和遗传算法三者有机的结合起来应用于温室夏季温湿度控制中 
,实验结果表明得到了良好的控制效果 .混沌表现出的随机性是系统内在的随机性 ,被称为伪随机性 ,它在生物进化中起着重要的作用 ,是系统进化与信息之源 
.混沌与遗传算法的结合已有人进行过尝试 ,如吴新余等[47]采用多种混沌模型构造随机开关 ,以此控制交叉操作以改进 GA的性能 .文献 [3 4]中更加直接 
,采用混沌序列构造变异算子 ,为遗传算法的实现开辟了新的途径 .<BR>3 . 3　并行处理的遗传算法<BR>并行处理的遗传算法的研究不仅是遗传算法本身的发展 
,而且对于新一代智能计算机体系结构的研究都是十分重要的 . GA在操作上具有高度的并行性 ,许多研究人员都正在探索在并行机上高效执行 GA的策略 
.近几年也发表了不少这方面的论文 ,研究表明 ,只要通过保持多个群体和恰当地控制群体间的相互作用来模拟并执行过程 ,即使不使用并行计算机 
,我们也能提高算法的执行效率 .在并行GA的研究方面 ,一些并行 GA模型已经被人们在具体的并行机上执行了 ;并行 GA可分为两类 :一类是粗粒度并行 
GA,它主要开发群体间的并行性 ,如Cohoon分析了在并行计算机上解图划分问题的多群体 GA的性能 ;另一类是细粒度 GA,它主要开发一个群体中的并行性 ,如 
Kosak将群体中的每个个体映射到一个连接机的处理单元上 ,并指出了这种方法对网络图设计问题的有效性 .<BR>3 . 
4　遗传算法与人工生命的渗透<BR>人工生命是用计算机、机械等人工媒体模拟或构造出的具有自然生物系统特有行为的人造系统 ,人工生命与遗传算法有着密切的关系 
,基于遗传算法的进化模型是研究人工生命现象的重要理论基础 .虽然人工生命的研究尚处于启蒙阶段 
,但遗传算法已在其进化模型、学习模型、行为模型、自组织模型等方面显示出了初步的应用能力 ,并且必将得到更为深入的应用和发展 .人工生命与遗传算法相辅相成 
,遗传算法为人工生命的研究提供了一个有效的工具 ,人工生命的研究也必将促进遗传算法的进一步发展 .<BR>3 . 
5　遗传算法与进化规则及进化策略的结合<BR>遗传算法、进化规则及进化策略是演化计算的三个主要分支 
,这三种典型的进化算法都以自然界中生物的进化过程为自适应全局优化搜索过程的借鉴对象 ,所以三者之间有较大的相似性 ;另一方面 
,这三种算法又是从不完全相同的角度出发来模拟生物的进化过程 ,分别是依据不同的生物进化背景、不同的生物进化机制而开发出来的 ,所以三者之间也有一些差异 
.随着各种进化计算方法之间相互交流深入 ,以及对各种进化算法机理研究的进展 ,要严格地区分它们既不可能 ,也没有必要 
.在进化计算领域内更重要的工作是生物进化机制 ,构造性能更加优良、适应面更加广泛的进化算法 .<BR>4　结论 <BR>遗传算法作为一种非确定性的拟自然算法 
,为复杂系统的优化提供了一种新的方法 ,并且经过实践证明效果显著 .尽管遗传算法在很多领域具有广泛的应用价值 ,但它仍存在一些问题 
,各国学者一直在探索着对遗传算法的改进 ,以使遗传算法有更广泛的应用领域 
.<BR>总之,遗传算法的未来是非常的美好的,只要我们对它们进行细致的分析,对它的缺点加以改造,优点进行继承,把它应用到我们的生产当中去,这样在生产当中还可以对它的缺点进行完善. 
</SPAN><BR>
<P class=postfoot>posted on 2004年07月03日 5:53 PM </P></DIV><LINK 
href="http://blog.csdn.net/yuanqingfei/Services/Pingback.aspx" rel=pingback><!--
<rdf:RDF xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
xmlns:dc="http://purl.org/dc/elements/1.1/"
xmlns:trackback="http://madskills.com/public/xml/rss/module/trackback/">
<rdf:Description
rdf:about="http://blog.csdn.net/yuanqingfei/articles/33203.aspx"
dc:identifier="http://blog.csdn.net/yuanqingfei/articles/33203.aspx"
dc:title="遗传算法的发展现状与应用实例"
trackback:ping="http://blog.csdn.net/yuanqingfei/services/trackbacks/33203.aspx" />
</rdf:RDF>
--><A name=feedback>
<DIV id=comments>
<H3>Feedback</H3>本文尚无评论。 </DIV>
<DIV id=commentform>
<TABLE cellSpacing=1 cellPadding=1 border=0>
  <TBODY>
  <TR>
    <TD width=75>Title</TD>
    <TD><INPUT id=PostComment.ascx_tbTitle style="WIDTH: 300px" size=40 
      value=回复：遗传算法的发展现状与应用实例 name=PostComment.ascx:tbTitle></TD>
    <TD><SPAN id=PostComment.ascx_RequiredFieldValidator1 
      style="VISIBILITY: hidden; COLOR: red" initialvalue="" 
      evaluationfunction="RequiredFieldValidatorEvaluateIsValid" 
      errormessage="Please enter a title" 
      controltovalidate="PostComment.ascx_tbTitle">Please enter a 
  title</SPAN></TD></TR>
  <TR>
    <TD width=75>Name</TD>
    <TD><INPUT id=PostComment.ascx_tbName style="WIDTH: 300px" size=40 
      name=PostComment.ascx:tbName></TD>
    <TD><SPAN id=PostComment.ascx_RequiredFieldValidator2 
      style="VISIBILITY: hidden; COLOR: red" initialvalue="" 
      evaluationfunction="RequiredFieldValidatorEvaluateIsValid" 
      errormessage="Please enter your name" 
      controltovalidate="PostComment.ascx_tbName">Please enter your 
    name</SPAN></TD></TR>
  <TR>
    <TD>Url</TD>
    <TD><INPUT id=PostComment.ascx_tbUrl style="WIDTH: 300px" size=40 
      name=PostComment.ascx:tbUrl></TD>
    <TD></TD></TR>
  <TR>
    <TD colSpan=3>Comments&nbsp; <SPAN 
      id=PostComment.ascx_RequiredFieldValidator3 
      style="VISIBILITY: hidden; COLOR: red" initialvalue="" 
      evaluationfunction="RequiredFieldValidatorEvaluateIsValid" 
      errormessage="Please enter a comment" 
      controltovalidate="PostComment.ascx_tbComment">Please enter a 
      comment</SPAN><BR><TEXTAREA id=PostComment.ascx_tbComment style="WIDTH: 400px; HEIGHT: 193px" name=PostComment.ascx:tbComment rows=10 cols=50></TEXTAREA></TD></TR>
  <TR>
    <TD colSpan=3><INPUT id=PostComment.ascx_chkRemember type=checkbox 
      name=PostComment.ascx:chkRemember><LABEL 
      for=PostComment.ascx_chkRemember>Remember Me?</LABEL></TD></TR>
  <TR>
    <TD><INPUT language=javascript id=PostComment.ascx_btnSubmit onclick="if (typeof(Page_ClientValidate) == 'function') Page_ClientValidate(); " type=submit value=Submit name=PostComment.ascx:btnSubmit></TD>
    <TD colSpan=2><SPAN id=PostComment.ascx_Message 
    style="COLOR: red"></SPAN></TD></TR></TBODY></TABLE></DIV></DIV>
<P id=footer>Powered by: <BR><A id=Footer1_Hyperlink2 
href="http://scottwater.com/blog" name=Hyperlink1><IMG 
src="遗传算法的发展现状与应用实例.files/100x30_Logo.gif" border=0></A> <A 
id=Footer1_Hyperlink3 href="http://asp.net/" name=Hyperlink1><IMG 
src="遗传算法的发展现状与应用实例.files/PoweredByAsp.Net.gif" border=0></A> <BR>Copyright © 
yuanqingfei </P>
<SCRIPT language=javascript>
<!--
	var Page_Validators =  new Array(document.all["PostComment.ascx_RequiredFieldValidator1"], document.all["PostComment.ascx_RequiredFieldValidator2"], document.all["PostComment.ascx_RequiredFieldValidator3"]);
		// -->
</SCRIPT>

<SCRIPT language=javascript>
<!--
var Page_ValidationActive = false;
if (typeof(clientInformation) != "undefined" && clientInformation.appName.indexOf("Explorer") != -1) {
    if ((typeof(Page_ValidationVer) != "undefined") && (Page_ValidationVer == "125"))
        ValidatorOnLoad();
}

function ValidatorOnSubmit() {
    if (Page_ValidationActive) {
        ValidatorCommonOnSubmit();
    }
}
// -->
</SCRIPT>
</FORM></BODY></HTML>