Method of Optimizing a Combination Using a Neural Network

1. Field of the Invention

The present invention relates to a method of optimizing an arrangement of parts or the like.

2. Description of Related Art

A part arrangement optimization problem will first be explained. If it is assumed, for example, that the positions for arranging four parts and the number of wires between the respective parts are given as shown in Table 1, the parts arrangement optimization problem is how the parts should be arranged in order to make the total length of wiring the shortest.

Examples of the optimal solution and a non-optimal solution to this problem are shown in FIGS. 4a and 4b, respectively. In FIGS. 4a and 4b, the reference numeral 5 represents a part and 6 a wire. The arrangement shown in FIG. 4a is the optimal arrangement and the arrangement shown in FIG. 4b is an example of a non-optimal solution because the total length of wiring is longer than that in FIG. 4a. There is no analytical solution for the part arrangement optimization problem, and it is necessary to examine all the arrangements in order to attain the optimal solution. However, since there are N! combinations for the arrangement of N parts, if N increases, the calculation time for reaching the optimal solution increases enormously. In other words, the part arrangement optimization problem is a kind of combination optimization problem. Therefore, the object of solving this problem is generally to reach an approximate solution, which is approximate to the optimal solution, at a high speed.

FIG. 5 is a flowchart showing a conventional part arrangement optimization method which is described in Takahashi, W. Balzer, Kyuma: Improvement of Performance of Learning in Boltzmann Machine and Application to Recognition and Optimization Problem (Research Materials for System Control Study Meeting, the Institute of Electrical Engineers of Japan, SC-91-2, pp. 17 to 18, Mar. 19, 1991), and which uses a Boltzmann machine model, one of the mutual combination type neural network models.

The conventional method will now be explained. This method is used to (approximately) optimize the arrangement of N parts when N parts (part numbers 1 to N) and N positions (position numbers I to N) are given one neuron is allotted to each combination (there are N.sup.2 combinations) of a position number and a part number (step ST14). For example, Table 2 shows an example of the allotment of 4 parts.

The symbol n.sub.i represents an i-th neuron. In this case N.sup.2 neurons are used and the state of each neuron represents whether a certain part is disposed at a certain position. For example, the fact that n.sub.10 is in the excited state (the output of the neuron n.sub.10 is "1") means that the part 3 is disposed at the position 2. This introduces the following restricting conditions to the state of a neuron. That is, since one part can be disposed only at one position at one time, only one of the four neurons in each row in Table 1 can assume the excited state at one time. Since only one part can be disposed at one position at one time, only one of the four neurons in each column in Table 1 can assume the excited state at one time. The weight of a combination between neurons is then determined in accordance with the following equation (step S14):

The symbol W.sub.ij represents the synaptic weight from a neuron j to i, and c.sub.1 and c.sub.2 are constants. The symbol W.sub.ij s represents the above-described restricting condition, namely, the suppressive (negative) weight for mutually suppressing the excitation between the neurons in the row and in the column so as to maintain the excited state of only one neuron in one row and in one column. The symbol Wijc represents the weight which reflects the total length of wiring, and is obtained from the following equation:

wherein c.sub.3 is a constant hp.sub.i,p.sub.j represents the number of wires between parts p.sub.i and p.sub.j, and dq.sub.i,q.sub.j represents the distance between positions q.sub.i and q.sub.j, wherein p.sub.i is the residual when i is divided by N, and q.sub.i is the quotient. If W.sub.ij =W.sub.ji, in a mutual combination type neural network model like this example, the energy E of the network is defined by the following equation: ##EQU1## wherein Vi represents the output (excited state: "1", non-excited state: "0") of the i-th neuron. If the weight W.sub.ij is determined in accordance with the equations (1) and (2), the energy E is represented as follows:

The energy E does not change or is reduced when the state of the neurons are updated. Therefore, when the states of the neurons are updated serially, the state of the network becomes stable in the state in which the energy E is the minimum. The state of the neurons at this time determines the arrangement of the parts which minimizes the energy E and, hence, which makes the total length of wiring the shortest, as is obvious from the equation (4). Actually, the minimal point of the energy is obtained by using a technique called a simulated annealing method, which updates the state of the neurons stochastically in order to avoid the influence of a local stable point (minimal point) of the energy (step S16). The arrangement of the parts is determined on the basis of the state of the neurons at that time (step S17). This arrangement is the (quasi-)optimal solution.

