非光滑优化算法

franciscochonge · 发表于 2022-8-24 13:57

优化问题类型 - 非平滑优化
优化问题类型

非平滑优化 (NSP)
解决 NSP 问题
其他问题类型

非平滑优化 (NSP)
最难解决的优化问题类型是非光滑问题 (NSP)。这样的问题通常是或必须假定为非凸的。因此它可能不仅有多个可行区域和每个区域内的多个局部最优点——因为某些函数是非光滑甚至不连续的，导数或梯度信息通常不能用于确定函数增加的方向（或减少）。换句话说，一种可能的解决方案的情况很少能提供关于在哪里寻找更好解决方案的信息。
除了最简单的问题之外，详尽地列举所有可能的解决方案并选择最好的解决方案是不切实际的，即使在一台速度很快的计算机上也是如此。因此，大多数方法依赖于对可能解决方案的某种随机抽样。这些方法是不确定的或随机的——它们可能在不同的运行中产生不同的解决方案，即使从同一模型上的同一点开始，也取决于随机抽样的点。
解决 NSP 问题
遗传或进化算法提供了一种为非平滑优化问题找到“好的”解决方案的方法。（在遗传算法中，问题被编码在算法操作的一系列位串中；在“进化算法”中，直接使用决策变量和问题函数。大多数商业求解器产品都基于进化算法。）
这些算法维护大量候选解决方案，而不是迄今为止的单一最佳解决方案。从现有的候选解决方案中，他们通过单个点的随机突变或两个或多个现有点的交叉或重组来生成新的解决方案。然后人口接受选择，倾向于消除最差的候选解决方案并保留最好的解决方案。重复这个过程，产生越来越好的解决方案；但是，这些方法无法确定给定的解决方案是真正最优的。
Tabu Search 和 Scatter Search提供了另一种方法来找到非平滑优化问题的“好”解决方案。这些算法还维护大量候选解决方案，而不是迄今为止的单一最佳解决方案，并且它们从旧解决方案生成新解决方案。但是，它们较少依赖随机选择，而更多地依赖确定性方法。禁忌搜索使用过去搜索结果的记忆来指导未来搜索的方向和强度。这些方法连续生成更好的解决方案，但与遗传和进化算法一样，这些方法无法确定给定的解决方案是真正最优的。

非平滑优化

Frontline Systems 的优化器使用以下方法解决非平滑优化问题：

遗传和进化算法
禁忌搜索和散点搜索

有关这些类型问题的解释，请参阅优化问题类型：非平滑优化。
标准Microsoft Excel Solver和Premium Solver不提供用于解决全局优化问题的内置工具。
遗传和进化算法

高级求解器平台使用混合进化求解器来解决非平滑优化问题。这种混合求解器使用来自遗传和进化算法的方法以及“经典”优化方法的组合。它将整数变量和所有不同的约束（即变量集的排列）作为本机类型处理。
大规模 SQP 求解器引擎集成了与高级求解器平台相同的混合进化求解器，以解决非平滑优化问题，使用 SQP 方法进行本地搜索。该求解器对于混合了许多线性或平滑非线性函数和一些非平滑函数的问题特别有效。此 Solver 中的遗传算法方法使用四种类型的变异算子，其中两种特定于排列，四种类型的交叉算子，其中两种特定于排列。比赛选择用于交叉候选人，并且将更大的淘汰概率分配给最不适合的成员的算法用于更新总体。
此 Solver 中的“经典”方法使用无梯度直接搜索、基于梯度的准牛顿法和线性化局部梯度法。有几种方法用于满足约束，包括随机“约束修复”方法和确定性线性和非线性约束求解方法。
禁忌搜索和散点搜索

OptQuest Solver Engine使用禁忌搜索和分散搜索来解决非平滑优化问题。它将整数变量和所有不同的约束（即变量集的排列）作为本机类型处理。OptQuest Solver 中的散点搜索系统地生成某些参考点的线性组合以创建新点，每个参考点映射到满足整数和所有不同约束的关联点。然后叠加禁忌搜索以控制每个阶段的参考点组成。OptQuest Solver 中的禁忌搜索保留了对过去搜索结果的记忆，以指导未来搜索的方向、强化和多样化。

		自动登录	找回密码
密码			立即注册