


















Tutorial
on Modern Linkage Learning Techniques in Combinatorial Optimization 
















Tutorial
length 
2 hours 






Tutorial
level 
introductory 






The 2022 year updates in this tutorial are
marked in red. 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)

Typical extensions (eg.
populationsizing, to produce parameterless methods) 
Exemplary results and scalability on practical and
theoretical problems 




5. Linkage quality 





Linkage learning is an important part of many stateoftheart
methods. In this part, we will show the influence of linkage of the
stateoftheart optimizers 




6. New ideas – Empirical Linkage Learning 





DSMbased LL triggered a significant breakthrough,
but it also have some limitations. Therefore, in this part, we will show the
recent ideas concerning the linkage learning. This will include the closer
look on the Empirical Linkage Learning technique that can: 
Break the curse of false linkage 
Detect the direct linkage between genes 




7. Linkage learning in multiobjective optimization 





In this part, 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 




8. 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 




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 









