Entropy-Based Dynamic Heterogeneous Ant Colony Optimization

To solve large-scale traveling salesman problem (TSP) with better performance, this paper proposes an entropy-based dynamic heterogeneous ant colony optimization (EDHACO). The allotropic mechanism and the heterogeneous colonies model are proposed to balance the convergence and the solution diversity. First, entropy is used to measure the diversity, and the entropy-based allotropic mechanism with three communication strategies can improve the adaptability of EDHACO. Then, the heterogeneous colonies with complementary advantages are proposed to balance the convergence speed and the diversity of the algorithm. Besides, two operators are proposed to improve the performance of the algorithm. The adaptive 3-opt operator can be used to accelerate the convergence, and the dynamic-pheromone-reset operator can be introduced to avoid trapping in a local optimum. Finally, EDHACO is applied to solve TSPs, and the experimental results suggest that it has better performance with higher stability and precision in TSP instances, especially in the large-scale TSP instances.

SECTION I. Introduction

In 1996, Dorigo et al. [1] proposed the Ant System (AS), which is an optimization algorithm inspired by the labor division and the cooperation of ants, to solve combinatorial optimization problems. The main characteristics of AS are the positive feedback, the distributed computation, and the use of the constructive greedy heuristic.

Based on these characteristics, researchers proposed a sort of Ant System Optimizations (ACO) to improve the performance of AS and to meet the requirement of obtaining solutions with high quality and speed.

In 1997, Dorigo and Gambardella [2] proposed Ant Colony System (ACS), which is one of the best ACO, to improve AS. Based on AS, ACS introduces the local pheromone updating to improve the quality. The local pheromone updating can limit the pheromone to reduce the possibility of falling into a local optimum. Stützle and Hoos [3] proposed a new optimization algorithm called the Max -Min Ant System (MMAS), which has two main ideas as the global updating and the pheromone limits, to improve the premature convergence and to solve the stagnation problem Rank Based Ant System (RAS) is a kind of ACO to emphasize elites’ effect [4]. All the ants should be sorted by the length, and the effect of the elites can be embodied. Overall, these classical algorithms provide the valuable experiences to further research. Some improved operators can be introduced and some existing strategy can be modified, like the pheromone updating formula.

As the improvement of the single-population ACO, the multiple ant colony optimization (MACO) has been studied by researchers to find whether a better performance can be got by the cooperation of multiple ant colonies.

The concept of multiple ant colonies was first proposed by Gambardella et al. [5] to solve the vehicle routing problem with time windows. The two colonies in this algorithm were homogenous as ACS and they were designed to optimize different objective functions: the first colony could minimize the number of vehicles and the second colony was used to minimize the traveled distances. During the initial stages, homogenous colonies were popular in MACO. Chu et al. [6] proposed a homogenous MACO with seven communication methods to update the pheromones based on the best route of all groups. Twomey et al. [7] decided the migration integration policies for homogenous ant colonies communication.

The homogenous ant colony algorithms are relying on the basic ant colony algorithms to enhance the feature of single colony. To some extent, the heterogeneous ant colonies algorithms, in which different ant colonies have different behaviors, are more likely to take full advantage of different ACOs. Xu et al. [8] proposed the ACO with heterogeneous colonies as AS and IACS, in which AS can increase the solution diversity and IACS can help to fast the convergence speed. He et al. [9] proposed a heterogeneous dual population ACO with the colonies as EAS and RAS, which are the perfect complementarity. Sreeja and Sankar [10] proposed a hierarchical heterogeneous ant colony optimization with different ant agents and the minimal cost action rules to reduce time cost. ACO with heterogeneous colonies can make sure that each colony has its own division clearly, and be beneficial to balance the convergence and the diversity.

After the comparison between homogenous colonies and heterogeneous colonies, the communication mechanism of MACO should be analyzed as well. The communication mechanism may be subdivided into two issues, one is how to communicate, and another one is when to communicate.

According to the references, there is a good range of information can be communicated, such as the best solution [9], [11], [12], the pheromone matrix [11], and the insertion element [8]. Also, the worst ones can be replaced as well [13]. In the communication mechanism, different communication strategies can be used in different situations. Ellabib et al. [14] proposed three different exchange strategies according to the best solutions. Chu et al. [6] proposed seven communication methods to update pheromone for each colony. Middendorf et al. [12] proposed four strategies for information exchange.

According to the references above, the communication frequency is predefined by fixed iteration number [8], [14], [15]. To increase the self-adaptability of the algorithms, many researchers used entropy, which can measure the diversity and the evolution of populations, to decide the communication frequency [16], [17]. The good adaptability can help to balance the diversity and the convergence [18].

