人工智能基础-局部搜索算法

#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;
}

#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;
}

#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;
}