Multi-objective Evolutionary Algorithms for Decision-Making in Reconfiguration Problems Applied to the Electric Distribution Networks
J. E. MENDOZA, L. A. VILLALEIVA, M. A. CASTRO
Escuela de Ingeniería Eléctrica, Pontificia Universidad Católica de Valparaíso
P.O. Box 4059, CHILE
E. A. LOPEZ
Departamento de Ingeniería Eléctrica, Universidad de Concepción
Abstract: In this work the performance of three multiobjective optimization techniques based on evolutionary programming, applied to distribution network reconfiguration problems, are evaluated. The proposed model takes into account the power losses and the reliability index as minimization objectives. Due to their proven ability to find the commitment solution sets in multi-objective problems and due to the adaptability of techniques based on the Genetic Algorithms applied to reconfiguration processes the following algorithms were chosen: Microgenetic Algorithms, Non-Dominated Sorting Genetic Algorithm 2 and Strength Pareto Evolutionary Algorithm 2. The results of this research show the effectiveness of the SPEA 2 to solve this problem.
Keywords: Evolutionary algorithms, Multiobjective, Reconfiguration.
J. E. Mendoza was born in Concepción, Chile. He received his D.E.E in 2001, MSc. in 2003 and Doctorate degree in Electrical Engineering in 2007 from the Universidad de Concepción, Chile. Currently he is an associated professor at the Pontificia Universidad Católica de Valparaiso, Chile. His main research interests are optimization, numerical modeling, reliability and quality of electrical systems.
L. A. Villaleiva was born in Los Andes, Chile. He received his D.E.E in 2009 from the Pontificia Universidad Católica de Valparaiso, Chile. Actually is tendering in AREVA T&D Company, Chile. His main research interests are optimization, distribution systems and power system.
M. A. Castro was born in Santiago, Chile. He received his D.E.E in 2009 from the Pontificia Universidad Católica de Valparaiso, Chile. Actually is power quality engineering of CHILECTRA S.A, DISCO Chile. His main research interests are optimization, distribution systems and power quality.
E. A. López was born in Lota, Chile. He is an associate professor at the Electrical Engineering Department at Universidad de Concepción, Concepción, Chile. He has an Electrical Engineering degree from Universidad Técnica del Estado, Chile, and a Ph.D. at INPG, France. His interest areas are planning, optimization, control, reliability and quality of electrical systems.
CITE THIS PAPER AS:
J. E. MENDOZA, L. A. VILLALEIVA, M. A. CASTRO, E. A. LOPEZ, Multi-objective Evolutionary Algorithms for Decision-Making in Reconfiguration Problems Applied to the Electric Distribution Networks, Studies in Informatics and Control, ISSN 1220-1766, vol. 18 (4), pp. 325-336, 2009.
The reconfiguration of a distribution network is a process that alters feeder topological structure, changing the open/close status of sectionalizers and interrupters in the system. The objective of this process is to find the radial structure of the system which minimizes some previously defined objective.
The first publication on the reconfiguration problem was presented by Merlin and Back . In this paper a heuristic topology search was proposed for power loss minimization based on a meshed network.
In order to finding better results for loss minimization, a series of research studies have been carried out based on this first publication. These are summarized in the study by Sarfi, Salama and Chikhani . Several techniques have been used to solve these mono-objective optimization problems, for example, dynamic programming , Colored Petri nets , Annealing Simulation , Ant Colonies  and genetic algorithms . Moreover, a group of publications which focus on other important objectives for distribution network planning & operation, such as the cost functions , non-supplied energy  or , were Brown minimizes fault frequency and duration indices.
Additionally, there exist approaches which take where the reconfiguration problem is recognized as a multi-objective problem, using several indices. However, this group of works transforms this multi-objective problem into one optimization mono-objective problem using weighting factors or fuzzy logic . Thus, they do not really consider the real multi-objective dilemma.
In this research area, as in other engineering applications, there exists today a tendency to optimize problems from a broader perspective using a multi-objective approaches . Hence, in recent years there has been growing development of new optimization techniques based on artificial intelligence  and more specifically on evolutionary algorithms .
The studies presented in  and  approach the network configuration problem from a planning perspective, in order to find an efficient solution set over various objectives. In , two first generation techniques, called NSGA and SPEA, are compared. They take into account network construction costs and the cost of non-supplied energy. Paper  uses NSGA 2 to minimize network construction costs and costs associated to possible faults.
Following the above, the goal of this paper is the study of the performance of three important evolutionary techniques for multi-objective optimization reconfiguration. The techniques are Microgenetic Algorithms (uGA), Non-Dominated Sorting Genetic Algorithm 2 (NSGA 2) and Strength Pareto Evolutionary Algorithm 2 (SPEA 2). They were chosen due to 1) their proven ability for finding commitment solution sets to multi-objective problems and 2) the adaptability of genetic algorithms to solving problems with complex, non-differentiable, discrete and mainly combinatorial objective functions; as those involved in reconfiguration problems.
This study compared the performance of three important evolutionary techniques of multi-objective optimization applied to the distribution network reconfiguration problem.
The results show that the three multi-objective techniques are highly efficient in finding the Pareto front since they require the evaluation of a reduced number of candidates in order to identify all the solutions belonging to the real front. Moreover, the NSGA 2 and the SPEA 2 require only half the evaluation and simulation time of those of the uGA, in order to find the same solutions.
Additionally, the SPEA 2 has advantages over the NSGA 2 in all systems; being more efficient in the search for solutions. Consequently, it is recommended using the SPEA 2 in this application, since the reconfiguration problem is focused on systems of large size.
From the implementation viewpoint, the uGA is a very simple algorithm to program due to the philosophy of its conception, whereas the NSGA 2 and the SPEA 2 have similar levels of difficulty in terms of implementation, though slightly more complex than the uGA.
The authors gratefully acknowledge the support of the National found of scientific and technologic development of Chile, (Fondo Nacional de Desarrollo Científico y Tecnológico FONDECYT, Chile), project N° 11070019 and the Pontificia Universidad Católica de Valparaíso project N° 037.117/2008.
- MERLIN, A. G. BACK. Search for Minimum-Loss Operational Spanning Tree Configuration for an Urban Power Distribution System, Proc. of the Fifth Power System Computation Conference (PSCC), Cambridge, 1975, pp. 1 – 18.
- SARFI, R., M. SALAMA A. CHIKHANI. A Survey of the State of the Art in Distribution System Reconfiguration for System Loss Reduction. Electric Power Systems Research, Vol. 31, No. 1, 1994, pp. 61 – 70.
- LÓPEZ E., H. OPAZO, L. GARCIA, M. POLOUJADOFF. Minimal Loss Reconfiguration Based on Dynamic Programming Approach: Application to real. Electric Power Components and Systems, Vol. 30, No. 7, 2002, pp. 693 – 704.
- LIN, C. Distribution network reconfiguration for load balancing with a coloured Petri net algorithm. IEE Proceedings Generation, Transmission and Distribution, Vol. 150, No. 3, 2003, pp. 317 – 324.
- JEON, Y., J. KIM, J. SHIN, K. LEE. An efficient Simulated Annealing Algorithm for Network Reconfiguration in Large Scale Distribution Systems. IEEE Transactions on Power Delivery, Vol. 17, Nº 4, 2002, pp. 1070 – 1078.
- CHING-TZONG, S., C. CHUNG-FU, C. JI-PYNG. Distribution Network Reconfiguration for Loss Reduction by Ant Colony Search Algorithm. Electric Power Systems Research, Vol. 75, No. 2 – 3, 2005, pp. 190 – 199.
- MENDOZA, J., R. LÓPEZ, D. MORALES, E. LÓPEZ, PH. DESSANTE, R. MORAGA. Minimal Loss Reconfiguration Using Genetic Algorithms with Restricted Population and Addressed Operators: Real Application. IEEE Transactions on Power Systems, Vol. 21, No. 2, 2006, pp. 59 – 67.
- ZHOU, Q., D. SHIRMOHAMMADI, W. LIU, Distribution Feeder Reconfiguration for Operation Cost Reduction. IEEE Transactions on Power Systems, Vol. 12, No. 2, 1997, pp. 730 – 735.
- MENDOZA, J., R. LOPEZ, D. MORALES, E. LOPEZ, M. MEUNIER. Un Modèle de Reconfiguration pour la Minimisation de l’Energie Non Fournie Utilisant des Algorithmes Génétiques. IV Congres Internationale de Electrotechnique du Futur EF’2005.
- BROWN, R. Distribution Reliability Assesment and Reconfiguration Optimization. Transmission and Distribution Conference and Exposition, IEEE/PES, Vol. 2, 2001, pp. 994 – 999.
- DAS, D. Reconfiguration of Distribution System Using Fuzzy Multi-objective Approach. Electrical Power and Energy Systems, Vol. 28, No. 5, 2006, pp. 331-338.
- DUŢĂ, LUMINIŢA, F. G. FILIP, J. M. HENRIOUD, C. POPESCU, Disassembly Line Scheduling with Genetic Algorithms, International. Journal. of Computers, Communications & Control, Vol. III, No. 3, 2008, pp. 270-280.
- LIOUANE, N., H. YAHIA, P. PIERRE BORNE, Multi-objective Scheduling onto Heterogeneous Processors System Using Ant System & Fuzzy Logic Controller, Studies in Informatics and Control, Volume 17, Number 1, 2008.
- FILIP, F. G., Decision support and control for large scale complex systems: Annual Reviews in Control, 32 (1), pp. 61-70
- COELLO, C. A., G. B. LAMONT, D. A. Van VELDHUIZEN. Evolutionary Algorithms for Solving Multiobjective Problems. Kluwer Academic Publishers, 2002.
- TANGOUR FATMA, P. BORNE, Presentation of Some Metaheuristics for the Optimization of Complex Systems. Studies in Informatics and Control, Volume 17, Number 2, 2008.
- MENDOZA, F., J. BERNAL-AGUSTIN, J. DOMÍNGUEZ-NAVARRO. NSGA and SPEA Applied to Multiobjective Design of Power Distribution Systems. IEEE Transactions on Power Systems, Vol. 21, 2006, No. 4, pp. 1938 – 1045.
- CARRANO, E., L. SOARES, R. TAKAHASHI, R. SALDAÑA, O. NETO. Electric Distribution Network Multiobjective Design Using a Problem-Specific Genetic Algorithm. IEEE Transactions on Power Delivery. Vol. 21, 2006, No. 2, pp. 995 – 1005.
- COELLO, C. A. A Comprehensive Survey of Evolutionary-Based Multiobjective Optimization Techniques. Knowledge and Information Systems, Vol. 1, 1999, pp. 269 – 308.
- COELLO C. A., G. TOSCANO PULIDO, Multiobjective Optimization using a Micro-Genetic Algorithm, in Lee Spector, Erik Goodman, Annie Wu, William B. Langdon, Hans-Michael Voigt, Mitsuo Gen, Sandip Sen, Marco Dorigo, Shahram Pezeshk, Max H. Garzon, and Edmund Burke, (editors), Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001), Morgan Kaufmann Publishers, San Francisco, California, July 2001, pp. 274-282.
- DEB, K., S. AGRAWAL, A. PRATAB, T. MEYARIVAN. A Fast Elitist Non-Dominated Sorting Genetic Algorithm for Multi-Objective Optimization: NSGA-II. Proceedings of the Parallel Problem Solving from Nature VI Conference, 2000, pp. 849-858.
- ZITZLER, E., M. LAUMANNS, L. THIELE. SPEA2: Improving the Strength Pareto Evolutionary Algorithm. Computer Engineering and Networks Laboratory (TIK). TIK-Report 103, 2001.
- LÓPEZ E., J. CAMPOS, C. TARDON, F. SALGADO, J. TARDÓN, R. LÓPEZ, Solution to the Reliability Problem of Radial Electric Distribution Systems Through Artificial Intelligence. International Journal of Computers, Communications & Control, Vol. 1, 2006, No. 2, pp.61-71.
- ENACHEANU, B., B. RAISON, R. CAIRE, O. DEVAUX, W. BIENIA, N. HADJSAID, Radial Network Reconfiguration Using Generic Algorithm Based on the Matroid Theory. IEEE Transactions on Power System, Vol. 23, No. 1, 2008, pp. 186 – 195.
- CIVANLAR, S., J. GRAINGER, H. YIN, S. LEE. Distribution Feeder Reconfiguration for Loss Reduction IEEE Transactions on Power Delivery, Vol. 3, No. 3, 1988, pp. 1217 – 1223.
- BARAN M., F. WU, Network Reconfiguration in Distribution System for Loss Reduction and Load Balancing, IEEE Transactions on Power Delivery, Vol. 4, No. 2, 1989, pp. 1401 – 1407.