智能优化技术 课件汇 黄思翰 第5-7讲- 禁忌搜索算法 -NSGA系列算法

禁忌搜索算法目录一、算法概述二、算法分析及改进三、工程案例分析四、基于Python的编程实践目录一、算法概述二、算法分析及改进三、工程案例分析四、基于Python的编程实践禁忌搜索算法概述Glover提出禁忌搜索的概念随着禁忌搜索的第一本专著出版，禁忌搜索的研究达到了一个高峰禁忌搜索得到了广泛的应用，包括工程优化、网络设计、生产调度等。Glover与Laguna合著的第一本禁忌搜索专著正式出版，标志着禁忌搜索的相关研究日趋完善

19902000s19861997Glover1这也是一个局部最优，设置标记禁忌搜索算法理论基础这里是一个局部最优，设置一标记，免得重新来到这里AAB图中，登山者找到不同的山峰后，有意识地避开它们，从而获得更大的搜索区间，经过不断的”禁忌”和“解禁”，能找到最高的山峰C。C2禁忌表中保存了最近若干次迭代过程中的移动(移动:产生领域解的变化)，凡是处于禁忌表中的移动，不能再进入当前过程的迭代，这样可以避免算法重复访问已经访问过的解，扩大搜索区间，帮助算法摆脱局部最优解。为了尽可能不错产生最优解的“移动”，禁忌搜索采用“特赦准则”的策略，将禁忌对象“解禁”。禁忌搜索算法理论基础从一个初始可行解出发选择一系列的特定搜索方向采用禁忌表记录已经优化的部分特殊情况也可以解禁34禁忌搜索算法的新解不是在当前解的邻域中随机产生，它要么是优于“bestsofar”的解，要么是非禁忌的最佳解，因此选取优良解的概率远远大于其他劣质解的概率。取到优良解的概率大禁忌搜索算法具有记忆功能和藐视准则，并且在搜索过程中可以接受劣质解，所以具有较强的“爬山”能力，搜索时能够跳出局部最优解，转向解空间的其他区域，局部开发能力强，收敛速度很快。局部开发能力强禁忌搜索算法理论基础禁忌搜索算法的基本特点目录一、算法概述二、算法分析及改进三、工程案例分析四、基于Python的编程实践5禁忌搜索算法流程【步骤1】初始化【步骤2】终止条件判断【步骤3】生成候选解给定禁忌搜索算法参数，随机产生初始解，置空禁忌表。判断算法终止条件是否满足：若是，结束算法并输出优化结果；若否，则继续以下步骤。利用初始解的邻域函数产生其所有（或若干）邻域解，并从中确定若干候选解。6禁忌搜索算法流程【步骤4】对候选解判断是否满足藐视准则【步骤5】判断候选解中各对象的禁忌属性【步骤6】判断算法终止条件是否满足若满足终止条件，结束算法并输出优化结果。将满足藐视准则的最佳状态作为当前解，更新禁忌表，更新“bestsofar”状态。候选解中非禁忌对象对应的最佳状态作为新的当前解，同时将其放入禁忌表，更新禁忌表。7禁忌搜索算法概念详解相关术语术语表征初始解(Initialsolution)是优化问题的一个可行解，可以随机生成，也可以根据问题特点采用启发式方法生成。禁忌表(Tabulist)用来记录解前几次移动的表格，禁止这些移动在近期内返回。禁忌长度(Tabulength)是指禁忌对象在不考虑藐视准则的情况下不允许被选取的最大次数，相当于禁忌对象在禁忌表中的任期。终止准则(Terminationcriterion)结束算法的搜索进程的准则。适配值函数(Fitfunction)表示个体的优劣性，适配值函数的设定因问题而异。邻域(Neighborhood)是指当前解通过某种变化产生其他解，这些解的集合称为邻域。藐视准则(aspirationcriterion)将某些状态解禁的准则，以实现更高效的优化性能。8禁忌搜索算法概念详解

目标函数及约束9基于此数值案例剖析禁忌搜索算法，对其编解码方式、适配值值计算、初始化参数、邻域结构、禁忌表、藐视准则等具体流程深入讲解。求解下述二元函数的最大值禁忌搜索算法概念详解

10

编码编码是将问题的解决方案表征为具有一定特征的结构数据串。由于二进制编码方式表征形式简洁，生成方式简单，故本案例采用二进制编码方式。禁忌搜索算法概念详解11初始化参数禁忌长度

禁忌搜索算法的最大迭代次数T通常T的取值范围为100~500，其与算法的运行时间正相关。禁忌搜索算法概念详解禁忌长度是禁忌表中禁忌对象被禁忌的次数，禁忌长度可以是一个常数，也可以动态变化。初始解生成禁忌搜索算法的初始解可以随机给出，也可以事先使用其他启发式算法等给出，初始解的好坏对搜索的性能影响很大。当遇到一些带有复杂约束的优化问题时，可以针对特定的复杂约束，采用启发式方法或其他方法找出一个可行解作为初始解，再用禁忌搜索算法求解，以提高搜索的质量和效率。禁忌搜索算法概念详解

11适配值函数禁忌搜索算法概念详解适配值（适应度值）函数用于对搜索进行评价。目标函数及其变形都可以作为适配值函数。12本案例的适配值函数就是目标函数13邻域结构生成邻域结构是指一个解（当前解）通过“移动”产生另一个解（新解）的途径，是保证搜索产生优良解和影响算法搜索速度的重要因素之一。邻域的设计方法很多，包括：互换、插值、逆序等。不同的“移动”方式将导致邻域解个数及其变化情况的不同，对搜索质量和效率有一定影响。本案例邻域结构生成方法如上图所示。随机选择第5位，则产生的新邻域为：第4、5、6位上的基因发生突变。禁忌搜索算法概念详解当前解14禁忌表和禁忌长度从数据结构上讲，禁忌表是具有一定长度的先进先出的队列。禁忌长度是禁忌表中禁忌对象被禁忌的次数，禁忌长度可以是一个常数，也可以动态变化。禁忌搜索算法概念详解之后5次迭代中，邻域解不再由第5位生成记忆方式明晰记忆：表中记录的是一个完整的解，消耗内存属性记忆：记录当前解的移动信息

123456789105禁忌表出队位置进队位置后面元素准备集体前移队尾队头

