一种基于状态变换差分进化的混合离散变量优化方法及系统

摘要

本发明公开了一种基于状态变换差分进化的混合离散变量优化方法及系统。优化方法包括迭代执行多轮处理过程，在所述处理过程中，获取父代种群，对父代种群进行处理获得试验种群，将父代种群和试验种群组合成混合种群，对混合种群使用多目标更新策略进行更新获得更新种群等步骤。本发明通过将基于睡眠觉醒周期模式的状态变换机制应用于差分进化算法，受雁阵效应的启发，使用了多目标种群更新机制，将两种不同的选择算子以一定的代数阈值交替，可以更合理有效地平衡选择操作中的探索性与开发性，进而更好指导种群进化，可以用于解决既包含连续变量又包含离散变量的工业优化、设计、制造类问题。本发明广泛应用于工业数据处理技术领域。

说明书

技术领域

本发明涉及工业参数处理技术领域，尤其是一种基于状态变换差分进化的混合离散变量优化方法和系统。

背景技术

随着制造业的飞速发展，没有先验知识且包含离散、非线性、不可导等复杂特性的工业设计与制造问题越来越普遍。其中，混合离散变量优化问题是工业制造业中极具代表性的一类问题。混合离散变量优化问题是指待优化参数中既有连续变量又有离散变量的一类优化设计问题，用于自动求解此类问题的算法称为混合离散变量优化算法。解决混合离散变量优化问题的挑战在于如何基于迭代操作来确定最佳离散变量可能值，进而体现出优化的思想。确定性优化算法需要问题的先验知识且通常时间复杂度很高，而离散变量又不能使用传统随机化搜索算法来解决，因此有关混合离散变量优化算法的相关研究较少。目前基于演化算法的的离散变量处理方案大致可以分为直接法和间接法两大类。直接法是指在由离散参数组成的决策空间中对离散变量直接进行处理。而间接法通常引入额外的约束关系，通过转换算子将连续值映射为离散值。上述现有技术除了会引入高复杂度或者种群多样性缺失外，局限于考虑处理的离散参数为二进制数和整数的情况，在对参数为小数优化时难以取得理想效果。

发明内容

针对上述至少一个技术问题，本发明的目的在于提供一种基于状态变换差分进化的混合离散变量优化方法及系统。

一方面，本发明实施例包括一种基于状态变换差分进化的混合离散变量优化方法，包括以下步骤：

迭代执行多轮处理过程；

在每轮所述处理过程中，获取父代种群，对所述父代种群中的每个成员使用差分进化算法生成连续试验向量；对所述父代种群中的生存时间小于1的成员，将该成员内的每个离散变量依次从所有处于苏醒状态的可能值中通过轮盘赌方式确定取值，将该成员的生存时间置为1，从而获得离散试验向量；合并所述连续试验向量和所述离散试验向量，从而获得完整试验向量；整合所有所述完整试验向量，从而获得试验种群；将所述父代种群和所述试验种群组合成混合种群，对所述混合种群使用多目标更新策略进行更新，从而获得更新种群；使用所述更新种群更新存档；

其中，在第一轮所述处理过程中，所述父代种群由初始连续子群和初始离散子群合并得到，所述初始连续子群是在给定的连续参数取值范围内随机生成的，所述初始离散子群是对初始生成的成员中的离散变量依次从处于苏醒状态时的候选值中，通过轮盘赌方式确定取值生成的；在除第一轮所述处理过程以外的其他所述处理过程中，所述父代种群为上一轮所述处理过程所获得的所述更新种群。

进一步地，在每轮所述处理过程中，如果所获得的所述更新种群中部分或全部成员与所述父代种群中的成员相同，那么将所述更新种群中的这些相同的成员的生存时间延长一代；如果所获得的所述更新种群中部分或全部成员与所述父代种群中的成员不相同，那么将所述更新种群中的这些不相同的成员的生存时间缩短一代。

进一步地，在每轮所述处理过程中，对于一个处于苏醒状态的可能值，如果包含该可能值的所有成员未能从所述父代种群中存活至所述更新种群，将该可能值的状态由苏醒状态设置为睡眠状态。

进一步地，在每轮所述处理过程中，对于一个离散变量，如果该离散变量对应的全部可能值均为睡眠状态，将该离散变量对应的全部可能值设置为苏醒状态。

进一步地，对于一个离散变量，如果该离散变量对应的部分或全部可能值的状态在连续多轮所述处理过程中均未发生变化，将未发生变化的这些可能值的状态设置为苏醒状态。

