search

Akiira / Comp-524-program

A genetic algorithm to create test suites that cover every branch of a program
2 stars 0 forks source link

Local optimization #6

Closed Akiira closed 9 years ago

Akiira commented 9 years ago

Do we want to use it and if so how?

Akiira commented 9 years ago

From our discussion with Dr. Bui, we got several ideas for local optimization.

  1. We could generate a new TestCase and push it towards an uncovered edge and add that to the Organism.
  2. We could take an Organism and remove some TestCases that cover duplicate edges.
  3. We could grab two Organism with TestSuites that posses very little overlap and combine them.

If I missed anything please feel free to add it. Are you partial to any of these? I think the first would be quite effective but will require a good deal of work to get right.

Akiira commented 9 years ago

I wrote a very simple local optimization function. It searches a starting neighborhood and slowly expands outward. It actually works fairly well but I'm hoping its not too biased towards the given problem.

Akiira commented 9 years ago

So this local optimization works a little too well. It runs way fast by itself then with the genetic algorithm. Try playing around with how often it is called in the simulation loop to see what i mean. This makes me think it might be very biased towards this problem. I don't know if that is bad or good.

ambarket commented 9 years ago

So the case that we had so much trouble getting is when all three parameters are 0, so it makes sense that this does such a great job of finding it. Also all the other cases require a guess that is just slightly above the product of the two numbers, which becomes more likely as the ranges on the numbers decrease. I could imagine this being much less effective on a program with more parameters that aren't as directly related to one another and in cases where parameters must be selected from non-overlapping ranges in order to cover an edge or predicate.

We could make this more general by offsetting the parameter found by the median value of the range for each parameter. Or perhaps it would be more like typical local optimization to offset it by the parameter of a source test case instead of creating a new one.

Akiira commented 9 years ago

I added these two types of local opt as well. I think it might actually be more useful to use several types of local opt. During the simulations run when it wants to try local opt it could pick one randomly or keeping trying all of them until one works.

Akiira commented 9 years ago

As I think about it more the two local opts that don't take an organism are not really local optimizations. They are just a good starting point from which to search. This gives me two ideas.

  1. We could change these LOs to take an organism and add in numbers around zero or the mean randomly.
  2. We could use these as a TestCase generation heuristic and use them to seed the starting population with TestCases that have parameters around the mean or zero.
  3. We could do both 1 and 2.

I want to try at least 1. because I like the idea of having several "dumb" LOs rather than one super good one.

Akiira commented 9 years ago

Writing this as a note to myself mostly. Other local opt ideas:

  1. Push a test cases parameters towards the upper bounds for those parameters.
  2. Push a test cases parameters towards the lower bounds for those parameters.

Pushing could be done by taking the current value for a parameter and adding half the distance from the parameter to the bound.

Akiira commented 9 years ago

Can you just glance at this branch and make sure there is nothing obviously wrong with. I had been holding off merging into master until you had a chance to look at it. No rush though.

ambarket commented 9 years ago

Seems good to me.