 Open Access
 Total Downloads : 11
 Authors : Divya M
 Paper ID : IJERTCONV3IS01007
 Volume & Issue : ICNTE – 2015 (Volume 3 – Issue 01)
 Published (First Online): 24042018
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
A Comparison of Ant Colony Optimization Algorithms Applied to Distribution Network Reconfiguration
Divya M
Department of Electrical Engineering Fr.C.R.I.T, Vashi
Navi Mumbai, India
Abstract This paper presents a comparative study of three Ant Colony Optimization (ACO) algorithms applied to Distribution Network Reconfiguration Problem. The original ACO algorithm called the Ant System (AS) and two of its variants viz. MAXMIN Ant System (MMAS) and Ant Colony System (ACS) were used to minimize active power loss in distribution systems. The algorithms were coded in MATLAB and numerical experiments were conducted on two benchmark systems. The results indicate that even though all the three algorithms are capable of solving distribution network reconfiguration problem, ACS is found to perform better for larger systems.
Keywords Distribution network reconfiguration, Ant Colony Optimization algorithm, Ant System, MaxMin Ant System, Ant Colony System.

INTRODUCTION
Distribution Systems consist of many interconnected radial circuits. By changing the status of tie and sectionalizing switches the configuration of a given distribution system can be changed. The crux of a feeder reconfiguration problem lies in identifying the tie and sectionalizing switches that are to be opened and closed, respectively so as to achieve the maximum possible reduction in losses. Solving this problem is not easy even for a simple distribution network because of large number of switching options. Also, there are multiple constraints that shall not be violated while finding an optimal or near optimal solution to the distribution network
algorithms used in the study. Section IV provides an overview of the results obtained. The discussions and conclusions are presented in Section V.

DISTRIBUTION NETWORK RECONFIGURATION Mathematically, distribution system reconfiguration
problem is a complex optimization problem. This is because distribution network topology has to be radial and power flow constraints are nonlinear in nature.
Many algorithms have been developed to solve the reconfiguration problem. B. Morton and I. M. Y. Mareels [4] proposed an exhaustive, bruteforce search method. A. Merlin and H. Back [3] proposed a branchandbound type heuristic method to determine the network configuration with minimum losses. The method proposed by S. Civanlar et al. [1] involved a branchexchange type algorithm. M. E. Baran and
F. F. Wu [2] developed search techniques based on the idea of branch exchange for the reconfiguration. D. Shirmohammadi and H. Y. Hong [5] proposed a method which calculates optimal power flow.
In addition to above, several works based on algorithms like genetic algorithm [11], simulated annealing [12], particle swarm optimization method [13] and artificial bee colony algorithm [14] are available in literature.
Objective function for distribution network reconfiguration can be written as follows [17]:
reconfiguration problem. During the last few decades, a number of studies employing different methods are reported on distribution network reconguration [1 5], [1118].
Out of the various algorithms reported to solve the network reconfiguration, one of the latest and the most versatile algorithm is the Ant Colony Optimization (ACO) [6
Min F MinPT , Loss v .SCV
Subject to the constraint:
Vmin Vi Vmax
(1)
(2)
10],[19, 20]. It is a metaheuristic, iterative algorithm used to
where, PT,Loss
is the total real power loss of the
solve different combinatorial optimization problems. In ACO,
system,
is the penalty constant, S is the squared
solution for a problem is obtained by exchanging information V CV
through a communication scheme that is similar to the one adopted by real ants.
In the paper, three ant algorithms namely Ant System (AS), MaxMin Ant System (MMAS) and Ant Colony System (ACS) are compared in terms of their ability to solve distribution network reconfiguration problem.
Section II of the paper summarizes the mathematical formulation of the problem. Section III describes the three ant
sum of the violated voltage constraints, Vi is the voltage magnitude of bus i and Vmin ,Vmax are the minimum and maximum bus voltage limits respectively.
Other constraints such as network should be radial and all the nodes should be supplied with power also should be satisfied.

