System and method for analyzing genertic algorithms

• US 6,633,854 B1
• Filed: 11/05/1999
• Issued: 10/14/2003
• Est. Priority Date: 11/05/1999
• Status: Expired due to Fees

• Current Assignee: Raytheon BBN Technlogies Corp. (Rtx Corporation)
• Original Assignee: Genuity Inc. (Lumen Technologies, Inc.), Verizon Corporate Services Group Incorporated (Verizon Communications Inc.)
• Inventors: Moore, Sean Samuel Butler
• Primary Examiner(s): Voeltz, Emanuel Todd
• Assistant Examiner(s): Hirl, Joseph P.
• Application Number:
  US09/434,642
• Time in Patent Office: 1,439 Days
• Field of Search: 706/13, 706/14, 706/45
• US Class Current: 706/13
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

Systems and methods consistent with the present invention analyze control parameters of evolutionary algorithms. To this end, the system determines the value of a control parameter that controls the operation of the evolutionary algorithm. The system then executes the evolutionary algorithm according to the determined value of the control parameter to obtain a response value. Finally, the system determines an effect vector describing how a change in the value of the control parameter affects the response value. Systems and methods consistent with the present invention may also predict how changing the levels of a control parameter will affect the response value of the evolutionary algorithm. The system may also normalize an objective function of the evolutionary algorithm such that control parameters of the objective function have a relatively equal effect on the overall objective function.

Claims

1. A computer implemented method for analyzing an evolutionary algorithm using a response vector α

and an effect vector μ

, the method comprising the steps, performed by a processor, of;

determining a plurality of control parameters that control the operation of the evolutionary algorithm;

executing the evolutionary algorithm according to a set of the determined control parameters, with each control parameter having a value selected from a range of values for each control parameter, to obtain a corresponding response vector α

with response values; and

determining the effect vector μ

, having coefficients μ

_i, from the response vector α

, with each coefficient μ

_i representing a respective effect on the response value due to at least one change in the value of at least one of the plurality of control parameters.

2. The method of claim 1, wherein at least one of the control parameters may be set to one of a plurality of values, and wherein the executing step further includes the substep of:

executing the evolutionary algorithm when the at least one control parameter is set to each of the plurality of values, thereby obtaining a plurality of corresponding response values.

3. The method of claim 1, wherein the executing step further includes the substep of:

executing the evolutionary algorithm to obtain an average response of the evolutionary algorithm when the plurality of control parameters are set to a respective determined value.

4. The method of claim 1, wherein the step of determining the effect vector further includes the substep of:

determining an average effect value describing an average response value of the evolutionary algorithm when the control parameters are set to respective random values.

5. The method of claim 1, wherein the step of determining the effect vector further includes the substep of:

determining a primary effect value describing the effect of a particular control parameter on the response value of the evolutionary algorithm, independent of any other control parameter.

6. The method of claim 1, wherein the step of determining the effect vector further includes the substep of:

determining an interactive effect value describing how the effect of one control parameter on the response value of the evolutionary algorithm depends upon the value of another control parameter.

7. The method of claim 1, wherein the step of determining the effect vector further includes the step of determining the effect vector using analysis of variance techniques.

8. The method of claim 1, further including the step of:

displaying the effect vector to a user to provide an indication of the effect of the control parameters on the response value of the evolutionary algorithm.

9. The method of claim 1, further including the step of:

predicting a new response value of the evolutionary algorithm due to setting at least one control parameter to a new value.

10. The method of claim 9, wherein the predicting step further includes the substep of:

determining a modified effect vector describing an effect on the response value due to the new value of the at least one control parameter.

11. The method of claim 1, wherein the executing step further includes the substep of:

determining an objective function that provides a quality measure of the response value of the evolutionary algorithm.

12. The method of claim 11, wherein the objective function includes a plurality of subjective functions biased by a respective weight control parameter, the method further including the step of:

normalizing the objective function such that a change in a first weight control parameter has substantially the same effect on the objective function as a corresponding change to a second weight control parameter.

13. The method of claim 12, wherein the normalizing step further includes the substep of:

determining a dynamic range of the effect vector.

14. A computer for analyzing an evolutionary algorithm using a response vector α

and an effect vector μ

, the computer comprising;

a memory having program instructions; and

a processor, responsive to the programming instructions, configured to;

determine a plurality of control parameters that control the operation of the evolutionary algorithm;

execute the evolutionary algorithm according to a set of the determined control parameters, with each control parameter having a value selected from a range of values for each control parameter, to obtain a corresponding response vector α

with response values; and

determine the effect vector μ

, having coefficients μ

_i, from the response vector α

, with each coefficient μ

_i representing a respective effect on the response value due to at least one change in the value of at least one of the plurality of control parameters.

15. The computer of claim 14, wherein at least one of the control parameters may be set to one of a plurality of values, and wherein the processor is further configured to:

execute the evolutionary algorithm when the at least one control parameter is set to each of the plurality of values, thereby obtaining a plurality of corresponding response values.

16. The computer of claim 14, wherein the processor is further configured to:

execute the evolutionary algorithm to obtain an average response of the evolutionary algorithm when the plurality of control parameters are set to a respective determined value.

17. The computer of claim 14, wherein the processor is further configured to:

determine an average effect value describing an average response value of the evolutionary algorithm when the control parameters are set to respective random values.

18. The computer of claim 14, wherein the processor is further configured to:

determine a primary effect value describing the effect of a particular control parameter on the response value of the evolutionary algorithm, independent of any other control parameter.

19. The computer of claim 14, wherein the processor is further configured to:

determine an interactive effect value describing how the effect of one control parameter on the response value of the evolutionary algorithm depends upon the value of another control parameter.

20. The computer of claim 14, wherein the processor is further configured to determine the effect vector using analysis of variance techniques.

21. The computer of claim 14, wherein the processor is further configured to:

display the effect vector to a user to provide an indication of the effect of the control parameters on the response value of the evolutionary algorithm.

22. The computer of claim 14, wherein the processor is further configured to:

predict a new response value of the evolutionary algorithm due to setting at least one control parameter to a new value.

23. The computer of claim 22, wherein the processor is further configured to:

determine a modified effect vector describing an effect on the response value due to the new value of the at least one control parameter.

24. The computer of claim 14, wherein the processor is further configured to:

determine an objective function that provides a quality measure of the response value of the evolutionary algorithm.

25. The computer of claim 24, wherein the objective function includes a plurality of subjective functions biased by a respective weight control parameter, and wherein the processor is further configured to:

normalize the objective function such that a change in a first weight control parameter has substantially the same effect on the objective function as a corresponding change to a second weight control parameter.

26. The computer of claim 25, wherein the processor is further configured to:

determine a dynamic range of the effect vector.

27. An apparatus for evaluating an evolutionary algorithm using a response vector α

and an effect vector μ

, the apparatus comprising;

means for determining a plurality of control parameters that control the operation of the evolutionary algorithm;

means for executing the evolutionary algorithm according to a set of the determined control parameters, with each control parameter having a value selected from a range of values for each control parameter, to obtain a corresponding response vector α

with response values; and

means for determining the effect vector μ

, having coefficients μ

_i, from the response vector α

, with each coefficient μ

_i representing a respective effect on the response value due to at least one change in the value of at least one of the plurality of control parameters.

28. The apparatus of claim 27, wherein at least one of the control parameters may be set to one of a plurality of values, and wherein the means for executing further includes:

means for executing the evolutionary algorithm when the at least one control parameter is set to each of the plurality of values, thereby obtaining a plurality of corresponding response values.

29. The apparatus of claim 27, wherein the means for executing further includes:

means for executing the evolutionary algorithm to obtain an average response of the evolutionary algorithm when the plurality of control parameters are set to a respective determined value.

30. The apparatus of claim 27, wherein the means for determining the effect vector further includes:

means for determining an average effect value describing an average response value of the evolutionary algorithm when the control parameters are set to respective random values.

31. The apparatus of claim 27, wherein the means for determining the effect vector further includes:

means for determining a primary effect value describing the effect of a particular control parameter on the response value of the evolutionary algorithm, independent of any other control parameter.

32. The apparatus of claim 27, wherein the means for determining the effect vector further includes:

means for determining an interactive effect value describing how the effect of one control parameter on the response value of the evolutionary algorithm depends upon the value of another control parameter.

33. The apparatus of claim 27, wherein the means for determining the effect vector further includes:

means for determining the effect vector using analysis of variance techniques.

34. The apparatus of claim 27, further including:

means for displaying the effect vector to a user to provide an indication of the effect of the control parameters on the response value of the evolutionary algorithm.

35. The apparatus of claim 27, further including:

means for predicting a new response value of the evolutionary algorithm due to setting at least one control parameter to a new value.

36. The apparatus of claim 35, wherein the means for predicting further includes:

means for determining a modified effect vector describing an effect on the response value due to the new value of the at least one control parameter.

37. The apparatus of claim 27, wherein the means for executing further includes:

means for determining an objective function that provides a quality measure of the response value of the evolutionary algorithm.

38. The apparatus of claim 37, wherein the objective function includes a plurality of subjective functions biased by a respective weight control parameter, the apparatus further including:

means for normalizing the objective function such that a change in a first weight control parameter has substantially the same effect on the objective function as a corresponding change to a second weight control parameter.

39. The apparatus of claim 38, wherein the normalizing means further includes:

means for determining a dynamic range of the effect vector.

40. A computer-readable medium containing instructions for controlling a data processing system to perform a method for analyzing an evolutionary algorithm using a response vector α

and an effect vector μ

, the method comprising the steps of;

determining a plurality of control parameters that control the operation of the evolutionary algorithm;

executing the evolutionary algorithm according to a set of the determined control parameters, with each control parameter having a value selected from a range of values for each control parameter, to obtain a corresponding response vector α

with response values; and

determining the effect vector μ

, having coefficients μ

_i, from the response vector α

, with each coefficient μ

_i representing a respective effect on the response value due to at least one change in the value of at least one of the plurality of control parameters.