Orchestration musicale par optimisation
Orchestration musicale par optimisation
Prpare lIRCAM
par
Grgoire Carpentier
. . . Grard Assayag pour sa confiance et son soutien, Emmanuel Saint-James pour ses
conseils et sa prcieuse relecture du manuscrit ;
. . . Hugues Vinet pour son accueil au sein du dpartement scientifique de lIRCAM, Arshia
Cont pour son enthousiasme et pour les rencontres qui nauraient pas eu lieu sans lui ;
. . . Yan Maresz pour son implication et sa foi dans le projet Orchestration, ainsi qu Damien
Tardieu pour la richesse de nos changes ;
. . . aux nombreux compositeurs avec qui jai collabor, Marco Suarez, Oscar Bianchi, Jonathan
Harvey, Joshua Fineberg, Grard Buquet, Mauro Lanza, Tristan Murail, Raphal Cendo ;
. . . mes parents, mes grand-parents, tous ceux qui mont soutenu, Sigrid.
v
Table des matires
Remerciements v
Rsum xi
Abstract xiii
Introduction xv
0.1 Dmarche scientifique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvi
0.2 Structure du manuscrit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xviii
0.3 Grilles de lectures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xx
0.4 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xx
1 Informatique musicale 25
1.1 Musique et technologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.2 Le tournant de llectronique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
1.3 Fonctions de lInformatique musicale . . . . . . . . . . . . . . . . . . . . . . . . 26
4 Aide lorchestration 43
4.1 Convergence et maturit des savoirs . . . . . . . . . . . . . . . . . . . . . . . . 43
4.2 Discours de compositeurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
vii
4.3 Outils actuels daide lorchestration . . . . . . . . . . . . . . . . . . . . . . . . 45
7 Formulation du problme 85
7.1 Donnes du systme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
7.2 Paradigmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
7.3 Dfinitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
7.4 Formalismes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
7.5 Contraintes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
7.6 Dun espace lautre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
Conclusion 217
IV Annexes 223
Glossaire 239
Bibliographie 247
Rsum
xi
Mots cls : Orchestration, composition assiste par ordinateur, informatique musicale, timbre,
description du signal, descripteurs perceptifs, optimisation multicritre, algorithmes volution-
naires, programmation par contraintes, contraintes globales, recherche locale.
Abstract
Among all techniques of musical composition, orchestration has never gone further than
an empirical activity. Practicing and teaching orchestration the art of blending instrument
timbres together involve hard-to-formalize knowledge and experience that computer music
and composition systems have for years stayed away from.
The state-of-the-art orchestration tools search for sound combinations within instrument
sample databases that best match a target timbre defined by the composer. To this end, those
methods use either decomposition or matching pursuit algorithms, and therefore circumvent
to the combinatorial problem of orchestration. We propose in this thesis an original approach
for the discovery of relevant sound combinations, in which we explicitly address combinatorial
issues and tackle orchestration in its inner complexity.
Initial considerations of the problem in a multiobjective knapsack framework shows that
non-linearity and non-additivity of objective functions require a wider theoretic approach. We
suggest a generic and easily extendible formalization of orchestration as a constrained mul-
tiobjective search towards a target timbre, in which several perceptual dimensions are jointly
optimized. We first validate our approach on a small-size problems test set, with a rather
simple, spectral-based timbre description. We show that theoretic solutions of the optimiza-
tion problem correspond to perceptually relevant orchestration proposals. We then introduce
a time-efficient evolutionnary orchestration algorithm allowing the discovery of optimal solu-
tions. By estimating acoustic properties of sound mixtures, our method suggests orchestration
proposals in relation with perceptual criteria and favors the exploration of somehow non-
intuitive sound mixtures. From there, the search may be pursued in specific directions. To
enhance the control of symbolic features in orchestrations proposals, we define a formal fra-
mework for global constraints specification and introduce an innovative repair metaheuristic.
Thanks to this method the search is led towards regions fulfulling a set of musical-related
requirements.
We finally present a composer-friendly computer-aided orchestration prototype, in which
timbre space exploration is encouraged by a multiple viewpoints representation and an inter-
active mecanism for guessing the composers listening preferences. We end this thesis with
relevant application examples in real musical works.
Key words : Orchestration, computer-aided composition, computer music, audio signal des-
cription, perceptual audio features, multi-objective optimization, evolutionary algorithms,
constraint programming, global constraints, local search.
xiii
Introduction
Nos travaux sont ns dune problmatique dcriture musicale, terrain dlicat pour la re-
cherche scientifique qui touche l une technique dont lapprciation est soumise un jugement
esthtique, et dont les mcanismes paraissent difficilement formalisables. Au yeux des no-
phytes, linformatique musicale est souvent perue comme un non-sens, et la question des
rapports entre musique et ordinateur, dplace. Pourtant Varse lexprime travers la no-
tion d art-science la musique nest pas un simple cran de projection pour les techniques,
mais une entit bicphale o lart et la technologie ne cessent de sinterroger.
A ceux qui avancent que les compositeurs nont pas besoin dun ordinateur pour crire, nous
pourrions rpondre que lhomme na pas besoin non plus dun systme symbolique complexe
de notation, ni mme dinstruments pour produire de la musique. Il lui suffit douvrir la
bouche. Mais depuis les temps primitifs o le chant tait la seule pratique musicale, les socits
ont volu vers des formes bien plus complexes, et la musique ne peut faire autrement que
cristalliser cette complexit. En tmoignent aujourdhui la richesse des formes et des pratiques
dexpression musicale, ainsi que la rcurrence avec laquelle sont mis en question les rapports
entre musique et socit.
Lhistoire de la musique est jalonne de ruptures qui marquent ces moments critiques o
les ressources du systme musical ne suffisent plus pourvoir son besoin de complexit .
La musique se tourne alors vers la technologie, dont lapport nest pas synonyme dun ap-
pauvrissement des comptences, mais au contraire dun enrichissement du vocabulaire et des
pratiques. En retour la recherche scientifique, lorsquelle se penche sur des problmatiques mu-
sicales, na dautre choix que de laborder dans sa complexit. Imprgne de la complexit
du monde contemporain, la musique sollicite la science tout autant quelle la dfie : la seconde
peut-elle penser la complexit comme la premire la reflte ?
Les problmatiques musicales qui nous intressent ici concernent une discipline particulire
de lcriture : lorchestration, ou lart de mlanger les timbres, dallier les potentialits sonores
des instruments pour produire des couleurs particulires. Aujourdhui, lorchestration de-
meure le seul domaine de lcriture musicale ntre que trs peu abord par linformatique,
alors que les compositeurs rclament depuis plusieurs dcennies un outil dexploration et de
contrle du timbre orchestral qui tiennent compte de la formidable extension, depuis le dbut
du XXe xicle, des possibilits instrumentales. Daprs nous, cette lacune tient la difficult de
xv
xvi INTRODUCTION
formaliser les relations complexes entre les variables symboliques de lcriture et les proprits
perceptives des mlanges instrumentaux. A y regarder de prs, la complexit de lorchestration
se dcline selon trois axes : complexit combinatoire, complexit de la perception du timbre,
et complexit de lvolution temporelle. Si quelques rares systmes daide lorchestration
existent aujourdhui, aucun dentre eux ne traite ne serait-ce que lune de ces dimensions : le
temps nest jamais modlis, le problme combinatoire est toujours contourn, le timbre est
rduit une unique dimension.
Le travail que nous prsentons dans cette thse a t motiv par le dsir daborder, autant
que faire ce pouvait, le problme de lorchestration dans toute sa complexit.
2
Ces deux dimensions de lcriture se rfrent au plan de la partition. Lcriture verticale dsigne lagen-
cement des diffrentes voix (cest--dire les instruments de lorchestre) un instant donn, l o lcriture
horizontale concerne le dveloppement dans le temps dune seule voix.
xviii INTRODUCTION
Il nous faut encore signaler ici qu lheure o nous crivons ces lignes, lintgration au sein
de notre outil du travail de Damien Tardieu sur les modles dinstruments na pas encore t
effectue. Toutefois notre systme, bien que bas sur une connaissance rduite des possibilits
instrumentales, nous a dj permis dobtenir des rsultats significatifs, laissant augurer des
performances dcuples grce aux modles dinstruments. Aussi ne manquerons-nous pas de
discuter, en divers endroits de cette thse, leur apport potentiel pour laide lorchestration.
mergence comme fonction essentielle de lcriture musicale au XXe sicle jusqu sa compr-
hension travers des tudes perceptives psychoacoustiques, et sa caractrisation par lanalyse
et la description du signal audio, un clairage multiple est port sur la complexit de cet
objet dtude. Le chapitre 3 traite de lorchestration musicale proprement dite, expose les
fondements et les limites de sa pratique traditionnelle et tente de dgager le rle potentiel de
lordinateur dans une vision contemporaine de lorchestration. Nous montrons ensuite (cha-
pitre 4) en quoi la rencontre entre, dune part, le besoin actuel des compositeurs, et dautre
part des technologies et des savoirs suffisament matures, ouvre un vaste champ de recherche
pour lorchestration assiste par ordinateur. Nous prsentons les contributions rcentes dans
le domaine, exposons leurs apports et leurs limites et discutons en quoi ces dernires peuvent
tre dpasses. Au chapitre 5, nous entrons au cur de notre sujet de recherche : nous intro-
duisons les concepts fondamentaux des approches multicritres et proposons un tat de lart
des mthodes doptimisation combinatoire, en portant une attention toute particulire aux
algorithmes gntiques. Nous dtaillons en outre deux concepts rcents dont sinspire notre al-
gorithme de recherche dorchestrations, lagrgation des critres par fonctions scalarisantes de
Tchebycheff et lestimation de la densit locale au sein de la population par la mthode PADE
(Population size Adaptive Density Estimation). Enfin, le chapitre 6 est consacr au paradigme
de programmation par contraintes et aux mthodes associes, ainsi qu leur utilisation en
informatique musicale. L encore, nous approfondissons deux heuristiques de recherche locale
ayant influenc nos travaux, la recherche adaptative et lheuristique CN -Tabou.
0.4 Contributions
La contribution de notre travail la littrature se rsume en sept points :
une formalisation gnrique et extensible du problme de laide lorchestration (chapitre
7) comme une tche doptimisation multicritre sous contraintes ;
une validation exprimentale (chapitre 8) de la pertinence de descripteurs spectro-
harmoniques pour la caractrisation perceptive du timbre dans le cadre de sons com-
plexes ;
un algorithme volutionnaire doptimisation combinatoire multicritre adapt au pro-
blme de lorchestration (chapitre 9) ; respectant lquilibre entre intensification et di-
versification de la recherche et pouvant tenir compte des prfrences de lutilisateur.
une gnralisation des notions dinstanciation partielle et de consistance locale dans les
problmes de satisfaction de contraintes, travers les concepts de contraintes de design
et contraintes de conflit ;
une mtaheuristique de recherche locale pour la satisfaction de contraintes globales (cha-
pitre 10), sappuyant sur la distinction entre contraintes de design et contraintes de
conflit.
0.4. CONTRIBUTIONS xxi
une validation exprimentale, sur des instances de petite taille, de lefficacit des deux
mthodes prcdentes (chapitre 11) ;
un prototype exprimental daide lorchestration (chapitres 12, 13 et 14), facilitant lex-
ploration du timbre orchestral via une reprsentation multi-points de vue des solutions
et favorisant la dcouverte des prfrences implicites du compositeur.
xxii INTRODUCTION
Premire partie
23
Chapitre 1
Informatique musicale
Les amalgames trop frquents entre informatique musicale, musique assiste par ordina-
teur, musique lectronique et musique contemporaine sont source de bien des malentendus.
Si lordinateur est devenu un outil incontournable pour les musiciens actuels, linformatique
musicale se limite pour la plupart des utilisateurs aux squenceurs, instruments virtuels et
diteurs de partition. Les rapports riches et multiples entre ordinateur et cration musicale
contemporaine (et plus gnralement entre informatique et musique) sont la plupart du temps
dnigrs ou incompris du public. Du ct scientifique galement, les ides reues sont lgion.
Pour de nombreux aficionados des sciences dures , linformatique musicale fait rfrence
une poigne de chercheurs et musiciens contemporains profitant des technologies leur
disposition, et dont les objectifs thoriques ou esthtiques sont peu lisibles. En vrit, les
proccupations musicales ont toujours interrog de prs les ressources technologiques, et les
rapports entre informatique et musique vont aujourdhui bien au-del dune utilisation unila-
trale et aveugle des outils. A y regarder de prs, ils prennent davantage la forme dun change
stimulant o sont rgulirement souleves des problmatiques de reprsentation des structures
et de formalisation de la pense.
25
26 CHAPITRE 1. INFORMATIQUE MUSICALE
et par l mme, des rvolutions : elles modifient en profondeur pratique et pense musicales. Le
codage, travers la partition, de la musique sous forme symbolique a permis la manipulation
du matriau musical un niveau dabstraction plus lev que la seule pratique instrumentale.
La notion occidentale de composition sest alors enrichie de nouveaux procds (inversions,
symtries, miroirs, rptitions, imitations, esquisses. . .), rvls par la reprsentation graphique
de la musique. De faon similaire, linstauration progressive du temprament gal a conduit
la possibilit (voire la ncessit) dune musique modulante, de mme que le piano a apport
les nuances de dynamiques dans le jeu au clavier.
Possibilit offerte dabord, puis volution ncessaire, un changement technologique ne sur-
vient que lorsque la pratique ou la pense pitinent dans une impasse et ne peuvent sen
extraire avec leurs outils du moment. En mme temps quelle comble un besoin, ladoption
dune technologie engendre toujours un changement de paradigme. Cest sous ce double rap-
port de cause effet que doit tre considre larticulation contemporaine entre informatique
et musique.
2
Il suffit pour sen convaincre de considrer les multiples variations que lon peut engendrer partir dun
mme motif, procd omniprsent dans le rpertoire classique (chez Beethoven, par exemple).
28 CHAPITRE 1. INFORMATIQUE MUSICALE
dans lesquels les structures usuelles de lcriture musicale et lensemble des oprations sy
rapportant partagent le mme environnement graphique. Les environnements de CAO les plus
clbres ayant recours la programmation visuelle sont historiquement PatchWork [LD89],
Max/MSP [Puc91], Elody [OFL97] et OpenMusic [Ago98], dvelopp lIRCAM3 par
Grard Assayag, Carlos Agon et Jean Bresson, et que nous dtaillerons la partie III.
Aujourdhui, les deux courants de recherche en informatique musicale que nous voquions
en dbut de section se sont rejoints, et lon dispose actuellement doutils de CAO puissants
dans lesquels le son comme matire sensible coexiste et interagit avec des structures formelles.
Il devient donc possible pour le compositeur de relier lexploration du sonore lorganisation
de donnes symboliques, et dainsi renouer avec une conception plus classique de lcriture
dont la musique lectronique stait loigne (cf. paragraphe 1.2). Cette convergence est
toute bienvenue pour nos travaux : car lorchestration est en effet lart de contrler le timbre de
lorchestre laide des paramtres symboliques de lcriture musicale (voir chapitre 3). Aussi
verrons-nous au cours de cette thse quun des intrts thoriques majeurs de lorchestration
assiste par ordinateur rside dans le recours des reprsentations multi-chelle permettant
la mise en relation de donnes htrognes. Se dessinera ainsi, au travers de notre recherche,
un des enjeux contemporains de linformatique musicale : lintraction signal/symbolique.
3
Institut de recherche et de coordination acoustique/musique. http://www/ircam.fr/
Chapitre 2
29
30 CHAPITRE 2. LE TIMBRE, OBJET ET FONCTION
Lorchestre est peu peu vu comme une gigantesque palette sonore avec laquelle composer :
crer un nouveau son , un son dorchestre , partir de sons individuels. Le timbre, jusque
l conu comme une proprit intrinsque des instruments, va progressivement sen dtacher
pour devenir dans un premier temps llment dun nouveau langage musical, jusqu tre
pens comme le pivot central de lcriture.
Varse (et sa suite Xnakis) est sans doute le compositeur le plus emblmatique de cette
nouvelle tendance. Il sagit vritablement pour lui de crer de nouveaux timbres, de composer
le timbre en puisant dans les richesses multiples du vocabulaire instrumental. Varse a en
permanence invent de nouvelles structures sonores, et leur individualit est si marque que les
termes musicaux usuels (accord, voix, doublure. . .) ne conviennent plus pour les dcrire. [. . .]
Varse semploie crer des couches de son, et ces couches occupent lespace des hauteurs. Il y
a des bandes de sons, des strates, et lvolution de la musique est entirement gouverne par les
confluences et les disjonctions de ces strates. (Erickson, Sound Structure in Music [Eri75]).
Cette approche smantique du timbre, dont les impacts sont colossaux dans la musique
contemporaine, trouvera un cho dans la seconde moiti du XXe sicle avec la musique
concrte instrumentale , chez des compositeurs comme Lachenmann ou Sciarrino. Tirant parti
des possibilits bruitistes des instruments traditionnels, Lachenmann dveloppe et organise un
vocabulaire sonore extrment riche en une Klang Komposition . Il en ressort une musique
rapide, prcise et rigoureuse, o les timbres fourmillent au service de la composition du son.
rfrent un instrument donn. [Cependant, on peut trs bien parler du] timbre dun son
sans le rapporter clairement un instrument dtermin, mais plutt en le considrant comme
une caractristique propre de ce son. Voil donc une difficult supplmentaire : chaque ins-
trument possde son timbre, mais aussi chaque son quon en tire. Erickson [Eri75] explique
cette contradiction en rappelant quavant le XXe sicle lcriture tire parti en mme temps
quelle la conforte de la notion de consistance subjective du timbre. Une ligne mlodique
est en gnral confie un instrument ou un groupe dinstruments donns, invariants pour
lintgralit de la mlodie. Les diffrences de timbre rsultant des diffrences de hauteur et
dintensit sont alors identifies comme nuances dun timbre global qui fonctionne Erickson
use dune analogie avec la modulation de frquence comme une porteuse de la ligne
mlodique8 .
Bregman va encore plus loin : De mme quil existe le timbre dune note isole, on
peut parler de timbre orchestral pour un groupe dinstruments. (Albert Bregman, Timbre,
orchestration, dissonance et organisation auditive, in [Bar85]) Il semble falloir sy rsoudre, le
timbre renvoie plusieurs significations. Il dsigne soit lensemble des sonorits produites par
un instrument donn (fonction de consistance , ou porteuse ), soit la couleur sonore dun
son instrumental isol (fonction dissociante ), soit encore le son rsultant dune mixture
instrumentale (fonction unifiante ). Mais nous allons voir que cette polysmie peut tre
dpasse en considrant, linstar des compositeurs contemporains depuis Varse, le timbre
comme un langage, et en tentant de comprendre le rle quil remplit dans lcriture musicale.
rside dans les agrgats de timbres. Continuit et contraste, vision duale, temporelle de lop-
position boulzienne entre articulation et fusion [. . .,] les deux ples extrmes de lemploi du
timbre dans le monde instrumental. (Pierre Boulez, Le timbre et lcriture, le timbre et le
langage, in [Bar85])
Un espace de timbres est une reprsentation en deux ou trois dimensions dun corpus de
sons, chaque dimension tant relie une composante particulire du timbre. En gnral, sa
construction a lieu en quatre tapes :
1. La premire tape est la cration du corpus. Dans le cas de sons instrumentaux, il arrive
frquemment quil soient reproduits par une mthode de synthse afin de saffranchir
des conditions denregistrement et den liminer les parasites.
2. Les sons sont ensuite prsents par paires un ensemble de sujets qui doivent leur
attribuer une mesure de similarit ou de dissemblance.
3. On utilise alors une mthode de Multi-Dimensionnal Scaling (MDS) permettant de d-
terminer les coordonnes de sons dans un espace euclidien deux ou trois dimensions, de
telle manire que les distances entre les points correspondent aux dissimilarits moyennes
attribues par les sujets.
9
Chose amusante, on retrouve l les deux fonctions du timbre dans la musique du XXe sicle.
2.6. TIMBRE ET DESCRIPTION DU SIGNAL AUDIO 35
Les processus dextraction des descripteurs diffrent selon les cas. Certains descripteurs
sont calculs directement sur la forme donde du signal (autocorrlation, zero-crossing
rate), dautres ncessitent une tranformation pralable (lextraction des pics spectraux
passe par exemple par une FFT). Ils peuvent aussi tre obtenus par estimation (dans
le cas dun modle de signaux) ou dpendre dun modle perceptif (filtrage de loreille
interne, modlisation des bandes critiques. . .)
La description du son occupe certes une place importante dans nos travaux, mais non
centrale. Nous nous contenterons donc dintroduire, au chapire 8, les descripteurs utiliss par
notre systme et dici-l retiendrons deux :
1. quils peuvent tre calculs directement partir de la reprsentation du signal audio,
donc extraits automatiquement aussi bien dun son cible que dune banque dchantillons
instrumentaux ;
2. que certains dentre eux peuvent tre corrls des attributs perceptifs : le centrode
spectral peut tre reli la brillance, le taux de passage par zro (zero-crossing rate)
au niveau de bruit dans le signal, le logarithme du temps dattaque laspect percussif
du son. Encore une fois, nous renvoyons le lecteur dsirant davantage de prcisions aux
travaux de Geoffroy Peeters [PMH00].
Conclusion
En rsum, nous dirons que le timbre est une donne musicale dont la conception sest peu
peu transforme depuis la fin du XIXe sicle. Originellement considr comme un lment
tranger au systme symbolique et propre au jeu instrumental, le timbre a fait son entre dans
lcriture et en est devenu une variable centrale. Nous allons voir au chapitre suivant que lart de
lorchestration consiste justement en la matrise du timbre dans la composition. Nous verrons
en outre au long de ce manuscrit que la convergence entre lapproche psychoacoustique et le
traitement du signal travers un ensemble de mesures objectives (les descripteurs) permettra
la composition assite par ordinateur daborder le problme du timbre.
Chapitre 3
On pourrait dire de lorchestration quelle est lensemble des techniques dcriture dans les-
quelles le timbre agit comme paramtre principal. Walter Piston crit dans son trait [Pis55] :
Lorsquon analyse une orchestration, il sagit de dcouvrir comment lorchestre est utilis
pour traduire la pense musicale. [. . .] Cest un moyen dtudier la manire dont les instru-
ments se mlangent pour crer un quilibre de sonorits, lunit et la varit des timbres, la
clart, la brillance, lexpressivit, ainsi que dautres paramtres musicaux . Plus simplement,
on dira que lorchestration est lart de combiner des sonorits instrumentales pour crer des
agrgats sonores et en contrler lvolution temporelle.
Il est intressant de remarquer combien la position de lorchestration par rapport len-
semble du savoir musical varie selon les poques et les auteurs. Koechlin, par exemple, semble
la considrer comme une technique totalement asservie aux autres dimensions de lcriture :
Il faut planifier avec soin, par rapport luvre dans son ensemble, les lments orchestraux
suivants : accents, cadences, progressions dynamiques, sommets, chevauchements. Les chan-
gements de timbre sont fonction du contexte musical. Le rythme dentre ou de retrait des
timbres contribue, particulirement dans une mme phrase, aux effets de tension et de dtente.
Le degr de contraste timbral doit correspondre au degr de contraste formel : un changement
de section exige davantage de contraste orchestral que lapparition, dans une phrase, dun nou-
veau motif. (Alan Belkin, relatant Koechlin dans [Bel01]). Ce point de vue, en contraste avec
celui de Piston, reflte une conception encore classique du timbre, selon laquelle les mlanges
instrumentaux sont conditionns par les catgories usuelles de la pense musicale avant le XXe
sicle : Masses, nuages et autres effets de composition de texture ne sont en aucun cas une
invention rcente. Debussy, Strauss, Wagner, Berlioz et leur contemporains ont intensment
dvelopp et exploit le potentiel des textures orchestrales. Mais dans la plupart des uvres
de Varse, et dans certaines compositions de Schoenberg, Berg, Webern et Stravinsky la tex-
ture est au centre de lcriture, et ne rsulte pas dun procd contrapuntique, harmonique,
mlodique ou rythmique. Tant que la pense musicale ne sempare pas du timbre comme un
objet en soi, lorchestration reste une science secondaire. Mais chez Berlioz [Ber55], dj on
trouve les prmices de lmancipation future : Lemploi de ces divers lments sonores et leur
37
38 CHAPITRE 3. ORCHESTRATION : UN SAVOIR EMPIRIQUE EN MUTATION
application soit colorer la mlodie, lharmonie et le rythme, soit produire des impressions
sui generis (motives ou non par une intention expressive), indpendantes de tout concours
des trois autres puissances musicales, constitue lart de linstrumentation.
A propos des cordes : Comme le chur vocal, la famille des cordes offre une belle homognit
de timbres et peut excuter une grande varit de traits, de la simple ligne monophonique la plus
riche des polyphonies. Pratiquement tout ce qui convient aux voix sonnera bien aux cordes. Lcriture
pour cordes favorise les croisements, contrairement lcriture chorale.
A propos des bois : Les unissons produisent un effet de chur. Un changement de registre
provoque un changement radical de timbre. On peut presque aller jusqu considrer un instrument
par registre.
A propos des cuivres : Les cuivres sont plus homognes que les bois mais moins flexibles que les
cordes. On peut leur attribuer, aussi efficacement, des rles mlodiques, rythmiques, contrapuntiques
ou harmoniques. Ils reproduisent, mieux que les bois, le chant choral.
Lorchestration, quant elle, renvoie aux multiples manires de mlanger les timbres indi-
viduels. Nous ne nous sommes point impos la tche de donner une suite de mthodes des
divers instruments ; mais bien dtudier de quelle faon ils peuvent concourir leffet musical
dans leur association. [Ber55] Cest donc une science dun niveau de complexit suprieur
linstrumentation, et qui, dune certaine faon, la contient : Pour nous, comme domaine
dtude, lorchestration succde linstrumentation, cette tape prliminaire o ltudiant
explore le fonctionnement des instruments et ralise ce qui est raisonnablement jouable par
un excutant professionnel. La conception trop rpandue que lorchestration nest que lat-
tribution de timbres aux diverses lignes nous semble trs inadquate. (Alan Belkin, citant
Koechlin dans [Bel01]).
1
On trouve parfois dans les traits que pour une situation donne certains instruments conviennent mieux
que dautres, encore que ce jugement soit souvent trs subjectif : On apprend ce qui convient aux divers
instruments, ce qui pour eux est praticable ou non, ais ou difficile, sourd ou sonore ; on peut dire aussi, que tel
ou tel instrument est plus propre que tel autre rendre certains effets, exprimer certains sentiments. [Ber55]
3.2. LES TRAITS CLBRES 39
A propos des violoncelles : Quand les violoncelles chantent, il est quelquefois excellent de
les doubler lunisson par les altos. Le son des violoncelles acquiert alors beaucoup de rondeur et de
puret, sans cesser dtre prdominant.
A propos des harpes : Isolment ou par groupes de deux, trois ou quatre, il est singulier que
ce soit le timbre des cors, des trombones, et en gnral des instruments de cuivre, qui se marie le mieux
avec le leur. [. . .] Mais rien ne ressemble la sonorit de ces notes mystrieuses unies des accords de
fltes et de clarinettes jouant dans le mdium.
Sur lutilisation du cor anglais : Le mlange des sons graves du cor anglais avec les notes
basses des clarinettes et des cors pendant un trmolo du contrebasses donne une sonorit spciale
autant que nouvelle, propre colorer de ses reflets menaants les ides musicales o dominent la
crainte, lanxit.
On trouve galement dans les traits des principes dorchestration plus gnraux, qui nont
pas valeur de rgles auquelles se soumettre imprativement, mais que le jeune orchestrateur
est invit suivre. Ainsi chez Koechlin [Koe43] :
2
Les compositeurs les plus frquemment rencontrs dans le trait de Berlioz sont Gluck, Beethoven, Weber,
et Berlioz lui-mme.
40 CHAPITRE 3. ORCHESTRATION : UN SAVOIR EMPIRIQUE EN MUTATION
Au sujet des dynamiques : Evitez dindiquer des dynamiques diffrentes aux diffrents ins-
truments : cette faon de faire exige beaucoup dexprience puisque les excutants, dans lignorance des
indications de leurs collgues et sans consignes particulires du chef dorchestre, cherchent normalement
squilibrer entre eux.
Au sujet des plans sonores : Des plans sonores distincts exigent une individualisation
forte, grce des contrastes de registre, de timbre et/ou de rythme. Si les plans dialoguent, il faut
sassurer dune quivalence la fois de force et de volume. Les couleurs, le registre et le rythme gnrent
alors le contraste.
Sur la manire dcrire un tutti : La recherche dquilibre, entre les masses sonores, impose
des contraintes acoustiques qui limitent les possibilits dorganisation dun tutti : les cuivres et les
percussions gnrent, invitablement, le plus de puissance. Certaines combinaisons, par exemple, les
bois dans le mdium pendant que les cuivres jouent forts ne fonctionnent jamais.
Aussi riches dexemples, aussi exhaustifs que soient les traits, la question de leur prcision
et de leur porte mrite toutefois dtre pose. Quelle est leur utilit pour un compositeur dau-
jourdhui ? Quel est lapport de cette impressionnante connaissance pour la musique contem-
poraine ? On vous donne quelques recettes puises dans les uvres du rpertoire, recettes
trs disparates, sans cohrence, auxquelles se mle une certaine affectivit lie directement aux
modles proposs. (Pierre Boulez, Le timbre et lcriture, le timbre et le langage, in [Bar85]).
Et sans mme discuter lventuelle obsolescence du rpertoire dtude, le vocabulaire employ
ne reflte-t-il pas dj la vision esthtique dune poque ? Nous ne rsistons pas ici citer
encore une fois Berlioz [Ber55], dont le trait vaut certainement davantage aujourdhui pour
sa valeur littraire que musicale :
Le trombone est, mon sens, le vritable chef de cette race dinstruments vent
que jai qualifis dpiques. Il possde en effet au suprme degr la noblesse et la
grandeur ; il a tous les accents graves ou forts de la haute posie musicale, depuis
laccent religieux, imposant et calme, jusquaux clameurs forcenes de lorgie. Il
dpend du compositeur de le faire tour tour chanter un chur de prtres, mena-
cer, gmir sourdement, murmurer un glas funbre, entonner un hymne de gloire,
clater en horribles cris, ou sonner sa redoutable fanfare pour le rveil des morts
ou la mort des vivants.
des problmes complexes. Lide que nous dfendons dans cette thse est alors la suivante :
la puissance de calcul de lordinateur doit permettre dexplorer de manire efficace lespace
des alliages de timbre et dvaluer en un temps raisonnable les combinaisons instrumentales a
priori les plus pertinentes pour le compositeur. Un systme daide lorchestration agirait donc
avant tout comme un outil de stimulation de limaginaire , en proposant au compositeur
des solutions auxquelles son savoir et son exprience personnelle ne laurait pas ncessairement
men. Il ne sagit videmment en aucun cas de subsituer aux techniques usuelles dorchestra-
tion la formalisation dun ensemble de rgles (et dabord lesquelles ?), mais plutt dutiliser
lordinateur comme un explorateur qui, de manire interactive et guide, dcouvrirait
de nouveaux territoires dans lcriture du timbre orchestral. Une nouvelle manire dorchestrer
certes, mais qui ninvalide pas lancienne, et la pourvoie au contraire dune dimension nouvelle.
Chapitre 4
Aide lorchestration
43
44 CHAPITRE 4. AIDE LORCHESTRATION
Rose et Hetrick [RH05] ont propos un outil la fois pdagogique et cratif, permettant
dune part danalyser une orchestration existante, dautre part de crer des orchestrations
46 CHAPITRE 4. AIDE LORCHESTRATION
originales dont la sonorit sapparente un son cible donn en entre du systme. La connais-
sance des possibilits instrumentales est obtenue par analyse dchantillons instrumentaux, en
calculant des spectres harmoniques moyens sur la partie entretenue des sons. Le spectre du
son cible est calcul par une analyse similaire. Lalgorithme dorchestration de Rose et Hetrick
repose sur une dcomposition en valeurs singulires du spectre de la cible, celle-ci sexprimant
alors comme une somme pondre des spectres de la base de donnes.
Cette mthode prsente deux avantages significatifs. Elle garantit que la dcomposition
trouve est la plus proche du spectre de la cible au sens de la norme L2 . En outre, le cot de
calcul est drisoire. En revanche, les spectres sont calculs avec des FFT1 de 4096 points, et
la comparaison de spectre sur quelques miliers de points est, sur le plan perceptif, sujette
caution. En outre, cette approche ne permet pas de prendre en compte les contraintes lies
leffectif instrumental : il se peut en effet que loutil de Rose et Hetrick propose en combinaison
ncessitant, mettons, trois violoncelles, alors que lorchestre nen compte quun seul.
SPORCH (SPectral ORCHestration) est un systme dvelopp en Lisp par David Pseni-
cka [Pse03] dans lequel la recherche seffectue sur les instruments eux-mmes, non sur les sons.
SPORCH utilise un algorithme itratif de matching pursuit pour trouver une combinaison
dinstruments sapprochant au mieux dune cible sonore, donne comme prcdemment sous
forme dun son enregistr. Chaque instrument de la base est associ un ensemble de hau-
teurs et de dynamiques, auxquelles sajoute une collection de partiels les plus importants dun
point de vue perceptif. Lalgorithme de SPORCH extrait les partiels principaux de la cible
et cherche dans la base les sons les plus pertinents. Le critre de slection est une distance
euclidienne entre les partiels suffisamment proches en frquence. Un partiel prsent dans un
son candidat mais absent dans la cible augmente donc la valeur de distance.
Lalgorithme de SPORCH est itratif. Aprs avoir trouv le candidat qui minimise la dis-
tance au son reproduire, son spectre est soustrait celui de la cible et lalgorithme reprend
la recherche avec pour cible lensemble de partiels rsultant de la soustraction. Evidemment,
linstrument slectionn ltape prcdente est exclu du domaine de recherche. Cette m-
thode permet de trouver rapidement des solutions excutables par lorchestre (les contraintes
lies leffectif instrumental sont toujours vrifies), mais rien ne garantit loptimalit de la
solution obtenue. En outre, cette technique a tendance privilgier les configurations de faible
cardinalit.
Un troisime systme est d Thomas Hummel [Hum05]. Un algorithme itratif est ga-
lement utilis, mais la mesure de distance entre les sons candidats et la cible se base sur
lenveloppe spectrale plutt que sur les partiels. Par consquent, les hauteurs perues dans
la mixture propose peuvent tre trs diffrentes du contenu harmonique de la cible. Hum-
mel conseille dailleurs dutiliser son systme pour les sons dpourvus de hauteur, comme les
voyelles chuchotes.
Avant daller plus loin, quelques remarques simposent. Ces trois systmes prsentent de
nombreux points communs. Voyons lesquels, et discutons les implications des choix faits par
leurs auteurs :
1
Lalgorithme de FFT (Fast Fourrier Transform, en franais Transforme de Fourrier rapide) est une m-
thode particulirement efficace pour le calcul de la Transforme de Fourrier court terme (TFCT, ou STFT
Short Time Fourrier Transform en anglais), lorsque la taille de la transforme est une puissance de 2.
4.3. OUTILS ACTUELS DAIDE LORCHESTRATION 47
Il est chaque fois question dapprocher une cible sonore , et celle-ci est toujours don-
ne au systme comme un son enregistr. Cest l se restreindre un cas trs particulier
de lorchestration, car la plupart du temps, le compositeur ne dispose pas au pralable
de ce son. Lorchestration, en gnral, a pour but de produire, non de re-produire, un
timbre. Savoir comment obtenir tel effet prcis ne suffit pas la cration. Cela suppose
que leffet en question soit dj conu. Or, le processus de cration est aussi celui de
la gense des ides. Un outil de cration doit permettre cette gense. (Claude Cadoz,
Timbre et causalit, in [Bar85]) La dmarche smantique chre Varse est donc exclue
de lapproche adopte par les auteurs.
Pour chacun de ces systmes, la connaissance instrumentale se rsume un ensemble
de sons instrumentaux. Sans mme parler de leur accessibilit, la gnricit de ces bases
de donnes mrite dtre questionne. Quelle est linformation apporte par un Si bmol
mdium de tombone tnor jou ordinario en dynamique mezzo-forte ? Est-elle indpen-
dante des conditions denregistrement de ce son ? Lacoustique du lieu denregistrement,
linstrumentiste, la qualit et le type de prise de son constituent, tout comme les indi-
cations mentionnes sur la partition, des paramtres majeurs du timbre. Ne court-on
pas alors un risque de surapprentissage ? Quelle est la part variationnelle lie aux
conditions denregistrement dans ce que le systme apprend de lchantillon ? Les
orchestrations obtenues par ces outils produiront-elles les mmes effets de timbre dans
des conditions de jeu diffrentes ?
Tous les auteurs utilisent un critre spectral unique pour lvaluation des orchestrations
proposes. Certes, il fut longtemps considr que linformation spectrale tait prdo-
minante dans la caractrisation du timbre instrumental, mais on sait aujourdhui que
les phnomnes temporels et spectro-temporels ont une importance considrable. Par
ailleurs, bien que linformation spectrale soit dans ces sytmes reprsente par des don-
nes multidimensionnelles, lvaluation des propositions se rsume toujours un critre
unique, sans doute pertinent pour une certaine classe de problmes, mais certainement
pas pour tous.
Les trois systmes formulent lhypothse implicite de ladditivit des timbres instrumen-
taux. Or la simple considration de leffet de phase suffit la mettre en dfaut. Les
compositeurs connaissent bien ce phnomne. Cest lui qui explique en grande partie
pourquoi un ensemble de quatorze violons lunisson ne sonne pas quatorze fois plus
fort quun violon solo.2 Il est donc permis de douter des capacits prdictives dun modle
additif, aussi avantageux soit-il dun point de vue mathmatique.
Les effets de salle (notamment la rverbration) ne sont pris en compte dans aucun de
ces systmes. Or, la rverbration naturelle des lieux de concert a un impact norme sur
les phnomnes de fusion acoustique. Les compositeurs le savent bien, et comptent les
effets de salle parmi leurs allis pour la russite de leurs orchestrations.3
Enfin les trois auteurs, recourant des algorithmes itratifs ou de dcomposition,
2
Koechlin [Koe43] fait ce sujet la distinction entre le volume ( entendre au sens spatial) du son,
cest--dire son paisseur, son talement dans lespace, et la force , cest--dire sa puissance. Ainsi, peu
importe le niveau dynamique, un cor sonnera toujours plus ample, plus pais, quun violon. La rgle gnrale
concernant les doublures lunisson est quelle ajoutent plus de volume que de force.
3
Berlioz [Ber55] est mme all jusqu dire que sans rverbration il ny avait pas de musique : Voil
pourquoi la musique en plein air nexiste pas. Le plus terrible orchestre plac au milieu dun vaste jardin
ouvert de toutes parts, comme celui des Tuileries, ne produira aucun effet.
48 CHAPITRE 4. AIDE LORCHESTRATION
Nous rassemblons au chapitre 7 les ides matresses de notre outil daide lorchestraion,
et dcrivons plus profondment ce dernier la partie III de ce document. Nous verrons que les
limites des systmes existants ne peuvent tre simultanment dpasses. Aussi retomberons
nous parfois, en connaissance de cause, dans les cueils que nous venons de dnoncer. Cela
dit, la conception et le dveloppement de notre outil ont toujours t gouverns par un souci
de gnricit et dextensibilit future. Il faut donc voir dans notre travail une volution vers
un environnement de cration puissant et complet, rpondant aux exigences actuelles des
compositeurs.
4
Pour donner un ordre de grandeur, la base de donnes de lIRCAM Studio Online [BBHL99] compte en
moyenne un millier de sons par instrument. Quant la clbre Vienna Symphonic Library [VSL], elle dnombre
pas moins de 250000 chantillons.
Chapitre 5
Optimisation combinatoire
multicritre
Problmes N P
Introduction loptimisation multicritre
Panorama des algorithmes gntiques
Fonctions scalarisantes de Tchebycheff
Population size Adaptive Density Estimation
49
50 CHAPITRE 5. OPTIMISATION COMBINATOIRE MULTICRITRE
Dfinition 5.1. Soit E un espace de dcisions et {fn }n les fonctions dun problme multicri-
tre sur E, alors lespace :
Il arrive que E ne soit pas dfini explicitement (par des bornes dintervalles par exemple)
mais implicitement. Cest le cas notamment dune optimisation sous contraintes, dans lequel
les solutions de lquation 5.1 doivent galement satisfaire un ensemble de conditions. Nous
verrons au paragraphe 7.5 que bien souvent lespace de recherche dans un problme dor-
chestration est dfini la fois explicitement (par la donne des instruments de lorchestre) et
implicitement (par un ensemble de contraintes).
En gnral, la solution idale xideal du problme 5.1, qui minimise simultanment tous les
critres, nexiste pas :
critre B
Solutions domines
1
Solutions efficientes
Front de Pareto
critre A
Fig. 5.1 Solutions efficientes et solutions domines dun problme de minimisation deux
critres
Ds lors, le problme 5.1 ne se rsout pas en une solution idale unique, mais en un ensemble
de solutions optimales dites solutions efficientes ou encore solutions de Pareto, ou solutions
non domines, ou solutions de compromis. Une solution efficiente ne peut tre amliore sur
un des critres sans tre simultanment dgrade sur un autre critre. Autrement dit, on ne
peut amliorer conjointement lensemble des critres dune solution efficiente.
Dfinition 5.2. Dominance de Pareto. Soient x et y deux points dun espace de recherche
E sur lequel on a pos un problme de minimisation multicritre. On dira que x domine y au
sens de Pareto (on notera x y) si et seulement si :
Fig. 5.2 Relations de dominance dans un espace deux critres pour un problme de
minimisation
il y a fort parier que certaines solutions non domines soient plus pertinentes que dautres
pour le dcideur. Si ce dernier met une prfrence pour la solution 1 par exemple, nous pou-
vons alors en dduire que le critre A est prdominant pour ce problme. Le dcideur est en
effet prt accepter une erreur consquente sur le critre B pour satisfaire le critre A en pre-
mier. A loppos, si la solution 3 est prfre, cest le critre B qui prime. Enfin, la solution 2
indique que les deux critres sont mobiliss gale importance dans le choix dune solution.
Il sera donc illusoire de prtendre aborder le problme de lorchestration avec des mthodes
compltes, dautant plus que les fonctions optimiser ne sont ni linaires, ni additives, ni
monotones (voir annexe A).
Les mtaheuristiques se proposent de contourner ces limitations en se restreignant des
solutions satisfaisantes bien que trs souvent non-optimales. Le terme d heuristique d-
signe une mthode permettant de calculer en temps polynomial une solution ralisable dun
problme doptimisation N P. Lefficacit dune heuristique ne peut tre dmontre, mais seule-
ment vrifie par lexprience. En gnral, une heuristique sappuie sur la structure propre du
problme rsoudre et propose une mthode de recherche ad-hoc. A contrario, les mtaheu-
ristiques regroupent un ensemble de mthodes gnrales, dun haut niveau dabstraction,
pouvant sappliquer diffrents problmes.
Labondante littrature sur les problmes doptimisation combinatoire multicritre a cou-
tume de sparer les mtaheuristiques en mthodes dites de voisinage et en mthodes
population . Les premires ont la particularit de nutiliser, tout moment de lexcution,
quune seule configuration, itrativement modifie dans le but de converger vers le front de
Pareto. Lorsque lvolution nest plus possible, la recherche peut ventuellement repartir dune
nouvelle configuration pour converger vers une autre zone de la frontire efficiente. Les m-
thodes de voisinage les plus utilises aujourdhui sont la recherche tabou, le recuit simul et
la mthode GRASP (Greedy RAndomized Search Procedure).
A loppos, les mthodes population utilisent un ensemble de configurations dont les
coordonnes dans lespace des dcisions sont mises jour chaque itration de lalgorithme.
Lintgralit de la population converge alors vers le front de Pareto, sans quaucune rgion
de la frontire ne soit, en thorie, privilgie. Les algorithmes gntiques (AGs) constituent la
classe la plus ancienne et la plus utilise des mthodes doptimisation population. Ils sont
lorigine de mthodes plus rcentes comme les systmes immunitaires artificiels et les algo-
rithmes valuation de distribution. Une autre famille de mthodes, inspires des phnomnes
dorganisation complexe chez les animaux vivant en groupe, se base sur une collaboration entre
les individus qui permet la population de sauto-organiser et de sadapter au pro-
blme courant. Les plus clbres sont les colonies de fourmis et loptimisation par essaims
particulaires.
Plus rcmment, des auteurs ont propos des mthodes hybrides, couplant en gnral un
algorithme gntique une mthode recherche locale. La figure 5.3 propose une classification
des mthodes doptimisation combinatoire multicritre. Le lecteur dsirant davantage de d-
tails pourra consulter les tats de lart dresss par Ulungu & Teghem [UT94], Talbi [Tal99],
ou encore Ehrgott & Gandibleux [EG00].
min fk ,
k
certaines solutions efficientes peuvent tre trouves en rsolvant le problme uni-critre sui-
vant : X
min k fk , (5.5)
k
54
Mthodes
Mtaheuristiques
compltes
Programmation
Mthodes Programmation Mthode de Mthode Mthodes
linaire en
arborescentes dynamique voisinage population hybrides
nombres entiers
Frontire de Pareto
Solutions
supportes
Solution
non-supporte
La premire ide qui vient lesprit lorsquon a affaire un problme multi-critre est
videmment de se ramener un problme uni-critre, afin de bnficier des mthodes classiques
doptimisation. Lagrgation linaire propose en 5.5 est lapproche la plus intuitive. Une
alternative est la mthode -contrainte, qui consiste transformer N 1 des N objectifs en
contraintes et optimiser sur lobjectif restant. Une troisime approche, la programmation par
buts (goal programming), propose de minimiser la distance un vecteur objectif de rfrence
selon une norme Lp pondre. Talbi [Tal99] note que seule cette dernire permet de dcouvrir
des solutions non-supportes, condition toutefois que le dcideur soit capable de dfinir un
but atteindre et un ensemble de poids relatifs associs chacun des critres. En pratique, cela
ncessite une trs bonne connaissance du problme et des fonctions objectifs qui le modlisent,
ce qui est trs rarement le cas.
Certains auteurs ont tent daborder les problmes multicritres en traitant sparment
chaque objectif. La slection des critres peut tre mene de faon parallle (algorithme de
Schaffer), lexicographique (algorihme de Fourman) ou encore alatoire (algorithme de Kur-
sawe). Cependant, Talbi [Tal99] et Fonseca & Fleming [FF95] ont montr que ces algorithmes
ne permettaient pas de trouver des solutions non-supportes.
Les mthodes numres ci-dessus sont souvent dnommes approches non-Pareto, car la
dominance Pareto ny est jamais prise en compte ni exploite. Elles ne peuvent dcouvrir
que des solutions supportes et sont donc inutilisables en cas de non-convexit du front de Pa-
reto. A contrario, les approches Pareto, initialement introduites par Goldberg [Gol89], utilisent
56 CHAPITRE 5. OPTIMISATION COMBINATOIRE MULTICRITRE
directement la notion de dominance de Pareto dans lvaluation et la mise jour des configu-
rations. Elles permettent notamment de trouver des solutions non-supportes. Les mthodes
rcentes doptimisation combinatoire multicritre appartiennent toutes cette catgorie. Les
algorithmes gntiques en constituent la famille la plus rpandue, nous les dtaillons donc
la section suivante.
A c B A a Y h 1 A c B A a Y f 7
e c v z a Y f 7 e c v z a Y h 1
A c B A a Y h 1 e c v A a Y h 7
e c v z a Y f 7 A c B z a Y f 1
A c B A a Y h 1 A c B A a Y f 1
Mutation monopoint
Remarque 5.2. Les oprations de crossover (aussi bien monopoint quuniforme) conservent
les schmas gntiques (voir Holland [Hol75] et Whitley [Whi93]) : si les mmes gnes sont
prsents chez les deux chromosomes parents (en bleu sur la figure 5.5), ils sont alors transmis
aux deux chromosomes issus du crossover.
Population
initiale
Population
intermdiaire
Slection
Oprations
gntiques
Mise jour de la
population
Population
intermdiaire
Critre
d'arrt
Population
finale
Les individus franchissant avec succs ltape de slection vont alors engendrer, par ap-
plication des oprateurs gntiques, de nouvelles solutions. Lide maitresse des AGs est que
les rgions optimales de lespace de recherche sont caractrises par des schmas gntiques
60 CHAPITRE 5. OPTIMISATION COMBINATOIRE MULTICRITRE
La figure 5.6 illustre le droulement type dun algorithme gntique. La plupart du temps,
le critre darrt est dtermin par un nombre maximum de gnrations ou dvaluation de
fitness.
wheel selection, stochastic remainder ), en raison notamment de son insensibilit aux intervalles
de valeurs prises par les critres. En outre, les auteurs mettent en garde contre un risque de
comportement chaotique des AGs lorsque le tournoi binaire est combin avec une mthode de
partage (sharing), qui consite pnaliser la fitness dans les zones de forte densit.
Bien que les algorithmes sus-cits aient t, ou continuent dtre, implments dans de
nombreux systmes daide la dcision, les recherches rcentes en optimisation multicritre
ont conduit les critiquer sur un certain nombre de points. Deb et al. [DPAM00] identifient
par exemple trois dfauts majeurs de lalgorithme NSGA :
1. une complexit en temps souvent rdhibitoire pour des problmes grand nombre de
critres ;
2. une convergence vers la frontire Pareto relativement lente, due la disparition progres-
sive de bonnes solutions au fur et mesure des gnrations (absence dlitisme) ;
3. des paramtres difficiles calibrer et devant tre adapts chaque nouvelle instance
dun problme.
Jaszkiewicz [Jas01] remarque en outre que la notion de dominance assure la convergence de
la population vers lensemble de Pareto mais pas la dispersion sur lintgralit de la frontire
(cest effet de spciation , ou drive gntique ).
Pour remdier ces inconvnients, certains auteurs ont propos de renforcer llitisme dans
les AGs en conservant une mmoire des solutions optimales, servant de rfrence pour
lvaluation des individus. Les algorithmes SPEA, PAES, et NSGA-II sont conus selon ce
principe. Dautres auteurs [Tal99] [FF95] [BAKC99] font observer quen gnral les AGs et les
mthodes de recherche locale (cf. section 5.3 et figure 5.3) donnent des solutions diffrentes et
proposent des algorithmes hybrides combinant les deux mthodes (MOGLS, M-PAES, SPEA-
II).
les auteurs ont propos M-PAES [KC00] (Memetic Pareto-Archived Evolution Strategy), une
version hybride de lalgorithme PAES dans laquelle chaque progniture est amliore par une
mthode de recherche locale avant le tournoi contre son gniteur. Au cours de cette phase
doptimisation, lacceptation dun nouveau voisinage est soumis aux mmes rgles que celle
du tournoi final entre parent et enfant.
Deb et al. [DPAM00] ont propos une amlioration de NSGA (cf. supra) corrigeant les
dfauts principaux de lalgorithme initial. La complexit de NSGA-II est ramene O(KN 2 )
et la diversit est maintenue grce une fonction destimation de la densit dchantillonnage
du front de Pareto. Par ailleurs, NSGA-II propose une gestion trs pertinente des ventuelles
contraintes, en introduisant une mesure de consistance (fonction de cot) de celles-ci dans la
dominance Pareto.
En 1996, Ishibuchi & Murata [IM96] ont introduit une premire version de lalgorithme
MOGLS (Mutli Objective Genetic Local Search). A chaque gnration les nouvelles solutions
sont amliores grce une mthode de recherche locale, optimisant une somme pondre
des critres, dont le jeu de poids est tir alatoirement. Jaszkiewicz [Jas01] fait observer que
lalgorithme MOGLS, bien que bas sur une agrgation linaire des critres le rapprochant
des mthodes de goal programming, neffectue pas une transformation vers luni-objectif pour
autant, du fait de sa structure dAG permettant une recherche simultane de solutions mul-
tiples dans des directions multiples. MOGLS tire parti des rsultats de Chen et Liu [CL94] et
Steuer [Ste86], prouvant que lintgralit de lensemble Pareto peut tre obtenu en rsolvant
un problme de goal programming pour lensemble de jeux de poids possibles.
Une seconde version de lalgorithme MOGLS a t propose par Jaszkiewicz [Jas01] [Jas02].
Le mcanisme de roulette wheel selection est remplac par un tirage alatoire parmi les
meilleurs candidats, et la somme pondre par une distance de Tchebycheff pondre (cf.
dfinition 8.5.1). Jaszkiewicz [Jas02] fait observer que les fonctions de Tchebycheff sont plus
adaptes que les fonctions linaires pour des problmes o la forme du front de Pareto est com-
plexe ; elles permettent notamment de trouver des solutions non-supportes (voir section 5.4).
Lauteur fournit en outre une mthode efficace pour calculer le nombre de solutions initiales.
Ishibushi et al. [IY02] ont suggr une autre amlioration de lalgorithme MOGLS en ex-
ploitant lide que la performance de lAG peut tre accrue en utilisant dans la recherche
locale une direction doptimisation adapte chaque solution et indpendante du jeu de poids
employs dans le mcanisme de slection des parents. La mthode permet ainsi de sparer
totalement volution gntique et exploration du voisinage des solutions, et peut donc sadap-
ter trs facilement tout type de recherche locale. Lalgorithme SPEA-II [ZLT02] exploite
galement une hybridation de ce type.
Par ailleurs, Ishibuchi et al. [IY02] font remarquer que dans de nombreux algorithmes
hybrides la majeure partie du temps de calcul est dvoue la recherche locale, et fournissent
quelques pistes pour quilibrer la balance entre les deux metaheuristiques.
Grosan et al. font remarquer que les alphabets binaires ne sont pas adapts tous les
problmes, et quil existe de nombreux cas o il est plus judicieux dutiliser une autre encodage
des solutions. Malheureusement, le choix dun alphabet ncessite une trs bonne connaissance
de lalgorithme employ et du problme rsoudre, laquelle ne peut sacqurir qua posteriori,
et par un dcideur matrisant les concepts scientifiques des algorithmes gntiques.
Les auteurs ont donc propos de laisser lalgorithme de choix de lalphabet, en codant la
taille de ce dernier directement dans le gnome. Les oprateurs gntiques permettent alors
soit de modifier le gnome au sein du mme alphabet (mutation), soit de traduire linformation
porte par les gnes dans un autre alphabet (transmutation). De faon vidente, le crossover
ne peut sappliquer, car les chromosomes apairs ne partagent pas ncessairement le mme
alphabet.
Ce principe dadaptabilit de lalphabet a t exploit dans les aglorithmes APAES (Adap-
tive Pareto-Archive Evolution Strategy) [OGAK05] et MAREA [Gro06]. Dans chacune de ces
deux mthodes, lorsquun individu ne peut plus tre amlior par mutation gntique, une
transmutation est applique pour changer dalphabet.
Une autre volution rcente dans les mtaheuristiques pour loptimisation multicritre
concerne le maintien de la diversit dans la population. La prservation de la diversit est
essentielle dans une mthode population, car elle empche que lensemble des individus soit
attir par un rgion unique de lespace. En recherche uni-critre, elle permet dviter le pige
des minima locaux ; en multicritre, elle garantit une rpartition uniforme des solutions le long
du front de Pareto.
Traditionnellement, le maintien de la diversit passe par une estimation de la densit locale
dans lespace des critres, afin soit de pnaliser les zones les plus denses lors de la slection pour
la reproduction, soit den retirer des individus lors de la mise jour de la population. Elle est
base sur la notion de voisinage dans lespace des critres, dfinie laide de paramtres
comme le rayon de voisinage ou la distance aux plus proches voisins. Hlas, les valeurs de
ces paramtres sont trs difficiles dfinir ou interprter, car elles dpendent fortement du
problme considr.
Lust & Teghem [LT06] ont donc propos lalgorithme MEMOTS (Memetic Multi-Objective
Tabu Search), dans lequel la densit est calcule laide dune hypergrille divisant lespace des
critres en hypervolumes. La densit locale y est alors dfinie comme le nombre de solutions
dans chaque hypervolume. Les auteurs fournissent galement une mthode simple pour dfinir
la taille de lhypergrille en fonction de la taille de la population.
Une autre approhe est propose par Elaoud et al. [ELT07] avec lalgorithme PFGA (Pa-
reto Fitness Genetic Algorithm). L encore, une hypergrille est utilise, mais celle-ci sadapte
automatiquement la taille de la population et aux chelles de valeurs prises par les critres.
La mesure de la densit locale par la mthode PADE (Population size Adaptive Density Esti-
mation) ne ncessite aucun paramtre dont la valeur doit tre dfinie par le dcideur et peut
donc en thorie sadapter tout type de problme. Cette mthode est dtaille la section
5.8
dautres se basent sur le dnombrement des configurations dominant et/ou domines par la
configuration value. SPEA [ZT98a] [ZT98b] [ZT99], SPEA-II [ZLT02], MEMOTS [LT06] et
PFGA [ELT07] fonctionnent sur ce principe. Toutes ces mthodes corrigent parfois la valeur de
fitness laide dune estimation de densit locale, afin de dfavoriser les zones les plus peuples
de lespace des critres au profit des moins denses. Une troisime approche, exploite dans les
diffrentes versions de lalgorithme MOGLS [IM96] [Jas01] [Jas02], procde une agrgation
des critres par normes de Tchebycheff pondres alatoirement (voir dfinition 8.2).
Lagrgation par normes de Tchebycheff pondres (dites aussi fonctions scalarisantes de
Tchebycheff ) sappuie sur une proprit nonce par Chen & Liu [CL94] et Steuer [Ste86],
selon laquelle un problme multicritre est quivalent un ensemble de problmes mono-
critre scalariss .
Proprit 5.1. Avec les notations introduites la dfinition 5.4, une solution x appartient
au front de Pareto si et seulement si :
, x = argminkyk ,
yC
La dmonstration de la proprit 5.1 utilise la notion de norme induite qui sera introduite
au paragraphe 8.5.1.
La figure 5.7 illustre cette dualit entre un problme multicritre et un ensemble de pro-
blmes mono-critre. Les trois configurations efficientes x1 , x2 et x3 sont respectivement so-
lutions de problmes de minimisation des normes N1 , N2 et N3 . Pour chacune dentre elles,
les jeux de poids associs dfinissent des directions doptimisation diffrentes. Notons que
les normes de Tchebycheff pondres, par les boules hyper-rectangulaires quelles induisent,
permettent de sadapter aux portions concaves du front : les solutions non-supportes (voir
section 5.4) peuvent tre dcouvertes par minimisation dune norme de Tchebycheff, ce que
lagrgation linaire des critres ne permet pas.
Dans les algorithmes MOGLS, un nouveau jeu de poids est tir alatoirement chaque it-
ration. La population est donc chaque fois value avec une fonction scalarisante diffrente. La
minimisation de la norme pondre courante assure la convergence vers une zone particulire
du front de Pareto, tandis que le renouvellement des poids favorise la diversit des solutions
le long de la frontire efficiente. Jaszkiewicz expose dans [Jas01] et [Jas02] une mthode effi-
cace pour gnrer uniformment des poids alatoires normaliss. Elle garantit une couverture
5.7. FONCTIONS SCALARISANTES DE TCHEBYCHEFF 65
x1
x2
N1
N2
x3
N3
Fig. 5.7 Trois solutions efficientes obtenues par optimisation unicritre dans un problme
de minimisation
f (, x) = max k xk , (5.9)
1kK
xk xmin
k
xk =
xmax
k x min
k
Les coordonnes rduites permettent de saffranchir des diffrentes chelles de valeurs prises
par chacun des critres. Pour chaque dimension k, xmink et xmax
k sont estimes par les plus
petite et plus grande valeurs de xk obtenues depuis le dbut de lexcution de lalgorithme.
66 CHAPITRE 5. OPTIMISATION COMBINATOIRE MULTICRITRE
w1 W1
W2
D=4
D=2
w2
Fig. 5.8 Estimation de la densit locale par la mthode PADE : Population size Adaptive
Density Estimation (daprs Elaoud & Teghem [ELT07]).
en un ensemble de cellules dont la largeur Wk sur chaque objectif k est donne par :
La figure 5.8 illustre le calcul de densit par la mthode PADE dans un cas bicritre.
Conclusion
Les mthodes multicritres permettent daborder des problmes doptimisation pour les-
quels limportance relative des objectifs ne peut tre connue a priori. Cependant, la complexit
N P de la plupart des problmes combinatoires multicritres les rend inabordables par les m-
thodes compltes, et le recours aux mtaheuristiques est la plupart du temps incontournable.
Les algorithmes gntiques en constituent la variante la plus courante, et leur efficacit dpend
avant tout des mthodes choisies pour valuer et diversifier les solutions.
68 CHAPITRE 5. OPTIMISATION COMBINATOIRE MULTICRITRE
Chapitre 6
Sans anticiper sur la seconde partie de ce document, il est ais de comprendre que la
recherche dorchestrations ne se ramne pas uniquement une tache doptimisation, mais
implique galement un ensemble de conditions que les solutions proposes se doivent de v-
rifier. Dans sa version actuelle, notre outil est une aide lcriture pour orchestre ; aussi les
orchestrations quil suggre doivent-elles se plier aux contraintes imposes par leffectif ins-
trumental : une orchestration ncessitant huit trombones nest pas ralisable par un orchestre
symphonique classique, qui nen comporte que trois ou quatre. En outre, comme nous le ver-
rons au chapitre 10, il doit tre possible pour le compositeur dexiger, par exemple, que les
orchestrations dcouvertes par notre systme ne mobilisent quune partie de lorchestre, quelle
laissent la disposition du compositeur au moins un instrument de chaque type ou de chaque
famille, quelles couvrent une certaine densit harmonique (nombre de notes de hauteurs
diffrentes joues simultanment), etc. La formalisation et la gestion de contraintes au sein de
notre systme est donc invitable. Nous proposons dans ce chapitre un aperu des principes
de la programmation par contraintes et des mthodes de rsolution sy rapportant. Nous d-
taillons en outre deux approches rcentes, la recherche adaptative et lheuristique CN -tabou,
dont sinspire notre algorithme CDCSolver prsent au chapitre 10.
69
70 CHAPITRE 6. PROGRAMMATION PAR CONTRAINTES
N
jeu de contraintes (ou rseau de contraintes) C1 , . . . , Cp , fonctions boolennes sur ( Di )iI ,
o I est un sous-ensemble de {1, . . . , N }. On parle de contrainte unaire (ou de filtre) si I
est un singleton, de contrainte binaire si I est un couple, de contrainte N-aire sinon. De
faon gnrale, une contrainte reprsente une information partielle sur les valeurs que peuvent
prendre les variables dun problme donn. La programmation par contraintes propose des
mthodes de rsolution bases sur la manipulation et la propagation de ces informations
partielles au cours du calcul. Lorsquon avance dans la rsolution, les incertitudes sur
les valeurs autorises pour les variables sont peu peu leves, et une configuration consistante
est alors synonyme dinformation totale.
En pratique, de nombreux domaines dapplication se prtent la programmation par
contraintes, en raison notamment du fort pouvoir expressif de ce paradigme. De la mise en
page des documents multimdia aux problmes de planification, dordonnancement, de gestion
de ressources ou demplois du temps, les contraintes ont t employes avec succs dans des
situations complexes, difficiles formaliser autrement que par un ensemble de conditions
logiques sur les variables.
Le lecteur dsirant approfondir ses connaissances sur la programmtion par contraintes
pourra consulter les ouvrages de Tsang [Tsa93] ou Mariott & Stuckey [MS98].
lenvironnement de CAO Boxes dAntony Beuriv [Beu00]. Boxes est bas sur une repr-
sentation hirarchique de type conteneurs/contenus assortis de paramtres temporels (dbut,
dure, fin). Le compositeur peut ainsi facilement organiser dans le temps des objets sonores
par la simple donne de contraintes dantriorit, de postrit, ou de synchronisation.
Antoine Allombert et Myriam Desainte-Catherine [AADC08] ont poursuivi et gnralis
ce travail avec le concept de partitions interactives, permettant aux compositeurs de crer
des pices musicales dans lesquelles des liberts sont laisses aux interprtes quant aux d-
clenchements de certains vnements musicaux. Les partitions interactives ont recours un
formalisme bas sur les relations temporelles de Allen2 grce auquel les compositeurs peuvent
dfinir un ensemble de contraintes temporelles sur les vnements.
Dans un tout autre registre, citons encore le programme MusicSpace dOlivier Dele-
rue [Del04], dans lequel les connaissances sur la spatialisation sonore sont modlises par un
ensemble de relations entre les positions des sources et de lauditeur. MusicSpace allie
une reprsentation graphique des scnes sonores un moteur de contraintes permettant den
respecter la cohrence spatiale.
6.4 Mtaheuristiques
Les mtaheuristiques diffrent des mthodes compltes en ce sens quelles nexplorent pas
larbre de recherche de faon systmatique (elles ne peuvent donc assurer de toujours dcouvrir
des solutions globalement consistantes avec le rseau de contraintes), mais procdent un
affinage itratif dune ou plusieurs solutions courantes, en gnral totalement instancies.
les mtaheuristiques couvrent une large classe de mthodes que nous dtailleront pas in-
tgralement ici. Nous nous contentons de prsenter celles en rapport direct avec la program-
mation par contraintes.
nissent lespace de recherche dune fonction de cot globale, drive (par exemple par somma-
tion) des fonctions associes chaque contrainte, et que lon cherche minimiser. La fonction
de cot peut donc tre vue comme un critre qui guide la configuration courante vers des
solutions consistantes avec lensemble des contraintes.
Le dplacement dans lespace de recherche se fait par exploration du voisinage de la
configuration courante. A chaque itration, on remplace la configuration courante par celle de
son voisinage qui minimise la fonction de cot. En pratique, le voisinage est souvent dfini
comme lensemble des configurations dont seule une variable diffre de la configuration cou-
rante. Toutefois, lexploration du voisinage peut rapidement devenir un processus fastidieux
dans le cas de problmes de grande taille, et on a alors gnralement recours une heuristique
de voisinage pour se limiter un nombre restreint de configurations.
Ce principe de rsolution suppose une gestion efficace des minima locaux qui peuvent trs
facilement engendrer des cycles dans le parcours de lespace de recherche : si y est la
meilleure solution dans le voisinage de x, et x la meilleure solution dans le voisinage de y,
alors la recherche va boucler sur le cycle x y x y . . . La mthode la plus utilise
en PPC pour viter ce phnomne est la recherche tabou.
La recherche tabou, propose par Glover [GL97], consiste stocker dans une mmoire
court terme appele liste tabou lensemble des configurations visites. Le choix de la
prochaine affectation se fait alors parmi les configurations nappartenant pas la liste tabou.
Le cot en mmoire pouvant devenir prohibitif, on emploie en gnral une liste de taille limite
N . La recherche ne pourra alors chapper un minimum local que si le nombre dtapes
pour obtenir une nouvelle amlioration est infrieur N . Nous prsentons en infra deux
mtaheuristiques pour les problmes de satisfaction de contraintes utilisant la recherche tabou,
la recherche adaptative et lheuristique CN -tabu.
Il convient en dernier lieu de mentionner lusage frquent dans les recherches rcentes de
techniques hybrides qui combinent plusieurs mtaheuristiques ou tirent parti de la com-
plmentarit entre mthodes compltes et incompltes. Lheuristique CN -tabou de Vasquez &
Dupont [VHD03] en est un exemple. Elle sera prsente au paragraphe 6.6.
lapparition de minima locaux artificiels4 : le cot associ une variable est simplement le
nombre de contraintes violes dans lequel elle intervient. Ce type de fonction est appel min-
conflict. Dans lexemple prcdent, les cots associs au variables A, B, C, D seraient alors
respectivement 1, 2, 1, 0 ; cest donc bien sur B quil faut agir en premier.
Si nous rajoutons maintenant la contrainte C3 : A + B + C + D 3 au problme prcdent,
alors les deux configurations x = (1, 0, 1, 2) et y = (2, 1, 2, 0) vrifient toutes deux C1 et C2 ,
mais pas C3 . Quelles sont les variables responsables ? A priori les quatre, car la contrainte C3
les implique toutes. Comment alors choisir la variable modifier ? Il est clair quune fonction
min-conflict est ici inefficace. Etant donn le type de contrainte, il ne serait pas idiot dagir sur
les plus grandes valeurs, soit C pour x et A ou B pour y. Il apparat que dans ce cas, le choix de
la variable changer dpend de la configuration, donc ncessite un calcul qui peut vite devenir
trs coteux sur des problmes de grande taille avec beaucoup de contraintes. En rsum, la
recherche adaptative nest envisageable que pour les contraintes darit faible (impliquant
un petit nombre de variables) par rapport la taille du problme. Ce nest toutefois gure
prjudiciable, car dans la plupart des CSPs, les contraintes sont unaires ou binaires, et quand
ce nest pas le cas, on peut souvent les dcomposer en un ensemble de contraintes binaires.
Lalgorithme de recherche adaptative [CD01] [CDT02] utilise une mmoire court terme
de type tabou (voir paragraphe 6.4.1. A chaque itration, le voisinage explorer est obtenu
en remplaant, dans la configuration courante, la variable Vmax non marque tabou et de
cot maximal, par toutes les valeurs de son domaine. La meilleure configuration remplace alors
la configuration courante si elle en amliore le cot global. Sinon, Vmax est marque tabou
pour un nombre fix ditrations.
Outre ses performances obtenues sur un grand nombre de problmes musicaux, la recherche
adaptative a prouv son efficacit sur des CSPs classiques (problme des n-reines, carrs ma-
giques. . .) en affichant des temps de calcul significativement infrieurs ceux obtenus par
des solveurs implmentant dautres mtaheuristiques. En outre, elle a permis de rsoudre des
instances jusqu 50 fois plus grandes que les limites actuelles des mthodes compltes.
configurations ainsi produites, les ventuelles violations sont alors rsolues en dsinstan-
ciant toutes les variables en conflit avec la nouvelle affectation. Les contraintes tant binaires,
un simple filtrage par arc-consistance suffit pour propager linformation apporte par nou-
velle affectation. Dans le voisinage localement consistant ainsi obtenu, la configuration
comptant le plus grand nombre de variables instancies devient alors la configuration cou-
rante, et la variable modifie est marque tabou . Le statut tabou est rvoqu aprs
un nombre ditrations gal au nombre de fois o la variable a t modifie depuis le dbut
de lexcution. La liste tabou est ici gre dynamiquement : plus une variable a t modifie
dans le pass, et plus il sera difficile de la changer dans le futur.
Lheuristique CN -tabou a t employe avec succs pour rsoudre des problmes rels
dassignation de frquence et de positionnement dantennes, trs grand nombre de variables
et de contraintes.
capacit soient de nouveau satisfaites (voir Ishibuchi & Kaige [IK03]). Dans le cas gnral,
le choix dune mthode de rparation ncessite une trs bonne connaissance du problme, et
dbouche sur une procdure parfois coteuse en temps de calcul : la plus grande partie de
lexcution est consacre au maintien de la consistance plutt qu lvolution de la popula-
tion. Dans le cas du sac dos, les contraintes sont en faible nombre, les algorithmes gloutons
de rparation sont de complexit acceptable, en gnral en O(N log(N )). Mais la rparation
nest pas toujours prconiser pour des problmes fortement contraints et dont la structure
ne permet pas dimaginer de mthodes de faible complexit.
Oprateurs ad-hoc Une troisime solution, frquente dans la rsolution de CSPs au moyen
dAGs, consiste imaginer des oprateurs gntiques qui garantissent (ou dfaut maximisent)
la consistance des configurations quils engendrent (voir par exemple Dorne & Hao [DJ98]).
Cest dans cette direction que sest oriente notre premire version dun algorithme gntique
pour laide lorchestration [CTA+ 07], dans lequel loprateur de mutation agissait tantt
comme dplacement horizontal (la hauteur de note est conserve), tantt comme dplacement
vertical (linstrument est conserv). Bien que donnant de bons rsultats sur des problmes fai-
blement contraints, ces oprateurs se sont vite rvls inefficaces face un rseau de contraintes
plus dense.
Eiben [Eib01] fait observer que si la gestion directe des contraintes peut savrer extr-
mement efficace si elle est bien implmente, elle est en revanche fortement dpendante du
problme. Elle est donc recommander pour des applications trs cibles, dans lesquelles la
structure des problmes rencontrs ne change pas ou peu.
6
Le plus souvent, elle est dfinie comme le nombre de contraintes violes, ou le nombre de variables impli-
ques dans lensemble des violations.
80 CHAPITRE 6. PROGRAMMATION PAR CONTRAINTES
Conclusion
La programmation par contraintes permet de dfinir un problme par un ensemble de
conditions que doivent satisfaire ses variables. Selon la complexit des situations, les mtaheu-
ristiques peuvent savrer nettement plus efficaces que les mthodes compltes. La recherche
locale notamment la recherche adaptative a prouv son efficacit dans bien des cas et
permet souvent de rsoudre en un temps acceptable des instances de trs grande taille. En
revanche, la gestion des contraintes dans un problme doptimisation pose problme bien des
gards, en raison notamment de lhtrognit des formalisations. En outre, la rsolution de
problmes doptimisation par algorithmes gntiques se prte mal aux problmes contraints,
car les oprateurs gntiques engendrent trs facilement des configurations inconsistantes. Une
solution lgante consiste alors introduire la consistance dans la relation de dominance entre
les configurations.
Rsum de la premire partie
81
82
Deuxime partie
Algorithme de recherche
dorchestrations
83
Chapitre 7
Formulation du problme
Nous abordons dans cette thse le problme de lorchestration assite par ordinateur dun
point de vue algorithmique. Nous nous ramenons un problme combinatoire dans lequel il
sagit de trouver une combinaison de sons instrumentaux qui, jous simultanment, produisent
le timbre dsir par le compositeur. Des questions prliminaires surgissent aussitt : Comment
caractriser ce timbre cibl ? Comment reprsenter la connaissance instrumentale dans un
outil informatique ? Comment valuer la qualit dun mlange (i.e. sa distance la cible) ?
Sur quels critres se baser ? Ce chapitre aborde ces questions. Nous y exposons nos propres
conceptions et les choix mthodologiques qui en dcoulent.
85
86 CHAPITRE 7. FORMULATION DU PROBLME
un timbre, travers un processus interactif dessais/erreurs. Bien sr, cette dmarche est tout
fait lgitime dun point de vue esthtique, mais elle na rien de scientifique.
Il nous faut donc dfinir une cible. Dans notre cas, elle serait un ensemble de caractris-
tiques dcrivant les particularits du timbre souhait. Or, caractriser le timbre ncessite une
collection de termes tablis et univoques chacun dentre eux se rfrant une caractris-
tique prcise du son partage par les compositeurs, les chercheurs et les instrumentistes.
Hlas, la construction dun tel vocabulaire est illusoire, car la manire dont la perception
auditive est verbalise implique toujours une grande part de subjectivit. Certains champs
lexicaux conviennent certes davantage que dautres. Erickson [Eri75] fait ainsi observer que
des termes du vocabulaire visuel ou tactile sont souvent appropris pour dcrire les sons ou
les combinaisons de sons : tranchant, rugueux, sourd, doux, mordant, clair, clatant, cassant,
pais, fin, sec, vaporeux, ar, minutieux, flasque, fluide, translucide, flamboyant, granuleux,
cru, brumeux, lourd, glacial, brch, limpide, luxuriant, lger, ondul, pour en citer quelques
uns. Mais quest-ce, en dfinitive, quun son fluide ? Quest-ce quun son glacial ? Interro-
geons des compositeurs, ils donneront (sils le peuvent) des exemples diffrents, en rapport
avec leur exprience musicale personnelle. Alors que tout le monde sentend sur ce quest un
accord majeur, ou un accelerando.
A la rigueur, ces termes peuvent tre utiliss dans la comparaison des timbres ; on dira par
exemple que tel son est plus clair que tel autre. On pourra alors tenter de relier le concept
de clart un paramtre acoustique mesur ou calcul sur le signal. Cette dmarche est celle
des psychoacousticiens qui cherchent comprendre les mcanismes de diffrentiation et de
catgorisation dans la perception auditive (cf. 2.5). Elle nest daucun secours lorsquil sagit
de dfinir positivement les qualits perceptives dun son.
On comprend alors pourquoi nos prdcesseurs ont toujours contourn le problme de
la caractrisation du timbre souhait par le compositeur en restreignant la cible un son
enregistr. Aprs tout, la meilleure faon de dcrire un son est encore de le donner entendre1 .
Orchestration imitative
Fichier son
Orchestration gnrative
Outil
d'orchestration
Interface de
synthse
Son de synthse
Compositeur
Donnes symboliques
Signal audio
pour communiquer avec lordinateur. Lorsque le timbre vis nest pas un son enregistr, le
compositeur dispose dune interface de synthse sonore pour le construire itrativement,
travers un processus dessais/erreurs. Bien sr, il y a fort parier que le son ainsi cr soit
trs pauvre dun point de vue perceptif, mais son rle est uniquement de capturer len-
semble des caractristiques sonores souhaites par le compositeur. Il nest quun modle, un
portrait-robot dont lorchestration finale propose par le systme possdera les traits tout
en y ajoutant la richesse du timbre instrumental. Comme lillustre la figure 7.1, des donnes
symboliques peuvent aussi tre passes au systme dans le cas dune orchestration gnrative.
Nous donnerons davantage de dtails ce sujet au chapitre 12.
Cette piste t explore de manire prospective en parallle de nos travaux,
en collaboration avec Jean Bresson (Chercheur lIRCAM, charg du dveloppement
dOpenMusic [Ago98]). Nous verrons au chapitre 14 un exemple dorchestration utilisant
un son de synthse comme intermdiaire entre un accord crit et un timbre. Nous exposerons
galement au chapitre 12 un ensemble dinterfaces et de mthodes permettant de contrler le
timbre de ce son de synthse partir de donnes symboliques.
N.B. Si la cohrence des dynamiques est essentielle pour la capacit du systme valuer
la pertinence dun mlange, elle nempche pas pour autant certaines surprises dans les rsul-
tats obtenus. Les musiciens interprtent la dynamique en fonction de plusieurs paramtres :
hauteur, contexte musical, situation dans lorchestre, dynamique de lorchestre. . . Une mme
dynamique est joue differemment en solo, en ensemble ou en grand orchestre. Un forte est
jou diffremment sil est prcd dun pianissimo ou dun triple forte. Bref, les musiciens
passent leur temps quilibrer les dynamiques lorsquils jouent en ensemble, afin de rendre au
mieux les effets dorchestre voulus par le compositeur. On ne sera donc pas surpris, parfois,
dentendre des simulations dorchestration dont les dynamiques paraissent dsquilibres, ou
qui traduisent de faon peu raliste la partition. Ce sera au compositeur, par son exprience,
dajuster les dynamiques pour que la simulation dun timbre soit fidle la partition que
loutil dorchestration propose.
Mme avec une base cohrente en dynamiques telle que SOL, les problmes de gnricit et
de robustesse de la connaissance instrumentale voqus en 4.3 restent en suspens. Notre sys-
tme dorchestration ne connat des potentialits du basson que ce que le bassonniste enregistr
en a donn entendre dans un studio de lIRCAM. Les orchestrations proposes seront-elles
valables pour un autre bassoniste dans une salle de concert ?
Nous navons malheureusement pas dautre choix, dans un premier temps, que de sen
remettre cette hypothse. Cela dit, les travaux de Damien Tardieu doctorant-chercheur
dans lquipe Analyse-Synthse de lIRCAM, avec qui nous collaborons sur le sujet de lorches-
tration permettent de dpasser cette limitation en remplaant la base de donnes de sons
instrumentaux par un ensemble de modles dinstruments. Il sagit de modles probabilistes
agrgeant la connaissance issues de plusieurs bases de donnes sonores laide de mlanges
de gaussiennes (GMM4 ). En utilisant plusieurs chantillons dun mme son, par exemple un
La5 mezzo-forte de hautbois, on construit un modle gnrique du La5 mezzo-forte pour le
hautbois, plus robuste aux changements de conditions de jeu quun unique chantillon. Evi-
demment, un travail pralable sur la gestion des problmes de dynamique a t ncessaire.
Damien Tardieu a en outre mis en place une hirarchie de modles permettant de gnraliser
aisment la connaissance instrumentale et de construire des modles pour des sons absents
des bases de donnes. Par exemple, le modle de lalto vibr se dcompose facilement en deux
sous-modles : lalto non vibr et le vibrato de cordes. Si les bases de donnes utilises pour
lapprentissage ne contiennent aucun son dalto vibr, on peut quand mme en construire un
modle base de lalto non vibr et du vibrato de cordes appris sur le violon. Le lecteur
dsirant davantage de prcisions sur les modles dinstruments pourra consulter [TR07].
7.2 Paradigmes
La conduite de nos travaux et le dveloppement de notre outil daide lorchestration ont
t conditionns par un ensemble de paradigmes que semblaient imposer non seulement ltat
de maturit actuelle des savoirs connexes notre problme (voir 4.1), mais galement un en-
semble de scnarii dutilisation de notre outil, imagins lors du dialogue avec les compositeurs.
4
Gaussian Mixture Models.
90 CHAPITRE 7. FORMULATION DU PROBLME
3. Quelle distance utiliser, au sein de cet espace, pour la comparaison des timbres ? La
distance euclidienne est-elle la plus approprie ? Les dimensions de lespace de timbres
ont-elles toutes la mme importance dans le calcul de la distance ? Si non, comment
dterminer les poids relatifs chaque dimension ? Ces poids sont-ils invariants dune
comparaison lautre ?
En ce qui concerne le premier point, nous ferons lhypothse que nos descripteurs valent
aussi bien pour les sons instrumentaux individuels que les cibles ou les mixtures. Cette hy-
pothse sera confirme par notre exprience avec loutil dorchestration, lors du parcours, le
long dun descripteur, des solutions trouves (voir chapitre 13). Le choix des descripteurs va
dpendre conjointement des restrictions que nous nous imposons dans un premier temps de
notre recherche (voir section 8.1.1), des hypothses et paradigmes relatifs la conception de
notre outil, et en majeure partie des proprits additives de ces descripteurs. Concernant
ce dernier point, la question fondamentale est de savoir si, tant donne une combinaison de
sons de la base de donnes, on peut en estimer les descripteurs partir des descripteurs indi-
viduels de chaque son. Elle renvoie la deuxime des difficults voques ci-dessus. Quant
la troisime, se pose dabord le problme de dfinir une distance entre une mixture et la cible
pour chaque descripteur, ensuite seulement de savoir sil est possible de rapporter ce vecteur de
distance une valeur unique. Nous verrons en infra quune telle agrgation nest pas possible
a priori, sans connaissances supplmentaires sur les prfrences dcoute du compositeur.
Plutt que de travailler directement sur les chantillons reprsentant la connaissance ins-
trumentale, nous privilgions donc une vision descriptive du timbre instrumental. Outre les
gains considrables en temps de calcul qui en rsultent5 , cette approche nous permet la fois
de conserver un certain recul par rapport aux chantillons6 et de dfinir des distances
selon des directions indpendantes du timbre. Il devient alors possible de s approcher de la
cible en privilgiant une dimension ou une combinaison de dimensions : nous savons en effet
que toutes ne sont pas quivalentes dans la perception du timbre et que les critres perceptifs
utiliss dans les jugements de similarits perceptives dpendent la fois de lauditeur et des
sons compars (voir paragraphe 2.5). Nous exposerons au paragraphe 8.1.2 les dimensions du
timbre que nous choisirons de retenir pour notre propre problme.
Nous considrons que la description du son doit tre aussi simple que possible et accessible
au compositeur non-scientifique. En dautres termes, les dimensions du timbre doivent toujours
tre relies des paramtres perceptifs, afin de faciliter une manipulation intuitive de loutil
dorchestration.
5
Nous proposerons au chaptre 9 une mthode efficace pour la dcouverte en un temps raisonnable dorches-
trations pertinentes pour un problme donn. Au cours dune excution, cet algorithme value plusieurs milliers
de configurations intermdiaires. Or aujourdhui le temps dextraction des descripteurs est du mme ordre que
la dure du signal. Sans compter le temps ncessaire laddition des signaux pour gnrer les mixtures, une
simple excution de lalgorithme dorchestration ncessiterait donc plusieurs heures.
6
Une mme valeur de descripteur pouvant tre partage par plusieurs sons diffrents, le description se situe
toujours un niveau dabstraction plus lev que le signal. Il suffit pour sen convaincre de considrer le
descripteur de frquence fondamentale perue (pour les sons monophoniques).
92 CHAPITRE 7. FORMULATION DU PROBLME
7.2.5 Agnostisme
La connaissance de notre systme se limite la description de la base de sons instrumen-
taux. Nous choisissons de ne pas formaliser les ventuelles rgles dorchestration que lon
pourrait trouver dans les traits, et laissons le systme dcouvrir par lui-mme les bonnes
solutions. Notre outil dorchestration na de donc connaissances quen instrumentation. Cela
doit lui suffire puisquil peut, en thorie, imaginer nimporte quelle mixture instrumentale.
critre B
1 critre A prdominant
3
critre B prdominant
critre A
construire un systme expert guidant le compositeur vers des solutions pertinentes, et ce sans
avoir en passer par une caractrisation verbale du timbre.
Nous proposerons au chapitre 8 une validation de cette approche sur une description r-
duite du timbre instrumental, et prsenterons au chapitre 9 un algorithme efficace pour la
dcouverte de solutions efficientes.
7.3 Dfinitions
Nous rappelons ou introduisons dans cette section les dfinitions des concepts cls de notre
approche, articule autour des notions de cible sonore et de descripteur .
Dfinition 7.1. Un descripteur d est une valeur numrique scalaire ou vectorielle dcrivant
un aspect du timbre perceptivement identifiable.
Dfinition 7.2. Une mthode dextraction associe un descripteur d est une mthode de
calcul permettant dobtenir la valeur d(S) de ce descripteur partir du signal audio S.
Dfinition 7.3. Une cible T est un ensemble de descripteurs audio {d1 (T ), . . . , dN (T )} ca-
ractrisant un timbre recherch, obtenus par lanalyse dun son soit enregistr (orchestration
imitative), soit de synthse (orchestration gnrative).
Nous dfinissons alors les concepts de fonction dagrgation et fonction de comparaison per-
mettant de passer en deux tapes dune configuration un ensemble de distances la cible
selon chaque descripteur. La figure 7.3 illustre cette transformation.
94 CHAPITRE 7. FORMULATION DU PROBLME
Dfinition 7.5. Etant donn une configuration, une fonction dagrgation fd est une fonc-
tion n-aire associe un descripteur d permettant destimer la valeur de d pour la configuration
en fonction des valeurs individuelles prises par d pour chacune de ces composantes.
Dfinition 7.6. Etant donn une cible orchestrer T , une configuration, un descripteur d
et une valeur de d retourne par la fonction dagrgation fd associe d pour cette configura-
tion, la fonction de comparaison DdT associe d permet de calculer la distance entre la
configuration et la cible T selon ce descripteur d.
7.4 Formalismes
Nous dsignons respectivement par lensemble des sons possibles (quils soient enre-
gistrs, produits par un orchestre, ou le rsultat dune synthse), (si )1iNs la partie de
constituant la connaissance instrumentale de notre outil dorchestration et lopration in-
terne sur qui un ensemble de sons de associe leur mlange7 .
En gnral un tel sous-ensemble nexiste pas. Il sagit alors de trouver celui qui reprsente la
configuration la plus proche de T . Nous avons introduit pour cela le concept de descripteur.
Formellement, un descripteur est une fonction d de dans Rp , o p est la dimension du
descripteur.
T {d1 (T ), . . . , dN (T )} (7.2)
Remarque 7.1. Ce formalisme doit nous rappeler que le systme dorchestration ne peut
connatre de la cible orchestrer uniquement la description quil en a. Il ne cherchera
donc des configurations quen fonction de ce quil entend de la cible, travers le prisme de
la description. Il ne faut donc pas sattendre trouver dans les orchestrations proposes des
particularits de la cible que le systme ne peut pas reprer. A titre dexemple, la rugosit due
la modulation damplitude dans un son flatterzunge ne pourra pas tre considre lheure
actuelle.
7
En traitement du signal cette opration pourrait sapparenter une somme de signaux.
8
Nous rappelons que T est fourni au systme sous forme de son enregistr dans le cas dune orchestration
imitative et reprsent par un avatar de synthse dans le cas dune orchestration gnrative.
7.4. FORMALISMES 95
Les fonctions dagrgation, quant elles, peuvent tre formalises de la faon suivante :
Formulation 7.3. Soit d un descripteur et I = {i1 , . . . , iI } un sous-ensemble de {1, . . . , N }.
La fonction dagrgation fd associe d vrifie alors :
!
M
d si = fd (d (si1 ) , . . . , d (siI )) + (7.3)
iI
o est une erreur destimation dont on montrera la section 8.3 quelle est raisonnable.
De faon similaire, une fonction de comparaison est une application de dans R vrifiant
lensemble des proprits suivantes :
Proprit 7.1. Soit d un descripteur et T la cible dun problme dorchestration. Soit DTd la
fonction de comparaison associe d pour la cible T . On a alors :
1. x , DTd (x) 0
2. x , DTd (x) = 0 d(x) = d(T )
3. Pour tout couple (x, y) de , DTd (x) DTd (y) si et seulement si x est perceptivement
plus proche de T que x relativement au descripteur d.
Remarque 7.2. Les fonctions de comparaison utilises dans notre outil et explicites en an-
nexe A vrifient par construction les points (1) et (2) de la proprit 7.1. En ce qui concerne le
troisime point, nous sommes contraints den faire une hypothse. Bien quelle semble raison-
nable, elle nest pas systmatiquement vrifie, en grande partie cause de lerreur destimation
introduite dans la formulation 7.3. Nous montrerons au chapitre suivant que cette erreur est
rsonnable en pratiqu et ne remets pas en cause la proprit (3).
Remarque 7.3. Les travaux de Damien Tardieu [TR07] sur les modles dinstruments permet-
tront bientt de se passer la fois des fonctions dagrgation et des fonctions de comparaison.
Lvaluation dune combinaison x sera alors une simple mesure de probabilit conditionnelle.
La valeur de critre associe un descripteur d et une cible T sera dfinie comme la probabili
dobserver la valeur d(T ) sachant la combinaison x :
Nous avons commenc lvoquer la section 4.3, le problme ainsi pos est N P-
difficile : sa complexit en temps est exponentielle. Nous verrons quil ne peut tre abord par
des mthodes compltes9 et quil nous faudra avoir recours des heuristiques. Nous introdui-
rons au chapitre 9 un algorithme volutionnaire permettant dobtenir en un temps raisonnable
une bonne approximation du front de Pareto.
7.5 Contraintes
Nous avons identifi le problme de lorchestration une recherche multicritre de combi-
naisons de sons, dont la pertinence est juge sur un ensemble de descripteurs. Si le formalisme
introduit la section prcdente autorise lvaluation de nimporte quelle configuration, il ne
permet pas en revanche de modliser dventuelles contraintes sur lorchestration recherche,
ni donc de pnaliser les configurations qui ne satisferaient pas ces contraintes.
Il ne faut toutefois par perdre de vue que les combinaisons identifies par le systme
comme tant les plus pertinentes relativement un ensemble de critres doivent avant tout
tre excutables par lorchestre. Quel serait par exemple lintrt dune solution ncessitant
huit violoncelles pour un petit orchestre comme LEnsemble Intercontemporain nen comptant
au maximum que deux ? En dautres termes, leffectif instrumental de lorchestre impose des
contraintes de cardinalit sur les instruments que les solutions trouves par le systme se
doivent de respecter.
En outre, de mme que le compositeur peut, par son interaction avec loutil, orienter la
recherche dans une direction privilgie (cf. 7.2), de mme la spcification de contraintes peut
faciliter la dcouverte de solutions pertinentes en liminant systmatiquement certaines rgions
de lespace de recherche. Dans notre systme, les contraintes portent sur la caractrisation
symbolique des sons, cest--dire sur leurs attributs : hauteur, dynamique, instrument, mode
de jeu, sourdine. . . Les contraintes sont donc mesures directement dans lespace de dcisions.
Le compositeur peut par exemple exiger des configurations proposes par le systme quelles
mobilisent obligatoirement certains instruments, que leurs composantes aient une dynamique
commune ou encore quelles ne sollicitent quune partie de lorchestre.
Dfinition 7.7. Une contrainte est une relation logique que doivent satisfaire les attributs
dune configuration, cest--dire lensemble de ses caractristiques symboliques, en lien direct
avec lcriture musicale. Un ensemble de contraintes est appel rseau de contraintes. une
configuration est dite consistante si et seulement si elle satisfait toutes les contraintes du
rseau.
Dfinition 7.8. Une contrainte est caractrise par une fonction de cot, valeurs relles
positives, qui une configuration donne associe le niveau de violation de la contrainte. La
contrainte est satisfaite si et seulement si sa fonction de cot est nulle.
Les fonctions de cot sont en lien direct avec ce que le monde de la programmation par
contraintes (PPC) dsigne par contraintes molles (soft constraints). En rgle gnrale,
une contrainte na que deux tats possibles : soit elle est satisfaite, soit elle et viole. Les
contraintes molles offrent davantage de souplesse en permettant de quantifier le degr de
9
Les mthodes compltes, en procdant implicitement une exploration totale de lespace de recherche,
garantissent loptimalit des solutions trouves. En revanche, elles ncessitent souvent des temps de calcul
rdhibitoires pour les problmes de grande taille.
7.6. DUN ESPACE LAUTRE 97
Descripteurs
Fonctions Fonctions de Critres
de la
d'agrgation comparaison audio
configuration
Configuration
Fonctions de Critres
cot symboliques
Contraintes
Attributs symboliques (contraintes)
violation. Considrons par exemple un orchestre ne comprenant quun seul hautbois et quune
seule flte. Une proposition dorchestration A deux hautbois et une proposition B trois
fltes sont toutes deux inconsistantes du point de vue de leffectif orchestral. Pourtant, la
fonction de cot sera infrieure pour A que pour B.
des sons possibles muni de lopration interne , (si )1iNs la partie de constituant la
connaissance instrumentale et E le sous-ensemble de (, ), engendr par (si )i , alors E est
lespace de dcisions. Tout lment de E scrit comme la somme dun sous-ensemble de
(si )i : (N )
Ms
E= xi si | xi {0; 1} (7.5)
i=1
On serait donc tent de munir E une distance de type Hamming , dfinie comme le
nombre de coordonnes diffrentes entre deux vecteurs :
Ns
X
x y
= |xi yi | (7.6)
E
i=1
Il nest toutefois pas certain que ce choix soit trs pertinent, car la distance sera la mme
entre une clarinette en si bmol et une clarinette en mi bmol jouant la mme note la mme
dynamique dune part, et entre un violon col legno-tratto et un cor brassy dautre part.
En revanche, on peut trs bien utiliser une distance de Hamming sur les attributs, et
comparer deux configurations selon leurs instruments, leurs hauteurs, leurs familles dins-
truments. . . Ce principe sera utilis au chapitre 8 pour comparer des solutions du point de
vue du compositeur et au chapitre 13 pour explorer lensemble des solutions selon un critre
symbolique.
Le schma de la figure 7.3 indique comment passer dun espace lautre. Etant donn un
point de lespace de dcision (cest--dire une mixture de sons instrumentaux), les fonctions
dagrgation permettent destimer, partir des descripteurs individuels de chaque son, les
descripteurs de la mixture selon chaque dimension du timbre. Dans un second temps, les
fonctions de comparaison permettent de calculer les distances relatives la cible pour chaque
descripteur.
Ces fonctions ne sont pas monotones. Il suffit de considrer la valeur absolue des fonctions
de comparaisons des moments spectraux pour sen persuader (voir annexe A). Ainsi, rduire la
distance entre deux configurations dans lespace des critres nimplique pas que cette distance
diminue dans lespace des dcisions et vice-versa.
A la non-monotonie des ces fonctions transformant lespace des dcisions en espace des
critres sajoute leur non-injectivit. Les deux espaces extrmes de la figure 7.3 ont donc des
topologies trs diffrentes. Nous ne devons pas perdre du vue que lapproche multicritre se
justifie avant tout par laspect multidimensionnel de la perception du timbre et que lespace
des critres nest l que pour distinguer les solutions efficientes des solutions domines, et pour
estimer limportance relative des dimensions de lcoute, ainsi quexpos au paragraphe 7.2.
Le compositeur, de son ct, juge la qualit des rsultats obtenus dans lespace des dcisions.
Nous aurons donc nous poser la question fondamentale suivante : Les solutions optimales
du problme doptimisation sous contraintes, savoir les configurations la fois efficientes
et consistantes, correspondent-elles des orchestrations intressantes pour le compositeur ?
En dautres termes, le problme de lorchestration formul en 7.4 est-il bien pos ? Ce sera le
propos du chapitre 8.
Chapitre 8
Nous proposons dans ce chapitre une validation exprimentale des concepts et formalismes
introduits au chapitre prcdent. Nous commenons par introduire un ensemble rduit de
descripteurs du timbre puis montrons quils permettent de traiter une classe particulire de
problmes, sans remettre en cause le cadre thorique du chapitre 7.
Nous valuons dans un premier temps la qualit des fonctions dagrgation en comparant,
pour un ensemble consquent de mixtures de test, lestimation des descripteurs au calcul par
extraction directe. Dans un second temps, nous prouvons que le problme de lorchestration
assist par ordinateur, reformul en 7.4 comme un problme doptimisation multicritre sous
contraintes, est bien pos : nous calculons pour cela les fronts de Pareto pour un ensemble
de problmes de petite taille et montrons quils contiennent des configurations pertinentes
pour le compositeur.
Aspects temporels : Tous les sons manipuls par notre systme (aussi bien la cible que
les chantillons de la connaissance instrumentale) sont supposs entretenus et sans volution
temporelle. Les non-entretenus (piano, guitare, harpe, glockenspiel, pizzicati. . .), de mme que
101
102 CHAPITRE 8. VALIDATION SUR UNE DESCRIPTION RDUITE
les sons prsentant une variation temporelle (trmolos, vibratos, crescendos, decrescendos,
glissandi. . .) sont absents de la banque de sons instrumentaux.
Effets despace : En dernier lieu, nous ngligeons les qualits acoustiques du lieu dcoute
ainsi que les positions des instrumentistes et de lauditeur. Lhypothse sous-jacente est que le
timbre obtenu par un mlange instrumental ne dpend que des paramtres dcriture et non
des conditions dexcution de la musique.
En regard de lexprience musicale et des souhaits des compositeurs (voir 4.2) ces hypo-
thses pourront paratre extrmement rductrices voire irralistes. Elles ont toutefois permis,
aprs trois annes de recherche, de construire un outil dorchestration dont les potentiali-
ts dpassent dj ce que ltat de lart propose aujourdhui. En outre, la considration de
phnomnes tels que les effets despace na de sens quune fois leves les imprcisions de la
connaissance instrumentale. Il serait en effet absurde de calculer une rverbration avec une
grande prcision sans parfaitement matriser les caractristiques timbrales des sources sonores.
Il nous semble donc lgitime de considrer que de telles hypothses naffectent pas, aujourdhui,
la qualit des rsultats de faon significative.
a donc paru ncessaire. Elle consiste en un ensemble des principaux partiels rsolus par
le systme auditif. On sait en effet que la membrane basilaire de loreille interne se comporte
comme un ensemble de filtres passe-bande [Zwi61]. Un partiel est rsolu lorsquil est seul
lintrieur dune bande critique. Si une mme bande contient plusieurs partiels, seul le plus
lev en amplitude est considr comme rsolu.
Nous dsignerons dsormais par MRP (Main Resolved Partials) les principaux partiels
rsolus. Dans le cas dun son monophonique (de hauteur unique) ou polyphonique (peru
comme un accord), les MRP jouent un rle dterminant dans la perception de la (des) hau-
teur(s). Dans le cas dun son complexe (une cloche par exemple), ils dterminent la couleur
harmonique du son.
Centrode spectral
Le centrode spectral est souvent dfini comme le centre de gravit spectral du son. Les
psychoacousticiens le relient la brillance : les sons brillants ont un centrode lev, les sons
sourds un centrode bas. Son rle dans la perception et les jugements de similarit de timbre
na plus tre dmontr : le centrode spectral figure toujours parmi les dimensions principales
des espaces de timbres (voir section 2.5).
Le centrode peut tre calcul en considrant le spectre comme la densit dune variable
alatoire dont les valeurs sont les frquences du spectre et les probabilits dobservation sont
les amplitudes normalises [Pee04] :
Z
sc = f a(f ) df (8.1)
0
Etant donn que les frquences peuvent tre exprimes sur une chelle linaire ou logarith-
mique, et que le spectre peut tre calcul en amplitude, en energie ou en dcibels, il y a en tout
six faons de calculer le centrode spectral. Pour des raisons dadditivit des descripteurs, nous
prfrons le centrode linaire, calcul avec des frquences linaires et un spectre damplitude.
La formule 8.1 permet de calculer le centrode instantan, associ une fentre tempo-
relle unique. Le centrode global (caractrisant la brillance gnrale du son) est obtenu par
une moyenne du centrode instantan, pondre par lintensit perceptive sur chaque fentre
temporelle (voir A).
o sc est le centrode spectral du son. De mme que le centrode, il y a six calculs possibles pour
ltendue. Toujours pour des raisons dadditivit des descripteurs, nous travaillerons avec un
104 CHAPITRE 8. VALIDATION SUR UNE DESCRIPTION RDUITE
spread linaire, calcul avec des frquences linaires et un spectre damplitude. La formule 8.2
renvoie galement une valeur instantane. Le calcul de ltendue globale fait intervenir lin-
tensit perceptive instantanne (voir A).
(chapitre 10), valuation de lalgorithme dorchestration (chapitre 11). Pour lensemble de ces
valuations, une base commune dinstances de test a t gnre. Chaque cas de test est un
son rsultant dun mlange dchantillons de la connaissance instrumentale, qui peut servir
de cible pour un problme dorchestration. Nous dtaillons dans cette section le processus de
cration de cette base.
2
Dans lintgralit de ce document, Do4 dsigne le Do central. Cest la convention de notation adopte par
la base SOL.
106 CHAPITRE 8. VALIDATION SUR UNE DESCRIPTION RDUITE
Tab. 8.1 Tailles moyennes des espaces de recherche pour des problmes de petite taille (seules
sont comptabilises les configurations consistantes avec les contraintes de hauteur, deffectif
et de cardinalit).
1: P {c1 }
2: pour i = 2 . . . #C faire
3: P P {ci }
4: pour tout p P p 6= ci faire
5: si ci p alors
6: P P \ {p}
7: sinon si p ci alors
8: P P \ {ci }
9: aller la ligne 2
10: fin si
11: fin pour
12: fin pour
1: pour i = 1 . . . #C faire
2: P P {ci }
3: pour tout p P p 6= ci faire
4: si ci p alors
5: P P \ {p}
6: sinon si p ci alors
7: P P \ {ci }
8: aller la ligne 1
9: fin si
10: fin pour
11: fin pour
Les tableaux 8.3 recensent les tailles moyennes des fronts de Pareto pour chaque type de
mixture et chaque combinaison de critres. De faon vidente, la taille des fronts augmente
toujours avec le nombre de critres. En effet, une configuration efficiente dans un espace rduit
de critres lest encore dans un espace plus large, alors que linverse nest pas vrai. Cest un des
effets de la multidimensionnalit, qui veut que les distances diminuent quand la dimension des
espaces augmente. Nous aurons loccasion de rediscuter ces phnomnes et les consquences
quils engendrent pour notre problme. Ce qui nous semble remarquable ce stade, cest que la
taille relative des fronts de Pareto par rapport aux espaces de recherche chute considrablement
avec la taille du problme, comme en atteste le dernier tableau de 8.3. Seule une configuration
sur 10000 est efficiente dans un espace trois critres pour une cible polyphonique de 4 sons ;
le problme est donc dautant plus difficile que la cardinalit de lespace de recherche est
leve. Laugmentation du nombre de critres ne se traduit pas par une explosion du nombre
de solutions efficientes.
Dans la situation idale o les fonctions dagrgation prdiraient exactement les valeurs
issues de lanalyse, il est clair que les distances relatives entre la cible analyse et la configura-
tion compose des lments de la cible serait nulle pour chacun des critres. Corrlativement,
le front de Pareto serait alors rduit un unique point, lorigine du repre. Dune manire
plus gnrale, on peut dire quen optimisation multicritre la taille de fronts de Pareto diminue
dautant plus quil est possible dobtenir simultanment de bonnes valeurs sur chacun des
critres, comme cela semble tre le cas pour nos problmes de test. Il est donc normal que les
fronts soient de faible cardinalit.
La figure 8.1 rsume le processus de cration dune instance de test. A partir dun jeu
de hauteurs et dun orchestre ne contenant quun seul instrument de chaque type, on dduit
dans un premier temps un ensemble de contraintes de hauteur, deffectif et de cardinalit. Ces
contraintes vont servir dune part dlimiter lespace de recherche, dautre part gnrer une
mixture instrumentale consistante forme dchantillons de la connaissance instrumentale (les
botes RI dsignent les rponses impulsionnelles dune salle de petite taille, voir 8.2.1). Les
descripteurs extraits de la mixture constituent alors la cible dun problme dorchestration
pour lequel plusieurs fronts de Pareto sont extraits de lespace des critres. Une instance de
test est donc compos dune cible, dun jeu de contraintes, dun espace de recherche (et de
8.2. CRATION DUNE BASE DE TEST 109
Mixtures monophoniques
Mixtures polyphoniques
Proportion de lespace de recherche (seuls les fronts 3 critres sont reports ici)
RI
DB Extraction de
RI + Mixture Cible
(sons) descripteurs
RI
Fig. 8.1 Processus de cration dune instance de test (un cas de test est constitu de
lensemble des lments en bleu).
Remarque 8.1. Si les fonctions dagrgation sont de bons prdicteurs des descripteurs dune
configuration, peu sensibles la rverbration, on doit alors abserver les relations suivantes :
d
d, DM (KT ) ' 0 ,
2500 2000
2000
1500
Centrode calcul (Hz)
1000
1000
500
500
0 0
0 500 1000 1500 2000 2500 0 500 1000 1500 2000
Centrode mesur (Hz) Spread mesur (Hz)
Fig. 8.2 Estimation des moments spectraux des cibles polyphoniques 4 sons
La figure 8.2 permet de se faire une ide de la qualit de lestimation des moments spec-
traux pour les cibles polyphoniques 4 sons. Des nuages de points similaires sont obtenus
pour les autres types de mixtures. En ce qui concerne les MRP (rappelons quil sagit dun
descripteur multidimensionnel), la reprsentation de lestimation est plus problmatique, car
lerreur destimation dfinie en 8.3 est de mme dimension que le descripteur associ. Afin
de comparer des erreurs exclusivement scalaires, nous choisissons donc de mesurer, pour les
MRP, lerreur propage dans la fonction de comparaison :
M RP
DM (KT ) = 0M RP
Nous valuons donc, pour chaque instance de test, les descripteurs associs la solution
thorique, puis nous calculons les erreurs destimation des moments spectraux et des MRP.
Lerreur relative aux moments est dfinie par = (dbKT dM )/dM et peut donc tre ngative
en cas de sous-valuation. Lerreur relative au MRP scrit M RP = DM M RP (K ), elle est
T
donc toujours positive. Les moyennes et carts-type de ces erreurs sont reportes dans les
tableaux 8.4. La figure 8.3 permet en outre de se faire une ide de la distribution des fonctions
de comparaison pour les cibles polyphoniques 4 sons.
Les tests sur les sons isols (mixtures monophoniques une seule composante) permettent
de quantifier leffet de la rverbration sur les valeurs de descripteurs. Il semble que dans notre
cas leffet de salle (ou la mthode utilise pour le simuler) diminue en moyenne les valeurs des
moments spectraux (donc rende le son moins brillant et moins large), tout en conservant
bien lenveloppe spectrale dans la partie basse du spectre. Nous expliquons ces phnomne en
rappelant que la rverbration se comporte en gnral comme un filtre passe-bas.
Pour lensemble des instances de test, le biais destimation est denviron +11% pour le
centrode et +8,5% pour ltendue spectrale. Mme si lon peut considrer ces valeurs comme
relativement leves, leur constance doit nous rassurer : la qualit de lestimation ne se dgrade
pas avec la taille de la mixture. Il y a donc fort parier que lerreur destimation des moments
spectraux soit uniquement due la rverbration pour les mixtures considres dans ces tests.
112 CHAPITRE 8. VALIDATION SUR UNE DESCRIPTION RDUITE
Tab. 8.4 Erreurs moyennes destimation des descripteurs (cart-type de lerreur destima-
tion)
Mixtures monophoniques
Mixtures polyphoniques
0 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 0 0.2 0.4 0.6 0.8 1
Centrode Spread MRP
Fig. 8.3 Distribution des fonctions de comparaison pour les cibles polyphoniques 4 sons
8.4. POSITION DE LA SOLUTION THORIQUE DANS LESPACE DES CRITRES113
En ce qui concerne les MRP, les faibles valeurs de la distance en cosinus indiquent une forte
corrlation entre les vecteurs damplitude des partiels les plus importants, donc une grande
similitude entre les enveloppes spectrales mesures et calcules.
N.B. Rappelons encore une fois que si les deux premiers moments spectraux correspondent
bien des dimensions perceptives (la brillance pour le centrode et lpaisseur pour ltendue),
ces relations nont jamais t tablies que pour des sons monophoniques. Nous ne savons donc
a priori pas comment interprter une valeur de centrode ou dtendue pour des mixtures
dont les lments ont des hauteurs diffrentes. La seule conclusion que nous pouvons tirer
de notre test est que lestimation des moments spectraux par le calcul et leur extraction
par un processus danalyse conduisent approximativement aux mmes valeurs. Nous verrons
toutefois la section 8.5.4 que les moments spectraux contribuent grandement lidentification
de solutions perceptivement pertinentes.
KT M
Dans lhypothse o lerreur destimation des fonctions dagrgation serait nulle, le front de
Pareto associ une instance de test serait alors rduit la seule solution thorique (voir
section 8.2.3). Or, les tableaux 8.3 prouvent bien que cette erreur ne peut tre nglige, et que
les fronts contiennent bien plus quune seule configuration. Mais contiennent-ils au moins la
solution thorique ?
Dun point de vue perceptif, la mixture cible et la solution thorique sont par construction
similaires. La question que nous soulevons dans cette section est de savoir si la seconde occupe
une place privilgie dans lespace de critres, dont la topologie est induite par la premire
(cf. section 7.6). Nous montrons que la solution thorique est dautant mieux place dans
lespace des critres que le nombre de descripteurs est lev.
Tab. 8.5 Frquence laquelle la solution thorique appartient au front de Pareto (tableau
infrieur : rapport entre la frquence observe et probabilit dappartenance au front - un
rapport suprieur 1 indique une performance suprieure au hasard).
Frquences observes
ce critre est utilis. En outre, le tableau infrieur montre que lemploi simultan des trois
critres est prconiser pour les instances quatre sons.
Cela dit, mme si les performances par rapport au random semblent satisfaisantes en
combinant les trois critres, la frquence dappartenance au front de Pareto diminue de faon
drastique avec la taille du problme, et il y a fort parier qutant donn la marge der-
reur intrinsque aux fonctions dagrgation et le caractre exclusivement spectro-harmonique
des descripteurs utiliss, la solution thorique sorte systmatiquement du front pour les
problmes de grande taille3 . Que faut-il en conclure ? Peut-tre simplement que mesurer une
frquence dappartenance nest sans doute pas pertinent pour valuer notre approche. Nous
prfrons donc tenter de savoir si le front de Pareto, lorsquil ninclut pas la solution tho-
rique, contient au moins des solutions satisfaisantes pour lutilisateur. Ce sera lobjet de la
section 8.5. En attendant, nous cherchons estimer quelle distance du front se situe la
solution thorique.
Nous valuons dans cette section la distance au sens de Pareto entre la solution tho-
rique et le front. Nous calculons pour chaque instance de test et chaque combinaison de critres
le nombre de solutions de lespace de recherche qui dominent la solution cible. Plus ce nombre
est faible, et plus la solution cible est proche du front au sens de la dominance de Pareto.
Les rsultats de ce test sont reports dans le tableau 8.6. La statistique r50 correspond
au nombre mdian de configurations dominant la solution thorique pour chaque classe de
mixtures et chaque combinaison de critres. La mesure dom% est le pourcentage moyen de
solutions ne dominant pas la solution cible ; pour les solutions efficientes, on a : dom% = 100.
Elle se calcule de la faon suivante :
r
dom% = 100 1 (8.4)
#E
3
Sans doute lextension des critres des descripteurs de variation temporelle, de bruit, de rugosit, etc.,
permettrait-elle de ramener la solution thorique dans le front.
116 CHAPITRE 8. VALIDATION SUR UNE DESCRIPTION RDUITE
Tab. 8.6 Nombre mdian de configurations dominant la solution thorique (dom% : pour-
centage de lespace ne dominant pas la solution thorique)
Mixtures monophoniques
Mixtures polyphoniques
Remarque 8.2. Si toutes les coordonnes de x sont strictement positives, alors lunicit de
la norme induite par x est assure par lquation 8.5. Le calcul des poids associs la norme
induite est donn en annexe B.
Nous pouvons alors noncer les deux proprits essentielles de la norme induite :
Proprit 8.1. Soit x C un point de lespace des critres et k kx la norme induite par x
sur C. On a alors :
y C, y x k ykx kxkx (8.8)
i, kxkx = i xi
118 CHAPITRE 8. VALIDATION SUR UNE DESCRIPTION RDUITE
Par consquent :
k ykx kxkx max i yi kxkx
i
i, i yi kxkx
i, i yi i xi
i, yi xi
yx
La proprit 8.1 est fondamentale. Cest elle qui nous permettra, au chapitre 9, de trans-
former localement un problme multicritre en un problme uni-critre.
Proprit 8.2. Soit x C un point de lespace des critres et k kx la norme induite par x
sur C. k kx vrifie :
, k xk kxkx (8.9)
j {1; N }, lj j
On a alors :
lj xj j xj
lj xj kxkx
max li xi kxkx
i
kxkl kxkx
En dautres termes, k kx est, de toutes les normes de Tchebycheff pondres, celle qui
attribue x la plus petite valeur, donc celle qui permet dobtenir le meilleur rang pour x.
Cette proprit sera pour nous dun grand intrt dans linfrence des prfrences de lutili-
sateur voque au paragraphe 7.2.4. En effet, si le compositeur met une prfrence pour une
configuration K de lespace de recherche, alors la norme induite par K est celle qui reflte le
mieux cette prfrence. Le calcul des poids associs k kK peut donc nous renseigner sur
limportance relative des critres perceptifs qui a conduit au choix de K.
La figure 8.4 illustre ces trois heuristiques dans un cas bi-critres. La distance symbolique
tant calcule dans lespace de dcisions, Ks a donc t plac alatoirement dans lespace des
critres sur cette figure. Pour chaque classe de problmes et chaque combinaison de critres,
nous identifions dans les fronts de Pareto les solutions K , Ke et Ks laide des heuristiques
H , He et Hs , et valuons leur qualit laide des mesures suivantes :
M AD (mean audio distance) Distance euclidienne moyenne dans lespace des descrip-
teurs entre la solution thorique et la solution du front trouve par lheuristique. Les distances
associes chaque descripteur sont les fonctions de comparaison. Ainsi que mentionn la
partie 7.6, il est impossible dagrger ces distances sans connatre les prfrences de lutili-
sateur. Faute de mieux, nous exprimons donc la statistique M AD comme la norme L2 du
vecteur des distances associes chaque descripteur4 .
4
Pour calculer la statistique M AD nous utilisons systmatiquement toutes les fonctions dagrgation, et ce
quels que soient les critres utiliss. La distance ainsi obtenue est alors une distance euclidienne sur lespace
des descripteurs normaliss, dont la dimension est indpendante du nombre de critres choisis, ce qui permet
en outre des comparaisons entre des espaces de critres de dimensions diffrentes.
120 CHAPITRE 8. VALIDATION SUR UNE DESCRIPTION RDUITE
KT
minimisation
de distance
Ke symbolique
ne
Kl
ien
clid
Ks
T
K
eu
de
nce
n
io
ct
ista
re
di
d
en
de
nt
fro
ion
le
sat
ec
imi
av
min
n
io
ct
e
rs
te
in
Fig. 8.4 Trois heuristiques pour trouver des solutions pertinentes dans le front de Pareto
lorsque ce dernier ne contient pas la solution thorique KT . K (heuristique H ) est obtenue
par classement du front selon la norme de Tchebycheff induite par KT ; Ke (heuristique He )
par minimisation de la norme euclidienne, et Ks (heuristique Hs ) par minimisation de la
distance symbolique entre KT et le front (la position de Ks nest pas significative sur cette
figure).
8.5. QUALIT DES SOLUTIONS DU FRONT DE PARETO 121
P F M (perfect family match) Frquence laquelle la solution du front trouve par lheu-
ristique comporte exactement les mmes familles dinstruments que la solution thorique.
Nous reportons dans les tableaux 8.7 et 8.8 les mesures moyennes relatives aux mixtures
monophoniques et polyphoniques quatre sons.
Ces rsultats confirment tout dabord que les principaux partiels rsolus (MRP) constituent
le critre le plus pertinent dans lvaluation des configurations, puisque la distance moyenne
dans lespace des descripteurs et les mesures de proximit symbolique entre la solution du
front trouve par lheuristique et la solution thorique sont systmatiquement plus faibles
quand les partiels sont utiliss. Mais le rsultat principal est le suivant : aussi bien pour
les cibles monophoniques que polyphoniques, la qualit des solutions trouves par les
heuristiques H , He et Hs augmente avec le nombre de critres ; la distance audio moyenne
et les valeurs de similarit symbolique atteignent leurs optima lorsque les trois critres sont
considrs simultanment.
Toutefois, si cette tendance est globalement observe pour les trois heuristiques, elle est
moins marque pour la seconde dentre elles, qui choisit la solution du front la plus proche de
lorigine au sens de la norme euclidienne. Ses performances sont systmatiquement infrieures
aux deux autres heuristiques, et trois critres ne sont que de peu suprieures aux cas mono- ou
bi-critres. Loptimum de Salukwadze choisi par cette heuristique est la solution dun problme
doptimisation o tous les critres sont agrgs par une norme euclidienne. La qualit moindre
de cette solution prouve donc la supriorit dune vritable approche multicritre par rapport
ce que Talbi [Tal99] appelle la transformation vers luni-objectif.
Les mesures employes pour valuer la qualit des solutions trouves par les heuristiques
se divisent en deux catgories : lvaluation symbolique (P F M , M F M , P IM et M IM )
et lvaluation audio (M AD). Les solutions Ks obtiennent toujours de meilleurs rsultats
sur le critre symbolique et les solutions K sont toujours plus performantes sur le critre
audio, sans quaucune catgorie de solutions ne surpasse lautre sur les critres audio et sym-
boliques simultanment. Il est donc impossible a priori de dcider que lune des heuristiques
est meilleure que lautre. En revanche les solutions dcouvertes par lheuristique He sont sys-
tmatiquement battues sur les critres audio et symboliques. Il est donc permis de douter de
la pertinence de He , ce qui sera dailleurs confirm par la suite.
Nous avons donc prouv dune part que lutilisation simultane de trois critres spectro-
harmoniques pour lvaluation des configurations garantit des solutions efficientes plus proches
de la solution thorique, dautre part que ces trois critres doivent tre considrs conjointe-
ment dans une approche multicritre, et non agrgs en une seule valeur optimiser.
Il reste maintenant savoir si les solutions trouves par les heuristiques reprsentent vri-
tablement dun point de vue perceptif des propositions intressantes pour lutilisateur.
122 CHAPITRE 8. VALIDATION SUR UNE DESCRIPTION RDUITE
Heuristique H
M AD PFM MF M P IM M IM
k(1) 0.217 16.9 % 2.89 5.1 % 2.22
k(2) 0.250 15.5 % 2.87 6.3 % 2.21
k(3) 0.243 23.9 % 3.02 10.0 % 2.41
k(12) 0.123 18.6 % 2.90 5.9 % 2.24
k(13) 0.081 23.3 % 3.00 10.0 % 2.33
k(23) 0.075 24.3 % 3.05 8.6 % 2.41
k(123) 0.046 26.9 % 3.08 12.9 % 2.49
Heuristique He
M AD PFM MF M P IM M IM
k(1) 0.217 16.9 % 2.89 5.1 % 2.22
k(2) 0.250 15.5 % 2.87 6.3 % 2.21
k(3) 0.243 23.9 % 3.02 10.0 % 2.41
k(12) 0.183 9.8 % 2.67 4.7 % 1.97
k(13) 0.164 14.3 % 2.77 6.5 % 2.15
k(23) 0.167 14.5 % 2.80 6.3 % 2.16
k(123) 0.168 9.8 % 2.59 6.1 % 1.95
Heuristique Hs
M AD PFM MF M P IM M IM
k(1) 0.217 16.9 % 2.89 5.1 % 2.22
k(2) 0.250 15.5 % 2.87 6.3 % 2.21
k(3) 0.243 23.9 % 3.02 10.0 % 2.41
k(12) 0.143 36.7 % 3.26 12.9 % 2.60
k(13) 0.122 53.1 % 3.44 26.3 % 2.89
k(23) 0.126 53.5 % 3.46 25.1 % 2.91
k(123) 0.094 72.0 % 3.70 41.2 % 3.22
8.5. QUALIT DES SOLUTIONS DU FRONT DE PARETO 123
Heuristique H
M AD PFM MF M P IM M IM
k(1) 0.378 3.4 % 1.69 0.0 % 0.63
k(2) 0.421 2.8 % 1.63 0.2 % 0.61
k(3) 0.299 6.0 % 2.04 1.4 % 1.03
k(12) 0.310 3.4 % 1.76 0.4 % 0.71
k(13) 0.133 6.4 % 1.96 1.6 % 0.99
k(23) 0.133 7.2 % 2.00 0.4 % 0.99
k(123) 0.084 7.8 % 2.06 2.6 % 1.08
Heuristique He
M AD PFM MF M P IM M IM
k(1) 0.378 3.4 % 1.69 0.0 % 0.63
k(2) 0.421 2.8 % 1.63 0.2 % 0.61
k(3) 0.299 6.0 % 2.04 1.4 % 1.03
k(12) 0.305 5.0 % 1.87 0.2 % 0.95
k(13) 0.190 4.8 % 2.09 1.2 % 1.21
k(23) 0.216 6.0 % 2.09 1.4 % 1.28
k(123) 0.239 4.4 % 1.87 1.4 % 1.07
Heuristique Hs
M AD PFM MF M P IM M IM
k(1) 0.378 3.4 % 1.69 0.0 % 0.63
k(2) 0.421 2.8 % 1.63 0.2 % 0.61
k(3) 0.299 6.0 % 2.04 1.4 % 1.03
k(12) 0.279 10.6 % 2.31 1.0 % 1.07
k(13) 0.154 16.8 % 2.59 3.4 % 1.51
k(23) 0.175 19.0 % 2.62 4.0 % 1.54
k(123) 0.114 36.8 % 3.11 11.2 % 2.03
124 CHAPITRE 8. VALIDATION SUR UNE DESCRIPTION RDUITE
Tab. 8.9 Test dcoute 1 : Pour chaque combinaison de critres, frquence laquelle la
meilleure solution du front de parmi K , Ke et Ks est juge satisfaisante.
mono-4 poly-4
k(1) 10 % 10%
k(2) 10 % 0%
k(3) 20 % 10%
k(12) 25 % 20%
k(13) 40 % 40%
k(23) 75 % 45%
k(123) 80 % 60%
Tab. 8.10 Test dcoute 2 : Les trois critres tant considrs simultanment, frquence la
quelle chacune des solutions K , Ke et Ks est juge satisfaisante. Proche : frquence laquelle
au moins une des trois solutions est proche de la cible. Trs proche : frquence laquelle au
moins une des trois solutions est trs proche la cible.
mono-4 poly-4
H 55 % 30%
He 25 % 15%
Hs 65 % 45%
Proche 100 % 80%
Trs proche 75 % 35%
les plus proches de la cible sonore, puis valuer cette similarit sur une chelle trs simple :
peu similaire, proche ou trs proche. Le but de ce test est dvaluer la pertinence des solutions
du front en multicritre.
Ce test prouve la supriorit des heuristiques H et Hs sur He . L encore, nous retrouvons
les rsultats du paragraphe prcdent. La solution Ke , qui rsulte dune transformation du
problme vers luni-objectif, est la moins pertinente. Par ailleurs, notons quau moins lune
des solutions proposes par ces heuristiques est juge proche de la cible dans une grande
proportion de cas (100 % des cas en monophonique, 80 % en polyphonique).
Nous nirons pas plus loin dans lexploitation de ces rsultats. Bien que trs informels et
raliss sur un petit nombre de sujets, ces tests nous semblent suffisants pour justifier aussi
bien lapproche multicritre que la qualit des solutions trouves.
A : wsc > wM RP Le poids associ au centrode spectral est suprieur au poids associ
aux partiels.
B : wsc > 0.5 Le poids associ au centrode spectral est suprieur 0.5 (son rle est
dterminant dans le choix de la solution).
C : wss > wM RP Le poids associ ltendue spectrale est suprieur au poids associ
aux partiels.
126 CHAPITRE 8. VALIDATION SUR UNE DESCRIPTION RDUITE
D : wss > 0.5 Le poids associ ltendue spectrale suprieur 0.5 (son rle est dter-
minant dans le choix de la solution).
E : wM RP < 0.5 Le poids associ aux partiels est infrieur 0.5 (le rle des moments
spectraux est dterminant dans le choix de la solution).
A partir des probabilits observes, nous pouvons dduire les intervalles de confiance pour
les probabilits relles de ces vnements en inversant un test de Student. Ce test permet de
confronter une probabilit observe P (X) = p une probabilit thorique P (X) = pt . Sous
lhypothse nulle H0 : P (X) = pt , alors la statistique :
|p pt |
t= p n (8.10)
p(1 p)
suit une loi normale centre rduite. Etant donn une probabilit observe P (X) = p, nous en
dduisons lintervalle de confiance au niveau pour la probabilit thorique :
r
p(1 p)
pt = p t (8.11)
n
Les bornes infrieures des intervalles de confiance au niveau 0.01 sont reportes dans le
tableau 8.11. Globalement, les probabilits des vnements A, C, D, E et dans une moindre
mesure B sont loin dtre ngligeables. Les cas sont donc nombreux dans lequels les partiels
ninterviennent pas de faon majeure dans lvaluation des solutions. Nous justifions ainsi
lemploi simultan de plusieurs critres spectro-harmoniques. Une analyse plus fine mrite
toutefois de distinguer les heuristiques employes.
Lorsque la solution de lheuristique H est retenue, les probabilits des vnements sont
indpendantes de la taille du problme et ne dpendent que du caractre monophonique ou
polyphonique des cibles. Si la solution obtenue par lheuristique H est la plus pertinente,
cela signifie que les coordonnes de la solution thorique dans lespace des critres donnent la
bonne direction doptimisation (voir figure 8.4). Autrement dit, les erreurs dans lestimation
des descripteurs de la solution thorique sont toutes du mme ordre de grandeur, a fortiori
faible. En consquence, il y a fort a parier que cette dernire est relativement proche de la
frontire de Pareto. Dans ce cas, si lestimation des descripteurs est correcte pour tous les
critres, il est normal que les partiels apportent lessentiel de linformation dans 60 % des cas,
comme en atteste les probabilits moyennes de lvnement E.
En revanche, lorsque lheuristique Hs donne une meilleure solution, alors la position de
la solution cible dans lespace des critres ne donne pas la bonne direction doptimisa-
tion. Nous pensons que ce faux cap est d des erreurs destimation diffrentes selon les
descripteurs. La difficult du calcul des principaux partiels rsolus (notamment cause des
phnomnes de masquage) permet de faire lhypothse que les MRP de la solution thorique
ont t mal valus. En consquence, leur importance relative dans lidentification dune so-
lution pertinente dans le front est diminue. Cest bien ce que confirme la lecture du tableau
infrieur, en particulier pour les mixtures polyphoniques, pour lesquelles la probabilit que le
poids associ aux partiels soit infrieur 0.5 augmente fortement avec la taille du problme.
Dans les cas o Ks est une solution meilleure que K , les MRP ne permettent donc pas de
lidentifier, et sont peu peu relays par les moments spectraux qui interviennent alors des
fins de robustesse dans lvaluation des solutions. Pour les cibles monophoniques toutefois,
limportance des partiels augmente avec la taille du problme, sans doute car leur valuation
est plus aise (les phnomnes de masquage interviennent peu dans ces cas).
8.5. QUALIT DES SOLUTIONS DU FRONT DE PARETO 127
Tab. 8.11 Bornes infrieures des intervalles de confiance au niveau 0.01 pour les probabilits
thoriques des vnements A : wsc > wM RP , B : wsc > 0.5, C : wss > wM RP , D : wss > 0.5 et
E : wM RP < 0.5.
Heuristique H
Pinf (A) Pinf (B) Pinf (C) Pinf (D) Pinf (E)
mono-1 0.209 0.098 0.237 0.114 0.419
mono-2 0.213 0.101 0.228 0.110 0.398
mono-3 0.183 0.072 0.240 0.109 0.405
mono-4 0.174 0.056 0.225 0.107 0.416
poly-2 0.152 0.055 0.176 0.082 0.325
poly-3 0.164 0.075 0.155 0.056 0.308
poly-4 0.163 0.055 0.201 0.094 0.333
Heuristique Hs
Pinf (A) Pinf (B) Pinf (C) Pinf (D) Pinf (E)
mono-1 0.262 0.154 0.270 0.126 0.476
mono-2 0.333 0.179 0.343 0.215 0.502
mono-3 0.377 0.241 0.407 0.255 0.606
mono-4 0.174 0.056 0.225 0.107 0.416
poly-2 0.305 0.180 0.335 0.199 0.509
poly-3 0.454 0.298 0.480 0.289 0.695
poly-4 0.590 0.382 0.541 0.327 0.808
128 CHAPITRE 8. VALIDATION SUR UNE DESCRIPTION RDUITE
Conclusion
Nous concluons ici quant au caractre bien pos du problme de lorchestration formul
comme une tche doptimisation multicritre avec trois critres spectro-harmoniques a priori
non indpendants : le centrode spectral linaire, ltendue spectrale linaire, et les principaux
partiels rsolus. Afin de prouver la validit de cette formulation, nous avons gnr 3500 mix-
tures monophoniques et polyphoniques comprenant entre 1 et 4 sons. Chacune de ces mixtures
a t considre comme la cible dun problme dorchestration particulier, avec contraintes de
hauteurs, de capacit et de cardinalit. Pour chaque problme, le front de Pareto (les solutions
du problme multicritre) a t extrait aprs un parcours exhaustif de lespace de recherche, et
ce pour diffrentes combinaisons de critres. Lenjeu tait de vrifier si les solutions thoriques
de chaque problme taient pertinentes, savoir proches de la mixture cible. Cette tude
notamment montr :
quaugmenter le nombre de critres augmente la probabilit de trouver la solution tho-
rique dans le front de Pareto ;
quaugmenter le nombre de critres diminue la portion de lespace dominant la solution
thorique ;
que les solutions du front thorique sont dautant plus proches de la cible que le nombre
de critres est lev, et ce aussi bien en termes symboliques que descriptifs et perceptifs ;
enfin, que malgr une slectivit ingale des critres spectraux, les critres a priori mi-
neurs peuvent apporter une information prvalante dans lidentification dune bonne
solution, et que lemploi simultan de critres non indpendants permet souvent dva-
luer de manire plus robuste les solutions.
Nous nous autorisons donc dsormais poser le problme de lorchestration comme une
tache doptimisation combinatoire multicritre. Convaincus que les solutions des fronts de Pa-
reto sont pertinentes pour le compositeur, nous pouvons ds lors nous consacrer la recherche
dalgorithmes permettant de dcouvrir ces solutions en un temps raisonnable.
Chapitre 9
Algorithme dorchestration
129
130 CHAPITRE 9. ALGORITHME DORCHESTRATION
donc trouver un sous-ensemble I de {0; 1}Ns tel que la mixture compose des lments dindices
i I maximise la similarit perceptive avec la cible orchestrer, et ce dans la limite des
capacits instrumentales.
Ainsi formul, le problme de lorchestration sapparente fort un problme de sac dos
binaire [MT90] (Binary Knapsack Problem KP-O/1 ), dans lequel il sagit de remplir un
sac laide dobjets de poids (pi ) et dutilits (ui ) en maximisant lutilit totale, sans excder
la capacit C du sac :
P
max z(x) = xi ui
(KP-0/1) s.t. x P i {0; 1} (9.1)
xi p i C
1. Dans le cas de lorchestration, lutilit dun lment dpend des lments dj prsents
dans la configuration. Lajout dun trombone brassy na par exemple pas le mme
effet dans un alliage mezzo-fote de cordes que dans un accord de cuivres jou fortissimo.
2. Lutilit dune configuration ne peut pas tre dfinie comme la somme des utilits de
ses composantes. Pour sen convaincre, remarquons simplement que lajout dun lment
dans une configuration peut trs bien en dgrader la qualit.
3. Les contraintes instrumentales dans le cas de lorchestration ne se ramnent pas une
unique capacit C, mais un vecteur de capacits dont chaque lment reprsente la
quantit de chaque instrument dans lorchestre considr.
Notons toutefois quil existe une variante du problme du sac dos, connue sous le nom de
Multiple Container Knapsack Problem, dans laquelle le sac est divis en plusieurs conteneurs
de capacits variables. Nous tirons parti de la modlisation de ce problme dans la section
suivante.
1
Le caractre uni-critre de problme 9.1, en regard de laspect multicritre de lorchestration, ne doit pas
remettre en cause cette similitude. Il existe dailleurs une formulation multicritre du problme du sac dos.
9.2. MODLISATION ET ENCODAGE 131
Nous rappelons que DTdk (x) est la fontion de comparaison entre la cible T et un configuration
x pour le descripteur dk (voir dfinition 7.6 et proprit 7.1).
Encore une fois, la formulation 9.2 incite considrer le problme de lorchestration comme
un problme de sac dos multicritre conteneurs multiples. Mais, comme nous lavons dit au
paragraphe prcdent, la non-linarit (et plus particulirement la non-additivit) des fonctions
objectifs minimiser ne peut que nous en dissuader. Aussi sduisant soit-il, le cadre formel
du sac dos nest pas assez souple pour supporter la complexit des mlanges de timbres.
Les variables de dcision du problme 9.2 sont binaires : xi = 1 si et seulement si lchan-
tillon si de la base de donnes est retenu dans lorchestration, 0 sinon. On serait donc facilement
tent davoir recours la technique dencodage la plus rpandue dans les algorithmes gn-
tiques, qui consiste reprsenter les solutions par des chanes binaires (bit-string encoding),
ici de longueur Ns . Trois raisons sopposent ce choix :
1. La taille du problme. Nous travaillons actuellement avec un rservoir denviron 5000
sons. Pour une population de 1000 individus, lencodage du type bit-string implique donc
le stockage et la mise jour rcurrente dune matrice 5 millions dlments. Mme si
cela reste encore acceptable, la taille mmoire deviendra vite une limite sitt que nous
travaillerons avec davantage de sons et des populations potentiellement plus grandes.
2. Le petit nombre ditems impliqus dans une solution. Dans notre problme
dorchestration au maximum une petite centaine de sons (dans le cas de trs grands
orchestres) seront choisis parmi plusieurs milliers, occasionnant une frquence trs faible
de valeurs gales 1 dans la matrice reprsentant la population. On pourrait certes
choisir davoir recours une reprsentation parcimonieuse des donnes, mais cela ne
rsout pas le problme des contraintes multiples de capacit (cf. infra).
3. La multiplicit des contraintes de capacit. Dans le problme du sac dos, la
seule contrainte est la capacit globale du sac. La gestion des solutions inconsistantes
produites au cours des gnrations fait en gnral appel une mthode de rparation
de type glouton qui retire rcursivement les lments les plus volumineux jusqu
ce que la contrainte de capacit soit satisfaite ; ventuellement, des items plus petits
peuvent alors tre insrs dans le sac sil reste de la place. En orchestration, il y a
autant de contraintes de capacit que de type dinstruments, soit onze contraintes pour
linstrumentarium actuellement disposition, et leur respect exige le recours autant
de procdures de rparation. Autant donc chercher une reprsentation qui permette de
sen affranchir.
Compte tenu de ces remarques nous optons pour un encodage en N -uplets dentiers. Soit
(si )1iNs un ensemble de sons instrumentaux reprsentatifs dun orchestre de taille N . Une
solution K E est alors reprsente par un N -uplet i = (i1 , ..., iN ) valeurs dans D1 ...DN .
Chaque domaine Dk est dfini par :
Dk = Dk {e} , (9.3)
132 CHAPITRE 9. ALGORITHME DORCHESTRATION
o e est llment neutre, indiquant que linstrument k nest pas impliqu dans lorchestration,
et Dk la partie de {1, ..., n} associe linstrument k, i.e. (si )iDk sont les sons de la base
associs linstrument k.
En outre, afin dviter les doublons dencodage (i.e. deux gnomes diffrents exprimant la
mme solution) nous imposons la condition suivante, trs facilement satisfaite laide dun tri
par parties aprs chaque gnration dune solution :
Remarque 9.1. Grce cette reprsentation des solutions (qui se confond strictement avec
leur encodage gntique), une configuration est donc dfinie comme un ensemble de couples
variable/valeur dont chaque variable correspond un instrument j de lorchestre, valeurs
dans Dj . On notera D = D1 ... DN , quivalent E et {0; 1}Ns
Remarque 9.2. Comme nous le verrons au paragraphe suivant, les oprateurs gntiques
sont stables sur D. Toute configuration gnre alatoirement ou produite par une opration
gntique est donc, par dfinition, consistante avec les contraintes de capacit (i.e. lie aux
effectifs instrumentaux de lorchestre).
En dautres termes, le problme de lorchestration ainsi reformul est non contraint. Nous
verrons au chapitre 10 de quelle manire les ventuelles contraintes autres que celles de capacit
peuvent tre prises en compte au sein de lalgorithme de recherche.
En pratique, les rejetons sont engendrs par interversion alatoire des coordonnes des chro-
mosomes parents.
Remarque 9.3. Lquation 9.5 certifie que si (i, j) D2 (i.e. i et j reprsentent deux configu-
rations consistantes avec les contraintes de capacit), alors (k, l) D2 (le crossover uniforme
est stable sur D).
9.2. MODLISATION ET ENCODAGE 133
Crossover uniforme
art-harm B6 p
(b)
sul-ponticello D4 f
art-harm B6 p
sul-tasto Eb5+ mf
(c)
sul-ponticello D4 f
non-vibrato G3 mf
1-mutation
(a) substitution - (b) dltion - (c) insertion
Fig. 9.1 Oprateurs gntiques pour lorchestration (cas dun quatuor cordes). La case
vide (en gris) dsigne llment neutre.
134 CHAPITRE 9. ALGORITHME DORCHESTRATION
Lorsque deux chromosomes parents sont recombins non pas par un crossover uniforme,
mais, comme cest souvent le cas, par un crossover monopoint (voir figure 5.5, les gnes loi-
gns ont plus de chances dtre spars par le crossover que les gnes voisins dans la chane
(voir Whitley [Whi93]). Cette proprit est parfois souhaitable dans le cas de reprsentations
binaires chantillonnant un espace de dcisions valeurs relles, pas dans le cas de lorchestra-
tion. Considrons par exemple un quatuor cordes reprsent par des quadruplets (violon1,
violon2, alto, violoncelle), comme il en va sur la figure 9.1. Le crossover monopoint spa-
rera toujours le premier violon du violoncelle, et maintiendra toujours lun des duos (violon1,
violon2) ou (alto, violoncelle). En dautres termes, le potentiel exploratoire du crossover mo-
nopoint dpend de lordre dans lequel les instruments de lorchestre sont encods dans les
chromosomes. Le crossover uniforme nimplique quant lui aucune de ces restrictions, raison
pour laquelle nous le prfrons pour lorchestration.
En pratique, j est engendr par modification dune seule variable m, la nouvelle valeur tant
choisie dans le domaine associ Dm . La mutation monopoint est donc stable sur D.
Les domaines associs chaque variable contenant llment neutre e (voir section 9.2),
la mutation monopoint peut donc prendre la forme soit dune substitution, soit dune instan-
ciation de variable (insertion) soit dune dsinstanciation (dltion). La figure 9.1 illustre ces
trois types de mutation.
y a quivalence entre le choix dune solution et le choix dune fonction scalarisante (ou dune
direction doptimisation).
En un sens, le but de la recherche multicritre est ici de trouver la bonne fonction
scalarisante pour un problme dorchestration donn. Notons que grce cette approche, le
seul fait de rendre les poids alatoires ou dtermins permet de commuter entre un problme
multicritre et un problme mono-critre.
9.5 Pseudo-code
Lalgorithme que nous prsentons ici permet dobtenir, en un temps raisonnable, une ap-
proximation du front de Pareto associ tout problme pouvant tre ramen la formula-
tion 9.1. Grce la modlisation propose au paragraphe 9.2, les contraintes de capacit (i.e.
les restrictions imposes par les effectifs instrumentaux de lorchestre) sont toujours satisfaites.
Cette version de lalgorithme aborde donc des problmes exclusivement non contraints. Son
extension des problmes assortis de contraintes supplmentaires est lobjet du chapitre 10.
La qualit de lapproximation retourne par notre algorithme est value au chapitre 11.
Lalgorithme 4 est un AG inspir de lalgorithme MOGLS (Multi-Objective Genetic Local
Search) de Jaszkiewicz [Jas01] [Jas02] pour son approche de loptimisation multicritre par
tirage alatoire de fonctions sclarisantes (voir sections 5.7 et 9.3). Dans lalgorithme MOGLS,
une seule configuration est obtenue chaque gnration par crossover, avant dtre amliore
par une mthode de recherche locale (il sagit en loccurence dune simple descente) selon la
fonction scalarisante en cours. La nouvelle configuration remplace alors, dans la population, la
configuration de moins bonne fitness. La partie gntique de MOGLS peut donc tre considre
comme un moyen de gnrer la configuration initiale dun algorithme de descente pour lequel
la fonction optimiser est chaque fois diffrente.
Ishibushi et Murata [IY02] font observer que dans cette classe dalgorithmes dit hy-
brides la partie gntique tient un rle dexploration alors que la recherche locale est
dvolue lintensification de la recherche. Les auteurs constatent par ailleurs quen gnral
la majorit du temps de calcul est absorbe par la recherche locale, et recommandent, pour
une performance optimale des mthodes hybrides, dviter ce dsquilibre. Soucieux de privil-
gier dans un premier temps lexploration de lespace de recherche au profit de lintensification
dans une zone particulire, nous avons donc choisi dlibrment de ne pas implmenter de
recherche locale dans notre algorithme dorchestration. Ce parti pris va lencontre des rsul-
tats de Ishibushi et Murata [IY02], selon lesquels la mthode MOGLS sans recherche locale
est moins performante que le SPEA de Zitzler & Thiele [ZT98b] [ZT98a] [ZT99]. Rappelons
toutefois que le but premier de notre algorithme est de dcouvrir une configuration intres-
sante pour le compositeur, rvlatrice de ses prfrences en termes dcoute du timbre (voir
section 7.2). Si cette configuration nest pas pleinement satisfaisante, elle permet au moins
didentifier la fonction scalarisante la plus pertinente pour un problme donn, selon laquelle
une intensification de la recherche (voir paragraphe 9.3) pourra toujours tre mene par la
suite. Pas de recherche locale dans cet algorithme donc, mais, comparativement MOGLS,
un plus grand nombre de configurations engendres par les oprateurs gntiques chaque
gnration.
Lalgorithme 4 prend en arguement une cible orchestrer T . Une population initiale de
pop
taille Ninit est gnre par instanciation alatoire des variables, avec une probabilit dinstan-
ciation gale 0.55. Ainsi, chaque configuration de la population initiale mobilise en moyenne
un peu plus de la moiti de la ressource orchestrale.
A chaque gnration, un sous-ensemble de la population (de taille Nmate ) est slectionn
par tournoi binaire, dont la supriorit sur les autres mthodes de slection a t voque
au paragraphe 5.6. Deux individus sont tirs alatoirement dans la population courante, et
le meilleur des deux selon la fonction scalarisante en cours est retenu dans le bassin de re-
production. Cette opration est rpte jusqu ce que le bassin atteigne la taille Nmate . Les
oprations de crossover et mutations sappliquent alors sur les lments du bassin, et les nou-
veaux individus sont intgrs la population courante.
9.5. PSEUDO-CODE 137
pop
Si la taille de la population dpasse une valeur limite Nmax , la procdure decrease_PADE
est invoque pour liminer les individus situs dans les zones les plus denses. La diversit de la
population dans lespace des critres est ainsi prserve (voir sections 9.4 et 5.8). En pratique,
on retire itrativement les individus de densit locale maximale et de moins bonne fitness selon
la fonction scalarisante en cours. Afin dviter de retirer des solutions de lapproximation
courante, lchantillonnage de la population par la procdure decrease_PADE ne sapplique
quaux solutions domines.
A chaque gnration, lapproximation courante est mise jour par lalgorithme 3
pareto
(update_pareto_set). Si la taille de cette dernire dpasse une valeur limite Nmax , la pro-
cdure decrease_PADE est invoque. Lalgorithme se termine lorsque le nombre de gnrations
atteint itermax .
Nous prsentons dans ce chapitre une mthode efficace pour la gestion, dans un problme
dorchestration, de contraintes autres que celles lies leffectif instrumental (voir chapitre
9). Nous commenons par numrer un ensemble de contraintes N -aires portant sur les attri-
buts des configurations, puis montrons quelles se rpartissent en deux catgories : contraintes
de design et contraintes de conflit. Nous introduisons alors lheuristique de recherche locale
CDCSolver, qui sappuie sur cette dichotomie pour trouver en un temps acceptable une confi-
guration consistante avec lensemble du rseau de contraintes. CDCSolver est valu par com-
paraison avec un algorithme alatoire sur des problmes de petite taille et de difficult variable.
Nous terminons avec lintgration de CDCSolver dans lalgorithme dorchestration.
139
140 CHAPITRE 10. GESTION DES CONTRAINTES
contraintes de capacit. Dune faon plus gnrale, on dira que la consistance est garantie pour
toute contrainte de cardinalit maximale place sur lattribut instrument , quelle que soit
la valeur de ce dernier. Mais, nous allons le voir, il existe bien dautres types de contraintes,
portant sur dautres attributs.
Notre exprience avec les compositeurs au cours de notre recherche dune part, et celle plus
gnrale des contraintes en composition assiste par ordinateur dautre part, nous enseignent
qu lexception des problmes de composition entirement formalisables par la PPC1 , il est
trs difficile de spcifier des contraintes en dehors dun contexte musical. Imaginons le cas
dun compositeur dsirant orchester une srie daccords et disposant dj de lorchestration
du premier. Selon le degr de contraste dsir chaque changement daccord, on peut imposer
pour laccord courant davoir au plus ou au moins un certain nombre de notes communes avec
le prcdent. Aussi rudimentaire soit-il, laccord initial constitue dj un contexte : cest ici
un point de dpart, ce sera ailleurs un point de passage, ou un point darrive. Contraindre
une orchestration , cest donc dj penser le matriau musical dans sa mise en temps, dans ses
relations temporelles aux autres objets musicaux. Or notre outil dorchestration a t conu
comme un environnement hors temps dexploration du timbre : il produit une matire, un
objet brut que le compositeur devra polir avant de linsrer dans la composition. De
fait, dans la grande majorit des cas, tous les problmes dorchestration commencent sans
contraintes.
Bien souvent toutefois, les critiques faites aux suggestions dorchestration dans le cas o
elles ne satisfont pas le compositeur portent certes sur leurs proprits timbrales, mais aussi
sur leurs attributs : telle hauteur est prsente dans la cible et manque dans lorchestration,
tel mode de jeu est inaudible en prsence dinstruments jouant fortissimo, telle sourdine est
ncessaire, la densit harmonique (i.e. le nombre de hauteurs diffrentes joue simultanment)
est trop faible ou trop forte, lorchestration mobilise une trop grande ou trop petite proportion
de lorchestre, etc. La possibilit dajouter des contraintes sur les attributs est alors bienvenue
pour guider la recherche vers des solutions plus pertinentes. Certes ces contraintes ne
viennent pas spontanment au compositeur, mais elles surgissent en raction aux solutions
libres retournes par le systme. Dun certain point de vue, on peut dire quelles viennent
combler les carences ventuelles de la description du timbre (voir section 8.1) qui, dans certains
cas, ne suffit pas pour dcouvrir les solutions les plus proches de la cible au sens perceptif.
En thorie, nimporte quel attribut est recevable : instrument, famille, hauteur, mode de jeu,
dynamique, sourdine, corde. . . si cela bien sr a un sens musicalement. Quant aux oprateurs,
ils se rpartissent en trois catgories selon le nombre darguments supplmentaires quils re-
quirent, comme lindique le tableau 10.1.
Loprateur all-diff associ un attribut A signifie que toutes les composantes de lorches-
tration doivent avoir des valeurs diffrentes pour lattribut A.
1
Les problmes de sries dintervalles, de suites daccords ou de canons rythmiques, pour nen citer que
quelques uns, appartiennent cette catgorie voir ce sujet la thse de Charlotte Truchet [Tru04].
10.1. CONTRAINTES EN ORCHESTRATION 141
Tab. 10.1 Oprateurs darit variable exprimant des contraintes sur les attributs des confi-
gurations.
Oprateur Argument 1 Argument 2
all-diff - -
at-most-diff quantit n -
at-least-diff quantit n -
at-most quantit n valeur v
at-least quantit n valeur v
Ex.1 Lorchestration ne doit jamais impliquer deux fois la mme hauteur scrit :
<attribut=note><oprateur =all-diff >
Ex.3 Tous les instruments doivent jouer avec la mme dynamique scrit :
<attribut=dynamique><oprateur =at-most-diff ><quantit=1>
permet deffectuer la recherche avec tous les sons de flte tout en garantissant quun seul son
sera compris dans lorchestration. Le mme raisonnement est videmment valable pour les
clarinettistes, trompettistes, trombonistes, saxophonistes et percussionnistes, qui peuvent tre
amens changer dinstrument au cours dune mme uvre.
Nous avons en outre pourvu notre langage de deux oprateurs de cardinalit globale : size-
min et size-max. Comme leur nom lindique, ils permettent de minorer ou de majorer le nombre
142 CHAPITRE 10. GESTION DES CONTRAINTES
dinstruments impliqus dans une orchestration. Ces oprateurs sont dun grand intrt lorsque
le compositeur veut augmenter la masse orchestrale ou au contraire rserver une partie de
lorchestre pour un matriau musical se superposant la texture propose par loutil.
Pour les raisons voques au dbut de cette section, les contraintes lies lexcution
i.e. au droulement de la musique dans le temps ne sont pas prises en compte au sein de
notre systme. Modliser le potentiel sonore des instruments hors de tout contexte temporel
est une tche difficile, mais abordable du moins partiellement dans le cadre dune
thse. Matriser les possibilits denchanement de timbres ralisables par un instrument solo
est dune complexit bien suprieure, et ne parlons mme pas de linfinit de variations que
peut produire un orchestre. Nous verrons cependant en fin de chapitre de quelle manire les
contraintes peuvent tre utilises pour transformer progressivement une orchestration, sans
toutefois disposer dune formalisation temporelle du timbre. Lvolution sera alors contrle
non pas par des descripteurs perceptifs, mais par les attributs symboliques des configurations
successives.
Nos fonctions de cot ne dpendent que de loprateur impliqu dans la contrainte : at-
most, at-least, at-most-diff, at-least-diff, all-diff, size-min, size-max. Nous les construisons selon
la rgle suivante : elles renvoient le nombre minimum de variables modifier pour que la
contrainte soit satisfaite. Elles sont calcules partir de la reprsentation des configurations
introduites la section 9.2 : chaque variable correspond un instrument, et chaque valeur
un son jouable par linstrument. Une requte pralable dans une base de donne permet
de retourner, pour chaque son, la valeur de lattribut impliqu dans la contrainte avant den
calculer la consistance. Dans la suite de cette section, nous dsignons respectivement par n et
v les premier et second arguments ventuels de nos oprateurs.
10.1. CONTRAINTES EN ORCHESTRATION 143
at-most, at-least
Soit nv le nombre de fois o apparait la valeur v dans la configuration (effectif de la valeur
v). On a alors trivialement, pour les oprateurs at-least et at-most :
zat-least = max(nv n, 0) et zat-most = max(n nv , 0) (10.1)
at-least-diff
Soit maintenant nA le nombre total de valeurs que peut prendre lattribut A et (ni )1inA
les effectifs des valeurs prises par A. Soit la fonction indicateur de R+ ((x) = 1 si x > 0,
(x) = 0 sinon). La fonction de cot pour loprateur at-least-diff compte le nombre de valeurs
diffrentes pour lattribut A et renvoie la diffrence avec la quantit limite n si cette dernire
et suprieure :
nA
!
X
zat-least-diff = max n (ni ), 0 (10.2)
i=1
at-most-diff
De faon non intuitive, la fonction de cot pour at-most-diff nest pas la symtrique de la
prcdente. Soit par exemple la contrainte :
<attribut=note> <oprateur =at-most-diff > <quantit=1>
(Tous les instrument doivent jouer la mme note)
Soient alors les deux configurations K1 = (C4,A4,C4,A4) et K2 = (C4,C4,C4,A4) (seules
les hauteurs ont t mentionnes par souci de lisibilit. Si on compte le nombre de valeurs
diffrentes pour lattribut A et que lon renvoie sa diffrence avec la quantit limite n si
cette dernire est infrieure, on obtient alors z(K1 ) = z(K2 ) = 1. Autrement dit, il ny a
aucun intrt pour un algorithme de recherche locale remplacer A4 par C4 pour la seconde
variable, alors que K2 est plus proche de satisfaire la contrainte que K1 (il faut modifier une
seule variable dans K2 contre deux dans K1 ).
Soit (ni )1inA la permutation de (ni )1inA pour laquelle les effectifs sont classs dans
lordre dcroissant, ce qui donne (2, 2) pour K1 et (3, 1) pour K2 . On a alors :
nA
X
zat-most-diff = ni , (10.3)
i=n+1
all-diff
Quant loprateur all-diff, lide la plus immdiate consiste retourner leffectif maximal
moins 1. Toutefois, si nous considrons les deux configurations K1 = (C4,A4,C4,A4) et K2 =
(C4,G4,C4,A4), on obtient pour la contrainte all-diff sur les hauteurs les valeurs de cot
z(K1 ) = z(K2 ) = 1. Encore une fois, un algorithme de recherche locale naura donc aucun
intrt remplacer A4 par G4 pour la seconde variable, alors que K2 est plus proche de
satisfaire la contrainte que K1 . Alors quavec la foncion :
nA
X
zall-diff = (ni 1)(ni 1) , (10.4)
i=1
144 CHAPITRE 10. GESTION DES CONTRAINTES
size-min, size-max
Soit n le nombre de variables dont la valeur est diffrente de llement neutre e (voir
section 9.2). On a alors trivialement :
Consistance globale
Comme la plupart des mthodes de recherche locale, notre algorithme favorise dans
ces dplacements les configurations de consistance maximale pour lensemble du rseau de
contraintes. Lvolution dans lespace de recherche est donc guide par une fonction de cot
globale , que nous dfinissons comme la somme des fonctions de cot associes chaque
constrainte. Elle peut sinterprter une estimation du nombre de variables modifier pour
parvenir une solution satisfaisant toutes les contraintes.
potentiellement engendrs par linstanciation dune nouvelle variable sont alors rsolus par ds-
instanciation des variables incompatibles avec la nouvelle valeur. Lalgorithme sarrte lorsque
toutes les variables sont instancies.
Dun point de vue plus abstrait, on peut donc dire que lheuristique CN -tabou permet de
traiter des problmes dfinis par un ensemble de contraintes de conflit et par une contrainte
de design exigeant que toutes les variables doivent tre instancies. Lalgorithme avance dans
la rsolution en diminuant la fonction de cot associe la contrainte de design (i.e. en
instanciant des variables), tout en sadaptant la vole aux contraintes de conflit qui surgissent
des nouvelles instanciations.
N.B. Dans un contexte dorchestration, une configuration dont certaines variables ont pour
valeur llment neutre (cest--dire, dun point de vue musical, un silence) nest en aucun
cas une instanciation partielle. Il nest en effet prcis nulle part que tous les instruments
disponibles doivent tre mobiliss dans une orchestration. Ce sont au contraire les variations
de leffectif instrumental et des plans sonores qui, au cours du temps, crent la richesse du
timbre orchestral. En cela, lorchestration se distingue des problmes classiques pour lesquels
il ny a en gnral pas dlment neutre. Dans le problme des N -reines par exemple, une
configuration dans laquelle la position dune reine nest pas dtermine nest videmment pas
recevable. A lextrme inverse, une configuration constitue uniquement dlments neutres
est une solution, certes inintressante, mais admissible pour un problme dorchestration sans
contraintes de design : le silence total ne peut pas violer de contrainte de conflit. Encore une
fois, la notion d instanciation partielle na de sens quen prsence de contraintes de design.
Dans la plupart des CSP classiques, il ny en a quune seule : toutes les variables doivent tre
instancies.
Le tableau 10.3 recense lensemble des oprateurs introduits au paragraphe 10.1.2 et les
rpartit en fonction du type de contrainte quils induisent. Notre langage de contraintes pour
lorchestration peut ainsi tre tendu de deux manires :
146 CHAPITRE 10. GESTION DES CONTRAINTES
10.3 CDCSolver
Dans cette section, nous nous concentrons sur la dimension thorique de lheuristique
CDCSolver et en exposons les mcanismes au travers des notions gnriques de contraintes de
design et contraintes de conflit, indpendamment des oprateurs dfinis en supra.
Nous avons dtaill, au chapitre 6, deux mthodes rcentes de recherche locale pour la
rsolution de problmes de satisfaction de contraintes : la recherche adaptative et lheuris-
tique CN -tabou. La premire manipule des configurations totalement instancies et utilise
une projection des contraintes sur les variables pour choisir celle modifier en priorit.
La seconde garantit en permanence une consistance locale sur des instanciations partielles.
Lorsquune nouvelle valeur est assigne une variable libre, linstancation est propage en
dsaffectant les variables en conflit.
Lalgorithme CDCSolver combine les deux mthodes. A partir dune configuration incon-
sistante, on commence par modifier ou dsinstancier en les remplaant par llment neutre
les variables impliques dans les contraintes de conflit. Lorsque ces dernires sont toutes
vrifies, une variable libre est alors instancie de manire rduire les contraintes de design.
Les affectations se poursuivent soit jusqu la satisfaction de lensemble des contraintes, soit
jusqu lapparition de nouveaux conflits. Dans ce dernier cas, le processus prcdent est rpt
tant quun nombre maximal ditrations na pas t dpass. A chaque mouvement, une heu-
ristique permet de dterminer la variable modifier en premier (dans le cas dune contrainte
de conflit) ou instancier en priorit (dans le cas dune contrainte de design). Contrairement
la recherche adaptative, il nest pas possible de comptabiliser le nombre de contraintes violes
dans lesquelles intervient chaque variable, en raison du caractre global de nos contraintes.
Nous procdons alors de la manire suivante :
Si une contrainte de conflit est viole dans la configuration courante K, alors nous calcu-
lons la consistance pour toutes les configurations obtenues partir de K en remplaant
tour tour chaque variable instancie par llment neutre. La configuration de cot
minimal correspond alors la variable modifier en priorit (voir algorithme 5).
Si une contrainte de design est viole dans la configuration courante K, alors nous calcu-
lons la consistance pour toutes les configurations obtenues partir de K en remplaant
10.3. CDCSOLVER 147
tour tour chaque variable libre par une valeur alatoire de son domaine. La confi-
guration de cot minimal correspond alors la variable instancier en priorit (voir
algorithme 6). Si aucune variable nest libre, le choix seffectue par dsinstanciation,
selon la mthode applique aux variables de conflit.
Dans les deux cas, la valeur de la variable modifie est remplace par toutes les autres du
domaine, et la configuration de cot global minimal est retenue comme configuration courante.
Le fonctionnement de CDCSolver (voir algorithme 7) est donc bas sur une alternance de
mthodes change_worst_variable et instanciate_best_variable. Bien souvent, ces dernires
ont des objectifs contradictoires : remplacer une variable affecte par llment neutre permet
de soulager les contraintes de conflit, au risque de violer davantage de contraintes de design
(et vice-versa). Lalgorithme peut donc rapidement se retrouver enferm dans un cycle d
la prsence dun minimum local dans la fonction de cot (voir section 6.4.1). Pour viter ce
problme, CDCSolver dispose dune mmoire court terme de type tabou . Cette technique
propose par Glover [GL97] consiste stocker dans une liste FIFO dite liste tabou
les dernires configurations visites. Lors de lexploration du voisinage courant, le mouvement
ne peut se faire vers une configuration de la liste tabou.
En pratique on se contente souvent, pour viter davoir rechercher une configuration
passe dans une liste potentiellement longue, de marquer tabou la dernire variable modi-
fie ; on ne pourra alors pas changer cette variable tant quelle demeurera dans la liste tabou.
CDCSolver utilise une version dynamique de ce principe : lorsquune variable est modifie,
elle est marque tabou pour un nombre ditrations gal au nombre de fois o la variable a
dj t modifie depuis le dbut de lexcution. Ce mcanisme, utilis par Vasquez & Dupont
[VHD03] dans lheuristique CN -tabou, permet de sadapter en cours dexcution la longueur
des cycles engendrs par le paysage de la fonction de cot.
148 CHAPITRE 10. GESTION DES CONTRAINTES
Dans notre algorithme, seules les variables non tabou peuvent donc tre modifies. Cette
restriction est forte, car elle interdit dexplorer de nombreuses configurations nayant pas encore
t visites. La technique habituellement utilise pour contrecarrer cet effet est laspiration : si
la modification dune variable marque tabou permet datteindre une valeur de cot inf-
rieure celle de la meilleure configuration obtenue jusqualors, le statut tabou est exception-
nellement rvoqu. En pratique, les mthodes change_worst_variable et change_best_variable
commencent par essayer de modifier une variable marque tabou . Si laspiration nest pas
justifie, le voisinage non tabou est alors explor.
Pour des raisons de lisibilit, les oprations lies la gestion des statuts tabou ne
figurent pas dans les algorithmes 5, 6 et 7.
Complexit
1: Kbest K
2: iter 1
3: tant que iter < itermax faire
4: tant que K viole au moins une contrainte faire
5: tant que K viole au moins une contrainte de conflit faire
6: K change_worst_variable(K)
7: si z(K) z(Kbest ) alors
8: Kbest K
9: fin si
10: iter + +
11: fin tant que
12: si K viole au moins une contrainte de design alors
13: K instanciate_best_variable(K)
14: si z(K) z(Kbest ) alors
15: Kbest K
16: fin si
17: iter + +
18: fin si
19: fin tant que
20: fin tant que
21: retourner Kbest
reste du mme ordre de grandeur que la recherche adaptative, le paramtre N tant dans tous
les cas major par la taille des plus gros orchestres.
La fonction de cot z dans lalgorithme 7 est par dfaut la somme des fonctions de cot as-
socies chaque contrainte du rseau. A chaque mouvement, lalgorithme se dplace donc vers
la configuration du voisinage courant qui viole le moins les contraintes. Si plusieurs choix sont
possibles, la nouvelle configuration est choisie alatoirement, sans se soucier de ses proprits
timbrales (i.e. de ses valeurs de descripteurs).
Dans un contexte doptimisation multicritre, on pourrait trs bien dcider de choisir, au
sein du voisinage courant de consistance maximale (i.e. de fonction de cot minimale), une
solution non-domine. Cela ncessiterait toutefois un grand nombre de comparaisons de valeurs
chaque mouvement. En revanche, il existe un cas de figure dans lequel les poids relatifs des
critres intervenant dans les fonctions scalarisantes de Tchebycheff (voir sections 5.7 et 9.3)
sont connus : lorsquaprs une premire excution de lalgorithme, le compositeur choisit une
solution intermdiaire pour relancer la recherche (voir section 13.3) ou pour la transformer
laide de contraintes (voir sections 10.6 et 13.3), alors les poids ne sont plus alatoires, mais
dduits des valeurs de critres de cette solution (voir annexe B). La recherche devient alors
mono-critre, guide par une fonction scalarisante unique.
Nous avons dans ce cas tout intrt considrer, en plus de la consistance, la valeur de
fitness pour guider les mouvements de CDCSolver. Lors de lexploration du voisinage cou-
rant, la nouvelle configuration sera celle de meilleure fitness parmi les configurations les plus
150 CHAPITRE 10. GESTION DES CONTRAINTES
consistantes (i.e. de cot minimal). Il suffit pour cela de modifier la fonction de cot z dans
les mthodes change_worst_variable ou change_best_variable ainsi que dans lalgorithme
principal : en rajoutant z la valeur de fitness, on obtient une fonction de cot qui favo-
rise les configurations les plus consistantes, tout en pnalisant, niveau gal de violation de
contraintes, les configurations de plus grande fitness (i.e. les moins adaptes).
Quand cela est possible, CDCSolver prend donc sa charge une partie de loptimisation.
La recherche profite alors de la complmentarit entre les mthodes de recherche locale et les
mthodes population.
10.4 Evaluation
Lalgorithme CDCSolver a t valu laide sur des problmes de petite taille. Nous
rutilisons ici les cibles polyphoniques quatre sons construites la section 8.2 et utilises
dans lensemble du chapitre 8 pour valider notre approche thorique de lorchestration sur une
description rduite du timbre instrumental.
Rappelons que ces cibles ont t construites de manire satisfaire trois types de
contraintes, cela afin de rduire suffisamment lespace de recherche pour pouvoir en calcu-
ler lensemble des possibilits en un temps acceptable :
Contraintes de cardinalit : les cibles sont des mixtures impliquant exactement quatre
instruments.
Contraintes de hauteur : les cibles sont des mixtures comprenant quatre notes diffrentes
dans un intervalle de deux octaves.
Contraintes de capacit : les cibles sont des mixtures nutilisant quune seule fois le mme
instrument.
Chaque cible ainsi construite induit un espace de possibilits, que nous avons choisi de res-
treindre par un orchestre constitu dun seul instrument de chaque type ; les contraintes de
capacit y sont donc toujours vrifies, grce la modlisation adopte dans le chapitre prc-
dent. En outre, nous excluons de cet ensemble de possibilits toute configuration ne compre-
nant pas exactement quatre instruments. Ces deux limitations nous permettent de rutiliser
les espaces de recherche patiemment calculs au chapitre 8 pour chaque mixture cible.
N.B. Les mixtures dont nous nous servons dans cette valuation nont ici pas dintrt en
tant que cibles (i.e. comme objectifs dun problme doptimisation), mais parce quelles sont
lies des espaces de possibilits dj calculs et qui peuvent tre dfinis par deux contraintes
et un filtre : contraintes de cardinalit (lespace se limite aux combinaisons de quatre instru-
ments), contraintes de capacit (on ne peut pas avoir deux fois le mme instrument dans une
combinaison), et filtre sur les hauteurs (lespace de recherche est limit aux sons dont la hau-
teur appartient celle de la mixture cible ce nest quau cours de la recherche proprement
dite que la condition davoir exactement toutes les notes de la cible dans la solution deviendra
une contrainte).
appelerons dsormais cet ensemble espace de rfrence de niveau 2 car il est dfini laide
de deux contraintes de cardinalit :
A partir de cette espace de rfrence, nous construisons des sous-ensembles inclus les uns
dans les autres par ajout successif de contraintes supplmentaires mentionnes dans le tableau
10.4 (chaque niveau est donc dfini par toutes les contraintes des niveaux infrieurs). Cette
opration est rpte pour toutes les mixtures polyphoniques quatre sons : notre base de
test dnombre donc 500 instances de problmes, comprenant chacune 5 niveaux de difficult
croissante (de 3 7) par rapport aux espaces de recherche (ensembles de rfrence de niveau
2). CDCSolver a donc t excut 2500 fois dans ce processus dvaluation.
Niveau Description
2 Exactement quatre instruments dans lorchestration
3 Les quatre notes de la cible prsentes dans lorchestration
4 Les instruments sont tous de familles diffrentes
5 Au moins un violoncelle dans lorchestration
6 Au plus deux dynamiques diffrentes
7 Au plus un mode de jeu ordinario
Le tableau 10.5 donne une ide de la taille moyenne des ensembles consistants pour chaque
niveau de contrainte. Il permet de se faire une ide de la difficult du problme : pour le niveau 6
par exemple, seules 0.05% des configurations du niveau 2 sont consistantes. La probabilit de
tirer au hasard une solution est donc denviron 1 sur 2000. Une mthode de recherche purement
alatoire ou un algorithme generate-and-test (voir paragraphe 6.3.1) dcouvriront une solution
au bout de 2000 itrations en moyenne.
Les performances comparatives de CDCSolver par rapport un algorithme alatoire (ran-
dom) sont reportes dans le tableau ??. La dernire colonne montre que plus la difficult du
problme augmente, plus la performance relative de CDCSolver est leve.
152 CHAPITRE 10. GESTION DES CONTRAINTES
Dans cette valuation, lalgorithme CDCSolver ne pouvait excder 500 itrations. Dans
plus de 99 % des cas pour les problmes de niveau infrieur ou gal 6, et dans plus de 95 % des
cas pour le niveau 7, une configuration consistante a t trouve en moins de 500 itrations. Le
nombre moyen ditrations bien infrieur 500 pour lensemble des niveaux de difficult montre
que la lgre dgradation des performances pour les problmes de niveau 7 peut tre impute
des instances particulirement difficiles pour lesquelles davantage ditrations auraient t
ncessaires.
Nous avons vu la section 10.3 que le mouvement vers une configuration du voisinage
courant pouvait tre dtermin de deux manires :
soit en choisissant une configuration non tabou qui minimise la somme des fonctions de
cot associes aux contraintes ;
soit en choisissant, parmi les configurations non tabou qui minimisent la somme des
fonctions de cot associes aux contraintes, celle de fitness minimale, sous rserve que
celle-ci soit calculable (i.e. quun jeu de poids ou une fonction scalarisante soit
spcifi pour lagrgation des contraintes en une valeur unique).
Nous avons galement test les performances de CDCSolver dans ce second cas de figure,
en donnant pour fonction scalarisante la norme induite (voir section 8.5.1 et annexe B) par
chaque solution thorique (i.e. la configuration qui reproduit exactement lorchestration utilise
comme mixture cible voir section 8.3).
Tab. 10.7 Performances de CDCSolver (les configurations sont values selon leur niveau
de violation de contrainte et sur leur fitness).
Les performances avec fitness sont reportes dans le tableau 10.7. Encore une fois, ces
dernires augmentent (relativement au hasard) avec la difficult du problme. Autre phno-
mne notable, les taux moyens de russite (dcouverte dune solution consistante) et le nombre
moyen ditrations sont meilleurs lorsque les critres audio interviennent dans lvaluation des
configurations. La fitness semble donc apporter une information supplmentaire pour diminuer
le niveau de violation des contraintes. Cest a priori surprenant, car la fitness est calcule
laide de la norme induite par la solution thorique du problme doptimisation, laquelle na
a priori aucune raison de satisfaire les contraintes du tableau 10.4. Toutefois, remarquons que
par construction des cibles de test, les solutions thoriques sont toujours consistantes jusquau
niveau 3. Or les contraintes dfinissant le troisime niveau figurent (avec celles des niveaux
4 et 7) parmi les plus dlicates satisfaire : il faut dans le pire cas modifier trois variables
pour obtenir la consistance. Faire intervenir la fitness dans lvaluation des configurations per-
met donc peut-tre, en favorisant (en principe) les mouvements vers la solution thorique, de
satisfaire plus facilement la contrainte sur les hauteurs.
Tab. 10.8 Amlioration de fitness avec CDCSolver dans le cas o les valeurs de critres
interviennent dans lvaluation des configurations.
Le tableau 10.8 montre en outre que lorsque les valeurs de critres audio sont prises en
compte dans lvaluation du voisinage, CDCSolver amliore de faon significative la fitness
dune configuration alatoire inconsistante. Lalgorithme peut donc combiner la fois rpara-
tion et affinage des configurations. Cette observation est pour nous dun double intrt :
1. Dans un cas dorchestration sous contraintes, lorsque lalgorithme est relanc partir
dune solution intermdiaire juge pertinente par le compositeur (voir sections 9.3 et
13.3), le processus doptimisation est pris en charge la fois par lalgorithme gntique
et par CDCSolver. La complmentarit dune mthode population et dune mthode
de recherche locale (voir section 5.3) contribue alors lefficacit du processus global.
2. Lorsque CDCSolver est utilis pour transformer graduellement une solution dorchestra-
tion laide de contraintes (voir sections 10.6 et 13.3), le mouvement dune configura-
tion la suivante seffectue de manire minimiser les diffrences perceptives entre les
timbres.
En rsum, lintgration dune phase doptimisation au sein de CDCSolver est possible
et souhaitable sitt quune bonne fonction scalarisante a t identifie pour le problme en
cours. Nous retrouvons l le constat nonc aux chapitres prcdents quant notre approche
multicritre : elle doit permettre dinfrer au plus vite les prfrences dcoute du compositeur,
afin dinjecter cette information dans les tapes suivantes du processus de recherche.
154 CHAPITRE 10. GESTION DES CONTRAINTES
Dans notre algorithme dorchestration (voir section 9.5), les configurations ne sont jamais
compares selon la dominance de Pareto, mais toujours aprs une agrgation des critres par
une fonction scalarisante de Tchebycheff. Les relations de dominance entre les configurations
sont alors projetes sur une distance mono-value la fitness qui permet de comparer
toute paire de configurations.
En prsence de contraintes, nous utilisons aprs chaque agrgation des critres une fonction
pnaliser_fitness qui permet de retrouver les proprits de la dominance au sens de Deb.
Soient respectivement f = {f (x) | x X} et z = {z(x) | x X} les valeurs de fitness et de
fonction de cot dans la population courante. On dfinit alors :
f (x) si z(x) = 0
x X, pnaliser_fitness (f (x), z(x)) =
z(x) + max f sinon
Lors de la slection des individus pour la reproduction : les configurations ont dautant
plus de chances dtre slectionnes quelles violent peu les contraintes.
Lors de la mise jour de la population : les configurations de plus faible consistance
sont retires en premier.
Fig. 10.1 Passage continu dun accord de cordes vers un accord de vents laide de CDC-
Solver. Partition en Ut.
158 CHAPITRE 10. GESTION DES CONTRAINTES
Lvolution du timbre se fait par un transfert continu des cordes vers les vents, en modifiant
la contrainte sur la famille dinstruments (les contraintes de cardinalit sont conserves de
manire abandonner progressivement les cordes) :
La partition de la figure 10.1 permet de suivre la trace de cette transformation (chaque mesure
correspond une tape du calcul). Lorchestration finale tant limite quatre instruments,
linstanciation dune nouvelle variable entraine systmatiquement la violation de la contrainte
de cardinalit maximale : une dsinstanciation est alors ncessaire. Lentre dun instrument
vent donc est aussitt suivie, la mesure suivante, par le retrait dun instrument cordes. En
ne conservant que les mesures impaires de la figure 10.1, on obtient un mouvement de timbre
nimpliquant jamais que quatre instruments.
Du point de vue des contraintes, le choix dun instrument rajouter ou retirer de lor-
chestration est, fonctions de cot gales, indiffrent : la seconde mesure par exemple, la
mme valeur de consistance est obtenue selon quon insre un basson, une flte, une clari-
nette ou un hautbois dans lorchestration. En revanche, la fitness permet de distinguer ces
possibilits, en retenant la configuration de fitness maximale selon la fonction scalarisante
en cours (cette dernire est calcule laide des valeurs de critres obtenus pour lorches-
tration initiale). La continuit du timbre est ainsi encourage dans le passage dune confi-
guration la suivante. Lexemple de la figure 10.1 peut tre cout en ligne sur le site :
http://recherche.ircam.fr/equipes/repmus/carpentier/phdsounds/.
Chapitre 11
Tests de performances
Nous terminons cette partie avec un chapitre consacr lvaluation quantitative de notre
algorithme dorchestration. Nous commenons par montrer en quoi lvaluation des mthodes
multicritres est une tche particulirement dlicate, et discutons brivement les approches
en gnral adoptes dans la littrature. Nous proposons alors un cadre multi-expert dans
lequels les performances de notre mthode sont mesures selon plusieurs points de vue .
Nous montrons lintrt, selon chaque point de vue, des diffrents modules de lalgorithme
dorchestration : crossover, mutation, rparation des configurations initiales par CDCSolver,
maintien de la diversit par la mthode PADE.
159
160 CHAPITRE 11. TESTS DE PERFORMANCES
critre 2
Approximation A
Approximation B
cne de dominance
de l'approximation B
critre 1
le critre 2, alors que B est meilleur que A sur le critre 1. En outre, il existe une portion de
lespace des critres (le cne de dominance en gris) sur laquelle B domine totalement A, alors
que linverse nest pas vrai. Autrement dit, il existe un ensemble de fonctions scalarisantes de
Tchebycheff pour lesquelles les lments de B obtiennent une meilleure fitness que ceux de A.
Si en gnral deux approximations ne peuvent tre compares selon la dominance de Pareto,
on peut donc choisir de les considrer selon un point de vue particulier. Se concentrer sur
une rgion de lespace des critres peut constituer un tel point de vue. Comme nous aurons
loccasion de le voir, il en existe bien dautres. Cette approche est celle retenue par la plupart
des auteurs, qui en gnral ne font pas intervenir la dominance de Pareto (pour les raisons
voques ci-dessus) dans leurs processus dvaluation, mais proposent un certain nombre de
mesures de qualit .
Une mesure de qualit est une fonction M (le plus souvent unaire ou binaire) sur lensemble
des approximations, valeurs dans R. Elle saccompagne dune fonction dinterprtation, en
gnral implicite, permettant de dcider, en fonction des valeurs prises par M(A) et M(B)
(ou M(A, B) et M(B, A) dans le cas dune mesure binaire), si lapproximation A est meilleure
ou moins bonne que B. Lorsque le front de Pareto thorique est connu, on peut par exemple
utiliser la mtrique T (appele aussi generational distance) de Veldhuizen [vV99], qui renvoie
la moyenne des distances euclidiennes entre chaque point de lapproximation et le vrai front.
On rencontre de nombreuses mesures de qualit dans la littrature. Outre la mtrique T ,
les plus connues sont lerror ratio de Veldhuizen [vV99], les mtriques S (hypervolume) et
C (coverage) [ZT98b] [ZT98a] ainsi que lepsilon indicator [ZTL+ 03] de Zitzler et al., et les
indicateurs R1 , R2 et R3 de Hansen et Jaszkiewicz [HJ97]. Certaines dentre elles, que nous
utilisons dans notre processus dvaluation, seront dtailles la section suivante. Pour les
autres, nous renvoyons le lecteur aux travaux de Zitzler et al. [Zit99] [ZTL+ 03], Knowles et
al. [KFTZ05], Hansen et Jaszkiewicz [HJ97], Grosan [Gro05] ou encore Deb [DJ02].
Ziztler et al. [ZTL+ 03] ont rcemment propos un cadre formel pour lvaluation des m-
11.2. MESURES DE QUALIT RETENUES 161
critre 2
Approximation A
Approximation B
Front thorique
critre 1
Zitzle et al. [ZTL+ 03] ont montr que parmi toutes les mthodes dvaluation proposes
dans la littrature, seules deux mesures de qualit unaires et quatre mesures binaires per-
mettent de conclure la suprorit (au sens de Pareto) dune approximation sur une autre,
et ce dans un trs petit nombre de cas. Il faut donc tre extrmement prudent lors de leur
emploi. Lexemple de la figure 11.2 est frappant. Si les approximations sont compares selon
la distance au front thorique, alors B est incontestablement meilleure que A. Mais si on en
juge la diversit des solutions dans lespace des critres, alors A lemporte.
Lorsque deux approximations ne peuvent tre compares au sens de Pareto, il faut donc
les valuer selon plusieurs points de vue diffrents, afin de saisir prcisment en quoi elles
diffrent. En dautres termes, lvaluation des mthodes multicritres est aussi un problme
multicritre.
Point nadir
critre 2
Point idal
critre 1
11.2.1 Supriorit
Nous commenons par comparer les approximations selon la dominance au sens de Pa-
reto. Ce calcul est bas sur celui de lhypervolume H [Zit99], i.e. la partie de lespace des
critres domine par lapproximation (en gris sur la figure 11.3). Dans le cas gnral pour un
problme
max i de minimisation, H est le volume dlimit par lunion des polytopes de diagonale
x ; x , o xmax est le point nadir1 et xi un point de lapproximation. Lorsque lespace de
recherche nest pas connu, ces points sont estims par gnration alatoire dun grand nombre
de configurations (voir paragraphe 11.3).
Lorsque la dimension de lespace des critres est suprieure 2, le calcul de lhyper volume
peut devenir trs complexe, et ncessite alors le recours une mthode adapte. Lalgorithme
HSO (Hypervolume by Slicing Objectives) [WHBH06] est le plus courant.
En pratique, nous calculons lhypervolume binaire, qui consiste en la donne de deux
valeurs : H(A, B), la portion de lespace domine par A et non par B, et H(B, A), la portion de
lespace domine par B et non par A. Zitzler et al. [ZTL+ 03] ont montr que si H(A, B) > 0 et
H(B, A) = 0, alors A est meilleure que B, i.e. chaque lment de B est faiblement domin2 par
un lment de A, et A 6= B. Dans les cas o les deux approximations peuvent tre compares
1
Les coordonnes du point nadir sont les pires valeurs obtenues pour chacun des critres.
2
x domine faiblement y si et seulement si x y ou x = y.
11.2. MESURES DE QUALIT RETENUES 163
selon la dominance de Pareto, le calcul de lhypervolume binaire permet didentifier lequel des
deux ensembles est meilleur que lautre.
11.2.2 Pseudo-dominance
Dans bien des cas toutefois, les approximations sont incomparables au sens de Pareto (voir
section 11.1). Il nous faut alors convenir dune notion plus souple de la dominance. Sur la figure
11.1 par exemple, certains lments de B dominent des points de A, alors que linverse nest
pas vrai. Lapproximation B peut donc tre juge prfrable A, car il existe des situations
pour lesquelles B est meilleure (elles sont reprsentes par le cne de dominance en gris).
Nous dfinissons alors cinq prdicats P1 , P2 , P3 , P4 , P5 , exprimant diffrents points de
vue sur les relations de dominance entre les lments des approximations :
(P1 ) Binary epsilon indicator : (A, B) est le facteur unique par lequel il faudrait diviser
lensemble des valeurs de critres de A pour que A domine B au sens de Pareto. Zitzler
et al. donnent un algorithme efficace pour le calcul de dans [ZTL+ 03]. P1 (A, B) est
vrai si et seulement si (A, B) < (B, A).
(P2 ) Coverage : C(A, B) est le pourcentage dlments de B domins par A (voir par
exemple [ZT98b]). P2 (A, B) est vrai si et seulement si C(A, B) > C(B, A).
(P3 ) Binary R1 : Cette mesure introduite par Hansen et Jaszkiewicz [HJ97] value les
approximations laide dun ensemble de fonctions scalarisantes de Tchebycheff (voir
section 5.7). Etant donn un jeu de poids (i )1in , soient respectivement f (A, i ) et
f (B, i ) les meilleures valeurs de k ki obtenues sur respectivement A et B. R1 (A, B)
est alors gal au nombre fois o f (A, i ) < f (B, i ). P3 (A, B) est vrai si et seulement
si R1 (A, B) > R1 (B, A).
(P4 ) Binary R2 : De faon similaire, R2 est dfinie par :
n
1 X
R2 (A, B) = f (A, i ) f (B, i )
N
i=1
11.2.3 Convergence
Nous avons vu au chapitre 5 quune bonne mtaheuristique pour loptimisation multicritre
devait assurer la fois la convergence vers le front de Pareto thorique et la diversit des
solutions optimales. Nous proposons donc une mesure adquate pour chacun de ces aspects.
Nous mesurons la convergence vers la frontire efficiente laide de la mtrique T (gene-
rational distance) introduite au dbut de ce chapitre. T (A) est dfinie comme la moyenne des
distances euclidiennes entre chaque point de lapproximation A et le font thorique. Lorsque
ce dernier nest pas connu, on utilise un ensemble de rfrence obtenu par gnration alatoire
dun grand nombre de configurations (voir paragraphe 11.3).
Nous dirons que A atteint un meilleur niveau de convergence que B si et seulement si
T (A) < T (B).
164 CHAPITRE 11. TESTS DE PERFORMANCES
critre 2
Approximation A
Approximation B
Front thorique
critre 1
Fig. 11.4 Deux approximations obtenant les mmes valeurs de diversit pour la mesure de
Grosan
11.2.4 Diversit
Grosan a propos dans [Gro05] une mesure pertinente pour la diversit des solutions de lap-
proximation dans lespace des critres. Pour chaque point de lapproximation, on marque
le point du front thorique le plus proche au sens de la distance euclidienne. La diversit de
lapproximation peut alors tre estime par le pourcentage de points marqus dans le front
thorique.
Cette mthode intuitive et facile mettre en uvre possde un inconvnient majeur,
illustr par la figure 11.4. Bien que beaucoup plus diversifie, lapproximation A marque
exactement le mme nombre de points que B sur le front thorique. On peut corriger ce dfaut
en commenant par ramener lapproximation et le front thorique au mme nombre dlments.
Nous rduisons le plus grand des deux ensembles la taille du plus petit laide de la procdure
decrease_PADE introduite la section 9.4, puis calculons la diversit D propose par Grosan.
L encore, lorsque le front thorique nest pas connu, on utilise un ensemble de rfrence
obtenu par gnration alatoire dun grand nombre de configurations (voir paragraphe 11.3).
Nous dirons alors que A est au moins aussi diversifi que B si et seulement si D(A) D(B),
et vice versa.
Remarque 11.1. Dans le cas de problmes contraints, la question dune mesure de consis-
tance des solutions de lapproximation pourrait se poser. Les instances de test tant toutefois
faiblement contraintes, le hasard des oprations gntiques permet toujours, dans le cadre de
cette valuation, de dcouvrir des configurations consistantes, mme en labsence dune m-
11.3. PERFORMANCES DE LALGORITHME DORCHESTRATION 165
thode de rparation telle que CDCDSolver. Assurs que les approximations ne contiennent que
des solutions satisfaisant les contraintes, nous ne retenons donc pas de critre de consistance
dans notre valuation.
500 problmes polyphoniques non contraints, pour lesquels lespace de recherche est
inconnu.
Dans le reste de cette section, les diffrentes versions de lalgorithme sont toujours para-
pop pop pareto
mtres par les mmes valeurs4 : Ninit = 200, Nmax = 500, Nmate = 50 et Nmax = 100.
Le paramtre itermax est calcul de manire ce que le nombre dvaluations de fitness soit
toujours gal 20 000.
Dans la suite de cette section, cet algorithme sera simplement dsign par random .
Tab. 11.2 Performances dun algorithme gntique lmentaire par rapport une recherche
alatoire.
monophonique contraint monophonique libre
v.1.0 random v.1.0 random
Supriorit 18.40 % 2.04 % 8.79 % 1.23 %
Pseudo-dominance 84.25 % 15.75 % 61.15 % 38.85 %
Convergence 83.44 % 16.56 % 78.73 % 21.27 %
Diversit 69.12 % 84.25 % 25.15 % 78.32 %
polyphonique contraint polyphonique libre
v.1.0 random v.1.0 random
Supriorit 56.00 % 0.00 % 27.00 % 0.00 %
Pseudo-dominance 98.40 % 1.60 % 89.40 % 10.60 %
Convergence 95.20 % 4.80 % 98.00 % 2.00 %
Diversit 54.60 % 82.60 % 40.60 % 60.20 %
la procdure derease_PADE est remplace par une gestion nave de la population (lorsque
pop pop pop
la taille de celle-ci dpasse Nmax , on conserve uniquement les (Ninit +Nmax )/2 meilleures
configurations au sens de Deb).
En dautres termes, nous comparons au random un algorithme gntique lmentaire, que nous
dsignons par v.1.0 , dont les principales caractristiques sont :
des contraintes gres exclusivement par la dominance au sens de Deb (voir dfinition
6.1) ;
une slection par tournoi binaire (voir paragraphe 5.6) ;
une volution par crossover uniforme (voir dinition 9.1) ;
une gestion de la taille de la population par limination des plus mauvais individus au
sens de Deb.
Le tableau 11.2 rapporte les performances compares des algorithmes v.1.0 et random.
Sur les quatre types de problmes, les approximations retournes par v.1.0 dominent frquem-
ment (au sens de Pareto) celles dcouvertes par lalgorithme alatoire, et leurs performances
en termes de pseudo-dominance et de convergence sont crasantes, en particulier pour les pro-
blmes polyphoniques. Lintrt de lapproche gntique est patent : loprateur de crossover
uniforme permet bien damliorer itrativement la qualit des configurations.
Lorsquon compare toutefois les deux mthodes selon un critre de diversit, la supriorit
de lalgorithme gntique est moins vidente. Cependant, la capacit du hasard pur produire
des solutions trs diffrentes les unes des autres ne doit pas vraiment nous surprendre. Mais,
comme le montre la figure 11.5, cette diversit nest rien sans loptimalit : si les solutions
de lalgorithme alatoire sont en effet plus diversifies que celles de lalgorithme gntique,
en revanche ces dernires les dominent toutes au sens de Pareto. Il faut donc se mfier de la
mesure de diversit, et toujours linterprter en regard des autres critres.
En outre, rappelons quil est connu que sans mthode explicite de maintien de la diversit
(comme cest le cas pour v.1.0), un algorithme gntique tendance voluer vers une zone
particulire de lespace des critres, au dtriment des autres. Cest le phnomne de drive
gntique (ou genetic drift, voir paragraphe 5.5.4). La figure 11.5 en est un exemple. Elle
168 CHAPITRE 11. TESTS DE PERFORMANCES
critre 2
random
v.1.0
Front thorique
critre 1
montre quun petit nombre de solutions optimales est souvent prfrable un large ensemble
de configurations mdiocres.
Nous aurons loccasion de rediscuter des effets de lalatoire pur dans la suite de cette
section. Nous verrons en outre que sous couvert de diversit apparente, une trop grande part
dalatoire introduit en ralit du bruit dans le processus doptimisation.
Xinit :
pmute = P(z(x) = 0) , x Xinit
Pour les problmes libres, les versions v.1.2 et v.1.1 sont quivalentes. Nous ne comparons
donc v.1.2 et v.1.0 que sur les problmes contraints.
Le tableau 11.4 montre quen prsence de contraintes, la mutation alatoire nagit pas
comme un oprateur de diversification, mais permet dans certains cas de parvenir des ap-
proximations sensiblement meilleures, en termes de pseudo-dominance, que celles retournes
par la version v.1.0. La mutation agit donc ici comme un oprateur dintensification de la
recherche : lorsquelle nen dtriore pas la consistance, elle permet dans certains cas daffiner
la qualit des configurations.
Tab. 11.6 Pertinence de la rparation des solutions initiales pour les problmes contraints
Magr tout, la diversit des solutions de lapproximation est sans doute un critre privi-
lgier dans un cadre de cration musicale. Cest donc pour linstant la version v.4.0 qui est
implmente dans le prototype daide lorchestration qui fait lobjet de la dernire partie de
ce document.
Conclusion
Nous avons montr, travers un processus dvaluation multi-expert, que notre algorithme
dorchestration converge rapidement vers la frontire efficiente tout en maintenant la diversit
au sein de la population et parmi les solutions optimales. Au cours de cette valuation, les
paramtres de notre algorithme nont pas t modifis. On sait pourtant que loptimisation
par algorithmes gntiques demande une attention particulire dans le choix de paramtres
tels que la taille de la population et la taille du bassin de reproduction. Il conviendrait donc
de reprendre cette valuation avec diffrentes valeurs pour ces paramtres.
Gardons toutefois lesprit que le but ultime de notre mthode est avant tout de dcouvrir
une solution qui satisfasse les exigences esthtiques de lutilisateur. En garantissant lquilibre
entre convergence et diversit, on peut donc esprer identifier rapidement une configuration
pertinente, partir de laquelle la recherche peut tre intensifie par infrence des prfrences
172 CHAPITRE 11. TESTS DE PERFORMANCES
Laide lorchestration est aborde comme la recherche, au sein de grandes banques de sons
instrumentaux, de combinaisons dchantillons sapprochant le plus possible dun timbre cible.
Afin dune part de tenir compte du caractre multidimensionnel de la perception du timbre,
dautre part de traiter directement le problme combinatoire des mlanges, nous ramenons
lorchestration une tache doptimisation combinatoire multicritre sous contraintes.
La caractrisation des possibilits timbrales des instruments et de leurs alliages est aborde
travers un paradigme de description du signal. Lanalyse automatique de grandes banques
dchantillons sonores permet de condenser une connaissance synthtique du son instrumental
en un ensemble de descripteurs perceptifs, de prvoir les proprits acoustiques des mlanges
de timbre et dvaluer leur similarit avec un timbre cible selon plusieurs dimensions. A tra-
vers ce cadre formel, les combinaisons instrumentales ne sont plus identifies par les variables
de lcriture musicale, mais par un vecteur de distances perceptives, dans un espace o un
problme doptimisation multicritre peut tre pos. Nous montrons sur un ensemble de pro-
blmes de petite taille quune description spectro-harmonique du timbre permet de traiter
un ensemble consquent de cas dorchestration et prouvons que les solutions optimales du
problme doptimisation correspondent des configurations pertinentes dun point de vue
perceptif. Nous validons ainsi lapport des approches descriptive, multicritre et combinatoire
pour aborder la complexit de lorchestration.
Un algorithme gntique multicritre est introduit, dans lequel les propositions dorchestra-
tion sont reprsentes par des N -uplets dentiers, ce qui permet dignorer les contraintes lies
aux limitations de linstrumentarium utilis. Les configurations sont values laide de fonc-
tions scalarisantes de Tchebycheff poids alatoires, garantissant loptimisation simultane
de lensemble critres perceptifs. Une mthode destimation de la densit locale au sein de la
population assure en outre le maintien de sa diversit et empche une convergence prmature
vers une zone particulire de lespace des critres.
Un cadre thorique pour lexpression et la gestion de contraintes globales sur les variables
symboliques de lorchestration est galement propos. La dcouverte de solutions consistantes
est prise en charge par lheuristique de recherche locale CDCSolver, qui sappuie sur la dis-
tinction entre contraintes de design et containtes de conflit, et dont lefficacit est prouve sur
des problmes de petite taille. Dans certains cas, CDCSolver peut assurer, en complment de
lalgorithme gntique, une partie de loptimisation. Une intgration dans lalgorithme dor-
chestration pour la gestion de problmes contraints est propose, de manire rpartir quita-
blement le temps de calcul : CDCSolver intervient comme procdure de rparation tandis que
lvolution vers les configurations consistantes est encourage par une dominance de Pareto
tendue. Nous montrons enfin comment CDCSolver peut tre utilis pour des transformations
continues de timbre.
Les performances de lalgorithme dorchestration sont values dans un premier temps sur
173
un ensemble de problmes contraints de petite taille pour lesquels les fronts de Pareto tho-
riques sont connus, puis sur des instances plus consquentes pour lesquelles le front thorique
est estim par une approximation de rfrence. Un systme dvaluation multi-expert est pro-
pos pour comparer diffrentes versions de lalgorithme selon diffrents critres : dominance
faible, pseudo-dominance, convergence, diversit. Nous prouvons tout dabord la supriorit
dune version nave de lalgorithme par rapport une recherche purement alatoire, et justi-
fions lapport de la mutation gntique, de la rparation des configurations inconsistantes, et
du maintien de la diversit.
174
Troisime partie
175
Chapitre 12
Prototype actuel
Cette troisime partie est consacre au prototype doutil dorchestration, dvelopp par
nos soins en parallle de nos recherches. Le choix dun environnement de dveloppement sest
rapidement port sur Matlab
c
, pour au moins quatre raisons majeures :
1. Matlab
c
est un langage multi-plateforme. Le prototype est donc facilement portable
et utilisable par des compositeurs ne travaillant pas ncessairement sur des machines
AppleTM .
2. Matlab
c
est un langage interprt. La modification de certains lments du projet
nimpose donc pas de recompiler lensemble.
3. Nos recherches ont t menes paralllement la thse de Damien Tardieu, doctorant
dans lquipe Analyse-synthse des sons lIRCAM et collaborant avec nous sur laide
lorchestration. Les travaux de ce dernier ont port sur la caractrisation du timbre
instrumental laide de descripteurs du signal audio (voir section 2.6) et de llaboration
de modles dinstruments (voir section 7.1.2 et [TR07]). Or, Matlab
c
est un outil de
rfrence en traitement du signal. Afin de favoriser la communication et linteroprabilit
de nos recherches, il tait donc prfrable de travailler dans le mme environnement.
4. Si Matlab
c
est majoritairement utilis pour le calcul numrique, il sagit galement
dun outil de dveloppement pratique et puissant pour le prototypage, notamment pour
la conception dinterfaces graphiques.
12.1 Architecture
Notre outil daide lorchestration rpond au schma gnral de la figure 12.1. La connais-
sance instrumentale y est reprsente par la base de donnes de descripteurs et dattributs
obtenus respectivement par extraction automatique et indexation manuelle du signal audio,
partir des chantillons de SOL [BBHL99], la banque de sons instrumentaux enregistre
lIRCAM (voir paragraphe 7.1.2).
La notion de cible orchestrer a t introduite au paragraphe 7.1.1. Elle est donne en
entre par le compositeur, par le biais dun son enregistr dans le cas dune orchestration
177
178 CHAPITRE 12. PROTOTYPE ACTUEL
Compositeur
Construction
Orchestre Contraintes
de la cible
EXPORT :
Exploration / - Partition
DB Algorithme d'orchestration
dtion des - MIDI
(desc.) [+ Solveur de contraintes]
solutions - Texte
- Son
DB Simulation
(sons)
Donnes symboliques
Signal audio
imitative ou dun son de synthse pour une orchestration gnrative. Le compositeur doit en
outre prciser la composition de lorchestre quil utilise, et est libre de spcifier un ensemble
de contraintes supplmentaires sur les attributs des solutions quil souhaite obtenir (voir sec-
tion 7.5 et chapitre 10).
Lalgorithme dorchestration, que nous avons prsent au chapitre 9, va alors chercher selon
les critres de timbres proposs en 8.1.2 un ensemble de configurations efficientes, en optimisant
les distances entre leurs descripteurs et ceux de la cible. Au cours de cette recherche, un solveur
de contraintes (voir chapitre 10) sassure que les configurations proposes sont consistantes
avec le rseau de contraintes dfinies par le compositeur.
Une fois la recherche termine, une interface de navigation permet au compositeur dex-
plorer lensemble des configurations efficientes trouves par le systme, selon plusieurs points
de vue. Espaces de dcisions, espace des descripteurs et espace de critres (voir section 7.6)
sont simultanment accessibles lutilisateur, et ce de faon croise (les dplacements dans un
espace se propageant dans les deux autres). Coupl cette interface, un chantillonneur per-
met, grce aux chantillons instrumentaux de la base de donnes, de simuler les propositions
dorchestration.
Linterface de navigation incorpore les mcanismes dinfrence des prfrences de lutili-
sateur introduits la section 7.2.4. Le compositeur a la possibilit de relancer la recherche
partir dune solution intermdaire ; dans ce cas, le systme privilgie la combinaison de cri-
tres qui a implicitement prsid au choix de cette solution. Tout se passe donc comme si la
recherche sintensifiait dans son voisinage. Lutilisateur peut galement diter manuellement
les solutions, ainsi que les transformer par ajout de contraintes suppmentaires.
La figure 12.1 montre que le signal audio intervient de faon privilgie dans la communi-
cation entre le compositeur et loutil dorchestration, que ce soit au niveau de la construction
de la cible ou de lexploration des solutions. Ce primat du sonore permet dviter le recours
un vocabulaire peu prcis pour la caractrisation du timbre, et de se cantoner aux symboles
usuels de lcriture musicale (hauteurs, intensits, mode de jeu,. . .). De plus amples dtails sur
linteraction avec loutil seront donns au chapitre 13.
Construction de
Analyse d'un son
cible abstraite
OSC Mapping des
(orchestration
fondamentales
gnrative)
OSC
Construction /
Extraction des dition de cible
partiels principaux SDIF concrte
(pm2) (orchestration
imitative)
Recherche Connaissance
d'orchestrations instrumentale
Exploration /
transformation
Sampler
des solutions
d'orchestrations
OSC
Echantillons
OSC Editeur
Fig. 12.2 Prototype daide lorchestration : espace disque et outils existants ncessaires.
Les communications internes sont en pointills ; celles par fichier ou par OSC sont en traits
pleins.
Nous sommes aujourdhui loin de cette encapsulation idale des technologies. Nous ne
pouvons pas mme dire si, dans sa version finale, loutil dorchestration sera un programme
part entire (standalone), un plug-in , ou une bibliothque (mais dans quel langage ?) dans
lenvironnement de CAO OpenMusic [Ago98]. En vrit, nous pensons quil faut dabord en
passer par une phase consquente dexprimentation auprs des compositeurs avant de dcider
dune architecture finale et dune stratgie de dveloppement ; car ces dernires devront tre
suffisamment souples et visionnaires pour intgrer les rsultats de recherches futures.
En attendant, nous tirons parti des technologies existantes et implmentons, de ma-
nire rapide et sre, les modules satellites de notre outil au sein denvironnements tels
quOpenMusic ou Max/MSP [Puc91]. Quant Matlab
c
, nous y rservons le cur de
notre recherche : optimisation combinatoire multicritre (chapitre 9), gestion des contraintes
(chapitre 10), et interfaces de navigation dans les propositions dorchestration (chapitre 13).
Mais l o OpenMusic permet, travers des structures de donnes complexes, un haut niveau
dexpressivit pour la programmation, Max/MSP propose un langage plus pauvre, mais dune
trs grande efficacit pour le contrle et le traitement du signal en temps rel. OpenMusic
est donc prfr pour la composition, tandis que Max/MSP est utilis avant tout dans des
contextes performatifs.
En ce qui nous concerne, Max/MSP sest naturellement impos pour la conception des
interfaces dans lesquelles circulent des flux audio : analyse du son cible, simulation des propo-
sitions dorchestration (sampler ), dition des solutions. Dans les deux derniers cas, la difficult
est de dclencher la lecture simultane de plusieurs chantillons de la base de sons. Cet ordre
peut tre pass aussi bien depuis Matlab
c
que Max/MSP, et la lecture doit commencer
aussitt aprs, sans quoi linteraction avec le compositeur travers une coute des proposi-
tions dorchestration nest pas possible. La rapidit de Max/MSP en termes daccs disque et
de chargement des buffers audio et sa grande facilit dutilisation (due au paradigme de pro-
grammation visuelle) permettent de satisfaire ces exigences tout en conomisant de fastidieuses
heures de dveloppement. Par ailleurs laspect modulaire de Max/MSP permet dimaginer un
certain nombre de traitements possibles (individuels ou collectifs) sur les chantillons impliqus
dans une orchestration : modification continue de paramtres de jeu (intensit, hauteur. . .),
modulations (vibratos, tremolos. . .), dplacements dans lespace ( laide du spatialisateur
Spat [Jot97] par exemple). Ces mouvements permettent, travers un processus interactif
dessais/erreurs, de crer des timbres dynamiques ; ils correspondent des paramtres tradi-
tionnels de lcriture musicale. Dautres traitements sont galement envisageables, si le son
des chantillons est pens comme une matire . A linstar du compositeur Grard Buquet
(voir section 14.5), on peut en effet utiliser laide lorchestration comme un environnement
de production sonore.
La souplesse et la rapidit dans la gestion des flux audio ne sont pas les seules raisons du
choix de Max/MSP. Cet environnement comporte galement un certain nombre d objets
prdfinis, tels que le clavier de piano ou la reprsentation dun accord sous forme de partition,
qui permettent dagir de faon rapide et intuitive sur le paramtrage dune orchestration. Ces
lments sont particulirement utiles pour le mapping de fondamentales opration qui
consiste expliquer le spectre de la cible par un ensemble de spectres harmoniques (pour
plus de dtails, voir sections 13.1 et A).
Les communications entre Matlab
c
et Max/MSP se font par change de fichiers tem-
poraires ou par messages OSC (OpenSound Control ) [WFM03]. Dvelopp au CNMAT1 , OSC
est un protocole de communication entre ordinateurs, synthtiseurs et contrleurs multimdia,
bas sur la norme UDP2 et optimis pour les technologies organises en rseaux.
Nous avons insist au paragraphe 7.1.1 sur la ncessit de trouver une alternative lorches-
tration imitative, dans laquelle le timbre cible est donn par le compositeur sous forme dun
son enregistr. Nous avons propos pour cela le concept dorchestration gnrative : partir
dun matriau musical symbolique (un accord par exemple), le compositeur va gnrer un son
de synthse dont les caractristiques sont dtermines par des paramtres de haut niveau.
Modifiable souhait jusqu lobtention dun timbre satisfaisant, ce son est alors considr
comme la cible dun problme dorchestration imitative. Dun point de vue formel, il sagit
dune abstraction : lisse et froid, ce son de synthse est un portrait-robot qui cristallise les
proprits acoustiques du timbre recherch. Face la difficult de caractriser verbalement le
1
Center for New Music and Audio Technology, Universit de Californie, Berkeley.
2
User Datagram Protocol.
182 CHAPITRE 12. PROTOTYPE ACTUEL
Fig. 12.3 Construction dune cible dans OpenMusic laide de paramtres exclusivement
symboliques (orchestration gnrative).
timbre (voir chapitre 2 et section 7.1.1), cest encore le moyen de sentendre sur une ide de
timbre .
Cette piste de travail a t explore en parallle de nos travaux, en collaboration avec
Jean Bresson, chercheur lIRCAM dans lquipe Reprsentations musicales, et en charge
notamment du dveloppement dOpenMusic. OpenMusic (OM) est un environnement de
CAO bas sur la programmation visuelle et dot dun haut niveau dexpressivit. Il permet
la mise en relation dobjets musicaux (symboliques ou concrets) au travers dun ensemble de
botes interconnectes au sein dun patch , et formalisant un processus compositionnel
(voir la figure 14.2 pour un exemple de patch OM).
Un objet sound-target (voir figure 12.3) a donc t implment dans OM : il prend en
entre un accord (objet chord) et propose un ensemble doutils pour sa spectralisation :
chaque note est assortie dun spectre dont les caractristiques (enveloppe, inharmonicit, fr-
quences et amplitudes des partiels. . .) sont aisment ditables. Un spectre complexe peut ainsi
tre construit, puis affin par un filtre global avant dtre rendu par un moteur de synthse
additive dans CSound [Bou00]. Le compositeur peut ainsi construire le timbre recherch
travers un processus itratif. Une fois satisfait, le son cible est envoy au systme daide
lorchestration par un message OSC.
Lextraction des descripteurs du son cible se fait dune part grce au programme ircamdes-
criptor de Geoffroy Peeters [Pee04] (dvelopp en Matlab
c
), dautre pat via la commande
pm2 [Rod97] qui sert en partie de noyau au logiciel AudioSculpt [BR05]. Dans ltat actuel
12.3. CONSIDRATIONS SUR LES LIMITES ACTUELLES 183
des choses, lutilisateur a donc galement besoin dune licence pour pm2. Les rsultats de cette
analyse sont imports dans Matlab
c
sous forme dun fichier SDIF3 [SW00].
En dernier lieu, notons que si la connaissance instrumentale (voir section 7.1.2) est stocke
dans une structure de donnes dont la taille avoisine les 10 mgaoctets, en revanche lensemble
des chantillons instrumentaux ncessaires aux simulations dorchestration occupe aujourdhui
un espace mmoire de plusieurs gigaoctets, et ce pour une reprsentativit seulement partielle
des possibilits instrumentales (voir paragraphe 8.1.1).
Il est vident que la simulation par lecture de simples fichiers son nest pas extensible
linfini. Deux solutions soffrent alors nous :
1. Ne retenir quun chantillon par zone de hauteur et de dynamique o le timbre varie peu,
et recourir la vole des techniques de transposition et dajustement de volume.
Cest la stratgie adopte par la plupart des samplers.
2. Dvelopper un moteur de synthse instrumentale puissant et raliste, mais cela sort to-
talement de notre domaine de comptences. Il serait alors plus raisonnable de convenir
dun format standard de donnes (de type MIDI4 ) grce auquel les propositions dor-
chestrations pourraient tre interprts par un environnement de synthse existant,
quoique la gnricit dun tel format na rien dvident. Cette question reste aujourdhui
en suspens. . .
Tous les sons de la base de donnes constituant la connaissance instrumentale sont harmo-
niques et monophoniques. Lextraction des principaux partiels rsolus de la cible permet de
dduire la contribution de chaque son de la base un spectre simplifi , et cette contribution
se fait actuellement par le prisme de la hauteur (voir section A en annexe). Dans notre sys-
tme daide lorchestration, la hauteur est donc implicitement considre comme un attribut
privilgi, alors quune part significative de la musique contemporaine prtend au contraire
sen affranchir.
Peut-il en tre autrement ? Le problme, lorsquil sagit dvaluer le rle du timbre en
soi, est que, pour la plupart des musiques occidentales dont limportance esthtique est avre,
lutilisation du timbre est largement subordonne aux structures de hauteurs et de rythmes.
(McAdams & Saariaho, Qualits et fonctions du timbre musical, in [Bar85]). Erickson [Eri75]
confirme ce point du vue, et va jusqu douter quon puisse se passer de la hauteur : La
hauteur complique normment la situation, et il nest pas sr que lon puisse envisager des
situations o elle nintervienne pas de faon significative.
En se tournant vers le timbre (voir chapitre 2), la pense musicale a certes tempr limpor-
tance de hauteur, mais ne la pas radique pour autant. Lcriture base sur une organisation
des hauteurs a perdur avec la musique spectrale, dans laquelle le timbre est majoritairement
considr comme une agrgation fusionne de hauteurs. Dautre part, lutilisation massive de
la transforme de Fourrier, qui permet de dcomposer le son en une somme de hauteurs l-
mentaires, a trs certainement contribu au maintien du primat de la hauteur. Notre outil
dorchestration, en partant de lanalyse dun son cible et en tentant de lapprocher laide
dune mixture de sons monophoniques ne cautionne-t-il pas cette supriorit de la hauteur, et
ne favorise-t-il pas une approche spectrale de lorchestration ?
Au dbut de notre thse, les techniques lies aux descripteurs spectro-harmoniques du si-
gnal taient dj suffisamment matures pour quun modle spectral du timbre instrumental,
la fois descriptif et prdictif, puisse tre rapidement dvelopp. Nos premiers travaux [CTA+ 06]
ont ainsi concern limitation dun instrument de lorchestre par un petit groupe de deux ou
trois instruments. Lanalyse spectrale et la dcomposition harmonique de la cible travers les
MRP (voir paragraphe 8.1.2 et annexe A) procdaient de cette dmarche initiale. Dans un
second temps seulement fut-il question de problmes plus gnraux, que nous avons dlibr-
ment choisi daborder avec la mme description. Les composantes transitoires ou bruites du
timbre tant beaucoup plus dlicates modliser, il tait normal que la recherche sur laide
lorchestration se concentre dans un premier temps sur des problmes spectraux, sans jamais
cependant les traiter comme une finalit, mais comme un moyen la fois dprouver notre
approche combinatoire de lorchestration et de valider nos stratgies doptimisation bases sur
une conception descriptive du timbre.
Cette vision de lorchestration, dans laquelle le timbre comme objet danalyse induit une
organisation des hauteurs, sapparente fort la dmarche du mouvement spectral. Bien que
nayant jamais affich la volont de privilgier une esthtique musicale particulire, il est
invitable que dans les premiers temps de son mergence une technologie favorise certaines
pratiques. L o certains pourraient donc dnoncer une drive ou une focalisation esthtique,
nous prfrons y voir un point dentre vers la complexit de lorchestration. Notre recherche
nest en rien confine dans le spectralisme, mais lapproche analytique de cette dmarche la
rendue plus permable une pense scientifique qui saventurait en terre inconnue.
12.3. CONSIDRATIONS SUR LES LIMITES ACTUELLES 185
ne par lutilisateur. Une telle solution na rien dvident mettre en uvre, car lintensit
perceptive est une donne minemment subjective. En outre, elle ne rsout pas le problme
des sons lectroniques, pour lesquels la notion de dynamique au sens dune intention de
compositeur laisse lapprciation des interprtes nexiste pas vraiment.
188 CHAPITRE 12. PROTOTYPE ACTUEL
Chapitre 13
Scnario dutilisation
189
190 CHAPITRE 13. SCNARIO DUTILISATION
1. Dfinir manuellement les hauteurs possibles. Un systme de claviers (le second est un
quart de ton plus haut que le premier) est prvu cet effet dans la partie infrieure du
patch Max/MSP.
2. Dduire automatiquement des frquences de partiels les hauteurs fondamentales sus-
ceptibles de les expliquer. Cette mthode t prsente dans [CTA+ 06] et donne de
bons rsultats lorsque le son cible est harmonique ou une mixture de sons harmoniques.
Elle prend toutefois en argument des paramtres dpendant du problme et en gnral
dlicats fixer.
3. Convertir les frquences des partiels en hauteurs de note par approximation au quart de
ton le plus proche : cest la technique habituelle des compositeurs spectraux , et la
mthode par dfaut dans notre systme.
Dans les deux derniers cas, lutilisateur a videmment la possibilit dditer manuellement les
hauteurs suggres par le systme. Cest dailleurs ce que nous avons fait en rajoutant la note
E2 (voir figure 13.1), trs prsente lcoute, mais dont la frquence nappartient pas aux
principaux partiels rsolus (MRP).
Suite cette tape, seuls les sons dont la hauteur appartient lensemble prcdemment
construit pourront figurer dans les propositions dorchestration. Avant de lancer la recherche,
la connaissance instrumentale est donc filtre selon lattribut hauteur , et la contribution
aux MRP de chacun des candidats est calcule selon la mthode expose en annexe A. Les
contributions sont calcules par groupes de mme hauteur : ce que nous avons appel en infra le
mapping des fondamentales consiste projeter chaque hauteur prcdemment slectionne
sur les MRP de la cible. En pratique, nous associons chaque hauteur un peigne harmonique
thorique (sans inharmonicit1 ) et nous identifions les harmoniques dont la frquence concide
( une erreur relative prs) avec un partiel de la cible. La fentre de droite de la figure 13.1
illustre cette mise en correspondance. Tous les sons de hauteur Mi2 (premire srie rouge)
contribuent aux MRP numros 2, 4, 6, 8, 9, 11, 12, 13, 16, 17, 20, 21, 24, 25 de la cible. Tous
les sons de hauteur Si2 (premire srie verte) contribuent aux MRP numros 1, 2, 3, 6, 11, 17,
19, 21, 24, 25 de la cible, etc. Un son de hauteur Sol#6 haut ne contribue quau 24e MRP, un
son de hauteur Mi7 au 25e . Il y a contribution si lerreur relative entre la frquence thorique
de lharmonique et la frquence dun MRP est infrieure un certain seuil, modifiable par
lutilisateur.
A la fin de ce processus, qui pour certaines cibles peut tre assez long, les descripteurs de
la cible ont t extraits, la banque de sons filtre selon les hauteurs et les contributions aux
MRP de la cible calcules pour chaque son candidat. La recherche dorchestrations peut alors
commencer. Cette tape, qui constitue lessentiel de notre travail, nest pas dcrite ici. Nous
renvoyons pour cela le lecteur au chapitre 9.
La fentre en haut gauche sur la figure 13.2 reprsente le rsultat dun clustering par
schmas sur les hauteurs de note. Les solutions sont reprsentes en bas de larbre par des
cercles. Les schmas apparaissent sous formes de petits carrs, et leur hauteur dans larbre
correspond leur niveau dabstraction : le schma slectionn (sous-arbre rouge) est situ deux
niveaux au dessus des solutions et comporte deux fois le symbole . Toutes les configurations
de ce cluster ont donc dix caractristiques communes : la clarinette joue toujours un La5#
haut, le basson un Fa#4, la trompette un Mi5, etc. Le second violon ne joue jamais. Ce qui
diffrencie les solutions au sein du groupe sont les hauteurs joues par le violoncelle et le
13.3. EDITION, AFFINAGE, TRANSFORMATION 195
premier violon. Le schma associ au nud courant est reprsent dans la partie droite de la
fentre. Chaque cluster est reprsent par la solution qui minimise la somme des distances aux
autres membres du groupe dans lespace des critres normaliss. Cest ce reprsentant qui est
envoy dans la fentre de solution courante et jou dans le sampler.
La solution ainsi obtenue va alors pouvoir tre insre dans un mouvement orchestral
dvelopp et contrl laide de contraintes supplmentaires. Lalgorithme CDCSolver pr-
sent au chapitre 10 possde la particularit de ne modifier quune seule coordonne la fois
au cours de la rsolution. Il est donc possible, en partant dune solution initiale et dun rseau
de contraintes, de transformer continument cette solution pour parvenir un autre timbre.
L enregistrement de lvolution se fait en conservant la trace de lalgorithme de rsolution.
Celle-ci se prsente alors comme une suite de configurations dans laquelle un seul instrument
est modifi chaque tape. Rappelons que lalgorithme de rsolution de contraintes utilis dans
ce cas par opposition la procdure de rparation des configuration initiales (voir chapitre
10) incorpore des notions doptimisation. Lors du mouvement vers une configuration voi-
sine, le niveau de violation des contraintes ainsi que la fitness selon la fonction scalarisante
en cours (voir section 5.7) sont simultanment considrs travers la notion de dominance
au sens de Deb (voir dfinition 6.1). Lvolution se fait donc de manire certes amliorer
13.3. EDITION, AFFINAGE, TRANSFORMATION 197
Fig. 13.6 Partition finale dune lorchestration imitative et volutive. A chaque mesure, seul
un lment est modifi. Partition en Ut.
200 CHAPITRE 13. SCNARIO DUTILISATION
Chapitre 14
Exemples et productions
Nous reportons dans ce chapitre des exemples probants dorchestration obtenus laide
de notre systme. Dans le premier, la cible est un son concret pr-enregistr ; dans le second
lenvironnement de CAO OpenMusic a t utilis pour gnrer un son cible partir dun
accord crit. Le troisime est une requte du compositeur Oscar Bianchi. Il sagit dun timbre
dynamique dont seule la premire partie est orchestre avec notre systme, en spcifiant des
contraintes qui permettent de dduire la seconde partie. Le quatrime exemple rsulte
dune collaboration avec le compositeur Jonathan Harvey. La encore, des contraintes sont
utilises pour le contrle temporel du timbre, mais lensemble du mouvement est gouvern
par une fonction objectif globale traduisant une intention prcise du compositeur. Enfin, le
dernier exemple est tir dun travail rcent avec le compositeur Grard Buquet, dans lequel
loutil dorchestration est utilis comme un environnement de production sonore. Tous ces
exemples peuvent tre couts en ligne sur le site : http://recherche.ircam.fr/equipes/repmus/
carpentier/phdsounds/.
201
202 CHAPITRE 14. EXEMPLES ET PRODUCTIONS
Fig. 14.1 Deux orchestrations dun mme son de klaxon (en haut avec un ensemble de
cuivres, en bas avec un ensemble de cordes). Partition un Ut.
14.2. UNE CIBLE CONSTRUITE DANS OPENMUSIC (TRISTAN MURAIL) 203
Fig. 14.2 Un patch dans OpenMusic gnrant une cible partir dun accord
G#4
D4
B4+
D4
A#3
C#3
G2
Fig. 14.3 Orchestration dun son de synthse gnr partir dun accord dans OpenMusic
(les notes en rouge font partie de laccord initial). Partition en Ut.
initial sont prsentes, compltes par deux sons de hauteur R4, troisime harmonique de
Sol2. Lorchestration rsultante possde les mmes caractristiques harmoniques que le son de
synthse, auxquelles sajoutent la richesse des petites variations du timbre instrumental.
aeol+ord aeol+ord
Fl & c #w #w
Cl &c
#w #w
harm-fngr harm-fngr
Bn
?c
p p
Hn & c #w #w
F F
+ + o
wah-wah wah-wah
Tp & c #w #w
F
+ + o
wah-wah wah-wah
Tb
? c #w #w
F
?c
pdl-tone pdl-tone
Tb
#w #w
f F
o
?c + +
wah-wah wah-wah
Tb
#w #w
F
& c #w
sordina sordina
Vn #w
#w #w
sordina sordina
Va Bc
?c
Vc
#w #w
F F
Cb
?c
#w #w
F
Solution initiale (statique) Solution rcrite (dynamique)
Fig. 14.5 Orchestration dun timbre dynamique par propagation dun timbre statique.
Partition en Ut.
14.4. SPEAKINGS (JONATHAN HARVEY) 207
t entirement crite laide de loutil dorchestration partir dun mantra chant par le
compositeur (voir figure 14.6).
Jonathan Harvey souhaitait que le motif de la figure 14.6 soit rpt 22 fois, non pas
lidentique, mais en respectant les directions dvolution suivantes :
1. La dynamique de lostinato doit aller crescendo au cours des 22 rptitions.
2. Le son de lorchestre doit devenir de plus en plus brillant, et se rapprocher de plus en
plus du timbre des voyelles chantes.
3. Les orchestrations doivent utiliser des hauteurs de plus en plus leves (harmoniques des
notes fondamentales chantes), et composer des accords de densit harmonique (nombre
de hauteurs diffrentes) croissante.
Loutil dorchestration ntant pas directement utilisable pour traiter ce problme, nous avons
donc procd de la manire suivante :
1. Le sous-orchestre mobilis pour jouer lostinato tant compos de 13 musiciens, au
plus 13 notes sont jouables simultanment. Pour chaque voyelle chante, nous avons donc
gnr 13 ensembles de 10 solutions chacun, avec pour le k-ime ensemble, la contrainte
davoir au moins k hauteurs diffrentes dans les propositions dorchestration.
2. Pour chaque voyelle chante, nous avons donc obtenu 130 solutions de timbres varies,
pour lesquelles nous avons calcul plusieurs descripteurs : Intensit perceptive, centrode
spectral, MRP (voir section 8.1.2 et annexe A), nombre de sons utiliss, densit harmo-
nique, hauteur maximale.
3. Pour chaque voyelle, nous avons enfin utilis un algorithme de recherche locale pour
trouver un chemin reliant 22 solutions parmi 130, de telle manire que les valeurs
des descripteurs ci-dessus soient des fonctions croissantes du temps.
Un extrait de la solution totale calcule par cette procdure est reproduit sur la figure
14.7, et la partition finale de ce passage est donne figure 14.8 (les parties crites laide du
systme dorchestration sont surlignes en rose). Dans lensemble, lorchestration suggre par
le systme t conserve par le compositeur, quelques modifications prs. Ces dernires
concernent essentiellement la conduite des voix, cest--dire la cohrence interne de chaque
partie, dans son dveloppement horizontal, mlodique . Notre outil dorchestration na en
effet pour linstant quune vision verticale, harmonique , de la texture. En outre, labsence
de contraintes dexcution dans notre modlisation engendre immanquablement des enchane-
ments irralisables. Par exemple, le trompettiste qui veut scrupuleusement suivre la partition
de la figure 14.7 doit changer de sourdine au milieu de la 13e mesure, lenlever sur le premier
temps de la 14e , puis en changer encore deux fois sur les deux temps suivants. Cest videm-
ment parfaitement impossible, et le compositeur a choisi de garder la mme sourdine pour le
passage entier.
Une autre diffrence remarquable est la disparition aux cordes des legno-tratto , mode
de jeu contemporain qui consiste jouer avec le bois de larchet au lieu de la mche. Le son
208 CHAPITRE 14. EXEMPLES ET PRODUCTIONS
13 14
!
Fl
)&"1!"#$ )&"1!"#$ )&"1!"#$ )&"1!"#$ )&"1!"#$
pp mf pp mf ff ff
Ob
*)#,!9'2# *)#,!9'2# *)#,!9'2#
pp p pp p p
!
Cl
)&"1!"#$
)&"1!"#$
mf mf pp mf pp pp
Hn
:+"%%&$
mf ff mf ff mf mf
Tp
Vn
)#+!*)#,-.-/0 1&2'"!+#)++"-.-30 1&2'"!+#)++"-.-30 )#+!*)#,-.-40
1&2'"!+#)++"-.-/0
1&2'"!+#)++"-.-40
mf mf mf mf mf mf
Vn
1&2'"!+#)++"-.-30 1&2'"!+#)++"-.-30 '"'567-.-30 1&2'"!+#)++"-.-30 1&2'"!+#)++"-.-30 '"'567-.-/0
8"#$6')!%6",7" 8"#$6')
mf mf mf mf mf pp
Vn
1&2'"!+#)++"-.-30
mf
Va
)#+!*)#,-.-;0 1&2'"!+#)++"-.-30 )#+!*)#,-.-30 )#+!*)#,-.-/0
1&2'"!+#)++"-.-40 +):+"-.-;0
mf mf mf mf mf mf
Va
Vc
'"'567-.-40 '"'567-.-40 '"'567-.-40 )#+!*)#,-.-30 )#+!*)#,-.-30 +):+"-.-40
mf mf ff mf mf mf
Vc
'"'567-.-/0 '"'567-.-/0 '"'567-.-40 '"'567-.-/0 '"'567-.-/0 '"'567-.-40
8"#$6') 8"#$6')!%6",7" 8"#$6') 8"#$6') 8"#$6') 8"#$6')
mf mf ff ff ff ff
Cb
'"'567-.-/0 '"'567-.-;0
'"'567-.-40 '"'567-.-40 '"'567-.-40 '"'567-.-40
ff mf mf ff ff ff
Fig. 14.7 Mesures 11 et 12 dune orchestration de mantra (ostinato) pour la pice Speakings
de Jonathan Harvey. Partition en Ut.
14.4. SPEAKINGS (JONATHAN HARVEY) 209
qui en rsulte est de trs faible intensit, avec une forte composante bruite. Si les tratto
sont frquents dans le jeu en solo ou en petit ensemble, ils sont plus difficiles utiliser dans
un contexte orchestral o ils risquent dtre masqus par dautres instruments.
En revanche, les changements de dynamique (qui surviennent presque chaque note)
ont t majoritairement conservs par le compositeur avec, en dbut de passage, une note
lattention du chef dorchestre : Great care to respect the dynamics. Loutil dorchestration
a donc ici t dun grand secours pour parvenir un ajustement prcis des intensits.
Cet exemple est pour nous le signe dune double russite. Tout dabord, il prouve que
loutil dorchestration, bien quayant dans un premier temps t conu pour produire des
timbres statiques, peut, laide dun systme de contraintes adquat, tre utilis pour contrler
lvolution temporelle du timbre. En second lieu, il a suscit lintrt et lenthousiasme dun
compositeur mrite, peu familier des outils technologiques, et dont les talents dorchestrateur
sont avrs et reconnus depuis longtemps. Cette collaboration aura permis de parcourir toutes
les tapes de la cration musicale, de lide du compositeur lexcution en concert : Speakings
a t cr le 19 aot 2008 au Royal Albert Hall de Londres, interprt par le BBC Scottish
Symphony Orchestra, dirig par Ilan Volkov.
transposes au cours du temps, avec un rapport diffrent pour chaque son. On obtient ainsi
une texture qui s tire peu peu, la frontires des mondes acoustique et lectronique.
212 CHAPITRE 14. EXEMPLES ET PRODUCTIONS
Rsum de la troisime partie
213
214
Conclusion
215
Synthse
En abordant le problme de laide lorchestration, nous nous sommes pos la question
de la complexit de cette pratique. Comment penser cette complexit ? Comment concevoir
des formalismes qui la traduisent et lexpriment au mieux, sans la rduire un modle sim-
plificateur ? En quoi un outil informatique peut-il aider les compositeurs faire face cette
complexit ? Telles sont les questions qui ont anim ce travail de thse.
Nous avons montr que la complexit de lorchestration tait multiple, quelle se situait la
rencontre de plusieurs axes, plusieurs faisceaux de complexit : complexit de la perception
du timbre, complexit combinatoire des mlanges instrumentaux, complexit de nos rapports
aux structures temporelles en musique. Pour chacun dentre eux, nous avons propos des
formalismes et des mthodes adapts.
Le caractre multidimensionnel du timbre a t trait travers une approche descriptive.
Lextraction automatique de descripteurs perceptifs dans de grandes banques dchantillons
sonores a permis daboutir un modle robuste du timbre instrumental, capable de prdire les
proprits acoustiques des mlanges. Nous avons ensuite propos un algorithme de recherche
dorchestrations fond sur des mtaheuristiques doptimisation multicritre. Une recherche
interactive et supervise permet la dcouverte simultane dorchestrations pertinentes et des
dimensions privilgies de lcoute pour un problme donn. Nous avons enfin montr que
la contextualisation des orchestrations dans un processus compositionnel plus gnral tait
possible laide de contraintes sur les variables symboliques de lcriture, et que cette approche
permettait en outre daborder le problme du temps.
Notre travail va donc bien au del des potentialits des quelques outils actuels daide
lorchestration. Il permet linformatique musicale daborder pleinement une discipline de
lcriture qui jusqualors stait toujours soustraite la formalisation, et laisse entrevoir la
possibilit dune comprhension plus fine des rapports entre deux mondes htrognes, celui
de la partition comme systme symbolique et celui du timbre comme ralit sonore.
Nous disposons donc aujourdhui dun prototype daide lorchestration capable de propo-
ser rapidement au compositeur un ensemble diversifi dorchestrations pour un timbre statique
donn en entre, et den contrler lvolution temporelle laide dun systme de contraintes.
Que cet outil fut plusieurs reprises utilis avec enthousiasme et succs par des composi-
teurs renomms dans leurs crations rcentes constitue, au del de notre apport scientifique,
la preuve tangible dune avance significative.
217
un algorithme volutionnaire doptimisation combinatoire multicritre adapt au pro-
blme de lorchestration, respectant lquilibre entre intensification et diversification de
la recherche et pouvant tenir compte des prfrences de lutilisateur.
une gnralisation des notions dinstanciation partielle et de consistance locale dans les
problmes de satisfaction de contraintes, travers les concepts de contraintes de design
et contraintes de conflit ;
une mtaheuristique de recherche locale pour la satisfaction de contraintes globales,
sappuyant sur la distinction entre contraintes de design et contraintes de conflit.
une validation exprimentale, sur des instances de petite taille, de lefficacit des deux
mthodes prcdentes ;
un prototype exprimental daide lorchestration facilitant lexploration du timbre
orchestral via une reprsentation multi-points de vue des solutions et favorisant la d-
couverte des prfrences implicites du compositeur.
Extension de linstrumentarium
Pour de multiples raisons que nous ne rappellerons pas ici, nous nous sommes restreints
dans notre travail une description spectro-harmonique du timbre, limitant ainsi la connais-
sance instrumentale aux sons harmoniques, entretenus et sans variations temporelles. Or cette
large classe de sons nest pas intgralement reprsente par linstrumentrium actuel au sein de
notre systme. Manquent en particulier les sons de tuba, accordon, saxophones, contrebas-
son, clarinette basse, trombone basse, flte picolo, flte basse. Ces instruments produisent des
timbres accessibles nos descripteurs et leur utilisation est frquente dans les grands orchestres
comme dans les ensembles. La gnralisation de notre outil dorchestration pourrait donc com-
mencer par lajout de ces instruments, ainsi qu la possibilit pour linstrumentarium complet
de jouer en quarts de tons.
Notre vision exclusivement spectrale du timbre est aujourdhui sur le point dtre tendue
par les rsultats des travaux mens en parallle des ntres lIRCAM sur les modles dinstru-
ments. De nouvelles composantes du timbre, telles que le bruit ou la modulation damplitude,
pourront tre prises en compte. Il conviendra alors dvaluer lintrt de ces modles proba-
bilistes, en comparant leurs performances celles de notre approche descriptive actuelle. Si
les rsultats sont concluants, la connaissance instrumentale de notre outil pourra alors tre
tendue aux sons bruits et moduls.
218
Perspectives de recherche plus long terme
A plus long terme, la pluridisciplinarit de laide lorchestration laisse entrevoir de mul-
tiples directions de recherche. Nous bauchons ici quelques pistes de travail.
219
Infrence automatique des critres pertinents
Si les progrs venir sur la caractrisation du timbre instrumental permettront den consi-
drer de nombreuses dimensions supplmentaires, ils augmenteront aussi considrablement le
nombre de critres dans le processus doptimisation. Or, plus le nombre de critres est en
effet lev, plus une configuration alatoire a une probabilit forte dtre non-domine. Luti-
lisateur risque alors dtre confront des ensembles de solutions gigantesques dans lesquels
lidentification dune configuration pertinente peut savrer longue et fastidieuse.
Dans un contexte daide la dcision mutli-critres comme lorchestration assiste par or-
dinateur, la singularit dune solution tient moins un jeu de valeurs prcises pour un grand
nombre de critres qu lidentification de descripteurs adquats pour le problme considr.
Il est inutile daccumuler les critres de dcision si ceux-ci ne permettent pas de distinguer
perceptivement les solutions. Une description approfondie et multidimensionnelle du timbre
instrumental est donc certes un pr-requis indispensable pour laide lorchestration, condi-
tion toutefois de pouvoir proposer lutilisateur un nombre rduit de critres pertinents pour
un problme particulier. A terme, il conviendrait donc dimaginer un moyen de dduire de
lanalyse de la cible les meilleurs critres pour une optimisation dans un espace de dimension
acceptable.
Fusion attaque/rsonnance
Du ct de la psychoacoustique et de la perception du timbre, les phnomnes de fusion
entre attaque et rsonnances sont galement investiguer. En orchestration, les sons non
entretenus sont frquemment employs pour leurs attaques rapides. Ds le dbut de XXe
sicle, les compositeurs ont cr des timbres nouveaux en les associant aux vents ou aux
cordes joues larchet. Le caractre inou de ces sonorits rsulte de leur aspect la fois
percussif et soutenu : ne sapparentant aucun instrument connu, elles sont trs droutantes
pour lcoute qui les peroit comme un timbre unifi . Lintgration des instruments sons
non entretenus au sein de notre systme passe donc par une comprhension des phnomnes de
couplage entre une attaque rapide produite par une catgorie dinstruments et une rsonnance
assure par une autre.
Ecriture de llectronique
Nous avons vu en dernire partie de cette thse que loutil dorchestration pouvait non
seulement aider lcriture instrumentale, mais galement servir denvironnement de cration
sonore pour des parties lectroniques dans le cadre de musiques mixtes. En admettant que du
point de vue de la modlisation du timbre les sons lectroniques peuvent tre reprsents par les
220
mmes descripteurs que les sons instrumentaux, lorchestration avec parties lectroniques ne se
rsume pas lajout dinstruments supplmentaires. Dans notre modle actuel dorchestration,
chaque son de la connaissance instrumentale est soumis des contraintes dintgrit (soit il
est utilis dans lorchestration, soit il ne lest pas) et de capacit (le nombre total de sons
provenant dun mme instrument est limit par leffectif orchestral). Ces contraintes nont
plus cours pour lcriture des parties lectroniques : les sons sont mlangeables volont, et
dans toutes les proportions de volume possibles. Autrement dit, la reprsentation mme des
orchestrations est dans ce cas repenser. Quant lalgorithme doptimisation, il devra pouvoir
traiter simultanment variables binaires et variables continues.
Le problme du temps
Au commencement de nos recherches sur laide lorchestration, nous avons fait le choix de
laisser de ct, dans un premier temps, les aspects temporels du timbre. Nous avons dfini une
cible orchestrer comme un ensemble de descripteurs spectro-harmoniques statiques, calculs
sur une partie suppose stable du son. En consquence, notre outil est capable dassister
les compositeurs dans la cration de textures complexes, dune grande richesse spectrale, mais
ne peut pas gnrer de mouvements .
Malgr cela, la question dun timbre voluant dans le temps, na jamais cess, au cours de
nos recherches, dtre pose. Peut-on considrer lorchestration dynamique comme une simple
extension du modle statique, o lvolution au cours du temps ne serait rien dautre quune
succession de segments ? Ou cela ncessite-t-il au contraire une modlisation temporelle
des possibilits instrumentales ? Il nest pas dit que nous disposions lheure actuelle des
outils et du recul ncessaire pour dcider de la pertinence et de la faisabilit de chacune des
approches, mais nous pouvons dj apporter un clairage sur cette question en distinguant
deux approches du temps.
Dun point de vue formel, si lvolution du timbre dans le temps est considre comme un
ensemble de relations dantriorit, de postrit ou de simultanit, on peut alors dcider que
tel timbre est suivi de tel autre, se superpose tel troisime, se fond dans tel quatrime,
etc. Il sagit videmment dune vision segmente de lorchestation, dans laquelle les couleurs
se succdent comme des panneaux dtachs les uns des autres. A priori, cette approche
du temps ne remet pas en cause notre modle combinatoire, car lhorizontalit de lcriture y
est pense comme une succession de segments verticaux, dont le contrle est possible laide
dun ensemble de contraintes sur les variables de lcriture musicale.
Nous devons toutefois reconnatre que cette approche ne permet de traiter que des va-
riations de timbre relativement lentes, et rien ne nous laisse aujourdhui prvoir la finesse
temporelle que nous pourrons atteindre par ce biais. Une autre vision du temps, horizontale et
continue, semble donc ncessaire, et implique llaboration dun modle temporel du timbre.
Vaste problme, qui reporte la complexit de lorchestration sur celle du jeu instrumental. Si
une recherche future sengage dans cette voie, il lui faudra sans doute abandonner, ne serait-ce
que temporairement, lapproche combinatoire, verticale, de lorchestration pour se concentrer
sur une modlisation des enchanements de timbres au cours du temps.
221
222
Quatrime partie
Annexes
223
Annexe A
Nous explicitons dans cette annexe les mthodes dextraction des descripteurs introduits
en 8.1.2. Nous dfinissons galement les fonctions dagrgation et fonctions de comparaison
pour chacun dentre eux.
Extraction Lextraction des MRP se fait en plusieurs tapes rsumes par la figure A.1.
Dans un premier temps, les partiels du signal sont calculs fentre par fentre grce une FFT
et une extraction de pics spectraux. Ensuite, une procdure de suivi de partiels permet de ne
retenir que les partiels prsents sur lintgralit du son. Ces deux premires tapes sont ralises
par le programe pm2 [Rod97] qui sert en partie de noyau au logiciel AudioSculpt [BR05].
Dans un troisime temps, un modle perceptif est utilis pour slectionner les partiels rso-
lus par le systme auditif, ainsi quen estimer la correction damplitude et de frquence opre
par lensemble de la chane perceptive. Notre modle auditif utilise une mesure ERB (Equiva-
lent Rectangular Bandwidth [GM00]) pour simuler les bandes critiques de loreille interne et
identifier les partiels rsolus.
Le nombre de MRP varie selon le type de cible. Pour les cibles harmoniques, une quinzaine
de partiels suffisent en gnral. Les cibles plus complexes en ncessitent souvent davantage
(entre 20 et 30).
FFT +
Fentrage Suivi de Modle
Signal Extraction MRP
temporel partiels perceptif
des pics
225
226 ANNEXE A. DESCRIPTEURS : EXTRACTION, AGRGATION, COMPARAISON
Fig. A.2 Enveloppes spectrales moyennes des les sons entretenus de SOL
Agrgation Les MRP ne sont calculs que pour la cible. Les sons de la base dchantillons
instrumentaux tant harmoniques (voir section 8.1.1) et leur enveloppe spectrale lexcep-
tion du registre grave gnralement dcroissante (voir figure A.2), leurs MRP se rsument la
plupart du temps aux premiers partiels. Tirant parti de ce constat, nous introduisons une m-
thode dagrgation efficace en complexit, permettant de calculer la contribution des partiels
dun mlange instrumental aux MRP de la cible, mais ncessitant un prtraitement pralable
des sons de la base.
Pour chaque son nous identifions les partiels quil partage avec la cible. Le critre diden-
tification est un seuil de tolrance sur les frquences et correspond environ un huitime de
ton, soit un cart maximal de frquence infrieur 1.5%. Par exemple, si la cible possde son
3me MRP 500 Hz, tous les sons de la base ayant un partiel entre 493 Hz et 507 Hz verront
ce partiel identifi avec le 3me MRP de la cible. (On notera par la suite f1 f2 pour dsigner
deux frquences dans un rapport infrieur au seuil de tolrance.)
Soit T la cible orchestrer et {fkT } et {aTk } les vecteurs de frquences et amplitudes des
MRP de T . Soit S un son de la base de donnes dont les partiels ont respectivement pour
frquences et amplitudes {fkS } et {aSk }. La contributiton de S aux j me MRP de T sera alors :
i
ak0 si k0 , fkS0 fjT
0 sinon
Plus simplement,
on retiendra quon associe chaque son Si de la base de donnes un vecteur
damplitudes M RPST (j) de mme taille que {aTk } exprimant la contribution de S chaque
alors :
T
max M RPSTi (1) , max M RPSTi (2) , . . .
M
\ RP K = (A.1)
iI iI
Une fonction de maximum est prfr une addition des amplitudes en raison des phnomnes
de phase voqus en 4.3 et responsables de la non-additivit des spectres.
La figure A.3 illustre les processus de calcul de contributions des MRP ainsi que de lagr-
gation des contributions. Sur le diagramme suprieur, on a report le spectre dun son cible
orchestrer (en pointills) ainsi que les principaux partiels rsolus (MRP, en trait plein). Le
diagramme mdian est un exemple de contribution aux MRP de deux sons de hauteurs res-
pectives C2 et D2. Il y apparat par exemple que le 4me partiel du C2 a t identifi au 3me
MRP, que les 9me partiel de C2 et 8me partiel de D2 ont t identifis au 13me MRP. Les
contributions de chaque son se ramnent par ce procd des vecteurs damplitude de mme
taille que les MRP et dont les valeurs ne dpendent ques des amplitudes des partiels de ces
sons. Enfin, le diagramme infrieur illustre lagrgation des contributions.
Comparaison Soit DTM RP la fonction de comparaison associe aux MRP pour la cible T ,
cest--dire une mesure de distance entre une mixture K de sons instrumentaux et T dans le
sous-espace associ aux MRP. Nous la dfinissons par :
M RP T T
DT (K) = 1 cos M RP K , M RPT
\ (A.2)
La distance sera donc nulle si les deux vecteurs damplitudes sont dans un rapport de proporti-
nalit. Ce degr de libert est ncessaire pour viter toute influence du niveau denregistrement
du son donn en entre du systme. Avec cette mthode, les sons sont donc compars sur la
forme de leurs enveloppes spectrales.
N.B. Si la contribution dun son aux MRP augmente avec le nombre de partiels identifis
ceux de la cible, en revanche aucune mesure ne pnalise les partiels non identifis. La raison
principale est quil ny a pas de conduite particulire tenir en pareil cas. Dans lexemple
de la figure A.3, les 5me et 8me partiels de C2 sont bien prsents dans la cible mais
damplitude trop faible pour tre rsolus. Il ny a donc aucune raison pnaliser leur prsence.
Dautres cas peuvent ce prsenter, pour lesquels lajout dun son dans une mixture introduit
des partiels absents dans la cible et que la fonction de comparaison A.2 ne peut pas voir .
Cest l une limite inhrente la modlisation en MRP de la partie basse frquence du spectre.
Mais ce que nous perdons en prcision destimation, nous le gagnons en rapidit de calcul :
Les contributions des sons de la base de donnes aux MRP sont calculs une seule fois pour
une cible donne, et lvaluation des mixtures selon ce critre nimplique que des oprations
lmentaires sur des vecteurs damplitudes. Une comparaison ayant recours aux informations
de damplitude et de frquence aurait t beaucoup plus coteuse en temps de calcul.
dcrits en infra. Nous ne dcrivons donc dans ce paragraphe que sa mthode dextraction. Il
est calcul pour tous les sons de la base de donnes mais nest pas extrait de la cible, puisque
nous considrons lintensit de cette dernire comme non significative.
Lextraction de lintensit perceptive est schmatise figure A.4. Pour chaque fentre tem-
porelle le spectre instantan du signal est extrait par FFT. Un modle perceptif calcule ensuite
lintensit perceptive instantane pour chaque fentre. Ce modle applique dabord un premier
filtre simulant la fonction de transfert de loreille moyenne [MGB97], puis utilise une mesure
ERB [GM00]) pour simuler les bandes critiques de loreille interne et calculer lintensit dans
chaque bande. Lintensit totale instantane est obtenue par sommation de linstensit dans
les bandes critiques. Cette extraction est ralise par le programme ircamdescriptor [Pee04].
Le lecteur trouvera davantage de prcision sur la dfinition et le calcul de lintensit perceptive
dans [MGB97].
Centrode spectral
Le centrode spectral est communment dfini comme le barycentre spectral du son. Dun
point de vue perceptif, il est corrl la brillance.
Extraction Le calcul du centrode (ou premier moment spectral) se fait un deux tapes.
Dans un premier temps, le centrode instantan du signal (dfini comme le barycentre du
spectre damplitude) est extrait pour chaque fentre temporelle. La moyenne des centrodes
instantans pondre par lintensit perceptive instantane dfinit alors le centrode global. La
figure A.5 rsume ce processus.
Intensit
instantane
O est un facteur de proportionalit dont la valeur nintervient pas dans lquation A.3.
Comparaison Soient T la cible orchestrer, scT son centrode et K une proposition dor-
chestration. Nous choisissons comme fonction de comparaison relative au centrode spectral
une simple distance relative :
|sc
b K scT |
DTsc (K) = (A.4)
scT
Comparaison Soit T la cible orchestrer dtendue spectrale ssT . Soit K une proposition
dorchestration dtendue ss
b K . La fonction de comparaison scrit :
|ss
b K ssT |
DTss (K) = (A.6)
ssT
Annexe B
Etant donn un point x = (x1 , . . . , xN ) C de lespace des critres, nous avons dfini au
paragraphe 8.5.1 la norme induite par x (note kkx ) comme la norme pondre de Tchebycheff
vrifiant :
(i, j) {1; N }2 , i xi = j xj (B.1)
La proprit 8.2 garantit que la valeur de la norme induite par une configuration x est infrieure
toutes les autres normes pondres de Tchebycheff pour x. Cest la norme qui optimise le
classement x sur lespace de recherche. La figure illustre cette proprit. Lespace des critres
y est ordonn jusqu x (reprsente par un carr noir) selon trois normes pondres de
Tchebycheff. Les solutions en rouge ont un rang infrieur x, elles sont donc prfres x pour
la norme considre. De faon vidente, seule la norme plaant la solution x sur le sommet
dun hyper-rectangle correspondant une surface isomtrique permet de minimiser le nombre
de solutions de meilleur rang que x. Cette position correspond lquation B.1 de la norme
induite.
La proprit 8.2 assure en outre que si une solution x minimise k kx , alors x est non-
domine et vice-versa. La figure B.2 permet de sen convaincre aisment. Seule la norme
induite par une configuration efficiente permet de classer cette dernire en premier lorsque
lespace de recherche est ordonn selon cette norme. Cest cette proprit qui a permis Chen
& Liu [CL94] et Steuer [Ste86] dtablir lquivalence entre un problme multicritre et un
ensemble de problmes mono-critre scalariss (voir sections 5.7 et 8.5.1).
Fig. B.1 Classement dune configuration domine selon trois normes de Tchebycheff
231
232 ANNEXE B. NORME INDUITE PAR UNE CONFIGURATION
Fig. B.2 Classement dune configuration efficiente selon trois normes de Tchebycheff
10.1 Passage continu dun accord de cordes vers un accord de vents . . . . . . . . . . 157
233
234 TABLE DES FIGURES
B.1 Classement dune configuration domine selon trois normes de Tchebycheff . . . 231
B.2 Classement dune configuration efficiente selon trois normes de Tchebycheff . . . 232
Liste des tableaux
8.1 Tailles moyennes des espaces de recherche pour des problmes de petite taille . 107
8.2 Diffrentes combinaisons de critres testes . . . . . . . . . . . . . . . . . . . . . 107
8.3 Tailles moyennes des fronts de Pareto . . . . . . . . . . . . . . . . . . . . . . . . 109
8.4 Erreurs moyennes destimation des descripteurs . . . . . . . . . . . . . . . . . . 112
8.5 Frquence laquelle la solution thorique appartient au front de Pareto . . . . 114
8.6 Rangs mdians de la solution thorique dans lespace des critres . . . . . . . . 116
8.7 Statistiques M AD, P F M , M F M , P IM , M IM pour les mixtures monopho-
niques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
8.8 Statistiques M AD, P F M , M F M , P IM , M IM pour les mixtures polyphoniques123
8.9 Test dcoute 1 : validation de lapproche multicritre . . . . . . . . . . . . . . . 124
8.10 Test dcoute 2 : valuation des heuristiques H , He et Hs . . . . . . . . . . . . 125
8.11 Information approte par les critres . . . . . . . . . . . . . . . . . . . . . . . . 127
235
236 LISTE DES TABLEAUX
Liste des algorithmes
237
238 LISTE DES ALGORITHMES
Glossaire
mode de jeu Technique de jeu enrichissant le vocabulaire sonore des instruments de musique.
modle dinstrument Modle probabiliste caractrisant les possibilits sonores dun instru-
ment, dont les paramtres sont estims partir de bases de donnes dchantillons.
mthode dextraction Fonction associe un descripteur permettant den calcuer la valeur
partir du signal audio.
239
240 Glossaire
241
242 BIBLIOGRAPHIE
[MGB97] Brian C.J. Moore, Brian R. Glasberg, and Thomas Baer, A Model for Prediction
of Thresholds, Loudness, and Partial Loudness, Journal of Audio Engeneering
Society (1997), 224240.
[Mic96] Z. Michalewicz, Denetic Algorithms + Data Structures + Evolution Programs (3rd
Ed.), Springer, berlin, 1996.
[Mie99] Kaisa Miettinen, Nonlinear Multiobjective Optimization, International Series in
Operations Research and Management Science, vol. 12, Kluwer Academic Publi-
shers, Dordrecht, 1999.
[MS98] Kim Mariott and Peter Stuckey, Programming with Constraints : An Introducion,
MIT Press, 1998.
[MT90] S. Martello and P. Toth, Knapsack Problems : Algorithms and Computer Imple-
mentations, John Wiley & Sons, Chichester, 1990.
[MWD+ 95] S. McAdamcs, S. Winnsberg, S. Donnadieu, G. De Soete, and J. Krimphoff, Per-
ceptual Scaling of Synthesized Musical Timbres : Common Dimensions, Specifici-
ties, and Latent Subject Classes, Psychological Research (1995), no. 58, 177192.
[OFL97] Y. Orlarey, D. Fober, and S. Letz, Lenvironnement de composition musicale
Elody, Actes des Journes dinformatique musicale (JIM97) (Lyon, France),
1997.
[OGAK05] M. Oltean, C. Grosan, A. Abraham, and M. Koppen, Multiobjective Optimiza-
tion Using Adaptive Pareto Archived Evolution Strategy, Proceedings of the 5th
International Conference on Intelligent Systems Design and Applications (ISDA),
2005, pp. 558563.
[Pee04] Geoffroy Peeters, A Large Set of Audio Features for Sound Description (Similarity
and Classification) in the CUIDADO Project, Tech. report, IRCAM, 2004.
[Pis55] Walter Piston, Orchestration, Norton Company, New York, 1955.
[PMH00] Geoffroy Peeters, Stephen McAdams, and Perfecto Herrera, Instrument Sound
Description in the Context of MPEG-7, International Computer Music Conference
(ICMC) (Berlin, Allemagne), Septembre 2000, pp. 166169.
[Pop91] S.T. Pope (ed.), The Well-Tempered Object (Musical Application of Object-
Oriented Technology), MIT Press, 1991.
[PR01] Franois Pachet and Pierre Roy, Musical Harmonization with Constraints : A
Survey, Constraints Journal 6 (2001), no. 1, 719.
[Pse03] David Psenicka, Sporch : An Algorithm for Orchestration Based on Spectral Ana-
lyses of Recorded Sounds, Proceedings of International Computer Music Confe-
rence (ICMC), 2003.
[Puc91] Miller Puckette, Combining Event and Signal Processing in the Max Graphical
Programming Environment, Computer Music Journal 15 (1991), no. 3.
[RAQ+ 01] C. Rueda, G. Alvarez, L.O. Quesada, G. Tamura, Valencia F.D, J.F. Diaz, and
G. Assayag, Integrating Constraints and Concurrent Objects in Musical Applica-
tions : A Calculus ans its Visual Language, Constraints 6 (2001), no. 1.
[RH05] Franois Rose and James Hetrick, Spectral Analysis as a Ressource for Contem-
porary Orchestration Technique, Proceedings of Conference on Interdisciplinary
Musicology, 2005.
246 BIBLIOGRAPHIE
[Ris86] Jean-Clause Risset, Son musical et perception auditive, Pour la Science (1986),
no. 109.
[RK64] Nicola Andre Rimski-Korsakov, Principles of Orchestration, with Musical
Examples Drawn from his own Works, Maximilian Steinberg, New York, 1964.
[RLBA98] Camilo Rueda, Mikael Laurson, Georges Bloch, and Grard Assayag, Integrating
Constraints Programming in Visual Musical Composition Languages, Proceedings
of the European Conference on Artificial Intelligence, 1998.
[Rod97] Xavier Rodet, Musical Sound Signal Analyis/Synthesis : Sinusoidal+Residual and
Elementary Waveform Models, Proceedings of the IEEE Time-Frequency and
Time-Scale Workshop (Coventry, Grande Bretagne), 1997.
[Sal79] M.E. Salukwadze, Vector-Valued Optimization Problems in Control Theory, Aca-
demic Press, 1979.
[Sch11] Arnold Schoenberg, Harmonielehre, Universal Edition, Vienne, 1911.
[Sch66] Pierre Schaeffer, Trait des objets musicaux, Seuil, Paris, 1966.
[Sch68] J.F. Schouten, The Perception of Timbre, Reports of the 6th Internation Cangress
on Acoustics (Tokyo, Japon), no. GP-6-2, 1968, pp. 3544, 90.
[SD94] N. Srinivas and K. Deb, Multiobjective Optimization Using Nondominated Sorting
in Genetic Algorithms, Evolutionary Computation 2 (1994), no. 3, 221248.
[SF97] Eleanor Selfridge-Field (ed.), Beyond MIDI : The Handbook of Musical Codes,
MIT Press, Cambridge, 1997.
[Sol02] Christine Solnon, Ants Can Solve Constraint Satisfaction Problems, IEEE Tran-
sactions on Evolutionary Computation 6 (2002), 347357.
[Ste86] R.E. Steuer, Multiple Critera Optimization - Theory, Computation and Applica-
tion, Wiley, New York, 1986.
[Ste90] G.L. Steele (ed.), Common Lisp, the Language (2nd Ed.), Digital Press, 1990.
[SW00] D. Schwartz and M. Wright, Extensions and Applications of the SDIF Sound Des-
cription Interchange Format, Proceedings of the International Computer Music
Conference (Berlin, Allemagne), 2000.
[Tal99] E.G. Talbi, Mtaheuristiques pour loptimisation combinatoire multi-objectif : Etat
de lart, Tech. report, C.N.E.T. (France Telecom), octobre 1999.
[TR07] Damien Tardieu and Xavier Rodet, An Instrument Timbre Model For Computer
Aided Orchestration, WASPAA (New Paltz, NY, USA), Octobre 2007.
[Tru04] Charlotte Truchet, Contraintes, recherche locale et composition assiste par ordi-
nateur, Ph.D. thesis, Univerit Paris 7 Denis Diderot, Paris, 2004.
[Tsa93] E.P. Tsang, Fondations of Constraint Satisfaction, Academic Press, 1993.
[UT94] E.L. Ulungu and J. Teghem, Multi-Objective Combinatorial Optimization : A
Survey, Foundations of Computing and Decision Sciences 20 (1994), no. 2, 149
165.
[VHD03] Michel Vasquez, Djamal Habet, and Audrey Dupont, Neighborhood Design by
Consistency Checking, Actes du 5e congrs de la socit franaise de recherche
oprationnelle et daide la dcision (ROADEF2003) (Avignon, France), 2003.
[VSL] Vienna Symphonic Library, http://www.vsl.co.at.
BIBLIOGRAPHIE 247