基础知识

传统最优化算法：线性规划

线性规划：目标函数和约束条件都是线性的，决策变量是连续的。

求法是单纯形法，实际使用，各大语言都已经有成熟的函数可以直接拿来用了，所以了解原理即可。

整数规划：将线性规划的决策变量变成整数离散即可。

求法是分支定界法，将整数规划的整数变为连续，就是松弛后的规划（相当于线性规划），求出的结果代表可能的上界，如果不如现有最值，那这个分支就没用了，剪枝。否则就继续分支。

是否可解的探讨：NP问题

1.P（polynomial）： 多项式内可解

2.NP（non-deterministic polynomial）：多项式内可验证。只能验证一个结果是否正确，但是无法求出所有解。

3.NP-hard：任意一个NP都可以规约到NPH问题。假设能解决NPH问题，就一定能解决NP问题。

4.NP-completeness：当NPH问题本身就是NP时，则称为NPC问题。

一些补充：

1.规约举例：能解决一元二次就必然能解决一元一次问题。这是将一元一次规约到一元二次上了。

2.P类必是NP，如果连NP都做不到，更别提P了。

3.对于NPC，世界上已有1w+问题被证明是NPC问题，这可能是证明P=NP的机会。如果能证明一个NPC是P，那么所有NP都就是P了。但是还没人整出来。

4.下图是目前的分类，NPH问题中有一部分是NPC，其属于NP问题。如果未来能够证明NP=P，那么就可以将NPC，NP，P全部统一。

 

智能搜索概述

如何实现智能？

高大上的方式是剪枝，很容易想到的是随机，人的特性就是不稳定，机器才是极端稳定，极度稳定未必就比略微的不稳定好。

所以记住随机这个核心。

局部搜索

局部搜索之所以叫局部，是因为每次决策变量的变化与判断都是在一个邻域里进行的。

最朴素的思路就是登山搜索，但是只看邻域的贪心思路容易陷入局部最优解。

这是因为登山搜索依赖于初始化位置与最优决策。

解决思路一是局部束搜索，通过并行多路搜索来进行更合理的决策，这相当于在随机初始化做手脚。

另一种思路就是模拟退火，通过一定的概率来选择非最优情况来避免，这是通过改变最优决策来实现。 

登山搜索

基本思路

登山搜索思路朴素，假设我们要登山：

1.随机初始化。

2.在当前点邻域里逐个判断，找出最优点。

3.如果有非当前点的最优点，则移动到最优点，继续2步骤。

4.否则就说明当前点已经局部最优，就是最终结果。

实际做法——八皇后问题

具体实施，其实最难的在于邻域如何选择。对于简单的函数优化，邻域就在坐标轴上，非常简单。但是对于平常的问题，决策变量有非常多，甚至决策变量的取值之间也会存在约束，比如不能选相同的值（比如求解最佳顺序问题，不可能AB都是第一位）。

 

回到问题，八皇后问题属于求解约束满足问题，对于这类问题，不冲突的决策变量肯定不用变，没必要变，所以要在冲突的变量里选择要变的决策变量。那在冲突的变量里选择一个该怎么选呢？选择违反约束最少的变量。这就是最小冲突启发式算法选择变量值。

注意，冲突变量是会变的，每次变成新状态，都要重新计算冲突变量，有可能原来不是冲突变量，变了一下以后就变成冲突变量了。

还需要补充一个邻域算子的概念，邻域算子可以理解为一个函数，所有算法都用，用来产生一个变量的邻域，但是不同问题具体产生的邻域肯定不同。

那么给出八皇后的最终算法与例子：

基于登山搜索（最小冲突启发式）的局部搜索算法对于百万皇后问题有极好的性能，这是因为搜索空间虽然O（），但合法状态分布集中，意味着整体来看，任意随机生成的状态距离合法状态只有几步之遥，所以无论有多少皇后，迭代次数都不会多，时间反而消耗在了计算冲突上面了。

登山搜索的局限性

解空间的地形是很复杂的，可能有平的，也有可能是局部最优等等。

随机重启搜索

随机重启就是重复n次搜索，取最好的一次。

局部束搜索（Beam Search）

局部束搜索通过改变初始状态来克服初始化依赖的问题。

其实这个和k个随机点重启动的登山搜索只差在了：并行点之间信息是互通的。举例分析：

比如一个状态可以产生10000个后继，我们跟踪3个状态，定义为ABC。

这三个状态可以产生10000*3-30000个状态，分为ABC三组。

局部束搜索的三个新状态，在30000个状态中直接挑选。注意，这新的三个状态完全可能集中在A组中，这就体现了三个束互相影响的特点了，可以理解为先合并成一股，然后再分出三头。反观随机重启，完全就是平行不相交的三股，新的状态必须在ABC中各有一个。

————————————————

本文转载自CSDN博主：亦梦亦醒乐逍遥

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

原文链接：https://blog.csdn.net/weixin_50295745/article/details/123886311

 