1010011001本案例禁忌过程如右图所示，禁忌长度设为常数5邻域解由第5位产生将编码中第五个位置加入禁忌表邻域解中较优的解被禁忌15禁忌表和禁忌长度禁忌搜索算法概念详解藐视准则禁忌搜索算法中，可能会出现候选解全部被禁忌，或者存在一个优于“bestsofar”状态的禁忌候选解，此时藐视准则将某些状态解禁，以实现更高效的优化性能。基于适配值原则基于搜索方向原则基于最小错误原则基于影响力原则该准则可直观理解为算法搜索到了一个更好的解。该准则可直观理解为算法正按有效的搜索途径进行。该准则可直观理解为对算法死锁的简单处理。搜索过程中不同对象的变化对适配值的影响都不同，将这种影响力作为一种属性与禁忌长度和适配值来共同构造藐视准则。禁忌搜索算法概念详解1617本案例采用基于适配值的原则，当算法进行到某一迭代次数，邻域中所有解都被禁，但存在适配值优于目前最优解的邻域解，此时可以藐视禁忌，解禁该邻域解。藐视准则禁忌搜索算法概念详解18终止准则禁忌搜索算法需要一个终止准则来结束算法的搜索进程。主要有以下3种方法：给定最大迭代步数当禁忌搜索算法运行到指定的迭代步数之后，则终止搜索。设定最大禁忌频率若某个状态、适配值或对换等对象的禁忌频率超过某一阈值，或最佳适配值连续若干步保持不变，则算法终止。设定适配值的偏离阈值首先估计问题的下界，一旦算法中最佳适配值与下界的偏离值小于某规定阈值，则终止搜索。本案例采用给定最大迭代步数的方法来终止搜索。禁忌搜索算法概念详解19取一个好的初始解禁忌表中加入移动方向的信息好的初始解可使禁忌搜索算法在解空间中搜索到好的解，而较差的初始解则会降低禁忌搜索的收敛速度。因此可以与遗传算法、模拟退火算法等优化算法结合，先产生较好的初始解，再用禁忌搜索算法进行搜索优化。a是禁忌值；b代表优质解的出现次数，即此项有b次反位或交换是优于当前解的评估值的；c代表劣质解出现的次数，即此项有c次反位或交换是劣于当前解的评估值的。b越大，c越小说明此项的反位或交换越有可能有利于搜索更优解。禁忌搜索是著名的启发式搜索算法，但是禁忌搜索也有不足，可以在以下几个方面进行改进：禁忌搜索算法改进目录一、算法概述二、算法分析及改进三、工程案例分析四、基于Python的编程实践20工程案例分析可重构制造系统调度问题面向具有多品种、小批量特点的产品订单，在一个基于可重构机床的制造系统中如何合理的组织现有的制造资源，进行快速高效的产品生产是制造企业需要解决的关键问题。具体来说，该制造系统由多台可重构机床组成。每台可重构机床具有多种构型，每种构型对应一种产品特征（工序）的加工。对于一台可重构机床来说，不同构型之间的转化需要一定的设置时间和成本。此外，订单由多种类型的产品组成，每种产品的加工数量也各不相同。一种产品包含多个特征（工序），特征的加工存在固定的先后顺序。21工程案例分析可重构制造系统调度问题问题假设：针对每台可重构机床切换不不同构型时的设置时间及成本是固定相同的。可重构机床加工期间针对某一产品特征加工时间固定不考虑其运行故障。一台可重构机床的一种构型至多对应一种产品的一个特征的加工，即不考虑一种可重构机床的构型可以生产一种产品的多个特征的加工的情况。每种产品类型的同一产品特征必须在一台可重构机床上连续生产，不允许间断及生产任务拆分。在零时刻所有可重构机床均可用，所有产品均可以被加工。22工程案例建模符号说明：索引常量符号含义i,j产品类型索引(i,j=(1,2,…,P))k,lm可重构机床索引(m=(1,2,…,M))c23工程案例建模常量符号说明：常量符号含义产品

i

的特征总数量可重构机床m的构型总数量产品i的加工数量产品i

的第k个特征在可重构机床m上的加工时间可重构机床m的构型切换时间产品i

的第k个特征能采用可重构机床m的第c个构型加工则为1，否则为0如果在可重构机床m上产品i

的第k个特征的加工构型与产品j

的第l个特征的加工构型不同则为1，否则为0足够大的数24工程案例建模符号说明：决策变量与辅助变量常量符号含义产品i

的第k

个特征的生产开始时间产品i

的第k

个特征的生产完成时间产品i

的最终生产完成时间如果产品i

的第

k个特征选择可重构机床m进行加工则为1，否则为0如果在可重构机床

m上产品i

的第

k个特征加工完成后紧接加工产品

j

的第

l个特征则为1，否则为025工程案例建模优化目标：Makespan

模型约束：1）产品特征加工时间约束26工程案例建模模型约束：2）产品前后特征的加工时间约束模型约束：3）产品完工时间约束模型约束：4）可重构机床上时间占用约束模型约束：5）构型加工约束27工程案例建模模型约束：6）可重构机床的一种构型至多对应一种产品的一个特征的加工模型约束：7）对于任意的一个产品特征必须被某一个可重构机床进行加工模型约束：8）可重构机床上一个特征加工至多只有一个紧前、紧后加工特征模型约束：9）定义变量的取值范围28基于禁忌搜索算法的案例求解禁忌搜索算法应用分析使用禁忌搜索算法求解可重构制造系统调度问题，需要重点解决以下2个问题：如何根据该可重构制造系统调度问题设计合理可行的编解码方案？邻域结构、禁忌表、藐视准则如何具体执行？29产品特征的加工顺序子决策问题:基于可重构制造系统调度的问题特征，我们需要进行两个子决策问题的求解：

在满足同一产品前后加工特征的顺序约束的基础上，我们需要考虑在可供选择的可重构机床上先生产哪一产品特征，以及后生产哪一产品特征。不同的产品特征生产顺序会影响最终调度方案的整体完工时间。加工产品特征的可重构机床配置子决策问题:

在满足同一时刻一台可重构机床至多只能用于一项产品特征加工的约束基础上，我们需要考虑针对不同产品的不同特征选择哪一可重构机床进行加工。不同的可重构机床配置方案会影响可重构机床的加工进程，进而影响最终调度方案的整体完工时间。编码基于禁忌搜索算法的案例求解30基于禁忌搜索算法的案例求解编码考虑到以上两个子决策问题的解决，针对本数值案例，我们设计了如下双层编码形式。

