Mathematical modelling of bio-inspired frog leap optimization algorithm for transmission expansion planning

1.   Introduction

Evolutionary algorithms (EAs) are stochastic optimization techniques that imitate natural biological evolution, i.e., the social behavior of species ^[1]. Most research focuses on stochastic optimization, searching simultaneously on a set of points to reach a global optimum solution ^[2]. The objective function decides the search space. Meta-heuristic methods amalgamate the optimization and heuristic techniques ^[3]. With the introduction of high-speed parallel processing, the solution of large-scale optimization algorithms has become very easy and time-saving for researchers. Various optimization problems have been solved by other meta-heuristic approaches, like the expert system ^[4], the object-oriented model, fuzzy set theory ^[5,6], the greedy randomized adaptive search procedure (GRASP), the strength Pareto evolutionary algorithm (SPEA) ^[7], other modern AI techniques like particle swarm optimization ^[8], AI-hybrid approaches ^[9], ant colony optimization ^[10], bacterial foraging technique ^[11], the game theory approach ^[12], and the shuffled frog leap algorithm ^[13].

One of the newly developed AI algorithms, the shuffled frog leap (SFL) algorithm ^[14,15,16], is a bio-inspired method used to optimize the function restricted by constraints ^[17]. It is effective but faces slow convergence, and sometimes it becomes trapped with the locally optimal points ^[18,19,20]. Eussuf and Lansey ^[14] proposed a shuffled frog leap algorithm (meta-heuristic approach) for solving water distribution network optimization tasks. Like most optimization algorithms ^[21,22], shuffled frog leap algorithm (SFLA) is also a cooperative search algorithm, which initializes with the population of solutions (frogs) and then allows the leaps within the memeplex for searching a place that has the maximum amount of food ^[15]. It could be used to solve nonlinear, non-differentiable, and multimodal complex optimization problems effectively ^[13].

Since its inception, the transmission system expansion planning problem has been solved using several algorithms as single or multiple objective optimization problems based on the optimizing factor of cost. The main contribution of this paper can be summarized as follows:

• We have provided a thorough empirical analysis of MSFLA;

• we have designed a new enhanced version of MSFLA for the transmission system expansion planning task;

• we have compared MSFLA and the proposed EMSFLA and have presented the empirical results of different scenarios, with evidence of the outperformance of EMSFLA over MSFLA.

2.   Frog leap algorithms

2.1.   Shuffled frog leap algorithm (SFLA)

In the SFLA, the population is a set of solutions (frogs) partitioned into various subsets, known as memeplexes. Different memeplexes are assumed as other cultures of frogs. Inside every memeplex, a local search is performed for the local best solution. These memeplexes are further evolved in the process of memetic evolution. After a pre-defined number of different memetic evolutions, the memeplexes go to the operation of shuffling, and the process of memeplex-evolution and shuffling repeats until the convergence criteria are met, which is generally pre-defined ^[14,15]. In the SFLA, the ideas are interchanged among individuals in memeplexes during memetic evolution by performing a local search (Figure 1). Further, the ideas are interchanged among all individuals taking part in optimization through a shuffling strategy. This step leads toward a global optimum solution ^[14].

Initially, the population is to be generated arbitrarily ^[23,24] to keep the solutions mimicked as frogs, which are to be arranged according to their fitness values in a decreasing manner. Pf (Pf = initial population of frogs) is then partitioned into memeplexes wherein each memeplex has s frogs (s = number of frogs in each memeplex). The frogs are divided into memeplexes as per their locations. The best and worst solutions for each memeplex and the position of the global best frog of the entire population are identified. After that, the SFL is applied to improve each frog's fitness with the lowest (worst frog) in every iteration.

The fitness function of the frog can be configured as the application domain. Each frog is considered to be a potential solution to the problem; therefore, the fitness value of a frog denotes the final solution to the problem. Like, in the presented case, the transmission expansion plan is each frog's solution, mentioning which lines are to be expanded after careful comparisons.

The changes in the memeplexes are incremental and depend on the step size (maximum change allowed in frog replacement). The improvement in the position during evolution is calculated as per ^[14]:

where, F_b = position of the frog with the best fitness in a memeplex, F_w = position of the frog with worst fitness in a memeplex, X_i = current location of the worst frog in each memeplex, X_i+1 = new location for the worst frog with improved fitness, D_i = change in the location of worst solution (frog), rand = random number [0, 1]. This will allow better control to generate the next move using the information available and controlling the specific frog accordingly.

where ${D}_{max}$ is the maximum location leap allowed for a frog in one move (iteration).

Check the new fitness obtained for the worst frog; if f(F_wn) > f(F_wo), then replaces the worst frog with the new frog; if not, the procedure is repeated by replacing F_b with F_g in Eq (1). Again, the new position is checked, and if still no replacement is possible, then generate a new frog randomly.

The local search algorithm uses the following steps:

Step 1: Initialize the memeplex count mc = 0.

Step 2: Increment mc = mc + 1.

Step 3: Initialize the memeplex evolution count me = 0.

Step 4: Increment me = me + 1.

Step 5: For each memeplex, find the positions of the best frog, worst frog, and global best.

Step 6: Use Eqs (1) and (2) to modify the position of the worst frog.

Step 7: Check the new fitness obtained for the worst frog. If

f(F_wn) > f(F_wo), then replace the worst frog with the new frog, and go to step 11.

Step 8: Replace F_b by F_g in Eq (1) and repeat the calculations.

Step 9: Again, check the new fitness obtained for the worst frog. If f(F_wn) > f(F_wo), then replace the worst solution (frog) with the new solution (frog), and go to step 1.

Step 10: If still no replacement is possible, generate a new frog randomly to remove the condition in which memeplex evolution gets trapped.

Here, mc, the memeplex counter, counts the memeplex, i.e., it is included to perform a local search in all the memeplexes. The memeplex evolution count is the number of local search iterations to be completed in each memeplex.

2.2.   Modified shuffled frog leap algorithm (MSFLA)

The major difficulty encountered in the shuffled frog leap algorithm is the convergence rate. The problem is associated with the lack of adaptive acceleration in Eq (1), i.e., the position updating term. The criterion that shows improvement in the new frog position concerning the old position is the objective of the problem ^[16]. Hence, the gaps in the values of the objective function for consecutive iterations can be used for representing the improvement in frog position. Thus, Eq (1) can be modified as follows ^[16]:

where, $f\left({F}_{b}\right)$ is the fitness-value of the best frog, $f\left({F}_{w}\right)$ is the fitness-value of the worst frog, C is the constant [0, C_max], and C_max is the case dependent.

The algorithm for local search in MSFLA is the same as that of SFLA. It replaces Eq (1) with Eq (4) in local search. In Eq (4), C (>1) is the constant value to control the evolution procedure. The value of C defines the acceptance criteria of the search space by allowing the longer leaps (position changes) of frogs (solutions). The appropriate value of C is important for natural evolution and better positioning for random frogs for the next iteration. In contrast, an incorrect value may lead the procedure to an incorrect solution, early convergence and unnecessary algorithm processing. The value of C can be set large for the initial steps of evolution to allow fast positioning and elaboration of the search space. The value can be minimized in later stages to reach the best solution while avoiding local minima ^[25].

In Eq (4) the modification term is called the "adaptive coefficient", which controls the adaptive movement. Depending on the value of the objective function, the adaptive coefficient term defines the movement size, which changes according to the relative position from the optimum point. The inclusion of this term in the position-changing step makes the step size more adaptive to the problem statement than linear. Further, this improves the convergence rate of the algorithm. This modified version of SFLA is termed modified SFLA (MSFLA), which possesses the qualities of fast convergence and adaptive movements ^[26].

2.3.   Proposed method: Enhanced shuffled frog leap algorithm (EMSFLA)

The drawback of MSFLA is the intermediate elimination of potentially effective frogs (solutions) from the search space. It leads to repetitive and useless computations to establish the memeplexes at their mature stage. One solution to avoid this situation is to allow some unique replacements of frogs to avoid the local minima. This means that the best frog in each memeplex is guided towards the global best and explores the hidden area of the search space when moving toward the global best solution. The proposed method in this paper is based on the movement of the best frog towards the global best, which has not yet been deployed in either SFLA or MSFLA. This method extends the hybrid method proposed by Farahani et al. ^[27]. It is done by introducing the equation shown below in the MSFLA equations.

