Development of a Convolution-Based Multi-Directional and Parallel Ant Colony Algorithm Considering a Network with Dynamic Topology Changes

Abstract

While network path generation has been one of the representative Non-deterministic Polynomial-time (NP)-hard problems, changes of network topology invalidate the effectiveness of the existing metaheuristic algorithms. This research proposes a new and efficient path generation framework that considers dynamic topology changes in a complex network. In order to overcome this issue, Multi-directional and Parallel Ant Colony Optimization (MPACO) is proposed. Ant agents are divided into several groups and start at different positions in parallel. Then, Gaussian Process Regression (GPR)-based pheromone update method makes the algorithm more efficient. While the proposed MPACO algorithm is more efficient than the existing ACO algorithm, it is limited in a network with topological changes. In order to overcome the issue, the MPACO algorithm is modified to the Convolution MPACO (CMPACO) algorithm. The proposed algorithm uses the pheromone convolution method using a discrete Gaussian distribution. The proposed pheromone updating method enables the generation of a more efficient network path with comparatively less influence from topological network changes. In order to show the effectiveness of CMPACO, numerical networks considering static and dynamic conditions are tested and compared. The proposed CMPACO algorithm is considered a new and efficient parallel metaheuristic method to consider a complex network with topological changes.

1. Introduction

The route generation in a complicated network is a representative NP-Complete problem requiring a non-deterministic solution time with the polynomial increase of problem complexity. It has a number of applications, such as escape route production, and transport optimization. Specifically, in dynamic environment circumstances that cause traffic congestion, such as road construction or traffic accident, the driver’s effective route is subsequently compounded with various dynamic situations. In order to overcome this complexity and to produce an efficient route, various existing studies [1,2,3,4,5,6,7], including Ant Colony Optimization (ACO) [8,9], have been presented, and meta-heuristic algorithms have been applied.

This research proposes an efficient route production algorithm for large-scale networks or mazes, which have a start point and a terminal point, by combining the ACO algorithm with a new distributed algorithm.

The study of Dorigo, Maniezzo, and Colonia [1] presented a meta-heuristic algorithm that produces routes by describing an agent’s traces as a pheromone model using an ACO algorithm. Li and Xiao [2] used an ACO algorithm to search parallel routes by introducing a parameter matrix design method, in order to produce fast escape routes from a maze. Yan and Yuan [3] developed faster routes using the modification of the pheromone renewal rule, by minimizing the pheromone concentration in a blind spot, whenever an ant agent in the maze reached the blind spot. Moreover, Ilie and Badica [4] generated a more efficient route using an exchange of messages among various ant agents. Yoshikawa and Nagura [5] conducted a study to limit ant agents that suddenly behave in an unusual way, minimizing deviations in route production. Moreover, Yoshikawa and Otani [6] presented a study that aimed to limit the possibility of an ant agent being trapped in a dead end. Kim and Lee [7] minimized the escape time using the cooperation of multiple agents to avoid consequent congestion. In the studies mentioned above, all agents used a unidirectional direction-based strategy [1,2,3,4,5,6,7] to produce routes from the start point to the terminal point, in the escape from a maze or large network. However, as the network becomes more complex, more time and computational loads are added to this strategy.

In order to overcome this issue, this research study uses a new and efficient strategy, the “Multi-directional and Parallel Ant Colony Optimization (MPACO)” algorithm, to start agents at any number of points simultaneously, not simply from the start point to the terminal point. The MPACO algorithm supports parallel searches of agents, and uses a Gaussian Processes Regression (GPR)-based pheromone updating method. Specifically, the proposed algorithm generates evacuation routes faster than the previous algorithms in a dynamic network where the topology of the network is transformed due to several reasons, such as traffic congestion or construction.

Section 2 of this research study examines the current ACO algorithms and relevant studies. Section 3 proposes the MPACO framework in a static environment. Section 4 proposes the Convolution-based Multi-directional and Parallel Ant Colony Algorithm (CMPACO) framework that is effective in a dynamic environment. Section 5 analyzes the effectiveness of the proposed framework with the experimental results of ACO, MPACO algorithm, and CMPACO algorithm.

2. Background Knowledge

2.1. Routing Generation Methods and Ant Colony Optimization

The purpose of routing generation is to search for the more effective paths among numerous alternative paths. A number of metaheuristic algorithms have been applied to find more efficient routes.

Table 1. Existing research studies for route generation.