第一行代表产品特征的加工顺序，其中各编码位为产品序号。同一产品序号的出现次数表示该产品的加工特征数。第二行代表产品特征选用的可重构机床序号。如图，第一行的第一个1代表产品1的第1个特征，第2个1代表产品1的第2个特征，以此类推。第二行的第一个编码位的1代表产品1的特征1由可重构机床1进行加工，以此类推。31在设计完成解码方式后，针对一个编码方案我们需要对其进行评价，以表征编码方案的优劣。因此，此步的设计与数学模型中的目标函数密切相关。即根据具体的编码方案，计算得出与之对应的目标函数值。注：在算法的具体编程实现时，我们不必拘泥于形式化的表达方式，即选用适配值函数形式是多样的，但要保证适配值的最佳性与目标函数的最优性一致。解码、计算目标函数值在禁忌搜索算法中，采用适配值值函数（Fitness）表征目标函数值(f(x))，即在一般化的禁忌搜索算法范式中，适配值越优，表明当前个体越优。即针对极大化目标函数模型时Fitness=f(x)。而针对本问题的最小化目标函数模型时Fitness=-f(x)即可。基于禁忌搜索算法的案例求解32基于禁忌搜索算法的案例求解初始化针对该工程案例，本节采用最为基础的随机生成方式进行初始解。针对第一层编码，假设针对一个产品1、2、3、4其各自所对应的特征总数为：3、3、4、2。我们只需要打乱其顺序即可获得不同的产品特征层编码。然后依照确定的第一行编码，从前向后逐个为产品特征随机选取进行加工的可重构机床，进而获得第二行机床配置层的编码。33基于禁忌搜索算法的案例求解邻域的生成本工程案例的邻域解产生方式为：交换。即在编码索引0-11中，随机确定一位索引，定位到当前解的第一层和第二层编码上，然后进行交换产生邻域解。在本案例中，邻域解数量较少，故邻域集合中的所有解都作为与候选解。邻域结构是指一个当前解通过“移动”产生另一个解（新解）的途径，是保证搜索产生优良解和影响算法搜索速度的重要因素之一。编码进行交换的方式由产生的随机数a来决定，有以下三种情况：34基于禁忌搜索算法的案例求解邻域的生成 0<

a

<11

第一个邻域解：第a位同前一位（a-1位）进行交换；第二个邻域解：第a位同后一位（a+1位）进行

交换；第三个邻域解：第a-1位同第a+1位进行交换。35基于禁忌搜索算法的案例求解邻域的生成

a=0

第一个邻域解：第0位同第1位进行交换；第二个邻域解：第0位同第11位进行交换；第三个邻域解：第 1位同第11位进行交换。36基于禁忌搜索算法的案例求解邻域的生成

a

=11

第一个邻域解：第10位同第11位进行交换；第二个邻域解：第0位同第11位进行交换；第三个邻域解：

第0位同第10位进行交换。基于禁忌搜索算法的案例求解非法解的合法化3738基于禁忌搜索算法的案例求解禁忌表每次产生邻域解后，我们计算邻域解集中每一个解的适应度函数值，并将其中适应度函数最优的解作为禁忌对象。在本案例中，禁忌表记录的是每次生成邻域解时在0-11中随机产生的数字，禁忌长度设置为12，禁忌表如上图所示。在迭代固定次数（也就是禁忌长度）后，禁忌表释放这些移动，重新参加运算，因此，禁忌表是一个循环表。每迭代一次，就将禁忌对象对应的禁忌长度减小1，当长度减为0时，该禁忌对象就从禁忌表中释放出来。目录一、算法概述二、算法分析及改进三、工程案例分析四、基于Python的编程实践39工程实例产品类型产品数量特征数量1A20032B50033C10044D3002针对如下所示的具体实例数据进行禁忌搜索算法的编写。生产订单信息可重构机床构型数转换时间转换成本1A38003502B56003003C31000500可重构机床信息40工程实例产品特征可重构机床1可重构机床2可重构机床3F(1,1)1-2F(1,2)-41F(1,3)213F(2,1)23-F(2,2)3-1F(2,3)11-F(3,1)-52F(3,2)2-1F(3,3)143F(3,4)33-F(4,1)143F(4,2)322产品特征对应机床构型表41工程实例产品特征可重构机床1可重构机床2可重构机床3F(1,1)5-8F(1,2)-1012F(1,3)679F(2,1)1319-F(2,2)10-5F(2,3)812-F(3,1)-49F(3,2)6-1F(3,3)3710F(3,4)93-F(4,1)594F(4,2)836产品特征加工时间（Min）42参数设置算法参数设定值种群大小1迭代次数200禁忌长度12机床更新概率0.343工程求解主函数导入依赖包输入初始化数据执行算法并作甘特图首先进行工程案例数据输入。然后，创建工程问题类FJSP_RMT，创建禁忌搜索算法类TS。最后，根据算法运行结果画出迭代图和最优解甘特图。Main文件44FJSP工程类问题代码FJSP_RMT类的初始化导入依赖包45FJSP_RMT类的初始化FJSP工程类问题代码FJSP_RMT类下的方法：检查机床编码是否合法、甘特图坐标轴、初始化个体和种群然后根据可选机床随机确定加工机床将初始状态随机打乱46FJSP工程类问题代码FJSP_RMT类下的方法---计算目标函数值：makespan根据当前解计算其所对应的实际运行方案，然后获取其所对应的Makespan。47FJSP工程类问题代码FJSP_RMT类下的方法---画甘特图根据当前对应的实际运行方案，画出其所对应的甘特图。48禁忌搜索算法主代码先将禁忌搜索算法类的参数初始化，接着进入算法的流程：产生初始解、计算初始解适配值（解码）、置空禁忌表…禁忌搜索算法类TS类初始化禁忌搜索算法流程导入依赖包49禁忌搜索算法主代码迭代循环主程序选出适配函数值最好的，判断是否满足藐视准则，并更新禁忌表，记录更新后的当前解，查找迭代到目前的最小完工时间，记录“bestsofar”的索引。50根据当前解，产生邻域解。这种方法每次生成三个邻域解，数量较少，这时候候选解也就是邻域解集中的所有解。0<a<11的情况禁忌搜索算法主代码TS类下，生成邻域的方法51a=0的情况a=11的情况禁忌搜索算法主代码52更新禁忌长度，判断是否满足藐视准则，判断候选解对应的各对象的禁忌属性禁忌搜索算法主代码TS类下，更新禁忌表的方法53禁忌搜索算法主代码TS类下，计算邻域解中所有解适配值的方法54实例验证主讲教师：黄思翰本节结束粒子群算法目录一、算法概述二、算法分析及改进三、工程案例分析四、基于Python的编程实践目录一、算法概述二、算法分析及改进三、工程案例分析四、基于Python的编程实践粒子群算法发展历程粒子群算法的诞生Shi等引入了惯性权重的概念Baskar等提出多群粒子协同PSO算法，使用多群粒子分别优化问题的不同维Higashi等引入变异算子跳出局部极值点的吸引1998200419952003Kennedy和Eberhart发表题为“ParticleSwarmOptimization”的论文粒子群算法在深度学习领域的应用逐渐增多，用于调优神经网络的超参数，优化模型结构等。Coello和Lechuga首次将粒子群算法扩展应用于多目标优化问题201020071粒子群算法理论基础2粒子群算法,又称微粒群算法，属于群智能算法的一种，源于对鸟群捕食行为的研究，基本思想是通过群体中个体之间的协作和信息共享来寻找最优解。由Kennedy和Eberhart等于1995年提出，最初是受到飞鸟集群活动的规律性启发，进而利用群体智能建立的一个简化模型。粒子群算法的信息共享机制可以解释为一种共生合作的行为，每个粒子的搜索行为在不同程度上受到群体中其他个体的影响，同时其搜索行为在受其他个体影响的同时还受到自身经验的引导。鸟群捕食3粒子群算法理论基础粒子群探索解空间粒子群算法受鸟类捕食行为的启发并对这种行为进行模仿，将优化问题的搜索空间类比于鸟类的飞行空间，将每只鸟抽象为一个粒子以表征问题的一个可行解，优化问题所要搜索到的最优解则等同于鸟类寻找的食物源。粒子群算法为每个粒子制定了与鸟类运动类似的简单行为规则，使整个粒子群的运动表现出与鸟类捕食相似的特性，从而可以求解复杂的优化问题鸟类搜索食物个体最优结果个体最优的影响群体最优结果群体最优的影响个体上次前进方向自身惯性影响个体最终的前进方向4粒子群算法理论基础鸟群觅食粒子群算法鸟群搜索空间的一组有效解（粒子群）；觅食空间问题的搜索空间；飞行速度解的速度向量；所在位置解的位置向量；个体认知和群体协作每个粒子根据自身历史最优位置和群体的全局最优位置更新速度和位置；找到食物算法结束，输出全局最优；鸟群觅食现象和粒子群优化算法的基本定义对照粒子群算法理论基础5粒子群算法的四个基本特点粒子群算法是基于群智能理论的优化算法，通过群体中粒子间的合作与竞争产生的群体智能指导优化搜索。与其他算法相比，粒子群算法是一种高效的并行搜索算法粒子群算法根据自己的速度和基于种群的全局搜索策略，采用的速度-位移模型进行一定的随机搜索，使用适应值来评价个体的优劣程度。操作相对简单。粒子在算法结束时仍保持其个体极值，即粒子群算法除了可以找到问题的最优解外，还会得到若干较好的次优解，因此将粒子群算法用于调度和决策问题可以给出多和有意义的方案。粒子群算法特有的记忆使其可以动态地跟踪当前搜索情况并调整其搜索策略。粒子群算法对种群的大小不敏感，即使种群数目下降时，性能下降也不是很大。合作与竞争操作简单同时生成次优解规模不敏感目录一、算法概述二、算法分析及改进三、工程案例分析四、基于Python的编程实践6粒子群算法流程【步骤1】初始化初始化所有的粒子的速度和位置。【步骤2】适应度计算在每一代的进化中，计算各个粒子的适应度函数值。【步骤3】个体最优计算如果该粒子当前的适应度函数值比其历史最优值要好，那么历史最优将会被当前位置所替代。【步骤4】全局最优计算如果该粒子的历史最优比全局最优要好，那么全局最优将会被该粒子的历史最优所替代。【步骤5】粒子更新基于速度更新公式和位置更新公式更新粒子的速度和位置。【步骤6】终止条件判断如果还没有到达结束条件，转到步骤二，否则停止并结束。7粒子群算法概念详解算法术语表征种群规模(Populationsize)粒子种群个体的数量。初始解(Initialsolution)是优化问题的一个可行解，可以随机生成，也可以根据问题特点采用启发式方法生成。适应度值函数(Fitfunction)用于对搜索进行评价。惯性因子(Inertiafactor)是标准粒子群算法中非常重要的控制，可以用来控制算法的开发和探索能力。学习因子(Learningfactor)调节向个体最优和全局最优方向飞行的步长，决定粒子个体经验和群体经验对粒子运行轨迹的影响。个体最优(Personaloptimization)是粒子的历史最优位置。全局最优(Globaloptimization)所有粒子的历史最优位置。粒子群算法的基本术语8粒子群算法概念详解

