Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456
JP6011928B2 - Solution search system and method, solution search program - Google Patents
[go: Go Back, main page]

JP6011928B2 - Solution search system and method, solution search program - Google Patents

Solution search system and method, solution search program Download PDF

Info

Publication number
JP6011928B2
JP6011928B2 JP2012232402A JP2012232402A JP6011928B2 JP 6011928 B2 JP6011928 B2 JP 6011928B2 JP 2012232402 A JP2012232402 A JP 2012232402A JP 2012232402 A JP2012232402 A JP 2012232402A JP 6011928 B2 JP6011928 B2 JP 6011928B2
Authority
JP
Japan
Prior art keywords
data
output
data generation
generation unit
output adjustment
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired - Fee Related
Application number
JP2012232402A
Other languages
Japanese (ja)
Other versions
JP2014085733A (en
Inventor
真士 青野
真士 青野
成主 金
成主 金
原　正彦
正彦 原
政光 若林
政光 若林
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
RIKEN
Original Assignee
RIKEN
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by RIKEN filed Critical RIKEN
Priority to JP2012232402A priority Critical patent/JP6011928B2/en
Publication of JP2014085733A publication Critical patent/JP2014085733A/en
Application granted granted Critical
Publication of JP6011928B2 publication Critical patent/JP6011928B2/en
Expired - Fee Related legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Landscapes

  • Complex Calculations (AREA)

Description

本発明は、最適解探索問題の解を高速かつ効率的に探索する解探索システム及び方法、解探索プログラムに関するものである。   The present invention relates to a solution search system and method for searching for an optimal solution search problem at high speed and efficiently, and a solution search program.

与えられた制約条件を満足する解を探索する問題の代表例として、与えられた命題論理式を“真”にできるような変数の真偽値の組合せを探索する、いわゆる充足可能性問題（Satisfiability Problem, SAT）がよく知られている。SATは、解候補の数が問題サイズに対して指数関数的に成長する極めて高い計算複雑性をもつ、代表的な組合わせ最適化問題であり、ソフトウェアおよびハードウェア検証、ならびに情報セキュリティー関連技術等を含む、多くのアプリケーションと密接に関連している。このため、SATを解くシステム及び方法、解探索プログラムは、今後の情報化社会において極めて重要である。これに関連した先行技術としては、ＳＡＴ解法プログラムや、障害診断プログラム等が提案されている（特許文献１、２参照）。   A typical example of a problem that searches for a solution that satisfies a given constraint is a so-called satisfiability problem that searches for a combination of variables that can make a given propositional formula "true". Problem, SAT) is well known. SAT is a typical combinatorial optimization problem with extremely high computational complexity in which the number of solution candidates grows exponentially with the problem size. Software and hardware verification, information security related technologies, etc. It is closely related to many applications, including For this reason, systems and methods for solving SAT, and solution search programs are extremely important in the future information society. As prior art related to this, a SAT solution program, a fault diagnosis program, and the like have been proposed (see Patent Documents 1 and 2).

特開２０１２−００３７３３号公報JP 2012-003733 A 特開２０１１−０７０５１５号公報Japanese Patent Application Laid-Open No. 2011-070515

しかしながら、上述した従来の特許文献１、２の開示技術は、特にＳＡＴの所与の問題に対する解をより高速かつ効率的に探索する方法を提案する技術ではない。情報量が増大の一途を辿る昨今において、大量の情報から高速かつ効率的にＳＡＴの解を求めるための社会的要請が高くなると考えられるが、これについて特段の解決策が提案されていないのが現状であった。   However, the conventional techniques disclosed in Patent Documents 1 and 2 described above are not techniques that propose a method for searching for a solution for a given problem of SAT more quickly and efficiently. With the ever-increasing amount of information, it is thought that social demands to find a SAT solution quickly and efficiently from a large amount of information will increase, but no specific solution has been proposed for this. It was the current situation.

本発明は、上述した問題点に鑑みて案出されたものであり、その目的は、高速かつ効率的にＳＡＴ問題を解くことが可能な解探索システム及び方法、解探索プログラムを提供することにある。   The present invention has been devised in view of the above-described problems, and an object thereof is to provide a solution search system and method, and a solution search program that can solve a SAT problem efficiently at high speed. is there.

本発明に係る解探索システムは、２値化されたデータを出力可能とし、揺らぎを持つデータを出力する複数のデータ生成ユニットと、上記データ生成ユニットから出力されたデータを読み取って情報に変換するデータ変換手段と、何れかの上記各データ生成ユニットに出力調節信号を送信することにより、上記データの出力を調節する出力調節手段と、上記データ変換手段により変換された情報及び予め入力された探索問題情報に基づいて、上記出力調節手段による出力調節信号の送信を上記データ生成ユニット毎に制御するフィードバック制御手段とを備え、上記フィードバック制御手段は、上記出力調節信号の送信制御の繰り返しを経て最終的に上記データ変換手段により変換された上記データ生成ユニットからの出力データに関する情報に基づき、上記探索問題情報に対する探索解を表示するとともに、上記データ生成ユニットにおけるデータ出力の揺らぎを調節する揺らぎ調節手段を更に備え、上記揺らぎ調節手段は、上記出力調節信号が既に送信されているデータ生成ユニットの数が多くなるにつれて、上記出力調節信号が既に送信されているデータ生成ユニットについて上記２値化されたデータの一方の出力頻度を高くするとともに、上記出力調節信号が送信されていないデータ生成ユニットについて２値化されたデータの他方の出力頻度を高くすることにより、上記データ生成ユニットの状態の空間的な分布に基づいて、上記各データ生成ユニットからのデータ出力の揺らぎを調節することを特徴とする。
また、本発明に係る解探索システムは、２値化されたデータを出力可能とし、揺らぎを持つデータを出力する複数のデータ生成ユニットと、上記データ生成ユニットから出力されたデータを読み取って情報に変換するデータ変換手段と、何れかの上記各データ生成ユニットに出力調節信号を送信することにより、上記データの出力を調節する出力調節手段と、上記データ変換手段により変換された情報及び予め入力された探索問題情報に基づいて、上記出力調節手段による出力調節信号の送信を上記データ生成ユニット毎に制御するフィードバック制御手段とを備え、上記フィードバック制御手段は、上記出力調節信号の送信制御の繰り返しを経て最終的に上記データ変換手段により変換された上記データ生成ユニットからの出力データに関する情報に基づき、上記探索問題情報に対する探索解を表示するとともに、上記データ生成ユニットにおけるデータ出力の揺らぎを調節する揺らぎ調節手段を更に備え、上記揺らぎ調節手段は、時間経過に応じて、上記出力調節信号が既に送信されているデータ生成ユニットについて上記２値化されたデータの一方の出力頻度を高くするとともに、上記出力調節信号が未だ送信されていないデータ生成ユニットについて２値化されたデータを交互に出力する頻度を高くすることにより、上記データ生成ユニットにおける出力データの時系列が時間相関をもつように上記データ生成ユニットからのデータ出力の揺らぎを調節することを特徴とする。 The solution search system according to the present invention is capable of outputting binarized data, and a plurality of data generation units that output data having fluctuations, and the data output from the data generation unit is read and converted into information. A data conversion means; an output adjustment means for adjusting the output of the data by transmitting an output adjustment signal to any one of the data generation units; information converted by the data conversion means; and a search inputted in advance Feedback control means for controlling transmission of the output adjustment signal by the output adjustment means for each of the data generation units based on the problem information, and the feedback control means is finally subjected to repetition of transmission control of the output adjustment signal. Information on the output data from the data generation unit converted by the data conversion means. A search solution for the search problem information is displayed based on the information, and further includes fluctuation adjusting means for adjusting fluctuation of data output in the data generation unit, wherein the fluctuation adjusting means has the output adjustment signal already transmitted. As the number of data generation units increases, the frequency of output of one of the binarized data is increased for the data generation units for which the output adjustment signal has already been transmitted, and the output adjustment signal is transmitted. The fluctuation of the data output from each data generation unit is adjusted based on the spatial distribution of the state of the data generation unit by increasing the output frequency of the other binarized data for the non-data generation unit It is characterized by doing.
In addition, the solution search system according to the present invention is capable of outputting binarized data, reading a plurality of data generation units that output data having fluctuations, and data output from the data generation unit as information. Data conversion means for conversion, output adjustment means for adjusting the output of the data by transmitting an output adjustment signal to any one of the data generation units, information converted by the data conversion means and previously inputted Feedback control means for controlling transmission of the output adjustment signal by the output adjustment means for each data generation unit based on the search problem information, and the feedback control means repeats transmission control of the output adjustment signal. After that, the output data from the data generation unit finally converted by the data conversion means A search solution for the search problem information is displayed based on the information, and further includes fluctuation adjusting means for adjusting fluctuation of data output in the data generation unit, the fluctuation adjusting means being configured to output the output according to the passage of time. The output frequency of one of the binarized data is increased for the data generation unit for which the adjustment signal has already been transmitted, and the binarized data for the data generation unit for which the output adjustment signal has not yet been transmitted. The fluctuation of the data output from the data generation unit is adjusted so that the time series of the output data in the data generation unit has a time correlation by increasing the frequency of alternately outputting.

本発明に係る解探索プログラムは、２値化されたデータを出力可能とする複数のデータ生成ユニットから、揺らぎを持つデータを出力させるデータ出力ステップと、上記データ生成ユニットから出力させたデータを読み取って情報に変換するデータ変換ステップと、何れかの上記各データ生成ユニットにおけるデータの出力を調節する出力調節ステップと、上記データ変換ステップにおいて変換した情報及び予め入力された探索問題情報に基づいて、上記出力調節ステップにおける出力調節を上記データ生成ユニット毎に制御し、上記出力調節ステップにおける調節の繰り返しを経て最終的に上記データ変換ステップにおいて変換された上記データ生成ユニットからの出力データに関する情報に基づき、上記探索問題情報に対する探索解を表示するフィードバック制御ステップと、上記データ生成ユニットにおけるデータ出力の揺らぎを調節する揺らぎ調節ステップを有し、上記揺らぎ調節ステップでは、上記出力調節信号が既に送信されているデータ生成ユニットの数が多くなるにつれて、上記出力調節信号が既に送信されているデータ生成ユニットについて上記２値化されたデータの一方の出力頻度を高くするとともに、上記出力調節信号が送信されていないデータ生成ユニットについて２値化されたデータの他方の出力頻度を高くすることにより、上記データ生成ユニットの空間的な分布に基づいて、上記各データ生成ユニットからのデータ出力の揺らぎを調節することをコンピュータに実行させることを特徴とする。
また、本発明に係る解探索プログラムは、２値化されたデータを出力可能とする複数のデータ生成ユニットから、揺らぎを持つデータを出力させるデータ出力ステップと、上記データ生成ユニットから出力させたデータを読み取って情報に変換するデータ変換ステップと、何れかの上記各データ生成ユニットにおけるデータの出力を調節する出力調節ステップと、上記データ変換ステップにおいて変換した情報及び予め入力された探索問題情報に基づいて、上記出力調節ステップにおける出力調節を上記データ生成ユニット毎に制御し、上記出力調節ステップにおける調節の繰り返しを経て最終的に上記データ変換ステップにおいて変換された上記データ生成ユニットからの出力データに関する情報に基づき、上記探索問題情報に対する探索解を表示するフィードバック制御ステップと、上記データ生成ユニットにおけるデータ出力の揺らぎを調節する揺らぎ調節ステップを有し、上記揺らぎ調節ステップでは、上記出力調節信号が既に送信されているデータ生成ユニットの数が多くなるにつれて、時間経過に応じて、上記出力調節信号が既に送信されているデータ生成ユニットについて上記２値化されたデータの一方の出力頻度を高くするとともに、上記出力調節信号が送信されていないデータ生成ユニットについて２値化されたデータの他方の出力頻度を高くすることにより、上記データ生成ユニットにおける出力データの時系列が時間相関をもつように上記データ生成ユニットからのデータ出力の揺らぎを調節することをコンピュータに実行させること特徴とする。 Solution search program according to the present invention, read from a plurality of data generation unit which enables outputs binarized data, a data output step of outputting the data having fluctuations, the data is output from the data generating unit Based on the data conversion step for converting the information into information, the output adjustment step for adjusting the output of the data in any one of the data generation units, the information converted in the data conversion step, and the search problem information input in advance, Based on the information on the output data from the data generation unit , which is controlled for each data generation unit in the output adjustment step, and is finally converted in the data conversion step after repeating the adjustment in the output adjustment step. Represents the search solution for the search problem information. And a feedback control step of having a fluctuation adjusting step of adjusting the fluctuation of the data output in the data generation unit, in the fluctuation adjustment step, as the number of data generating unit power controlling signal has already been transmitted is increased The output frequency of one of the binarized data is increased for the data generation unit for which the output adjustment signal has already been transmitted, and the binarization is performed for the data generation unit for which the output adjustment signal has not been transmitted. Increasing the output frequency of the other data causes the computer to adjust fluctuation of data output from each data generation unit based on the spatial distribution of the data generation units. .
Further, the solution search program according to the present invention includes a data output step for outputting data having fluctuations from a plurality of data generation units capable of outputting binarized data, and data output from the data generation unit. A data conversion step of reading data into information, an output adjustment step of adjusting the output of data in each of the data generation units, information converted in the data conversion step, and search problem information input in advance The output adjustment in the output adjustment step is controlled for each data generation unit, and the output data from the data generation unit is finally converted in the data conversion step after repeating the adjustment in the output adjustment step. Based on the above search problem information And a fluctuation adjustment step for adjusting fluctuation of data output in the data generation unit. In the fluctuation adjustment step, the number of data generation units to which the output adjustment signal has already been transmitted is large. As the time elapses, the output frequency of one of the binarized data is increased for the data generation unit for which the output adjustment signal has already been transmitted, and the data for which the output adjustment signal has not been transmitted. By increasing the output frequency of the other of the binarized data for the generating unit, the fluctuation of the data output from the data generating unit is adjusted so that the time series of the output data in the data generating unit has a time correlation. It is characterized by having a computer execute this.

