改进量子进化算法及其在物流配送路径优化问题中的应用

量子进化算法的性能直接受量子旋转门旋转角计算方法的影响.文中提出一种改进量子进化算法,核心是设计了基于量子比特概率幅比值自适应计算量子旋转门旋转角的新方法,算法具有收敛速度快和全局搜索能力强的特点.通过0/1背包问题分析了新方法中相关参数对算法性能的影响,并应用算法求解物流配送路径优化问题,仿真表明改进量子进化算法性能优于量子进化算法和传统进化算法.     

基于量子状态转移算法的作业车间调度问题

针对传统优化方法存在种群多样性受限、寻优能力差等问题,提出一种量子状态转移算法求解作业车间调度问题.构建以最大完工时间最小为目标的数学模型;利用量子状态转移算法进行问题求解,通过状态转移算法中的旋转、伸缩、平移和坐标变换操作对量子旋转角进行更新,从而实现状态转移框架下的量子旋转、量子伸缩、量子平移和量子坐标变换操作;为提高算法的局部和全局探索能力,提出将移位解码和位置交换编码相结合对解空间进行映射,并提出非局部最优解容忍机制可有效避免算法早熟及丰富解的多样性以提高收敛精度.通过对12种基准算例进行仿真,结果表明,该算法与传统算法相比可有效缩短最大完工时间且具有精度高、寻优能力强及可跳出局部最优等优点.     

带最小批量约束的计划问题及其拉格朗日松弛算法

针对一类带最小批量约束的计划问题, 提出了基于拉格朗日松弛策略求解算法. 通过拉格朗日松弛策略, 将原问题转为一系列带最小批量约束的动态经济批量W-W(Wagner-Whitin)子问题. 提出了解决子问题且其时间复杂度O(T³)的最优前向递推算法. 对于拉格朗日对偶问题, 用次梯度算法求解, 获得原问题的下界. 若对偶问题的解是不可行的, 通过固定装设变量, 求解一个剩余的线性规划问题来进行可行化处理. 最后, 数据仿真验证了算法的有效性.     

基于磁阻传感器的旋转弹姿态测量算法研究

在旋转弹高速自旋的情况下,传统角速率陀螺测量滚转角时无法克服角速率量程和测量精度的矛盾,不能准确测量旋转弹弹体姿态。针对这一问题,在保证旋转弹的制导方式高度自主的前提下引入地磁信息,设计了一种高精度、适用于大动态范围的旋转弹姿态测量算法。着重针对滚转角的测量提出了一种新的解算思想,将滚转角以旋转弹横截面内的地磁矢量为界进行分解,并给出了结合地磁测量信息的偏航角、俯仰角计算公式。仿真结果表明:利用测量旋转弹姿态的算法是可行的,且精度高,值得推广。     

基于Oracle罚方法的混合约束差分进化算法

为有效求解复杂约束优化问题,提出了一种基于Oracle的混合约束差分进化算法OBHSaDE.在OBHSaDE算法中,首先对Oracle罚方法进行了改进,并符合约束优化问题的求解要求.利用改进后的Oracle罚方法来快速找到问题的可行域,借助无约束优化算法SaDE能对可行域进行有效搜索,利用序列二次规划的超线性的收敛速度来减少评估次数和提高解的质量.仿真结果表明,改进算法不仅减少了评估次数、提高了解的质量,且具有很好的鲁棒性,还具有较少的用户参数,提高了算法的实用性.OBHSaDE是求解约束优化问题的一种具有竞争力的新方法.     

基于双旋转模板的黑白棋盘角点检测算法

摄像机标定技术已被广泛地应用于三维重建技术中。针对标定时需要手动确认角点比较耗时且可能存在误差的问题,本文提出一种基于双旋转模板的黑白棋盘角点检测算法。该算法首先通过Harris算法获得初始角点,然后通过构造旋转模板对获得的角点进行迭代筛选,最终求解得到符合标定要求的角点。实验证明本文算法不仅具有较高的稳定性,还提高了黑白棋盘上有效角点的检测精度和效率。     

基于改进的CORDIC算法的FFT复乘及其FPGA实现

根据定点FFT中旋转因子所对应的CORDIC旋转方向可预先求解的特点,改进了CORDIC算法中旋转方向的计算方法,在节约乘法器资源的同时兼顾了速度与精度的要求,并基于改进的CORDIC算法,利用FPGA实现了这种FFT复乘模块。仿真结果表明该设计可行,具有一定的实际意义和应用前景。     

基于多参数规划的显式模型预测系统设计的可行域扩张算法

