PDF《量子竞争决策算法及其在旅行商问题中的应用》

收稿日期: 2009唱06唱23;

修回日期: 2009唱07唱29 基金项目: 国家自然科学基金资助项目(70871081);

上海市重点学科建设资助项目 (S30504);

上海市研究生创新基金资助项目(JWCXSL0902) 作者简介:刘勇(1982唱),男,江苏淮安人,博士研究生,主要研究方向为智能优化、系统工程( liuyong.

seu@163. com);

马良(1964唱),男,上海 人,教授,博导,主要研究方向为智能优化、系统工程;

宁爱兵(1972唱),男,湖南邵东人,讲师,博士,主要研究方向为组合优化算法. 量 子竞 争决 策算法及其在旅 行商 问题 中的 应用 倡刘勇1,2 , 马良1,宁爱兵

1 (1畅上海理工大学 管理学院, 上海 200093;

2畅盐城工学院 基础教学部, 江苏 盐城 224051) 摘要: 提出一种新型优化算法― ― ―量子竞争决策算法,在竞争决策的基础上,将进化博弈论中博弈者不断学 习和调整来提高竞争力的思想引入到优化中,使竞争者具有自进化能力,同时充分利用量子进化计算中量子比 特、叠加态等理论,增加竞争群体的多样性,缩小群体规模. 通过对典型的 TSP 实验计算和与其他算法比较,均 取得了较好的效果,算法具有较强的全局优化能力. 关键词: 竞争决策;

进化博弈;

量子进化;

旅行商问题 中图分类号: TP301畅6文献标志码: A 文章编号: 1001唱3695(2010)02唱0586唱04 doi:10.

3969 / j. issn. 1001唱3695. 2010. 02.

051 Quantum competitive decision algorithm and its application in TSP LIU Yong 1,2 , MA Liang

1 , NING Ai唱bing

1 (1畅School of Management, University of Shanghai for Science & Technology, Shanghai 200093, China;

2畅Dept.of Fundamental Science Teaching, Yancheng Institute of Technology, Yancheng Jiangsu 224051, China) Abstract: This paper proposed a novel optimization algorithm―quantum competitive decision algorithm. Based on competition and decision, the algorithm introduced the theory of continuous learning and adjustment to improve the competitiveness in evo唱lutionary game theory into optimization, making competitors possess the ability of self唱optimizing. The algorithm made full use of quantum bit, superposition state and other concepts in quantum evolutionary algorithm to increase the diversity of competi唱tors and reduce the population size. Experiments on typical TSP and comparisons with other methods show the new algorithm is more efficient and the algorithm has strong capability of global optimization. Key words: competition and decision;

evolutionary game;

quantum evolutionary;

TSP

0 引言 最优化方法在工程技术、科学研究和经济管理等诸多领域 中有着广泛的应用,随着目标问题的复杂性越来越强,对高效 的优化技术的需求日益迫切,探寻适合复杂计算的具有智能特 征的算法已成为研究热点. 竞争决策算法是近年来提出的一种新型优化算法,是在分 析大自然生物世界特别是人类的各种竞争机制和决策原理的 基础上,利用竞争造就优化和决策左右结果的特性而得出的一 种寻优算法,能广泛用于求解组合优化问题 [1 ~ 4] . 但在优化过 程中,竞争者缺少学习和自进化能力,无法实现进化过程中的 动态调整更新,同时定义的竞争力函数个数较多,影响算法的 求解速度和求解问题的规模. 进化博弈论是博弈论的新发展,是一种博弈学习的动态演 化理论,已成功用于生物、经济等领域. 其思想来源于生物进 化理论,按照生物在进化过程中生物性状和行为特征的复制动 态的思想,进化博弈论中竞争者在博弈过程中不断学习和调整 策略,提高自身的竞争能力 [5] . 基于进化博弈论的思想,将竞争决策和量子进化算法相结 合,提出一种新型优化算法― ― ―量子竞争决策算法. 定义每个 竞争者携带一组表示当前解信息的量子比特,采用量子旋转门 更新竞争者携带的量子比特,实现每个竞争者的学习和策略调 整过程,在竞争的同时完成自身的进化;

同时将量子计算中量 子比特、叠加态等理论与竞争者相结合,增加竞争者的多样性, 缩小竞争群体的规模,加快算法的收敛速度.

