# Optimizing Biomedical Ontology Alignment through a Compact Multiobjective Particle Swarm Optimization Algorithm Driven by Knee Solution

Authors: Xingsi Xue; Xiaojing Wu; Junfeng Chen
Journal: Discrete Dynamics in Nature and Society
 (2020)

---

## Abstract

Nowadays, most real-world decision problems consist of two or more incommensurable or conflicting objectives to be optimized simultaneously, so-called multiobjective optimization problems (MOPs). Usually, a decision maker (DM) prefers only a single optimum solution in the Pareto front (PF), and the PF’s knee solution is logically the one if there are no user-specific or problem-specific preferences. In this context, the biomedical ontology matching problem in the Semantic Web (SW) domain is investigated, which can be of help to integrate the biomedical knowledge and facilitate the translational discoveries. Since biomedical ontologies often own large-scale concepts with rich semantic meanings, it is difficult to find a perfect alignment that could meet all DM’s requirements, and usually, the matching process needs to trade-off two conflict objectives, i.e., the alignment’s recall and precision. To this end, in this work, the biomedical ontology matching problem is first defined as a MOP, and then a compact multiobjective particle swarm optimization algorithm driven by knee solution (CMPSO-K) is proposed to address it. In particular, a compact evolutionary mechanism is proposed to efficiently optimize the alignment’s quality, and a max-min approach is used to determine the PF’s knee solution. In the experiment, three biomedical tracks provided by Ontology Alignment Evaluation Initiative (OAEI) are used to test CMPSO-K’s performance. The comparisons with OAEI’s participants and PSO-based matching technique show that CMPSO-K is both effective and efficient.


---

## Body

## 1. Introduction

Decision-making requires finding an optimum solution to a decision problem in the process of identifying and evaluating alternatives. Nowadays, most real-world decision problems consist of two or more incommensurable objectives to be optimized simultaneously, so-called multiobjective optimization problems (MOPs) [1]. In general, MOP does not have one optimum solution but a set of solutions, so-called Pareto optimal solutions, which are superior to the others in terms of one or more objectives. In many situations, a decision maker (DM) only prefers one single optimum solution in the Pareto front (PF) [2], and therefore, the optimization and the decision process are often combined. One of the multiobjective methods is driven by the PF’s knee solution which is the one for which an improvement in one of its objectives will result in a deterioration in another. Often, PF’s knee solution is logically preferred to the DM if there are no user-specific or problem-specific preferences [3].In this context, the biomedical ontology matching problem in the Semantic Web (SW) domain is investigated. Although biomedical ontology is extensively used in the biomedical domain to model the biomedical knowledge, it is developed and maintained by different communities, and the same biomedical knowledge could be described with different terminologies or in different contexts. To bridge the semantic gaps between two biomedical ontologies and support their communications, it is necessary to find their identical concept mapping, which is the so-called biomedical ontology matching. Since biomedical ontologies often own large-scale concepts with rich semantic meanings, it is difficult to find a perfect alignment that could meet all DM’s requirements, and usually, the matching process needs to trade-off two conflict objectives, i.e., the alignment’s recall and precision. To this end, in this work, the biomedical ontology matching problem is defined as a MOP. Although there are many studies on the single-objective approaches for addressing the ontology matching problem [4–8], the research on multiobjective ontology matching techniques is still in this infancy [9]. Being inspired by the success of the particle swarm optimization algorithm (PSO) in the ontology matching domain [10], large-scale discrete optimization domain [11–13], and biomedical engineering [14], in this work, a compact multiobjective particle swarm optimization algorithm driven by knee solution (CMPSO-K) is further proposed to address this problem. In particular, CMPSO-K uses a compact multiobjective evolutionary mechanism to efficiently optimize the alignment’s quality and a max-min approach to determine the PF’s knee solution. The contributions made in this paper are as follows: (1) a discrete multiobjective optimal model for the biomedical ontology matching problem is constructed; (2) a hybrid biomedical concept similarity metric is proposed, which can effectively calculate the similarity value of two biomedical ontology concepts; and (3) a CMPSO-K is proposed to optimize the biomedical ontology alignment, which takes into consideration both DM’s preference and algorithm’s performance.The rest of the paper is organized as follows: Section2 overviews the SIA-based ontology matching techniques; Section 3 defines the biomedical ontology matching problem and presents the similarity measure on biomedical concepts; Section 4 presents the CMPSO-K-based biomedical ontology matching technique in detail; Section 5 shows the experimental results; and finally, Section 6 draws the conclusion and presents the future work.


## 2. Swarm Intelligence Algorithm-Based Ontology Matching Technique

