21-05-2012, 10:18 AM
Solving transcendental equations using Genetic Algorithms
Solving transcendental equations using.pdf (Size: 51.71 KB / Downloads: 44)
I. Analytical/Iterative methods to solve transcendental equations
Transcendental equations are equations containing trigonometric, algebraic, exponential,
logarithmic, etc. terms. Many analytical/iterative methods are used to solve
transcendental equations. Though these methods are capable of solving many
transcendental equations they suffer from many common disadvantages. Usually
transcendental equations have many solutions in a given range, and analytical methods
are not able to find all these roots in a given interval, even when they find several
solutions, it is not possible to conclude that the given method has found the complete set
of roots/solutions, and has not missed any particular solution. Also, these methods fail in
case of misbehaved or discontinuous functions. Hence, though these methods may work
very well in some situations, they are not general in nature and need a lot of homework
from the Analyst.
An analysis of some common methods used for solving transcendental equations, their
disadvantages and cases of failures are discussed below.
a) Newton Raphson method: This is a commonly used method for solving
transcendental equations. The method makes use of the slope of the curve at
different points. Therefore, if the function is non differentiable at points or has a
point of inflexion, the method is not able to find the root. Secondly, if the function
changes its slope very quickly (frequently achieves slope of zero), or is
discontinuous, cannot be solved by this method. If the function is discrete, the
derivative has no meaning for it and this method cannot be used. Also there is no
straightforward way to find all the roots in an interval or even ascertain the
number of roots in the interval.
b) Bisection method: This method needs two points on the graph such that
f(a)*f(b)<0. There is no straightforward analytical method to find these points.
Another problem lies in choosing the distance between the points a and b. For the
method to work, a and b should be close enough, such that the function behaves
monotonously in these limits. At the same time, a small difference in values of a
and b makes it difficult to search the sample space. An algorithm to ascertain
such points for all roots of the equation has to be essentially random in nature and
can be another applications of GA. This will be discussed later. Further still, the
method fails for discontinuities in function.
c) Method of False Position: This method suffers from same problems as Bisection
method.
2
Hence it can be concluded that analytical methods cannot find all the roots of a
transcendental equation reliably.
II. Introduction to Genetic Algorithms
Genetic Algorithms (GAs) were first presented by J. H. Holland in his book “Natural and
Artificial Systems” in the year 1975 and developed further by his students. With time,
many changes and improvements have been suggested. Here, we discuss the present form
of implementation of Genetic Algorithms.
Genetic algorithms are a class of algorithms inspired by evolution. These algorithms
encode solutions to a specific problem on a simple chromosome like data structure and
apply recombination operators to these structures so as to preserve critical information.
An implementation of a genetic algorithm begins with a population of (typically random)
chromosomes. Then these structures are evaluated and allocated reproductive
opportunities in such a way that those chromosomes which represent a better solution to
the problem are given more chances to reproduce than those chromosomes which are
poorer solutions. The "goodness" of a solution is typically defined with respect to the
current population.
The basic steps involved in a GA are the following.
1. Build an initial population of samples (solutions) created randomly or using some
initialization method.
2. Calculate the fitness (measure of being provided reproductive opportunities) of all
the samples and select individuals for the reproduction process. The selection of the
individual is though based on fitness, but it is a probabilistic mechanism. Roulette
wheel selection, Rank Tournament Selection, Stochastic Universal Selection are some
of the selections used.
3. Apply the genetic operators of crossover, mutations, inversions, etc. to the selected
individuals to create new individuals and thus a new generation. Crossover exchanges
some of the bits of the two chromosomes and mutation inverts any bit(s) of the
chromosome depending on a probability. Crossovers is a distinguishing feature of
Genetic Algorithms. Many evolutionary algorithms were earlier used, but they
basically worked on mutations and no crossovers took place. In GAs crossovers
‘explore’ around the already found good solutions and mutations help ‘exploiting’ the
search space for new solutions.
Then again Step2 is followed till the condition for ending the algorithm is reached. Many
issues such as encoding of problem, the types of selection operator, the type of fitness
functions have been discussed and experimented at large by researchers to reach better
results.
III. GAs for the present problem
GAs have been traditionally used for optimization problems. Function optimization
implemented by GAs was studied by De Jong [1] in detail and GAs were successful to
3
solve the problem. Solving transcendental equations is also a kind of optimization
problem and hence GAs are applicable here.
Also, Melanie Mitchell [2] states, if the space to be searched is large, is known not to be
perfectly smooth and unimodal or is not well understood or if the fitness function is noisy
and if the task doesn’t require a global optimum to be found i.e. quickly finding a
sufficient good solution is enough, GAs will have a good chance to be competitive with
or other surpassing other weak methods. The present problem has a large search space, a
fitness function which might be misbehaved and has more than one solution. All these
difficulties indicate that genetic algorithms may be useful in such situations and I will
address this problem in this paper.
IV. Implementation of GAs for the present problem
Encoding: There is no strict rule for encoding the solutions to the problem. Generally
binary coded solutions are used, though lately, real coded chromosomes are also being
used. I have used binary encoding for my experiments. The advantage of using binary
encoding is that the maximum number of schemas is investigated [3].
Fitness function: The fitness function tells the algorithm how good a particular solution
is. The fitness function chosen for the problem was 1/ (1 + abs(f(x)). The relevance of the
fitness function is discussed later.
Selection and reproduction operators: As the present problem is multimodal, the selection
and reproduction operator depends on it. These will be discussed later.
The method is kept free from differentiation or any other analytical methods to tackle
non-differentiable and discontinuous functions.
V. GAs to tackle Multimodal problems
It is observed that the problem at hand is multimodal in nature i.e. one equation can have
many roots. The simple genetic algorithm is capable of searching optimum for a
unimodal function, but converges to some local optimum for a multimodal problem.
Actually the population drifts towards that optimum whose neighbouring points were
seeded in the initial population (typically, generated randomly). It happens so, that the
samples neighbouring one of the optimum get more reproductive opportunities.
Therefore, there is a better exploitation of this region, which increases the average fitness
of these samples, thus giving them more reproductive opportunities every time. Finally
these samples dominated the search space and the population converged to that particular
solution.
Various methods were devised to solve this multimodal problem, starting from De Jong
(the crowding model), followed by Perry (1984), etc. But the study of Goldberg and
Richardson on niches (sub domains of a function) and species (stable sub-populations)
based on the sharing principle [4] preformed quite well. The paper discusses the sharing
methods and analyses a relatively new method, “Clearing Procedure as a niching
method” given by A. Petrowski [5].
4
The sharing function devised by Goldberg and Richardson was the first organized
approach for multimodal problems. The sharing method was based on the principle that
resources should be shared in all different species. A sharing function was defined which
reduced the fitness of a sample depending upon its distance of individuals in the
population.
A sharing function can be defined as following
Sij(d) = 1 – (dij / σ)n for d < σ
0 for d > σ
where dij = distance and σ = threshold value of distance.
The fitness of a particular sample is changed as its fitness divided by sum of the values of
its sharing with all other samples in the population. This way the fitness of samples,
which had dominance in the population, was decreased and thus there reproductive
capabilities were limited. Goldberg also observed that mutation was necessary in this
procedure for good exploration of the search space.
The method had some limitations. The value of σ was dependent on the problem at hand.
The method asked for larger size of subpopulation, otherwise it converged prematurely.
More recently, a clearing procedure was devised by Alain Petrowski [5]. This method
allocates the resources of a niche (sub domain of a function) to the best individual of the
species rather than sharing it among all the samples of the particular niche as done in
sharing. This method worked more successfully than the sharing procedure even with a
smaller population.
Implementation of the Clearing Procedure: Alain Petrowski gave the following steps for
implementing the clearing procedure. Starting with the fittest sample in the population
and equate the fitness of all samples having distance from the sample less than the
clearing radius (equivalent to threshold radius) to zero. Then, take the next fittest sample
(whose fitness is non-zero) and repeat the clearing procedure with it. In this way, only the
fittest samples of each niche are provided with reproductive capabilities. Stochastic
Universal Sampling (SUS) was recommended for selection to reduce ‘selection noise’.
For the reproductive capabilities, crossover probability was kept equal to 1 and
probability for mutation was kept low.
Petrowski also suggested an elitist strategy in the procedure. The elitist strategy used
initially by De Jong [1], kept record of the fittest individual of a population. If the new
population generated didn’t contain that individual, it was included in the new population
incrementing its size by 1. De Jong observed that the strategy worked well with unimodal
search space, but degraded the performance of the GA considerably in multimodal search
space. Petrowski implemented the elitist strategy with every sub-population separately.
This modification improved the clearing strategy significantly.
The working of the clearing procedure is dependent on the value of the clearing radius,
which is not known in our problem. Experiments (detailed in the following discussion)
were carried out and a strategy was evolved to solve this issue.