A New Distributed Evolutionary Computation
Technique for Multi-Objective Optimization
Md. Asadul Islam1, G.M. Mashrur-E-Elahi2, M.M.A. Hashem3
Department of Computer Science and Engineering
Khulna University of Engineering & Technology (KUET)
Khulna 9203, Bangladesh
asad_kuet@yahoo.com1, ranju2k4cse_kuet@yahoo.com2, mma_hashem@hotmail.com3

Abstract— Now-a-days, it is important to find out solutions of
Multi-Objective Optimization Problems (MOPs). Evolutionary
Strategy helps to solve such real world problems efficiently and
quickly. But sequential Evolutionary Algorithms (EAs) require
an enormous computation power to solve such problems and it
takes much time to solve large problems. To enhance the
performance for solving this type of problems, this paper
presents a new Distributed Novel Evolutionary Strategy
Algorithm (DNESA) for Multi-Objective Optimization. The
proposed DNESA applies the divide-and-conquer approach to
decompose population into smaller sub-population and involves
multiple solutions in the form of cooperative sub-populations. In
DNESA, the server distributes the total computation load to all
associate clients and simulation results show that the time for
solving large problems is much less than sequential EAs. Also
DNESA shows better performance in convergence test when
compared with other three well-known EAs.
Keywords- Novel evolutionary algorithm; time variant mutation;
subpopulation; MOPs; Distributed computing;

I.

INTRODUCTION

Multi-Objective optimization optimize a set of conflicting
objectives simultaneously. MOP is a very important research
topic, not only for the Multi-Objective nature of most realworld decision problems, but also there are still many open
questions in this area. Traditionally, there are several methods
available in the Operational Research (OR) literature for
solving MOPs as mathematical programming models [1]. None
of the OR methods treats all the objectives simultaneously
which is a basic requirement in most MOPs. In addition, these
methods handle MOPs with a set of impractical assumptions
such as linearity and convexity. In MOPs, there is no single
optimal solution, but contains a set of alternative solutions.
These solutions are optimal in the wider sense since there is no
other solutions in the search space that is superior to them
when all objectives are simultaneously considered. They are
known as pareto-optimal solutions or non-dominated solutions
[2][3]. In principle, multiobjective optimization is difficult than
the single-objective optimization. In single objective
optimization, one attempts to obtain the best design or decision,
which is usually the global minimum or the global maximum
depending on the optimization problem.

Recently, EAs are found to be useful for solving MOPs [4].
EAs have some advantages over traditional OR techniques.
This allows us to find several members of the Pareto-optimal
set in a single run of the algorithm [5]. Also, there is no
requirement for differentiability of the objective functions and
the constraints. Moreover, evolutionary algorithms are
susceptible to the shape of the Pareto front and can easily deal
with discontinuous or concave Pareto front. There is no wellaccepted method for MOPs that will produce a good set of
solutions for all problems. Also, sequential EAs require an
enormous computing power and take much time to solve large
problems. This motivates the further development of good
approaches to MOPs.
This paper proposes a parallel evolutionary algorithm called
Distributed Novel Evolutionary Strategy Algorithm (DNESA)
for MOPs, which is developed from a sequential evolutionary
algorithm called Novel Evolutionary Strategy (NES) algorithm
[10]. The proposed DNESA uses parallel approach to find out
the member of pareto-optimal solution, which is more
promising than sequential approach. Also diversity of
population and fast convergence are achieved by using
subpopulation and parallelization. In DNESA, the server
divides the problem loads into all associate clients and the
simulated results show that it takes less time to solve large
problems than sequential EAs. For the convergence test,
DNESA is compared with three algorithms namely Pareto
Enveloped-based Selection Algorithm (PESA) [6], NonDominated Sorting Genetic Algorithm (NSGA-II) [7] and the
Strength Pareto Evolutionary Algorithm (SPEA-2) [8]. The
compared results showed that DNESA achieved better
convergence with respect to other three algorithms.
The organization of the paper is as follows. Section II
discusses various existing techniques of Multi-Objective
optimization. A brief discussion about the proposed approach is
presented in section III. Experimental setup and results is
presented in section IV. Section V concludes the paper.
II.

