[go: up one dir, main page]

CN111311638B - 基于分割多向预测策略的动态多目标优化方法 - Google Patents

基于分割多向预测策略的动态多目标优化方法 Download PDF

Info

Publication number
CN111311638B
CN111311638B CN202010087473.5A CN202010087473A CN111311638B CN 111311638 B CN111311638 B CN 111311638B CN 202010087473 A CN202010087473 A CN 202010087473A CN 111311638 B CN111311638 B CN 111311638B
Authority
CN
China
Prior art keywords
population
prediction
vector
individuals
search
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Active
Application number
CN202010087473.5A
Other languages
English (en)
Other versions
CN111311638A (zh
Inventor
齐智敏
马贤明
宋亚飞
张海林
倪鹏
陈敏
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Evaluation Argument Research Center Academy Of Military Sciences Pla China
Original Assignee
Evaluation Argument Research Center Academy Of Military Sciences Pla China
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Evaluation Argument Research Center Academy Of Military Sciences Pla China filed Critical Evaluation Argument Research Center Academy Of Military Sciences Pla China
Priority to CN202010087473.5A priority Critical patent/CN111311638B/zh
Publication of CN111311638A publication Critical patent/CN111311638A/zh
Application granted granted Critical
Publication of CN111311638B publication Critical patent/CN111311638B/zh
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T7/00—Image analysis
    • G06T7/20—Analysis of motion
    • G06T7/246—Analysis of motion using feature-based methods, e.g. the tracking of corners or segments
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
    • G06N3/00—Computing arrangements based on biological models
    • G06N3/004—Artificial life, i.e. computing arrangements simulating life
    • G06N3/006—Artificial life, i.e. computing arrangements simulating life based on simulated virtual individual or collective life forms, e.g. social simulations or particle swarm optimisation [PSO]
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T7/00—Image analysis
    • G06T7/10—Segmentation; Edge detection
    • G06T7/11—Region-based segmentation
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T2207/00—Indexing scheme for image analysis or image enhancement
    • G06T2207/10—Image acquisition modality
    • G06T2207/10016—Video; Image sequence

Landscapes

  • Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Computer Vision & Pattern Recognition (AREA)
  • Biophysics (AREA)
  • Data Mining & Analysis (AREA)
  • Life Sciences & Earth Sciences (AREA)
  • Artificial Intelligence (AREA)
  • Biomedical Technology (AREA)
  • Multimedia (AREA)
  • Computational Linguistics (AREA)
  • Health & Medical Sciences (AREA)
  • Evolutionary Computation (AREA)
  • General Health & Medical Sciences (AREA)
  • Molecular Biology (AREA)
  • Computing Systems (AREA)
  • General Engineering & Computer Science (AREA)
  • Mathematical Physics (AREA)
  • Software Systems (AREA)
  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)

Abstract

本发明公开了一种基于分割多向预测策略的动态多目标优化方法，它针对线性模型预测误差弥补不足的问题，能够更好的预测最优前沿的变化，保证对最优前沿凹凸性的分布变化的预测，有效弥补方向预测的距离误差。它包括如下步骤：(1)对动态多目标问题进行描述；(2)分割多向预测。本发明的有益效果在于：首先将搜索到的最优前沿进行分割，依据最优前沿的分割结果划分种群，对种群每个部分进行线性预测，借鉴云模型对于不确定时间的描述，用熵和超熵弥补预测误差，针对动态问题中可能发生的突发性非线性变化，采用偏角增强搜索策略保证预测过程中种群的多样性。

Description