本発明に係る解探索方法は、２値化されたデータを出力可能とする複数のデータ生成ユニットから、揺らぎを持つデータを出力させるデータ出力ステップと、上記データ生成ユニットから出力させたデータを読み取って情報に変換するデータ変換ステップと、何れかの上記各データ生成ユニットにおけるデータの出力を調節する出力調節ステップと、上記データ変換ステップにおいて変換した情報及び予め入力された探索問題情報に基づいて、上記出力調節ステップにおける出力調節を上記データ生成ユニット毎に制御し、上記出力調節ステップにおける調節の繰り返しを経て最終的に上記データ変換ステップにおいて変換された上記データ生成ユニットからの出力データに関する情報に基づき、上記探索問題情報に対する探索解を表示するフィードバック制御ステップと、上記データ生成ユニットにおけるデータ出力の揺らぎを調節する揺らぎ調節ステップを有し、上記揺らぎ調節ステップでは、上記出力調節信号が既に送信されているデータ生成ユニットの数が多くなるにつれて、上記出力調節信号が既に送信されているデータ生成ユニットについて上記２値化されたデータの一方の出力頻度を高くするとともに、上記出力調節信号が送信されていないデータ生成ユニットについて２値化されたデータの他方の出力頻度を高くすることにより、上記データ生成ユニットの状態の空間的な分布に基づいて、上記各データ生成ユニットからのデータ出力の揺らぎを調節することを特徴とする。
また、本発明に係る解探索方法は、２値化されたデータを出力可能とする複数のデータ生成ユニットから、揺らぎを持つデータを出力させるデータ出力ステップと、上記データ生成ユニットから出力させたデータを読み取って情報に変換するデータ変換ステップと、何れかの上記各データ生成ユニットにおけるデータの出力を調節する出力調節ステップと、上記データ変換ステップにおいて変換した情報及び予め入力された探索問題情報に基づいて、上記出力調節ステップにおける出力調節を上記データ生成ユニット毎に制御し、上記出力調節ステップにおける調節の繰り返しを経て最終的に上記データ変換ステップにおいて変換された上記データ生成ユニットからの出力データに関する情報に基づき、上記探索問題情報に対する探索解を表示するフィードバック制御ステップと、上記データ生成ユニットにおけるデータ出力の揺らぎを調節する揺らぎ調節ステップを有し、上記揺らぎ調節ステップでは、上記出力調節信号が既に送信されているデータ生成ユニットの数が多くなるにつれて、時間経過に応じて、上記出力調節信号が既に送信されているデータ生成ユニットについて上記２値化されたデータの一方の出力頻度を高くするとともに、上記出力調節信号が送信されていないデータ生成ユニットについて２値化されたデータの他方の出力頻度を高くすることにより、上記データ生成ユニットにおける出力データの時系列が時間相関をもつように上記データ生成ユニットからのデータ出力の揺らぎを調節することを特徴とする。 Solution search method according to the present invention, read from a plurality of data generation unit which enables outputs binarized data, a data output step of outputting the data having fluctuations, the data is output from the data generating unit Based on the data conversion step for converting the information into information, the output adjustment step for adjusting the output of the data in any one of the data generation units, the information converted in the data conversion step, and the search problem information input in advance, Based on the information on the output data from the data generation unit , which is controlled for each data generation unit in the output adjustment step, and is finally converted in the data conversion step after repeating the adjustment in the output adjustment step. , Display the search solution for the search problem information And fed back control step, as has the fluctuation adjustment step of adjusting the fluctuation of the data output in the data generation unit, in the fluctuation adjustment step, the number of data generating unit power controlling signal has already been transmitted is increased, The output frequency of one of the binarized data is increased for the data generation unit for which the output adjustment signal has already been transmitted, and the binarized data for the data generation unit for which the output adjustment signal has not been transmitted By increasing the other output frequency, the fluctuation of the data output from each data generation unit is adjusted based on the spatial distribution of the state of the data generation unit .
The solution search method according to the present invention includes a data output step for outputting data having fluctuations from a plurality of data generation units capable of outputting binarized data, and data output from the data generation unit. A data conversion step of reading data into information, an output adjustment step of adjusting the output of data in each of the data generation units, information converted in the data conversion step, and search problem information input in advance The output adjustment in the output adjustment step is controlled for each data generation unit, and the output data from the data generation unit is finally converted in the data conversion step after repeating the adjustment in the output adjustment step. The search solution for the search problem information is expressed based on And a fluctuation adjustment step for adjusting fluctuation of data output in the data generation unit. In the fluctuation adjustment step, as the number of data generation units to which the output adjustment signal has already been transmitted increases. A data generation unit in which the output frequency of one of the binarized data is increased for a data generation unit to which the output adjustment signal has already been transmitted over time, and the output adjustment signal has not been transmitted. By adjusting the output frequency of the other of the binarized data with respect to the data generation unit, the fluctuation of the data output from the data generation unit is adjusted so that the time series of the output data in the data generation unit has a time correlation. Features.

上述した構成からなる本発明によれば、複数のデータ生成ユニットから揺らぎを持つデータを出力させることにより、高速かつ効率的にＳＡＴ問題を解くことが可能となる。   According to the present invention having the above-described configuration, it is possible to solve the SAT problem efficiently at high speed by outputting data having fluctuations from a plurality of data generation units.

特に、本発明の方法は、従来より知られているSAT問題解決アルゴリズム（WalkSAT等）と比較して、解を求めるのに要する時間ステップ数（反復回数）を減少させることができ、より効率的に解を得ることが可能となる。また、本発明の技術思想を、FPGA(field-programmable gate array)等の回路で実装をすることで、上記の１ステップに必要な実時間を短縮することができ、より高速に解を得ることができる。   In particular, the method of the present invention can reduce the number of time steps (number of iterations) required to find a solution compared to a conventionally known SAT problem solving algorithm (WalkSAT etc.), and is more efficient. It is possible to obtain a solution. In addition, by implementing the technical idea of the present invention with a circuit such as an FPGA (field-programmable gate array), the real time required for the above one step can be shortened and a solution can be obtained at a higher speed. Can do.

本発明を適用した解探索システムの全体構成を示す図である。It is a figure which shows the whole structure of the solution search system to which this invention is applied. 出力調節信号の送信によるデータ生成ユニットからの出力データの制御について説明するための図である。It is a figure for demonstrating control of the output data from the data generation unit by transmission of an output adjustment signal. 出力調節信号の送信によるデータ生成ユニットからの出力データの制御について説明するための他の図である。It is another figure for demonstrating control of the output data from the data generation unit by transmission of an output adjustment signal. 与えられたブール式Ｆ１１〜Ｆ１６の論理積を１（“真”）にするための命題論理式を示す図である。It is a figure which shows the propositional logical expression for making the logical product of the given Boolean expressions F11-F16 into 1 ("true"). １の変数への値の割当てを２つのデータ変換ユニットで表現する場合について説明するための図である。It is a figure for demonstrating the case where the assignment of the value to 1 variable is expressed with two data conversion units. 空間相関に基づいて揺らぎが設定される状況について説明するための図である。It is a figure for demonstrating the condition where fluctuation is set based on a spatial correlation. 空間相関に基づく揺らぎを設定する例について説明するための図である。It is a figure for demonstrating the example which sets the fluctuation | variation based on a spatial correlation. 時間相関に基づく揺らぎを設定する例について説明するための図である。It is a figure for demonstrating the example which sets the fluctuation | variation based on a time correlation. 本発明を適用した解探索システムの効果について説明するための図である。It is a figure for demonstrating the effect of the solution search system to which this invention is applied.

以下、本発明を適用した解探索システムについて図面を参照しながら詳細に説明をする。   Hereinafter, a solution search system to which the present invention is applied will be described in detail with reference to the drawings.

図１は、本発明を適用した解探索システム１の全体構成を示している。解探索システム１は、複数のデータ生成ユニット１１−１、１１−２、・・・、１１−ｉと、データ生成ユニットから出力されたデータを読み取り可能な複数のデータ変換部１２−１、１２−２、・・・、１２−ｉと、このデータ変換部１２に接続されるフィードバック制御部１３と、このフィードバック制御部１３に接続された出力調節部１４と、複数のデータ生成ユニット１１−１、１１−２、・・・、１１−ｉにそれぞれ接続され、更にフィードバック制御部１３にも接続される揺らぎ調節部１５とを備えている。   FIG. 1 shows the overall configuration of a solution search system 1 to which the present invention is applied. The solution search system 1 includes a plurality of data generation units 11-1, 11-2,..., 11-i and a plurality of data conversion units 12-1, 12 that can read data output from the data generation units. ,..., 12-i, a feedback control unit 13 connected to the data conversion unit 12, an output adjustment unit 14 connected to the feedback control unit 13, and a plurality of data generation units 11-1. 11-2,..., 11-i, and a fluctuation adjusting unit 15 connected to the feedback control unit 13.

ちなみに、これらデータ生成ユニット１１、データ変換部１２、フィードバック制御部１３、出力調節部１４、揺らぎ調節部１５の各構成要素は、これらの機能を発揮するいかなる既存の回路やデバイス、装置等で具現化されるものであってもよい。   Incidentally, each component of the data generation unit 11, the data conversion unit 12, the feedback control unit 13, the output adjustment unit 14, and the fluctuation adjustment unit 15 is embodied in any existing circuit, device, apparatus, or the like that exhibits these functions. It may be made.

データ生成ユニット１１−１、１１−２、・・・、１１−ｉは、それぞれデータを出力する。このデータ生成ユニット１１−１、１１−２、・・・、１１−ｉから出力されるデータは、２値化されたデジタルデータであってもよいし、アナログデータであってもよいが、以下の説明では、“１”又は“０”の何れかを出力する場合を例にとり説明をする。また、このデータ生成ユニット１１−１、１１−２、・・・、１１−ｉの何れか１以上は、出力調節部１４から出力されてくる出力調節信号を受信する。そして、この出力調節信号を受信したデータ生成ユニット１１は、これに基づいて出力すべきデータが制御される。   The data generation units 11-1, 11-2,..., 11-i each output data. The data output from the data generation units 11-1, 11-2,..., 11-i may be binarized digital data or analog data. In the description, the case where either “1” or “0” is output will be described as an example. Any one or more of the data generation units 11-1, 11-2,..., 11-i receives the output adjustment signal output from the output adjustment unit 14. And the data generation unit 11 which received this output adjustment signal controls the data which should be output based on this.

図２に示すように、一のデータ生成ユニット１１−１に着目すると、当該データ生成ユニット１１−１に対して出力調節信号が供給された場合、データ生成ユニット１１−１は“０”を出力する頻度が高くなる。   As shown in FIG. 2, when focusing on one data generation unit 11-1, when an output adjustment signal is supplied to the data generation unit 11-1, the data generation unit 11-1 outputs "0". The frequency to do becomes high.

また図３に示すように、一のデータ生成ユニット１１−１に着目すると、当該データ生成ユニット１１−１に対して出力調節信号が供給されない場合、データ生成ユニット１１−１は“１”を出力する頻度が高くなる。   Also, as shown in FIG. 3, when focusing on one data generation unit 11-1, when no output adjustment signal is supplied to the data generation unit 11-1, the data generation unit 11-1 outputs "1". The frequency to do becomes high.

ちなみに、このデータ生成ユニット１１は、上述した機能を実現できるものであればいかなる形態で具現化されるものであってもよい。データ生成ユニット１１は、例えば、“１”又は“０”の何れかを一定時間間隔で出力可能な回路ユニットで構成してもよいし、また本発明をコンピュータに実行させるためのプログラムで具現化する際には、仮想的に定義された概念的な構成要素として考えることも可能となる。   Incidentally, the data generation unit 11 may be embodied in any form as long as the function described above can be realized. The data generation unit 11 may be constituted by a circuit unit that can output either “1” or “0” at regular time intervals, or may be embodied by a program for causing a computer to execute the present invention. In doing so, it can also be considered as a conceptual component that is virtually defined.

このようなデータ生成ユニット１１から出力されるデータは、無相関の確率的乱数のようにランダムに出力されるもののみならず、カオス力学系や非線形振動子結合系のようなシステムから出力される空間相関や時間相関をもつ揺らぎをともなった状態で出力されるものを含める。この出力されるデータに持たせる揺らぎの特性は、揺らぎ調節部１５に基づいて決定される。   Such data output from the data generation unit 11 is output not only from the random output such as uncorrelated stochastic random numbers, but also from a system such as a chaotic dynamical system or a nonlinear oscillator coupling system. Include output that is output with fluctuations that have spatial or temporal correlation. The fluctuation characteristic to be given to the output data is determined based on the fluctuation adjusting unit 15.

