# Enhanced Hyper-Cube Framework Ant Colony Optimization for Combinatorial Optimization Problems
## 2 Ant Colony Optimization Algorithms (ACOs)  
[PERSON] [6] developed the basic Ant Colony Optimization (ACO) algorithm, or Ant System (AS), which is a metaheuristic approach inspired by the collaborative work of ants in finding the source of food. The ants cooperate to find the best possible path from their colony to the food source, Figure 1. Ants search cooperatively using pheromone trails. During their searching tour, the ants communicate by depositing a certain amount of a substance, called the pheromone, on their way to the food site. The following group of ants tends to follow the paths with higher pheromone concentration. Over time, the less selected paths gradually lose information due to the pheromone evaporation process. The virtual ants traveling and selecting paths can be interpreted as a probabilistic selection of certain nodes, of which they are part of the solution, in the path based on the pheromone value. The ACO general procedure is illustrated in Algorithm 1. ```
1:Initialization
2:While (termination criteria not satisfied) Do
3: Construct Solutions Table by Ants
4: Local Search (optional)
5: Global Pheromones Updating
6:End ACO algorithm
```  
**Algorithm 1** Ant Colony Optimization procedure. To understand the mathematical interpretation of ACO, there is a need to go through each step of the ACO procedure shown in Algorithm 1. ACO starts with initial values of the pheromone trail \(\tau_{0}\), set to a small value for all ant trails as this gives all nodes \(j\) of the  
Figure 1: Cooperative search of ants using pheromone trails. design variable \(i\), an equal probability of selection. Next, each ant starts to construct its own solution by applying the rule of selection, which has the following general form:  
\[p_{ij}^{(k)}=\frac{\tau_{ij}^{\alpha}\cdot\eta_{ij}^{\beta}}{\sum_{j\in N_{i}^{k }}\tau_{ij}^{\alpha}\cdot\eta_{ij}^{\beta}}\cdot\forall\;j\in N_{i}^{k} \tag{1}\]  
\(p_{ij}^{(k)}\) represents the probability of selecting the path \(i\)\(j\) for the \(k^{th}\) ant, \(\tau_{ij}\) is the updated pheromone trail, \(\eta_{ij}\) denotes the value of heuristic information for each feasible solution \(s\), \(N_{i}^{(k)}\) indicates the neighborhood nodes of the \(k^{th}\) ant, when it is located at node \(i\) and \(\alpha\), \(\beta\) are the amplification parameters for pheromone trials and the influence of heuristic information on the algorithm behavior, respectively [15]. At the end of each tour, all the pheromone trails are updated through two steps of pheromone evaporation and depositing, according to the following formula:  
\[\tau_{ij}^{k(t+1)}=\ (1-\rho)\cdot\tau_{ij}^{k(t)}+\sum_{k=1}^{n}\Delta\tau_{ij}^{ k(t)} \tag{2}\]  
where \(\rho\) is the evaporation rate, \(\rho\in(0,1]\), and \(\Delta\tau_{ij}^{k(t)}\) is the amount of deposited pheromone by ant \(k(t)\) that could be determined as:  
\[\Delta\tau_{ij}^{k(t)}=\frac{Q}{L_{k(t)}} \tag{3}\]  
where \(Q\) is a constant and \(L_{k(t)}\) represents the distance traveled by ant \(k(t)\). Equation (3) is the basic form of the pheromone trail updating which is used to solve the TSP optimization problem and it could be implemented in more general form:  
\[\Delta\tau_{ij}^{k(t)}=\left\{ \begin{array}{ll}\xi\cdot\frac{f_{event}}{f_{ host}},&\text{if $i,j\;\in\;$global \;$best$ solution}\\ 0,&\text{otherwise}\end{array} \right. \tag{4}\]  
where \(f_{worst}\), \(f_{best}\) are the worst and the best values of the objective function \(f\) obtained by \(N\) ants in tour \(t\) and \(x\) is the global pheromone scaling factor [16]. Eventually, the ACO loop continues until one of the termination conditions is met.