Version originale en anglais au format PDF ou HTML Traduit en mai 2002 par Joël Eymard pour http://la.trompette.free.fr
Optimisation informatique des cuivres par Wilfried Kausel (suite)
Les différents algorithmes d'optimisation
Dans cet article on montrera comment la modélisation
des instruments par ligne de transmission est combinée avec un jeu d'algorithmes
d'optimisation informatiques pour créer un outil puissant, le "Brass
Instrument Optimization Software" (BIOS)
[16]
[17]
.
Il a été développé pour aider les fabricants d'instruments
à améliorer les instruments existants aussi bien qu'à en
concevoir de nouveaux selon une spécification donnée. Quand des
instruments historiques doivent être reconstruits à partir de peintures
ou de descriptions, la modélisation par ligne de transmission peut aider
à en prévoir les caractéristiques essentielles et le programme
optimiseur peut être utilisé pour les rendre jouables au lieu de
gaspiller des matériaux et d'innombrables heures de travail dans un processus
d'essais et de correction d'erreurs.
On considère parfois l'optimisation informatique comme un art plutôt
qu'une science, en particulier quand on parle des approches génétiques
ou de recuit simulé
[6]
. La raison est qu'il faut habituellement beaucoup
d'expérience, une connaissance approfondie du sujet et parfois de l'intuition
pour choisir les bonnes variables d'optimisation et leurs plages de variation,
créer une fonction cible qui reflète vraiment les intentions de
son créateur et trouver une bonne combinaison de valeurs initiales pour
tous les paramètres de l'algorithme d'optimisation.
Le programme d'optimisation présenté ici met
en œuvre plusieurs stratégies d'optimisation différentes.
Un très ancien algorithme, déjà proposé au début
des années soixante et qui a été presque oublié
et remplacé par plusieurs approches modernes, comme le recuit simulé,
le recuit simulé adaptatif et toute la famille des algorithmes génétiques,
s'est révélé être le gagnant - au moins jusqu'ici.
Il a été capable de trouver de bons compromis même avec
des objectifs d'optimisation difficiles à atteindre, voire contradictoires,
et il a parfaitement réussi dans le défi suprême de créer
complètement un instrumentà partir de zéro en tant que
"concepteur informatisé d'instrument". Cet algorithme dit de
Rosenbrock sera décrit plus en détail dans la section suivante.
Ses résultats ont été comparés avec les résultats
de cinq autres stratégies, qui ont aussi été évaluées.
Toutes sont des algorithmes dits "génétiques"
[9]
, où des "individus-trompettes" se reproduisent par accouplement
pour former des populations, qui sont exposées à la sélection
naturelle. Les enfants héritent des propriétés de base
des deux parents et de mauvaises trompettes ont une chance beaucoup plus petite
de se reproduire car elles peuvent mourir plus tôt. On met en œuvre
des mutations aléatoires ainsi que des populations parallèles
indépendantes avec quelques individus migrant de l'une à un autre.
La première approche qui a été mise en œuvre est "l'algorithme
génétique simple" tel que décrit par Goldberg
[13]
.
Il utilise des populations non chevauchantes et l'élitisme optionnel.
L'élitisme signifie que les meilleurs individus sont directement déplacés
d'une génération à la suivante, les rendant d'une certaine
façon immortels - au moins jusqu'à ce que de meilleurs individus
prennent leur place. A chaque génération l'algorithme crée
une population entièrement nouvelle d'individus.
La deuxième approche est un "algorithme génétique
stationnaire" qui utilise des populations se chevauchant. On peut spécifier
quelle part de la population doit être remplacée à chaque
génération.
La troisième variante est "l'algorithme génétique
progressif", dans lequel chaque génération consiste en seulement
un ou deux enfants. Les algorithmes génétiques progressifs permettent
de spécifier les méthodes de remplacement qui définissent
comment la nouvelle génération doit être intégrée
dans la population. Ainsi, par exemple, un enfant nouvellement engendré
peut remplacer son parent, remplacer un individu aléatoire dans la population,
ou remplacer un individu qui lui ressemble étroitement.
Le quatrième type est l'algorithme génétique "Deme".
Cet algorithme fait évoluer de multiples populations en parallèle
en utilisant un algorithme stationnaire. A chaque génération l'algorithme
transfère certains des individus de chaque population à une des
autres populations.
Le dernier mis en œuvre est un "modèle de cohue déterministe"
basé sur l'algorithme génétique stationnaire tel que proposé
par Goldberg. Comme les autres algorithmes génétiques il est tiré
du progiciel d'algorithme génétique GAlib, écrit par Matthew
Wall au Massachussetts Institute of Technology (MIT)
[6]
.
Le type de génome, qui a été associé aux individus-trompettes,
était le génome dit de suite binaire. Chaque paramètre
d'optimisation a été quantifié dans sa plage de variation
selon une résolution de paramètre minimale spécifiée
et le nombre de bits requis a été alors placé à
l'emplacement vide suivant de la suite binaire. Les populations sont initialisées
aléatoirement et les mutations sont des erreurs de bits simples aléatoires
créées dans la suite binaire avec une probabilité donnée.
La méthode de croisement par défaut, qui était normalement
utilisée, consiste à déterminer une position de bit aléatoire
dans les chromosomes des parents, et à créer ensuite un fils avec
la partie inférieure de la suite de son père et la partie supérieure
de la suite de la mère, et à créer une fille avec les segments
restants.
Quelques inconvénients de cette implémentation simple sont immédiatement
évidents. L'un est qu'une position de départ déjà
bonne est complètement perdue pendant l'initialisation d'une population.
La plage de variation spécifiée est utilisée pour l'initialisation
aléatoire aussi bien que pour les mutations aléatoires.
Un autre est que la probabilité de créer une amélioration,
pour une mutation d'un simple bit, est presque nulle. Dans le paragraphe de
résultats ci-dessous, il sera évident qu'il y a beaucoup trop
de liberté de créer des formes folles et sans signification. Pour
que les algorithmes génétiques soient compétitifs, une
représentation de données complètement différente
serait nécessaire.
La méthode d'optimisation qui a donné les meilleurs
résultats jusqu'ici, a été décrite par Schwefel
dans
[8]
. À l'origine elle a été publiée par Rosenbrock
en 1960 [7]
. Dans le passé cet algorithme a déjà été
utilisé avec succès par l'auteur pour l'optimisation de fonctions
cibles avec jusqu'à 50 paramètres et plus (pour des filtres digitaux
et analogiques ou la conception de circuit électrique). La stratégie
est basée sur un algorithme de recherche très stable d'ordre 0
qui n'exige pas de dériver la fonction cible bien qu'il s'approche d'une
méthode de gradient. Donc il combine les avantages des stratégies
d'ordre 0 et 1.
La première itération est une simple recherche d'ordre 0 dans
les directions des vecteurs de base d'un système de coordonnées
à n dimensions. En cas de succès, un essai fournissant une nouvelle
valeur minimale de la fonction cible, la longueurs de pas est augmentée,
tandis que dans le cas d'un échec elle est diminuée et on essaye
la direction opposée.
Une fois qu'un succès a été trouvé et exploité
dans chaque direction de la base, le système de coordonnées est
réorienté pour que le premier vecteur de base soit dans la direction
du gradient. Toutes les longueurs de pas sont réinitialisées et
le processus est répété en utilisant le nouveau système
de coordonnée. En initialisant les longueurs de pas à des valeurs
plutôt grandes, on permet à la stratégie de laisser de côté
des optimums locaux et de continuer la recherche de minimums plus globaux.
Il s'est avéré que cette approche simple est
plus stable que beaucoup d'algorithmes sophistiqués et exige beaucoup
moins de calculs de la fonction cible que des stratégies plus élaborées
[8]
. À cause de cette stabilité inhérente et avec de bonnes
heuristiques pour le calcul des longueurs de pas, cet algorithme est même
approprié et a déjà prouvé sa valeur pour des problèmes
d'optimisation impliquant des fonctions d'objectif fortement non-linéaires
et non monotones.
Finalement un utilisateur qui n'est pas un expert en optimisation a une chance
réelle de le comprendre et de fixer et ajuster ses paramètres
correctement. Des procédures de contrôle heuristiques ont été
mises en œuvre pour ajuster les paramètres d'optimisation en cours
d'exécution dès que l'optimisation ralentit ou se bloque. Cela
permet de réussir des optimisations sans aucune intervention d'utilisateur.
Introduction
Modélisation des cuivres
Modèle de ligne de transmission
pour l'optimisation
Les différents algorithmes d'optimisation
L'algorithme de Rosenbrock
Représentation de la géométrie
de l'instrument
Calcul de l'impédance d'entrée
Objectif de la fonction d'optimisation
Résultats d'optimisations
Références