进一步地，所述对所述混合种群使用多目标更新策略进行更新，包括：

使用第一选择算子和第二选择算子对所述混合种群进行连续多代的交替执行；其中，所述第一选择算子为基于非支配占优的NSGAIII的选择算子，所述第二选择算子为MOEA/D中基于Tchebyshev分解的选择算子。

进一步地，所述使用所述更新种群更新存档，包括：

将所述混合种群中通过非支配排序确定的最前面多个成员存储至所述存档中，并覆盖所述存档中的原内容。

进一步地，还包括：

当所述处理过程满足终止条件，以最后一轮所述处理过程所使用的所述父代种群与从所述存档中读取出的内容混合后，通过非支配排序确定混合结果中的最前面多个成员作为最终解；

返回所述最终解。

进一步地，所述终止条件为所有所述处理过程的总轮数达到预设轮数阈值。

另一方面，本发明实施例还包括一种基于状态变换差分进化的混合离散变量优化系统，所述基于状态变换差分进化的混合离散变量优化系统用于：

迭代执行多轮处理过程；

在每轮所述处理过程中，获取父代种群，对所述父代种群中的每个成员使用差分进化算法生成连续试验向量；对所述父代种群中的生存时间小于1的成员，将该成员内的每个离散变量依次从所有处于苏醒状态的可能值中通过轮盘赌方式确定取值，将该成员的生存时间置为1，从而获得离散试验向量；合并所述连续试验向量和所述离散试验向量，从而获得完整试验向量；整合所有所述完整试验向量，从而获得试验种群；将所述父代种群和所述试验种群组合成混合种群，对所述混合种群使用多目标更新策略进行更新，从而获得更新种群；使用所述更新种群更新存档；

其中，在第一轮所述处理过程中，所述父代种群由初始连续子群和初始离散子群合并得到，所述初始连续子群是在给定的连续参数取值范围内随机生成的，所述初始离散子群是对初始生成的成员中的离散变量依次从处于苏醒状态时的候选值中，通过轮盘赌方式确定取值生成的；在除第一轮所述处理过程以外的其他所述处理过程中，所述父代种群为上一轮所述处理过程所获得的所述更新种群。

本发明的有益效果是：实施例中的基于状态变换差分进化的混合离散变量优化方法，提通过将基于睡眠觉醒周期模式的状态变换机制应用于差分进化算法，可以处理既包含连续变量又包含离散变量的混合离散变量优化设计类问题；受雁阵效应的启发，使用了多目标种群更新机制，将两种不同的选择算子以一定的代数阈值交替，可以更合理有效地平衡选择操作中的探索性与开发性，进而更好指导种群进化，可以用于解决决策变量为离散参数的工业优化、设计、制造类问题。

附图说明

图1为实施例中基于状态变换差分进化的混合离散变量优化方法与现有的混合离散变量优化算法在常用多目标测试函数上输出解的分布情况效果图。

具体实施方式

经典算法的遗传算子最初是为连续空间的优化而设计的，因此在求解离散变量的问题上进展缓慢。然而，在处理实际工业制造类问题时，常常涉及离散变量的优化，而且，离散变量的优化通常也伴随着连续变量的优化。目前相关的文献较少，关于混合离散变量优化的问题的研究还处于早期阶段。

离散问题是指决策变量为离散值的问题，而混合离散变量优化问题同时包含需要优化的离散变量和连续变量。离散变量可以是二进制、整数或小数。在优化算法中涉及离散变量的问题很难处理，主要是由于作为可行解的父代所产生的后代可能是非可行解。换句话说，离散变量的可能值在进行突变、重组等遗传操作后，产生的子代可能是该离散变量的非候选值，这种情况下迭代操作无法正常进行。

针对这种情况，本实施例中提出了一种基于睡眠觉醒周期模式的差分进化算法来解决离散变量维度高候选值多的混合离散变量优化问题。其原理在于：对于每个离散变量的所有可能值，存在两种状态，睡眠状态和苏醒状态。苏醒状态表明当前可能的值有机会用于构造一个完整的解决方案，而睡眠状态则不会。根据选择操作的反馈，合理设置可能值的状态，可以快速排除无效解，遴选出有效解，直到得到最优解。出于多样性的考虑，睡眠状态在一定情况下会重置为苏醒状态，用于避免陷入局部最优或者可以从局部最优中跳出。此外，为了增强本方案及系统的适用性，受雁阵效应启发，配合使用一种多目标种群更新机制。

本实施例中，基于状态变换差分进化的混合离散变量优化方法包括以下步骤：