データ変換部１２−１、１２−２、・・・１２−ｉは、データ生成ユニット１１−１、１１−２、・・・、１１−ｉから出力されてくるデータを読み取り、これを情報に変換する。このデータ変換部１２は、データ生成ユニット１１から、例えばデジタルデータとして“１”が出力されてきた場合には、これを読み取り、これに応じた情報として現ステップの値に“＋１”を加算した値を出力する。また、データ変換部１２は、データ生成ユニット１１から、例えばデジタルデータとして“０”が出力されてきた場合には、これを読み取り、これに応じた情報として現ステップの値に“−１”を加算した値を出力する。ただし、データ変換部１２の取り得る値は、その最大値が2、最小値が−2となるように制限しても良い。その場合、データ変換部１２の取り得る値は、−2、−1、0、1、2の５種類のうちのいずれかとなる。そのために、データ変換部１２の現ステップの値が2の場合はデータ生成ユニット１１からの出力データの値とは無関係に次ステップで値１を出力し、データ変換部１２の現ステップの値が−2の場合はデータ生成ユニット１１からの出力データの値とは無関係に次ステップで値−1を出力することにする。ちなみに、このデータ変換部１２から出力される情報としては、上述したものに限定されることなく、あくまでデータ生成ユニット１１からのデータに基づくものであればいかなるものであってもよい。   The data conversion units 12-1, 12-2,... 12-i read the data output from the data generation units 11-1, 11-2,. Convert. For example, when “1” is output as digital data from the data generation unit 11, the data conversion unit 12 reads this and adds “+1” to the value of the current step as information corresponding thereto. Output the value. Further, when “0” is output as digital data, for example, from the data generation unit 11, the data conversion unit 12 reads this, and sets “−1” as the value of the current step as information corresponding thereto. The added value is output. However, the values that the data converter 12 can take may be limited so that the maximum value is 2 and the minimum value is −2. In that case, the value that the data conversion unit 12 can take is any one of five types, -2, -1, 0, 1, and 2. Therefore, when the value of the current step of the data conversion unit 12 is 2, the value 1 is output in the next step regardless of the value of the output data from the data generation unit 11, and the value of the current step of the data conversion unit 12 is In the case of −2, the value −1 is output in the next step regardless of the value of the output data from the data generation unit 11. Incidentally, the information output from the data converter 12 is not limited to the information described above, and may be any information as long as it is based on data from the data generation unit 11 to the last.

このようにしてデータ変換部１２−１、１２−２、・・・１２−ｉは、個々のデータ生成ユニット１１−１、１１−２、・・・、１１−ｉから出力されてくるデータを読み取り、その出力された個々のデータに基づいてそれぞれ情報変換を行う。データ変換部１２は、この情報変換を行った情報を出力する。このとき、データ変換部１２の取り得る値−2、−1、0、1、2が正の値（0より大きい）であるか負の値(0以下)であるかを出力するようにしてもよい。また、データ変換部１２から出力する情報としては、これら正又は負の２値に限定されることなく、変換されたデータに基づくものであればいかなるものであってもよい。   In this way, the data conversion units 12-1, 12-2,... 12-i receive the data output from the individual data generation units 11-1, 11-2,. Information conversion is performed based on the read and output individual data. The data conversion unit 12 outputs information obtained by this information conversion. At this time, whether the values −2, −1, 0, 1, 2 that the data conversion unit 12 can take is a positive value (greater than 0) or a negative value (less than 0) is output. Also good. Further, the information output from the data converter 12 is not limited to these positive or negative binary values, but may be any information as long as it is based on the converted data.

ちなみに、変数がＮ個の場合に、これらデータ生成ユニット１１−１、１１−２、・・・、１１−ｉ及びデータ変換部１２−１、１２−２、・・・１２−ｉは、Ｎ個で構成するようにしてもよいし、２Ｎ個で構成するようにしてもよい。   Incidentally, when there are N variables, these data generation units 11-1, 11-2,..., 11-i and the data conversion units 12-1, 12-2,. You may make it comprise by piece, and you may make it comprise by 2N pieces.

このデータ変換部１２から出力された情報は、フィードバック制御部１３へと送られることとなる。また、この出力される情報を画面上に表示するようにしてもよい。   The information output from the data conversion unit 12 is sent to the feedback control unit 13. The output information may be displayed on the screen.

フィードバック制御部１３は、データ変換部１２により変換されて出力された情報を受信する。このフィードバック制御部１３は、受信した情報及び予め入力された探索問題情報に基づいて、出力調節部１４による出力調節信号の送信を制御する。具体的には、フィードバック制御部１３は、かかる出力調節信号が送信される各データ生成ユニット１１−１、１１−２、・・・、１１−ｉ毎に、その出力調節信号の送信の有無を制御する。また、このフィードバック制御部１３は、出力調節信号の送信制御の繰り返しを経て最終的にデータ変換手段により変換されたデータ生成ユニット情報に基づき、探索問題情報に対する探索解を表示する。この探索解の表示は、図示しないユーザインタフェースを介して表示するようにしてもよい。   The feedback control unit 13 receives the information converted and output by the data conversion unit 12. The feedback control unit 13 controls transmission of the output adjustment signal by the output adjustment unit 14 based on the received information and the search problem information input in advance. Specifically, the feedback control unit 13 determines whether or not the output adjustment signal is transmitted for each of the data generation units 11-1, 11-2, ..., 11-i to which the output adjustment signal is transmitted. Control. In addition, the feedback control unit 13 displays a search solution for the search problem information based on the data generation unit information that is finally converted by the data conversion unit through the repetition of transmission control of the output adjustment signal. The search solution may be displayed via a user interface (not shown).

出力調節部１４は、フィードバック制御部１３からの制御に基づいて、データ生成ユニット１１−１、１１−２、・・・、１１−ｉに対して出力調節信号を送信する。この出力調節信号は、フィードバック制御部１３からの制御に基づいて、全てのデータ生成ユニット１１に対して供給される場合もあれば、その逆として全てのデータ生成ユニット１１に対して供給されない場合もある。この出力調節信号が供給されたデータ生成ユニット１１は、出力調節信号が供給されないデータ生成ユニット１１と比較して、出力されるデータが異なる傾向をもつこととなる。   Based on the control from the feedback control unit 13, the output adjustment unit 14 transmits an output adjustment signal to the data generation units 11-1, 11-2, ..., 11-i. The output adjustment signal may be supplied to all the data generation units 11 based on the control from the feedback control unit 13 or may not be supplied to all the data generation units 11 in reverse. is there. The data generation unit 11 to which the output adjustment signal is supplied has a tendency that the output data is different compared to the data generation unit 11 to which the output adjustment signal is not supplied.

揺らぎ調節部１５は、データ生成ユニット１１から出力されるデータの揺らぎを調節するデバイスである。この揺らぎ調節部１５により調節されるデータの揺らぎについては後段において詳述する。   The fluctuation adjustment unit 15 is a device that adjusts fluctuation of data output from the data generation unit 11. The data fluctuation adjusted by the fluctuation adjusting unit 15 will be described in detail later.

本発明を適用した解探索システム１は、複数のデータ生成ユニット１１−１、１１−２、・・・、１１−ｉ、データ変換部１２、フィードバック制御部１３の順に処理動作が進行し、探索解が求まるまで出力調節部１４からの出力調節信号の送信を行うことで、これらの処理動作が繰り返し実行される。   In the solution search system 1 to which the present invention is applied, the processing operation proceeds in the order of the plurality of data generation units 11-1, 11-2,... These processing operations are repeatedly executed by transmitting the output adjustment signal from the output adjustment unit 14 until a solution is obtained.

次に、本発明を適用した解探索システム１の動作について説明をする。   Next, the operation of the solution search system 1 to which the present invention is applied will be described.

本発明を適用した解探索システム１では、いずれかのデータ生成ユニット１１−１、１１−２、・・・、１１−ｉに対して出力調節信号を送信し、或いは送信しないかを、予め入力された探索問題情報に基づいて制御することとなる。換言すれば、フィードバック制御部１３は、データ生成ユニット１１から出力され、データ変換部１２により変換された情報と、予め入力された探索問題情報の２つの要因に基づいて、出力調節部１４による出力調節信号の送信を制御する。   In the solution search system 1 to which the present invention is applied, whether or not to transmit an output adjustment signal to any one of the data generation units 11-1, 11-2,. Control is performed based on the search problem information. In other words, the feedback control unit 13 outputs from the output adjustment unit 14 based on two factors, the information output from the data generation unit 11 and converted by the data conversion unit 12 and the search problem information input in advance. Controls the transmission of adjustment signals.

ここでいう探索問題情報とは、命題論理式で表されるあらゆる問題情報を含むものである。この探索問題情報とは、最適解探索問題に関するあらゆる問題情報と解されるものであってもよい。この探索問題情報は、例えば、Ｎ個の変数からなる命題論理式で表されるものであってもよい。この探索問題情報は、（ｐ0？ｐ1？・・・・？ｐn）＝“真”("１")又は“偽”("0")、（ここで？は、論理和（or）、論理積（and）等を始めとしたいかなる演算記号を適用してもよい。）で表される。 The search problem information here includes all problem information expressed by a propositional logical expression. This search problem information may be interpreted as any problem information related to the optimal solution search problem. This search problem information may be expressed by a propositional logical expression composed of N variables, for example. The search problem information is (p 0 ? P 1 ?... P n ) = “true” (“1”) or “false” (“0”), where “? ), Any operation symbol including logical product (and), etc. may be applied.

この解探索システム１に探索問題情報の探索解を探索させる上で、データ生成ユニット１１から出力され、データ変換部１２により変換された情報に応じて、探索問題情報として命題論理式を満たさないものを排除するように、出力調節信号の供給制御を行う。これを利用することで、例えば探索問題情報として、命題論理式の全体の値を“真” ("１")にするために充足可能な変数を探索する充足可能性問題（Satisfiability Problem, SAT）を与えることで、その解を探索することも可能となる。   When the solution search system 1 searches for a search solution of search problem information, according to the information output from the data generation unit 11 and converted by the data converter 12, the propositional logical expression is not satisfied as the search problem information The supply of the output adjustment signal is controlled so as to eliminate the above. By using this, for example, as a search problem information, a satisfiability problem (SAT) that searches for variables that can be satisfied to make the entire value of the propositional formula “true” (“1”). It is also possible to search for the solution.

例えば図４は、与えられたブール式Ｆ１１〜Ｆ１６の論理積を１（“真”）にするための命題論理式を示している。この命題論理式は、４個の変数と、６個の節をもつ式である。論理積を１とするためには、各節を全て１にしなければならないことが分かる。Ｆ１１に着目した場合に、仮にｘ1が“０”である場合には、ｘ2を“０”にしない限りＦ１１を“１”にすることができない。かかる場合には、ｘ2が“１”であることを打ち消すような制御を行う。また、ｘ2が“１”である場合には、ｘ1が“０”であるとＦ１１を“１”にすることができない。かかる場合には、ｘ1が“０”であることを打ち消すような制御を行う。 For example, FIG. 4 shows a propositional logical expression for setting a logical product of given Boolean expressions F11 to F16 to 1 (“true”). This propositional formula is an expression having four variables and six clauses. It can be seen that in order to set the logical product to 1, all the clauses must be set to 1. When attention is focused on the F11, if when x 1 is "0" can not be "1" to F11 unless you the x 2 "0". In such a case, control is performed to cancel that x 2 is “1”. Further, when x 2 is “1”, F 11 cannot be set to “1” if x 1 is “0”. In such a case, control is performed to cancel that x 1 is “0”.

また、Ｆ１２に着目した場合、ｘ3が“０”かつｘ4が“1”である場合には、ｘ2が“０”であるとＦ１２を“１”にすることができない。かかる場合には、ｘ2が“１”であることを打ち消すような制御を行う。同様にｘ2が“1”でｘ3が“０”である場合には、ｘ4が“1”であるとＦ１２を“１”にすることができない。かかる場合には、ｘ4が“１”であることを打ち消すような制御を行う。同様にｘ2が“1”でｘ4が“1”である場合には、ｘ3が“０”であるとＦ１２を“１”にすることができない。かかる場合には、ｘ3が“０”であることを打ち消すような制御を行う。 Furthermore, when focusing on F12, x 3 is the case where "0" and x 4 is "1", x 2 can not be the F12 If it is "0", "1". In such a case, control is performed to cancel that x 2 is “1”. Similarly, when x 2 is “1” and x 3 is “0”, F 12 cannot be set to “1” if x 4 is “1”. In such a case, control is performed to cancel that x 4 is “1”. Similarly, when x 2 is “1” and x 4 is “1”, if x 3 is “0”, F12 cannot be set to “1”. In such a case, control is performed to cancel that x 3 is “0”.

残りのＦ１３〜Ｆ１６についても同様の論理に基づいて、命題論理式の全体の値を“真”にするために、命題論理式を満たさないものを排除するような制御をする。これにより、命題論理式の全体の値を“真”へと導くことが可能となる。また、このような解探索を行う上で、本発明を適用した解探索システム１では、各データ変換部１２の保持する情報に応じて探索問題情報としての命題論理式を満たさないものを排除するように、各データ生成ユニット１１に対する出力調節信号の供給を行うことができる。このため、図４に例示されるような命題論理式からなる探索問題情報を与えることにより、これに沿った出力調節信号の供給動作を行い、最終的には探索問題情報としての命題論理式を満たすようなデータ変換部１２の出力状態に到達することとなる。   For the remaining F13 to F16, based on the same logic, control is performed to exclude those that do not satisfy the propositional logical expression in order to make the entire value of the propositional logical expression “true”. This makes it possible to lead the entire value of the propositional formula to “true”. Further, in performing such a solution search, the solution search system 1 to which the present invention is applied excludes those that do not satisfy the propositional logical expression as the search problem information according to the information held by each data conversion unit 12. As described above, the output adjustment signal can be supplied to each data generation unit 11. For this reason, by providing search problem information consisting of a propositional logical expression as illustrated in FIG. 4, an output adjustment signal is supplied in accordance with this, and finally, a propositional logical expression as search problem information is obtained. The output state of the data conversion unit 12 that satisfies the condition is reached.

