离散二进制粒子群算法分析

DOI:10.13232/j.cnki.jnju.2011.05.002

第４７卷　第５期Ｖｏｌ．４７，Ｎｏ．５

　　　ＪＯＵＲＮＡＬＯＦＮＡＮＪＩＮＧ　ＵＮＩＶＥＲＳＩＴＹ　　　　　　

２０１１年９月Ｓｅｔ．２０１１ｐ （）ＮＡＴＵＲＡＬＳＣＩＥＮＣＥＳ　

南京大学学报（自然科学）

离散二进制粒子群算法分析

＊

，刘建华＊杨荣华，孙水华

＊

（）福建工程学院计算机与信息科学系，福州，３５０１０８

，摘　要：主要用优化计算实值的连续性问题，而离散ＰａｒｔｉｃｌｅＳｗａｒｍ　ＯｔｉｍｉｚａｔｉｏｎＰＳＯ）　粒子群算法（　ｐ，它扩展了二进制粒子群算法（ＢｉｎａｒＰａｒｔｉｃｌｅＳｗａｒｍ　ＯｔｉｍｉｚａｔｉｏｎＢＰＳＯ）则用来优化离散空间问题，　ｙｐ　现已广泛应用到各种离散优化问题计算中，但目前对ＢＰＳＯ算法的应用，ＰＳＯ算法的理论分析研究还很少，难以指导算法性能．本文从位改变概率和遗传算法的模式定理两方面对Ｂ分析得出，ＰＳＯ进行分析．但不能收敛于粒子的全局最优位置，而且随着算法迭代运行，ＢＰＳＯ算法具有很强全局搜索能力，ＢＰＳＯ的随机性越来越强，缺乏后期的局部搜索能力．本文利用基准的函数，通过仿真实验计算，验证本文的分析结果．基于分析的结果，本文提出Ｂ新方法采用新的概率映射函数和混合遗传算法ＰＳＯ的改进方法，通过对基准函数的仿真试验，验证了改进方法的有效性．的方法．

关键词：收敛性，位改变概率，模式定理　二进制粒子群算法，中图分类号：Ｐ１８　Ｔ　

Ｔｈｅａｎａｌｓｉｓｏｆｂｉｎａｒａｒｔｉｃｌｅｓｗａｒｍｏｔｉｍｉｚａｔｉｏｎ　　　　　ｙｙｐｐ　

ＬｉｕＪｉａｎ－Ｈｕａ，ＹａｎＲｏｎＨｕａ，ＳｕｎＳｈｕｉ－Ｈｕａ　　ｇ　ｇ－

（，，，）ＤｅａｒｔｍｅｎｔｏｆＣｏｍｕｔｅｒａｎｄＩｎｆｏｒｍａｔｉｏｎＳｃｉｅｎｃｅＦｕｉａｎＵｎｉｖｅｒｓｉｔｏｆＴｅｃｈｎｏｌｏＦｕｚｈｏｕ３５０１０８，Ｃｈｉｎａ　　　　　　　ｐｐｊｙｇｙ　：ＡｂｓｔｒａｃｔａｒｔｉｃｌｅＳｗａｒｍ　Ｏｔｉｍｉｚａｔｉｏｎ（ＰＳＯ）ｉｓａｎｅｖｏｌｕｔｉｏｎａｒｃｏｍｕｔａｔｉｏｎｉｎｓｉｒｅｄｂｓｗａｒｍｉｎｔｅｌｌｉｅｎｃｅ．　Ｐ　　　　　　ｐｙｐｐｙｇ　　，ＣｏｍａｒｅｄｔｏｏｔｈｅｒｅｖｏｌｕｔｉｏｎａｒｃｏｍｕｔａｔｉｏｎａｌｏｒｉｔｈｍｓＰＳＯｃａｎｎｏｔｏｎｌｓｏｌｖｅａｖａｒｉｅｔｏｆｄｉｆｆｉｃｕｌｔｏｔｉｍｉｚａｔｉｏｎ　　　　　　　　　　　ｐｙｐｇｙｙｐ　　　，ｒｏｂｌｅｍ，ｂｕｔａｌｓｏｉｓｅａｓｅｔｏｂｅｕｓｅｄ．ＳｏＰＳＯｈａｖｅｂｅｅｎｕｓｅｄａｃｒｏｓｓａｗｉｄｅｒａｎｅｏｆａｌｉｃａｔｉｏｎｓ．ＢｕｔＰＳＯｉｓｍａｉｎｌ　　　　　　　　　　　　　　　　　　ｐｇｐｐｙ，ａｌｉｅｄｉｎｔｈｅａｒｅａｏｆｃｏｎｔｉｎｕｏｕｓｓａｃｅａｎｄｒａｒｅｌｉｎｔｈａｔｏｆｄｉｓｃｒｅｔｅｓａｃｅ．Ｉｎｏｒｄｅｒｔｏｂｅｕｓｅｄｉｎｄｉｓｃｒｅｔｅｓａｃｅ　　　　　　　　　　　　　　　　　　　ｐｐｐｙｐｐ　ｂｉｎａｒＰａｒｔｉｃｌｅＳｗａｒｍ　Ｏｔｉｍｉｚａｔｉｏｎ（ＢＰＳＯ）ｗａｓｄｅｖｅｌｏｅｄｔｏｍａｋｅＰＳＯｃａａｂｌｅｔｏｏｔｉｍｉｚｅｔｈｅｃｏｍｂｉｎａｔｉｏｎ　　　　　　　　　　ｙｐｐｐｐ　ｒｏｂｌｅｍ，ｗａｒｔｉｃｌｅｒｏｂｌｅｍ．ｈｉｃｈｅｘｔｅｎｄｅｄｓｗａｒｍｏｔｉｍｉｚａｔｉｏｎａｎｄｉｓｕｓｅｄｔｏｏｔｉｍｉｚｅｔｈｅｄｉｓｃｒｅｔｅｂｉｎａｒｓａｃｅ　　　　　　　　　　　　　ｐｐｐｐｐｙｐ　ＡｌｔｈｏｕｈＢＰＳＯｈａｓｂｅｅｎｒｏｏｓｅｄｆｏｒｏｖｅｒｔｅｎｅａｒｓａｎｄｈａｓｂｅｅｎｕｓｅｄｉｎｍａｎｃｏｍｂｉｎａｔｉｏｎｏｔｉｍｉｚｉｎｒｏｂｌｅｍｓ　　　　　　　　　　　　　　　ｇｐｐｙｙｐｇｐ　　，，ａｅｒａｎｄａｌｉｅｄｉｎｍａｎａｒｅａｓｉｔｗａｓｒａｒｅｌａｎａｌｚｅｄ．ＩｎｔｈｉｓｔｈｅｂｉｎａｒＰａｒｔｉｃｌｅＳｗａｒｍ　Ｏｔｉｍｉｚａｔｉｏｎ（ＢＰＳＯ）ｉｓ　　　　　　　　　ｐｐｐｐｙｙｙｙｐ　　　，ｒｏｂａｂｉｌｉｔｗｉｔｈｂｉｔｃｈａｎｅａｎｄｓｃｈｅｍａｔｈｅｏｒｅｍｏｆＧｅｎｅｔｉｃＡｌｏｒｉｔｈｍ（ＧＡ）．Ｏｎｔｈｅｏｎｅｈａｎｄｔｈｅｃｈａｎｅａｎａｌｚｅｄ　　　　　　　　　　　　　ｐｙｇｇｇｙ　ｒｏｂａｂｉｌｉｔｏｆｅｖｅｒｂｉｔｏｆＢＰＳＯｉｓｃｏｍｕｔｅｄ．ＡｎｄＩｔｗａｓｆｏｕｎｄｔｈａｔｃｈａｎｅｒｏｂａｂｉｌｉｔｏｆｅｖｅｒｂｉｔｏｆＢＰＳＯｉｓ　　　　　　　　　　　　　　　ｐｙｙｐｇｐｙｙ　　　　

