US5452400A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method of optimizing a combination using a neural network
Assignee: Mitsubishi Electric Corp
•
Filing: 1994-03-11
•
Granted: 1995-09-19
•
Expires: 2014-03-11
Abstract
Abstract A neural network for solving the problem of the optimization of the arrangement of at least two parts which are combined with each other through connecting wires. One neuron is assigned to each part. Each neuron has a synapse with a weight. Weights of the synapses of a neuron are initially set, and a learning process is repeated a while satisfying restricting conditions. In the learning process, the fittest neurons for all the coordinates of the positions at which the parts are disposed are selected in accordance with a predetermined standard while serially updating the weights of the synapses of the neurons so as to satisfy the restricting conditions. After the fittest neurons for all the coordinates of the positions are selected, judgment is made as to whether or not the arrangement obtained in the current learning cycle is closer to an optimal arrangement than any other arrangement which has been obtained in previous learning cycles. The optimal arrangement obtained from a set of learning cycles is provided as an indication of a quasi-optimal arrangement.
Inventors
- 👤 Masanobu Takahashi
- 👤 Kazuo Kyuma
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 20:20
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/392; G06N; G06N3/00; G06N3/02; G06N3/08; G06N3/086
Claims Analysis
Total Claims: 88
Claim 1
Independent Claim
236 words
A method utilizing a neural network for solving a problem of optimizing an arrangement of a plurality of interconnected parts among N positions in M dimensions, the neural network having a plurality of neurons, each neuron having at least one input, each input having a synapse, each synapse having a weight, a composite weight being formed for a neuron as an ordered combination of the weight of each synapse of the neuron, the method comprising the steps of: a) assigning each of the plurality of neurons to a different part, of the plurality of parts; b) initializing the weight of each synapse of each neuron; and c) determining an arrangement of parts by performing a learning cycle, the learning cycle comprising the steps of: i) inputting a position coordinate indicative of one of the N positions to the inputs of a set of neurons, of the plurality of neurons; ii) generating, for each neuron of the set of neurons, a similarity value responsive to the input coordinate to a neuron and the composite weight of the neuron; iii) selecting a fittest neuron, from the set of neurons, whose similarity value is an extreme value across the set of neurons; iv) updating the weight of each synapse of the neurons of the set of neurons; and d) repeating the steps c)i through c)iv until all of the plurality of neurons have been selected as a fittest neuron.
Claim 2
Independent Claim
236 words
A method utilizing a neural network for solving a problem of optimizing an arrangement of a plurality of interconnected parts among N positions in M dimensions, the neural network having a plurality of neurons, each neuron having at least one input, each input having a synapse, each synapse having a weight, a composite weight being formed for a neuron as an ordered combination of the weight of each synapse of the neuron, the method comprising the steps of: a) assigning each of the plurality of neurons to a different part, of the plurality of parts; b) initializing the weight of each synapse of each neuron; and c) determining an arrangement of parts by performing a learning cycle, the learning cycle comprising the steps of: i) inputting a position coordinate indicative of one of the N positions to the inputs of a set of neurons, of the plurality of neurons; ii) generating, for each neuron of the set of neurons, a similarity value responsive to the input coordinate to a neuron and the composite weight of the neuron; iii) selecting a fittest neuron, from the set of neurons, whose similarity value is an extreme value across the set of neurons; iv) updating the weight of each synapse of the neurons of the set of neurons; and d) repeating the steps c)i through c)iv until all of the plurality of neurons have been selected as a fittest neuron.
Claim 3
Dependent Claim
26 words
The method of claim 1, wherein the similarity value is a function of a difference between the position coordinate and the composite weight of a neuron.
Claim 4
Dependent Claim
25 words
The method of claim 2, wherein the similarity value is a function of a squared Euclidian distance between the position coordinate and the composite weight.
Claim 5
Dependent Claim
17 words
The method of claim 1, wherein the similarity value is further a function of a restricting condition.
Claim 6
Dependent Claim
24 words
The method of claim 4, wherein the restricting condition biases a predetermined neuron to be positioned at a predetermined position of the N positions.
Claim 7
Dependent Claim
24 words
The method of claim 4, wherein the restricting condition biases a predetermined neuron to be excluded from a predetermined position of the N positions.
Claim 8
Dependent Claim
18 words
The method of claim 1, wherein each neuron has M inputs, one for each of the M dimensions.
Claim 9
Dependent Claim
11 words
The method of claim 7, wherein M equals two or three.
Claim 10
Dependent Claim
33 words
The method of claim 1, further including the step of updating the set of neurons, after the step of selecting a fittest neuron, to exclude the fittest neuron from the set of neurons.
Claim 11
Dependent Claim
28 words
The method of claim 1, further including the step of assigning the part to which the fittest neuron is assigned to the position indicated by the position coordinate.
Claim 12
Dependent Claim
29 words
The method of claim 10, wherein the learning cycle further includes the step of determining a total wiring length for the arrangement of parts determined by the learning cycle.
Claim 13
Dependent Claim
18 words
The method of claim 11, further including the step of repeating the learning cycle a plurality of times.
Claim 14
Dependent Claim
32 words
The method of claim 12, wherein the learning cycle is repeated a predetermined number of times, and wherein a quasi-optimal arrangement is selected as the arrangement yeilding a minimum total wiring length.
Claim 15
Dependent Claim
28 words
The method of claim 12, wherein the learning cycle is repeated until a total wiring length is obtained for an arrangement that is less than a predetermined threshold.
Claim 16
Dependent Claim
29 words
The method of claim 12, wherein a learning cycle is repeated until successive repetitions of the learning cycle fail to realize any significant reduction in the total wiring length.
Claim 17
Dependent Claim
26 words
The method of claim 1, wherein the step of initializing the weight of each synapse of each neuron includes initializing the weight to a random value.
Claim 18
Dependent Claim
49 words
The method of claim 1, wherein the step of updating the weight of each synapse of a neuron includes changing the weight by an amount ΔWi equal to a product of a wiring function, f(i,b), and a difference between the input position and the composite weight of the neuron.
Claim 19
Dependent Claim
16 words
The method of claim 17, wherein the wiring function for the fittest neuron is a constant.
Claim 20
Dependent Claim
40 words
The method of claim 18, wherein the wiring function for a neuron other than the fittest neuron is proportional to a number of connecting wires between a part assigned to the neuron and a part assigned to the fittest neuron.
Claim 21
Dependent Claim
63 words
The method of claim 19, wherein ΔW.sub.i =(Xs-W.sub.i)·ε·f(i, b), wherein ##EQU4## wherein ε is a learning rate constant between zero and one, f(i, b) is 1 when the i-th neuron is the fittest neuron and α·h ib in the other cases, h ib represents a number of connecting wires between the i-th part and a b-th part, and α is a wiring constant.
Claim 22
Dependent Claim
12 words
The method of claim 20, wherein α is between zero and one.
Claim 23
Dependent Claim
19 words
The method of claim 21, wherein multiple learning cycles are performed, and wherein α is varied between learning cycles.
Claim 24
Dependent Claim
11 words
The method of claim 20, wherein ε is a selectable constant.
Claim 25
Dependent Claim
40 words
The method of claim 19, wherein the wiring function for a neuron other than the fittest neuron is further indicative of a number of interconnecting wires between the part assigned to the fittest neuron and a plurality of other parts.
Claim 26
Dependent Claim
41 words
The method of claim 24, wherein the wiring function for a current neuron other than the fittest neuron is further indicative of a number of interconnecting wires between the part assigned to the current neuron and a plurality of other parts.
Claim 27
Dependent Claim
81 words
The method of claim 25, wherein the wiring function f(i,b)=α·h.sub.ib +Σ.sub.j (α·h.sub.jb ×α'×h.sub.ij) wherein h ib represents a number of connecting wires between the i-th part and a b-th part, α is a wiring constant, α' is a constant, j is a positive integer representing a j-th neuron, h jb is the number of connecting wires between a j-th part and a b-th part, and h ij is the number of connecting wires between an i-th part and a j-th part.
Claim 28
Dependent Claim
16 words
The method of claim 1, implemented on a general purpose computer using a computer programming language.
Claim 29
Dependent Claim
10 words
The method of claim 1, implemented on a parallel computer.
Claim 30
Dependent Claim
12 words
The method of claim 1, implemented with a special purpose hardware circuit.
Claim 31
Dependent Claim
34 words
The method of claim 1, wherein the step of inputting a position coordinate includes selecting the position coordinate from one of the N positions which have not been previously selected in the learning cycle.
Claim 32
Dependent Claim
219 words
A computer-implemented neural network system for arranging a plurality of parts among N positions in M-dimensions, including a plurality of neurons, wherein each neuron has M inputs, each input having a synapse, each synapse having a weight, and each neuron having an output indicative of similarity of the inputs to the weights, the parts being combined with one another through a set of connecting wires, the neural network system comprising: means for assigning each of the plurality of neurons to a different part; means for initializing the weight of each synapse of each neuron; and means for executing a learning cycle, comprising: means for inputting a position coordinate to the inputs of the neurons, indicative of one of the N positions at which a part can be placed; means, responsive to the input position coordinate, for generating a similarity value for each neuron; means for selecting a fittest neuron, responsive to the similarity value for each neuron, wherein the fittest neuron is the neuron whose weights are most similar to the input position coordinate; means for updating the weights of the synapses of the plurality of neurons; and means for repetitively operating the means for inputting, means for generating, means for selecting, and means for updating, so that a fittest neuron is selected for each of the N positions.
Claim 33
Dependent Claim
219 words
A computer-implemented neural network system for arranging a plurality of parts among N positions in M-dimensions, including a plurality of neurons, wherein each neuron has M inputs, each input having a synapse, each synapse having a weight, and each neuron having an output indicative of similarity of the inputs to the weights, the parts being combined with one another through a set of connecting wires, the neural network system comprising: means for assigning each of the plurality of neurons to a different part; means for initializing the weight of each synapse of each neuron; and means for executing a learning cycle, comprising: means for inputting a position coordinate to the inputs of the neurons, indicative of one of the N positions at which a part can be placed; means, responsive to the input position coordinate, for generating a similarity value for each neuron; means for selecting a fittest neuron, responsive to the similarity value for each neuron, wherein the fittest neuron is the neuron whose weights are most similar to the input position coordinate; means for updating the weights of the synapses of the plurality of neurons; and means for repetitively operating the means for inputting, means for generating, means for selecting, and means for updating, so that a fittest neuron is selected for each of the N positions.
Claim 34
Dependent Claim
26 words
The system of claim 31, wherein the similarity value is a function of a difference between the position coordinate and the composite weight of a neuron.
Claim 35
Dependent Claim
25 words
The system of claim 32, wherein the similarity value is a function of a squared Euclidian distance between the position coordinate and the composite weight.
Claim 36
Dependent Claim
17 words
The system of claim 31, wherein the similarity value is further a function of a restricting condition.
Claim 37
Dependent Claim
24 words
The system of claim 34, wherein the restricting condition biases a predetermined neuron to be positioned at a predetermined position of the N positions.
Claim 38
Dependent Claim
24 words
The system of claim 34, wherein the restricting condition biases a predetermined neuron to be excluded from a predetermined position of the N positions.
Claim 39
Dependent Claim
18 words
The system of claim 31, wherein each neuron has M inputs, one for each of the M dimensions.
Claim 40
Dependent Claim
11 words
The system of claim 37, wherein M equals two or three.
Claim 41
Dependent Claim
32 words
The system of claim 31, further including means for updating the set of neurons, after the step of selecting a fittest neuron, to exclude the fittest neuron from the set of neurons.
Claim 42
Dependent Claim
27 words
The system of claim 31, further including means for assigning the part to which the fittest neuron is assigned to the position indicated by the position coordinate.
Claim 43
Dependent Claim
29 words
The system of claim 40, wherein the learning cycle further includes the step of determining a total wiring length for the arrangement of parts determined by the learning cycle.
Claim 44
Dependent Claim
17 words
The system of claim 41, further including means for repeating the learning cycle a plurality of times.
Claim 45
Dependent Claim
32 words
The system of claim 42, wherein the learning cycle is repeated a predetermined number of times, and wherein a quasi-optimal arrangement is selected as the arrangement yeilding a minimum total wiring length.
Claim 46
Dependent Claim
28 words
The system of claim 42, wherein the learning cycle is repeated until a total wiring length is obtained for an arrangement that is less than a predetermined threshold.
Claim 47
Dependent Claim
29 words
The system of claim 42, wherein a learning cycle is repeated until successive repetitions of the learning cycle fail to realize any significant reduction in the total wiring length.
Claim 48
Dependent Claim
25 words
The system of claim 31, wherein means for initializing the weight of each synapse of each neuron includes initializing the weight to a random value.
Claim 49
Dependent Claim
48 words
The system of claim 31, wherein means for updating the weight of each synapse of a neuron includes updating the weight by an amount ΔWi equal to a product of a wiring function, f(i,b), and a difference between the input position and the composite weight of the neuron.
Claim 50
Dependent Claim
16 words
The system of claim 47, wherein the wiring function for the fittest neuron is a constant.
Claim 51
Dependent Claim
40 words
The system of claim 48, wherein the wiring function for a neuron other than the fittest neuron is proportional to a number of connecting wires between a part assigned to the neuron and a part assigned to the fittest neuron.
Claim 52
Dependent Claim
63 words
The system of claim 49, wherein ΔW.sub.i =(Xs-W.sub.i)·ε·f(i, b), wherein ##EQU5## wherein ε is a learning rate constant between zero and one, f(i, b) is 1 when the i-th neuron is the fittest neuron and α·h ib in the other cases, h ib represents a number of connecting wires between the i-th part and a b-th part, and α is a wiring constant.
Claim 53
Dependent Claim
12 words
The system of claim 50, wherein α is between zero and one.
Claim 54
Dependent Claim
20 words
The system of claim 51, further including means for repeating learning cycles and means for urging α between learning cycles.
Claim 55
Dependent Claim
11 words
The system of claim 50, wherein ε is a selectable constant.
Claim 56
Dependent Claim
40 words
The system of claim 49, wherein the wiring function for a neuron other than the fittest neuron is further indicative of a number of interconnecting wires between the part assigned to the fittest neuron and a plurality of other parts.
Claim 57
Dependent Claim
41 words
The system of claim 54, wherein the wiring function for a current neuron other than the fittest neuron is further indicative of a number of interconnecting wires between the part assigned to the current neuron and a plurality of other parts.
Claim 58
Dependent Claim
81 words
The system of claim 55, wherein the wiring function f(i,b)=α·h.sub.ib +Σ.sub.j (α·h.sub.jb ×α'×h.sub.ij) wherein h ib represents a number of connecting wires between the i-th part and a b-th part, α is a wiring constant, α' is a constant, j is a positive integer representing a j-th neuron, h jb is the number of connecting wires between a j-th part and a b-th part, and h ij is the number of connecting wires between an i-th part and a j-th part.
Claim 59
Dependent Claim
16 words
The system of claim 31, implemented on a general purpose computer using a computer programming language.
Claim 60
Dependent Claim
10 words
The system of claim 31, implemented on a parallel computer.
Claim 61
Dependent Claim
12 words
The system of claim 31, implemented with a special purpose hardware circuit.
Claim 62
Dependent Claim
36 words
The system of claim 31, wherein the means for inputting a position coordinate includes means for selecting a position coordinate from one of the N positions which have not been previously selected in the learning cycle.
Claim 63
Dependent Claim
216 words
A computer system utilizing a neural network model for optimizing an arrangement of a plurality of parts among N positions of in M-dimensions, the parts being connected through a set of connecting wires, the computer system comprising: a neural network having a plurality of neurons, wherein each neuron has M inputs, each input having a synapse, each synapse having a weight, each neuron having an output indicative of a similarity of the inputs to the weights, each neuron being assigned to a different part; means for initializing the weight of each synapse of each neuron; means for executing a learning process, comprising: i) means for selecting one of the N positions and inputting a position coordinate identifying the selected position to the inputs of a set of neurons of the plurality of neurons; ii) means, within each of the neurons, for generating a similarity value, responsive to the input position coordinate; iii) means for selecting a fittest neuron from among the set of neurons, responsive to the similarity value of each neuron of the set of neurons, wherein the fittest neuron is the neuron whose weights are most similar to the input position coordinate; and iii) means for updating the weights of the synapses of the set of neurons according to a set of restricting conditions.
Claim 64
Dependent Claim
216 words
A computer system utilizing a neural network model for optimizing an arrangement of a plurality of parts among N positions of in M-dimensions, the parts being connected through a set of connecting wires, the computer system comprising: a neural network having a plurality of neurons, wherein each neuron has M inputs, each input having a synapse, each synapse having a weight, each neuron having an output indicative of a similarity of the inputs to the weights, each neuron being assigned to a different part; means for initializing the weight of each synapse of each neuron; means for executing a learning process, comprising: i) means for selecting one of the N positions and inputting a position coordinate identifying the selected position to the inputs of a set of neurons of the plurality of neurons; ii) means, within each of the neurons, for generating a similarity value, responsive to the input position coordinate; iii) means for selecting a fittest neuron from among the set of neurons, responsive to the similarity value of each neuron of the set of neurons, wherein the fittest neuron is the neuron whose weights are most similar to the input position coordinate; and iii) means for updating the weights of the synapses of the set of neurons according to a set of restricting conditions.
Claim 65
Dependent Claim
26 words
The system of claim 61, wherein the similarity value is a function of a difference between the position coordinate and the composite weight of a neuron.
Claim 66
Dependent Claim
25 words
The system of claim 62, wherein the similarity value is a function of a squared Euclidian distance between the position coordinate and the composite weight.
Claim 67
Dependent Claim
18 words
The system of claim 61, wherein the similarity value is a further a function of a restricting condition.
Claim 68
Dependent Claim
24 words
The system of claim 64, wherein the restricting condition biases a predetermined neuron to be positioned at a predetermined position of the N positions.
Claim 69
Dependent Claim
24 words
The system of claim 64, wherein the restricting condition biases a predetermined neuron to be excluded from a predetermined position of the N positions.
Claim 70
Dependent Claim
29 words
The system of claim 61, wherein the learning cycle further includes the step of determining a total wiring length for the arrangement of parts determined by the learning cycle.
Claim 71
Dependent Claim
18 words
The system of claim 67, further including the step of repeating the learning cycle a plurality of times.
Claim 72
Dependent Claim
32 words
The system of claim 68, wherein the learning cycle is repeated a predetermined number of times, and wherein a quasi-optimal arrangement is selected as the arrangement yeilding a minimum total wiring length.
Claim 73
Dependent Claim
28 words
The system of claim 68, wherein the learning cycle is repeated until a total wiring length is obtained for an arrangement that is less than a predetermined threshold.
Claim 74
Dependent Claim
29 words
The system of claim 68, wherein a learning cycle is repeated until successive repetitions of the learning cycle fail to realize any significant reduction in the total wiring length.
Claim 75
Dependent Claim
49 words
The system of claim 61, wherein the step of updating the weight of each synapse of a neuron includes changing the weight by an amount ΔWi equal to a product of a wiring function, f(i,b), and a difference between the input position and the composite weight of the neuron.
Claim 76
Dependent Claim
16 words
The system of claim 72, wherein the wiring function for the fittest neuron is a constant.
Claim 77
Dependent Claim
40 words
The system of claim 73, wherein the wiring function for a neuron other than the fittest neuron is proportional to a number of connecting wires between a part assigned to the neuron and a part assigned to the fittest neuron.
Claim 78
Dependent Claim
62 words
The system of claim 74, wherein ΔW.sub.i =(Xs-W.sub.i)·ε·f(i,b), wherein ##EQU6## wherein ε is a learning rate constant between zero and one, f(i, b) is 1 when the i-th neuron is the fittest neuron and α·h ib in the other cases, h ib represents a number of connecting wires between the i-th part and a b-th part, and α is a wiring constant.
Claim 79
Dependent Claim
12 words
The system of claim 75, wherein α is between zero and one.
Claim 80
Dependent Claim
19 words
The system of claim 76, wherein multiple learning cycles are performed, and wherein α is varied between learning cycles.
Claim 81
Dependent Claim
11 words
The system of claim 75, wherein ε is a selectable constant.
Claim 82
Dependent Claim
40 words
The system of claim 74, wherein the wiring function for a neuron other than the fittest neuron is further indicative of a number of interconnecting wires between the part assigned to the fittest neuron and a plurality of other parts.
Claim 83
Dependent Claim
41 words
The system of claim 79, wherein the wiring function for a current neuron other than the fittest neuron is further indicative of a number of interconnecting wires between the part assigned to the current neuron and a plurality of other parts.
Claim 84
Dependent Claim
81 words
The system of claim 80, wherein the wiring function f(i,b)=α·h.sub.ib +Σ.sub.j (α·h.sub.jb ×α'×h.sub.ij) wherein h ib represents a number of connecting wires between the i-th part and a b-th part, α is a wiring constant, α' is a constant, j is a positive integer representing a j-th neuron, h jb is the number of connecting wires between a j-th part and a b-th part, and h ij is the number of connecting wires between an i-th part and a j-th part.
Claim 85
Dependent Claim
16 words
The system of claim 61, implemented on a general purpose computer using a computer programming language.
Claim 86
Dependent Claim
10 words
The system of claim 61, implemented on a parallel computer.
Claim 87
Dependent Claim
12 words
The system of claim 61, implemented with a special purpose hardware circuit.
Claim 88
Dependent Claim
28 words
The system of claim 61, wherein the means for selecting one of the N positions selects a position which have not been previously selected in the learning cycle.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-09-18 | 1999-03-20 | 1999-09-19 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-09-18 | 2003-03-20 | 2003-09-19 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-09-18 | 2007-03-20 | 2007-09-19 | $7700.00 | Window Closed / Lapsed |