特に図４に示すＦ１１〜Ｆ１６のような複数の節からなる命題論理式を解く場合においても、これをフィードバック制御部１３において探索問題情報として入力しておくことにより、当該探索問題情報に沿って出力調節信号の供給制御が行われ、解へと導くことが可能となる。ちなみに、図４に示す命題論理式の解は、(x1,x2,x3,x4)=(1,1,1,1)であるが、本発明を適用した解探索システム１により、この解を得ることが可能となる。 In particular, even in the case of solving a propositional logical expression consisting of a plurality of clauses such as F11 to F16 shown in FIG. 4, by inputting this as search problem information in the feedback control unit 13, the search problem information can be Supply control of the output adjustment signal is performed, and it is possible to lead to a solution. Incidentally, the solution of the propositional formula shown in FIG. 4 is (x 1 , x 2 , x 3 , x 4 ) = ( 1 , 1 , 1 , 1 ), but the solution search system 1 to which the present invention is applied is used. This solution can be obtained.

充足可能性問題(SAT)は、ソフトウェアおよびハードウェア検証、ならびに情報セキュリティー関連技術等を含む、多くのアプリケーションで使用され、今後も重要性が向上するものと考えられるが、本発明を適用した解探索システム１により、その解を自動的に求めることが可能となる。
なお、本発明では、SATの他のいかなる命題論理式をも予めフィードバック制御部１３に入力しておけば、同様の手法によりその解を得ることが可能となる。例えば、ハミルトン閉路問題や、ナップサック問題を始めとした問題をＳＡＴに変換して解くこともできるが、これらの変換機能をもフィードバック制御部１３にもたせるようにしてもよい。これにより、ＳＡＴ以外の探索問題情報が入力されていても、これをＳＡＴに変換することで解を求めることが可能となる。ちなみに、このようなＳＡＴ以外の探索問題をＳＡＴに変換する方法は、従来のいかなる手法を用いるようにしてもよい。 The satisfiability problem (SAT) is used in many applications, including software and hardware verification, information security related technologies, etc. and is expected to increase in importance in the future. The search system 1 can automatically find the solution.
In the present invention, if any other propositional logical expression of SAT is input to the feedback control unit 13 in advance, the solution can be obtained by the same method. For example, problems such as the Hamiltonian circuit problem and knapsack problem can be converted into SAT and solved, but these conversion functions may also be provided to the feedback control unit 13. Thereby, even if search problem information other than SAT is input, it is possible to obtain a solution by converting this into SAT. Incidentally, any conventional method may be used as a method for converting such a search problem other than SAT into SAT.

なお、上述したフィードバック制御を行う際には、以下のＩＮＴＲＡ、ＩＮＴＥＲ、ＣＯＮＴＲＡという３つのルールに基づいて実行していくこととなる。この３つのルールを考える際には、例えば図５に示すように１の変数への値の割当てを２つのデータ変換ユニット１２で表現する場合を想定している。この図５では、８個のデータ生成ユニット１１と、それら各々から出力されたデータを読み取る８個のデータ変換ユニット１２の状態により、４変数の真偽値("0"又は"1")を表現する場合を示している。Ｎ変数の真偽値を表現する場合には、２N個のデータ生成ユニット１１と、それら各々から出力されたデータを読み取る2N個のデータ変換ユニット１２が必要になる。この例では、２つのデータ変換ユニット１２ａ、１２ｂのペアで１の変数x1を表現する。２つのデータ変換ユニット１２ｃ、１２ｄのペアで１の変数x2を表現する。２つのデータ変換ユニット１２ｅ、１２ｆのペアで１の変数x3を表現する。２つのデータ変換ユニット１２ｇ、１2ｈのペアで１の変数x4を表現する。また、各変数x1〜x4においてデータ変換ユニット１２ａ、１2ｃ、１2ｅ、１2ｇはそれぞれの変数xiに値“０”が割当てられることを表現するものであり、データ変換ユニット１２ｂ、１2ｄ、１2ｆ、１2ｈはそれぞれの変数xiに値“０”が割当てられることを表現するものである。 In addition, when performing the feedback control mentioned above, it will perform based on the following three rules, INTRA, INTER, and CONTRA. When considering these three rules, for example, it is assumed that the assignment of a value to one variable is expressed by two data conversion units 12 as shown in FIG. In FIG. 5, the true / false values (“0” or “1”) of four variables are obtained depending on the states of the eight data generation units 11 and the eight data conversion units 12 that read the data output from each. The case of expressing is shown. In the case of expressing the truth value of the N variable, 2N data generation units 11 and 2N data conversion units 12 for reading data output from each of them are required. In this example, one variable x 1 is expressed by a pair of two data conversion units 12a and 12b. Two data conversion unit 12c, representing one of the variables x 2 in 12d pair. Two data conversion unit 12e, representing one of the variables x 3 in 12f pairs. Two data conversion unit 12g, representing one of the variables x 4 pairs of 12h. In each of the variables x 1 to x 4 , the data conversion units 12a, 12c, 12e, and 12g express that the value “0” is assigned to each variable x i , and the data conversion units 12b, 12d, and 12f. 12 h represents that the value “0” is assigned to each variable x i .

このようなデータ変換ユニット１２により例えば４変数の真偽値割当を表現したい場合、例えば、データ変換ユニット１２ｂ、１２ｄ、１２ｆ、１２ｈのみが正の値(0より大きい)をとり、データ変換ユニット１２ａ、１２ｃ、１２ｅ、１２ｇは負の値(0以下)をとるとき、真偽値割当(x1,x2,x3,x4)=(1,1,1,1)が表現されることとなる。データ変換ユニット１２ａ、１２ｄ、１２ｅ、１２ｈのみが正の値をとるとき、これは真偽値割当（０１０１）を表す。またデータ変換ユニット１２ｂ、１２ｃ、１２ｆ、１２ｇのみが正の値をとるとき、これは真偽値割当（１０１０）を表す。 For example, when it is desired to express the Boolean value assignment of four variables by such a data conversion unit 12, for example, only the data conversion units 12b, 12d, 12f, and 12h take positive values (greater than 0), and the data conversion unit 12a , 12c, 12e, and 12g are expressed as true / false value assignments (x 1 , x 2 , x 3 , x 4 ) = ( 1 , 1 , 1 , 1 ) when taking negative values (0 or less) It becomes. When only the data conversion units 12a, 12d, 12e, 12h take a positive value, this represents a true / false value assignment (0101). When only the data conversion units 12b, 12c, 12f, and 12g take a positive value, this represents a true / false value assignment (1010).

このようなＮ変数の真偽値割当を表現する２Ｎ個のデータ変換ユニット１２を用いる場合において、ＩＮＴＲＡは、１の変数xiの真偽値を表現するデータ変換ユニット１２のペアに着目した場合において、それらの双方が正の値をとる状態（変数xiが値“０”でありかつ値“1”であるという矛盾）が生じないようにするための出力調節信号の供給ルールである。そのために、１の変数xiに対応するデータ変換ユニット１２のペアの一方が正の値をとるならば、他方のデータ変換ユニット１２が正の値をとらなくなるように、当該データ生成ユニット１１に出力調節信号の供給制御を行うこととなる。 In the case of using 2N data conversion units 12 expressing such a true / false value assignment of N variables, INTRA focuses on a pair of data conversion units 12 expressing a true / false value of one variable x i , The output adjustment signal supply rule for preventing the occurrence of a state in which both of them take a positive value (the contradiction that the variable x i is the value “0” and the value “1”). Therefore, if one of the pairs of data conversion units 12 corresponding to one variable x i takes a positive value, the data generation unit 11 is set so that the other data conversion unit 12 does not take a positive value. Supply control of the output adjustment signal is performed.

Figure 0006011928
Figure 0006011928

表１に、図４に示す命題論理式に対応するフィードバック制御を行うＩＮＴＲＡ、ＩＮＴＥＲ、ＣＯＮＴＲＡの例を示す。この表１においてＩＮＴＲＡ、ＩＮＴＥＲ、ＣＯＮＴＲＡの要素は、何れも[Ｐ、Ｑ]という形式で示される。これは、「Ｐが成り立つならばＱが成り立たないように制御する」という意味である。すなわち、「Pが要素として含む変数とその真偽値に対応するデータ変換ユニット１２が正の値をとるならば、Qが要素として含む変数とその真偽値に対応するデータ生成ユニット１１がデータ“１”を出力する確率が低下するように出力調節信号を供給する」という意味である。   Table 1 shows examples of INTRA, INTER, and CONTRA that perform feedback control corresponding to the propositional logical expression shown in FIG. In Table 1, the elements of INTRA, INTER, and CONTRA are all shown in the format [P, Q]. This means that “control is performed so that Q does not hold if P holds”. That is, if the data conversion unit 12 corresponding to the variable that P includes as an element and its true / false value takes a positive value, the data generation unit 11 that corresponds to the variable that Q includes as an element and its true / false value This means that the output adjustment signal is supplied so that the probability of outputting “1” decreases.

先ずＩＮＴＲＡについて、例えば、ｘ1が“０”である場合には、ｘ1が“１”である状態を打ち消すように出力調節信号を供給する。ｘ1が“１”である場合には、ｘ1が“０”である状態を打ち消すように出力調節信号を供給する。このために、ｘ1の“１”に対応するデータ変換ユニット１２が正の値をとった場合には、ｘ1の“０”に対応するデータ変換ユニット１２が正の値をとることを抑制するために、当該データ生成ユニット１１へ出力調節信号を供給する。同様に、ｘ1の“０”に対応するデータ変換ユニット１２が正の値をとった場合には、ｘ1の“１”に対応するデータ変換ユニット１２が正の値をとることを抑制するために、当該データ生成ユニット１１へ出力調節信号を供給する。残りのｘ2〜ｘ4についても、このＩＮＴＲＡの表に従って出力調節信号の供給制御が行われることとなる。 First, for INTRA, for example, when x 1 is “0”, an output adjustment signal is supplied so as to cancel the state where x 1 is “1”. When x 1 is “1”, the output adjustment signal is supplied so as to cancel the state where x 1 is “0”. For this reason, when the data conversion unit 12 corresponding to “1” of x 1 takes a positive value, the data conversion unit 12 corresponding to “0” of x 1 is prevented from taking a positive value. In order to do so, an output adjustment signal is supplied to the data generation unit 11. Similarly, when the data conversion unit 12 corresponding to “0” of x 1 takes a positive value, the data conversion unit 12 corresponding to “1” of x 1 is prevented from taking a positive value. Therefore, an output adjustment signal is supplied to the data generation unit 11. For the remaining x 2 to x 4 , the supply control of the output adjustment signal is performed according to this INTRA table.

ＩＮＴＥＲは、与えられた探索問題情報に基づいた出力調節信号の供給ルールである。例えば、図４におけるＦ１１に着目した場合、ｘ2の“１”に対応するデータ変換ユニット１２が正の値をとった場合には、ｘ1の“０”に対応するデータ変換ユニット１２が正の値をとることを抑制するために、当該データ生成ユニット１１へ出力調節信号を供給する。同様に、ｘ1の“０”に対応するデータ変換ユニット１２が正の値をとった場合には、ｘ2の“１”に対応するデータ変換ユニット１２が正の値をとることを抑制するために、当該データ生成ユニット１１へ出力調節信号を供給する。 INTER is an output adjustment signal supply rule based on given search problem information. For example, when focusing on F11 in FIG. 4, when the data conversion unit 12 corresponding to "1" x 2 took a positive value, the data conversion unit 12 corresponding to the "0" x 1 positive Is supplied to the data generation unit 11 in order to suppress the value of. Similarly, when the data conversion unit 12 corresponding to “0” of x 1 takes a positive value, the data conversion unit 12 corresponding to “1” of x 2 is prevented from taking a positive value. Therefore, an output adjustment signal is supplied to the data generation unit 11.

表１において、このＩＮＴＥＲについても、その要素は、何れも[Ｐ、Ｑ]という形式で示される。Ｐについてｘ2が“１”である場合には、Ｑに示すようにｘ1が“０”である状態を打ち消すように出力調節信号を供給する。Ｐについてｘ1が“０”である場合には、Ｑに示すようにｘ2が“１”である状態を打ち消すように出力調節信号を供給する。Ｐについてｘ3が“０”であり、かつ、ｘ4が“１”である場合に、Ｑに示すようにｘ2が“１”である状態を打ち消すように出力調節信号を供給する。これ以下についても同様にＩＮＴＥＲの表に従って出力調節信号の供給制御が行われることとなる。 In Table 1, all elements of this INTER are shown in the format [P, Q]. When x 2 is “1” for P, the output adjustment signal is supplied so as to cancel the state where x 1 is “0” as indicated by Q. When x 1 is “0” for P, the output adjustment signal is supplied so as to cancel the state where x 2 is “1” as indicated by Q. For P, when x 3 is “0” and x 4 is “1”, an output adjustment signal is supplied so as to cancel the state where x 2 is “1” as indicated by Q. Similarly, the supply control of the output adjustment signal is performed in accordance with the INTER table.

