搜索
传统优化算法可以解决一些比较简单的问题，但对于一些非线性的复杂问题，往往优化时间很长，并且经常不能得到最优解，甚至无法知道所得解同最优解的近似程度，而一些现代优化算法就能很好地解决这些问题。20世纪60年代学者开始对遗传进化感兴趣，进而形成了遗传算法。遗传算法(GA)是由美国Michigan大学的Holland教授于1975年首先提出的。它源于达尔文的进化论、孟德尔的群体遗传学说和魏茨曼的物种选择学说;其基本思想是模拟自然界遗传机制和生物进化论而形成的一种过程搜索最优解的算法。从公开发表的论文看,我国首先开始研究应用遗传算法的有赵改善和华中理工大学的师汉民等人。遗传算法最早应用于一维地震波形反演中,其特点是处理的对象是参数的编码集而不是问题参数本身,搜索过程既不受优化函数联系性的约束,也不要求优化函数可导,具有较好的全局搜索能力;算法的基本思想简单,运行方式和实现步骤规范,具有全局并行搜索、简单通用、鲁棒性强等优点,但其局部搜索能力差,容易出现早熟现象。自1985年起,国际遗传算法会议每两年召开一次,在欧洲,从1990年开始每隔一年也举办一次类似的会议。1993年,国际上第一本以遗传算法和进化计算为核心内容的学术期刊《EvolutionaryComputation》(进化计算)在MIT创刊;1994年,在美国奥兰多召开的IEEEWorldCongressonComputationntelligence(IEEE全球计算智能大会)上,进化计算与模糊逻辑、神经网络一起统称为计算智能;1997年,《IEEETransac-tionsonEvolutionaryComputation》创刊。这些刊物及时全面地报道了近年来遗传算法的最新研究成果。目前,与遗传算法有关的学术会议包括ICGA、PPSN、ICEC、ANN＆GA、EP、FOGA、COGANN、EC、GP、SEAL等。遗传算法是模拟生物在自然环境中优胜劣汰、适者生存的遗传和进化过程而形成的一种具有自适应能力的、全局性的概率搜索算法。它是从代表问题可能潜在解集的一个种群开始,首先将表现型映射到基因型即编码,从而将解空间映射到编码空间,每个编码对应问题的一个解,称为染色体或个体。初始种群产生之后,按照适者生存和优胜劣汰的原理,逐代演化产生出越来越好的近似解。在每一代,根据问题域中个体的适应度大小选择个体,并借助自然遗传学的遗传算子进行组合交叉和变异,产生出代表新的解集的种群。这个过程使种群像自然进化一样,后代种群比前代更加适应于环境,末代种群中的最优个体经过解码可以作为问题近似最优解。利用遗传算法求解问题的流程如下。a)建立数学模型。b)编码,即用设计好的算法将表现型映射到个体基因型。c)解码,遗传算子只对编码后的染色体起作用,由个体表现型计算目标函数值后就可以判断染色体的优劣。d)确定适应度转换规则,染色体所对应的解空间的值可能相差很大,需要一定的转换使其适合定量评估个体的优劣。e)设计遗传算子,即设计交叉、变异和选择算子等。遗传算子与待优化问题、染色体的编码方案有很大的关系。f)确定运行参数,运行参数包括交叉概率、变异概率和种群数目等。遗传算法本身的参数还缺乏定量的标准,目前采用的多是经验数值,并且遗传参数的选取与编码和遗传算子的设计有很大关系。目前在遗传算法的应用中,最突出的问题是局部搜索能力差和容易出现早熟现象。近年来,众多学者围绕这两个核心问题发表了大量有价值的学术论文,从各方面对遗传算法进行了改进。在遗传算子方面,Pan等人提出自适应变异算子,使得变异能够根据解的质量自适应地调整搜索区域,较明显地提高了搜索能力。Louis等人根据个体之间的海明距离进行非均匀的交叉和变异,在保持群体多样性的同时还防止了早熟。夏虎等人提出了一种考虑环境作用的协同免疫遗传算法,在该算法中,设计了克隆环境演化算子和自适应探索算子,并构造了三个子种群协同进化来发挥克隆环境演化算子的作用,从而提高了算法的全局搜索能力。蔡良伟等人提出一种改进的交叉操作,根据种群的多样性和个体的相关性选择不同的交叉策略以减少无效的交叉操作,从而提高了交叉操作的效率并改善了算法的收敛性能。江雷等人提出的基于并行遗传算法求解TSP,对遗传算法的杂交算子进行改进,探讨了使用弹性策略来维持群体的多样性,使得算法跨过局部收敛的障碍,向全局最优解方向进化。Whitley等人提出了自适应和有指导的变异,这种方法对改进遗传算法的性能起了一定的作用。一些学者提出了基于多种群的遗传算法,将一个大的种群分成多个小的种群,每个小种群独立地进行进化,进化一定代数后进行种群间的通信。由于这种方式可以采用并行计算的模式,取得了较好的效果。贺新等人介绍了一种基于新的变异算子多种群的新遗传算法,该算法引入一种基于主群、附属子群的结构,可避免传统遗传算法难以克服的早熟收敛问题。叶在福等人引入多种群,对不同种群赋予不同的控制参数,实现不同的搜索目的,通过移民算子联系各种群,通过人工选择算子保存各种群每个进化代中的最优个体,对遗传算法的早熟现象有了很大的改进。朱灿等人提出了一种考虑性别特征的遗传算法,该方法模拟生物系统多物种同时进化,指出最优种子的获得不但需要一个好的个体(父体),而且需要一个好的进化方向(母体),通过增加母体的方法加速最优物种的进化,从而提高了算法的效率。遗传算法的控制参数主要有种群数目Npop、交叉概率Pc和变异概率Pm,不同的参数组合对遗传算法的运行性能影响很大。DeJong首先系统地研究了不同的参数组合对遗传算法的性能影响,他对五个函数进行测试后,提出了一组参数选择范围:Npop=50,Pc=0.6,Pm=0.001,这一组参数值后来被作为标准参数广泛使用。丁承明等人提出了利用正交试验法去优化选取控制参数,这种方法利用正交试验的均衡分散性,使得通过较少的试验次数就能搜索大部分参数组合空间,而且还可以确定哪个参数对结果影响最显著,然后有针对性地进行精确的搜索,从而使得参数问题得到圆满解决。李康顺等人提出的改进遗传算法能够根据个体适应度大小和群体的分散程度自动调整遗传控制参数,从而能够在保持群体多样性的同时加快收敛速度,克服了传统遗传算法的收敛性差、易早熟等问题。还有许多学者从其他方面对遗传算法进行了改进,如设计交互式遗传算法、引入量子理论等。这些改进都在某种程度上提高了遗传算法的性能,然而这些改进都具有一定的局限性。因此,提高遗传算法的收敛速度、克服早熟现象将是一个永恒的目标。由于遗传算法具有全局并行搜索、简单通用、鲁棒性强等优点,使得遗传算法广泛地应用于各个领域。在计算机科学与人工智能方面遗传算法在计算机科学与人工智能领域中的应用包括数据库查询优化、数据挖掘与知识获取、人工神经网络结构与参数优化、模式识别、专家系统等。另外,遗传算法在软件测试用例自动生成方面也作出了很大的贡献。组合优化(combinatorialoptimization)研究那些含有有限个可行解的、日常生活中大量存在的问题。这其中一个重要并且普遍的应用领域就是考虑如何有效利用稀缺资源来提高生产力。GA在组合优化问题中的应用包括路径覆盖、装箱、背包、确定最小生成树、机器调度排序与平衡、车辆路径、网络设计与路径、旅行推销员分配等。将遗传算法用于知识获取,构成以遗传算法为核心的机器学习系统。比较经典的是Holland设计的用于序列决策学习的桶链算法(bucketbrigade)反馈机制(该系统被称为分类器系统),以及机器人规则、概念学习、模式识别等。早期的经济学研究采用遗传算法来求解数学公式,取得了不错的效果,但离机器学习还差得很远。例如,Lettau在1997年建立的一个简单的主体模型中就使用了这种方法;Bauer对遗传算法在经济与投资中的应用进行了全面分析。近年来,商业、金融领域已经成为遗传算法应用热点,目前已经有许多基于遗传算法的软件包应用于金融系统和股票投资分析。遗传算法的研究归纳起来可分为理论与技术研究和应用研究两个方面。可以说,遗传算法的应用已经渗透到了各个领域。但目前遗传算法的算法分析和理论分析还没有跟上,还有很多富有挑战性的课题亟待完善与解决,主要有:a)算法规模小。虽然遗传算法模拟了生物的进化过程,但目前遗传算法的运行规模还远小于生物的进化规模。随着计算机系统性能的不断提高,人们将有可能实现模拟更接近于自然的进化系统,从而充分利用遗传算法的并行性解决更复杂、更有价值的问题。b)遗传算法的编码问题。编码是遗传算法求解问题的前提,最基本的是二进制编码。其他的编码方法有格雷码、实数编码、符号编码、多参数编码和DNA编码等。不同的应用应该采用不同的编码方式,因此基于不同的应用,遗传算法的编码还有待改进与完善。c)遗传算法控制参数的选择问题。遗传算法中控制参数的不同选取会对遗传算法的性能产生较大的影响,将影响到整个算法的收敛性。这些参数包括交叉概率(pc)、变异概率(pm)和种群数目(Npop)等。d)早熟收敛和局部搜索能力差问题。早熟收敛和局部搜索能力差是遗传算法最突出的两个问题。有很多学者针对这两个问题发表了大量的学术文章,但从根本上解决这两个问题还有待研究发现。e)遗传算子的无方向性问题。基本遗传算子包括选择算子、交叉算子和变异算子。设计性能优良的遗传算子一直是遗传算法的重要问题,如果能从遗传算子的方向性着手改进遗传算法,有可能会得到意想不到的结果。对上述问题的深入研究必将大大促进遗传算法理论和应用的发展,遗传算法也必将在智能计算领域中展现出更加光明的前景。