S1.初始化种群的基本参数，配置最大迭代次数、代数计数器，为离散变量的全部可能值分配设置苏醒状态，设置交叉概率CR，设置种群规模NP，连续变量维度Dc，离散变量维度Dd，每个离散变量的可能值数量M，将所有离散变量的全部可能值都设置为苏醒状态，设置最大迭代次数g

S2.迭代执行多轮处理过程。

本实施例中，步骤S1为初始化过程，执行步骤S1的目的是为了设置步骤S2中需要用到的各项参数。在执行步骤S1时，具体可以执行以下步骤：

S101.设置种群规模为NP，连续变量的维度D

S102.初始化连续变量的上下限：

S103.基于变量的上下限生成初始连续种群

其中，离散变量维度为D

x

其中，c

步骤S1实际上是：在给定的连续参数取值范围内，随机生成初始连续子群

在执行完步骤S1之后，执行步骤S2。步骤S2中以循环迭代方式执行多个处理过程，即每个处理过程执行完毕后检查是否达到终止条件，如果达到终止条件，则输出最终结果，如果未达到终止条件，则执行下一轮处理过程，而且除了第一轮处理过程之外，每一轮处理过程对上一轮处理过程获得的结果进行处理。

本实施例中，执行的第一轮处理过程中的父代种群是指父代种群P

本实施例中，在执行第g轮处理过程时，具体执行以下步骤S201g-S206g：

S201g.对于父代种群中的每个成员，使用经典差分进化算法生成连续的试验向量

S202g.对于父代种群P

S203g.对于父代种群P

S204g.对于每个离散变量中处于苏醒状态的可能值依次进行检查，如果原始父代中包含该可能值的所有成员都没能在选择操作时存活下来，即出现在更新后的种群中，那么该可能值的状态由苏醒状态变为睡眠状态。经过上述操作后，如果该离散变量的所有可能值状都为睡眠状态，则将全部可能值都重置为苏醒状态。

S205g.对所有离散变量依次进行检查，如果某离散变量的所有可能值状态都没有发生改变，那么该离散变量的状态不变旗标加一，否则重置为一。若该离散变量的状态不变旗标数值超过了T

S206g.更新代数计数器，g＝g+1。选择操作中更新的种群P

步骤S201g-S206g中，对于待优化问题中的离散变量，每个离散变量有若干个可能值组成候选值池。为池中的每个可能值都分配两个状态，睡眠状态和苏醒状态，这两个状态不会同时出现，但在任何时刻该可能值都处于其中的一种状态。对于包含离散变量的优化问题，依据离散变量的可能值的状态确定该参数的取值。具体来讲，对于每个离散参数的可能值池，其中处于苏醒状态的可能值有机会被选择出来用于确定离散变量取值，具体的确定方法是使用轮盘赌的方式选择其中一个作为该离散变量的取值；而处于睡眠状态的可能值则不会被选择。对于包含离散参数的优化设计问题，种群内成员的生存时间的作用，定义与更新方式。成员的生存时间的作用是决定内部的离散变量是否进行更新，通常定义为一个整数。如果生存时间小于等于零，则成员的离散变量需要进行更新，否则不更新。生存时间的更新方式与该成员的适应度有关，如果该成员在选择操作中存活下来，那么生存时间增加一代，否则生存时间减少一代。对进行了离散变量更新的成员，其生存时间设置为1。

步骤S202g的原理是：受雁阵效应启发，提出一种多目标种群更新策略。具体来说，引入NSGAIII和MOEAD中基于Tchebyshev分解的选择方式作为基线选择算子，结合雁阵效应的思想，从而获得一种更合理、更有效的选择操作。输入亲本种群P，试验种群P

步骤S204g-S205g的原理是：包含离散变量的优化问题中，离散变量可能值的状态变换规则。对于某一个处于苏醒状态的可能值，如果包含该可能值的所有成员在选择操作中都没能存活下来，那么该可能值的状态由苏醒状态变换为睡眠状态。如果有一个离散变量，如果对应的全部可能值都为睡眠状态，那么这些可能值会全部重置为苏醒状态。对于某离散变量的可能值的状态有连续超过T

本实施例中，步骤S201g-S206g可以通过以下(1)-(9)所示的公式和计算机代码执行：

(1)进行while判断，当g≤g

(2)使用for循环遍历当前种群内的每一个成员，即for(ii＝1,ii≤NP,ii++)；

(3)从连续子群

(4)根据传统差分进化算法的变异操作生成突变向量：

(5)基于交叉操作生成试验向量

其中jj表示连续变量维度的索引，rand是位于[0,1]区间内的随机数，rand

