局部搜索定义为候选解集合.ppt
中国科学院软件研究所中国科学院软件研究所Institute of Software,Chinese Academy of Sciences格局检测：普适的格局检测：普适的局部搜索策略局部搜索策略蔡少伟蔡少伟中国科学院软件研究所中国科学院软件研究所2015.6.13中国科学院软件研究所中国科学院软件研究所Institute of Software,Chinese Academy of Sciences 组合优化组合优化组合优化问题组合优化问题u优化问题可以分为两类：一类是优化问题可以分为两类：一类是连续变量连续变量的问题，另一类是的问题，另一类是离散变量离散变量的问的问题，后者称为题，后者称为组合优化问题组合优化问题。u组合优化问题的任务：从一个有限或可数无限集里，寻找一个使得目标函组合优化问题的任务：从一个有限或可数无限集里，寻找一个使得目标函数最优的对象数最优的对象典型地包括：一组赋值，一个集合，一个排列。典型地包括：一组赋值，一个集合，一个排列。u组合优化问题随处可见，具有很强的工程代表性应用。组合优化问题随处可见，具有很强的工程代表性应用。u许多组合优化问题都是许多组合优化问题都是NP难的：最大可满足性（难的：最大可满足性（MaxSAT)问题，最大团问问题，最大团问题，最小顶点覆盖问题，旅行商问题。题，最小顶点覆盖问题，旅行商问题。中国科学院软件研究所中国科学院软件研究所Institute of Software,Chinese Academy of Sciences 组合优化组合优化组合优化问题组合优化问题u优化问题可以分为两类：一类是优化问题可以分为两类：一类是连续变量连续变量的问题，另一类是的问题，另一类是离散变量离散变量的问的问题，后者称为题，后者称为组合优化问题组合优化问题。u组合优化问题的任务：从一个有限或可数无限集里，寻找一个使得目标函组合优化问题的任务：从一个有限或可数无限集里，寻找一个使得目标函数最优的对象数最优的对象典型地包括：一组赋值，一个集合，一个排列。典型地包括：一组赋值，一个集合，一个排列。u组合优化问题随处可见，具有很强的工程代表性应用。组合优化问题随处可见，具有很强的工程代表性应用。u许多组合优化问题都是许多组合优化问题都是NP难的：最大可满足性（难的：最大可满足性（MaxSAT)问题，最大团问问题，最大团问题，最小顶点覆盖问题，旅行商问题。题，最小顶点覆盖问题，旅行商问题。n求解求解NP难组合优化问题难组合优化问题u分支限界：完备算法（保证解的最优性），回溯搜索，遍历解空间分支限界：完备算法（保证解的最优性），回溯搜索，遍历解空间u启发式搜索（包括局部搜索，演化算法等）：不完备算法，迭代改进，采启发式搜索（包括局部搜索，演化算法等）：不完备算法，迭代改进，采样解空间样解空间中国科学院软件研究所中国科学院软件研究所Institute of Software,Chinese Academy of Sciences局部搜索局部搜索简单地说，局部搜索是：简单地说，局部搜索是：u先产生一个（或一群）完整的候选解，然后进行迭代改进，每一步只修改先产生一个（或一群）完整的候选解，然后进行迭代改进，每一步只修改解的某个局部（比如一个基本单元），直到得到一个令人满意的解或者达解的某个局部（比如一个基本单元），直到得到一个令人满意的解或者达到某个资源限制（一般是时间限制）。到某个资源限制（一般是时间限制）。中国科学院软件研究所中国科学院软件研究所Institute of Software,Chinese Academy of Sciences局部搜索局部搜索简单地说，局部搜索是：简单地说，局部搜索是：u先产生一个（或一群）完整的候选解，然后进行迭代改进，每一步只修改先产生一个（或一群）完整的候选解，然后进行迭代改进，每一步只修改解的某个局部（比如一个基本单元），直到得到一个令人满意的解或者达解的某个局部（比如一个基本单元），直到得到一个令人满意的解或者达到某个资源限制（一般是时间限制）。到某个资源限制（一般是时间限制）。形式化一点说，局部搜索定义为：形式化一点说，局部搜索定义为：u候选解集合（也称搜索空间）候选解集合（也称搜索空间）S；u目标函数目标函数 f：S-R(实数集实数集)；u初始候选解集合初始候选解集合 I；u邻域关系邻域关系 N:S-2S，对于每个候选解，对于每个候选解s，N(s)=s S|N(s,s)S;（一（一般是基于候选解的海明距离，最常见的是般是基于候选解的海明距离，最常见的是1-海明距离邻域）海明距离邻域）u跳转函数（跳转函数（Step function）：定义了如何从当前候选解跳转到它的一个邻）：定义了如何从当前候选解跳转到它的一个邻居候选解居候选解中国科学院软件研究所中国科学院软件研究所Institute of Software,Chinese Academy of Sciences局部搜索局部搜索局部搜索的优点：局部搜索的优点：u简单；简单；u通用；通用；u容易实现；容易实现；u可扩展性强；可扩展性强；u许多许多NP难问题在求解性能上最好的算法都是基于局部搜索难问题在求解性能上最好的算法都是基于局部搜索什么时候使用局部搜索什么时候使用局部搜索u组合爆炸：对于组合爆炸：对于NP难问题，解空间是问题规模的指数级别难问题，解空间是问题规模的指数级别u时间限制短，或者时间资源非常重要时间限制短，或者时间资源非常重要u关于问题的领域知识太少关于问题的领域知识太少u接受近似解接受近似解中国科学院软件研究所中国科学院软件研究所Institute of Software,Chinese Academy of Sciences 一个局部搜索的例子一个局部搜索的例子一个例子：最大可满足性问题（一个例子：最大可满足性问题（MaxSAT）变元：x1,x2,x3,xn文字：变元或者其否定形式 x1,x1,子句：文字的析取 x1/x2,x1/x2/x4,.CNF公式：子句的合取，可看为一个子句集合MaxSAT（优化问题)：给出一组（布尔）赋值，满足最多子句。SAT（判定问题）：是否存在一组（布尔）赋值，满足所有子句。中国科学院软件研究所中国科学院软件研究所Institute of Software,Chinese Academy of Sciences 一个局部搜索的例子一个局部搜索的例子一个例子：最大可满足性问题（一个例子：最大可满足性问题（MaxSAT）u用局部搜索求解以下用局部搜索求解以下MaxSAT（或（或SAT）实例）实例u x1/x2,x1/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 Sciences局部搜索的循环问题局部搜索的循环问题局部搜索的局部搜索的循环问题循环问题u重复访问（近期刚访问过的）候选解重复访问（近期刚访问过的）候选解u花费很长时间在解空间的某个区域（比如某个局部最优附近的区域）搜索花费很长时间在解空间的某个区域（比如某个局部最优附近的区域）搜索u导致：容易陷入局部最优，花费太多时间在做无效搜索。导致：容易陷入局部最优，花费太多时间在做无效搜索。u很多局部搜索的文献其实都是围绕如何解决这个问题很多局部搜索的文献其实都是围绕如何解决这个问题循环问题不可能完全避免循环问题不可能完全避免u这是由局部搜索的无记忆性决定的这是由局部搜索的无记忆性决定的u不可能增加一个记忆机制来记住访问过的候选解，空间时间要求都太庞大不可能增加一个记忆机制来记住访问过的候选解，空间时间要求都太庞大中国科学院软件研究所中国科学院软件研究所Institute of Software,Chinese Academy of Sciences局部搜索的循环问题局部搜索的循环问题局部搜索的局部搜索的循环问题循环问题u重复访问（近期刚访问过的）候选解重复访问（近期刚访问过的）候选解u花费很长时间在解空间的某个区域（比如某个局部最优附近的区域）搜索花费很长时间在解空间的某个区域（比如某个局部最优附近的区域）搜索u导致：容易陷入局部最优，花费太多时间在做无效搜索。导致：容易陷入局部最优，花费太多时间在做无效搜索。u很多局部搜索的文献其实都是围绕如何解决这个问题很多局部搜索的文献其实都是围绕如何解决这个问题循环问题不可能完全避免循环问题不可能完全避免u这是由局部搜索的无记忆性决定的这是由局部搜索的无记忆性决定的u不可能增加一个记忆机制来记住访问过的候选解，空间时间要求都太庞大不可能增加一个记忆机制来记住访问过的候选解，空间时间要求都太庞大已有的（通用）方法已有的（通用）方法u随机游动随机游动u重启重启u以一定条件（如概率）允许非改进步以一定条件（如概率）允许非改进步uTabu策略：禁止反转近期内（策略：禁止反转近期内（t步内）所做的改动步内）所做的改动u加权方法改变能量地图加权方法改变能量地图中国科学院软件研究所中国科学院软件研究所Institute of Software,Chinese Academy of Sciences格局检测格局检测相关概念：相关概念：u 解的基本单元一般称为解部件(solution component)：在最大团问题中是一个点，在可满足性问题中是一个变元。u解部件的赋值：例如，点 选中，没选中,变元 true,false中国科学院软件研究所中国科学院软件研究所Institute of Software,Chinese Academy of Sciences格局检测格局检测相关概念：相关概念：u 解的基本单元一般称为解部件(solution component)：在最大团问题中是一个点，在可满足性问题中是一个变元。u解部件的赋值：例如，点 选中，没选中,变元 true,false格局检测（格局检测（configuration checking，简称，简称CC）的直观理解：）的直观理解：u无法记忆整个解，但可以记忆每个解部件的环境及其变化。u通过检测解部件的环境，减少解的局部结构上的循环，以此减少整个搜索的循环问题。u对于一个解部件x，如果从上次x改变赋值之后，x的环境没有改变过，那么禁止x变回原来的赋值。格局检测是一种从空间（或结构）上考虑的禁忌策略格局检测是一种从空间（或结构）上考虑的禁忌策略中国科学院软件研究所中国科学院软件研究所Institute of Software,Chinese Academy of Sciences格局检测格局检测解部件的格局解部件的格局u我们把解部件的环境信息称为它的格局，可以有不同的定义u最常见的是：一个解部件的格局，是一个由它的邻居解部件的赋值构成的向量。中国科学院软件研究所中国科学院软件研究所Institute of Software,Chinese Academy of Sciences格局检测格局检测解部件的格局解部件的格局u我们把解部件的环境信息称为它的格局，可以有不同的定义u最常见的是：一个例子：一个例子：CC for SATu邻居变量：如果两个变量出现在同一个子句中，称他们是邻居。u变量x的格局：一个由x的所有邻居变量的赋值构成的向量。一个解部件的格局，是一个由它的邻居解部件的赋值构成的向量。中国科学院软件研究所中国科学院软件研究所Institute of Software,Chinese Academy of Sciences格局检测用于格局检测用于SATSAT问题问题CC for SAT：对于一个变量v，如果从上次v改变赋值之后，v的格局没有改变过，那么禁止v变回原来的赋值。中国科学院软件研究所中国科学院软件研究所Institute of Software,Chinese Academy of Sciences顶点覆盖问题顶点覆盖问题顶点覆盖：对于一个无向图，一个顶点覆盖是一个顶点子集，使得每条边都至少有一个点属于该集合。最小顶点覆盖问题：给定一个无向图，找出最小的顶点覆盖。中国科学院软件研究所中国科学院软件研究所Institute of Software,Chinese Academy of Sciences格局检测用于顶点覆盖问题格局检测用于顶点覆盖问题最小顶点覆盖问题可以通过迭代解决其判定问题来求解u当找到一个规模为k的顶点覆盖时，继续寻找一个规模为k-1的顶点覆盖。u算法核心：对一个整数k，找一个规模为k的顶点集合覆盖所有的边。u初始的时候，构造一个规模为k的顶点集合（候选解）。u局部搜索的每一步交换集合中的一点和集合外的一点。中国科学院软件研究所中国科学院软件研究所Institute of Software,Chinese Academy of Sciences格局检测用于顶点覆盖问题格局检测用于顶点覆盖问题最小顶点覆盖问题可以通过迭代解决其判定问题来求解u当找到一个规模为k的顶点覆盖时，继续寻找一个规模为k-1的顶点覆盖。u算法核心：对一个整数k，找一个规模为k的顶点集合覆盖所有的边。u初始的时候，构造一个规模为k的顶点集合（候选解）。u局部搜索的每一步交换集合中的一点和集合外的一点。格局检测：对一个顶点v，如果从上次v被移出候选解之后，v的格局没有改变过，那么禁止把v重新加入候选解。中国科学院软件研究所中国科学院软件研究所Institute of Software,Chinese Academy of Sciences格局检测格局检测更一般的说，格局检测（更一般的说，格局检测（CC）是一种思想）是一种思想u不同的格局定义不同的CC策略。v比如对SAT问题，变量的格局还可以定义为：变量的关联子句的状态构成的向量。u不同的检测方法不同的CC策略。v比如量化CC，以格局改变的幅度作为选择解部件的一个优先序法则。u不同的格局定义，禁忌强度不同。v可以设计多层次的CC策略。中国科学院软件研究所中国科学院软件研究所Institute of Software,Chinese Academy of Sciences格局检测格局检测格局检测已经被使用于多个组合优化问题格局检测已经被使用于多个组合优化问题uSAT，MaxSAT，顶点覆盖，最大团，图着色，集合覆盖，支配集，刻度划分问题等等。u从2011年提出到目前已经产生20几篇论文（包括其他团队）。格局检测对格局检测对SAT领域产生极大影响领域产生极大影响u2013年SAT比赛随机组接近40%的solver使用该技术；u最近三年，共有6个获奖SAT solver使用该技术，包括2个第一，2个第二，2个第三；u最近两年，非完备算法组获奖的MaxSAT solver大都采用了格局检测。uAAAI 2013年关于SAT方面的Tutorial Forum评价“It is outstanding.It is likely changing the game.”中国科学院软件研究所中国科学院软件研究所Institute of Software,Chinese Academy of Sciences机遇和挑战机遇和挑战把格局检测（把格局检测（CC）用于提高原有局部搜索算法）用于提高原有局部搜索算法u容易实现，开销小（高效实现CC策略参考本人在AI Journal 2011和AI Journal 2013的两篇论文）u可以普遍用于各种组合优化问题u尝试不同的CC策略，总有一款适合你（比如对于SAT问题已有4种CC策略：基于邻居变量的CC，基于关联子句的CC，量化CC，双层CC）中国科学院软件研究所中国科学院软件研究所Institute of Software,Chinese Academy of Sciences机遇和挑战机遇和挑战把格局检测（把格局检测（CC）用于提高原有局部搜索算法）用于提高原有局部搜索算法u容易实现，开销小（高效实现CC策略参考本人在AI Journal 2011和AI Journal 2013的两篇论文）u可以普遍用于各种组合优化问题u尝试不同的CC策略，总有一款适合你（比如对于SAT问题已有4种CC策略：基于邻居变量的CC，基于关联子句的CC，量化CC，双层CC）格局检测的理论分析u目前只得到一个结果u从理论上证明格局检测的有效性？需要理论工作！中国科学院软件研究所中国科学院软件研究所Institute of Software,Chinese Academy of Sciences参考文献参考文献关于格局检测（关于格局检测（CC）的更多信息，请参考以下文献）的更多信息，请参考以下文献uLocal search with edge weighting and configuration checking heuristics for minimum vertex cover.Artif.Intell.175(9-10):1672-1696(2011)uLocal search for Boolean Satisfiability with configuration checking and subscore.Artif.Intell.204:75-98(2013)uClause States Based Configuration Checking in Local Search for Satisfiability.IEEE T.Cybernetics 45(5):1014-1027(2015)uCCLS:An Efficient Local Search Algorithm for Weighted Maximum Satisfiability.IEEE Trans.Computers 64(7):1830-1843(2015)也欢迎大家访问我的主页：也欢迎大家访问我的主页：http:/ of Software,Chinese Academy of Sciences谢谢！
