genetic_algorithm.htm

人工智能；进化算法；遗传算法（GA）；多目标最小生成树

 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1031"
  DrawAspect="Content" ObjectID="_1254726195">
 </o:OLEObject>
</xml><![endif]--></SPAN><SPAN 
style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%; FONT-FAMILY: 宋体; mso-hansi-font-family: 'Times New Roman'; mso-ascii-font-family: 'Times New Roman'">个区间段，每个染色体所占的区间段的长度既是它的适应度。这样，随机产生一个</SPAN><SPAN 
lang=EN-US style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%">1</SPAN><SPAN 
style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%; FONT-FAMILY: 宋体; mso-hansi-font-family: 'Times New Roman'; mso-ascii-font-family: 'Times New Roman'">～</SPAN><SPAN 
lang=EN-US><SUB><!--[if gte vml 1]><v:shape id=_x0000_i1032 
style="WIDTH: 23.25pt; HEIGHT: 15.75pt" o:ole="" type = "#_x0000_t75" coordsize 
= "21600,21600"> <v:imagedata o:title="" src = 
"yichuan.files/image013.wmz"></v:imagedata></v:shape><![endif]--><![if !vml]><img width=31 height=21
src="yichuan.files/image014.gif" v:shapes="_x0000_i1032"><![endif]></SUB><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1032"
  DrawAspect="Content" ObjectID="_1254726196">
 </o:OLEObject>
</xml><![endif]--></SPAN><SPAN 
style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%; FONT-FAMILY: 宋体; mso-hansi-font-family: 'Times New Roman'; mso-ascii-font-family: 'Times New Roman'">的整数，抽取该点所属区间段相对应的染色体，就可以保证任意一个染色体</SPAN><I 
style="mso-bidi-font-style: normal"><SPAN lang=EN-US 
style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%">x<SUB>i</SUB></SPAN></I><SPAN 
lang=EN-US style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%"> </SPAN><SPAN 
style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%; FONT-FAMILY: 宋体; mso-hansi-font-family: 'Times New Roman'; mso-ascii-font-family: 'Times New Roman'">在抽取操作中被抽取到的概率为</SPAN><SPAN 
lang=EN-US 
style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%"><SUB><!--[if gte vml 1]><v:shape 
id=_x0000_i1033 style="WIDTH: 33pt; HEIGHT: 33.75pt" o:ole="" type = 
"#_x0000_t75" coordsize = "21600,21600"> <v:imagedata o:title="" src = 
"yichuan.files/image015.wmz"></v:imagedata></v:shape><![endif]--><![if !vml]><img width=44 height=45
src="yichuan.files/image016.gif" v:shapes="_x0000_i1033"><![endif]></SUB><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1033"
  DrawAspect="Content" ObjectID="_1254726197">
 </o:OLEObject>
