Multi-objective learning backtracking search algorithm for economic emission dispatch problem

Abstract

The backtracking search algorithm (BSA) as a novel intelligent optimizer belongs to population-based evolutionary algorithms. In this paper, a multi-objective learning backtracking search algorithm (MOLBSA) is proposed to solve the environmental/economic dispatch (EED) problem. In this algorithm, we design two novel learning strategies: a leader-choosing strategy, which takes a sparse solution from an external archive as leader; a leader-guiding strategy, which updates individuals with the guidance of leader. These two learning strategies have outstanding performance in improving the uniformity and diversity of obtained Pareto front. The extreme solutions, compromise solution and three metrics obtained by MOLBSA are further compared with those of well-known multi-objective optimization algorithms in IEEE 30-bus 6-unit test system and 10-unit test system. Simulation results demonstrate the capability of MOLBSA in generating well-distributed and high-quality approximation of true Pareto front for the EED problem.

1 Introduction

The backtracking search algorithm (BSA) (Civicioglu 2013), a population-based evolutionary algorithm (EA), was first proposed by Civicioglu in 2013 as a novel approach to solve nonlinear, non-differentiable and multi-modal numerical optimization problems. Compared with some similar evolutionary algorithms, BSA has only one single control parameter (mixrate). More particularly, BSA possesses a memory called old population to provide search direction for the mutation, which stores a population randomly selected from the current generation or a previous generation. Over the past few years, there have been some successful applications of BSA in various fields (Wang et al. 2019; Pare et al. 2018; Mohd Zain et al. 2018; Hannan et al. 2018; Abdolrasol et al. 2018). It is widely used in engineering fields, such as power system (Modiri-Delshad and Rahim 2014; Ali 2015; Modiri-Delshad et al. 2016; Pal et al. 2016; Modiri-Delshad et al. 2016; Dubey et al. 2016; Bhattacharjee et al. 2015; Modiri-Delshad and Rahim 2016; Kılıç 2015; Ayan and Kılıç 2016; Chaib et al. 2016; Ishak et al. 2014; El-Fergany 2015a, b; Khamis et al. 2015a, b; Gupta et al. 2015; El-Fergany 2016; Khamis and Tai 2017; Khamis et al. 2015; Shahriar et al. 2015; Shafiullah et al. 2015; Niamul Islam et al. 2016; Islam et al. 2017; Shafiullah et al. 2017; De Souza et al. 2016; Najibi et al. 2016), control engineering (Ali et al. 2015, 2016), digital image processing (Eskandari and Toygar 2015; Atasever et al. 2014), antenna array (Guney et al. 2014; Guney and Durmus 2015, 2016) and machine layout and measurement (Vitayasak et al. 2016).

As a young intelligence optimization algorithm, BSA has been widely researched and applied in power system since it was proposed in 2013. At present, we can find the references on the application of BSA in power system no less than 30. The number of these references is the largest number of BSA publications in the engineering field. These literatures can be classified as Table 1. The following three conclusions can be given from the table.

• Only one literature (Ali 2015) proposes the improved BSA to solve power system problem and the remaining ones adopt the basic BSA.

• Only one literature (Modiri-Delshad and Rahim 2016) presents the multi-objective BSA with non-dominated approach to handle multi-objective problems and the remaining ones use the basic BSA with weighted sum method.

• The ED problem and the EED problem developed on the ED problem are the research hotspot of BSA application in power system.

Many researchers have been interested in solving the bi-objective EED problem. Initially, some researchers adopt conventional optimization methods (Talaq et al. 1994; Farag et al. 1995). However, these conventional optimization methods can not achieve ideal results in the complex bi-objective EED problem. Therefore, with the rise of meta-heuristics, using meta-heuristics to solve the bi-objective EED problem has become a research hotspot (Zhang et al. 2012; Jubril et al. 2014; Bhattacharjee et al. 2014). The reported methods in the literatures of BSA application to handle the EED problem can be separated into two groups. The first method is weighting aggregation. Bhattacharjee et al. (2015) used the linear combination of two different objectives as a weighted sum to transform the bi-objective EED problem into a single-objective problem. The second method is multi-objective BSA. Modiri-Delshad and Rahim (2016) used multi-objective BSA to handle the both objectives (fuel cost and $NO_x$ emission) in the EED problem simultaneously, and an elitist external archive is adopted to store non-dominated solutions. The first method is easy to be implemented, while its common defect is that it needs to run many times to obtain the trade-off non-dominated solution set by varying different weights. The second method can not find the solutions with a uniform distribution.

Table 1 Summary of applications of BSA to power system

There are many other natural heuristics applied to EED problem except BSA, and nature-inspired algorithm is the most successful and suitable method. Qu et al. (2017) have reviewed the application of multi-objective evolutionary algorithms (MOEAs) in solving bi-objective EED problem, mainly including GA-based approaches, PSO-based approaches, DE-based approaches and some hybrid algorithms. Although the classical EED problem has a lot of publications, the research of MOEAs on EED problem is still in its infancy. Moreover, there are few studies on the improvement of multi-objective BSA. The existing research does not provide a unified comprehensive evaluation of the accuracy, stability and time efficiency of algorithm.

In this paper, an enhanced multi-objective learning backtracking search algorithm (MOLBSA) is proposed to solve the bi-objective EED problem. This algorithm use the information of the solution selected in elitist external archive to enhance the diversity and uniformity of obtained Pareto front. The primary contributions of MOLBSA are that it uses two different strategies:

• Leader-choosing strategy The solutions with the maximum distance between non-dominated solutions are used in the course of searching to enhance the uniformity performance of approximate solutions.

• Leader-guiding strategy Some individuals are replaced by the leaders’ neighbors, while others are updated by learning from leader.

The remainder of this paper is organized as follows: Section 2 formulates the mathematical model of EED problem. Section 3 briefly reviews the basic BSA. Section 4 presents MOLBSA. Section 5 describes the search behavior of two strategies. Section 6 describes how to implement MOLBSA in the EED problem. Section 7 provides the comparison of several existing optimization methods. Finally, Section 8 gives the concluding remarks.

2 Mathematical model of the EED problem

As a nonlinear bi-objective optimization problem, EED problem is the simultaneous minimization of the fuel cost and emission while satisfying a real power balance equality constraint and several boundary constraints. The objective functions and constraints are described as follows. The parameter setting and function meaning of the EED problem are introduced in more detail in Saadat (1979).

2.1 Objective functions

2.1.1 Fuel cost minimization

Considering the valve point loading effects, the total fuel cost $f_c(P_u)$($/h) of D generators can be represented by adding a sine component to a quadratic function. The expression of the $f_c(P_u)$ can be as Eq. (1):

$$\begin{aligned} f_c(P_u)= & {} \sum \limits _{j = 1}^D {({a_j}} + {b_j}{P_{uj}} + {c_j}P_{uj}^2)\nonumber \\&+|d_j \times sin(e_i(P_{uj}^{\mathrm{\min }}-P_{uj}))| \end{aligned}$$

(1)

where $j{=}1{,}2{,}{\ldots }{,}D$. The vector $P_u {=} ({P_{u1}}{,}{P_{u2}}{,} {\ldots } {,}{P_{uD}})$ is the output power of generators. $P_{uj}$ is the output power of the jth generator. $a_j$, $b_j$, $c_j$, $d_j$ and $e_j$ are the cost function coefficients for the jth generator. $P_{uj}^{\min }$ is the minimum output power of the jth generator.

2.1.2 Pollution emission minimization

The pollution emission objective function can be expressed as the sum of all kinds of the pollutant emission. But in this study, we only consider the emission of nitrogen oxides $NO_x$ caused by the generators. The total pollution emission $f_c(P_u)$(ton/h) of the $NO_x$ is expressed as the sum of some quadratic and exponential functions, as shown in Eq. (2).

$$\begin{aligned} f_e(P_u) = \sum \limits _{j = 1}^D ((\alpha _j + {\beta _j}{P_{uj}} + {\gamma _j}P_{uj}^2)10^{- 2} + {\zeta _j}e^{\lambda _j}P_{uj}) \end{aligned}$$

(2)

where $\alpha _j$, $\beta _j$, $\gamma _j$, $\zeta _j$ and $\lambda _j$ are the $NO_x$ emission function coefficients for the jth generator.

2.2 Constraints

2.2.1 Generation capacity constraints

To ensure the stable operation of the power system, the actual output power of each generator should be limited by the upper and lower limits. The formula is as follows.

$$\begin{aligned} P_{uj}^{\min } \le {P_{uj}} \le P_{uj}^{\max },\ j = 1,2, \cdots ,D. \end{aligned}$$

(3)

where $P_{uj}^{\min }$ and $P_{uj}^{\max }$ are the minimum and maximum limits of the jth generator, respectively.

2.2.2 Real Power balance constraint

The total real power generation must be the sum of the transmission power loss PL and the total power demand PD, namely,

$$\begin{aligned} \sum \limits _{j = 1}^D {{P_{uj}}} = {PL} + {PD} \end{aligned}$$

(4)

Where PL is calculated by Kron’s loss formula (Saadat 1979). The calculation formula of PL is as follows.

$$\begin{aligned} {PL} = \sum \limits _{j = 1}^D {\sum \limits _{k = 1}^D {{P_{uj}}} {B_{jk}}} {P_{uj}} + \sum \limits _{j = 1}^D {{B_{0j}}{P_{uj}}} + {B_{00}} \end{aligned}$$

(5)

where B, $B_{0}$ and $B_{00}$ are the transmission network power loss coefficients.

2.3 Problem statement

The EED problem is composed of some constraint functions and two nonlinear objective functions which need to be minimized simultaneously. It is mathematically formulated as