Besides, some improved operators can be used to optimize the algorithms as well, such as the 3-Opt operator [19], [20].

In this paper, we focus on the balance between convergence and diversity to solve large-scale TSPs. To improve the algorithm diversity with less communication cost than traditional dual colony algorithms, we propose a novel entropy-based communication mechanism called allotropic mechanism, which can use its three different communication strategies to take full advantage of each colony. The basic idea of communication is the use of the best solution and pheromone matrix with weight, and the information entropy is used to decide when to communicate adaptively and which strategy should be used. To balance the convergence speed and diversity better than other heterogeneous colony algorithms, we propose dual heterogeneous colonies called the Depth-first population, which improve the convergence of the algorithm, and the Breadth-first population, which can increase the solution diversity. Compared with other algorithms, EDHACO has a better performance in large-scale TSPs.

Additionally, to improve the performance of the algorithm proposed, the adaptive 3-Opt operator and the dynamic-pheromone-reset operator are applied in the algorithm to reduce the possibility of falling into a local optimum and to increase the convergence.

Besides, to set the suitable parameters, the two-way analysis of variance test is used in instance eil51.

This paper is organized as follows. Section II gives an overview of the related work. Section III describes the proposed the EDHACO including the allotropic mechanism, the heterogeneous colonies and the improved operators. Section IV sets the parameters by tests such as the two-way analysis of variance test. Section V discusses the impact of the communication strategies and the effect of each improved operator. Section VI shows the experimental results of EDHACO in different TSPs and discusses about the overall performance. Finally, Section VII concludes the paper and proposes the future work.

SECTION II. Related Work

A. Ant System (AS)

The Ant System algorithm was proposed by Dorigo et al. [1] in 1996 to solve combinatorial optimization problems, such as TSPs. The core parts of AS are pheromone updating and path construction.

Let $\tau _{ij}$ be the pheromone intensity of the trail on edge (i,j) when one ant moves from town i to town j. The trail intensity should be updated according to the following formula.

$$\begin{equation*} \tau _{ij} =(1-\alpha).\tau _{ij} +\Delta \tau _{ij}\tag{1}\end{equation*}$$ where $(1-\alpha)$ is a coefficient and $\alpha$ represents the evaporation of the trail after the movement. $\Delta \tau _{ij}$ follows (2). $$\begin{equation*} \Delta \tau _{ij} =\sum \limits _{k=1}^{m} {\Delta \tau _{ij}^{k} }\tag{2}\end{equation*}$$ where $\Delta \tau _{ij}^{k}$ is the quantity per unit of length of the trail substance (pheromone in real ants) laid on edge (i,j) by the k-th ant after its movement. It is given by $$\begin{equation*} \Delta \tau _{ij}^{k} =\begin{cases} \dfrac {Q}{L_{k} }& \text {if {k-th} ant uses edge (i,j) in its tour} \\ 0& \text {otherwise } \end{cases}\tag{3}\end{equation*}$$ where $Q$ is a constant and $L_{k}$ is the tour length of the k-th ant.

The visibility $\eta _{ij}$ is called the quantity $1/d_{ij}$ , where $d_{ij}$ is the distance between town i and town j. Then, the transition probability for the k-th ant to move from town i to town j can be defined as

$$\begin{equation*} p_{ij}^{k} =\begin{cases} \dfrac {\tau _{ij}^{\alpha }.\eta _{ij}^{\beta } }{\sum \limits _{k\in \text {allowed}_{\text {k}} } {\tau _{ik}^{\alpha }.\eta _{ik}^{\beta } } }& \text {if j }\in \text {allowed}_{k} \\ 0& \text {otherwise}\qquad \end{cases}\tag{4}\end{equation*}$$ where $\text {allowed}_{k}$ are the towns that can be chosen for the k-th ant in its movement, and $\alpha$ and $\beta$ are parameters that control the relative importance of trail versus visibility.

B. Ant Colony System (ACS)

ACS was proposed by Dorigo to improve the performance of AS and it differed from the previous AS in three main aspects [2].

First, the state transition rule is used to balance between the exploration of new edges and the exploitation of the priori and accumulated knowledge, and is given by

$$\begin{equation*} s=\begin{cases} \mathop {\arg \max }(\tau {ij}\bullet \eta _{ij}^{\beta }),& \text {if}~q\leq q_{0}\\ S &\text {otherwise} \end{cases}\tag{5}\end{equation*}$$ where $q$ is a random number uniformly distributed between 0 to 1, $q_{0}$ is a parameter which should be set with the help of experience and $S$ is equal to (4). With this rule, not only the probability selection, but also the greedy method can be used to construct the solution. ACS can speed up the convergence speed while ensuring the randomness.

