Memetic algorithm with Preferential Local Search using adaptive weights for multi-objective optimization problems

Abstract

Evolutionary multi-objective optimization algorithms are generally employed to generate Pareto optimal solutions by exploring the search space. To enhance the performance, exploration by global search can be complemented with exploitation by combining it with local search. In this paper, we address the issues in integrating local search with global search such as: how to select individuals for local search; how deep the local search is performed; how to combine multiple objectives into single objective for local search. We introduce a Preferential Local Search mechanism to fine tune the global optimal solutions further and an adaptive weight mechanism for combining multi-objectives together. These ideas have been integrated into NSGA-II to arrive at a new memetic algorithm for solving multi-objective optimization problems. The proposed algorithm has been applied on a set of constrained and unconstrained multi-objective benchmark test suite. The performance was analyzed by computing different metrics such as Generational distance, Spread, Max spread, and HyperVolume Ratio for the test suite functions. Statistical test applied on the results obtained suggests that the proposed algorithm outperforms the state-of-art multi-objective algorithms like NSGA-II and SPEA2. To study the performance of our algorithm on a real-world application, Economic Emission Load Dispatch was also taken up for validation. The performance was studied with the help of measures such as Hypervolume and Set Coverage Metrics. Experimental results substantiate that our algorithm has the capability to solve real-world problems like Economic Emission Load Dispatch and is able to produce better solutions, when compared with NSGA-II, SPEA2, and traditional memetic algorithms with fixed local search steps.

1 Introduction

Many of the real-world problems like scheduling, resource allocation, aerodynamic design, supply chain management, microprocessor chip design, mechanical component design, and medical image reconstruction (Bagchi 1999; Cheng and Li 1997; Joines et al. 2002; Aguilar and Miranda 1999; Deb 2001) have multiple competing objectives to optimize. These are called multi-objective optimization problems (MOOPs), where the objectives need to be simultaneously optimized. Almost all of these real-world multi-objective problems have constraints that are to be satisfied. A constrained multi-objective optimization problem with M objectives is formulated as,

$$\begin{aligned} \left. \begin{array}{ll} \mathrm{Minimize/maximize} ~f_m(x),&{}\quad m=1,2,\ldots ,M; \\ \mathrm{subject~ to} ~g_j(x)\le 0,&{}\quad j=1,2,\ldots ,J; \\ h_k(x) = 0,&{}\quad k=1,2,\ldots ,K;\\ x_i^{(L)} \le x_i \le x_i^{(U)}&{}\quad i=1,2,\ldots ,I; \end{array} \right\} \end{aligned}$$

(1)

There are J inequality and K equality constraints with I decision variables in the above equation. Constrained multi-objective problems divide the search space into two regions as feasible and infeasible regions (Deb 2001). Solution $x^{(i)}$ that satisfies all the constraints is a feasible solution.

Multi-objective optimization problems require a set of Pareto optimal solutions rather than a single optimal solution. These Pareto optimal solutions exhibit a trade-off among the objectives (Coello 2000; Konak et al. 2006) and are non-dominating in nature. A solution x is said to dominate another solution y, when it is not worse than y in all objectives and strictly better than y in at least one objective (Deb 2001). If x does not dominate y and y does not dominate x, then x and y are non-dominant solutions. Such solutions are Pareto optimal and are not dominated by any other solution in the population. For a Pareto optimal solution, improvement in one objective of the solution will worsen at least one of the other objectives. Objective values corresponding to Pareto optimal solutions form Pareto optimal front in the objective space.

The goals of any multi-objective optimization algorithm that solves a MOOP are to converge towards optimal front and to generate uniformly spread solutions across the Pareto front in low computation time (Zitzler et al. 2000; Mostaghim 2004). Multi-objective evolutionary algorithms (MOEAs) (Fonseca and Fleming 1995) are widely used for solving MOOPs. Evolutionary algorithms inherently deal with a population of solutions and have the ability to generate a set of optimal solutions while solving multiple objectives. Genetic Algorithm (GA) (Holland 1975; Goldberg 1989) is one kind of evolutionary algorithm that performs a stochastic search and imitates the evolution of nature. Genetic Algorithms are designed to explore the entire search space and generate Pareto optimal solution set when used to optimize multiple contradicting objectives. Genetic Algorithms are broadly categorized under global search algorithms.

Multi-objective evolutionary algorithms are generally classified into elitist and nonelitist algorithms with respect to whether any explicit measures are taken to retain potential solutions or not. Several nonelitist and elitist algorithms have been reported so far. VEGA (Schaffer 1985), MOGA (Fonseca and Fleming 1993), NPGA (Horn et al. 1994), NSGA (Srinivas and Deb 1994), and WBGA (Hajela and Lin 1992) are a few of the nonelitist multi-objective evolutionary algorithms, whereas NSGA-II (Deb et al. 2000, 2002), SPEA (Zitzler and Thiele 1999), SPEA2 (Zitzler et al. 2001), and PAES (Knowles and Corne 2000) are some of the widely used elitist multi-objective evolutionary algorithms. A detailed survey of such algorithms can be found in Konak et al. (2006), Coello and Zacatenco (2006), Coello (2000), and Coello (2002).

Advantages of evolutionary algorithms (EAs) are many when compared with other optimization algorithms. They are simple, are easy to customize, have wide range of applications, are suitable for complex search spaces, and can outperform classical techniques for optimization (Blickle 1996). Despite having advantages, EAs have a few drawbacks such as lack of fine tuning the solutions in the search space (Krasnogor and Smith 2005) and premature convergence (McGinley et al. 2011). To overcome these drawbacks, a global search algorithm like GA can be combined with a local search procedure resulting in memetic algorithm (MA) (Moscato 1989) or hybrid algorithm. Performance of any search algorithm can be enhanced further by combining with other search algorithms, by accelerating the nature of problem solving (Ong et al. 2010). GAs can be easily combined with any other traditional optimization techniques (Fogel 1995; Abraham 2005). This kind of integration of two different search procedures will improve the search performance of the hybrid algorithm. The research issues to be considered while integrating two search procedures are (Ong et al. 2010; Krasnogor and Smith 2005):

• Whether all the individuals or only a few individuals are chosen for local search;

• How often a local search can be applied;

• How deep a local search is allowed;

• How multi-objectives can be converted into a single objective for performing local search.

Our proposed algorithm addresses the abovelisted issues by preferentially selecting individuals on the basis of their potential, limiting the number of local searches applied, facilitating iterative deepening of search and using a new adaptive weight scheme for combining multiple objectives into a single one. These ideas have been incorporated into the existing NSGA-II algorithm arriving at a new algorithm called memetic algorithm with Preferential Local Search using adaptive weights (MAPLS-AW).

Performance of the proposed algorithm has been evaluated on constrained and unconstrained benchmark test problems using four metrics: Generational Distance, Spread, Max spread and HyperVolume Ratio. The proposed algorithm has also been applied on Economic Emission Load Dispatch (EELD), a real-world application and performance was evaluated using Hypervolume metric and Set Coverage Metrics. The results observed show that MAPLS-AW performs better than NSGA-II, SPEA2, and traditional memetic algorithms with fixed local search steps.

This paper is organized as follows. Section 2 gives rest of background and presents various issues in designing hybrid search algorithms. Proposed algorithm MAPLS-AW is presented in Sect. 3. Section 4 summarizes the details of implementation and experiments conducted along with discussion of results. Application of proposed MAPLS-AW on a real-world problem, EELD, is discussed in Sect. 5. Section 6 gives the conclusion of the proposed algorithm with future directions.

2 Background and related works

2.1 Multi-objective optimization

Conventionally, multi-objective problems are solved by combining multiple objectives into a single objective. Classical aggregation methods such as weighted sum, value function, and $\epsilon$-constraint method generate single optimal solution per run. To obtain a set of Pareto optimal solutions, a classical optimization method has to be repeatedly executed with different parameters. Several algorithms have been developed to simultaneously solve multiple objectives in order to generate a set of Pareto optimal solutions. The generated Pareto optimal solutions should be close to the optimal front and also be uniformly distributed across the Pareto front by exploring the extreme regions of the search space (Konak et al. 2006).