(6)如果第ii个成员的生存时间小于1，那么就重新生成新的离散试验变量

其中kk是指该成员内离散变量的索引，而c

(7)合并连续试验向量

结束for循环。

(8)合并所有的试验向量

(9)执行多目标种群更新策略：

引入NSGAIII和MOEAD中基于Tchebyshev分解的选择方式作为基线选择算子，结合雁阵效应的思想，从而获得一种更合理、更有效的选择操作。输入亲本种群P

其中，NSIII和MO/D_Tchebyshev分别表示NSGAIII中的选择算子和MOEA/D中基于Tchebyshev分解法的选择算子。在发生选择算子变换时，会用更新后的种群对存档进行更新，即P

本实施例中，步骤S201g-S206g组成一轮处理过程。在执行完一轮处理过程后检查当前已执行过的所有处理过程的总轮数是否已达到预设轮数阈值g

执行本实施例中的基于状态变换差分进化的混合离散变量优化方法，其结果与现有混合离散变量优化算法在测试函数上的IGD结果比较如表1所示。具体地，将本实施例方法与现有技术在常用多目标测试集上独立运行30次的性能比较，获得表1所示数据。

执行本实施例中的基于状态变换差分进化的混合离散变量优化方法，其结果与不同选择方式在测试函数上的IGD结果比较如表2所示。具体地，将本实施例方法与现有技术在不同的多目标选择算子在常用测试集上独立运行30次地IGD结果比较，获得表2所示数据。

执行本实施例中的基于状态变换差分进化的混合离散变量优化方法，其结果与不同离散参数变异策略在测试函数上的IGD结果比较如表3所示。具体地，将本实施例方法与现有技术在不同的离散变量变异策略在常用测试集上独立运行30次地IGD的结果比较，获得表3所示数据。

执行本实施例中的基于状态变换差分进化的混合离散变量优化方法，其结果与现有混合离散变量优化算法在测试函数上的输出解的分布情况如图1所示。

表1

表2

表3

通过表1、表2、表3、图1的结果比较，可以总结出本实施例中基于状态变换差分进化的混合离散变量优化方法的有益效果包括：

(1)提出一种基于睡眠觉醒周期模式的状态变换机制的优化方法及系统，可以用于解决决策变量为离散参数的工业优化、设计、制造类问题；具体如单车间调度问题，N个工件在M台机器上加工，每个工件有特定的加工工艺，每个工件加工的顺序以及每道工序所花的时间给定，安排工件在每台机器上工件加工的顺序，使得某种指标最优。可以将一台机器对应本实施例中基于睡眠觉醒周期模式的状态变换机制的优化方法中的一个离散变量，这个离散变量的可能值可以是这台机器所加工的工件的编号等数据，即机器对应了系统中的离散变量，工件对应了离散变量的可能值。最终输出的解就是每台机器上工件加工的顺序，使得总的加工时间最短。

(2)将基于睡眠觉醒周期模式的状态变换机制应用于差分进化算法，得到一个基于状态变换差分进化的混合离散变量优化方法及系统。该方案可以处理既包含连续变量又包含离散变量的混合离散变量优化设计类问题；例如相控阵天线的优化设计就是一个既包含连续变量又包含离散变量的混合离散变量优化设计类问题，对于一个包含1*2N个阵元的相控阵天线，每个阵元需要优化的参数有幅度和相位。因为相控阵的对称性，所以只用优化其中的N个阵元。N个阵元的幅度可以视为是本实施例中基于睡眠觉醒周期模式的状态变换机制的优化方法中种群中的连续变量，取值范围可以为[0.01,1]，N个阵元使用数字移相器控制的相位可以视为是本实施例中基于睡眠觉醒周期模式的状态变换机制的优化方法中种群中的离散变量，假设每个阵元有64个可能值，则它们分别是[-180,180]中以5.625为步进的所有值。通过本实施例中基于睡眠觉醒周期模式的状态变换机制的优化方法对幅度和相位进行优化，从而可以得到符合要求的辐射为笔形光束或平顶光束的相控阵天线，输出的解则是该天线中幅度和相位的具体取值。

(3)提出一种新颖的多目标种群更新机制，受雁阵效应的启发，将具有强开发性的NSGAIII选择算子和注重探索性的MOEA/D中基于Tchebyshev分解的选择算子以一定的代数阈值交替，可以更合理有效地平衡选择操作中的探索性与开发性，进而更好指导种群进化。

