# Multiobjective Lightning Flash Algorithm Design and Its Convergence Analysis via Martingale Theory

Authors: Jiandong Duan; Jing Wang; Xinghua Liu; Gaoxi Xiao
Journal: Complexity
 (2020)

---

## Abstract

In this paper, a novel multiobjective lightning flash algorithm (MOLFA) is proposed to solve the multiobjective optimization problem. The charge population state of the lightning flash algorithm is defined, and we prove that the charge population state sequence is a Markov chain. Since the convergence analysis of MOLFA is to investigate whether a Pareto optimal solution can be reached when the optimal charge population state is obtained, the development of a charge population state is analyzed to achieve the goal of this paper. Based on the martingale theory, the MOLFA convergence analysis is carried out in terms of the supermartingale convergence theorem, which shows that the MOLFA can reach the global optimum with probability one. Finally, the effectiveness of the proposed MOLFA is verified by a numerical simulation example.


---

## Body

## 1. Introduction

Lightning flash algorithm (LFA), a new heuristic algorithm proposed by Kheshti [1], has been successfully applied to large-scale nonconvex economic dispatch [2], nonconvex combined emission economic dispatch [3], protective relay coordination [4], and intelligent inertial control of wind turbines for grid frequency control [5, 6]. As demonstrated in [3], LFA not only searches the global optimal solution more quickly but also has better reliability and effectiveness, compared with other intelligent algorithms such as particle swarm optimization (PSO) [7], lightning search algorithm (LSA) [8], firefly algorithm (FA) [9], and harmony search algorithm (HSA) [10]. In a word, the lightning flash algorithm can synthesize the outstanding computational characteristics of both swarm intelligence algorithm and evolutionary algorithm. Since most of problems need to optimize two or more objectives simultaneously, the multiobjective optimization algorithm is increasingly prevalent, such as multiple objective particle swarm optimization (MOPSO) [11] and nondominated sorting genetic algorithm (NSGA-II) [12]. However, a comprehensive theoretical study on LFA or multiple objective LFA is largely still in vain. The missing theoretical results include a global convergence analysis which is of high importance for further studies and improvements.The convergence analysis of an intelligent algorithm is typically to investigate whether the algorithm can converge to a global optimal value. For example, the artificial immune algorithm is proposed based on the principle of the artificial immune system, however with a relatively low computational efficiency and slow convergence [13]. To overcome such drawbacks, a novel hybrid immune algorithm is proposed in [14], with its convergence under weaker conditions being proven using a quasidescent method. Jin et al. [15] analyze and deduce the stability of mean-square convergence of the PSO algorithm based on the theory of stochastic processes and give a sufficient condition for the system to be mean-square stable. For multiobjective optimization methods, a simple theoretical proof of the convergence of the general Pareto-based bacteria colony chemotaxis algorithm is presented in [16].Markov chain is a class of important stochastic processes with nonaftereffect property [17–20]. As it is proved that the optimization processes of some classical intelligent algorithms also have this property [21], Markov chain has been widely applied in convergence analysis of many intelligent algorithms [22–28], e.g., chicken swarm optimization, ant colony algorithm, and genetic algorithm (GA). In [22], the finite homogeneous Markov chain model of chicken swarm optimization is established with some of its properties being analyzed. It is proved that the algorithm satisfies two convergence criteria and guarantees the global convergence. In [23], Huang et al. analyze the convergence time of the ant colony algorithm based on the absorbing Markov chain model. Markov models of genetic algorithm and artificial bee colony algorithm are established, respectively, in [24, 25]. The Markov chain model and a dynamic matrix model of the bat algorithm are proposed in [26]. It is shown that the transition matrix of the wolf pack algorithm can converge to a limit value with probability one, which demonstrates it global convergence property [27]. The state transition probability of particles is discussed in [28]. Martingale theory is the basis of modern probability theory and stochastic process and also has important applications in financial pricing decision-making and control model [29]. To avoid complex calculations for solving eigenvalue of the transfer matrix, the state sequence of particles with the best fitness value is transformed to a supermartingale, and the convergence of standard PSO and improved algorithm QPSO is analyzed in [30]. The analysis for the convergence properties of the ant colony algorithm is conducted by using Markov chains and martingale theory. The pheromone trail vector almost always converges to the optimal solution when the iteration time is infinite [31]. Despite of all these efforts, however, the convergence analysis of LFA and MOLFA has not been fully studied.To shorten such a gap, this study proposes a multiobjective lightning flash algorithm and analyzes the global convergence of LFA. Major contributions are summarized as follows:(1)
Based on the repository mechanism, a novel multiobjective lightning flash algorithm (MOLFA) is proposed to solve multiobjective optimization problems. MOLFA has high computational efficiency and can obtain better Pareto optimal front.(2)
The Markov chain of LFA is modelled, and martingale theory is applied to the optimal fitness value of population state discussing the convergence of the algorithm.(3)
Numerical are conducted by employing the latest test function of CEC2017, which commendably validate the effectiveness of the proposed MOLFA in this paper.The remainder of this paper is organized as follows: Section2 introduces the mechanism of the lightning flash algorithm; Section 3 presents the multiobjective lightning flash algorithm and establishes the convergence of the multiobjective lightning flash algorithm via martingale theory; Section 4 provides a numerical example to verify the effectiveness of the proposed MOLFA; and finally, concluding remarks are given in Section 5.


