Exploration vs Exploitation

[ambarket]

TO_DISCUSS: The general idea presented here, which is to have two different series of operators for exploration vs exploitation, and the decision of how to determine when exploration has ended and exploitation should begin. Also how would something like this play into the adaptation of our parameters and is it worth spending the time on this when our current algorithm already seems to function quite well.

Exploration: Defined as the period of time from generation 1 to 75% of max generations, or until the population's coverage ratio exceeds 90%, whichever occurs sooner.

• Selection: TO_DISCUSS: Does tournament selection make more sense during exploration? As Dr. Bui suggested, it generally will do a better job of maintaining diversity in the population, especially with our replace parent replacement scheme. The counterpoint is of course the time tradeoff as the deadlines approach. This shouldn't take long at all to implement however.
• Crossover: K-point crossover is performed between two parent test suites to generate two children.
• Mutation: Each child test suite is subjected to random mutation in the form of replacing constituent test cases with new random tests cases with a probability equal to the current mutation probability.
• Local Optimization: A random local search heuristic may be applied to the better of the two children with a likeliness dependent upon the current local optimization probability.
• Replacement: Replace parent if better, otherwise replace worst if better, otherwise kill child and move to next generation.

Exploitation: This phase starts immediately after exploration, as defined above ends. TO_DISCUSS: likely the mutation, crossover, and local optimization probabilities will change at this point to some predefined start point for exploitation.

• Selection: A single Organism will be selected using fitness proportional selection.
• Crossover: K-point crossover is performed between test cases within the seed Organism. TO_DISCUSS:: How many test cases to crossover, and how is the probability determined.
• Mutation: Each child test suite is subjected to random mutation in the form of replacing constituent test cases with new random tests cases with a probability equal to the current mutation probability.
• Local Optimization: A random local search heuristic is selected and applied with a likeliness dependent upon the current local optimization probability.
• Replacement: Replace parent if better, otherwise replace worst if better, otherwise kill child and move to next generation.

[Akiira]

I will give a more thoughtful reply tomorrow after I ponder this some more. Though my initial thoughts are maybe the algorithm will do this on its own because of the adaptive parameters and the variety of local optimizations.

What we really need is a harder control flow graph to really strain the algorithm. Then we could see how the current algorithm runs near the end and see if we could improve it with an explicit switch to exploitation mode.

[ambarket]

Yea I started trying to do this and I have doubts about if it even makes sense and that I should be spending time on it. It makes the adaptive parameters a lot harder to reason about. I think I'll set that branch aside for now.