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

Adaptive Parameters #8

Closed Akiira closed 9 years ago

Akiira commented 9 years ago

This is another thing our proposal says we will do. Should we do, and if so whats the best way? Discuss here.

ambarket commented 9 years ago

I think we should. Perhaps the adaptation can be based upon how how close we are to full coverage.

To throw an idea out maybe we could make test suite crossover probability a continuous function mapping 0 to 90% coverage to 1 to 0 probability.

Test case crossover then would be similar but start later. Maybe map 80 to 100% coverage with 1 to 0 test case crossover probability.

Mutation could be handled similarly.

Local optimization probability should remain very low the whole time. But may increase rapidly towards the very end.

Akiira commented 9 years ago

I like the idea of doing more local optimizations near the end. I can imagine TestSuites near the end will cover all but a few edges, and trying to cover the small number of uncovered edges with mutation and crossover seems like it would be inefficient.

Akiira commented 9 years ago

I added two methods to adapt the probability for mutation. One decreases the mutation as the coverage ratio increases. The other method adapts the mutation probability for a specific organism based on its coverage compared to the populations coverage. The reasoning behind the 2nd method is that if the organism covers the same edge as 100 other organism then it is not very helpful, thus we should increase its chance for mutation.

I might add the idea in my last post here, about adapting the frequency of calling local optimization, if I have time today.

edit: My first method might be redundant since I forgot you already added something similar on your branch. The only difference is mine does it in steps and yours is continuous.

ambarket commented 9 years ago

I think the second makes a lot of sense to be done on a per test case basis. So we have a mutation probability adapted based on the coverage ratio to determine if to mutate the test suite at all, then for each test case use the second probability algorithm to determine whether to mutate that test case.

Akiira commented 9 years ago

Good idea. Right now it just picks a random test case. I will change it to take an Organism and apply this to each test case.

ambarket commented 9 years ago

I'm envisioning this more in the Organism class itself. Where when you call Organism::mutate, in the forloop before each toss it will calculate a mutation probability for the current test case to be mutated.

Akiira commented 9 years ago

Alright i'll add it there. It will require the populations coverage to be passed in but that shouldn't be too bad because it's just a pointer.

ambarket commented 9 years ago

What are your thoughts on adapting cross over probability? I'm not sure it makes sense to do. ALso should we try to adapt the number of cut points?

Akiira commented 9 years ago

Cross over probability is a bit of a black hole for us. We never messed with it in problem set one, never read about it in any papers, and I don't recall the book talking about it either. If we can't reason about it, maybe its best to just keep it fixed rather then adding a new parameter to the simulation that must be tuned/adapted.

Cut points is a more interesting question. In problem set one it showed to have a decent effect on the time it took for the population to converge but we never tried changing it during a run. The beneficial effects could have been due to the type of problem we were looking at as well; I think it would be less useful here but am not opposed to the idea of adapting it.