现代优化算法...ppt

遗传算法及其模拟计算
一遗传算法
其主要特点是群体搜索策略和群体中个体之间的信息交换,搜索不依赖于梯度信息。
它的应用范围非常广泛,尤其适合于处理传统搜索方法难于解决的复杂和非线性问题,可广泛用于组合优化,机器学习,自适应控制,规划设计和人工生命等领域,从而确立了它在21世纪的智能计算技术中的关键地位。
1 遗传算法的基本步骤
遗传算法流程图如下:
集团中个体适应度的检测评估
选择
交叉
变异
图1 遗传算法的基本流程
编码和初始集团生成
一、编码
遗传算法主要是通过遗传操作对群体中具有某种结构形式的个体施加结重组处理,从而不断地搜索出群体中个体间结构相似性,由此可见,遗传算法不能直接处理问题空间参数,必须把它们转换成遗传空间的由基因按一定结构组成的染色体或个体。这一转换操作就叫做编码。
二、初始群体的生成
遗传操作是对于多个体同时进行的。
初始群体的设定可采取如下策略:
(1) 根据问题固有的知识,设法确定最优解所占空间在整个问题空间中的分布范围,然后,在此分布范围内设定初始群体。
(2) 先随机生成一定数目的个体,然后从中挑出最好的个体加到初始群体当中去。这种过程不断迭代,直到初始群体中个数达到了预先确定的规模。
三、适应度函数
适应度函数表明个体或解的优劣性。不同的问题,适应性函数的定义方式也不同。这一操作是借用了达尔文的自然选择原则,即个体适应度越高,其被选择的个体越多。
四、遗传操作
遗传操作是模拟生物基因遗传的操作。在遗传算法中,通过编码组成初始群体后,遗传操作的任务就是对群体的个体按照他们对环境适应的程度(适应度评估)施加一定的操作,从而实现优胜劣汰的进化过程,从优化搜索的角度而言,遗传操作可以使问题的解,一代又一代地优化,并逼近最优解。遗传算法的基本操作包括以下三个基本算子:选择,交叉,变异。
(一)选择:选择的目的是为了从当前群体中选出优良的个体,使它们有机会作为父代为下一代繁殖子孙。进行选择的原则是适应性强的个体为下一代贡献一个或多个后代的概率大。
适应度比例方法(fitness proportional model)
适应度比例方法是目前遗传算法中最基本也是最常用的选择方法,他也叫赌轮或蒙特卡罗(monte carlo)选择。
设群体的大小为n,其中个体i的适应度值为,则i被选择的概率为

显然,概率反映个体i的适应度在总和中所占的比例,个体的适应度越大,其被选择的概率就越高,反之亦然,计算出群体中各个个体的选择概率后,就可以决定那些个体可以被选出。
(二)交叉:交换操作是遗传算法中最主要的遗传操作。在遗传算法中使用交叉算子来产生新的个体。
基本交叉算子如下:
单点交叉(one-point crossover),它是指在个体编码串中只随机设置一个交叉点,然后在该点相互交换两个配对个体的部分染色体。
双点交叉(two-point crossover)是指在个体编码串中随机设置了二交叉点,然后再进行部分基因交换。