International Journal of Distributed and Parallel Systems (IJDPS) Vol.2, No.6, November 2011

DISTRIBUTED EVOLUTIONARY COMPUTATION: A
NEW TECHNIQUE FOR SOLVING LARGE NUMBER
OF EQUATIONS
Moslema Jahan, M. M. A Hashem and Gazi Abdullah Shahriar
Department of Computer Science and Engineering,
Khulna University of Engineering and Technology, Khulna 9203, Bangladesh
mjahan.cse@gmail.com, mma_hashem@hotmail.com and rana_kuet@yahoo.com

ABSTRACT
Evolutionary computation techniques have mostly been used to solve various optimization and learning
problems successfully. Evolutionary algorithm is more effective to gain optimal solution(s) to solve
complex problems than traditional methods. In case of problems with large set of parameters,
evolutionary computation technique incurs a huge computational burden for a single processing unit.
Taking this limitation into account, this paper presents a new distributed evolutionary computation
technique, which decomposes decision vectors into smaller components and achieves optimal solution in
a short time. In this technique, a Jacobi-based Time Variant Adaptive (JBTVA) Hybrid Evolutionary
Algorithm is distributed incorporating cluster computation. Moreover, two new selection methods named
Best All Selection (BAS) and Twin Selection (TS) are introduced for selecting best fit solution vector.
Experimental results show that optimal solution is achieved for different kinds of problems having huge
parameters and a considerable speedup is obtained in proposed distributed system.

KEYWORDS
Master-Slave Architecture, Linear Equations, Evolutionary Algorithms, Hybrid Algorithm, BAS selection
method, TS selection method, Speedup.

1. INTRODUCTION
In recent years, application of evolutionary algorithms is increasing to a greater extent.
Evolutionary algorithms (EAs) are stochastic search methods that have been applied
successfully in many search, optimization and machine learning problems. Successful use of
evolutionary algorithm for solving linear equations is applied in [1], [2], [3]. However, it is
often very difficult to estimate the optimal relaxation factor, which is the key parameter of the
successive over relaxation (SOR) method. Optimal solution is achieved quickly as relaxation
factors are adapted automatically in evolutionary algorithm. Equation solving abilities was
extended in [2], [3], [4] by using time variant parameter. The invention of hybrid evolutionary
algorithm [5], [6] brought a greater benefit to solve linear equations within very short time.
Many problems with huge parameters such as Numerical Weather Forecasting, Chain Reaction,
Astrophysics (Modelling of Black hole), Astronomical formation, Semiconductor Simulation,
Sequencing of the human genome, Oceanography need high computational cost in case of
single processor. One approach to overcome this kind of limitation is to formulate the problem
into distributed computing structure.
The main parallel achievements in the algorithmic families including the evolutionary
computation, parallel models and parallel implementations are discussed in [7]. A distributed
cooperative coevolutionary algorithm is developed in [8] which is beneficial for solving
complex problems. As there are no free lunch theorems for optimization algorithms, a graceful
convergence is the key challenge for designing an optimization algorithm. A number of “no free
DOI : 10.5121/ijdps.2011.2604

31

International Journal of Distributed and Parallel Systems (IJDPS) Vol.2, No.6, November 2011

lunch” (NFL) theorems [9] are presented for any algorithm, which state that any two algorithms
are equivalent when their performance is averaged across all possible problems. On the other
hand, there are coevolutionary free lunches theorems in [10]. The proposed technique follows
coevolutionary theme. A distributed technique [11] is proposed for parallelizing fitness
evaluation time. Fitness evaluation time is high but other operations of evolutionary algorithm
take more time. This paper proposes a Distributed Evolutionary Computation (DEC) in which
mutation and adaptation processes are also distributed. This is the Champion Selection
technique, where best champion is selected within short period of time.
Master (Server)

Slaves (Clients)
Figure 1. Distributed Master-Slave Architecture
Basic master-slave architecture (Figure 1) is used in proposed distributed technique that follows
a server-client paradigm where connections are closed after each request. Slaves are connected
with master through local area network (LAN) to take the advantage of distributed processing
power of slaves. The basic approach of this system is to split a large problem into many
subproblems and to evolve subproblems separately. These subproblems are then combined and
actual solution is achieved. This process continues until the less erroneous solution comes out
compared to a threshold error level.
The remainder of this paper is structured as follows: Section 2 represents the previous work
related to the proposed work. Section 3 mentions Jacobi method of solving linear equations and
distributed model. Timing calculation is discussed in section 4. Section 5 examines results of
the experiment of various problems and provides a comprehensive comparison of single and
distributed system on the basis of BAS and TS selection mechanism. Finally, Section 6 provides
our concluding remarks.

2. RELATED WORK
The intrinsically parallel and distributed nature of EAs did not escape the attention of early
researchers. Grefenstette [12] was one of the first in examining a number of issues pertaining to
the parallel implementations of GAs in 1981. Grosso [13] is another early attempt to introduce
parallelism using spatial multipopulation model. Several attempts were made to have a better
and fast system that is capable of doing Evolutionary computations in parallel fashion. DREAM
(Distributed Resource Evolutionary Algorithm Machine) [14] is such a system that used island
model architecture on peer-to-peer connection. Both island-model and master-slave architecture
has been combined at ParadisEO (PARAllel and DIStributed Evolving Objects) [15]. But in
either case, all genetic operations are not done with a distributed manner. Among different
models and architectures, this paper follows master-slave architecture to develop parallel and
distributed environment.

32

International Journal of Distributed and Parallel Systems (IJDPS) Vol.2, No.6, November 2011