由此，粒子群算法的表征模型可以表示为如下的7元组：C：个体编码方法;（Coding）I0：初始解;

（Initialsolution）P：个体最优;

（Personaloptimization）T：算法终止条件;

（Termination）F：个体适应度评价函数;

（Fitfunction）G1：速度和位置更新方法;（GenerationUpdating）G2：全局最优;

（Globaloptimization）9粒子群算法概念详解数值案例简介求解下述二元二次函数的最大值:

基于此数值案例对粒子群算法的具体流程进行深度讲解。解析其中编码、速度更新、位置更新、个体最优更新、全局最优更新等过程。10粒子群算法概念详解编码与解码问题分析实际问题解决方案结构数据串算法执行问题求解算法编码算法解码输入输出编码:即将问题的解决方案表征为具有一定特征的结构数据串。解码:是将结构化的数据串转化为解决方案的过程，即编码的逆运算。常见的编码形式包括：二进制编码、实数编码等。

11粒子群算法概念详解编码与解码—二进制编码

特点：解码简单，粒子位置上每个位置维的数值非0即1。但要通过实际决策变量的取值范围及求解精度来确定编码串长度。编码串长度确定：在本数值案例中，因为x1,x2

为0~31之间的整数，故求解范围为[0,31]，求解精度为1。由于24<31-0<25，所以用5位二进制编码串来表示决策变量。故粒子位置采用10位的二进制编码串来表示。如图所示，位置编码X＝1010011001所对应的解是：[x1,x2]＝[20,

25]。粒子位置

12粒子群算法概念详解编码与解码—实数编码举例说明：如图所示，在本数值案例中，粒子位置X＝20|25所对应的表现型是：[x1,x2]＝[20,

25]。每个位置维的取值均为0~31之间的整数。粒子位置对应解13粒子群算法概念详解适应度计算粒子的适应度指粒子对应位置在问题空间中的优劣程度度量。

位置编码对应解目标函数值适应度函数值1010011001

解码

计算目标函数值

14粒子群算法概念详解种群大小N即粒子群中所含个体的数目，通常N的取值范围为20~50。对于特殊或比较复杂的问题范围为100~200种群过大则使得算法运行时间变长，种群过小则容易导致算法搜索能力偏弱，易陷入局部最优。

15粒子群算法概念详解速度更新公式

更新后速度原速度调整

个体最优位置调整全局最优位置调整

16粒子群算法概念详解

线性惯性权重策略非线性惯性权重策略固定惯性权重策略

17粒子群算法概念详解

1.线性惯性权重策略

18粒子群算法概念详解

2.非线性惯性权重策略

19粒子群算法概念详解

固定学习因子策略线性学习因子调整策略非线性学习因子调整策略学习因子更新策略

