An Application Of Genetic Algorithms To The Network Reconfiguration In Distribution For Loss

An Application of Genetic Algorithms to the Network Reconfiguration in Distribution for Loss Minimization and Load Balancing Problem (part 2) b Dai-Seub ChoAa Chang-Si& Kim and Jua Hasegawaa

a :Dept. of Electrical Eng. Hokkaido University, North 13 West 8, Uta-ku, Sapporo 060, Japan b: Dept. of Electrical Eng. Chosun University, 375 Seosuk Dong, Kwangju City, 501-759 South Korea Abstract- Network reconfiguration in distribution system is realized by changing the s h t u s of sectionalizing switches, and is usually done for loss reducing or for load balancing in the system. This paper presents a new method which applies a genetic algorithm for determining which sectionalizing switch to operate in order to solve the distribution system loss minimization reconfiguration problem. In addition, the proposed method introduces a new limited life feature for performing natural selection of individuals. Simulations were carried out in order to veri@ the effectiveness of the proposed method. These results showed that the proposed method is effective in dealing with the problems of homogeneity and genetic drift associated with the population in the initial state.

algorithm to result. In order to successfully apply a genetic algorithm to this distribution system loss minimization reconfiguration problem 121, a new method that automatically amends the crossover and mutation rate is proposed in this paper. .This is referred to as 'dynamic parameter modification' (DPM) . However, as one GA behaviaral problem, in the case where the difference of fitness within a population is small, population homogenization is incurred, and due to genetic drift [SI evolution becomes slow. in order to improve the GA convergence characteristics for the loss minimization reconfiguration problem, a ' limited life feature [3] is introduced. More specifically, for the population homogenization and genetic drift problems, in addition to fitness dependent elimination, we introduce a mechanism that carries out elimination when the limited age is reached. Then, by combining this technique with ' elitist policy' pi], we can expect solution convergence to be significantly faster. We can carry out the search process efficiently because faster convergence to an optimal solution is achieved by the 'limited life' In addition, convergence characteristics are improved because the DPM method gradually limits the field of search from the initial state.

Keywords: Distribu tionau tomation,Distributionsystem operation, distribution system planning, power flow analysis, genetic algorithm, limited life, combination optimization. 1. INTRODUCTION

The distribution system loss minimization reconfiguration problem is in essence a 0-1 planning problem which means that for typical system scales the number of combinations requiring searches becomes extremely large. In order to deal with this problem, a new approach which applies a genetic algorithm (GA). [11 was presented. Briefly, genetic algorithms are a type of random number search method, however, they are not merely a one-point search as they incorporate a multi-point search feature. h r t h e r , every point is not separately and respectively renewed, therefore, if parallel processingis applied, we can expect a fast solution IEEE Catalogue No. 95TH8130 0-7803-2981-3/95/$4.00@1995IEEE

2. PROPOSED METHOD

2.1 Formulation of a loss minimum problem In an open loop radial distribution system, loss minimum reconfiguration problem is to decide the positions of open sectionalizing switches, which can minimize distribution losses under the electric current capacity limit and voltage drop limit

376

similar. They both require the same data (system parameters and load ) and load flow calculation to evaluate the objectives for a given network topology.

constraints. This problem can be formulated as 0-1 integer programming problem as follows. To simplify the presentation, we will represent the system on a per phase basis and the loads along a feeder section as constant P,Q loads placed at the end of the lines. Distribution system loss minimization . The network reconfiguration problems for loss reduction and load balancing involve the same type of operation, namely the load transfer between the feeders or substations by changing the positions of switches. They only differ in their objective. Other factors, such as the voltage profile of the system, capacities of the lines/transformers, reliability constraints can be considered as constraints. To state these problems as optimizationproblems, note that the radial configuration to a spanning tree" of a graph representing the network topology. Thus, we have a so-called minimal spanning tree problem which can be stated as follows. Given a graph, find a spanning tree such that the objective function is minimized while the following constraints are satisfied.

2.2 Genetic Algorithm The number of the open state of a sectionalizing switch is denoted as a gene. The candidate solutions for the optimization problem are expressed by the strings (chromosome) pertaining to each gene. GA use the following. (1) Fitness function links genetic algorithms with the problems we are asking them to solve. The fitness of individual i that does not form a closed loop is not limited to the usual satisfying of constraints, therefore, it is necessary to consider this as a penalty from the fitness function. That is to say, li;: is calculated by the following equation.

Fi

=

.

Constraints - Voltage drop limit - Line capacity limit - Transformers - Power supply constraint

{Li - Lb

+

1 a* (gZl + gZ2) + b* gZ3)

where,

Li : sum of the distribution system loss : loss base Gli: penalty pertaining to line capacity constraint

Objective Terms Having a network model, now we can express the power loss and measure the balance in the system in terms of system variables. For loss reduction, the objective is to minimize the totali2r losses in the system, which can be calculated as follows pi.

LP

n-1

=

xri i -0

pi'

Lb

violation

ai: penalty pertaining to transformer capacity constraint violation penalty pertaining to voltage drop constraint violation a,b : weight constants G3i:

+ Qi'

(2) Selection: In accordance with the rules which depend on the fitness A of each individual, the multiplication and natural selection is performed.

vi'

This will be the objective function, Lp of network reconfiguration for loss reduction. For load balancing, we will use the ratio of complex power at the sending end of a branch, Siover its KVA capacity, Si as a measure of how much that branch is loaded. The branch can be a transformer, a tie-line with a sectionalizing switch or simply a line section.

Lb

=

(3) crossover: One-point crossover occurs when parts of two parent chromosomes are swapped after a

randomly selected point, creating two children.

(4) Mutation: By mutation is one procedure carried out by one-point mutate. When bit mutation is applied to a bit string it sweeps down the list of bits, replacing each by a randomly selected bit if a probability test is passed. The selection of individuals and the exchange point are randomly decided. The child obtained replaces the parent.

E(+)' 2 p i 2 + Qi' =

.m*

SI

This will be the objective function, Lb of load balancing. As noted before, the two problems are

(5) Elitist Policy: If no increasingly fit individual has

377

been discovered between generations, the elitist

If an individual has attained the predetermined age, it

policy simply carries forward the most fit individual

is selected. By repeating this manipulation, an

from the previous generation into the next.

individual cannot live too long and can be picked out

When the individuals which proceed to next

at an early time. This results in increased evolution

generation are selected, the individuals which have

speed.

small differences in fitness are difficult to select. So, 3. NUMERICAL EXAMPLES

a group of individuals which shows the same fitness in each generation occurs. This phenomenon is called

3.1 Simulation Conditions

genetic drift, and this controls the evolution speed,

In primary distribution systems, sectionalizing

that is, the convergence speed becomes slow.

switches are used for both protection, to isolate a fault, and for configuration management, to reconfiguration

2.3 Dynamic Parameter Modification

the network. Fig. 1 shows a schematic diagram of a

A special method is necessary to control genetic

simplified primary circuit of a distribution system

operator for broad search during the early stages of

together with sectionalizing switches.

evolution and narrow search in the latter stages. We Distribution systems are normally operated as

propose the Dynamic Parameter Modification (DPM)

radial networks; however , configuration is changed

which offers the decision of crossover rate and

during operation by changing the state of some

mutation rate by fitness. That is, crossover rate

sectionalizing switches.

Pc(t+l) and mutation rate Pm(t+l) in the (t+l)th generation are determined by the average of fitness f(t) in the t-th generation as follows.

Branching Point

8 Sectionalizing Switch(c1osed)

Sectionalizing Switch(open)

aBreaker

a : crossover weight coefficient

p : mutation weight coefficient

ar>

Transformer

Fig.1. Schematic diagram of a primary circuit of a distribution system

2.4 Selection by Limited Life

,

We introduceThe introduce the concept of age in each individual and a mechanism which applies natural

The system load is assumed to be constant.

selection if an individual has aged. The offspring

Convergence condition is satisfied when the number

which is born by the manipulation of early

of identical individuals having the highest fitness

circumstances and genes (crossover, mutation,

exceeds 90%. In the case where even after 5000

selection ) is set age 0, and simultaneously the

generations convergence has not been achieved, the

parent's age is increased by 1.

process is terminated.

378

Simulations were carried out for 10 case randomly made initial states. 3.2 TEST RESULTS

The proposed solution method has been implemented in C + + . The test results for loss reduction will be presented to illustrate the performance of the proposed method. The test system is hypothetical system with a 4 feeder substation, 12 branches, 37 sectionalizing switched and 49 sections .The system data is given in Table 1. (b) With Limited Life Fig.2. Convergent Characteristics.

Table 1. Model System Specification Values(pu)

With regard to this, in the case where natural

Transformer Capacity

selection is considered at the point where the limited

Section Load Feeder Voltage Drop Constraint

0.1

Feeder Line Capacity Constraint

1.5

Section Resistance

I

life age of an individual is reached,the improvement of convergence against

0.01

homogenization and genetic drift, can be obtained. (1) Efficacy relating to limited life of an

Variation in aging layer of a population (case for

individual

Limited Life of 4 years) is shown in Fig. 3.

The combination setting was crossover rate 0.4,mutation rate 0.06 [SIand given the same initial state. The case where a limited life is not considered SELECTION BY LIMITED LIFE

is shown in Fig. 2(a) and the case where a limited life

is considered is shown in Fig. 2 0 ) . These results compare the variation in the number of individuals for the various types of individuals. In this figure, the most numerous individuals having the highest fitness become the optimum solution a t the final stage. In the

case where a limited life is not considered, due to GENERATlON NUMBER

genetic drift the suppression in the increase of individuals with high fitness can be understood.

Fig. 3. Variation in aging layer of a population ( case for Limited Life of 4 years).

Because of this, convergence is slower as 1838 generation were required.

379

(2) Comparison with DPM

the convergence generation number ranged from 45 to

Fig. 4(a) compares different cases of parameter

86, which is to say that a number of infeasible paths

variation. Within DPM, the results for the case where

existed in the solution search process is successfully

a limited life is not considered are shown. The vertical

restricted meaning that a stable convergence feature

axis Is the convergence generation number, the

is obtained.

horizontal axis is for the 10 cases resulting form

Further, it can be seen from the optimum solutions

different initial state conditions which are plotted in

and from fitness variation, crossover rate variation

order from the smallest case to the largest. Similarly,

and situation of variation of mutation rate in Figures

Fig. 4@)gives the results obtained when a limited life

5(a), @) and (e) respectively, that the crossover rate

