2.3　学习型智能优化算法的框架与流程

本书针对连续优化问题设计并实现了一种求解函数优化问题的学习型遗传算法；针对离散优化问题设计并实现了求解3类典型离散优化问题的5种学习型智能优化方法；针对实际工程问题设计并实现了求解体系仿真优化问题的学习型遗传算法、求解卫星地面站系统任务调度的学习型蚁群算法和求解多星任务规划问题的学习型蚁群算法；这些方法稍加修改就可以推广到其他复杂优化问题的求解中。

• 求解函数优化问题的学习型遗传算法。将5种交叉算子、8种变异算子和5种灾变（局部优化）算子有效地集成到学习型遗传算法中，根据算子绩效知识为每次操作智能地选择交叉、变异或灾变算子。学习型遗传算法从演化过程中挖掘算子绩效知识，在优化过程中基于算子绩效知识尽可能使用那些优化性能高的算子，从而极大地提高了优化性能。采用21个标准测试函数进行实验，结果表明学习型遗传算法在优化性能方面优于近期公开发表的3种典型方法。
• 求解非对称旅行商问题的学习型遗传算法。在参数绩效知识的指导下，采用动态参数决策模型为下次迭代随机选择参数组合；使用多次操作取最优策略执行交叉和变异操作；采用种群替换和局部搜索来改进当前种群中的部分个体。在遗传算法、动态参数决策模型和局部优化的共同作用下，学习型遗传算法的优化绩效得到了极大提高。采用非对称旅行商问题的16个标准实例进行实验，结果表明学习型遗传算法在优化性能方面优于近期公开发表的4种典型方法。
• 求解双层CARP优化问题的学习型遗传算法。为了提高初始种群质量，采用两种扩展启发式方法来辅助生成初始种群；为了提高遗传操作效率，采用多种不同算子来实现选择、交叉和变异操作，同时基于算子绩效知识为每次选择、交叉和变异选择操作算子；为了进一步提高遗传操作效率，基于构件顺序知识为每次交叉和变异选择合适的断点位置；为了保持种群多样性，采用局部替换程序不断地向当前种群中注入新的优秀个体。采用双层CARP优化问题的87个测试实例进行实验，结果表明学习型遗传算法在优化性能方面优于其他两种改进方法。
• 求解双层CARP优化问题的学习型蚁群算法。为了消除蚁群算法对参数的敏感性，采用动态参数决策模型为每次迭代动态地选择参数组合；为了提高蚁群算法的效率，基于构件聚类知识和构件顺序知识来构建可行解；为了进一步提高蚁群算法的效率，采用2-Opt方法对每次迭代中的最优解进行局部优化。采用双层CARP优化问题的87个测试实例进行实验，结果表明学习型蚁群算法在优化性能方面优于其他3种改进方法。
• 求解柔性作业车间调度问题的学习型蚁群算法。在参数绩效知识的指导下，采用动态参数决策模型为下次迭代随机选择参数组合；从优化过程中不断抽取构件知识，采用构件知识来指导人工蚂蚁的后续寻优过程；采用调度改进操作来改进当前方案集中的部分个体。在蚁群算法、动态参数决策模型、构件知识模型和局部优化模型的共同作用下，学习型蚁群算法的优化绩效得到了极大提高。采用柔性作业车间调度问题的15个标准实例进行实验，结果表明学习型蚁群算法在优化性能方面优于近期公开发表的7种典型方法。
• 求解柔性车间作业调度问题的学习型协同进化算法。各个种群采用不同的进化方法和参数设置来推进各自的演化进程；种群之间通过相互的资源竞争和信息共享，共同推动着整体算法的进化进程。采用柔性作业车间调度问题的15个标准实例进行实验，结果表明学习型协同进化算法在优化性能方面优于近期公开发表的7种典型方法。
• 求解体系仿真优化问题的学习型遗传算法。采用量化正交遗传算法在整个可行域内快速地搜索出一些较优方案；应用灵敏度分析方法对已评估方案进行分析，得到待研究体系各输入变量的灵敏度知识；应用变量灵敏度知识来指导量化正交遗传算法继续在可行域内搜索最优解。数据实例结果表明，本方法是可行的、正确的和有效的。
• 求解卫星地面站系统任务调度的学习型蚁群算法。将蚁群优化和导向局部搜索有效地结合在一起，极大地提高了学习型蚁群算法的优化绩效。计算结果表明，学习型蚁群算法能有效地求解卫星地面站系统任务调度问题。
• 求解多星任务规划问题的学习型蚁群算法。在参数绩效知识的指导下，采用动态参数决策模型为下次迭代随机选择参数组合；从优化过程中不断抽取构件知识，采用构件知识来指导人工蚂蚁的后续寻优过程。采用多星任务规划问题的21个测试实例进行实验，结果表明学习型蚁群算法在优化性能方面优于其他两种方法。