## 2. Basic Principle of Lightning Flash Algorithm

Lightning is a natural phenomenon, generated by storm clouds (cumulonimbus clouds). The storm clouds generate negative electricity at the bottom and positive electricity at the top, as shown in Figure1, which can be seen in [1]. As the electric field between the bottom of cloud and the ground becomes stronger, the charges ionize the around atmosphere, eventually breakdown air and open a way to the ground. In other words, when the electric field becomes stronger, an air column ionized appears at the bottom of cloud, also called stepped leader. After the formation of stepped leader, the charge branches connected to the tip of stepped leader develop rapidly and jump and struggle to find a path to the Earth. However, during the process of jumping, only one branch reaches the ground successfully. These charges at the tip of the winner branch also mean the better solution of the optimization problem in the algorithm.Figure 1
Development of downward and upward leaders initiating a lightning.As mentioned above, the lightning flash algorithm learns from the lightning phenomenon between clouds and ground. In this algorithm, each individual (called charge) represents a possible solution and has two characteristics: position and velocity. The initial populations of LFA are some different charges, randomly generated in a bounded interval, as shown in the following equation:(1)X=Xmin+rXmax−Xmin,where Xmax and Xmin are the maximum and minimum values of charge individual, respectively. r∈0,1 is a random value.The initial populations find the optimal solution by iterating and updating. First, all charge particles move to the ground along its channel; namely, each charge updates value according to the stepped leader of the channel. The moving distance of chargei at channel j is expressed as equation (2), and the position of charge is updated as equation (3). If any updated charge is a better fitness value than the stepped leader, the stepped leader will be replaced by the charge:(2)Jijt=wJijt−1+c1r1XjLt−1−Xijt−1,(3)Xijt=Xijt−1+Jijt,where t is the iteration number, w is the inertia weight, r1∈0,1 is a random value, Jijt denotes the moving distance of charge i in channel j at the t-th iteration, XjLt−1 denotes the stepped leader of channel j at the t−1-th iteration, Xijt denotes the position of charge i in lightning channel j at the t-th iteration, and c1 is a constant to ensure that all charges move downward in line with the stepped leader’s position.Before the jump process takes place, the lightning channels have a pause time to rest. During the short rest time, the distance between the best and the worst charge in each channel is measured, which is a decision parameter in the jumping process later. As described in the following equation,djt is the measured distance and XjWt is the worst charge with farthest distance to the ground in channel j:(4)djt=XjLt−XjWt.The stepped leader will absorb and mutate all charges in the channel same like it. That is, all charges are equal to stepped leader, as shown in the following equation:(5)Xijt=XjLt.Finally, to diversify the charge population, the jump of each charge happens in different directions and can be described as follows:(6)Xijt=XjLt+αr2djt,where r2∈0,1 is a random value and α is a constant to show the speed of the lightning strike.If any updated charge is with better fitness value than its stepped leader, the stepped leader is replaced by the individual. The lightning flash algorithm mainly includes four steps: performing downward flow, measuring the critical distance, accumulation of charge, and jumping process. The latter three steps are repeated until the algorithm finds an optimal value, normally setting a maximum iteration or predefined tolerance to end the procedure. The above equations (1)–(6) can be referred to [2, 3]. For a better illustration, the flowchart of LFA is shown in Figure 2.Figure 2
Flowchart of the lightning flash algorithm.Remark 1.
In this paper, we assume that there arem lightning channels and each channel has a stepped leader to lead it; namely, the stepped leader is the best particle in a lightning path and has the shortest distance to the ground. Combined with the optimization problem, the stepped leader refers to the optimal solution among the feasible solutions that have been searched. The remained charge particles of the population are equally distributed to m lightning channels.


## 3. Multiobjective Lightning Flash Algorithm and Its Convergence

