自记忆的深度强化学习模型求解多维背包问题  

Based Self Memorized Deep Reinforcement Learning Model for Solving Multidimensional Knapsack Problem

作　　者：盛佳浩 马良[1] 刘勇[1] SHENG Jiahao;MA Liang;LIU Yong(Business School,University of Shanghai for Science and Technology,Shanghai 200093,China)

机构地区：[1]上海理工大学管理学院,上海200093

出　　处：《小型微型计算机系统》2024年第9期2137-2148,共12页Journal of Chinese Computer Systems

基　　金：上海市哲学社会科学规划课题项目(2019BGL014)资助;教育部人文社会科学研究青年基金项目(21YJC630087)资助.

摘　　要：本文针对多维背包问题维度高,约束强的特点提出了自记忆的学习优化模型(self memorized learn to improve,SML2I),通过深度强化学习的学习机制选择迭代搜索过程中的算子即模型学习当前的解以及历史搜索过程中的解,判断对当前解采用提升策略或者是扰动策略,在此基础上,进一步提出了哈希表与设计了2种有效的基于价值密度的扰动算子.使用哈希表记录历史搜索过程中的解,防止模型重复探索相同的解,基于价值密度的扰动策略生成的新解与之前的解决方案完全不同,因此针对扰动后的解再次采用提升策略同样有效,通过测试89个MKP数据集并与其他文献中先进的求解方法进行对比,实验结果验证了SML2I模型求解MKP问题的可行性与有效性.This paper proposes a self memorized learning to improve(SML2I)model for multidimensional knapsack problem,which is characterized by high dimensions and strong constraints.Through the learning mechanism of deep reinforcement learning,the operator in the iterative search process is selected,that is,the model learns the current solution and the solution in the historical search process.On this basis,the current solution is judged to be improved or disturbed,Furthermore,a hash table is proposed and two effective perturbation operators based on value density are designed.Using a hash table to record the solutions during the historical search process prevents the model from repeatedly exploring the same solution.The new solution generated by the value density based perturbation strategy is completely different from the previous solution,so it is equally effective to use the lifting strategy again for the perturbed solution.By testing 89 MKP datasets and comparing them with advanced solution methods in other literature,the experimental results verify the feasibility and effectiveness of the SML2I model in solving the MKP problem.

关 键 词：多维背包问题 深度强化学习 多哈希 邻域算子 策略梯度 

分 类 号：TP183[自动化与计算机技术—控制理论与控制工程]