where, ${X}_{j}$ is the current location of the best frog in each memeplex, ${D}_{j}$ is the change in the location of the worst solution (frog), ${X}_{j+1}$ is a new location for the best frog with improved fitness, and $f\left({F}_{g}\right)$ is the fitness-value of the best frog.

This enhances the convergence rate by exploring hidden search space and is called the enhanced shuffled frog leap algorithm (EMSFLA). MSFLA is the fastest of most evolutionary algorithms, as it takes the least time to reach the optimal solution, which helps to find out the global best more quickly. EMSFLA takes approximately the same time to get the convergence criterion with fewer variables than MSFLA. If the number of variables is the same, the number of iterations is also reduced to reach convergence.

The simulation results indicated that the quality of local searches inside the memeplexes plays a vital role in reaching the global optimum. The results also revealed that after reaching the maturity stage, the worst frogs behave in the reverse direction, i.e., away from the local best frog. Therefore, the proper estimation of the maturity stage is required to avoid unnecessary computation. The proposed EMSFLA is programmed and used for all scenarios to prove the abovementioned idea to check the validity. The proposed method possesses all the advantages of MSFLA, better diversification ability and better dealing with local optima. The comparative results are presented in Table 1.

3.   Transmission network expansion problem formulation

The generation of electricity through any mode requires vast infrastructure which cannot be shifted geographically. Also, once the generation station and respective transmission system ^[28,29] are set with heavy investment, it is not advisable to change it, as it will add more cost per unit of electricity to the customer. Therefore, careful strategic planning is required to choose the location for generating electricity and its transmission plan, along with the availability of resources, due to the ever-growing population and changing government schemes. Therefore, transmission expansion planning needs careful, comprehensive and futuristic observation of all factors. It is a critical and complex decision-making procedure to quantify the resources and time required for each expansion plan.

Transmission expansion planning attempts to consider the best possible ways to optimize the electricity grid's time, cost and sustainability, while it serves the purposes of today and can expand further if needed. It is generally solved by applying multi-factor optimization methods while satisfying the load-flow equations. These factors can be geographical, economic, technical or environmental. Therefore, transmission expansion planning is a critical decision-making problem, which requires careful consideration of all constraints before suggesting the proposed expansion plans. Also, in the case of multiple expansion plans, all the viable plans need to be prioritized either based on profitability or sustainability.

The transmission expansion planning of the modern electricity grid requires finding the best and optimal routes for electricity transmission from the generation point to the end while satisfying all the power and load constraints. The major problem in transmission expansion planning is to keep it cost-effective while fulfilling all the technical and economic conditions. The most common solution to this problem is applying a multi-factor optimization algorithm that can produce all the feasible expansion plans and prioritize them as per the prime objective while avoiding all locally optimal points.

The objectives of the TSEPP are to minimize the total investment and expansion costs while considering N-1 contingency. It is formulated as follows:

where: C is the total cost incurred in transmission expansion under a particular scenario, ${L}_{k}$ is the length of the transmission line of the candidate, k is the set of candidates, ${D}_{k}$ is the type of transmission, ${C}_{k}\left({D}_{k}\right)$ is the investment cost for line k of type D_k, ${n}_{i, j},$ is the number of lines to be increased in the corridor ij, such that the total number of lines between corridor ij is subtracted by the existing number of lines in the same corridor.

The power flow constraints are as follows:

where P_L = branch flow vector, b = (b_kk), equal to susceptance of line k, having non-diagonal elements as zero, A = branch bus incidence matrix, X = admittance matrix with R = 0, P = bus active power injection:

where ${P}_{d}$ is the demand at the bus, ${P}_{g}$ is the generation at a bus,

where ${n}_{i, j}^{0}$ is the already existing branches, $S$ is the power flow calculated on the basis of load flow, and ${S}_{max}$ is the maximum possible power flow in the branch.

where ${B}_{i, j}$ is the susceptance of branch ij $\left({B}_{i, j}\right)$, ${\theta }_{i}$ is the voltage phase angle of bus i, ${\theta }_{j}$ is the voltage phase angle of bus j, m is the contingency parameters.

