Multiobjective Evolution Programming Method For Feeder Reconfiguration

594

IEEE TRANSACTIONS ON POWER SYSTEMS, VOL. 19, NO. 1, FEBRUARY 2004

Multiobjective Evolution Programming Method for Feeder Reconfiguration Ying-Tung Hsiao, Member, IEEE

Abstract—This paper proposes a multiobjective evolution programming method for distribution feeder reconfiguration in a practical system. The multiple objectives are minimizing power losses, ensuring voltage quality, service reliability assurance, and minimizing switching operations. Generally, the attributes of the above four objectives are not the same and operators’ judgment must be involved in trading off between these objectives. Accordingly, this investigation presents an interactive fuzzy algorithm for obtaining a compromise solution. Furthermore, the solution algorithm is implemented in C++ with man-machine interactive procedures and tested on a Tai-Power 102-bus system with very promising results. Index Terms—Evolution programming, feeder reconfiguration, interactive fuzzy satisfying method, multiobjective optimization.

I. INTRODUCTION

D

ISTRIBUTION feeders have two type of switches–sectionalizing switches (normally closed) and tie switches (normally open). The network reconfiguration determines the status of these switches for a new topological structure in the normal state to enhance service reliability and reduce power losses. The network reconfiguration problem is a complex nonlinear combinatorial problem, since the status of switches is nondifferentiable and the normally open tie switches must be determined to satisfy system requirements. Several different techniques have been presented to resolve the network reconfiguration problem. For instance, [1] adopted a quadratic expression for system losses. In [2]–[4], heuristic algorithms were employed to minimize the power loss, while [5] developed a global optimality condition for the problem and two solution algorithms. In [6], explicit loss reduction and line flow formulas were developed to determine efficiently the switching operations. [7] applied weighting factors to multiple objectives and presented a two-stage solution approach. Recently, AI-based approaches have been described to solve the problem and the results of such methods as the expert system [8], neural network [9], simulated annealing [10], evolutionary programming (EP)[11]–[13], and fuzzy logic [14] are all encouraging. In light of above developments, this work investigates four distinct objectives that most concern system managers who try to solve the network reconfiguration problem. The real power loss of feeders is selected as the first objective function since Manuscript received March 26, 2003. This work was supported by the National Science Council of the Republic of China under Contract NSC 90-2213-E-032-018. The author is with the Department of Electrical Engineering, Tamkang University, Tamsui, Taipei 251, Taiwan, R.O.C. (e-mail: [email protected]). Digital Object Identifier 10.1109/TPWRS.2003.821430

reducing the real power loss is the primary aim of network reconfiguration as operating conditions change. The deviation of bus voltage is the second objective because the bus voltage is one of the most essential security and service quality indexes. However, satisfying the voltage magnitude constraint does not guarantee the satisfaction of the security margin requirement since the state of system might be unstable if some feeders or supply transformers are unable to meet a load demand. Hence, the network reconfiguration must remain secure to increase the reliability of the service. The capacity margin of feeders and transformers is taken as a service reliability index to specify the security of the distribution system. This index can be adopted to measure the ability to support increasing loads and the ability to back up other feeders. Finally, this study addresses the minimization of the number of switching operations in the objective function because operators prefer to minimize the switching operations. The network reconfiguration problem is formulated as a multiobjective and nondifferentiable optimization problem in light of the above considerations. This is a step toward a practical formulation for this problem. However, most optimal algorithms cannot effectively solve this kind of problem and they usually achieve local optimal solutions rather than global optimal solutions. Hence, this study first models the multiple objectives using fuzzy sets to evaluate their imprecise nature and for ease of integration. Then, an interactive satisfying method [15], [16] based on EP is presented to solve constrained multiple objective problems. Finally, the effectiveness of the solution algorithm is demonstrated on a Tai-Power distribution system. II. PROBLEM FORMULATION This section proposes a more realistic problem formulation by fuzzy model for the network reconfiguration problem. Four different objective functions with practical constraints are also discussed. A. Fuzzy Modeling Objective functions are formulated as fuzzy sets since they are imprecise. A fuzzy set is typically represented by a member. A higher membership function implies ship function greater satisfaction with the solution. The membership function consists of lower and upper boundaries, together with a strictly monotonically decreasing and continuous function. Fig. 1 plots a possible curve of a strictly monotonically decreasing membership function. The lower and upper bounds, and , of each objective function under the given constraints are established to elicit a membership function

0885-8950/04$20.00 © 2004 IEEE

