# A Dynamic Opposite Learning Assisted Grasshopper Optimization Algorithm for the Flexible JobScheduling Problem

Authors: Yi Feng; Mengru Liu; Yuqian Zhang; Jinglin Wang
Journal: Complexity
 (2020)

---

## Abstract

Job shop scheduling problem (JSP) is one of the most difficult optimization problems in manufacturing industry, and flexible job shop scheduling problem (FJSP) is an extension of the classical JSP, which further challenges the algorithm performance. In FJSP, a machine should be selected for each process from a given set, which introduces another decision element within the job path, making FJSP be more difficult than traditional JSP. In this paper, a variant of grasshopper optimization algorithm (GOA) named dynamic opposite learning assisted GOA (DOLGOA) is proposed to solve FJSP. The recently proposed dynamic opposite learning (DOL) strategy adopts the asymmetric search space to improve the exploitation ability of the algorithm and increase the possibility of finding the global optimum. Various popular benchmarks from CEC 2014 and FJSP are used to evaluate the performance of DOLGOA. Numerical results with comparisons of other classic algorithms show that DOLGOA gets obvious improvement for solving global optimization problems and is well-performed when solving FJSP.


---

## Body

## 1. Introduction

Global optimization has become an important research topic in scientific research and engineering applications. Neural network training [1, 2], path planning [3, 4], industrial design [5, 6], and many other complex problems hope to use optimization algorithms to achieve optimum solutions. Global optimization algorithms mainly consist of two classes: deterministic mathematical programming method [7–10] and metaheuristic algorithms (MAs) [11–14]. MAs have simple structure and strong adaptability, which is very advantageous in solving complex problems [15, 16]. In recent decades, inspired by nature, MAs with many different characteristics have been proposed by researchers. Glover et al. proposed tabu search (TS) [17] by simulating the feature that human has memory function. Simulated annealing algorithm (SA) [18] was proposed by simulating the industrial annealing process of high temperature object. Based on Darwin’s evolution theory and Mendel’s genetics, Holland and John proposed genetic algorithm (GA) [19] for the first time in the 1970s. Dorigo and Sttzle proposed ant colony optimization (ACO) [20] based on the study of ant colony behavior. Inspired by the foraging behavior of birds, American psychologist Kennedy and electrical engineer Eberhart proposed particle swarm optimization (PSO) in 1995 [13]. In addition to these classical algorithms, some new MAs have been proposed in recent years, such as grey wolf optimizer (GWO) [21], moth flame optimization (MFO) [22], firefly algorithm (FA) [23], teaching-learning-based optimization (TLBO) [24, 25] competitive swarm optimization (CSO) [26, 27], dragonfly algorithm (DA) [28], whale optimization algorithm (WOA) [29], and pigeon-inspired optimization [30].The grasshopper optimization algorithm (GOA) is a recently proposed new MA. It was inspired by the foraging behavior of grasshopper and proposed by Saremi et al. in 2017 [31]. The algorithm has simple principle and distinctive features and demonstrated good performance in solving optimization problems. As soon as the algorithm was proposed, scholars applied it to different optimization problems. Mirjalili et al. applied GOA to the multiobjective optimization problem in 2017 [32]. Tumuluru and Ravi used GOA to update the weight of the deep confidence neural network and applied it to the classification of cancer in 2017 [33]. Aljarah et al. used GOA for feature selection and support vector machine optimization for solving feature selection task in 2018 [34].In addition to the original GOA, many variants have emerged for the improvements of the algorithm performance. In 2017, Wu et al. proposed an adaptive grasshopper optimization algorithm (AGOA) and applied it to the UAV tracking trajectory optimization problem [35]. In 2018, Ewees et al. proposed an improved version of the grasshopper optimization algorithm based on the opposition-based learning strategy called OBLGOA for solving benchmark optimization functions and engineering problems [36]. Although the existing method has greatly improved GOA, there is still a large probability of falling into local optimum. This paper adopts the DOL strategy proposed by Xu et al. [37] to improve the optimization performance of GOA. The search space of DOL strategy is asymmetric and dynamic, which greatly improves the probability of GOA to obtain the optimal solution and avoids it falling into local optimum to some extent.The job shop scheduling problem (JSP) [38] is a famous NP hard problem in the discrete manufacturing system, and flexible job shop scheduling problem (FJSP) is an extension of the classical JSP [39, 40]. In FJSP, there may be more than one machine for the same process, so two subproblems should be considered when solving FJSP: the machine selection (MS) and the operations sequencing (OS) [41]. Although there is only one more step than JSP to assign a series of optional machines to a specified process, it is much more difficult to get optimal solution to the FJSP in polynomial time. Intelligent optimization algorithm can obtain the approximate solution with better quality in a short time, due to which an increasing number of intelligent optimization algorithms are used to solve FJSP. The literature shows that many swarm intelligent optimization algorithms such as GA [42–44], TS [45, 46], and artificial bee colony algorithm (ABC) [47, 48] have been successfully applied to FJSP and obtained good results. Though numerous approaches have been proposed for solving the given problem, the complex FJSP problem calls for more competitive solvers for solving the problem. In order to further test the performance of DOLGOA, we use DOLGOA algorithm to solve FJSP.The main contribution of this paper is as follows:(1)
An encoding scheme FJSP is discussed in detail, and the mathematical model and constrains are given(2)
A new variant of GOA by adopting a dynamic opposite learning strategy is proposed to improve the exploitation ability of GOA and increase the possibility of finding the global optimum(3)
Various popular benchmarks from CEC 2014 and FJSP are used to evaluate the performance of DOLGOA by comparing with other classic algorithmsIn this paper, we introduce the background in Section1, then the problem description of FJSP is discussed in Section 2, and followed by the GOA algorithm and DOL strategy which are demonstrated in Section 3. Then, the DOLGOA is proposed in Section 4. The experiment and discussion are given in Section 5 with the comparison of other algorithms. Finally, Section 6 concludes the paper.


## 2. Problem Formulation

In the FJSP, we assume that there areN jobs to be processed and M usable machines in a workshop, where each job contains multiple operations, and each operation can be processed by a series of specified machines. Each machine can only serve one process at a time, the purpose of optimization is to arrange the machines according to the process requirements to minimize the maximal completion time Cmax. In order to express the problem more clearly, we use notations as follows:i: the ith jobj: the jth operation of the corresponding jobk: the kth machinepi: the total number of operations for job iBijk: beginning time of operation j of job i on machine kPijk: processing time of operation j of job i on machine kCijk: completion time of operation j of job i on machine kCi: completion time for jobCmax: maximal completion timeObjective function: minimizeCmaxThe constraints of FJSP can be expressed as follows:(i)
All machines are available at time zero, and all jobs can start at time zero:(1)Bijk≥0,Cijk≥0.(ii)
Processing time of each operation on the corresponding machine is definite, and the transmission time is ignored:(2)Ci≥Cij,∀j∈1,pi,Cmax≥Ci,∀i∈1,N.(iii)
Jobs are independent of each other and cannot be inserted or cancelled by force:(3)Sijk+Pijk=Cijk,∑kSijk≥∑kCij−1k.(iv)
Each machine can only process one job at a time:(4)Bik+Pik≤Bi+1k,∀j∈1,pi.(v)
Each operation of a job can only be processed by one machine at a time:(5)Bij+Pij≤Bij+1,∀k∈1,M.


## 3. Algorithm Preliminaries

### 3.1. Grasshopper Optimization Algorithm

GOA optimization algorithm is a featured intelligent optimization algorithm based on population, which is inspired by the foraging behavior of grasshopper population. The grasshoppers’ position constitutes the solution space, and the optimal grasshopper’s position corresponds to the optimal solution. Grasshopper is always moving during the foraging process, so the position is constantly changing. During each iteration, the optimal position will be updated if a better position is found until the iteration termination condition is satisfied.The mathematical model employed to simulate the swarming behavior of grasshoppers is shown as follows:(6)Xi=Si+Gi+Ai,where Xi defines the position of the ith grasshopper, Si is social interaction, Gi is the influence of gravity on the ith grasshopper, and Ai is the influence of wind on the ith grasshopper. However, in order to provide random behavior, the equation can be written as Xi=r1Si+r2Gi+r3Ai, where r1, r2, and r3 is a random number between 0,1:(7)Si=∑j=1,j≠iNsdijdij^,where dij is the distance between the ith and the jth grasshopper, calculated as dij=xj−xi, s is a function to define the strength of social forces, which is shown in equation (8), and dij^=xj−xi/dij is a unit vector from the ith grasshopper to the jth grasshopper.The functions, which defines the strength of social forces, is calculated as follows:(8)sr=fe−r/ı−e−r,where f is the strength of attraction and l is the scale of attraction length.TheG component in equation (6) is calculated as follows:(9)Gi=−geg^,where g is the gravitational constant and eg^ is a unit vector towards the center of Earth.TheA component in equation (6) is calculated as follows:(10)Ai=−uew^,where u is an offset constant and ew^ is the unit vector along the direction of wind.SubstitutingS, G, and A in equation (6), this equation can be expressed as follows:(11)Xi=∑j=1,j≠iNsxj−xixj−xidij−geg^+uew^,where sr=fe−r/l−e−r and N is the number of grasshoppers.However, this mathematical model cannot be used directly to solve the optimization problems mainly because the grasshoppers quickly reach their comfort zone and the swarm does not converge to the specified point. In order to solve the optimization problem, the modified form of this equation is as follows:(12)Xid=c∑j=1,j≠iNcubd−lbd2sxjd−xidxj−xidij+Td^,where ubd is the upper bound of the dth dimension, lbd is the lower bound of the dth dimension, sr=fe−r/l−e−r, Td^ is the value of dth dimension of the target (best solution found so far), and c is a decreasing coefficient of comfort zone, repulsion zone, and attraction zone, as defined in equation (13). Note that S is almost similar to the component S in equation (6). However, we do not consider the gravity (no G component) and assume that the wind direction is always toward a target Td^. According to equation (12), the next position of the grasshopper is determined according to its current position, the position of the target, and the position of all other grasshoppers:(13)c=cmax−lcmax−cminL,where cmax is the maximum value, cmin is the minimum value, l is the current iteration number, and L is the maximum iteration number. In this paper, we take 1 and 0.00001 for cmax and cmin, respectively.


