An Improved Hybrid Particle Swarm Optimization and Tabu Search Algorithm for Expansion Planning of Large Dimension Electric Distribution Network

Abstract

Optimal expansion of medium-voltage power networks is a common issue in electrical distribution planning. Minimizing the total cost of the objective function with technical constraints make it a combinatorial problem which should be solved by powerful optimization algorithms. In this paper, a new improved hybrid Tabu search/particle swarm optimization algorithm is proposed to optimize the electric expansion planning. The proposed method is analyzed both mathematically and experimentally and it is applied to three different electric distribution networks as case studies. Numerical results and comparisons are presented and show the efficiency of the proposed algorithm. As a result, the proposed algorithm is more powerful than the other algorithms, especially in larger dimension networks.

1. Introduction

Due to load demand growth, the different component of distribution networks should be planned optimally. Many papers have been published in which the optimal distribution network components have been planned using different techniques and algorithms. For example, the optimal planning of energy storage in [1,2,3], wind distributed generation in [4,5], hybrid energy storage and distributed generations in [6,7] have been proposed. One of the planning components is the expansion of existent network so that the high voltage/medium voltage (HV/MV) substations are allocated and medium voltage feeders are expanded optimally. The optimal planning is carried out considering a complex objective function, where technical and economic constraints are taken into account. The objective function, generally, includes the network investment cost and power loss cost. The main constraints are also satisfaction of supply-demand requirements and grid nodes’ voltage and grid lines’ capacity. In addition, the distribution network should have a radial configuration because of protection systems constraints.

Different mathematical methods and optimization algorithms have been developed in the literature to optimal expansion planning of the distribution network. The authors in [8] have proposed a comprehensive review of classical models and issues for distribution planning. However, the classic methods need high computational cost. The metaheuristic-based optimization algorithms can find a global solution of the problem with an acceptable computation cost. Genetic algorithm (GA), particle swarm optimization (PSO), Tabu search (TS), simulated annealing (SA), ant colony optimizations (ACO), and branch exchange (BE) are the most popular types of metaheuristic algorithms that are used for distribution network planning in [9,10,11,12,13,14,15]. In addition, different hybrid methods have improved in [16,17,18,19,20,21,22] for optimal distribution networks. Although, the metaheuristic algorithms have a good ability to find the optimum solution, they may find the global optimum point when the problem is more complex. The optimal planning of the distribution network becomes a complex problem if the dimension of the network is high. Therefore, the conventional modern metaheuristic algorithms cannot find the global optimum solution for high dimension distribution networks. In this paper, a new improved hybrid algorithm is proposed that includes PSO and TS algorithms and some adaptations are also taken into account. The proposed modified optimization algorithm is applied to the planning of a single stage distribution network in different scenarios. The mathematical analysis and simulation results show that the proposed modified optimization algorithm, in comparison with other algorithms, has better performance especially in the high dimension distribution network.

2. Problem Statement

This section explains the mathematical formulation of the distribution network expansion planning. The location and type of feeders as well as the allocation of new substations and/or the capacity increment of existent substations are the results of the defined problem. The cost of objective function is minimized under technical and economic constraints. The objective function includes the investment cost and power loss cost. The optimal distribution network must supply the required load demand and keep the grid nodes’ voltage within the allowable boundary. In addition, grid feeders’ capacity should not be violated and the configuration of the network must be radial. Therefore, the mathematical formulation can be written as Equation (1). The technical constraints are presented as Equations (2)–(5).

Objective function:

$$\begin{array}{ll}F=& {\displaystyle \sum _i{x}_{i,a}\times L_{i,a}\times C_{Con,i,a}}\\ & +{\displaystyle \sum _j{y}_j\times C_{Sub}(S_j,S_{Ins,j})}\\ & +{\displaystyle \sum _t\{[{\displaystyle \sum _i{P}_{Loss,f,i}+{\displaystyle \sum _j{P}_{Loss,s,j}]}}}\\ & \times C_E\times (\frac{1+Intr}{1+Infr})\times {(1+Incr)}^{2(t-1)}\times 8760\}\end{array}$$

(1)

Constraints:

$${\displaystyle \sum _i{P}_{s,i}}\ge P_{Loss}+{\displaystyle \sum _j{L}_j}$$

(2)

$$V_{\min }\le V_i\le V_{\max }$$

(3)