2.3.1　求解函数优化问题的学习型遗传算法框架与流程

函数优化问题是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用算例。遗传算法是求解函数优化问题的一种非常有力的工具，大量理论分析和实际应用都表明遗传算法能有效地求解函数优化问题。遗传算法从点的群体开始搜索，对初始点集要求不高；遗传算法不是直接在参变量集上实施，而是利用参变量集的某种编码；遗传算法利用个体适应度值信息，无需导数或其他辅助信息，在搜索过程中不容易陷入局部最优；即使适应度函数是不连续的、非规则的或有噪声的，遗传算法也能以较大概率找到全局最优解。实践表明，遗传算法求解函数优化问题的计算效率比较高、适用范围相当广。与传统优化方法相比，遗传算法具有简单通用、鲁棒性强、适于并行处理以及高效、实用等优点。

虽然遗传算法对函数优化问题的求解非常有效，但在应用遗传算法求解函数优化问题时，以下问题还有待进一步研究：发展一些启发式策略，引入领域知识，对搜索过程给予指导或引导；最大限度地减少参数环境对遗传算法性能和结果质量的影响；研究遗传算法的选择策略，使之具有更广泛的适用性，避免早熟；进一步研究遗传算法的并行性和并行计算问题，以提高计算效益；研究其他一些性能更好的编码方式；研究遗传算法中的智能化问题，如智能选择操作算子、自主挖掘领域知识和智能应用领域知识来提高优化性能等。

遗传算法经过选择、交叉和变异的迭代搜索过程，最终收敛于最优状态。选择操作使适应度值高的个体有较高的复制概率，能加快遗传算法的收敛速度；交叉算子通过基因重组产生新的更优个体，寻优搜索过程主要通过它来实现；变异算子通过某些基因位的变异而产生一些有效的基因信息。传统遗传算法的交叉、变异算子只是采用某种特定操作，来完成遗传算法中各代染色体的演化过程。采用一种特定交叉、变异算子的遗传算法对于解决一些问题非常有效，而对解决另外一些问题就无能为力了。

下面通过具体实验来说明各种算子在求解不同优化问题时的性能差异。本部分实验中用到的两个测试函数分别为

函数F₁（X）和函数F₂（X）的优化目标都为最小化目标函数值；函数F₁（X）的可行空间为[–10，10]³，函数F₂（X）的可行空间为[–5.12，5.12]²⁵；在函数F₂（X）中，A表示一个比较大的正数，M表示一正整数。本部分的实验结果如图2.6～图2.8所示。假设采用某算子执行特定操作的总次数为T_total，采用该算子执行特定操作的成功次数为T_succ，则采用该算子执行特定操作的成功率可表示为。

图2.6展示了采用不同交叉算子求解函数F₁（X）和F₂（X）的成功率。本书共采用5种交叉算子（具体信息参见第3.2节）来求解函数F₁（X）和F₂（X）的最优解。从图2.6中可以看出，第一种交叉算子（CR₁）、第三种交叉算子（CR₃）和第四种交叉算子（CR₄）在求解函数F₁（X）时成功率比较高，即这三种交叉算子非常适于求解函数F₁（X）的最优解；第一种交叉算子（CR₁）和第五种交叉算子（CR₅）在求解函数F₂（X）时成功率比较高，即这两种交叉算子非常适于求解函数F₂（X）的最优解。

图2.7展示了采用不同变异算子求解函数F₁（X）和F₂（X）的成功率。本书共采用8种变异算子（具体信息参见第3.2节）来求解函数F₁（X）和F₂（X）的最优解。从图2.7中可以看出，第一种变异算子（MU₁）和第二种变异算子（MU₂）在求解函数F₁（X）时成功率比较高，即这两种变异算子非常适于求解函数F₁（X）的最优解；第一种变异算子（MU₁）、第二种变异算子（MU₂）和第四种变异算子（MU₄）在求解函数F₂（X）时成功率比较高，即这三种变异算子非常适于求解函数F₂（X）的最优解。