### 3.2. Oppositional-Based Learning (OBL)

Opposition-based learning (OBL) [49] is one of the most successful learning strategies and is widely used in the effective learning phase to enhance the search capability of population-based algorithms. When finding the solution X of a given problem, OBL makes the candidate solution more likely to approach the optimal solution by simultaneously computing the current X and the inverse solution of X.


#### 3.2.1. Opposite Number

X is a real number in [a, b], where a and b are the boundaries of X. XO is the opposite number of X, which can be defined as follows:(14)XO=a+b−X.


#### 3.2.2. Opposite Point

Assume thatX=X1,X2,…,XD is a point in a D-dimensional space, and Xj∈aj,bj, where j = 1 : D and aj and bj are the low and high boundaries of the current population respectively, which change with iteration. A D-dimension opposite point is defined as follows:(15)XjO=aj+bj−Xj,j=1:D.


### 3.3. Dynamic-Opposite Learning (DOL)

On the basis of OBL strategy, many new ideas such as quasi-opposite-based learning (QOBL) [50] and quasi-reflection-based learning (QRBL) [51] are proposed, and the quasi-opposite number in QOBL and the quasi-reflection number in QRBL are both closer to the global optimum than the opposite number in OBL. However, if there is a local optimum in the search space, all strategies including OBL, QOBL, and QRBL tend to converge the search space to the local optimal location. Concerning this problem, a dynamic opposite learning (DOL) strategy is proposed in [37], which can improve the probability of convergence to the global optimum while avoiding falling into the local optimum.In order to avoid the situation of falling into the local optimum in the space from the current number to the opposite number in OBL theory, a random opposite numberXRO was proposed, and XRO=rand∗XO,rand∈0,1. We can see that XRO can be not only between X and XO but also greater or less than X or XO. DOL strategy is formulated by randomly selecting a DOL number XDO between X and XRO. When XRO∈a,b, XDO=X+randXRO−X; otherwise, if XRO exceeds the range of a,b, it is necessary to check whether the number obtained by DOL has a boundary: if X+randXRO−X∈a,b, XDO is equal to X+randXRO−X; otherwise, XDO should be reset as a random number between a and b. Although XRO can enhance the diversity of the search space, the search space may shrink along with the iteration, which will lead to the deterioration of the exploitation capability. In light of this, a positive weighting factor w is used to balance the region and diversity of the search space. The mathematical model of DOL can be described as follows.


#### 3.3.1. Dynamic Opposite Number

X is a real number in [a, b], where a and b are the boundaries of X. The dynamic opposite number XDO can be defined as equation (16), where a and b are the boundaries and rand is a random number between 0 and 1. Moreover, w is a positive weighting factor, and XO is the opposite number defined as equation (14):(16)XDO=X+w∗rand∗rand∗XO−X.


#### 3.3.2. Dynamic Opposite Point

X=X1,X2,…,XD is a point in a D-dimensional space, and Xj∈aj,bj, where j = 1 : D and aj and bj are the low and high boundaries of the current population, respectively, which change with iteration. A D-dimension dynamic opposite point is defined as follows:(17)XjDO=Xj+w∗rand∗XjO−Xj,j=1:D,where rand is a random number between 0 and 1, w is a positive weighting factor, and XjO is the opposite point defined as equation (15).


#### 3.3.3. DOL-Based Optimization

Assume thatX=X1,X2,…,XD is a point in a D-dimensional space, and Xj∈aj,bj, where j = 1 : D and aj and bj are the low and high boundaries of the current population, respectively, which change with iteration. Dynamic opposite point XDO=X1DO,X2DO,…,XDDO is defined according to equation (17) and is updated by X in each generation. X should be replaced by XDO if the fitness of XDO is better than X. Otherwise, X stays the same. It is important to note that XjDO should be in aj,bj, otherwise, XjDO needs to be redefined as a random number in this interval.


## 3.1. Grasshopper Optimization Algorithm

GOA optimization algorithm is a featured intelligent optimization algorithm based on population, which is inspired by the foraging behavior of grasshopper population. The grasshoppers’ position constitutes the solution space, and the optimal grasshopper’s position corresponds to the optimal solution. Grasshopper is always moving during the foraging process, so the position is constantly changing. During each iteration, the optimal position will be updated if a better position is found until the iteration termination condition is satisfied.The mathematical model employed to simulate the swarming behavior of grasshoppers is shown as follows:(6)Xi=Si+Gi+Ai,where Xi defines the position of the ith grasshopper, Si is social interaction, Gi is the influence of gravity on the ith grasshopper, and Ai is the influence of wind on the ith grasshopper. However, in order to provide random behavior, the equation can be written as Xi=r1Si+r2Gi+r3Ai, where r1, r2, and r3 is a random number between 0,1:(7)Si=∑j=1,j≠iNsdijdij^,where dij is the distance between the ith and the jth grasshopper, calculated as dij=xj−xi, s is a function to define the strength of social forces, which is shown in equation (8), and dij^=xj−xi/dij is a unit vector from the ith grasshopper to the jth grasshopper.The functions, which defines the strength of social forces, is calculated as follows:(8)sr=fe−r/ı−e−r,where f is the strength of attraction and l is the scale of attraction length.TheG component in equation (6) is calculated as follows:(9)Gi=−geg^,where g is the gravitational constant and eg^ is a unit vector towards the center of Earth.TheA component in equation (6) is calculated as follows:(10)Ai=−uew^,where u is an offset constant and ew^ is the unit vector along the direction of wind.SubstitutingS, G, and A in equation (6), this equation can be expressed as follows:(11)Xi=∑j=1,j≠iNsxj−xixj−xidij−geg^+uew^,where sr=fe−r/l−e−r and N is the number of grasshoppers.However, this mathematical model cannot be used directly to solve the optimization problems mainly because the grasshoppers quickly reach their comfort zone and the swarm does not converge to the specified point. In order to solve the optimization problem, the modified form of this equation is as follows:(12)Xid=c∑j=1,j≠iNcubd−lbd2sxjd−xidxj−xidij+Td^,where ubd is the upper bound of the dth dimension, lbd is the lower bound of the dth dimension, sr=fe−r/l−e−r, Td^ is the value of dth dimension of the target (best solution found so far), and c is a decreasing coefficient of comfort zone, repulsion zone, and attraction zone, as defined in equation (13). Note that S is almost similar to the component S in equation (6). However, we do not consider the gravity (no G component) and assume that the wind direction is always toward a target Td^. According to equation (12), the next position of the grasshopper is determined according to its current position, the position of the target, and the position of all other grasshoppers:(13)c=cmax−lcmax−cminL,where cmax is the maximum value, cmin is the minimum value, l is the current iteration number, and L is the maximum iteration number. In this paper, we take 1 and 0.00001 for cmax and cmin, respectively.


## 3.2. Oppositional-Based Learning (OBL)

Opposition-based learning (OBL) [49] is one of the most successful learning strategies and is widely used in the effective learning phase to enhance the search capability of population-based algorithms. When finding the solution X of a given problem, OBL makes the candidate solution more likely to approach the optimal solution by simultaneously computing the current X and the inverse solution of X.


### 3.2.1. Opposite Number

X is a real number in [a, b], where a and b are the boundaries of X. XO is the opposite number of X, which can be defined as follows:(14)XO=a+b−X.


### 3.2.2. Opposite Point

Assume thatX=X1,X2,…,XD is a point in a D-dimensional space, and Xj∈aj,bj, where j = 1 : D and aj and bj are the low and high boundaries of the current population respectively, which change with iteration. A D-dimension opposite point is defined as follows:(15)XjO=aj+bj−Xj,j=1:D.


## 3.2.1. Opposite Number

X is a real number in [a, b], where a and b are the boundaries of X. XO is the opposite number of X, which can be defined as follows:(14)XO=a+b−X.


## 3.2.2. Opposite Point

