A Comparison of Ant Colony Optimization Algorithms Applied to Distribution Network Reconfiguration

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. MAX-MIN 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, Max-Min Ant System, Ant Colony System.

1. INTRODUCTION

   Distribution Systems consist of many inter-connected 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.

2. 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 non-linear in nature.

   Many algorithms have been developed to solve the reconfiguration problem. B. Morton and I. M. Y. Mareels [4] proposed an exhaustive, brute-force search method. A. Merlin and H. Back [3] proposed a branch-and-bound type heuristic method to determine the network configuration with minimum losses. The method proposed by S. Civanlar et al. [1] involved a branch-exchange 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], [11-18].

   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 meta-heuristic, 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), Max-Min 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.

3. 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 [6-10]. 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

4. 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 co-efficient ( ), 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:

   1. 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 .

   2. Max-Min 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 non-iterative 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, Max-Min 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, Max-Min 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
      Tie-switches	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.

5. CONCLUSIONS

Reconfiguration of two benchmark distribution systems was carried out using Ant Search, Max-Min 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.

In Max-Min 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

Summary of the results obtained for the reconfiguration carried out for Baran and Wu system using Ant Search algorithm, Max-Min Ant Search algorithm and Ant Colony Search algorithm is given in Table IV. Total loss reduction

REFERENCES

1. 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. 1217-1223, Jul. 1988.

2. 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. 401-1407, Apr. 1989.

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

4. B. Morton and I. M. Y. Mareels, An Efficient Brute-Force Solution to the Network Reconfiguration Problem, IEEE Trans. on Power Delivery, vol. 15, No. 3, pp. 996-1000. Jul. 2000.

5. 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. 1492-1498, Apr. 1989.

6. 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.

7. 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. 1-13, Feb. 1996.

8. 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. 1470-1477.

   ..

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

   ..

10. Marco Dorigo, Mauro Birattari, and Thomas St u tzle,Ant Colony Optimization Artificial- Ants as a Computational Intelligence

    Technique, IEEE Computational Intelligence Magazine, pp. 28-39, Nov 2006.

11. 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.

12. [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.

13. 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.

14. 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. 116-122, 2008.

15. 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. 1241-1249, Aug. 2005.

16. 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. 1-5.

17. Ching-Tzong Su, Chung-Fu Chang and Ji-Pyng Chiou, Distribution network reconguration for loss reduction by ant colony search algorithm, Electric Power Systems Research, vol.75, pp. 190199, 2005.

18. E. Carpaneto and G. Chicco, Ant-colony search-based minimum losses reconfiguration of distribution systems, Proceedings of the 12th IEEE Mediterranean Electrotechnical Conference, 2004, pp. 971-974.

19. 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.

20. 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, Sep-Oct 1999.