Data processing: artificial intelligence – Machine learning – Genetic algorithm and genetic programming system
Reexamination Certificate
1997-01-31
2002-03-26
Davis, George B. (Department: 2122)
Data processing: artificial intelligence
Machine learning
Genetic algorithm and genetic programming system
Reexamination Certificate
active
06363368
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to an optimal solution search method and an optimal solution search apparatus as well as a storage medium in which an optimal solution search program is stored, suitable for use for optimization of a system using genetic algorithms (GAs), and contemplates provision of a technique for allowing genetic algorithms to be executed at a high speed to allow a high speed search for an optimal solution to a problem.
2. Description of the Related Art
In recent years, optimal solution search apparatus which search for an optimal solution to a problem using genetic algorithms have been conceived from a principle of biological evolution (selection (reproduction), mutation or crossover).
An optimal solution search apparatus which employs genetic algorithms, represents candidates for solution to a problem as chromosomes. Each chromosome is an arrangement of genes. The apparatus performs various genetic operations for the chromosomes to search for one of the optimal solutions each of which is obtained as one of the chromosomes having the highest fitness value.
It is to be noted that the fitness value is calculated from a gene arrangement of a chromosome and represents a degree of fitness to a problem. That is, a degree of quality of a solution represented by a chromosome.
An optimal solution search apparatus of the type mentioned above is typically constructed such that, at the end (or start) of a generation, a fitness value of a gene arrangement obtained as a result of the performance of genetic operations is calculated.
The optimal solution search apparatus has a problem in that, when genetic algorithms are executed, for calculation processing of fitness values is time consuming.
Particularly, when fitness values are calculated for gene arrangements obtained as a result of the performance of genetic operations (as in the optimal solution search apparatus described above)) a large amount of time is required for calculation processing of fitness values.
The optimal solution search apparatus has another problem in that, as the number of chromosomes which make an object of processing increases, or as the length of a chromosome which makes an object of processing increases, or as the calculation processing for fitness values becomes complicated, the time required for execution of genetic algorithms increases.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide an optimal solution search method and apparatus wherein genetic algorithms can be executed at a high speed to allow an optimal solution to a problem to be searched for at a high speed.
It is another object of the present invention to provide a storage medium in which an improved optimal solution search program for operating a computer to search for an optimal solution is stored.
In order to attain the objects described above, according to an aspect of the present invention, there is provided an optimal solution search method wherein candidates for solution to a problem are represented as chromosomes, which are arrangements of genes and genetic operations, and are performed for individual chromosomes for each generation to successively update the generation to search for an optimal solution to the problem based on fitness values calculated from gene arrangements of the chromosomes, the optimal solution search method comprising the fitness value updating step of updating, for each of those chromosomes for which a particular genetic operation which allows a fitness value after execution thereof to be calculated readily making use of a fitness value before the execution thereof, and the fitness value based on variation information of the fitness value by execution of the particular genetic operation.
The optimal solution search method according to the present invention is advantageous in that, since the time required for calculation processing of fitness values can be reduced, genetic algorithms can be executed at a high speed and an optimal solution to a problem can be searched at a high speed.
According to another aspect of the present invention, there is provided an optimal solution search method wherein candidates for solution to a problem are represented as chromosomes, which are arrangements of genes and genetic operations, and are performed for individual chromosomes for each generation to successively update the generation to search for an optimal solution to the problem based on fitness values calculated from gene arrangements of the chromosomes, the optimal solution search method comprising the schedule determination step of determining, prior to execution of those genetic operations which remain before the end of a generation, an execution schedule of the genetic operations to be performed for each of the chromosomes, the chromosome discrimination step of referring to the execution schedules determined by the schedule determination step to discriminate, for each of the chromosomes, whether or not the chromosome is a particular chromosome for which only a particular genetic operation which allows a fitness value after execution thereof to be calculated readily making use of a fitness value before the execution thereof, and the fitness value updating step of updating, for each of those chromosomes which have been determined to be the particular chromosomes by the chromosome discrimination step, and the fitness value based on variation information of the fitness value by execution of the particular genetic operation.
In another aspect of the present invention, the fitness value updating step, the fitness values may be updated in synchronism with execution of the particular genetic operation.
In another aspect of the present invention, the fitness value updating step, upon execution of the particular genetic operation, variation information of the fitness value may be calculated by execution of the particular genetic operation.
In another aspect of the present invention, the fitness value updating step, upon execution of the particular genetic operation from among those genetic operations which make an object of determination in the schedule determination step, variation information of the fitness value may be calculated by execution of the particular genetic operation independently of a result of the discrimination in the chromosome discrimination step.
In another aspect of the present invention, in the fitness value updating step, variation information of the fitness value may be calculated by execution of the particular genetic operation after execution of an arbitrary one of those genetic operations which make an object of determination in the schedule determination step.
Upon execution of the particular genetic operation from among those genetic operations executed prior to one of the genetic operations which has been determined as an object of determination in the schedule determination step, variation information of the fitness value by execution of the particular genetic operation may be calculated.
In the schedule determination step, it is only required that the execution schedules be determined before the particular genetic operation appearing last is executed.
In another aspect of the present invention, in the schedule determination step, the execution schedules may be determined before the first genetic operation is executed, or before the particular genetic operation appearing first is executed, or before an arbitrary genetic operation is executed.
In another aspect of the present invention, in the schedule determination step, the execution schedules of genetic operations may be determined for the individual chromosomes, or an execution schedule of genetic operations which is common to all of the chromosomes may be determined.
In another aspect of the present invention, in the chromosome discrimination step, the execution schedules determined by the schedule determination step and also execution conditions of those genetic operations which have been executed prior to a genetic operation determined as an object of determina
Davis George B.
Fujitsu Limited
Staas & Halsey , LLP
LandOfFree
Optimum solution search method and optimum solution search... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Optimum solution search method and optimum solution search..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimum solution search method and optimum solution search... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2878479