</xml><![endif]--></SPAN><SPAN 
style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%; FONT-FAMILY: 宋体; mso-hansi-font-family: 'Times New Roman'; mso-ascii-font-family: 'Times New Roman'">。</SPAN><SPAN 
lang=EN-US style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%"><o:p></o:p></SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 150%"><B 
style="mso-bidi-font-weight: normal"><SPAN lang=EN-US 
style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%; FONT-FAMILY: 宋体"><o:p>&nbsp;</o:p></SPAN></B></P>
<P class=MsoNormal style="LINE-HEIGHT: 150%"><B 
style="mso-bidi-font-weight: normal"><SPAN 
style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%; FONT-FAMILY: 宋体">▲ 终止条件<SPAN 
lang=EN-US><o:p></o:p></SPAN></SPAN></B></P>
<P class=MsoNormal 
style="MARGIN-LEFT: 17.95pt; TEXT-INDENT: 27pt; LINE-HEIGHT: 150%; mso-char-indent-count: 2.25; mso-para-margin-left: 1.71gd"><SPAN 
style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%; FONT-FAMILY: 宋体">遗传算法的终止条件用于防止遗传算法无止境的迭代下去，一般限制条件可以设为达到指定的迭代次数后终止，或当解的收敛速度低于一定值时自动终止。当遗传算法达到终止条件时，遗传算法结束，并按照要求返回中途最优的一个染色体（或所有满足条件的非劣最优解）<SPAN 
lang=EN-US><o:p></o:p></SPAN></SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 150%"><SPAN lang=EN-US 
style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%; FONT-FAMILY: 宋体"><o:p>&nbsp;</o:p></SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 150%"><B 
style="mso-bidi-font-weight: normal"><SPAN lang=EN-US 
style="FONT-SIZE: 14pt; LINE-HEIGHT: 150%; FONT-FAMILY: 宋体">2</SPAN></B><B 
style="mso-bidi-font-weight: normal"><SPAN 
style="FONT-SIZE: 14pt; LINE-HEIGHT: 150%; FONT-FAMILY: 宋体">．<SPAN 
lang=EN-US>3</SPAN>重要参数设置<SPAN lang=EN-US><o:p></o:p></SPAN></SPAN></B></P>
<P class=MsoNormal style="LINE-HEIGHT: 150%"><B 
style="mso-bidi-font-weight: normal"><SPAN lang=EN-US 
style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%; FONT-FAMILY: 宋体"><o:p>&nbsp;</o:p></SPAN></B></P>
<P class=MsoNormal 
style="TEXT-INDENT: 26.9pt; LINE-HEIGHT: 150%; mso-char-indent-count: 2.24"><SPAN 
style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%; FONT-FAMILY: 宋体">在应用遗传算法解决问题的时候，往往需要根据实际情况的不同，对不同问题使用不同的遗传参数。在大规模的问题上，一次遗传算法的不同时期也可以设置不同的遗传参数。对遗传算法效率影响较大的参数如下：<SPAN 
lang=EN-US><o:p></o:p></SPAN></SPAN></P>
<P class=MsoNormal 
style="TEXT-INDENT: 26.9pt; LINE-HEIGHT: 150%; mso-char-indent-count: 2.24"><SPAN 
lang=EN-US 
style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%; FONT-FAMILY: 宋体"><o:p>&nbsp;</o:p></SPAN></P>
<P class=MsoNormal 
style="MARGIN-LEFT: 80.85pt; TEXT-INDENT: -62.9pt; LINE-HEIGHT: 150%; tab-stops: 18.0pt; mso-char-indent-count: -5.22; mso-para-margin-left: 1.71gd"><B 
style="mso-bidi-font-weight: normal"><SPAN 
style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%; FONT-FAMILY: 宋体">群体大小</SPAN></B><SPAN 
style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%; FONT-FAMILY: 宋体">：一代群体中染色体的数量，群体大小越大所能容纳的染色体品种也越多，越有利于搜索全局最有解，但是会下降收敛的速度，所需的时间也更多。<SPAN 
lang=EN-US><o:p></o:p></SPAN></SPAN></P>
<P class=MsoNormal 
style="MARGIN-LEFT: 80.6pt; TEXT-INDENT: -62.65pt; LINE-HEIGHT: 150%; tab-stops: 18.0pt; mso-char-indent-count: -5.22; mso-para-margin-left: 1.71gd"><SPAN 
lang=EN-US 
style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%; FONT-FAMILY: 宋体"><o:p>&nbsp;</o:p></SPAN></P>
<P class=MsoNormal 
style="MARGIN-LEFT: 80.85pt; TEXT-INDENT: -62.9pt; LINE-HEIGHT: 150%; tab-stops: 18.0pt; mso-char-indent-count: -5.22; mso-para-margin-left: 1.71gd"><B 
style="mso-bidi-font-weight: normal"><SPAN 
style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%; FONT-FAMILY: 宋体">迭代次数</SPAN></B><SPAN 
style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%; FONT-FAMILY: 宋体">：最多更新群体的次数，迭代次数的增加可以使得解收敛更精确但是所需的时间也越多，如果时间允许，采用多次初始化群体的操作要比设置很大的迭代次数来得更高效些。<SPAN 
lang=EN-US><o:p></o:p></SPAN></SPAN></P>
<P class=MsoNormal 
style="MARGIN-LEFT: 80.6pt; TEXT-INDENT: -62.65pt; LINE-HEIGHT: 150%; tab-stops: 18.0pt; mso-char-indent-count: -5.22; mso-para-margin-left: 1.71gd"><SPAN 
lang=EN-US 
style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%; FONT-FAMILY: 宋体"><o:p>&nbsp;</o:p></SPAN></P>
<P class=MsoNormal 
style="MARGIN-LEFT: 80.85pt; TEXT-INDENT: -62.9pt; LINE-HEIGHT: 150%; tab-stops: 18.0pt; mso-char-indent-count: -5.22; mso-para-margin-left: 1.71gd"><B 
style="mso-bidi-font-weight: normal"><SPAN 
style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%; FONT-FAMILY: 宋体">保持率</SPAN></B><SPAN 
style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%; FONT-FAMILY: 宋体">：保持算子所占的比例，通常不超过<SPAN 
lang=EN-US>70%<o:p></o:p></SPAN></SPAN></P>
<P class=MsoNormal 
style="MARGIN-LEFT: 80.6pt; TEXT-INDENT: -62.65pt; LINE-HEIGHT: 150%; tab-stops: 18.0pt; mso-char-indent-count: -5.22; mso-para-margin-left: 1.71gd"><SPAN 
lang=EN-US 
style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%; FONT-FAMILY: 宋体"><o:p>&nbsp;</o:p></SPAN></P>
<P class=MsoNormal 
style="MARGIN-LEFT: 80.85pt; TEXT-INDENT: -62.9pt; LINE-HEIGHT: 150%; tab-stops: 18.0pt; mso-char-indent-count: -5.22; mso-para-margin-left: 1.71gd"><B 
style="mso-bidi-font-weight: normal"><SPAN 
style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%; FONT-FAMILY: 宋体">交配率</SPAN></B><SPAN 
style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%; FONT-FAMILY: 宋体">：交配算子所占的比例，通常不超过<SPAN 
lang=EN-US>50%<o:p></o:p></SPAN></SPAN></P>
<P class=MsoNormal 
style="MARGIN-LEFT: 80.6pt; TEXT-INDENT: -62.65pt; LINE-HEIGHT: 150%; tab-stops: 18.0pt; mso-char-indent-count: -5.22; mso-para-margin-left: 1.71gd"><SPAN 
lang=EN-US 
style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%; FONT-FAMILY: 宋体"><o:p>&nbsp;</o:p></SPAN></P>
<P class=MsoNormal 
style="MARGIN-LEFT: 80.85pt; TEXT-INDENT: -62.9pt; LINE-HEIGHT: 150%; tab-stops: 18.0pt; mso-char-indent-count: -5.22; mso-para-margin-left: 1.71gd"><B 
style="mso-bidi-font-weight: normal"><SPAN 
style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%; FONT-FAMILY: 宋体">变异率</SPAN></B><SPAN 
style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%; FONT-FAMILY: 宋体">：变异算子所占的比例，通常不超过<SPAN 
lang=EN-US>1%<o:p></o:p></SPAN></SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 150%"><B 
style="mso-bidi-font-weight: normal"><SPAN lang=EN-US 
style="FONT-SIZE: 16pt; LINE-HEIGHT: 150%; FONT-FAMILY: 宋体"><o:p>&nbsp;</o:p></SPAN></B></P>
<P class=MsoNormal style="LINE-HEIGHT: 150%"><B 
style="mso-bidi-font-weight: normal"><SPAN lang=EN-US 
style="FONT-SIZE: 16pt; LINE-HEIGHT: 150%; FONT-FAMILY: 宋体"><o:p>&nbsp;</o:p></SPAN></B></P>
<P class=MsoNormal style="LINE-HEIGHT: 150%"><B 
style="mso-bidi-font-weight: normal"><SPAN lang=EN-US 
style="FONT-SIZE: 16pt; LINE-HEIGHT: 150%; FONT-FAMILY: 宋体"><o:p>&nbsp;</o:p></SPAN></B></P>
<P class=MsoNormal style="LINE-HEIGHT: 150%"><B 
style="mso-bidi-font-weight: normal"><SPAN lang=EN-US 
style="FONT-SIZE: 16pt; LINE-HEIGHT: 150%; FONT-FAMILY: 宋体"><o:p>&nbsp;</o:p></SPAN></B></P>
<P class=MsoNormal style="LINE-HEIGHT: 150%"><B 
style="mso-bidi-font-weight: normal"><SPAN lang=EN-US 
style="FONT-SIZE: 16pt; LINE-HEIGHT: 150%; FONT-FAMILY: 宋体"><o:p>&nbsp;</o:p></SPAN></B></P>
<P class=MsoNormal style="LINE-HEIGHT: 150%"><B 
style="mso-bidi-font-weight: normal"><SPAN lang=EN-US 
style="FONT-SIZE: 16pt; LINE-HEIGHT: 150%; FONT-FAMILY: 宋体"><o:p>&nbsp;</o:p></SPAN></B></P>
<P class=MsoNormal style="LINE-HEIGHT: 150%"><B 
style="mso-bidi-font-weight: normal"><SPAN lang=EN-US 
style="FONT-SIZE: 16pt; LINE-HEIGHT: 150%; FONT-FAMILY: 宋体"><o:p>&nbsp;</o:p></SPAN></B></P>
<P class=MsoNormal style="LINE-HEIGHT: 150%"><B 
style="mso-bidi-font-weight: normal"><SPAN lang=EN-US 
style="FONT-SIZE: 16pt; LINE-HEIGHT: 150%; FONT-FAMILY: 宋体"><o:p>&nbsp;</o:p></SPAN></B></P>
<P class=MsoNormal 
style="MARGIN-LEFT: 21.75pt; TEXT-INDENT: -21.75pt; LINE-HEIGHT: 150%; TEXT-ALIGN: center; tab-stops: list 21.75pt; mso-list: l25 level1 lfo4" 
align=center><![if !supportLists]><B style="mso-bidi-font-weight: normal"><SPAN 
lang=EN-US 
style="FONT-SIZE: 16pt; LINE-HEIGHT: 150%; FONT-FAMILY: 宋体; mso-bidi-font-family: 宋体"><SPAN 
style="mso-list: Ignore">三.<SPAN 
style="FONT: 7pt 'Times New Roman'">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
</SPAN></SPAN></SPAN></B><![endif]><B style="mso-bidi-font-weight: normal"><SPAN 
style="FONT-SIZE: 16pt; LINE-HEIGHT: 150%; FONT-FAMILY: 宋体">遗传算法在多目标最小生成树问题中的应用<SPAN 
lang=EN-US><o:p></o:p></SPAN></SPAN></B></P>
<P class=MsoNormal style="LINE-HEIGHT: 150%"><B 
style="mso-bidi-font-weight: normal"><SPAN lang=EN-US 
style="FONT-SIZE: 16pt; LINE-HEIGHT: 150%; FONT-FAMILY: 宋体"><o:p>&nbsp;</o:p></SPAN></B></P>
<P class=MsoNormal 
style="TEXT-INDENT: 24pt; LINE-HEIGHT: 150%; mso-char-indent-count: 2.0"><SPAN 
style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%; FONT-FAMILY: 宋体">生活中的很多问题，例如道路铺设，电网架设，网络构设等，其实都可以归结到最小生成树模型，经典的<SPAN 
lang=EN-US>Prim</SPAN>算法和<SPAN 
lang=EN-US>Kruskal</SPAN>算法都可以解决该问题，算法的时间复杂度都是线形的，但是现实生活中的问题往往没有那么简单，一条边上可能不只带一个权，例如一条公路的铺设道路长度还要考虑环境和人文因素，电网架设时除了考虑线路费用还要考虑架设难度，一个网络连接除了考虑网络延时还要考虑传输稳定性和安全性等，于是问题就转化为求解多目标的最小生成树问题的非劣最优解，这个问题是<SPAN 
lang=EN-US>NP</SPAN>难的，<SPAN lang=EN-US>Prim</SPAN>算法，<SPAN 
lang=EN-US>Kruskal</SPAN>算法等常规算法就显得无能为力，搜索算法的复杂度却又过高。<SPAN 
lang=EN-US><o:p></o:p></SPAN></SPAN></P>
<P class=MsoNormal 
style="TEXT-INDENT: 24pt; LINE-HEIGHT: 150%; mso-char-indent-count: 2.0"><SPAN 
lang=EN-US 
style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%; FONT-FAMILY: 宋体"><o:p>&nbsp;</o:p></SPAN></P>
<P class=MsoNormal 
style="TEXT-INDENT: 24pt; LINE-HEIGHT: 150%; mso-char-indent-count: 2.0"><SPAN 
lang=EN-US 
style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%; FONT-FAMILY: 宋体"><o:p>&nbsp;</o:p></SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 150%"><B 
style="mso-bidi-font-weight: normal"><SPAN lang=EN-US 
style="FONT-SIZE: 14pt; LINE-HEIGHT: 150%; FONT-FAMILY: 宋体">3</SPAN></B><B 
style="mso-bidi-font-weight: normal"><SPAN 
style="FONT-SIZE: 14pt; LINE-HEIGHT: 150%; FONT-FAMILY: 宋体">．<SPAN 
lang=EN-US>1</SPAN>多目标最小生成树问题</SPAN></B><SPAN lang=EN-US 
style="FONT-SIZE: 14pt; LINE-HEIGHT: 150%; FONT-FAMILY: 宋体"><o:p></o:p></SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 150%"><B 
style="mso-bidi-font-weight: normal"><SPAN lang=EN-US 
style="FONT-SIZE: 12pt; LINE-HEIGHT: 150%; FONT-FAMILY: 宋体"><o:p>&nbsp;</o:p></SPAN></B></P>
<P class=MsoNormal 
style="MARGIN-LEFT: 54pt; TEXT-INDENT: -54pt; LINE-HEIGHT: 150%; tab