图片
有很多不同的方法可以解决数学优化问题。你可以使用贪心算法（Greedy algorithms）、约束规划（Constraint programming）、混合整数规划（Mixed integer programming）、遗传算法（Genetic algorithms）、局部搜索美工（Local search）等。根据问题的规模和类型，以及期望的解的质量，不同的技术可能会有不同的效果。
这篇文章概述不同的用于解决离散优化问题的启发式方法。首先，我将解释描述一个优化问题所需的三个组成部分。然后，我将解释一些常见的且效果良好的搜索启发式方法。
优化问题
要数学地定义一个优化问题，你需要以下三个组成部分：决策变量（Decision variables）、约束（Constraints）和目标（Objective）。
让我们来看一个简单的例子。你是一家小型快递公司老板，每送一个包裹你都会赚取不同的金额。送货车的空间是有限的。快递公司希望在每次送货中尽可能地送出总价值最高的包裹。你应该选择哪些包裹来配送呢？
图片
决策变量
决策变量可以取不同的值。目标是找到决策变量的最佳值。什么是最佳值？这取决于目标和约束条件。在快递例子中，每个包裹都有一个二元决策变量。如果包裹不会被送出，则变量为0；如果包裹会被送出，变量为1。
约束条件
约束条件是指限制解的范围或规定哪些情况是不可接受的。通过正确地设置这些条件，你可以确保找到一个既符合实际需求又能够在现实中实施的解决方案。在快递例子中，你不能送出所有的包裹，因为送货车的空间是有限的。如果送货车的最大容量为600，你需要添加一个约束条件，确保选择的包裹总和不超过这个限制。
目标
目标是在优化问题中你想要最大化或最小化的部分。快递公司的目标是选择最有价值的包裹进行配送。在目标函数中，你希望最大化所选择包裹的总价值。
如果问题定义得当（即存在可行解），那么优化问题总是存在至少一个最优解的。找到这些最优解之一可能很困难，尤其是当问题规模大且复杂时。本文讨论的所有技术并不能保证找到最优解，但如果你正确应用它们于大型问题，它们可能比使用约束或混合整数规划技术的解更快。
优化技术
你可以使用不同的启发式方法（Heuristics）来解决优化问题。这里，我将解释其中一些方法。
我假设你已经熟悉暴力求解法，它是尝试所有可能的解并跟踪最佳解的过程。另一种你可能知道的技术是动态规划，它将问题分解为较小的子问题。当问题规模较小时，暴力求解和动态规划是完全可以使用的。但当问题规模增加时，它们会耗时过长且效率低下。暴力求解和动态规划并不是启发式方法，因为它们并不会减少搜索空间。你可以选择将暴力求解与局部搜索或遗传算法结合起来，通过系统地测试一个较小子集中的所有可能解（暴力求解）。
贪心算法
要解决快递公司的问题，一个简单的方法是使用贪心算法。它们提供了一个基线，并且能够非常快速地给出解决方案。贪心算法的思路是，你不断选择包裹装进送货车，但不是随意选择，而是从价值最高的包裹开始。你重复这个过程，依次选择价值较高的包裹，直到送货车的容量被完全利用。假设送货车的最大容量是60，以下是我们选择的包裹：
图片
还有其他方法可以决定下一个包裹。通过将每个包裹的价值与其大小相除，可以得到每个包裹的单位尺寸的价值。你可以将其描述为价值密度。通过选择单位尺寸价值最高的包裹，有可能提出更好的解决方案。
图片
贪心算法的一个优点是它速度快。但对于更复杂的问题，在大多数情况下，解远非最优。
局部搜索
局部搜索非常直观。它的工作原理如下：你从一个初始解开始，通过逐步对这个解进行小幅调整来提高它的效果。每次调整都是为了使目标函数的值更高。你不断重复这个过程，直到找不到任何进一步提高目标函数的小调整为止。
让我们再次来看快递的例子。我们可以从一个解开始：
图片
局部移动可以是用一个未选中的包裹替换一个已选中的包裹。我们时刻注意容量限制，尝试在每次局部移动时都满足这个约束条件。一个移动的例子可以是：
图片
通过这个移动，新的目标值为115。我们将值较低的包裹从选择中移除，并添加值较高的包裹，同时仍然保持一个可行的解。
所有你可以通过应用一个局部移动达到的可能解被称为当前解的邻域。
你不能超出送货车的容量限制。因此在这种情况下，如果一个包裹比任何其他包裹都大，即使其价值很高，我们也永远不会选择这个包裹！
这是局部搜索的一个缺点：你可能会陷入局部最优解：
图片
为了克服这个问题，电商美工外包网有一些方法。你可以选择一次交换多个包裹，并将其视为一个移动。通过这样做，邻域扩大了，可以达到更多的解。
你也可以选择从多个解开始，而不是仅仅一个。然后你对每个解重复交换的过程，这称为迭代局部搜索。
另一种方法是选择以一定概率使目标变差的操作：
图片
如果温度参数较高，接受使目标值下降的移动的概率就高。如果温度较低，这个概率就低。模拟退火（Simulated annealing）利用了这种概率。它以高温开始，然后逐渐降低。这意味着在开始时，你是在解空间中进行随机游走。当温度降低时，搜索变得局部化。模拟退火在困难的基准测试上表现出色。
最后，我想提到的一种逃避局部最优解的技术是禁忌搜索（Tabu search）。禁忌搜索的想法是记录你已经访问过的解，不允许再次回到它们。将所有之前的解保存在内存中可能会很昂贵。你可以选择存储过渡状态或保持固定大小的禁忌列表。
可以将迭代局部搜索、模拟退火和禁忌搜索等技术结合起来使用。
遗传算法
你也可以选择使用遗传算法。遗传算法的核心概念是模仿自然选择的过程，每个解都被称为一个个体。算法从一个由多个个体组成的初始种群开始。然后，你计算每个个体的适应度，它表示解的优劣。适应度最高的个体，即表现最好的解，会被选出来进行繁殖，以产生下一代的解。
在快递例子中，每个包裹是一个基因，可以取0或1的值。初始种群包含四个个体，可能如下所示：
图片
交叉:交换最优个体的基因，直到交叉点。
现在我们选择适应度最高的个体（目标值最高的）来产生后代。在这个例子中，个体2和4具有最高的适应度。产生后代的常见方法是随机选择一个交叉点，并在这个交叉点之前交换基因。
下一步是突变。我们以较低的随机概率翻转一些基因，在这个例子中，取0.14（1除以7，7是包裹的数量）。这是一个重要的步骤，因为我们希望保持多样性，并防止过早收敛。我们将突变后代1：
图片
突变:以一定概率将一个基因从0 -> 1或1 -> 0转换。
现在，我们将计算新个体的适应度。种群的大小是固定的。适应度最低的个体将被淘汰。
图片
这里是完整的算法：
创建初始种群。
重复直到收敛：
选择适应度最高的个体。
选择一个交叉点以创建后代。突变基因。
计算适应度，部分个体被淘汰。
使用遗传算法时，也有可能陷入局部最优。可以通过多种方式克服这一问题。你可以创建初始种群的子集，并在选择阶段进行随机化。这可以防止在选择过程中一再使用相同的种群。避免局部最小值的另一种方法是给予那些存活时间较长的个体和/或与其他个体更为独特的个体额外的奖励，因为它们可能有助于找到一个更具普遍性的解。
混合技术
最后讨论的快速找到高质量解的方法是结合不同的技术。
例如，大邻域搜索就是将局部搜索与约束规划（CP）或混合整数规划（MIP）结合在一起。CP和MIP的缺点是它们在面对大规模问题时可能会遇到困难，并且需要大量时间来获得最优解。通过将局部搜索与CP或MIP结合起来，可以得到两者的优点。你可以用CP或MIP解决小型子问题，并通过局部搜索选择新的子问题。
大邻域搜索的步骤是：
从问题的一个可行解开始。可以使用任何你喜欢的技术找到一个解。
重复直到满足某一标准：
选择一个邻域（问题的一部分）。
详情页设计优化这个子问题（使用CP或MIP）。
在求解过程中，你要跟踪最佳解。邻域可以通过例如固定一组变量来定义。
混合方法的另一个例子是记忆算法。记忆算法结合了遗传算法和局部搜索。
在这篇文章中美工，你看到了不同的用于解决数学优化问题的启发式方法。希望你可以通过局部搜索、遗传算法或混合方法快速找到优化问题的解决方案！还有其他有趣且表现良好的搜索启发式方法，如粒子群优化、蚁群优化和随机隧道。
本站仅提供存储服务，所有内容均由用户发布，如发现有害或侵权内容，请点击举报。 特别声明：以上内容（如有图片或视频亦包括在内）来源于网络，不代表本网站立场。本网站仅提供信息存储服务。如因作品内容、版权和其他问题需要同我们联系的，请联系我们及时处理。联系方式：451255985@qq.com，进行删除。