Evolutionary GA is a nature inspired computation strategy that imitates the evolutionary process. Each individual in GA is called a chromosome that carries distinct elements called genes. To solve an optimization problem using GA, the first essential step is to encode the solutions into chromosomes. Several different encoding schemes are available to represent the solutions, such as binary encoding, value encoding, real encoding, and permutation encoding. Selecting a specific encoding technique depends on the problem to be solved. Binary encoding (Goldberg 1989) is the most common representation used to encode chromosomes and has got a variety of applications. When some real-world problems require real values to encode decision parameters, real coding scheme finds its use (Herrera et al. 1998). A collection of chromosomes forms the population. With iterative application of genetic operators such as crossover and mutation on selected solutions evolves the population towards the optimal solutions.

As GAs are designed to work with population of solutions, they are suitable to solve multi-objective problems. Such multi-objective GAs differ in their working with respect to Pareto ranking principle or fitness sharing strategy. Most of the recent GAs use elitism to preserve the elite solutions (Coello and Zacatenco 2006). Two methods have been used to employ elitism. They are maintaining an elite population set and maintaining a separate archive for elite solutions which will be used during the evolution. NSGA-II is an elitist multi-objective GA that preserves elitist solutions in the population itself. This algorithm remains as one of widely used MOEAs, due to its effective performance (Coello and Zacatenco 2006) and hence we have decided to adapt NSGA-II for our proposed work.

NSGA-II is a ranking-based evolutionary algorithm which has measures to maintain elitism and preserve the diversity of solutions. Once the population is initialized with random solutions, the population is sorted into different ranks using non-dominated sorting method. Individuals in the same rank are placed in the same front. NSGA-II uses the crowded sorting operator for selecting an individual from the same front. This operator sorts the individuals in the same rank with respect to the density of surrounding solutions. A solution from less dense space is given the highest preference for selection (Deb et al. 2002). This feature is one that explicitly maintains the Spread of optimal solutions.

The Pareto optimal solutions generated by the optimization process should be from the feasible region of search space. In such case, the selection procedure in the evolutionary cycle needs to select feasible solutions from the search space. Constrained binary tournament selection (Deb 2001) is one such selection procedure used in constrained optimization problems. Two solutions say x and y are chosen at random from the population.

• If x and y both are feasible solutions and are in different ranks, a solution with better rank is selected. If both solutions are in same rank then a solution from less crowded space will be selected.

• If one out of x and y is feasible and other is an infeasible solution, then a feasible solution is selected.

• If x and y, both are infeasible solutions then the one with less constraint violation will be selected.

NSGA-II calls the above procedure as crowded comparison operator.

2.1.1 Crossover and its characteristics

The primary search operator that explores the search space in the nature inspired evolutionary algorithms is the crossover operator (De Jong and Spears 1992; Črepinšek et al. 2013). Crossover operation determines the extent of exploration to be performed in the search space. Search space can be divided into exploration zone and exploitation zone (Herrera et al. 2003). When similar parents undergo crossover they lead to exploitation of the region than exploration. McGinley et al. (2011) introduces an adaptive crossover by varying the crossover probability. Two different measures such as Standard Population Diversity (SPD) and Healthy Population Diversity (HPD) are used for crossover adaptation thereby to improve the diversity of the population.

Simulated binary crossover (SBX) (Deb and Kumar 1995; Deb and Agrawal 1995) is one of real-coded crossover operators. This has the same search ability as that of single-point binary crossover. If $P_1$ and $P_2$ are the two parents selected for SBX crossover, new offspring say $C_1$ and $C_2$ will be generated as per the following procedure: A random value u between 0 and 1 is selected. $\beta$, the Spread factor is calculated with respect to u value. If u is less than 0.5 then $\beta = (2*\textit{u})^{1/\eta _c+1}$ otherwise $\beta = 1/(2*(1-\textit{u})^{1/\eta _c+1})$. $\eta _c$ is the distribution factor that decides whether children should be generated nearer to the parents or not. Higher the value of $\eta _c$ closer the children to the parents otherwise they will be generated far away from the parents.

$$\begin{aligned} C_1=0.5*{[(P_1 + P_2)} - \beta *{ \mid P_2 - P_1 \mid }] \nonumber \\ C_2=0.5*{[(P_1 + P_2)} + \beta *{ \mid P_2 - P_1 \mid }] \end{aligned}$$

(2)

Balanced exploration and exploitation (Črepinšek et al. 2013) always generate diverse set of good quality solutions. Values suggested in Deb et al. (2002) for distribution parameter $\eta _c$ is between 5 and 20. To achieve maximum exploration of search space, we decided to eliminate the need of this parameter in our proposed work. By reducing the significance of $\eta _c$, the extreme regions of the search space can be explored. The new offspring will be generated in the unexplored areas of the search space.

To introduce diversity at gene level, mutation is performed on the new offspring and not all the offspring will undergo mutation. High mutation rate will affect the probability of getting the global optimum and hence always limited to a lesser value (Weise 2009). Polynomial mutation is the kind of mutation used by real-coded GAs which tries to simulate the binary mutation. Polynomial mutation, mutates the new offspring as follows. A new mutated individual $Y_i$ is given by

$$\begin{aligned} Y_i= x_i + (x_i^U - x_i^L) *\delta _i \end{aligned}$$

(3)

where $x_i$ is the $i$th parameter selected with mutation probability $p_m$, $x_i^U$ and $x_i^L$ are the lower and upper bounds of $x_i$, respectively. Mutation probability $p_m$ is usually set to 1/n, where n is the number of decision parameters in the multi-objective problem (Deb and Goyal 1996). $\delta _i$ is given by

