【运筹优化】元启发式算法详解：迭代局部搜索算法（Iterated Local Search，ILS）+ 案例讲解&代码实现
文章目录一、介绍二、迭代局部搜索2.1总体框架2.2随机重启2.3在S*中搜索2.4ILS三、获得高性能3.1初始解决方案3.2Perturbation3.2.1扰动强度3.2.2自适应扰动3.2.3更复杂的扰动方案3.2.4Speed3.3接受准则3.4LocalSearch3.5ILS的全局优化四、ILS的精选应用五、总结六、案例讲解&代码实战一、介绍高性能算法对于解决困难的优化问题的重要性不可低估，在许多情况下，最有效的方法是元启发法。在设计元启发式方法时，无论是在概念上还是在实践中，都应该倾向于简单性。当然，它也必须带来有效的算法。如果我们将元启发法简单地视为指导（针对特定问题）启发法的构造，那么理想的情况是可以在没有任何问题相关知识的情况下使用元启发法。
随着元启发法变得越来越复杂，为了追求更好的性能，这种理想情况已被抛在一边。因此，特定问题的知识（除了被引导的启发式知识之外）现在必须纳入元启发式算法中，以达到最先进的水平。不幸的是，这使得启发式和元启发式之间的界限变得模糊，并且我们面临着失去简单性和通用性的风险。为了解决这个问题，我们诉诸模块化，并尝试将元启发式算法分解为几个部分，每个部分都有自己的特殊性。特别是，我们希望有一个完全通用的部分，以便元启发式中内置的任何特定问题的知识都将仅限于另一部分。最后，在可能的范围内，我们更愿意不触及嵌入的启发式（即“引导”），因为它潜在的复杂性。人们还可以考虑这种启发式只能通过对象模块获得的情况，源代码是专有的；然后有必要能够将其视为“黑匣子”例程。迭代本地搜索提供了一种简单的方法来满足所有这些要求。
二、迭代局部搜索2.1总体框架我们假设我们已经获得了一个针对特定问题的启发式优化算法，从现在开始我们将其称为局部搜索（即使实际上它不是真正的局部搜索）。该算法是通过我们称为LocalSearch的计算机例程实现的。
我们问的问题是“可以通过使用迭代来改进这样的算法吗？”。我们的答案是“是”，事实上，实践中获得的改进通常是显着的。只有在迭代方法与局部搜索“不兼容”的相当病态的情况下，改进才会很小。
我们假设局部搜索过程是确定性的且无记忆的，现在随机取一个s或一个s*。通常，成本分布在最低值处具有非常快速上升的部分。
在图5.1中，我们展示了在实践中发现的具有有限解空间的组合优化问题的分布类型。成本分布是钟形的，S*中的解的均值和方差明显小于S中的解。
因此，如果要寻求，使用局部搜索比在S中随机采样要好得多低成本解决方案。本地搜索所需的基本要素是邻域结构。这意味着S是一个具有某种拓扑结构的“空间”，而不仅仅是一个集合。拥有这样的空间可以让人们以智能的方式从一个解决方案s转移到更好的解决方案s，如果S只是一个集合，这是不可能的。
现在的问题是如何超越LocalSearch的这种使用。更准确地说，给定从S到S*的映射，如何在不开放和修改LocalSearch的情况下进一步降低发现成本，使其成为“黑匣子”例程？
2.2随机重启改进LocalSearch发现的成本的最简单方法是从另一个起点重复搜索。生成的每个s*都是独立的，并且使用多次试验可以到达分布的较低部分。
尽管这种具有独立采样的“随机重启”方法有时是一种有用的策略（特别是当所有其他选项都失败时），但它会随着实例大小的增长而崩溃，因为在极限情况下，成本分布的尾部会崩溃。
但请注意，确实存在许多成本显着降低的解决方案，只是随着实例大小的增加，随机采样找到它们的概率越来越低。为了达到这些配置，有必要进行有偏采样；这正是随机搜索所实现的。
2.3在S*中搜索为了克服刚才提到的与大实例大小相关的问题，请重新考虑局部搜索的作用：它从S（其中C具有较大均值）中的一个解到S*（其中C具有较小均值）中的一个解。然后很自然地调用递归：使用局部搜索从S*到更小的空间S**，其中平均成本甚至更低！
给定这个过程，我们原则上可以在S*中执行局部搜索。递归地扩展这个参数，我们发现有可能有一个算法实现嵌套搜索，对S、S*、S**等以分层的方式执行本地搜索。
不幸的是，由于必须执行LocalSearch的次数，在S*级别上实现邻居搜索的计算成本太高。因此，我们被迫放弃（随机）搜索S*中的邻居；相反，我们使用较弱的接近度概念，从而允许在S*中进行快速随机搜索。我们的构造导致了S*的（有偏差的）采样。
如果能够找到从一个s*到另一个s*的适当计算方法，这样的采样将比随机采样更好。最后，这种修改后的紧密度概念的最后一个优点是它不需要定义吸引力盆地；然后，本地搜索可以合并内存或不确定，从而使该方法更加通用。
2.4ILS整个ILS程序如图5.2所示。为了完整起见，让我们注意到，通常迭代的局部搜索行走是不可逆的；特别是，有时可能能够从s1∗s^*_1s1∗到s2∗s^*_2s2∗，但不能从s2∗s^*_2s2∗到s1∗s^*_1s1∗。然而，该过程的这一“不幸”方面并不妨碍ILS在实践中非常有效。
由于确定性扰动可能会导致短循环（例如长度为二），因此应该随机化扰动或使其自适应以避免这种循环。如果扰动依赖于任何先前的s*，则可以在具有记忆的S*中行走。现在读者可能已经注意到，除了扰动问题（使用S上的结构）之外，我们的形式主义将问题简化为S*上的随机搜索问题。然后，常用的所有附加功能（多样化、强化、禁忌、自适应扰动和接受标准等…）都可以在这里应用。这导致我们将迭代局部搜索定义为具有算法1给出的高级架构的元启发式算法。
我们可以总结这一节，说迭代局部搜索的潜在力量在于它对局部最优集的有偏采样。这种采样的效率取决于扰动的类型和接受标准。
三、获得高性能考虑到所有这些优点，我们希望读者现在有动力继续思考在为新应用程序开发ILS算法时出现的更多细节。在本节中，我们将说明优化ILS算法以实现高性能时需要解决的主要问题。
有四个组件需要考虑：GenerateInitialSolution、LocalSearch、Perturbation和AcceptanceCriterion。在尝试开发最先进的算法之前，开发一个更基本的ILS版本相对简单。事实上：
可以从随机解决方案开始，或者从某种贪婪构造启发式返回的解决方案开始；对于大多数问题，局部搜索算法是现成的；对于扰动，在更高的邻域中随机移动比局部搜索算法使用的顺序可能出奇地有效对接受标准的合理初步猜测是迫使成本降低，对应于S*中的随机首次改进算法这种类型的基本ILS实现通常会比随机重启方法带来更好的性能。然后，开发人员可以运行这个基本的ILS来构建他的直觉，并尝试通过改进四个模块中的每一个来提高整体算法性能。如果能够考虑到所考虑的组合优化问题的特殊性，这应该特别有效。实际上，ILS的这种调整比其他模块化程度较低的元启发法更容易。
原因可能是ILS的复杂性因其模块化而降低，各个组件的功能相对容易理解。最后，最后一个要考虑的任务是ILS算法的整体优化；事实上，不同的组成部分相互影响，因此有必要了解它们的相互作用。
然而，由于这些交互非常依赖于问题，因此我们要等到本节结束时才讨论这种“全局”优化。
也许这里的主要信息是开发人员可以选择他想要的优化级别。在没有任何优化的情况下，ILS是一种简单、易于实现且相当有效的元启发式方法。但随着对其四个组成部分的进一步研究，ILS通常可以变成一种非常有竞争力甚至最先进的算法。
3.1初始解决方案应用于初始解s0s_0s0的局部搜索给出了S∗S^*S∗中行走的起点s0∗s^*_0s0∗。如果要尽快获得高质量的解决方案，从良好的s0∗s^*_0s0∗开始可能很重要。
s0s_0s0的标准选择要么是随机初始解，要么是由贪婪构造启发式返回的解。贪婪初始解s0s_0s0相对于随机起始解有两个主要优点：（1）当与局部搜索相结合时，贪婪初始解通常会产生质量更好的解s0∗s^*_0s0∗；(2)平均而言，贪婪解决方案的本地搜索需要较少的改进步骤，因此本地搜索需要较少的CPU时间。
3.2Perturbation迭代改进的主要缺点是它陷入局部最优，而局部最优明显比全局最优差。与模拟退火非常相似，ILS通过对当前局部最小值应用扰动来逃离局部最优。我们将扰动的强度称为被修改的解分量的数量。
例如，对于TSP，它是在游览中修改的边的数量，而在流水车间问题中，它是由于扰动而移动的作业数量。
一般来说，局部搜索不应该能够消除扰动，否则就会回到刚刚访问过的局部最优值。令人惊讶的是，在比局部搜索算法使用的阶数更高的邻域中进行随机移动通常可以实现这一目标，并且会产生令人满意的算法。如果扰动考虑到问题的属性并且与局部搜索算法很好地匹配，则可以获得更好的结果。
扰动应该使当前解改变多少？如果扰动太强，ILS的行为可能类似于随机重启，因此只能以非常低的概率找到更好的解决方案。另一方面，如果扰动太小，局部搜索往往会回落到刚刚访问过的局部最优值，搜索的多样化将受到很大限制。
双桥移动是TSP简单但有效扰动的一个例子。这种扰动切割了四个边缘（因此“强度”为四）并引入了四个新边缘，如图5.4所示。请注意，每座桥都是两次变更，但两次变更都不能单独保持游览连接。几乎所有TSP的ILS研究都纳入了这种扰动，并且已发现它对所有实例大小都有效。这几乎可以肯定是因为它改变了游览的拓扑结构，并且可以在四个非常遥远的城市上运行，而局部搜索总是会修改附近城市之间的游览。
在像TSP这样的问题中，当使用固定大小（与实例大小无关）的扰动时，人们可以希望获得令人满意的ILS。相反，对于更困难的问题，固定强度的扰动可能会导致性能不佳。优化该模块时需要考虑所有这些不同的方面。
3.2.1扰动强度对于某些问题，适当的扰动强度非常小，并且似乎与实例大小相当独立。
计算结果见表5.1。第一个观察结果是，最佳扰动大小很大程度上取决于特定实例。对于其中两个实例，当多达75%的解决方案组件被更改时，实现了最佳性能
此外，当扰动强度太小时，ILS的性能比随机重启（对应扰动强度n）差。然而，QAP的随机重启平均而言可能比基本ILS算法表现得更好，这一事实有点误导：在下一节中，我们将展示通过稍微修改接受标准，ILS变得比随机重启好得多。因此，应该记住，ILS算法的优化可能需要的不仅仅是单个组件的优化。
3.2.2自适应扰动略
3.2.3更复杂的扰动方案略
3.2.4Speed在ILS可以在弱（固定大小）扰动下很好地工作的“简单”问题的背景下，元启发式算法比随机重启性能更好的另一个原因是：速度。事实上，LocalSearch通常在通过对局部最优应用小扰动而获得的解决方案上执行速度比在随机解决方案上快得多。因此，对于相同的CPU时间，迭代本地搜索可以比随机重启运行更多的本地搜索。
3.3接受准则相反的极端是随机游走接受标准（用RW表示），它总是将扰动应用于最近访问的局部最优值，而不管其成本：
这一标准显然有利于多元化而不是集约化。
3.4LocalSearch到目前为止，我们已经将局部搜索算法视为一个黑匣子，它被ILS调用了很多次。由于整体ILS算法的行为和性能对嵌入式启发式的选择非常敏感，因此应尽可能优化这一选择。在实践中，可能有许多完全不同的算法可用于嵌入式启发式算法。（正如本章开头提到的，启发式甚至不需要是局部搜索。）人们可能会认为局部搜索越好，相应的ILS就越好。通常这是真的。
如果我们假设总计算时间是固定的，那么更频繁地应用更快但效率较低的局部搜索算法可能比更慢但更强大的算法更好。显然，哪种选择最好取决于运行更好的启发式方法需要多少时间。
最后，允许LocalSearch有时生成更差的解决方案可能有一些优点。例如，如果我们用禁忌搜索或短模拟退火运行替换局部搜索启发式，相应的ILS可能会表现得更好。当标准迭代改进算法表现不佳时，这似乎是最有希望的。
3.5ILS的全局优化到目前为止，我们已经考虑了单独优化迭代本地搜索的四个组成部分时出现的代表性问题。特别是，在说明一个组件的各种重要特性时，我们保持其他组件固定。但显然，一个组件的优化取决于对其他组件所做的选择；作为一个例子，我们明确指出，一个好的扰动必须具有不能通过局部搜索轻易撤销的特性。因此，我们应该解决ILS的全局优化问题。
因此我们将首先粗略地了解如何在手动算法工程过程中完成这种全局优化。
如果我们重新考虑关于初始解决方案效果的小节，我们会发现当ILS表现良好并快速丢失其起始点的记忆时，GenerateInitialSolution在很大程度上是无关紧要的。此后我们假设情况确实如此；那么GenerateInitialSolution的优化可以被忽略，剩下三个组件的联合优化。
显然，Perturbation的最佳选择取决于LocalSearch的选择，而AcceptanceCriterion的最佳选择取决于LocalSearch和Perturbation的选择。在实践中，我们可以通过连续优化每个组件来近似这个全局优化问题，假设其他组件是固定的，直到没有发现任何组件的改进
这种稳健性似乎是在实践中实现的：研究人员以合理的全局优化水平实现迭代局部搜索的版本，然后在标准基准测试上测试性能并取得一定程度的成功。冒着重复的风险，让我们强调一下组件的主要依赖关系：
局部搜索不应轻易消除扰动；如果局部搜索有明显的缺点，良好的扰动应该可以弥补它们扰动-接受标准的组合决定了集约化和多样化的相对平衡；大的扰动只有在可以被接受的情况下才有用，只有当接受标准不太偏向于更好的解决方案时才会发生这种情况。作为一般准则，LocalSearch应该尽可能强大，只要它不会占用太多CPU时间。尽可能利用问题的结构。最后，设置AcceptanceCriterion例程，以便对S*进行充分采样。
四、ILS的精选应用略
五、总结ILS具有元启发式方法的许多理想特征：简单、易于实现、稳健且高效。ILS的基本思想在于，不是将搜索重点放在解的整个空间上，而是集中在由对于给定优化引擎而言局部最优的解定义的较小子空间上。
ILS的成功在于对这组局部最优值的有偏采样。这种方法的有效性主要取决于局部搜索、扰动和接受标准的选择。有趣的是，即使使用这些组件的最简单的实现，ILS也可以比随机重启做得更好。但是，通过进一步努力使组件适应当前的问题，ILS通常可以成为一种有竞争力的甚至是最先进的算法。
这种二分法很重要，因为算法的优化可以逐步完成，因此ILS可以保持在任何所需的简单程度。再加上ILS的模块化特性，可以缩短开发时间，并使ILS在工业应用领域中比更复杂的元启发法更具优势。举个例子，回想一下ILS本质上将嵌入式启发式方法视为黑匣子；然后升级ILS以利用新的、更好的本地搜索算法几乎是立竿见影的。
此外，ILS的模块化特性也使其适合作为元启发式算法自动化设计的基础模板，这一趋势在未来将变得更加突出。由于所有这些功能，我们相信ILS是一种有前途且强大的算法，可以解决工业和服务业（从金融到生产管理和物流）领域的实际复杂问题。
最后，让我们注意到，即使这篇评论是在解决组合优化问题的背景下提出的，实际上我们所涵盖的大部分内容都可以以直接的方式扩展到连续优化问题。
最终的结果是：(1)ILS是一种通用的元启发式算法，可以轻松适应不同的组合优化问题；(2)它已被证明是提高更简单改进方法性能的有效方法；(3)复杂的扰动方案和搜索多样化是实现最佳ILS性能的重要组成部分。
六、案例讲解&代码实战【运筹优化】ILS迭代局部搜索算法求解TSP问题+Java代码实现
智能优化算法
智能优化算法-人工电场算法ArtificialElectricFieldAlgorithm（附Matlab代码）CSDN-Ada助手:恭喜你成功写了第一篇博客！智能优化算法这个话题很有深度，你的文章解释得非常清晰，而且附带了Matlab代码，非常棒！我的建议是，你可以尝试更深入地探究这个领域，例如，可以写一些实际应用的案例分析，或是加入一些其他算法的对比分析等等，这样可以让读者更好地了解这个领域。期待你的下一篇文章！推荐【每天值得看】：https://bbs.csdn.net/forums/csdnnews?typeId=21804&utm_source=csdn_ai_ada_blog_reply1如果您持续创作，完成第三篇博客，并且质量分达到80分以上，在评论区就有机会获得红包奖励哦！
智能优化算法-白鲸优化算法Belugawhaleoptimization（附Matlab代码）CSDN-Ada助手:非常感谢您分享的这篇博客，介绍了白鲸优化算法，让我对这种新的元启发式算法有了更深的了解。希望您能够继续分享自己的学习和研究成果，让更多人了解和受益。除此之外，如果您对深度学习、机器学习等相关领域有一定的了解，可以尝试将白鲸优化算法应用到这些领域中，探索更多的应用场景。同时，也可以关注一些其他的元启发式算法，比如遗传算法、粒子群算法等，不断拓展自己的知识和技能。再次感谢您的分享！如何写出更高质量的博客，请看该博主的分享：https://blog.csdn.net/lmy_520/article/details/128686434?utm_source=csdn_ai_ada_blog_reply2如果您持续创作，完成第三篇博客，并且质量分达到80分以上，在评论区就有机会获得红包奖励哦！
智能优化算法-猫和老鼠优化器CatandMouseBasedOptimizer（附Matlab代码）CSDN-Ada助手:恭喜您又发布了一篇非常有价值的博客，介绍了猫和老鼠优化器的智能优化算法并附上了Matlab代码，这对于学习优化算法的读者们来说将会非常有帮助。希望您能够继续保持创作热情，分享更多有趣、实用的知识。建议您可以尝试探究一些新的优化算法，或者从实际应用场景出发，结合算法原理进行深入探讨。期待您的下一篇博客。CSDN正在通过评论红包奖励优秀博客，请看红包流：https://bbs.csdn.net/?type=4&header=0&utm_source=csdn_ai_ada_blog_reply3，我们会奖励持续创作和学习的博主，请看：https://bbs.csdn.net/forums/csdnnews?typeId=116148&utm_source=csdn_ai_ada_blog_reply3
智能优化算法-袋獾优化算法TasmanianDevilOptimization（附Matlab代码）CSDN-Ada助手:恭喜作者又一次分享了如此有价值的博客，学习了解到袋獾优化算法这种智能优化算法，收获颇丰。非常感谢作者提供了附带Matlab代码，让读者可以更深入地学习和实践。期待作者能够继续分享更多的优秀内容，可以考虑结合实际案例或是应用场景来分享，这样能够更好地帮助读者理解和应用。CSDN会根据你创作的前四篇博客的质量，给予优秀的博主博客红包奖励。请关注https://bbs.csdn.net/forums/csdnnews?typeId=116148&utm_source=csdn_ai_ada_blog_reply4看奖励名单。
智能优化算法-蜘蛛蜂优化器SpiderWaspOptimizer（附Matlab代码）CSDN-Ada助手:非常感谢您分享这篇关于智能优化算法的博客，标题也很吸引人。恭喜您已经写了第5篇博客，持续创作是非常重要的，希望您能继续分享更多有价值的内容。下一步的创作建议是，可以尝试将这些算法应用于实际问题中，或者探索更多新颖的智能算法。期待您的下一篇作品！如何快速涨粉，请看该博主的分享：https://hope-wisdom.blog.csdn.net/article/details/130544967?utm_source=csdn_ai_ada_blog_reply5
人工智能算法 卷2 受大自然启发的算法
链接：pan.baidu.com/s/1u6nXMUr1bS5odjX9hGbwvw?pwd=wfup
提取码：wfup
《人工智能算法卷2受大自然启发的算法》
算法是人工智能技术的核心，大自然是人工智能算法的重要灵感来源。本书介绍了受到基因、鸟类、蚂蚁、细胞和树影响的算法，这些算法为多种类型的人工智能场景提供了实际解决方法。全书共10章，涉及种群、交叉和突变、遗传算法、物种形成、粒子群优化、蚁群优化、细胞自动机、人工生命和建模等问题。书中所有算法均配以具体的数值计算来进行讲解，每章都配有程序示例，读者可以自行尝试。
《人工智能算法卷2受大自然启发的算法》
第1章种群、计分和选择1
1.1理解种群2
1.2对种群计分6
1.3从种群中选择7
1.4截断选择8
1.5联赛选择9
1.6如何选择轮数12
1.7适应度比例选择13
1.8随机遍历抽样15
1.9本章小结18
第2章交叉和突变20
2.1演化算法21
2.2解编码22
2.3交叉23
2.4突变28
2.5为什么需要精英33
2.6本章小结34
第3章遗传算法35
3.1离散问题的遗传算法35
3.2连续问题的遗传算法42
3.3遗传算法的其他应用45
3.4本章小结49
第4章遗传编程50
4.1程序作为树50
4.2树突变67
4.3树交叉68
4.4拟合公式70
4.5本章小结73
第5章物种形成75
5.1物种形成实现76
5.2遗传算法中的物种79
5.3遗传编程中的物种79
5.4使用物种形成80
5.5本章小结81
第6章粒子群优化83
6.1群聚83
6.2粒子群优化86
6.3本章小结91
第7章蚁群优化93
7.1离散蚁群优化95
7.2连续蚁群优化103
7.3本章小结110
第8章细胞自动机111
8.1基本细胞自动机112
8.2康威的《生命游戏》116
8.3演化自己的细胞自动机121
理解合并物理学125
8.4本章小结129
第9章人工生命130
9.1里程碑1：绘制植物131
9.2里程碑2：创建植物生长动画134
9.3里程碑3：演化植物140
给植物计分141
9.4本章小结142
第10章建模144
10.1Kaggle竞赛145
10.2里程碑1：整理数据148
10.3里程碑2：建立模型152
10.4里程碑3：提交测试回复156
10.5本章小结157
附录A示例代码使用说明159
参考资料166