was considered. These 2 sets of results verify that on

and mutation rate follow the generation progress and

average the proposed method with a limited life

gradually decrease which contributes to convergence

converges approximately 12% faster.

characteristic improvement. U.

In the case where a limited life was not considered,

.....'.~.""".~.......,.......,...............,.......,.......,....... .i :* .: .: i i ,pu.blm

depending on the initial state the convergence generation number ranges from 48 to 101, thus, comparing this with the fixed parameter easel71 a large margin of improvement has been realized. m

With the proposed method consideringa limited life (a) Fitness

"I

I

............................................................. , * ,

I

,

,

I

,

,

,

I

I

I

I

I

I I

I

.____. ..... _ _..... ___: ,

I

.

I

....._I

,

I

,

I

,

I

t

I I

I

I

,

.

,

I

I I

I

I

I

I

I

____.; .....:_ _ _ __.._: _ __:_ _ _ . :

cur

(b) Crossover Rate

(a) Without Limited Life.

.

. ,

,

,

L.....

L.

L.....L.

!

I I!

.

: ....:

.

. . . .................................. : : ,

!

,

I

!

I

;

. I

.

.

m-: I

I

(c) Mutation Rate

cu*

Fig. 5. Changes of fitness crossover rate and mutation rate.

(b) With Limited Life. Fig. 4. DPM Dependent Characteristics.