ANT COLONY OPTIMIZATION ALGORITHMS
Ant algorithms are adapted from the natural behaviour of ant groups. They identify and bring food to the nest by the help of pheromone trail. The method was first applied to the Travelling Salesman Problem by M. Dorigo and L. M. Gambardella [6]. Later, the method was applied to other optimization problems like vehicle routing problem [19] and quadratic assignment problem [20].
Several variants of Ant algorithms have been proposed over the years [610]. General aspects of the original Ant System and the two of its most successful variants: MAX
Where max and min are the upper and lower values of the pheromone respectively.
C. Ant Colony System
In this algorithm, a local update rule is introduced to update the pheromone deposits. The local pheromone update is performed by all the ants after each construction step. While constructing its tour, an ant modifies the amount of pheromone on the visited path by applying local updating rule which is given by [6]:
MIN Ant System and Ant Colony System are given below.
(i, j) (1 ) (i, j) 0
(7)
A. Ant System
Mathematical model of Ant System can be explained as follows.
At first, each ant placed on a starting state, will build a full path from the beginning to the end state through repetitive application of state transition rule which is given by [7]:
Where 0 the initial pheromone is level and is a heuristically defined parameter.
Once all ants have terminated their tour, the amount of pheromone on edge is modified again through global updating rule which is given by [6]:
(i, j) (1 ) (i, j) 1
(8)
[ (i, j)] [(i, j)], if
j Jk i
pk (i, j)
[ (i, m)] [(i, m)](3)
Where is the distance of the globally best tour from the
mJk i
beginning of the trail and
0,1is the pheromone decay
0 ,
otherwise
parameter.
Where is the pheromone which is deposited on the edge between node i and node j , is the inverse of the edge

SIMULATION RESULTS
distance, Jk iis the set of nodes that remain to be visited by
Numerical experiments on distribution
re u b
network
ant k positioned on node i and and are parameters
configuration were cond cted on two enchmark r s ( s ar
econfiguration ystems Civanlar sy tem and B an and Wu
signifying the importance of trail intensity and visibility respectively.
Once all ants have terminated their tour, the amount of pheromone on edge is modified through offline updating rule which is given by [7]:
system) using the three ACO algorithms explained above. All the three algorithms were coded in MATLAB (version 2010a) and executed on a personal computer with Intel core i3 processor (3.5 GHz) and 4GB RAM. Performance of all the three ACO algorithms for solving the reconfiguration problems in terms of best solution, success rate and CPU time
m k were compared. Each control parameters of various
(i,j) (1 ) (i, j) ij
(4)
algorithms viz. trail intensity factor (), visibility factor ( ),
k=1
pheromone trail decay coefficient ( ), heuristic parameter
k 1L
,if ant k used edge (i, j) in its tour
(5)
(q), number of ants, (n) and number of iterations (N ) were
ij k
0,
otherwise
assigned same values:

Experiment 1
Where is the evaporation rate, m is the number of ants
k
The first experiment was conducted on a three feeder system known as Civanlar system [1]. The system is shown in
and
ij is the pheromone deposited on edge (i, j) by ant
Figure 1. The system consists of three feeders which are
k whose has covered a length of Lk .