Assume thatX=X1,X2,…,XD is a point in a D-dimensional space, and Xj∈aj,bj, where j = 1 : D and aj and bj are the low and high boundaries of the current population respectively, which change with iteration. A D-dimension opposite point is defined as follows:(15)XjO=aj+bj−Xj,j=1:D.


## 3.3. Dynamic-Opposite Learning (DOL)

On the basis of OBL strategy, many new ideas such as quasi-opposite-based learning (QOBL) [50] and quasi-reflection-based learning (QRBL) [51] are proposed, and the quasi-opposite number in QOBL and the quasi-reflection number in QRBL are both closer to the global optimum than the opposite number in OBL. However, if there is a local optimum in the search space, all strategies including OBL, QOBL, and QRBL tend to converge the search space to the local optimal location. Concerning this problem, a dynamic opposite learning (DOL) strategy is proposed in [37], which can improve the probability of convergence to the global optimum while avoiding falling into the local optimum.In order to avoid the situation of falling into the local optimum in the space from the current number to the opposite number in OBL theory, a random opposite numberXRO was proposed, and XRO=rand∗XO,rand∈0,1. We can see that XRO can be not only between X and XO but also greater or less than X or XO. DOL strategy is formulated by randomly selecting a DOL number XDO between X and XRO. When XRO∈a,b, XDO=X+randXRO−X; otherwise, if XRO exceeds the range of a,b, it is necessary to check whether the number obtained by DOL has a boundary: if X+randXRO−X∈a,b, XDO is equal to X+randXRO−X; otherwise, XDO should be reset as a random number between a and b. Although XRO can enhance the diversity of the search space, the search space may shrink along with the iteration, which will lead to the deterioration of the exploitation capability. In light of this, a positive weighting factor w is used to balance the region and diversity of the search space. The mathematical model of DOL can be described as follows.


### 3.3.1. Dynamic Opposite Number

X is a real number in [a, b], where a and b are the boundaries of X. The dynamic opposite number XDO can be defined as equation (16), where a and b are the boundaries and rand is a random number between 0 and 1. Moreover, w is a positive weighting factor, and XO is the opposite number defined as equation (14):(16)XDO=X+w∗rand∗rand∗XO−X.


### 3.3.2. Dynamic Opposite Point

X=X1,X2,…,XD is a point in a D-dimensional space, and Xj∈aj,bj, where j = 1 : D and aj and bj are the low and high boundaries of the current population, respectively, which change with iteration. A D-dimension dynamic opposite point is defined as follows:(17)XjDO=Xj+w∗rand∗XjO−Xj,j=1:D,where rand is a random number between 0 and 1, w is a positive weighting factor, and XjO is the opposite point defined as equation (15).


### 3.3.3. DOL-Based Optimization

Assume thatX=X1,X2,…,XD is a point in a D-dimensional space, and Xj∈aj,bj, where j = 1 : D and aj and bj are the low and high boundaries of the current population, respectively, which change with iteration. Dynamic opposite point XDO=X1DO,X2DO,…,XDDO is defined according to equation (17) and is updated by X in each generation. X should be replaced by XDO if the fitness of XDO is better than X. Otherwise, X stays the same. It is important to note that XjDO should be in aj,bj, otherwise, XjDO needs to be redefined as a random number in this interval.


## 3.3.1. Dynamic Opposite Number

X is a real number in [a, b], where a and b are the boundaries of X. The dynamic opposite number XDO can be defined as equation (16), where a and b are the boundaries and rand is a random number between 0 and 1. Moreover, w is a positive weighting factor, and XO is the opposite number defined as equation (14):(16)XDO=X+w∗rand∗rand∗XO−X.


## 3.3.2. Dynamic Opposite Point

X=X1,X2,…,XD is a point in a D-dimensional space, and Xj∈aj,bj, where j = 1 : D and aj and bj are the low and high boundaries of the current population, respectively, which change with iteration. A D-dimension dynamic opposite point is defined as follows:(17)XjDO=Xj+w∗rand∗XjO−Xj,j=1:D,where rand is a random number between 0 and 1, w is a positive weighting factor, and XjO is the opposite point defined as equation (15).


## 3.3.3. DOL-Based Optimization

Assume thatX=X1,X2,…,XD is a point in a D-dimensional space, and Xj∈aj,bj, where j = 1 : D and aj and bj are the low and high boundaries of the current population, respectively, which change with iteration. Dynamic opposite point XDO=X1DO,X2DO,…,XDDO is defined according to equation (17) and is updated by X in each generation. X should be replaced by XDO if the fitness of XDO is better than X. Otherwise, X stays the same. It is important to note that XjDO should be in aj,bj, otherwise, XjDO needs to be redefined as a random number in this interval.


## 4. DOL-Based GOA Algorithm

Conventional GOA algorithm has limitation in the exploitation ability, which calls for novel strategies in enhancing the solution diversity. In this section, an algorithm named DOLGOA is proposed, which applies DOL strategy to GOA algorithm in accelerating the convergence speed and preventing the algorithm from falling into local optimal. DOL strategy contributes to GOA mainly in two aspects, including population initialization and generation jumping.


### 4.1. DOL Population Initialization

The DOL initialization is shown as follows:(18)Xi,jDO=Xi,j+r1i∗r2i∗aj+bj−Xi,j−Xi,j,where Xi,j is the randomly generated initial population and Xi,jDO is the population obtained by DOL strategy. N is the population size, i represents the ith individual i=1,2,…,Np, j represents the jth dimension j=1,2,…,D, and r1i and r2i are two random numbers in [0, 1]. In DOL initialization, the weighting factor w is set as 1.To ensure the effectiveness of DOL, boundary detection is also required:(19)Xi,jDO=randaj,bj,ifXi,jDO<ajorXi,jDO>bj.In the initialization step, the optimal individual is selected from the new population consisting ofXi,j and Xi,jDO.


### 4.2. DOL Generation Jumping

In each iteration, if the selected probability (random number between [0, 1]) is smaller than the jump rate (Jr), the population will be updated through DOL strategy. The DOL jump process is shown as follows:(20)Xi,jDO=Xi,j+w∗r3i∗r4i∗aj+bj−Xi,j−Xi,j,where Xi,jDO also needs to meet the boundary conditions. In order to lock the new candidate objects generated by DOL into a smaller search space, we dynamically update the boundary aj,bj as follows:(21)aj=minXi,j,bj=maxXi,j.In DOL generation jumping step, the optimal individuals are selected from the new population consisting ofXi,j and Xi,jDO.


### 4.3. DOLGOA Algorithm Steps

When DOL population initialization and generation jumping are added, a new GOA variant, named dynamic opposite learning assisted GOA (DOLGOA), is proposed. In order to visualize the concrete algorithm, the steps of DOLGOA algorithm are described in Algorithm1. The procedure of DOLGOA is shown in Figure 1.Algorithm 1:The DOLGOA algorithm.
(1)
Randomly generate an initial populationX;(2)
fori=1; i≤Np; i++do(3)
r1i=rand0,1,r2i=rand0,1;(4)
forj=1; j≤D; j++do(5)
XijDO=Xij+r1i∗r2i∗aj+bj−Xij−Xij;(6)
Check the boundaries;(7)
end for(8)
end for(9)
SelectN number of the fittest individuals from X∪XDO;(10)
SetG=0;(11)
whileG ≤ maximal iteration do(12)
Evaluate all learners by the fitness functionf.;(13)
ifG=1then(14)
Sort individuals by the fitness value to get the best grasshopperXbest in the first population;(15)
else(16)
fori=1; i≤Np; i++do(17)
Update the position of the individualsXi according to update mechanism (equation (12));(18)
Check the boundaries;(19)
Evaluate the fitness values of the new individualsX′;(20)
iffXi′<fXbestthen(21)
ReplaceXbest with Xi′;(22)
end if(23)
end for(24)
end if(25)
G++;(26)
ifrand<Jrthen(27)
fori=1; i≤Np; i++do(28)
r3i=rand0,1,r4i=rand0,1;(29)
forj=1; j≤D; j++do(30)
aj=minXi,j,bj=maxXi,j;(31)
Xi,jDO=Xi,j+w∗r3i∗r4i∗aj+bj−Xi,j−Xi,j;(32)
Check boundaries;(33)
end for(34)
end for(35)
SelectN number of the fittest individuals from X∪XDO;(36)
G++;(37)
end if(38)
end whileFigure 1
The flowchart of DOLGOA algorithm.


### 4.4. Encoding and Decoding

