\chapter{Problem domains}
\label{chap:ProblemDomains}

One of the strengths of evolutionary algorithms is the fact that they can be used to solve a wide range of optimization problems. In general, adapting an evolutionary algorithm to solve a different problem involves only three steps:
\begin{enumerate}
	\item Defining the genome for the given problem. This includes setting the number of genes in the cromosome, the bit lengths, etc.
	\item Writing the fitness function. The fitness function is the algorithm's mapping from genotype to phenotype and links the abstract genetic domain with the concrete problem domain.
	\item Tuning the algorithm's parameters. Different problems have different characteristics, and settings that may work well for one problem might not work for another.
\end{enumerate}

In this chapter, we will describe the two problem domains that were implemented for the Parallel Selfish Gene Algorithm. The first is the \emph{Vertex Cover Problem}, a well-known problem from the realm of graph theory. The second problem is known as the \emph{Cellular Automata Problem}, and it is a real-world problem from the field of VLSI design.

\section{The Vertex Cover Problem}
\label{sec:VertexCoverProblem}
The Vertex Cover Problem is one of Karp's 21 NP-complete problems \cite{karp72} and is defined as follows:
\begin{quote}
A vertex cover for an undirected graph $G=(V,E)$ is a subset $C$ of its vertices such that every edge in $E$ has at least one endpoint in $C$.
The Vertex Cover Problem is an optimization problem with the goal of finding a vertex cover of minimal size.
\end{quote}

\subsection{Data structures for graphs}
Undirected graphs with $n$ vertices are supplied to the program as an adjacency matrix: a symmetric binary matrix $G[n \times n]$, where $G(i,j)=1$, iff there is an edge between $i$ and $j$. Internally, the program uses an adjacency list; after loading the adjacency matrix, the program converts it to an adjacency list, and this is the structure that is used in fitness evaluations.

\subsection{Definition of the genome}
In the Selfish Gene Algorithm, a problem domain is described by the number of genes, and the number of possible alleles for each locus. Intuitively, the number of genes equals the number of vertices in the graph, and the number of possible alleles is equal to 2 for each locus. This means that each locus can have two values: 0 or 1. A value of 0 at locus $i$ means that the $i$'th vertex in the graph is excluded from the vertex cover, a value of 1 means that it is included.

\subsection{Fitness evaluation}
Fitness evaluation is rather straightforward. An individual is described as an $n$-bit binary vector; from this we can construct subsets $C$ and $U$ of the graph. Subset $C \subseteq V$ is the set of vertices included in the vertex cover, and subset $U=V \setminus C$ is the set of vertices not included in the vertex cover.

For each vertex $v_c \in C$ we know that all edges with an endpoint in $v_c$ are ``covered,'' so no checking is needed. For each vertex $v_u \in U$ we have to check that all neighboring vertices are included in the vertex cover; in other words, that for each neighbor $v_n$ of $v_u$, $v_n \in C$. If this holds, the cover is valid and the fitness value is equal to $n-\left|C\right|$. If the cover is not valid, the fitness is set to negative infinity.

\subsection{Problem instances}
Two sets of problem instances were created for use with the algorithm. The first set of problems is a set of random graphs created according to the Erd\H{o}s-R\'enyi model. A MATLAB script was created based on the work of David Gleich \cite{gleich06}. The script creates graphs according to some parameters such as the number of vertices and the degree of connectivity.

The second set of problems was taken from \cite{dharwadker06}; it is a set of twenty interesting graphs specifically chosen for solving the Vertex Cover Problem.

All problem instances were simple text files representing an adjacency matrix.

\section{The Cellular Automata Problem}
\label{sec:CellularAutomataProblem}
The goal of the \emph{Cellular Automata Problem} is to evolve the optimal configuration of a cellular automaton for use in the \emph{built-in self-test} (BIST) of a combinational circuit. This problem is a lot harder than the Vertex Cover Problem, which is why it was chosen as the problem to be solved by the Parallel Selfish Gene Algorithm.

\subsection{Built-in self-test (BIST)}
\label{sec:BIST}
In integrated circuits, a built-in self-test mechanism is a function by which a circuit is able to verify its functionality and detect any logic faults that may occur. The basic principle of BIST involves a controller inside the circuit which generates a sequence of input vectors which are placed on the circuit's (external) inputs. The controller then checks if the circuit exhibits the expected behavior and raises a signal if any error is detected.

A crucial part of the design of a BIST mechanism is the choice of the circuitry responsible for generating the test vectors. This circuitry is knows as the \emph{test pattern generator} (TPG). Many different types of TPG have been developed \cite{fiser04}, the most popular being linear feedback shift registers (LFSR) followed closely by cellular automata (CA). The latter are described in-depth in \autoref{sec:CellularAutomata}.

There are various ways of testing a specific TPG in software. This generally involves applying the sequence of test vectors obtained from the TPG to a virtual representation of a benchmark circuit. Two approaches are popular: full fault-simulation and fault vector covering.

\begin{figure}[htb]
	\sffamily
	\begin{center}
		\includegraphics[scale=0.75]{miscfigs/tpg_full-fault-sim}
		\caption{Full fault-simulation method of TPG evaluation.}
		\label{fig:FullFaultSim}
	\end{center}
\end{figure}

\subsubsection*{Full fault-simulation}
\autoref{fig:FullFaultSim} shows the principle of full fault-simulation. The heart of this method is a piece of software called the \emph{fault simulator}. The fault simulator can load a benchmark circuit and introduce faults into it, mimicking the behavior of real hardware circuits that develop logic faults.

A series of test vectors is extracted from the TPG. These test vectors are given to the fault simulator; the fault simulator loads the circuit, introduces faults, and applies the test vectors to the circuit's inputs. It is then able to determine which of the introduced faults can not be detected by a BIST controller using this set of test vectors.

The result of the full fault-simulation method is that for any set of test vectors and any circuit, we are able to find the set of undetected faults. It stands to reason that when more and more test vectors are extracted from the TPG, the set of undetected faults becomes smaller and smaller. A common practice is to keep extracting test vectors until the set of undetected faults becomes empty. The number of test vectors necessary for achieving 100\% fault coverage is then used as a quality measure for the TPG.

\begin{figure}[htb]
	\sffamily
	\begin{center}
		\includegraphics[scale=0.75]{miscfigs/tpg_fault-vector-covering}
		\caption{Fault vector covering method of TPG evaluation.}
		\label{fig:FaultVectorCovering}
	\end{center}
\end{figure}

\subsubsection*{Fault vector covering}
Unfortunately, full fault-simulation is a very time-consuming affair, and so another approach called \emph{fault vector covering} is sometimes employed; the principles of this method are shown in \autoref{fig:FaultVectorCovering}.

The idea behind fault vector covering is that the costly fault simulation is performed only once for each circuit, producing some intermediate result with which we can evaluate many different TPG's quickly. This intermediate result is a set of fault vectors $V_F$ and is constructed as follows.

First, the fault simulator is employed in the usual way. A pseudo-random pattern generator (PRPG) is used as the TPG, and a fixed number of test vectors is extracted. Commonly, an LFSR is used as the PRPG in this step. The fault simulator loads the circuit and applies the vectors from the PRPG. The undetected faults returned by the fault simulator are known as \emph{random-pattern resistant faults} (RPRF) since they are the faults that remain undetected when an arbitrary sequence of (pseudo-)random test vectors is applied to the circuit.

In the second step, a piece of software known as the \emph{automatic test pattern generator} (ATPG) is used. For each fault in the set of RPRF's, the ATPG is able to calculate a so-called \emph{fault vector}. A fault vector $F \in V_F$ is a binary vector with \emph{don't-care} states: a $\{0,1,X\}^i$ tuple, where $i$ is the number of circuit inputs. When the non-$X$ symbols in the fault vector are applied to their respective circuit inputs, the fault will be detected.

The ATPG creates one fault vector for each of the RPRF's and collects them in $V_F$, the set of fault vectors. This set can be seen to represent the ``difficult'' faults of the circuit; if a TPG is able to produce test vectors corresponding to these fault vectors, all the RPRF's from step 1 will be detected. The problem of TPG evaluation is now reduced to the problem of matching test vectors with fault vectors.

A test vector $T$ from the TPG is said to ``cover'' a fault vector $F \in V_F$ if for every $k$, where $1 \leq k \leq i$, either $T_k = F_k$ or $F_k = X$. A given TPG may then be tested by taking a fixed number of test vectors from the TPG and determining how many of the fault vectors are covered by these test vectors. The number of uncovered fault vectors is used as a measure of the TPG's quality in a manner similar to the number of undetected faults in the case of full fault-simulation.

\subsection{Cellular automata}
\label{sec:CellularAutomata}
A cellular automaton \cite{wolfram94} is a system of cells composed in a grid. Each cell has a finite number of states. Time advances in discrete steps, and the state of each cell in the grid at time $t$ is determined by the states of some of the cells at time $t-1$.

Cellular automata come in all shapes and sizes. The kind of CA that is most commonly used as a TPG is known as the \emph{elementary cellular automaton}, which is a 1-bit CA (each cell has only two states) where the cells are arranged in a ring. The state of a cell at time $t$ is calculated according to the states of three cells at time $t-1$: the state of the cell itself, the state of its left neighbor and the state of its right neighbor. In other words, the state transition rule of the cell is a binary function of three variables. There are $2^{2^3}=2^8=256$ distinct rules, and each is identified by a number from 0 to 255 according to a scheme called the \emph{Wolfram code}.

\begin{figure}[htb]
	\sffamily
	\begin{center}
		\includegraphics[width=0.8\textwidth]{miscfigs/cellular-automaton}
		\caption[Cell structure of an elementary cellular automaton.]
		{Cell structure of an elementary cellular automaton. $S_k$ is the state of cell $k$, $R_k$ is the state transition rule, a function of $S_{k-1}$, $S_{k}$ and $S_{k+1}$.}
		\label{fig:CellularAutomaton}
	\end{center}
\end{figure}

\autoref{fig:CellularAutomaton} shows the cell structure of an elementary cellular automaton. In the diagram, the state of the $k$'th cell is denoted as $S_k$; the cell's state transition rule $R_k$ is a function of the cell's state and the neighboring cell's states: $R_k=f(S_{k-1},S_{k},S_{k+1})$. When the CA is used as a TPG, a test vector is constructed by concatenating the states $S_k$, where $1 \leq k \leq i$ at a given time $t$; in other words, each cell of the CA is connected to one circuit input. At time $t+1$, each state $S_k$ is recalculated by its rule $R_k$ according to the states $S_{k-1},S_{k},S_{k+1}$ at time $t$.

Many of the 256 distinct CA rules are equivalent to one another, and only a few of them are useful in constructing TPG's. The most important ones are \textbf{Rule 60}, \textbf{Rule 90}, \textbf{Rule 150} and \textbf{Rule 240}. In the CA implementation for the Parallel Selfish Gene Algorithm, only these four rules are available.

\subsection{Definition of the genome}
The genome for the Cellular Automata Problem is based on the definition from Corno et al.\ \cite{corno00}:
\begin{itemize}\compactlist
	\item For a cellular automaton of $i$ cells, the number of genes $n=2\cdot i$.
	\item For each cell, one locus is used for the CA rule and one locus for the cell's initial state.
	\item ``Rule'' cells can have four different allele values corresponding to the four important rules introduced in the previous section.
	\item ``Initial state'' cells can have two values corresponding to the binary nature of the 1-bit CA.
	\item The total number of alleles $\Sigma a = 2\cdot i + 4\cdot i = 3\cdot n$.
\end{itemize}

\subsection{Fitness evaluation}
Fitness values are calculated according to the fault vector covering method described in \autoref{sec:BIST}. A set of 1000\footnote{This particular value was selected as it has been shown to lead to good coverage when $100 \leq \left|V_F\right| \leq 150$, while keeping the fitness evaluations short.} test vectors $V_T$ is generated by the CA and compared to the set of fault vectors $V_F$. This is done by iterating through the fault vectors; for each vector $F \in V_F$, an inner loop checks if any vector $T \in V_T$ covers $F$. When any vector is found to cover $F$, the fitness value is incremented by $\left|V_F\right|^{-1}$ and the next fault vector is checked. This produces fitness values in the range 0--1.

The worst-case time complexity for one fitness evaluation is $O(\left|V_F\right| \cdot \left|V_T\right| \cdot i)=O(\left|V_F\right| \cdot n)$ (since $V_T$ is of constant size).

The final fitness value is a value in the range 0--1 indicating the percentage of fault vectors covered by this CA.

\subsection{Problem instances}

\begin{table}[hb]
	\sffamily
	\begin{center}
		\begin{tabular}{|l|l|l|l|}
			\hline
				\textbf{Circuit name} & \textbf{No.\ of circuit inputs $i$} & \textbf{No.\ of fault vectors $\left|V_F\right|$} & \textbf{Percentage of don't-cares} \\
			\hline
				\texttt{c17}			& 5			& 13		& 40\% \\
			\hline
				\texttt{c432}			& 36		& 112		& 51\% \\
			\hline
				\texttt{c499}			& 41		& 111		& 1.6\% \\
			\hline
				\texttt{c880}			& 60		& 132		& 75\% \\
			\hline
				\texttt{c1355}		& 41		& 104		& 1.5\% \\
			\hline
				\texttt{c1908}		& 33		& 121		& 49\% \\
			\hline
				\texttt{c2670}		& 233		& 146		& 83\% \\
			\hline
				\texttt{c3540}		& 50		& 121		& 79\% \\
			\hline
				\texttt{c5315}		& 178		& 123		& 89\% \\
			\hline
				\texttt{c6288}		& 32		& 94		& 27\% \\
			\hline
				\texttt{c7552}		& 207		& 146		& 72\% \\
			\hline
		\end{tabular}
		\caption{Problem instances constructed from combinational ISCAS'85 benchmark circuits.}
		\label{tab:IscasCombProblemInstances}
	\end{center}
\end{table}

Since the built-in self-test is a much-studied topic in VLSI design, a standard set of benchmarks known as the \emph{ISCAS'85} benchmark set is available \cite{iscas89} and is used by most researchers. In order not to overload the computing cluster, which is shared by many users, only the combinational circuits from this set were studied. For each benchmark circuit, the set of fault vectors $V_F$ was constructed as follows:
\begin{enumerate}
	\item Using the program \texttt{atalanta-m}\ \cite{watalanta}, originally developed at Virginia Tech \cite{lee93,lee96}, a list of logic faults was created by fault-simulating the circuit using an LFSR as the TPG. The LFSR's generating polynomial, as well as its seed, were random integers of $i$ bits generated using a Mersenne Twister pseudo-random number generator. 
	\item A set of fault vectors covering all faults was created, again using \texttt{atalanta-m}.
	\item The resulting set of fault vectors often had duplicate items, so in the last step, the set of fault vectors was sorted lexicographically, and duplicates were stripped. The final set of fault vectors $V_F$ was then written to a file and used as a problem instance for the Parallel Selfish Gene Algorithm. Note that only the file containing the fault vectors is needed: the algorithm has no knowledge of the actual benchmark circuit.
\end{enumerate}

Care was taken to ensure that the number of fault vectors was in the range 100--150 for all circuits in the benchmark set. However, for some ``easy'' circuits such as \texttt{c17} this was not possible, and for those circuits the set is smaller. For reference, the full set of combinational circuits in the ISCAS'85 benchmark set is given in \autoref{tab:IscasCombProblemInstances}, along with the number of circuit inputs $i$, the number of fault vectors $\left|V_F\right|$ and the percentage of don't-care symbols in the fault vectors. \autoref{fig:IscasCombProblemInstances} conveys this information in a graphical form.

\vspace{\parskip}

\begin{figure}[htb]
	\sffamily
	\begin{center}
		\includegraphics[width=0.8\textwidth]{miscfigs/bist_iscas-comb}
		\caption[Problem instances for the Cellular Automata Problem.]
		{Problem instances for the Cellular Automata Problem. Included are the combinational circuits from the ISCAS'85 benchmark set. In the graph, the number of circuit inputs is depicted, along with the number of fault vectors generated and the number of don't-care symbols in those fault vectors.}
		\label{fig:IscasCombProblemInstances}
	\end{center}
\end{figure}

\vspace{\parskip}

\subsection{Previous work}
\label{sec:PreviousWork}
The Parallel Selfish Gene Algorithm is not the first evolutionary algorithm solving the problem of evolving cellular automata for BIST design. In \cite{corno00}, Corno et al.\ used the Selfish Gene Algorithm to solve this problem, although their approach had some subtle differences from what was adopted for PSG. In their approach, they recognized the fact that certain combinations of CA rules \textbf{Rule 90} and \textbf{Rule 150} produce cellular automata with a maximal period, that is, one that traverses all possible $(2^i-1)$ non-zero states before returning to its initial non-zero state \cite{cattell95}. This type of CA is known as the \emph{90/150~LHCA}. The researchers ``pre-loaded'' the algorithm with the 90/150~LHCA and started the search in the neighborhood of the 90/150~LHCA. In contrast, the implementation of the Cellular Automata Problem in the PSG starts the search ``from scratch,'' without any prior knowledge.

Another difference is the fact that Corno et al.\ allowed all 256 CA rules to be used; the final difference is their use of fault-simulation for the fitness function, compared to the fault vector covering method used in PSG.

In their paper, the researchers showed that they were able to find cellular automata that detected more faults than the 90/150~LHCA, reaching full 100\% fault coverage for many circuits in the ISCAS'85 set.
