JPH0561848A - Device and method for selecting and executing optimum algorithm - Google Patents

Abstract

(57) [Summary] [Purpose] The selection and execution of the optimal minimum / maximum point search algorithm for a given multimodal multivariable function, and the improvement of the convergence of the synchronous variable update processing. [Structure] In advance, a plurality of algorithms for searching for a local minimum point or a local maximum point are applied to each of a plurality of multimodal multivariable functions having different statistic values that characterize the function, and The comparison data is created and stored in the storage device 101.
Stored in. Given a multimodal multivariable function, the optimal algorithm for that function, based on the value of the statistic of the quantity that characterizes this function and the contrast data,
Select from the plurality of algorithms. In synchronous updating of all variables, the convergence is improved by compressing the amount of change in updating at a certain rate.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to computer processing of multimodal multivariable functions, and more particularly to finding the minimum or maximum points (including the minimum and maximum points, respectively) of this type of function. Related to computer selection and execution of algorithms. Computer processing of this type of function is applied to solve various optimization problems, control various types, and the like.

[0002]

2. Description of the Related Art A typical example of searching for a minimum point of a multimodal multivariable function is energy minimization calculation when an optimization problem is solved using a neural network model.

Conventionally, as an algorithm for minimizing the energy of the neural network, Biological C
ybernetics, Vol. 52, 1985, 141-152
Page, "" Neural "Computation of Decisions in Optimiz
ation Problems ”(hereinafter referred to as Reference 1), SCIENCE, Vol. 220, No. 4598,198
May 13, 2013, pp. 671-680, "Optimization
by simulated annealing "(hereinafter referred to as Reference 2), IEICE technical report, 9
0, 274, 1990, pp. 1-6, "Optimization calculation method by mean field approximation annealing method" (hereinafter referred to as Reference 3). The method described in Reference 1 is fast, but cannot escape when trapped in a minimal solution, and the method described in Reference 2 can reach the minimum solution, but Since the time is very long, the method described in Literature 3 can obtain the approximate solution of the minimum solution in a short time. Thus, these proposed algorithms have their own characteristics.

In the process of energy minimization, it is necessary to repeatedly update the state of each neuron many times. The basic methods for updating the state of a neuron are the synchronous method and the asynchronous method. The synchronous method updates the states of all neurons in parallel and has a short calculation time, but the state of the neural network does not always converge to a stable point. On the other hand, the asynchronous method is a sequential method in which the state of one neuron is updated and then the state of the next neuron is updated based on the updated state of this neuron. Although it occurs, it takes a long time. An eclectic method is the checkerboard method described by Kenro Murata et al., Published by Maruzen in 1988, "Numerical Simulation in Engineering", page 57 (hereinafter referred to as Reference 4). According to this method, neurons are assigned to grid points and are classified into even points and odd points according to the sum of their coordinate values, and synchronous updating of only even points and synchronous updating of only odd points are alternately repeated. Therefore, reliable convergence can be expected in a relatively short time.

[0005]