1 算法分析 1畅1竞争决策算法 竞争决策算法通过构造一个或多个竞争者参与到对一个 或多个资源的竞争过程中,通过优胜劣汰的决策原则使一部分 竞争者获得资源而增加实力,另一部分竞争者失去资源而减弱 实力甚至死亡. 对竞争决策算法的结果有较大影响的因素有 以下几种: a)竞争规则. 它是竞争决策算法中竞争者必须要满足的条件,它包括以 下三种条件: (a) 初始条件,在开始进行竞争时必须满足的条件. (b) 竞争条件,在竞争过程中始终必须满足的条件. (c) 终止条件,在竞争过程中若满足该条件就可终止当前 的一次竞争决策,此时竞争者各方达到一个竞争平衡状态,即 此时每个竞争者都不能凭自己的实力从竞争对手手中抢占 资源. 第27 卷第

2 期2010 年2月计算机应用研究Application Research of Computers Vol.

27 No.

2 Feb.2010 b)竞争力函数. 该函数代表竞争者对某种资源具有的竞争力,一般来说, 竞争力函数大的竞争者占有该资源的可能性要大. c)决策函数. 该函数起到裁判的作用,它根据每个竞争者竞争力函数值 的大小来决定把资源分配给哪一个竞争者,如可将决策函数定 义成把某资源分配给对该资源具有最大竞争力的竞争者. d)初始格局. 它是指在某一轮竞争开始前各个竞争者对资源的占有情 况和竞争者的实力情况. 这些因素中的某一个单独发生变化或者组合发生变化都 会对竞争和决策的结果产生较大的影响,对同一个问题来说竞 争规则一般只有一个. 为了取得较好的效果,可能对同一个问 题采用多个竞争力函数、多个决策函数和多个初始格局的组合 来实现多轮竞争,最后取竞争和决策效果最好的值作为优化 值[1 ~ 4] . 1畅2量子进化算法 量子进化算法是一种基于量子计算思想的概率进化算法, 吸取了量子计算中的量子比特、叠加态等概念,有更好的群体 多样性和优化能力. 基本的量子进化计算概念如下: a)量子位. 比特是经典计算和经典信息的基本概念,量 子计算与量子信息建立在类似的概念量子比特或量子位的基 础上 [6] . 量子位或量子比特是量子计算中保存信息的最小单 元,一个量子位可能处于| 1也可能处于| 0,或者两种状态的 线性叠加. 因此一个量子位可以表示为 | φ =α|0 +β |

1 其中:α和β分别表示| 0和 | 1的概率幅,| α |

2 表示量子位处 于| 0概率,| β |

2 表示量子位处于| 1的概率. 量子比特的状 态是二维复向量空间中的向量,特殊的 | 0和|1状态称为计 算基态,是构成这个向量空间的一组正交基. | α |

2 +| β |

2 = 1, 因为概率和一定是 1,同时从几何意义上看,是要求量子比特 的状态归一化到长度

1 [6] . b)量子个体. 在量子进化算法中,量子个体定义为由量 子比特组成的串: α

1 β

1 α

2 β

2 … … α m β m m 为个体长度,[α i ,β i ] T 为第 i 个量子位的概率幅(i = 1,2, …,m) ,一个长度为 m 的个体能表示

2 m 个状态的叠加. 如一 个三个量子位编码的量子个体

1 2

1 2

1 2 -

1 2

1 2

3 2 则表示的个体状态为

1 4 | 000+34|001-14|010-34|011+14|100+34|101-14|110-34|111 表明状态| 000,| 001, | 010, | 011, | 100, | 101, | 110和 |

111 的概率分别为

1 / 16,3 / 16,1 / 16,3 / 16,1/ 16,3 / 16,1/

16 和3/16. 这种特性使量子进化计算能以较小的群体规模获得 较好的优化结果. c)量子门. 该量子门的设计有多种形式,但由于概率归 一化的要求,变换矩阵必须满足酉正矩阵,酉性限制是对量子 门的惟一限制. 常用的有非门、受控非门、Hadamard 门、量子 旋转门等. 量子门是实现算法进化操作的执行机构,通过量子 门算子使量子比特的概率幅发生变化,推动量子个体向最优解 方向演化. d)测量. 它是指根据量子比特的概率幅 | β |

2 来生成二进 制解. 具体做法为:随机产生一个[0,1]上的数 r,若r