【作者】 丰小月；

【导师】 梁艳春；

【作者基本信息】 吉林大学 ， 计算机应用技术， 2008， 博士

【摘要】 智能优化算法,如人工神经网络、遗传算法、模拟退火、粒子群算法及其优化策略等,通过模拟或揭示某些自然现象或过程而得到发展,其内容涉及数学、物理学、生物进化、人工智能、神经科学和统计力学等方面,为解决复杂问题提供了新的思路和手段。量子计算利用了量子理论中有关量子态的叠加、纠缠和干涉等特性,通过量子并行计算使得某些在经典计算机上计算复杂度很高的问题有可能降低其复杂度。由于量子计算机尚未实现,因此如何在传统计算机利用量子计算也是一个研究的热点。本文将量子机制引入到智能优化算法中,提出几种改进的优化算法,希望利用量子机制的优点,进一步提高优化算法的求解能力及运算效率。具体内容如下:(1)将量子机制与进化算法结合,根据旅行商问题的特点,尝试将量子进化算法应用于求解小规模旅行商问题,实验结果表明量子进化算法求解旅行商问题的可行性。(2)提出一种量子群进化算法模型,引入量子角的概念,将量子机制与粒子群算法相结合,用于求解背包问题,得到了令人满意的结果。(3)提出一种量子组合优化算法模型,将量子进化算法同智能优化算法结合,求解两类组合优化问题。(4)根据可满足性问题的特点,进一步改进量子组合优化算法,并应用于求解3-SAT问题。(5)提出了AFTER_PSO算法,并且将其应用于股票及太阳黑子数据的预测问题上,结果表明了算法的可行性与有效性。本文的研究结果丰富了智能优化算法的研究,提高了智能优化算法求解一类优化问题的效率,同时为如何在传统计算机上应用量子机制研究提供了一种参考。更多还原

【Abstract】 Optimization technique is based on mathematics and used to find the optimum solutions of many engineering problems. Since 1980’s, the industry control has been developing in the direction of large-scale, sequential, compositive and intricate process. Owing to the feature of complexity, constraint, nonlinearity, multi-local minimum and difficulty to model, optimality calculation of all kinds of process control is an urgent problem that needs to be solved. So it has become a primary research direction in the related subject and field to research intelligent algorithms for solving large-scale parallel problems.Intelligent optimal algorithm is an important branch of artificial intelligent field. With the flourishing development, the research of intelligent computation is very active. The intelligent computation is also called“soft computing”. It is developed by simulating or revealing some phenomenon and process of nature. Nature is the source of human creativity. For recent years, the research of intelligent optimization algorithms is currently a focus in the advanced field. These algorithms include artificial neural network (ANN), genetic algorithm (GA), simulated annealing (SA), particle swarm optimization (PSO), ant colony optimization (ACO), artificial immune system (AIS), etc., which are developed by simulating or revealing some phenomenon and process of nature. They provide innovative thought and means to solve many complicated problems. These algorithms enrich the optimization technique and provide workable solutions for some traditional combinatorial optimization problems.Quantum computation was proposed by Benioff and Feynman in the early 1980s. Quantum algorithms exploit the laws of quantum mechanics in order to perform efficient computation. Due to its unique computational performance, the quantum computation has attracted extensive attention of researchers. The characteristic of quantum world has made the quantum system break the limit of classical information system. Quantum computer can easily break existing cryptosystem and lead the revolution of the cryptosystem. It will influence all the departments of defense and the whole society.Based on the intelligent optimal algorithms, quantum mechanism is introduced, some improvements are made and different algorithms are combined. The major contents could be summarized as follows:(1) Quantum-inspired evolutionary algorithm (QEA) is the combination of quantum mechanism and evolutionary algorithm. It is based on the concept and principles of quantum computation, such as quantum bit and superposition of states. The chromosomes are coded by qubit. This probabilistic presentation can make one chromosome to present information of several states. The quantum gate is adopted to evolve superposition states. It can keep the diversity of population and avoid the pressure of choice. The information of current best individual can lead mutation which makes the population evolve to excellent schema with a large probability. According to the characteristic of travelling salesman problem, the QEA is adopted to solve small scale travelling salesman problem. The results show that using the QEA to solve travelling salesman problem is feasible.(2) Based on quantum evolutionary algorithm and particle swarm optimization, a novel quantum swarm evolutionary algorithm (QSE) is presented. A new definition of Q-bit expression called quantum angle is proposed, and an improved particle swarm optimization is employed to update the quantum angles automatically. The simulated results in solving 0–1 knapsack problem show that QSE is superior to traditional QEA. In addition, the comparison experiments show that QSE is better than many traditional heuristic algorithms, such as climb hill algorithm, simulation anneal algorithm and taboo search algorithm.(3) A quantum evolutionary combinatorial algorithm is presented based on the quantum-inspired evolutionary algorithm and conventional evolutionary algorithms. There are two phases and two different groups GroupI and GroupII in the proposed algorithm. In the first-phase, GroupI with population size n is optimized by the quantum-inspired evolutionary algorithm. And the GroupII with population size 2n is optimized in the second-phase. In each generation, there are n individuals of the GroupII derived from GroupI. Meanwhile, the best solution from GroupII is used to guide the update of a quarter of individuals of the GroupI. To demonstrate the effectiveness and applicability of the proposed approach, several experiments are performed on function optimization and 0-1 knapsack problems. The compared results with the quantum-inspired evolutionary algorithm show that the proposed quantum combinatorial optimal algorithm is more powerful in the aspects of population diversity, convergence speed and the ability of global optimization.(4) The satisfiability problem (SAT) is the basic NP-hard problem in the field of computer science. As one of the six basic core NP-complete problems, it is the basic for many theoretical problems, for example, symbolic logic, reasoning, machine learning. Besides its theoretical importance, SAT has a large number of practical applications such as VLSI test and verification, design of asynchronous circuits, sports planning and so on. In this paper, we propose the improved quantum-inspired evolutionary algorithm and, extending the application field of the QEA, use it to solve the 3-SAT problem. The quantum angle is adopted in the improved algorithm. And a new quantum rotation gate strategy is adopted to update the population. Furthermore, to accelerate the convergence speed, the particle swarm optimization is combined with the IQEA. Experimental results show that the improved algorithm is feasible and effective for solving 3-SAT problems. It can be as a new incomplete method to solve satisfiability problems.(5) A modified particle swarm optimization (PSO) algorithm is proposed. Linear constraints in the PSO are added to satisfy normalization conditions for different problems. A hybrid algorithm based on the modified PSO and aggregated forecast through exponential re-weighting (AFTER) is presented. The AFTER is adopted to initialize the weight of different problem. Then the improved PSO is adopted to optimize the population. The AFTER accelerate the search speed of PSO and the global and local search ability of PSO avoid the possibility of local optimal of Bayesian probability. Combining forecasting can improve the forecasting accuracy through combining different forecasting methods. The effectiveness of the algorithm is demonstrated through the prediction on the sunspots and the stocks data. Simulated results show that the hybrid algorithm can improve the forecasting accuracy to a great extent.The research of this article has enriched the study of intelligent optimal algorithm and developed the efficiency of solving combinational problems. And it also provides a reference on how to apply quantum mechanism to classical computer.更多还原