GENETIC ALGORITHM WITH CHEMOTAXIS
TUNABLE LOCAL SEARCHING
OPTIMIZATION
By
WEILl
Bachelor of Science
Changchun University
Science and Technology
Changchun, China
1982
Submitted to the Faculty of the
Graduate College of the
Oklahoma State University
In partial fulfillment of
the requirements for
the Degree of
MASTER OF SCIENCE
May, 2001
GENETIC ALGORITHM WITH CHEMOTAXIS
TUNABLELOCALSEARCfITNG
OPTIMIZATION
Thesis Approved:
" ThesIs Advisor
~ ~s H· ~~ ~~4..b.
~~L__,'_
Dean~a~
ii
ACKNOWLEDGMENTS
I would like to express sincere appreciation to the chairperson of my thesis committee,
Dr. Chandler, for his time and effort. He has provided helpful advice and encouragement
all through the various stages of the program. I would like to thank the other members of
my committee, Dr. Samadzadeh and Dr. Park, for their helpful comments and
suggestions. I would like to thank my family, my husband Jianping Lu, my daughter
Zhen Lu and my son Jeffrey Lu, for their encouragement of my aspirations~ their faith in
me never lagged.
III
Chapter
TABLE OF CONTENTS
Page
I. INTRODUCTION , 1
1.1 Principle of Genetic Algorithm 1
1.2 Principle of Chemotaxis 10
1.3 Principle of Simulated Annealing 12
1.4 Artificial Neural Networks 14
II. METHODOLOGy 19
2.1 Comparison of GA and CA 20
2.2 The Proposed Algorithm GADCA , 22
2.3 Case Studies and the Selection of Main Parameters 24
III. RESULTS AND DISCUSSION 25
3.1 Case 1 25
3.2 Case 2 49
IV. CONCLUSIONS '14
REFERENCES 56
APPENDIX A  PROGRAM LISTING 60
IV
LIST OF TABLES
Table Page
31 Training data for the lubricant viscosity at different temperature and
pressure 26
32 Comparison of the impact of using genetic diversity guidance for the
genetic algorithm (epoch =100) 30
33 Comparison of the impact of using genetic diversity guidance for the
genetic algorithm (epoch = 1000) 32
34 Comparison of the impact of using genetic di versity guidance for the
genetic algorithm (epoch = 2000) 34
35 Comparison of the genetic algorithm with diversity guidance (GAD) and
the genetic algorithm with diversity guidance combined with chemotaxis
(GADC) 36
36 Comparison of the genetic algorithm with diversity guidance (GAD),
chemotaxis algorithm (CA) and the genetic algorithm with diversity
guidance combined with chemotaxis (GADCA) 38
37 Influence of varying the parameters on the performance of GADCA .40
3S The influence of varying the number of neurons in the hiddenlayer to the
performance of GADCA ·12
39 Training result for the lubricant viscosity at different temperature
and pressure in Table 31 .43
310 Test data for the lubricant viscosity at different temperature and
pressure 46
311 Testing result forthe test data set in Table 310 46
312 Generalization data set .47
313 Generalization results for the data in Table 312 .48
v
314 Vapor pressure of water 50
315 Training results for the data in Table 314 52
316 Test data for water vapor at different temperatures 53
317 Testing results forthe data in Table 316 53
vi
LIST OF FIGURES
Figure Page
11 Initial population " ..4
12 Population after reproduction 6
13 Crossover 6
14 Population after crossover 7
15 Final population after mutation 8
31 Effect of the variation of population size on the objecti ve function value
(error) for pure genetic algorithm and genetic algorithm with diversity
guidance, respectively, when the epoch =100 32
32 Effect of the variation of population size on the objective function value
(error) for pure genetic algorithm and genetic algorithm with diversity
guidance, respectively. when the epoch = 1000 33
33 Effect of the variation of population size on the objective function value
(error) for pure genetic algorithm and genetic algorithm with diversity
guidance, respectively, when the epoch =2000 35
VII
r
CHAPTER 1 INTRODUCTION
One of the most fundamental problems in applied mathematics is that of optimization to
maximize or minimize a simple function. Consider as an example the function f(x) = 10
 (X_2)3. By differentiating f with respect to x, setting the derivative equal to zero, and
