Laboratoire de Génie Informatique et d’Automatique de l’Artois

Séminaire

une méthode d’optimisation génétique "Spacing Memetic Algorithms" (ref. http://www.lgi2a.univ-artois.fr/ porumbel).

Le 20 novembre 2012 à 14h00 Salle des séminaires du LGI2A, FSA, Béthune
Daniel PORUMBEL Maître de conférences LGI2A

La première partie de la présentation porte sur une méthode
d’optimisation construite à partir des algorithmes mémétiques
(algorithmes génétiques qui incorporent une routine de recherche
locale à la place de l’opérateur de mutation). Ces algorithmes
mémétiques ont une forte capacité d’intensification grâce à la
recherche locale ; cependant, cela peut souvent conduire à une
convergence trop rapide, prématurée. Autrement dit, les individus de
la population peuvent devenir quasi-identiques après un nombre limité
d’itérations. On propose d’utiliser une distance dans l’espace de
recherche afin de contrôle l’espacement entre les individus et la
dynamique de la population. On présente des tests numérique sur
plusieurs problèmes d’optimisation discrète, avec plusieurs mesures de
distance.

Partie 2 : Programmation en Ruby et son intérêt pour les étudiants
non-informaticiens qui veulent faire de la recherche en optimisation.

Dans la deuxième partie de la présentation, je présente quelques
applications possibles du langage Ruby dans ce type de travaux de
recherche. Par exemple, le code ci-dessous permet d’exécuter une
descente pure sur une instance du problème du voyageur de commerce.

n=4

s=Array.new(n)

d=Array.new(n,Array.new(n))

d[0]=[0,1,2,6]

d[1]=[1,0,4,7]

d[2]=[2,4,0,5]

d[3]=[6,7,5,0]

def trajet(sol,d,n)

somme=0

for i in (0..n-1) do

somme = somme + d[sol[i]][sol[i+1]]

end

return somme

end

for i in 0..n do

s[i]=i%n

end

puts "Trajet de départ :"+s.to_s()

trajetpluspetit = true

while (trajetpluspetit) do

trajetpluspetit = false

for i in 1..n-2 do

for j in i+1..n-1 do

s2=s.dup()

s2[i]=s[j]

s2[j]=s[i]

if trajet(s2,d,n)<trajet(s,d,n) then

s=s2

trajetpluspetit = true

end

end

end

end

puts "Trajet final :"+s.to_s()