Font Size: a A A

Research On Solving Knapsack Problem By Discrete Slime Mould Algorithm

Posted on:2022-12-09Degree:MasterType:Thesis
Country:ChinaCandidate:X J LiFull Text:PDF
GTID:2518306728471044Subject:Computer software and theory
Abstract/Summary:PDF Full Text Request
With the continuous progress of science and technology,combinatorial optimization is becoming more and more important in many fields,such as commerce,economy,manpower,transportation,communication,image processing and so on.Knapsack problem is an important combinatorial optimization problem,which is widely used in energy optimization,satellite scheduling,housing problem and so on.Because of the difficulty of knapsack problem,for the solution of its large-scale examples,the accurate algorithm can not meet the requirements of practical application because it takes a lot of time.The inexact algorithm represented by evolutionary algorithm has achieved great success in solving large-scale knapsack examples and has become one of the main methods to solve difficult knapsack problems.Slime mould algorithm(SMA)is a novel evolutionary algorithm proposed by Li Shimin et al in 2020,which has strong global exploration ability and optimization ability,and has been used in many fields such as water resources management,wind power generation,engineering and so on.Because SMA was originally proposed to solve numerical optimization problems,it can not be directly used to solve combinatorial optimization problems in discrete space,so how to discretize it is an important research problem.This paper mainly studies the discretization of SMA.Based on transcoding and modular operation,two discrete slime mould algorithms are proposed and applied to solve knapsack problems with single continuous variables(KPC),multiple knapsack problems(MKP),and multi-electric aircraft load management problems.The main research contents of this paper are as follows:1.Based on the direct discretization method of modular 2 operation,a novel discrete slime mould algorithm DDSMA is proposed,which can solve the combinatorial optimization problem on{0,1}n,and a new method for solving KPC is proposed by combining DDSMA with cross-mutation strategy.Compared with the existing best algorithms for solving KPC,the efficiency of the new method is verified.2.The feasibility and effectiveness of discretization of slime mould algorithm based on transcoding function are studied.Based on the transcoding method,a second novel discrete slime molud algorithm MDSMA is proposed,which can be used to solve combinatorial optimization problems in discrete domain{0,1,...,a1}×{0,1,...,a2}×...×{0,1,...,an}.3.In order to use the algorithm MDSMA to solve the MKP problem,a repair optimization method GROIA is proposed.On this basis,a new method for solving MKP problem is proposed based on MDSMA.The effectiveness of the new method is verified by comparison with discrete particle swarm optimization algorithm(DisPSO),discrete whale optimization algorithm(DWOA),genetic algorithm(GA)and optimization algorithm based on group theory(GTOA).4.In order to demonstrate the practicability of the algorithm MDSMA,MDSMA is applied to the multi-electric aircraft load management problem,and a new method for solving the power load management problem is proposed.Compared with the existing algorithms,the efficiency of the new method is verified.
Keywords/Search Tags:combinatorial optimization problem, knapsack problem, slime mould algorithm, discretization method, automatic load management problem of more electric aircraft
PDF Full Text Request
Related items