


















Tutorial
on Modern Linkage Learning Techniques in Combinatorial Optimization 
















Tutorial
length 
2 hours 






Tutorial
level 
introductory 






Tutorial
overview (agenda) 







1. Introduction 





The introductory part will clarify the aim
and construction of the tutorial. We will explain why do we
concentrate on discrete and permutationbased optimization problems. The main
issues that will be presented are as follows: 
The aims of problem decomposition techniques
(including linkage learning, estimation of distribution algorithms and
Graybox optimization) 
The aims of the tutorial 
Explain why do we concentrate on discrete and
permutationbased search spaces 




2. Linkage example in practical problem 





As a starter, we will show the simple test
case of a nonbinary practical problem concerning computer network
optimization (we will show the visualization of a problem solution). The main
issues that will be presented are as follows: 
We will show that in the analyzed case, the linkage
between various gene groups may exist or not 
We will show how the information about gene
dependencies may be utilized in solving the problem from the proposed example 




3. Linkage learning based on Dependency Structure
Matrix (DSM) 





In the third part, we will concentrate on
presenting the DSMbased linkage learning. We will use simple examples and
appropriate animations. We will show that the concept of DSM applies to
various optimization domains. The main issues that will be presented are as
follows: 
DSM definition 
DSM computation example on a simple test case 
DSM applicability to various search spaces (binary,
discrete nonbinary, permutationbased, continuous [just to signal it is
possible!]) 
Linkage tree construction with examples 




4. DSMbased modern evolutionary methods 





The fourth part of the tutorial will present
the main stateoftheart methods that employ DSMbased linkage learning.
Note that these evolutionary methods were shown
highly effective for a set of theoretical and practical problems. The main
issues that will be presented are as follows: 
Optimal mixing 
Linkage Tree Genetic Algorithm (LTGA) 
Parameterless Population Pyramid (P3) 
DSM Genetic Algorithm (DSMGAII) and Incremental
Linkage Set utilization. 
Typical extensions (eg.
populationsizing, to produce parameterless methods) 
Exemplary results and scalability on practical and theoretical
problems 




5. Linkage learning classifications and overview 





After presenting the main achievements of
linkage learning problem decomposition gained in the recent 10 years, we will
give the audience a breath and show the main linkage learning
classifications. The main issues that will be presented are as follows: 
The main classifications considering the way linkage
is discovered 
Predetermined and Learned Linkage Models –
classification and differences 




8. Linkage learning in multiobjective optimization 





In part eight, we will show the main
stateoftheart evolutionary methods that decompose the underlying problem
structure in solving multiobjective optimization. We will present the core
idea behind decomposing multiobjective problems that is an extension of
singleobjective problems decomposition. We will present the details of
stateoftheart evolutionary methods that use linkage learning and are
dedicated to solving multiobjective problems. To show such methods'
potential, we will present the recent results obtained for theoretical and
practical problems. As a baseline, we will use NSGAII and MOEA/D. The main
issues that will be presented are as follows: 
Multiobjective problem decomposition into a set of
singleobjective problems 
Population clusterization 
Stateoftheart evolutionary methods that employ
linkage learning and are dedicated to solving multiobjective problems 




9. Promising future work directions 





In the last part of the tutorial, we will
present the most promising directions for future research concerning linkage
learning. The proposed directions will consider the most recent achievements
and results (not older than
two years). Some of the propositions will refer to results published in the
leading journals, awarded or nominated to the bestpaper award on the leading
conferences in the field of evolutionary computation. 
Linkage diversity & conditional linkage 
Linkage quality measurement in overlapping problems 
Linkage hybridization 
HyperLinkage Learning techniques 
Linkage approximation in multiobjective
optimization 