In this section, as an extension of LFA, we propose a multiobjective lightning flash algorithm to provide a reference method for the multiobjective optimization problem. After that, the convergence of MOLFA is analyzed on the basis of martingale theory.


### 3.1. Multiobjective Lightning Flash Algorithm

As described in [32], given a function f:Ω⊂ℝn⟶ℝ, Ω≠∅, for X∈Ω, the value fX∗>−∞ is called a global minimum if and only if ∀X∈Ω:fX∗≤fX, where X∗ is the global minimum solution, f is the objective function, and the set Ω is the feasible region of X. The goal of determining the global minimum solution is called the global optimization problem for a single-objective problem.Multiobjective problems are those problems where the goal is to optimize simultaneouslyD objective functions f1X,f2X,…,fDX and forming a vector function FX=f1X,f2X,…,fDX⊤. A multiobjective minimum optimization problem is defined as (7)minFX=minf1X,f2X,…,fDX⊤,where fiX is the i-th objective function and X represents decision variable. If fiX∗≤fiX, i=1,2,…,D, and at least one i makes fiX∗<fiX,i=1,2,…,D true, then X∗ is nondominated solutions; namely, X∗ is superior to X. If the inequalities are strictly hold, X∗ is called optimal solution.Based on the multiobjective particle swarm optimization (MOPSO) proposed by Coello et al. [33], the multiobjective lightning flash algorithm (MOLFA) is proposed in this paper. The principle of MOLFA is to use the adaptive grid mechanism to save external population. When the number of individuals in the external population exceeds a predetermined value, the space of their objective function is divided into hypergrids with equal spacing, and the number of individuals gi in each grid is calculated (where i represents the grid number). The probability of particle to be selected in the i-th grid is pi=1/gi; that is, the more crowded the lower selection probability. The multiobjective lightning flash algorithm is described as Algorithm 1.Algorithm 1: Multiobjective lightning flash algorithm.
Step 1. Initialize the charges populationPop and compute and evaluate the fitness of each charge in Pop.Step 2. Store the charge particles that represent nondominated solutions into the repositoryRep.Step 3. Generate hypercubes of fitness space calculated byPop, and each charge’s coordinates are defined according to its fitness value.Step 4. While maximum number of cycles has not been reached Do(1) Update the charge applying downward movement:(8)Jijt=wJijt−1+c1r1XRep∗t−1−Xijt−1,Xijt=Xijt−1+Jijt,whereXRep∗ is a solution variable taken from the repository and represents the stepped leader in this equation.(2)
Compute and evaluate the fitness values of newPop, and then update the Rep together with the geographical representation of the particles within the hypercubes. If the number of charge particles in Rep is full, the adaptive grid criterion can be used to retain the nondominated solutions.(3)
Measure the critical distance between the best charge and the worst, and conduct the accumulation of charges. Update the charge by jump process.(4)
Go to 2.(5)
Increase the loop counter.Step 5. End While.


### 3.2. Markov Chain of MOLFA