Besides, in ACS, there are two methods to update pheromone as the global updating and the local updating. The pheromone can be updated by the updating rules of the same formula as

$$\begin{equation*} \tau _{rs}=(1-\alpha)\bullet \tau _{rs}+\alpha \bullet \Delta \tau _{rs}\tag{6}\end{equation*}$$

Be similar with (1), $\alpha$ is the pheromone decay parameter, and $(1-\alpha)$ is applied in the formula as well. The improved formula can help to reduce the impact of superfluous pheromone and adjust the pheromone with different feedback effect in different situations. It can be used to balance the diversity and convergence, and to avoid the premature phenomena.

For local updating, $\Delta \tau _{rs}$ is a beforehand parameter, and for global updating, only the global best tour can be allowed to deposit pheromone. It should be performed after the path construction. The global updating is intended to make the search more directed. $\Delta \tau _{rs}$ can be set as

$$\begin{equation*} \Delta \tau {rs}=\begin{cases} (L_{gb})^{-1}, &\text {if}(r,s)\in \text {global-best tour}\\ 0, &\text {otherwise} \end{cases}\tag{7}\end{equation*}$$ where $L_{gb}$ is the length of the global-best tour.

With the global updating, the convergence can be improved, and the effect of the global-best tour can be reflect. Meanwhile, the local updating can be used to improve the diversity and to avoid the premature phenomena.

C. Max-Min Ant System (MMAS)

Compared with AS, MMAS has two main characteristics. One is that, in MMAS, only the pheromone on the best tour can be updated in each iteration. Another one is the pheromone trail limits.

The pheromone trail update rule is given by

$$\begin{equation*} \tau _{ij} =(1-\alpha)\bullet \tau _{ij} +\Delta \tau _{ij}^{best}\tag{8}\end{equation*}$$ where $\Delta \tau _{ij}^{best} =1/f(s^{best})$ and $f(s^{best})$ is either the iteration-best solution or the global-best solution.

MMAS imposes explicit the minimum pheromone and maximum pheromone, $\tau _{\min }$ and $\tau _{\max }$ , as $\tau _{\min } \le \tau _{ij} \le \tau _{\max }$ . When $\tau _{ij} >\tau _{\max }$ , we set $\tau _{ij} =\tau _{\max }$ , and when $\tau _{ij} < \tau _{\min }$ , we set $\tau _{ij} =\tau _{\min }$ .

The utilization of pheromone trail limits can help to prevent premature convergence and improve the diversity. It can be applied in a different way as well, such as the pheromone reset.

D. Social Group Search Algorithm (SGSA)

Based on the division of labor and the animal rating system, Feng et al. [21] proposed a social group search algorithm (SGSA). According to it, individuals can be classified into four groups with different search strategies as the head, the leaders, the followers and the weak ones.

$\lambda _{i}$ is defined as the decision factor for individual i to assess its influence. Individuals with higher values would rather be a leader than a follower.

Then, $\lambda _{i}$ can be defined in two different ways depending on the methods of evaluation as

$$\begin{equation*} \lambda _{i} =\begin{cases} \raise 0.7ex\hbox {${fit_{i} }$} \!\mathord {\left /{ { \vphantom {{fit_{i} } {fit_{\min } }}}}\right. }\!\lower 0.7ex\hbox {${fit_{\min } }$}& \text {if }\lambda _{i} \text {is directly proportional to }fit_{i} \\ \raise 0.7ex\hbox {${fit_{\min } }$} \!\mathord {\left /{ { \vphantom {{fit_{\min } } {fit_{i} }}}}\right. }\!\lower 0.7ex\hbox {${fit_{i} }$}& \text {if }\lambda _{i} \text {is inversely proportional to }fit_{i} \end{cases}\tag{9}\end{equation*}$$ where $fit_{i}$ is the individual fitness. The best fitness is defined as $fit_{\min }$

The individuals are classified into different groups with varying responsibilities through the decision factor. And individuals in different groups can have different behaviors.

E. Information Entropy

The concept of information entropy was introduced by Shannon [22] in 1948. It can measure the unpredictability of the state. Also, it is one of several ways to measure the diversity.

The entropy can explicitly be written as

$$\begin{equation*} H(X)=-\sum \limits _{i=1}^{n} {P(x_{i})\log _{b} P(x_{i})}\tag{10}\end{equation*}$$ where $b$ is the base of the logarithm used. $P(x_{i})$ is the probability mass function.

