Study On The Ontology Matching Problem Based On Evolutionary Algorithms

Ontology is an explicit specification of a conceptualization, i.e. the formal specification of the objects, concepts, and other entities that are assumed to exist in some areas of interest and the relationships that hold them. However, because of subjectivity of ontology designers, various ontologies related to the same application domain may define one entity with different names or in different ways, raising so-called heterogeneity problem which is an obstacle for achieving semantic interoperability. The most solid solution for enabling semantic interoperability and really taking advantage of the ontological representation is to perform a so-called ontology matching process which leads two heterogeneous ontologies into a mutual agreement by detecting a set of correspondences between semantically related ontology entities. Since modeling the meta-matching problem is a complex(nonlinear problem with many local optimal solutions) and time-consuming task(particularly when the number of similarity measures is significantly large,), approximate methods are usually used for computing the correspondence. From this point of view, evolutionary optimization methods could represent an efficient approach for addressing this problem. However, current existing ontology matching systems based on evolutionary algorithm suffer from the following five drawbacks:(1) the slow convergence and premature convergence problem which makes classic Evolutionary Algorithm(EA) incapable of effectively searching the optimal solution for large scale and complex problems;(2) a standard ontology alignment should be provided by the experts which is unable to obtain in real application scenarios;(3) incapability of matching several pairs of ontology, i.e. finding a universal parameter configuration that can be used for different ontology pairs without adjustment;(4) the utilization of f-measure, a generally used evaluation metric of the alignment’s quality, may cause the bias improvement of the solution;(5) incapability of providing various alignment simultaneously for different requirements of the decision makers. In order to overcome these drawbacks, this dissertation studies on the Single Objective Optimization Problem(SOOP) and Multi-Objective Optimization Problem(MOOP) in the ontology matching domain, and the work of this thesis is summarized as follows:(1) A Partial Reference Alignment(PRA) based single objective optimization model for ontology meta-matching problem is firstly constructed, then a measure based on PRA is proposed and a ontology concept clustering algorithm is designed for constructing PRA, and on this basis, a MA based ontology matching method with PRA is proposed. After that, the preprocessing work, individual encoding, genetic operators and local searching process of using Memetic Algorithm(MA) to solve PRA based single objective optimization model for ontology meta-matching problem are presented in details. The test case set used in the experiment is the well known Benchmark in Ontology Alignment Evaluation Initiative 2012(OAEI 2012), and the principle of MA’s parameter configuration and the concrete configuration of MA’s parameters are given. The experimental results of MA based on partial reference alignment show that using PRA constructed by ontology concept clustering algorithm is able to determine better solutions than using PRA built by randomly selecting classes from ontology and the quality of the solution is very close to the approach using Reference Alignment(RA) where the precision value of the solution is generally high. The results of Wilcoxons test show that our approach achieve the average improvement of 47.33% on the classic EA based ontology matching sytem GOAL in terms of performance. Since MA based on PRA overcomes premature convergence problem of classic EA, it is able to obtain more accurate results than the famous ontology matching system based on classic EA and other states of the art ontology matching systems.(2) A no RA based single objective optimization model for ontology meta-matching problem is firstly constructed, then a measure based on no RA is proposed and the Unanimous Improvement Ratio(UIR) is proposed to work with the measure based on no RA in order to overcome the bias improvement problem and to simultaneously match multiple pairs of ontology, i.e. finding a universal weight configuration that can be used for different ontology pairs without adjustment, and on this basis, a MA based ontology matching method with no RA and UIR is proposed. The test case set used in the experiment is the Benchmark in OAEI 2012, experimental results show that MA based on no RA and UIR is able to simultaneously deal with multiple pairs of ontologies, avoid the bias improvement problem and obtain the ontology alignments with higher quality than the states of the art ontology matching systems.(3) A multi-objective optimization model, with two objectives recall and precision respectively, for ontology meta-matching problem is constructed, then the motivation of selecting Multi-Objective Evolutionary Algorithm(MOEA) and the selecting strategy of the representative solutions in Pareto front of MOEA are presented, and on this basis, two MOEAs, i.e. NSGA-II and MOEA/D, are utilized to solve the multi-objective optimization model for ontology meta-matching problem. After that, a self-adaptive similarity aggregation strategy is proposed to improve the efficiency of NSGA-II based approach, and the optimization problem decomposing approach and the implementing details of MOEA/D are presented. The test case set used in the experiment is the Benchmark in OAEI 2012, the T-test static analyzing results show that the ontology matching approaches using self-adaptive similarity aggregation strategy based NSGA-II and MOEA/D respectively are able to obtain better ontology alignment than ontology matching system based on classic EA and other states of the art ontology systems. Moreover, the results of Wilcoxons test show that MOEA/D based ontology matching approach outperforms the method using NSGA-II.(4) A multi-objective optimization model, with two objectives recall and precision, for ontology matching problem is constructed, then a novel instance similarity measure and similarity propagation algorithm are proposed, a new individual coding is designed, and on this basis, an instance based ontology matching approach using NSGA-II based on instance is proposed. The test case set used in the experiment is the Benchmark, Anatomy and Library in OAEI 2012, the experimental results show that the results obtained by instance based ontology matching approach using NSGA-II rank forefront among the states of the art ontology systems.