如何用源代码做网站,搭建网站工具,北京装修公司家装排名,石材做网站1. 关于全局最优化求解全局最优化是一个非常复杂的问题#xff0c;目前还没有一个通用的办法可以对任意复杂函数求解全局最优值。上一篇文章讲解了一个求解局部极小值的方法——梯度下降法。这种方法对于求解精度不高的情况是实用的#xff0c;可以用局部极小值近似替代全局最…1. 关于全局最优化求解全局最优化是一个非常复杂的问题目前还没有一个通用的办法可以对任意复杂函数求解全局最优值。上一篇文章讲解了一个求解局部极小值的方法——梯度下降法。这种方法对于求解精度不高的情况是实用的可以用局部极小值近似替代全局最小值点。但是当要求精确求解全局最小值时梯度下降法就不适用了需要采用其他的办法求解。常见的求解全局最优的办法有拉格朗日法、线性规划法、以及一些人工智能算法比如遗传算法、粒子群算法、模拟退火算法等(可以参见我之前的博客)。而今天要讲的是一个操作简单但是不易陷入局部极小值的方法随机游走算法。2. 随机游走算法操作步骤设\(f(x)\)是一个含有\(n\)个变量的多元函数,\(x(x_1,x_2,…,x_n)\)为\(n\)维向量。给定初始迭代点\(x\)初次行走步长\(\lambda\)控制精度\(\epsilon\)(\(\epsilon\)是一个非常小的正数用于控制结束算法)。给定迭代控制次数\(N\)\(k\)为当前迭代次数置\(k1\)。当 \(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 : 919987476qq.com# File : random_walk.pyDescription:使用随机游走算法求解函数极值这里求解:f sin(r)/r 1,r sqrt((x-50)^2(y-50)^2)e,0x,y100 的最大值求解f的最大值可以转化为求-f的最小值问题from __future__ import print_functionimport mathimport randomN 100 # 迭代次数step 0.5 # 初始步长epsilon 0.00001variables 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.ef math.sin(r)/r 1return -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 1x x1else:k 1step step/2print(第%d次随机游走完成。 % walk_num)walk_num 1print(随机游走次数:,walk_num-1)print(最终最优点:,x)print(最终最优值:,function(x))输出结果如下:迭代次数: 100初始步长: 0.5epsilon: 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\)可以在一定程度上增加寻优能力比如设置\(N3000,\lambda10.0\)得到结果如下迭代次数: 3000初始步长: 10.0epsilon: 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(i1,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\)其他步骤保持不变。通过这种方式改进之后随机游走算法的寻优能力大大提高而且对于初始值的依赖程度也降低了。令\(n10\)初始点为\((-100,-10)\),\(N100,\lambda10.0,\epsilon 0.00001\)改进的随机游走算法实现代码如下#!/usr/bin/env python# -*- coding: utf-8 -*-# Time : 2017/7/20 10:48# Author : Lyrichu# Email : 919987476qq.com# File : improve_random_walk.pyDescription:改进的随机游走算法这里求解:f sin(r)/r 1,r sqrt((x-50)^2(y-50)^2)e,0x,y100 的最大值求解f的最大值可以转化为求-f的最小值问题from __future__ import print_functionimport mathimport randomN 100 # 迭代次数step 10.0 # 初始步长epsilon 0.00001variables 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.ef math.sin(r)/r 1return -f# 开始随机游走while(step epsilon):k 1 # 初始化计数器while(k N):# 产生n个向量ux1_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对应的x1if(f1_min function(x)): # 如果找到了更优点k 1x x11else:k 1step step/2print(第%d次随机游走完成。 % walk_num)walk_num 1print(随机游走次数:,walk_num-1)print(最终最优点:,x)print(最终最优值:,function(x))输出结果如下迭代次数: 100初始步长: 10.0每次产生随机向量数目: 10epsilon: 1e-05变量数目: 2初始点坐标: [-100, -10]第1次随机游走完成。第2次随机游走完成。第3次随机游走完成。.....第20次随机游走完成。随机游走次数: 20最终最优点: [49.999997561093195, 49.99999839875969]最终最优值: -1.15111685082可以发现即使迭代次数\(N100\)不大初始点\((-100,-10)\)离最优点\((50,50)\)非常远改进的随机游走算法依然可以达到最优点。这说明了改进的随机游走算法具有更强大的寻优能力以及对于初始点更低的依赖性。注经过多次试验发现无论是随机游走算法还是改进的随机游走算法对于步长都是非常依赖的。步长\(\lambda\)越大意味着初始可以寻找最优解的空间越大但同时也意味着更多的迭代次数(要搜索空间变大寻找次数变多相应时间自然要增加)。如果步长取得过小即使\(N\)很大也很难达到最优解。无论对于随机游走算法还是改进的随机游走算法皆是如此。所以理论上步长\(\lambda\)越大越好。但是步长越大迭代总次数越高算法运行时间越长。所以实践中可以多试验几次将\(\lambda\)取得适当地大即可。
