Quantum-Inspired Evolutionary Algorithm And Its Application In Image Sparse Decomposition

The quantum-inspired evolutionary algorithm (QIEA) is a novel kind of evolutionary algorithms (EAs) combining the quantum computing and EAs. The QIEA adapts from on the concepts and principles of quantum computing, such as quantum bits, quantum gates and quantum superposition. Compared with conventional EAs, the QIEA has better balance between exploration and exploitation, stronger global search capability and faster convergence. Furthermore, the QIEA is able to explore the search space with a small number of individuals. However, there are some key issues in QIEA, such as how to select quantum gate (Q-gate), applying it to engineering applications, convergence analysis, and combining it with other EAs, which are well worthy of further investigation and discussion.Until now, the QIEA has been applied to the problem of image processing. However, the application and research of the QIEA in the field of image sparse decomposition are still at early stage. Therefore, this paper presents a QIEA in application to realize the best approximation of the image sparse decomposition, which expands the application of QIEA. The main work and research fruits are as follows:1. The investigation about QIEA and image sparse decomposition is summarized and analyzed. The problems need to be solved are also pointed out.2. The basic theory and related concepts of quantum computing are introduced. The basic theory of QIEA and its structure are discussed, and its brief description is presented.3. The principle of image sparse decomposition and the dictionary of image atoms are introduced. The implementation process of image sparse decomposition and its evaluation criteria are given. Then in order to reduce the computational complexity of conventional spare decomposion, the fast MP algorithm based on the QIEA is presented. On this basis, six images are sparsely decomposed, and the decomposing results are analyzed in detail. Experimental results show that the QIEA can release the computational burden to improve the efficiency of image sparse decomposition. Besides, in order to verify the impact of parameters on the performance, extensive experiments conducted on image sparse decomposition based on QIEAs under different circumstance, such as different population size, different maximal evolutionary generation and different maximal number of decomposing iterations, are carried out. The experiment results provide a reference for the choice of experiment parameters.4. A quantum rotation gate (QR-gate) is the key operator in a QIEA. In the literature, there are six versions of QR-gates. How to evaluate and choose a QR-gate is very worth discussing. However, relatively little work has been done on the comparisons and evaluations of these QR-gates. Therefore, the survey and investigation about these QR-gates are discussed. Firstly, a brief introduction of six main quantum rotation gates is given. Subsequently, the comparison and analysis of these six QR-gates are discussed, and their advantages and disadvantages are summarized. Finally, the performances of QIEAs with the six different QR-gates are tested on the problem of image sparse decomposition. The comparative results can be used as a reference for the further investigation on QIEAs.5. In order to abtain a better search method and reduce the computational complexity of the image sparse decomposition, a hybrid search algorithm (HQIDA) based on QIEA and improved differential evolution (IDE) is proposed, and then applied to image sparse decomposition. The fast MP based on the HQIDA is proposed to settle the issue of high computational complexity of the conventional MP approach. This fast algorithm can quickly search the best atom from the over-complete dictionary of atoms, and achieve the image decomposition quickly. Experimental results show that the HQIDA is feasible and effective.This work is supported partially by the National Natural Science Foundation of China (60702026), the Scientific and Technological Funds for Young Scientists of Sichuan (09ZQ026-040) and the open Research Fund of Key Laboratory of Signal and Information Processing, Xihua University (SZJJ2009-003).