The entropy of the unknown result is maximized if each probability is fair.

SECTION III. Entropy-Based Dynamic Heterogeneous Ant Colony Optimization (EDHACO)

In this section, an Entropy-based Dynamic Heterogeneous Ant Colony Optimization (EDHACO) is proposed with dual heterogeneous colonies and a novel communication mechanism called allotropic mechanism. The improved operators used in EDHACO will be introduced in this section as well.

A. Heterogeneous Colonies

In EDHACO, the dual heterogeneous colonies are called as Depth-first population and Breadth-first population. Depth-first population is an improved AS with faster convergence speed. And Breadth-first population is the combination of ACS and MMAS, which can adjust the pheromone adaptively to improve the diversity. They are complementary with each other.

1) Depth-First Population

To improve the convergence and adaptability of AS dynamically, according to SGSA [21], we use the decision factor$\lambda _{i}$ to assess the influence of individual i based on the length, which is called $length_{i}$ . The shorter $length_{i}$ is the better. It should be calculated in real time as

$$\begin{equation*} \lambda _{i} =\frac {length_{i} }{length_{\min } }\tag{11}\end{equation*}$$ where $length_{\min }$ is the length of the iteration–best solution. Then, $R_{i}$ is defined as the group of individual i. It can be determined as $$\begin{equation*} R_{i} =\begin{cases} \text {head }&if~\lambda _{i} =1 \\ \text {leader }&if~1< \lambda _{i} \le LT \\ \text {ordinary }&if~LT< \lambda _{i} \le OT \\ \text {outer }&if~\lambda _{i} >OT \end{cases}\tag{12}\end{equation*}$$ where $\lambda _{i}$ is the decision factor we defined above, and $LT$ and $OT$ are the lower-limit and the upper-limit, respectively.

Let $\tau _{ij}$ be the pheromone intensity of the trail on edge (i,j) when one individual moves from town i to town j. It is updated as (1), and $\Delta \tau _{ij}$ is given by

$$\begin{equation*} \Delta \tau _{ij} =\begin{cases}\dfrac {Q_{1}} {n_{1}} & R_{k} \in \text {head }\\ \dfrac {Q_{2} }{n_{2}} & R_{k} \in \text {leader }\\ \dfrac {Q_{3} }{n_{3}}& R_{k} \in \text {ordinary} \end{cases}\tag{13}\end{equation*}$$ where $Q_{1}$ , $Q_{2}$ and $Q_{3}$ are the constants set for the head, the leader and the ordinary groups, respectively. In the first iteration, the effect of each ant is considered as the same. When we set the value of $Q_{1}$ as 1, the value of $Q_{2}$ and $Q_{3}$ can be calculated as $Q_{2} =Q_{1} {}^{\ast } n_{2} /n_{1}$ , $Q_{3} =Q_{1} {}^{\ast } n_{3} /n_{1}\,\,n_{1}, n_{2}$ and $n_{3}$ are the sizes of the head group, the leader group and the ordinary group, respectively. Except for the size of the head group, all the other groups can vary in size.

As an improved AS, Depth-first population only update the pheromone table at the end of each iteration. It attaches more importance to the sub-best ants than AS, which contributes to a faster convergence speed.

2) Breadth-First Population

To increase the diversity, breadth-first population is proposed. It has the same pheromone strategy as ACS and the similar limit of pheromone as MMAS to avoid the pheromone oversaturation.

In breadth-first population, the local updating is given as (6). And the limit of pheromone should be set as (14)

$$\begin{equation*} \tau _{ij} =\begin{cases} {\tau _{\max } } & {\text {if }\tau _{ij} \ge \tau _{\max } } \\ {(1-\alpha)\bullet \tau _{ij} +\alpha \bullet \Delta \tau _{ij} } & {\text {if }\tau _{\min } < \tau _{ij} < \tau _{\max } } \\ {\tau _{\min } } & {\text {if }\tau _{ij} \le \tau _{\min } } \\ \end{cases}\tag{14}\end{equation*}$$

The pheromone limits can help to adjust the remained pheromone and improve the diversity, and to avoid falling into a local optimum.

B. Allotropic Mechanism

In order to realize the adaptive ACO, we propose a novel entropy-based communication mechanism called allotropic mechanism. As we known, the entropy can be used to measure the diversity. It is calculated as follow:

$$\begin{align*} H_{\max }=&-\sum \limits _{i=1}^{ant~number} {\raise 0.7ex\hbox {1} \!\mathord {\left /{ { \vphantom {1 {ant{ }number}}}}\right. }\!\lower 0.7ex\hbox {${ant\,\,number}$}\log _{2} \raise 0.7ex\hbox {1} \!\mathord {\left /{ { \vphantom {1 {ant\,\,number}}}}\right. }\!\lower 0.7ex\hbox {${ant\,\,number}$}} \\=&-\log _{2} \raise 0.7ex\hbox {1} \!\mathord {\left /{ { \vphantom {1 {ant{ }number}}}}\right. }\!\lower 0.7ex\hbox {${ant~number}$}{ }\tag{15}\end{align*}$$ where $H_{\max }$ is the maximum entropy of the algorithm based on the number of ants. The value of $ant~number$ is number of the solutions we can get in one iteration and $1/ant~number$ is the probability of each solution when they are fair.

In allotropic mechanism, three different communication strategies are applied to improve the performance of EDHACO. These strategies will be used according to the entropy and they follow (16).

$$\begin{align*}&\hspace{-1.2pc}\text {communication strategy} \\&\qquad =\begin{cases}\text {Strategy-1},& \text {if }H_{df} < q_{df} \bullet H_{\max }\\ \text {Strategy-2},& \text {if }H_{bf} >q_{bf} \bullet H_{\max }\\ \text {Strategy-3},& \text {if abs(}H_{df} -H_{bf} {)>}\Delta H\end{cases}\tag{16}\end{align*}$$

$H_{df}$ is the entropy of depth-first population, $H_{bf}$ is the entropy of breadth-first population, and $\Delta H$ is the predefined parameter.

From the description of these two population, we can know that the depth-first population can help to fast the convergence speed, and the breadth-first population should have a good diversity. So the diversity of depth-first population should be smaller than the diversity of breath-first population, which can be reducible to $H_{df} < H_{bf} \le H_{\max }$ . All these strategies are used to adjust the effect of the populations based on entropy to make sure that the convergence and the diversity of the algorithm can be balanced. To implement the function of each population adaptively, $q_{df}$ should be a random number uniformly distributed between 0 to 0.3, and $q_{bf}$ should be set as a number between 0.7 to 1. So that, all these strategies can be used at the right time.

The communication strategies can be defined as follows:

1) Strategy-1

$$\begin{equation*} \begin{cases} \tau ^{df}=\tau ^{bf} \\ \tau ^{bf}=\tau ^{df} \\ \end{cases}\end{equation*}$$ This strategy is used while the diversity of depth-first population is too poor to continue. The pheromone information will be exchanged from each colony, and help depth-first population to improve the diversity and to avoid the pheromone oversaturation. $\tau ^{df}$ is the pheromone matrix of depth-first population and $\tau ^{bf}$ here is the pheromone matrix of breadth -first population.

2) Strategy-2

$$\begin{equation*} \begin{cases} {\tau _{worst}^{bf} =\tau _{best}^{df} } \\ {\tau _{sub-worst}^{bf} =\tau _{sub-best}^{df} } \\ \end{cases}\end{equation*}$$ In order to fast the convergence speed of breadth-first population, the worst solution and the sub-worst solution of breadth-first population should be replaced by the best and sub-best solutions of depth-first population. These information can be reflected by the pheromone on these trails.

3) Strategy-3

$$\begin{equation*} {\begin{cases} {\tau ^{df}=\raise 0.5ex\hbox {$\scriptstyle {H_{df} }$}/\lower 0.25ex\hbox {$\scriptstyle {H_{df} +H_{bf} }$}\bullet \tau ^{df}+\raise 0.5ex\hbox {$\scriptstyle {H_{bf} }$}/\lower 0.25ex\hbox {$\scriptstyle {H_{df} +H_{bf} }$}\bullet \tau ^{bf}} \\ {\tau ^{bf}=\raise 0.5ex\hbox {$\scriptstyle {H_{df} }$}/\lower 0.25ex\hbox {$\scriptstyle {H_{df} +H_{bf} }$}\bullet \tau ^{df}+\raise 0.5ex\hbox {$\scriptstyle {H_{bf} }$}/\lower 0.25ex\hbox {$\scriptstyle {H_{df} +H_{bf} }$}\bullet \tau ^{bf}} \\ \end{cases} }\end{equation*}$$ To balance the diversity and convergence of the algorithm, the pheromone matrix of both the colonies should be set as the same value from the weighting formula based on entropy.

C. Improved Operators

1) Adaptive 3-Opt Operator

The use of traditional 3-Opt local search operator is to select 3 points from the closed loop randomly, then cut off the circle from these points and reconstruct this loop. Thus the chance of getting better solutions can be increased.

