抱歉,您的浏览器无法访问本站
本页面需要浏览器支持(启用)JavaScript
了解详情 >

爬山算法

算法概念

爬山算法类似于贪心搜索,它每次都会查找附近节点里的最优节点,并移动到最优节点,如此循环便找到最优解,但是它只能找到局部的最优解,而非整体最优解

问题示例

以搜索最高点为例,已知山坡的高度f(x,y)满足 DearXuan 给定初始地点,找到最高点

显然x和y的范围是无穷大的,无法遍历全部结果,因此采用爬山算法找到局部最优解

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <cmath>

using namespace std;

#define pai 3.141592653589
#define e 2.718281828284
#define step 0.1
#define Node _Node

//计算(x,y)处的高度
double f(double x, double y) {
double x2 = x * x, y2 = y * y;
double x_2 = (x - 2) * (x - 2), y_2 = (y - 3) * (y - 3);
return pow(e, -(x2 + y2)) + 4 * pow(e, -(x_2 + y_2));
}

//节点类
class _Node {
public:
double x;//x坐标
double y;//y坐标
double height;//高度
void init(double x, double y);//初始化节点
};

void _Node::init(double x, double y) {
this->x = x;
this->y = y;
this->height = f(x, y);
}

//查找附近的最高点并返回
Node Search(Node node) {
double x = node.x;
double y = node.y;
Node nodes[4];
nodes[0].init(x + step, y);
nodes[1].init(x - step, y);
nodes[2].init(x, y + step);
nodes[3].init(x, y - step);
for (Node &i: nodes) {
//查找最高点
if (i.height > node.height) {
node = i;
}
}
return node;
}

int main() {
Node node;
Node nearly;
double x, y;
scanf("%ld%lf", &x, &y);
node.init(x, y);
while (true) {
nearly = Search(node);
if (nearly.height == node.height) {
//如果最高点是自己或者和自己一样高,说明已经找到局部最优解
break;
} else {
//最高点不是自己,继续查找
node = nearly;
}
}
printf("\nx: %lf\ny: %lf\nHeight: %lf\n", node.x, node.y, node.height);
return 0;
}

初始位置为(0.5, 0.5)

DearXuan

初始位置为(5, 5)

DearXuan

模拟退火算法

Metropolis准则

Metropolis准则使用随机因素来确定是否接收新状态

设时间为t, 温度为T, 状态函数F(t), 下一状态F(t+1)

接收(t+1)状态的概率为P,且P满足

DearXuan

其中k是[0,1]范围内的实数

算法概念

模拟退火算法遵循Metropolis准则,按照一定的概率接受下一个解,即使它是非最优解,因此随着迭代次数的增加,最终会趋向于全局最优解

问题示例

已知山坡高度f(x)满足 DearXuan 求x∈[0, 20]时山坡的最低点

通过图像可以看出该函数拥有多个极小值点
DearXuan
如果使用爬山算法会在其中一个极小值点结束

爬山算法
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
#include <iostream>
#include <cmath>

using namespace std;

#define ERROR INT32_MAX
#define step 0.1

double x_min = 0;//最小值
double x_max = 20;//最大值

//计算函数值
double f(double x) {
if (x < x_min || x > x_max) {
//超出界限,返回int32的最大值
return ERROR;
} else {
return x + sin(x) - 2 * cos(2 * x);
}
}

//使用爬山算法求解
int main() {
double x;
cin >> x;//输入初始位置
double height = f(x);//状态值(高度)
for (;;) {
//获取x的左边和右边的状态值
double x1 = x + step, x2 = x - step;
double h1 = f(x1), h2 = f(x2);
//用x1和h1保存两边的较低点
if (h2 < h1) {
h1 = h2;
x1 = x2;
}
//将两边的较优解与当前解比较
if (h1 < height) {
//存在比当前位置更优的解,则向该位置移动
x = x1;
height = h1;
} else {
//两边都不存在更优的解,退出循环
break;
}
}
printf("x: %lf\nh: %lf\n", x, height);
return 0;
}

DearXuan
显然x=12.3并不是全局的最优解,而是局部最优解

现使用模拟退火算法的思路改良爬山算法:

  1. 每次从当前解周围随机取一个新的解
  2. 如果新的解更优,则直接替换当前解
  3. 如果当前解更优,则按照一定概率接受新的解
模拟退火算法
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <cmath>
#include <sysinfoapi.h>

using namespace std;

#define step 0.1

double x_min = 0;//最小值
double x_max = 20;//最大值

double k = 0.9;
double T = 50000;//初始温度
double dT = 0.99;//下降倍率
double minT = 100;//最低温度
int num = 50000;//迭代次数

double x;
double height;
double x_next;
double height_next;

//计算函数值
double f(double x) {
return x + sin(x) - 2 * cos(2 * x);
}

//获取start到end的随机数
double random(double start, double end) {
double len = end - start;//区间长度
double r = rand() / ((double) RAND_MAX + 1.0);//0到1之间的随机数
return start + r * len;
}

//使用模拟退火算法求解
int main() {
cin >> x;//输入初始位置
height = f(x);
while (T > minT) {
//重置随机数种子
srand(GetTickCount());
for (int i = 0; i < num; i++) {
//添加(-0.5, 0.5)的扰动,获取新的解
x_next = x + random(-1, 1);
//确保新的解不越界,否则直接跳过
if (x_next >= x_min && x_next <= x_max) {
height_next = f(x_next);
if (height_next < height) {
//新的解更优,直接替换当前解
x = x_next;
height = height_next;
} else {
//当前解更优,以一定的概率接受新的解
double dx = x_next - x;
double p = exp(dx / (T * k));
if (p < random(0, 1)) {
x = x_next;
height = height_next;
}
}
}
}
T *= dT;
}
printf("x: %lf\nh: %lf\n", x, height);
return 0;
}

DearXuan
成功找到全局最优解

评论