，ｂｉｅｒａｎｄｂｉｅｒｗｉｔｈｉｔｅｒａｔｉｏｎｏｉｎｏｎ．ＯｎｔｈｅｏｔｈｅｒｈａｎｄＢＰＳＯｕｓｔｕｓｅｓｔｈｅｍｕｔａｔｉｏｎｏｆＧＡｉｎｔｅｒｍｏｆｔｈｅｏｒ　　　　　　　　　　　　　　　　　　ｇｇｇｇｇｇｊｙ　，ｏｆＧｅｎｅｔｉｃＡｌｏｒｉｔｈｍ，ａｎｄｉｓｌａｃｋｏｆｔｈｅｏｅｒａｔｉｏｎａｎｄｃｒｏｓｓｏｖｅｒｏｆｓｅｌｅｃｔｉｏｎｓｏｉｔｃａｎｎｏｔｋｅｅｔｈｅｏｔｉｍａｌｓｃｈｅｍａ　　　　　　　　　　　　　　　　ｇｐｐｐ　

）福建省科技厅Ｋ类项目（ＪＫ２０１１０３５＊基金项目：

收稿日期：２０１１－０５－２０

，：ａｉｌｊｈｌｉｕｆｎｕ．ｅｄｕ．ｃｎ＊＊通讯联系人Ｅ－ｍ＠ｊ

　第５期

刘建华等：离散二进制粒子群算法分析

·５０５·

，ｉｎｃｒｅａｓｅｉｎＢＰＳＯｗｉｔｈｉｔｅｒａｔｉｏｎｏｉｎｏｎｉｎｔｅｒｍｏｆｓｃｈｅｍａｔｈｅｏｒｅｍｏｆＧＡ．Ｆｒｏｍｔｈｅｔｗｏｗａｓｉｔｗａｓｆｏｕｎｄｔｈａｔ　　　　　　　　　　　　　　　　　　ｇｇｙ　，ｗ，ｏｗｅｒｆｕｌｌｏｂａｌＰＳＯｉｓｍｏｒｅａｎｄｍｏｒｅｓｔｏｃｈａｓｔｉｃｈｉｃｈｈａｓｔｈｅａｂｉｌｉｔｏｆｓｅａｒｃｈｂｕｔｃａｎｎｏｔｃｏｎｖｅｒｅｓｔｏｂｉｎａｒ　　　　　　　　　　　　　　ｐｇｙｇｙ　　，，ａｒｔｉｃｌｅｏｉｎｏｗｅｒｆｕｌｔｈｅｏｔｉｍａｌｏｆｓｗａｒｍ．ＷｉｔｈｔｈｅｉｔｅｒａｔｉｏｎｏｎｔｈｅｒａｎｄｏｍｎｅｓｓｏｆＢＰＳＯｉｓｍｏｒｅａｎｄｍｏｒｅｓｏ　　　　　　　　　　　　　　　ｐｇｇｐｐ　，ｅｔｈｅＢｉｎａｒＰＳＯｉｓｌａｃｋｏｆｌｏｃａｌｅｘｌｏｒａｔｉｏｎｗｈｉｃｈｉｎｓｔｒｕｃｔｓｔｈｅｉｍｒｏｖｅｍｅｎｔｏｆＢＰＳＯ．Ａｎｄｔｈｅｎｘｅｒｉｍｅｎｔｓ　　　　　　　　　　　　　ｙｐｐｐ　，ｃｏｎｄｕｃｔｅｄｗｉｔｈＢｅｎｃｈｍａｒｋｆｕｎｃｔｉｏｎｈａｖｅｔｅｓｔｅｄｔｈｅｒｅｓｕｌｔｓｉｎｔｈｉｓａｅｒ．ＢａｓｅｄｏｎｔｈｅａｎａｌｓｉｓａｎｉｍｒｏｖｅｄＢｉｎａｒ　　　　　　　　　　　　　　　ｐｐｙｐｙＰＳＯｉｓｒｏｏｓｅｄｗｈｉｃｈｃｈａｎｅｓｔｈｅｆｏｒｍｕｌａｏｆｉｔｓｒｏｂａｂｉｌｉｔｍａｉｎａｎｄｔｈｅｆｏｒｍｕｌａｏｆｂｉｔｏｂｔａｉｎｉｎｖａｌｕｅ．Ｔｈｅ　　　　　　　　　　　　　　ｐｐｇｐｙｐｐｇｇ　　　’ａｒｔｉｃｌｅａｒｔｉｃｌｅｎｅｗｆｏｒｍｕｌａｓａｒｅｆａｖｏｒａｂｌｅｏｆｓｃｏｎｖｅｒｅｎｃｅｔｏｔｈｅｏｔｉｍａｌａｎｄｉｎｔｅｎｓｉｆｔｈｅｌｏｃａｌｅｘｌｏｒａｔｉｏｎｏｆ　　　　　　　　　　　　　　　ｐｐｇｐｙｐ　，ａｅｒｂｉｎａｒＰＳＯ．ＷｉｔｈＢｅｎｃｈｍａｒｋｆｕｎｃｔｉｏｎｔｈｅｅｘｅｒｉｍｅｎｔｃｏｎｄｕｃｔｅｄｉｎｔｈｉｓｉｌｌｕｓｔｒａｔｅｓｔｈａｔｔｈｅｉｍｒｏｖｅｄｂｉｎａｒ　　　　　　　　　　　　ｐｐｙｐｐｙ　ｉｓｏｕｔｅｒｆｏｒｍｅｄｔｏｏｒｉｉｎａｌｂｉｎａｒＰＳＯ．ＰＳＯ　　　　　ｐｇｙ　

：，ｃ，ｓ，ａｒｔｉｃｌｅｒｏｂａｂｉｌｉｔＫｅｗｏｒｄｓｉｎａｒｗａｒｍｔｉｍｉｚａｔｉｏｎｏｎｖｅｒｅｎｃｅｃｈｅｍａｈｅｏｒｅｍ，ｂｉｔｈａｎｅ　ｂ　ｓ　ｏ　ｔ　ｃ　ｐｙｙｐｇｇｙ　ｐ　

ｅｘｅｃｔｅｄｖａｌｕｅ　ｐ

，ＰａｒｔｉｃｌｅＳｗａｒｍ　Ｏｔｉｍｉｚａｔｉｏｎ　　粒子群算法（　ｐ

是由ＪＰＳＯ）．ＫｅｎｎｅｄＣ．Ｅｂｅｒｈａｒｔ于１９９５年ｙ和Ｒ．

］１，２

，开发的智能优化算法［它是受鸟群、鱼群等群

对离散二进制粒子群算法的模式定理两方向，

（进行分析，本文分析发现ＢＢＰＳＯ）ＰＳＯ具有过

强的随机的全局探索性，缺少后期局部探测性，进而改进了ＢＰＳＯ算法．

体社会智能而产生的灵感．后来Ｙ．Ｓｈｉ和Ｒ．Ｃ．Ｅｂｅｒｈａｒｔ增加一个动态变化的权重来控制ＰＳＯ

］３

，算法的探索性和探测性［形成现在的标准粒子群算法．相比其它进化算法，粒子群算法有着参数少，不需要编码，易于使用等优势，它已广泛应例如，图像处理，模用于各个领域的优化计算中，

