# An Advanced Chemical Reaction Optimization Algorithm Based on Balanced Local and Global Search

Authors: Min Zhang; Liang Chen; Xin Chen
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

An advanced chemical reaction optimization algorithm based on balanced local search and global search is proposed, which combines the advantages of adaptive chemical reaction optimization (ACRO) and particle swarm optimization (PSO), to solve continuous optimization problems. This new optimization is mainly based on the framework of ACRO, with PSO’s global search operator applied as part of ACRO’s neighborhood search operator. Moreover, a “finish” operator is added to the ACRO’s structure and the search operator is evolved by an adaptive scheme. The simulation results tested on a set of twenty-three benchmark functions, and a comparison was made with the results of a newly proposed hybrid algorithm based on chemical reaction optimization (CRO) and particle swarm optimization (denoted as HP-CRO). The finial comparison results show the superior performance improvement over HP-CRO in most experiments.


---

## Body

## 1. Introduction

We often encounter optimization problems in scientific and technological research and development. Over the past decades, a series of optimization algorithms have been proposed: genetic algorithm (GA) (see, e.g., [1]), simulated annealing (SA) (see, e.g., [2]), ant colony optimization (ACO) (see, e.g., [3]), particle swarm optimization (PSO) (see, e.g., [4]), chemical reaction optimization (CRO) (see, e.g., [5]), and others. The optimization algorithms mentioned above are with the same objective, that is, to find a best (or optimal) solution.In general, when faced with an optimization problem, we can always simplify it as follows: a solutions and a solution space S, an objective function f, and a set of constraints (assume there are m constraints), c1x,c2x,…,cm(x), which confine the search region, respectively. A particular solution s is usually represented by a vector of variables x={x1,x2,…,xn}, where n corresponds to the problem dimensions.The optimality ofx is evaluated by an objective function f and its output value y, that is, y=f(x). Our objective can be to either maximize or minimize f. In this paper we assume the latter. Then our goal is to find the minimum solution s∗∈S where f(s∗)≤f(s),  ∀s∈S. Then a minimization problem can be described as follows:(1)minx∈Rnsubject  tocix=0,i∈Ecix≤0,i∈I,where R, E, and I represent the real number set, the index set for equalities, and the index set for inequalities, respectively. The No-Free-Lunch theorem states that all metaheuristics which search for extreme are exactly the same in performance when averaged over all possible objective function (see, e.g., [6]). In other words, when one works excellent in a certain class of problems, it will be outperformed by the others in other classes.In recent years, CRO has been proposed and attracted an increasing interest from the community of optimization algorithms, a variety of improved algorithms based on CRO has been suggested (see, e.g., [7–10]) and it has been applied in many fields (see, e.g., [11–15]). Of all these algorithms, adaptive chemical reaction optimization (ACRO) stands out and shows its strong superiority. PSO has been applied in variety of fields and shows its higher convergence speed. However, it usually converges to local minimum quickly and loses the opportunity to find a better one.According to the introduction mentioned above, ACRO seems to be a well-performed optimization algorithm. However, similar to CRO, ACRO is still lacking in convergence speed. In order to avoid weaknesses of ACRO and PSO, we proposed a new algorithm which combines the advantages of both (denoted as AACRO).The rest of the paper is organized as follows. Section briefly outlines the related works in this paper and gives the inspiration of our proposed algorithm. We explain the modifications of ACRO and introduce the basic framework of AACRO in Section. In Section, we propose the proof on convergence and provide the convergence speed analysis. In Section, we describe 23 benchmark problems. In Section, we present the simulations results and compare the results of AACRO and HP-CRO. In particular, Section presents the experimental environment, parameter settings are shown in Section, and Section gives the comparison results. We conclude this paper and give some potential future works in Section.A good optimization algorithm must have a good global search performance as well as a good local search performance. However, global search and local search performance are always confined to each other in practice. For example, if an optimization algorithm is good at global search then it must be poor at local search and vice versa. In order to achieve the best performance, the two abilities should be well balanced.


## 2. Related Works

### 2.1. The Adaptive Chemical Reaction Algorithm

As an improvement of CRO, ACRO is proposed by Yu et al. in 2015 (see, e.g., [9]) and substantially inherits the standard CRO’s structure. ACRO reduces the number of parameters defined in canonical from eight (initial population size(inipopsize), initial molecular kinetic energy(iniKE), initial central energy buffer(iniBuffer), molecular collision rate(CollRate), energy loss rate(LossRate), decomposition occurrence threshold(DecThres), synthesis occurrence threshold(SynThres), and perturbation step size(StepSize)) to three classes (energy-related, reaction-related, and real-coded-related) and makes the occurrence of elementary reactions adaptive.The energy-related class includesiniKE,iniBuffer, andLossRate. The modifications of the parameters are as follows:(2)iniKE=PEωl-PEωs×iniPopSize,LossRate~N0,r2,iniBuffer=0,where PEωl and PEωs are molecules with the largest and the smallest PE and the value forLossRate of each molecule is approximated by a modified folded normal distribution, which is generated from a normal distribution with a mean value of 0 and standard deviation of r.The reaction-related class includesCollRate,SynThres, andDecThres. A new parameterChangeRate has been introduced to replace the original parametersSynThres andDecThres to control the frequency of decompositions and syntheses. And in order to control the number of molecules, fpop, fdec, and fsyn have been introduced to the system; then the population feedback term is modified as follows:(3)fpop=curPopSize-iniPopSizeiniPopSize,fdec=12×1-fpop,fsyn=1-fdec=12×1+fpop,wherecurPopSize is the current population size andiniPopSize is the initial population size. fdec and fsyn determine that the probability the current iteration is a decomposition and a synthesis, respectively.The real-code-related class includesStepSize. In order to solve the continuous optimization problems, the parameterStepSize needs to keep changing with iterations. The modification inStepSize is twofold.(1  ) Initial Value of StepSize (4) S t e p S i z e init , i = B o u n d upper , i - B o u n d lower , i 2 ,where StepSizeinit,i is the initialStepSize for the ith element in the solution and Boundupper,i and Boundlower,i are the upper and lower bounds for the ith element, respectively.(  2) Evolution of StepSize. The strategy “1/5 success rule” (see, e.g., [16]) has been adopted to modifyStepSize in the course of searching. This rule was originally stated as follows.After everyn mutations, check how many successes have occurred over the preceding 10n mutations. If the number is less than 2n, multiply the step lengths by the factor 0.85; divide them by 0.85 if more than 2n successes occurred.Besides these parameter modifications, the framework of ACRO is similar to the canonical CRO. ACRO also satisfies two thermodynamics laws and four basic reactions (i.e., on-wall ineffective collision, decomposition, intermolecular ineffective collision, and synthesis).


#### 2.1.1. On-Wall Ineffective Collision Operator

An on-wall ineffective collision represents the situation when a molecule collides with the container (i.e.,ω→ω′). This can be done by picking ω′ in the neighborhood of ω, so it only leads to a small change of the previous molecule’s structure. With the increasement of this elementary reaction, more and more KE will be transferred to the buffer and offers the energy needed in decomposition. This process can be regarded as a kind of local search of the solution space.


#### 2.1.2. Intermolecular Ineffective Collision Operator

Intermolecular ineffective collision takes place when molecules collide with each other and then bounce away. The molecules (assume two) (i.e.,ω1+ω2→ω1′+ω2′) remain unchanged before and after the process. This elementary reaction is very similar to the on-wall ineffective collision operator but no external buffer is involved. The new molecules ω1′ and ω2′ are generated from their own neighborhoods. This process can also be regarded as a kind of local research.


#### 2.1.3. Decomposition Operator

Decomposition refers to the situation when a molecule hits the wall and breaks into several parts (for simplicity, we only consider two parts, i.e.,ω→ω1′+ω2′). The idea of decomposition is to allow the system to explore other regions of the solution space after enough local search by the ineffective collisions, so this process can be regarded as a local search over a wider range.


#### 2.1.4. Synthesis Operator

A synthesis happens when multiple (assume two) molecules collide with each other and then fuse together (i.e.,ω1+ω2→ω′). The resulting molecules have a higher “ability” to explore a new solution region. In other words, the resultant molecule may appear in a region farther away from the existing ones in the solution space. The idea behind synthesis is a kind of global research.Based on the framework introduced above, we can formulate ACRO algorithm as Algorithm1.Algorithm 1:ACRO algorithm.
(1) Input: Objective function f, constraints (2) ∖∖Initialization (3) Set iniPopSize, iniKE, buffer, CollRate, iter, ChangeRateandStepSize (4) Create PopSize number of molecules (5) ∖∖Iterations (6) while (the stopping criteria not met) do (7)if  iter% n=0 and iter/n> 10 (8)if totalsuccess   (iter-10n)>=2n (9)StepSize= StepSize/0.85 (10)else (11)StepSize= StepSize× 0.85 (12)endif (13)endif (14) Generate b∈[0,1] (15)ifb>CollRatethen (16)Randomly select one molecule (17)if Decomposition criterion met then (18)Trigger Decomposition (19)else (20)Trigger On-wall Ineffective Collision (21)endif (22)else (23) Randomly select two molecules (24)ifSynthesis criterion met then (25)Trigger Synthesis (26)else (27)Trigger Inter-molecular Ineffective Collision (28)endif (29)endif (30)Check for any new minimum solution (31) endwhile (32) ∖∖The final stage (33) Output the best solution found and its objective function value


### 2.2. Particle Swarm Optimization Algorithm

Similar to CRO, the PSO searches the solution space by using a series of particles, which is randomly distributed in initial search spaceD. Each particle has its own attributes (i.e., ith particle has three attributes, including its position vector xi=(xi1,…,xid,…,xiD), velocity vi=(vi1,…,vid,…,viD), and its best location found so far pi=(pi1,…,pid,…,piD)), and the position of each particle is determined by its own flight experience as well as the swarm’s optimal position. Based on the rules of PSO, the update process from iteration k to k+1 becomes the following:(5)vik+1=wvik+c1ζ1kpik-xik+c2ζ2kgsk-xik,xik+1=xik+vik+1,where vik denotes the velocity of particle i in iteration k; xik denotes the position of particle i in iteration k; pik is the optimal solution found by particle i;gsk is the global optimal solution; w is the inertia weight; c1 is the cognitive weight and c2 is the social weight; ζ1k and ζ2k are random numbers uniformly distributed in [0,1].


### 2.3. Inspiration of Advanced Adaptive Chemical Reaction Optimization Algorithm

PSO is famous with its high convergence speed. However, high convergence speed ability may lead to inadequate local search and a high probability of falling into local optimum. Moreover, CRO was proposed as a new algorithm; it demonstrates strong local search ability. As an advanced algorithm based on CRO, ACRO simplifies the CRO’s structure in a wide range and makes theStepSize adaptive, which further improves CRO’s performance.CRO’s strong local search performance and PSO’s excellent global search performance make the combination of the two algorithms an inevitable trend. The algorithm HP-CRO (see, e.g., [17]) proposed by Nguyen et al. combines both algorithms and achieves a good result.However, HP-CRO just replaces CRO’s decomposition and synthesis operators with PSO’s search operator, so it has the same global optimization operator as PSO, which brings about that the accuracy of the optimization depends largely on the parameter settings of the PSO algorithm. In other words, if there exits an incorrect parameter setting, the optimization result may be poor, which greatly weakens the performance of the HP-CRO algorithm. Moreover, without an adaptive scheme, the fixed parameter settings in CRO algorithm greatly limit the accuracy of algorithm optimization.In order to overcome the shortcomings mentioned above, AACRO is proposed. In next section, the detailed algorithm for AACRO is designed.


