Distribution Network Reconfiguration For Loss Reduction By Ant Colony Search Algorithm

Electric Power Systems Research 75 (2005) 190–199

Distribution network reconfiguration for loss reduction by ant colony search algorithm Ching-Tzong Su a , Chung-Fu Chang b,∗ , Ji-Pyng Chiou c a

Department of Electrical Engineering, WuFeng Institute of Technology, Chiayi 621, Taiwan Institute of Electrical Engineering, National Chung Cheng University, Chiayi 621, Taiwan c Institute of Electrical Engineering, Mingchi University of Technology, Taipei 243, Taiwan

b

Received 22 October 2004; received in revised form 18 March 2005; accepted 18 March 2005 Available online 10 May 2005

Abstract This paper introduces an ant colony search algorithm (ACSA) to solve the optimal network reconfiguration problem for power loss reduction. The ACSA is a relatively new and powerful intelligence evolution method for solving optimization problems. It is a population-based approach that uses exploration of positive feedback as well as greedy search. The ACSA was inspired from natural behavior of the ant colonies on how they find the food source and bring them back to their nest by building the unique trail formation. By applying the ACSA, the near-optimal solution to the network reconfiguration problem can be effectively achieved. The ACSA applies the state transition rule, local pheromoneupdating rule, and global pheromone-updating rule to facilitate the computation. The network reconfiguration problem of one three-feeder distribution system from the literature and one practical distribution network of Taiwan Power Company (TPC) are, respectively, solved using the proposed ACSA method, the genetic algorithm (GA), and the simulated annealing (SA). Numerical results show that the proposed method is better than the other two methods. © 2005 Elsevier B.V. All rights reserved. Keywords: Ant colony search algorithm (ACSA); Simulated annealing (SA); Genetic algorithm (GA); Network reconfiguration; Power loss reduction

1. Introduction Distribution systems consist of groups of interconnected radial circuits. The configuration may be varied via switching operations to transfer loads among the feeders. Two types of switches are used in primary distribution systems. There are normally closed switches (sectionalizing switches) and normally open switches (tie switches). Those two types of switches are designed for both protection and configuration management. Network reconfiguration is the process of changing the topology of distribution systems by altering the open/closed status of switches. Because there are many candidate-switching combinations in the distribution system, ∗

Corresponding author. E-mail addresses: [email protected] (C.-T. Su), [email protected] (C.-F. Chang), [email protected] (J.-P. Chiou). 0378-7796/$ – see front matter © 2005 Elsevier B.V. All rights reserved. doi:10.1016/j.epsr.2005.03.002

network reconfiguration is a complicated combinatorial, nondifferentiable constrained optimization problem. Civanlar et al. [1] conducted the early research on feeder reconfiguration for loss reduction. In [2], Baran and Wu modelled the problem of loss reduction and load balancing as an integer programming problem. In [3,4], the authors used a genetic algorithm to look for the minimum loss configuration. In [5–7], the authors presented the use of the power flow method based on a heuristic algorithm to determine the minimum loss configuration to radial distribution networks. In [8–10], the authors proposed a solution procedure which employed simulated annealing to search for an acceptable non-inferior solution. The authors in [11] outlined and validated a methodology for optimizing the operation of megavolt (MV) distribution networks. In [12], the authors have considered time varying load on the analysis to loss reduction. In [13], the authors employed bidirectional feeder models to simplify calculation for distribution systems. In [14],

C.-T. Su et al. / Electric Power Systems Research 75 (2005) 190–199