where K is the line between buses i and j.

Eq (10) represents Kirchhoff's law constraint, i.e., power flowing to a node is equal to the power flowing out of a node. Eqs (11) and (12) illustrate the thermal rules that should not exceed their capacity during normal and contingency conditions. Eqs (13) and (14) represents the constraints under contingency, while Eq (15) denotes the output of generators, and Eq (16) denotes the limit on the number of lines.

4.   Solution algorithm

Transmission expansion planning is an optimization problem in which the expansion lines are to be proposed after careful examination of various factors like cost, time, and other socio-economic factors. Frog leap optimization is a potential bio-inspired technique that can provide the optimum solution to transmission expansion planning. The application of SFLA to transmission expansion planning introduces a more detailed load-flow analysis while avoiding the local optima and considering all the possible plans with N-1 contingency.

The solution starts with the generation of the population. First, the base frog is generated, defining the existing system. Then, the candidates are added randomly (in base frog) in each corridor to the maximum number of possible candidates in a corridor. For any practical TSEPP, the planner must first select the candidates. If the number of candidates is significant, as in any actual system, the search space is large, and therefore the number of iterations increases, as does the solution time.

The frogs are initially generated at random, where each represents the network topology (existing as added lines) to resolve this issue in the proposed algorithm. So, the population of frogs is described as, $\mathrm{X}\mathrm{ } = \mathrm{ }[{\mathrm{X}}_{1}, {\mathrm{X}}_{2}, \mathrm{ }\dots, {\mathrm{X}}_{n}]$.

Here, n is the total frogs in a population, and each frog is characterized by m variables (candidate transmission lines in different corridors for the problem considered in this paper), like ${\mathrm{X}}_{i} = \left({\mathrm{X}}_{i1}, {\mathrm{X}}_{i2}, \mathrm{ }\dots, {\mathrm{X}}_{im}\right).$

The next step in population generation is considering only the most effective candidates. This process reduces the search space and ensures that the result reaches the optimal global solution. The candidate evaluation function is defined as (18) to select the most effective lines in the frog:

It is calculated by the difference between the branch's maximum and actual power flow. The candidates with a higher value of CEFi show the overloading limit left, i.e., free capacity. During the population formation process, the condition of islanding should not appear in any frog.

The optimal solution provides the total number and best locations for the candidates. EMSFLA is applied to TSEPP to verify the feasibility of the proposed method, and the simulation results are shown in Table 1. The same problem is solved using MSFLA, and the comparative results are shown in subsequent sections.

5.   Results and discussion

The garver ^[19] 6-bus system (a well-explored standard dataset) is used to validate the proposed TSEPP algorithm, i.e., EMSFLA. The complete data for the buses, existing network, and new candidates can be obtained from ^[30]. This paper considers the standard Graver system under future load and generating conditions. Various scenarios were considered for testing the proposed algorithm. A maximum number of four candidates in any corridor is allowed. The total cost for expanding a system is length-dependent for simplicity, i.e., one monetary unit per kilometer of line length. It helps in comparing results with other research already done with different algorithms. The modified Garver system is shown in Figure 2.

A new bus is added to the existing system, resulting in an islanding condition. Further, the already existing generation was unable to meet the demand; hence, an expansion plan is to be generated for maintaining the system's reliability, stability, and security.

The parameters considered for MSFLA/EMSFLA (Case Ⅰ) are as follows:

a)     Number of frogs = 32.

b)     Number of memeplexes = 4.

c)     Memeplex evolution count = 5.

d)     Generation count = 30.

The parameters considered for MSFLA/EMSFLA (Case Ⅱ) are

a)     Number of frogs = 16.

b)     Number of memeplexes = 4.

c)     Memeplex evolution count = 5.

d)     Generation count = 12.

Different scenarios are considered in the system, and expansion plans are shown in Figures 3–6, respectively. The total cost incurred in expansion is also shown in Table 1. For Scenario 1, two plans are suggested by the proposed algorithm as mentioned in Table 1 by P-1 and P-2.

