局部搜索定义为候选解集合优秀PPT.ppt

《局部搜索定义为候选解集合优秀PPT.ppt》由会员分享，可在线阅读，更多相关《局部搜索定义为候选解集合优秀PPT.ppt（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、中国科学院软件研究所中国科学院软件研究所Institute of Software,Chinese Academy of Sciences格局检测：普适的格局检测：普适的局部搜寻策略局部搜寻策略蔡少伟蔡少伟中国科学院软件探讨所中国科学院软件探讨所中国科学院软件研究所中国科学院软件研究所Institute of Software,Chinese Academy of Sciences 组合优化组合优化组合优化问题组合优化问题优化问题可以分为两类：一类是连续变量的问题，另一类是离散变量优化问题可以分为两类：一类是连续变量的问题，另一类是离散变量的问题，后者称为组合优化问题。的问题，后者称为组合优化

2、问题。组合优化问题的任务：从一个有限或可数无限集里，找寻一个使得目组合优化问题的任务：从一个有限或可数无限集里，找寻一个使得目标函数最优的对象标函数最优的对象典型地包括：一组赋值，一个集合，一个排列。典型地包括：一组赋值，一个集合，一个排列。组合优化问题随处可见，具有很强的工程代表性应用。组合优化问题随处可见，具有很强的工程代表性应用。很多组合优化问题都是很多组合优化问题都是NP难的：最大可满足性（难的：最大可满足性（MaxSAT)问题，最大问题，最大团问题，最小顶点覆盖问题，旅行商问题。团问题，最小顶点覆盖问题，旅行商问题。中国科学院软件研究所中国科学院软件研究所Institute of S

3、oftware,Chinese Academy of Sciences 组合优化组合优化组合优化问题组合优化问题优化问题可以分为两类：一类是连续变量的问题，另一类是离散变量优化问题可以分为两类：一类是连续变量的问题，另一类是离散变量的问题，后者称为组合优化问题。的问题，后者称为组合优化问题。组合优化问题的任务：从一个有限或可数无限集里，找寻一个使得目组合优化问题的任务：从一个有限或可数无限集里，找寻一个使得目标函数最优的对象标函数最优的对象典型地包括：一组赋值，一个集合，一个排列。典型地包括：一组赋值，一个集合，一个排列。组合优化问题随处可见，具有很强的工程代表性应用。组合优化问题随处可见，具

4、有很强的工程代表性应用。很多组合优化问题都是很多组合优化问题都是NP难的：最大可满足性（难的：最大可满足性（MaxSAT)问题，最大问题，最大团问题，最小顶点覆盖问题，旅行商问题。团问题，最小顶点覆盖问题，旅行商问题。求解求解NP难组合优化问题难组合优化问题分支限界：完备算法（保证解的最优性），回溯搜寻，遍历解空间分支限界：完备算法（保证解的最优性），回溯搜寻，遍历解空间启发式搜寻（包括局部搜寻，演化算法等）：不完备算法，迭代改进，启发式搜寻（包括局部搜寻，演化算法等）：不完备算法，迭代改进，采样解空间采样解空间中国科学院软件研究所中国科学院软件研究所Institute of Software

5、,Chinese Academy of Sciences局部搜寻局部搜寻简洁地说，局部搜寻是：简洁地说，局部搜寻是：先产生一个（或一群）完整的候选解，然后进行迭代改进，每一步只先产生一个（或一群）完整的候选解，然后进行迭代改进，每一步只修改解的某个局部（比如一个基本单元），直到得到一个令人满足的修改解的某个局部（比如一个基本单元），直到得到一个令人满足的解或者达到某个资源限制（一般是时间限制）。解或者达到某个资源限制（一般是时间限制）。中国科学院软件研究所中国科学院软件研究所Institute of Software,Chinese Academy of Sciences局部搜寻局部搜寻简洁地

