Study Of Quantum Intelligent Optimization Algorithm On Steiner Tree In Network

With the progress of network and multimedia technology, network multimedia services such as video conferencing, video on demand, data distribution and online gaming applications become the mainstream of network applications. Most of these applications require large amounts of bandwidth and other network resources, multicast is just the effective way to solve these problems. To save bandwidth and improve the utilization of network resources, constructing the minimum cost Steiner tree become a critical issue. Traditional algorithms for solving Steiner tree usually search end-to-end paths first, and then merge them into a tree. Too much repetitive work is done in these algorithms, so the efficiency is not high. Intelligent optimization algorithms, such as ant colony optimization and particle swarm optimization algorithm, with the advantages of distributed parallelism and good optimization ability, are increasingly used to solve Steiner tree and achieved good results. However, there remains some deficiencies such as slow convergence, computational complexity, premature convergence and so on.In recent years, the quantum algorithm with the advantage of high degree of parallelism, exponential storage capacity and speeding up other algorithms, was proposed to solve Steiner tree, this can either improve the performance of the original algorithm, but also broaden the application of quantum algorithm. Meanwhile, in order to combine the advantages of intelligent algorithms and quantum algorithm, we comply with the thinking of combinational optimization, combine them to propose a new algorithm to solve Steiner tree in network, play the role of acceleration of quantum algorithm, overcome the premature convergence, improve the global optimization ability and speed up the convergence. This paper mainly studied the application of quantum and its intelligent optimization algorithm in solving Steiner tree problem in network, details are as follows:First, an improved quantum algorithm based on the basic one is proposed to solve Steiner tree. In this algorithm, the edges are represented by quantum bit, and the probability amplitude represents the probability of being selected in Steiner tree, quantum bit was observed to generate a solution. Traditional algorithms usually search end-to-end paths and then merge them into a tree, too much work was done and the efficiency is not high. The improved algorithm can enhance the capacity of global optimization and accelerate the convergence speed. The simulation results shows that new algorithm can greatly reduce the convergence time, improve the efficiency and get better solutions compared to the traditional ones, especially when the scale of network becomes larger.Secondly, to combine the advantages of intelligent optimization and quantum algorithm and comply with the principle of combination and optimization, and based on ant colony optimization and particle swarm optimization, we proposed quantum ant algorithm and quantum particle swarm algorithm to solve Steiner tree problem. In quantum ant colony optimization algorithm, QACO, the ant release pheromones in the current point not in the path, and use the probability amplitude to represent the current point, adopt quantum gates to move the ant, and achieve mutation by quantum non-doors. In QPSO, the quantum evolution was introduced into PSO, and use quantum bit to represent the current position, and use the quantum gates to search the optimal position and avoid premature convergence by permuting the position through quantum non-gate. The simulation results show that, compared with the original algorithms, the new algorithm can enhance the ability of global optimization, speed up the convergence rate, avoid premature convergence, and improve the performance of original algorithms. The performance is more obvious when the scale of topology becomes larger.