the authors proposed an EGA-based fuzzy multi-objective approach to solve the network reconfiguration problem. In [15,16], the fuzzy theory and evolutionary programming were employed to solve the problem of feeder reconfiguration. In [17], the authors proposed an economic operation model to solve distribution network configuration. Although the studied problem had been solved by the above methods, either its optimality is not guaranteed or much of computation time is required. Thanks to the advancement of computational ability, there has been growing attention in algorithms inspired by the observation of natural phenomena to help solving complex combinatorial problems in the last decades. Colorni and coworkers [18,19] proposed the concept of ant system (AS) and applied it to the traveling salesman problems (TSP) [20,21]. Ant algorithm has been inspired by the behavior of real ant colonies, in particular, by their foraging behavior. As it is well known, real ants are capable of finding the shortest path from food sources to the nest without using visual cues. Recently, the ant algorithm has been applied to various optimization problems, such as the short-term generation scheduling problem [22], unit commitment [23], hydroelectric generation scheduling [24], and so on. In this paper, a method employing the ant colony search algorithm (ACSA) is proposed to solve the network reconfiguration problems. The merits of the ACSA are parallel search and optimization capabilities. This method was inspired by the observation of the behaviors of ant colonies. The ACSA used in this paper uses artificial ants, which to some extent have memory and are not completely blind, thus can be applied to the network reconfiguration problem in which switch is discrete. The state transition rule, global, and local updating rules are introduced to ensure the optimal solution. In order to demonstrate the effectiveness, the proposed approach is applied to two example systems. One is a three-feeder distribution system from the literature and another is a practical distribution network of Taiwan Power Company (TPC), both are solved, respectively, by the proposed methods, SA and GA. From the computational results, it is observed that the convergence property of the ACSA method is better than that of the other two methods. This paper is organized as follows. The problem description is formulated in Section 2. The paradigm of the proposed method is introduced in Section 3. The computation procedure is described in Section 4. Numerical results are given in Section 5. Finally, the conclusion is given in Section 6.

191

where PT,Loss is the total real power loss of the system. Parameters λV and λI are the penalty constants, SCV the squared sum of the violated voltage constraints, and SCI is the squared sum of the violated current constraints. Moreover, the penalty constants are determined as follows: (1) Constant λV (λI ) is given a value of 0, if the associated voltage (current) constraint is not violated. (2) A significant value is given to λV (λI ) if the associated voltage (current) constraint is violated; this makes the objective function to move away from the undesirable solution. For secure operation, the voltage magnitude at each bus must be maintained within its limits. The current in each branch must satisfy the branch’s capacity. These constraints are expressed below: Vmin ≤ |Vi | ≤ Vmax

(2)

|Ii | ≤ Ii,max

(3)

where |Vi | is voltage magnitude of bus i, Vmin and Vmax are minimum and maximum bus voltage limits, respectively. |Ii | and Ii,max are current magnitude and maximum current limit of branch i, respectively. The proposed method uses a set of simplified feeder-line flow formulations for power flow analysis to prevent complicated computation. Referring to Fig. 1, this set of simplified formulations can be described as [2] Pi = Pi+1 + PLi+1 + Ri,i+1

Pi2 + Q2i |Vi |2

Qi = Qi+1 + QLi+1 + Xi,i+1

Pi2 + Q2i |Vi |2

2 + (R2i,i+1 + Xi,i+1 )

Pi2 + Q2i |Vi |2

(6)

where Pi and Qi are the real and reactive line powers flowing out of bus i, respectively, PLi and QLi are the real and reactive load powers at bus i. The resistance and reactance of the line section between buses i and (i + 1) are denoted by Ri,i+1 and Xi,i+1 , respectively. The power loss of the line section

This objective of the model describing the studied problem is to minimize the system power loss, subject to operating constraints under a certain load pattern. This model can be expressed as follows: (1)

(5)

|Vi+1 |2 = |Vi |2 − 2(Ri,i+1 Pi + Xi,i+1 )

2. Problem formulation

min F = min (PT,Loss + λV SCV + λI SCI )

(4)

Fig. 1. Single-line diagram of a main feeder.

192

C.-T. Su et al. / Electric Power Systems Research 75 (2005) 190–199

shorter path. This behavior forms the fundamental paradigm of the ant colony search algorithm.

connecting buses i and (i + 1) can be computed as PLoss (i, i + 1) = Ri,i+1

Pi2 + Q2i |Vi |2

(7) 3.2. State transition rule and local/global updating rule

The power loss of the feeder PF,Loss may then be determined by summing the losses of all line sections of the feeder, as below PF,Loss =

n−1


PLoss (i, i + 1)

(8)

i=0

The total system power loss PT,Loss is the sum of power losses of all feeders in the system.

3. ACSA paradigm 3.1. Ant colony behavior The ACSA imitates the behaviors of real ants. As is well known, real ants are capable of finding the shortest path from food sources to the nest without using visual cues. Also, they are capable of adapting to changes in the environment, for example, finding a new shortest path once the old one is no longer feasible due to a new obstacle. Moreover, the ants could manage to establish shortest paths through the medium that is called “pheromone”. The pheromone is the material deposited by the ants, which serves as critical communication information among ants, thereby guiding the determination of the next movement. Any trial that is rich of pheromone will thus become the goal path. The process is illustrated in Fig. 2. In Fig. 2(a), the ants are moving from food source A to the nest B on a straight line. Once an obstacle appears as shown in Fig. 2(b), the path is cut off. The ants will not be able to follow the original trial in their movements. Under this situation, they have the same probability to turn right or left. Fig. 2(c) depicts that the shorter path will collect larger amount of pheromone than the longer path. Hence, more ants will be increasingly guided to move on the shorter path. Due to this autocatalytic process, very soon all ants will choose the

