Mixed-Integer Constrained Optimization Based on Memetic Algorithm

Abstract

Evolutionary algorithms (EAs) are population-based global search methods. They have been successfully applied to many complex optimization problems. However, EAs are frequently incapable of finding a convergence solution in default of local search mechanisms. Memetic Algorithms (MAs) are hybrid EAs that combine genetic operators with local search methods. With global exploration and local exploitation in search space, MAs are capable of obtaining more high-quality solutions. On the other hand, mixed-integer hybrid differential evolution (MIHDE), as an EA-based search algorithm, has been successfully applied to many mixed-integer optimization problems. In this paper, a memetic algorithm based on MIHDE is developed for solving mixed-integer optimization problems. However, most of real-world mixed-integer optimization problems frequently consist of equality and/or inequality constraints. In order to effectively handle constraints, an evolutionary Lagrange method based on memetic algorithm is developed to solve the mixed-integer constrained optimization problems. The proposed algorithm is implemented and tested on two benchmark mixed-integer constrained optimization problems. Experimental results show that the proposed algorithm can find better optimal solutions compared with some other search algorithms. Therefore, it implies that the proposed memetic algorithm is a good approach to mixed-integer optimization problems.

1

Introduction

Evolutionary algorithms (EAs) are powerful search algorithms based on the mechanism of natural selection [1, 2]. Unlike conventional search approaches, they simultaneously consider many points in the search space so as to increase the chance of global convergence Therefore, EAs exhibit a good potential of global exploration. In the past decade, EAs have been successfully applied to many complex continuous optimization problems such as highly nonlinear, non-differentiable and multi-modal optimization problems [1-6]. However, EAs are frequently incapable of finding a precise solution in default of local search mechanisms.

In recent years, memetic algorithms (MAs) have been receiving increasing attention from the evolutionary computation community. MAs are inspired by Darwinian’s principles of natural evolution and Dawkins’ notion of a memes [7]. MAs are hybrid EAs that combine genetic operators with local search methods. The local search methods are used to perform the local refinement procedures [8]. Therefore, they can be regarded as the integration between population-based EAs and local search methods. With global exploration and local exploitation in search space, MAs are capable of obtaining more high-quality solutions. MAs have shown to be promising for solving optimization problems in a wide range of applications [8-11].

In real world, many optimization problems frequently contain integer variables in addition to continuous variables. For example, the standard formats of steel thickness must be chosen as integers in mechanical design. This kind of optimization problems involved continuous and integer variables are generally called mixed-integer optimization problems. Mixed-Integer Hybrid Differential Evolution (MIHDE) [12] is a mixed-integer EA-based search algorithm. A mixed coding is introduced in MIHDE to implement the evolutionary process of continuous and integer variables. In order to enhance the global exploration, the migration is devised to maintain the population diversity in MIHDE. The MIHDE has been successfully applied to many complex mixed-integer optimization problems [12-14].

In this paper, a memetic algoritm based on MIHDE, called Memetic MIHDE, is developed to deal with mixed-integer optimization problems. The Memetic MIHDE incorporates a local search method called Nelder-Mead simplex method [15] into MIHDE to enhance the local exploitation. The Nelder-Mead method is one of the most popular derivative-free nonlinear optimization methods. Instead of using the derivative information of the function to be minimized, through reflection, expansion, contraction and shrinkage search steps for a simplex, the Nelder-Mead method can maintain a non-degenerate simplex to find a local optimum.

In addition, these mixed-integer optimization problems are often coupled with nonlinear constraints so that they are more intractable because the feasible solution space is greatly suppressed by the constraints. Several methods based on EAs have been developed to solve mixed-integer optimization problems [16-18]. However, these methods are not well posed for various mixed-integer problems due to lack of a good constraint-handling mechanism. Hence, in order to tackle mixed-integer constrained optimization problems effectively, it is worthwhile to develop an efficient evolutionary mixed-integer constrained optimization method. In this paper, we can combine the Memetic MIHDE algorithm with Lagrange method to construct an evolutionary Lagrange method to deal with mixed-integer constrained optimization problems. Finally, the proposed algorithm is implemented and tested on two benchmark mixed-integer optimization problems [19]. Experimental results show that the proposed algorithm can find better optimal solutions compared with the other search algorithms. This demonstrates that the proposed memetic algorithm is a good approach to mixed-integer optimization problems.

