单目标应用：最有价值球员算法（MostValuablePlayerAlgorithm，MVPA）求解旅行商问题TSP

最有价值球员算法&＃xff08;Most Valuable Player Algorithm&＃xff0c;MVPA&＃xff09;由Bouchekara 等人于2017年提出&＃xff0c;该算法受到体育比赛的启发&＃xff0c;球员们为了赢得冠军而组成队伍进行队伍竞争&＃xff0c;他们也为了赢得最有价值球员( most valuable player&＃xff0c;MVP) 奖杯进行独立竞争。在最有价值球员算法中&＃xff0c;每个球员代表一个潜在的解&＃xff0c;通过球员竞争和队伍竞争来不断提高球员的能力&＃xff0c;最终产生一个 MVP&＃xff0c;而 MVP 对应问题的最优解。

最有价值球员算法中的每个球员都代表了一个潜在的解。球员通过所在球队中的个人竞争以及联盟中队伍与队伍之间的竞争不断提高球员的能力&＃xff0c;相应解的质量也在不断提高&＃xff0c;从而产生联盟中能力最强的球员&＃xff0c;即 MVP&＃xff0c;同时算法找到问题的最优解。最有价值球员算法的实现过程如下:

1.1初始化

在搜索空间内&＃xff0c;首先随机生成 PlayersSize 个球员&＃xff0c;然后将这些球员随机分成 TeamsSize 个队伍。球队的生成方法如下&＃xff1a;









n


P


1


&＃61;


 ceil 


(


 PlayersSize 


/


 TeamsSize 


)










n


P


2


&＃61;


n


P


1


−


1










n


T


1


&＃61;


 PlayersSize 


−


n


P


2


⋅


 TeamsSize 


)










n


T


2


&＃61;


 TeamsSize 


−


n


T


1







\begin{array}{c} n P 1&＃61;\text { ceil }(\text { PlayersSize } / \text { TeamsSize }) \\ n P 2&＃61;n P 1-1 \\ n T 1&＃61;\text { PlayersSize }-n P 2 \cdot \text { TeamsSize }) \\ n T 2&＃61;\text { TeamsSize }-n T 1 \end{array}


nP1&＃61; ceil ( PlayersSize / TeamsSize )nP2&＃61;nP1−1nT1&＃61; PlayersSize −nP2⋅ TeamsSize )nT2&＃61; TeamsSize −nT1​

其中&＃xff0c;ceil 为向上取整函数&＃xff0c;nT1 表示第一部分的队伍数量&＃xff0c;nP1 表示第一部分每个队伍的队员数量; nT2 表示第二部分的队伍数量&＃xff0c;nP2 表示第二部分每个队伍的队员数量。

1.2竞争阶段

在完成初始化之后&＃xff0c;算法进入竞争阶段。在该阶段中&＃xff0c;球员通过队内竞争来提高自身能力&＃xff0c;同时球队为了提升其实力与其它队伍进行队间竞争。下文给出球员之间的个体竞争以及球队之间的队伍竞争的具体方法。

1.2.1个体竞争

在个体竞争阶段&＃xff0c;每个球员都致力于成为所在队伍中的最佳球员( Franchise Player) 和联盟最有价值球员( MVP) 。为此&＃xff0c;球员努力去提高自身能力&＃xff0c;并与所在队伍中最佳球员和联盟最有价值球员做比较。因此&＃xff0c;每个球员按照如下式更新&＃xff1a;

$$TEAMi\&＃61;TEAMi\&＃43;rand\cdot (FranchisePlayers-TEAMi)\&＃43;2\cdot \mathrm{rand}\cdot (MVP-TEAMi)$$
其中&＃xff0c;TEAMi表示第 i 个队伍中队员; rand 是&＃xff3b;0&＃xff0c;1&＃xff3d;之间服从均匀分布的常数; FranchisePlayeri表示第 i 个队伍中的最佳球员; MVP 表示联盟最有价值球员。

1.2.2队伍竞争

在球员完成个体竞争之后&＃xff0c;球队之间进行队伍竞争。在这个阶段&＃xff0c;TEAMi和 TEAMj两个队伍相互比赛。按以下机制选取获胜队伍:

以最小化问题为例&＃xff0c;首先按照下式标准化队伍的适应度。









 fitness 


N


(


 TEAMi 


)


&＃61;


 fitness 


(


 TEAMi 


)


−


min


⁡


(


 fitness 


(


 ALLTeams 


)


)