$$\begin{aligned} \begin{aligned} \min&\quad (f_c({P_u}),f_e({P_u}))\\ st.&\quad \left\{ \begin{array}{l} h(P_u)=0\\ g(P_u) \le 0 \end{array} \right. \end{aligned} \end{aligned}$$

(6)

3 Backtracking search algorithm

BSA is a novel population-based EA and is designed for solving numerical optimization problems. It mainly consists of five parts: initialization, selection-I, mutation, crossover and selection-II. Its unique feature is that it uses two populations i.e., current and historical populations. As a memory of BSA, the historical population is randomly selected from the previous generation to calculate the search-direction matrix. BSA uses two random crossover operations to ensure that each generation will produce new trial individuals and retain certain information from the previous generation. The five parts of BSA are described below.

3.1 Initialization

The beginning of BSA is to generate new individuals randomly within a specified range to form a population P and a historical population oldP. The mode of population generation is shown in Eq. (7).

$$\begin{aligned} \left\{ \begin{array}{l} P_{i,j} \sim U(P^{\mathrm{min}}_j,P^{\mathrm{max}}_j)\\ oldP_{i,j} \sim U(P^{\mathrm{min}}_j,P^{\mathrm{max}}_j) \\ \end{array} \right. \end{aligned}$$

(7)

where $i = 1, 2, \ldots , N$ and $j = 1, 2, \ldots , D$ , N and D are the population size and the dimension of the population, respectively. $P_{i,j}$ and $oldP_{i,j}$ are the jth element of the ith individual in the population P and the historical population oldP, respectively. U is a random uniform distribution. $P^{\mathrm{min}}_j$ and $P^{\mathrm{max}}_j$ are the minimum and maximum limits of the jth dimension of individual, respectively.

3.2 Selection-I

This stage is the beginning of each iteration, which is to update and disorder the historical population oldP according to Eq. (8):

$$\begin{aligned} oldP = \left\{ \begin{array}{lcl} oldP &{} &{} \mathrm{if}\ r1 < 0.5\\ P &{} &{} \mathrm{otherwise} \\ \end{array} \right. \end{aligned}$$

(8)

where r1 is a random number from 0 to 1. After assigning the oldP, a key operation is to shuffle the oldP randomly.

3.3 Mutation

Unlike other EA, the BSA uses the difference of population P and historical population oldP for its mutation operators. The generation of the initial trial population Mut is shown in Eq. (9).

$$\begin{aligned} Mut = P + F \cdot (oldP-P), \quad F=3 \cdot randn \end{aligned}$$

(9)

where F denotes the control factor to control the amplitude of the search direction, randn is a random number which obeys the standard normal distribution. As shown in Eq. (9), BSA generates the trial population Mut by using the experience of previous generations.

3.4 Crossover

In this process, one or more population dimensions need to be selected. Then, the same dimension elements of individual in P and individual in Mut are exchanged to generate new individual. A matrix Map with the size $N*D$ composed of zero and one is adopted to record this operation. The Map is represented in Eq. (10).

$$\begin{aligned} \left\{ \begin{array}{ll} Map_{i,{u(1:\left\lceil {D\cdot rand(0,1)\cdot mixrate} \right\rceil )}}=0 &{} \quad \mathrm{if}\ r2 < 0.5 \\ Map_{i,randi(D)}=0 &{} \quad \mathrm{otherwise} \\ \end{array} \right. \end{aligned}$$

(10)

where $u=permuting({[1,2,\cdots , D]})$, $permuting(\cdot )$ is a random shuffling function, $mixrate=1$, randi(D) generates a uniformly distributed random integer in [1, D], $\lceil \cdot \rceil$ rounds the elements to the nearest integers toward infinity, r2 is a random number from 0 to 1.

The generation of the final trial population T is calculated by in Eq. (11):

$$\begin{aligned} T_{i,j} = \left\{ \begin{array}{ll} P_{i,j} &{} \quad \mathrm{if} Map_{i,j}=1\\ V_{i,j} &{} \quad \mathrm{otherwise} \\ \end{array} \right. \end{aligned}$$

(11)

If some dimensions of individuals in T exceed the feasible region, they are randomly generated within the allowed range.

Eq. (9) in the mutation and Eq. (11) in the crossover are built together in the following formula.

$$\begin{aligned} T = P + Map \cdot 3 \cdot randn \cdot (oldP-P) \end{aligned}$$

(12)

3.5 Selection-II

In BSA, this process is to select the individuals with high fitness from the P and T to enter the next generation. The selection mechanism is greedy selection. When the fitness of $T_i$ is better than that of $P_i$, $T_i$ is used to replace $P_i$. Otherwise $P_i$ is retained. The selection strategy formula is shown in Eq. (13):

$$\begin{aligned} P_{i}^{new} = \left\{ \begin{array}{ll} T_{i} &{} \quad \mathrm{if} fitness(T_i)<fitness(P_i)\\ P_{i} &{} \quad \mathrm{otherwise} \\ \end{array} \right. \end{aligned}$$

(13)

The best individual of the population is also updated in this process.

4 Multi-objective learning backtracking search algorithm(MOLBSA)

BSA has the characteristics of simple principle and good optimization ability, and has been successfully applied to various single-objective optimization problems. Moreover, BSA’s ability to learn from population is weak during the evolution process, which leads to slow convergence speed. One reason is that BSA uses historical information to update all individuals, but doesn’t make good use of the best information in current population. Hence, an extended BSA, multi-objective learning backtracking search algorithm (MOLBSA), is designed to solve multi-objective optimization problem. It selects leaders to guide individual updating according to the maximum distance of Pareto optimal solution. MOLBSA’s operation strategy will be given in detail below.

4.1 Leader-choosing strategy

A multi-objective optimization problem has two or more conflicting objective functions. However, it is difficult for the basic BSA to solve conflicting multi-objective problem. Because the convergence speed of basic BSA is slow, a leader-choosing strategy is designed, which selects a leader Xg from the external archive to guide individual mutation. In this strategy, a new concept of maximum distance is designed. The maximum distance is used to measure the sparsity of each solution in the external archive, so that the sparse solution can be chosen as a leader according to the sparsity. The $md_t$ of tth non-dominated solution ($Ar_t$) in Ar is calculated as follows.

$$\begin{aligned} md_t = \max ({ud_t},{ld_t}) \quad t=1,\ldots ,Nt \end{aligned}$$

(14)

where Nt is non-dominated solutions number in Ar. The formulas for calculating the distance of $Ar_t$ from the upper point $Ar_{t-1}$ to the lower point $Ar_{t+1}$ are shown in Eq. (15) and (16), respectively.

$$\begin{aligned} ud_t= & {} \sum \limits _{m = 1}^M {\left| \frac{{{f_m}(Ar_t) - {f_m}(Ar_{t-1})}}{{f_m^{\max } - f_m^{\min }}}\right| } \end{aligned}$$

(15)

$$\begin{aligned} ld_t= & {} \sum \limits _{m = 1}^M {\left| \frac{{{f_m}(Ar_t) - {f_m}(Ar_{t+1})}}{{f_m^{\max } - f_m^{\min }}}\right| } \end{aligned}$$

(16)

where M indicates the objective functions number. ${f_m}(Ar_t)$ is the mth objective function value of the tth non-dominated solution $Ar_t$. $f_m^{\min }$ and $f_m^{\max }$ are the minimum and maximum values of the tth objective function, respectively.

Fig. 1

Maximum distance of MOLBSA

In Fig. 1, the solid points represent the non-dominated solutions in Ar. $md_t$ is the relative maximum of the length and width sums of its two adjacent rectangles. The two extreme points of Ar have only one adjacent point, so the md of two extreme points is the distance between the point and the only adjacent point. Fig. 1 shows that the $md_1$ of the extremum point $Ar_1$ is the relative value of side-length sum of the matrix composed of $Ar_1$ and $Ar_2$.

MOLBSA selects leaders from Ar by using a roulette wheel selection. In Algorithm 1, the leader-choosing strategy is described in detail in pseudocode.

In the line 4 of Algorithm 1, the calculation formula of $P_t$ is given. $P_t$ is the selection probability of the tth solution in Ar. In Roulette_wheel_selection, the input and output are an array of probabilities ${p_1,p_2,\cdots ,p_{Nt}}$ and an index $index_i$, respectively.

4.2 Leader-guiding strategy

As is well known, some evolutionary algorithms have shown that learning from the best individual is an effective method for improving the convergence speed of EA. However, only the historical information is used to generate a new individual in the basic BSA. To enhance the learning ability of MOLBSA, leaders’ guidance is designed in the process of updating population. The new learning method of MOLBSA, leader-guiding strategy, contains two parts i.e., a wise random walk strategy based on non-dominated solution and a guidance strategy using the leaders and the oldP to generate search direction. First, each individual is replaced by its corresponding leader’s neighbor. Second, each individual learns knowledge from the historical population (oldP) and the corresponding leader (Xg). The two parts have the same probability to be selected in the following updating equation. The formula for the generation of trial individual $T_i$ is as Eq. 17.

$$\begin{aligned} T_i = \left\{ \begin{array}{ll} {Xg_i} + rand \cdot (Ar_{index_i + l_{index}} - {Xg_i}), &{} \quad if \ r3 < 0.5 |r3 \sim U(0,1)\\ P_i + Map_i \cdot (rand \cdot (oldP_i-P_i)&{}\\ \qquad + rand \cdot (Xg_i-P_i)), &{} \quad otherwise\\ \end{array} \right. \nonumber \\ \end{aligned}$$

(17)

where $i=1,2,\cdots ,N$. $l_{index}$ is the sparse direction of indexth solution of the archive.

Eq. 18 gives the design formula of the sparse distance $l_t$ for tth solution in Ar. $l_t$ is recorded by comparing $ud_t$ and $ld_t$. If $ld_t$ is greater than $ud_t$, then $l_t=1$. Otherwise, $l_t=-1$.

$$\begin{aligned} l_t=\left\{ \begin{array}{ll} 1, &{} \quad ld_t > ud_t\\ -1, &{}\quad ld_t \le ud_t\\ \end{array} \right. , \quad t=1,2,\cdots ,Nt \end{aligned}$$

(18)

Fig. 2

Sparse direction of MOLBSA

Figure 2 shows the sparse directions of $Ar_1$, $Ar_A$ and $Ar_B$. In this figure, $ld_A$ is greater than $ud_A$ for $Ar_{A}$, so $l_A=1$. For the $Ar_B$, $ud_B$ is greater than $ld_B$, hence $l_B=-1$. For the first extreme point $Ar_1$, its neighbor has only $Ar_2$, so $l_1=1$.

On the one hand, the strategy makes the population P move around Xg, thus generates a new population T, which can make the Pareto front more uniform. In Fig. 2, the red arrow indicates the direction of the non-dominated solution. $Ar_A$ will move to its neighbor $Ar_{A+1}$ because there is a big gap between them.

On the other, the strategy brings the population P nearer to the population oldP and the current archive Ar.

4.3 Update and maintenance of archive

Different from the single objective algorithms, the multi-objective algorithms need to output a non-dominated solution set at the end after cycle termination. It is essential to maintain the quantity and quality of non-dominated solutions in search process. Since Goldberg (1989) put forward a selection strategy with non-dominated sorting in niched pareto genetic algorithm (NSGA) in 1989. Srinivas and Deb (1994) described and used the non-dominated sorting. In 1999, Zitzler and Thiele (1999) introduced formally strength pareto evolutionary algorithm (SPEA) with elitist reservation mechanism. Deb et al. (2002) designed a fast non-dominated sorting, which is more efficient non-dominated sorting technique.

This paper uses an external archive with a specific volume to save non-dominated solutions in each iteration. Initially, the non-dominated solutions are stored into this empty external archive. There are three rules when a trial vector X compares with the current external archive Ar as follows.

• (i) if $\exists a, a \in Ar, a \prec X$, then X is rejected into Ar;

• (ii) if $\exists a, a \in Ar, X \prec a$, then $Ar=Ar/a \wedge Ar=Ar \cup X$;

• (iii) if $\forall a, a \in Ar, X \nprec a \wedge a \nprec X$, then $Ar=Ar \cup X$

When the non-dominated solutions number in the external archive reaches its own capacity, the crowding distance designed by Deb et al. (2002) in NSGA-II is used to remove redundant members with small crowding distance, so as to ensure that the solutions number in the external archive will not exceed the capacity. In NSGA-II, the crowding distance of the external archive is calculated only once in each iteration, which may lead to the sparsity of the congested area on the Pareto front after one iteration. Therefore, a cyclic crowding sorting technique (Luo et al. 2010) is generated to enhance the uniformity of Pareto front. The cyclic crowded sorting algorithm is illustrated as the following Algorithm 2.

In Algorithm 2, we first check to see if the number of solutions in Ar has exceeded the maximum capacity (Na) of Ar. If it exceeds, the crowding distance of each solution is calculated. The formula of crowding distance is presented in the line 9 of Algorithm 2, and the crowding degree of extremum solutions are set as infinite. It is necessary to find out index of the solution with the minimum crowding distance and eliminate the solution in Ar. Again, we check whether the number of residual solutions in Ar exceeds the maximum capacity of Na. If it exceeds, the algorithm enters the loop again, otherwise, the algorithm stops the loop. Finally, we get an external archive Ar whose number of solutions is equal to the maximum capacity Na.

4.4 Algorithm procedures

Algorithm 3 shows the pseudocode for MOLBSA. In Algorithm 3, the two novel learning strategies are shown on lines 14, 16 and 23, respectively, and are shown in bold and underline. The update and maintenance of Ar in lines 20-32. Figure 3 is a flowchart of the algorithm.

Fig. 3

The flowchart of MOLBSA

5 Analysis of the search behavior of MOLBSA

As mentioned earlier, the proposed algorithm MOLBSA has two core strategies. The first strategy (strategy1) is the leader-choosing strategy. It calculates the sparsity of non-dominated solutions by Eq. (14), and chooses the sparse non-dominated solution as the leader to serve for the second strategy. The second strategy (strategy2), leader-guiding strategy, operates through Eq. (17) which randomly selects one of two mutation operators to mutate individuals. The first operator is to make the Pareto front more uniform. The second operator is to preserve the global search ability of the population.

In order to illustrate the search behavior of MOLBSA and the effectiveness of its two strategies, three algorithms are designed and compared as follows.

• (i) multi-objective BSA (origin MOBSA for short).

• (ii) $\mathbf{Origin MOBSA } + \mathbf{strategy2 }$: being build by adding the leader-guiding strategy to origin MOBSA

• (iii) $\mathbf{Origin MOBSA } + \mathbf{strategy1 } + \mathbf{strategy2 }$(MOLBSA): being formulated by adding the leader-choosing strategy and the leader-guiding strategy to origin MOBSA.

In this little test, three algorithms are applied to a simple bi-objective problem, which is shown in the following Eq. (19). The parameters including $N=50$,$D=2$,$Na=30$,$T^{max}=40$ are provided.

$$\begin{aligned} \left\{ \begin{array}{l} \min {f_1} = 4x_1^2 + 4x_2^2\\ \min {f_2} = {({x_1} - 5)^2} + 4{({x_2} - 5)^2}\\ st.\ 0< {x_1}< 5,\ 0< {x_2} < 3 \end{array} \right. \end{aligned}$$

(19)

Fig. 4

Comparisons of adding strategies in MOBSA

Figure 4 shows the Pareto front obtained by the three algorithms. The following two results can be obtained from the figure:

• (i) From Fig. 4, the Pareto front obtained by the origin MOBSA + strategy2 has better uniformity than origin MOBSA. This illustrates that the strategy2 (leader-guiding strategy) enhances the uniformity of Pareto front. The Pareto front obtained by the origin MOBSA + strategy1 + strategy2 has slightly better uniformity than that of the origin MOBSA + strategy2. This is because the strategy1 (the leader-choosing strategy) plays a significant role in the origin MOBSA + strategy1 + strategy2. The strategy1 selects the sparse solution of external archive as the leader. Under the action of the strategy2, more solutions are generated near the sparse solution, thus the distribution of the obtained Pareto front is more uniform.

• (ii) In the figure, the extreme points of the origin MOBSA + strategy2 (represented by two green diamonds) has slightly better coverage than those of the origin MOBSA represented by two blue squares. The extreme points obtained by the origin MOBSA + strategy1 + strategy2 (represented by two red circles) has slightly better coverage than those of the origin MOBSA + strategy2. Therefore, it can be concluded that the leader-choosing strategy and leader-guiding strategy can improve the diversity of Pareto front.

6 Implementation of MOLBSA

In subsection 2.2, we have introduced the constraint of EED problem, which contains one power balance equality constraint. Therefore, a constraint handling mechanism is needed to move infeasible solutions to feasible regions. In addition, a fuzzy theory to select a best compromise solution has been frequently adopted to simulate the preference of decision maker. In this final subsection, the parameter setting of MOLBSA is introduced.

6.1 Constraint handling

In this section, a constraint handling strategy is introduced to solve the power balance equality constraint in the EED problem. To guarantee all solutions can satisfy the equality constraint, scholars adopt a rejecting strategy to handle the power balance equality constraint in the EED problem (Wang and Singh 2007, 2008; Cai et al. 2009). But this method is time-consuming to deal with equality constraint.

In MOLBSA, a straightforward constraint handling approach is provided to deal with the power balance equality constraint. Algorithm 4 gives the detailed operation of Constrint_Handling. In Algorithm 4, we set $\sigma =1e-12$.

6.2 Select of compromise solution

After getting Pareto optimal solutions, one solution called compromise solution is selected to satisfy the different goals. The difficulties of trade-off decision is summarized that the different objectives function values are measured in different physical units. Moreover, there are no specific compromise rules between different objectives. In the published literatures (Modiri-Delshad and Rahim 2016; Sivasubramani and Swarup 2011; Wu et al. 2010), a fuzzy-based approach (Sakawa et al. 1987) is usually adopted to simulate preference of a decision maker.

This work calculates the satisfactory degrees of Pareto optimal solutions by using a simple linear membership function. The objective functions of different physical units are scaled by 0-1 metric. The satisfactory degree $\mu _{t,j}$ of $Ar_t$ for $f_j$ is herein defined as

$$\begin{aligned} \mu _{t,m}=\left\{ \begin{array}{ll} 1, &{} \quad {{f_m}(Ar_t) \le f_m^{\min }}\\ \frac{f_m^{\max } - {f_m}({Ar_t})}{f_m^{\max } - f_m^{\min }}, &{} \quad {f_m^{\min } \le {f_m}({Ar_t}) \le f_m^{\max }}\\ 0, &{} \quad {{f_m}(Ar_t) \ge f_m^{\max }}\\ \end{array} \right. \end{aligned}$$

(20)

where $t=1,2,\cdots ,Nt$, $m=1,2,\cdots ,M$, Nt and M are the number of solutions in Ar and the number of objective functions, respectively. The M of the bi-objective EED problem is 2. ${f_m}(Ar_t)$ is the mth objective function of the tth solution in Ar. $\mu _{t,m}=1$ indicates complete satisfaction, and $\mu _{t,m}=0$ expresses dissatisfaction. The normalized membership function is defined as follows. The fuzzy membership function is described in Fig.5.

$$\begin{aligned} \mu _k = \frac{\sum \limits _{m = 1}^M {{\mu _{k,m}}} }{\sum \limits _{t = 1}^{Nt} {\sum \limits _{m = 1}^M {{\mu _{t,m}}} } } \end{aligned}$$

(21)

Fig. 5

The fuzzy-based membership function

The non-dominated solution with maximum $\mu _k$ is considered as a compromise solution which represents the decision makers’ decision.

6.3 Parameter setting

The proposed MOLBSA is simulated on IEEE 30-bus 6-unit system with the total power demand 2.834 p.u and 10-unit system with the total power demand 2000 MW. Tables 2 and 3 provide the data of fuel cost and $NO_x$ emission coefficients referenced in Basu (2011). The transmission power loss formula coefficients of 6-unit system and 10-unit system are exhibited in Tables 4 and 5.

Table 2 Fuel cost and $NO_x$ emission coefficients in 6-unit system

Table 3 Fuel cost and $NO_x$ emission coefficients in 10-unit system

Table 4 Transmission power loss formula coefficients in 6-unit system

Table 5 Transmission power loss formula coefficients in 10-unit system

The parameters for all simulation runs are set as follows. Both the maximum capacity of Ar (Na) and the population size (N) and are set to 50. The number of fitness function evaluations is restricted to 10000 for all experiments as terminating condition. All algorithms are run independently for 30 times. To demonstrate the optimization effectiveness of MOLBSA, the simulations are carried out for two different cases as follows.

• Case1: not consider the transmission power losses in power balance constraint.

• Case2: consider the transmission power losses in power balance constraint.

7 Computational results

Experiments in this paper are designed to estimate the quality of the Pareto optimal solution obtained by comparing the simulation results of extreme solutions, compromise solutions, spacing metric(SP), hypervolume (HV) and c-metric (C) in all cases for MOLBSA and other algorithms.

7.1 Comparisons of compromise solutions and extreme solutions in Pareto front

In this part, an experiment is designed to study the performance of MOLBSA by comparisons of the extreme points and compromise solutions obtained by different algorithms. Firstly, the fuel cost and $NO_x$ emissions are independently optimized as a single-objective function. Table 6 shows the results of best solution for 6-unit system in two cases. From this table, when the fuel cost is minimized as a unique objective function, the optimal values obtained by BSA are 600.1114($/h) and 605.9983($/h) in two cases. When the $NO_x$ emission is only minimized, BSA reaches the optimal values of 0.194203(ton/h) and 0.194179(ton/h) in Case1 and Case2, respectively.

Table 6 Best solutions for $f_c$ and $f_e$ minimized individually in 6-unit system for two cases

Next, we discuss the multi-objective extreme solutions and compromise solutions obtained by MOLBSA for 6-unit system—Case1. Tables 7 and 8 compare the extreme points of Pareto fronts obtained by MOLBSA , MOBSA, multi-objective stochastic search technique (MOSST) (Das and Patvardhan 1998), non-dominated sorting genetic algorithm (NSGA) (Abido 2003a), niched pareto genetic algorithm (NPGA) (Abido 2003b), strength pareto evolutionary algorithm (SPEA) (Abido 2003c), non-dominated sorting genetic algorithm-II (NSGA-II) (Ah King et al. 2005),and fuzzy clustering-based PSO (FCPSO) (Agrawal et al. 2008). The best results are bold in all tables.

As is revealed in Table 7, the best fuel cost of MOLBSA equals 600.120251($/h) when using the minimum 10,000 times function evaluation times (FEs), which is superior to the results of other seven algorithms compared. The error of equality constraint obtained by MOLBSA is 0. This value is better than those of MOSST, NSGA and SPEA, which is the same as those of MOBSA, NPGA, NSGA-II and FCPSO. In Table 8, the best solution for the emission obtained by MOLBSA equals 0.194200(ton/h) when only using the minimum 10,000 times FEs. Although this value is not the smallest of the eight algorithms listed in Table 8, it is also idea with ranking second. The minimum emission value obtained by MOSST is 0.19418(ton/h), but MOSST’s the error of equality constraint is not ideal equal to 0.027000. However, the error of equality constraint by using MOLBSA is 0. In Tables 7and 8, MOLBSA only use 10,000 times FEs. This FEs value is the same as those of MOBSA and NSGA-II, and is smaller than those of other comparative algorithms. From the discussion, it can be concluded that MOLBSA is more effective than almost all other seven algorithms.

Table 7 Best solutions for $f_c$ in 6-unit system—Case1

Table 8 Best solutions for $f_e$ in 6-unit system—Case1

Table 9 shows the compromise solutions of six algorithms. Since these compromise solutions have no dominance relationship, it is difficult to compare them directly. The method of decision-maker’s average satisfactory degree (ASD) mentioned in Zhang et al. (2012) is adopted to estimate the quality of compromise solutions. The ASD of compromise solution is calculated by

$$\begin{aligned} {\bar{\mu }}^{com}=\frac{1}{M}\sum \limits _{m = 1}^{M}\mu ^{com}_m \end{aligned}$$

(22)

In Table 9, the ${\bar{\mu }}^{com}$ value obtained by MOLBSA is 0.757962, which is larger than those of the other five algorithms. This proves that the satisfaction of compromise solution obtained by MOLBSA is higher than those of other five algorithms to some extent.

Table 9 Best compromise solutions in 6-unit system—Case1

Fig.6 depicts the approximations of the true Pareto front obtained by MOLBSA and MOBSA. From Fig.6, the distribution of Pareto front obtained by MOLBSA is more uniform than that of MOBSA in 6-unit system—Case1.

Tables 10 and 11 show the numerical results of two extreme points in Pareto front (minimum cost and minimum emission) for seven algorithms as shown in 6-unit system—Case2. The numerical results of MOLBSA are compared with those of well-known MOBSA, NSGA (Abido 2003a), NPGA (Abido 2003b), SPEA (Abido 2003c), NSGA-II (Ah King et al. 2005) and FCPSO (Agrawal et al. 2008).

From Table 10, MOLBSA gains the minimum fuel cost equal to 606.00818($/h) with fewer FEs. Not only the minimum fuel cost of MOLBSA is lower than those of the other six algorithms, but also its FEs is the smallest. As is demonstrated in Table 11, the $NO_x$ emissions of MOLBSA is 0.194196(tons/h). Its value is only 0.0006(tons/h) larger than that of NSGA-II, but smaller than those of the other five methods. Therefore, the above results show that MOLBSA can obtain more extensive Pareto front compared with the other six algorithms.

Fig. 6

Pareto fronts obtained by MOLBSA and MOBSA in 6-unit system—Case1

Table 10 Best solutions for $f_c$ in 6-unit system—Case2

Table 11 Best solutions for $f_e$ in 6-unit system—Case2

7.2 Comparison of solution quality

Three performance evaluation criteria are generally introduced to evaluate the performance of Pareto optimal solutions obtained by MOEAs (Zitzler 1999).

• Uniformity The distribution of the obtained Pareto front is as uniform as possible.

• Diversity The distribution of the obtained Pareto front is as wide as possible.

• Convergence The obtained Pareto optimal set is as close as possible to the true Pareto optimal front.

In order to evaluate the quality of the Pareto optimal solutions, MOBSA, multi-objective PSO (MOPSO) (Bo and Yi-Jia 2005) and NSGA-II (Ah King et al. 2005) are selected to compare with MOLBSA. Table 12 provides the parameter settings (Xu et al. 2018). The four algorithms adopt the same constraint handling strategy, which has been shown in Section 6.1.

7.2.1 Comparison of spacing metric value

To evaluate the uniformity of the Pareto front obtained, a spacing metric (SP) (Schott 1995) is used to measure the uniformity of Pareto front. The formula of SP is as Eq. (23).

$$\begin{aligned} SP= & {} \sqrt{\frac{1}{{|Ar| - 1}}\sum \limits _{t = 1}^{|Ar|} {{{({{\overline{d}}} - {d_t})}^2}} }, \quad {d_t} \nonumber \\= & {} \mathop {\min }\limits _{{Ar_k} \in Ar \wedge {Ar_k} \ne {Ar_t}} \sum \limits _{m = 1}^M {|{f_m}} ({Ar_t}) - {f_m}({Ar_k})| \end{aligned}$$

(23)

where $d_t$ indicates the Euclidean distance of two consecutive solutions of Pareto optimal set. ${{\overline{d}}}$ is the average of all $d_t$. If the SP value is very small, it indicates that the distribution of Pareto front is uniform. The SP value is zero, which represents that all solutions of the Pareto front are equidistant.

Table 12 Parameter settings for 4 algorithms

Table 13 Statistical results of the SP in 6-unit system—Case2

Table 14 Statistical results of the SP in 10-unit system—Case2

Fig. 7

Pareto fronts and compromise solutions obtained by 4 algorithms in 6-unit system—Case2

Fig. 8

Pareto fronts and compromise solutions obtained by the four algorithms in 10-unit system—Case2

Tables 13 and 14 show the statistical results of the SP values of the four algorithms on two systems for Case2, respectively. The statistics are the best, median, worst, average and standard deviation (Std) of SP values in 30 independent experiments. From Tables 13 and 14, the statistical results of five statistics obtained by MOLBSA are smaller than those of the other three algorithms. That is to say, the Pareto front obtained by MOLBSA is more uniform than those of the other algorithms on two system for case2. Moreover, MOLBSA also demonstrates the best robustness in terms of uniformity.

To visually compare the distribution of the Pareto front obtained, Figs. 7 and 8 illustrate the Pareto fronts obtained by MOLBSA, MOBSA, MOPSO and NSGA-II. From these two figures, it can be inferred that the distribution of MOLBSA is more uniform than those of the other three algorithms on two systems for Case2. Combined with the information of graphs and tables, it can be concluded that the Pareto front obtained by MOLBSA is more uniform than those of the other three algorithms.

7.2.2 Comparison of hypervolume value

Hypervolume (HV) (Wu et al. 2010) is a hybrid metric proposed by Zitler and Thiele, which can measure the convergence and diversity of Pareto front. HV denotes the volume covered by Pareto front in the target domain, Eq. (24) is the specific calculation formula of HV.

$$\begin{aligned} HV = \sum \limits _{t = 1}^{|Ar|} {{v_t}} \end{aligned}$$

(24)

where $v_t$ is the volume of a hypercube formed by a given fixed reference point $w_r$ and the solution $Ar_t$. HV can be obtained from the sum of $v_t$, and varies with $w_r$ taking different points. The larger the HV value, the wider the coverage of obtained Pareto front is. The same reference point $w_r$ is adopted to calculate HV in the four algorithms.

The statistical results of the HV values for the four different algorithms are compared in Tables 15 and 16. From Table 15, the five statistics of the proposed MOLBSA reach the maximum HV values. This implies that the Pareto front obtained by MOLBSA has better the diversity and convergence than those of MOBSA, MOPSO and NSGA-II in 6-unit system. The results in 10-unit system are slightly different from those in 6-unit system. Table 16 shows that the results of MOLBSA are not the best at the four statistics (Best, Worst, Median and Average). However, in terms of standard deviation (Std), the MOLBSA is the best. This shows that the diversity of MOLBSA is no longer an advantage with the increase of variables, but MOLBSA has the best robustness in the HV.

7.2.3 Comparison of c-metric value

C-metric (C) (Zitzler et al. 2000) is adopted to evaluate the quality of the obtained Pareto front for optimization problems with unknown true Pareto front in advance, and to represent the dominance relationship between two Pareto optimal sets. C formula can be expressed as

$$\begin{aligned} C(Ar1,Ar2) = \frac{{|\{ {x_2} \in Ar2,\exists {x_1} \in Ar1:{x_1} \prec {x_2}\} |}}{{|Ar2|}} \end{aligned}$$

(25)

where Ar1 and Ar2 are two Pareto optimal sets obtained by two different algorithms, respectively. $C(Ar1,Ar2)=1$ represents that Ar2 are dominated by Ar1. That is to say, Ar1 covers Ar2. $C(Ar1,Ar2)=0$ means that none solution in Ar2 is dominated by any solution in Ar1.

Tables 17 and 18 show the comparison results of the C values calculated from the best Pareto optimal sets of different algorithms. From Table 17, the solutions of MOBSA, MOPSO and NSGA-II dominate 2%, 2% and 6% solutions of MOLBSA, respectively. However, the solutions of MOLBSA dominate 72%, 68% and 24% of the solutions of MOBSA, MOPSO and NSGA-II separately. As shown in Table 18, the solutions of MOBSA, MOPSO and NSGA-II dominate 0%, 24% and 4% solutions of MOLBSA, respectively, and the solutions of MOLBSA dominate 72%, 18% and 48% of the solutions of MOBSA, MOPSO and NSGA-II, respectively. All these data clearly prove the fact that the Pareto front obtained by MOLBSA is closer to the true Pareto optimal front than those obtained by MOBSA, MOPSO and NSGA-II in two system. That is to say, the Pareto front obtained by MOLBSA has better convergence than those of MOBSA, MOPSO and NSGA-II.

Table 15 Statistical results of the HV in 6-unit system—Case2

Table 16 Statistical results of the HV in 10-unit system—Case2

Table 17 Statistical results of the C in 6-unit system—Case2

Table 18 Statistical results of the C in 10-unit system—Case2

8 Conclusions

In this paper, a multi-objective learning backtracking search algorithm (MOLBSA) is successfully presented for solving the bi-objective EED problem with constrains. To enhance the quality of the Pareto optimal solutions obtained by MOLBSA, two learning strategies are proposed. The first is a leader-choosing strategy, which accords to maximum distance between solutions to select the sparse Pareto optimal solution as the leader. The second is a leader-guiding strategy, which leads individuals to move toward the direction of sparse solution in Pareto optimal set. Moreover, a constraint handling technique is used to settle the power balance equality constraint in the EED problem. This paper studies the effectiveness of MOLBSA by testing 6-unit system and 10-unit system. Numerical results of compromise solutions and extreme solutions using MOLBSA and other seven well-known approaches disclosure that MOLBSA has can obtain a satisfactory compromise solution and highly diverse Pareto optimal set. Compared with other three established methods for three metrics, namely, spacing metric (SP), hypervolume (HV) and c-metric (C), the Pareto front obtained by MOLBSA in EED problem shows superior uniformity. However, as the number of decision variables increases, the diversity of Pareto front obtained by MOLBSA is no longer advantageous. This is because the proposed algorithm puts more efforts on improving the uniformity.