As described above, since the conventionally proposed algorithms have their respective characteristics, the characteristics of the multimodal multivariable function to be applied (for example, neural network It is desirable to select the optimum algorithm according to the configuration (as determined by the configuration). However, among these algorithms, an algorithm that is optimal for any given multimodal multivariable function (for example, that energy can be minimized for a given neural network) is set in advance. The selection criteria for quantitatively judging and selecting have not been known yet.

Also, regarding the iterative updating of the value of a variable (for example, the state of a neuron), the above-mentioned checkerboard method is generally expected to shorten the calculation time and surely converge, but Since variables (neurons) must be divided into multiple groups and synchronous updates must be performed sequentially for each group, the processing becomes complicated and vectorized by a super computer etc. for calculation. However, there is a drawback in that the vectorization rate becomes low and the calculation time becomes long when performing.

A first object of the present invention is to search for a minimum point or a maximum point which is optimum for a given multimodal multivariable function (for example, which has the smallest energy for a neural network). It is an object to provide an apparatus and a method capable of automatically selecting an algorithm from a plurality of algorithms and executing the algorithm.

A second object of the present invention is to ensure reliable convergence even if the values of all variables (for example, the states of all neurons) are updated synchronously without grouping. To provide a simple variable updating method.

[0009]

One of the basic features of the present invention is the amount of characterizing a function as an index of the feature of a multimodal multivariable function (for example, a neural network configuration).
Optimal data is created by pre-creating and retaining data indicating how the results of applying various algorithms by adopting these statistics instead of themselves, and changing such statistics. It is referred to as a measure for selecting an algorithm.

That is, the optimum algorithm selecting device of the present invention is a method for searching a plurality of minimum points or maximum points for each of a plurality of multimodal multivariable functions having different statistic values of the features characterizing the function. A storage device in which contrast data of application results are stored, and an optimum algorithm for a given multimodal multivariable function are compared with the value of the statistic of the quantity that characterizes the given multimodal multivariable function A processing device that selects from among the plurality of algorithms based on the data. As this statistic, for example, at least one of average and variance of thresholds can be used.

In the case of a neural network, this function is an energy function, the quantity characterizing the function is at least one of the synaptic connection weight and the neuron threshold, and the contrast data is the calculated minimum energy. In the case of nonlinear programming, the function is the evaluation function in nonlinear programming, the quantity characterizing the function is at least one of the coefficients in this evaluation function, and the contrast data is the calculated minimum or maximum function value. is there. Also,
In the case of associative memory consisting of neural networks,
The function is a function that represents the characteristic of the associative memory, the amount that represents the feature of the function is the correlation amount of a group of key patterns of the associative memory, and the contrast data is the data that indicates the accuracy rate of the response of the associative memory.

In the case of a neural network and a non-linear programming method, the optimum algorithm selection method in this apparatus is to calculate the value of the statistic of the quantity that characterizes a given multimodal multivariable function, and Referring to, selecting an algorithm that gives a minimum or maximum function value for the statistic value closest to the calculated statistic value. Further, in the case of associative memory, the step of calculating at least one of the average value and the variance value of the correlation value between the pattern pairs in the given group of key patterns, and referring to the comparison data, Selecting the algorithm that gives the best accuracy rate for values of the same kind that are closest to the calculated value. In these methods, when there are a plurality of algorithms giving substantially the same function value or accuracy rate,
The one having the shortest calculation time may be selected from them.

A program for executing each of the plurality of algorithms is further stored in the storage device of the optimum algorithm selecting device, and the processing device is provided with:
An optimum algorithm execution device can be obtained by providing a function for executing a program for executing the selected optimum algorithm.

Another basic feature of the present invention is that, when executing the selected algorithm, the amount of change in updating the values of various variables is compressed more than in the usual method, and synchronous updating is performed. is there.

That is, the variable value updating method of the present invention comprises a step of calculating a temporary updated value according to a selected algorithm, and a step of compressing and updating the difference between the temporary updated value and the value before updating according to a predetermined parameter. It includes the steps of determining later values and applying both of these steps to synchronously update the values of all variables. This parameter may be a constant or may change in a constant direction as the number of iterative updates progresses.

[0016]

According to the optimum algorithm selecting apparatus and method of the present invention, the computer calculates the value of the statistic of the quantity which characterizes the given multimodal multivariable function, and the calculated value of the statistic is used as a key. As a reference, the optimum algorithm for the given function is selected by referring to the performance comparison data of the various algorithms held in the storage device.

Further, according to the optimum algorithm executing apparatus of the present invention, the computer applies the optimum algorithm selected as described above to the given function to create a solution.

Furthermore, according to the algorithm execution method of the present invention, when updating the values of the variables, the values of all the variables are updated synchronously while suppressing rapid changes in the values. As a result, fast and reliable convergence can be expected.

[0019]

DESCRIPTION OF THE PREFERRED EMBODIMENTS FIG. 1 shows an outline of an optimum algorithm selecting / executing apparatus according to the present invention. The external memory 101 holds each program for executing a plurality of minimization algorithms and algorithm contrast data representing superiority or inferiority when these algorithms are applied to various neural networks having different configuration statistics. Has been done. Data representing the structure of the given neural network is input by the keyboard 102, and the computer 103 is entered.
Calculates the statistic of the configuration of this neural network, selects the optimum algorithm for this neural network by referring to the algorithm comparison data stored in the external memory 101, and applies the selected algorithm. Then, the energy minimization calculation of this neural network is executed, and the obtained solution is displayed on the display 104.

The algorithm comparison data is described in the above-mentioned reference 3
The spin-glass model used in this study is used as the target of trial calculation, and each algorithm is applied to various spin-glass models with different coupling weights and threshold statistics. It is compiled into a convenient format for comparison with the above statistics. Calculate the same kind of statistics of a given neural network,
The optimum algorithm for this neural network can be selected by referring to the algorithm comparison data using those values as keys. In addition, when the selected algorithm is applied, the amount of change in updating the state (output value) of each neuron is appropriately compressed, so that reliable convergence can be expected despite synchronous updating.

Generally, the neural network is shown in FIG.
It is represented by the mutual connection type neural network shown in FIG. A plurality of neurons 201 are interconnected by synapses 202 each having a unique connection weight.
As shown in FIG. 3, each neuron 201 has a threshold value and an output function 304, and determines the output signal 305 according to the value of the weighted total input 303. In the present embodiment, the output function is not the step function 401 that can take only binary values discretely as shown in FIG. 4, but the saturation type sigmoid function that can take monotonically increasing analog values. The energy of the network converges toward the minimum value by the cooperative and competitive actions of these neurons. In addition,
The energy function is such that W _ij is the connection weight from the i-th neuron to the j-th neuron, a _i is the threshold value of the i-th neuron, Vi is the output value of the i-th neuron, and N _i is the output value.
Is generally defined by the following equation.

[0022]

[Equation 1]

First, the procedure for creating the algorithm comparison data will be described. Generally, an interconnected neural network
Ku's energy function exhibits a complex energy surface,
It has many minimal solutions. Therefore, it is very difficult to reach the optimum solution in which the energy is truly the minimum, and various algorithms have been proposed for reaching a good quality suboptimal solution at high speed. In this embodiment, as typical algorithms, the method of Hopfield et al. Described in Document 1 (hereinafter abbreviated as H method) and the simulated annealing method described in Document 2 (hereinafter abbreviated as SA method). Do),
In addition, the mean field approximation annealing method (hereinafter abbreviated as MFAA method) and the mixing method described in Reference 3 are adopted, and these are applied to the spin glass model. In the spin glass model, the coupling load between neurons and the threshold value of each neuron are given as normal random numbers that can take positive or negative values, and W _ij = W _ji . At this time, the shape of the energy-curved surface can be adjusted by changing the average and variance of the set normal random numbers.