## 2.1. The Adaptive Chemical Reaction Algorithm

As an improvement of CRO, ACRO is proposed by Yu et al. in 2015 (see, e.g., [9]) and substantially inherits the standard CRO’s structure. ACRO reduces the number of parameters defined in canonical from eight (initial population size(inipopsize), initial molecular kinetic energy(iniKE), initial central energy buffer(iniBuffer), molecular collision rate(CollRate), energy loss rate(LossRate), decomposition occurrence threshold(DecThres), synthesis occurrence threshold(SynThres), and perturbation step size(StepSize)) to three classes (energy-related, reaction-related, and real-coded-related) and makes the occurrence of elementary reactions adaptive.The energy-related class includesiniKE,iniBuffer, andLossRate. The modifications of the parameters are as follows:(2)iniKE=PEωl-PEωs×iniPopSize,LossRate~N0,r2,iniBuffer=0,where PEωl and PEωs are molecules with the largest and the smallest PE and the value forLossRate of each molecule is approximated by a modified folded normal distribution, which is generated from a normal distribution with a mean value of 0 and standard deviation of r.The reaction-related class includesCollRate,SynThres, andDecThres. A new parameterChangeRate has been introduced to replace the original parametersSynThres andDecThres to control the frequency of decompositions and syntheses. And in order to control the number of molecules, fpop, fdec, and fsyn have been introduced to the system; then the population feedback term is modified as follows:(3)fpop=curPopSize-iniPopSizeiniPopSize,fdec=12×1-fpop,fsyn=1-fdec=12×1+fpop,wherecurPopSize is the current population size andiniPopSize is the initial population size. fdec and fsyn determine that the probability the current iteration is a decomposition and a synthesis, respectively.The real-code-related class includesStepSize. In order to solve the continuous optimization problems, the parameterStepSize needs to keep changing with iterations. The modification inStepSize is twofold.(1  ) Initial Value of StepSize (4) S t e p S i z e init , i = B o u n d upper , i - B o u n d lower , i 2 ,where StepSizeinit,i is the initialStepSize for the ith element in the solution and Boundupper,i and Boundlower,i are the upper and lower bounds for the ith element, respectively.(  2) Evolution of StepSize. The strategy “1/5 success rule” (see, e.g., [16]) has been adopted to modifyStepSize in the course of searching. This rule was originally stated as follows.After everyn mutations, check how many successes have occurred over the preceding 10n mutations. If the number is less than 2n, multiply the step lengths by the factor 0.85; divide them by 0.85 if more than 2n successes occurred.Besides these parameter modifications, the framework of ACRO is similar to the canonical CRO. ACRO also satisfies two thermodynamics laws and four basic reactions (i.e., on-wall ineffective collision, decomposition, intermolecular ineffective collision, and synthesis).


### 2.1.1. On-Wall Ineffective Collision Operator

An on-wall ineffective collision represents the situation when a molecule collides with the container (i.e.,ω→ω′). This can be done by picking ω′ in the neighborhood of ω, so it only leads to a small change of the previous molecule’s structure. With the increasement of this elementary reaction, more and more KE will be transferred to the buffer and offers the energy needed in decomposition. This process can be regarded as a kind of local search of the solution space.


### 2.1.2. Intermolecular Ineffective Collision Operator

Intermolecular ineffective collision takes place when molecules collide with each other and then bounce away. The molecules (assume two) (i.e.,ω1+ω2→ω1′+ω2′) remain unchanged before and after the process. This elementary reaction is very similar to the on-wall ineffective collision operator but no external buffer is involved. The new molecules ω1′ and ω2′ are generated from their own neighborhoods. This process can also be regarded as a kind of local research.


### 2.1.3. Decomposition Operator

Decomposition refers to the situation when a molecule hits the wall and breaks into several parts (for simplicity, we only consider two parts, i.e.,ω→ω1′+ω2′). The idea of decomposition is to allow the system to explore other regions of the solution space after enough local search by the ineffective collisions, so this process can be regarded as a local search over a wider range.


### 2.1.4. Synthesis Operator

A synthesis happens when multiple (assume two) molecules collide with each other and then fuse together (i.e.,ω1+ω2→ω′). The resulting molecules have a higher “ability” to explore a new solution region. In other words, the resultant molecule may appear in a region farther away from the existing ones in the solution space. The idea behind synthesis is a kind of global research.Based on the framework introduced above, we can formulate ACRO algorithm as Algorithm1.Algorithm 1:ACRO algorithm.
(1) Input: Objective function f, constraints (2) ∖∖Initialization (3) Set iniPopSize, iniKE, buffer, CollRate, iter, ChangeRateandStepSize (4) Create PopSize number of molecules (5) ∖∖Iterations (6) while (the stopping criteria not met) do (7)if  iter% n=0 and iter/n> 10 (8)if totalsuccess   (iter-10n)>=2n (9)StepSize= StepSize/0.85 (10)else (11)StepSize= StepSize× 0.85 (12)endif (13)endif (14) Generate b∈[0,1] (15)ifb>CollRatethen (16)Randomly select one molecule (17)if Decomposition criterion met then (18)Trigger Decomposition (19)else (20)Trigger On-wall Ineffective Collision (21)endif (22)else (23) Randomly select two molecules (24)ifSynthesis criterion met then (25)Trigger Synthesis (26)else (27)Trigger Inter-molecular Ineffective Collision (28)endif (29)endif (30)Check for any new minimum solution (31) endwhile (32) ∖∖The final stage (33) Output the best solution found and its objective function value


## 2.1.1. On-Wall Ineffective Collision Operator

An on-wall ineffective collision represents the situation when a molecule collides with the container (i.e.,ω→ω′). This can be done by picking ω′ in the neighborhood of ω, so it only leads to a small change of the previous molecule’s structure. With the increasement of this elementary reaction, more and more KE will be transferred to the buffer and offers the energy needed in decomposition. This process can be regarded as a kind of local search of the solution space.


## 2.1.2. Intermolecular Ineffective Collision Operator

Intermolecular ineffective collision takes place when molecules collide with each other and then bounce away. The molecules (assume two) (i.e.,ω1+ω2→ω1′+ω2′) remain unchanged before and after the process. This elementary reaction is very similar to the on-wall ineffective collision operator but no external buffer is involved. The new molecules ω1′ and ω2′ are generated from their own neighborhoods. This process can also be regarded as a kind of local research.


## 2.1.3. Decomposition Operator

Decomposition refers to the situation when a molecule hits the wall and breaks into several parts (for simplicity, we only consider two parts, i.e.,ω→ω1′+ω2′). The idea of decomposition is to allow the system to explore other regions of the solution space after enough local search by the ineffective collisions, so this process can be regarded as a local search over a wider range.


## 2.1.4. Synthesis Operator

A synthesis happens when multiple (assume two) molecules collide with each other and then fuse together (i.e.,ω1+ω2→ω′). The resulting molecules have a higher “ability” to explore a new solution region. In other words, the resultant molecule may appear in a region farther away from the existing ones in the solution space. The idea behind synthesis is a kind of global research.Based on the framework introduced above, we can formulate ACRO algorithm as Algorithm1.Algorithm 1:ACRO algorithm.
(1) Input: Objective function f, constraints (2) ∖∖Initialization (3) Set iniPopSize, iniKE, buffer, CollRate, iter, ChangeRateandStepSize (4) Create PopSize number of molecules (5) ∖∖Iterations (6) while (the stopping criteria not met) do (7)if  iter% n=0 and iter/n> 10 (8)if totalsuccess   (iter-10n)>=2n (9)StepSize= StepSize/0.85 (10)else (11)StepSize= StepSize× 0.85 (12)endif (13)endif (14) Generate b∈[0,1] (15)ifb>CollRatethen (16)Randomly select one molecule (17)if Decomposition criterion met then (18)Trigger Decomposition (19)else (20)Trigger On-wall Ineffective Collision (21)endif (22)else (23) Randomly select two molecules (24)ifSynthesis criterion met then (25)Trigger Synthesis (26)else (27)Trigger Inter-molecular Ineffective Collision (28)endif (29)endif (30)Check for any new minimum solution (31) endwhile (32) ∖∖The final stage (33) Output the best solution found and its objective function value


## 2.2. Particle Swarm Optimization Algorithm

Similar to CRO, the PSO searches the solution space by using a series of particles, which is randomly distributed in initial search spaceD. Each particle has its own attributes (i.e., ith particle has three attributes, including its position vector xi=(xi1,…,xid,…,xiD), velocity vi=(vi1,…,vid,…,viD), and its best location found so far pi=(pi1,…,pid,…,piD)), and the position of each particle is determined by its own flight experience as well as the swarm’s optimal position. Based on the rules of PSO, the update process from iteration k to k+1 becomes the following:(5)vik+1=wvik+c1ζ1kpik-xik+c2ζ2kgsk-xik,xik+1=xik+vik+1,where vik denotes the velocity of particle i in iteration k; xik denotes the position of particle i in iteration k; pik is the optimal solution found by particle i;gsk is the global optimal solution; w is the inertia weight; c1 is the cognitive weight and c2 is the social weight; ζ1k and ζ2k are random numbers uniformly distributed in [0,1].


## 2.3. Inspiration of Advanced Adaptive Chemical Reaction Optimization Algorithm

PSO is famous with its high convergence speed. However, high convergence speed ability may lead to inadequate local search and a high probability of falling into local optimum. Moreover, CRO was proposed as a new algorithm; it demonstrates strong local search ability. As an advanced algorithm based on CRO, ACRO simplifies the CRO’s structure in a wide range and makes theStepSize adaptive, which further improves CRO’s performance.CRO’s strong local search performance and PSO’s excellent global search performance make the combination of the two algorithms an inevitable trend. The algorithm HP-CRO (see, e.g., [17]) proposed by Nguyen et al. combines both algorithms and achieves a good result.However, HP-CRO just replaces CRO’s decomposition and synthesis operators with PSO’s search operator, so it has the same global optimization operator as PSO, which brings about that the accuracy of the optimization depends largely on the parameter settings of the PSO algorithm. In other words, if there exits an incorrect parameter setting, the optimization result may be poor, which greatly weakens the performance of the HP-CRO algorithm. Moreover, without an adaptive scheme, the fixed parameter settings in CRO algorithm greatly limit the accuracy of algorithm optimization.In order to overcome the shortcomings mentioned above, AACRO is proposed. In next section, the detailed algorithm for AACRO is designed.


## 3. An Advanced Chemical Reaction Optimization Algorithm Based on Balanced Local Search and Global Search

This section focuses on discussing the infrastructure and basic principles of the AACRO algorithm.


### 3.1. Basic Modifications

In order to make ACRO and PSO organically combined, we modify 2 parameters of ACRO and introduce a finish operator. The details are as follows.


#### 3.1.1. Changing ACRO’s Neighborhood Operator by Adding PSO’s Search Operator (pik and gsk)

