Descripteur
Termes IGN > 1- Outils - instruments et méthodes > méthode > méthode heuristique
méthode heuristiqueSynonyme(s)méthode de recherche heuristique |
Documents disponibles dans cette catégorie (29)
Ajouter le résultat dans votre panier
Visionner les documents numériques
Affiner la recherche Interroger des sources externes
Etendre la recherche sur niveau(x) vers le bas
Automatic revision of the control knowledge used by trial and error methods: Application to cartographic generalisation / Patrick Taillandier in Applied soft computing, vol 11 n° 2 (March 2011)
[article]
Titre : Automatic revision of the control knowledge used by trial and error methods: Application to cartographic generalisation Type de document : Article/Communication Auteurs : Patrick Taillandier , Auteur ; Cécile Duchêne , Auteur ; Alexis Drogoul, Auteur Année de publication : 2011 Article en page(s) : pp 2818 - 2832 Note générale : bibliographie Langues : Anglais (eng) Descripteur : [Termes IGN] connaissance thématique
[Termes IGN] généralisation cartographique automatisée
[Termes IGN] instance
[Termes IGN] méthode heuristique
[Vedettes matières IGN] GénéralisationMots-clés libres : Knowledge revision Problem solving Trial and error method Cartographic generalisation Résumé : (auteur) Humans frequently have to face complex problems. A classical approach to solve them is to search the solution by means of a trial and error method. This approach is often used with success by artificial systems. However, when facing highly complex problems, it becomes necessary to introduce control knowledge (heuristics) in order to limit the number of trials needed to find the optimal solution. Unfortunately, acquiring and maintaining such knowledge can be fastidious. In this paper, we propose an automatic knowledge revision approach for systems based on a trial and error method. Our approach allows to revise the knowledge off-line by means of experiments. It is based on the analysis of solved instances of the considered problem and on the exploration of the knowledge space. Indeed, we formulate the revision problem as a search problem: we search the knowledge set that maximises the performances of the system on a sample of problem instances. Our knowledge revision approach has been implemented for a real-world industrial application: automated cartographic generalisation, a complex task of the cartography domain. In this implementation, we demonstrate that our approach improves the quality of the knowledge and thus the performance of the system. Numéro de notice : A2011-581 Affiliation des auteurs : IGN+Ext (1940-2011) Thématique : GEOMATIQUE Nature : Article nature-HAL : ArtAvecCL-RevueIntern DOI : 10.1016/j.asoc.2010.11.012 Date de publication en ligne : 27/11/2010 En ligne : http://dx.doi.org/10.1016/j.asoc.2010.11.012 Format de la ressource électronique : URL article Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=83482
in Applied soft computing > vol 11 n° 2 (March 2011) . - pp 2818 - 2832[article]Area aggregation in map generalisation by mixed-integer programming / Jan‐Henrik Haunert in International journal of geographical information science IJGIS, vol 24 n°11-12 (december 2010)
[article]
Titre : Area aggregation in map generalisation by mixed-integer programming Type de document : Article/Communication Auteurs : Jan‐Henrik Haunert, Auteur ; A. Wolff, Auteur Année de publication : 2010 Article en page(s) : pp 1871 - 1897 Note générale : Bibliographie Langues : Anglais (eng) Descripteur : [Termes IGN] agrégation de données
[Termes IGN] analyse combinatoire (maths)
[Termes IGN] base de données ATKIS
[Termes IGN] base de données topographiques
[Termes IGN] distance
[Termes IGN] généralisation cartographique automatisée
[Termes IGN] graphe
[Termes IGN] jeu de données localisées
[Termes IGN] méthode heuristique
[Termes IGN] optimisation (mathématiques)
[Termes IGN] programmation par contraintes
[Termes IGN] rédaction cartographique
[Termes IGN] sémiologie graphique
[Vedettes matières IGN] GénéralisationRésumé : (Auteur) Topographic databases normally contain areas of different land cover classes, commonly defining a planar partition, that is, gaps and overlaps are not allowed. When reducing the scale of such a database, some areas become too small for representation and need to be aggregated. This unintentionally but unavoidably results in changes of classes. In this article we present an optimisation method for the aggregation problem. This method aims to minimise changes of classes and to create compact shapes, subject to hard constraints ensuring aggregates of sufficient size for the target scale. To quantify class changes we apply a semantic distance measure. We give a graph theoretical problem formulation and prove that the problem is NP-hard, meaning that we cannot hope to find an efficient algorithm. Instead, we present a solution by mixed-integer programming that can be used to optimally solve small instances with existing optimisation software. In order to process large datasets, we introduce specialised heuristics that allow certain variables to be eliminated in advance and a problem instance to be decomposed into independent sub-instances. We tested our method for a dataset of the official German topographic database ATKIS with input scale 1:50,000 and output scale 1:250,000. For small instances, we compare results of this approach with optimal solutions that were obtained without heuristics. We compare results for large instances with those of an existing iterative algorithm and an alternative optimisation approach by simulated annealing. These tests allow us to conclude that, with the defined heuristics, our optimisation method yields high-quality results for large datasets in modest time. Numéro de notice : A2010-554 Affiliation des auteurs : non IGN Thématique : GEOMATIQUE Nature : Article DOI : 10.1080/13658810903401008 En ligne : https://doi.org/10.1080/13658810903401008 Format de la ressource électronique : URL article Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=30746
in International journal of geographical information science IJGIS > vol 24 n°11-12 (december 2010) . - pp 1871 - 1897[article]Réservation
Réserver ce documentExemplaires(2)
Code-barres Cote Support Localisation Section Disponibilité 079-2010071 RAB Revue Centre de documentation En réserve L003 Disponible 079-2010072 RAB Revue Centre de documentation En réserve L003 Disponible Finding shortest paths on real road networks: the case for A* / W. Zeng in International journal of geographical information science IJGIS, vol 23 n°3-4 (march - april 2009)
[article]
Titre : Finding shortest paths on real road networks: the case for A* Type de document : Article/Communication Auteurs : W. Zeng, Auteur Année de publication : 2009 Article en page(s) : pp 531 - 543 Note générale : Bibliographie Langues : Anglais (eng) Descripteur : [Vedettes matières IGN] Analyse spatiale
[Termes IGN] chemin le plus court, algorithme du
[Termes IGN] Los Angeles
[Termes IGN] méthode heuristique
[Termes IGN] réseau de transport
[Termes IGN] réseau routier
[Termes IGN] système d'information géographiqueRésumé : (Auteur) The problem of identifying the shortest path along a road network is a fundamental problem in network analysis, ranging from route guidance in a navigation system to solving spatial allocation problems. Since this type of problem is solved so frequently, it is important to craft an approach that is as efficient as possible. Based upon past research, it is generally accepted that several efficient implementations of the Dijkstra algorithm are the fastest at optimally solving the 'one-to-one' shortest path problem (Cherkassky et al. 1996). We show that the most efficient state-of-the-art implementations of Dijkstra can be improved by taking advantage of network properties associated with GIS-sourced data. The results of this paper, derived from tests of different algorithmic approaches on real road networks, will be extremely valuable for application developers and researchers in the GIS community. Copyright Taylor & Francis Numéro de notice : A2009-162 Affiliation des auteurs : non IGN Thématique : GEOMATIQUE Nature : Article DOI : 10.1080/13658810801949850 En ligne : https://doi.org/10.1080/13658810801949850 Format de la ressource électronique : URL article Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=29792
in International journal of geographical information science IJGIS > vol 23 n°3-4 (march - april 2009) . - pp 531 - 543[article]Réservation
Réserver ce documentExemplaires(2)
Code-barres Cote Support Localisation Section Disponibilité 079-09021 RAB Revue Centre de documentation En réserve L003 Disponible 079-09022 RAB Revue Centre de documentation En réserve L003 Disponible
Titre : Heuristic revision by heuristic space exploration Type de document : Article/Communication Auteurs : Patrick Taillandier , Auteur Editeur : New York : Institute of Electrical and Electronics Engineers IEEE Année de publication : 2009 Conférence : KSE 2009, International Conference on Knowledge and Systems Engineering 13/10/2009 17/10/2009 Hanoï Viet Nam Proceedings IEEE Importance : pp 55 - 60 Note générale : bibliographie Langues : Français (fre) Descripteur : [Termes IGN] méthode heuristique
[Vedettes matières IGN] GénéralisationRésumé : (auteur) Heuristics are often used to solve complex problems. Indeed, such problem-specific knowledge, when pertinent, helps to efficiency find good solutions to complex problems. Unfortunately, acquiring and maintaining a heuristic set can be fastidious. In order to face this problem, an approach consists in revising the heuristic sets by means of experiments. In this paper, we are interested in a specific revision method of this type based on the exploration of the heuristic space. The principle of this method is to revise the heuristic set by searching among all possible heuristics the ones that maximize an evaluation function. In this context, we propose a revision approach, dedicated to heuristics represented by production rules, based on the reduction of the search space and on a filtered local search. We present an experiment we carried out in an application domain where heuristics are widely used: cartographic generalization. Numéro de notice : C2009-065 Affiliation des auteurs : COGIT (1988-2011) Autre URL associée : vers HAL Thématique : GEOMATIQUE Nature : Communication nature-HAL : ComAvecCL&ActesPubliésIntl DOI : 10.1109/KSE.2009.31 Date de publication en ligne : 28/12/2009 En ligne : https://doi.org/10.1109/KSE.2009.31 Format de la ressource électronique : URL article Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=102370 Révision automatique des connaissances guidant l'exploration informée d'arbres d'états / Patrick Taillandier (2008)
Titre : Révision automatique des connaissances guidant l'exploration informée d'arbres d'états : application au contexte de la généralisation de données géographiques Type de document : Thèse/HDR Auteurs : Patrick Taillandier , Auteur ; Alexis Drogoul, Directeur de thèse ; Cécile Duchêne , Encadrant Editeur : Champs/Marne : Université de Marne-la-Vallée Année de publication : 2008 Importance : 415 p. Format : 21 x 30 cm Note générale : Bibliographie
Thèse pour obtenir le grade de docteur de l'université de Paris-Est, spécialité informatiqueLangues : Français (fre) Descripteur : [Termes IGN] arbre (mathématique)
[Termes IGN] généralisation automatique de données
[Termes IGN] méthode heuristique
[Termes IGN] révision des connaissances
[Termes IGN] système à base de connaissances
[Termes IGN] système multi-agents
[Vedettes matières IGN] GénéralisationIndex. décimale : THESE Thèses et HDR Résumé : (Auteur) Ce travail de thèse traite de la révision automatique des connaissances contenues dans les systèmes fonctionnant par exploration informée d'arbres d'états. Ces systèmes, de par leur performance, sont employés dans de nombreux domaines applicatifs. En particulier, des travaux ont proposés d'utiliser cette approche dans le cadre de l'automatisation de la généralisation de données géographiques. La généralisation de données géographique s'intéresse à la dérivation, à partir de données géographiques détaillées, de données moins détaillées adaptées à un besoin particulier (e.g. changement d'échelle). Son automatisation, enjeu majeur pour les agences cartographiques telles que l'Institut Géographique National (IGN), est particulièrement complexe. Les performances des systèmes basés sur l'exploration informée d'arbres d'états sont directement dépendantes de la qualité de leurs connaissances (heuristiques). Or, la définition et la mise à jour de ces dernières s'avèrent généralement fastidieuses. Dans le cadre de cette thèse, nous proposons une approche de révision hors ligne des connaissances basée sur le traçage du système et sur l'analyse de ces traces. Ces traces sont ainsi utilisées par un module de révision qui est chargé d'explorer l'espace des connaissances possibles et d'en modifier en conséquence les connaissances du système. Des outils de diagnostic en ligne de la qualité des connaissances permettent de déterminer quand déclencher le processus de révision hors ligne des connaissances. Pour chaque méthode et approche que nous présentons, une mise en oeuvre est détaillée et expérimentée dans le cadre de l'automatisation de la généralisation de données géographiques. Note de contenu : Contexte général
Objectifs de la thèse
Plan
Remarques sur le vocabulaire et les notations
1. Contexte applicatif : la généralisation de données géographiques
1.1 Introduction
1.2 La généralisation de données géographiques
1.2.1 Représentation numérique de l'information géographique
1.2.2 La généralisation de données géographiques
1.3 L'automatisation de la généralisation de données géographiques
1.3.1 Enjeu de l'automatisation de la généralisation
1.3.2 Problématique de l'automatisation de la généralisation
1.3.3 Séquence prédéfinie
1.3.4 Approches globales
1.3.5 Approches locales
1.4 Le modèle agent : un modèle de généralisation automatique fonctionnant par exploration informée d'arbres d'états
1.4.1 Principe général
1.4.2 Les contraintes
1.4.3 Cycle d'actions
1.4.4 Connaissances procédurales en jeu
1.5 Enjeu de la révision des connaissances procédurales dans les systèmes de généralisation fonctionnant par exploration informée d'arbres d'états
1.6 Objectif de la thèse
2. Problématique et approche générale
2.1 Introduction
2.2 Acquisition et révision automatique de connaissances
2.2.1 Acquisition et révision des connaissances en intelligence artificielle
2.2.2 Acquisition et révision des connaissances dans le cadre de la généralisation de données géographiques
2.2.3 Bilan
2.3 Révision par l’expérience des connaissances procédurales d'un système fonctionnant par exploration informée d'arbres d'états : formalisation
2.3.1 Système fonctionnant par exploration informée d'arbres d'états
2.3.2 Révision par l’expérience des connaissances procédurales
2.4 Révision par l’expérience des connaissances procédurales d'un système fonctionnant par exploration informée d'arbres d'états : problématiques
2.4.1 Problèmes lies au diagnostic des connaissances
2.4.2 Problèmes lies a l'acquisition de connaissances
2.4.3 Problèmes lies a la révision des connaissances
2.5 Approche et modèle généraux de révision des connaissances proposes
2.5.1 Approche générale proposée pour la révision des connaissances procédurales
2.5.2 Modélisation agent des connaissances
2.5.3 Application dans le cadre du modèle agent
2.6 Bilan
3. Constitution de l’expérience : production de traces d’exécution
3.1 Introduction
3.2 Choix de l'échantillon d'instances du problème utilise pour la révision des connaissances
3.2.1 Problématique du choix de l'échantillon utilise pour produire de l'expérience
3.2.2 Approche proposée de choix de l'échantillon de révision
3.2.3 Application de l'approche pour le système agent
3.3 Choix du jeu de connaissances utilise lors de la production de traces
3.3.1 Importance du jeu de connaissances choisi lors de la production de traces
3.3.2 Jeu de connaissances minimal pour le modèle agent
3.4 Construction des bases d'exemples
3.4.1 Introduction
3.4.2 Construction des bases d'exemples
3.4.3 Evaluation des jeux de mesures
3.4.4 Application pour le système agent
3.5 Bilan
4. Révision des connaissances procédurales par analyse des traces d’exécution
4.1 Introduction
4.2 Approche générale de révision par analyse
4.2.1 Problématiques liées au processus de révision par analyse
4.2.2 Présentation de l'approche générale de révision par analyse
4.3 Révision par analyse d'un groupe de connaissances
4.3.1 Introduction
4.3.2 Approche générique de révision par analyse d'un groupe de connaissances
4.3.3 Approche de révision par analyse pour les connaissances représentées sous forme de bases de règles de production
4.4 Bilan
5. Diagnostic en ligne de la qualité des connaissances procédurales
5.1 Introduction
5.2 Problématique du diagnostic en ligne de la qualité des connaissances procédurales
5.2.1 Difficultés du diagnostic en ligne
5.2.2 Problématique du diagnostic en ligne
5.3 Approche proposée
5.3.1 Principe
5.3.2 Analyse d'une instance résolue d'un problème d'optimisation
5.3.3 Analyse de l'historique
5.3.4 Evaluation qualitative du jeu de connaissances
5.3.5 Bilan sur l'approche de diagnostic proposée
5.4 Application pour le modèle agent
5.4.1 Les agents connaissance et l'agent diagnostic
5.4.2 Analyse du résultat d'une généralisation d'un agent géographique
5.4.3 Analyse de l'historique
5.5 Bilan
6. Expérimentation et évaluation du modèle complet de révision des connaissances et du module de diagnostic
6.1 Introduction
6.2 Contexte général des expérimentations
6.2.1 Données et types d'objets géographiques considérés : les groupements de bâtiments
6.2.2 Zone de révision des connaissances et zone de test
6.2.3 Jeux de connaissances initiaux définis
6.2.4 Choix des algorithmes d'apprentissage et d'exploration et de leurs paramètres pour les expérimentations
6.2.5 Implémentation
6.3 Expérimentation du modèle de révision des connaissances procédurales
6.3.1 Introduction
6.3.2 Révision de la connaissance relative à la validité des états
6.3.3 Révision des connaissances relatives à la restriction d'application des actions
6.3.4 Révision de la connaissance relative à l'optimalité des états
6.3.5 Révision de la connaissance relative à la fin de cycle
6.3.6 Révision des connaissances relatives à la priorité des contraintes
6.3.7 Révision des connaissances relatives à l'application des actions
6.3.8 Révision de l'ensemble des connaissances
6.3.9 Bilan
6.4 Expérimentation sur l'influence de l'échantillon de révision
6.4.1 Contexte de l'expérimentation
6.4.2 Résultats obtenus
6.4.3 Bilan de l'expérimentation
6.5 Expérimentation de l'approche d'évaluation des jeux de mesures
6.5.1 Contexte de l'expérimentation
6.5.2 Résultats obtenus
6.5.3 Bilan de l'expérimentation
6.6 Expérimentation du module de diagnostic
6.6.1 Contexte de l'expérimentation
6.6.2 Résultats obtenus
6.6.3 Bilan de l'expérimentation
6.7 Discussion sur les résultats
6.7.1 Evaluation des résultats
6.7.2 Difficultés posées
6.8 Bilan
CONCLUSIONNuméro de notice : 13661 Affiliation des auteurs : COGIT (1988-2011) Thématique : GEOMATIQUE/INFORMATIQUE Nature : Thèse française Note de thèse : Thèse de doctorat : informatique : Marne-la-Vallée : 2008 Organisme de stage : COGIT (IGN) nature-HAL : Thèse DOI : sans En ligne : https://hal.science/tel-00481927 Format de la ressource électronique : URL Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=45231 Exemplaires(1)
Code-barres Cote Support Localisation Section Disponibilité 13661-01 K325 Livre LASTIG Dépôt en unité Exclu du prêt Classified road detection from satellite images based on perceptual organization / J. Yang in International Journal of Remote Sensing IJRS, vol 28 n°19-20 (October 2007)PermalinkA shortest path algorithm with novel heuristics for dynamic transportation networks / B. Huang in International journal of geographical information science IJGIS, vol 21 n° 6-7 (july 2007)PermalinkOptimisation en traitement du signal et de l'image / Patrick Siarry (2007)PermalinkAd hoc shared-ride trip planning by mobile geosensor networks / Stephan Winter in International journal of geographical information science IJGIS, vol 20 n° 8 (september 2006)PermalinkScale-space for generalization of 3D buildings / Helmut Mayer in International journal of geographical information science IJGIS, vol 19 n° 8 - 9 (september 2005)Permalink7es Rencontres des Jeunes Chercheurs en Intelligence Artificielle [Plate-forme AFIA 2005] / Emmanuel Guéré (2005)PermalinkK-guarding of polyhedral terrain / B. Kaucic in International journal of geographical information science IJGIS, vol 18 n° 7 (november 2004)PermalinkLes cartes de la connaissance / Jean-Paul Bord (2004)PermalinkPermalinkRecherche opérationnelle et réseaux / G. Finke (2002)PermalinkSystème multi-agents d’aide à la photo-interprétation sur architecture multiprocesseur / Valéry Lefèvre (1994)PermalinkAutomation in photogrammetric block adjustment systems / Tapani Sarjakoski (1988)PermalinkA new heuristic search technique - algorithm SA / B. Zhang in IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI, vol 7 n° 1 (01/01/1985)Permalink