连续型进化算法首达时间分析的更新理论模型  

Renewal Theory Model of First Hitting Time Analysis for Continuous Evolutionary Algorithms

作　　者：周珍胜 王林[2] 冯夫健 谭棉[1,2] 何兴 张再军[3] ZHOU Zhensheng;WANG Lin;FENG Fujian;TAN Mian;HE Xing;ZHANG Zaijun(School of Data Sciences and Information Engineering,Guizhou Minzu University,Guiyang 550025;Key Laboratory of Pattern Recognition and Intelligent Systems of Guizhou Province,Guizhou Minzu University,Guiyang 550025;School of Mathematics and Statistics,Qiannan Normal University for Nationalities,Duyun 558000)

机构地区：[1]贵州民族大学数据科学与信息工程学院,贵阳550025 [2]贵州民族大学贵州省模式识别与智能系统重点实验室,贵阳550025 [3]黔南民族师范学院数学与统计学院,都匀558000

出　　处：《模式识别与人工智能》2023年第10期918-930,共13页Pattern Recognition and Artificial Intelligence

基　　金：国家自然科学基金项目(No.62241206);贵州省科技计划项目(No.黔科合基础-ZK[2022]一般195,黔科合基础-ZK[2023]一般143,黔科合基础-ZK[2022]一般550);贵州省教育厅自然科学研究项目(No.黔教技[2023]061号,黔教技[2023]012号,黔教技[2022]015号);贵州省模式识别与智能系统重点实验室开放课题(No.GZMUKL[2022]KF01,GZMUKL[2022]KF05)资助。

摘　　要：连续型进化算法首达时间上界研究中需要较强的前提假设且较少关注其下界.文中引入鞅论和更新过程,结合瓦尔德不等式以及更新定理,提出基于增长率的更新理论模型,用于估计进化策略(Evolution Strategies,ES)平均首达时间的上界和下界.更新理论模型依赖算法的初始种群以及增长率概率密度函数,这为进化策略的首达时间分析提供估计优势.为了验证文中更新理论模型,首先计算带均匀变异(1,λ)ES在二维倾斜平面问题上的平均首达时间,得到(1,λ)ES种群规模与时间上下界之间的关系闭合表达式,并且验证平均首达时间与种群规模之间并非负相关.再计算带均匀变异(1,λ)ES在五维超平面问题上的平均首达时间,得到理论计算的上下界闭合表达式.数值实验表明,理论计算的上界和下界与实际运行平均首达时间一致,这为分析进化策略的首达时间提供一种理论工具.In the research on upper bound of the first hitting time for continuous evolutionary algorithms,strong assumptions are required and less attention is given to its lower bound.In this paper,martingale theory and renewal process are introduced and combined with Wald′s inequality and renewal theorem.A renewal theory model based on progress rate is proposed to estimate the upper and lower bounds of the expected first hitting time of evolution strategies.The renewal theory model relies on the initial population and the probability density function of the progress rate,providing an estimation advantage for the analysis of the first hitting time of evolutionary strategies.To verify the validity of the proposed renewal theory model,experiments are conducted to estimate the expected first hitting time.Firstly,the expected first hitting time of(1,λ)evolution strategies with uniform mutation on a two-dimensional inclined plane problem is calculated.The closed-form expression for the relationship between(1,λ)evolution strategies population size and the time upper and lower bounds is obtained.It is proved that the expected first hitting time is not negatively correlated with the population size.Next,the expected first hitting time of evolution strategies with uniform mutation on a five-dimensional hyperplane problem is calculated,and the closed-form expression for theoretical upper and lower bounds is derived.Numerical experiments show that the theoretically calculated upper and lower bounds are consistent with the actual expected first hitting time,which provides a theoretical tool for analyzing the first hitting time of evolution strategies.

关 键 词：连续型进化算法 瓦尔德不等式 更新理论模型 首达时间 种群规模 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]