The first generation of swarm intelligence algorithm- (SIA-) based matcher dedicates to optimize the ways of aggregating various ontology matchers’ corresponding alignments. The very first matching system is Genetics for Ontology ALignments (GOAL) [7], which uses evolutionary algorithm (EA) to optimize the aggregating weight set of different ontology matchers. Later, Alexandru-Lucian and Iftene [15] further used EA to optimize one more parameter to filter the unauthentic concept mappings to final alignment. Acampora et al. [4] introduced a local search process into EA’s evolving process to improve the algorithm’s performance. Xue and Wang [16] used a new metric as the fitness function to guide the algorithm’s search direction. Their approach can address the holistic matching problem and determine a universal weight configuration for matching several pairs of ontologies at a time. He et al. [6] proposed to utilize artificial bee colony algorithm (ABC) to optimize all the parameters in the matching process, whose results are better than the EA-based matchers. More recently, Xue et al. [17] proposed a new approach that uses NSGA-III [18] to combine various similarity measures without tuning the aggregating parameters. However, when the scale of the similarity measures becomes huge, e.g., more than 50 similarity measures, this approach could be inefficient.The above matchers need to calculate all the matchers’ alignments and store them in the main memory before aggregating them, which requires huge memory consumption. Recently, the second generation of the SIA-based matcher tries to directly find an entity correspondence set that is close to the golden alignment. GAOM (genetic algorithm-based ontology matching) [8] regards two ontologies as two discrete concept sets and employs EA to determine the optimal entity mapping set. Alves et al. utilized a memetic algorithm (MA), which combines EA with a local search strategy, to execute the instance-based ontology matching process [5]. They first matched the instances and then propagated the instance pair’s similarity value to the corresponding concepts. More recently, MapPSO [10] uses PSO to determine the optimal entity correspondence set. In particular, MapPSO introduces a new quality measure on the ontology alignment, which depends on the statistical results on the alignment. More recently, Chu et al. [19] first modeled the ontologies in the vector space so that two entities’ similarity value can be calculated through the cosine function, and then EA was used to determine the optimal alignments. Xue [20] proposed a new similarity metric for measuring the biomedical concepts’ similarity value and then used the firefly algorithm (FA) to optimize the biomedical ontology alignment. However, their proposal suffers from the premature convergence when matching large-scale ontologies. Our proposal also belongs to this category, but different from the existing work, in this work, the biomedical ontology problem is regarded as a discrete MOP, and a multiobjective SIA is presented to address it, which takes into consideration the DM’s preference.


## 3. Preliminaries

### 3.1. Biomedical Ontology Matching Problem

Ontology matching aims at determining the identical entity mappings, which is the so-called ontology alignment. In the past, the ontology alignment’s quality was often measured by f-measure [21], which is defined as follows:(1)recall=R∩AR,precision=R∩AA,f−measure=recall×precisionα×recall+1−α×precision,where R and A are, respectively, the alignments determined by the domain expert and ontology matcher. Recall and precision, respectively, measure A’s completeness and soundness, f-measure is their harmony mean, and α∈ [0, 1] is the weight to trade-off recall and precision. However, f-measure requires domain experts to provide R, which limits its application in real practice. Supposing a golden biomedical ontology alignment’s cardinality is 1 : 1, since the larger cardinality of the concept mapping set is and the higher the found correspondences’ mean similarity value is, the better the alignment quality is, three approximate measures, i.e., recall’, precision’, and f-measure’, are used to, respectively, approximate the original recall, precision, and f-measure [22]:(2)recall′=AmaxC1，C2,precision′=∑i=1AsimValueiA,f−measure′=recall′×precision′α×recall′+1−α×precision′,where C1and C1are two ontologies’ concept scale, Ais A’s concept mapping number, and simValueiis the i-th concept mapping’s similarity value.Finally, biomedical ontology matching problem’s discrete multiobjective optimal model is defined as follows:(3)maxfx=rx,px,s.t.X=x1,x2,…,xC1T,xi∈1,2,…,C2,i=1,2,⋯,C1,where C1 and C2 are, respectively, the concept number of two biomedical ontologies, ximeans the i-th pair of concept correspondence, i.e., i-th source concept is mapped to target xi-th concept, and two objective functions r and pare to, respectively, maximize recall’ and precision’ of X’s corresponding alignment.


### 3.2. Similarity Measure on Biomedical Concept

In this work, a hybrid similarity measure is used to enhance the confidence of the calculated similarity value, which takes into consideration the concept’s syntax and linguistic and context information. First, for each biomedical concept, the information (the label, comment, and property name) from itself and its context concept are put into its separated profile. Then, two biomedical concepts’ similarity value is calculated according to the following equation:(4)simp1,p2=∑i=1fmaxj=1⋯gsimp1i,p2j+∑j=1gmaxi=1⋯fsimp1i,p2jf+g,where p1and p2are, respectively, two biomedical concept’s corresponding profiles and simp1i,p2j is calculated by integrating the SMOA [23] based on syntax measure and Unified Medical Language System (UMLS) [24] based on linguistic measure.(5)simp1i,p2j=1,if two elements are synonymous in UMLSSMOAp1i,p2j,otherwise.


## 3.1. Biomedical Ontology Matching Problem

