See part I here.

Finally the end of another semester and another incredibly long week. It was a huge effort to get the software and report finished for AI in just over a week. Nevertheless, it was quite interesting. After running batch files, collating enourmous amounts of data, producing graphs and analysing algorithmic trends and points of interest it was all over. The final assessment in.After testing the canonical genetic algorithm (GA) we tested each of the additonal features we implemented; repair function, elites, random immigrants, adaptive mutation and the big kick. The latter was actually something I added at the last minute to make running tests a bit quicker from the batch file. After I realised it could potentially help with local maxima problems we were having I tweaked it a bit.Ted and I made many, many interesting observations from the data we collated.

This graph is an example of introducing random immigrants back into the population. The slightly thicker red line represents the basic GA and is included to provide a baseline or normal. Here, you can see that the general trend of introducing immigrants into the population is that the population fitness is raised. Where the basic GA converged and was unable to find a solution, this feature helped.

This charts shows the early convergence the basic GA exhibits on a tough problem.

 

This chart is an example of the Super GA (SGA) performance on the same problem as that above. The general fitness obtained for each population size of the Super GA is approx. 2-3 times greater then that of the basic GA. That is, the population fitness at convergence is considerably higher on the Super GA.This general trend of periods of stagnation then a rising of fitness is attributed to the big kick mentioned earlier. In some cases it forces the algorithm beyond the local maxima (observed just below fitness 90) allowing it to find the global maxima.

This shows how our Super GA compared to our basic GA. It took quite a few generations and big kicks but the Super GA did eventually push beyond the local maxima to find the global maximum. Regardless of this, the overall fitness before convergence is higher. Thus, qualitatively the SGA does appear to be better.

These were but a few examples of the 30+ graphs we collated, each showing some new interesting trend. There were so many things we wished to explore but just did not have the time to do so. Our general consensus was that the canonical GA or SGA are not well suited to the Sudoku problem domain. A hybrid approach adopting a GA and some further metaheruistic like Tabu Search would prove to be an interesting study.Sorry about the poor quality, chopped up graphs. For some reason they just got totally garbled when copying them into Paint.Net. We didn’t really have time to optimise graph layout either. But it was an interesting study that I hope to continue further at some point.