As illustrated in Fig. 2, by the guidance of the pheromone intensity, the ants select preferable path. Finally, the favorite path rich of pheromone becomes the best tour, the solution to the problem. This concept develops the emergence of the ACSA method. At first, each ant is placed on a starting state. Each will build a full path, from the beginning to the end state, through the repetitive application of state transition rule. While constructing its tour, an ant also modifies the amount of pheromone on the visited path by applying the local updating rule. Once all ants have terminated their tour, the amount of pheromone on edge is modified again through the global updating rule. In other words, the pheromone-updating rules are designed so that they tend to give more pheromone to paths which should be visited by ants. In the following, the state transition rule, the local updating rule, and the global updating rule are briefly introduced. 3.2.1. State transition rule The state transition rule used by the ant system, called a random-proportional rule, is given by (9), which gives the probability with which ant k in node i chooses to move to node j.  β    [τ(i, j)][η(i, j)] , if j ∈ Jk (i) β pk (i, j) = m ∈ Jk (i) [τ(i, m)][η(i, m)]   0, otherwise (9) where τ is the pheromone which deposited on the edge between nodes i and j, η the inverse of the edge distance, Jk (i) the set of nodes that remain to be visited by ant k positioned on node i, and β is a parameter which determines the relative importance of pheromone versus distance. Equation (9) indicates that the state transition rule favors transitions toward nodes connected by shorter edges and with greater large amount of pheromone. 3.2.2. Local updating rule While constructing its tour, each ant modifies the pheromone by the local updating rule. This can be written below: τ(i, j) = (1 − ρ)τ(i, j) + ρτ0

Fig. 2. An example of the real ant’s behavior.

(10)

where τ 0 is the initial pheromone value and ρ is a heuristically defined parameter. The local updating rule is intended to shuffle the search process. Hence, the desirability of paths can be dynamically changed. The nodes visited earlier by a certain ant can be also explored later by other ants. The search space can be therefore extended. Furthermore, in so doing, ants will make a better use of pheromone information.

C.-T. Su et al. / Electric Power Systems Research 75 (2005) 190–199

193

Without local updating, all ants would search in a narrow neighborhood of the best previous tour. 3.2.3. Global updating rule When tours are completed, the global updating rule is applied to edges belonging to the best ant tour. This rule is intended to provide a greater amount of pheromone to shorter tours, which can be expressed below: τ(i, j) = (1 − σ)τ(i, j) + σδ−1

(11)

where δ is the distance of the globally best tour from the beginning of the trial and σ ∈ [0, 1] is the pheromone decay parameter. This rule is intended to make the search more directed; therefore, the capability of finding the optimal solution can be enhanced through this rule in the problem solving process.

4. Computational procedures of the proposed method The solution process begins with encoding parameters. A tie switch (TS) and some sectionalizing switches with the feeders form a loop. A particular switch of each loop is selected to open to make the loop radial such that the selected switch naturally becomes a tie switch. The network reconfiguration problem is identical to the problem of selecting an appropriate tie switch for each loop to minimize the power loss. A coding scheme that recognizes the positions of the tie switches is proposed. The total number of tie switches is kept constant, regardless of any change in the system’s topology or the tie switches’ positions. Fig. 3 shows an individual that is composed of tie switches’ positions. Different switches from a loop are, respectively, selected for cutting the loop circuit and trying to become a tie switch. After each loop is made radial, a configuration is proposed. The fitness value (defined as the system loss) associated with this proposed configurations is determined using (4)–(6). Finally, the best one among the proposed configurations is selected, and which is a feasible solution (radial configuration) with minimum loss. The fitness function to be minimized is as follows: n −1  M k

min f = min PT,Loss = min PLoss (i, i + 1) k=1

i=0

(12)

Fig. 4. Flowchart of the proposed method.

finds configurations with various states of switches so that the value of the objective function is successively reduced. The main computational processes are briefly stated below.

