Data processing: artificial intelligence – Machine learning – Genetic algorithm and genetic programming system
Reexamination Certificate
1999-11-05
2003-10-14
Voeltz, Emanuel Todd (Department: 2121)
Data processing: artificial intelligence
Machine learning
Genetic algorithm and genetic programming system
C706S045000, C706S014000
Reexamination Certificate
active
06633854
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to methods and systems for analyzing genetic algorithms and, more particularly, to methods and systems for analyzing control parameters of genetic algorithms and for analyzing the genetic algorithm's parent class of evolutionary algorithms.
2. Description of the Related Art
Evolutionary algorithms (EAs), including genetic algorithms, have been used to determine optimal solutions to complex problems. U.S. Pat. No. 5,848,403, for example, describes the use of EAs to generate resource schedules for performing various tasks. To solve such problems, EAs start by generating an initial set of solutions to the problem. The EA then cyclically evaluates the quality of each solution using an objective function, selects those solutions having a relatively higher quality level, and alters the selected solutions. In this way, the EA eventually converges to an optimal solution after a number of iterations.
Several types of control parameters affect the speed, quality, and solution characteristics of such an EA system. While not an exhaustive list, these control parameters include: (1) the number of evaluations used to converge to the final result; (2) the population size of the initial set of solutions; and (3) the weighting factors of an objective function used to test the quality of each solution. Each of these control parameters will be described below.
The EA performs a number of evaluations to converge to the final recognition result. Typically, a programmer predefines the number of evaluations that the EA system will perform. Roughly speaking, the greater the number of evaluations, the higher the quality (as measured by the objective function) of the final result. However, the processing resource requirements increase along with the number of evaluations performed by the EA system. Thus, the programmer should select a number of evaluations that strikes the proper balance between processing resources and quality of the EA system's results.
The population size of the initial number of solutions also affects the speed and quality of the EA system. In particular, a larger population size provides better initial coverage of the solution space to the problem at hand. Thus, the EA may be more likely to find higher quality solutions when converging to the final result. On the other hand, a smaller initial population size may provide enough quality, while allowing the EA system to converge at a faster rate. Thus, the programmer should also carefully choose the number of initial solutions when balancing speed and quality constraints.
As known in the art, the EA system uses an objective function to measure interesting properties of each solution during the convergence process. The objective function may be any function that returns a numerical value. This value measures the quality of each potential solution. Based on the value of the objective function, the typical EA system selects the higher quality solutions, alters the selected solutions, and then repeats the entire cycle. In this way, the EA system converges to an optimal final result.
For illustrative purposes, an objective function is described that consists of a linear combination of several weighted subfunctions. Typically, each subfunction measures the quality of a possible solution in terms of a single property or characteristic of the problem at hand. For the scheduling problem described in U.S. Pat. No. 5,848,403, for example, the properties may be the distance between tasks, the time to achieve each task, labor costs, or customer satisfaction. The equation below describes an exemplary objective function:
F
(
x
)=
w
0
f
0
(
x
)+
w
1
f
1
(
x
) . . . +
w
N−1
f
N−1
(
x
)
where:
x represents a possible solution to the problem;
f
i
(x) represents a subfunction for measuring the i
th
property of the problem; and
w
i
represents a bias weight for subfunction f
i
(x), such that 0≦w
i
≦1.
Thus, a user can bias the EA to produce solutions that emphasize certain properties by changing the relative values of the bias weights applied to each subfunction. In this way, a programmer can choose to emphasize the relative importance of an individual subfunction when evaluating the quality of each possible solution. These bias weights may be viewed as input parameters, or control parameters, to the EA system.
Currently, programmers have no general purpose, analytical or empirical method to predict how varying the values of any of the above control parameters will affect the final result of the EA system. Each parameter may affect the final result to a different degree. Also, the effect of varying a particular parameter differs between different applications of an EA. Additionally, parameters may interact, such that the effect of varying one parameter may depend upon the current value of other parameters. Thus, a programmer must often resort to a trial-and-error approach to “tune” the parameters. Such an ad hoc approach, however, is inefficient, difficult to analyze, and difficult to reproduce.
Thus, it is desired to have a standardized system and method for analyzing EAs. In particular, it is desirable to have a system and method that can analyze how changing a control parameter value affects the response of an EA.
SUMMARY OF THE INVENTION
Systems and methods consistent with the present invention analyze control parameters of an evolutionary algorithm to thereby allow a programmer to understand the effects of changing control parameter values and to efficiently select new values for the control parameters.
In accordance with the purposes of the invention as embodied and broadly described herein, a system and method consistent with the present invention evaluates evolutionary algorithms. The system determines the value of a control parameter that controls the operation of the evolutionary algorithm. The system also executes the evolutionary algorithm according to the determined value of the control parameter to obtain a response value, and determines an effect vector describing how a change in the value of the control parameter affects the response value.
Both the foregoing general description and the following detailed description are exemplary and are intended to provide further explanation of the invention as claimed.
REFERENCES:
patent: 4935877 (1990-06-01), Koza
patent: 5319781 (1994-06-01), Sywerda
patent: 5848403 (1998-12-01), Gabriner et al.
patent: 5946673 (1999-08-01), Francone et al.
S. C. Ng et al; The Genetic search Approach; 1996; IEEE; 1053-5888/96; 38-46.*
Trevor D. Collins et al; Understanding Evolutionary Computing: A Hands on Approach; 1998; IEEE; 0-7803-4869-9/98; 564-569.*
D.C. Montgomery, Design and Analysis of Experiments, Chapters 3, 7 and 9 (3rded., 1991).
Genuity Inc.
Hirl Joseph P.
Suchyta Leonard Charles
Todd Voeltz Emanuel
Weixel James K.
LandOfFree
System and method for analyzing genertic algorithms 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 and method for analyzing genertic algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for analyzing genertic algorithms will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3131413