最近发展起来的新算法

最近发展起来的新算法第一页，共五十一页，编辑于2023年，星期六2第八章最近发展起来的新算法一.我们的工作：群落选址算法(CLA)二.捕食搜索算法(PS)三.其他新算法第二页，共五十一页，编辑于2023年，星期六3一.我们的工作：群落选址算法

ColonyLocationAlgorithm(CLA)CLA的产生：汪定伟2004WangDingwei.Colonylocationalgorithmforassignmentproblems[J],JournalofControlTheoryandApplications,2004,2(2):111-116.

WangDingwei.Colonylocationalgorithmforcombinatorialoptimization[A],Proc.IEEE.Conf.onSystems,Man&Cybernetics[C],PiscatawayNJ:IEEEServiceCenter,2004,1903-1909.

基本思想模拟植物群落形成机制－－土地含有的适于植物生长营养成分；不同物种间对生存资源的竞争；人工干预手段——施肥策略。第三页，共五十一页，编辑于2023年，星期六4CLA养分函数Nij(t):在

t时刻，土地j对群落i的养分。加上时间t，是因为施肥可以改变肥力。第四页，共五十一页，编辑于2023年，星期六5CLA生长率与衰亡率生长率：

r是平均生长率，是所有土地对i的平均肥力（行均值）第五页，共五十一页，编辑于2023年，星期六6衰亡率：是土地j对所有群落的肥力的均值。（列均值）CLA第六页，共五十一页，编辑于2023年，星期六7CLA群落比例与归一化设xij(t)是群落i

在土地j

上的比例；生长过程带来比例的和不是1。行、列归一化，反复进行。第七页，共五十一页，编辑于2023年，星期六8生长过程CLA第八页，共五十一页，编辑于2023年，星期六9CLA解的构成与评估xij(t)不是解。以xij(t)为概率，在每块土地上产生一个群落，问题是要保证一个群落不能同时在两块土地上—解的合法性。其实很简单，按随机顺序，在剩余群落中选。第九页，共五十一页，编辑于2023年，星期六10CLA施肥过程若S(k*)是最好解；或者第十页，共五十一页，编辑于2023年，星期六11CLA解的信息熵的计算解的信息熵：第十一页，共五十一页，编辑于2023年，星期六12CLA停止判据停止准则的计算：第十二页，共五十一页，编辑于2023年，星期六13CLA流程Step1:输入数据和参数Step2:产生初始群落比例Step3:停止准则判断Step4:生长和衰亡过程Step5:解的构成与评估Step6:选取最优解Step7:施肥Step8:结果输出第十三页，共五十一页，编辑于2023年，星期六14指派问题的计算结果第十四页，共五十一页，编辑于2023年，星期六15第十五页，共五十一页，编辑于2023年，星期六16第十六页，共五十一页，编辑于2023年，星期六17CLATSP的计算结果全国33城市的TSP计算结果好于文献的结果，但TSP.Lab测试题的计算结果不好。工作还需要继续进行。第十七页，共五十一页，编辑于2023年，星期六18CLAQAP的计算结果自己编的题目计算结果不错但对大规模问题计算效果不好，还需要做很多工作。包括养分函数的设置方法都还是问题。第十八页，共五十一页，编辑于2023年，星期六19PredatorySearchAlgorithm捕食搜索算法的基本思想：模仿动物的捕食策略（广域与邻域有效结合起来）。二.捕食搜索算法（PS）第十九页，共五十一页，编辑于2023年，星期六20AlexandreLinhares在1998提出来的一种用于解决组合优化问题的模拟动物捕食行为的空间搜索策略。把捕食搜索策略分别应用于解决旅行商问题（TSP）和超大规模集成电路设计（VLSI）问题，都取得了较好效果

捕食搜索算法——产生第二十页，共五十一页，编辑于2023年，星期六21

动物捕食时，在没有发现猎物和猎物的迹象时在整个捕食空间沿着一定的方向以很快的速度寻找猎物；一旦发现猎物或者发现有猎物的迹象，它们就放慢步伐，在发现猎物或者有猎物的迹象的附近区域进行集中的区域搜索，以找到更多的猎物。在搜寻一段时间没有找到猎物后，捕食动物将放弃这种集中的区域，而继续在整个捕食空间寻找猎物。动物的这种捕食搜索策略可以概括为以下两个搜索：

捕食搜索算法——基本原理第二十一页，共五十一页，编辑于2023年，星期六22搜索1（全局搜索）：在整个搜索空间进行全面搜索，直到发现猎物或者有猎物的迹象而转到搜索2进行局域搜索；搜索2（局域搜索）：在猎物或者有猎物的迹象的附近区域进行集中搜索，直到搜索很多次也没有找到猎物而放弃局域搜索，转到搜索1进行全局搜索。

捕食搜索算法——基本原理第二十二页，共五十一页，编辑于2023年，星期六23动物的捕食策略第二十三页，共五十一页，编辑于2023年，星期六24应用捕食搜索算法寻优时，先在整个搜索空间进行全局搜索，直到找到一个较优解；然后在较优解附近的区域进行集中搜索，直到搜索很多次也没有找到更优解，从而放弃局域搜索；然后再在整个搜索空间进行全局搜索。如此循环，直到找到最优解（或近似最优解）为止。在捕食搜索算法中，使用限制（restriction）来表征较优解的邻域大小。通过限制的调节，实现搜索空间的增大和减小，从而达到探索能力和开发能力的平衡。

捕食搜索算法——基本原理第二十四页，共五十一页，编辑于2023年，星期六25捕食搜索算法——基本原理第二十五页，共五十一页，编辑于2023年，星期六26捕食搜索算法——基本概念第二十六页，共五十一页，编辑于2023年，星期六27捕食搜索算法——基本概念第二十七页，共五十一页，编辑于2023年，星期六28捕食搜索算法——基本概念第二十八页，共五十一页，编辑于2023年，星期六29捕食搜索算法——基本概念解空间示意图第二十九页，共五十一页，编辑于2023年，星期六30捕食搜索算法——基本概念第三十页，共五十一页，编辑于2023年，星期六31捕食搜索算法——基本概念第三十一页，共五十一页，编辑于2023年，星期六32捕食搜索算法——基本概念第三十二页，共五十一页，编辑于2023年，星期六33捕食搜索算法——算法步骤第三十三页，共五十一页，编辑于2023年，星期六34捕食搜索算法——算法步骤第三十四页，共五十一页，编辑于2023年，星期六35捕食搜索算法——限制的计算第三十五页，共五十一页，编辑于2023年，星期六36捕食搜索算法——参数的设置第三十六页，共五十一页，编辑于2023年，星期六37捕食搜索算法——参数的设置第三十七页，共五十一页，编辑于2023年，星期六38捕食搜索算法——计算举例第三十八页，共五十一页，编辑于2023年，星期六39捕食搜索算法——计算举例第三十九页，共五十一页，编辑于2023年，星期六40捕食搜索算法——计算举例第四十页，共五十一页，编辑于2023年，星期六41捕食搜索算法——计算举例第四十一页，共五十一页，编辑于2023年，星期六42捕食搜索算法——计算举例第四十二页，共五十一页，编辑于2023年，星期六43捕食搜索算法——计算举例第四十三页，共五十一页，编辑于2023年，星期六44捕食搜索算法——计算举例第四十四页，共五十一页，编辑于2023年，星期六45捕食搜索算法——计算举例第四十五页，共五十一页，编辑于2023年，星期六46捕食搜索算法——计算举例第四十六页，共五十一页，编辑于2023年，星期六47捕食搜索算法——计算举例第四十七页，共