# Determining the Optimum Section of Tunnels Using Ant Colony Optimization

Authors: S. Talatahari
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

Ant colony optimization is developed to determine optimum cross sections of tunnel structures. Tunnel structures are expensive infrastructures in terms of material, construction, and maintenance and the application of optimization methods has a great role in minimizing their costs. This paper presents the formulation of objective function and constraints of the problem for the first time, and the ant colony optimization, as a developed metaheuristic approach, has been used to solve the problem. The results and comparisons based on numerical examples show the efficiency of the algorithm.


---

## Body

## 1. Introduction

In general, the optimization techniques can be categorized into classical and metaheuristic search methods. Classical optimization methods often require substantial gradient information, the final results depend on the initially selected points, and many engineering problems are too complex to be handled with classical methods [1–3]. However, metaheuristic methods do not require the gradient data and perform better global search abilities [4–8].Among many exiting metaheuristics, there are few algorithms that present many results (instead of only one best result). The ant colony optimization (ACO) was one of them. In the design of tunnel, engineers need to have many different designs to combine/select/improve them as the final result. Therefore, we select ACO in this paper. Previously, ACO has been applied to water distribution system optimization [9], optimal design of open channels [10], optimization of soil hydraulic parameters [11], identifying optimal sampling networks that minimize the number of monitoring locations in groundwater design optimization [12], and deterring the optimum design of skeletal structures with optimum weight [2], among many others. The advantages of applying ACO to engineering problems are similar to those of other evolutionary algorithms. It is a multiagent randomized search technique in which in each cycle a number of search space points are selected and tested. The random selection and the information obtained in each cycle are used to choose new design vectors in subsequent cycles.On the other hand, the necessity for tunnels and the benefits they bring cannot be overestimated. Tunnels improve connections and shorten lifelines. The utilization of underground space for storage, power and water treatment plants civil defense, and other activities is often a must in view of limited space, safe operation, environmental protection, and energy saving [13]. Of course, the construction of tunnels is risky and expensive and requires a high level of technical skill [13]. There are many methods proposed in the community for the modeling of the complex problem and geometrical structures [14–16]. For the first time, this paper presents the formulation of tunnel cross-sectional design problems and utilizes ant colony optimization to determine the optimum section of tunnels.


## 2. Formulation of the Optimization Problem

### 2.1. Problem Statement

There are different shapes or profiles for a tunnel cross section. The choice of the profile aims at accommodating the performance requirements of the tunnel. Moreover, it tries to minimize bending moments in the lining (or displacements) as well as costs for excavation and lining [13]. Therefore, the objective function can be defined as
(1)minimizeA+φd,
where A is the area of the profile, and d is the maximum value of displacements. Also,  φ is a constant parameter.A typical problem of tunnel design is to fit two rectangles (one is required as a traffic space, and the other is required as air conductor space) into a mouth profile as shown in Figure1. The figure shows two types of cross sections: in Figure 1(a), for a determined height (Hd), a vertical wall is considered, while in Figure 1(b), the vertical wall is not utilized. For both types, the design functions of crown should be determined.  Based on the kind of the selected function for crown, different shapes of profiles will be achieved. Here, we utilized the polynomial functions. As a result, the aim of optimization problem is to determine the parameters of the crown polynomial functions. The value of Hd for profile type I should be also considered as a variable. The geometry constraints of a such problem can be summarized as follows.The different profiles of tunnel cross sections.
(a)
(b)For the profile with vertical wall (type I):(2)Hdmin≤Hd≤Hdmax,Hreq≤H1,Breq≤B1,As+Breq×Hreq≤A.For the profile without vertical wall (type II):(3)Breq≤B1,As+Breq×Hreq≤A,
where Hreq and Breq are the required height and width of traffic space, respectively. min and max denote lower and upper bounds, respectively. As is the required space for the air conductor.


### 2.2. Constraint Handling Approach

There are different methods to handle the constraints [16–18]. One of well known approaches to handle constraints is to employ a penalty function. In utilizing penalty functions, if the constraints are between the allowable limits, the penalty is zero; otherwise, the amount of penalty is obtained by dividing the violation of allowable limit to the limit itself, as
(4)Hreq≤H1⇒ΦH=0,Hreq>H1⇒ΦH=H1-HreqHreq,Breq≤B1⇒ΦB=0,Breq>B1⇒ΦB=B1-BreqBreq,As+Breq×Hreq≤A⇒ΦA=0,As+Breq×Hreq>A1⇒ΦA=A-(As+Breq×Hreq)As+Breq×Hreq,
and the total value of the penalty functions equals
(5)Φ=ΦH+ΦB+ΦA.


