Patent Publication Number: US-8977581-B1

Title: Data mining technique with diversity promotion

Description:
CROSS-REFERENCE TO OTHER APPLICATIONS 
     The following patent applications are incorporated herein for their teachings: U.S. patent application Ser. No. 13/184,307, filed 15 Jul. 2011, entitled “DATA MINING TECHNIQUE WITH EXPERIENCE-LAYERED GENE POOL”; and U.S. patent application Ser. No. 13/358,381, filed 25 Jan. 2012, entitled “DATA MINING TECHNIQUE WITH MAINTENANCE OF FITNESS HISTORY”. 
     BACKGROUND 
     The invention relates generally to data mining, and more particularly, to the use of genetic algorithms to extract useful rules or relationships from a data set for use in controlling systems. 
     In many environments, a large amount of data can be or has been collected which records experience over time within the environment. For example, a healthcare environment may record clinical data, diagnoses and treatment regimens for a large number of patients, as well as outcomes. A business environment may record customer information such as who they are and what they do, and their browsing and purchasing histories. A computer security environment may record a large number of software code examples that have been found to be malicious. A financial asset trading environment may record historical price trends and related statistics about numerous financial assets (e.g., securities, indices, currencies) over a long period of time. Despite the large quantities of such data, or perhaps because of it, deriving useful knowledge from such data stores can be a daunting task. 
     The process of extracting patterns from such data sets is known as data mining. Many techniques have been applied to the problem, but the present discussion concerns a class of techniques known as genetic algorithms. Genetic algorithms have been applied to all of the above-mentioned environments. With respect to stock categorization, for example, according to one theory, at any given time, 5% of stocks follow a trend. Genetic algorithms are thus sometimes used, with some success, to categorize a stock as following or not following a trend. 
     Evolutionary algorithms, which are supersets of Genetic Algorithms, are good at traversing chaotic search spaces. According to Koza, J. R., “Genetic Programming: On the Programming of Computers by Means of Natural Selection”, MIT Press (1992), incorporated by reference herein, an evolutionary algorithm can be used to evolve complete programs in declarative notation. The basic elements of an evolutionary algorithm are an environment, a model for a genotype (referred to herein as an “individual”), a fitness function, and a procreation function. An environment may be a model of any problem statement. An individual may be defined by a set of rules governing its behavior within the environment. A rule may be a list of conditions followed by an action to be performed in the environment. A fitness function may be defined by the degree to which an evolving rule set is successfully negotiating the environment. A fitness function is thus used for evaluating the fitness of each individual in the environment. A procreation function generates new individuals by mixing rules with the fittest of the parent individuals. In each generation, a new population of individuals is created. 
     At the start of the evolutionary process, individuals constituting the initial population are created, usually randomly, by putting together the building blocks, or alphabets, that form an individual. In genetic programming, the alphabets are a set of conditions and actions making up rules governing the behavior of the individual within the environment. Once a population is established, it is evaluated using the fitness function. Individuals with the highest fitness are then used to create the next generation in a process called procreation. Through procreation, rules of parent individuals are mixed, and sometimes mutated (i.e., a random change is made in a rule) to create a new rule set. This new rule set is then assigned to a child individual that will be a member of the new generation. In some incarnations, known as elitist methods, the fittest members of the previous generation, called elitists, are also preserved into the next generation. 
     A common problem with evolutionary algorithms is that of premature convergence: after some number of evaluations the population converges to local optima and no further improvements are made no matter how much longer the algorithm is run. In one of a number of solutions to this problem, known as the Age-Layered Population Structure (ALPS), an individual&#39;s age is used to restrict competition and breeding between individuals in the population. In the parlance of ALPS, “age” is a measure of the number of times that an individual&#39;s genetic material has survived a generation (i.e., the number of times it has been preserved due to being selected into the elitist pool). 
     When using genetic algorithms to mine a large database, it may not be practical to test each individual against the entire database. The system therefore rarely if ever knows the true fitness of any individual. Rather, it knows only an estimate of the true fitness, based on the particular subset of data samples on which it has actually been tested. The fitness estimate itself therefore varies over time as the individual is tested on an increasing number of samples. It is in this kind of environment that embodiments of the present invention reside. 
     SUMMARY 
     In the above-incorporated “DATA MINING TECHNIQUE WITH EXPERIENCE-LAYERED GENE POOL” application, a computer-implemented evolutionary data mining system includes a memory storing a candidate gene database in which each candidate individual has a respective fitness estimate; a gene pool processor which tests individuals from the candidate gene pool on training data and updates the fitness estimate associated with the individuals in dependence upon the tests; and a gene harvesting module providing for deployment selected ones of the individuals from the gene pool, wherein the gene pool processor includes a competition module which selects individuals for discarding from the gene pool in dependence upon, among other things, their updated fitness estimate. Accommodations are made to account for the incompleteness of fitness testing of various individuals at the time they are competing with each other. 
     Applicants have recognized, however, that in some circumstances there remains a tendency to converge on local optima with the population being overwhelmed by genotypes that are not very different in nature. This phenomenon can result in the crowding out of genotypes that are not as fit as the general population, but that are diverse enough in nature that they may eventually be the ancestral basis for much better genotypes in future generations. 
     In order to address this tendency, roughly described, a system can be arranged to select individuals not only for fitness, but also for their diversity relative to other individuals in the gene pool. Preferably, individuals are selected for discarding from the gene pool first by finding pairs of individuals which are similar to each other, and only then by discarding the less fit of the pair. Preferably, pairs are considered for their similarity only when both individuals of the pair have roughly the same experience level. 
     The above summary of the invention is provided in order to provide a basic understanding of some aspects of the invention. This summary is not intended to identify key or critical elements of the invention or to delineate the scope of the invention. Its sole purpose is to present some concepts of the invention in a simplified form as a prelude to the more detailed description that is presented later. Particular aspects of the invention are described in the claims, specification and drawings. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The invention will be described with respect to specific embodiments thereof, and reference will be made to the drawings, in which: 
         FIG. 1  is an overall diagram of an embodiment of a data mining system incorporating features of the invention. 
         FIG. 2  is a symbolic drawing of the candidate gene pool in  FIG. 1 . 
         FIG. 3  is a symbolic drawing of an individual in either the candidate gene pool or the production gene population of  FIG. 1 . 
         FIG. 4  is a symbolic drawing indicating how the training data database is organized. 
         FIG. 5  illustrates modules that can be used to implement the functionality of the training system in  FIG. 1 . 
         FIGS. 6 and 6A  collectively illustrate a method of operation of the competition module in  FIG. 5 . 
         FIG. 7  is a simplified block diagram of a computer system that can be used to implement either or both of the training system or production system in  FIG. 1 , and/or the training server and clients in  FIG. 8 . 
         FIG. 8  is a high-level block diagram of an example embodiment of the training system of  FIG. 1  using a network computing system. 
         FIG. 9  illustrates modules that can be used to implement the functionality of training server of  FIG. 8 . 
         FIG. 10  is a flow chart illustrating another method of operation of the competition module in  FIG. 5 . 
     
    
    
     DETAILED DESCRIPTION 
     The following description is presented to enable any person skilled in the art to make and use the invention, and is provided in the context of a particular application and its requirements. Various modifications to the disclosed embodiments will be readily apparent to those skilled in the art, and the general principles defined herein may be applied to other embodiments and applications without departing from the spirit and scope of the present invention. Thus, the present invention is not intended to be limited to the embodiments shown, but is to be accorded the widest scope consistent with the principles and features disclosed herein. 
     Data mining involves searching for patterns in a database. The fittest individuals are considered to be those that identify patterns in the database that optimize for some result. In embodiments herein, the database is a training database, and the result is also represented in some way in the database. Once fit individuals have been identified, they can be used to identify patterns in production data which are likely to produce the desired result. In a healthcare environment, the individual can be used to point out patterns in diagnosis and treatment data which should be studied more closely as likely either improving or degrading a patient&#39;s diagnosis. In a financial assets trading environment, the individual can be used to detect patterns in real time data and assert trading signals to a trading desk. The action signals from an individual can be transmitted to the appropriate controlled system for execution. 
     One difference between the data mining environments of the embodiments described herein, and many other environments in which evolutionary algorithms can be applied, is that the fitness of a particular individual in the data mining environment usually cannot be determined by a single test of the individual on the data; rather, the fitness estimation itself tends to vary as it is tested on more and more samples in the training database. The fitness estimate can be inaccurate as testing begins, and confidence in its accuracy increases as testing on more samples continues. This means that if an individual is “lucky” early on, in the sense that the first set of samples that it was given for testing happened to have been in some sense “easy”, then after only the first set of samples the individual will appear to be fitter than it actually is. If compared to other individuals that have much more experience, lucky individuals could displace individuals whose fitness estimates are lower but more realistic. If care is not taken, therefore, the algorithm will optimize for individuals that are lucky early on, rather than their actual fitness. 
     A solution to this problem, implemented in certain embodiments described herein but not required for all embodiments of the present invention, is to consider individuals for the elitist pool only after they have completed testing on a predetermined number of samples, for example 1000 samples. Once an individual has reached that minimum threshold experience level, comparisons with other individuals are considered valid and can compete for a place in the elitist pool. 
     However, the argument that high fitness values of individuals with less experience could be due to luck rather than true fitness, also applies, though to a lesser degree, even to individuals within the elitist pool. That is, if compared to other individuals that have much more experience, younger, luckier individuals that have already entered the elitist pool could still displace individuals whose fitness levels are lower but more realistic. Again, allowing such individuals to compete against each other even partially on the basis of fitness would continue to optimize to some degree for individuals that are lucky. The same solution can be applied to avoid this problem: divide the elitist pool into two layers on the basis of experience level. For example, layer 1 (L 1 ) may include only those individuals that have been tested on 1000-1999 samples, while a layer 2 (L 2 ) includes all individuals that have been tested on 2000 or more samples. Individuals compete only against other individuals within the same experience layer. 
     It will be appreciated that the tendency to optimize for lucky individuals still remains, within each layer, though to a still lesser degree. A solution is again the same: add more layers until the tendency to optimize for lucky individuals is reduced to a level sufficiently small for the particular application. In the extreme, each layer contains only those individuals having a single experience level, meaning only individuals that have been tested on exactly the same number of samples can compete against each other. This extreme may not be practical, however, as it can require a large amount of memory to maintain. Thus for a particular application, there will be an appropriate number of layers which minimizes the tendency to optimize for lucky individuals, yet remains practical to implement. 
     In general, in embodiments herein, the elitist pool contains T layers numbered L 1 -L T , with T&gt;1. The overall pool of candidate individuals also includes some that have not yet undergone sufficient numbers of tests to be considered for the elitist pool, and those individuals are considered herein to reside in a layer below the elitist pool, designed layer 0 (L 0 ). Each i&#39;th one of the layers in [L 0  . . . L T-1 ] contains only individuals with a respective range of testing experience [ExpMin(L i ) . . . ExpMax(L i )], each ExpMin(L i+1 )&gt;ExpMax(L i ). The minimum experience level of the bottom layer L 0  is 0, and the top layer L T  has a minimum experience level ExpMin(L T ) but no maximum experience level. Preferably, the experience ranges of contiguous layers are themselves contiguous, so that ExpMin(L i+1 )=ExpMax(L i )+1, for 0&lt;=i&lt;T. Note that testing experience level is a significantly different basis on which to stratify individuals in an elitist pool than age in the sense of ALPS. 
     In an embodiment, each layer i in the elitist pool (i.e. in layers [L 1  . . . L T ]) is permitted to hold a respective maximum number of individuals, QuotaL(L i ). The quota is chosen to be small enough to ensure competition among the individuals within the corresponding range of experience levels, but large enough to ensure sufficient diversity among the fit individuals that graduate to the next higher layer. The quota of layer L 0  is not chosen based on these criteria, since the individuals in that layer do not yet compete. Preferably the number of layers T in the elitist pool is fixed, but in another embodiment it can vary. 
     As each individual gains more experience, assuming it is not displaced within its current experience layer, it will eventually graduate to the next higher experience layer. If the next higher experience layer is not yet full, then the individual is added to that layer. If it fails the competition, then it is discarded. 
     Either way, a space is opened in the current experience layer (the layer from which the individual is graduating). The open space means that the next individual graduating into the current experience layer from below will be accepted without having to compete for its place—thereby defeating a purpose of the elitist pool. To mitigate this problem, an embodiment introduces the concept of an elitist pool minimum fitness, which in one embodiment is set to the minimum fitness of the top layer. The individuals in the top layer are assumed to have a relatively accurate estimate of their fitness, and since after the top layer is full the goal of the evolutionary algorithm is to identify individuals that are better than the ones already there, it makes sense to avoid devoting resources to individuals which already appear to be inferior. Thus in the embodiment, once the elitist pool minimum fitness is set, any individual being considered into the elitist pool can only be added if it has a fitness value above the elitist pool minimum fitness. Stated differently, once the top layer L T  is full, individuals are not allowed to enter L 1  unless their fitness level is at least as high as the minimum fitness FitMin(L T ) of the top layer L T . 
     In an embodiment, the elitist pool minimum fitness is not established until the top layer is full. Otherwise, if the earliest entrants into the top layer happen to have excellent fitness, they will block other entrants which might be needed for diversity. Also, rather than being based strictly on fitness, some embodiments can establish other minimum criteria for entry into the elitist pool, such as criteria which consider diversity relative to other individuals already in the elitist pool. Other useful criteria for some embodiments include a minimum acceptable activity level. 
     It will be appreciated that since the fitness estimate of individuals is still somewhat uncertain at the time they are being considered for entry into the elitist pool from L 0 , establishing the minimum entry fitness at exactly FitMin(L T ) may cull individuals that eventually would have been determined to have an actual fitness which exceeds FitMin(L T ). In another embodiment, therefore, the minimum fitness for entry into the elitist pool is set at some other fitness level which is a function of FitMin(L T ). For example, it can be set at 90% of FitMin(L T ). It will also be appreciated that the accuracy of an individual&#39;s fitness estimate improves as the individual progresses up through the experience layers. Another embodiment, therefore, reduces the potential inaccuracy of the elitist pool minimum fitness test by applying it at the entry to one of the higher layers in the elitist pool, rather than at L 0 . In yet another embodiment, the test is applied more than once, at the entry to more than one of the layers, or all of them. Other variations will be apparent. In general, in embodiments which attempt to cull unfit individuals early, individuals are discarded at the entry to at least one of the experience layers in the elitist pool, if their fitness estimate at that time is less than some function f( ) that depends at least on FitMin(L T ). Note that the function f( ) need not necessarily be the same for all the layers at which the rule is applied. 
     Individuals that enter the top layer may themselves undergo further testing on samples in the training database. With such further experience, the fitness estimate of even those individuals may change. This can introduce a wave effect in the top layer due to fluctuations in fitness estimates of the individual with minimum fitness. This will, in turn, affect the elitist pool minimum fitness if the top layer is at quota. If the fitness estimate of the individual with the minimum fitness in the top layer decreases, then the minimum fitness of the top layer (and hence the entire elitist pool minimum fitness) will decrease. In order to prevent this, in one embodiment, individuals that have reached the top layer do not undergo further testing. The justification here is that individuals in the top layer are assumed to already have fitness estimates which are as representative as possible to their actual fitness. Such an embodiment accepts any remaining error in the fitness estimate because the likelihood that purely random variations at that point would exceed an error range already considered acceptable, is too large. 
     In one embodiment, individuals are harvested from the entire elitist pool for use against production data. In another embodiment, only individuals that have reached the top layer are subject to harvesting. In either embodiment, further selection criteria can be applied in the harvesting process. Such criteria is usually specific to the application environment, and can include, for example, both fitness as well as characteristics of each individual&#39;s fitness trial history. 
     Even in a layered elitist pool arrangement, diversity can still be an issue. Diversity is an important factor in avoiding premature convergence on local optima. In the embodiments herein, therefore, promotion of diversity is integrated directly into the competition process. Individuals are selected not only for fitness, but also for their diversity relative to other individuals in the gene pool. Preferably, individuals are selected first for diversity, and only secondarily for fitness. The system ultimately optimizes for fitness, but by also promoting diversity along the way, local optima are avoided and the optimization can be improved. 
     Example Embodiment 
       FIG. 1  is an overall diagram of an embodiment of a data mining system incorporating features of the invention. The system is divided into three portions, a training system  110 , a production system  112 , and a controlled system  128 . The training system  110  interacts with a database  114  containing training data, as well as with another database  116  containing the candidate gene pool. As used herein, the term “database” does not necessarily imply any unity of structure. For example, two or more separate databases, when considered together, still constitute a “database” as that term is used herein. The candidate gene pool database  116  includes a portion  118  containing the elitist pool. The training system  110  operates according to a fitness function  120 , which indicates to the training system  110  how to measure the fitness of an individual. The training system  110  optimizes for individuals that have the greatest fitness, however fitness is defined by the fitness function  120 . The fitness function is specific to the environment and goals of the particular application. For example, the fitness function may be a function of the predictive value of the individual as assessed against the training data—the more often the individual correctly predicts the result represented in the training data, the more fit the individual is considered. In a financial asset trading environment, an individual might provide trading signals (e.g. buy, sell, hold current position, exit current position), and fitness may be measured by the individual&#39;s ability to make a profit, or the ability to do so while maintaining stability, or some other desired property. In the healthcare domain, an individual might propose a diagnosis based on patient prior treatment and current vital signs, and fitness may be measured by the accuracy of that diagnosis as represented in the training data. 
     The production system  112  operates according to a production gene population in another database  122 . The production system  112  applies these individuals to production data  124 , and produces outputs  126 , which may be action signals or recommendations. In the financial asset trading environment, for example, the production data  124  may be a stream of real time stock prices and the outputs  126  of the production system  112  may be the trading signals or instructions that one or more of the individuals in production gene population  122  outputs in response to the production data  124 . In the healthcare domain, the production data  124  may be current patient data, and the outputs  126  of the production system  112  may be a suggested diagnosis or treatment regimen that one or more of the individuals in production gene population  122  outputs in response to the production data  124 . The production gene population  122  is harvested from the training system  110  once or at intervals, depending on the embodiment. Preferably, only individuals from elitist pool  118  are permitted to be harvested. In an embodiment, further selection criteria are applied in the harvesting process. 
     The controlled system  128  is a system that is controlled automatically by the signals  126  from the production system. In the financial asset trading environment, for example, the controlled system may be a fully automated brokerage system which receives the trading signals via a computer network (not shown) and takes the indicated action. Depending on the application environment, the controlled system  128  may also include mechanical systems such as a engines, air-conditioners, refrigerators, electric motors, robots, milling equipment, construction equipment, or a manufacturing plant. 
       FIG. 2  is a symbolic drawing of the candidate gene pool  116  in  FIG. 1 . An “experience layered” elitist pool is used in the present embodiment, though aspects of the invention can be used in embodiments without experience layers, and indeed without an elitist pool. As can be seen in  FIG. 2 , the individuals in the pool are stratified into T+1 “experience layers”, labeled L 0  through L T . The individuals in L 0  are very inexperienced (have been tested on only a relatively small number of samples in training data  114 , if any), whereas the higher layers contain individuals in successively greater experience ranges. The layers L 1  through L T  constitute the elitist pool  118  ( FIG. 1 ). Each layer i in the elitist pool  118 , except for the top layer L T , has associated therewith three “layer parameters”: low and high quotas QuotaL(L i ) and QuotaH(L i ) for the layer, and a range of experience levels [ExpMin(L i ) . . . ExpMax(L i )] for the layer. The layer parameters for the top layer L T  include low and high quotas QuotaL(L T ) and QuotaH(L T ), but only a minimum experience level ExpMin(L T ). The layer parameters for the top layer L T  also include a minimum fitness level FitMin(L T ) in some embodiments. 
     In the embodiment of  FIG. 2 , the low quotas for all the layers in the elitist pool  118  are equal and fixed, as are the high the quotas for all the layers in the elitist pool  118 . Neither is required in another embodiment. In addition, ExpMin(L 0 )=0 in this embodiment. Also, as the experience ranges of the layers are contiguous, ExpMin of each layer can be inferred as one higher than ExpMax of the next lower layer, or ExpMax of each layer can be inferred as one lower than ExpMin of the next higher layer. Thus only the minimum experience level or the maximum experience level need be specified for each layer. In the embodiment, only the minimum experience levels are specified, and they are specified for layers L 1 -L T ; in another embodiment only the maximum experience levels are specified, and they are specified for layers L 0 -L T-1 . In yet another embodiment, the size of the range of experience layers assigned to all the layers is constant, and only one minimum or maximum experience level is specified in the layer parameters; the remainder are calculated algorithmically as needed. Other variations will be apparent. 
     The FitMin(L T ) value in  FIG. 2  is not specified a priori. Rather, it is filled by copying from the fitness estimate associated with the least fit individual in the top layer L T . Whenever the fitness estimate of the least fit individual in the top layer is updated, and whenever the least fit individual itself is replaced, FitMin(L T ) is updated correspondingly. FitMin(L T ) is used in embodiments that enforce an elitist pool minimum fitness level, and may be omitted in embodiments that do not. 
     In general, each layer has associated with it an “indication” of its layer parameters. As used herein, an “indication” of an item of information does not necessarily require the direct specification of that item of information. Information can be “indicated” in a field by simply referring to the actual information through one or more layers of indirection, or by identifying one or more items of different information which are together sufficient to determine the actual item of information. In addition, the term “identification” and its variants are used herein to mean the same as “indication”. 
     In one embodiment, the experience layer in candidate gene pool  116  define separate regions of memory, and the individuals having experience levels within the range of each particular layer are stored physically within that layer. Preferably, however, the experience layers are only implied by the layer parameters and the individuals can actually be located anywhere in memory. In one embodiment, the individuals in candidate gene pool  116  are stored and managed by conventional database management systems (DBMS), and are accessed using SQL statements. Thus a conventional SQL query can be used to obtain, for example, the fitness estimate of the least fit individual in the highest layer. New individuals can be inserted into the candidate gene pool  116  using the SQL “insert” statement, and individuals being discarded can be deleted using the SQL “delete” statement. In another embodiment, the individuals in candidate gene pool  116  are stored in a linked list. In such an embodiment insertion of a new individual can be accomplished by writing its contents into an element in a free list, and then linking the element into the main linked list. Discarding of individuals involves unlinking them from the main linked list and re-linking them into the free list. 
       FIG. 3  is a symbolic drawing of an individual  310  in either the candidate gene pool  116  or the production gene population  122 . As used herein, an “individual” is defined by its contents. An individual created by procreation is considered herein to constitute a different individual than its parents, even though it retains some if its parents&#39; genetic material. In this embodiment, the individual identifies an ID  312 , its experience level  314 , its current fitness estimate 316, and optionally its fitness trial history  324  (see the above-incorporated DATA MINING TECHNIQUE WITH MAINTENANCE OF FITNESS HISTORY patent application). It also includes one or more “rules”  318 , each of which contains one or more conditions 320 and an output  322  to be asserted if all the conditions in a given sample are true. During procreation, any of the conditions or any of the outputs may be altered, or even entire rules may be replaced. The individual&#39;s experience level  314  increments by one for each sample of the training data  114  on which it is tested, and its overall fitness estimate 316 is determined by fitness function  120 , averaged (or otherwise combined) over the all the trials. 
     As used herein, a “result” is the combination of outputs produced by an individual in response to a single data sample (either during training or in production), and the “performance” of an individual is a measure of how good the “result” was on that single sample. “Experience” level is a count of the number of samples on which the individual has been tested, though in systems that discard duplicate tests, it is a count of the number of unique samples on which the individual has been tested. An individual&#39;s “average performance” is the average of the “performance” of the individual over all the samples counted in the individual&#39;s experience level, and it can be used directly as the overall fitness estimate of the individual in some embodiments. In other embodiments the overall fitness estimate can be weighted to favor or disfavor some characteristic, such as a characteristic of the individual&#39;s fitness trial history. 
     A rule is a conjunctive list of indicator-based conditions in association with an output. Indicators are the system inputs that can be fed to a condition. These indicators are represented in the training database  114 , as well as in the production data  124 . Indicators can also be introspective, for example by indicating the fitness estimate of the individual at any given moment. In the embodiment of  FIG. 1 , the individual&#39;s conditions are all specified as parameter/value (“P/V”) pairs. That is, if in the current sample, the specified parameter has the specified value (or range of values), then the condition is true. Another embodiment can also include conditions which are themselves conditioned on other items (such as other conditions in the rule or in a different rule or the result of another entire one of the rules). Yet another embodiment can also include conditions or rules which are specified procedurally rather than as PN pairs. Many other variations will be apparent. 
     In a financial asset trading embodiment, during training, an individual can be thought of as a virtual trader that is given a hypothetical sum of money to trade using historical data. Such trades are performed in accordance with a set of rules that define the individual thereby prompting it to buy, sell, hold its position, or exit its position. The outputs of the rules are trading action signals or instructions, such as buy, sell, exit or hold. Rules may also be designed to contain gain-goal and stop-loss targets, thus rendering the exit action redundant. A hold occurs when no rule in the individual is triggered, therefore, the individual effectively holds its current position. The indicators on which the rules are based can be, for example, a time increment (“tick”), or the closing price for a stock day. 
     The following code defines an example rule in terms of conditions and indicators, as well as the action asserted by the rule, in accordance with one embodiment of the present invention:
         if (PositionProfit&gt;=2% and !(tick=(−54/10000)% prey tick and MACD is negative)   and !(tick=(−119/10000)% prey tick and Position is long))   and !(ADX×100&lt;=5052))   then SELL
 
