东北大学学报:自然科学版  2019, Vol. 40 Issue (11): 1521-1526  
0

引用本文 [复制中英文]

关守平, 邹立夫, 张菁菁. 区间多目标粒子群优化算法及其应用[J]. 东北大学学报:自然科学版, 2019, 40(11): 1521-1526.
[复制中文]
GUAN Shou-ping, ZOU Li-fu, ZHANG Jing-jing. Interval Multi-objective Particle Swarm Optimization Algorithm and Its Application[J]. Journal of Northeastern University Nature Science, 2019, 40(11): 1521-1526. DOI: 10.12068/j.issn.1005-3026.2019.11.001.
[复制英文]

基金项目

国家自然科学基金资助项目(61573087)

作者简介

关守平(1965-),男,辽宁大连人,东北大学教授。

文章历史

收稿日期:2018-12-06
区间多目标粒子群优化算法及其应用
关守平 , 邹立夫 , 张菁菁     
东北大学 信息科学与工程学院, 辽宁 沈阳 110819
摘要:提出了一种区间多目标粒子群优化(IMOPSO)算法, 用于解决多目标下区间变量的优化问题.基于区间可信度定义两个区间解的占优关系, 通过归一化方法和区间拥挤度距离对Pareto最优解排序, 并设立归档机制, 利用外部存储器保存Pareto最优解集.针对有界误差系统的建模问题, 提出了基于IMOPSO算法训练区间神经网络(INN)模型参数的建模方法, 解决了误差界已知和误差界未知两种情况下的有界误差系统建模问题.最后, 以一阶不确定系统为例, 利用所提算法进行了建模仿真, 验证了建模方法的有效性.
关键词区间多目标优化    区间粒子群优化    区间神经网络    未知但有界(UBB)    一阶不确定系统    
Interval Multi-objective Particle Swarm Optimization Algorithm and Its Application
GUAN Shou-ping , ZOU Li-fu , ZHANG Jing-jing     
School of Information Science & Engineering, Northeastern University, Shenyang 110819, China
Corresponding author: GUAN Shou-ping, E-mail: guanshouping@ise.neu.edu.cn
Abstract: An interval multi-objective particle swarm optimization(IMOPSO)algorithm was proposed to solve the optimization problem of interval variables under multi-objectives. A dominant relationship between two intervals was defined based on interval credibility. Normalization method and interval crowding distance were used to sort the Pareto-optimal solutions. And an archiving mechanism was set up to save the Pareto optimal set in the external memory. Then, an interval neural network(INN)employing the IMOPSO to train was proposed for the unknown-but-bounded(UBB)errors modeling problem, which can be suited for the two situations of the error bounds that is either known or unknown. The first-order uncertain system was taken as an example to verify the proposed method, and the simulation results validated the effectiveness.
Key words: interval multi-objective optimization    interval particle swarm optimization    interval neural network    unknown but bounded(UBB)    first-order uncertain system    

在文献[1]中对区间单目标粒子群优化(interval particle swanm optimization, IPSO)算法如何优化区间神经网络(interval neural network, INN)参数的问题进行了研究, 但是在对许多复杂区间控制系统的建模与优化中, IPSO算法无法满足实际需求.近年来, 多目标优化算法受到了广泛关注, 其中群体智能算法最为著名.群体智能算法是通过模拟自然生物群落的智能行为而产生的算法, 并在区间多目标优化问题中得到了一定程度的应用[2-3].目前对于区间多目标优化的研究主要是针对目标函数中包含区间参数的多目标问题, 而本文针对以决策变量为区间数的多目标优化问题, 提出了一种区间多目标粒子群优化算法(interval multi-objective particle swarm optimization, IMOPSO).其中关键问题是如何定义基于区间的Pareto占优关系比较不同进化个体的性能.为此, 本文给出了区间可信度、区间拥挤度距离等相关定义, 利用外部存储器对Pareto最优解进行存储和排序.通过选取的多个测试函数, 验证了本算法的有效性.

