论文部分内容阅读
摘要:约束满足问题是人工智能的重要研究方向。约束传播技术和启发式策略是影响约束求解算法效率的关键。对于大规模和大型具有结构化特征的问题,设计并运用有效的值序、变量序启发式策略将大大缩减搜索空间,极大提高问题求解效率。文中对现在流行的静态启发式、动态启发式和冲突驱动的启发式等不同类别的启发式采用标准库问题实例进行适应性求解测试,并对各种启发式策略进行性能评估。
关键词:人工智能;约束满足问题;弧相容;启发式策略
中图分类号:TP18 文献标识码:A 文章编号:1674-7712 (2012) 12-0123-03
一、引言
近年来,作为人工智能领域最活跃的研究分支之一,约束程序(Constraint Programming,CP)研究方向得到蓬勃发展。约束程序研究的核心问题是约束满足问题(Constraint Satisfaction Problem,CSP)。目前,该领域出现了以约束传播技术和针对大规模应用问题的启发式策略为代表的研究新热点。
相容性技术是约束传播的代表技术,它在加速求解效率和压缩求解空间上发挥着不可估量的巨大作用0。目前主流技术是弧相容性和路径相容性技术。弧相容技术是相容性技术中应用最为广泛的。1977年,Mackworth提出了著名的实现弧相容性的算法AC30。为得到最优的时间复杂度,Mohr和Henderson提出AC40,但以较大的空间复杂度为代价。此后Bessière相继提出算法AC60,AC70和AC20010。
对于变量启发式,早期主要是静态变量启发式(SVO),代表是最小宽度(min width)和最大度(max degree)启发式0;2001年Bessiere提出带选择函数的动态变量启发式的一般框架0;2004年Boussemart等提出了冲突驱动的变量启发式策略0;2007年,2008年Grims和Wallace共同提出了将值删除作为基本传播事件及与加权约束相结合冲突驱动的变量启发式00。但对于多种启发式策略的全面性能评估和对于问题的适应性研究,以及各种启发式策略混合应用方面还有很大的研究空间。
二、约束满足问题
约束满足问题(Constraint Satisfaction Problem)常表示成一个三元组 。其中X是变量的有限集合,表示成 ; = 是变量值域的集合,其中 是变量 的值域; 是一个有限约束集合。约束满足问题的求解是为变量集 中的每个变量从其有限论域中寻找一个值,使得约束集 中的所有约束被满足。
通常可将约束满足问题用约束图的形式表示。图1为地图着色问题实例的约束图。其中,数字表示二元约束满足问题的变量;字母表示变量的论域;变量之间的直线代表二元约束关系,含义为这两个变量不能取相同的值。
三、弧相容技术
为了提高效率,常在约束满足问题的求解过程中应用约束传播技术或相容性技术。弧相容技术是相容性技术中最为著名的。对于二元约束图中的弧 ,称它是弧相容的(Arc Consistency),当且仅当对于变量 的论域中的每一个值 ,在变量 的论域中都存在一个值 ,使得 满足 上的一元约束,并且 满足 和 上的二元约束 。一个CSP是弧相容的,当且仅当它的约束图中每一条弧都是弧相容的0。
1977年Mackworth提出了著名的弧相容算法AC-30。AC-3长久以来被广泛应用。下面我们给出AC-3的算法框架:
Algorithm 3.1 AC-3( )
while do
if revise( ) then
if then return false
else
return true
Algorithm 3.2 revise( ):boolean
flag=false
for each a do
if not such that then
delete from
flag=true
end if
end for
return flag
AC-3算法的时间复杂度下界为 ,最坏情况下的时间复杂度为 ,其空间复杂度为 。其中 是约束的个数, 是变量域的规模, 是变量的个数。
四、启发式策略
启发式策略作为一种展望策略,引导或者决定接下来要实例化哪个变量或将论域中的哪个值赋给变量。对于大规模的约束满足问题的求解,启发式的应用能够有效压缩求解空间,快速得到问题的解或者指出问题无解。我们研究了当前流行的各种变量启发式策略,将其分类为:静态变量启发式、动态变量启发式和冲突驱动的变量启发式。
(一)静态变量启发式
静态变量启发式策略(SVOs)中,变量在搜索的整个过程中保持不变的排序,仅仅使用问题初始状态的结构化信息。最简单的静态启发式策略是字典序(lexico),即将变量按字典序排序。在约束图中,相互间有约束关系的变量称为彼此的邻居。变量的度定义为邻居的个数。启发式策略deg(max degree)根据度的降序将变量排序。
其他的静态变量启发式策略有min width启发式策略和min bandwidth启发式策略等。
(二)动态变量启发式
动态变量启发式策略(DVOs)是非常高效的,因此受到更多的关注。这些启发式策略考虑搜索过程中每一时刻问题当前状态的信息。
最早广为人知的动态启发式策略是由Haralick和Elliott提出的dom启发式,它选择有着最小剩余域的变量。另一种常用动态启发式是deg的一个动态变种叫做ddeg,它选择有最大动态度的变量,即被最多的未被赋值的变量所约束的变量。将 和 (或ddeg)结合而衍生出的复合启发式称作 (或dom/ddeg)。这些启发式选择当前域大小与静态度(动态度)的比值最小的变量。这两种复合启发式结合了变量的多重信息,可以显著地提高搜索性能。 当应用启发式时,经常见到这样的现象:两个或多个变量是等价的。如用dom启发式时,会遇到有两个变量 与 的域大小相等且最小。这时需要一种策略来打破这一关系。常见的能打破dom启发式中这种关系的是lexico,(dom+lexico组合的启发式)它选在同时有最小域的多个变量中按字典序排在第一位置的那个变量。
(三)冲突驱动的变量启发式
2004年Boussemart等受SAT求解器的启发,提出了冲突驱动的变量启发式策略0。在启发式中为每一个约束设置一个权重,并初始化为1。在搜索期间,当某个约束导致一个失败(即变量的域为空DWO)时,该约束的权重加1。每个变量有一个动态变化的权度,定义为与该变量关联的所有约束的权重之和。变量的权度由下式计算:
| (1)
其中, 表示约束 中未实例化的变量, 是约束 的权重, 是 所约束的变量。
权度变量启发式(wdeg)选择有最大权度的变量。同时,我们可以结合域的信息,进而产生一种复合启发式 ,它选择域大小与权度的比值最小的变量。
冲突驱动的启发式wdeg和 为每个约束设置一个计数器,用于记录权重。每当约束导致一个DWO,约束的权重加1。这个动态过程可由下述算法描述:
Algorithm 4.1 revice( ):boolean
for each a do
If not such that then
Delete from
responsibleConstraint[ ][ ]=
end if
end for
if then
Weight[ ]++
end if
return
经验表明上述启发式对大部分问题非常有效,但其权重的分配不总是合理的,它们没有考虑到有的约束虽没有直接导致DWO,但它起到间接作用。为此,Grims和Wallace共同提出了将值删除作为基本传播事件并与加权约束相结合的冲突驱动变量启发式00。根据权重计算方法的不同,有三种冲突驱动的变量启发式 。其权重的计算可由下述算法描述:
Algorithm 4.1 revice( ):boolean
for each a do
If not such that then
Delete from
responsibleConstraint[ ][ ]=
end if
end for
if then
//
for each
//
//
end for
end if
return
对于上述启发式,我们可以定期的老化约束的权重,即让约束的权重周期性的除以一个大于1的小常数。从而给予最近发现的冲突更大的影响力,这样的策略有助于提高性能。
五、启发式策略测试
为得到各种变量启发式策略的适应性数据,我们采用标准库问题对算法进行测试。主要通过执行效率(CPU时间)和搜索树节点数来比较各种启发式策略在不同规模问题上的性能。测试的环境为:Lenovo ideapad Y450,Inter Core(TM) Duo 2.13GHz CPU,2.00G RAM;Windows 7 home basic,Visual C++6.0。
从结果分析,静态变量启发式为弱启发式,并不能很好地提高求解效率,甚至当问题规模太大时得不到解。动态启发式策略(dom/deg、dom/ddeg等)对于提高求解效率有着不错的效果。冲突驱动的变量启发式(wdeg、dom/wdeg等)由于其算法中有冗余计算,在问题规模较小时并不能体现其优势,效果有时不如其他启发式;但当问题规模变大时,冲突驱动的变量启发式能显著提高求解效率。
六、结束语
相容性技术和启发式策略在CSP求解过程之中发挥着巨大的作用,决定着求解算法的性能。本文论述了最具代表性的相容性技术——弧相容技术。对现在流行的变量启发式进行了分类,并使用标准库问题对不同启发式策略进行测试,得到其适应性数据。未来的研究工作中,我们将应用更具结构化特征的随机问题对各类启发式进行效率评估,探索建立一个面向问题结构化特征结合多种启发式策略的高效约束求解算法框架。
参考文献:
[1]P.van Beek,F. Rossi,and T.Walsh editors. Handbook of constraint programming.Elsevier,2006
[2]A.K.Mackworth.Consistency in networks of relations.Artificial Intelligence,1977,8:99-118
[3]R.Mohr and T.C.Henderson.Arc and Path Consistency Revised,Artificial Intelligence,1986,28:225-233
[4]C.Bessière.Arc consistency and arc consistency again.Artificial Intelligence,1994,65:179-190
[5]C.Bessière,E.C.Freuder,and J.C.Régin.Using constraint metaknowledge to reduce arc consistency computation.Artificial Intelligence,1999,107:125-148
[6]C.Bessière and J.C.Régin.Refining the basic constraint propagation algorithm.In:Proceedings of IJCAI,2001:309-315 [7]E.C.Freuder.A sufficient condition for backtrack-free search.Journal of the ACM,1982,29(1):24-32
[8]C.Bessière,A.Chmeiss,and L.Sais.Neighborhood-based variable ordering heuristics for the contraint satisfaction problem.In Proceedings of the 7th Conference on Principles and Practice of Constraint Programming (CP-2001),pages2001:61-75
[9]F.Boussemart,F.Hemery,C.Lecoutre,and L.Sais.Boosting systematic search by weighting constraints.In Proceedings of 16th European Conference on Artificial Intelligence (ECAI-2004),pages 146-150,Valencia, Spain,2004
[10]D.Grimes and R.J.Wallace.Sampling strategies and variable selection in weighted degree heuristics.In Proceedings of the 13th Conference on Principles and Practice of Constraint Programming (CP-2007),pages,2007,831-838
[11]R.J.Wallace and D.Grimes.Experimental studies of variable selection strategies based on constraint weights.Journal of Algorithms,2008,63(1-3):114–129
[12]M.Correia and P.Barahona.On the integration of singleton consistency and look-ahead heuristics.In Proceedings of the ERCIM workshop-CSCLP,pages,2007,47-60
关键词:人工智能;约束满足问题;弧相容;启发式策略
中图分类号:TP18 文献标识码:A 文章编号:1674-7712 (2012) 12-0123-03
一、引言
近年来,作为人工智能领域最活跃的研究分支之一,约束程序(Constraint Programming,CP)研究方向得到蓬勃发展。约束程序研究的核心问题是约束满足问题(Constraint Satisfaction Problem,CSP)。目前,该领域出现了以约束传播技术和针对大规模应用问题的启发式策略为代表的研究新热点。
相容性技术是约束传播的代表技术,它在加速求解效率和压缩求解空间上发挥着不可估量的巨大作用0。目前主流技术是弧相容性和路径相容性技术。弧相容技术是相容性技术中应用最为广泛的。1977年,Mackworth提出了著名的实现弧相容性的算法AC30。为得到最优的时间复杂度,Mohr和Henderson提出AC40,但以较大的空间复杂度为代价。此后Bessière相继提出算法AC60,AC70和AC20010。
对于变量启发式,早期主要是静态变量启发式(SVO),代表是最小宽度(min width)和最大度(max degree)启发式0;2001年Bessiere提出带选择函数的动态变量启发式的一般框架0;2004年Boussemart等提出了冲突驱动的变量启发式策略0;2007年,2008年Grims和Wallace共同提出了将值删除作为基本传播事件及与加权约束相结合冲突驱动的变量启发式00。但对于多种启发式策略的全面性能评估和对于问题的适应性研究,以及各种启发式策略混合应用方面还有很大的研究空间。
二、约束满足问题
约束满足问题(Constraint Satisfaction Problem)常表示成一个三元组 。其中X是变量的有限集合,表示成 ; = 是变量值域的集合,其中 是变量 的值域; 是一个有限约束集合。约束满足问题的求解是为变量集 中的每个变量从其有限论域中寻找一个值,使得约束集 中的所有约束被满足。
通常可将约束满足问题用约束图的形式表示。图1为地图着色问题实例的约束图。其中,数字表示二元约束满足问题的变量;字母表示变量的论域;变量之间的直线代表二元约束关系,含义为这两个变量不能取相同的值。
三、弧相容技术
为了提高效率,常在约束满足问题的求解过程中应用约束传播技术或相容性技术。弧相容技术是相容性技术中最为著名的。对于二元约束图中的弧 ,称它是弧相容的(Arc Consistency),当且仅当对于变量 的论域中的每一个值 ,在变量 的论域中都存在一个值 ,使得 满足 上的一元约束,并且 满足 和 上的二元约束 。一个CSP是弧相容的,当且仅当它的约束图中每一条弧都是弧相容的0。
1977年Mackworth提出了著名的弧相容算法AC-30。AC-3长久以来被广泛应用。下面我们给出AC-3的算法框架:
Algorithm 3.1 AC-3( )
while do
if revise( ) then
if then return false
else
return true
Algorithm 3.2 revise( ):boolean
flag=false
for each a do
if not such that then
delete from
flag=true
end if
end for
return flag
AC-3算法的时间复杂度下界为 ,最坏情况下的时间复杂度为 ,其空间复杂度为 。其中 是约束的个数, 是变量域的规模, 是变量的个数。
四、启发式策略
启发式策略作为一种展望策略,引导或者决定接下来要实例化哪个变量或将论域中的哪个值赋给变量。对于大规模的约束满足问题的求解,启发式的应用能够有效压缩求解空间,快速得到问题的解或者指出问题无解。我们研究了当前流行的各种变量启发式策略,将其分类为:静态变量启发式、动态变量启发式和冲突驱动的变量启发式。
(一)静态变量启发式
静态变量启发式策略(SVOs)中,变量在搜索的整个过程中保持不变的排序,仅仅使用问题初始状态的结构化信息。最简单的静态启发式策略是字典序(lexico),即将变量按字典序排序。在约束图中,相互间有约束关系的变量称为彼此的邻居。变量的度定义为邻居的个数。启发式策略deg(max degree)根据度的降序将变量排序。
其他的静态变量启发式策略有min width启发式策略和min bandwidth启发式策略等。
(二)动态变量启发式
动态变量启发式策略(DVOs)是非常高效的,因此受到更多的关注。这些启发式策略考虑搜索过程中每一时刻问题当前状态的信息。
最早广为人知的动态启发式策略是由Haralick和Elliott提出的dom启发式,它选择有着最小剩余域的变量。另一种常用动态启发式是deg的一个动态变种叫做ddeg,它选择有最大动态度的变量,即被最多的未被赋值的变量所约束的变量。将 和 (或ddeg)结合而衍生出的复合启发式称作 (或dom/ddeg)。这些启发式选择当前域大小与静态度(动态度)的比值最小的变量。这两种复合启发式结合了变量的多重信息,可以显著地提高搜索性能。 当应用启发式时,经常见到这样的现象:两个或多个变量是等价的。如用dom启发式时,会遇到有两个变量 与 的域大小相等且最小。这时需要一种策略来打破这一关系。常见的能打破dom启发式中这种关系的是lexico,(dom+lexico组合的启发式)它选在同时有最小域的多个变量中按字典序排在第一位置的那个变量。
(三)冲突驱动的变量启发式
2004年Boussemart等受SAT求解器的启发,提出了冲突驱动的变量启发式策略0。在启发式中为每一个约束设置一个权重,并初始化为1。在搜索期间,当某个约束导致一个失败(即变量的域为空DWO)时,该约束的权重加1。每个变量有一个动态变化的权度,定义为与该变量关联的所有约束的权重之和。变量的权度由下式计算:
| (1)
其中, 表示约束 中未实例化的变量, 是约束 的权重, 是 所约束的变量。
权度变量启发式(wdeg)选择有最大权度的变量。同时,我们可以结合域的信息,进而产生一种复合启发式 ,它选择域大小与权度的比值最小的变量。
冲突驱动的启发式wdeg和 为每个约束设置一个计数器,用于记录权重。每当约束导致一个DWO,约束的权重加1。这个动态过程可由下述算法描述:
Algorithm 4.1 revice( ):boolean
for each a do
If not such that then
Delete from
responsibleConstraint[ ][ ]=
end if
end for
if then
Weight[ ]++
end if
return
经验表明上述启发式对大部分问题非常有效,但其权重的分配不总是合理的,它们没有考虑到有的约束虽没有直接导致DWO,但它起到间接作用。为此,Grims和Wallace共同提出了将值删除作为基本传播事件并与加权约束相结合的冲突驱动变量启发式00。根据权重计算方法的不同,有三种冲突驱动的变量启发式 。其权重的计算可由下述算法描述:
Algorithm 4.1 revice( ):boolean
for each a do
If not such that then
Delete from
responsibleConstraint[ ][ ]=
end if
end for
if then
//
for each
//
//
end for
end if
return
对于上述启发式,我们可以定期的老化约束的权重,即让约束的权重周期性的除以一个大于1的小常数。从而给予最近发现的冲突更大的影响力,这样的策略有助于提高性能。
五、启发式策略测试
为得到各种变量启发式策略的适应性数据,我们采用标准库问题对算法进行测试。主要通过执行效率(CPU时间)和搜索树节点数来比较各种启发式策略在不同规模问题上的性能。测试的环境为:Lenovo ideapad Y450,Inter Core(TM) Duo 2.13GHz CPU,2.00G RAM;Windows 7 home basic,Visual C++6.0。
从结果分析,静态变量启发式为弱启发式,并不能很好地提高求解效率,甚至当问题规模太大时得不到解。动态启发式策略(dom/deg、dom/ddeg等)对于提高求解效率有着不错的效果。冲突驱动的变量启发式(wdeg、dom/wdeg等)由于其算法中有冗余计算,在问题规模较小时并不能体现其优势,效果有时不如其他启发式;但当问题规模变大时,冲突驱动的变量启发式能显著提高求解效率。
六、结束语
相容性技术和启发式策略在CSP求解过程之中发挥着巨大的作用,决定着求解算法的性能。本文论述了最具代表性的相容性技术——弧相容技术。对现在流行的变量启发式进行了分类,并使用标准库问题对不同启发式策略进行测试,得到其适应性数据。未来的研究工作中,我们将应用更具结构化特征的随机问题对各类启发式进行效率评估,探索建立一个面向问题结构化特征结合多种启发式策略的高效约束求解算法框架。
参考文献:
[1]P.van Beek,F. Rossi,and T.Walsh editors. Handbook of constraint programming.Elsevier,2006
[2]A.K.Mackworth.Consistency in networks of relations.Artificial Intelligence,1977,8:99-118
[3]R.Mohr and T.C.Henderson.Arc and Path Consistency Revised,Artificial Intelligence,1986,28:225-233
[4]C.Bessière.Arc consistency and arc consistency again.Artificial Intelligence,1994,65:179-190
[5]C.Bessière,E.C.Freuder,and J.C.Régin.Using constraint metaknowledge to reduce arc consistency computation.Artificial Intelligence,1999,107:125-148
[6]C.Bessière and J.C.Régin.Refining the basic constraint propagation algorithm.In:Proceedings of IJCAI,2001:309-315 [7]E.C.Freuder.A sufficient condition for backtrack-free search.Journal of the ACM,1982,29(1):24-32
[8]C.Bessière,A.Chmeiss,and L.Sais.Neighborhood-based variable ordering heuristics for the contraint satisfaction problem.In Proceedings of the 7th Conference on Principles and Practice of Constraint Programming (CP-2001),pages2001:61-75
[9]F.Boussemart,F.Hemery,C.Lecoutre,and L.Sais.Boosting systematic search by weighting constraints.In Proceedings of 16th European Conference on Artificial Intelligence (ECAI-2004),pages 146-150,Valencia, Spain,2004
[10]D.Grimes and R.J.Wallace.Sampling strategies and variable selection in weighted degree heuristics.In Proceedings of the 13th Conference on Principles and Practice of Constraint Programming (CP-2007),pages,2007,831-838
[11]R.J.Wallace and D.Grimes.Experimental studies of variable selection strategies based on constraint weights.Journal of Algorithms,2008,63(1-3):114–129
[12]M.Correia and P.Barahona.On the integration of singleton consistency and look-ahead heuristics.In Proceedings of the ERCIM workshop-CSCLP,pages,2007,47-60