Previous Optimization meetings

2005

Friday 28th October - Prasanna BALAPRAKASH

Agenda

1. Short Introduction to the optimization group weekly meeting
2. Presentation / Discussion
   • Local Search under Uncertainty
   • Probabilistic Traveling Salesman Problem as a case study
   • Overview of the state-of-the-art local search techniques to tackle uncertainty
   • Empirical estimation based local search to tackle uncertainty
3. Optimization Group Admin
   • Structure for the weekly meeting
   • Time schedule for the Optimization weekly meeting
   • Wiki page administration
   • Next week...

People who will be absent
-NA-

Results

• Sharing Code: Writing code in a way such that others can understand (with comments where ever possible). This helps to share the code with others.
• For the moment, the weekly meeting is scheduled on Thursdays at 11.00 AM.
• The person, who is giving the talk, should present the field/area in which he/she considers himself/herself as an expert for about 5 mins.
• We should agree on the coding language and compilers(if possible). At the moment we are using Mauro's R "code" for statistical analysis and parameter tuning. This code will be made available in this wiki.
• Skripts for doing useful things will be collected and also be made available in this wiki.

Download Presentation(PDF)

Thursday 3nd November - Max MANFRIN

Agenda

1. Introduction / General interest discussion
   • Brief introduction on Max background
   • IRIDIA Cluster
     • The architecture of the IRIDIA cluster
     • The Sun Grid Engine queueing system
     • Policies for submission and execution of the jobs
2. Presentation / Discussion
   • Survey on Parallelization of Ant Colony Optimization
   • Proposal of a parallel design for ACO algorithm to solve Rich Vehicle Routing Problems

Linked Presentations

• An overview on Parallel Computing and Message Passing Seminar at IRDIA - ULB, Brussels, Belgium, January 26, 2005

Reading Material

• There is no reading material for this weeks presentation

People who will be absent

Christophe Philemotte

Wednesday 9th November - Jodelson A. SABINO

This talk is going to be given as a IRIDIA seminar. Therefore it will not take place on Thursday but on Wednesday. After the talk, there will be a MEETOPT discussion about the organizational matters.

Agenda

1. Introduction
   • Field of expertise etc.
2. Presentation / Discussion
   • The Problem of Railroad Yards Operational Planning
3. MEETOPT Admin (10-15 mins)

Linked Presentations

Abstract and Reading Material

• The Problem of Railroad Yards Operational Planning

People who will be absent
Christophe Philemotte

Thursday 17th November - Jodelson A. SABINO

Agenda

1. Introduction
2. Presentation / Discussion
   • A certain solution for the Switch Engine Assignment Problem
3. MEETOPT Admin (10-15 mins)

Linked Presentations

Abstract and Reading Material

This seminar gives an overview of the algorithm presented in Jodelson's Master Degree dissertation to solve the Switch Engine Assignment Problem. This presentation start with a quick review of the problem statement (as it was presented in a previous IRIDIA seminar), definition of the concept of PDP path and the solution by the RR-COMPETants algorithm.

• The Problem of Railroad Yards Operational Planning

People who will be absent
N.A.

Thursday 24th November - Thomas STÜTZLE

Agenda

1. Introduction
2. Presentation / Discussion
   • Stochastic Local Search, introduction and engineering of algorithms
3. MEETOPT Admin (10-15 mins)

Linked Presentations

Abstract and Reading Material
This presentation explaines concisely what Stochastic Local Search is and gives some thoughts on further work in this area that should lead to what can be called "Stochastic Local Search algorithms Engineering" or, short, SLS Engineering.

Download Presentation(PDF)

People who will be absent
N.A.

Wednsday 30th November - Marco MONTES DE OCA

Agenda

1. Introduction
2. Presentation / Discussion
   • Particle Swarm Optimization
3. MEETOPT Admin (10-15 mins)

Linked Presentations

Download Presentation(PDF)

Abstract and Reading Material

Particle Swarm Optimization (PSO for short) was first inspired by the flocking behavior of birds, although it also has roots in some theories of social adaptation. PSO is a population-based optimization technique in which each individual or "particle" represents a solution to a continuous optimization problem. Associated with each particle, there is a velocity vector that changes according to its own best past performance and that of its neighbors. In this way, particles "fly" over the search space resembling the movement of insects in a swarm.

After its first publication, PSO has attracted the interest of a growing research community because it is conceptually simple, technically easy to implement, and has been successfully applied to many problems.

In this meeting, a brief overview of what has been done in PSO research and possible future work will be presented.

PSO introductory tutorial

People who will be absent
N.A.

Thursday 8th December - Andrea ROLI

Agenda

1. Introduction
2. Presentation / Discussion
   • An introduction to constraint programming (for metaheuristic-minded researchers) -- Part 1