このように、ＩＮＴＥＲは、探索問題情報として与えられた論理式の１の節を構成する１の変数に着目した場合に、当該節を構成する他の変数との論理和が“真”を構成しない場合（上述の例でいえば、１の変数：ｘ2が“１”、他の変数：ｘ1が“０”、である場合等）には、他の変数（ｘ1が“０”）を表すデータ生成ユニット１１からのデータ出力状態を打ち消すように、出力調節信号の供給を制御する。「ｘ1が“０”」の状態が打ち消されれば、「ｘ1が“１”」となることを誘導し得る。 In this way, when INTER pays attention to one variable that constitutes one clause of a logical expression given as search problem information, the logical sum with other variables that constitute that clause constitutes “true”. If not (in the above example, 1 variable: x 2 is “1”, other variable: x 1 is “0”, etc.), another variable (x 1 is “0”). The supply of the output adjustment signal is controlled so as to cancel the data output state from the data generation unit 11 representing). If the state of “x 1 is“ 0 ”” is canceled, it can be induced that “x 1 is“ 1 ””.

また、ＣＯＮＴＲＡは、上述のＩＮＴＥＲに基づいて出力調節信号の供給制御を行おうとする場合に生じる論理矛盾を解消するための出力調節信号の供給ルールである。   CONTRA is a rule for supplying an output adjustment signal for eliminating a logic contradiction that occurs when an output adjustment signal is supplied based on the above INTER.

INTERにおいて、例えば、Ｑに含まれるｘ1に着目した場合に、ｘ2が“１”である場合に、ｘ1が“０”である状態を打ち消すルール、ｘ3が“０”である場合に、ｘ1が“０”である状態を打ち消すルールが定義されている。またｘ4が“０”である場合に、ｘ1が“１”である状態を打ち消すルールが定義されている。このため、例えば、ｘ2が“１”であり、かつ、ｘ4が“０”である場合に、ｘ1が“０”である状態も“１”である状態も打ち消されるという、論理矛盾が生じてしまう。こうした事態を防ぐために、かかる場合には、ｘ2が“１”である状態と、ｘ4が“０”である状態が同時に生じないように制御する。具体的には、ｘ2が“１”であることを表現するデータ変換ユニット１２が正の値をとり、かつ、ｘ4が“０” であることを表現するデータ変換ユニット１２が正の値をとる場合には、次ステップにおいて、それらに対応する２つのデータ生成ユニット１１に対して出力調節信号を供給することで、対応するデータ変換ユニット１２が正の値をとることを抑制する制御を行うこととなる。 In INTER, for example, when focusing on x 1 included in Q, when x 2 is “1”, a rule that cancels the state where x 1 is “0”, and when x 3 is “0” In addition, a rule for canceling a state where x 1 is “0” is defined. Further, a rule is defined to cancel the state where x 1 is “1” when x 4 is “0”. For this reason, for example, when x 2 is “1” and x 4 is “0”, both the state where x 1 is “0” and the state where “1” are canceled out. Will occur. In order to prevent such a situation, in such a case, control is performed so that a state where x 2 is “1” and a state where x 4 is “0” do not occur simultaneously. Specifically, the data conversion unit 12 expressing that x 2 is “1” takes a positive value, and the data conversion unit 12 expressing that x 4 is “0” is a positive value. In the next step, in the next step, by supplying an output adjustment signal to the two data generation units 11 corresponding to them, control for suppressing the corresponding data conversion unit 12 from taking a positive value is performed. Will be done.

同様に、ｘ3が“０”であり、かつｘ4が“０”である場合には、ｘ1の状態が“０”であることも“１”であることも許されなくなってしまう矛盾が生じる。これを防ぐために、ｘ3が“０”であることを表現するデータ変換ユニット１２と、ｘ4が“０” であることを表現するデータ変換ユニット１２とが、同時に正の値をとる場合には、次ステップにおいて、当該データ生成ユニット１１に対して出力調節信号を供給することで、対応するデータ変換ユニット１２が正の値をとることを抑制する制御を行う。 Similarly, if x 3 is “0” and x 4 is “0”, it is inconsistent that the state of x 1 cannot be “0” or “1”. Occurs. In order to prevent this, when the data conversion unit 12 expressing that x 3 is “0” and the data conversion unit 12 expressing that x 4 is “0”, simultaneously take a positive value. In the next step, by supplying an output adjustment signal to the data generation unit 11, the corresponding data conversion unit 12 is controlled to take a positive value.

またINTERにおいて、例えば、Ｑに含まれるｘ3に着目した場合に、ｘ2が“１”であり、かつｘ4が“１”である場合に、ｘ3が“０”である状態を打ち消すルールが定義されている。同様に、ｘ2が“０”である場合に、ｘ3が“１”である状態を打ち消すルールが定義されている。このため、ｘ2が“１”であり、ｘ4が“１”であり、かつｘ2が“０”である場合には、ｘ3は“０”と“１”の何れも取りえないこととなり、論理矛盾が生じる。かかる場合においても同様に、ｘ2が“１”、ｘ4が“１”、かつｘ2が“０”の状態が同時に生じないように制御する。具体的には、ｘ2が“１”、ｘ4が“１”、ｘ2が“０”であることを表現するデータ変換ユニット１２が、３つ同時に正の値をとる場合には、次ステップにおいて、当該の３つのデータ生成ユニット１１に対して出力調節信号を供給することで、対応する３つのデータ変換ユニット１２が正の値をとることを抑制する。 In INTER, for example, when focusing on x 3 included in Q, if x 2 is “1” and x 4 is “1”, the state where x 3 is “0” is canceled. Rules are defined. Similarly, a rule is defined that cancels the state where x 3 is “1” when x 2 is “0”. Therefore, when x 2 is “1”, x 4 is “1”, and x 2 is “0”, x 3 cannot be “0” or “1”. As a result, logical contradiction occurs. In such a case, similarly, control is performed so that the states where x 2 is “1”, x 4 is “1”, and x 2 is “0” do not occur simultaneously. Specifically, when three data conversion units 12 expressing that x 2 is “1”, x 4 is “1”, and x 2 is “0” are simultaneously positive, In the step, the output adjustment signal is supplied to the three data generation units 11 to suppress the corresponding three data conversion units 12 from taking a positive value.

他のｘ2〜ｘ4についても同様に論理矛盾が生じる組合せを調べることによって得られるＣＯＮＴＲＡの全てのルールを、表１に示す。すなわち、ＣＯＮＴＲＡは、探索問題情報に基づいて出力調節信号の供給制御を行うルールであるＩＮＴＥＲにおいて、各変数が“真”と“偽”のいずれの値をとることも共に禁じられてしまうような状態の組合せを列挙することで得られるルールの集合である。 Table 1 shows all rules of CONTRA obtained by examining combinations in which logical contradiction similarly occurs for the other x 2 to x 4 . In other words, CONTRA is prohibited from taking any value of “true” or “false” in INTER, which is a rule for controlling the supply of an output adjustment signal based on search problem information. A set of rules obtained by enumerating combinations of states.

上述のようなＩＮＴＲＡ、ＩＮＴＥＲ、ＣＯＮＴＲＡにより、Ｐ、Ｑの関係を、探索問題情報に基づいて予め定義することが可能となる。そして、ＩＮＴＲＡ，ＩＮＴＥＲ、ＣＯＮＴＲＡが定義するルールに基づき、Ｐの場合にＱの状態を打ち消すように制御を行うことで、最終的に、充足可能性問題の解を導くことができる。   With INTRA, INTER, and CONTRA as described above, the relationship between P and Q can be defined in advance based on search problem information. Then, based on the rules defined by INTRA, INTER, and CONTRA, by controlling so as to cancel the Q state in the case of P, a solution to the satisfiability problem can be finally derived.

ちなみに、このようなＩＮＴＲＡ、ＩＮＴＥＲ、ＣＯＮＴＲＡの制御は、Pの要素に対応するデータ変換ユニット１２の状態が、それぞれ２値（正の値又は負の値）のうち何れであるかを判定し、Ｑの要素に対応するデータ生成ユニット１１に出力調節信号の供給制御を行うという単純な動作である。このため、本発明では、フィードバック制御部１３は、ＣＰＵ（Central Processing Unit）を備えた高度な情報処理能力をもつデバイスではなく、データ変換ユニット１２からの入力をルールに基づき変換しデータ生成ユニット１１に出力を供給する機能のみをもつような、いわゆるスイッチ等のいかなる簡便な手段により実現してもよい。   Incidentally, such control of INTRA, INTER, CONTRA determines whether the state of the data conversion unit 12 corresponding to the element of P is a binary value (positive value or negative value), respectively. This is a simple operation of controlling the supply of the output adjustment signal to the data generation unit 11 corresponding to the element of Q. For this reason, in the present invention, the feedback control unit 13 is not a device having a high-level information processing capability equipped with a CPU (Central Processing Unit), but converts the input from the data conversion unit 12 based on a rule to convert the data generation unit 11. It may be realized by any simple means such as a so-called switch having only a function of supplying an output to the terminal.

なお、上述した解探索システム１は、上述した実施の形態に限定されるものではない。データ生成ユニット１１から出力されるデータ“１”又は“０”は、ある揺らぎを持った状態で出力される旨を説明した。この揺らぎとして無相関白色ノイズを設定する場合よりも、空間相関を持つ揺らぎや、時間相関を持つ揺らぎを設定する場合の方がより少ない時間ステップ数で効率的に探索解を求めることができることを解明している。以下、この揺らぎとして、空間相関を持つ揺らぎや、時間相関を持つ揺らぎを設定する場合について説明をする。   The solution search system 1 described above is not limited to the embodiment described above. It has been described that the data “1” or “0” output from the data generation unit 11 is output with a certain fluctuation. Compared to setting uncorrelated white noise as the fluctuation, the search solution can be obtained more efficiently with fewer time steps when the fluctuation with spatial correlation or the fluctuation with time correlation is set. Elucidated. Hereinafter, as the fluctuation, a case where a fluctuation having a spatial correlation or a fluctuation having a time correlation is set will be described.

図６は、かかる空間相関について説明するための図である。例えば、データ生成ユニット１１−１〜１１−８の８個で構成されており、その個々の空間的な配置が図６に示す形態とされているものとする。かかる場合において、出力調節信号が供給されているデータ生成ユニットの数を“num”と定義することにする。以下では、numが大きくなるにつれて、出力調節信号が供給されていないデータ生成ユニット１１から“１”が多く出力されるように、揺らぎを調節する例を説明する。   FIG. 6 is a diagram for explaining the spatial correlation. For example, it is assumed that the data generation units 11-1 to 11-8 are composed of eight units, and the individual spatial arrangement is as shown in FIG. In such a case, the number of data generation units to which the output adjustment signal is supplied is defined as “num”. In the following, an example will be described in which fluctuation is adjusted so that more “1” s are output from the data generation unit 11 to which no output adjustment signal is supplied as num increases.

図６（ａ）に示すように、出力調節部１４から出力調節信号がデータ生成ユニット１１に何ら供給されていない、いわゆる初期ステップを考えるものとする。このときnum=0である。ここで、１のデータ生成ユニット１１−６に着目した場合に、そこから出力されるデータの揺らぎを調節するためのパラメータとして、β-(num)とβ+(num)を定義する。β-(num)とβ+(num)の値はnumの関数として変化する。 As shown in FIG. 6A, let us consider a so-called initial step in which no output adjustment signal is supplied from the output adjustment unit 14 to the data generation unit 11. At this time, num = 0. Here, when attention is paid to one data generation unit 11-6, β − (num) and β + (num) are defined as parameters for adjusting fluctuation of data output therefrom. beta - the value of (num) and β + (num) varies as a function of num.

初期ステップでは、揺らぎを調節するためのパラメータの設定値をβ-(0)＝０．５、β+(0)＝０．５とする。これらの設定値は、データ生成ユニット１１において、前者は出力調節信号が供給されていないときに値“０”が生成され、後者は出力調節信号が供給されているときに値“１”が生成されるという、出力調節信号が誘導する値とは異なる値が生成される状況、いわば「エラー」のような状況が発生する確率が、ともに５０％であることを意味している。ただし、こうした「エラー」は真偽値割当の多様な組合せを探索するためには必要不可欠な動作であり、その発生頻度を適切に調節することが、効率的に解を探索するためには重要である。 In the initial step, set values of parameters for adjusting fluctuations are set to β − (0) = 0.5 and β + (0) = 0.5. In the data generation unit 11, these setting values are generated with the value “0” when the output adjustment signal is not supplied, and the latter with the value “1” when the output adjustment signal is supplied. This means that the probability that a value different from the value induced by the output adjustment signal is generated, that is, a situation such as “error”, is 50%. However, these “errors” are indispensable for searching for various combinations of true / false assignments, and appropriately adjusting the frequency of occurrence is important for efficiently searching for solutions. It is.

一方、図６（ｂ）では、出力調節部１４から出力調節信号がデータ生成ユニット１１−２、１１−４、１１−５に供給されているものとする。このときnum=3である。かかる場合には、揺らぎを調節するためのパラメータの設定値をβ-(3)＝０．２５、β+(3)＝０．０５に変化させる。こうすると、データ生成ユニット１１−６において、出力調節信号が供給されていないときに“０”が生成される確率が２５％、出力調節信号が供給されているときに“１”が生成される確率が５％となる。すなわち、numが増加するにつれて、「エラー」のような状況が発生する確率が低下するように制御することになる。 On the other hand, in FIG. 6B, the output adjustment signal is supplied from the output adjustment unit 14 to the data generation units 11-2, 11-4, and 11-5. At this time, num = 3. In such a case, the setting value of the parameter for adjusting the fluctuation is changed to β − (3) = 0.25 and β + (3) = 0.05. Thus, in the data generation unit 11-6, the probability that “0” is generated when the output adjustment signal is not supplied is 25%, and “1” is generated when the output adjustment signal is supplied. Probability is 5%. That is, as num increases, control is performed so that the probability of occurrence of a situation such as “error” decreases.

