Adaptive problem solving method and apparatus utilizing evolutionary computation techniques

摘要

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 generated by a goal-seeking algorithm that uses a hint database and recursion to intelligently and efficiently generate a robust chromosome population. The 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.