clock怎么巧记忆，智造讲堂：智能优化方法的重要元素

引自：《制造智能技术基础》（主编：张智海, 副主编：李冬妮、苏丽颖、张磊、贾旭杰、裴植、谢小磊）

优化算法有三个要素：决策变量（decision variable）、约束条件（constraints）和目标函数（objective function）。

在最优化问题中，目标函数指与变量有关的待求其极值(或最大值最小值)的函数。决策变量是指最优化问题中所涉及的与约束条件和目标函数有关的待确定的变量。而约束条件则限制了对决策变量的赋值，以及搜索时解空间的大小。

可行解就是满足约束条件的x的值，也称可行点或容许点。全体可行解构成的集合称为可行域，也称为容许集，记为D。

「 1. 智能优化方法的分类 」

优化方法可以分为精确算法和近似算法两大类。常见的精确算法包括分支界限法、背景分割法和动态规划法等，精确算法的计算复杂度一般比较大，只适合于求解小规模问题，并不适用于求解现代制造业的复杂优化问题，通常会与其他优化算法结合起来使用。近似算法，或称启发式算法，包括一些专用算法和元启发式算法。元启发式算法又可进一步分为基于个体行为的爬山法、模拟退火算法、禁忌搜索算法等；基于群体行为的进化类算法和群智能算法等。

目前常用的智能优化方法，按其产生来源、算法机理、求解更新过程等要素的不同，可以有多种分类方式。本文按照算法产生根源，分为以下三类。

1）模仿生物种群进化机制的进化类算法

主要有遗传算法、差分进化算法、免疫算法等。

①遗传算法：是模拟生物在自然环境中的遗传和进化过程而形成的自适应随机全局搜索和优化方法。算法操作的基本过程是在解决方案种群中逐次产生一个近似最优解，称为一代；在每一代中，根据个体在问题域中的适应度和从自然遗传学中借鉴来的再造方法进行选择，产生一个新的近似解，即下一代。新个体比原个体更适应环境，即解更优。

②差分进化算法：是通过群体内个体间的合作与竞争产生的智能优化搜索方法，采用一对一的竞争生存策略，同时具有记忆能力，可跟踪搜索情况以调整搜索策略。

③免疫算法：是模仿生物免疫机制，采用群体搜索策略并迭代计算；利用自身多样性和维持机制，克服早熟问题，求解全局最优。

2）模仿生物群体行为社会性的群体智能算法

主要有蚁群算法、粒子群优化算法、人工蜂群算法、人工鱼群算法、杜鹃搜索算法、萤火虫算法、狼群算法、混合蛙跳算法和菌群优化算法等。本文主要介绍蚁群算法和粒子群算法。其他算法的基本原理类似，有兴趣的读者可以自行学习。

①蚁群算法是通过模拟自然界中蚂蚁集体寻径行为而提出的基于种群智能行为的启发式随机搜索算法。

②粒子群算法是一种基于群体智能的全局随机搜索算法。

3）模仿某些物理过程规律的算法

主要有模拟退火算法、烟花算法、禁忌搜索算法等。

模拟退火算法是一种基于迭代求解策略的随机寻优算法，是局部搜索算法的扩展，以一定的概率选择邻域内距离目标值最大的状态。

「 2. 贪心算法与启发式规则 」

在设计算法求解优化问题中，贪心算法与启发式规则是两种常见的设计思想。

1）贪心算法

顾名思义，贪心算法的思想就是总是做出在当前看来最好的选择，即，总是选择当前的最大值或最小值，并不从整体最优考虑。它所做出的选择只是在某种意义上的局部最优选择。

虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，贪心算法即使不能得到整体最优解，也能得到比较好的近似解。

（1）采用贪心算法的基本条件

①问题具备贪心选择性质。对于一个具体问题，要确定它是否具备贪心选择性质，必须证明每一步所作的贪心选择能最终求出问题的整体最优解，即所求问题的整体最优解可以通过一系列局部最优选择，即贪心地选择来达到。

这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。动态规划算法通常以自底向上的方式求解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式做出贪心选择，每做一次贪心选择就将所求问题简化为规模更小的子问题。

②问题具有最优子结构性质。指一个问题的最优解包含其子问题的最优解。所求问题是否具备最优子结构性质是该问题能否采用贪心算法进行求解的关键特征。在实际操作中，一般判断一个问题是否适用贪心算法，可以先选择该问题下的几个实际数据进行分析验证，就可以做出判断。

（2）贪心算法的基本思路

从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到算法中的某一步不能再继续前进时，算法停止。其一般求解步骤为：

①对问题进行数学建模；

②把要求解的问题分成若干个子问题；

③对每个子问题求解，得到子问题的局部最优解；

④把子问题的解局部最优解合成原来问题的一个解。

（3）贪心算法的主要问题

贪心算法不能保证求得的最后解是最佳的；不能用来求最大或最小解问题；只能求满足某些约束条件的可行解的范围。

2）启发式规则

采用某种算法求解一个问题，希望得到的是该问题每个实例的最优解。而启发式算法则是在可接受的计算成本（多指计算时间和存储空间的开销）内，求出问题每个实例的一个可行解，也就是在实际问题的背景下，可被接受的解。并且该可行解与该问题的最优解之间的偏离程度通常不可预计。

