第8章——捕食搜索算法.ppt

1
第八章捕食搜索算法
2
Predatory Search Algorithm
捕食搜索算法的基本思想:
模仿动物的捕食策略(广域与邻域有效结合起来)。
捕食搜索算法(PS)
3
Alexandre Linhares 在1998提出来的一种用于解决组合优化问题的模拟动物捕食行为的空间搜索策略。
把捕食搜索策略分别应用于解决旅行商问题(TSP)和超大规模集成电路设计(VLSI)问题,都取得了较好效果
捕食搜索算法——产生
4
动物捕食时,在没有发现猎物和猎物的迹象时在整个捕食空间沿着一定的方向以很快的速度寻找猎物;一旦发现猎物或者发现有猎物的迹象,它们就放慢步伐,在发现猎物或者有猎物的迹象的附近区域进行集中的区域搜索,以找到更多的猎物。在搜寻一段时间没有找到猎物后,捕食动物将放弃这种集中的区域,而继续在整个捕食空间寻找猎物。动物的这种捕食搜索策略可以概括为以下两个搜索:
捕食搜索算法——基本原理
5
搜索1(全局搜索):在整个搜索空间进行全面搜索,直到发现猎物或者有猎物的迹象而转到搜索2进行局域搜索;
搜索2(局域搜索):在猎物或者有猎物的迹象的附近区域进行集中搜索,直到搜索很多次也没有找到猎物而放弃局域搜索,转到搜索1进行全局搜索。
捕食搜索算法——基本原理
6
动物的捕食策略
7
应用捕食搜索算法寻优时,先在整个搜索空间进行全局搜索,直到找到一个较优解;然后在较优解附近的区域进行集中搜索,直到搜索很多次也没有找到更优解,从而放弃局域搜索;然后再在整个搜索空间进行全局搜索。如此循环,直到找到最优解(或近似最优解)为止。在捕食搜索算法中,使用限制(restriction)来表征较优解的邻域大小。通过限制的调节,实现搜索空间的增大和减小,从而达到探索能力和开发能力的平衡。
捕食搜索算法——基本原理
8
捕食搜索算法——基本原理
9
捕食搜索算法——基本概念
10
捕食搜索算法——基本概念