第３３卷第７期 计算机应用研究 Ｖｏ１．３３ Ｎｏ．７ ２０１６年７月 Ａｐｐｌｉｃａｔｉｏｎ Ｒｅｓｅａｒｃｈ ｏｆ Ｃｏｍｐｕｔｅｒｓ Ｊｕ１．２０１６ 动态搜索空间的粒子群算法 张水平，王碧 （江西理工大学信息工程学院，江西赣州３４１０００） 摘要：为进一步缓解粒子群优化算法在后期收敛速度慢、早熟等问题，提出了一种挂载式的、依赖自适应阈值 和已知全局最优解的压缩搜索空间策略。在此基础上对粒子重新分配初始位置、调整速度权值来提升算法的后 期探索能力。实验表明，在使用相同的权重和学习因子策略时，比之原粒子群优化算法具有较好的表现，在对量 子粒子群算法进行嵌入时依然具有一定效果。该策略可以有效避免早熟问题，提升算法在后期的寻优效果，具 有较好的鲁棒性。 关键词：粒子群算法；搜索空间；自适应；均匀分布 中图分类号：ＴＰ３０１．６ 文献标志码：Ａ 文章编号：１００１—３６９５（２０１６）０７—２０４７－０４ ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１—３６９５．２０１６．０７．０２８ Ｄｙｎａｍｉｃ ｓｅａｒｃｈ ｓｐａｃｅ ｆｏｒ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ Ｚｈａｎｇ Ｓｈｕｉｐｉｎｇ，Ｗａｎｇ Ｂｉ （Ｓｃｈｏｏｌ ｏｆＩｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｊｉａｎｇｘｉ Ｕｎｉｖｅｒｓｉｔｙ ｏｆＳｃｉｅｎｃｅ＆Ｔｅｃｈｎｏｌｏｇｙ，Ｇａｎｚｈｏｕ Ｊｉａｎｇｘｉ ３４１０００，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｏ ｆｕｒｔｈｅｒ ｅａｓｅ ｔｈｅ ｐｒｏｂｌｅｍｓ ｓｕｃｈ ｆｌＳ ｔｈｅ ｓｌｏｗ ｃｏｎｖｅｒｇｅｎｃｅ ｓｐｅｅｄ ａｎｄ ｔｈｅ ｐｒｅｍａｔｕｒｅ ｃｏｎｖｅｒｇｅｎｃｅ ｏｆ ｔｈｅ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ，ｔｈｉｓ ｐａｐｅｒ ｐｒｏｐｏｓｅｄ ａ ｎｅｗ ｓｔｒａｔｅｇｙ ｎａｍｅｄ ｓｔｒａｔｅｇｙ ｏｆ ｄｙｎａｍｉｃ ｓｅａｒｃｈ ｓｐａｃｅ（ＤＳＰＳＯ）．Ｔｈｉｓ ｓｔｒａ— ｔｅｇｙ ｓｔｒｕｃｔｕｒｅｄ ａｎ ｅｍｂｅｄｄｉｎｇ ｓｙｓｔｅｍ ｂｙ ｇｌｏｂａｌ ｏｐｔｉｍａｌ ｓｏｌｕｔｉｏｎｓ ａｎｄ ｓｅｌｆ－ａｄａｐｔｉｏｎ ｔｈｒｅｓｈｏｌｄ．Ｔｈｅ ａｌｇｏｒｉｔｈｍ ｒｅｉｎｉｔｉａｌｉｚｅｄ ｔｈｅ ｐｏ— ｓｉｔｉｏｎ ｏｆ ｐａｒｔｉｃｌｅｓ ａｎｄ ｓｐｅｅｄ ｗｅｉｇｈｔｓ ｔｏ ｉｍｐｒｏｖｅ ｅｘｐｌｏｒａｔｉｏｎ ｃａｐａｂｉｌｉｔｉｅｓ ｏｆ ｉｍｐｒｏｖｅｄ ＰＳＯ ａｌｇｏｒｉｔｈｍｓ．Ｓｉｍｕｌａｔｉｏｎ ｔｅｓｔ ｏｆ ｄｉｆｅｒｅｎｔ ｂｅｎｃｈｍａｒｋ ｆｕｎｃｔｉｏｎｓ ｃｌｅａｒｌｙ ｓｈｏｗ ｔｈａｔ．ｗｉｔｈ ｔｈｅ ｓａｍｅ ｗｅｉｇｈｔ ａｎｄ ｌｅａｒｎｉｎｇ．ｆａｃｔｏｒｓ ｓｔｒａｔｅｇｙ。ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ＤＳＰＳＯ ｉＳ ｂｅｔｔｅｒ ｔｈａｎ ＰＳＯ．Ａｎｄ ｔｈｅ ｓａｍｅ ｔｈｉｎｇｓ ｈａｐｐｅｎ ｄｕｒｉｎｇ ｔｈｅ ｃｏｍｐａｒｅ ｂｅｔｗｅｅｎ ｔｈｅ ＱＰＳＯ ａｎｄ ｉｔｓ ｅｍｂｅｄｄｉｎｇ．Ｓｔｕｄｉｅｓ ｉｌｌｕｍｉｎａｔｅ ｔｈｉｓ ｓｔｒａｔｅ— ｇＹ ｗｉｔｈ ｒｏｂｕｓｔｎｅｓｓ ｃａｎ ｐｒｅｖｅｎｔ ｔｈｅ ｐｒｅｍａｔｕｒｅ ｃｏｎｖｅｒｇｅｎｃｅ ａｎｄ ｐｒｏｍｏｔｅ ｔｈｅ ｃａｐａｃｉｔｉｅｓ ｏｆ ｅｘｐｌｏｒａｔｉｏｎ ｉｎ ｔｈｅ ｅｎｄ ｏｆ ａｌｇｏｒｉｔｈｍ． Ｋｅｙ ｗｏｒｄｓ：ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ（ＰＳＯ）；ｓｅａｒｃｈ ｓｐａｃｅ；ｓｅｌｆ－ａｄａｐｔｉｏｎ；ｕｎｉｆｏｒｌｎ ｄｉｓｔｉｒｂｕｔｉｏｎ 粒子群优化（ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ，ＰＳＯ）算法作为群 了适度重新初始化，但由于收敛点的预判方式使其无法自动进 智能算法的一员，自１９９５年由Ｋｅｎｎｅｄｙ等人 提出后便被关 行空间压缩触发；同时也是在向搜索空间的几何中心进行压 注与研究。在文献［３］中详细归纳了ＰＳＯ算法的应用领 缩，鲁棒性不足。为此，本文设计了一种挂载于原ＰＳＯ算法核 域Ｍ Ｊ，其中包括生物、控制、设计、通信网络等众多行业。与 心外的优化策略，即可与绝大多数粒子群优化共存的优化策 其他群智能算法（如蚁群算法。。’ ）一样具有早熟、且对高复杂 略。当大多数粒子都聚集于已知全局最优解ｇ：。 。附近时，判定 度问题收敛性较差等问题。为解决这些问题，Ｃｌｅｒｃ等人 ．９ 提 为近似收敛，为自适应阈值。此时依照搜索空间边界和ｇ 各 出采用收缩因子来保证收敛，并进行讨论；同时，大量的学者也 维度之间的欧氏距离及相邻的两次满足放缩要求时迭代所得 在为解决或缓解算法存在的问题，在惯性权重、学习因子、拓扑 ｇ 与ｇ ７的实际位移来动态决定对搜索空间的缩放力度。同 结构等方向不断进行尝试。 时将分别采用标准ＰＳＯ和文献［１３，１４］中的惯性权重及学习 文献［１０～１２］通过压缩搜索空间来提高算法性能。文献 因子策略，对文献［１５］中的部分基准函数进行仿真实验，并对 ［１０］以搜索空间的几何中心为基点进行空间压缩，当全局最 比文献［８］与本文算法的具体表现。 优解在几何中心附近时，可以获得很好的效果；然而当空间非 对称时，并未给出对应的测试结果，可能会增加寻优难度。文 １ 基本思想 盯 献［１１］提出了基于概率理论、边界变异和粒子吸引子的创新 策略，并成功提出了有效的速度更新策略。可以对最优解为 为了采用压缩空间的方式来提升算法优化效果，解决早熟 ， （０，０，…，０）：ｍｉｎ｛ｆ（ 。， ：，…， ）｝具有非常好的搜寻能 问题，首先需要对压缩空间是否可以导致解丢失这一问题进行 力，然而却是在对速度更新式进行调整后取得的，并不适应搭 讨论。利用泛函分析中柯西（Ｃａｕｃｈｙ）列的相关知识对定理１ 载在所有的ＰＳＯ系统上，且收敛点为近似估计获得，无法由程 进行了简单证明。 ｎ 定理１依照当前全局最优解（收敛点），对陷入早熟的粒 序自行判断。文献［１２］采用近似估计值ｎ一５× 为收敛 ０ Ｍ 子群算法（已收敛）的解域进行压缩，不会导致更优解丢失。 ｎ 点预测值，其中— 为问题维度与种群规模的比值。虽然采取 证明式（１）为粒子群算法的基本速度更新公式。 ＝０９ｏ３ ＋ｃＩａ（ｐｆ一 ）＋ｃｚ＃（ｐｇ一 ） （１） 收稿日期：２０１５—０３—０５；修回日期：２０１５—０４—３０ 作者简介：张水平（１９６５．），男，教授，主要研究方向为智能计算、智能矿山；王碧（１９８８．），男（通信作者），硕士研究生，主要研究方向为智能计 算、智能应用（ｈａｐｐｙｅｖｅｒｙｄａｙ＿３８６＠１６３．ｃｏｎ）． ·２０４８· 计算机应用研究 第３３卷 其中：０３为惯性权重； ， ∈［０，１］的随机数；ｃ。、ｃ 为学习因子； 出更新。其每个维度上的位置分配公式如式（４）所示。 ；ｐ 为个体已知最优位置和种群已知最优位置。当算法早熟 ＝伽 ＋ｃｌ （ｐ 一 ）＋ｃ２１３（ｐ 一 ）：Ｖｋ＝ ＝ｄ× 十０＋收敛时，可知 （１一 ）口 ＝ｃｌ （ｐｆ一 ）＋ｃ２／３（ｐ 一 ）＝ 字（ｉ一１） （４） 其中：０Ｌ∈［０，１］的随机数，ｓｉｚｅ（Ｘ）＝ ， ∈［。，ｂ］。这样可以 保证每个粒子均匀分布在整个搜索空间中，有利于算法的搜索 表现。 即粒子处于静止或基本静止状态。 根据位置更新式（２）可知，当粒子处于静止状态时，对于 ２．４重置权重及学习因子策略 单个粒子而言，其位置更新序列构成柯西列。 ＝ ＋ （２） 为保证算法可以在最初的规定次数内完成，本文采取了一 个折中的办法来近似重置权重和学习因子。在程序中增加了一 个新的变量Ｚ 用来记录满足近似收敛条件，并进行了重新部署 当依照当前全局最优解的位置进行压缩空间时，可以看做 在压缩后的新空间Ｘ 内，柯西列前ｍ（ｍ Ｎ）项被舍弃。设存 在收敛点 ，则可推出： 若ｍ≥ ，贝０Ｐ（ “ ， ）＜ ，Ｖ占＞０ ａｎｄ ≥ｍ； 若ｍ≤ ，则Ｐ（ “ ， ）＜ｓ，Ｖ８＞０ ａｎｄ ≥ 。 即定理１成立。 在此基础上，本文采用近似收敛点判断当前算法的收敛情 况，当算法近似收敛时，进行空间压缩可以在保证解正确性的 情况下完成对搜索范围的精简；在满足收敛条件后压缩空间的 同时对粒子位置进行重新分配，通过改变粒子群位置来提升算 法后续探索效果，从而避免早熟问题的出现。 ２参数设定及实现 ２．１ 近似收敛及其判定条件 近似收敛，意味着并非真正意义上的收敛，而是人为设置 的一个标准，用来判断粒子的聚集程度。当超过这一标准时， 近似将其看做收敛。本文判定步骤如下： ａ）将当前搜索空间的各维度上、下限分别存人两个向量 中，并计算其欧氏距离ｄ＝ｐｄｉｓｔ２（Ａ，占）。 ｂ）将步骤ａ）所得值ｄ与给定常数／．ｔ＝１ｅ一６相乘，得到近 似收敛判定标量 ＝ ×ｄ。 ｃ）对每个粒子作位置检验，若与全局已知最优解Ｐ 的欧 氏距离小于 ，则计数器加１；若这类粒子所占比例超过ｒｚ＝ ０．９，则判定为近似收敛。 其中的各项给定参数可以根据实际情况进行修改。这里 的数值为后续仿真实验中使用的具体数值。下同。 ２．２空间缩放控制 空间缩放将通过以下步骤进行控制： ａ）构建空间最小范围控制向量ｘ＿ｌｉｍｉｔ。 （ａ）比较最近两次满足近似收敛条件的全局已知最优解 Ｐ （其中Ｐ 为当前最优解，ｐ 为前次最优解）在各维度上 的位移量ｄ ； （ｂ）若ｄ ＜ｂ＝ｌｅ一５，则认为在这一维度上已达到近似最 优位置，缩小最小范围控制值，记ｘ＿ｌｉｍｉｔ ＝（１．５ｅ～２×ｄ ／ｂ）； （ｃ）若ｄ ≥ｂ＝ｌｅ一５，则认为在这一维度尚未达到近似最 优位置，放大最小范围控制值，记ｘ＿ｌｉｍｉｔ ＝０．５； ｂ）新的搜索空间为［Ａ ，Ｂ ］，其中 ， ［０，１］的随 机数。 Ａ ＝Ｐ —ｍａｘ（（ｐ 一Ａ）× ×０．５，ｘ＿ｌｉｍｉｔ） Ｂ ＝Ｐｇ＋ｍａｘ（（Ｂ－ｐ ）×卢×０．５， 一ｌｉｍｉｔ） （３） Ｃ）更新记录ｐ ＝ 。这里的ｐ 是需要进行存储的。 ２．３重分配粒子位置策略 仅对位置在新的搜索空间中进行均匀分配，而不对速度作 的当前迭代次数ｆ。这样的话，在下一次迭代开始后，可以清楚 地知道Ａｌ＝２一ｚ ，△ ＝Ｌ—ｚ ，并通过△２、△ 来计算速度权重 和学习因子。这里可以看到，这种策略只能对依照ｆ、工来确定 权重和学习因子的因子选择策略有效。其他类型的因子选择策 略在本文中并未进行讨论，但这并不影响整个算法的可行性。 ２．５伪代码实现 Ｗ＝ｆ（１，Ｌ，１ ）； …－ＰＳＯ主体算法完成…． ｆｏｒ ｉ＿ｓｃｏｐｅ＿ｃ＝１：ＰａｒｔｉｃｌｅＳｉｚｅ ｂｍｉｎ（ｉ＿ｓｃｏｐｅ＿ｃ）＝ＰａｒｔｉｃｌｅＳｃｏｐｅ（ｉ＿ｓｃｏｐｅ—ｃ，１）； ｂ＿ｍａｘ（ｉ—ｓｃｏｐｅ—ｃ）＝ＰａｒｔｉｃｌｅＳｅｏｐｅ（ｉ＿ｓｃｏｐｅ—ｃ，２）； ｅｎｄ Ｘ＝ｐｄｉｓｔ２（ｂ＿ｍｉｎ，ｂ ｍａｘ） （１ｅ一６）； ｆｓｕｍ—Ｓｗａｒｍ＝０．０ ％计数量，当粒子与全局最优点距离小于值ｘ时，加１ ｆｏｒ ｒＯＷ＝１：ＳｗａｒｍＳｉｚｅ ｘ＿ｔｅｍｐ＝ｐｄｉｓｔ２（Ｐ ，ｄ ）； ｉｆ（ｘ＿ｔｅｍｐ＜＝Ｘ） ｆｓｕｍ—Ｓｗａｒｍ＝ｆ—ｓｕｍＰａｒｔｉｃｌｅ＋１； ｅｎｄ ｅｎｄ ％近似判断为稠密 ｉｆ ｆｓｍｎ Ｓｗａｒｍ／ＳｗａｒｍＳｉｚｅ＞＝ｆ ｒｅｓｅｔＲａｔｅ ＿＿ｏｆｒｉ＝ｌ：ＰａｒｔｉｅｌｅＳｉｚｅ ｃ＝ｐｄｉｓｔ２（Ｐ ｐ：）； ％设置压缩下限 ｉｆ Ｃ＜＝１ｅ一５ ｂ＿ｌｉｍｉｔ（ｉ）＝（３ｅ一２ ｃ／（１ｅ一５））／２；％缩紧区间 ｅｌｓｅ ｂ＿ｌｉｍｉｔ（ｉ）＝０．５；％放开区间 ｅｎｄ ｅｎｄ ％更新搜索区域 ＰａｒｔｉｃｌｅＳｅｏｐｅ—ｔｅｍｐ（：，１） Ｐ 一ｉｎａｘ（（Ｐ 一ＰａｒｔｉｃｌｅＳｃｏｐｅ（：． １））｝ｕｎｉｆｒｎｄ（０，１） ０．５，ｂ＿ｌｉｍｉｔ）； ＰａｒｔｉｃｌｅＳｃｏｐｅ—ｔｅｍｐ（：，２）＝Ｐ ＋ｍａｘ（（（ＰａｒｔｉｅｌｅＳｅｏｐｅ（：，２）一 Ｐ 。））￥ｕｎｉｆｒｎｄ（０，１） ０．５，ｂ＿ｌｉｍｉｔ）； ＰａｒｔｉｃｌｅＳｃｏｐｅ＝ＰａｒｔｉｃｌｅＳｃｅｐｅ—ｔｅｍｐ； ％备份最优解，用来判断是否发生位移 ｐ ＝Ｐｇ； ％重新分配粒子位置 ｒｅｓｅｔＰａｒｔｉｅｌｅＳｉｔｅ（ＰａｒｔｉｃｌｅＳｃｏｐｅ）； ｌ ＝ｌ；％更新压缩发生时当前循环次数 ｅｎｄ ３实验分析 ３．１ ＰＳＯ算法对比及分析 表１～３记录的是在选择不同惯性权重和学习因子策略 时，原ＰＳＯ算法与加动态搜索区域策略对基准函数进行１００ 次仿真寻优实验所采集的具体数值来整理获得的，分别记录了 均值、标准差、最优解和最差解。本文选择的各权重一学习因 子策略是由其自身特性决定的，分别为线性权重与定值学习因 子、线性权重与依赖权重的学习因子、线性权重与依赖当前查 询次数的学习因子。本次实验仅仅是对其因子的使用，并未对 其他地方进行修改。 第７期 张水平，等：动态搜索空间的粒子群算法 表１函数性能分析表：ＰＳＯ ·２０４９· 表１中记录的是在 ＝ …一— ｂ（ …一 ），ｃ１＝ｃ２＝ 一定下降。不难看出，其原始收敛曲线并未有明显的收敛，即 收敛曲线对比可以发现，策略搭载前后曲线重叠部分的跨度， 不存在类似早熟问题，所以本文策略并不适用。再者与ＰＳＯ ２．０５条件下两种算法的比较，其中（ｃ，一＝０．９，∞…＝０．４，Ｌ＝ １０００。表２中记录的是在Ｃ ＝４（１一（ｔＪ），Ｃ：＝４ｗ条件下两种算 法的比较。表３中记录的是在 ＝∞ ＋（ 一 …） ＋ ， ＰＳＯ中明显具有更好的稳定性，所以整体表现也更好。 ｆ｛ ｑ ｌｎＩ一：， ｌ —ｑ‰ ：、，ｆ…、条件下两种算法的比较，／ 条件下两种算法的比较，其中 【Ｃ２ Ｃ２ｉｎｉ一【Ｃ２ｉｆｎ—Ｃ２ｉ ｉ Ｊ【ｔ／Ｌ） ｆ ＝０．９５，∞…＝０．５，Ｌ＝１０００ 【ｃｌ。 ＝２，ｃｌｎｎ＝０．５，ｃ２ｉｎｉ：０．５，ｃ２６ｎ＝２。 由上述表中可以看出，在相同速度权重和学习因子选择策 略的情况下，基准函数实验中的大多数统计指标均有明显提 升，可以较好地适应各种特性的因子选择策略。图１—６将使 用具体图像来展示改进效果，其中各图中的第四幅子图为坐标 轴说明与策略图形说明，图中曲线仅作展示，并无实际意义。 由图１—６可以清晰地看出，在大多数测试结果中，本文提 出的策略相较原算法都有不错的提升。同时也可以看出，文中 策略最后的效果与原算法是否能快速收敛于最优解附近有一 定的关联。当原算法趋于成熟时，本文提出的动态搜索空间策 略依然具有一定的探索能力，如各图中并未呈成熟态势的曲线 所示。因此从实际数据方面证实了该策略的切实可行性。 迭代次数 图１ Ｒａｓｔｆｉｇｉｎ函数的测试均值 ３．２ ＱＰＳＯ算法对比及分析 量子粒子群算法（ＱＰＳＯ）作为一种有效的粒子群算法已被 广泛应用于各个领域之中［１８，１９１。为保证该策略的充分有效 性，本文还将其嵌入ＱＰＳＯ 中，并对嵌入前后的效果进行对 比展示。同样采用１００组实验，展现的是其效果均值的收 敛曲线。ＱＰＳＯ与ＤＳＰＳＯ对比如图７、８所示。由图７可以看 出，在搭载文中策略后效果有不小提升。对照其原始收敛曲线 可以发现，其原始收敛曲线虽然寻优效果并不理想，但拥有不 错的收敛稳定性，为文中策略提供了必要的前提支持。对比而 言，图８中的效果并不明显，甚至在函数 的对比中效果还有 迭代次数 图２ Ａｃｋｌｅｙ函数的测试均值 ·２０５０· 计算机应用研究 第３３卷 趔 辍 陋 图３ Ｆ２＿ＳｆｔＲａｓｔｒｉｇｉｎ函数的测试均值 趔 辍 圜 三 图４ Ｆ３＿ＳｆｔＡｅｋｌｅｙ函数的测试均值 ＰＳ０．Ｆ１９Ｓｃｈｗｅｆｅｌ ｊ型 瓤 陋 图５ Ｆ１９ Ｓｅｈｗｅｆｅｌ函数的测试均值 陌 ＿呈 迭代次数 图６ Ｆ２０＿Ｒｏｓｅｎｂｒｏｃｋ函数的测试均值 辍 闰 －宴 图７ ＱＰＳＯ与ＤＳＰＳＯ对比１ Ｆ１９Ｓｃｈｗｅｆｅｌ 世 骚 闰 一窖 图８ ＱＰＳＯ与ＤＳＰＳＯ对比２ ４结束语 至此，可以证明本文提出的策略是可行且有效的。在对部 分基准函数进行实验中取得了不错的效果，可以在ＰＳＯ算法 收敛的情况下利用压缩空间与重新初始化粒子位置来进一步 提升寻优效果。同时也存在着一些不足：该策略是建立在所搭 载的ＰＳＯ主体算法收敛的情况下的，但本文并未给出ＰＳＯ算 法收敛的直接证明，而是作为一个已知命题来使用；该策略依 赖于更快的收敛速度和稳定的收敛性，才可以更快地划分出区 间提升寻优精度；同时，当原ＰＳＯ主体未能在最优解附近收敛 时，将需要花费较多的运算量以便将已收缩的搜索空间再次扩 展，如图６所示，虽然其比原策略获得更好的探索，但并未能取 得很好的结果，如图８所示，在对ＱＰＳＯ的嵌入过程中，对于原 收敛曲线并不明显或收敛性不稳定的情况下，提升效果并不明 显或有所降低。所以对ＰＳＯ算法主体的优化仍然是进一步研 究的内容。 参考文献： ［１］Ｋｅｎｎｅｄｙ Ｊ，Ｅｂｒｈａｒｔ Ｒ．Ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ［Ｃ］／／Ｐｒｏｃ ｏｆ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｎｅｕｒａｌ Ｎｅｔｗ０ｒｋｓ．１９９５：１９４２—１９４８． ［２］Ｅｂｅｒｈａｒｔ Ｒ，Ｋｅｎｎｅｄｙ Ｊ．Ａ ｎｅｗ ｏｐｔｉｍｉｚｅｒ ｕｓｉｎｇ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｔｈｅｏｒｙ ［Ｃ］／／Ｐｒｏｃ ｏｆ ｔｈｅ ６ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｍｉｃｒｏ Ｍａｃｈｉｎｅ ａｎｄ Ｈｕｍ 蚰Ｓｃｉｅｎｃｅ．１９９５：３９—４３． ［３］Ｐｏｌｉ Ｒ．Ａｎａｌｙｓｉｓ ｏｆ ｔｈｅ ｐｕｂｌｉｃａｔｉｏｎｓ ｏｎ ｔｈｅ ａｐｐｌｉｃａｔｉｏｎｓ ｏｆ ｐａｒｔｉｃｌｅ ｓｗａｒｌｆｌ ｏｐｔｉｍｉｓａｔｉｏｎ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ａｒｔｉｆｉｃｉａｌ Ｅｖｏｌｕｔｉｏｎ ａｎｄ Ａｐｐｌｉｃａ－ ｔｉｏｎｓ，２００８，２００８：１－１０． （下转第２０６７页） 第７期 郑锦勤，等：基于函数调用路径的回归测试用例选择排序方法研究 ·２０６７· 量结果分析可知，选择排序方法的 度量标准值和ＡＰＦＣ度 Ｓｏｆｔｗａｒｅ Ｅｎｇｉｎｅｅｒｉｎｇ．１９９４：２１１·２２０． 量标准值都分别高于选择方法的度量标准值，因此，对选择的 ［６］Ｖｏｋｏｌｏｓ Ｆ Ｉ，Ｆｒａｎｋｌ Ｐ Ｇ．Ｐｙｔｈｉａ：ａ ｒｅｇｒｅｓｓｉｏｎ ｔｅｓｔ ｓｅｌｅｃｔｉｏｎ ｔｏｏｌ ｂａｓｅｄ 测试用例进行优先级排序并再次确定，提高了程序变更部分和 ｏｎ ｔｅｘｔｕａｌ ｄｉｆｆｅｒｅｎｃｉｎｇ［Ｃ］／／Ｐｒｏｃ ｏｆ ｔｈｅ ３ｒｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ 受影响部分的函数对被覆盖的速度，使函数对被覆盖的次数达 ｏｎ Ｒｅｌｉａｂｉｌｉｔｙ，Ｑｕａｌｉｔｙ ａｎｄ Ｓａｆｅｔｙ ｏｆ Ｓｏｆｔｗａｒｅ－Ｉｎｔｅｎｓｉｖｅ Ｓｙｓｔｅｍｓ．１９９７： 到最小，能有效地减少测试用例的个数。可见，本文提出的基 ３－２１． 于ＦＣＰ的回归测试用例选择排序方法可以有效地优化回归测 ［７］魏冬梅，洪玫，袁伟，等．基于切片技术的ＧＵＩ回归测试用例选择 试用例。 ［Ｊ］．微计算机信息，２００８，２４（２７）：１７８—１８０． ［８］王克朝，王甜甜，苏小红，等．面向有效错误定位的测试用例优选 ３结束语 方法［Ｊ］．计算机研究与发展，２０１４，５１（４）：８６５—８７３． ［９］Ｗｏｎｇ Ｗ Ｅ，Ｈｏｒｇａｎ Ｊ Ｒ，Ｌｏｎｄｏｎ Ｓ，ｅｔ ａ１．Ａ ｓｔｕｄｙ ｏｆ ｅｆｆｅｃｔｉｖｅ ｒｅｇｒｅｓ— 近几年课题组对基于ＦＣＰ的回归测试用例自动生成、优 ｓｉｏｎ ｔｅｓｔｉｎｇ ｉｎ ｐｒａｃｔｉｃｅ［Ｃ］／／Ｐｍｃ ｏｆ ｔｈｅ ８ｔｈ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｓｙｍ— 先级排序与优化等算法进行了研究，本文结合测试用例选择技 ｐｏｓｉｕｍ ｏｎ Ｓｏｆｔｗａｒｅ Ｒｅｌｉｂａｉｌｉｔｙ Ｅｎｇｉｎｅｅｒｉｎｇ．１９９７：２６４—２７４． 术与优先级排序技术对回归测试用例展开了进一步的研究。 ［１０］Ｒｏｔｈｅｒｍｅｌ Ｇ，Ｕｎｔｃｈ Ｒ Ｈ，Ｃｈｕ Ｃｈｅｎｇｙｕｎ，ｅｔ ａ１．Ｐｒｉｏｒｉｔｉｚｉｎｇ ｔｅｓｔ ｃａｓｅｓ 通过分析被修改函数与其他函数的关联关系，并以函数对被覆 ｆｏｒ ｒｅｇｒｅｓｓｉｏｎ ｔｅｓｔｉｎｇ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓ ｏｎ Ｓｏｆｔｗａｒｅ Ｅｎｇｉｎｅｅｒｉｎｇ， 盖次数最少为原则，该方法只对因为系统修改受到影响的代码 ２００１，２７（１０）：９２９－９４８． 部分进行测试，与已有技术相比，进一步地减少了回归测试用 ［１ １］Ｅｌｂａｕｍ Ｓ，Ｍａｌｉｓｈｅｖｓｋｙ Ａ，Ｒｏｔｈｅｒｍｅｌ Ｇ．Ｉｎｃｏｒｐｏｒａｔｉｎｇ ｖａｒｙｉｎｇ ｔｅｓｔ 例的数量，大大缩减了测试人员的工作量，并且降低了测试成 ｃｏｓｔｓ ａｎｄ ｆａｕｌｔ ｓｅｖｅｒｉｔｉｅｓ ｉｎｔｏ ｔｅｓｔ ｃｓａｅ ｐｉｒｏｒｉｔｉｚａｔｉｏｎ［Ｃ］／／Ｐｒｏｃ ｏｆ ｔｈｅ 本。通过实验证明，本文提出的基于ＦＣＰ的测试用例选择排 ２３ｒｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｓｏｆｔｗａｒｅ Ｅｎｇｉｎｅｅｒｉｎｇ．２００１：３２９－ 序方法是有效的。本文是针对只修改软件系统的函数代码，并 ３３８． 且未改变函数调用关系图的情况论述的，对由于软件版本变 ［１２］屈波，聂长海，徐宝文．基于测试用例设计信息的回归测试优先级 更，如添加或删除功能的情况，如何对相关测试用例进行设计 算法［Ｊ］．计算机学报，２００８，３１（３）：４３１·４３９． ［１３］杨广华，包阳，李东红，等．基于需求的测试用例优先级排序［Ｊ］． 与修改将是下一步的研究重点。 计算机工程与设计，２０１１，３２（８）：２７２４—２７２８． 参考文献： ［１４］潘伟丰，李兵，马于涛，等．基于复杂软件网络的回归测试用例优 ［１］牟永敏，杨志嘉．基于函数调用路径的软件实现与设计一致性验 先级排序［Ｊ］．电子学报，２０１２，４０（１２）：２４５６—２４６５． 证［Ｊ］．中国科学，２０１４，４４（１Ｏ）：１２９０—１３０４． ［１５］张志华，牟永敏．基于函数调用的路径覆盖生成技术研究［Ｊ］．电 ［２］Ｂｅｉｚｅｒ Ｂ．Ｓｏｆｔｗａｒｅ ｔｅｓｔｉｎｇ ｔｅｃｈｎｉｑｕｅｓ［Ｍ］．Ｎｅｗ Ｙｏｒｋ：Ｖａｎ Ｎｏｓｔｒａｎｄ 子学报，２０１０，１３８（８）：１８０８—１８１１． Ｒｅｉｎｈｏｌｄ，１９９０． ［１６］孙赢盈，张毅坤，杨凯峰，等．一种基于程序关联性分析的软件测 ［３］Ｌｅｕｎｇ Ｈ，Ｗｈｉｔｅ Ｌ．Ｉｎｓｉｇｈｔｓ ｉｎｔｏ ｒｅｇｒｅｓｓｉｏｎ ｔｅｓｔｉｎｇ［Ｃ］／／Ｐｒｏｃ ｏｆ Ｉｎｔｅｒ－ 试方法［Ｊ］．计算机应用研究，２００８，２５（１２）：３６５０—３６５３． ｎａｔｉｏｎａｌ Ｃｏｎｆｅｆｅｎｃｅ ｏｎ Ｓｏｆｔｗａｒｅ Ｍａｉｎｔｅｎａｎｃｅ．１９８９：６０－６９． ［１７］牟永敏，李慧丽．基于函数调用路径的测试用例优先级排序［Ｊ］． ［４］Ｌｅｕｎｇ Ｈ Ｋ Ｎ，Ｗｈｉｔｅ Ｌ．Ａ ｓｔｕｄｙ ｏｆ ｉｎｔｅｇｒａｔｉｏｎ ｔｅｓｔｉｎｇ ａｎｄ ｓｏｆｔｗａｒｅ ｒｅ· 计算机工程，２０１４，４０（７）：２４２－２４６． ｒｇｅｓｓｉｏｎ ａｔ ｔｈｅ ｉｎｔｅｇｒａｔｉｏｎ ｌｅｖｅｌ［Ｃ］／／Ｐｒｏｅ ｏｆ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ［１８ Ｊ孙继荣，李志蜀，倪建成，等．回归测试用例集优化策略［Ｊ］．吉林 ｏｎ Ｓｏｆｔｗａｒｅ Ｍａｉｎｔｅｎａｎｃｅ．１９９０：２９０－３０１． 大学学报：工学版，２００８，３８（２）：１８４—１９０． ［５］Ｃｈｅｎ Ｙ Ｆ，Ｒｏｓｅｎｂｌｕｍ Ｄ，Ｖｏ Ｋ Ｐ．ＴｅｓｔＴｕｂｅ：ａ ｓｙｓｔｅｍ ｆｏｒ ｓｅｌｅｃｔｉｖｅ ｒｅ． ［１９］陈翔，陈继红，鞠小林，等．回归测试中的测试用例优先排序技术 ｇｒｅｓｓｉｏｎ ｔｅｓｔｉｎｇ［Ｃ］／／Ｐｒｏｃ ｏｆ ｔｈｅ １６ｔｈ Ｉｎｔｅｎｒａｔｉｏｎａｌ Ｃｏｆｎｅｒｅｎｃｅ ｏｎ 述评［Ｊ］．软件学报，２０１３，２４（８）：１６９５．１７１２． （上接第２０５０页） ［Ｊ］．计算机工程与应用，２０１０，４６（２）：５１—５４。 ［４］姚丽娟，罗可．基于粒子群的粗糙核聚类算法［Ｊ］．计算机应用研 ［１３］赵志刚，黄树运，王伟倩．基于随机惯性权重的简化粒子群优化算 究，２０１２，２９（８）：２８５４－２８５７，２９０２． 法［Ｊ］．计算机应用研究，２０１４，３１（２）：３６１ ３６３，３９１． ［５］杨志，罗可．一种改进的基于粒子群的聚类算法［Ｊ］．计算机应用 ［１４］秦洪德，石丽丽．一种新型的被动启发式粒子群优化算法［Ｊ］．哈 研究，２０１４，３１（９）：２５９７－２５９９，２６０５． 尔滨工程大学学报，２０１０，３１（１０）：１２９８－１３０２． ［６］Ｄｏｒｉｇｏ Ｍ，Ｂｉｒａｔｔａｒｉ Ｍ．Ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ，ｅｎｃｙｃｌｏｐｅｄｉａ ｏｆ ｍａ· ［１５］Ｔａｎｇ Ｋｅ，Ｌｉ Ｘｉａｏｄｏｎｇ，Ｓｕｇａｎｔｈａｎ Ｐ Ｎ，ｅｔ ａ１．Ｂｅｎｃｈｍａｒｋ ｆｕｎｃｔｉｏｎｓ ｆｏｒ ｃｈｉｎｅ ｌｅａｒｎｉｎｇ［Ｍ］．Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ，２０１０：３６·３９． ｈｔｅ ＣＥＣ’２００８ ｓｐｅｃｉｌａ ｓｅｓｓｉｏｎ ａｎｄ ｃｏｍｐｅｔｉｔｉｏｎ ｏｎ ｌａｒｇｅ ｓｃａｌｅ ｇｌｏｂａｌ ［７］Ｄｏｉｒｇｏ Ｍ，Ｂｉｒａｔｔａｒｉ Ｍ，Ｓｔｕｔｚｌｅ Ｔ．Ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ［Ｊ］．Ｃｏｍｐｕ－ ｏｐｔｉｍｉｚａｔｉｏｎ［Ｄ］．Ｈｅｆｅｉ：Ｎａｔｕｒｅ Ｉｎｓｐｉｒｅｄ Ｃｏｍｐｕｔａｔｉｏｎ ａｎｄ Ａｐｐｌｉｃａ－ ｔａｔｉｏｎａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ Ｍａｇａｚｉｎｅ，２００６，１（４）：２８－３９． ｔｉｏｎｓ Ｌａｂｏｒａｔｏｒｙ，ＵＳＴＣ，２００７． ［８］ Ｃｌｅｒｃ Ｍ．Ｔｈｅ ｓｗａｎＴｌ ａｎｄ ｔｈｅ ｑｕｅｅｎ：ｔｏｗａｒｄｓ ａ ｄｅｔｅｒｍｉｎｉｓｔｉｃ ａｎｄ ａｄａｐ— ［１６］龚怀云，寿纪麟，王绵森．应用泛函分析（基础部分）［Ｍ］．西安： ｔｉｒｅ ｐａｒｔｉｃｌｅ ｓｗ￣－＇ｎｌ ｏｐｔｉｍｉｚａｔｉｏｎ［ｃ］／／Ｐｒｏｃ ｏｆ Ｃｏｎｇｒｅｓｓ ｏｎ Ｅｖｏｌｕｔｉｏ－ 西安交通大学出版社，１９８５． ｎａｒｙ Ｃｏｍｐｕｔａｔｉｏｎ．１９９９． ［１７］Ｓｔｅｉｎ Ｅ Ｍ，Ｓｈａｋａｒｃｈｉ Ｒ．Ｆｕｎｃｔｉｏｎａｌ ａｎｌａｙｓｉｓ：ｉｎｔｒｏｄｕｃｔｉｏｎ ｔｏ ｆｕｒｔｈｅｒ ［９］Ｃｌｅｒｃ Ｍ，Ｋｅｎｎｅｄｙ Ｊ．１１１ｅ ｐａｒｔｉｃｌｅ ｓｗａｒｍ—ｅｘｐｌｏｓｉｏｎ，ｓｔａｂｉｌｉｔｙ，ａｎｄ ｃｏｎ－ ｔｏｐｉｃｓ ｉｎ ａｎａｌｙｓｉｓ［Ｍ］．４ｔｈ ｅｄ．［ｓ．１．］：Ｐｒｉｎｃｅｔｏｎ Ｕｎｉｖｅｒｓｉｔｙ Ｐｒｅｓｓ， ｖｅｒｇｅｎｃｅ ｉｎ ａ ｍｕｌｔｉｄｉｍｅｎｓｉｏｎａｌ ｃｏｍｐｌｅｘ ｓｐａｃｅ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓ ｏｎ ２０１１． ， Ｅｖｏｌｕｔｉｏｎａｒｙ Ｃｏｍｐｕｔａｔｉｏｎ，２００２，６（１）：５８－７３． ［１８］李炜，蔡翔．基于改进量子粒子群算法的ＮＣＳ模糊控制器参数优 ［１Ｏ］陈炳瑞，冯夏庭．压缩搜索空间与速度范围粒子群优化算法［Ｊ］． 化［Ｊ］．计算机应用研究，２０１３，３０（８）：２３０１－２３０３，２３１４． 东北大学学报：自然科学版，２００５，２６（５）：４８８－４９１． ［１９］杨涛，孙怀江，叶俊．基于量子粒子群优化算法的运动捕获数据关 ［１１］迟玉红，孙富春，王维军，等．基于空间缩放和吸引子的粒子群优 键帧提取［Ｊ］．计算机应用研究，２０１４，３１（８）：２５２３－２５２７． 化算法［Ｊ］．计算机学报，２０１１，３４（１）：１１５－１３０． ［２０］李士勇，李盼池．求解连续空间优化问题的量子粒子群算法［Ｊ］． ［１２］，张定华，陈冰．基于分工合作和搜索空间重构的粒子群优化 量子电子学报，２００７，２４（５）：５６９·５７４．