In MOLFA, charge particles in each channel have similar optimization development. In other words, one charge only relates to the condition of itself channel and independent of other lightning channels. Therefore, the following convergence analysis is given on a certain lightning channel for convenience.According to equations (2)–(6), the state of charge particle i at the t-th iteration consists of Xit−1 and Xit, the stepped leader (the best charge) XLt, and the worst charge XWt; i.e., it is defined as cit=Xit−1,Xit,XLt,XWt. The set of all possible charge states is called charge state space, defined as C. For all charge particles, the charge population state at the t-th iteration is denoted as st=c1t,c2t,…,cnt, where n is the population size. The set of all possible charge population states is called charge population state space S.Proposition 1.
If acceleration factorsc1r1 and αr2 of LFA satisfy uniform distribution, i.e., c1r1∼U0,a and αr2∼U0,a, then the probability of charge i transferring from Xit to the spherical region centered at Xit+1 with radius ε can be computed as follows: (9)Pcit+1cit=ε2awXit−Xit−1⋅XLt−XWt,case1,ε3a2wXit−Xit−1⋅XLt−Xit⋅XLt−XWt,case2,where w is a constant, as described in equation (2). Case 1 is XLt−Xit≤δ, and case 2 is XLt−Xit>δ.Proof.
In view of the basic principle of the lightning flash algorithm, we introduce the following three steps (downward movement, absorption, and jumping) to develop the transition probability of chargei. We use Pdown, Pabs, and Pjump to represent the probabilities of the downward movement step, absorption step, and jumping step, respectively.Part (a): downward movement. When the population completes initialization, all charge particles start moving down. From equations (2) and (3), the downward movement formula can be described as follows:(10)Xit+1=Xit+wXit−Xit−1+c1rXLt−Xit.For case 1, sinceδ is close to zero, we obtain Xit+1≈Xit+wXit−Xit−1. Thus, the state transition probability of charge i from Xit to the spherical region centered at Xit+1 with radius ε is calculated as(11)PdownXit+1cit=∫Xit+1−0.5εXit+1+0.5εdy∫XitXit+wXit−Xit−1dy=εwXit−Xit−1.For case 2, we obtainXit+1=Xit+wXit−Xit−1+c1rXLt−Xit. Thus, the state transition probability of charge i is defined as(12)PdownXit+1cit=∫Xit+1−0.5εXit+1+0.5εdy∫XitXit+wXit−Xit−1dy∫c1r−0.5εc1r+0.5εdy∫XitXit+c1rXLt−Xitdy=εwXit−Xit−1⋅εaXLt−Xit.Part (b): absorption: the absorption process means that the stepped leader will unify all charges in the channel; namely, the state of chargei must transfer from Xit to XLt, and the state transition probability is(13)PabsXLtcit=1Part (c): jumping: according to equations (5) and (6), the formula of the jumping process can be described as(14)Xit+1=XLt+αr2XLt−XWt.The transition probability is then computed as follows:(15)PjumpXit+1cit=∫αr2−0.5εαr2+0.5εdy∫XLtXLt+αr2XLt−XWtdy=εaXLt−XWt.Due to the fact thatXLt and XWt are both determined by Xit+1, the transition probability of charge i from cit to cit+1 is obtained as follows:(16)Pcit+1cit=εwXit−Xit−1⋅εaXLt−Xit⋅εaXLt−XWt.Moreover, we assume that(17)εaXLt−Xit=1,whenXLt−Xit≤δ.On the basis of equation (16), we can easily obtain equation (9). This completes the proof.
Next, we will proceed to develop the transition probability of charge population state. The transition of charge population state means that, fromst to st+1, namely, all charge particles’ states of st transferred to st+1 at the same time. So, the transition probability from st to st+1 can be followed that (18)Pst+1st=∏m=1nPcmt+1|cmt.Proposition 2.
The charge population state sequencest,t≥1 is a Markov chain.Proof.
According to equations (2)–(6), the charge population state st+1=c1t+1,c2t+1,…,cnt+1 only depends on the state of last iteration. Thus, st,t≥1 is a Markov chain. The proof is completed.
In this paper,XRep∗ is employed to denote a certain solution of the Pareto optimal front (POF). If the stepped leader XLt of charge population equals XRep∗, it indicates that a certain optimum solution of POF has been found by population. The optimal charge population state is defined as s∗t=c1∗t,c2∗t,…,cn∗t, where ci∗t=Xit−1,Xit,XRep∗,XWt, i=1,2,…,n. Besides, the optimal charge population state set is defined as Γ=s∗t=c1∗t,c2∗t,…,cn∗t,t∈ℕ+.


### 3.3. Convergence Analysis of MOLFA

