基于均匀免疫优化算法的最大团问题求解.pdf

《基于均匀免疫优化算法的最大团问题求解.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、CN43—1258／TP计算机工程与科学第37卷第3期2015年3月ISSN1007—130XComputerEngineering&ScienceVo1．37．No．3，Mar．2015文章编号：1007—130X(2015)03—0534—05基于均匀免疫优化算法的最大团问题求解汪宏海，张正球。(1．西安电子科技大学计算机学院，陕西西安710071；2．赣州师范高等专科学校计算机系，江西赣州341000；3．福建师范大学软件学院，福建福州350027)摘要：最大团问题是一种典型的组合优化问题，具有广泛的应用背景。针对最大团问题的NP特性，提出了一种基于免疫克隆优化的智能求解算法。描述了最

2、大团问题的数学模型，设计了求解最大团问题的抗体编码、亲和度函数、变异算子及抗体修正方法。在免疫克隆参数设置时，将其描述为多因素多水平的均匀设计，减少了设置参数的实验次数。通过最大团问题的基准算例进行了实验。结果表明，本算法求解效果较好，并且求解速度较快。关键词：免疫优化；最大团问题；抗体编码；均匀设计中图分类号：TP18文献标志码：Adoi：10．3969／j．issn．1007—130X．2015．O3．O21A●Unl●f，●Orml●mmunec一lone0based_‘inte’l’li‘gentopti‘mi‘zat‘‘ionalgorithmtosolvethemaximumcl

3、iqueproblemWANGHong—hai．ZHANGZheng—qiu。(1．SchoolofComputer，XidianUniversity，Xi’an710071；2．DepartmentofComputersScience，GanzhouTeachersColleage，Ganzhou341000；3．FacultyofSoftware，FujianNormalUniversity，Fuzhou350027，China)Abstract：Themaximumcliqueproblemisatypicalcombinatorialoptimizationproblem，which

4、haswideapplicationbackground．FortheNPcharacteristicofthemaximumcliqueproblem，animmuneclonebasedonintelligentoptimizationalgorithmisproposedtosolveit．Themathematicalmodelofthemaximumcliqueproblemisdescribed．Forsolvingthemaximumcliqueproblem，antibodyencoding，af—finityfunction，mutationoperatorandantib

5、odycorrectionmethodaredesigned．Toreducethenumberofparametersettingfortheexperiment，itisconvertedintoauniformdesignproblemofmulti—factorandmulti-leve1．TheBenchmarkexperimentalresultsshowthatthealgorithmhasbetterperformanceandrapidsolvingspeed．Keywords：immuneoptimization；maximumcliqueproblem；antibody

6、encoding；uniformdesign因此，研究最大团问题具有较高的理论价值和现实1引言意义。最大团问题是一类典型的NP完全问题。目最大团问题MCP(MaximumCliqueProb—前，求解MCP问题的算法主要分为两类：确定性lem)是图论中的一个经典组合优化问题，也称为最算法和启发式智能算法。常见的确定性算法大独立集问题n]。MCP在市场分析、方案选择、计有分支限界算法和回溯算法等，确定性算法要算机视觉、故障诊断等领域具有非常广泛的应用。求在有效的时间内给出最大团问题的最优解，而非*收稿日期：2013—11—0I；修回B期：2014—02—24基金项目：福建省教育厅JK类科技资助

7、项目(JK2010010)；福建省自然科学基金资助项目(201IJ01339)通信地址：341000江西省赣州市经济技术开发区高校园区35号Address：No35，EconomicandTechnologicalDevelopmentZone，Ganzhou341000，Jiangxi，P．R．China汪宏海等：基于均匀免疫优化算法的最大团问题求解535确定性的算法并不保证最终给出的是最优解。由免疫克隆算