基于分割多向预测策略的动态多目标优化方法
技术领域
本发明属于智能计算、多目标优化技术领域，具体涉及基于分割多向预测策略的动态多目标优化方法。
背景技术
在空天高速目标探测跟踪过程中，由于目标速度快、机动能力强、飞行区域跨度大，单一传感器难以有效持续探测跟踪，因此运用多源异构传感器调度技术合理安排探测跟踪任务与时序显得尤为重要。调度的资源主要包含天基红外传感器和地基雷达传感器，涉及到的传感器类型包括高轨红外探测卫星、低轨红外卫星、地基P波段雷达和地基X波段雷达等。
由于空天高速目标是一类新型目标，目前关于此类目标探测跟踪的传感器资源调度问题的研究较少。卫星资源调度与此问题相似，两者的求解调度方案都是基于时间的资源分配问题。但是传感器资源对目标的探测跟踪有严格的时间约束，如果在有限时间内传感器只能实现部分监视或是无监视，那么该任务失败且不存在二次观测的机会，这是与一般的遥感或是导航卫星调度问题的主要区别。
由于问题特性不同，传感器资源调度问题与传统调度问题存在以下3点区别：
(1)任务无时间等待，目标在有限时间内不被观测则没有观测机会。
(2)一对多和多对一同时存在的资源匹配，匹配规则不一致导致编码和搜索难度加大。
(3)传感器观测时间碎片化，搜索过程中容易产生不符合约束条件的碎片时间，搜索难度加大。
针对上述问题，考虑构建空天高速目标探测跟踪多源异构传感器资源调度模型因素，可以利用动态多目标优化(Dynamic Multi-objective Optimization,DMO)模型来实现多源异构传感器资源的实时调度，为空天高速目标的协同跟踪构建可靠的传感器网络。
动态多目标优化问题(Dynamic Multi-objective Optimization Problem,DMOP)不仅表现出多目标优化问题的优化目标冲突、解空间维度高等特点，还具有优化目标、条件约束、决策空间随时间变化的特点。传统优化方法受限较多，难以满足现代化工程和科研的问题大规模、高时效性和复杂NP问题的要求。与传统方法相比，进化方法对问题模型要求低，求解效率高，并且表现出高度并行、自组织、自适应等优点，已经应用在许多工业应用和研究领域。
在求解动态多目标优化问题的进化算法中，最简单的方法是保持种群多样性。Deb提出的DNSGA-II(Dynamic multi-objective optimization and decision-making usingmodified NSGA-II)采用部分随机初始化或是随机变异增加种群在变化环境中的适应性(K.Deb,U B.Rao N,S.Karthik.Dynamic multiobjective optimization and decision-making using modified NSGA-II:a case study on hydro-thermal powerscheduling.In:Proceedings of the 4th International Conference on EvolutionaryMulti-Criterion Optimization.Matsushima,Japan:Springer,2007.803-817.)Azevedo采用三种移民策略初始化环境变化后的种群(C.R.B.Azevedo,A.F.R.Araujo.Generalizedimmigration schemes for dynamic evolutionary multiobjective optimization.In:Proceedings of IEEE Congress on Evolutionary Computation.New Orleans,LA,USA:IEEE,2011:2033–2040.)；尚荣华采用多种免疫策略相结合的方法初始化环境变化后的种群进行(R.H.Shang,L.C.Jiao,M.G.Gong,W.P.Ma.An immune clonal algorithm fordynamic multi-objective optimization.Journal of Software,2007,18(11):2700-2711.)。由于对动态环境的变化趋势未知，这种方法凭借尝试性探索未知区域以保证在变化后的存有优势个体。其优势是能够应对各种环境变化，缺点是难以在环境变化后延续环境变化前的搜索优势，因此这种方法表现较强的环境适应性和较差的搜索优势保持能力。
相比与早期以保持种群多样性应对环境变化的方法，研究者们开始利用多次环境变化后的历史信息，通过统计分析多次环境变化前的非支配解集预测下一时刻环境变化的种群位置。通过统计分析多次环境变化前的非支配解集预测下一时刻环境变化的种群位置。
这种思想主要有两种求解思路：记忆策略和预测策略。记忆策略存储大量非支配解集信息，通过规律预测下一时刻种群位置，这种方法对于解决“短周期性”的动态问题效果较好，因为“周期性”可以通过历史信息描述，“短”表示存储空间少。
但是这种策略在处理环境变化频率高或是非线性时变问题时，表现出较多的存储空间消耗大和预测不准确。相对于记忆策略，预测策略通过统计分析历史信息，利用预测理论(如线性回归模型、自回归模型等)预测种群可能迁移的方向。Hatzakis提出前向预测方法(Feed-forward Prediction Strategy，FPS)(I.Hatzakis,D.Wallace.Dynamic multi-objective optimization with evolutionary algorithms:a forward-lookingapproach.In:Proceedings of the 8th Annual Conference on Genetic andEvolutionary Computation.Washington,USA:ACM,2006.1201-1208.)，该算法使用自回归模型预测非支配解集迁移位置，由于FPS历史信息统计分析不完全，预测效果不佳。Zhou提出了种群预测策略(Population Prediction Strategy，PPS)(A.M.Zhou,Y.C.Jin,Q.F.Zhang.A population prediction strategy for evolutionary dynamicmultiobjective optimization.IEEE Transactions on Cybernetics,2014,44(1):40-53)，使用自回归模型预测预测种群中心迁移位置，然后采用形状估计平移整个种群。PPS与FPS相比有两个优点，一是历史信息的进一步处理，即采用种群中心位置进行预测；二是形状估计的方法比种群个体逐个预测迁移的效果要好。但是，自回归模型的策略有一个根本上的弊端，即需要大量的统计信息构建模型。如果多次预测偏差增加，那么预测误差会被放大，当环境变化规律发生变化时，难以较快适应。
自回归模型是一种很常用的预测规律性变化问题的模型，但具有响应慢、统计数据量大等缺点，线性模型虽然简单，通过简单的多样性保持策略能够有效弥补自回归模型的缺点。Wu提出定向预测策略(Directed Search Strategy，DSS)(Y.Wu,Y.Jin,X.Liu.Adirected search strategy for evolutionary dynamic multiobjetiveoptimization.Soft Computing,2015,19(11):3221-3235.)，使用种群中心预测和横向搜索两种策略处理动态问题，其中种群中心预测采用线性预测方法，这种方法具有历史信息少的优点，比多元线性回归环境适应能力更快。Rong分割最优前沿并逐个采用线性模型预测变化(Miao Rong,Dunwei Gong,Yong Zhang,Yaochu Jin,WitoldPedrycz.Multidirectional prediction approach for dynamic multiobjectiveoptimization problems.In:Intelligent Computing Methodologies.ICIC2016.Lecture Notes in Computer Science,vol 9773,Springer,Cham.)。Li采用自回归模型预测最优前沿的边界点、拐点等关键点预测，然后使用线性模型预测非支配解位置(Qingya Li,Juan Zou,Shengxiang Yang,Jinhua Zheng,Gan Ruan.A predictivestrategy based on special points for evolutionary dynamic multi-objectiveoptimization,Soft Computing,2018,(1):1-17.https://doi.org/10.1007/s00500-018-3033-0.)。Ruan采用了线性模型模型预测最优前沿位置(Gan Ruan,Guo Yu,Jinhua Zheng,Juan Zou,Shengxiang Yang.The effect of diversity maintenance on prediction indynamic multi-objective optimization.Applied Soft Computing,2017(58):631–647)，在多样性保持方面，将上一代的极值点与线性模型结合预测种群变化。但值得注意的是，线性模型虽然简单，但是求解递增递减或是更加复杂变化的动态问题中始终存在预测误差，因此上述现有技术中公开的内容均采用多样性保持的方法弥补预测误差。
发明内容
本发明的目的是提供一种基于分割多向预测策略的动态多目标优化方法，它针对线性模型预测误差弥补不足的问题，能够更好的预测最优前沿的变化，保证对最优前沿凹凸性的分布变化的预测，有效弥补方向预测的距离误差。
本发明的技术方案如下：基于分割多向预测策略的动态多目标优化方法，它包括如下步骤：
(1)对动态多目标问题进行描述；
(2)分割多向预测。
所述的步骤(1)中的动态多目标问题描述如下：
Figure BDA0002382556920000051
其中，x＝(x1,...,xn)T是n维决策空间中的决策变量，t为时间变量，g(x,t)和h(x,t)分别是不等式约束和等式约束，(f1(x,t),f2(x,t),L,fm(x,t))T是动态多目标优化问题的目标函数向量，评价函数F(x,t)为决策空间到目标空间的映射，s.t.表示约束条件。
所述的步骤(2)中的分割多向预测首先将最优前沿分割成多个片段，依据分割结果对决策空间的种群进行划分，然后在每个种群中选择部分个体采用偏角增强搜索策略寻找最优前沿变化方向，最后采用偏角增强搜索对最优前沿可能偏移的位置进行补充搜索。
所述的步骤(2)具体包括如下步骤：
(a)进行种群分割；
(b)定向云预测；
(c)偏角增强搜索；
(d)环境检测；
(e)进行分割多向云预测策略计算。
所述的步骤(a)进行种群分割包括，在PF中，选择一个边界点作为第一个关键点，然后计算每个点到此边界点的距离，选择距离最大点作为第二关键点；计算其他个体距离第二关键点的距离，选择一个点距离两个关键点距离之和最大的点作为第三关键点，依次类推选择m+1个关键点，m为目标个数，每个个体选择距离最近的关键点，构成m+1个片段，依据PF的分割结果划分多个种群。
所述的步骤(b)定向云预测包括，
种群规模为N，第i个种群Popi含有Ki个个体，对于t时刻子种群Popi中心描述如下：
Figure BDA0002382556920000061
其中，
Figure BDA0002382556920000062
表示种群所有个体，第k个个体为
Figure BDA0002382556920000063
n为决策空间维度，Ci(t)表示t时刻种群中心位置，|·|表示集合的势；
利用t时刻和t-1时刻的种群中心点位置预测t+1时刻的预测种群迁移向量di(t)和两次迁移误差Δ(t)如下
di(t)＝Ci(t)-Ci(t-1) (3)
Δ(t)＝di(t)-di(t-1) (4)
使用正态云模型预测种群迁移位置，种群移动方向为期望，移动向量的欧氏距离di(t)为熵，两次种群移动方向的偏差Δ(t)作为超熵，使用期望、熵和超熵构建正态云发生器，首先以Δ(t)为期望，||Δ(t)||/n为标准差生成正态随机向量En'～N(Δ(t),||Δ(t)||2/n2)，其中En'＝(En1',...,Enn')；然后以di(t)为期望，En'为标准差生成正态随机向量v1～N(di(t),En'2)，环境变化后个体的预测位置y表示如下：
y＝p+v1 (5)
其中，p为环境变化前个体位置，v1是预测方向。
所述的步骤(c)偏角增强搜索包括，
构造一个垂直于di(t)的随机向量，生成[-1,1]范围内的随机向量r＝(r1,...,rn)，任意选取r的第j维度的赋值如式(6)，
Figure BDA0002382556920000071
偏角增强搜索方向向量e(t)＝(e1,...,en)计算如下
Figure BDA0002382556920000072
式中，θ为偏角大小，表示可能的搜索范围，计算如下：
Figure BDA0002382556920000073
在确定偏角增强搜索方向向量e(t)＝(e1,...,en)后，使用正态云模型对个体进行偏差角度搜索，以ei(t)为期望，Δ(t)为标准差差生成正态随机向量En*～N(di(t),Δ(t)2)，其中En*＝(En1*,...,Enn*)；然后以ei(t)为期望，En*为标准差生成正态随机向量v2～N(ei(t),En*2)，偏差角度搜索对个体的预测位置y*如下：
y*＝y+v2 (9)
其中，v2是偏差角度搜索后的预测方向。
所述的步骤(d)中的环境敏感性因子ε(t)计算如下：
Figure BDA0002382556920000081
其中，H为从种群中随机抽取的个体的个数，F(xj,t)表示个体xj在t时刻的目标函数向量，环境监测抽取种群的比例为5％。
所述的步骤(e)进行分割多向云预测策略计算包括：
步骤1：随机初始化种群；
步骤2：利用式(10)
Figure BDA0002382556920000082
检测环境是否变化，如果发生变化转步骤3；否则转步骤8；
步骤3：判断d(t-1)是否为0，如果d(t-1)≠0，跳转步骤5；否则转步骤4；
步骤4：随机选择ζ×N个体进化，令d(t-1)＝d(t)；
步骤5：将种群分割m+1部分，对每个子种群Popi，利用式(2)计算种群中心，
Figure BDA0002382556920000083
根据式(3)
di(t)＝Ci(t)-Ci(t-1) (3)
计算时间t的种群移动方向d(t)，使用2进制联赛法选择L1×N个体，使用正态云模型预测预测位置；
步骤6：使用2进制联赛法选择N×(1-L1)个个体，根据式(6)-(8)
Figure BDA0002382556920000084
偏角增强搜索方向向量e(t)＝(e1,...,en)计算如下
Figure BDA0002382556920000091
式中，θ为偏角大小，表示可能的搜索范围，计算如下：
Figure BDA0002382556920000092
计算这些个体的偏差角度搜索向量，使用云模型预测位置；
步骤7：对新生成个体进行边界检测；
步骤8：计算非支配排序和拥挤距离保留前N个体；
步骤9：迭代终止条件判断，若满足，跳转步骤10；否则转步骤2；
步骤10：输出种群PS。
所述的步骤7对新生成个体进行边界检测，对超出决策空间的个体进行修复：
Figure BDA0002382556920000093
其中，xi表示个体x预测前的第i维，yi为预测后的个体第i维位置，i＝{1,...,n}，ai和bi分别决策变量第i维的下界和上界。
本发明的有益效果在于：首先将搜索到的最优前沿进行分割，依据最优前沿的分割结果划分种群，对种群每个部分进行线性预测，借鉴云模型对于不确定时间的描述，用熵和超熵弥补预测误差，针对动态问题中可能发生的突发性非线性变化，采用偏角增强搜索策略保证预测过程中种群的多样性。
附图说明
图1为定向云搜索示意图；
图2为偏角增强搜索示意图；
图3为4种算法在JY1测试函数中IGD指标随时间变化曲线图；
图4为4种算法在JY2测试函数中IGD指标随时间变化曲线图；
图5为4种算法在JY3测试函数中IGD指标随时间变化曲线图；
图6为4种算法在JY4测试函数中IGD指标随时间变化曲线图；
图7为4种算法在JY5测试函数中IGD指标随时间变化曲线图；
图8为4种算法在JY6测试函数中IGD指标随时间变化曲线图；
图9为4种算法在JY7测试函数中IGD指标随时间变化曲线图；
图10为4种算法在JY8测试函数中IGD指标随时间变化曲线图。
图1中，d(t)为定向预测方向d'(t)为云预测可能方向，即定向云预测是以方向d(t)为主要搜索方向，并以一定的概率对上一次偏移方向Δ(t)进行搜索。
具体实施方式
下面结合附图及具体实施例对本发明作进一步详细说明。
基于分割多向预测策略的动态多目标优化方法，具体包括如下步骤：
(1)对动态多目标优化问题进行描述
动态多目标优化问题描述如下：
Figure BDA0002382556920000101
其中，x＝(x1,...,xn)T是n维决策空间中的决策变量，t为时间变量，g(x,t)和h(x,t)分别是不等式约束和等式约束，(f1(x,t),f2(x,t),L,fm(x,t))T是动态多目标优化问题的目标函数向量，评价函数F(x,t)为决策空间到目标空间的映射，s.t.表示约束条件，m为目标个数。
(2)分割多向预测
分割多向预测方法首先将最优前沿分割成多个片段，依据分割结果对决策空间的种群进行划分，然后在每个种群中选择部分个体采用偏角增强搜索方法寻找最优前沿变化方向，最后采用偏角增强搜索对最优前沿可能偏移的位置进行补充搜索。
具体包括如下步骤：
(a)进行种群分割
动态多目标优化问题中，最优前沿可能产生偏转和形变，为了更准确的预测Pareto最优前沿(Pareto-optimal front，PF)变化的形式，将PF分割部分片段，分别对每个片段进行预测，这种方法与种群中心线性预测相比能够更精确的判断PF形变和非线性偏移。
首先，在PF中，选择一个边界点作为第一个关键点，然后计算每个点到此边界点的距离，选择距离最大点作为第二关键点。计算其他个体距离第二关键的距离，选择一个点距离两个关键点距离之和最大的点作为第三关键点，依次类推选择m+1个关键点(m为目标个数)。每个个体选择距离最近的关键点，构成m+1个片段，依据PF的分割结果划分多个种群。
这种方法计算简单，复杂度低。每次选择一个关键点需要时间复杂度O(N)，N为种群规模，此方法计算复杂度为O(N(m+2)/2)＝O(Nm)。而聚类方法计算复杂度为O(N2)，分割方法能够更简单的对种群分割，计算复杂度低。
(b)定向云预测
种群规模为N，第i个种群Popi含有Ki个个体，对于t时刻子种群Popi中心描述如下：
Figure BDA0002382556920000111
其中，
Figure BDA0002382556920000112
表示种群所有个体，第k个个体为
Figure BDA0002382556920000113
n为决策空间维度，Ci(t)表示t时刻种群中心位置，|·|表示集合的势。
如图1所示，利用t时刻和t-1时刻的种群中心点位置预测t+1时刻的预测种群迁移向量di(t)和两次迁移误差Δ(t)如下
di(t)＝Ci(t)-Ci(t-1) (3)
Δ(t)＝di(t)-di(t-1) (4)
使用正态云模型预测种群迁移位置。设种群移动方向为期望，移动向量的欧氏距离di(t)为熵，两次种群移动方向的偏差Δ(t)作为超熵，使用期望、熵和超熵构建正态云发生器。首先以Δ(t)为期望，||Δ(t)||/n为标准差生成正态随机向量En'～N(Δ(t),||Δ(t)||2/n2)，其中En'＝(En1',...,Enn')；然后以di(t)为期望，En'为标准差生成正态随机向量v1～N(di(t),En'2)。环境变化后个体的预测位置y表示如下：
y＝p+v1 (5)
其中，p为环境变化前个体位置，v1是预测方向。
(c)偏角增强搜索
定向云预测中包含了线性预测的误差补偿，但这种补偿仅针对渐进规律性变化有效。如果动态问题呈现出反向往复或是非渐进变化，那么定向云预测的方向会与动态问题变化方向完全相反或是垂直。针对这种问题，本发明提出偏角增强搜索，即随机选取一部分个体，以一定的角度向各个可能的方向进行搜索。
如图2所示，首先构造一个垂直于di(t)的随机向量，生成[-1,1]范围内的随机向量r＝(r1,...,rn)，任意选取r的第j维度的赋值如式(6)。
Figure BDA0002382556920000121
偏角增强搜索方向向量e(t)＝(e1,...,en)计算如下。
Figure BDA0002382556920000122
式中，θ为偏角大小，表示可能的搜索范围，计算如下：
Figure BDA0002382556920000131
在确定偏角增强搜索方向向量e(t)＝(e1,...,en)后，使用正态云模型对个体进行偏差角度搜索。以ei(t)为期望，Δ(t)为标准差差生成正态随机向量En*～N(di(t),Δ(t)2)，其中En*＝(En1*,...,Enn*)；然后以ei(t)为期望，En*为标准差生成正态随机向量v2～N(ei(t),En*2)。偏差角度搜索对个体x的预测位置y*如下：
y*＝y+v2 (9)
其中，v2是偏差角度搜索后的预测方向。
(d)环境检测
算法对于环境的敏感性十分重要，敏感性过度或是欠缺都会降低动态多目标优化问题(DMOP)的求解效率。此外，DMOP的每个目标函数不一定同时发生变化，不同目标函数变化的幅度也不相同。因此，本发明综合考虑每个目标函数值的变化并进行归一化处理，环境检测通过计算环境敏感性因子ε(t)来实现，具体计算如下：
Figure BDA0002382556920000132
其中，H为从种群中随机抽取的个体的个数，随机抽取主要是减少环境检测对算法计算代价的消耗；F(xj,t)表示个体xj在t时刻的目标函数向量，F(xj，t-1)表示个体xj在t-1时刻的目标函数向量，F(xi，t)表示个体xi在t时刻的目标函数向量，F(xj，t-1)表示个体xi在t-1时刻的目标函数向量。一般的，环境监测抽取种群的比例为5％。
(e)进行分割多向云预测策略(Segment Cloud Prediction Strategy,SCPS)计算
SCPS算法在基本的动态MOEA算法框架内进行迭代。基本的动态MOEA算法框架主要包括两部分，动态预测和静态MOEA搜索。由于本发明主要研究DMOEA的预测性能，因此，选择经典的NSGA-II作为静态MOEA搜索。
SCPS算法详细描述如下：
输入：历史信息未收集充足时随机初始化种群比例为ζ，实施中心定向预测种群比例L1，种群规模N，环境变化最终时间Tmax，t:＝0，d(t-1):＝0。
输出：Pareto最优解集(Pareto-optimal set，PS)。
步骤1：随机初始化种群；
步骤2：利用式(10)检测环境是否变化，
Figure BDA0002382556920000141
如果发生变化转步骤3；否则转步骤8；
步骤3：判断d(t-1)是否为0，如果d(t-1)≠0，跳转步骤5；否则转步骤4；
步骤4：随机选择ζ×N个体进化，令d(t-1)＝d(t)；
步骤5：将种群分割m+1部分，对每个子种群Popi，利用式(2)计算种群中心，
Figure BDA0002382556920000142
根据式(3)计算时间t的种群移动方向d(t)，
di(t)＝Ci(t)-Ci(t-1) (3)
使用2进制联赛法选择L1×N个体，使用正态云模型预测预测位置；
步骤6：使用2进制联赛法选择N×(1-L1)个个体，根据式(6)-(8)计算这些个体的偏差角度搜索向量，
Figure BDA0002382556920000151
偏角增强搜索方向向量e(t)＝(e1,...,en)计算如下。
Figure BDA0002382556920000152
式中，θ为偏角大小，表示可能的搜索范围，计算如下：
Figure BDA0002382556920000153
使用云模型预测位置；
步骤7：对新生成个体进行边界检测；
步骤8：计算非支配排序和拥挤距离保留前N个体；
步骤9：迭代终止条件判断，若满足，跳转步骤10；否则转步骤2；
步骤10：输出种群PS。
SCPS算法中的基于云模型的一步预测步骤5和偏差角度搜索步骤6分别随机选择K1×N和N×(1-K1)个个体进行预测。由于预测的个体有可能超出决策空间，因此增加步骤7对新生成个体进行边界检测，对超出决策空间的个体进行修复：
Figure BDA0002382556920000154
其中，xi表示个体x预测前的第i维，yi为预测后的个体第i维位置，i＝{1,...,n}，ai和bi分别决策变量第i维的下界和上界。
本发明的效果说明如下：
(1)测试函数
文献(Shouyong Jiang,Shengxiang Yang.Evolutionary dynamicmultiobjective optimization:bencmarks and algorithm comparisons.IEEETransactions on Cybernetics,2017,47(1):198-211.)构造了一个新的动态测试函数生成器JY，基于JY产生的动态测试函数与很多实际工程问题相关，如受温室系统、水利发电调度、路线导引调度等问题。其中的测试函数除了具有一般的PF凸凹转换、动态问题三种类型等特点以外，还包含决策变量非单调相关(non-monotonic dependencies)、PF离散、multi-modal等特点。将基于JY生成的八个测试函数(JY1-JY8)作为本发明的测试函数，八个测试函数JY1-JY8的区别在于PS和PF随时间的变化规律，能够较好的分析SCPS算法的性能。所有的函数动态变化都是依据变化时间t而确定的，时间t的计算如下：
Figure BDA0002382556920000161
其中，nt为变化强度，τt为环境变化频率，τ为迭代次数。
为了更好的测试本发明提出算法在动态问题寻优方面的性能，设置3组测试函数的环境变化频率和频度，(n,τ)分别为(5,10)、(10,10)、(10,20)。测试的对比算法选择MOEA/D(Qingfu Zhang,Hui Li.MOEA/D:A multiobjective evolutionary algorithmbased on decomposition.IEEE Transactions on Evolutionary Computation.2007,11(6):712-731)，PPS(A.M.Zhou,Y.C.Jin,Q.F.Zhang.A population prediction strategyfor evolutionary dynamic multiobjective optimization.IEEE Transactions onCybernetics,2014,44(1):40-53)，MDP(Miao Rong,Dunwei Gong,Yong Zhang,YaochuJin,Witold Pedrycz.Multidirectional prediction approach for dynamicmultiobjective optimization problems.In:Intelligent ComputingMethodologies.ICIC 2016.Lecture Notes in Computer Science,vol 9773,Springer,Cham.)与SCPS进行对比实验，所有对比算法的种群规模N＝200，进化终止时间Tmax＝10。
(i)MOEA/D：T＝20；
(ii)PPS：种群中心点保留数量M＝23，使用p元线性回归模型，p＝3；
(iii)SCPS：ζ＝0.2，预测模型选择个体数量K1＝0.5×N；
动态多目标进化算法的度量指标非常多，选择反向世代距离(Invertedgenerational distance，IGD)作为每一次迭代的评估标准，使用修正IGD(Modified IGD，MIGD)作为每种算法在每个测试函数运行多次的综合评价标准。
Figure BDA0002382556920000171
其中，P*(t)表示时刻t的均匀分布的理想PF解集；P(t)表示算法求解出的PF解集；
Figure BDA0002382556920000172
表示个体x与解集P(t)的距离；|P*(t)|表示集合P*(t)的势。
MIGD用于评价算法在测试函数中运行一段时间的平均IGD，定义如下：
Figure BDA0002382556920000173
其中，T表示一组离散的时间点，|T|表示T的势。
表1是4种动态多目标进化方法在8个测试函数中运行20次的平均MIGD指标结果，黑体加粗表示最优数值。从表1中可以看出，SCPS具有在8个动态测试问题中表现出较优的寻优性能，仅在JY4测试问题(n,τ)＝(5,10)的情况下，性能略逊于PPS。在所有测试问题中，四种方法在JY1-JY5和JY8问题寻优能力较强，在MIGD指标均达到10-2量级，证明了四种方法都能较好的追踪动态前沿。JY6是一个多峰的PS和PF都随时间变化的TypeIII型动态问题，不仅它的最优解的数量在变化，最优解的分布也持续变化，虽然SCPS在此问题的表现优于其他三个算法，但在MIGD指标上表现并不令人满意。JY7也是一个多峰问题，它的PF的凸凹分布持续变化，但是JY7比JY6相对简单，因为它的局部最优数量是固定的。因此四种测试函数在JY7的表现上比JY6好一点。但是观察四种算法在JY7函数中MIGD指标的标准差可以看出，SCPS相比其他三种具有较好的稳定性，且求解结果精确度更高。
为了进一步分析四种算法的动态寻优性能，选择(n,τ)＝(10,20)情况下的8组测试函数分析算法的IGD指标随时间变化曲线。图3-图10为4种算法在测试函数中IGD指标随时间变化曲线。从图中可以看出MOEA/D算法尽管在静态问题上具有较好的寻优性能，但是由于没有动态预测能力，因此有限的时间内对动态问题的寻优能力不足。在JY2和JY5问题上，PPS的性能明显由于MDP，但在JY7和JY8问题上PPS的性能不如MDP。尤其JY7，PPS的预测明显出现了较大的误差，且误差持续增大。在8个测试函数中，SCPS明显由于其他3个方法。
表1.四种方法在8个测试函数中的MIGD指标
Figure BDA0002382556920000181
综合均值和IGD指标走势图对比结果分析，可以看出，本发明提出的方法性能稳定且具有较好的预测能力，能够较好地预测出分布均匀且贴近上一时刻位置的种群。