HSIAO: MULTIOBJECTIVE EVOLUTION PROGRAMMING METHOD FOR FEEDER RECONFIGURATION

Fig. 1.

Example of a membership function.

, for each objective function, . Then, a strictly monotonically decreasing and continuous function , which can be linear or nonlinear, is determined. A membership function of a minimizing problem can be defined as (1)

B. Objective Function 1) Minimization of Power Loss: The minimization of the total real power losses arising from feeders can be calculated as follows: (2) represent the resistance, real power, and where , , and reactive power of branch i, respectively, and is the voltage on is the total number of branches; denotes the switch bus i. denotes the power lost from the system state vector, and value indicates economic operation of in state . A low a network. 2) Ensuring Reliability of Service: From the operator’s perspective, service reliability in operating distribution systems refers to the ability to support unexpected increasing loads and to relieve other feeders following faults (restoration). A simple index to assess the service reliability is the capacity margin of a feeder and a transformer. a) Capacity margin of feeders: The capacity margin of feeders is calculated as follows:

(3) is the total number of branches; and and where are the actual loading current and the rated current of branch i, respectively. The function represents the relative value of the margin between the rated and the actual current among the indicates a greater current reserve in the feeders. A lower feeders, implying that the considered system is more secure. b) Capacity margin of transformers: The capacity margin of transformers is calculated as follows:

(4) is the total number of the transformers, and and are the actual and rated megavolt amperes (MVA) loadings of transformer i, respectively. The function specifies where

595

the relative value of the margin between the rated and the actual values MVA loading of the supply transformers. Lower indicate a larger alternate supply in the supply transformers, implying that the operating state has higher service reliability. Selecting a specific index for ensuring reliability of service is utility-dependent and would not alter the basic formulation presented in this paper. The above simple form of reliability is selected just for purposes of illustration. 3) Minimizing the Deviation of Bus Voltage: Bus voltage is one of the most significant security and service quality indices, which can be described as follows: (5) is the total number of buses; and are the real where represents the maximal and rated voltage on bus i, and deviation of the bus voltage in the system of interest. Lower values indicate a higher quality voltage profile and better security of the considered system. 4) Minimizing Switching Operations: Minimizing the number of switching operations can be denoted as follows: (6) represents the total number of switches; and are where the new and original states of switch i, respectively; and represents the number of switching operations under state . A value implies that less time is needed during the lower network reconfiguration process. C. Constraints Two constraints are considered in the formulation of the problem, although other constraints could also be taken into account within the proposed solution procedure: • The radial structure of the network must be maintained in each new structure. • All loads must be served. The second constraint is considered in a situation without faults (in a normal case, in which reconfiguring yields multiple benefits). Notably, feeder voltage and line flows (capacity limits of transformers, feeders, and switches) are not included in the set of constraints, but they are reflected in the objective function used in this paper. III. EVOLUTIONARY ALGORITHM This section applies EP to solve multiobjective optimization problems. EP is different from conventional optimization methods because it is a simulation approach based on a biological process. EP utilizes probability transition rules to select generations. Each individual competes with other individuals in a combined population of the old generation and the new generation mutated from the old generation. The winners from the combined population constitute the next generation. The state variable represents a chromosome of which each gene represents an opened switch to the network reconfiguration problem. For example, if the states of the opened switches in

596

IEEE TRANSACTIONS ON POWER SYSTEMS, VOL. 19, NO. 1, FEBRUARY 2004

a given network are represented by defined as follows:

,

, and , then the chromosome is . The fitness function of is

(7) and Min

Max

(8)

and denote the expected and real values of where represents the number of total objectives, respectively, and objective functions. The function includes a minimax operation to minimize the objective with a maximum distance away from its expected value among the multiple objectives , the solution reaches the optimum as function. For a given the fitness value increases. The steps of EP are detailed as follows. Step 1) Input parameters. Input the parameters of EP, such as the length of . the individual and the population size Step 2) Initialization. The initial population is determined by selecting from the set of the original tie switches and their derivatives according to the mu, with tation rules. is an individual, is the total number of tie Ns dimensions, where switches. Step 3) Scoring Calculate the fitness value of an individual by (7) and (8). Step 4) Mutation In the network reconfiguration problem concerning a distribution network, the radial structure must be retained for each new structure and power must be supplied to each loading. Consequently, is mutated and assigned to . The each mutation mechanism is designed in the following manner to satisfy the constraints: , from ; 1) randomly select a gene 2) randomly select a switch in the same feeder pair (two feeders connected by the tie switch ) and replace by . The number of offspring for each individual is given by (9) where represents the fitness value of individual and rounds the elements of to the nearest integer. More offspring are generated from the individual with a greater fitness. A combined population is formed from the old generation and the new generation is mutated from the old generation. Then, the corresponding fitness value is calculated by (7). Step 5) Competition.