Ontology matching aims at determining the identical entity mappings, which is the so-called ontology alignment. In the past, the ontology alignment’s quality was often measured by f-measure [21], which is defined as follows:(1)recall=R∩AR,precision=R∩AA,f−measure=recall×precisionα×recall+1−α×precision,where R and A are, respectively, the alignments determined by the domain expert and ontology matcher. Recall and precision, respectively, measure A’s completeness and soundness, f-measure is their harmony mean, and α∈ [0, 1] is the weight to trade-off recall and precision. However, f-measure requires domain experts to provide R, which limits its application in real practice. Supposing a golden biomedical ontology alignment’s cardinality is 1 : 1, since the larger cardinality of the concept mapping set is and the higher the found correspondences’ mean similarity value is, the better the alignment quality is, three approximate measures, i.e., recall’, precision’, and f-measure’, are used to, respectively, approximate the original recall, precision, and f-measure [22]:(2)recall′=AmaxC1，C2,precision′=∑i=1AsimValueiA,f−measure′=recall′×precision′α×recall′+1−α×precision′,where C1and C1are two ontologies’ concept scale, Ais A’s concept mapping number, and simValueiis the i-th concept mapping’s similarity value.Finally, biomedical ontology matching problem’s discrete multiobjective optimal model is defined as follows:(3)maxfx=rx,px,s.t.X=x1,x2,…,xC1T,xi∈1,2,…,C2,i=1,2,⋯,C1,where C1 and C2 are, respectively, the concept number of two biomedical ontologies, ximeans the i-th pair of concept correspondence, i.e., i-th source concept is mapped to target xi-th concept, and two objective functions r and pare to, respectively, maximize recall’ and precision’ of X’s corresponding alignment.


## 3.2. Similarity Measure on Biomedical Concept

In this work, a hybrid similarity measure is used to enhance the confidence of the calculated similarity value, which takes into consideration the concept’s syntax and linguistic and context information. First, for each biomedical concept, the information (the label, comment, and property name) from itself and its context concept are put into its separated profile. Then, two biomedical concepts’ similarity value is calculated according to the following equation:(4)simp1,p2=∑i=1fmaxj=1⋯gsimp1i,p2j+∑j=1gmaxi=1⋯fsimp1i,p2jf+g,where p1and p2are, respectively, two biomedical concept’s corresponding profiles and simp1i,p2j is calculated by integrating the SMOA [23] based on syntax measure and Unified Medical Language System (UMLS) [24] based on linguistic measure.(5)simp1i,p2j=1,if two elements are synonymous in UMLSSMOAp1i,p2j,otherwise.


## 4. Compact Multiobjective Swarm Optimization Algorithm Driven by Knee Solution

This work proposes a CMPSO-K for solving the biomedical ontology matching problem, which approximates the population-based PSO’s evolving process through a probability vector (PV) [25]. In the next, the objective decomposition approach, the encoding mechanism, and knee solution determination are presented, respectively, and finally, the details of CMPSO-K are shown through the pseudo-code.


### 4.1. Objective Decomposition

In this work, the weighted sum approach is used to transform a MOP into a set of subproblems and solves them simultaneously.(6)maxgwsxw=∑i=1Nwi·fixs.t.x∈Ω⊂Rn,where N is the number of decomposed problems and wi∈0,1i=1,…,N,∑i=1Nwi=1. Two objectives of our problem are to maximize recall’ and precision’, and the ith subproblem’s objective is defined as follows:(7)maxrecall′×precision′αi×recall′+1−αi×precision′,where α1=0 and αi=i−1/N−1, …∞,αN=1.


### 4.2. Encoding Mechanism

In this work, the Gray coding, a binary encoding mechanism, is used to encode an alignment. As can be seen from Figure1, an example of the encoding mechanism is shown, in which the source concept “uterine gland” with index 8 is mapped to target concept “Uterine Gland” with index 6 whose Gray code is 110. In particular, Gray code 000 means a source concept is not mapped to any target concept.Figure 1
An example of the encoding mechanism.Moreover, a PV is utilized to characterize a population for solving one decomposed subproblem, whose element number is equal to that of an individual, and each element in PV represents the probability of being 0. Therefore, various individuals can be generated with the binary code through a PV. Figure2 shows an example of generating an individual through PV. Through comparing each of PV’s element with the random number, the new individual’s element value can be determined. It is obvious that when all of PV’s elements are close to 1 or 0, the algorithm tends to converge. At the end of each generation, PV is updated according to the best individual by increasing (or decreasing) its element value if the corresponding element of that individual is 1 (or 0).Figure 2
An example of generating an individual through PV.


### 4.3. Crossover Operator

The crossover operator generates one child individual by mixing the information of two parent individuals, which is carried out according to the crossover probability. In this work, the uniform crossover operator is used, whose pseudo-code is shown in Algorithm1. Given two parent solutions ind1 and ind2, each gene bit value of their offspring ind new is the same with the corresponding gene bit value of ind1 (or ind2) when a random number rand0,1 is larger than (or smaller than) the crossover ratepcr.Algorithm 1: Uniform crossover.
Input: two individualsind1 and ind2, crossover probability pcr
Output: a new individualindnew
(1)
i
n
d
new = ind1;
(2)
for ind i = 1; i ≤ ind1 .length, i++ do
(3)
if rand0,1 < pcr then
(4)
i
n
d
new
,
i = ind2,i;
(5)
end if
(6)
end for
(7)
returnindnew;


