MINISTRY OF EDUCATION AND TRAINING MINISTRY OF NATIONAL DEFENSE

MILITARY TECHNICAL ACADEMY NGUYEN LONG A MULTI-OBJECTIVE EVOLUTIONARY
ALGORITHM USING DIRECTIONS OF
IMPROVEMENT AND APPLICATION

THE THESIS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY
IN MATHEMATICS


Code: 62 46 01 10
THE THESIS IS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS
FOR THE DEGREE OF DOCTOR OF PHILOSOPHY IN MATHEMATICS
SUPERVISORS:
1. ASSOC. PROF. DR BUI THU LAM
2. ASSOC. PROF. DR NGUYEN VAN HAI Hanoi - 2014 Abstract
Amulti-objectiveoptimizationprobleminvolvesatleasttwoconflictingobjectivesandithas
a set of Pareto optimal solutions. Multi-objective evolutionary algorithms (MOEAs) use a
population of solutions to approximate the Pareto optimal set in a single run. MOEAs have
attracted a lot of research attention during the past decade. They are still one of the hottest
research areas in the field of Computation al Intelligence and they are the main focus of th i s
thesis.
Firstly, the main concepts for multi-objective optimization are presented, then the thesis con-
cerns about mentions the solving multi-objective optimization problems by multi-objective
evolutionary algorithms. This thesis also conducts a sur vey on the usage of directorial infor-

II. The pr o posed system helps use rs to have m or e good choices for the Sp a m Assa ssi n
system in configuration.
iii
Acknowledgeme nts
The first of all, I would like to express my r espectful thanks to my principal sup er vi sor ,
Assoc.Prof. Bui Thu Lam for his directly guid a n ce to my PhD progress. Assoc.Prof. Bui
has given me knowledge and passion as the motivation of this thesis. His valued guidance
has inspired much of the research in the thesis.
I also wish to thank my co-supportive Assoc.Prof. Nguyen Van Hai for his suggestions and
knowledge during my research, especially the relation b etween theories and real problems in
work. I a l so would like to thank Prof. Hussein Abbass, Assoc.Prof. Tran Quang Anh and
Assoc.Prof. Dao Thanh Tinh for their invaluable support throughout my PhD. I feel lucky
to work with such excellent people.
IalsowouldliketothankallofmyfellowsintheDepartmentofSoftwareTechnologyand
Evolutionary Computation research group for their assistance and support.
Last but not least, I also would like to acknowledge the supp ort of my family, especially my
parents Dr. Nguyen Nghi, Truong Thi Hong, they worked hard an d believed strongly in their
children. I also would like to thanks my wife, sisters, brothers who always support me during
my research.
iv
Originality Statement
Iherebydeclarethatthisthesisismyownwork,withmyknowledgeandbeliefthethesis
has no material previously publish ed or written by others. Any contributions made to the
research by colleagues, with people in our research team at Le Qu y Don Technical University
or elsewhere, during my candidature is clearly acknowledged.
Ialsodeclarethattheintellectualcontentinthissubmissionistheresearchresultsofmyown
work, except to the extent that assistance from others in conception or in style, presentation
and linguistic expression is acknowledged.
v
Contents

2.4 Statistical testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.5 Search’s guidance in MOEAs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.5.1 Technique of using guided directions . . . . . . . . . . . . . . . . . . . 32
2.5.2 Advantages and disadvantages . . . . . . . . . . . . . . . . . . . . . . . 45
2.6 Research Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.6.1 Direction based multi-objective evolutionary algorithm (DMEA) . . . . 48
2.6.2 Issue 01: The disadvantages of the fixed ratio between types of directions 51
2.6.3 Issue 02: Lack of an efficient niching metho d for the main population . 52
2.6.4 Issue 03: The disadvantages of using the weighted sum scheme . . . . . 53
2.6.5 Issue 04: Using a ’hard’ niching method . . . . . . . . . . . . . . . . . 53
2.6.6 Issue 05: Investigating on how the DM can interact with DMEA. . . . 53
2.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3 A guided methodology using directions of improvement 55
3.1 Using an adaptive ratio between convergence and spread directions . . . . . . 55
3.2 Using a Ray based density niching for the main po p u l a ti o n . . . . . . . . . . . 56
3.3 Using a ray based density selection schemes . . . . . . . . . . . . . . . . . . . 59
3.4 Direction based Multi-objective Evolutionary
Algorithm-II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.4.1 General structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.4.2 Computational complexity . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.4.3 Experimental Studies . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
vii
3.4.4 Results and Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.5 Analyzing e↵ects of di↵erent selection schemes for the perturbation . . . . . . 81
3.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
4 A guided methodology using interaction with decision makers 87
4.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
4.2 A multi-point Interactive method for DMEA- II . . . . . . . . . . . . . . . . . 92
4.2.1 Rays replacement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
4.2.2 Rays Redistribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