FIG. 5 and FIG. 6 show that in the above model,
The comparison results of the performances of the four algorithms when the average WA and the variance Wσ of the coupling weights and the average aA and the variance aσ of the threshold values are changed are shown. The number of iterative calculations in each algorithm is 1000 for H method, SA method and MFA
The method A was 10,000 times, the mixing method was 100 times by the MFAA method, and the subsequent SA method was 10,000 times. The total number of neurons is 50. Then, a normal random number having 10 different series is given as an initial state, and the average of the energy values of each result is plotted. In these graphs, the horizontal axis (logarithmic scale) shows the changed statistics, and the vertical axis shows the minimum energy obtained by the H method.
The standardization error ER with respect to EH of the minimum energy −E obtained by another algorithm with reference to the value EH, that is, ER = (EH−E) / EH is shown. ▽ indicates S
The A method, the Δ mark represent the MFAA method, and the ○ mark represent the mixed method. The horizontal axis of ER = 0% is the solution result by the H method,
The larger the standardization error is, the closer the solution is to the optimal solution.

In FIG. 5A, the average WA of the joint loads and the average aA of the thresholds are changed by changing only the variance Wσ of the joint loads.
And the comparison results of the performance of these four algorithms when the variance aσ is set to “0”. The horizontal axis represents Wσ. First, focusing on the SA method, the resulting solution is always farthest from the optimal solution among the four algorithms. Therefore, it is unlikely that this algorithm will be fully effective within a realistic number of iterations. Next, in the MFAA method, when Wσ is 2 or less, the best solution among these algorithms is obtained. However, when Wσ is 3 or more, the order is reversed from that of the mixed method, and when Wσ is 8 or more, the rank is the same as that of the H method, and thus the performance gradually deteriorates as Wσ increases. This cause is MF
Since the AA method is an approximation method, it can be qualitatively understood that the error due to the approximation becomes large as Wσ becomes large and the energy-curved surface becomes complicated and many minimum points are generated. On the other hand, the mixed method is slightly inferior to the H method when Wσ is 0.07 or less, but a stable and good solution is obtained when Wσ is 0.08 or more. This is Wσ
This is because the characteristics of the mixed method capable of escaping from the minimal solution are exhibited when H becomes large and the minimal solution increases, in contrast to the H method, which is a simple steepest descent method.

