Keywords

1 Introduction

Since the last few decades, stochastic search techniques gather the attention of many researchers, scientist, and academicians to solve larger-scale and complex optimization problems arising in the domain of engineering, science, and management. The advantage of such techniques over traditional techniques is their simplicity and easy to implement without requiring the derivation of the objective function and constraints. These techniques require only auxiliary knowledge about the problem.

The stochastic techniques are formulated by inspiring from the natural and social behavior of species. Some of the stochastic techniques are evolutionary programming (EP) [1], genetic algorithms (GA) [2], evolution strategies (ES) [3], particle swarm optimization (PSO) [4], differential evolution (DE) [5], bacterial foraging optimization algorithm (BFOA) [6], artificial bee colony algorithm (ABC) [7, 8], and ant colony optimization (ACO) [9].

Following the same trend, Eusuff and Lansey [10] proposed SFLA, based on evolution of memeplexes. A detailed note is given in Sect. 2. Having the advantage of both PSO and mixing of the information (taken from GA), SFLA has also proved its efficacy and ability in discovering global optimal solutions to several combinatorial optimization problems [10]. In this paper, we have a proposed a penalty-guided SFLA to solve constrained optimization problems.

The rest of the paper is structured as follows: Sect. 2 describes the process of handling constraints. Section 3 briefs the basic SFLA followed by Sect. 4, which briefs the proposal. Optimal selection of processes is described in Sect. 5, and experimental setup and simulated results are defined in Sect. 6. Finally, the conclusions drawn from the study are presented in Sect. 7.

2 Constraints Handling Process

Handling of the constraint in solving constraints optimization problems is an important and key issue. To find the feasible solution for a problem with the presence of equalities and inequalities in constraints, optimization problem is not an easy task. Many techniques have been proposed to handle such constraints. Penalty functions are one of the well-known approaches to handle constraints. Penalty functions, in spite of their popularity, have certain limitations like there are too many parameters to be adjusted. It is too tough to identify or fix the parameter values in order to balance the penalty and objective functions. Further, the search process is comparatively slow, and there is no assurance of attaining the global optimal solution. Deb [11] modified these algorithms to overcome this limitation by giving the concept of parameter-free penalty functions, i.e., one attempt to solve an unrestrained minimization problem in a search space S using a modified objective function F such as

