## 2 Background
### Oppositional Biogeography-Based Optimization for Combinatorial Problems  
When dealing with \(D\) dimensional vectors in continuous domain (the space would be \(\mathbf{R}^{D}\)), the definition of opposite numbers is first given by [PERSON] as follows [2]. **Definition 1. ** Let \(P=(x_{1},\,x_{2},\,...,\,x_{D})\) be a point in \(D\)-dimensional space, where \(x_{1},\,x_{2},\,...,\,x_{D}\in\mathbf{R}\) and \(x_{i}\in[a_{i},\,b_{i}],\,\,\forall\,\,i\in\{1,\,2,\,...,\,D\}\). The opposite point \(\bar{P}=(\,\bar{x}_{1},\,\,\bar{x}_{2},\,...,\,\bar{x}_{D})\) is completely defined by its coordinates  
\[\bar{x}_{i}=a_{i}+b_{i}-x_{i} \tag{1}\]  
Figure 1 illustrates the opposite point \(\bar{P}\,\) in one dimensional case. **Figure 1.** Opposite point defined in domain \([a,\,b]\). \(x\) is a candidate solution and \(\bar{x}\,\) is the opposite of \(x\). To the best of our knowledge, the great majority of published research papers on opposition-based learning are for solving continuous domain optimization problems. Recently, more and more researchers gradually realized that opposition-based learning, originally introduced for accelerating a continuous search space, can also be modified to be used alongside BBO to solve combinatorial problems, including TSP. Obviously, wherein the main difficulty of these algorithm extensions is that how to define and evaluate opposite numbers in discrete domain [26]. For instance, given a candidate path, the attempting to apply opposition concept by simply reversing its order of the nodes is meaningless because the reversed path will yield the same cost as the original path in a TSP problem. For example, a tour (1, 2, 3, 4, 1) and its opposite tour, (1, 4, 3, 2, 1), have the same cost values because all of the cities preserve their neighbors. As a result, based on superficial analysis above, a new definition of opposition for TSP is needed and it should be different appreciably from that for continuous domain problems. In [28], an opposite path as following was defined as a candidate path that maximizes the distance between the adjacent vertices in the original path. **Definition 2. ** Let \(n\) be the number of nodes in a graph and \(P=[1,\,2,\,...,\,n]\) be an even node cycle. The clockwise opposite path, \(P_{o}^{Cw}\), is defined as  
\[P_{o}^{Cw}=[1,1+\frac{n}{2},\,2,\,2+\frac{n}{2},\,\cdots,\,\frac{n}{2}-1,\,n- 1,\frac{n}{2},\,n] \tag{2}\]  
It is notice that, the opposite point cannot be assigned as defined in (2) if \(n\) is odd. Since the number of nodes in a graph is odd, a possible and simple way to implement the clockwise opposition is to add an auxiliary node (denoted by \"\(n\) + 1\") to the end of the path and then complete the city count to an even number. Using the definition 2, we can work out the clockwise opposite path of candidate solution and then remove the auxiliary city \"\(n\) + 1\" from the end of opposite path. On the basis of classical BBO and the definition of opposite path, the original OBBO algorithm was proposed by [PERSON] and [PERSON] [28]. The basic procedure of OBBO algorithm is presented as follows in Algorithm 1. It is noticeable that the classical BBO algorithm is enhanced using the scheme of the Opposition-based Differential Evolution [12], namely, opposition-based population initialization (Rows 2-4 in Algorithm 1) and opposition-based generation jumping (Rows 9-13 in Algorithm 1). As far as we know, this exact scheme seems to be a generally-accepted and widely used mode in many opposition-based soft computing algorithms.