］４～８

电力规划，生产调度等等［然而，标式识别，．

１　离散二进制粒子群算法

Ｋｅｎｎｅｄｂｅｒｈａｒｔ开发出来离散二进制ｙ和ＥＰＳＯ算法的速度更新公式与原始ＰＳＯ算法一

首先粒子是由二进制编码组成，每个二制位样，

）式产生速度，利用（而其速度值被转换成变１换的概率，也就是位变量取１值的机会．

·ｖ（）·（ｖｃｒａｎｄｘ＋ｐｉｄ＝ωｉｄ＋１·ｉｄ－ｉｄ）

（）·（（）ｃｒａｎｄｘ１ｐ２·ｉｄ）ｄ－ｇ但没有原始Ｐ为ＳＯ的粒子位置更新公式．速度了表示速度的值是二进制位取１的概率，］，的值被映射到区间［映射的方法一般采用０，１（）式ｓ２ｉｍｏｉｄ函数：ｇ

（（）ｓｖ＝２ｉｄ）

１＋ｅｘ－ｖｐｉｄ（这里ｓ表示位置ｘ粒子ｖｉｄ）ｉｄ取１的概率，）式改变它的位值：通过（３

（）（ａｎｄｖ１≤ｓｉｄ）　ｉｆｒ（）ｘ３ｉｄ＝０ｏｔｈｅｒｗｉｓｅ）这里ｒ是一个随机数，从区间［ａｎｄ（０，１］

（的统一分布中随机产生．为了避免ｓ太靠ｖｉｄ）近１或０，一个参数Ｖｍ用于ａｘ作为最大速度值，限制ｖ即ｖ速度的－ＶｍＶｍ．ｉｄ的范围，ｉｄ∈［ａｘ，ａｘ］

准Ｐ对ＳＯ算法适应在连续搜索空间进行计算，于离散的搜索空间，其不能直接加以应用，必须需要对标准Ｐ使其适合求解ＳＯ算法进行改进，离散空间的问题．

为了使ＰＳＯ算法能解决离散组合优化问题，Ｊ．ＫｅｎｎｅｄＣ．Ｅｂｅｒｈａｒｔ在１９９７年设计ｙ和Ｒ．一个ＰＳＯ算法的离散二进制版本（Ｂｉｎａｒｙ

［９］

，，用来ＰａｒｔｉｃｌｅＳｗａｒｍ　ＯｔｉｍｉｚａｔｉｏｎＢＰＳＯ）　ｐ优化离散二进制空间的问题，扩展了ＰＳＯ算法大量文献的应用．ＢＰＳＯ算法提出来有十多年，将其应用于组合优化问题，获得广泛的应用，例如，生物信息，背包问题，经济规划和图形图像

１０～１８］

标准粒子群算法从提出来以后，有等等［．

很多文献对它进行了理论分析，已获得一些成果．但很少有文献对离散二进制粒子群算法（ＢＰＳＯ）进行理论分析，难以从理论上说明本文从位改变概率和遗传算法ＢＰＳＯ的性能．

·５０６·

南京大学学报（自然科学）　　　　　

第４７卷

限制最终是限制了位ｘｉｄ取１或０的概率．

）］在（式中，其函数值被映射成区间［２０，１．）根据（式，函数值代表了某位为１的概率．需３要注意的是：Ｓｉｍｏｎｄ函数值并不代表某位变ｇ化概率，只是代表某位取１的概率．所以，在分析中需要考虑某位变化的概率是多少，本文将对此进行分析．

时，位的改变绝对概率最大，最大值为０这．２５．是Ｊ．ＫｅｎｎｅｄＣ．Ｅｂｅｒｈａｒｔ在文献［９］ｙ和Ｒ．的分析结果，其分析方式不严格，比较简单，下节对此进一步分析．

）表示２．２　位改变率的进一步分析　设ｖｔｉｄ（第ｉ粒子的第ｔ代在ｄ维的速度．第ｔ代位为１

（）），的概率为Ｓ而位为０概率是１－Ｓ（ｖｔｖｉｄ（ｉｄ（））此外，如果第ｔ则第ｔｔ．－１代位值已经是０，

））；代将发生改变的概率为Ｓ（同样，如果ｖｔｉｄ（第ｔ则第ｔ代发生改变的－１代位值已经是１，（））概率为１－Ｓ而第ｔｖｔ．－１代位值是０的ｉｄ（（）），概率为１－Ｓ第ｔｖｔ－１－１代位值是１的ｉｄ（（）因此，第ｔ代位发生改变概率为Ｓｖｔ－１）．ｉｄ（

（）应该为：的概率ｐｔ（）（）））（））ｔ＝（１－Ｓｖｔ－１Ｓｖｔ＋ｐｉｄ（ｉｄ（（））（（）））（）Ｓｖｔ－１１－Ｓｖｔ７ｉｄ（ｉｄ（））结合（式与（式，得到下式：２７

（）ｔ＝１－ｐ×ｅｘ－ｖｔ－１１＋ｐｉｄ２　二进制粒子群算法的分析

２．１　位变化概率的分析　文献［９］提出一个

位变化概率的概念，这里据此对它进行分析．根）据（式，粒子轨迹是一种概率改变，而单维的３速度转化为位取１的概率．位为１的概率为Ｓ（，而位为０概率是１－Ｓ（如果位已经ｖｖ．ｉｄ）ｉｄ）

；是０，则位发生改变的概率为Ｓ（如果位已ｖｉｄ）（经是１，则其发生改变的概率为１－Ｓ位发ｖ．ｉｄ）生改变的绝对率为：

（（（（）＝Ｓｖ１－ＳｖΔ）ｐｉｄ）ｉｄ）

即

２

（（（（）＝Ｓｖ－Ｓｖ５Δ）ｐｉｄ）ｉｄ）

公式表示为位给定一个速度ｖ其发生改变ｉｄ值，

（）４

的绝对概率．所以，ｖｉｄ值改变就是位改变概率））的变化．结合（式和（式，得到下式：２５

２

（）－ｐΔ＝

１＋ｅｘ－ｖ１＋ｅｘ－ｖｐ（ｐ（ｉｄ）ｉｄ）

）

（）

ｅｘ－ｖｔ１＋）＋ｐ））１＋ｅｘ－ｖ（ｔ－１）×ｐ（

１－ｔ（１＋ｅｘｐ－ｖ）

ｉｄｉｄ

ｉｄ

（）８

（）６

（）式是位的速度与位改变绝对概率之间６

关系，其关系图见图１．根据图１，当位速度为０

（）式就是第ｔ代位改变的概率，其与速度８

关系如图２．根据图２，第ｔ代位改变的概率与两代的速度有关，但其最大改变的概率应该在

图２　位两代速度与位的改变概率之间关系

图１　位速度与位的改变概率之间关系

Ｆｉ．１　Ｒｅｌａｔｉｏｎｏｆｂｉｔｃｈａｎｅｒｏｂａｂｉｌｉｔｔｏｂｉｔｖｅｌｏｃｉｔ　　　　　　ｇｇｐｙｙ　

Ｆｉ．２　Ｒｅｌａｔｉｏｎｏｆｂｉｔｃｈａｎｅｒｏｂａｂｉｌｉｔｔｏｔｗｏｅｎｅｒａｔｉｏｎ　　　　　　ｇｇｐｙｇ　ｖｅｌｏｃｉｔｏｆｂｉｔ　ｙ　

　第５期

刘建华等：离散二进制粒子群算法分析

·５０７·