## 2.1. Problem Statement

There are different shapes or profiles for a tunnel cross section. The choice of the profile aims at accommodating the performance requirements of the tunnel. Moreover, it tries to minimize bending moments in the lining (or displacements) as well as costs for excavation and lining [13]. Therefore, the objective function can be defined as
(1)minimizeA+φd,
where A is the area of the profile, and d is the maximum value of displacements. Also,  φ is a constant parameter.A typical problem of tunnel design is to fit two rectangles (one is required as a traffic space, and the other is required as air conductor space) into a mouth profile as shown in Figure1. The figure shows two types of cross sections: in Figure 1(a), for a determined height (Hd), a vertical wall is considered, while in Figure 1(b), the vertical wall is not utilized. For both types, the design functions of crown should be determined.  Based on the kind of the selected function for crown, different shapes of profiles will be achieved. Here, we utilized the polynomial functions. As a result, the aim of optimization problem is to determine the parameters of the crown polynomial functions. The value of Hd for profile type I should be also considered as a variable. The geometry constraints of a such problem can be summarized as follows.The different profiles of tunnel cross sections.
(a)
(b)For the profile with vertical wall (type I):(2)Hdmin≤Hd≤Hdmax,Hreq≤H1,Breq≤B1,As+Breq×Hreq≤A.For the profile without vertical wall (type II):(3)Breq≤B1,As+Breq×Hreq≤A,
where Hreq and Breq are the required height and width of traffic space, respectively. min and max denote lower and upper bounds, respectively. As is the required space for the air conductor.


## 2.2. Constraint Handling Approach

There are different methods to handle the constraints [16–18]. One of well known approaches to handle constraints is to employ a penalty function. In utilizing penalty functions, if the constraints are between the allowable limits, the penalty is zero; otherwise, the amount of penalty is obtained by dividing the violation of allowable limit to the limit itself, as
(4)Hreq≤H1⇒ΦH=0,Hreq>H1⇒ΦH=H1-HreqHreq,Breq≤B1⇒ΦB=0,Breq>B1⇒ΦB=B1-BreqBreq,As+Breq×Hreq≤A⇒ΦA=0,As+Breq×Hreq>A1⇒ΦA=A-(As+Breq×Hreq)As+Breq×Hreq,
and the total value of the penalty functions equals
(5)Φ=ΦH+ΦB+ΦA.


## 3. Ant Colony Optimization

### 3.1. General Aspects

Ant colony optimization (ACO) is a cooperative search technique that mimics the foraging behavior of real life ant colonies [19]. The ant algorithms mimic the techniques employed by real ants to rapidly establish the shortest route from food source to their nest and vice versa. Ethologists observed that ants can construct the shortest path from their colony to the feeding source and back through the use of pheromone trails [19]. When an isolated ant comes across some food source in its random sojourn, it deposits a quantity of pheromone on that location. Other randomly moving ants in the neighborhood can detect this marked pheromone trail. Further, they follow this trail with a very high degree of probability and simultaneously enhance the trail by depositing their own pheromone. More and more ants follow the pheromone-rich trail, and the probability of the trail being followed by other ants is further enhanced by the increased trail deposition. This is an autocatalytic (positive feedback) process which favors the path along which more ants previously traversed [19]. The ant algorithms were based on the indirect communication capabilities of the ants. Artificial ants in ACO algorithms are deputed to generate rules by using heuristic information or visibility and by using the principle of indirect pheromone communication capabilities for iterative improvement of rules [2].


### 3.2. Pseudocode

