前言

爬山算法

以最简单的连续一元函数找最大值为例，大致阐述一下爬山法

  1. 在解空间中随机生成一个初始解;
  2. 根据初始解的位置，在下一步有两种走法：向左邻域走一步或者向右邻域走一步 (走的步长越小越好，但会加大计算量);
  3. 比较不同走法下目标函数的大小，并决定下一步往哪个方向走。
  4. 不断重复 3，直到找到一个极大值点(或定义域边缘处)，结束搜索。

爬山算法的局限

很明显，如果初始解在途中局部最大值附近，那么最后有可能直接在局部最大值处结束。

而从“上帝视角”来看，局部最大值本非全局最大值！

综上所述，爬山法属于一种 贪心算法，很容易陷入局部最优。

蒙特卡洛

待更

原理

模拟退火算法是一种基于蒙特卡洛思想设计的近似求解最优化问题的方法。

它是一种适合解大规模组合优化问题的通用有效近似算法，是局部搜索算法的扩展。

它通过在搜索过程引入随机因素。使得计算过程中会以一定的概率来接受一个比当前解要差的解，因此有可能**会跳出这个局部的最优解，达到全局的最优解。

所以从理论上来说它是一个能求得全局最优化结果的算法，它是一种启发式算法，源于对固体退火的研究。

退火

算法细则

代码模板

Matlab

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
clc;clear all;close all;

%退火参数配置
a=0.95; %温度衰减速度
T0 = 100; %初始温度
Tf = 0.1; %结束温度
T = T0; %当前温度值
mar_length=1000; %马氏链长度,每次迭代内循环中生成新解的次数

sol_new=round(rand(1,num));%随机生成初始解
E_current=inf; %当前解对应的目标函数
E_best=inf; %最优解
%E_new是新解的目标函数值

%迭代开始,若当前温度大于结束温度，就继续迭代
while T > Tf 

    for i=1:mar_length
        % 产生随机新解sol_new并剪枝
		% 略
        %计算新解函数值，注：模拟退火算法只能求最小值
        E_new = func(sol_new);
        %若新值比前一次小
        if E_new<E_current
            %更换成当前的
            E_current=E_new;
            sol_current=sol_new;
            %若新值比最优解小
            if E_new<E_best
                %更换最优解
                E_best=E_new;
                sol_best=sol_new;
            end
        %否则，根据概率选择是否容忍
        else
            if (rand<exp(-(E_new-E_current)./T))
                 E_current=E_new;
                 sol_current=sol_new;
            else
                 sol_new=sol_current;
            end
        end
    end
    % 减小当前温度
    T=T*a;
end
%显示结果
disp('最优路径如下：');

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
# 设置退火类
class MySA:
    def __init__(self,alpha,T_max,T_min,length,sol0):
        self.a = alpha
        self.T0 = T_max
        self.Tf = T_min
        self.mar_len = length
        self.p = 0
        self.best_sol = []
        self.best_ans = float('+inf')
        self.new_sol = copy.deepcopy(sol0)
        self.new_ans = func(self.new_sol) #func为目标函数
        self.current_sol = copy.deepcopy(sol0)
        self.current_ans = float('+inf')
    
    # 更新退火概率
    def update_p(self):
        self.p = math.exp(-(self.new_ans-self.current_ans)/self.T0)

    # 产生新解
    def create_newsol(self):
     '''
     	如何产生的根据实际问题进行调整，此处略
     '''
        # 计算新解的函数值
        self.new_ans = func(self.new_sol)
    
    # 开始退火
    def derstart(self):
        for i in range(self.mar_len):
            self.create_newsol()
            if self.new_ans < self.current_ans:
                self.current_sol = copy.deepcopy(self.new_sol)
                self.current_ans = self.new_ans
                if self.new_ans < self.best_ans:
                    self.best_sol = copy.deepcopy(self.new_sol)
                    self.best_ans = self.new_ans
            # 概率容忍
            else:
                t = random.random()
                self.update_p()
                if t < self.p:
                    self.current_sol = copy.deepcopy(self.new_sol)
                    self.current_ans = self.new_ans
                else:
                    self.new_sol = copy.deepcopy(self.current_sol)
    
    def get_sol(self):
        while self.T0 > self.Tf:
            # 退火
            self.derstart()
            self.T0 = self.T0*self.a
        return self.best_sol,self.best_ans

参考资料

1.模拟退火算法|bilibili专栏

2.数学建模清风第二次直播：模拟退火算法|bilibili