20粒子群算法概念详解

1.线性学习因子调整策略

2.非线性学习因子调整策略

21粒子群算法概念详解

22粒子群算法概念详解位置更新

粒子新位置为原位置+

更新后的速度个体位置值超出边界，需要进行边界条件处理，本案例边界条件为：

23粒子群算法概念详解个体最优和全局最优

24粒子群算法概念详解终止准则制定最大迭代次数。（最常用的标准方式）计算耗费的资源限制。（如算法所用的时间或计算所占用的内存空间等）算法已经找到最优解。（往往使用在有标准最优解的情况下）个体不再移动。（即在一定的时间范围内，算法继续移动不会产生适应度值更好的个体。通常认为算法基本达到收敛水平。）其他的人为干预。25粒子群算法改进改进1：针对学习因子的改进

26粒子群算法改进改进2：针对惯性权重和收缩因子的改进：惯性权重

27粒子群算法改进改进2：针对惯性权重和收缩因子的改进：收缩因子

28粒子群算法改进改进3：最优粒子选择策略

【例1】把多目标优化问题分解分配粒子对相应的子问题进行优化，设计了一种基于外部存档集引导的择优策略，进行粒子速度更新，有效提高了收敛速度。【例2】基于增强选择策略的更新机制，通过切比雪夫聚集函数值、有利权重的切比雪夫值和随机选择三种方式，自适应切换聚集函数值，加强局部搜索的同时提高了收敛速度。【例3】基于动态加权聚合函数进行最优粒子的动态选择。最优粒子选择策略改进目录一、算法概述二、算法分析及改进三、工程案例分析四、基于Python的编程实践29工程案例分析可重构制造系统调度问题面向具有多品种、小批量特点的产品订单，在一个基于可重构机床的制造系统中如何合理的组织现有的制造资源，进行快速高效的产品生产是制造企业需要解决的关键问题。具体来说，该制造系统由多台可重构机床组成。每台可重构机床具有多种构型，每种构型对应一种产品特征（工序）的加工。对于一台可重构机床来说，不同构型之间的转化需要一定的设置时间和成本。此外，订单由多种类型的产品组成，每种产品的加工数量也各不相同。一种产品包含多个特征（工序），特征的加工存在固定的先后顺序。30工程案例分析可重构制造系统调度问题问题假设：针对每台可重构机床切换不不同构型时的设置时间及成本是固定相同的。可重构机床加工期间针对某一产品特征加工时间固定不考虑其运行故障。一台可重构机床的一种构型至多对应一种产品的一个特征的加工，即不考虑一种可重构机床的构型可以生产一种产品的多个特征的加工的情况。每种产品类型的同一产品特征必须在一台可重构机床上连续生产，不允许间断及生产任务拆分。在零时刻所有可重构机床均可用，所有产品均可以被加工。31工程案例建模符号说明：常量符号含义i,j产品类型索引(i,j=(1,2,…,P))k,lm可重构机床索引(m=(1,2,…,M))c索引32工程案例建模常量常量符号含义产品

i

的特征总数量可重构机床m的构型总数量产品i的加工数量产品i

的第k个特征在可重构机床m上的加工时间可重构机床m的构型切换时间产品i

的第k个特征能采用可重构机床m的第c个构型加工则为1，否则为0如果在可重构机床m上产品i

的第k个特征的加工构型与产品j

的第l个特征的加工构型不同则为1，否则为0足够大的数符号说明：33工程案例建模符号说明：决策变量与辅助变量常量符号含义产品i

的第k

个特征的生产开始时间产品i

的第k

个特征的生产完成时间产品i

的最终生产完成时间如果产品i

的第

k个特征选择可重构机床m进行加工则为1，否则为0如果在可重构机床

m上产品i

的第

k个特征加工完成后紧接加工产品

j

的第

l个特征则为1，否则为034工程案例建模优化目标：Makespan

模型约束：1）产品特征加工时间约束35工程案例建模模型约束：2）产品前后特征的加工时间约束模型约束：3）产品完工时间约束模型约束：4）可重构机床上时间占用约束模型约束：5）构型加工约束36工程案例建模模型约束：6）可重构机床的一种构型至多对应一种产品的一个特征的加工模型约束：7）对于任意的一个产品特征必须被某一个可重构机床进行加工模型约束：8）可重构机床上一个特征加工至多只有一个紧前、紧后加工特征模型约束：9）定义变量的取值范围37基于粒子群算法的案例求解粒子群算法应用分析使用粒子群算法求解可重构制造系统调度问题，需要重点解决以下3个问题：如何根据该可重构制造系统调度问题设计合理可行的编解码方案？边界条件、学习因子、惯性因子等参数如何设置？速度更新和位置更新操作如何具体执行？38基于粒子群算法的案例求解编码产品特征的加工顺序子决策问题:基于可重构制造系统调度的问题特征，我们需要进行两个子决策问题的求解：

在满足同一产品前后加工特征的顺序约束的基础上，我们需要考虑在可供选择的可重构机床上先生产哪一产品特征，以及后生产哪一产品特征。不同的产品特征生产顺序会影响最终调度方案的整体完工时间。加工产品特征的可重构机床配置子决策问题:

在满足同一时刻一台可重构机床至多只能用于一项产品特征加工的约束基础上，我们需要考虑针对不同产品的不同特征选择哪一可重构机床进行加工。不同的可重构机床配置方案会影响可重构机床的加工进程，进而影响最终调度方案的整体完工时间。39基于粒子群算法的案例求解编码考虑到以上两个子决策问题的解决，针对本数值案例，我们设计了如下双层编码形式。第一行代表产品特征的加工顺序，其中各编码位为产品序号。同一产品序号多次出现戴代表产品的不同特征。例如，第1个3代表产品3的第1个特征，第2个3代表产品3的第2个特征，以此类推。第二行代表产品特征选用的可重构机床序号，例如，第一个编码位的2代表产品3的特征1由可重构机床2进行加工，以此类推。可以看出，对于产品总数为P，每个产品i的加工特征为的Fi问题时，位置编码是长度为的整数编码串。40基于粒子群算法的案例求解解码在设计完成编码方式后，针对一个编码方案我们需要对其进行评价，以表征编码方案的优劣。因此，此步的设计与数学模型中的目标函数密切相关。即根据具体的编码方案，计算得出与之对应的目标函数值。在粒子群算法中，采用适应度值函数（Fitness）表征目标函数值(f(x))，即在一般化的粒子群算法范式中，适应度值越大，表明粒子位置越优。即针对极大化目标函数模型时Fitness=f(x)。而针对本问题的最小化目标函数模型时Fitness

=

