新的仿生优化算法_食物车-蟑螂群优化算法

—208— 新的仿生优化算法：食物车-蟑螂群优化算法 程 乐，徐义晗，张洪斌，钱兆楼，冯 刚 (淮安信息职业技术学院计算机科学与工程系，江苏 淮安 223003) 摘 要：提出一种新的仿生优化算法——食物车-蟑螂群优化算法。该算法模拟蟑螂的觅食行为，通过食物车在解空间定义域内抛洒食物， 吸引蟑螂向食物爬行，完成搜索。在求解过程中通过巢穴变迁、平等搜索和食物筛选等策略加强全局搜索和局部搜索能力，提高算法收敛 速度。仿真实验结果表明，该算法寻优率高，收敛速度快。 关键词：仿生优化算法；食物车-蟑螂群优化算法；巢穴变迁；食物筛选 New Bionics Optimization Algorithm: Food Truck-Cockroach Swarm Optimization Algorithm CHENG Le, XU Yi-han, ZHANG Hong-bin, QIAN Zhao-lou, FENG Gang (Department of Computer Science and Engineering, Huaian College of Information Technology, Huaian 223003, China) 【Abstract】This paper proposes a new bionics optimization algorithm named Food Truck-Cockroach Swarm Optimization(FT-CSO). Food is thrown by food truck in solution space, and cockroaches crawl to the food and search for optimal solutions. Nest migration, food filtration and equality search are used to enhance global and local search ability of FT-CSO. Simulation experimental result shows that the algorithm has high optimization rate and convergence speed. 【Key words】bionics optimization algorithm; Food Truck-Cockroach Swarm Optimization(FT-CSO) algorithm; nest migration; food filtration 计 算 机 工 程 Computer Engineering 第 36卷 第 18期 Vol.36 No.18 2010年 9月 September 2010 ·人工智能及识别技术· 文章编号：1000—3428(2010)18—0208—02 文献标识码：A 中图分类号：TP301.6 1 概述 近几年，仿生算法中一类群智能优化算法受到了广泛关 注。此类算法通常以模拟群居生物觅食行为作为寻优手段， 具有收敛性强、计算代价低、易于并行编程实现等特点，如 蚁群优化算法(Ant Colony Optimization, ACO)[1]和微粒群优 化算法(Particle Swarm Optimization, PSO)[2-3]。传统的群智能 优化算法在求解连续优化问时通常存在一定局限性。例如， PSO算法容易早熟；ACO算法擅长处理 TSP等离散域问题， 但处理连续域问题时寻优率低、收敛速度慢。为了克服 PSO 算法的早熟，一些改进的 PSO算法被提出，例如惯性权重线 性递减的 PSO 算法、θ-PSO 算法。而为了将 ACO 应用到连 续域，有学者提出了二进制蚁群算法、API(After Pachycondyla Apicalis)算法等。这些改进算法显著提高了传统 ACO和 PSO 算法的性能。 本文在借鉴已有群智能优化算法处理连续问题成功经验 的基础上，通过模拟蟑螂的觅食行为，提出一种新的连续优 化算法：食物车-蟑螂群优化(Food Truck-Cockroach Swarm Optimization, FT-CSO)算法。 2 解决连续空间优化问题的 FT-CSO算法 2.1 FT-CSO算法策略 为了方便介绍本文算法，以符号 C 代表算法中的蟑螂， 以符号 T 代表算法中的食物车，以符号 F 代表算法中的食 物。 T 、C 、 F 在解空间都有确定的位置坐标，其位置坐标 均可表示为向量 1 2( , , , )Dx x x=x " 。 2.1.1 T迁移、食物抛洒与食物筛选策略 FT-CSO 算法中 T 的主要功能是记录当前最优解和抛洒 食物。因此，T 中设有食物抛洒装置 Ts 和记录当前最优解装 置 Tr 。其中， Ts 记录上次算法迭代产生的最优解，本次迭 代不更新，Ts 的向量为当前 T 所在的位置坐标，本次迭代的 所有食物由 Ts 生成，如图 1所示。 图 1 食物抛洒 Tr 时刻记录算法到目前为止搜索到的最优解，因此，会 频繁更新。在下一次迭代开始前，如果 Tr记录的解优于当前 Ts ，则 Tr 赋值给 Ts ： Ts Tr= 。 设算法中一次生成 k 个 F 。每个 1 2( , , , )i i i iDF f f f " ( 1,2, , )i k= " 是由 1 2( , , , )nTs ts ts ts " 与向量 1 2( , , , )Dλ λ λ=λ " 相 加得到的。 λ的分量生成如下： i Rand Stepλ = × (1) 其中， Rand 为一个随机整数； Step 为步长，具体数值可以 根据实际问题设定。由 Ts 生成 F 的如下： F Ts= + λ (2) 为兼顾全局搜索和局部搜索， F 有 2种抛洒：局部 抛洒与全局抛洒。局部抛洒目的是使食物抛洒在 T 附近，全 局抛洒则使食物抛洒在整个解的定义域空间中。2 种抛洒方 法主要通过限制 Rand 的取值范围实现。局部抛洒时 Rand 的 基金项目：国家自然科学基金资助项目(60673102)；江苏省自然科学 基金资助项目(BK2006218) 作者简介：程 乐(1979－)，男，讲师、硕士，主研方向：人工智能， 智能控制；徐义晗，讲师、硕士；张洪斌，研究员、硕士；钱兆楼、 冯 刚，讲师、硕士 收稿日期：2010-03-03 E-mail：cl211282@163.com —209— 取值范围为： [( ) /( ), ( ) /( )]Min Step Max Stepη η× × ；全局抛洒时 Rand 的取值范围为： [ / , / ]Min Step Max Step ，其中， η 为域 划分值，其值与局部抛洒时食物抛洒范围的大小呈反比。因 此，可以通过调节η 值来调整局部抛洒的范围。在 k个 F 中， 抛洒到局部和全局的比例可以调整。 Ts 生成若干 F 后，要根据当前 Tr 和 F 的适应值设定一 个食物 _F level。在全局抛洒过程中，如果 Ts 生成的 F 的评价函数值低于 _F level，则该食物不被抛出。食物筛选 只针对全局抛洒。随着迭代的深入、 Tr 优化程度的提高， _F level的水平也将提高。 筛选过程保证了吸引 C 爬行的 F 的质量，同时在很大程 度上减少了本次抛洒的实际 F 数量，提高了算法收敛速度。 本文实验中局部和全局的 F数量各为 / 2k ，则 _F level为： 1 _ (2 _ ) / k i i F level F fit k = = × ∑ (3) 2.1.2 C爬行与平等搜索策略 平等搜索策略如下：每一个 C 的行为(如觅食、寻找黑暗 巢穴)都会引来其同伴的追随[3]，因此，在 FT-CSO中，每个 C 向 F 爬行时都会引来算法内其他 C 向该 F 爬行，如图 2 所 示，并沿途搜索更优的解。平等搜索策略使算法具有较强的 全局和局部搜索能力。 图 2 C 向 iF 爬行过程 假设算法中有 m个 C 。爬行时 1 2( , , , )( 1,2, , )j j j jDC c c c j m=" " 的每个分量每次前进一个 Step。于是 C 向 F 或者 T 爬行的一 步可表示为向量 1 2( , , , )Dγ γ γ=γ " 。分量 ( 1,2, , )i i Dγ = " 的取值 可以是 Step− 、0 和 Step。以 C 向 F 爬行为例， iγ 的取值情 况描述如下： (1)初始 i ic f= ，则 0iγ = ； (2)初始 i ic f< ，本次爬行后 i ic f< ，则 i Stepγ = ； (3)初始 i ic f< ，本次爬行后 i ic f> ，则 0iγ = ； (4)初始 i ic f> ，本次爬行后 i ic f> ，则 i Stepγ = − ； (5)初始 i ic f> ，本次爬行后 i ic f< ，则 0iγ = 。 由此可见，当 1 2( , , , )Dγ γ γ=γ " 的分量 ( 1,2, , )i i Dγ = " 全部 为 0时，个体 C 向 F 爬行结束。当所有 F 搜索完成后，C 群 将向 T ( T 的坐标为 Ts )爬行一次。 根据以上描述， C 向 F 或者 T 爬行的公式为 1t tC C+ = + γ (4) 2.1.3 巢穴迁移策略 自然界的 C 不同于蚂蚁、蜜蜂等群居生活的昆虫，没有 固定的巢穴，经常集体“搬家”，因此，FT-CSO 在每次迭代 后。群 C 返回到一个随机生成的新巢穴(位置坐标)。然后在 下一次迭代中从新的巢穴位置爬向 F 或者 T ，并且沿途搜索 更优的解，即巢穴迁移策略。巢穴迁移加强了算法全局搜索 能力，一定程度上避免了早熟。 2.2 FT-CSO算法步骤 结合 2.1 节的描述，以全局优化中最小化问题为例，描 述 FT-CSO算法流程。 Step1 初始化 C 群：定义种群规模 m，初始化每个 C 的 位置坐标(巢穴) 1 2( , , , )( 1,2, , )j j j jDC c c c j m=" " 。初始化 T ：选 择 C 群中适应值最高的 *C ， *Ts C= ， *Tr C= ，此时 Ts 、Tr 相等，对算法无影响。初始化 k， k为 Ts 一次抛洒的食物个 数。初始化算法的总迭代次数 M 。 Step2 Ts 生成 F ：根据 Ts 和当前所有全局抛洒的 F 的 适应值水平设置 _F level，在求解空间内进行近端抛洒和全 局抛洒(式(1)~式(3))。 Step3 C 群向 F 爬行：算法逐个判定 Step2 生成的所有 F 。设当前 ( 1,2, , )iF i k= " 的适应值为 _F fit，如果 _F fit > _F level，则本次爬行不发生，算法转向判断 1iF+ 是否满足筛 选条件；如果 _F fit≤ _F level，则本次爬行发生， C 群爬 向 iF ，如果沿途搜索到更优的解，则利用式(4)更新 Tr 。 Step4 C 群向 T 爬行：C 群向当前食物车的坐标( Ts )爬 行，如果沿途搜索到更优的解，则利用式(4)更新 Tr 。 Step5 巢穴变迁：随机重新分配群内所有 C 初始位置 (巢穴)。 Step6 判断算法是否结束：满足算法结束条件( Tr 达到最 优或者算法总迭代次数达到 M )，则算法结束，否则，如果 Tr < Ts ，则 Ts Tr= ，转 Step2。 3 计算机仿真实验 为了验证 FT-CSO 算法的性能，进行了大量实验，包括 与新近改进的粒子群优化算法的比较实验。实验设备为一般 PC，CPU 为 Intel Pentium Dual CPU 1.6 GHz、1 014 MB Memory，实验仿真软件为 VC++ 6.0。 实验用测试函数如下： 2 2 2 1 2 1 2 2 2 1 2 (sin 0.5) 0.5 (1 0.001( )) x x f x x + −= − + + , x∈ [-10,10] 5 5 2 1 2 1 1 2 2 1 2 [ cos(( 1) )] [ cos(( 1) )] ( 1.42513) ( 0.800 32) , [ 10,10] i j f i i x i j j x j x x x = = = + + + + + ∑ ∑ + + + ∈ − 2 2 2 3 1 1 [100 ( ) ( 1) ] D i i i i f x x x+= = × − + −∑ , x∈ [-2.048, 2.048] 2 4 1 1 1 120 e 20 exp( 0.2 ) exp[ cos(2π )] D D i i i i f x x D D= = = + − × − −∑ ∑ , x∈ [-32.768, 32.768] 1 2 5 1 418.982 9 sin( ) D i i i f D x x = = × − ×∑ , x∈ [-500,500] 2 6 1 [ 10 cos(2π ) 10] D i i i f x x = = − × +∑ , x∈ [-5.12,5.12] 2 2 0.25 2 2 2 0.1 7 1 2 1 2( ) [sin (50(( ) )) 1.0]f x x x x= + + + , x∈ [-10,10] 2 4 2 2 2 8 1 1 1 1 2 2 2(4 2.1 / 3) ( 4 4 )f x x x x x x x= − + + + − + , x∈ [-10,10] 2 2 2 2 9 1 2 1 2( 11) ( 7)f x x x x= + − + + − , x∈ [-10,10] 其中，f1 的极值为 1；f2 的极值为-176.137 5；f8 的极值为 -1.031 628；其他函数的极值都为 0。 3.1 FT-CSO寻优性能测试 表 1 为 FT-CSO 对 1f ~ 6f 这 6 个著名的复杂多峰测试函 数的实验结果，包括在满足解的精度前提下求得的各函数最 优解的成功率 G、最优、最差和平均解 Value 以及求得满足 精度的解所需要的平均、最多和最少评价次数 Evals。实验中 FT-CSO对每个测试函数连续运行 100次，求解精度为 1e-20。 从表 1 可以看到，算法在有限且较少的评价次数内能够稳定 地收敛到精度较高的函数最优解。 (下转第 213页) 圈8摩套后豹伪彩色图片 圈9 2诙分类嚣结果 圈lO分为7类的圈像 圈ll使用lsodata的分类结果 从图8、图lO和图11可以看出，使用Isodata算法分类 的结果与图8差别较大，特别是在本应属于一类的位置中插 入多个类的数据，如对于图lO中圆圈内明显为～类，本文算 法能很好地进行分类，而图ll中使用Isodata算法则将它分 为多个类，误差较大，精度较低。表2是本算法和Isodata算 法的比较。 表2本文算法和lsodata算法的运行时问对比 算法 运fr时Ihlh, Isodata l()24 本史并法857 9结束语 本文在研究了很多无监督分类法的基础上，提出一种新 的无监督分类方法，可以实现数据的高效自动分类。下一步 工作将改进计算算法，进一步降低计算时间。 参考文献 (1】余红伟，张艳宁，袁和金．一种无监督高光谱图像分类算法【JJ． 中国图象图形学报，2008，13(6)：1123一1127． [21LuQuabo，XiangLibin，XueBin，eta1．EndmemberDetermination inHyperspectralData[J]．ActaPhotonicaSinica,2005，34(9)： 1336一1339． 131DuPeijun，FangTao．TangHong，eta1．SpectralFeaturesEx仃acfion inHyperspectralRSDataandItsApplicationtoInformation Processing[J]．ActaPhotonicaSinica。2005，34(2)：293—298． [41GengXiurui，ZhangXia,ChenZhengchao，eta1．Classification AlgorithmBasedonSpatialContinuityforHyperspectmlImage[J]． JournalofInfraredandMillimeterWaves．2004，23(4)：299—302． [51FaridM，LorenzoB．ClassificationofHyperspectralRemoteSensing ImageswithSupportVectorMachines[J]．IEEETransactionson GeoscienceandRemoteSensing，2004，42(8)：1778—1790． 161JiaXiuping，RichardsJ A．Cluster-spaceRepresentationfor hyperspectralDataClassificationlJ]．IEEETransactionson GeoscienceandRemoteSensing，2002．40(3)：593—598． 编辑陆燕菲 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯～～ (上接第209页) 襄1 复杂多峰函敦的测试结果 函(Ⅳ 丝!丝 数 《％) 平均 肇优 ^ 100 1 000Oe+001 00(JOe+00 ^83一1835202 -1860369 ^ 91 1．9344e．272．0875e一28 矗 98 2．8899e．142．428Oe．14 最差 ￡vnts 平均 最少 最多 698 1603200 230 60 520 17l 50 290 185 100 300 l 000Oe+00 ．1790264 60594e．27 7，0466e．14 ^87凄盟翟嚣-19503e+00184 100 2．40 五 !!!．!型!：：婴些!塑：2：：121：!!!!：：!!尘 ：! !：1 3．2与PPBO算法的对比实验 PPBO(PSO··inspiredProbability·-basedBinaryOptimiza·- tion)13i是一种较新的改进的PSO算法，其在求解精度、收敛 速度等方面均较之前的PSO变异算法有较大提高。表2列出 了PPBO与FT-CSO的对比实验数据，包括群规模m、最优 解Vbest、平均解Vage、求得最优解的成功率G、找到最优 解所需要的平均评价次数Eage。 表2 PPBO与FT-CSO对比实验结果 函数 算法 Vbest Vage G，(％) Eage PPBO(m=2010 6 1le-6 88 10860 ^PPBOfm=40)04．83e．7 98 9800 F，r-CSO(，，l=10J 0 0 100 426 PPBO(m=20)00259 80 2700 矗PPBOfro--40)01．89e一5 98 7800 FT．CSO(m=10}00 100 114 PPBO(m=20l0 0 100 2860 疗PPBO(m=40)00 100 4080 FT-CSO(，，l=1010 0 100 309 PPBO(m=20)．1 031628．1．03l626 96 5460 五PPBO(ra=40)-1．031628．1．03l628 100 6160 FT-CSO(m=101-1．03l625一l 03l625 100 303 PPBO(m：20)02．33e一4 56 6760 ^PPBO(m=40)01．578e．5 60 11920 FT．CSO(m=1010 769e．6 7l 856 表2中，PPBO求解精度为le一5；FT-CSO参数如下： t=10，Step=o．02；PPBO参数如下：q=L?2=2，‰=50， ‰。=-50，‰=20，‰。=-20。可以看出，FT-CSO在群 规模较小的情况下，利用远少于PPBO的评价次数便可以稳 定地收敛到与PPBO精度相当的全局最优解，证明了FT-CSO 的稳定性高、收敛性强。 4结束语 本文从研究新的仿生算法角度对优化领域进行研究，提 出了FT-CSO算法。根据实验结果，FT-CSO所表现出的收敛 速度、求解精度、稳定性均令人满意。但是FT-CSO算法仍 然存在一些不足。例如，算法中每个C的行为都会引来其他 所有c的追随，在群规模较大时势必会影响算法执行效率。 下一步将就这些问题对算法进行改进。 参考文献 【l】孙琦，王东．具有粒子群特征的优化并行蚁群算法【J】．计算 机工程，2008，34(24)：208—210． 【21焦巍，刘光斌．一种新的双子群PSO算法fJ】．计算机工程， 2009．35(16)：173—174． 【3】ZhenLanlan，WangLing．ANovelPSO—inspiredProbability—based BinaryOptimizationAlgorithm[C]／／Proc．ofInt’lSymposiumon InformationScienceandEngineering．Shanghai，China：fs．n．】， 2008． 编辑张帆 一213— 新的仿生优化算法:食物车-蟑螂群优化算法 作者： 程乐， 徐义晗， 张洪斌， 钱兆楼， 冯刚， CHENG Le， XU Yi-han， ZHANG Hong-bin， QIAN Zhao-lou ， FENG Gang 作者单位： 淮安信息职业技术学院计算机科学与工程系,江苏,淮安,223003 刊名： 计算机工程 英文刊名： COMPUTER ENGINEERING 年，卷(期)： 2010,36(18) 参考文献(3条) 1.Zhen Lanlan;Wang Ling A Novel PSO-inspired Probability-based Binary Optimization Algorithm 2008 2.焦巍;刘光斌 一种新的双子群PSO算法[期刊]-计算机工程 2009(16) 3.孙琦;王东 具有粒子群特征的优化并行蚁群算法[期刊论文]-计算机工程 2008(24) 本文链接：http://d.g.wanfangdata.com.cn/Periodical_jsjgc201018072.aspx