The remainder of this paper is organized as follows. Section 2 presents an overview of Memetic MIHDE algorithm. In Section 3, The formulation of evolutionary Lagrange method based on Memetic MIHDE is developed. Computational results for mixed-integer constrained optimization problems are provided in Section 4. Finally, conclusions are drawn in Section 5.

2

Memetic MIHDE algorithm

First, consider a mixed-integer optimization problem as follows:

where x represents an n_C-dimensional vector of real-valued variables, y is an n_I-dimensional vector of integer-valued variables, and (xL,yL) and (xU,yU) are the lower and upper bounds of the corresponding decision vectors.

Table 1 shows the basic operations of conventional evolutionary algorithms and Memetic MIHDE. Each operation of Memetic MIHDE is discussed as follows:

Table 1.

Basic of evolutionary algorithmsand Memetic MIHDE.

Evolutionary Algorithms	Memetic MIHDE
1. Initialization 2. Mutation 3. Crossover 4. Evaluation and Selection 5. Repeat step 2 to 4 until stop criterion is satisfied	1. Initialization 2. Mutation 3. Crossover 4. Evaluation and Selection 5. Migration if necessary 6. Local Search 7. Repeat step 2 to 6 until stop criterion is satisfied

1)

Initialization

The Memetic MIHDE algorithm uses N_p decision vectors ziG=(xG,yG)i, i = 1,...,N_p to denote a population of N_p individuals in the G-th generation. The decision vector (chromosome), (x,y)_i, is represented as (x1i,…,xji,…,xnCi,y1i,…,ynIi). The decision variables (genes), x_ji and y_ji, are directly coded as real-valued and integer-valued numbers. The initialization process generates N_pdecision vectors (x, y)_i randomly, and should try to cover the entire search space uniformly as in the form:

where ρi=Diag(ρi,1,ρi,2,…,ρi,nC+nI) is a diagonal matrix, the diagonal elements (ρi,1,ρi,2,…,ρi,nC+nI) are random numbers in the range [0,1], the other elements are zero, and the rounding operator a =ρi(xU-xL), b =ρi(yU-yL)} in (2) is defined as (a, INT[b]) in which the operator INT[b] is expressed as the nearest integer-valued vector to the real-valued vector b.

2)

Mutation

The i-th mutant individual (uG,vG)_i is obtained by the difference for two random individuals as expressed in the form: The i-th mutant individual (uG,vG)_i is obtained by the difference for two random individuals as expressed in the form:

where random indices k, l∈1,...,N_p are mutually different. The operator INT INT[b=ρm(ykG-ylG)] in (3) is to find the nearest integer vector to the real vector b. The mutation factor ρ_m is a real random number between zero and one. This factor is used to control the search step among the direction of the differential variation (xG,yG)_k − (xG,yG)_l.

3)

Crossover

In crossover operation, each gene of the i-th individual is reproduced from the mutant vector (uG,vG)i=(u1iG,u2iG,…,unCiG,v1iG,v2iG,…,vnIiG) and the individual (xG,yG)i=(x1iG,x2iG,…,xnCiG,y1iG,y2iG,…,ynIiG) as follows:

where the crossover factor ρ_c ∈[0 1] is a constant and the value can be specified by the user.

4)

Evaluation and selection

The operation includes two evaluation phases. The first phase is performed to produce the new population in the next generation as (6). The second phase is used to obtain the best individual as (7).

where (x^G+1,y^G+1)_b is the best individual with the smallest objective function value.

5)

Migration

In order to increase the exploration of the search space, a migration operation is introduced to generate a diversified population. Based on the best individual (xG+1,yG+1)b=(x1bG+1,x2bG+1,…,xnCbG+1,y1bG+1,y2bG+1,…,ynIbG+1), the j-th gene of the i-th individual can be diversified by the following equations:

where ρ₁ and ρ₂ are the random numbers in the range [0,1].

The migration operation in Memetic MIHDE is performed only if a measure for the population diversity is not satisfied, that is when most of individuals have clustered together, the migration has to be actuated to make some improvements. In this paper, we propose a measure called the population diversity degree η to check whether the migration operation should be performed. In order to define the measure, we first introduce the following gene diversity index for each real-valued gene yjiG+1 and for each integer-valued gene ykiG+1,

where dx_ji and dy_ji are the gene diversity indices and ε₂ ∈[0,1] is a tolerance for real-valued gene provided by the user. According to (10) and (11), we assign the j-th gene diversity index for the i-th individual to zero if this gene clusters to the best gene. We now define the population diversity degree η as a ratio of total diversified genes in the population. From (10) and (11) we have the population diversity degree as