### 4.4. Determination of Knee Solution

Figure3 shows an example of knee solution and user preferred region. As can be seen from the figure, the knee solution, a subproblem’s elite solution, and the PF form a user preferred region for that subproblem. In each generation, the newly generated solution tends to move toward that region to meet a DM’s requirement. Thus, the knee solution’s determination is of utmost importance for the algorithm’s search performance. In this work, for those solutions in the PF, a max-min approach is used to determine the knee solution. In particular, suppose ind1 and ind2 are two solutions in the PF, and recalli' and precisioni', i=1,2, are, respectively, their recall’ and precision’, and they can be compared according to the following formula:(8)xi=argimaxminrecalli′,precisioni′.Figure 3
An example of knee solution and user preferred region.On this basis, a best solution can be selected from PF solutions, and this procedure is shown in Algorithm2.Algorithm 2: Determination of knee solution.
Input: PF solution set INDpf=ind1,ind2,···
Output: a knee solution indelite
(1)
max
=
0;
(2)
for ind i = 1; i ≤ INDpf .length, i++do
(3)
mini=minindi.recall′,indi.precision′
(4)
if mini>max then
(5)
max = mini;
(6)
indelite = indi;
(7)
end if
(8)
end for
(9)
returnindelite


### 4.5. Pseudo-Code of Compact Multiobjective Particle Swarm Optimization Algorithm Driven by Knee Solution

The pseudo-code of CMPSO-K is presented in Algorithm3. CMPSO-K first divides the problem into three subproblems that, respectively, maximize fα=0, fα=0.5, and fα=1. First, three PVs and local best individuals are, respectively, initialized for three subproblems, and then the knee solution (or global best individual) is initialized by first using the nondominated sorting algorithm [26] on the population and then the knee solution in the PF is determined. In each generation, CMPSO-K tries to solve each subproblem by approximating PSO’s position updating strategy, i.e., crossover an individual with the local best individual and global best individual to obtain a new individual, and then use the new one to update the local best individual and PV. After solving each subproblem, a population in the current generation is obtained by 3 local best individuals and 6 individuals in total generated through PVα=0, PVα=0.5, and PVα=1, respectively, and then the nondominated sorting algorithm is used to determine its PF and the current generation’s knee solution indelite′. Through comparing indelite′ with historical knee solution indelite through the max-min approach, the latter can be updated. Finally, when the generation approaches the maximum generation maxGen, the algorithm terminates and returns indelite.Algorithm 3: Compact multiobjective particle swarm optimization algorithm driven by knee solution.
Input: maximum generation maxGen, crossover rate pcr, step length for updating PVstep
Output: knee solution indelite
(1)
∗
∗Initialization∗∗
(2)
initialize generationt=0;
(3)
initializePVα=0, PVα=0.5 and PVα=1 by setting all the elements inside as 0.5;
(4)
initialize three local best individualsindα=0,elite, indα=0.5,elite and indα=1,elite;
(5)
generate5 individuals through PVα=0, PVα=0.5 and PVα=1;
(6)
N
o
n
D
o
m
i
n
a
t
e
d
S
o
r
t;
(7)
initialize the knee solution (or global best individual)indelite;
(8)
∗
∗Evolving Process∗∗
(9)
while t<maxGen do
(10)
∗
∗Updating indα=0,elite∗∗
(11)
generate an individualindα=0,new through PVα=0;
(12)
i
n
d
α
=
0
,
n
e
w
=
c
r
o
s
s
o
v
e
r
i
n
d
α
=
0
,
n
e
w
,
i
n
d
α
=
0
,
e
l
i
t
e
(13)
i
n
d
α
=
0
,
n
e
w
=
c
r
o
s
s
o
v
e
r
i
n
d
α
=
0
,
n
e
w
,
i
n
d
e
l
i
t
e;
(14)
w
i
n
n
e
r
,
l
o
s
e
r
=
c
o
m
p
e
t
e
i
n
d
α
=
0
,
n
e
w
,
i
n
d
α
=
0
,
e
l
i
t
e;
(15)
u
p
d
a
t
e
P
V
w
i
n
n
e
r
,
l
o
s
e
r;
(16)
if winner==indα=0,new then
(17)
i
n
d
α
=
0
,
e
l
i
t
e = indα=0,new;
(18)
end if
(19)
∗
∗Updating indα=0.5,elite∗∗
(20)
generate an individualindα=0,new through PVα=0.5;
(21)
i
n
d
α
=
0.5
,
n
e
w = crossoverindα=0,new,indα=0.5,elite;
(22)
i
n
d
α
=
0.5
,
n
e
w = crossoverindα=0,new,indelite;
(23)
w
i
n
n
e
r
,
l
o
s
e
r
=
c
o
m
p
e
t
e
i
n
d
α
=
0
,
n
e
w
,
i
n
d
α
=
0.5
,
e
l
i
t
e
(24)
u
p
d
a
t
e
P
V
w
i
n
n
e
r
,
l
o
s
e
r;
(25)
if winner = = indα=0,new then
(26)
i
n
d
α
=
0.5
,
e
l
i
t
e  =  indα=0,new;
(27)
end if
(28)
∗
∗Updating indα=1,elite∗∗
(29)
generate an individualindα=1,new through PVα=1;
(30)
i
n
d
α
=
1
,
n
e
w = crossoverindα=1,new,indα=1,elite;
(31)
i
n
d
α
=
1
,
n
e
w  =  crossoverindα=1,new,indelite;
(32)
w
i
n
n
e
r
,
l
o
s
e
r
=
c
o
m
p
e
t
e
i
n
d
α
=
1
,
n
e
w
,
i
n
d
α
=
1
,
e
l
i
t
e
(33)
u
p
d
a
t
e
P
V
w
i
n
n
e
r
,
l
o
s
e
r;
(34)
if winner==indα=1,new then
(35)
i
n
d
α
=
1
,
e
l
i
t
e = indα=1,new;
(36)
end if
(37)
∗
∗Updating indelite∗∗
(38)
generate 2 individuals throughPVα=0, PVα=0.5 and PVα=1, respectively,
(39)
N
o
n
D
o
m
i
n
a
t
e
d
S
o
r
t;
(40)
determine current generation’s knee solutionindelite′;
(41)
w
i
n
n
e
r
,
l
o
s
e
r
=
c
o
m
p
e
t
e
i
n
d
e
l
i
t
e
,
i
n
d
e
l
i
t
e
′;
(42)
if winner==indelite′ then
(43)
i
n
d
e
l
i
t
e = indelite′;
(44)
end if
(45)
t
=
t
+
1;
(46)
end while
(47)
return indelite;