两代速度都为０时，而最大值为０也就是．５．说，最大位改变概率不超过０作一个特殊假．５．）），）式改为：即ｖ则（设，ｔ＝ｖｔ－１７ｉｄ（ｉｄ（

（）（（）））（））ｔ＝２１－ＳｖｔＳｖｔｐｉｄ（ｉｄ（

）而（式改变得到下式：８（）ｔ＝２１－　ｐ））×ｅｘ－ｖｔ１＋ｐ（ｉｄ（

（）９

根据上面的分析，这里得到以两点结论：（１）位改变概率与速度的变化式应该为

（）式或（式，而不是（式．当速度ｖ８）１０）５）ｔｉｄ（为０时，按文献［位改变概率是９］分析，

而这里得到结果应该０这个结论与０．２５，．５．分Ｊ．ＫｅｎｎｅｄＣ．Ｅｂｅｒｈａｒｔ在文献［９］ｙ和Ｒ．

这将在后面的实验中可以得析结果有差别，

（）

（））１＋ｅｘｔ）ｐ－ｖ（

ｉｄ

（）１０

到检验．

（）２ＢＰＳＯ算法粒子不太可能收敛于全局

最优粒子，因为如果其收敛到全局最优粒子，则其速度为０，这反而位发生改变的概率最大，即此时，搜索具有更强的随机性，缺乏方为０．５．向性．所以，ＢＰＳＯ算法是全局随机搜索性算法，算法本身随着迭代运行，其随机性更强，没有收敛．ＢＰＳＯ算法是缺少局部探测性的随机搜索算法．

这２．３　实验验证　为了验证上节分析的结论，里用实验判断Ｂ实验利用ＢＰＳＯ算法．ＰＳＯ算法来求解基准函数Ｊ．其函Ｄ．Ｓｃｈａｅｒ函数，ｆｆ数形式如下：

ｎ

）（式关系为图３其图形类似一个抛物１０．

）线，其最高点在速度ｖ为０时，最大值为０ｔ．５

．ｉｄ（

图３　位改变的概率与速度关系

Ｆｉ．３　Ｒｅｌａｔｉｏｎｏｆｂｉｔｃｈａｎｅｔｏｂｉｔｖｅｌｏｃｉｔｒｏｂａｂｉｌｉｔ　　　　　　ｇｇｙｐｙ　

）ｆｘ＝２（

２

ｓｉｎ

ｉ＝１

２

０．５∑ｘｉ－

ｎ

２ｉ

２

＋０．５

１＋０．００１×（∑ｘ）（）ｉ＝１

－５０＜ｘ５０ｉ＜

在二维上，利用离散二进制ＰＳＯ算法优化函数最小值，首先对搜索空间每一维编码，每一

１０

维共２位二进制数字表示，迭代运行步数为

这个结论与Ｊ．ＫｅｎｎｅｄＣ．Ｅｂｅｒ－ｙ和Ｒ．］分析结果不同．因为，当速度ｖｈａｒｔ在文献［９ｉｄ

（）为０时，按文献［分析，位改变概率是ｔ９］而这里得到结果应该是０这个结论将０．２５，．５．在后面的实验中可以得到检验．

）根据（式，１ｘｐｉｄ、ｉｄ及ｐｄ分别是二进制位，ｇ

（它们的取值为０或１．因此，和（ｐｐｄ－ｉｄ－ｘｉｄ）ｇ）·（可能为－１，所以ｃｘ０，１．ｒａｎｄ（ｐｉｄ）１·ｉｄ－

）·（的值为区间［ｘ＋ｃｒａｎｄ（－ｐｉｄ）２·ｉｄ）ｄ－ｘｇ（，（］随机值．假设（式只有一ｃｃｃｃ１）１＋２）１＋２）

（）·（项，即ｖ如果ｐｃｒａｎｄ．ｐｉｄ＝２·ｄ－ｘｉｄ）ｄ＝ｇｇ则ｖ这意味位取１或０ｘ０；Ｓ（ｖ＝０．５．ｉｄ，ｉｄ＝ｉｄ）

）的概率分别是一样．由（式，意味８）ｔ＝０．５，ｐ（着粒子的位发生改变的概率为０因此，当粒．５．子的位置都收敛到全局最优粒子位置ｐ粒子ｄ，ｇ达到最高．的位改变概率为５０％，

，，粒子数为２最大限制速度Ｖ每个１００００９．　ｍａｘ＝

１０

，］粒子有二维，每一维区间［被编码成２－５０５０位．对某个粒子的位平均速度随迭代计算如图，其粒子各位取１的平均概率迭代变化如图５４．图６是某粒子的位改变概率迭代变化．某粒子的

１０

也可能不改变，一个粒子共２×２位可能改变，

二进制位，每次迭代计算其位改变数，再除以其

１０

二进制位，得到粒子的位平均改变率．２×２

图４和图５表明粒子速度在减少，并慢慢

地趋向一个固定值上下波动，当然其取１的平）均概率也是具有相同特征．图６更好地反映（８式及图３的特征，从图６可以看出，位的改变是在慢慢增加，位改变概率在０图４显示．５左右；

·５０８·

南京大学学报（自然科学）　　　　　

第４７卷

速度随迭代而靠近０．再结合图６可得，当速度趋靠近０时，速度改变率基本靠近０这．５左右．）式的分析结论．些图的结果验证了对图３及（８图７显示某粒子到最优粒子平均距离的迭代变

化，从图中可以到，粒子与最优粒子距离是慢慢增加，而不趋向０，这图形式反映了粒子不收敛粒子随着迭代越来越具有随于全局最优粒子，机性，缺少局部探测性

．

３　二进制ＰＳＯ的模式分析

从前面的分析可以知道，二进制ＰＳＯ算法因每一次迭代主要是对二进制串位进行改变，此从遗传算法角度来理解，二进制ＰＳＯ是一个每一次迭代是对每一位求出其特殊变异操作，

变异概率，从而对某一位进行变异．其变异概率就是前面改变率．特殊性就在于其求解变异概

是根据当前速度和上代为０或１概率．速率时，

））度为（式，而根据位的速度，利用（式再转变１２为位取１的概率．

ＰＳＯ算法就在于速度是根据粒子靠近最

优点和自身历史位置的距离来求解．因此，二进制粒子变异与最优点和历史自身最优点有关．但从上面分析可以知，粒子越靠近最优点时，其速度越靠近０，位变异率也就越高．当速度为０

　第５期

刘建华等：离散二进制粒子群算法分析

·５０９·

时，位变异概率高达到０．５．

根据遗传算法变异算子性质，模式Ｈ保持概率为：

（ｏＨ）

Ｐ１－Ｐｍ）ｏ（Ｈ）Ｐｍ≈１－ｓ＝（

为模式的阶．从上Ｐｍ为位变异概率，ｏ（Ｈ）

式中分析可，位变异概率Ｐｍ越小，模式Ｈ保

为０，而粒子的位很可能为１．因此，位需要最大可能转变为０；而速度为正，最优粒子和历史最粒子的位很可能为０，位需优位置很可能为１，要最大可能转变为１．

４．１　公式的变换　为了让速度和位改变的关

系与上面分析相符，对（式进行改进．当速度２）为０，希望新的概率映射函数值为０；当速度小于０与大于０时，概率映射函数关于ｙ轴对称，即为偶函数；当速度趋向正负无穷时，概率映射直接对ｓ函数值为１．ｉｍｏｎｄ函数改为如下：ｇ当ｖ０１－ｉｄ≤（１＋ｅｘ－ｖｐｉｄ）

（ｓｖ＝ｉｄ）

