信息处理装置、信息处理方法和计算机可读存储介质与流程

1.本文讨论的实施方式涉及信息处理装置、信息处理方法以及存储信息处理程序的非暂态计算机可读存储介质。


背景技术：

2.组合优化问题存在于当今社会的各个领域。例如，在制造/分配、销售等领域中，搜索优化成本或使成本最小化的元素的组合。然而，因为计算时间随着与上述元素对应的变量的数目的增加而指数地增加，因此组合优化问题被认为是难以用常规的冯诺依曼计算机求解的问题。
3.作为用于求解冯诺依曼计算机不擅长的多变量优化问题的方法，存在使用伊辛型能量函数的优化装置。这种优化装置也被称为伊辛机、玻尔兹曼机等。此外，能量函数也可以被称为成本函数或目标函数。优化装置通过用伊辛模型代替要计算的问题来执行计算，伊辛模型是表示磁性材料的自旋行为的模型。
4.作为用于使用伊辛模型的最小值获得问题的计算方法，存在用于通过使用马尔可夫链蒙特卡罗(mcmc)获得伊辛型能量函数的最小值的方法。在mcmc方法中，通常的做法是执行状态转变，即根据玻尔兹曼分布的转变概率来更新能量函数的状态变量。在mcmc方法中，通过以概率方式反转表示状态的位串中的任何位来执行搜索，并且基于从当前状态转变至邻近状态的情况下的能量差来确定是否可以进行转变。伊辛型能量是二进制变量的二次系统的能量。
5.在这样的优化问题中，存在施加了被称为独热约束的约束条件的问题。独热约束是其中在存在多个状态变量的情况下在一个解中其值为1的状态变量的数目被限制为一的约束。出现独热约束的优化问题包括许多调度问题例如旅行商问题(tsp)及通用的地点和路线(vpr)问题以及背包问题和装箱问题。
6.此外，存在两种类型的独热约束。一种是被称为单向独热(1w1h)约束的约束。在这种情况下，在约束表达式中每个变量在集合中仅出现一次。具有这种约束的优化问题包括流量优化问题和装箱问题。
7.另一种是被称为双向独热(2w1h)约束的约束。在这种情况下，当n2个变量以n
×
n方阵布置时，每一行的总和与每一列的总和全部为1。例如，该约束等同于在确定n个不同元素例如整数1、2、
……
、n的顺序的情况下的约束。具有这种约束的优化问题包括旅行商问题、通用的地点和路线问题以及二次分配问题(qap)。
8.在对这种双向独热问题的解中，通过设计公式，例如在通用的地点和路线问题中，目标储库(depot)的数目可以从约20增加至约100。此外，提出了通过下述执行优化处理的技术：使用具有不同惩罚系数的两个评估函数中的一个评估函数来进行确定最低能量状态的处理并且使用另一个评估函数来进行搜索优化问题的解的处理。此外，提出了通过使用马尔可夫链蒙特卡罗基于下述转变概率分布来更新状态变量的值的技术，在该转变概率分布中，评估函数的值的变化由于状态变量的值在正方向上的变化而越大，该转变概率就越
大于玻尔兹曼分布的转变概率。
9.日本公开特许公报第2019-121137号和日本公开特许公报第2020-205049号作为相关技术被公开。


技术实现要素：