To solve FJSP with DOLGOA, we encode the problem. In the FJSP, we define three variablesX, T1, and T2, all of which are matrix with m rows and n columns, where m is the total number of jobs and n is the maximum number of operations.The specific meaning of these three variables is shown as follows:(i)
X represents the machine number used in each operation, and the initial value of X is randomly selected from the set of alternative machines.(ii)
T1 represents the beginning time of each process, and T2 represents the completion time of each process. The values of T1 and T2 depend on X.(iii)
We treat eachX as an individual and randomly generate Np individuals X at initialization time to form a population with Np number of individuals.In addition, the decoding process can be expressed as follows:(1)
For each individualX, we calculate the beginning time T1 and completion time T2 of the first process for each job(2)
Then, calculate the arrangement of the remaining operations, where the beginning time of one operation is equal to the completion time of the previous one which is processed on the same machine, and the completion time of each operationT2 is equal to the sum of the corresponding starting time T1 and processing time(3)
Calculate the maximum completion time of each individualX, which is equal to the completion time of the last operation of the whole work(4)
With the goal of minimizing the maximum completion time, DOLGOA was used to select the optimal individualX, that is, the optimal machine allocation strategy(5)
Calculate theT1 and T2 corresponding to each procedure in the optimal strategy, and then draw the Gantt chart. The number i on the Gantt chart represents the ith job, and the tthi represents the tth process of the ith job


## 4.1. DOL Population Initialization

The DOL initialization is shown as follows:(18)Xi,jDO=Xi,j+r1i∗r2i∗aj+bj−Xi,j−Xi,j,where Xi,j is the randomly generated initial population and Xi,jDO is the population obtained by DOL strategy. N is the population size, i represents the ith individual i=1,2,…,Np, j represents the jth dimension j=1,2,…,D, and r1i and r2i are two random numbers in [0, 1]. In DOL initialization, the weighting factor w is set as 1.To ensure the effectiveness of DOL, boundary detection is also required:(19)Xi,jDO=randaj,bj,ifXi,jDO<ajorXi,jDO>bj.In the initialization step, the optimal individual is selected from the new population consisting ofXi,j and Xi,jDO.


## 4.2. DOL Generation Jumping

In each iteration, if the selected probability (random number between [0, 1]) is smaller than the jump rate (Jr), the population will be updated through DOL strategy. The DOL jump process is shown as follows:(20)Xi,jDO=Xi,j+w∗r3i∗r4i∗aj+bj−Xi,j−Xi,j,where Xi,jDO also needs to meet the boundary conditions. In order to lock the new candidate objects generated by DOL into a smaller search space, we dynamically update the boundary aj,bj as follows:(21)aj=minXi,j,bj=maxXi,j.In DOL generation jumping step, the optimal individuals are selected from the new population consisting ofXi,j and Xi,jDO.


## 4.3. DOLGOA Algorithm Steps

When DOL population initialization and generation jumping are added, a new GOA variant, named dynamic opposite learning assisted GOA (DOLGOA), is proposed. In order to visualize the concrete algorithm, the steps of DOLGOA algorithm are described in Algorithm1. The procedure of DOLGOA is shown in Figure 1.Algorithm 1:The DOLGOA algorithm.
(1)
Randomly generate an initial populationX;(2)
fori=1; i≤Np; i++do(3)
r1i=rand0,1,r2i=rand0,1;(4)
forj=1; j≤D; j++do(5)
XijDO=Xij+r1i∗r2i∗aj+bj−Xij−Xij;(6)
Check the boundaries;(7)
end for(8)
end for(9)
SelectN number of the fittest individuals from X∪XDO;(10)
SetG=0;(11)
whileG ≤ maximal iteration do(12)
Evaluate all learners by the fitness functionf.;(13)
ifG=1then(14)
Sort individuals by the fitness value to get the best grasshopperXbest in the first population;(15)
else(16)
fori=1; i≤Np; i++do(17)
Update the position of the individualsXi according to update mechanism (equation (12));(18)
Check the boundaries;(19)
Evaluate the fitness values of the new individualsX′;(20)
iffXi′<fXbestthen(21)
ReplaceXbest with Xi′;(22)
end if(23)
end for(24)
end if(25)
G++;(26)
ifrand<Jrthen(27)
fori=1; i≤Np; i++do(28)
r3i=rand0,1,r4i=rand0,1;(29)
forj=1; j≤D; j++do(30)
aj=minXi,j,bj=maxXi,j;(31)
Xi,jDO=Xi,j+w∗r3i∗r4i∗aj+bj−Xi,j−Xi,j;(32)
Check boundaries;(33)
end for(34)
end for(35)
SelectN number of the fittest individuals from X∪XDO;(36)
G++;(37)
end if(38)
end whileFigure 1
The flowchart of DOLGOA algorithm.


## 4.4. Encoding and Decoding

To solve FJSP with DOLGOA, we encode the problem. In the FJSP, we define three variablesX, T1, and T2, all of which are matrix with m rows and n columns, where m is the total number of jobs and n is the maximum number of operations.The specific meaning of these three variables is shown as follows:(i)
X represents the machine number used in each operation, and the initial value of X is randomly selected from the set of alternative machines.(ii)
T1 represents the beginning time of each process, and T2 represents the completion time of each process. The values of T1 and T2 depend on X.(iii)
We treat eachX as an individual and randomly generate Np individuals X at initialization time to form a population with Np number of individuals.In addition, the decoding process can be expressed as follows:(1)
For each individualX, we calculate the beginning time T1 and completion time T2 of the first process for each job(2)
Then, calculate the arrangement of the remaining operations, where the beginning time of one operation is equal to the completion time of the previous one which is processed on the same machine, and the completion time of each operationT2 is equal to the sum of the corresponding starting time T1 and processing time(3)
Calculate the maximum completion time of each individualX, which is equal to the completion time of the last operation of the whole work(4)
With the goal of minimizing the maximum completion time, DOLGOA was used to select the optimal individualX, that is, the optimal machine allocation strategy(5)
Calculate theT1 and T2 corresponding to each procedure in the optimal strategy, and then draw the Gantt chart. The number i on the Gantt chart represents the ith job, and the tthi represents the tth process of the ith job


## 5. Experiment and Discussion

### 5.1. Benchmark Function

In this section, we use 23 benchmark test functions to evaluate the performance of DOLGOA. These 23 benchmark functions are derived from CEC2014 and are shown in Table1. They include 3 unimodal functions, 13 multimodal functions, 6 hybrid functions, and 1 composite function. Unimodal functions are supposed to test the exploitation capability of DOLGOA because it has no local optimum in the searching space. On the contrary, multimodal functions have many local optimum and are used for exploration capability test of DOLGOA. In order to better mimic real search spaces, we also use hybrid functions and composite functions to test the performance of the algorithm.Table 1
Benchmark functions provided by CEC 2014 test set.
LabelFunctionsOptimumDimsCharacterF1High conditioned elliptic10030UnimodalF2Bent cigar20030UnimodalF3Discus30030UnimodalF4Rosenbrock40030MultimodalF5Ackely50030MultimodalF6Weierstrass60030MultimodalF7Griewank70030MultimodalF8Rastrigin80030MultimodalF9Rotated rastrigin90030MultimodalF10Schwefel100030MultimodalF11Rotated schwefel110030MultimodalF12Katsuura120030MultimodalF13HappyCat130030MultimodalF14HGBat140030MultimodalF15Expanded griewank plus rosenbrock150030MultimodalF16Expanded scaffer160030MultimodalF17HF1170030HybridF18HF2180030HybridF19HF3190030HybridF20HF4200030HybridF21HF5210030HybridF22HF6220030HybridF23CF1230030Composition


### 5.2. Parameter Settings

The 23 test functions above were used to test and compare DOLGOA with four other algorithms, including GOA, GWO, TLBO, and Jaya. The parameter settings for these experiments are listed in Table2.Table 2
The parameters settings of optimization algorithms.
ParametersValueSize of population100Total generation number for test functions3000Total generation number for FJSP200Times conducting the experiment10cmax of GOA (maximum value)1cmin of GOA (minimum value)0.00001c of GOA (decreasing coefficient)cmax−iter∗cmax−cmin/MaxiterJr of DOLGOA1w of DOLGOA4Inerita weight of PSO0.9−0.4∗G/GmScale factor of DE0.5Crossover constant of DE0.5For DOLGOA algorithm, weight factorw and jump rate Jr are two important parameters, and their analysis is shown in Table 3. We divide w and Jr into ten levels and analyze the effects of w and Jr on the optimization results by using orthogonal experiment [52]. For every pair of w and Jr, we run the corresponding algorithm 10 times and record the average results in Table 3. As shown in Table 3, when w=5 and Jr=0.9, DOLGOA gets the best result. Therefore, w=5 and Jr=0.9 are the most appropriate parameter settings.Table 3
The analysis ofw and Jr.
DOLGOAw = 1w = 2w = 3w = 4w = 5w = 6w = 7w = 8w = 9w = 10Jr = 0.15.68E + 068.08E + 069.04E + 061.13E + 074.98E + 063.16E + 068.49E + 068.23E + 067.78E + 061.06E + 07Jr = 0.21.39E + 075.65E + 061.06E + 078.21E + 064.33E + 064.56E + 062.09E + 065.58E + 066.16E + 063.02E + 06Jr = 0.32.25E + 062.59E + 068.37E + 066.23E + 069.51E + 064.18E + 064.69E + 063.14E + 064.63E + 062.28E + 06Jr = 0.46.06E + 062.62E + 066.35E + 061.98E + 067.11E + 065.48E + 066.07E + 065.37E + 067.52E + 068.97E + 06Jr = 0.54.69E + 062.45E + 065.14E + 063.53E + 064.22E + 061.84E + 065.63E + 067.82E + 064.79E + 066.35E + 06Jr = 0.65.62E + 061.17E + 077.51E + 064.16E + 063.17E + 062.59E + 063.19E + 061.82E + 061.55E + 067.45E + 06Jr = 0.76.57E + 063.74E + 065.18E + 062.25E + 063.91E + 069.26E + 066.98E + 063.54E + 063.26E + 066.74E + 06Jr = 0.81.54E + 067.66E + 068.43E + 063.67E + 065.07E + 062.82E + 062.10E + 063.08E + 063.60E + 062.35E + 06Jr = 0.93.90E + 066.37E + 063.47E + 063.90E + 061.11E + 064.90E + 061.56E + 068.06E + 066.84E + 061.60E + 06Jr = 12.40E + 063.34E + 064.59E + 062.57E + 062.23E + 061.40E + 061.94E + 061.55E + 063.38E + 064.14E + 06In addition, the total number of individuals for all tests is 100. The function evaluations (FES) is set as 300,000, and all tests were executed 10 times.