未知但有界(unknown but bounded, UBB)误差建模问题[4]一直是控制领域研究的重要方向.UBB误差建模问题存在两种情况:第一种是误差界未知(用UBB-U表示), 系统的实际输出为在一定范围内波动的点值, 没有明确的界限; 第二种是误差界已知(用UBB-N表示), 系统的实际输出为区间值.现有的UBB求解方法都是针对UBB-N情况, 对于UBB-U的相关研究较少.求解UBB-N问题的方法目前有凸多面体法[5]、最小二乘法[6]、区间分析集逆算法[7](如SIVIA)等, 上述方法的一个共性问题是需要已知系统的模型结构, 但在实际工程中, 往往只能得到不确定系统的输入输出数据, 而很难确定其结构, 对于非线性系统更是如此.针对该问题, 本文提出了基于INN的UBB问题建模方法.由于神经网络一直以来在复杂系统建模方面表现出优良的性能[8], 因此利用由区间理论与神经网络结合成的INN[9-10]模型能有效解决不确定信息的建模问题.

现有的神经网络大都是基于梯度下降法进行学习的, 这种方法常常会陷入局部最优[11], 该问题同样存在于INN中.故本文针对UBB-U和UBB-N两种情况, 定义了相应的多目标函数, 采用IMOPSO算法对INN模型参数进行训练, 从而得到不确定性系统的INN模型, 用于预报、控制和优化等应用.

1 预备知识 1.1 区间分析

1966年, 美国数学家Moore第一次系统提出了区间分析理论[12], 从此开启了区间分析的研究热潮.有区间数如A=[a, a], 其中a, aR, 且aa.当a=a时, A退化为点, 成为退化区间, 所以点可以认为是区间数的一种特例.在本文中, 小写的字母如a, b表示实数, 大写的字母如A, B表示区间数, 小写字母加粗如a, b表示实数向量或矩阵, 加粗的大写字母如A, B代表区间向量或矩阵.本文的区间关系按照文献[13]中的区间运算法则计算.

1.2 IPSO算法

粒子群优化(particle swarm optimization, PSO)算法是Kennedy等[14]提出的一种智能优化算法.IPSO[1]与常规PSO的区别主要在优劣粒子的比较方法和迭代公式的计算方法.

1) 优劣粒子的比较. IPSO算法在评价粒子优劣时使用的是区间适应度, 此时简单地通过点值来判断粒子优劣的方法将不再适用.因此, 给出区间可信度定义:

定义1  考虑区间A=[a, a]和B=[b, b], CAB的极大区间, C=[c, c], 其中c=max{a, b}, c=max{a, b, a, b\c}表示除去c以外的从{a, b, a, b}选择最大值.则区间A大于等于区间B的可信度P(AB)为

(1)

其中, d(A, C)=max{|ac|, |ac|}, 代表区间A和区间C的距离.

2) 迭代公式.严格采用区间减法更新粒子位置信息时, 会破坏粒子的跟踪性, 文献[15]提出了一种趋势减法, 保证了粒子的趋向性, 其定义为

定义2  对于区间A=[a, a], B=[b, b], 有

(2)

则称上述运算为趋势减法, 用符号“--”表示.

综上, 区间粒子的速度及位置更新公式为

(3)
(4)

式中:Xidk+1表示粒子群在第k次迭代过程中第i个粒子的位置,k=1, 2, …, G, G为最大迭代次数,i=2, 3, …, m, m为种群规模;Vidk+1为粒子群在第k次迭代过程中第i个粒子的速度;Pidk表示在第k次迭代过程中第i个粒子的历史最优位置;Pgdk表示当前种群在第k次迭代中的全局最优位置.粒子群算法的惯性系数为w,学习因子c1, c2, ξη为[0, 1]范围内的均匀随机数.

2 区间多目标粒子群优化算法

区间多目标优化问题的数学模型为

(5)

其中:Fi(X, C)(i=1, 2, …, q)为第i个目标函数, 该函数值也是一个区间数, Fi=[fi, fi]; X为决策变量, X=(X1, X2, …, Xn)T, Xj=[xj, xj], j=1, 2, …, n, n表示决策变量维度; C为参数向量, C=(C1, C2, …, Cl)T, Ck=[ck, ck], k=1, 2, …, l; S为决策变量可行域; 当区间向量X和参数C都退化为点值时, 则式(5)就退化为点值多目标数学模型.

2.1 IMOPSO算法基础