## 4.1. Objective Decomposition

In this work, the weighted sum approach is used to transform a MOP into a set of subproblems and solves them simultaneously.(6)maxgwsxw=∑i=1Nwi·fixs.t.x∈Ω⊂Rn,where N is the number of decomposed problems and wi∈0,1i=1,…,N,∑i=1Nwi=1. Two objectives of our problem are to maximize recall’ and precision’, and the ith subproblem’s objective is defined as follows:(7)maxrecall′×precision′αi×recall′+1−αi×precision′,where α1=0 and αi=i−1/N−1, …∞,αN=1.


## 4.2. Encoding Mechanism

In this work, the Gray coding, a binary encoding mechanism, is used to encode an alignment. As can be seen from Figure1, an example of the encoding mechanism is shown, in which the source concept “uterine gland” with index 8 is mapped to target concept “Uterine Gland” with index 6 whose Gray code is 110. In particular, Gray code 000 means a source concept is not mapped to any target concept.Figure 1
An example of the encoding mechanism.Moreover, a PV is utilized to characterize a population for solving one decomposed subproblem, whose element number is equal to that of an individual, and each element in PV represents the probability of being 0. Therefore, various individuals can be generated with the binary code through a PV. Figure2 shows an example of generating an individual through PV. Through comparing each of PV’s element with the random number, the new individual’s element value can be determined. It is obvious that when all of PV’s elements are close to 1 or 0, the algorithm tends to converge. At the end of each generation, PV is updated according to the best individual by increasing (or decreasing) its element value if the corresponding element of that individual is 1 (or 0).Figure 2
An example of generating an individual through PV.


## 4.3. Crossover Operator

The crossover operator generates one child individual by mixing the information of two parent individuals, which is carried out according to the crossover probability. In this work, the uniform crossover operator is used, whose pseudo-code is shown in Algorithm1. Given two parent solutions ind1 and ind2, each gene bit value of their offspring ind new is the same with the corresponding gene bit value of ind1 (or ind2) when a random number rand0,1 is larger than (or smaller than) the crossover ratepcr.Algorithm 1: Uniform crossover.
Input: two individualsind1 and ind2, crossover probability pcr
Output: a new individualindnew
(1)
i
n
d
new = ind1;
(2)
for ind i = 1; i ≤ ind1 .length, i++ do
(3)
if rand0,1 < pcr then
(4)
i
n
d
new
,
i = ind2,i;
(5)
end if
(6)
end for
(7)
returnindnew;


## 4.4. Determination of Knee Solution

Figure3 shows an example of knee solution and user preferred region. As can be seen from the figure, the knee solution, a subproblem’s elite solution, and the PF form a user preferred region for that subproblem. In each generation, the newly generated solution tends to move toward that region to meet a DM’s requirement. Thus, the knee solution’s determination is of utmost importance for the algorithm’s search performance. In this work, for those solutions in the PF, a max-min approach is used to determine the knee solution. In particular, suppose ind1 and ind2 are two solutions in the PF, and recalli' and precisioni', i=1,2, are, respectively, their recall’ and precision’, and they can be compared according to the following formula:(8)xi=argimaxminrecalli′,precisioni′.Figure 3
An example of knee solution and user preferred region.On this basis, a best solution can be selected from PF solutions, and this procedure is shown in Algorithm2.Algorithm 2: Determination of knee solution.
Input: PF solution set INDpf=ind1,ind2,···
Output: a knee solution indelite
(1)
max
=
0;
(2)
for ind i = 1; i ≤ INDpf .length, i++do
(3)
mini=minindi.recall′,indi.precision′
(4)
if mini>max then
(5)
max = mini;
(6)
indelite = indi;
(7)
end if
(8)
end for
(9)
returnindelite