As we can see in Section,pik and gsk refer to ith particle’s optimal solution and the global best solution. PSO’s high convergence speed is closely related to these two parameters. Add these to ACRO’s search operator will also lead to a high convergence speed. However, if we simply add them together, then the ACRO’s search operator will be the same as the PSO’s, which will lead to a premature convergence. To solve this, we define a new parameterw_global to control whether it is a global search or a local search. Then the ACRO’s neighborhood operator becomes the following:(6)Nω=sΔ+r1×c1ζ1PBest-ω+c2ζ2GBest-ω,where the value of r1 is manly dependent on a randomly generated number r2 distributed in [0,1]. If the value of r2 is larger thanw_global, we set r1=1, else r1=0. sΔ~N(0,StepSize) is also a random number generated by Gaussian distribution. N(ω) is the neighborhood operator. Equation (6) combines global search operator and local search operator with each other; the value of parameterw_global can be set manually and change in schedule, which increases the flexibility of the algorithm.


#### 3.1.2. Modifying Synthesis and Decomposition Criterion

With the change of the neighborhood search operator, AACRO will have a higher convergence speed, if synthesis operator conducts in a relatively fast frequency then the population diversity cannot be maintained. On the other hand, if there are too many decomposition reactions, the total amount of the molecules will shoot up, which turns the algorithm into an unordered search. So if molecule amount is less than one-half of the original molecule amount, the synthesis operator is suspended; the decomposition operator is prohibited if the number of molecules is more than doubled.


#### 3.1.3. Introducing a “Finish” Operator

At the end of the iteration, we introduce a finish operator. If the molecules are more than two, we continuously choose two molecules from the existing molecular population randomly and conduct the synthesis operator. The optimal particle is obtained until the number of molecules is reduced to one. The difference is that the new molecule produced by the operator will be reserved if itsPE is less than the global minima, otherwise give up. The finish operator is somewhat similar to the crossover operator of genetic algorithm, the only difference is that the finish operator combines Darwin’s theory of evolution in the “survival of the fittest” thought (see, e.g., [18]) and just selects the final optimum solution. The steps of the finish operator can be described as shown in Algorithm 2.Algorithm 2:The finish operator.
(1) Get current PopSize (2) whilePopSize≥2 (3) choose two molecules randomly, conduct synthesis reaction (4) if PEω′≤MinPEthen (5)popsize=popsize-1,MinPE=PEω′ (6)endif (7) update molecules, update PopSize (8) endwhile (9) Output optimal solution


### 3.2. The Framework of AACRO

After some structure changes, we establish the framework of AACRO. Similar to other optimization algorithms, there are also three stages in AACRO: initialization, iteration, and the final stage. Figure1 shows its flow chart.Figure 1
Flow chart of AACRO.In the first stage, all parameters need to be initialized. In this step, the state space and some constraints are defined first; then we produce the molecule swarm by generatingPopSize numbers of solutions randomly in the solution space; at last, the PE and KE of each molecule are initialized.In the iteration stage, a number of iterations are performed. In each iteration, we first determine whether a unimolecular collision or an intermolecular collision would happen by randomly generating a numberr in the interval [0,1] and comparing withCollRate. If r is larger thanCollRate, it will result in an intermolecular collision and two molecules are randomly chosen. If both of them satisfy the synthesis criterion (KE≤β), they combine through synthesis, or an intermolecular ineffective collision takes place. Otherwise, unimolecular collision is triggered and one molecule is randomly chosen. If it satisfies the decomposition criterion (NumHit-MinHit>α, where α is the duration tolerance without obtaining any new local minimum solution.), the molecule will experience a decomposition, else an on-wall ineffective collision will take place.In the final stage, a finish operator is triggered. The existing molecules will continuously take a synthesis reaction until the numbers of the molecules reduce to one. After each synthesis reaction, the new molecule is updated and the old ones are abandoned.We provide the source code (see, e.g., [19]), and the pseudocode of the details of AACRO is also given in Algorithm 3.Algorithm 3:Details of AACRO.
(1) Input: Objective function f and the parameter values (2) ∖∖Initialization (3) Set PopSize, w_global, ChangeRate, CollRate, LossRate andtotaliters (4) Create Swarm, PE, KE, StepSize, success (iter), n and MinPE (5) ∖∖Iterations (6) while (the stopping criteria not met) do (7) if (step size change rule met) then (8) if (“1/5 success rule” met) then (9) StepSize=StepSize×0.85 (10) else (11) StepSize=StepSize/0.85 (12) endif (13) endif (14) Generate b∈[0,1] (15) if(b<CollRate)then (16) Randomly select one molecule Mω (17) if (Decomposition criterion met) then (18) Trigger Decomposition (19) else (20) Trigger On-wall Ineffective Collision (21) endif (22) else (23) Randomly select two molecules Mω1 and Mω2 (24) if (synthesis criterion met) then (25) Trigger Synthesis (26) else (27) Trigger Inter-molecular Ineffective Collision (28) endif (29) endif (30) check for any new minimum solution (31) endwhile (32) Trigger Finish operator (33) Obtain the global optimal (34) Output the best solution found and its objective function value


### 3.3. The Differences between the CRO Versions

We can see from Section that the ACRO version is proposed as an improvement of canonical CRO version and in this section we continue to optimize the structure of ACRO, so the AACRO version is actually also an improvement of the canonical CRO version. Therefore, we conclude several modification experiences and analyze the differences between the canonical CRO, ACRO, and ACCRO version.As an initial version, the canonical CRO version builds its basic framework and shows its relatively balanced global search and local search abilities. However, it adopts fixed step size and unreasonable collision criterions, which results in a low optimization efficiency. So the promoted version ACCRO comes out, it greatly streamlines the structure of the canonical CRO version and adopts several adaptive strategies, which makes the canonical CRO adaptive and speeds up its optimization efficiency to some extent.The AACRO version inherits most of the adaptive strategies used in ACRO version and makes some further improvements. In order to solve the low efficiency at the beginning of the optimization process, we adopt PSO’s global search operator as part of ACRO’s neighborhood operator and use a new parameter to control whether it is a global search or a local search, which greatly enhances ACRO’s optimization efficiency. However, high optimization efficiency may lead to a premature convergence. To prevent this, we modify ACRO’s synthesis and decomposition criterions again and make some molecule amount restrictions to ensure a relatively high converge speed.So we can conclude that the ACRO and AACRO versions are both with adaptive strategies; what is more, the AACRO version has a higher convergence speed and owns a better search ability.


## 3.1. Basic Modifications

In order to make ACRO and PSO organically combined, we modify 2 parameters of ACRO and introduce a finish operator. The details are as follows.


### 3.1.1. Changing ACRO’s Neighborhood Operator by Adding PSO’s Search Operator (pik and gsk)

As we can see in Section,pik and gsk refer to ith particle’s optimal solution and the global best solution. PSO’s high convergence speed is closely related to these two parameters. Add these to ACRO’s search operator will also lead to a high convergence speed. However, if we simply add them together, then the ACRO’s search operator will be the same as the PSO’s, which will lead to a premature convergence. To solve this, we define a new parameterw_global to control whether it is a global search or a local search. Then the ACRO’s neighborhood operator becomes the following:(6)Nω=sΔ+r1×c1ζ1PBest-ω+c2ζ2GBest-ω,where the value of r1 is manly dependent on a randomly generated number r2 distributed in [0,1]. If the value of r2 is larger thanw_global, we set r1=1, else r1=0. sΔ~N(0,StepSize) is also a random number generated by Gaussian distribution. N(ω) is the neighborhood operator. Equation (6) combines global search operator and local search operator with each other; the value of parameterw_global can be set manually and change in schedule, which increases the flexibility of the algorithm.


### 3.1.2. Modifying Synthesis and Decomposition Criterion

With the change of the neighborhood search operator, AACRO will have a higher convergence speed, if synthesis operator conducts in a relatively fast frequency then the population diversity cannot be maintained. On the other hand, if there are too many decomposition reactions, the total amount of the molecules will shoot up, which turns the algorithm into an unordered search. So if molecule amount is less than one-half of the original molecule amount, the synthesis operator is suspended; the decomposition operator is prohibited if the number of molecules is more than doubled.


### 3.1.3. Introducing a “Finish” Operator

At the end of the iteration, we introduce a finish operator. If the molecules are more than two, we continuously choose two molecules from the existing molecular population randomly and conduct the synthesis operator. The optimal particle is obtained until the number of molecules is reduced to one. The difference is that the new molecule produced by the operator will be reserved if itsPE is less than the global minima, otherwise give up. The finish operator is somewhat similar to the crossover operator of genetic algorithm, the only difference is that the finish operator combines Darwin’s theory of evolution in the “survival of the fittest” thought (see, e.g., [18]) and just selects the final optimum solution. The steps of the finish operator can be described as shown in Algorithm 2.Algorithm 2:The finish operator.
(1) Get current PopSize (2) whilePopSize≥2 (3) choose two molecules randomly, conduct synthesis reaction (4) if PEω′≤MinPEthen (5)popsize=popsize-1,MinPE=PEω′ (6)endif (7) update molecules, update PopSize (8) endwhile (9) Output optimal solution


## 3.1.1. Changing ACRO’s Neighborhood Operator by Adding PSO’s Search Operator (pik and gsk)

As we can see in Section,pik and gsk refer to ith particle’s optimal solution and the global best solution. PSO’s high convergence speed is closely related to these two parameters. Add these to ACRO’s search operator will also lead to a high convergence speed. However, if we simply add them together, then the ACRO’s search operator will be the same as the PSO’s, which will lead to a premature convergence. To solve this, we define a new parameterw_global to control whether it is a global search or a local search. Then the ACRO’s neighborhood operator becomes the following:(6)Nω=sΔ+r1×c1ζ1PBest-ω+c2ζ2GBest-ω,where the value of r1 is manly dependent on a randomly generated number r2 distributed in [0,1]. If the value of r2 is larger thanw_global, we set r1=1, else r1=0. sΔ~N(0,StepSize) is also a random number generated by Gaussian distribution. N(ω) is the neighborhood operator. Equation (6) combines global search operator and local search operator with each other; the value of parameterw_global can be set manually and change in schedule, which increases the flexibility of the algorithm.


## 3.1.2. Modifying Synthesis and Decomposition Criterion

With the change of the neighborhood search operator, AACRO will have a higher convergence speed, if synthesis operator conducts in a relatively fast frequency then the population diversity cannot be maintained. On the other hand, if there are too many decomposition reactions, the total amount of the molecules will shoot up, which turns the algorithm into an unordered search. So if molecule amount is less than one-half of the original molecule amount, the synthesis operator is suspended; the decomposition operator is prohibited if the number of molecules is more than doubled.


## 3.1.3. Introducing a “Finish” Operator

At the end of the iteration, we introduce a finish operator. If the molecules are more than two, we continuously choose two molecules from the existing molecular population randomly and conduct the synthesis operator. The optimal particle is obtained until the number of molecules is reduced to one. The difference is that the new molecule produced by the operator will be reserved if itsPE is less than the global minima, otherwise give up. The finish operator is somewhat similar to the crossover operator of genetic algorithm, the only difference is that the finish operator combines Darwin’s theory of evolution in the “survival of the fittest” thought (see, e.g., [18]) and just selects the final optimum solution. The steps of the finish operator can be described as shown in Algorithm 2.Algorithm 2:The finish operator.
(1) Get current PopSize (2) whilePopSize≥2 (3) choose two molecules randomly, conduct synthesis reaction (4) if PEω′≤MinPEthen (5)popsize=popsize-1,MinPE=PEω′ (6)endif (7) update molecules, update PopSize (8) endwhile (9) Output optimal solution