-f(x)即可。注：在算法的具体编程实现时，我们不必拘泥于形式化的表达方式，即选用适应度值函数形式还是目标函数值都是可以的，但是要保证编码方案的优劣是可以进行对比的。41基于粒子群算法的案例求解粒子群初始化——初始位置生成针对本工程案例，我们设计了如下双层编码形式。如何初始化一个粒子的初始位置?这里采用了随机生成方式进行初始化粒子位置。针对第一层编码，假设针对一个产品1、2、3、4其各自所对应的特征总数为：3、3、4、2。我们只需要打乱其顺序即可获得不同的产品特征层编码。然后依照确定的第一行编码，从前向后逐个为产品特征随机选取进行加工的可重构机床，进而获得第二行机床配置层的编码。42基于粒子群算法的案例求解粒子群初始化——速度、个体最优、全局最优确定初始速度

初始个体最优对应个体初始位置初始全局最优

43基于粒子群算法的案例求解粒子速度更新速度更新速度修正

产品编码层设备编码层当前粒子位置当前粒子位置44基于粒子群算法的案例求解粒子位置更新位置更新基于位置公式更新近似值取整法化整边界修复判断是否超过边界若超过：随机重新初始化位置编码修复基于规则“相消替换”个体当前位置更新后速度更新位置取整位置修正位置当前粒子位置45基于粒子群算法的案例求解粒子位置更新位置更新基于位置公式更新近似值取整法化整边界修复判断是否超过边界若超过：随机重新初始化位置编码修复基于规则“相消替换”执行完交叉操作后，所得的更新后粒子位置对应解可能是非法解，即该粒子的位置编码不满足编码方式的要求。针对本工程案例：第一行产品特征层可能出现部分产品特征缺失和多余的情况；第二行机床配置层可能出现无法加工第一层所对应的产品特征的情况；因此，需要针对更新后粒子位置逐一进行编码修复以使其满足编码规范要求。46基于粒子群算法的案例求解粒子位置更新—修复产品特征层编码如下图所示，粒子的更新后位置出现了（1个1、4个2、7个3、0个4）。对比（3个1、3个2、4个3、2个4）的要求（缺失2个1、2个4，多余1个2、3个3）。本案例采用“相消替换”的思路来合法化非法粒子位置，即首先明确更新后位置与个体最优位置的缺失、多余特征，然后按照缺失多余的次序一一配对进行替换，进而完成解的合法化。当前粒子位置47基于粒子群算法的案例求解粒子位置更新—修复机床配置层编码即按照产品特征层的编码确定机床配置层编码是否可行，如果不可行则需为其随机选择可行的机床进行加工。如右图所示，首先查找粒子当前位置中机床配置层的非法位置编码，然后根据其可选机床为其随机配置机床配置层编码。48基于粒子群算法的案例求解评估新位置基于适应度值函数评估更新后粒子群各个粒子的位置。评价粒子位置的一般过程为对粒子位置编码串进行解码处理，得到当前粒子位置的对应解。由粒子的对应解可计算出对应粒子的目标函数值。如果粒子找到了相对于自身更好的位置，将该粒子的个体最优位置更新为当前粒子位置。如果整个粒子群中有粒子找到了相对于粒子群更好的位置，将全局最优位置更新为粒子群中找到的更好的位置。目录一、算法概述二、算法分析及改进三、工程案例分析四、基于Python的编程实践50工程实例产品类型产品数量特征数量1A20032B50033C10044D3002针对如下所示的具体实例数据进行粒子群算法的编写。生产订单信息可重构机床构型数转换时间转换成本1A38003502B56003003C31000500可重构机床信息51工程实例产品特征可重构机床1可重构机床2可重构机床3F(1,1)1-2F(1,2)-41F(1,3)213F(2,1)23-F(2,2)3-1F(2,3)11-F(3,1)-52F(3,2)2-1F(3,3)143F(3,4)33-F(4,1)143F(4,2)322产品特征对应机床构型表52工程实例产品特征可重构机床1可重构机床2可重构机床3F(1,1)5-8F(1,2)-1012F(1,3)679F(2,1)1319-F(2,2)10-5F(2,3)812-F(3,1)-49F(3,2)6-1F(3,3)3710F(3,4)93-F(4,1)594F(4,2)836产品特征加工时间（Min）53参数设置算法参数设定值种群大小20迭代次数100最大惯性因子0.9最小惯性因子0.1个体学习因子2全局学习因子2工件编码区最大速度2机器编码区最大速度254工程求解主代码执行粒子群算法并作图首先进行数据输入。然后，创建工程问题类FJSP_RMT，创建粒子群算法类PSO。最后，根据算法运行结果画出迭代图和最优解甘特图。导入依赖包输入初始化数据61工程问题类FJSP_RMTFJSP_RMT类的初始化60粒子群初始化该初始化代码每次生成一个满足要求的粒子及对应位置编码，然后通过粒子群算法主函数里的For循环实现初始粒子群群的创建。61解码代码根据粒子位置编码，计算其所对应的实际运行方案，然后获取其所对应的Makespan。62解码代码根据粒子位置编码，计算其所对应的实际运行方案，然后获取其所对应的Makespan。55粒子群算法主代码用于实现粒子群算法的主循环功能，通过初始化粒子群、粒子位置解码、粒子速度更新、粒子位置更新、位置编码修复、个体最优更新、全局最优更新操作对粒子群进行不断更新直至达到最大迭代要求终止搜索，输出最优解。确定粒子群算法各个参数56粒子群算法主代码创建运行过程中变量57粒子群算法主代码初始化粒子群并计算适应度值58粒子群算法主代码粒子群迭代循环主程序59粒子群算法主代码粒子群迭代循环主程序63速度更新代码基于速度更新公式，利用粒子的当前速度、个体最优位置、全局最优位置、惯性因子、学习因子对粒子的速度进行更新，并进行速度边界判断。64惯性因子更新代码基于惯性因子公式，根据当前迭代次数、最大惯性因子和最小惯性因子对惯性因子进行更新。惯性因子初始为值为最大惯性因子。65速度边界判断代码根据给定的最大速度所得到的速度取值范围，判断更新后的速度是否在取值范围内。对超过速度范围的速度进行速度截断操作。66位置更新代码基于位置更新公式，根据更新后的速度和粒子当前位置对粒子位置进行更新。并根据近似值取整法对粒子位置进行取整，最后进行位置边界判断。67位置边界判断代码根据问题中的产品数量和设备数量所确定的位置取值范围，判断更新后的位置是否在取值范围内。对超过位置范围的位置进行随机重新初始化位置的操作。68位置编码修复代码根据更新后的位置编码，判断编码是否满足问题中产品特征要求。如果更新后的位置非法，则对位置编码进行合法化修复。69实验结果实验结果展示如下，其搜索到的最优Makespan=13000s，运行时间为0.372s。粒子群算法迭代优化图最优个体方案的Gantt图主讲教师：黄思翰本节结束非支配排序遗传算法(NSGA-I/II/III)目录一、算法概述二、算法分析及改进三、工程案例分析四、基于Python的编程实践目录一、算法概述二、算法分析及改进三、工程案例分析四、基于Python的编程实践多目标优化1引入：在科学和工程实践问题求解时，决策者往往需要针对多个目标进行优化。基于此，为了客观公平地选出优秀的求解方案以供决策者参考，诸多学者将研究视野转向多目标优化问题（Multi-objectiveOptimizationProblem，MOP）。并且，随着进化算法的兴起，基于遗传算法发展演化而形成的多目标进化算法（Multi-objectiveevolutionaryalgorithm，MOEA）逐渐成为MOP问题求解的研究热点。传统的处理方式:赋予各目标权重，将多目标优化问题转化为单目标优化问题进行求解。但是，加权方式只能得到特定权重组合下的最优解，并且权重的设置很难使所有的决策者都信服。车间调度场景总完工时间（Makespan）能源消耗（Energy）成本/收益（Cost/profit）负载平衡（Workloadbalance）决策目标……非支配排序遗传算法概述2DavidSchaffer提出了向量评估遗传算法KalyanmoyDeb提出了NSGA的改进版本—NSGA-IINSGA系列算法已经形成了完整的理论体系KalyanmoyDeb提出了NSGA-III2002至今19852013“NSGA-II算法被ThomsonReuters评为最高引用论文和当代经典，已有超过31,000次引用。”“NSGA系列算法在组合优化、车间调度、机器人控制等领域均得到广泛应用。”19951989DavidGoldberg在其著作中提出了Pareto排序和基于适应度值共享的小生境方法来求解MOP问题KalyanmoyDeb提出了非支配排序遗传算法（NSGA）“它是众多的多目标进化算法中最直接体现了Goldberg思想的方法。““该算法的提出被视为利用进化算法求解MOP问题的开创性工作。”“弥补了NSGA-II在高维多目标优化问题上的不足。“多目标优化理论基础3多目标优化问题可以描述为多个目标同时在定可行域内寻优的问题，如下所示：