### 5.3. Unimodal/Multimodal Test Functions and Their Analysis

Unimodal functions and multimodal functions are used to test the exploitation and exploration capability of DOLGOA. The mean and standard values of the result under these functions are shown in Table4.Table 4
The mean and standard value of unimodal/multimodal test functions.
AlgorithmsDOLGOAGOAGWOTLBOJayaF1Mean1.11E + 061.17E + 075.71E + 071.27E + 084.70E + 06Std4.32E + 069.91E + 063.26E + 078.84E + 071.27E + 06F2Mean5.66E + 033.79E + 031.73E + 092.25E + 104.73E + 08Std4.38E + 032.21E + 039.04E + 086.61E + 091.43E + 08F3Mean2.75E − 024.30E + 022.13E + 043.63E + 042.87E + 04Std2.28E − 021.89E + 027.27E + 035.82E + 034.28E + 03F4Mean1.05E + 021.04E + 023.09E + 022.57E + 032.12E + 02Std6.07E + 016.55E + 011.84E + 021.53E + 031.40E + 01F5Mean2.00E + 012.00E + 012.09E + 012.04E + 012.09E + 01Std9.33E − 041.95E − 066.04E − 021.43E − 015.19E − 02F6Mean1.59E + 011.71E + 011.29E + 012.69E + 012.24E + 01Std2.09E + 005.52E + 003.85E + 003.89E + 004.18E + 00F7Mean2.91E − 021.32E − 027.38E + 002.61E + 025.68E + 00Std3.15E − 021.51E − 024.22E + 008.86E + 011.76E + 00F8Mean1.10E + 021.10E + 028.41E + 011.91E + 021.83E + 02Std3.50E + 012.65E + 011.48E + 013.18E + 011.45E + 01F9Mean1.06E + 026.50E + 017.82E + 012.16E + 021.84E + 02Std1.95E + 012.40E + 018.74E − 022.21E + 011.60E + 01F10Mean2.45E + 033.49E + 032.09E + 035.02E + 035.03E + 03Std6.29E + 023.02E + 026.41E + 023.65E + 028.82E + 02F11Mean2.85E + 032.96E + 032.09E + 035.04E + 036.23E + 03Std6.49E + 025.70E + 026.25E + 023.71E + 024.48E + 02F12Mean1.65E − 015.26E − 011.87E + 001.13E + 002.39E + 00Std7.88E − 022.47E − 011.03E + 003.46E − 012.71E − 01F13Mean3.92E − 014.21E − 014.21E − 013.88E + 005.89E − 01Std9.92E − 028.89E − 027.52E − 024.79E − 011.01E − 01F14Mean2.29E − 012.21E − 011.03E + 019.67E + 012.79E − 01Std6.40E − 022.98E − 021.62E + 011.52E + 012.10E − 02F15Mean7.03E + 006.87E + 002.21E + 018.24E + 032.20E + 01Std2.04E + 009.11E − 019.62E + 008.24E + 031.75E + 00F16Mean1.18E + 011.15E + 011.09E + 011.15E + 011.26E + 01Std5.11E − 016.85E − 014.16E − 013.96E − 012.09E − 01Best num57500It can be seen that DOLGOA and GOA algorithms are superior to other algorithms in unimodal test functions F1–F3. Especially in terms of F1 and F3, DOLGOA is greatly improved on the basis of original GOA, which indicates that DOL strategy can improve the exploitation of individuals and help them converge to the global optimum in asymmetric space.Multimodal functions contain multiple local optimum, which are used to test the exploration capability of DOLGOA under various local optimal conditions. It can be seen from F4–F16 that compared with other algorithms, GOA and DOLGOA algorithms show better exploration capability, especially on F5, F12, and F13, and DOLGOA has the best performance.


### 5.4. Analysis of Hybrid and Composition Test Functions

The hybrid function combines both unimodal and multimodal functions to better simulate the real search space. When dealing with the hybrid function, it needs to balance the exploitation ability and exploration ability, which requires higher requirements on the algorithm. The mean and standard values of all hybrid and composition test functions are shown in Table5.Table 5
The mean and standard value of hybrid test functions.
AlgorithmsDOLGOAGOAGWOTLBOJayaF17Mean3.89E + 048.39E + 059.13E + 057.88E + 052.79E + 05Std2.11E + 041.06E + 061.03E + 066.08E + 051.38E + 05F18Mean2.95E + 035.90E + 038.69E + 062.17E + 037.73E + 05Std2.94E + 033.81E + 031.56E + 072.92E + 033.06E + 05F19Mean1.50E + 011.37E + 014.51E + 015.37E + 011.20E + 01Std1.97E + 004.99E + 002.33E + 012.77E + 011.39E + 00F20Mean1.71E + 023.10E + 021.06E + 045.49E + 031.04E + 03Std2.67E + 011.00E + 022.17E + 036.47E + 039.24E + 02F21Mean2.05E + 041.30E + 052.51E + 052.51E + 044.14E + 04Std8.65E + 037.83E + 043.33E + 051.27E + 049.43E + 03F22Mean2.40E + 024.64E + 022.49E + 025.03E + 023.85E + 02Std1.48E + 022.25E + 021.01E + 021.44E + 027.13E + 01F23Mean2.00E + 023.21E + 023.32E + 022.00E + 023.25E + 02Std1.18E − 054.80E + 008.01E + 002.03E − 132.94E + 00Best num50021As can be seen from the table, DOLGOA performs very well in hybrid functions, especially in F17, F20, F21, and F22. On the composition function F23, the result of DOLGOA is not worse than other algorithms, which indicates that DOLGOA can well balance the exploitation and exploration capability in practical application.


### 5.5. Statistical Test Results

Two independent-sampleT tests are applied to test whether there is a significant difference in the mean value of the two samples. The t values are shown in Table 6, and the P values are shown in Table 7, which is marked as “+” and “−”.Table 6
Thet values of DOLGOA and other algorithms.
GOAGWOTLBOJayaDOLGOAF11.56E + 011.20E + 022.83E + 027.32E − 01F24.26E + 003.95E + 065.14E + 071.08E + 06F31.89E + 059.35E + 061.60E + 071.26E + 07F42.91E − 013.35E + 014.06E + 021.75E + 02F57.37E − 011.00E + 044.45E + 039.86E + 03F65.73E + 001.39E + 015.29E + 013.11E + 02F75.05E + 002.33E + 038.29E + 041.79E + 03F81.89E − 027.39E + 002.04E + 012.08E + 01DOLMFOF92.14E + 011.46E + 015.61E + 013.94E + 01F101.65E + 015.80E + 004.08E + 014.10E + 01F111.72E + 001.17E + 013.37E + 015.20E + 01F124.58E + 012.17E + 021.22E + 022.83E + 02F133.02E + 002.94E + 003.52E + 021.99E + 01F141.21E + 001.58E + 031.51E + 047.86E + 00F157.55E − 017.37E + 014.03E + 047.33E + 01F166.32E + 001.87E + 015.79E + 001.45E + 01F173.78E + 024.13E + 023.54E + 021.14E + 02F181.00E + 012.95E + 042.67E + 002.61E + 03F196.96E + 001.52E + 021.95E + 021.54E + 01F205.18E + 013.92E + 031.98E + 033.27E + 02F211.26E + 022.67E + 025.25E + 002.41E + 01F221.51E + 015.88E − 011.77E + 019.75E + 00F231.02E + 081.12E + 081.50E + 011.06E + 08Table 7
TheP values of DOLGOA and other algorithms.
GOAGWOTLBOJayaDOLGOAF1−−−+F2−−−−F3−−−−F4+−−−F5−−−−F6−−−−F7−−−−F8+−−−F9−−−−F10−−−−F11+−−−F12−−−−DOLMFOF13−−−−F14+−−−F15+−−−F16−−−−F17−−−−F18−−−−F19−−−−F20−−−−F21−−−−F22−+−−F23−−−−Better18222322Same5101Set 0.05 as the level of significance:t300.05=2.0423. When t<2.0423, it indicates P>0.05, and P is marked as “+” in Table 7. In this case, the null hypothesis is eligible and accepted, which means there is no significant difference between the two algorithms. On the contrary, when t>2.0423, P<0.05 is indicated, and P is marked as “−” in Table 7; the null hypothesis is rejected, which means the two algorithms are significantly different. In Table 7, “Same” means the total number of DOLGOA that is not significantly different from other algorithms, and “Better” means the total number of DOLGOA that is significantly different from other algorithms.From Tables6 and 7, it can be seen that, for most test functions, DOLGOA shows significant difference from other algorithms, which means that DOL greatly improves the performance of GOA.


