分散搜索二进制的问题.docx
《分散搜索二进制的问题.docx》由会员分享，可在线阅读，更多相关《分散搜索二进制的问题.docx（8页珍藏版）》请在冰点文库上搜索。
分散搜索二进制的问题
分散搜索二进制的问题
旧金山Gorta'zar1,亚伯拉罕·杜阿尔特1,曼努埃尔·拉古纳2,拉斐尔Marti'3。
抽象
在这一章,我们提出了一种基于散射程序搜索方法,可用于搜索解空间的优化问题的解决方案可表示为二进制向量。
这是一个暗箱操作程序在这个意义上说,它不是定制解决某个特定问题在这个班。
我们把它和三个软件产品时,基于准启发式技术解决两个众所周知的二进制优化问题:
背包和最大多样性的问题。
1简介
本文的目的是发展一个暗箱操作方法求解一类重要组合优化问题。
具体地说,我们解决问题的解决方案可以代表一个向量二进制变量与。
我们工作的主要贡献的发展是一个程序基于分散搜索方法,可用于搜索解空间的优化问题的解决方案可表示为二进制向量。
程序一般都在这个意义上说,它不是定制解决某个特定问题在这个班。
求解优化问题时,有个普遍的作法是建立一个上下文方法（例如,一个过程,即明确地剥削的结构和性能问题,才能进行有效的搜索）。
大多数启发式准启发式的实现是基于这种范式,即:
发展一个专门的方法为一个特定的问题。
我们当前的目标是不同的,因为我们试图创造一个合理的解决方法,发现质量问题,对一类基于上下文独立的范式。
暗箱操作的人（也称通用优化的基础上找到了自己的家metaheuristics商业的实现。
我们已发现三种软件产品基于准启发式技术,这是能够解决类二元问题。
保险费由FrontlineSystems求解股份有限公司（Opttek图书馆系统公司（
2分散搜索程序
分散的搜索（SS）是一个准启发式探索一套解决进化的空间参考点。
这里有5个方法及其相关的策略。
他们三个人,一代的多样化、改进和组合方法,通常是模拟的特点,适用于问题或类别的问题被解决（我们投入他们各人一节）。
其他两个,参考组和子集更新生成方法,我们使用了标准实现[4]因为大多数的分散搜索的实现。
我们已经适应学生开发一个暗箱操作方面和二进制变量优化问题。
我们假设一个问题实例包括找到一套价值观x=（x1;x2;:
:
:
;xn）-wherexi=0or1-为了最大限度地一个未知的目标函数。
用户已经选择特定的问题是是否无约束或限制。
为无约束问题,任何二元向量氮元素是一个可行的解决方案。
针对有约束问题,解决的办法评估师返回一个布尔值表示是否切实可行解。
换句话说,解决的方法不知道的水平或哪些特定变量预测需要给予一个值为0,使解决方案是可行的。
解决的方法,然而,我们知道这个类型的问题,可能最终实现可行性开关变量值从1到0。
2．1多样化的生成方法。
搜索开始多样化的应用与生成方法,其结果在P的人口的点数PSize选定一个子集为初始参考集（RefSet）。
得到不同结构的解决方案与江苏三个不同的发电机,创造PSize二元向量/3的解决方案与每一个元素。
我们首先创建PSize/3的解决方案与系统发电机[4],然后计算评分（i）,为每一个变量xi估计其对目标函数值的大小为了产生剩下的两PSize/3方案考虑在质量和多样性。
分数的计算,这样大（小）评分变量的值表明,从历史上看,目标函数值较高的这个变量的质量得到了需要的价值1（0）。
第二个发电机,G2,构筑了溶液一步一步,从所有的变量设置为0,和交换的每一步一个变量从0到1。
变量的概率随机选择和改变选择从0到1变量问题,给出了Prob（xi=1）=0:
1+score（i）。
增加0.1的概率计算方面是一种偏见去改变这个变量的值从0到1当比分是接近0.5。
为无约束问题,G2执行步骤只要解决施工能力的提高。
针对有约束问题,G2执行步骤只要解决仍然是可行的。
第三个发电机,G3,可以看作是一种破坏性的方法[2]。
它始于所有的变量设置为1,在每一步,它的价值转换变量从1到0。
根据变量选择分数的概率值。
补充的成绩（i.e.,1-Prob（xi=1））被用来计算的概率值变化从1到0。
停止准则是定制的两方面的问题以类似的方式在G2。
最初的RefSet必须平衡解的质量和多样性,我们遵循标准集更新方法,选择最佳的b/2解决方案（whereb=|RefSet|）地方从P然后b/2的解决方案是最多样P关于这些已在RefSet（计算最大值之间的最小安全距离和解决方案,每个解决方案已经在RefSet分散,因为它是前所未有的搜索）。
多样性是根据以下距离测量函数关系的解决方案。
解决方案之间的距离x=（x1;x2;:
:
:
;xn）andy=（y1;y2;:
:
:
;yn）给出了d（x;y）=∑（i=1-n）|xi-yi|。
我们按标准的子集生成方法和程序生成所有成对的参考解决方案,没有结合之前。
我们会限制应用改进的方法对前途的解决方案。
具体地说,我们保存试验方案产生的应用在临时池相结合的方式,运用改进的方法对b/2最好的解决方案在池中。
参考设置则是通过选择最佳更新b的解决方案的结合、泳池RefSet（这里的改进方案在池代替了原先的）。
若该等特征组合方法是无法创造解决方案,可以被RefSet,参考设置重建。
重建由保持最好的b/2的解决方案和更换最坏的完整的b/2的解RefSet不同的解决方案和新方法后页停止MaxTimeCPU秒预设定。
2．2改善方法
改进的方法包括将一种局部搜索过程。
它是适用于最好的b/2RefSet的解。
一个全球的迭代改进的方法包括三个步骤。
首先,我们构造的候选名单上CL=fxij（喜=0^评分（我）¸th1）_（喜=0^（i）与分数·）克的元素（变量）被改变。
CL包含变量和0的值和一个大型的评分值（接近1）,以及变量与一个数值为1和一个小得分值（接近于0）。
因此,基于分数信息我们应该°ip（1-0,从0到1）价值的变量在冠军杯。
在第二步我们订购元素氯（变量）根据他们的分数值（那些最大的分数都位于第一）,然后,在第三步,我们浏览顺序中寻找提高动作。
在我们完成几个迭代的第三个步骤交替°ip和交换动作,一个由交换价值交换的两种不同的变量。
我们努力在第一个迭代°ip活动的所有元素氯（放在号令）,改变他们的价值提高了目标函数。
重建的CL是在这一点。
然后,在第二个迭代我们认为交换活动的所有元素氯（检查为了）,我们试着交换价值与价值中的每个变量的另一个变量的改变。
为了做到这一点,我们实行第一策略,用于扫描的名单中变量的搜索结果的第一个运动以一个严格的积极的改变,使目标函数值。
在这个过程中,冠军联赛是一项重建了。
进一步的迭代进行°之间的转换,实现ip和交换动作。
该方MaxImpIter迭代或之前停止后,如果没有提升尽°后取得了（ip）和互换。
2.3相结合的方式
参考设置是一家集b方案被用来产生新的解决方案的应用相结合的方式。
摘要为了设计出一种独立的方法,具有良好的背景下,跨越广泛收集不同的二进制的问题,我们提出一套六组合方法是选择哪一个概率根据其性能在以前的迭代（即,选择过程是反应性的）。
该方法成功地应用[1]。
在RefSet方案排序根据他们的目标函数值的大小（这里的最佳解决方案排第一位）。
当一个解相结合的方法jth离心机械公司认可的成员RefSet现状的基础上,增加“+1b.成功（离心机械公司）。
因此,组合方法,良好解决方案积累产生较高的成功的价值观和增加的可能性被选中的比例。
为了避免最初的偏见,这一机制是激活在第一个InitIter组合,而在此之前,是完全随意的选择。
结合的方法描述如下。
这些方法产生新的试验方案,结合两种z从x和y的参考方案。
应当指出,得分值,解决这些问题的初步计算在P,更新是在整个搜索过程,从而提供一个估计的贡献的每一个变量（当它需要的价值1）目标函数值的大小。
结合的方法先CM1计算z形成了一个以解决部分问题的“联盟”的x和y,那是zi=1如果xi=1或者yi=1,否则zi=0.然后进行了一系列的步骤交换一些变量从1变为0,以类似方式为G3发电机。
具体地说,在每一个步骤,该方法使用分数值概率选择一个变量的值为1,把它设置为0。
为无约束（限制）问题,它还在这时尚,并解决提高（仍然可行的。
平方厘米的组合方法类似于CM1唯一不同的变量选择（开关价值从1到0在z）,执行这些是完全随机的,就是不考虑得分值。
结合的方法是一种适应CM3一文献[4]提出的背景下,背包问题。
该方法计算出的权值,每一个变量,基于目标函数值的两个参考方案被结合在一起。
我的体重相适应的变量结合x和y的对照溶液计算,下面的公式:
在这个公式f（x）是解决方案的目标函数值x和xi的价值与变量。
然后,解决了试验利用z分量的概率为每个变量的设置一个,即不利于（zi=1）=重量（i）
你的CM4组合计算方法先解决部分问题z构建“十字路口”的x和y。
很多步骤,然后执行一个变量的值为0被选中我选择变量的概率是成正比的重量（i）。
（注:
大的重量更吸引人它,至少从历史的搜索,将此值设置一个变量的。
）区别是CM3和CM4，CM3开始过程变量值切换从0到1与所有的变量被设置为0的CM4时从z是解决部分问题交叉参考解决方案被结合在一起。
CM4停在CM1一样,这取决于类型的问题。
CM5的方法组合是非常相似的CM4。
从解决部分问题采用对照溶液的交汇点,变量被设置为0的时候被选出来改变他们的价值为1。
唯一的不同是变量CM4与0的值是完全随意的选择,那就是,无视他们的权值。
CM6方法组合的开始与所有的变量值设置为0。
然后,适用于建设性的方法与G2制约子变量转换为候选人1是一个数值为1在x或y（即为xi+yi>=1）。
3实验结果
这一节将描述计算实验表明,从文学我们实施了测试效率的搜索程序上下文独立的分散以及各种方法对比。
我们已经实行了硒的方法,在爪哇6和所有的实验进行了4计算机奔腾3兆赫2GB的内存。
我们已经使用了两个组合优化问题,考验我们的程序。
这些问题的解决方案是自然的二元向量表现为:
0-1背包问题和最大多样性的问题。
这个背包问题包括选择,从一组项目,子集,最大限度的价值目标函数进行容量约束。
这是一个budget-constrained问题,试图最大限度地利益联系在一起的一个子集可以选择n对象。
Pisinger[6]被认为是一个三步方法比基于熟知之间的目标函数和约束coeffcients。
我们用这个专业方法相比在我们的实验结果。
我们认为96年从四种类型实例,证明在Pisinger[5]:
密切相关,子集金额、性能和弱相关实例。
具体地说,我们的目标组,每组24实例和n=100、300、1000、3000（6实例为每个n值）。
最大的多样性问题（家乐福）是由一个子集的钾元素选择从一组元素氮以这样一种方式的总和要素之间的距离是选择最大化。
显然,解决这个问题的办法可以表现为一个二进制字符串x,在西安以其变量的价值选择1和0元素我,否则我=1;:
:
;n。
只有一个约束力量这个问题到底在字符串中k变量被分配的价值为1。
这个问题属于一类二元约束问题。
我们将对照法和最近的专业SS算法在[3],因为它已被证明比以前的方法。
我们认为两种来源的92件。
第一个有40个情况下,被称为格,其价值是欧氏距离计算为随机生成的分在0到100的坐标范围。
第二个有52个情况下,被称为席尔瓦,其价值是整数编号随机生成的,50至100。
产品的价值50-300和中k值的范围很广,从0:
1n到0:
3n。
在每个实验,我们为每一个实例计算,整体最佳解决方案价值、最佳值,得到的所有执行过程的方法。
然后,对每种方法的相对百分比计算最佳解决方案价值之间的偏差（价值）取得最佳值方法和实例。
我们报告了平均的偏差（开发）,100%是指定的价值是没有找到一种可行的解决方案。
以这种方式,平均开发价值反映方法的能力来寻找可行的解决方案。
我们也报告,给每一个方法,一定数量的情况下,取得任何可行的解决方案（#可行的）和数量的情况下,最好的解决方法的价值通过该方法,已得到最有价值的比赛（#最好的）。
此外,我们提出的计算秩统计量[7]-与相关各方法。
为每一种媒体,n等级的方法M是定义为方法的数量,发现了一个更好的解决办法比一个发现M。
在案例的领带,所有的方法得到同样的n等级,等于严格方法的数量超过一切。
等级的价值之和的n等级值情况下在实验中,因此,低等级的更好的方法。
在我们的实验实例初步代表（48背包和48躁郁我们设置参数,与th1）等于（0,1）和MaxImpIter参数等于30岁。
我们实施我们比较分散的搜索（黑匣子的SS）对三个众所周知的商业解决以上介绍中提到:
进化求解系统的保险费线求解软件开发工具包（7.2版）,OptQuest由OptTek系统（6.2版）和Evolver围护公司由Evolver开发工具包（版本4.1.2）。
我们也与专业的方法以及解用Cplex數学求解线性整数配方时的问题。
表格1和2Dev.报告,#可行,#最好的和阶级价值观的六种方法考虑问题分别背包、家乐福。
解除限制被设定为所有30秒的方法。
表1。
背包问题
表2。
最大分集度问题
学生的行为是相当一致的暗箱操作问题在两类。
该方法提供了低相对百分比偏差就最著名的解决方案和总是队伍在暗箱操作的人最好,这也是基于进化策略。
此外,在两个问题都得到可行解的情况下。
注意Evolver得到可行的解决方法只有在9个实例求解家乐福在92年仅仅是能够获得47个可行解的96个背包实例。
OptQuest的性能是相当强劲这两种问题。
另一方面,取得了较好的效果上Cplex數学背包问题（它优于其他方法）,但是提供低品质的结果。
家乐福正如所料,解决所有的暗箱操作的人并不好,因为那些获得专业,最著名的算法。
然而,他们可以广泛应用于二进制的过程中必须注意的问题
专业的SS算法考虑只能应用到一个特定的问题。
我们运用了多种相关测试非佛里德曼的样品,最好的解决方案得到每一4暗箱操作的方法。
这个测试计算,因为每个实例,等级的价值根据每个方法解的质量。
然后,它计算了每种方法的平均等级值在所有的情况下解决。
如果平均水平差异较大,相关的p-value和意义将会很小。
结果p-value0.000所获实验表明存在统计上的显著差异这四种方法进行测试。
4结论
我们已经描述了开发的一种搜索应用分散的问题的优化解的形式,给出了一个二元向量。
我们的实验结果是相当结论性的关于该方法的有效性,我们开发了。
在该方法的发展过程中,我们能够显示的优势,利用多种方法,同时减少不利影响的社区的大小改进的方法。
第一个改进策略应用到附近导致完整有效的利用搜索时间分配。
我们希望我们的经验将帮助软件开发者改进商业解决基于进化的过程。
5承认
本研究已部分支持CienciaeIn-novaci¶德、西班牙的（TIN2006-02696和TIN2009-07516）和马德里Comunidad国王胡安·卡洛斯-校长工程（URJC-CM-2008-CET-3731）。
在此感谢OptTek系统测试和运行OptQuest提供解决方案,我们用来比较。
参考文献
1.Campos,V.,Laguna,M.,Mart¶³,R.:
Context-independentscatterandtabusearch
forpermutationproblems.INFORMSJournalonComputing17
（1）,111{122（2005）
2.Duarte,A.,Mart¶³,R.:
Tabusearchforthemaximumdiversityproblem.European
JournalofOperationalResearch178,71{84（2007）
3.Gallego,M.,Duarte,A.,Laguna,M.,Mart¶³,R.:
Hybridheuristicsforthemaximum
diverstityproblem.ComputationalOptimizationandAppl.44,411-426（2009）
升级会员 