solving for x, one can generate a list of possible local extreme value for the function.
While all optimization problems can be viewed as an extension of this example, most,
unfortunately, cannot he solved so easily. In more typical applications, the objective
function has more than one variable.
Another complication is in the fact that many functions are not so easily defined or
differentiated. Not all functions can be written in terms of a mathematical expression,
and many complex functions are difficult or impossible to differentiate. In an attempt to
find other ways of solving these more realistic, less wellbehaved optimization problems,
other computational techniques have been investigated, some popular methods that show
some promise are the genetic algorithm [I, 2], the chemotaxis algorithm [3], the simplex
algorithm [4], the simulated annealing algorithm [5], etc. We are focusing on discussing
the principles of genetic algorithms and chemotaxis algorithms, since these two
algorithms are implemented in this thesis.
1.1 Principles of Genetic Algorithms
The genetic algorithm (GA) is a combinatorial optimizer that is domainindependent: it is
applicable to all functions that can be evaluated. The genetic algorithm requires only two
things: (1) a means of representing possible solutions and (2) an objective function
evaluator which is a function that maps a value from the domain of possible solutions to a
scalar value. The genetic algorithm starts with a computercreated population of
individuals, each representing a point in the search space of a given function. Using an
individual's objective function as a measure of how "fit" that individual is within its
environment, the genetic algorithm simulates nature's survival of the fittest, essentially
forcing the evolution of a nearly optimal creature. This early optimal creature is then the
approximate solution to the corresponding optimization problem.
The genetic algorithm has been implemented in various forms since its introduction in the
late of 1960s. As its name suggests, the first research done on geneticsbased algorithms
was not motivated by unsolved optimization problems. Instead, these algorithms were
designed as simulations of natural adaptive processes. Most researchers in the young
field of adaptationsimulation used models with properties closely resembling natural
phenomena. For example, the biological notions of diploid chromosomes and dominance
were both frequently mimicked by early algorithms. John Holland [6], a professor at the
University of Michigan, was one of the first researchers to carry out a substantial amount
of work in the field. He recognized the broad applicability of geneticsbased algorithms
for optimization purposes, and this insight formed the basis for the modern notion of a
genetic algorithm.
Despite its power, the genetic algorithm is both elegant and simple. That such a simple,
straightforward routine can accomplish so much is quite unexpected. The genetic
algorithm contains only one main data structure: a population of individuals. Each
individual, affectionately known as a clitter, represents an element within the domain of
the solution space of the optimization problem; i.e., each critter represents a possible
solution to the problem. The issue of how to best represent a critter is very complex and
has tremendous problemsolving implications. In the simplest genetic algorithm, critters
are simple strings of bits (binary digits: ones and zeros). Each string of ones and zeros is
called a chromosome; the chromosome of a given critter is the only source for all the
information about the corresponding solution. In biological terms, the chromosomal
string is the genotype and the solution it represents the phenotype of a particular critter.
Associated with each individual is a fitness value. The value is a numerical
quantification of how good a solution to the optimization problem the individual is.
Individuals with chromosomal strings representing better solutions have higher fitness
value, while lower fitness values are attributed to those whose bit strings represent
inferior solutions [7].
It is important to realize that only two elements of the genetic algorithm need to be
changed in order to apply the algorithm to a new problem: the representation of the
individuals and the objective functions. Consider, for example, one of the most basic test
problems the GA is applied to: One Max. The goal in One Max is to maximize the
number of occurrences of digit 1 in an arbitrarily long string of bits. As an example, let
us assume that strings are eight bits long. The representation of an individual is thus a
string of eight ones and zeros: 10U0001, for example. Standard GA terminology refers
to each bit position as a locus and to the values at the loci as aIJeles. The set of all
symbols which an allele can assume is called the alphabet of the representation. In our
examples, the alphabet consists of a and 1 [8].
3
Since the goal in One Max is to maximize the number of I bits, we need an objective
function evaluator which gives better ratings to individuals with more 1 bits. The
obvious choice is the function which assigns as an individual's fitness value the number
of ones in its representation; e.g., 10110001 has fitness four, while סס oo0000 has fitness
zero. The goal, then, of our algorithm is to find the individual with fitness value eight:
11111111.
Now that we have a suitable representation and an appropriate function, the construction
of the genetic algorithm is almost complete. One of the important parameters of any GA
is population size. which is how many critters are maintained at any given time. In our
One Max example, we will assume a population size of four; populations are typically
much larger, often 20 to 200. Since we intend to have four critters "alive" in the current
population at any given time, the GA must create four individuals to form the initial
population. In the GA, these initial individuals are merely random bit strings. Thus our
initial population might consist of the four individuals in Figure 11, where each Xi is a
critter in the population.
Critter's String Fitness Selection Probability
XI = 00101111 5 5/17
X2 = 00111010 4 4117
X, = 10111011 6 6/17
~ = 10000100 2 2/J7
Figure 11. Initial population.
4
Common sense tells us that some of the initial individuals probably are going to be better
than others. That is, some bit strings will score higher fitness values, meaning they are
better solutions to the One Max problem. Analogously, some of the critters in the initial
population will be better adapted to their environment. In nature, those individuals that
are better adapted are more likely to survive. Survival of the fittest is mirrored in the
genetic algorithm through reproduction. one of the three main genetic operators.
The GA thus creates a second generation of individuals. Since the population size must
remain constant, however, each new individual must replace an old one. The GA creates
a population of new indi viduals to replace the previous generation; in our example, the
GA would create four new individuals. Each new individual will be identical to a certain
previous generation. Specifically, the probability of an individual Xk in the first
generation reproducing is f(X0/Lf(XD.
We can thus list for each of the individuals in our initial population that individual's
fitness value and the probability of it reproducing, shown in Figure 11. To continue
with our One Max example, we will assume that X3 reproduces twice, that Xl and X2
each reproduce once, and that ~, the least fit individual, fails to reproduce, thus yielding
the new population depicted in Figure 12.
The next step of the GA distinguishes it from other domainindependent optimization
techniques. In this step, the crossover operator, which is the second main genetic
operator, is repeatedly applied to pairs of individuals. Suppose for example that critters
one and three are chosen to mate or to be crossed. This would leave critters two and four
to be crossed. The process of crossing two individuals involves randomly selecting a
locus and then swapping between the two individuals their genetic materials following

that locus. If in our example the crossover point selected for critters one and three were
the fourth locus, the resulting strings would be 10111111 and 00101011 shown in Figure
13. Likewise, if the sixth locus were selected as the crossover point for X2 and X4, the
individuals 10111010 and 00111011 would be formed.
Critter's String Fitness Selection Probability
XI = 10111011 6 6121
X2 = 10 111011 6 6/21
X3 = 00101 II 1 5 5/21
~=OOl1lO1O 4 4121
Figure 12. Population after reproduction.
Parents
101111011
001011111
Figure 13. Crossover.
Offspring
1O111111
00101011
One crossover thus creates two new individuals, called offspring; one containing the
beginning portion of the first individual followed by the ending portion of the second
individual, and another containing the beginning portion of the second individual
6
followed by the ending portion of the first individual demonstrated in Figure 14. After
some portion of the population is crossedover, we have a new population of individuals,
Critter's String Fitness Selection Probability
XI =10111111 7 7/21
X2 =10111010 5 5121
X3 = 00101011 4 4121
Xt =OOll1O11 5 5/21
Figure 14. Population after crossover (XI, X2, and X3, Xt)
each of which is either identical to an individual in the prior population or is the product
of genetic recombination through crossover. The significance of the crossover is
explained by Holland "the purpose of crossing strings in the genetic algorithm is to test
new parts of target regions rather than testing the same string over and over again in
successive generations." [1].
Before evaluating the new population, one final genetic operator is applied: mutation.
Mutation involves the flipping (switching 0 to 1 and vice versa) of alleles. A probability
Pm (which is usually rather low) is defined as the chance of any given allele being flipped.
In our One Max example, let us set pm = 0.05. Since there are four individuals, each with
eight loci, we would expect (4)(8)(Pm) =1.6 mutations to occur. We will say that two
mutations occur, in locus two of Xl and in locus seven of~. We thus have the resulting
critters 11111111 and 00111001.
7
After mutation, out new population is in its final state illustrated in Figure 15. The
fitness values of the new individuals are evaluated by the objective function, and the new
population is designated the current population, from which future generations will
derive. As long as the completion criterion is not met, the threestep process of
reproduction, crossover, and mutation is repeated. The completion criterion is generally
either a perfect solution or a predetermined number of generations. 10 our rather
simplistic One Max example, a fortunate sequence of events yielded a perfect solution
after only one generation. In a more realistic application, it would not be unusual for the
algorithm to continue for two hundred generations or more. When the algorithm does
conclude, it gives as its solution to the optimization problem the individual in the final
population with the highest fitness rating.
Critter's String Fitness
Xl=lllllill 8
X2 = 10111010 :"
X3 = 0010101] 4
~ = 00111001 4
Figure 15. Final population after mutation.
The repeated application of these three operators, each inspired by some aspect of natural
selection, can thus solve some optimization problems. The reasons for the effectiveness
of these operators are fairly clear. Building blocks (contiguous sequences of alleles)
8

which are beneficial to an individual are recombined through crossover with other
individuals' building blocks from different loci within the chromosomal string. Since
more fit strings are selected more frequently for reproduction and crossover, the more fit
building blocks will join to fonn better and better solutions. Mutation serves to
reintroduce diversity into the population, thus insuring that no alleles are lost. In our One
Max example, for instance, none of the original individuals contained a 1 at the second
locus. Mutation of the second allele in some individual was therefore necessary before
the perfect 11111111 chromosome could be produced [911].
While the GA has achieved some definite success, it has its limitations. Things are not so
simple that in order to solve any optimization problem, all we need to do is represent and
evaluate individual solutions. The first difficulty is that the computation of objective
fitness is nontrivial. It needs to be something a computer can do relatively quickly, since
thousands, even millions, of individuals will need to be evaluated in the process of
evolving better and better critters.
There are also many complications invol ved in the representation of indi viduals. If a
representation is not chosen carefully, there could easily fail to be a onetoone
correspondence between genotypes and phenotypes; i.e., between representation of
solutions to the problem and actual solutions. Careless representation schemes can also
nullify the effectiveness of the crossover operator; it is possible that crossover would no
longer serve to recombine useful parts of pairs of individuals, and even that crossover
could create a chromosome which does not represent a legitimate solution [12]. In the
processing of generating new generation from old generation using the three operators of
GA, we have a big chance of losing the best point (or chromosome). In order to
9

circumvent this problem, a method called elitism is adapted. Elitism first copies the best
point to new population. The rest is done in classical way. Elitism can very rapidly
increase performance of GA, because it prevents losing the best found solution.
1.2 Principle of Chemotaxis
In the fall of 1971 Max DelbIiick [13] gave a lecture at Berkeley that described the
peculiar behavior of chemotactic bacteria. They dash ahead in a more or less straight
line, then tumble all over themselves, then dash off in a seemingly random direction,
tumble again, etc. The dashes on which the concentration increases tend to be longer
than dashes in the "wrong" direction. Intuitively it is clear that the net effect is that each
bacterium migrates towards greater concentrations of the attractant. Professor Hans
Bremermann at Berkeley realized at once that the behavior reported by DelbIiick is
equivalent to the steps of an optimization algorithm that he had reported earlier [3]. In
both cases a maximum is sought, i.e. the maximum of a chemical concentration and the
maximum of a function, respectively. The details of the optimization algorithm,
however, vary greatly and there is very extensive literature. Many algorithms compute
the gradient of a function and then proceed in the direction of the gradient (steepest
descent). Some algorithms take successive directions to be orthogonal (conjugate
gradient methods) to avoid certain difficulties than arise in some cases when the
algorithms always follow the gradient. All these methods converge to local maxima or
minima [14].
The chemotaxis algorithm performs a randombased search to find a set of parameter
values which gives an objective function its lowest error. Two sets of parameters are
10
used, one set containing the values which have given the lowest error so far and a second
set containing updated parameter values. The updated value set is produced by
multiplying a random vector by a number, called the step size, and adding it to the lowest
error set. The errors produced by the two parameter sets are compared after each update.
If the updated set produces the lowest error, then it replaces the previous lowest error set.
The same random vector is then used for successive updates, until it produces an updated
set with a larger error. When an updated set produces a larger error, it is discarded and a
new random vector is generated. Chemotaxis can alter the rate of convergence to the
lowest error by altering the step size. If a particular random vector has produced a set of
parameters with a lower error a number of times, then the step size is increased, since the
direction on the error surface produced by the random vector is towards an area of low
error. Hence convergence speed is increased. If a number of different random vectors
have failed to produce a parameter set with a lower error, then the step size is reduced. It
is assumed that the lowest error lies within the region described by a circle about the
current lowest error, with radius given by the step size. Hence, by reducing the step size,
chemotaxis can converge approximately to the lowest error without overshooting it [15,
16]. The application of using chemotaxis could be further found in references J7  19.
The chemotaxis algorithm can be described as working in the following steps when it is
used to train a neural network:
Step 1. Initialize weights and biases of the network with small random values.
Step 2. Present the inputs to the network, and propagate data forward to obtain the
predicted output.
Step 3. Determine the objective function over the whole data set.
II
Step 4. Generate a random vector for changes of weights and biases.
Step 5. Increment the weights and biases with changes.
Step 6. Calculate the new objective function.
Step 7. If the latter objective function is an improvement on the former then retain the
modified weights and biases, and go to Step 5. If there has been no improvement then go
to Step 4.
1.3 Principle of Simulated Annealing
Even though the simulating annealing technique is not used in this paper, there exist
some similarities between Chemotaxis and simulated annealing. Publications based on
the simulated annealing or its hybridized with genetic algorithms could be found in
references [20  23J. Now I briefly introduce simulated annealing algorithm here, for
further reference, see references [24  26].
Annealing is a term from metallurgy. When the atoms in a piece of metal are aligned
randomly, the metal is brittle and fractures easily. In the process of annealing, the metal
is heated to a high temperature, causing the atoms to shake violently. If it were cooled
suddenly, the microstructure would be locked into a random unstable state. Instead, it is
cooled very slowly. As the temperature drops, the atoms tend to fall into patterns that are
relatively stable for that temperature. Providing that the temperature drop is slow
enough, the metal will eventually stabilize into an orderly structure.
Simulated annealing can be performed in optimization by randomly perturbing the
independent variables (weights in the case of neural network) and keeping track of the
best (lowest error) function value for each randomized set of variables. A relatively high
12
standard deviation for the random number generator is used at first. After many tries, the
set that produced the best function value is designed to be the center about which
perturbation will take place for the next temperature. The temperature (standard
deviation of the random number generator) is then reduced, and new tries done. The
algorithm is summarized as following [271:
1) Randomly generate an initial point S with a set of parameters.
2) Set the initial S to be the bestsofar point S*, thus S* =S.
3) Compute the cost of S, say C(S).
4) Compute the initial temperature To.
5) Set the temperature T = To.
6) While stop criterion is not satisfied do:
(a) Repeat M times:
(i) Select a random neighbor S' to the current S.
(ii) Set IJ.C =C(S')  C(S).
(iii) If(IJ.C) ~ 0 (downhill move):
• Set S = S'.
• If(C(S) < C(S*) then set S* =S.
(iv) If (IJ.C > 0) (uphill move):
• Choose a random number r uniformly from [0,1].
• Ifr < e'tJ.Cff, then set S =S'.
(b) Reduce temperature T.
How do we progress from the starting temperature to the stopping temperature? One
method is by multiplying by a constant factor each time. This factor is computed as
l3
Fausett[28] gives these
...
c = e In(stop/start)/(nl)
where start and stop are starting and stopping temperatures, and n is the number of
temperatures.
1.4 Artificial Neural Networks
Since the artificial neural network is used to test the proposed algorithm, it necessitates
the brief introduction of neural networks before we discuss any detail of the proposed
algorithm.
An artificial neural network (ANN) is an informationprocessing system that is based on
generalization of human cognition or neural biology.
assumptions in common between the two:
• Information processing occurs at many simple elements called neurons.
• Signals are passed between neurons over connection links.
• Each connection link has an associated weight, which, in a typical neural net,
multiplies the signal transmitted.
• Each neuron applies an activation function to its net input to detennine its output
signal.
A neural network is characterized by its particular:
• Architecture; its pattern of connections between the neurons.
• Learning Algorithm; its method of determining the weights on the connection.
• Activation function; which determines its output.
The processing elements considered in the definition of ANN are usually organized in a
sequence of layers, with full connections between layers. Typically, there are three or
14
more layers: an input layer where data are presented to the network through an input
buffer, an output layer with a buffer that holds the output response to a given input, and
one or more intermediate or hidden layers as shown in Figure 6 [29].
Input
vector
Input
layer
Hidden
layer
Neurons
Output
vector
Output
layer
Figure 1 6. Artificial Neural Network.
The operation of an ANN involves two processes: learning and generalization. Learning
is the process of adapting the connection weights in response to external stimuli at the
15
(1.1)

input buffer. The network "learns" in accordance with a learning rule governing the
adjustment of connection weights in response to learning examples applied at the input
and output buffers. Generalization is the process of accepting an input and producing a
response determined by the geometry and synaptic weights of the network.
Each hidden neuron provides an additive contribution to the input of the neuron with
which it is connected. The total input to a neuron is simply the weighted sum of the
separate outputs from each of the connected neurons plus a bias or offset tenn Sj :
ij(t) =LWij{t)ait) + Si(t)
j
where aj is current state of neuron j and each Wij is the weight of the connection between
neurons i and j. A positive weight is considered as an excitation and a negative weight an
inhibition.
It is necessary to have a rule which gives the effect of the total input on the activation of
the neuron. This rule j~ a function Fj which takes the total input ij(t) and current
acti vation ai(t) and produces a new value of the acti vation of the neuron i:
( 1.2)
Often, the activation function is a nondecreasing function of the total input of the neuron:
although activation functions are not restricted to nondecreasing function. Generally,
some sort of threshold function is used: a hard limiting threshold function, or a linear or
semilinear function, or a smoothly limiting threshold. A sigmoid (Sshaped) function for
this smoothly limiting function is often used, for example:
(1.4)
In all networks the output of a neuron is considered to be identical to its activation level.
lG

Network topologies are divided into the following groups [30]:
• Feedforward networks, where the data flow from input to output neurons is strictly
feedforward. The data processing can extend over multiple (layers of) neurons, hut
no feedback connections are present, that is, connections extending from outputs of
neurons to inputs of neurons in the same layer or previous layers.
• Recurrent networks, which do not contain feed back connections. Contrary to feedforward
networks, the dynamical properties of the network are important. In some
cases, the activation values of the neurons undergo a relaxation process such that the
network will evolve to a stable state in which these activations do not change
anymore. In other applications, the change of the activation values of the output
neurons are significant, with the dynamic behavior constituting the output of the
network.
The learning algorithm plays an important role in any NN. This is the process of
modifying the weights and biases to the neurons. Typically, we do not know what the
output space will look like in advance. The NN must be trained to classify certain data
patterns to certain outputs. In the process of training, the weights on the neural
connections change, and thus the output decision boundaries change during training. The
learning situations of NNs can be categorized in these two paradigms:
• Fixed weights, so that no learning occurs.
• Supervised learning or associative learning, where each input vector is associated
with a target output vector.
• Unsupervised learning or selforganization, where no target outputs are specified.
17
Typically, training is continued until a preset condition is met. This may be, for
example, minimization of a defined error function. One full pass through the training set
is termed an epoch. Sometimes training is performed until a set number of epochs have
been completed.
Training is performed on an NN so that it will correctly identify input patterns. By
training an NN we separate the output space into regions. Of course, the output space
will not only separate (classify) the input data patterns, but it will also separate data
patterns which it has not seen before. The ability of an NN to classify input data patterns
correctly that it has not seen before (has not been trained with) is termed generalization.
A net that has been overtrained will usually have poor generalization, since the output
space will follow the training data too closely.
The input patterns must be chosen so that they display the particular features one would
like the net to learn. They are prepared in an Ndimensional array which is fed into the
N input neurons of the input layer. It is important to limit the number of variable, used
in the input patterns, since the actual training of a neural network is very time
consuming. Finally one should make sure that the input variahles are normalized, to
avoid saturating the activation functions [31, 32].
18

CHAPTER II METHODOLOGY
During the past decades, the role of optimization has steadily increased in such diverse
areas as, for example, electrical engineering, operation research, computer science, and
communications [33]. Optimization problems are very important to production and our
daily life. In practice optimization problems become more and more complex. For
example, many large scale combinatorial optimization problems can only be solved
approximately on prescntday computers, which is closely related to the fact that many of
these problems have been proven to be NPhard [34]. Deterministic polynomial time
algorithms for their solution are unlikely to exist. The quality of the final solution is not
improved computation time. In some continuous optimization problems, the search for
an optimum of a function of continuous variables is difficult if there are peaks and
valleys, ruts and ridges. In these cases, traditional optimization methods are not
effective. They either become trapped in local minima or need much more search time.
In recent years, many researchers have tried to find some new ways to solve these
difficult problems. Stochastic approaches have attracted much attention [35].
Genetic algorithms (GA) and the chemostaxis algorithm (CA) are all stochastic
algorithms. Stochastic algorithms have some good characteristics. Many results have
been presented [36]. Although stochastic algorithms have been successfully used in
some difficult cases, there are still some problems. Based on the analysis and
applications of GA and CA, we propose a new stochastic algorithm called GADCA (GA:
19

genetic algorithm with eli versity guidance, CA: chemotaxis algorithm) which integrates
the advantages of GA and CA. It has high search speed and precision.
2.1 Comparison of GA and CA
A. The main features of a GA are summarized as:
1) GAs work from a population instead of a single state. The population evolves by
the use of operators such as crossover, mutation and so on.
2) Good individuals with a higher fitness value always have a better chance of
producing offspring. In contrast, bad individuals with low fitness value still have
a chance to reproduce.
3) The mutation operator can introduce some new infonnation into a generation.
The probability of escaping from local minima of a GA is higher than that of a
CA.
A GA is effective for many optimization problems, but it still has difficulties such as
premature convergence and evolving too slowly. Many advanced genetic algorithms
have been presented in the literature, but their complexity is also increased over
traditional genetic algorithms.
B. The key features of the CA are shown as follows:
1) The CA is very simple and easy to use.
2) The CA only accepts good states which have lower search cost. It can converge
rapidly, but it has more difficulty escaping from local minima than do GAs.
3) The CA uses Gaussianly (normally) distributed variables to generate new states,
so it is not suitable for optimizing discrete problems.
20
After analyzing the search process of stochastic algorithms we find that there are two
kinds of search in a stochastic optimization method. They are "directed search" and
"blind search". For example, in the search process some algorithms mainly accept new
states corresponding to a decrease in cost function. This kind of search is directed.
Sometimes the search process accepts bad states randomly; this kind of search process is
blind. "Blind search" enables the search process to escape from local minima.
Therefore, if these two kinds of search cooperate properly, the optimization algorithm
will have good properties of inheriting the advantages of genetic algorithm and
chemotaxis method, respectively. The combination can be made by generating some of
the new points by a genetic algorithm with diversity guidance (to be discussed in chapter
3) and some by the chemotaxis method. A point is a complete neural network structure
consisting of weights. The proportion of points is determined by following two equations
as the global optimum is approached:
Pc = k/km (2.1)
Pg =1Pc (2.2)
Where Pg is the proportion of the points generated by the genetic algorithm with diversity
guidance and Pc the proportion by the chemotaxis method. k is the generation sequential
number, and km is the maximum number of generations expected. From the beginning of
the search, a very low proportion of points are allowed to be generated by the chemotaxis
method, because their parents are far from the global optimum. As the search progresses,
the points gradually approach the global optimum and then a high proportion of points
generated by the chemotaxis method are needed to speed up convergence. Based on the
above analysis, we present a novel algorithm GADCA.
21
2.2 The Proposed Algorithm GADCA
A. The outline of GADCA
Step 1. Randomly initialize n points from the search space with equal probability.
Step 2. Calculate the objective function values of the n points.
Step 3. Sort the n points in the order of increasing objective function values, so that the
first point represents the best and the last point represents the worst.
Step 4. Each of the points is assigned a probability pi, i= 1, 2, 3, ... , n, giving a higher
probability to the points with lower function values and lower probabilities to those with
higher function values.
Step 5. Randomly select two different points from n points according to the probability
Pi·
Step 6. For each of the genes or weights, randomly select one value from the
corresponding two selected points to construct a new point.
Step 7. For each of the genes of the newly created point, generate a random number r, if
pn > r; then replace the value of that gene by another random number.
Step 8. Repeat k times Step 57 so that k new points are generated (steps 5  7 are
genetic algorithm steps).
Step 9. Randomly generate a point, multiply each gene of the point by a number called
step size (for example 0.01). Add each gene of the point to the corresponding gene of
the bestsafar point resulting in an updated point.
Step 10. If the updated point is better than the bestsafar point, keep the point randomly
generated and multiply each gene by the step size until the updated point is worse than
the bestsafar point. Add the updated point just before it fails into the new population.
22