### 5.6. Analysis of Convergence

The convergence trends of all algorithms for unimodal and multimodal test functions are shown in Figures2 and 3, respectively, and the convergence trends of all algorithms for hybrid function and composite function are shown in Figure 4.Figure 2
The convergence trends of all algorithms on unimodal functions.
(a)(b)(c)Figure 3
The convergence trends of all algorithms on multimodal functions.
(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)(m)Figure 4
The convergence trends of all algorithms on hybrid and composition functions.
(a)(b)(c)(d)(e)(f)(g)As can be seen from the figure, the convergence result of DOLGOA is the best for most of the test functions, which indicates that DOLGOA has good exploration capability to avoid falling into the local optimum. The convergence curve of DOLGOA eventually tends to the optimal value, thanks to the exploitation capability of the DOL strategy.


### 5.7. Application to FJSP

In addition to the test on numerical benchmark functions, DOLGOA is adopted to solve the FJSP to further evaluate its performance. The purpose of FJSP in this paper is to minimize the maximal completion time. We analyze the performance of DOLGOA by comparing with GOA, PSO, Jaya, DE , GWO [53–56], HTS/TA, ITS, and ISA. Some of the data of these experiments are adopted from the literature [57]. These algorithms are implemented on 21 different problems, which are classified into three classes: small (SFJS01–SFJS10), medium (MFJS01–MFJS10), and large ((LFJS01)) size FJSP problems. The data of small and medium size experiments is adopted from the literature [57], and the data of the large size experiment is adopted from the literature [58]. Table 1 shows the parameter settings of these optimization algorithms. To eliminate the randomness, each problem implements 10 independent runs. Table 8 shows the experimental results of these algorithms in small and medium size experiments, and the results with ∗ are the best solution results of the corresponding problem.Table 8
The statistical results obtained by algorithms for solving FJSP.
AlgorithmsDOLGOAGOAPSOJayaDEGWOHTS/TAITSISAMFJS01481482484490469∗481503584518MFJS02456∗463466457456∗467494544494MFJS03491∗538531505495494540606611MFJS04653651646620600562∗660870798MFJS05593613614558538508∗633729706MFJS06643∗749756708682651741876889MFJS071093109211001009990933∗99911271307MFJS08997∗11001108102210251009100013521437MFJS091263134713661291128612711158∗12191218MFJS101517156715921458∗14881500151117371733SFJS0166∗66∗66∗66∗66∗66∗66∗66∗66∗SFJS02107∗107∗107∗107∗107∗107∗107∗107∗107∗SFJS03221∗221∗221∗221∗221∗221∗221∗221∗231SFJS04355∗355∗355∗355∗355∗355∗355∗390375SFJS05119∗119∗119∗119∗119∗119∗119∗137137SFJS06320∗320∗320∗320∗320∗320∗320∗320∗336SFJS07397∗397∗397∗397∗397∗397∗397∗397∗397∗SFJS08253∗253∗253∗253∗253∗253∗253∗253∗254SFJS09210∗210∗210∗210∗210∗210∗210∗218228SFJS10533∗533∗533∗533∗533∗533∗533∗624570Best num1410101112131163It can be seen that DOLGOA obtains the best results for 14 problems. Although DOLGOA does not get the best results in other medium size problems, the difference is not significant from the best results. From Table8, we can see that almost all algorithms can get the best result for small size FJSP, but as the scale of the problem gets larger, the advantage of DOLGOA becomes more apparent. For the 10 medium size FJSPs, DOLGOA obtains the best results on four of them, and the results are much better than GOA. This demonstrates that DOL strategy improves the exploitation capability of the algorithm, which makes DOLGOA more effective for solving FJSP. Figure 5 shows the mean convergence curve of the makespan in MFJS03 of the six algorithms in 10 separate runs. Figure 6 shows the convergence curve of the makespan in MFJS09 of six algorithms in 10 independent runs. It can be seen that DOLGOA obtains the best result. Figures 7 and 8 illustrate the Gantt charts of the optimal solutions obtained by DOLGOA in a featured run for problem MFJS03 and MFJS10, respectively. We can see that the shortest completion time solved by DOLGOA algorithm is 489 and 1517 for MFJS03 and MFJS10, respectively. Figure 9 shows the convergence curve of the average results of ten runs obtained by DOLGOA for the large size experiments. In addition, Figure 10 shows the Gantt chart of the optimal solutions obtained by DOLGOA for the large size experiments. In the large size problem LFJS01, there are 15 jobs to be processed by 10 machines in a workshop, where each job consists of 2–4 processes and each process can only be completed by several specified machines. It can be seen that DOLGOA can assign a series of optional machines to a specified process to obtain the best solution. As shown in Figure 7, the optimal solution obtained by DOLGOA for LFJS01 is 31. In Table 9, we list the computational time of these 6 algorithms to solve FJSP, and all the simulations run on an Intel(R) Core(TM) i5-9400F CPU@2.90 GHz PC and the Matlab(R) 2019a software platform.Figure 5
Convergence results of MFJS03 for all the compared algorithms.Figure 6
Convergence results of MFJS09 for all the compared algorithms.Figure 7
Gantt chart of an optimal solution to MFJS03 obtained by DOLGOA.Figure 8
Gantt chart of an optimal solution to MFJS10 obtained by DOLGOA.Figure 9
Convergence results on LFJS01.Figure 10
Gantt chart on LFJS01.Table 9
The CPU time periods obtained by algorithms for solving FJSP.
AlgorithmsDOLGOAGOAPSOJayaDEGWOMFJS016.897.536.884.194.183.02MFJS026.547.816.664.754.263.03MFJS037.188.207.865.344.863.38MFJS047.758.528.735.915.453.82MFJS057.828.518.636.005.503.85MFJS068.559.069.926.686.164.34MFJS0710.3110.5712.858.338.375.74MFJS0811.1311.1614.308.879.026.25MFJS0912.68∗12.2816.6610.4410.577.46MFJS1013.6812.9918.2410.8811.347.85SFJS013.755.702.231.191.360.97SFJS023.595.322.211.161.341.00SFJS034.235.582.841.531.671.33SFJS044.195.722.981.531.751.33SFJS054.215.813.064.191.701.31SFJS065.026.224.334.752.521.95SFJS075.316.534.675.342.861.99SFJS085.136.654.495.912.671.91SFJS095.086.514.456.002.561.95SFJS105.786.955.896.683.352.51


## 5.1. Benchmark Function

In this section, we use 23 benchmark test functions to evaluate the performance of DOLGOA. These 23 benchmark functions are derived from CEC2014 and are shown in Table1. They include 3 unimodal functions, 13 multimodal functions, 6 hybrid functions, and 1 composite function. Unimodal functions are supposed to test the exploitation capability of DOLGOA because it has no local optimum in the searching space. On the contrary, multimodal functions have many local optimum and are used for exploration capability test of DOLGOA. In order to better mimic real search spaces, we also use hybrid functions and composite functions to test the performance of the algorithm.Table 1
Benchmark functions provided by CEC 2014 test set.
LabelFunctionsOptimumDimsCharacterF1High conditioned elliptic10030UnimodalF2Bent cigar20030UnimodalF3Discus30030UnimodalF4Rosenbrock40030MultimodalF5Ackely50030MultimodalF6Weierstrass60030MultimodalF7Griewank70030MultimodalF8Rastrigin80030MultimodalF9Rotated rastrigin90030MultimodalF10Schwefel100030MultimodalF11Rotated schwefel110030MultimodalF12Katsuura120030MultimodalF13HappyCat130030MultimodalF14HGBat140030MultimodalF15Expanded griewank plus rosenbrock150030MultimodalF16Expanded scaffer160030MultimodalF17HF1170030HybridF18HF2180030HybridF19HF3190030HybridF20HF4200030HybridF21HF5210030HybridF22HF6220030HybridF23CF1230030Composition


## 5.2. Parameter Settings

