《配送企业车辆路径问题的建模及优化方法》:
3.3.3 基于禁忌规则的模拟退火算法
模拟退火(SA)算法是受到热力学退火过程的启发而创立的搜索算法。物理上的退火过程是指固体加热到一定高的温度,此时该物体内的分子成无序运动,相差很大,随着温度的逐步降低,分子的动能减少导致体内分子的排列趋于稳定状态。该算法是由Metropolis等在1953年提出,随之应用于组合优化。基于蒙特卡洛迭代算法求解,由某一高温度开始,利用具有概率突变特性的Metropolis抽样策略,在解空间随机搜索,随着温度不断下降,重复搜索过程,最终得到问题的全局最优解。SA与通常的局部搜索算法相比,其最大的特点是以一定的概率选择邻域中目标值相对较大(对于最小值问题)的状态,这一点使SA成为一种理论上的全局最优算法。SA在初始温度足够高、温度下降足够慢的条件下,能以概率1收敛到全局最优点。
模拟退火算法有着明显的优点,运算的稳定性与质量比较高,逻辑思路比较清晰,初始值的鲁棒性较强,结果不过多依赖初始值。其缺点则是解的质量与求解时间长之间的矛盾。温度下降多次,从而需要计算多次抽样结果,为了得到一个好的近似最优解,需要进行反复迭代运算,导致运算时间较长。
为了弥补这个缺陷,可以引入禁忌搜索算法(TS)中的禁忌表,通过设置存储体来记忆最近访问过的解集,这样退火过程可以避免重新访问已经搜索过的解,在一定程度上使搜索过程避开局部极值点,并且搜索过程的速度可以得到一定程度的提高。
……
展开