Step 11. Repeat step 9 10 nk time's to obtain the size of the new generation is the same
size as that of its parents n (step 9 10 are chemotaxis algorithm).
Step 12. Calculate the objective function values for the newly created points.
Step 13. Sort the newly created points into ascending order.
Step 14. If the best point of the new generation is not better than the best one of the old
generation, then replace the worst point of the new generation by the best point of the old
generation and resort them. This step is to ensure that the current bestsofar point in the
community is always retained.
Step 15. Start from the nextbest point of the new generation and compare it with the
point in the same rank of the old generation. If the new point is better than the old one
and is further away from the bestsafar point, then keep the new one; then compare the
rest until they are all finished; go to Step 18; otherwise, go to Step 16.
Step 16. If the distance of the old point is further away from the bestsafar point and has
better fitness, then keep the old one and reject the new one and go to Step 15 to screen
others; otherwise, go to Step 17.
Step 17. If the distance of the new one from the bestsafar point dn times the objective
function value of the old one fo is greater than the distance of the old one do times the
objective function value of the new one fn (i.e., dn fo > do fn), then select the new one and
go to Step 15. Otherwise, generate a random number; if it is greater than 0.5, then keep
the old one and discard the new one and vice versa (introduction of diversity).
Step 18. Use the new population as a new generation, repeat Step 3 to Step 18 until either
a predetermined iterative number or an acceptable objective function value is reached.
B. The Features of GADCA
23