The 23 test functions above were used to test and compare DOLGOA with four other algorithms, including GOA, GWO, TLBO, and Jaya. The parameter settings for these experiments are listed in Table2.Table 2
The parameters settings of optimization algorithms.
ParametersValueSize of population100Total generation number for test functions3000Total generation number for FJSP200Times conducting the experiment10cmax of GOA (maximum value)1cmin of GOA (minimum value)0.00001c of GOA (decreasing coefficient)cmax−iter∗cmax−cmin/MaxiterJr of DOLGOA1w of DOLGOA4Inerita weight of PSO0.9−0.4∗G/GmScale factor of DE0.5Crossover constant of DE0.5For DOLGOA algorithm, weight factorw and jump rate Jr are two important parameters, and their analysis is shown in Table 3. We divide w and Jr into ten levels and analyze the effects of w and Jr on the optimization results by using orthogonal experiment [52]. For every pair of w and Jr, we run the corresponding algorithm 10 times and record the average results in Table 3. As shown in Table 3, when w=5 and Jr=0.9, DOLGOA gets the best result. Therefore, w=5 and Jr=0.9 are the most appropriate parameter settings.Table 3
The analysis ofw and Jr.
DOLGOAw = 1w = 2w = 3w = 4w = 5w = 6w = 7w = 8w = 9w = 10Jr = 0.15.68E + 068.08E + 069.04E + 061.13E + 074.98E + 063.16E + 068.49E + 068.23E + 067.78E + 061.06E + 07Jr = 0.21.39E + 075.65E + 061.06E + 078.21E + 064.33E + 064.56E + 062.09E + 065.58E + 066.16E + 063.02E + 06Jr = 0.32.25E + 062.59E + 068.37E + 066.23E + 069.51E + 064.18E + 064.69E + 063.14E + 064.63E + 062.28E + 06Jr = 0.46.06E + 062.62E + 066.35E + 061.98E + 067.11E + 065.48E + 066.07E + 065.37E + 067.52E + 068.97E + 06Jr = 0.54.69E + 062.45E + 065.14E + 063.53E + 064.22E + 061.84E + 065.63E + 067.82E + 064.79E + 066.35E + 06Jr = 0.65.62E + 061.17E + 077.51E + 064.16E + 063.17E + 062.59E + 063.19E + 061.82E + 061.55E + 067.45E + 06Jr = 0.76.57E + 063.74E + 065.18E + 062.25E + 063.91E + 069.26E + 066.98E + 063.54E + 063.26E + 066.74E + 06Jr = 0.81.54E + 067.66E + 068.43E + 063.67E + 065.07E + 062.82E + 062.10E + 063.08E + 063.60E + 062.35E + 06Jr = 0.93.90E + 066.37E + 063.47E + 063.90E + 061.11E + 064.90E + 061.56E + 068.06E + 066.84E + 061.60E + 06Jr = 12.40E + 063.34E + 064.59E + 062.57E + 062.23E + 061.40E + 061.94E + 061.55E + 063.38E + 064.14E + 06In addition, the total number of individuals for all tests is 100. The function evaluations (FES) is set as 300,000, and all tests were executed 10 times.


## 5.3. Unimodal/Multimodal Test Functions and Their Analysis

Unimodal functions and multimodal functions are used to test the exploitation and exploration capability of DOLGOA. The mean and standard values of the result under these functions are shown in Table4.Table 4
The mean and standard value of unimodal/multimodal test functions.
AlgorithmsDOLGOAGOAGWOTLBOJayaF1Mean1.11E + 061.17E + 075.71E + 071.27E + 084.70E + 06Std4.32E + 069.91E + 063.26E + 078.84E + 071.27E + 06F2Mean5.66E + 033.79E + 031.73E + 092.25E + 104.73E + 08Std4.38E + 032.21E + 039.04E + 086.61E + 091.43E + 08F3Mean2.75E − 024.30E + 022.13E + 043.63E + 042.87E + 04Std2.28E − 021.89E + 027.27E + 035.82E + 034.28E + 03F4Mean1.05E + 021.04E + 023.09E + 022.57E + 032.12E + 02Std6.07E + 016.55E + 011.84E + 021.53E + 031.40E + 01F5Mean2.00E + 012.00E + 012.09E + 012.04E + 012.09E + 01Std9.33E − 041.95E − 066.04E − 021.43E − 015.19E − 02F6Mean1.59E + 011.71E + 011.29E + 012.69E + 012.24E + 01Std2.09E + 005.52E + 003.85E + 003.89E + 004.18E + 00F7Mean2.91E − 021.32E − 027.38E + 002.61E + 025.68E + 00Std3.15E − 021.51E − 024.22E + 008.86E + 011.76E + 00F8Mean1.10E + 021.10E + 028.41E + 011.91E + 021.83E + 02Std3.50E + 012.65E + 011.48E + 013.18E + 011.45E + 01F9Mean1.06E + 026.50E + 017.82E + 012.16E + 021.84E + 02Std1.95E + 012.40E + 018.74E − 022.21E + 011.60E + 01F10Mean2.45E + 033.49E + 032.09E + 035.02E + 035.03E + 03Std6.29E + 023.02E + 026.41E + 023.65E + 028.82E + 02F11Mean2.85E + 032.96E + 032.09E + 035.04E + 036.23E + 03Std6.49E + 025.70E + 026.25E + 023.71E + 024.48E + 02F12Mean1.65E − 015.26E − 011.87E + 001.13E + 002.39E + 00Std7.88E − 022.47E − 011.03E + 003.46E − 012.71E − 01F13Mean3.92E − 014.21E − 014.21E − 013.88E + 005.89E − 01Std9.92E − 028.89E − 027.52E − 024.79E − 011.01E − 01F14Mean2.29E − 012.21E − 011.03E + 019.67E + 012.79E − 01Std6.40E − 022.98E − 021.62E + 011.52E + 012.10E − 02F15Mean7.03E + 006.87E + 002.21E + 018.24E + 032.20E + 01Std2.04E + 009.11E − 019.62E + 008.24E + 031.75E + 00F16Mean1.18E + 011.15E + 011.09E + 011.15E + 011.26E + 01Std5.11E − 016.85E − 014.16E − 013.96E − 012.09E − 01Best num57500It can be seen that DOLGOA and GOA algorithms are superior to other algorithms in unimodal test functions F1–F3. Especially in terms of F1 and F3, DOLGOA is greatly improved on the basis of original GOA, which indicates that DOL strategy can improve the exploitation of individuals and help them converge to the global optimum in asymmetric space.Multimodal functions contain multiple local optimum, which are used to test the exploration capability of DOLGOA under various local optimal conditions. It can be seen from F4–F16 that compared with other algorithms, GOA and DOLGOA algorithms show better exploration capability, especially on F5, F12, and F13, and DOLGOA has the best performance.


## 5.4. Analysis of Hybrid and Composition Test Functions

The hybrid function combines both unimodal and multimodal functions to better simulate the real search space. When dealing with the hybrid function, it needs to balance the exploitation ability and exploration ability, which requires higher requirements on the algorithm. The mean and standard values of all hybrid and composition test functions are shown in Table5.Table 5
The mean and standard value of hybrid test functions.
AlgorithmsDOLGOAGOAGWOTLBOJayaF17Mean3.89E + 048.39E + 059.13E + 057.88E + 052.79E + 05Std2.11E + 041.06E + 061.03E + 066.08E + 051.38E + 05F18Mean2.95E + 035.90E + 038.69E + 062.17E + 037.73E + 05Std2.94E + 033.81E + 031.56E + 072.92E + 033.06E + 05F19Mean1.50E + 011.37E + 014.51E + 015.37E + 011.20E + 01Std1.97E + 004.99E + 002.33E + 012.77E + 011.39E + 00F20Mean1.71E + 023.10E + 021.06E + 045.49E + 031.04E + 03Std2.67E + 011.00E + 022.17E + 036.47E + 039.24E + 02F21Mean2.05E + 041.30E + 052.51E + 052.51E + 044.14E + 04Std8.65E + 037.83E + 043.33E + 051.27E + 049.43E + 03F22Mean2.40E + 024.64E + 022.49E + 025.03E + 023.85E + 02Std1.48E + 022.25E + 021.01E + 021.44E + 027.13E + 01F23Mean2.00E + 023.21E + 023.32E + 022.00E + 023.25E + 02Std1.18E − 054.80E + 008.01E + 002.03E − 132.94E + 00Best num50021As can be seen from the table, DOLGOA performs very well in hybrid functions, especially in F17, F20, F21, and F22. On the composition function F23, the result of DOLGOA is not worse than other algorithms, which indicates that DOLGOA can well balance the exploitation and exploration capability in practical application.


## 5.5. Statistical Test Results