通过编写用于执行本实施例中的基于状态变换差分进化的混合离散变量优化方法的计算机代码，将计算机代码写入至计算机系统的存储器中，使得计算机系统的处理器从存储器中读取并运行计算机代码时，将执行本实施例中的基于状态变换差分进化的混合离散变量优化方法。这样的计算机系统成为基于状态变换差分进化的混合离散变量优化系统，当这样的计算机系统被运行时能够执行基于状态变换差分进化的混合离散变量优化方法，从而实现与基于状态变换差分进化的混合离散变量优化方法实施例相同的技术效果。

需要说明的是，如无特殊说明，当某一特征被称为“固定”、“连接”在另一个特征，它可以直接固定、连接在另一个特征上，也可以间接地固定、连接在另一个特征上。此外，本公开中所使用的上、下、左、右等描述仅仅是相对于附图中本公开各组成部分的相互位置关系来说的。在本公开中所使用的单数形式的“一种”、“所述”和“该”也旨在包括多数形式，除非上下文清楚地表示其他含义。此外，除非另有定义，本实施例所使用的所有的技术和科学术语与本技术领域的技术人员通常理解的含义相同。本实施例说明书中所使用的术语只是为了描述具体的实施例，而不是为了限制本发明。本实施例所使用的术语“和/或”包括一个或多个相关的所列项目的任意的组合。

应当理解，尽管在本公开可能采用术语第一、第二、第三等来描述各种元件，但这些元件不应限于这些术语。这些术语仅用来将同一类型的元件彼此区分开。例如，在不脱离本公开范围的情况下，第一元件也可以被称为第二元件，类似地，第二元件也可以被称为第一元件。本实施例所提供的任何以及所有实例或示例性语言(“例如”、“如”等)的使用仅意图更好地说明本发明的实施例，并且除非另外要求，否则不会对本发明的范围施加限制。

应当认识到，本发明的实施例可以由计算机硬件、硬件和软件的组合、或者通过存储在非暂时性计算机可读存储器中的计算机指令来实现或实施。所述方法可以使用标准编程技术-包括配置有计算机程序的非暂时性计算机可读存储介质在计算机程序中实现，其中如此配置的存储介质使得计算机以特定和预定义的方式操作——根据在具体实施例中描述的方法和附图。每个程序可以以高级过程或面向目标终端的编程语言来实现以与计算机系统通信。然而，若需要，该程序可以以汇编或机器语言实现。在任何情况下，该语言可以是编译或解释的语言。此外，为此目的该程序能够在编程的专用集成电路上运行。

此外，可按任何合适的顺序来执行本实施例描述的过程的操作，除非本实施例另外指示或以其他方式明显地与上下文矛盾。本实施例描述的过程(或变型和/或其组合)可在配置有可执行指令的一个或多个计算机系统的控制下执行，并且可作为共同地在一个或多个处理器上执行的代码(例如，可执行指令、一个或多个计算机程序或一个或多个应用)、由硬件或其组合来实现。所述计算机程序包括可由一个或多个处理器执行的多个指令。

进一步，所述方法可以在可操作地连接至合适的任何类型的计算平台中实现，包括但不限于个人电脑、迷你计算机、主框架、工作站、网络或分布式计算环境、单独的或集成的计算机平台、或者与带电粒子工具或其它成像装置通信等等。本发明的各方面可以以存储在非暂时性存储介质或设备上的机器可读代码来实现，无论是可移动的还是集成至计算平台，如硬盘、光学读取和/或写入存储介质、RAM、ROM等，使得其可由可编程计算机读取，当存储介质或设备由计算机读取时可用于配置和操作计算机以执行在此所描述的过程。此外，机器可读代码，或其部分可以通过有线或无线网络传输。当此类媒体包括结合微处理器或其他数据处理器实现上文所述步骤的指令或程序时，本实施例所述的发明包括这些和其他不同类型的非暂时性计算机可读存储介质。当根据本发明所述的方法和技术编程时，本发明还包括计算机本身。

计算机程序能够应用于输入数据以执行本实施例所述的功能，从而转换输入数据以生成存储至非易失性存储器的输出数据。输出信息还可以应用于一个或多个输出设备如显示器。在本发明优选的实施例中，转换的数据表示物理和有形的目标终端，包括显示器上产生的物理和有形目标终端的特定视觉描绘。

以上所述，只是本发明的较佳实施例而已，本发明并不局限于上述实施方式，只要其以相同的手段达到本发明的技术效果，凡在本发明的精神和原则之内，所做的任何修改、等同替换、改进等，均应包含在本发明保护的范围之内。在本发明的保护范围内其技术方案和/或实施方式可以有各种不同的修改和变化。