## 4.5. Pseudo-Code of Compact Multiobjective Particle Swarm Optimization Algorithm Driven by Knee Solution

The pseudo-code of CMPSO-K is presented in Algorithm3. CMPSO-K first divides the problem into three subproblems that, respectively, maximize fα=0, fα=0.5, and fα=1. First, three PVs and local best individuals are, respectively, initialized for three subproblems, and then the knee solution (or global best individual) is initialized by first using the nondominated sorting algorithm [26] on the population and then the knee solution in the PF is determined. In each generation, CMPSO-K tries to solve each subproblem by approximating PSO’s position updating strategy, i.e., crossover an individual with the local best individual and global best individual to obtain a new individual, and then use the new one to update the local best individual and PV. After solving each subproblem, a population in the current generation is obtained by 3 local best individuals and 6 individuals in total generated through PVα=0, PVα=0.5, and PVα=1, respectively, and then the nondominated sorting algorithm is used to determine its PF and the current generation’s knee solution indelite′. Through comparing indelite′ with historical knee solution indelite through the max-min approach, the latter can be updated. Finally, when the generation approaches the maximum generation maxGen, the algorithm terminates and returns indelite.Algorithm 3: Compact multiobjective particle swarm optimization algorithm driven by knee solution.
Input: maximum generation maxGen, crossover rate pcr, step length for updating PVstep
Output: knee solution indelite
(1)
∗
∗Initialization∗∗
(2)
initialize generationt=0;
(3)
initializePVα=0, PVα=0.5 and PVα=1 by setting all the elements inside as 0.5;
(4)
initialize three local best individualsindα=0,elite, indα=0.5,elite and indα=1,elite;
(5)
generate5 individuals through PVα=0, PVα=0.5 and PVα=1;
(6)
N
o
n
D
o
m
i
n
a
t
e
d
S
o
r
t;
(7)
initialize the knee solution (or global best individual)indelite;
(8)
∗
∗Evolving Process∗∗
(9)
while t<maxGen do
(10)
∗
∗Updating indα=0,elite∗∗
(11)
generate an individualindα=0,new through PVα=0;
(12)
i
n
d
α
=
0
,
n
e
w
=
c
r
o
s
s
o
v
e
r
i
n
d
α
=
0
,
n
e
w
,
i
n
d
α
=
0
,
e
l
i
t
e
(13)
i
n
d
α
=
0
,
n
e
w
=
c
r
o
s
s
o
v
e
r
i
n
d
α
=
0
,
n
e
w
,
i
n
d
e
l
i
t
e;
(14)
w
i
n
n
e
r
,
l
o
s
e
r
=
c
o
m
p
e
t
e
i
n
d
α
=
0
,
n
e
w
,
i
n
d
α
=
0
,
e
l
i
t
e;
(15)
u
p
d
a
t
e
P
V
w
i
n
n
e
r
,
l
o
s
e
r;
(16)
if winner==indα=0,new then
(17)
i
n
d
α
=
0
,
e
l
i
t
e = indα=0,new;
(18)
end if
(19)
∗
∗Updating indα=0.5,elite∗∗
(20)
generate an individualindα=0,new through PVα=0.5;
(21)
i
n
d
α
=
0.5
,
n
e
w = crossoverindα=0,new,indα=0.5,elite;
(22)
i
n
d
α
=
0.5
,
n
e
w = crossoverindα=0,new,indelite;
(23)
w
i
n
n
e
r
,
l
o
s
e
r
=
c
o
m
p
e
t
e
i
n
d
α
=
0
,
n
e
w
,
i
n
d
α
=
0.5
,
e
l
i
t
e
(24)
u
p
d
a
t
e
P
V
w
i
n
n
e
r
,
l
o
s
e
r;
(25)
if winner = = indα=0,new then
(26)
i
n
d
α
=
0.5
,
e
l
i
t
e  =  indα=0,new;
(27)
end if
(28)
∗
∗Updating indα=1,elite∗∗
(29)
generate an individualindα=1,new through PVα=1;
(30)
i
n
d
α
=
1
,
n
e
w = crossoverindα=1,new,indα=1,elite;
(31)
i
n
d
α
=
1
,
n
e
w  =  crossoverindα=1,new,indelite;
(32)
w
i
n
n
e
r
,
l
o
s
e
r
=
c
o
m
p
e
t
e
i
n
d
α
=
1
,
n
e
w
,
i
n
d
α
=
1
,
e
l
i
t
e
(33)
u
p
d
a
t
e
P
V
w
i
n
n
e
r
,
l
o
s
e
r;
(34)
if winner==indα=1,new then
(35)
i
n
d
α
=
1
,
e
l
i
t
e = indα=1,new;
(36)
end if
(37)
∗
∗Updating indelite∗∗
(38)
generate 2 individuals throughPVα=0, PVα=0.5 and PVα=1, respectively,
(39)
N
o
n
D
o
m
i
n
a
t
e
d
S
o
r
t;
(40)
determine current generation’s knee solutionindelite′;
(41)
w
i
n
n
e
r
,
l
o
s
e
r
=
c
o
m
p
e
t
e
i
n
d
e
l
i
t
e
,
i
n
d
e
l
i
t
e
′;
(42)
if winner==indelite′ then
(43)
i
n
d
e
l
i
t
e = indelite′;
(44)
end if
(45)
t
=
t
+
1;
(46)
end while
(47)
return indelite;