BACKGROUND INFORMATION

A. Problem Definition
The MOPs [9] (also called multicriteria optimization,
multiperformance or vector optimization problem) can be

defined as the problem of finding a vector of decision variables
x, which optimizes a vector function

satisfies inequality


and equality constraints


and whose elements represent the objective functions. These
functions form a mathematical description of performance
criteria, which are usually in conflict with each other. Hence,
the term optimization means finding such a solution, which
would give the values of all the objective functions acceptable
to the decision maker. These objective functions constitute a
multi-dimensional space in addition to the usual decision
space. This additional space is called the objective space, Z.
For each solution x in the decision variable space, there exist,
a point in the objective space:

In Multi-Objective optimization, the concept of Pareto
dominance and Pareto optimality will form the basis of solution
quality. Specifically, the important concepts are defined as
follows.
Definition 1: Consider without loss of generality the
following multiobjective optimization problem with m decision
variables x (parameters) and n objectives y:
Minimizes



Where

and where x is called decision (parameter) vector, X parameter
space, y objective vector and Y objective space. A decision
vector
is said to dominate a decision vector
(also written as)
if and only if:


Additionally, we say a covers b
or
.

if and only if

B. Existing Approaches
There are many Multi-Objective Evolutionary Algorithms
(MEAs) for solving MOPs. They are classified as plain
aggregating, population-based non-Pareto and Pareto-based
approaches [1]. According to this classification, various types
of EAs for MOPs are discussed here. The Random Sampling
Evolutionary Algorithm (RAND) [4] generates randomly a
certain number of individuals per generation. RAND generates
individual according to the rate of crossover and mutation.
One of the popular population-based non-Pareto approaches
is Vector Evaluated Genetic Algorithm (VEGA) [14]. In this
approach, the total population is divided into sub populations
based on the number of objective functions to be optimized.
Each sub population is used to optimize each objective function
independently. The crossover and mutation operators are used
to shuffle the population together. According to Schaffer the
solutions generated by VEGA were non-dominated in a local
sense, because their non-dominance was limited to the current
population, and while a locally dominated individual is also
globally dominated, the converse is not necessarily true. There
are also a non-Pareto approach that uses the weighted sum
method for fitness assignment which is known as Hajelas and
Lins genetic algorithm (HLGA) [15]. A weight between zero
and one is assigned to each objective, with the sum of all
weight being exactly equal to one. To search for multiple
solutions in parallel, the weights are encoded in the genotype.
Phenotypic fitness sharing is used to maintain diversity of the
weight combinations. The EA evolves solutions and weight
combinations simultaneously.
The dominated and non-dominated solutions in the current
population are separated in the Pareto-based approaches.
Goldberg [16] suggested a non-dominated ranking procedure to
decide the fitness of the individuals. After that based on the
idea Golgerg, Srinivas and Dev [12] introduced Nondominated Sorting Genetic Algorithms (NSGA).
In this method, the fitness assignment is carried out
through several steps. In each step, the non-dominated
solutions constituting a non-dominated frontier are assigned the
same dummy fitness value. These solutions have the same
fitness values and are ignored in the further classification
process. Finally, the dummy fitness is set to a value less than
the smallest shared fitness value in the current non-dominated
frontier. Then the next frontier is extracted. This procedure is
repeated until all individuals in the population are classified.
Fonseca and Fleming [17] proposed a slightly different scheme
which is known as Fonseca and Fleming’s genetic algorithm
(FFGA). In this approach, an individual’s rank is determined
by the number of individuals dominating it.
Horn and Nafpliotis [18] used phenotypic sharing on the
objective vectors. The common features of the Pareto-based
approaches mentioned above are that (i) the Pareto-optimal
solutions in each generation are assigned either the same fitness
or rank, and (ii) some sharing and niche techniques are applied
in the selection procedure. Recently, Zitler and Thiele [4]
proposed a Pareto-based method, the Strength Pareto
Evolutionary Algorithm (SPEA). The main features of this
approach are: it (i) sorts the non-dominated solutions externally
and continuously updates the population, (ii) evaluates an