where “and” represents logical “AND” operation, “!” represents logical “NOT” operation, “tick”, “MACD” and “ADX” are stock indicators, “SELL” represents action to sell, and “PositionProfit” represents the profit position of the individual.
       

     In a healthcare embodiment, an individual can be thought of as a set of rules predicting a patient&#39;s future state, given the patient&#39;s current and past state. The outputs of the rules can be proposed diagnoses or proposed treatment regimens that the individual asserts are appropriate given the conditions of the individual&#39;s rules. The indicators on which the rules are based can be a patient&#39;s vital signs, and past treatment and medication history, for example. An example rule is as follows:
         if pulse&gt;=120 and 18&lt;=blood pressure[6]&lt;20 and temp&gt;=104 and surgery duration&lt;22 and clamp on artery and medication=EB45 and last medication&gt;=60 and !white blood cell count [3]&lt;−2.3 and !oxygen level [1]&lt;−1.1-&gt;&gt;&gt;   then thromboembolism @ prob&lt;=0.65       

     In an embodiment, each individual also identifies a firing count for each rule. Whenever a rule asserts an action during training, the firing count for the rule is incremented. 
     The training data is arranged in the database  114  as a set of samples, each with parameters and their values, as well as sufficient information to determine a result that can be compared with an assertion made by an individual on the values in the sample. In one embodiment, the result is explicit, for example a number set out explicitly in association with the sample. In such an embodiment, the fitness function can be dependent upon the number of samples for which the individual&#39;s output matches the result of the sample. In another embodiment, such as in the financial asset trading embodiment, the result may be only implicit. For example, the sample may include the price of an asset at each tick throughout a trading day, and the training system  110  must hypothetically perform all the trading recommendations made by the individual throughout the trading day in order to determine whether and to what extent the individual made a profit or loss. The fitness function can be dependent upon the profit or loss that the individual, as a hypothetical trader, would have made using the tick data for the sample. 
       FIG. 4  is a symbolic drawing indicating how the training data is organized in the database  114 . The illustration in  FIG. 4  is for the financial asset trading embodiment, and it will be understood how it can be modified for use in other environments. Referring to  FIG. 4 , three samples  410  are shown. Each sample includes a historical date, an identification of a particular security or other financial asset (such as a particular stock symbol), and raw historical market data for that financial asset on that entire trading day, e.g. tick data, trading volume data, price, etc.; and all other data needed to test performance of the individual&#39;s trading recommendations on this asset on this historical trading day. 
       FIG. 5  illustrates various modules that can be used to implement the functionality of training system  110  ( FIG. 1 ). Candidate gene pool  116  and production gene population database  122  are also shown in the drawing. Solid lines indicate process flow, and broken lines indicate data flow. The modules can be implemented in hardware or software, and need not be divided up in precisely the same blocks as shown in  FIG. 5 . Some can also be implemented on different processors or computers, or spread among a number of different processors or computers. In addition, it will be appreciated that some of the modules can be combined, operated in parallel or in a different sequence than that shown in  FIG. 5  without affecting the functions achieved. Also as used herein, the term “module” can include “sub-modules”, which themselves can be considered herein to constitute modules. In particular, the gene testing module  512 , competition module  514 , and procreation module  516  are also considered herein to be sub-modules of a gene pool processor module  520 . The blocks in  FIG. 5  designated as modules can also be thought of as flowchart steps in a method. 
     Referring to  FIG. 5 , the candidate gene pool  116  is initialized by pool initialization module  510 , which creates an initial set of candidate individuals in L 0  of the gene pool  116 . These individuals can be created randomly, or in some embodiments a priori knowledge is used to seed the first generation. In another embodiment, individuals from prior runs can be borrowed to seed a new run. At the start, all individuals are initialized with an experience level of zero and a fitness estimate that is undefined. 
     Gene testing module  512  then proceeds to test the population in the gene pool  116  on the training data  114 . Only a subset of the population in the gene pool  116  is tested at this point. As used herein, the term “subset”, unless otherwise qualified, includes both proper and improper subsets as well as the null set. However, for the reasons explained above, the subset which is tested at this point is a non-null subset which includes only those individuals that have not yet reached the top layer L T  of the elitist pool  118  (of which there are none initially). Each individual in the subset undergoes a battery of tests or trials on the training data  114 , each trial testing the individual on one sample  410 . In one embodiment, each battery might consist of only a single trial. Preferably, however, a battery of tests is much larger, for example on the order of 1000 trials. In one embodiment, at least the initial battery of tests includes at least ExpMin(L 1 ) trials for each individual, to enable the initial individuals to qualify for consideration for the first layer of the elitist pool  118 . Note there is no requirement that all individuals undergo the same number of trials. After the tests, gene testing module  512  updates the fitness estimate associated with each of the individuals tested. 
     In an embodiment, the fitness estimate may be an average of the results of all trials of the individual. In this case the “fitness estimate” can conveniently be indicated by two numbers: the sum of the results of all trials of the individual, and the total number of trials that the individual has experienced. The latter number may already be maintained as the experience level of the individual. The fitness estimate at any particular time can then be calculated by dividing the sum of the results by the experience level of the individual. In an embodiment such as this, “updating” of the fitness estimate can involve merely adding the results of the most recent trials to the prior sum. In another embodiment, the fitness estimate can be affected by the fitness trial history, as discussed more fully in the above-incorporated DATA MINING TECHNIQUE WITH MAINTENANCE OF FITNESS HISTORY patent application. 
     After the gene testing module  512  has updated the fitness estimate associated with each of the individuals tested, competition module  514  updates the candidate pool  116  contents in dependence upon the updated fitness estimates. The operation of module  514  is described in more detail below, but briefly, the module considers individuals from lower layers for promotion into higher layers, discards individuals that are too similar and not as fit as other individuals in their target layer, and discards individuals that have been replaced in a layer by new entrants into that layer. Candidate gene pool  116  is updated with the revised contents. 
     After the candidate gene pool  116  has been updated, a procreation module  516  evolves a random subset of them. Only individuals in the elitist pool are permitted to procreate. Any conventional or future-developed technique can be used for procreation. In an embodiment, conditions, outputs, or rules from parent individuals are combined in various ways to form child individuals, and then, occasionally, they are mutated. The combination process for example may include crossover—i.e., exchanging conditions, outputs, or entire rules between parent individuals to form child individuals. New individuals created through procreation begin with an experience level of zero and with a fitness estimate that is undefined. Also, all of their firing counts are set to zero. These individuals are placed in L 0  of the gene pool  116 . Preferably, after new individuals are created by combination and/or mutation, the parent individuals are retained. In this case the parent individuals also retain their experience level, firing counts and fitness estimates, and remain in their then-current elitist pool layers. In another embodiment, the parent individuals are discarded. 
     After procreation, gene testing module  512  operates again on the updated gene pool  116 . The process continues repeatedly. 
     Sometime after the top layer of elitist pool  118  is full, individuals can be harvested for use by production system  112 . Gene harvesting module  518  retrieves individuals for that purpose. In one embodiment, gene harvesting module  518  retrieves individuals periodically, whereas in another embodiment it retrieves individuals only in response to user input. Gene harvesting module  518  selects only from the top layer L T , and can apply further selection criteria as well in order to choose desirable individuals. For example, it can select only the fittest individuals from L T , and/or only those individuals that have shown low volatility. Other criteria will be apparent to the reader. The individuals also undergo further validation as part of this further selection criteria, by testing on historical data not part of training data  114 . The individuals selected by the gene harvesting module  518  are written to the production gene population database  122  for use by production system  112  as previously described. 
     As mentioned, competition module  514  manages the graduation of individuals from lower layers in the candidate gene pool  116 , up to higher layers. In an aspect of the invention, at least for layers in the elitist pool below the top layer, the competition favors diversity of individuals in the target layer, as well as fitness. The competition can be implemented in a variety of ways.  FIG. 10  is a flow chart illustrating one implementation, in which individuals are considered sequentially. As with all flow charts herein, it will be appreciated that some of the acts described in  FIG. 10  can be combined, operated in parallel or in a different sequence than that shown in the drawing without affecting the functions achieved. Note also that because the competition module  514  is part of the gene processor  520 , whenever the competition module  514  is said to perform a particular function, it is equally valid to say that the gene processing module  520  performs that function. 
     Referring to  FIG. 10 , first, a loop  1010  is begun through all individuals which are candidates for promotion to a higher layer below the top layer. In a client/server embodiment (discussed below with respect to  FIG. 8 ), loop  1010  may be executed on the server and the candidates are either new individuals arriving from clients or individuals that have been updated based on client testing. In step  1014 , the module  514  determines whether the target experience layer is already at or above its low quota QuotaL. If not, then the candidate is simply added into that experience layer (step  1016 ). If the target layer is already at or above its low quota QuotaL, then in step  1018  the competition module  514  adds the candidate to the target layer and discards the less fit individual (which may be the candidate) from the one pair, of all the unique pairs of individuals now in the layer, which most nearly satisfies some predetermined measure of similarity. More specifically, the competition module  514  finds all unique pairs of individuals then in the layer (including the candidate), and selects the pair whose two individuals best satisfy the measure of similarity (step  1020 ). In step  1022  it then discards from the gene pool whichever individual in that pair has a lower fitness level. This may well be the candidate itself, if it happens to be very similar to another individual already in the layer, or it may be some other individual previously present in the layer. The competition module  514  then returns to step  1010  to consider the next candidate individual. By limiting competition to only those individuals within a common testing experience layer, the system is selecting individuals for discarding at least partially in dependence upon their testing experience level. By selecting individuals for discarding only from pairs whose two individuals best satisfy a measure of similarity, the system is selecting individuals for discarding at least partially in dependence upon a diversity measure of individuals in the gene pool. As used herein, diversity is the opposite of similarity. Both terms include the possibility of various kinds of group diversity/similarity, though in most embodiments described herein, similarity is considered only between the two individuals in a pair. 
     In discarding whichever individual of the pair which as the lower fitness level, step  1022  can operate as follows. In step  1040 , competition module  514  determines whether the candidate is in the most similar pair. If so, then in step  1042  it determines whether the candidate is more fit than the other individual in the pair. If it is more fit, then in step  1044  the other individual is replaced in the layer by the candidate. If in step  1042  the candidate is not fitter than the other in the pair, then in step  1046  the candidate is discarded. If in step  1040  the candidate is not in the most similar pair, then in step  1048 , whichever individual in the pair is least fit is replaced in the layer by the candidate. 
     Returning to step  1018 , the rationale for discarding the less fit individual from a pair of similar individuals rather than merely the least fit individual in the layer regardless of similarity, can be understood by considering the individuals in a layer as being grouped into “clusters” of individuals that are all likely to find similar patterns in the data. Only one representative is needed from each cluster, since the others are likely to be duplicative. And because limitations on computing power mandate limitations on the total number of individuals that can be evaluated, computing power expended on a duplicative individual can crowd out another individual which may appear now to be less fit, but might turn after more testing to be better. By using a measure of similarity which is good at predicting whether individuals are likely to find substantially the same patterns in the data, the two individuals found to be the most similar to each other are likely to be in the same cluster. 
     Various measures can be used in various embodiments as the measure of similarity. Since it can be difficult to know in advance what measures will be good at predicting similarity of behavior, as used herein, a “measure of similarity” is not required to be accurate in all instances. As used herein, a “measure of similarity” need only be more likely than not to predict accurately whether individuals are likely to find the same patterns in the sample data. 
     In an environment in which individuals are defined by rule sets as in  FIG. 3 , two individuals will find identical patterns if their rule sets are identical. As used herein, similarity is considered to include identity as a special case. If they are not identical, some measure of their similarity can be gleaned from the extent by which the rule sets differ from each other. Thus in one embodiment, similarity between two individuals is measured by placing them on an N-grid and calculating the distance between them (either Euclidean distance or Manhattan distance) in grid units. In the N-grid, each dimension represents a different one of the parameters in a rule, and an individual&#39;s coordinate in an i&#39;th dimension of the grid is calculated from the values which all its different rules require for the i&#39;th parameter in order to fire. To normalize these values, the values for a given parameter are grouped into buckets, and the bucket number is used in the calculation of grid coordinates. For example, if parameter j is share price, 10 buckets may be defined which divide the range of possible share prices into 10 sub-ranges, numbered 1-10. The sub-ranges for a given parameter need not necessarily all be of equal size. Then the j&#39;th coordinate then can be calculated as the sum or average over all the rules in the individual, of the bucket numbers into which the values specified for the j&#39;th parameter fall. 
     Preferably the bucket numbers for each rule are further weighted by the frequency at which the rule has fired during its testing experience. This is because even if rules are similar, they may fire at very different rates in different individuals (and therefore cause the individuals to find very different kinds of patterns) because (a) a small value difference could be significant, and (b) the sequence in which rules fire in a given individual can also affect the patterns that the individual will find. Thus individuals are preferably assigned different positions in the grid if their rules have fired at different frequencies. 
     In summary, the “similarity” between two individuals is calculated in this example as the distance between their positions on an N-grid. The position of an individual on the N-grid is calculated as (X 1 , X 2 , . . . , X N ), where 
     
       
         
           
             
               
                 X 
                 j 
               
               = 
               
                 
                   1 
                   R 
                 
                 ⁢ 
                 
                   
                     ∑ 
                     
                       i 
                       = 
                       1 
                     
                     R 
                   
                   ⁢ 
                   
                     
                       B 
                       
                         i 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         j 
                       
                     
                     ⁢ 
                     
                       F 
                       i 
                     
                   
                 
               
             
             , 
             
               j 
               = 
               1 
             
             , 
             … 
             ⁢ 
             
                 
             
             , 
             N 
             , 
           
         
       
         
         
           
             R is the total number of rules in the individual, 
             B ij  is the bucket number into which the value that rule i specifies for parameter j falls, 
             F i  is the firing frequency of rule i and is given by the firing count of rule i divided by the experience level of the individual. 
           
         
       
    
     It will be appreciated that the above is only one example of a measure of similarity, and many other types of measures can be used instead in different embodiments. It will also be appreciated that merely because one identified pair of individuals happens to be the most similar, does not necessarily mean they are similar. In some situations the individuals in a layer are already very diverse, and the newly added candidate does not significantly degrade such diversity. Preferably, therefore, the competition module  514  allows an escape, by which the quantity of individuals in a given layer is allowed to swell up to a second (high) quota, QuotaH, so long as diversity remains sufficiently strong. Thus before discarding any individuals in step  1022 , competition module  514  determines in step  1024  whether the candidate&#39;s target layer has reached its high quota QuotaH. If so, then the module  514  proceeds to step  1022  to discard the less fit of the most similar pair. If the layer has not yet reached QuotaH, then in step  1026  competition module  514  decides whether, even after adding the candidate, diversity in the layer remains sufficiently strong. If so, then the candidate is added without discarding any individual (step  1016 ). If not, then the module  514  again proceeds to step  1022  to discard the less fit of the most similar pair. 
     In an embodiment, the decision in step  1026  whether diversity in the layer is sufficiently strong, can be made by again referring to the N-grid discussed above. If the distance in the N-grid between the individuals in the most similar pair found in step  1020  is greater than some predetermined threshold, then the same can necessarily be said about the individuals in each of the pairs in the layer. In that case the layer diversity is considered sufficiently strong. In addition, the threshold in one embodiment can itself be determined as a function of the distance in the N-grid between the individuals in the least similar pair. For example, in one embodiment the threshold might be set at 90% of 1/P times the distance in the N-grid between the individuals in the least similar pair, where P is the number of individuals in the layer (including the candidate). If the individuals in the most similar pair are more distant from each other in the N-grid than that threshold, then all pairs in the layer are already sufficiently diverse even after adding the candidate, and so long as the layer is not above QuotaH, no individual need be discarded. In an embodiment, the least similar pair is found as part of the same algorithm that finds the most similar pair in step  1020 . 
     It can be appreciated that the calculation of similarity scores in step  1020  can be computationally expensive, especially when it is considered that the number of unique pairs to consider increases dramatically as the number of individuals in the layer increases. Therefore, in an embodiment, instead of searching every unique pair in the layer for the most and least similar, step  1020  searches only through those pairs in what are deemed to constitute a representative subset of the individuals in the layer. Thus in step  1020 , the competition module  514  first selects a proper subset, referred to herein as a “sample set”, of the individuals from the target layer for the candidate (step  1028 ). If the sample set does not already include the candidate, it is added in. Then, in step  1030 , using the methods described above, the competition module  514  finds the least and most similar pairs in the sample set. These pairs are considered to be the least and most similar pairs in the layer, or at least representative of such pairs. In one embodiment the sample set is selected randomly, whereas in another embodiment it is selected based on a preliminary similarity measure which is rougher but less computationally intensive than the measure used in step  1030  to find the most similar pair in the sample set. 
     It can be seen that the smaller the sample set relative to the number of individuals in the layer, the less effective will be the diversity promotion effect of step  1018 . An implementation of an embodiment that includes selection of a sample set therefore will involve a tradeoff between the extent of diversity promotion desired, and the amount of computing time or resources required. The sample set (including the candidate) must include a minimum of three individuals, in order that there be at least two pairs to compare for better similarity. And though the pair of individuals found most similar to each other in a sample set may not be the most similar pair of all the individuals in the layer, it can always be said that the pair determined to be the most similar pair in the sample set is more similar than at least one other pair in the layer. The size of the similarity set need not be the same for all layers. 
     In an embodiment that enforces an elitist pool minimum fitness criteria (see below with respect to  FIG. 6 ), the initial consideration of each candidate (prior to step  1014 ) can include a test of whether the candidate&#39;s fitness estimate satisfies the elitist pool minimum fitness. Typically this test is applied only on individuals graduating out of layer 0, but as mentioned previously, could be applied to individuals being considered for other layers in the elitist pool  118  as well. If the current individual does not satisfy the elitist pool minimum fitness, then it is discarded. 
     The  FIG. 10  routine processes candidates sequentially, and different embodiments can implement different sequences for processing the them. Note that the processing sequence can affect the results if, for example, an individual in layer L i  is being considered for layer L i+1  at the same time that an individual in layer L i−1  is being considered for layer L i . If the former test occurs first, then the population in layer L i  may fall below QuotaL(L i ) and the individual graduating from layer L i−1  will be promoted into layer L i  automatically (step  1016 ). If the latter test occurs first, then the individual graduating from layer L 1−1  may have to compete for its place in layer L i  (step  1022 ). In another embodiment, individuals are considered layer by layer either according to their target layer after promotion, or according to their current layer prior to promotion. Again, the sequence of individuals to consider within each layer will depend on the embodiment, as will the sequence in which the layers themselves are considered. 
       FIG. 6  illustrates a bulk-oriented method of operation of competition module  514 . In the embodiment of  FIG. 6 , the layers in the candidate gene pool  116  are disbanded and reconstituted each time the competition module  514  executes. These executions of competition module  514  are sometimes referred to herein as competition “events”, and each comparison made between the fitness estimate of one individual and that of another is sometimes referred to herein as a comparison “instance”. 
     In step  610 , the target experience layer is determined for all the individuals to be considered in the present competition event. In step  611 , all individuals whose experience level is still within that of L 0 , are assigned automatically to L 0 . (In another embodiment, individuals in L 0  are required to compete with each other on diversity just like individuals in the elitist pool.) 
     Step  616  implements the policy that once L T  is full, no individuals are allowed into the elitist pool  118  unless they are at least as fit as some predetermined function f( ) of the top layer minimum fitness. In step  616 , therefore, if L T  is full, all individuals graduating from L 0  to L 1  whose fitness estimate is less than f(FitMin(L T )) are discarded. Variations of step  616  to implement variations of the elitist pool minimum fitness policy, will be apparent. In step  618 , for each layer L i  above layer L 0 , all the individuals in the elitist gene pool  118  having experience level within the range associated with layer L i  are considered. Of these individuals, only some number, between QuotaL(L i ) and QuotaH(L i ), inclusive, of the individuals are assigned to layer L i  and the remainder are discarded. 
     As used herein, a phrase such as “only the five fittest individuals”, or “only some number of individuals”, need not necessarily fill all available places. That is, if there are only three individuals to consider for five available places, the phrase is satisfied if all three individuals are assigned places. Thus it can be seen that step  618  includes both a policy that individuals entering a layer that is already at quota must compete for their place in that layer, as well as a policy that individuals entering a layer that is not yet full are promoted to that layer automatically. It can also be seen that step  618  implements a policy that only individuals having roughly the same experience level compete with each other. 
     The competition in step  618 , like that in step  1018  ( FIG. 10 ), optimizes for diversity then fitness.  FIG. 6A  is a flow chart illustrating a layer-oriented technique for implementing step  618 . In step  650 , the competition module  514  begins a loop through all of the layers L 1  through L T . For each layer, roughly described, the system will identify clusters of similar individuals and discard the least fit individual from each cluster until (a) the layer population shrinks to QuotaL(L i ), or (b) the layer population shrinks to QuotaH(L i ) and no more clusters are present. 
     In step  652 , the competition module  514  ranks all unique pairs in the current layer by similarity. The measure by which similarity is determined can be the same as that discussed above. The  FIG. 6A  embodiment can use sample sets as in the  FIG. 10  embodiment, in which case step  652  involves a step  654  in which a sample set is selected from the pre-existing individuals in the current layer, and the candidate individuals for adding to the layer are added into the sample set. All unique pairs in the sample set are then ranked by similarity. 
     The embodiment of  FIG. 6A , like that of  FIG. 10 , can include an escape to allow for swelling the layer population, up to its high quota QuotaH(L i ), if the layer population is and remains sufficiently diverse even with the addition of new candidates. Thus in step  658 , like step  1024  ( FIG. 10 ), competition module  154  determines whether the current layer has reached its high quota QuotaH(L i ). If not, then in step  660  competition module  514  decides whether, even after all pending candidates, diversity in the layer remains sufficiently strong. If it does, then the process returns to step  650  to consider the next layer. If either the current layer is already at its high quota QuotaH(L i ), or the current layer is not found sufficiently diverse, then in step  662  the least fit individual is discarded from the most similar pair in the sample set (or in the layer, if no sample set is used). 
     In step  664  it is determined whether the population of the current layer, including new candidates, still exceeds the low quota QuotaL for the layer. If so, then another individual is considered for discarding. In one embodiment, this can involve returning to step  654  to select a new sample set and to re-rank the unique pairs in the new sample set by similarity. In another embodiment, the existing sample set is re-used. The competition module  154  returns to step  662  to again discard the least fit individual from the most similar pair remaining in the sample set after the previous iteration of step  662 . Step  662  can be implemented by scanning the previously-ranked list of unique pairs in the sample set, starting from the most similar pair and stopping at the first pair which does not contain an individual previously discarded. Optionally in this latter embodiment involving re-use of the existing sample set, steps  658  and  660  can be repeated prior to each iteration of step  662 , to end the competition in the current layer if it is already sufficiently diverse and its population is no greater than the high quota QuotaH for the layer. Also in this latter embodiment, it is preferable that the sample set not be re-used too often because of the imprecision by which the sample set truly represents the clustering of all the individuals in the layer. Thus in yet a third embodiment, each sample set is re-used only up to some predetermined number of times (in step  662 ), after which a new sample set is selected (step  654 ). Other variations will be apparent to the reader. 
     If in step  664  it is determined that the current layer population has fallen to its low quota QuotaL, then in step  666  it is determined whether there are more layers to consider. If so, then the competition module returns to step  650  to consider the next layer. 
       FIG. 7  is a simplified block diagram of a computer system  710  that can be used to implement training system  110 , production system  126 , or both. While  FIGS. 1 ,  5 ,  6 ,  6 A,  9  and  10  indicate individual components for carrying out specified operations, it will be appreciated that each component actually causes a computer system such as  710  to operate in the specified manner. 
     Computer system  710  typically includes a processor subsystem  714  which communicates with a number of peripheral devices via bus subsystem  712 . These peripheral devices may include a storage subsystem  724 , comprising a memory subsystem  726  and a file storage subsystem  728 , user interface input devices  722 , user interface output devices  720 , and a network interface subsystem  716 . The input and output devices allow user interaction with computer system  710 . Network interface subsystem  716  provides an interface to outside networks, including an interface to communication network  718 , and is coupled via communication network  718  to corresponding interface devices in other computer systems. Communication network  718  may comprise many interconnected computer systems and communication links. These communication links may be wireline links, optical links, wireless links, or any other mechanisms for communication of information. While in one embodiment, communication network  718  is the Internet, in other embodiments, communication network  718  may be any suitable computer network. Typically it is an IP-based communication network. 
     The physical hardware component of network interfaces are sometimes referred to as network interface cards (NICs), although they need not be in the form of cards: for instance they could be in the form of integrated circuits (ICs) and connectors fitted directly onto a motherboard, or in the form of macrocells fabricated on a single integrated circuit chip with other components of the computer system. 
     User interface input devices  722  may include a keyboard, pointing devices such as a mouse, trackball, touchpad, or graphics tablet, a scanner, a touch screen incorporated into the display, audio input devices such as voice recognition systems, microphones, and other types of input devices. In general, use of the term “input device” is intended to include all possible types of devices and ways to input information into computer system  710  or onto computer network  718 . 
     User interface output devices  720  may include a display subsystem, a printer, a fax machine, or non-visual displays such as audio output devices. The display subsystem may include a cathode ray tube (CRT), a flat-panel device such as a liquid crystal display (LCD), a projection device, or some other mechanism for creating a visible image. The display subsystem may also provide non-visual display such as via audio output devices. In general, use of the term “output device” is intended to include all possible types of devices and ways to output information from computer system  710  to the user or to another machine or computer system. In particular, an output device of the computer system  710  on which production system  112  is implemented, may include a visual output informing a user of action recommendations made by the system, or may include a communication device for communicating action signals directly to the controlled system  128 . Additionally or alternatively, the communication network  718  may communicate action signals to the controlled system  128 . In the financial asset trading environment, for example, the communication network  718  transmits trading signals to a computer system in a brokerage house which attempts to execute the indicated trades. 
     Storage subsystem  724  stores the basic programming and data constructs that provide the functionality of certain embodiments of the present invention. For example, the various modules implementing the functionality of certain embodiments of the invention may be stored in storage subsystem  724 . These software modules are generally executed by processor subsystem  714 . Storage subsystem  724  also stores the candidate gene pool  116 , the training database  114 , and/or the production gene population  122 . Alternatively, one or more of such databases can be physically located elsewhere, and made accessible to the computer system  710  via the communication network  718 . 
     Memory subsystem  726  typically includes a number of memories including a main random access memory (RAM)  730  for storage of instructions and data during program execution and a read only memory (ROM)  732  in which fixed instructions are stored. File storage subsystem  728  provides persistent storage for program and data files, and may include a hard disk drive, a floppy disk drive along with associated removable media, a CD ROM drive, an optical drive, or removable media cartridges. The databases and modules implementing the functionality of certain embodiments of the invention may have been provided on a computer readable medium such as one or more CD-ROMs, and may be stored by file storage subsystem  728 . The host memory  726  contains, among other things, computer instructions which, when executed by the processor subsystem  714 , cause the computer system to operate or perform functions as described herein. As used herein, processes and software that are said to run in or on “the host” or “the computer”, execute on the processor subsystem  714  in response to computer instructions and data in the host memory subsystem  726  including any other local or remote storage for such instructions and data. 
     Bus subsystem  712  provides a mechanism for letting the various components and subsystems of computer system  710  communicate with each other as intended. Although bus subsystem  712  is shown schematically as a single bus, alternative embodiments of the bus subsystem may use multiple busses. 
     Computer system  710  itself can be of varying types including a personal computer, a portable computer, a workstation, a computer terminal, a network computer, a television, a mainframe, a server farm, a widely-distributed set of loosely networked computers, or any other data processing system or user device. Due to the ever-changing nature of computers and networks, the description of computer system  710  depicted in  FIG. 7  is intended only as a specific example for purposes of illustrating the preferred embodiments of the present invention. Many other configurations of computer system  710  are possible having more or less components than the computer system depicted in  FIG. 7 . 
     Client/Server Embodiment 
     In some environments, the training data used to evaluate an individual&#39;s fitness can be voluminous. Therefore, even with modern high processing power and large memory capacity computers, achieving quality results within a reasonable time is often not feasible on a single machine. A large gene pool also requires a large memory and high processing power. In one embodiment, therefore, a client/server model is used to provide scaling in order to achieve high quality evaluation results within a reasonable time period. Scaling is carried out in two dimensions, namely in pool size as well as in evaluation of the same individual to generate a more diverse gene pool so as to increase the probability of finding fitter individuals. In the client/server embodiment, the gene pool is distributed over a multitude of clients for evaluation. Each client continues to evaluate its own client-centric gene pool using data from training database  114 , which it may receive in bulk or periodically on a sustained and continuing basis. Individuals that satisfy one or more predefined conditions on a client computer are transmitted to the server to form part of a server-centric gene pool. 
     Distributed processing of individuals also may be used to increase the speed of evaluation of a given individual. To achieve this, individuals that are received by the server but have not yet been tested on a certain number of samples, or have not yet met one or more predefined conditions, may be sent back from the server to a multitude of clients for further evaluation. The evaluation result achieved by the clients (alternatively called herein a partial evaluation) for an individual is transferred back to the server. The server merges the partial evaluation results of an individual with that individual&#39;s fitness estimate at the time it was sent to the clients to arrive at an updated fitness estimate for that individual in the server-centric gene pool. For example, assume that an individual has been tested on 500 samples and is sent from the server to, for example, two clients each instructed to test the individual on 100 additional samples. Accordingly, each client further tests the individual on the additional 100 samples and reports its own client-centric fitness estimate to the server. The server combines these two estimates with the individual&#39;s fitness estimate at the time it was sent to the two clients to calculate an updated server-centric fitness estimate for the individual. Preferably, as set forth in the above-incorporated DATA MINING TECHNIQUE WITH MAINTENANCE OF FITNESS HISTORY patent application, an intelligent merging process is used which compares the fitness trial history of each testing battery and deletes duplicate tests. The combined results represent the individual&#39;s fitness evaluated over 700 days. In other words, the distributed system, in accordance with this example, increases the experience level of an individual from 500 samples to 700 samples using only 100 different training samples at each client. A distributed system, in accordance with the present invention, is thus highly scalable in evaluating its individuals. 
     Advantageously, clients are enabled to perform individual procreation locally, thereby improving the quality of their individuals. Each client is a self-contained evolution device, not only evaluating the individuals in its own pool, but also creating a new generation of individuals and moving the evolutionary process forward locally. Thus clients maintain their own client-centric gene pool which need not match each other&#39;s or the server-centric gene pool. Since the clients continue to advance with their own local evolutionary process, their processing power is not wasted even if they are not in constant communication with the server. Once communication is reestablished with the server, clients can send in their fittest individuals to the server and receive additional individuals from the server for further testing. 
       FIG. 8  is a high-level block diagram of an example embodiment of training system  110  implemented using a network computing system. The training system  110  includes a plurality of client computers  820  (sometimes referred to herein simply as “clients”) and a training server computer  810 . Server  810  may itself be a central or a distributed server. A client computer  820  may be a laptop computer, a desktop computer, a cellular/VoIP handheld computer or smart phone, a tablet computer, distributed computer, or the like. An example system may have hundreds of thousands of clients. In an embodiment, the training server and/or each of the client computers can have the structure of  FIG. 7 , or any of its variations as described above. The client computers  820  communicate with the training sever  810  to receive individuals for testing, and to report tested individuals back to the training server  810 . The training server  810  maintains a server-centric experience-layered elitist pool  118 , but in an embodiment, does not maintain any candidate individuals below layer L 1  of the elitist pool. New individuals are created by clients, both during initialization and by procreation, and they are not reported to the training server  810  until they have been tested on sufficient numbers of samples to qualify for the server&#39;s elitist pool  118 . The number of individuals created by the clients  820  may vary depending on the memory size and the CPU processing power of the client. For example, in one embodiment, a client may have 1000 individuals for evaluation. Each client computer  820  further has a communication port to access one or more data feed servers  830 , which retrieve and forward training samples from the training database  114  to the client computers  820 . Alternatively, although not shown, the training samples may be supplied from data feed server  830  to the clients  820  via the training server  810 . 
       FIG. 9  illustrates various modules that can be used to implement the functionality of training server  810  ( FIG. 8 ). Elitist pool  118  and production gene population database  122  are also shown in the drawing. As in the embodiment of  FIG. 5 , solid lines in  FIG. 9  indicate process flow, and broken lines indicate data flow. The implementation variations mentioned above with respect to the embodiment of  FIG. 5  apply to  FIG. 9  as well. 
     In the operation of the client/server model, the training server  810  does not perform any testing or procreation itself. It does, however, enforce competition within its own server-centric elitist pool  118  when individuals are returned from clients.  FIG. 9  illustrates various modules that can be used to implement the functionality of training server  810 . Like the embodiment of  FIG. 5 , the training server  810  includes a competition module  904 . It also includes gene harvesting module  518 , which may be same as in  FIG. 5 . It also includes gene testing and procreation functionality, but these are combined into a single client delegation module  902  in  FIG. 9 . The client delegation module  902  and the competition module  904  constitute two sub-modules in a gene pool processor module (not shown specifically in  FIG. 9 ). The  FIG. 9  embodiment does not include a pool initialization module in the sense of  FIG. 5 , since as mentioned, the clients initialize their own individual pools. 
     Referring to  FIG. 9 , in step  910 , the competition module  904  receives individuals from one or more of the client computers  820 . These individuals may arrive asynchronously, if and when client computers have them available to transmit. They may arrive out-of-order, and some individuals previously sent out for testing may never return. Individuals may arrive individually, or in bunches. At various times determined by competition module  904 , after at least one individual has arrived, competition module  904  proceeds to step  912  to begin a competition “event”. 
     In step  912 , competition module  904  determines whether each incoming individual is a new one, or a return of an individual that the server previously sent out for testing. This determination can be made on the basis of individual IDs  312  ( FIG. 3 ). If the latter, then the training server  810  merges the newly received copy of the individual into the prior version in the server-centric elitist pool  118 . In one embodiment, the merging step involves merely replacing the prior copy of the individual in the server-centric elitist pool  118 , with the one newly received. In a variation of that embodiment, replacing may involve merely updating the experience level and the fitness estimation of the prior copy of the individual in the server-centric elitist pool  118 . Preferably, an intelligent merging process is used which deletes duplicate tests. 
     In step  914  the incoming individual (if new) or the updated individual (if merged) competes for its position in the server elitist pool  118 . In one embodiment, the same rules of competition apply here as they do for the competition module  514  in the server-only model. The same implementation options would be available here as well. In another embodiment, diversity is not particularly encouraged in client machines in the same way as set forth above with respect to  FIG. 5 . Rather, individuals compete for their places in each layer solely (or mainly) on the basis of fitness. See the above-incorporated DATA MINING TECHNIQUE WITH EXPERIENCE-LAYERED GENE POOL patent application for an example illustrating how competition may be implemented in this latter embodiment. 
     In the client delegation module  902 , in step  916 , the server  810  selects individuals from the server-centric elitist pool  118 , and sends them out to one or more clients  820  for further testing (step  918 ). As in the server-only embodiment, the client delegation module  902  is restricted from selecting for further testing individuals already in the top layer of the elitist pool  118 . In one embodiment, the battery of trials that an individual is to undergo is dictated by the training server. In such an embodiment, the server-centric view of the battery is the same as the client-centric view of the battery. In another embodiment, the battery of trials that an individual is to undergo is left to the client to decide, and client may perform more than one battery of trials on the individual before returning it to the server. In the latter embodiment, the client has its own client-centric view of a testing battery. 
     In step  920  the client machines  820  test the individuals against training data from the data feed server  830 , and update each individual&#39;s fitness and experience level locally. Step  920  is shown in broken lines in  FIG. 9  because it is performed by clients rather than training server  810 . At various subsequent times, the server  810  again receives back updated individuals from the clients in step  910 , and repeats the process of  FIG. 9 . 
     The operation of the client computers  820  is the same as that previously described with respect to  FIG. 5 , with the exception that individuals are provided both by the pool initialization module  510 , as well as from the training server  810 . Also, in an embodiment, individuals compete in client computers in a manner set forth in the above-incorporated DATA MINING TECHNIQUE WITH EXPERIENCE-LAYERED GENE POOL patent application. Optionally in such embodiment, diversity is promoted in the client computers by guaranteeing that a percentage of the client elitist pool be randomly selected individuals. 
     The candidate gene pool  116  in a client computer  820  is client-centric, and includes all candidate individuals being considered by the clients, including those that do not yet have sufficient experience to be considered for the elitist pool in the client computer. The candidate gene pool in the clients are layer-oriented as shown in  FIG. 2 , and for convenience, the layers in a client computer are sometimes designated herein with a top layer numbered CT rather than T, and with layers designated CL O -CL CT . None of the layer parameters in the client-centric gene pool, including the number of layers, need be the same as their corresponding parameters in other clients or in the server. Preferably the candidate gene pool  116  in the client computers  820  are implemented using linked lists, whereas the elitist pool  118  in the server  810  are implemented using a DBMS, both as previously described. 
     Unlike the single server embodiment, the gene testing module in the client computer  820  does not prevent further testing of individuals that have reached the top layer CL CT  of the client-centric elitist pool  820 . The gene harvesting module in a client computer  820  selects individuals only from the top layer CL CT  of the client computer  820  for transmitting back to the server  810 . Since the server  810  does not maintain any individuals that do not qualify for the server-centric elitist pool  118 , the minimum experience level of the top layer CL CT  in the client-centric elitist pool on each client computer  820  must be at least as high as the minimum experience level of the lowest layer L 1  of the elitist pool  118  of the training server  810 . Preferably the minimum experience level of the top layer CL CT  in the client-centric elitist pool on each client computer  820  is equal to the minimum experience level of the lowest layer L 1  of the elitist pool  118  of the training server  810 . 
     Note that because of procreation on the client system  820 , individuals may be sent up to the training server  810  which the training server  810  had never before seen. Such individuals are handled in step  914  ( FIG. 9 ), by requiring them to compete for their position in the server-centric elitist pool  118  of the training server  810 . Note further that because of competition in the client computer  820 , some individuals that the training server  810  sent to the client computer  820  for further testing will never be returned to the training server  810 . In this case the prior copy of the individual, retained by the training server  810 , remains in place in the elitist pool  118  of the training server  810  unless and until it is displaced through competition in the training server  810  (step  914 ). Still further, note that an individual retained in the training server  810  after it has also been sent to a client  820  for further testing, may become displaced and deleted from the elitist pool  118  in the training server  810  through competition in the training server  810  (step  914 ). In this case, if the same individual is returned by the client computer  820 , the training server  810  simply ignores it. 
     As used herein, a given event or value is “responsive” to a predecessor event or value if the predecessor event or value influenced the given event or value. If there is an intervening processing element, step or time period, the given event or value can still be “responsive” to the predecessor event or value. If the intervening processing element or step combines more than one event or value, the signal output of the processing element or step is considered “responsive” to each of the event or value inputs. If the given event or value is the same as the predecessor event or value, this is merely a degenerate case in which the given event or value is still considered to be “responsive” to the predecessor event or value. “Dependency” of a given event or value upon another event or value is defined similarly. 
     Applicants hereby disclose in isolation each individual feature described herein and each combination of two or more such features, to the extent that such features or combinations are capable of being carried out based on the present specification as a whole in light of the common general knowledge of a person skilled in the art, irrespective of whether such features or combinations of features solve any problems disclosed herein, and without limitation to the scope of the claims. Applicants indicate that aspects of the present invention may consist of any such feature or combination of features. In view of the foregoing description it will be evident to a person skilled in the art that various modifications may be made within the scope of the invention. 
     The foregoing description of preferred embodiments of the present invention has been provided for the purposes of illustration and description. It is not intended to be exhaustive or to limit the invention to the precise forms disclosed. Obviously, many modifications and variations will be apparent to practitioners skilled in this art. In particular, and without limitation, any and all variations described, suggested or incorporated by reference in any section of this patent application are specifically incorporated by reference into the description herein of embodiments of the invention. In addition, any and all variations described, suggested or incorporated by reference herein with respect to any one embodiment are also to be considered taught with respect to all other embodiments. The embodiments described herein were chosen and described in order to best explain the principles of the invention and its practical application, thereby enabling others skilled in the art to understand the invention for various embodiments and with various modifications as are suited to the particular use contemplated. It is intended that the scope of the invention be defined by the following claims and their equivalents.