$$0\le x_{i,a}\times S_{i,a}\le S_{\max ,i,a}$$

(4)

$$N_b=N_l$$

(5)

where C_Con,i,a = 0 for existent feeders and C_Sub is a discrete function.

In a radial configuration, each load node should be fed by only one substation. So feeding a load from two different substations makes a loop in the network which is not allowed.

3. Proposed Optimization Algorithms

Although, the metaheuristic algorithms have a good ability to find the optimum solution, they may find the global optimum point when the problem is more complex. The optimal planning of the distribution network becomes a complex problem if the dimension of the network is high. Therefore, the conventional modern metaheuristic algorithms cannot find the global optimum solution for high dimension distribution networks. In this paper, a new improved hybrid algorithm is proposed that includes PSO and TS algorithms and some adaptations are also taken into account. The details of the proposed optimization algorithm are as follows.

3.1. Tabu Search

TS is an intelligent search algorithm that is based on the neighborhood evaluations. Starting from an initial solution, in each iteration the best neighbor solution is selected to move, although it increases the objective function of the current solution. So, TS includes the hill-climbing movements, too. Moreover, a Tabu list, as a memory, is used to prevent cycling movements. In practice, the probability local search is used in TS and therefore there is no guarantee to achieve a global optimum especially in large dimension problems [9]. However, TS is not used merely for the distribution network planning problem and it needs improvements or commonly is used as an auxiliary algorithm [17,21].

3.2. Particle Swarm Optimization

PSO is a swarm intelligent algorithm that is based on the movement of some groups of particles which share their explorations among themselves. This technique is motivated by simulation of social behavior. Instead of using evolutionary operators to manipulate the individuals like in GA, each individual in PSO called particle flies in the searching space with a velocity, which is dynamically adjusted according to its own flying experience and its components’ flying experience. Assuming that the searching space is n-dimensional, the ith particle of the swarm is presented by the vector $x_i=(x_{i1},x_{i2},\dots ,x_{in})$ with a flying velocity $v_i=(v_{i1},v_{i2},\dots ,v_{in})$. Each particle maintains a memory of its previous best position and swarm remembers its global best position. The particles are manipulated according the Equations (6) and (7).

$$v_{ij}=w{v}_{ij}+c_{1}r(x_{pbest,ij}-x_{ij})+c_{2}r(x_{gbest,j}-x_{ij})$$

(6)

$$x_{ij}=x_{ij}+v_{ij}$$

(7)

where $i=1,2,\dots ,N_p$ and $j=1,2,\dots ,n$.

However, in discrete space Equation (7) is modified as Equation (8).

$$x_{ij}=1\mathrm{if}r<sigmoid(v_{ij})$$

(8)

where:

$$sigmoid(v_{ij})=\frac{1}{1+e^{-v_{ij}}}$$

(9)

From Equation (6) it is found that the particles’ velocity will be slowed down and the swarm is congregating for $x_{gbest}$ if the latter two terms are zero. As a result, the swarm global best individual $x_{gbest}$ may not be updated for a long time and the algorithm converges to a local optimum, especially in smaller problems. So sometimes the restricted velocity is introduced [23] as Equation (10).

$$v_{\min }\le v_{ij}\le v_{\max }$$

(10)

Moreover, using a dynamic mutation operator of GA in PSO, as a hybrid GA/PSO, instead of the restricted velocity is introduced [22]. In such hybrid algorithm, the mutation rate must be decreased during iterations because the constant mutation rate may disturb the converging. However, the mutation operator is commonly needed in small size problems.

This section includes three parts: The first part describes the proposed algorithm for modification of the particles’ movement; the proposed hybrid algorithm is explained in part two and the proposed algorithm for expansion of substations with feeders is presented in the third part.

3.3. Proposed Movement Algorithm

The proposed algorithm is based on two new controller parameters (z and q₀) and a Tabu list (T) of branches as candidate feeders of the network. In this algorithm, the removing-from-network movements are controlled and the left movements are restricted by the constraints of the problem. In the first step, T is empty and the velocity vector (v_i) of the moving individual (x_i) is calculated by Equation (11).

$$v_{ij}=w{v}_{ij}+c_{1}r|x_{ij}-x_{pbest,ij}|+c_{2}r|x_{ij}-x_{gbest,j}|$$

(11)