1) 区间拥挤度距离.若存在进化个体X1X2, 它们第i个目标函数值分别为Fi(X1)和Fi(X2), i=1, 2, …, m, 则进化个体X1X2距离为

(6)

假设与X1距离最近的两个进化个体分别为X2, X3, 则X1的拥挤距离为

(7)

2) Pareto最优解的选择.在得到区间可信度定义的基础上, Pareto最优解集的选择方法为:在初始化各个区间粒子Xi(i=1, 2, …, N)之后, 默认其为当前粒子的个体历史最优位置, 计算其区间目标函数值Fm(Xi), m=1, 2, …, M, 其中M为目标函数个数.如果∃i, 对于∀j, j=1, 2, …, N, 且ji, XiXj总成立, 则将其保留至外部存储器FLJ中, FLJ={FLJ, {F1(Xi), F2(Xi), …, FM(Xi), Xi}}.

3) Pareto最优解的排序.由于不同的目标函数值的量化范围不同, 因此本算法先将各个目标函数值进行归一化处理后再排序, 具体步骤如下:

步骤1  将归一化之后, 可得;

步骤2  将Xj在各个目标函数进行归一化后的值qi(j)相加, 即;

步骤3 将各粒子对应的r进行排序sort(r);

步骤4 计算粒子的拥挤度距离C(Xi), 其中i=2, 3, …, s-1, 并设置X1Xs的拥挤度距离为C(X1)=C(Xs)=max(C(X2), C(X3), …, C(Xs-1))+1;

步骤5 将所有Pareto最优解基于拥挤度距离进行降序排列存入到外部存储器中.

2.2 IMOPSO算法

IMOPSO算法的详细步骤如下:

步骤1 初始化区间粒子群算法的相关参数, 包括学习因子C1C2、惯性系数W、种群规模m、最大迭代次数G、搜索范围Rd、区间粒子宽度bd, 外部存储器Pareto最优解最大个数N;

步骤2 初始化粒子群中粒子在各个维度上的位置和速度, 并设其为个体历史最优位置;

步骤3 计算区间粒子在各个目标函数上的值Fm(Xi), 基于区间可信度选择Pareto最优解并存入外部存储器中;

步骤4 归一化外部存储器中的各个Pareto最优解的所有目标函数值, 并求和, 按照降序排列Pareto最优解;

步骤5 计算外部存储器中各个Pareto最优解的拥挤度距离并降序排序, 基于轮盘赌选择法从Pareto最优解集中选择全局最优位置Pgd;

步骤6 根据式(3)、式(4)更新区间粒子的速度Vidk+1和位置Xidk+1;

步骤7 基于占优关系选择个体历史最优位置Pid;

步骤8 基于区间关系更新外部存储器;

步骤9 判断Pareto最优解个数是否大于N, 若大于则继续下一步; 若不大于则转至步骤11;

步骤10 基于区间拥挤度选取前N个Pareto最优解;

步骤11 判断当前迭代次数k>K, 若满足则继续下一步, 若不满足则转至步骤5;

步骤12 输出Pareto最优解集.

2.3 算法仿真算例

本文选择两个多目标测试函数进行测试, 测试函数表达式如下:

函数1 Binh and Korn函数:

(8)

算法中Rd=[0, 3]×[0, 5], bd=0.3.

函数2 Quaglia-rella函数:

(9)

其中:A1==1[(Xi)2-10cos[2π(Xi)]+10];A2==1[(Xi-1.5)2-cos10[2π(Xi-1.5)]+10];算法中Rd=[-5.12, 5.12]n, bd=0.03.

图 1图 2为仿真结果, 表示所得的Pareto最优前沿, 其中每个矩形区域对应问题的一个解.从图中可以看出, 得到的矩形区域与真实的Pareto前沿的轨迹基本一致, 证明了IMOPSO算法的有效性.

图 1 函数1仿真结果 Fig.1 Function 1 simulation results
图 2 函数2仿真结果 Fig.2 Function 2 simulation results
3 有界误差建模

