微处理机
微處理機
미처리궤
MICROPROCESSORS
2015年
3期
31-33
,共3页
改进%博弈论%蚁群算法%旅行商问题
改進%博弈論%蟻群算法%旅行商問題
개진%박혁론%의군산법%여행상문제
Improved%Game theory%Ant colony optimization%Travelling Salesman Problem
TSP 问题是一个组合优化问题,该问题具有 NP 计算复杂性,运用量子蚁群算法求解该问题时易陷入局部最优和收敛速度慢的问题。因此提出一种基于博弈论的量子蚁群算法(GQA-CA),该算法采用重复博弈模型,在重复博弈中产生一个博弈序列,使得每次博弈都能够产生最大效益,并得到相应博弈过程的纳什均衡。把该算法应用于 TSP 求解,实验结果表明本文中 GQACA算法的收敛精度和稳定性均要优于其他量子蚁群算法。
TSP 問題是一箇組閤優化問題,該問題具有 NP 計算複雜性,運用量子蟻群算法求解該問題時易陷入跼部最優和收斂速度慢的問題。因此提齣一種基于博弈論的量子蟻群算法(GQA-CA),該算法採用重複博弈模型,在重複博弈中產生一箇博弈序列,使得每次博弈都能夠產生最大效益,併得到相應博弈過程的納什均衡。把該算法應用于 TSP 求解,實驗結果錶明本文中 GQACA算法的收斂精度和穩定性均要優于其他量子蟻群算法。
TSP 문제시일개조합우화문제,해문제구유 NP 계산복잡성,운용양자의군산법구해해문제시역함입국부최우화수렴속도만적문제。인차제출일충기우박혁론적양자의군산법(GQA-CA),해산법채용중복박혁모형,재중복박혁중산생일개박혁서렬,사득매차박혁도능구산생최대효익,병득도상응박혁과정적납십균형。파해산법응용우 TSP 구해,실험결과표명본문중 GQACA산법적수렴정도화은정성균요우우기타양자의군산법。
TST,as a combinatorial optimization problem,is solved by Quantum ant colony algorithm which is easy to fall into the local optimum and slow convergence.The quantum ant colony algorithm, based on game theory (GQACA),is put forward in this paper.It uses the repeated game to create the repeated game sequence for maximum benefit in each game,and get the corresponding game process of Nash equilibrium.The typical test functions are used for GQACA algorithm optimization performance experiment testing.The experimental results show that the GQACA convergence precision and stability of the algorithm are better than QACA algorithm and ACA one.