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 ">
Enlace público actualizado
El enlace público a tu chat ha sido actualizado.