Data processing: artificial intelligence – Machine learning
Reexamination Certificate
1998-09-29
2001-07-17
Powell, Mark R. (Department: 2122)
Data processing: artificial intelligence
Machine learning
C706S013000, C706S025000
Reexamination Certificate
active
06263325
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a technique for obtaining an optimum solution or promising solutions to a problem according to a learning algorithm such as an evolutionary algorithm (EA), etc.
2. Description of the Related Art
Currently, the evolutionary algorithm, which is one of the learning algorithms, is applied to a variety of fields such as an LSI arrangement, image processing, scheduling, database classification, etc.
The evolutionary algorithm is a general term for problem-solving algorithms which use the evolution of living things as a model. The mechanism of a typical evolutionary algorithm is that a candidate of a solution to a given problem is recognized as an individual, and the whole of a population composed of individuals is evolved with the steps such as selection, crossover, etc., that is, the population is made to approach an optimum solution (or a semi-optimum solution or a feasible solution).
For example, a genetic algorithm (GA), which is most typical of the evolutionary algorithm, converts a group of solution candidates to a given problem into character strings each of which is recognized as a chromosome, defines a fitness function as a degree of suitability to a solution (that is, a chromosome), and performs the operations for changing a character string, which are recognized as the genetic operations such as selection according to the fitness, crossover, mutation, etc. A series of these genetic operations is regarded as a single generation and several generations are made to elapse so that an entire chromosome population approaches a better solution. A number of chromosomes with higher degrees of fitness emerge from the chromosome population by repeating the series of genetic operation steps for many generations. Consequently, an optimum solution or a semi-optimum solution can be obtained. “Genetic Algorithm” edited by Hiroaki KITANO (Sangyo Tosho ISBN 4-7828-5136-7) and “Genetic Algorithms in Search, Optimization and Machine Learning” edited by David E. Goldberg (Addison-Wesley Pub Co.; ISBN 0-201-15767-5) refer to the evolutionary algorithm and the genetic algorithm in detail.
The evolutionary algorithm can be applied to many types of problems. This algorithm has a characteristic that an optimum solution, a semi-optimum solution, or a feasible solution can be obtained to a large-scale and complicated problem, which is difficult to be solved with conventional methods.
In the evolutionary algorithm, there is a group of parameters (execution conditions) to be set for each given problem when the algorithm is executed, in order to improve its performance. By way of example, there are parameters such as a chromosome representation method, a fitness function, a selection method, a crossover method, a mutation method, etc. in a standard genetic algorithm.
A combination of execution conditions for obtaining the highest performance depends on the type, the scale, etc. of a problem, and its coordination is normally made according to a user's experience and the repetition of algorithm execution. It is said to be desirable that the behavior of the genetic algorithm is grasped in order to coordinate the execution conditions of the evolutionary algorithm and to improve its performance. However, it is not easy to handle the representations of a spatial distribution and a charge with time, namely, the evolution of a population, which is the characteristic of the evolutionary algorithm.
Conventionally, visualization was frequently used as a method for representing the behavior (and the performance) of an evolutionary algorithm. For example, the solution representation of each individual or the degree of suitability (the degree of fitness) of a solution in the evolutionary algorithm is plotted in a solution space or on a time axis by visualizing the behavior of the evolutionary algorithm, so that the behavior can be intuitively represented and displayed even if the execution of the evolutionary algorithm requires a relatively large-scale problem area, a large population, or a large amount of time.
A variety of methods for visualizing the evolutionary algorithm have been developed up to now. For example, the Japanese Laid-Open Patent Gazette No. 9-305565 “Genetic Algorithm Analysis and Display Processing Device” reciting the invention filed by the present applicant discloses the technique intended not only to implement a display visualized by various methods for the genetic algorithm, but to integrate the input and storage of execution conditions and the execution of a genetic algorithm, so that a user can efficiently coordinate the execution conditions and the performance is improved.
However, if the scale of a problem or of the evolutionary algorithm itself (the size of a population, the number of generations, etc.) is significantly large, a computer having the capability for performing high-speed arithmetic operations, and a sufficient disk capacity for storing the detailed record of the evolution of the evolutionary algorithm depending on need, is required. However, such a computer does not always comprise a desired graphics capability for visualizing the behavior of the evolutionary algorithm in a current situation. Therefore, it may sometimes be difficult to process both the execution and the visualized display of the evolutionary algorithm by using a single computer.
Additionally, with the conventional techniques, the visualized display capability does not greatly contribute to the improvement of the performance of the evolutionary algorithm. For example, the conventional techniques do not implement the capability for immediately changing an execution condition while viewing a visualized display, although the progress state of the execution of the evolutionary algorithm is visualized and displayed.
SUMMARY OF THE INVENTION
The present invention aims at overcoming the above described problems, and at providing a technique with which a user can be positively involved in the execution of a learning algorithm such as an evolutionary algorithm, and the performance of the learning algorithm is efficiently and dynamically improved.
The learning algorithm targeted by the present invention is an algorithm intended for machine learning, and includes an immune algorithm, a learning algorithm and a problem-solving algorithm implemented with a neural network or a fuzzy system, etc., in addition to the evolutionary algorithm such as a genetic algorithm, etc.
A system according to the present invention comprises a change processing unit for setting a change of the execution process of the learning algorithm during its execution, and an executing unit for continuing the execution of the learning algorithm according to the change of the execution process. The change processing unit may be a portion for setting a new execution condition of the learning algorithm during the execution of the learning algorithm. In this case, the executing unit may continue the execution of the learning algorithm under the new execution condition. Additionally, the change processing unit may set a new step progress controlling method of the learning algorithm during the execution of the learning algorithm. In this case, the executing unit may continue the execution of the evolutionary algorithm with the new step progress controlling method.
Here, the step of the evolutionary algorithm mean, for example, one generation or several generations of the genetic algorithm. However, the step may be a single genetic operation such as crossover, mutation, etc. in one generation. The step progress controlling method of the evolutionary algorithm is intended to, for example, automatically advance the evolutionary algorithm, suspend the algorithm at an arbitrary step, or suspend at every step or at every predetermined step.
Additionally, the system according to the present invention may further comprise a displaying unit for visualizing and displaying the progress state of the execution of a learning algorithm by using an object. In this case, the change
Adachi Nobue
Yoshida Yukiko
Fujitsu Limited
Khatri Anil
Powell Mark R.
Staas & Halsey , LLP
LandOfFree
System, method, and program storage medium for executing a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System, method, and program storage medium for executing a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System, method, and program storage medium for executing a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2540948