10.技术问题
11.然而，在通用的地点和路线问题中的大规模或高度困难的问题中，很难通过借助于设计公式获得的典型解来从准局部解中逃离，并且可能难以获得最优解。其原因在于，在通过设计公式获得的典型解中，当执行状态转变时，状态的窄邻域此时变为搜索目标。这是因为根据双向独热约束的状态转变是作为置换操作的简单操作。因此，考虑一种用于通过使宽邻域成为搜索目标而从准最优状态逃离的方法，但是在进行转变的状态变量的数目增加的情况下，要搜索的下一状态的数目急剧增加，这使计算变得困难。
12.在这点上，在通过使用具有不同惩罚系数的两个评估函数来执行优化处理的技术中，从准局部解中逃离的概率高，但是难以减少以宽邻域作为搜索目标根据双向独热约束执行状态转变的情况下的计算量。此外，即使利用基于其中转变概率根据评估函数的值而增加的转变概率分布来更新状态变量的值的技术，也难以减少以宽邻域作为搜索目标根据双向独热约束执行状态转变的情况下的计算量。
13.鉴于以上描述实现了所公开的技术，并且其目的是提供有效地获得对于根据双向独热约束的问题的解的信息处理装置、信息处理方法和信息处理程序。
14.问题的解决方案
15.根据实施方式的一方面，提供了一种信息处理装置，包括：搜索单元，该搜索单元通过使用基于目标函数的第一矩阵作为权重矩阵来搜索向其赋予了包括双向独热约束的约束条件的问题的解；转变单元，该转变单元在由搜索单元进行的搜索达到特定状态的情况下改变作为搜索单元的搜索结果的解的值的一部分；以及权重矩阵切换单元，该权重矩阵切换单元在解中包括的多个变量的值的一部分被转变单元改变的情况下，通过将通过在权重矩阵中使用惩罚系数生成的返回矩阵设置为权重矩阵来使搜索单元执行搜索，并且当由搜索单元作出的搜索结果达到满足双向独热约束的状态时，通过将权重矩阵返回至第一矩阵来使搜索单元执行搜索。
16.发明的有益效果
17.在一个方面，该实施方式可以有效地获得对于根据双向独热约束的问题的解。
附图说明
18.图1是用于说明双向独热约束的图；
19.图2是根据实施方式的优化装置中包括的优化单元的配置图；
20.图3是示出实施方式中使用的权重矩阵的图；
21.图4是示出存储元件中的数据存储状态的示例的图；
22.图5是示出选择电路的示例的图；
23.图6是详细示出根据实施方式的优化装置的控制单元的框图；
24.图7是示出容量受限的车辆路线问题的示例的图；
25.图8是示出被赋予矩阵元素的组变量的示例的图；
26.图9是由根据实施方式的优化装置进行的优化处理的流程图；
27.图10是根据双向独热约束的优化处理的流程图；以及
28.图11是用于返回至满足双向独热约束的状态的优化处理的流程图。
具体实施方式
29.在下文中，参照附图详细描述本技术中公开的信息处理装置、信息处理方法和信息处理程序的实施方式。注意，以下实施方式不限制本技术中公开的信息处理装置、信息处理方法和信息处理程序。
30.[实施方式]
[0031]
考虑下述情况：其中，双向独热伊辛模型中包括的与多个自旋(自旋的数目＝n)对应的n个位的值由状态变量x1至xn表示。在下文中，由xi表示的状态变量可以由状态变量xi表示或者简单地由xi表示。
[0032]
在这种情况下，例如，当在以下表达式(1)中的大括号之间的每个组中仅存在其值为1的一个状态变量时，满足独热约束。
[0033]
[表达式1]
[0034][0035]
例如，在某一组中存在三个状态变量x1、x2和x3的情况下，状态{x1,x2,x3}＝{1,0,0},{0,1,0}或{0,0,1}满足独热约束。相反，状态{x1,x2,x3}＝{0,0,0},{1,1,0},{1,0,1},{0,1,1}或{1,1,1}不满足独热约束。
[0036]
此外，在双向独热约束的情况下，在两组条件中的每一组中都满足独热约束，例如，在每个组中都存在其值为1的一个状态变量。在双向独热约束中，例如，在两组条件中的每一组包括n个分量的情况下，可以将其中的每一个统一表示每个组的分量的元素布置为如图1所示的n
×
n方阵。在这种情况下，每一行的总和与每一列的总和全部为1。图1是用于说明双向独热约束的图。在图1中，m＝1、2、...、n，并且n＝n2。
[0037]
在这种情况下，为了从满足双向独热约束的某个状态转变至满足双向独热约束的另一状态，优化装置在一次状态更新处理中改变四个位的值。例如，在图1中状态变量xj的值为0的情况下，当xj从0转变至1时，与xj在同一行中的具有值1的状态变量xi从1转变至0。此外，与xj在同一列中的具有值1的状态变量xg从1转变至0。此外，与xi在同一列中且与xg在同一行中的xk从0转变至1。在下文中，某个状态变量的值从0转变至1或从1转变至0被称为状态变量的值反转或位反转。
[0038]
以这样的方式，为了从满足双向独热约束的某个状态转变至满足双向独热约束的另一状态，如以下表达式(2)中那样进行四个状态变量的转变。
[0039]
[表达式2]
[0040]
xi：1
→
0，xj:0
→
1，xk:0
→
l，xg：1
→0…
(2)
[0041]
例如，在这种情况下使用权重值的伊辛型能量函数由以下表达式(3)限定。
[0042]
[表达式3]
[0043][0044]
右侧的第一项通过以下操作来获得：在没有遗漏或重复的情况下针对可以从伊辛模型中包括的所有位中选择的两个位的所有组合，对两个位的值(0或1)与权重值的乘积进行合并。表示其索引(位标识信息)为i的位的值的状态变量由xi表示，并且表示其索引为j的位的值的状态变量由xj表示。在下文中，存在由i表示的索引被称为索引i或者被简单地称为i的情况。此外，w
ij
表示指示其索引为i的位与其索引为j的位之间的相互作用的大小的权重值。注意，w
ii
＝0。此外，在许多情况下w
ij
＝w
ji
。
[0045]
右侧的第二项表示所有位中的每个位的偏置值与位值的乘积的总和。具有索引i的位的偏置值由bi表示。
[0046]
接下来，在表达式(2)中，当xi的值变为1-xi时，xi的增量可以由δxi＝(1-xi)-xi＝1-2xi表示。与该值的变化相关联的能量变化(δei)由以下表达式(4)表示。
[0047]
[表达式4]
[0048][0049]
此外，如上所述为了从满足双向独热约束的某个状态转变至满足双向独热约束的另一状态，改变四个位的值。假设如表达式(2)中那样更改索引中的i、j、k和g，则通过使用表达式(3)按照以下表达式(5)获得这种情况下的能量变化。
[0050]
[表达式5]
[0051]
δej＝(hi+hg)-(hj+hk)-(w
ig
+w
jk
)
…
(5)
[0052]
当xi从1改变至0时，δxi为-1，并且当xi从0改变至1时，δxi为1。注意，hi被称为局部字段值(局部字段)，并且通过将hi乘以取决于δxi的符号(+1或-1)来获得δei。
[0053]
然后，xj的位反转时的局部字段hi的变化量δh
i(j)
由以下表达式(6)表示。
[0054]
[表达式6]
[0055][0056]
例如，通过准备存储hi的寄存器并且在xj的位反转时添加由表达式(5)表示的变化量来获得正确的hi。
[0057]
当xj从0改变至1时hm的变化量为δh
m(j)
＝+w
mj
，并且当xj从1改变至0时hm的变化量为δh
m(j)
＝-w
mj
。类似地，关于其索引为m的位的hm在xi改变时的变化量可以由δh
m(i)
＝δxmw
mi
表示。此外，关于其索引为m的位的hm在xk改变时的变化量可以由δh
m(k)
＝δxmw
mk
表示。此外，关于其索引为m的位的hm在xg改变时的变化量可以由δh
m(k)
＝δxmw
mk
表示。
[0058]
如上所述，为了从满足双向独热约束的某个状态转变至满足双向独热约束的另一状态，改变四个位的值。例如，在状态变量xj从0改变至1、状态变量xi从1改变至0、状态变量xk从0改变至1并且状态变量xg从1改变至0的情况下，其索引为m的局部字段的变化量由以下表达式(7)表示。
[0059]
[表达式7]
[0060]
δhm＝w
mj
+w
mk-(w
mi
+w
mg
)
…
(7)
[0061]
顺便提及，当优化装置通过在一次状态更新处理中重复改变四个位的值的处理来搜索基态时，对局部字段值进行更新以用于计算每次状态更新处理中的能量变化。例如，在某个组中索引j和索引k的位的值都从0改变至1并且索引i和索引g的位的值都从1改变至0的情况下，基于以下表达式(8)更新关于n个位的h1至hn。
[0062]
[表达式8]
[0063][0064]
在表达式(8)中，h1'至hn'表示更新之后的局部字段值。
[0065]
接下来，详细描述根据本实施方式的优化装置1。图2是根据实施方式的优化装置中包括的优化单元的配置图。作为信息处理装置的优化装置1包括控制单元10和优化单元20。优化单元20包括存储单元21、局部字段生成单元22、能量变化计算单元23、偏移添加单元24、选择电路25和更新单元26。优化单元20对应于“搜索单元”的示例。此处，描述使用均包括n个分量的条件组来求解具有双向独热约束的优化问题的情况。
[0066]
存储单元21包括多个列的路线，并且在每一列中还布置有与列一样多的存储元件210。例如，在图2中，存储单元21包括n个列的路线。然后，存储单元21在每一列中包括n个存储元件210。布置在从各个列的顶部起相同数目的级中的存储元件210对应于包括n个元件的行。例如，存储单元21通过以n
×
n矩阵布置的存储元件210分别保存指示相应的n个位之间的相互作用的大小的权重值。在作为权重值的矩阵的权重矩阵中，在初始设置处理时，由控制单元10将初始值存储在存储单元21的存储元件210中的每一个中。在图2中，每一行和每一列的存储元件210包括在行编号为i且列编号为j的情况下由w
ij
表示的权重值。存储单元21通过使用例如寄存器、静态随机存取存储器(sram)等来实现。
[0067]
此处，描述存储在存储单元21的存储元件210中的权重矩阵和权重值。图3是示出实施方式中使用的权重矩阵的图。此外，图4是示出存储元件中的数据存储状态的示例的图。
[0068]
在该实施方式中，使用下述矩阵作为权重矩阵：用于在状态变量满足双向独热约束时执行优化处理的优化矩阵31和用于将不满足双向独热约束的状态变量返回至满足双向独热约束的状态的返回矩阵32。优化矩阵31对应于“第一矩阵”的示例。此处，用于在状态变量满足双向独热约束时使用优化矩阵31执行优化处理的模式被称为优化模式。此外，用于使用返回矩阵32将不满足双向独热约束的状态变量返回至满足双向独热约束的状态的模式被称为返回模式。
[0069]
如图3所示，优化矩阵31是通过组合0矩阵与距离矩阵d而获得的矩阵。距离矩阵d是根据两个储库之间的距离给出成本的矩阵。例如，距离矩阵d由矩阵33表示。矩阵33对应于在优化矩阵31的第一行且第二列中的距离矩阵d。
[0070]
此外，如图3所示，返回矩阵32是通过组合惩罚矩阵p与经校正的距离矩阵d'而获得的矩阵。惩罚矩阵p是将惩罚系数p赋予违反双向独热约束中的条件之一的状态变量的矩阵并且由矩阵35表示。此外，经校正的距离矩阵d'是对违反双向独热约束中的另一条件的状态变量给予惩罚的矩阵，并且通过将具有惩罚系数p的对角矩阵34作为对角分量添加至
距离矩阵d来获得。例如，描述了下述情况：其中，状态变量以矩阵布置、时间流逝由以行布置的元素表示、并且储库由以列布置的元素表示。在这种情况下，惩罚矩阵p是对违反下述条件的状态变量给予惩罚的矩阵，该条件是不允许同时存在于两个或更多个不同储库处例如在时间t1处位于储库b1处并且在时间t1处移动至储库b2。此外，经校正的距离矩阵d'是对违反访问一个储库的次数为一的条件例如在时间t1和时间t2处处于储库b1处的条件的状态变量给予惩罚并且向其他状态变量赋予权重值的矩阵。
[0071]
此外，描述了存储在每个存储元件210中的权重值。例如，存储元件210存储图4所示的数据211。数据211包括权重值212和标志213。
[0072]
当权重值212位于与除了距离矩阵d中的对角分量之外的元素对应的位置时，存储指示与由该元素表示的两个储库之间的距离对应的成本的值。相反，当权重值212位于与除了距离矩阵d的对角分量和惩罚矩阵p的对角分量之外的元素对应的位置处，存储0和惩罚系数p。
[0073]
此外，作为标志213，存储指示权重值212是惩罚系数p还是根据两个储库之间的距离的成本的信息。此处，在标志213的值为0的情况下，其指示权重值212是成本，并且在标志213的值为1的情况下，其指示权重值212是惩罚系数。例如，其值为0的标志213被添加至位于与除了距离矩阵d的对角分量之外的元素对应的位置处的权重值212。相反，其值为1的标志213被添加至位于与除了距离矩阵d的对角分量和惩罚矩阵p的对角分量之外的元素对应的位置处的权重值212。
[0074]
此外，存储元件210包括选择电路214。选择电路214接收由存储元件210保存的数据211的输入。此外，选择电路214还从控制单元10接收指示优化装置1的操作模式是优化模式还是返回模式的信息的输入。然后，选择电路214确认数据211的标志213，并且确定权重值212是惩罚系数p还是成本。在权重值212是成本的情况下，选择电路214总是按原样输出权重值212的值。相反，在权重值212是惩罚系数p的情况下，选择电路214在优化装置1以优化模式操作的情况下输出0，并且在优化装置1以返回模式操作的情况下输出惩罚系数。
[0075]
返回至图2继续描述存储单元21。当选择电路25选择其值要被反转的状态变量时，存储在存储单元21的存储元件210中的权重值中与所选择的状态变量对应的权重的值被分别重写为反转之后的值。例如，在选择xj作为要反转的状态变量的情况下，从选择电路25输入索引j，并且重写由w
mj
表示的权重值。
[0076]
此处，在双向独热约束下以优化模式操作的情况下，四个位被一起反转。因此，在优化模式的情况下，在存储于存储单元21的各个存储元件210中的权重值中，由指示与由选择电路25指定的索引对应的其他三个位的索引标识的存储元件210保存的权重值也被重写。例如，在图1所示的矩阵的情况下，指示与索引j对应的其他三个位的索引为i、k和g。
[0077]
局部字段生成单元22包括多个局部字段生成电路220，所述多个局部字段生成电路220被布置成分别对应于布置在存储单元21的矩阵中的存储元件210的列。每个局部字段生成电路220获得布置在对应的列中的每个存储元件210中包括的权重值。然后，每个局部字段生成电路220通过使用所获得的权重值来生成局部字段值，该局部字段值是局部字段的值。
[0078]
在图2中的示例中，局部字段生成单元22包括局部字段生成电路220，该局部字段生成电路220生成h1、h2、
……
、和hn，h1、h2、
……
、和hn分别是关于n个位的局部字段值。虽然
未示出，但是局部字段生成电路220中的每一个包括保存单元(例如，寄存器)，并且保存局部字段值h1至hn并对由局部字段生成电路中的每一个保存的局部字段值h1至hn进行更新。
[0079]
例如，在更新状态变量xj的情况下，局部字段生成电路220中的每一个通过下述来更新局部字段：将与局部字段生成电路中的每一个对应的权重值w
j1
、w
j2
、
……
、或w
jn
添加至所保存的局部字段或者从所保存的局部字段中减去所述权重值w
j1
、w
j2
、
……
、或w
jn
。例如，与行i对应的局部字段生成电路220在状态变量xj从0转变至1的情况下将权重值w
ji
添加至局部字段hi，并且在状态变量xj从1转变至0的情况下从局部字段hi中减去权重值w
ji
。此处，如上所述，在双向独热的情况下四个位被反转，使得局部字段生成电路220通过向由其自身保存的局部字段添加表达式(7)或者从由其自身保存的局部字段中减去表达式(7)来更新局部字段。
[0080]
h1至hn的初始值分别是例如偏置值b1至bn，并且在初始设置处理时由控制单元10设置。通过使用例如加法器或减法器代替寄存器来实现局部字段生成电路220。
[0081]
此外，在操作模式从优化模式改变至返回模式的情况下，局部字段生成单元22使每个局部字段生成电路220重新计算改变时的作为局部字段的局部字段值。这是因为在操作模式从优化模式改变至返回模式的情况下，值为1至0的适当状态变量的转变被控制单元10强制进行，使得发生违反双向独热约束并且局部字段显著地改变。然而，在这种情况下，局部字段生成单元22没有使局部字段生成电路220从开始起重新计算局部字段，而是使局部字段生成电路220通过将两倍的惩罚系数p添加至发生违反双向独热约束的行和列中包括的变量的局部字段来重新计算局部字段。
[0082]
能量变化计算单元23基于由局部字段生成单元22生成的局部字段值来计算能量变化。在图2中的示例中，能量变化计算单元23包括能量变化计算电路230，该能量变化计算电路230计算δe1、δe2、
……
、和δen，δe1、δe2、
……
、和δen是在与存储单元21的存储元件210的列对应的相应的n个位分别改变的情况下的能量变化。在图2中，作为示例示出了从保存局部字段hi的局部字段生成电路220延伸至每个能量变化计算电路230的路线，但是该路线从其他局部字段生成电路220延伸至所有能量变化计算电路230。
[0083]
能量变化计算电路230使用表达式(5)计算能量变化量。例如，δej表示在如表达式(2)中那样转变四个状态变量的情况下的能量变化量。此后，每个能量变化计算电路230将所计算的能量变化量输出至选择电路25。
[0084]
偏移添加单元24监控从每个能量变化计算电路230输出的能量变化量。然后，在从能量变化计算电路230输出的所有能量变化量为正的情况下，偏移添加单元24将向每个值添加偏移。该偏移是负值，并且偏移添加单元24进行调整，使得能量变化量变为负值，例如在能量降低的情况下出现的能量变化量。
[0085]
选择电路25接收从每个能量变化计算电路230输出的能量变化量的输入。此处，在所有能量变化量为正的情况下，选择电路25接收通过由偏移添加单元24添加偏移而获得的值的输入。
[0086]
选择电路25输出用于标识基于热激发能量与由多个能量变化计算电路230中的每一个输出的能量变化量之间的大小关系允许进行值更新的状态变量的索引。热激发能量基于随机数和从控制单元10输入的温度参数来确定。在优化装置1中执行模拟退火的情况下，例如由控制单元10控制温度参数，使得每当更新伊辛模型的状态的处理被重复预定次数
时，该值减小。此外，还可以选择其中能量降低的方向上的状态变化，但是在这种情况下，状态变化在局部最小值处停止。因此，选择随机地允许能量增加的变化。
[0087]
图5是示出选择电路的示例的图。图5中的选择电路25是以平行取向选择更新位的候选的电路。输入端子251是接收与从能量变化计算电路230输出的能量变化量对应的索引的值的输入的端子。每个端子两个接两个地连接至选择器252。此外，来自选择器252的输出在下一级两个接两个地连接至选择器252。
[0088]
选择电路25通过将从能量变化计算电路230输入的能量变化量与从控制单元10输入的温度参数进行比较来确定所述能量变化量是否可以接受状态变量的转变。例如，在能量变化量小于根据温度参数计算的预定值的情况下，选择电路25确定状态变量的转变是可接受的。然后，选择电路25针对与被确定为能够接受状态变量的转变的能量变化对应的索引设置可更新标志。然后，选择电路25将与每个能量变化对应的索引输入至输入端子251中的每一个，并且通过选择器252执行比较(tournament)。
[0089]
选择器252通过例如图5中纸面右侧的电路来实现。包括该电路的选择器252接收两个状态01和02的输入，并且分别从这两个状态获得标志f1和f2以及索引#1和#2。然后，选择器252接收随机数的输入，并且选择具有可更新标志设置的索引#1或索引#2中的任何一个。选择器252将指示所选择的索引的0或1的条目号添加至较高级的索引。然后，选择器252将所选择的索引输出至下一级中的选择器252。由最后一级中的选择器252选择的索引指示被选择电路25选择的位。由选择电路25选择的索引的信息被输出至更新单元26并且发送至存储单元21。因此，更新了由该索引所标识的由存储元件210保存的权重值和由指示其他对应的位的索引所标识的存储元件210。
[0090]
更新单元26包括存储单元260，该存储单元260保存n个位的值(x1至xn)，n个位中的每个位表示状态变量。存储单元260例如通过使用寄存器、sram等来实现。更新单元26将由从选择电路25输入的索引所标识的位的值从0更新为1。此外，更新单元26更新与从选择电路25输入的索引对应的其他三个位的值。例如，在从选择电路25输入指示图1所示的状态变量xj的索引j的情况下，更新单元26更新由索引i、k和g所标识的位的值。在这种情况下，更新单元26如由表达式(2)表示的那样更新每个值。
[0091]
更新单元26向控制单元10输出状态变量的更新完成的通知。此外，更新单元26还向控制单元输出每个状态变量的更新值。
[0092]
接下来，描述控制单元10。图6是详细示出根据实施方式的优化装置的控制单元的框图。如图6所示，控制单元10包括上限计算单元11、目标函数生成单元12、初始化执行单元13、候选确定单元14、温度管理单元15、更新控制单元16、通知单元17、强制转变单元18和权重矩阵切换单元19。控制单元10通过例如现场可编程门阵列(fpga)来实现。例如，通过编程的fpga中包括的计算部和存储单元，实现上限计算单元11、目标函数生成单元12、初始化执行单元13、候选确定单元14、温度管理单元15、更新控制单元16、通知单元17、强制转变单元18和权重矩阵切换单元19的功能。
[0093]
此处，描述了优化装置1求解容量受限的车辆路线问题(cvrp)的情况。图7是示出容量受限的车辆路线问题的示例的图。在容量受限的车辆路线问题中，如图7所示，确定了收集站点101和作为包裹的递送目的地的储库102的位置。此外，给出了收集站点101与每个储库102之间的距离以及车辆的装载上限值。此外，给出了与要递送至每个储库102的包裹
量对应的需求量。然后，从收集站点101开始并且返回至收集站点101的多个车辆向每个储库102运送供应品。在上述条件下获得使由所有车辆行进的总距离最小化的路线的问题是容量受限的车辆路线问题。图7示出了在使用四个车辆通过四个路线运输供应品的情况下的容量受限的车辆路线问题。
[0094]
初始化执行单元13接收要求解的容量受限的车辆路线问题的条件的输入。作为这种容量受限的车辆路线问题的条件的问题实例包括作为递送目的地的储库102的数目、收集站点101与储库102中的每个储库之间的距离、路线的数目等。符合输入条件的每个元素通过使用表示下述分量的矩阵来表示：表示指示其包括在哪个路线中的一组条件的分量；以及表示指示在哪个时间点处在该储库处执行递送的一组条件的分量。表示指示其包括在哪个路线中的一组条件的分量和表示指示在哪个时间点处在该储库处执行递送的一组条件的分量对应于“在两个组中的每个组中包括的预定数目的分量”的示例。初始化执行单元13将容量受限的车辆路线问题的条件输出至上限计算单元11。
[0095]
此后，初始化执行单元13从目标函数生成单元12接收表示满足双向独热约束的状态变量的每个位的矩阵和目标函数的信息的输入。然后，初始化执行单元13根据矩阵的元素选择用于存储单元21的优化的存储元件210。接下来，初始化执行单元13根据目标函数获得与每个状态变量对应的权重值，并且设置与每个存储元件210对应的权重值。
[0096]
接下来，初始化执行单元13将所有状态变量x1至xn设置为0，然后将表示状态变量x1至xn的位中的每个位设置为0或1，以满足双向独热约束。然后，初始化执行单元13将表示状态变量x1至xn的位中的每个位的值输出至优化单元20。因此，初始状态下的每个位的值被存储在更新单元26中包括的存储单元260中，并且根据每个位的状态来生成作为局部字段的h1至hn中的每一个以由局部字段生成单元22保存。
[0097]
此外，图8是示出被赋予矩阵的元素的组变量的示例的图。初始化执行单元13向矩阵中的同一行中的元素分配行组号作为同一行组，并且向同一列中的元素分配列组号作为同一列组。然后，初始化执行单元13将指示每个元素的索引与行组号和列组号进行关联。
[0098]
然后，初始化执行单元13将与指示每个元素的索引相关联的组变量的信息输出至候选确定单元14。此外，初始化执行单元13向温度管理单元15通知初始温度的设置。
[0099]
上限计算单元11以升序排列储库102的需求量。接下来，当计算第m路线中的储库的最大数目时，上限计算单元11计算从所排列的需求量的顶部到第(m-1)需求量的累积需求量，包括储库数目。接下来，上限计算单元11指定储库的最小数目，该最小数目不超过“m
×
车辆的装载上限值”。然后，上限计算单元11将通过将指定的储库数目除以m得到的商设置为第n路线中的储库的最大数目。这是因为通过以升序排列需求量而使需求量变为目标递减序列，使得第m路线变得比通过将不大于“m
×
车辆的装载上限值”的储库的最小数目除以m而获得的数目大的事实是矛盾的。上限计算单元11将m从1改变至车辆的上限数目，以获得第一车辆至上限数目的车辆的每个路线中的储库的最大数目。此后，上限计算单元11将关于每个路线中的储库的最大数目的信息输出至目标函数生成单元12。
[0100]
目标函数生成单元12从上限计算单元11接收关于每个路线中的储库的最大数目的信息的输入。接下来，目标函数生成单元12计算每个路线中的储库的最大数目的总和与储库102的数目之间的差。然后，目标函数生成单元12将计算出的差设置为冗余储库(虚拟储库)的数目。接下来，目标函数生成单元12创建由其中按顺序布置针对每个路线的直到储
库的最大数目的行和其中布置包括冗余储库的储库的行表示的矩阵。例如，假设行延伸的方向是时间流逝，该矩阵表示通过将冗余储库添加至车辆访问的实际储库102而获得的扩展储库中的储库以及车辆访问储库的时间点。每一行是指示储库包括在哪个路线中的一组条件，并且每一列是指示在哪个时间点处执行到储库的递送的一组条件。
[0101]
然后，目标函数生成单元12：将编号分配至储库102，如i＝0、1、2、
……
；如果在时间t处在索引i的储库102处存在车辆，则将x
it
设置为1；如果不存在车辆，则将x
it
设置为0，并且设置表示状态变量的位。
[0102]
在该矩阵中，从第一行至第一路线中的储库的最大数目的行的行表示在第一路线中行进的车辆的位置，并且从下一行至第二路线中的储库的最大数目的行的行表示在第二路线中行进的车辆的位置。以这样的方式，路线的数目按顺序递增，并且从最后一行至与矩阵的第n路线中的储库的最大数目对应的行的行表示在第n路线中行进的车辆的位置。该矩阵具有相同数目的行和列，并且满足“每一行和每一列中的1的数目为一”的双向独热约束。
[0103]
然后，目标函数生成单元12通过以下表达式(9)限定目标函数。
[0104]
[表达式9]
[0105]
e(x，y)＝c(x)+p1(x)+p2(x，y)
…
(9)
[0106]
e(x,y)表示能量。然后，c(x)表示成本的总和。此外，p1(x)表示对冗余储库的约束。此外，p2(x,y)表示松弛变量y的不等式约束。
[0107]
目标函数生成单元12将所生成的矩阵的信息和能量函数输出至初始化执行单元13。
[0108]
温度管理单元15从初始化执行单元13接收初始温度设置的指令。然后，温度管理单元15将为高温的初始温度设置为温度参数。然后，温度管理单元15将温度参数通知给优化单元20。此后，当温度管理单元15从更新控制单元16接收用于降低温度的指令时，温度管理单元15根据预先指定的温度时间表降低温度参数的值。每当温度参数改变时，温度管理单元15就向优化单元20通知所改变的温度参数。
[0109]
候选确定单元14从初始化执行单元13接收表示每个索引的组变量的信息的输入。此外，候选确定单元14从更新控制单元16接收优化装置1的操作模式的输入。然后，候选确定单元14根据操作模式将指示要反转的状态变量的索引确定为转变候选，并且将该转变候选通知给优化单元20。下面描述用于选择作为转变候选的要反转的状态变量的方法。
[0110]
描述操作模式为优化模式的情况。候选确定单元14使用组变量的信息来选择指示其值要被反转的状态变量的索引。例如，候选确定单元14在图1所示的矩阵中选择指示状态变量xj的索引j。然后，候选确定单元14根据所选择的索引指定指示根据双向独热约束确定的其他三个位的索引。例如，在候选确定单元14在图1所示的矩阵中首先选择指示状态变量xj的索引j的情况下，候选确定单元14选择i、k和g作为其他三个索引。接下来，候选确定单元14将与所选择的索引对应的状态变量确定为其值要被反转的候选。然后，候选确定单元14将被确定为其状态变量的值要被反转的候选的索引通知给优化单元20。
[0111]
通过从1至n逐一选择要反转的索引j，候选确定单元14针对所有索引确定由每个索引指示的状态变量是否成为位反转的候选，并且将其通知给优化单元20。
[0112]
接下来，描述操作模式为返回模式的情况。在这种情况下，不施加双向独热约束，使得候选确定单元14使用组变量的信息从1至n顺序地选择指示其值要被反转的状态变量
的索引。然后，候选确定单元14针对每次选择将被确定为其状态变量的值将被反转的候选的索引通知给优化单元20。
[0113]
此后，当从更新控制单元16接收用于选择下一状态变量x的指令时，候选确定单元14根据操作模式按顺序再次从1至n选择索引，并且将各个状态变量是否成为位反转的候选通知给优化单元20。
[0114]
更新控制单元16从优化单元20接收状态变量的更新完成的通知。此时，更新控制单元16还从优化单元20接收每个状态变量的值的输入。然后，更新控制单元16顺序地累积关于状态变量的更新值的信息，并且使用最近信息来确定该状态变量是否落入局部解。
[0115]
在状态变量落入局部解的情况下，更新控制单元16指示强制转变单元18执行强制转变处理，以从局部解中逃离。此外，更新控制单元16向候选确定单元14、权重矩阵切换单元19和优化单元20通知操作模式从优化模式改变至返回模式。
[0116]
在转变至返回模式之后，当从优化单元20接收到状态变量的更新完成的通知时，更新控制单元16还从优化单元20获得每个状态变量的值。然后，更新控制单元16确定每个状态变量是否处于状态变量的值满足双向独热约束的状态。在不满足双向独热约束的状态下，更新控制单元16继续返回模式下的操作，并且重复状态转变以恢复至满足双向独热约束的状态。相反，在满足双向独热约束的情况下，更新控制单元16确定恢复至优化模式。然后，更新控制单元16将从优化模式改变至返回模式通知给候选确定单元14、权重矩阵切换单元19和优化单元20。
[0117]
相反，当状态变量没有落入局部解时，更新控制单元16确定状态变量是否以相同的温度设置被选择了指定次数。在状态变量以相同的温度设置没有被选择指定次数的情况下，更新控制单元16指示候选确定单元14选择下一个状态变量x。
[0118]
相反，在以相同的温度设置选择状态变量指定次数完成的情况下，更新控制单元16确定温度是否被降低预定次数。在温度降低的次数没有达到预定次数的情况下，更新控制单元16指示温度管理单元15降低温度，并且指示候选确定单元14选择下一个状态变量x。
[0119]
相反，在温度降低的次数达到预定次数的情况下，更新控制单元16确定结束优化处理。然后，更新控制单元16获得表示存储在优化单元20的更新单元26中包括的存储单元260中的各个状态变量(x1至xn)的n＝n2个位的值。然后，更新控制单元16从表示各个获得的状态变量(x1至xn)的n＝n2个位的值中删除表示冗余储库的状态变量的位值。然后，更新控制单元16将指示行进实际储库102的优化路线的信息输出至通知单元17。
[0120]
此处，在本实施方式中，在落入局部解的情况下更新控制单元16确定执行强制转变处理，但是执行强制转变处理的时机不限于此。例如，更新控制单元16可以确定在预定数目的迭代结束时执行强制转变处理，例如在100次迭代结束时执行一次强制转变处理或者在10000次迭代结束时执行一次强制转变处理。此外，当选择电路25拒绝x1至xn的所有转变时，更新控制单元16可以确定执行强制转变处理。可替选地，更新控制单元16可以在能量变化小的状态持续预定次数的情况下确定执行强制转变处理。
[0121]
通知单元17从更新控制单元16接收指示行进实际储库102的优化路线的信息的输入。然后，通知单元17从所获得的指示行进实际储库102的优化路线的信息中获得最优路线，并且通过将所获得的最优路线发送至用户使用的终端装置(未示出)等来将所获得的最优路线通知给用户。
[0122]
强制转变单元18从更新控制单元16接收用于执行强制转变处理的指令，以用于在落入局部解的情况下从局部解中逃离。此处，落入局部解的情况对应于“搜索达到特定状态的情况”的示例。然后，强制转变单元18根据预定算法选择行组和列组，对其中的值进行强制转变。例如，强制转变单元18选择包括指示在行进至每个储库的路线中到不同路线彼此靠近的位置处或在路线中彼此交叠的位置处的储库的行进的信息的行组和列组。在图7的情况下，强制转变单元18将区域121和122限定为不同路线彼此靠近或彼此交叠的位置，并且选择包括指示到区域121和122中的储库的行进的信息的行组和列组。
[0123]
此后，强制转变单元18强制地将在所选择的行组和列组中包括的状态变量中的其值为1的状态变量的值转变至0。因此，将状态变量转变至从当前状态显著改变的状态，并且将状态变量置于违反双向独热约束的状态。
[0124]
此处，虽然根据本实施方式的强制转变单元18选择其中使用预定算法强制进行状态变量的值的转变的行组和列组，但是选择方法不限于此。例如，强制转变单元18可以随机地选择经受强制转变的行组和列组。此外，强制转变单元18可以从未示出的管理者终端等接收经受强制转变的行组和列组的说明。此外，可能存在期望根据优化阶段确定经受强制转变的行组和列组的情况。在这种情况下，强制转变单元18可以从优化单元20的更新单元26获得此时的状态变量，并且将该状态变量输出至外部装置，使得外部装置进行分析和计算以获得被适当地改变的位，并且基于计算结果进行选择。强制转变单元18对应于“转变单元”的示例。
[0125]
权重矩阵切换单元19从更新控制单元16接收操作模式从优化模式改变至返回模式的通知。然后，权重矩阵切换单元19将指示优化装置1的操作处于返回模式的信号发送至优化单元20中的存储单元21和局部字段生成单元22。因此，从存储单元21的存储元件210中保存惩罚系数p的存储元件210输出惩罚系数p。例如，图3中的返回矩阵32用于计算局部字段。此外，局部字段生成单元22中的每个局部字段生成电路220重新计算指示该局部字段的局部字段值。
[0126]
此后，当状态变量达到满足双向独热约束的状态时，权重矩阵切换单元19从更新控制单元16接收操作模式从返回模式改变至优化模式的通知。然后，权重矩阵切换单元19将指示优化装置1的操作处于优化模式的信号发送至优化单元20中的存储单元21。因此，存储单元21的存储元件210中保存惩罚系数p的存储元件210返回至输出0的状态。例如，存储单元21的存储元件210中保存惩罚系数p的存储元件210返回至其中使用优化矩阵31计算局部字段的状态。
[0127]
图9是由根据实施方式的优化装置进行的优化处理的流程图。接下来，参照图7描述由根据实施方式的优化装置1进行的优化处理的流程。该优化处理通过在优化装置1中执行的信息处理程序来实现。
[0128]
初始化执行单元13接收容量受限的车辆路线问题的条件的输入。然后，初始化执行单元13将所获得的容量受限的车辆路线问题的条件输出至上限计算单元11。上限计算单元11以需求量的升序排列作为递送目的地的储库102。接下来，上限计算单元11从顶部起顺序地选择以需求量的升序排列的储库102，并且通过使用直到所选择的储库102的累积需求量和车辆的装载上限值来计算每个路线中的储库的最大数目。目标函数生成单元12使用储库的最大数目来设置冗余储库，并且生成表示下述路线及递送顺序的矩阵，在该路线中包
括包含冗余储库和实际储库102的扩展储库。然后，目标函数生成单元12给出表示所生成的矩阵的各个元素的位，并且使用这些位来生成目标函数。初始化执行单元13获得由目标函数生成单元12生成的矩阵和目标函数。接下来，初始化执行单元13执行下面描述的组索引设置和初始化处理(步骤s1)。
[0129]
例如，初始化执行单元13向所获得的矩阵的每一行中的每个元素赋予指示每一行的行组号，并且向每一列中的每个元素赋予指示每一列的列组号。然后，初始化执行单元13将指示每个元素的索引与行组号和列组号进行关联。此外，初始化执行单元13根据每个索引是否指示向冗余储库递送来设置指示每个索引是否属于冗余变量组的信息。
[0130]
此外，初始化执行单元13根据矩阵中的每个元素来固定在优化单元20的存储单元21中包括的存储元件210，并且将从目标函数获得的针对每个位的权重值存储在该存储元件210中。此外，初始化执行单元13设置每个位的初始值以满足双向独热，并且将该初始值通知给优化单元20。因此，在优化单元20中，局部字段生成单元22进行计算以保存作为局部字段的h1至hn，并且将每个位的初始值存储在更新单元26中包括的存储单元260中。
[0131]
温度管理单元15从初始化执行单元13接收温度设置的指令。然后，在温度管理单元15还没有设置温度的情况下，温度管理单元15将为高温的初始温度通知给优化单元20，并且设置初始温度。此外，在已经设置温度的情况下，温度管理单元15根据预先指定的温度时间表从此时已经设置的设定温度起降低温度。然后，温度管理单元15将新的降低的设定温度通知给优化单元20，并且设置温度(步骤s2)。
[0132]
控制单元10和优化单元20根据双向独热约束执行优化处理(步骤s3)。
[0133]
此后，当优化单元20中的状态变量和局部字段的更新完成时，控制单元10中的更新控制单元16基于每个状态变量的更新值来确定是否落入局部解(步骤s4)。
[0134]
在已经落入局部解的情况下(步骤s4：是)，更新控制单元16指示强制转变单元18执行强制转变处理以从局部解中逃离。强制转变单元18根据所确定的算法选择行组和列组，对其中的值进行强制转变。然后，强制转变单元18将所选择的行组和列组中值为1的状态变量的值转变至0(步骤s5)。
[0135]
此外，更新控制单元16向存储单元21和局部字段生成单元22通知操作模式改变至返回模式。然后，将指示返回模式的信号输入至存储单元21的存储元件210中包括的选择电路214。选择电路214使用标志213来确定输入权重值是否是惩罚系数p，并且在权重值是惩罚系数p的情况下输出指示输入惩罚系数p的权重值。此时，在权重值也是成本的情况下，选择电路214输出指示成本的权重值。因此，存储单元21改变要用于返回矩阵32的权重矩阵(步骤s6)。
[0136]
局部字段生成单元22从更新控制单元16接收操作模式改变至返回模式的通知，并且使每个局部字段生成电路220在一些状态变量的值被从1强制转变至0之后重新计算局部字段(步骤s7)。
[0137]
然后，控制单元10和优化单元20执行用于返回至满足双向独热约束的状态的优化处理(步骤s8)。
[0138]
此后，当在优化单元20中状态变量和局部字段的更新完成时，控制单元10中的更新控制单元16基于每个状态变量的更新值来确定该状态变量是否返回至满足双向独热约束的状态(步骤s9)。
[0139]
在状态变量没有返回至满足双向独热约束的状态的情况下(步骤s9：否)，优化处理重复步骤s8。
[0140]
相反，在状态变量返回至满足双向独热约束的状态的情况下(步骤s9：是)，更新控制单元16将操作模式恢复至优化模式通知给存储单元21。然后，将指示优化模式的信号输入至存储单元21的存储元件210中包括的选择电路214。选择电路214使用标志213来确定输入权重值是否是惩罚系数p，并且在权重值是惩罚系数p的情况下输出0作为权重值。此时，当权重值是成本时，选择电路214输出指示成本的权重值。因此，存储单元21将要使用的权重矩阵返回至优化矩阵31(步骤s10)。此后，优化处理返回至步骤s3。
[0141]
相反，在没有落入局部解的情况下(步骤s4：否)，更新控制单元16确定状态变量更新指定次数是否完成(步骤s11)。在状态变量没有更新指定次数的情况下(步骤s11：否)，优化处理返回至步骤s3。
[0142]
相反，在状态变量更新指定次数完成的情况下(步骤s11：是)，更新控制单元16确定温度是否降低指定次数(步骤s12)。
[0143]
在温度没有降低指定次数的情况下(步骤s12：否)，优化处理返回至步骤s2。相反，在温度降低指定次数的情况下(步骤s12：是)，优化装置1结束优化处理。
[0144]
图10是根据双向独热约束的优化处理的流程图。接下来，参照图10，描述根据双向独热约束的优化处理的流程。图10所示的每个处理对应于图9中在步骤s3处执行的处理的示例。
[0145]
候选确定单元14从初始化执行单元13获得与指示每个状态变量的索引相关联的组变量的信息。接下来，候选确定单元14在图1所示的矩阵的元素中选择与xj对应的索引j作为指示要被反转的状态变量的索引。接下来，候选确定单元14根据所选择的索引j指定与图1所示的矩阵中的状态变量xi、xk和xg对应的索引i、k和g作为根据双向独热约束确定的其他三个位的索引(步骤s101)。候选确定单元14从1至n顺序地选择索引作为索引j。
[0146]
候选确定单元14将索引i、j、k和g通知给优化单元20。优化单元20读取保存在更新单元26中包括的存储单元260中的xj的值。然后，优化单元20将xj的值是从0转变至1还是从1转变至0通知给能量变化计算单元23。能量变化计算单元23：读取hj，hj为与j对应的局部字段；进一步指定与j对应的i、k和g；以及分别从保存hi、hk和hg的局部字段生成电路220读取hi、hk和hg(步骤s102)。
[0147]
接下来，能量变化计算单元23计算δe(δe1、δe2、
……
、δen)，δe(δe1、δe2、
……
、δen)为针对每个j的能量变化量(步骤s103)。此后，能量变化计算单元23输出所计算的能量变化量的信息。
[0148]
在从能量变化计算单元23输出的所有能量变化量为正的情况下，偏移添加单元24将偏移添加至每个能量变化量(步骤s104)。
[0149]
选择电路25获得从能量变化计算单元23输出的每个能量变化量的信息。然后，选择电路25通过与从控制单元10中的温度管理单元15获得的设定温度进行比较来针对指示可以接受值的反转的状态变量的索引设置可更新标志。此后，选择电路25从向其添加了可更新标志的索引中选择一个索引q(步骤s105)。
[0150]
优化单元20从控制单元10获得分配给每个索引的组变量的信息。然后，优化单元20指定指示其值被反转的状态变量x
p
、xr和xs的索引p、r和s，以满足与由选择电路25选择的
索引q指示的状态变量xq的值的反转对应的双向独热约束。然后，优化单元20指定表示索引p、r和s的组变量(步骤s106)。
[0151]
将作为指示其值要被更新的状态变量的索引的p、q、r和s的信息输入至存储单元21，并且将与所述索引对应的权重值分别输出至局部字段生成单元22中的局部字段生成电路220。每个局部字段生成电路220接收与p、q、r或s的更新对应的权重值的输入，并且对所保存的局部字段进行更新(步骤s107)。
[0152]
此外，存储单元21分别更新存储在与索引p、q、r和s对应的存储元件210中的权重值(步骤s108)。
[0153]
向其输入作为指示其值要被更新的状态变量的索引的p、q、r和s的信息的更新单元26指定x
p
、xq、xr和xs，x
p
、xq、xr和xs是由从存储单元260保存的状态变量获得的索引指示的状态变量。然后，更新单元26反转并更新所指定的状态变量x
p
、xq、xr和xs的值(步骤s109)。
[0154]
此后，更新单元26将所有更新的状态变量写入存储单元260。此外，每个局部字段生成电路220将更新的局部字段写入由其保存的寄存器中(步骤s110)。
[0155]
图11是用于返回至满足双向独热约束的状态的优化处理的流程图。接下来，参照图11，描述用于返回至满足双向独热约束的状态的优化处理的流程。图11中所示的每个处理对应于图9中在步骤s8处执行的处理的示例。
[0156]
候选确定单元14从初始化执行单元13获得与指示每个状态变量的索引相关联的组变量的信息。接下来，候选确定单元14在图1所示的矩阵的元素中选择与xj对应的索引j作为指示要被反转的状态变量的索引(步骤s201)。候选确定单元14从索引1至索引n顺序地进行选择作为索引j。
[0157]
候选确定单元14将索引j通知给优化单元20。优化单元20读取保存在更新单元26中包括的存储单元260中的xj的值。然后，优化单元20将xj的值是从0转变至1还是从1转变至0通知给能量变化计算单元23。能量变化计算单元23读取hj，hj为与j对应的局部字段。接下来，能量变化计算单元23计算δe(δe1、δe2、
……
、δen)，δe(δe1、δe2、
……
、δen)为针对每个j的能量变化量(步骤s202)。此后，能量变化计算单元23输出所计算的能量变化量的信息。
[0158]
在从能量变化计算单元23输出的所有能量变化量为正的情况下，偏移添加单元24将偏移添加至每个能量变化量(步骤s203)。
[0159]
选择电路25获得从能量变化计算单元23输出的每个能量变化量的信息。然后，选择电路25通过与从控制单元10中的温度管理单元15获得的设定温度进行比较来针对指示可以接受值的反转的状态变量的索引设置可更新标志。此后，选择电路25从向其添加了可更新标志的索引中选择一个索引q作为要被更新的索引(步骤s204)。
[0160]
将指示其值要被更新的状态变量的索引q的信息输入至存储单元21，并且将与该索引对应的权重值输出至局部字段生成单元22中的每个局部字段生成电路220。每个局部字段生成电路220接收与索引q的更新对应的权重值的输入，并且对所保存的局部字段进行更新(步骤s205)。
[0161]
此外，存储单元21更新存储在与索引q对应的存储元件210中的权重值(步骤s206)。
[0162]
向其输入指示其值要被更新的状态变量的索引q的信息的更新单元26指定xq，xq为
由从存储单元260保存的状态变量获得的索引指示的状态变量。然后，更新单元26反转并更新所指定的状态变量xq的值(步骤s207)。
[0163]
此后，更新单元26将所有更新的状态变量写入存储单元260。此外，每个局部字段生成电路220将更新的局部字段写入由其保存的寄存器中(步骤s208)。
[0164]
如上所述，根据本实施方式的优化装置在求解具有双向独热约束的优化问题时，在达到预定状态例如落入局部解的情况下，强制地将一些状态变量的值从1转变至0。然后，将权重矩阵切换为使用惩罚系数的矩阵，执行优化处理，并且返回至满足双向独热约束的状态。因此，在落入准最优解的情况下，可以容易地从准最优解中逃离并且容易地获得最优解。

