Method and apparatus for adaptively solving sequential problems in a target system utilizing evolutionary computation techniques

• US 6,088,690 A
• Filed: 06/27/1997
• Issued: 07/11/2000
• Est. Priority Date: 06/27/1997
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Gounares, Alexander G., Spady, Stephen W.
• Primary Examiner(s): Hafiz, Tariq R.
• Assistant Examiner(s): Pender, Jr., Michael J
• Application Number:
  US08/883,680
• Time in Patent Office: 1,110 Days
• Field of Search: 706/13
• US Class Current: 706/13
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

A system for adaptively solving sequential problems in a target system utilizing evolutionary computation techniques and in particular genetic algorithms and modified genetic algorithms. Stimuli to a target system such as a software system are represented as actions. A single sequence of actions is a chromosome. Chromosomes are applied to the target system one action at a time and the change in properties of the target system is measured after each action is applied. A fitness rating is calculated for each chromosome based on the property changes produced in the target system by the chromosome. The fitness rating calculation is defined so that successive generations of chromosomes will converge upon desired characteristics. For example, desired characteristics for a software testing application are defect discovery and code coverage. Chromosomes with high fitness ratings are selected as parent chromosomes and various techniques are used to mate the parent chromosomes to produce children chromosomes. Children chromosomes with high fitness ratings are entered into the chromosome population. Defects in a target software system are minimized by evolving ever-shorter chromosomes that produce the same defect. Defect discovery rate, or any other desired characteristic, is thereby maximized.

Claims

1. A method for adaptively solving a sequential problem in a target system comprising the steps of:

producing a population of chromosomes of varied length where each chromosome is formed of a plurality of actions each of said actions representing a stimulus applicable to said target system;

applying said population of chromosomes to said target system;

measuring characteristics of said target system, responsive to application of each of said chromosomes, and said characteristics being definitive of a state of said target systems;

determining, responsive to measurement of said characteristics, a fitness rating for each of said chromosomes comprising said population of chromosomes;

removing said chromosomes having the lowest fitness rating to a noisy archive; and

evolving said population of chromosomes to produce a child chromosome wherein said child chromosome is a solution to said sequential problem.

2. The method of claim 1 wherein said producing step includes:

assigning an action designation to individual stimuli receivable by said target system; and

randomly combining a plurality of said actions to form a chromosome.

3. The method of claim 1 wherein said applying step includes:

exercising said target system with ones of said chromosomes one at a time until said target system has been exercised with all of said population of chromosomes.

4. The method of claim 3 wherein said exercising step includes:

inputting a sequence of actions constituting one of said chromosomes one at a time to said target system until all of said actions constituting said chromosome have been input to said target system.

5. The method of claim 1 where said measuring step further includes:

measuring defects of said target system wherein ones of said actions or ones of said chromosomes cause said defects in said target system.

6. The method of claim 1 wherein said determining step includes:

calculating said fitness rating for each of said chromosomes wherein each of said fitness ratings is a function of said property changes attributable to one of said chromosomes and a length of said one of said chromosomes.

7. The method of claim 1 wherein said determining step includes:

calculating said fitness rating for each of said chromosomes wherein each of said fitness ratings is a function of said property changes attributable to one of said chromosomes, a length of said one of said chromosomes and any defects attributable to said one of said chromosomes.

8. The method of claim 7 wherein said determining step includes:

measuring properties of said target system to determine property changes brought about by application of each action comprising each child chromosome;

measuring defects of said target system wherein ones of said actions or ones of said child chromosomes cause said defects in said target system; and

calculating said fitness rating for each of said chromosomes wherein each of said fitness ratings is a function of said property changes attributable to one of said child chromosomes, a length of said one child chromosome and any defects attributable to said one child chromosomes.

9. The method of claim 1 wherein said evolving step includes:

selecting a parent chromosome from said chromosome population;

mutating said parent chromosome to form a child chromosome wherein said child chromosome differs from said parent chromosome;

determining fitness of said child chromosome; and