多目标优化多目标优化理论基础4在多目标优化问题求解时，多个目标之间的可能存在相互制约、冲突的情况，因此同时达到多个目标的最优几乎是不可能实现的。一个优化目标的提升往往导致另外一个或几个优化目标的降低，所以，不可能找到对所有的目标函数都是最优解的解。因此，多目标优化的解是一组解，其中的每个解相对其他解都有其独特的优势。这种优势可以通过一些标准来衡量，一个常用的方法是帕累托最优（Paretooptimality）。多目标优化概念多目标优化理论基础5多目标优化概念

多目标优化理论基础6多目标优化概念

NSGA系列算法理论基础7首先，NSGA系列算法（NSGA-I/NSGA-II/NSGA-III）均为基于Pareto排序的多目标进化算法。NSGA算法与基本遗传算法(GA)相比改进了选择算子，即通过非支配排序分层，可以使支配层级高的个体有更大的机会遗传到下一代。同时，采用适应度共享策略可以使帕累托前沿上的个体均匀分布，保持了群体多样性，克服了超级个体的过度繁殖，防止了早熟收敛。NSGA-I算法概述：NSGA系列算法理论基础8NSGA算法的不足(主要体现在如下3个方面):

NSGA系列算法理论基础9引入了快速非支配排序法、拥挤度距离和精英保留策略等概念。快速非支配排序：可以有效减少种群个体分层时的计算量，精简非支配排序流程。拥挤度距离：用于替换NSGA中的基于适应度值共享的小生境方法，并将拥挤度作为种群中个体之间的比较准则，使当前Pareto前沿面中的个体能够分布的更加均匀，从而保证了种群的多样性。精英保留策略：通过父代种群和子代种群合并后共同竞争来产生下一代种群，提升了NSGA算法的进化效率，保证优良个体不丢失。NSGA算法NSGA-II算法发展改进NSGA系列算法理论基础10NSGA-III与NSGA-II区别在于维持解的多样性的方法上：NSGA-II：运用拥挤度距离对同一非支配等级的个体进行选择，适用于2~3个目标的优化问题；NSGA-III：运用分布参考点在高维目标下来维持种群的多样性，适用于3个及以上的高维优化问题。NSGA-II算法NSGA-III算法发展改进NSGA系列算法理论基础11NSGA系列算法NSGA系列算法理论清晰易懂、算法流程简约高效，所以被广泛的应用在各个领域的研究中。如今，尤其是针对2-3个优化目标问题的求解中，NSGA-II仍是最为经典的、性能优良的多目标优化算法之一。因此，本书以NSGA-II为核心算法，辅以NSGA算法、NSGA-III算法中的差异之处进行后续的介绍和说明，使得读者更好的掌握NSGA系列算法。NSGA系列算法理论基础12基于Pareto排序的优化NSGA系列算法的核心就是在多个目标之间存在冲突时，采用Pareto占优的方式进行个体的优劣评判，从而实现在多个目标同时考虑下的算法寻优。NSGA系列算法的基本特点保障解的多样性针对多目标优化，最优解并非单个解而是一组解。因此，保障解的多样性是必要的。NSGA系列算法分别采用小生境、拥挤度距离、分布参考点的方式来保障解的多样性。遗传算法的特点由于NSGA系列算法的基本流程框架是遗传算法，故具有遗传算法的四个基本特点，即自组织、自适应性；并行性；不依赖数学性质；概率转换规则；目录一、算法概述二、算法分析及改进三、工程案例分析四、基于Python的编程实践113NSGA-II算法流程【步骤1】初始化参数：设置种群大小N、交叉概率Pc、变异概率Pm、每个个体染色体的基因个数n、遗传算法的最大迭代次数T，并按照随机或某种方式产生N个个体，进而组成初始种群。【步骤2】适应度计算：每个个体通过适应度函数（基于优化目标）计算出多个适应度值，用以判断个体的优劣程度。【步骤3】快速非支配排序与拥挤度距离：

根据每个个体的适应度值间的支配关系进行排序。排序后的个体解被分为若干个非支配序值。在每个非支配序值内，计算每个个体解的拥挤度距离。拥挤度距离是衡量解周围空间拥挤程度的指标，计算方式是在目标空间中，计算每个解在各目标函数上的相邻解之间的距离。114NSGA-II算法流程【步骤4】选择操作：

