Study of Chemical Reaction Based Algorithms for Knapsack Pro

发布时间：2021-04-01 23:27

　　背包问题在众多工业领域中都能遇到,诸如交通、物流、切割及包装、电信、可靠性、广告、投资、预算分配和生产管理。在这些应用中,背包问题一般作为独立的问题或复杂的子问题出现。从化学反应优化算法（chemical reaction optimization, CRO）中得到启发,本研究提出了两种启发式化学反应算法,并应用于0-1背包问题和多选择背包问题。首先,化学反应优化算法应用于求解0-1背包问题。在该算法中,五个特定化学反应操作算子来实现平衡强化和多元化。其次,在解决0-1背包问题的化学反应优化算法中,提出了一个贪婪的策略。第三,提出了一个新的基于化学反应优化的方法解决多选择背包问题。第四,在多选择背包问题中,提出了一个并行版本的化学反应优化算法。我们在一个大范围的数据集中使用这些新的方法进行了测试。实验结果表明,这些算法在解决背包问题等有很大的优势。论文结构：论文的结构分为六章。在第一章,介绍了0-1背包问题,并提出了多选择背包问题。同时提出了两个元启发式化学反应算法。第二章提出了一种新的具有贪婪策略的化学反应优化算法来解决0-1背包问题。一个新的集成了贪婪策略和随机选择的修复算子用于修... 

【文章来源】：湖南大学湖南省 211工程院校 985工程院校 教育部直属院校

【文章页数】：129 页

【学位级别】：博士

【文章目录】：
ABSTRACT
摘要
TABLE OF CONTENTS
LIST OF FIGURES
LIST OF TABLES
CHAPTER 1:INTRODUCTION
    1.1 Background and motivation
    1.2 Research objectives
    1.3 0-1 knapsack problem
        1.3.1 Brand-and-bound algorithms
    1.4 Multiple-choice knapsack problem
    1.5 Chemical reaction optimization
        1.5.1 Basic reaction operators
        1.5.2 Algorithm design
    1.6 Artificial chemical reaction optimization algorithm
        1.6.1 Chemical reactions
        1.6.2 Reactants update
        1.6.3 Termination criterion check
    1.7 Dissertation Structure
CHAPTER 2:AN ARTIFICIAL CHEMICAL REACTION OPTIMIZATIONALGORITHM FOR 0-1 KNAPSACK PROBLEM
    2.1 Introduction
    2.2 Artificial chemical reaction optimization algorithm
        2.2.1 Chemical reactions
        2.2.2 Reactants update
    2.3 Designing ACROA For KP01
        2.3.1 Solution Representation
        2.3.2 O bjective function
        2.3.3 Repair operator
    2.4 Simulation Results
    2.5 Summary
CHAPTER 3:CHEMICAL REACTION OPTIMIZATION WITH GREEDYSTRATEGY FOR THE 0-1 KNAPSACK PROBLEM
    3.1 Introduction
    3.2 Related works
        3.2.1 Chemical Reaction Optimization
        3.2.2 Quantum-Inspired Evolutionary Algorithm
        3.2.3 Ant Colony Algorithm（ACO）
        3.2.4 Genetic Algorithm
    3.3 Designing CROG for KP01
        3.3.1 Solution Representation
        3.3.2 Neighborhood Search Operator
        3.3.3 Other implementation
    3.4 Simulation Results
    3.5 Summary
CHAPTER 4:CHEMICAL REACTION OPTIMIZATION FOR MULTIPLE-CHOICE KNAPSACK PROBLEM
    4.1 1Introduction
    4.2 Genetic algorithm
    4.3 Designing CRO for MCKP
        4.3.1 Solution Representation
        4.3.2 3.2 Objective function
        4.3.3 Elementary operators
    4.4 Experiment and analysis
        4.4.1 Data test set
        4.4.2 Parameter setting
        4.4.3 Experiment results
    4.5 Summary
CHAPTER 5:A PARALLEL CHEMICAL REACTION OPTIMIZATIONFOR MULTIPLE-CHOICE KNAPSACK PROBLEM
    5.1 1 Introduction
    5.2 A basic Chemical Reaction Optimization
        5.2.1 Elementary reactions
    5.3 A PCRO for MCKP
        5.3.1 PCRO structure
        5.3.2 Solution Representation
        5.3.3 Objective function
        5.3.4 Elementary operators
    5.4 Experiment and analysis
        5.4.1 Data test set
        5.4.2 Experiment results
    5.5 Summary
CHAPTER 6:AN ARTIFICIAL CHEMICAL REACTION OPTIMIZATIONALGORITHM FOR MULTIPLE-CHOICE KNAPSACK PROBLEM
    6.1 Introduction
    6.2 Genetic algorithm for MCKP
    6.3 Artificial chemical reaction optimization algorithm
        6.3.1 Chemical reactions
        6.3.2 Termination criterion check
    6.4 Designing ACROA for MCKP
        6.4.1 Solution Representation
        6.4.2 Objective and penalty functions
        6.4.3 Reaction operators
        6.4.4 Reactants update
        6.4.5 Termination criterion check
    6.5 Experiment and analysis
        6.5.1 Data test set
        6.5.2 Parameter setting
        6.5.3 Experiment results
    6.6 Summary
CONCLUSIONS
REFERENCES
APPENDIX A:LIST OF PUBICATIONS
APPENDIX B:ACKNOWLEDGEMENTS



本文编号：3114154