Data processing: artificial intelligence – Machine learning – Genetic algorithm and genetic programming system
Reexamination Certificate
1997-12-12
2001-01-30
Hafiz, Tariq R. (Department: 2762)
Data processing: artificial intelligence
Machine learning
Genetic algorithm and genetic programming system
Reexamination Certificate
active
06182057
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a genetic algorithm executing device and method for efficiently searching for a solution using a genetic algorithm (GA), and a program storage medium thereof.
2. Description of the Related Art
Genetic algorithms are application technologies inspired by mechanisms of inheritance and evolution of living things. In the evolution of living things, genomic changes like crossovers of chromosomes, mutations of genes, etc. may occur when new individuals (children) are born from old ones (parents). An individual which can not adapt to the environment fails to survive after natural selection on the other hand an adaptable one survives and becomes a parent of a new descendant. Such adaptability is determined by their genomic properties.
In a genetic algorithm, a candidate of solution to an optimization problem is represented as a character string (corresponding to a chromosome which is a one-dimensional string of genes), and a solution is searched by repeating genetic operations including selection, crossover, mutation, etc. In this specification, we use the word “character” not only in the sense of alphabets but also in the universal sense of numbers, symbols, . . . , etc.
Here, evolution of living things corresponds to a process in which a value of the objective function (which is the function evaluated to determine the suitability for the optimization problem) of each character string approaches an optimum value. The selection operation is performed by choosing parent strings with a high evaluation value (which is calculated by the objective function), as shown in FIG.
1
A. In a mutation operation, some characters are replaced with other characters at random, as shown in FIG.
1
B. In the crossover operation, substrings of a pair of strings are exchanged, as shown in FIG.
1
C. By repeating these operations, we can obtain new strings that make the objective function more suitable than with the initial ones.
In the conventional genetic algorithm, mutation is performed uniformly in the whole the of string, i.e. over all positions in the string. However in many optimization problems, there are some positions that need not (or have to) be mutated. For such problems, the conventional uniform mutation is not efficient. Accordingly, we can barely obtain a solution by the conventional method, especially for large scale problems.
Furthermore, since a sufficiently large number of generations is required to obtain an adequate string by the conventional genetic algorithm, the search process is continued up to the designated generation, even if a solution has been obtained. The conventional method also has a problem of efficiency of calculation.
SUMMARY OF THE INVENTION
An object of the present invention is to improve the search efficiency of a genetic algorithm by estimating the effect of each position. Another object of the present invention is to save calculation time by automatically terminating the search.
A genetic algorithm executing device according to the present invention is for solving an optimization problem by a genetic algorithm. This device comprises a character-distribution calculating unit for calculating a distribution of characters at each position from a set of strings; a mutation rate calculating unit for calculating a degree of disorder at each position from the distributions of characters, and calculating a mutation rate at each position from the degrees of disorder; and a mutation processing unit for mutation operation according to the mutation rates.
The genetic algorithm executing device according to the present invention may further comprise a character distribution registering unit for registering the distributions of characters. The mutation rate calculating unit may obtain a degree of disorder at each position from the distributions of characters registered in the character distribution registering unit. This device may further comprise a generation number counting unit for counting the number of generations; and a termination condition evaluating unit for evaluating termination condition by using the distributions of characters and/or the number of generations.
Another genetic algorithm executing device according to the present invention comprises a character-distribution calculating unit for calculating a distribution of characters at each position; a character position selecting unit for calculating a degree of disorder at each position from the distributions of characters, and selecting positions with a high degree of disorder; and a combination generating unit for generating new strings by the combinations of characters at the selected positions.
A genetic algorithm executing method according to the present invention is for solving an optimization problem by a genetic algorithm. The method comprises the steps of: calculating a distribution of characters at each position from a set of strings; calculating a degree of disorder at each position from the distributions of characters; calculating a mutation rate at each position from the degrees of disorder; and generating new strings by mutation operation according to the mutation rates.
This method may further comprise the steps of: counting the number of generations; and evaluating termination condition by using the distributions of characters and/or the number of generations. Another genetic algorithm executing method according to the present invention comprises the steps of: calculating a distribution of characters at each position from a set of strings; calculating a degree of disorder at each position from the character distributions; selecting positions with a high degree of disorder; and generating new strings by the combinations of characters at the selected positions. In the step of generating new strings, characters at the selected positions are reset to the best combination.
A computer-readable storage medium according to the present invention stores a computer program for implementing a genetic algorithm executing method for solving an optimization problem by a genetic algorithm. The genetic algorithm executing method implemented by the computer program may comprise the steps of the above described genetic algorithm executing method according to the present invention. If the storage medium is an external storage medium, it is realized by an optical storage medium such as a CDROM, etc., a magnetic storage medium such as a floppy disk, etc., and a magneto-optical storage medium such as an MD, etc. If the storage medium is an internal storage medium, it is realized by a hard disk, a ROM, a RAM, etc.
REFERENCES:
patent: 5148513 (1992-09-01), Koza et al.
patent: 5319781 (1994-06-01), Syswerda
patent: 5793644 (1998-08-01), Koford et al.
patent: 5819244 (1998-10-01), Smith
patent: 5848403 (1998-12-01), Gabriner et al.
patent: 5940533 (1999-08-01), Gentric
patent: 5974355 (1999-10-01), Matsumoto et al.
patent: 5978507 (1999-11-01), Snackleton et al.
Nakata et al., “Image Reconstruction from Projections Using a Genetic Algorithm”, IEEE Nuclear Science Symposium and Medical Imaging Conference, Oct.-No. 1994.
Saito et al., “Shape Modeling of Multiple Objects from Shading Images Using Genetic Algorithms”, IEEE Inter. Conf. on Systems, Man and Cybernetics, Oct. 1996.
Tompkins et al., “Genetic Algorithms in Optimizing Simulated Systems”, IEEE Proceedings of the 1995 Winter Simulation Conference, 1995.
Binglin et al., “A Genetic Algorithm for Diagnosis Problem solving”, IEEE International Conference On Systems, Man and Cybernetics, Oct. 1993.
Haida, “Genetic Algorithms Approch to Voltage Optimization”, IEEE Pproceedings of the 1st Inter—forum on Applications of Neural Networks to Power Systems, Jul. 1991.
Skomorokhov, Alexander, “Genetic Algorithms=APL2 Implementation and a Real Life Application”, Proceedings of the APLm96 Conf. on Designing the Future, Aug. 1996.
Logar et al, “Implementation of Massively Parallel Genetic Algorthms on the Maspar MP-1”, Proceedings of the 1992 ACM/SIGAPP Symposium on Applied Computing (vol.-
Doi Hirofumi
Kikuchi Yasuhiro
Davis George
Fujitsu Limited
Hafiz Tariq R.
Staas & Halsey
LandOfFree
Device, method, and program storage medium for executing... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Device, method, and program storage medium for executing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Device, method, and program storage medium for executing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2545123