背包問題在眾多工業(yè)領(lǐng)域中都能遇到,諸如交通、物流、切割及包裝、電信、可靠性、廣告、投資、預(yù)算分配和生產(chǎn)管理。在這些應(yīng)用中,背包問題一般作為獨立的問題或復(fù)雜的子問題出現(xiàn)。從化學(xué)反應(yīng)優(yōu)化算法（chemical reaction optimization, CRO）中得到啟發(fā),本研究提出了兩種啟發(fā)式化學(xué)反應(yīng)算法,并應(yīng)用于0-1背包問題和多選擇背包問題。首先,化學(xué)反應(yīng)優(yōu)化算法應(yīng)用于求解0-1背包問題。在該算法中,五個特定化學(xué)反應(yīng)操作算子來實現(xiàn)平衡強(qiáng)化和多元化。其次,在解決0-1背包問題的化學(xué)反應(yīng)優(yōu)化算法中,提出了一個貪婪的策略。第三,提出了一個新的基于化學(xué)反應(yīng)優(yōu)化的方法解決多選擇背包問題。第四,在多選擇背包問題中,提出了一個并行版本的化學(xué)反應(yīng)優(yōu)化算法。我們在一個大范圍的數(shù)據(jù)集中使用這些新的方法進(jìn)行了測試。實驗結(jié)果表明,這些算法在解決背包問題等有很大的優(yōu)勢。論文結(jié)構(gòu)：論文的結(jié)構(gòu)分為六章。在第一章,介紹了0-1背包問題,并提出了多選擇背包問題。同時提出了兩個元啟發(fā)式化學(xué)反應(yīng)算法。第二章提出了一種新的具有貪婪策略的化學(xué)反應(yīng)優(yōu)化算法來解決0-1背包問題。一個新的集成了貪婪策略和隨機(jī)選擇的修復(fù)算子用于修... 

【文章來源】：湖南大學(xué)湖南省 211工程院校 985工程院校 教育部直屬院校

【文章頁數(shù)】：129 頁

【學(xué)位級別】：博士

【文章目錄】：
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