25 - 29 de Noviembre de 2002

Montevideo, Uruguay

Radisson Victoria Plaza Hotel

 
CL37
 
New Data Structure and Spanning Forest Operators for Evolutionary Algorithms

A.C.B Delbem
University of São Paulo, ICMC-USP
acbd@icmc.usp.br
A. De Carvalho
University of São Paulo, ICMC-USP
andre@icmc.usp.br
 
Abstract

Network design is, in general, a combinatorial optimization problem. The minimun spanning tree (MST) is possibly one of the simplest problem in network design. Polynomial-time algorithms has been proposed for solving MST problems. However, other similar problems are generally NP-Hard. Due to their complexity, resent researches have been proposed the use of evolutionary algorithms (EAs) to solve them. Very encouraging result have been archieved when compared with conventional algorithms. Nervertheles, EAs approaches still require enormous computational time when considering large-scale network problems. The tree encoding (the data structure) for EAs is a critical factor in large systems. In order to overcome this drawbook, the author propose a new tree representation and its related genetic operations. The authors apply the proposed EA approach using the new encoding to solve the electical distribution restoration problems. The algorithm performance suggests that the contribution of the approach is relevant.

Keywords: Main Chain Representation, Evolutionary Algorithms, Minimum Spanning Tree, Dynamic Graphs, Distribution Systems Restoration



Texto completo        Volver

infoUYclei 2002