０－１当ｖｉｄ＞１＋ｅｘ－ｖｐｉｄ（）１１

（）式的演示图为图８．根据图８，当速度１１（）式概率映射函数为递减；当速度为为负时，１１（）正时，式概率映射函数为递增；当速度为０１１时，函数为０

．

持不变概率越大．从二进制编进化算法理论来说，变异有利于种群的多样性，增强算法全局探测能力．而算法早期应该种群具有多样性，也就但晚期算法的种是增强算法的全局探测能力．

群多样性减性，有利于算法局部探索．因此，进化算法变异概率早期应该大于晚期，才有利于算法性能提高．

从上一节分析可以知道，二进制ＰＳＯ算法其位变异的概率越高．当速度越为０时，ＰＳＯ算法思想是粒子在飞行中，粒子越来越靠近最优粒子，也就是速度慢慢收敛于０．因此，其变异概率越来越大．进而，种群多样性越来越强，全局探测能力越来越增强，缺乏局部探索性．这所以不少利用二进制应该二进制ＰＳＯ的缺点，ＰＳＯ算法求解离散的论文混合一些局部搜索

这种改进策略在不少文献中可以算法原因，看到．

此外，从遗传算理论原理分析来看，二进制其缺少选择操ＰＳＯ算法只是利用了变异算子．

作和交叉操作，并不能保持最优模式能呈指数级增长．

４　二进制ＰＳＯ算法的改进

）式，分析速度公式（公式为三部分，第一１部分ｗ·而第二部分ｃｖｉｄ是速度惯性部分，１·）·（）·和第三部分ｃｒａｎｄ（ｘｒａｎｄ（ｐｉｄ－ｉｄ）２·（分别为自身认知部分和社会认知部ｘｐｄ－ｉｄ）ｇ分．而（和（取值分别－１，ｘｘ０，ｐｐｉｄ－ｉｄ）ｉｄ）ｄ－ｇ１．０意味着ｐ－１意ｉｄ或ｐｄ与ｘｉｄ位的值相等；ｇ

，；味着ｐ而ｘ１意味着ｐｉｄ或ｐｄ为０ｉｄ的值为１ｉｄｇ，或ｐ而ｘ因此，速度ｖ．ｄ为１ｉｄ的值为０ｉｄ的值ｇ意味着最优粒子可以理解为，当速度为０时，

和历史最优位值相等，位应该不需要变化．而当速度为负时，最优粒子和历史最优位置很可能

图８　新概率映射函数

Ｆｉ．８　Ｎｅｗｍａｉｎｆｕｎｃｔｉｏｎｏｆｒｏｂａｂｉｌｉｔ　　　ｇｐｐｇｐｙ　

）对粒子的位值改变式（改为如下形式：３当ｖ０时ｉｄ＜

）（ｒａｎｄ（ｓｖｆ０ｉ≤　ｉｄ）ｘｉｄ＝ｘｏｔｈｅｒｗｉｓｅｉｄ当ｖ０时ｉｄ＞

）（ｒａｎｄ（ｓｖｆ１ｉ≤　ｉｄ）（）ｘ＝１３ｉｄ

ｘｏｔｈｅｒｗｉｓｅｄｉ

）同样，这里ｒ是一个随机数，从区间ａｎｄ（

（）１２

·５１０·

南京大学学报（自然科学）　　　　　

第４７卷

［］（的统一分布中随机产生．为了避免ｓ０，１ｖｉｄ）太靠近１，一个参数Ｖｍａ用于ｘ作为最大速度值，即ｖ限制ｖ－ＶｍａＶｍａ．ｉｄ的范围，ｉｄ∈［ｘ，ｘ］

新方法与原方法区别在于两个层次．首先，是概率映射函数与ｓ目的是ｉｍｏｎｄ函数差别．ｇ让速度趋为０时，其概率函数值为０．第二层次，根据概率函数值让位取０和１形式为（１２）），和（这种形式能保证速度为０时，位的值不１３变；当速度为负时，位只能改变为０；当速度为位只能改变为１．这样做目的，可以让粒正时，

子群最终很容易靠近全局最优粒子，当速度为粒子的位改变率更靠近０的概率增大．这０时，

种思想符合粒子群算法本质理念．

为了检验上述改进思想，利用新的二进制粒子群算法来求解基准函数Ｊ．Ｄ．Ｓｃｈａｆｆｅｒ函数，在二维上，求基准函数Ｊ．Ｄ．Ｓｃｈａｆｆｅｒ的最小值．算法流程与原始二进制粒子群算法类似，）只不过映射函数与位改变为新改进的形式（１１）和（式．１２

首先，对搜索空间每一维编码，每一维共

１０

位二进制数字表示，迭代运行步数为３粒２００，

最大限制速度Ｖｍａ每个粒子有子数为２０，９．ｘ＝１０

二维，每一维区间［被编码成２位，－５０，５０］与前面试验类似，某个粒子的位平均速度随迭

代变化．对一个粒子每位其可能改变，也可能不

１０

改变，一个粒子共２×２二进制位，每次迭代计

再除以其２×１算其位改变数，０２４二进制位，　得到粒子的位改变率．

图９表明粒子速度在减少，并慢慢地趋向个，因此，粒子的位置在很快收敛．根据图１粒０．１

，子到最优粒子的距离也慢慢地靠近０所以粒子的位置趋向于最优粒子．图１０粒子取１的概率，慢慢靠近０这意味粒子的位为１或０的概率．５，图１这各为５０％．１粒子的位改变率慢慢趋向０也意味着粒子在慢慢稳定，并且到了晚期，粒子的位置并没有多少变异发生．因此，本节的改进让粒子能够慢慢收方法与思想符合粒子群思想，

，敛于最优粒子的位置．根据图１位的改变在减１位改变概率非常低，最终不会高于０少，．０５．）用（式和（式来代替原始Ｂ１２１３）ＰＳＯ算

）法（式和（式，粒子会很快收敛于全局点而２３）不动，算法效果会很不理想．从上面分析可以知，原始Ｂ其更具有随ＰＳＯ算法运行到最后时，这说明其是一种全局搜索能力，不具有局机性，

部搜索性．而新公式（和（式刚好与其相１２）１３）收敛很快，因此是局部搜索能力很强，而全反，

局搜索能力很弱．根据一般的启发式随机搜索算法开始应该是需要全局搜索能力，算法原理，

而晚期是需要局部搜索能力．根据这个道理，对算法作如下改进

：

代计算如图９，其粒子各位取１的平均概率迭代变化如图１图１０．１是某粒子的位改变率迭

　第５期

刘建华等：离散二进制粒子群算法分析

·５１１·

ｉｆｉｔｅｒａｘＩｔｅｒ　　　＜γ＊Ｍ

））算法利用（式和（式２３

ｅｌｓｅ

））算法采用新变公式（式和（式１１１２ｅｎｄ

］这里γ是一个参数，其取值为［之间实０，１数，而Ｉｉｔｅｒ为当前运行的迭代步数，ｔＭａｘ为算法迭代运行最大步数．当其为１时，算法就是原当为０时，其完全是新的变换公始ＢＰＳＯ算法；式．这里把这种算法叫做新Ｂ简称为ＰＳＯ算法，ＮＢＰＳＯ．