inserting child chromosome into said chromosome population.

10. The method of claim 9 wherein said mutating step includes:

mating said parent chromosomes to produce children chromosomes.

11. The method of claim 10 wherein said mating step includes:

choosing a first range of actions from said actions comprising a first one of said parent chromosomes;

choosing a second range of actions from said actions comprising a second one of said parent chromosomes; and

swapping said first range of actions with said second range of actions to produce two children chromosomes said children chromosomes differing from said parent chromosomes.

12. The method of claim 10 wherein said mating step includes:

choosing first and second ranges of actions from a first one of said parent chromosomes where said second range of actions is adjacent to and sequentially after said first range of actions;

choosing third and fourth ranges of actions from a second one of said parent chromosomes where said third range of actions matches said first range of actions and is adjacent to and sequentially after said third range of actions; and

swapping said second range of actions with said fourth range of actions to produce two children chromosomes said children chromosomes differing from said parent chromosomes.

13. The method of claim 10 wherein said mating step includes:

choosing first and second ranges of actions from a first one of said parent chromosomes where said second range of actions is adjacent to and sequentially after said first range of actions;

choosing third and fourth sequentially adjacent ranges of actions from a second one of said parent chromosomes where said third range of actions includes an action matching an action in said first range of actions and said fourth range of actions includes an action matching an action in said second range of actions; and

swapping said second range of actions with said fourth range of actions to produce two children chromosomes said children chromosomes differing from said parent chromosomes.

14. The method of claim 13 wherein said step of choosing third and fourth ranges of actions includes:

choosing said third range of actions wherein said third range of actions includes multiple actions having a first type and a first sequence wherein said first type and said first sequence match actions included in said first range of actions; and

choosing said fourth range of actions adjacent to and sequentially after said third range of actions wherein said fourth range of actions includes multiple actions having a second type and a second sequence wherein said second type and said second sequence match actions included in said second range of actions.

15. The method of claim 10 wherein said mating step includes:

computing an action state delta sum total for each one of multiple segments of a first one of said parent chromosomes;

computing an action state delta sum total for each one of a first set of multiple segments of a second one of said parent chromosomes;

computing an action state delta sum total for each one of a second set of multiple segments of a second one of said parent chromosomes;

comparing said action state delta sum total for said first and second set of segments to said action state delta sum totals for said multiple segments of said first parent chromosome;

selecting, responsive to said comparing step, said first or second set of segments; and

swapping said selected segment with a one of said multiple segments of said first one of said parent chromosomes.

16. The method of claim 10 wherein said mating step further includes:

applying mutagens to said children chromosomes to further alter said children chromosomes.

17. The method of claim 16 wherein applying mutagens step includes:

selecting a sequence of actions in one of said child chromosomes; and

replacing said selected sequence with an inverse of said selected sequence.

18. The method of claim 16 wherein applying mutagens step includes:

selecting a sequence of actions at a first location within one of said child chromosomes;

cutting said sequence of actions from said one child chromosome; and

inserting said sequence of actions in said one child chromosome at a second location.

19. The method of claim 16 wherein applying mutagens step includes:

selecting a first sequence of actions in one of said child chromosomes;

determining an action state delta sum for said selected sequence;

choosing a second sequence of actions from said chromosome population wherein said second sequence of actions the same said action state delta sum as said first sequence of actions; and

replacing said first sequence with said second sequence.

20. The method of claim 9 wherein said inserting step includes:

removing child chromosomes having the lowest said fitness ratings to a noisy archive; and

inserting remaining child chromosomes in said chromosome population.

21. The method of claim 1 further including the step of evolving the population of said noisy archive to produce a child chromosome wherein said child chromosome is a solution to said sequential problem.

22. The method of claim 1 wherein said evolving step includes:

selecting a first parent chromosome from said chromosome population;

selecting a second parent chromosome from said noisy archive;

mating said parent chromosomes to produce children chromosomes; and

inserting said children chromosomes into said chromosome population.

23. A method for locating defects in a target software system, comprising the steps of:

