Monday, July 18, 2005

 

One little model

Previous posts (here and here) have explained the utility and cost effectiveness of so called "little models." These are models that are less complex then something like the Navier-Stokes equations of motions but are more complex then mere intuition. These are the models that can be understood and provide meaningful insights into the dynamics of a problem and can simultaneously be sufficently accurate. With a little more effort, precise coefficients and functions of variables can be expanded to make the approximated model more accurate. My point is not to rehash what has already been said on the matter but to provide one example (of many existing little models!) that has proven very useful - the gambler's ruin (GR) model.

Population sizing estimates for GAs based on GR were first provided by Harik, Cantu-Paz, Golberg, and Miller in 1997 and later extended in 1999. The GR problem is simple: start with some initial amount of money, make a series of wagers, and predict how long it will take before you are completely broke or have won $n. There are fixed probabilities for winning or losing each wager.

This can be carried over quite nicely to GAs by considering the pairwise BB-decision making problem - where we are wondering which of two BBs provides the higher fitness. In this case, we consider that the best and second best are battling it out, and that the observed better of the two BBs corresponds to the outcome of the wager. Now in reality, other BBs are also concurrently competing and the probabilities are not fixed, but with some algebraic substitutions and minor approximations, a nice model is derived that is both intuitive and accurate for many problems. See the papers or David Goldberg's book for more information. This has been extended to account for exogenous noise and other tournament sizes. In the original analysis, these factors were not explicitly modeled because the goal was to understand how solution quality and population sizes are related, assuming that the other factors were favorably constant. With a proper population sizing bound, other pertinent relationships can be better understood and modified.

There are a myriad of techniques to derive such little models. These models can explain critical bounds or key trends and behaviors. More complex and accurate models may be needed at times, but little models are often extensible because they capture the underlying concepts of the problem. Anyway, just some musings on an important subject after rereading the GR problem.

Comments:
I like to read up on the latest info here sports fitness
 
Nice blog with interesting topics. I have a website that offers alot of controversial topics here. Just go to the links page and look for "Video Reviews"
 
And A Link Back To Your Web Site Excite You?
 
This comment has been removed by a blog administrator.
 
Post a Comment

<< Home

This page is powered by Blogger. Isn't yours?