Multi-universe Parallel Quantum-inspired Multi-objective Evolutionary Algorithm Research And Its Application

Quantum-inspired Evolutionary Algorithm (QEA) is a novel kind of probability seach algorithm by combining quantum theory with evolutionary algorithm. Based on the principles of Quantum Computing, QEA uses Q-bit string as the probabilistic representation of solutions and Q-gates as variation operators to drive evolutionary searching. Compared with traditional EAs, QEA can balance between exploration and exploitation better. Additionally it is characterized by small population size, rapid convergence and strong global search capability.As what the research results show, QEA has better performances than conventional EAs on many problems, but it tends to run into local optima in solving some complex optimization problems, and fundamentally the problem of QEA's premature convergence has still not been solved. Meanwhile, the general QEA still evolves based on the single group at present and doesn't make full use of the characteristicis of quantum's multi-universe. To improve QEA well, the idea that many universes have been used and cooperate together in algorithm may be the possible resolvent.Consequently, a novel Quantum-inspired Multi-objective Evolutionary Algorithm is proposed inspired by quantum computing, which is named multi-universe parallel quantum-inspired multiobjective evolutionary algorithm (MPQMEA). In order to get more efficient convergence, this paper divides all individuals into some independent sub-colonies, called universes, according to their definite topological structure. The uniform assignment principle of target individuals and dynamic adjusting rotation angle mechanism are applied to update each universal individual. Information among the universes is exchanged by adopting the best emigration. To make good use of global information, the best reservation scheme is designed for the improvement of search efficiency.In theory, we prove the convergence of the algorithm based on the partial set theory and probability theory.Meanwhile, Multi-objective 0-1 knapsack problem is a complex NP hard problem. It can be used to test whether the multi-objective evolutionary algorithm is good or not. In this paper, the algorithm we proposed is applied to nine 0-1 knapsack problems and a series of experiment results on the knapsack problems show that MPQMEA can be more close to the Pareto front in the same running time, and its Pareto solutions has better distribution. These experiments fully verify the effectiveness of the algorithm.At the practical applications, we applied the algorithm to the water resource allocation. Based on MPQMEA, a reasonable method has been proposed. Its application for water resource allocation in the area shows that the proposed method is feasible.