8 resultados para Algorithms
em Université de Montréal, Canada
Resumo:
Le problme de localisation-routage avec capacits (PLRC) apparat comme un problme cl dans la conception de rseaux de distribution de marchandises. Il gnralisele problme de localisation avec capacits (PLC) ainsi que le problme de tournes de vhicules multiples dpts (PTVMD), le premier en ajoutant des dcisions lies au routage et le deuxime en ajoutant des dcisions lies la localisation des dpts. Dans cette thse on dvelope des outils pour rsoudre le PLRC laide de la programmation mathmatique. Dans le chapitre 3, on introduit trois nouveaux modles pour le PLRC bass sur des ots de vhicules et des ots de commodits, et on montre comment ceux-ci dominent, en termes de la qualit de la borne infrieure, la formulation originale deux indices [19]. Des nouvelles ingalits valides ont t dvelopes et ajoutes aux modles, de mme que des ingalits connues. De nouveaux algorithmes de sparation ont aussi t dvelops qui dans la plupart de cas gnralisent ceux trouvs dans la litterature. Les rsultats numriques montrent que ces modles de ot sont en fait utiles pour rsoudre des instances de petite moyenne taille. Dans le chapitre 4, on prsente une nouvelle mthode de gnration de colonnes base sur une formulation de partition densemble. Le sous-problme consiste en un problme de plus court chemin avec capacits (PCCC). En particulier, on utilise une relaxation de ce problme dans laquelle il est possible de produire des routes avec des cycles de longueur trois ou plus. Ceci est complt par des nouvelles coupes qui permettent de rduire encore davantage le saut dintgralit en mme temps que de dfavoriser lapparition de cycles dans les routes. Ces rsultats suggrent que cette mthode fournit la meilleure mthode exacte pour le PLRC. Dans le chapitre 5, on introduit une nouvelle mthode heuristique pour le PLRC. Premirement, on dmarre une mthode randomise de type GRASP pour trouver un premier ensemble de solutions de bonne qualit. Les solutions de cet ensemble sont alors combines de faon les amliorer. Finalement, on dmarre une mthode de type dtruir et rparer base sur la rsolution dun nouveau modle de localisation et raffectation qui gnralise le problme de raffectaction [48].
Resumo:
Navement peru, le processus dvolution est une succession dvnements de duplication et de mutations graduelles dans le gnome qui mnent des changements dans les fonctions et les interactions du protome. La famille des hydrolases de guanosine triphosphate (GTPases) similaire Ras constitue un bon modle de travail afin de comprendre ce phnomne fondamental, car cette famille de protines contient un nombre limit dlments qui diffrent en fonctionnalit et en interactions. Globalement, nous dsirons comprendre comment les mutations singulires au niveau des GTPases affectent la morphologie des cellules ainsi que leur degr dimpact sur les populations asynchrones. Mon travail de matrise vise classifier de manire significative diffrents phnotypes de la levure Saccaromyces cerevisiae via lanalyse de plusieurs critres morphologiques de souches exprimant des GTPases mutes et natives. Notre approche base de microscopie et danalyses bioinformatique des images DIC (microscopie dinterfrence diffrentielle de contraste) permet de distinguer les phnotypes propres aux cellules natives et aux mutants. Lemploi de cette mthode a permis une dtection automatise et une caractrisation des phnotypes mutants associs la sur-expression de GTPases constitutivement actives. Les mutants de GTPases constitutivement actifs Cdc42 Q61L, Rho5 Q91H, Ras1 Q68L et Rsr1 G12V ont t analyss avec succs. En effet, limplmentation de diffrents algorithmes de partitionnement, permet danalyser des donnes qui combinent les mesures morphologiques de population native et mutantes. Nos rsultats dmontrent que lalgorithme Fuzzy C-Means performe un partitionnement efficace des cellules natives ou mutantes, o les diffrents types de cellules sont classifis en fonction de plusieurs facteurs de formes cellulaires obtenus partir des images DIC. Cette analyse dmontre que les mutations Cdc42 Q61L, Rho5 Q91H, Ras1 Q68L et Rsr1 G12V induisent respectivement des phnotypes amorphe, allong, rond et large qui sont reprsents par des vecteurs de facteurs de forme distincts. Ces distinctions sont observes avec diffrentes proportions (morphologie mutante / morphologie native) dans les populations de mutants. Le dveloppement de nouvelles mthodes automatises danalyse morphologique des cellules natives et mutantes savre extrmement utile pour ltude de la famille des GTPases ainsi que des rsidus spcifiques qui dictent leurs fonctions et rseau dinteraction. Nous pouvons maintenant envisager de produire des mutants de GTPases qui inversent leur fonction en ciblant des rsidus divergents. La substitution fonctionnelle est ensuite dtecte au niveau morphologique grce notre nouvelle stratgie quantitative. Ce type danalyse peut galement tre transpos dautres familles de protines et contribuer de manire significative au domaine de la biologie volutive.
Resumo:
Parmi les mthodes destimation de paramtres de loi de probabilit en statistique, le maximum de vraisemblance est une des techniques les plus populaires, comme, sous des conditions legres, les estimateurs ainsi produits sont consistants et asymptotiquement efficaces. Les problmes de maximum de vraisemblance peuvent tre traits comme des problmes de programmation non linaires, ventuellement non convexe, pour lesquels deux grandes classes de mthodes de rsolution sont les techniques de rgion de confiance et les mthodes de recherche linaire. En outre, il est possible dexploiter la structure de ces problmes pour tenter dacclerer la convergence de ces mthodes, sous certaines hypothses. Dans ce travail, nous revisitons certaines approches classiques ou rcemment developpes en optimisation non linaire, dans le contexte particulier de lestimation de maximum de vraisemblance. Nous dveloppons galement de nouveaux algorithmes pour rsoudre ce problme, reconsidrant diffrentes techniques dapproximation de hessiens, et proposons de nouvelles mthodes de calcul de pas, en particulier dans le cadre des algorithmes de recherche linaire. Il sagit notamment dalgorithmes nous permettant de changer dapproximation de hessien et dadapter la longueur du pas dans une direction de recherche fixe. Finalement, nous valuons lefficacit numrique des mthodes proposes dans le cadre de lestimation de modles de choix discrets, en particulier les modles logit mlangs.
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.
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:
Les algorithmes d'apprentissage profond forment un nouvel ensemble de mthodes puissantes pour l'apprentissage automatique. L'ide est de combiner des couches de facteurs latents en hierarchies. Cela requiert souvent un cot computationel plus elev et augmente aussi le nombre de paramtres du modle. Ainsi, l'utilisation de ces mthodes sur des problmes plus grande chelle demande de rduire leur cot et aussi d'amliorer leur rgularisation et leur optimization. Cette thse adresse cette question sur ces trois perspectives. Nous tudions tout d'abord le problme de rduire le cot de certains algorithmes profonds. Nous proposons deux mthodes pour entrainer des machines de Boltzmann restreintes et des auto-encodeurs dbruitants sur des distributions sparses haute dimension. Ceci est important pour l'application de ces algorithmes pour le traitement de langues naturelles. Ces deux mthodes (Dauphin et al., 2011; Dauphin and Bengio, 2013) utilisent l'chantillonage par importance pour chantilloner l'objectif de ces modles. Nous observons que cela rduit significativement le temps d'entrainement. L'accleration atteint 2 ordres de magnitude sur plusieurs bancs d'essai. Deuximement, nous introduisont un puissant rgularisateur pour les mthodes profondes. Les rsultats exprimentaux dmontrent qu'un bon rgularisateur est crucial pour obtenir de bonnes performances avec des gros rseaux (Hinton et al., 2012). Dans Rifai et al. (2011), nous proposons un nouveau rgularisateur qui combine l'apprentissage non-supervis et la propagation de tangente (Simard et al., 1992). Cette mthode exploite des principes gometriques et permit au moment de la publication d'atteindre des rsultats l'tat de l'art. Finalement, nous considrons le problme d'optimiser des surfaces non-convexes haute dimensionalit comme celle des rseaux de neurones. Tradionellement, l'abondance de minimum locaux tait considr comme la principale difficult dans ces problmes. Dans Dauphin et al. (2014a) nous argumentons partir de rsultats en statistique physique, de la thorie des matrices alatoires, de la thorie des rseaux de neurones et partir de rsultats exprimentaux qu'une difficult plus profonde provient de la prolifration de points-selle. Dans ce papier nous proposons aussi une nouvelle mthode pour l'optimisation non-convexe.
Resumo:
This paper proposes and investigates a metaheuristic tabu search algorithm (TSA) that generates optimal or near optimal solutions sequences for the feedback length minimization problem (FLMP) associated to a design structure matrix (DSM). The FLMP is a non-linear combinatorial optimization problem, belonging to the NP-hard class, and therefore finding an exact optimal solution is very hard and time consuming, especially on medium and large problem instances. First, we introduce the subject and provide a review of the related literature and problem definitions. Using the tabu search method (TSM) paradigm, this paper presents a new tabu search algorithm that generates optimal or sub-optimal solutions for the feedback length minimization problem, using two different neighborhoods based on swaps of two activities and shifting an activity to a different position. Furthermore, this paper includes numerical results for analyzing the performance of the proposed TSA and for fixing the proper values of its parameters. Then we compare our results on benchmarked problems with those already published in the literature. We conclude that the proposed tabu search algorithm is very promising because it outperforms the existing methods, and because no other tabu search method for the FLMP is reported in the literature. The proposed tabu search algorithm applied to the process layer of the multidimensional design structure matrices proves to be a key optimization method for an optimal product development.
