CAJ | 학술논문

该文用量子近似动态规划解大规模机组组合问题.利用量子叠加态可表示海量信息的特性,把大规模的0-1机组组合状态用量子叠加态表示,将量子旋转门作为量子叠加态的搜索策略,实现了近似动态规划对海量机组组合状态空间的全局搜索.使用量子测量塌缩原理解Bellman方程,提高了方程的求解效率.用量子平均收敛概率改进迭代中断条件,避免了算法的过度迭代.10~1000机系统的计算结果表明:该文算法能有效地搜索大规模状态空间,产生解Bellman方程所必须的预决策状态;可在多项式时间内获取高质量的解,与外-内逼近法相比最优值的平均偏差小于1/100;所解系统的规模较传统动态规划法增加10倍以上,克服了"维数灾"问题.用量子计算理论克服近似动态规划遇到的状态空间搜索难等问题是可行的,算法具有广阔的应用前景.
해문용양자근사동태규화해대규모궤조조합문제.이용양자첩가태가표시해량신식적특성,파대규모적0-1궤조조합상태용양자첩가태표시,장양자선전문작위양자첩가태적수색책략,실현료근사동태규화대해량궤조조합상태공간적전국수색.사용양자측량탑축원리해Bellman방정,제고료방정적구해효솔.용양자평균수렴개솔개진질대중단조건,피면료산법적과도질대.10~1000궤계통적계산결과표명:해문산법능유효지수색대규모상태공간,산생해Bellman방정소필수적예결책상태;가재다항식시간내획취고질량적해,여외-내핍근법상비최우치적평균편차소우1/100;소해계통적규모교전통동태규화법증가10배이상,극복료"유수재"문제.용양자계산이론극복근사동태규화우도적상태공간수색난등문제시가행적,산법구유엄활적응용전경.
The quantum inspired approximate dynamic programming (QI-ADP) algorithm was applied to solve the large-scale unit commitment (UC) problems. The large numbers of 0-1 states in the large-scale UC problem were expressed with the quantum superposition state effectively by means of its ability in storing massive information. Using the quantum rotation gate as the search strategy for the quantum superposition state, the QI-ADP algorithm implemented the global search in the space of the massive states of the UC problem. Meanwhile, the principle of the quantum collapsing was applied to solve the Bellman equation with a higher efficiency. To avoid the over-iteration, the average convergence probability was used to improve the iteration interrupt condition of the QI-ADP algorithm. The calculated results of the test systems from 10 units to 1000 units show that the QI-ADP algorithm can efficiently search in the space of large-scale states to generate the necessary pre-decision states for solving the Bellman equation. Furthermore, the QI-ADP algorithm can obtain the high-quality solutions within a polynomial time. The average deviations of the optimal values between the QI-ADP and the outer-inner approximation approach are less than 1%. On the other hand, the QI-ADP algorithm can solve large-scale UC problems successfully, and the size of the UC problems is over 10 times larger than that by using the classic dynamic programming. Moreover, the QI-ADP algorithm has overcome the problem of "curse of dimensionality". Therefore, it is feasible using the principle of quantum computing to overcome some practical disadvantages in ADP, such as the difficulty of searching in the state space. Consequently, the QI-ADP algorithm has very broad application prospects.