MaxMin Ant System
In this variant of ACO algorithms, only the best ant updates the pheromone trails. Also, the pheromone trails are bound between a specified maximum and minimum values. The offline pheromone update rule is given by [9]:
connected to a root node, thirteen sectionalizing switches and three tie switches. Open switches are represented by dotted lines, and closed switches by solid lines.
The system load is taken constant. The base values of power and voltage are 100MVA and 23kV. The original system has tie switches numbered as 15, 21 and 26 and the power loss is 511.4kW. Power flow calculations for the study is done using a set of noniterative equations called Distflow
= (1 )
+ best max
(6)
branch equations [2]. The control parameters used for all the
ij ij
ij
min
algorithms for reconfiguration of Civanlar system are given in Table I.
Fig. 1. Civanlar System
TABLE I. CONTROL PARAMETERS USED
Parameter
AS
MMAS
ACS
Trail intensity factor,
1
1
1
Visibility factor,
5
5
5
Pheromone trail decay coefficient,
0.5
0.5
0.5
Heuristic parameter, q
10
10
10
Number of ants, n
3
3
3
Number of iterations, N
100
100
100
Pheromone decay coefficient,
–
–
0.5
It was observed that all the three ACO algorithms could effectively find the best solution for the reconfiguration problem of Civanlar system. Figure 2 shows a typical plot of ant paths corresponding to last iteration of all the three algorithms.
Summary of the results obtained for the reconfiguration carried out for Civanlar system using Ant Search algorithm, MaxMin Ant Search algorithm and Ant Colony Search algorithm is given in Table II.
The results show that out of the three algorithms used for the reconfiguration of Civanlar system, MaxMin Ant System produced best results with respect to rate of success and CPU time used.
Fig. 2. Ant paths for reconfiguration of Civanlar system
TABLE II. SUMMARY OF RESULTS
Specifications
AS
MMAS
ACS
Tieswitches
19,17,26
19,17,26
19,17,26
Power Loss (kW)
438.82
438.82
438.82
Average power loss (kW)
561.25
522.60
543.58
CPU time (s)
0.2964
0.3021
0.3089
Average CPU time (s)
0.2954
0.283
0.3022
Success percentage
94
98
95
B. Experiment 2
The second experiment was conducted on a 33 bus system known as Baran and Wu system [2]. The system is shown in Figure 3. The system has 33 buses, 37 branches and 5 tie lines. Original system consists of tie switches numbered 33, 34, 35, 36 and 37 and the base values of the system are 100MVA and 12.66kV.
The control parameters used for all the three algorithms for reconfiguration of Baran and Wu system are given in Table III.
Fig. 3. Baran and Wu system
TABLE III. CONTROL PARAMETERS USED
achieved due to network reconfiguration of the system is 19.75%.
Experimental results showed that out of the three algorithms used for the reconfiguration of Baran and Wu system, Ant Colony System provides best results with respect to rate of success and CPU time used.


CONCLUSIONS
Reconfiguration of two benchmark distribution systems was carried out using Ant Search, MaxMin Ant System and Ant Colony System. To compare the performance, same parameter values were used for all the three algorithms. Even though all the three algorithms were found to be capable of solving both the benchmark systems, it emerged that ACS yielded optimal solution more number of times compared to others for the larger distribution system viz. Baran and Wu system whereas MMAS performed marginally better for the relatively smaller Civanlar system.
Parameter 
AS 
MMAS 
ACS 
Trail intensity factor, 
1 
1 
1 
Visibility factor, 
8 
8 
8 
Pheromone trail decay coefficient, 
0.5 
0.5 
0.5 
Heuristic parameter, q 
10 
10 
10 
Number of ants, n 
5 
5 
5 
Number of iterations, N 
100 
100 
100 
Pheromone decay coefficient, 
– 
– 
0.4 
Parameter 
AS 
MMAS 
ACS 
Trail intensity factor, 
1 
1 
1 
Visibility factor, 
8 
8 
8 
Pheromone trail decay coefficient, 
0.5 
0.5 
0.5 
Heuristic parameter, q 
10 
10 
10 
Number of ants, n 
5 
5 
5 
Number of iterations, N 
100 
100 
100 
Pheromone decay coefficient, 
– 
– 
0.4 
In MaxMin Ant System, only the global best solution of each iteration is updated. Therefore only good solutions are reinforced. This makes the search more focused. Upper and lower bounds on pheromone trails in this method avoid stagnation of the search. For small systems these rules of MMAS assures global optimal solution within lesser number of iterations.
Local updating rule of Ant Colony Search algorithm ensures search diversification of the ants in a given iteration. This makes the algorithm more suitable for large systems because for such systems an extensive search of possible solutions should be done before converging to a common solution.
TABLE IV. SUMMARY OF RESULTS
Specification 
AS 
MMAS 
ACS 
Tieswitches 
7,37,32,14,9 
7,37,32,14,9 
7,37,32,14,9 
Power Loss (kW) 
141.81 
141.81 
141.81 
Average power loss (kW) 
176.71 
172.54 
169.23 
CPU time (s) 
1.95 
1.87 
1.82 
Average CPU time (s) 
2.05 
2.01 
1.93 
Success percentage 
88 
91 
94 
Summary of the results obtained for the reconfiguration carried out for Baran and Wu system using Ant Search algorithm, MaxMin Ant Search algorithm and Ant Colony Search algorithm is given in Table IV. Total loss reduction
REFERENCES

S. Civanlar, J. J. Grainger, H. Yin and S. S. H. Lee, Distribution feeder reconfiguration for loss reduction, IEEE Trans. Power Delivery, vol. 3, no. 3, pp. 12171223, Jul. 1988.