In the conventional part arrangement optimization method described above, since N.sup.2 neurons and N.sup.4 weights are necessary for solving the problem for N parts, if the problem is solved by a computer, the memory capacity and the calculation time which are proportional to N.sup.4 are necessary, so that this method cannot be applied to a large-scale problem in which the number of parts is large.

According to this structure, the number of neurons which are necessary for solving the part arrangement optimization problem for N parts is reduced to N. The number of synapses is proportional to N. For example, in the case of determining the two-dimensional arrangement of the N parts, the required number of synaptic weights is 2N and in the case of determining the three-dimensional arrangement of the N parts, the required number of synaptic weights is 3N. The memory capacity and the calculation time required for a computer are therefore reduced, thereby enabling the solution of a large-scale problem in which the number of parts is large.

In the present invention, the part arrangement optimization problem for at least two parts, which are connected through connecting wires, is solved by assigning a neuron to each part, wherein each neuron has a synapse with a weight. The weights are initially set to preferably random values near the center of the search space. A learning process is repeated a number of times after the weights of the synapses are initially set, during which weights of the synapses are updated on the basis of restricting conditions. In this learning process, a fittest neuron is selected for each position at which the parts are disposed. This selection is made in accordance with a predetermined standard. In this arrangement, each part is placed at the position for which its neuron is selected as the fittest neuron. In this process the weights of a selected fittest neuron become approximate to the position at which the part assigned to that neuron is to be disposed.

The arrangement obtained in a current learning cycle is kept as a quasi-optimal arrangement if it is closer to an optimal arrangement than any other arrangement which has been obtained in previous learning cycles after the fittest neurons for all the coordinates of the positions are selected.

The features and advantages of the present invention will become clear from the following description of the preferred embodiment thereof, taken in conjunction with the accompanying drawings.

FIGS. 1a and 1b are flowcharts of a part arrangement optimization method in an embodiment of the present invention;

FIG. 2 shows the structure of a neural network model in this embodiment;

FIG. 3 is an explanatory view of an example of the positions at which 9 parts are disposed in this embodiment;

FIGS. 4a and 4b are explanatory views of examples of the optimal arrangement and a non-optimal arrangement of parts when the number of wires connecting the parts is given, as shown in Table 1; and

FIG. 5 is a flowchart of a conventional part arrangement optimization method.

The present invention will now be explained with reference to an embodiment.

FIGS. 1a and 1b are flowcharts of a part arrangement optimization method in an embodiment of the present invention. In this embodiment, N neurons are used for solving the problem for N parts, where N is an integer equal to or larger than 2. Otherwise, there is no problem of optimizing the part arrangement. One neuron is allotted to each part. It is now assumed that an i-th neuron is allotted to an i-th part. In the case of arranging parts two-dimensionally, a neuron has two input lines. Position coordinates are provided for each input line, as will be described later. The neuron i has a two-dimensional weight W.sub.i =(W.sub.i1, W.sub.i2) [i=1 to N], corresponding to each input line. FIG. 2 shows a neural network model in this embodiment. In FIG. 2, the reference numerals 1a, 1b and 1c represent neurons, 2a, 2b input lines and 3a to 3f synapses having the weights W.sub.i1, W.sub.l2 of the neurons. In the case of using N parts, N possible positions at which the N parts are disposed are determined in advance. FIG. 3 is an example of the positions at which 9 parts are disposed. In FIG. 3, the reference numeral 4 represents the position at which a certain part is disposed, wherein a circle represents the center position at which a certain part is disposed, and the number in the circle represents the position number. The coordinates of each position are represented by X.sub.i =(X.sub.i1,X.sub.i2) [i=1 to N]. The output 4a-4c of each neuron 1a-1c provides a measure of the difference, similarity, or comparison of the input X.sub.i1, X.sub.i2 with the weight of the neuron, for example, the neuron may output the ordered pair (X.sub.i1 -W.sub.i1, X.sub.i2 -W.sub.i2). A controller 8 is connected to the outputs 4a-4c, input lines 2a-2b and synapses 3a, 3c and 3e so as to control the neural network in accordance with this method.