2.10 An il l u s tr a t i on o f di r ect i o n al co nvergence and directional spread . . . . . . . . 41
2.11 An il l u s tr a t i on o f th e movement of a centroid . . . . . . . . . . . . . . . . . . 43
2.12 An il l u s tr a t i on o f convergence and spread directions . . . . . . . . . . . . . . . 44
2.13 An il l u s tr a t i on o f th e r ay system . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.14 An il l u s tr a t i on o f th e performance of DMEA . . . . . . . . . . . . . . . . . . . 52
3.1 An illustration of the Ray-based Density . . . . . . . . . . . . . . . . . . . . . 57
3.2 The obtained non-dominated of DMEA and D MEA- II . . . . . . . . . . . . . . 70
3.3 Results on DTLZ2, UF1, UF3 and UF8 . . . . . . . . . . . . . . . . . . . . . . 71
3.4 Visualization of GD and IGD overtime for ZDT1, ZDT4 . . . . . . . . . . . . 73
3.5 The chart for DMEA-II and DMEA comparison on GD, IGD an d HYP . . . . 79
3.6 The chart for DMEA-II and other MOEAs comparison on G D . . . . . . . . . 79
3.7 The chart for DMEA-II and other MOEAs comparison on I GD . . . . . . . . . 80
3.8 The chart for DMEA-II and other MOEAs comparison on HYP . . . . . . . . 80
3.9 The chart for DMEA-II and other MOEAs comparison on S C . . . . . . . . . 81
ix
3.10 Visu al i za t i on o f G D an d IGD over time for ZDT1, ZDT2 . . . . . . . . . . . . 84
3.11 Visu al i za t i on o f G D an d IGD over time for ZDT3, DTLZ3 . . . . . . . . . . . 85
4.1 An illustration of altering the referen ce point . . . . . . . . . . . . . . . . . . . 90
4.2 An illustration of the use reference directi o n a p p ro a ch . . . . . . . . . . . . . . 92
4.3 An illustration of the rays replacement approach . . . . . . . . . . . . . . . . . 94
4.4 An illustration of the rays redistribution approach . . . . . . . . . . . . . . . . 95
4.5 An Illustration of the value added niching approach . . . . . . . . . . . . . . . 97
4.6 A visualization of the interactive method on ZDT1 . . . . . . . . . . . . . . . 99
4.7 A visualization of the interactive method on ZDT2 . . . . . . . . . . . . . . . 99
4.8 A visualization of the interactive method on ZDT3 . . . . . . . . . . . . . . . 100
4.9 A visualization of the interactive method on ZDT4 . . . . . . . . . . . . . . . 100
4.10 A visualization of the interactive method on ZDT6 . . . . . . . . . . . . . . . 101
5.1 An illustration of results with 30 and 100 r u l es fo r 27 2 em ai l s . . . . . . . . . . 116
5.2 An illustration of results with 30 and 100 r u l es fo r 42 6 em ai l s . . . . . . . . . . 117
5.3 An illustration of results with 30 and 100 r u l es fo r 28 6 multilingual emails . . 118

xi
Abbreviations
Abbreviation Meaning
EA Evolutionary Algorithm
GA Genetic Algorithm
ES Evolution Strategies
EP Evolution Programming
GP Genetic Programming
MOP Multi-objective Optimization Problem
MOEA Multi-objective Evolutionary Algorithm
POF Pareto Optimal F ront
POS Pareto Optimal Set
RD Ray based Density
DMEA Direction based Mu l t i -objective Evolutionary Algorithm
DMEA-II Direction based Multi-objective Evolutionary Algorithm-II
NSGA-II Non-Dominated Sorting Genetic Algorit h m II
SPEA2 Strength Pareto Evolutionary Algorithm 2
MOEA/D Multi-objective Evolutionary Algorithm Based on Decomposition
MOGA Multi-objective Genetic Algorithm
NPGA Niched Pareto Genetic Algorithm
PAES Pareto-Archived Evolution Strategy
MOPSO Multi-objective Particle Swarm Optimization
PDE Pareto Di↵erential Evolution
DM Decision Maker
GD Generational Distance
IGD Inverse Generational Distance
HYP Hypervolume
SC Two Set Converge
SDR Spam Detection Rate
FAR False Alarm Rate

Gradient Direction
Hướng Gradient
Generational Distance
Khoảng cách thế hệ
Inverse Generational Distance
Khoảng cách thế hệ đảo
Hypervolume
Siêu diện tích
Spam Detection Rate
Tỷ lệ nhận dạng thư rác
False Alarm Rate
Tỷ lệ nhận dạng sai
Decision Maker
Người ra quyết định
Reference point
Điểm tham chiếu
Reference region
Vùng tham chiếu
Spam Detection System
Hệ thống lọc thư rác
Interactive method
Phương pháp tương tác