JDEAL (Java Distributed Evolutionary Algorithms Library) [16] is a master-slave architecture
coded in Java platform. Paladin-Dec [17] was another Java implementation of genetic
algorithms, genetic programming and evolution strategies, with dynamic load balancing and
fault tolerance. Still the communications among the nodes in distributed architecture uphold an
issue. ECJ [18] is a Java-based framework that doing its computation using Java TCP/IP
sockets. MPI (Message Passing Interface) is used at [19] with C++ framework. The developed
distributed EC system was integrated transparently with the C++ Open BEAGLE framework
[20] in 2002. Parallel performance of MPI sorting algorithms is presented in [21]. By gathering
all ideas this paper implement a hybrid algorithm combining the jacobi-based successive
relaxation (SR) method with evolutionary computation techniques which follow Java-based
framework with socket programming in distributed manner and related speedup is calculated.
Same algorithm was implemented in single processing system [4] using C++ framework and the
related speedup was calculated. Finally experimental result shows distributed system is more
speedy than single system to solve the problems with huge parameters.
Selection mechanism of an Evolutionary Computation technique has been a key part which
brings up a significant computational cost. In 1982 Hector Garcia-Molina provides an election
algorithm in [22] for two categories failure environments by which a coordinator will be selected
when failure occurs in distributed computing system. A sum-bottleneck path algorithm is
developed in [23] that allows the efficient solution of many variants of the problem of optimally
assigning the modules of a parallel program over the processors of a multiple-computer system
under some constraints on the structure of the partitions. An individual selection method is
provided in [24] to select efficient individuals and whole system follows a distributed technique.
In 2010, an improved system of an abstraction, all-pairs that fits the needs of several
applications in biometrics, bioinformatics, and data mining is implemented in [25] shows the
effect of campus grid system which is more secured than single system because of following
distributed manner. Different papers followed various election mechanisms for choosing right
population. Like these, our paper also provides two new selection mechanisms BAS which
choose all best individual with less error rate and TS which choose one individual between
adjacent two and develop twin copy of the individual with low error.

3. PROPOSED MODEL OF DISTRIBUTED EVOLUTIONARY ALGORITHM
The new distributed technique is anticipated based on Jacobi Based Time- Variant Adaptive
Hybrid Evolutionary algorithm [3] through cluster computing environment. The proposed
algorithm initializes a relaxation factor in a given domain which is adapted with time and fitness
of the solution vector.

3.1. Jacobi Method of Solving Linear Equations
Consider the following linear equations:
(1)
Ax = b or Ax − b = 0
n
n
n
Where A ∈ ℜ × ℜ and x, b ∈ ℜ
Let, A is n × n matrix, where aii is the diagonal elements, aij is other elements of the A
matrix and bi is elements of b matrix. For solving linear equations Jacobi method is used [26].
Let,

Linear equations is Ax = b and A ≠ 0

(D + U + L )x = b , Where A = (D + U + L )
Dx = b − (U + L )x or, x = D −1b − D −1 (U + L) x

Then

or,
or, x = H j x + V j

Where H j = D −1 (− L − U ) and V j = D −1b
The linear equation can be written as
33

International Journal of Distributed and Parallel Systems (IJDPS) Vol.2, No.6, November 2011
n

∑a

ij x j

= b j , (i = 1,2,3,.....n )

(2)

j =1

In Jacobi method by using SR technique [27] is given by,

ω 
x i(k +1) = x i(k ) +
bi −
a ii 

n

∑a

(k )
ij x j

j =1


,



(i = 1,2,3,.....n )

(3)

In matrix form matrix-vector equation is

x (k +1) = H ω x (k ) + Vω

(4)

Where H ω called Jacobi iteration matrix, and Vω are given successively by

H ω = D −1 {(1 − ω )I − ω (L + U )}
And

−1

Vω = ωD b

(5)
(6)

If ω is set at a value between 0 and 1, the result is weighted average of corresponding previous
result and sum of other (present or previous) result. It is typically employed to make a nonconvergence system or to hasten convergence by dampening out oscillations. This approach is
called successive under relaxation. For value of ω from 1 to 2, extra weight is placed. In this
instance, there is an implicit assumption that the new value is moving in the correct direction
towards the true solution but at a very slow rate. Thus, the added weight ω is intended to
improve the estimate by pushing it closer to the truth. This type of modification, which is called
over relaxation, is designed to accelerate the convergence of an already convergent system. This
approach is called successive over relaxation (SOR). The combine approach, i.e. for value of ω
from 0 to 2, is called successive relaxation or SR technique [26].
Iterative process is continued using equation (3) until the satisfactory result is achieved. Based
on this method, different hybrid evolutionary algorithms are developed in [1] [2]. Parallel
iterative solution method for large sparse linear equation systems is developed in [28].

3.2. Proposed Distributed Technique
The availability of powerful network computers represents a wealth of computing resources to
solve problems with large computational effort. Proposed distributed technique uses masterslave architecture and classical numerical method with Evolutionary Algorithm for solving
complex problems.
In this system, large problems are decomposed into smaller subproblems and mapped into the
computers available in a distributed system. Communication process between master and slaves
follow message passing paradigm that is identical with [29]. This technique introduces the high
performance cluster computation, linking the slaves through LAN to exploit the advantage of
distributed processing of the subproblems. Here each slave in a cluster always solves same
weighted subproblems although machine configuration is different. In this cluster computing
environment, master processor defines number of subproblems according to slave number in a
cluster. The workflow diagram of proposed algorithm is portrayed as in Figure 2.

34

International Journal of Distributed and Parallel Systems (IJDPS) Vol.2, No.6, November 2011

Start
Set Parameters

Initialization of
Population
Stop
Y

Error<Th
reshold

Begin

Mutation

Recombination

Connection Setup with
master processor

Fitness
Evaluation

Determine number
of Subpopulations

Waiting for coming job

N

Adaptation

Y
Is BAS
Method?

Job
assigned?

Distribute
all
subpopulat
ions?