where M is the total number of feeders in the system and nk is the total number of sections of feeder k. Fig. 4 shows a flowchart of the main computational procedures. The proposed method mainly involves power loss computation using (4) and (5), bus voltage determination using (6), and ACSA application, which will be described below. The computation

Step 1 (Initiation). At first, the colonies of ants are randomly selected which estimated the initial fitness in the different permutations. A random number generator can be employed to generate the number of ants within the feasible search space. In addition, these ants are positioned on different nodes while the initial pheromone value of τ 0 is also given at this step.

Fig. 3. Composition of an individual.

Step 2 (Estimation of the fitness). In this step, the fitness of the ants, which is defined as the objective function, is estimated. Then, the pheromone can be added to the particular direction in which the ants have chosen. At this stage, a roulette

194

C.-T. Su et al. / Electric Power Systems Research 75 (2005) 190–199

selection algorithm can be employed based on the computed fitness [25]. Then, by spinning this designated roulette, a new permutation of pheromone associated with different paths is formed. In other words, based on a roulette selection method, a path (fitness) with higher amount of pheromone will be easy to find a new path. Hence, it would be more suitable for guiding the ants to the direction. Step 3 (Ant reconfiguration). The ant’s reconfigurations are based on the level of pheromone and distance. As (9) shows, each ant selects the next node to move taking into account the τ(i, j) and η(i, j) values. A greater τ(i, j) means that there has been a lot of traffic on this edge; hence, it is more desirable to approach the optimal solution. On the other hand, a greater η(i, j) indicates that the closer node should be chosen with a higher probability. In the network reconfiguration study, this can be seen as the difference between the original total power loss and the new total power loss. Therefore, in this step, the ant reconfiguration process helps convey ants by selecting directions based on these two parameters. Step 4 (Local/global updating rule). While constructing a solution of the network reconfiguration problem, ants visit edges and change their pheromone level by applying the local updating rule of (10). Its purpose is not only broadening the search space, but dynamically increasing the diversity of ant colony. After n iterations, all ants have completed a tour; the pheromone level is updated by applying the global updating rule of (11) for the trail which belongs to the best selected path. Therefore, according to this rule, the shortest path found by the ants is allowed to update its pheromone, also this shortest path will be saved as a record for the later comparison with the succeeding iteration. Step 5 (Termination of the algorithm). End the process if “the maximum iteration number is reached” or “all ants have selected the same tour” is satisfied; otherwise, repeat the outer

Fig. 5. A three-feeder distribution system for Example 1.

loop. In addition, the number of ants and the number of iterations were experimentally determined. All the tours visited by ants in each iteration should be evaluated. If a better path found in the process, it will be saved for later reference.

5. Application examples One three-feeder distribution system from the literature and one practical distribution network of Taiwan Power Company are investigated using the proposed ACSA method and the GA and SA methods, and the results are compared. These methods have been programmed using MATLAB and run on a Pentium IV—1.3 GHz personal computer. Example 1. The first example is a three-feeder distribution system [1] shown in Fig. 5. Input data of this example system are shown in Table 1. The system consists of 3 feeders, 13 normally closed sectionalizing switches, and 3 normally open tie switches. The system load is assumed to be constant and Sbase = 100 MVA. Parameters for the ACSA application were selected as the number of ants to be 5, β = 0.1, ρ = 0.6, σ = 0.1, and the maximum generation to be 30. For comparison, the SA and GA are also applied to solve this problem.

Table 1 Input data for Example 1 Section bus to bus

Section resistance (P.U.)

Section reactance (P.U.)

End bus real load (MW)

End bus reactive load (MVAR)

End bus fixed capacitor (MVAR)

1–4 4–5 4–6 6–7 2–8 8–9 8–10 9–11 9–12 3–13 13–14 13–15 15–16 5–11 10–14 7–16

0.075 0.08 0.09 0.04 0.11 0.08 0.11 0.11 0.08 0.11 0.09 0.08 0.04 0.04 0.04 0.12

0.1 0.11 0.18 0.04 0.11 0.11 0.11 0.11 0.11 0.11 0.12 0.11 0.04 0.04 0.04 0.12

2.0 3.0 2.0 1.5 4.0 5.0 1.0 0.6 4.5 1.0 1.0 1.0 2.1 – – –

1.6 1.5 0.8 1.2 2.7 3.0 0.9 0.1 2.0 0.9 0.7 0.9 1.0 – – –

– 1.1 1.2 – – 1.2 – 0.6 3.7 – 1.8 – 1.8 – – –

