\chapter{Introduction}
\label{chap:Introduction}

One of the most intriguing things about the field of computer science and engineering is the fact that its disciplines are intricately related and meet in various unexpected places. This work explores one such place, where evolutionary algorithms, parallel systems and VLSI design come together to form the Parallel Selfish Gene Algorithm, a parallel evolutionary algorithm based on the latest developments in modern evolutionary biology. This algorithm is used to solve the difficult problem of creating efficient test pattern generators for built-in self-test circuitry.

\section{Aim of the work}

The work stands at a crossroads between three major fields of science; unsurprisingly, the aim of the work is threefold. The first goal is to study and describe the state of the art in evolutionary algorithms and parallel evolutionary algorithms, in particular the Selfish Gene Algorithm, a lesser-known evolutionary algorithm that breaks away from its field by adopting a new and somewhat controversial interpretion of classical Darwinian evolution.

The second goal is to design and implement a parallel version of the Selfish Gene Algorithm, taking into account the special nature of the Selfish Gene Algorithm, as well as the constraints imposed by contemporary parallel systems. Of course, this implies the additional goal of thoroughly analyzing the algorithm's performance, scalability and efficiency.

The final aim is to utilize this algorithm to solve the problem of evolving cellular automata for use in the built-in self-test of digital circuits, again following the road of the lesser-known but potentially superior approach.


\section{Background}

The field of evolutionary computation is wide and diverse and has spawned, throughout its history, a host of research and algorithms. These algorithms, besides all being heuristic in nature, share one common characteristic: they attempt to exploit the principles of natural selection and population genetics to find quick and accurate solutions to difficult problems. One particular algorithm was created in 1998 and attempts to introduce some of the recent developments in modern evolutionary biology to the field of evolutionary computation. This algorithm is known as the Selfish Gene Algorithm.

The field of parallel systems and algorithms is a venerable discipline in the realm of computer science, with many academic as well as practical angles. Despite its age and status, the field is ever-changing, keeping abreast of modern developments in both hardware and software.

The synergy of these two fields results in parallel evolutionary algorithms. Unlike other parallel algorithms, parallel evolutionary algorithms are more than just evolutionary algorithms adapted to execute on multiple processors. In fact, their biological foundations may cause a hidden dimension to appear, by which parallel evolutionary algorithms exhibit unique behavior not found among other (parallel) algorithms.

In the field of VLSI design, the principle of built-in self-test (BIST) is based on the need to provide mechanisms by which a digital circuit may verify its functionality without the need for external testing. The success of BIST relies on a unit known as the test pattern generator, and the problem of creating and setting up good test pattern generators is a difficult one for which clever search algorithms are needed.



\section{Structure of the thesis}
The text is organized into eight chapters. After the brief introduction to the research areas given in this chapter, the next chapter delves into the field of evolutionary computation, introducing the overall concepts and also the Selfish Gene Algorithm. For the interested reader an overview of the algorithm's biological foundations is presented as well.

The third chapter addresses the field of parallel evolutionary algorithms in a similar way. This chapter also provides an overview of parallel systems and defines some of the metrics that are in use for analyzing parallel algorithms.

The Parallel Selfish Gene Algorithm (PSG) is introduced in \autoref{chap:PSG}. A detailed overview of the algorithm's structure and architecture is given in the first part, while the second part introduces the concept of self-adaption and shows how it may be used in an algorithm like PSG. Chapter \ref{chap:SoftwareDevelopment} describes the software development process used for implementing PSG.

Chapter \ref{chap:ProblemDomains} describes the problem domains that PSG was used with. The chapter opens with a well-known problem from graph theory and moves on to identify the issues concerning the built-in self-test of digital circuits and the generation of suitable test patterns. The so-called ``Cellular Automata Problem'' is then formally stated and defined.

Chapter \ref{chap:Experiments} sets the stage for a comprehensive set of experiments designed to analyze the performance of PSG from all angles. In particular, the algorithm is analyzed from the point of view of parallel systems, evaluating its speedup and scalability, and from the point of view of VLSI design, evaluating the algorithm's success at evolving test pattern generators for built-in self-test.

The final chapter is a place for review and reflection, drawing conclusions from the results of the work, and stating some of the open questions and suggestions for further work.