From the TSP instance (especially the large-scale TSP instance), we can find that the transition from the suboptimum solution to the optimum solution is based on small adjustments. As shown in Figure 1, the suboptimum solution of kroA100 is described by red solid line, and the blue dotted line stands for the optimum solution. They are similar.

FIGURE 1.

Comparison of the optimum solution and the suboptimum solution in kroA100.

To improve the traditional 3-Opt local search operator, an adaptive 3-Opt operator is designed in this paper. Different from the traditional 3-Opt local search operator, the adaptive 3-Opt operator we proposed is to select one point first. Based on this point, we can decide the range for the selection of the other points, and the range of the selected point can be adjusted according to the iteration. We define the point chosen first as point-A, and then we can calculate the range for the selection of the other two points, which should be defined as point-B and point-C. The calculation formula is given by

$$\begin{align*} range=&\frac {\text {city number}}{2}\ast w \\ w=&\begin{cases} 1 &\text {if 1}\le iteration_{now} \le ^{\mathrm {iteration_{\text {max}}/2}}\\ 0.5 &\text {otherwise} \end{cases}\tag{17}\end{align*}$$

$range$ is designed as a series of labels of the cities. Point-B should be chosen between [point-$\text{A}- range$ , point-A), and point-C should be chosen between (point-A, point-$\text{A}+ range$ ].

At the earlier stage, the selection range is relatively large, and the solution can be modified significantly. At the later stage, the selection range is relatively small, and the local optimization ability of algorithm can be improved. The implementation is shown as Figure 2.

FIGURE 2.

Selection range adaptive 3-Opt operator at different stages. (a) Selection range at the earlier stage. (b) Selection range at the later stage.

2) Dynamic-Pheromone-Reset Operator

The dynamic-pheromone-reset operator is designed to prevent stagnation. When the gained solution is retained over $\gamma$ iterations (where $\gamma$ is the step function based on the iteration), the pheromone table should be reset as the original pheromone table. $\gamma$ is described as

$$\begin{equation*} \gamma =\begin{cases} {value1} & {\text {if }iter\le \text {itersum}/2} \\ {value2} & {\text {if itersum}/2< iter< \text {itersum}} \end{cases}\tag{18}\end{equation*}$$ where $value1$ and $value2$ are the parameter set firstly, $iter$ is the retained iteration and itersum is the maximum iteration.

The dynamic-pheromone-reset operator is used to improve the diversity, and to increase the chance of searching for a better solution.

D. Framework of Proposed Algorithm

To solve the TSPs (especially large-scale TSP), this algorithm is proposed with dual heterogeneous colonies, a novel allotropic mechanism, and the improved operators called the adaptive 3-Opt operator and the dynamic-pheromone-reset operator.

The framework of this algorithm can be described as follow.

Algorithm 1 EDHACO

1)

Initialize the Parameters

2)

while termination condition is not satisfied do

1. Construct solution with Depth-first population and Breadth-first population according to (4) and (5);

2. Apply adaptive 3-Opt operator and Dynamic-pheromone-reset operator in the global best solution;

3. Depth-first population updates pheromone according to (1), (2), (11), (12) and (13);

4. Breadth-first population updates pheromone according to (6) and (14);

5. If the entropy meet the conditions

   Use different strategies to communicate according to Strategy-1, Strategy-2 and Strategy-3;

6. End if

7. NC = NC +1;

3)

End while

In this framework, the number of iteration is nc, the number of ant of the dual colonies are m1 and m2, and the number of city is $n$ .

After the analysis of the framework, we can learn that the time complexity is$O(((n-1)^{\ast } m1+(n-1)^{\ast } m2+n)^{\ast } nc)$ , and the maximum time complexity is $O(n^{\ast } m^{\ast } nc)$ . As we known, The time complexity of AS is $O(n^{\ast } m^{\ast } nc)$ , and the time complexity of MMAS is $O(n^{\ast } m^{\ast } nc)$ as well. So the maximum time complexity of EDHACO is the same with these algorithms and the result shows that this algorithm do not have extra time consumption.

In EDHACO, the entropy-based allotropic mechanism is the core. The entropy can measure the diversity of the algorithm and decide when to and how to communicate adaptively, and the three communication strategies can help to balance the convergence and the diversity. The depth-first population and the breadth-first population in this paper are the heterogeneous colonies, which are complementary with each other. Besides, the improved operators can improve the performance of the algorithm. The adaptive 3-Opt operator can be used to accelerate the convergence and the dynamic-pheromone-reset operator can be used to increase the diversity.

SECTION IV. Parameter Setting