Although the parts are arranged in a two-dimensional lattice, in the embodiment as shown in FIG. 3, the arrangement is not restricted thereto and may be determined as desired. For example, the arrangement may be three-dimensional. Thus, this description can be generalized to more than two dimensions where

The part arrangement optimization method of this embodiment will now be explained with reference to FIG. 1. The learning cycle number T is first set to "0" (step ST1). A neuron is then assigned to each part (step ST2). The weight Wi of a neuron is then initialized, ordinarily, at a random number (step ST3). The part arrangement derived as the solution does not depend upon the initial weights. For instance, the initial weights can be chosen at random, or all the initial weights may be the same. No uniqueness in the initial weights is necessary. In one embodiment, the initial weights are set at random so as to be distributed near the center of the search space.

After the weights are initially set, a first learning cycle is executed. In the first learning cycle, a position S for disposing a part is selected at random from the positions which have not been selected in this learning cycle (step ST4). The position coordinates X.sub.s of the selected position S are input from the input lines 2a and 2b, and the neuron having the weight closest to that of the input signal (this neuron is called the fittest neuron) is selected from the neurons which have not been selected in this learning cycle (step ST5). The number b of the fittest neuron may be represented by the following equation (5a): ##EQU2## wherein U represents the set of neuron numbers which have not been selected in this learning cycle. For example, if a b-th neuron is selected as the fittest neuron for the position S, this means that the b-th part is disposed or arranged at the position S. During the learning cycles the position S is assigned to the b-th part. An actual physical placement of the b-th part at position S may be performed at a later time.

The number b of the fittest neuron may also be determined, for example, in accordance with the following equation (5b):

wherein Xs represents the position coordinates selected by the signal inputting means, W.sub.i the weights of the synapses of an i-th neuron, i the number of a neuron which has not been selected in the current learning cycle, and E(s,i) is a cost function where a part assigned to the i-th neuron is provisionally positioned at the s-th position. The cost function is determined in accordance with restricting conditions. For example, if it is desired to make it difficult to position a part (assigned to a neuron p) at a position r, E(r,p) is set to be large. On the other hand, if it is desired to make it easy to position the part assigned to a neuron p at the position r, E(r,p) is set to be small, e.g., a negative value.

In consideration of restricting conditions, the weights of the neurons are updated by the amount of update represented by the following equations (6) and (7) at the next step (ST 6): ##EQU3## wherein e is a constant called a learning rate and is ordinarily set to be not more than 1, and f(i, b) is 1 when the i-th neuron is the fittest neuron and .alpha..multidot.h.sub.ib in the other cases, wherein .alpha. is a constant called a wiring constant. The constant a is usually equal to or larger than 0 and is equal to or smaller than 1 (i.e., 0.ltoreq..alpha..ltoreq.1). A preferable value of a .alpha. depends upon a part arrangement problem to be solved. Further, .alpha. should be variable among learning cycles. The expression h.sub.ib represents the number of connecting wires between the i-th part and a b-th part. Thus, what are updated are the weights of the synapses of the fittest neuron just previously determined and the weights of the synapses of neurons assigned to parts which are wired to the part assigned to the fittest neuron. Although a two-dimensional value is used in the embodiments, the present invention is also applicable to any dimensions such as three dimensions.

The following equation (8) may also be used instead of equation (7) when i.noteq.b

where .alpha.' is a constant, j is a positive integer representing a j-th neuron, h.sub.jb is the number of connecting wires between a j-th part and a b-th part, and hij is the number of connecting wires between an i-th part and a j-th part. When this equation is used, influences applied via other parts can be taken into account. That is, Equation 8 is helpful in quickly optimizing the respective weights of the neurons because it considers those neurons which are connected to neurons connected to a selected fittest neuron.

A judgment is then made as to whether or not all the positions at which the parts are disposed have been selected in this learning cycle (step ST7). If not all positions have been selected, the process continues with the step of selecting of a position at which a part should be disposed (step ST4). On the other hand, if all of the positions have been selected, the sum L of the virtual lengths of wiring for the determined arrangement of the parts is determined (step ST8). If the arrangement is that shown in FIG. 4a, for example, the virtual length of wiring is calculated as the sum of the distances in the horizontal direction (X) and in the vertical direction (X.sub.2) of two adjacent positions at which parts are disposed.