図６（ｃ）では、出力調節部１４から出力調節信号がデータ生成ユニット１１−１、１１−３、１１−５、１１−７に供給されており、num=4であるものとする。かかる場合には、β-(4)＝０．０５、β+(4)＝０．００に変化させ、データ生成ユニット１１−６において、出力調節信号が供給されていないときに“０”が、出力調節信号が供給されているときに“１”が生成される確率が、それぞれ５％と０％となる。すなわち、numがさらに増加したときに、「エラー」のような状況の発生確率がさらに低下するように制御することになる。 In FIG. 6C, the output adjustment signal is supplied from the output adjustment unit 14 to the data generation units 11-1, 11-3, 11-5, and 11-7, and it is assumed that num = 4. In such a case, β − (4) = 0.05 and β + (4) = 0.00 are changed, and “0” is set when the output adjustment signal is not supplied in the data generation unit 11-6. The probability that “1” is generated when the output adjustment signal is supplied is 5% and 0%, respectively. That is, when num further increases, control is performed so that the probability of occurrence of a situation such as “error” further decreases.

揺らぎ調節部１５は、出力調節信号が供給されているデータ生成ユニット１１の数に応じて、各データ生成ユニット１１からのデータ出力の揺らぎを調節する。具体的には、データ生成ユニット１１からは、“０”又は“１”の２値化されたデジタルデータを出力することとなるが、ランダムに、つまりホワイトノイズと同様にランダムに“０”又は“１”を出力するのではなく、“０”又は“１”の何れか一方がより多く出力されるような揺らぎを設定する。   The fluctuation adjustment unit 15 adjusts fluctuation of data output from each data generation unit 11 according to the number of data generation units 11 to which the output adjustment signal is supplied. Specifically, the data generation unit 11 outputs binary digital data “0” or “1”, but randomly “0” or “0” or in the same manner as white noise. Instead of outputting “1”, a fluctuation is set such that either “0” or “1” is output more.

以下の例では、出力調節信号が送信されているデータ生成ユニットの数numが大きくなるにつれて、出力調節信号が送信されていないデータ生成ユニット１１から“１”がより高い頻度で出力されるように揺らぎを調節する。そして、numが大きくなるにつれて、出力調節信号が送信されているデータ生成ユニット１１から“０”がより高い頻度で出力されるように制御する。   In the following example, as the number num of data generation units to which the output adjustment signal is transmitted increases, “1” is output at a higher frequency from the data generation unit 11 to which the output adjustment signal is not transmitted. Adjust the fluctuation. Then, as num increases, control is performed so that “0” is output at a higher frequency from the data generation unit 11 to which the output adjustment signal is transmitted.

図７（ａ）は、いわゆるホワイトノイズを示しており、縦軸はそのホワイトノイズの値を示している。このうちβ+、１−β-は、揺らぎに関する閾値（スレッショルド）である。β+は、出力調節信号が送信されているデータ生成ユニット１１の閾値である。ホワイトノイズがβ+以上であれば、出力調節信号が送信されているデータ生成ユニット１１から“０”を出力し、ホワイトノイズがβ+未満であれば“１”を出力する。１−β-は、出力調節信号が送信されていないデータ生成ユニット１１の閾値である。ホワイトノイズが１−β-以上であれば、出力調節信号が送信されていないデータ生成ユニット１１から“０”を出力し、１−β-未満であれば“１”を出力する。 FIG. 7A shows so-called white noise, and the vertical axis shows the value of the white noise. Of these, β + and 1-β − are thresholds related to fluctuations. β + is a threshold value of the data generation unit 11 to which the output adjustment signal is transmitted. If the white noise is β + or more, “0” is output from the data generation unit 11 to which the output adjustment signal is transmitted, and “1” is output if the white noise is less than β + . 1−β − is a threshold value of the data generation unit 11 to which no output adjustment signal is transmitted. If the white noise is 1−β − or more, “0” is output from the data generation unit 11 to which the output adjustment signal is not transmitted, and if it is less than 1−β − , “1” is output.

上述のように、このβ+、１−β-は、出力調節信号が供給されているデータ生成ユニット１１の数numに応じて変化するように設定するので、numの関数となっている。図７（ｂ）は、β+、１−β-をnumの関数としてプロットした例を示している。β+は、numが増加するにつれて、直ぐに０付近の値に収束するように設定したので、出力調節信号が供給されているデータ生成ユニット１１から出力されるデータは、ほぼ１００％の確率で “０”になる。 As described above, since β + and 1−β − are set so as to change according to the number num of data generation units 11 to which the output adjustment signal is supplied, they are functions of num. FIG. 7B shows an example in which β + and 1−β − are plotted as a function of num. Since β + is set to converge to a value near 0 as num increases, the data output from the data generation unit 11 to which the output adjustment signal is supplied has a probability of almost 100%. 0 ”.

これに対して、図７（ｂ）で示されるように、１−β-は、出力調節信号が供給されているデータ生成ユニット１１の数numが増加するにつれて、０．５から１に向けて徐々に増加するように設定した。これにより、numが増加するにつれて、出力調節信号が供給されてないデータ生成ユニット１１が“１”を出力する確率が増加する。 On the other hand, as shown in FIG. 7B, 1−β − increases from 0.5 to 1 as the number num of data generation units 11 to which the output adjustment signal is supplied increases. It was set to increase gradually. Accordingly, as num increases, the probability that the data generation unit 11 to which the output adjustment signal is not supplied outputs “1” increases.

このようにして出力調節信号が供給されているデータ生成ユニット１１の数numに応じて、出力すべきデータの揺らぎを調整することが可能となる。   In this way, it is possible to adjust the fluctuation of data to be output according to the number num of data generation units 11 to which the output adjustment signal is supplied.

なお、本発明では、この出力調節信号が供給されているデータ生成ユニット１１の数numに応じてβ+、β-を調節する場合に限定されるものではない。その上位概念として、出力調節信号が供給されているデータ生成ユニット１１の空間的な分布に基づいて、β+、β-を調節するものであればいかなる形態であってもよい。即ち、出力調節信号が供給されているデータ生成ユニット１１の数num以外に、その空間的な配置に基づいてβ+、β-を調節してもよい。換言すれば、numは同数であっても、その出力調節信号が供給されているデータ生成ユニット１１の配置に応じて、各データ生成ユニット１１ごとにβ+、β-の設定値が変わるように調節してもよい。つまり、出力調節信号が供給されているデータ生成ユニット１１の数num、配置といった空間に関する全ての事象に基づいて、β+、β-を調節してもよい。 The present invention is not limited to the case where β + and β − are adjusted according to the number num of data generation units 11 to which the output adjustment signal is supplied. As its superordinate concept, any form may be used as long as β + and β − are adjusted based on the spatial distribution of the data generation unit 11 to which the output adjustment signal is supplied. That is, in addition to the number num of data generation units 11 to which the output adjustment signal is supplied, β + and β − may be adjusted based on the spatial arrangement. In other words, even if num is the same number, the set values of β + and β − change for each data generation unit 11 according to the arrangement of the data generation units 11 to which the output adjustment signal is supplied. You may adjust. That is, β + and β − may be adjusted based on all the events related to the space such as the number num and the arrangement of the data generation units 11 to which the output adjustment signal is supplied.

なお、β+、１−β-の変化傾向は、図７（ｂ）に示される傾向に限定されるものではなく、上述した空間に関するあらゆる事象に基づくものであればいかなる揺らぎを以って設定されていてもよい。 Note that the change tendency of β + and 1-β − is not limited to the tendency shown in FIG. 7B, and is set with any fluctuation as long as it is based on any event related to the space described above. May be.

なお、本発明を適用した解探索システム１では、データ生成ユニット１１から出力されるデータ“１”又は“０”は、いわゆる時間相関をもつ揺らぎを伴って出力されるようにしてもよい。   In the solution search system 1 to which the present invention is applied, the data “1” or “0” output from the data generation unit 11 may be output with a fluctuation having a so-called time correlation.

図８（ａ）は、この時間相関をもつ揺らぎを設定するためにカオス揺らぎを生成するロジスティック写像を用いる例を示している。この図８（ａ）において、横軸は、ｆ（ｔ）の値であり、縦軸は、ｆ（ｔ＋１）の値である。   FIG. 8A shows an example in which a logistic map that generates chaotic fluctuations is used to set fluctuations having this time correlation. In FIG. 8A, the horizontal axis is the value of f (t), and the vertical axis is the value of f (t + 1).

これらの再帰的関係を一般式で示したのが以下の式（Ｐ）である。
ｆ（ｔ＋１）＝４・ｆ（ｔ）・（１−ｆ（ｔ））・・・・・（Ｐ） The following formula (P) shows these recursive relationships as general formulas.
f (t + 1) = 4 · f (t) · (1−f (t)) (P)

図８（ａ）で示されるロジスティック写像を用いる例では、揺らぎを調節するためのパラメータは、numの関数ではなく、定数β-＝０．２５、β+＝０に固定する。これにより、１−β-＝０．７５というスレッショルドが設定されることになる。出力調節信号が供給されていないデータ生成ユニット１１は、ｆ（ｔ）がスレッショルドを下回るときにデータ“１”を、上回るときに “０”を出力する。スレッショルドを０．７５に設定した理由は、ロジスティック写像は、不動点ｆ（ｔ＋１）＝ｆ（ｔ）＝０．７５を持つため、後述するように、この設定により負の時間相関をもちながらカオス的に揺らぐ時系列を生成することができるからである。 In the example using the logistic map shown in FIG. 8A, the parameter for adjusting the fluctuation is not a function of num but is fixed to constants β − = 0.25 and β + = 0. As a result, a threshold of 1−β − = 0.75 is set. The data generation unit 11 to which no output adjustment signal is supplied outputs data “1” when f (t) falls below the threshold, and outputs “0” when it exceeds. The reason for setting the threshold to 0.75 is that the logistic map has a fixed point f (t + 1) = f (t) = 0.75, and as described later, this setting causes chaos while having a negative time correlation. This is because a time series that fluctuates dynamically can be generated.

図８（ａ）において、ｆ（１）＝０．２はスレッショルド１−β-＝０．７５より小さいので、出力調節信号が供給されていないデータ生成ユニット１１は“０”を出力する。このｆ（１）＝０．２である場合における曲線Ｐ上の点ｙ1が、ｆ（２）の値となる。点ｙ1の縦軸に対応する値がｆ（２）=０．６４である。このｆ（２）＝０．６４はスレッショルドより小さいので、出力調節信号が供給されていないデータ生成ユニット１１は“０”を出力する。ｆ（２）＝０．６４である場合における曲線Ｐ上の点ｙ2の縦軸に対応するｆ（３）=０．９２１６は、スレッショルドより大きいので、出力調節信号が供給されていないデータ生成ユニット１１は“１”を出力する。ｆ（３）＝０．９２１６である場合における曲線Ｐ上の点ｙ3の縦軸に対応するｆ（４）=０．２８９０１４は、スレッショルドより小さいので、出力調節信号が供給されていないデータ生成ユニット１１は“０”を出力する。またｆ（５）以降についても同様に実行していく。 In FIG. 8A, since f (1) = 0.2 is smaller than the threshold 1−β − = 0.75, the data generation unit 11 to which no output adjustment signal is supplied outputs “0”. The point y 1 on the curve P when this f (1) = 0.2 is the value of f (2). The value corresponding to the vertical axis of the point y 1 is f (2) = 0.64. Since f (2) = 0.64 is smaller than the threshold, the data generation unit 11 to which no output adjustment signal is supplied outputs “0”. f (3) = 0.9216 corresponding to the longitudinal axis of the point y 2 on the curve P in the case of f (2) = 0.64 is greater than the threshold, the data generation power controlling signal is not supplied The unit 11 outputs “1”. Since f (4) = 0.289014 corresponding to the vertical axis of the point y 3 on the curve P in the case of f (3) = 0.9216 is smaller than the threshold, data generation in which no output adjustment signal is supplied Unit 11 outputs “0”. The same processing is performed after f (5).

このようなプロセスで、点ｙがｆ（t）＝０．７５の前後に近づくと、スレッショルドを交互に跨ぎ、その結果、出力調節信号が供給されていないデータ生成ユニット１１が“０”と“１”とを交互に出力する頻度が高くなる。図８（ｂ）は、実際に計算されたｆ（ｔ）の値を縦軸に、またｔを横軸としてプロットしたものである。スレッショルドｆ（ｔ）＝０．７５を跨いで折れ線が交互に上下する頻度が高いことが見て取れる。これは、出力調節信号が送信されていないデータ生成ユニット１１において、自らの１ステップ前（ｔ−１）の値が“０”ならば現ステップ（ｔ）では“１”を出力し、自らの１ステップ前（ｔ−１）の値が“１”ならば現ステップ（ｔ）では“０”を出力するという、いわゆる負の時間相関をもった時系列が発生する頻度が高くなるように、揺らぎが調節されていることを意味する。還元すると、自らの１ステップ前（ｔ−１）の値が“０”ならば現ステップ（ｔ）でも“０”を出力し、自らの１ステップ前（ｔ−１）の値が“１”ならば現ステップ（ｔ）でも“１”を出力するという、いわゆる正の時間相関をもった時系列が発生する頻度が低くなる。   In such a process, when the point y approaches around f (t) = 0.75, the data generation unit 11 to which the output adjustment signal is not supplied is alternately “0” and “ The frequency of alternately outputting 1 ″ is increased. FIG. 8B is a plot of the actually calculated f (t) value on the vertical axis and t on the horizontal axis. It can be seen that the frequency with which the broken lines alternately rise and fall across the threshold f (t) = 0.75 is high. This is because in the data generation unit 11 to which no output adjustment signal is transmitted, if the value one step before (t−1) is “0”, “1” is output at the current step (t) and If the value of 1 step before (t−1) is “1”, “0” is output at the current step (t) so that the frequency of occurrence of a time series having a negative time correlation is increased. It means that the fluctuation is adjusted. In other words, if the value one step before (t−1) is “0”, “0” is output even at the current step (t), and the value one step before (t−1) is “1”. If so, the frequency of generating a time series having a so-called positive time correlation, ie, outputting “1” even in the current step (t), is reduced.

