In this article, a hybrid heuristic algorithm is proposed to solve the Traveling Salesman Problem (TSP). This algorithm combines two main metaheuristics: optimization of multi-colony ant colonies (MACO) and Lin-Kernighan-Helsgaun (LKH). The proposed hybrid approach (MACO-LKH) is a so-called insertion and relay hybridization. It brings two major innovations: The first consists in replacing the static visibility function used in the MACO heuristic by the dynamic visibility function used in LKH. This has the consequence of avoiding long paths and favoring the choice of the shortest paths more quickly. Hence the term insertion hybridization. The second innovation consists in modifying the pheromone update strategy of MACO by that of the dynamic λ-opt mechanisms of LKH in order to optimize the solutions generated and save in execution time, hence the relay hybridization. The significance of the hybridization, is examined and validated on benchmark instances including small, medium, and large instance problems taken from the TSPlib library. The results are compared to four other state-of-the-art metaheuristic approaches. It results in that they are significantly outperformed by the proposed algorithm in terms of the quality of solutions obtained and execution time.
De nos jours, il existe un intérêt croissant pour les applications d'exploration de données et de recherche d'informations à partir de graphes de connaissances (KG). Cependant, ces derniers (KG) souffrent de plusieurs problèmes de qualité de données tels que la précision, la complétude et différents types d'erreurs. Dans DBpedia, il existe plusieurs problèmes liés à la qualité des données. Parmi eux, nous nous concentrons sur le suivant: plusieurs entités se trouvent dans des classes auxquelles elles n'appartiennent pas. Par exemple, la requête pour obtenir toutes les entités de la classe Person retourne aussi les entités de groupe, tandis que celles-ci devraient être dans la classe Group. Nous appelons ces entités "outliers". La découverte de ces entités mal classées est cruciale pour l'apprentissage et la compréhension des classes. Cet article propose une nouvelle méthode de détection des outliers qui permet de trouver ces entités. Nous définissons une mesure sémantique qui favorise les entités réelles de la classe (inliers) avec des valeurs positives tout en pénalisant les outliers avec des valeurs négatives et nous l'améliorons avec la découverte d'itemsets fréquents et rares. Notre mesure est plus performante que celle du FPOF (Frequent Pattern Outlier Factor). Les expérimentations prouvent l'efficacité de notre approche.
