An efficient algorithm for constrained global optimization and application to mechanical engineering design: League championship algorithm (LCA)

Abstract

The league championship algorithm (LCA) is a new algorithm originally proposed for unconstrained optimization which tries to metaphorically model a League championship environment wherein artificial teams play in an artificial league for several weeks (iterations). Given the league schedule, a number of individuals, as sport teams, play in pairs and their game outcome is determined given known the playing strength (fitness value) along with the team formation (solution). Modelling an artificial match analysis, each team devises the required changes in its formation (a new solution) for the next week contest and the championship goes for a number of seasons. In this paper, we adapt LCA for constrained optimization. In particular: (1) a feasibility criterion to bias the search toward feasible regions is included besides the objective value criterion; (2) generation of multiple offspring is allowed to increase the probability of an individual to generate a better solution; (3) a diversity mechanism is adopted, which allows infeasible solutions with a promising objective value precede the feasible solutions. Performance of LCA is compared with comparator algorithms on benchmark problems where the experimental results indicate that LCA is a very competitive algorithm. Performance of LCA is also evaluated on well-studied mechanical design problems and results are compared with the results of 21 constrained optimization algorithms. Computational results signify that with a smaller number of evaluations, LCA ensures finding the true optimum of these problems. These results encourage that further developments and applications of LCA would be worth investigating in the future studies.

Introduction

Due to the frequent appearance in the real world applications, constrained optimization problems, especially nonlinear optimization problems, are of scientists’ great interests in recent decades. Structural optimization, engineering design, VLSI design, etc., are just a few fields in which constrained optimization problems are met. A general constrained optimization problem can be defined as follows:

$$\begin{array}{ccc}\text{minimize}\hfill & f\left(X\right)\hfill & \hfill \\ \hfill & g_j\left(X\right)\le 0\text{,}\hfill & j=1,\dots ,q\hfill \\ \hfill & h_j\left(X\right)=0\text{,}\hfill & j=q+1,\dots ,m\hfill \\ \hfill & L\le X\le U\hfill & \hfill \end{array}$$

where $X=(x_1,x_2,\dots ,x_n)\in {\Re }^n$ is an $n$-dimensional decision vector, $L=(l_1,l_2,\dots ,l_n)$ and $U=(u_1,u_2,\dots ,u_n)$ are the lower and upper bound vectors with the condition that $l_d\le x_d\le u_d,d=1,\dots ,n.f\left(X\right)$ is a numerical function to be minimized, $g_j\left(X\right)\le 0,j=1,\dots ,q$ are $q$ inequality constraints and $h_j\left(X\right)=0,j=q+1,\dots ,m$ are $m-q$ equality constraints. The feasible region in which every point satisfies all constraints is denoted with $F$, and $E$ is the whole search space in which every point satisfies the upper and lower bound constraints; therefore $F\subseteq E$. At any point $X\in F$, the constraint $g_k$ that satisfies $g_k\left(X\right)=0$ is called an active constraint at $X$. Hence, all equality constraints $h_j$ are active at all points of $F$ [1].

The main challenge in constrained optimization is how to balance the search between feasible and infeasible regions effectively, i.e., to design an efficient constraint handling technique to locate the global optimum in the feasible region [2]. Several trends for handling infeasible solutions have been emerged in the area of evolutionary computation. Among numerous methods that have been proposed for handling constraints, the most popular methods are the penalty function method, special representations and operators, repair methods, methods based on the separation of objectives and constraints, etc [3], [4].

To tackle a certain difficult problem for which a common representation scheme might not be appropriate, a typical way would be to develop special representations and consequently design special operators to enforce feasibility of solutions at all time. However, this approach is problem dependent and remains applicable for problems in which locating the feasible solutions is extremely difficult [4]. Repair methods are also applicable when it is relatively easy to repair an infeasible solution to obtain a feasible one (for example, many combinatorial optimization problems admit such repairs). The difficulty with this method is that there is no unique way for designing the intended repair operator [4].

The most common approach for handling constraints is the method of penalty function. The idea is to transform a constrained optimization problem into an unconstraint one by adding a certain value to the objective function value based on the amount of constraint violation present in a solution [4]. The constraint violation for the $j$th constraint in (1) is defined as follows:

$$c{v}_j\left(X\right)=\{\begin{array}{cc}max\{0,g_j\left(X\right)\}\text{,}\hfill & j=1,\dots ,q\hfill \\ max\{0,|h_j\left(X\right)-\epsilon |\}\text{,}\hfill & j=q+1,\dots ,m\hfill \end{array}$$

where, $\epsilon$ is a small positive tolerance value to convert an equality constraint into an inequality constraint. The formulation of the penalty function is as follows:

$$\varphi \left(X\right)=f\left(X\right)+\sum _{j=1}^m{r}_j\times c{v}_j\left(X\right)$$

where $\varphi \left(X\right)$ is the penalized objective function and $r_j$ is a positive coefficient called “penalty factor”. As the infeasible solutions are penalized by the function in (3), the search ability in feasible regions will be enhanced. The most critical challenge with this method is how to set appropriate penalty weights $r_j$ [4]. It is often required to reset the penalty factors for different kinds of optimization problems and this sounds a main drawback for such methods.

The method of multi objective optimization is one of the widely used methods working based on the separation of objectives and constraints. In such methods, the objective function $f\left(X\right)$ and constraint violation measures $c{v}_j$ constitute a ($m+1$)-dimensional vector. Using some multi-objective optimization methods, the attempt is to minimize the components of the composite vector. Therefore, an ideal solution $X^{\ast }$ would have $c{v}_j\left(X^{\ast }\right)=0,j=1,\dots ,m$ and $f\left(X^{\ast }\right)\le f\left(Y\right)$ for all $Y\in F$ [3]. One of the main drawbacks of such methods is that while the computation complexity increases, the problem difficulty is not decreased.

There have been proposed many approaches that make the use of penalty functions unnecessary. Deb [5] introduced a tournament selection operator for evolutionary algorithms, where two solutions are compared at a time and the following selection criteria are always enforced:

• Between 2 feasible solutions, the one with better fitness value wins.

• If one solution is feasible and the other one is infeasible, the feasible solution wins.

• If both solutions are infeasible, the one with the lowest sum of constraint violations is preferred.

In Deb’s approach, feasible solutions are always preferred to infeasible ones. Therefore, this approach will have difficulties in problems in which the global optimum lies on the boundary between the feasible and infeasible regions [6]. To cover the lack of a diversity preserving mechanism in Deb’s approach, Mezura-Montes et al. [7] used the Deb’s approach while allowing the survival for the next generation of those individuals with a good value of the objective function, regardless of the feasibility. Through introducing a user-defined parameter called $S_r$, with probability $S_r$ the selection between the parent and offspring is only based on the objective function value and with probability $1-S_r$ the selection is by using Deb’s selection criteria. Runarsson and Yao [8] proposed a new constraint handling technique called stochastic ranking (SR). In SR, the balance between the objective and penalty functions is achieved through a ranking procedure based on the stochastic bubble-sort algorithm. Like method of Mezura-Montes et al. [7], SR uses a comparison probability ($P_f$) for comparing the feasible and infeasible solutions which enables the user to specify an agreeable bias toward the objective function in ranking individuals in evolutionary algorithms. Takahama and Sakai proposed the $\alpha$ constrained method [9] and $\epsilon$ constrained method [10], which adopt a lexicographic ordering with relaxation of the constraints. The authors call these methods algorithm transformation methods, because these methods convert an algorithm for unconstrained optimization into an algorithm for constrained optimization by replacing the ordinal comparisons with the $\alpha$ level and the $\epsilon$ level comparisons.

There are several deterministic algorithms which are efficient to solve numerical constrained optimization problems, such as the recursive quadratic programming, projection method and the generalized reduced gradient method [11]. However, efficiency of these methods is under assumptions of differentiability and continuity of the objective function, which may be rarely met in real world applications. Besides deterministic algorithms, metaheuristics, e.g., evolution strategies, particle swarm optimization, ant colony optimization, differential evolution etc., which are stochastic optimization techniques do not require any assumption on the objective function. However, such methods lack a mechanism to bias the search efficiently toward the feasible region in constrained search spaces. To cover this deficiency, a considerable amount of research have been devoted and a wide variety of approaches have been suggested in the last few years to handle constraints efficiently during the search [4], [8], [7], [10], [12].

The league championship algorithm (LCA) is a novel metaheuristic algorithm designed based on the metaphor of sporting competitions in sport leagues [13]. Besides the nature, culture, politics, human, etc. as the typical sources of inspiration behind various algorithms, the metaphor of sporting competitions is used for the first time in LCA. The methodology of LCA can be overviewed as follows. A number of individuals making role as sport teams compete in an artificial league for several weeks (iterations). Based on the league schedule in each week, teams play in pairs and their game outcome is determined in terms of win or loss, given known the playing strength (fitness value) along with the particular team formation/arrangement (solution) followed by each team. Keeping track of the previous week events, each team devises the required changes in its formation (a new solution is generated) for the next week contest and the championship goes on for a number of seasons (stopping condition). The way in which a new solution associated to an LCA’s team is generated is governed via imitating the match analysis process followed by coaches to design a suitable arrangement for their forthcoming match. In a typical match analysis, coaches will modify their arrangement on the basis of their own game experiences and their opponent’s style of play.

Following our successful adaptation of LCA to solve unconstrained optimization problems [13], in this paper we investigate the adaptation of LCA to solve constrained optimization problems. The remainder of the paper is organized as follows. Section 2 reviews the common terminology related to team sports, especially those which will be used metaphorically in LCA. Section 3 introduces LCA and gives a detailed report of its algorithmic features for optimizing an unconstrained numerical function. Section 4 describes how to adapt LCA to solve constrained optimization problems. The experiments performed and the results obtained are given in Section 5. In this section a collection of 22 constrained optimization problems together with several engineering design optimization problems are used to test the performance of LCA in comparison with other rivals. Finally Section 6 concludes the paper.