图2.8展示了采用不同灾变（局部搜索）算子求解函数F₁（X）和F₂（X）的成功率。本书共采用5种灾变算子（具体信息参见3.2节）来求解函数F₁（X）和F₂（X）的最优解。从图2.8中可以看出，第四种灾变算子（ZB₄）和第五种灾变算子（ZB₅）在求解函数F₁（X）时成功率比较高，即这两种灾变算子非常适于求解函数F₁（X）的最优解；第一种灾变算子（ZB₁）、第四种灾变算子（ZB₄）和第五种灾变算子（ZB₅）在求解函数F₂（X）时成功率比较高，即这三种灾变算子非常适于求解函数F₂（X）的最优解。

根据以上分析，在设计求解函数优化问题的遗传算法时，一方面要保证尽可能地使用成功率较高的操作算子来执行遗传操作，另一方面也要保证操作算子的随机性和多样性。因此可考虑以下两个问题：尽可能将多种操作算子集成到遗传算法中；基于操作算子的成功率来动态地选择需要使用的操作算子。

鉴于此，提出了一种求解函数优化问题的学习型遗传算法^[181]，其特点是融合了多种交叉、变异和灾变算子。求解函数优化问题的学习型遗传算法^[181]的优化框架如图2.9所示，该算法根据算子绩效知识智能地选择交叉、变异和灾变算子，在不影响搜索过程随机性的前提下收敛于全局最优解。学习型遗传算法可表示为

学习型遗传算法（KGA）中的五元体可解释如下：

• SE表示选择操作；
• CR表示交叉操作，CR={CR₁，CR₂，…，CR₅}；
• MU表示变异操作，MU={MU₁，MU₂，…，MU₈}；
• ZB表示灾变操作，ZB={ZB₁，ZB₂，…，ZB₅}；
• FV表示适应度函数评价。

2.3.2　求解非对称旅行商问题的学习型遗传算法框架与流程

近年来，遗传算法从理论到实践都取得了许多重要成果。遗传算法具有良好的全局搜索能力，是解决各种优化问题的最有效方法。遗传算法在旅行商问题上的应用研究，对于构造合适的遗传算法框架、建立有效的遗传操作及有效地解决旅行商问题等方面具有重要意义。

遗传算法具有良好的全局搜索能力，但通常需要较长时间才能收敛到全局最优解^{[182]，[183]}。局部搜索技术在可行空间的某个小区域内能快速地找到局部最优解，但全局搜索能力较弱。同时，一些优化策略（optimization strategy）对于求解复杂组合优化问题非常有效^[184-186]。鉴于此，可考虑将局部搜索技术和优化策略有效地融入遗传算法，以最大限度地提高优化绩效。

为了提高遗传算法的优化绩效，部分学者尝试将一些优化策略融入遗传算法中，取得了比较满意的实验结果^[187-189]。大部分优化策略中包含了实际问题的领域知识，可有效地辅助遗传算法来提高优化绩效。从这种意义上来讲，优化策略可看作是一种知识模型。将知识模型（如优化策略）和智能搜索模型（如遗传算法）结合起来能有效地搜索到优化问题的（准）最优解。将智能优化模型和知识模型有效结合起来的混合优化方法，在求解组合优化问题中的效果已被众多学者多次以实际问题加以验证^[190-192]。

求解非对称旅行商问题的学习型遗传算法^[193]的优化框架如图2.10所示。在该框架中，智能优化模型为遗传算法，知识模型为局部优化操作和动态参数决策模型。根据各种渠道的反馈信息，学习型遗传算法采用交叉和变异机制不断地调整非对称旅行商问题的可行方案。局部优化操作从学习型遗传算法的演化过程中抽取一些较优个体，采用局部优化操作改进后再将改进个体插入到当前种群中。动态参数决策模型从学习型遗传算法的演化过程中抽取一些参数知识，然后应用参数知识来指导改进遗传算法的后续演化过程。学习型遗传算法^[193]采用知识模型和智能优化模型相结合的集成建模思路，以智能优化模型为基础，同时突出知识模型的作用，将智能优化模型和知识模型进行优化组合、优势互补，以提高学习型智能优化方法的效率。

求解非对称旅行商问题的学习型遗传算法^[193]的优化流程如图2.11所示。在每次迭代之前，学习型遗传算法根据参数组合的优化绩效，采用动态参数决策模型为本次迭代随机选择参数组合。与标准遗传算法相似，学习型遗传算法依然包括种群初始化、选择、交叉和变异4个基本操作；与标准遗传算法不同的是，学习型遗传算法在交叉和变异操作中均采用了多次操作取最优的策略。当完成一次迭代后，学习型遗传算法采用种群替换操作和3种局部搜索操作来改进当前种群中部分个体的质量。在遗传算法、动态参数决策模型和局部优化操作的共同作用下，学习型遗传算法在求解非对称旅行商问题时优于其他几种方法。

