Parallel and distributed
evolutionary algorithms
Prof. El-Ghazali TALBI
University Lille 1
El-ghazali.talbi@univ-lille1.fr
www.lifl.fr/~talbi

Motivations
 High-dimensional and complex optimization
problems in science and industry
o networks, genomics, transportation, engineering
design, power systems, …

 Metaheuristics (ex. EAs) reduce thecomputational complexity of search BUT Parallel
issue remains important: More and more complex metaheuristics
 Huge search space CPU or memory intensive of the objective function

Motivations
 Rapid development oftechnology
 Processors: Multi-coreprocessors, GPU, …
 Networks (LAN & WAN):
Myrinet, Infiniband, Optical
networks, …
 Data storage

 Increasing ratio
performance / cost

Goals Speedup the search Æ real-time and interactive
optimization methods, dynamic optimisation, …
 Improve quality of solutions Æ cooperation, better evenon a single processor

 Improve robustness (different instances, design space) Solving large problems Æ instances, accuracy ofmathematics models

Taxonomy of metaheuristics
Metaheuristics

Singlesolution
Hill
Climbing

SimulatedannealingTabu
searchPopulation

Evol.
algorithms

Swarm
optimisation

 Solution-based metaheuristics: HillClimbing,
Simulated Annealing, Tabu Search, VNS, …

 Population-based metaheuristics: Evolutionary
Algorithms, Scatter Search, Swarm optimization, …

Outline Parallel Metaheuristics: Design issues
 Parallel Metaheuristics: Implementation
issues Hardware platforms, Programming models
 Performance evaluation

 Adaptation to Multi-objective Optimization
 Software frameworks
 IIlustration : Network design problem

Parallel Models for Metaheuristics
 A unified view for single-based metaheuristics andpopulation based metaheuristics
 Three major hierarchical models: Algorithm-Level: Independent/Cooperative self-contained
metaheuristics
 Iteration-Level: parallelization of a single step of the metaheuristic(based on distribution of the handled solutions) Solution-Level: parallelization of the processing of a single solution

Parallel Models for Metaheuristics
Solution-level:
Processing of a single solution(Objective / Data partitioning)
Algorithm-level:
Independent walks,Multi-start model,
Hybridization/Cooperationof metaheuristics
Iteration-level:
Parallel evaluation of
the neighborhood/population

Scalability
Search algorithms

H u PuS
Population / Neighborhood

sub-solutions

Algorithm-level Parallel Model
Meta.

 Problem Independent Alter the behavior of themetaheuristic
 Design questions:

Meta
Cooperation

 When ? Migration decision:
 Blind: Periodic or Probabilistic
 Adaptive: state dependent Where ? Exchange topology:
complete graph, ring, torus, random,…
 Which ? Information : elite solutions,search memory, …
 How ? Integration

Meta.

Meta

Simulated Annealing
Genetic Programming
Evolution Strategy
Tabu search
Ant Colonies
Scatter search, …

