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()