9 resultados para Genetic Algorithms, Multi-Objective, Pareto Ranking, Sum of Ranks, Hub Location Problem, Weighted Sum
em Université de Montréal, Canada
Resumo:
Les systmes logiciels sont devenus de plus en plus rpondus et importants dans notre socit. Ainsi, il y a un besoin constant de logiciels de haute qualit. Pour amliorer la qualit de logiciels, lune des techniques les plus utilises est le refactoring qui sert amliorer la structure d'un programme tout en prservant son comportement externe. Le refactoring promet, s'il est appliqu convenablement, amliorer la comprhensibilit, la maintenabilit et l'extensibilit du logiciel tout en amliorant la productivit des programmeurs. En gnral, le refactoring pourra sappliquer au niveau de spcification, conception ou code. Cette thse porte sur l'automatisation de processus de recommandation de refactoring, au niveau code, sappliquant en deux tapes principales: 1) la dtection des fragments de code qui devraient tre amliors (e.g., les dfauts de conception), et 2) l'identification des solutions de refactoring appliquer. Pour la premire tape, nous traduisons des rgularits qui peuvent tre trouvs dans des exemples de dfauts de conception. Nous utilisons un algorithme gntique pour gnrer automatiquement des rgles de dtection partir des exemples de dfauts. Pour la deuxime tape, nous introduisons une approche se basant sur une recherche heuristique. Le processus consiste trouver la squence optimale d'oprations de refactoring permettant d'amliorer la qualit du logiciel en minimisant le nombre de dfauts tout en priorisant les instances les plus critiques. De plus, nous explorons d'autres objectifs optimiser: le nombre de changements requis pour appliquer la solution de refactoring, la prservation de la smantique, et la consistance avec lhistorique de changements. Ainsi, rduire le nombre de changements permets de garder autant que possible avec la conception initiale. La prservation de la smantique assure que le programme restructur est smantiquement cohrent. De plus, nous utilisons l'historique de changement pour suggrer de nouveaux refactorings dans des contextes similaires. En outre, nous introduisons une approche multi-objective pour amliorer les attributs de qualit du logiciel (la flexibilit, la maintenabilit, etc.), fixer les mauvaises pratiques de conception (dfauts de conception), tout en introduisant les bonnes pratiques de conception (patrons de conception).
Resumo:
We provide a survey of the literature on ranking sets of objects. The interpretations of those set rankings include those employed in the theory of choice under complete uncertainty, rankings of opportunity sets, set rankings that appear in matching theory, and the structure of assembly preferences. The survey is prepared for the Handbook of Utility Theory, vol. 2, edited by Salvador Barber, Peter Hammond, and Christian Seidl, to be published by Kluwer Academic Publishers. The chapter number is provisional.
Resumo:
Thse ralise en cotutelle entre l'Universit de Montral et l'Universit de Technologie de Troyes
Resumo:
Lvolution rcente des commutateurs de slection de longueurs donde (WSS -Wavelength Selective Switch) favorise le dveloppement du multiplexeur optique dinsertionextraction reconfigurable (ROADM - Reconfigurable Optical Add/Drop Multiplexers) plusieurs degrs sans orientation ni coloration, considr comme un quipement fort prometteur pour les rseaux maills du futur relativement au multiplexage en longueur donde (WDM -Wavelength Division Multiplexing ). Cependant, leur proprit de commutation asymtrique complique la question de lacheminement et de lattribution des longueur dondes (RWA - Routing andWavelength Assignment). Or la plupart des algorithmes de RWA existants ne tiennent pas compte de cette proprit dasymtrie. Linterruption des services cause par des dfauts dquipements sur les chemins optiques (rsultat provenant de la rsolution du problme RWA) a pour consquence la perte dune grande quantit de donnes. Les recherches deviennent ainsi incontournables afin dassurer la survie fonctionnelle des rseaux optiques, savoir, le maintien des services, en particulier en cas de pannes dquipement. La plupart des publications antrieures portaient particulirement sur lutilisation dun systme de protection permettant de garantir le reroutage du trafic en cas dun dfaut dun lien. Cependant, la conception de la protection contre le dfaut dun lien ne savre pas toujours suffisante en termes de survie des rseaux WDM partir de nombreux cas des autres types de pannes devenant courant de nos jours, tels que les bris dquipements, les pannes de deux ou trois liens, etc. En outre, il y a des dfis considrables pour protger les grands rseaux optiques multidomaines composs de rseaux associs un domaine simple, interconnects par des liens interdomaines, o les dtails topologiques internes dun domaine ne sont gnralement pas partags lextrieur. La prsente thse a pour objectif de proposer des modles doptimisation de grande taille et des solutions aux problmes mentionns ci-dessus. Ces modles-ci permettent de gnrer des solutions optimales ou quasi-optimales avec des carts doptimalit mathmatiquement prouve. Pour ce faire, nous avons recours la technique de gnration de colonnes afin de rsoudre les problmes inhrents la programmation linaire de grande envergure. Concernant la question de lapprovisionnement dans les rseaux optiques, nous proposons un nouveau modle de programmation linaire en nombres entiers (ILP - Integer Linear Programming) au problme RWA afin de maximiser le nombre de requtes acceptes (GoS - Grade of Service). Le modle rsultant constitue celui de loptimisation dun ILP de grande taille, ce qui permet dobtenir la solution exacte des instances RWA assez grandes, en supposant que tous les noeuds soient asymtriques et accompagns dune matrice de connectivit de commutation donne. Ensuite, nous modifions le modle et proposons une solution au problme RWA afin de trouver la meilleure matrice de commutation pour un nombre donn de ports et de connexions de commutation, tout en satisfaisant/maximisant la qualit dcoulement du trafic GoS. Relativement la protection des rseaux dun domaine simple, nous proposons des solutions favorisant la protection contre les pannes multiples. En effet, nous dveloppons la protection dun rseau dun domaine simple contre des pannes multiples, en utilisant les p-cycles de protection avec un chemin indpendant des pannes (FIPP - Failure Independent Path Protecting) et de la protection avec un chemin dpendant des pannes (FDPP - Failure Dependent Path-Protecting). Nous proposons ensuite une nouvelle formulation en termes de modles de flots pour les p-cycles FDPP soumis des pannes multiples. Le nouveau modle soulve un problme de taille, qui a un nombre exponentiel de contraintes en raison de certaines contraintes dlimination de sous-tour. Par consquent, afin de rsoudre efficacement ce problme, on examine : (i) une dcomposition hirarchique du problme auxiliaire dans le modle de dcomposition, (ii) des heuristiques pour grer efficacement le grand nombre de contraintes. propos de la protection dans les rseaux multidomaines, nous proposons des systmes de protection contre les pannes dun lien. Tout dabord, un modle doptimisation est propos pour un systme de protection centralise, en supposant que la gestion du rseau soit au courant de tous les dtails des topologies physiques des domaines. Nous proposons ensuite un modle distribu de loptimisation de la protection dans les rseaux optiques multidomaines, une formulation beaucoup plus raliste car elle est base sur lhypothse dune gestion de rseau distribu. Ensuite, nous ajoutons une bande pasiv sante partage afin de rduire le cot de la protection. Plus prcisment, la bande passante de chaque lien intra-domaine est partage entre les p-cycles FIPP et les p-cycles dans une premire tude, puis entre les chemins pour lien/chemin de protection dans une deuxime tude. Enfin, nous recommandons des stratgies parallles aux solutions de grands rseaux optiques multidomaines. Les rsultats de ltude permettent dlaborer une conception efficace dun systme de protection pour un trs large rseau multidomaine (45 domaines), le plus large examin dans la littrature, avec un systme la fois centralis et distribu.
Resumo:
La scoliose idiopathique de ladolescent (SIA) est une dformation tri-dimensionelle du rachis. Son traitement comprend lobservation, lutilisation de corsets pour limiter sa progression ou la chirurgie pour corriger la dformation squelettique et cesser sa progression. Le traitement chirurgical reste controvers au niveau des indications, mais aussi de la chirurgie entreprendre. Malgr la prsence de classifications pour guider le traitement de la SIA, une variabilit dans la stratgie opratoire intra et inter-observateur a t dcrite dans la littrature. Cette variabilit saccentue dautant plus avec lvolution des techniques chirurgicales et de linstrumentation disponible. Lavancement de la technologie et son intgration dans le milieu mdical a men lutilisation dalgorithmes dintelligence artificielle informatiques pour aider la classification et lvaluation tridimensionnelle de la scoliose. Certains algorithmes ont dmontr tre efficace pour diminuer la variabilit dans la classification de la scoliose et pour guider le traitement. Lobjectif gnral de cette thse est de dvelopper une application utilisant des outils dintelligence artificielle pour intgrer les donnes dun nouveau patient et les vidences disponibles dans la littrature pour guider le traitement chirurgical de la SIA. Pour cela une revue de la littrature sur les applications existantes dans lvaluation de la SIA fut entreprise pour rassembler les lments qui permettraient la mise en place dune application efficace et accepte dans le milieu clinique. Cette revue de la littrature nous a permis de raliser que lexistence de black box dans les applications dveloppes est une limitation pour lintgration clinique ou la justification base sur les vidence est essentielle. Dans une premire tude nous avons dvelopp un arbre dcisionnel de classification de la scoliose idiopathique bas sur la classification de Lenke qui est la plus communment utilise de nos jours mais a t critique pour sa complexit et la variabilit inter et intra-observateur. Cet arbre dcisionnel a dmontr quil permet daugmenter la prcision de classification proportionnellement au temps pass classifier et ce indpendamment du niveau de connaissance sur la SIA. Dans une deuxime tude, un algorithme de stratgies chirurgicales bas sur des rgles extraites de la littrature a t dvelopp pour guider les chirurgiens dans la slection de lapproche et les niveaux de fusion pour la SIA. Lorsque cet algorithme est appliqu une large base de donne de 1556 cas de SIA, il est capable de proposer une stratgie opratoire similaire celle dun chirurgien expert dans prt de 70% des cas. Cette tude a confirm la possibilit dextraire des stratgies opratoires valides laide dun arbre dcisionnel utilisant des rgles extraites de la littrature. Dans une troisime tude, la classification de 1776 patients avec la SIA laide dune carte de Kohonen, un type de rseaux de neurone a permis de dmontrer quil existe des scoliose typiques (scoliose courbes uniques ou double thoracique) pour lesquelles la variabilit dans le traitement chirurgical varie peu des recommandations par la classification de Lenke tandis que les scolioses a courbes multiples ou tangentielles deux groupes de courbes typiques taient celles avec le plus de variation dans la stratgie opratoire. Finalement, une plateforme logicielle a t dveloppe intgrant chacune des tudes ci-dessus. Cette interface logicielle permet lentre de donnes radiologiques pour un patient scoliotique, classifie la SIA laide de larbre dcisionnel de classification et suggre une approche chirurgicale base sur larbre dcisionnel de stratgies opratoires. Une analyse de la correction post-opratoire obtenue dmontre une tendance, bien que non-statistiquement significative, une meilleure balance chez les patients oprs suivant la stratgie recommande par la plateforme logicielle que ceux aillant un traitement diffrent. Les tudes exposes dans cette thse soulignent que lutilisation dalgorithmes dintelligence artificielle dans la classification et llaboration de stratgies opratoires de la SIA peuvent tre intgres dans une plateforme logicielle et pourraient assister les chirurgiens dans leur planification propratoire.
Resumo:
Gnralement, les problmes de conception de rseaux consistent slectionner les arcs et les sommets dun graphe G de sorte que la fonction cot est optimise et lensemble de contraintes impliquant les liens et les sommets dans G sont respectes. Une modification dans le critre doptimisation et/ou dans lensemble de contraintes mne une nouvelle reprsentation dun problme diffrent. Dans cette thse, nous nous intressons au problme de conception dinfrastructure de rseaux maills sans fil (WMN- Wireless Mesh Network en Anglais) o nous montrons que la conception de tels rseaux se transforme dun problme doptimisation standard (la fonction cot est optimise) un problme doptimisation plusieurs objectifs, pour tenir en compte de nombreux aspects, souvent contradictoires, mais nanmoins incontournables dans la ralit. Cette thse, compose de trois volets, propose de nouveaux modles et algorithmes pour la conception de WMNs o rien nest connu l avance. Le premiervolet est consacr loptimisation simultane de deux objectifs quitablement importants : le cot et la performance du rseau en termes de dbit. Trois modles bi-objectifs qui se diffrent principalement par lapproche utilise pour maximiser la performance du rseau sont proposs, rsolus et compars. Le deuxime volet traite le problme de placement de passerelles vu son impact sur la performance et lextensibilit du rseau. La notion de contraintes de sauts (hop constraints) est introduite dans la conception du rseau pour limiter le dlai de transmission. Un nouvel algorithme bas sur une approche de groupage est propos afin de trouver les positions stratgiques des passerelles qui favorisent lextensibilit du rseau et augmentent sa performance sans augmenter considrablement le cot total de son installation. Le dernier volet adresse le problme de fiabilit du rseau dans la prsence de pannes simples. Prvoir linstallation des composants redondants lors de la phase de conception peut garantir des communications fiables, mais au dtriment du cot et de la performance du rseau. Un nouvel algorithme, bas sur lapproche thorique de dcomposition en oreilles afin dinstaller le minimum nombre de routeurs additionnels pour tolrer les pannes simples, est dvelopp. Afin de rsoudre les modles proposs pour des rseaux de taille relle, un algorithme volutionnaire (mta-heuristique), inspir de la nature, est dvelopp. Finalement, les mthodes et modles proposs on t valus par des simulations empiriques et dvnements discrets.
Resumo:
Depuis quelques annes, la recherche dans le domaine des rseaux maills sans fil ("Wireless Mesh Network (WMN)" en anglais) suscite un grand intrt auprs de la communaut des chercheurs en tlcommunications. Ceci est d aux nombreux avantages que la technologie WMN offre, telles que l'installation facile et peu coteuse, la connectivit fiable et l'interoprabilit flexible avec d'autres rseaux existants (rseaux Wi-Fi, rseaux WiMax, rseaux cellulaires, rseaux de capteurs, etc.). Cependant, plusieurs problmes restent encore rsoudre comme le passage l'chelle, la scurit, la qualit de service (QdS), la gestion des ressources, etc. Ces problmes persistent pour les WMNs, d'autant plus que le nombre des utilisateurs va en se multipliant. Il faut donc penser amliorer les protocoles existants ou en concevoir de nouveaux. L'objectif de notre recherche est de rsoudre certaines des limitations rencontres l'heure actuelle dans les WMNs et d'amliorer la QdS des applications multimdia temps-rel (par exemple, la voix). Le travail de recherche de cette thse sera divis essentiellement en trois principaux volets: le contrle dadmission du trafic, la diffrentiation du trafic et la raffectation adaptative des canaux lors de la prsence du trafic en relve ("handoff" en anglais). Dans le premier volet, nous proposons un mcanisme distribu de contrle d'admission se basant sur le concept des cliques (une clique correspond un sous-ensemble de liens logiques qui interfrent les uns avec les autres) dans un rseau multiples-sauts, multiples-radios et multiples-canaux, appel RCAC. Nous proposons en particulier un modle analytique qui calcule le ratio appropri d'admission du trafic et qui garantit une probabilit de perte de paquets dans le rseau n'excdant pas un seuil prdfini. Le mcanisme RCAC permet dassurer la QdS requise pour les flux entrants, sans dgrader la QdS des flux existants. Il permet aussi dassurer la QdS en termes de longueur du dlai de bout en bout pour les divers flux. Le deuxime volet traite de la diffrentiation de services dans le protocole IEEE 802.11s afin de permettre une meilleure QdS, notamment pour les applications avec des contraintes temporelles (par exemple, voix, visioconfrence). cet gard, nous proposons un mcanisme d'ajustement de tranches de temps ("time-slots"), selon la classe de service, ED-MDA (Enhanced Differentiated-Mesh Deterministic Access), combin un algorithme efficace de contrle d'admission EAC (Efficient Admission Control), afin de permettre une utilisation leve et efficace des ressources. Le mcanisme EAC prend en compte le trafic en relve et lui attribue une priorit suprieure par rapport au nouveau trafic pour minimiser les interruptions de communications en cours. Dans le troisime volet, nous nous intressons minimiser le surcot et le dlai de re-routage des utilisateurs mobiles et/ou des applications multimdia en raffectant les canaux dans les WMNs Multiples-Radios (MR-WMNs). En premier lieu, nous proposons un modle d'optimisation qui maximise le dbit, amliore l'quit entre utilisateurs et minimise le surcot d la relve des appels. Ce modle a t rsolu par le logiciel CPLEX pour un nombre limit de noeuds. En second lieu, nous laborons des heuristiques/mta-heuristiques centralises pour permettre de rsoudre ce modle pour des rseaux de taille relle. Finalement, nous proposons un algorithme pour raffecter en temps-rel et de faon prudente les canaux aux interfaces. Cet algorithme a pour objectif de minimiser le surcot et le dlai du re-routage spcialement du trafic dynamique gnr par les appels en relve. Ensuite, ce mcanisme est amlior en prenant en compte lquilibrage de la charge entre cliques.
Resumo:
Les techniques de groupement technologique sont aujourdhui utilises dans de nombreux ateliers de fabrication; elles consistent dcomposer les systmes industriels en sous-systmes ou cellules constitus de pices et de machines. Trouver le groupement technologique le plus efficace est formul en recherche oprationnelle comme un problme de formation de cellules. La rsolution de ce problme permet de tirer plusieurs avantages tels que la rduction des stocks et la simplification de la programmation. Plusieurs critres peuvent tre dfinis au niveau des contraintes du problme tel que le flot intercellulaire,lquilibrage de charges intracellulaires, les cots de sous-traitance, les cots de duplication des machines, etc. Le problme de formation de cellules est un problme d'optimisation NP-difficile. Par consquent les mthodes exactes ne peuvent tre utilises pour rsoudre des problmes de grande dimension dans un dlai raisonnable. Par contre des mthodes heuristiques peuvent gnrer des solutions de qualit infrieure, mais dans un temps dexcution raisonnable. Dans ce mmoire, nous considrons ce problme dans un contexte bi-objectif spcifi en termes dun facteur dautonomie et de lquilibre de charge entre les cellules. Nous prsentons trois types de mthodes mtaheuristiques pour sa rsolution et nous comparons numriquement ces mtaheuristiques. De plus, pour des problmes de petite dimension qui peuvent tre rsolus de faon exacte avec CPLEX, nous vrifions que ces mtaheuristiques gnrent des solutions optimales.
Resumo:
Les dcisions de localisation sont souvent soumises des aspects dynamiques comme des changements dans la demande des clients. Pour y rpondre, la solution consiste considrer une flexibilit accrue concernant lemplacement et la capacit des installations. Mme lorsque la demande est prvisible, trouver le planning optimal pour le dploiement et l'ajustement dynamique des capacits reste un dfi. Dans cette thse, nous nous concentrons sur des problmes de localisation avec priodes multiples, et permettant l'ajustement dynamique des capacits, en particulier ceux avec des structures de cots complexes. Nous tudions ces problmes sous diffrents points de vue de recherche oprationnelle, en prsentant et en comparant plusieurs modles de programmation linaire en nombres entiers (PLNE), l'valuation de leur utilisation dans la pratique et en dveloppant des algorithmes de rsolution efficaces. Cette thse est divise en quatre parties. Tout dabord, nous prsentons le contexte industriel lorigine de nos travaux: une compagnie forestire qui a besoin de localiser des campements pour accueillir les travailleurs forestiers. Nous prsentons un modle PLNE permettant la construction de nouveaux campements, lextension, le dplacement et la fermeture temporaire partielle des campements existants. Ce modle utilise des contraintes de capacit particulires, ainsi quune structure de cot conomie dchelle sur plusieurs niveaux. L'utilit du modle est value par deux tudes de cas. La deuxime partie introduit le problme dynamique de localisation avec des capacits modulaires gnralises. Le modle gnralise plusieurs problmes dynamiques de localisation et fournit de meilleures bornes de la relaxation linaire que leurs formulations spcialises. Le modle peut rsoudre des problmes de localisation o les cots pour les changements de capacit sont dfinis pour toutes les paires de niveaux de capacit, comme c'est le cas dans le problme industriel mentionne ci-dessus. Il est appliqu trois cas particuliers: l'expansion et la rduction des capacits, la fermeture temporaire des installations, et la combinaison des deux. Nous dmontrons des relations de dominance entre notre formulation et les modles existants pour les cas particuliers. Des expriences de calcul sur un grand nombre dinstances gnres alatoirement jusqu 100 installations et 1000 clients, montrent que notre modle peut obtenir des solutions optimales plus rapidement que les formulations spcialises existantes. Compte tenu de la complexit des modles prcdents pour les grandes instances, la troisime partie de la thse propose des heuristiques lagrangiennes. Bases sur les mthodes du sous-gradient et des faisceaux, elles trouvent des solutions de bonne qualit mme pour les instances de grande taille comportant jusqu 250 installations et 1000 clients. Nous amliorons ensuite la qualit de la solution obtenue en rsolvent un modle PLNE restreint qui tire parti des informations recueillies lors de la rsolution du dual lagrangien. Les rsultats des calculs montrent que les heuristiques donnent rapidement des solutions de bonne qualit, mme pour les instances o les solveurs gnriques ne trouvent pas de solutions ralisables. Finalement, nous adaptons les heuristiques prcdentes pour rsoudre le problme industriel. Deux relaxations diffrentes sont proposes et compares. Des extensions des concepts prcdents sont prsentes afin d'assurer une rsolution fiable en un temps raisonnable.
