求解高维动态0-1背包问题的修补二进制差分进化算法

Solving high-dimensional dynamic 0-1 knapsack problem using binary differential evolution algorithm with repair strategy

针对已有的动态优化算法求解高维动态背包问题(DKP)难以获得高质量的可行解,且跟踪环境速度慢,提出了一种修补二进制差分进化算法(BDE/R)用于求解高维DKP。在BDE/R设计中,一种随机压缩变异策略直接根据个体间的差异在离散域内对个体进行突变;提出了一种贪婪的修补策略,提高了所获可行解的质量和算法的收敛速度;设计了一种对偶变换算子,提高种群的多样性,加速了算法跟踪环境的能力。数值实验以平均环境跟踪精确度(Av-Acc)和平均环境跟踪适应度(Av-Ada)为性能评价指标,通过四种DKP测试BDE/R跟踪动态最优值的能力,并将BDE/R与其他五种著名的优化算法进行了比较。结果表明:BDE/R所获的Av-Acc和Av-Ada指标优越于其他算法;由平均适应度跟踪曲线比较获知,BDE/R跟踪环境速度快于其他算法。

The existing dynam ic o p tim ization algo rithm is difficu lt to achieve high q u a lity feasible solutions on high -dimensionaldynam ic knapsack problem (DKP) ,and shows a slower tracking environmental speed. This paper proposed a bin x ry d iffe re n tial evo lu tion algo rithm w ith re p a ir strategy (BDE/R ) fo r solving DKP. In BDE/R , it a p plied a random co m p re ssib ility m utation strategy d ire c tly to carry out in d iv id u a l5 s m utation in discrete space according to the diffe ren ce between two in d iv id u a ls . Itdeveloped greedy re p a ir strategy to im prove the feasible solution 5 squality obtained and the convergence speed o f the BDE/R .I t used dual transform ation to im prove po pulatio n d iv e rs ity , and accelerated the a b ility o f tra ckin g en vironm ental o p tim um . Tovalida te the tra ckin g perform ance o f the BDE/R ,w h ic h was a p plied to solve fo u r high -dim ension al DKPs. E xperim enta l resultsshow that BDE/R can achieve a superior average a ccu ra cy( Av-Acc) and a d a p ta b ility ( Av-Ada ) when com pared w ith five peerop tim ization algo rithm s. F u rth e rm o re , BDE/R displays a fast tra ckin g environm ental speed in terms o f the average fitness tra c k ing curves.