C.-T. Su et al. / Electric Power Systems Research 75 (2005) 190–199

195

Table 2 Numerical results of Example 1 Main items

Original configuration

After reconfiguration SA

GA

ACSA

15, 21, 26

19, 17, 26 (best solution)

19, 17, 26 (best solution)

19, 17, 26 (best solution)

511.4

466.1 511.4 482.3

466.1 493.2 474.8

466.1 483.3 470.2

Average loss reduction (%)

–

5.69

7.16

Number of the switches changed

–

CPU time (s)

–

Tie switches Power loss (kW) Best Worst Average

8.06 2

2.07

2.32

1.81

Table 3 The results based on different parameters setting of ACSA for Example 1 Parameters setting

Average power loss (kW)

Average loss reduction (%)

(1) β = 0.1, ρ = 0.6, σ = 0.1 (2) β = 0.5, ρ = 0.6, σ = 0.1 (3) β = 1.0, ρ = 0.6, σ = 0.1 (4) β = 0.1, ρ = 0.9, σ = 0.1 (5) β = 0.1, ρ = 0.6, σ = 0.5 (6) β = 0.1, ρ = 0.6, σ = 0.9 (7) β = 0.1, ρ = 0.1, σ = 0.1 (8) β = 0.1, ρ = 0.1, σ = 0.5

470.2 471.5 475.0 471.9 472.2 471.1 472.5 471.3

8.06 7.80 7.12 7.72 7.67 7.88 7.61 7.84

For SA application, the parameters were selected as the initial temperature to be 500, the temperature reduction ratio to be 0.95, and the maximum iteration to be 200; for GA application, parameters were selected as population size to be 5, the crossover ratio to be 0.5, the mutation ratio to be 0.03, and the maximum generation to be 50. To investigate performance of the proposed algorithm, this example was repeatedly solved for 100 runs. The best and worst computation results among the 100 runs are expressed in Table 2. The average value for the best solutions of those 100 runs and the average CPU time are also shown in this table. From the computational results of Table 2, it is observed that these three methods have the same best solution. However, for the ACSA, the average loss reduction ratio and average CPU time are less than those of the SA and GA. Moreover, the numbers of times to which the best solution is obtained are 35, 78, and 85, for the SA, GA, and ACSA, respectively, in 100 runs. From the above discussion, it could be concluded that the performance of the proposed ACSA method is better than both the SA and GA methods. Furthermore, Table 3 shows the results based on different parameters setting of ACSA. It is observed that among them, the setting (1) is the best. Example 2. The second example is a practical distribution network of Taiwan Power Company. Its conductors mainly employ both overhead lines ACSR 477KCM and underground lines copper conductors 500KCM. The system is shown in Fig. 6 and the relating data are shown in Table 4. It is a three-phase, 11.4 kV system. The system consists of 11 feeders, 83 normally closed sectionalizing switches, and 13 normally open tie switches. Three-phase balance and con-

stant load are assumed. Parameters for the ACSA application were selected as the number of ants to be 5, β = 0.15, ρ = 0.9, σ = 0.2, and the maximum generation to be 500. For comparison, the SA and GA are also applied to solve this problem. For SA application, the parameters were selected as the initial temperature to be 5000, the temperature reduction ratio to be 0.99, and the maximum iteration to be 4000; for GA

Fig. 6. A distribution system of Taiwan Power Company for Example 2.

196

C.-T. Su et al. / Electric Power Systems Research 75 (2005) 190–199

Table 4 The three-phase load and line data of Example 2 Section bus to bus

Section resistance ()

Section reactance ()

End bus real load (kW)

End bus reactive load (kVAR)

A-1 1–2 2–3 3–4 4–5 5–6 6–7 7–8 7–9 7–10

0.1944 0.2096 0.2358 0.0917 0.2096 0.0393 0.0405 0.1048 0.2358 0.1048

0.6624 0.4304 0.4842 0.1883 0.4304 0.0807 0.1380 0.2152 0.4842 0.2152

0 100 300 350 220 1100 400 300 300 300

0 50 200 250 100 800 320 200 230 260

B-11 11–12 12–13 12–14

0.0786 0.3406 0.0262 0.0786

0.1614 0.6944 0.0538 0.1614

0 1200 800 700

0 800 600 500

C-15 15–16 16–17 17–18 18–19 19–20 20–21 21–22 21–23 23–24