6、说，局部搜寻是：简洁地说，局部搜寻是：先产生一个（或一群）完整的候选解，然后进行迭代改进，每一步只先产生一个（或一群）完整的候选解，然后进行迭代改进，每一步只修改解的某个局部（比如一个基本单元），直到得到一个令人满足的修改解的某个局部（比如一个基本单元），直到得到一个令人满足的解或者达到某个资源限制（一般是时间限制）。解或者达到某个资源限制（一般是时间限制）。形式化一点说，局部搜寻定义为：形式化一点说，局部搜寻定义为：候选解集合（也称搜寻空间）候选解集合（也称搜寻空间）S；目标函数目标函数 f：S-R(实数集实数集)；初始候选解集合初始候选解集合 I；邻域关系邻域关系 N:S-2S，对于每个候

7、选解，对于每个候选解s，N(s)=s S|N(s,s)S;（一般是基于候选解的海明距离，最常见的是（一般是基于候选解的海明距离，最常见的是1-海明距离邻域）海明距离邻域）跳转函数（跳转函数（Step function）：定义了如何从当前候选解跳转到它的一）：定义了如何从当前候选解跳转到它的一个邻居候选解个邻居候选解中国科学院软件研究所中国科学院软件研究所Institute of Software,Chinese Academy of Sciences局部搜寻局部搜寻局部搜寻的优点：局部搜寻的优点：简洁；简洁；通用；通用；简洁实现；简洁实现；可扩展性强；可扩展性强；很多很多NP难问题在求解性能上

8、最好的算法都是基于局部搜寻难问题在求解性能上最好的算法都是基于局部搜寻什么时候运用局部搜寻什么时候运用局部搜寻组合爆炸：对于组合爆炸：对于NP难问题，解空间是问题规模的指数级别难问题，解空间是问题规模的指数级别时间限制短，或者时间资源特别重要时间限制短，或者时间资源特别重要关于问题的领域学问太少关于问题的领域学问太少接受近似解接受近似解中国科学院软件研究所中国科学院软件研究所Institute of Software,Chinese Academy of Sciences 一个局部搜寻的例子一个局部搜寻的例子一个例子：最大可满足性问题（一个例子：最大可满足性问题（MaxSAT）变元：x1,x2

9、,x3,xn文字：变元或者其否定形式 x1,x1,子句：文字的析取 x1/x2,x1/x2/x4,.CNF公式：子句的合取，可看为一个子句集合MaxSAT（优化问题)：给出一组（布尔）赋值，满足最多子句。SAT（判定问题）：是否存在一组（布尔）赋值，满足全部子句。中国科学院软件研究所中国科学院软件研究所Institute of Software,Chinese Academy of Sciences 一个局部搜寻的例子一个局部搜寻的例子一个例子：最大可满足性问题（一个例子：最大可满足性问题（MaxSAT）用局部搜寻求解以下用局部搜寻求解以下MaxSAT（或（或SAT）实例）实例 x1/x2,x

10、1/x2,x2/x3,x1/x2/x3变元：x1,x2,x3,xn文字：变元或者其否定形式 x1,x1,子句：文字的析取 x1/x2,x1/x2/x4,.CNF公式：子句的合取，可看为一个子句集合MaxSAT（优化问题)：给出一组（布尔）赋值，满足最多子句。SAT（判定问题）：是否存在一组（布尔）赋值，满足全部子句。赋值不满足的子句初始000 x1/x2,x2/x3Step 1001x1/x2Step 2101x1/x2/x3Step 3110无（找到最优解）中国科学院软件研究所中国科学院软件研究所Institute of Software,Chinese Academy of Science

