局部搜索之随机游走

随机游走（random walk）是局部搜索算法中最简单的一个，它的基本策略就是每次从当前候选解的邻居中选择一个更优的进行转移。在二维世界里，如果你一直这样随机游走下去，你还是可能到达你的目的地的，就如一个醉汉在大街上盲目的走，如果他一直随机游走下去，最后很有可能回到自己的家，但是如果是三维世界，醉汉开飞机，概率就很低了，维度越高，概率越低。

基本的随机游走

每次随机选择一个当前解的邻域点进行比较，如果优于当前解则将该点作为新的中心。如果连续N次都找不到更优的值，则认为，最优解就在以当前最优解为中心，当前步长为半径的N维球内(如果是三维，则刚好是空间中的球体)。此时，如果步长已经小于阈值，则结束算法；否则，令步长减半，开始新一轮游走。

# -*- coding: utf-8 -*-
'''
使用随机游走算法求解函数极值
'''
import math
import random

#========================================================
#  运行参数
#========================================================

N = 50 # 迭代次数
step = 10 # 初始步长
epsilon = 0.00001 # 终止条件
variables = 2 # 变量数目
x = [100,200] # 初始点坐标
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)
    return r

def randomwalk(x):
    '''
    随机漫步
    '''
    dx = [random.uniform(-1,1) for i in range(variables)] # 随机向量
    dx_s = [dx[i]/math.sqrt(sum([dx[i]**2 for i in range(variables)])) for i in range(variables)] # 标准化后的随机向量
    x_new = [x[i] + step*dx_s[i] for i in range(variables)]
    return x_new

#========================================================
#  主程序
#========================================================
if __name__ == '__main__':
    # 开始随机游走
    while(step > epsilon):
        k = 1 # 初始化计数器
        while(k < N):
            x_new=randomwalk(x)
            if(function(x_new) < function(x)): # 如果找到了更优点
                k = 1
                x = x_new
            else:
                k += 1
        step = step/2
        print("第%d次随机游走完成。" % walk_num)
        walk_num += 1

    print("随机游走次数:",walk_num-1)
    print("最终最优点:",x)
    print("最终最优值:",function(x))

改进的随机游走

改进的随机游走算法的不同之处是在于原来是产生一个随机向量u，现在则是产生n个随机向量u₁,u₂,⋯,u_n，n是给定的一个正整数。通过这种方式改进之后，随机游走算法的寻优能力大大提高，而且对于初始值的依赖程度也降低了。

# -*- coding: utf-8 -*-
'''
使用随机游走算法求解函数极值
'''
import math
import random

#========================================================
#  运行参数
#========================================================

N = 50 # 迭代次数
step = 10 # 初始步长
epsilon = 0.00001 # 终止条件
variables = 2 # 变量数目
x = [100,200] # 初始点坐标
walk_num = 1
n = 10 # 每次随机生成向量u的数目
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)
    return r

def randomwalk(x):
    '''
    随机漫步
    '''
    dx = [random.uniform(-1,1) for i in range(variables)] # 随机向量
    dx_s = [dx[i]/math.sqrt(sum([dx[i]**2 for i in range(variables)])) for i in range(variables)] # 标准化后的随机向量
    x_new = [x[i] + step*dx_s[i] for i in range(variables)]
    return x_new

#========================================================
#  主程序
#========================================================
if __name__ == '__main__':
    # 开始随机游走
    while(step > epsilon):
        k = 1 # 初始化计数器
        while(k < N):
            x_list = [] # 存放n个邻域点的列表
            for i in range(n):
                x_list.append(randomwalk(x))
                i += 1
            f_list = [function(point) for point in x_list]
            f_min = min(f_list)
            f_index = f_list.index(f_min)
            x_new = x_list[f_index] # 最小f对应的point
            if(function(x_new) < function(x)): # 如果找到了更优点
                k = 1
                x = x_new
            else:
                k += 1
        step = step/2
        print("第%d次随机游走完成。" % walk_num)
        walk_num += 1

    print("随机游走次数:",walk_num-1)
    print("最终最优点:",x)
    print("最终最优值:",function(x))