Font Size: a A A

Solution Of Multidimensional Backpack Problem Based On Firework Algorithm

Posted on:2021-04-10Degree:MasterType:Thesis
Country:ChinaCandidate:B C LvFull Text:PDF
GTID:2428330611972220Subject:Software engineering
Abstract/Summary:PDF Full Text Request
Multidimensional knapsack problem(MKP),as an extension of the 0-1 knapsack problem,is a typical NP-hard problem.There are a large number of application scenarios in daily life,such as cargo loading,resource allocation,and investment decisions.Therefore,it is of great significance to solve the multidimensional knapsack problem both in theory and in practical applications.With the gradual increase in the scale of the problem,the traditional precise solution algorithm and heuristic algorithm gradually seem to be inadequate,and the development of group intelligence algorithms has opened up a new path for the solution of such problems.The swarm intelligence algorithm is a new type of algorithm that achieves the purpose of solving by simulating information exchange between biological populations.The fireworks algorithm is implemented by simulating the process of fireworks explosion in the night sky.As a kind of swarm intelligence algorithm,the firework algorithm has the characteristics of few parameters,simple execution process,easy implementation,and strong robustness.It has certain advantages in solving large and complex optimization problems,and has been widely concerned by academia.This article introduces various precise solving algorithms,heuristic algorithms and swarm intelligence algorithms used to solve the multidimensional backpack problem.In-depth analysis of the characteristics of the multidimensional backpack problem and the firework algorithm.For the multidimensional backpack problem,the item selection strategy appears as a binary string The characteristics of fireworks algorithm and the advantages and disadvantages of fast search speed in the early stage and slow convergence speed in the later period,the binary firework algorithm and the elite opposition-based learning mechanism were introduced,and the binary elite opposition-based learning firework algorithm was designed.,BEOFA),at the cost of slightly reducing the early search speed of the algorithm,effectively speeding up the late convergence speed of the algorithm.BEOFA first refers to the characteristics of the solution set of the multidimensional backpack problem,referring to the binary encoding method of the firework algorithm,that is,the binary firework algorithm;secondly,in the binary environment,the binary mutation operator mechanism is introduced to replace the traditional firework algorithm.The Gaussian mutation mechanism improves the algorithm's global search ability and ability to jump out of the local optimal value;then for the shortcomings of the traditional fireworks algorithm's late convergence speed,the elite opposition-based learning mechanism is introduced,and the elite opposition-based learning mechanism is designed in a binary environment The running process of the algorithm improves the late convergence speed of the algorithm.Finally,a total of 4kinds of 8 classic multidimensional knapsack problem functions were selected to simulate and test the performance of BEOFA's fast optimization performance,mining ability,global search ability and comprehensive ability,and compared with other 4population intelligent algorithms.And analyze the results.The results of simulation experiments show that BEOFA is not weaker than other algorithms in solving small problems,and its overall performance in solving large and complex problems is better than the other four algorithms,which achieved the purpose of optimizing the algorithm.
Keywords/Search Tags:Firework Algorithm, Multidimensional Knapsack Problem, Swarm Intelligence Algorithm, Elite Opposition-based Learning
PDF Full Text Request
Related items