Next, in FIG. 5B, Wσ = 0.1, aσ
= AA = 0, the comparison results when the average WA of the coupling load is changed are shown. WA of 0.0 in the MFAA method and the mixed method
2 or more, SA method has WA of 0.4 or more, which is equivalent to H method. This is probably because the influence of the dispersion of the coupling load becomes smaller and the energy-curved surface becomes monotonous as the average of the coupling load becomes larger.

Further, in FIG. 6A, Wσ = 0.1, WA
= AA = 0, the comparison result when the threshold variance aσ is changed is shown. It can be seen that the superiority or inferiority does not fluctuate even if aσ changes, and the influence of the threshold dispersion can be almost ignored.

Finally, in FIG. 6B, Wσ = 0.1, W
A comparison result when A = aσ = 0 and the average threshold value aA is changed is shown. In the mixing method, aA is 0.002 or more,
In the MFAA method, the aA is 0.3 or more, and in the SA method, the aA is 0.7 or more. This may be because the energy surface becomes monotonic as the threshold average increases. The mixed method is reversed from that of Hopfield et al. When aA is 0.2,
Since the difference is about 2%, this can be regarded as an error.

In addition to this, changes in WA, aσ, and aA when Wσ is set to a value other than 0.1 can be assumed, and even in that case, the superiority or inferiority of the algorithm is presumed to show the same tendency. Therefore, the optimal algorithm is W
It can be roughly estimated by considering only σ,
It is sufficient to consider WA, aσ, and aA only when strictness is required.

The processing procedure for comparing the performances of various algorithms for the spin glass model is shown in FIG.
Shown in the figure. The processing in each block in the figure is as follows.

Block 701: Set joint weights and thresholds to initial conditions. Block 702: Set joint weight and threshold end state. Block 703: Blocks 704 to 707 are repeated until the combined load reaches the end state set in block 702. Block 704: Change the coupling load. Block 705: Blocks 706 and 707 are repeated until the threshold value reaches the end state set in block 702, and the process proceeds to block 703. Block 706: Change threshold. Block 707: Perform performance comparison of algorithms.
That is, the energy minimization calculation is performed by each algorithm under the connection weight and the threshold value specified by the processing in blocks 701, 704, and 706, and the obtained solution (minimum energy value) and WA at that time, Wσ, aA,
Record aσ. Instead of the solution values themselves, the rank obtained by comparing them may be recorded. When the above processing is completed, the processing is moved to the block 705.