Route Generation Based Research Studies	Applications and Characteristics
Garcia, Tria and Talampas [10]	Particle Swarm Optimization-based Energy efficient route generation to maximize vehicle mileage
Quang, Sanner, Morin and Aoul [11]	Route generation of large-scale networks using genetic algorithm
Yu, Liu, Liu, Hu, Zhang and Xiao [12]	Clustering routing algorithm based on glowworm swarm optimization
Xu, Wang and Sun [13]	Generation of efficient distributed model to reduce communication load using intelligent routing algorithm
Qiu, Zhong, Luo, Liu, Luo and Jiang [14]	Power distribution network routing generation using ACO

summarizes several existing meta-heuristics and the relevant applications to generate more efficient routs in complex networks.

Among a number of meta-heuristic algorithms, swarm-based optimization methods [10,12,14] have been widely used for more efficient route generations. One of the representative swarm-based optimization is ACO. ACO is an algorithm derived by Dorigo [15,16], based on the cooperative behavior of ants in finding the shortest route from their colony to the food location.

Table 2. Several applications using Ant Colony Optimization.

Research Studies Using ACO	Application Fields
Dorigo, Maniezzo, Colorni and Trubian [17]; Arnaout, Musa and Rabadi [18]; Chen, Lo, Wu and Lin [19]	Transportation and scheduling issues
Dorigo and Gambardella [20]; Oh and Lee [21]	Efficient route production
Ahmadizar, Barzinpour and Arkat [22]	Permutation flow shop scheduling problem
Dorigo, Maniezzo and Colorni [1]	Traveling salesman problem
Reza, Mahfujur, Abdur, Wail and Abdulmotaleb [23]	Wireless sensor network design
Maniezzo and Colorni [24]	The quadratic assignment problem

shows that the algorithm has been utilized as one of the meta-heuristics in solving the route problem in complex and difficult networks.

In a general ACO algorithm, each ant acts as an artificial agent that moves to the target probabilistically. At each step, the agent moves based on the graph topology of the problem, deposits the pheromone, and updates the pheromone amount, using iterations to increase the probability of the optimal route production.

Figure 1a depicts how agents move to produce an efficient route using ACO in a multilayered graph. All agents start at the same position (e.g., the Ant Colony) at the beginning of each iteration. However, agents in Figure 1b are initially located at random places, and search for the shortest path more efficiently. Section 3 provides the detailed process and method.

The agents (the number of agents = AN) move from the first layer, the ant colony, up to the last layer, the food location. In each destination point, an agent can select one of the directly connected neighbor nodes, and diffuses its pheromone. The route is stronger as the concentration of pheromone is stronger.

$${\mathrm{P}}_{ij}^{\left(k\right)}=\frac{{\tau }_{ij}}{{\sum }_{j\in N_{ij}^{\left(k\right)}}{\tau }_{ij}},ifj\in N_i^{\left(k\right)}$$

(1)

In Equation (1), ${\mathrm{P}}_{ij}^{\left(k\right)}$ denotes the probability that the $k^{th}$ ant moves from node $i$ to node $j$, $N_i^{\left(k\right)}$ denotes the set of all movable nodes directly connected to node $i$, and ${\tau }_{ij}$ is the pheromone deposited in the route from node $i$ to node $j$.

$$f_k={\sum }_{i\in S}{\sum }_{j\in S}\sqrt{{\left(x_i-x_j\right)}^2+{\left(y_i-y_j\right)}^2},k=1,2,\dots ,N$$

(2)

Equation (2) indicates the cost function (${\mathrm{f}}_k$) when the $k^{th}$ ant goes from node $i$ to node $j$. $S$ is the set of all nodes passed by the $k^{th}$ ant. When the $k^{th}$ ant is at node $i$, the coordinates are presented as $\left(x_i,y_i\right)$; and when it is at node $j$, the coordinates are presented as $\left(x_j,y_j\right)$.

$$f_{best}=\underset{k=1,2,\dots ,N}{\min }{f}_k$$

(3)

$$f_{worst}=\underset{k=1,2,\dots ,N}{\max }{f}_k$$

(4)

The optimal route (Equation (3)) and the worst route (Equation (4)) between routes selected by the $k^{th}$ ant are determined. When $f_{best}$ is determined at one iteration count, the algorithm updates the deposited pheromone for the next iteration. The updated pheromone is used as a guide to search for the future route of other ants.