Claims (2)

1.基于分割多向预测策略的动态多目标优化方法，其特征在于，它包括如下步骤：
(1)对动态多目标问题进行描述；
(2)分割多向预测；
所述的步骤(1)中的动态多目标问题描述如下：
Figure FDA0002760508020000011
其中，x＝(x1,...,xn)T是n维决策空间中的决策变量，g(x,t)和h(x,t)分别是不等式约束和等式约束，t为时间变量，(f1(x,t),f2(x,t),…,fm(x,t))T是动态多目标优化问题的目标函数向量，评价函数F(x,t)为决策空间到目标空间的映射，m为目标个数，s.t.表示约束条件；
所述的步骤(2)中的分割多向预测首先将最优前沿分割成多个片段，依据分割结果对决策空间的种群进行划分，然后在每个种群中选择部分个体采用偏角增强搜索策略寻找最优前沿变化方向，最后采用偏角增强搜索对最优前沿可能偏移的位置进行补充搜索；
所述的步骤(2)具体包括如下步骤：
(a)进行种群分割；
(b)定向云预测；
(c)偏角增强搜索；
(d)环境检测；
(e)进行分割多向云预测策略计算；
所述的步骤(a)进行种群分割包括，在PF中，选择一个边界点作为第一个关键点，然后计算每个点到此边界点的距离，选择距离最大点作为第二关键点；计算其他个体距离第二关键点的距离，选择一个点距离两个关键点距离之和最大的点作为第三关键点，依次类推选择m+1个关键点，m为目标个数，每个个体选择距离最近的关键点，构成m+1个片段，依据PF的分割结果划分多个种群；
所述的步骤(b)定向云预测包括，
种群规模为N，第i个种群Popi含有Ki个个体，对于t时刻子种群Popi中心描述如下：
Figure FDA0002760508020000021
其中，第k个个体为
Figure FDA0002760508020000022
n为决策空间维度，Ci(t)表示t时刻种群中心位置，|·|表示集合的势；
利用t时刻和t-1时刻的种群中心点位置预测t时刻的预测种群迁移向量di(t)和两次迁移误差Δ(t)如下
di(t)＝Ci(t)-Ci(t-1) (3)
Δ(t)＝di(t)-di(t-1) (4)
使用正态云模型预测种群迁移位置，种群迁移向量为期望，迁移向量di(t)的欧氏距离为熵，两次种群迁移向量的偏差Δ(t)作为超熵，使用期望、熵和超熵构建正态云发生器，首先以Δ(t)为期望，||Δ(t)||/n为标准差生成正态随机向量En'～N(Δ(t),||Δ(t)||2/n2)，其中En'＝(En1',...,Enn')；然后以di(t)为期望，En'为标准差生成正态随机向量v1～N(di(t),En'2)，环境变化后个体的预测位置y表示如下：
y＝p+v1 (5)
其中，p为环境变化前个体位置，v1是预测方向；
所述的步骤(c)偏角增强搜索包括，
构造一个垂直于di(t)的随机向量，生成[-1,1]范围内的随机向量r＝(r1,...,rn)，任意选取r的第j维度的赋值如式(6)，
Figure FDA0002760508020000031
偏角增强搜索方向向量e(t)＝(e1,...,en)计算如下
Figure FDA0002760508020000032
式中，θi为偏角大小，表示可能的搜索范围，计算如下：
Figure FDA0002760508020000033
其中，di(t)为t时刻的预测种群迁移向量，di(t-1)为t-1时刻的预测种群迁移向量，di(t-2)为t-2时刻的预测种群迁移向量；
在确定偏角增强搜索方向向量e(t)＝(e1,...,en)后，使用正态云模型对个体进行偏差角度搜索，以ei(t)为期望，Δ(t)为标准差差生成正态随机向量En*～N(di(t),Δ(t)2)，其中En*＝(En1*,...,Enn*)；然后以ei(t)为期望，En*为标准差生成正态随机向量v2～N(ei(t),En*2)，偏差角度搜索对个体的预测位置y*如下：
y*＝y+v2 (9)
其中，v2是偏差角度搜索后的预测方向；
所述的步骤(d)中的环境敏感性因子ε(t)计算如下：
Figure FDA0002760508020000034
其中，H为从种群中随机抽取的个体的个数，F(xj,t)表示个体xj在t时刻的目标函数向量，环境监测抽取种群的比例为5％；
所述的步骤(e)进行分割多向云预测策略计算包括：
步骤1：随机初始化种群；
步骤2：利用式(10)
Figure FDA0002760508020000041
H为从种群中随机抽取的个体的个数，F(xj,t)表示个体xj在t时刻的目标函数向量，检测环境是否变化，如果发生变化转步骤3；否则转步骤8；
步骤3：判断d(t-1)是否为0，如果d(t-1)≠0，跳转步骤5；否则转步骤4；
步骤4：随机选择ζ×N个个体进化，令d(t-1)＝d(t)，N为种群规模，ζ为历史信息未收集充足时随机初始化种群比例；
步骤5：将种群分割m+1部分，对每个子种群Popi，利用式(2)计算种群中心，
Figure FDA0002760508020000042
根据式(3)
di(t)＝Ci(t)-Ci(t-1) (3)
计算时间t的预测种群迁移向量di(t)，使用2进制联赛法选择L1×N个个体，使用正态云模型预测预测位置，L1为实施中心定向预测种群比例；
步骤6：使用2进制联赛法选择N×(1-L1)个个体，根据式(6)-(8)
Figure FDA0002760508020000043
ri(t)为一个垂直于di(t)的随机向量，
偏角增强搜索方向向量e(t)＝(e1,...,en)计算如下
Figure FDA0002760508020000044
式中，θi为偏角大小，表示可能的搜索范围，计算如下：
Figure FDA0002760508020000045
di(t-1)为t-1时刻的预测种群迁移向量，计算这些个体的偏差角度搜索向量，使用云模型预测位置；
步骤7：对新生成个体进行边界检测；
步骤8：计算非支配排序和拥挤距离保留前N个个体；
步骤9：迭代终止条件判断，若满足，跳转步骤10；否则转步骤2；
步骤10：输出种群PS。
2.如权利要求1所述的基于分割多向预测策略的动态多目标优化方法，其特征在于：所述的步骤7对新生成个体进行边界检测，对超出决策空间的个体进行修复：
Figure FDA0002760508020000051
其中，xi表示个体x预测前的第i维，yi为预测后的个体第i维位置，i＝{1,...,n}，ai和bi分别决策变量第i维的下界和上界。
CN202010087473.5A 2020-02-11 2020-02-11 基于分割多向预测策略的动态多目标优化方法 Active CN111311638B (zh)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN202010087473.5A CN111311638B (zh) 2020-02-11 2020-02-11 基于分割多向预测策略的动态多目标优化方法

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN202010087473.5A CN111311638B (zh) 2020-02-11 2020-02-11 基于分割多向预测策略的动态多目标优化方法