producing a population of chromosomes of varied length where each chromosome is formed of a plurality of actions each of said actions being a stimulus applicable to said target software system;

applying said population of chromosomes one at a time to said target software system;

measuring characteristics of said target software system, responsive to application of each of said chromosomes, said characteristics being definitive of a state of said target software system produced by each of said chromosomes;

identifying, responsive to measurement of said characteristics, a defect-producing chromosome wherein said defect-producing chromosome produces a defect in said target software system, said defect being one of said characteristics; and

minimizing said defect-producing chromosome wherein said minimized defect-producing chromosome has fewer ones of said actions than said defect-producing chromosome and produces the same said defect in said target software system as said defect-producing chromosome.

24. The method of claim 23 wherein said producing step includes:

assigning an action designation to individual stimuli receivable by said target software system; and

randomly combining a plurality of said actions to form each of said chromosomes.

25. The method of claim 23 wherein said applying step includes:

exercising said target software system with ones of said chromosomes one at a time until said target system has been exercised with all of said population of chromosomes.

26. The method of claim 25 wherein said exercising step includes:

inputting a sequence of actions constituting one of said chromosomes one at a time to said target software system until all of said actions constituting said chromosomes have been input to said target software system.

27. The method of claim 23 wherein said measuring step includes:

measuring properties of said target software system to determine property changes brought about by application of each action comprising each chromosome.

28. The method of claim 27 wherein said step of measuring properties includes:

calculating a fitness rating for each of said chromosomes wherein each of said fitness ratings is a function of said property changes attributable to one of said chromosomes.

29. The method of claim 28 wherein said step of calculating a fitness rating includes:

adding to said fitness rating for a one of said chromosomes if said one of said chromosomes brings about a large delta in said property changes when applied to said target software system;

adding to said fitness rating for a one of said chromosomes if said one of said chromosomes brings about a defect in said target software system; and

adding to said fitness rating for a one of said chromosomes if said one of said chromosomes comprises a fewer number of said actions than another of said chromosomes producing the same said property changes and same said defect.

30. The method of claim 23 wherein said minimizing step includes:

mutating said defect-producing chromosome to form a child chromosome wherein said child chromosome comprises fewer of said actions than is comprised by said defect-producing chromosome;

applying said child chromosome to said target software system; and

determining, responsive to said step of applying said child chromosome, if said child chromosome produces the same said defect as said defect-producing chromosome.

31. The method of claim 30 wherein said determining step includes:

measuring properties of said target software system to determine property changes brought about by application of each action comprising said child chromosome;

calculating a fitness rating for said child chromosome;

identifying, responsive to calculation of said fitness rating, whether said child chromosome produces said defect.

32. The method of claim 30 wherein said mutating step includes:

mating said defect-producing chromosome with a second chromosome from said population to produce children chromosomes.

33. The method of claim 32 wherein said mating step further includes:

applying mutagens to said defect-producing chromosome to alter said defect-producing chromosome.

34. The method of claim 23 further comprising the steps of:

applying extinction, responsive to said minimizing step, to said chromosome population.

35. The method of claim 34 wherein said step of applying extinction includes:

determining when said defect-producing chromosome has been minimized to an acceptable number of actions; and

removing, responsive to determining that said defect-producing chromosome has been minimized, any chromosomes from said chromosome population that produce the same said defect produced by said defect-producing chromosome.

36. The method of claim 35 further including the step of:

adjusting a fitness rating means to generate a low fitness rating for any chromosome producing said defect produced by said defect-producing chromosome.

37. The method of claim 35 further including the step of:

adjusting a fitness rating means to generate a low fitness rating for any chromosome producing said defect produced by said defect-producing chromosome.

38. The method of claim 34 wherein said step of applying extinction includes:

determining when said defect-producing chromosome has been minimized to an acceptable number of actions;

destroying said chromosome population; and

creating a new chromosome population.

39. A system for adaptively testing multiple interacting target software systems comprising:

at least one genetic testing engine for generating test cases said genetic testing engine operable to evolve said test cases to produce test cases having a high fitness rating;

a product driver manager for receiving test cases from said genetic testing engine and for selectively communicating said test cases to said target software systems;

multiple product drivers, each of said multiple product drivers being associated with a different one of said target software systems for interfacing between said product driver manager and said associated target software system for applying said test cases to said associated target software system and for measuring properties of said associated target software system.

40. A method for adaptively solving a sequential problem in a target system comprising the steps of:

producing a population of chromosomes where each chromosome is formed of a plurality of actions each of said actions representing a stimulus application to said target system;

applying said population of chromosomes to said target system;

measuring characteristics of said target system, responsive to application of each of said chromosomes, said characteristics being definitive of a state of said target system;

determining, responsive to measurement of said characteristics, a fitness rating for each of said chromosomes comprising said population of chromosomes;

selecting a pair of parent chromosomes from said chromosome population;

computing an action state delta sum total for each one of multiple segments of a first one of said parent chromosomes;

computing an action state delta sum total for each one of a first set of multiple segments of a second one of said parent chromosomes;

comparing said action state delta sum total for said first and second set of segments to said action state delta sum totals for said multiple segments of said first parent chromosome;

selecting, responsive to said comparing step, said first or second set of segments;

swapping said selected segment with a one of said multiple segments of said first one of said parent chromosomes to produce child chromosomes wherein said children chromosomes differ from said parent chromosomes; and

said inserting children chromosomes in said chromosome population.

41. A method for adaptively solving a sequential problem in a target system comprising the steps of:

producing a population of chromosomes where each chromosome is formed of a plurality of actions each of said actions representing a stimulus application to said target system;

applying said population of chromosomes to said target system;

measuring characteristics of said target system, responsive to application of each of said chromosomes, said characteristics being definitive of a state of said target system;

determining, responsive to measurement of said characteristics, a fitness rating for each of said chromosomes comprising said population of chromosomes;

selecting a parent chromosome from said chromosome population;

mutating said parent chromosome to form a child chromosome wherein said child chromosome differs from said parent chromosome;

selecting a sequence of actions in said child chromosome;

replacing said selected sequence with an inverse of said selected sequence; and

inserting said child chromosome in said chromosome population.

42. A method for adaptively solving a sequential problem in a target system comprising the steps of:

producing a population of chromosomes where each chromosome is formed of a plurality of actions each of said actions representing a stimulus application to said target system;

applying said population of chromosomes to said target system;

measuring characteristics of said target system, responsive to application of each of said chromosomes, said characteristics being definitive of a state of said target system;

determining, responsive to measurement of said characteristics, a fitness rating for each of said chromosomes comprising said population of chromosomes;

selecting a parent chromosome from said chromosome population;

mutating said parent chromosome to form a child chromosome wherein said child chromosome differs from said parent chromosome;

selecting a sequence of actions at a first location within said child chromosome;

cutting said sequence of actions from said child chromosome;

inserting said sequence of actions in said child chromosome at a second location; and

inserting said child chromosome in said chromosome population.

43. A method for adaptively solving a sequential problem in a target system comprising the steps of:

producing a population of chromosomes where each chromosome is formed of a plurality of actions each of said actions representing a stimulus application to said target system;

applying said population of chromosomes to said target system;

measuring characteristics of said target system, responsive to application of each of said chromosomes, said characteristics being definitive of a state of said target system;

determining, responsive to measurement of said characteristics, a fitness rating for each of said chromosomes comprising said population of chromosomes;

selecting a parent chromosome from said chromosome population;

mutating said parent chromosome to form a child chromosome wherein said child chromosome differs from said parent chromosome;

selecting a first sequence of actions in said child chromosome;

determining an action state delta sum for said selected sequence;

choosing a second sequence of actions from said chromosome population wherein said second sequence of actions has the same said action state delta sum as said first sequence of actions;

replacing said first sequence with said second sequence; and

inserting said child chromosome into said chromosome population.