技术特征：
1.一种信息处理装置，包括：搜索单元，所述搜索单元通过使用基于目标函数的第一矩阵作为权重矩阵来搜索向其赋予了包括双向独热约束的约束条件的问题的解；转变单元，所述转变单元在由所述搜索单元进行的搜索达到特定状态的情况下改变作为所述搜索单元的搜索结果的所述解的值的一部分；以及权重矩阵切换单元，所述权重矩阵切换单元在所述解中包括的多个变量的值的一部分被所述转变单元改变的情况下，通过将通过在所述权重矩阵中使用惩罚系数生成的返回矩阵设置为所述权重矩阵来使所述搜索单元执行所述搜索，并且当由所述搜索单元作出的所述搜索结果达到满足所述双向独热约束的状态时，通过将所述权重矩阵返回至所述第一矩阵来使所述搜索单元执行所述搜索。2.根据权利要求1所述的信息处理装置，其中，所述搜索单元通过在不允许重复的情况下将预定数目的状态变量分配至两个组中的每个组中包括的预定数目的分量来满足所述双向独热约束，并且所述转变单元通过改变所述解的值的一部分来取消所述状态变量至所述分量的分配的一部分。3.根据权利要求1所述的信息处理装置，其中，在由所述搜索单元进行的所述搜索落入局部解的情况下，所述转变单元将所述解的一部分转变至另一值。4.根据权利要求1所述的信息处理装置，还包括候选确定单元，在使所述搜索单元通过使用所述第一矩阵执行所述搜索的情况下，所述候选确定单元通过在所述目标函数的变量中选择要被四个接四个地改变的变量来使所述搜索单元执行所述搜索，以满足所述双向独热约束，并且在使所述搜索单元通过使用所述返回矩阵执行所述搜索的情况下，所述候选确定单元通过在所述目标函数的变量中选择要被一个接一个地改变的变量来使所述搜索单元执行所述搜索。5.根据权利要求1所述的信息处理装置，其中，在所述解的值的一部分被所述转变单元改变的情况下，所述搜索单元重新计算局部字段。6.根据权利要求1所述的信息处理装置，其中，在所述第一矩阵中，将所述目标函数中使用的值赋予多个第一元素，并且将0赋予除了所述第一元素之外的第二元素，在所述返回矩阵中，将与所述第一矩阵的值相同的值赋予所述第一元素，并且将所述惩罚系数的值赋予所述第二元素，所述搜索单元包括存储元件，所述存储元件保存所述返回矩阵的每个元素，在使用所述返回矩阵的情况下，所述搜索单元从其中存储有所述第二元素的值的所述存储元件中读取所述惩罚系数的值，并且在使用所述第一矩阵的情况下，所述搜索单元从其中存储有所述第二元素的值的所述存储元件中读取0。7.一种由计算机实现的信息处理方法，所述信息处理方法包括：对搜索单元进行初始化，所述搜索单元通过使用基于目标函数的第一矩阵作为权重矩阵来进行搜索，所述搜索单元是用于向其赋予了包括双向独热约束的约束条件的问题的解的电路系统；执行转变处理，所述转变处理包括在由所述搜索单元进行的搜索达到特定状态的情况
下改变作为所述搜索单元的搜索结果的所述解的值的一部分；以及执行权重矩阵切换处理，所述权重矩阵切换处理包括：在所述解中包括的多个变量的值的一部分被所述转变处理改变的情况下，通过将通过在所述权重矩阵中使用惩罚系数生成的返回矩阵设置为所述权重矩阵来使所述搜索单元执行所述搜索，以及在由所述搜索单元作出的所述搜索结果达到满足所述双向独热约束的状态的情况下，通过将所述权重矩阵返回至所述第一矩阵来使所述搜索单元执行所述搜索。8.一种非暂态计算机可读存储介质，其存储有使计算机执行处理的信息处理程序，所述处理包括：对搜索单元进行初始化，所述搜索单元通过使用基于目标函数的第一矩阵作为权重矩阵来进行搜索，所述搜索单元是用于向其赋予了包括双向独热约束的约束条件的问题的解的电路系统；执行转变处理，所述转变处理包括在由所述搜索单元进行的搜索达到特定状态的情况下改变作为所述搜索单元的搜索结果的所述解的值的一部分；以及执行权重矩阵切换处理，所述权重矩阵切换处理包括：在所述解中包括的多个变量的值的一部分被所述转变处理改变的情况下，通过将通过在所述权重矩阵中使用惩罚系数生成的返回矩阵设置为所述权重矩阵来使所述搜索单元执行所述搜索，以及在由所述搜索单元作出的所述搜索结果达到满足所述双向独热约束的状态的情况下，通过将所述权重矩阵返回至所述第一矩阵来使所述搜索单元执行所述搜索。

技术总结
本申请涉及信息处理装置、信息处理方法和计算机可读存储介质。信息处理装置包括：搜索单元，该搜索单元通过使用基于目标函数的第一矩阵作为权重矩阵来搜索向其赋予了包括双向独热约束的约束条件的问题的解；转变单元，该转变单元在由搜索单元进行的搜索达到特定状态的情况下改变作为搜索单元的搜索结果的解的值的一部分；以及权重矩阵切换单元，该权重矩阵切换单元在解中包括的多个变量的值的一部分被转变单元改变的情况下，通过将通过在权重矩阵中使用惩罚系数生成的返回矩阵设置为权重矩阵来使搜索单元执行搜索，并且当由搜索单元作出的搜索结果达到满足双向独热约束的状态时，通过将权重矩阵返回至第一矩阵来使搜索单元执行搜索。索单元执行搜索。索单元执行搜索。


技术研发人员：神田浩一
受保护的技术使用者：富士通株式会社
技术研发日：2022.11.21
技术公布日：2023/7/26