The martingale is a stochastic process defined by conditional mathematical expectation, which is a basic tool of probability analysis. In the following, we present two definitions and one lemma to derive our main results.Definition 1.
A stochastic processYt,t=0,1,2,…, is a martingale if for all t the following conditions are satisfied:(1)
BYt<∞.(2)
BYt+1Y0,Y1,…,Yt=Yt.Definition 2.
For given two stochastic processesYt,t=0,1,2,…, and Zt,t=0,1,2,…,, Yt,t=0,1,2,…, is a supermartingale (or submartingale) with respect to Zt if Yt meets the following conditions:(1)
Yt is a function of Z0,Z1,…,Zt.(2)
BYt<∞.(3)
BYt+1Z0,Z1,…,Zt≤or≥Yt.Lemma 1.
(see [30]). If stochastic process Yt,t=0,1,2,…, is a submartingale with respect to Zt and supt≥0BYt<∞, then the state sequence Yt,t=0,1,2,…, converges to a state Y∞ with probability one, namely, Plimt⟶+∞Yt=Y∞=1.The purpose of MOLFA is to search for Pareto optimal front, a best repository, i.e., the optimal charge population state. The POF of charge population state is defined as(19)Fst=f1XRept,f2XRept,…,fDXRept,where XRept is a vector of nondominated solutions of Rep. For solving multiobjective optimization problem, POF can be obtained only when the optimal charge population state is searched. Therefore, the convergence analysis of MOLFA can be transformed into the convergence study of Fst. When the conditional expectation of Fst with new charge population state is less than or equal to the current population state, Fst can be transformed into a supermartingale. Since Fst is a monotone nonincremental process, the convergence of the supermartingale can be investigated.Theorem 1.
The stochastic process of population state sequenceFst,t=1,2,…, is a nonnegative and bounded supermartingale with respect to population state sequence st,t=1,2,…,, i.e., BFst+1s1,s2,…,st≤Fst. Moreover, as t⟶∞, st will converge to s∞ with probability 1, i.e., Plimt⟶∞st=s∞=1.Proof.
Stochastic processFst,t=1,2,…, is obviously nonnegative and bounded. According to Proposition 2, st,t=1,2,…, is a Markov chain. It then follows that(20)EFst+1s1,s2,…,st=EFst+1st.
It can be seen that we only need to prove that(21)∀y∈S,EFst+1st=y≤Fy.
Since the left side of (21) follows that (22)EFst+1st=y=∑z∈SFzPst+1=zst=y,the proof can be transformed to show (23)∑z∈SFzPst+1=zst=y≤Fy.
For any charge population statez subsequent to y, there is Fst+1=z≤Fst=y. Then, it implies that (24)∑z∈SFzPst+1=zst=y≤∑z∈SFyPst+1=zst=y=Fy∑z∈SPst+1=zst=y=Fy,where the last equality holds due to S is a closed set, i.e., ∑z∈SPst+1=zst=y. Hence, we obtain that (25)EFst+1st=y≤Fy,which indicates that Fst,t=1,2,…, is a nonnegative and bounded supermartingale with respect to st,t=1,2,…,. This competes the proof.Theorem 2.
The stochastic processFst,t=1,2,…, will converge to the global optimal solution Γ.Proof.
According to Theorem1, we know that Fst,t=1,2,…, is a bounded supermartingale. Then, by Lemma 1, it can be deduced that it can converge to the global optimal solution Γ with probability one. This completes the proof.Remark 2.
In Theorem2, the convergence of MOLFA is proposed by using the martingale sequence convergence theorem. In terms of the principle of the algorithm, the jumping process guarantees the diversity of the population and prevents the population falling into local optimum. Therefore, the MOLFA can converge to the Pareto optimal front with probability one.


## 3.1. Multiobjective Lightning Flash Algorithm

As described in [32], given a function f:Ω⊂ℝn⟶ℝ, Ω≠∅, for X∈Ω, the value fX∗>−∞ is called a global minimum if and only if ∀X∈Ω:fX∗≤fX, where X∗ is the global minimum solution, f is the objective function, and the set Ω is the feasible region of X. The goal of determining the global minimum solution is called the global optimization problem for a single-objective problem.Multiobjective problems are those problems where the goal is to optimize simultaneouslyD objective functions f1X,f2X,…,fDX and forming a vector function FX=f1X,f2X,…,fDX⊤. A multiobjective minimum optimization problem is defined as (7)minFX=minf1X,f2X,…,fDX⊤,where fiX is the i-th objective function and X represents decision variable. If fiX∗≤fiX, i=1,2,…,D, and at least one i makes fiX∗<fiX,i=1,2,…,D true, then X∗ is nondominated solutions; namely, X∗ is superior to X. If the inequalities are strictly hold, X∗ is called optimal solution.Based on the multiobjective particle swarm optimization (MOPSO) proposed by Coello et al. [33], the multiobjective lightning flash algorithm (MOLFA) is proposed in this paper. The principle of MOLFA is to use the adaptive grid mechanism to save external population. When the number of individuals in the external population exceeds a predetermined value, the space of their objective function is divided into hypergrids with equal spacing, and the number of individuals gi in each grid is calculated (where i represents the grid number). The probability of particle to be selected in the i-th grid is pi=1/gi; that is, the more crowded the lower selection probability. The multiobjective lightning flash algorithm is described as Algorithm 1.Algorithm 1: Multiobjective lightning flash algorithm.
Step 1. Initialize the charges populationPop and compute and evaluate the fitness of each charge in Pop.Step 2. Store the charge particles that represent nondominated solutions into the repositoryRep.Step 3. Generate hypercubes of fitness space calculated byPop, and each charge’s coordinates are defined according to its fitness value.Step 4. While maximum number of cycles has not been reached Do(1) Update the charge applying downward movement:(8)Jijt=wJijt−1+c1r1XRep∗t−1−Xijt−1,Xijt=Xijt−1+Jijt,whereXRep∗ is a solution variable taken from the repository and represents the stepped leader in this equation.(2)
Compute and evaluate the fitness values of newPop, and then update the Rep together with the geographical representation of the particles within the hypercubes. If the number of charge particles in Rep is full, the adaptive grid criterion can be used to retain the nondominated solutions.(3)
Measure the critical distance between the best charge and the worst, and conduct the accumulation of charges. Update the charge by jump process.(4)
Go to 2.(5)
Increase the loop counter.Step 5. End While.