380

REFERENCES

4. CONCLUSIONS

[l] J. H. Holland. "Adaptation in Natural and

In this paper, the authors presented a new method which applies a genetic algorithm for determining

Artificial Systems", Univ. Michigan Press, 1975.

which sectionalizing switch to operate in order to

[2] K. Nara, et al. "Implementation of Genetic

solve the distribution system loss minimization

Algorithm for Distribution Systems Loss Minimum

reconfiguration problem.

Reeonfiguration", IEEE Trans. Power Systems,

In addition the proposed method introduces a new

Vol. 7', No. 3, pp. 1044,1992.

limited life feature for performing natural selection of

J. F.. Crow and M. Kimura. An Introduction to

individuals. Simulations were carried out in order to

Population Genetics Theory. Harper & Row, 1970.

verify the effectiveness of the proposed method. From

K. DeJong. "An Analysis of the Behavior of a

these results the following points were observed.

Class of Genetic Adaptive Systems", Ph.D. Thesis, University of Michigan, 1975.

(1) For the purpose of solving the problems of

M. N. Swamy & K. Thulasirmaman. Graphs,

homogeneity and genetic drift associated with the

Networks, and Algorithms, John Wiley & Sons,

population in the initial state it can be concluded that

1981.

the proposed method is effective. The conventional

D.S. Choi, J. S. Lee & J. Hasegawa. "An

method which does not consider the limited life

Application of Genetic Algorithms to the Network

feature and uses fixed parameters requires long

Reconfiguration in Distribution Systems for Loss

calculation time depending on initial state conditions .

Minimization and Load Balancing Problem",

In contrast, the proposed method is able to perform

B E E SICICI '95 2-8 July pp.81-86,1995.

solution searches effectively and results in improved convergence. (2) The GA based on DPM considering the limited life

feature when compared with a DPM only dependent GA, demonstrates less dependence on initial state condition and a more stable convergence can be obtained.

381

,

I