Spelling suggestions: "subject:"heuristique."" "subject:"euristique.""
121 |
Approches de modélisation et d'optimisation pour la conception d'un système interactif d'aide au déplacement dans un hypermarchéHadj Khalifa, Ismahène 16 June 2011 (has links) (PDF)
Les travaux présentés dans cette thèse ont porté sur l'étude de faisabilité technique et logicielle du système i-GUIDE, système interactif de guidage des personnes dans les hypermarchés. Nous avons détaillé l'analyse fonctionnelle du besoin du système. Ensuite, nous avons étudié l'impact de l'intégration du système dans le magasin à travers le diagramme BPMN. Nous avons opté pour l'approche UML pour décrire les principales fonctionnalités de notre système ainsi que les objets nécessaires pour son bon fonctionnement. Une architecture du système i-GUIDE, basée sur la technologie RFID avec une application sous Android, a été présentée. Par ailleurs, nous avons proposé des approches d'optimisation de parcours dans un hypermarché basées sur la méthode de recherche tabou pour deux problèmes. Pour le premier problème, nous avons choisi le critère de la plus courte distance pour la détermination du chemin et pour le deuxième nous avons ajouté une contrainte de temps pour des articles en promotion. Avant de chercher le chemin le plus court à parcourir pour trouver les articles existants dans la liste de courses, nous avons proposé une méthode pour ladétermination des distances entre les articles de l'hypermarché pris deux à deux
|
122 |
Isomorphisme Inexact de Graphes par Optimisation ÉvolutionnaireBärecke, Thomas 22 October 2009 (has links) (PDF)
L'isomorphisme inexact de graphes est un problème crucial pour la définition d'une distance entre graphes, préalable nécessaire à une multitude d'applications allant de l'analyse d'images à des applications biomédicales en passant par la reconnaissance optique de caractères. Ce problème est encore plus complexe que celui de l'isomorphisme exact. Alors que ce dernier est un problème de décision de complexité au moins de classe P et qui ne s'applique qu'à des graphes exactement identiques, l'isomorphisme inexact est un problème combinatoire de complexité de classe NP qui permet de prendre en compte des perturbations dues au bruit, qui apparaissent fréquemment dans les applications réelles. Dans ce cadre, nous choisissons d'étudier une solution basée sur les algorithmes génétiques pouvant être appliquée à l'isomorphisme exact et inexact. Nous proposons des opérateurs de croisement généraux pour tout problème représenté par un codage de permutation, ainsi que des opérateurs spécifiques à l'isomorphisme de graphes qui exploitent une heuristique gloutonne. Nous réalisons une étude exhaustive pour comparer ces opérateurs avec les opérateurs existants, soulignant leurs propriétés, avantages et inconvénients respectifs. Nous étudions par ailleurs plusieurs pistes d'amélioration de l'algorithme, en théorie ou en pratique, considérant successivement les objectifs d'accélération de l'exécution, d'augmentation de la précision et de garantie de résultat optimal. Nous proposons pour cela de combiner l'approche proposée avec d'autres techniques telles que des heuristiques générales comme la recherche locale, des heuristiques dédiées comme l'algorithme A*, et des outils pratiques comme la parallélisation. Ces travaux conduisent à la définition d'une méthode générique pour la résolution de tous les problèmes d'isomorphismes de graphes, qu'il s'agisse d'isomorphismes exact ou inexact, d'isomorphismes de graphes de même taille ou d'isomorphismes de sous-graphes. Nous illustrons enfin la validité de cette solution générale par trois applications concrètes issues de domaines différents, la recherche d'images et la chimie, qui présentent chacune des caractéristiques spécifiques, utilisant des graphes attribués ou non, soumis aux perturbations plutôt structurelles ou au niveau d'attributs.
|
123 |
Résolution par satisfation de contraintes appliquée à l'aide à la décision en conception architecturaleChenouard, Raphaël 01 December 2007 (has links) (PDF)
La conception architecturale de systèmes mécaniques et énergétiques permet d'étudier la faisabilité de concepts préalablement choisis pendant la phase de recherche de concepts. Elle fait partie de la phase de conception préliminaire et son achèvement vise à définir l'architecture globale qui sera étudiée pendant la phase de conception détaillée d'un produit. Les principales caractéristiques d'un produit (dimensions, choix de composants, de formes, de topologies ou de matériaux) sont alors fondamentales à ce stade de la conception. La conception architecturale nécessite aussi la prise en compte des comportements physiques et des interactions du produit, de ses composants et des milieux extérieurs, de critères économiques, environnementaux, etc. suivant les exigences du cahier des charges fonctionnel. Le concepteur définit un modèle mathématique exprimant cette connaissance liée au produit. Ce modèle peut être traité à l'aide d'un solveur de Problèmes de Satisfaction de Contraintes numériques (CSP). Ce type de solveur traite de manière générique des problèmes formulés à l'aide de contraintes, de variables et de domaines. Nous proposons de nouveaux algorithmes et de nouvelles heuristiques qui prennent en compte des besoins spécifiques au concepteur en conception préliminaire, comme : la classification des variables, les précisions relatives aux valeurs de certaines variables, les contraintes par morceaux. Les études de faisabilité de plusieurs systèmes mécaniques et énergétiques ont été réalisées avec succès. Les nouveaux algorithmes ont permis de diminuer significativement les temps de calculs, mais ils ont aussi permis d'améliorer la qualité des solutions calculées au regard des besoins du concepteur.
|
124 |
Sélection de modèle pour la classification non supervisée. Choix du nombre de classes.Baudry, Jean-Patrick 03 December 2009 (has links) (PDF)
Le cadre principal de cette thèse est la classification non supervisée, traitée par une approche statistique dans le cadre des modèles de mélange. Plus particulièrement, nous nous intéressons au choix du nombre de classes et au critère de sélection de modèle ICL. Une approche fructueuse de son étude théorique consiste à considérer un contraste adapté à la classification non supervisée : ce faisant, un nouvel estimateur ainsi que de nouveaux critères de sélection de modèle sont proposés et étudiés. Des solutions pratiques pour leur calcul s'accompagnent de retombées positives pour le calcul du maximum de vraisemblance dans les modèles de mélange. La méthode de l'heuristique de pente est appliquée pour la calibration des critères pénalisés considérés. Aussi les bases théoriques en sont-elles rappelées en détails, et deux approches pour son application sont étudiées. Une autre approche de la classification non supervisée est considérée : chaque classe peut être modélisée elle-même par un mélange. Une méthode est proposée pour répondre notamment à la question du choix des composantes à regrouper. Enfin, un critère est proposé pour permettre de lier le choix du nombre de composantes, lorsqu'il est identifié au nombre de classes, à une éventuelle classification externe connue a priori.
|
125 |
Prise de décision multiattribut avec le modèle GAIDubus, Jean-Philippe 23 September 2010 (has links) (PDF)
Les réseaux GAI sont une représentation graphique compacte et expressive des préférences d'un décideur en Décision Multiattribut, c'est-à-dire dans des situations où les alternatives sur lesquelles portent les choix du décideur sont décrites à l'aide d'un ensemble d'attributs (de caractéristiques). L'exploitation de leur structure graphique permet de définir des procédures efficaces d'élicitation de préférences (détermination des préférences à l'aide de questionnaires) ainsi que des algorithmes assez performants de prise de décision (calcul de l'alternative préférée du décideur ou des k meilleures alternatives). Le but de cette thèse est double. Tout d'abord elle vise à étendre les algorithmes de prise de décision dans des cas où les réseaux GAI sont denses, c'est-à-dire dans des situations où leur structure ne permet pas aux algorithmes de l'état de l'art de s'exécuter en un temps raisonnable. Pour cela, une nouvelle méthode de triangulation approchée a été développée, qui produit des réseaux GAI approchés sur lesquels des mécanismes d'inférence adaptés permettent d'obtenir les alternatives optimales des réseaux GAI d'origine. Ensuite, elle propose de nouvelles méthodes d'inférence en Décision multicritère. Plus précisément, elle propose des approches pour déterminer des frontières de Pareto (exactes ou approchées avec garantie de performance) ou des frontières de Lorenz. Elle prop ose également des algorithmes pour déterminer des solutions optimales dans les cas où les critères peuvent être agrégés via des opérateurs tels que OWA (Ordered Weighted Average), l'intégrale de Choquet ou bien encore la norme de Tchebyche ff.
|
126 |
Vers un Model Checking avec accélération plate des systèmes hétérogènesBardin, Sébastien 20 October 2005 (has links) (PDF)
Cette thèse s'inscrit dans le cadre de la vérification formelle de systèmes informatiques. Plus exactement nous nous intéressons au calcul de l'ensemble d'accessibilité d'automates étendus par des variables à domaines infinis. Bien que cet ensemble ne soit pas récursif en général, des techniques à base d'accélération permettent de le calculer en pratique. Cependant ces méthodes sont encore mal connues. Nous nous intéressons à l'étude de l'accélération, des points de vue théorique, algorithmique et implantation logicielle.
|
127 |
Ordonnancement cyclique multi-produits des lignes de traitement de surface : Méthodes exactes et approchéesEl Amraoui, Adnen 12 July 2011 (has links) (PDF)
Cette thèse s'intéresse au fonctionnement cyclique multi-produits des ateliers de traitement de surface, et au problème d'ordonnancement associé (HSP), caractérisé par des contraintes fortes et atypiques, dont certaines sont liées aux ressources de transport. Dans le cas de productions en grandes séries, une commande cyclique de ces systèmes est particulièrement adaptée, permettant notamment de réduire la combinatoire de résolution, et sous réserve que les ratios de produits soient connus à l'avance. Notre objectif est de trouver le meilleur ordonnancement des tâches de traitement et de transport en un temps raisonnable. Pour cela, nous proposons une première approche, basée sur un modèle linéaire et une méthode de résolution arborescente de type séparation et évaluation. Nous présentons des modélisations pour différentes extensions du problème dit de base et nous fournissons des exemples illustratifs et des résultats sur des benchmarks. Par la suite et compte tenu de l'analyse de la littérature relative aux ordonnancements cycliques mono-produit et multi-produits, nous proposons tout d'abord une heuristique dédiée au cas multi-produits étudié, et basée sur un algorithme de liste. Avec ce dernier, nous obtenons un ordonnancement cyclique dont le degré du cycle n'est pas fixé au préalable. Enfin, nous présentons une deuxième modélisation approchée sous la forme d'un algorithme génétique pour résoudre un HSP 2-cyclique. Ces différents modèles sont validés par des tests sur des benchmarks de la littérature pour lesquels nous avons obtenus des résultats prometteurs. Nous terminons par une analyse critique des avantages et inconvénients des modèles élaborés et par quelques propositions de perspectives pour ce travail.
|
128 |
Analyse bayésienne et élicitation d’opinions d’experts en analyse de risques et particulièrement dans le cas de l’amiante chrysotilePietrocatelli, Simon 12 1900 (has links)
L’appréciation de la puissance cancérogène des fibres d’amiante chrysotile
repose en grande partie sur des jugements subjectifs et incertains des
experts et des analystes en raison des résultats hétérogènes et équivoques
d’études épidémiologiques et toxicologiques sérieuses. L’approche
probabiliste bayésienne en évaluation de risques peut formaliser l’impact des
jugements subjectifs et de leurs incertitudes sur les estimations de risques,
mais elle est encore peu utilisée en santé publique. Le présent travail
examine la possibilité d’appliquer l’approche bayésienne dans une récente
élicitation d’opinions d’experts pour estimer la toxicité du chrysotile, le degré
de consensus et de divergence, ainsi que les niveaux d’incertitude des
experts. Les estimations des experts concordaient assez bien sur la
différence de toxicité entre chrysotile et amphiboles pour les mésothéliomes.
Pour le cancer du poumon, les évaluations probabilistes étaient bien plus
disparates. Dans ce cas, les jugements des experts semblaient influencés à
différents degrés par des biais heuristiques, surtout les heuristiques d’affect
et d’ancrage liés à la controverse du sujet et à l’hétérogénéité des données.
Une méthodologie rigoureuse de préparation des experts à l’exercice
d’élicitation aurait pu réduire l’impact des biais et des heuristiques sur le
panel. / Characterizing the carcinogenic potency of chrysotile asbestos fibres relies a
great deal on subjective and uncertain judgements by experts and analysts,
given heterogeneous and equivocal results of important epidemiological and
toxicological studies. The probabilistic Bayesian approach in risk
assessments quantifies these subjective judgements and their uncertainties,
along with their impact on risk estimations, but it is rarely used in the public
health context. This report examines how the Bayesian approach could have
been applied to a recent elicitation of experts’ opinions to estimate the toxicity
of chrysotile asbestos, the degree of convergence and divergence, as well as
the uncertainty levels of these experts. The experts’ estimations on the
relative toxicity of chrysotile and amphibole asbestos were similar in the case
of mesothelioma. However, in the case of lung cancer, the heterogeneity of
the studies resulted in diverging and incompatible probabilistic evaluations.
The experts’ judgements seemed influenced by heuristic biases, particularly
the affect and anchor heuristics associated with a controversial topic and to
heterogeneous data. If the elicitation process had been prepared following a
rigorous methodology, these heuristics and biases could have been mitigated.
|
129 |
Optimisation de stratégies de fusion pour la reconnaissance de visages 3D.Ben Soltana, Wael 11 December 2012 (has links) (PDF)
La reconnaissance faciale (RF) est un domaine de recherche très actif en raison de ses nombreuses applications dans le domaine de la vision par ordinateur en général et en biométrie en particulier. Cet intérêt est motivé par plusieurs raisons. D'abord, le visage est universel. Ensuite, il est le moyen le plus naturel par les êtres humains de s'identifier les uns des autres. Enfin, le visage en tant que modalité biométrique est présente un caractère non intrusif, ce qui le distingue d'autres modalités biométriques comme l'iris ou l'emprunte digitale. La RF représente aussi des défis scientifiques importants. D'abord parce que tous les visages humains ont des configurations similaires. Ensuite, avec les images faciales 2D que l'on peut acquérir facilement, la variation intra-classe, due à des facteurs comme le changement de poses et de conditions d'éclairage, les variations d'expressions faciales, le vieillissement, est bien plus importante que la variation inter-classe.Avec l'arrivée des systèmes d'acquisition 3D capables de capturer la profondeur d'objets, la reconnaissance faciale 3D (RF 3D) a émergé comme une voie prometteuse pour traiter les deux problèmes non résolus en 2D, à savoir les variations de pose et d'éclairage. En effet, les caméras 3D délivrent généralement les scans 3D de visages avec leurs images de texture alignées. Une solution en RF 3D peut donc tirer parti d'une fusion avisée d'informations de forme en 3D et celles de texture en 2D. En effet, étant donné que les scans 3D de visage offrent à la fois les surfaces faciales pour la modalité 3D pure et les images de texture 2D alignées, le nombre de possibilités de fusion pour optimiser le taux de reconnaissance est donc considérable. L'optimisation de stratégies de fusion pour une meilleure RF 3D est l'objectif principal de nos travaux de recherche menés dans cette thèse.Dans l'état d'art, diverses stratégies de fusion ont été proposées pour la reconnaissance de visages 3D, allant de la fusion précoce "early fusion" opérant au niveau de caractéristiques à la fusion tardive "late fusion" sur les sorties de classifieurs, en passant par de nombreuses stratégies intermédiaires. Pour les stratégies de fusion tardive, nous distinguons encore des combinaisons en parallèle, en cascade ou multi-niveaux. Une exploration exhaustive d'un tel espace étant impossible, il faut donc recourir à des solutions heuristiques qui constituent nos démarches de base dans le cadre des travaux de cette thèse.En plus, en s'inscrivant dans un cadre de systèmes biométriques, les critères d'optimalité des stratégies de fusion restent des questions primordiales. En effet, une stratégie de fusion est dite optimisée si elle est capable d'intégrer et de tirer parti des différentes modalités et, plus largement, des différentes informations extraites lors du processus de reconnaissance quelque soit leur niveau d'abstraction et, par conséquent, de difficulté.Pour surmonter toutes ces difficultés et proposer une solution optimisée, notre démarche s'appuie d'une part sur l'apprentissage qui permet de qualifier sur des données d'entrainement les experts 2D ou 3D, selon des critères de performance comme ERR, et d'autre part l'utilisation de stratégie d'optimisation heuristique comme le recuit simulé qui permet d'optimiser les mélanges des experts à fusionner. [...]
|
130 |
Conception et évaluation d'outils décisionnels pour des systèmes réactifs d'aide à la mobilitéRen, Libo 05 October 2012 (has links) (PDF)
Dans le cadre de cette thèse, nous nous intéressons au traitement des problèmes d'optimisation combinatoire liés à la conception d'outils de gestion des systèmes de véhicules partagés. Ces problèmes sont proches des problèmes de collecte et de livraison. Après avoir réalisé une étude théorique sur des problèmes d'optimisation combinatoire autour du transport et des méthodes de résolutions, nous nous sommes intéressés ici à trois problèmes particuliers : le PPRV, le PPRV-PM et le PPRV-T. Le premier problème est le Problème de Planification du Redéploiement de Véhicules partagés (PPRV). C'est une extension du One-commodity Pickup-and-Delivery Problem (1-PDP) car les véhicules partagés sont indifférenciés. Nous avons proposé un modèle linéaire et une heuristique utilisant le schéma hybride ILS/VND. L'approche développée repose sur la stratégie " route-first, cluster-second " : on commence par construire une tournée géante, puis on l'améliore par une procédure de perturbation et une recherche locale. Pendant la recherche locale, la contrainte de capacité des véhicules est momentanément relaxée et progressivement restaurée ; la tournée géante obtenue est ensuite transformée en plusieurs tournées à l'aide de la procédure Split. Les deux problèmes suivants sont considérés comme des extensions du PPRV en autorisant des livraisons partielles : PPRV avec Passage Multiple (PPRV-PM) et PPRV avec Transfert d'objets (PPRV-T). Nous proposons une approche de type " divide-first, route-second " pour la résolution du PPRV-PM. Elle consiste à effectuer d'abord un fractionnement de la demande, puis la résoudre à l'aide d'un schéma hybride de type GRASP/VND. Le PPRV-T étend le PPRV-PM au transfert d'objets entre les transporteurs lors du passage sur un sommet. Nous avons reformulé le PPRV-T comme un problème de multi-flots couplés sur un réseau dynamique. Nous avons proposé une méthode d'insertion basée sur cette modélisation.
|
Page generated in 0.0352 seconds