## 3.2. Markov Chain of MOLFA

In MOLFA, charge particles in each channel have similar optimization development. In other words, one charge only relates to the condition of itself channel and independent of other lightning channels. Therefore, the following convergence analysis is given on a certain lightning channel for convenience.According to equations (2)–(6), the state of charge particle i at the t-th iteration consists of Xit−1 and Xit, the stepped leader (the best charge) XLt, and the worst charge XWt; i.e., it is defined as cit=Xit−1,Xit,XLt,XWt. The set of all possible charge states is called charge state space, defined as C. For all charge particles, the charge population state at the t-th iteration is denoted as st=c1t,c2t,…,cnt, where n is the population size. The set of all possible charge population states is called charge population state space S.Proposition 1.
If acceleration factorsc1r1 and αr2 of LFA satisfy uniform distribution, i.e., c1r1∼U0,a and αr2∼U0,a, then the probability of charge i transferring from Xit to the spherical region centered at Xit+1 with radius ε can be computed as follows: (9)Pcit+1cit=ε2awXit−Xit−1⋅XLt−XWt,case1,ε3a2wXit−Xit−1⋅XLt−Xit⋅XLt−XWt,case2,where w is a constant, as described in equation (2). Case 1 is XLt−Xit≤δ, and case 2 is XLt−Xit>δ.Proof.
In view of the basic principle of the lightning flash algorithm, we introduce the following three steps (downward movement, absorption, and jumping) to develop the transition probability of chargei. We use Pdown, Pabs, and Pjump to represent the probabilities of the downward movement step, absorption step, and jumping step, respectively.Part (a): downward movement. When the population completes initialization, all charge particles start moving down. From equations (2) and (3), the downward movement formula can be described as follows:(10)Xit+1=Xit+wXit−Xit−1+c1rXLt−Xit.For case 1, sinceδ is close to zero, we obtain Xit+1≈Xit+wXit−Xit−1. Thus, the state transition probability of charge i from Xit to the spherical region centered at Xit+1 with radius ε is calculated as(11)PdownXit+1cit=∫Xit+1−0.5εXit+1+0.5εdy∫XitXit+wXit−Xit−1dy=εwXit−Xit−1.For case 2, we obtainXit+1=Xit+wXit−Xit−1+c1rXLt−Xit. Thus, the state transition probability of charge i is defined as(12)PdownXit+1cit=∫Xit+1−0.5εXit+1+0.5εdy∫XitXit+wXit−Xit−1dy∫c1r−0.5εc1r+0.5εdy∫XitXit+c1rXLt−Xitdy=εwXit−Xit−1⋅εaXLt−Xit.Part (b): absorption: the absorption process means that the stepped leader will unify all charges in the channel; namely, the state of chargei must transfer from Xit to XLt, and the state transition probability is(13)PabsXLtcit=1Part (c): jumping: according to equations (5) and (6), the formula of the jumping process can be described as(14)Xit+1=XLt+αr2XLt−XWt.The transition probability is then computed as follows:(15)PjumpXit+1cit=∫αr2−0.5εαr2+0.5εdy∫XLtXLt+αr2XLt−XWtdy=εaXLt−XWt.Due to the fact thatXLt and XWt are both determined by Xit+1, the transition probability of charge i from cit to cit+1 is obtained as follows:(16)Pcit+1cit=εwXit−Xit−1⋅εaXLt−Xit⋅εaXLt−XWt.Moreover, we assume that(17)εaXLt−Xit=1,whenXLt−Xit≤δ.On the basis of equation (16), we can easily obtain equation (9). This completes the proof.
Next, we will proceed to develop the transition probability of charge population state. The transition of charge population state means that, fromst to st+1, namely, all charge particles’ states of st transferred to st+1 at the same time. So, the transition probability from st to st+1 can be followed that (18)Pst+1st=∏m=1nPcmt+1|cmt.Proposition 2.
The charge population state sequencest,t≥1 is a Markov chain.Proof.
According to equations (2)–(6), the charge population state st+1=c1t+1,c2t+1,…,cnt+1 only depends on the state of last iteration. Thus, st,t≥1 is a Markov chain. The proof is completed.
In this paper,XRep∗ is employed to denote a certain solution of the Pareto optimal front (POF). If the stepped leader XLt of charge population equals XRep∗, it indicates that a certain optimum solution of POF has been found by population. The optimal charge population state is defined as s∗t=c1∗t,c2∗t,…,cn∗t, where ci∗t=Xit−1,Xit,XRep∗,XWt, i=1,2,…,n. Besides, the optimal charge population state set is defined as Γ=s∗t=c1∗t,c2∗t,…,cn∗t,t∈ℕ+.


