Table of Contents

MFE 2009-2010 : Intelligence Artificielle

Introduction

Le laboratoire IRIDIA aborde des problèmes dans le domaine de l'Intelligence Artificielle. Si l'on reprend les dires d'un de ses pioniers Marvin Lee Minsky, l'Intelligence Artificielle est définit comme “la construction de programmes informatiques qui s'adonnent à des tâches qui sont, pour l'instant, accomplies de façon plus satisfaisante par des êtres humains car elles demandent des processus mentaux de haut niveau tels que : l'apprentissage perceptuel, l'organisation de la mémoire et le raisonnement critique”. L'IA a beaucoup évolué depuis et s'inspire largement de phénomènes biologiques, physiques, cognitifs ou encore écologiques. C'est donc définitivement une approche transdisciplinaire qui s'accorde principalement à traîtrer des problèmes très complexes. Les domaines principaux de compétence d'IRIDIA sont : l'intelligence en essaim, les métaheuristiques, l'étude des réseaux biologiques et l'application de Business Intelligence. C'est dans cette perspective que les sujets de MFE présentés ci-après s'inscrivent.

Ces sujets sont prêt à être encadrer, mais il va s'en dire qu'ils ne sont pas uniques. Les étudiants sont vivement encouragés à prendre contact avec Hugues Bersini (bersini AT ulb.ac.be) ou Marco Dorigo (mdorigo AT ulb.ac.be) afin de discuter de l'une ou l'autre initiative inspirée pouvant faire l'objet dun autre sujet de MFE ou de préciser le cadres, le contenu et les attentes relatives au sujets présentés.

Exploration, exploitation and evaluation of the .Net Linq library for the problem of object permanence.

The MFE will consist in a deep exploration of the very new microsoft Linq library which aims at resolving the classical problem of mapping between the OO and the relational and the XML world. The different additions of .Net necessary to the implementation of this library will be studied. The library will also be tested in terms of robustness and performance as compared with the previous existing solutions.

Etude et réalisation orientée objet d'une cellule minimale

Le MFE consistera en un développement orienté objet d'une cellule biologique minimale avec son métabolisme chimique interne, un génome élémentaire et sa membrane. Cette cellule devra être capable de croître et de spontanément se dupliquer. Il fera suite à un MFE déjà réalisé il y a deux ans.

Data/text mining - Traitement automatique de documents sur base de leur contenu

Ce sujet est destiné aux étudiants en Informatique ou en Sciences Appliquées. Il pourrait être traité par un groupe de deux étudiants.

Au cours de ce travail, nous nous interesserons a l'application d'algorithmes de traitement automatique de documents dans le cadre d'un projet (projet STRATEGO) avec les sociétés IRIS, Mentis et Denali. Nous serons confrontés par exemple à la categorisation (classification) de documents sur base de leur contenu ainsi qu'au clustering de documents.

Les developpements seront effectués en Java, C++, Perl, Python, Matlab ou S-Plus (R).

Il s'agit donc d'un travail de recherche et développement.

Etude de la topologie de réseaux lexicaux extraits de documents