## 5. Experiment

To test CMPSO-K’s performance, the experiment exploits three biomedical tracks in Ontology Alignment Evaluation Initiative (OAEI), i.e., anatomy track, large biomed track, and disease and phenotype track. The testing cases in these tracks are all practical ontologies that are widely used in the biomedical domain and open to achieve, which have lots of overlapping information with different representations. OAEI provides the reference alignments for each track to test a matcher’s performance, and Table1 briefly describes the ontologies in these tracks.Table 1
Description on the OAEI’s tracks.
Track
Subtask
Ontology
Scale
Anatomy
MA-HA
Adult Mouse Anatomy (MA)
2,744 classes
Human Anatomy (HA)
3,304 classes
Large biomed
FMA-NCI
Foundation Model of Anatomy (FMA)
78,989 classes
FMA-SNOMED
Systemized Nomenclature of Medicine (SNOMED)
122,464 classes
SNOMED-NCI
National Cancer Institute Thesaurus (NCI)
66,724 classes
Disease and phenotype
HP-MP
Human Phenotype Ontology (HP)
33,205 classes
Mammalian Phenotype Ontology (MP)
32,298 classes
DOID-ORDO
Human Disease Ontology (DOID)
24,034 classes
Orphanet Rare Disease Ontology (ORDO)
68,009 classesIn terms of the alignment’s quality, the EA-based matcher [8], ABC-based matcher [6], PSO-based matcher [10], and OAEI’s participants are compared in Tables 2 and 3, and also, in terms of the memory consumption and converging speed, CMPSO-K-based matcher and other SIA-based matchers are compared in Figures 4 and 5. All the SIAs’ results are the mean values of 30 independent executions. EA, ABC, and PSO’s configurations are referred to their literatures, and CMPSO-K uses the following configuration: number of decomposed problems: N=3; maximum generation: maxGen=3000; crossover probability:pcr=0.6; and step length for updating PV:step=0.1. This configuration is determined in an empirical way, which represents a trade-off setting in the experiment to obtain the highest average results on all testing cases.Table 2
Friedman’s test on the alignment’s quality. Each value represents the f-measure, and the number in round parentheses is the corresponding computed rank.
Anatomy
FMA-NCI
FMA-SNOMED
NCI-SNOMED
HP-MP
DOID-ORDO
Average
AML [27]
0.94 (1.5)
0.93 (1.5)
0.83 (2)
0.80 (2)
0.84 (3)
0.64 (7)
0.83 (2.83)
LogMap [28]
0.89 (4)
0.92 (3)
0.79 (3)
0.77 (3)
0.85 (2)
0.84 (2)
0.84 (2.83)
XMap [29]
0.89 (4)
0.86 (5.5)
0.77 (4)
0.69 (4)
0.47 (8.5)
0.70 (6)
0.73 (2.33)
DOME [30]
0.76 (6)
0.86 (5.5)
0.33 (9)
0.64 (6)
0.47 (8.5)
0.60 (9)
0.61 (7.33)
POMAP++ [31]
0.89 (4)
0.88 (4)
0.40 (8)
0.68 (5)
0.68 (6)
0.83 (3)
0.73 (5.00)
EA [8]
0.68 (9)
0.73 (8)
0.64 (6)
0.53 (8)
0.70 (5)
0.61 (8)
0.65 (7.33)
ABC [6]
0.72 (7)
0.75 (7)
0.64 (6)
0.62 (7)
0.62 (7)
0.72 (5)
0.68 (6.50)
PSO [10]
0.70 (8)
0.72 (9)
0.64 (6)
0.51 (9)
0.72 (4)
0.75 (4)
0.67 (6.67)
CMPSO-K
0.94 (1.5)
0.93 (1.5)
0.85 (1)
0.82 (1)
0.86 (1)
0.86 (1)
0.88 (1.17)Table 3
Holm’s test on the alignment’s quality.
i
Approach
z value
Unadjustedpvalue
α
/
k
−
i
,
α
=
0.05
8
XMap
2.33
0.045
0.050
7
AML
2.83
0.004
0.025
6
LogMap
2.83
0.004
0.016
5
POMAP++
5.00
1.28 × 10−7
0.012
4
ABC
6.50
9.82 × 10−8
0.010
3
PSO
6.67
3.79 × 10−8
0.008
2
EA
7.33
5.38 × 10−11
0.007
1
DOME
7.33
5.38 × 10−11
0.006Figure 4
Comparison on the converging speed, (a) comparison on the anatomy track, (b) comparison on the large biomed track, and (c) comparison on the disease and phenotype track.
(a)
(b)
(c)Figure 5
Comparison on the memory consumption.First, Friedman’s test [32] is used to figure out whether all the matchers present any difference and then determines whether one matcher statistically outperforms others through Holm’s test [33]. In Friedman’s test, the null hypothesis is that all the matchers are equivalent, and if the computed value χr2 must be equal to or greater than the tabled critical chi-square value at the specified level of significance [34], this hypothesis can be rejected. In this work, a level of significance =0.05 is chosen, and the critical value for 8 degrees of freedom (since there are 9 matchers), i.e., χ0.052=15.507, needs to be considered.In Table2, computed χr2 = 54.43, which is greater than 15.507, and therefore, the null hypothesis can be rejected, and Holm’s test can be further carried out. As shown in Table 2, since the CMPSO-K-based matcher ranks with the lowest value, it is set as a control matcher that will be compared with others.In Holm’s test,z value is the testing statistic for comparing the i-th and j-th matchers, which is used for finding the pvalue that is the corresponding probability from the table of the normal distribution. pvalue is then compared with α=0.05, which is an appropriate level of significance. According to Table 3, it is possible to state that our approach statistically outperforms other biomedical ontology matchers on f-measure at 5% significance level. Since the multiobjective evolving mechanism can better trade-off two objectives and the knee solution can effectively guide the algorithm’s search direction, CMPSO-K’s solutions are much better than other SIAs.Figures4 and 5, respectively, compare CMPSO-K with other SIAs on the memory consumption and converging speed. As can be seen from the figures, CMPSO-K can significantly improve the converging speed and reduce the memory consumption, which shows the effectiveness of the compact encoding mechanism and the compact evolutionary operators. To sum up, CMPSO-K-based ontology matching technique can efficiently optimize the biomedical ontology alignments.