individual’s fitness depending on the number of external nondominated points that dominate it, (iii) preserves population
diversity using the Pareto dominance relationship, and (iv)
incorporates a clustering procedure in order to reduce the nondominated set without destroying its characteristics.
Recently Pareto Differential Evolution (PDE) algorithm is
developed by Sarker et al [21] to handle multiobjective
optimization problems. In DE, each variable’s value in the
chromosome is represented by a real number. The approach
works by creating a random initial population of potential
solutions, where it is guaranteed, by some repair rules that the
value of each variable is within its boundaries. An individual is
then selected at random for replacement and three different
individuals are selected as parents. One of these three
individuals is selected as the main parent. With some
probability, each variable in the main parent is changed but at
least one variable should be changed. The change is undertaken
by adding to the variable’s value a ratio of the difference
between the two values of this variable in the other two parents.
In essence, the main parent’s vector is perturbed by the other
two parents’ vectors. This process represents the crossover
operator in DE. If the resultant vector is better than the one
chosen for replacement, it replaces it; otherwise the chosen
vector for replacement is retained in the population.
III.

PROPOSED APPROACH

EAs are stochastic search methods that have been applied
successfully in many search, optimization, and machine
learning problems. Unlike most other optimization techniques,
EAs maintain a population of encoded tentative solutions that
are manipulated competitively by applying some variation
operators to find a satisfactory, if not globally optimum
solution. Parallelism of evolutionary algorithm is performed to
speed up the computation. NES algorithm [10] solve problem
by using sequential approach. But it takes much time to achieve
solution. In the proposed approach parallelization of the
sequential NES algorithm is performed. The proposed
distributed evolutionary approach is named as Distributed
Novel Evolutionary Strategy Algorithm( DNESA). Fig 1.
MOOP
Minimize f1
Minimize f2
…………..
Minimize fM

shows the approach of Multi-Objective optimization technique
that is used in this paper. Multiple single objectives function
are combined on the basis of high level information. Each
single objective function are multiplied by a suitable weight
factor. After that, functions are added and converted to single
objective function. This single objective function is optimized
by using the approach of single objective optimization.
A. Distributed Novel Evolutionary Strategy Algorithm
(DNESA)
The availability of powerful-networked computers presents
a wealth of computing resources to solve problems with large
computational effort. As the communication level in coarsegrained parallelization is low as compared to other
parallelization strategies, it is a suitable computing model for
distributed networks with limited communication speeds. A
model of distributed computing is shown in Fig 2.
The parallelization approach is considered here, where
large problems are decomposed into smaller subtasks that are
mapped into the computers available in a distributed system.
The flowchart of the proposed DNESA is illustrated in
Figure 3. The initialization process involves the creation of
subpopulations of random individuals, where the ith
subpopulation will represent the ith decision variable. The
individuals will then undergo the competitive-cooperation
Subpopulation 1
Client PC1
Subpopulation 2
Client PC2
Server PC
Creates n
Subpopulations and
sends to n clients

Subpopulation n

Figure 2. A model of DNESA.

High level
information
Estimate a relative
importance Vector
(w1,w2,…….., wM)

Single objective
optimization problem
F = w1f1 + w2f2 +
…….. + wMfM
Optimul solution
Single
objective
optimizer
Figure 1. Approach of Multi-Objective Optimization

Client PCn

process until the stopping criteria is satisfied, which can be set
based upon a fixed number of function evaluations. In this
work, the number of fitness function evaluations is determined
according to past experience and complexity of the test
functions, which can be in multiples of the number of decision
variables.
Server generates the initial population and it also initializes
the parameters such as generation number and size of the
subpopulation. After that, the server calculates the initial fitness
value of each individual so that individuals can be ordered and
subpopulations can be generated. The condition is checked so
that the generation number could not exceed maximum
generation number. If so then the process is stopped and the
result is reported. Subpopulations are generated according to
the number of clients. Each subpopulation is assigned to each
client and server waits for the result to come from the clients.

Server Program Flow chart
Client Program Flow chart

Start

Begin
Create Initial Population
Check Status
Evaluate Initial Fitness
No
Order Population

Assign Jobs?
Yes

Yes

Perform Crossover

Finished?
No