From equations (10), (11) and (12), the value of η is in the range [0, 1]. Consequently, we can set a tolerance for population diversity, ε₁ ∈[0,1], to assess whether the migration should be actuated. If η is smaller than ε₁, then Memetic MIHDE performs the migration to generate a new population to escape a local solution. Contrary, if η is not less than ε₁, then Memetic MIHDE suspends the migration operation to keep a constant search direction to a target solution.

6)

Local search

The local search procedure of Nelder-Mead method [15] is used after migration operation at each generation. The Nelder-Mead method is a nonlinear programming approach in continuous domain. In mixed-integer programming, a simplex is devised to search for the optimal solution with respect to continuous decision variables by fixing the values of integer decision variables of each candidate solution. Therefore, the local search procedure refines the candidate solution to approach a local optimum. As a result, The Memetic MIHDE algorithm can enhance the global exploration and local exploitation for the mixed-integer optimization problems.

3

Evolutionary Lagrange method based on Memetic MIHDE algorithm

In order to solve mixed-integer constrained optimization problems, a Lagrange method based on memetic MIHDE is developed to handle the constraints. First, let us consider a mixed-integer constrained optimization problem as follows:

where x represents an n_C-dimensional vector of continuous variables, y is a n_I-dimensional vector of integer variables, and h_j(x,y) and g_j(x,y) stand for the equality and inequality constraints respectively. To abbreviate these expressions, a compact notation z = (x,y) is used in the following discussions, and the problem is referred to as primal problem.

An augmented Lagrange function corresponding to the primal problem is defined by:

where α_k and β_k are positive penalty parameters, the bracket operation is denoted as ’ 〈g〉₊ = max{g,0}, and v=(v1,…,vme) and υ=(υ1,…,υmi)≥0 are the corresponding Lagrange multipliers.

In nonlinear programming, the saddle point theorem [20] states that, if a point is a saddle point of the augmented Lagrange function associated with the primal problem, then the point is the solution of the primal problem. Accordingly, the saddle point theorem can be used to solve mixed-integer constrained optimization problems.

If (z*,ν^*,υ^*) is a saddle point of the augmented Lagrange function l_a(z, ν,υ), then (z*,ν^*,υ^*) satisfies the following condition:

The saddle point can be obtained by minimizing L_a(z,ν^*,υ^*) with the optimal Lagrange multipliers (_ν^*,_υ^*) as a fixed parameter vector. However, the difficulty of this minimization is that it requires the knowledge of (_ν^*,_υ^*) previously. In general, the optimal values of Lagrange multipliers are unknown a priori. The duality theorem can be employed to overcome this difficulty.

According to the duality theorem, the primal problem (13) can be transformed into a dual problem as follows:

where the dual function H(ν,υ) is denoted as

and the set Ξ = {(ν,υ)|H(ν,υ) exists, and υ ≥ 0}. Based on (16) and (17), the duality theorem can be expressed by the following duality relationship statements:

• 1)

  z* = (x^*,y^*) is a minimizer of the primal problem (13).

• 2)

  (ν*, υ*) withυ* ≥ 0 is a maximizer of the dual problem (16).

• 3)

  H(ν*, υ*) = f(z*). That is, the saddle point of the augmented Lagrange function (14) is the optimal solution of the primal problem (13).

According to the duality relations, we can construct an evolutionary max-min algorithm to solve mixed-integer constrained optimization problems. The evolutionary max-min algorithm includes two phases as stated in Table 2. In the first phase (step 2 in Table 2), the Memetic MIHDE is used to minimize the augmented Lagrange function with multipliers fixed. In the second phase (step 3 in Table 2), the Lagrange multipliers are updated to ascend the value of the dual function toward obtaining maximization of the dual problem.

Table 2.

Evolutionary max-min algorithm.

Step 1.	Set initial iteration index: l = 0.Set initial multipliers: vkl=0 for k = 1,...,me, υkl=0 for k = 1,...,mi.Set penalty parameters: αk > 0 for k = 1,...,me, βk > 0 for k = 1,...,mi.
Step 2.	Use Memetic MIHDE to minimize La (z,νl,υl).Let zbl=(xl,yl)b be a minimum solution to the function La (z, νl, υl).
Step 3.	Update the multipliers as follows:vkl+1=hk(zbl)+vklυkl+1=gk(zbl)+υkl+
Step 4.	Update αk and βk if necessary.
Step 5.	Stop if stopping criterion is satisfied.Otherwise, let l = l +1 and repeat Steps 2 to 4.