Chapter 1
Introduction
1.1 Overview
In many disciplines, optimization problems often have two or more objectives, which are
normally in conflict with others, and that we wish to optimize them simultaneously. These
problems are called multi-objective optimization problems (MOPs). In fact, MOPs normally
give rise not to one, but to a set of solutions (called a Pareto optimal set (POS)) which,

is called a genotype. The values at each bit location or locus are called alleles.
This genotype is generally composed of one or several chromosomes where each
chromosome is a composition of several genes. F or real-valued problems, this
genotype will be decoded into an array of real values (equivalent to a solution
of the problem) using a mapping function. This array is usually considered as a
phenotype.
– Real-valued : For this type of representation, t h e solution is represented by an
array of real values. This array is considered as a chromosome and each element of
this array is a gene. Here the genotype and phenotype are identical. Each element
of the array is considered a gene.
– Graph:Insomecases,theprobleminquestionistofindatopology,network,
or pr og r am of function containing a set of symbols. Here, a graph such as a tree
representation is more suitable. The genotype-phenotype mapping is even more
complicated than the one with binary representation.
2
1.1. OVERVIEW
Although the concept of an individua l is larger than the concept of a solution, for the
sake of simplicity, the thesis uses both of them interchangeably.
• Mutation operator:Mutationisforself-changinggenesinordertodevelopdi↵erent
characteristics. Based on this idea from biology, EAs use mutation to change values in
the genotype t o allow individuals to search surrounding areas. For a binary geno type,
mutation can simply be done through a bit-flipping operation along the string with
some probability. For a real-valued genotype, mutation is done by pertu r b i n g the
values of genes using some distribut i o n s such as Un i for m , Gaussian, or Cauchy. For a
tree genotype, a segment of the tree can be removed or moved to a di↵erent location
in the tree.
• Crossover operator:Thisproductionoperationallowsthecombinationofgenetic
materials from two or more parents to create o↵spring. In evolutionary computation,
crossover is u sed to create new individuals that have gene values from selected pa r ents.
The e↵ect of this operator is to potentially combine good elements of parents. For a

– Select the new population C( t +1).
– Advance to the new generation, i.e. t = t +1.
• End.
Based on di↵erent representations, conventional EAs have b een c at eg or i ze d as f ol lows [130]:
• Genetic Algorithms (GA): model genetic evolution and use binary representation.
• Evolution Strategies (ES):gearedtowardsmodelingthestrategyparametersthat
control variation in evolution and use real-valued vectors.
• Evolutionary Program mi ng (EP):derivedfromthesimulationofadaptivebehav-
ior in evolution (phenotypic evolution), currently evolutionary programming is a wide
evolutionary computing dialect with no fixed rep resentation.
• Genetic Programming (GP):basedongeneticalgorithms,butindividualsarepro-
grams (represented as trees).
Recently, researchers extended EA’s paradigms to Di↵erential Evolution (DE)[89], Particle
Swarm Optimization (PSO)[24] and Ant Colony Optimization (ACO)[111] etc.
In genetic algorithms, problems are encoded in a series of bit strings that are manipulated
by the algorithm. I n evolutionary, the decision variables a n d objective functions are used
directly. Both of genetic or evolutionary algorithms apply the principles of evolution found
4
1.1. OVERVIEW
in nature to find an optimal solution for an optimization problem.
In EAs, niching method s are used to allow EAs to maintain a diverse population of indi-
viduals. EAs that incorporate niching methods are capable of locating multiple, optimal
solutions within a single population. E↵ective niching methods are critical to s u ccess of EAs
in classification and machine learning, multi-modal optimization, multi-objective optimiza-
tion, and simulation of complex and adapti ve systems. Niching is also useful for findi n g
better, single solution to hard problems, the intermediate formation and m a i ntenance of di-
verse sub-solutions is often critical to the solution of hard problems. In [67] Mahfoud suggests
a classification based on the way that multiple niches are found in a EA:
• Spatial or Parallel Niching methods: Niching methods belonging to this category
find and maintain multiple niches simultaneously in a single population. Exampl e s of