基于约束线性优化控制问题的多参数二次规划求解方法, 提出设计显式模型预测控制系统的可行域逐步扩张算法. 首先建立一种求取优化控制问题输出不变集的迭代算法. 以该输出不变集作为多参数规划问题中状态区域约束限制的初始条件, 通过反复求解多参数规划问题和不断改变状态区域约束限制, 能够逐步扩大显式模型预测控制系统的无限时间可行区域, 直到可行域不再继续扩大. 算法收敛时设计得到的显式模型预测控制系统在其所有的状态分区上都是无限时间可行的. 通过数值仿真计算, 验证本文提出算法的有效性.     

求解多目标优化问题的改进蚁群算法

蚁群算法是一种模拟蚂蚁行为进行优化的启发式优化算法,该算法在许多领域已经得到应用.针对多目标优化问题优化与求解较困难的问题,提出一种嵌入变尺度算法的改进蚁群算法用于求解,为蚁群算法在连续空间中的应用提供了怂一个可行的方案.给出了该算法的详细定义及实现步骤,实例仿真表明,该算法能加快收敛速率,对连续空间的蚁群算法研究具有重要的意义.     

一种角速率输入下二次优化的单子样旋转矢量姿态算法

姿态解算是惯性导航中的关键技术,旋转矢量法可以补偿转动的不可交换性误差。针对多子样旋转矢量算法会降低姿态更新频率的问题,本文提出了一种利用当前以及前一时刻角增量信息和当前以及前N个时刻角速率信息求解更新旋转矢量的单子样角速率旋转矢量姿态算法,并在传统的误差补偿系数圆锥优化方法的基础上,设计了周期项的算法系数优化准则,对周期项的误差补偿系数进行二次优化。实验结果表明,本文提出的角速率输入下二次优化的单子样旋转矢量姿态算法既具有较高的姿态解算精度,又可以将姿态更新频率提高至惯导采样频率,即与N子样旋转矢量算法相比姿态更新频率可提高N倍,具有一定的工程应用价值。     

Quantum-inspired evolutionary algorithms with a new termination criterion, H/sub /spl epsi// gate, and two-phase scheme

From recent research on combinatorial optimization of the knapsack problem, quantum-inspired evolutionary algorithm (QEA) was proved to be better than conventional genetic algorithms. To improve the performance of the QEA, this paper proposes research issues on QEA such as a termination criterion, a Q-gate, and a two-phase scheme, for a class of numerical and combinatorial optimization problems. A new termination criterion is proposed which gives a clearer meaning on the convergence of Q-bit individuals. A novel variation operator H/sub /spl epsi// gate, which is a modified version of the rotation gate, is proposed along with a two-phase QEA scheme based on the analysis of the effect of changing the initial conditions of Q-bits of the Q-bit individual in the first phase. To demonstrate the effectiveness and applicability of the updated QEA, several experiments are carried out on a class of numerical and combinatorial optimization problems. The results show that the updated QEA makes QEA more powerful than the previous QEA in terms of convergence speed, fitness, and robustness.     

求解TSP的新量子蚁群算法

鉴于蚁群算法（ACA）在求解TSP时表现出的优越性,以及量子进化算法（QEA）在求解组合优化问题时表现出的高效性,将ACA与QEA的算法思想进行融合,提出一种新的求解TSP的量子蚁群算法。该算法对各路径上的信息素进行量子比特编码,设计了一种新的信息素表示方式,即量子信息素;采用量子旋转门及最优路径对信息素进行更新,加快算法收敛速度;为了避免搜索陷入局部最优,设计了一种量子交叉策略,以改善种群信息结构。仿真实验结果表明了该算法具有较快的收敛速度和全局寻优能力,性能明显优于ACS。     

A quantum-inspired Tabu search algorithm for solving combinatorial optimization problems

In this study, we propose a novel quantum-inspired evolutionary algorithm (QEA), called quantum inspired Tabu search (QTS). QTS is based on the classical Tabu search and characteristics of quantum computation, such as superposition. The process of qubit measurement is a probability operation that increases diversification; a quantum rotation gate used to searching toward attractive regions will increase intensification. This paper will show how to implement QTS into NP-complete problems such as 0/1 knapsack problems, multiple knapsack problems and the traveling salesman problem. These problems are important to computer science, cryptography and network security. Furthermore, our experimental results on 0/1 knapsack problems are compared with those of other heuristic algorithms, such as a conventional genetic algorithm, a Tabu search algorithm and the original QEA. The final outcomes show that QTS performs much better than other heuristic algorithms without premature convergence and with more efficiency. Also on multiple knapsack problems and the traveling salesman problem QTS verify its effectiveness.     

Quantum computation based bundling optimization for combinatorial auction in freight service procurements