$$ F(x) = \left\{ {\begin{array}{*{20}l} {f(x)} \hfill & {{\text{if}}\;x \in S} \hfill \\ {f_{\text{w}} + \sum\limits_{z = 1}^{p + q} {g_{z} (x)} } \hfill & {{\text{if}}\;x \notin S} \hfill \\ \end{array} } \right. $$
(1)

where x are solutions obtained by approaches, f w is the worst feasible solution in the population, p and q are the number of equality and inequality constraints, S is the set of feasible solutions, and g z is the set of constraints.

3 Overview of SFLA

SLFA is a stochastic search algorithm based on evolution of memeplexes. In essence, SLFA contains the element of both the local search method of PSO and the concept of mixing information of the shuffled complex evolution. SFLA has also proved its efficacy in finding global solutions to several combinatorial optimization problems [10]. In SFLA, a set of frogs represents the population of possible solutions, which is partitioned into subsets called memeplexes. Different subsets are having frogs from different cultures, each frog carries out a local search, and the position of the worst frog is modified or updated so that the frogs can move toward optimization. When each subset evolves through the fixed number of generations or memetic evolution steps, the ideas hold by the frogs within the subset are passed among subsets through shuffling process. This process of local search and shuffling of information continues until the termination criterion is satisfied.

There are four steps in SFLA:

  1. A.

    Initialization Process

    The initialization of a set of frogs (solutions) is similar to initialization process of other stochastic techniques, i.e., using Eq. (2). The population of frogs (P) be represented by X i  = (x i1, x i2, …, x iS ), and then, position of each frog is generated by

    $$ x_{ij} = {\text{lb}}_{j} + {\text{rand}}(0,1) \times ({\text{ub}}_{j} - {\text{lb}}_{j} ) $$
    (2)

    for i = 1, 2, …, P (set of frogs); j = 1, 2, …, S (S-dimensional vector) and lb j and ub j are the lower and upper bounds, respectively, for the dimension j.

  2. B.

    Sorting and Division Process

    The frogs, based on their fitness evaluations, are sorted in descending order. Then, the sorted population of P frogs is distributed into m subsets (memeplexes), and each subset holds n frogs such that P = m × n. The distribution is done such that the frog with maximum fitness value will go into subset first, accordingly the next frog into second subset, and so on. Then, X b (best) and X w (worst) individuals in each subset are determined.

  3. C.

    Local Search Process

    Worst individual position is improved using Eqs. (3) and (4):

    $$ D_{i} = {\text{rand}}(0,1) \times (X_{\text{b}} - X_{\text{w}} ) $$
    (3)
    $$ X_{\text{w}} = X_{\text{w}} + D_{i} ;\quad - D_{\hbox{max} } \le D_{i} \le D_{\hbox{max} } $$
    (4)

    where i = 1, 2, …, N gen; D is the movement of a frog, whereas D max represents the maximum permissible movement of a frog in feasible domain; N gen is maximum generation of evolution in each subset. The old frog is replaced if the evolution produces the better solution, or else X b is replaced by X g (optimal solution). If no improvement is observed, then a random frog is generated and replaces the old frog. This process of evolution continues till the termination criterion met.

  4. D.

    Shuffling Process

    The frogs are again shuffled and sorted to complete the round of evolution.

    Again follow the same four steps until the termination condition is met.

4 Accelerated-SFLA

Each frog in its memeplex explores the solution space locally, and then, all the memeplexes are shuffled and again divided into new subset of memeplexes. This information exchanging between memeplexes results in optimal search. As it can be analyzed from Eq. (3), when the difference between the position of the best frog (X b) and the worst frog (X w) decreases, the perturbation decreases on the position of the worst frog.

Thus, the search process might stagnate and lead to premature convergence. To avoid such incident, we have modified the local searching process in SFLA.

Searching mechanism for the worst frog is accelerated by embedding scalar factor component in improving the position of the worst frog. The modified equation is given below:

$$ D_{i} = {\text{rand}}(0,1) \times {\text{SF}}(X_{\text{b}} - X_{\text{w}} ) $$
(5)

SF is a scaling factor that controls the amplification or length of exploration of (X b − X w) vector. SF is computed using golden section search [12] and is given in Fig. 1. Two intermediate points SF 1 i and SF 2 i are generated using Eqs. (6) and (7). \( \frac{1 + \sqrt 5 }{2} \) is the golden ratio. The fitness values of f(SF 1 i ) and f(SF 2 i ) are evaluated and compared. If the fitness of f(SF 1 i ) < f(SF 2 i ), then α = SF 1 i .

Fig. 1
figure 1

SF computation

Full size image

If the resulting value falls outside the acceptable range for parameter j, it is set to the corresponding extreme value in that range. The pseudo-code of Accelerated-SFLA is given below:

  • Begin:

    • Initialize the random population of frogs P [using Eq. (2)];

    • Evaluate the fitness of each frog [using Eq. (1)];

    • Sort the population of frogs (P) based on their fitness function value;

    • Distribute the population of frogs (P) into m memeplexes;

  • For each m;

    • X b (best frog) and X w (worst frog) are identified;

    • Update the position of the worst frog using Eqs. (5) and (4);

    • Repeat until the fix number of iterations;

  • End;

    • Evolved memeplexes are combined;

    • Evaluate fitness using Eq. (1) and arrange the population of frogs (based on their fitness value) in descending order.

    • Repeat till the termination criterion is true;

  • End;

Impact of the proposal: This process widens the searching area and balances local and global searching capabilities. Initially, it explores and then converges toward the optimal solutions with the process of combination and shuffling.

5 Optimal Selection of Processes

This problem has been taken from Floudas [13]. There are three processes (P 1, P 2, and P 3) in a company (Fig. 2) that are used to produce a chemical C. Process 1 uses B as a raw material to produce C. However, B can be either produced via two processes (P 2 or P 3), or purchased from other producer. Chemical A is used as a raw material in processes P 2 and P 3. The related data with specifications (nonlinear I/O relationship) are presented in Table 1.

Fig. 2
figure 2

Processes to produce a chemical C

Full size image
Table 1 Problem data
Full size table

The objective of the problem is to select the appropriate processes (based on their level of production) to maximize the profit.

Processes P 1 and P 2 consume A 2 and A 3 amounts of chemical A. As a result, P 1 and P 2 produce B 2 and B 3 amounts of B. BP is the quantity of B purchased from some external entity. P 1 produces C 1 amount of C. The existence of the three processes is defined by 0–1 variables (Y 1, Y 2, and Y 3).

$$ {\text{Max}}\;{\text{Profit}}\;F = 11C_{1} - 3.5Y_{1} - Y_{2} - B_{2} - 1.5Y_{3} - 1.2B_{3} - 7BP - 1.8A_{2} - 1.8A_{3} $$

w.r.t. the constraints:

  • Conversion

    \( \begin{aligned} C_{1} & = 0.9B_{1} \\ B_{2} & = { \ln }(1 + A_{2} ) \\ B_{3} & = 1.2\ln (1 + A_{3} ) \\ \end{aligned} \)

  • Mass balance for B

    \( B_{1} = B_{2} + B_{3} + BP \)

The applied limits and specifications are as follows:

  • Condition for non-negativity continuous variables

    \( A_{2} ,A_{3} ,B_{1} ,B_{2} ,B_{3} ,C_{1} \ge 0 \)

  • Integer constraints:

    \( Y_{1} ,Y_{2} ,Y_{3} = 0 \;{\text{or}}\; 1 \)

  • Maximum demand for C

    \( C_{1} \le 1 \)

  • Plant capacity limit

    \( \begin{aligned} B_{2} & \le 4Y_{2} \\ B_{3} & \le 5Y_{3} \\ C_{1} & \le 2Y_{1} \\ \end{aligned} \)

Finally, for the objective function, the terms for the profit PR expressed in $103/h are given as follows:

  1. 1.

    Revenue generated from sales of product \( C = 13C \)

  2. 2.

    Expense incurred in purchasing chemical \( B = 7BP \)

  3. 3.

    Expense incurred in purchasing chemical A:

    \( 1.8A_{2} + 1.8A_{3} A + 1.8A_{2} + 1.8A_{3} \)

  4. 4.

    Preset (fixed) cost for the P 1, P 2, and P 3:

    \( 3.5Y_{1} + 2C_{1} + Y_{2} + B_{2} + 1.5Y_{3} + 1.2B_{3} \)

6 Experimental Setup and Results

The above-stated problem is simulated on Deb C++ with the following parameters.

  • All experiments were repeated 25 times independently with 24,000 objective function evaluations for each problem.

  • Population size of frogs is fixed to 100.

  • Number of function evaluations (NFEs) fixed to 5,000.

  • m (number of memeplexes) = 10.

  • n (number of iterations evolves in each memeplexes) = 10.

  • N gen = 10.

  • D max = 100 % of variable range.

  • Binary variables and integers are handled by rounding of the decision variables to nearest integer [14].

The optimal solution for the problem of selecting process is achieved by both SFLA and Accelerated-SFLA with 100 % success rate (both are able to reach the optimum solution in all 25 trial runs). The difference lies in the time and NFE taken to achieve the optimal values. Accelerated-SFLA took only 1.5 s and 1,095 NFEs, whereas SFLA took 2 s and 1,978 NFEs to reach the optimal solution. The simulated results show that the proposal is 44 % faster than SFLA. The results for the optimal selection of processes are as follows:

Y 1 = Y 3 = 1 and Y 2 = 0; hence, processes P 1 and P 3 are selected to maximum profit with the following details:

A 2 = 0.0000; A 3 = 1.5201; B 1 = 1.1110; B 2 = 0.0000; B 3 = 1.1114; BP = 0.0000; C 1 = 1.0000. The subtotal of fix cost will be 5 (Y 1 + Y 3), operating cost will be 3.333 (C 1 + B 2 + B 3), and the raw material cost is 2.744 (A 2 + A 3 + BP); hence, the total cost will be 11.077, and the net profit will be F = 1.923 (total revenue − total cost). The success rate of both the algorithms is 100 %.

7 Conclusions

The paper proposes Accelerated-SFLA variant of SFLA, a memetic algorithm based on the improvement done in shuffled leap frog algorithm. A simple modification is proposed in SFLA. In the proposal, scaling factor based on golden section in searching process of SFLA is introduced. The aim of the study is to accelerate the convergence speed of SFLA and preventing it from trapping into local optima. This kind of hybridization seems to be very efficient in solving computational optimization problems. We have tested the efficacy of the proposal on an optimal selection of processes in chemical manufacturing company.

In the future, we will try to further investigate the proposal and enhance the employment of the proposal on large-scale optimization problems.