As far as the evolutionary computation is concerned, the evolutionary max-min procedure may increase many function evaluations and affect the convergence rate. However, in order to find the exact solution, it is necessary and inevitable unless using other special approaches, e.g., sequential quadratic programming (SQP) [21], to continuously update the Lagrange multipliers. Unfortunately, SQP is not applicable for the non-differentiable mixed-integer constrained optimization problems. The update of the Lagrange multipliers is based on the exact or approximate minimum of the augmented Lagrange function with multipliers fixed. As presented by Arora et al.[21], an exact or approximate minimum is necessary in order to ensure proper shift of the Lagrange function towards the required solution. With a rough minimum, the shift of the Lagrange function may be far away from the required solution leading to obtain a nonexistent dual function so that the duality theorem shall be disobeyed. The saddle point is accordingly unable to be obtained using the rough shift. Therefore, in order to obtain an exact or approximate minimum, sufficient iterations for Memetic MIHDE minimization phase are necessary for the evolutionary max-min algorithm.

In addition, constant penalty parameters are used in the max-min algorithm. These parameters are suited for solving linear constrained problems because the contours of L_a(z,ν,υ) do not change shape from generation to generation. However, if the constraints are highly nonlinear, the contours of L_a(z,ν,υ) still highly depend on the values of penalty parameters. This fact indicates that the evolutionary max-min algorithm in Table 2 may be sensitive to the setting values of penalty parameters. Small penalty parameters, for example, might lead to an infeasible solution. On the other hand, large penalty parameters might cause the penalty functions to be ill conditioned. In order to increase the possibility of global convergence, a self-adaptation scheme for the penalty parameters is embedded into the evolutionary max-min algorithm as shown in Table 3. The evolutionary max-min algorithm with self-adaptation scheme is called Memetic MIHDE MIHDE-Adaptive MaxMin (Memetic MIHDE-AMM) algorithm. It is extended from Powell‘s multiplier algorithm [22] towards improving the extent of the constraint violations.

Table 3.

Evolutionary max-min algorithm with adaptive penalty parameters.

Step 1.	Set initial iteration: l = 0.Set initial multipliers: vkl=0 for k = 1,...,me, υkl=0 for k = 1,...,mi.Set penalty parameters: αK > 0 for k = 1,..., me, βk > 0 for k = 1,...,mi. Set tolerance for the maximum constraint violation, εK (e.g. εK = 10^32).
Step 2.	Use Memetic MIHDE to solve La (z, νl,υl).Let zbl=(xl,yl)b be a minimum solution to the function La (z,νl, υl).
Step 3.	Evaluate the maximum constraint violation asεˆK=maxmaxkhk,maxkgk+υk+-υk,and establish the following sets for the equality and inequality constraints whose violation is not improved by the factor ω1:IE={k:|hk|>εK/ω1,k=1,…,me}II={k:|[〈gk+υk〉+-υk]|>εK/ω1,k=1,…,mi}
Step 4.	If εˆK≥εK, let αk=ω2αk,vkl+1=vkl/ω2 forall k∈IE, and βk=ω2βk,υkl+1=υkl/ω2 forall k∈II. Go to Step 7.Otherwise, go to Step 5.
Step 5.	Update the multipliers as follows:vkl+1=hk(zbl)+vklυkl+1=gk(zbl)+υkl+
Step 6.	If εˆK≤εK/ω1, let εK=εˆK and go to Step 7.Otherwise, let αk=ω2αk,vkl+1=vkl+1/ω2 for all βk=ω2βk,υkl+1=υkl/ω2 for all k∈II, and εK=εˆK. Go to Step 7.
Step 7.	Stop if stopping criterion is satisfied.Otherwise, let l = l +1 and repeat Steps 2 to 6.

