Combining Gauss and Genetic Algorithms for Multi-Objective Transmission Expansion Planning
F.S. REIS(1), P.M.S. CARVALHO(2), L.A.F.M. FERREIRA(2)
(1)Planning Division
Rede Eléctrica Nacional
Rua Cidade de Goa, 4, 2685-038 Sacavém
PORTUGAL
(2)DEEC, Instituto Superior Técnico
Av. Rovisco Pais, 1049-001 Lisboa
PORTUGAL
Abstract: – In the paper we address the problem of reinforcements scheduling in transmission power system. The paper reports a new approach to solve the scheduling problem by combining classic optimisation techniques such as Gaussian search with evolutionary computation techniques. The paper focuses on the developed evolutionary operators and taken hybridisation process. An illustration example is given to illustrate the approach taken and the robustness of the planning solutions yielded.
Key-Words: – Transmission Planning, Genetic Algorithms, Project Scheduling, Optimisation and mathematical programming.
1 Introduction
The main objectives of power system transmission planning are to find where and what type of reinfor-cements should be built in order to cope with expected load forecast and generation planning at minimum cost.
Many mathematical models have been proposed in the past [1-6], some dealing with a fixed horizon year and single network solution topology – these are known as single stage models. Other models deal with the dynamic nature of demand through time as well as with a sequence of network solution topologies (one per stage) – these are known as multistage models [2,3]. Additionally, in power systems one is faced with the problem of scheduling a set of system reinforcements, considered as projects (e.g., lines, substations) in order to meet security and quality standards at minimum cost.
The scheduling problem is NP-Hard [7] and has been addressed by different authors in different fields and is known in literature as the Project Scheduling Problem. To see a review of the efforts that have been made in recent years to expand the variety of project scheduling problems refer to [8].
In this paper we address the multi-stage reinforcement scheduling problem for transmission expansion planning of power systems. We present a local search procedure known as Gaussian Search (GS) and show that the procedure is sensible w.r.t. the order by which the different system reinforcements are analysed. We then propose to solve the optimal order subproblem with a specific Genetic Algorithm (GA).
The organization of the paper is as follows. In §2 the formulation of the problem is given. In §3 we give the specific GA operators together with the GS local search algorithm and the hybridisation approach taken. In §4 an illustration example is reported and in §5 we present the main conclusions.
2 Problem Formulation
2.1 - Notation
The following notation will be used throughout the paper.
T Number of periods
N Number of projects
Set of alternatives for project n
Investment alternative chosen for project n
Starting time for alternative chosen for project n
2.2 - Formulation
Consider a set of projects P={P1, … PN} each , j=1,…N, with a set of alternatives An, n=1,…N. A schedule S is a pair (,) where is an array of time periods [t1,…tN] for the projects and is corresponding array of alternatives [m1,…mN], m1ÎA1,…mNÎAN.
The following assumptions are taken into account: (i) each project is considered nonpreemptive, i.e., once started it cannot be interrupted; (ii) the duration of each project has been minimized by known procedures like CPM, PERT with a correspondent expected resource (investment) profile, (iii) in each project several different alternative solutions to implement it may exist.
The problem may be formulated as in the following:
/ (1)/ (2)
Where,
is the present value associated with the schedule of investment alternatives;
is the present value of the system operational costs associated with the schedule of investment alternatives along the planning period T. These system operational costs incorporate different performance measures like number and severity of expected overloads and system losses that may occur along the planning period T.
3 Solution Approach
The stated problem is a nonconvex problem [9]. Because of that, the solutions yielded by classical methods are not guaranteed to be optimal: typically they get trapped in local optima. Several meta-heuristics have proven to work well as global optimisation methods for nonconvex problems [4-6].
Our approach is hybrid: we address the problem by combining a classical local optimisation procedure to search on project timings and alternatives (T, A) given a project sequence [P], together with a meta-heuristic to search on the best project sequence [P].
3.1 Scheduling by Gaussian Search
Given a project sequence [P] and a network graph G we take the following procedure to find the lower possible value for the objective function, i.e., to try solving the problem formulated in Eq.(1).
Gaussian Search
Make n=1.
Step 1. Take the nth project in the sequence [P] and choose the best alternative as well the best timing for its implementation ; add the project reinforcement to the network graph G.
Step 2. Go to the next project in the sequence
(n = n + 1) and repeat Step1 until the sequence of projects [P] is finished.
Step 3. If the sequence of projects [P] is finished, make n=1 and repeat Step 1 until the timings and alternatives between iterations are equal.
In the following, an example with three projects P={P1, P2, P3} is given for illustration. P1 is defined with three alternatives m1 Î A1={A11, A12, A13}, P2 with two alternatives m2 Î A2={A21, A22} and P3 with two alternatives m3 Î A3={A31, A32}. Table 1 illustrates the best project sequence as well as the best timing for each alternative.
Table 1. Example for three projects {P1, P2, P3}, each with different proposed alternatives.
Projects / Alternatives / Periods1 / 2 / 3 / 4 / 5
P1 / A11
A12
A13
P2 / A21
A22
P3 / A31
A32
For the presented sequence [P] = [P1 P2 P3], the best alternatives found and their timings of implementation are:
(m1= A12, t1= 1)
(m2= A21, t2= 3)
(m3= A31, t3= 5)
As the nature of the problem is nonconvex, if one chooses a different sequence [P’] one would most probably end up with a different schedule. That fact is the motivation for using better solution guidance for this ordering problem and that can be provided using genetic algorithms.
3.2 Ordering with Genetic Algorithms
A specific GA was designed for the ordering problem. We take the genotype to represent the order by which the projects are to be analysed by the GS. The genotype is taken to be a string O of order values indexed to a string of projects. See Fig. 1 for illustration.
Projects / P1 / P2 / P3 / P4 / P5 / P6 / P7Order O / 1 / 7 / 2 / 5 / 3 / 6 / 4
Fig. 1. Coding of the sequence of projects [P] = [P1 P3 P5 P7 P4 P6 P2]
The recombination is taken to be a one-point crossover operation where projects relative order is changed between parents in order to generate two other offspring. The operation changes relative order as we illustrate in Fig. 2 and report in the recombination algorithm.
Fig2. Offspring v is obtained from Parent v and subject to order relation contained in sub-string ou (5, 6, 7). By swapping P7 with P6 the Offspring v respect the order relation contained in sub-string ou as indicated in bold. Similar procedure is applied for Offspring u.
Recombination
Given two Parents, say u and v, the following procedure can be used to submit a sub-string ou to the solution genotype Ov.
Step 1. Divide the order relation ou into pairs of successive order relations. E.g., ou={4>6>2} is divided into pairs (4,6), (6,2).
Step 2. Check for each pair of successive order relations ou the order relation contained in Ov.
Step 3. If in genotype Ov the pair of successive order relation is not respected swap the genes of Ov.
Step 4. Repeat Step 3 until the order relation of sub-string ou is respected in genotype Ov .
With this recombination algorithm one may proceed with a general GA search procedure [9].
3.3 Hybridisation
We combine the GA search for the best order of projects together with GS for the best schedule, given a specific order of projects, using the following hybrid search algorithm:
Hybrid Search
Step 1. Initialise population of individuals representing feasible schedules
Step 2. Obtain the best schedule for each ordering scheme using GS as indicated in §3.1
Step 3. Subject the population to genetic manipulation using the recombination given in §3.2
Step 4. Generate new population of individuals
Step 5. Return to Step 2 until convergence is reached
4 Application Results
For illustration purposes a small example is conduced over a six-bus power system network. Fig. 3 depicts the one-line diagram of such network and Table 2 shows the possible alternatives that are considered. The correspon-ding system data can be found in [10].
The objective is to find, for a four-periods planning horizon, which system reinforcements will be introduced and when they will be introduced for given expected load and generation scenario.
Fig. 3. Six bus system used for illustration
For the six-bus system of Fig. 3 one may be interested on finding the best four reinforcement decisions given the fact that for each there may exist more than one solution alternative. This is illustrated in Table 1 where we have grouped all reasonable alternatives into four sets, named projects, each with the corresponding alternatives. The projects include two types of decisions common in power systems: reinforcements of existing branches (e.g., branch 2-6) or new connections between existing buses (e.g., branch 1-5).
Table 2. Possible system reinforcements, grouped by projects, for the six bus system.
Projects / Alternatives / BranchesP1 / A11 / 2-3
A12 / 2-6
A13 / 3-6
P2 / A21 / 1-5
A22 / 5-6
P3 / A31 / 1-4
A32 / 2-4
P4 / A41 / 4-5
A42 / 3-5
To illustrate the sensitivity of the solution yielded w.r.t. the order by which the projects are analysed, in Table 3 it is shown the different schedules obtained for different sequences of projects. The best sequences found are [P]=[P1 P3 P4 P2], [P]=[P3 P1 P4 P2] and [P]=[P4 P3 P1 P2].
Table 3. Results for different order sequences
Order Sequence [P] / Best Schedule / Distance to optimal solutionP1 / P2 / P3 / P4
P1 P3 P4 P2 / (A12,1) / (A21,4) / (A31,3) / (A41,4) / 0%-Optimal
P3 P1 P4 P2 / (A12,1) / (A21,4) / (A31,3) / (A41,4) / 0%-Optimal
P4 P3 P1 P2 / (A12,1) / (A21,4) / (A31,3) / (A41,4) / 0%-Optimal
P1 P2 P3 P4 / (A12,1) / (A21,3) / (A31,4) / (A41,4) / 0.3 %
P2 P4 P3 P1 / (A12,1) / (A21,3) / (A31,4) / (A42,4) / 1.5%
P4 P3 P1 P2 / (A12,1) / (A21,4) / (A32,3) / (A42,4) / 5.9%
No additions / - / - / - / - / 163%
Fig. 4. Results from the process of building schedules for different project order sequences. The best order, measured by (1), was found to be [P]=[P1 P3 P4 P2] and the worst order sequence given by [P’]=[P4 P3 P1 P2] with a deviation from the optimal solution from 5.9%.
Taking the first sequence and by looking at Table 3 one may conclude that the best decision for project P1 is alternative A12 scheduled for period 1. Also note that the solution (A12,1) is insensitive w.r.t. the order sequence [P]. On the other hand, if one takes the project P3, not only the best alternative chosen is sensitive to the order sequence [P] but also the timing of the correspondent reinforcement is different. The evolutionary process, as described in §3, pointed out the optimal schedule for this problem. For the first three entries of Table 3 the optimal solution yielded is insensitive to the order sequence chosen as both alternative and timings do not change.
In Fig. 4 the building of two schedules for two different project order sequences [P]=[P1 P3 P4 P2] and
[P’]=[P4 P3 P1 P2] is shown. In the first four iterations a GS for the best alternative is conducted as reported by the Step 2 of the algorithm presented in §3.1. This is illustrated by adding to the present solution (e.g., (A12,1)) of P1 the best second alternative and timing (e.g., (A31,3)) for the next project P3 presented in the order sequence [P]. This process is repeated until a schedule is obtained. Once a schedule is built the GS algorithm proceeds to Step 3 of §3.1 in order to find an improved solution. This process converges when the best alternatives and timings do not change between GS iterations.
5 Conclusion
We have presented an approach to search for the optimal schedule of system reinforcements for transmission power systems. The approach combines classical local optimisation techniques such as GS with global optimisation techniques such as GA. The GS is used to find the best project schedule given an order to analyse the projects. The GA is used to find the best order for the GS optimisation. The hybrid approach as proven to yield robust solutions in multi-objective transmission expansion planning problems.
References:
[1]. Pereira, M.V.F., Pinto, L.M.V.G., Cunha, S.H, Oliveira, G. C., “A Decomposition approach to automated Generation Transmission Expansion Planning”, IEEE Trans. on Power Systems, vol. PAS-104, no. 11, pp. 3074-3083, Nov. 1985.
[2]. R. Romero, A. Monticelli, "A Hierarchical decomposition approach for Transmission Network Expansion Planning," IEEE Trans. on Power Systems, vol. 9, no. 1, pp. 373--380, Feb. 1994.
[3]. R. Romero, A. Monticelli, "A zero-one implicit enumeration method for optimizing investments in transmission expansion planning," IEEE Trans. on Power Systems, vol. 9, no. 3, pp. 1385--1391, August 1994.
[4]. G. C. Oliveira, A. P. C. Costa, S. Binato, "Large scale Transmission Network Planning using Optimization and Heuristic techniques," IEEE Trans. on Power Systems, vol. 10, no. 4, pp. 1828--1833, Nov. 1995.
[5]. Romero R., Gallego, R.A., Monticelli A., “Transmission Expansion Planning by Simulated Annealing”, IEEE Trans. on Power Systems, vol. 11, no. 1, pp. 364-369, Feb. 1996.