遗传算法综述

摘要:本文简述了遗传算法的基本原理和特点,以及在各个领域的应用情况。

关键词:遗传算法;GA;进化;最优化

中图分类号:TP18 文献标识码:A文章编号:1007-9599 (2010) 04-0000-01

Summary on Genetic Algorithm

Gao Ying

(Shandong Industry Vocational College,Zibo256414,China)

Abstract:This article has summarized the genetic algorithm basic principle and the characteristic, as well as in each domain application situation.

Keyword:Genetic algorithm;Evolution;Optimization

一、引言

在人工智能领域中,有不少问题需要在复杂而庞大的搜索空间中寻找最优解或准最优解。在计算此类问题时,若不能利用问题的固有知识来缩小搜索空间则会产生搜索的组合爆炸。因此,研究能在搜索过程中自动获取和积累有关搜索空间的知识并自适应地控制搜索过程从而得到最优解的通用搜索算法一直是令人瞩目的课题[1]。遗传算法简称就是这类特别有效的算法之一。

二、遗传算法基本原理

遗传算法是建立在自然选择和群众遗传学机理基础上的,具有广泛适应性的搜索方法。遗传算法搜索结合了达尔文适者生存和随机信息交换的思想,适者生存消除了解中不适应因素,随机信息交换利用了原有解中已知的知识,从而有力地加快了搜索过程。

遗传算法的基本思想[2]:遗传算法是从代表问题可能潜在解集的一个种群开始的,一个种群由经过基因编码的一定数目的个体组成,初始种群产生之后,按照适者生存和优胜劣汰的原理,逐步演化产生出越来越好的近似解。在每一代,根据问题域中个体的适应度大小挑选个体,并借助自然遗传学的遗传算子进行交叉和变异,产生出代表新的解集的种群。这个过程将导致种群向自然进化一样的后代种群比前代更加适应环境,末代种群中的最优个体经过解码,可以作为问题近似最优解。

三、遗传算法的主要特点及改进

随着问题种类的不同以及问题规模的扩大,要寻求一种能以有限的代价来解决搜索和优化的通用方法,遗传算法正是为我们提供的一个有效的途径,它不同于传统的搜索和优化方法。主要区别在于:

(1)自组织、自适应和自学习性。

(2)遗传算法的本质并行性。

(3)遗传算法不要求导或其他辅助知识,而只需要影响搜索方向的目标函数和相应的适应度函数。

(4)遗传算法强调概率转换规则,而不是确定的转换规则。

(5)遗传算法可以更加直接地应用。

(6)遗传算法对给定问题,可以产生许多的潜在解,最终选择可以由使用者确定。

其中对全局信息有效利用和隐含并行性是遗传算法的两大特点,同时遗传算法对问题本身的限制较少,因而具有很强的通用优化能力。但遗传算法容易过早收敛,这样就会使其他个体中的有效基因不能得到有效复制,最终丢失;而且在进化后期染色体之间的差别极小,整个种群进化停滞不前,搜索效率较低,这样就会导致搜索到的结果不是全局最优解。

自从1975年J.H.Holland系统地提出遗传算法的完整结构和理论以来,众多学者一直致力于推动遗传算法的发展,对编码方式、控制参数的确定、选择方式和交叉机理等进行了深入的探究,其基本途径概括起来有以下几个方面[3]:

(1)改变遗传算法的组成部分或使用技术;

(2)采用混合遗传算法;

(3)采用动态自适应技术,在进化过程中调整算法控制参数和编码粒度;

(4)采用非标准的遗传操作算子;

(5)采用并行遗传算法等。

四、遗传算法的应用领域

遗传算法经过几十年的发展,逐渐被人们接受和运用,遗传算法的应用研究比理论研究更为丰富,下面是遗传算法的一些主要应用领域[4]:

(1)优化问题:优化问题包括函数优化和组合优化两种。函数优化是遗传算法的经典领域,也是对遗传算法进行性能评价的常用算例。对于组合优化,随着问题规模的扩大,搜索空间急剧扩大,这类复杂问题,人们已经意识到把精力放在寻找其满意解上。实践证明,遗传算法对于组合优化中的NP完全问题非常有效。

(2)生产调度问题:生产调度问题在许多情况下所建立起来的数学模型难以精确求解,即使经过一些简化之后可以进行求解,也会因简化太多而使得求解结果与实际相差甚远。遗传算法已成为解决复杂调度问题的有效工具,在单件生产车间调度、流水线生产车间、生产规划、任务分配等方面遗传算法都得到了有效的应用。

(3)自动控制:在自动控制领域中许多与优化相关的问题需要求解,遗传算法的应用日益增加,并显示了良好的效果。例如用遗传算法进行航空控制系统的优化、基于遗传算法的参数辨识、利用遗传算法进行人工神经网络的结构优化设计和权值学习,都显示了遗传算法在这些领域中应用的可能性。

(4)机器人智能控制:机器人是一类复杂的难以精确建模的人工系统,而遗传算法的起源就来自于对人工自适应系统的研究。例如遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行动协调等方面得到研究和应用。

(5)图像处理和模式识别:图像处理和模式识别是计算机视觉中的一个重要研究领域。在图像处理过程中,如扫描、特征提取、图像分割等不可避免地产生一些误差,这些误差会影响到图像处理和识别的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求。遗传算法在图像处理中的优化计算方面是完全胜任的。目前已在图像恢复、图像边缘特征提取、几何形状识别等方面得到了应用。

五、总结

遗传算法作为一种非确定性的模拟自然演化的学习过程的求解问题方法,在很多领域具有广泛的应用价值,但其在很多方面有待于进一步研究、探讨和完善。可以预期,随着计算机技术的进步和生物学研究的深入,遗传算法在操作技术和方法上将更通用、更有效。

参考文献:

[1]王煦法.遗传算法及其应用.小型微型计算机系统,1995,2

[2]席裕庚.遗传算法综述.控制理论与应用,1996,12,13(6)

赵振勇,王力,王保华,杨本娟.遗传算法改进策略的研究.计算机应用,2006,12(26)