1. 關于全局最優化求解
全局最優化是一個非常復雜的問題，目前還沒有一個通用的辦法可以對任意復雜函數求解全局最優值。上一篇文章講解了一個求解局部極小值的方法——梯度下降法。這種方法對于求解精度不高的情況是實用的，可以用局部極小值近似替代全局最小值點。但是當要求精確求解全局最小值時，梯度下降法就不適用了，需要采用其他的辦法求解。常見的求解全局最優的辦法有拉格朗日法、線性規劃法、以及一些人工智能算法比如遺傳算法、粒子群算法、模擬退火算法等(可以參見我之前的博客)。而今天要講的是一個操作簡單但是不易陷入局部極小值的方法：隨機游走算法。
2. 隨機游走算法操作步驟
設\(f(x)\)是一個含有\(n\)個變量的多元函數,\(x=(x_1,x_2,…,x_n)\)為\(n\)維向量。
給定初始迭代點\(x\)，初次行走步長\(\lambda\)，控制精度\(\epsilon\)(\(\epsilon\)是一個非常小的正數，用于控制結束算法)。
給定迭代控制次數\(N\)，\(k\)為當前迭代次數，置\(k=1\)。
當 \(k
計算函數值，如果 \(f(x_1)
如果連續\(N\)次都找不到更優的值，則認為，最優解就在以當前最優解為中心，當前步長為半徑的\(N\)維球內(如果是三維，則剛好是空間中的球體)。此時，如果\(\lambda < \epsilon\)，則結束算法；否則，令\(\lambda = \frac{\lambda}{2}\)，回到第1步，開始新一輪游走。
3. 隨機游走的代碼實現(使用Python)
這里使用的測試函數為\(f(r) = \frac{sin(r)}{r} + 1,r=\sqrt{(x-50)^2+(y-50)^2}+e,0 \leq x,y \leq 100\),求\(f(r)\)的最大值。該函數是一個多峰函數，在\((50,50)\)處取得全局最大值\(1.1512\)，第二最大值在其全局最大值附近，采用一般的優化方法很容易陷入局部極大值點。這里是求解函數的最大值問題，可以將其轉化為求目標函數的相反數的最小值問題。具體代碼如下：
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time : 2017/7/20 10:08
# @Author : Lyrichu
# @Email : 919987476@qq.com
# @File : random_walk.py
'''
@Description:使用隨機游走算法求解函數極值
這里求解:f = sin(r)/r + 1,r = sqrt((x-50)^2+(y-50)^2)+e,0<=x,y<=100 的最大值
求解f的最大值，可以轉化為求-f的最小值問題
'''
from __future__ import print_function
import math
import random
N = 100 # 迭代次數
step = 0.5 # 初始步長
epsilon = 0.00001
variables = 2 # 變量數目
x = [49,49] # 初始點坐標
walk_num = 1 # 初始化隨機游走次數
print("迭代次數:",N)
print("初始步長:",step)
print("epsilon:",epsilon)
print("變量數目:",variables)
print("初始點坐標:",x)
# 定義目標函數
def function(x):
r = math.sqrt((x[0]-50)**2 + (x[1]-50)**2) + math.e
f = math.sin(r)/r + 1
return -f
# 開始隨機游走
while(step > epsilon):
k = 1 # 初始化計數器
while(k < N):
u = [random.uniform(-1,1) for i in range(variables)] # 隨機向量
# u1 為標準化之后的隨機向量
u1 = [u[i]/math.sqrt(sum([u[i]**2 for i in range(variables)])) for i in range(variables)]
x1 = [x[i] + step*u1[i] for i in range(variables)]
if(function(x1) < function(x)): # 如果找到了更優點
k = 1
x = x1
else:
k += 1
step = step/2
print("第%d次隨機游走完成。" % walk_num)
walk_num += 1
print("隨機游走次數:",walk_num-1)
print("最終最優點:",x)
print("最終最優值:",function(x))
輸出結果如下:
迭代次數: 100
初始步長: 0.5
epsilon: 1e-05
變量數目: 2
初始點坐標: [49, 49]
第1次隨機游走完成。
第2次隨機游走完成。
第3次隨機游走完成。
......
第16次隨機游走完成。
隨機游走次數: 16
最終最優點: [49.99999305065255, 50.00000102537616]
最終最優值: -1.15111524497
基本的隨機游走算法對于初始點比較敏感，可以看出，當初始點位于最優點附件時，可以很好地達到全局最優點；如果將初始點設置得離最優點較遠，比如設置初始點為\((10,10)\)時，其他參數不變，得到結果為：
隨機游走次數: 16
最終最優點: [10.042835581532445, 11.648866165553416]
最終最優值: -1.01720848747
可以發現，隨機游走陷入了局部最優點。當然，如果增大迭代次數\(N\)以及初始步長\(\lambda\)，可以在一定程度上增加尋優能力，比如設置\(N=3000,\lambda=10.0\)，得到結果如下：
迭代次數: 3000
初始步長: 10.0
epsilon: 1e-05
變量數目: 2
初始點坐標: [10, 10]
第1次隨機游走完成。
第2次隨機游走完成。
第3次隨機游走完成。
......
第20次隨機游走完成。
隨機游走次數: 20
最終最優點: [49.99999900055026, 50.0000023931389]
最終最優值: -1.15111697755
可以看出，當增大迭代次數以及初始步長之后，函數最終達到了全局最優點。但是迭代次數增加的代價則是運行時間的增加。總得來說，基本的隨機游走算法可以很好地達到全局最優點，但是有時會依賴于初始點的選擇。
4. 改進的隨機游走算法
改進的隨機游走算法的不同之處是在于第3步，原來是產生一個隨機向量\(u\)，現在則是產生\(n\)個隨機向量\(u_1,u_2,\cdots,u_n\)，\(n\)是給定的一個正整數。將\(n\)個\(u_i(i=1,2,\cdots,n)\)標準化得到\(u_1^{‘},u_2^{‘},\cdots,u_n^{‘}\)，利用公式\(x_i = x + \lambda u_i^{‘}\),令\(min\{x_1,x_2,\cdots,x_n\}\)替換原來的\(x_1\)，其他步驟保持不變。通過這種方式改進之后，隨機游走算法的尋優能力大大提高，而且對于初始值的依賴程度也降低了。令\(n=10\)，初始點為\((-100,-10)\),\(N=100,\lambda=10.0,\epsilon = 0.00001\)，改進的隨機游走算法實現代碼如下：
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time : 2017/7/20 10:48
# @Author : Lyrichu
# @Email : 919987476@qq.com
# @File : improve_random_walk.py
'''
@Description:改進的隨機游走算法
這里求解:f = sin(r)/r + 1,r = sqrt((x-50)^2+(y-50)^2)+e,0<=x,y<=100 的最大值
求解f的最大值，可以轉化為求-f的最小值問題
'''
from __future__ import print_function
import math
import random
N = 100 # 迭代次數
step = 10.0 # 初始步長
epsilon = 0.00001
variables = 2 # 變量數目
x = [-100,-10] # 初始點坐標
walk_num = 1 # 初始化隨機游走次數
n = 10 # 每次隨機生成向量u的數目
print("迭代次數:",N)
print("初始步長:",step)
print("每次產生隨機向量數目:",n)
print("epsilon:",epsilon)
print("變量數目:",variables)
print("初始點坐標:",x)
# 定義目標函數
def function(x):
r = math.sqrt((x[0]-50)**2 + (x[1]-50)**2) + math.e
f = math.sin(r)/r + 1
return -f
# 開始隨機游走
while(step > epsilon):
k = 1 # 初始化計數器
while(k < N):
# 產生n個向量u
x1_list = [] # 存放x1的列表
for i in range(n):
u = [random.uniform(-1,1) for i1 in range(variables)] # 隨機向量
# u1 為標準化之后的隨機向量
u1 = [u[i3]/math.sqrt(sum([u[i2]**2 for i2 in range(variables)])) for i3 in range(variables)]
x1 = [x[i4] + step*u1[i4] for i4 in range(variables)]
x1_list.append(x1)
f1_list = [function(x1) for x1 in x1_list]
f1_min = min(f1_list)
f1_index = f1_list.index(f1_min)
x11 = x1_list[f1_index] # 最小f1對應的x1
if(f1_min < function(x)): # 如果找到了更優點
k = 1
x = x11
else:
k += 1
step = step/2
print("第%d次隨機游走完成。" % walk_num)
walk_num += 1
print("隨機游走次數:",walk_num-1)
print("最終最優點:",x)
print("最終最優值:",function(x))
輸出結果如下：
迭代次數: 100
初始步長: 10.0
每次產生隨機向量數目: 10
epsilon: 1e-05
變量數目: 2
初始點坐標: [-100, -10]
第1次隨機游走完成。
第2次隨機游走完成。
第3次隨機游走完成。
.....
第20次隨機游走完成。
隨機游走次數: 20
最終最優點: [49.999997561093195, 49.99999839875969]
最終最優值: -1.15111685082
可以發現，即使迭代次數\(N=100\)不大，初始點\((-100,-10)\)離最優點\((50,50)\)非常遠，改進的隨機游走算法依然可以達到最優點。這說明了改進的隨機游走算法具有更強大的尋優能力以及對于初始點更低的依賴性。
注：經過多次試驗發現，無論是隨機游走算法還是改進的隨機游走算法，對于步長都是非常依賴的。步長\(\lambda\)越大，意味著初始可以尋找最優解的空間越大，但同時也意味著更多的迭代次數(要搜索空間變大，尋找次數變多，相應時間自然要增加)。如果步長取得過小，即使\(N\)很大，也很難達到最優解。無論對于隨機游走算法還是改進的隨機游走算法皆是如此。所以理論上步長\(\lambda\)越大越好。但是步長越大，迭代總次數越高，算法運行時間越長。所以實踐中可以多試驗幾次，將\(\lambda\)取得適當地大即可。