## 6. Conclusion and Future Work

To optimize biomedical ontology alignment’s quality, in this paper, a discrete multiobjective optimal model is constructed, and a hybrid similarity metric to distinguish the heterogeneous biomedical concepts, a CMPSO-K-based ontology matching technique is then proposed for addressing it. Compared with the most existing SIA-based ontology matching techniques, CMPSO-K takes into consideration both the algorithm’s performance and the DM’s preference. Accordingly, three methods are proposed to achieve this goal: (1) the compact encoding mechanism for saving the memory consumption and runtime; (2) multiobjective decomposition and evolutionary mechanism for trading-off different objectives; and (3) the max-min strategy for determining the knee solution and guiding the algorithm’s searching direction. Our work presents a novel compact multiobjective evolutionary framework that can improve the efficiency of the current SIA-based ontology matching technique.In the experiment, the f-measure values obtained by CMPSO-K outperform all the other competitors, which shows that CMPSO-K can effectively optimize the ontology alignments. In particular, the quality of alignment of CMPSO-K is better than EA ABC and PSO, which shows that CMPSO-K’s multiobjective evolutionary mechanism driven by the knee solution can effectively trade-off two optimal objectives and find the better solution. Moreover, since the compact encoding mechanism uses PVs to represent the swarms and the compact evolutionary operators can simplify the population-based PSO’s evolving process, CMPSO-K can significantly reduce the memory consumption and runtime. Since none of the similarity measures can effectively distinguish all the heterogeneous concepts in any situations, it is necessary to aggregate several similarity measures to improve the result’s precision. We utilize a hybrid similarity measure which combines three kinds of similarity measures to calculate the entity similarity value, and therefore, CMPSO-K’s results are significantly higher than other systems that only take into consideration one or two categories of similarity measure, such as DOME, POMAP++, and LogMap. However, AML applies too many similarity measures that lead to the conflicting results, which decrease its recall value. Thus, how many similarity measures should be selected and combined to ensure the quality of the alignment will be one of our future work. Last but not the least, CMPSO-K takes into consideration of DM’s preference and utilizes the knee solution to guide the algorithm’s search direction, which can effectively trade-off two optimal objectives and find better solutions.To further improve the matching process’s efficiency, in the future, we will be interested in developing a biomedical ontology partitioning technique to split two ontologies into disjoint ontology segments so that the large-scale problem can be converted into several small-scale segment matching problems. After that, the parallel computation can also be further utilized to match the similar segments and improve the matching process’s performance. With respect to the similarity measure, we would like to develop an adaptive biomedical concept similarity measure framework, which can instantiate an effective similarity metric according to two biomedical ontologies’ heterogeneous characteristics.



---

*Source: 4716286-2020-05-01.xml*