Font Size: a A A

Quantum Genetic Algorithm Based On Adaptive Mechanism And Its Applicationon

Posted on:2021-03-19Degree:MasterType:Thesis
Country:ChinaCandidate:S S WangFull Text:PDF
GTID:2428330605467908Subject:Computer technology
Abstract/Summary:PDF Full Text Request
Combinatorial optimization problem has been proved to be NP hard,and its goal is to find the optimal solution from the feasible solutions of many combinations.With the increase of the scale of the problem,the high cost of the conventional precise algorithm in time complexity and space complexity makes it difficult to apply in large-scale combinatorial optimization problems.Intelligent optimization algorithm is an effective approximate algorithm for solving combinatorial optimization problems.It is suitable for solving large-scale practical optimization problems.It can quickly obtain the global approximate optimal solution.It has a very high cost performance ratio in algorithm time and space cost and solution quality,and becomes the main method for solving combinatorial optimization problems.As a typical intelligent optimization algorithm,quantum genetic algorithm(QGA)has the advantages of small population size and strong global search ability.It has been widely used in many fields of combinatorial optimization.Firstly,an adaptive evolutionary mechanism is proposed to improve the performance of quantum genetic algorithm(QGA)in view of the slow convergence speed and easy to fall into the local optimum in the traditional unified evolutionary QGA.In the iterative process of the algorithm,each individual is assigned rotation angle step size and mutation probability suitable for its own evolution according to the current evolution state of the population,so that each individual evolves in the best direction at present,thus speeding up the convergence speed of the algorithm,and improving the ability of the algorithm to jump out of the local optimum through adaptive modulation mutation probability.In addition,in the process of algorithm implementation,a multi-universe parallel structure was employed to achieve parallel operation,which improves the efficiency of the algorithm.The results show that the proposed adaptive quantum genetic algorithm has good performance in convergence and global optimization.Secondly,the proposed quantum genetic algorithm based on adaptive mechanism is applied to solve the multicast resource optimization problem based on network coding,and the multicast routing with minimum coding times is solved.A solvable optimization model and fitness function from network resource optimization to evolutionary algorithm are constructed,and the resource is mapped to chromosome by quantum coding.In addition,in order to further improve the optimization ability of the algorithm,individual similarity evaluation factor,fitness evaluation factor and population variation adjustment factor are introduced on the basis of adaptive evolution mechanism,and the global optimization ability and convergence speed of the algorithm are further improved through multi factor collaborative decision-making.Experimental results show that the improved algorithm has better performance in solving the problem of resource optimization network coding multicast routing.
Keywords/Search Tags:Combinatorial optimization, Quantum genetic algorithm, Adaptive mechanism, Network coding, Multicast routing
PDF Full Text Request
Related items