in the combined population Each individual has to compete with some other individuals to have the opportunity to be transcribed to the next generation. All individuals of the combined population are ranked in descending order of their corresponding individuals are tranfitness value. Then, the first scribed to the next generation. Step 6) Stop criterion. Convergence is achieved when either the number of generations reaches the maximum number of generations or the sampled mean fitness function values do not change noticeably throughout five consecutive generations. The process will stop if one of these conditions is met, but otherwise returns to the mutation step. IV. MULTIOBJECTIVE OPTIMIZATION A multiple objective problem can be considered to have the following form: Min

(10)

subject to (11) (12) where are distinct objective functions of the decision and are constraints. If some vector , and (generally all) of the objective functions are competing, no point simultaneously minimizes all of the objective functions. Restated, when objectives compete with each other, no “optimal solution” is available for the multiobjective optimization problem. Rather than optimality, the concept of noninferiority [16] is employed to characterize a solution to the problem. Definition: The feasible region, , in the decision vector space is the set of all decision vectors that satisfy the constraints, such that (13) The feasible region, , in the objective function space is the image of of the feasible region in the decision vector space (14) A point a local noninferior point if and only if for such that some neighborhood of , there does not exist a and (15) (16) A point other point

is a global noninferior point if and only if no exists there such that (17) (18)

HSIAO: MULTIOBJECTIVE EVOLUTION PROGRAMMING METHOD FOR FEEDER RECONFIGURATION

In other words, is a local noninferior point a neighborhood exists such that for any other point , at least one component of will increase its value above its value at or , . A global noninferior solution of the multiobjective problem is one where any improvement of one objective function can be achieved only at the expense of at least one of the other objectives. Typically, an infinite number of noninferior points exist in a given multiobjective problem. A noninferior point is the same as the intuitive notion of an optimum tradeoff solution, since a design is noninferior if improving an objective requires degradation in at least one of the other objectives. Clearly, if a decision-maker were able, he or she would not want to choose an inferior design. Thus, the decision-maker attempts to generate noninferior solutions to a multiobjective problem when trying to obtain a final design. The decision-maker combines subjective judgment with the quantitative analysis, since the noninferior optimal solutions generally consist of an infinite number of points. This section introduces the interactive fuzzy satisfying algorithm based on EP to determine the optimal noninferior solution for the decision-maker. The decision-maker must specify his (or her) expected membership functions to generate a candidate solution of the multiobjective problem. The expected value is a real number in [0, 1], and represents the importance of each objective function. The following minimax problem is solved to generate the optimal solution; that is, the best compromise and satisfactory solution, which is close to the requirements for the decision-maker’s exis pected values

Min

Max

(19)

where is the solution space of , and represents the number of total objective functions. The optimization technique can now be described as follows. . Step 1) Input the data and set the interactive pointer Step 2) Determine the upper and lower bounds for every oband , and elicit a strictly jective function monotonically decreasing function to formulate the . membership functions and depend on The lower and upper bounds the constraints of the considered problem. For example, let if the bus voltage is limited to the range (0.9–1.1 p.u.). Step 3) Set the initial expected value of each objective funcfor . tion Step 4) Apply EP to solve the minimax problem (19). , and , and Step 5) Calculate the values of , proceed to the next step if they are satisfactory. Othand erwise, set the interactive pointer , . choose a new expected value Then go to step 4. Step 6) Output the most satisfactory feasible solution , , and for .

597

TABLE I PARAMETERS OF OBJECTIVE FUNCTIONS

Remark: represents the original power loss from the system before reconfiguration. Notably, the decision-maker is only involved in step 5 and the sequence of this program is processed automatically thereafter, and the decision-maker does not need to provide an accurate goal for each objective. The expected value (preferred degree) of an objective is estimated from the decision-maker’s experience (or by trial and error) according to the current values of the membership and objective functions. Thus, the decision-maker can determine the optimal compromise (or most satisfactory) solution for the minimax problem using the interactive fuzzy satisfying algorithm.