このようにして、出力調節信号が送信されていないデータ生成ユニット１１から出力されるデータの時系列が時間相関をもつように、データ出力の揺らぎが調節されることになる。揺らぎ調節部１５は、上述のようなデータ出力の揺らぎが生じるようにデータ生成ユニット１１をコントロールする。なお、スレッショルドについては、ロジスティック写像以外のカオス揺らぎを発生する機構を用いる際には、特に上述した値１−β-＝０．７５に限定されるものではなく、他の適切な値に設定されていてもよい。 In this way, fluctuations in data output are adjusted so that the time series of data output from the data generation unit 11 to which no output adjustment signal is transmitted has a time correlation. The fluctuation adjusting unit 15 controls the data generation unit 11 so that the data output fluctuation as described above occurs. Note that the threshold is not particularly limited to the above-described value 1−β − = 0.75, but is set to another appropriate value when using a mechanism that generates chaotic fluctuations other than the logistic map. It may be.

また、図８（ｂ）に示すように、出力調節信号が供給されているデータ生成ユニット１１の閾値β+は、例えば０に設定しておくことにより、当該出力調節信号が供給されているデータ生成ユニット１１から出力されるデータは、常時０となる。このβ+についても、０に限定されるものではない。 Further, as shown in FIG. 8B, the threshold value β + of the data generation unit 11 to which the output adjustment signal is supplied is set to 0, for example, so that the data to which the output adjustment signal is supplied is set. Data output from the generation unit 11 is always 0. This β + is not limited to 0.

図９は、本発明の提案手法について、データ生成ユニット１１が空間相関をもつ揺らぎを伴ったデータを出力する場合と、時間相関をもつ揺らぎを伴ったデータを出力する場合について、それぞれ一つの問題につき５００試行のシミュレーションを行い、解が求まるまでに要した時間（ステップ数t）の平均値と標準偏差（エラーバー）を、他のよく知られている“WalkSAT”と呼ばれるSAT解探索アルゴリズムと比較した結果を示している。横軸は問題サンプルの番号である。このシミュレーションで扱った問題サンプルは、ＳＡＴのベンチマーク問題例をオンラインで公開している学術ライブラリー“ＳＡＴＬＩＢ”より取得したものである。ここで扱った全ての問題サンプルは、変数の数が２０、節の数が９１で、各節は上述した図４のＦ１２に示すような3つの変数とその否定からなる問題であり、かつ、８個の解を持つものを合計５４個を選択した。   FIG. 9 shows one problem for the proposed method of the present invention when the data generation unit 11 outputs data with fluctuations having spatial correlation and when data with fluctuations having time correlation is output. A simulation of 500 trials is performed, and the average value and standard deviation (error bar) of the time (number of steps t) required to find a solution are calculated using another well-known SAT solution search algorithm called “WalkSAT”. The comparison results are shown. The horizontal axis is the number of the problem sample. The problem sample dealt with in this simulation was obtained from an academic library “SATLIB” which is an online publication of SAT benchmark problem examples. All of the problem samples dealt with here are 20 variables, 91 clauses, and each clause is a problem consisting of the above three variables and their negation as shown in F12 of FIG. 4, and A total of 54 items with 8 solutions were selected.

図９のシミュレーション結果が示しているように、WalkSATと比較して、データ生成ユニット１１が空間相関や時間相関をもつ揺らぎを伴ったデータを出力する本発明の提案手法の方が、より少ないステップ数で効率的に解を求めることができる。   As shown in the simulation results of FIG. 9, the proposed method of the present invention in which the data generation unit 11 outputs data with fluctuations having a spatial correlation or a temporal correlation is fewer steps than the WalkSAT. A solution can be obtained efficiently with a number.

本発明を適用した解探索システム１では、上述の例のように、空間相関に基づく揺らぎを設定する場合と、時間相関に基づく揺らぎを設定する場合の何れか一方のみを行うのではなく、双方を取り入れることで、より効率的に解を求められるようにしてもよい。   In the solution search system 1 to which the present invention is applied, not only one of the case of setting the fluctuation based on the spatial correlation and the case of setting the fluctuation based on the time correlation as in the above-described example, both are performed. The solution may be obtained more efficiently by incorporating.

また、上述した実施の形態では、データ生成ユニット１１から出力されるデータは、２値のデジタルデータである場合を例に挙げているが、アナログデータを出力する場合においても同様の技術思想に基づいて解を探索させるようにしてもよい。。   In the above-described embodiment, the case where the data output from the data generation unit 11 is binary digital data is taken as an example, but analog data is output based on the same technical idea. You may make it search for a solution. .

なお、本発明を適用した解探索システム１は、より高速な計算を可能とする回路として具現化しても良い。回路として具現化される場合には、FPGA(field-programmable gate array)に基づいて、構成を設定するようにしてもよい。また本発明は、解探索システムとして具体化される場合以外には、解探索プログラムとして具体化されるものであってもよい。かかる場合には、仮想的に生成したデータ生成ユニット１１に対して、上述したデータ変換部１２、フィードバック制御部１３、出力調節部１４、揺らぎ調節部１５の各構成要素を、プログラムの各ステップにおいて実行するもので具現化することが可能となる。   Note that the solution search system 1 to which the present invention is applied may be embodied as a circuit that enables faster calculation. When embodied as a circuit, the configuration may be set based on a field-programmable gate array (FPGA). Further, the present invention may be embodied as a solution search program, except when embodied as a solution search system. In such a case, the components of the data conversion unit 12, the feedback control unit 13, the output adjustment unit 14, and the fluctuation adjustment unit 15 described above are added to the virtually generated data generation unit 11 in each step of the program. It becomes possible to embody with what is executed.

１ 解探索システム
１１ データ生成ユニット
１２ データ変換部
１３ フィードバック制御部
１４ 出力調節部
１５ 揺らぎ調節部 DESCRIPTION OF SYMBOLS 1 Solution search system 11 Data generation unit 12 Data conversion part 13 Feedback control part 14 Output adjustment part 15 Fluctuation adjustment part

Claims (6)