De plus en plus de scientifiques sont convaincus qu’une même topologie de réseaux (c'est-à-dire la manière dont les nœuds en sont connectés) se retrouve dans de nombreux réseaux, pourtant extraits de réalités très diverses (Web, Internet, réseaux sociaux, biologiques, épidémiques). Cette topologie leur conférerait des propriétés intéressantes comme une plus grande robustesse ou une communication réduite entre les nœuds. Il est possible de construire des réseaux lexicaux à partir d’un document quelconque, par exemple, en connectant deux mots qui apparaissent dans une même phrase. Le MFE consistera en un développement logiciel ayant pour but la réalisation automatique de ces réseaux lexicaux à partir d’une variété de documents et l’étude automatisée de leur topologie : distance inter-nœuds, degré de clustering, etc …

Expérimentation des designs patterns pour la modélisation de systèmes biologiques complexes

Tout bon informaticien se doit aujourd’hui de maîtriser ces recettes de conception OO que sont les designs patterns. Au-delà des langages de programmation ou de modélisation (UML), ils sont devenus le sujet d’étude et de développement le plus prisé de la communauté informatique. Leur maîtrise permet à ces mêmes informaticiens d’attaquer la simulation de procédés complexes avec plus de facilité. Le MFE consistera en la mise en pratique de ces designs patterns pour la modélisation de systèmes biologiques complexes comme le système immunitaire ou les mécanismes de régulations génétiques. Le travail devrait déboucher sur une adaptation de ces mêmes designs patterns au monde et aux problèmes de la biologie.

Etude de la topologie de réseaux de musiciens de Jazz

De plus en plus de scientifiques sont convaincus qu’une même topologie de réseaux (c'est-à-dire la manière dont les nœuds en sont connectés) se retrouve dans de nombreux réseaux, pourtant extraits de réalités très diverses (Web, Internet, réseaux sociaux, biologiques, épidémiques). Cette topologie leur conférerait des propriétés intéressantes comme une plus grande robustesse ou une communication réduite entre les nœuds. Il est possible de construire un réseau de musiciens de Jazz connectant deux musiciens dès lors qu’ils ont joué sur un même disque. Le MFE consistera en un développement logiciel ayant pour but la réalisation automatique de ces réseaux de musiciens à partir de documentations sur les disques téléchargés automatiquement de sites de vente en ligne.

Evolution de circuits logiques

Depuis quelques années, de nouvelles techniques d'optimisations comme les algorithmes évolutionnistes servent de méthodologie d'aide à la conception. De par leur nature, ces techniques offrent une approche “bottom-up” qui peut sortir des sentiers battus que sont les les approches classiques dite “top-down”. C'est par exemple le cas en conception de circuits logiques et électroniques. Ainsi, cette nouvelle méthodologie de conception assistée par des algorithmes d'optimisation permet de parfois souligner de nouvelles idées inconnues de l'homme jusqu'à ce jour. Ce mémoire se concentrera sur les algorithmes évolutionnistes comme aide à la conception de circuits logiques. Il s'inscrira dans la continuité d'un mémoire effectué en 2007-2008 sur le même sujet. Il s'agira, par exemple, de mettre en oeuvre des techniques pour détecter des motifs récurrents de portes qui peuvent apparaitre, et ainsi permettre une construction automatique de la modularité de la solution. Ou encore de développer une approche multi-objective de la question.

Mise au point d’un système automatique de génération de code à partir d’un diagramme d’état-transition

Le diagramme d’état-transition représente le cycle de vie d’un objet, de sa naissance à sa disparition, en suivant les différents états par lesquels cet objet transite. Il est par exemple très largement mis à l’œuvre dans la modélisation des procédures parlementaires (l’évolution des décrets de loi). C’est le cas dans plusieurs parlements belges avec lesquels IRIDIA collabore. Le MFE étudiera la possibilité d’une génération automatique de code fidèle à ces diagrammes et tout ce qui les compose.

Détection de modularités appliquée à la biochimie

En biochimie, la simulation et l'optimisation des systèmes font intervenir tant et tant de variables que les dimensions sont plus que nombreuses. Ce caractère hyperdimensionnel fait exploser d'une part l'espace de recherche, mais augmente également la difficulté de l'espace de recherche. En effet, les variables d'états du système sont souvent corrélées non-linéairement. La force de ces dépendances délimite d'ailleurs souvent des modules fonctionnels qui, une fois détectés, peuvent être mis à profit. Les nouvelles techniques d'optimisation trouvent ainsi un écho logique dans le domaine de la bioinformatique ou de la chimie pharmaceutique. Au cours de ce mémoire, l'étudiant mettra en oeuvre diverses techniques se basant sur un principe de modularité. Il les analysera et les comparera sur un problème appliqué dans les domaines précités (diverses possibilités envisageables). Ce travail se constitue donc principalement comme une recherche appliquée où une méthodologie expérimentale rigoureuse sera requise.

Software framework for Ant Colony Optimization

Ants have inspired a number of computational techniques and among the most successful is ant colony optimization (ACO). ACO is an optimization technique that can be applied to tackle a wide variety of computational problems that arise in computer science, telecommunications, and engineering. While ACO has a very wide applicability, the development times for effective ACO algorithms can be relatively high. This is due to the fact that each time a new problem is to be tackled by an ACO algorithm, a researcher needs to implement the algorithms almost from scratch.

The goal of the project is to provide a software framework to support the application and the implementation of ACO algorithms to new problems. The software framework will offer all the standard procedures that are used in ACO algorithms and will allow for the rapid prototyping of ACO algorithms. The application of this software framework will be tested on a number of optimization problems.

Required skills: The candidate should be well acquainted with programming in object oriented languages.

Optimising Ant Colony Algorithms for Performance

Ants have inspired a number of computational techniques and among the most successful is ant colony optimization (ACO). ACO is an optimization technique that can be applied to tackle a wide variety of computational problems that arise in computer science, telecommunications, and engineering.

The goal of this project is to improve the performance of ACO algorithms by investigating and testing various implementation techniques: intrinsic functions (MMX/SSE floating-point operations), CPU cache effects, or GPU programming.

Required skills: knowledge of C programming. Some knowledge about computer architecture.

Graphical Tools for analysing Multi-Objective Data.

In multi-objective problems, not only one objective function must be minimised but several, often conflicting, objectives must be taken into account. The result is often a set of solutions modelling the trade-off between the objectives of the problem.

The goal of this project is to develop graphical tools to interactively examine and compare the results of algorithms for multi-objective problems.

Required skills: The candidate should be well acquainted with programming in object oriented languages.

Swarm robotics using the e-puck platform

The e-Puck is a robot developed by the Ecole Polytechnique Fédérale de Lausanne, Switzerland. It is equipped with a dsPIC micro-controller, it has an RS232 and a bluetooth interface, 8 infrared proximity sensors, a 3 axis accelerometer, 3 microphones and a speaker, a color camera with a resolution of 640×480 pixels and 8 red leds for displaying patterns.

In the last years, a number of projects carried out at IRIDIA developed a set of tools and a fully functional platform to work efficiently with e-puck robots. In particular, a precise description of the properties of the robots, software libraries and an accurate simulator are now available. A number of controllers were developed and successfully tested on the robots.

The goal of the project ``Swarm robotics using the e-puck platform'' is to design and carry out experiments of swarm robotics that are typically bio-inspired and involve several robots. Possible experiments include p2p communication networks for path finding, flocking for exploration, transport of objects and aggregation of robots. 12 e-Puck will be available for the project.

The project is tightly connected to the research in swarm robotics carried out at IRIDIA and in particular to the EU funded Swarmanoid project, the aim of which is to study new approaches to the design and implementation of self-organizing and self-assembling artifacts. See http://www.swarmanoid.org for more details.

Required skills: The candidates should be acquainted with C/C++ programming and have a working knowledge of the English language.

Simulation et optimisation de trafic routier

Mentis, spin-off du laboratoire IRIDIA, est une société de consultance spécialisée en Data Mining et en Text Mining. Mentis cherche actuellement des mémorants pour lancer diverses études d’optimisation dans le domaine de la simulation de trafic routier.

Dans le cadre d’un projet pour un de ses clients, Mentis travaille actuellement dans le domaine de la simulation de trafic routier. L’objectif du mémoire proposé consiste à lancer plusieurs études d’optimisation pour évaluer l’impact de différentes politiques routières sur le trafic. Il sera demandé à l’étudiant de mettre en œuvre diverses techniques d’optimisation afin de déterminer les politiques routières optimales. Une grande partie du mémoire sera faite dans les bureaux de Mentis ainsi qu’en interaction directe avec le client.

Comparison of fast heuristics for the longest common subsequence problem

The longest common subsequence (LCS) problem has important applications in Computational Biology. Several heuristic methods have been proposed to obtain approximate solutions. These methods require different computation time and obtain solutions of varied quality. In this project, the student will learn several methods that have been proposed in the literature to tackle a difficult optimization problem, and compare them in terms of computation time and quality of the resulting solutions. The final goal is to propose appropriate combinations of existing methods that solve diverse instances of the LCS problem.

Applications of the Multi-objective ACO framework

We have recently developed a software framework of Ant Colony Optimization algorithms for multi-objective optimization problems. This framework has only been applied to a few problems. The goal of this project would be to extend this framework to other problems and compare its results with the methods proposed in the literature. The student will learn to solve multi-objective optimization problems with ACO algorithms, automatic configuration of optimization algorithms, and analysis and comparison of optimization algorithms for multi-objective problems.

A graphical interface for the optimisation of Water Distribution Networks

The optimization of the operations of Water Distribution Networks may save important amounts of energy and its associated costs, and, therefore, it is an important problem in practice. There are graphical tools and simulators available. In addition, several optimization methods based on evolutionary algorithms and ant colony optimization have been proposed in the literature. The goal of this project is to integrate the optimization algorithms into a graphical environment that can be used by water engineers and operators. No knowledge about water distribution networks is necessary. The optimisation algorithms and toolkit libraries for handling water distribution networks will be available to the student.

Automatic fine-tuning of an evolutionary multi-objective framework

The goal of this project is to explore the possibilities of using automatic configuration tools for fine-tuning an existing evolutionary multi-objective framework. The student will learn about automatic configuration tools, evolutionary algorithms for multi-objective optimization problems and analysis and comparison of multi-objective algorithms.