In Memetic MIHDE-AMM algorithm, a scalar factor ω₁ is used to enforce an improvement for the constraint violations. The other scalar factor ω₂ is used to increase the values of penalty parameters. For implementation, we used ω₁ = 4 and ω₂ = 10 as suggested in Powell’s algorithm [22]. Owing to using the self-adaptation scheme, the initial penalty parameter values do not affect the final search result except for the convergence rate. This implies that the algorithm is insensitive to the penalty parameters. Steps 3, 4 and 6 in Table 3 are used to improve the constraint violation and update the penalty parameters. In step 4, if the maximum constraint violation does not improve (i.e. εK=εˆK), for those unimproved constraints (i.e. k∈I_E ⌣I_I) the associated penalty parameters can be increased by the factor ω₂ and the associated multipliers can be decreased by the same factor. In step 5, if the maximum constraint violation improves (i.e. εˆK<εK), the penalty parameters keep unchanged and the multipliers are updated. In step 6, if the maximum constraint violation does not be improved by the factor ω₁, for those unimproved constraints the associated penalty parameters can be increased by the factor ω₂ and the associated multipliers can be decreased by the same factor. And then the new maximum constraint violation εˆK replaces the previous maximum constraint violation ε_K. Because the penalty parameters are automatically updated, the maximum constraint violation εˆK will keep descending until all of the constraints are satisfied so that finally the Memetic MIHDE-AMM can converge to the saddle point of the augmented Lagrange function.

4

Experimental examples

Two typical mixed-integer optimization problem presented by Sandgren [19] are used to test the Memetic MIHDE and Memetic MIHDE-AMM algorithm. For implementation, the setting parameters used in Memetic MIHDE are listed as follows: population size n_P =[sp/]5,crossover factor ρ_c = 0.5, and two tolerances ε₁ = ε_{2 =} 0.1. In order to illustrate their performance of global search, the other three algorithms, IDCNLP, SA and MVEP [18, 23, 24], are chosen for comparison.

Problem 1:

The mechanical optimization problem is an optimal design problem of compound gear train as shown in Figure 1. It is desired to produce a gear ratio as possible to 1/6.931. For each gear, the number of teeth must be between 12 and 60. The design variables are the numbers of teeth, which must be integers.

Figure 1.

Gear train design.

The optimization problem is formulated as:

subject to 12 ≤ yi ≤ 60, i = 1,...,4.

Computational results are shown in Table 4. The objective value obtained by Memetic MIHDE is lowest. This indicates that the optimal solution obtained by Memetic MIHDE is better than those obtained by IDCNLP, SA and MVEP. Therefore, the Memetic MIHDE algorithm is a good approach to global optimization.

Table 4.

Computational results with different solvingalgorithms.

Item	IDCNLP	SA	MVEP	Memetic MIHDE
y1	14	30	30	19
y2	29	15	15	16
y3	47	52	52	43
y4	59	60	60	49
f(y)	4.5×10^-6	2.36×10^-9	2.36×10^-9	2.70×10^-12

Problem 2:

The mechanical optimization problem is an optimal design problem of pressure vessel as shown in Figure 2. The design variables are the dimensions required for the specifications of the vessel, i.e. (x,y) = (x₁,x₂,y₁, y₂).

Figure 2.

Pressure vessel design.

The objective function is the combined costs of material, forming and welding of the pressure vessel. The constraints are set in accordance with the respective ASME codes. The mixed-integer constrained optimization problem is expressed as:

Computational results are shown in Table 5. The objective value obtained by Memetic MIHDE-AMM is lowest and all constraints are satisfied (g_i ≤ 0). This demonstrates that the optimal solution obtained by Memetic MIHDE-AMM is better than those obtained by IDCNLP, SA and MVEP. Therefore, the proposed Memetic MIHDE-AMM algorithm is appropriate for solving mixed-integer constrained optimization problems.

Table 5.

Computational results with different solving algorithms.

Item	IDCNLP	SA	MVEP	Memetic MIHDE-AMM
x1	48.3807	58.2900	51.1958	38.8571
x2	111.7449	43.6930	90.7821	221.4116
y1	18	18	16	12
y2	10	10	10	10
g1	-0.1913	-0.0250	-0.0119	-0.0001
g2	-0.1634	-0.0689	-0.1366	-0.2543
g3	-75.8750	-6.5496	-13584.5631	-1.9921
g4	-128.2551	-196.3070	-149.2179	-18.5884
f	8048.6190	7197.7	7108.6160	6521.9778

5

Conclusions

In this paper, a memetic algorithm, Memetic MIHDE, is developed to solve mixed-integer optimization problems. Combined Memetic MIHDE algorithm with Lagrange method, an evolutionary Lagrange method, Memetic MIHDE-AMM algorithm, can be implemented to deal with mixed-integer constrained optimization problems. Finally, the proposed method is applied to two typical mixed-integer optimization problems. Computational results show the proposed method is superior to the other three solving algorithms in searching global solution. This demonstrates that the proposed evolutionary Lagrange method based on Memetic MIHDE algorithm can effectively solve mixed-integer constrained optimization problems. Therefore, it implies that the proposed memetic algorithm is a good approach to mixed-integer optimization problems.