连续域蚁群算法开题报告

PAGE研究生论文开题报告学科工学专业计算机科学与技术研究方向人工智能与模式识别学号研究生姓名学位级别硕士导师姓名填表日期2016年12月12日PAGE9论文题目连续域蚁群算法的研究及应用本人已查阅过哪些科研资料及调研情况：１、主要参考资料及文献：[1]M.Dorigo,V.Maniezzo,andA.Colorni.Antsystem:Optimizationbyacolonyofcooperatingagents[J].IEEETransactionsonSystems,Man,andCybernetics-partB:Cybernetics,1996,26(1):29–41.[2]M.DorigoandL.Gambardella.Antcolonysystem:Acooperativelearningapproachtothetravellingsalesmanproblem[J].IEEETrans.Evol.Comput.,1997,1(1):53–66.[3]T.StützleandH.Hoos.Max-minantsystem[J].FutureGener.Comput.Syst.,2000,16(9):889–914.[4]B.Bullnheimer,G.Kotsis,andC.Strauss.Anewrank-basedversionoftheantsystem:Acomputationalstudy[J].CentralEur.J.Oper.Res.,1999,7(1):25–38.[5]O.Cordon,I.F.deViana,andF.Herrera.Analysisofthebest-worstantsystemanditsvariantsontheTSP[J].Math.SoftComput.,2002,9(2/3):177–192.[6]M.DorigoandT.Stützle.AntColonyOptimization[M].Cambridge,MA:MITPress,2004.[7]G.Bilchev,andI.C.Parmee.Theantcolonymetaphorforsearchingcontinuousdesignspaces[C].LNCS,1995,933:25-39.[8]N.Monmarché,G.Venturini,,andM.Slimane.OnhowPachycondylaapicalisantssuggestanewsearchalgorithm[J].FutureGenerationComputerSystems,2000,16:937–946.[9]J.Dréo,P.Siarry.Anewantcolonyalgorithmusingtheheterarchicalconceptaimedatoptimizationofmultiminimacontinuousfunctions[J].LNCS,2002,2463:216–221.[10]Guntsch,M.,Middendorf,M..ApopulationbasedapproachforACO[J].LNCS,2002,2279:71–80.[11]S.H.Pourtakdoust,H.Nobahari.Anextensionofantcolonysystemtocontinuousoptimizationproblems[J].LNCS,2004,3172:294–301.[12]Socha,K.,&Dorigo,M.Antcolonyoptimizationforcontinuousdomains[J].EuropeanJournalofOperationalResearch.2006,185,1155–1173.[13]Hu,X.M.,Zhang,J.,&Li,Y.Orthogonalmethodsbasedantcolonysearchforsolvingcontinuousoptimizationproblems[J].JournalofComputerScienceandTechnology.2008,23(1),2–18.[14]F.Franca,G.P.Coelho,F.J.VonZuben,etal.Multivariateantcolonyoptimizationincontinuoussearchspaces[A].InProceedingsoftheGeneticandEvolutionaryComputationConference[C],Atlanta,USA,2008,9–16.[15]G.Leguizam_onandC.Coello.AnalternativeACORalgorithmforcontinuousoptimizationproblems[J].LNCS,2010,6234:48-59.[16]XiaoJing，LiLiangPing.Ahybridantcolonyoptimizationforcontinuousdomains[J].ExpertSystemswithApplications,38:11072-11077.[17]LiaoT,MontesdOMA,AydinD,etal.Anincrementalantcolonyalgorithmwithlocalsearchforcontinuousoptimization[C]//ConferenceonGeneticandEvolutionaryComputation.ACM,2011:182-183.[18]LiaoT,StützleT,OcaMand,etal.Aunifiedantcolonyoptimizationalgorithmforcontinuousoptimization[J].EuropeanJournalofOperationalResearch,2014,234(3):597-609.[19]KumarU,SomanS,Jayadeva.BenchmarkingNLoptandstate-of-the-artalgorithmsforcontinuousglobaloptimizationviaIACORIACORmathContainerLoadingMathjax[J].Swarm&EvolutionaryComputation,2015,27:116-131.[20]高尚，钟娟，莫述军.连续优化问题的蚁群算法研究明.微机发展，2003,13(1):21-22.[21]段海滨,王道波,朱家强.蚁群算法理论及应用研究的进展[J].控制与决策,2004,12.[22]熊伟清，魏平.二进制蚁群进化算法[J].自动化学报，2007,33(3):259-264.[23]段海滨，马冠军，王道波等.一种求解连续空间优化问题的改进蚁群算法[[J].系统仿真学报，2007,19(5):974977.[24]李盼池.李士勇.LIPan-chi.LIShi-yong求解连续空间优化问题的量子蚁群算法[J].控制理论与应用,2008,25(2).[25]马卫，朱庆保.求解函数优化问题的快速连续蚁群算法[[J].电子学报，2008,36(11):21212124[26]周新建，杨卫东，李掌.求解连续函数优化问题的改进蚁群算法及仿真[[J].系统仿真学报，2009,21(6):16851688.[27]刘正龙,杨艳梅.基于交叉变异操作的连续域蚁群算法研究[J].重庆师范大学学报（自然科学版）,2009,2.[28]黄永青,郝国生,钟志水.基于网格划分策略的连续域改进蚁群算法[J].计算机工程与应用,2013,49(9):61:64.２、调研情况：蚁群算法作为一种群智能优化算法，不依赖于待求解问题及其约束条件的可导性，能以较大概率收敛到全局最优解，具有很好的鲁棒性，是智能优化领域目前的研究热点。蚁群算法起源于离散型的网络路径问题，并用该方法求解旅行商问题、指派问题、调度问题等，取得了一系列较好的实验结果。然而，现实世界中有大量的连续性优化问题，将离散型蚁群算法扩展到连续域蚁群优化算法，并提高连续域蚁群算法的收敛速度和精度具有重大的应用价值和现实意义。课题的意义及我国在这方面已进行的工作情况：随着现代科学发展，复杂性、非线性、系统性的最优化问题越来越多。最优化问题是指在给定的条件下，通过对现有方案和参数进行设计，使某个问题呈现出较为满意的答案。许多工程实践问题都可以转化为相对应的优化问题，因此优化问题充满工程领域的方方面面。传统的数值优化方法如共扼梯度法、牛顿法等，对能够建立明确数学模型的几种特定问题，如线性规划、目标规划、动态规划等获得了具体优化方法。但是，这些方法通常只能处理变量规模较小的优化问题，并且要求目标函数具有较多的数学性质如连续、可导等，而且处理非线性信息的能力较弱。因此，寻求更为广泛高效的适合于大规模并行且具有智能特征的优化方法已成为一个引人注目的研究方向。目前，除了常用的遗传算法、模拟退火算法等启发式搜索算法外，近年来兴起的群智能算法也开始展现出了其优越性，提供了一些新的具有竞争力的求解复杂性优化问题的途径。蚁群算法就是其中一种典型的启发式仿生类搜索算法。蚁群算法是由意大利学者Dorigo首次提出的[1]，蚁群算法受自然界中真实蚁群集体行为的启发而提出的一种基于种群的模拟进化算法，属于带有构造性特征的随机搜索算法。该算法利用了蚁群从蚁穴到食源搜索最短路径的过程与著名的旅行商问题(TSP)之间的相似性，通过人工蚂蚁搜索食物的过程来求解TSP问题。并用该方法求解旅行商问题、指派问题、调度问题等，取得了一系列较好的实验结果。众多的研究己经证明蚁群算法具有很强的发现较好解的能力，这是因为该算法不仅利用了正反馈原理，在一定程度上可以加快进化过程，而且是一种本质并行的算法，不同个体之间不断进行信息的交流和传递，从而能够相互协作，有利于发现较好解。蚁群优化自问世以来，获得了广泛的关注，大量的学者对蚁群算法进行了改进[2-5]。由于最初的蚁群算法起源于离散型的网络路径问题，每个蚂蚁决策仅限于离散的空间，因此蚁群算法在处理连续空间的优化问题还具有一定的局限性，必须对算法中许多实施细节加以修正。国内有大量的学者对连续域蚁群算法进行了研究。2003年，高尚等[20]提出了一种基于网格划分模式的连续域蚁群算法，将搜索空间划分为网格似的小区域，蚂蚁在不同区域间大范围转移或在区间内小范围搜索，即表现为蚂蚁的全局搜索和局部搜索并行的寻优过程。与网格划分法的不同处在于该算法利用了网格中每一点的信息，而网格划分法只利用了最小值的信息。2007年，段海滨等[21]首先采用网格划分策略将连续空间离散化，然后通过评价函数确定蚂蚁的转移概率同时引入了相遇搜索策略，在求解连续空间优化问题时，该算法有着较快的收敛速度。同年，熊伟清等[22]提出的连续域蚁群算法是基于二进制编码的，该算法将决策空间中的每个候选解采用类似于遗传算法中的二进制方式进行编码，寻优的过程即是蚂蚁在二进制地图上进行搜索的过程，这样就方便的将本质上离散的蚁群算法应用到了连续域的优化问题中。2008年，李盼池等[24]提出一种求解连续优化的量子蚁群算法，将蚁群算法中的每只蚂蚁携带一组量子比特，根据信息素强度和可见度构造概率选择蚂蚁的前进目标，采用量子旋转门更新蚂蚁携带的量子比特完成蚂蚁的移动，采用量子非门实现蚂蚁所在位置的变异增加位置的多样性。同年，马卫等[25]提出了一种新的由侦察蚁和觅食蚁两种蚂蚁协作搜索的函数优化连续蚁群算法，在搜索策略中引入混沌序列算法确定侦察蚁的初始位置，然后由其进行全局大视域快速搜索，再由觅食蚁在侦察蚁发现的全局较好解附近进行局部搜索，加快了收敛速度，提高了求解精度。2009年，周新建等[26]提出的一种用于连续函数优化的改进蚁群算法中，采用全局信息素和局部信息素相结合的方法来进行信息素的动态更新，为了避免算法过早的出现停滞现象，算法中设置了信息素浓度的上下界限值。2013年，黄永青等[28]提出基于网格划分策略的连续域改进蚁群算法，使用一种特殊的信息素更新策略，使得更新信息素时不需要使用解的具体目标函数值，从而降低了目标函数值差异化给算法性能带来的不利影响，并且网格点上的信息素可以直接作为构建解过程中的转移概率。国外的研究动态及发展趋势：国外对蚁群算法等智能算法已有较深入的研究，提出了许多改进的算法模型，也出现了一些将几种智能算法相融合的模型。在1995年Bilchev和Parmee首次提出一个连续域的蚁群优化算法CACO[7].CACO在搜索空间给定的一个点处作为初始化巢，然后生成随机向量对应蚂蚁行走的方向，每个蚂蚁沿着这些方向追求更好的解。如果一只蚂蚁在这样的追求是成功的，则对应的方向向量就会更新。这个算法将遗传算法和蚁群算法融合在一起。在2000年Monmarche提出API[8]，这个方法中，虽然每只蚂蚁从同一个巢开始行走，但是每只蚂蚁作为一个个体独立地搜索解，然后蚂蚁的巢周期的进行移动。在2002年Dreo和Siarry创造了CIAC[9]，这个方法将一些污点放在对蚂蚁有吸引力的地方，同时还将蚂蚁之间的方向信息做为交流来增强蚂蚁的搜索能力。在2004年Pourtakdoust提出另一个蚁群系统方法，即CACS[11]，将离散的信息素概率分布换成连续的高斯概率密度函数，其中值和标准差由蚂蚁动态的调整。在2006年Socha受PB-ACO和CACS的启发，提出ACOR[12]，将蚂蚁搜索的至今最优解作为信息素保存在档案，用高斯核函数作为信息素概率分布函数，并通过更新档案解来更新信息素。在2008年Hu提出COAC[13]，将搜索空间离散化，用正交设计方法，蚂蚁在他们自己的可行域里可以更快和高效地搜索，应用自适应的区域半径方法，减少了陷入局部最优的概率和增强了全局搜索能力和精度。同年，Franca提出MACACO[14]使用多元的高斯密度函数来搜索空间。2010年Leguizamon提出DACOR[15]，是ACOR的一个变种，利用控制参数q增强了搜索的多样性，更适合搜索空间大的连续域优化问题。2011年XiaoJing提出了一种混合的连续域蚁群优化算法HACO[16]，使用了与ACOR相同的思想，并结合了差分进化和基于种群增长式学习动态产生高斯概率密度函数。为了缓解传统基于种群的蚁群算法的较弱的搜索能力，利用差分进化算子来计算高斯中值。与其它算法相比，该算法一般需要较长的搜索时间，而且如果算法参数选得不合适，该算法容易出现搜索的停滞现象(陷入局部最优)，即搜索到一定程度后，所有的个体所发现的解完全一致，不能对解空间进一步进行搜索，不利于发现更好的解。所以连续域蚁群算法还需要探索与研究。开题报告立题的依据，选题必须对国民经济或在学术上有一定意义。在科学工程实践中，很多问题往往表达为一个连续性最优化问题，当问题的规模较大且复杂(如不可微、非线性、多极值等)时，就迫切需要有效的优化算法来进行求解。而传统的数值优化方法，对初始点的选取和目标函数的性质依赖比较大。蚁群算法作为一种群智能优化算法，不依赖于待求解问题及其约束条件的可导性，能以较大概率收敛到全局最优解，具有很好的鲁棒性，是智能优化领域目前的研究热点。蚁群算法起源于离散型的网络路径问题，并用该方法求解旅行商问题、指派问题、调度问题等，取得了一系列较好的实验结果。然而，现实世界中有大量的连续性优化问题，将离散型蚁群算法扩展到连续域蚁群优化算法，并提高连续域蚁群算法的收敛速度和精度具有重大的应用价值和现实意义。课题进行的途径，步骤的设想。蚁群优化是模拟蚁群在觅食过程中能获得巢穴到食物源间最短路径的机制而提出的启发式方法。蚁群算法的框架为三部分，分别是：初始化，解的构建，信息素更新。初始化阶段，一般是对参数值，迭代次数，信息素的初始化。解的构建阶段，是问题的关键点，选择蚂蚁下一步的取值的策略有很多种，对应有很多种蚁群优化模型，本课题采取同ACOR算法[12]一样的模型，将解和对应的解的函数值按照解的质量从高到低的排列在解档案中，并赋给每一个解与解质量成比例的相应的权值，权值的公式如下：wi=利用高斯核函数来取样，高斯核函数公式为：Gjx=i∈{1,2,…,k},j∈{1,2,…,n},k为解个数，n为问题维数。信息素更新阶段，要明确算法中作为信息素的这个变量，并用什么方式进行更新，显然，本课题是用解档案中的解作为信息素的，那么信息素的更新，体现在蚂蚁产生的新的较好的解加入解档案，同样多的最差的解从解档案中移除。蚁群算法有其固有的缺点，归纳如下:1)易陷入局部最优解。随着重复执行算法，当一条局部最优的路径积累了足够多的信息素，并且其余路径上的信息素含量低于该条路径时，将会出现停滞现象，所有的蚂蚁都聚集到这条局部相对最优的路径上，使得算法陷入局部最优解。2)收敛速度低。蚁群中单个蚂蚁的运动是随机的，当群体规模较大时，蚂蚁群体受信息素所驱动，在大量杂乱的路径中找到一条相对较优的路径需要花费很多时间。针对以上蚁群算法的2大缺点，将阅读大量国内外相关的文献，尝试将蚁群算法与其他智能优化算法相结合，来改进连续域蚁群算法。其他的智能算法有遗传算法，粒子群算法，人工蜂群算法，鱼群算法，教与学算法等。了解了这些算法的基本结构和优点。因为教与学算法中的邻域搜索策略，导致教与学算法有比较强的搜索能力，尝试将教与学算法中的这个策略引入蚁群算法，由此达到改进的目的，并将改进的连续域蚁群算法进行应用。在实际生产生活中，遇到的大多数问题都带有约束条件，这类广泛存在的问题的求解要比无约束优化问题的求解困难和复杂得多。在求解带约束优化问题时，本课题的基本思路是:首先对约束条件进行处理，把约束优化问题转化为无约束优化问题，然后利用改进的连续域蚁群算法，通过两者之间的有效结合，从而求得约束优化问题的全局最优解。需使用的仪器，一般应以选择本院现有仪器及设备为主，估计需要经费多少？Windows版本：Window7旗舰版硬件：处理器酷睿i5，CPU2.6GHz,内存4G软件：Matlab2015a课题进行时可能出现的问题及准备采取的应变措施。在本课题研究过程当中，找到一个合适的领域搜索是关键，这是一个难点，要克服这方面的困难主要依赖于阅读大量的文献和导师的指导，编程并在相应的测试函数上验证其实效。很有可能找到的方法在应用中效果不好，碰到这样的情况，可以请教导师和同学，查阅资料对改进后的模型进行修饰。课题与教研室及导师的科研工作有无关系，与已毕业的研究生课题联系：蚁群算法是人工智能