UBB条件下的区间系统建模[4]一般称之为有界误差建模问题, 可以描述为非线性模型y=f(x, p)+e, 其中p为待辨识模型参数向量.已知输入输出的实际观测数据对(xi, yi)和误差ei, 其中.当误差界已知时, 可以写成区间模型为, 其中P为不确定参数集, pP, F(·)为f(·)的区间扩张函数.于是可以用INN模型逼近区间函数F(·), 即, 其中WΘ为网络参数.根据区间和点值的关系, 误差界未知的情况可以看作误差界已知情况的特例处理.

3.1 区间神经网络

将区间分析与神经网络相结合构成的INN拥有和传统神经网络一样的结构, 目前常见的INN为前馈区间神经网络(feed for ward interval neural network, FINN)[1, 9-10].本文采用与文献[1]相同的FINN进行建模, 其三层i-j-k结构如图 3所示.

图 3 三层FINN结构图 Fig.3 Structure of a three-layer FINN

图 3中, xi表示网络的输入(点值), WijWjk分别表示隐含层和输出层的权值(区间), BjBk分别表示隐含层和输出层的阈值(区间), 由此可以得到点值输入/区间值输出的函数关系.

输入层:

(10)

隐含层:

(11)
(12)

输出层:

(13)
(14)

式中:oi表示输入层的输出值; Netj表示隐含层的节点关系; Oj表示隐含层的输出值; Netk表示输出层的节点关系; Ok表示输出层的输出值; f(x)为激励函数,一般选取sigmoid函数.

3.2 目标函数的选择

首先选取两个指标σ1σ2作为建模准确度的评价指标, 定义如下:

在UBB-U条件下,

(15)

其中:np为训练样本的总数量; yi为目标输出点值; 为INN预测输出区间值.

(16)

其中: ymax=max(y1, y2, …, ynp); ymin=min(y1, y2, …, ynp).

在UBB-N条件下,

(17)

其中:

为目标输出区间值.

(18)

其中:

分析式(15)~式(18)易知, σ1值越大且σ2值越小, 建模准确度越高.

基于σ1σ2, 选择两个优化目标函数如下:

目标函数1:

(19)

目标函数2:

(20)
3.3 一阶不确定系统建模

一阶离散不确定系统的数学模型可以表示为

(21)

其中, y(k)和u(k)是在k时刻可以得到的系统输出和输入数据.设输入u(k)为单位阶跃信号, v(k)为不确定但有界噪声序列, v(k)∈V=[-0.2, 0.2], a=0.5, b=0.5, y(0)=0, u(0)=0.

在UBB-U情况下, 系统输出为随机波动的点值, 则其噪声为随机点值序列rand(V); 在UBB-N情况下, 系统的输出为区间值, 则其噪声为随机区间序列RND(V), 因输入须是点值, 则对Y(k-1)取中点得Mid(Y(k-1)), 因此式(21)可以分别表示为

(22)
(23)

其中:rand(·)为点值随机函数; RND(·)为区间值随机函数; .

对该系统进行多目标下的INN建模, INN的拓扑结构为2-5-1, 选取1 000组系统阶跃响应时间序列作为训练数据.IMOPSO算法中, 选取参数为c1=c2=1.25, ω=0.5, m=60, G=500, N=10, Rd=[-10, 10], bd=0.1.

在UBB-U和UBB-N情况下, 利用IMOPSO算法对该区间神经网络训练得到的Pareto前沿如图 4图 5所示.

图 4 Pareto前沿(UBB-U) Fig.4 Pareto front(UBB-U)
图 5 Pareto前沿(UBB-N) Fig.5 Pareto front(UBB-N)

由3.2节可知, σ1值越大且σ2值越小, 建模准确度越高, 取σ=σ1+(1-σ2), 将每个Pareto最优解在各个评价指标下的数值按照σ降序排列, 并记录于表 1中.

表 1 评价指标数值表 Table 1 Evaluating indicators

据此选取最优解(序列号为1的评价指标对应的解)作为INN的权值和阈值, 选取100组输入输出测试数据对该一阶不确定系统模型进行测试, 输出测试数据作为目标输出区间, INN的输出数据为预测输出区间, 仿真结果如图 6图 7所示.从图中可以看出, 对于选取的100个测试数据, 其中98%以上都在预测输出区间内, 因此该仿真结果证明了本文所提建模方法的有效性.