Abstract and Reading Material
Click here for more details

Download Presentation(PDF)

People who will be absent
Marco DORIGO, Thomas STÜTZLE

Friday 9th December - Andrea ROLI

Agenda

1. Introduction
2. Presentation / Discussion
   • An introduction to constraint programming (for metaheuristic-minded researchers) -- Part 2

Abstract and Reading Material
Click here for more details

People who will be absent
Marco DORIGO, Thomas STÜTZLE

2006

Thursday 12th January - Tom LENAERTS

Agenda

1. Introduction
2. Presentation / Discussion
   • Evolutionary Transitions in Solution Complexity

Abstract
Recently, Evolutionary Biology has proposed a generalised theory for the origin of complexity in biological systems. This theory, referred to as Evolutionary Transition Theory, provides a description on how complexity could have arisen out of the interaction of simple components. A well-known example is the transition from single cell to multi-cellularity. As evolution itself, this theory provides a metaphor for optimisation and learning where complex solutions are constructed through the evolutionary combination of partial ones. This talk discusses a new evolutionary algorithm based on this metaphor. We show that, in the context of constraint satisfaction problems, this metaphor provides a very useful technique to find solutions. Moreover, the results of this basic, unoptimised algorithm are close to what is observed in other highly-adjusted evolutionary techniques. As a consequence, it provides an important foundation for the further investigation of compositional algorithms in the context of optimisation

People who will be absent

Thursday 19th January - General Discussion (Optimization Library)

Agenda

1. Outcome of the discussion
   • The C programming language will be selected for the implementation and development. We'll follow the C99 standard and use GCC compiler tools (Status of C99 features in GCC). The standard compiler is the one provided in the most recent stable version of Debian.
     • Are you Ready For C99?
     • Open source development using C99
   • We will have a look at GNU coding standards and if everyone feels it is good then they will be adopted.
     • Christophe suggests the formating tool GNU Indent to respect some GNU standards
   • Subversion will be adopted as the revision control system (Max will make a brief study)
   • The format of result files should be standardised (Mauro, Thomas and Prasanna will come up with a format which should be discussed later).
   • Common scripts have to be developed to extract required information from the results file should be developed. Mauro, Thomas, and Prasanna make an initial list of scripts to be developped.
   • Mauro will have a look at COMET software libraries book and Prasanna will check about software libraries, in general, and the features they provide.
     • Short term goal - sharing code to save the development time
     • Long term goal - IRIDIA Optimization Library
   • Christophe suggests Doxygen as documentation tools.

Thursday 26th January - Thomas STÜTZLE

Agenda

1. Introduction
2. Presentation / Discussion
   • Empirical analysis of stochastic algorithms by measuring run-time distributions
3. MEETOPT Admin (10-15 mins)
   • Follow-up of the meeting about optimization libraries, tools etc. of the previous week

Linked Presentations

Abstract and Reading Material
We start now the part of presentations / discussions on specific topics. The first topic to be discussed in a number of presentations / discussions is the Empirical Analysis of Algorithms, in particular SLS Algorithms. In this series we will discuss methods for their empirical analysis including run-time distributions, statistical analysis (hypothesis tests, ANOVA and alike methods), experimental design, tuning of algorithms, etc. We start this series by a presentation about the empirical analysis of algorithms through measuring run-time distributions. The presentation will be based on Chapter 4 of the book about Stochastic Local Search: Foundations and Applications by Holger Hoos and Thomas. The slides for the presentation are available via SLS:FA (check for the slides and figures section). The presentation will discuss only a small selection of the most important issues presented there.

People who will be absent
N.A.

Thursday 2nd February - Thomas STÜTZLE

Agenda

Below is a list of topics that we will cover on empirical analysis. Since these topics in part also have to be elaborated from scratch, we will switch to the envisaged bi-weekly meeting, that is have roughly every two weeks one meeting. The topics below will be elaborated by the people participating in the seminar. This Thursday, Feb 2, we willl have a short meeting where we distribute the responsabilites of the tasks.

On Thursday everybods needs to have a lists of his two main preferred tasks so that we make the decision on who takes over what part.

We will also shortly discuss the state for the more practical directions.

In any case, the meeting on Thursday should be finished after 10 - 15 minutes max.

Topics on Empirical Analysis:

- Statistical Analysis (hypothesis tests -- param, non-param, permutation; stability of estimates -- confidence intervals; various situations of things to test -- correlation, metric measures, binary tests etc.) Maybe follow some text-book (Sheshkin / Siegel Castellan)

- Experimental Design (ANOVA and non-parametric analysis; planning of experiments; methodologies -- factorial designs, response surface methodology; follow some book: Montgomery / Dean, Voos etc.)