算法设计人员可以通过一定的启发式规则来求出问题的一个可行解，这类规则通常基于直观感受或相关经验。例如在求解作业车间调度问题中，就可以采用先到先服务原则（FCFS），对到达的订单进行排产。即优先对先到达的订单进行排产，再对后到达的订单进行排产。又如还可以采用最长处理时间（LPT）原则进行排产，即先集中产能优先生产在制造过程中耗时最多的产品，再生产耗时较少的产品。相应地，也可以采用最短处理时间（SPT）原则进行排产，即将生产速度最快、消耗工时最短的工件排在优先生产的计划中。

「 3. 局部搜索与群体智能 」

对于某些计算起来非常复杂的最优化问题，找到最优解需要花费的时间会随着问题规模扩大呈指数型增长。考虑到现实中的工程问题，为了在实际可接受的时间和计算成本内、求得精度可接受的解，诞生了各种启发式算法来寻找次优解。局部搜索就是这样一种以时间换精度的启发式算法。

局部搜索算法从一个初始解开始，通过邻域动作，产生其邻居解，判断邻居解的质量，根据某种策略来选择邻居解，重复上述过程，直至到达终止条件。不同局部搜索算法的区别在于邻域动作的定义和选择邻居解的策略，同时这也是决定算法好坏的关键。

邻域动作是一个函数，通过这个函数，对当前解，产生其相应的邻居解集合。

在基本局部搜索算法的基础上，还产生了多种改进的总局搜索算法。典型的有迭代局部搜索（iterated local search，ILS）和变邻域搜索（variable neighborhood search，VNS）两种。

迭代局部搜索是在局部搜索得到的局部最优解上，加入扰动，再重新进行局部搜索。其思想是：物以类聚，好的解之间会有一些共性，所以在局部最优解上做扰动，比随机的选择一个初始解在进行局部搜索，效果更好。

变邻域搜索的主要思想是：采用多个不同的邻域进行系统搜索。首先采用最小的邻域搜索，当无法改进解的质量时，则切换到稍大一点的邻域。如果能继续改进解，则退回到最小的邻域，否则继续切换到更大的邻域。利用不同的动作构成的邻域结构进行交替搜索，从而在集中性和疏散性之间达到很好的平衡。

群体智能源于对以蚂蚁、蜜蜂等为代表的社会性昆虫群体行为的研究中，最早被用在细胞机器人系统的描述中。单只蚂蚁的智能并不高，它看起来不过是一段长着腿的神经节而已。几只蚂蚁凑到一起，就可以一起往蚁穴搬运路上遇到的食物。如果是一群蚂蚁，它们就能协同工作，建起坚固、漂亮的巢穴，一起抵御危险，抚养后代。这种群居性生物表现出来的智能行为被称为群体智能。

Millonas在1994年提出群体智能应该遵循5条基本原则：

①邻近原则（proximity principle），群体能够进行简单的空间和时间计算；

②品质原则（quality principle），群体能够响应环境中的品质因子；

③多样性反应原则（principle of diverse response），群体的行动范围不应该太窄；

④稳定性原则（stability principle），群体不应在每次环境变化时都改变自身的行为；

⑤适应性原则（adaptability principle），在所需代价不太高的情况下，群体能够在适当的时候改变自身的行为。

这些原则说明实现群体智能的智能主体必须能够在环境中表现出自主性、反应性、学习性和自适应性等智能特性。群体智能的核心是由众多简单个体组成的群体能够通过相互之间的简单合作来实现某一功能，完成某一任务。简单个体是指单个个体只具有简单的能力或智能，而简单合作是指个体和与其邻近的个体进行某种简单的直接通信或通过改变环境间接与其他个体通信，从而可以相互影响、协同动作。

群体智能具有以下特点：

①具有较强的鲁棒性。群体智能的控制是分布式的，不存在中心控制。即不会由于某一个或几个个体出现故障而影响群体对整个问题的求解。

②具有较好的可扩展性。群体中的每个个体都能够改变环境。由于群体智能可以通过非直接通信的方式进行信息的传输与合作，因而随着个体数目的增加，通信开销的增幅较小。

③具有简单性。群体中每个个体的能力或遵循的行为规则非常简单。因而群体智能的实现比较方便。

④具有自组织性。群体表现出来的复杂行为是通过简单个体的交互过程突现出来的智能。

人们正是基于对这类生物群体智能行为的观察与研究，发明了蚁群、粒子群等智能优化算法。

「 4. 元启发式算法与超启发式算法 」

元启发式算法将随机算法与局部搜索算法相结合，其优化机理不过分依赖于算法的组织结构信息，可以广泛的应用到函数的组合优化和函数计算中。

现代的元启发式算法主要包括模拟退火算法、遗传算法、列表搜索算法、进化规划、进化策略、蚁群算法(ACA)和人工神经网络等。不同算法在优化机制方面存在一定的差异，但在优化流程上却具有较大的相似性，均是一种邻域搜索结构。算法都是从一个（一组）初始解出发，在算法关键参数的控制下通过邻域函数产生若干邻域解，按接受准则（确定性、概率性或混沌方式）更新当前状态，再按照关键参数修改准则调整关键参数。如此重复上述搜索步骤直到满足算法的收敛准则，最终得到问题的优化结果。

随着近年来智能计算领域的发展，又出现了一类被称为超启发式算法（hyper-heuristic algorithm）的新算法类型。不同于启发式算法，寻找的是问题的解。超启发式算法可以简单阐述为寻找启发式算法的启发式算法，其求解的是一些启发式算法的组合。超启发式算法更加严格的定义是：提供了一种高层次启发式方法，通过管理或操纵一系列低层次的启发式算法（low-level heuristics，LLH），以产生新的启发式算法。这些新启发式算法被用于求解各类组合优化问题。