Perform Mutation

Create Subpopulation
Send to Client i

Evaluate Fitness

Send Subpopulations to all the clients
Send Subpopulation to Server
Sleep
Yes

Receive all Subpopulation?

No

Receive from Client i
Submit Results

Stop

Figure
3. Theby
program
chartexecution
of DNESA. time than sequential approach. Sequential EAs
A client checks status and waits until any job
assigns
the Flow
much
server. If any job assigns by the server a client begins process.
executes each subpopulation sequentially.
At the first step it finds out the representative and performs
IV. EXPERIMENTAL SETUP AND RESULTS
subpopulation based max min crossover (SBMAC) [10]
operation to the representative for generating new
Six benchmark problems are solved by using DNESA. The
subpopulation. After SBMAC, client performs time variant
DNESA algorithm is implemented in the lab environment,
mutation(TMV) [10] for diversity among the generated
where maximum 10 computers are used as clients and one
individuals. Finesses are evaluated at the next stage. Then the
computer as server. The communication between server and
fitness value and parameter values are returned to the server.
clients are established using Local Area Networking (LAN).
The server checks that all subpopulations are received from
Both the server and clients programs are written in C#.net
clients, if so then it go back to order generation phase and
framework and communication is done using socket
repeat the operation until the generation number reach the
programming. Initial population size, maximum number of
maximum number of generation or the fitness value reached
generation varies problem to problem. The crossover rate and
the expected goal.
mutation rate are same for all problems. The initial population
is generated by using a Uniform Random Number (URN)
In this parallel approach, for a particular generation all the
within desired domain of the object variables. After evaluating
subpopulations are send to the clients at a time and thus
the fitness value of initial individuals, this population is
execution of each subpopulation is done at a time, which saves

considered as parents for the next generation. SBMAC [10] and
DEFINITION OF TEST PROBLEMS

TABLE I.
Definition of Problems
Problem P1[10]:

where Problem P2[11]:

The DNESA is compared with some other MEAs to
compare the performance of DNESA with respect to those
algorithms. There are three other MEAs are used to compare
with the proposed one. The MEAs are the PESA [6], NSGA-II
[7] and SPEA2 [8]. Two benchmark problems are used for this
comparison. The problems are DLTZ1 (P5) and DLTZ2 (P6).
Each algorithm is compared with each other with respect to
each problem. The algorithms are compared according to the
convergence metric. Convergence represent the distance
between the converged non-dominated solution and the global
pareto-optimal front, hence lower values of convergence metric
represent good convergence ability. Therefore, lower the value
of convergence of an algorithm is more superior.

for
∑

⁄√

∑

⁄√

where
Problem P3[12]:

for

where
Problem P4[13]:

where
for
Problem P5(DLTZ1)[9]:

A. Convergence for Problem DLTZ1 (P5)
A lower convergence metric value implies better result.
Following sections present results for convergence on the
DLTZ1 test problem. The DNESA gives the better
performance than PESA, SPEA2 and NSGA-II in terms of
convergence for the DLTZ1 problem. PESA is better than
SPEA2 and NSGA-II but not better than DNESA. SPEA2 and
NSGA-II have similar performances. The data are taken for 20
and 50 individuals with a fixed generation of 300. From 30
runs with different sample path, the average value of
convergence are calculated for the DNESA algorithm. The data
for the PESA, SPEA2 and NSGA-II are recorded form data
sheet of [9].

.
.
.

for
where
Problem P6(DLTZ2)[9]:

–
);

.
.
.

TABLE II.
Gen
No.

Runs

300

30

MEAN CONVERGENCE VALUE (CV) FOR PROBLEM DLTZ1
Indivi
duals
20
50

DNESA

PESA

SPEA2

0.00129
0.00128

2.86948
0.04419

3.08825
0.04843

NSGAII
2.27666
0.38360

From the data TABLE II, it is shown that for 20 individuals
convergence value of DNESA is much better than other
algorithms. For 50 individuals also DNESA is the best among
the algorithms.

for
where

TMV [10] are used for crossover and mutation respectively
time is reducing with increasing the number of clients, but after
a certain number of clients it does not reduce time periodically.
Also with the increasing clients, the ratio of the time reduction
decreases due to extra time needed for the communication
among the clients and server.

