新颖的离散差分演化算法求解D{0-1}KP问题

doi:10.3778/j.issn.1673-9418.2007047

计算机科学与探索 ›› 2022, Vol. 16 ›› Issue (2): 468-479.DOI: 10.3778/j.issn.1673-9418.2007047

新颖的离散差分演化算法求解D{0-1}KP问题

张发展, 贺毅朝⁺(), 刘雪静, 王泽昆

河北地质大学信息工程学院,石家庄 050031

收稿日期:2020-07-17 修回日期:2020-10-15 出版日期:2022-02-01 发布日期:2020-11-05
通讯作者: + E-mail: heyichao@hgu.edu.cn
作者简介:张发展（1995—）,男,山东潍坊人,硕士研究生,主要研究方向为演化算法及其应用。
贺毅朝（1969—）,男,河北晋州人,硕士,教授,主要研究方向为演化算法及其应用、组合优化、强化学习。
刘雪静（1980—）,女,河北定州人,硕士,讲师,主要研究方向为群智能、演化计算、近似计算等。
王泽昆（1996—）,男,河北石家庄人,硕士研究生,主要研究方向为演化算法及其应用。
基金资助:
河北省自然科学基金(F2020403013);河北省高等学校科学研究计划项目(ZD2021016)

Novel Discrete Differential Evolution Algorithm for Solving D{0-1}KP Problem

ZHANG Fazhan, HE Yichao⁺(), LIU Xuejing, WANG Zekun

School of Information and Engineering, Hebei GEO University, Shijiazhuang 050031, China

Received:2020-07-17 Revised:2020-10-15 Online:2022-02-01 Published:2020-11-05
About author:ZHANG Fazhan, born in 1995, M.S. candidate. His research interests include evolutionary algorithm and its applications.
HE Yichao, born in 1969, M.S., professor. His research interests include evolutionary algorithm and its applications, combinatorial optimization and reinforcement learning.
LIU Xuejing, born in 1980, M.S., lecturer. Her research interests include swarm intelligence, evolutionary computation, approximation algorithm, etc.
WANG Zekun, born in 1996, M.S. candidate. His research interests include evolutionary algorithm and its applications.
Supported by:
Natural Science Foundation of Hebei Province(F2020403013);Scientific Research Program of Colleges and Universities in Hebei Province(ZD2021016)

摘要/Abstract

摘要：

折扣{0-1}背包问题(D{0-1}KP)是0-1背包问题（0-1KP）的一种更复杂的扩展形式。为了利用离散差分演化高效求解D{0-1}KP,首先提出了一个新V型转换函数（NV）,通过NV将个体的实向量映射为一个二进制向量,与已有的S型和V型转换函数相比,NV计算复杂度更低,求解效率更高。然后,基于新V型转换函数给出了一种新的离散差分演化算法（NDDE）,并利用NDDE提出了求解D{0-1}KP的一个新的高效方法。最后,为了验证NDDE求解D{0-1}KP的性能,利用它求解四类大规模D{0-1}KP实例,并与基于群论的优化算法（GTOA）、基于环理论的演化算法（RTEA）、混合教学优化算法（HTLBO）和鲸鱼优化算法（WOA）等已有算法的最好计算结果进行比较,比较结果表明,NDDE不仅求解精度更高,而且算法的稳定性佳,非常适于求解大规模D{0-1}KP实例。

关键词: 演化算法, 离散差分演化, 折扣{0-1}背包问题（D{0-1}KP）, 新V型转换函数（NV）

Abstract:

The discounted {0-1} knapsack problem (D{0-1}KP) is a more complex variant of the classic 0-1 knap-sack problem (0-1KP). In order to efficiently solve the D{0-1}KP by using discrete differential evolution algorithm, firstly, a novel V-shape transfer function (NV) is proposed. The real vector of an individual is mapped into a binary vector by NV. Compared with the existing S-shaped and V-shaped transfer function, NV has lower computational complexity and higher efficiency. Then, a new discrete differential evolution algorithm (NDDE) is given based on the novel V-shape transfer function. A novel and efficient method for solving D{0-1}KP is proposed by NDDE. Finally, in order to verify the efficiency of NDDE in solving D{0-1}KP, it is used to solve four kinds of large-scale D{0-1}KP instances, and the results are compared with the existing algorithms such as group theory-based optimi-zation algorithm (GTOA), ring theory-based evolutionary algorithm (RTEA), hybrid teaching-learning-based optimi-zation algorithm (HTLBO) and whale optimization algorithm (WOA). The results show that NDDE not only has higher accuracy, but also has good stability, which is very suitable for solving large-scale D{0-1}KP instances.

Key words: evolutionary algorithms, discrete differential evolution, discounted {0-1} knapsack problem (D{0-1}KP), novel V-shape transfer function (NV)

中图分类号:

TP18

张发展, 贺毅朝, 刘雪静, 王泽昆. 新颖的离散差分演化算法求解D{0-1}KP问题[J]. 计算机科学与探索, 2022, 16(2): 468-479.