Ex : Evolutionary Algorithms (Island
Model Distribution of the population in a setof islands in which semi-isolated EAs
are executed
GA

GA
GA

GA

GA
GA

GA
GA

 Sparse individual exchanges are
performed among these islands withthe goal of introducing morediversity into the target populations

 Improvement of robustness
and quality

Ex : The multi-start model in Local Search Independent set of Local
Searches Improve robustness andquality of solutions
 May start from the same ordifferent initial solution,
population
 Different parameters
 encoding, operators,
memory sizes (tabu list, …),etc.

Flat classification
Algorithm-Level Parallel Model

Homogeneous Heterogenenous

PartialGlobalSpecialist GeneralHomogeneous / Heterogeneous Homogeneous hybrids = Same Metaheuristic
 Heterogeneous = Different Metaheuristics
 Example
Evolutionary
Algorithm
Communication
mediumSimulated
Annealing

Tabu Search
Several different metaheuristics cooperate andco-evolve some solutions

Global / Partial Partial : Problem is decomposed in sub-problems.
Each algorithm is dedicated to solve one subproblem
 Combinatorial / Continuous : Decomposition of
the problem, decision space, …
 Problem dependant: Vehicle routing, Scheduling, …
Problem

Sub-problem

Sub-problem

Sub-problem

Meta

Meta

Meta

EAs, Tabu search
Simulated annealing

Synchronization : Build a global viable solution

Specialist / General Specialist: Algorithms solve different problems(ex: Co-evolutionary)
Intensifying Agent

Solutionsfrom
unexplored regions

Promisingsolutions

Refers toRefers toDiversifying Agent

Adaptative Memory
Promising regions
Explored regions
explored
space

Initialsolutions

Local Search AgentGood
solutionsIteration-level Parallel Model Problem independent Complex objective functions (nonlinear, simulations, …)
 Do not alter the behavior of
the metaheuristic Æ Speedup
the search Design questions: Single-solution based algorithms:
decomposition of the neighborhood
 Population based algorithms:
decomposition of the population

Meta

Solution(s)FullfitnessEx : Single-Solution Based Metaheuristic
LS
Solution
Partitionof theneighborhood

 Evaluation of theneighborhood: computationallyintensive step
 Decomposition of theneighborhood : Asynchronous for Simulated
Annealing (# behavior) Synchronous for deterministic
algorithms (e.g. Tabu Search)Ex : Population Based Metaheuristic
Selection
Replacement

E.A.

Couple ofindividuals
Evaluated
offsprings

Crossover,
Mutation,
evaluation

 Decomposition of the
population:
 Individuals (EAs), Ants (AS),Particles (PSO), etc.
 Sharing Information:
Pheromone matrix, etc.
 Asynchronous for steady stateGAs (# behavior) Synchronous forgenerational GAs

Solution-level Parallel Model Problem dependent Do alter the behavior of themetaheuristic Æ Speedup thesearch (CPU or I/O intensive) Synchronous Design questions: Data / Task Decomposition
 Data : database, geographical area,
structure, …
 Task : sub-functions, solvers, …

Aggregation ofpartial fitnesses
Solution
Partialfitness

Outline Parallel Metaheuristics: Design issues
 Parallel Metaheuristics: Implementation
issues Hardware platforms, Programming models
 Performance evaluation

 Adaptation to Multi-objective Optimization
 Software frameworks
 IIlustration : Network design problem

Parallel Metaheuristics: Implementation issues
Design of
Parallel
Metaheuristics
Programming Paradigms
Parallel Programming
Environments

Execution Support

Parallel Architecture
P

P

P

P

P



HardwareP

Main criteria : Memory sharing, Homogeneity,
Dedicated, Scalability, Volatility
P Processor

ThreadProcess

Shared Memory Machine (SMP)
Memory Easy to program: conventional OS
and programming paradigms

network
CPU

CPU

CPU

interconnection network:bus, crossbar, multistage
crossbar Poor Scalability: Increase inprocessors leads memory
contention
 Ex. : Multi-core (Intel, AMD), Origin(Silicon Graphics), ....

Distributed Memory Architectures
CPU Memory Good Scalability : Several hundred
nodes with a high speed
interconnection network/switch

network
Memory CPU

Memory CPU

 Harder to programInterconnection schema :hypercube, (2D or 3D) torus,
fat-tree, multistage crossbars

Communication cost Ex. : Clusters

Clusters & NOWs (DSM) Clusters: A

collections of PCsinterconnected throughhigh speed network, Low cost
 Standard components

 NOWs: Network Of
Workstations
 take advantage ofunused computing
power

ccNUMA architectures Mixing SMP and DSM
 Small number of processors (up to 16)
clustered in SMP nodes (fast connectio n,crossbar for instance)
 SMPs are connected through a lesscostly network with poorer
performance
Memory CPU
network

Memory CPU
network

Memory CPU
network

CPUCPUCPU

CPUCPUCPU

CPUCPUCPUInterconnection network

Periph.

Grid Computing“Coordinated resource sharing and problem solving in
dynamic, multi-institutional virtual organizations”
High-Performance
Computing GRID

High-Throughput
Computing GRID

• Offer a virtual supercomputer Billions of idle PCs …
 Stealing unused CPU
cycles of processors (amean of 47%)

 Inexpensive, potentially very powerful but more difficult
to program than traditional parallel computers

GRID Platforms

Lille

Rennes

Orsay

Nancy

Lyon
Bordeaux
Toulouse

Grenoble
SophiaHPC Grid: GRID’5000: 9 sites
distributed in France andinter-connected by Renater
7800 proc: between 500 and
1500 CPUs on each site

HTC Grid: PlanetLab: 711
nodes on 338 sites over 25
countries

Main criteria for an efficient implementation
Criteria

SharedMemory /Distributed

Homogenous Dedicated//Heterogenous Non Dedi.

Local
network /Large
network

Volatility& Fault
Tolerance

SMP

SM

Hom

Dedi

Local

No

COW

DM

Hom

Dedi

Local

No

NOW

DM

Het

Non

Local

Yes

HP Grid DM

Het

Dedi

Large

No

HT Grid DM

Het

Non

Large

Yes

ArchitectureParallel Programming Environments
 Shared-memory:
SystemCategory

Language binding

PThreads

Operating system

C

Java threads

Programming language

Java

OpenMP

Compiler directives

Fortran, C, C++ Distributed-memory: Hybrid model

Messagepassing

RPC or Objectbased systems

Gridcomputing

Sockets

Java RMI

GlobusMPI

CondorAlgorithm-Level Parallel Model Granularity = Ratio Execution cost between
communication / Size Information exchanged
 Large Granularity Æ Well suited to large scalearchitectures
 Frequency of migration, Size of informationexchanged Asynchronous exchange more efficient than
Synchronous exchange for Heterogeneous or
Non-dedicated Architectures
 Fault tolerance for Volatile architectures Æ
Checkpointing (reduced cost) Scale : Number of optimization algorithms

Iteration-Level Parallel Model Granularity = Evaluation of a partition / Partition
communication cost Æ Adapt granularity to target architecture (size ofpartitions) Asynchronous evaluation is more efficient: Heterogeneous or Non Dedicated or Volatile
platforms
 Heterogeneous computation of the objective function(#solutions #costs)

 Scale: Limited by Size of population
 Size of Neighborhood.

Solution-Level Parallel Model Granularity = Evaluation of sub-function /Cost of solution communication Æ Not
well suited to Large scale and distributed
memory architectures

 Limited scalability (number of subfunctions or data partitions) SynchronousFault-tolerance issues
 Important in volatile, non-dedicated, large-scale
platforms
 Checkpointing – Recovery mechanism Application-oriented and NOT System-oriented(reduced complexity in time and space) Algorithmic-level: Current solution or population,
iteration number, …
 Iteration-level: Which partition of population orneighborhood + fitnesses Solution-level: Solution + partial fitnesses

Load Balancing, Security, …
 Static load balancing important forheterogeneous architectures
 Dynamic load balancing important for non
dedicated, volatile architectures.
 Security issues important for large-scalearchitectures (multi-domain administration,
firewalls, …) and some applications(medical and bio research, industrial, …)

Performance evaluation
 Speedup ?
SN = T1 / TN
Ti : Execution time using i processors (wall clock time)
N : number of used processors
 If S < N Î Sublinear speedup If S = N Î Linear speedup If S > N Î Superlinear speedup

 Absolute speedup
 Strong: T1 = Best known sequential algorithm ??
 Weak :
Population of N individuals compared to K
islands of N/K individualsSingle-solution metaheuristic with N iterations
with K S-Meta with N/K iterations

Performance evaluation
 Relative speedup Fixed number of iterations
 Interesting for evaluating the efficiency of the implementation
 Superlinear speedup is possible: architecture source (memory,cache, …)

 Convergence to a solution with a given quality
 Interesting for evaluation the efficiency of the parallel design(Algorithm-level parallel model)
 Superlinear speedup possible: search source (such as in branch andbound)

 Heterogenous or Non Dedicated architectures: Efficiency: EN = SN * 100% / N (fraction of time processors are
conducting work) 100% efficiency means linear speedupt ( j)¦jJ t(j): time for task i, U(i): availability of worker iE Stochastic : Mean, …

¦ U (i)i I

Outline Parallel Metaheuristics: Design issues
 Parallel Metaheuristics: Implementation
issues Hardware platforms, Programming models

 Adaptation to Multi-objective
Optimization
 Software frameworks
 IIlustration : Network design problem

Multi-Objective Optimization(MOP)

min f (x)(f (x), f (x),..., f (x)) n t2
12

ns.c. x  S Dominance y dominates z if and only if
i[1, …, n], yi d zi
and i[1, …, n], yi < zi

 Pareto solutionf2

Feasible solutions

 A solution x is Pareto if a solution
which dominates x does not exist

Î Goal: Find a good quality and welldiversified set of Pareto solutions

Pareto front
Solution foundf1

Algorithm-Level Parallel Model General and Global Cooperative Models: Which Information to exchange ?
 Pareto archive or current populations (random, elite, uniform,…), …

 Any replacement strategy for the current population
 Based on: Dominance, Indicator, Scalarization, …

 Partial:
 Decompose the Pareto front (objective space) # dominance criteria

 Specialist : Solve # problems (# objectives subsets)

Iteration-Level Parallel Model Many MOP applications with complex
objectives (CFD – computational fluid dynamics,

CEM – computational electromagnetics, FEM - finite
element method, …)

 Fitness assignment
 Dominance, performance indicator, … :complex procedures to parallelize Elitism Pareto archiving : complex procedure toparallelize

Solution-Level Parallel Model Decomposition of the n objectives
 Multi-disciplinary Design Optimization
 Many engineering domains with different
models (# disciplines, #solvers)
 Ex: Car design
 Optimize the air flow around a car Æ
computational fluid dynamics (CFD) solver Optimize the toughness of materials Æ finite
element method (FEM) solverOutline Parallel Metaheuristics: Design issues
 Parallel Metaheuristics: Implementation• issues Hardware platforms, Programming models

 Adaptation to Multi-objective Optimization
 Software Frameworks for Parallel
Metaheuristics
 IIlustration : Network design problem

Why ?
 From scratch: high development cost, error prone,difficult to maintain, …
 Code reuse: difficult to reuse, adaptation cost, …
 Design and code reuse – software components:
Hollywood principle « Don’t call us, we call you»

Combinatorial Optimization Problems (COPs) in practice: Diversity
 Continual evolution of the modeling (regards
needs, objectives, constraints, …)
 Need to experiment many solving methods, techniquesof parallelization, hybridization, parameters, …

Design Objectives
 Maximal Reuse of code and design
 Separation between resolution methods and target problems
 Invariant part given
 Problem specific part specified but to implement

 Flexibility et Adaptability
 Adding and updating other optimization methods, search mechanisms,
operators, encoding, ...
 … to solve new problems

 Utility
 Large panel of methods, hybrids, parallel strategies, …

 Portability Deployment on different platforms (Standard library) Transparent access to performance and robustness
 Parallel implementation is tranparent to the target hardware platform Open source, Efficiency, Easy to use, …

Examples
Metaheuristics

Parallelism
support at design

Parall. and dist.
atimplementation

ECJ

E.A.

Island cooperation

Threads / Sockets

D. BEAGLE

E.A.

Centralized model /Island cooperation.

Sockets

J-DEAL

E.A.

Centralized model

Sockets

DREAM

E.A.

Island cooperation

Sockets / P2P

MALLBA

L.S. / E.A.

All

MPI, Netstream

PARADISEO

S-Meta / P-Meta

All

MPI, Condor,
PThreads,
Globus,CUDA

PARADISEO (PARAllel and
DIStributed Evolving Objects)
 PARADISEO in some words …
http://paradiseo.gforge.inria.fr

 An Open Source C++ framework (STL-Template) Paradigm-free, unifying metaheuristics
 Flexible regards the tackled problem
 Generic and reusable components (operators ofvariation, selection, replacement, criterion oftermination, …)
 Many services (visualization, management of commandline parameters, check-pointing, …)

PARADISEO : http://paradiseo.gforge.inria.fr
PEO
MO

MOEO

EO
 Evolving Objects (EO) for the design of population-based
metaheuristics: GA, GP, ES, EDA, PSO, …
 Moving Objects (MO) for the design of solution-based
metaheuristics: LS, TS, SA, VNS, ILS
 Multi-Objective EO (MOEO) embedding features and techniques
related to multi-objective optimization,
 PEO for the parallelization and hybridization of metaheuristics

Architecture (level of execution)
Parallel and distributed platforms
PEO
MO

MOEO

LAM-MPI

PThreads

CUDA

EO

 Parallelism and distribution
 Communication libraries (MPI LAM)o Deployment on networks/clusters of stations (COWs, NOWs)
 Multi-threading layer (Posix threads)o multi-core, multi-processors with shared memory (SMPs)
 CUDA environmentso GPUs Transparent to the user

Architecture (level of execution)
Grid computing
PEO
MO
EO

MOEO

Master/Worker
Condor (HTC)

Globus (HPC) Gridification
 Re-visit parallel models taken into account the characterisitics of Grids Coupling of ParadisEO with a Grid middleware (Condor-MW and Globus)

 Transparent volatility & checkpointing
 Ex : Definition in ParadisEO-CMW of the memory of each metaheuristic andthe associated parallel models

Illustration: Core classes of the Local
Search
UML notation(Unified Modeling Language)Illustration: Core classes of the
Evolutionary AlgorithmIllustration: The cooperative island model of
E.A.s/* To enable migrations (i.e. exchanges
of individuals) */eoPopChan <Route> pop_chan ;/* Migrations will occur periodically */eoFreqContinue <Route> mig_cont (FREQ_MIG) ;/* Migrations are composed of random individuals*/
eoRandomSelect <Route> mig_select_one ;/* Selector of NUM_EMIG emigrants*/
eoSelectNumber <Route> mig_select(mig_select_one,
NUM_EMIG) ;/* Emigrants replace the worst individuals*/eoPlusReplacement <Route> mig_replace ;/* The ring topology */eoRingTopology topo (naming_chan) ;/* Building a manager of migrations */eoDistAsyncIslandMig <Route> island_mig(naming_chan, pop_chan,
mig_cont,
mig_select,
mig_replace,
pop,
pop,
topo)
;

E.A.

E.A.
Migration

Illustration: The parallelization of
the evaluation step
E.A.
SolutionFullfitness

Illustration: The parallelization of theobjective function
Aggregation ofpartial fitnesses
Solution
Partialfitness

Outline Parallel Metaheuristics: Design issues
 Parallel Metaheuristics: Implementation issues
 Hardware platforms, Programming models

 Adaptation to Multi-objective Optimization
 Software frameworks

 IIlustration : Network design problem
 Combined use of the 3 parallel models
 Multi-objective problem
 Implemented on COWs, NOWs, HPC Grids and
HTC Grids
 Using of PARADISEO – EO & MO & MOEO & PEO

Design of radio networks inmobile telecommunication


Network design
Positioning sites
 Fixing a set of parameters for eachantennaMulti-objective problem
Cost of the network: Number of sites
 Quality of ServiceNP-hard problem with:

Huge search space
High cost (CPU and memory )objective functions, constraints.

A brief description
Working area

A set of base stations that satisfy
the following constraints …





Cover
Handover… and optimizes the following
criterion

Min. the number of sites
Min. interferences
Max. yield traffic

Propagation model(Free spaceOkumura-Hata)

Parameters ofantennas
DonnéesbornesPs[26, 55] dBm
Diagram3 types
Hauteur[30, 50] m
Azimut[0, 359] °Inclinaison[-15, 0] °TRX
[1, 7]

Used sites
Useless sites
Handover area
Cover area

A multi-layer hierarchical parallel/hybrid
metaheuristic
1. Cooperativeisland EAs

2. Distributionof networks

3. Parallel evaluation(data partitioning)

1. Deployment of
incremental
Local Searches

Iteration-level Parallel Model (Homogeneousand Dedicated Cluster) Synchronous/AsynchronousDeploying irregular taskso The computation time isdependent of the number ofactivated sites of the network
Limited scalability of thesynchronous model (size of thepop., e.g. 100)
A.E.
Network
Full
fitness

Solution-level Parallel Model
Agregation

 Synchronous, fine-grained !
 Larger instances Poor scalability

Solution
Partialfitness

Partitioned
data

Partitioningof the geographicaldata(f1.3,f2.3, f3.3)(f1.1,f2.1, f3.1)(f1.2,f2.2, f3.2)

Experimentation under PARADISEO(non-dedicated cluster of PCs)

Superlinear speedup

models 2&3

model 2 alone

Parallel evaluation of the
population (model 2)

Parallel Evaluation of a solution(model 3)

Synchronous vs. Asynchronous

Influence of the granularity on theefficiency (synchronous)

High-Throughput Computing Grid:
Campus of Lille (3 # administrative domains)Platform

HTC Grid (Polytech, IUT, LIFL)

Prog. Environment

CondorNumber of proc.

100 (heterog. and non dedicated)

Cumulative wall clock time

30681 h.

Wall clock time

Almost 15 days

Parallel efficiency

0.98

Highway

Urban

High-Performance Computing
Grid: GRID’5000 under
Globus400 CPUs on 6 sites: Lille,
Nice-Sophia Antipolis, Lyon,
Nancy, Rennes
Parallel efficiency = 0.92
 Best results obtainedMore than 22 years of
cumulative wall clock time(other benchmark on 2465
processors)

GRID’5000: A fully reconfigurable grid! :Linux « images » having Globus and MPICH-G2
already installed.

Conclusions
 Unifying Parallel Models
for Metaheuristics[Parallel] Metaheuristics

 Clear separation between
parallel design andparallel implementation

Software framework for[Parallel] metaheuristics

 Encourage the use ofsoftware framework for[parallel] metaheuristics

Different Architectures:Sequential, Cluster, NOW,
Grid, SMP, …

Perspectives
 Parallel models combining Metaheuristics &Exact methods (Algorithms, Coupling ofSoftware, …)
 Parallel models for dynamic and robust
optimization problems
 Parallel models for optimization problems withuncertainty
 Need a multiple evaluation of a solution

 Solving challenging problems on Grids (Ex:
Molecular biology, Engineering design, …)
 Metaheuristics on heterogeneousarchitectures (GPU+multi-cores)