2.3.3　求解双层CARP优化问题的学习型遗传算法框架与流程

在求解双层CARP优化问题的学习型遗传算法^[194]中，为了提高初始种群质量，采用两种扩展启发式方法来辅助生成初始种群；为了提高遗传操作效率，采用多种算子来实现学习型遗传算法的选择、交叉和变异操作，同时基于算子绩效知识为每次选择、交叉和变异操作选择操作算子；为了进一步提高遗传操作效率，基于构件顺序知识为每次交叉和变异操作选择合适的断点位置；为了保持种群多样性，采用局部替换程序不断地向当前种群中注入新的优秀个体。

求解双层CARP优化问题的学习型遗传算法^[194]的优化框架如图2.12所示。学习型遗传算法采用知识模型和智能优化模型相结合的集成建模思路，以智能优化模型（遗传算法）为基础，同时突出知识模型（构件顺序知识的抽取和应用、算子知识的抽取和应用、经典启发式方法的有效融入）的作用，将智能优化模型和知识模型进行优化组合、优势互补，以提高学习型智能优化方法的效率。

求解双层CARP优化问题的学习型遗传算法^[194]的优化流程如图2.13所示。与标准遗传算法相比，学习型遗传算法具有以下几个显著特点。

• 构件顺序知识的抽取和应用。为了防止当前个体中的优良子序列在交叉或变异操作中被破坏，使用构件顺序知识为交叉或变异操作选择断点位置。如果某弧段序列在已获得准最优解中出现的次数非常多，则应以较小概率在该弧段序列之间选择断点位置；反之，则应以较大概率在该弧段序列之间选择断点位置。
• 算子知识的抽取和应用。基于算子绩效知识为下一步操作动态地选择操作算子，既保证了尽可能使用成功率较高的操作算子来执行遗传操作，又保证了操作算子的随机性和多样性。
• 经典启发式方法的有效融入。为了最大限度地提高优化绩效，将3种经典启发式方法有效地融入学习型遗传算法中。采用启发式方法ERPS（extended random path-scanning）和ERUH（extended random ulusoy's heuristic）来生成一些初始种群，可极大地提高初始种群的质量；采用启发式方法2-Opt来执行变异操作，可极大地提高变异操作的成功率。

2.3.4　求解双层CARP优化问题的学习型蚁群算法框架与流程

将基因型知识表述、知识学习方法和智能优化方法有效地集成起来，可在求解质量和计算时间两个方面极大地提高优化绩效^[18]。将知识模型和智能优化模型有效地结合起来求解组合优化问题，已不再单纯停留在理论概念的层面上，而且在实践中被证明是非常有效的^[190-192]。

求解双层CARP优化问题的学习型蚁群算法的优化框架如图2.14所示。学习型蚁群算法从功能上分为两个模块：智能优化模型（蚁群算法）和知识模型。智能优化模型负责从广阔的可行解空间中搜索并识别出一些准最优解；知识模型从已获得准最优解中学习可用知识，然后采用知识来指导后续优化过程。学习型蚁群算法的优化流程如图2.15所示，其优化过程可概括如下。

• 宏观配置优化。本阶段将确定仓库的最优位置及数目。具体求解过程参见5.2.2节。

• 相关知识的初始化。在本阶段中，记录构件顺序知识、构件聚类知识和算子知识的矩阵被初始化。
• 动态参数调整。根据参数组合的优化绩效为下次迭代随机选择一个参数组合。
• 可行方案的构造。在已有知识的指导下采用蚁群优化机制构建一组可行方案。
• 可行方案的改进。采用2-Opt方法对每次迭代中的最优解进行局部优化。
• 相关知识的更新。采用已获得的准最优解来更新构件顺序知识、构件聚类知识和算子知识。

在求解双层CARP优化问题的学习型蚁群算法^[195]中，为了消除蚁群算法对参数的敏感性，采用动态参数决策模型为每次迭代动态选择参数组合；为了提高蚁群优化效率，基于构件聚类知识和构件顺序知识来构建可行解；为了进一步提高蚁群优化效率，采用2-Opt方法对每次迭代中的最优解进行局部优化。

2.3.5　求解柔性作业车间调度问题的学习型蚁群算法框架与流程

