2022/01/23 by Congcong Wu, Xiangyun Gao, Wu, Congcong +5
Computer Science · Engineering · #Advanced Manufacturing and Logistics Optimization #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Neural and Evolutionary Computing (cs.NE) #Optimization and Packing Problems #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2202.05698
openalex publication_date 2022/01/23 · openalex created_date 2022/03/05 · openalex updated_date 2026/07/28
The set-union knapsack problem (SUKP) is a constrained composed optimization\nproblem. It is more difficulty for solving because values and weights depend on\nitems and elements respectively. In this paper, we present two self-adjusting\noptimization algorithms for approximating SUKP from items and elements\nperspective respectively. By analyzing the dynamic characters in the SUKP, we\ndesign two types of self-adjusting repair and optimization operators that are\nbased on the different loading process. We use the novel\nteaching-learning-based optimization algorithm (TLBO) to design a general\ndiscrete framework (DTLBO) suitable for these two types of operators. In\naddition, we introduce elite opposite search and natural selection mechanism\ninto DTLBO to furtherly improve the performance of the algorithm from the\nperspective of population. Finally, we performed experimental comparisons on\nbenchmark sets to verify the effectiveness of the proposed algorithm. The\nexperimental results show that the item-based self-adjusting optimization\nalgorithm I-DTLBO is outstanding, and the algorithm is superior to the other\nswarm intelligence methods for solving SUKP. IDTLBO algorithm reaches the upper\nboundary of the current swarm intelligence algorithms for solving SUKP in 10\ninstances, and gotten new upper boundary in 15 instances. The algorithm E-DTLBO\nbased on element loading only perform slightly better on small and middle data\nsets, but worse on large-scale instances. It shows that element-based design is\nnot suitable for solving SUKP.\n