\begin{array}{c} \text { fitness } N(\text { TEAMi })&＃61;\text { fitness }(\text { TEAMi })- \min (\text { fitness }(\text { ALLTeams })) \end{array}


 fitness N( TEAMi )&＃61; fitness ( TEAMi )−min( fitness ( ALLTeams ))​

其中&＃xff0c;fitness( TEAMi) 是第 i 个队伍未标准化的适应度值; min( fitness( ALL Teams) 是全联盟中最小的适应度值。TEAMi打败 TEAMj的概率如下式所示&＃xff1a;









Pr


⁡


{


 TEAMibeatTEAMj 


)


&＃61;


1


−




(


 fitness 


N


(


 TEAMi 


)



)


k





(


 fitness 


N


(


 TEAMi 


)



)


k



&＃43;


(


 fitness 


N


(


 TEAMj 


)



)


k










\begin{array}{l} \operatorname{Pr}\{\text { TEAMibeatTEAMj })&＃61;1- \frac{(\text { fitness } N(\text { TEAMi }))^{k}}{(\text { fitness } N(\text { TEAMi }))^{k}&＃43;(\text { fitness } N(\text { TEAMj }))^{k}} \\ \end{array}


Pr{ TEAMibeatTEAMj )&＃61;1−( fitness N( TEAMi ))k&＃43;( fitness N( TEAMj ))k( fitness N( TEAMi ))k​​

其中&＃xff0c;其中&＃xff1a; k &＃61; 1; fitness N( TEAMi) 为第 i 个队伍的适应度值&＃xff0c;Pr 表示获胜概率。

根据上两个式字 &＃xff0c;获胜概率分为不同和相同两种情况&＃xff1a;

&＃xff08;1&＃xff09;如果两个队伍的获胜概率不同&＃xff0c;则会生成一个&＃xff3b;0&＃xff0c;1&＃xff3d;之间的随机数&＃xff0c;如果这个随机数大于较高的获胜概率&＃xff0c;则获胜概率较低的队伍获胜&＃xff0c;反之&＃xff0c;则获胜概率较高的队伍获胜。

&＃xff08;2&＃xff09;如果两个队伍的适应度相同&＃xff0c;则会得到相同的获胜概率。因此&＃xff0c;还需要再生成一个&＃xff3b;0&＃xff0c;1&＃xff3d;之间的随机数&＃xff0c;若这个随机数高于 0. 5&＃xff0c;第一个队伍获胜&＃xff0c;否则&＃xff0c;第二个队伍获胜。

当球队 TEAMi获胜时&＃xff0c;则 TEAMi中队员按如下公式更新





 TEAM 


i


&＃61;


 TEAM 


i


&＃43;


 rand 


⋅



(


 TEAMi 


−



 FranchisePlayers 


j



)




\text { TEAM } i&＃61;\text { TEAM } i&＃43;\text { rand } \cdot\left(\text { TEAMi }-\text { FranchisePlayers }_{j}\right)


 TEAM i&＃61; TEAM i&＃43; rand ⋅( TEAMi − FranchisePlayers j​)
其中&＃xff0c;TEAMi表示第 i 个队伍中队员; rand 表示&＃xff3b;0&＃xff0c;1&＃xff3d;之间均匀分布的随机数; FranchisePlayerj表示第 j 个队伍中的最佳球员。当球队 TEAMj获胜时&＃xff0c;该队伍中队员按如下公式更新

 TEAM 


i


&＃61;


 TEAM 


&＃43;


 rand 


⋅



(



 FranchisePlayers 


j



−


 TEAM 


)




\text { TEAM } i&＃61;\text { TEAM }&＃43;\text { rand } \cdot\left(\text { FranchisePlayers }_{j}-\text { TEAM }\right)


 TEAM i&＃61; TEAM &＃43; rand ⋅( FranchisePlayers j​− TEAM )

1.3MVPA伪代码

参考文献&＃xff1a;
[1]王宁,刘勇.求解最优化问题的新型最有价值球员算法[J].计算机仿真,2020,37(06):273-282&＃43;327.
[2]缪炳荣,彭齐明,杨树旺,雒耀祥,裘杨喆.基于最有价值球员算法的结构损伤识别方法[J].重庆交通大学学报(自然科学版),2022,41(01):67-75.
[3]王宁,刘勇.考虑多种训练方式的自适应最有价值球员算法[J].计算机应用,2020,40(06):1722-1730.
[4]刘鑫. 最有价值球员算法及应用研究[D].广西民族大学,2019.DOI:10.27035/d.cnki.ggxmc.2019.000513.
[5]Bouchekara, Reh H . Most Valuable Player Algorithm: a novel optimization algorithm inspired from sport[J]. Operational Research, 2017.

旅行商问题&＃xff08;Traveling salesman problem, TSP&＃xff09;是一个经典的组合优化问题&＃xff0c;它可以描述为一个商品推销员去若干城市推销商品&＃xff0c;要求遍历所有城市后回到出发地&＃xff0c;目的是选择一个最短的路线。当城市数目较少时&＃xff0c;可以使用穷举法求解。而随着城市数增多&＃xff0c;求解空间比较复杂&＃xff0c;无法使用穷举法求解&＃xff0c;因此需要使用优化算法来解决TSP问题。
一般地&＃xff0c;TSP问题可描述为&＃xff1a;一个旅行商需要拜访n个城市&＃xff0c;城市之间的距离是已知的&＃xff0c;若旅行商对每个城市必须拜访且只拜访一次&＃xff0c;求旅行商从某个城市出发并最终回到起点的一条最短路径。
记n个城市序号构成集合为N&＃61;{1,2,…,n},旅行商拜访完n个城市所经过的回路记为&＃xff1a;





P


&＃61;



{



p


1



→



p


2



→


⋯


→



p


n



→



p


1



}




P&＃61;\left\{p_{1} \rightarrow p_{2} \rightarrow \cdots \rightarrow p_{n} \rightarrow p_{1}\right\}


P&＃61;{p1​→p2​→⋯→pn​→p1​}
其中&＃xff0c;





p


i



∈


N


,



p


i



≠



p


j



(


i


≠


j


)


,


i


&＃61;


1


,


2


,


⋯
 

,


n



p_{i} \in N, p_{i} \neq p_{j}(i \neq j), i&＃61;1,2, \cdots, n


pi​∈N,pi​​&＃61;pj​(i​&＃61;j),i&＃61;1,2,⋯,n
若城市之间的距离矩阵为




D


&＃61;




∣



d



i


j




∣




n


×


n





D&＃61;\left|d_{i j}\right|_{n \times n}


D&＃61;∣dij​∣n×n​&＃xff0c;则TSP问题的数学模型可表示为&＃xff1a;





min


⁡


f


(


P


)


&＃61;



∑



i


&＃61;


1




n


−


1





d




p


i



,



p



i


&＃43;


1






&＃43;



d




p


n



,



p


1






\min f(P)&＃61;\sum_{i&＃61;1}^{n-1} d_{p_{i}, p_{i&＃43;1}}&＃43;d_{p_{n}, p_{1}}


minf(P)&＃61;i&＃61;1∑n−1​dpi​,pi&＃43;1​​&＃43;dpn​,p1​​
其中,$f(P)$表示旅行商行走路线的总路径长度。

本文选取国际通用的TSP实例库TSPLIB中的测试集burma14&＃xff0c;burma14中城市分布如下图所示&＃xff1a;

本文采用最有价值球员算法求解burma14&＃xff1a;

close all
clear
clc
代码链接&＃xff1a;https://pan.baidu.com/s/11I6eMyMU3k-UHfUu1O_mIA
提取码&＃xff1a;1234
%数据集参考文献 REINELT G.TSPLIB-a traveling salesman problem[J].ORSA Journal on Computing,1991,3(4):267-384.
%最有价值球员算法(Most Valuable Player Algorithm, MVPA)
global data
Dim&＃61;size(data,1)-1;%维度
lb&＃61;-10;%下界
ub&＃61;10;%上界
fobj&＃61;&＃64;Fun;%计算总距离
SearchAgents_no&＃61;120; % 种群大小&＃xff08;可以修改&＃xff09;
Max_iteration&＃61;30; % 最大迭代次数&＃xff08;可以修改&＃xff09;
[bestX,fMin,curve]&＃61;MVPA(SearchAgents_no,Max_iteration,lb,ub,Dim,fobj); %最有价值球员算法(Most Valuable Player Algorithm, MVPA)


其中一次结果&＃xff1a;

最有价值球员算法的收敛曲线&＃xff1a;

最有价值球员算法求得的路径&＃xff1a;

最有价值球员算法求解的最短总路径:30.8785

文件夹内包含所有代码及使用说明&＃xff0c;点击main.m即可运行。