２値化されたデータを出力可能とし、揺らぎを持つデータを出力する複数のデータ生成ユニットと、
上記データ生成ユニットから出力されたデータを読み取って情報に変換するデータ変換手段と、
何れかの上記各データ生成ユニットに出力調節信号を送信することにより、上記データの出力を調節する出力調節手段と、
上記データ変換手段により変換された情報及び予め入力された探索問題情報に基づいて、上記出力調節手段による出力調節信号の送信を上記データ生成ユニット毎に制御するフィードバック制御手段とを備え、
上記フィードバック制御手段は、上記出力調節信号の送信制御の繰り返しを経て最終的に上記データ変換手段により変換された上記データ生成ユニットからの出力データに関する情報に基づき、上記探索問題情報に対する探索解を表示するとともに、
上記データ生成ユニットにおけるデータ出力の揺らぎを調節する揺らぎ調節手段を更に備え、
上記揺らぎ調節手段は、上記出力調節信号が既に送信されているデータ生成ユニットの数が多くなるにつれて、上記出力調節信号が既に送信されているデータ生成ユニットについて上記２値化されたデータの一方の出力頻度を高くするとともに、上記出力調節信号が送信されていないデータ生成ユニットについて２値化されたデータの他方の出力頻度を高くすることにより、上記データ生成ユニットの状態の空間的な分布に基づいて、上記各データ生成ユニットからのデータ出力の揺らぎを調節すること
を特徴とする解探索システム。 A plurality of data generation units that can output binarized data and output data with fluctuation;
Data conversion means for reading the data output from the data generation unit and converting it into information;
Output adjustment means for adjusting the output of the data by transmitting an output adjustment signal to any one of the data generation units;
Feedback control means for controlling transmission of the output adjustment signal by the output adjustment means for each data generation unit based on the information converted by the data conversion means and the search problem information input in advance.
The feedback control means displays a search solution for the search problem information based on information on the output data from the data generation unit finally converted by the data conversion means through repetition of transmission control of the output adjustment signal. And
The apparatus further comprises fluctuation adjusting means for adjusting fluctuation of data output in the data generation unit,
As the number of data generation units to which the output adjustment signal has already been transmitted increases, the fluctuation adjustment means has one of the binarized data for the data generation unit to which the output adjustment signal has already been transmitted. Based on the spatial distribution of the state of the data generation unit by increasing the output frequency and increasing the output frequency of the other of the binarized data for the data generation unit to which the output adjustment signal is not transmitted. And adjusting a fluctuation in data output from each of the data generation units. ２値化されたデータを出力可能とし、揺らぎを持つデータを出力する複数のデータ生成ユニットと、
上記データ生成ユニットから出力されたデータを読み取って情報に変換するデータ変換手段と、
何れかの上記各データ生成ユニットに出力調節信号を送信することにより、上記データの出力を調節する出力調節手段と、
上記データ変換手段により変換された情報及び予め入力された探索問題情報に基づいて、上記出力調節手段による出力調節信号の送信を上記データ生成ユニット毎に制御するフィードバック制御手段とを備え、
上記フィードバック制御手段は、上記出力調節信号の送信制御の繰り返しを経て最終的に上記データ変換手段により変換された上記データ生成ユニットからの出力データに関する情報に基づき、上記探索問題情報に対する探索解を表示するとともに、
上記データ生成ユニットにおけるデータ出力の揺らぎを調節する揺らぎ調節手段を更に備え、
上記揺らぎ調節手段は、時間経過に応じて、上記出力調節信号が既に送信されているデータ生成ユニットについて上記２値化されたデータの一方の出力頻度を高くするとともに、上記出力調節信号が未だ送信されていないデータ生成ユニットについて２値化されたデータを交互に出力する頻度を高くすることにより、上記データ生成ユニットにおける出力データの時系列が時間相関をもつように上記データ生成ユニットからのデータ出力の揺らぎを調節すること
を特徴とする解探索システム。 A plurality of data generation units that can output binarized data and output data with fluctuation;
Data conversion means for reading the data output from the data generation unit and converting it into information;
Output adjustment means for adjusting the output of the data by transmitting an output adjustment signal to any one of the data generation units;
Feedback control means for controlling transmission of the output adjustment signal by the output adjustment means for each data generation unit based on the information converted by the data conversion means and the search problem information input in advance.
The feedback control means displays a search solution for the search problem information based on information on the output data from the data generation unit finally converted by the data conversion means through repetition of transmission control of the output adjustment signal. And
The apparatus further comprises fluctuation adjusting means for adjusting fluctuation of data output in the data generation unit,
The fluctuation adjusting means increases the output frequency of one of the binarized data for the data generation unit to which the output adjustment signal has already been transmitted as time elapses, and the output adjustment signal is not yet transmitted. Data output from the data generation unit so that the time series of output data in the data generation unit has a time correlation by increasing the frequency of alternately outputting binarized data for the data generation unit that has not been performed Solution search system characterized by adjusting fluctuations of ２値化されたデータを出力可能とする複数のデータ生成ユニットから、揺らぎを持つデータを出力させるデータ出力ステップと、
上記データ生成ユニットから出力させたデータを読み取って情報に変換するデータ変換ステップと、
何れかの上記各データ生成ユニットにおけるデータの出力を調節する出力調節ステップと、
上記データ変換ステップにおいて変換した情報及び予め入力された探索問題情報に基づいて、上記出力調節ステップにおける出力調節を上記データ生成ユニット毎に制御し、上記出力調節ステップにおける調節の繰り返しを経て最終的に上記データ変換ステップにおいて変換された上記データ生成ユニットからの出力データに関する情報に基づき、上記探索問題情報に対する探索解を表示するフィードバック制御ステップと、
上記データ生成ユニットにおけるデータ出力の揺らぎを調節する揺らぎ調節ステップを有し、
上記揺らぎ調節ステップでは、上記出力調節信号が既に送信されているデータ生成ユニットの数が多くなるにつれて、上記出力調節信号が既に送信されているデータ生成ユニットについて上記２値化されたデータの一方の出力頻度を高くするとともに、上記出力調節信号が送信されていないデータ生成ユニットについて２値化されたデータの他方の出力頻度を高くすることにより、上記データ生成ユニットの空間的な分布に基づいて、上記各データ生成ユニットからのデータ出力の揺らぎを調節すること
をコンピュータに実行させることを特徴とする解探索プログラム。 A plurality of data generation unit which enables outputs binarized data, a data output step of outputting the data having fluctuations,
A data conversion step of reading the data output from the data generation unit and converting it into information;
An output adjustment step for adjusting the output of data in any one of the data generation units;
Based on the converted information and the pre-entered search problem information in the data conversion step, the output adjustment in the output adjustment step to control for each of the data generation unit, and finally through the repetition of the adjustment in the output adjustment step A feedback control step of displaying a search solution for the search problem information based on information on the output data from the data generation unit converted in the data conversion step;
A fluctuation adjusting step for adjusting fluctuation of data output in the data generation unit;
In the fluctuation adjusting step, as the number of data generation units to which the output adjustment signal has already been transmitted increases, one of the binarized data for the data generation unit to which the output adjustment signal has already been transmitted. Based on the spatial distribution of the data generation unit by increasing the output frequency and increasing the output frequency of the other of the binarized data for the data generation unit for which the output adjustment signal is not transmitted , A solution search program that causes a computer to adjust fluctuations in data output from each of the data generation units. ２値化されたデータを出力可能とする複数のデータ生成ユニットから、揺らぎを持つデータを出力させるデータ出力ステップと、
上記データ生成ユニットから出力させたデータを読み取って情報に変換するデータ変換ステップと、
何れかの上記各データ生成ユニットにおけるデータの出力を調節する出力調節ステップと、
上記データ変換ステップにおいて変換した情報及び予め入力された探索問題情報に基づいて、上記出力調節ステップにおける出力調節を上記データ生成ユニット毎に制御し、上記出力調節ステップにおける調節の繰り返しを経て最終的に上記データ変換ステップにおいて変換された上記データ生成ユニットからの出力データに関する情報に基づき、上記探索問題情報に対する探索解を表示するフィードバック制御ステップと、
上記データ生成ユニットにおけるデータ出力の揺らぎを調節する揺らぎ調節ステップを有し、
上記揺らぎ調節ステップでは、上記出力調節信号が既に送信されているデータ生成ユニットの数が多くなるにつれて、時間経過に応じて、上記出力調節信号が既に送信されているデータ生成ユニットについて上記２値化されたデータの一方の出力頻度を高くするとともに、上記出力調節信号が送信されていないデータ生成ユニットについて２値化されたデータの他方の出力頻度を高くすることにより、上記データ生成ユニットにおける出力データの時系列が時間相関をもつように上記データ生成ユニットからのデータ出力の揺らぎを調節すること
をコンピュータに実行させること特徴とする解探索プログラム。 A plurality of data generation unit which enables outputs binarized data, a data output step of outputting the data having fluctuations,
A data conversion step of reading the data output from the data generation unit and converting it into information;
An output adjustment step for adjusting the output of data in any one of the data generation units;
Based on the converted information and the pre-entered search problem information in the data conversion step, the output adjustment in the output adjustment step to control for each of the data generation unit, and finally through the repetition of the adjustment in the output adjustment step A feedback control step of displaying a search solution for the search problem information based on information on the output data from the data generation unit converted in the data conversion step;
A fluctuation adjusting step for adjusting fluctuation of data output in the data generation unit;
In the fluctuation adjusting step, as the number of data generation units to which the output adjustment signal has already been transmitted increases, the binarization is performed on the data generation unit to which the output adjustment signal has already been transmitted over time. Output data in the data generation unit by increasing the output frequency of one of the generated data and increasing the output frequency of the other of the binarized data for the data generation unit to which the output adjustment signal is not transmitted A solution search program that causes a computer to adjust fluctuations in data output from the data generation unit so that the time series of the above has a time correlation. ２値化されたデータを出力可能とする複数のデータ生成ユニットから、揺らぎを持つデータを出力させるデータ出力ステップと、
上記データ生成ユニットから出力させたデータを読み取って情報に変換するデータ変換ステップと、
何れかの上記各データ生成ユニットにおけるデータの出力を調節する出力調節ステップと、
上記データ変換ステップにおいて変換した情報及び予め入力された探索問題情報に基づいて、上記出力調節ステップにおける出力調節を上記データ生成ユニット毎に制御し、上記出力調節ステップにおける調節の繰り返しを経て最終的に上記データ変換ステップにおいて変換された上記データ生成ユニットからの出力データに関する情報に基づき、上記探索問題情報に対する探索解を表示するフィードバック制御ステップと、
上記データ生成ユニットにおけるデータ出力の揺らぎを調節する揺らぎ調節ステップを有し、
上記揺らぎ調節ステップでは、上記出力調節信号が既に送信されているデータ生成ユニットの数が多くなるにつれて、上記出力調節信号が既に送信されているデータ生成ユニットについて上記２値化されたデータの一方の出力頻度を高くするとともに、上記出力調節信号が送信されていないデータ生成ユニットについて２値化されたデータの他方の出力頻度を高くすることにより、上記データ生成ユニットの状態の空間的な分布に基づいて、上記各データ生成ユニットからのデータ出力の揺らぎを調節すること
を特徴とする解探索方法。 A plurality of data generation unit which enables outputs binarized data, a data output step of outputting the data having fluctuations,
A data conversion step of reading the data output from the data generation unit and converting it into information;
An output adjustment step for adjusting the output of data in any one of the data generation units;
Based on the converted information and the pre-entered search problem information in the data conversion step, the output adjustment in the output adjustment step to control for each of the data generation unit, and finally through the repetition of the adjustment in the output adjustment step A feedback control step of displaying a search solution for the search problem information based on information on the output data from the data generation unit converted in the data conversion step;
A fluctuation adjusting step for adjusting fluctuation of data output in the data generation unit;
In the fluctuation adjusting step, as the number of data generation units to which the output adjustment signal has already been transmitted increases, one of the binarized data for the data generation unit to which the output adjustment signal has already been transmitted. Based on the spatial distribution of the state of the data generation unit by increasing the output frequency and increasing the output frequency of the other of the binarized data for the data generation unit to which the output adjustment signal is not transmitted. And adjusting a fluctuation in data output from each of the data generation units. ２値化されたデータを出力可能とする複数のデータ生成ユニットから、揺らぎを持つデータを出力させるデータ出力ステップと、
上記データ生成ユニットから出力させたデータを読み取って情報に変換するデータ変換ステップと、
何れかの上記各データ生成ユニットにおけるデータの出力を調節する出力調節ステップと、
上記データ変換ステップにおいて変換した情報及び予め入力された探索問題情報に基づいて、上記出力調節ステップにおける出力調節を上記データ生成ユニット毎に制御し、上記出力調節ステップにおける調節の繰り返しを経て最終的に上記データ変換ステップにおいて変換された上記データ生成ユニットからの出力データに関する情報に基づき、上記探索問題情報に対する探索解を表示するフィードバック制御ステップと、
上記データ生成ユニットにおけるデータ出力の揺らぎを調節する揺らぎ調節ステップを有し、
上記揺らぎ調節ステップでは、上記出力調節信号が既に送信されているデータ生成ユニットの数が多くなるにつれて、時間経過に応じて、上記出力調節信号が既に送信されているデータ生成ユニットについて上記２値化されたデータの一方の出力頻度を高くするとともに、上記出力調節信号が送信されていないデータ生成ユニットについて２値化されたデータの他方の出力頻度を高くすることにより、上記データ生成ユニットにおける出力データの時系列が時間相関をもつように上記データ生成ユニットからのデータ出力の揺らぎを調節すること
を特徴とする解探索方法。 A plurality of data generation unit which enables outputs binarized data, a data output step of outputting the data having fluctuations,
A data conversion step of reading the data output from the data generation unit and converting it into information;
An output adjustment step for adjusting the output of data in any one of the data generation units;
Based on the converted information and the pre-entered search problem information in the data conversion step, the output adjustment in the output adjustment step to control for each of the data generation unit, and finally through the repetition of the adjustment in the output adjustment step A feedback control step of displaying a search solution for the search problem information based on information on the output data from the data generation unit converted in the data conversion step;
A fluctuation adjusting step for adjusting fluctuation of data output in the data generation unit;
In the fluctuation adjusting step, as the number of data generation units to which the output adjustment signal has already been transmitted increases, the binarization is performed on the data generation unit to which the output adjustment signal has already been transmitted over time. Output data in the data generation unit by increasing the output frequency of one of the generated data and increasing the output frequency of the other of the binarized data for the data generation unit to which the output adjustment signal is not transmitted A solution search method comprising adjusting fluctuations in data output from the data generation unit so that the time series of the data has a time correlation.
JP2012232402A 2012-10-19 2012-10-19 Solution search system and method, solution search program Expired - Fee Related JP6011928B2 (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
JP2012232402A JP6011928B2 (en) 2012-10-19 2012-10-19 Solution search system and method, solution search program

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP2012232402A JP6011928B2 (en) 2012-10-19 2012-10-19 Solution search system and method, solution search program

Publications (2)

Publication Number Publication Date
JP2014085733A JP2014085733A (en) 2014-05-12
JP6011928B2 true JP6011928B2 (en) 2016-10-25

Family

ID=50788763

Family Applications (1)

Application Number Title Priority Date Filing Date
JP2012232402A Expired - Fee Related JP6011928B2 (en) 2012-10-19 2012-10-19 Solution search system and method, solution search program

Country Status (1)

Country Link
JP (1) JP6011928B2 (en)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2025224994A1 (en) 2024-04-26 2025-10-30 Ａｍｏｅｂａ Ｅｎｅｒｇｙ株式会社 Route plan search method and computation device

Families Citing this family (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP6974955B2 (en) * 2017-03-28 2021-12-01 学校法人慶應義塾 Crossbar structure and optimization problem solution search system
JP7141614B2 (en) * 2018-05-14 2022-09-26 国立大学法人北海道大学 device
JP7141615B2 (en) * 2018-05-14 2022-09-26 国立大学法人北海道大学 Robot, robot control method and program
CN116457803A (en) * 2020-11-05 2023-07-18 阿米巴能源股份有限公司 Solution search system, solution search method, and solution search program
KR20230084261A (en) * 2020-11-05 2023-06-12 아메바 에너지 가부시키가이샤 Sea search system, sea search method and sea search program
JP7627453B2 (en) * 2020-11-05 2025-02-06 Ａｍｏｅｂａ Ｅｎｅｒｇｙ株式会社 Solution search system, solution search method, and solution search program

Family Cites Families (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP3648370B2 (en) * 1997-12-25 2005-05-18 日本電信電話株式会社 Satisfaction judgment method and apparatus for sum product type logic

Cited By (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2025224994A1 (en) 2024-04-26 2025-10-30 Ａｍｏｅｂａ Ｅｎｅｒｇｙ株式会社 Route plan search method and computation device
KR20250168212A (en) 2024-04-26 2025-12-02 아메바 에너지 가부시키가이샤 Path planning search method and processor
EP4693125A1 (en) 2024-04-26 2026-02-11 Amoeba Energy Co., Ltd. Route plan search method and computation device

Also Published As

Publication number Publication date
JP2014085733A (en) 2014-05-12

Similar Documents

Publication Publication Date Title
JP6011928B2 (en) Solution search system and method, solution search program
Li et al. A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates
EP3879465B1 (en) Method and apparatus for updating parameter of model, distributed training system
Chaouiya et al. Logical modelling of gene regulatory networks with GINsim
Li et al. Event-triggered synchronization control for complex networks with uncertain inner coupling
Yao et al. Structural controllability of temporal networks with a single switching controller
Zhang et al. Influence maximization based on threshold models in hypergraphs
Cavalcante et al. On the origin of chaos in autonomous Boolean networks
Gupta et al. Online Platt scaling with calibeating
Liu et al. Accelerated distributed dual averaging over evolving networks of growing connectivity
Sun et al. Outer synchronization between two complex dynamical networks with discontinuous coupling
Moradi et al. Heterogeneous reinforcement learning for defending power grids against attacks
Nguyen et al. Featured hybrid recommendation system using stochastic gradient descent
Sun et al. A new four-dimensional chaotic system with rich transitional characteristics between dissipative and conservative
Suhas et al. HsClone genetic algorithm implementation on a combinational circuit
Osband et al. On optimistic versus randomized exploration in reinforcement learning
Zhao et al. New-type stability theorem for stochastic functional differential equations with application to SFDSs with distributed delays
CN118916637A (en) Social network key node selection method, system and storage medium based on influence attenuation
De Lellis et al. Inferring directional interactions in collective dynamics: a critique to intrinsic mutual information
Mougouei et al. Partial selection of software requirements: a fuzzy method
JP7529043B2 (en) Information processing device, hypothesis generation method, program, and recording medium
CN110908342B (en) O-GERT method for multi-process manufacturing quality loss prediction based on fusion operator
Deng et al. Multipopulation Genetic Algorithms with Different Interaction Structures to Solve Flexible Job‐Shop Scheduling Problems: A Network Science Perspective
Norrell et al. Boolean modeling of collective effects in complex networks
Wu An information fractal dimensional relative entropy

Legal Events

Date Code Title Description
A621 Written request for application examination

Free format text: JAPANESE INTERMEDIATE CODE: A621

Effective date: 20150831

A977 Report on retrieval

Free format text: JAPANESE INTERMEDIATE CODE: A971007

Effective date: 20160518

A131 Notification of reasons for refusal

Free format text: JAPANESE INTERMEDIATE CODE: A131

Effective date: 20160628

A521 Written amendment

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20160825

TRDD Decision of grant or rejection written
A01 Written decision to grant a patent or to grant a registration (utility model)

Free format text: JAPANESE INTERMEDIATE CODE: A01

Effective date: 20160906

A61 First payment of annual fees (during grant procedure)

Free format text: JAPANESE INTERMEDIATE CODE: A61

Effective date: 20160908

R150 Certificate of patent or registration of utility model

Ref document number: 6011928

Country of ref document: JP

Free format text: JAPANESE INTERMEDIATE CODE: R150

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

LAPS Cancellation because of no payment of annual fees