0.1134 0.0524 0.0524 0.1572 0.0393 0.1703 0.2358 0.1572 0.1965 0.1310

0.3864 0.1076 0.1076 0.3228 0.0807 0.3497 0.4842 0.3228 0.4035 0.2690

0 300 500 700 1200 300 400 50 50 50

0 150 350 400 1000 300 350 20 20 10

D-25 25–26 26–27 27–28 28–29

0.0567 0.1048 0.2489 0.0486 0.1310

0.1932 0.2152 0.5111 0.1656 0.2690

50 100 100 1800 200

30 60 70 1300 120

E-30 30–31 31–32 32–33 33–34 34–35 35–36 36–37 37–38 38–39 39–40 38–41 41–42

0.1965 0.1310 0.1310 0.0262 0.1703 0.0524 0.4978 0.0393 0.0393 0.0786 0.2096 0.1965 0.2096

0.3960 0.2690 0.2690 0.0538 0.3497 0.1076 1.0222 0.0807 0.0807 0.1614 0.4304 0.4035 0.4304

0 1800 200 200 800 100 100 20 20 20 20 200 50

0 1600 150 100 600 60 60 10 10 10 10 160 30

F-43 43–44 44–45 45–46

0.0486 0.0393 0.1310 0.2358

0.1656 0.0807 0.2690 0.4842

0 30 800 200

0 20 700 150

G-47 47–48 48–49 49–50 50–51 51–52 52–53 53–54 54–55

0.2430 0.0655 0.0655 0.0393 0.0786 0.0393 0.0786 0.0524 0.1310

0.8280 0.1345 0.1345 0.0807 0.1614 0.0807 0.1614 0.1076 0.2690

0 0 0 200 800 500 500 500 200

0 0 0 160 600 300 350 300 80

H-56 56–57 57–58 58–59

0.2268 0.5371 0.0524 0.0405

0.7728 1.1029 0.1076 0.1380

0 30 600 0

0 20 420 0

C.-T. Su et al. / Electric Power Systems Research 75 (2005) 190–199

197

Table 4 (Continued ) Section bus to bus

Section resistance ()

Section reactance ()

59–60 60–61 61–62 62–63 63–64

0.0393 0.0262 0.1048 0.2358 0.0243

0.0807 0.0538 0.2152 0.4842 0.0828

20 20 200 300 300

10 10 130 240 200

I-65 65–66 66–67 67–68 68–69 69–70 70–71 71–72

0.0486 0.1703 0.1215 0.2187 0.0486 0.0729 0.0567 0.0262

0.1656 0.3497 0.4140 0.7452 0.1656 0.2484 0.1932 0.0528

0 50 0 400 0 0 2000 200

0 30 0 360 0 0 1500 150

J-73 73–74 74–75 75–76

0.3240 0.0324 0.0567 0.0486

1.1040 0.1104 0.1932 0.1656

0 0 1200 300

0 0 950 180

K-77 77–78 78–79 79–80 80–81 81–82 82–83

0.2511 0.1296 0.0486 0.1310 0.1310 0.0917 0.3144

0.8556 0.4416 0.1656 0.2640 0.2640 0.1883 0.6456

0 400 2000 200 500 100 400

0 360 1300 140 360 30 360

5–55 7–60 11–43 12–72 13–76 14–18 16–26 20–83 28–32 29–39 34–46 40–42 53–64

0.1310 0.1310 0.1310 0.3406 0.4585 0.5371 0.0917 0.0786 0.0524 0.0786 0.0262 0.1965 0.0393

0.2690 0.2690 0.2690 0.6994 0.9415 1.0824 0.1883 0.1614 0.1076 0.1614 0.0538 0.4035 0.0807

– – – – – – – – – – – – –

– – – – – – – – – – – – –

application, parameters were selected as population size to be 10, the crossover ratio to be 0.5, the mutation ratio to be 0.03, and the maximum generation to be 500. Table 5 expressed the best and worst computation results among the 100 runs and the average results for the best solutions of those 100 runs.

End bus real load (kW)

End bus reactive load (kVAR)

From the numerical results, it is observed that the three methods have the same best solution. Similarly, Table 6 shows the results based on different parameters setting of ACSA. It is observed that among them the setting (1) is the best. In addition, the convergence rate of the proposed ACSA method

Table 5 Numerical results of Example 2 Main items

Original configuration

SA

GA

ACSA

Tie switches

84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96