In the next step, all selected branches of x_i with high velocity and not the selected branches of x_i with low velocity are moved to the Tabu list with a probability of q₀ if they are not selected in the best global position. Controller q₀ is a constant parameter that determines the importance of intensification and diversification of the algorithm. The criterion of velocity is: $\mathrm{sigmond}-z$, where $0\le z\le 1$ and it is a constant parameter that controls the intensification of the Tabu list.

Finally, a new individual is generated of not-Tabu branches and it is substituted as a moved individual if it satisfies the constraints. The flowchart of this algorithm is presented in Figure 1.

3.4. Hybrid TS/PSO Algorithm

In this paper, a PSO-based hybrid TS/PSO is proposed for the distribution network expansion planning. The hybrid algorithm includes the neighborhood search for the best position of each group x_pbest,i (that: $i=1,2,\dots ,N_g$) and set the best neighbor as the new best position of group, if it satisfies the constraints and also it improves the previous best position. This process repeats in each iteration after moving the particles. Flowchart of the hybrid algorithm is presented in Figure 2.

Local searches in TS/PSO can be supposed as intelligent mutations that control the diversification and they do not disturb the converging. This may be important in small dimension problems or in the converging conditions for large problems.

3.5. Proposed Algorithm for Substations Expansion

In the distribution network expansion planning because of the load growth, it may be needed to add some new HV/MV substations to the network. Added substations are selected among some candidate substations. In this paper, a two-phase and one-switching algorithm is proposed to expand both substations and feeders of the distribution network. In phase one, each group of particles loads a random feasible configuration of substations and evaluates the candidate configuration of substations using the proposed hybrid algorithm for feeders expansion. In this phase, $q_0\approx 0.5$ and also mutation in the substations’ states is needed to avoid the soon converging to a local optimum in the substations search space. In these conditions, it can be proofed that the optimum mutation rate is: $m_{best}=\frac{1}{N_{Sub}}$ [24]. After enough iteration, the algorithm is switched to phase two that uses the selected information of the first phase. In the switching step, the selected substations of the best solution resulting of phase one are selected for all groups in phase two and all other information is reset. In the second phase, $0.5<<q_0<1$ and $m=0$ and the search space is of the feeders’ configuration. Here, a step-decreasing mutation rate is used because of the difference between two search spaces. The algorithm can be stated as follows.

First Phase:

Search in substations’ configuration space based on feeders’ configurations search;

• Using mutation in substations
• Using the proposed hybrid algorithm in feeders
• Set a medium q₀

Switching Step:

After enough iteration;

• Set $m=0$
• Set $S_{Sub,i}=S_{Sub,best}$ (that: $i=1,2,\dots ,N_p$)
• Reset all feeders’ positions and velocity vectors

Second Phase:

Search in feeders’ configurations space based on the best selected substations;

• Using the proposed hybrid algorithm in feeders
• Set $q_0\approx 1$(depends on network size)

4. Mathematical Modeling

In this section, the mathematical model of the proposed methodology is presented. To analyze the proposed algorithm and its advantages a parameter called success probability (P_Suc) is used. Success probability is defined as the probability of changing at least one incorrect component and not changing any of the correct components of a solution. Here, P_Suc is defined for the best individuals of the groups and the success at least in one of them. The similar success probability can be defined for other individuals too; however, it is neglected in this paper. So the success probability mathematically is as Equation (12).

$$P_{Suc}=\{1-{(1-P_{Ch})}^{i\times N_g}\}\times \{1-{[1-{(1-P_{Ch})}^{n-i}]}^{N_g}\}$$

(12)

where i is the number of incorrect components and P_Ch is the probability of changing a component by the algorithm’s operators in an iteration. Changing the probability of the improved PSO algorithm is as Equation (13).

$$P_{Ch}=\sigma \times (\frac{1}{1+e^{-v_1}}-z)+(1-\sigma )\times (\frac{1}{1+e^{-v_2}}-z)\times (1-q_0)$$

(13)

where $0\le \sigma \le 1$ is the variance of the all best solutions of groups from the global best solution and v₁ and v₂ are components of the velocity vector when $x_{ij}\ne x_{gbest}$ and $x_{ij}=x_{gbest}$, respectively and they are obtained of Equation (11). It is found of Equation (11) that: $v_{\min }\le v_2\le v_1\le v_{\max }$. Whereas the initial population of the PSO algorithm is generated randomly so we expect that $i=\frac{n}{2}$ in Equation (12) for the first iteration and i is decreased partly during the iterations of the algorithm.