４．２　与遗传算法混合的二进制ＰＳＯ算法　上述改变思想能保证二进制ＰＳＯ算法能更好收敛到全局最优点，速度为０时，位发生改变的概率为０．二进制ＰＳＯ算法实际可以看作一种特殊变异操作，而且只有变异．新的二进制算法变异率最终变成只有０这与遗传算法的变异．０５，概率取值基本相同．但只有变异操作，不能保证要算法能保证适用度好的模式呈指数级增加，保证好模式呈指数级增加，应该存在遗传算法的选择操作．因此，把遗传算法与新二进制，也就是遗传算法的ＰＳＯ算法混合（ＧＡＢＰＳＯ）变异操作改为这里新的二进制ＰＳＯ算法．４．２．１　混合算法　二进制ＰＳＯ算法与遗传算法的混合主要是把遗传算法中的变异操作更换

事实上就是对遗为新改进的二进制ＰＳＯ算法，其算法流程传算法引进一种新的变异操作．如下：

算法

Ｓｔｅ１　随机产生一个由确定长度的二进ｐ　制串组成的初始种群．

Ｓｔｅ２　对该种群迭代地执行下面的步ｐ　

骤，直到满足某种停止条件：

）计算种群中每个个体的适用值；（ａ

）按由个体适应度值所决定的某个规则（ｂ

选择将进入下一代的个体；

（）按概率Ｐｃｃ进行交叉操作；）执行二进制Ｐ（执行改进ｄＳＯ算法操作：的二进制ＰＳＯ算法公式．

Ｓｔｅ３　把在后代中出现的最好的个体指ｐ　

定为遗传算法的执行结果，这个结果可以表示问题的一个解．

４．３　算法实验分析　为了验证本文算法的有效性，分别采用原始ＢＰＳＯ算法、ＮＢＰＳＯ算法、遗传算法ＧＡ算法和ＧＡＢＰＳＯ算法对下列基准函数的最优问题进行实例计算并进行对为了检验改进效果，先选两个多模态测试函比．

数ｆｆ２、３进行第一类实验：

（）测试函数２：１ｎ维的Ｒａｓｔｒｉｉｎ函数ｇ

２

（］ｘ）＝∑［ｘ１０ｃｏｓ２ｘ＋１０πｆ２（ｉ－ｉ）

ｎ

ｉ＝１

·５１２·

南京大学学报（自然科学）　　　　　

第４７卷

－５．１２＜ｘ５．１２ｉ＜

（）测试函数３：２ｎ维的Ｇｒｉｅｗａｎｋ函数

交叉比例为７变异率为０分别９０％，０％；．５％．

用Ｂ遗传算法）和ＧＡＰＳＯ、ＮＢＰＳＯ、ＧＡ（ＰＳＯ进行优化．为了使计算较为准确，每个函数迭代运行为１每种算法各自运算５表１０００代，０次．　中分别列出两函数用不同算法算出５０次平均最优值．

第一类实验数据如表１．从表中可以看出，对于每个函数所求得值，ＮＢＰＳＯ算法优于原始的ＢＰＳＯ算法．ＧＡＰＳＯ与遗传算法ＧＡ基

但其结果也优于原始的Ｂ本一致，ＰＳＯ算法．

ｉｎ２ｎ

（）ｘ＝ｃｏｓ＋１∑ｘｆ３ｉ－∏

１４０００１）

－６００＜ｘ６００ｉ＜

…，，上两函数的最优点ｘ＊为（最优０，０）值为ｆ（ｘ＊）＝０．

对于这两个基准函数的自变量维数及粒子个数设置如表中所示．算法的参数设置为：ｃ１＝

ｃ１．４，ｗｍａ１．２，ｗｍ０．４；ＮＢＰＳＯ算１．４，２＝ｘ＝ｉｎ＝

法的参数γ＝０遗传算法的选择比例为．９５；

表１　最小平均适应值和标准方差

Ｔａｂｌｅ１　Ｔｈｅｓｍａｌｌｅｓｔｆｉｔｎｅｓｓａｎｄｓｔａｎｄａｒｄｖａｒｉａｎｃｅ　　　　　　

维数１０　

粒子规模２０

函数ＧｒｉｅｗａｎｋＲａｓｔｒｉｒｉｎｇＧｒｉｅｗａｎｋＲａｓｔｒｉｒｉｎｇＧｒｉｅｗａｎｋＲａｓｔｒｉｒｉｎｇ

ＢＰＳＯ　７０．０９５　１９．２５２５　０．０３６２　９０．４４１８　０．０１５７　１６０．７４５０　

ＧＡ　１０．０６７　１３１４３　８２０．０２１　８３１０５　０．０１１７　１３０．４８２８　

ＮＢＰＳＯ　７０．０７５　１４．５４３２　３０．０２２　７８．１２７０　０．０１０９　１２０．４８２８　

ＧＡＰＳＯ４０．０４８　１５．４３５６　２０．０１６　８４．４７８０．００９７　１４２．４２６

２０　４０

３０　８０

利用　　为了进一步验证本文算法的有效性，基本ＢＰＳＯ算法、ＮＢＰＳＯ算法、ＧＡ算法和ＧＡＰＳＯ算法对Ｊ．Ｄ．Ｓｃｈａｆｆｅｒ函数的最小化问题进行实例计算并进行对比．

（）测试函数１：３２维的Ｊ．Ｄ．Ｓｃｈａｆｆｅｒ函数

ｎ

－５０＜ｘ５０ｉ＜

实验数据如表２．实验方法是在第一类实验的条件下，比较４个算法收敛最优的百分比（在计算１００次中有多少次在误差范围内收，以及收敛时平均收敛代数．参数的设置与敛）

上面相同．对上述问题进行了１００次仿真计算，其计算结果如表２所示．

ｘ）＝ｆ１（

２

ｓｉｎ

ｉ＝１

２

０．５∑ｘｉ－

２２　

１＋０．００１×（∑ｘｉ）（）ｉ＝１

ｎ

＋０．５

表２　测试函数ｆ在计算１１的平均寻优结果比较（００次情况下）

）Ｔａｂｌｅ２　Ｃｏｍａｒｉｓｏｎｏｆｍｅａｎｏｔｉｍａｌｒｅｓｕｌｔｓｏｆｔｅｓｔｆｕｎｃｔｉｏｎｆ１（Ａｂｏｕｔｃｏｍｕｔａｔｉｏｎｏｆ１００ｔｉｍｅｓ　　　　　　　　　　　　ｐｐｐ模群

体规２０　４０　

进化

代数

收敛误差

平均收敛率

ＢＰＳＯＢＰＳＯ　ＮＢＰＳＯＰＳＯ　ＧＡ　ＧＡ　Ｂ　２０　７０　

２１　７４　

２４　７３　

２８　８２　

平均收敛代数

ＧＡ　ＧＡＢＰＳＯ　ＮＢＰＳＯ

１０００．００１　　０　２０００．００１　　０　

５６．７１１２．５４７１．６４３９．３６４　５　５　４６８．８６９３．５７８３．９４４０．４６７　５　５　５

　第５期

刘建华等：离散二进制粒子群算法分析

·５１３·

不论从平均收敛概率　　从表２中可以看出，

还是从平均收敛代数来看，ＮＢＰＳＯ算法比基本ＢＰＳＯ算法、ＧＡ算及ＧＡＢＰＳＯ算法有所提高．但性能改善程度来看，平均收敛率比平均收敛代数改善程度更好．因为ＮＢＰＳＯ其主要改善收敛问题，在尽量对探索能力不影响情况下，希望能够改善其收敛性能，更好性能是在粒子第一次找到最优点时，不会飞出此邻域，而产生抖动，振荡现象．从平均收敛代数性能提高中，可以发现ＮＢＰＳＯ比ＢＰＳＯ性能有提高．说明

不会轻易飞出ＮＢＰＳＯ算法能更早收敛最优点，最优点．