55, 7, 86, 72, 13, 89, 90, 83, 92, 39, 34, 41, 62 (best solution)

55, 7, 86, 72, 13, 89, 90, 83, 92, 39, 34, 41, 62 (best solution)

55, 7, 86, 72, 13, 89, 90, 83, 92, 39, 34, 41, 62 (best solution)

531.99

469.88 498.22 489.82

469.88 489.25 479.73

469.88 482.95 471.41

Average loss reduction (%)

–

7.93

9.82

11.39

Number of the switches changed

–

CPU time (s)

–

Power loss (kW) Best Worst Average

9 257.43

303.66

241.51

198

C.-T. Su et al. / Electric Power Systems Research 75 (2005) 190–199

Table 6 The results based on different parameters setting of ACSA for Example 2 Parameters setting

Average power loss (kW)

Average loss reduction (%)

(1) β = 0.15, ρ = 0.9, σ = 0.2 (2) β = 0.25, ρ = 0.9, σ = 0.2 (3) β = 0.10, ρ = 0.9, σ = 0.2 (4) β = 0.20, ρ = 0.3, σ = 0.4 (5) β = 0.15, ρ = 0.8, σ = 0.4 (6) β = 0.15, ρ = 0.9, σ = 0.4 (7) β = 0.15, ρ = 0.9, σ = 0.4 (8) β = 0.15, ρ = 0.9, σ = 0.5

471.41 473.29 474.16 488.49 472.70 473.99 473.97 476.32

11.39 11.03 10.87 8.18 11.14 10.90 10.91 10.46

(ACSA) is better than the SA and GA. It can be observed that a 8.06% of average loss reduction can be achieved by the ACSA comparing with a 5.69% by the SA, and a 7.16% by the GA, as shown in Table 2. For the large-scale system like Example 2, numerical results demonstrate that the advantage of ACSA is more remarkable. In Example 2, a 11.39% of average loss reduction can be achieved by the ACSA comparing with a 7.93% by the SA and a 9.82% by the GA, as shown in Table 5. From Table 3 of Example 1 and Table 6 of Example 2, the results based on some different parameters setting for the ACSA method show that the proposed method is effective in average loss reduction for various parameters setting demonstrating a certain extent adaptive performance for the proposed method. Fig. 7 further confirms that the ACSA method can more efficiently search the optimal or near-optimal solution for network reconfiguration problems. Moreover, it can be observed from Tables 2 and 5, the proposed method is the best in the average solution as well as the average CPU time. The proposed method is helpful for operating existing systems and planning future systems.

Acknowledgment Financial research support from the National Science Council of the R.O.C. under grant NSC90-2213-E-131-007 is greatly appreciated.

Fig. 7. The convergence situation of different algorithms.

compared with that of the GA, DE, and SA methods is depicted in Fig. 7. It can be seen that the proposed method has a relatively fast convergence performance.

6. Conclusion A new powerful intelligence evolution algorithm has been presented in this paper for the network reconfiguration of distribution systems. The merits of the ACSA are parallel search and optimization capabilities. This method was inspired by observation of the behaviors of ant colonies. The ACSA repetitively applies the state transition rule to favor transitions toward nodes connected by shorter edges. Then, it applies the local updating rule to shuffle the search process to extend the search space. Finally, it applies the global updating rule to make the search more directed and enhance the capability of finding the optimal solution in the problem solving process. These three rules make the ACSA an extremely powerful method for optimization problems. The computational results obtained from solving two examples including one three-feeder distribution system and one practical distribution network are investigated. The computational results of Example 1 showed that the ant colony search algorithm