Publications (2)

Publication Number Publication Date
CN111311638A CN111311638A (zh) 2020-06-19
CN111311638B true CN111311638B (zh) 2020-12-08

Family

ID=71148929

Family Applications (1)

Application Number Title Priority Date Filing Date
CN202010087473.5A Active CN111311638B (zh) 2020-02-11 2020-02-11 基于分割多向预测策略的动态多目标优化方法

Country Status (1)

Country Link
CN (1) CN111311638B (zh)

Families Citing this family (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN112052598B (zh) * 2020-09-14 2024-06-21 中国人民解放军国防科技大学 一种基于偏好moea的卫星地面站资源多目标优化方法
CN112446097B (zh) * 2020-12-03 2023-08-29 武汉第二船舶设计研究所(中国船舶重工集团公司第七一九研究所) 一种蒸汽发生器体积和负荷的多目标优化方法
CN115062882A (zh) * 2022-08-19 2022-09-16 湖南师范大学 一种求解大规模工业过程流量传感器最优布局的进化方法
CN115470704B (zh) * 2022-09-16 2023-07-21 烟台大学 一种动态多目标优化方法、装置、设备和计算机可读介质
CN117765541A (zh) * 2024-01-10 2024-03-26 北京中卡信安电子设备有限公司 一种通行证图像对齐方法及装置

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN103064289A (zh) * 2012-12-19 2013-04-24 华南理工大学 一种垃圾发电厂多目标运行优化及协调的控制方法及装置
CN106228232A (zh) * 2016-07-07 2016-12-14 淮北师范大学 一种基于模糊推理种群预测策略的动态多目标教学优化方法
CN107506914A (zh) * 2017-08-13 2017-12-22 天津大学 计及分布式电源渗透率变化的变电站动态扩展规划方法

Family Cites Families (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6847854B2 (en) * 2001-08-10 2005-01-25 Rockwell Automation Technologies, Inc. System and method for dynamic multi-objective optimization of machine selection, integration and utilization
US7797062B2 (en) * 2001-08-10 2010-09-14 Rockwell Automation Technologies, Inc. System and method for dynamic multi-objective optimization of machine selection, integration and utilization
CN103580020B (zh) * 2013-03-07 2016-05-25 长沙理工大学 一种基于NSGA-II和Look-ahead的含风电场电力系统多目标动态优化调度方法
CN105719091B (zh) * 2016-01-25 2019-05-10 大连理工大学 一种梯级水电站群并行多目标优化调度方法
CN105740895A (zh) * 2016-01-28 2016-07-06 长春师范大学 一种基于动态多目标优化的图像分割方法及系统
US20190317760A1 (en) * 2018-04-17 2019-10-17 The Regents Of The University Of Michigan Interactive And Dynamic Search Based Approach To Software Refactoring Recommendations
CN109767438B (zh) * 2019-01-09 2021-06-08 电子科技大学 一种基于动态多目标优化的红外热图像缺陷特征识别方法
CN110138000B (zh) * 2019-06-11 2022-08-16 河海大学 基于鲁棒多目标优化算法的混合直流输电系统控制参数优化方法

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN103064289A (zh) * 2012-12-19 2013-04-24 华南理工大学 一种垃圾发电厂多目标运行优化及协调的控制方法及装置
CN106228232A (zh) * 2016-07-07 2016-12-14 淮北师范大学 一种基于模糊推理种群预测策略的动态多目标教学优化方法
CN107506914A (zh) * 2017-08-13 2017-12-22 天津大学 计及分布式电源渗透率变化的变电站动态扩展规划方法

Also Published As

Publication number Publication date
CN111311638A (zh) 2020-06-19

Similar Documents

Publication Publication Date Title
CN111311638B (zh) 基于分割多向预测策略的动态多目标优化方法
Shi et al. Novel L1 regularized extreme learning machine for soft-sensing of an industrial process
Peng et al. Novel prediction and memory strategies for dynamic multiobjective optimization
Zhang et al. Fast covariance matching with fuzzy genetic algorithm
CN114897129A (zh) 一种基于日相似聚类与Kmeans-GRA-LSTM的光伏电站短期功率预测方法
Elhariri et al. H-ahead multivariate microclimate forecasting system based on deep learning
Shi et al. Dynamic barycenter averaging kernel in RBF networks for time series classification
Li et al. Zero-shot neural architecture search: Challenges, solutions, and opportunities
Lei et al. A hybrid regularization semi-supervised extreme learning machine method and its application
CN105913078A (zh) 改进自适应仿射传播聚类的多模型软测量方法
CN116187835A (zh) 一种基于数据驱动的台区理论线损区间估算方法及系统
CN117575672A (zh) 一种基于时空特征迁移学习的行业电量预测方法、装置
Behera et al. GAN-based multi-task learning approach for prognostics and health management of IIoT
Wang et al. Otsu multi-threshold image segmentation algorithm based on improved particle swarm optimization
Wu et al. A dynamic multi-objective evolutionary algorithm based on prediction
Alagarsundaram et al. A Short-Term Load Forecasting model using Restricted Boltzmann Machines and Bi-directional Gated Recurrent Unit
Xie et al. An efficient fuzzy stream clustering method based on granular-ball structure
Liu et al. Research on soft sensor modeling method for complex chemical processes based on local semi-supervised selective ensemble learning
Rajkumar et al. Weather forecasting using fuzzy neural network (FNN) and hierarchy particle swarm optimization algorithm (HPSO)
Liu et al. Cascading model based back propagation neural network in enabling precise classification
CN116304983A (zh) 一种数据驱动的层次递归加权传感器信息融合识别方法
Berikov et al. Solving weakly supervised regression problem using low-rank manifold regularization
Vahidipour et al. Comparing weighted combination of hierarchical clustering based on Cophenetic measure
Ma et al. Multi-spatial information joint guidance evolutionary algorithm for dynamic multi-objective optimization with a changing number of objectives
Zhang et al. Adaptive truncation technique for constrained multi-objective optimization

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant