%%Please change your runningheads for the {Book Title}{Chapter Title} 
%%at the \markboth command here %

\chapter{Genetic Algorithms}

\markboth{Book Title}{Chapter Title for Chapter~2 Headings}  %CHANGE HERE

\section{Introduction}
Our earlier emerging optimization techniques classification, which
differentiates between population-based strategies and adaptive memory
strategies, is often taken to be a fundamental distinction in the
literature. Population-based strategies manipulate a collection of 
solutions\index{solutions} rather than a single
solution\index{solution} at each stage.\index{stage} Genetic
algorithms, scatter search, path re-linking, and ant system 
approaches belong to this subclass of population-based strategies.

The ingenuity\index{ingenuity} of such methods in coordinating the
individual solutions contributions is the focus of parallel
processing\index{processing} methods.\index{methods} Consequently,
several population-based strategies turn out to be a subset of
parallel\index{parallel} processing methods.

Population-based strategies induce a pattern whose present state
depends on the past states,\index{states!present!past} hence
incorporate\index{incorporate} 
an {\it implicit memory\/} structure. The preservation of
previous choices is in a sense remembered by current choices, since
the present is inherited from the past. Genetic\index{genetic}
algorithms and scatter search approach are techniques, whose mode of
solution combination transmit\index{transmit} features of selected
past solutions to current solutions. They use no conscious
design\index{design} for keeping record of the past and no purposeful
strategy of comparing previous and currently anticipated states. We
therefore, conclude that genetic algorithms are based on {\it implicit
memory\/} rather than adaptive memory. Implicit memory does not take a
form normally viewed to be a hallmark of an intelligent memory
construction. Does genetic algorithm therefore, qualify as an emerging
optimization technique?  The answer is that genetic algorithms do not
strictly qualify as emerging optimization techniques\index{techniques}
because they do not exhibit adaptive memory structure, although they
can be said to have weak membership since they exhibit implicit memory
and since elements of adaptive memory can be included into it.

A number of factors also conspire to make the process difficult to
study experimentally. Molecular ions are difficult to prepare and
maintain at high concentrations, and they are particularly difficult
to prepare with a well-defined vibrational distribution. The ions
should further be brought to interact with electrons with a 
{\it known\/} velocity\index{velocity} distribution. Depending on the 
experimental technique, the production of neutral particles (beam
techniques) or the removal of charge (afterglow techniques, ion traps)
is monitored.

\subsection{Genetic algorithms versus traditional optimization 
and search techniques} Traditional search methods include such methods
as calculus-based methods, and enumerative methods. Calculus methods
search for extrema (maxima and minima) by equating the first
derivative to zero.\index{zero} Enumerative method uses a finite
search space or a discretised infinite search space to consider
objective function values at every point in the space one at a
time. The limitation of this method is that it is only effective in a
small search space. Traditional methods lack robustness because
\begin{enumerate}[(4)]
\item they are local in scope and the optima that they seek are the 
best in a neighborhood of the current point;

\item calculus method depends on the existence of derivatives; 

\item they depend on restrictive requirements of continuity, whilst 
many practical functions are discontinuous in nature;

\item traditional methods fail in cases where there are several minima 
and\break maxima as shown.
\end{enumerate}

The search techniques that cautiously exploits historical information
in order to speculate strings with higher potential of better
performance, i.e.~those approaching the optimal solution. Simply,
genetic\index{genetic} algorithms reach the solution\index{solution}
of a problem by generating and modifying a certain number of tentative
solutions so as to find the individual (i.e.~the solution) best suited
to a given environment (i.e.~the problem domain). A solution is
represented by a string of numbers or characters forming a so-called
{\it string}. A set of strings is referred to as a {\it solution
space}.  A random initialization of a population, the algorithm
proceeds in an iterative way through:
\begin{romanlist}[(iii)]
\item an evaluation of strings by the way of a score function with 
respect to an objective function of the problem; 

\item a selection of candidates and recombination; 

\item a generation of a new solution space from the old one through 
genetic operators of partial bits exchange and random bits exchange.
\end{romanlist}

In every generation of strings (strings of binary numbers, 
characters, etc.), a new set of strings (of integers, characters, etc.) is
generated using pieces/bits of the old strings and are tried for good
measure by using a predetermined evaluation criterion. The algorithm
stops when a given criterion is reached. Due to the particular way
genetic algorithms represent the problem solution (sequence of bits),
their use in combinatorial problems, such as scheduling, is quite
natural.\index{natural} A strategic decision\index{decision} 
must be made in terms of suitability of problem\index{problem} 
representation in genetic algorithms before it is used for
solving a combinatorial optimization problem.

\section{Fundamentals of Genetic Algorithms}
The procedure comprises two steps. The first step\index{step} results
in the creation of the top-level scenegraph hierarchy and cell
knowledge acquisition procedure. The nodes\index{nodes} in this
hierarchy encapsulate the facility\index{facility} properties, such as
the dimension, location, neighbors and intercellular
relationships. This step explores the cell components, determines
workstation groupings, and creates the top level of the job sequences
may look like the following:
\[
\begin{array}{ccccc}
2\qquad &3\qquad &5\qquad &4\qquad &1\\[2pt] 
4\qquad &1\qquad &3\qquad &5\qquad &2\\[2pt]
1\qquad &2\qquad &4\qquad &3\qquad &5\\[2pt] 
5\qquad &4\qquad &1\qquad &2\qquad &3
\end{array}
\]

Such solution spaces are usually generated at random but they do
represent a design or decision variable. Each string in the solution
space is evaluated in turn to find its score, known as string
score. The solution space is normally operated through three main
operators listed as follows:
\begin{enumerate}[(3)]	
\item Selection: selection of good strings to form an intermediate 
solution set of strings. This operator is sometimes called the
selection operator.  

\item Partial bits exchange: partial exchange of bits in the 
intermediate solution set.  

\item Random bit alteration: random alteration of bits in solution strings.
\end{enumerate}

From the partial bits exchange and random bit alteration operators, a
new set of solution space is obtained and is further evaluated and
tested for better performance. These operators are now discussed in
more details.

\subsection{Selection}
Selection is the random selection of copies of solutions from the
solution space, according to their score value, to generate one or
more new structures (roulette wheel method). The selection
operator\index{selection operator} is the first operator applied to a
solution space of strings. It involves the selection of individual
strings according to their objective function, $f$, which is referred
to as score.\index{score}

The function $f$, is a measure of goodness, profit,\index{profit}
validity, that we want to measure. In this way, the high quality
strings will be selected into the next generation. Since strings are
copied according to their objective function, or score, $f$, it means
strings with higher values\index{values} have a higher probability of
contributing one or more subsequent string in the next generation.

There exists a number of selection operators in genetic algorithm
literature, but in each case the essential idea\index{idea} is that
the above-average strings\index{strings} are selected and the copies
are inserted into the intermediate solution set in a probabilistic
manner.\index{manner} The commonly used selection operator is the
proportionate selection operator where a string is selected with a
probability proportional to its score. The $i$th string is 
selected with a probability $p_i$ proportional to $f_i$, 
$\binom{p_i}{f_i}$ thus, 
\begin{equation}	
p_i = \frac{f_i}{\sum\limits_{j=1}^n f_j}
\end{equation}
where $n$ is solution space size. Another selection criterion similar
to the one just described is the use of the expected count $e_i$ that
is a count of the expected number of copies in the next
generation. The expected count can be calculated as,
\begin{equation}	%2
e_i = \frac{f_i}{\sum\limits_{j=1}^n \frac{f_j}{n}} = \frac{f_i}{f_{\rm ave}}
\end{equation}
where $f_{\rm ave}$ is average score. Since $e_i$ is usually a real
number, it has a fractional part. The decimal part is then used as a
probability of having extra copies of that particular string. Having
selected strings for the intermediate solution set, the next operator
is partial bits exchange.

\subsection{Partial bits exchange}
Partial bits exchange operation is a random modification of a randomly
selected string. Its function is to guarantee the possibility of
exploring the space of solutions for any initial population so as to
permit\index{permit} a zone of local minimum to be abandoned during
the search. In selection, good strings are probabilistically assigned
a larger number of copies and an intermediate solution set is
formed. It is an important point to note\index{note} here that no new
strings are formed in the selection phase. In the partial bits
exchange operator, unlike in selection, new strings are generated by
exchange of information among strings of the intermediate solution
set. There are a number of partial bits exchange operators applied to
genetic algorithms.

This type of partial bits exchange operator is the commonly used
operator in the published genetic algorithm applications. Single
partial bits exchange operation takes place through three steps: 
\begin{enumerate}[Step~3:]	
\item[Step~1:] Two strings are picked at random from the 
intermediate solution set obtained from the selection phase;

\item[Step~2:] A common exchanging site, or a point of exchanging, 
is randomly chosen along the string;

\item[Step~3:] Exchange all bits on the right hand side of the 
exchanging site.
\end{enumerate}

The extreme case of the multi-point operator is called {\it the
uniform partial bits exchange operator\/} where a bit at any location
is chosen from either of the current string with a probability. This
operator appears to have great search power, and should be
incorporated in implementation.

\subsubsection{The bits exchange operator}
In order to preserve some good strings in the present solution space,
not all strings in the intermediate solution set are used in the
partial bits exchange operation.  A partial bits exchange operator is
mainly used for the search of new strings, and random bit alteration
operator is also used.

\section{Interior-Outer-Set Model}
Although we can develop some information diffusion techniques with
more high work efficiency to improve accuracy of the probability
estimate\index{estimate} from a small sample, we never eliminate the
imprecision of the estimate. In parametric statistical theory, the
interval\index{interval} estimation is suggested to quantify the
imprecision by selecting a region in the parameter space and specify
the probability that the estimated values of a set of parameters will
lie within the selected region. 

In the case that the size of $X_{in-j}$ is $n_j$, the most possible
probability that the event $x$ occurs in $I_j$ is $n_j/n$. Hence, we
can suppose that
\begin{eqnarray}
\pi_{I_j}(n_j/n)=1\,.
\end{eqnarray}

As already discussed, genetic algorithms candidate-solution, which is
a point in the search space is represented by a sequence of numbers
({\it bits\/}) and is known as a {\it string}. The potential of a
string being a solution is determined by its {\it score
function\/}\index{score function} which evaluates the string with
respect\index{respect} to the objective function of the optimization
problem under consideration. A randomly selected set of strings is
called a {\it solution space\/}\index{solution space} and the solution
space at a given time is called a {\it generation\/} or {\it
iteration}. The size of the solution space remains the same from
iteration to iteration and has been found to have a significant impact
on the performance of the genetic algorithm.

\begin{table}[th]      %Table~2.1
\def\p#1{\phantom{#1}}
\tbl{Processing times.}
{\tabcolsep6.5pt
\begin{tabular}{@{}ccccc@{}} 
\hline
{} &{} &{} &{} &{}\\[-1.5ex]
{} & \multicolumn{4}{c}{Jobs}\\
Machines & 1 & 2 & 3 & 4\\               
\colrule
1 & \p05 & \p09 & 9 & 4\\ 
2 & \p09 & \p03 & 4 & 8\\
3 & \p08 & 10 & 5 & 8\\
4 & 10 & \p01 & 8 & 7\\
5 & \p01 & \p08 & 6 & 2\\[1ex]
\hline
\end{tabular}\label{t2.1}}   
\end{table}

In order to have a good grasp\index{grasp} of the fundamental features
of genetic algorithms discussed so far, we work through an
example. Including the aggregate production planning-problem at this
early stage will put off new comers to genetic algorithms. As the goal
at this stage is to understand the fundamental principles of genetic
algorithms, we first use scheduling problem\index{problem} as an
example since it is easier to follow. So a sequence occupies a
solution string shown in Table~\ref{t2.1}. Then problem on aggregate
production planning is deferred toward the end of the chapter.

Let us apply our genetic algorithm to solve this problem of minimizing
the flowshop\index{flowshop} makespan. Since there are four jobs,
there is need to generate sequence of a job. For example, \{1, 2, 3,
4\} is a sequence.

To start off, we select an initial solution space. For the problem, we
choose a solution space size of 10, tossing a fair coin 40 times. Let
us make sure at this stage that we understand how the {\it objective
function values, score functions\/} and {\it expected counts\/} are
calculated from the string representation. Let us use the first
solution string for illustration purposes. The genetic algorithm
scheme tossed fair coins 5 times to obtain sequence \{4, 3, 1,
2\}. 

\begin{table}[th]      %Table~2.2
\def\p#1{\phantom{#1}}
\def\2p#1#2{\phantom{#1#2}}
\tbl{Solution space report from genetic algorithm.}
{\tabcolsep7.54pt
\begin{tabular}{@{}cccccccc@{}} 
\hline
{} &{} &{} &{} &{} &{}\\[-1.5ex]
No. & \multicolumn{4}{c}{String} & objvalue & score & expecc\\
\colrule
(1) & 4 & 3 & 1 & 2 & 54.0000 & 8.0000 & 1.5094\\ 
(2) & 4 & 3 & 2 & 1 & 55.0000 & 7.0000 & 1.3208\\
(3) & 1 & 3 & 2 & 4 & 56.0000 & 6.0000 & 1.1321\\
(4) & 1 & 3 & 2 & 4 & 56.0000 & 6.0000 & 1.1321\\ 
(5) & 1 & 3 & 2 & 4 & 56.0000 & 6.0000 & 1.1321\\
(6) & 1 & 3 & 2 & 4 & 56.0000 & 6.0000 & 1.1321\\
(7) & 1 & 3 & 2 & 4 & 56.0000 & 6.0000 & 1.1321\\
(8) & 3 & 4 & 2 & 1 & 58.0000 & 4.0000 & 0.7547\\
(9) & 3 & 1 & 2 & 4 & 58.0000 & 4.0000 & 0.7547\\
(10)\p0 & 2 & 1 & 4 & 3 & 62.0000 & 0.0000 & 0.0000\\[1ex]
\hline
\end{tabular} \label{t2.2}}
\end{table}

The objective function is obtained. We are only doing this so that
readers can follow the steps involved, otherwise, genetic algorithm
will use an objective value formulation included as a subprogram to
calculate the makespan for each sequence automatically, (see
Table~\ref{t2.2}). The solution space consists of ten sequences, their
objective junction values, score functions and expected counts.

The agent has strong preferences for trend data over the fluctuation
data in process of decision making. In other words, the trend data are 
much more significant for decision maker\index{maker} than the fluctuation
residue. It means that the selection of smoothing parameter for trend
identification by individual agent strongly affects their future
actions. 

The trend is much less stochastic than the fluctuation component in
time series. In most cases, during decision making
procedure\index{procedure} the agents take into account only trend
data and discard highly stochastic residue totally. The data for
decision making could be characterized by their complexity.

The time evolution of the isospin distribution in multifragmentation
for heavy-ion collisions at the energy studied we can draw the
neutrons diffuse much faster than protons so the number of neutrons
emitted much larger than that of protons at the beginning, and the
final isospin distribution is a result of dynamical balance of
symmetry\index{symmetry} potential and Coulomb force under the total
charge number conservation which leads to the ratios.

Let an ensemble $E$ have $C$ clusters $C^k$ $(k=1\cdots C)$ with $n_k$
individuals in $k$th cluster such that $\sum^c_{k=1}n_k=N$, where $N$
is the total number of individuals in the ensemble. For each cluster,
we can compute the group preferences using the vector addition method;
i.e.~$G^k =\sum_{i\in C^k} {\bf V}^i \cdot \hat {G}^k$ is
the normalized unit vector along $G^k$ such that
\begin{equation}	
\hat {G}^k_j =\frac{\sum_{i\in C^k} {\bf V}^i_j}{\sqrt{\sum^n_i 
(\sum_{i\in C^k} {\bf V}^i_j)^2}}\, .
\end{equation}

We can input the parameters which represent the set to see using the
pointing device.\index{device} These abstract sets of points become
vivid geometrical realities in virtual space.\index{space} This 
time the two interacting individuals, who do not have a memory of
their past conduct, can recognize the type of ethnic group of the
other individual. They do not know their personal history, neither
their personal\index{personal} penalty or ``image'' obtained by
encounters with other individuals. They only know, whether in the
recent past\index{past} some of the other group did not cooperate,
which penalty then clings to the whole group. For a general measure as
shown by the Table~\ref{t2.3}.