基础知识

传统最优化算法：线性规划

线性规划：目标函数和约束条件都是线性的，决策变量是连续的。

求法是单纯形法，实际使用，各大语言都已经有成熟的函数可以直接拿来用了，所以了解原理即可。

整数规划：将线性规划的决策变量变成整数离散即可。

求法是分支定界法，将整数规划的整数变为连续，就是松弛后的规划（相当于线性规划），求出的结果代表可能的上界，如果不如现有最值，那这个分支就没用了，剪枝。否则就继续分支。

是否可解的探讨：NP问题

1.P（polynomial）： 多项式内可解

2.NP（non-deterministic polynomial）：多项式内可验证。只能验证一个结果是否正确，但是无法求出所有解。

3.NP-hard：任意一个NP都可以规约到NPH问题。假设能解决NPH问题，就一定能解决NP问题。

4.NP-completeness：当NPH问题本身就是NP时，则称为NPC问题。

一些补充：

1.规约举例：能解决一元二次就必然能解决一元一次问题。这是将一元一次规约到一元二次上了。

2.P类必是NP，如果连NP都做不到，更别提P了。

3.对于NPC，世界上已有1w+问题被证明是NPC问题，这可能是证明P=NP的机会。如果能证明一个NPC是P，那么所有NP都就是P了。但是还没人整出来。

4.下图是目前的分类，NPH问题中有一部分是NPC，其属于NP问题。如果未来能够证明NP=P，那么就可以将NPC，NP，P全部统一。

 

智能搜索概述

如何实现智能？

高大上的方式是剪枝，很容易想到的是随机，人的特性就是不稳定，机器才是极端稳定，极度稳定未必就比略微的不稳定好。

所以记住随机这个核心。

局部搜索

局部搜索之所以叫局部，是因为每次决策变量的变化与判断都是在一个邻域里进行的。

最朴素的思路就是登山搜索，但是只看邻域的贪心思路容易陷入局部最优解。

这是因为登山搜索依赖于初始化位置与最优决策。

解决思路一是局部束搜索，通过并行多路搜索来进行更合理的决策，这相当于在随机初始化做手脚。

另一种思路就是模拟退火，通过一定的概率来选择非最优情况来避免，这是通过改变最优决策来实现。 

登山搜索

基本思路

登山搜索思路朴素，假设我们要登山：

1.随机初始化。

2.在当前点邻域里逐个判断，找出最优点。

3.如果有非当前点的最优点，则移动到最优点，继续2步骤。

4.否则就说明当前点已经局部最优，就是最终结果。

实际做法——八皇后问题

具体实施，其实最难的在于邻域如何选择。对于简单的函数优化，邻域就在坐标轴上，非常简单。但是对于平常的问题，决策变量有非常多，甚至决策变量的取值之间也会存在约束，比如不能选相同的值（比如求解最佳顺序问题，不可能AB都是第一位）。

 

回到问题，八皇后问题属于求解约束满足问题，对于这类问题，不冲突的决策变量肯定不用变，没必要变，所以要在冲突的变量里选择要变的决策变量。那在冲突的变量里选择一个该怎么选呢？选择违反约束最少的变量。这就是最小冲突启发式算法选择变量值。

注意，冲突变量是会变的，每次变成新状态，都要重新计算冲突变量，有可能原来不是冲突变量，变了一下以后就变成冲突变量了。

还需要补充一个邻域算子的概念，邻域算子可以理解为一个函数，所有算法都用，用来产生一个变量的邻域，但是不同问题具体产生的邻域肯定不同。

那么给出八皇后的最终算法与例子：

基于登山搜索（最小冲突启发式）的局部搜索算法对于百万皇后问题有极好的性能，这是因为搜索空间虽然O（），但合法状态分布集中，意味着整体来看，任意随机生成的状态距离合法状态只有几步之遥，所以无论有多少皇后，迭代次数都不会多，时间反而消耗在了计算冲突上面了。

登山搜索的局限性

解空间的地形是很复杂的，可能有平的，也有可能是局部最优等等。

随机重启搜索

随机重启就是重复n次搜索，取最好的一次。

局部束搜索（Beam Search）

局部束搜索通过改变初始状态来克服初始化依赖的问题。

其实这个和k个随机点重启动的登山搜索只差在了：并行点之间信息是互通的。举例分析：

比如一个状态可以产生10000个后继，我们跟踪3个状态，定义为ABC。

这三个状态可以产生10000*3-30000个状态，分为ABC三组。

局部束搜索的三个新状态，在30000个状态中直接挑选。注意，这新的三个状态完全可能集中在A组中，这就体现了三个束互相影响的特点了，可以理解为先合并成一股，然后再分出三头。反观随机重启，完全就是平行不相交的三股，新的状态必须在ABC中各有一个。

————————————————

本文转载自CSDN博主：亦梦亦醒乐逍遥

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

原文链接：https://blog.csdn.net/weixin_50295745/article/details/123886311