Fitness function circuit, genetic algorithm machine, and fitness evaluation method

• US 20050267851A1
• Filed: 01/19/2005
• Published: 12/01/2005
• Est. Priority Date: 05/25/2004
• Status: Abandoned Application

• Current Assignee: OKI Electric Industry Company Limited
• Original Assignee: Semiconductor Leading Edge Technologies, Inc.
• Inventors: Wada, Tetsunori, Baba, Shunsuke
• Application Number:
  US11/037,284
• Publication Number:
  US 20050267851A1
• Time in Patent Office: Days
• US Class Current: 706/13
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

An optimization method for extracting a model parameter in a semiconductor circuit. A fitness function circuit 15 installed in a genetic algorithm machine 900 is provided with an evaluated value calculation section 21, which receives an offspring model parameter from an offspring model parameter file 44, obtains k model evaluated values based on the offspring model parameter received, and stores the k model evaluated values in an evaluated value file 32 in a storage section 17. The fitness function circuit 15 is also provided with an area calculation section 22, which reads the k model evaluated values stored in the evaluated value file 32 by the evaluated value calculation section 21, calculates the size of an area formed by the k model evaluated values read, and stores the size of the area in an area value file 33 in the storage section 17. The fitness function circuit 15 is also provided with a fitness evaluation section 23, which reads the size of the area stored in the area value file 33 by the area calculation section 22, evaluates fitness of the offspring model parameter based on the size of the area read, and stores the fitness in a fitness file 34 in the storage section 17.

Claims

1. A fitness function circuit used for genetic algorithms, the fitness function circuit receiving a model parameter, obtaining a model evaluated value, and outputting fitness for a specific problem, the fitness function circuit comprising:

an evaluated value calculation section, receiving the model parameter, for obtaining the model evaluated value based on the model parameter received, and storing the model evaluated value in a storage section;

an area calculation section for reading the model evaluated value stored in the storage section by the evaluated value calculation section, calculating a size of an area that is formed by the model evaluated value read, and storing the size of the area in the storage section; and

a fitness evaluation section for reading the size of the area stored in the storage section by the area calculation section, evaluating the fitness of the model parameter based on the size of the area read, and storing the fitness in the storage section.

2. The fitness function circuit of claim 1, wherein the area calculation section calculates an area based on a true value and an area based on the model evaluated value, and stores the areas in the storage section, and

wherein the fitness evaluation section evaluates the fitness according to a difference between the area based on the true value and the area based on the model evaluated value.

3. The fitness function circuit of claim 1, wherein the evaluated value calculation section calculates a model evaluated value f(P, x_i) based on a model parameter P and a variable value x_i where P denotes a model parameter that has n components {p₁, p₂, . . . , p_n}, x denotes a variable, x_i denotes a variable value, f denotes a function with variables of the model parameter P and the variable value x_i, and f(P, x_i) denotes the model evaluated value;

wherein the area calculation section calculates, for every i, a first area that is based on the variable value x_i, a variable value x_i+1, a true value I_d(x_i) and a true value I_d(x_i+1) and a second area that is based on the variable value x_i, the variable value x_i+1, the model evaluated value f(P,x_i) and a model evaluated value f(P, x_i+1) where I_d(x_i) denotes the true value of the variable value x_i, g denotes the fitness, and i=1, 2, . . . , k; and

wherein the fitness evaluation section calculates a difference between the first area and the second area and calculates a sum of differences between the areas calculated for the every i as the fitness.

4. The fitness function circuit of claim 1, wherein the area calculation section calculates an area enclosed with a true value and the model evaluated value, and stores the area enclosed with the true value and the model evaluated value in the storage section, and

wherein the fitness evaluation section evaluates the fitness based on the area enclosed with the true value and the model evaluated value.

5. The fitness function circuit of claim 1, wherein the evaluated value calculation section calculates a model evaluated value f(P, x_i) based on a model parameter P and a variable value x_i where P denotes a model parameter that has n components {p₁, p₂, . . . , p_n}, x denotes a variable, x₁ denotes a variable value, f denotes a function with variables of the model parameter P and the variable value x_i, and f(P, x_i) denotes the model evaluated value;

wherein the area calculation section calculates, for every i, a first area that is based on the variable value x_i, a variable value x_i+1, a true value I_d(x_i) and a true value I_d(x_i+1) and a second area that is based on the variable value x_i, the variable value x_i+1, the model evaluated value f(P, x_i) and a model evaluated value f(P,x_i+1) where I_d(x_i) denotes the true value of the variable value x_i, g denotes the fitness, and i=1, 2, . . . , k; and

wherein the fitness evaluation section calculates a difference between the first area and the second area and calculates a sum of absolute values of differences between the areas calculated for the every i as the fitness.

6. A genetic algorithm machine, which executes a genetic algorithm using a model parameter, comprising:

a population memory for storing a population of model parameters having fitness;

a select section for selecting a parent model parameter from among the population of model parameters stored in the population memory;

a crossover module for crossing parent model parameters selected by the select section and producing an offspring model parameter; and

a fitness function circuit for evaluating the fitness for a specific problem of the offspring model parameter obtained from the crossing by the crossover module,

wherein the fitness function circuit includes,

an evaluated value calculation section, receiving the offspring model parameter, for calculating k model evaluated values based on the offspring model parameter received, and storing the k model evaluated values in a storage section;

an area calculation section for reading a model evaluated value stored in the storage section by the evaluated value calculation section, calculating a size of an area formed by the model evaluated value read, and storing the size of the area in the storage section; and

a fitness evaluation section for reading the size of the area stored in the storage section by the area calculation section, evaluating the fitness of the offspring model parameter based on the size of the area read, and storing the fitness in the storage section.

7. A fitness evaluation method used by a fitness function circuit installed in a genetic algorithm machine, comprising:

retrieving a variable value string and an observed data string corresponding to the variable value string from a storage section, calculating a size of an area based on observed data using the variable value string and the observed data string, and storing the size of the area based on the observed data calculated in the storage section;

retrieving the variable value string and a model parameter from the storage section, calculating a model evaluated, value string using the variable value string and the model parameter, calculating a size of an area based on the model parameter using the variable value string and the model evaluated value string, and storing the size of the area based on the model parameter calculated in the storage section; and

retrieving from the storage section the size of the area based on the observed data and the size of the area based on the model parameter, evaluating fitness of the model parameter based on a difference between the sizes, and storing the fitness in the storage section.

8. The fitness evaluation method of claim 7, comprising:

calculating a size of an area formed by a minimum value of the variable value string, a maximum value of the variable value string, the observed data string, and an X-axis, according to a two-dimensional coordinate graph where the X-axis indicates the variable value string and a Y-axis indicates the observed data string, for the size of the area based on the observed data;

calculating a size of an area formed by the minimum value of the variable value string, the maximum value of the variable value string, the model evaluated value string, and an X-axis, according to a two-dimensional coordinate graph where the X-axis indicates the variable value string and a Y-axis indicates the model evaluated value string, for the size of the area based on model parameter; and

storing the sizes in the storage section.

9. A fitness evaluation method used by a fitness function circuit installed in a genetic algorithm machine, comprising:

retrieving a variable value sting and a model parameter from a storage section, and calculating a model evaluated value string based on the variable value sting and the model parameter;

retrieving an observed data string corresponding to the variable value string from the storage section; and

calculating fitness of the model parameter based on an absolute value of a difference between the observed data string and the model evaluated value string, and storing the fitness in the storage section.

10. The fitness evaluation method of claim 9, comprising:

evaluating the fitness by obtaining a value by integrating the absolute value of the difference between the observed data string and the model evaluated value string.