图 6 目标输出点值与预测输出区间值对比图(UBB-U) Fig.6 Comparison between target point and prediction interval for UBB-U
图 7 目标输出区间值与预测输出区间值对比图(UBB-N) Fig.7 Comparison between target interval and prediction interval for UBB-N
4 结语

本文提出了一种区间多目标粒子群优化算法, 给出了基于区间的Pareto占优关系, 选择了两种测试函数证明了IMOPSO算法的可行性.在UBB-U和UBB-N情况下, 基于INN对一阶不确定线性系统进行建模, 并采用所提的IMOPSO算法训练INN, 证明了本文所提建模方法的有效性.本文将区间分析理论、智能算法中的进化思想以及神经网络相结合, 为有界误差建模提供了一条有效的途径.

参考文献
[1]
Guan S P, Zhang J J, Zou L F.An interval particle swarm optimization algorithm for evolving interval neural networks[C]// 2018 Chinese Control and Decision Conference(CCDC).Shenyang, 2018: 1615-1619.
[2]
Zhang J, Wang S, Zhang K. Cooperative artificial bee colony algorithm with multiple populations for interval multi-objective optimization problems[J]. IEEE Transactions on Fuzzy Systems, 2019, 27(5): 1052–1065. DOI:10.1109/TFUZZ.2018.2872125
[3]
Hsu C, Chang S, Yu C. Tolerance design of robust controllers for uncertain interval systems based on evolutionary algorithms[J]. IET Control Theory & Applications, 2007, 1(1): 244–252.
[4]
杨卫封, 曾芳玲. 区间分析在非线性系统模型参数估计中的应用[J]. 仪器仪表学报, 2008, 29(4): 244–252.
( Yang Wei-feng, Zeng Fang-ling. Application of interval analysis for parameter estimational nonlinear system model[J]. Chinese Journal of Scientific Instrument, 2008, 29(4): 244–252. )
[5]
Liu Y, Zhao Y, Wu F. Ellipsoidal state-bounding-based set-membership estimation for linear system with unknown-but-bounded disturbances[J]. IET Control Theory & Applications, 2016, 10(4): 431–442.
[6]
Bontayeb M. Identification of nonlinear systems in the presence of unknown but bounded disturbances[J]. IEEE Transactions on Automatic Control, 2000, 45(8): 1503–1507. DOI:10.1109/9.871759
[7]
Jaulin L, Walter E. Guaranteed nonlinear parameter estimation via interval computations[J]. Interval Computation, 1993, 35(2): 61–75.
[8]
Khosravi A, Nahavandi S, Creighton D, et al. Comprehensive review of neural network-based prediction intervals and new advances[J]. IEEE Transactions on Neural Networks, 2011, 22(9): 1341–1356. DOI:10.1109/TNN.2011.2162110
[9]
Song M, Pedrycz W. Granular neural networks:concepts and development schemes[J]. IEEE Transactions on Neural Networks and Learning System, 2013, 24(4): 542–553. DOI:10.1109/TNNLS.2013.2237787
[10]
Guan S P, Liang R Y.Study of full interval feed-forward neural network[C]// 2016 Chinese Control and Decision Conference(CCDC).Yinchuan, 2016: 2652-2655.
[11]
De Weerdt E, Chu Q P, Mulder J A. Neural network output optimization using interval analysis[J]. IEEE Transactions on Neural Networks, 2009, 20(4): 638–653. DOI:10.1109/TNN.2008.2011267
[12]
Moore R E. Interval analysis[M]. Englewood: Prentice-Hall, 1966.
[13]
Moore R E, Kearfott R B, Cloud M J. Introduction to interval analysis[M]. Philadelphia: SIAM Press, 2009.
[14]
Kennedy J, Eberhart R C.Particle swarm optimization[C]//Proceeding of IEEE International Conference on Neural Networks.Perth: IEEE Press, 1995: 1942-1948.
[15]
关守平, 房少纯. 一种新型的区间-粒子群优化算法[J]. 东北大学学报(自然科学版), 2012, 33(10): 1381–1384.
( Guan Shou-ping, Fang Shao-chun. A new interval particle swarm optimization algorithm[J]. Journal of Northeastern University(Natural Science), 2012, 33(10): 1381–1384. DOI:10.12068/j.issn.1005-3026.2012.10.004 )