–

The proposed DNESA use server client model, where
server controls multiple clients. It needs much less time to
solve problems rather than single clients. When the number of
clients increases, it reduce the time to find out optimal solution.
Four problems (P1, P2, P3 and P4) in TABLE I are tested to
find out the relationship between time needed to find optimal
solution and number of clients. The experimented results are
shown as plotted graph in Fig. 4 for the problems. From Fig.
4(a), it is shown that when single client is used for problem P1
then it takes much time to find optimal solution. But increasing
the number of clients, it is shown that the time for finding the
optimal solution is reduced. Also for problems P2 and P4 in
Fig. 4(b) and Fig. 4(d), it is shown that increasing the number
of clients reduced the execution time for finding optimal
solution. But for problem P3 in Fig. 4(c) shows that initially

B. Convergence for Problem DLTZ2 (P6)

DNESA gives the better performance than SPEA2 and
NSGA-II but not better than PESA in terms of convergence for
the DLTZ2 problem. PESA is better than NESA, SPEA2 and
NSGA-II. SPEA2 and NSGA-II have similar performances.
The data are taken for 20 and 50 individuals with a fixed
generation of 300. From 30 runs with different sample path, the
average value of convergence are calculated for the DNESA
algorithm. The data for the PESA, SPEA2 and NSGA-II are
recorded form data sheet of [9].
TABLE III.
Gen
No.

Runs

300

30

MEAN CONVERGENCE VALUE (CV) FOR PROBLEM DLTZ2
Indivi
duals
20
50

DNESA

PESA

SPEA2

0.00138
0.00083

8.40E-05
0.00035

0.00026
0.00663

NSGAII
0.00179
0.01003

[4]

[5]

(a)

(b)

[6]

[7]

(c)

(d)

[8]

Figure 4.Time needed to find optimal solution with respect to number of
clients for problems P1(a), P2(b), P3(c), P4(d).

[9]

From the data TABLE III, it is shown that for 20
individuals, convergence value of DNESA is much better than
SPEA2 and NSGA-II but not better than PESA. For 50
individuals also DNESA is the better than SPEA2 and NSGAII but little worse than PESA.

[10]

The DNESA is developed from NES algorithm and uses
minimum genetic drift. Due to minimum genetic drift in
DNESA, the DNESA shows better performance in
convergence than other three algorithms.
V.

CONCLUSION

In this paper a distributed evolutionary computation
technique for Multi-Objective Optimization problems is
proposed. This distributed approach helps to achieve the
optimal solution quickly for solving MOPs. In DNESA, total
population is divided into subpopulations. This subpopulation
concept makes easy to parallelize NES algorithm.
Subpopulations are assigned to each client to find out optimal
solution. All clients perform in parallel. Hence, the time to find
the solution is greatly reduced. Four benchmark problems
namely P1, P2, P3 and P4 are used to show the relationship
between the numbers of clients versus the time needed to find
out an optimal solution. DNESA is also compared with PESA,
SPEA2 and NSGA-II for convergence metrics. Two
benchmark problems namely P5 and P6 are used for
comparison. The convergence value for the proposed DNESA
is better than other three algorithms.

[11]

[12]

[13]
[14]

[15]

[16]

[17]

[18]

[19]

REFERENCES
[1]

[2]
[3]

Carlos A. Coello Coello ”A comprehensive survey of evolutionarybased multiobjective optimization techniques.” Knowledge and
Information Systems, VOL.1 NO. 3, pp. 269 - 308, 1998.
Chankong V., Haimes, Y.Y ”Multiobjective decision making theory and
methodology”. New Work: North Holland, 1983.
Hans, A.E.” Multicriteria optimization for highly accurate systems.
Multicriteria Optimization in Engineering and Sciences”, W.

[20]

[21]