- Exploratory data analysis (usage of plots to illustrate things ?); Take ideas here from published papers, maybe some book about exploratory data analysis..

- Automated tuning of metaheuristics (overview of methods, issues); Overview of published papers plus new directions of work ..

- Integration of experimental methodologies in the design of algorithms; still fuzzy, to be defined.

Results

We will read and discuss the book chapter by chapter. For each chapter, one person will be responsable to lead the discussion by a short presentation. However, it is expected that everybody present in the meeting has already read through the material; in fact, reading the material is important to make the meetings effective.

The current schedule for the meetings is as follows.

- Feb 16, Marco M.: Empirical Research + Exploratory Data Analysis

- March 23, Anders: Basic Issues in Experiment Design

- March 29, Max: Hypothesis Testing and Estimation

- April 20, Christophe: Computer-Intensive Statistical Methods

- May 4, Shervin: Performance Assessment

- May 18, Prasanna: Explaining Performance: Interactions and Dependencies

- June 1, Roderich: Modeling

- June 15, Alexandre: Tactics for Generalization

Thursday 16th Feb - Marco M

Agenda

1. Introduction
2. Presentation / Discussion
   • Empirical Research + Exploratory Data Analysis
3. MEETOPT Admin (10-15 mins)

Resources

• Should Computer Scientists Experiment More? by Walter F. Tichy
• R Graph Gallery A gallery of graphs that can be created using the R Graphic Engine.

Slides

• Empirical research & exploratory data analysis

People who will be absent
Rodi (I feel really very sorry for this, but its for my health)

Thursday 20th April - Anders

Agenda

1. Introduction
2. Presentation / Discussion
   • Basic Issues in Experiment Design
3. MEETOPT Admin (10-15 mins)

People who will be absent
N.A.

Slides

• Basic Issues in Experiment Design

Thursday 27th April - Max Manfrin

Agenda

1. Introduction
2. Presentation / Discussion
   • Hypothesis Testing and Estimation (1st part)
3. MEETOPT Admin (10-15 mins)

Resources

• Sampling distribution demo A java applet to test sampling distribution of the mean, standard deviation and variance.

Slides

• Hypothesis Testing and Estimation (1st part)

People who will be absent
N.A.

Thursday 4th May - Max Manfrin

Agenda

1. Introduction
2. Presentation / Discussion
   • Hypothesis Testing and Estimation (2nd part)
3. MEETOPT Admin (10-15 mins)

Resources

• Confidence Intervals for Means A java applet to demo the confidence intervals for means.
• Making the Concepts of Power and Sample Size Relevant and Accessible to Students in Introductory Statistics Courses using Applets Journal of Statistics Education

Slides

• Hypothesis Testing and Estimation (2nd part)

People who will be absent
Marco Montes de Oca

Thursday 11th May - Prasanna

Agenda

1. Introduction
2. Presentation / Discussion
   • Computer-Intensive Statistical Methods
3. MEETOPT Admin (10-15 mins)

Slides

• Computer-Intensive Statistical Methods

People who will be absent
N.A.

Wednesday 24th May - Shervin

Agenda

1. Introduction
2. Presentation / Discussion
   • Performance Assessment
3. MEETOPT Admin (10-15 mins)

People who will be absent
Prasanna

Thursday 15th June - Christophe

Agenda

1. Introduction
2. Presentation / Discussion
   • Explaining Performance: Interactions and Dependencies
3. MEETOPT Admin (10-15 mins)

Slides

File:Talk-150606.pdf

People who will be absent
Prasanna, Roderich

Thursday 22nd June - Christos

Agenda

1. Introduction
2. Presentation / Discussion
   • Modeling
3. MEETOPT Admin (10-15 mins)

People who will be absent
Prasanna

Thursday 29th June -Alexandre

Agenda

1. Introduction
2. Presentation / Discussion
   • Tactics for Generalization
3. MEETOPT Admin (10-15 mins)

People who will be absent
N.A.

2008

Thursday 12th June 2008 - Eliseo

Paper Info

• Title
  • Ant clustering with locally weighted ant perception and diversified memory

• Authors
  • Gilbert L. Peterson, Christopher B. Mayer, Thomas L. Kubler

• Summary
  • The paper introduces two improvements to existing state of the art clustering algorithm based on ants. The first is the use of kernel functions as a way to increase the local perception capabilities of ants, enabling them to better distinguish between similar and dissimilar objects in their neighborhood. The second is the introduction of similarity-based memory, i.e. a very simple memory that can be equipped into single ants or in the entire ant colony and enables a better exploitation of the past experience. Results show that these improvements yield to better clustering quality and performance.

Reading material

• The paper is not yet published so it cannot be distributed in pdf. Paper copies can be obtained passing by Eliseo's office.

People who will be absent