## 3.3. Convergence Analysis of MOLFA

The martingale is a stochastic process defined by conditional mathematical expectation, which is a basic tool of probability analysis. In the following, we present two definitions and one lemma to derive our main results.Definition 1.
A stochastic processYt,t=0,1,2,…, is a martingale if for all t the following conditions are satisfied:(1)
BYt<∞.(2)
BYt+1Y0,Y1,…,Yt=Yt.Definition 2.
For given two stochastic processesYt,t=0,1,2,…, and Zt,t=0,1,2,…,, Yt,t=0,1,2,…, is a supermartingale (or submartingale) with respect to Zt if Yt meets the following conditions:(1)
Yt is a function of Z0,Z1,…,Zt.(2)
BYt<∞.(3)
BYt+1Z0,Z1,…,Zt≤or≥Yt.Lemma 1.
(see [30]). If stochastic process Yt,t=0,1,2,…, is a submartingale with respect to Zt and supt≥0BYt<∞, then the state sequence Yt,t=0,1,2,…, converges to a state Y∞ with probability one, namely, Plimt⟶+∞Yt=Y∞=1.The purpose of MOLFA is to search for Pareto optimal front, a best repository, i.e., the optimal charge population state. The POF of charge population state is defined as(19)Fst=f1XRept,f2XRept,…,fDXRept,where XRept is a vector of nondominated solutions of Rep. For solving multiobjective optimization problem, POF can be obtained only when the optimal charge population state is searched. Therefore, the convergence analysis of MOLFA can be transformed into the convergence study of Fst. When the conditional expectation of Fst with new charge population state is less than or equal to the current population state, Fst can be transformed into a supermartingale. Since Fst is a monotone nonincremental process, the convergence of the supermartingale can be investigated.Theorem 1.
The stochastic process of population state sequenceFst,t=1,2,…, is a nonnegative and bounded supermartingale with respect to population state sequence st,t=1,2,…,, i.e., BFst+1s1,s2,…,st≤Fst. Moreover, as t⟶∞, st will converge to s∞ with probability 1, i.e., Plimt⟶∞st=s∞=1.Proof.
Stochastic processFst,t=1,2,…, is obviously nonnegative and bounded. According to Proposition 2, st,t=1,2,…, is a Markov chain. It then follows that(20)EFst+1s1,s2,…,st=EFst+1st.
It can be seen that we only need to prove that(21)∀y∈S,EFst+1st=y≤Fy.
Since the left side of (21) follows that (22)EFst+1st=y=∑z∈SFzPst+1=zst=y,the proof can be transformed to show (23)∑z∈SFzPst+1=zst=y≤Fy.
For any charge population statez subsequent to y, there is Fst+1=z≤Fst=y. Then, it implies that (24)∑z∈SFzPst+1=zst=y≤∑z∈SFyPst+1=zst=y=Fy∑z∈SPst+1=zst=y=Fy,where the last equality holds due to S is a closed set, i.e., ∑z∈SPst+1=zst=y. Hence, we obtain that (25)EFst+1st=y≤Fy,which indicates that Fst,t=1,2,…, is a nonnegative and bounded supermartingale with respect to st,t=1,2,…,. This competes the proof.Theorem 2.
The stochastic processFst,t=1,2,…, will converge to the global optimal solution Γ.Proof.
According to Theorem1, we know that Fst,t=1,2,…, is a bounded supermartingale. Then, by Lemma 1, it can be deduced that it can converge to the global optimal solution Γ with probability one. This completes the proof.Remark 2.
In Theorem2, the convergence of MOLFA is proposed by using the martingale sequence convergence theorem. In terms of the principle of the algorithm, the jumping process guarantees the diversity of the population and prevents the population falling into local optimum. Therefore, the MOLFA can converge to the Pareto optimal front with probability one.


## 4. Experiments on the Performance of MOLFA

