Algorithme d’orchestration

Algorithme d’orchestration

Encore une fois, la formulation 9.2 incite à considérer le problème de l’orchestration comme un problème de sac à dos multicritère à conteneurs multiples. Mais, comme nous l’avons dit au paragraphe précédent, la non-linéarité (et plus particulièrement la non-additivité) des fonctions objectifs à minimiser ne peut que nous en dissuader. Aussi séduisant soit-il, le cadre formel du sac à dos n’est pas assez souple pour supporter la complexité des mélanges de timbres.de la base de données est retenu dans l’orchestration, 0 sinon. On serait donc facilement tenté d’avoir recours à la technique d’encodage la plus répandue dans les algorithmes géné- tiques, qui consiste à représenter les solutions par des chaînes binaires (bit-string encoding), ici de longueur Nsons. Pour une population de 1000 individus, l’encodage du type bit-string implique donc le stockage et la mise à jour récurrente d’une matrice à 5 millions d’éléments. Même si cela reste encore acceptable, la taille mémoire deviendra vite une limite sitôt que nous travaillerons avec davantage de sons et des populations potentiellement plus grandes.2. Le petit nombre d’items impliqués dans une solution. Dans notre problème d’orchestration au maximum une petite centaine de sons (dans le cas de très grands orchestres) seront choisis parmi plusieurs milliers, occasionnant une fréquence très faible de valeurs égales à 1 dans la matrice représentant la population. On pourrait certes choisir d’avoir recours à une représentation parcimonieuse des données, mais cela ne résout pas le problème des contraintes multiples de capacité (cf. infra).

La multiplicité des contraintes de capacité. Dans le problème du sac à dos, la seule contrainte est la capacité globale du sac. La gestion des solutions inconsistantes produites au cours des générations fait en général appel à une méthode de réparation de type « glouton » qui retire récursivement les éléments les plus volumineux jusqu’à ce que la contrainte de capacité soit satisfaite ; éventuellement, des items plus petits peuvent alors être insérés dans le sac s’il reste de la place. En orchestration, il y a autant de contraintes de capacité que de type d’instruments, soit onze contraintes pour l’instrumentarium actuellement à disposition, et leur respect exige le recours à autant de procédures de réparation. Autant donc chercher une représentation qui permette de s’en affranchir. Remarque 9.2. Comme nous le verrons au paragraphe suivant, les opérateurs génétiques sont stables sur D. Toute configuration générée aléatoirement ou produite par une opération génétique est donc, par définition, consistante avec les contraintes de capacité (i.e. liée aux effectifs instrumentaux de l’orchestre).Lorsque deux chromosomes parents sont recombinés non pas par un crossover uniforme, mais, comme c’est souvent le cas, par un crossover monopoint (voir figure 5.5, les gènes éloi- gnés ont plus de chances d’être séparés par le crossover que les gènes voisins dans la chaîne (voir Whitley [Whi93]). Cette propriété est parfois souhaitable dans le cas de représentations binaires échantillonnant un espace de décisions à valeurs réelles, pas dans le cas de l’orchestra- tion. Considérons par exemple un quatuor à cordes représenté par des quadruplets (violon1, violon2, alto, violoncelle), comme il en va sur la figure 9.1. Le crossover monopoint sépa- rera toujours le premier violon du violoncelle, et maintiendra toujours l’un des duos (violon1, violon2) ou (alto, violoncelle). En d’autres termes, le potentiel exploratoire du crossover mo- nopoint dépend de l’ordre dans lequel les instruments de l’orchestre sont encodés dans les chromosomes. Le crossover uniforme n’implique quant à lui aucune de ces restrictions, raison pour laquelle nous le préférons pour l’orchestration.

Dans notre algorithme d’orchestration la fitness (i.e. l’adaptabilité d’un individu à son environnement) est calculée à l’aide de fonctions scalarisantes de Tchebycheff, car cette ap- proche est en lien direct avec notre problématique d’inférence des préférences d’écoute du compositeur (voir sections 7.2.4 et 8.5.1). A chaque itération de l’algorithme, la population est évaluée avec un jeu de poids différent, donc selon des préférences d’écoute différentes. Si λ = (λLorsque l’algorithme se termine, le compositeur peut, s’il le désire, « relancer » la rechercheà partir d’une solution efficiente courante. La direction de recherche est alors « figée » par la norme induite par la solution choisie (cf. section 8.5.1). Le même algorithme est utilisé, cette fois-ci avec les poids associés à la norme induite, déterministes et invariants. La direction d’optimisation fixée, le problème devient alors mono-critère. Grâce à l’approche par fonctions scalarisantes, la méthode permettant d’« affiner » une solution intermédiaire n’est donc pas conceptuellement différente de l’algorithme de « recherche globale ». Seul change le caractère des poids : ils n’y sont plus aléatoires, mais fixés par le choix intermédiaire du compositeur.