PALISADE EVOLVER 5.5 Manuel utilisateur

Guide d’utilisation
Evolver
Solveur par algorithmes
génétiques pour Microsoft Excel
Version 5.5
janvier, 2010
Palisade Corporation
798 Cascadilla St.
Ithaca, NY 14850
États-Unis
+1-607-277-8000
+1-607-277-8001 (fax)
http://www.palisade.com (site Web)
[email protected] (courriel)
Avis de copyright
Copyright © 2010, Palisade Corporation.
Marques déposées
Microsoft, Excel et Windows sont des marques déposées de Microsoft Corporation.
IBM est une marque déposée d’International Business Machines, Inc.
Palisade, Evolver, TopRank, BestFit et RISKview sont des marques déposées de Palisade
Corporation.
RISK est une marque commerciale de Parker Brothers, une division de Tonka Corporation,
exploitée sous licence.
Table des matières
Chapitre 1 : Introduction
1
Introduction .........................................................................................3
Installation ...........................................................................................7
Chapitre 2 : Principes
11
Qu’est-ce qu’Evolver ?.....................................................................13
Chapitre 3 : Evolver : Pas à pas
21
Introduction .......................................................................................23
Visite guidée......................................................................................25
Chapitre 4 : Applications types
43
Introduction .......................................................................................45
Sélection publicitaire........................................................................47
Ordre alphabétique...........................................................................49
Affectation de tâches .......................................................................53
Boulangerie .......................................................................................55
Allocation budgétaire .......................................................................57
Équilibre chimique............................................................................59
Planificateur de classes ...................................................................61
Segmenteur de code ........................................................................65
Dakota : Itinéraires sous contraintes .............................................69
Ordonnancement multigamme........................................................73
Emplacement de pylônes radio.......................................................75
Équilibrage de portefeuilles.............................................................77
Composition de portefeuille ............................................................81
Table des matières
i
Émetteurs radio ................................................................................ 83
Achat ................................................................................................. 85
Problème du voyageur de commerce ............................................ 87
Navigateur spatial ............................................................................ 89
Opérateur en bourse ........................................................................ 91
Transformateur................................................................................. 93
Transports......................................................................................... 95
Chapitre 5 : Guide de référence Evolver
97
Commande Définition du modèle ................................................... 99
Commande Paramètres d'optimisation ....................................... 123
Commande Démarrer l'optimisation ............................................ 129
Commandes Utilitaires .................................................................. 131
Suivi Evolver................................................................................... 135
Chapitre 6 : Optimisation
147
Méthodes d’optimisation ................................................................. 149
Solveur Excel.................................................................................. 155
Types de problèmes....................................................................... 159
Chapitre 7 : Algorithmes génétiques
165
Introduction .................................................................................... 167
Histoire ............................................................................................ 167
Exemple biologique ....................................................................... 171
Exemple numérique ....................................................................... 173
Chapitre 8 : Et aussi…
177
Ajout de contraintes....................................................................... 179
Accélération du processus ........................................................... 189
Mode d’exécution de l’optimisation Evolver ............................... 191
ii
Annexe A : Automatisation d’Evolver
195
Annexe B : Dépannage / Questions-Réponses
197
Dépannage / Questions-Réponses ...............................................197
Table des matières
Annexe C : Ressources complémentaires
201
Glossaire
207
Indice
217
iii
iv
Chapitre 1 : Introduction
Introduction .........................................................................................3
Avant de commencer ...............................................................................3
Éléments du progiciel..............................................................................3
À propos de cette version........................................................................3
Votre contexte d’exploitation.................................................................4
Si vous avez besoin d’aide......................................................................4
Avant d’appeler...........................................................................4
Contacter Palisade ......................................................................5
Versions étudiants......................................................................6
Configuration requise .............................................................................6
Installation ...........................................................................................7
Généralités ................................................................................................7
Désinstallation d’Evolver..........................................................7
DecisionTools Suite.................................................................................8
Configuration des icônes ou raccourcis d'Evolver .............................8
Messages d’avertissement de sécurité des macros au démarrage ...9
Renseignements complémentaires .......................................................9
Fichier Lisezmoi d'Evolver......................................................10
Didacticiel d’Evolver................................................................10
Apprendre Evolver.................................................................................10
Chapitre 1 : Introduction
1
2
Introduction
Evolver représente l’optimiseur par algorithmes génétiques
commercial le plus rapide et le plus poussé jamais encore proposé sur
le marché. À travers les puissantes techniques d’optimisation par
algorithmes génétiques, Evolver identifie les solutions optimales aux
problèmes impossibles à résoudre pour les optimiseurs linéaires et
non linéaires. Evolver est disponible en deux versions – Professional
et Industrial - suivant la capacité d’optimisation recherchée.
Ce Guide de l’utilisateur Evolver présente une introduction au
programme et aux principes qui le sous-tendent. Vous y trouverez
aussi plusieurs exemples d’application de la technologie des
algorithmes génétiques unique d’Evolver. Ce manuel peut aussi servir
de guide de référence complet et pleinement indexé, avec description
et illustration de chaque fonctionnalité d’Evolver.
Avant de commencer
Avant d’installer et de démarrer Evolver, vérifiez que votre progiciel
contient bien tous les éléments nécessaires et que votre ordinateur
satisfait aux exigences de configuration minimales requises.
Éléments du progiciel
Evolver peut être acheté en autonome ou dans le cadre des versions
DecisionTools Suite Professional et Industrial. Le CD-ROM Evolver
contient le complément Excel Evolver, plusieurs exemples
d’application d’Evolver et un système d’aide Evolver en ligne indexé.
Les versions DecisionTools Suite Professional et Industrial
contiennent, en plus des éléments ci-dessus, une série d’autres
applications.
À propos de cette version
Cette version d’Evolver peut être installée en tant que programme 32
bits pour Microsoft Excel 2000 ou version ultérieure.
Chapitre 1 : Introduction
3
Votre contexte d’exploitation
Les descriptions contenues dans ce guide présupposent une
connaissance générale du système d’exploitation Windows et du
tableur Excel, notamment :
♦
familiarité avec l’ordinateur et la souris
♦
compréhension des termes icônes, cliquer, double-clic, menu,
fenêtre, commande, objet, etc.
♦
notions élémentaires de structure de répertoires et désignation des
fichiers
Si vous avez besoin d’aide
Un service d’assistance technique est proposé gratuitement à tous les
utilisateurs enregistrés d’Evolver dotés d’un plan de maintenance à
jour, ou sur forfait à l’incident. Pour assurer que vous êtes bien un
utilisateur enregistré d’Evolver, enregistrez-vous en ligne sur
http://www.palisade.com/support/register.asp.
Si vous nous contactez par téléphone, soyez prêt à nous communiquer
le numéro de série de vos outils et gardez votre guide d’utilisation à
portée de main. Nous pourrons vous être d’une meilleure assistance si
vous vous trouvez face à votre ordinateur, prêt à exécuter les
commandes du programme.
Avant d’appeler
4
Avant d’appeler le service d’assistance technique, passez en revue la
liste de contrôle suivante :
•
Avez-vous consulté l’aide en ligne ?
•
Avez-vous consulté ce manuel et passé en revue le didacticiel multimédia
en ligne ?
•
Avez-vous consulté le fichier LISEZMOI.WRI ? Il contient des
informations sur Evolver non disponibles lors de l’impression du
manuel.
•
Pouvez-vous reproduire le problème de manière cohérente ? Pouvez-vous
reproduire le problème sur un autre ordinateur ou avec un autre
modèle ?
•
Avez-vous consulté notre site Web, à l’adresse
http://www.palisade.com ? Vous y trouverez notre dernier fichier
FAQ (base de données consultable de questions et réponses techniques)
et les correctifs Evolver dans la section de support technique. Il est utile
de consulter régulièrement notre site pour obtenir les dernières
informations publiées sur Evolver et sur les autres logiciels Palisade.
Introduction
Contacter
Palisade
Vos questions, commentaires ou suggestions relatifs à Evolver sont les
bienvenus ! Vous pouvez prendre contact avec notre personnel
d’assistance technique par l’une des méthodes suivantes :
•
Courriel : [email protected]
•
Téléphone : +1-607-277-8000, du lundi au vendredi, de 9 à 17 heures,
heure de l’Est des États-Unis. Suivez les instructions données pour
joindre l’Assistance technique (Technical Support).
•
Fax : +1-607-277-8001
•
Adresse postale :
Technical Support
Palisade Corporation
798 Cascadilla St.
Ithaca, NY 14850
USA
Palisade Europe :
•
Courriel : [email protected]
•
Téléphone : +44 1895 425050 (Royaume-Uni)
•
Fax : +44 1895 425051 (Royaume-Uni)
•
Adresse postale :
Palisade Europe
31 The Green
West Drayton
Middlesex
UB7 7PN
Royaume-Uni
Palisade Asie-Pacifique :
•
Courriel : [email protected]
•
Téléphone : +61 2 9929 9799 (Australie)
•
Fax : +61 2 9954 3882 (Australie)
•
Adresse postale :
Palisade Asia-Pacific Pty Limited
Suite 101, Level 1
8 Cliff Street
Milsons Point NSW 2061
Australie
Chapitre 1 : Introduction
5
Quelle que soit la méthode choisie, veillez à indiquer le nom de votre
produit, sa version et son numéro de série. La version exacte de votre
produit est indiquée sous la commande Aide, À propos de… du
menu Evolver proposé dans Excel.
Versions
étudiants
L’assistance téléphonique n’est pas disponible pour la version
étudiants d’Evolver. Si vous avez besoin d’aide, procédez de l’une des
manières suivantes :
♦
Consultez votre professeur ou assistant.
♦
Consultez le fichier FAQ sur http://www.palisade.com.
♦
Adressez-vous au service d’assistance technique par courriel ou
par fax.
Configuration requise
Evolver – Configuration requise
6
•
PC Pentium ou mieux avec disque dur.
•
Microsoft Windows 2000 SP4 ou mieux.
•
Microsoft Excel, version 2000 ou ultérieure.
Introduction
Installation
Evolver, complément de Microsoft Excel, enrichit la fonctionnalité du
tableur moyennant l’ajout de commandes à ses barres de menus.
Généralités
Le programme d’installation copie les fichiers système Evolver dans
un répertoire spécifié du disque dur. Sous Windows 2000 ou version
ultérieure :
1) Insérez le CD-ROM Evolver ou de la version DecisionTools Suite
Professional ou Industrial dans le lecteur CD-ROM.
2) Cliquez sur le bouton Démarrer, puis sur Paramètres et enfin sur
Panneau de configuration.
3) Cliquez deux fois sur l’icône Ajout/Suppression de programmes.
4) Cliquez sur le bouton Installer de l’onglet Installation/désinstallation.
5) Suivez les instructions d’installation affichées à l’écran.
En cas de problème, vérifiez que vous disposez d’un espace suffisant
sur le disque prévu pour l’installation. Après avoir libéré l’espace
disque requis, essayez de réexécuter l’installation.
Désinstallation
d’Evolver
Pour désinstaller Evolver (ou DecisionTools Suite), utilisez l’utilitaire
Ajout/Suppression de programmes du Panneau de configuration et
sélectionnez l’entrée correspondant à Evolver ou DecisionTools Suite.
Chapitre 1 : Introduction
7
DecisionTools Suite
Evolver est compatible avec les outils d’analyse du risque et de
décision DecisionTools Suite, de Palisade Corporation. L’installation
par défaut d’Evolver place le programme dans un sous-répertoire du
répertoire principal « Program Files\Palisade », de la même manière
qu’Excel s’installe généralement dans un sous-répertoire du répertoire
« Microsoft Office ».
Ce sous-répertoire de Program Files\Palisade devient le répertoire
Evolver (appelé, par défaut, Evolver5). Ce répertoire contient le fichier
programme d'Evolver (EVOLVER.XLA), plus les modèles types et
autres fichiers nécessaires à l’exécution d’Evolver. Un autre sousrépertoire de Program Files\Palisade, intitulé SYSTEM, reçoit les
fichiers nécessaires à tous les programmes de la série DecisionTools
Suite, y compris les fichiers d’aide et bibliothèques communs.
Configuration des icônes ou raccourcis d'Evolver
Sous Windows, l’installation crée automatiquement une commande
Evolver dans le menu Programmes de la barre des tâches. Si toutefois
vous rencontrez des problèmes en cours d’installation ou que vous
désirez exécuter cette opération ultérieurement, procédez comme
suit :
1) Cliquez sur le bouton Démarrer et pointez sur Paramètres.
2) Cliquez sur Barre des tâches, puis sur l’onglet Programmes du
menu Démarrer.
3) Cliquez sur Ajouter, puis sur Parcourir.
4) Repérez le fichier EVOLVER.EXE et cliquez deux fois dessus.
5) Cliquez une fois sur Suivant, puis deux fois sur le menu de votre
choix.
6) Tapez le nom « Evolver » et cliquez sur Terminer.
8
Installation
Messages d’avertissement de sécurité des
macros au démarrage
Microsoft Office propose plusieurs paramètres de sécurité pour éviter
l’exécution de macros indésirables ou hostiles dans vos applications
Office. Sauf sous le paramètre de sécurité le plus faible, un message
d’avertissement s’affiche à chaque tentative de chargement d’un
fichier assorti de macros. Pour éviter l’affichage de ce message à
chaque exécution d’un compagnon Palisade, Palisade signe
numériquement ses fichiers. Après avoir spécifié Palisade
Corporation en tant que source fiable, vous pouvez dès lors ouvrir les
compagnons Palisade sans message d’avertissement. Pour ce faire :
•
Chapitre 1 : Introduction
Séléctionnez l’option Approuver tous les documents de cet
éditeur lorsqu’une boîte de dialogue Options de sécurité (telle
que celle illustrée ci-dessous) s’ouvre au démarrage
d’Evolver.
9
Renseignements complémentaires
Les ressources suivantes peuvent contenir une information
complémentaire relative à Evolver :
Fichier Lisezmoi
d'Evolver
Ce fichier contient une présentation rapide d’Evolver, ainsi que,
éventuellement, l’information de dernière minute publiée sur la
dernière version du logiciel. Pour y accéder, choisissez Démarrer/
Programmes/ Palisade DecisionTools/ Lisezmoi et cliquez sur
Evolver – Lisezmoi. Il est utile de lire ce fichier avant l’emploi
d’Evolver.
Didacticiel
d’Evolver
Le didacticiel en ligne d’Evolver apporte aux utilisateurs débutants
une présentation rapide du logiciel et des algorithmes génétiques. La
présentation se limite à quelques minutes seulement. Voir la rubrique
Apprendre Evolver ci-dessous pour tous détails concernant l’accès au
didacticiel.
Apprendre Evolver
Pour vous familiariser rapidement avec Evolver, suivez le didacticiel
en ligne, où des experts du logiciel vous guident à travers différents
modèles types en format cinéma. Ce didacticiel est une présentation
multimédia des principales fonctionnalités d’Evolver.
Pour y accéder, choisissez la commande Didacticiel du menu Aide
d’Evolver.
10
Installation
Chapitre 2 : Principes
Qu’est-ce qu’Evolver ?.....................................................................13
Principes fonctionnels d’Evolver ........................................................14
Algorithmes génétiques ..........................................................14
Qu’est-ce que l’optimisation ? .............................................................15
Pourquoi bâtir des modèles Excel ? ....................................................16
Pourquoi Evolver ?.................................................................................16
Plus question de « deviner »...................................................17
Plus précis et plus utile ...........................................................17
Plus souple.................................................................................17
Plus puissant .............................................................................18
Plus convivial ............................................................................18
Rentable .....................................................................................19
Chapitre 2 : Principes
11
12
Qu’est-ce qu’Evolver ?
Le progiciel Evolver apporte à l’utilisateur une méthode simple de
recherche de solutions optimales à pratiquement tous les types de
problèmes. En un mot, Evolver trouve les meilleures entrées pour la
production d’une sortie désirée. Servez-vous-en pour rechercher la
combinaison, l’ordre ou le groupement de variables qui produisent les
meilleurs bénéfices, le moindre risque ou la plus grande quantité de
produits au moyen de la plus faible quantité de matériaux. Evolver
sert souvent de complément au tableur Microsoft Excel : la
configuration du problème s’effectue dans Excel, et sa résolution à
l’aide d’Evolver.
MODÈLE
DÉCRIRE LA RECHERCHE
SOLUTION
Commencez par modéliser le problème dans Excel, avant de le décrire à Evolver.
Excel apporte toutes les formules, fonctions, graphiques et capacités
de macro dont la plupart des utilisateurs ont besoin pour créer des
modèles réalistes de leurs problèmes. Evolver apporte l’interface de
description de l’incertitude du modèle et de la cible recherchée, ainsi
que les moteurs qui permettent de l’atteindre. Ensemble, ils
découvrent les solutions optimales à pratiquement tous les problèmes
modélisables.
Chapitre 2 : Principes
13
Principes fonctionnels d’Evolver
Evolver recourt à un ensemble exclusif d’algorithmes génétiques pour
rechercher les solutions optimales à un problème. Il fait aussi appel
aux distributions de probabilité et à la simulation pour gérer
l’incertitude présente dans le modèle.
Algorithmes
génétiques
Evolver fait appel aux algorithmes génétiques pour rechercher la
meilleure solution à un modèle Les algorithmes génétiques imitent les
principes darwiniens de sélection naturelle en créant un
environnement dans lequel des centaines de solutions possibles à un
problème rivalisent les unes avec les autres, avec survie de « la plus
apte ». Comme dans l’évolution biologique, chaque solution transmet
ses bons « gènes » à ses solutions « descendantes », de sorte que la
population de solutions tout entière continue à évoluer vers de
meilleures solutions.
Vous l’avez compris, la terminologie des algorithmes génétiques est
souvent similaire à celle du domaine dont elle est inspirée. Les
fonctions de « croisement » aident à concentrer la recherche de
solutions ; les taux de « mutation » contribuent à la diversification du
« capital génétique » ; et l’évaluation porte sur l’ensemble de la
« population » de solutions ou « organismes ». Pour plus de détails
sur le fonctionnement des algorithmes génétiques d’Evolver, voir le
Chapitre 7 – Algorithmes génétiques.
14
Qu’est-ce qu’Evolver ?
Qu’est-ce que l’optimisation ?
L’optimisation est le processus qui consiste à rechercher la meilleure
solution à un problème présentant de nombreuses solutions possibles.
La plupart des problèmes impliquent de nombreuses variables
interdépendantes basées sur des formules et des contraintes données.
Supposons par exemple une entreprise comptant trois usines,
fabriquant chacune différentes quantités de différents produits. Étant
donné le coût de production de chaque produit par chaque usine, les
coûts de livraison de chaque usine à chaque débouché des produits et
les limites de chaque usine, quelle est la formule optimale qui
permettrait de répondre adéquatement à la demande des magasins de
détail locaux tout en minimisant les coûts de transport ? Il s’agit là du
type de question auquel les outils d’optimisation sont censés
répondre.
L’optimisation consiste souvent à rechercher la
combinaison la plus rentable compte tenu de ressources données.
Dans l’exemple ci-dessus, chaque solution proposée consisterait en
une liste complète indiquant quels produits fabriqués par quelle usine
sont expédiés dans quel camion vers quel magasin. D’autres
problèmes d’optimisation pourraient chercher, par exemple, comment
réaliser le plus grand bénéfice, le moindre coût, le plus grand nombre
de vies sauvées, le moins de bruit dans un circuit, le chemin le plus
court entre différentes villes, ou la combinaison la plus rentable
d’achats de médias publicitaires. Un sous-ensemble important de
problèmes d’optimisation concerne la planification d’horaires ou de
programmes, le but étant de maximiser l’efficacité d’un poste de
travail ou de minimiser les conflits de rencontre de groupes. Pour
plus de détails sur l’optimisation, voir le Chapitre 6 – Optimisation.
Chapitre 2 : Principes
15
Pourquoi bâtir des modèles Excel ?
Si l’on veut accroître l’efficacité d’un système, il faut d’abord en
comprendre le comportement. Là se trouve l’utilité de la construction
d’un modèle fonctionnel du système. Les modèles sont les
abstractions nécessaires à l’étude de systèmes complexes. Pour que les
résultats restent applicables au « monde réel », le modèle doit
cependant éviter de simplifier à l’excès les rapports de cause à effet
entre ses variables. De meilleurs logiciels et des ordinateurs de plus
en plus puissants permettent aux économistes de bâtir des modèles
plus réalistes de la conjoncture ; aux scientifiques, d’améliorer leurs
prédictions de réactions chimiques et aux gestionnaires, d’accroître la
sensibilité de leurs modèles d’entreprise.
Ces dernières années, le matériel informatique et les programmes
logiciels tels que Microsoft Excel ont progressé à une telle allure qu’il
suffit pour ainsi dire aujourd’hui de disposer d’un ordinateur
personnel pour créer des modèles réalistes de systèmes complexes.
Les fonctions intégrées d’Excel, ses capacités de macros et son
interface rationnelle et intuitive permettent même aux débutants de
modéliser et d’analyser des problèmes de haut niveau. Pour plus de
détails sur l’élaboration d’un modèle, voir le Chapitre 9 – Et aussi…
Pourquoi Evolver ?
La technologie unique d’Evolver met les avantages de l’optimisation à
la portée de tout utilisateur de PC et d’Excel pour Windows. Avant
Evolver, trois choix s’offraient à toute personne désireuse d’accroître
l’efficacité d’un processus ou d’identifier les solutions optimales à un
problème : deviner, faire appel à un solveur logiciel de faible
envergure ou engager les services d’experts de l’optimisation pour la
conception et l’élaboration d’un logiciel personnalisé. Grâce à
Evolver, la situation a aujourd’hui bien changé. Pour ne citer que
quelques-uns de ses principaux avantages :
16
Qu’est-ce qu’Evolver ?
Plus question de
« deviner »
En présence de nombreuses variables interactives, il peut être tentant,
pour trouver la meilleure combinaison, le meilleur ordre ou le
groupement optimal de ces variables, de procéder par « supposition
éclairée ». Un nombre surprenant de personnes croient que toute
forme de modélisation et d’analyse au-delà de la supposition exige
une programmation compliquée ou le recours à de complexes
statistiques ou algorithmes mathématiques. Une bonne solution
optimisée peut pourtant épargner des millions d’euros, des milliers de
litres de combustible rare, des mois de travail inutile, etc. Maintenant
que de puissants ordinateurs et logiciels de bureau tels qu’Excel et
Evolver sont à la portée de tous, la simple supposition, ou la perte de
temps précieux à essayer différents scénarios, ne se justifient plus.
Plus précis et
plus utile
Evolver permet le recours à toutes les formules et même aux macros
d'Excel pour l’élaboration de modèles plus réalistes, quel que soit le
système représenté. Avec Evolver, le « compromis » n’est pas
nécessaire, car l’algorithme choisi peut gérer les complexités du
monde réel. Les « mini-solveurs » conventionnels (outils statistiques
et de programmation linéaire) obligent l’utilisateur à supposer
l’interaction entre les variables d’un problème, imposant dès lors la
création de modèles par trop simplistes et peu réalistes. Une fois le
système suffisamment simplifié pour permettre l’usage de ces
solveurs, la solution résultante est souvent plus abstraite que
pratique. Les problèmes présentant de nombreuses variables,
fonctions non linéaires, tables de recherche, déclarations
conditionnelles, interrogations de base de données ou éléments
stochastiques (aléatoires) sont exclus de ces méthodes, quel que soit le
degré de simplification du modèle.
Plus souple
Beaucoup d’algorithmes conviennent à la résolution de simples
problèmes linéaires et non linéaires, qu’ils procèdent par escalade,
mini-solveur ou autres approches mathématiques. Même proposés
sous forme de compagnons ou compléments de tableur, ces outils
d’optimisation universels ne gèrent que l’optimisation numérique.
Pour les problèmes plus vastes ou plus complexes, il est parfois
possible de formuler des algorithmes personnalisés, au prix de
longues opérations de recherche et développement toutefois. Dans
cette éventualité même, le programme résultant doit être modifié à
chaque changement de modèle !
Chapitre 2 : Principes
17
Evolver gère en revanche les problèmes numériques et est le seul
programme commercial au monde apte à résoudre la plupart des
problèmes combinatoires. Ces problèmes sont ceux où les variables
doivent être réorganisées (par permutation) ou combinées les unes
avec les autres. Par exemple, choisir l’ordre des joueurs à la batte,
pour une équipe de baseball, est un problème de nature combinatoire.
Les problèmes de planification complexes aussi. Le seul et même
Evolver peut résoudre tous ces types de problèmes et bien d’autres
encore qu’aucun autre programme ne peut aborder. La technologie
unique des algorithmes génétiques proposée par Evolver permet
d’optimiser pratiquement tous les types de modèles, aussi
volumineux et complexes soient‐ils.
Plus puissant
Evolver trouve de meilleures solutions. La plupart des logiciels
dérivent mathématiquement et systématiquement leurs solutions
optimales. Trop souvent, ces méthodes se limitent à la considération
d’une solution existante et à la recherche de la meilleure réponse la
plus proche. Or, cette solution « locale » peut être loin d’être la
solution optimale. Evolver échantillonne intelligemment toutes les
possibilités envisageables et produit dès lors une solution « globale »
bien meilleure.
Plus convivial
Malgré ses avantages de puissance et de souplesse manifestes,
Evolver reste convivial et simple d’emploi, car il n’est pas nécessaire
de comprendre les techniques complexes des algorithmes génétiques
sur lesquelles il repose. Evolver ne s’inquiète pas des menus détails
du problème : il lui faut simplement un modèle de tableur apte à
évaluer la qualité des différents scénarios. Il suffit de sélectionner les
cellules qui contiennent les variables et d’indiquer à Evolver l’objectif
recherché. Evolver masque intelligemment la difficulté de la
technologie, présentant comme automatique l’analyse hypothétique
du problème.
18
Qu’est-ce qu’Evolver ?
Beaucoup de programmes commerciaux ont été développés pour la
programmation mathématique et l’élaboration de modèles, mais les
tableurs sont de loin les plus appréciés et se vendent, littéralement,
comme des petits pains. Leur format intuitif en lignes et colonnes les
rend plus faciles à configurer et à gérer que les autres progiciels
spécialisés. Ils offrent également une meilleure compatibilité avec
d’autres programmes, tels que traitements de texte et bases de
données, et proposent plus de formules intégrées, options de
formatage, capacités graphiques et de macros que les systèmes
autonomes. Compagnon et complément de Microsoft Excel, Evolver
donne accès à toute la gamme de fonctions et outils de
développement d’Excel, pour une modélisation plus simple et plus
réaliste.
Rentable
Quantité d’entreprises ont engagé les services d’experts-conseils
chargés du développement de systèmes d’optimisation personnalisés.
S’ils répondent généralement adéquatement aux besoins définis, ces
systèmes exigent souvent, outre un investissement monétaire
considérable, de nombreux mois de développement et mise en œuvre.
Ils sont souvent difficiles à apprendre et requièrent de vastes budgets
de formation et une maintenance constante. Le moindre changement
peut exiger la définition d'un tout nouvel algorithme. Pour un
investissement largement inférieur, Evolver apporte l'avantage des
algorithmes génétiques les plus puissants aujourd’hui disponibles et
assure la production de solutions rapides et précises à un large
éventail de problèmes. Son interface intuitive et familière élimine
pratiquement tous coûts de formation et de maintenance.
Rien ne vous empêche même d'ajouter la puissance d'optimisation
d'Evolver à vos propres programmes personnalisés. En l’espace de
quelques jours à peine, vous pouvez, à l’aide de Visual Basic,
développer votre propre système de planification, distribution,
fabrication ou gestion financière. Voir le Kit du développeur Evolver
pour plus de détails sur l’élaboration d’une application Evolver.
Chapitre 2 : Principes
19
20
Chapitre 3 : Evolver : Pas à pas
Introduction .......................................................................................23
Visite guidée......................................................................................25
Démarrer Evolver ...................................................................................25
La barre d’outils Evolver .........................................................25
Ouverture d’un modèle type ..................................................25
La boîte de dialogue Evolver – Modèle..............................................26
Sélectionner la cellule cible .................................................................27
Ajouter les plages de cellules ajustables ...........................................27
Méthode de résolution.............................................................30
Contraintes ..............................................................................................31
Ajout de contrainte...................................................................32
Simple plage de valeurs ou Formule ....................................32
Autres options Evolver..........................................................................35
Conditions d'arrêt.....................................................................35
Options d’affichage..................................................................36
Exécuter l’optimisation .........................................................................37
Suivi Evolver .............................................................................38
Arrêt de l’optimisation ............................................................39
Rapport de synthèse.................................................................40
Placement des résultats dans le modèle ...............................41
Chapitre 3 : Evolver : Pas à pas
21
22
Introduction
Ce chapitre suit, pas à pas, une optimisation complète sous Evolver. Si
Evolver n’est pas installé sur votre disque dur, reportez-vous à la
section du Chapitre 1 : Introduction consacrée à l’installation et
installez Evolver avant d’entreprendre ce didacticiel.
Nous commencerons par ouvrir un modèle de calcul prédéfini, pour
définir le problème à Evolver à l’aide de distributions de probabilités
et des boîtes de dialogue Evolver. Nous suivrons ensuite la
progression d’Evolver dans sa recherche de solutions et nous
explorerons quelques-unes des nombreuses options de Suivi Evolver.
Pour plus de détails sur une rubrique abordée ici, voir l’index en fin
de manuel ou le Chapitre 5 : Guide de référence Evolver.
REMARQUE : Les écrans illustrés ci-dessous sont extraits d’Excel
2007. Les fenêtres d’autres versions d’Excel seront peut-être
légèrement différentes.
Le processus de résolution commence par l’élaboration d’un modèle
qui représente précisément le problème. Ce modèle doit pouvoir
évaluer un ensemble donné de valeurs en entrée (les cellules
ajustables) et produire une cote numérique indicatrice de la qualité de
la solution produite sous ces valeurs (évaluation ou fonction de
« pertinence »). Tandis qu’Evolver recherche les solutions possibles, la
fonction de pertinence lui renvoie une indication de la qualité ou non
de chaque supposition, permettant ainsi à Evolver d’améliorer en
permanence ses suppositions. Lors de la création du modèle d’un
problème, la fonction de pertinence revêt une extrême importance en
ce qu’Evolver n’a de cesse de maximiser (ou minimiser) la cellule
concernée.
Chapitre 3 : Evolver : Pas à pas
23
24
Visite guidée
Démarrer Evolver
La barre d’outils
Evolver
Ouverture d’un
modèle type
Pour lancer Evolver : 1) cliquez sur l’icône Evolver sur le bureau
Windows ou 2) choisissez Palisade DecisionTools puis Evolver 5.0
dans la liste des programmes listés sous le menu Démarrer de
Windows. Ces deux méthodes démarrent chacune Microsoft Excel et
Evolver.
Lorsqu’Evolver est chargé, un nouveau ruban ou une nouvelle barre
d’outils s’affiche dans Excel. Cette barre contient les boutons de
commande d’Evolver, pour la spécification des paramètres et le
démarrage, la pause et l’arrêt des optimisations.
Pour passer en revue les fonctionnalités d’Evolver, nous allons
examiner un modèle type installé lors de l’installation du
programme :
1) Sous la commande Exemples du menu d’Aide, ouvrez la feuille de
calcul Boulangerie – Didacticiel.XLS.
Chapitre 3 : Evolver : Pas à pas
25
Cet exemple présente un simple problème de maximisation du profit
pour une boulangerie. La boulangerie produit 6 types de pain. Vous
êtes responsable de la boulangerie et du suivi des revenus, coûts et
profits de la production. Vous devez déterminer le nombre de caisses
de chaque type de pain apte à maximiser le bénéfice total tout en
respectant les directives de limite de production. Vos directives sont
les suivantes : vous devez 1) respecter le quota de pain hypocalorique, 2)
maintenir un rapport acceptable entre pain riche en fibres et pain
hypocalorique, 3) maintenir un rapport acceptable entre le pain 5 céréales et
le pain hypocalorique et 4) respecter les heures-personnes de production
fixées.
La boîte de dialogue Evolver – Modèle
Pour configurer les options Evolver de notre feuille de calcul :
1) Cliquez sur l’icône Définition du modèle de la barre d’outils
Evolver (à l’extrême gauche).
La boîte de dialogue Evolver – Modèle illustrée ci-dessous s’ouvre :
Cette boîte est conçue pour permettre à l’utilisateur de décrire le
problème de manière simple et directe. Nous cherchons, dans notre
exemple, à déterminer le nombre de caisses de chaque type de pain à
produire pour maximiser le bénéfice total global.
26
Visite guidée
Sélectionner la cellule cible
Le « bénéfice total », dans notre exemple, représente la « cellule
cible ». Cette cellule est celle dont la valeur doit être minimisée ou
maximisée, ou dont la valeur doit se rapprocher autant que possible
d’une valeur prédéfinie. Pour spécifier la cellule cible :
1) Pour « But d’optimisation », choisissez l’option « Maximum ».
2) Entrez la cellule cible, $I$11, dans le champ « Cellule ».
Les références de cellule peuvent être entrées dans les champs des
boîtes de dialogue Evolver de deux manières : 1) Cliquez dans le
champ et tapez-y directement la référence de la cellule, ou 2) curseur
dans le champ sélectionné, cliquez sur l’icône d’entrée de référence
pour sélectionner la ou les cellules voulues directement dans la feuille
de calcul à l’aide de la souris.
Ajouter les plages de cellules ajustables
L’étape suivante consiste à spécifier l’emplacement des cellules qui
contiennent les valeurs qu’Evolver peut faire varier, ou « ajuster »,
dans sa recherche de solutions. Ces variables s’ajoutent et se
modifient, un bloc à la fois, dans le volet Plages de cellules ajustables de
la boîte de dialogue Modèle. Le nombre de cellules admis dépend de
la version Evolver utilisée.
1) Cliquez sur le bouton « Ajouter » dans le volet « Plages de cellules
ajustables ».
2) Sélectionnez $C$4:$G$4 comme cellules Excel à ajouter comme
plage de cellules ajustables.
Chapitre 3 : Evolver : Pas à pas
27
Plage Min-Max
de cellules
ajustables
Il convient, dans la plupart des cas, de restreindre les valeurs
possibles d’une plage de cellules ajustables à une plage minimummaximum spécifique. Il s’agit là, en jargon Evolver, d’une contrainte
de « plage ». Cette plage se définit rapidement lors de la sélection de
l’ensemble de cellule à ajuster. Dans l’exemple qui nous occupe, la
valeur minimum possible de caisses produits par type de pain dans
cette plage est 0 et la valeur maximum, 100 000. Pour définir cette
contrainte de plage :
1) Entrez 0 dans la cellule Minimum et 100 000 dans la cellule
Maximum.
2) Pour la cellule Valeurs, sélectionnez Entiers dans la liste
déroulante.
28
Visite guidée
Entrez maintenant une deuxième plage de cellules à ajuster :
1) Cliquez sur Ajouter.
2) Sélectionnez la cellule B4.
3) Entrez 20 000 comme Minimum et 100 000 comme Maximum.
On spécifie ainsi la dernière cellule ajustable, B4, représentant le
niveau de production de pain hypocalorique.
Si le problème comportait d’autres variables encore, on continuerait à
ajouter des cellules ajustables. Evolver admet un nombre illimité de
groupes de cellules ajustables. Il suffit, pour chacun, de cliquer sur le
bouton « Ajouter ».
Si vous décidez plus tard de vérifier les cellules ajustables ou d’en
changer les paramètres, il suffit de modifier la plage min-max dans ce
tableau. Le bouton « Supprimer » permet aussi de supprimer un
ensemble de cellules sélectionné.
Chapitre 3 : Evolver : Pas à pas
29
Méthode de
résolution
La méthode de résolution à utiliser peut être spécifiée lors de la
définition des cellules ajustables. Différentes méthodes de résolution
gèrent différents types de cellules ajustables. Les méthodes se
définissent pour un Groupe de cellules ajustables et se modifient en
cliquant sur le bouton « Groupe » pour afficher la boîte de dialogue
Paramètres du groupe de cellules ajustables. La méthode par défaut
« recette » convient généralement. Cette méthode permet le
changement de valeur de chaque cellule indépendamment des autres.
Cette méthode est sélectionnée par défaut. Il est donc inutile de la
changer ici.
Les méthodes de résolution « recette » et « ordre » sont les plus
courantes et peuvent être utilisées ensemble pour la résolution de
problèmes combinatoires compliqués. Plus spécifiquement la
méthode « recette » traite chaque variable comme s’il s’agissait d’un
ingrédient d’une recette, essayant de trouver la « meilleure
combinaison » en changeant indépendamment la valeur de chaque
variable. En revanche, la méthode « ordre » permute les valeurs des
variables, réorganisant les valeurs originales à la recherche du
« meilleur ordre ».
Pour ce modèle, nous allons conserver la méthode de résolution
Recette et
♦
30
entrer simplement « Caisses produites » dans le champ
Description.
Visite guidée
Contraintes
Evolver admet les contraintes, qui définissent les conditions à remplir
pour qu’une solution soit valable. Dans notre exemple, trois autres
contraintes doivent être satisfaites pour assurer la validité d’un
ensemble possible de niveaux de production par type de pain. Ces
contraintes sont complémentaires à celles de plage définies plus haut
pour les cellules ajustables. Elles se définissent comme suit :
1) Maintien d’un rapport acceptable entre les types de pain riche
en fibres et hypocalorique (caisses fibres produites >= 1,5 *
caisses hypocaloriques produites).
2) Maintien d’un rapport acceptable entre les types de pain
5 céréales et hypocalorique (caisses 5 céréales produites >= 1,5 *
caisses hypocaloriques produites).
3) Respect des limites d’heures-personnes de production (total
d’heures-personnes < 50 000).
À chaque génération de solution possible au problème, Evolver vérifie
le respect des contraintes définies.
Les contraintes s’affichent au bas du volet Contraintes de la boîte de
dialogue Evolver – Modèle. Evolver admet deux types de contraintes :
♦
Ferme. Les contraintes fermes sont les conditions qui doivent être
satisfaites pour qu’une solution soit valable. Par exemple, une
contrainte d’itération ferme pourrait être exprimée sous la forme
C10<=A4, et si une solution générait une valeur C10 supérieure à
celle de la cellule A4, la solution serait rejetée.
♦
Souple. Les contraintes souples sont les conditions que l’on veut
respecter autant que possible, mais pour lesquelles on est prêt à
accepter le compromis en vue d’une importante amélioration de
pertinence ou de résultat de cellule cible. Par exemple, une
contrainte souple pourrait être exprimée sous la forme C10<100.
Dans ce cas, C10 pourrait dépasser la valeur 100, mais la valeur
calculée de la cellule cible serait alors diminuée conformément à
la fonction de pénalité définie.
Chapitre 3 : Evolver : Pas à pas
31
Ajout de
contrainte
Pour ajouter une contrainte :
1) Cliquez sur le bouton Ajouter du volet Contraintes, dans la boîte
de dialogue Evolver principale.
La boîte de dialogue Paramètres de contrainte s’ouvre, pour la
définition des contraintes du modèle.
Simple plage de
valeurs ou
Formule
Les contraintes peuvent être définies selon deux formats : Simple ou
Formule. Le format Simple plage de valeurs permet la définition des
contraintes selon de simples relations <, <=, >, >= ou =. Par exemple :
0<Valeur de A1<10, où A1 s’entre dans la case Plage, 0 dans la case Min
et 10 dans la case Max. Les opérateurs désirés se sélectionnent dans
les listes déroulantes. Sous une contrainte de format « Simple », on
peut entrer une valeur Min, une valeur Max, ou les deux.
Le format Formule permet en revanche l’entrée, pour la contrainte,
d’une formule Excel correcte, telle que A19<(1,2*E7)+E8. Pour chaque
solution possible, Evolver vérifie si la formule entrée est VRAIE ou
FAUSSE, afin de déterminer le respect ou non de la contrainte. Pour
utiliser une formule booléenne de cellule de feuille de travail comme
contrainte, il suffit de faire référence à cette cellule dans le champ
Formule de la boîte de dialogue Paramètres de contrainte.
32
Visite guidée
Nous allons, pour notre modèle de boulangerie, spécifier trois
nouvelles contraintes fermes. Il s’agit de contraintes fermes car les
conditions définies doivent être satisfaites pour qu’Evolver accepte
une solution possible. Commencez par configurer une contrainte
ferme de style Simple :
1) Entrez « Total d’heures de travail acceptable » comme
description.
2) Dans la case Plage sous contrainte, entrez I8.
3) Sélectionnez l’opérateur <= à droite de Plage sous contrainte.
4) Entrez 50 000 dans la case Maximum.
5) Supprimez la valeur par défaut 0 de la case Minimum.
6) À gauche de Plage sous contrainte, supprimez l’opérateur en
sélectionnant l’option blanche dans la liste déroulante.
7) Cliquez sur OK pour valider cette contrainte.
Chapitre 3 : Evolver : Pas à pas
33
Sélectionnez maintenant le format Formule de contrainte ferme :
1) Cliquez sur Ajouter pour rouvrir la boîte de dialogue Paramètres
de contrainte.
2) Entrez « Rapport acceptable fibres/hypocalorique » comme
description.
3) Sélectionnez le style Formule.
4) Dans la zone Formule de contrainte, entrez C4>= 1,5*B4.
5) Cliquez sur OK.
6) Cliquez sur Ajouter pour rouvrir la boîte de dialogue Paramètres
de contrainte.
7) Entrez « Rapport acceptable 5 grains/hypocalorique » comme
description.
8) Sélectionnez le style Formule.
9) Dans la zone Formule de contrainte, entrez D4>= 1,5*B4.
10) Cliquez sur OK.
La boîte de dialogue résultante doit se présenter comme suit :
34
Visite guidée
Autres options Evolver
Les options telles qu’Actualiser l’affichage, Racine de nombres aléatoires et
Arrêt d’optimisation permettent de gérer le fonctionnement d’Evolver en
cours d’optimisation. Précisons donc quelques conditions d’arrêt et
paramètres d’actualisation de l’affichage.
Conditions d'arrêt
Evolver s’exécute aussi longtemps que vous le désirez. Les conditions
d’arrêt gèrent l’arrêt automatique d’Evolver lorsque a) un certain
nombre de scénarios ou d’ « essais » a été examiné, b) un certain temps s’est
écoulé, c) les n derniers scénarios n’ont produit aucune amélioration ou d) la
formule Excel entrée est VRAIE. Pour afficher et modifier les conditions
d’arrêt :
1) Cliquez sur l’icône Paramètres d’optimisation de la barre d’outils
Evolver.
2) Cliquez sur l’onglet Temps d’exécution.
Dans la boîte de dialogue Paramètres d’optimisation, vous pouvez
sélectionner une combinaison quelconque de conditions d’arrêt. Vous
pouvez aussi choisir de n’en sélectionner aucune. Si vous sélectionnez
plusieurs conditions d’arrêt, Evolver s’arrête lorsque l’une d’entre
elles est remplie. Si vous ne sélectionnez aucune condition d’arrêt,
Evolver s’exécute indéfiniment, jusqu’à ce que vous l’arrêtiez
manuellement en cliquant sur le bouton Arrêter de la barre d’outils.
Chapitre 3 : Evolver : Pas à pas
35
Essais
Minutes
Cette option définit
le nombre
d’« essais » à
exécuter. À chaque
essai, Evolver
évalue un ensemble
complet de
variables ou une
solution possible au
problème.
Evolver s’arrête au
terme de la durée
de temps spécifiée.
Cette valeur peut
être une fraction
(4,25).
♦
Options
d’affichage
36
Progrès
Cette condition
d’arrêt est la plus
appréciée car elle
suit l’amélioration
du processus et
permet à Evolver
de continuer
jusqu’à ce que le
degré
d’amélioration se
réduise. Par
exemple, Evolver
pourrait s’arrêter
au bout de 100
essais si aucune
nouvelle
amélioration n’est
apparue par
rapport au dernier
scénario optimal.
Formule vraie
Evolver s’arrête si
la formule Excel
entrée s’avère
VRAIE dans un
recalcul du modèle.
N'activez aucune condition d’arrêt pour laisser Evolver
s’exécuter librement.
En cours d’exécution d’Evolver, les options de l’onglet Affichage
déterminent ce que vous voyez à l’écran.
Visite guidée
Les options d’actualisation suivantes sont proposées sous le titre
Pendant l’optimisation :
A chaque essai
A chaque meilleur essai
Jamais
Cette option actualise
l’affichage après chaque
calcul et vous permet de
voir Evolver ajuster les
variables et calculer la
sortie. Nous la
recommandons pendant la
période d’apprentissage
d’Evolver, ainsi qu’à
chaque utilisation
d’Evolver sur un nouveau
modèle, pour vous
permettre d’en vérifier le
calcul correct.
Cette option actualise
l’écran chaque fois
qu’Evolver produit une
nouvelle meilleure
réponse, pour vous
permettre de toujours voir
la solution optimale
courante pendant
l’optimisation.
Cette option n’actualise
jamais l’écran en cours
d’optimisation. Elle
accélère le processus mais
n'offre guère d’information
sur les résultats calculés
pendant l’exécution.
♦
Sélectionnez l’option « À chaque essai ».
Exécuter l’optimisation
Il ne reste plus qu’à optimiser notre modèle de maximisation du
bénéfice total conformément aux contraintes de production :
1) Cliquez sur OK pour fermer la boîte de dialogue Paramètres
d’optimisation.
2) Cliquez sur l’icône Démarrer l’optimisation.
Tandis qu’Evolver se lance dans la résolution du problème, les
meilleures valeurs actuelles des cellules variables – Caisses produites –
s’affichent sur la feuille de calcul. La meilleure valeur de Bénéfice total
s'affiche dans la cellule en surbrillance.
Chapitre 3 : Evolver : Pas à pas
37
La fenêtre de progression suit l’exécution et affiche : 1) la meilleure
solution trouvée jusque là, 2) la valeur originale de la cellule cible en
début d’optimisation par Evolver, 3) le nombre d’essais du modèle
exécutés et le nombre de ceux acceptés comme valables (où toutes les
contraintes ont été satisfaites) et 4) le temps d’optimisation écoulé.
À tout moment pendant l’exécution, l’icône Afficher les options
d’actualisation Excel permet de visualiser chaque essai en direct à
l’écran.
Suivi Evolver
Evolver peut aussi afficher un journal courant des essais réalisés pour
chaque solution itérative. Ce journal s’affiche dans la fenêtre Suivi
Evolver en cours d’exécution. Le système Suivi Evolver vous permet
d’explorer et de modifier de nombreux aspects de votre problème en
cours d’exécution. Pour afficher le journal courant des essais
effectués :
1) Cliquez sur l’icône Suivi (loupe) dans la fenêtre de progression.
2) Cliquez sur l’onglet Journal.
Ce rapport présente les résultats de la simulation exécutée pour
chaque solution itérative. La colonne Résultat indique, par essai, la
valeur de la cellule cible à maximiser ou minimiser – en l’occurrence,
Bénéfice total dans $I$11. Les colonnes C4 et G4 identifient les valeurs
utilisées pour les cellules ajustables.
38
Visite guidée
Arrêt de
l’optimisation
Au bout de cinq minutes, Evolver arrête l’optimisation. Vous pouvez
aussi arrêter l’optimisation en
1) cliquant sur l’icône Arrêter dans la fenêtre Suivi Evolver ou dans
celle de progression.
À l’arrêt du processus, Evolver affiche l’onglet Options d’arrêt. Les
choix suivants y sont proposés :
Ces mêmes options s’affichent automatiquement lorsqu’une condition
d’arrêt quelconque de la boîte de dialogue Paramètres d’optimisation
est remplie.
Chapitre 3 : Evolver : Pas à pas
39
Rapport de
synthèse
Evolver peut créer un rapport de synthèse d’optimisation faisant état
des date et heure de l’exécution, des paramètres d’optimisation
utilisés, de la valeur calculée pour la cellule cible et de la valeur de
chaque cellule ajustable.
Ce rapport est utile à la comparaison des résultats d’optimisations
successives.
40
Visite guidée
Placement des
résultats dans le
modèle
Pour placer la nouvelle combinaison optimisée de niveaux de
production de la boulangerie pour chacun des six types de pain dans
la feuille de calcul :
1) Cliquez sur le bouton « Arrêter ».
2) Sélectionnez l’option « Actualiser les valeurs de cellules
ajustables affichées dans le classeur aux valeurs » « Meilleures ».
La feuille de calcul Boulangerie-Didacticiel.xls réapparaît, garnie de
toutes les nouvelles valeurs variables à l’origine de la meilleure
solution.
REMARQUE IMPORTANTE : Bien que notre exemple ait produit une
solution présentant un bénéfice total de 3 940 486, votre résultat
pourra être supérieur ou inférieur à cette valeur. Ces différences
s’expliquent par l’importante distinction qui sépare Evolver de tous
les autres algorithmes de résolution de problèmes : c’est la nature
aléatoire du moteur d’algorithmes génétiques d’Evolver qui lui
permet de résoudre une plus grande variété de problèmes et d’y
trouver de meilleures solutions.
Chapitre 3 : Evolver : Pas à pas
41
Lorsque vous enregistrez une feuille après l’exécution d’Evolver (et
même si vous en « rétablissez » les valeurs originales après cette
exécution), tous les paramètres Evolver configurés dans les boîtes de
dialogue du programme s’enregistrent avec cette feuille. À
l’ouverture suivante de la feuille, tous les paramètres les plus récents
d’Evolver se chargent ainsi automatiquement. Tous les autres
exemples de feuilles de calcul sont déjà dotés des paramètres Evolver
et sont prêts à être optimisés.
REMARQUE : Si vous désirez consulter le modèle Boulangerie déjà
assorti de tous ses paramètres d’optimisation, ouvrez le fichier
d’exemple Boulangerie.XLS.
42
Visite guidée
Chapitre 4 : Applications types
Introduction ...................................................................................... 45
Sélection publicitaire ....................................................................... 47
Ordre alphabétique .......................................................................... 49
Affectation de tâches ....................................................................... 53
Boulangerie....................................................................................... 55
Allocation budgétaire....................................................................... 57
Équilibre chimique ........................................................................... 59
Planificateur de classes .................................................................. 61
Segmenteur de code ........................................................................ 65
Dakota : Itinéraires sous contraintes ............................................. 69
Ordonnancement multigamme ....................................................... 73
Emplacement de pylônes radio ...................................................... 75
Équilibrage de portefeuilles ............................................................ 77
Composition de portefeuille............................................................ 81
Émetteurs radio ................................................................................ 83
Achat ................................................................................................. 85
Problème du voyageur de commerce ............................................ 87
Navigateur spatial ............................................................................ 89
Opérateur en bourse ........................................................................ 91
Transformateur................................................................................. 93
Transports......................................................................................... 95
Chapitre 4 : Applications types
43
44
Introduction
Dans ce chapitre, vous trouverez différentes applications d’Evolver.
Ces exemples ne couvrent pas nécessairement toutes les
fonctionnalités qui vous intéressent. Leur but serait plutôt de servir de
modèles et d’éveiller de nouvelles idées. Tous les exemples présentés
illustrent la manière dont Evolver recherche ses solutions sur la base
des relations existantes dans la feuille de calcul. Veillez par
conséquent à ce que vos modèles représentent précisément le
problème à résoudre.
Tous les exemples de feuille de calcul Excel présentés ici se trouvent
dans le répertoire EVOLVE32, sous-répertoire « EXEMPLES ». Tous
suivent les conventions de couleur suivantes :
♦ cellules surlignées en bleu . . . . .
cellules ajustables qu’Evolver
fera varier.
♦ cellule surlignée en rouge . . . . .
cellule cible.
Tous les paramètres Evolver voulus sont présélectionnés dans chaque
exemple : cellule cible, cellules ajustables, méthodes de résolution et
contraintes. Ne manquez pas d’examiner ces paramètres dans leur
boîte de dialogue avant de lancer l’optimisation. En examinant les
formules et en essayant différents paramètres, vous comprendrez et
maîtriserez mieux le fonctionnement d’Evolver. Les modèles proposés
vous permettent aussi de remplacer les données d’échantillon par vos
propres données « utilisateur ». Si vous décidez de modifier ou
d’adapter ces feuilles d’exemple, enregistrez-les sous un autre nom
pour conserver les versions originales pour référence.
Chapitre 4 : Applications types
45
46
Sélection publicitaire
Une agence de publicité doit déterminer l’allocation la plus rentable
de son budget pour maximiser la couverture de son audience cible.
Elle ne doit pas dépasser le budget et le montant alloué à la télévision
doit être supérieur à celui affecté à la radio.
Fichier de l’exemple :
Sélection publicitaire.xls
But :
Répartir les achats de publicité, dans le cadre du
budget imparti, parmi différents médias à tarifs
distincts. Maximiser l'audience atteinte.
Méthode de résolution :
budget
Problèmes similaires :
Problèmes de nature budgétaire avec autres
contraintes.
Chapitre 4 : Applications types
47
Modèle
La première chose à faire consiste à choisir une méthode de résolution
qui indique à Evolver comment traiter les variables. Voir le
Chapitre 5 : Guide de référence pour une description complète des
différentes méthodes de résolution.
Nous avons ici essentiellement un problème de type budget, avec la
contrainte supplémentaire que les dépenses TV doivent être
supérieures aux dépenses radio.
Résolution
48
Les variables à ajuster occupent les cellules C5:C9. Evolver va les faire
varier selon la méthode « budget », permettant à chacune de rester
une valeur indépendante. L’audience totale est calculée par la
fonction SOMME dans la cellule G13, que nous désignons comme
cellule à maximiser. Les contraintes fermes spécifient que les
dépenses TV doivent être supérieures à celles affectées à la publicité à
la radio.
Sélection publicitaire
Ordre alphabétique
Cet exemple présente une liste de sept noms à organiser en ordre
alphabétique. Il s’agit ici d’un exemple simple, mais Evolver pourrait
tout aussi bien traiter des tris complexes avec données
interdépendantes ou pondérations différentes en fonction d’autres
informations du modèle.
Fichier de l’exemple :
Ordre alphabétique.xls
But :
Mettre la liste de noms en ordre alphabétique.
Méthode de résolution :
ordre
Problèmes similaires :
Tout problème de tri au-delà des capacités
d’Excel.
Chapitre 4 : Applications types
49
Modèle
Le fichier « Ordre alphabétique.xls » présente une modèle très simple
appelé à illustrer les capacités de tri d'Evolver. La colonne B contient
les prénoms de sept personnes et la colonne A, le numéro
d'identification « ID » correspondant de chaque personne. La colonne
D utilise la fonction Excel RECHERCHEV pour convertir le nombre
choisi dans la colonne C en son nom correspondant. Les cellules E4:E9
appliquent une simple fonction de pénalisation qui affecte la valeur 1
chaque fois qu’un nom antérieur est classé après un nom ultérieur de
la liste. La somme de toutes les erreurs figure dans la cellule E11,
désignée comme cellule cible.
Résolution
Dans ce modèle, les variables à ajuster occupent les cellules de la
colonne C (C3:C9). On demande à Evolver de jongler avec les valeurs
des cellules C3:C9 selon la méthode de résolution « ordre ». Sous cette
méthode, Evolver réorganise l’ordre des valeurs sélectionnées, par
permutations différentes des variables plutôt qu'essai de nouvelles
valeurs. On configure l’opération pour qu’Evolver recherche la valeur
la plus proche de 0 comme erreur totale dans la cellule E11. Dans la
cellule cible, cette valeur signifie en effet que tous les noms sont
classés dans l’ordre correct.
50
Ordre alphabétique
En ne sélectionnant aucun critère d’arrêt dans la boîte de dialogue
d’Options Evolver, on indique à Evolver de poursuivre l'opération
indéfiniment, jusqu'à arrêt manuel d’un clic sur le bouton d’arrêt de la
barre d’outils. Dans ce modèle, nous avons cependant sélectionné
l'option de valeur la plus proche. Evolver s'arrêtera donc
automatiquement s’il trouve une solution répondant au critère de
« valeur la plus proche » de 0.
Nous avons choisi une population réduite car, bien qu’il n’existe
aucune règle définitive quant au choix d’une population optimale, on
peut généralement sélectionner une population de moindre envergure
pour les problèmes qui présentent un nombre total réduit de solutions
possibles. L'opération se concentre ainsi plus rapidement sur la
production des solutions les plus performantes. Dans ce problème, il
n’existe que 5040 ordres possibles pour les 7 noms.
Chapitre 4 : Applications types
51
52
Affectation de tâches
Cet exemple modélise un problème courant d’allocation de
ressources. Dans ce problème, un manager dispose de 16 ouvriers
pour accomplir 16 tâches. L’aptitude de chaque ouvrier à accomplir
chaque tâche a été évaluée sur une échelle de 1 à 10 (1 = ne peut pas
accomplir la tâche ; 10 = excellente aptitude à accomplir la tâche). La
difficulté consiste ici à affecter chaque ouvrier à une tâche de façon à
maximiser la productivité globale du groupe.
Fichier de l’exemple :
Affectation de tâches.xls
But :
Affecter 16 ouvriers à 16 tâches de manière à
maximiser la rentabilité totale.
Méthode de résolution :
ordre
Problèmes similaires :
Problèmes d’affectation, planification de réunions
aux heures qui conviendraient le mieux à la
plupart des employés, identification des
meilleures machines pour la réalisation d'une
série de travaux.
Chapitre 4 : Applications types
53
Le modèle présente une grille de 16 cellules sur 16 occupant la plage
B4:Q19. L’aptitude de chaque ouvrier à accomplir chaque tâche y est
cotée sur une échelle de 1 à 10. La colonne de « tâche choisie » (S), à
droite de la grille, affecte arbitrairement chaque ouvrier à une tâche.
La colonne suivante (U) vérifie la tâche affectée et entre la cote de
l’ouvrier à cette tâche. Enfin, la cote totale de la solution intégrale
(cellule U21) représente la somme de toutes les cotes individuelles.
Modèle
Une seule personne ne peut être affectée à chaque tâche : aucun
nombre ne peut donc être redoublé, et chaque nombre doit être utilisé
une fois. La cote de chaque ouvrier à la tâche affectée s’inscrit dans la
colonne U selon la fonction INDEX(). Les cotes de la colonne U se
totalisent dans la cellule U21 pour déterminer la cote totale de
l'ensemble d'affectation considéré.
Résolution
Evolver est appelé à jongler avec les variables de « tâche choisie »
contenues dans la colonne S (S4:S19), selon la méthode « ordre ». Cette
méthode réorganise l’ordre des valeurs existantes de ces cellules. Il
importe donc de vérifier que chaque valeur ne soit représentée qu’une
fois avant de lancer l’optimisation. Evolver doit rechercher la valeur
maximum possible de la cellule U21, désignée comme cellule cible,
car plus cette valeur est élevée, plus l'affection générale est bonne.
54
Affectation de tâches
Boulangerie
Cet exemple illustre un problème courant de décision de production,
où la recherche de la quantité adéquate de chaque produit à produire
devient particulièrement difficile, même en présence de quelques
articles seulement. Un boulanger doit déterminer le nombre de caisses
de pains de différents types à produire pour maximiser le bénéfice
total de sa boulangerie. Il importe aussi de respecter les limites
applicables, telles que le nombre total d’heures-employés et les
rapports de production. (Remarque : Ce modèle est décrit en détail au
Chapitre 3 : Evolver Pas à pas.)
Fichier de l’exemple :
Boulangerie.xls
But :
Identifier la quantité optimale de chaque type de
pain à produire pour respecter tous les quotas et
maximiser les bénéfices.
Méthode de résolution :
recette
Problèmes similaires :
Composition de portefeuilles, planification de
production.
Chapitre 4 : Applications types
55
Modèle
Ce problème liste la quantité de chaque pain à produire sur la
première ligne du tableau (ligne 4). Lorsque ces variables de quantité
(B4:G4) sont ajustées, le modèle calcule les heures et les coûts
représentés, ainsi que le bénéfice qui résulterait de la production de
ces quantités. Le bénéfice (cellules B11:G11) est totalisé dans la cellule
I11, désigné comme cellule cible à maximiser.
Le modèle est aussi soumis à trois contraintes fermes : la première au
format de simple plage de valeurs, et les deux autres au format de
formules Excel.
Résolution
56
Evolver doit rechercher les valeurs des cellules B4:G4 (quantités à
produire) aptes à maximiser la valeur de la cellule I11 (bénéfice total).
Chaque valeur identifiée peut être indépendante des autres. On utilise
donc la méthode de résolution « recette ». Les contraintes applicables
aux cellules C4, D4 et I8 doivent aussi être respectées.
Boulangerie
Allocation budgétaire
Supposons qu’un haut cadre désire identifier le mode le plus efficace
de distribution de fonds entre les différents services de son entreprise
pour maximiser le bénéfice. Le modèle ci-dessous représente
l’entreprise et son bénéfice projeté pour l’année prochaine. Le modèle
estime ce bénéfice en examinant le budget annuel et en supposant, par
exemple, la manière dont la publicité affecte les ventes. Il s’agit ici
d’un modèle simple, mais qui illustre la configuration d’un modèle et
le recours à Evolver pour y identifier la sortie optimale.
Fichier de l’exemple :
Allocation budgétaire.xls
But :
Affecter le budget annuel entre cinq services pour
maximiser le bénéfice de l’an prochain.
Méthode de résolution :
budget
Problèmes similaires :
Affecter des ressources précaires (telles que maind’œuvre, argent, carburant, temps) à des postes
susceptibles de les utiliser de différentes manières
plus ou moins efficientes.
Chapitre 4 : Applications types
57
Modèle
Le fichier « Allocation budgétaire.xls » modélise les effets du budget
d’une entreprise sur ses ventes et bénéfices à venir. Les cellules C4:C8
(les variables) représentent les montants à allouer à chacun des cinq
services. La cellule C10 représente le total de ces valeurs, soit le
budget annuel total de l’entreprise. Ce budget est défini par
l’entreprise et est inchangeable.
Les cellules F6:F10 calculent une estimation de la demande du produit
de l’entreprise pour l’année prochaine, en fonction des budgets
publicitaires et de marketing. Le montant de ventes réelles représente
le minimum de la demande calculée et de l’offre. L’offre dépend des
fonds alloués aux services de production et d’exploitation.
Résolution
On maximise le bénéfice dans la cellule I16 en choisissant la méthode
de résolution « budget » pour ajuster les valeurs des cellules C4 :C8.
En fixant les plages indépendantes de chacune des cellules ajustables
du budget de chaque service, on évite qu’Evolver n’essaie de valeurs
négatives ou de chiffres qui ne produiraient pas de solutions
budgétaires pertinentes (toute publicité sans production, par
exemple).
La méthode de résolution « budget » opère de la même manière que
« recette » en ce qu’elle recherche la bonne « combinaison » des
variables choisies. La différence est que sous la méthode « budget »,
on ajoute la contrainte que le total de toutes les variables doit rester
égal avant et après l’optimisation.
58
Allocation budgétaire
Équilibre chimique
Tout processus modélisable destiné à produire un résultat conforme à
certaines conditions initiales peut être optimisé par Evolver. Cet
exemple illustre la manière dont Evolver peut identifier les niveaux
de différents produits chimiques (produits et réactifs) pour minimiser
l’énergie libre après une réaction équilibrée. Dans les processus
chimiques compliqués, les ingrédients (réactifs) et les produits se reforment continuellement les uns les autres jusqu’à ce que la
concentration des composés deviennent constante, quand
« l'équilibre » est atteint. À tout moment après l’accès à cet équilibre,
un pourcentage constant des substances chimiques d'équilibre
pourraient être des réactifs (5 %, par exemple) et un pourcentage
constant serait représenté par des produits (95 %).
Fichier de l’exemple :
Equilibre chimique.xls
But :
Calculer l’énergie libre du milieu de réaction et
identifier les niveaux chimiques, compte tenu des
contraintes souples définies (certains niveaux
chimiques sont proportionnels à d’autres).
Méthode de résolution :
recette
Problèmes similaires :
Déterminer les conditions de l’équilibre de
marché le plus stable.
Chapitre 4 : Applications types
59
Modèle
Les variables de ce problème, dans les cellules B4:B13, sont les
niveaux chimiques à mélanger. La cellule B15 calcule le montant total,
qui doit être maintenu dans une plage donnée, compte tenu des
pénalités définies.
Les contraintes définies dans F20:F22 sont souples : Evolver ne doit
pas accepter que les solutions conformes, mais il calculera les
pénalités applicables si certaines proportions ne sont pas respectées.
Ces contraintes souples reposent sur les fonctions de pénalité
intégrées directement dans le modèle de la feuille de calcul. Les
pénalités s’ajoutent à la cellule d’énergie libre totale F17, de sorte que
pour minimiser la cible, Evolver recherchera les solutions non grevées
de pénalités.
Résolution
60
On choisit la méthode de résolution recette pour les cellules B4:B13.
On minimise la cellule F17.
Équilibre chimique
Planificateur de classes
Une université doit affecter 25 classes différentes à 6 blocs temps
prédéfinis. La durée de chaque classe est d’exactement un bloc temps.
Cela permettrait ordinairement d’aborder le problème par la méthode
de résolution « groupement ». La programmation des classes exige
cependant la satisfaction de plusieurs contraintes. Par exemple, les
cours de biologie et chimie ne doivent pas être programmés en même
temps, pour que les étudiants de médicine puissent les suivre la
même année. Pour satisfaire à ces contraintes, on choisira donc la
méthode de résolution « programmation ». Cette méthode est
comparable à celle de « groupement », si ce n’est que certaines tâches
doivent (ou ne doivent pas) se produire avant (ou après ou pendant)
d’autres.
Fichier de l’exemple :
Planificateur de classes.xls
But :
Affecter 25 classes à 6 périodes de temps de
manière à minimiser le nombre d’étudiants qui
devront être exclus de certaines classes. Satisfaire
aux contraintes d’agencement des classes dans le
temps.
Méthode de résolution :
programme
Problèmes similaires :
Tout problème de programmation où toutes les
tâches sont de même longueur et peuvent être
affectées à un bloc temps discret quelconque.
Tout problème de groupement soumis à des
contraintes quant aux groupes auxquels certains
éléments peuvent être affectés.
Chapitre 4 : Applications types
61
Modèle
Le fichier « Planificateur de classes.xls » contient un modèle de
problème de programmation type soumis à de nombreuses
contraintes. Les cellules C5:C29 affectent les 25 classes aux 6 blocs
temps. On ne dispose que de cinq salles de classe. L’affectation de
plus de cinq classes par bloc temps impliquerait l’impossibilité de
réunion d’au moins une classe.
Les cellules K17:M25 définissent les contraintes. À gauche de ces
contraintes figurent leurs descriptions littérales. Vous pouvez utiliser,
au choix, le code numérique ou la description littérale de la
contrainte. La liste des codes de contrainte des problèmes de
programmation figure en détails dans la section du Chapitre 5 : Guide
de référence consacrée aux « Méthodes de résolution ».
Chaque programme possible est évalué en calculant a) le nombre de
classes exclues et b) le nombre d’étudiants exclus pour cause de classe
saturée. Cette dernière contrainte évite la programmation simultanée
de toutes les classes nombreuses. Si une ou deux classes nombreuses
seulement se réunissent sur un bloc temps donné, les salles de classe
plus vastes peuvent leur être réservées.
62
Planificateur de classes
Les cellules I8:N8 font appel à la fonction Excel BDNB pour compter
le nombre de classes affectées à chaque bloc temps. Juste au-dessous
les cellules I9:N9 calculent ensuite le nombre de classes non affectées à
une salle de classe pour le bloc temps correspondant. Toutes les
classes sans salle sont totalisées dans la cellule K10.
Si le nombre de sièges requis pour une classe donnée dépasse le
nombre de sièges disponibles, les cellules I12:N12 calculent l’excès et
le nombre total d’étudiants sans siège est calculé dans la cellule K13.
Dans la cellule F6, ce nombre total d’étudiants sans siège est ajouté à
la taille de classe moyenne et multiplié par le nombre de classes sans
salle. Une cellule combine ainsi toutes les pénalités, de sorte qu’un
nombre inférieur, dans cette cellule, indique toujours un meilleur
programme.
Résolution
On minimise la valeur des pénalités dans F6 par variation des cellules
C5:C29. On choisit la méthode de résolution « programme ». Lorsque
cette méthode est sélectionnée, ses options s’affichent dans le volet
« options » inférieur de la boîte de dialogue. On fixe le nombre de
blocs temps à 6 et les cellules sous contrainte à K17:M25.
Chapitre 4 : Applications types
63
64
Segmenteur de code
Un programmeur Windows désire diviser un programme en
plusieurs segments de code, pour que Windows opère plus
efficacement en ne gardant en mémoire que les segments de code
utilisés.
Cet exemple illustre la collecte d’éléments similaires dans des
groupes. L’interaction est efficace entre les éléments d’un même
groupe, mais elle est difficile entre ceux de groupes différents. En
présence d'obstacles naturels à l’interaction directe de chaque élément
avec tous les autres (si tous les utilisateurs d’ordinateurs voulaient
être connectés directement à une imprimante, par exemple), il est
nécessaire de répartir les éléments en différents groupes. Un
groupement efficace peut produire un effet considérable sur la
productivité globale du système.
Fichier de l’exemple :
Segmenteur de code.xls
But :
Grouper les sous-programmes en huit segments
de code différents pour que le programme
s’exécute aussi rapidement que possible.
Méthode de résolution :
groupement
Problèmes similaires :
Collecte de postes de travail en groupes de
réseau local, ou de circuits en zone de micropuce,
pour minimiser le coût de la communication
entre les groupes.
Chapitre 4 : Applications types
65
Modèle
Les programmeurs Windows divisent souvent leurs programmes de
cette matière pour en accroître l’efficacité. Lorsqu’un sous-programme
d’un segment différent doit s’exécuter, Windows rejette le segment
d’appel et lit celui appelé sur le disque. Si un programme de 2Mo est
divisé en 80 segments de 20 Ko chacun, le programme peut s’exécuter
avec 20 Ko de mémoire disponible seulement. Pour que la
performance soit acceptable, toutefois, les segments doivent être
soigneusement organisés. L’appel d’une fonction dans un autre
segment demande plus de temps que si l’appel se fait dans le même
segment. Le problème de segmentation de code consiste à minimiser
le nombre d’appels intersegmentaux.
Pour éviter d’optimiser certaines parties d’une application au
détriment de l’application dans son ensemble, nous allons utiliser
Evolver pour exécuter une optimisation globale.
Le fichier d’exemple « Segmenteur de code.xls » suppose qu’une
application a été compilée avec une certaine segmentation.
L’application a été exécutée de façon ordinaire, avec suivi par un
sous-programme de traçage de performance du nombre d’appels
survenus entre les fonctions. Les résultats représentent donc la nature
des appels sous usage type de l’application. La vitesse de l’application
sous différentes stratégies de segmentation peut ainsi être prédite.
La feuille de calcul utilise la fonction personnalisée « SegCost ».
SegCost calcule le temps qu’il faudrait à l’utilisateur pour exécuter le
programme de la même manière que lors de l’acquisition de
statistiques d’usage type. La fonction procède par calcul du nombre
d'appels inter- et intrasegmentaux, et par multiplication de chacun
par le coût de chaque type d'appel. On suppose ici qu’un appel
intersegmental (ou appel proche) exige sept cycles d’horloge et un
appel intrasegmental (ou appel lointain), 34 cycles, comme dans le cas
d'un processeur 386.
66
Segmenteur de code
La fonction SegCost est programmée sous forme de macro Excel VBA,
comme illustré ici :
Function segCost(segs, calls, inP, outP) As Double
Dim inCost#, outCost#, total#, temp#, tempPtr#
Dim i%, j%, wide%, funcNumber%, ThisSeg%, OtherSeg%
Dim NumCalls%, NumInCall%, NumOutCall%, SegOrder$,
CallOrder$
SegOrder = Application.Names("segs").RefersTo
CallOrder = Application.Names("calls").RefersTo
NumInCall = 0
NumOutCall = 0
inCost = Range("k2")
outCost = Range("k3")
total = 0
wide = Range(CallOrder).Columns.Count
For i = 1 To Range(SegOrder).Rows.Count
ThisSeg = Range(SegOrder).Rows(i)
For j = 1 To wide
temp = Range(CallOrder).Rows(i).Columns(j)
If temp <> 0 Then
funcNumber = Int(temp)
OtherSeg = Range(SegOrder).Rows(funcNumber + 1)
NumCalls = 10000 * (temp - funcNumber)
If ThisSeg = OtherSeg Then
temp = NumCalls * inCost
NumInCall = NumInCall + 1
Else
temp = NumCalls * outCost
NumOutCall = NumOutCall + 1
End If
total = total + temp
End If
Next
Next
segCost = total
End Function
L’application de notre exemple comporte 80 fonctions. Le nombre
d’appels de chaque fonction par chaque autre se stocke dans la plage
des « appels » (C5:I104). On pourrait créer une matrice de 80 sur 80
pour représenter les motifs d’appels, mais cette approche n sur n
deviendrait inutilisable au-delà d’environ 250 fonctions car Excel est
limité à 256 colonnes (sans compter que l’approche exigerait une
quantité exponentielle de mémoire).
Chapitre 4 : Applications types
67
On utilise donc plutôt une notation condensée pour représenter les
motifs d’appel. On suppose d’abord qu’aucune fonction n’appelle
plus qu’un certain nombre d’autres fonctions. Dans cet exemple, on
fixe à sept la limite supérieure, raison pour laquelle la plage des
appels compte sept colonnes, mais cette limite est arbitraire. On
suppose aussi qu’aucune fonction n’est appelée par aucune autre plus
de 9999 fois.
Considérons donc la fonction 1, à partir de la cellule C5. La fonction 1
appelle 4 fonctions : les fonctions 3, 9, 11 et 41. Les cellules C5:I5,
première ligne de la plage d’appels, contiennent un nombre réel pour
chaque fonction appelée (3,0023, par exemple). La partie entière (3)
représente la fonction appelée et la fraction multipliée par 10 000
(0,0023 x 10 000 = 23) représente le nombre de fois que la fonction 1 a
appelé la fonction 3 sous usage type de l’application. Ainsi, 9,1117
veut dire que la fonction a appelé la fonction n° 9 1 117 fois, et ainsi de
suite. Ce format concis épargne la mémoire et tire le meilleur parti
possible du nombre limité de colonnes disponibles dans Excel.
La plage A5:A104 (plage des « segments ») contient le numéro du
segment auquel chaque fonction est affectée. La cellule K4 fait appel à
la fonction « SegCost » pour calculer la performance globale de la
stratégie de segmentation courante.
Résolution
68
On minimise la valeur de la cellule K4 en ajustant les cellules
A5:A104. On utilise la méthode « groupement ». Sous la méthode de
résolution « groupement », Evolver dispose les variables en x
groupes, où x représente le nombre de valeurs différentes dans les
cellules ajustables au début d’une optimisation.
Segmenteur de code
Dakota : Itinéraires sous contraintes
Une agence immobilière doit faire expertiser chacun de ses biens dans
le Dakota du Nord. L’opération doit se dérouler dans un certain
ordre, pour que certains biens soient visités avant d’autres. Similaire
au problème classique du voyageur de commerce, le but est
d'identifier l’itinéraire le plus court à travers un ensemble de villes, en
assurant le passage par chaque ville. Cet exemple est cependant
soumis à la contrainte supplémentaire que certaines villes doivent en
précéder d’autres sur l’itinéraire (la ville n° 2 doit par exemple figurer
après la ville n° 4 dans l’itinéraire). Plutôt que la méthode de
résolution « ordre », on utilisera donc celle intitulée « projet ».
Cette méthode organise un ensemble de tâches dans lequel certaines
doivent en précéder d’autres. La méthode « projet » permettrait
notamment, en combinaison avec les fonctions personnalisées
appropriées, d'identifier le meilleur minutage d’un projet (en fonction
d'une combinaison de critères tels que durée de réalisation, utilisation
de ressources, etc.)
Fichier de l’exemple :
Dakota.xls
But :
Planifier un itinéraire couvrant 41 villes du Dakota
du Nord, de manière à assurer la plus faible
distance entre toutes les villes et en respectant un
ordre donné entre certaines villes.
Méthode de résolution :
projet
Problèmes similaires :
Re-planifier un projet pour équilibrer l’utilisation
de ressources. Planifier l’ordonnancement des
tâches d’un atelier pour réduire la durée totale
d’un projet tout en assurant la réalisation de
certaines tâches avant d’autres.
Chapitre 4 : Applications types
69
Modèle
Les cellules F3:F43 contiennent l’ordre de passage dans chaque ville.
La cellule H10 calcule la distance totale de l’itinéraire, en fonction de
l’ordre et des coordonnées x,y des villes (dans C3:D43). La cellule H10
fait appel à la fonction personnalisée « BigRouteLength » pour
accélérer le calcul de la distance totale.
Les cellules J3:L43 définissent les précédences. Il s’agit d’un tableau
de cellules décrivant l’ordre de précédence des tâches (quelles villes
doivent précéder quelles autres sur l’itinéraire). Huit villes (1,2,3,4,5,7,
11 et 13) doivent être visitées après d’autres particulières.
70
Dakota : Itinéraires sous contraintes
Résolution
On minimise la distance dans H10 en faisant varier les cellules F3:F43.
On choisit la méthode de résolution « projet » et on définit l’ordre de
précédence dans J3:L43. Les « tâches précédentes » se définissent dans
la boîte de dialogue Paramètres du groupe de cellules ajustables
comme illustré ci-dessous.
Chapitre 4 : Applications types
71
72
Ordonnancement multigamme
Un atelier de travail des métaux doit trouver le meilleur moyen de
planifier un ensemble de projets à répartir par étapes réalisables sur
différentes machines. Chaque projet compte cinq tâches, dont la
réalisation doit s’effectuer dans un certain ordre. Chaque tâche doit
être accomplie sur une machine particulière et requiert une durée
d’exécution spécifique. Il y a cinq projets et cinq machines.
Le bouton Programme, en haut de la feuille de calcul, retrace le
graphique à barres pour indiquer le moment d’exécution prévu de
chaque tâche.
Fichier de l’exemple :
Ordonnancement multigamme.xls
But :
Affecter les éléments d’un projet (tâches) à des
machines de manière à minimiser la durée totale
de tous les projets.
Méthode de résolution :
ordre
Problèmes similaires :
Problèmes de planification ou gestion de projet
Chapitre 4 : Applications types
73
Modèle
La cellule D5 calcule le temps écoulé entre le début de la première
tâche planifiée et la fin de la dernière tâche planifiée. Ce temps total
est l’élément à minimiser. Les cellules G11:G35 contiennent les
variables (les tâches) à organiser de différentes manières pour
déterminer l’ordre optimal. Les équations calculent le moment auquel
chaque tâche peut être exécutée sur la machine nécessaire à sa
réalisation.
Résolution
On sélectionne l’ensemble de cellules ajustables G11:G35 et on choisit
la méthode de résolution ordre. On minimise la cellule D5.
74
Ordonnancement multigamme
Emplacement de pylônes radio
Un réseau radio veut ériger trois pylônes dans une région comptant
12 communautés importantes. Chaque communauté présente une
population de taille différente et chaque pylône, une portée différente.
Le but est de placer les pylônes de manière à couvrir un maximum
d’auditeurs possibles dans le rayon de diffusion des pylônes.
y
x
1
1
Un exemple plus complexe de ce type de problème serait celui de
l’emplacement de plusieurs usines appelées à se trouver a) à
proximité de leurs fournisseurs comme de leurs clients, b) dans un
vaste espace peu onéreux et c) à proximité d’une vaste main-d’œuvre
technique qualifiée. D’autres facteurs d’influence, tels que les
programmes d’incitation fiscale, pourraient également entrer en ligne
de compte. Evolver peut aider à trouver les meilleurs emplacements
dans un espace à coordonnées x,y ou même x,y,z.
Fichier de
l’exemple :
Emplacement de pylônes radio.xls
But :
Trouver les meilleures coordonnées x,y pour
l’emplacement de trois pylônes radio, de manière à
couvrir la plus grande population d’écoute potentielle.
Méthode de
résolution :
recette
Problèmes
similaires :
Recherche de sites d’entreposage qui minimisent les
transports entre entrepôts et magasins. Implantation
de casernes de pompiers de manière à couvrir
optimalement les populations avec un nombre de
casernes limités, compte tenu de facteurs tels que la
densité de logement.
Chapitre 4 : Applications types
75
Modèle
Le fichier « Emplacement de pylônes radio.xls » modélise un espace
bidimensionnel où la disposition de trois pylônes radio détermine le
nombre d'auditeurs potentiels atteints. Les cellules C6:D8 contiennent
les coordonnées x,y des trois pylônes. L’illustration du modèle se
compose de deux éléments : une image bitmap des densités de
population (en vert) collée depuis le programme Windows
Paintbrush, et un diagramme de dispersion Excel recalculé
automatiquement en fonction de l’emplacement des pylônes.
Dix communautés sont représentées ponctuellement. Le modèle Excel
calcule la distance entre les communautés et les pylônes dans les
cellules K4:M15, de manière à déterminer si chaque communauté est
couverte (oui) ou non. La population totale de toutes les
communautés couvertes (la valeur à maximiser) se calcule dans la
cellule O17.
Résolution
On maximise la population atteinte dans la cellule O17 par ajustement
des cellules d’emplacement des pylônes C6:D8. On choisit la méthode
de résolution « recette » et on fixe les plages des variables de 0 à 50
(limites de la zone d’emplacement).
Sous cette méthode, Evolver ajuste les variables choisies comme bon
lui semble. Comme dans le cas d’une recette de cuisine, l'approche
essaie de trouver le bon mélange d'« ingrédients » (les coordonnées
x,y) pour produire la solution optimale.
76
Emplacement de pylônes radio
Équilibrage de portefeuilles
Un courtier a une liste de 80 titres, représentant chacun une valeur
monétaire différente. Il désire grouper ces titres en cinq ensembles
(portefeuilles) dont les valeurs totales sont aussi proches que possible.
Il s’agit ici d’un exemple relevant d’une classe générale de problèmes
dits d’emballage optimal. Le chargement des cales d’un cargo de
manière à répartir uniformément le poids en est un autre exemple. S’il
y a des millions de petits éléments à « emballer » dans quelques
groupes seulement (des grains de blé dans les cales d’un navire, par
exemple), une distribution plus ou moins égale peut être estimée sans
grande différence de poids. En revanche, plusieurs douzaines de
paquets de poids et/ou tailles différents peuvent être disposés de
différentes manières, et un emballage efficace peut améliorer
l’équilibre qu’on atteindrait manuellement.
Fichier de l’exemple :
Equilibrage de portefeuilles.xls
But :
Répartir une liste de titres en cinq portefeuilles
différents dont les valeurs totales sont aussi
proches que possible les unes des autres.
Méthode de résolution :
groupement
Problèmes similaires :
Formation d’équipes dotées de talents collectifs
plus ou moins équivalents. Chargement de
conteneurs dans les cales d’un bateau pour
répartir uniformément la charge.
Chapitre 4 : Applications types
77
Modèle
Le fichier « Equilibrage de portefeuilles.xls » modélise une tâche de
groupement typique. La colonne A contient les numéros
d’identification des titres spécifiques et la colonne B, la valeur de
chacun. La colonne C affecte chaque titre à l’un des cinq portefeuilles.
Lors de la configuration d’un type de problème à groupement ou
emballage optimal sous la méthode de résolution groupement, on
veillera, avant de lancer Evolver, à ce que chaque groupe (1-5) soit
représenté au moins une fois dans le scénario.
Les cellules F6:F10 calculent la valeur totale de chacun des cinq
portefeuilles. Ce calcul s’effectue sous critères de base de données
hors écran (dans la colonne I) et à l’aide des formules « BDSOMME() »
dans les cellules F6:F10. Ainsi, par exemple, la cellule F6 calcule la
BDSOMME de toutes les valeurs de la colonne B affectées au groupe 5
(dans la colonne C).
78
Équilibrage de portefeuilles
La cellule F12 calcule l’écart type des valeurs de portefeuille totales au
moyen de la fonction « ECARTYPE() ». On obtient ainsi une mesure
de la proximité des valeurs de portefeuille les unes par rapport aux
autres. Le graphique représente la valeur totale de chaque
portefeuille, avec une ligne de référence marquant la valeur cible s’ils
étaient tous égaux.
Résolution
On minimise la valeur de la cellule F12 en ajustant les cellules
C5:C104. On choisit la méthode « groupement » et on s’assure que les
valeurs 1, 2, 3, 4 et 5 figurent chacune au moins une fois dans la
colonne C.
Sous la méthode de résolution « groupement », Evolver dispose les
variables en x groupes, où x représente le nombre de valeurs
différentes dans les cellules ajustables au début d’une optimisation.
Chapitre 4 : Applications types
79
80
Composition de portefeuille
Un jeune couple détient des valeurs dans plusieurs types
d’investissement différents, présentant chacun leur propre rapport,
croissance potentielle et risque. En combinant plusieurs formules de
multiplication de différentes pondérations, ils ont personnalisé une
« cote » leur indiquant la mesure dans laquelle une combinaison
particulière d'investissements répond à leurs besoins.
Fichier de l’exemple :
Composition de portefeuille.xls
But :
Trouver la combinaison optimale
d’investissements pour maximiser le bénéfice,
compte tenu du rapport risque/besoin de
rendement actuel.
Méthode de résolution :
budget
Chapitre 4 : Applications types
81
Modèle
Cet exemple présente un modèle d’investissement classique cherchant
à équilibrer le risque de perte par rapport au rendement. Chaque type
d’investissement listé dans la colonne A reçoit une certaine
pondération dans la colonne C. Le modèle multiplie les pourcentages
de rendement par la pondération de chaque investissement dans le
portefeuille pour révéler le rapport total dans la cellule C18. On
calcule aussi le risque total dans la cellule C19, dont la valeur ne doit
pas être supérieure à celle de risque acceptable indiquée dans la
cellule C20.
Résolution
La « cote » totale, dans la cellule 22, reflète le rapport total moins la
pénalité du risque éventuel au-delà du pourcentage acceptable. Cette
cote doit être maximisée.
82
Composition de portefeuille
Émetteurs radio
Un réseau radio achète trois pylônes radio désaffectés dans une
région comptant neuf communautés importantes. Le réseau désire
acheter de nouveaux émetteurs et les installer aux pylônes pour les
remettre en service.
Comme le budget est limité, le but est de dépenser le moins possible
pour l’achat d’émetteurs capables, malgré tout, de couvrir les neuf
communautés avoisinantes. On présume un modèle de prix linéaire,
où le coût d'un émetteur est directement lié à sa puissance. On
recherche donc la puissance la plus faible possible. On pourrait tout
aussi bien créer un tableau de recherche des types et prix des
émetteurs.
Fichier de l’exemple :
Emetteurs radio.xls
But :
Trouver pour chaque pylône l’émetteur le plus
faible (le moins cher) possible et couvrir les neuf
communautés visées.
Méthode de résolution :
recette
Problèmes similaires :
Problèmes de couverture d’ensemble, où plusieurs
éléments doivent être décrits par un petit nombre
d'ensembles bien définis.
Chapitre 4 : Applications types
83
Modèle
Cet exemple est fort similaire à celui d'emplacement de pylônes radio
(Emplacement de pylônes radio.xls), à la différence que les
emplacements sont dans ce cas-ci hors service, et que les variables à
ajuster sont les plages de puissance des pylônes, dans les cellules
E5:E7. On additionne le coût des émetteurs des trois pylônes dans la
cellule E12, qui représente la cellule cible à minimiser.
Les cellules K4:M12 calculent la distance entre les pylônes et chaque
communauté, et la colonne N renvoie VRAI quand une communauté
est suffisamment proche d’un émetteur pour être couverte. Toutes ces
contraintes sont vérifiées sous une seule contrainte ferme intitulée
Toutes zones couvertes ?. Cette contrainte fait appel à la formule
ET($N$4:$N$12), qui ne renvoie VRAI que si toutes les valeurs de la
colonne N sont vraies.
Résolution
84
On minimise la puissance requise dans la cellule E12 en ajustant les
rayons des pylônes dans les cellules E5:E7. On choisit la méthode de
résolution « recette » et on définit les plages des variables de 0 à 100.
La seule contrainte ferme, définie au format de formule Excel, est
décrite plus haut.
Émetteurs radio
Achat
Quand il existe de nombreuses manières d'acheter un produit, les
remises sur quantité rendent difficile la détermination de l’approche
la plus rentable. Ce modèle présente un simple tarif, indiquant les
prix d’un solvant particulier avec remises sur quantité. Vous devez
acheter au moins 155 litres du solvant, vendu en fûts de petite,
moyenne, grande et extra-grande capacité.
Vous désirez acheter la quantité adéquate de chaque type de fût pour
minimiser votre coût.
Fichier de l’exemple :
Achat.xls
But :
Dépenser le moins possible à l’achat de 155 litres
de solvant.
Méthode de résolution :
recette
Problèmes similaires :
Situation opposée : Créer un tarif qui récompense
le plus uniformément et le plus équitablement les
commandes de grandes quantités.
Chapitre 4 : Applications types
85
Modèle
Le solvant est proposé en fûts de 3, 6, 10 et 14 litres. Le tarif de chaque
format est présenté dans les cellules D6:H9. Les cellules H13:H16
contiennent les quantités à acheter dans chaque format. La colonne K
calcule le coût de chaque achat et la cellule K18 représente le coût
total. Ce modèle permet de changer la quantité requise (cellule I19) de
155 à une valeur au choix. La cellule I18 contient le nombre total de
litres achetés ; elle doit donc représenter au moins le nombre requis
tel qu’établi à la cellule I19 (155). La seule contrainte ferme est que la
quantité achetée soit au moins égale à celle requise.
Il nous faut 155 litres. On pourrait donc juger utile de commander 11
fûts extra-larges (154 litres) plus un petit fût (3 litres), soit un total de
157 litres. Au tarif indiqué, cela reviendrait à un coût total de €1 200.
L’optimisation révèle cependant une formule plus rentable encore.
Résolution
86
On minimise le coût dans la cellule K18 en ajustant les quantités à
acheter dans les cellules H13:H16. On choisit la méthode de résolution
recette pour ajuster les valeurs, et on limite les plages de ces variables
entre 1 et 20. Comme il n’est pas possible d’acheter un fût partiel, on
spécifie l’option de valeurs « entières » dans la boîte de dialogue
Cellules ajustables. Comme on ne peut pas acheter moins de 155 litres,
on définit aussi une contrainte ferme indiquant que I18>155.
Achat
Problème du voyageur de commerce
Un voyageur de commerce doit se rendre une fois dans chaque ville
de son territoire. Quel est l’itinéraire le plus court qui lui permettra de
couvrir chaque ville ? Il s’agit ici d’un problème d’optimisation
classique particulièrement difficile à résoudre selon les techniques
traditionnelles quand le nombre de villes est grand (>50).
La recherche du meilleur ordre d’exécution des tâches dans une usine
présenterait un problème similaire. Ainsi, il pourrait être beaucoup
plus simple d’appliquer la peinture noire après la blanche plutôt que
l’inverse. Sous Evolver, ces types de problème se résolvent le mieux à
l’aide de la méthode ordre.
Fichier de l’exemple :
Problème du voyageur de commerce.xls
But :
Rechercher l’itinéraire le plus court entre n villes
en passant une fois par chacune.
Méthode de résolution :
ordre
Problèmes similaires :
Planifier le perçage le plus rapide possible d’une
carte de circuit imprimé.
Chapitre 4 : Applications types
87
Modèle
Le fichier « Problème du voyageur de commerce.xls » calcule
l’itinéraire d'un voyage vers différentes villes en recherchant les
distances sur un tableau. La colonne A contient les numéros
d’identification des villes. La colonne B contient les noms
correspondant à ces numéros (par fonction de recherche). L’ordre
dans lequel les villes (et leurs numéros) figurent de haut en bas
représente l’ordre dans lequel elles sont visitées. Par exemple, si on
entre « 9 » dans la cellule A3, Ottawa est la première ville visitée. « 6 »
(Halifax) dans la cellule A4 désignerait Halifax comme deuxième
ville.
Les distances entre les villes sont représentées dans le tableau à partir
de C25. Les distances indiquées dans le tableau sont symétriques (la
distance de A à B est identique à celle de B à A). Les modèles plus
réalistes peuvent cependant inclure des distances non symétriques
pour représenter la difficulté accrue du voyage dans l’une ou l’autre
des directions (à cause des péages, moyens de transport disponibles,
direction des vents, relief, etc.)
Une fonction doit maintenant être utilisée pour calculer la longueur
du trajet entre ces villes. La longueur de route totale se stocke dans la
cellule G2, qui représente la cellule à optimiser. On utilise ici la
fonction « RouteLength ». Il s’agit d’une fonction VBA personnalisée
dans Problème du voyageur de commerce.xls.
Résolution
On minimise la valeur de la cellule G2 en ajustant les cellules A3:A22.
On choisit la méthode « ordre » et on assure que les valeurs 1 à 20
figurent dans les cellules ajustables (A3:A22) avant de démarrer
l’optimisation.
Sous la méthode de résolution « ordre », Evolver réorganise les
variables choisies, en essayant différentes permutations des variables
existantes.
88
Problème du voyageur de commerce
Navigateur spatial
Membre de l’équipage de lancement de la navette spatiale « Evolver
III », vous devez calculer la force et la direction de chaque poussée de
fusée pour atteindre votre destination en consommant le moins de
carburant possible. Les meilleures solutions exploiteront
probablement l’effet de « fouet » gravitationnel des « soleils » proches
pour économiser le carburant.
Fichier de l’exemple :
Navigateur spatial.xls
But :
Amener un vaisseau spatial à sa destination en
consommant le moins de carburant possible.
Profiter de la gravité d’étoiles avoisinantes.
Méthode de résolution :
recette
Problèmes similaires :
Problèmes de contrôle de procédé
Chapitre 4 : Applications types
89
Modèle
Les cellules Q5:R15 contiennent les valeurs de souffle et de direction
de chacune de 10 étapes. La cellule Q16, que nous voulons minimiser,
représente simplement la somme de tout le carburant consommé sur
les 10 étapes (Q4:Q13).
Le modèle est soumis aux contraintes fermes suivantes : a) la position
finale du vaisseau doit se trouver dans une marge de 10 unités
horizontales de sa destination et b) elle doit se trouver dans une
marge de 10 unités verticales.
Résolution
90
On minimise la cellule Q16. On crée un groupe de cellules ajustables
et on choisit la méthode de résolution recette applicable aux cellules
Q5:R13. Les cellules de souffle (Q5:Q13) doivent être comprises entre
0 et 300 et celles de direction (R5:R13) entre -3 et 3 puisque les radians
servent à représenter la direction des souffles. Un radian représente
environ 57 degrés.
Navigateur spatial
Opérateur en bourse
Vous opérez sur le marché S&P 500 et vous avez déterminé que
l’analyse technique produit de meilleures prédictions que l’analyse
fondamentale traditionnelle, et que vous gagnerez du temps une fois
votre système élaboré. Il semble qu’il existe un nombre infini de
règles d’opération, mais quelques-unes seulement vous auraient
assuré un beau profit si vous les aviez suivies. Une recherche par
ordinateur intelligente pourrait vous aider à déterminer les règles qui
vous auraient permis de réaliser le plus gros gain sur une certaine
période historique.
Fichier de l’exemple :
Opérateur en bourse.xls
But :
Rechercher l’ensemble de trois règles qui auraient
produit le meilleur rendement sur une certaine
période de temps.
Méthode de résolution :
recette
Problèmes similaires :
Trouver les moyennes mobiles optimales qui
auraient produit le meilleur résultat ; tous
problèmes de recherche de critères ou de règles.
Chapitre 4 : Applications types
91
Modèle
Ce modèle utilise plusieurs groupes de cellules ajustables pour
résoudre le problème global. Trois règles sont évaluées pour chaque
jour de bourse. Si les conditions des trois règles sont vraies,
l’ordinateur achète ; sinon, il vend. (Un système plus réaliste ne se
limiterait pas simplement à acheter ou vendre, mais parfois aussi à
garder ce qu’il a.)
Chaque règle est décrite par un ensemble de quatre nombres dans les
cellules C5:E8. Cette plage indique : 1) la source de données à laquelle
la règle se réfère ; 2) si la valeur des données doit être supérieure ou
inférieure à une valeur limite ; 3) la valeur limite qui détermine si la
règle est vraie et 4) une valeur modificatrice qui détermine si la valeur
en soi doit être examinée ou si la valeur de la veille ou le changement
depuis la veille doit l'être.
Les valeurs limites varient entre 0 et 1. Elles représentent le
pourcentage de la plage de la source de données. Par exemple, si le
volume varie entre 5 000 et 10 000, une valeur limite de 0,0
correspondrait à un volume de 5 000, 1,0 à un volume de 10 000 et 0,5
à un volume de 7 500. Ce système permet la référence des règles à
n'importe quelle source de données, indépendamment des valeurs
prises.
Résolution
92
On crée les groupes de cellules ajustables et on choisit la méthode de
résolution « recette ». Chaque ligne de C5:E5, C6:E6, C7:E7 et C8:E8
doit être créée séparément, de manière à ce que chaque groupe puisse
être associé à ses propres options, telles que valeurs entières et plages.
Les paramètres de chaque ensemble de variables sont listés dans
F5:F8. On maximise la cellule E10, qui fait appel à une macro pour
simuler l’opération sous ces règles. Le profit total réalisé après la
simulation de chaque jour dans la base de données historique est
renvoyé dans la cellule E10.
Opérateur en bourse
Transformateur
Le transformateur à 2 enroulements doit avoir une puissance
nominale de 1080 VA avec pertes pleine charge inférieures à 28 watts
et dissipation de chaleur de surface maximum de 0,16 watts/cm². Les
coûts doivent être minimisés tout en respectant les critères de
performance.
Fichier de l’exemple :
Transformateur.xls
But :
Minimiser le coût initial et le coût de
fonctionnement d’un transformateur.
Méthode de résolution :
recette
Problèmes similaires :
Conception de circuit, conception de pont.
Chapitre 4 : Applications types
93
Modèle
Les contraintes de valeur nominale, perte de charge et dissipation
thermique sont définies comme contraintes souples. On crée une
contrainte souple en pénalisant les solutions non conformes aux
critères définis. Contrairement aux contraintes fermes qui doivent
obligatoirement être satisfaites, Evolver peut, sous contrainte souple,
essayer certaines solutions non conformes. Comme ces solutions sont
cependant pénalisées par une fonction du modèle qui contrôle les
infractions, elles produisent de faibles résultats dans la cellule cible.
Ces solutions finissent donc par être rejetées de la population
évolutive de solutions possibles.
Un modèle sous contrainte souple fonctionne parfois mieux que sous
contrainte ferme, si l’approche permet de soulager les contraintes
d’un problème. Il permet aussi à Evolver d’accepter une très bonne
solution même si elle n’est pas tout à fait conforme aux contraintes, ce
qui vaut parfois mieux qu'une solution moins bonne même si
conforme à toutes les contraintes.
Résolution
94
On calcule le coût des matériaux (coût initial) et les coûts de
fonctionnement (coût de l’électricité * électricité gaspillée) dans les
cellules F11 et F12. On combine ces valeurs aux fonctions de pénalité
définies dans F18:F20 pour produire le coût final sous contraintes
dans la cellule F22. On minimise cette cellule cible selon la méthode
de résolution « recette ».
Transformateur
Transports
Est-il possible d’assurer économiquement le transport d’objets à
travers les États-Unis ? Ce problème standard est une version élaborée
d’un exemple plus ancien de Microsoft Solver.
On cherche à minimiser les coûts de transport de produits depuis les
usines de production vers les entrepôts à proximité des centres de
demande urbaine, le tout sans dépasser l’offre de chaque usine et en
répondant à la demande de chaque centre urbain.
Pour rendre le problème plus réaliste, les coûts de transport, non plus
linéaires, dépendent ici du nombre de camions nécessaires. Un
camion peut transporter jusqu’à 6 objets ; le transport de 14 objets
requiert donc 3 camions (transportant 6 + 6 + 2 objets).
Fichier de l’exemple :
Transports.xls
But :
Transporter des objets depuis trois usines vers
cinq entrepôts aussi économiquement que
possible.
Méthode de résolution :
recette
Problèmes similaires :
Conception de réseaux de communications.
Chapitre 4 : Applications types
95
Modèle
Les cellules C5:E7 contiennent le nombre d’objets transportés depuis
chaque usine vers chaque entrepôt. C13:E13 calculent le nombre de
camions nécessaires au transport de ces objets. Le modèle est soumis
aux contraintes fermes suivantes : 1) le total expédié depuis chaque
usine doit être inférieur ou égal à l’offre disponible à l’usine et 2) le
total expédié depuis toutes les usines vers chaque entrepôt doit être
supérieur ou égal à la quantité demandée par l'entrepôt. On assure
ainsi que chaque entrepôt reçoive ce dont il a besoin, sans surcharger
aucune usine.
Résolution
On applique la méthode de résolution « recette » sur les cellules
C5:E7, avec valeurs entières comprises entre 0 et 500. Un ensemble de
contraintes fermes est entré pour chaque usine, spécifiant que les
expéditions d’usine <= offre d’usine. Un deuxième ensemble de
contraintes fermes est défini pour chaque entrepôt, spécifiant que les
expéditions totales vers l’entrepôt >= demande de l’entrepôt. On
minimise les coûts de transport dans la cellule B22.
96
Transports
Chapitre 5 : Guide de référence
Evolver
Commande Définition du modèle ...................................................99
Plages de cellules ajustables ..................................................................101
Groupes de cellules ajustables ..........................................................104
Méthode de résolution « recette »........................................106
Méthode de résolution « ordre » ..........................................106
Méthode de résolution « groupement »..............................107
Méthode de résolution budget.............................................108
Méthode de résolution « projet ».........................................109
Méthode de résolution « programme »...............................110
Taux de croisement et de mutation .....................................112
Nombre de blocs temps et cellules sous contrainte .........114
Tâches précédentes.................................................................114
Opérateurs................................................................................115
Contraintes ............................................................................................118
Ajouter – Ajout de contraintes .............................................118
Format de contrainte Simple ou Formule ..........................119
Contraintes souples................................................................120
Commande Paramètres d'optimisation ........................................123
Commande Paramètres d’optimisation – Onglet Général............123
Commande Paramètres d’optimisation – Onglet Temps
d’exécution ............................................................................................124
Optimisation............................................................................125
Commande Paramètres d’optimisation – Onglet Affichage ........127
Commande Paramètres d’optimisation – Onglet Macros .............128
Commande Démarrer l'optimisation.............................................129
Commandes Utilitaires...................................................................131
Commande Paramètres d’application................................................131
Commande Solveur de contraintes...................................................132
Chapitre 5 : Guide de référence Evolver
97
Suivi Evolver................................................................................... 135
Suivi Evolver – Onglet Progression ................................................. 136
Suivi Evolver – Onglet Synthèse...................................................... 138
Suivi Evolver – Onglet Journal ......................................................... 139
Suivi Evolver – Onglet Population .................................................. 140
Suivi Evolver – Onglet Diversité...................................................... 141
Suivi Evolver – Onglet Options d’arrêt........................................... 142
98
Commande Définition du modèle
Définit le but, les cellules ajustables et les contraintes d’un
modèle.
La commande Définition du modèle d’Evolver (ou l’icône Modèle de
la barre d’outils d’Evolver) ouvre la boîte de dialogue Modèle .
Boîte de dialogue Evolver – Modèle.
La boîte de dialogue Evolver – Modèle sert à spécifier ou décrire un
problème d’optimisation à Evolver. Vide à chaque ouverture de
nouveau classeur Excel, cette boîte de dialogue enregistre cependant
son information avec chaque classeur. À la réouverture de la feuille
de calcul, elle se remplit donc de la même manière. Chaque
composant de cette boîte de dialogue est décrit dans cette section.
Chapitre 5 : Guide de référence Evolver
99
Options de la boîte de dialogue Modèle :
•
But d’optimisation.. L’option But d’optimisation détermine le type
de réponse qu’Evolver doit rechercher. Minimum configure la
recherche de valeurs variables qui produisent la plus petite valeur
possible pour la cellule cible (jusqu’à –1e300). Maximum configure
la recherche de valeurs variables qui produisent la plus grande
valeur possible pour la cellule cible (jusqu’à +1e300).
Valeur cible configure la recherche de valeurs variables qui
produisent pour la cellule cible une valeur aussi proche que
possible de la valeur spécifiée. Evolver s’arrête automatiquement
lorsqu’il trouve une solution qui produit le résultat désiré. Par
exemple, si vous configurez la recherche du résultat le plus
proche de 14, Evolver trouvera peut-être des scénarios produisant
une valeur de 13,7 ou 14,5. Remarquez que 13,7 est plus proche de
14 que 14,5. Peu importe que la valeur soit supérieure ou
inférieure à celle que vous spécifiez : Evolver considère
strictement la proximité de la valeur.
•
Cellule. La cellule ou cellule cible contient la sortie du modèle.
Une valeur sera générée pour cette cellule cible à chaque
« solution itérative » produite par Evolver (c.-à-d. chaque
combinaison de valeurs possibles des cellules ajustables). La
cellule cible doit contenir une formule qui dépend (directement
ou à travers une série de calculs) des cellules ajustables. Cette
formule peut faire appel aux formules Excel standard telles que
SOMME() ou aux macro-fonctions VBA définies par l’utilisateur.
Ces dernières permettent l’évaluation par Evolver de modèles
extrêmement complexes.
Pendant la recherche, Evolver se réfère à la valeur de la cellule
cible comme cote ou « fonction de pertinence » pour évaluer la
qualité de chaque scénario possible et déterminer les valeurs
variables dont il convient de poursuivre le croisement et celles
destinées à « mourir ». Dans l’évolution biologique, la mort est la
« fonction de pertinence » qui détermine les gènes appelés à
survivre et prospérer dans la population. Lors de l’élaboration
d’un modèle, la cellule cible doit refléter la pertinence ou la
« qualité » d’un scénario donné, de sorte qu’Evolver puisse
mesurer précisément le progrès de ses calculs.
100
Commande Définition du modèle
Plages de cellules ajustables
Le tableau des Plages de cellules ajustables affiche chaque plage
contenant les cellules ou valeurs qu’Evolver peut ajuster, ainsi que la
description entrée pour ces cellules. Chaque ensemble de cellules
ajustables figure sur une ligne horizontale. Une ou plusieurs plages de
cellules ajustables peuvent être incluses dans un Groupe de cellules
ajustables. Toutes les plages de cellules d’un groupe ont en commun
leur méthode de résolution, leur taux de croisement, leur taux de
mutation et leurs opérateurs.
Comme les cellules ajustables contiennent les variables du problème,
il faut définir au moins un groupe de cellules ajustables pour utiliser
Evolver. Un groupe de cellules ajustables suffit à décrire la plupart
des problèmes. Ceux plus complexes peuvent cependant requérir
différents blocs de variables à résoudre simultanément sous plusieurs
méthodes de résolution. Cette architecture permet l’élaboration et la
description de problèmes complexes sous la forme de groupes divers
de cellules ajustables.
Les options suivantes sont proposées pour la définition des plages de
cellules ajustables :
•
Ajouter. Pour ajouter de nouvelles cellules ajustables, cliquez sur
le bouton « Ajouter » en regard de la zone de liste de cellules
ajustables. Sélectionnez la cellule ou la plage de cellules à ajouter.
Une nouvelle ligne s’affiche dans le tableau des Plages de cellules
ajustables. Ce tableau admet l’entrée de valeurs Minimum et
Maximum pour les cellules de la plage, de même que du type de
valeurs à tester – entières sur toute la plage, ou quelconques.
Chapitre 5 : Guide de référence Evolver
101
•
Minimum et Maximum. Après la spécification de l’emplacement
des cellules ajustables, les entrées Minimum et Maximum
définissent la plage de valeurs acceptables pour chaque cellule.
Par défaut, chaque cellule ajustable reçoit une valeur de nombre
réel (virgule flottante double précision) entre l’infini négatif
(infini-) et l’infini positif (infini+).
Les paramètres de plage sont des contraintes strictement
appliquées. Evolver n’admet aucune variable de valeur extérieure
aux plages définies. La définition de plages spécifiques de
variables est recommandée, dans la mesure du possible, pour
améliorer les performances d’Evolver : par exemple, quand vous
savez que le nombre ne peut pas être négatif ou qu’Evolver ne
doit essayer que les valeurs comprises entre 50 et 70 pour une
variable donnée.
•
Plage. La référence de la ou des cellules à ajuster s’inscrit dans le
champ Plage. Cette référence se saisit par sélection de la région
concernée de la feuille de calcul à l’aide de la souris, par l’entrée
d’un nom de plage ou par la saisie d’une référence Excel valable
telle que Feuille1!A1:B8. Le champ Plage est disponible pour
toutes les méthodes de résolution. Pour les méthodes recette et
budget, toutefois, les options Minimum, Maximum et Valeurs
peuvent être ajoutées pour permettre l’entrée d’une plage pour les
cellules ajustables.
REMARQUE : Affecter des plages étroites aux variables limite
l’étendue de la recherche et accélère la convergence d’Evolver vers
une solution. Attention cependant à ne pas limiter excessivement
les plages de variables : Evolver risquerait de ne pas trouver de
solutions optimales.
102
Commande Définition du modèle
•
Valeurs. L’entrée Valeurs permet de préciser qu’Evolver doit
traiter toutes les variables de la plage spécifiée en tant que valeurs
entières (par exemple, 22), plutôt que de nombres réels (22,395).
Cette option n’est disponible que pour les méthodes de résolution
« recette » et « budget ». Par défaut, les variables sont traitées en
tant que nombres réels.
Veillez à activer le paramètre Entiers pour les modèles dont les
variables recherchent des éléments de table (RECHERCHEH(),
RECHERCHEV(), INDEX(), DECALER(), etc.) Remarquez que le
paramètre Entiers affecte toutes les variables de la plage sélectionnée.
Pour traiter certaines variables comme nombres réels et d’autres
comme valeurs entières, on créera deux groupes de cellules ajustables
plutôt qu’un et on choisira Entiers pour un bloc et Quelconques pour
l’autre : on « ajoute » un groupe recette de cellules ajustables et on
garde le paramètre de valeurs « Quelconques ». On « ajoute » ensuite
une deuxième plage de cellules, en sélectionnant cette fois le
paramètre de valeurs « Entiers » pour les cellules ajustables
concernées.
Chapitre 5 : Guide de référence Evolver
103
Groupes de cellules ajustables
Chaque groupe de cellules ajustables peut contenir plusieurs plages
de cellules. On peut ainsi créer une « hiérarchie » de groupes de
plages de cellules apparentées les unes aux autres. Au sein de chaque
groupe, chaque plage de cellules peut avoir sa propre contrainte de
plage Min-Max.
Toutes les plages de cellules d’un groupe de cellules ajustables ont en
commun leur méthode de résolution, leur taux de croisement, leur
taux de mutation et leurs opérateurs, spécifiés dans la boîte de
dialogue Paramètres du groupe de cellules ajustables. Pour accéder
à cette boîte de dialogue, cliquez sur le bouton Groupe, en regard du
tableau Plages de cellules ajustables. Vous pouvez ainsi créer un
nouveau Groupe et y ajouter des plages de cellules ajustables ou
modifier les paramètres d’un groupe existant.
104
Commande Définition du modèle
L’onglet Général de la boîte de dialogue Paramètres du groupe de
cellules ajustables propose les options suivantes :
•
Description. Décrit le groupe des plages de cellules ajustables
dans les boîtes de dialogue et les rapports.
•
Méthode de résolution. Détermine la méthode de résolution à
utiliser pour chaque plage de cellules ajustables comprise dans le
groupe.
Lors de la sélection d’une plage de cellules à ajuster, on précise aussi
la « méthode de résolution » à appliquer lors de l’ajustage de ces
cellules par Evolver. Chaque méthode de résolution représente
essentiellement un algorithme génétique différent, doté de ses propres
routines de sélection optimisée, croisement et mutation. Chaque
méthode de résolution jongle avec les valeurs des variables de
manières différentes.
La méthode de résolution « recette », par exemple, traite chaque
variable sélectionnée comme un ingrédient d’une recette : la valeur de
chaque variable peut changer indépendamment de celle des autres.
En revanche, la méthode « ordre » permute les valeurs des cellules
ajustables, par réorganisation des valeurs originales.
Evolver propose six méthodes de résolution. Trois d’entre elles
(recette, ordre et groupement) reposent sur des algorithmes
totalement différents. Les trois autres sont les descendantes des trois
premières, auxquelles elles ajoutent des contraintes.
Chapitre 5 : Guide de référence Evolver
105
La fonction de chaque méthode de résolution est décrite dans les
paragraphes qui suivent. Pour mieux comprendre l’emploi de chaque
méthode, ne manquez pas d’explorer les fichiers d’exemple joints au
logiciel (voir le Chapitre 4 : Applications types).
Méthode de
résolution
« recette »
La méthode de résolution « recette » est la plus simple et la plus
courante. Choisissez-la quand les variables à ajuster peuvent varier
indépendamment les unes des autres. Pensez à chaque variable
comme s’il s’agissait de la quantité d’un ingrédient dans un gâteau :
en choisissant la méthode de résolution « recette », on dit à Evolver de
générer pour ces variables des valeurs devant mener au meilleur
mélange possible. La seule contrainte imposée sous la méthode recette
est celle de la plage (valeur supérieure et valeur inférieure) dans
laquelle les valeurs doivent être comprises. Cette plage se définit dans
les champs Min et Max de la boîte de dialogue Cellules ajustables (1 à
100, par exemple). On y indique aussi si Evolver doit essayer des
nombres entiers (1, 2, 7) ou réels (1,4230024 ; 63,72442).
Les exemples ci-dessous illustrent un ensemble de valeurs de
variables telles qu’elles pourraient figurer dans une feuille de calcul
avant l’invocation d’Evolver, puis selon deux nouveaux scénarios
résultant de la méthode de résolution recette.
Méthode de
résolution
« ordre »
106
Ensemble initial de
valeurs de variables
Ensemble de valeurs
de recette possibles
Autre ensemble de valeurs
de recette possibles
23,472
15,344
37,452
145
101
190
9
32,44
7,073
65,664
14,021
93,572
La méthode de résolution « ordre » est la seconde méthode la plus
utilisée, après « recette ». Elle repose sur la permutation d’une liste
d’éléments, dans un effort de recherche du meilleur ordre d’un
ensemble de valeurs données. Contrairement aux méthodes de
résolution « recette » et « budget », sous lesquelles Evolver doit
générer des valeurs pour les variables choisies, cette méthode utilise
les valeurs existantes du modèle.
Commande Définition du modèle
La méthode peut être choisie pour déterminer l’ordre dans lequel
différentes tâches doivent être accomplies. Par exemple, pour
déterminer l’ordre dans lequel il convient d’accomplir les tâches
1,2,3,4 et 5, la méthode « ordre » mélange ces valeurs, produisant par
exemple le scénario 3,5,2,4,1. Comme Evolver se limite à essayer les
valeurs variables de la feuille de calcul initiale, il n’est pas nécessaire
de définir de plage Min – Max pour les cellules ajustables sous la
méthode « ordre ».
Les exemples ci-dessous illustrent un ensemble de valeurs de
variables telles qu’elles pourraient figurer dans une feuille de calcul
avant l’invocation d’Evolver, puis selon deux nouveaux scénarios
résultant de la méthode de résolution ordre.
Méthode de
résolution
« groupement »
Ensemble initial de
valeurs de variables
Ensemble de valeurs
d’ordre possibles
Autre ensemble de valeurs
d’ordre possibles
23,472
145
65,664
145
23,472
9
9
65,664
145
65,664
9
23,472
La méthode de résolution « groupement » est utile quand le problème
implique plusieurs variables à regrouper en ensembles. Le nombre de
groupements créés par Evolver correspond à celui de valeurs uniques
présentes dans les cellules ajustables en début d’optimisation. Lors de
l’élaboration d’un modèle, on veillera donc à ce que chaque groupe
soit représenté au moins une fois.
Supposons, par exemple, une plage de 50 cellules contenant
seulement les valeurs 2, 3,5 et 17. Si on sélectionne ces 50 cellules et
qu’on ajuste les valeurs selon la méthode de résolution
« groupement », Evolver affecte chacune des 50 cellules à l’un de trois
groupes : 2, 3,5 et 17. Tous les groupes sont représentés par au moins
une des cellules ajustables, comme si on jetait chacune des 50
variables dans des casiers, en veillant à ce qu’il y ait au moins une
variable dans chaque casier. On pourrait aussi, par exemple, affecter
les valeurs 1, 0 et –1 à un système d’opérations boursières, pour
indiquer l’achat, la vente et le maintien. Comme dans la méthode
« ordre », Evolver organise les valeurs existantes. Il n’y a donc pas de
plage min-max ni d’option de nombres entiers ou réels à définir.
REMARQUE : Si vous choisissez la méthode « groupement », ne
laissez aucune cellule blanche, à moins que vous ne désiriez que la
valeur 0,0 soit considérée comme l’un des groupes.
Chapitre 5 : Guide de référence Evolver
107
Remarquez que la méthode « recette » sous option de valeurs
« entières » activée et plage de 1 à 3 (ou autre nombre applicable) se
rapprocherait de la méthode « groupement ». La différence tient à la
manière dont les méthodes « recette » et « groupement » exécutent
leur recherche. Les routines de sélection, mutation et croisement sont
différentes : le groupement considère davantage les valeurs de toutes
les variables, car il peut permuter les ensembles de variables entre les
différents groupes.
Les exemples ci-dessous illustrent un ensemble de valeurs de
variables telles qu’elles pourraient figurer dans une feuille de calcul
avant l’invocation d’Evolver, puis selon deux nouveaux scénarios
résultant de la méthode de résolution groupement.
Méthode de
résolution budget
Ensemble initial de
valeurs de variables
Ensemble de valeurs de
groupement possibles
Autre ensemble de
valeurs de
groupement possibles
6
6
8
7
6
7
8
8
6
8
7
7
Un « budget » est comparable à une « recette » si ce n’est que toutes
les valeurs des variables doivent représenter un certain total. Ce
nombre représente le total des valeurs des variables au moment du
démarrage d’une optimisation.
Par exemple, pour trouver le meilleur moyen de répartir un budget
annuel entre plusieurs services, la méthode de résolution « budget »
prend le total des valeurs actuelles des services et utilise cette somme
comme budget total à distribuer de manière optimale. Les exemples
ci-dessous illustrent deux nouveaux scénarios résultant de la méthode
de résolution budget.
Ensemble initial de
valeurs de budget
Ensemble de valeurs
de budget possibles
Autre ensemble de
valeurs de budget
possibles
200
93,1
223,5
3,5
30
0
10
100
-67
10
0,4
67
Différentes valeurs sont essayées, mais leur somme demeure 223,5.
108
Commande Définition du modèle
Méthode de
résolution
« projet »
La méthode de résolution « projet » est similaire à la méthode
« ordre », si ce n’est que certains éléments (tâches) doivent en
précéder d’autres. Elle est utile à la gestion de projet, pour réorganiser
l’ordre d’exécution des tâches, tout en respectant toujours la
préséance des contraintes.
Un problème modélisé sous la méthode de résolution Projet est
beaucoup plus facile à gérer et à comprendre si les cellules ajustables
contenant l’ordre des tâches sont présentées en une seule colonne,
plutôt que sur une ligne. La méthode de résolution attend en effet une
organisation verticale des cellules de tâches précédentes ; il est du
reste plus facile d’examiner la feuille de calcul sous présentation
verticale des cellules ajustables.
Après avoir spécifié l’emplacement des cellules ajustables, on précise
celui des cellules de tâches précédentes dans le volet Tâches précédentes
de la boîte de dialogue. Il s’agit ici d’un tableau de cellules décrivant
l’ordre de précédence des tâches. La méthode de résolution se réfère à
ce tableau pour réorganiser les variables d’un scénario jusqu’à ce que
les contraintes de précédence soient satisfaites. Il doit y avoir une
ligne dans la plage de tâches précédentes pour chaque tâche comprise
dans les cellules ajustables. À partir de la première colonne de la
plage des tâches précédentes, le numéro d’identification de chaque
tâche dont la tâche de la ligne considérée dépend doit être indiqué
dans des colonnes différentes.
Exemple de configuration de l’ordre de précédence pour
la méthode de résolution Projet.
La plage des tâches précédentes doit être spécifiée sur n lignes sur m
colonnes, où n représente le nombre de tâches comprises dans le
projet (cellules ajustables) et m le plus grand nombre de tâches
précédentes possible pour une tâche.
Chapitre 5 : Guide de référence Evolver
109
Les exemples ci-dessous illustrent un ensemble de valeurs de
variables telles qu’elles pourraient figurer dans une feuille de calcul
avant l’invocation d’Evolver, puis selon deux nouveaux scénarios
résultant de la méthode de résolution projet, compte tenu de la
contrainte que 2 doit toujours suivre 1 et 4 doit toujours suivre 2.
Méthode de
résolution
« programme »
Ensemble initial de
valeurs de variables
Ensemble de valeurs
de projet possibles
Autre ensemble de
valeurs de projet
possibles
1
1
1
2
3
2
3
2
4
4
4
3
Un programme est similaire à un groupement : il s’agit d’une
affectation de tâches dans le temps. Chaque tâche est censée être de
même durée, à l’image des classes d’un établissement scolaire.
Contrairement au groupement, toutefois, la boîte de dialogue
Paramètres du groupe de cellules ajustables de la méthode de
résolution « programme » permet de spécifier directement le nombre
de blocs temps (ou groupes) à utiliser. Lorsque cette méthode est
sélectionnée, ses options s’affichent dans le volet inférieur de la boîte
de dialogue.
Dans le volet Paramètres d’optimisation, remarquez qu’une plage de
cellules de contrainte peut être définie pour cette méthode. La
longueur de cette plage est illimitée, mais sa largeur doit être
d’exactement trois colonnes. Huit types de contraintes sont reconnus :
1) (avec) Les tâches de la 1re et de la 3e colonnes doivent avoir lieu dans le
même bloc temps.
2) (pas avec) Les tâches de la 1re et de la 3e colonnes ne doivent pas avoir
lieu dans même bloc temps.
3) (avant) La tâche de la 1re colonne doit avoir lieu avant celle de la 3e
colonne.
110
Commande Définition du modèle
4) (à) La tâche de la 1re colonne doit figurer dans le bloc temps de la 3e
colonne.
5) (pas après) La tâche de la 1re colonne doit avoir lieu en même temps que
celle de la 3e colonne ou avant.
6) (pas avant) La tâche de la 1re colonne doit avoir lieu en même temps que
celle de la 3e colonne ou après.
7) (pas à) La tâche de la 1re colonne ne doit pas figurer dans le bloc temps de
la 3e colonne.
8) (après) La tâche de la 1re colonne doit avoir lieu après celle de la 3e
colonne.
Une contrainte peut être désignée par son code numérique (1 à 8) ou
par sa description textuelle (après, pas à, etc.) (Remarque : Toutes les
versions traduites d’Evolver reconnaissent la description de
contrainte entrée en anglais (after, not at, etc.) aussi bien que dans la
langue traduite.) Toutes les contraintes définies dans le problème
doivent être satisfaites. Pour définir les contraintes, recherchez un
espace vide sur la feuille de calcul et créez-y un tableau dont les
colonnes de gauche et de droite représentent les tâches, et celle du
milieu indique le type de contrainte. Un chiffre de 1 à 8 représente le
type de contrainte correspondant décrit ci-dessus. Les cellules de la
plage de contrainte doivent contenir les données de contrainte
applicables avant le lancement de l’optimisation.
Cette tâche
Contrainte
Cette tâche
5
4
2
12
2
8
2
3
1
7
1
5
6
2
4
9
3
1
Chapitre 5 : Guide de référence Evolver
111
Les exemples ci-dessous illustrent un ensemble de valeurs de
variables telles qu’elles pourraient figurer dans une feuille de calcul
avant l’invocation d’Evolver, puis selon deux nouveaux scénarios
résultant de la méthode de résolution programme.
Ensemble initial de
valeurs de variables
Ensemble de valeurs
de programme
possibles
Autre ensemble de
valeurs de
programme possibles
1
1
1
2
1
3
3
3
1
1
1
2
2
2
2
3
3
2
REMARQUE : La méthode de résolution « programme » utilise
toujours des nombres entiers, à partir de 1 (1, 2, 3, etc.),
indépendamment des valeurs originales des cellules ajustables.
Taux de
croisement et
de mutation
L’une des plus grandes difficultés de la recherche de solutions
optimales, quand le problème semble présenter des possibilités
infinies, consiste à déterminer le point de concentration. Autrement
dit, combien de temps de calcul faut-il consacrer à la recherche dans
de nouvelles zones de « l’espace de résolution » et combien au
raffinement des solutions, dans la population testée, qui se sont déjà
révélées plutôt bonnes ?
Une bonne partie du succès de l’algorithme génétique a été attribuée à
sa capacité de préserver cet équilibre inhérent. La structure de l’AG
permet aux bonnes solutions de « se reproduire », tout en gardant
toutefois des organismes « moins aptes » pour entretenir la diversité
dans l’espoir que, peut-être, un « gène » latent se révèle important
dans la solution finale.
Le croisement et la mutation sont deux paramètres qui affectent
l’envergure de la recherche. Evolver permet à l’utilisateur de les
changer avant, mais aussi pendant le processus évolutif. Ainsi, un
utilisateur informé peut aider l’AG en décidant de l’endroit où il doit
concentrer son énergie. Il est inutile, dans la plupart des cas, d’ajuster
les paramètres de croisement et de mutation par défaut (0,5 et 0,1,
respectivement). Au cas où vous désireriez affiner l’algorithme de
résolution d’un problème, comparer ou, simplement, faire
112
Commande Définition du modèle
d’expérience de différents réglages, les paragraphes qui suivent
présentent une brève introduction à ces deux paramètres.
•
Croisement. Le taux de croisement peut être réglé entre 0,01 et
1,0. Il reflète la probabilité que de futurs scénarios ou
« organismes » contiennent un mélange d’information de la
génération précédente d’organismes parents. Les utilisateurs
expérimentés peuvent changer ce taux pour raffiner la
performance d’Evolver face à un problème complexe.
Ainsi, un taux de 0,5 veut dire qu’un organisme descendant tirera
environ 50 % de ses valeurs variables d’un parent et les valeurs
restantes de l’autre parent. Un taux de 0,9 veut dire qu’environ
90 % des valeurs de l’organisme descendant viendront du
premier parent et les 10 % restants de l’autre parent. Au taux de
croisement 1, aucun croisement n’intervient et seuls des clones
des parents sont évalués.
Evolver utilise par défaut un taux de croisement de 0,5. Il est
possible de changer le taux de croisement après le lancement
d’une optimisation, à travers l’utilitaire Suivi Evolver (voir plus
loin dans ce chapitre).
•
Taux de mutation. Le taux de mutation peut être réglé entre 0,0 et
1,0. Il reflète la probabilité que les scénarios futurs contiennent
des valeurs aléatoires. Un taux de mutation supérieur veut
simplement dire qu’un plus grand nombre de mutations ou
valeurs de « gène » aléatoires sera introduit dans la population.
Comme la mutation intervient après le croisement, un taux de
mutation réglé sur 1 (100 % de valeurs aléatoires) empêche
effectivement le croisement de produire le moindre effet et
Evolver ne produira dans ce cas que des scénarios totalement
aléatoires.
Si toutes les données de la solution optimale se trouvaient
quelque part dans la population, l’opérateur de croisement seul
suffirait à composer, en fin de compte, la solution. La mutation
s’est révélée une force puissante dans le monde biologique, pour
beaucoup des raisons qui la rendent utiles aussi dans un
algorithme génétique : il est essentiel d’entretenir la diversité
d’une population d’organismes individuels et d’éviter ainsi
qu’elle ne devienne trop rigide et inapte à s’adapter à un
environnement dynamique. Comme dans un algorithme
génétique, les mutations génétiques, chez les animaux, sont
souvent la cause ultime du développement de nouvelles fonctions
critiques.
Chapitre 5 : Guide de référence Evolver
113
Il est inutile, dans la plupart des cas, d’ajuster le paramètre de
mutation par défaut. Les utilisateurs expérimentés peuvent
cependant l’ajuster pour raffiner la performance d’Evolver face à
un problème complexe : lorsque, par exemple, l’utilisateur désire
renforcer les mutations si la population est plutôt homogène et
qu’aucune nouvelle solution n’a été produite depuis quelques
centaines d’essais. La variation de ce paramètre s’effectue
généralement entre 0,06 et 0,2. Il est possible de changer
dynamiquement le taux de mutation après le lancement d’une
optimisation, à travers l’utilitaire Suivi Evolver (voir plus loin
dans ce chapitre).
L’option Auto, dans la liste déroulante du champ Taux de
mutation, active l’ajustement automatique du taux. Cette option
permet à Evolver d’accroître automatiquement le taux de
mutation lorsqu’un organisme « vieillit » significativement (c.-à-d.
qu’il ne change pas sur un nombre considérable d’essais). Pour de
nombreux modèles, surtout lorsque le taux de mutation optimal
est inconnu, l’option Auto produit plus rapidement de meilleurs
résultats.
Nombre de blocs
temps et cellules
sous contrainte
Tâches
précédentes
114
Pour plus de détails concernant ces options, voir la méthode de
résolution Programme dans la section de ce chapitre consacrée aux
Méthodes de résolution.
Pour plus de détails concernant ces options, voir la méthode de
résolution Projet dans la section de ce chapitre consacrée aux Méthodes
de résolution.
Commande Définition du modèle
Opérateurs
Pour la méthode de résolution Recette, Evolver inclut des opérateurs
génétiques sélectionnables. L’onglet Opérateurs de la boîte de
dialogue Paramètres du groupe de cellules ajustables permet de
sélectionner l’opérateur génétique (tel que croisement heuristique ou
mutation limitrophe) à utiliser lors de la génération des valeurs
possibles d’un ensemble de cellules ajustables. Evolver peut même
tester automatiquement tous les opérateurs disponibles et identifier le
plus performant pour le problème considéré.
Les algorithmes génétiques emploient les opérateurs génétiques pour
créer de nouveaux membres dans la population de membres actuels.
Deux des types d’opérateurs génétiques utilisés par Evolver sont la
mutation et le croisement. L’opérateur de mutation détermine si des
changements aléatoires vont se produire au niveau des « gènes » (les
variables) et comment. L’opérateur de croisement détermine comment
les paires de membres d’une population échangent leurs gènes pour
produire une « descendance » susceptible de présenter une meilleure
solution que l’un ou l’autre des « parents ».
Evolver gère les opérateurs génétiques spécialisés suivants :
♦
Croisement arithmétique – Crée un nouveau descendant par
combinaison arithmétique des deux parents (par opposition à
l’échange de gènes).
♦
Croisement heuristique – Utilise les valeurs produites par les
parents pour déterminer le mode de production du descendant.
Chapitre 5 : Guide de référence Evolver
115
Mène la recherche dans la direction la plus prometteuse et raffine
au niveau local.
♦
Mutation de Cauchy – Conçu pour produire, la plupart du
temps, de faibles variations de variables mais capable aussi de
produire, occasionnellement, de fortes variations.
♦
Mutation limitrophe – Conçu pour optimiser rapidement les
variables qui affectent le résultat de manière monotone et qui
peuvent être portées aux extrêmes de leur plage sans violer les
contraintes.
♦
Mutation non uniforme – Produit des mutations de plus en plus
faibles à mesure que le nombre d’essais calculés augmente.
Evolver peut ainsi « raffiner » ses réponses.
♦
Linéaire – Conçu pour résoudre les problèmes pour lesquels la
solution optimale se trouve à la limite de l’espace de recherche
défini par les contraintes. Cette paire d’opérateurs de mutation et
de croisement convient particulièrement bien à la résolution des
problèmes d’optimisation linéaire.
♦
Recherche locale – Conçu pour mener la recherche, dans l’espace
de résolution, dans le voisinage d’une solution antérieure, avec
expansion dans les directions qui produisent une amélioration et
contraction dans celles qui produisent un moins bon résultat.
Suivant le type de problème d’optimisation considéré, différentes
combinaisons d’opérateurs de mutation et de croisement peuvent
produire de meilleurs résultats que d’autres. Pour la méthode de
résolution Recette, un nombre quelconque d’opérateurs peut être
sélectionné sous l’onglet Opérateurs de la boîte de dialogue
Paramètres du groupe de cellules ajustables. En présence de sélections
multiples, Evolver teste les combinaisons valables des opérateurs
sélectionnés pour identifier les plus performants pour le modèle.
Après une exécution, la feuille de synthèse d’optimisation classe chaque
opérateur sélectionné en fonction de sa performance durant
l’exécution. Pour les exécutions ultérieures du même modèle, la
sélection des quelques opérateurs les plus performants peut favoriser
un processus d’optimisation plus rapide et plus performant.
116
Commande Définition du modèle
REMARQUE : Lors de la création de groupes multiples de cellules
ajustables, vérifiez qu’aucune cellule de la feuille de calcul ne figure
dans plusieurs groupes différents. Chaque groupe de cellules
ajustables doit contenir des cellules ajustables uniques car les valeurs
du premier groupe seraient sinon omises et remplacées par celles du
second groupe. S’il vous paraît qu’un problème doit être représenté
par plus d’une méthode de résolution, considérez la répartition des
variables en au moins deux groupes.
Chapitre 5 : Guide de référence Evolver
117
Contraintes
Evolver admet les contraintes, qui définissent les conditions à remplir
pour qu’une solution soit valable. Les contraintes définies figurent
dans le tableau Contraintes de la boîte de dialogue de Définition du
modèle.
Ajouter – Ajout
de contraintes
118
Cliquez sur le bouton Ajouter, en regard du tableau Contraintes, pour
afficher la boîte de dialogue Paramètres de contrainte et y définir les
contraintes voulues. La description, le type, la définition et le moment
d’évaluation de la contrainte désirée se définissent dans cette boîte de
dialogue.
Commande Définition du modèle
Type de
contrainte
Format de
contrainte Simple
ou Formule
Evolver admet deux types de contraintes :
•
Ferme ‐ Les contraintes fermes sont les conditions qui doivent
être satisfaites pour qu’une solution soit valable (par exemple,
une contrainte ferme pourrait être exprimée sous la forme
C10<=A4, et si une solution générait une valeur C10 supérieure à
celle de la cellule A4, la solution serait rejetée).
•
Souple‐ Les contraintes souples sont les conditions que l’on veut
respecter autant que possible, mais pour lesquelles on est prêt à
accepter le compromis en vue d’une importante amélioration de
pertinence ou de résultat de cellule cible. (Par exemple, une
contrainte souple pourrait être exprimée sous la forme C10<100 :
C10 pourrait dépasser la valeur 100, mais la valeur calculée de la
cellule cible serait alors diminuée conformément à la fonction de
pénalité définie.)
Les formules peuvent être définies selon deux formats : Simple ou
Formule. Le type d’information admis pour une contrainte dépend du
format sélectionné.
•
Simple – Le format Simple permet la définition des contraintes
selon de simples relations <, <=, >, >= ou =, où une cellule est
comparée à la valeur numérique entrée. Par exemple :
0<Valeur de A1<10
où A1 s’entre dans la case Plage de cellules, 0 dans la case Min et 10
dans la case Max. Les opérateurs désirés se sélectionnent dans les
listes déroulantes. Sous une contrainte de format « Simple », on
peut entrer une valeur Min, une valeur Max, ou les deux. Les
valeurs Min et Max entrées doivent être numériques.
•
Formule – Le format Formule permet l’entrée, pour la contrainte,
d’une formule Excel valable, telle que A19<(1,2*E7)+E8. Evolver
vérifie si la formule entrée est VRAIE ou FAUSSE, afin de
déterminer le respect ou non de la contrainte.
Chapitre 5 : Guide de référence Evolver
119
Contraintes
souples
Les contraintes souples sont les conditions que l’on veut respecter
autant que possible, mais pour lesquelles on est prêt à accepter le
compromis en vue d’une importante amélioration de pertinence ou de
résultat de cellule cible. Lorsqu’une contrainte souple n’est pas
satisfaite, il en résulte un changement de résultat pour la cellule cible,
plus éloigné de sa valeur optimale. L’importance du changement
imputable à une contrainte souple non satisfaite se calcule d’après
une fonction de pénalité définie au moment de la configuration de la
contrainte souple.
Concernant les fonctions de pénalité :
•
Définition d’une fonction de pénalité. Evolver propose une
fonction de pénalité par défaut, affichée dès les premières étapes
de définition d’une contrainte souple. Une formule Excel valable
quelconque peut cependant être utilisée pour calculer
l’importance de la pénalité à appliquer lorsque la contrainte
souple n’est pas satisfaite. Une fonction de pénalité ainsi entrée
doit inclure le mot-clé écart, pour représenter le dépassement
absolu de la limite de la contrainte. Au terme de chaque
simulation de solution itérative, Evolver vérifie si la contrainte
souple a été respectée. Si non, la valeur de l’écart est introduite
dans la formule de pénalité pour calcul de la pénalité à appliquer
à la statistique de la cellule cible.
La pénalité s’ajoute à la statistique calculée pour la cellule cible ou
s’en soustrait, de manière à la rendre « moins optimale ». Ainsi, si
Maximum est sélectionné dans le champ But d’optimisation de la
boîte de dialogue Modèle d’Evolver, la pénalité est déduite de la
statistique calculée pour la cellule cible.
120
Commande Définition du modèle
•
Visualisation des effets d’une fonction de pénalité entrée.
Evolver s’accompagne d’une feuille de calcul Excel intitulée
Penalité.xls, utile à l’évaluation des effets de différentes fonctions
de pénalité sur les contraintes souples et les résultats de cellule
cible.
Cette feuille de calcul permet la sélection, dans un modèle, d’une
contrainte souple dont on désire analyser les effets. On peut ensuite
changer la fonction de pénalité pour voir comment elle mappera une
valeur spécifique pour une contrainte souple non satisfaite dans une
valeur cible particulière pénalisée. Par exemple, si la contrainte souple
est A10<100, on pourrait consulter Penalité.xls pour voir ce que serait
la valeur cible si une valeur de 105 était calculée pour la cellule A10.
•
Visualisation des pénalités appliquées. Lorsqu’une pénalité est
appliquée à la cellule cible sous l’effet d’une contrainte souple
non satisfaite, Suivi Evolver permet de visualiser l’importance de
cette pénalité. Les valeurs des pénalités figurent aussi dans le
Journal d’optimisation créé, facultativement, après l’optimisation.
REMARQUE : Si vous placez une solution dans votre feuille de calcul
sous les options Actualiser les valeurs de cellules ajustables de la
boîte de dialogue Arrêt, le résultat calculé pour la cellule cible affiché
dans le tableur n’inclut pas les pénalités appliquées pour cause de
contraintes souples non respectées. Consultez la feuille Journal
d’optimisation pour obtenir le résultat pénalisé et l’importance de la
pénalité imposée sous l’effet de chaque contrainte souple non
satisfaite.
Chapitre 5 : Guide de référence Evolver
121
•
122
Contraintes souples dans les formules de calcul. Les fonctions
de pénalité peuvent être appliquées directement dans les
formules de la feuille de calcul. Les contraintes souples
appliquées directement dans la feuille de calcul ne doivent pas
être définies dans la boîte de dialogue principale d’Evolver. Pour
plus de détails sur l’application directe des fonctions de pénalité
dans la feuille de calcul, voir le Chapitre 9 : Et aussi…, sous le titre
Contraintes souples.
Commande Définition du modèle
Commande Paramètres d'optimisation
Commande Paramètres d’optimisation – Onglet
Général
Définit les paramètres généraux d’une optimisation.
L’onglet Général de la boîte de dialogue Paramètres d’optimisation
affiche les paramètres de population, d’actualisation de l’affichage et
de racine de nombres aléatoires.
Les options Paramètres d’optimisation suivantes sont proposées :
•
Population. Ce paramètre indique à Evolver le nombre
d’organismes (ou ensembles complets de variables) devant être
stockés en mémoire à tout moment. La question de la population
optimale à utiliser pour différents problèmes continue à faire
l’objet de nombreux débats et d’une intense recherche, mais nous
recommandons généralement 30 à 100 organismes, suivant
l’envergure du problème (population proportionnelle au
problème). L’opinion générale est qu’une population plus vaste
demande plus de temps pour produire une solution mais est plus
susceptible de trouver une réponse globale car elle dispose d’un
capital génétique plus diversifié.
•
Racine de nombres aléatoires. Cette option permet de régler la
valeur de départ du générateur de nombres aléatoires d’Evolver.
Lorsqu’une même valeur de départ est utilisée, l’optimisation
génère des réponses identiques pour un même modèle pour
autant qu’il ne soit pas modifié. La racine doit être un nombre
entier compris entre 1 et 2147483647.
Chapitre 5 : Guide de référence Evolver
123
Commande Paramètres d’optimisation – Onglet
Temps d’exécution
Définit les paramètres de temps d’exécution d’une
optimisation.
Cet onglet de la boîte de dialogue Paramètres d’optimisation affiche
les paramètres de temps d’exécution de l’optimisation Evolver. Les
conditions paramétrées ici spécifient la manière et le moment d’arrêt
d’une optimisation Evolver. Une fois l’optimisation démarrée,
Evolver s’exécute en continu, à la recherche de meilleures solutions,
de simulation en simulation, jusqu’à ce que les critères d’arrêt soient
satisfaits. Un nombre quelconque de ces conditions peut être activé –
ou même aucune si l’on veut qu’Evolver poursuive indéfiniment la
recherche (ou jusqu’au moment où l’utilisateur l’arrête
manuellement). Lorsque plusieurs conditions sont activées, Evolver
arrête l’optimisation dès que l’une d’entre elles est remplie.
Indépendamment de ces sélections, il est possible d’arrêter Evolver
manuellement, à tout moment, en cliquant sur le bouton d’arrêt de la
fenêtre de progression ou de Suivi Evolver.
124
Commande Paramètres d'optimisation
Optimisation
Les options Temps d’exécution suivantes sont proposées :
•
Essais – Sous cette option, Evolver s’arrête après génération du
nombre d’essais indiqué.
Le paramètre Essais est particulièrement utile à la comparaison
d’efficacité d’Evolver lors de l’essai de différentes méthodes de
modélisation. La manière dont on modélise un problème, ou le
choix d’une méthode de résolution différente, peut accroître
l’efficacité d’Evolver. L’exécution d’un nombre donné de
simulations indique l’efficacité de convergence d’Evolver sur une
solution, indépendamment des différences de nombre de
variables choisies, de la vitesse de traitement de l’ordinateur ou
des délais de régénération de l’écran. La feuille de synthèse
d’optimisation Evolver est également utile à la comparaison des
résultats d’une simulation à l’autre. Pour plus de détails sur les
feuilles de synthèse d’optimisation, voir la section Suivi Evolver –
Options d’arrêt, plus loin dans ce chapitre.
•
Durée – Sous cette option, Evolver arrête de simuler ses scénarios
après écoulement du nombre indiqué d’heures, minutes ou
secondes. Un nombre réel positif quelconque peut être entré pour
ce paramètre (600, 5,2, etc.)
•
Progression – Sous cette option, Evolver arrête la simulation de
scénarios lorsque l’amélioration de la cellule cible est inférieure à
la valeur indiquée (critère de changement). Le nombre (entier) de
simulations à considérer peut être indiqué. Un pourcentage (1 %,
par exemple) peut être défini comme valeur de changement
maximum.
Supposons par exemple que l’on essaie de maximiser la moyenne
de la cellule cible et que, après 500 simulations, la meilleure
réponse trouvée jusque là est 354,8. Si l’option Progression est la
seule condition d’arrêt sélectionnée, Evolver s’interrompra à la
600e simulation et ne continuera que s’il trouve une réponse égale
à au moins 345,9 dans les 100 dernières simulations. Autrement
dit, si les réponses d’Evolver ne se sont pas améliorées d’au moins
0,1 au cours des 100 dernières simulations, la recherche s’arrête.
Pour les problèmes plus complexes, il peut être utile de porter le
nombre de simulations à 500 avant de déterminer si l’amélioration
est suffisante pour justifier la poursuite de l’optimisation.
Chapitre 5 : Guide de référence Evolver
125
Cette option représente la condition d’arrêt la plus courante, car
elle apporte à l’utilisateur un moyen efficace d’arrêter
l’optimisation après le ralentissement du taux d’amélioration,
quand Evolver ne semble plus trouver de meilleures solutions.
Sur les graphiques des meilleurs résultats de l’onglet Progression
de Suivi Evolver, les graphiques atteignent un plateau ou leurs
courbes s’aplanissent pendant un moment avant que cette
condition ne soit remplie et qu’Evolver s’arrête. La progression
représente ainsi un mode automatique d’arrêt lorsque les niveaux
d’amélioration se nivellent.
•
La formule est vraie. Cette condition arrête l’optimisation lorsque
la formule Excel entrée (ou référencée) s’avère (VRAIE).
•
Arrêt sur erreur. Cette condition arrête l’optimisation lorsqu’une
valeur erronée est calculée pour la cellule cible.
REMARQUE : La sélection de conditions d’arrêt n’est pas obligatoire.
En leur absence, Evolver s’exécute indéfiniment, jusqu’à arrêt manuel
commandé depuis la fenêtre Suivi Evolver.
126
Commande Paramètres d'optimisation
Commande Paramètres d’optimisation – Onglet
Affichage
Définit les paramètres d’affichage d’une optimisation.
Cet onglet de la boîte de dialogue Paramètres d’optimisation définit
les paramètres de l’affichage en cours d’optimisation.
Les options suivantes sont proposées :
•
Réduire Excel au démarrage. Sous cette option, Excel se réduit au
démarrage d’une optimisation.
•
Afficher les recalculs Excel. Sous cette option, Excel s’actualise à
chaque meilleur essai ou à la fin de chaque essai.
•
Tenir un journal des essais. Sous cette option, Evolver tient un
journal courant de chaque nouvelle simulation exécutée. Ce
journal peut être consulté dans la fenêtre de Suivi Evolver.
Chapitre 5 : Guide de référence Evolver
127
Commande Paramètres d’optimisation – Onglet
Macros
Définit les macros à exécuter en cours d’optimisation.
Des macros VBA peuvent être exécutées à différent moments d’une
optimisation ainsi que pendant la simulation de chaque solution
itérative. Il est ainsi possible de développer des calculs personnalisés
à invoquer en cours d’optimisation.
Les macros peuvent être exécutées aux moments suivants de
l’optimisation :
•
En début d’optimisation – La macro s’exécute après invocation
de l’icône Exécuter, avant la génération de la première solution
itérative.
•
Avant le recalcul de chaque essai – La macro s’exécute avant le
recalcul de chaque essai exécuté.
•
Après le recalcul de chaque essai – La macro s’exécute après le
recalcul de chaque essai exécuté.
•
Après le stockage de la sortie – La macro s’exécute après chaque
essai exécuté et après le stockage de la valeur de la cellule cible.
•
En fin d’optimisation – La macro s’exécute en fin d’optimisation.
Cette fonction permet d’exécuter des calculs tributaires d’une macro
au cours d’une optimisation. Les calculs de « bouclage » itératif et
calculs nécessitant de nouvelles données provenant de sources
externes en sont deux exemples.
Nom de la macro définit la macro à exécuter.
128
Commande Paramètres d'optimisation
Commande Démarrer l'optimisation
Démarre une optimisation.
La commande ou l’icône Démarrer l’optimisation lance l’exécution
d’une optimisation du modèle et du classeur actifs. Dès le démarrage,
Evolver affiche cette fenêtre de progression :
Cette fenêtre affiche l’information suivante :
•
Essai : nombre total d’essais effectués ; x valables indique le
nombre de ces essais pour lesquels toutes les contraintes ont
été satisfaites.
•
Temps d’exécution : temps écoulé de l’exécution.
•
Valeur originale : valeur originale de la cellule cible.
•
Meilleure valeur : meilleure valeur actuelle de la cellule cible
à minimiser ou maximiser.
Chapitre 5 : Guide de référence Evolver
129
La barre d’outils Evolver de la fenêtre de progression propose les
options suivantes :
130
•
Afficher les options d’actualisation Excel. L’affichage Excel peut
être actualisé à chaque essai, à chaque meilleur essai ou jamais.
Remarquez que dans certaines situations, l’écran s’actualise
indépendamment de ces paramètres : en cas de pause de
l’optimisation, par exemple.
•
Afficher Suivi Evolver. Affiche la pleine fenêtre de Suivi Evolver.
•
Exécuter. Cette icône lance la recherche Evolver d’une solution
basée sur la description actuelle contenue dans la boîte de
dialogue Modèle Evolver. Après pause, l’icône Exécuter permet
de relancer la recherche de meilleures solutions.
•
Pause. Pour suspendre ou « figer » momentanément le processus
Evolver, cliquez sur l’icône Pause. La pause permet d’ouvrir et
d’explorer les données de Suivi Evolver, de changer les
paramètres, d’examiner la population au complet, d’afficher un
rapport d’état ou de copier un graphique.
•
Arrêt. Arrête l’optimisation.
Commande Démarrer l'optimisation
Commandes Utilitaires
Commande Paramètres d’application
Affiche la boîte de dialogue Paramètres d’application, où se
définissent les paramètres par défaut.
De nombreux paramètres Evolver peuvent être configurés par défaut
et appliqués à chaque exécution du programme. Notamment : les
paramètres d’arrêt par défaut, les taux de croisement et de mutation
par défaut, etc.
Chapitre 5 : Guide de référence Evolver
131
Commande Solveur de contraintes
Exécute le Solveur de contraintes
Le Solveur de contraintes améliore la capacité de traitement des
contraintes de modèle d’Evolver. Lorsqu’Evolver exécute une
optimisation, les valeurs de cellules ajustables de départ sont censées
satisfaire à toutes les contraintes fermes – ce qui veut dire que la
solution originale est censée être valable. Si tel n’est pas le cas,
l’algorithme peut exécuter un très grand nombre de simulations avant
de trouver une première solution valable. Cependant, si un modèle
contient plusieurs contraintes, les valeurs de cellules ajustables qui
seront conformes à toutes ne sont pas nécessairement évidentes.
Si un modèle Evolver contient plusieurs contraintes fermes et que les
optimisations échouent (aucune solution valable), vous en êtes avisé
et le Solveur de contraintes peut être exécuté. Le Solveur de
contraintes exécute l’optimisation en mode spécial, dans le but
d'identifier une solution conforme à toutes les contraintes fermes.
L’utilisateur peut suivre la progression de l’opération comme s’il
s’agissait d’une optimisation ordinaire. La fenêtre de progression
affiche le nombre de contraintes satisfaites dans la solution originale
et dans la meilleure.
132
Commandes Utilitaires
Un bouton de la fenêtre donne accès au Suivi Evolver. En mode
Solveur de contraintes, les détails de progression de l’optimisation
peuvent être consultés comme en mode d’optimisation ordinaire, sous
les onglets Progression, Synthèse, Journal, Population et Diversité.
En mode Solveur de contraintes, l’écran de suivi propose un autre
onglet encore, intitulé Solveur de contraintes. Cet onglet affiche l’état
de chaque contrainte ferme (Satisfaite ou Non satisfaite) pour les
solutions Meilleure, Originale et Dernière.
L’optimisation du Solveur de contraintes s’arrête automatiquement
lorsqu’une solution conforme à toutes les contraintes fermes est
identifiée. Elle peut aussi être interrompue d’un clic sur le bouton
d’arrêt de la fenêtre de progression ou de Suivi Evolver. En fin
d’exécution du Solveur de contraintes, vous pouvez choisir, sous
l’onglet Options d’arrêt du Suivi Evolver, la meilleure solution, la
solution originale ou la dernière solution, comme pour les
optimisations réalisées en mode ordinaire.
Remarquez qu’il n’est pas nécessaire de configurer le Solveur de
contraintes avant l’exécution : les paramètres spécifiés dans le modèle
sont utilisés, à la seule différence que l’objectif d’optimisation est de
trouver une solution conforme à toutes les contraintes fermes.
Chapitre 5 : Guide de référence Evolver
133
134
Commandes Utilitaires
Suivi Evolver
L’icône loupe, sur la barre d’outils de la fenêtre de progression
d’Evolver, affiche l’utilitaire Suivi Evolver. Suivi Evolver régit et
rapporte toute l’activité d’Evolver.
Il permet le changement des paramètres et l’analyse de progression de
l’optimisation. On peut aussi y suivre l’information en temps réel du
problème et la progression d’Evolver sur la barre d’état, au bas de la
fenêtre.
Chapitre 5 : Guide de référence Evolver
135
Suivi Evolver – Onglet Progression
Affiche les graphiques de progression de la valeur de la
cellule cible
Cet onglet de Suivi Evolver représente graphiquement l’évolution des
résultats obtenus, par simulation, pour la cellule cible sélectionnée.
Ces graphiques de progression indiquent le nombre de simulations
sur l’axe X et la valeur de la cellule cible sur l’axe Y. Pour en changer
l’échelle, cliquez sur les limites des axes et ramenez-les à la nouvelle
valeur d’échelle désirée. Un clic droit sur le graphique de progression
ouvre la boîte de dialogue Options graphiques, pour une
personnalisation accrue des graphiques.
136
Suivi Evolver
Options
graphiques
La boîte de dialogue Options graphiques affiche les paramètres de
titres, légendes, échelle et polices du graphique affiché.
Chapitre 5 : Guide de référence Evolver
137
Suivi Evolver – Onglet Synthèse
Affiche les détails des valeurs des cellules ajustables.
Cet onglet de Suivi Evolver affiche un tableau récapitulatif des
valeurs des cellules ajustables testées pendant l’optimisation, ainsi
que les outils de réglage des taux de croisement et de mutation de
chaque groupe de cellules ajustables du modèle.
Sous le titre Paramètres de groupe de cellules ajustables, on peut
changer les taux de croisement et de mutation de l’algorithme
génétique en cours de résolution du problème. Les changements
apportés ici l’emportent sur les valeurs initiales de ces paramètres et
deviennent immédiatement applicables. Ils affectent la population (le
groupe de cellules ajustables) sélectionnée dans le champ Groupe
affiché.
Le taux de croisement par défaut de 0,5 est presque toujours
recommandé. Pour la mutation, beaucoup de modèles admettent
jusqu’à 0,4, si l’on veut trouver la meilleure solution et qu’on est prêt
à consacrer plus de temps à la recherche. Une valeur de mutation de 1
(maximum) donne lieu à une recherche totalement aléatoire. Evolver
effectue en effet la mutation après le croisement. En d’autres termes,
après que les deux parents sélectionnés ont été croisés pour créer une
solution descendante, 100 % des « gènes » de cette solution passent
par mutation à des valeurs aléatoires, annulant effectivement le rôle
du croisement (voir « taux de croisement, fonction » et « taux de
mutation, fonction » dans l’index pour plus de détails).
138
Suivi Evolver
Suivi Evolver – Onglet Journal
Affiche un journal de chaque exécution de simulation
pendant l’optimisation.
Cet onglet de Suivi Evolver affiche un tableau récapitulatif de chaque
simulation exécutée pendant l’optimisation. Ce journal inclut les
résultats relatifs à la cellule cible, à chaque cellule ajustable et aux
contraintes définies. Il n’est disponible que si l’option Tenir un
journal de tous les essais est sélectionnée sous l’onglet Affichage de
la boîte de dialogue Paramètres d’optimisation.
Les options « Afficher » régissent l’affichage du journal de tous les
essais ou de ceux pour lesquels il y a eu progression seulement
(amélioration du résultat d’optimisation). Données consignées :
1) Temps écoulé : point de départ de la simulation.
2) Essai : nombre d’essais exécutés.
3) Résultat : valeur de la statistique de la cellule cible à maximiser
ou minimiser, pénalités de contraintes souples comprises.
4) Moyenne sortie, Ec. Type sortie, Min sortie et Max sortie :
statistiques de la distribution de probabilités de la cellule cible
calculée.
5) Colonnes d’entrée : valeurs utilisées pour les cellules ajustables.
6) Colonnes de contrainte : indiquent si les contraintes ont été
satisfaites.
Chapitre 5 : Guide de référence Evolver
139
Suivi Evolver – Onglet Population
Liste toutes les variables de chaque organisme (chaque
solution possible) de la population actuelle.
Ce tableau présente une grille listant toutes les variables de chaque
organisme (chaque solution possible) de la population actuelle. Ces
organismes (« Org n ») sont classés dans l’ordre allant du pire au
meilleur. Comme ce tableau liste tous les organismes de la
population, le paramètre « Population » de la boîte de dialogue
Paramètres d’Evolver en détermine le nombre (50 par défaut). De
plus, la première colonne du tableau affiche la valeur résultante de la
cellule cible pour chaque organisme.
140
Suivi Evolver
Suivi Evolver – Onglet Diversité
Affiche un tracé couleurs de toutes les variables de la
population actuelle.
Le tracé de l’onglet Diversité attribue des couleurs aux valeurs des
cellules ajustables en fonction de la variation de la valeur d’une
cellule donnée à travers la population d’organismes (solutions)
stockés en mémoire en un point donné. (En termes d’optimisation
génétique, il s’agit ici d’une indication de la diversité du capital
génétique.) Chaque barre verticale du tracé correspond à une cellule
ajustable. Les lignes horizontales de chaque barre représentent les
valeurs de la cellule concernée dans différents organismes (solutions).
Les couleurs de ces lignes sont attribuées par division de la plage
entre la valeur minimum et maximum d’une cellule ajustable donnée
en 16 intervalles de longueur égale représentés, chacun, par une
couleur différente. Ainsi le fait que la barre verticale représentant la
deuxième cellule ajustable ne comporte qu’une seule couleur veut
dire que la cellule a la même valeur dans chaque solution en mémoire.
Chapitre 5 : Guide de référence Evolver
141
Suivi Evolver – Onglet Options d’arrêt
Affiche les options d’arrêt de l’optimisation.
Un clic sur le bouton Arrêter fait apparaître l’onglet Options d’arrêt
de Suivi Evolver. Ces options régissent l’actualisation de la feuille de
calcul en fonction des meilleures valeurs calculées pour les cellules
ajustables, le rétablissement des valeurs originales et la production
d’un rapport de synthèse d’optimisation.
OK détruit la population de solution d’Evolver et place les valeurs
sélectionnées dans le tableur. Pour enregistrer l’information relative à
la session Evolver (valeurs de population, durée et nombre d’essais
exécutés), on veillera à sélectionner la création d’un rapport de
synthèse d’optimisation.
142
Suivi Evolver
Cette boîte de dialogue s’ouvre aussi lorsqu’une condition d’arrêt
spécifiée par l’utilisateur est remplie (fin d’évaluation du nombre
d’essais demandés, durée d’optimisation écoulée, etc.) L’alerte d’arrêt
propose trois choix pour l’actualisation des valeurs des cellules
ajustables dans le tableur : Meilleures, Originales et Dernières.
•
Meilleures. Cette option accepte les résultats d’Evolver et met fin
à la recherche de meilleures solutions. Les valeurs du meilleur
scénario identifié par la recherche d’Evolver s’inscrivent dans les
cellules ajustables du tableur.
•
Originales. Cette option rétablit les valeurs originales des cellules
ajustables, avant l’exécution d’Evolver, et met fin à la recherche
de meilleures solutions.
•
Dernières. Sous cette option, Evolver place les dernières valeurs
calculées de l’optimisation dans la feuille de calcul. Cette option
est particulièrement utile au débogage des modèles.
Les options Rapports à générer peuvent produire des feuilles de
synthèse d’optimisation utiles au rapport des résultats d’une
exécution et à la comparaison des résultats d’une exécution à l’autre.
Les options de rapport suivantes sont proposées :
Chapitre 5 : Guide de référence Evolver
143
•
Synthèse d'optimisation. Ce rapport de synthèse d’optimisation
fait état des date et heure de l’exécution, des paramètres
d’optimisation utilisés, de la valeur calculée pour la cellule cible et
de la valeur de chaque cellule ajustable.
Ce rapport est utile à la comparaison des résultats d’optimisations
successives.
144
Suivi Evolver
•
Journal de tous les essais Ce rapport consigne les résultats de
tous les essais effectués.
•
Journal de progression. Ce rapport consigne les résultats de tous
les essais ayant amélioré le résultat de la cellule cible.
Chapitre 5 : Guide de référence Evolver
145
146
Chapitre 6 : Optimisation
Méthodes d’optimisation .................................................................149
Algorithmes par escalade....................................................................151
Solveur Excel ..................................................................................155
Evolver vs Solveur ...............................................................................156
Quand utiliser Evolver ........................................................................157
Types de problèmes .......................................................................159
Problèmes linéaires ................................................................159
Problèmes non linéaires .......................................................159
Problèmes à base de tables ...................................................162
Problèmes combinatoires......................................................162
Chapitre 6 : Optimisation
147
148
Méthodes d’optimisation
Comme nous l’avons vu dans les quelques exemples présentés dans
les didacticiels, certains problèmes d’optimisation sont beaucoup plus
difficiles à résoudre que d’autres. Pour les problèmes complexes, tels
que la recherche de l’itinéraire le plus court entre 1000 villes, il n’est
pas réaliste d’examiner chaque solution possible. L’approche exigerait
en effet plusieurs années de calculs sur les ordinateurs les plus
performants.
Pour résoudre ce type de problème, il faut effectuer la recherche dans
un sous-ensemble de solutions possibles. L’examen de ces solutions
peut indiquer la manière d’en trouver de meilleures, par le biais d’un
algorithme. Un algorithme représente, tout simplement, une
description, pas à pas, de l’approche d’un problème. Tous les
programmes informatiques, par exemple, reposent sur la combinaison
de nombreux algorithmes.
Commençons donc par explorer la manière dont la plupart des
algorithmes de résolution représentent un problème. Les problèmes
se répartissent pour la plupart en trois composants fondamentaux :
des entrées, une fonction et une sortie résultante.
Composants du
problème
Dans Evolver/Excel
Recherche de
étant donné
pour obtenir le
meilleur
Entrées
Fonction
Sortie
Variables
Modèle
But
Supposons que notre problème d’optimisation implique deux
variables, X et Y. En équation, ces deux variables produisent le
résultat =Z. Notre problème consiste à identifier la valeur de X et de Y
qui produit la plus grande valeur Z. Z est, en quelque sorte, la « cote »
qui indique la qualité d’une association particulière de X et Y.
Dans cet exemple
Chapitre 6 : Optimisation
Recherche de
étant donné
pour obtenir le
meilleur
X et Y
Équation
Z
149
Un tracé de chaque ensemble de X, Y et des Z résultants produirait un
graphique de surface tridimensionnel tel que celui illustré ci-dessous.
« Paysage » de scénarios ou solutions possibles.
Chaque intersection d’une valeur X et d’une valeur Y produit une
hauteur Z. Les sommets et les vallées de ce « paysage » représentent
de bonnes et de mauvaises solutions, respectivement. La recherche du
maximum ou du plus haut point de cette fonction à travers l’examen
de chaque solution prendrait beaucoup trop de temps, même sur un
ordinateur puissant doté du plus rapide des logiciels* . N’oublions pas
que nous ne donnons à Excel que la fonction en soi, pas un graphique
de la fonction, et que nous pourrions tout aussi bien nous trouver face
à un problème à 200 dimensions plutôt qu’à celui-ci, à deux
dimensions. Il nous faut donc une méthode qui nous permette
d’effectuer moins de calculs et de trouver malgré tout une
productivité maximale.
*
Dans notre diagramme, la fonction est représentée tel un paysage lisse. Dans
les rares cas où les fonctions sont simples et lisses (différenciables), il est
possible de recourir au calcul pour trouver les minima et les maxima. Les
problèmes réalistes ne se décrivent cependant pas, pour la plupart, par des
fonctions lisses.
150
Méthodes d’optimisation
Algorithmes par escalade
Considérons donc un simple algorithme, dit « d’escalade ». Cet
algorithme procède comme suit :
1)
On part d’un point aléatoire du paysage (supposition aléatoire).
2)
3)
On progresse d’une faible distance dans une direction arbitraire.
Si on aboutit à un nouveau point plus élevé, on y reste et on répète
la deuxième étape. Si le nouveau point est moins élevé, on revient au
point d’origine et on recommence.
L’escalade n’essaie qu’une solution, ou un scénario, à la fois. Nous
allons utiliser un point noir (•) pour représenter une solution possible
(un ensemble des valeurs X, Y et Z). En plaçant ce point au point de
départ aléatoire, on espère que la méthode par escalade l’amènera au
plus haut point du graphique.
Le diagramme ci-dessus illustre bien que la direction désirée est vers
la droite. Nous ne le savons cependant que parce que nous avons déjà
vu l’ensemble du paysage. Tandis que l’algorithme s’exécute, il
perçoit le paysage avoisinant, mais pas sa totalité : il voit l’arbre, mais
pas la forêt.
Chapitre 6 : Optimisation
151
Dans la plupart des problèmes réels, le paysage n’est pas aussi lisse et
il faudrait des années pour procéder au calcul complet. On ne calcule
donc que le scénario actuel et ceux de son environnement immédiat.
Imaginez que notre point noir est un homme aux yeux bandés planté
au beau milieu d’un paysage vallonné. Selon l’algorithme de
l’escalade, cet homme dirigerait le pied dans chaque direction mais ne
le poserait que s’il sentait une élévation du terrain. Il progresserait
ainsi vers le haut et finirait par arriver au sommet de la colline, où le
sol, dans chaque direction, serait maintenant plus bas. L’approche
paraît simple, mais le problème est grave si l’homme part d’un autre
endroit … et escalade la mauvaise colline (voir le diagramme cidessous) !
Même si la fonction est lisse, l’escalade peut échouer
si l’on part d’un endroit moins idéal (image de droite).
L’escalade n’identifie que le sommet le plus proche, ou le maximum
local. Ainsi, si le problème considéré présente un paysage de
solutions extrêmement accidenté, comme la plupart des modèles
réalistes, il n’est guère probable que l’escalade trouve le sommet le
plus élevé, ou même l’un des plus élevés seulement.
L’escalade présente un autre problème : comment trouve-t-on
effectivement le terrain voisin de l’emplacement où l’on se trouve ? Si
le paysage est décrit par une fonction lisse, la différenciation (une
technique de calcul) peut permettre d’identifier la direction de la côte
la plus raide. Si le paysage est discontinu ou non différenciable
(comme il l’est plus généralement dans la réalité), il faut calculer la
« pertinence » des scénarios avoisinants.
152
Méthodes d’optimisation
Supposons par exemple qu’une banque engage un agent de sécurité
de 9 à 17 heures pour garder la banque, mais qu’elle doive lui
accorder deux (2) pauses d’une demi-heure. Le problème consiste à
identifier les heures de pause optimales, compte tenu des règles
générales de rapports de performance/fatigue et les différents
niveaux d’activité de clientèle pendant la journée. On peut
commencer par essayer différentes combinaisons de pauses et par les
évaluer. Si le programme actuel prévoit les pauses à 11 et à 15 heures,
on pourrait calculer la productivité des scénarios avoisinants
suivants :
Direction
Solution actuelle
Scénario Ouest
Scénario Est
Scénario Nord
Scénario Sud
Pause 1 (x)
11 heures
10 h 45
11 h 15
11 heures
11 heures
Pause 2 (y)
15 heures
15 heures
15 heures
15 h 15
14 h 45
–Cote" (z)
= 46,5
= 44,67
= 40,08
= 49,227
= 43,97
Si le nombre de cellules ajustables (pauses) était de trois au lieu de
deux, on aurait à considérer huit directions différentes. En fait, pour
50 variables seulement (hypothèse parfaitement réaliste pour un
problème d’envergure moyenne), on devrait calculer la productivité
de 250, soit plus de mille billions de scénarios, pour un simple agent de
sécurité !
Certaines modifications peuvent être apportées à la méthode de
l’escalade pour améliorer sa capacité de produire des maxima
globaux (les collines les plus hautes de l’ensemble du paysage).
L’escalade convient le mieux à la résolution de problèmes unimodaux
(à un seul sommet), d’où le recours à cette technique par certains
programmes d’analyse. Son utilité est cependant très limitée face aux
problèmes complexes et/ou volumineux.
Chapitre 6 : Optimisation
153
154
Méthodes d’optimisation
Solveur Excel
Excel s’accompagne d’un utilitaire d’optimisation appelé Solveur. Son
rôle est similaire à celui d’Evolver : trouver les solutions optimales.
Solveur peut résoudre deux types de problèmes : linéaires et simples
non linéaires. La résolution des problèmes linéaires s’effectue selon
une routine de programmation linéaire. Cette technique
mathématique classique, parfois appelée méthode « Simplexe »,
trouve toujours la réponse parfaite aux petits problèmes purement
linéaires.
Comme la plupart des autres mini‐solveurs, le solveur Microsoft
résout également les problèmes non linéaires, selon une routine
d’escalade (dite « GRG2 »). Une routine d’escalade part des valeurs de
variable courantes et les ajuste lentement jusqu’à ce que la sortie du
modèle ne s’améliore plus. Ainsi, les problèmes qui présentent plus
d’une solution possible peuvent être impossibles à résoudre
adéquatement, car Solveur aboutit à une solution locale, sans pouvoir
accéder à la solution globale (voir la figure ci‐dessous).
Solution locale perçue
Solution globale réelle
Paysage de solutions possibles
Solveur exige en outre que la fonction représentée par le modèle soit
continue. Autrement dit, la sortie doit évoluer de manière lisse sous
l’effet de l’ajustement des entrées. Si le modèle utilise des tables de
recherche, acquiert des données bruyantes en temps réel d’un autre
programme, contient des éléments aléatoires ou implique des règles
de type « si, alors », il sera irrégulier et discontinu et Solveur ne
pourra pas le résoudre.
Solveur impose par ailleurs une limite au nombre de variables et à
celui de contraintes du problème (200), au-delà duquel une technique
plus puissante doit être utilisée.
Chapitre 6 : Optimisation
155
Evolver vs Solveur
Le Solveur Excel et Evolver ont chacun leurs qualités et leurs
faiblesses. De manière générale, Solveur est plus rapide pour la
résolution de petits problèmes simples, tandis qu’Evolver offre le seul
moyen de résoudre de nombreux autres types de problèmes. Evolver
trouve généralement aussi de meilleures réponses aux problèmes plus
vastes et plus complexes, tels qu’ils se présentent souvent dans la
réalité.
Evolver peut résoudre beaucoup plus de types de problèmes que
Solveur. Evolver peut optimiser pratiquement toutes les situations
numériques modélisables dans Excel.
Plus spécifiquement, Evolver trouve les solutions optimales aux
problèmes numériques linéaires, non linéaires, à base de tables ou
stochastiques (aléatoires). Il résout les problèmes présentant une
combinaison quelconque de ces qualités. Evolver peut aussi générer
des permutations de valeurs existantes, réordonner les valeurs ou les
groupes de manières différentes pour identifier la solution optimale.
En fait, pour tout modèle de tableur à variables pouvant être ajustées
pour influencer la sortie du modèle, Evolver peut automatiser la
recherche par le calcul intelligent de milliers de scénarios et retenue
des meilleurs.
L’algorithme génétique d’Evolver est mieux adapté que Solveur aux
interruptions : vous pouvez l’interrompre à tout moment et voir la
meilleure solution qu’Evolver a identifiée jusque là. Vous pouvez
alors apporter les changements nécessaires au problème en soi, avant
de relancer le processus. Par exemple, pour un problème
d’ordonnancement multigamme, il peut être utile d’identifier les
meilleures tâches à affecter aux machines. Lorsqu’une machine est
disponible, on peut interrompre l’algorithme génétique pour
identifier la tâche optimale à lui affecter. La tâche peut ensuite être
omise du problème et l’optimisation peut reprendre avec les tâches
restantes.
L’algorithme génétique qui donne à Evolver cette capacité de
traitement de problèmes aussi variés est aussi généralement plus lent
que Solveur ou que d’autres méthodes mathématiques ou statistiques
conventionnelles. Il existe, pour certaines catégories de problèmes,
des sous-programmes d’optimisation bien connus et bien réglés. Les
méthodes personnalisées résolvent ces problèmes plus rapidement
que la méthode universelle d’Evolver.
156
Solveur Excel
Quand utiliser Evolver
De manière générale, il convient d’utiliser Evolver dans les cas
suivants :
1) quand les algorithmes traditionnels ne produisent pas de bonnes solutions
globales ;
2) quand le problème est trop vaste et/ou contient plus de variables que ne
peut en gérer votre algorithme classique ;
3) quand le problème est trop complexe pour être résolu par une autre
méthode ;
4) quand le modèle implique des nombres aléatoires, des tables de recherche,
des instructions si-alors ou d’autres fonctions discontinues qui excluent les
solveurs classiques ;
5) quand vous n’avez pas la moindre idée de ce que pourrait être la solution
et que vous ne pouvez même pas imaginer donc le point de départ de la
recherche d’un solveur traditionnel ;
6) quand vous désirez pouvoir « assouplir » certaines contraintes « fermes »
du problème (X doit être égal à Y) et les rendre ainsi plus exactes (X devrait
être égal à Y, sous peine de perdre des Z), rendant possible l’exploration
d’une plage plus large de solutions potentiellement meilleures, même si elles
font défaut à quelques contraintes ;
7) quand il est préférable d’obtenir rapidement une bonne solution à un
problème plutôt que d’avoir à attendre la meilleure solution absolue ;
8) quand il vous faut plusieurs solutions possibles proches de la meilleure ;
9) quand vous désirez intégrer un simple et robuste algorithme de recherche
dans une application personnalisée (voir le Kit du développeur Evolver pour
plus de détails).
REMARQUE : Si les délais d’exécution le permettent, Evolver peut
toujours servir à titre complémentaire à d’autres méthodes, pour
vérifier leur précision. Si le processus est plus long que celui d’autres
méthodes, la meilleure solution qu’Evolver trouvera peut-être en vaut
très probablement l’investissement.
Chapitre 6 : Optimisation
157
Evolver ne s’inquiète pas des menus détails du problème. Peu lui
importe donc que l’utilisateur soit versé ou non dans les techniques
de programmation linéaire, la théorie de l’optimisation, les
mathématiques ou les statistiques. Il suffit, pour utiliser Evolver, de
définir les variables (les cellules qui contiennent les valeurs
ajustables), le but (la cellule qui contient la sortie) et de décrire les
valeurs qu’Evolver peut utiliser pendant la recherche de solutions
optimales.
158
Solveur Excel
Types de problèmes
Plusieurs types de problèmes se prêtent généralement à
l’optimisation. Si vous comprenez ces types de problèmes, vous serez
mieux équipé pour appliquer Evolver à vos propres modèles.
Problèmes
linéaires
Dans les problèmes linéaires, toutes les sorties sont de simples
fonctions linéaires des entrées, comme dans y=mx+b. Quand les
problèmes font appel à de simples opérations arithmétiques telles que
l’addition, la soustraction et les fonctions Excel telles que
TENDANCE() et PREVISION(), les relations entre les variables sont
purement linéaires.
Depuis l’avènement de l’ordinateur et l’invention de la méthode
Simplexe par George Dantzig, les problèmes linéaires sont assez
faciles à résoudre. Un utilitaire de programmation linéaire convient le
mieux à la résolution rapide et précise d’un simple problème linéaire.
L’utilitaire Solveur d’Excel devient un outil de programmation
linéaire lorsque la case « Modèle supposé linéaire » est cochée*.
Solveur utilise dans ce cas une routine de programmation linéaire
pour trouver rapidement la solution idéale. Si un problème peut être
exprimé en termes purement linéaires, la programmation linéaire est
le choix de prédilection. Dans la réalité, la plupart des problèmes ne
sont malheureusement pas linéaires.
Problèmes
non linéaires
Si le coût de production et de livraison de 5 000 objets était de €5 000,
cela voudrait-il dire que la production et la livraison d’un objet
coûteraient €1 ? Probablement pas. La chaîne de production de l’usine
consomme toujours de l’énergie, le travail de bureau est identique, les
matières premières doivent toujours être achetées en vrac, les camions
consomment la même quantité de carburant pour la livraison et les
chauffeurs doivent toujours être payés pour leur journée quelle que
soit l’importance du chargement. Dans la réalité, la plupart des
problèmes n’impliquent pas de variables à simples relations linéaires.
Ils impliquent des opérations de multiplication, division, des
exposants et des fonctions Excel intégrées telles que RACINE() et
CROISSANCE(). Quand les variables ont un rapport disproportionné
les unes par rapport aux autres, le problème devient non linéaire.
* Pour plus de détails sur l’utilitaire Solveur de Microsoft, voir le Guide de
l’utilisateur Excel.
Chapitre 6 : Optimisation
159
La gestion d’un processus de fabrication dans une usine de produits
chimiques présente un parfait exemple de problème non linéaire.
Supposons que nous voulions mélanger certains réactifs en vue de
l’obtention, comme résultat, d’un produit chimique. La vitesse de la
réaction peut varier de manière non linéaire suivant la quantité de
réactifs disponible. À un moment donné, le catalyseur est saturé et
l’excès de réactif devient encombrant. Le diagramme ci-dessous
illustre cette relation :
vitesse de réaction / niveau de réactif
Si l’on cherche simplement à identifier le niveau minimum de réactif
qui produira la plus grande vitesse de réaction, il suffit de partir d’un
point quelconque du graphique et de suivre la courbe jusqu’au
sommet, selon la méthode de l’escalade.
L’escalade produit toujours la meilleure réponse quand (a) la fonction
explorée est lisse et que (b) la valeur de départ est sur un versant du
plus haut sommet. Si l’une de ces conditions n’est pas satisfaite, on
risque d’aboutir à une solution locale plutôt que globale.
160
Types de problèmes
Pour les problèmes qui ne sont vraiment pas linéaires, comme on le
voit souvent en pratique, beaucoup de solutions sont possibles sur un
paysage particulièrement compliqué. Si le problème présente de
nombreuses variables et/ou que les formules impliquées sont
extrêmement bruyantes ou vallonnées, l’escalade ne trouvera
probablement pas la meilleure réponse, même après des centaines
d’essais au départ de points différents. Une solution sous-optimale et
extrêmement locale sera plus vraisemblablement produite (voir la
figure ci-dessous).
L’escalade trouve le maximum local
mais pas global.
Données bruyantes : l’escalade n’est pas
efficace, même après plusieurs essais.
Contrairement à cette méthode, Evolver applique plutôt une
technique de recherche stochastique dirigée, dite d’« algorithme
génétique ». Il évolue ainsi dans tout l’espace de solution d’un
problème, examinant de nombreuses combinaisons de valeurs en
entrée sans se perdre dans les valeurs optimales locales. Mieux
encore, Evolver favorise la « communication » entre les scénarios
intéressants, afin d’obtenir une information précieuse sur le paysage
de solution globale. Il utilise ensuite cette information pour mieux
estimer les scénarios susceptibles de réussite. Pour les problèmes
complexes ou définitivement non linéaires, il vaut mieux, et il faut
même souvent, recourir à Evolver.
Evolver génère de nombreux scénarios possibles, puis
raffine la recherche en fonction de l’information reçue.
Chapitre 6 : Optimisation
161
Problèmes à base
de tables
Beaucoup de problèmes exigent le recours à des tables de recherche et
bases de données. Ainsi, pour déterminer les quantités de différents
matériaux à acquérir, il peut être nécessaire de rechercher le prix
facturé pour différentes quantités.
Les tables et les bases de données rendent les problèmes
« discontinus » (non lisses). La recherche en devient difficile pour les
routines d’escalade telles que Solveur. Indifférent à la continuité des
fonctions qu’il évalue, Evolver peut trouver de bonnes solutions aux
problèmes qui font appel aux tables, même nombreuses, vastes et
interconnectées.
Si un problème exige la recherche de valeurs dans une base de
données ou une table de données Excel et que l’index de l’élément de
table est une variable ou une fonction de variable, il convient
d’utiliser Evolver. Si l’élément de table est simple et constant (le
même enregistrement est extrait de la table indépendamment des
valeurs des variables en entrée), il s’agit en fait simplement d’une
constante et Solveur permet probablement de résoudre efficacement
le problème.
Problèmes
combinatoires
162
Il existe une vaste catégorie de problèmes extrêmement différents des
problèmes numériques examinés jusqu’ici. Les problèmes dont les
sorties impliquent le changement d’ordre des variables en entrée
existantes ou le groupement de sous-ensembles d’entrées sont
qualifiés de problèmes combinatoires. Ces problèmes sont
généralement très difficiles à résoudre, car ils exigent souvent un
temps exponentiel. Autrement dit, la durée nécessaire à la résolution
d’un problème à 4 variables pourrait être 4 x 3 x 2 x 1, et le
redoublement du nombre de variables (8) ferait passer la durée de
résolution à 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1, soit un facteur de 1 680. Le
nombre de variables est double, mais celui des solutions possibles à
vérifier augmente de 1 680 fois. Par exemple, le choix de l’ordre de jeu
d’une équipe de base-ball est un problème combinatoire. Si l’on a 9
joueurs, on peut choisir l’un des 9 comme premier à la batte. Il faut
ensuite choisir l’un des 8 joueurs restants en deuxième position, puis
l’un des 7 joueurs restants en troisième position, etc. Il y a donc
9x8x7x6x5x4x3x2x1 possibilités d’organisation des 9 joueurs, soit
environ 362 880 ordres différents. Si l’on double le nombre de
joueurs, on se trouve face ・ 18 choix factoriels, soit
6 402 373 705 000 000 d’ordres possibles !
Types de problèmes
L’algorithme générique d’Evolver analyse intelligemment les
permutations possibles. Il s’agit d’une méthode beaucoup plus
pratique que la recherche de toutes les possibilités. L’approche est
aussi beaucoup plus efficace que l’examen de permutations purement
aléatoires : les sous-ordres des bons scénarios peuvent être conservés
et utilisés pour produire de meilleurs scénarios encore.
Chapitre 6 : Optimisation
163
164
Types de problèmes
Chapitre 7 : Algorithmes
génétiques
Introduction .....................................................................................167
Histoire.............................................................................................167
Exemple biologique........................................................................171
Exemple numérique........................................................................173
Chapitre 7 : Algorithmes génétiques
165
166
Introduction
Evolver recourt aux algorithmes génétiques pour rechercher les
réponses optimales aux modèles de simulation. Ce chapitre présente
une introduction aux algorithmes génétiques pour aider à
comprendre leur usage dans l’optimisation de modèles de simulation.
Histoire
Les premiers algorithmes génétiques ont été développés par John
Holland, à l’University of Michigan, au début des années 1970
Holland était intrigué par la facilité avec laquelle les systèmes
biologiques pouvaient exécuter des tâches qui échappaient même aux
superordinateurs les plus puissants. Les animaux peuvent, sans
erreur, reconnaître des objets, comprendre et traduire des sons et,
généralement, naviguer à travers un environnement dynamique de
manière presque instantanée.
Depuis des dizaines d’années, les scientifiques promettent de
reproduire ces capacités au niveau de la machine. On commence
cependant à reconnaître combien la tâche est difficile. La plupart des
scientifiques conviennent que tout système biologique complexe
présentant ces qualités est le produit d’une évolution.
Théorie de
l’évolution
D’après ce qu’en dit la théorie, l’évolution a produit des systèmes
dotés d’étonnantes capacités par le biais de blocs de construction
relativement simples autorépliqués selon quelques règles
élémentaires :
1) L’évolution a lieu au niveau du chromosome. L’organisme n’évolue
pas. Il ne sert que de véhicule au transport et au transfert des gènes.
Ce sont les chromosomes qui changent dynamiquement à chaque
réorganisation des gènes.
2) La nature tend a reproduire davantage les chromosomes qui
produisent un organisme plus « apte ». Si un organisme survit
suffisamment longtemps et qu’il est sain, ses gènes sont plus
susceptibles d’être transmis à une nouvelle génération d’organismes,
par la reproduction. Ce principe est souvent désigné sous l’expression
de « survie du plus apte ». N’oublions pas que « le plus apte » est une
expression relative : un organisme ne doit être pertinent que par
rapport aux autres de la population courante pour « réussir ».
Chapitre 7 : Algorithmes génétiques
167
3) La diversité doit être maintenue dans la population. Des mutations
apparemment aléatoires se produisent fréquemment dans la nature
pour assurer la variation des organismes. Ces mutations génétiques
donnent souvent lieu à un trait utile, et parfois même essentiel à la
survie de l’espèce. Dotée d’un plus large spectre de combinaisons
possibles, une population est aussi moins vulnérable à une faiblesse
commune qui risquerait de la détruire (virus, etc.) ou aux problèmes
d’endogamie.
Lorsqu’on décompose l’évolution en ses blocs élémentaires, il est plus
facile d’appliquer ces techniques au monde de l’informatique et de
progresser véritablement vers des machines plus fluides au
comportement plus naturel.
Holland s’est ainsi mis à appliquer ces propriétés de l’évolution à de
simples chaînes de valeurs numériques représentant les
chromosomes. Commençant par encoder son problème en chaînes
binaires (lignes de chiffres « 1 » et « 0 ») chromosomiques, il a ensuite
demandé à l’ordinateur de générer un grand nombre de ces chaînes
de « bits » pour en former une vaste population. Une fonction de
pertinence lui a permis d’évaluer et de classer chaque chaîne de bits.
Celles jugées les plus « aptes » ont échangé leurs données avec
d’autres à travers une routine de « croisement » pour créer des
chaînes de bits « descendantes ». Holland a même soumis ses
chromosomes numériques à un opérateur de « mutation » chargé
d’injecter un certain caractère aléatoire dans les chromosomes
« descendants » résultants, afin de conserver la diversité de la
population. Cette fonction de pertinence a remplacé le rôle de la mort
dans le monde biologique, en déterminant les chaînes suffisamment
fortes pour continuer à se reproduire et celles à éliminer de la
mémoire.
« Gène »
168
« Chromosome » descendant
Histoire
Le programme a gardé un nombre donné de ces « chromosomes » en
mémoire, et cette « population » complète de chaînes a continué à
évoluer jusqu’à maximisation de la fonction de pertinence. Le résultat
a ensuite été décodé et réexprimé dans ses valeurs originales pour
révéler la solution. John Holland demeure un pionnier actif dans son
domaine. Des centaines de scientifiques et autres experts l’ont rejoint
et consacrent la plus grande partie de leur temps à ce remplacement
prometteur des techniques linéaires, mathématiques et statistiques
conventionnelles.
L’algorithme génétique original de John Holland était plutôt simple,
mais remarquablement solide et apte à trouver les solutions optimales
à une grande variété de problèmes. Bien des programmes
personnalisés résolvent aujourd’hui des problèmes réels
particulièrement complexes et imposants à l’aide de versions
légèrement modifiées seulement de ce premier algorithme génétique.
Adaptations
modernes des
algorithmes
génétiques
L’intérêt a grandi dans les milieux académiques et, tandis que la
puissance informatique commençait à s’introduire dans les
ordinateurs de bureau grand public, les normes telles que Microsoft
Windows et Excel n’ont pas tardé à faciliter la conception et la
maintenance de modèles complexes. L’usage de nombres réels plutôt
que de représentations de chaînes binaires a éliminé la tâche difficile
de l’encodage et du décodage des chromosomes.
Le succès de l’algorithme génétique est aujourd’hui exponentiel,
séminaires, guides, articles de magazine et conseils d’experts à
l’appui. L’International Conference of Genetic Algorithms se
concentre d’ores et déjà sur les applications pratiques, signe de
maturité qui échappe aux autres technologies de l’« intelligence
artificielle ». Les plus grandes entreprises recourent régulièrement
aux algorithmes génétiques pour résoudre leurs problèmes, des
sociétés de courtage aux centrales électriques, en passant par les
compagnies de téléphone, les chaînes de restauration, les
constructeurs automobiles et les réseaux de télévision. Il y a en fait de
fortes chances que vous ayez vous-même déjà utilisé, indirectement,
un algorithme génétique.
Chapitre 7 : Algorithmes génétiques
169
170
Histoire
Exemple biologique
Considérons un simple exemple d’évolution (à faible échelle) dans le
monde biologique. Par « évolution », on entend ici tout changement
de la distribution ou fréquence de gènes dans une population. Bien
sûr, l’aspect intéressant de l’évolution est qu’elle tend à donner lieu à
des populations en adaptation permanente à leur environnement.
Supposons donc que nous examinions une population de souris. Ces
souris présentent deux tailles, petite et grande, et deux couleurs, gris
clair et gris foncé. Notre population se compose des huit souris
suivantes :
Un jour, des chats arrivent dans les environs et se mettent à manger
les souris. Il se révèle que les chats ont plus de difficulté à trouver les
souris plus petites et plus foncées. Ainsi, différentes souris ont
différentes chances d’éviter les chats pendant une période
suffisamment longue pour pouvoir se reproduire. La nature de la
génération suivante de souris en est affectée. Si l’on suppose que les
vieilles souris meurent peu après s’être reproduites, la nouvelle
génération peut se présenter comme suit :
Remarquez que les grandes souris, celles de couleur claire et, tout
particulièrement, les grandes souris gris clair ont du mal à survivre
suffisamment longtemps pour se reproduire. La tendance se poursuit
à la génération suivante.
Chapitre 7 : Algorithmes génétiques
171
La population se compose désormais principalement de petites souris
de couleur plus foncée, plus aptes à survivre dans cet environnement
que les autres types. De même, tandis que les chats deviennent
affamés par manque de souris, peut-être ceux qui préfèrent l’herbe
seront-ils mieux adaptés et transmettront-ils leur gène herbivore à une
nouvelle génération de chats. Tel est le principe fondamental de la
« survie du plus apte ». Plus précisément, on pourrait parler de
« survie jusqu’à la reproduction ». En termes d’évolution, être le
célibataire en meilleure santé d’une population est sans intérêt,
puisqu’il faut qu’un être se reproduise pour que ses gènes influencent
les générations futures.
172
Exemple biologique
Exemple numérique
Imaginons un problème à deux variables, X et Y, produisant un
résultat, Z. Le calcul et le tracé du résultat Z pour chaque valeur X et
Y possible produirait un « paysage », comme nous l’avons déjà décrit
au chapitre 6 : Optimisation. Si nous cherchons à identifier le « Z »
maximum, les sommets de la fonction représentent de « bonnes »
solutions et les creux, de « mauvaises » solutions.
Lors de l’utilisation d’un algorithme génétique visant à maximiser la
fonction, on commence par créer aléatoirement plusieurs solutions ou
scénarios possibles (les points noirs), plutôt que de ne choisir qu’un
point de départ. On calcule ensuite la sortie de la fonction pour
chaque scénario et on marque chaque scénario d’un point noir. On
classe ensuite tous les scénarios en fonction de leur hauteur, du
meilleur au pire. On garde les scénarios de la moitié supérieure et on
élimine les autres.
On commence par créer une « population »
complète des solutions possibles. Certaines
seront meilleures (plus hautes) que d’autres.
Chapitre 7 : Algorithmes génétiques
On classe ensuite tous les points obtenus
et on ne garde que les solutions qui
présentent de meilleurs résultats.
173
Chacun des trois scénarios restants se redouble, pour ramener le
nombre total à six. La partie intéressante de l’opération se produit ici :
Chacun des six scénarios se compose de deux valeurs ajustables
(tracées sous forme de coordonnées X et Y). Les scénarios s’associent
aléatoirement en paires. Chaque scénario échange maintenant la
première de ses deux valeurs ajustables avec la valeur correspondante
de son partenaire. Par exemple :
Scénario 1
Scénario 2
Avant
Après
3,4, 5,0
2,6, 5,0
2,6, 3,2
3,4, 3,2
Cette opération porte le nom de croisement. Après accouplement
aléatoire et croisement de nos six scénarios, on peut obtenir un nouvel
ensemble de scénarios tel que celui-ci :
Dans l’exemple ci-dessus, on suppose que les trois scénarios originaux
– a, b et c – se sont associés avec les doubles A, B et C pour former les
paires aB, bC et cA. Ces paires ont ensuite échangé la valeur de leur
première cellule ajustable – ce qui revient, dans notre diagramme, à
échanger les coordonnées x et y entre les paires de points. La
population de scénarios a ainsi vécu une génération, avec son cycle de
« mort » et de « naissance ».
174
Exemple numérique
Remarquez que certains des nouveaux scénarios produisent une
sortie inférieure (hauteur moindre) à celle de la génération d’origine.
Signe de progrès, un scénario a cependant progressé sur la colline la
plus élevée. Si nous laissons la population évoluer pendant une
génération encore, on obtiendra peut-être un paysage semblable à
celui-ci :
Il est clair que la performance moyenne de la population de scénarios
s’est améliorée par rapport à la dernière génération. Dans cet
exemple, il ne reste plus guère de place à l’amélioration. La raison en
est qu’il n’y a que deux gènes par organisme, six organismes
seulement et aucune possibilité de création de nouveaux gènes. En
d’autres termes, le capital génétique est limité. Le capital génétique
représente la somme de tous les gènes de tous les organismes de la
population.
Les algorithmes génétiques peuvent être rendus beaucoup plus
puissants par réplication accrue de la force inhérente de l’évolution
dans le monde biologique : en accroissant le nombre de gènes par
organisme, en accroissant le nombre d’organismes d’une population
et en admettant des mutations aléatoires occasionnelles. On peut de
plus choisir les scénarios appelés à survivre et à se reproduire de
manière plus proche de la réalité naturelle : avec un élément aléatoire
favorisant légèrement les meilleures performances, plutôt que de ne
retenir que les meilleures performances à la reproduction (même le
plus grand et le plus fort des lions peut être frappé par la foudre !)
Toutes ces techniques stimulent le raffinement génétique et
contribuent au maintien de la diversité du capital génétique, en
préservant toutes sortes de gènes au cas où ils s’avéreraient utiles
dans d’autres combinaisons. Evolver applique automatiquement
toutes ces techniques.
Chapitre 7 : Algorithmes génétiques
175
176
Exemple numérique
Chapitre 8 : Et aussi…
Ajout de contraintes .......................................................................179
Contraintes plages................................................................................180
Contraintes fermes – personnalisées ................................................181
Contraintes souples .............................................................................182
Fonctions de pénalité .............................................................182
Entrée d’une fonction de pénalité .......................................183
Visualisation des effets d’une
fonction de pénalité entrée ...................................................184
Visualisation des pénalités appliquées..............................184
Entrée de contraintes souples dans la
feuille de calcul .......................................................................185
Autres exemples de fonctions de pénalité .........................185
Utilisation des fonctions de pénalité ..................................186
Problèmes à buts multiples................................................................187
Accélération du processus............................................................189
Mode d’exécution de l’optimisation Evolver................................191
Sélection ...................................................................................191
Croisement...............................................................................192
Mutation...................................................................................193
Remplacement.........................................................................193
Contraintes...............................................................................193
Chapitre 8 : Et aussi…
177
178
Ajout de contraintes
Les problèmes réalistes présentent souvent des contraintes à respecter
dans la recherche de solutions optimales. Ainsi, dans l’exemple du
didacticiel relatif à la recherche de conception du transformateur le
moins onéreux, l’une des contraintes est que le transformateur doit
rester froid et ne doit pas émettre plus de 0,16 watts/cm².
Un scénario qui satisfait à toutes les contraintes d’un modèle est
qualifié de solution viable ou « valable ». Il est parfois difficile de
trouver de solutions viables pour un modèle, et encore plus de
solution optimale viable : dans les cas, notamment, où le problème est
particulièrement complexe et où il n’existe que quelques solutions
viables, ou dans ceux où le problème est spécifié à outrance (trop de
contraintes, ou contraintes en conflit les unes avec les autres) et où il
n’existe donc aucune solution viable.
Il existe trois grands types de contraintes : les contraintes plages, ou
plages min‐max imposées aux cellules ajustables, les contraintes
fermes, dont le respect est obligatoire, et les contraintes souples que
l’on désire respecter autant que possible mais pour lesquelles on est
prêt à accepter le compromis en vue d’une importante amélioration
de pertinence.
Chapitre 8 : Et aussi…
179
Contraintes plages
Les contraintes fermes les plus simples sont celles imposées aux
variables elles-mêmes. En fixant une certaine plage pour chaque
variable, on limite le nombre global de solutions possibles, au
bénéfice d’une recherche plus efficace. Les valeurs Min et Max se
définissent dans le volet Plages de cellules ajustables de la fenêtre
Modèle. Elles indiquent à Evolver la plage de valeurs acceptables
pour chaque variable.
Evolver n’essaie que les valeurs comprises entre 0 et 5 000 pour les cellules spécifiées.
Un second type de contrainte ferme imposée aux variables est intégré
dans chacune des méthodes de résolution d’Evolver (recette, ordre,
groupement, etc.) Par exemple, si l’on ajuste les variables selon la
méthode de résolution budget, Evolver est soumis à la contrainte
ferme de n’essayer que les ensembles de valeurs dont le total
représente une même somme. À l’image du paramètre de plage, cette
contrainte ferme réduit le nombre de scénarios possibles à soumettre
à la recherche.
L’option entières de la boîte de dialogue Modèle représente aussi une
contrainte ferme, en ce qu’elle limite les essais d’Evolver aux seules
valeurs entières (1, 2, 3, etc.), à l’exclusion des nombres réels (1,34,
2,034, etc.) lors de l’ajustement des valeurs de variable.
180
Ajout de contraintes
Contraintes fermes – personnalisées
Les contraintes extérieures aux contraintes de variables Evolver se
définissent dans la boîte de dialogue Paramètres de contrainte.
REMARQUE : Comme l’évolution dans la nature, la puissance de
résolution d’un algorithme génétique tient principalement à sa
capacité d’exploration libre de nombreuses combinaisons de solutions
vraisemblables, avec prédilection naturelle à l’égard des meilleures.
Interdire à Evolver ne fût-ce que de regarder les solutions non
conformes à nos exigences, c’est handicaper, potentiellement, le
processus d’optimisation de l’algorithme génétique.
Il est toujours plus simple pour Evolver de trouver des solutions
conformes aux contraintes fermes si le scénario initial de la feuille de
calcul satisfait lui-même à ces contraintes. Evolver dispose ainsi d’un
point de départ dans l’espace des solutions valables. En l’absence de
scénario conforme aux contraintes, Evolver devra être exécuté au
départ d’un scénario initial quelconque et il fera de son mieux pour
identifier ceux qui satisfont aux contraintes.
Chapitre 8 : Et aussi…
181
Contraintes souples
Forcer un programme à ne rechercher que les solutions conformes à
toutes les contraintes peut aboutir à l’absence de solutions viables. Il
est souvent plus utile de disposer d’une solution approximativement
viable, ou les contraintes ne sont pas nécessairement toutes satisfaites
à la perfection.
Plutôt que d’imposer des « contraintes fermes » dont le respect doit
être assuré, la configuration de « contraintes souples » définit les
contraintes quʹEvolver s’efforcera de satisfaire. Les contraintes
souples sont plus réalistes et elles permettent à Evolver d’essayer
beaucoup plus d’options. Dans le cas d’un problème soumis à de
nombreuses contraintes (où il n’existe pas beaucoup de solutions
possibles qui satisferaient à toutes les exigences), l’algorithme
génétique d’Evolver est beaucoup plus susceptible de trouver la
meilleure solution possible s’il lui est possible d’évaluer les solutions
presque conformes aux contraintes.
Quand les contraintes concernent des buts conceptuels, tels que
« produire deux fois plus de fourchettes que de couteaux », il est
rarement important d’y satisfaire en toute précision : surtout si
l’obtention d’un programme de production parfaitement équilibré
imposerait un processus d’optimisation exigeant toute une journée !
En l’occurrence, une bonne solution au problème, presque conforme à
la contrainte (40 % de fourchettes, 23 % de couteaux et 37 % de
cuillers, par exemple), serait plus acceptable que le gaspillage de toute
une journée pour arriver, peut‐être, à la conclusion qu’il n’y a pas de
solution parce qu’il est impossible de satisfaire à toutes les contraintes.
Fonctions de
pénalité
182
Les fonctions de pénalité facilitent la mise en œuvre de contraintes
souples dans Excel. Plutôt que d’interdire strictement à Evolver la
considération de certaines valeurs dans la recherche de solutions, on
permet l’exploration de ces valeurs « incorrectes » mais on pénalise en
conséquence les solutions qu’elles produisent. Par exemple, un
problème peut impliquer la recherche du moyen de distribution de
biens le plus efficace, compte tenu du fait qu’on ne dispose que de
trois camions. Un modèle plus précis inclurait une fonction de
pénalité qui reconnaîtrait un plus grand nombre de camions mais qui
augmenterait substantiellement le coût du résultat. Les fonctions de
pénalité se définissent dans la boîte de dialogue Paramètres de
contrainte, ou directement dans le modèle moyennant l’ajout de
formules qui les représentent.
Ajout de contraintes
Entrée d’une
fonction de
pénalité
Evolver propose une fonction de pénalité par défaut, affichée dès les
premières étapes de définition d’une contrainte souple. Une formule
Excel valable quelconque peut cependant être utilisée pour calculer
l’importance de la pénalité à appliquer lorsque la contrainte souple
n’est pas satisfaite. Une fonction de pénalité ainsi entrée doit inclure le
mot-clé écart, pour représenter le dépassement absolu de la limite de
la contrainte. Au terme d’une simulation de solution itérative, Evolver
vérifie si la contrainte souple a été respectée. Si non, la valeur de
l’écart est introduite dans la formule de pénalité pour calculer la
pénalité à appliquer à la statistique de simulation de la cellule cible
minimisée ou maximisée.
La pénalité s’ajoute à la statistique calculée pour la cellule cible ou
s’en soustrait, de manière à la rendre moins « optimale ». Ainsi, si
Maximum est sélectionné dans le champ But d’optimisation de la boîte
de dialogue Modèle d’Evolver, la pénalité est déduite de la statistique
calculée pour la cellule cible.
Chapitre 8 : Et aussi…
183
Visualisation des
effets d’une
fonction de
pénalité entrée
Evolver s’accompagne d’une feuille de calcul Excel intitulée
Penalité.xls, utile à l’évaluation des effets de différentes fonctions de
pénalité sur les contraintes souples et les résultats de cellule cible.
Cette feuille de calcul permet la sélection, dans un modèle, d’une
contrainte souple dont on désire analyser les effets. On peut ensuite
changer la fonction de pénalité pour voir comment elle mappera une
valeur spécifique pour la contrainte souple non satisfaite dans une
statistique pénalisée particulière de la cellule cible. Par exemple, si la
contrainte souple est A10<100, on pourrait consulter Penalité.xls pour
voir ce que serait la valeur cible si une valeur de 105 était calculée
pour la cellule A10.
Visualisation des
pénalités
appliquées
184
Lorsqu’une pénalité est appliquée à la cellule cible sous l’effet d’une
contrainte souple non satisfaite, Suivi Evolver permet de visualiser
l’importance de cette pénalité. Les valeurs des pénalités figurent aussi
dans le Journal d’optimisation créé, facultativement, après
l’optimisation.
Ajout de contraintes
Entrée de
contraintes
souples dans la
feuille de calcul
Les fonctions de pénalité peuvent aussi être introduites directement
dans la feuille de calcul. Une fonction de pénalité booléenne affecte
une pénalité définie à tout scénario non conforme à la contrainte
spécifiée. Par exemple, si la valeur de la cellule B1 (offre) doit être au
moins égale à celle de la cellule A1 (demande), on pourrait définir
cette fonction de pénalité dans une autre cellule : =SI(A1>B1; ‐1000; 0).
Si le résultat de cette cellule était ajouté à la statistique de la cellule
cible, chaque fois qu’Evolver produirait une solution non conforme à
la contrainte (offre non conforme à la demande), la statistique de la
cellule cible maximisée serait réduite d’une valeur de 1 000 par
rapport au résultat réel. Toute solution contraire à la contrainte
produirait une valeur inférieure pour la statistique de la cellule cible,
au point qu’Evolver finirait par éliminer naturellement ces
organismes.
Un autre type de fonction, à échelle de pénalité, pénalise plus
exactement la solution en fonction de son degré de non conformité
par rapport à la contrainte. Cette fonction convient généralement
mieux à la réalité des choses, car une solution où l’offre ne répond pas
tout à fait à la demande vaudrait mieux qu’une solution où elle y
serait vraiment très inférieure. Une simple fonction d’échelle de
pénalité calcule la différence absolue entre la valeur cible de la
contrainte et sa valeur réelle. Par exemple, dans ce même exemple où
A1 (la demande) ne doit pas dépasser B1 (l’offre), on pourrait
appliquer la fonction de pénalité suivante : =SI(A1>B1, (A1-B1)^2, 0).
Ce type de fonction de pénalité mesure la proximité de satisfaction
d’une contrainte et exagère la différence en l’élevant au carré. La
pénalité varie ainsi en fonction de la gravité de la violation de la
contrainte.
Autres exemples
de fonctions de
pénalité
Chapitre 8 : Et aussi…
Supposons par exemple un modèle de production où l’une des
contraintes est que la quantité de bois utilisée doit être égale à celle de
plastique. Cette contrainte est satisfaite lorsque « QtéBois » =
« QtéPlastique ». Pour rechercher les solutions qui incluent une même
quantité des deux matériaux, on crée une fonction de pénalité
défavorable aux solutions éloignées du but. La formule
« =ABS(QtéBois‐QtéPlastique) » calcule la différence absolue (non
négative) entre la quantité de bois et celle de plastique utilisée. La
fonction ABS() produit la même valeur de pénalité si QtéBois est
supérieure de 20 unités à QtéPlastique ou que QtéPlastique est
inférieure de 20 unités à QtéBois. Lors de l’optimisation du modèle, le
but est de minimiser la moyenne des résultats de simulation pour
cette différence absolue.
185
Supposons que nous imposions plutôt, comme contrainte, que la
quantité de bois doit être deux fois supérieure à celle de plastique. La
fonction de pénalité deviendrait alors :
=ABS(QtéBois-QtéPlastique*2)
Une autre contrainte possible serait que la quantité de bois doive être
au moins deux fois supérieure à celle de plastique. Là où l’exemple
précédent produisait une pénalité s’il y avait trop de bois, celui-ci ne
s’intéresse qu’à la quantité minimale de bois : si QtéBois est 10 fois
supérieure à QtéPlastique, aucune pénalité ne doit être appliquée. La
fonction de pénalité applicable s’exprimerait ainsi :
=SI(QtéBois<QtéPlastique*2; ABS(QtéPlastique*2QtéBois);0)
Si QtéBois est au moins deux fois supérieure à QtéPlastique, la
fonction de pénalité renvoie 0. Sinon, elle indique de combien la
valeur QtéBois est inférieure à deux fois QtéPlastique.
Utilisation des
fonctions de
pénalité
Une fois définies, les fonctions de pénalité appelées à décrire les
contraintes souples du modèle peuvent être combinées à la formule
de cellule cible ordinaire pour obtenir une formule de cellule cible
sous contrainte. Dans l’exemple illustré ci-dessous, si la cellule C8
calcule le coût total d’un projet et les cellules E3:E6 contiennent cinq
fonctions de pénalité, on peut introduire dans la cellule C10 une
formule telle que =SOMME(C8; E3:E6).
On crée une cellule qui ajoute les contraintes au total et on minimise la moyenne des
résultats de la simulation pour cette cellule.
186
Ajout de contraintes
On ajoute ainsi les pénalités de la colonne E au coût de C8 pour
obtenir une fonction de coût sous contrainte ou pénalité dans C10.
Remarquez que s’il s’agissait d’un problème de maximisation, on
soustrairait, plutôt que d’additionner, les pénalités de la cellule cible
originale. Lors de l’utilisation d’Evolver, on sélectionne simplement
cette cellule sous contrainte, C10, comme cellule cible dont la
statistique de simulation doit être optimisée.
Quand Evolver essaie d’optimiser une statistique sous contrainte pour
la cellule cible, les fonctions de pénalité tendent à forcer la recherche
vers les scénarios conformes aux contraintes. Evolver finit ainsi par
produire des solutions qui apportent de bonnes solutions au
problème et qui satisfont ou presque à toutes les contraintes (valeurs
de pénalité proches de 0).
Problèmes à buts multiples
Le champ de cellule cible d’Evolver n’admet qu’une cellule. Il n’en est
pas moins possible de résoudre le problème pour plusieurs en créant
une formule qui combine deux buts en un. Considérons, par exemple,
un expert en polymère à la recherche d’une matière à la fois souple et
robuste. Son modèle calcule la résistance, la souplesse et le poids qui
résulteraient d’une formule donnée de combinaisons chimiques. Les
quantités de chaque ingrédient sont les variables ajustables du
problème.
Comme on cherche à maximiser la robustesse de la matière (cellule
S3) mais aussi sa souplesse (cellule F3), on peut définir dans une
nouvelle cellule la formule =(S3+F3). Cette cellule devient la nouvelle
cellule cible. Plus sa valeur est élevée, plus la solution globale est
bonne.
Si la souplesse est plus importante que la robustesse, la formule de la
cellule cible pourrait devenir =(S3+(F3*2)). De cette façon, les scénarios
qui accroissent la souplesse d’une certaine valeur seront mieux vus
(meilleure « cote » de pertinence) que ceux qui augmentent la
robustesse de la même valeur.
Pour maximiser la robustesse d’une matière (cellule S5) tout en
minimisant son poids (cellule W5), on créerait une nouvelle cellule
dotée de la formule suivante : =(S5^2)-(W5^2). Cette formule
produirait une valeur supérieure pour les structures à la fois robustes
et légères, moindre pour les structures faibles et lourdes et également
moyenne pour les scénarios de structures faibles mais légères ou
robustes mais lourdes. Cette nouvelle cellule servirait de cible, avec
maximisation de la moyenne pour satisfaire les deux objectifs.
Chapitre 8 : Et aussi…
187
188
Ajout de contraintes
Accélération du processus
L’utilisation d’Evolver pour la résolution d’un problème fait appel, à
la fois, à la bibliothèque Evolver de routines compilées pour gérer le
processus et à la fonction d’évaluation de feuille de calcul d’Excel
pour examiner les différents scénarios. Une grande partie du temps
consacré à l’opération tient en fait au recalcul de la feuille par Excel.
Différentes approches permettent d’accélérer le processus
d’optimisation Evolver et celui du recalcul d’Excel.
Chapitre 8 : Et aussi…
♦
La vitesse d’Evolver est directement liée à celle du processeur de
l’ordinateur. Ainsi, un Pentium/2 GHz est environ deux fois plus
rapide qu’un Pentium/1 GHz. Autrement dit, Evolver peut
évaluer deux fois plus d’essais pendant une même période de
temps.
♦
Dès le moment où Evolver a plus ou moins convergé sur une
solution et que la meilleure solution n’est plus améliorée depuis
un certain temps (1 000 derniers essais, par exemple),
l’accroissement du taux de mutation peut permettre à Evolver
d’élargir sa recherche plutôt que de continuer à raffiner ses
solutions dans la population actuelle à l’aide, principalement, du
croisement. L’utilitaire Suivi Evolver permet d’accroître ce taux
de mutation, à travers la commande Paramètres de population.
♦
Les plages de cellules ajustables plus étroites réduisent la zone de
recherche d’Evolver et peuvent par conséquent accélérer le
processus. On veillera cependant à prévoir suffisamment d’espace
pour assurer l’exploration de toutes les solutions réalistes.
189
190
Accélération du processus
Mode d’exécution de l’optimisation Evolver
Cette section décrit plus spécifiquement la manière dont les
algorithmes d’optimisation d’Evolver s’exécutent.
REMARQUE : Il n’est pas nécessaire de maîtriser cette information
pour utiliser Evolver.
La technologie des algorithmes génétiques d’Evolver (méthodes de
résolution recette et ordre, etc.) repose pour la plupart sur les travaux
académiques réalisés ces 10 dernières années dans le domaine des
algorithmes génétiques. La plupart des méthodes de résolution
descendantes incluses dans Evolver et les fonctionnalités de groupes
multiples de cellules ajustables, de recul, de stratégie et de probabilité
sont toutefois uniques à Evolver.
Evolver repose sur une approche de régime permanent. Cela veut dire
qu’un seul organisme est remplacé à la fois, plutôt que toute une
« génération ». Cette technique s’est avérée équivalente ou même
supérieure à la méthode de remplacement générationnel. Pour
déterminer le nombre équivalent de « générations » exécutées par
Evolver, il suffit de diviser le nombre d’essais individuels explorés
par la taille de la population.
Sélection
Lorsqu’un nouvel organisme doit être créé, deux parents sont choisis
dans la population actuelle. Les organismes dont les cotes de
pertinence sont plus élevées ont plus de chances d’être choisies
comme parents.
Dans Evolver, le choix des parents s’effectue selon un mécanisme de
rang. Contrairement à certains systèmes d’algorithmes génétiques, où
la probabilité qu’un parent soit sélectionné à la reproduction est
directement proportionnelle à sa pertinence, l’approche par rang
présente une courbe de probabilité de sélection plus lisse. On évite
ainsi que les bons organismes ne dominent complètement l’évolution
dès le début du processus.
Chapitre 8 : Et aussi…
191
Croisement
Comme chaque méthode de résolution ajuste les variables de
différentes manières, Evolver applique une routine de croisement
différente optimisée selon le type de problème considéré.
La méthode recette fondamentale exécute le croisement selon une
routine de croisement uniforme : plutôt que de couper la liste de
variables en un scénario donné à un certain point et de traiter chacun
des deux blocs ainsi formés (croisement à « un point » ou « double
point »), deux groupes sont formés par sélection aléatoire d’éléments .
Les croisements conventionnels à x points risquent d’influencer la
recherche en raison de la position étrangère des variables, alors que la
méthode de croisement uniforme préserve vraisemblablement mieux
le schéma et peut produire n’importe quel schéma au départ des deux
parents.
population originale
croisement ponctuel unique – En cas de croisement, un point est
sélectionné aléatoirement et l’organisme se coupe en deux.
croisement uniforme – Un % donné de l’organisme est
sélectionné aléatoirement.
La méthode de résolution ordre effectue le croisement selon un
algorithme similaire à l’opérateur décrit dans le guide Handbook of
Genetic Algorithms de L. Davisfn : elle sélectionne aléatoirement les
éléments d’un parent, trouve leur place dans l’autre parent et copie
les éléments restants dans le second parent, dans le même ordre que
celui dans lequel ils figuraient dans le premier. On préserve ainsi une
partie des sous-ordres des parents originaux tout en en créant
quelques nouveaux.
192
Mode d’exécution de l’optimisation Evolver
Mutation
À l’image du croisement, les méthodes de mutation sont adaptées à
chacune des méthodes de résolution. La méthode recette
fondamentale exécute la mutation par considération individuelle de
chaque variable. Un nombre aléatoire compris entre 0 et 1 est généré
pour chacune des variables de l’organisme et, si une variable reçoit un
nombre inférieur ou égal au taux de mutation (0,06, par exemple), elle
est mutée. Un algorithme exclusif détermine automatiquement
l’importance et la nature de la mutation. La mutation d’une variable
implique son remplacement par une valeur aléatoire (comprise dans
la plage min-max applicable).
Pour préserver toutes les valeurs originales, la méthode de résolution
ordre effectue la mutation par permutation des positions de certaines
variables dans l’organisme. Le nombre de permutations augmente ou
diminue proportionnellement à l’accroissement ou à la réduction du
taux de mutation (de 0 à 1).
Remplacement
Comme Evolver applique une méthode de remplacement par rang
plutôt que de remplacement générationnel, les organismes les moins
performants sont toujours remplacés par le nouvel organisme créé par
sélection, croisement et mutation, indépendamment de sa « cote » de
pertinence.
Contraintes
Les contraintes fermes sont exécutées selon la technologie de « recul »
exclusive de Palisade. Si un nouveau descendant est contraire à
certaines contraintes imposées de l’extérieur, Evolver revient à l’un
des parents et change l’enfant jusqu’à ce qu’il soit conforme à l’espace
de solution admis.
croisement
recul
organismes valables (solutions)
organisme « descendant » non valable
Chapitre 8 : Et aussi…
193
194
Mode d’exécution de l’optimisation Evolver
Annexe A : Automatisation
d’Evolver
Evolver est assorti d’un langage macro intégral qui permet
l’élaboration d’applications personnalisées tirant parti de ses
capacités. Les fonctions personnalisées d’Evolver sont exploitables en
VBA pour la configuration et l’exécution d’optimisations et l’affichage
de leurs résultats. Pour plus de détails sur cette interface de
programmation, voir le document d’aide Kit du développeur Evolver,
accessible depuis le menu d’aide d’Evolver.
Annexe A : Automatisation d’Evolver
195
196
Annexe B : Dépannage /
Questions-Réponses
Dépannage / Questions-Réponses
Vous trouverez dans cette section la réponse aux questions souvent
posées au sujet d’Evolver. Après l’avoir consultée, si vous n’y trouvez
pas la question, le problème ou la suggestion appropriée, prenez
contact avec le service d’assistance Palisade à l’un des numéros
indiqués au premier chapitre de ce manuel.
Q : Pourquoi m’est-il difficile d’obtenir une réponse valable
d’Evolver ?
R : Vérifiez que votre boîte de dialogue Evolver est bien configurée.
La plupart des problèmes rencontrés tiennent à la définition des
variables. Chaque groupe de cellules ajustables doit être exclusif :
aucune cellule ou plage de cellules ne peut être traitée sous plus
d’une méthode de résolution.
Q : Evolver peut-il gérer des concepts ou des catégories plutôt que
de simples valeurs numériques ?
R : Evolver gère, indirectement, toutes les formes de données : les
nombres n’en sont que les symboles. Employez une table de
recherche dans Excel pour traduire vos entiers en chaînes de texte
et vice-versa. Evolver (comme tous les autres programmes
informatiques) ne traite, en soi, que des valeurs numériques, mais
votre interface peut utiliser ces valeurs pour représenter et
afficher n’importe quelles chaînes.
Annexe B : Dépannage / Questions-Réponses
197
Q : Alors que je configure mes boîtes de dialogue de la même
manière et que je laisse Evolver tourner pendant la même durée,
j’obtiens parfois des solutions différentes. Pourquoi ?
R : Comme dans la sélection naturelle du monde biologique,
l’algorithme génétique d’Evolver ne suit pas toujours la même
voie lors de la recherche de solutions (à moins que vous n’utilisiez
une racine de nombres aléatoires fixe). Ironiquement, c’est cette
« imprévisibilité » qui permet à Evolver de résoudre plus de types
de problèmes et, souvent, de produire de meilleures solutions que
les techniques conventionnelles. Le moteur d’algorithmes
génétiques d’Evolver ne se limite pas à exécuter une série de
commandes préprogrammées, ou à insérer des valeurs dans une
formule mathématique. Il essaie efficacement de nombreux
scénarios hypothétiques aléatoires simultanés, pour raffiner
ensuite la recherche au moyen de nombreux opérateurs de
« survie du plus apte » également porteur d’éléments aléatoires.
Q : Pourquoi la meilleure solution trouvée ne change-t-elle pas ?
R : Vous avez peut-être spécifié une mauvaise cellule cible dans la
boîte de dialogue Modèle d’Evolver. Evolver considère cette
cellule vierge et la valeur ne change pas, faute de formule. Pour
remédier à ce problème, ouvrez la boîte de dialogue Modèle
d’Evolver et sélectionnez une cellule cible appropriée, qui reflète
adéquatement la qualité ou non de chaque solution possible. Une
cellule cible appropriée contient une formule qui dépend
(directement ou indirectement) des variables qu’Evolver ajuste
(les cellules ajustables).
Q : Certaines cellules de mon modèle de feuille de calcul
contiennent les symboles « #### ».
R : Si la cellule est trop petite pour afficher son contenu intégral, elle
affiche plusieurs signes ####. Augmentez la taille de la cellule.
198
Dépannage / Questions-Réponses
Q : Evolver fonctionne bien mais n’existe-t-il pas de moyen simple
d’obtenir de meilleurs résultats ?
R : Pouvez-vous assouplir les contraintes de votre problème, y
compris les plages de variables ? Remplacez certaines de vos
contraintes fermes par des contraintes souples, avec fonctions de
pénalité (voir Ajout de contraintes au Chapitre 8 : Et aussi…) Trop
de restrictions à la liberté d’Evolver peuvent l’empêcher
d’explorer certains espaces de possibilités susceptibles de
produire de meilleurs résultats. N’oubliez pas que plus Evolver
explore de possibilités, plus il aura de chances de trouver la
solution optimale. Pour d’autres idées sur la manière d’affiner
Evolver, voir le Chapitre 8 : Et aussi...
Plus Evolver peut examiner de scénarios, plus il est apte à
produire de bons résultats. Pour accélérer le traitement,
désactivez l’option d’actualisation de l’affichage « à chaque
recalcul ».
Annexe B : Dépannage / Questions-Réponses
199
Annexe B : Dépannage / Questions-Réponses
200
Annexe C : Ressources
complémentaires
Ressources complémentaires
La liste présentée ci-dessous propose une sélection de documentation
relative aux algorithmes génétiques et à la vie artificielle [en anglais].
L’astérisque (*) identifie les ouvrages préférés de Palisade.
Livres
• Bolles, R.C., & Beecher, M.D. (Eds.). (1988). Evolution and Learning.
Lawrence Erlbaum.
• Beer, R.D. (1990). Intelligence as Adaptive Behavior: An Experiment in
Computational Neuroethology. Academic Press.
• Davis, Lawrence (1987). Genetic Algorithms and Simulated Annealing. Palo
Alto, CA: Morgan Kaufman.
* Davis, Lawrence (1991). Handbook of Genetic Algorithms. New York: Van
Nostrand Reinhold.
• Darwin, Charles (1985). On The Origin of Species. London: Penguin Classics.
(Publication originale en 1859)
* Dawkins, Richard. (1976). The Selfish Gene. Oxford University Press.
• Eldredge, N. (1989). Macroevolutionary Dynamics: Species, Niches, and
Adaptive Peaks. McGraw-Hill.
• Fogel, L., Owens, J., and Walsh, J. (1966). Artificial Intelligence through
Simulated Evolution. New York: John Wiley and Sons.
• Goldberg, David (1989). Genetic Algorithms in Search, Optimization, and
Machine Learning. Reading, MA: Addison-Wesley Publishing.
• Holland, J.H. (1975). Adaptation in Natural and Artificial Systems. Ann
Arbor, MI: University of Michigan Press.
• Koza, John (1992). Genetic Programming. Cambridge, MA: MIT Press.
* Langton, C.L. (1989). Artificial Life. MIT Press. [ALife I]
• Levy, Steven (1992). Artificial Life. New York: Pantheon.
Annexe C : Ressources complémentaires
201
• Meyer, J.-A., & S.W. Wilson (Eds.). (1991). Proceedings of the First
International Conference on Simulation of Adaptive Behavior: From
Animals to Animats. MIT Press/Bradford Books.
* Proceedings of the Sixth International Conference (ICGA) on Genetic
Algorithms (1995). San Mateo, CA: Morgan Kaufman Publishing. (Also
available; the first five ICGA proceedings).
• Proceedings of the Workshop on Artificial Life (1990). Christopher G.
Langton, Senior Editor. Reading, MA: Addison-Wesley Publishing.
• Rawlins, Gregory (1991). Foundations of Genetic Algorithms. San Mateo,
CA: Morgan Kaufman Publishing.
• Richards, R.J. (1987). Darwin and the Emergence of Evolutionary Theories of
Mind and Behavior. U. Chicago Press.
• Williams, G.C. (1966). Adaptation and Natural Selection. Princeton U. Press.
Articles
* Antonoff, Michael (October, 1991). Software by Natural Selection. Popular
Science, p. 70-74.
• Arifovic, Jasmina (January, 1994). Genetic Algorithm Learning and the
Cobweb Model. Dans Journal of Economic Dynamics & Control v18 p.3
* Begley, S (May 8, 1995). “Software au Naturel” Dans Newsweek p. 70
• Celko, Joe (April, 1993). Genetic Algorithms and Database Indexing. Dans
Dr. Dobb’s Journal p.30
• Ditlea, Steve (November, 1994). Imitation of Life. Dans Upside Magazine
p.48
• Gordon, Michael (June, 1991). User-based Document Clustering by
Redescribing Subject Descriptions with a Genetic Algorithm. Dans
Journal of the American Society for Information Science v42 p.311
• Hedberg, Sara (September, 1994). Emerging Genetic Algorithms. Dans AI
Expert, p. 25-29.
• Hinton, G.E., & Nowlan, S.J. (1987). How Learning Can Guide Evolution.
Dans Complex Systems 1: p.495-502.
* Kennedy, Scott (June, 1995). Genetic Algorithms: Digital Darwinism. Dans
Hitchhicker’s Guide to Artificial Intelligence Miller Freeman Publishers
• Kennedy, Scott (December, 1993). Five Ways to a Better GA. Dans AI Expert,
p. 35-38
• Lane, A (June, 1995). The GA Edge in Analyzing Data. Dans AI Expert p.11
• Lee, Y.C. (Ed.). (1988). Evolution, learning, and cognition. Dans World
Scientific.
202
Ressources complémentaires
• Levitin, G and Rubinovitz, J (August, 1993). Genetic Algorithm for Linear
and Cyclic Assignment Problem. Dans Computers & Operations
Research v20 p.575
• Marler, P., & H.S. Terrace. (Eds.). (1984). The Biology of Learning. SpringerVerlag.
• Mendelsohn, L. (December, 1994) Evolver Review dans Technical Analysis
of Stocks and Commodities. p.33
• Maynard Smith, J. (1987). When Learning Guides Evolution. Dans Nature
329: p.761-762.
• Murray, Dan (June, 1994). Tuning Neural Networks with Genetic
Algorithms. Dans AI Expert p.27
• Wayner, Peter (January, 1991). Genetic Algorithms: Programming Takes a
Valuable Tip from Nature. Dans Byte Magazine v16 p.361
Magazines et bulletins d’information
• Advanced Technology for Developers (monthly newsletter). Jane
Klimasauskas, Ed., High-Tech Communications, 103 Buckskin Court,
Sewickley, PA 15143 (412) 741-7699
• AI Expert (monthly magazine). Larry O’Brien, Ed., 600 Harrison St., San
Francisco, CA 94107 (415) 905-2234. *Bien que AI Expert ne soit plus
publié depuis le printemps 1995, ses anciens numéros contiennent de
nombreux articles intéressants. Miller-Freeman, San Francisco.
• Applied Intelligent Systems (bimonthly newsletter). New Science
Associates, Inc. 167 Old Post Rd., Southport, CT 06490 (203) 259-1661
• Intelligence (monthly newsletter). Edward Rosenfeld, Ed., PO Box 20008,
New York, NY 10025-1510 (212) 222-1123
• PC AI Magazine (monthly magazine). Joseph Schmuller, Ed., 3310 West Bell
Rd., Suite 119, Phoenix, AZ 85023 (602) 971-1869
• Release 1.0 (monthly newsletter). Esther Dyson, Ed., 375 Park Avenue, New
York, NY 10152 (212) 758-3434
• Sixth Generation Systems (monthly newsletter). Derek Stubbs, Ed., PO Box
155, Vicksburg, MI, 49097 (616) 649-3592
Annexe C : Ressources complémentaires
203
Introduction à la simulation
Si vous découvrez la simulation ou que vous souhaitez approfondir
vos connaissances, les ouvrages et articles suivants peuvent se révéler
utiles :
* Baird, Bruce F. Managerial Decisions Under Uncertainty: John Wiley & Sons,
Inc. 1989.
* Clemen, Robert T. Making Hard Decisions: Duxbury Press, 1990.
• Hertz, D.B. "Risk Analysis in Capital Investment": HBR Classic, Harvard
Business Review, September/October 1979, pp. 169-182.
• Hertz, D.B. and Thomas, H. Risk Analysis and Its Applications: John Wiley
et Sons, New York, NY, 1983.
• Megill, R.E. (Editor). Evaluating and Managing Risk: PennWell Books,
Tulsa, OK, 1984.
• Megill, R.E. An Introduction to Risk Analysis, 2nd Ed.: PennWell Books,
Tulsa, OK, 1985.
• Morgan, M. Granger and Henrion, Max, with a chapter by Mitchell Small,
Uncertainty: Cambridge University Press, 1990.
• Newendorp, P.D. Decision Analysis for Petroleum Exploration: Petroleum
Publishing Company, Tulsa, Okla., 1975.
• Raiffa, H. Decision Analysis: Addison-Wesley, Reading, Mass., 1968.
204
Ressources complémentaires
Références techniques à la simulation et aux
techniques Monte Carlo
Si vous souhaitez approfondir vos connaissances en matière de
simulation, techniques d’échantillonnage et théorie statistique, les
ouvrages suivants peuvent se révéler utiles :
• Iman, R. L., Conover, W.J. "A Distribution-Free Approach To Inducing Rank
Correlation Among Input Variables": Commun. Statist.-Simula.
Computa.(1982) 11(3), 311-334
* Law, A.M. et Kelton, W.D. Simulation Modeling and Analysis: McGrawHill, New York, NY, 1991,1982.
Rubinstein, R.Y. Simulation and the Monte Carlo Method: John Wiley et Sons,
New York, NY, 1981.
Références techniques aux techniques
d’échantillonnage Hypercube latin
Si vous souhaitez obtenir des informations sur la technique
relativement nouvelle de l’échantillonnage Hypercube latin, les
sources suivantes peuvent se révéler utiles :
• Iman, R.L., Davenport, J.M., and Zeigler, D.K. "Latin Hypercube Sampling
(A Program Users Guide)": Technical Report SAND79-1473, Sandia
Laboratories, Albuquerque (1980).
• Iman, R.L. and Conover, W.J. "Risk Methodology for Geologic Displosal of
Radioactive Waste: A Distribution – Free Approach to Inducing
Correlations Among Input Variables for Simulation Studies »: Technical
Report NUREG CR 0390, Sandia Laboratories, Albuquerque (1980).
• McKay, M.D, Conover, W.J., and Beckman, R.J. "A Comparison of Three
Methods for Selecting Values of Input Variables in the Analysis of
Output from a Computer Code": Technometrics (1979) 211, 239-245.
• Startzman, R. A. and Wattenbarger, R.A. "An Improved Computation
Procedure for Risk Analysis Problems With Unusual Probability
Functions": SPE Hydrocarbon Economics and Evaluation Symposium
Proceedings, Dallas (1985).
Annexe C : Ressources complémentaires
205
Exemples et études de cas faisant appel à la
simulation
Si vous souhaitez examiner des études de cas démontrant l’utilisation
de la simulation dans le cadre de situations réelles, consultez les
ouvrages suivants :
Hertz, D.B. et Thomas, H. Practical Risk Analysis – An Approach Through
Case Histories: John Wiley et Sons, New York, NY, 1984.
* Murtha, James A. Decisions Involving Uncertainty, An @RISK Tutorial for
the Petroleum Industry: James A. Murtha, Houston, Texas, 1993
• Newendorp, P.D. Decision Analysis for Petroleum Exploration: Petroleum
Publishing Company, Tulsa, Okla., 1975.
• Pouliquen, L.Y. Risk Analysis in Project Appraisal: World Bank Staff
Occasional Papers Number Eleven. John Hopkins Press, Baltimore, MD,
1970.
* Trippi, Robert R. and Truban, Efraim, Neural Networks: In Finance et
Investing: Probus Publishing Co., 1993
206
Ressources complémentaires
Glossaire
Pour tous autres détails concernant un terme particulier, voir l’index
Evolver au chapitre suivant.
Algorithme
Méthode mathématique de résolution pas à pas d’un certain type de
problème. Tous les programmes informatiques reposent sur la
combinaison de nombreux algorithmes.
Algorithme
génétique
Procédure d’amélioration des résultats d’une opération par essai
répété de plusieurs solutions possibles et reproduction et mélange des
éléments des meilleures solutions. Le processus est inspiré de celui de
l’évolution biologique naturelle, avec survie et reproduction du plus
apte. Il ressemble d’ailleurs très fort à ce processus.
Algorithme par
escalade
Procédure d’optimisation partant d’un scénario donné et procédant
par répétition, à petits pas, dans la direction qui l’améliore le plus. Les
algorithmes par escalade sont rapides et simples, mais ils présentent
deux inconvénients. Le premier est qu’il n’est pas toujours facile de
trouver la direction de la meilleure amélioration. Ensuite, les
algorithmes escaladent généralement la colline la plus proche, ou
maximum local. La technique échoue ainsi dans la recherche du
maximum global d’un problème difficile.
Aplatissement
Mesure de la forme d’une distribution, plate ou culminante. Plus la
valeur d’aplatissement est élevée, plus la distribution est culminante.
Voir Asymétrie
Asymétrie
Mesure de la forme d’une distribution. L’asymétrie indique le degré
de dissymétrie dans une distribution. Les distributions asymétriques
comportent un plus grand nombre de valeurs d’un côté de la valeur
culminante ou valeur probable : une queue est beaucoup plus longue
que l’autre. Une asymétrie nulle (0) indique une distribution
symétrique, tandis qu’une asymétrie négative révèle une distribution
désaxée vers la gauche et une asymétrie positive, une dissymétrie vers
la droite.
Voir Aplatissement
Barre d’état
Barre figurant au bas de la fenêtre Excel, indicatrice de l’activité
courante d’Evolver.
Glossaire
207
Boîte de dialogue
Fenêtre d’un écran d’ordinateur dans laquelle l’utilisateur est invité à
fournir l’information demandée. Evolver présente deux grandes
boîtes de dialogue : Modèle et Cellules ajustables.
Cellule
La cellule est l’unité élémentaire de la feuille de calcul, dans laquelle
les données sont stockées. Chaque feuille de calcul Excel peut compter
jusqu’à 256 colonnes et 16 000 lignes, pour un total de plus de 4
millions de cellules.
Cellule ajustable
Cellule de tableur dont la valeur peut être ajustée par Evolver dans le
but d’optimiser la valeur de la cellule cible. Une cellule ajustable est
une valeur variable. Elle doit toujours contenir une valeur numérique
simple, plutôt qu’une équation.
Cellule cible
Cellule de la feuille de calcul dont on veut minimiser ou maximiser la
valeur. Cette cellule est identifiée dans la boîte de dialogue Modèle
d’Evolver (commande Définition du modèle ou icône Modèle
d’Evolver).
Centile
Incrément des valeurs dans un groupe de données. Les centiles
divisent les données en 100 parts égales, contenant chacune un pour
cent des valeurs totales. Le 60e centile, par exemple, est la valeur de
l’ensemble par rapport à laquelle 60 % des valeurs sont inférieures et
40 %, supérieures.
Champ
Unité élémentaire destinée à l’entrée de données. Suivant son type, un
champ peut recevoir du texte, des images ou des valeurs numériques.
La plupart des champs des boîtes de dialogue d’Evolver invitent
l’utilisateur à indiquer l’emplacement de cellules de tableur ou à
préciser les options de comportement d’Evolver.
Contraintes
Les contraintes sont les conditions qui devraient (contraintes souples)
ou doivent (contraintes fermes) être satisfaites pour qu’un scénario
soit jugé valable.
Contraintes
fermes
Contraintes obligatoires. Par exemple, les plages des variables d’un
problème de type recette sont des contraintes fermes. Une variable de
plage comprise entre 10 et 20 ne peut jamais représenter une valeur
inférieure à 10 ou supérieure à 20. Voir aussi contraintes souples.
208
Contraintes
souples
Les contraintes qui ne doivent pas obligatoirement être respectées de
manière rigoureuse peuvent être définies comme contraintes souples
plutôt que fermes. On spécifie alors une fonction de pénalité dans
Evolver ou on ajoute cette fonction à la fonction de pertinence de la
cellule cible.
Il vaut généralement mieux que les contraintes soient souples. La
raison en est que : 1) Evolver résout généralement plus rapidement les
problèmes sous contraintes souples et 2) un modèle sous contraintes
souples trouve souvent une très bonne solution presque parfaitement
conforme aux contraintes souples et donc plus intéressante qu’une
solution moins bonne même si conforme aux contraintes fermes.
Croisement
Dans le contexte génétique, le croisement est un échange de matériel
génétique équivalent entre chromatides homologues lors de la
méiose. Dans Evolver, le terme croisement désigne l’équivalent
informatique de ce concept, où l’échange entre les variables produit
de nouvelles combinaisons de scénarios.
Déterministe
Terme indiquant l’absence d’incertitude dans une valeur ou variable
donnée.
Distribution
continue
Distribution de probabilités dans laquelle n’importe quelle valeur
comprise entre le minimum et le maximum est possible (probabilité
finie).
Voir Distribution discrète
Distribution
cumulative
Ensemble de points dont chacun représente une distribution de
probabilités intégrale commençant à la valeur minimale et aboutissant
à la valeur associée de la variable aléatoire.
Voir Distribution cumulative de fréquences, Distribution de probabilités
Distribution
cumulative de
fréquences
Terme désignant les distributions cumulatives en entrée et de sortie
d’Evolver. Une distribution cumulative se construit par cumul de la
fréquence (ajout progressif de hauteurs de barres) sur la plage d’une
distribution de fréquence. Une distribution cumulative peut être une
courbe « à pente inclinée vers le haut », dans laquelle la distribution
décrit la probabilité d’une valeur inférieure ou égale à une valeur
variable quelconque. Elle peut aussi être « inclinée vers le bas »,
lorsque la distribution décrit la probabilité d’une valeur supérieure ou
égale à une valeur variable quelconque.
Voir Distribution cumulative
Distribution de
fréquence
Terme correct désignant les distributions de probabilités de sortie et
les histogrammes en entrée (HISTOGRM) d’Evolver. Une distribution
de fréquence se construit à partir des données, moyennant
l’organisation des valeurs en classes et la représentation de la
Glossaire
209
fréquence de réalisation dans une classe quelconque par la hauteur de
la barre. Cette fréquence correspond à la probabilité.
Distribution de
probabilités
Distribution de probabilités ou fonction de densité de probabilité est
le terme statistique correct désignant une distribution de fréquence
construite à partir d’un ensemble de valeurs infiniment grand, où la
taille des classes est infinitésimale.
Voir Distribution de fréquence
Distribution
discrète
Distribution de probabilités dans laquelle seul est possible un nombre
fini de valeurs discrètes compris entre le minimum et le maximum.
Voir Distribution continue
Écart type
Mesure de la dispersion des valeurs d’une distribution, égale à la
racine carrée de la variance.
Voir Variance
Échantillon
aléatoire
Valeur choisie dans une distribution de probabilités décrivant une
variable aléatoire. Cet échantillon est prélevé au hasard selon un
« algorithme » d’échantillonnage. La distribution de fréquence
construite à partir d’un grand nombre d’échantillons aléatoires
prélevés par un tel algorithme se rapproche étroitement de la
distribution de probabilités pour laquelle l’algorithme a été conçu.
Essais
Processus par lequel Evolver génère une valeur pour chaque variable
du problème, puis recalcule le scénario en vue de son évaluation.
Fonction de
pénalité
Équation de feuille de calcul qu’Evolver peut utiliser pour pénaliser
les scénarios non conformes à certains critères. Les fonctions de
pénalité servent à minimiser les effets secondaires des scénarios ou à
atteindre de multiples objectifs. Contrairement à une contrainte ferme,
une fonction de pénalité admet l’exploration de solutions non
conformes : elle « pénalise » simplement ces solutions pour que
l’évolution de la population s’en écarte. Les pénalités booléennes sont
de type « oui » ou « non » : elles imposent la même pénalité à toutes
les solutions non conformes. Les échelles de pénalité sont plus
souples, en ce que leur action est proportionnelle à l’importance de la
violation.
Fonction de
pertinence
Formule de calcul de la qualité ou non d’une solution proposée à un
problème donné. L’expression désigne souvent le champ de
l’algorithme génétique par analogie à la sélection biologique. La
conception exacte d’une fonction de pertinence est essentielle à
l’utilisation d’un algorithme génétique pour la résolution d’un
problème. Un résultat de simulation de cette fonction de pertinence
devient le but ou la valeur cible à optimiser.
210
Fonctions
Dans Excel, une fonction est une formule prédéfinie qui prend une
valeur, effectue une opération et renvoie une valeur. Excel propose
des centaines de formules intégrées (« SOMME », par exemple), pour
une économie de temps et d’espace. Par exemple, plutôt que de taper
A1+ A2+ A3+ A4+ A5+ A6, on tapera SOMME(A1:A6) et on
obtiendra, rapidement, le même résultat.
Génération
Dans le domaine des algorithmes génétiques, chaque population
totalement nouvelle de solutions « descendantes » est une nouvelle
« génération ». Certaines routines d’algorithme génétique accouplent
tous les membres d’une population en même temps, pour créer une
toute nouvelle « génération » d’organismes descendants venant
remplacer la population précédente. Evolver évalue et remplace
plutôt un organisme à la fois (par rang). Le terme « génération » n’est
donc pas utilisé dans sa documentation. L’approche d’Evolver, dite de
régime permanent, est tout aussi efficace que le remplacement
générationnel.
Génotype
En biologie, constitution génétique d’un individu. Le terme fait
généralement référence à la somme totale des gènes de l’individu.
Dans l’étude des AG, le génotype sert à décrire le « chromosome »
artificiel évalué comme solution possible au problème.
Groupe de
cellules
ajustables
Chaque ensemble de variables, assorti de la manière dont il doit être
traité, constitue un groupe de cellules ajustables. Evolver liste tous les
groupes de cellules ajustables dans le volet réservé aux variables de la
boîte de dialogue Modèle. Cette architecture permet l’élaboration et la
description de problèmes complexes sous la forme de groupes divers
de cellules ajustables.
Hypercube latin
Technique d’échantillonnage stratifié relativement neuve utilisée dans
la modélisation par simulation. Contrairement aux techniques de type
Monte Carlo, les techniques d’échantillonnage stratifié tendent à
forcer la convergence d’une distribution échantillonnée en moins
d’échantillons.
Voir Monte Carlo
Itération
Désigne un recalcul du modèle de l’utilisateur durant une simulation.
Une simulation comprend de nombreux recalculs ou itérations. À
chaque itération, toutes les variables incertaines sont échantillonnées
une fois selon leur distribution de probabilités, et le modèle est
recalculé sur la base des valeurs échantillonnées.
Aussi connu sous le terme d’essai de simulation
Maximum global
Plus grande valeur possible d’une fonction donnée. Les fonctions ou
les modèles complexes peuvent avoir de nombreux maxima locaux
mais un seul maximum global.
Glossaire
211
Maximum local
Plus grande valeur possible d’une fonction donnée dans une plage
donnée de valeurs. Un maximum local existe à un ensemble de
valeurs de variables d’une fonction si une légère variation de la valeur
d’une variable ou de toutes produit un moindre résultat de la
fonction. (Comparer avec maximum global).
Méthode de
résolution
Evolver propose six méthodes de résolution, reposant chacune sur un
algorithme adapté au type de problème considéré. Pour chaque
ensemble de variables sélectionnées dans un problème, l’utilisateur
doit choisir la méthode de résolution à utiliser. Les six méthodes
proposées sont les suivantes : groupement, ordre, recette, budget,
projet et programme.
Mini-solveur
jargon Programme logiciel peu élaboré de recherche des entrées qui
produisent une sortie désirée par une combinaison de techniques de
programmation linéaire ou d’algorithmes élémentaires d’escalade.
Les mini-solveurs procèdent souvent « au pifomètre », puis raffinent
leur réponse pour arriver à une solution « locale » plutôt que
« globale ».
Modèle
Aux fins de ce manuel, un modèle est une représentation numérique,
dans Excel, d’une situation réelle.
Moments élevés
Les moments élevés sont des statistiques de distribution de
probabilités. Le terme désigne généralement l’asymétrie et
l’aplatissement, soit le troisième et le quatrième moment,
respectivement. Les premier et deuxième moments sont,
respectivement, la moyenne et l’écart type.
Voir Asymétrie, Aplatissement, Moyenne, Écart type
Monte Carlo
Désigne la méthode traditionnelle d’échantillonnage de variables
aléatoires dans la modélisation par simulation. Les échantillons sont
sélectionnés au hasard sur la plage de la distribution, nécessitant dès
lors de nombreux échantillons pour la convergence des distributions
hautement asymétriques ou à queue étalée.
Voir Hypercube latin
Moyenne
La moyenne d’un ensemble de valeurs est la somme de toutes les
valeurs de l’ensemble, divisée par le nombre total des valeurs qu’il
contient.
Synonyme : valeur probable
Mutation
Dans le monde biologique, la mutation génétique est la source de
variation nécessaire à une sélection naturelle efficace. De même, un
algorithme génétique recourt aux techniques de mutation pour
maintenir la diversité d’une population de scénarios possibles.
212
Optimisation
Processus de recherche de valeurs de variables en vue de la
maximisation (valeur la plus grande possible) ou de la minimisation
(valeur la plus petite possible) de la sortie. L’optimisation par
résolution d’équation est simple pour les fonctions à variation lisse et
variables peu nombreuses. Elle est cependant extrêmement difficile
dans le cas de nombreux problèmes réels. Ces problèmes complexes
exigent généralement un mécanisme de recherche. Evolver utilise un
mécanisme de recherche par optimisation basé sur un algorithme
génétique.
Organisme
Bloc de mémoire d’une population qui stocke un ensemble de valeurs
de variables (scénario).
Phénotypes
En biologie, trait observable d’un individu, issu de l’interaction des
gènes et de l’interaction entre les gènes et le milieu. Dans l’étude des
AG, le phénotype sert à décrire les variables ou « gènes » individuels
dont se compose une solution complète ou un « chromosome ». (voir
Génotype)
Plages
Dans Evolver :
L’utilisateur définit la plage, soit la valeur la plus et la moins élevée
qu’Evolver peut essayer lors de l’ajustement d’une certaine variable.
Bien qu’une plage ne soit pas nécessaire à la résolution d’un
problème, sa définition limite les possibilités et concentre donc la
recherche effectuée par Evolver.
Dans Excel :
Bloc de cellules contiguës d’une feuille de calcul, défini par la cellule
supérieure gauche et la cellule inférieure droite (A5:C9 décrit par
exemple une plage de 15 cellules).
Population
Ensemble complet de scénarios qu’Evolver garde en mémoire pour la
génération de nouveaux scénarios. Evolver conserve une population
de solutions possibles pour chaque groupe de cellules ajustables d’un
système.
Probabilité
Grandeur par laquelle on mesure la vraisemblance de réalisation
d’une valeur ou d’un événement. Elle peut être mesurée à partir de
données de simulation, sous forme de fréquence, par le calcul du
nombre de réalisations de la valeur ou de l’événement divisé par le
nombre total de réalisations. Ce calcul renvoie une valeur comprise
entre 0 et 1 qui, multipliée par 100, est alors convertie en pourcentage.
Voir Distribution de fréquence, Distribution de probabilités
Glossaire
213
Racine /
Générateur
de nombres
aléatoires
Algorithme régissant le choix des nombres aléatoires, généralement
compris entre 0 et 1. Ces nombres aléatoires correspondent aux
échantillons prélevés dans une distribution uniforme à valeur
minimum de 0 et maximum de 1. Ils constituent la base d’autres
routines les convertissant en échantillons prélevés des types de
distribution spécifiques.
Voir Échantillon aléatoire, Racine
Scénario
Ensemble de valeurs des variables d’un modèle de feuille de calcul.
Chaque scénario représente le plus souvent une solution possible.
Simulation
Technique selon laquelle un modèle, tel qu’une feuille de calcul Excel,
est calculé à de nombreuses reprises sur la base de différentes valeurs
en entrée, dans le but d’obtenir une représentation complète de tous
les scénarios susceptibles de se produire dans une situation incertaine.
Solution
Un système contient de nombreuses variables en entrée qui
produisent une sortie. Dans Evolver, une « solution »représente plus
souvent l’une des combinaisons possibles de variables plutôt que la
meilleure combinaison.
Stochastique
Synonyme de risqué, incertain.
Voir Risque, Déterministe
Survie du plus
apte
Concept selon lequel les organismes mieux adaptés à leur milieu sont
plus susceptibles de vivre suffisamment longtemps pour se
reproduire et répandre leurs gènes dans la génération suivante d’une
population.
Valeur probable
La valeur ou le mode probable représente la valeur le plus
fréquemment rencontrée dans un ensemble de valeurs. Dans un
histogramme et une distribution de résultats, il s’agit de la valeur
centrale de la classe ou barre indiquant la probabilité la plus élevée.
Variable
dépendante
Variable tributaire, dans une certaine mesure, des valeurs d’autres
variables du modèle considéré. La valeur d’une variable dépendante
incertaine peut être calculée dans une équation en tant que fonction
d’autres variables incertaines du modèle. Elle peut aussi être tirée
d’une distribution en fonction du nombre aléatoire corrélé à un
nombre aléatoire utilisé pour prélever un échantillon de variable
indépendante.
Voir Variable indépendante
214
Variable
indépendante
Glossaire
Variable non tributaire des valeurs d’aucune autre variable du modèle
considéré. La valeur d’une variable indépendante incertaine est
déterminée par le prélèvement d’un échantillon dans la distribution
de probabilités appropriée. L’échantillon est prélevé
indépendamment de tout autre échantillon aléatoire prélevé pour les
autres variables du modèle.
Voir Variable dépendante
215
216
Indice
A
Ajout de contraintes
algorithme, définition
algorithmes génétiques
exemple biologique
pourquoi ?
Apprendre Evolver
118
149
172
16
10
B
barre d’état
bases de données
boîte de dialogue Modèle
Boîte de dialogue Modèle
But d’optimisation
135, 207
162
99
26
27, 100
C
capital génétique
cellule cible
cellules ajustables
Centile
Commande Paramètres d’application
Commande Solveur de contraintes
conditions d’arrêt
Conditions d’arrêt
introduction
contraintes
mode d’exécution
contraintes fermes
contraintes souples
croisement
mode d’exécution
Indice
175
27, 100, 208
27, 101
208
131
132
125
35
179
193
31, 119
31, 119, 120, 182
192
217
D
Désinstallation d’Evolver
didacticiel
7
10
E
Entières
escalade
description
exemple
utilisation Solveur
Evolver
Didacticiel
Evolver
qu’est-ce que…?
Evolver
pourquoi ?
Evolver
vs Solveur Microsoft
Evolver
quand ?
Evolver
capacités
exemple boulangerie
exemple d’achat
exemple d’affectation de tâches
exemple d’allocation budgétaire
exemple d’emplacement de pylônes radio
exemple d’équilibrage de portefeuilles
exemple d’équilibre chimique
exemple d’itinéraire
exemple d’ordonnancement multigamme
exemple de composition de portefeuille
exemple de l’opérateur en bourse
exemple de mise en ordre alphabétique
exemple de planificateur de classes
exemple de segmenteur de code
exemple de sélection publicitaire
exemple de transports
exemple du navigateur spatial
exemple du transformateur
exemple du voyageur de commerce
exemple émetteurs radio
218
103
151
159
160
155
10
13
16
156
157
149
55
85
53
57
75
77
59
69
73
81
91
49
61
65
47
95
89
93
87
83
F
fenêtre Progression
Fichier Lisezmoi
fonctions de pénalité
description
exemples
utilisation
function de pertinence
129
10
182
185
186
23, 100
G
générations
pourquoi pas
graphiques
191
38, 136
M
méthode de remplacement
méthode de résolution budget
description
exemple
méthode de résolution groupement
description
exemple
méthode de résolution ordre
description
exemple
méthode de résolution programme
description
exemple
méthode de résolution projet
description
exemple
méthode de résolution recette
description
exemple
Méthode Simplexe
méthodes de résolution
budget
exemple
en tant que contraintes
groupement
exemple
ordre
exemple
programme
Indice
193
108
47, 57, 81, 83
107
65, 77
106
53, 73, 87
110
61
109
69
106
49, 55, 59, 75, 85, 89, 91, 93, 95
159
108
47, 57, 81, 83
180
107
65, 77
106
53, 73, 87
110
219
exemple
projet
exemple
recette
exemple
minutes
modèles continus
61
109
69
106
49, 55, 59, 75, 85, 89, 91, 93, 95
125
155
O
opérateur génétique
Opérateurs
optimisation
définition
exemple
méthodes
options Temps d’exécution
115
115
15
153
149
125
P
Palisade Corporation
paysage de solutions
problèmes
à base de tables
combinatoires
linéaires
non linéaires
problèmes à base de tables
problèmes à buts multiples
problèmes combinatoires
problèmes linéaires
problèmes non linéaires
Progression graphique
image
5
150
162
162
159
159
162
187
149
159
159
36
R
recul
redessin d‘écran
image
routine de sélection
routines GRG
220
193
36
191
155
S
solution globale
vs solution locale
solution locale
vs solution globale
Solveur
vs Evolver
spécifications techniques
Suivi
Suivi Evolver
155
155
156
191
38, 135
38, 135
T
taux de croisement
fonction
taux de mutation
fonction
mode d’exécution
138, 174
113
138
113
193
V
Valeurs
vitesse, amélioration
Indice
103
189
221
">