Tutorial on Modern Linkage Learning Techniques in Combinatorial Optimization

 

 

 

 

 

 

 

 

Back to tutorial overview

 

 

 

 

 

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 permutation-based 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 Gray-box optimization)

-          The aims of the tutorial

-          Explain why do we concentrate on discrete and permutation-based search spaces

 

 

 

2. Linkage example in practical problem

 

 

 

 

As a starter, we will show the simple test case of a non-binary 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 DSM-based 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 non-binary, permutation-based, continuous [just to signal it is possible!])

-          Linkage tree construction with examples

 

 

 

4. DSM-based modern evolutionary methods

 

 

 

 

The fourth part of the tutorial will present the main state-of-the-art methods that employ DSM-based 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)

-          Parameter-less Population Pyramid (P3)

-          DSM Genetic Algorithm (DSMGA-II) and Incremental Linkage Set utilization.

-          Typical extensions (eg. population-sizing, to produce parameter-less 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 multi-objective optimization

 

 

 

 

In part eight, we will show the main state-of-the-art evolutionary methods that decompose the underlying problem structure in solving multi-objective optimization. We will present the core idea behind decomposing multi-objective problems that is an extension of single-objective problems decomposition. We will present the details of state-of-the-art evolutionary methods that use linkage learning and are dedicated to solving multi-objective problems. To show such methods' potential, we will present the recent results obtained for theoretical and practical problems. As a baseline, we will use NSGA-II and MOEA/D. The main issues that will be presented are as follows:

-          Multi-objective problem decomposition into a set of single-objective problems

-          Population clusterization

-          State-of-the-art evolutionary methods that employ linkage learning and are dedicated to solving multi-objective 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 best-paper award on the leading conferences in the field of evolutionary computation.

-          Linkage diversity & conditional linkage

-          Linkage quality measurement in overlapping problems

-          Linkage hybridization

-          Hyper-Linkage Learning techniques

-          Linkage approximation in multi-objective optimization