## 3.2. The Framework of AACRO

After some structure changes, we establish the framework of AACRO. Similar to other optimization algorithms, there are also three stages in AACRO: initialization, iteration, and the final stage. Figure1 shows its flow chart.Figure 1
Flow chart of AACRO.In the first stage, all parameters need to be initialized. In this step, the state space and some constraints are defined first; then we produce the molecule swarm by generatingPopSize numbers of solutions randomly in the solution space; at last, the PE and KE of each molecule are initialized.In the iteration stage, a number of iterations are performed. In each iteration, we first determine whether a unimolecular collision or an intermolecular collision would happen by randomly generating a numberr in the interval [0,1] and comparing withCollRate. If r is larger thanCollRate, it will result in an intermolecular collision and two molecules are randomly chosen. If both of them satisfy the synthesis criterion (KE≤β), they combine through synthesis, or an intermolecular ineffective collision takes place. Otherwise, unimolecular collision is triggered and one molecule is randomly chosen. If it satisfies the decomposition criterion (NumHit-MinHit>α, where α is the duration tolerance without obtaining any new local minimum solution.), the molecule will experience a decomposition, else an on-wall ineffective collision will take place.In the final stage, a finish operator is triggered. The existing molecules will continuously take a synthesis reaction until the numbers of the molecules reduce to one. After each synthesis reaction, the new molecule is updated and the old ones are abandoned.We provide the source code (see, e.g., [19]), and the pseudocode of the details of AACRO is also given in Algorithm 3.Algorithm 3:Details of AACRO.
(1) Input: Objective function f and the parameter values (2) ∖∖Initialization (3) Set PopSize, w_global, ChangeRate, CollRate, LossRate andtotaliters (4) Create Swarm, PE, KE, StepSize, success (iter), n and MinPE (5) ∖∖Iterations (6) while (the stopping criteria not met) do (7) if (step size change rule met) then (8) if (“1/5 success rule” met) then (9) StepSize=StepSize×0.85 (10) else (11) StepSize=StepSize/0.85 (12) endif (13) endif (14) Generate b∈[0,1] (15) if(b<CollRate)then (16) Randomly select one molecule Mω (17) if (Decomposition criterion met) then (18) Trigger Decomposition (19) else (20) Trigger On-wall Ineffective Collision (21) endif (22) else (23) Randomly select two molecules Mω1 and Mω2 (24) if (synthesis criterion met) then (25) Trigger Synthesis (26) else (27) Trigger Inter-molecular Ineffective Collision (28) endif (29) endif (30) check for any new minimum solution (31) endwhile (32) Trigger Finish operator (33) Obtain the global optimal (34) Output the best solution found and its objective function value


## 3.3. The Differences between the CRO Versions

We can see from Section that the ACRO version is proposed as an improvement of canonical CRO version and in this section we continue to optimize the structure of ACRO, so the AACRO version is actually also an improvement of the canonical CRO version. Therefore, we conclude several modification experiences and analyze the differences between the canonical CRO, ACRO, and ACCRO version.As an initial version, the canonical CRO version builds its basic framework and shows its relatively balanced global search and local search abilities. However, it adopts fixed step size and unreasonable collision criterions, which results in a low optimization efficiency. So the promoted version ACCRO comes out, it greatly streamlines the structure of the canonical CRO version and adopts several adaptive strategies, which makes the canonical CRO adaptive and speeds up its optimization efficiency to some extent.The AACRO version inherits most of the adaptive strategies used in ACRO version and makes some further improvements. In order to solve the low efficiency at the beginning of the optimization process, we adopt PSO’s global search operator as part of ACRO’s neighborhood operator and use a new parameter to control whether it is a global search or a local search, which greatly enhances ACRO’s optimization efficiency. However, high optimization efficiency may lead to a premature convergence. To prevent this, we modify ACRO’s synthesis and decomposition criterions again and make some molecule amount restrictions to ensure a relatively high converge speed.So we can conclude that the ACRO and AACRO versions are both with adaptive strategies; what is more, the AACRO version has a higher convergence speed and owns a better search ability.


## 4. Convergence Proof and Convergence Speed Analysis

Similar to CRO, the operation of the AACRO algorithm is a process of repetitive operation of on-wall ineffective collisions, intermolecular ineffective collisions, decomposition, and synthesis operators. Each iteration process is related only to the state of the current population. Therefore, the AACRO algorithm process can also be modeled as a Markov chain (see, e.g., [20]) and the convergence of AACRO can be proved by using the characteristics of the Markov chain. However, it is worth noting that the search domain (i.e., state space S) of continuous constraint problem is often infinite; that is, the algorithm cannot be proved directly by using Markov chain property.To solve the problem above, we define a minimal step sizesΔ; if theStepSize generated by the neighborhood operator is smaller than sΔ,StepSize is equal to sΔ. Furthermore,StepSize in the ACRO algorithm will slowly decrease with the iteration, which leads to gradually reducing the actual search domain. With this feature, we can simplify the infinite search domain into a finite state space; then the convergence can be proved.


### 4.1. Algorithm Convergence Proof

Before the proof process, we first provide some basic definitions, assumptions, and corresponding inferences.Definition 1 (pseudomolecule).
A pseudomoleculeωϕ is an imaginary molecule with no attributes (i.e., PE and KE.).The purpose of introducing the pseudomolecule is to keep the numbers of the molecules constant.Definition 2 (state space).
Given a problemA, a state of AACRO can be described as follows:(7)SA=ω1A×ω2A×⋯×ωnmaxA,where ωiA denotes the state space of ith molecule and nmax⁡ is the maximum population size.Definition 3 (the best-so-far solution).
For a problemA, the best-so-far solution xtA,bsf is the current optimal solution found up to current iteration t, where t=0,1,2,….Definition 4 (absorbing Markov chain).
LetΩ be the set of states, where the probability of transiting from one absorbing state to another is 1. Then a Markov chain {St}t=0+∞ is absorbing if it satisfies(8)PSt+1∉Ω∣St∈Ω=0,t=0,1,2,….Theorem 5.
The optimizing process of AACRO on solving problemA can be modeled by a Markov chain {StA}t=0+∞.Proof.
We can see that the state spaceSt+1A at time t+1 is only dependent on the state StA at time t, namely, we have(9)PStA∈ΩA∣S0A,S1A,…,StA=PSt+1A∈ΩA∣StA,where P·∣· is the transition probability and ΩA is the state space on problem A. Equation (10) is a Markov property, so {StA}t=0+∞ is actually a Markov chain with state space ΩA. Besides, we can model AACRO as an absorbing Markov chain by an additional term xtA,bsf, the state space of iteration t is StA=xtA,bsf×ω1A×ω2A×⋯×ωnmaxA, and then we have PSt+1∉Ω∣St∈Ω=0, t=0,1,2,…, which makes AACRO an absorbing Markov chain.Definition 6 (nonattenuation sequence).
Let{σt}t=0+∞ be a sequence, where ∀t≥0, 0≤σt≤1. The sequence is nonattenuation if it satisfies ∏t=0+∞(1-σt)=0.Lemma 7.
Given an absorbing Markov chain{St}t=0+∞, there exists a nonattenuation sequence {σt}t=0+∞ such that PSt+1∉Ωopt∣St∈Ωopt≥σt for t=0,1,2,… if and only if the Markov chain is said to be convergent.Proof.
We first prove the sufficiency part. If fort=0,1,2,…,PSt+1∉Ωopt∣St∈Ωopt≥σt, it implies PSt+1∉Ωopt∣St∉Ωopt≤1-σt. Define(10)P~t=∏i=0tPSi+1∉Ωopt∣Si∉Ωopt.Then, we have(11)limt→∞P~t=∏i=0∞PSi+1∉Ωopt∣Si∉Ωopt≤∏i=0∞1-σi=0.Obviously, P~(t)≥0 for all t. From (11) we have P~(t)≤0; thus limt→∞⁡P~(t)=0. From the property of the absorbing Markov chain, we have(12)PSt+1∉Ωopt∣St∈Ωopt=0.Then(13)PSt+1∈Ωopt∣St∈Ωopt=1.Therefore(14)PSt+1∉Ωopt=PSt+1∉Ωopt∣St∈ΩoptPSt∈Ωopt+PSt+1∉Ωopt∣St∉ΩoptPSt∉Ωopt=PSt+1∉Ωopt∣St∉ΩoptPSt∉Ωopt=PS0∉Ωopt∏i=0tPSi+1∉Ωopt∣Si∉Ωopt=PS0∉ΩoptP~t.As limt→∞⁡P~(t)=0, we have limt→∞⁡P{St∉Ωopt}=0. Then(15)limt→∞PSt∈Ωopt=1-limt→∞PSt∉Ωopt=1.Therefore, the algorithm will reach the optimal state with probability 1 if iteration time tends to infinity.Necessity Part. If a Markov chain is convergent, we can see from Definition that if time tends to infinity, the probability that the state space St converges to the optimal space Ωopt is 1, that is, limt→∞⁡P{St∈Ωopt}=1, which is equivalent to(16)limt→∞PSt∉Ωopt=1-limt→∞PSt∈Ωopt=0.According to (11), we have(17)limt→∞⁡P~t=limt→∞⁡PSt∉ΩoptPS0∉Ωopt=1PS0∉Ωoptlimt→∞⁡PSt∉Ωopt=0.Therefore,(18)∏i=0∞PSi+1∉Ωopt∣Si∉Ωopt=0.Letσi=1-PSi+1∉Ωopt∣Si∉Ωopt; that is, (19)1-σi=PSi+1∉Ωopt∣Si∉Ωopt.Then ∏i=0+∞(1-σi)=0; by Definition, we have {σt}t=0+∞ is a nonattenuation sequence.As can be seen from the proof of necessity of Lemma, an absorbing Markov chain will reach the optimal state with probability 1 if iteration time tends to infinity. Furthermore, the AACRO algorithm can also be modeled as an absorbing Markov chain according to Theorem. So we can get AACRO can reach the optimal state with probability as long as the time allowed to evolve is sufficiently long.


### 4.2. Convergence Speed Analysis