V. SIMULATION RESULTS A. Illustrative Example A time-sharing computer program is implemented in C++ with man-machine interactive procedures based on the proposed algorithm. Table I provides the critical parameters of the objective functions. A Tai-Power Company distribution system is tested by the proposed method. This system includes two transformers, ten feeders, 102 branches, 13 tie lines, 102 buses, and 217 switches, as depicted in Fig. 2, where s(i,j) represents the switch between buses i and j; t(m) represents the tie line m with its tie switch t(m). The network reconfiguration problem is to determine the states of 217 switches to 1) minimize real power losses; 2) minimize the number of switch operations; 3) minimize the deviation of the bus voltage; and 4) increase the service reliability consistent with the network constraints. The search space is so large that most optimization algorithms cannot effectively solve the problem. B. Results Three loading levels (heavy, medium, and light) are considered to illustrate the effectiveness of practical operations. Table II illustrates the proposed solution algorithm. The minimax problem is solved to derive a global noninferior solution in the first interaction for the initial expected membership values . The decision-maker terminates the interactive steps if satisfied with this solution, or selects and inputs a set of new expected memberships for the following interactive steps if not.

598

IEEE TRANSACTIONS ON POWER SYSTEMS, VOL. 19, NO. 1, FEBRUARY 2004

Fig. 2. Network structure for testing. TABLE II INTERACTIVE PROCEDURE

the decision-maker evaluates the values of the membership and objective functions from the first run. He (or she) is not satisfied with this solution and he (or she) wishes to reduce the cost of further with little expense in the energy loss . Hence, larger expected number of operating switches (increased from 0.84) is selected membership value in the second run to reduce the power loss and lower expected (reduced from 0.85) are selected membership values for the number of operating switches. This procedure continues according to this schema until the decision-maker is satisfied with the solution. The above example indicates that decision-makers must determine the optimal solution while attaining these objectives. Such a multiple objective optimization problem has features in which the objectives are typically noncommensurable and subject to mutual interference. These objectives generally conflict with each other. Identifying a solution is commonly impossible while simultaneously optimizing all objectives. The proposed tradeoff method can be used to resolve the conflicts among multiple objectives so that a decision-maker can select a compromise or the most satisfactory plan. The proposed solution algorithm can extract one optimal noninferior solution in the first run of the interactive program. If the decision-maker is unsatisfied with the results of this interactive program, then he or she can obtain other solutions from the following interactive steps of this program. Objectives should be selected for changing their expected value in the interactive procedure after the first run, according to the situation of the network or the policies of the utilities. The power loss is selected for further reduction in the above example because the cost of power loss exceeds that associated with operating switches in this test system. The decision-maker was satisfied with the values of the other objectives and so did not consider them in need of change. The selection of objectives in the above example demonstrates only the interactive procedure. Decision-makers of other systems may have different options. The results of the second interaction reveal the best compromise and most satisfactory solution for this case. The power loss was reduced by approximately 50%. (Such a decrease is theoretical and subject to the set of operation constraints faced by the decision-makers). At the same time, the power quality and service reliability were also enhanced after reconfiguration, as illustrated in Table III. The test case confirms that the proposed method can be implemented in a practical system. Additionally, the run time is short for application to an online system since a reconfiguration plan was obtained in under 36 s for one interaction, on a Pentium-CELERON 300A PC in all cases. VI. CONCLUSIONS

The interactive steps are implemented until the algorithm generates the desired solution. In the test case shown in Table II,

A multiobjective algorithm based on the interactive fuzzy satisfying method and evolutionary technique was developed herein to solve the network reconfiguration problem and enhance service reliability and reduce power loss. Four objectives were considered—to 1) minimize real power losses; 2) minimize the number of switch operation; 3) minimize the deviation of the bus voltage, and 4) increase the service reliability consistent with the network constraints. EP was applied to the solu-

HSIAO: MULTIOBJECTIVE EVOLUTION PROGRAMMING METHOD FOR FEEDER RECONFIGURATION

TABLE III RESULTS IN THE TEST CASE

tion algorithm to derive the noninferior optimal solution because EP can search many paths to solve a problem with nonlinear and nondifferentiable objective functions. Finally, the proposed method was implemented and tested on a Tai-Power distribution system. The following conclusions are based on the test results. 1) The proposed method can efficiently yield the optimal noninferior solution for the tested system with a large search space. 2) The interactive fuzzy satisfying method, based on EP, enables a decision-maker to choose the most satisfactory solution from the multiple objectives. 3) The human interaction in the solution process can handle multiple competing objective problems using a tradeoff design. REFERENCES [1] K. Aoki, T. Ichimori, and M. Kanezashi, “Normal state optimal load allocation in distribution system,” IEEE Trans. Power Delivery, vol. PWRD-2, pp. 147–155, Jan. 1987.