求解柔性作业车间调度问题时，一方面需要考虑机器分配问题，另一方面还要考虑工序调度问题；机器分配问题和工序调度问题的同时考虑，无疑增加了柔性作业车间调度问题的求解难度。同时，在柔性作业车间调度问题中，满足各种约束条件的可行方案数量巨大；很难对这些可行方案进行逐个验证，以获得待求解问题的最优调度；众多可行方案也使得柔性作业车间调度问题成为一类非常具有挑战性的问题。

最新研究表明：将知识表达（knowledge representation）、学习方式（learning methodology）和智能优化方法（intelligent optimization approach）有效结合起来，可在求解质量（solution quality）和计算时间（computational time）上获得极大改进^[18]。可将知识表达和学习方式统一到知识模型中，即知识的表达、获取、存储和应用等操作都由知识模型来完成。将知识模型和智能优化模型结合起来，是求解柔性作业车间调度问题的一种有效方法。

求解柔性作业车间调度问题的学习型蚁群算法^[196]的优化框架如图2.16所示。在该框架中，智能优化模型为蚁群算法，知识模型为局部优化模型、构件知识（构件指派机器知识和构件指派顺序知识）模型和动态参数决策模型。根据各种渠道的反馈信息，学习型蚁群算法通过工序指派、工序排序和调度改进等操作不断地产生一些新的可行方案。局部优化模型从优化过程中抽取一些较优个体，采用调度改进操作将它们改进后再插入到可行方案集中。构件知识模型从优化过程中抽取构件指派机器知识和构件指派顺序知识，然后应用构件知识来指导人工蚂蚁构建可行方案。动态参数决策模型从优化过程中抽取一些参数知识，然后应用参数知识来指导蚁群算法的后续优化过程。求解柔性作业车间调度问题的学习型蚁群算法^[196]采用知识模型和智能优化模型相结合的集成建模思路，以智能优化模型为基础，同时突出知识模型的作用，将智能优化模型和知识模型进行优化组合、优势互补，以提高学习型智能优化方法的效率。

求解柔性作业车间调度问题的学习型蚁群算法^[196]的优化流程如图2.17所示。在每次迭代之前，学习型蚁群算法根据参数组合的优化绩效，采用动态参数模型为本次迭代随机选择参数组合。学习型蚁群算法通过构件知识模型从优化过程中不断地抽取构件知识，然后采用构件知识来指导人工蚂蚁在后续优化过程中构建可行方案。当完成一次迭代后，学习型蚁群算法采用调度改进操作来改进当前可行方案集中的部分个体。在蚁群算法、动态参数决策模型、构件知识模型和局部优化模型的共同作用下，学习型蚁群算法在求解柔性作业车间调度问题时优于其他几种方法。

2.3.6　求解柔性作业车间调度问题的学习型协同进化算法框架与流程

达尔文的进化理论过分强调生存斗争（繁殖过剩所引起的种内斗争），忽略了生物种群之间其他方面的种种联系。大部分现有进化模型都存在着这样的不足：未能很好地反映出整个生物系统复杂的自适应进化过程。生物系统的演化可看作是多个子系统局部相互作用的协同进化过程，生物界就是一种大规模协同动力学系统。在自然界中，不同地域的生物有着不同的特点和进化程度，它们都从自然界中争取资源为己所用；另外，这些生物之间又通过信息交换取长补短、共同进步。学习型协同进化算法就是借鉴自然界中的这一现象设计出来的。整个算法由计算环境中的多个普通种群和一个优良种群构成，各个普通种群进行竞争，从计算环境中得到计算资源；一旦某个种群获得计算资源，它便进行一次自己的进化进程。各个普通种群将进化得到的优良个体贡献出来，组成优良种群；普通种群可从优良种群中获取优良个体，以改善本种群的品质。在学习型协同进化算法中，各个种群均采用不同的优化方法和参数设置来推进各自的进化进程；同时，这些种群又通过相互的资源竞争和信息共享，共同推动着整体算法的演化进程。

求解柔性作业车间调度问题的学习型协同进化算法的基本框架如图2.18所示。在图2.18中，A类遗传算法、B类遗传算法、C类遗传算法和D类遗传算法分别代表4种采用不同参数组合进行演化的遗传算法；A类蚁群算法、B类蚁群算法、C类蚁群算法和D类蚁群算法分别代表4种采用不同参数组合进行优化的蚁群算法。在学习型协同进化算法中，主要通过各种不同的遗传算法和蚁群算法来完成各个普通种群的演化。各种遗传算法（蚁群算法）的不同，可体现在进化机制、优化算子和控制参数等方面的差异。下面将从4个方面来重点说明学习型协同进化算法和传统进化算法的区别。