As can be seen according to Definitions 11 and 12 in (see, e.g., [21]), the convergence rate at time t is defined as(20)πt=PSt∈Ωoptt=0,1,2,…,where Ωopt represents the optimal state set. The first hitting time in Definition 12 is denoted as(21)ETf=∑t=1∞tPSt∈Ωopt∩St-1∉Ωopt=∑t=1∞tπt-πt-1.From (20) and (21), we can see that the first hitting time and the convergence rate at time t are closely related. Intuitively speaking, the faster the convergence rate, the shorter the first collision time should be.Although it is difficult to derive accurate convergence rate and first hitting time from the above (20) and (21), it provides a good mathematical basis for analyzing the convergence rate of AACRO.This paper mainly studies the effect ofStepSize on convergence rate. First, the effect ofStepSize on the convergence rate is analyzed. For simplicity, it is assumed that the neighborhood operator is directly equal to the given step size, so that the continuous domain optimization problem becomes a discrete one, that is, the state space is finite.Since the molecules are randomly generated in the state space, the probability that any molecule converges to a region near to the optimal solution is as follows:(22)πt=Popt=popsize×SΔUb-Lbn,where Ub and Lb correspond to the upper bound and lower bound of the state space, respectively, SΔ is the optimal solution space,and n is the problem dimensions.It can be seen from (22) that if theStepSize is equal to the difference between the upper and lower bounds, the algorithm has been completely changed to a random search process, and its efficiency will be greatly reduced. So the maximum value of the general step is half of the difference between the upper and lower bounds. Moreover, if theStepSize is large, the probability of reaching the optimal solution from the initial stage space is larger; that is, the convergence rate is larger. However, if theStepSize still remained unchanged, the probability of getting a worse solution will increase since each iteration has a quite largeStepSize; we may have(23)PSi+1∉Ωopt∣Si∈Ωopt>0,which will result in reduction of the current convergence speed.If we changeStepSize by “1/5 success rule,” we will actually get a smaller search space (state space), then the state space and the convergence rate are changed as follows:(24)SA′=ω1A′×ω2A′×⋯×ωnmaxA′,πt=popsize×sΔUb-Lb/raten>πtinitial,where rate denotes the change rate of theStepSize and πtinitial represents the initial convergence speed.We can see from (24) that πt keeps increasing and maintains in a high speed. What is more, the neighborhood of AACRO combines the PSO’s search operator, which further enhances the convergence rate.It can be seen from the above analysis that the “1/5 success rule” strategy can greatly improve the convergence speed of the algorithm while the algorithm is guaranteed to converge on the global optimal solution.


## 4.1. Algorithm Convergence Proof

Before the proof process, we first provide some basic definitions, assumptions, and corresponding inferences.Definition 1 (pseudomolecule).
A pseudomoleculeωϕ is an imaginary molecule with no attributes (i.e., PE and KE.).The purpose of introducing the pseudomolecule is to keep the numbers of the molecules constant.Definition 2 (state space).
Given a problemA, a state of AACRO can be described as follows:(7)SA=ω1A×ω2A×⋯×ωnmaxA,where ωiA denotes the state space of ith molecule and nmax⁡ is the maximum population size.Definition 3 (the best-so-far solution).
For a problemA, the best-so-far solution xtA,bsf is the current optimal solution found up to current iteration t, where t=0,1,2,….Definition 4 (absorbing Markov chain).
LetΩ be the set of states, where the probability of transiting from one absorbing state to another is 1. Then a Markov chain {St}t=0+∞ is absorbing if it satisfies(8)PSt+1∉Ω∣St∈Ω=0,t=0,1,2,….Theorem 5.
The optimizing process of AACRO on solving problemA can be modeled by a Markov chain {StA}t=0+∞.Proof.
We can see that the state spaceSt+1A at time t+1 is only dependent on the state StA at time t, namely, we have(9)PStA∈ΩA∣S0A,S1A,…,StA=PSt+1A∈ΩA∣StA,where P·∣· is the transition probability and ΩA is the state space on problem A. Equation (10) is a Markov property, so {StA}t=0+∞ is actually a Markov chain with state space ΩA. Besides, we can model AACRO as an absorbing Markov chain by an additional term xtA,bsf, the state space of iteration t is StA=xtA,bsf×ω1A×ω2A×⋯×ωnmaxA, and then we have PSt+1∉Ω∣St∈Ω=0, t=0,1,2,…, which makes AACRO an absorbing Markov chain.Definition 6 (nonattenuation sequence).
Let{σt}t=0+∞ be a sequence, where ∀t≥0, 0≤σt≤1. The sequence is nonattenuation if it satisfies ∏t=0+∞(1-σt)=0.Lemma 7.
Given an absorbing Markov chain{St}t=0+∞, there exists a nonattenuation sequence {σt}t=0+∞ such that PSt+1∉Ωopt∣St∈Ωopt≥σt for t=0,1,2,… if and only if the Markov chain is said to be convergent.Proof.
We first prove the sufficiency part. If fort=0,1,2,…,PSt+1∉Ωopt∣St∈Ωopt≥σt, it implies PSt+1∉Ωopt∣St∉Ωopt≤1-σt. Define(10)P~t=∏i=0tPSi+1∉Ωopt∣Si∉Ωopt.Then, we have(11)limt→∞P~t=∏i=0∞PSi+1∉Ωopt∣Si∉Ωopt≤∏i=0∞1-σi=0.Obviously, P~(t)≥0 for all t. From (11) we have P~(t)≤0; thus limt→∞⁡P~(t)=0. From the property of the absorbing Markov chain, we have(12)PSt+1∉Ωopt∣St∈Ωopt=0.Then(13)PSt+1∈Ωopt∣St∈Ωopt=1.Therefore(14)PSt+1∉Ωopt=PSt+1∉Ωopt∣St∈ΩoptPSt∈Ωopt+PSt+1∉Ωopt∣St∉ΩoptPSt∉Ωopt=PSt+1∉Ωopt∣St∉ΩoptPSt∉Ωopt=PS0∉Ωopt∏i=0tPSi+1∉Ωopt∣Si∉Ωopt=PS0∉ΩoptP~t.As limt→∞⁡P~(t)=0, we have limt→∞⁡P{St∉Ωopt}=0. Then(15)limt→∞PSt∈Ωopt=1-limt→∞PSt∉Ωopt=1.Therefore, the algorithm will reach the optimal state with probability 1 if iteration time tends to infinity.Necessity Part. If a Markov chain is convergent, we can see from Definition that if time tends to infinity, the probability that the state space St converges to the optimal space Ωopt is 1, that is, limt→∞⁡P{St∈Ωopt}=1, which is equivalent to(16)limt→∞PSt∉Ωopt=1-limt→∞PSt∈Ωopt=0.According to (11), we have(17)limt→∞⁡P~t=limt→∞⁡PSt∉ΩoptPS0∉Ωopt=1PS0∉Ωoptlimt→∞⁡PSt∉Ωopt=0.Therefore,(18)∏i=0∞PSi+1∉Ωopt∣Si∉Ωopt=0.Letσi=1-PSi+1∉Ωopt∣Si∉Ωopt; that is, (19)1-σi=PSi+1∉Ωopt∣Si∉Ωopt.Then ∏i=0+∞(1-σi)=0; by Definition, we have {σt}t=0+∞ is a nonattenuation sequence.As can be seen from the proof of necessity of Lemma, an absorbing Markov chain will reach the optimal state with probability 1 if iteration time tends to infinity. Furthermore, the AACRO algorithm can also be modeled as an absorbing Markov chain according to Theorem. So we can get AACRO can reach the optimal state with probability as long as the time allowed to evolve is sufficiently long.


## 4.2. Convergence Speed Analysis

As can be seen according to Definitions 11 and 12 in (see, e.g., [21]), the convergence rate at time t is defined as(20)πt=PSt∈Ωoptt=0,1,2,…,where Ωopt represents the optimal state set. The first hitting time in Definition 12 is denoted as(21)ETf=∑t=1∞tPSt∈Ωopt∩St-1∉Ωopt=∑t=1∞tπt-πt-1.From (20) and (21), we can see that the first hitting time and the convergence rate at time t are closely related. Intuitively speaking, the faster the convergence rate, the shorter the first collision time should be.Although it is difficult to derive accurate convergence rate and first hitting time from the above (20) and (21), it provides a good mathematical basis for analyzing the convergence rate of AACRO.This paper mainly studies the effect ofStepSize on convergence rate. First, the effect ofStepSize on the convergence rate is analyzed. For simplicity, it is assumed that the neighborhood operator is directly equal to the given step size, so that the continuous domain optimization problem becomes a discrete one, that is, the state space is finite.Since the molecules are randomly generated in the state space, the probability that any molecule converges to a region near to the optimal solution is as follows:(22)πt=Popt=popsize×SΔUb-Lbn,where Ub and Lb correspond to the upper bound and lower bound of the state space, respectively, SΔ is the optimal solution space,and n is the problem dimensions.It can be seen from (22) that if theStepSize is equal to the difference between the upper and lower bounds, the algorithm has been completely changed to a random search process, and its efficiency will be greatly reduced. So the maximum value of the general step is half of the difference between the upper and lower bounds. Moreover, if theStepSize is large, the probability of reaching the optimal solution from the initial stage space is larger; that is, the convergence rate is larger. However, if theStepSize still remained unchanged, the probability of getting a worse solution will increase since each iteration has a quite largeStepSize; we may have(23)PSi+1∉Ωopt∣Si∈Ωopt>0,which will result in reduction of the current convergence speed.If we changeStepSize by “1/5 success rule,” we will actually get a smaller search space (state space), then the state space and the convergence rate are changed as follows:(24)SA′=ω1A′×ω2A′×⋯×ωnmaxA′,πt=popsize×sΔUb-Lb/raten>πtinitial,where rate denotes the change rate of theStepSize and πtinitial represents the initial convergence speed.We can see from (24) that πt keeps increasing and maintains in a high speed. What is more, the neighborhood of AACRO combines the PSO’s search operator, which further enhances the convergence rate.It can be seen from the above analysis that the “1/5 success rule” strategy can greatly improve the convergence speed of the algorithm while the algorithm is guaranteed to converge on the global optimal solution.


## 5. Test Problems

