第8章——最近发展起来的新算法-2008概要.ppt

1、1,第八章最近发展起来的新算法,2,第八章最近发展起来的新算法,一.我们的工作：群落选址算法(CLA)二.捕食搜索算法(PS)三.其他新算法,3,一.我们的工作：群落选址算法ColonyLocationAlgorithm(CLA),CLA的产生：汪定伟2004WangDingwei.ColonylocationalgorithmforassignmentproblemsJ,JournalofControlTheoryandApplications,2004,2(2):111-116.WangDingwei.Colonylocationalgorithmforcombinatorialoptim

2、izationA,Proc.IEEE.Conf.onSystems,Man&CyberneticsC,PiscatawayNJ:IEEEServiceCenter,2004,1903-1909.基本思想模拟植物群落形成机制土地含有的适于植物生长营养成分；不同物种间对生存资源的竞争；人工干预手段施肥策略。,4,CLA,养分函数Nij(t):在t时刻，土地j对群落i的养分。加上时间t，是因为施肥可以改变肥力。,5,CLA,生长率与衰亡率生长率：r是平均生长率，是所有土地对i的平均肥力（行均值）,6,衰亡率：是土地j对所有群落的肥力的均值。（列均值）,CLA,7,CLA,群落比例与归一化设xij(t

3、)是群落i在土地j上的比例；生长过程带来比例的和不是1。行、列归一化，反复进行。,8,生长过程,CLA,9,CLA,解的构成与评估xij(t)不是解。以xij(t)为概率，在每块土地上产生一个群落，问题是要保证一个群落不能同时在两块土地上解的合法性。其实很简单，按随机顺序，在剩余群落中选。,10,CLA,施肥过程若S(k*)是最好解；,或者,11,CLA,解的信息熵的计算解的信息熵：,12,CLA,停止判据停止准则的计算：,13,CLA流程,Step1:输入数据和参数Step2:产生初始群落比例Step3:停止准则判断Step4:生长和衰亡过程Step5:解的构成与评估Step6:选取最优解S

4、tep7:施肥Step8:结果输出,14,指派问题的计算结果,15,16,17,CLA,TSP的计算结果全国33城市的TSP计算结果好于文献的结果，但TSP.Lab测试题的计算结果不好。工作还需要继续进行。,18,CLA,QAP的计算结果自己编的题目计算结果不错但对大规模问题计算效果不好，还需要做很多工作。包括养分函数的设置方法都还是问题。,19,PredatorySearchAlgorithm捕食搜索算法的基本思想：模仿动物的捕食策略（广域与邻域有效结合起来）。,二.捕食搜索算法（PS）,20,AlexandreLinhares在1998提出来的一种用于解决组合优化问题的模拟动物捕食行为的空

5、间搜索策略。把捕食搜索策略分别应用于解决旅行商问题（TSP）和超大规模集成电路设计（VLSI）问题，都取得了较好效果,捕食搜索算法产生,21,动物捕食时，在没有发现猎物和猎物的迹象时在整个捕食空间沿着一定的方向以很快的速度寻找猎物；一旦发现猎物或者发现有猎物的迹象，它们就放慢步伐，在发现猎物或者有猎物的迹象的附近区域进行集中的区域搜索，以找到更多的猎物。在搜寻一段时间没有找到猎物后，捕食动物将放弃这种集中的区域，而继续在整个捕食空间寻找猎物。动物的这种捕食搜索策略可以概括为以下两个搜索：,捕食搜索算法基本原理,22,搜索1（全局搜索）：在整个搜索空间进行全面搜索，直到发现猎物或者有猎物的迹象而

6、转到搜索2进行局域搜索；搜索2（局域搜索）：在猎物或者有猎物的迹象的附近区域进行集中搜索，直到搜索很多次也没有找到猎物而放弃局域搜索，转到搜索1进行全局搜索。,捕食搜索算法基本原理,23,动物的捕食策略,24,应用捕食搜索算法寻优时，先在整个搜索空间进行全局搜索，直到找到一个较优解；然后在较优解附近的区域进行集中搜索，直到搜索很多次也没有找到更优解，从而放弃局域搜索；然后再在整个搜索空间进行全局搜索。如此循环，直到找到最优解（或近似最优解）为止。在捕食搜索算法中，使用限制（restriction）来表征较优解的邻域大小。通过限制的调节，实现搜索空间的增大和减小，从而达到探索能力和开发能力的平衡

7、。,捕食搜索算法基本原理,25,捕食搜索算法基本原理,26,捕食搜索算法基本概念,27,捕食搜索算法基本概念,28,捕食搜索算法基本概念,29,捕食搜索算法基本概念,解空间示意图,30,捕食搜索算法基本概念,31,捕食搜索算法基本概念,32,捕食搜索算法基本概念,33,捕食搜索算法算法步骤,34,捕食搜索算法算法步骤,35,捕食搜索算法限制的计算,36,捕食搜索算法参数的设置,37,捕食搜索算法参数的设置,38,捕食搜索算法计算举例,39,捕食搜索算法计算举例,40,捕食搜索算法计算举例,41,捕食搜索算法计算举例,42,捕食搜索算法计算举例,43,捕食搜索算法计算举例,44,捕食搜索算法计算