Date: 27 and 28 February 2017

Venue: William Penn Suite, Friends House, 173-177 Euston Road, London NW1 2BJ

 

Overview: 

Understanding the nature of the underlying structure of the search landscape is important for Search Based Software Engineering (SBSE). The purpose of this pair of distinguished tutorials is to help the Software Engineering community to raise its appreciation and potential application of landscape analysis to problems in SBSE.  We are delighted to have two absolutely outstanding speakers, of high international renown, who have graciously agreed to each give a full day tutorial on the subject.

 

This workshop will run from approximately 10- 5pm

 

Speakers: 

Monday 27th - Sebastien Verel, Université du Littoral Côte d'Opale, France 

Tuesday 28th - Darrell Whitley, Colorado State University, USA

 

Schedule:

10:00 – 10:30 – Pastries 

12:30 – 13:30  – Lunch 

15:00 – 15:30 – Refreshments 

17:00 - Finish

Day 1: Sébastien Verel - Fitness landscape analysis for understanding and designing local search heuristics (Slides: 1, 2, 3, 4, 5, 6, 7; Videos: 480p, 720p)

Local search heuristics (metaheuristics, evolutionary algorithms, etc.) are stochastic optimization methods which split a global optimization problem into a succession of local optimization problems. Although it can not be guaranteed to find global optimum by local search, they have been applied to number of real-world problems due to their efficiency and robustness. Such methods like many evolutionary processes in others research fields can be analyzed using Markov chains and related methods. However, when there is no explicit definition of the problem, only poor results can be obtained in that way.
 
Fitness landscape is one of the powerful metaphors which depicts the local search dynamics on a landscape based on peaks, valleys, plateaus, etc. Beside the picture which helps to understand the problem structure and to intuitively design better algorithms, fitness landscapes analysis is a way to characterize problem structure, and to be able to  predict algorithm performance, or to select a relevant local search heuristic.
 
The main geometries of the fitness landscapes will be presented by showing the multimodality features with local optima networks, or neutrality features with plateau shape. We will show how fitness landscapes can help to explain problem difficulty, and the performance of local search heuristics. Then, after a brief introduction of multi-objective optimization methods, we will introduce the fitness landscape of problems where several criteria should be fulfilled. All along, the tutorial will be illustrated by examples, in particular related to computer program design.
 
Outline:
 
- Basis of fitness landscape:
        - introductory example
        - brief history and background of fitness landscape
        - fundamental definitions
        
- Geometries of fitness landscapes:
        - neutral networks
        - local optima networks
        - landscape-aware design 
 
- Fitness landscape for multi-objective optimization problems:
        - brief overview of multi-objective optimization
        - features of multi-objective optimization problems
        - landscape aware design 
 
- Examples and practical exercises:
        - an engineering design problem 
        - cellular automata problems
        - a basic example of computer program design

 

Day 2: Darrell Whitley - Search Landscapes and Gray Box Optimization: A Tutorial (Slides: 1, 2, 3, 4, 5, 6; Videos: 480p, 720p). Gabriela Ochoa - The Cartography of Computational Search Spaces (Slides, Videos: 480p, 720p)

"Landscape Theory for search and optimization has intuitive appeal. It seem obvious that search methods must be sensitive to the structure of the "landscapes" that are being search and navigated. But "Landscape Theory also suffers from the same problems that plague all heuristics: to what degree are landscapes just metaphors, and to what degree are landscapes mathematically rigorous and useful constructs? We will look at the mathematics of landscapes as well as how the mathematics can be translated into useful search techniques. This also naturally leads to "Gray Box Optimization" methods that are inherently more powerful than Black Box Optimization methods. Applications will include: MAX-kSAT, the TSP, Graph Coloring, and Higher Order Mutation Testing.

The following is an approximate breakdown of topics to be covered.

INTRODUCTION:

1) No Free Lunch
2) Gray Box Optimization.
3) Multi-Funnel Search Spaces and Related Metrics
4) Visualization of Landscapes

TOPICS:

1) Elementary Landscapes: MAX-kSAT, TSP, Graph Coloring, Min-Cut, …
2) k-bounded pseudo-Boolean optimization, Walsh Decomposition, and Efficient O(1) Moves for Local Search (including Graph Coloring and Time Tabling).
3) Tunneling Between Local Optima in O(n) time Using Partition Crossover: Theory and Practice for the TSP and pseudo-Boolean optimization. (Solving 1 million variable NK Landscapes to optimality; improving on state of the art TSP heuristics.)
4) High Order Mutation Testing: Constructing a Better Landscape.

  

Photos:

 

 

 

This workshop is supported by the following sponsors:

 

 

Registered attendees:

1. Darrell Whitley, Colorado State University, USA

2. Sebastien Verel, Université du Littoral Côte d'Opale, France 

3. Matheus Paixao, CREST Centre, SSE Group, Department of Computer Science, UCL, UK

4. Gabriela Ochoa, Computing Science and Mathematics, University of Stirling, UK

5. John R. Woodward, Computing Science and Mathematics, University of Stirling, UK

6. Nada Veerapen, Computing Science and Mathematics, CHORDS, University of Stirling, UK

7. Fabio Daolio, Computing Science and Mathematics, University of Sterling, UK

8. Sarah Thomson, Computing Science and Mathematics, University of Sterling, UK

9. Earl Barr, CREST Centre, SSE Group, Department of Computer Science, UCL, UK 

10. Justyna Petke, CREST Centre, SSE Group, Department of Computer Science, UCL, UK

11. David White, CREST Centre, SSE Group, Department of Computer Science, UCL, UK

12. Mosab Bazargani, Computer Science, Queen Mary University London, UK

13. Mohd Zairul Jilani, Department of Computer Science, Brunel University, UK 

14. Bill Langdon, CREST Centre, SSE Group, Department of Computer Science, UCL, UK

15. Carlos Gavidia, CREST Centre, SSE Group, Department of Computer Science, UCL, UK

16. Federica Sarro, CREST Centre, SSE Group, Department of Computer Science, UCL, UK

17. Ken Reid, Computing Science and Mathematics, University of Stirling, UK

18. John Drake, Computer Science, Queen Mary University London, UK

19. Lee A. Christie, Computing Science and Mathematics, University of Stirling, UK

20. Irfan Muhammad, University of Birmingham, UK

21. Hector D Menendez, CREST Centre, SSE Group, Department of Computer Science, UCL, UK

22. Bobby Bruce, CREST Centre, SSE Group, Department of Computer Science, UCL, UK

23. Khulood Alyahya, Computer Science, University of Exeter, UK

24. Santanu Dash, CREST Centre, SSE Group, Department of Computer Science, UCL, UK

25. Ozgur Akman, Mathematics, University of Exeter, UK

26. Kevin Doherty,  Computer Science, University of Exeter, UK

27. Abdessalam Elhabbash, School of Computer Science, University of Birmingham, UK

28. Momodou Lamin Sanyang, School of Computer Science, University of Birmingham, UK

29. Pietro Consoli, School of Computer Science, University of Birmingham, UK

30. Junfeng Chen, College of IOT Engineering, Hohai University, China

31. Annan Yearian, Computing Science and Mathematics, University of Stirling, UK

32. Liangli Zhen, College of Computer Science, Sichuan University, China