11、s局部搜寻的循环问题局部搜寻的循环问题局部搜寻的循环问题局部搜寻的循环问题重复访问（近期刚访问过的）候选解重复访问（近期刚访问过的）候选解花费很长时间在解空间的某个区域（比如某个局部最优旁边的区域）花费很长时间在解空间的某个区域（比如某个局部最优旁边的区域）搜寻搜寻导致：简洁陷入局部最优，花费太多时间在做无效搜寻。导致：简洁陷入局部最优，花费太多时间在做无效搜寻。很多局部搜寻的文献其实都是围绕如何解决这个问题很多局部搜寻的文献其实都是围绕如何解决这个问题循环问题不行能完全避开循环问题不行能完全避开这是由局部搜寻的无记忆性确定的这是由局部搜寻的无记忆性确定的不行能增加一个记忆机制来记住访问过的候

12、选解，空间时间要求都太不行能增加一个记忆机制来记住访问过的候选解，空间时间要求都太浩大浩大中国科学院软件研究所中国科学院软件研究所Institute of Software,Chinese Academy of Sciences局部搜寻的循环问题局部搜寻的循环问题局部搜寻的循环问题局部搜寻的循环问题重复访问（近期刚访问过的）候选解重复访问（近期刚访问过的）候选解花费很长时间在解空间的某个区域（比如某个局部最优旁边的区域）花费很长时间在解空间的某个区域（比如某个局部最优旁边的区域）搜寻搜寻导致：简洁陷入局部最优，花费太多时间在做无效搜寻。导致：简洁陷入局部最优，花费太多时间在做无效搜寻。很多局部

13、搜寻的文献其实都是围绕如何解决这个问题很多局部搜寻的文献其实都是围绕如何解决这个问题循环问题不行能完全避开循环问题不行能完全避开这是由局部搜寻的无记忆性确定的这是由局部搜寻的无记忆性确定的不行能增加一个记忆机制来记住访问过的候选解，空间时间要求都太不行能增加一个记忆机制来记住访问过的候选解，空间时间要求都太浩大浩大已有的（通用）方法已有的（通用）方法随机游动随机游动重启重启以确定条件（如概率）允许非改进步以确定条件（如概率）允许非改进步Tabu策略：禁止反转近期内（策略：禁止反转近期内（t步内）所做的改动步内）所做的改动加权方法变更能量地图加权方法变更能量地图中国科学院软件研究所中国科学院软件

14、研究所Institute of Software,Chinese Academy of Sciences格局检测格局检测相关概念：相关概念：解的基本单元一般称为解部件解的基本单元一般称为解部件(solution component)：在最大团问题：在最大团问题中是一个点，在可满足性问题中是一个变元。中是一个点，在可满足性问题中是一个变元。解部件的赋值：例如，点解部件的赋值：例如，点 选中，没选中选中，没选中,变元变元 true,false中国科学院软件研究所中国科学院软件研究所Institute of Software,Chinese Academy of Sciences格局检测格局检测相关

15、概念：相关概念：解的基本单元一般称为解部件解的基本单元一般称为解部件(solution component)：在最大团问题：在最大团问题中是一个点，在可满足性问题中是一个变元。中是一个点，在可满足性问题中是一个变元。解部件的赋值：例如，点解部件的赋值：例如，点 选中，没选中选中，没选中,变元变元 true,false格局检测（格局检测（configuration checking，简称，简称CC）的直观理解：）的直观理解：无法记忆整个解，但可以记忆每个解部件的环境及其变更。无法记忆整个解，但可以记忆每个解部件的环境及其变更。通过检测解部件的环境，削减解的局部结构上的循环，以此削减整个通过检测解

16、部件的环境，削减解的局部结构上的循环，以此削减整个搜寻的循环问题。搜寻的循环问题。对于一个解部件对于一个解部件x，假如从上次，假如从上次x变更赋值之后，变更赋值之后，x的环境没有变更过，的环境没有变更过，那么禁止那么禁止x变回原来的赋值。变回原来的赋值。格局检测是一种从空间（或结构）上考虑的禁忌策略格局检测是一种从空间（或结构）上考虑的禁忌策略中国科学院软件研究所中国科学院软件研究所Institute of Software,Chinese Academy of Sciences格局检测格局检测解部件的格局解部件的格局u我们把解部件的环境信息称为它的格局，可以有不同的定义u最常见的是：一个解部

