量子遗传算法的改进及在货物配装问题中的应用

发布时间：2019-02-10 20:01

【摘要】：量子遗传算法是将量子算法和遗传算法相结合起来的一种高效的智能优化算法,除具有遗传算法的优点外,还具有全局寻优能力强、收敛速度快、种群规模小等优点。对于复杂优化问题的求解,量子遗传算法是一种有效的解决方法。但是量子遗传算法在复杂函数优化问题上存在迭代次数多、收敛速度慢、较易陷入局部最优解的不足。为此本文对传统的量子遗传算法作改进,主要研究工作如下：一是提出了一种改进的量子遗传算法(IQGA),采用动态策略调整量子旋转角,加快量子搜索的收敛速度；在量子旋转策略中动态嵌入变异算子,增加种群的多样性,并通过灾变算子使算法及时跳出局部最优点,避免早熟收敛。二是在IQGA的基础上提出了一种基于多种群的改进量子遗传算法(MPIQGA),使用多种群替代单种群,同时在种群初始化过程中采用小生境协同策略来均匀划分量子位空间,使各子种群均匀分布到解空间,有利于保持种群的多样性,各种群之间通过全局最优个体来更新进化目标的形式联系。多种群的并行搜索可以加快搜索速度,缩短迭代次数。实验首先通过若干个复杂连续函数验证改进量子遗传算法的可行性和有效性。物流配送中的货物配装问题属于工程领域的约束优化问题,本文利用IQGA和MPIQGA对一种多车型多货物配装问题模型进行求解,其中对该模型的约束条件进行变形,转化成惩罚函数添加到适应度函数里,并加入整车合并思想,能够有效的减少所需配装车辆的数量。实验结果说明新算法用于解货物配装问题是可行的、有效的,新算法具有一定应用价值。
[Abstract]:Quantum genetic algorithm (QGA) is an efficient intelligent optimization algorithm which combines quantum algorithm with genetic algorithm. In addition to the advantages of genetic algorithm, quantum genetic algorithm also has the advantages of strong global optimization ability, fast convergence speed and small population size. Quantum genetic algorithm (QGA) is an effective method for solving complex optimization problems. However, quantum genetic algorithm (QGA) has the disadvantages of many iterations, slow convergence rate and easy to fall into local optimal solution in complex function optimization problems. The main research work of this paper is as follows: firstly, an improved quantum genetic algorithm (IQGA),) is proposed to adjust the quantum rotation angle by dynamic strategy to speed up the convergence of quantum search. The mutation operator is dynamically embedded in the quantum rotation strategy to increase the diversity of the population, and the catastrophe operator is used to make the algorithm jump out of the local optimum in time and avoid premature convergence. Secondly, based on IQGA, an improved quantum genetic algorithm (MPIQGA),) based on multiple populations is proposed, in which multiple groups are used to replace single population, and niche coordination strategy is used to divide the qubit space evenly in the process of population initialization. The uniform distribution of each subpopulation to solution space is conducive to maintaining the diversity of the population and updating the formal association of evolutionary objectives by the globally optimal individual among the various groups. Parallel search for multiple clusters can speed up the search and shorten the number of iterations. Firstly, the feasibility and effectiveness of the improved quantum genetic algorithm are verified by several complex continuous functions. The cargo loading problem in logistics distribution belongs to the constrained optimization problem in the field of engineering. In this paper, we use IQGA and MPIQGA to solve a model of multi-model and multi-cargo loading problem, in which the constraint conditions of the model are deformed. The penalty function is added to the fitness function, and the whole vehicle merging idea is added, which can effectively reduce the number of vehicles that need to be installed. The experimental results show that the new algorithm is feasible and effective in solving the cargo loading problem, and the new algorithm has certain application value.
【学位授予单位】：广西大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP18

【参考文献】