By referring to the results of the performance comparisons thus obtained, it is possible to select the optimum algorithm from the given homogenous statistics of any given neural network. The energy minimization calculation of a given neural network may be executed using the algorithm described above. FIG. 7B is a PAD diagram showing a processing procedure for selecting an optimum algorithm for a given neural network. The processing in each block in the figure is as follows.

Block 708: Coupling weights and threshold statistics Wσ, W of a given neural network.
Calculate A, aσ, and aA. Block 709: Refer to the above-mentioned algorithm performance comparison result for the statistic closest to the statistic obtained in block 708. Block 710: Select the algorithm that gives the smallest energy value based on the result of the reference in block 709. From this point of view, when there are a plurality of equivalent algorithms, the selection may be performed according to another factor, for example, the calculation time.

Next, the effectiveness of this selection method will be examined by the cyclic search.
The Rusman problem (hereinafter abbreviated as the TSP problem) will be verified as an example. The TSP problem is a problem of finding a route that minimizes the total travel distance between cities when passing through each city only once and traveling around all cities. This is a so-called NP-complete problem that is difficult to solve within a time that can be represented by a polynomial. The energy function of the TSP problem is shown in the following equation.

[0035]

[Equation 2]

However, the neurons are arranged in n rows and n columns, each row corresponds to each city, and each column corresponds to the rank of the tour. V _Xi represents the output of the neuron in row X and column i, and d _XY
Represents the distance between the Xth and Yth cities, and A, B, and C represent arbitrary constants. The first term of this energy function takes the minimum value “0” when each V _XY saturates to one of the binary values (0, 1), and the second term is one new value in each row and each column. -Only Ron outputs "1", all other neurons output "0", and take the minimum value "0",
The third term corresponds to the total traveling distance, and if this becomes the minimum, the solution has been obtained. Corresponding equation 2 to equation 1, the connection weight and the threshold value are set.

Adjusting the constants A, B, and C, Wσ, W
A comparison of normalized energy-E / N obtained by each algorithm when A, aσ, and aA are changed in three ways is shown in FIG. 8, and obtained by each algorithm under the condition 2 in FIG. The patrol route thus obtained is shown in FIG. In FIG.
(A) H method (repeated 1000 times), (B) SA method (repeated 1000 times), (C) MFAA method (repeated 1000 times).
(D), mixed method (repeated 10 times by MFAA method, SA
Method 1000 times).

Under conditions 1 and 2, the algorithm excellence was in the order of the mixed method, the MFAA method, the H method, and the SA method. Under the condition 3, the mixed method, the MFAA method, and the H method were almost equivalent, and the SA method was slightly inferior. This result is shown in FIG.
It does not conflict with the corresponding rank in Wσ of (A). WA and aA
However, the difference between the mixed method and the MFAA method and the H method became small. However, as in FIG. 5A, Wσ
The energy difference tends to decrease as is smaller, and even if the energy difference is small, the difference in FIG.
Since the patrol route is different between (C) and (D),
It can be confirmed that this is not just a numerical error.

Therefore, it is possible to select the optimum algorithm for a given problem from a plurality of algorithms by the above method. Next, a method for updating the neuron state according to the present invention will be described. This method improves the convergence of the synchronous state update method, thereby allowing the state update to be performed in a short time with a simple program, and thus to speed up the energy minimization calculation.

The state updating method according to the present invention synchronously updates the states of all neurons according to the following equation.

[0041]

