Final Construction Phase (Ending GA once we have 100% coverage population wide)

[ambarket]

Below is a proposal for how we might design the final construction of a near optimal organism once the GA terminates.

After the population's coverage ratio reaches 100% or the max number of generations has been reached, the GA terminates and the program shifts into the final construction phase. During this phase an optimal Organism will be hand crafted from the pool of genetic material in the population. This is done in two steps

• First the best organism in the population is taken and grown by adding test cases from other organisms until it's coverage matches the population's coverage. This process involves looping through the population at most once, asking each organism if it happens to have an edge or predicate that the optimal organism is missing. If it does, the test case possessing the needed coverage is taken and inserted into the optimal organism.
• Once the optimal organism exhibits the best possible coverage, a simple minimization heuristic is applied in an attempt to achieve the same coverage using a lesser number of test cases. First the test cases are sorted in ascending order by the number of edges and predicates they cover. Then, starting with the test cases that contribute the least, an attempt is made to remove each test case. The removal is only performed if the overall test suite coverage is not decreased by the removal. After the minimization process completes, the resulting optimal organism is returned and the program exits.

[Akiira]

We could do this in one phase by starting with an empty test suite and using a greedy algorithm to always add the test case that covers the most uncovered edges. This could require O(n^2) time but should provide well sized test suites. Or it could be something as simple as taking the best organism and simply removing duplicates.

But, I don't think we should be too concerned with minimizing the test suite size. Our problem statement in the proposal stated the problem to solve was to "automatically create a test suite that covers all, or most, paths in a programs control flow graph." So we never really stated we were trying to minimize the test suite size.

That's not to say we shouldn't do it, just it should be a lower priority.

[ambarket]

This is now implemented and seems to work quite nicely. Will update the progress report to indicate it is completed. I also just deleted all the branches since they were all behind master. I hope that doesn't cause any problems for you, I probably should have asked first..

[ambarket]

I updated the progress report to include this. Please read over it at some point, I'm tired and my writing is probably very poor and maybe it should be included or worded differently. Its in both the update goals section and completed goals section.

[Akiira]

I don't think it really makes sense to add it to our updated goals because its not a goal our project was ever trying to achieve and isn't even part of the genetic algorithm, it is just run afterwards.

[ambarket]

That's fine go ahead and remove it On Mar 24, 2015 1:47 PM, "Akiira" notifications@github.com wrote:

I don't think it really makes sense to add it to our updated goals because its not a goal our project was ever trying to achieve and isn't even part of the genetic algorithm, it is just run afterwards.

— Reply to this email directly or view it on GitHub https://github.com/Akiira/Comp-524-program/issues/14#issuecomment-85617357 .

[Akiira]

I believe there is a bug in the constructFinalOrganism function. In at least some cases where the population does not have all the coverage it seems to loop forever. I would look into it myself but I'm getting very sleepy.