17、件的格局，是一个由它的邻居解部件的赋值构成的向量。中国科学院软件研究所中国科学院软件研究所Institute of Software,Chinese Academy of Sciences格局检测格局检测解部件的格局解部件的格局我们把解部件的环境信息称为它的格局，可以有不同的定义我们把解部件的环境信息称为它的格局，可以有不同的定义最常见的是：最常见的是：一个例子：一个例子：CC for SAT邻居变量：假如两个变量出现在同一个子句中，称他们是邻居。邻居变量：假如两个变量出现在同一个子句中，称他们是邻居。变量变量x的格局：一个由的格局：一个由x的全部邻居变量的赋值构成的向量。的全部邻居变量的赋值

18、构成的向量。一个解部件的格局，是一个由它的邻居解部件的赋值构成的向量。中国科学院软件研究所中国科学院软件研究所Institute of Software,Chinese Academy of Sciences格局检测用于格局检测用于SATSAT问题问题CC for SAT：对于一个变量v，假如从上次v变更赋值之后，v的格局没有变更过，那么禁止v变回原来的赋值。中国科学院软件研究所中国科学院软件研究所Institute of Software,Chinese Academy of Sciences顶点覆盖问题顶点覆盖问题顶点覆盖：对于一个无向图，一个顶点覆盖是一个顶点子集，使得每条边都至少有一个

19、点属于该集合。最小顶点覆盖问题：给定一个无向图，找出最小的顶点覆盖。中国科学院软件研究所中国科学院软件研究所Institute of Software,Chinese Academy of Sciences格局检测用于顶点覆盖问题格局检测用于顶点覆盖问题最小顶点覆盖问题可以通过迭代解决其判定问题来求解当找到一个规模为k的顶点覆盖时，接着找寻一个规模为k-1的顶点覆盖。算法核心：对一个整数k，找一个规模为k的顶点集合覆盖全部的边。初始的时候，构造一个规模为k的顶点集合（候选解）。局部搜寻的每一步交换集合中的一点和集合外的一点。中国科学院软件研究所中国科学院软件研究所Institute of So

20、ftware,Chinese Academy of Sciences格局检测用于顶点覆盖问题格局检测用于顶点覆盖问题最小顶点覆盖问题可以通过迭代解决其判定问题来求解当找到一个规模为k的顶点覆盖时，接着找寻一个规模为k-1的顶点覆盖。算法核心：对一个整数k，找一个规模为k的顶点集合覆盖全部的边。初始的时候，构造一个规模为k的顶点集合（候选解）。局部搜寻的每一步交换集合中的一点和集合外的一点。格局检测：对一个顶点v，假如从上次v被移出候选解之后，v的格局没有变更过，那么禁止把v重新加入候选解。中国科学院软件研究所中国科学院软件研究所Institute of Software,Chinese Aca

21、demy of Sciences格局检测格局检测更一般的说，格局检测（更一般的说，格局检测（CC）是一种思想）是一种思想不同的格局定义不同的格局定义不同的不同的CC策略。策略。比如对比如对SAT问题，变量的格局还可以定义为：变量的关联子句的状态问题，变量的格局还可以定义为：变量的关联子句的状态构成的向量。构成的向量。不同的检测方法不同的检测方法不同的不同的CC策略。策略。比如量化比如量化CC，以格局变更的幅度作为选择解部件的一个优先序法则。，以格局变更的幅度作为选择解部件的一个优先序法则。不同的格局定义，禁忌强度不同。不同的格局定义，禁忌强度不同。可以设计多层次的可以设计多层次的CC策略。策略