The general procedure of the ACO algorithm manages the scheduling of four activities [2].Step 1 (initialization).
The initialization of the ACO consists of the initialization of the pheromone trail, the number of ants randomly and the required constant parameters.Step 2 (solution construction).
In the iteration step, each ant constructs a complete solution to the problem according to a state transition rule. The state transition rule depends mainly on the state of the pheromone and visibility of ant. Visibility is an additional ability used to make this method more efficient. In engineering problems, the visibility for allowable value numberj, in variable i, equals the reverse of its real value, as
(6)ηij=1xij.
For the kth ant, the selection of allowable value j of variable i is according to the transition probability function as
(7)Pijk(t)=[τij(t)]α·[ηij]β∑l∈Ni[τil(t)]α·[ηil]β,∀j∈Ni,
where τij(t) is the intensity of pheromone on variable i and allowable value j, Ni is the list of allowable values that are available to variable i, and the α and β are control parameters. The intensity of pheromone reflecting the previous experiences of the ants is a shared memory which provides an indirect communication between ants. Pheromone information stored in the trail matrix provides a global view about the selection of the edge based on a quality measure of the solution constructed afterward. On the other hand, the value of visibility is determined by a greedy heuristic for the original problem which considers only the local information on allowable values.Step 3 (pheromone updating rule).
When every ant has constructed a solution, the intensity of pheromone trails on selected values is updated by the pheromone updating rule (global pheromone updating rule). The global pheromone updating rule is applied in two phases: first, an evaporation phase where a fraction of the pheromone evaporates, second, a reinforcement phase where the elitist ant, which has constructed the best solution in that iteration, deposits an amount of pheromone(8)τij(t+ng)=(1-ρ)·τij(t)+ρ·Δτij+,
where ρ(0<ρ<1) represents the persistence of pheromone trails ((1-ρ) is the evaporation rate), ng is the number of variables, and Δτij+, the amount of pheromone increase for the elitist ant, equals
(9)Δτij+=1L+,
where L+ is the length of the solution found by the elitist ant.
At the end of each movement, local trail updating rule reduces the level of trail on values selected by the ant colony during the preceding iteration. When an ant selects the valuej for variable i, the local update rule adjusts the intensity of trail by
(10)τij(t+1)=ξ·τij(t),
where ξ is the adjustable parameter between 0 and 1 representing the persistence of the trail.Step 4 (stopping control level).
This process is repeated until a stopping criterion is fulfilled.


### 3.3. Improved Ant Colony Optimization

Kaveh and Talatahari [2] suggested an improved ACO, using sub-optimization mechanism which divides the search space into smaller parts and deletes the infeasible parts, and then the remaining space is divided into smaller parts again for more investigation in the next stage. So, the algorithm can be summarized as follows.Step 1.
Calculating cross-sectional area boundaries for each variable.Step 2.
Creating the series of the allowable cross-sectional areas.Step 3.
Determining the optimum solution of the stage by using ACO algorithm.Step 4.
Repeating Steps1–3 for definite times.


## 3.1. General Aspects

Ant colony optimization (ACO) is a cooperative search technique that mimics the foraging behavior of real life ant colonies [19]. The ant algorithms mimic the techniques employed by real ants to rapidly establish the shortest route from food source to their nest and vice versa. Ethologists observed that ants can construct the shortest path from their colony to the feeding source and back through the use of pheromone trails [19]. When an isolated ant comes across some food source in its random sojourn, it deposits a quantity of pheromone on that location. Other randomly moving ants in the neighborhood can detect this marked pheromone trail. Further, they follow this trail with a very high degree of probability and simultaneously enhance the trail by depositing their own pheromone. More and more ants follow the pheromone-rich trail, and the probability of the trail being followed by other ants is further enhanced by the increased trail deposition. This is an autocatalytic (positive feedback) process which favors the path along which more ants previously traversed [19]. The ant algorithms were based on the indirect communication capabilities of the ants. Artificial ants in ACO algorithms are deputed to generate rules by using heuristic information or visibility and by using the principle of indirect pheromone communication capabilities for iterative improvement of rules [2].


## 3.2. Pseudocode

