\chapter{Conclusions}
\label{chap:Conclusions}

In this chapter, we will review the development and analysis of the Parallel Selfish Gene Algorithm, presenting the knowledge gained, the lessons learned, and the questions that remain unanswered. First, some general conclusions will be given, followed by the definitive verdict on scalability and efficiency in the second section. The final section presents a critical view of the results of the work, and states some open questions and suggestions for further work.



\section{General conclusions}

In \autoref{sec:SelfishGeneAlgorithm} the Selfish Gene Algorithm (SG) is introduced, while \autoref{sec:DevPhase1} describes the process of implementing this algorithm. The main conclusion here is that despite its relative anonymity, SG is a solid algorithm. Corno et al.\ already showed the algorithm to be capable of handling the 0/1~Multiple Knapsack Problem \cite{corno98} and the Cellular Automata Problem \cite{corno00}; the implementation of SCP-SG shows that the algorithm can also solve the Vertex Cover Problem, while the implementation of PSG confirms that the algorithm is capable of evolving high-quality cellular automata.

Furthermore, the implementation of PSG demonstrates that the ``island model'' of parallel evolutionary algorithms described in \autoref{sec:IslandModel} can be successfully applied to a non-standard, implicit-population algorithm such as SG.

Taking a closer look at the Cellular Automata Problem, we conclude that the fault vector covering method of TPG evaluation is a good alternative to the much more time-consuming fault simulation approach. This evokes the analogy of the differences between heuristic search algorithms (evolutionary algorithms, simulated annealing, among others) and exhaustive methods such as depth-first search; heuristic search methods are capable of finding near-optimal solutions to a problem in a fraction of the time needed for an exhaustive search.

Another lesson learned from the Cellular Automata Problem is that elementary cellular automata are good test pattern generators for BIST circuitry. This confirms the findings of Corno et al.\ \cite{corno00} and Fi{\v{s}}er \cite{fiser04}. Moreover, the cellular automata evolved by PSG have only four of the 256 CA rules available to them, yet yield a fault coverage upwards of 93\% for all benchmark circuits considered.


\section{Scalability and efficiency}
\label{sec:ScalabilityEfficiency}

In \autoref{sec:PPM} we introduced the general concept of scalability, defined as the ability to utilize increasing numbers of processors effectively. By this definition, PSG was shown to scale reasonably well: an increase in the number of processors translates to either a reduction in execution time, or an increase in solution quality.

In \autoref{sec:SpeedupAndSolutionQuality} two approaches to measuring speedup of PEA's are presented: the convergence-based approach and the solution-quality-based approach. Since there is no strict consensus on which of these should be used, both were attempted.

When convergence-based speedup is considered, PSG shows no signs of time savings when more processors are utilized. This is in no way a bad sign, since the solution quality attained by high-$p$ configurations does tend to exceed that of the sequential implementation.

The situation is different when the solution-quality-based approach to speedup is adopted. In this case, the algorithm does show clear time savings for higher-$p$ configurations, and the speedup $S(n,p)$ is an increasing function of $p$. Aggregate speedup is depicted in \autoref{fig:ScalabilityPhase2SpeedupAll}; this is perhaps the most important graph in the document, and so it is reproduced here once more.

%%% Figure showing aggregate speedup
\begin{figure}[htb]
  \sffamily
  \begin{center}
    \includegraphics[width=0.8\textwidth]{scalability/phase2_speedup_all}
    \caption*{\autoref{fig:ScalabilityPhase2SpeedupAll}: Speedup $S(n,p)$ of PSG for different combinations of $p$ and $\delta$ for all ISCAS circuits tested. The dotted line denotes the theoretical linear speedup $S(n,p)=p$.}
  \end{center}
\end{figure}

Speedup was found to depend somewhat on the degree of the interconnection network; however, this dependence does not fully correspond to the behavior predicted by the numerical analysis given in \cite{cantupaz00}.

The final conclusion is that PSG is a processor-efficient algorithm. The extension of the Selfish Gene Algorithm onto multiple processors gives users the ability to reduce execution time or increase solution quality.




\section{Discussion}
\label{sec:Discussion}

The main unanswered question is whether there is a correlation between the level of convergence and solution quality. Many PEA's display such a correlation, and it is often taken as an assumption when analyzing algorithms numerically \cite{back00,cantupaz00}.

PSG does not appear to exhibit such a correlation. In fact, the results of convergence-based speedup testing can neither confirm nor deny the hypothesis. Further research would be needed to analyze the dependence between convergence and solution quality for algorithms derived from the Selfish Gene Algorithm.

The uncertainty of this matter affects the assessment of the deterministic self-adaption schedule descibed in \autoref{sec:SelfAdaptionPSG}. Like the methods from which it is derived, this method assumes that the hypothesis holds and that there is a clear relation between convergence and solution quality. When the hypothesis cannot be confirmed, the mechanism's foundation is weakened.

It should also be noted that no comparisons were made between the self-adaption mechanism and any other methods of setting the mutation probability. An objective evaluation of the self-adaption strategy cannot be made until further research provides results of such a comparison.

PSG was compared head-to-head with a random search algorithm. The results of this comparison are less than favorable. The question why PSG was not able to outperform the random search algorithm remains unanswered. A hypothesis was stated that the lack of a performance gain was due to the limited execution time available for the experiment. However, further experiments would be needed to confirm this.

The last issue concerns speedup again. The degree of connectivity resulting in the highest values of speedup does not correspond to the value accepted as ``usually optimal'' by both experimental evaluation \cite{cao03} and numerical analysis \cite{cantupaz00}. More research would be needed to examine this issue in-depth. Of particular interest is the question to what extent the numerical analysis of general PEA's may be applied to the Parallel Selfish Gene Algorithm.