（1）机制设计。学习型协同进化算法使用多个种群同时推进演化进程，可有效地保证演化过程中种群的多样性，能对求解空间进行更有效的搜索，更倾向于收敛到全局最优解。学习型协同进化算法借鉴生态学中的种群协同理论，将种群间自动调节和自适应调整的思想充分应用于算法设计中。根据生态学对种群相互关系的划分，一般有以下关系：捕食者与被捕食者、寄生物与寄主、竞争和互惠共生，这些关系可概括为两种协同进化模型，即竞争协同模型和合作协同模型。最新研究成果表明：采用生态模型和协同进化结构来扩展进化算法是一种非常有效的方法。协同进化可分为竞争协同进化和合作协同进化，前者通过演化使得个体更有竞争力，后者通过演化寻找最佳个体使得系统构造得更好。许多研究表明：竞争协同导致“军备竞赛”，多个种群通过交互机制有效地提高了系统性能。鉴于此，基于竞争协同模型提出了一种学习型协同进化算法。

（2）问题表示。在进化算法中，一般采用二进制编码或实数编码来表示种群中的个体。种群结构是进化算法演化的基础，种群规模直接影响着进化算法的优化绩效。为了获得较好的演化性能，一般需要采用较大的种群规模。随着种群规模的增大，计算量按多项式增长，而算法性能却并不同比例增长。Ficici等认为：种群结构在协同进化算法中起着非常重要的作用^[197]。Kim等提出基于主种群和寄生种群的协同进化算法，分别采用了邻近演化、联赛竞争和局部杰出者等组合策略^[198]。曹先彬等构造了基于生态种群竞争模型的新协同进化模式^[199]。为了提高学习型协同进化算法的优化性能，本书采用多种群表示方法来维持演化过程中种群的多样性。

（3）演化操作。在Potter的协同进化模型中，多个遗传算法程序并行运行；通过组合多个程序所获得的局部解而构成协同进化算法的全局解^[200]。He等提出了设计混合变异策略的博弈论方法，实验表明该方法是有效的^[201]。Ficici等在协同进化算法中，利用演化博弈论来研究选择方法的动态均衡^[202]。本书通过集成现有算法中的几种优势操作算子，利用混合策略思想结合具体问题设计学习型协同进化算法，来提高优化性能。

（4）算法实现。1997年，Potter给出了一个通用的合作协同进化算法框架；以一般进化算法框架为基础，将种群分为若干子种群，进一步考虑子种群之间基于合作关系的协同进化^[203]。在Potter提出的合作协同进化框架的基础上，本书构建了学习型协同进化算法的基本框架。学习型协同进化算法采用多种群协同优化方法来不断演化当前种群。多种群优化方法通过各个种群之间的相互竞争和良种共享来提高算法的优化效率。

求解柔性作业车间调度问题的学习型协同进化算法^[204]的优化框架如图2.19所示。在学习型协同进化算法中，用到了三类知识：精英个体知识，将普通种群中的一些精英个体共享到优良种群中，通过良种更新和良种迁移策略来实现普通种群和优良种群之间的交互；构件知识，从优良种群中抽取构件指派机器知识和构件指派顺序知识，应用构件指派机器知识和构件指派顺序知识来指导人工蚂蚁构建可行方案；参数知识，采用不同优化方法和参数配置来实现各个普通种群的演化，以较高概率给竞争力指数高的种群赋予计算资源。学习型协同进化算法^[204]采用知识模型和智能优化模型相结合的集成建模思路，以智能优化模型为基础，同时突出知识模型的作用，将智能优化模型和知识模型进行优化组合、优势互补，以提高学习型智能优化方法的效率。

2.3.7　求解体系仿真优化问题的学习型遗传算法框架与流程

