A common problem in Evolutionary Computation as well as other forms of Stochastic Local Search is premature convergence on a local optima. A large variety of strategies have been devised for overcoming this problem including Simulated Annealing, Swarm Intelligence, Fitness Uniform Selection to Preserve Genetic Diversity (FUSS), as well as many others.
Once a given local optima has been reached, it is often very difficult to escape, particularly if adaptation is taking place on a fairly non-linear or "rough" fitness landscape. In his extensive work dealing with adaptation on NK-model landscapes, biologist Stuart Kaufman has made the following observations in his book The Origins Of Order:
Walks always stop at local optima well below the global optimum. Trapping is rife in network space. This has a critical consequence: adaptive walks typically cannot achieve arbitrary patterns of activities on attractors! Adaptation via fitter variants in network space becomes grossly hindered by the rugged structure of the landscape. Walks become frozen into small regions of the space. Any intuition we may have harbored that mutation and selection alone could tune attractors to arbitrary patterns of behavior appears to be wrong.
I suggest that once a given solution has reached a fairly fit local optima and has stopped improving at a reasonable rate, further computational resources are best spent on experiments involving other potential solutions of lesser fitness that still have a reasonable chance for improvement (i.e. have not yet reached their own local optima), hopefully allowing at least one of them to surpass the current best optima before inevitably grinding to a halt.
Assuming that the above idea is correct, it would be highly desirable to have some way of detecting when a given solution has reached an optima (either local or global) and thus be able to automatically trigger reallocation of search resources.
The Theory of Records may offer a way to do just that...
FELLER'S THEORY OF RECORDS
To again quote Kaufman:
In keeping with the sensible intellectual strategy of gaining insight into complex behavior by proposing simple initial caricatures, it is of interest to find that a simple, near-universal law describes the behavior of an adapting population in the limit of search by long jumps across sequence space. The "law" is equivalent to Feller's theory of records, which asks the waiting time for successive new athletic records to be set. The answer is that the waiting time doubles after each record is set.
Kaufman proceeds to explain his findings relating to optimization on a variety of problems, including the Traveling Salesman Problem, in which the rate of improvement very closely matches the Theory of Records schedule described above.
The Theory of Records can be characterized by the following simple equation:
where X is the total number of improvements found during the lifetime of the agent, and T is the total number of generations of experimentation that the agent has undergone.
LOCAL OPTIMA DETECTION VIA THE THEORY OF RECORDS
I suggest that it may be possible to use the Theory Of Records to statistically predict whether or not a given agent has become "stuck" on a local optima by examining the density of it's recent improvements X w.r.t. its total lifetime T.
We would anticipate that once an agent had reached a "dead-end" it would stop improving, thus leading to the following inequality:
The above inequality would be a signal to us that further improvement of a particular agent is becoming increasingly unlikely. This would suggest that we allocate fewer computational resources to that particular agent, and instead redirect those freed resources to other, more promising (albeit lower fitness) agents within the population.
No comments:
Post a Comment