As shown in Equations (5) and (6), the ants deposit more pheromone on the selected route, using Equations (2) and (3). This enhanced route is used as a key indicator to the preferred route in future route selection by other ants. Longer routes that do not attract attention are reduced relative to pheromone evaporation as shown in Equation (7), and the pheromone in each route is updated as learning processing.

$${\tau }_{ij}\leftarrow {\tau }_{ij}+{\sum }_{k=1}^N\Delta {\tau }_{ij}$$

(5)

$$\Delta {\tau }_{ij}=\{\begin{array}{ll}\frac{\complement f_{best}}{f_{worst}}, & if \left(i,j\right)\in global best tour\\ 0& otherwise\end{array}$$

(6)

$${\tau }_{ij}\leftarrow \left(1-\rho \right){\tau }_{ij}$$

(7)

In Equation (6), $\complement$ is a parameter to control the scale of the pheromone updated as an ant moves, while in Equation (7), $\rho$ is a pheromone decay parameter. The pheromones of all the route evaporate, as shown in Equation (7). The pheromone of the route with the minimum objective function value is updated, as shown in Equation (5). The renewal amount of pheromone is determined using Equation (6) with $f_{best}$ and $f_{worst}$. Closest nodes with fewer objective function values are selected using these pheromone updating processes. Finally, the algorithm generates the efficient solution route.

While a number of research studies have applied the ACO method to relevant application fields, it is limited in a complex network with dynamically changing topology. This research proposes the MPACO and CMPACO methods. The detailed algorithms are provided in Section 3 and Section 4. The following subsection explains the Gaussian Process Regression (GPR) method, which the proposed method uses for estimating and updating pheromones.

2.2. Gaussian Processes Regression

GPR [25,26,27] is one of the representative nonparametric Bayesian algorithms. GPR is a technique of estimating and updating the frequency of occurrence, using a Gaussian nonlinear distribution function with a mean function and a covariance function. GPR algorithm has been used in many research fields, as provided in

Table 3. Research applications using GPR.

Research Studies Using GPR	Application Fields
Ak, Ergonul, Sencan, Torunoglu and Gonen [28]	The time and space prediction of an infectious diseases
Luttinen and Ilin [29]	Sea level temperature reconstruction
Nguyen and Peters [30]	Kinetics model estimation
Nguyen, Hu and Spanos [31]	Efficient building field formation by estimating indoor environment fields
Chen, Qian, Meng and Nabney [32]	Wind prediction for energy efficiency

.

GPR has been used in many fields, as it has high prediction measurement for changing environment based on a Bayesian framework, and enables probabilistic analyses using Gaussian distribution.

Figure 2 illustrates the process for estimating the final output value $Y_{*}$ using an $f_{*}$ at the input value $X_{*}$ after producing the intermediate value $f_i$ by Bayesian renewal to convert the input value $X_i$ to the observed value $Y_i$.

Equations (8)–(11) summarize the general GPR model.

$$\begin{array}{c}\mathrm{y}=f+ϵ,\\ \mathrm{where},ϵ~\mathrm{N}\left(0,{\mathsf{\sigma }}_{\mathrm{y}}^2\mathrm{I}\right)\end{array}$$

(8)

$$\mathrm{D}=\left\{\left(X_i,Y_i\right),\mathrm{i}=1,\dots ,\mathrm{a}\right\}$$

(9)

$$\begin{array}{c}f~\mathrm{GP}\left(\mathrm{m}\left(X\right),\mathrm{k}\left(X,X_{*}\right)\right)\\ \mathrm{where}\mathrm{m}\left(X\right)=\mathrm{E}\left[f\left(X\right)\right]\\ \mathrm{and}\mathrm{k}\left(X,X_{*}\right)=\mathrm{E}\left[\left(f\left(X\right)-\mathrm{m}\left(X\right)\right)\left(f\left(X_{*}\right)-\mathrm{m}\left(X_{*}\right)\right)\right]\end{array}$$

(10)

In Equation (8), $ϵ$ is a noise parameter with a mean of 0 and a variance of ${\sigma }_y^2$ subsequent to the Gaussian distribution, and $I$ is an Identity matrix considering the data dimension. Equation (10) is the “distribution over functions” [33] for converting to the target value $Y$, if $\mathrm{a}$ training data is assigned with input vector $X$ and output vector $Y$ as shown in Equation (9), which is a Gaussian process distribution modeled with mean $\mathrm{m}\left(X\right)$ and variance covariance $\mathrm{k}\left(X,X_{*}\right)$. $\mathrm{k}\left(X,X_{*}\right)$ is a covariance function ($\mathrm{cov}\left(f\left(X\right),f\left(X_{*}\right)\right)=$), and indicates the similarity measure between both data. In general, a special kernel function is modeled as a radial basis kernel of Equation (11).

$$\mathrm{k}\left(X,X_{*}\right)=\exp (-\frac{1}{2}|X-X_{*}{|}^2)$$

(11)

Equation (10) can be mapped to Equation (12) with the condition of the absence of noise, and then the pre-distribution is expressed as Equation (13).

$$f_{*}~\mathrm{N}\left(0,\mathrm{k}\left(X_{*},X_{*}\right)\right)$$

(12)

$$\left[\begin{array}{c}f\\ f_{*}\end{array}\right]~\mathrm{N}\left(0,\left[\begin{array}{c}k\left(X,X\right) k\left(X,X_{*}\right)\\ k\left(X_{*},X\right) k\left(X_{*},X_{*}\right)\end{array}\right]\right)$$

(13)

However, the value obtained by the measurement of the actual data contains noise in general. In this manner, the $Y$ value is expressed as Equation (14).

$$Y~\mathrm{N}\left(0,\mathrm{k}+{\sigma }_y^2\mathrm{I}\right)$$

(14)

This indicates that the estimated $Y$ using a general GPR model follows the attributes of multivariate normal distribution with mean 0 and covariance $\mathrm{k}+{\sigma }_y^2\mathrm{I}$. This derived GPR model is used as a prediction model using Bayesian framework.

When the function value $f_{*}\left(X_{*}\right)$ is predicted for the test data $X_{*}$, the pre-distribution for $f_{*}\left(X_{*}\right)$ considering the occurring noises is modeled using Equation (15).

$$\left[\begin{array}{c}Y\\ f_{*}\end{array}\right]~\mathrm{N}\left(0,\left[\begin{array}{cc}k\left(X,X\right)+{\sigma }_y^{2}I& k\left(X,X_{*}\right)\\ k\left(X_{*},X\right)& k\left(X_{*},X_{*}\right)\end{array}\right]\right)$$

(15)

Using the newly updated Gaussian process, the derived Maximum Likelihood Estimator (MLE) and its variance follow Equations (16) and (17), respectively.

$$\overline{f_{*}}=\mathrm{k}{(X_{*},X)}^T{(\mathrm{k}\left(X,X\right)+{\sigma }_y^2\mathrm{I})}^{-1}Y$$

(16)

$$\mathrm{V}\left[f_{*}\right]=\mathrm{k}\left(X_{*},X_{*}\right)-\mathrm{k}{(X_{*},X)}^T{(\mathrm{k}\left(X,X\right)+{\sigma }_y^2\mathrm{I})}^{-1}\mathrm{k}\left(X,X_{*}\right)$$

(17)

This research uses the introduced GPR framework for connecting and estimating the pheromones of paralleled agents. Section 3 provides the detailed framework and algorithms of MPACO algorithm using the GPR pheromone updating method.

3. Multi-Directional and Parallel Ant Colony Optimization (MPACO)

MPACO algorithm orients “multiple directional searches”, in which each group of ants start at any point, as opposed to the ACO algorithm, where all agents start from the same start point (Ant Colony). Moreover, MPACO algorithm has the characteristic of “parallelism”, in which each agent searches in multiple directions simultaneously.

This section explains how MPACO works in a static network environment. Figure 3 illustrates the detailed procedures of the MPACO algorithm.

Figure 3a depicts the initial situation of the MPACO algorithm. The agents of each group start at the start point and the terminal point as usual, not just the start point of the maze. If the number of groups (randomly selected starting points) is $v$, each group is composed of $AN/v$ agents, where $AN$ is the number of overall agents. When the agents from different groups often occur together with each other in a node, this node is defined as a collision node ($q$). The existence of the collision node implies that the node may have a higher probability to be used as one of the paths. For this reason, when the collision node is detected, the pheromone is diffused and calculated.

The pheromone value is estimated using a GPR-based updating method. As shown in Figure 3b, the collision node $q$ is detected, and the amount of pheromone (Figure 3c) is adjusted using a GPR around the collision node. Equation (18) defines the GPR-type pheromone distribution D, where $X$ denotes a node belonging to radius $w$ in the detected collision node.

$$\mathrm{D}\left(Y_{*}\right)~\mathrm{N}\left(\mathrm{m}\left(X\right), \mathrm{k}\left(X,X_{*}\right)\right)$$

(18)

$${\mathrm{M}}^{\left(int\right)}=\underset{\forall \left(i,j\right)\in A}{\arg }·\max {\mathsf{\tau }}_{ij}$$

(19)

Equation (18) is derived using the prediction procedure provided in Section 2.2. The pheromone value $(Y_{*})$ of node $X_{*}$ is predicted based on the GPR, and used as the updated pheromone value. The parameter radius w depends on the characteristics of the problem. This research study uses 2 as the value for each experimental measurement.

After updating the pheromone, a new node (Equation (19)) with the highest pheromone in the network is selected. The node selected is called an intermediate node (${\mathrm{M}}^{\left(int\right)}$), as shown in Figure 3d. The reasoned ${\mathrm{M}}^{\left(int\right)}$ node is added as a new starting node of the agents, as shown in Figure 3e, and additional collision nodes (Figure 3f) are detected in the following iteration. Then, the GPR-type pheromone is updated at the additional nodes, as shown in Figure 3g, using Equation (18). Finally, the strongest pheromone points are linked with each other, and determine a final effective route, as shown in Figure 3h.

When an agent diffuses pheromones in the shortened route using the cost function, MPACO algorithm with collision nodes and intermediate nodes generates the route to the large network faster and more efficiently than ACO algorithm. When these collision and intermediate nodes are not found, the MPACO algorithm follows the route search procedure of the ACO algorithm.

Figure 4 depicts a flowchart of MPACO algorithm that produces an optimal candidate route. As shown in Figure 4, two collision nodes are detected in the initial searches. Then, the intermediate node is reasoned using the GPR rule. The node is registered to starting node lists. Then, the final route is completed using the same iterations.

Table 4. Comparison of the computation speed between ACO and MPACO.

	ACO	MPACO
Iterations	1	1
Computation speed (Agents’ Total Movement)	70.64	61.64

summarizes the comparison of the computation speed using ACO and the proposed MPACO. The network as shown in Figure 4 is used as a test network. Four ants are used in both algorithms, and the optimal paths are obtained in one iteration.

Table 4 shows that the overall agents’ movement using ACO is longer than the movement using MPACO. This indicates that the computation speed of MPACO is faster than the speed of ACO.

Algorithm 1 explains the route search algorithm for detecting a collision node. As explained with the illustrations, initial agents are divided into two groups, which start at the S-node and T-node, respectively.

Algorithm 1. Route search algorithm for detecting a collision node.

Initialize: Current iteration→ $int$ Overall number of agents → $AN$ for k=1 to $AN/2$ Ants start from $S$ node and $T$ node ($S$ node has $AN/2$ ants, and $T$ node has $AN/2$ ants). Choose the next node using a ${\mathrm{P}}_{ij}^{\left(k\right)}$. (Equation (1)) end for When ants in different groups meet in a node, it is classified as a collision node (q). If (the existence of q == false) Go to Algorithm 2. else Go to Algorithm 3. end if

When a collision node is not detected, MPACO follows the procedures of ACO algorithm, as shown in Algorithm 2.

Algorithm 2. Route search in the case of the non-existence of a “collision node”.

Initialize: Evaporation rate $\mathsf{\rho }\in \left(0,1\right]$ The objective function is to minimize the distance of the route where the ants are moved (Equation (2)). Combine the distances moved in each section. Choose the optimal candidate route $f_{\mathrm{best}}$ (Equation (3)). Evaporate the pheromones (Equation (5)). Update the pheromones on $f_{\mathrm{best}}$ route (Equation (6)). return Algorithm 1

When a collision node is detected, the GPR-type pheromone amount is estimated and updated with Algorithm 3.

Algorithm 3. GPR based Pheromone renewal Algorithm.

Initialize: Radius w $\in {\mathrm{I}}^{+}$ In the q node, all nodes in the radius w = $X$ Y = the pheromone values of the $X$. Input: Training data point { $X$, $Y$ } GPR is applied to predict test data $X_{*}$ and $Y_{*}$ (Equation (18)). Update pheromone with $Y_{*}$ value on $X_{*}$ node. Choose the ${\mathrm{M}}^{\left(int\right)}$ node with the highest pheromone value (Equation (19)). Go to Algorithm 4.

Then, the subsequent process is to find an intermediate node (${\mathrm{M}}^{\mathrm{int}}$) with the highest pheromone value near a collision node. The reasoned ${\mathrm{M}}^{\mathrm{int}}$ is listed as another starting node, and agents start their search with an updated starting node list (${\mathrm{M}}^{\left(\mathrm{int}+1\right)}$), as shown in Algorithm 4. The updated node list (${\mathrm{M}}^{\left(\mathrm{int}+1\right)}$) at the following iteration (int+1) includes the initial starting point (S-node) and the target node (T-node). If the number of nodes in ${\mathrm{M}}^{\left(\mathrm{int}+1\right)}$ is greater than the number of overall agents (AN), additional detection processes for collision nodes and intermediate nodes are stopped. The numerical analyses using the proposed algorithm are provided in Section 5.1.

Algorithm 4. Route generation Algorithm with an intermediate node (${\mathrm{M}}^{\left(\mathrm{int}+1\right)}$).

Initialize: Current iteration→ int+1 number of ${\mathrm{M}}^{\left(int+1\right)}$ → v for k=1 to AN/v Ants start from all ${\mathrm{M}}^{\left(int+1\right)}$ nodes that are detected. Choose the next node using ${\mathrm{P}}_{ij}^{\left(k\right)}$ (Equation (1)). end for

4. Dynamic Configurable Network and Convolution-Type Multi-Directional and Parallel Ant Colony Optimization (CMPACO)

While the previous section shows the effectiveness of the proposed network with networks with static topology, a number of real networks have dynamic changes in their topologies and configurations due to various reasons, such as route constructions and heavy traffic jams. An algorithm that constructs an efficient route in a dynamic network has been used in many research fields, as provided in

Table 5. Research applications on dynamic networks.

Research Studies on Dynamic Networks	Application Fields
Eklund, Kirkby and Pollitt [34]	Use dijkstra’s classic double bucket algorithm to find the network route
Giraldal, Rodriguez, Pernas, Higuera, Ortega and Zarzuela [35]	Intelligent system for transport fleet management
Noto and Sato [36]	Route search for car navigation systems using the extended dijkstra algorithm
Moss and Segall [37]	Optimal control theory to the problem of dynamic routing
Cauvery and Viswanatha [38]	Generate the shortest route applied ants algorithm and genetic algorithm

. The changes of network topologies for learning processes have resulted in low performances of the existing algorithms. This section provides a variation of the MPACO algorithm that overcomes the issue, and explains how it works.

Although the MPACO algorithm is more successful than the ACO algorithm in static network environments, dynamic changes in network topologies might invalidate the pheromone-based route reasoning using the learning processes of MPACO. In order to overcome this issue, a new and efficient dynamic network framework (Convolution-type Multi-directional and Parallel Ant Colony Optimization (CMPACO) algorithm) is proposed. The new algorithm uses a discrete Gaussian convolution. Figure 5 illustrates how the pheromone is renewed when the collision nodes are detected using the proposed CMPACO algorithm.

As shown in Figure 5a, when a collision node is detected, the algorithm examines another collision node that shares the area within the given radius $\mathsf{\alpha },\mathsf{\beta },\mathsf{\gamma }$. The pheromone at each collision node is modeled as a step-based Gaussian distribution, as shown in Equation (20). Equation (20) is a discrete Gaussian distribution with mean 0 and standard deviation according to the discrete ranges ($\mathsf{\alpha },\mathsf{\beta },\mathsf{\gamma }$) of the converted radius, while ‘$t$’ is a parameter for controlling the concentration of diffused pheromone values.

$$f\left(x\right)=\frac{t}{\sqrt{\left(2\pi \ast \sigma \right)}}ex{p}^{-\frac{1}{2\ast {\sigma }^2}{x}^2}, \{\begin{array}{l}x=\alpha , 0<x\le \alpha \\ x=\beta , \alpha <x\le \beta \\ x=\gamma , \beta <x\end{array}, 0<\mathsf{\alpha }<\mathsf{\beta }<\mathsf{\gamma }$$

(20)

Then, pheromones in the shared regions are synthesized with the convolution of both the step-based Gaussian distributions, as shown in Figure 5b.

As shown in Figure 6, the pheromone amount of A, B, and C in radii $\mathsf{\alpha },\mathsf{\beta }$, and $\mathsf{\gamma }$ at node $q$ are modeled using Equation (21).

$$\{\begin{array}{l}{\tau }_{ij}\leftarrow A, if \left(ij\right)\in \pi {\alpha }^2\\ {\tau }_{ij}\leftarrow B, if \left(ij\right)\in \pi {\beta }^2-\pi {\alpha }^2\\ {\tau }_{ij}\leftarrow C, if \left(ij\right)\in \pi {\gamma }^2-\pi {\beta }^2\end{array}$$

(21)

Then, the pheromone convolution between both collision nodes is executed using Equations (20) and (21). Figure 7 shows the pheromone convolution using both discrete Gaussian distributions.

The subsequent processes follow the processes of MPACO. While MPACO algorithm purses a node with the highest pheromone using the GPR process, topology changes in a target network might lead to mis-estimated nodes. However, the proposed CMPACO uses the discrete additions of the amount of diffusion of each pheromone when multiple collision nodes are located within a close radius, as shown in Figure 7. The comparatively simple convolution-based node selection is influenced less by the dynamic changes in network topology. Then, it makes the finding of the effective route more robust against small network changes in the learning process. Section 5.2. provides the effectiveness of the proposed CMPACO algorithm with the examples of the dynamically changing networks

5. Numerical Studies and Performance Analysis of MPACO and CMPACO

5.1. Performance Comparisons of MPACO and ACO

This section provides the performance comparisons between ACO and the proposed algorithm; MPACO under networks with fixed topology. As explained in the previous section, the MPACO algorithm has the advantage of generating an efficient route faster than ACO algorithm in a large network, by simultaneously searching for routes in multiple directions, and updating pheromones based on GPR. In order to verify the validity of the proposed algorithm, numerical experiments and analyses under labyrinth type networks are provided and compared with ACO algorithm.

Table 6. Experimental conditions and assumptions.

Type	Detailed Assumptions
Condition No.1	The same number of ants is used in both ACO and MPACO tests.
Condition No. 2	The locations for ant colony and food location are the same in each network for both cases.
Assumption No. 1	When ants in different groups meet each other in a node, the ants stop moving.
Assumption No. 2	When the ants reach the wall/block of the maze, they go back to find another route.

and

Table 7. Parameters and their values for experiments.

Variable	Value
Evaporation rate ($\mathsf{\rho }$)	0.5
Initial pheromone (${\tau }_{ij}$)	1
Number of ant (AN)	12

summarize the conditions and the assumptions for the numerical experiments conducted and the parameters used.

Table 8. The test platform.

Platform	Parameters
System Version	Windows 10 Pro. 64-bit
CPU	Intel(R) Core (TM) i7-4870HQ @ 2.50GHz
RAM	16GB

shows the test platform parameters.

Figure 8 illustrates the tested network, and how the intensity of pheromone is strengthened during the iterations using the proposed MPACO algorithm. As shown in Figure 8a–d, the x and y axes are the coordinates of the node, and the z axis indicates the amount of pheromone. The explained GPR process is applied in every iteration, and the pheromone is deposited around the collision nodes. As a result, it can be seen that the route from each start node to the terminal node is searched effectively.

Figure 9 illustrates the change of the cost function value in each iteration using ACO and MPACO, where the x axis indicates the number of iterations, and the y axis the route distance from the start node to the terminal node.

Figure 9 shows that the proposed MPACO algorithm produces the optimal routes much faster than ACO algorithm.

Table 9. Computation time comparison between ACO and MPACO.

Test Framework	Iteration	Computation Time
ACO	32	19.16(s)
MPACO	5	4.92(s)

summarizes the computation time comparison between both algorithms.

In order to show the effectiveness of the proposed algorithm, various networks are tested, as shown in

Table 10. Test comparison with various networks.

Map	Iteration	Route Search Time
		ACO	MPACO
	100	18.96(s)	12.98(s)
	100	24.91(s)	16.41(s)
	100	27.63(s)	19.21(s)

. The tests using various networks provide the effectiveness of the proposed MAPCO framework compared to the existing ACO algorithm.

5.2. Performance Analyses of CMPACO Considering Dynamic Network Topology

In order to verify the validity of the proposed CMPACO algorithm, numerical experiments are conducted on the dynamic changes of network topology, where during the learning process, a portion of the network changes. As shown in the previous section, the topology of the network often changes due to the sudden congestion that in real applications is often caused by road construction. The tests with CMPACO are analyzed and compared with tests with the ACO algorithm and MPACO algorithm. The test conditions and assumptions follow the descriptions in Table 6 and Table 7 of Section 5.1.

For the comparison with the previous methods used, the route topology of the maze is set to change after every (30 and 60) iterations to describe a network with a dynamic topology change. $\mathsf{\sigma }$ and $t$ in Equation (20) are modeled in this experiment with (1.4 and 5), respectively. As shown in Figure 10, a network has two topological changes during the learning processes.

Figure 11 depicts the amount of final pheromone using MPACO and CMPACO algorithm in the dynamically changing maze.

Figure 11 shows that the x and y axes are the node coordinates on the final network, and the level contour indicates the amount of finally formed pheromones. In the case of the MPACO algorithm (Figure 11a), the pheromone distribution is strong, primarily at the start point; however, the pheromone is low in the movement route. This observation indicates that MPACO is not effective in generating the final route considering dynamical topology changes. On the other hand, in the case of the CMPACO algorithm (Figure 11b), a comparatively strong pheromone is formed around the movement route.

Table 11. Computation time comparisons among ACO, MPACO and CMPACO.

Test Framework	Iteration	Computation Time (Unit: Seconds)
ACO	100	17.15
MPACO	100	25.81
CMPACO	100	9.88

summarizes the results of applying ACO, MPACO, and CMPACO. The results show that the proposed CMPACO has better performances than other algorithms in a network environment with variable topology. The test platform parameters follow Table 8.

Figure 12 illustrates comparisons of the cost function values using ACO, MPACO, and CMPACO algorithms in the network. Each dotted line indicates the time when the topology changes.

Taking into account the case of the ACO algorithm, the route search for the shortest distance takes the longest time in all dynamic environments. In the case of the MPACO algorithm, the performance of MPACO is more unstable than that of the proposed CMPACO algorithm.

The MPACO algorithm updates the pheromone around the collision node by applying the GPR whenever the route changes in a dynamic environment. Then, there is a high probability that the collision node will fail to predict the amount of pheromone in the neighboring node, due to the sudden change. It is impossible to predict a new collision node caused by a dynamic network topology change and the pheromone of a changed route. In addition, an effective route cannot be produced by predicting the pheromone distributed in the previous collision node.

However, the CMPACO algorithm updates the pheromone value discretely from the collision node to the radius node. As explained previously, CMPACO’s discretized pheromone convolution is influenced less by the changes of network topology. The provided numerical example shows the effectiveness of the proposed algorithm, particularly when searching a complex maze with dynamic topology changes.

In order to compare algorithms’ performances, a number of networks with dynamic topological changes are tested using ACO, MPACO and CMPAO. As shown in Figure 13a,b, two more networks are configured with two dynamical topologies during the learning processes.

Figure 14 shows the changes of the objective function value per iterations with the networks shown in Figure 13a.

As shown in Figure 14, CMPACO shows the best performances per each change of the network topology, compared to ACO and MPACO.

Table 12. Computation time comparisons among ACO, MPACO and CMPACO.

Test Networks	Computation Time for the Best Result
	ACO	MPACO	CMPACO
Test network 1	15.82(s)	17.33(s)	10.45(s)
Test network 2	18.98(s)	20.55(s)	10.50(s)

compares each computation time for the final best routs using ACO, MPACO and CMPACO. As shown in Figure 14 and Table 12, these numerical studies show that the proposed CMPACO has better performances for network path generation considering dynamic network topology changes.

6. Conclusions and Further Studies

The path generation from the start node to the target node in a complex network is a representative problem that has been steadily investigated in the field of network optimization and machine learning. While most algorithms, including ACO, use a unidirectional search in a serial manner, the computation takes a long time as the complexity increases, with the drawback that it fails to search the route effectively in a dynamic environment.

In order to overcome these issues, the MPACO algorithm is proposed to search for an effective path by updating the pheromone through a Bayesian-type GPR process at the node where ant agents search multi-directionally. The numerical studies show the greater effectiveness of the MPACO algorithm than the existing ACO and the greater the complexity of the network, the more efficient it is. However, while the MPACO algorithm generates the route faster than the ACO algorithm in a static environment, the renewal process of the pheromone fails to recognize the neighboring nodes’ topology changes in the network.

This issue is overcome using the proposed CMPACO framework, which updates the pheromone by interpolating discrete Gaussian distributions at the collision node. In order to verify the effectiveness of the proposed algorithm, it is compared to the ACO algorithm and the MPACO algorithm. The experimental results show that the presented CMAPCO algorithm offers better performance than the ACO algorithm and MPACO algorithm, with respect to the computation speed and the optimized cost function.

The proposed framework can be applied to various network route problems with complex and dynamic topology changes and to real road networks. As further studies, more effective meta-heuristic algorithms and pheromone diffusion algorithms can be considered for much quicker path generation.