Using $0<q_0<1$ in Equation (13) describes that if the best solution of the group is similar to the global best, it is changed with lower probability. As a result, if the parameter q₀ increases the variance decreases as Equation (14).

$$\sigma \propto (1-q_0)$$

(14)

Equations (12)–(14) can describe the influence of problem dimension on the success probability of PSO. Figure 3 presents the influence of n on the P_Suc of conventional PSO and the proposed improved PSO using Equations (12)–(14), $N_g=10$, $v_1=5$, $v_2=0.1$, $z=0.5$ and $i=\frac{n}{10}$ in Equation (12) as normal conditions.

Figure 3 shows that P_Suc of the conventional PSO ($q_0=0$) is high enough for low dimension networks ($5<n<50$), but is poor when the dimension is high. Increasing q₀ in the improved PSO algorithm increases the success probability and shifts the maximum point of it to the higher dimension problems. Therefore it is more powerful for large-scale distribution networks planning. However, decreasing the controller parameter z may disturb the success of the algorithm. The influence of parameter z on the success probability in various problem dimensions is presented in Figure 4, using Equations (12)–(14), $N_g=10$, $v_1=5$, $v_2=0.1$, $z=0.5$, $i=\frac{n}{10}$ and $q_0=0.98$.

The figure shows that the success probability in high dimension problems ($200\le n\le 300$) is poor if parameter z decreases ($0\le z\le 0.4$). Increasing z to 0.6, improves the success probability in $n=300$. However, increasing z is not needed in low dimension problems. Additionally, it is found of Equation (13) that z should be increased if q₀ is decreased.

Adding local searches to the improved PSO increases the probability of changing incorrect components and it decreases the probability of changing correct components. The probability of changing a component in one neighborhood search, using the branch exchange algorithm, is equal to $\frac{2}{n}$. So, the probability of not changing a correct component in any d local searches, after it was changed by the PSO, is equal to ${(1-\frac{2}{n})}^d$ and the probability of not changing an incorrect component in any d local searches, after it was not changed by the PSO, is equal to ${(1-\frac{2}{n})}^d$. As a result, the success probability of hybrid algorithm is as Equation (15).

$$\begin{array}{l}{P}_{Suc}=\{1-{[(1-P_{Ch})\times {(1-\frac{2}{n})}^d]}^{i\times N_g}\}\times \\ \{1-{[1-{(1-P_{Ch}\times {(1-\frac{2}{n})}^d)}^{n-i}]}^{N_g}\}\end{array}$$

(15)

where P_Ch is obtained of Equation (13).

To analyze the advantage of using local searches in PSO, in convergence conditions for high dimension problems, suppose that in Equations (13) and (15), we have $n>>1$, $i<<n$, $\sigma <<1$, $d\ge 1$, $q_0\approx 1$ and so $P_{Ch}\approx (\frac{1}{1+e^{-v_2}}-z)\times (1-q_0)<<1$, then the success probability is as Equation (16).

$$P_{Suc}\cong \frac{2id}{n}[N_g-(1-q_0)\times (n-2d)]\cong 2d{N}_g(\frac{i}{n})$$

(16)

where the following approximation is used:

$${(1+\alpha )}^{\beta }\approx 1+\alpha \beta$$

(17)

where $\alpha <<1<<\beta$.

It is found of Equation (16) that in converging conditions ($\frac{i}{n}<<1$), if $d=1$ then $P_{Suc}<<1$, but using $d>>1$ increases the success probability. As a result, increasing the local search size is more efficient than increasing the group size, until $d<N_g$. Figure 5 presents the influence of the local search size on P_Suc in various problem dimensions using Equations (13)–(15) where $i=\frac{n}{50}$.

Figure 5 shows that using TS in PSO increases the P_Suc in all problem dimensions; however the increment is less in larger problems.

5. Case Study

In order to show the capability of the proposed algorithm for solving the distribution network expansion planning problem, three different distribution networks as case studies are presented. The first case is a 23-bus network with one existent HV/MV substation, for expanding only the feeders. The second case is a 48-bus network with one existent HV/MV substation, for expanding only the feeders. The third case is a 71-bus network with one existent and five candidate HV/MV substations and it includes both substations and feeders expansion. Economic data are shown in

Table 1. Economic data for numerical studies.

