一、遗传算法与模拟退火算法比较
分析模拟退火算法的基本原理可以看出,模拟退火算法是
通过温度的不断下降渐进产生出最优解的过程,
是一个列马尔科
夫链序列,在一定温度下不断重复
Metropolis
过程,目标函数值
满足
Boltzmann
概率分布。在温度下降足够慢的条件下,
Boltzmann
分布收敛于全局最小状态的均匀分布,从而保证模拟
退火算法以概率为
1
收敛到全局最优。另外,不难看出,模拟退
火算法还存在计算结构简单、
通用性好以及鲁棒性强等优点。
但
是,模拟退火算法存在如下缺陷:
1.
尽管温度参数下降缓慢时理论上可以保证算法以概率为
1
地收敛到最优值,但是需要的时间过长加之误差积累与时间长
度的限制,难以保证计算结果为最优;
2.
如果降温过程加快,很可能得不到全局最优解,因此,温
度的控制是一个需要解决的问题;
3.
在每一种温度下什么时候系统达到平衡状态,即需要多少
次
Metropolis
过程不易把握,
从而影响模拟退火算法的最终结果。
与模拟退火算法相比较,遗传算法具有如下典型特征:
这两种算法的相同点是都采用进化控制优化的过程。
主要不
同点是模拟退火是采用单个个体进行进化,
遗传算法是采用种群
进行进化。
模拟退火一般新解优于当前解才接受新解,
并且还需
要通过温度参数进行选择,
并通过变异操作产生新个体。
而遗传
算法新解是通过选择操作进行选择个体,
并通过交叉和变异产生
新个体。具体说来,遗传算法具有如下特点:
(
1
)
与自然界相似,
遗传算法对求解问题的本身一无所知,
对搜索空间没有任何要求(如函数可导、光滑性、连通性等),
只以决策编码变量作为运算对象并对算法所产生的染色体进行
评价,
可用于求解无数值概念或很难有数值概念的优化问题,
应
用范围广泛;
(
2
)
搜索过程不直接作用到变量上,
直接对参数集进行编
码操作,
操作对象可以是集合、
序列、
矩阵、
树、
图、
链和表等;
(
3
)搜索过程是一组解迭代到另一组解,采用同时处理群
体中多个个体的方法,因此,算法具有并行特性;