收稿日期:2008-01-12；修回日期:2008-03-26 基金项目：西南大学研究生科技创新基金资助项目(2006011) 作者简介：葛继科(1977-)，男，河南濮阳人，博士研究生，主要研究方向为人工智能、语义网格(g j k i d @s w u .e d u .c n )；邱玉辉(1938-)，男，教授，博导，主要研究方向为人工智能、语义网格；吴春明(1972-)，男，博士研究生，主要研究方向为网络技术；蒲国林(1971-)，男，博士研究生，主要研究方向为人工智能.
＊
葛继科1
，邱玉辉1
，吴春明1
，蒲国林
2
(1.西南大学计算机与信息科学学院，重庆400715;2.四川文理学院计算机科学系，四川达州635000)摘 要：介绍了遗传算法的基本工作原理和主要特点，讨论了遗传算法的理论、技术、存在问题及改进方法，概 述了遗传算法的常见应用领域，分析了近五年国内对遗传算法的研究现状。最后，进一步探讨了遗传算法的未来研究方向。
关键词：遗传算法；算子；优化；收敛性中图分类号:T P 301.6 文献标志码:A 文章编号:1001-3695(2008)10-2911-06
S u m m a r y o f g e n e t i c a l g o r i t h m s r e s e a r c h
G EJ i -k e 1,Q I U Y u -h u i 1,WUC h u n -m i n g 1,P UG u o -l i n
2
(1.S c h o o l o f C o m p u t e r ＆I n f o r m a t i o n S c i e n c e ,S o u t h w e s t U n i v e r s i t y ,C h o n g q i n g 400715,C h i n a ;2.D e p t .o f C o m p u t e r S c i e n c e ,S i c h u a n U n i -v e r s i t y o f A r t s ＆S c i e n c e ,D a z h o u S i c h u a n 635000,C h i n a )
A b s t r a c t :T h i s p a p e r i n t r o d u c e dt h e h i s t o r y ,b a s i c p r i n c i p l e a n d m a i n c h a r a c t e r s o f g e n e t i c a l g o r i t h m s ,d i s c u s s e d t h e t h e o r y ,
t e c h n o l o g y ,l i m i t a t i o na n d i m p r o v i n g m e a s u r e s a b o u t g e n e t i c a l g o r i t h m .T h e ns u m m a r i z e d t h e i m p l e m e n t a t i o nt e c h n i q u e s a n d a p p l i c a t i o n s o f g e n e t i c a l g o r i t h m s ,a n a l y z e dt h e r e s e a r c h s t a t eo f g e n e t i ca l g o r i t h m s i nC h i n a d u r i n g t h e p a s t f i v ey e a r s ,a n d p o i n t e d o u t t h e g e n e t i c a l g o r i t h m s 'r e s e a r c hd i r e c t i o n s i nt h e f u t u r e .K e y w o r d s :g e n e t i c a l g o r i t h m (G A );o p e r a t o r ;o p t i m i z a t i o n ;c o n v e r g e n c e 遗传算法是由美国M i c h i g a n 大学的H o l l a n d 教授于1969年提出，后经D e J o n g 、G o l d b e r g 等人归纳总结所形成的一类模拟进化算法
[1～3]
。它来源于达尔文的进化论、魏茨曼的物种选
择学说和孟德尔的体遗传学说。遗传算法是模拟自然界生物进化过程与机制求解极值问题的一类自组织、自适应人工智能技术
[4]
，其基本思想是模拟自然界遗传机制和生物进化论
虽然遗传算法在许多领域中都有成功的应用，但其自身也存在不足，如局部搜索能力差、存在未成熟收敛和随机游走等现象，导致算法的收敛性能差，需要很长时间才能到最优解等问题。这些不足阻碍了遗传算法的推广应用。如何改善遗传算法的搜索能力和提高算法的收敛速度，使其更好地应用于实际问题的解决中，是各国研究者一直探索的主要课题。
遗传算法的执行过程及特点
. 遗传算法的执行过程
遗传算法作为一种自适应全局优化搜索算法，使用二进制
遗传编码，即等位基因Γ={0,1}，个体空间H L = {0,1}L
，且繁殖分为交叉与变异两个独立的步骤进行。其基本执行过程如 下[5]:
a )初始化。确定种规模N 、交叉概率P c 、变异概率P m
和置终止进化准则；随机生成N 个个体作为初始种X (0)；置进化代数计数器t →0。
b )个体评价。计算或估价X (t )中各个体的适应度。
c )种进化。
(a )选择(母体)。从X (t )中运用选择算子选择出M/2对母体(M ≥N )。
(b )交叉。对所选择的M/2对母体，依概率P c 执行交叉形成M 个中间个体。
(c )变异。对M 个中间个体分别独立依概率P m 执行变异，形成M 个候选个体。
(d )选择(子代)。从上述所形成的M 个候选个体中依适应度选择出N 个个体组成新一代种X (t +1)。
d )终止检验。如已满足终止准则，则输出X (t +1)中具有最大适应度的个体作为最优解，终止计算；否则置t →t +1并转c )。
. 遗传算法的特点
遗传算法利用了生物进化和遗传的思想。它不同于枚举法、启发式算法、搜索算法等传统的优化方法，具有如下特点:
a )自组织、自适应和智能性。遗传算法削除了算法设计中的一个最大障碍，即需要事先描述问题的全部特点，并说明针对问题的不同特点算法应采取的措施。因此，它可用来解决复杂的非结构化问题，具有很强的鲁棒性。
b )直接处理的对象是参数编码集，而不是问题参数本身。
第25卷第10期2008年10月
计算机应用研究A p p l i c a t i o n R e s e a r c h o f C o m p u t e r s
V o l .25N o .10
O c t .2008
c )搜索过程中使用的是基于目标函数值的评价信息，搜索过程既不受优化函数连续性的约束，也没有优化函数必须可导的要求。
d )易于并行化，可降低由于使用超强计算机硬件所带来的昂贵费用。
e )基本思想简单，运行方式和实现步骤规范，便于具体使用。
遗传算法的理论研究
. 编码表示
在许多问题求解中，编码是遗传算法中首要解决的问题，对算法的性能有很重要的影响。H o l l a n d 提出的二进制编码是遗传算法中最常用的一种编码方法，它采用最小字符编码原则，编/解码操作简单易行，利于交叉、变异操作的实现，也可以采用模式定理对算法进行理论分析
[1]
。但二进制编码用于多
维、高精度数值问题优化时，不能很好地克服连续函数离散化时的映射误差；不能直接反映问题的固
有结构，精度不高，并且个体长度大、占用内存多。针对二进制编码存在的不足，人们提出了多种改进方法，比较典型的有以下几种:
a )格雷码编码。为了克服二进制编码在连续函数离散化时存在的不足，人们提出了用格雷码进行编码的方法，它是二进制编码的变形[6]。假设有一个二进制编码为X=x m x m-1…x 2x 1，其对应的格雷码为Y =y m y m-1…y 2y 1，则
y m =x m
y i =x i +1⊕x i
i =m-1,m-2,…,1
格雷码不仅具有二进制编码的一些优点，而且能够提高遗传算法的局部搜索能力。
b )实数编码。该方法适合于遗传算法中表示范围较大的数，使遗传算法更接近问题空间，避免了编码和解码的过程。它便于较大空间的遗传搜索，提高了遗传算法的精度要求[6]；便于设计专门问题的遗传算子；便于算法与经典优化方法的混合作用，改善了遗传算法的计算复杂性，提高了运算效率。
c )十进制编码。该方法利用十进制编码控制参数，缓解了“组合爆炸”和遗传算法的早熟收敛问题[7]。
d )非数值编码。染体编码串中的基因值取一个仅有代码含义而无数值含义的符号集，这些符号可以是数字也可以是字符
[8]
。非数值编码的优点是在遗传算法中可以利用所求问
题的专门知识及相关算法。对于非数值编码，问题的解和染体的编码要注意染体的可行性、染体的合法性和映射的惟一性。
. 适应度函数
在遗传算法中，适应度是描述个体性能的主要指标，根据适应度的大小对个体进行优胜劣汰。对于求解有约束的优化问题时，一般采用罚函数方法将目标函数和约束条件建立成一个无约束的优化目标函数；然后再将目标函数作适当处理，建立适合遗传算法的适应度函数。将目标函数转换成适应度函数一般应遵循两个原则：适应度必须非负；优化过程中目标函数的变化方向应与体进化过程中适应度函数变化方向一致
[9]
。在使用遗传算法求解具体问题时，适应度函数的选择
对算法的收敛性以及收敛速度的影响较大，针对不同的问题需根据经验或算法来确定相应的参数。
何新贵等人在对遗传算法的研究过程中，考虑函数在搜索点的函数值及其变化率，并将该信息加入适应度函数，使得按概率选择的染体不但具有较小的函数值，而且具有较大的函数变化率值[10]。实验结果表明，这类方法的收敛速度明显高于标准的遗传算法。陶卿等人提出基于约束区域神经网络的动态遗传算法[11]，将遗传算法的全局搜索和约束区域神经网络模型的局部搜索结合起来；利用动态遗传算法确定神经网络模型的初始点，同时使用神经网络确定动态遗传算法的适应度函数。. 遗传算子
在遗传算法中通过一系列算子来决定后代，算子对当前体中选定的成员进行重组和变异。
1)选择算子 选择操作通过适应度选择优质个体而抛弃劣质个体，体现了“适者生存”的原理。P o t t s 等人概括了23种选择方法[12]。常见的选择操作主要有以下几种:
a )赌选择。选择某假设的概率是通过这个假设的适应度与当前体中其他成员的适应度的比值而得到。此方法是基于概率选择的，存在统计误差，因此可以结合最优保存策略以保证当前适应度最优的个体能够进化到下一代而不被遗传操作的随机性破坏，保证算法的收敛性。
b )排序选择。对个体适应值取正值或负值以及个体适应度之间的数值差异程度无特殊要求，对体中的所有个体按其适应度大小进行排序，根据排序来分配各个体被选中的概率。
c )最优个体保存。父代体中的最优个体直接进入子代体中。该方法可保证在遗传过程中所得到的个体不会被交叉和变异操作所破坏，它是遗传算法收敛性的一个重要保证条件；它也容易使得局部最优个体不易被淘汰，从而使算法的全局搜索能力变强。
d )随机联赛选择。每次选取N 个个体中适应度最高的个体遗传到下一代体中。具体操作如下：从体中随机选取N 个个体进行适应度大小比较，将其中适应度最高的个体遗传到下一代体中；将上述过程重复执行M (为体大小)次，则可得到下一代体。
2)交叉算子 交叉是指对两个相互交叉的染体按某种方式相互交换其部分基因，从而形成两个新的个体。它是产生新个体的主要方法，决定了遗传算法的全局搜索能力，在遗传算法中起关键作用。P o t t s 等人概括了17种交叉方法[12]。几种常用的适用于二进制编码或实数编码方式的交叉算子如下:
a )单点交叉。在个体编码串中随机设置一个交叉点后在该点相互交换两个配对个体的部分基因。
b )两点交叉。在相互配对的两个个体编码串中随机设置两个交叉点，并交换两个交叉点之间的部分基因。
c )均匀交叉。两个相互配对个体的每一位基因都以相同的概率进行交换，从而形成两个新个体。
d )算术交叉。由两个个体的线性组合而产生出新的个体。
3)变异算子 变异是指将个体染体编码串中的某些基因座上的基因值用该基因座的其他等位基因来替换，从而形成一个新的个体。它是产生新个体的辅助方法，决定了遗传算法的局部搜索能力[12]。变异算子与交叉算子相互配合，可以共同完成对搜索空间的全局搜索和局部搜索，从而使得遗传算法以良好的搜索性能完成最优化问题的寻优过程。在遗传算法
·2912·计算机应用研究 第25卷
中使用变异算子主要有以下两个目的：改善遗传算法的局部搜索能力；维持体的多样性，防止出现早熟现象。下面是几种常用的变异操作:
a)基本位变异。对个体编码串以变异概率P随机指定某一位或某几位基因进行变异操作。
b)均匀变异(一致变异)。分别用符合某一范围内均匀分布的随机数，以某一较小的概率来替换个体编码串中各个基因座上的原有基因值。均匀变异操作特别适合应用于遗传算法的初期运行阶段，它使得搜索点可以在整个搜索空间内自由地移动，从而可以增加体的多样性，使算法能够处理更多的模式。
c)二元变异。需要两条染体参与，通过二元变异操作后生成两条新个体中的各个基因分别取原染体对应基因值的同或/异或。它改变了传统的变异方式，有效地克服了早熟收敛，提高了遗传算法的优化速度[13]。
d)高斯变异。在进行变异时用一个均值为μ、方差为σ2的正态分布的一个随机数来替换原有基因值。其操作过程与均匀变异类似。
. 参数选择
遗传算法的参数选择一般包括体规模、收敛判据、杂交概率和变异概率等。参数选择关系到遗传算法的精度、可靠性和计算时间等诸多因素，并且影响到结果的质量和系统性能。因此，在遗传算法中参数选择的研究非常重要。
在标准的遗传算法中经常采用经验对参数进行估计，这将带来很大的盲目性从而影响算法的全局最优性和收敛性，人们意识到这些参数应该随着遗传进化而自适应变化。基于这一观点,D a v i s提出了自适应算子概率方法[14]，即用自适应机制把算子概率与算子产生的个体表示适应性相结合，高适应性值被分配高算子概率。Wh i t l e y等人提出了自适应突变策略与一对父串间的H a m m i n g距离成反比的观点[15]，结果显示能有效地保持基因的多样性。张良杰等人通过引入i位改进子空间概念，采用模糊推理技术确定选取突变概率的一般性原则[16]。文献[17]中用模糊规则对选择概率和变异概率进行控制，在线改变其值。相应的算例表明，这种方法有较好的性能。
. 收敛性分析
遗传算法的收敛性通常是指遗传算法所生成的迭代种(或其分布)收敛到某一稳定状态(或分布)，或其适应值函数的最大或平均值随迭代趋于优化问题的最优值。依不同的研究方法及所应用的数学工具，收敛性分析可分为V o s e-L i e p i n s 模型、M a r k o v链模型和公理化模型等。
1)V o s e-L i e p i n s模型
该模型是V o s e和L i e p i n s提出来的，它用两个矩阵算子分别刻画比例选择与组合算子(即杂交算子与变异算子的复合)，通过这两个算子不动点的存在性与稳定性来刻画遗传算法的渐近行为[18]。
V o s e-L i e p i n s模型只适用于简单遗传算法，可应用于比例选择、单点杂交和单点变异等，没有推广到更具实用性的其他遗传算法执行策略中，如锦标赛选择、多点杂交等。另外, V o s e-L i e p i n s模型不易处理变异、杂交概率随时间变化的情形，其框架亦很难推广到描述一般非二进制或连续变量情形的遗传算法。
V o s e-L i e p i n s模型虽然在种规模无限的假设下可精确刻画遗传算法，但在有限规模情形下却只能描述遗传算法的平均形态。为了克服这个缺陷,N i x和V o s e结合V o s e-L i e p i n s模型与M a r k o v链描述，发展了遗传算法的一个精确M a r k o v链模型[19]。
2)M a r k o v链模型
遗传算法的马氏链模型主要有三种：种马氏模型、V o s e 模型[19]和C e r f扰动马氏链模型[20]。
种马氏链模型将遗传算法的种迭代序列视为一个有限状态马氏链加以研究，主要是运用种马氏链转移概率矩阵的某些一般性质分析遗传算法的极限行为。
在V o s e模型中，种的状态由一个概率向量表示，概率向量的维数为所有可能个体的数目。当种规模趋于无穷大时，相对频率的极限就代表了每一个个体在种中出现的概率。在无限种规模假设下，可以导出表示种的概率向量的不动点及其稳定性，从而导致对遗传算法极限行为的刻画。
R.C e r f利用A z e n c o t t等人关于模拟退火的一系列工作，将遗传算法看成一种特殊形式的广义模拟退火模型，利用动力系统的随机扰动理论对遗传算法的极限行为及收敛速度进行了研究[20]。尽管在C e r f模型中所研究的马氏链序列仍然是种序列，但研究方法与种马氏链模型有差异，所以称之为C e r f 扰动马氏链模型。
用M a r k o v链模型描述遗传算法虽然有直接、精确的优点，但由于有限状态M a r k o v链理论本身的限制，与V o s e-L i e p i n s模型类似，该模型只能用于描述通常的二进制或特殊的非二进制遗传算法。另外，这类方法所得收敛性一般是指相应的M a r-k o v链趋于某一平稳分布。这与优化中通常所指的收敛性定义不同，它并不保证遗传算法一定能收敛到问题的全局最优解。再者，相应M a r k o v链的状态数(转移矩阵的规模)通常很大，这使得具体确定、分析转移矩阵的性态十分困难，因而对于较大
规模的遗传算法,M a r k o v链分析只能基于遍历性考察而得出相应遗传算法收敛性的某些“粗糙”结论。
3)公理化模型
遗传算法的公理化方法基于对模拟进化计算操作的公理化描述，应用各个相关操作的本质特征数来对算法的收敛性直接进行概率估计[21]。这一方法不仅适用于包括非齐次、自适应等在内的各种遗传算法分析，而且分析方法本身直观、清晰，所导出的结论也对遗传算法的各种参数选择提供参考依据。这一模型具有重要的理论意义与实用价值。
文献[5]还通过详细估计常见选择算子与演化算子的选择压、选择强度、保持率、迁入率、迁出率等参数，导出了一系列具有重要应用价值的遗传算法收敛性结果。公理化模型也可用于其他模拟演化算法的收敛性分析。
. 欺骗问题
欺骗问题是遗传算法研究中的一个热点。根据模式定理可知，低阶、短距的优模式在遗传子代中将以指数级增长，最终，不同的最优模式相互组合，从而得到最优解。但是，对于欺骗问题，复制算子受欺骗条件的“迷惑”，使最优低阶模式在组合后形成非最优高阶模式，从而使遗传算法偏离最优解。由于欺骗问题的存在，许多问题被归结为遗传算法难题，使遗传算法的应用受到一定的局限。目前遗传算
法的欺骗问题研究主要集中在三个方面:a)设计欺骗函数，如G o l d b e r g曾设计一个离散遗传算法的最小欺骗问题。b)修改遗传算法以解决欺骗
·
2913
·
第10期葛继科，等：遗传算法研究综述
函数的影响，如黄炎等人提出一种基于可调变异算子求解遗传算法中欺骗问题的方法，即在遗传搜索过程中通过改变变异算子的方向和概率求解遗传算法的欺骗问题[22]。该方法能够在消除遗传算法中欺骗性条件的同时保持体的多样性，使遗传算法可以顺利地收敛到全局最优解。c)理解欺骗函数对遗传算法的影响，何军等人讨论了一类遗传算法求解完全欺骗性问题的平均计算时间[23]。
. 并行遗传算法
并行算法的基本思想是将一个复杂的任务分解为多个较简单的子任务，然后将各子任务分别分配给多个处理器并行执行求解。例如,Z e i g l e r等人把高性能并行遗传算法应用到大型并行计算机[24]，这种
分而治之的思想可以由不同的方法和途径实现，导致了各种不同类型的并行遗传算法。并行遗传算法可以分为四大类，即全局并行遗传算法、粗粒度并行遗传算法、细粒度并行遗传算法和混合并行遗传算法。
侯广坤等人讨论了并行遗传算法的迁移现象及体规模估算模型，分析了迁移的过程，揭示了迁移的实质，并提出了在理想条件下的迁移计算模型[25]，基于迁移计算模型导出了粗粒度并行遗传算法进化质量估量模型。王洪燕等人对并行遗传算法的研究现状进行了详细的介绍[26]。
遗传算法的应用
遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，广泛应用于多种学科领域。
. 函数优化
函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用算例。不同研究者构造出了各种各样的复杂形式的测试函数，有连续函数也有离散函数，有凸函数也有凹函数，有低维函数也有高维函数，有确定函数也有随机函数，有单峰值函数也有多峰值函数等。用这些几何特性各具特的函数来评价遗传算法的性能，更能反映算法的本质效果。对于一些非线性、多模型、多目标的函数优化问题，用其他优化方法较难求解，遗传算法却可以方便地得到较好的结果[27]。
. 组合优化
随着问题规模的增大，组合优化问题的搜索空间也急剧扩大，有时在目前的计算机上用枚举法很难或甚至不可能求出其精确的最优解。对这类复杂问题，应把主要精力放在寻求其满意解上，而遗传算法是寻求这种满意解的最佳工具之一。实践证明，遗传算法已经在求解旅行商问题、背包、装箱、布局优化、图形划分等各种具有N P难度的问题上得到成功的应用[6,28～30]。
. 生产调度
在很多情况下，用常规方法建立的数学模型难以精确求解生产调度问题，即使经过一些简化之后可以进行求解，有时也会因简化太多而使得求解结果与实际目标相差甚远。一般情况下，在现实生产中主要是靠经验来进行调度。研究发现，遗传算法已成为解决复杂调度问题的有效工具，在单件生产车间调度、流水线生产车间调度、生产规划、任务分配等方面，遗传算法都得到了有效的应用[8,31,32]。
. 自动控制
在自动控制领域中有很多与优化相关的问题需要求解，遗传算法已在其中得到了初步的应用，并显示出良好的效果。例如用遗传算法进行航空控制系统的优化[33]、使用遗传算法设计空间交汇控制器、基于遗传算法的模糊控制器的优化设计[34]、基于遗传算法的参数辨识、基于遗传算法的模糊控制规则的
学习，利用遗传算法进行人工神经网络的结构优化设计和权值学习等，都显示出了遗传算法在这些领域中应用的可能性。
. 机器人学
机器人是一类复杂的、难以精确建模的人工系统。由于遗传算法的起源来自于人工自适应系统的研究，机器人学理所当然地成为遗传算法的一个重要应用领域。遗传算法已经在移动机器人路径规划[35]、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行为协调等方面进行了研究和应用[36]。
. 图像处理
图像处理是计算机视觉中的一个重要研究领域。在图像处理过程中，如扫描、特征提取、图像分割等不可避免地会存在一些误差，从而影响图像的效果。如何使这些误差最小化是计算机视觉达到实用化的重要要求。遗传算法可用于图像处理中的优化计算，目前已在模式识别(包括汉字识别[37])、图像恢复、图像边缘特征提取等方面得到了应用[38,39]。
. 人工生命
人工生命是用计算机、机械等人工媒体模拟或构造出的具有自然生物系统特有行为的人造系统。自组
织能力和自学习能力是人工生命的两大主要特征。人工生命与遗传算法有着密切的联系，基于遗传算法的进化模型是研究人工生命现象的重要基础理论。虽然人工生命的研究尚处于初期阶段，但遗传算法已在其进化模型、学习模型、行为模型、自组织模型等方面显示出了初步的应用能力，并且必将会得到更为深入的应用和发展。人工生命与遗传算法相辅相成，遗传算法为人工生命的研究提供一个有效的工具，人工生命的研究也必将促进遗传算法的进一步发展[40]。
. 遗传编程
遗传编程(g e n e t i c p r o g r a m m i n g,G P)采用树型结构表示计算机程序，运用遗传算法的思想，通过自动生成计算机程序来解决问题。虽然遗传编程的理论尚未成熟，应用也有一些限制，但它已成功地应用于人工智能、机器学习等领域[41]。K o z a 等人描述了基本的遗传编程方法并且给出了很多可以被G P 成功学习的程序[42～44]。
. 机器学习
学习能力是高级自适应系统所具备的能力之一，基于遗传算法的机器学习，特别是分类器系统，在很多领域中都得到了应用。遗传算法被用于学习模糊控制规则，可以更好地改进模糊系统的性能；基于遗传算法的机器学习不但可以用来调整人工神经网络的连接权，也可用于人工神经网络结构的优化设计[45,46]。
. 数据挖掘
数据挖掘能够从大规模数据库中提取隐含的、未知的、有潜在应用价值的知识和规则。许多数据挖掘问题可以看做是搜索问题。其中，数据库可看做是搜索空间，挖掘算法可看做
·
2914
·计算机应用研究 第25卷
是搜索策略。应用遗传算法在数据库中进行搜索，对随机产生的一组规则进行进化，直到数据库能被该组规则覆盖，从而挖掘出隐含在数据库中的规则[47～49]。S u n i l 已成功地开发了一个基于遗传算法的数据挖掘工具[50]，利用该工具对两个飞机失事的真实数据库进行了数据挖掘实验，结果表明遗传算法是进行数据挖掘的有效方法之一。
近五年国内遗传算法研究现状
在前人研究的基础上，本文以已发表论文为依据，重点考查了2002—2006年国内学者及工程技术人员在遗传算法方面的研究情况，如表1所示。该表数据的统计源是中国知网(C N K I )的“电子技术及信息科学类”中收录的中文核心期刊。
表1 2002—2006年国内遗传算法研究现状
年度综述函数优化组合优化生产调度自动控制机器人学图像处理人工生命遗传编程机器
学习数据挖掘2002699104231991833166200391027827882723201020044127933921828101715200531207732258322226212006
1
94
57
28
12
7
24
2
1
16
12
表1分别从综述、函数优化、组合优化、生产调度、自动控制、机器人学、图像处理、人工生命、遗传编程、机器学习、数据挖掘11个方面对近五年国内发表在中文核心期刊上、与遗传算法有关的论文进行了分类。图1是根据表1生成的对比分析图
。
通过对表1及图1的分析可以得出如下结论:
a )针对遗传算法函数优化和组合优化方面进行研究的文章每年几乎都是最多的。这说明对遗传算法进行的研究更多的还是停留在理论层面，而生产调度及自动控制等实际应用领域的研究成果较少，有待进一步深入研究。
b )总体来看，近五年国内对遗传算法的研究在逐年增长，但从2005年起有所回落，到2006年出现减少的现象。从这一现象来看，国内关于遗传算法的研究兴趣可能已达到饱和，理论研究已经比较成熟。另外，就目前研究现状来看，很难在原有的基础上得出更多新的成果。
c )遗传算法在数据挖掘和机器学习领域进行的研究在研究成果中所占的比重逐年明显增长。这说明遗传算法在数据挖掘和机器学习领域的研究成为新的热点。虽然有效成果占总的研究成果的比例还很少，但这是一个可以进行深入研究的方向。
遗传算法的未来研究方向
遗传算法在各种问题的求解与应用中展现了其特点和魅力，同时也暴露出它在理论和应用上的诸多不足和缺陷。未来几年内遗传算法的研究重点可能集中在以下几方面:
a )算法的数学基础，包括算法的收敛性、收敛速度估计、早熟机理的探索与预防、交叉算子的几何意义与统计解释、参数设置对算法的影响等方面。算法的收敛速度估计是当前特别值得研究和探讨的问题，它能从理论上对遗传算法的任何修正形式提供评判标准，从而指明改进算法性能的正确方向。
b )遗传算法与优化技术的融合。对遗传算法的大范围体搜索性能与快速收敛的局部优化方法进行混合，从而产生有效的全局优化方法。这种策略可从根本上提高遗传算法计算性能，对此可以进行大量的理论分析和实验。
c )算法的改进与深化。根据具体应用领域对遗传算法进行改进与完善，仅泛泛地对一般问题进行研究是远远不够的。当前针对具体应用问题深化研究遗传算法是特别值得提倡的工作。
d )算法的选择。基于实验研究的结论并不具有普遍意义上的指导作用，因此从数学的角度进行遗传算法的理论研究将对算法的合理选择提供理论指导。
e )算法的并行化研究。遗传算法的体适应度评价、随机搜索等特征使其具有明显的并行性。因此，设计各种并行执行策略、建立相应的并行化遗传算法的数学基础，是一项具有重要意义的工作。
结束语
遗传算法作为一种非确定性的拟自然算法，为复杂系统的优化提供了一种新的方法，实践证明其效果
显著。尽管遗传算法在很多领域具有广泛的应用价值，但它仍存在一些问题，各国学者一直都在探索对遗传算法的改进及发展，以使遗传算法有更广泛的应用领域。参考文献:
[1]H O L L A N D J H .A d a p t a t i o ni nn a t u r a l a n da r t i f i c i a l s y s t e m s [M].A n nA r b o r :U n i v e r s i t y o f M i c h i g a nP r e s s ,1975.
[2]
D e J O N GKA .T h e a n a l y s i s o f t h e b e h a v i o r o f a c l a s s o f g e n e t i c a d a p -t i v e s y s t e m s [D ].A n nA r b o r :U n i v e r s i t y o f M i c h i g a n ,1975.[3]
G O L D B E R GDE .G e n e t i c a l g o r i t h m s i n s e a r c h ,o p t i m i z a t i o n a n d m a -c h i n e l e a r n i n g [M ].B o s t o n :A d d i s o n -We s l e y L o n g m a n P r e s s ,1989.[4]张文修，梁怡.遗传算法的数学基础[M ].西安：西安交通大学出
版社,2000.
[5]徐宗本，张讲社，郑亚林.计算智能中的仿生学：理论与算法[M ].北京：科学出版社,2003.[6]周明，孙树栋.遗传算法原理及应用[M].北京：国防工业出版
社,1999.
[7]唐飞，滕弘飞.一种改进的遗传算法及其在布局优化中的应用
[J ].软件学报,1999,10(10):1096-1102.
[8]玄光男，程润传.遗传算法与工程设计[M].北京：科学出版社,
2000.
[9]邢文训，谢金星.现代优化计算方法[M].北京：清华大学出版
社,1999.[10]何新贵，梁久祯.利用目标函数梯度的遗传算法[J ].软件学报,
2001,12(7):981-985.
[11]陶卿，曹进德，孙德敏，等.基于约束区域神经网络的动态遗传
算法[J ].软件学报,2001,12(3):462-467.
[12]P O T T SCJ ,T E R R I D .T h ed e v e l o p m e n t a n de v a l u a t i o no f a ni m -p r o v e dg e n e t i ca l g o r i t h m b a s e do nm i g r a t i o na n da r t i f i c i a l s e l e c t i o n
[J ].I E E ET r a n so nS y s t e m s ,Ma n ,a n dC y b e r n e t i c s ,1994,24(1):73-86.
[13]杨启文，蒋静坪，张国宏.遗传算法优化速度的改进[J ].软件
学报,2001,12(2):270-275.
·
2915·第10期葛继科，等：遗传算法研究综述
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议