Equation 3] _{V i (t + 1) =} {V i '(t + 1) + τV i (t)} / (1 + τ) V i' (t + 1) = f (V i (t))

Here, V _i (t) is the time t, that is,
The output of each neuron obtained in the t-th iteration calculation is shown. The function f represents the algorithm that updates the neuron state, so V _i '(t + 1) is the neuron output at time t + 1 obtained with the conventional synchronous update method. The parameter τ can be appropriately selected within the range described later and may be, for example, a constant. Note that τ = 0 is equivalent to a normal synchronous update. The above equation means that the change amount of the state update by this method is compressed to 1 / (1 + τ) of the change amount by the conventional method.
That is, Equation 3 is equivalent to the following equation.

[0043]

Equation 4] _{V i (t + 1) -V} i (t) = {V i '(t + 1) -V i (t)} / (1 + τ)

The effectiveness of this method is verified by numerical simulation. The target model was a spin glass model (Neuron number 50), and the MFAA method was applied.

First, in the method shown in Equation 3, the change in the minimum energy value when τ is changed is shown in FIG.
Shown in. In the illustrated graph, the average value of the obtained results is plotted with the normal random number sequence of 10 different series as the initial state. Further, FIG. 10B shows the ratio of the converged states among the 10 types of initial states.

According to FIG. 10A, τ = 0 to τ = 0.
Up to 1, satisfactory results cannot be obtained. This is
As 0 (B) shows, there are cases where it did not converge,
This is because the value at that time is also included in the average value calculation. τ =
Above 0.2, all initial states cause convergence and the energy values are relatively stable. However, τ =
Compared with the case of 0.2, a slight deterioration can be seen at τ = 0.4. This is probably because increasing τ makes it difficult to change to a new state. Therefore, the value of τ is
It can be said that it is preferable to set it so that it is 0.2 or more and not too large.

Next, the asynchronous calculation method which is generally considered to have the best convergence, the simple synchronous calculation method, and the odd-numbered neuron group and the even-numbered neuron group described in Reference 4 are used. The checker-board method, which separately calculates the synchronization, and the four methods of the present invention will be compared and examined.

As the simulation conditions, the number of iterations t in each method is 10,000, and the parameter τ is 0.2.
Then, 10 different normal random number sequences were set as the initial state of the neuron. The simulation result by the vector calculation of the super computer is shown in FIG. 11 as an average value.

In the synchronous calculation, the speed is higher than that in the asynchronous calculation and the calculation time is shorter, but vibration occurs between the two states for the five types of initial states. In other words, it can be seen that the synchronous calculation method has a relatively poor convergence.
On the other hand, in the checkerboard method, it converged safely regardless of the initial state. The calculation time is longer than that of the synchronous calculation, but shorter than that of the asynchronous calculation. Next, according to the method of the present invention, the convergence is good and the checkerboard
It can be seen that it is faster than the Do method. Therefore, the method of the present invention is faster and simpler in program description than the conventional checkerboard method.

In the above simulation, the parameter τ
Was fixed to a constant value, but τ may be changed as a function of the iteration number t. In that case, if τ is gradually increased from a small value to a large value as t increases, the convergence becomes better, and conversely, if τ is gradually decreased from a large value to a small value, it is optimal. It can be expected that a solution closer to the solution can be obtained. In addition, this method can be applied to other than the MFAA method, and similar effects can be expected.

FIG. 12 shows the detailed procedure of this method by PAD.
Shown in the figure. The processing in each block in the figure is as follows.

Block 1201: Set the number of iterations T of the state update calculation. Block 1202: Set the initial state of each neuron. Block 1203: Blocks 1204-1207 are repeated until the number of iterations set in block 1201 is reached. Block 1204: For all neurons (i = 1,
, N), from the t-th iteration output V _i (t), iteration t + 1
The th output V _i '(t + 1) is calculated synchronously according to the chosen energy-minimization algorithm. Block 1205: Set the parameter τ. Block 1206: For all neurons (i = 1,
, N), V _i (t) and V calculated in block 1204
_{Using i} ′ (t + 1) and τ set in the block 1205, a new output V _i (t + 1) is calculated according to Equation 3.

It goes without saying that this state update algorithm can be similarly applied to the calculation for the performance comparison of the above-mentioned algorithms.