As further discussed in [1], it indicates that the LFA method has better search ability and convergence property than many other heuristic algorithms. In this paper, the latest test function of CEC2017 is utilized to validate performance and effectiveness of the proposed MOLFA, where similar multiobjective optimization test problems are considered in [34, 35] and the latest test function of CEC2017 can be found in [36]. It should be pointed out that the test functions include ZDT1, ZDT2, ZDT3, ZDT4, and ZDT6 problems, where the Pareto front of ZDT3 is noncontinuous; ZDT2 and ZDT6 are convex; and ZDT1 and ZDT4 are nonconvex. All problems have two objective functions described in Table 1. The table also shows the number of variables and their bounds for each problem. These typical test functions could cover the basic types of multiobjective optimization problems. In the following experiments, a charge population size of 100 and a repository size of 250 are utilized to test these multiobjective problems.Table 1
Standard test problems.
ProblemnVariable boundsObjective functionsZDT130xi∈0,1,1≤i≤nf1x=x1, f2x=gx1−x1/gx, gx=1+9∑i=2nxi/n−1ZDT230xi∈0,1,1≤i≤nf1x=x1, f2x=gx1−x1/gx2, gx=1+9∑i=2nxi/n−1ZDT330xi∈0,1,1≤i≤nf1x=x1, f2x=gx1−x1/gx−x1/gxsin10πx1, gx=1+9∑i=2nxi/n−1ZDT410xi∈−5,5,2≤i≤n, x1∈0,1f1x=x1, f2x=gx1−x1/gx, gx=1+10n−1+∑i=2nxi2−10sin4πxiZDT610xi∈0,1,1≤i≤nf1x=1−exp−4x1sin66πx1, f2x=gx1−f1x/gx2, gx=1+9∑i=2nxi/n−10.25For multiobjective optimization problems, we need to consider that whether the final optimal solutions are close to the true Pareto front, and the distribution of the solution is uniform and smooth. We use three indices, e.g., generational distance, spacing, and error ratio, to conduct a quantitative assessment of the performance of MOLFA.Generational distance (GD) [37] is to estimate the gap between the nondominated vectors produced by algorithm and true Pareto optimal front, which can be defined as (26)GD=∑i=1ndi2n,where n is the number of nondominated solutions obtained by the algorithm and di is the Euclidean distance between the i-th solution and the nearest member of the Pareto optimal front. It indicates that all the nondominated vectors can be regarded as the true Pareto optimal solution set when GD=0.Spacing (SP) [38] is used to evaluate the diversity of the obtained Pareto optimal solutions by comparing the uniform distribution and the deviation of solutions, which can be defined as (27)SP=1n−1∑i=1nd¯−di2,where d¯ is the average value of di and di also denotes the Euclidean distance between the i-th solution and the nearest member of the Pareto optimal front. It can be seen that all nondominated solutions are evenly spread if SP=0.Error ratio (ER) [39] is employed to report the number of nondominated vectors in Pareto front that are not members of true Pareto front, which can be defined as (28)ER=∑i=1nein,where ei=0or1. For the case ei=0, it indicates that the i-th solution can be a member of the true Pareto optimal front. Otherwise, it means that the i-th solution is not a member of the true Pareto optimal front.The simulated results for these test problems are shown in Figures3–7. The continuous red line is the true Pareto front. To conveniently show the distribution of the nondominated solution set produced by MOLFA, all solutions are connected with straight lines, as shown in the blue dot line. The closer the blue dot line is to the red line, the more accurate the solution obtained by the MOLFA. Besides, Table 2 shows the results of metric for the test problems. It can be seen that most of solutions are close to the true Pareto front and are unevenly distributed. Therefore, it is demonstrated that the proposed MOLFA method is able to solve these standard multiobjective optimization problems, which provide an effective nondominated solution set and cover the full Pareto front.Figure 3
Pareto front produced by MOLFA for the ZDT1 test function.Figure 4
Pareto front produced by MOLFA for the ZDT2 test function.Figure 5
Pareto front produced by MOLFA for the ZDT3 test function.Figure 6
Pareto front produced by MOLFA for the ZDT4 test function.Figure 7
Pareto front produced by MOLFA for the ZDT6 test function.Table 2
Results of GD, SP, and ER metric for the test problems.
GDSPERZDT10.0078210.22040.1630ZDT20.0062550.23600.1580ZDT30.010560.19970.3510ZDT40.0056170.61750.08520ZDT60.0064850.60970.1190


## 5. Conclusion

In this paper, a multiobjective optimization algorithm MOLFA is proposed. In order to discuss the convergence property of MOLFA, the Markov chain model and Martingale theory have been introduced. The stochastic process of the optimal charge population state has been transformed into a supermartingale, and the global convergence of MOLFA algorithm has been proved. At last, the convergence property has been investigated on the standard test functions. The simulation results show that the MOLFA method has a good performance on converging to the Pareto optimal front. The convergence property of the MOLFA method is firstly proved from theoretical aspect via the martingale theory, which may provide a new way for the theoretical research of multiobjective optimization problems.



---

*Source: 8451639-2020-10-09.xml*