在使用计算机仿真技术研究体系的过程中，仿真模型仅是对问题的直观描述，仿真运行只能提供一定条件下的可行方案，并不能给出体系的最优解。需要将优化技术嵌入到仿真过程中，以便在仿真环境下使输出响应不断地得到改进，从而实现体系性能的优化。仿真优化就是指非枚举地从可能值中找到最佳输入变量值，使得输出结果为满意解或最优解的过程。仿真优化研究基于仿真的目标优化问题，即基于模型仿真给出的输入输出关系通过优化算法得到最佳输入量。仿真优化的目标是在仿真试验中获得最多信息的同时，耗费资源最少，使用户更加容易地进行决策。仿真优化的难点如下：存在不确定因素，单次仿真仅给出对应某输入的一次性能估计，通常存在误差；系统仿真过程较费时，且缺少与优化模块的合理接口，使得整个优化过程很慢；输入变量空间大，且连续量、离散量和逻辑量共存，优化涉及多目标，并存在多极小，以致难以高效地实现全局优化。鉴于仿真优化的工程背景和上述难点，它一直是不同领域理论和工程人员共同关注的重要课题。

仿真优化效率在很大程度上依赖于优化过程中所采用的搜索技术。现有搜索算法在一定程度上把待求解问题的领域知识隐含地加入算法，并没有大量直接地挖掘、存储和应用待求解问题的相关领域知识，还不能最有效地得到优化问题满意解。鉴于此，提出了一种求解体系仿真优化问题的学习型遗传算法^[205]。该方法试图通过较少次数的体系仿真，使得待研究体系的输出结果为满意解或最优解，学习型遗传算法的优化框架如图2.20所示。

在求解体系仿真优化问题的学习型遗传算法^[205]中，主要用到了两类知识：精英个体知识，从当前种群中选取若干精英个体，然后采用灵敏度分析方法从这些精英个体中挖掘各变量对输出结果的敏感程度；构件知识，从已获得的精英个体中挖掘变量灵敏度知识，基于变量灵敏度知识来指导学习型遗传算法的后续演化。求解体系仿真优化问题的学习型遗传算法^[205]采用知识模型和智能优化模型相结合的集成建模思路，以智能优化模型为基础，同时突出知识模型的作用，将智能优化模型和知识模型进行优化组合、优势互补，以提高学习型智能优化方法的效率。

在求解体系仿真优化问题的学习型遗传算法^[205]中，首先采用量化正交遗传算法在整个可行域内快速地搜索出一些较优解（方案）；然后应用灵敏度分析方法对已评估方案进行分析，得到待研究体系各输入变量的灵敏度知识；接下来应用变量灵敏度知识来指导量化正交遗传算法继续在可行域内搜索最优解；通过这样的多次迭代，在经过较少次数的体系仿真后，得到待研究体系的最优解。

2.3.8　求解卫星地面站系统任务调度的学习型蚁群算法框架与流程

卫星地面站系统任务调度问题是一个基于约束的资源优化问题，即在给定时间内向需要执行的任务分配地面站及执行时间。该问题的优化目标可描述为：在给定时间内完成最多的任务或最大化完成任务的权重值之和（考虑任务权重时）。该问题的难点在于：资源（地面站）相对于某个特定活动（任务）来讲，只有一个或几个可用时间窗口（卫星和地面站之间满足任务要求的时间区段）；其调度过程既包括了资源指派问题，又包含了时间窗口的分配问题。

各国学者通常采用人工智能方法来求解卫星地面站系统任务调度问题，如贪婪算法^[206]、动态规划方法^[207]、启发式搜索方法^[208]和约束满足方法^[209]等。如何更加快速有效地求解该问题，依然是摆在人们面前的一个严峻挑战。本书提出了一种有效求解该问题的基于蚁群优化（ant colony optimization）^[210]和导向局部搜索（guided local search）^[211]的学习型蚁群算法。

求解卫星地面站系统任务调度的学习型蚁群算法^[212]的优化框架如图2.21所示。该算法主要用到了精英个体知识，即从蚁群算法的优化过程中选取精英个体，然后采用导向局部搜索对该精英个体进行改进，最后采用改进的精英个体来更新蚁群算法中的信息素水平。求解卫星地面站系统任务调度的学习型蚁群算法^[212]采用知识模型和智能优化模型相结合的集成建模思路，以智能优化模型为基础，同时突出知识模型的作用，将智能优化模型和知识模型进行优化组合、优势互补，以提高学习型智能优化方法的效率。

在蚁群算法中，人工蚂蚁按照状态转移规则逐步构造可行解，将一些随机性引入优化结果中。因此，通过蚁群优化算法很难快速得到优化问题的全局最优解。如果要快速得到优化问题的全局最优解，则需要采用局部搜索技术来辅助蚁群优化过程。本书将蚁群算法和局部搜索方法有效集成起来，提出了求解卫星地面站系统任务调度的学习型蚁群算法^[212]，学习型蚁群算法的优化流程如图2.22所示。

