全国服务热线:18888889999
在线报名
欧陆注册CURRICULUM
欧陆资讯 NEWS CENTER
联系我们 CONTACT US
手机:
18888889999
电话:
0898-66889888
邮箱:
admin@youweb.com
地址:
海南省海口市玉沙路58号
欧陆资讯
你的位置: 首页 > 欧陆资讯
现代优化算法 (一):模拟退火算法 及应用举例
2024-09-09 12:51:19 点击量:


组合优化算法系列:

现代优化算法 (一):模拟退火算法 及应用举例

现代优化算法 (二): 遗传算法 及应用举例

现代优化算法(三):禁忌搜索算法

现代优化算法(四):改进的遗传算法

现代优化算法(五): 蚁群算法


现代优化算法是 80 年代初兴起的启发式算法。这些算法包括禁忌搜索(tabu search),模拟退火(simulated annealing),遗传算法(genetic algorithms),人工神经网 络(neural networks)。它们主要用于解决大量的实际应用问题。目前,这些算法在理论 和实际应用方面得到了较大的发展。无论这些算法是怎样产生的,它们有一个共同的目 标-求 NP-hard 组合优化问题的全局优解。虽然有这些目标,但 NP-hard 理论限制它 们只能以启发式的算法去求解实际问题。

启发式算法包含的算法很多,例如解决复杂优化问题的蚁群算法(Ant Colony Algorithms)。有些启发式算法是根据实际问题而产生的,如解空间分解、解空间的限 制等;另一类算法是集成算法,这些算法是诸多启发式算法的合成。

现代优化算法解决组合优化问题,如 TSP(Traveling Salesman Problem)问题,QAP (Quadratic Assignment Problem)问题,JSP(Job-shop Scheduling Problem)问题等效 果很好。?

目录

?模拟退火算法简介?

1.2 ?应用举例


模拟退火算法得益于材料的统计力学的研究成果。统计力学表明材料中粒子的不 同结构对应于粒子的不同能量水平。在高温条件下,粒子的能量较高,可以自由运动和 重新排列。在低温条件下,粒子能量较低。如果从高温开始,非常缓慢地降温(这个过 程被称为退火),粒子就可以在每个温度下达到热平衡。当系统完全被冷却时,终形 成处于低能状态的晶体。

在模拟退火算法中应注意以下问题:

(1)理论上,降温过程要足够缓慢,要使得在每一温度下达到热平衡。但在计算 机实现中,如果降温速度过缓,所得到的解的性能会较为令人满意,但是算法会太慢, 相对于简单的搜索算法不具有明显优势。如果降温速度过快,很可能终得不到全局 优解。因此使用时要综合考虑解的性能和算法速度,在两者之间采取一种折衷。

(2)要确定在每一温度下状态转换的结束准则。实际操作可以考虑当连续m 次的 转换过程没有使状态发生变化时结束该温度下的状态转换。终温度的确定可以提前定 为一个较小的值 \small T_{e}?,或连续几个温度下转换过程没有使状态发生变化算法就结束。

(3)选择初始温度和确定某个可行解的邻域的方法也要恰当。?

例 ?已知敌方 100 个目标的经度、纬度如表 1 所示。

?

我们编写如下的 matlab 程序如下:?

 

计算结果为 44 小时左右。其中的一个巡航路径如图 1 所示。?

?


组合优化算法系列:

现代优化算法 (一):模拟退火算法 及应用举例

现代优化算法 (二): 遗传算法 及应用举例

现代优化算法(三):禁忌搜索算法

现代优化算法(四):改进的遗传算法

现代优化算法(五): 蚁群算法