N (TS)
N

Twin
selection

Block of genetic
operations

Return subpopulation to
master

Send solution to master
and update slave status

Y
Sleep until all
solutions return from
all slaves

End

Block of genetic operations

Champion selection
Master processor

Slave processor

Figure 2. The workflow diagram of DEC system
The proposed workflow diagram can be mapped into master-slave paradigm. In Figure 3 all
steps of proposed DEC are expressed using numbering system in each position. Step 1, 2, 7 are
completed in master processor and step 3, 4, 5 occurred in slave processors but working
principle of step 7 depends on selection method. For both methods, step 6 is dedicated for
checking whether selected offspring from all slaves return back in master processor or not.
35

International Journal of Distributed and Parallel Systems (IJDPS) Vol.2, No.6, November 2011

Server
(Master)

Controller

Evaluators
(Slaves)

Loopback

2

3

1

4

7

6

5

Figure 3. Working model of proposed technique

3.2.1. Initialization
In step 1, master processor initializes problems with population and relaxation factor. Initial
population X (0 ) = x1(0 ) , x 2(0 ) ,.....x N(0 ) is generated randomly using normal distribution at master.
Here N is the population size. Let k ← 0 where k is the generation counter. Relaxation factors
ω (0 ) = ω1(0 ) , ω 2(0 ) ,......, ω N(0 ) are also initialized on the basis of corresponding individuals.

{

{

}

}

3.2.2. Recombination
In step 2, Recombination operation is performed on parent at master and population

(

X (k + c ) = R X (k )

)

t

( )

is obtained, where R = rij

n

and

N×N

∑r

ij

= 1 and rij ≥ 0 for 1 ≤ i ≤ N

j =1

Matrix R is a stochastic matrix.
Population generated after recombination operation is distributed among slaves. Then mutation,
fitness evaluation and adaptation operations are performed on that distributed subpopulations.

3.2.3. Mutation
After completing recombination operation step 3 provides Mutation operation on the
subpopulation in slave processors and mutated subpopulation X (k + m ) is obtained. For each
Mutation on subpopulation is
N sub

∑x

(k + m)
i

= H ω x i( k + c ) + Vω

(7)

i =1

3.2.4. Fitness Evaluation
After completing mutation operation, fitness evaluation is performed in step 4. Error function is
N sub

E=

∑E

(8)

i

i =1

N sub

Where E =

∑ a (x ) − b
ij

j

i

, i = 1,2,....., N sub

j =1

The fitness evaluation of an individual measures the accuracy of an individual for a particular
problem and calculates the error rate which is used for selecting best individuals.
36

International Journal of Distributed and Parallel Systems (IJDPS) Vol.2, No.6, November 2011

3.2.5. Adaptation
In step 5, adaptation is performed on mutated offspring according to fitness evaluation.
Consider two individuals X and Y , corresponding errors e x and e y and relaxation factors ω x
and ω y .
If e x > e y then ω x is adapted to ω y .

ω xm = (0.5 + p x )(ω x + ω y )
Similarly if e y < e x then ω y is adapted to ω x and if e x = e y then no adaptation is
performed. Px is denoted as adaptive (TVA) probability parameter of ω x .
In step 6, controller checks whether offspring from all slaves have reached in master processor
or not. In BAS method, step 6 starts its task after completion of adaptation operation but in TS
method, after completing of partial selection of best offspring in each slave.

3.2.6. Selection
The DEC system provides two selection methods named BAS and TS. In BAS method, best
individuals are selected among parent and mutated offspring. At position 7, mutated offspring
from all slaves are combined and selection mechanism is performed on parent and newly
generated offspring by mutation.
Mathematically,
Selection(i ) = errmin {x1 , x 2 , x 3 ,.....x 2 N −i +1 }

(9)

N

Selection =

∑ Selection(i )

(10)

i =1

Individuals compete among themselves and select best individual based on error value. Before
finding the optimized solution, overall system will be continued in same process.
TS method provides a partial selection operation on mutated offspring in each slave where one
best individual is selected between two consecutive individuals and developed twin copy of
selected offspring.
Mathematically,
Selection(i ) = errmin {x i , x i +1 }

(11)

N sub

Selection =

∑ Selection(i)

(12)

i =1

These selected offspring are combined in server and select best one. The selected copy will be
the champion among all individuals or optimized solution for a particular problem if this fulfils
the desired condition, otherwise fill up the whole archive and next generation will be continued.
There is no direct communication among the subpopulations. All communications are
performed between the subpopulation and the central server. Such communications take place in
every generation before reaching the accurate result.

3.3. Scenario of “Champion Selection”
The DEC system can be compared with a game where a champion will be selected on the basis
of some criteria. At the starting moment, all players are presented at master which is a
coordinator. The Coordinator divides all players into different teams and assigns these teams in
different slaves. The number of players in a team is determined according to the slave number in
37

International Journal of Distributed and Parallel Systems (IJDPS) Vol.2, No.6, November 2011

a game region that is a cluster. After reaching the team, some operations are performed on that
team separately and simultaneously in each slave. Each player has enriched after operation and
all players from each slave come back in master. After coming back, all players compete with
each other and select best one. If the selected one fulfils the desired criteria then this is the
champion of the game or game will be continued following same process.
Subpopulation
Individuals
1

Slave 1
2
3

Slave 2

4
5

Server
(Master)

Slave 3
6

Figure 4. The model of DEC
A prototype model of DEC with six individuals over three slave computers is illustrated in
Figure 4. The figure shows the division of main population into three subpopulations containing
two individual in each according to the number of slave computers where master processor is
the coordinator which will take the decision. Each slave accepts two individuals among six of
them. Some Evolutionary mechanisms are operated separately in each slave. After completing
the operations, subpopulations are returned back to master and individuals compete among
themselves and a champion is coming out. If the champion is not best suited with the standard
value, this process will be continued. Otherwise this champion is the winner of the game.