In order to compare the performance between our proposed AACRO algorithm over the HP-CRO algorithm, we use a set of standard benchmark functions used in (see, e.g., [8]). The benchmark functions are shown in Table 1, which contains 23 benchmark functions with different dimension sizes, solution space S, and of course different global minimums fmin, and they can be classified into three categories according to their different characteristics.Table 1
23 benchmark functions.
Category Test function Name n S f min ⁡ I f 1 ( x ) = ∑ i = 1 n x i 2 Sphere model 30 - 100,100 n 0 f 2 x = ∑ i = 1 n x i + ∏ i = 1 n x i Schwefel’s problem 2.22 30 - 10,10 n 0 f 3 ( x  ) = ∑ i = 1 n ∑ j = 1 i x j 2 Schwefel’s problem 1.2 30 - 100,100 n 0 f 4 ( x ) = max i ⁡ x i , 1 ≤ i ≤ n Schwefel’s problem 2.21 30 - 100,100 n 0 f 5 ( x ) = ∑ i = 1 n - 1 100 x i + 1 - x i 2 2 + x i - 1 2 Generalized Rosenbrock’s function 30 - 30,30 n 0 f 6 ( x ) = ∑ i = 1 n x i + 0.5 2 Step function 30 - 100,100 n 0 f 7 ( x ) = ∑ i = 1 n i x i 4 + random  0,1 Quartic function with noise 30 - 1.28,1.28 n 0  II f 8 x = - ∑ i = 1 n x i  s i n x i Generalized Schwefel’s problem 2.26 30 - 500,500 n −12569.5 f 9 ( x ) = ∑ i = 1 n x i 2 - 10 cos ⁡ 2 π x i + 10 Generalized Rastrigin’s function 30 - 5.12,5.12 n 0 f 10 ( x ) = - 20 exp ⁡ - 0.2 1 n ∑ i = 1 n x i 2 - exp ⁡ 1 n ∑ i = 1 n cos ⁡ 2 π x i + 20 + e Ackley’s function 30 - 32,32 n 0 f 11 ( x ) = 1 4000 ∑ i = 1 n x i 2 - ∏ i = 1 n cos ⁡ x i i + 1 Generalized Griewank function 30 - 600,600 n 0 f 12 ( x ) = π n { 10  sin 2 ⁡ π y 1 + ∑ i = 1 29 y i - 1 2 1 + 10  sin 2 ⁡ π y i + 1 + y n - 1 2 + ∑ i = 1 30 u x i , 10,100,4 yi=1+14xi+1 uxi,a,k,m=kxi-am,xi>a0,-a≤xi≤ak(-xi-a)m,xi<-a Generalized penalized functions 30 - 50,50 n 0 f 13 x = 0.1 { sin 2 ⁡ π 3 x 1 + ∑ i = 1 29 x i - 1 2 1 + sin 2 ⁡ 3 π x i + 1 + x n - 1 2 1 + sin 2 ⁡ 2 π x 30 + ∑ i = 1 30 u x i , 5,100,4 30 - 50,50 n 0  III f 14 ( x ) = 1 500 + ∑ j = 1 25 1 j + ∑ i = 1 2 ( x i - a i j ) 6 - 1 Shekel’s Foxholes function 2 - 65.536,65.536 n 1 f 15 x = ∑ i = 1 11 a i - x 1 b i 2 + b i x 2 b i 2 + b i x 3 + x 4 2 Kowalik’s function 4 - 5,5 n 0.0003075 f 16 x = 4 x 1 2 - 2.1 x 1 4 + 1 3 x 1 6 + x 1 x 2 - 4 x 2 2 + 4 x 2 4 Six-hump camel-back function 2 - 5,5 n −1.0316285 f 17 x = x 2 - 5.1 4 π 2 x 1 2 + 5 π x 1 - 6 2 + 10 1 - 1 8 π cos ⁡ x 1 + 10 Brain function 2 [ - 5,10 ] × [ 0,15 ] 0.398 f 18 x = 1 + x 1 + x 2 + 1 2 19 - 14 x 1 + 3 x 1 2 - 14 x 2 + 6 x 1 x 2 + 3 x 2 2 × 30 + 2 x 1 - 3 x 2 2 18 - 32 x 1 + 12 x 1 2 + 48 x 2 - 36 x 1 x 2 + 27 x 2 2 Goldstein-Price function 2 - 2,2 n 3 f 19 x = - ∑ i = 1 4 c i exp ⁡ - ∑ j = 1 4 a i j x j - p i j 2 Hartman’s family 3 0,1 n −3.86 f 20 x = - ∑ i = 1 4 c i exp ⁡ - ∑ j = 1 6 a i j x j - p i j 2 6 0,1 n −3.32 f 21 x = - ∑ i = 1 5 ( x - a i ) ( x - a i ) T + c i - 1 Shekel’s family 4 0,10 n −10 f 22 x  = - ∑ i = 1 7 x - a i ( x - a i ) T + c i - 1 4 0,10 n −10 f 23 x = - ∑ i = 1 10 x - a i ( x - a i ) T + c i - 1 4 0,10 n −10(1  ) Unimodal Functions. f1–f7 belong to unimodal functions and the problem dimension sizes are all 30. However, these functions are relatively easy to solve since there is only one global minimum in each function.(2  ) High-Dimensional Multimodal Functions. f8–f13 belong to multimodal functions. The problem dimension sizes are also 30 but there are many local minimums in each function, so functions f8-f13 are considered as the most difficult problems in these 23 benchmark functions.(3  ) Low-Dimensional Multimodal Functions. f14–f23 belong to low-dimensional multimodal functions. These functions are with the lowest problem dimensions and the search space S, and there exits some local minimums in each function, so they are more difficult than unimodal functions and easier than high-dimensional multimodal functions. The detailed introduction of these benchmark functions can be seen in [22].


## 6. Simulation Results

### 6.1. Experimental Environment

Both AACRO and HP-CRO are implemented in Matlab7.8. All simulations are performed on a computer with an Intel Core I5-4590 @ 3.3 GHz CPU and 4 GB of RAM in Windows 7 environment.


### 6.2. Parameter Setting

In order to achieve the best results, different test functions are set with different parameters and each simulation terminates when a certain number of function evaluations (NFEs) have been performed. The NFEs limits of AACRO for different test functions are listed in Table2; the parameter settings are listed in Table 3. The local weight and global weight of PSO are chosen as c1=c2=2.Table 2
Number of NFEs for functionf1–f23.
Name Function AACRO HP-CRO RCCRO Category I f 1 , f 2 , f 4 , f 5 , f 6 , f 7 150000 150000 150000 f 3 250000 250000 250000  Category II f 8 , f 10 , f 11 , f 12 , f 13 150000 150000 150000 f 9 250000 250000 250000  Category III f 14 , f 20 7500 7500 7500 f 15 250000 250000 250000 f 16 1250 1250 1250 f 17 5000 5000 5000 f 19 4000 4000 4000 f 18 , f 21 , f 22 , f 23 10000 10000 10000Table 3
Parameter settings for different categories.
Order Parameter Category I Category II Category III f 1 – f 7 f 8 – f 13 f 14 – f 18 f 19 – f 23 (1) PopSize 10 100 100 100 (2) w_local 0.2 0.5 0.8 0.8 (3) w_global 0.8 0.5 0.2 0.2 (4) CollRate 0.2 0.2 0.2 0.2 (5) LossRate 0.3 0.3 0.3 0.3 (6) IniKE 1000 1000 1000 1000 (7) buffer 0 0 0 0 (8) ChangeRate 0.001 0.001 0.001 0.001


### 6.3. Comparisons

This paper also provides the results of the RCCRO versions of RCCRO1 (RCCRO1, RCCRO2, and RCCRO4) and HP-CRO (HP-CRO1 and HP-CRO2). All versions tested 23 standard test functions. For each function, we run AACRO 25 times and obtain the averaged computed minimum value (mean) and standard deviation (StdDev). We rank the results from the lowest mean to the highest and get the average rank. Finally, we order the average rank and get the overall rank.As shown in Tables4–6, the overall rank of AACRO is best and HP-CRO versions rank 2nd, followed by RCCRO versions. It is worth noting that each version has its specialty. In other words, no algorithm can work best on all functions. The AACRO version outperforms on f1, f2, f4, f6, f1, f8, f10, f11, f12, f13, f14, f15, f16, f18, f19, f21, f22, and f23. HP-CRO versions are on f3, f5, f6, f9, and f17. RCCRO versions are on f6, f7, and f20.Table 4
The optimization computing results forf1–f7.
AACRO HP-CRO1 HP-CRO2 RCCRO1 RCCRO2 RCCRO4 f 1 Mean 5.70 E - 55 6.93 E - 50 1.17 E - 50 2.35 E - 07 2.24 E - 07 2.20 E - 07 StdDev 2.85 E - 55 3.39 E - 49 4.18 E - 50 4.70 E - 08 4.43 E - 08 3.83 E - 08 Rank 1 3 2 6 5 4 f 2 Mean 1.42 E - 08 4.22 E - 06 1.50 E - 05 2.18 E - 03 2.24 E - 03 2.16 E - 03 StdDev 8.89 E - 09 1.28 E - 05 3.50 E - 05 3.65 E - 04 4.14 E - 04 3.32 E - 04 Rank 1 2 3 5 6 4 f 3 Mean 8.77 E - 09 7.70 E - 94 8.31 E - 104 2.50 E - 07 2.57 E - 07 2.41 E - 07 StdDev 4.32 E - 08 3.77 E - 93 2.98 E - 103 9.35 E - 08 9.18 E - 08 8.60 E - 08 Rank 3 2 1 5 6 4 f 4 Mean 8.32 E - 10 4.16 E - 04 3.37 E - 04 9.28 E - 03 9.42 E - 03 8.74 E - 03 StdDev 5.88 E - 09 3.05 E - 04 2.99 E - 04 3.97 E - 03 4.92 E - 03 3.63 E - 03 Rank 1 3 2 5 6 4 f 5 Mean 1.13 E + 01 1.13 E + 01 5.52 E + 00 9.37 E + 01 7.45 E + 01 6.98 E + 01 StdDev 1.50 E + 01 1.53 E + 01 7.13 E + 00 9.61 E + 01 9.30 E + 01 1.03 E + 02 Rank 2 3 1 6 5 4 f 6 Mean 0 0 0 0 0 0 StdDev 0 0 0 0 0 0 Rank 1 1 1 1 1 1 f 7 Mean 6.42 E - 03 7.21 E - 03 7.02 E - 03 3.79 E - 03 3.69 E - 03 3.83 E - 03 StdDev 1.03 E - 02 2.31 E - 03 2.00 E - 03 1.25 E - 03 9.65 E - 04 1.31 E - 03 Rank 4 6 5 2 1 3  Average rank 1.8 2.8 2.1 3.4 4.2 3.4 Overall rank 1 3 2 4 6 5Table 5
The optimization computing results forf8–f13.
AACRO HP-CRO1 HP-CRO2 RCCRO1 RCCRO2 RCCRO4 f 8 Mean - 1.26 E  +  04 - 1.23 E + 04 - 1.26 E + 04 - 1.24 E + 04 - 1.23 E + 04 - 1.24 E + 04 StdDev 3.07 E + 01 1.79 E + 02 4.34 E + 01 7.11 E + 01 9.16 E + 01 6.94 E + 01 Rank 1 5 2 4 6 3 f 9 Mean 8.60 E - 03 3.80 E - 03 1.57 E - 03 1.85 E - 03 1.70 E - 03 1.59 E - 03 StdDev 8.02 E - 02 1.02 E - 02 6.07 E - 03 4.62 E - 04 4.86 E - 04 4.94 E - 04 Rank 6 5 1 4 3 2 f 10 Mean 1.32 E - 14 3.02 E - 13 1.12 E - 11 2.32 E - 03 2.16 E - 03 2.37 E - 03 StdDev 1.36 E - 14 9.44 E - 13 5.43 E - 11 4.43 E - 04 2.93 E - 04 3.83 E - 04 Rank 1 2 3 5 4 6 f 11 Mean 7.14 E - 02 1 1 1.00 E + 00 1.000001 1.00 E + 00 StdDev 1.41 E - 01 1.18 E - 14 3.02 E - 15 1.48 E - 07 2.02 E - 07 1.39 E - 07 Rank 1 3 2 4 6 5 f 12 Mean 1.22 E - 01 3.08 E - 01 1.54 E - 01 5.82 E - 01 3.56 E - 01 1.60 E - 01 StdDev 8.45 E - 01 5.19 E - 01 2.33 E - 01 8.03 E - 01 5.99 E - 01 2.76 E - 01 Rank 1 4 2 6 5 3 f 13 Mean 3.75 E - 32 2.63 E - 14 3.81 E - 14 6.66 E - 06 7.71 E - 06 6.46 E - 06 StdDev 7.74 E - 32 8.96 E - 14 1.24 E - 13 4.85 E - 06 7.95 E - 06 4.56 E - 06 Rank 1 2 3 5 6 4  Average rank 1.8 3.5 2.1 4.6 5 3.8 Overall rank 1 3 2 5 6 4Table 6
The optimization computing results forf14–f23.
AACRO HP-CRO1 HP-CRO2 RCCRO1 RCCRO2 RCCRO4 f 14 Mean 9.98 E - 01 1.04 E + 00 9.98 E - 01 2.70 E + 00 3.55 E + 00 3.49 E + 00 StdDev 1.01 E - 09 1.95 E - 01 9.64 E - 07 1.81 E + 00 1.74 E + 00 2.58 E + 00 Rank 1 3 2 4 6 5 f 15 Mean 3.07 E - 04 1.31 E - 03 3.90 E - 04 5.63 E - 04 5.39 E - 04 5.39 E - 04 StdDev 5.17 E - 13 3.95 E - 03 2.46 E - 04 8.56 E - 05 1.10 E - 04 9.58 E - 05 Rank 1 6 2 5 4 3 f 16 Mean - 1.03 E + 00 - 1.01 E + 00 - 1.02 E + 00 - 9.33 E - 01 - 9.67 E - 01 - 9.72 E - 01 StdDev 1.57 E - 15 2.39 E - 02 1.27 E - 02 1.49 E - 01 1.01 E - 01 5.81 E - 02 Rank 1 3 2 6 5 4 f 17 Mean 3.97 E - 01 3.99 E - 01 3.98 E - 01 3.99 E - 01 4.00 E - 01 4.00 E - 01 StdDev 2.36 E - 15 8.06 E - 04 3.74 E - 04 7.09 E - 03 9.10 E - 03 7.28 E - 03 Rank 2 3 1 4 6 5 f 18 Mean 3.00 E + 00 3.00 E + 00 3.00 E + 00 3.04 E + 00 3.03 E + 00 3.03 E + 00 StdDev 2.51 E - 14 1.55 E - 04 8.11 E - 04 3.56 E - 02 2.47 E - 02 4.39 E - 02 Rank 1 2 3 5 4 6 f 19 Mean - 3.86 E + 00 - 3.86 E + 00 - 3.86 E + 00 - 3.86 E + 00 - 3.86 E + 00 - 3.86 E + 00 StdDev 2.20 E - 14 4.99 E - 03 3.61 E - 03 2.28 E - 03 1.06 E - 02 2.29 E - 03 Rank 1 5 4 2 6 3 f 20 Mean - 3.26 E + 00 - 3.25 E + 00 - 3.27 E + 00 - 3.32 E + 00 - 3.32 E + 00 - 3.32 E + 00 StdDev 4.72 E - 01 3.21 E - 02 2.62 E - 02 2.72 E - 03 3.72 E - 03 3.82 E - 03 Rank 5 6 4 1 2 3 f 21 Mean - 1.02 E + 01 - 9.65 E + 00 - 9.53 E + 00 - 8.92 E + 00 - 8.43 E + 00 - 9.03 E + 00 StdDev 6.28 E - 14 2.97 E - 01 5.33 E - 01 2.15 E + 00 2.78 E + 00 2.25 E + 00 Rank 1 2 3 5 6 4 f 22 Mean - 1.04 E + 01 - 9.86 E + 00 - 9.82 E + 00 - 9.39 E + 00 - 9.24 E + 00 - 7.73 E + 00 StdDev 6.28 E - 14 2.85 E - 01 3.45 E - 01 2.31 E + 00 2.42 E + 00 3.08 E + 00 Rank 1 2 3 4 5 6 f 23 Mean - 1.05 E + 01 - 9.99 E + 00 - 9.95 E + 00 - 8.84 E + 00 - 9.09 E + 00 - 9.27 E + 00 StdDev 1.42 E - 11 3.76 E - 01 5.50 E - 01 3.04 E + 00 2.58 E + 00 2.46 E + 00 Rank 1 2 3 6 5 4  Average rank 1.5 3.4 2.7 4.2 4.9 4.3 Overall rank 1 3 2 4 6 5Table4 gives the results for unimodal functions. From Table 4, we can see that AACRO outperforms the rest of the algorithms. AACRO behaves best on f1, f2, and f4, and the HP-CRO2 version has a better performance than other algorithms on functions f3 and f5; the RCCRO2 version ranks first on f7. For f6, all versions have the same performance, so they all rank first. The standard deviation of AACRO is also less than other versions.For this table, AACRO ranks first, the 2nd highest overall rank is HP-CRO, and the RCCRO versions have the worst performance. In general, AACRO is efficient in solving unimodal functions.Table5 gives the results for high-dimensional multimodal functions (Category II). AACRO also has the best performance compared to others. Besides f9, AACRO outperforms the HP-CRO and RCCRO versions. The HP-CRO2 version performs best on f9. For RCCRO versions, the performances are all not ideal, expect that RCCRO4 gets a 2nd rank on f9.For this table, AACRO also ranks first, followed by HP-CRO versions, and the RCCRO versions ranks last. Therefore, we can also believe that AACRO can treat high-dimensional multimodal functions well.Table6 gives the results for low-dimensional multimodal functions. From the overall rank we can see AACRO has a smaller standard deviation except f20. AACRO outperforms the rest on f14, f15, f16, f18, f19, f21, f22, and f23, and f17 gets a 2nd rank. The RCCRO versions perform best on f20. The 1st, 2nd, and 3rd ranks are all RCCRO versions, HP-CRO2 ranks 4th, AACRO ranks 5th, and HP-CRO1 ranks 6th. In general, AACRO is also efficient in solving low-dimensional multimodal functions.From Tables4–6, AACRO ranks 1st and HP-CRO versions ranks 2nd, followed by RCCRO versions. The details of AACRO are also presented, shown in Tables 7 and 8.Table 7
Average computation time(f1–f7).
Function f 1 f 2 f 3 f 4 f 5 f 6 f 7 f 8 f 9 f 10 f 11 f 12 Times(s) 0.00259 0.00116 0.00140 0.00243 0.00244 0.00262 0.00280 0.00144 0.00418 0.00114 0.00280 0.00347Table 8
Average computation time(f8–f13).
Function f 13 f 14 f 15 f 16 f 17 f 18 f 19 f 20 f 21 f 22 f 23 Times(s) 0.00343 0.00030 0.00036 0.00030 0.00034 0.00034 0.00041 0.00046 0.00038 0.00039 0.00034We can see from Tables7 and 8 that when dealing with unimodal problems, our proposed ACCRO algorithm takes less average computation time than other problems. It is obvious since this kind of problem has only one global minimum in each of the functions and it is relatively “easy” to get the optimal solution. For the Hartman’s family problems (f19 and f20), ACCRO takes the longest average computation time due to a “narrow” solution space S and a relatively complicated exponential function.For a more detailed comparison of the AACRO proposed in this paper with the HP-CRO version, we give experimental results of some functions, the results of the execution onf2, f5, f7, and f10 are shown in Figure 2. The convergence curves on f2, f5, f7, and f10 are shown in Figure 3.Figure 2
Results of G-best 25 run times of HP-CRO1 and AACRO: (a)f2, (b) f5, (c) f7, and (d) f10.
(a) (b) (c) (d)Figure 3
Convergence curves of HP-CRO1 and AACRO: (a)f2, (b) f5, (c) f7, and (d) f10.
(a) (b) (c) (d)It was observed that the performance of AACRO is better than HP-CRO in Figures2(a) and 2(d). It was worth noting that sometimes HP-CRO can have a better performance in Figure 2(c), and AACRO is better than HP-CRO in most cases in Figure 2(b). Moreover, we can see from Figure 3 that AACRO converges faster than HP-CRO.


## 6.1. Experimental Environment

Both AACRO and HP-CRO are implemented in Matlab7.8. All simulations are performed on a computer with an Intel Core I5-4590 @ 3.3 GHz CPU and 4 GB of RAM in Windows 7 environment.


## 6.2. Parameter Setting

In order to achieve the best results, different test functions are set with different parameters and each simulation terminates when a certain number of function evaluations (NFEs) have been performed. The NFEs limits of AACRO for different test functions are listed in Table2; the parameter settings are listed in Table 3. The local weight and global weight of PSO are chosen as c1=c2=2.Table 2
Number of NFEs for functionf1–f23.
Name Function AACRO HP-CRO RCCRO Category I f 1 , f 2 , f 4 , f 5 , f 6 , f 7 150000 150000 150000 f 3 250000 250000 250000  Category II f 8 , f 10 , f 11 , f 12 , f 13 150000 150000 150000 f 9 250000 250000 250000  Category III f 14 , f 20 7500 7500 7500 f 15 250000 250000 250000 f 16 1250 1250 1250 f 17 5000 5000 5000 f 19 4000 4000 4000 f 18 , f 21 , f 22 , f 23 10000 10000 10000Table 3
Parameter settings for different categories.
Order Parameter Category I Category II Category III f 1 – f 7 f 8 – f 13 f 14 – f 18 f 19 – f 23 (1) PopSize 10 100 100 100 (2) w_local 0.2 0.5 0.8 0.8 (3) w_global 0.8 0.5 0.2 0.2 (4) CollRate 0.2 0.2 0.2 0.2 (5) LossRate 0.3 0.3 0.3 0.3 (6) IniKE 1000 1000 1000 1000 (7) buffer 0 0 0 0 (8) ChangeRate 0.001 0.001 0.001 0.001


## 6.3. Comparisons

This paper also provides the results of the RCCRO versions of RCCRO1 (RCCRO1, RCCRO2, and RCCRO4) and HP-CRO (HP-CRO1 and HP-CRO2). All versions tested 23 standard test functions. For each function, we run AACRO 25 times and obtain the averaged computed minimum value (mean) and standard deviation (StdDev). We rank the results from the lowest mean to the highest and get the average rank. Finally, we order the average rank and get the overall rank.As shown in Tables4–6, the overall rank of AACRO is best and HP-CRO versions rank 2nd, followed by RCCRO versions. It is worth noting that each version has its specialty. In other words, no algorithm can work best on all functions. The AACRO version outperforms on f1, f2, f4, f6, f1, f8, f10, f11, f12, f13, f14, f15, f16, f18, f19, f21, f22, and f23. HP-CRO versions are on f3, f5, f6, f9, and f17. RCCRO versions are on f6, f7, and f20.Table 4
The optimization computing results forf1–f7.
AACRO HP-CRO1 HP-CRO2 RCCRO1 RCCRO2 RCCRO4 f 1 Mean 5.70 E - 55 6.93 E - 50 1.17 E - 50 2.35 E - 07 2.24 E - 07 2.20 E - 07 StdDev 2.85 E - 55 3.39 E - 49 4.18 E - 50 4.70 E - 08 4.43 E - 08 3.83 E - 08 Rank 1 3 2 6 5 4 f 2 Mean 1.42 E - 08 4.22 E - 06 1.50 E - 05 2.18 E - 03 2.24 E - 03 2.16 E - 03 StdDev 8.89 E - 09 1.28 E - 05 3.50 E - 05 3.65 E - 04 4.14 E - 04 3.32 E - 04 Rank 1 2 3 5 6 4 f 3 Mean 8.77 E - 09 7.70 E - 94 8.31 E - 104 2.50 E - 07 2.57 E - 07 2.41 E - 07 StdDev 4.32 E - 08 3.77 E - 93 2.98 E - 103 9.35 E - 08 9.18 E - 08 8.60 E - 08 Rank 3 2 1 5 6 4 f 4 Mean 8.32 E - 10 4.16 E - 04 3.37 E - 04 9.28 E - 03 9.42 E - 03 8.74 E - 03 StdDev 5.88 E - 09 3.05 E - 04 2.99 E - 04 3.97 E - 03 4.92 E - 03 3.63 E - 03 Rank 1 3 2 5 6 4 f 5 Mean 1.13 E + 01 1.13 E + 01 5.52 E + 00 9.37 E + 01 7.45 E + 01 6.98 E + 01 StdDev 1.50 E + 01 1.53 E + 01 7.13 E + 00 9.61 E + 01 9.30 E + 01 1.03 E + 02 Rank 2 3 1 6 5 4 f 6 Mean 0 0 0 0 0 0 StdDev 0 0 0 0 0 0 Rank 1 1 1 1 1 1 f 7 Mean 6.42 E - 03 7.21 E - 03 7.02 E - 03 3.79 E - 03 3.69 E - 03 3.83 E - 03 StdDev 1.03 E - 02 2.31 E - 03 2.00 E - 03 1.25 E - 03 9.65 E - 04 1.31 E - 03 Rank 4 6 5 2 1 3  Average rank 1.8 2.8 2.1 3.4 4.2 3.4 Overall rank 1 3 2 4 6 5Table 5
The optimization computing results forf8–f13.
AACRO HP-CRO1 HP-CRO2 RCCRO1 RCCRO2 RCCRO4 f 8 Mean - 1.26 E  +  04 - 1.23 E + 04 - 1.26 E + 04 - 1.24 E + 04 - 1.23 E + 04 - 1.24 E + 04 StdDev 3.07 E + 01 1.79 E + 02 4.34 E + 01 7.11 E + 01 9.16 E + 01 6.94 E + 01 Rank 1 5 2 4 6 3 f 9 Mean 8.60 E - 03 3.80 E - 03 1.57 E - 03 1.85 E - 03 1.70 E - 03 1.59 E - 03 StdDev 8.02 E - 02 1.02 E - 02 6.07 E - 03 4.62 E - 04 4.86 E - 04 4.94 E - 04 Rank 6 5 1 4 3 2 f 10 Mean 1.32 E - 14 3.02 E - 13 1.12 E - 11 2.32 E - 03 2.16 E - 03 2.37 E - 03 StdDev 1.36 E - 14 9.44 E - 13 5.43 E - 11 4.43 E - 04 2.93 E - 04 3.83 E - 04 Rank 1 2 3 5 4 6 f 11 Mean 7.14 E - 02 1 1 1.00 E + 00 1.000001 1.00 E + 00 StdDev 1.41 E - 01 1.18 E - 14 3.02 E - 15 1.48 E - 07 2.02 E - 07 1.39 E - 07 Rank 1 3 2 4 6 5 f 12 Mean 1.22 E - 01 3.08 E - 01 1.54 E - 01 5.82 E - 01 3.56 E - 01 1.60 E - 01 StdDev 8.45 E - 01 5.19 E - 01 2.33 E - 01 8.03 E - 01 5.99 E - 01 2.76 E - 01 Rank 1 4 2 6 5 3 f 13 Mean 3.75 E - 32 2.63 E - 14 3.81 E - 14 6.66 E - 06 7.71 E - 06 6.46 E - 06 StdDev 7.74 E - 32 8.96 E - 14 1.24 E - 13 4.85 E - 06 7.95 E - 06 4.56 E - 06 Rank 1 2 3 5 6 4  Average rank 1.8 3.5 2.1 4.6 5 3.8 Overall rank 1 3 2 5 6 4Table 6
The optimization computing results forf14–f23.
AACRO HP-CRO1 HP-CRO2 RCCRO1 RCCRO2 RCCRO4 f 14 Mean 9.98 E - 01 1.04 E + 00 9.98 E - 01 2.70 E + 00 3.55 E + 00 3.49 E + 00 StdDev 1.01 E - 09 1.95 E - 01 9.64 E - 07 1.81 E + 00 1.74 E + 00 2.58 E + 00 Rank 1 3 2 4 6 5 f 15 Mean 3.07 E - 04 1.31 E - 03 3.90 E - 04 5.63 E - 04 5.39 E - 04 5.39 E - 04 StdDev 5.17 E - 13 3.95 E - 03 2.46 E - 04 8.56 E - 05 1.10 E - 04 9.58 E - 05 Rank 1 6 2 5 4 3 f 16 Mean - 1.03 E + 00 - 1.01 E + 00 - 1.02 E + 00 - 9.33 E - 01 - 9.67 E - 01 - 9.72 E - 01 StdDev 1.57 E - 15 2.39 E - 02 1.27 E - 02 1.49 E - 01 1.01 E - 01 5.81 E - 02 Rank 1 3 2 6 5 4 f 17 Mean 3.97 E - 01 3.99 E - 01 3.98 E - 01 3.99 E - 01 4.00 E - 01 4.00 E - 01 StdDev 2.36 E - 15 8.06 E - 04 3.74 E - 04 7.09 E - 03 9.10 E - 03 7.28 E - 03 Rank 2 3 1 4 6 5 f 18 Mean 3.00 E + 00 3.00 E + 00 3.00 E + 00 3.04 E + 00 3.03 E + 00 3.03 E + 00 StdDev 2.51 E - 14 1.55 E - 04 8.11 E - 04 3.56 E - 02 2.47 E - 02 4.39 E - 02 Rank 1 2 3 5 4 6 f 19 Mean - 3.86 E + 00 - 3.86 E + 00 - 3.86 E + 00 - 3.86 E + 00 - 3.86 E + 00 - 3.86 E + 00 StdDev 2.20 E - 14 4.99 E - 03 3.61 E - 03 2.28 E - 03 1.06 E - 02 2.29 E - 03 Rank 1 5 4 2 6 3 f 20 Mean - 3.26 E + 00 - 3.25 E + 00 - 3.27 E + 00 - 3.32 E + 00 - 3.32 E + 00 - 3.32 E + 00 StdDev 4.72 E - 01 3.21 E - 02 2.62 E - 02 2.72 E - 03 3.72 E - 03 3.82 E - 03 Rank 5 6 4 1 2 3 f 21 Mean - 1.02 E + 01 - 9.65 E + 00 - 9.53 E + 00 - 8.92 E + 00 - 8.43 E + 00 - 9.03 E + 00 StdDev 6.28 E - 14 2.97 E - 01 5.33 E - 01 2.15 E + 00 2.78 E + 00 2.25 E + 00 Rank 1 2 3 5 6 4 f 22 Mean - 1.04 E + 01 - 9.86 E + 00 - 9.82 E + 00 - 9.39 E + 00 - 9.24 E + 00 - 7.73 E + 00 StdDev 6.28 E - 14 2.85 E - 01 3.45 E - 01 2.31 E + 00 2.42 E + 00 3.08 E + 00 Rank 1 2 3 4 5 6 f 23 Mean - 1.05 E + 01 - 9.99 E + 00 - 9.95 E + 00 - 8.84 E + 00 - 9.09 E + 00 - 9.27 E + 00 StdDev 1.42 E - 11 3.76 E - 01 5.50 E - 01 3.04 E + 00 2.58 E + 00 2.46 E + 00 Rank 1 2 3 6 5 4  Average rank 1.5 3.4 2.7 4.2 4.9 4.3 Overall rank 1 3 2 4 6 5Table4 gives the results for unimodal functions. From Table 4, we can see that AACRO outperforms the rest of the algorithms. AACRO behaves best on f1, f2, and f4, and the HP-CRO2 version has a better performance than other algorithms on functions f3 and f5; the RCCRO2 version ranks first on f7. For f6, all versions have the same performance, so they all rank first. The standard deviation of AACRO is also less than other versions.For this table, AACRO ranks first, the 2nd highest overall rank is HP-CRO, and the RCCRO versions have the worst performance. In general, AACRO is efficient in solving unimodal functions.Table5 gives the results for high-dimensional multimodal functions (Category II). AACRO also has the best performance compared to others. Besides f9, AACRO outperforms the HP-CRO and RCCRO versions. The HP-CRO2 version performs best on f9. For RCCRO versions, the performances are all not ideal, expect that RCCRO4 gets a 2nd rank on f9.For this table, AACRO also ranks first, followed by HP-CRO versions, and the RCCRO versions ranks last. Therefore, we can also believe that AACRO can treat high-dimensional multimodal functions well.Table6 gives the results for low-dimensional multimodal functions. From the overall rank we can see AACRO has a smaller standard deviation except f20. AACRO outperforms the rest on f14, f15, f16, f18, f19, f21, f22, and f23, and f17 gets a 2nd rank. The RCCRO versions perform best on f20. The 1st, 2nd, and 3rd ranks are all RCCRO versions, HP-CRO2 ranks 4th, AACRO ranks 5th, and HP-CRO1 ranks 6th. In general, AACRO is also efficient in solving low-dimensional multimodal functions.From Tables4–6, AACRO ranks 1st and HP-CRO versions ranks 2nd, followed by RCCRO versions. The details of AACRO are also presented, shown in Tables 7 and 8.Table 7
Average computation time(f1–f7).
Function f 1 f 2 f 3 f 4 f 5 f 6 f 7 f 8 f 9 f 10 f 11 f 12 Times(s) 0.00259 0.00116 0.00140 0.00243 0.00244 0.00262 0.00280 0.00144 0.00418 0.00114 0.00280 0.00347Table 8
Average computation time(f8–f13).
Function f 13 f 14 f 15 f 16 f 17 f 18 f 19 f 20 f 21 f 22 f 23 Times(s) 0.00343 0.00030 0.00036 0.00030 0.00034 0.00034 0.00041 0.00046 0.00038 0.00039 0.00034We can see from Tables7 and 8 that when dealing with unimodal problems, our proposed ACCRO algorithm takes less average computation time than other problems. It is obvious since this kind of problem has only one global minimum in each of the functions and it is relatively “easy” to get the optimal solution. For the Hartman’s family problems (f19 and f20), ACCRO takes the longest average computation time due to a “narrow” solution space S and a relatively complicated exponential function.For a more detailed comparison of the AACRO proposed in this paper with the HP-CRO version, we give experimental results of some functions, the results of the execution onf2, f5, f7, and f10 are shown in Figure 2. The convergence curves on f2, f5, f7, and f10 are shown in Figure 3.Figure 2
Results of G-best 25 run times of HP-CRO1 and AACRO: (a)f2, (b) f5, (c) f7, and (d) f10.
(a) (b) (c) (d)Figure 3
Convergence curves of HP-CRO1 and AACRO: (a)f2, (b) f5, (c) f7, and (d) f10.
(a) (b) (c) (d)It was observed that the performance of AACRO is better than HP-CRO in Figures2(a) and 2(d). It was worth noting that sometimes HP-CRO can have a better performance in Figure 2(c), and AACRO is better than HP-CRO in most cases in Figure 2(b). Moreover, we can see from Figure 3 that AACRO converges faster than HP-CRO.


## 7. Concluding and Future Work

In this paper, a new algorithm AACRO based on balanced local search and global search has been proposed. The algorithm combines the ACRO features and also incorporates the optimality operator of the PSO algorithm and adds the weighting factor to control the ratio of local search and global search. The algorithm’s structure allows the algorithm to switch seamlessly between global and local searches efficiently, making it easier to find optimal values.What is more, we give the convergence proof and convergence speed analysis. We draw a conclusion that the AACRO algorithm will keep converging with a high speed.At last, this algorithm is simulated and compared with HP-CRO and RCCRO two versions of the algorithm. The results show that the algorithm can solve the optimization problem efficiently.Our future work will be focused on the investigations of AACRO’s parameters and figuring out the impact of each parameter, and the structure of the algorithm still needs to be streamlined. We expect to combine improved algorithms with engineering practice, which is also another key issue in the near future.



---

*Source: 8042689-2018-04-16.xml*