Markov Chain-based Local Optima Network and Performance Estimation of (1+1)-EA
Markov Chain-based Local Optima Network and Performance Estimation of (1+1)-EA
复制标题
基于马尔可夫链的局部最优网络及(1 1)-EA的性能估计
DOI：
10.11394/tjpnsec.13.40
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
田中 彰一郎，古谷 博史，日和 悟，廣安 知之，高玉 圭樹，佐藤 寛之
中科院分区：
文献类型：
--
作者：
Tomoaki Takagi;Keiki Takadama and Hiroyuki Sato;田中 彰一郎，古谷 博史，日和 悟，廣安 知之，高玉 圭樹，佐藤 寛之
提出了一种基于马尔可夫链的局部最优网络（LON），表示进化算法（EA）的搜索转移。LON是由局部最优点作为节点，优化算法的搜索过渡点作为边构造的图。本文以基于突变的(1+ 1)-EA算法为目标优化算法，构建了基于马尔可夫链模型估计最优解的成功率和到达时间的LON。我们针对具有20个变量和2到5个不同协变量数量的nk -景观问题生成了建议的LONs，并讨论了从生成的LONs中观察到的成功率、收敛时间和定量特征之间的关系。结果表明，变量空间中最优解的漏斗比例对成功率影响较大。此外，我们还表明，随着目标函数评估次数的增加，所提出的LON对(1+ 1)-EA的成功率估计精度和收敛时间增加。当目标函数评价次数大于1000次时，成功率预测的决定系数大于0.9。
This paper proposed a Markov chain-based local optima network (LON), representing search transitions of an evolutionary algorithm (EA). LON is a graph constructed by local optima as nodes and search transitions of an optimization algorithm as edges. This paper focused on a mutation-based (1+ 1)-EA as the target optimization algorithm and constructed its LON, which could estimate the success ratio to find the optimal solution and the time to reach it based on the Markov chain model. We generated the proposed LONs on NK-landscape problems with twenty variables and the different number of co-variables from two to five and discussed the relations among the success ratio, the convergence time, and quantitative features observed from the generated LONs. The results revealed that the optimal solution’s funnel ratio in the variable space greatly impacts the success ratio. Also, we showed that the estimation accuracy of the success ratio and the convergence time of the (1+ 1)-EA by the proposed LON increase as the number of objective function evaluations increases. The coefficient of determination of the success ratio prediction exceeded 0.9 when the number of objective function evaluations got more than one thousand.