3.4. Explanation of Selection Methods
This section represents two selection methods which will help to find out the optimized solution
of a problem. Working mechanisms of these two methods are as follows:

3.4.1. BAS selection method
In this method, best individual is selected between parent and mutated offspring in each
iteration. After coming back all individuals from all slaves to master, they compete with each
other and provide best half of the total individuals including parent and offspring and assign
priority according to the error rate. On the basis of the priority, a champion is selected. If the
error rate of the champion is equal or less to the standard value, this is the optimized solution of
the problem. Otherwise the process will be going on.

38

International Journal of Distributed and Parallel Systems (IJDPS) Vol.2, No.6, November 2011

Parent
a

b

c

e3

e2 e5

Offspring

d

e8

e7

Recombination
and Mutation

e1

e3

e5

e1

e6

e4

Selection

e4

Figure 5. Selection mechanism for BAS method
In Figure 5: a, b, c and d patterns represent four parent individuals and the stripped patterns
represent offspring. Error of each parent individual is e3, e2, e5, e7 and corresponding
relaxation factors are ω3, ω2, ω5, ω7. Similarly error of each offspring is e8, e1, e6 and e4 and
relaxation factors are ω8, ω1, ω6 and ω4. Here error number represents the value of the error.
Now best half individuals are selected between parent and offspring according to error value.
Here two individuals are selected from parent and two are selected from offspring.
Corresponding relaxation factor is also rearranged. Next generation is started with these selected
offspring and their respective relaxation factor.
The time variant adaptive (TVA) parameters are defined as
Px = E x × N (0,0.25) × Tω
And Px is denoted as adaptive (TVA) probability parameter of ω x , and
Py = E y × [N (0,0.25)]× Tω

(13)
(14)
γ

t

And Py is denoted as adaptive (TVA) probability parameter of ω y ; Where Tω = 1 − 
 T
Here λ and γ are exogenous parameters, used for increased or decreased of rate of change of
curvature with respect to number of iterations; t and T denote number of generation and
maximum number of generation respectively. Also N (0,0.25) is the Gaussian distribution with
mean 0 and standard deviation 0.25.

Now E x and E y denote the approximate initial boundary of the variation of TVA parameters
of ω x and ω y respectively. If ω ∗ is denoted as the optimal relaxation factor then

E x = Px | max =

ωy ~ ωx

(

2 ωx +ω y

(15)

)

(

)

So that ω xm = (0.5 + Px | max ) ω x + ω y ≈ ω y and
∗

E y = Py | max =

∗

ω ~ ωy

(

2 ω y −ωL

)

or

ω ~ ωy
ωU − ω y

(16)

39

International Journal of Distributed and Parallel Systems (IJDPS) Vol.2, No.6, November 2011

(
(

)
)

ω y + Py |max ωU − ω y , ω y > ω x 
so that, ω ∗ ≈ ω ym = 

ω y + Py |max ω L − ω y , ω y < ω x 

(17)

3.4.2. TS selection method
Each slave contains a subpopulation and each subpopulation consists of at least two individuals.
After completing adaptation operation, best individual is selected between two consecutive
individuals. These individuals are returned back to the master and compete among themselves.
After the competition, a best quality champion is selected according to the error value and
checking with the standard value. If the error value is equal or less to the standard value, this is
the optimized solution. Otherwise this best champion is cloned and fills the archive and
continues the process. The corresponding relaxation factors are also rearranged which is
required for adaptation operation of next generation.
Parent
a

b

c

e3

e2 e5

Offspring

d

e7

e8

e1

Recombination
and Mutation

e1 e1 e1

e1

e6

e4

Selection

e1 e1 e6 e6

Select best champion
among all champions
Figure 6. Selection mechanism for TS method
In Figure 6: a, b, c and d patterns represent four parent individuals and the stripped designs
represent offspring. Error of each offspring is e8, e1, e6, e4 and corresponding relaxation factors
are ω8, ω1, ω6, ω4. There are two subpopulations in two slaves and each contains two
individuals. The error rate of the individuals in 1st subpopulation is e1 and e8, and 2nd
subpopulation is e6 and e4. Now, best individual is selected between two consecutive offsprings
and made a twin of it. The individual with the error rate e1 is chosen from 1st individual and
individual with the error rate e6 is chosen from 2nd subpopulation. These individuals are
returned back to master and select a best quality champion according to the error rate. This
champion is cloned to the equal number of the parent and next generation is started with these
cloned individuals. Corresponding relaxation factor is also rearranged.
The time variant adaptive (TVA) parameters are defined as
Px = gauss x × Pmax × Tω

(18)

Px is denoted as adaptive (TVA) probability parameter of ω x , and

Py = gauss y × Pmin × Tω

(19)
40

International Journal of Distributed and Parallel Systems (IJDPS) Vol.2, No.6, November 2011

Py is denoted as adaptive (TVA) probability parameter of ω y
Where

1 

Tω = λ ln1 +
, λ > 10
 t+λ 

Approximately, Pmax and Pmin are two exogenous parameters that are assumed as
Pmax = 0.125 and
Pmin = 0.0325
Here, λ and γ are exogenous parameters, used for increased or decreased of rate of change of
curvature with respect to number of iterations; t and T denote number of generation and
maximum number of generation respectively. Also, gauss x (0,0.25) is the Gaussian distribution
with mean 0 and standard deviation 0.25. Now Pmax and Pmin denote the approximate initial
boundary of the variation of TVA parameters of ω x and ω y respectively. And if ω ∗ is denoted
as the optimal relaxation factor then
ω y + Py | max ωU − ω y , ω y > ω x 
ω ∗ ≈ ω ym = 