22、。中国科学院软件研究所中国科学院软件研究所Institute of Software,Chinese Academy of Sciences格局检测格局检测格局检测已经被运用于多个组合优化问题格局检测已经被运用于多个组合优化问题SAT，MaxSAT，顶点覆盖，最大团，图着色，集合覆盖，支配集，顶点覆盖，最大团，图着色，集合覆盖，支配集，刻度划分问题等等。刻度划分问题等等。从从2011年提出到目前已经产生年提出到目前已经产生20几篇论文（包括其他团队）。几篇论文（包括其他团队）。格局检测对格局检测对SAT领域产生极大影响领域产生极大影响2013年年SAT竞赛随机组接近竞赛随机组接近40%的的so

23、lver运用该技术；运用该技术；最近三年，共有最近三年，共有6个获奖个获奖SAT solver运用该技术，包括运用该技术，包括2个第一，个第一，2个其个其次，次，2个第三；个第三；最近两年，非完备算法组获奖的最近两年，非完备算法组获奖的MaxSAT solver大都接受了格局检测。大都接受了格局检测。AAAI 2013年关于年关于SAT方面的方面的Tutorial Forum评价评价“It is outstanding.It is likely changing the game.”中国科学院软件研究所中国科学院软件研究所Institute of Software,Chinese Academ

24、y of Sciences机遇和挑战机遇和挑战把格局检测（把格局检测（CC）用于提高原有局部搜寻算法）用于提高原有局部搜寻算法简洁实现，开销小简洁实现，开销小（高效实现（高效实现CC策略参考本人在策略参考本人在AI Journal 2011和和AI Journal 2013的两篇论文）的两篇论文）可以普遍用于各种组合优化问题可以普遍用于各种组合优化问题尝试不同的尝试不同的CC策略，总有一款适合你策略，总有一款适合你（比如对于（比如对于SAT问题已有问题已有4种种CC策略：基于邻居变量的策略：基于邻居变量的CC，基于关联子句的，基于关联子句的CC，量化，量化CC，双层，双层CC）中国科学院软件研

25、究所中国科学院软件研究所Institute of Software,Chinese Academy of Sciences机遇和挑战机遇和挑战把格局检测（把格局检测（CC）用于提高原有局部搜寻算法）用于提高原有局部搜寻算法简洁实现，开销小简洁实现，开销小（高效实现（高效实现CC策略参考本人在策略参考本人在AI Journal 2011和和AI Journal 2013的两篇论文）的两篇论文）可以普遍用于各种组合优化问题可以普遍用于各种组合优化问题尝试不同的尝试不同的CC策略，总有一款适合你策略，总有一款适合你（比如对于（比如对于SAT问题已有问题已有4种种CC策略：基于邻居变量的策略：基于邻居

26、变量的CC，基于关联子句的，基于关联子句的CC，量化，量化CC，双层，双层CC）格局检测的理论分析格局检测的理论分析目前只得到一个结果目前只得到一个结果从理论上证明格局检测的有效性？从理论上证明格局检测的有效性？须要理论工作！须要理论工作！中国科学院软件研究所中国科学院软件研究所Institute of Software,Chinese Academy of Sciences参考文献参考文献关于格局检测（关于格局检测（CC）的更多信息，请参考以下文献）的更多信息，请参考以下文献Local search with edge weighting and configuration checking

27、 heuristics for minimum vertex cover.Artif.Intell.175(9-10):1672-1696(2011)Local search for Boolean Satisfiability with configuration checking and subscore.Artif.Intell.204:75-98(2013)Clause States Based Configuration Checking in Local Search for Satisfiability.IEEE T.Cybernetics 45(5):1014-1027(2015)CCLS:An Efficient Local Search Algorithm for Weighted Maximum Satisfiability.IEEE Trans.Computers 64(7):1830-1843(2015)也欢迎大家访问我的主页：也欢迎大家访问我的主页：:/lcs.ios.ac/caisw/中国科学院软件研究所中国科学院软件研究所Institute of Software,Chinese Academy of Sciences感谢！