References [1] S. Civanlar, J.J. Grainger, H. Yin, S.S.H. Lee, Distribution feeder reconfiguration for loss reduction, IEEE Trans. Power Deliv. 3 (1988) 1217–1223. [2] M.E. Baran, F.F. Wu, Network reconfiguration in distribution systems for loss reduction and load balancing, IEEE Trans. Power Deliv. 4 (1989) 1401–1407. [3] K. Nara, A. Shiose, M. Kitagawoa, T. Ishihara, Implementation of genetic algorithm for distribution systems loss minimum reconfiguration, IEEE Trans. Power Syst. 7 (1992) 1044–1051. [4] W.M. Lin, F.S. Cheng, M.T. Tsay, Distribution feeder reconfiguration with refind genetic algorithm, IEE Proc. Gen. Transm. Dist. 147 (2000) 349–354. [5] S.K. Goswami, S.K. Basu, A new algorithm for the reconfiguration of distribution feeders for loss minimization, IEEE Trans. Power Deliv. 7 (1992) 1484–1491. [6] D. Shirmohammadi, H.W. Hong, Reconfiguration of electric distribution networks for resistive line loss reduction, IEEE Trans. Power Deliv. 4 (1989) 1492–1498. [7] T.P. Wagner, A.Y. Chikhani, R. Hackam, Feeder reconfiguration for loss reduction: an application of distribution automation, IEEE Trans. Power Deliv. 6 (1991) 1922–1931. [8] H.C. Cheng, C.C. Kou, Network reconfiguration in distribution systems using simulated annealing, Electric Power Syst. Res. 29 (1994) 227–238. [9] H.D. Chiang, J.J. Rene, Optimal network reconfiguration in distribution systems. Part 1. a new formulation and a solution methodology, IEEE Trans. Power Deliv. 5 (1990) 1902–1908. [10] H.D. Chiang, J.J. Rene, Optimal network reconfiguration in distribution systems. Part 2. Solution algorithms and numerical results, IEEE Trans. Power Deliv. 5 (1992) 1568–1574.

C.-T. Su et al. / Electric Power Systems Research 75 (2005) 190–199 [11] G.J. Peponis, M.P. Papadopoulos, N.D. Hatziargyriou, Distribution network reconfiguration to minimize resistive line losses, IEEE Trans. Power Deliv. 10 (1995) 1338–1342. [12] R.P. Broadwater, A.H. Khan, H.E. Shaalan, R.E. Lee, Time varying load analysis to reduce distribution losses through reconfiguration, IEEE Trans. Power Deliv. 8 (1993) 294–300. [13] T.H. Chen, S.W. Wang, Simplified bidirectional-feeder models for distribution-system calculations, Proc. Inst. Elect. Eng. Gen. Transm. Dist. 142 (1995) 459–467. [14] Y.C. Huang, Enhanced genetic algorithm-based fuzzy multi-objective approach to distribution network reconfiguration, IEE Proc. Gen. Transm. Dist. 149 (2002) 615–620. [15] Y.T. Hsiao, C.Y. Chien, Multiobjective optimal feeder reconfiguration, IEE Proc. Gen. Transm. Dist. 148 (2001) 333–336. [16] Y.H. Song, G.S. Wang, A.T. Johns, P.Y. Wang, Distribution network reconfiguration for loss reduction using fuzzy controlled evolutionary programming, Proc. Inst. Elect. Eng. Gen. Transm. Dist. 144 (1997) 345–350. [17] A.A. Miguel, S.H. Hern´an, Distribution network configuration for minimum energy supply cost, IEEE Trans. Power Syst. 19 (2004) 538–542. [18] A. Colorni, M. Dorigo, V. Maniezzo, An investigation of some properties of an ant algorithm, in: Proceedings of the Second Conference

[19]

[20]

[21] [22]

[23]

[24]

[25]

199

on Parallel Problem Solving from Nature, North-Holland, Amsterdam, 1992, pp. 509–520. M. Dorigo, V. Maniezzo, A. Colorni, Ant system: optimization by a colony of cooperating agents, IEEE Trans. Syst. Man Cybern., Part B 26 (1996) 29–41. M. Dorigo, L.M. Gambardella, Ant colony system: a cooperative learning approach to the travelling salesman problem, IEEE Trans. Evol. Comput. 1 (1997) 53–66. M. Dorigo, L.M. Gambardella, Ant colonies for the traveling salesman problem, BioSystems (1997) 73–81. I.K. Yu, C.S. Chou, Y.H. Song, Application of the ant colony search algorithm to short-term generation scheduling problem of thermal units, in: Power System Technology, 1998, Proceedings, POWERCON’98, International Conference, vol. 1, 1998, pp. 552–556. N.S. Sisworahardio, A.A. El-Keib, Unit commitment using the ant colony search algorithm, in: Power Engineering 2002 Large Engineering Systems Conference, LESCOPE 02, 2002, pp. 2–6. S.J. Huang, Enhancement of hydroelectric generation scheduling using ant colony system based optimization approaches, IEEE Trans. Energy Convers. 16 (2001) 296–301. G. Leguizamon, Z. Michalewicz, A new version of ant system for subset problem, in: IEEE Congress Evol. Comput., Washington, DC, USA, 1999, pp. 1459–1464.