：ＥｖｏｌｕｔｉｏｎａｒＣｏｍｕｔａｔｉｏｎ．ＮｅｗＪｅｒｓＩＥＥＥ　ｙｐｙ　，１９９８，６９～７３．Ｐｒｅｓｓ

［ａｒｔｉｃｌｅ４］　ＷｅｉＪＸ，ＳｕｎＹ　Ｈ，ＳｕＸ　Ｎ．Ａｎｏｖｅｌ　　　　　　ｐ

ｓｗａｒｍｏｔｉｍｉｚａｔｉｏｎｂａｓｅｄｏｎｉｍｍｕｎｅｓｅｌｅｃｔｉｏｎ．　　　　　ｐ（），ＪｏｕｒｎａｌｏｆＮａｎｉｎＵｎｉｖｅｒｓｉｔＮａｔｕｒａｌＳｃｉｅｎｃｅｓ　　　ｊｇｙ　，（）：（魏建香，孙越泓，苏新宁．一２０１０４６１１～９．种基于免疫选择的粒子群优化算法．南京大学学，，（）：）报（自然科学）２０１０４６１１～９．

［ａｒｔｉｃｌｅ５］　ＬｉｕＪＨ，ＬｉｕＪＷ．Ａｎｅｗｓｗａｒｍ　　　　　　　ｐ

ｏｔｉｍｉｚａｔｉｏｎａｌｏｒｉｔｈｍａｎｄｒｅａｌｔｉｍｅｃｏｎｔｒｏｌｏｆ　　　－　　ｐｇｓｉｎａｌｉｎｕｒｂａｎｉｎｔｅｒｓｅｃｔｉｏｎ．Ｓｓｔｅｍｓｔｒａｆｆｉｃ　　　　ｇｙ，（）：（刘建华，Ｅｎｉｎｅｅｒｉｎ２００７，２５７８３～８７．ｇｇ刘建伟．基于粒子群算法的城市单交叉口信号（）：）控制．系统工程，２００７，２５７８３～８７．

［，Ａ６］　ＡｌｅｒＢ，ＶｉｎｃｅｎｔＪｎａｋｏｈａＣ．Ａｒｅｖｉｅｗｏｆ　　　　　ｙ

ａｒｔｉｃｌｅｗａｒｍｔｉｍｉｚａｔｉｏｎ．　ｓ　ｏｐｐ，（）：Ｃｏｍｕｔｉｎ２００８，７３１０９～１２４．ｐｇ

［ａｒｔｉｃｌｅ７］　ＬｉｕＪＨ，ＦａｎＸＰ，ＱｕＺＨ．Ａｎｅｗ　　　　　　　　ｐ

ｔｉｍｉｚａｔｉｏｎｌｏｒｉｔｈｍａｓｅｄｎｓｗａｒｍ　ｏ　ａ　ｂ　ｏｐｇ，２ｓｉｍｉｌａｒｉｔ．Ｃｏｎｔｒｏｌｎｄｅｃｅｉｏｓｎ００７，　ａ　Ｄｙ（）：（刘建华，樊晓平，瞿志２２１０１１５５～１１５９．华．一种基于相似度的新型粒子群算法．控制（）：）与决策，２００７，２２１０１１５５～１１５９．

［８］　ＬｉｕＪＨ，ＦａｎＸＰ，ＱｕＺＨ．Ａｎｉｍｒｏｖｅｄ　　　　　　　ｐ

ｗａｒｍｔｉｍｉｚａｔｉｏｎｉｔｈｕｔａｔｉｏｎａｒｔｉｃｌｅ　ｓ　ｏ　ｗ　ｍｐｐ

ｒｄ

ｂａｓｅｄｎｉｍｉｌａｒｉｔ．Ｔｈｅｎｔｅｒｎａｔｉｏｎａｌ　ｏ　ｓ　３　Ｉｙ

５　总　结

本文对二进制ＰＳＯ算法从位改变率和遗两种分析结传算法的模式概念两方面作分析．

论基本一致，那就是原始二进制ＰＳＯ算法随机能很好具有全局探索能力，但其不会收性很强，

敛到全局最优粒子，随着迭代运行，其随机反而因此，离散二进制Ｐ会增强．ＳＯ算法是一个缺乏局部探测性的算法．这个结论为二进制算法的应用提供改进的指导意义．本文基于上述分析结论，提出两种改进方法，一种是改进原始离散二进制ＰＳＯ算法的概率变换公及其位的取新的公式有助于粒子收敛于群体最优粒值式，

子，增强局部探测性．另一种方法是让离散二进制Ｐ利用二进制ＰＳＯ算法与遗传算法结合，ＳＯ算法代替遗传算法的变异操作．通过实验仿真检测，新的改进方法有效实用．

Ｒｅｆｅｒｅｎｃｅｓ

［１］　ＥｂｅｒｈａｒｔＲ，ＫｅｎｎｅｄＪ．Ａｎｅｗｏｔｉｍｉｚｅｒｕｓｉｎ　　　　ｙｐｇ　

ｔｈ

ａｒｔｉｃｌｅｓｗａｒｍｔｈｅｏｒ．Ｐｒｏｃｅｅｄｉｎｓｆｈｅ　　　ｏ　ｔ　６ｐｙｇ

Ｎａｔｕｒａｌ

，ｏｎＮａｔｕｒａｌＣｏｍｕｔａｔｉｏｎ．ＨａｉｋｏｕＣｏｎｆｅｒｅｎｃｅ　　　ｐ，Ｃｈｉｎａ２００７，９：８２４～８２８．

［，Ｅ９］　ＫｅｎｎｅｄＪｂｅｒｈａｒｔＲ．Ａｄｉｓｃｒｅｔｅｂｉｎａｒ　　　ｙｙ　

ｖｅｒｓｉｏｎｆｈｅａｒｔｉｃｌｅｗａｒｍｌｏｒｉｔｈｍ．　ｏ　ｔ　ｐ　ｓ　ａｇＰｒｏｃｅｅｄｉｎｏｆｔｈｅＷｏｒｌｄＭｕｌｔｉｃｏｎｆｅｒｅｎｃｅｏｎ　　　　ｇ　，ＣＳｓｔｅｍｉｃｓｂｅｒｎｅｔｉｃｓａｎｄＩｎｆｏｒｍａｔｉｃｓ．Ｎｅｗ　　ｙｙ：，ＪｅｒｓＰｉｓｃａｔａｗａ１９９７，４１０４～４１０９．ｙｙ

［］，Ａ１０ａｌｍａｎＡ，ＡｈｍａｄＩｌａｄａｎｉＳ．Ｐａｒｔｉｃｌｅ　Ｓ　　－ｍ　

ｔｉｍｉｚａｔｉｏｎｏｒａｓｋｓｓｉｎｍｅｎｔｓｗａｒｍ　ｏ　ｆ　ｔ　ａｐｇ，ａｎｄＭｉｃｒｏｓｓｔｅｍｓｒｏｂｌｅｍ．Ｍｉｃｒｏｒｏｃｅｓｓｏｒｓ　　ｐｐｙ（）：２００２，２６８３６３～３７１．

［］，Ｇａｒｔｉｃｌｅ１１ｉａｎＺｕＸ，ＪｉａｏＢ．Ａｎｏｖｅｌｓｗａｒｍ　Ｌ　　　　　　ｐ

ｅｒｍｕｔａｔｉｏｎｏｔｉｍｉｚａｔｉｏｎａｌｏｒｉｔｈｍｆｏｒｆｌｏｗｓｈｏ　　　　－ｐｐｇｐｓｃｈｅｄｕｌｉｎｔｏｍｉｎｉｍｉｚｅｍａｋｅｓａｎ．ＣｈａｏｓＳｏｌｉｔｏｎｓ　　　ｇｐ　，，（）：ａｎｄＦｒａｃｔａｌｓ２００８３５５８５１～８６１．　