1) GADCA works from a population, which takes the advantage from GA. Search from
many states simultaneously is more efficient than search from a single point. It is
easier to find the global optimum.
2) GADCA should converge fast in terms of the combination of the CA. At very
beginning of the training process, the GA plays dominant role. When the search is
approaching the global minima, the CA starts functioning. In the CA portion, only a
decreased objective function value is accepted, which strengthens the local search
around the best state of the populations. It is helpful to find the global optimum.
3) GADCA is better than pure GA. It only needs a small population size due to the
introduction of the diversity shown from Step 14 to Step 17. This introduction of the
diversity dramatically reduces the memory space requirement for the storage of the
population.
2.3 Case Studies and the Selection of Main Parameters
In the investigation of GADCA, two cases in a variety of areas are used to verify the
reasonability, correctness and effectiveness of GADCA. In addition, the selection of
main parameters such as mutation probability Pm, step size s and population size m will
be studied. Their effect upon the performance of the GADCA will be explored. The
multilayer neural networking architecture is utilized to investigate the GADCA. In all
cases, the objective function (2:(Yi  xi)lI2j (number of data points  number of
parameters) is maintained to evaluate the performance of the network, where y is the
computed output, x the target output, and i = 0, 1, 2, 3 ,... , n. The program is written in
C++.
24

CHAPTER ill RESULTS AND DISCUSSIONS
The procedure described in chapter 2 reflects natural genetics in some respects. For any
animal species, the DNA chain of an individual is a mixture of the DNA chain of its
parents. Furthermore, fit parents are likely to produce fit offspring, and better performing
individuals have a better chance of surviving and producing more offspring than worse
ones. In any case, the individual with the best adaptation remains in the population at the
expense of the weaker individual, until an individual with superior adaptation replaces it.
The combination of genetic algorithm and chemotaxis searching takes care of both the
genetic algorithm, which makes the searching globally optimum, and of the chemotaxis
method, which converges quickly as it approaches the optimum. The following case
studies will demonstrate the ideas and features of the proposed algorithm.
3.1 Case 1. The first case is the application of the proposed algorithm to a chemical
engineering problem. The training data is listed in Table 31 [36]. The temperatures and
pressures are the input data for the neurons in the input layer. The logarithm of the
viscosity, measured at different temperature and pressure, is the target output for the
comparison of the computed output from the neuron in the output layer. According to the
analysis of the data, the neural network architecture consists of three layers with two
neurons in the input layer, three neurons in the hidden layer and one neuron in the output
layer. There exist nine weights and four biases in this structure. Unfortunately, there is
no report of trying to fit these data using a nonneural model. Otherwise, it would have
25


gIven a good reference for my investigation. The purpose of my investigation is to
compare the results of using simplest genetic algorithm, chemotaxis algorithm, and their
scientific combinations, not to find the best search method. There is no doubt that there
exit a lot of algorithms, such as damped Newton method [37] and quasiNewton method
[38], maybe resulting in better results. The number of neurons selected for in the hidden
layer may be optional. However, the number of total weights in the neural network must
be not larger than the number of data items in the training data set. Otherwise, an overfit
condition will occur. When the neural network is constructed of many hidden layers, it
creates not only a complicated network structure, but also slows the process of training
the neural network without enhancing the perfonnance. The objective function is (1:(Yixi)
1/2j (number of data points  number of parameters), where y is the computed output,
x is the experimental output which is the value in the last column in the Table 11. The
goal of training the neural network is to minimize the objective function value using the
proposed algorithm through adjusting the weights of the network.
Table 31. Training data for the lubricant viscosity at different temperature and pressure
[37].
Sample Temperature Pressure In(viscosity)
number (oe) (atm) (experimental)
1 0.0 1.0 5.106
2 0.0 740.8 6.387
3 0.0 1407.5 7.385
26

Table 31 continued.
4 0.0 363.2 5.791
5 0.0 1.0 5.107
6 0.0 805.5 6.361
7 0.0 3907.5 11.927
8 0.0 4125.6 12.426
9 0.0 2572.0 9.156
10 25.0 1.0 4.542
11 25.0 805.0 5.825
12 25.0 1505.9 6.705
13 25.0 2340.0 7.716
14 25.0 422.9 5.298
15 25.0 5064.3 11.984
16 25.0 5280.9 12.444
17 25.0 3647.3 9.523
18 25.0 2813.9 8.345
19 37.8 516.8 5.173
20 37.8 1738.0 6.650
21 37.8 1008.7 5.807
22 37.8 2749.2 7.741
23 37.8 1375.8 6.232
24 37.8 191. ) 4.661
25 37.8 1.0 4.298
27
Table 31 continued.
26 37.8 4849.8 10.811
27 37.8 5605.8 11.822
28 37.8 6273.9 13.068
29 37.8 3636.7 8.804
30 37.8 1949.0 6.855
31 37.8 1298.5 6.119
32 98.9 1.0 3.381
33 98.9 686.0 4.458
34 98.9 1423.6 5.207
35 98.9 2791.4 6.291
36 98.9 4213.4 7.327
37 98.9 2103.7 5.770
38 98.9 402.2 4.088
39 98.9 1.0 3.374
40 98.9 2219.7 5.839
41 98.9 6344.2 8.914
42 98.9 7469.4 9.983
43 98.9 5640.9 8.323
44 98.9 4107.9 7.132
..
3.1.1 Comparison of Using Diversity and without Diversity
Genetic diversity is very important for genetic algorithms. The loss of diversity means
premature convergence and failure to achieve the global optimum. Population size and
mutation probability can increase diversity and lead to global optimization at the expense
of slowing the procedure and taking more time. The proposed guidelines in the proposed
algorithm, such as a onecouple, onechild policy, can avoid to some extent the loss of
genetic diversity. A more efficient procedure is introduced by considering the distances
among the points to purge the unwanted candidates and maintain a certain degree of
diversity.
To measure diversity, the Euclidean distance between two points,
d = (L(Xi  Yi)ll2/(number of data points  number of parameters)
is used, where Xi and Yi are the ith values of the points x and y, respectively. Obviously,
the larger the value of d, the greater the distance between the two points. For example, d
= 0 implies the two points are identical, that is, there is no difference between them.
Thus, to keep one of them in the population is enough. When d is very close to zero, the
two points are almost identical; if they produce a new point, this new point must be very
close to their parents and is unlikely to bring much further improvement, unless they are
close to the global optimum. Therefore, the distance d from the bestsafar point can be
considered as a factor to save some of the promising candidates and improve the
perfonnance of the algorithm. Reference 27 illustrates the improvement of genetic
algorithm perfonnance in terms of the introduction of diversity based upon consideration
of distance between two points.
29
..
In order to compare the difference between the pure genetic algorithm and the genetic
algorithm with the introduction of diversity, the procedure for training the neural network
is carried out using the two algorithms, respectively. When the mutation probability pm =
0.01, different population sizes are used and the tenrunaverage bestsofar objective
function value is calculated for various numbers of objective function evaluations.
Tables 32  4 depict two attractive advantages of using diversity guidance against
without using diversity guidance for genetic algorithm. First, performance is different
when genetic diversity guidance is introduced. The efficiency of the genetic algorithm is
remarkably improved. Figures 31 to 3 show that objective function evaluation with
genetic diversity guidance produces a much better result than objective function
evaluation without genetic diversity guidance. In Figures 31 to 3, the vertical axis
represents the objective function values or errors, horizontal axis represents population
size. When the genetic algorithm with the diversity guidance is introduced, the objective
function value or error decreases dramatically with compared to without the introduction
of diversity guidance in all cases of different epochs.
Second, when genetic diversity guidance is used, the genetic algorithm prefers a smaller
population size, rather than larger size. When the population size is large enough, the
Table 32. Comparison of the impact of using genetic diversity guidance for the genetic
algorithm. Mutation probability pm = 0.01, population size m, Epoch = 100.
m a* b*
2 10.535 0.417
3 6.948 0.368
30
d
Table 32 continued.
4 3.147 0.245
5 2.360 0.239
6 2.344 0.235
10 1.148 0.190
20 0.428 0.098
50 0.340 0.107
80 0.293 0.162
100 0.280 0.197
a* : not using genetic diversity guidance; b* : using genetic diversity guidance.
31
Pure Genetic vs. with Diversity Guidance
(100 epochs)
•
+ pure genetic
 genetic with
diversity guidance
;~ 1
8 ~
~ 6·
4
2
a Jao....
o
......
20 40 60 80
T
100 120
PopJation Sjze
Figure 31. Effect of the variation of population size on the objective function value
(error) for pure genetic algorithm and genetic algorithm with diversity guidance,
respectively, when the epoch = 100.
Table 33. Comparison of the impact of using genetic diversity guidance for the genetic
algorithm. Mutation probability pm =0.01, population size m, Epoch =1000.
m a* b*
2 7.454 0.192
3 4.531 0.136
'.'
4 4.180 0.091
_._..
5 2.571 0.070

6 2.126 0.088
32

Table 33 continued.
10 0.959 0.095
20 0.570 0.112
50 0.280 0.131
80 0.278 0.141
100 0.263 0.150
II
a* : not using genetic diversity guidance; b* : using genetic diversity guidance.
Pure Genetic vs. Genetic with Diversity Guidance
(1000 epochs)
+ pure genetic
 genetic with
diversity guidance
100 120
T"l'
40 60 80
~ 1
6
5
I
0 t: 4
U.J
3
'")
.:..
1
0 I..
0 20
Population Size
Figure 32. Effect of the variation of population size on the objective function value
(error) for pure genetic algorithm and genetic algorithm with diversity guidance,
respectively, when the epoch =1000.
33

Table 34. Comparison of the impact of using genetic diversity guidance for the genetic
algorithm. Mutation probability Pm =0.01, population size m, Epoch = 2000.
m a* b*
._.
2 19.042 0.316
._
3 5.481 0.086
4 4.927 0.085
,
5 2.270 0.054
6 1.970 0.068
_ ..
10 0.878 0.082
20 0.452 0.095
50 0.290 0.128
80 0.274 0.140
100 0.268 0.143
a* : not using genetic diversity guidance; b* : using genetic diversity guidance.
34
Pure Genetic vs. Genetic with Diversity
(2000 epochs)
+ Pure genetic
.genetic with diversity
guidance
60 80 100 120
20
18
16
14
.... 12
0
t: 10
u:l
8
6
4
2
0 !
0 20
Population Size
Figure 33. Effect of the variation of population size on the objective function value
(error) for pure genetic algorithm and genetic algorithm with diversity guidance,
respectively, when the epoch =2000.
efficacy of the genetic diversity guidance is damped because a large population size can
contain almost every possible character. When epoch is given, the error increases beyond
a certain population size for genetic algorithm with diversity guidance. As we notice,
each point consists of the random generated parameters. The larger the population size,
the more the parameter variation is. The possibility of introducing larger parameters in
generating a new point also increases, as a result, the error enhances. That may be the
reason why traditional genetic algorithms need a very large population size. However, as
the search progresses, all points converge gradually to the global minimum. Not
considering diversity guidance can result in many identical or semiidentical points in the
35
population and slow down the approach to the global minimum. Therefore, no matter
how large the population size is, the introduction of diversity guidance can improve the
efficiency of the genetic algorithm.
3.1.2 Comparison of Genetic Algorithm with Diversity (GAD) and Genetic Algorithm
with Diversity Combined with Chemotaxis (GADCA)
For the same problem, set Pm = 0.01, and use equations 2.1 and 2.2 to control the
proportion of new points generated by the genetic algorithm and the chemotaxis method.
Table 35 shows clearly that a combination with the chemotaxis method can further
improve the efficiency of the pure genetic algorithm, especially when a more accurate
result is required. When the generation increases, the objecti ve function value decreases
in both cases of GAD and GADCA. However, the objective function value decreases
much faster for GADCA than that for GAD. This is because the genetic algorithm only
drives the points in the vicinity of the global minimum. The rest of the work may be left
for the chemotaxis method to finish.
Table 35. Comparison of the genetic algorithm with diversity guidance (GAD) and the
genetic algorithm with diversity guidance combined with chemotaxis (GADC), case 1, Pm
= 0.01, p= 5, s = 0.0001.
Tenronaverage, bestsofar objective value
Generations
50
100
GAD
0.392
0.305
36
GADCA
0.096
0.056
Table 35 continued.
200
400
600
1000
0.221
0.157
0.093
0.086
0.048
0.031
0.029
0.027
3.1.3 Comparison of Genetic Algorithm with Diversity Guidance (GAD), Chemotaxis
Algorithm (CA) and Genetic Algorithm with Diversity Guidance Combined with
Chemotaxis (GADCA)
For comparison, the GAD, CA and GADCA performances are conducted under different
generations when Pm =0.01. Table 36 shows that GADCA can gradually reach the
global minimum. As the generation grows, the probability of reaching the global
minimum is increased. Even though GAD converges gradually, it shrinks slower than
GADCA, which includes the chemotaxis algorithm. In contrast, chemotaxis working on
a single point converges as the generation increases; the speed of convergence is much
slower than GAD and GADCA. It could be rationalized that it lacks a global minimum
since it only works on a single point, the global minimum is not guaranteed. The
possibility of becoming trapped in a local minimum cannot always be avoided.
Meanwhile, for each generation only one step closer to the minimum could be obtained
resulting in a slower convergence since chemotaxis only works on single point for each
generation. On the other hand, both GAD and GADCA inherit the advantage of the
natural adaptation character of which the smaller the objective function value for a point
37

is, the higher the probability for the point to survive. For each generation, a betterfit
group of offspring is obtained for the whole population resulting in a faster step to the
minimum. The introduction of diversity in both algorithms produces the global
minimum.
Table 36. Comparison of the genetic algorithm with diversity guidance (GAD),
chemotaxis algorithm (CA) and the genetic algorithm with diversity guidance combined
with chemotaxis (GADCA), case I, Pm = 0.01, P = 5, s = 0.0001.
Tenronaverage, bestsofar objective value
Generations
50
100
200
400
600
1000
GAD
0.392
0.365
0.221
0.157
0.093
0.086
CA
0.270
0.249
0.246
0.228
0.197
0.156
GADCA
0.096
0.056
0.048
0.031
0.029
0.027
3.1.4 Sensitivity of the Parameters of GADCA
GADCA is quite a simple algorithm, and easy to perfonn; however, there are a few
parameters required. GADCA has three parameters of its own, the population size m,
mutation probability pm and the step size s. From the results obtained by varying the
38

population size on the peIfonnance of the pure genetic algorithm and the genetic
algorithm with diversity guidance, we can detennine that the population size should be
smaller when the OADCA is conducted. The mutation probability, which controls the
change of the genes after the new point is selected, should be appropriately selected,
otherwise, the performance of the proposed algorithm will be deteriorated. The step size
of chemotaxis used to modify the bestsofar point is conducted to obtain onestep close
to a better point than the bestsofar point. However, there is no step size introduced in a
genetic algorithm. The step size of chemotaxis algorithm will give rise to a very long
training time if it is very small. If the step size is very large it will cause convergence
failure. It is possible that the selection of parameters for a given algorithm may be
problem related. However, there should be some general guidelines.
To investigate the sensitivity of the parameters for the proposed algorithm, the three
parameters are used and the tenronaverage, bestsofar objective function values are
calculated. The results for 100 and 1000 epochs evaluations in Table 37 illustrates
following points.
1. The proposed algorithm generally is not very sensitive to the parameters. Therefore it
is robust, and may be applied successfully in many conditions.
2. When the mutation rate is 0.05 and other parameters keep constant, the proposed
algorithm yields the objective function value. It is evident that the proposed
algorithm peIforms better with a smaller mutation probability value. However, when
the probability is less than 0.01, the generations end prematurely due to lack of great
diversity of points.
39

3. It is observed that the proposed algorithm gives the best objective function value even
though the objective function values are not very significant when the population size
is varied.
4. The algorithm is relatively more sensitive to step size than the other two parameters
m and Pm. If s is extremely small, updating the bestsofar point will take many steps
to finish until it fails. It is detrimental to the efficiency of the algorithm. On the other
hand, if s is large, finding a better point to update the bestsofar point will be
impossible. Thus, the algorithm will be in efficient in terms of finding a better point
to replace the bestsofar point. In this case, when s = 0.0001, the algorithm presents
the best performance.
Table 37. Influence of varying the parameters on the performance of GADCA, case 1,
tenrunaverage, bestsofar objective function values.
Effect of varying mutation probability Pm for m =5, s =0.0001 on performance
Pm 0.01 0.05 0.10 0.20 0.30 0.50
100 epochs 0.056 0.049 0.064 0.073 0.074 0.076
1000 epochs 0.027 0.013 0.028 0.035 0.038 0.038
Effect of varying step size s for m =5, pm =0.05 on the performance
S 1.0 0.1 0.01 0.001 0.0005 0.0001
100 epochs 0.243 0.201 0.119 0.068 0.049 0.026
1000 epochs 0.096 0.060 0.039 0.027 0.022 0.021
40

Table 37 continued.
Effect of varying population size m for pm = 0.05, s = 0.0001 on the perfonnance
m 3 4 5 10 20 100
100 epochs 0.078 0.050 0.041 0.041 0.060 0.062
I
1000 epochs 0.045 0.023 0.011 0.017 0.018 0.020
3.1.5 The effective of vary'ng the Number of Neurons In Hiddenlayer on the
Perfonnance of GADCA
Further experiment is carried out when the number of neurons in the hiddenlayer is
varied. The neural network structures are 3:2:1, 2:2:1 and 2:1:1 (number of neurons in
the input layer: that in the hiddenlayer: that in outputlayer). The experimental result is
shown in Table 38. It is evident that the perfonnance of neural network is better when
the structures are 2:3: 1 and 2:2: 1 than that of 2: 1: 1. However, the standard deviation
increases somewhat when neural network structure is 2: 1: 1.
41
.....
Table 38. The influence of varying the number of neurons in the hiddenlayer to the
perfonnance of GADCA. Number of points =5, step size =0.0001, mutation probability
=0.05. A: neural network structure 2:3:1, B: neural network structure: 2:2:1 and C:
neural network structure 2: 1: 1 (number of neurons in the input layer: that in the hiddenlayer:
that in outputlayer).
Standard Deviation
Generation A B C
50 0.096 0.112 0.16
100 0.056 0.054 0.084
200 0.048 0.039 0.053
400 0.031 0.029 0.058
600 0.029 0.026 0.061
:
1000 0.027 0.023 0.06
II
I
3.1.6 Training Result of Data in Table 31 Using GADCA
Based upon the above discussion of the effect of varying the parameters on the
perfonnance of the proposed algorithm GADCA, the following parameters may be
suggested:
1. Population size m =5,
2. Mutation probability Pm =0.05,
3. Step size s =0.0001.
42
.....
The neural network architecture is still a threelayered structure, two neurons in the input
layer, three neurons in the hidden layer and one neuron in the output layer. There exist
six weights and four biases in the structure. The objective function is (L(Yi Xj)
2)lf2/(number of data points  number of parameters), where y is the computed output,
x is the experimental output. When the above suggested parameters are accepted, the
proposed algorithm yields objective function value (error) of 0.0065 after 6000
generations. The computed results are listed in Table 39. If more accuracy is required,
it is capable of utilizing more generations.
Table 39. Training result for the lubricant viscosity at different temperature and pressure
in Table 31.
Sample Temperature Pressure In(viscosity) In(viscosity)
Number (oC) (atm) (experimental) (computed)
1 0.0 1.0 5.106 5.113
2 0.0 740.8 6.387 6.365
3 0.0 1407.5 7.385 7.425
4 0.0 363.2 5.791 5.741
5 0.0 1.0 5.107 5.113
6 0.0 805.5 6.361 6.469
7 0.0 3907.5 11.927 11.892
8 0.0 4125.6 12.426 12.375
9 0.0 2572.0 9.156 9.323
10 25.0 1.0 4.542 4.603
43

Table 39 continued.
11 25.0 805.0 5.825 5.780
12 25.0 1505.9 6.705 6.715
13 25.0 2340.0 7.716 7.757
14 25.0 422.9 5.298 5.255
15 25.0 5064.3 11.984 11.945
16 25.0 5280.9 12.444 12.389
17 25.0 3647.3 9.523 9.514
18 25.0 2813.9 8.345 8.362
19 37.8 516.8 5.173 5.097
20 37.8 1738.0 6.650 6.610
21 37.8 1008.7 5.807 5.745
22 37.8 2749.2 7.741 7.737
23 37.8 1375.8 6.232 6.191
24 37.8 191.1 4.661 4.625
25 37.8 1.0 4.298 4.330
26 37.8 4849.8 10.811 10.481
27 37.8 5605.8 11.822 11.802
28 37.8 6273.9 13.068 13.183
29 37.8 3636.7 8.804 8.779
30 37.8 1949.0 6.855 6.847
31 37.8 1298.5 6.119 6.100
32 98.9 1.0 3.381 3.417
44
....
Table 39 continued.
33 98.9 686.0 4.458 4.395
34 98.9 1423.6 5.207 5.218
35 98.9 2791.4 6.291 6.344
36 98.9 4213.4 7.327 7.268
37 98.9 2103.7 5.770 5.827
38 98.9 402.2 4.088 4.019
39 98.9 1.0 3.374 3.417
40 98.9 2219.7 5.839 5.920
41 98.9 6344.2 8.914 8.845
42 98.9 7469.4 9.983 10.060
43 98.9 5640.9 8.323 8.250
44 98.9 4107.9 7.132 7.201
3.1.7 Testing the Neural Network Using GADCA
Normally, after a neural network has been trained, it is tested using another data set to
examine whether the neural network has been trained reasonably. The neural network
was tested using the test data set in Table 310. The test results are shown in Table 310.
The objective function value (error) is 0.013.
45
....
Table 310. Test data for the lubricant viscosity at different temperature and pressure
[37].
Sample Temperature Pressure In(viscosity)
Number (oC) (atm) (experimental)
1 0.0 1407.5 7.385
2 0.0 3907.5 11.927
3 25.0 1505.9 6.705
4 25.0 5280.9 12.44
5 37.8 1375.8 6.232
6 37.8 3636.7 8.804
7 98.9 2791.4 6.291
8 98.9 7469.4 9.983
Table 311. Testing result for the test data set in Table 310.
Sample Temperature Pressure In(viscosity) In(viscosity)
number (oC) (atm) (experimental) (computed)
1 0.0 1407.5 7.385 7.424
2 0.0 3907.5 11.927 11.892
3 25.0 1505.9 6.705 6.714
4 25.0 5280.9 12.44 12.388
5 37.8 1375.8 6.232 6.190
6 37.8 3636.7 8.804 8.778
46

Table 311 continued.
7
8
98.9
98.9
2791.4
7469.4
6.291
9.983
6.343
10.059
3.1.8 Generalization of the Neural Network Using GADCA
Keeping the same neural network architecture as that in training and testing procedure
and the suggested parameters, the neural network is extended to arbitrary data set in
Table 312. The generalization results are shown in Table 313.
Table 312. Generalization data set [37].
Sample Temperature Pressure In(viscosity)
number COC) (atm) (experimental)
1 0.0 1868.1 7.973
2 0.0 3285.0 10.473
3 25.0 1168.4 6.226
4 25.0 2237.3 7.574
5 25.0 4216.9 10.354
6 37.8 2922.9 7.957
7 37.8 4044.6 10.511
8 98.9 3534.8 6.726
9 98.9 4937.7 7.768
47
Table 313. Generalization results for the data in Table 312.
Sample Temperature Pressure In(viscosity) In(viscosity)
number (oC) (atm) (experimental) (computed)
1 0.0 1868.1 7.973 8.156
2 0.0 3285.0 10.473 10.619
3 25.0 1168.4 6.226 6.282
4 25.0 2237.3 7.574 7.627
5 25.0 4216.9 10.354 10.402
6 37.8 2922.9 7.957 7.932
7 37.8 4044.6 10.511 9.304
8 98.9 3534.8 6.726 6.837
9 98.9 4937.7 7.768 7.741
3.1.9 Conclusions for OADCA
From the above case study, some general conclusions can be drawn:
1. The genetic algorithm with diversity guidance is efficient, because it only needs a
relatively small size population. This guidance dramatically reduces the memory size
for storing the large population compared to when the pure genetic algorithm is
applied.
2. The combination of genetic algorithm with chemotaxis is reasonable and effective.
The effectiveness of the combination of genetic algorithm with chemotaxis can he
found by comparing its objective function value with those of genetic algorithm and
48
chemotaxis, respectively (Table 36). For instance, when the generation =100, the
objective function value for combination of genetic algorithm with chemotaxis is
0.328. However, the objective function values for genetic algorithm and chemotaxis
are 1.781 and 1.450, respectively. The rationale of the combination of genetic
algorithm with chemotaxis can be suggested by the applicability of this algorithm in
case 1. The similarity between the experimental viscosity and computed viscosity
from the neural network trained by the combination genetic algorithm with
chemotaxis method shown in Table 312 demonstrates that the proposed algorithm is
reasonable. For instance, when the experimental data for viscosity are 7.973, 10.473,
6.226, 7.574, 10.354 and 7.957, the computed data corresponding to the experimental
data are 8.156, 10.619,6.282,7.627,10.402 and 7.932.
3. The GADCA is tunable. By controlling the composition of the points 10 the
population, the ratio of the points generated by the genetic algorithm with diversity
guidance to those generated by chemotaxis is tunable. It can easily avoid a local
minimum, reach the global minimum efficiently, and converge quickly.
4. Carefully selecting the parameters for GADCA, especially the step size, can make the
algorithm more efficient.
3.2 Case 2. Application of GADCA for Water Pressure at Different Temperatures
The genetic algorithm with diversity guidance combined with chemotaxis (GADCA) is
extended to the determination of water pressure at different temperatures. For the
training data set in Table 313 [39], the neural network architecture is a threelayer
structure, one neuron in the input layer, two neurons in the hidden layer and one neuron
49
in the output layer. There are four weights and three biases in this structure. The
temperatures in Table 314 serve as the input data. The pressures in Table 314 serve as
the target data which are used to compare the difference between the computed data and
the experimental data. The objective function is (L(y!  x[)2)1/2/(number of data points number
of parameters), where y is the computed output, x is the experimental output.
Table 314. Vapor pressure of water [39].
Sample Number Temperature (ue) Pressure (mmHg)
1 10 9.2
2 J1 9.8
3 12 10.5
4 13 11.2
5 14 12.0
6 16 13.6
7 17 14.5
8 18 15.5
9 19 16.5
10 20 17.5
11 21 18.7
12 22 19.8
13 23 21.1
14 24 22.4
15 26 25.2
50

Table 314 continued.
16 27 26.7
17 28 28.3
18 29 30.0
19 30 31.8
20 31 33.7
21 32 35.7
22 33 37.7
23 34 39.9
24 35 42.2
Table 315 shows the training results for the data in Table 314. After 3000 epochs, the
objective function value (error) is 0.007. For the same manner as it was performed in
easel study, the neural network is also tested using the test data set in Table 316. Due to
the limited available data, there arc only two rows of the test data, but we still can see the
applicability of the proposed algorithm. Table 317 presents the testing results for the test
data in Table 316.
51

Table 315. Training results for the data in Table 314.
Sample Number Temperature te) Pressure (mrnHg) Pressure (mmHg)
(experimental) (computed)
1 10 9.2 9.2
2 II 9.8 9.8
3 12 10.5 10.5
4 13 11.2 11.2
5 14 12.0 12.0
6 16 13.6 13.6
7 17 14.5 J4.5
8 18 15.5 15.5
9 19 16.5 16.5
10 20 17.5 17.5
II 21 18.7 18.7
12 22 19.8 19.8
13 23 21.1 21.1
14 24 22.4 22.4
15 26 25.2 25.2
16 27 26.7 26.7
17 28 28.3 28.3
18 29 30.0 30.0
19 30 3L.8
20 31 33.7 33.7
52

Table 315 continued.
21
22
23
24
32
33
34
35
35.7
37.7
39.9
42.2
35.7
37.7
39.8
42.2
1
Table 316. Test data for Water Vapor at Different Temperatures [39].
Sample Number Temperature (uC) Pressure (mmHg)
1 15 11.8
25
Table 317. Testing Results for the Data in Table 316.
Sample Number Temperature (uC) Pressure (mmHg)
(experimental)
23.8
Pressure (mmHg)
(computed)
1
2
15
25
12.8
23.8
12.8
23.8

CHAPTER IV CONCLUSIONS
The genetic algorithm is a robust method for global optimization. However, the
traditional genetic algorithm requires a very large population size and is slow. The
Chemotaxis method works on only one point, so its drawback is the possibility of being a
trapped in a local minimum. The introduction of diversity in the genetic algorithm
dramatically reduces the population size without loss of global optimization. Based on
the ideas of the genetic algorithm with diversity guidance and the chemotaxis method, a
novel algorithm, a simple genetic algorithm with diversity guidance combined with
chemotaxis (OADCA) is proposed. From the case studies considered, GADCA
demonstrates the following unique advantages as compared to the traditional genetic
algorithm and the chemotaxis method.
1. Using the real variables in a certain range as weights simplifies the representation of
the traditional bitstring coding system. This simplification makes the genetic
algorithm easier to understand.
2. Introduction of Euclidean distance as the standard to keep a new point in a population
is crucial for the diversity of the population. By this method, the promising
candidates are always kept in the population for the next generation.
3. The Chemotaxis search method is adapted and combined with the genetic algorithm
naturally.
4. GADCA should be fast for searching for a global minimum since it inherits both the
advantages of the genetic algorithm and the chemotaxis method.
.'i4

5. The drawback of the OADCA is the large amount of computing time for many
iterations. Thus, there still exists room for further improvement of the proposed
algorithm.
55

REFERENCES
[1] Holland, J. H., "Genetic Algorithms", Scientific American, July, 1992, pp. 66  87.
[2] Goldberg, D. E. Genetic Algorithms in Search, Optimization, and Machine Learning;
AddisonWesley: Reading, MA, 1989.
[3] Bremennann, H. J. and Anderson, R. W., "An Alternative to Back Propagation: A
Simple for Synaptic Modification for Neural Net Training and Memory", Internal
Report, Dept. of Mathematics, University of California, Berkeley, 1989.
[4] NeIder, J. A. and Mead, R. A., "A Simplex Method for Function Minimization",
Computer. J., 7, 1965, pp. 308  313.
[5] Masters, T., Practical Neural Network Recipes in C++, Academic Press, 1993.
[6] Holland, J. H., Adaptation In Natural and Artificial Systems, University of Michigan
Press, Ann Arbor, 1975.
[7] Michalewicz, Z., Genetic Algorithms + Data Structures = Evolution Programs,
Spri ngerVerlag Berlin Heidelberg, 1996.
[8] Connen, T. H., Charles, E. L. and Ronald, L. R., Introduction to Algorithms,
McGrawHill, 1990.
[9] Davis, L., Handbook ofGenetic Algorithms, Van NostrandReinhold, 1991.
[lOJ Hibbert, D. A., "Genetic Algorithms in Chemistry", Chemom. Intell. Lab. Syst., 19,
1993, pp. 277  293.
56

[11] Lucasius, C. B. and Kateman, G., "On Kmedoid Clustering of Large Data Sets with
the Aid of Genetic Algorithms: Background, Feasibility and Comparison",
Chemom. Intell. Lab. Syst., 25, 1994, pp. 99  145.
[12] Reeves, C. and Wright, c., "Genetic Algorithms and Statistical Methods: A
Comparison", First IEElIEEE International Conference on Genetic Algorithms in
Engineering Systems: Innovations and Applications, lEE Conference Publication
No. 44, 1995, pp. 137  140.
[13] Adler, J., "Chemotaxis in Bacteria", Science, 166, 1969, pp. 1588  1597.
[14] MacNab, R. M. and Koshland, D. E., "The Gradientsensing Mechanism in Bacterial
Chemotaxis", Proc. Nat. Acad. Sci., 69, 1972, pp. 2509  2512.
[15] Keller, E. F. and Segal, L. A., "Model for Chemotaxis", J. Theor. Biol., 30, 1971,
pp. 225  234.
[16] Rosen, G. "Fundamental Theoretical Aspects of Bacterial Chemotaxis", J. Theor.
Biol., 41, 1973, pp. 201  208.
[17] Ferree T. c., Marcottee B. A., and Lockery S. R., "Neural Network Models of
Chemotaxis in the Nematode Caenorhabditis Elegans", Advances in Neural
Infonnation Processing Systems, Vol. 9, The MIT Press, 1997, pp. 55.
[18] Web B. "Robots and Crickets and Ants: Models of Neural Control of Chemotaxis
and Phonotaxis", Neural Networks, Vol. 11, No. 78, 1998, pp. 14791496.
[19] Koshland D. E., "Bacterial Chemotaxis as a Model Behavioral System, Press Raven,
1980.
57

[20] Ahmed M., T. Alkhamis, and M. Hasan, "Optimizing Discrete Stochastic Systems
Using Simulated Annealing and Simulation", Computers and Industrial
Engineering, 32, 1997, pp. 823836.
[21] Okada M., S. Hara, S. Komaki, and N. Morinaga, "An Application of Simulated
Annealing to the Design of Block Coded Modulation", IEICE Transactions on
Communications, E79b, 1, 1996, pp. 8891.
[22] Park M., and Y. Kim, "A Systematic Procedure for Setting Parameters in Simulated
Annealing Algorithms", Computers and Operation Research, 25, 1998, pp. 207217.
[23] Karaboga D. and Pham D. T., Intelligent Techniques, Spring Verlag, May, 2000.
[24] Aarts E. and. Korst J., Simulated Annealing Boltzmann Machines: A Stochastic
Approach to Combinatorial Optimization and Neural Computing, John Wiley &
Son Ltd, January, 1989.
[25] Lee, L. D., "Gynandromorphs", Master's Report, Oklahoma State University, 1963.
[26] Romeijn H., and R. Smith, "SimuJated Annealing for Constrained Optimization",
Journal ofGlobal Optimization, 5, 1994, pp. 101126.
[27] Bos, M., Bos, A. and Van Der Linden, W. E., "Processing of Signals from An £onselective
Electrode Array by A Neural Network", Analytica Chemica Acta, 233,
1990, pp. 31  39.
[28] Hornik, K., Stinchcombe, M. and White, H., "MutiJayer Feedforward Networks Are
Universal Approximators", Neural Networks, 2, 1989, pp. 359  366.
[29] Barnard, E. and Casasent, D., "Shift Invariance and the Neocognitron", Neural
Networks, 3,1992, pp. 403410.
58

[30] Gallant, R. and White, H., "On Learning the Derivatives of an Unknown Mapping
with Multilayer Feedforward Networks", Neural Networks, 2, 1992, pp. 129  360.
[31] Maren, A., Harston, G. and Pap, R., Handbook of Neural Computing Applications,
Academic Press, New York, 1990.
[32] Li, B. and Jiang, W., "An Efficient Algorithm for Complex Problems", IEEE
International Conference on Intelligent Processing Systems, Oct. 1997, pp. 703706.
[33] Carey, M. and Skiscim, c., Computers and Intractability: A Guide to the Theory of
NPCompleteness, San Francisco, CA: Freeman, 1979.
[34] Bui, T. N. and Jones, C., "Finding Good Approximate Vertex and Edge Partitions is
NPHard", Information Processing Letters, Vol. 42, 1992, pp. 153159.
[35] Esbensen, Hand Masumder, P., "SAGA: A Unification of the Genetic Algorithm
with Simulated Annealing and its Application to MacroCell Placement", Seventh
International Conference on VLSI DesignJanuary 1994, pp. 211314.
[36] Baughman, D. R. and Liu, Y. A., Neural Networks in Bioprocessing and Chemical
Engineering, Academic Press, Inc., San Diego, California, 1995, pp. 218  219.
[37] Yang, R. and Douglas, I., "Simple Algorithm with Local Tuning: Efficient Global
Optimizing Technique", Journal Optimization Theory and Applications, 98, 1998,
pp. 449  465.
[38] Wang, L., "The Damped Newton Method: an ANN Learning Algorithm",
M.S. Thesis, Computer Science Department, Oklahoma Sate University, 1995.
[39] Brenda, W. H., Chemindustry Experiments, University of Cincinnati, 1979.
59

APPENDIX A
PROGRAM LISTING
////////////////////11////////////////////////////111///////////////////11///////////11//1/////////11//1/////////////////
// Thesis Program //
// Title: Simple Genetic Algorithm with Chemotaxis //
// Tunable Local Searching Optimization //
// Name: Li, Wei //
// Institute: Department of Computer Science //
// Oklahoma Sate University //
// Date: January 8, 2000 //
////////////1//////////////////11////////11///////111////////111///////////111//////////////////////////////111//////////
//////////11///11//111/////////////1//////////////1//////////////////////////////////////////////////////////////////////1
I/This is a driving main. In this main, you have a variety /1
/Iof choices such as training, testing, generalizing your neural //
/Inetwork. Meanwhile, the two methods used to generate random //
lin umber with original distribution between 0 and 1 are defined //
llin this class. //
/1/1/1//1//1111/1////////////11/1/////1////////111/////1111//1/////1//////1/1//1///11///1//111///1111/111/1/1/1//1///1/1//
#include<iostream.h>
#include<stdlib.h>
#include<string.h>
#include<fstream.h>
#include<ctype.h>
#include<time.h>
#include<math.h>
#inc1ude "network.h"
void trainO;
void testO;
void generalizationO;
void mainO{
/1=============================================================//
IlThis is program drive method. In this method, a couple of //
/Ioptions are displayed on the screen for you to choose. They //
/Iare training, testing and generalizing your network. 1/
u=============================================================u
srand((unsigned)time(NULL»;
char tcts_gen;
60
cout«"This algorithm. demonstrates perfomance of ";
cout«"a new method combining the genetic"«endl;
cout«"a1gorithm. with chemotaxis, which yeilds If;
cout«"better solution than either that of genetic"«endl;
cout«" algorithm or that of chemotaxis algorithm."«endl;
cout«" In this program, you have three choices, "«endl;
cout«"they are pure genetic algorithm, ";
cout«"genetic algorithm with diversity,";
cout<<"chemotaxis algorithm"<<endl;
cout«" and genetic algorithm with chemotaxis.";
cout«endl;
cout«"Enter T' to train the network:"«endl;
cout«"Enter 'S' to test the network:"«end1:
cout«"Enter 'G' to generalize the network:"«endl;
cout«endl;
cin»tr_ts_gen;
tcts_gen =toupper(tcts~en);
switch(tcts~en){
case T':
cout«"Now you are training the network."«endl;
trainO;
break;
case'S':
cout«"Now you are testing the network."«endl;
testO;
break;
case 'G':
cout«"Now you are generalizing ";
cout«"the network."«endl;
generalizationO;
break;
default:
cout«"Please enter T, S or G.";
}
///1/111111111111111111111111111///////11111111///111///111111111111111111///1/111111111//////111111111111111111111111111111I
Iffhis train matad gives you the ways of training a neural II
Iinetwork. For the simplicity, there is only one method II
l/implemented in this class. II
1111/111///111111111111///11/1/111111111111///1111111111111111111///11///11111111111////11/1///11111111111111111111111111111I
void train(){
11============================================================11
IIIn this method, you are provided four options to train a II
Iineural network. They are pure genetic algorithm, simple II
Ilgenetic algorithm with diversity, chemotaxis and simple II
Ilgenetic algorithm with chmotaxis. II
6l
11=================================================11
int choose;
int i, check, pg, pc, num_oCpoints, iterations;
network: :geclayecinfoO;
network::gectrain_inputO;
network::geCtrain_outputO;
cout«"Enter the number of points: "«end!;
cin»num_oCpoints;
GACA gaca(num_oCpoints);
cout«n 1. pure genetic algorithm." «endI;
cout«n2. genetic algorithm with di versity. "«end!;
cout«"3. chemotaxis algorithm."«endl;
cout«"4. genetic algorithm with chemotaxis."«endl;
cin>>choose;
switch(choose){
case 1:
cout«"You have chosen pure genetic method."«endl;
cout«"How many iterations do you want?"«endl;
cin»iterations;
for(i=O; i<iterations; i++){
check =gaca.checkPointsO;
if(check=l){
cout«"When all the points are the same,";
cout«"the iteration number is: "«(i+l)«endl;;
break;
}
gaca.geneticAlgorithm(num_oCpoints);
gaca.nextGenerationO;
}
gaca.getPointsO.print_trainO;
break;
case 2:
cout«"You have chosen simple genetic method."«endl;
cout«"How many iterations do you want?"«end!;
cin»iterations;
for(i=O; i<iterations; i++){
check = gaca.checkPointsO;
if(check==l){
cout«"When all the points are the same, ";
cout«"the iteration number is: "«(i+l)«endl;
break;
}
gaca.geneticAlgorithrn(num_oCpoints);
gaca.competitionO;
gaca.nextGenerationO;
}
62
gaca.getPointsO·prinCtrain();
break;
case 3:
cout«"You have chosen chemotaxis method.";
cout«"Now, you are working on single point."«endl;
gaca.set_stepsizeO;
cout«"How many iterations do you want?"«endl;
cin»iterations;
for(i=O; i<iterations; i++){
gaca.chemotaxis(O);
gaca.competitionO;
gaca.nextGenerationO;
}
gaca.getPointsO.print_trainO;
break;
case 4:
cout«"You have chosen genetic algrithm";
cout«" with chemotaxis method."«endl;
gaca.secstepsizeO;
cout«"How many iterations do you want?"«endl;
cin»iterations;
for(i=O; i<iterations; i++){
check = gaca.checkPointsO;
if(check==1H
cout«"When all the points are the same ";
cout«"the iteration number is: "«(i+1)«endl;
break;
}
pc = num_oCpoints * i/iterations:
pg = num_oCpoints  pc;
gaca.geneticAlgorithm(pg);
if(pc>=1){
gaca.combineChemo(pc);
}
gaca.competitionO;
gaca.nextGellerationO;
}
gaca.getPointsO·prinCtrainO;
break;
default:
cout«"You enetered an invalid number.";
cout«"Enter 1, 2 or 3."«endl;
exit(l);
}
}//end of train
63
//1/11/1//////1/11/11//111//111////////111//111/11///11///111//11111/11/11/1///////11111///1111/111111////1111/1////111///
/ffhe test method is implemented to get the test result with //
I/a related error. 1/
//////1111/11///1111111//111////////1/111///////1//1//1//////11//1///1//1//11/11//1//1////11//11//1/1//11///1////1/////1//
void testO{
1/===========================================================11
//In this method, the test input files are put in and the //
//output files are also inputed. Meanwhile the minimum data //
//and the maximum data in the input training files are asked. //
lito normalize the input test files. The same way also is //
//for the output test files. //
//==========================================================11
network: :geclayecinfoO;
network: :geCtest_inputO;
network: :get_tescoutputO;
GACA gaca(l);
network net;
net = gaca.getPoints();
net.setup_weightsO;
net.calc_outputO;
net.calc_errorO;
net.prinCtestO;
}//end of test
111/1////////1/11///11///1///1111111111///11111111111///11/1/1/1///11//1/1111111//111//111/1111/1//1/1/1/11////1/1/1111111/1
/ffhe class generalization is implemented to get a series of 1/
Iloutput results. The generalization input files are inputed. /1
lIAs illustrated in test class, the minimum and maximum data 1/
I/in the train files are asked to input to normalized the II
llinput files. However, in this class, there is no output /1
Ilfile. /1
111/111/11111//1///1/111111111///1/111/1/111//111111111/11111/11111/111111/11111111111/11/1111111////11111/1/111//111/11///1
void generalizationO{
11============================================================/1
/11n this method, the weights obtained from the training the II
/Ineural network are inputed to set the neural network //
Ilparameters. The output results will be printed in a file. 1/
I1============================================================1/
network::geclayecinfoO;
network::gecgeneralization_inputO;
GACA gaca(l);
network net;
net =gaca.getPoints();
net.setup_weightsO;
net.calc_outputO;
net.prinCgeneralizationO;
64
}llend of generalization
11111111111111111///111/11/1/11/11/////11////11///111///1111/11///111//1//1////11//////1////1//1/11//1111/111/1//1//1////1111/
//Header file network.h 1/
///1111//111//1//1//11//1111111/////111111//1/1/1111/111111I111I11/11/111/111///1////1/1/11/1//11111111/111///11////1/11//11I
#include<iostream.h>
#include<stdlib.h>
#include<math.h>
#include<ctype.h>
#include<string.h>
#include<time.h>
//=============================================================~
/rrhis method is implemented to generate a series of random 1/
Ilweights for the neural network. These random weights are in a //
Ilcertain range of 20 and 10. The loop is used to avoid creating //
/Ithe same points with identical weights. //
//==========================================================//
double random_weightsO{
double rdNurn;
for(int i=O; i<1O; i++)
rdNum = double(randO/32767.0);
I/convert the random number to a value between 20 and 10
rdNum = 20.0 + rdNum * (10.0  (20.0));
return rdNum;
}llend of random_weights
~============================================================/1
Irrhis method is used to just generate a random number between 0 1/
I/and 1. For the same purpose as above method, the loop is used //
I/to avid creating two identical random numbers. II
~============================================================1/
double random_generatorO{
double rdNum;
for(int i=O; i<lO; i++)
rdNum = double(randO/32767.0);
return rdNum;
}llend of random~enerator
11111111/1111/11I111/11//111/1//111111/111//111111111/111111111111111/11111//II/II~/IIIII/IIII/IIIIIIIII//II/11111111111111111/
IIClass network represents a complete neural network II
Iistructure. In this class, primarily, a set of randomly II
/Igenerated numbers are used to set up the weights for the II
Iineural network. A series of method implementaions are II
Iidefined in this class. Their functionalities will be II
Ildiscussed when they are implemented. II
111111111111111111111111/11///111//1/11/1111/1111111111111111/111/1///1111111111/1111/111111111111//111111111/111//11/1/1//1111/
class network {
private:
Ilarray for a number fo layers
65
static int numLayer[5];
I/number of layers of the neural network
static int numOfLayers;
/Inumber of the weights in the neural network
static int numOfWeights;
//array of weights stores the individual weight for
I/the neural network
double weights[50];
/Inumber of the input data inputed
static int numOflnputData;
//array to store the input data
static double inputData[5][90];
I/array to store normalized input data
static double normlnputData[5][90];
//number of output data
static int numOfOutputData;
/Iarray to store output data
static double outputData[5][90];
/Iarray to store normalized output data
static double nonnOutputData[5][90];
//array to store final output computed by the neural
//network
double finaIOutput[5][90];
friend class GACA;
public:
networkO;
static void geclayecinfoO;
void initiaJize_weightsO;
void setup_weightsO;
static void gectrain_inputO;
static void get_tesCinputO;
static void get_generalization_inputO;
static void get_train_outputO;
static void gct_tescoutputO;
void calc_outputO;
void get_firsClayer_input(double tmpl[], int nm);
int calc_temp_out(double tmpl [], double trnp2[],
int nd, int nr2, int count, int last);
double segmoid(double val);
void calc_errorO;
void princtrainO;
void princtestO;
void princgeneraii zation();
int gecnurn_weightsO:
};
int network::numLayer[5];
66
int network::numOfLayers =0;
double network::inputData[5H90];
double network: :nonnInputData[5H90J;
int network: :numOfOutputData = 0;
double network:: outputData[5] [90];
double network::nonnOutputData[5][90J;
int network::numOfWeights =0;
int network::numOfinputData =0;
11==========================================================V
I/Default constructor for the class network. II
11=====================================================11
network::networkO{ }
11=====================================================II
Iffhe method is used to get input files and nonnalized the II
lIthe input data in the range of 0 and 1 to avoid II
Iisaturation of the data. II
11=========================================================11
void network::geclayecinfoO{
int i=O;
cout«"Enter the number of";
cout«"layers for the neural network: "«end!;;
cin»numOfLayers;
Ilput the number of neurons in the different layers
Ihnto array of numLayer
while(i<numOfLayers){
cout«"Enter the number of neurons in ";
cout«"layer" «(i+l)«":"«endl;
cin»numLayer[i];
i++;
}
i = 0;
while(i<numOfLaycrsl){
numOfWeights = numOfWeights+numLayer[i]*numLayer[i+1]
+numLayer[i+l];
i++;
}
Iltwo additional numbers of weight are for error
Iland probability
numOfWeights = numOfWeights + 2;
}llend of geclayecinfo
11===========================================================V
IIIn this method, the total number of weights in the neural II
Iinetwork is calculated and randomly generated weight is put II
lithe array of weights. Also the array of finalOutput is II
Ilcreated for storing the output computed by the neural II
~~~. V
67
11===========================================================11
void network::initialize_weightsO{
int i=O;
Ilput the random number in the array of weights
for(i=O; i<numOfWeights2; i++)
weights[i] = random_weightsO;
}llend of initialize_weights
11=============================================================~
Iffhis method is used for testing or generalizing the neural II
Ilnetwork. The weights obtained from training the neural II
Ilnetwork are kept in a input file. Then the weights in the II
l/input file are stored in the array of weights. II
11============================================================11
voi d network:: setup_weightsO {
char filename[80];
ifstream infile;
double data;
int i=O;
numOfWeights = 0;
Ilcalculate the total number of weights
while(i<numOfLayersl)(
numOfWeights = numOfWeights+
numLayer[i]*numLayer[i+1]+numLayer[i+1];
i++;
}
numOfWeights =numOfWeights + 2;
cout«"Enter the weight file name:"«enJI;
cin»filename;
infi Ie.open(filename, ios::i nlios: :nocreate);
i =0;
while(!infile.eofOH
infile»data;
weights[iJ=data;
i++;
}
infile.closeO;
}llend of setup_weights
~===========================================================11
Iffhe input data is stored in an array of inputData, then the II
Ildata in the array is normalized and put in the array of II
IlnormlnputData II
~===========================================================~
void network: :geCtrain_inputO{
ifstream infile;
double data, min, max;
char filename[80];
68
int i=O, j;
while(i<numLayer[O]) (
cout«"Enter the train input ":
cout«"file "«(i+1)«" name: "«endl;;
cin»filename;
Ilopen the input data files
infile.open(filenarne, ios: :inlios: :nocreate);
numOfInputData=O;
while(!infile.eofOH
infile»data;
Iistore the data in an array
inputData[i] [numOfInputData]=data;
numOfinputData++;
}
infile.closeO;
llfind the minimum and maximum for normalizing
lithe input data
min = max = inputData[i][O];
for(j=1; j<numOfInputData; j++){
if(inputData[i] [j]<min)
min=inputData[i][j] ;
if(inputData[i] [j]>rnax)
max=inputData[i][jJ;
}
IInormalize the input data and put it in an array
Ilof normlnputData
for(j=O; j<numOfInputData; j++)
norrnInputData[i][j] = 1.0/(maxmin)*
(inputData[i] [j]min );
normInputData[i][j] = min;
nonnlnputData[i][j+1] = max;
i++;
}
}llend of geCtrain_input
//============================================================//
Iffhe input test file is opened and stored in an array of II
IlinputData. Then the data in the array is normalized and II
Ilput in an array of normlnputData. II
11============================================================11
void network::geCtescinputO{
ifstream infile;
double data, min, max;
char filename[80];
int i=O, j;
while(i<numLayer[O]){
cout«"Enter the test input file name: "«(i+1)«endl;;
69
cin»filename;
Ilopen the input test file
infile.open(filename, ios: :inlios: :nocreate);
numOfInputData=O;
while(! infile.eofO){
infile»data;
IIput the data in the test file in
Ilan array of inputData
inputData[i] [numOfInputData]=data;
numOfInputData++;
}
infile.closeO;
Ilget the minimun and maximum data in the
Ilcorresponding training input file
cout«"Enter the min data n;
cout«"in the train data set:"«endl;
cin»min;
cout«"Enter the max data ";
cout«"in the train data setn«endl;
cin»max;
Iinormalize the test data
for(j=O; j<numOfInputData; j++)
norrnlnputData[i][j]=1.0/(maxmin)*(inputData[i] [j]min);
normInputData[i] [j]=min;
normlnputData[i](j+1]=max;
i++;
}
}llend of geCtesCinput
11===========================================================11
Irrhe generalization input test file is opened and stored in II
Ilan array of inputData. Then the data in the array is II
Iinormalized and put in an array of normlnputData. II
11============================================================11
voi.d network: :gecgeneralization_inputO{
ifstream infile;
double data, min, max;
char filename[80];
int i=O, j;
while(i<numLayer[O]){
cout«nEnter the generalization input file name: "«(i+l)«endl;
cin»filename;
infile.open(filename, ios::inlios::nocreate);
numOfInputData=O;
while(!infile.eofOH
infile»data;
inputDatali][numOfInputData]=data;
70
numOflnputData++;
}
infile.closeO;
cout«"Enter the min in the train data set"«endl;
cin»rnin;
cout«"Enter the max in the train data set:"«endl;
cin»max;
for(j=O; j<numOflnputData; j++)
normInputData[i) [j )=l.O/(maxmin)*(inputData[i)[i)min);
normlnputData[i)[j]=rnin;
nonnlnputData[i][j+ l)=max;
i++;
}
}llend of gecgeneralization_input
11===========================================================~
IfThe input data is stored in an array of outputData, then II
lithe data in the array is nonnalized and put in the array II
Ilof normOutputData II
~===========================================================~
void network: :geCtrain_outputO{
iJstream infile;
double data, min, max;
char filename[80];
int i=O, j;
while(i<numLayer[numOtLayers1 ]){
cout«uEnterthe output file name: u«(i+l)«endl;
cin»fi lename;
Ilopen file
infile.open(filename, ios: :inlios: :nocreate);
while(!infile.eofO){
infile»data;
Ilput the data into an array
outputData[i)[numOfOutputData)=data;
numOfOutputData++;
}
infile.closeO;
Ilfind the minimum and maximum in the output
Ilfile
min = max = outputData[i][O);
for(j=I; j<numOfOutputData; j++){
if(outputData[i) [j)<min)
min=outputData[i)[j];
if(outputData[i)[j]>max)
max=outputData[i)[j];
}
Ilnormalize the data
71
forU=O; j<numOfOutputData; j++)
nonnOutputData[i][j]=l.O/(maxmin)*
(outputData[i) [j]min);
nonnOutputData[i) [jJ=min;
nonnOutputData[i)[j+ 1)=max.;
i++;
}
}/Iend of geCtrain_output
11============================================================11
Iffhe output test file is opened and stored in an array of II
lIoutputData. Then the data in the array is nonnalized and II
Ilput in an array of nonnOutputData. II
11===========================================================11
void network: :geCtescoutputO{
ifstream infile;
double data, min, max;
char filename[80);
int i=O, j;
while(i<numLayer[numOfLayersl]){
cout«"Enter the output file name: "«(i+l)«endl;
cin»filename;
Ilopen file
infile.open(filename, ios::inlios::nocreate);
numOfOutputData=O;
while(!infile.eof()) {
infile>>data;
Ilput data into an array
outputData[i)[numOfOutputData]=data;
numOfOutputData++;
}
infile.closeO;
Ilget the minimum and maximum data in the
IIcorresponding training fi Ie
cout«"Enter the min in the train ";
cout«"output data set"«endl;
cin»min;
cout«"Enter the max in the train";
cout«" output data set"«endl;
cin»max;
Ilnonnalize the data
for(j=O; j<numOfOutputData; j++)
nonnOutputData[i) [j]= 1.O/(maxmin)*
(outputData[i )[j]min);
nonnOutputData[i] [j]=min;
normOutputData[i][j+ 1)=max;
72
i++;
}
}llend of get_test_output
V========================================================II
Irrhis method is used to calculate the output of the neural V
Vnetwork. Two other method are called for the V
Vcalculations. Their functionalities will be discussed II
//later. /I
V=========================================================//
void network::calc_outputO{
int h, i, j, k, m, n, weight_count, lasclayer;
n=O;
i=O;
h=O;
k=O;
/larray temps are used to store temperaly data
/lcalculated by the neural network
double tempi [20], temp2[20];
while(k<numOfinputData) {
weighccount=O;
/lput the data in the first layer into the array
/1of tempi
gecfirsClayer_input(temp 1, k);
for(j=I; j<numOfLayers; j++) {
lasc1ayer=j;
/lcalculated the output in the consecutive layer
/land put them into array of temp2
weighCcount=calc_temp_out(temp1, temp2, numLayer[j I],
numLayer[j], weighccount, lasclayer);
/lcopy the data in temp2 into tempI
/lfor next layer calculation
for(m=O; m<numLayer[j]; m++)
tempI [m]=temp2[m];
i++;
//put final result computed by the neural network
l/into array of finalOutput
for(n=O; n<numLayerlnumOfLayersI]; n++){
finaIOutput[n][k]=temp 1[n];
}
k++;
}
}/lend of calc_output
11=========================================================//
Irrhis helper method is used to get the data in the /I
//normInputData in a temperary array of tmpl. II
73
V=========================================================II
void network::get_first_layer_input(double tmpl[], int nm){
int i;
for(i=O; i<numLayer[O]; i++)
tmpl[i] = nonnInputData[i][nm];
}I/end of get_firsClayer_input
V=========================================================11
Irrhis helper method is used to calculate the consecutive II
Illayer output and put it into a temporary array of tmp2. II
11=========================================================1/
int network::calc_temp_out(double tmpl[], double tmp2[],
int nr1, int nr2, int count, int last) {
int i, j;
double value;
for(i=O; i<nr2; i++){
value=O.O;
//calculate the output in a consecuti ve layer
for(j=O; j<nr1; j ++)(
value+=tmpl [j]*weights[count];
count++;
}
value = value+wcights[count];
count++;
Ilthis output should be between 0 and 1
if(last!=numOtLayersl)
tmp2[i]=segmoid(value);
//last layer should be linear without using
Ilsegmoid function
else
tmp2[i]=value;
return count;
}llend of calc_temp_out
11==========================================================11
Irrhis helper method is to get the output in a consecutive II
//layer in the neural network. II
11==========================================================11
double network::segmoid(double val){
double output;
output = l/(l+exp(val);
return output;
}Vend of segrnoid
11==========================================================11
Irrhis method calculates the error between the computed II
Ilresults by the neural network and the result from the /I
lithe input file. II
74
11==========================================================11
void network: :calc_errorO{
int i, j;
double sum=O.O;
double stdDev;
Ilcalculate the error
for(i=O; i<numLayer[numOfLayersl]: i++)
forO=O; j<numOfOutputData: j++)
sum += (norrnOutputData[ilU]finaIOutput[i)[j])*
(norrnOutputData[i] (j]finaIOutput[i] [j]);
stdDev = sqrt(sum);
weights[numOfWeights2]=stdDev;
}llend of calc_error
~=========================================================11
Irrhis method is implemented to denorrnalize the final data II
Ilcomputed by the neural network. The denorrnalized adta II
Ilis printed out. II
~=========================================================~
void network: :prinCtrainO {
ofstream outfile;
int i, j;
double data;
Ilopen an output file
outfile.open(" train .dat", ios: :out);
for(i=O; i<numLayer[numOfLayersl]; i++){
for(j=O; j<numOfOutputData; j++){
Iidenorrnalize the data
data = (normOutputData[i][numOfOutputData+L]normOutputData[
i][numOfOutputData])*
finalOutput[i] [j]+normOutputData[i]
[numOfOutputData];
outfile«data«" ";
}llend_for
}llend_for
outfile«endl;
Ilprint out weights
outfile«"The weights are: "«endl;
[or(i=O; i<numOfWeights2; i++){
data=weights[i];
outfile«data«" ";
}
Ilprint out error
outfile«endl;
outfile«"The standard deviation is:"«endl;
data = weights [numOfWci ghts2];
outfile«data;
75
outfile.closeO;
}llend of prinCtrain
~========================================================II=
l!This method is implemented to denonnalize the final data ~
I/computed by the neural network for the test. The ~
Ildenormalized adta is printed out. ~
11=========================================================~
void network: :prinCtestO{
ofstream outfile;
int i, j;
double data;
~open output file
outfile.open("test.dat", ios::out);
outfile«HThe final outputs are: "«endl;
for(i=O; i<numLayer[numOfLayersl]; i++){
forU=O; j<numOfOutputData; j++){
data = (nonnOutputData[i][numOfOutputData+ 11normOutputData[
i][n umOfOutputData])*
finalOutput[i] [j]+nonnOutputData[i]
[numOfOutputData];
outfile«data«" H;
}
~print the error
outfile«endl;
outfile«"The standard deviation is: "«endl;
data = weights[numOfWeights2];
outfile«data«endl;
outfile.close():
}~end of princtcst
~=========================================================~
l!This method is implemented to denormalize the final data ~
~computed by the neural network for the generalization. ~
l!The the denormalized data is printed out. ~
11=========================================================1/
void network: :princgeneratization0{
ofstream outfile;
int i, j;
double data, max, min;
Dutfile.open("gen.dat", iDS: :out);
~get the minimum and maximum data in the
/Icorresponding train file
cout«"Enter the min in the ";
cDut«"train output data set"«endl;
cin»min;
cDut«"Enter the max. in the ";
76
cout«"train output data set"«endl;
cin»max;
Ilopen output file
outfile«"The final outputs are: "«endl;
Ildenonnalize the data
for(i=O; i<numLayer[numOfLayersl]; i++){
forG=O; j<numOfInputData; j++){
data = (maxntin)*finalOutput[i][j]+ min;
outfile«data«" ";
}
}
outfile.closeO;
}llend of princgeneralization
v======================================================11
IfThe method is implemented to get the number of total II
Ilweights in a neural network. II
11=====================================================11
int network::gecnum_weightsO{
return numOtweights;
}/Iend of gecnum_weights
/111/1/111//111///1///111//111/111/1/11/111///111/1///1111////11111111/////111111111/1/11111/111/1/1111/11111111111111
IIClass GACA is to generate a couple of networks called II
Ilpoints. In this class, the all algorithms will be II
IIperformed. For individual algorithm, it will be II
Ildiscussed when it is implemented. II
1111111/111/111///11/1/1/1111///111//111//1111/111/1/11111/1/1//11111/11111/1/111111/1/1/11111111//11///111111111111111
class GACA(
private:
Iia couple of points
network ntwk[lOO];
Ila couple new points
network newNtwk[lOO);
Ilnumber of points
int numOfPoints;
Iltwo points
network twoPoints(2);
Iione point
network cross;
Ilanother one point
network chemo;
/lfor chemotaxis
double stepSize;
public:
GACA(int points);
void heapsort(network net[], int size);
void heapify(network netD, int pos, int size);
77
void assign_probabilityO;
void selecCtwo_pointsO;
int geCindex(double rd);
void crossoverO;
void mutationO;
void geneticAlgorithm(int pg);
void combineChemo(int pc);
void competitionO;
double distance(network net[], int indexOfPoints);
void secstepsizeO;
void chemotaxis(int pc);
void nextGenerationO;
int checkPointsO;
network getPointsO;
};
11========================================================H
IfThis constructor is for test and generalization, since II
llin this situation, only one point is needed. II
H========================================================11
GACA::GACA(int points){
int i;
numOtpoints = points;
Ilget the weights, calculated output
IIand eeror for each point
/IRandom number = new RandomO;
for(i=O; i<numOfPoints; i++){
ntwk[i). initialize_weightsO;
ntwk[i].calc_outputO;
ntwk[i].calc_errorO;
}
Hsort the points
heapsort(ntwk, numOtpoints);
Ilassign probability for each point
assign_probabilityO;
}llend of constructor
I1======================================================1I
IfThis helper method is to sort a couple of points II
Ilaccording to their error in ascending order. II
H======================================================H
void GACA::heapsort(network net[], int size){
network temp;
i.nt i, j;
for(i=(sizel)/2; i>=O; i)
heapify(net, i, size);
for(i=sizel; i>O; i) (
forU=O; j<temp.gecnum_weightsOl; j++){
78
temp.weights[j] = net[O].weights[j];
net[O].weights[j] = net[i].weights[j];
net[i].weights[j] = temp.weights[j];
}
heapify(net, 0, i);
}
}llend of heapsort
~=======================================================~
IfThis helper method is to help to sort the couple of II
~points. II
11=======================================================1/
void GACA::heapify(network net[], int pos. int sizc){
int j, I, r, k, largest;
network temp;
J = pos;
while(j<sizel) (
1= 2*j;
r=2*j+l;
ifO <=sizel )(
if(net[l].weights[temp.gecnum_weightsO2]>
net[j].weights[temp.get_num_weightsO2])
largest = 1;
else
largest = j;
}
if(r<=sizel ){
if(net[r]. weights[temp.gecnum_weightsO2l>
net[largest].wei ghts[temp.geCnum_weightsO2])
largest = r;
}
if(largest!=j){
for(k=O; k<temp.gecnum_weightsOl; k++){
temp.weights[k] = net[j].weights[k];
net[j].weights[k] = net[largest].weights[kJ;
net[largest].weights[k] = temp.weights[kJ;
}
j = largest;
}
else
break;
}
}/lend of heapify
11=========================================================~
IfThis method is implemented to assign probability to each ~
Ilpoint according to its error. II
~=========================================================/1
79
void GACA::assign_probabilityO{
network temp;
int i;
double c, pm, pb, p;
C=0.5;
pm = c/(double)numOfPoints;
pb = (2.0c)/(double)numOfPoints;
Ilassign the probability
for(i=numOfPoints; i>O; i){
P = pm+«double)(il)/(double)(numOfPointsl»*
(pbpm);
ntwk[numOfPointsi].weights[temp.gecnum_weightsOl]
=p;
}
}llend of assign_probability
~===========================================================~
Irrhis method is to find two different points among the II
Iloriginal population. II
~===========================================================~
void GACA::selecctwo_pointsO{
network temp;
int i, j, index, flag;
double rdNum;
flag = 1;
Iiselect two different points
while(flag==l){
for(i=O; i<2; i++) {
rdNum = random_generatorO;
index = get_index(rdNum);
forU=O; j<temp.geCnum_weightsO2; j++)
twoPoints[i]. weights[j] = ntwk[index]. weightsUL
}
Ilcheck whether the two points are the same
for(i=O; i<temp.gecnum_weightsO2; i++)
if(twoPoints[O] .weights[i] !=twoPoints[1J.weights[i D{
flag = 0;
break;
}
}
}llend of selecCtwo_points
11=====================================================~
Irrhis helper method is to return the index of point in II
lithe population according to the random generated II
linumber. II
11=====================================================11
int GACA::get_index(double rd){
80
network temp;
double start, end;
int i, target_index=O;
start = end = 0.0;
if(rd<ntwk[O].weights[temp.gecnum_weightsOl])
targecindex = 0;
Ilcalculate the probabilty range
for(i=I; i<numOfPoints; i++){
start += ntwk[iI].weights[temp.gecnum_weightsOl);
end = start + ntwk[i].weights[temp.gecnum_weightsOl);
if(start<rd&&rd<=end)
targeCindex = i;
}
return targeCindex;
}llend of get_index
11======================================================~
Irrhis helpre method is to get one point from the II
Iiselected two points. II
~====================================================II==
void GACA::crossoverO{
int i;
network temp;
double rdNum;
Ilget one point from the selected two points
for(i=O; i<temp.get_num_wei ghtsO2; i++){
rdNum = random_generatorO;
if(rdNum >= 0.5)
cross.weights[i] = twoPoints[O).weights[i];
else
cross.weights[i] = twoPoints[l].weights[i];
}
}llend of crossover
~===================================================== ==11
Irrhis helper method is to change the obtained one point II
Ilaccording to the randomly generated number. II
~=======================================================~
void GACA::mutation(){
network temp;
double rdNum;
int i;
for(i=O; i<temp.gecnum_weightsO2; i++){
rdNum = randoffi_generatorO;
Ilchange the weight according to the condition
if(rdNum < 0.05)
cross.weights[i] = random_weightsO;
}
81
}llend of mutation
11=========================================================11
IIIn this method, the new population is generated according II
lito the operators of the genetic algorithm. II
11======================================================11
void GACA::geneticAlgorithm(int pgH
network temp;
int i, j;
for(i=O; i<pg; i++H
selecCtwo_pointsO;
crossoverO;
mutationO;
Ilcopy the point after mutation
for(j=O; j<temp.get_num_weightsO2; j++)
newNtwk[i].weights[j] = cross.weightsU];
}
}llend of geneticAlgorithm
V======================================================11
Irrhis method is to manipulate the chemotaxis under genetic algorithm. II
V====================================================II
void GACA::combineChemo(int pc){
int i;
for(i=(numOfPointspc); i<numOfPoints; i++)
chemotaxis(i);
}llend of combineChemo
~===================================================II
Irrhe two populations are competed in this method. II
Irrhe result of the competition is that the bestso II
Ilfar point is kept. II
II===================================================V
void GACA::competitionO{
network temp;
int i, j;
double rdNum;
for(i=O; i<numOfPoints; i++){
newNtwk[i].calc_outputO;
newNtwk[i].calc_errorO;
}
heapsort(newNtwk, numOfPoints);
Ilcheck the best in the new points and old points
if(newNtwk[O].weights[temp.geCnum_weightsO2]>
ntwk[O].weights[temp.gecnum_weightsO2]){
Ilreplace the worst point in the new points
Ilby the best point in the old points
for(i=O; i<temp.gecnum_weightsOl; i++)
newNtwk[numOfPointsl].weights[i]=ntwk[O]. weights[i];
82
heapsort(newNtwk, numOfPoints);
}
Ilcheck other points
for(i=1; i<numOfPoints; i++){
if«newNtwk[i].weights[temp.gecnum_weightsO2]<
ntwk[i].weights[temp.gecnum_weightsO2])&&
(distance(newNtwk, i»distance(ntwk, i)){
l/keep the point
else if«distance(ntwk, i»distance(newNtwk, i)&&
(ntwk[i].weights[temp.gecnum_weightsO2]<
newNtwk[i].weights[temp.geCnum_weightsO2]){
Ilreplace the new point by the cprresponding point
[or(j=O; j<temp.gecnum_weightsO1; j++)
newNtwk[i].weights[j] = ntwk[i].weights[j];
heapsort(newNtwk, numOfPoints);
}
else if(distance(newNtwk, i)*
ntwk[i] .weights[temp.gecnum_weightsO2]>
distance(ntwk, i)*
newNtwk[i].weights[temp.gecnum_weightsO2]){
}
else{
1* for(j=O; j<temp.gecnum_weightsO2; j++)
newNtwk[i].weights[j] = op.random_weights(number);
newNtwk[i].calc_outputO;
newNtwk[i).calc_error();
heapsort(newNtwk, numOfPoints);*1
rdNum = random_generatorO;
if(rdNum>O. 5){
for(j=O; j <temp.get_num_weightsOl ; j++)
newNtwk[i].weights[j] = ntwk[i). weights[j];
heapsort(newNtwk, numOfPoints);
}
else
}
}llend of competition
fi=======================================================II
IfThis distance between the point and the bestsofar II
Ilpoint is calculated in this method. II
fi=======================================================fi
double GACA::distance(network net[], int indexOfPoints){
R3
network temp;
double d;
int i;
d=O.O;
for(i=O; i<temp.get_num_weightsO2; i++)
d += (net[indexOfPoints].weights[i]newNtwk[
O].weights[i])*(net[indcxOfPoints].weights[i]
newNtwk[O].weights[i]);
return sqrt(d);
}llend of distance
/1========================================================/1
I/When the algorithm is chemotaxis, a step size is required. II
Iffhe step size is asked to input in this method. II
11==========================================================11
void GACA::secstepsizeO{
cout«"Enter the step size ";
cout«"for the chemotaxis method: "«endl;
cin»stepSize;
}llend of set_stepsize
11=======================================================11
Iffhe chemotaxis algorithm is carried out in this method. II
1/=======================================================11
void GACA::chemotaxis(int pc){
int i, flag, less;
network temp;
flag = 1;
II Random number = new RandomO;
while(f1ag<WOH
less = 1;
chemo.initialize_weightsO;
while(less== 1){
IItime the step size and added to the best point
for(i=O; i<temp.gecnum_weightsO2; i++H
temp.weights[i] = chemo.weights[i]*stepSize;
temp.weights[i] = ntwk[O].weights[i] +
temp. weights[i];
}
Ilcalculate the error
temp.calc_outputO;
temp.calc_errorO;
if(temp.weights[temp.gecnum_weightsO2]<
ntwk[O].weights[temp.get_num_weightsO2J){
less =1;
J
else
less = 0;
84
if(less== 1){
for(i=O; i<temp.geCnum_weightsOI; i++)
newNtwk[pc].weights[i] = temp.weights[i];
IlcompetitionO;
nextGenerationO;
I/flag =0;
}
}llend whiJe(less==l)
flag++;
}Ilend while(flag== 1)
Ilreplace the worst point point by the bestPoint
1* for(i=O; i<temp.gecnum_weightsOl; i++)
newNtwk[pc].weights[i] = chemo.weights[il;*1
}llend of chemotaxis
V===============================================V
/fIn this method teh new population is copied II
lito the old population and the error is II
Ilcalculated. the obtained old population is II
Ilready for next generation. II
V===============================================II
void GACA: :nextGenerationO{
network temp;
int i, j;
for(i=O; i<numOtpoints; i++){
newNtwk[i].calc_outputO;
newNtwk[i].calc3rrorO;
}
heapsort(newNtwk, numOtpoints);
Ilcopy the newNtwk into ntwk for next generation
for(i=O; i<numOtpoints; i++)
for(j=O; j<temp.get_num_weightsOI; j++)
ntwk[i].wcights[j] = newNtwk[i].weightsljL
for(i=O; i<numOtpoints; i++){
ntwk[i].calc_outputO;
ntwk[i] .calc_errorO;
}
heapsort(ntwk, numOtpoints);
assign_probabilityO;
}llend of nextGeneration
11=========================================================V
IfThis method is to check the points whether they are equal or not. II
11=========================================================11
int GACA::checkPointsO{
int i, j, repeat=O;
int totaIWeights=O;
network temp;
85
totalWeights = (numOtPoints1 )*(temp.get_num_weightsO2);
for(i=1; i<numOfPoints; i++)
forU=O; j<temp.gecnum_weightsO2; j++)
if(ntwk[O].weights[j ]==ntwk[i].weights[j])
repeat++;
if(repeat==totaIWeights)
return 1;
else
return 0;
}lIend of checkPoints
11==========================================================11
Irrhis method is to get the wanted point. //
11==========================================================//
network GACA::getPointsO{
return ntwk[Ol;
86
VITA 9J
WeiLi
Candidate for the Degree of Master of Science
Thesis: Genetic Algorithm with Chemotaxis Tunable Local Searching Optimization
Major Field: Computer Science
Education: Graduated from Changchun University of Science and Technology,
Changchun, Jilin province, P. R. China in January 1982; received Bachelor of
Science degree in Chemistry. Then graduated from Murray State University,
Murray, Kentucky, USA in December 1993; received Master of Science degree in
Engineering Technology. Completed the requirements for the Master of Science
degree with a major in Computer Science at Oklahoma State University in May,
2001.
Experience: Employed as an engineer by Zhejiang Geological Institute from 1982 to
1990. Worked as a chemist in LCU Institute of Water Research in Lubbock, Texas
from 1994 to 1996.