本文中的公开内容涉及优化设备、优化程序和优化方法。
背景技术：
诸如计算机的算术设备通过各种数据操作进行信息处理以产生有意义的输出，从而使得能够在现代社会的各个领域中进行预测、确定、控制等。优化处理是信息处理的分支。优化问题是找到属于搜索空间的、使搜索空间中限定的目标函数的值最小化(或最大化)的点(即，解)的问题。优化问题可以大致分为线性规划问题和离散优化问题。在离散优化问题的情况下，搜索空间维数的增加导致变量的组合的数目爆炸性增长。在这种情况下，使用计算所有可能的组合的穷举搜索需要很长的计算时间，这实际上是不可行的。
大规模多元离散优化问题可以通过下述方式来解决：通过基于近似解方法或启发式方法在现实可行的计算时间内找到良好的近似解而不是找到精确的最优解。基于启发式方法并且适用于各种问题的通用近似算法(元启发式算法)包括随机游走搜索算法、模拟退火算法、遗传算法、随机进化算法等。用于执行模拟退火的机制的示例包括使用伊辛能量函数的伊辛机(即，玻尔兹曼机)。在伊辛机中，将要解决的问题转化为表示磁性材料的自旋行为的伊辛模型，并且然后计算该问题的解。
上述近似算法被设计成使得将概率元素引入从初始状态——即，起点——执行的状态转变中，以搜索获得目标函数的连续较小值的解，从而使得状态能够收敛于接近最优解而不会陷入不利的局部最小值。仔细设计的概率元素的控制和足够长的计算时间的使用允许状态收敛于最优解或足够接近最优解的解。然而，在实际可行的计算时间内，并不总是容易获得足够接近最优解的解。对于每个优化问题，也难以设计对概率元素的适当控制。
为了减少搜索解所需的时间，例如，可以随机地设置初始状态，并且可以从不同的初始状态多次重复对解的搜索。即使在其中从给定初始状态开始的对解的搜索陷入目标函数的值不足够小的局部最小值的情况下，这种对解的搜索也可以在适当的时间终止，然后从不同的初始状态开始新的对解的搜索。这种安排使得能够从局部解中逃离，并且减少了获得最优解所需的时间，而不会在从初始状态开始的搜索中浪费时间以致陷入不利的局部解而结束或者在达到最优解之前需要很长的时间。
如在施加了约束条件的情况下，当问题的难度由于大量的局部解而高时，在不增加从局部解逃离的发生次数的情况下，即，在不增加从新的初始状态进行对解的搜索的次数的情况下，即使如上所述从不同初始状态迭代地执行对解的搜索，可能也无法获得令人满意的解。此外，随着越来越多地逃离局部解，随机生成的初始状态接近已经通过先前搜索找到的局部解的概率增加。在这种情况下，可能执行第二次收敛于该局部解的不必要的搜索。
因此，可以期望提供在从不同的初始状态重复对解的搜索时通过其设置适当的初始状态的机制。
[专利文献1]日本未审查专利申请公开第2014-178717号
[专利文献2]日本公开特许公报第2009-48353号
技术实现要素：
根据实施方式的一方面，一种优化设备包括：搜索单元，用于通过使用第一方法来执行对解的搜索，通过该第一方法，包括作为限制条件的约束的目标函数的值被概率性地改善；以及初始状态生成单元，用于生成第一状态，所述第一状态处于距由搜索单元获得的一个或更多个先前的解超过预定距离处；以及用于通过使用第二方法来获得局部解，通过该第二方法，执行从第一状态开始的状态转变，以满足约束并且与通过第一方法相比以更高的概率改善目标函数的值，然后输出局部解作为初始状态，其中，初始状态生成单元输出初始状态的处理和搜索单元基于第一方法从初始状态执行对解的搜索的处理被迭代地执行。
附图说明
图1是示出优化设备的功能配置的示例的图；
图2是示出由优化设备执行的优化方法的示例的图；
图3是示出实现优化设备的计算机的硬件配置的示例的图；
图4是示出根据第一实施方式的优化方法的过程的流程图；
图5是示出初始状态生成单元基于其获得局部解的算法的示例的流程图；
图6是示出约束的示例的图；
图7是示出约束的另一示例的图；
图8是示出约束的另一示例的图；
图9是示出根据第二实施方式的优化方法的过程的流程图；
图10是示出根据第三实施方式的优化方法的过程的流程图；
图11是示出根据第四实施方式的优化方法的过程的流程图；
图12a至图12c是示出取决于温度差的状态转变的差异的图；
图13是示出根据第五实施方式的优化方法的过程的流程图；
图14是示出根据第六实施方式的优化方法的过程的流程图；以及
图15是示出根据第七实施方式的优化方法的过程的流程图。
具体实施方式
以下，将参照附图描述本发明的实施方式。
图1是示出优化设备的功能配置的示例的图；图1所示的优化设备10包括问题输入单元11、搜索参数和初始状态输入单元12、问题约束输入单元13、搜索单元14和初始状态生成单元15。在图1中，被示出为框的功能块之间的边界基本上指示功能边界，并且可能不对应于物理位置的分离、电信号的分离、控制逻辑的分离等。优化设备可以具有通过组合具有各个功能块的功能的电子电路块来实现的硬件配置，或者可以具有其中各个功能块的功能由作为电子电路的通用处理器执行的软件来实现的软件配置。在硬件实现方式的情况下，每个功能块可以是在某种程度上与其他块物理上分离的硬件模块，或者可以指示其中该功能块和其他块物理上组合在一起的硬件模块中的功能。在软件实现方式的情况下，每个功能块可以是在某种程度上与其他块逻辑上分离的软件模块，或者可以指示其中该功能块和其他块逻辑上组合在一起的软件模块中的功能。
优化设备10执行通用近似算法，例如随机游走搜索算法、模拟退火算法、遗传算法、随机进化算法等。这些近似算法被设计成使得将概率元素引入从初始状态——即，起点——执行的状态转变中，以搜索获得目标函数的连续改善值的解，从而使得状态能够收敛于尽可能令人满意的解，而不会陷入不利的局部最小值。在遗传算法的情况下，例如，在其中用作目标函数值的种群的适应度在相继代中增加的过程中，以概率方式控制对对的选择、交叉、选择、突变等，从而避免陷入不利的局部解。在模拟退火算法的情况下，例如，以概率方式控制状态转变，以便即使目标函数的值由于给定的状态转变而恶化，也允许以一定的概率发生这种状态转变，从而避免陷入不利的局部解。
优化设备10要解决的优化问题通常使得相对于解存在一些约束。解应当满足的约束可以是将问题公式化时引入的条件。例如，在旅行商问题的情况下，目标是获得针对其代表整个路线的距离的目标函数的值为尽可能小的解，并且所述解需要满足的约束可以被设置为在给定时刻访问不超过一个城市而且每个城市恰好访问一次的条件。这些条件被公式化为以下约束，当访问时间和访问城市分别与二维矩阵中的行和列相关联时，每行和每列中仅一个条目为1。可以将满足上述约束时其值为零以及其值与不满足约束的程度成比例地增加的约束项添加至表示整个路线的距离的目标函数中，从而创建新的目标函数。然后，优化问题可以被公式化为使新的目标函数最小化的任务。
问题输入单元11从外部源接收如上所述被公式化的优化问题。例如，使用优化设备10的用户可以输入表示优化问题的公式类型的指示(例如，伊辛类型的指示)和公式中的参数的值。
搜索参数和初始状态输入单元12接收用于搜索关于优化问题的解的初始状态和参数。在模拟退火的情况下，例如，使用优化设备10的用户可以输入热噪声(即，温度)的初始值、热噪声(即，温度)降低的速率、以及初始状态(例如，所有位都为零的状态)等。
问题约束输入单元13从外部源接收指示对优化问题的解施加的约束的条件。在旅行商问题的情况下，例如，使用优化设备10的用户输入表示约束的表达式等。
在图1中，搜索单元14通过使用第一方法来执行对解的搜索，通过该第一方法，包括作为限制条件的约束的目标函数的值被概率性地改善。对解的搜索中使用的第一方法是通用近似算法，如先前描述的例如随机游走搜索算法、模拟退火算法、遗传算法、随机进化算法等。搜索单元14基于第一方法从连续不同的初始状态重复地执行对解的搜索。例如，对解的搜索可以迭代地执行t次，并且当获得了t个解时停止。然后，优化设备10可以输出t个解中的具有最有利的目标函数值的一个解作为最优解。
对解的重复搜索的使用使得能够从局部解中逃离，并且减少了获得最优解所需的时间，而不会在从初始状态开始的搜索中浪费时间以致陷入不利的局部解而结束或者在达到最优解之前需要很长的时间。在这种安排中，优选生成适当的初始状态，以便不执行收敛于已经由搜索单元14在过去获得的解的无意义搜索。
初始状态生成单元15从搜索单元14接收优化问题(即，限定问题的目标函数公式)和在先前的搜索中获得的解，并且基于接收到的信息生成适当的初始状态。具体地，初始状态生成单元15随机地生成第一状态，在该第一状态下，距由搜索单元14先前获得的任意解的距离(例如，汉明距离、曼哈顿距离或欧几里德距离)大于预定距离。在这样做时，可以参考过去获得的所有解，或者可以参考过去获得的解中的预定数目的最近解。初始状态生成单元15还通过使用第二方法获得局部解，通过该第二方法，执行从第一状态开始的状态转变，以确定地满足约束并且与第一方法相比以更高的确定性改善目标函数的值，然后输出所获得的局部解作为初始状态。
如上所述，在随机生成第一状态时，状态生成过程不必是完全随机的，而可以是伪随机的。伪随机过程可以是利用嵌入在计算机中的伪随机数生成函数的过程。可替选地，实现利用确定性算法来生成看起来好像随机生成的状态的过程，并且该过程被用于生成第一状态。
由初始状态生成单元15输出的初始状态被提供至搜索单元14。初始状态生成单元15和搜索单元14用于使得初始状态生成单元15输出初始状态的处理和搜索单元14基于第一方法从初始状态执行对解的搜索的处理迭代地执行。如前所述，在对解的每次搜索中使用的初始状态对应于通过从处于距先前获得的解超过预定距离处的第一状态改善目标函数的值而获得的局部解。因此，使用足够大的预定距离使得可以以高的概率避免下述情况：基于第一方法从初始状态开始对解的搜索收敛于先前获得的解之一而结束。
此外，第二方法通过执行从第一状态开始的状态转变来获得局部解，以确定地满足约束并且与第一方法相比以更高的确定性改善目标函数的值，然后提供所获得的局部解作为初始状态。因此，可以整体上提高对解的搜索的速度。即，更加确定地改善目标函数的值使得能够迅速地获得初始局部解。此外，以这样的方式执行搜索以确定地满足约束使得对解的下一阶段的搜索能够从存在于可行解(即，满足限制条件的解)的域内的有利初始状态开始。
由初始状态生成单元15执行的第二方法可以执行状态转变，使得确定地满足约束并且使得目标函数的值单调地增加。即，贪婪方法的构思可以用作用于沿朝着目标函数的值的确定性改善的方向以确定性的方式(即，没有概率元素)执行状态转变的基础。当获得在其处目标函数的值无法进一步改善的局部解时，可以将这种局部解作为初始状态提供至搜索单元14。这确保了通过确定地改善目标函数的值来获得初始局部解所需的时间进一步减少。
当由初始状态生成单元15生成的局部解与由搜索单元14先前获得的任意解之间的距离小于预定阈值时，初始状态生成单元15可以重复随机生成第一状态并且基于第二方法获得局部解的过程，以获得新的局部解。即，当局部解与过去获得的任意解之间的距离相对小时，基于第二方法从与该局部解对应的初始状态开始的对解的搜索可能收敛于过去获得的同一解。因此，在这种情况下，可以重新计算新的局部解。以这种方式，迅速地执行改善目标函数的值的过程中的初始步骤，以确定初始局部解在较早的时间点的位置。在其中局部解与过去获得的任意解相对接近的情况下，重新计算新的初始状态来以更高的确定性避免不必要的对解的搜索。
图2是示出由优化设备执行的优化方法的示例的图。可以注意到，在图2和随后的流程图中，执行流程图所示的步骤的顺序仅是示例。所公开技术的范围不限于所公开的顺序。例如，描述可以说明在执行b步骤之前执行a步骤。尽管有这样的描述，但是在物理上和逻辑上可以在a步骤之前执行b步骤，也可以在b步骤之前执行a步骤。在这种情况下，无论首先执行哪个步骤，影响流程图的结果的所有后果都可能是相同的。于是，由此可见，出于所公开的技术的目的，显然可以在执行a步骤之前执行b步骤。尽管说明了在b步骤之前执行a步骤，但是这样的描述不旨在将如上所述的明显情况置于所公开的技术的范围之外。这种明显的情况不可避免地落入本公开内容意图技术的范围内。
以下，将参照其中关于伊辛型优化问题通过模拟退火来执行对解的搜索的具体示例来描述优化方法及其实施方式。在该具体示例中，目标函数可以为如下式表示的伊辛能量e(s)。
e(s)＝-σwijxixj-σbixi(1)
s为如下具有l个自旋(l：正整数)的状态。
s＝(x1,x2,...,xl)(2)
每个自旋假定值为-1或 1或者值为0或 1。wij为用于自旋之间的耦合的加权因子，并且可以使得wij<i＝j>＝0。此外，bj为偏置。在式(1)的右侧，第一个∑项表示在从1至l的整个范围内关于i与j之间的所有组合的总和。第二个∑项表示在从1至l的整个范围内关于i的总和。
式(1)可以已经包含表示约束的项。如果包括约束，则wij<i＝j>可能不为零。对解的搜索等同于找到其中上述能量尽可能低的状态。
在图2的步骤s1中，输入伊辛问题。具体地，问题输入单元11从外部源接收指定伊辛问题的信息。所述信息包括指示优化问题为上述式(1)的形式、状态s中的自旋数目l、加权因子wij的值以及偏差bi的值的信息。
在步骤s2中，设置输入参数和状态。具体地，搜索参数和初始状态输入单元12接收指示初始状态的信息和指示用于对解的搜索的参数的信息。所述信息包括热噪声(即，温度)的初始值、热噪声(即，温度)降低的速率、初始状态(例如，表示自旋的所有位都为零的状态)和搜索计数限制t等。
在步骤s55中，执行对解的搜索。具体地，搜索单元14基于状态转变导致的能量e(s)的值的变化来控制从当前状态向位于当前状态附近的下一状态的每个状态转变，从而找到其中能量e(s)的值尽可能低的状态s。
更具体地，搜索单元14计算当前状态s的能量值e，并且计算通过从当前状态s进行微小变化(例如，1位反转)而获得的下一状态s'的能量值e'，然后计算这两个状态之间的差δe(＝e'-e)。例如，在其中使用玻尔兹曼分布表示s的概率分布和使用metropolis方法的情况下，可以通过下式来限定发生向下一状态s'的转变的概率p。
p＝min[1,exp(-βδe)](3)
此处，β是热力学β(即，绝对温度的倒数)。函数min[1，x]假定值为1或值为x，以较小者为准。根据上式，在δe≦0的情况下，以概率“1”发生向下一状态的转变，并且在0<δe的情况下，以概率exp(-βδe)发生向下一状态的转变。
在执行状态转变的同时以足够慢的速率降低温度，理论上可以使状态收敛于具有最小能量值的最优解。metropolis方法是非限制性示例，并且可以可替选地使用其他转变控制算法，例如吉布斯采样。搜索单元14可以根据概率p确定是否进行向下一状态的状态转变。
当满足确定标准时，搜索单元14结束对解的搜索。确定标准可以要求执行了针对状态转变的预定数目的计算，或者可以要求能量值的变化小于或等于预定阈值。每当搜索单元14执行对解的搜索并且结束搜索时，就获得一个新的解。
在步骤s4中，进行终止检查。具体地，搜索单元14检查是否执行了与指定的搜索计数限制t相等的次数的对解的搜索，从而获得t个解。如果尚未获得t个解，则过程进行至步骤s5。
在步骤s5中，基于先前的解和关于问题的约束生成初始状态。具体地，初始状态生成单元15随机地生成处于距先前通过搜索单元14获得的任意解超过预定距离处的第一状态。初始状态生成单元15还通过使用第二方法获得局部解，通过该第二方法，执行从第一状态开始的状态转变，以确定地满足约束并且与第一方法相比以更高的确定性减小能量值，然后输出所获得的局部解作为初始状态。
当通过使用第二方法执行状态转变时，初始状态生成单元15可以使状态s的一个或更多个位反转，以找到满足约束的下一状态候选，并且可以从这些候选中选择使能量减少的下一状态s′。作为一般原理，状态转变可以被执行成使得能量以确定的方式减少。然而，可以注意到，在确定局部解之前执行的过程中可以引入一些概率元素。例如，当针对下一状态候选中的任意状态候选能量没有减少时，可以以一定的概率执行向候选之一的转变。可替选地，一旦以给定的次数执行了状态转变，就可以以一定的概率允许向使能量增加的状态的转变。
在步骤s5中获得要用作初始状态的局部状态后，过程返回至步骤s3，并且将再次执行步骤s3和随后步骤中的处理。在这种情况下，在步骤s3中执行的对解的搜索从由初始状态生成单元15在步骤s5中获得的初始状态开始。
在完成对解的搜索之后，在步骤s4中进行终止检查。如果该检查指示已经获得了t个解，则过程进行至步骤s6。在步骤s6中，搜索单元14输出在t个解中具有最低能量值的解作为最优解。
图3是示出当优化设备被实现为执行软件的处理器时的计算机的硬件配置的示例的图。
如图3所示，用于执行如上所述的优化方法的优化设备被实现为计算机，例如个人计算机、工程工作站等。图3的设备包括计算机20、连接至计算机20的显示设备30、通信设备33和输入设备。输入设备包括键盘31和鼠标32。计算机20包括cpu21、ram22、rom23、辅助存储装置24例如硬盘、可移动介质存储装置25和接口26。
键盘31和鼠标32提供用户接口，并且接收用于操作计算机20的各种指令和响应于数据请求的用户响应等。显示设备30显示由计算机20处理的结果，并且还显示使用户能够与计算机20通信的各种数据。通信设备33提供与外围设备或与远程站点进行的通信，并且通信设备33可以包括调制解调器、网络接口、usb(通用串行总线)等。
提供用于实现优化方法的功能作为可由计算机20执行的计算机程序。该计算机程序存储在可安装至可移动介质存储装置25的存储介质m中。计算机程序通过可移动介质存储装置25从存储介质m加载至ram22或辅助存储装置24。可替选地，计算机程序可以存储在外围设备或远程存储介质(未示出)中，并且通过通信设备33和接口26从远程存储介质加载至ram22或辅助存储装置24。
当通过键盘31和/或鼠标32输入用于程序执行的用户指令时，cpu21将程序从存储介质m、外围设备、远程存储介质或辅助存储装置24加载至ram22。cpu21通过使用ram22的可用存储空间作为工作区域来执行加载至ram22的程序，并且在出现这种需要时在与用户通信的同时继续处理。rom23在其中存储出于控制计算机20的基本操作的目的的控制程序。
通过如上所述执行计算机程序，计算机20执行如前所述的优化方法。
图4是示出根据第一实施方式的优化方法的过程的流程图。在步骤s11中，输入伊辛问题。具体地，问题输入单元11从外部源接收指定伊辛问题的信息，类似于先前描述的步骤s1。
在步骤s12中，根据对解的搜索中使用的方法来设置输入参数和初始状态。具体地，搜索参数和初始状态输入单元12接收指示初始状态的信息和指示用于对解的搜索的参数的信息，类似于先前描述的步骤s2。所述信息包括热噪声(即，温度)的初始值、热噪声(即，温度)降低的速率、初始状态(例如，表示自旋的所有位都为零的状态)、搜索计数限制t、指示预定距离的阈值a、参考的解的数目n等。
在步骤s13中，搜索单元14基于已经设置的输入参数和初始状态执行对解的搜索，从而获得具有小目标函数(能量)值的状态作为解。具体地，搜索单元14基于由状态转变导致的能量的值的变化来控制从当前状态向位于当前状态附近的下一状态的每个状态转变，从而找到其中能量的值尽可能低的状态，类似于先前描述的步骤s3。当满足确定标准时，搜索单元14结束对解的搜索。例如，确定标准可以要求已经执行了针对状态转变的预定次数的计算。在对解的搜索结束时的状态s是在步骤s13中获得的解。
在步骤s14中，搜索单元14检查已经执行的对解的搜索的次数是否超过预设的计数限制t。如果尚未获得t个解(在“否”的情况下)，则过程进行至步骤s15。
在步骤s15中，初始状态生成单元15保持随机地生成状态，直到生成数目a个或更多个位与先前对解的n次搜索中获得的n个解中的任意一个解不同的状态。在这样做时，当过去执行的对解的搜索的次数小于n时，可以使用通过这些先前执行的对解的搜索获得的所有解。当过去执行的对解的搜索的次数大于n时，可以使用通过先前执行的对解的搜索获得的所有解中的n个最近的解。
初始状态生成单元15还通过执行从所生成的状态开始的状态转变来获得局部解，以确定地满足约束并且与解搜索算法的情况相比以更高的确定性改善目标函数(即，能量)的值，然后输出所获得的局部解作为初始状态。在这样做时，可以单调地改善目标函数的值(即，能量单调减少)，以确定地减少目标函数(即，能量)的值。在步骤s16中获得要被用作初始状态的局部状态时，过程返回至步骤s13，并且将再次执行步骤s13和随后步骤中的处理。在这种情况下，在步骤s13中执行的对解的搜索从由初始状态生成单元15在步骤s16中获得的初始状态开始。
在完成对解的搜索之后，在步骤s14中进行终止检查。如果该检查指示已经获得了t个解(在“是”的情况下)，则过程进行至步骤s17。在步骤s16中，搜索单元14输出t个解中具有最低目标函数值(即，最低能量值)的解作为最优解。
还可以注意到，在先前描述的步骤s14中，搜索单元14检查执行的对解的搜索的次数是否超过预设的计数限制t。即，当通过第一方法执行的对解的搜索的次数达到预定的计数限制t加1时，搜索单元14终止对解的迭代搜索。代替检查计数，搜索单元14可以在用于通过第一方法执行的对解的迭代搜索的总累积时间达到预定时间量时终止对解的迭代搜索。以这样的方式，可以根据搜索计数或搜索时间终止对解的迭代搜索，这使得能够在期望的时间段内可靠地获得解。
图5是示出初始状态生成单元基于其获得局部解的算法的示例的流程图。该流程图所示的处理对应于结合图2描述的优化方法的第二方法，并且该流程图所示的处理也对应于图4中步骤s16的处理，即，执行状态转变以确定地满足约束并且与第一方法的情况相比以更高的确定性改善能量的值的方法。
在步骤s21中，输入问题、问题的约束以及通过基于解生成状态的处理获得的状态。具体地，初始状态生成单元15从搜索单元14接收表示经公式化的优化问题的表达式、表示关于解的约束的表达式(即，条件)以及过去获得的解。可以注意到，在图4的步骤s15中，初始状态生成单元15随机地生成相对于先前的n个解的满足预定距离条件(即，数目a个或更多个位为不同)的状态。
在步骤s22中，初始状态生成单元15通过改变通过基于先前获得的解生成状态的处理而获得的状态的所有位中的在1与m之间的预定数目的位来生成状态，并且从这些生成的状态中选择满足问题约束的一个或更多个状态，作为用于下一搜索的候选。m是比状态中包含的位的总数(l)足够小的数字，并且m是使得通过从当前状态反转m位而获得的状态可以被视为位于当前状态的附近的数字。
此后将考虑下述示例，在该示例中，例如构成状态的l个位被均等地划分为10个组，并且约束要求假定值为“1”的位数在每个组中恰好为1。如果在状态转变中要改变的位数被设置为1，则无论从满足约束的当前状态中选择并反转哪一个位，都会违反每个组中恰好1位为1的条件。另一方面，如果在状态转变中要改变的位数被设置为2，则当从满足约束的当前状态中选择并反转一个位并且然后在与经反转的位相同的组中反转值为1的位时，仍然满足每个组中恰好1位为1的条件。在步骤s22中，改变在一个位与m个位之间的预定数目的位(例如，2个位)，以生成满足约束的所有状态。所生成的状态用作用于下一搜索的候选。
在步骤s23中，初始状态生成单元15计算关于候选中的每个候选的目标函数(即，能量)的值。
在步骤s23中，初始状态生成单元15在候选中选择具有目标函数的值(即，能量值)的最大减小的候选(如果存在这样的候选)。在其中没有候选具有减少的能量的情况下，初始状态生成单元15可以以概率p(0≦p<1)终止处理，或者以随机方式或以响应于目标函数值(即，能量值)的差异的概率从候选中选择用于下一搜索的状态。例如，可以生成随机数r(0≤r≤1)，并且如果随机数r的值小于或等于p，则终止处理。在其中随机数r的值大于p的情况下，可以从候选中随机地选择状态，并且该状态可以用作用于下一搜索的状态。可替选地，在其中随机数r的值大于p的情况下，可以以响应于能量差δe的概率(例如，由δe指示的能量增加越小，选择的概率越大)来选择状态，并且可以将所选择的状态用作用于下一搜索的状态。
在步骤s25中，初始状态生成单元15检查是否作出了终止处理的选择，即，是否确定了局部解。如果未作出终止处理的选择(在“否”的情况下)，则过程返回至步骤s22，并且将再次执行步骤s22和随后步骤中的处理。可以注意到，当再次执行步骤s22的处理时，使用在步骤s24中获得的用于下一搜索的状态作为当前状态，并且通过从当前状态改变1至m个位的值来获得用于再下一搜索的候选。
如果步骤s25中的检查指示作出了终止处理的选择(在“是”的情况下)，则过程进行至步骤s26。在步骤s26中，输出在终止步骤s24中的处理时进行搜索的状态(即，从其起能量不进一步减少的局部解状态)作为用于要由搜索单元14执行的对解的搜索的初始状态。
如果步骤s25中的检查指示作出了终止处理的选择(在“是”的情况下)，则过程进行至步骤s26。在步骤s26中，输出在终止步骤s24中的处理时进行搜索的状态(即，从能量不进一步减少的局部解状态)作为用于要由搜索单元14执行的对解的搜索的初始状态。
图6是示出约束的示例的图。图6所示的约束可以用作图4所示的优化方法的第一实施方式中的约束。
在图6所示的示例中，将20位长的状态均等地划分为4个组(即，图6所示的4行)，每个组为5位长。所述约束要求每个组中恰好一个位的值为1。即，要求图6所示的4行中的每一行中值为1的位的数量恰好为1的条件。
更一般的说，其长度为α位的倍数的l位长的状态可以被划分为长度均为α位的组。在这种情况下，对于每个组，表示在每个组中值为1的位的数量恰好为1的约束项由以下式表示。
(σxi-1)2(4)
在上面的式中，符号“∑”是指感兴趣的组中α个位的值的总和(遍及从1至α的每个i)。当感兴趣的组满足约束时，式(4)所示的约束项的值为零，并且随着违反约束的程度增加，式(4)所示的约束项的值增加。
可以将由式(4)表示的针对各个组的约束项均乘以预定系数，并且然后可以将其添加至伊辛表达式，从而创建表示包含约束的优化问题的目标函数(即，能量)的表达式。搜索单元14搜索解，以尽可能地降低上面限定的能量，这使得能够找到具有降低的能量的解，同时以一定的确定性确保解满足约束。为了增加满足约束的概率，可以将上述系数设置为足够大的值。可以注意到，当初始状态生成单元15搜索局部解时，初始状态生成单元15不仅搜索以降低上述能量，而且如结合图5描述的，仅选择满足约束的状态作为用于进一步搜索的状态，由此使得约束被明确地满足。
图7是示出约束的另一示例的图。图7所示的约束可以用作图4所示的优化方法的第一实施方式中的约束。在图6所示的示例中，17位长的状态被划分为具有不同位长度的组，这些组被表示为4个组g1至g4，其中约束要求每个组中恰好一位的值为1。即，要求在图7所示的组g1至g4中的每个组中值为1的位的数量恰好为1的条件。约束项的生成和针对上述约束的目标函数表达式的生成可以类似于图6所示的约束进行。
图8是示出约束的另一示例的图。图8所示的约束可以用作图4所示的优化方法的第一实施方式中的约束。在图8所示的示例中，25位长的状态被均等地划分为5个组(即，图8中所示的5行)，每个组为5位长。约束要求每行(即，每组)中恰好一位的值为1，并且每列中恰好一位的值为1。即，要求下述条件：在图8所示的5行中的每行中值为1的位的数量恰好为1，并且在5列中的每列中值为1的位的数量恰好为1。可以通过针对每行和每列限定与先前描述的式(4)相同的式来生成限制项，所述限制项表示在每行(即，每组)中值为1的位的数量恰好为1并且在每列中值为1的位的数量恰好为1。可以将针对每行和每列生成的约束项乘以预定系数，并且然后可以将其添加至伊辛表达式，从而创建表示包含约束的优化问题的目标函数(即，能量)的表达式。
图9是示出根据第二实施方式的优化方法的过程的流程图。根据第二实施方式的优化方法与图4所示的第一实施方式的优化方法的不同之处仅在于存在附加步骤s30。关于在其他步骤中执行的处理，第一实施方式与第二实施方式之间基本上不存在差异。然而，可以注意到，在步骤s12中设置的输入参数包括与距离有关的附加阈值b。
在图9中，在步骤s16获得要用作初始状态的局部解之后执行步骤s30。在步骤s30中，初始状态生成单元15检查所获得的局部解与先前获得的n个解中的任意一个解之间的距离是否小于阈值b。如果该距离小于阈值b(在“是”的情况下)，则过程返回至步骤s15，并且将再次执行步骤s15和随后步骤中的处理。如果该距离大于或等于阈值b(在“否”的情况下)，则过程返回至步骤s13，并且通过使用在步骤s16中生成的初始状态来执行对解的搜索。在如上所述的第二实施方式中，可以根据需要重新计算要用作初始状态的局部解，使得可以获得处于距n个先前解超过阈值b的距离处的足够好的初始状态。利用这样的安排，可以更可靠地避免可能收敛于已获得的解而结束的不必要的对解的搜索。
图10是示出根据第三实施方式的优化方法的过程的流程图。根据第三实施方式的优化方法与图9所示的第二实施方式的优化方法的不同之处仅在于，步骤s15和步骤s30分别被替代为步骤s15a和步骤s30a。关于在其他步骤中执行的处理，第二实施方式与第三实施方式之间基本上不存在差异。
在图10的步骤s15a中，初始状态生成单元15保持随机地生成状态，直到生成数目为a或大于a的位与先前对解的n次搜索的n个解和n个初始值中的任意一者不同的状态。即，在随机生成状态的处理中，在距离确定中不仅使用过去的n个解，而且还使用过去的n个初始状态。
此外，在图10的步骤s30a中，初始状态生成单元15检查所获得的局部解与过去的解和过去的初始状态中的任意一者之间的距离是否小于阈值b。即，同样，在检查所获得的局部解是否令人满意的处理中，在基于阈值的确定中不仅使用过去的n个解，而且还使用过去的n个初始状态。
在如上所述的第三实施方式中，初始状态生成单元15获得处于距先前获得的解并且也距先前从初始状态生成单元15输出的初始状态超过预定距离处的第一状态。此外，当基于第一状态获得的局部解与过去获得的解和过去输出的初始状态中的任意一者之间的距离小于预定阈值时，初始状态生成单元15再次执行获得局部解的处理，从而获得新的局部解。以这样的方式，当确定在对解的下一搜索中使用的初始状态时，不仅参考先前获得的解，而且还参考先前获得的初始状态。这种安排用于避免执行与过去执行的搜索相同或相似的对解的搜索。因此，当迭代地执行对解的搜索时，可以尽可能从彼此不同的各个初始状态执行对解的搜索，从而使得能够在短时间内搜索更接近最优解的解。
图11是示出根据第四实施方式的优化方法的过程的流程图。根据第四实施方式的优化方法与图4所示的第一实施方式的优化方法的不同之处仅在于存在附加步骤s40。关于在其他步骤中执行的处理，第一实施方式与第四实施方式之间基本上不存在差异。然而，可以注意到，在步骤s12中设置的输入参数包括与距离有关的附加阈值b。
在图11中，在步骤s16获得要用作初始状态的局部解之后执行步骤s40。在步骤s40中，当过去的n个解均未处于距局部解小于阈值b的距离处时，初始状态生成单元15使用默认的解搜索参数。当存在处于小于阈值b的距离处的解时，解搜索参数被设置为在与这样的解对应的对解的搜索中尚未使用的值。
在如上所述的第四实施方式中，当局部解与先前获得的解中的任意一个解之间的距离小于预定阈值时，搜索单元14基于与默认值不同的解搜索参数执行对解的搜索。例如，热噪声(即，温度)的初始值和热噪声(即，温度)降低的速率中的至少之一可以被设置为与在步骤s12中设置的值不同的值，以执行对解的搜索。
图12a至图12c是示出取决于温度差的状态转变的差异的图。在图12a至图12c中，水平轴示意性地表示状态s在一维中的分布，并且纵轴表示针对每个状态的能量e。箭头41至43示意性地指示状态转变时能量可以变化的量。根据先前描述的式(3)可以理解，温度越高(即，热力学贝塔β越低)，状态转变导致大的能量变化的概率越高。在图12a中，温度高，并且如箭头41所指示的，在状态转变时可能发生大的能量变化。在图12b中，温度中等，并且在状态转变时可能发生中等的能量变化。在图12c中，温度低，并且在状态转变时可能仅发生小的能量变化。
当搜索解时，温度从高温(即，如图12a所示)逐渐降低至低温(即，如图12c所示)。这样的降低使得能够获得接近最优解的解，而不会陷入能量高的局部解。在这样的过程中，温度的初始值和温度降低的速率(更具体地，温度下降曲线的形状和斜率)中的至少之一的变化导致对解的搜索的行为被显著改变。结果是，即使从相同的初始状态开始，搜索也可能收敛于完全不同的解。
在第四实施方式中，当要用作初始状态的局部解与先前获得的解中的任意一个解之间的距离小于预定阈值时，基于与默认值不同的解搜索参数来执行对解的搜索。利用这样的安排，即使从与在先前执行的对解的搜索中使用的初始状态类似的初始状态来执行对解的新的搜索，也可以通过与先前对解的搜索中的搜索路径完全不同的搜索路径来获得完全不同的解。即，可以避免执行与先前执行的对解的搜索相同或相似的对解的搜索，从而使得能够在更短的时间内找到更接近最优解的解。
图13是示出根据第五实施方式的优化方法的过程的流程图。根据第五实施方式的优化方法与图11所示的第四实施方式的优化方法的不同之处仅在于，步骤s40被替代为步骤s40a。关于在其他步骤中执行的处理，第四实施方式与第五实施方式之间基本上不存在差异。然而，可以注意到，在步骤s12中设置的输入参数包括与搜索计数限制有关的附加阈值c。
在图13的步骤s40a中，当过去的n个解均未处于距局部解小于阈值b的距离处时，初始状态生成单元15使用默认的解搜索参数。当存在处于小于阈值b的距离处的解时，解搜索参数被设置为在与这样的解对应的对解的搜索中尚未使用的值。此外，在将解搜索参数设置为在相应的对解的搜索中尚未使用的值的情况下，当在第c次先前搜索处或在第c次先前搜索之前获得n个先前的解中具有最小目标函数值的解时，初始状态生成单元15使用解搜索参数的设置例如以扩展搜索范围。
如上所述的第五实施方式使得在改变解搜索参数的情况下，当在预定数目的搜索之前获得先前获得的解中具有最小目标函数值的解时，解搜索参数被设置为与默认值不同的值，例如以扩展对解的搜索的搜索范围。第四实施方式仅执行与先前的对解的搜索不同的对解的搜索。相比之下，与先前的对解的搜索相比，第五实施方式使得可以执行用于扩展搜索范围的对解的搜索。例如，可以增加温度的初始值，或者可以降低温度降低的速率(即，通过减小温度下降的斜率)，使得对解的搜索的范围被扩大。当在超过预定数目的搜索之前获得在过去获得的最令人满意的解时，进行这种用于扩展搜索范围的设置的更改。如果在获得最令人满意的解之后的特定持续时间内无法获得进一步改善的解，则存在解搜索参数可能不合适的可能性。在这种情况下，使用将扩大搜索范围的设置而不是简单地更改解搜索参数可能是合理的。
在上述第五实施方式中，在当前情况不允许容易地获得令人满意的解的情况下，对解搜索参数进行修改，例如以便利用将在比先前的对解的搜索中的范围更广的范围内进行搜索的搜索路径，并且同时，优选地修改解搜索参数。利用这样的安排，即使从与先前的初始状态类似的初始状态执行对解的新的搜索，也可以通过将在比先前的对解的搜索中的范围更广的范围内进行搜索的搜索路径来获得完全不同的解。即，与先前执行的对解的搜索相比，可以执行覆盖更宽范围的对解的搜索，从而使得能够在更短的时间内找到更接近最优解的解。
图14是示出根据第六实施方式的优化方法的过程的流程图。根据第六实施方式的优化方法与图4所示的第一实施方式的优化方法的不同之处仅在于存在附加步骤s50。关于在其他步骤中执行的处理，第一实施方式与第六实施方式之间基本上不存在差异。然而，可以注意到，在步骤s12中设置的输入参数包括与距离有关的附加阈值d。
在图14中，在随机地生成满足预定距离条件的状态的步骤s15之后执行步骤s50。在步骤s50中，初始状态生成单元15检查先前使用的任意初始状态与通过实现目标函数值(即，能量)从所生成的状态基本上单调增加的搜索而获得的状态(即，最大点)之间的距离是否小于阈值d。如果该距离小于阈值d(在“是”的情况下)，则过程返回至步骤s15，并且将再次执行步骤s15和随后步骤中的处理。如果该距离大于或等于阈值d(在“否”的情况下)，则过程进入至步骤s16。此处，表述“实现基本上单调增加的搜索”旨在表示可以毫无问题地引入一些概率元素。通常，可以进行搜索以通过实现单调能量增加来找到最大点。即，可以使用贪婪方法来找到最大点。
在上述第六实施方式中，通过实现目标函数值的单调恶化的搜索来获得最大点，并且当最大点处的状态与先前输出的任意初始状态之间的距离小于预定阈值时，再次执行随机生成状态的处理以找到新的状态。即使最初获得的第一状态处于距先前的解的足够距离处，通过从这样的第一状态爬升而到达的最大点的状态也可能接近先前的初始状态。在这种情况下，第一状态和先前的初始状态可以仅间隔一个峰值左右。在这种情况下，通过避免陷入局部解而执行的对解的搜索可能接近先前的初始状态，从而作为浪费的搜索而结束。因此，生成新的第一状态可以是优选的，以消除这种风险。利用这样的安排，可以更可靠地避免可能收敛于已获得的解而结束的不必要的对解的搜索。
图15是示出根据第七实施方式的优化方法的过程的流程图。根据第七实施方式的优化方法与图14所示的第六实施方式的优化方法的不同之处仅在于存在附加步骤s60。关于在其他步骤中执行的处理，第六实施方式与第七实施方式之间基本上不存在差异。
在图15中，在获得局部解的步骤s16之后执行步骤s60。在步骤s60中，初始状态生成单元15检查先前使用的任意初始状态与通过实现目标函数值(即，能量)从获得的局部解基本上单调增加的搜索而获得的状态(即，最大点)之间的距离是否小于阈值d。如果该距离小于阈值d(在“是”的情况下)，则过程返回至步骤s15，并且将再次执行步骤s15和随后步骤中的处理。如果该距离大于或等于阈值d(在“否”的情况下)，则过程进入至步骤s13。此处，表述“实现基本上单调增加的搜索”旨在意指可以毫无问题地引入一些概率元素。通常，可以进行搜索以通过实现单调能量增加来找到最大点。即，可以使用贪婪方法来找到最大点。在步骤s50中使用的阈值和在步骤s60中使用的阈值可以相同，或者可以彼此不同。
在上述第七实施方式中，通过实现目标函数值从局部解单调恶化的搜索来获得第二最大点，并且当第二最大点处的状态与先前输出的任意初始状态之间的距离小于预定阈值时，再次执行生成状态的处理以找到新的状态。即使最初获得的局部解处于距先前的解的足够距离处，通过从这样的局部解爬升而到达的最大点的状态也可能接近先前的初始状态。在这种情况下，局部状态和先前的初始状态可以仅间隔一个峰值左右。在这种情况下，通过避免陷入局部解而执行的对解的搜索可能接近先前的初始状态，从而作为浪费的搜索而结束。因此，生成新的状态以找到新的局部解可以是优选的，以消除这种风险。利用这样的安排，可以更可靠地避免可能收敛于已获得的解而结束的不必要的对解的搜索。
根据至少一个实施方式，当从不同的初始状态重复对解的搜索时，设置适当的初始状态。
1.一种优化设备，包括：
搜索单元，用于通过使用第一方法来执行对解的搜索，通过所述第一方法，包括作为限制条件的约束的目标函数的值被概率性地改善；以及
初始状态生成单元，用于生成第一状态，所述第一状态处于距由所述搜索单元获得的一个或更多个先前的解超过预定距离处；以及用于通过使用第二方法来获得局部解，通过所述第二方法，执行从所述第一状态开始的状态转变，以满足所述约束并且与通过所述第一方法相比以更高的概率改善所述目标函数的值，然后输出所述局部解作为初始状态，
其中，所述初始状态生成单元输出所述初始状态的处理和所述搜索单元基于所述第一方法从所述初始状态执行对解的搜索的处理被迭代地执行。
2.根据权利要求1所述的优化设备，其中，所述搜索单元用于当基于所述第一方法对解的迭代搜索的总次数达到预定计数时，或者当基于所述第一方法对解的迭代搜索的累积时间达到预定时间量时，终止基于所述第一方法对解的迭代搜索。
3.根据权利要求1所述的优化设备，其中，所述第二方法执行状态转变，使得满足所述约束并且使得所述目标函数的值单调地增加。
4.根据权利要求1至3中任一项所述的优化设备，其中，当所述局部解与所述一个或更多个先前的解中的任意一个解之间的距离小于预定阈值时，所述初始状态生成单元重复生成所述第一状态并且基于所述第二方法获得局部解的处理，从而获得新的局部解。
5.根据权利要求4所述的优化设备，其中，所述初始状态生成单元用于获得所述第一状态，使得所述第一状态处于距由所述搜索单元获得的所述一个或更多个先前的解超过所述预定距离处，并且使得所述第一状态处于距先前输出的每个所述初始状态超过所述预定距离处，并且
其中，当基于所述第一状态获得的所述局部解与所述一个或更多个先前的解和先前输出的每个所述初始状态中的任意一个之间的距离小于所述预定阈值时，所述初始状态产生单元重复生成所述第一状态并且基于所述第二方法获得局部解的处理，从而获得新的局部解。
6.根据权利要求1至3中任一项所述的优化设备，其中，当所述局部解与所述一个或更多个先前的解中的任意一个解之间的距离小于预定阈值时，所述搜索单元基于所述第一方法通过使用与默认值不同的解搜索参数来执行对解的搜索。
7.根据权利要求6所述的优化设备，其中，当所述局部解与所述一个或更多个先前的解中的任意一个解之间的距离小于所述预定阈值并且在所述一个或更多个先前的解中具有最小的目标函数值的解在超过预定次数的搜索之前获得时，所述搜索单元基于所述第一方法通过使用与默认值不同并且被设置成扩大对解的搜索的搜索范围的解搜索参数来执行对解的搜索。
8.根据权利要求1所述的优化设备，其中，所述初始状态生成单元用于通过执行实现所述目标函数的值从所述第一状态单调恶化的搜索来获得具有不利的所述目标函数的值的极值，并且所述初始状态生成单元用于当所述极值处的状态与先前输出的每个所述初始状态之间的距离小于预定阈值时，重复生成第一状态的处理，以获得新的第一状态。
9.根据权利要求8所述的优化设备，其中，所述初始状态生成单元用于通过执行实现所述目标函数的值从所述局部解单调恶化的搜索来获得具有不利的所述目标函数的值的第二极值，并且所述初始状态生成单元用于当所述第二极值处的状态与先前输出的每个所述初始状态之间的距离小于预定阈值时，重复生成第一状态的处理，以获得新的第一状态。
10.一种存储在计算机可读记录介质中的用于使计算机执行下述过程的程序：
通过使用第一方法来执行对解的搜索，通过所述第一方法，包括作为限制条件的约束的目标函数的值被概率性地改善；
生成第一状态，所述第一状态处于距先前通过所述对解的搜索获得的一个或更多个解超过预定距离处，以及通过使用第二方法来获得局部解，通过所述第二方法，执行从所述第一状态开始的状态转变，以满足所述约束并且与通过所述第一方法相比以更高的概率改善所述目标函数的值，然后输出所述局部解作为初始状态；以及
迭代地执行输出所述初始状态的处理和基于所述第一方法从所述初始状态执行所述对解的搜索的处理。
11.一种优化方法，包括：
通过使用第一方法来执行对解的搜索，通过所述第一方法，包括作为限制条件的约束的目标函数的值被概率性地改善；
生成第一状态，所述第一状态处于距先前通过所述对解的搜索获得的一个或更多个解超过预定距离处，以及通过使用第二方法来获得局部解，通过所述第二方法，执行从所述第一状态开始的状态转变，以满足所述约束并且与通过所述第一方法相比以更高的概率改善所述目标函数的值，然后输出所述局部解作为初始状态；以及
迭代地执行输出所述初始状态的处理和基于所述第一方法从所述初始状态执行所述对解的搜索的处理。
技术总结