Solving discounted {0-1} knapsack problems by a discrete hybrid teaching-learning-based optimization algorithm

doi:10.1007/s10489-020-01652-0

Solving discounted {0-1} knapsack problems by a discrete hybrid teaching-learning-based optimization algorithm

2020-02-19

24

PRE

AI

DOI：10.1007/s10489-020-01652-0

Original

Original request for help

Save

Abstract

En 中文

The discounted {0-1} knapsack problem (D{0-1}KP) is a kind of knapsack problem with group structure and discount relationships among items. It is more challenging than the classical 0-1 knapsack problem. A more effective hybrid algorithm, the discrete hybrid teaching-learning-based optimization algorithm (HTLBO), is proposed to solve D{0-1}KP in this paper. HTLBO is based on the framework of the teaching-learning-based optimization (TLBO) algorithm. A two-tuple consisting of a quaternary vector and a real vector is used to represent an individual in HTLBO and that allows TLBO to effectively solve discrete optimization problems. We enhanced the optimization ability of HTLBO from three aspects. The learning strategy in the Learner phase is modified to extend the exploration capability of HTLBO. Inspired by the human learning process, self-learning factors are incorporated into the Teacher and Learner phases, which balances the exploitation and exploration of the algorithm. Two types of crossover operators are designed to enhance the global search capability of HTLBO. Finally, we conducted extensive experiments on eight sets of 80 instances using our proposed approach. The experiment results show that the new algorithm has higher accuracy and better stability than do previous methods. Overall, HTLBO is an excellent approach for solving the D{0-1}KP.

Keywords:

Discounted {0-1} knapsack problem

Teaching-learning-based optimization algorithm

Self-learning

Crossover operator

Solving discounted {0-1} knapsack problems by a discrete hybrid teaching-learning-based optimization algorithm

Abstract

AI Summary

Journal

Organization