ZHANG Fazhan, HE Yichao, LIU Xuejing, WANG Zekun. Novel Discrete Differential Evolution Algorithm for Solving D{0-1}KP Problem[J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(2): 468-479.

图/表 11

表1 S型转换函数和V型转换函数

Table 1 S-shaped and V-shaped families of transfer functions

S型转换函数		V型转换函数
名称	计算公式	名称	计算公式
S1	$S 1 (x) = 1 1 + e - 2 x$	V1	$V 1 (x) = erf π 2 x$
S2	$S 2 (x) = 1 1 + e - x$	V2	$V 2 (x) = tanh x$
S3	$S 3 (x) = 1 1 + e - (x / 2)$	V3	$V 3 (x) = x 1 + x 2$
S4	$S 4 (x) = 1 1 + e - (x / 3)$	V4	$V 4 (x) = 2 π a rcta n π 2 x$

表1 S型转换函数和V型转换函数

Table 1 S-shaped and V-shaped families of transfer functions

S型转换函数		V型转换函数
名称	计算公式	名称	计算公式
S1	$S 1 (x) = 1 1 + e - 2 x$	V1	$V 1 (x) = erf π 2 x$
S2	$S 2 (x) = 1 1 + e - x$	V2	$V 2 (x) = tanh x$
S3	$S 3 (x) = 1 1 + e - (x / 2)$	V3	$V 3 (x) = x 1 + x 2$
S4	$S 4 (x) = 1 1 + e - (x / 3)$	V4	$V 4 (x) = 2 π a rcta n π 2 x$

图1 N V A的函数曲线

Fig.1 Function curve of N V A

表2 秩和检验结果

Table 2 Results of Kruskal-Wallis test

Instances	$n$	$P$
UDKP	500	1.90E-24
WDKP	500	3.10E-20
SDKP	500	1.10E-27
IDKP	500	1.96E-2

表2 秩和检验结果

Table 2 Results of Kruskal-Wallis test

Instances	$n$	$P$
UDKP	500	1.90E-24
WDKP	500	3.10E-20
SDKP	500	1.10E-27
IDKP	500	1.96E-2

图2 UDKP5、WDKP5、SDKP5和IDKP5实例的盒图

Fig.2 Boxplots of instances UDKP5, WDKP5, SDKP5 and IDKP5

表3 算法的参数设置

Table 3 Setting of algorithm parameters

Algorithm	$N$	$MI$	$Run$	Other parameters
NDDE	50	$3 n$	100	$CR = 0.05, FS = 0.1, [- V, V] n = [- 3.0,3.0] 3 n$
GTOA	20	$12 n$	100	$P m = 0.008$
RTEA	20	$12 n$	100	$P m = 0.005$
HTLBO2	50	$3 n$	30	$R = 0.8, β = 0.1$
DWOA	40	$3 n$	50	$b = 0.5$
FirEGA	50	$3 n$	30	$P c = 0.8, P m = 1.000$
SecEGA	50	$3 n$	30	$P c = 0.8, P m = 0.010$

表3 算法的参数设置

Table 3 Setting of algorithm parameters

Algorithm	$N$	$MI$	$Run$	Other parameters
NDDE	50	$3 n$	100	$CR = 0.05, FS = 0.1, [- V, V] n = [- 3.0,3.0] 3 n$
GTOA	20	$12 n$	100	$P m = 0.008$
RTEA	20	$12 n$	100	$P m = 0.005$
HTLBO2	50	$3 n$	30	$R = 0.8, β = 0.1$
DWOA	40	$3 n$	50	$b = 0.5$
FirEGA	50	$3 n$	30	$P c = 0.8, P m = 1.000$
SecEGA	50	$3 n$	30	$P c = 0.8, P m = 0.010$

表4 NDDE和其他算法求解UDKP类实例的计算结果

Table 4 Calculation results by NDDE and other algorithms for UDKP instances

Algorithm	Result	UDKP1	UDKP2	UDKP3	UDKP4	UDKP5	UDKP6	UDKP7	UDKP8	UDKP9	UDKP10
$OPT$		85 740	163 744	269 393	347 599	442 644	536 578	635 860	650 206	718 532	779 460
NDDE	$Best$	85 740^*	163 744^*	269 393^*	347 599^*	442 644^*	536 578^*	635 854	650 198	718 528	779 459
	$Mean$	85 732.9	163 741.0	269 355.0	347 571.0	442 614.0	536 546.0	635 807.0	650 110.0	718 401.0	779 387.0
	$Worst$	85 687	163 703	269 231	347 426	442 506	536 387	635 598	649 558	717 773	779 059
	$Std$	14.52	7.35	31.36	26.23	22.83	38.46	35.64	110.09	128.95	73.17
GTOA	$Best$	85 740^*	163 744^*	269 393^*	347 582	442 605	536 563	635 311	649 514	717 243	778 576
	$Mean$	85 684.8	163 727.0	269 305.0	347 535.0	442 514.0	536 177.0	634 648.0	648 719.0	715 941.0	777 781.0
	$Worst$	85 489	163 640	269 148	347 462	442 332	535 573	633 941	647 259	714 110	776 820
	$Std$	53.87	23.16	57.48	27.65	51.50	215.42	323.17	416.97	533.29	370.86
RTEA	$Best$	85 740^*	163 744^*	269 393^*	347 574	442 627	536 503	635 481	649 514	716 760	778 692
	$Mean$	85 661.0	163 710.0	269 273.0	347 507.0	442 499.0	536 067.0	634 402.0	647 934.0	714 787.0	777 524.0
	$Worst$	85 477	163 592	269 089	347 336	442 303	534 370	631 836	645 934	711 259	775 519
	$Std$	63.48	30.53	60.12	45.08	66.74	440.87	614.55	659.77	903.15	573.73
HTLBO2	$Best$	85 721	163 730	269 292	347 508	442 217	535 929	635 267	649 705	717 584	777 990
	$Mean$	85 686.0	163 647.2	269 094.8	347 288.2	441 792.5	535 434.1	634 671.4	649 020.9	717 045.5	777 004.1
	$Worst$	85 634	163 440	268 835	346 978	441 253	534 909	633 721	648 347	716 468	776 224
	$Std$	12.90	64.80	110.80	129.20	255.40	258.00	297.70	339.10	296.50	431.20
DWOA	$Best$	84 983	160 946	266 407	343 345	435 048	528 335	628 467	639 426	708 207	763 000
	$Mean$	84 862.6	160 625.8	266 238.4	343 167.9	434 859.9	528 168.0	628 234.2	639 075.9	708 035.6	762 830.2
	$Worst$	84 791	160 495	266 177	342 986	434 521	527 895	628 071	638 912	707 808	762 621
	$Std$	—	—	—	—	—	—	—	—	—	—
FirEGA	$Best$	80 593	152 969	244 291	319 680	403 908	483 350	564 656	590 237	652 354	708 744
	$Mean$	79 325.3	151 045.2	241 061.2	316 503.4	399 525.2	478 779.5	559 815.4	584 264.3	646 592.2	703 947.8
	$Worst$	78 499	149 732	239 114	313 141	396 937	474 558	555 763	580 258	642 965	700 702
	$Std$	—	—	—	—	—	—	—	—	—	—
SecEGA	$Best$	77 970	148 042	230 485	306 358	375 619	447 231	531 192	560 932	619 444	689 248
	$Mean$	76 808.3	146 310.5	225 232.4	301 700.8	371 688.8	442 556.4	523 809.2	555 100.7	615 990.4	684 872.4
	$Worst$	75 624	144 113	222 118	299 059	368 445	438 762	517 579	545 509	609 077	662 742
	$Std$	—	—	—	—	—	—	—	—	—	—

表4 NDDE和其他算法求解UDKP类实例的计算结果

Table 4 Calculation results by NDDE and other algorithms for UDKP instances

Algorithm	Result	UDKP1	UDKP2	UDKP3	UDKP4	UDKP5	UDKP6	UDKP7	UDKP8	UDKP9	UDKP10
$OPT$		85 740	163 744	269 393	347 599	442 644	536 578	635 860	650 206	718 532	779 460
NDDE	$Best$	85 740^*	163 744^*	269 393^*	347 599^*	442 644^*	536 578^*	635 854	650 198	718 528	779 459
	$Mean$	85 732.9	163 741.0	269 355.0	347 571.0	442 614.0	536 546.0	635 807.0	650 110.0	718 401.0	779 387.0
	$Worst$	85 687	163 703	269 231	347 426	442 506	536 387	635 598	649 558	717 773	779 059
	$Std$	14.52	7.35	31.36	26.23	22.83	38.46	35.64	110.09	128.95	73.17
GTOA	$Best$	85 740^*	163 744^*	269 393^*	347 582	442 605	536 563	635 311	649 514	717 243	778 576
	$Mean$	85 684.8	163 727.0	269 305.0	347 535.0	442 514.0	536 177.0	634 648.0	648 719.0	715 941.0	777 781.0
	$Worst$	85 489	163 640	269 148	347 462	442 332	535 573	633 941	647 259	714 110	776 820
	$Std$	53.87	23.16	57.48	27.65	51.50	215.42	323.17	416.97	533.29	370.86
RTEA	$Best$	85 740^*	163 744^*	269 393^*	347 574	442 627	536 503	635 481	649 514	716 760	778 692
	$Mean$	85 661.0	163 710.0	269 273.0	347 507.0	442 499.0	536 067.0	634 402.0	647 934.0	714 787.0	777 524.0
	$Worst$	85 477	163 592	269 089	347 336	442 303	534 370	631 836	645 934	711 259	775 519
	$Std$	63.48	30.53	60.12	45.08	66.74	440.87	614.55	659.77	903.15	573.73
HTLBO2	$Best$	85 721	163 730	269 292	347 508	442 217	535 929	635 267	649 705	717 584	777 990
	$Mean$	85 686.0	163 647.2	269 094.8	347 288.2	441 792.5	535 434.1	634 671.4	649 020.9	717 045.5	777 004.1
	$Worst$	85 634	163 440	268 835	346 978	441 253	534 909	633 721	648 347	716 468	776 224
	$Std$	12.90	64.80	110.80	129.20	255.40	258.00	297.70	339.10	296.50	431.20
DWOA	$Best$	84 983	160 946	266 407	343 345	435 048	528 335	628 467	639 426	708 207	763 000
	$Mean$	84 862.6	160 625.8	266 238.4	343 167.9	434 859.9	528 168.0	628 234.2	639 075.9	708 035.6	762 830.2
	$Worst$	84 791	160 495	266 177	342 986	434 521	527 895	628 071	638 912	707 808	762 621
	$Std$	—	—	—	—	—	—	—	—	—	—
FirEGA	$Best$	80 593	152 969	244 291	319 680	403 908	483 350	564 656	590 237	652 354	708 744
	$Mean$	79 325.3	151 045.2	241 061.2	316 503.4	399 525.2	478 779.5	559 815.4	584 264.3	646 592.2	703 947.8
	$Worst$	78 499	149 732	239 114	313 141	396 937	474 558	555 763	580 258	642 965	700 702
	$Std$	—	—	—	—	—	—	—	—	—	—
SecEGA	$Best$	77 970	148 042	230 485	306 358	375 619	447 231	531 192	560 932	619 444	689 248
	$Mean$	76 808.3	146 310.5	225 232.4	301 700.8	371 688.8	442 556.4	523 809.2	555 100.7	615 990.4	684 872.4
	$Worst$	75 624	144 113	222 118	299 059	368 445	438 762	517 579	545 509	609 077	662 742
	$Std$	—	—	—	—	—	—	—	—	—	—

表5 NDDE和其他算法求解WDKP类实例的计算结果

Table 5 Calculation results by NDDE and other algorithms for WDKP instances

Algorithm	Result	WDKP1	WDKP2	WDKP3	WDKP4	WDKP5	WDKP6	WDKP7	WDKP8	WDKP9	WDKP10
$OPT$		83 098	138 215	256 616	315 675	428 490	566 050	547 683	576 959	650 660	678 967
NDDE	$Best$	83 098^*	138 215^*	256 616^*	315 657^*	428 490^*	466 050^*	547 683^*	576 958	650 660^*	678 967^*
	$Mean$	83 087.6	138 213.0	256 610.0	315 653.0	428 486.0	466 044.0	547 672.0	576 944.0	650 656.0	678 960.0
	$Worst$	83 083	138 213	256 589	315 638	428 446	466 022	547 633	576 894	650 640	678 910
	$Std$	5.26	0.63	5.82	3.93	4.76	5.28	7.41	9.73	3.46	8.16
GTOA	$Best$	83 098^*	138 215^*	256 616^*	315 657^*	428 487	466 050^*	547 675	576 954	650 648	678 945
	$Mean$	83 083.9	138 202.0	256 605.0	315 635.0	428 469.0	466 036.0	547 647.0	576 904.0	650 596.0	678 857.0
	$Worst$	83 058	138 157	256 575	315 596	428 431	466 008	547 572	576 820	650 450	678 551
	$Std$	7.00	11.31	9.30	12.93	12.69	8.39	17.00	28.43	33.57	63.58
RTEA	$Best$	83 098^*	138 215^*	256 616^*	315 655	428 485	466 045	547 682	576 946	650 646	678 957
	$Mean$	83 085.0	138 195.0	256 592.0	315 622.0	428 452.0	466 023.0	547 631.0	576 893.0	650 592.0	678 836.0
	$Worst$	83 036	138 130	256 523	315 566	428 377	465 983	547 553	576 813	650 391	678 500
	$Std$	7.88	15.42	15.87	18.44	18.22	13.18	23.03	25.77	39.17	78.57
Algorithm	Result	WDKP1	WDKP2	WDKP3	WDKP4	WDKP5	WDKP6	WDKP7	WDKP8	WDKP9	WDKP10
HTLBO2	$Best$	83 090	138 213	256 612	315 606	428 385	466 012	547 623	576 847	650 538	678 848
	$Mean$	83 085.2	138 182.7	256 566.4	315 556.2	428 321	465 962.1	547 542.3	576 708.0	650 465.9	678 738.1
	$Worst$	83 049	138 120	256 501	315 492	428 233	465 886	547 426	576 565	650 395	678 629
	$Std$	28.00	22.30	28.00	30.70	39.90	35.00	49.50	70.80	37.30	58.20
DWOA	$Best$	82 887	137 859	255 891	314 994	427 645	464 806	546 477	575 494	648 699	677 428
	$Mean$	82 831.9	137 787.3	255 828.3	314 929.4	427 607.1	464 759.9	546 378.6	575 428.7	648 674.8	677 372.5
	$Worst$	82 786	137 747	255 816	314 925	427 566	464 733	546 297	575 374	648 623	677 332
	$Std$	—	—	—	—	—	—	—	—	—	—
FirEGA	$Best$	82 722	137 712	254 234	314 107	426 783	463 870	544 059	574 201	647 012	677 359
	$Mean$	82 539.6	137 225.8	253 294.4	312 343.1	424 384.2	460 750.4	541 505.3	571 594.9	644 298.2	673 776
	$Worst$	82 454	136 983	252 909	310 665	421 584	455 201	535 551	565 119	639 241	660 332
	$Std$	—	—	—	—	—	—	—	—	—	—
SecEGA	$Best$	82 664	137 712	254 315	313 227	426 783	463 435	544 776	574 862	648 402	677 118
	$Mean$	81 118.3	135 951.3	247 826.2	308 628.9	421 415.1	461 779.8	537 821.2	567 507.7	643 444.6	672 912.3
	$Worst$	80 284	134 490	236 444	293 697	391 633	446 741	501 094	527 204	589 018	610 343
	$Std$	—	—	—	—	—	—	—	—	—	—

表5 NDDE和其他算法求解WDKP类实例的计算结果

Table 5 Calculation results by NDDE and other algorithms for WDKP instances

Algorithm	Result	WDKP1	WDKP2	WDKP3	WDKP4	WDKP5	WDKP6	WDKP7	WDKP8	WDKP9	WDKP10
$OPT$		83 098	138 215	256 616	315 675	428 490	566 050	547 683	576 959	650 660	678 967
NDDE	$Best$	83 098^*	138 215^*	256 616^*	315 657^*	428 490^*	466 050^*	547 683^*	576 958	650 660^*	678 967^*
	$Mean$	83 087.6	138 213.0	256 610.0	315 653.0	428 486.0	466 044.0	547 672.0	576 944.0	650 656.0	678 960.0
	$Worst$	83 083	138 213	256 589	315 638	428 446	466 022	547 633	576 894	650 640	678 910
	$Std$	5.26	0.63	5.82	3.93	4.76	5.28	7.41	9.73	3.46	8.16
GTOA	$Best$	83 098^*	138 215^*	256 616^*	315 657^*	428 487	466 050^*	547 675	576 954	650 648	678 945
	$Mean$	83 083.9	138 202.0	256 605.0	315 635.0	428 469.0	466 036.0	547 647.0	576 904.0	650 596.0	678 857.0
	$Worst$	83 058	138 157	256 575	315 596	428 431	466 008	547 572	576 820	650 450	678 551
	$Std$	7.00	11.31	9.30	12.93	12.69	8.39	17.00	28.43	33.57	63.58
RTEA	$Best$	83 098^*	138 215^*	256 616^*	315 655	428 485	466 045	547 682	576 946	650 646	678 957
	$Mean$	83 085.0	138 195.0	256 592.0	315 622.0	428 452.0	466 023.0	547 631.0	576 893.0	650 592.0	678 836.0
	$Worst$	83 036	138 130	256 523	315 566	428 377	465 983	547 553	576 813	650 391	678 500
	$Std$	7.88	15.42	15.87	18.44	18.22	13.18	23.03	25.77	39.17	78.57
Algorithm	Result	WDKP1	WDKP2	WDKP3	WDKP4	WDKP5	WDKP6	WDKP7	WDKP8	WDKP9	WDKP10
HTLBO2	$Best$	83 090	138 213	256 612	315 606	428 385	466 012	547 623	576 847	650 538	678 848
	$Mean$	83 085.2	138 182.7	256 566.4	315 556.2	428 321	465 962.1	547 542.3	576 708.0	650 465.9	678 738.1
	$Worst$	83 049	138 120	256 501	315 492	428 233	465 886	547 426	576 565	650 395	678 629
	$Std$	28.00	22.30	28.00	30.70	39.90	35.00	49.50	70.80	37.30	58.20
DWOA	$Best$	82 887	137 859	255 891	314 994	427 645	464 806	546 477	575 494	648 699	677 428
	$Mean$	82 831.9	137 787.3	255 828.3	314 929.4	427 607.1	464 759.9	546 378.6	575 428.7	648 674.8	677 372.5
	$Worst$	82 786	137 747	255 816	314 925	427 566	464 733	546 297	575 374	648 623	677 332
	$Std$	—	—	—	—	—	—	—	—	—	—
FirEGA	$Best$	82 722	137 712	254 234	314 107	426 783	463 870	544 059	574 201	647 012	677 359
	$Mean$	82 539.6	137 225.8	253 294.4	312 343.1	424 384.2	460 750.4	541 505.3	571 594.9	644 298.2	673 776
	$Worst$	82 454	136 983	252 909	310 665	421 584	455 201	535 551	565 119	639 241	660 332
	$Std$	—	—	—	—	—	—	—	—	—	—
SecEGA	$Best$	82 664	137 712	254 315	313 227	426 783	463 435	544 776	574 862	648 402	677 118
	$Mean$	81 118.3	135 951.3	247 826.2	308 628.9	421 415.1	461 779.8	537 821.2	567 507.7	643 444.6	672 912.3
	$Worst$	80 284	134 490	236 444	293 697	391 633	446 741	501 094	527 204	589 018	610 343
	$Std$	—	—	—	—	—	—	—	—	—	—

表6 NDDE和其他算法求解SDKP类实例的计算结果

Table 6 Calculation results by NDDE and other algorithms for SDKP instances

Algorithm	Result	SDKP1	SDKP2	SDKP3	SDKP4	SDKP5	SDKP6	SDKP7	SDKP8	SDKP9	SDKP10
$OPT$		94 459	160 805	238 248	340 027	463 033	466 097	620 446	670 697	739 121	765 317
NDDE	$Best$	94 447	160 805^*	238 248^*	340 027^*	463 012	466 079	620 374	670 649	739 048	765 245
	$Mean$	94 407.6	160 787.0	238 205.0	339 963.0	462 912.0	466 024.0	620 290.0	670 548.0	738 971.0	765 183.0
	$Worst$	94 338	160 716	238 137	339 863	462 814	465 934	620 177	670 452	738 858	765 019
	$Std$	26.15	33.48	18.58	26.32	36.34	28.76	40.77	35.04	35.04	40.28
GTOA	$Best$	94 452	160 805^*	238 243	340 025	462 980	466 074	620 219	670 304	738 458	764 586
	$Mean$	94 425.5	160 769.0	238 204.0	339 995.0	462 868.0	466 010.0	619 978.0	670 071.0	738 107.0	764 159.0
	$Worst$	94 329	160 701	238 144	339 933	462 717	465 881	619 623	669 791	737 667	763 609
	$Std$	22.81	19.99	21.14	17.60	48.45	33.87	109.38	124.22	179.95	197.93
RTEA	$Best$	94 449	160 786	238 215	339 988	462 929	466 036	620 238	670 431	738 707	764 821
	$Mean$	94 333.0	160 702.0	238 133.0	339 918.0	462 766.0	465 903.0	620 048.0	670 151.0	738 162.0	764 263.0
	$Worst$	94 132	160 588	237 992	339 801	462 593	465 712	619 741	669 702	737 660	763 665
	$Std$	67.88	45.52	43.12	38.25	74.40	61.21	108.31	151.77	219.06	236.47
HTLBO2	$Best$	94 435	160 702	238 165	339 728	462 524	465 415	619 849	669 609	738 003	764 051
	$Mean$	94 397.9	160 590.3	238 041.6	339 456.4	462 335.3	465 077.8	619 686.9	669 350.1	737 678.6	763 834.2
	$Worst$	94 361	160 440	237 929	339 088	462 093	464 682	619 402	669 031	737 415	763 660
	$Std$	25.10	52.80	53.50	136.10	124.60	154.80	110.50	157.40	134.10	101.10
DWOA	$Best$	94 258	159 902	236 431	336 851	460 095	460 966	615 866	664 653	731 654	756 144
	$Mean$	94 218.9	159 728.0	236 227.1	336 717.6	459 937.2	460 776.2	615 692.9	664 519.5	731 522.3	755 976.5
	$Worst$	94 159	159 636	236 068	336 601	459 804	460 660	615 510	664 338	731 418	755 878
	$Std$	—	—	—	—	—	—	—	—	—	—
FirEGA	$Best$	93 316	159 116	235 372	336 369	451 184	459 236	607 200	661 104	728 443	755 189
	$Mean$	93 192.8	158 936.7	235 204.4	335 844.7	447 335.9	458 746.1	602 797.7	659 844.6	727 364.5	752 931.0
	$Worst$	93 064	158 798	235 015	335 524	44 252	458 427	600 496	659 120	726 872	749 879
	$Std$	—	—	—	—	—	—	—	—	—	—
SecEGA	$Best$	93 009	159 107	235 474	336 597	444 748	458 509	598 648	662 465	730 036	756 662
	$Mean$	91 684.0	156 557.3	231 287.4	330 437.4	435 933.3	453 973.9	592 672.4	653 459.8	726 324.1	750 716.4
	$Worst$	90 256	154 241	224 872	318 638	415 923	430 286	571 469	610 664	671 623	697 520
	$Std$	—	—	—	—	—	—	—	—	—	—

表6 NDDE和其他算法求解SDKP类实例的计算结果

Table 6 Calculation results by NDDE and other algorithms for SDKP instances

Algorithm	Result	SDKP1	SDKP2	SDKP3	SDKP4	SDKP5	SDKP6	SDKP7	SDKP8	SDKP9	SDKP10
$OPT$		94 459	160 805	238 248	340 027	463 033	466 097	620 446	670 697	739 121	765 317
NDDE	$Best$	94 447	160 805^*	238 248^*	340 027^*	463 012	466 079	620 374	670 649	739 048	765 245
	$Mean$	94 407.6	160 787.0	238 205.0	339 963.0	462 912.0	466 024.0	620 290.0	670 548.0	738 971.0	765 183.0
	$Worst$	94 338	160 716	238 137	339 863	462 814	465 934	620 177	670 452	738 858	765 019
	$Std$	26.15	33.48	18.58	26.32	36.34	28.76	40.77	35.04	35.04	40.28
GTOA	$Best$	94 452	160 805^*	238 243	340 025	462 980	466 074	620 219	670 304	738 458	764 586
	$Mean$	94 425.5	160 769.0	238 204.0	339 995.0	462 868.0	466 010.0	619 978.0	670 071.0	738 107.0	764 159.0
	$Worst$	94 329	160 701	238 144	339 933	462 717	465 881	619 623	669 791	737 667	763 609
	$Std$	22.81	19.99	21.14	17.60	48.45	33.87	109.38	124.22	179.95	197.93
RTEA	$Best$	94 449	160 786	238 215	339 988	462 929	466 036	620 238	670 431	738 707	764 821
	$Mean$	94 333.0	160 702.0	238 133.0	339 918.0	462 766.0	465 903.0	620 048.0	670 151.0	738 162.0	764 263.0
	$Worst$	94 132	160 588	237 992	339 801	462 593	465 712	619 741	669 702	737 660	763 665
	$Std$	67.88	45.52	43.12	38.25	74.40	61.21	108.31	151.77	219.06	236.47
HTLBO2	$Best$	94 435	160 702	238 165	339 728	462 524	465 415	619 849	669 609	738 003	764 051
	$Mean$	94 397.9	160 590.3	238 041.6	339 456.4	462 335.3	465 077.8	619 686.9	669 350.1	737 678.6	763 834.2
	$Worst$	94 361	160 440	237 929	339 088	462 093	464 682	619 402	669 031	737 415	763 660
	$Std$	25.10	52.80	53.50	136.10	124.60	154.80	110.50	157.40	134.10	101.10
DWOA	$Best$	94 258	159 902	236 431	336 851	460 095	460 966	615 866	664 653	731 654	756 144
	$Mean$	94 218.9	159 728.0	236 227.1	336 717.6	459 937.2	460 776.2	615 692.9	664 519.5	731 522.3	755 976.5
	$Worst$	94 159	159 636	236 068	336 601	459 804	460 660	615 510	664 338	731 418	755 878
	$Std$	—	—	—	—	—	—	—	—	—	—
FirEGA	$Best$	93 316	159 116	235 372	336 369	451 184	459 236	607 200	661 104	728 443	755 189
	$Mean$	93 192.8	158 936.7	235 204.4	335 844.7	447 335.9	458 746.1	602 797.7	659 844.6	727 364.5	752 931.0
	$Worst$	93 064	158 798	235 015	335 524	44 252	458 427	600 496	659 120	726 872	749 879
	$Std$	—	—	—	—	—	—	—	—	—	—
SecEGA	$Best$	93 009	159 107	235 474	336 597	444 748	458 509	598 648	662 465	730 036	756 662
	$Mean$	91 684.0	156 557.3	231 287.4	330 437.4	435 933.3	453 973.9	592 672.4	653 459.8	726 324.1	750 716.4
	$Worst$	90 256	154 241	224 872	318 638	415 923	430 286	571 469	610 664	671 623	697 520
	$Std$	—	—	—	—	—	—	—	—	—	—

表7 NDDE和其他算法求解IDKP类实例的计算结果

Table 7 Calculation results by NDDE and other algorithms for IDKP instances

Algorithm	Result	IDKP1	IDKP2	IDKP3	IDKP4	IDKP5	IDKP6	IDKP7	IDKP8	IDKP9	IDKP10
$OPT$		70 106	118 268	234 804	282 591	335 584	452 463	489 149	533 841	528 144	581 244
NDDE	$Best$	70 106^*	118 268^*	234 804^*	282 591^*	335 584^*	452 463^*	489 149^*	533 841^*	528 144^*	581 244^*
	$Mean$	70 106.0	118 268.0	234 803.0	282 590.0	335 583.0	452 462.0	489 144.0	533 835.0	528 140.0	581 238.0
	$Worst$	70 106	118 268	234 802	282 585	335 580	452 441	489 137	533 824	528 136	581 232
	$Std$	0	0	0.52	0.60	0.40	6.21	4.29	2.79	0.87	1.33
GTOA	$Best$	70 106^*	118 268^*	234 804^*	282 583	335 580	452 463^*	489 144	533 834	528 144^*	581 234
	$Mean$	70 089.3	118 239.0	234 792.0	282 560.0	335 549.0	452 438.0	489 109.0	533 807.0	528 103.0	581 200.0
	$Worst$	70 048	118 168	234 731	282 497	335 449	452 372	489 019	533 762	527 998	581 086
	$Std$	15.18	23.66	12.56	16.26	27.90	18.51	23.97	14.42	28.67	24.90
RTEA	$Best$	70 106^*	118 268^*	234 804^*	282 583	335 580	452 450	489 142	533 833	528 144^*	581 238
	$Mean$	70 082.0	118 235.0	234 770.0	282 557.0	335 528.0	452 405.0	489 102.0	533 800.0	528 099.0	581 197.0
	$Worst$	70 037	118 146	234 703	282 485	335 314	452 311	488 948	533 724	528 015	581 091
	$Std$	21.55	26.72	23.34	18.05	39.20	32.80	26.99	20.75	27.95	33.39
HTLBO2	$Best$	70 106^*	118 268^*	234 804^*	282 591^*	335 584^*	452 462	489 149^*	533 836	528 140	581 238
	$Mean$	70 094.3	118 266.8	234 800.9	282 584.2	335 582.4	452 453.2	489 141	533 830.1	528 136.2	581 236.0
	$Worst$	70 074	118 232	234 795	282 565	335 580	452 447	489 121	533 816	528 124	581 229
	$Std$	8.30	11.40	2.60	5.60	1.90	4.40	5.60	4.50	3.20	2.20
DWOA	$Best$	70 106^*	118 268^*	234 739	282 591	335 584	452 418	489 137	533 817	528 140	581 238
	$Mean$	70 101.2	118 247.0	234 718.9	282 568.4	335 580.3	452 387.1	489 102.7	533 816.0	528 118.6	581 226.7
	$Worst$	70 090	118 232	234 663	282 565	335 580	452 359	489 063	533 816	528 109	581 225
	$Std$	—	—	—	—	—	—	—	—	—	—
FirEGA	$Best$	70 106^*	118 034	234 508	281 804	335 068	451 498	487 675	531 872	525 460	578 897
	$Mean$	70 078.0	117 544.3	233 896.3	280 536.6	332 180.2	449 781.0	484 305.8	529 372.8	522 243.5	575 128.5
	$Worst$	70 022	117 249	233 447	278 179	328 661	446 456	475 476	524 404	501 428	551 772
	$Std$	—	—	—	—	—	—	—	—	—	—
SecEGA	$Best$	70 101	118 232	234 698	282 484	335 580	452 016	48 840	533 686	527 942	580 910
	$Mean$	70 010.4	116 921.7	228 166.1	273 731.2	331 886.1	447 358.4	483 569.7	531 844.8	523 597.8	572 178.7
	$Worst$	69 947	115 384	218 621	259 485	309 964	412 539	445 999	508 560	476 760	520 255
	$Std$	—	—	—	—	—	—	—	—	—	—

表7 NDDE和其他算法求解IDKP类实例的计算结果

Table 7 Calculation results by NDDE and other algorithms for IDKP instances

Algorithm	Result	IDKP1	IDKP2	IDKP3	IDKP4	IDKP5	IDKP6	IDKP7	IDKP8	IDKP9	IDKP10
$OPT$		70 106	118 268	234 804	282 591	335 584	452 463	489 149	533 841	528 144	581 244
NDDE	$Best$	70 106^*	118 268^*	234 804^*	282 591^*	335 584^*	452 463^*	489 149^*	533 841^*	528 144^*	581 244^*
	$Mean$	70 106.0	118 268.0	234 803.0	282 590.0	335 583.0	452 462.0	489 144.0	533 835.0	528 140.0	581 238.0
	$Worst$	70 106	118 268	234 802	282 585	335 580	452 441	489 137	533 824	528 136	581 232
	$Std$	0	0	0.52	0.60	0.40	6.21	4.29	2.79	0.87	1.33
GTOA	$Best$	70 106^*	118 268^*	234 804^*	282 583	335 580	452 463^*	489 144	533 834	528 144^*	581 234
	$Mean$	70 089.3	118 239.0	234 792.0	282 560.0	335 549.0	452 438.0	489 109.0	533 807.0	528 103.0	581 200.0
	$Worst$	70 048	118 168	234 731	282 497	335 449	452 372	489 019	533 762	527 998	581 086
	$Std$	15.18	23.66	12.56	16.26	27.90	18.51	23.97	14.42	28.67	24.90
RTEA	$Best$	70 106^*	118 268^*	234 804^*	282 583	335 580	452 450	489 142	533 833	528 144^*	581 238
	$Mean$	70 082.0	118 235.0	234 770.0	282 557.0	335 528.0	452 405.0	489 102.0	533 800.0	528 099.0	581 197.0
	$Worst$	70 037	118 146	234 703	282 485	335 314	452 311	488 948	533 724	528 015	581 091
	$Std$	21.55	26.72	23.34	18.05	39.20	32.80	26.99	20.75	27.95	33.39
HTLBO2	$Best$	70 106^*	118 268^*	234 804^*	282 591^*	335 584^*	452 462	489 149^*	533 836	528 140	581 238
	$Mean$	70 094.3	118 266.8	234 800.9	282 584.2	335 582.4	452 453.2	489 141	533 830.1	528 136.2	581 236.0
	$Worst$	70 074	118 232	234 795	282 565	335 580	452 447	489 121	533 816	528 124	581 229
	$Std$	8.30	11.40	2.60	5.60	1.90	4.40	5.60	4.50	3.20	2.20
DWOA	$Best$	70 106^*	118 268^*	234 739	282 591	335 584	452 418	489 137	533 817	528 140	581 238
	$Mean$	70 101.2	118 247.0	234 718.9	282 568.4	335 580.3	452 387.1	489 102.7	533 816.0	528 118.6	581 226.7
	$Worst$	70 090	118 232	234 663	282 565	335 580	452 359	489 063	533 816	528 109	581 225
	$Std$	—	—	—	—	—	—	—	—	—	—
FirEGA	$Best$	70 106^*	118 034	234 508	281 804	335 068	451 498	487 675	531 872	525 460	578 897
	$Mean$	70 078.0	117 544.3	233 896.3	280 536.6	332 180.2	449 781.0	484 305.8	529 372.8	522 243.5	575 128.5
	$Worst$	70 022	117 249	233 447	278 179	328 661	446 456	475 476	524 404	501 428	551 772
	$Std$	—	—	—	—	—	—	—	—	—	—
SecEGA	$Best$	70 101	118 232	234 698	282 484	335 580	452 016	48 840	533 686	527 942	580 910
	$Mean$	70 010.4	116 921.7	228 166.1	273 731.2	331 886.1	447 358.4	483 569.7	531 844.8	523 597.8	572 178.7
	$Worst$	69 947	115 384	218 621	259 485	309 964	412 539	445 999	508 560	476 760	520 255
	$Std$	—	—	—	—	—	—	—	—	—	—

图3 4类D{0-1}KP实例的Gap曲线

Fig.3 Gap curves of 4 types of D{0-1}KP instances

图4 4类D{0-1}KP实例的Std直方图

Fig.4 Std histogram of 4 types of D{0-1}KP instances

参考文献 27

[1]	DU D Z, KO K I, HU X D. Design and analysis of approxi-mation algorithms[M]. Berlin, Heidelberg: Springer, 2012.
[2]	KELLERER H, PFERSCHY U, PISINGE D. Knapsack pro-blems[M]. Berlin, Heidelberg: Springer, 2004.
[3]	HE Y C, XIE H R, WONG T L, et al. A novel binary artificial bee colony algorithm for the set-union knapsack problem[J]. Future Generation Computer Systems, 2018, 78:77-86. DOI URL
[4]	MAURO D A, MAXENCE D B, MANUEL I A, et al. Ma-thematical models and decomposition methods for the multiple knapsack problem[J]. European Journal of Oper-ational Research, 2019, 274(3):886-899.
[5]	MARCHAND H, WOLSEY L A. The 0-1 knapsack pro-blem with a single continuous variable[J]. Mathematical Programming, 1999, 85(1):15-33. DOI URL
[6]	GULDAN B. Heuristic and exact algorithms for discounted knapsack problems[D]. Erlangen: University of Erlangen- Nürnberg, 2007.
[7]	RONG A Y, FIGUEIRA J R, KLAMROTH K. Dynamic pro-gramming based algorithms for the discounted {0-1} knap-sack problem[J]. Applied Mathematics and Computation, 2012, 218(12):6921-6933. DOI URL
[8]	HE Y C, WANG X Z, HE Y L, et al. Exact and approximate algorithms for discounted {0-1} knapsack problem[J]. Infor-mation Sciences, 2016, 369:634-647.
[9]	贺毅朝, 王熙照, 李文斌, 等. 基于遗传算法求解折扣{0-1}背包问题的研究[J]. 计算机学报, 2016, 39(12):2614-2630.
	HE Y C, WANG X Z, LI W B, et al. Research on genetic al-gorithms for discounted {0-1} knapsack problem[J]. Chinese Journal of Computers, 2016, 39(12):2614-2630.
[10]	吴聪聪, 贺毅朝, 陈嶷瑛, 等. 变异蝙蝠算法求解折扣{0-1}背包问题[J]. 计算机应用, 2017, 37(5):1292-1299.
	WU C C, HE Y C, CHEN Y Y, et al. Mutated bat algorithm for solving discounted {0-1} knapsack problem[J]. Journal of Computer Applications, 2017, 37(5):1292-1299.
[11]	刘雪静, 贺毅朝, 吴聪聪, 等. 自适应细菌觅食算法求解折扣{0-1}背包问题[J]. 计算机工程与应用, 2018, 54(18):139-146.
	LIU X J, HE Y C, WU C C, et al. Adaptive bacterial foraging optimization algorithm for discounted {0-1} knap-sack problem[J]. Computer Engineering and Applications, 2018, 54(18):139-146.
[12]	HE Y C, WANG X Z. Group theory-based optimization algorithm for solving knapsack problems[J]. Knowledge-Based Systems, 2021, 219:104445.
[13]	HE Y C, WANG X Z, GAO S G. Ring theory-based evolutionary algorithm and its application to D{0-1} KP[J]. Applied Soft Computing, 2019, 77:714-722. DOI URL
[14]	WU C C, ZHAO J L, FENG Y H, et al. Solving discounted {0-1} knapsack problems by a discrete hybrid teaching-learning-based optimization algorithm[J]. Applied Intellig-ence, 2020, 50(6):1872-1888.
[15]	LI Y, HE Y C, LIU X J, et al. A novel discrete whale optimization algorithm for solving knapsack problems[J]. Applied Intelligence, 2020, 50(10):3350-3366. DOI URL
[16]	STORN R, PRICE K V. Differential evolution—a simple and efficient heuristic for global optimization over continu-ous spaces[J]. Journal of Global Optimization, 1997, 11(4):341-359. DOI URL
[17]	TIAN M N, GAO X B. An improved differential evolution with information intercrossing and sharing mechanism for numerical optimization[J]. Swarm and Evolutionary Com-putation, 2019, 50:1-21.
[18]	AJITHAPRIYADARSINI S, MARY P M, IRUTHAYAR-AJAN M W. Automatic generation control of a multi-area power system with renewable energy source under deregu-lated environment: adaptive fuzzy logic-based differential evolution (DE) algorithm[J]. Soft Computing, 2019, 23(11):12087-12101. DOI URL
[19]	ENGELBRECHT A P, PAMPARA G. Binary differential evolution strategies[C]//Proceedings of the 2007 IEEE Con-gress on Evolutionary Computation, Singapore, Sep 25-28, 2007. Piscataway: IEEE, 2007: 1942-1947.
[20]	HE Y C, WANG J H, ZHANG X L, et al. Encoding transformation-based differential evolution algorithm for so-lving knapsack problem with single continuous variable[J]. Swarm and Evolutionary Computation, 2019, 50:100507.
[21]	MIRJALILI S, LEWIS A. S-shaped versus V-shaped trans-fer functions for binary particle swarm optimization[J]. Swarm and Evolutionary Computation, 2013, 9:1-14. DOI URL
[22]	CORMEN T H, LEISERSON C E, RIVEST R L, et al. Introduction to algorithms[M]. 3rd ed. Cambridge: MIT Press, 2009.
[23]	DERRAC J, GARCÍA S, MOLINA D, et al. A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intel-ligence algorithms[J]. Swarm and Evolutionary Computa-tion, 2011, 1(1):3-18.
[24]	MIRJALILI S, MIRJALILI S M, LEWIS A. Grey wolf optimizer[J]. Advance in Engineering Software, 2014, 69:46-61. DOI URL
[25]	MIRJALILI S, LEWIS A. The whale optimization algorithm[J]. Advances in Engineering Software, 2016, 95:51-67. DOI URL
[26]	ASLAN M, GÜNDÜZ M, KIRAN M S. JayaX: Jaya algorithm with xor operator for binary optimization[J]. Applied Soft Computing, 2019, 82:105576.
[27]	BERGANTIÑOS G, GÓMEZ-RÚA M, LLORCA N, et al. Allocating costs in set covering problems[J]. European Journal of Operational Research, 2020, 284(3):1074-1087. DOI URL

新颖的离散差分演化算法求解D{0-1}KP问题

Novel Discrete Differential Evolution Algorithm for Solving D{0-1}KP Problem

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 11

参考文献 27

相关文章 5

编辑推荐

Metrics

[1]	康上, 钱雪忠, 甘霖. 面向申威众核处理器的并行SaNSDE算法[J]. 计算机科学与探索, 2021, 15(10): 2015-2024.
[2]	喻飞，魏波. 交互式差分演化卡通人脸生成[J]. 计算机科学与探索, 2017, 11(12): 2023-2032.
[3]	刘琛，林盈，胡晓敏. 差分演化算法各种更新策略的对比分析[J]. 计算机科学与探索, 2013, 7(11): 983-993.
[4]	王则林，吴志健. 运用差分演化算法实现多维包匹配的研究[J]. 计算机科学与探索, 2012, 6(7): 612-620.
[5]	敖友云1+ ,迟洪钦2 . 多目标差分演化算法研究综述[J]. 计算机科学与探索, 2009, 3(3): 234-246.