make the search being not biased towards local optima, that is why EAs are suitable for
global optimization problems. When solving multi-objecti ve problems, EAs are adaptively
and e↵ectively used to obtain a set of approximated Pareto optimal solutions. However, EAs
also have some difficult i es such as: the obtained solu t i on s are approximated Pareto optimal
solutions so they are not really desired optimal solutions for the problems. It also requires
a high number of generations to get a good set of solutions. To avoid these disadvantages,
a hybridization model that combines MOEAs with search mechanisms to improve the per-
formance quality of t h e algorithms. The search techniques are d i scu ssed and widely used
in multi-objective optimization such as: particle swarm optimization (PSO) [96], ant colony
[111]. These techniques are used to guide the evolutionary process quick towards Pareto
optimal fronts (POFs) in objective space ( or POSs in decision space), and to avoid being
trapped in local optima. This guidance helps MOEAs to be improved in their exploitation
and exploratio n characterises and the quality of the obtained solutions. Using guided inf or -
mation is a pro m i si n g technique to get g ood a p p r oximated solutions, it helps MOEAs to be
improved in their quality and capacity. In fact, there are many approaches in using guided
information in MOEAs, one of these kinds of guided informati on is directional information in
MOEAs, namely gradient based directions [45, 38, 5, 107], di↵erential evolution [2, 62, 65, 23],
6
1.3. MOTIVATION
directions of improvement [49, 18, 14, 15, 19].
Solving MOPs by gradient based directions is early discussed and used in di↵erence ap-
proaches. In fac t, gradient based multi-objective algorithms have some advantages: This
algorithms can be used to sol ve complex di↵erentiable MOPs, gradient based direction s are
used so it makes multi-objective algorithms to be go od convergence rate, when incorpo-
rating with evolution strategy in a hybridization MOEA, the algorithms can have a good
convergence rate and avoid the local optimums during the search. However, there are some
difficulties in using gra d i ent based directions such as: The algorithms can n o t be used with
non-di↵erentiable MOPs, it requires a hight performance cost to determine gradient based
directions. There are several difficulties for gradient based algorithms such as: determining
descent, Pareto descent and directed directions, keeping the balance between exploitation

is a need to have more investigation on how to have an e↵ective guidance from both as-
pects: 1) Automatically guiding the evolutionary process to make MOEAs balanced between
exploitation and exploration. 2) Combining decision maker’s preference with directions of
improvement to guide MOEAs during optimal p r ocess towards the most preferred region in
objective space. The previous discussions represent the motivation of this thesis.
1.4 Questions and Hypothesises
In MOEAs, using directions of im p r ovement has been concerned in much research, some
techniques for using directional information in MOEAs are proposed in [89, 2, 3, 18, 14,
15, 19, 52]. However, we need to use guided information for the evolutionary proce ss in
an e↵ective way to help MOEAs be good per for m a n ce in optimal approximation. This is a
hard problem that many researchers have been tried to solve. These are the focal points of
the research reported in this thesis. In other words, this thesis aims to address the following
question: How to design an e↵ective guidance for MOEAs to move quickly towards
a suspected optimum or decision makers’ preferred region and also to avoid being
trapped too easily in a basin surrounding a local optimum? In order to answer this
question, this thesis gives some hypothesises:
• When incorporating evolutionary techniques with directions of improvement, those
techniques have again the e↵ect on the balance between exploitation and exploration
of the algorithms. There is a need to have a guidance for the evolutionary
8
1.5. THESIS ORGANIZATION
process to make the MOEA balanced between exploitation and exploration
automatically.
• The usage of directions of improvement that d er i ved from decision makers will make
the MOEAs to be better satisfied decision makers to find their preferred solutions.
There is a need to combine decision maker’s preference with directions of
improvement to guide MOEAs during the optimal pr ocess towards the most
preferred region in objective space.
1.5 Thesis organization
This thesis is organized in six chapters, the remainder of the thesis is arranged as following:

Redistribution, Value Added Niching on DMEA-II. This chapter suggests a way for
decision makers to join to evolutionary processes, decision makers’ preference informa-
tion is used to guide the MOEAs to be converged to their preferred region in objective
space. To validate the proposed method, the experi m ents are presented and discussed.
• Chapter 5. An application of DMEA-II f or Spam Email Detection System is introduced.
The proposal is a multi-objective optimization approach for generating sets of feasible
trade-o↵ solutions for an anti-spam email system (using Apache SpamAssassin). The
experiments on Vietnamese language databases and rules are implemented. The results
indicated that, when solving the pro b l em using DMEA-II, it achieved more efficient
results but also created a set of ready-to-use rule scor es
• Chapter 6. Conclusions and future works are given.
1.6 Original Contributions
Using evolutionary algorithms (EAs) for approximating solutions of MOPs (MOPs) has been
a popular topic in the field of evolutionary computation, since EAs can o↵er simultaneously
a set of trade-o↵ solutions. To date, there have been a large set of MOEAs in the literature
addressing a widely range of problems with di↵erent properties. Di r ect i on s of improvement
have been discussed, con ce p tu a l i zed and used to guide MOEAs during the search process
10