ω y + Py | max ω L − ω y , ω y < ω x 

(
(

)
)

4. COMPUTATION TIME ANALYSIS
DISTRIBUTED PROCESSORS

(20)

OF

SINGLE PROCESSOR

AND

Timing is the main parameter which is compared for single and distributed processors. For a
specific optimization problem, DEC system provides some notation for recombination time,
mutation time, fitness evaluation time, adaptation time, and selection time can be denoted as
Tr , Tm , T f , Ta and Ts . Total time in single processor is indicated by Tsin gle . Time in single
processor is represented as follows,

TSingle = Tr + Tm + T f + Ta + Ts

(21)

In case of distributed system, time is calculated in master and slaves separately. Then total time
is calculated by combining master and slave time.

4.1. Time in master processor
For a particular problem, Recombination operation is performed on initial population and time
Tr is calculated. Then the server distributes individuals among all slaves connected to it.
Number of subpopulations is p which is distributed in slaves. In this case, Marshalling and
transmission time is considered. Marshalling time is the time to construct data stream from
object and transmission time is the time to place data stream in channel. Marshalling time of i th
individual is Tmi and Transmission time with i th individual is Ttransi .
Marshalling and transmission time with p subpopulations = P[Tmi + Ttransi ]

4.2. Time in slave processors
Mutation time, fitness evaluation time, adaptation time with p subpopulations is Tm , T f and
Ta respectively. Unmarshalling time Tumi is considered here. Unmarshalling time is the time to
create object from data stream. After completing adaptation operation, each slave sends mutated
offspring to server when BAS selection method is considered but in TS method, slaves send
individuals which are selected as best quality for a particular slave. In BAS method, selection
operation is performed in master processor but partial selection operation is completed in slave
processor in TS method. So this selection time for TS method is calculated in slave processor
41

International Journal of Distributed and Parallel Systems (IJDPS) Vol.2, No.6, November 2011

and sends to master. The processing time of each slave is not equal because of communication
delay. In experimental calculation, maximum time is considered for all cases.

4.3. Time in Master Processor for selection
The basic difference between BAS and TS selection method is to perform selection operation in
two different ways. So selection time for BAS and TS method is calculated in different manner.
Selection time with 2 N subpopulation is Ts , N individuals for parent and N individuals for
offspring. Maximum slave time is considered for calculating speedup. Consider m is the
number of slaves. In BAS selection method, total time for distributed processors is as follows,

[

)]