In this section, we will set the parameters of the algorithm for the experiments in the next section.

The decision factor $\lambda _{i}$ can classified individuals into four groups, and it is determined by the upper-limit $OT$ and the lower-limit $LT$ . To get a better combination of these parameters, we apply the two-way analysis of variance test, which can access the main effect of each independent variable and to find whether is any interaction between them, to determine the values of $OT$ and $LT$

In this paper, the two-way analysis of variance test is applied in the TSP instance eil51 and all the experimental results are averaged over 30 independent executions. There are 3 levels for each parameter, they are set as Table 1.

TABLE 1 Level of Two-Way Analysis of Variance Test for EDHACO

Table 2 shows the test results for the two-way variance test. Then, Table 3 and Table 4 show the analysis results and the statistical results. The F-values of the rows and the columns are all much less than their F-crit. It shows that neither of them is significant.

TABLE 2 Test result for the Two-Way Variance Test

TABLE 3 Statistics of the Two-Way Variance Test

TABLE 4 Analysis of the Two-Way Variance Test

From Table 2, we can know that $LT2 \text {X} OT1$ , which means $LT = 1.4$ and $OT= 2$ , is identified as the best-of-breed.

To determine the value of value1 and value2, we have done the pre-experiment of EDHACO in the instance eil51, and the results in Table 6 are averaged over 30 independent executions.

TABLE 5 Level of Pre-Experiment for EDHACO

TABLE 6 Result of Pre-Experiment

The 3 levels of value1 and value2 are set as the values in Table 5, and the results are shown in Table 6.

From the results, we can find that most of results are similar, and the value of value1 and value2 should be set as 5 and 15 as the best combination.

Eventually, from the tests above, the preinstall parameters of different algorithms can be set as the values shown in Table 7. They are used in the follow-up experiments in this paper.

TABLE 7 Parameter Setting for Different Algorithms

SECTION V. Strategy and Operator Analysis of EDHACO

In this section, the impact of each communication strategy and the effect of the improved operators used in EDHACO will be discussed to prove their validity.

A. Allotropic Mechanism Performance Test

The independent experiments have been repeated 10 times in kroB100 and pr152, and the performance of allotropic mechanism can be discussed depending on the experimental results. The allotropic mechanism based on entropy consists of three different communication strategies, and the variable-controlling approach can be used to validate the performance of each strategy and their contribution in EDHACO.

At first, the comparison between these strategies should be made to prove the improvement of each strategy in this algorithm. Figure 3 is the convergence curve of the comparisons in pr152 and kroB100, from which we can find that all the communication strategies in allotropic mechanism have a good effect to optimize the dual colonies algorithms.

FIGURE 3.

Performance comparison between different communication strategies. (a) Convergence curve of different algorithms in kroB100. (b) Convergence curve of different algorithms in pr152.

Next, the statistic results of the five algorithms have been shown in Table 8. It suggests that the complete EDHACO has the better performance than others both in accuracy and stability. Both in kroB100 and pr152, Algorithm_4, which is EDHACO without allotropic mechanism, has the worst performance as this is just a superposition of two single colony algorithms. In Algorithm_4, there is no communication between depth-first population and breadth-first population, and the characteristic of each colony cannot be reflected. Algorithm_1, the EDHACO without Strategy-1, has the better stability than other algorithms except the complete EDHACO, and Algorithm_2, the EDHACO without Strategy-2, has the best accuracy. Algorithm_3 is the balance between Algorithm_1 and Algorithm_2, but its performance is still worse than the complete EDHACO.

TABLE 8 Comparison of Different Strategies by Variable-Controlling Approach

In section III, we can know that Strategy-1 and Strategy-2 are used to improve the performance of each single colony, and Strategy-3 can balance the diversity and convergence of the algorithm to make full use of different characteristics of the heterogeneous colonies. These strategies are complementary and they all contribute to the proposed algorithm.

To prove the effectiveness of the allotropic mechanism, we compare EDHACO with some other dual population algorithms like the Dual Population Ant Colony Algorithm (DPACA) and the Heuristic Communication Heterogeneous Dual Population Ant Colony Optimization Algorithm (HHACO) [8], and the results are shown in Table 9.

TABLE 9 Comparison of Different Dual Population ACOs

The sub-populations of DPACA are used as ACS and MMAS and its performance is worse than other algorithms. The sub-populations of HHACO are AS and IACS, which is the improvement of ACS. It has similar performance with EDHACO, but cannot find the best solution of eil51. From these results, we can know that the dual population ACO has good performance in TSPs and EDHACO is effective. The proposed algorithm has the best precision.