根据某种选择策略从当前种群中根据非支配序值与拥挤度距离选择一定数量的个体，并将其作为父代种群。【步骤5】交叉操作：随机生成一个数c∈[0,1]，若c<Pc，则对父代种群中的两两个体进行交叉操作，直至产生N×Pc个子代个体。【步骤6】变异操作：随机生成一个数m∈[0,1]，若m<Pm，则根据变异概率Pm对当前种群中个体的单个或多个基因位进行变异操作产生变异个体，直至产生N×Pc个子代个体。15NSGA-II算法流程【步骤7】基于精英保留策略的种群修剪：

将父代、子代种群进行合并，计算其适应度值后，基于解的非支配序值与拥挤度距离按照精英保留策略保留N个个体形成当前种群。【步骤8】终止条件判断：若不满足终止条件，则返回算法步骤4；若满足终止条件，则输出最佳的Pareto前沿面个体解集，算法结束。16NSGA-II

算法概念详解术语表征编码(Coding)表现型到基因型的映射；解码(Decoding)从基因型到表现型的映射；个体(Individual)携带遗传基因的染色体，即具有串结构特征的解方案；种群(Population）个体的集合。其中第

t代种群记作

P(t)；适应度评估(Fitness)表示个体的优劣性，适应度值函数的设定因问题而异；快速非支配排序(Fastnon-dominatedsort)根据个体间适应度值支配关系进行排序，划分形成不同的序值曲面的过程；拥挤度距离(Crowdingdistance)针对同一序值曲面上的个体，衡量个体在序值曲面上空间拥挤程度的指标；首先，对NSGA-II算法的基本术语进行梳理表征。17NSGA-II

算法概念详解术语表征选择(Selection):根据个体适应度，按照一定规则，选择出一些优良的个体遗传到下一代种群中；交叉(Crossover)将种群个体搭配成对，并针对每对个体根据交叉概率按照一定方法交换它们之间的部分染色体片段；变异(Mutation)针对种群中的每一个个体，根据变异概率改变单(多)个基因位上的基因值为其他的等位基因；精英保留策略(Elitismstrategy)将父代种群、子代种群合并后，采取最优个体保留的形式进行种群修剪；（续表）18NSGA-II

算法概念详解

由此，NSGA-II算法的表征模型可以表示为如下的11元组：S：选择算子;

（Select）C：交叉算子;

（Crossover）M：变异算子;

（Mutation）Es：精英保留策略（Elitismstrategy）

T：算法终止条件;

（Termination）C：个体染色体的编码方法;（Coding）F：个体的适应度评价函数;（Fitness）Ns：非支配排序；（Non-dominatedsort）Cd：拥挤度距离；（Crowdingdistance）P0：初始种群;

（Population）N：种群大小;

（Number）

19NSGA-II

算法概念详解数值案例简介同时求解下述两个二元二次函数的最大值:基于此数值案例剖析NSGA-II算法，并辅以介绍NSGA及NSGA-III算法对其编解码方式、适应度值计算、初始化参数、快速非支配排序、维持解的多样性(小生境、拥挤度距离、分布参考点)

、选择、交叉、变异操作、基于精英保留策略的种群修剪等具体流程深入讲解。

20NSGA-II

算法概念详解编码与解码问题分析实际问题解决方案结构数据串算法执行问题求解算法编码算法解码输入输出编码:即将问题的解决方案表征为具有一定特征的结构数据串。解码:是将结构化的数据串转化为解决方案的过程，即编码的逆运算。常见的编码形式包括：二进制编码、实数编码、符号编码等。21NSGA-II

算法概念详解编码与解码—二进制编码二进制编码是常见的编码方式。特点：解码简单，染色体上每个基因位的数值非0即1。交叉、变异算子易于实现。但要通过实际决策变量的取值范围及求解精度来确定编码串长度。编码串长度确定：在本数值案例中，因为x1,x2

为0~31之间的整数，故求解范围为[0,31]，求解精度为1。由于24<31-0<25，所以用5位二进制编码串来表示决策变量。故个体的基因型采用10位的二进制编码串来表示。如图所示，基因型X＝1010011001所对应的表现型是：[x1,x2]＝[20,

25]。

22NSGA-II

算法概念详解适应度计算个体的适应度指个体在种群生存的优劣程度度量。针对个体进行解码处理后，得到个体的表现型。由个体的表现型计算出个体的目标函数值。根据最优化问题的类型，由目标函数值按一定的转换规则求出个体的适应度。评价个体适应度的一般过程为

23NSGA-II

算法概念详解初始化参数1.种群大小N

即种群中所含个体的数目，通常N的取值范围为20~200。

种群过大则使得算法运行时间变长，种群过小则容易导致算法搜索能力偏弱。2.选择代沟S_gap从父代种群中选择出子代种群的个体比例，一般其取值范围为0.8~1。选择概率不能过小，过小会导致后续的交叉、变异操作起不到对种群进化的推进作用。24初始化参数3.交叉概率Pc指定交叉操作发生的概率，一般其取值范围为0.4~0.9。交叉概率不能过大不易保留优秀的基因片段。过小则起不到更新进化的作用。4.变异概率Pm

变异操作发生的概率，用于保证种群多样性。一般取值范围为0.001~0.2。5.遗传算法的最大迭代次数T通常T的取值范围为100~500，其与算法的运行时间正相关。NSGA-II

算法概念详解25NSGA-II

算法概念详解初始化参数6.算法停止条件计算耗费的资源限制。（如算法所用的时间或计算所占用的内存空间等）算法已经找到最优解。（往往使用在有标准最优解的情况下）个体不再进化。（即在一定的时间范围内，算法继续进化不会产生适应度值更好的个体。通常认为算法基本达到收敛水平。）其他的人为干预。27NSGA-II

算法概念详解快速非支配排序在介绍快速非支配排序法之前，我们首先回顾NSGA中所提出的非支配排序法，进而便于读者理解快速非支配排序法中的快速是如何体现的。求解多目标优化问题获取Pareto最优解集快速非支配排序法关键经典方法28NSGA-II

算法概念详解NSGA—非支配排序流程在NSGA算法中，通过支配与非支配关系，实现了种群个体间的序值划分，序值越低的个体将拥有越大的选择权利。如果优化目标函数为最大化函数，即函数值越大越好。优化目标数量为

M，种群的大小为N，popi表示种群中第i个个体。首先，针对种群中的所有个体进行适应度值函数的计算，然后进行非支配排序，具体过程如下：流程1：令

i=1；流程2：对于所有的

j=1,2,...,N，且

j≠i，判断个体

popi和个体

popj之间的支配关系；流程3：如果不存在支配

popi的个体

popj，就称

popi为非支配个体；流程4：i=i+1，转到流程2，直到获取所有的非支配个体；流程5：将当前的非支配个体集合设置为第一序值层，然后将种群中的其余个体重复流程1~4进行新一轮的分层任务，直到种群中的所有个体