Stadler(ED.), Mathematical concept and methods in science and
engineering, VOL. 19, pp. 309 - 352. New York:Plenum oress, 1988.
Eckart Zitzler and Lothar Thiele. ”Multiobjective Evolutionary
Algorithms: A Comparative Case Study and the Strength Pareto
Approach”. IEEE Transactions on Evolutionary Computation, VOL. 3,
NO. 4, pp. 257 - 271, November 1999
Coello C A C.” Evolutionary multiobjective optimization: a historical
view of the field.” IEEE Computational Intelligence Magazine ,VOL.1,
NO. 1, pp. 28 - 36 ,February 2006.
David W. Corne, Joshua D. Knowles, and Martin J. Oates. ”The Pareto
Envelope-based Selection Algorithm for Multiobjective Optimization”.
Proceedings of The Parallel Problem Solving from Nature VI
Conference, pp. 839 - 848, Paris, France,Springer Publication, 2000.
Kalyanmoy Deb, Samir Agrawal, Amrit Pratab, and T. Meyarivan.” A
Fast Elitist Non-Dominated Sorting Genetic Algorithm for MultiObjective Optimization: NSGA-II.” Proceedings of the Parallel Problem
Solving from Nature VI Conference, pp. 849 - 858, Paris, France,
Springer Publication, 2000.
Eckart Zitzler, Marco Laumanns, and Lothar Thiele. ” SPEA2:
Improving the Strength Pareto Evolutionary Algorithm.” May 2001.
V.Khare, X. Yao and K.Deb, ”Performance Scaling of Multiobjective
Evolutionary Algorithms”, In Proc, 2nd Int. Conf. Evolutionary Multicriteria Optimization, pp. 376 - 390,Springer Publication, 2003.
Hashem, M. M. A., ”Global Optimization Through a New Class of
Evolutionary Algorithm”, Ph.D. dissertation, Diss. No. 19, Saga
University, Japan, pp. 1 - 25, 1999.
K. C. Tan, Y. J. Yang, and C. K. Goh, ” A Distributed Cooperative
Coevolutionary Algorithm for Multiobjective Optimization”, IEEE
Transactions on Evolutionary Computation, VOL. 10, NO. 5, pp. 527549, October 2006.
N. Srinivas and Kalyanmoy Deb, ” Multiobjective Optimzation Using
Nondominated Sorting in Genetic Algorithms” , Proceedings of
Evolutionary Computation, Indian Institute of Technology, Kanpur,
VOL. 2, pp. 221 248, 1994.
Ehrgott M, ”Multicriteria optimization.” Springer, second edition, 2005.
Schaffer, J, ”Multiple objective optimization with vector evaluated
genetic algorithms”. Proceedings of the First International Conference
on Genetic Algorithms, pp. 93 - 100, L. Erlbaum Associates Inc
publisher,Hillsdale, NJ, USA, 1985.
Hajela, P. and C. Lin , ”Genetic search strategies in multicriterion
optimal design”. Structural Optimization, VOL. 4,NO. 2, pp. 99 - 107,
June 1992.
Goldberg, D.,” Genetic algorithms: in search, optimisation and machine
learning”. Addison-Wesley Longman Publishing Co., Inc. Boston, MA,
USA, 1989.
Fonseca, C. and P. Fleming ,” Genetic algorithms for multiobjective
optimization: Formulation, discussion and generalization.” Proceedings
of the Fifth International Conference on Genetic Algorithms, San Mateo,
California, pp. 416 - 423, 1993.
Horn, J., N. Nafpliotis, and D. Goldberg ,” A niched pareto genetic
algorithm for multiobjective optimization.” Proceedings of the First
IEEE Conference on Evolutionary Computation VOL. 1, pp. 82 - 87,
1994.
Knowles, J. and D. Corne ,” The pareto archived evolution strategy: a
new baseline algorithm for multiobjective optimization.” In 1999
Congress on Evolutionary Computation, Washington D.C., IEEE
Service Centre, pp. 98 - 105, 1999.
Knowles, J. and D. Corne ,” Approximating the nondominated front
using the pareto archived evolution strategy.” Evolutionary
Computation, VOL. 8, NO. 2, pp. 149 - 172. MIT Press Cambridge,
MA, USA, 2000.
Abbass, H., R. Sarker, and C. Newton .” A pareto differential evolution
approach to vector optimisation problems.” Congress on Evolutionary
Computation 2, 971–978. 2001