The present invention can also be applied to the selection and execution of optimal algorithms for nonlinear programming.
One of the methods for solving combinatorial optimization problems is nonlinear programming, and various algorithms for it have been proposed.
It is desirable to select the optimal algorithm according to the problem. Those algorithms set the evaluation function equivalent to the energy function in the neural network,
It results in an algorithm that searches for its minimum (or maximum) by an iterative method. The coefficient of the first-order term of this evaluation function corresponds to the threshold value in the neural network, and the coefficient of the second-order term corresponds to the connection weight. Therefore, substituting the energy minimization algorithm in the above embodiment with these search algorithms,
It is possible to select and execute an optimal algorithm for nonlinear programming.

In other words, the coefficient of the first-order term and the coefficient of the second-order term of the evaluation function are variously made different from each other, and the plurality of search algorithms are used for the minimization (or the maximization). The comparison data of the minimum value (or the maximum value) is stored in the storage device. Given a problem, calculate the mean and variance of the coefficients of the first-order term and the second-order term of the evaluation function, and refer to the above-mentioned contrast data based on these values to determine the minimum (or maximum) The algorithm that gives the evaluation function value of is selected as the optimum algorithm and executed. The execution of this algorithm includes an iterative updating process similar to that in the energy minimization calculation of the neural network, and for this process, the synchronous calculation accompanied by the compression of the state change amount can be applied.

The present invention can also be applied to an algorithm for associative memory by a neural network. In general, it is possible to make a neural network have multiple energy minima of similar depth, that is, multiple different stable states of the network, by choosing appropriate coupling weights and thresholds, and which Whether it converges to a stable state depends on the initial state of each neuron. Associative memory is realized by associating each initial state with an input pattern and associating a stable state that converges from the initial state with an output pattern. There are various algorithms for realizing such associative memory, and the superiority or inferiority between them depends on the memory content to be set.

According to the present invention, the respective averages and variances of the correlation amounts between the various key patterns to be set are changed in advance, each algorithm is applied, and the comparison data indicating the superiority or inferiority of the results is created and stored. Store in the device. As the correlation amount,
The dot product between key patterns can be used. That is, the initial state of the i-th neuron for the p-th key pattern and the q-th key pattern is V
_When expressed by _i (p) and V _i (q), the correlation amount of these patterns is expressed by the following equation.

[0058]

[Equation 5]

It is possible to calculate such a correlation quantity for every pattern pair (p, q) in the group of key patterns to be set, and then to calculate their mean and variance. A plurality of key pattern groups having different average and variance values obtained in this way are prepared, and various associative memory algorithms are applied to each key pattern group to calculate the connection weight, threshold value, and output pattern. To do. Then, a group of test patterns consisting of correct key patterns and patterns different from them in various degrees is given as an input, an output pattern is calculated, and the rate at which a correct response occurs is stored in a storage device as contrast data. When the key pattern group to be set is given, the average and variance of the correlation amount of those patterns are calculated, and the algorithm giving the highest correct answer rate under the condition closest to it is selected and executed. The iterative update of the state of the neuron, which is performed when calculating the output pattern, can be applied by the synchronous calculation accompanied by the compression of the state change amount as described above.

[0060]

According to the present invention, the most suitable algorithm for each given various multimodal multivariable functions can be preselected and executed by a computer. In this case, it is possible to expect reliable convergence while reducing the calculation time by synchronous calculation. Therefore, it is possible to extremely efficiently perform a search for a minimum point or a maximum point of a multimodal multivariable function that generally takes a long time.

In addition, since the change of the object to which the algorithms are applied for collecting the contrast data is determined by the change of the statistical amount, it is possible to use various kinds of functions with a relatively small amount of the contrast data. The optimum algorithm for each of these can be selected accurately.

[Brief description of drawings]

FIG. 1 is a block diagram showing a system configuration of the present invention.

FIG. 2 is a schematic diagram showing the configuration of an interconnected neural network.

FIG. 3 is a schematic diagram showing the function of a neuron.

FIG. 4 is a graph showing a neuron output function.

FIG. 5 is a graph showing a performance comparison of algorithms when the weighted combination statistics are changed.

FIG. 6 is a graph showing a performance comparison of algorithms when the threshold statistic changes.