2.3.9　求解多星任务规划问题的学习型蚁群算法框架与流程

成像卫星是利用星载遥感器从太空中获取地面图像信息的对地观测卫星，具有覆盖范围广、运行时间长、不受国界和空域限制、无须考虑人员安全等独特优势。成像卫星主要分为光学成像卫星和雷达（微波）成像卫星两大类，光学成像卫星采用可见光、红外、多光谱相机成像，而雷达成像卫星采用SAR遥感器进行成像。可见光成像卫星具有空间分辨率高等优点，但不能全天候、全天时工作；雷达成像卫星不受白天、黑夜及云雾的影响，具有一定的穿透能力。目前，成像卫星在灾害防治、环境保护、城市规划及农业、气象等许多领域都发挥了重要作用，也得到了世界各国的高度重视。

在成像卫星技术发展之初，由于卫星载荷能力有限，用户任务也相对较少，任务的成像时间和成像角度都相对固定，卫星管理控制比较简单，任务规划问题也不突出。随着成像卫星技术的发展和地面影像数据需求的增加，卫星开始需要调整遥感设备的侧视角度选择地面目标进行成像，在安排成像过程中必须考虑多种成像约束以保证卫星安全可靠的运行和成像计划的顺利实施。成像卫星高速运行于近地轨道，对地面实施成像受到卫星同目标的可见时间窗限制；卫星成像设备在一定时间内姿态调整的能力有限，在成像任务之间进行动作转换需要满足多种约束条件。一般而言，不能对一次任务规划时间范围内所有的任务请求进行成像，卫星每次执行的任务是任务数据集合的一个子集，不能满足用户提出的所有任务请求。

为了缓解这种供求矛盾，越来越多的成像卫星出现在空间中执行对地观测的任务。但是尽管在轨运行的卫星数量不断增加，相对于迅速增长的影像数据需求，有限的成像卫星资源仍然显得异常宝贵。为了充分利用成像卫星资源，需要针对用户成像需求，对多颗成像卫星进行统一管理，均衡考虑各种因素，传统的手工或简单推理计算已不能满足卫星日常管理和指挥控制的需求，必须借助于先进的优化方法和工具才能较好管理和分配卫星资源，以最大化满足用户日益增长的成像需求。

求解多星任务规划问题时，需要解决以下两个问题：一是卫星资源分配问题，即从多颗卫星的多个遥感器资源中指派一个遥感器去响应用户的成像需求；二是观测任务合成问题，在给定时段安排到某遥感器的观测任务可能有多个，需要采用任务合成手段来确定该遥感器在给定时段去观测哪些目标。卫星资源分配问题和观测任务合成问题的同时考虑，无疑增加了多星任务规划问题的求解难度。同时，在多星任务规划问题中，满足各种约束条件的可行方案数量巨大，很难对这些可行方案进行逐个验证，以获得待求解问题的最优规划方案；众多可行方案也使得多星任务规划问题成为一类非常具有挑战性的问题。

求解多星任务规划问题的学习型蚁群算法的优化框架如图2.23所示。在该框架中，智能优化模型为蚁群算法，知识模型为构件知识模型和动态参数决策模型。根据各种渠道的反馈信息，学习型蚁群算法通过任务指派、任务合成和调度改进等操作不断地产生一些新的可行方案。构件知识模型从优化过程中抽取构件指派机器知识和构件聚类知识，然后应用构件知识来指导人工蚂蚁构建可行方案。动态参数决策模型从优化过程中抽取一些参数知识，然后应用参数知识来指导蚁群算法的后续优化过程。求解多星任务规划问题的学习型蚁群算法采用知识模型和智能优化模型相结合的集成建模思路，以智能优化模型为基础，同时突出知识模型的作用，将智能优化模型和知识模型进行优化组合、优势互补，以提高学习型智能优化方法的效率。

求解多星任务规划问题的学习型蚁群算法的优化流程如图2.24所示。在每次迭代之前，学习型蚁群算法根据参数组合的优化绩效，采用动态参数模型为本次迭代随机选择参数组合。学习型蚁群算法通过构件知识模型从优化过程中不断地抽取构件知识，然后采用构件知识来指导人工蚂蚁在后续优化过程中构建可行方案。当完成一次迭代后，学习型蚁群算法采用邻域调整操作来改进当前可行方案集中的部分个体。在蚁群算法、动态参数决策模型和构件知识模型的共同作用下，学习型蚁群算法在求解多星任务规划问题时优于其他两种方法。