B. Improved Operator Performance Test

In EDHACO, dynamic-pheromone-reset operator and adaptive 3-Opt operator are introduced to improve the performance. The operators proposed in this paper are used as the optimization operators, and they can optimize the results we get from ACO. To validate the effect of these proposed operators, we compare EDHACO and EDHACO without operators in eil51, pr107 and pr152.

From Figure 4, we can find that both the adaptive 3-opt operator and the dynamic-pheromone-reset operator have improved the precision of the solution. The adaptive 3-Opt operator can improve the local optimization ability to reconstruct better solutions without more consumption. And the dynamic-pheromone-reset operator is used to improve the diversity and to increase the chance to search for the better solution. As the combine of them, EDHACO is more likely to get the better solution in TSP instances.

FIGURE 4.

Performance comparison of different improved operators. (a) eil51. (b) pr107. (c) pr152.

SECTION VI. Performance Test of EDHACO

In this section, the performance of EDHACO is discussed and compared with ACS and MMAS to prove its improvement effect.

A. Algorithm Performance Test

According to the parameters set in section IV, the independent experiment in the 10 different TSP instances, such as eil51 and kroA100, should be repeated 10 times. Table 10 shows the statistical results of these independent experiments, which proves that as the improvement of AS, EDHACO has better solution stability and precision.

TABLE 10 Statistical Result of EDHACO in Different Instances

B. Comparison With Other Algorithms

We present computational results from EDHACO in 10 different TSP instances and compare the proposed algorithm with ACS and MMAS in these instances. To ensure a fair comparison, all these algorithms are improved with the adaptive 3-Opt operator and the dynamic-pheromone-reset operator and Table 11 shows the result.

TABLE 11 Comparison of Different Algorithms in 10 TSP Instances

The convergence curve of different algorithms in Figure 5 shows that compared with ACS and MMAS, EDHACO can generally achieve the best performance in all these TSP instances.

FIGURE 5.

The comparison of different algorithms in 10 different TSP instances. (a) eil76. (b) kroA100. (c) kroB100. (d) eil101. (e) kroA150. (f) kroB150. (g) pr152. (h) kroA200. (i) lin318.

From these comparisons, we can find that EDHACO has better performance than ACS and MMAS in such instances. Compared the comparison between ACS, MMAS and EDHACO in Figure 5. (a) and Figure 5. (i), we can find that the algorithm proposed in this paper shows better performance in the large-scale TSP instances than in the small-scale TSP instances. The proposed allotropic mechanism is a kind of communication mechanism with three different strategies based on entropy. The dual heterogeneous colonies are used to emphasize the convergence and diversity respectively. The global search ability and the local search ability can be increased. A better balance between the breadth and the depth of the search can be gained as well. In large-scale TSP instances, the importance of the balance between different characteristics and the adaptability can be better reflected.

The use of the adaptive 3-Opt operator can reduce the crossover segments in the solutions as much as possible. At the later stage, the selection range is relatively small, and the local optimization ability of the algorithm can be improved to reconstruct the better solution. It works better in the large-scale TSP instances. The dynamic-pheromone-reset operator is used to avoid the search stagnation and increase the diversity to search continuously in large-scale TSP instances.

SECTION VII. Conclusion

This paper proposes an Entropy-based Dynamic Heterogeneous Ant Colony Optimization to solve large-scale TSPs. The entropy-based allotropic mechanism is used to balance the convergence speed and the solution diversity, in which the entropy can be used to measure the diversity and to decide when to and how to communicate in this mechanism. It can improve the adaptability. The dual heterogeneous colonies proposed here are the depth-first population, which can improve the diversity, and the breadth-first population, which can fast the convergence speed.

The application of the adaptive 3-Opt operator can dynamically change the selection range of the random points. The problem of poor convergence at the earlier stage is improved. The difficulty of finding the optimum solution at the later stage can be improved as well. The dynamic-pheromone-reset operator avoids the premature convergence and the stagnation behavior. The diversity and the possibility to search for the better solutions can be increased.

Besides, we discuss the impact of the proposed algorithm. The results suggest that EDHACO has good performance in some TSP instances. The strategy analysis and operator analysis of EDHACO are shown in this paper to prove their effectiveness. Compared with ACS and MMAS, EDHACO has better performance with improved stability and good solution precision in especially the large-scale TSP instances.

Furthermore, we will continue the study of other large-scale TSP instances. The study of the connection between different parameters can be focused to improve algorithm performance. Additionally, the mathematical model will be built to enhance the robustness and adaptability of our algorithm. The study of hardware should be started to provide better platform for the research as well [23], [24].