The general procedure of the ACO algorithm manages the scheduling of four activities [2].Step 1 (initialization).
The initialization of the ACO consists of the initialization of the pheromone trail, the number of ants randomly and the required constant parameters.Step 2 (solution construction).
In the iteration step, each ant constructs a complete solution to the problem according to a state transition rule. The state transition rule depends mainly on the state of the pheromone and visibility of ant. Visibility is an additional ability used to make this method more efficient. In engineering problems, the visibility for allowable value numberj, in variable i, equals the reverse of its real value, as
(6)ηij=1xij.
For the kth ant, the selection of allowable value j of variable i is according to the transition probability function as
(7)Pijk(t)=[τij(t)]α·[ηij]β∑l∈Ni[τil(t)]α·[ηil]β,∀j∈Ni,
where τij(t) is the intensity of pheromone on variable i and allowable value j, Ni is the list of allowable values that are available to variable i, and the α and β are control parameters. The intensity of pheromone reflecting the previous experiences of the ants is a shared memory which provides an indirect communication between ants. Pheromone information stored in the trail matrix provides a global view about the selection of the edge based on a quality measure of the solution constructed afterward. On the other hand, the value of visibility is determined by a greedy heuristic for the original problem which considers only the local information on allowable values.Step 3 (pheromone updating rule).
When every ant has constructed a solution, the intensity of pheromone trails on selected values is updated by the pheromone updating rule (global pheromone updating rule). The global pheromone updating rule is applied in two phases: first, an evaporation phase where a fraction of the pheromone evaporates, second, a reinforcement phase where the elitist ant, which has constructed the best solution in that iteration, deposits an amount of pheromone(8)τij(t+ng)=(1-ρ)·τij(t)+ρ·Δτij+,
where ρ(0<ρ<1) represents the persistence of pheromone trails ((1-ρ) is the evaporation rate), ng is the number of variables, and Δτij+, the amount of pheromone increase for the elitist ant, equals
(9)Δτij+=1L+,
where L+ is the length of the solution found by the elitist ant.
At the end of each movement, local trail updating rule reduces the level of trail on values selected by the ant colony during the preceding iteration. When an ant selects the valuej for variable i, the local update rule adjusts the intensity of trail by
(10)τij(t+1)=ξ·τij(t),
where ξ is the adjustable parameter between 0 and 1 representing the persistence of the trail.Step 4 (stopping control level).
This process is repeated until a stopping criterion is fulfilled.


## 3.3. Improved Ant Colony Optimization

Kaveh and Talatahari [2] suggested an improved ACO, using sub-optimization mechanism which divides the search space into smaller parts and deletes the infeasible parts, and then the remaining space is divided into smaller parts again for more investigation in the next stage. So, the algorithm can be summarized as follows.Step 1.
Calculating cross-sectional area boundaries for each variable.Step 2.
Creating the series of the allowable cross-sectional areas.Step 3.
Determining the optimum solution of the stage by using ACO algorithm.Step 4.
Repeating Steps1–3 for definite times.


## 4. Numerical Examples

A numerical investigation is performed in this section. The required height and width are 4 and 6.5 meters, respectively.As is set to 1.8 × 1.8 meters. The proposed algorithm is coded in MATLAB and structures are analyzed using a finite element method. In fact, by using the constant properties for the utilized materials, a detailed model of tunnel sections is provided.The values of constantsα and β are set to 1.0 and 0.4, respectively. The local update coefficient, ξ, is taken as 0.25, and the global update coefficient, ρ, is set to 0.2, [2]. Our research results show that the number of 20 ants is sufficient to reach the desirable solution.Figure2 shows the obtained optimum profiles of tunnel cross sections (type I) when the order of polynomial functions is changed from 7 to 20. For type II, Figure 3. Presents the obtained results of tunnel cross sections. Due to the symmetry of the section, only one half of the tunnel is shown in these figures.The optimum profiles of tunnel cross sections (type I); the order of functions is as follows: (a) 7, (b) 8, (c) 9, (d) 10, and (e) 20.
(a)
(b)
(c)
(d)
(e)The optimum profiles of tunnel cross sections (type II); the order of functions is as follows: (a) 7, (b) 8, (c) 9, (d) 10, and (e) 20.
(a)
(b)
(c)
(d)
(e)A comparison of final optimum results is performed as shown in Figure4. The profile of type II (without vertical wall) is known as the best results when the degree of the function is set to 20. Another important result is that the differences between the functions with order 10 and 20 are small, and therefore, due to the existence of more variables for the function with degree 20, one may be satisfied to use a function with order of 10.  Also, Figure 5 compares the final results obtained by the ACO and GA. The differences between the final results obtained by the ACO and GA are small; however, almost in all cases, the ACO can find better results.Figure 4
Comparison of final optimum results of types I and II.Comparison of final optimum results obtained by ACO and GA; (a) type I and (b) type II.
(a)
(b)


## 5. Concluding Remarks

The choice of the profile aims at accommodating the performance requirements of the tunnel. Optimum cross section tries to minimize displacements as well as costs for excavation and lining. For the first time, this paper utilizes ant colony optimization (ACO) to determine optimum cross section of tunnels. ACO, a metaheuristic method, is inspired from natural phenomena which do not require an explicit relationship between the objective function and constraints, and it is not necessary for a given function to be derivable. The proposed method is tested on a numerical example. A section without vertical wall is found as the best design when the degree of the function is set to 20. The investigation shows that using a function with order 10 can reduce the computational costs while the final results do not change considerable. The result comparisons with genetic algorithm prove the robustness of the proposed method.



---

*Source: 320360-2013-02-17.xml*