Two independent-sampleT tests are applied to test whether there is a significant difference in the mean value of the two samples. The t values are shown in Table 6, and the P values are shown in Table 7, which is marked as “+” and “−”.Table 6
Thet values of DOLGOA and other algorithms.
GOAGWOTLBOJayaDOLGOAF11.56E + 011.20E + 022.83E + 027.32E − 01F24.26E + 003.95E + 065.14E + 071.08E + 06F31.89E + 059.35E + 061.60E + 071.26E + 07F42.91E − 013.35E + 014.06E + 021.75E + 02F57.37E − 011.00E + 044.45E + 039.86E + 03F65.73E + 001.39E + 015.29E + 013.11E + 02F75.05E + 002.33E + 038.29E + 041.79E + 03F81.89E − 027.39E + 002.04E + 012.08E + 01DOLMFOF92.14E + 011.46E + 015.61E + 013.94E + 01F101.65E + 015.80E + 004.08E + 014.10E + 01F111.72E + 001.17E + 013.37E + 015.20E + 01F124.58E + 012.17E + 021.22E + 022.83E + 02F133.02E + 002.94E + 003.52E + 021.99E + 01F141.21E + 001.58E + 031.51E + 047.86E + 00F157.55E − 017.37E + 014.03E + 047.33E + 01F166.32E + 001.87E + 015.79E + 001.45E + 01F173.78E + 024.13E + 023.54E + 021.14E + 02F181.00E + 012.95E + 042.67E + 002.61E + 03F196.96E + 001.52E + 021.95E + 021.54E + 01F205.18E + 013.92E + 031.98E + 033.27E + 02F211.26E + 022.67E + 025.25E + 002.41E + 01F221.51E + 015.88E − 011.77E + 019.75E + 00F231.02E + 081.12E + 081.50E + 011.06E + 08Table 7
TheP values of DOLGOA and other algorithms.
GOAGWOTLBOJayaDOLGOAF1−−−+F2−−−−F3−−−−F4+−−−F5−−−−F6−−−−F7−−−−F8+−−−F9−−−−F10−−−−F11+−−−F12−−−−DOLMFOF13−−−−F14+−−−F15+−−−F16−−−−F17−−−−F18−−−−F19−−−−F20−−−−F21−−−−F22−+−−F23−−−−Better18222322Same5101Set 0.05 as the level of significance:t300.05=2.0423. When t<2.0423, it indicates P>0.05, and P is marked as “+” in Table 7. In this case, the null hypothesis is eligible and accepted, which means there is no significant difference between the two algorithms. On the contrary, when t>2.0423, P<0.05 is indicated, and P is marked as “−” in Table 7; the null hypothesis is rejected, which means the two algorithms are significantly different. In Table 7, “Same” means the total number of DOLGOA that is not significantly different from other algorithms, and “Better” means the total number of DOLGOA that is significantly different from other algorithms.From Tables6 and 7, it can be seen that, for most test functions, DOLGOA shows significant difference from other algorithms, which means that DOL greatly improves the performance of GOA.


## 5.6. Analysis of Convergence

The convergence trends of all algorithms for unimodal and multimodal test functions are shown in Figures2 and 3, respectively, and the convergence trends of all algorithms for hybrid function and composite function are shown in Figure 4.Figure 2
The convergence trends of all algorithms on unimodal functions.
(a)(b)(c)Figure 3
The convergence trends of all algorithms on multimodal functions.
(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)(m)Figure 4
The convergence trends of all algorithms on hybrid and composition functions.
(a)(b)(c)(d)(e)(f)(g)As can be seen from the figure, the convergence result of DOLGOA is the best for most of the test functions, which indicates that DOLGOA has good exploration capability to avoid falling into the local optimum. The convergence curve of DOLGOA eventually tends to the optimal value, thanks to the exploitation capability of the DOL strategy.


## 5.7. Application to FJSP

In addition to the test on numerical benchmark functions, DOLGOA is adopted to solve the FJSP to further evaluate its performance. The purpose of FJSP in this paper is to minimize the maximal completion time. We analyze the performance of DOLGOA by comparing with GOA, PSO, Jaya, DE , GWO [53–56], HTS/TA, ITS, and ISA. Some of the data of these experiments are adopted from the literature [57]. These algorithms are implemented on 21 different problems, which are classified into three classes: small (SFJS01–SFJS10), medium (MFJS01–MFJS10), and large ((LFJS01)) size FJSP problems. The data of small and medium size experiments is adopted from the literature [57], and the data of the large size experiment is adopted from the literature [58]. Table 1 shows the parameter settings of these optimization algorithms. To eliminate the randomness, each problem implements 10 independent runs. Table 8 shows the experimental results of these algorithms in small and medium size experiments, and the results with ∗ are the best solution results of the corresponding problem.Table 8
The statistical results obtained by algorithms for solving FJSP.
AlgorithmsDOLGOAGOAPSOJayaDEGWOHTS/TAITSISAMFJS01481482484490469∗481503584518MFJS02456∗463466457456∗467494544494MFJS03491∗538531505495494540606611MFJS04653651646620600562∗660870798MFJS05593613614558538508∗633729706MFJS06643∗749756708682651741876889MFJS071093109211001009990933∗99911271307MFJS08997∗11001108102210251009100013521437MFJS091263134713661291128612711158∗12191218MFJS101517156715921458∗14881500151117371733SFJS0166∗66∗66∗66∗66∗66∗66∗66∗66∗SFJS02107∗107∗107∗107∗107∗107∗107∗107∗107∗SFJS03221∗221∗221∗221∗221∗221∗221∗221∗231SFJS04355∗355∗355∗355∗355∗355∗355∗390375SFJS05119∗119∗119∗119∗119∗119∗119∗137137SFJS06320∗320∗320∗320∗320∗320∗320∗320∗336SFJS07397∗397∗397∗397∗397∗397∗397∗397∗397∗SFJS08253∗253∗253∗253∗253∗253∗253∗253∗254SFJS09210∗210∗210∗210∗210∗210∗210∗218228SFJS10533∗533∗533∗533∗533∗533∗533∗624570Best num1410101112131163It can be seen that DOLGOA obtains the best results for 14 problems. Although DOLGOA does not get the best results in other medium size problems, the difference is not significant from the best results. From Table8, we can see that almost all algorithms can get the best result for small size FJSP, but as the scale of the problem gets larger, the advantage of DOLGOA becomes more apparent. For the 10 medium size FJSPs, DOLGOA obtains the best results on four of them, and the results are much better than GOA. This demonstrates that DOL strategy improves the exploitation capability of the algorithm, which makes DOLGOA more effective for solving FJSP. Figure 5 shows the mean convergence curve of the makespan in MFJS03 of the six algorithms in 10 separate runs. Figure 6 shows the convergence curve of the makespan in MFJS09 of six algorithms in 10 independent runs. It can be seen that DOLGOA obtains the best result. Figures 7 and 8 illustrate the Gantt charts of the optimal solutions obtained by DOLGOA in a featured run for problem MFJS03 and MFJS10, respectively. We can see that the shortest completion time solved by DOLGOA algorithm is 489 and 1517 for MFJS03 and MFJS10, respectively. Figure 9 shows the convergence curve of the average results of ten runs obtained by DOLGOA for the large size experiments. In addition, Figure 10 shows the Gantt chart of the optimal solutions obtained by DOLGOA for the large size experiments. In the large size problem LFJS01, there are 15 jobs to be processed by 10 machines in a workshop, where each job consists of 2–4 processes and each process can only be completed by several specified machines. It can be seen that DOLGOA can assign a series of optional machines to a specified process to obtain the best solution. As shown in Figure 7, the optimal solution obtained by DOLGOA for LFJS01 is 31. In Table 9, we list the computational time of these 6 algorithms to solve FJSP, and all the simulations run on an Intel(R) Core(TM) i5-9400F CPU@2.90 GHz PC and the Matlab(R) 2019a software platform.Figure 5
Convergence results of MFJS03 for all the compared algorithms.Figure 6
Convergence results of MFJS09 for all the compared algorithms.Figure 7
Gantt chart of an optimal solution to MFJS03 obtained by DOLGOA.Figure 8
Gantt chart of an optimal solution to MFJS10 obtained by DOLGOA.Figure 9
Convergence results on LFJS01.Figure 10
Gantt chart on LFJS01.Table 9
The CPU time periods obtained by algorithms for solving FJSP.
AlgorithmsDOLGOAGOAPSOJayaDEGWOMFJS016.897.536.884.194.183.02MFJS026.547.816.664.754.263.03MFJS037.188.207.865.344.863.38MFJS047.758.528.735.915.453.82MFJS057.828.518.636.005.503.85MFJS068.559.069.926.686.164.34MFJS0710.3110.5712.858.338.375.74MFJS0811.1311.1614.308.879.026.25MFJS0912.68∗12.2816.6610.4410.577.46MFJS1013.6812.9918.2410.8811.347.85SFJS013.755.702.231.191.360.97SFJS023.595.322.211.161.341.00SFJS034.235.582.841.531.671.33SFJS044.195.722.981.531.751.33SFJS054.215.813.064.191.701.31SFJS065.026.224.334.752.521.95SFJS075.316.534.675.342.861.99SFJS085.136.654.495.912.671.91SFJS095.086.514.456.002.561.95SFJS105.786.955.896.683.352.51


## 6. Conclusion

In this paper, a new variant of GOA named DOLGOA is proposed, which embeds DOL strategy into GOA to prevent it from falling into local optimum. The asymmetric and dynamic nature of DOL helps DOLGOA possess better exploitation and exploration capabilities than GOA. The performance of the proposed DOLGOA algorithm is evaluated in 23 benchmarks from CEC2014, and the proposed algorithm is applied in 21 FJSP problems. Comprehensive results show that DOLGOA behaves the best when solving numerical benchmarks and is well-performed for FJSP problems in different scales. The proposed algorithm is promising to be applied in solving various engineering optimization problems.



---

*Source: 8870783-2020-12-30.xml*