文档介绍：并行遗传算法及其应用
1、遗传算法(GA)概述
GA是一类基于自然选择和遗传学原理的有效搜索方法,它从一个种群开始,利用选择、交叉、变异等遗传算子对种群进行不断进化,最后得到全局最优解。生物遗传物质的主要载体是染色体,在GA中同样将问题的求解表示成“染色体Chromosome”,通常是二进制字符串表示,其本身不一定是解。首先,随机产生一定数据的初始染色体,这些随机产生的染色体组成一个种群(Population),种群中染色体的数目称为种群的大小或者种群规模。第二:用适值度函数来评价每一个染色体的优劣,即染色体对环境的适应程度,用来作为以后遗传操作的依据。第三:进行选择(Selection),选择过程的目的是为了从当前种群中选出优良的染色体,通过选择过程,产生一个新的种群。第四:对这个新的种群进行交叉操作,变异操作。交叉、变异操作的目的是挖掘种群中个体的多样性,避免有可能陷入局部解。经过上述运算产生的染色体称为后代。最后,对新的种群(即后代)重复进行选择、交叉和变异操作,经过给定次数的迭代处理以后,把最好的染色体作为优化问题的最优解。
GA通常包含5个基本要素:1、参数编码:GA是采用问题参数的编码集进行工作的,而不是采用问题参数本身,通常选择二进制编码。2、初始种群设定:GA随机产生一个由N个染色体组成的初始种群(Population),也可根据一定的限制条件来产生。种群规模是指种群中所含染色体的数目。3、适值度函数的设定:适值度函数是用来区分种群中个体好坏的标准,是进行选择的唯一依据。目前主要通过目标函数映射成适值度函数。4、遗传操作设计:遗传算子是模拟生物基因遗传的操作,遗传操作的任务是对种群的个体按照它们对环境的适应的程度施加一定的算子,从而实现优胜劣汰的进化过程。遗传基本算子包括:选择算子,交叉算子,变异算子和其他高级遗传算子。5、控制参数设定:在GA的应用中,要首先给定一组控制参数:种群规模,杂交率,变异率,进化代数等。
GA的优点是擅长全局搜索,一般来说,对于中小规模的应用问题,能够在许可的范围内获得满意解,对于大规模或超大规模的多变量求解任务则性能较差。另外,GA本身不要求对优化问题的性质做一些深入的数学分析,从而对那些不太熟悉数学理论和算法的使用者来说,无疑是方便的。
2、遗传算法的运行机理:
对GA运行机理的解释有两类: 一是传统的模式理论;二是1990 年以后发展起来的有限状态马尔可夫链模型。
(1)模式理论:由Holland创建,主要包括模式定理,隐并行性原理和积木块假说三部分。模式是可行域中某些特定位取固定值的所有编码的集合。模式理论认为遗传算法实质上是模式的运算,编码的字母表越短,算法处理一代种群时隐含处理的模式就越多。当算法采用二进制编码时,效率最高,处理规模为N的一代种群时,可同时处理O(N3)个模式。遗传算法这种以计算少量编码适应度而处理大量模式的性质称为隐并行性。模式理论还指出,目标函数通常满足积木块假说,即阶数高,长度长,平均适应度高的模式可以由阶数低,长度短,平均适应度高的模式(积木块)在遗传算子的作用下,接合而生成。而不满足积木块假说的优化问题被称为骗问题(deceptive problem)。模式理论为遗传算法构造了一条通过在种群中不断积累、拼接积木块以达到全局最优解的寻优之路。但近十多年的研究