Combinatorial auction is a useful trade manner for transportation service procurements in e-marketplaces. To enhance the competition of combinatorial auction, a novel auction mechanism of two-round bidding with bundling optimization is proposed. As the recommended the auction mechanism, the shipper/auctioneer integrates the objects into several bundles based on the bidding results of first round auction. Then, carriers/bidders bid for the object bundles in second round. The bundling optimization is described as a multi-objective model with two criteria on price complementation and combination consistency. A Quantum Evolutionary Algorithm (QEA) with β-based rotation gate and the encoding scheme based on non-zero elements in complementary coefficient matrix is developed for the model solution. Comparing with a Contrast Genetic Algorithm, QEA can achieve better computational performances for small and middle size problems.     

求解VRPSDP问题的改进模拟退火遗传算法

配送和回收一体化的车辆路径问题（VRPSDP）是一种非常复杂的NP难题。针对这一问题,设计了一种改进的模拟退火遗传算法ISAGA,采用非零自然数编码机制和弱可行解到强可行解的解码机制,将3PM交叉算子和退火选择相结合,形成贪心3PM交叉算子,引进insert 、swap和2-opt分别对解进行迭代优化,并将模拟退火算法和遗传算法巧妙地结合,使得遗传算法在前期发挥着全局搜索的强大功能;后期用模拟退火算法来处理遗传算法前期的全局较优解,充分利用模拟退火算法后期局部搜索的强大功能。经过国际公认的测试算例验证,ISAGA算法在Min算例、Salhi和Nagy算例中均找到了比现有算法已知最好解更优的解。     

基于自适应机制的多宇宙并行量子衍生进化算法

进化参量的选取对量子衍生进化算法(QEA)的优化性能有极大的影响,传统QEA在选择进化参量时并未考虑种群中个体间的差异,种群中所有个体采用相同的进化参量完成更新,导致算法在解决组合优化问题中存在收敛速度慢、容易陷入局部最优解等问题。针对这一问题,采用自适应机制调整QEA的旋转角步长和量子变异概率,算法中任意一代的任一个体的进化参量均由该个体自身适应度确定,从而保证尽可能多的进化个体能够朝着最优解方向不断靠近。此外,由于自适应量子进化算法需要评估个体的适应度,导致运算时间较长,针对这一问题则采用多宇宙机制将算法分布于多个宇宙中并行实现,从而提高算法的执行效率。通过搜索多峰函数最优解和求解背包问题测试算法性能,结果表明,与传统QEA相比,所提出算法在收敛速度、搜索全局最优解及执行速度方面具有较好的表现。     

Design of an improved quantum-inspired evolutionary algorithm for a transportation problem in logistics systems

Logistics faces great challenges in vehicle schedule problem. Intelligence Technologies need to be developed for solving the transportation problem. This paper proposes an improved Quantum-Inspired Evolutionary Algorithm (IQEA), which is a hybrid algorithm of Quantum-Inspired Evolutionary Algorithm (QEA) and greed heuristics. It extends the standard QEA by combining its principles with some heuristics methods. The proposed algorithm has also been applied to optimize a problem which may happen in real life. The problem can be categorized as a vehicle routing problem with time windows (VRPTW), which means the problem has many common characteristics that VRPTW has, but more constraints need to be considered. The basic idea of the proposed IQEA is to embed a greed heuristic method into the standard QEA for the optimal recombination of consignment subsequences. The consignment sequence is the order to arrange the vehicles for the transportation of the consignments. The consignment subsequences are generated by cutting the whole consignment sequence according to the values of quantum bits. The computational result of the simulation problem shows that IQEA is feasible in achieving a relatively optimal solution. The implementation of an optimized schedule can save much more cost than the initial schedule. It provides a promising, innovative approach for solving VRPTW and improves QEA for solving complexity problems with a number of constraints.     

A study on a quantum-inspired evolutionary algorithm based on pair swap

A quantum-inspired evolutionary algorithm (QEA) is proposed as a stochastic algorithm to perform combinatorial optimization problems. The QEA is evolutionary computation that uses quantum bits and superposition states in quantum computation. Although the QEA is a coarse-grained parallel algorithm, it involves many parameters that must be adjusted manually. This paper proposes a new method, named pair swap, which exchanges each best solution information between two individuals instead of migration in the QEA. Experimental results show that our proposed method is a simpler algorithm and can find a high quality solution in the 0-1 knapsack problem. This work was presented in part at the 12th International Symposium on Artificial Life and Robotics, Oita, Japan, January 25–27, 2007     

一种改进的量子进化算法及其在乡村邮路问题的应用

针对基本量子进化算法易陷于局部最优解的缺陷,提出一种改进的量子进化算法(QEA)。结合乡村邮路问题,对算法进行了测试,结果表明,改进算法在全局寻优能力和种群多样性方面比基本量子进化算法有所改进,是求解乡村邮路问题的一种有效算法。