M. E. Baran and F. F. Wu, Network reconfiguration in distribution systems for loss reduction and load balancing, IEEE Trans. Power Delivery, vol. 4, no. 2, pp. 4011407, Apr. 1989.

A. Merlin and H. Back, Search for a minimalloss operating spanning tree configuration in an urban power distribution system, Proceedings of 5th Power System Computation Conference, Cambridge, UK, 1975, pp. 118.

B. Morton and I. M. Y. Mareels, An Efficient BruteForce Solution to the Network Reconfiguration Problem, IEEE Trans. on Power Delivery, vol. 15, No. 3, pp. 9961000. Jul. 2000.

D. Shirmohammadi and H. W. Hong, Reconfiguration of electric distribution networks for resistive line losses reduction, IEEE Trans. on Power Delivery, vol. 4, no. 2, pp. 14921498, Apr. 1989.

M. Dorigo and L. M. Gambardella, Ant Colony System: A cooperative learning approach to the travelling salesman problem, IEEE Trans. on Evolutionary Computation, vol. 1, no. 1, pp. 53 66, Apr. 1997.

M. Dorigo, V. Maniezzo and A. Colorni, The ant system: optimization by a colony of cooperating agents, IEEE Trans. on Systems, Man, and CyberneticsPart B, vol. 26, no. 1, pp. 113, Feb. 1996.

M. Dorigo and G. Di Caro, Ant colony optimization: a new meta heuristic, Proceedings of the 1999 Congress on Evolutionary Computation, 1999, Washington, DC, pp. 14701477.
..

Thomas St u tzle,Holger H Hoos, MAXMIN Ant System Future Generation Computer Systems, 16 (8): 889914, 2000.
..

Marco Dorigo, Mauro Birattari, and Thomas St u tzle,Ant Colony Optimization Artificial Ants as a Computational Intelligence
Technique, IEEE Computational Intelligence Magazine, pp. 2839, Nov 2006.

K. Nara, A. Shiose, M. Kitagawoa, and T. Ishihara, Implementation of genetic algorithm for distribution systems loss minimum reconfiguration, IEEE Trans. Power Systems, vol. 7, no. 3, pp. 1044 1051, Aug. 1992.
 [39] Y. J. Jeon and J. C. Kim, An efficient algorithm for network reconfiguration in distribution system, Proceedings of the IEEE Region 10 Conference TENCON 99, Cheju Island, Dec. 1999, vol. 2, pp. 907 910.

A. Y. Abdelaziz, F. M. Mohammed, S. F. Mekhamer and M. A. L. Badr, Distribution systems reconfiguration using a modified particle swarm optimization algorithm, Electric Power Systems Research, vol. 79, Issue.11, pp. 15211530, Nov. 2009.

R. S. Rao, S. V. L. Narasimham and M. Ramalingaraju, Optimization of distribution network configuration for loss reduction using artificial bee colony algorithm, International journal of Electrical Power and Energy Systems Engineering, pp. 116122, 2008.

J. G. Vlachogiannis, N. D. Hatziargyriou and K. Y. Lee, Ant colony system based algorithm for constrained load flow problem, IEEE Trans. Power Systems, vol. 20, no. 3, pp. 12411249, Aug. 2005.

F. S. Pereira, K. Vittori and G. R. M. da Costa, Distribution system reconfiguration for loss reduction based on ant colony behaviour, IEEE/PES Transmission & Distribution Conference and Exposition: Latin America, 2006, Venezuela, pp. 15.

ChingTzong Su, ChungFu Chang and JiPyng Chiou, Distribution network reconguration for loss reduction by ant colony search algorithm, Electric Power Systems Research, vol.75, pp. 190199, 2005.

E. Carpaneto and G. Chicco, Antcolony searchbased minimum losses reconfiguration of distribution systems, Proceedings of the 12th IEEE Mediterranean Electrotechnical Conference, 2004, pp. 971974.

B. Buiinheimer, R. Hartl and Christine Strauss, A new rank based version of ant system a computational study, Central European Journal of Operations Research and Economics, vol. 7, issue 1, pp. 25 38, 1999.

V. Maniezzo, A. Colorni, The ant system applied to the quadratic assignment problem, IEEE Trans. Knowledge and Data Engineering, vol. 11, issue 5, pp. 769 778, SepOct 1999.