$$\begin{aligned} \delta _i = \left\{ \, \begin{aligned}&(2r_i)^{1/\eta _m +1} - 1 ~&~&\mathrm{if} \,\, r_i \le 0.5, \\&1 - (2(1 - r_i))^{1/\eta _m +1} - 1 ~&~&\mathrm{if}\,\, r_i \ge 0.5. \end{aligned} \right. \end{aligned}$$

(4)

where $r_i$ takes a random value between [0,1] and $\eta _m$, the mutation constant is any non-negative real number. As a measure to impose elitism, NSGA-II combines the parent solutions with new offspring and non-dominated sorting is applied on the combined population. We have used the template of NSGA-II to fit in the design of our proposed algorithm.

Another kind of elitist multi-objective Evolutionary Algorithm where an external archive of non-dominating solutions is maintained is Strength Pareto Evolutionary Algorithm 2 (SPEA2) (Zitzler et al. 2001). It is different from its predecessor SPEA, in terms of fitness assignment, density estimation and truncation operations (Guliashki et al. 2009). The size of external archive can be set as same as that of population size or may be different. When the number of non- dominating solutions exceeds the size of archive, they are truncated with respect to a procedure similar to $k$th nearest neighbor. Fitness of any individual in this algorithm does not solely depend on the functional objective, but also on a strength value of dominated individuals and density information. NSGA-II and SPEA2 are the two most widely used elitist MOEAs in the literature (Zhou et al. 2011). The performance of our proposed algorithm has been compared with these two state-of-art algorithms.

2.2 Local optimization

Local search method is one of the metaheuristic techniques which is otherwise referred to as trajectory method or iterative improvement method. Local optimization or local search techniques start with an initial solution and search its neighborhood (Gaspero 2003; Blum and Roli 2003), by applying changes to the current solution. The new solution will be accepted if it is better than the previous one and by this manner an initial solution is enhanced through local optimization.

Local search techniques can be classified into derivative and nonderivative techniques (Jang et al. 2004). Nonderivative methods are simplex method (Nelder and Mead 1965), tabu search (Glover and Laguna 1997), etc, and derivative techniques include Gradient descent methods and Newton methods. Nonderivative methods rely on objective function to guide the search process (Deb 2001), whereas the derivative methods make use of gradient information from the objective space to decide the search direction.

Steepest descent or Gradient descent is one of the derivative-based algorithms which, ‘begins with an initial solution and repeatedly subtracts a fraction of locally calculated gradient from the current solution’ (Salomon 1998). That is, the new solution $x_{k+1}$ is obtained by the following equation.

$$\begin{aligned} x_{k+1} = x_k +\lambda d_k \end{aligned}$$

(5)

where x $\in$ $\mathbb {R}$, $\lambda$ is the step size. Descent direction is given by $d_k$ = $- \bigtriangledown f(x_k)$, where $f$ is the function to be optimized.

2.2.1 Issues in scalarizing objectives

Local search requires the multiple objectives to be converted into a single objective. Weighted sum approach (Zadeh 1963; Koski 1988; Coello 2000) is one among the most widely used classical aggregating methods. Weighted sum optimization scalarizes the objectives such that the sum of the weights should be equal to 1, i.e., $\sum _i^{M} W_i=1$, where M is the number of objectives. The decision for providing different weights to the objectives depends on the importance of the objectives in the optimization problem. Here are the possible ways one can assign weights to the objectives Case a: Knowing the preferences or the significance of each of the objectives in the problem, the decision maker can assign the weights to the objectives. This is the most simplest or reasonable way of using the weighted sum method. Multi-objective real-world applications are mostly optimized by this method of accepting user given preferences.

Case b: But one may not always know the significance of the objectives. In that case, following are the options that can be used.

Case b.1: Assign random weights to the objectives. The uncertainty in the weights will affect the direction of optimization and also the time taken to converge towards the optimal solutions.

Case b.2: Provide equal weights to all the objectives (Steuer 1986; Bhuvana and Aravindan 2011a). An objective that does not deserve to get equal weight as others will mislead the optimization process. That is, the equal weight will help the optimization process towards wrong direction and hence will consume more than expected time to converge towards the optimal solution. Another aspect is the weights assigned will remain fixed during the entire evolution and may also have its impact over the diversity of solutions obtained.

Case b.3: Using adaptive weights for the objectives is the other way of weight assignment. Adaptive weights are weights that change across the iterations with respect to geometric nature of the Pareto front (Kim and De Weck 2005; Jiang et al. 2011) and with the help of nadir and utopia points (Gen and Lin 2005). Hamada et al. (2010) uses one weighted scalarization method, where the initial point and the weight decide the convergence. Weight is randomly generated initially for each point in the search space and no weight adaptation performed for first iteration. The weights are assigned as the midpoint between solutions using subdivision method for the new search points. The solution is optimized for the new weight and repeated until the movement between points is too short. Scalability (Hamada et al. 2010) is limited to six or seven objectives, since the number of search points increases exponentially with respect to the number of objectives. Above drawback was overcome using barycentric subdivision and new weight adaptation scheme in Hamada et al. (2011). In Li and Landa-Silva (2008) adaptive weights are assigned according to their nearness to non-dominated neighboring solution in the population. In general, the weighted sum aggregation approach has its own set of drawbacks. Jubril (2012) discusses the drawbacks of weighted sum such as:

• 1. Missing the nonconvex surface of Pareto front.

• 2. Diversity is not controlled.

• 3. Distribution depends on relative scaling of objectives.

Proposed algorithm has introduced one form of adaptive weights for scalarizing the objectives before performing the local search. This adaptive weight strategy is scalable and hence not affected by increasing the number of objectives. Our adaptive weight assignment neither depends on the geometric nature of Pareto front, since it is not known in advance, nor it relies on the nadir or utopia points. Our proposed adaptive weight assignment algorithm overcomes the drawbacks listed earlier. The obtained results confirm that our proposed algorithm is not affected by any of the listed drawbacks.

2.3 Hybridization of evolutionary algorithms:

In MAs, the memes refer to the ‘unit of cultural evolution’ (Ong et al. 2006) that enhances or fine tunes an individual by a separate procedure. Therefore, the GA will be responsible for the exploration and the local search will take care of exploitation of local neighborhood. The main advantage of hybridization of Genetic Algorithms is to prevent premature convergence of optimization process (El-Mihoub et al. 2006). Memetic algorithms can be classified according to the types of algorithms used, level of hybridizations applied and type of inheritance performed. A survey about such classification can be found in Chen et al. (2011).

Challenges and issues in combining global and local search algorithms have been mentioned in Sect. 1. Local search (LS) is itself a separate optimization process and when it is embedded into another algorithm, the complexity of the procedure significantly increases. To reduce the complexity of the hybrid algorithm few solutions have been identified so far. LS cannot be applied on all individuals always and requires some selection strategy for filtering the individuals which can undergo the local search (Krasnogor and Smith 2005; Mongus et al. 2012). The frequency of performing local optimization during the evolutionary cycle needs to be decided. When the LS is applied on individuals, how deep the local optimization be allowed is one important issue to be addressed. Performing LS till every solution reaches the optimal value will definitely have its impact on total time consumed by the procedure. To overcome this, if the number of LS steps taken is restricted, then the fine tuning of good individuals may not happen. This requires a balanced and optimal way of integrating LS into EA to generate optimal solutions.

Having identified major issues while embedding a LS into EA, our paper proposes a memetic approach addressing how deep a local search can be applied in an optimal manner and what set of population can undergo the local search. The proposed algorithm also addresses how the weights can be assigned in an adaptive manner before applying LS. In our proposed algorithm the global search is performed by NSGA-II and local search is performed by steepest descent method.

3 Proposed algorithm

3.1 Design of memetic algorithm

The goal of memetic algorithm is to generate quality solutions by combining global and local search together. The purpose of combining two different search processes is to perform exploration of the search space and exploitation of the neighborhood locality. Issues related to combining global search and local search have been listed and discussed in the previous section. Two major proposals in this paper are adaptive weight assignment scheme for performing local search and Preferential Local Search. These two key ideas can be incorporated into any of the global search algorithms to arrive at a new memetic algorithm. In this paper, we have integrated the above two approaches into NSGA-II arriving at a new algorithm, MAPLS-AW. Balance should be maintained, when a global search is integrated with a local search process. Our proposed algorithm maintains that balance between exploration and exploitation through preferential local search and using adaptive weight assignment scheme. Due to this, the explicit exploration parameter, $\eta _c$ in Simulated binary crossover used by NSGA-II is not needed. We have eliminated the need of that parameter in our proposed algorithm and kept $\eta _c$ as a constant. In the following subsections, we have introduced the working of adaptive weight assignment and Preferential Local Search.

3.2 Adaptive weights

Using the weighted sum method, multi-objectives are combined together into single objective before the local optimization process is performed. This requires the weights to be assigned to the functional objectives. An adaptive weight mechanism has been introduced in this paper that dynamically adapts weights for the objectives.

Multi-objective problems with minimizing objectives are considered in this work, since any maximization problem can be converted (Runarsson and Yao 2000) into minimization problem.

Different cases of assigning weights have been discussed in Sect. 2.2. Uniformly distributed optimal solutions are the solutions expected out of the evolutionary process, where providing equal weights will affect the diversity of solutions obtained. Equal weights may never explore the extreme regions of the optimal front. Hence, we have decided to provide weights for the multiple objectives in an adaptive manner (Bhuvana and Aravindan 2011b). Classical aggregation techniques aggregate the objectives before the evolution begins and also does it only once. We are proposing a new aggregation method that aggregates during evolution and it is prudent to use information available in the objective space.

Adaptive weights are assigned by collecting information about a solution from its multidimensional objective space. Weights computed from these functional values will keep on changing during the course of evolutionary process.

The aim is to provide lesser preference for any objective which has larger functional value in a minimization problem. Higher preference can be given to sustain a lesser functional objective and vice versa. While associating weight in this manner to one objective function, we need to consider other objectives at the same time. If we do not consider other objectives then the evolution may take the solutions towards one particular region and make them crowded. This will affect the diversity of optimal solutions. Instead, we need to move an objective functional value towards its optimal minimum with respect to every other functional objectives in the search space. By this a solution is shifted proportionately towards the Pareto optimal. Proportionate movement in the objective space is achieved with the help of Euclidean norm.

If $f_i^{(x)}$ is the $i$th functional objective of a solution x, then the proportionate movement is given by $\omega _i$.

$$\begin{aligned} \omega _i= \frac{f_i^{(x)}}{\Vert f^{(x)}\Vert } \end{aligned}$$

(6)

where $\Vert f^{(x)}\Vert$, the Euclidean norm is given by

$$\begin{aligned} \Vert f^{(x)}\Vert ~=~\sqrt{f_1^{2^{(x)}}+f_2^{2^{(x)}}+f_3^{2^{(x)}}+\cdots +f_M^{2^{(x)}}} \end{aligned}$$

(7)

Since sum of weights in the weighted sum aggregation approach should be equal to 1, following scaling of $\omega _i$ is done:

$$\begin{aligned} \alpha _i= \frac{\omega _i}{\sum _{i=1}^M \omega _i} \end{aligned}$$

(8)

Once the individual weights are determined for all the objectives, they are combined together into a single objective F and is given by,

$$\begin{aligned} F=\alpha _1f_1+\alpha _2f_2+\alpha _3f_3+\cdots +\alpha _Mf_M \end{aligned}$$

(9)

where the sum of the weights, $\alpha _1+\alpha _2+\alpha _3+\cdots +\alpha _M~=~1$.

Local search applied after such dynamic weight adaptation will overcome the drawbacks, such as convergence time, taking optimization in the wrong direction and diversity of obtained optimal solutions.

3.3 Preferential Local Search (PLS)

The objective of integrating a local search in a global search process is to enhance the quality of solutions by fine tuning them. To establish a balance between exploration and exploitation, we are proposing Preferential Local Search (PLS). PLS addresses the issues related to combining global and local searches together. Issues addressed by PLS are choosing individuals for local search, deciding the depth of local search and determining the frequency of local search.

3.3.1 Choosing individuals for LS

Time incurred in allowing all the individuals for local search adds to the complexity of the memetic algorithm. Decision should be made to selectively allow a few for the local search. An individual in the population can be passed on to next generation only when it has potential enough to survive and compete with other peer solutions and offspring. In any $i$th generation where the population is a mix of varied set of solutions, PLS identifies the elite solutions. Preference can be given to such elite solutions to undergo local search (Krasnogor and Smith 2005; Mongus et al. 2012). These kinds of preferences to good solutions strengthen them to counter new offspring.

The offspring that are generated after the genetic operations may loose their chance in the evolution when compete with the potential parents. PLS selects the new offspring for depth-limited local search. That is, each solution will undergo at least one depth limited local search once they are newly generated. If they survive next generation, and has the potential to optimize further, local search will be deepened further.

3.3.2 Depth of LS

PLS is designed in such away to limit the depth of local search, that is, potential solutions will undergo depth-limited LS. Depth of LS is determined by predetermined number of steps. If potential solutions survive the next generation, local search will be deepened further. This way the local search is continued and iteratively deepened on good solutions across generations. Lesser the potential of one candidate solution, lesser the depth of local searches applied on it. Greater the potential, deeper will be the local search applied on that solution across generations. The potential of a candidate depends on the fitness of that individual, which is associated with both exploration of the search space and exploitation of its neighborhood. We decided to use the steepest descent as local search method, since it suits the decision of limiting the depth of applying local search.

Thus PLS chooses individuals for depth-limited local search and fine tunes them. This fine tuning spreads across generations and iteratively deepens. These steps are collectively referred to as Preferential Local Search. Algorithm for PLS incorporating the adaptive weight computation is given in Algorithm 1.

3.4 Memetic algorithm with Preferential Local Search using adaptive weights (MAPLS-AW)

Having defined the adaptive weight (AW) procedure and the concept of Preferential Local Search (PLS), the actual proposed approach, memetic algorithm with Preferential Local Search using Adaptive Weights (MAPLS-AW), is given below. These two ideas are incorporated into NSGA-II and MAPLS-AW has been arrived at. Detailed procedure is given in Algorithm 2.

MAPLS-AW begins with random initialization of population according to problem specific boundary constraints. Fitness of every individual is evaluated and non-dominated sorting is applied. Crowding distance is computed for every individual. This distance helps in selecting individuals from less crowded region and maintains diversity of solutions across the Pareto front. Binary tournament selection chooses the parents and SBX crossover is applied to generate new offspring. In SBX crossover, the distribution parameter is nullified to explore the vast search space. Polynomial mutation with respect to mutation probability modifies the new offspring. Single-step Preferential Local Search is applied on the new offsprings. These locally optimized individuals are now merged with the parent population. Non-dominated sorting is applied on combined population and it is resized to meet the population size. Crowding distance is computed for the resized population. MAPLS-AW now identifies the elite or best individuals in the current population which will undergo Preferential Local Search (PLS). To apply PLS, the objectives of the individual are combined into single using Eq. (9). To combine the objectives using weighted sum method, the adaptive weights are calculated. LS will be continued on the same individual in the next generation if it is competent enough to survive. Fitness for the new individual is computed and replaces the original one in population. Steps from selection are repeated until maximum fitness evaluations reached. MAPLS-AW performs both exploration and exploitation in a balanced manner by nullifying the distribution parameter in the SBX crossover and by Preferential Local Search. MAPLS-AW computes the fitness only when a new individual is added to the population. By design of the algorithm, MAPLS-AW reduces the computation overhead of traditional memetic algorithm by limiting the depth of local search.

4 Implementation and experiments

To assess the performance of our proposed memetic algorithm with Preferential Local Search using adaptive weight (MAPLS-AW), we have carried out several experiments. Experimental results have been evaluated in comparison with other MOEAs. This section presents implementation details of MAPLS-AW, few variants, control parameters used, benchmark test functions, and performance criteria used for evaluation. Our proposed algorithm, MAPLS-AW, has adapted NSGA-II as its global search heuristic procedure and steepest descent as the local search procedure. We have followed the guidelines suggested in Črepinšek et al. (2012, 2014) to conduct the experiments in this work.

4.1 Parameters used

Initial population for the benchmark test problems are randomly generated. These random values are generated with respect to the boundary constraints of the decision parameters of a chosen benchmark test problem. The population size is set to 50. Termination condition has been fixed as 25000 fitness evaluations for all the variants of search algorithm. For the depth-limited Preferential Local Search, the step size is 0.001 and the depth of LS is set to 1. In order to compare the performance, we have used the same initial population for all the variants of the search algorithm. To observe the consistency in performance of the algorithms, all the implementations are run for 50 times with different initial population and the mean of results is reported here. Other parameters used for implementation are given in Table 1.

Table 1 Memetic algorithm control parameters

4.2 Validation on benchmark problems

20 multi-objective benchmark test problems were used to validate our work. These are the test problems for which the optimal solutions are already known. To demonstrate the superiority of an EA over other algorithms, the new algorithm is applied over benchmark test problems (Huband et al. 2006) and the results are studied for evaluating the performance. As per Nguyen et al. (2012), benchmark test problems should exhibit flexibility, simplicity and efficiency in evaluating an algorithm and also should resemble real-world problems. Huband et al. (2006) have analyzed and reviewed a set of unconstrained test problems available in the literature. The test suites addressed are Deb’s toolkit, Zitzler’s ZDT test suite, Deb’s DTLZ test suite, and Van Veldhuizen’s tool kit. For validation, we have used fifteen unconstrained benchmark test problems in this paper. They are ZDT1, ZDT2, ZDT3, ZDT4, ZDT6, SCH1, FONSECA, SCH2, DTLZ1, DTLZ2, DTLZ3, DTLZ4, DTLZ5, DTLZ6, and DTLZ7. Among the ZDT series, ZDT3 has a disconnected Pareto front whereas the ZDT2 and ZDT6 have concave Pareto front each. Pareto fronts obtained from ZDT1 and ZDT4 are convex in nature. In DTLZ series, we have used seven DTLZ problems, where DTLZ1, DTLZ3 have multimodal Pareto fronts which are linear and concave, respectively. DTLZ2, DTLZ4, DTLZ5, DTLZ6 and DTLZ7 all have unimodal Pareto fronts whereas DTLZ4 has a concave Pareto front. DTLZ7 has got a disconnected Pareto front. In case of SCH1 and SCH2, both have convex Pareto fronts and FONSECA has a concave Pareto front. The number of decision variables for these test problems differs and is in the range of 1 and 30. The DTLZ series of problems are considered with 3 functional objectives.

Apart from unconstrained problems, we have used five constrained test problems. They are BINH2, SRN, TNK, CTP1, and CTP2 (Deb 2001). The first three test problems have 2 decision variables each, whereas the last two have 4 decision variables each.

4.3 Performance metrics

Quality of solutions determines the performance of any multi-objective optimization algorithm. Two criteria that were used to evaluate the performance of a multi-objective optimization are, how close the obtained Pareto optimal solutions are to the known optimal set and how diverse are the obtained solutions across the Pareto front. Performance metrics such as Generational Distance (GD), Spread, Max spread and HyperVolume Ratio (HVR) (Van Veldhuizen and Lamont 1999; Deb 2001) are used as measures of the above two criteria. All the above four metrics require the knowledge of the known Pareto optimal set P.

Generational Distance (GD) is the distance between the known optimal set of a problem and the obtained optimal set. It is given by

$$\begin{aligned} GD~=~\frac{\left( \sum _{i=1}^{\mid Q \mid } d_i^p\right) ^{1/p}}{\mid Q \mid } \end{aligned}$$

(10)

with $p=2$, $d_i$ is the Euclidean distance between solutions of obtained set Q and the nearest member in the known optimal set, P. The second metric is Spread $\Delta$, that measures how well the solutions are distributed and its extent across the Pareto front.

$$\begin{aligned} \Delta ~=~\frac{ d_f + d_l + \sum _{i=1}^{N-1}\mid d_i - \bar{d}\mid }{d_f + d_l +(N-1)\bar{d}} \end{aligned}$$

(11)

where $d_f$ and $d_l$ are the distance between the extreme solutions of known and obtained optimal set; $d_i$ is the Euclidean distance between the consecutive solutions of the obtained optimal set and $\bar{d}$ is the mean of the above distance. The third performance metric is Max spread (Zitzler 1999). It measures the length of the diagonal of hyperbox formed by the extreme objective values in the obtained non-dominated set (Deb 2001). It is given by

$$\begin{aligned} \bar{D}~=~ \sqrt{\frac{1}{M}\sum _{m=1}^M\left( \frac{\mathrm{max}_{i=1}^{\mid Q \mid }f_m^i - \mathrm{min}_{i=1}^{\mid Q \mid } f_m^i}{F^{\mathrm{max}}_m - F_m^{\mathrm{min}}} \right) ^2} \end{aligned}$$

(12)

$F^{\mathrm{max}}_m$ and $F^{\mathrm{min}}_m$ are the maximum and minimum value of $m$th objective in obtained optimal solution set. The final measure is the HyperVolume Ratio (HVR), which computes the ratio of HV between obtained Pareto set and known Pareto set, where HV calculates the volume covered by the Pareto set (Van Veldhuizen 1999)

$$\begin{aligned}&\mathrm{HVR}~=~ \frac{ \mathrm{HV}(Q)}{\mathrm{HV}(P)} \nonumber \\&\mathrm{HV}~=~ \mathrm{volume}\left( \bigcup _{i=1}^{\mid Q \mid } v_i\right) \end{aligned}$$

(13)

where $v_i$ is a hypercube formed between the chosen reference point and solutions of Q. Among the four performance metrics used, the first one, GD is the metric that measures the closeness criteria and Spread and Max spread test the diversity measure, whereas the Hypervolume metric measures both the closeness and diversity criteria.

Smaller value of GD metric shows that the obtained non-dominated Pareto points are closer to the known Pareto solutions. That is, the distance between the obtained and known optimal solutions is small, which is the desired one for any multi-objective evolutionary algorithm. For Spread, lesser the value, uniform will be the Spread and for Max spread metrics, higher the value better the distribution that covers the extreme regions of the Pareto front. Higher the HVR metric, larger the volume covered by the optimal solutions and closer towards the optimal front. Performance of proposed MAPLS-AW was evaluated using the above four metrics by applying the algorithm on 15 unconstrained and 5 constrained benchmark multi-objective problems.

4.4 Experiments conducted

Different experiments were conducted to observe the performance of our proposed algorithm MAPLS-AW. The objectives of these experiments are as follows:

• To demonstrate the overall performance of proposed MAPLS-AW algorithm as a Multi-objective evolutionary algorithm.

• To study the effectiveness of Preferential Local Search;

• To study the performance of assigning adaptive weights to multi-objectives while combining them into a single objective.

We have carried out three sets of experiments by implementing different variants of search algorithms. They are:

• 1. Our proposed MAPLS-AW algorithm, that combines Preferential Local Search and adaptive weight mechanism.

• 2. TLS-EW, traditional hybrid algorithm with depth-limited local search for 10 steps on every solution in the population. To perform local search, multiple objectives are combined into single objective using equal weights.

• 3. TLS-AW, traditional hybrid algorithm with depth-limited local search for 10 steps on every solution in the population but uses adaptive weights.

• 4. Two elitist multi-objective evolutionary algorithms: NSGA-II and SPEA2.

All the variations of search algorithms were implemented in C programming language in Intel(R) Core(TM)i5-3470 CPU @3.20 GHZ system. The performance of all the abovelisted algorithms was evaluated by applying them on a set of benchmark test suite and by analyzing the metrics obtained. Experiments have been carried out in the following order,

• 1. The first set of experiments were conducted to study the overall performance of MAPLS-AW as a memetic or hybrid MOEA and compared with NSGA-II and SPEA2.

• 2. NSGA-II, TLS-EW and TLS-AW were compared to study the performance of memetic algorithm and to analyze the nature of adaptive weights.

• 3. TLS-AW and MAPLS-AW were compared to study the collective performance of adaptive weights and preferential local search.

The above three experiments can be categorized into two, first that evaluates the performance of MAPLS-AW by comparing it with NSGA-II & SPEA2 and second category includes the experiments 2 and 3. Experiment 1 used same initial population to perform the evaluation on MAPLS-AW, NSGA-II, and SPEA2. For each trial of experiments 2 and 3, we have used same initial population to evaluate the variants TLS-EW, TLS-AW and to compare them with NSGA-II and MAPLS-AW. This is repeated for 50 trials, where each trial used different seed to generate different initial population. The implementations of existing algorithms, NSGA-II and SPEA2, are checked for correctness by statistically comparing their results with those of Deb et al. (2002). There are 7 common problems reported in Deb et al. (2002) and in our paper. Independent two-tailed t test was applied on Spread metric obtained for those 7 problems to check whether our implementation was error free. From the obtained t stat value, 0.330977 and the p value, 0.74823, we infer that solutions obtained by both implementations are similar with no significant difference in means and hence our implementation of NSGA-II is inferred to be error free.

Quality Metrics were computed on the final population for all the experiments carried out. Percentage of improvement was calculated on the results obtained from different variant algorithms. We have tested the data normality and homoscedasticity of the results obtained, using Chi-square test. After verifying that data normality and homoscedasticity hold good on the obtained results, we have applied ANOVA test, since multiple comparisons have been carried out. From the F values of ANOVA test, we have verified that the populations under comparison are significantly different. We then applied t test, whose p values are adjusted by Holm–Bonferroni correction to control Type-I error (Veček et al. 2014). The tables reporting the p values are corrected with respect to the number of comparisons made in that context.

4.5 Performance of proposed algorithm: MAPLS-AW

To demonstrate the overall performance of our proposed MAPLS-AW as a multi-objective evolutionary algorithm, we have carried out the first set of experiments. This section presents the comparison of performances between our proposed MAPLS-AW and the two other multi-objective evolutionary algorithms, NSGA-II and SPEA2. The mean of the four performance metrics such as Generational Distance (GD), Spread, Max spread, and HyperVolume Ratio (HVR) were observed.

Table 2 shows the performance of NSGA-II, SPEA2, and MAPLS-AW for the benchmark unconstrained and constrained problems through different metrics. Values tabulated are the mean values computed after 50 runs. Table 3 shows the superiority of the proposed MAPLS-AW algorithm through percentage of improvement on the four metrics between NSGA-II, SPEA2, and MAPLS-AW for all the test problems.

Table 2 Performance metrics of NSGA-II, SPEA2, and MAPLS-AW

Table 3 Percentage of improvement in metrics between NSGA-II, SPEA2, and MAPLS-AW

Performance of MAPLS-AW algorithm under GD metric is better than other two MOEAs, NSGA-II and SPEA2. The highest difference has been observed in DTLZ7 with 68 % of improvement and 46.5 % of improvement in DTLZ4 test problem over NSGA-II. In case of SPEA2, MAPLS-AW has shown a maximum of 76.2 and 54 % of improvement in DTLZ3 and DTLZ7, respectively. All these problem instances in which the MAPLS-AW outperforms are multidimensional problems with 3 objectives each. The non-dominating points generated by our algorithm are more closer to the known Pareto front than the other two algorithms. This is because of the exploration capability exhibited by the hybrid nature of the algorithm. Advantage of using weighted sum in the local search has guided the optimization properly and realized through the better convergence towards known Pareto.

For the Spread metric, the empirical values show a largest improvement of about 77.4 % for DTLZ1 test problem over NSGA-II algorithm. This reveals the exploration ability of our algorithm with constrained problems and ability to generate evenly distributed non-dominating points across the Pareto front. The second best value of Spread was observed with TNK for about 75.5 % when compared with NSGA-II and in SCH2 89.8 % of improvement is shown over SPEA2. Showing such high amount of improvement for a test problem with a discontinuous Pareto front clearly states that adaptive weighted sum in our algorithm has overcome the primary drawback of weighted sum approaches. ZDT4 is a complex test problem with $21^9$ local Pareto solutions (Deb 2001). Our proposed algorithm MAPLS-AW has shown an improvement in Spread metric of about 9 % over NSGA-II and 11 % over SPEA2 for this test problem. This substantiates the strength of MAPLS-AW to explore and exploit the search space and ability to generate Pareto optimal solutions with better Spread across the Pareto front.

Max spread metric obtained for proposed MAPLS-AW algorithm has shown a 43.6 % of improvement over NSGA-II in DTLZ4. This test problem has its Pareto front which is concave in nature. 97.8 % of improvement for this metric over SPEA2 has been observed in DTLZ5 problem, which has a convex Pareto front. These observations clearly show that adaptive weighted sum approach in our MAPLS-AW algorithm has not missed out the convex and nonconvex parts of Pareto front.

For HVR, 94.9 % of improvement was observed for SCH1 test problem over NSGA-II, which has shown the amount of area covered under the optimal front by the proposed MAPLS-AW. 92.2 % of improvement has been observed for DTLZ7 test problem over SPEA2. The increase in performance was due to the exploitation of the neighborhood of potential solutions by hybrid MAPLS-AW search algorithm.

One-tailed t test was applied on all the 50 samples of obtained metric values for the three algorithms, NSGA-II, SPEA2, and MAPLS-AW. Computed t stat values and adjusted p values are reported in Table 4. The number of comparisons involved here is two and the p values reported in Table 4 are after Holm–Bonferroni correction. For both GD and $\Delta$ metrics, computed t stat values are larger than t critical value and from the sign of t value, we infer that the means of GD and $\Delta$ metric obtained by NSGA-II are greater than means of those metrics obtained by MAPLS-AW.

Table 4 t stat and adjusted p values of t test when applied on performance metrics of NSGA-II, SPEA2, and MAPLS-AW

For the Max spread and HVR metrics, the absolute t stat values are greater than t critical value and from the sign of t value, we infer that means of these two metrics of MAPLS-AW are greater than NSGA-II. These are supported by corresponding p values, which are less than 0.05, implying a high confidence on the inferences made.

Finally we did a t test on the means of performance metrics obtained from 20 test problems. 2.0785, 3.465, $-$5.53, and $-$4.211 are the t stat values obtained for GD, $\Delta$, MS, and HVR when NSGA-II and MAPLS-AW are compared. Their corresponding adjusted p values are 4.15E-02, 2.59E-03, 2.47E-05, and 4.72E-04. Computed t stat values between MAPLS-AW and SPEA2 for all the test problems are, 2.557, 3.5, $-$4.05, and $-$4.355 and their corresponding adjusted p values are 1.93E-02, 2.39E-03, 6.78E-04, and 3.40E-04, respectively. From this, we infer that MAPLS-AW is in general better than NSGA-II and SPEA2.

The sample Pareto fronts shown in Figs. 1, 2, and 3 pictorially depict, how the obtained non-dominant solutions are wide spread and distributed across the Pareto front. The Pareto points were uniformly distributed and were not crowded in one region.

Fig. 1

Pareto fronts of Unconstrained benchmark problems. a Pareto front of BINH2. b Pareto front of FONSECA

Fig. 2

Pareto fronts of Constrained benchmark problems. a Pareto front of SRN. b Pareto front of CTP1

The results obtained reveal that the MAPLS-AW exploits the neighborhood region of potential parent solutions with better exploration of search space. The adaptive weights provide the functional objectives with the weight they deserve and take the optimization process in the proper direction. Hence the unnecessary random searching has been avoided here.

Fig. 3

Pareto front of ZDT6, an unconstrained benchmark problem

4.6 Performance of adaptive weights and Preferential Local Search

We have established that memetic algorithm MAPLS-AW works better than global search algorithm like NSGA-II and SPEA2. We have introduced two new features in our work, adaptive weights and Preferential Local Search, the following two subsections will discuss the individual performances of these two contributing features of MAPLS-AW. To enable this study, couple of variants of search algorithms TLS-EW and TLS-AW were implemented and experiments were carried out to compare their performances. Same initial population was used to compare the variants.

4.6.1 Adaptive weights

This section discusses about the performance of two variant memetic algorithms,TLS-EW and TLS-AW over a global search algorithm like NSGA-II. The objective is to study the performance of adaptive weights used to combine multiple objectives into a single objective.

TLS-EW, a hybrid or memetic algorithm was implemented with an integrated local search (LS), where the LS has been depth limited to 10 steps. The multi-objectives of the test problems were combined into a single objective problem on which the LS was applied. Weighted sum approach was used where the multiple objectives were assigned with equal weights. The mean of the four performance metrics such as Generational Distance (GD), Spread, Max spread, and HyperVolume Ratio (HVR) and time consumed by each of the algorithms were computed.

Table 5 shows the performance difference quantified in terms of metrics between NSGA-II and TLS-EW for the benchmark unconstrained and constrained problems. Values tabulated are the mean values computed after 50 runs.

Table 5 Performance metrics of NSGA-II, TLS-EW, TLS-AW, and MAPLS-AW

The percentage of improvement in the magnitude of the four metrics between TLS-EW and NSGA-II for all the unconstrained and constrained test problems is tabulated in Table 6. The increase in performance was due to the fine tuning through integrated LS performed on all the solutions by TLS-EW and substantiates the superiority of TLS-EW over NSGA-II.

Table 6 Percentage of improvement in metrics between NSGA-II, TLS-AW, TLS-AW and MAPLS-AW

To study the performance of adaptive weights, we implemented TLS-AW, where the LS has been depth limited to 10 steps. Adaptive weights are calculated for each solution according to their positional values in objective space using Eqs. 6, 8, and 9. Table 6 shows the difference in performance between TLS-EW and TLS-AW for the benchmark unconstrained and constrained problems. Looking at the performance of TLS-AW variant of search algorithm under GD metric, results show that it performs better in all the test problems with a lesser GD value compared to the equal weight version TLS-EW. There was a 40.6 % of percentage of improvement for DTLZ7 problem shown in Table 6 and a minimum of 2.06 % was observed for ZDT2. This shows that the adaptive weight variant of the memetic algorithm really have taken the optimization towards the known optimal solutions. The metrics computed for Spread and Max spread show that TLS-AW outperforms TLS-EW on all the benchmark problems. Spread shows an improvement from 7.42 to 83.47 %, where for the Max spread the percentage of improvement is in the range 1.14–51.65 %. The increase in performance is due to the exploitation of the neighborhood of potential solutions by hybrid TLS-AW search algorithm. Under HVR metric, the DTLZ3 test problem has shown a highest percentage of improvement of 85.33 % than any other problem in the test suite.

One-tailed t test was applied and the computed t stat values are given in Table 7 along with the p values. The p values are reported after the Holm–Bonferroni adjustment. For the GD and $\Delta$ metrics, we can infer that means of metrics obtained by TLS-EW are less than those of NSGA-II and means of metrics obtained by TLS-AW are less than those of TLS-EW. For MS and HVR metrics, the absolute t stat values are greater than t critical value and from the sign of t-stat values, we have inferred that means of these metrics obtained by NSGA-II are lesser than those of TLS-EW and means of metrics obtained by TLS-EW are lesser than those of TLS-AW.

Table 7 t stat and adjusted p values of t test applied on metrics obtained using NSGA-II, TLS-EW, TLS-AW, and MAPLS-AW

4.6.2 Preferential Local Search

The second feature contributing to the working of MAPLS-AW is the application of Preferential Local Search. To study the effectiveness of Preferential Local Search, we have conducted the experiments on variant search algorithms with PLS and without PLS. This section discusses the results obtained from proposed MAPLS-AW and hybrid algorithm TLS-AW. Former has Preferential Local Search along with adaptive weight mechanism whereas the later has got fixed 10-step local search incorporated using adaptive weights but without PLS feature. This is the third category of experiment carried out where the mean of metrics are given in Table 5.

When the metrics obtained are examined (last two columns of the Table 5), it show that MAPLS-AW outperforms the TLS-AW. This is because of the fact that, the potentially good solutions in every generation are identified and undergo local search. Those solutions are iteratively deepened further, if they survive across generations. This has been reflected in the four metrics. Percentage of improvement is shown in Table 6, where a maximum of 69.38 % in DTLZ7 in GD, 63.86 % of Spread is achieved in DTLZ1. HVR attains a maximum of 75.15 % for DTLZ3 test problem. These three test problems are multidimensional test problems which show that MAPLS-AW works better than traditional hybrid algorithm TLS-AW on multidimensional objective space as well. Quality of solutions obtained from MAPLS-AW is due to identification of potential solutions in each generation. Instead of applying N fixed local search steps on every solution, MAPLS-AW prefers individuals who survive across generations for local search and hence local search is iteratively deepened for good individuals. Statistical one-tailed t test was applied between TLS-AW and MAPLS-AW, whose adjusted p values are shown in last column of Table 7. We can infer that means of GD, $\Delta$ of MAPLS-AW are lesser than those of TLS-AW and means of MS, HVR of MAPLS-AW are better than those of TLS-AW. The time consumed by NSGA-II, TLS-EW, TLS-AW, and MAPLS-AW are given in Table 8. To summarize, we have substantiated that MAPLS-AW outperforms traditional memetic algorithm, TLS-AW, with fixed local search steps. This has been observed through performance metrics computed from the non-dominated solutions obtained.

5 Economic emission load dispatch

To demonstrate that the proposed algorithm can be used to solve real-world problems, we applied it on Economic Emission Load Dispatch (EELD) with valve point loading. The reason for choosing EELD with valve point model is to establish that our MAPLS-AW works well with the nonsmooth functions and produces better trade-off solutions. EELD is a bi-objective optimization problem that requires the objectives to be optimized for best fuel cost and emission cost. In general, the power plants want to reduce the cost involved in power generation, often neglecting the amount of pollutants they produce. Due to increase in awareness over the environmental pollution (Talaq et al. 1994; Abido 2006), there is an increase in need that demands the pollution to be controlled and to be reduced. That is, the EELD problem is to balance the two conflicting objectives of minimizing fuel cost and emission cost.

Table 8 Time consumed by each of NSGA-II, TLS-EW, TLS-AW, and MAPLS-AW in milliseconds

5.1 Problem formulation

The objective of Economic Emission Load Dispatch is to bring out a schedule of power units that generate power to meet the load demand. The schedule should be in such a way that it minimizes the costs involved in it by satisfying the equality and inequality constraints (Abido 2003; Balakrishnan et al. 2003).

5.1.1 Minimization of fuel cost

One of the objectives of Economic Emission Load Dispatch is to minimize the cost function $F(P_G)$

$$\begin{aligned} \mathrm{Minimize}~ F(P_G)= \sum _{i=1}^N f_i(P_G^i) \end{aligned}$$

(14)

where N is the number of generating units and $f_i(P_G^i)$ is the cost of generation of each unit represented by a quadratic function,

$$\begin{aligned} f_i(P_G^i) = a_i (P_G^i)^2 + b_i P_G^i +c_i \end{aligned}$$

(15)

In the above equation, $a_i$, $b_i$ and $c_i$ are the cost coefficients. Considering the valve point effect, the function is represented as a sum of quadratic and sinusoidal functions,

$$\begin{aligned} f_i(P_G^i)&= a_i + b_i P_G^i +c_i (P_G^i)^2 \nonumber \\&+\mid d_i sin(e_i(P_G^i{\mathrm{min}} - P_G^i ) \mid \end{aligned}$$

(16)

$d_i$, $e_i$, and $P_G^i{\mathrm{min}}$ are the cost coefficients and lower power generation limit of $i$th unit.

5.1.2 Minimization of emission cost

The other objective of EELD is to minimize the total amount of emission from the system,

$$\begin{aligned} \mathrm{Minimize}~ E(P_G)= \sum _{i=1}^N E_i(P_G^i) \end{aligned}$$

(17)

where $E_i(P_G^i)$ is the emission dispatch from each generating unit given by sum of quadratic and exponential function.

$$\begin{aligned} E_i(P_G^i) = \alpha _i + \beta _i P_G^i +\gamma _i (P_G^i)^2 + \eta _i \mathrm{exp}(\delta _i P_G^i) \end{aligned}$$

(18)

where $\alpha _i$, $\beta _i$, $\gamma _i$, and $\eta _i$, $\delta _i$ are the emission coefficients of $i$th unit.

5.1.3 Constraints

5.1.4 (i) Power balance constraints

The total power generated by all the units should be equal to the sum of total demand $P_D$ and transmission loss $P_L$,

$$\begin{aligned} \sum _{i=1}^N P_G^i - P_D - P_L = 0 \end{aligned}$$

(19)

$P_L$ is calculated by B coefficients method (Wood and Wollenberg 2011) which can be represented by

$$\begin{aligned} P_L = \sum _{i=1}^N \sum _{j=1}^N P_G^i B_{ij} P_G^j \end{aligned}$$

(20)

5.1.5 (ii) Capacity constraints

The power generated by each unit is restricted by upper and lower power limits

$$\begin{aligned} P_G^i{\mathrm{min}} ~ \le ~ P_G^i ~ \le ~P_G^i{\mathrm{max}} ~~~ i~\in ~ N \end{aligned}$$

(21)

5.2 Implementation of MAPLS-AW to solve EELD problem

Population is initialized with randomly generated individuals within the capacity constraints. Each chromosome will be a vector of N parameters, where each parameter refers to the power generated by each generator.

$$\begin{aligned} \langle P_1 ~ P_2 ~ P_3 ~ P_4 ~ \cdots ~ P_N \rangle \end{aligned}$$

(22)

Fitness of each individual is evaluated and the steps of MAPLS-AW namely, identifying the parents, applying Preferential Local Search on them, computing ranks and fronts using non-domination relation, computing crowding distance, constructing the mating pool using constrained binary tournament selection are carried out. This is followed by the recombination operations over selected parents. SBX crossover with nullified distribution parameter is applied over every gene of the chromosome. Polynomial mutation is performed on the new offspring with respect to mutation probability. The new set of offspring undergoes the one-step preferential local search and then combined with parents for the next generation.

Adaptive weight is computed for each individual and used for the calculation of the weight to be assigned for the individual objectives. Stopping criteria is set to 1,500 fitness evaluations. We have used the inputs for cost and emission coefficients from Basu (2011).

5.2.1 Performance metrics

To evaluate the performance of the MAPLS-AW on a real-world problem, we have used two metrics to examine the quality of obtained solutions. They are Hypervolume (HV) and Set Coverage metric (SCM). Since the optimum solutions are not known for EELD problem, these two metrics will help in evaluating the proposed MAPLS-AW algorithm.

The SCM compares two sets of solutions and yields an outcome in the range 0 and 1, with respect to the amount of coverage between the sets. Let A and B be the two solution sets, Set Coverage Metric (Zitzler and Thiele 1999) between A and B is given by

$$\begin{aligned} SCM(A,B)~=~ \frac{ \mid \{b~\epsilon ~ B~\mid ~ \exists ~a~ \in ~A: a~\prec ~ b \}\mid }{\mid B \mid } \end{aligned}$$

(23)

SCM(A,B) $=$1, when solutions of A are dominating all the solutions of B and SCM(A,B) $=$ 0, when none of A is dominating the solutions of B. SCM is not symmetric that is, SCM(A,B) $\ne$  SCM(B,A). The resultant set generated by MAPLS-AW has been compared with the set obtained from NSGA-II and SPEA2. That is, SCM(MAPLS-AW, NSGA-II), and SCM(NSGA-II, MAPLS-AW) have been computed to analyze the performance of MAPLS-AW. Similarly, SCM between MAPLS-AW and SPEA2 has been computed.

Three different test cases are used to evaluate the performance of the MAPLS-AW algorithm. They are 6, 10, and 40 generator systems to generate 1,200 MW, 2,000 MW, and 10,500 MW power, respectively.

5.3 Performance of MAPLS-AW on EELD problem

5.3.1 Case I

This is a 6 generator system with simple quadratic fuel and emission cost functions and with the transmission loss to generate 1,200 MW power. The test data are taken from Basu (2011). The results of best fuel cost and emission cost obtained from NSGA-II, SPEA2, and memetic algorithm with Preferential Local Search using adaptive weights (MAPLS-AW are shown in Fig 4. The Hypervolume metric obtained for this test case is listed in Table 9. The proposed MAPLS-AW resulted in higher value, i.e., the volume covered under the optimal front by the MAPLS-AW algorithm was larger when compared with the rest of the algorithms. MAPLS-AW shown an improvement of about 6.6 and 3.5 % over NSGA-II and SPEA2, respectively.

Fig. 4

Pareto front of 6 generator case

Table 9 Performance metrics obtained from NSGA-II, SPEA2, and MAPLS-AW

The adjusted p values of t test over Hypervolume metric shown in Table 10 also confirmed that there is a significant difference between MAPLS-AW, NSGA-II, and SPEA2 algorithms. Along with Hypervolume metric, we have computed SCM. Mean of SCM values after 50 runs has been computed and tabulated in Table 9. The SCM between the proposed MAPLS-AW and NSGA-II for case I, 6 generator system shows the effective coverage of non-dominating solutions of MAPLS-AW than NSGA-II. That is, number of non-dominating solutions generated by MAPLS-AW is 54.49 % more than non-dominating solutions obtained from NSGA-II. There was a massive 83.54 % of improvement in the SCM metric between MAPLS-AW and SPEA2.

Table 10 t stat and adjusted p values of t test applied on metrics obtained from NSGA-II, SPEA2, MAPLS-AW

5.3.2 Case II

The second case is a system with 10 generators considering the nonsmooth functions of valve point effect and with transmission loss to generate 2,000 MW power. Optimal fuel and emission cost obtained generated by three algorithms are shown in Fig. 5, which depicts that proposed MAPLS-AW obtained best emission and fuel cost outperforming the other two algorithms. The Hypervolume metric tabulated in Table 9 shows that proposed MAPLS-AW has covered larger area under the optimal front and this has been supported by the t test results in Table 10. This 10 generator case has shown an improvement of about 63.73 % over NSGA-II and 57.81 % over SPEA2 in Hypervolume metric. It is evident that this kind of improvement is due to the presence of two contributing features, Preferential Local Search and adaptive weights that enable a wide exploration of extreme regions of search space.

Fig. 5

Pareto front of 10 generator case

The SCM computed between NSGA-II and MAPLS-AW reveals that less number of non-dominating solutions have been obtained from NSGA-II than MAPLS-AW. Similarly, the amount of coverage by MAPLS-AW over SPEA2 was way better with 75.7 % of improvement than set coverage of SPEA2 over MAPLS-AW. The adjusted p values of t test over SCM for these algorithms are given in Table 10, where the adjusted probability values for the one-tailed were well below the level of significance, which is 5 %. The t test confirmed that proposed MAPLS-AW algorithm is significantly better than NSGA-II and SPEA2.

5.3.3 Case III

As the third case, we took the 40 generator system with valve point loading with demand of 10,500 MW of power using nonsmooth fuel cost and emission functions. Cost coefficients and generator capacity constraints are taken from Basu (2011). 40 generator system has been taken as a no loss case. We applied MAPLS-AW algorithm, NSGA-II, and SPEA2 to solve this multi-objective problem. Non-dominated solutions obtained from three algorithms are shown in Fig. 6. The amount of area covered under Pareto front measured in terms of Hypervolume obtained by MAPLS-AW is better than other two algorithms. Table 9 presents the performance of algorithms in comparison where there is a 4.6 % of improvement over NSGA-II and 5.6 % of improvement over SPEA2.

Fig. 6

Pareto front of 40 generator case

The mean of SCM obtained by comparing non-dominated solutions obtained from MAPLS-AW, NSGA-II, and SPEA2 for this case is given in Table 9. There is an improvement of 74.2 % observed by MAPLS-AW over SPEA2 and 19.2 % over NSGA-II. The t test was applied over the metrics HV & SCM. The computed t stat values and the adjusted p values are presented in Table 10. From these values, we can infer that the metrics of MAPLS-AW are better than those of NSGA-II & SPEA2. This shows that MAPLS-AW is able to achieve quality solutions on complex real-world applications as well.

6 Conclusion

In this paper, we have introduced a hybrid algorithm referred to as MAPLS-AW. This memetic algorithm addresses the challenges that arise while combining a global search with local search procedure. MAPLS-AW deals with which individuals are chosen for local search, how often a local search can be applied, and how deep a local search is allowed. MAPLS-AW identifies potential solutions for Preferential Local Search and facilitates iterative deepening of local search over them. We have proposed an adaptive weight mechanism which is used while converting multi-objectives into single objective. This adaptive weight assigned to every objective is dynamic and adapts across generations. Adaptive weights are computed by taking the current positional information of a solution from the objective space.

To examine the overall performance of proposed MAPLS-AW algorithm as a multi-objective evolutionary algorithm, we compared it with NSGA-II and SPEA2. We tested the performance of the proposed algorithm by applying it on 20 constrained and unconstrained benchmark test problems and a real-world application EELD.

The performance metrics reveal that the proposed MAPLS-AW stands out as a better algorithm. This is due to the preferential identification of good solutions and the fine tuning applied on them. Statistical t test confirmed that proposed MAPLS-AW algorithm is performing better than NSGA-II and SPEA2.

When applied on a real-world application like EELD, MAPLS-AW is able to produce the better fuel and emission cost in all the three different case studies taken. The performance of proposed algorithm on EELD is measured using Hypervolume metric and Set Coverage Metrics and tested using statistical t test. The results reveal that our proposed algorithm has the ability to provide a trade-off among the nonsmooth functional objectives.

In the current work, we have used a hard fixed termination condition of 25000 fitness evaluations. Instead, proper decision making can be incorporated to decide upon when to stop the evolution of the memetic algorithm. In this paper, the idea of Preferential Local Search with adaptive weights has been incorporated into NSGA-II to develop the hybrid algorithm. But these ideas can be easily integrated with any of the other evolutionary optimization algorithms.