Different scenarios used here are considering both contingency and rescheduling of generators, only rescheduling, only contingency, and none, respectively. To validate the results, the same variables were used, and MSFLA solved the same population of frogs and generation count (Case Ⅰ). The comparison of the two algorithms (MSFLA and EMSFLA) is shown in Figures 7 and 8 for Scenario 3.

The convergences of both algorithms concerning the number of iterations are shown in Figure 7. EMSFLA outperformed in this analysis, as it reaches the optimal state faster than MSFLA. This was possible in EMSFLA due to the better strategy for choosing better frogs (solutions) towards the global best. This analysis has been done with several variations, and we have found that EMSFLA always obtains the global optimum quicker than MSFLA. When time is used as the comparative measure for both algorithms, MSFLA is quick in intermediate processing (memeplex evolution). This is evident due to the processing of Eqs (6) and (7) in the case of EMSFLA. These equations were introduced for faster convergence as compared to MSFLA. However, the choice of algorithm depends on the problem. In the case of transmission expansion planning, uncertainties are of more concern than the time taken to solve them; therefore, EMSFLA is suitable for such problems in which long-time decisions are required with more accuracy. However, it is not recommended for such situations, which require a certain quality of results within the stipulated time frame.

The movement of best frogs of both the algorithms towards the global best is analyzed in Figure 8 concerning the memeplexes evolution. EMSFLA was also found to be a more feasible approach than MSFLA, as the solutions are generated and explored in the inclined direction of the global best. This was tested with 20 different scenarios, and in each variation, the EMSFLA strategic movement of best frogs towards the global best frog (solution) is more refined as compared to MSFLA.

Analysis using the second case (Case Ⅱ), by changing the MSFLA/EMSFLA to the minimum, i.e., number of frogs from 32 to 16 and generation count from 30 to 12, is important to see the efficiency of the proposed algorithm to compare it with MSFLA. The EMSFLA has also shown the predicted performance growth, as shown in Figure 9.

Also, in the case of Figure 9, although the EMSFLA takes more time for intermediate processing, it converges in the minimum number of iterations. Similarly, other scenarios were compared, and EMSFLA outperformed in all the cases regarding the convergence in fewer iterations. However, the time taken by both algorithms goes hand-in-hand.

The presented meta-heuristic approach is also applied to the IEEE 24-bus reliability test system. The reliability test system data is used for the analysis, and the results are shown in Table 2. This simulation is run under normal conditions and N-1 contingency conditions.

The convergence characteristics of EMSFLA are verified to be better than MSFLA. Further, as the system is more extensive, the time taken by EMSFLA to reach the global best is better than MSFLA. This fact indicates that the proposed algorithm is far better than the existing ones in reaching the global optimum. Figures 10 and 11 show a comparison concerning time and convergence. Figure 12 shows the convergence of the best frog under the normal and N-1 conditions, respectively. In both cases, the movement is more inclined towards the global best solution.

6.   Conclusions

This paper presents a new approach, EMSFLA (enhanced modified shuffled frog leap algorithm), for more refinement of the movement of the frogs (solutions) towards the food (global best solution). The presented approach is applied to optimize the transmission expansion planning problem. The advantage of the proposed method is its ability to avoid local minima and to converge in a smaller number of iterations. EMSFLA took special considerations for population formation and evolution to incline the intermediate results towards the global best solution. The local search mechanism is redefined to quickly take the memeplexes into their mature stage. The total processing time in using EMSFLA is not improved compared to MSFLA (the least time-taking algorithm so far). However, EMSFLA somehow managed to get the results in almost the same time as MSFLA with some refinement in variable values. This also makes EMSFLA the least time-taking algorithm compared to other optimization methods. The results of EMSFLA facilitated the identification of the optimal number of transmission lines to be added to satisfy future load and generating conditions. The proposed algorithm may be refined and fine-tuned for any optimization problem due to the generalized modular programming paradigm. Future research will be conducted on designing a hybrid system with ANNs ^[31,32] and the proposed method.

Conflict of interest

The authors declare no conflict of interest.

Acknowledgements

The authors would like to thank the reviewers for the correct and concise recommendations that helped present the materials better. We would also like to thank the Armed Forces of Ukraine for providing security to perform this work. This work has become possible only because of the resilience and courage of the Ukrainian Army.