(

TDistributed ( BAS ) = Tr + p Tmi + Ttransi + max 1....m Tm + T f + Ta + pTumi + Ts

(22)

Where Tdistributed represents total distributed time, Tr , Tmi , Ttransi , Tm , T f , Ta , Tumi , Ts represents
recombination time, marshalling time, transmission time, mutation time, fitness evaluation time,
adaptation time, unmarshalling time and selection time.
Speedup for distributed technique using BAS method is:

Speedup = TSingle T Distributed ( BAS )

(23)

In TS selection method, selection operation is performed on mutated offspring in each slave
where each best individual is selected between two consecutive individuals
and corresponding time is obtained. Then slaves send selected offspring with selection time
calculated in slave to master.
Total selection time with p subpopulation = Ts
Consider m is the number of slaves. In the case of TS method:

[

TDistributed = Tr + p[Tmi + Ttransi ] + T f + Tm + Ta + Ts

]

(24)

Speedup for TS method:
Speedup = TSingle T Distributed

(25)

Furthermore, percentage of improvement:
%=Speedup/Number of computers

(26)

Computation time in distributed processors will be less than single processor. So, speedup will
be gradually rising with increasing number of individuals in a population.

5. EXPERIMENTAL RESULTS
The environment of experiment consists with 15 homogeneous computers and 100 Mbits/sec
Ethernet switch. This system is implemented in Java on a personal computer with Intel Pentium
IV and 512MB RAM. In our experiment, individual values are generated randomly. Here,
random values are generated using normal distribution with the range from -15 to 15. In order to
evaluate the effectiveness and efficiency of the proposed algorithm, various problems are tested.
A problem which is tested for different approaches is shown in different graphs. The testing
problem is:
Ax = b
Where, a ii = 20.0 , a ij ∈ (0,1) , bi = 10 * i
and i = 1,2,3,......, n , j = 1,2,3,......, n

42

International Journal of Distributed and Parallel Systems (IJDPS) Vol.2, No.6, November 2011

The parameter is n = 100 and the problem was solved with an error rate resides in the domain
from 9 × 10 −9 to 1×10 −8 for both BAS and TS method. Different experiments were carried out
using this problem.
Table I gives the results produced by proposed distributed algorithm and single processor
algorithm. Here, different problems are tested with comparing time between single and
distributed processors. Table I provides the results using BAS method. Similarly, Table II
summarizes experimental results of various problems with TS method. In these two tables,
number of computers in a cluster is five as distributed processors. In all cases, optimum solution
is achieved. It is possible to solve various benchmark problems using the proposed distributed
system.
It is very clear from Table Ι and Table II that performance of distributed processors is better
than single processor. Although BAS and TS both are selection methods that are used in
distributed system, BAS method shows better performance than TS method.

Table 1. Experimental Results of Time for Different Problems in Single and Distributed
Processors for BAS Method
Problem
Number

Problem

Individu
al
Number

Parame
ter
Numbe
r

Time in
Single
Processor
(seconds)

Time in
Distributed
Processor
(seconds)

Error

p1

a ii = 20.0; a ij ∈ (0,1);

40

170

4.02 × 10 −1

6.88 × 10 −2

9 × 10 −4

bi = 10 * i

p2

a ii = 20n; a ij = j; bi

40

120

3.68 × 10 −1

6.75 × 10 −2

9 × 10 −9

p3

a ii = 2i 2 ; a ij = j; bi =

40

120

3.38 × 10 −1

6.16 ×10 −2

9 ×10 −9

20

100

1.18 × 10 −1

3.57 × 10 −2

9 × 10 −9

20

100

1.33 × 10 −1

3.45 × 10 −2

9 × 10 −9

40

100

1.85 × 10 0

2.13 × 10 −2

9 × 10 −4

p4

a ii ∈ (− 100,100 );
a ij ∈ (− 10,10 );
bi ∈ (− 100,100 )

p5

a ii ∈ (− 70,70 );
a ij ∈ (0,7 );
bi ∈ (0,70 )

p6

a ii = 70;
a ij ∈ (− 10,10 );
bi ∈ (− 70,70 )

Table 2. Experimental Results of Time for Different Problems in Single and Distributed
Processors for TS Method

43

International Journal of Distributed and Parallel Systems (IJDPS) Vol.2, No.6, November 2011

Proble
m
Numb
er
p1

Problem

aii = 20.0; aij ∈ (0,1

Individual
Number

Parameter
Number

Time in
Single
Processor
(seconds)
1.21 × 10 −1

Time in
Distribute
d
Processor
(seconds)
9.93 × 10 −2

20

100

Error

1× 10 −8

bi = 10 * i

p2

a ii = 20n; a ij = j; b

20

100

1.28 × 10 −1

1.05 × 10 −1

1× 10 −8

p3

a ii = 2i 2 ; a ij = j; b

20

100

1.48 × 10 −1

1.22 × 10 −1

1× 10 −8

p4

aii ∈ ( −100,100 ) ;

20

100

1.46 × 10 −1 1.34 × 10 −1

1× 10 −5

20

50

1.06 × 10 −1

9.59 × 10 −2

1× 10 −4

20

10

1.12 × 10 −1

9.94 × 10 −2

1× 10 −4

aij ∈ ( −10,10 ) ;
bi ∈ ( −100,100 )
p5

a ii ∈ (− 70,70 );
a ij ∈ (0,7 ); bi ∈ (0,

p6

aii = 70;
aij ∈ ( −10,10 ) ;
bi ∈ ( −70, 70 )

5.1. Speedup comparison between BAS and TS method
To compare speedup, BAS and TS method follows the system standard with 40 individuals for
5 and 10 number of computers in a cluster as well as 30 individuals for 15 number of computers
when parameters are 100 for each case.
8

BAS method

TS method

7

Speed up

6
5
4
3
2
1
5

10
Number of computers in a cluster

15

Figure 7. Speed up measurement according to number of computers in a cluster
In Figure 7, speedup is calculated using eqn (23) in BAS method and TS method uses eqn (25).
Speedup is 3.36, 4.57, 6.72 in BAS method and 2.109, 1.999, 2.421 in TS method when number
44

International Journal of Distributed and Parallel Systems (IJDPS) Vol.2, No.6, November 2011

of slave computers is 5, 10 and 15. Percentage of improvement is sequentially 67.2 %, 45.7 %
and 44.8 % for BAS method as well as 21.09 %, 19.99 % and 24.21 % for TS method which is
calculated based on eqn (26). It can be easily visualized that BAS method provides better
performance than TS method.
0.02

Time(Seconds)

0.015

0.01

0.005

0

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Computer Number

Figure 8. Time (in seconds) measurement according to computer number in a cluster
Figure 8 shows the time required for performing genetic operation in each slave. Here, number
of slave computers in a cluster is 15 and individual is 30 and parameters are 100. There is no
load balancing system so different slave computers need different time.
Intuitively, workload balancing for a distributed system can be difficult because the working
environment in a network is often complex and uncertain. From Figure 8, we can see that
computer number 1 needs the highest computation time among all slaves. For calculating total
distributed time, this maximum value is considered in both methods.

5.2. Comparing time with dimension
Figure 9 and Figure 10 show the time requirement on the basis of parameter number to solve the
problems using BAS and TS method and compare the performance in single and distributed
processors. The system runs with 5 and 20 slave computers in a cluster and parameters are 50,
60, 70, 80, 90 and 100. There is a fluctuation of time with increasing number of parameters
because of random production. All parameters are same for two methods. Distributed system
needs less time than single system in both cases but BAS method is better selection mechanism
than TS selection method.
0.16
0.16

0.14

0.14

0.1
0.08

Time(Seconds)

Time(Seconds)

0.12
Single Processor
Distributed Processor

0.06

0.12
0.1
0.08

0.04

0.06

0.02

0.04

0
50

Single Processor

60

70
80
Number of parameters

90

100

Figure 9. Time measurement according to
the number of parameters in BAS method

0.02
50

Distributed Processor
60

70
80
90
Number of parameters

100

Figure 10. Time measurement according to
the number of parameters in TS method
45

International Journal of Distributed and Parallel Systems (IJDPS) Vol.2, No.6, November 2011

5.3. Comparing time with individual
Time is compared between single and distributed processors according to individuals using
BAS and TS method; this is shown in Figure 11 and Figure 12. The number of slave computers
in a cluster is 5 and number of parameters is 100 in all cases where individual number is varying
with the value of 10, 20, 30, 40 and 50. Time is increasing with increasing number of
individuals but more time is always needed in single system comparing with distributed system.
0.35

0.35
Single Processor

Single Processor

0.3

Distributed Processor

0.25

Time(Seconds)

Time(Seconds)

0.3

0.2
0.15
0.1

Distributed Processor

0.25
0.2
0.15
0.1
0.05

0.05
0
10

20

30
40
Number of individual

0
10

50

20

30
40
Number of individual

50

Figure 12. Measurement of Time with
number of individuals in TS method

Figure 11. Measurement of Time with
number of individuals in BAS method.

5.4. Comparing error with generation
Figure 13 and Figure 14 visualize the error rating with number of generations in BAS and TS
method. In both cases, efficiency is compared between single and distributed. These two
methods use 5 slave computers in a cluster but other parameters are different. Number of
parameters is 100 and number of individuals is 40 for BAS method but TS method uses 90
parameters and 20 individuals for this experiment. From figures it is easily understandable that
some cases of distributed system needs less generation than single system to go convergence.
0.01

0.015

Single Processor

Single Processor

Distributed Processor

0.008

Distributed Processor
0.01
Error

Error

0.006
0.004
0.005
0.002

0
7

8

9

10
11
Generation

12

Figure 13. Error measurement according to
generation in BAS method

13

0
10

11

12

13
14
Generation

15

16

Figure 14. Error measurement according to
generation in TS method

46

International Journal of Distributed and Parallel Systems (IJDPS) Vol.2, No.6, November 2011

In all cases, performance of distributed processor is better than single processor. In the mean
time it is also noticeable that BAS selection method shows incredible performance than TS
method although this method completes a partial selection in slave processor. A tricky point is
that individuals are filtering primarily in each slave, so there may be discarded better quality
individual from a slave. On the other hand, BAS method choose best individual from parent and
all offspring coming back from all slaves. So achieving optimal result in BAS method is faster
than TS method. Apparently, it is not realized because of distributed selection operation in TS
method which is not in BAS method. But in some case, TS method provide better performance
if the selection order is perfect for each slave.

6. CONCLUSIONS
It is easy to solve linear equations with less number of parameters in single processor but high
computational cost is required for large number of parameters. This cost can be drastically reduced
using distributed system. This paper introduced a new distributed algorithm for solving large number
of equations with huge parameters. It also introduced two new selection methods called BAS and TS
for selecting offspring. In these methods, best individuals are selected and computation load is
distributed in each slave and mutation, fitness evaluation, and adaptation operations are performed
on distributed load. As distributed technique is used, computation time is reduced using these
selection methods but BAS method provides better performance compared to TS method. For both
selection methods, computational time is analyzed and hence speed up is calculated in this new
distributed computing system.

REFERENCES
[1]

Jun He, Jiyou Xu and Xin Yao, (September 2000) “Solving Equations by Hybrid Evolutionary
Computation Techniques”, IEEE Transactions on Evolutionary Computations, Vol. 4, No. 3, pp.
229-235.

[2]

A.R.M. Jalal Uddin Jamali, Md. Bazlar Rahman and M.M.A. Hashem, (2005), “Solving Linear
Equations by Classical Jacobi-SR Based Hybrid Evolutionary Algorithm with Time-Variant Adaptation
Technique”, Ganit: Journal of Bangladesh Mathematical Society, Vol. 24, No. 24, pp. 67-79.

[3]

A.R.M. Jalal Uddin Jamali, M.M.A. Hashem and Md. Bazlar Rahman, (2004), “An approach to Solve
Linear Equations Using a Time-Variant Adaptation Based Hbrid Evolutionary Algorithm”,
Jahangirnagar University Journal of Science, Vol. 27, pp. 277-289.

[4]

Jamali A.R.M.J.U., (2004), “Study of Solving Linear Equations by Hybrid Evolutionary Computation
Techniques”, M.Phil Thesis, Khulna University of Engineering & Technology, Khulna, Bangladesh.

[5]

Hashem, M.M.A., (1999) “Global Optimization through a New Class of Evolutionary Algorithm,”
Ph.D. dissertation, Diss. No. 19, Saga University, Japan, pp. 1-25.

[6]

K. Watanabe and M.M.A. Hashem, (2004) “Evolutioary Computations: New Algorithms and their
Applications to Evolutionary Robots”, Vol. 3, Springer-Verlag, Berlin.

[7]

E. Alba and M. Tomassini, (October 2002), “Parallelism and Evolutionary Algorithms”, IEEE
Transactions on Evolutionary Computations, Vol. 6, No. 5, pp. 443-462.

[8]

K. C. Tan, Y. J. Yang and C. K. Goh, (October 2006), “A Distributed Cooperative Coevolutionary
Algorithm for Multiobjective Optimization”, IEEE Transactions on Evolutionary Computation, Vol.
10, No. 5.

[9]

David H. Wolpert and William G. Macready, (April 1997), “No Free Lunch Theorems for
Optimization”, IEEE Transactions on Evolutionary Computation, Vol. 9, No. 1, pp. 67-82.

[10]

David H. Wolpert and William G. Macready, (December 2005), “Coevolutionary Free
Lunches”, IEEE Transactions on Evolutionary Computation, Vol. 9, No. 6, pp. 721-734.

[11]

M. Dubreuil, C. Gagńe, and M. Parizeau, (February 2006), “Analysis of a Master-Slave Architecture for
Distributed Evolutionary Computations”, IEEE Transactions on Systems, Man and Cybernetics-Part B,
Vol. 36, No. 1, pp. 229-235.
47

International Journal of Distributed and Parallel Systems (IJDPS) Vol.2, No.6, November 2011
[12]

J. J. Grefenstette, (1981), “Parallel adaptive algorithms for function Optimization”, Vanderbilt
University, Nashville, TN, Tech. Rep, CS- 81-19.

[13]

P. B. Grosso, (1985), “Computer simulation of genetic adaptation Parallel subcomponent interaction
in a multilocus model”, Ph. D. dissertation, Uni. Michigan, Ann Arbor.

[14]

B. Paechter, T. Bӓck, M. Schoenauer, M. Sebag, A. E. Eiben, J. J. Merelo, and T. C. Fogarty,
(2000), “A distributed resource evolutionary algorithm machine (DREAM)” in Proceedings of
CEC’00. IEEE Press, pp. 951–958.

[15]

S.Cahon, N. Melab and E. Talbi, (2004), “ParadisEO: A framework for the reusable design of parallel
and distributed metaheuristics”, Journal of Heuristics, pp. 357-380.

[16]

J.Costa, N. Lopes and P. Silva, “JDEAL: The java distributed evolutionary algorithms library”,
http://laseeb.isr.istutl.pt/sw/jdeal/home.html.

[17]

K. C. Tan, A. Tay and J. Cai, (August 2003), “Design and implementation of a distributed evolutionary
computing software”, IEEE Transactions on Systems, Man and Cybernetics, Part C, Vol. 3, pp. 325338.

[18]

S. Luke, L. Panait, G. Balan, S. Paus, Z. Skolicki, J. Bassett, R. Hubbley and A. Chircop,(2005), “ECJ
1: A java-based evolutionary computation and genetic programming research system”.

[19]

Message Passing Interface Forum (1994). MPI: A message-pasing interface standard, Int. J.
Supercomputer. Application, Vol. 8, No. 3, pp. 165-414.

[20]

C. Gagné and M. Paizeau, (2002), “Open BEAGLE: A New Versatile C++ framework for evolutionary
computation”, in Late Breaking Papers of GECCO 2002, New York, NY, USA.

[21]

Alaa Ismail El-Nashar, (May 2011), “Parallel Performance of MPI Sorting Algorithms on DualCore Processor Windows-Based Systems”, International Journal of Distributed and Parallel
Systems (IJDPS), Vol. 2, No. 3, pp. 1-14.

[22]

Hector Garcia-Molina, (1982), “Elections in a Distributed Computing System”, IEEE Transactions
on Computers, Vol. 31, No. 1, pp. 48-59.

[23]

Shahid H. Bokhari, (1988), “Partitioning Problems in Distributed Parallel, Pipelined, and
Distributed Computing”, IEEE Transactions on Computers, Vol. 37, No. 1, pp. 48-57.

[24]

Moslema Jahan, M. M. A Hashem and G. A. Shahriar, (2008), “A New Distributed Evolutionary
Computation Technique for Solving Large Number of Equations”, IEEE 11th International
Conference on Computer and Information Technology (ICCIT).

[25]

Christopher Moretti, Hoang Bui, Karen Hollingsworth, Brandon Rich, Patrick Flynn and Douglas
Thain, (2010), “ All-Pairs: An Abstraction for Data-Intensive Computing on Campus Grids”,
IEEE Transactions on Parallel and Distributed System, Vol. 21, No. 1, pp. 33-46.

[26]

Gerald, C. F. and P.O. Wheatley, (1994), “Applied Numerical Analysis (5th edition)”, Addison-Wesley,
New York.

[27]

Engell-Mǘllges, G.E. and F. Uhlig, (1999), “Numerical Algorithms with C”, Springer-Verlag,
Heidlberg.

[28]

Rashid Mehmood, Jon Crowcroft, (2005), “Parallel iterative solution method for large spare
linear equation systems”, Technical Report, University of Cambridge Computer Library,
Cambridge, UK, UCAM-CL-TR-650, ISSN 1476-2986.

[29]

Alaa Ismail El-Nashar, (March 2011), “To Parallelize or Not to Parallelize, Speed up Issue”,
International Journal of Distributed and Parallel Systems (IJDPS), Vol. 2, No. 2, pp. 14-28.

48

International Journal of Distributed and Parallel Systems (IJDPS) Vol.2, No.6, November 2011
Authors
Moslema Jahan achieved the B.Sc. Engg. Degree (with honours) in Computer
Science and Engineering (CSE) from KhulnaUniversity of Engineering &
Technology (KUET), Khulna, Bangladesh. Currently she is serving as a Lecturer in
the Department of Computer Science & Engineering in Dhaka University of
Engineering & Technology (DUET), Gazipur. Her research interest is on Parallel
and Distributed computing, Evolutionary Computation, Networking and Image
processing. Moslema Jahan is now Member of the Engineers Institution,
Bangladesh (IEB).
M. M. A. Hashem received the Bachelor’s degree in Electrical & Electronic
Engineering from Khulna University of Engineering & Technology (KUET),
Bangladesh in 1988. He acquired his Masters Degree in Computer Science from
Asian Institute of Technology (AIT), Bangkok, Thailand in 1993 and PhD degree
in Artificial Intelligence Systems from the Saga University, Japan in 1999. He is a
Professor in the Department of Computer Science and Engineering, Khulna
University of Technology (KUET), Bangladesh. His research interest includes Soft
Computing, Intelligent Networking, Wireless Networking, Distributed Evolutionary
Computing etc. He has published more than 50 referred articles in international Journals/Conferences. He
is a life fellow of IEB and a member of IEEE. He is a coauthor of a book titled “Evolutionary
Computations: New Algorithms and their Applications to Evolutionary Robots,” Series: Studies in
Fuzziness and Soft Computing, Vol. 147, Springer-Verlag, Berlin/New York, ISBN: 3-540-20901-8,
(2004). He has served as an Organizing Chair, IEEE 2008 11th International Conference on Computer
and Information Technology (ICCIT 2008) and Workshops, held during 24-27 December, 2008 at KUET.
Currently, he is working as a Technical Support Team Consultant for Bangladesh Research and Education
Network (BdREN) in the Higher Education Quality Enhancement Project (HEQEP) of University Grants
Commission (UGC) of Bangladesh.
Gazi Abdullah Shahriar achieved the B.Sc. Engg. Degree in Computer Science and
Engineering (CSE) from Khulna University of Engineering & Technology (KUET),
Khulna, Bangladesh. Now he is working at Secure Link Services BD Ltd as software
engineer. His current research interest is in Evolutionary computation, Distributed
computing and Bioinformatics.

49

