Abstract
A multiperiod generation and transmission expansion planning (G&TEP) problem is considered. This model integrates conventional generation with renewable energy sources, assuming a stochastic approach. The proposed approach is based on a centralized planned transmission expansion. Due to the worldwide recent energy guidelines, it is necessary to generate expansion plans adequate to the forecast demand over the next years. Nowadays, in most energy systems, a public entity develops both the short and long of electricity-grid expansion planning. Due to the complexity of the problem, there are different strategies to find expansion plans that satisfy the uncertainty conditions addressed. We proposed to address the G&TEP problem with a pure genetic algorithm approach. Different constraint-handling techniques were applied to deal with two complex case studies presented. Numerical results are shown to compare the strategies used in the test systems, and key factors such as a prior initialization of population and the estimated minimum number of generations are discussed.
1. Introduction
Reasons for conducting a planning process are numerous. Some reasons that can potentially lead to a planning process are the following: (i) high costs for transport and storage equipment; (ii) high rate of accidents, failures, and breakdowns; (iii) bottlenecks, damage, or rejections in your production; (iv) out-of-date technical or infrastructural equipment, and so on. Two fundamental types of planning should be distinguished. The first one is a complete replanning, and the second one is a planning that aims at modernizing your planning objective. The second one is the approach in this paper. The modernization planning is characterized by a high number of planning constraints, a lower amount of possible solutions, and a high rate of by-the-way-planning. This may lead to unsatisfactory results.
Planning for power systems is essentially a projection of how the system should grow over a specific period of time, given certain assumptions and judgment about the future loads and the size of investment in generating capacity additions and transmission facility expansion and reinforcements. Power system planning faces enormous challenges and problems as, for example, future load growth in the face of uncertainties, the constraints imposed on investment, the type and availability of fuel for the generating units, and the need for consolidating the dispersed electric utilities in the isolated regions as a prerequisite for future interconnecting these regions via local national grids and with other neighboring countries. Also, an optimal reliability level should be achieved that will guarantee a continuous power flow with a reasonable cost. All these obstacles made power system planners and concerned agencies face tremendous difficulties in planning electric power facilities and making sound and appropriate decisions in constructing new power plants or adding new generating units or reinforcing the transmission and distribution networks [1–5].
A typical power system consists of enormous number of elements. The elements may vary from a small lamp switch to a giant generator. However, in this paper, the main elements of concern become the following: (i) generating facilities; (ii) transmission facilities. As a matter of fact, in power system planning, the details of each element design are not of main interest. For instance, for a generating facility, the type (steam turbine, gas turbine, etc.), the capacity, and its location are only determined [6]. Regarding the transmission lines, the periods when they should be installed are determined.
Power system expansion has been widely investigated as a generation and transmission expansion planning (G&TEP) optimization problem. Real-world G&TEP problems are nonlinear and complex, given that it entails handling high number of constraints, high dimensionality, and uncertainty related to the demand, fuel price, market price, interest rate, among other factors. In the technical literature, generation (GEP), transmission (TEP), and G&TEP problems have been solved using different methods of mathematical programming. The application of linear programming (LP) in the planning of electrical networks started with [7]. Later, in [8], a comprehensive review of the models applied to GEP was made in the 1970s. Another widely used approach for modeling expansion of a transmission system is mixed integer programming (MIP), which was introduced in [9, 10]. In the MIP context, a decision variable for system expansion is represented by an integer or binary variable.
One of the first integral approaches for generation and transmission expansion planning was reported in [11], which solution technique is based on the Benders decomposition. In [12], a methodology for planning the expansion of energy systems is described assuming several factors with uncertainty: (i) growth in demand; (ii) fuel cost; (iii) delay in the completion of the project; (iv) financial constraints, and so on, by using stochastic programming. A recent study [13] includes the costs of reducing CO2 emissions; the demand and the wind potential are modeled as two correlated random variables; subsequently, scenarios are generated by means of Monte Carlo techniques, and GEP is formulated as a problem of stochastic optimization of two stages that is solved using Benders decomposition. More complex models have been reported as in [14] where a multistage stochastic integer programming formulation for the problem expansion of capacity in an uncertain environment is presented. A scenario tree approach was used to model the evolution of demand uncertainty, parameters, and fixed cost functions.
Aiming to reduce greenhouse gas emissions, power systems worldwide are utilizing more energy from renewable sources. To this end, setting renewable targets is one of the mechanisms largely adopted to guide this process with tight levels of renewable penetration. Many countries have established policy targets related to renewable energy. The European Union (EU), for example, established a target to meet 20% of its energy consumption by means of renewable sources by 2020. Some EU member countries have stricter targets, for example, Germany with 30% by 2020 and 60% by 2050.
Currently, due to the high penetration of renewable energy, energy storage elements are extensively used, whose main function is to support the electrical network especially during frequency and voltage transients [15]. Energy storage also helps smoothing wind uncertainty. In recent work [16], Hemmati presented a unified planning for battery energy systems in electric power systems. However, in the problem raised in this paper, dynamic conditions are not assumed, so the inclusion of such elements has been omitted.
In [17, 18], different models and solution methods in order to solve a generation and transmission expansion planning problem are presented; authors propose mathematical programming by either approach direct or decomposition for solving the problem.
In mathematical problems with a high number of constraints, the search for a feasible solution can be almost as difficult as finding the optimal solution. The stochastic G&TEP considers the generation of uncertainty scenarios related to demand, fuel prices, equipment failures, and other conditions. These considerations increase exponentially the number of constraints, so obtaining feasible solutions complicates the direct solution by commercial optimizers or heuristic strategies. In [19], we can observe the development of valid inequalities for multistage stochastic integer programs.
Metaheuristic approaches have proven to be well suited to solve large real-world problems. Genetic algorithms, artificial bee colony algorithm, harmony search method, big bang-big algorithm, cuckoo search algorithm, firefly algorithm, group search algorithm, bat-inspired algorithm, and hunting search algorithm are some examples of metaheuristic techniques. However, it is difficult to use these methods successfully for complex optimization problems with high number of constraints. Researchers have developed constraint-handling techniques to deal with specific features of these problems [20]. It is difficult to estimate good penalty factors or even generate a single feasible solution [20]. Many of these so-called pure metaheuristic techniques have been used to solve the power system expansion as a GEP [21], TEP [22], or distribution (DEP) problem. Recently, the combined G&TEP have been addressed mainly with hybrid metaheuristic approaches [23].
In this paper, we propose to address the combined G&TEP problem with a genetic algorithm dealing with this nonlinear complexity and high number of constraints with several techniques reported in literature [20]. We compare several constraint-handling techniques in order to determine if a pure metaheuristic like genetic algorithm is enough to handle the complexity of G&TEP problem avoiding more complex processes. We propose a multiperiod stochastic model applied to G&TEP considering the insertion of renewable energies, which objective is to achieve a generation and transmission expansion plan that minimizes the total cost of investment. The solution to the problem is approached from two perspectives: (i) using a heuristic method and (ii) a conventional full-scale mixed integer method. The stochastic framework allows to represent, through scenarios, a wide range of demand-operating conditions throughout the planning horizon. In this work, we employed two case studies for our experiments: a three-year period time with eight different scenarios and a ten-year period time with 1024 scenarios. This allows to include uncertainty in the costs of future investments. Due to environmental considerations, a minimum amount of clean energies (30%) of the total installed generation is assumed, which must meet the demand in each instance.
The remainder of this paper is organized as follows. A review of previous contributions to G&TEP in the literature is formally presented in Section 2. Then, in Section 3, the mathematical model is provided. Section 4 describes the design of our solution method and constraint-handling strategies used for G&TEP. Case studies for three- and ten-year period times are presented in Section 5. Description of experiments and computational results are presented in Section 6. Lastly, conclusions are provided.
2. Metaheuristic Approaches for G&TEP Problem
Real-world problems like G&TEP are high-dimensional optimization tasks that cannot always be solved with deterministic methods. Metaheuristic approaches are well suited to solve this complex optimization problem. An introduction to metaheuristics and their evolution is presented below. Next, the most representative solutions in literature using metaheuristic algorithms or framework for GEP, TEP, and G&TEP optimization problems are discussed.
2.1. Metaheuristics
Stochastic optimization methods have proven to solve large problems finding a good solution. Stochastic algorithms are relatively easy to implement on complex problems [24]. Besides probabilistic methods, there are two types of stochastic approaches, heuristic and metaheuristic. In heuristic methods, a search is performed step by step and a heuristic technique aims to select the best option for expansion in order to exploit and explore the search space. Methods of local search are adequate when looking for a satisfactory solution. Heuristic methods usually obtain good quality solutions in a reasonable time although optimal solution cannot be guaranteed. Metaheuristic procedures consist in “applying at each step a subordinate heuristic which has to be designed for each particular problem type” [25]. According to [26], the term “metaheuristic” has been used with two different meanings. The first meaning conceives metaheuristic as a framework, a set of concept and strategies that guides the development of optimization algorithms. The second meaning refers to a specific implementation or algorithm based on certain strategies. This difference can be understood analyzing the evolution of metaheuristics in the last four decades [26].
An important shift of paradigm occurred in 2000 from method-centric to framework-centric. Metaheuristic concepts and strategies imitate nature, social culture, biology, or laws of physics to guide the search in an optimization problem [27]. The implementations of metaheuristic algorithms have the ability to conduct global searches avoiding local optimal solutions [28]. There is always a trade-off between two characteristics in metaheuristic algorithms balanced in order to obtain better results: intensification and diversification [24]. Metaheuristic algorithms generally perform better than simple heuristics; they are robust and efficient [29].
From the 1970s, early metaheuristic methods were used to solve different optimization problems. References [26, 29–31] reviewed the history and development of metaheuristics. Genetic algorithms, simulated annealing, immune algorithm, and tabu search [30] are some examples of early metaheuristic techniques. Ant colony optimization, differential evolution, and swarm optimization appeared in the nineties. As these so-called pure metaheuristic techniques prove to be valuable in finding good solutions in reasonable time, new techniques were developed in the nineties and the first years from 2000. Artificial bee colony algorithm, harmony search method, big bang-big algorithm, cuckoo search algorithm, firefly algorithm, group search algorithm, bat-inspired algorithm, and hunting search algorithm are some examples among many nature-inspired techniques.
Many of the above-mentioned methods became successful for solving many optimization techniques. Hence, in recent decades, it became clear that pure metaheuristic algorithms had reached their limits, and the research community shifted towards combining several techniques [31]. Memetic algorithm, for example, uses a local search to improve solutions obtained with an evolutionary algorithm. As we stated above, in the early 2000s, the paradigm of metaheuristics changed so they are described as high-level frameworks, and hybridization began to be more commonly used. Hybrid metaheuristic approaches try to use complementary strategies even from different frameworks in order to achieve better results. A combination of metaheuristics with exact methods, for example, was done creating “metaheuristics” [32]. For more details in hybrid metaheuristics, see [31].
In summary, for real-world problem with high dimensionality, deterministic methods do not reach optimal or good solutions in reasonable computing time. Stochastic and in particular metaheuristic approaches have proven to be robust and efficient for complex problems delivering near to optimal solutions, with no guarantee to be optimal, in reasonable amount of time. When human and computational time is critical, hybrid metaheuristics are not recommended; if a pure metaheuristic works well, there is no need to use more complex processes [31].
2.2. Related Work
Power system expansion has been widely investigated as a GEP, TEP, or DEP optimization problems [33]. In recent years, research works also address the combined G&TEP problem. Real-world G&TEP problems are nonlinear and complex, given that it entails handling high number of constraints, high dimensionality, and uncertainty related to the demand, fuel price, market price, interest rate, among other factors. For two decades, GEP, TEP, and G&TEP problems have been solved with deterministic and stochastic approaches. Models can be linear or nonlinear and single- or multiobjective. In this section, we present an overview of literature that tackles these three problems focusing in those using metaheuristic strategies.
2.2.1. Metaheuristics for GEP Problem
“Regardless of being linear/nonlinear and multi-/single-objective, a multitude of methods were applied successfully to solve the GEP problem during the past few decades. These methods are very diverse, from conventional techniques to modern metaheuristic algorithms” [21].
According to [21] review, genetic algorithms [34, 35] and particle swarm optimization [36, 37] are the most frequently used metaheuristic techniques to address GEP problem. The authors also enumerated related works using evolutionary programming algorithm [38], differential evolution algorithm [39], ant colony optimization, tabu search [40], simulated annealing, modified honey bee mating optimization algorithm [41], artificial immune systems [42], modified shuffled frog leaping algorithm [43], NSGA [44, 45], and gravity search algorithm [46].
In [47], they presented one of the early hybrid approaches to solve GEP long-term problem. The authors combined a genetic algorithm with tunnel-based dynamic programming. The genetic algorithm aimed to find the global optimum while the tunnel-based dynamic programming gets a local optimum. In [48], the GEP problem is analyzed with three test systems with 6-year, 14-year, and 24-year horizons. They compare the performance of nine metaheuristic techniques applied to solve GEP problem, namely, genetic algorithms, differential evolution, evolutionary programming, evolutionary strategy, ant colony optimization, particle swarm optimization, tabu search, simulated annealing, and a hybrid approach. Optimal or near-optimal solutions were obtained in a reasonable time. This work showed that metaheuristic techniques could be adaptable and more efficient in comparison with other optimization approaches.
2.2.2. Metaheuristics for TEP Problem
TEP problem is solved with many metaheuristic optimization methods [22], such as genetic algorithms [49–51], simulated annealing [52, 53], tabu search [54, 55], ant colony optimization [56], artificial immune system [57], harmony search [58], particle swarm optimization [59, 60], and hybrid metaheuristic methods [61, 62].
In [61], they presented an approach based in a genetic algorithm and tabu search that presented the ability of avoiding local optimum and compared their results with other methods. They conclude that tabu search needed longer computational time and the genetic algorithm could present good solutions without tabu search.
One of the most recent works is [63]. In this paper, they proposed to solve TEP problem using an imperialist competitive algorithm comparing the results with other evolutionary methods. Given that optimality is not guaranteed, comparisons between different heuristic performances are frequently found in last decade’s literature. Comparison in terms of time of performance and the quality of the solutions found is necessary in order to evaluate the suitability of certain proposed method [63].
2.2.3. Metaheuristics for G&TEP Problem
Recently, the coordinated problem G&TEP has gained more attention [23]. Given that the problem should be associated with uncertainty, market concepts, congestion management, reliability, distributed generation, and reactive power planning [23], metaheuristics are well suited to address this coordinated problem.
In [64], they present a novel idea on the model in the expansion and transmission planning problem: a multiobjective framework to evaluate the integration of distant wind farm. The first objective considers annual operation and investment cost while the second objective deals with minimizing the expected energy not served. In [65], they proposed a multiperiod-integrated framework based in genetic algorithms for GEP, TEP, and natural gas grid expansion planning for large-scale systems. It was applied to the Iranian power proving that the proposed framework can be applicable for large-scale real-world problems. In [66], they proposed a framework for transmission planning considering also generation expansion. In order to solve this interrelated multilevel optimization problem, the authors present an iterative solution linking agent-based and search-based algorithms. Murugan et al. and Kannan et al. published several works using sorting genetic algorithm version II (NSGA-II) to solve G&TEP problem [44, 45]. Lastly, the authors applied elitist nondominated NSGA-II to the combined G&TEP problem [67]. The addressed problem is multiobjective.
A combination of genetic algorithm and fuzzy technique was developed to solve the multiperiod G&TEP problem [68]. The framework optimizes multiple goals in a deregulated environment. The authors performed a comparison with genetic algorithms, NSGA-II, and others to evaluate the optimization method.
From the foregoing, we recap the following: (1)The evolution of metaheuristics described above is also valid when reviewing, in literature, the solutions presented for G&TEP with metaheuristics. Early works use pure metaheuristics; comparisons are made from 2000 to validate the method; hybridization is more commonly used in recent years. Nevertheless, hybridization is not recommended if a pure metaheuristic works well for a given scenario.(2)Metaheuristic approaches have proven to find high-quality solutions at relatively low computational costs when addressing G&TEP problem, hence optimality cannot be guaranteed. Heuristic methods generally perform better than classical ones for large problems where classical optimization methods become unmanageable [63].(3)In [69], they mentioned two difficulties when implementing evolutionary optimization methods for G&TEP problem: handling the highly constraints in large and medium G&TEP problems and large computational time-consuming algorithms that do not permit online applications. A drawback of heuristic and metaheuristic methods applied to G&TEP problem is that they highly rely in the setting of control parameters and operation mechanisms [50]. The search for the best settings is also a big challenge.
3. Mathematical Model
To solve the problem, in the following, a linearized stochastic mixed integer multiperiod problem is proposed, assuming the insertion of renewable energies. The power and location of wind units were chosen to take into account a generation and transmission reinforcement, as well as a totally new transmission case. The capacities of such elements were estimated to provide the expected demand in all periods of study. Thus, the problem minimizes an objective function of costs, subject to a set of constraints, which include the following: (i) investment constraints and (ii) operating constraints. The latter refer to both conventional and renewable generation costs, nonsupplied demand, and costs for failing with a percentage of clean energies; such costs are multiplied by a weighting factor associated with the number of hours of operation. For each scenario, the investment and operation costs are added along the entire planning horizon, and the resulting value in turn is multiplied by the probability of each scenario. The final investment integrates the sum of all the scenarios.
The economic assessment method used in this paper is the annual equivalent method [70], which converts the cost during the operational lifetime to an equivalent annual cost. The annual amortization rate multiplied by the capital cost of the proposed scheme (generating units and transmission lines) expresses the annual amortization cost. The amortization rate is expressed as (1), where is the interest rate or discount rate and stands for the project’s lifetime. The discount rate assumed in the studies becomes [71]. The lifetime for generating units and transmission lines has been considered as 35 and 40 years, respectively.
The set of constraints corresponding to investment (4), (5), (6), (7), (8), (9), and (10) takes into account the physical limitations of the generating units and the budget limit. Within the group of operating constraints (11), (12), (13), (14), (15), (16), (17), (18), (19), (20), (21), (22), (23), (24), (25), (26), (27), (28), (29), and (30), (11), (12), (13), (14), and (15) state that if there are operating points with the same demand, they will have the same expansion plan in generation and transmission. Power balance constraints, thermal capacity limits in existing lines and those proposed by the model, constraints of direct current (DC) power flows for existing lines and candidates are represented in (17), (18), (19), (20), and (21), respectively. The maximum generation capacity for existing and proposed units (conventional and clean) is guaranteed by (22), (23), (24), and (25). The limits on nonsupplied demand and the phase angle are described in (26), (27), and (28). The clean energy deficit for each operating point corresponding to each period and scenario is represented by (29) and (30); such a constraint implies that a fixed percentage of the loads must be supplied from renewable energies.
The objective function (2) and constraints (4), (5), (6), (7), (8), (9), (10), (11), (12), (13), (14), (15), (16), (17), (18), (19), (20), (21), (22), (23), (24), (25), (26), (27), (28), (29), and (30) are the following [13, 14, 17]: where subject to constraints:
The mixed integer nonlinear problem model preview is nonlinear, due to the products of binary and continuous variables in constraints (see (31)). These nonlinear constraints are replaced by the following sets of exact equivalent mixed integer linear constraints (32) and (33), where is a large enough positive constant.
Let us consider that prospective transmission line is built, that is, binary variable is equal to 1. In such a case, (32) and (33) impose that and . On the other hand, let us consider that prospective transmission line is not built, that is, binary variable is equal to . In such a case, (32) and (33) impose that and . First, we impose that the power flow through this transmission line is null. Second, we consider large enough bounds on the difference between the voltage angles at two nodes that are not connected through the disjunctive parameter [17].
In this paper, criterion was not included. To take it into account, it is necessary to consider the following aspects. The present work solves the G&TEP of the electric system under normal operating requirements since the objective is to forecast the capacity, location, and start date of operation of the generation units and transmission lines that will be installed in a given planning horizon. However, a safety study of the system can be included using security-constrained optimal power flow, where a contingency analysis is combined with an optimal power flow that seeks to make changes to the optimal dispatch of generation, as well as other adjustments, so that when a security analysis is run, no contingencies result in violations [72]. One of the easiest ways to provide a quick calculation of possible overloads is to use linear sensitivity factors. These factors show the approximate change in line flows for changes in generation on the network configuration and are derived from the DC load flow. Power transfer distribution factors (PTDF) and line outage distribution factors (LODF) are used to model the pre- and postcontingency constraints. A strategy is proposed in [73] where the authors use the nodal admittance matrix in order to transform the DC-network balance constraints to a global power balance equation, and the transmission limit constraints are modeled using the PTDF matrix. The proposed methodology solves the optimization problem taking into account only the power units to be built and the active power generation of each unit as decision variables. In [74], the PTDF and LODF are used to model the pre- and postcontingency constraints simultaneously in a stochastic model. In our work, we choose to make a good approximation of the contingencies in transmission using distribution factors based on [75]. We show its use applied to the 3-year period G&TEP case scenario (see Section 5.1).
Given the complexity of the problem, the authors decided not to include transmission losses in the formulation. Likewise, it was assumed that the degree of uncertainty handled in the proposal may be of the level of such losses; this, coupled with the fact of managing a sufficiently long term, results in a favorable aspect of the proposal in a stochastic environment.
Similarly to the transmission losses, the uncertainty that the wind energy systems have will fall within the ranges of randomness of the problem posed, especially as regard the load refers. For this reason, the authors consider that the results found may well be considered appropriate by the assumptions made, which gives additional value to the stochastic approach.
4. Design of Genetic Algorithm for G&TEP Problem
As we described in Section 2, genetic algorithms are among the most used metaheuristic techniques when addressing GET, TEP, or combined G&TEP problems. Hybrid metaheuristic approaches are recently used to solve complex real-world optimization problems, but it is important to avoid high computational costs if possible. Therefore, if a pure metaheuristic works well for a given scenario, it is not necessary to use a hybrid approach. In this section, we describe an attempt to solve the G&TEP problem with a genetic algorithm using this unconstrained optimization procedure and several constraint-handling techniques.
The well-known procedure of genetic algorithms considers an initial population of individuals, each representing a solution to the problem at stake. The set of individuals is evaluated with a fitness function to select those which represent the best solutions. The application of crossover and mutation operation to selected individuals generates new offspring at each epoch. The generations evolve as in natural selection, creating more fitted individuals delivering eventually a good solution to the problem. Algorithm 1 describes a simple genetic algorithm.
| ||||||||||||||
4.1. Individual Representation
The genetic algorithm begins by defining the solution representation, for example, chromosome or the array of variables to be optimized. The chromosome that defines and individual solution for the G&TEP proposed problem consists in an array of real variables that represent the decision variables (see Section 3) to be optimized in the case studies of G&TEP described in Section 5. A detailed description of a chromosome is presented in Table 1 for the 3-year period case study. The chromosome was encoded in a similar way for the 10-year period case study. Due to space restrictions and since the latter has 552,960 variables, we are not able to provide a detailed description of the values.
4.2. Evaluation Function
The evaluation function is based on the objective function () shown in (2) of the mathematical model. The feasibility of each G&TEP solution is subject to constraints corresponding to those described in the mathematical models (4), (5), (6), (7), (8), (9), (10), (11), (12), (13), (14), (15), (16), (17), (18), (19), (20), (21), (22), (23), (24), (25), (26), (27), (28), (29), and (30). In order to handle these complex constraints in the genetic algorithm, first, we transformed the constrained problem to an unconstrained problem. Next, we use seven different constraint-handling techniques to deal with the infeasibility, presented below.
4.3. Strategies of Constraint-Handling for G&TEP Problem
Several constraint-handling techniques have been adopted in order to handle high constraint problems. In this paper, we used different approaches inspired in the most popular constraint-handling techniques reported in [20]: static penalty functions. (1)Number of violated constraints: the first strategy consists in considering only counting the number of violated constraints so that (2)Objective function incorporating the number of constraints: this strategy follows a common penalty function incorporating the objective function plus a static penalty to the fitness function. When applying a penalization in the fitness function, we decrease the aptitude of those individuals that violate one or more constraints. where are the constraints not fulfilled by the individual and is a large constant.(3)Harmonic mean: this strategy, inspired in [76], formulates the fitness function as a harmonic mean of the two objectives: and . It tries to get a trade-off of and . (4)Feasibility differentiation: following [77], this approach defines a different fitness function to infeasible individuals. In this case, is not computed for all infeasible individuals. where = number of satisfied constraints and = total number of constraints.(5)Weighted: in this approach, the penalty is not the same for all the violated constraints. Based on the knowledge of an expert in the domain, weights are set for each constraint. where is the weight of constraint and .(6)Distance-based: the aim of this strategy is to measure the amount of the individual infeasibility. Fitness function is determined assessing the individual distance from the feasibility in each constraint. where is the evaluation of the individual in constraint and is the bound of constraint .(7)Squares of distance: this strategy seeks to achieve a greater sensitivity to the infeasibility of individuals.
4.4. Selection, Crossover, and Mutation Operators
The parents of each generation are selected by the tournament selection method, which randomly picks a small subset of mating pool and the lowest cost chromosome becomes a parent. This method avoids sorting as in elitisms providing a good choice of selection for large population sizes [78]. Crossover is done using a single-point crossover operator that picks two selected individuals with probability and randomly determines a crossover point so that the segments of the chromosomes beyond this point are exchanged to form two new individuals. Finally, each new individual is subjected to uniform random mutation operator that selects each gene of the individual and changes its value with probability .
5. Case Studies
In this work, two case studies were employed for testing a pure genetic algorithm in G&TEP problems. The first case study considers a three-year period time and eight scenarios that helped to configure the parameters of the genetic algorithm. Then, the second case study with a ten-year period and 1024 scenarios was considered for testing purposes.
5.1. Case Study 1: G&TEP for 3-Year Periods
Regarding the generating scenarios, in this paper, two demand levels are taken into account, Figure 1, where L means low demand and H means high demand. Likewise, it is assumed that subsequent periods exhibit L and H scenarios. Data for combinations in the tree diagram are obtained by using a uniform distribution with the intervals in Table 2. The second and third columns provide the lower and higher demand for the first period by each demand bus. Each period represents a year, which in turn has been divided into two operating conditions and , which weights (for all periods) become 6000 and 2760 hours, respectively. For this case study, it was assumed that and equal probability for each scenario . Notice that the test system has 4 load buses as shown in Figure 2. Then, for every load bus, there is a tree diagram similar to that in Figure 1. Tables 2 and 3 summarize demand for each operating condition and period during the planning horizon.
Figure 2 includes all elements described in the proposed formulation: (i) candidate transmission lines (dotted lines, and ); (ii) candidate conventional and wind generators ( and ). For each bus, low () and high () load demands are taken into account (see Tables 2 and 3). This gives rise to eight scenarios per bus (see Figure 1).
A linear stochastic mixed integer programming strategy was used for solving the problem from (2), (4), (5), (6), (7), (8), (9), (10), (11), (12), (13), (14), (15), (16), (17), (18), (19), (20), (21), (22), (23), (24), (25), (26), (27), (28), (29), and (30) using the above information for the 3-year period time. In this regard, the best expansion plan obtained is objective function = $468.85M USD.
Table 4 shows that the clean energy candidate unit with rating equal to 150 MW must be installed during the first period for all scenarios –. Table 5 indicates that the conventional candidate unit is installed during period for scenarios –. In the period , it is proposed to install an initial capacity for the scenarios – and an additional capacity for the scenarios –.
According to the information in Table 6, transmission line must be installed during period for the 8 demand scenarios, while line is installed during period for scenarios , and –. If scenarios and arise, it is installed during period .
Tables 7–13 summarize the installed capacity of clean and conventional power, as well as the number of lines installed along the planning horizon, Figure 3. The next step is related to the generators’ dispatch for each operating condition, period, and particular scenario. For this case study, there are two demand conditions and ; three periods , , and ; and eight scenarios –. Therefore, the present model generates 48 different ways of dispatching the generating units (). It is impossible to describe each case here, so the following analysis corresponds to the condition , , and . Figure 3 displays the magnitude of the power flow through the transmission lines –, the generation of units , , , , and , and the demand level at buses –.
An approximate analysis of the problem of contingencies by distribution factors [75] can corroborate that it is difficult to be able to operate satisfactorily in the face of out-of-service elements (either generation or transmission). For the system studied, Table 14 illustrates the case of contingencies in transmission. In that sense, the problem can be seen as a financial one, since to support the outage of elements, the others have to be oversized. Although there are direct ways of dealing with the problem of contingencies [79], the mentioned approach seems a good approximation in this case. That is, it is reiterated that in this case, one way to solve such problems is by oversizing the generation and transmission elements.
5.2. Case Study 2: G&TEP for 10-Year Periods
This case study considers the same model presented from (2), (4), (5), (6), (7), (8), (9), (10), (11), (12), (13), (14), (15), (16), (17), (18), (19), (20), (21), (22), (23), (24), (25), (26), (27), (28), (29), and (30). In this particular case, the demand for each operating condition and period was defined in correspondence of each one of 1024 scenarios. Data for combinations in the scenario tree are obtained by using a uniform distribution with the intervals summarized in Table 15 (only shown for , , and ). In the second and third columns of the same table, the lower and higher demands are provided for the first period by each demand bus. Similar to the previous case study, each period represents a year, which in turn has been divided into two operating conditions and , with weights (for all periods) becoming 6000 and 2760 hours. This case study assumes and equal probability for each scenario of . Notice that test system has 4 load buses, as shown in Figure 4. Then, for every load bus, there is a tree diagram similar to that in Figure 5. The demand for each operating condition and period was defined in correspondence of each one of 1024 scenarios. The installed capacity for clean energy for all ten periods and 1024 scenarios was set to 60 MW.
Figure 4 includes all elements described in the proposed formulation: (i) candidate transmission lines (dotted lines, and ); (ii) candidate conventional and wind generators ( and ). For each bus, low () and high () load demands are taken into account (see Tables 15–20. This gives rise to one thousand twenty-four scenarios per bus (see, e.g., Figure 5). The strategy to solve the problem is the linear mixed integer programming. After solving problems (2), (4), (5), (6), (7), (8), (9), (10), (11), (12), (13), (14), (15), (16), (17), (18), (19), (20), (21), (22), (23), (24), (25), (26), (27), (28), (29), and (30), the optimal expansion plan considers an objective function value of $3375.6M USD.
Table 16 indicates that the conventional candidate unit is installed from the period . Table 17 provides information about transmission lines. Tables 18–20 summarize the installed capacity of clean and conventional power, as well as the number of lines installed along the planning horizon, as shown in Figure 6. The next step is related to the generators’ dispatch for each operating condition, period, and particular scenario. For this case study, there are two demand conditions and ; ten periods –; and one thousand twenty-four scenarios –. Therefore, the present model generates 20,480 different ways of dispatching the generating units (). It is impossible to describe each case here, so the following analysis corresponds to the condition . Figure 6 displays the magnitude of the power flow through the transmission lines –, the generation of units , , , , and , and the demand level at buses –. Data for costs of nonsupplied demand and operating conditions were used from Tables 9 and 10.
6. Experiments and Results
In this section, we describe the computational experiments designed to assess the performance of the proposed genetic algorithm, and we present the corresponding results. We make a comparative analysis of constraint-handling techniques applied in the pure genetic algorithm for three- and ten-year period time case studies of G&TEP problem. In these complex optimization problems with high number of constraints, it is very difficult even to find feasible solutions. The aim of the experiments is to determine which of these techniques is able to reduce the number of constraints that are not fulfilled and is better suited for complex problems. Therefore, even if infeasible solutions are reported, the purpose of identifying the best strategy was achieved.
6.1. Experiments
We designed eight experiments for each of the three- and ten-year period time case studies. The first experiment was done for comparison purposes just taking into account the unconstraint problem. The fitness function is equal to the computation of the objective function of the case study. No penalty was incorporated to the fitness function (individual) = . Seven computational experiments were performed to test the effectiveness of the constraint-handling strategies presented in Section 4. The parameters of the pure genetic algorithm were set as shown in Table 21 for all experiments.
6.2. Results
For comparison purposes, we used the results of the best solution found of each experiment. We report the best result in the objective function of each experiment. The fitness function cannot be compared given that each constraint-handling strategy is computed in different ways. We also calculate the distance of the best with the aim of determining the completion cost, that is, the distance to feasibility. The number of constraints violated by the best solution in the generation is also considered.
First, we conducted the experiments over case study 1 (3-year period G&TEP problem). For the analysis, we also considered comparing the effectiveness of the pure genetic algorithm when the initial population is created randomly, but bounded; and also in the case when the initial set of individuals is populated with an initial guess trying to fulfill with all constraints, as many as possible. Table 22 summarizes the results for all experiments, including the following information: best , the distance to feasibility of the best presented as the sum of the absolute error calculated with (39) and the relative error of the distance to feasibility, and the number of violated constraints of the best . In addition, the evolution of the fitness function through generations is presented in Figures 7–14 for both initialization procedures (black lines for random and red lines for prior) and using all handling-constraint strategies.
In terms of the random initialization, the results of the first experiment (Figure 7), considering the unconstrained problem, show that although it seems to achieve the best , the distance to feasibility of the best solution is huge in relation to a great number of constraints violated. The next experiments were compared with this result in order to determine the quantity of improvement obtained with each of the different proposed strategies. Then, in the second experiment, we applied the number of violated constraints strategy (strategy 1). The results show a considerable improvement in the distance to feasibility. Nevertheless, the best increased significantly (Figure 8). The third experiment uses strategy 2 (Figure 9) which incorporates the number of violated constraints to the objective function. Although the distance to feasibility and the number of violated constraints remained similar to the previous experiment, the best is below from the best solution presented in Section 5. The harmonic mean strategy (strategy 3, Figure 10) was applied in the fourth experiment. Even if this strategy balanced both objectives, the distance of feasibility and number of constraints violated, the best remained below the best solution. The feasibility differentiation strategy (strategy 4, Figure 11) did not provide a significant improvement in comparison with previous strategies. The performance of weighted strategy (strategy 5, Figure 12) is similar to the results obtained in strategy 2, hence the infeasibility of the best solution shown with the distance increased. The performance of the distance-based strategies 6 (Figure 13) and 7 (Figure 14) proved to obtain a solution closer to feasibility region. They achieved the best improvement in comparison with the first experiment. However, the is still not close to the best solution of the case study.
In contrast to the random initialization process, results from deliberative initialization showed a significant improvement in terms of the number of constraints violated. It is evident that fulfilling more constraints, the objective function increases more than when many constraints are violated. Moreover, the distance of the best also decreases, as expected. To this end and considering the above results, strategies 4, 6, and 7 are the better alternatives for using in a pure genetic algorithm for solving the G&TEP problem. Prior initialization avoiding constraint failure is an improvement for the algorithm, too. Also, it can be observed that an abrupt change in the evolution of the minimization of the fitness function occurs in less than 150 generations.
Later on, we conducted the experiments over case study 2 (10-year period G&TEP problem). Notice that this problem is challenging in the way that there are 552,960 variables for optimizing, in contrast to the 1152 variables from the 3-year period G&TEP problem. Thus, we ran the experiments using the observations from the previous case study: prior initialization of the population was done trying to fulfill the constraints as many as possible, and a maximum of 200 generations was fixed. Table 23 summarizes the results of all the experiments over case study 2, and Figures 15–22 show the evolution of the fitness function over generations.
As shown in the results, strategy 4 (Figure 19) obtained the least number of violated constraints among the other strategies. However, it can be seen that all strategies had difficulties to minimize the fitness functions, in comparison to the unconstrained strategy. However, in terms of the distance of the best , strategies 6 and 7 were the best ones comparing to the unconstrained strategy. It is remarkable to say that these experiments had issues in terms of the implementation. For this case study, all experiments were run in a flexible cloud-service in order to achieve the results because they could not run under a standard quadcore computer, as done for case study 1.
To this end, the present analysis highlights that using a pure genetic algorithm for G&TEP problems can achieve a first approximation to a suitable solution. However, it is worth noting that other optimization approaches should be selected in order to handle this complex problem. Furthermore, it can be shown that strategies 4, 6, and 7 consistently achieve better results than the other strategies, and a prior initialization of the population is a key insight for further research when dealing with G&TEP problems.
7. Conclusions and Future Work
In this paper, we proposed a multiperiod stochastic model applied to the G&TEP problem considering the insertion of renewable energies, which objective is to achieve a generation and transmission expansion plan that minimizes the total cost of investment. In addition, we proposed to address the G&TEP problem with a pure genetic algorithm approach. Different constraint-handling techniques were applied to deal with the complex case studies.
The comparative analysis conducted in this work shows that although we applied many of the most commonly used constraint-handling techniques reported in literature, our proposed genetic algorithm did not performed efficiently as required. The best solutions reported did not provide a feasible solution. From these results, we can state that a pure metaheuristic approach like genetic algorithm is not fitted for this particular G&TEP case study with clean energies, which is a nonlinear complexity problem with a high number of constraints (e.g., the 10-year period G&TEP problem). However, our analysis showed that the techniques to handle constraints with penalty functions based on the feasibility differentiation, the absolute-distance, and the squares-of-distance performed better than the other implemented strategies. Ultimately, a pure genetic algorithm implementing those strategies, as well as a prior initialization of the population, promotes a first approximation to a suitable solution if other optimization approaches are then conducted.
Unless these results with a metaheuristic method apparently show worst performance than the linear stochastic mixed integer programming method, a large-scale real-world problem cannot be solved without using metaheuristic optimization approaches as stated in [18]. Therefore, for future work, we will explore hybrid metaheuristic approaches for this G&TEP problem. With regard to the mathematical model, we will search for possible valid inequalities to ensure a bigger feasibility region. We will also explore an analysis including contingencies.
Notations
Indices| : | Buses |
| : | Existing conventional generators |
| : | Existing clean energy generators |
| : | Candidate conventional generators |
| : | Candidate clean energy generators |
| : | Demand |
| : | Transmission lines |
| : | Operating conditions |
| : | Time periods |
| : | Scenarios. |
| : | Candidate transmission lines |
| : | Conventional existing generators located at bus |
| : | Existing wind generators located at bus |
| : | Candidate conventional generators located at bus |
| : | Candidate clean energy generators located at bus |
| : | Demand at bus |
| : | Sending bus for transmission line |
| : | Ending bus for transmission line . |
| : | Susceptance of transmission line |
| : | Production cost of the conventional candidate generating unit |
| : | Production cost of the clean candidate generating unit |
| : | Cost of the not supplied demand not supplied |
| : | Production cost for the existing conventional generating unit |
| : | Production cost of the existing clean generating unit |
| : | Rating of the transmission line |
| : | Investment budget to build the clean generation candidate unit |
| : | Investment budget to build the conventional generating candidate unit |
| : | Investment budget to build the candidate transmission line |
| : | Investment cost for the candidate clean generation unit |
| : | Investment cost for the candidate conventional generating unit |
| : | Investment cost for the candidate transmission line |
| : | Maximum generation capacity of the candidate clean generation unit |
| : | Maximum generation capacity of the candidate conventional generation unit |
| : | Maximum demand |
| : | Maximum production capacity of the existing conventional generation unit |
| : | Maximum production capacity of the existing clean energy generation unit |
| : | Weight of the operating condition |
| : | Penalization cost for breaching the renewable portfolio requirement |
| : | Amortization rate [%] |
| : | Clean energy’s goal [%] |
| : | Probability of the scenario . |
| : | Binary variable: equal to 1 if the candidate transmission line is constructed, and 0 otherwise. |
| : | Power supplied by the existing conventional generating unit |
| : | Power supplied by the existing wind generating unit |
| : | Power supplied by the candidate wind generator unit |
| : | Power supplied by the conventional candidate generating unit |
| : | Not supplied demand |
| : | Power flow through the transmission line |
| : | Angle of voltage at bus |
| : | Rating of the candidate clean generation unit |
| : | Rating of the candidate conventional generating unit |
| : | Deficiency of the renewable goal |
| : | Objective function, total investment . |
| : | Fitness function |
| : | Number of violated constraints |
| : | Large penalty constant |
| : | Number of satisfied constraints |
| : | Total number of constraints |
| : | Penalty weights |
| : | Bounds of constraints. |
Data Availability
The data used to support the findings of this study are available from the corresponding author upon request.
Conflicts of Interest
The authors declare that they have no conflict of interest.