Economic Parameters	Value
Electrical Energy Cost ($/MWh)	50
Inflation Rate	0.12
Interest Rate	0.07

and more details of the cases are presented in

Table 2. Information of three cases for numerical studies.

Parameters of Cases	Case 1	Case 2	Case 3
Voltage Level (kV)	33	20	20
Number of Load Nodes	22	47	65
Number of Existent Substations	1	1	1
Number of Candidate Substations	0	0	5
Number of Existent Feeders	8	16	24
Number of Candidate Feeders	41	119	178
Average Load per Node (kW)	320	315	800
Power Factor	0.9	0.9	0.9
Annual Increment Load Rate	0.01	0.03	0.03
Time Period (years)	20	15	15

. More details about the case studies including networks configuration, candidate substation positions, etc. can be found in [25,26].

The proposed algorithm is applied to the three cases in three statuses. In the first status, conventional PSO is applied to the cases. The Improved PSO (IPSO) without hybridization is applied in the second statuses. The hybrid Tabu Search/Improved PSO (TS/IPSO) is applied to the cases in the third status. Moreover, the proposed two-phase algorithm in Section 3.5 for substations expansion is used in the third case for all statuses. Controller parameters of algorithms are presented in

Table 3. Controller parameters of algorithms in three case studies.

Controller Parameter	Value
	Case 1	Case 2	Case 3
w	0.9	0.9	0.9
(c1, c2)	(1, 0.1)	(1, 0.1)	(1, 0.1)
Ng	10	10	10
(vmin, vmax)	(0.1, 5)	(0.01, 10)	(0.01, 10)
m	0	0	0.1
Z *	0.6	0.5	0.5
q0 *	0.8	0.95	0.5, 0.995
d *	5	10	10

* All of them are defined in the Nomenclature.

, regarding the mathematical analysis in Section 4. The results of each algorithm are presented in Figure 6, which shows the objective function and convergence time of the algorithms in three case studies.

The results show that objective functions of PSO, IPSO and TS/IPSO are the same in case 1 (where $n=41$), but the convergence time is decreased by improvement and hybridization. However, the objective function is decreased by IPSO in cases 2 and 3 (where $n=119$ and $n=183$, respectively) and it is decreased more by the hybrid TS/IPSO. As a result, the proposed algorithm is more efficient in larger-scale distribution networks expansion planning.

To show the advantage of the proposed algorithm compared with the other algorithms, six modern algorithms are applied to the same three case studies which are described in Table 2 and the results are compared with the proposed hybrid TS/IPSO algorithm’s result. Figure 7, Figure 8 and Figure 9 present the comparison of the objective functions obtained of SA [12], TS [23], improved GA (IGA) [18,19], hybrid SA/TS [20], hybrid TS/IGA [21], hybrid GA/ACS [13] and proposed algorithm in three case studies.

The comparisons show that all algorithms obtain the same solution in case 1, however only hybrid TS/IGA and the proposed TS/IPSO algorithms obtain the global optimum in case 2 which is larger than case 1. According to Figure 9, the proposed algorithm obtains the best solution among all algorithms in case 3 which is larger than case 2. This figure also shows the efficiency of the proposed two-phase algorithm for substations and feeders expansion in large-scale networks compared with the other modern algorithms.

6. Conclusions

Particle swarm optimization is a modern algorithm which is extremely applied to various combinatorial optimization problems. However, it needs diversification in low dimension problems such as HV/MV substations expansion and it needs intensification in high dimension problems such as the distribution feeders expansion. In this paper, a modified PSO algorithm which is improved by increasing diversification in substations expansion and increasing intensification in feeders expansion, is proposed. Moreover, local searches, as intelligent mutations, were added to the modified PSO to improve the algorithm in converging conditions for feeders expansion. As a result, particles’ movements of the improved PSO move the hybrid algorithm to proper areas and local searches find the best point of the area. Finally, combining the algorithms for substations and feeders expansion in the proposed serial two-phase algorithm makes the proposed PSO-based hybrid TS/IPSO algorithm a powerful method for large-scale distribution networks expansion planning. Mathematical analysis and numerical comparisons show that the proposed TS/IPSO algorithm has better performance in comparison with other algorithms including SA, TS, IGA, SA/TS, TS/IGA, and GA/ACS. Moreover, the ability of the proposed methodology is more highlighted in case studies 2 and 3, where the dimension of the electric network is high.