The sum L of the virtual lengths of wiring obtained is then compared with the minimum sum L.sub.min of the virtual lengths of wiring obtained in the previous learning cycles (step ST9). If L is not smaller than L.sub.min the process proceeds to step ST11, while if L is smaller than L.sub.min the new arrangement of the parts obtained in this learning cycle is stored as the optimal arrangement, and L is substituted into L.sub.min as the minimum sum of the virtual lengths of wiring (step ST10). The first learning cycle is thus ended. At the next step (ST11), "1" is added to the learning cycle number T. The learning cycle number T is then compared with a predetermined maximum number of times T.sub.max for learning (step ST11). If T has not reached T.sub.max, the process returns to step ST3 so as to start the next learning cycle. If T is T.sub.max, the arrangement of the parts which is finally stored as the optimal arrangement is output as the intended (sub)optimal arrangement (step ST13).

Alternatively, the learning process can be terminated when the total length of wiring L is less than a predetermined threshold. As yet a further alternative, the learning process can be terminated when the total length of wiring L for successive repetitions of the learning cycle fails to realize any significant improvement. That is, if the difference between L for a given learning cycle and L.sub.min is small for a series of learning cycles, the learning process may be terminated.

In the above embodiment, the number of positions is equal to the number of parts, but it is possible to similarly optimize the arrangement of parts at positions the number of which is larger than the number of parts by considering dummy parts which are not connected to any other part.

Although the order of selecting the positions at which the parts are disposed is random in this embodiment, the order may be determined in accordance with some standard. The two parameters .epsilon. and .alpha., which are fixed at certain values in this embodiment, may be changed during a learning cycle.

The weights are updated in accordance with the equations (6) and (7) in this embodiment, but these equations are not strictly limiting. For example, a certain change such as the removal of (X.sub.i -W.sub.i) from the equation (6) and a change of "1" on the right-hand side of the equation (7) to "2" similarly enables the optimization of the part arrangement.

Although only the reduction in the total length of wiring as much as possible is aimed at in this embodiment, the optimization of the arrangement of parts including other conditions (e.g., avoidance of crowded wiring and avoidance of the deposition of a specific part at an adjacent position) is also possible. For this purpose, the terms reflecting these conditions may be introduced into the equation (5), for example, and the fittest neuron is selected so as to satisfy these conditions at the step ST 5.

Although the neuron having the weight closest to that of an input signal is selected when the fittest neuron is selected in this embodiment, another neuron may be selected at a certain probability by introducing a noise term into the equation (5), for example. By such a stochastic fluctuation, the abilities of finding the optimal solutions to some problems are enhanced.

As described above, according to the present invention, a method of optimizing the arrangement of at least two parts thus involves allotting a neuron to each part, setting the weights of each neuron, then inputting the coordinates of a position at which a part should be disposed to a neuron as an input signal. A fittest neuron for the input signal is then selected on the basis of a preset standard. The weights of the neurons are updated in accordance with restricting conditions. The weights of each neuron tend to approximate the position for which they were selected as the fittest neuron. These steps are repeated until all the positions for the N parts are selected. In this way, since the problem of arranging N parts at optimal positions is solved by using N neurons and the weight of the synapses of these neurons, it is possible to solve a large-scale problem in which the number of-parts is large and to greatly reduce the cost (for the calculation time and the memory capacity).

This embodiment is applied to a part arrangement optimization problem, but the present invention is not restricted thereto. For example, the present invention is applicable to arrangement of switch boards in a factory or a plant.

Further, when there are parts which are always arranged at constant positions, neurons assigned to these parts can be continuously selected as the fittest neuron for the part arrangement in question.

It will be understood that there are many ways to implement this invention. In particular, the invention could be implemented using a general purpose computer, such as an engineering workstation, which would be programmed to implement an appropriate neural network and controller using a computer programming language, for example, C. A parallel computer, such as those available from Cray, may also be used. The neural network and controller may also be implemented with special purpose hardware circuits.

Having now described an embodiment of the invention, it should be apparent to those skilled in the art that the foregoing is merely illustrative and not limiting, having been presented by way of example only. Numerous modifications and other embodiments are within the scope of one of ordinary skill in the art and are contemplated as falling within the scope of the invention as defined by the appended claims and equivalents thereto .