FIG. 7 is a PAD showing a processing procedure for comparing performances of algorithms and a processing procedure for selecting an optimum algorithm according to the present invention.
Fig.

FIG. 8 is a diagram showing an example of performance comparison data of various algorithms when applied to a traveling salesman problem.

FIG. 9 is a diagram showing an example of a solution of a traveling salesman problem obtained by various algorithms.

FIG. 10 is a graph showing the effect of the state update method of the present invention.

FIG. 11 is a diagram showing comparison data between the state update method of the present invention and another method.

FIG. 12 is a PAD diagram showing a processing procedure of a status update method according to the present invention.

[Explanation of symbols]

101 ... Storage device storing algorithm comparison data and execution program 103 ... Computer 701-707 ... Comparison data creation procedure 708-710 ... Optimal algorithm selection procedure 1201-1207 ... Iterative update procedure

Claims (12)

[Claims] 1. A plurality of algorithms for searching for a minimum point or a maximum point of a multimodal multivariable function, wherein each of the plurality of multimodal multivariable functions differing in the value of the statistic of the quantity characterizing the function. The storage device storing the contrast data, which shows the contrast of the results applied to the, and the optimum algorithm for the given multimodal multivariable function, and the statistics of the quantity characterizing the given multimodal multivariable function. An optimum algorithm selecting device, comprising: a processing device that selects from the plurality of algorithms based on a value of quantity and the comparison data. 2. The optimum algorithm selecting device according to claim 1, wherein the statistic includes at least one of a mean and a variance. 3. The function according to claim 1, wherein the function is an energy function of a neural network, the quantity characterizing the function is at least one of a synaptic connection weight and a threshold value of a neuron, and the contrast data is calculated. Optimal algorithm selection device that is the minimum energy value. 4. The function according to claim 1 or 2, wherein the function is an evaluation function in nonlinear programming, the quantity characterizing the function is at least one of coefficients in the evaluation function, and the contrast data is a calculated minimum. Optimal algorithm selection device that is a function value or maximum function value. 5. The function according to claim 1 or 2, wherein the function is a function representing a characteristic of an associative memory composed of a neural network, and the amount representing the characteristic of the function is a correlation amount of a group of key patterns of the associative memory. The optimum algorithm selecting device, wherein the comparison data is data indicating the correctness rate of the response of the associative memory. 6. A method, implemented in an apparatus according to any of claims 1 to 4, for calculating the value of a statistic of a quantity characterizing a given multimodal multivariable function, said method comprising: Referring to the comparison data, and selecting an algorithm that gives a minimum or maximum function value to the statistic value closest to the calculated statistic value. 7. A method performed in an apparatus according to claim 5, wherein at least one of a mean value and a variance value of correlation values between pattern pairs in a given group of key patterns is calculated. And a step of selecting, with reference to the comparison data, an algorithm that gives the best correctness rate to a value of the same kind that is closest to the calculated value. 8. The algorithm selecting step according to claim 6 or 7, wherein, when there are a plurality of algorithms giving substantially the same function value or correctness rate, the algorithm having the shortest calculation time is selected from them. The optimal algorithm selection method. 9. The program according to claim 1, wherein the storage device further stores a program for executing each of the plurality of algorithms, and the processing device stores the selected optimum algorithm. An optimal algorithm execution device that executes a program for execution. 10. A method of executing the selected algorithm in an apparatus according to claim 9, wherein the step of iteratively updating the value of each variable of the function is tentative according to the selected algorithm. Of calculating the update value of, the step of compressing the difference between the tentative update value and the value before update according to a predetermined parameter to determine the value after update, and applying the calculation step and the determining step An optimal algorithm execution method comprising the step of synchronously updating the value of a variable. 11. The optimal algorithm execution method according to claim 10, wherein the parameters for the compression are kept constant during all iterations. 12. The optimum algorithm executing method according to claim 10, including a step of changing a parameter for the compression in a constant direction as the number of times of iterative update progresses.