\begin{sidewaystable}
%\begin{table}[t]
\tbl{Accuracy of three compression techniques. We give the average 
difference between an original series and its compressed version,
using three difference measures; smaller differences correspond to more 
accurate compression.}
{\begin{tabular}{@{}l|ccc|ccc|ccc@{}}
\hline
{} &{} &{} &{} &{} &{} &{} &{} &{} &{}\\[-2ex]
{} &\multicolumn{3}{c|}{\bf Mean difference} &\multicolumn{3}{c|}{\bf
Maximum difference} &\multicolumn{3}{c}{\bf Root mean square
diff.}\\[0.6ex]
\hline
{} &{} &{} &{} &{} &{} &{} &{} &{} &{}\\[-2ex]
{} &Important &Fixed &Random &Important &Fixed &Random &Important
&Fixed &Random\\
{} &points &points &points &points &points &points &points &points
&points\\[0.6ex]
\hline
\multicolumn{10}{c}{\raisebox{0pt}[11pt][0pt]{\it Eighty percent 
compression}}\\[1ex]
\hline
{} &{} &{} &{} &{} &{} &{} &{} &{} &{}\\[-2ex]
Stock prices &0.02 &0.03 &0.04 &0.07 &1.70 &1.60 &0.05 &0.14 &0.14\\
Air temp. &0.01 &0.03 &0.03 &0.33 &0.77 &0.72 &0.03 &0.10 &0.10\\
Sea temp. &0.01 &0.03 &0.03 &0.35 &0.81 &0.75 &0.03 &0.10 &0.10\\
Wind speeds &0.02 &0.03 &0.03 &0.04 &1.09 &1.01 &0.04 &0.05 &0.05\\[0.6ex]
\hline
\multicolumn{10}{c}{\raisebox{0pt}[11pt][0pt]{\it Ninety percent
compression}}\\[1ex]
\hline
{} &{} &{} &{} &{} &{} &{} &{} &{} &{}\\[-2ex]
Stock prices &0.03 &0.06 &0.07 &1.10 &1.70 &1.70 &0.08 &0.21 &0.21\\
Air temp. &0.02 &0.05 &0.05 &0.64 &0.80 &0.78 &0.08 &0.16 &0.14\\
Sea temp. &0.01 &0.04 &0.05 &0.60 &0.83 &0.82 &0.07 &0.16 &0.14\\
Wind speeds &0.03 &0.04 &0.04 &0.06 &1.09 &1.03 &0.05 &0.06 &0.06\\[0.6ex]
\hline
\multicolumn{10}{c}{\raisebox{0pt}[11pt][0pt]{\it Ninety-five
compression}}\\[1ex]
\hline
{} &{} &{} &{} &{} &{} &{} &{} &{} &{}\\[-2ex]
Stock prices &0.05 &0.10 &0.12 &1.30 &1.80 &1.80 &0.11 &0.32 &0.30\\
Air temp. &0.03 &0.09 &0.08 &0.74 &0.83 &0.83 &0.12 &0.23 &0.21\\
Sea temp. &0.03 &0.08 &0.08 &0.78 &0.85 &0.85 &0.12 &0.23 &0.21\\
Wind speeds &0.05 &0.04 &0.04 &0.08 &1.09 &1.10 &0.07 &0.08 &0.08\\[0.6ex]
\hline
\end{tabular}\label{t2.3}}
\begin{tabnote}
The different parameters of the density distribution 
function for points, temperature, energy\index{energy} and
speeds.\index{speeds} The average reading comes from different
percentage. The readjustment process sustain exchanges long enough 
to maintain in the temperature and compression.
\end{tabnote}
\end{sidewaystable}

To obtain the vibration frequency by using the dynamic stiffness
matrix, we assume that the shape functions for the beam\index{beam} 
element are polynomials and we have to find the appropriate
coefficients. It is widely known that the exact terms will result, if
one uses the solution\index{solution} of the differential equation as
the shape\index{shape} functions, for the derivation of the 
terms\index{terms} in the stiffness matrix.\index{matrix}

Corresponding with these 4~sets there are 4~solutions $w_j$, $j =
1,2,3,4$, for $w(\zeta)_j$ and $w^\prime(\zeta)_j$, which are found
using the recurrence. Then, the holding actions will be
\begin{eqnarray}	
S(1,j) &=& \frac{EI}{L^3}\frac{d^3 w_j(0)}{d\zeta^3}\\[3pt]
S(2,j) &=& \frac{EI}{L^2}\frac{d^2 w_j(0)}{d\zeta^2}\\[3pt]
S(3,j) &=& - \frac{EI}{L^3}\frac{d^3 w_j(1)}{d\zeta^3}\\[3pt]
S(4,j) &=& \frac{EI}{L^2}\frac{d^2 w_j(1)}{d\zeta^2}\,.
\end{eqnarray}

The principle\index{principle} guarantees the existence of diffusion
functions to improve the diffusion estimates\index{estimates} when the
given samples\index{samples} are incomplete. It does not provide any
indication on how to find the diffusion functions.\index{functions}


