Genetic algorithm technique for designing neural networks

• US 5,249,259 A
• Filed: 05/28/1992
• Issued: 09/28/1993
• Est. Priority Date: 01/23/1990
• Status: Expired due to Fees

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Harvey, Robert L.
• Primary Examiner(s): MacDonald, Allen R.
• Application Number:
  US07/892,401
• Time in Patent Office: 488 Days
• Field of Search: 395/13, 395/24, 395/27, 395/23
• US Class Current: 706/13
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

A generic algorithm search is applied to determine an optimum set of values (e.g., interconnection weights in a neural network), each value being associated with a pair of elements drawn from a universe of N elements, N an integer greater than zero, where the utility of any possible set of said values may be measured. An initial possible set of values is assembled, the values being organized in a matrix whose rows and columns correspond to the elements. A genetic algorithm operator is applied to generate successor matrices from said matrix. Matrix computations are performed on the successor matrices to generate measures of the relative utilities of the successor matrices. A surviving matrix is selected from the successor matrices on the basis of the metrics. The steps are repeated until the metric of the surviving matrix is satisfactory.

Claims

1. A computer method for implementing a neural network for use in a selected application, said neural network being implemented to effect a desired relationship between inputs representing real world phenomena and outputs corresponding to the inputs, said neural network having neurons and neurons interconnections each of said neurons possibly having an interconnection to any other of said neurons, each of said interconnections characterized by an associated weight value, said weight values having potentially any value including zero, positive, or negative, the method comprising

(a) by computer, searching possible sets of weight values and selecting a set of weight values for use in the neural network, said step of searching and selecting comprising

(i) picking an initial set of weight values;

(ii) organizing said initial set of weight values in rows and columns, so the weight values in each of said rows all are associated with interconnections to the same one of said neurons, and the weight values in each of said columns all are associated with interconnections from the same one of said neurons;

(iii) generating successor sets of weight values from said initial set of weight values;

(iv) for each of said successor sets of weight values, determining test outputs of a neural network having those weights, when activated by predetermined inputs;

(v) analyzing the merits of each of said successor sets of weight values based on how well the test outputs conform to predetermined outputs;

(vi) selecting a single surviving set of weight values from among said successor sets of weight values based on the relative merits of said surviving set of weight values, said surviving set of weight values serving as an initial set; and

(vii) if the merits of said surviving set of weight values meet a threshold, treating said surviving set of weight values as a final set of weight values;

otherwise repeating steps (iii)-(vi) using said surviving set of weights as a new initial set of weight values; and

(b) implementing said neural network with said final set of weight values.

2. The method of claim 1 further comprising constraining said interconnection weight values to comply with constraints that correspond to said selected application.

3. The method of claim 2 wherein said constraints include requiring that the interconnection weight values between a neuron and itself be zero.

4. The method of claim 2 wherein said constraints include requiring that the interconnection weight values leading from a given neuron all be of the same sign.

5. The method of claim 1 wherein said step of organizing said interconnection weight values comprises organizing said weight values with the interconnection weights leading to a given neuron all appearing in a single row (or a single column), and the interconnection weight values leading from a given neuron all appearing in a single column (or a single row).

6. The method of claim 5 wherein said rows and columns of interconnection weight values are organized in a number of matrices based on layers of neurons in said neural network.

7. The method of claim 6 wherein said neural network comprises a layer of input neurons, a layer of hidden neurons, and a single output neuron.

8. The method of claim 1 wherein said predetermined input comprises binary values which represent edges of an image.

9. The method of claim 1 wherein said step of generating successor sets of weight values comprises applying a genetic algorithm operator to said initial set of weight values.

10. The method of claim 9 wherein said step of applying a genetic algorithm operator comprises applying a mutation operator.

11. The method of claim 10 wherein applying said mutation operator comprises randomly changing a portion of said interconnection weight values.

12. The method of claim 1 wherein said step of analyzing the relative merits of the successor sets of weight values comprises computing a metric corresponding to the difference between said test outputs and said predetermined outputs.

13. The method of claim 12 wherein said step of selecting a surviving matrix comprises testing whether said metric lies within a band between upper and lower bounds.

14. The method of claim 12 wherein said step of selecting a surviving matrix comprises testing whether said metric lies above a passband or below a stop band.

15. The method of claim 1 wherein said predetermined input comprises gray gradient values which represent edges of an image.