599

[2] S. Civanlar, J. J. Grainger, H. Yin, and S. S. H. Lee, “Distribution feeder reconfiguration for loss reduction,” IEEE Trans. Power Delivery, vol. 3, pp. 1217–1223, July 1988. [3] M. E. Baran and F. F. Wu, “Network reconfiguration in distribution systems for loss reduction and load balancing,” IEEE Trans. Power Delivery, vol. 4, pp. 1401–1407, Apr. 1989. [4] V. Borozan, D. Rajicic, and R. Ackovski, “Minimum loss reconfiguration of unbalanced distribution networks,” IEEE Trans. Power Delivery, vol. 12, pp. 435–441, Jan. 1997. [5] C. C. Liu, S. J. Lee, and K. Vu, “Loss minimization of distribution feeders: optimality and algorithms,” IEEE Trans. Power Delivery, vol. 4, pp. 1281–1289, Apr. 1989. [6] J. C. Wang, H. D. Chiang, and G. R. Darling, “An efficient algorithm for real time network reconfiguration in large scale unbalanced distribution systems,” IEEE Trans. Power Syst., vol. 11, pp. 511–517, Feb. 1996. [7] I. Roytelman, V. Melnik, S. S. H. Lee, and R. L. Lugtu, “Multi-objective feeder reconfiguration by distribution management system,” IEEE Trans. Power Syst., vol. 11, pp. 661–667, May 1996. [8] C. C. Liu, S. J. Lee, and S. S. Venkata, “An expert system operational aid for restoration and loss reduction of distribution system,” IEEE Trans. Power Syst., vol. 3, pp. 619–629, May 1988. [9] H. Kim, Y. K. Ko, and H. Jung, “Artificial neural networks based feeder reconfiguration for loss reduction in distribution systems,” IEEE Trans. Power Delivery, vol. 8, pp. 1356–1366, July 1993. [10] H. C. Chang and C. C. Kuo, “Network reconfiguration in distribution system using simulated annealing,” Elect. Power Syst. Res., vol. 29, pp. 227–238, 1994. [11] M. Kitayama and K. Matsumoto, “An optimization method for distribution system configuration based on genetic algorithm,” in Proc. Inst. Elect. Eng. Int. Conf. Advances in Power Syst. Contr. Oper. Manage., 1995, pp. 614–619. [12] Y. H. Song, G. S. Wang, A. T. Johns, and P. Y. Wang, “Distribution network reconfiguration for loss reduction using fuzzy controlled evolutionary programming,” Proc. Inst. Elect. Eng., Gen. Transm. Dist., vol. 144, no. 4, pp. 345–350, July 1997. [13] W. M. Lin, F. S. Cheng, and M. T. Tsay, “Feeder loss reduction by switching operations with a hybrid programming technique,” in Proc. IEEE Transm. Dist. Conf., vol. 2, 1999, pp. 603–608. [14] Q. Zhou, D. Shirmohammadi, and W. H. E. Liu, “Distribution feeder reconfiguration for service restoration and load balancing,” IEEE Trans. Power Syst., vol. 12, pp. 724–729, May 1997. [15] J. B. C. Chen and Z. J. Zhang, “The interactive step trade-off method for multi-objective optimization,” IEEE Trans. Syst., Man, Cybern., vol. SMC-20, pp. 688–694, May/June 1990. [16] J. G. Lin, “Multiple-objective problems: pareto-optimal solutions by method of proper equality constraints,” IEEE Trans. Automat. Contr., vol. AC-21, pp. 641–650, Oct. 1976.

Ying-Tung Hsiao (M’93) received the B.S. degree in electrical engineering from the National Taiwan Institute of Technology, Taipei, Taiwan, R.O.C., in 1986, and the M.S. and Ph.D. degrees in electrical engineering from National Taiwan University, Taipei, Taiwan, R.O.C., in 1989 and 1993, respectively. Currently, he is an Associate Professor of Electrical Engineering at Tamkang University, Tamsui, Taipei, Taiwan, R.O.C. He was also on the faculty of St. John’s & St. Mary’s Institute of Technology, Taipei, Hsien, R.O.C. His research interests include power system analysis, optimal theory, and motor control.