［］，１２ｉａｏＣＪＴｓｅｎＣＴ，ＬｕａｒｎＰ．Ａｄｉｓｃｒｅｔｅｖｅｒｓｉｏｎ　Ｌ　　　　　　ｇ　

ａｒｔｉｃｌｅｏｆｗａｒｍｔｉｍｉｚａｔｉｏｎｏｒｌｏｗｓｈｏ　ｐ　ｓ　ｏ　ｆ　ｆｐｐｒｏｂｌｅｍ．ＣｏｍｕｔｅｒｓｓｃｈｅｄｕｌｉｎａｎｄＯｅｒａｔｉｏｎｓ　　ｐｐｇｐ　

ＩｎｔｅｒｎａｔｉｏｎａｌＳｍｏｓｉｕｍｏｎＭｉｃｒｏＭａｃｈｉｎｅａｎｄ　　　　　ｙｐ，，，Ｓｃｉｅｎｃｅ．ＮａｏａＪａａｎ１９９５３９～４３．Ｈｕｍａｎ　ｇｙｐ

［，Ｅ２］　Ｋｅｎｎｅｄｂｅｒｈａｒｔａｒｔｉｃｌｅｗａｒｍ　Ｒ．Ｐ　ｓｙ　Ｊ

ｏｔｉｍｉｚａｔｉｏｎ．ＩＥＥＥＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅ　　ｐ

，Ｎ：ＮｅｕｒａｌＮｅｔｗｏｒｋｓ．ＰｉｓｃａｔａｗａｅｗＪｅｒｓｏｎ　　　ｙｙ，ＩＥＥＥＳｅｒｖｉｃｅＣｅｎｔｅｒ１９９５，１９４２～１９４８．　　

［ａｒｔｉｃｌｅ３］　ＳｈｉＹ，ＥｂｅｒｈａｒｔＲ．Ａ　ｍｏｄｉｆｉｅｄｓｗａｒｍ　　　　ｐ

ｏｔｉｍｉｚｅｒ．ＩＥＥＥＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎ　　　ｐ

·５１４·

南京大学学报（自然科学）　　　　　

第４７卷

，，（）：Ｒｅｓｅａｒｃｈ２００７３４１０３０９９～３１１１．

［］，Ｆ１３ｏｒｒｅａＥＳｒｅｉｔａｓＡ　Ａ，ＪｏｈｎｓｏｎＣＧ．Ｐａｒｔｉｃｌｅ　Ｃ　　　　　

ｓｗａｒｍｏｒｔｔｒｉｂｕｔｅｅｌｅｃｔｉｏｎｎａｅｓｉａｎ　ｆ　ａ　ｓ　ｉ　Ｂｙ：Ａｒｏｔｅｉｎｃｌａｓｓｉｆｉｃａｔｉｏｎｎａｌｉｃａｔｉｏｎｔｏｆｕｎｃｔｉｏｎ　　　　ｐｐｐｏｆｒｔｉｆｉｃｉａｌＥｖｏｌｕｔｉｏｎａｎｄｒｅｄｉｃｔｉｏｎ．Ｊｏｕｒｎａｌ　　Ａ　　ｐ

，，（）：Ａｌｉｃａｔｉｏｎｓ２００８８２１～１２．ｐｐ

［］１４ｈｅｎＱ，ＳｈｉＷ　Ｍ，ＫｏｎＷ，ｅｔａｌ．Ａｃｏｍｂｉｎａｔｉｏｎ　Ｓ　　　　ｇ　

ａｒｔｉｃｌｅｏｆｍｏｄｉｆｉｅｄｓｗａｒｍｏｔｉｍｉｚａｔｉｏｎａｌｏｒｉｔｈｍ　　　　　ｐｐｇｓｕｏｒｔｖｅｃｔｏｒｍａｃｈｉｎｅｆｏｒｓｅｌｅｃｔｉｏｎａｎｄａｎｄｅｎｅ　　　　　　　ｐｐｇ，，（）：ｔｕｍｏｒｃｌａｓｓｉｆｉｃａｔｉｏｎ．Ｔａｌａｎｔａ２００７７１４１６７９　６８３．～１

［］１５ｉｎＰＹ．Ａｄｉｓｃｒｅｔｅａｒｔｉｃｌｅｓｗａｒｍａｌｏｒｉｔｈｍｆｏｒ　Ｙ　　　　　　　ｐｇ

ｏｔｉｍａｌｏｌｏｎａｌａｒｏｘｉｍａｔｉｏｎｏｆｄｉｉｔａｌｃｕｒｖｅｓ．　　　　　ｐｐｙｇｐｐｇｆｉｓｕａｌｏｍｍｕｎｉｃａｔｉｏｎｎｄｍａｅＪｏｕｒｎａｌ　ｏ　Ｖ　Ｃ　ａ　Ｉｇ，，（）：２００４１５２２４１～２６０．Ｒｅｒｅｓｅｎｔａｔｉｏｎｐ

［］，Ｈ１６ｈａｎＸ　Ｍ，ＳｕｎＬＢａｎＪＱ，ｅｔａｌ．Ａｎ　Ｚ　　　　　ｇ　

ａｒｔｉｃｌｅｏｆｓｗａｒｍｉｎｔｅｌｌｉｅｎｃｅｂｉｎａｒａｌｉｃａｔｉｏｎ　　　　ｐｇｙｐｐ　ｓｗａｒｍｔｉｍｉｚａｔｉｏｎ　ｏｐ（）：ＸＬ４９４９～９６３．

［］１７ｕｈＧＣ，ＬｉｎＣＹ，ＬｉｎＹＳ．Ａｂｉｎａｒａｒｔｉｃｌｅ　Ｌ　　　　　　　ｙｐ　

ｓｗａｒｍｔｉｍｉｚａｔｉｏｎｏｒｏｎｔｉｎｕｕｍｔｒｕｃｔｕｒａｌ　ｏ　ｆ　ｃ　ｓｐ，ｔｏｏｌｏｏｔｉｍｉｚａｔｉｏｎ．ＡｌｉｅｄＳｏｆｔＣｏｍｕｔｉｎ　　ｐｇｙｐｐｐｐｇ　，（）：２０１０１１２２８３３～２８４４．

［］１８ｏｈｄＳ　Ｍ，ＳｉｅｒｕＯ，ＳａｆａａｉＤ，ｅｔａｌ．Ｐａｒｔｉｃｌｅ　Ｍ　　　　ｇ

ｔｉｍｉｚａｔｉｏｎｉｔｈｏｄｉｆｉｅｄｉｍｏｉｄｓｗａｒｍ　ｏ　ｗ　ａ　ｍ　ｓｐｇｆｕｎｃｔｉｏｎｆｏｒｅｎｅｓｅｌｅｃｔｉｏｎｆｒｏｍｅｎｅｅｘｒｅｓｓｉｏｎ　　　　　　ｇｇｐ，，（）：ｄａｔａ．ＡｒｔｉｆｉｃｉａｌＬｉｆｅａｎｄＲｏｂｏｔｉｃｓ２０１０１５１２１　　　４．～２

（ＢＰＳＯ）ａｌｏｒｉｔｈｍｏ　ｔｇ

，，ｍｕｌｔｉｆｏｃｕｓｉｍａｅｆｕｓｉｏｎ．ＯｔｉｃａＡｌｉｃａｔａ２０１０－　　　ｇｐｐｐ