Novel Discrete Differential Evolution Algorithm for Solving D{0-1}KP Problem
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 i...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | zho |
| Published: |
Journal of Computer Engineering and Applications Beijing Co., Ltd., Science Press
2022-02-01
|
| Series: | Jisuanji kexue yu tansuo |
| Subjects: | |
| Online Access: | http://fcst.ceaj.org/fileup/1673-9418/PDF/2007047.pdf |
| _version_ | 1819277526764093440 |
|---|---|
| author | ZHANG Fazhan, HE Yichao, LIU Xuejing, WANG Zekun |
| author_facet | ZHANG Fazhan, HE Yichao, LIU Xuejing, WANG Zekun |
| author_sort | ZHANG Fazhan, HE Yichao, LIU Xuejing, WANG Zekun |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-23T23:57:31Z |
| format | Article |
| id | doaj.art-c1d6f77f137f4885827cdf328bcad2a7 |
| institution | Directory Open Access Journal |
| issn | 1673-9418 |
| language | zho |
| last_indexed | 2024-12-23T23:57:31Z |
| publishDate | 2022-02-01 |
| publisher | Journal of Computer Engineering and Applications Beijing Co., Ltd., Science Press |
| record_format | Article |
| series | Jisuanji kexue yu tansuo |
| spelling | doaj.art-c1d6f77f137f4885827cdf328bcad2a72022-12-21T17:25:13ZzhoJournal of Computer Engineering and Applications Beijing Co., Ltd., Science PressJisuanji kexue yu tansuo1673-94182022-02-0116246847910.3778/j.issn.1673-9418.2007047Novel Discrete Differential Evolution Algorithm for Solving D{0-1}KP ProblemZHANG Fazhan, HE Yichao, LIU Xuejing, WANG Zekun0School of Information and Engineering, Hebei GEO University, Shijiazhuang 050031, ChinaThe 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.http://fcst.ceaj.org/fileup/1673-9418/PDF/2007047.pdf|evolutionary algorithms|discrete differential evolution|discounted {0-1} knapsack problem (d{0-1}kp)|novel v-shape transfer function (nv) |
| spellingShingle | ZHANG Fazhan, HE Yichao, LIU Xuejing, WANG Zekun Novel Discrete Differential Evolution Algorithm for Solving D{0-1}KP Problem Jisuanji kexue yu tansuo |evolutionary algorithms|discrete differential evolution|discounted {0-1} knapsack problem (d{0-1}kp)|novel v-shape transfer function (nv) |
| title | Novel Discrete Differential Evolution Algorithm for Solving D{0-1}KP Problem |
| title_full | Novel Discrete Differential Evolution Algorithm for Solving D{0-1}KP Problem |
| title_fullStr | Novel Discrete Differential Evolution Algorithm for Solving D{0-1}KP Problem |
| title_full_unstemmed | Novel Discrete Differential Evolution Algorithm for Solving D{0-1}KP Problem |
| title_short | Novel Discrete Differential Evolution Algorithm for Solving D{0-1}KP Problem |
| title_sort | novel discrete differential evolution algorithm for solving d 0 1 kp problem |
| topic | |evolutionary algorithms|discrete differential evolution|discounted {0-1} knapsack problem (d{0-1}kp)|novel v-shape transfer function (nv) |
| url | http://fcst.ceaj.org/fileup/1673-9418/PDF/2007047.pdf |
| work_keys_str_mv | AT zhangfazhanheyichaoliuxuejingwangzekun noveldiscretedifferentialevolutionalgorithmforsolvingd01kpproblem |