# A Multiobjective Optimization Algorithm Based on Discrete Bacterial Colony Chemotaxis

Authors: Zhigang Lu; Tao Feng; Zhaozheng Liu
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Bacterial colony chemotaxis algorithm was originally developed for optimal problem with continuous space. In this paper the discrete bacterial colony chemotaxis (DBCC) algorithm is developed to solve multiobjective optimization problems. The basic DBCC algorithm has the disadvantage of being trapped into the local minimum. Therefore, some improvements are adopted in the new algorithm, such as adding chaos transfer mechanism when the bacterium choose their next locations and the crowding distance operation to maintain the population diversity in the Pareto Front. The definition of chaos transfer mechanism is used to retain the elite solution produced during the operation, and the definition of crowding distance is used to guide the bacteria for determinate variation, thus enabling the algorithm obtain well-distributed solution in the Pareto optimal set. The convergence properties of the DBCC strategy are tested on some test functions. At last, some numerical results are given to demonstrate the effectiveness of the results obtained by the new algorithm.


---

## Body

## 1. Introduction

In the field of optimization, many researchers have been inspired by biological processes such as evolution [1, 2] or the food-searching behavior of ants [3] to develop new optimal methods such as evolutionary algorithms or ant codes. These techniques have been found to perform better than the classical heuristic or gradient-based optimization methods, especially when faced with the problem of optimizing multimodal, nondifferentiable, or discontinuous functions. Examples of applying these biologically inspired strategies in the field of engineering range from aerodynamic design [4] to job-shop scheduling problems [5]. Another biologically inspired optimization method is the chemotaxis algorithm, pioneered by Bremermann [6] and his coworkers [7, 8], that is proposed by analogy to the way bacteria react to chemoattractants in concentration gradients. This algorithm was analyzed for chemotaxis in a three-dimensional (3D) gradient by Bremermann [6] and employed for the training of neural networks [7, 8]. This strategy is evaluated on a number of test functions for local and global optimization, compared with other optimization techniques, and applied to the problem of inverse airfoil design [9]. A similar algorithm is the guided accelerated random search technique [10], which was applied to optimize parameters in flight control systems, [11] and to optimize perceptrons [12]. The BCC algorithm is a new colony intelligence optimization algorithm which was introduced in [13]. This novel algorithm considers not only the chemotactical strategy but also the communication between the colony members, and the performance has improved greatly.Most real-world optimization problems require making decisions involving two or more goals. When these goals are the minimization or maximization of the objective functions they are typically referred to as multiobjective optimization (MO). From the 1950s, a variety of methods known as classical have been developed for the solution of multiobjective optimal problems (MOP). These methods are based on formal logic or mathematical programming [14]. Another interesting biological process that has been already implemented as an optimization technique is the BCC algorithm. This novel technique exposed the potential of implementing bacterial chemotaxis as a distributed optimization process, recognizing that in natural colonies, it is the interaction and communication between bacteria the mechanism that enables them to develop biologically advantageous patterns. Many real-world binary-discrete optimization problems require making decisions involving two or more goals that typically are in contradiction with each other. So in this paper the DBCC algorithm is developed to solve MOP. The basic DBCC algorithm has the disadvantage of being trapped into the local minimum and also cannot maintain the population diversity in the Pareto optimal set. Therefore, some improvements are adopted in the new algorithm, as adding arithmetic operator when the bacteria choose their next locations and taking into account the chaos transfer mechanism.This paper is organized as follows. Section2 describes the basic theorem of MOP. The model is shown in Section 3. The convergence properties of the developed DBCC strategy which is applied on test functions are given by comparing with other algorithms in Section 4. Finally, some conclusions are drawn in Section 5.


## 2. Preparative Theorem of MOP

A MOP [15] is defined as the problem of finding a vector of decision variables that satisfies some restrictions and optimizes a vector function, whose elements represent the values of the functions. A MOP may be formulated as follows [16]:
(1)Min:fm(x)m=1,2,…,MSubjectto:gj(x)≥0j=1,2,…,Jhk(x)=0k=1,2,…,Kxi∈{0,1}i=1,2,…,n,
where x is the vector of discrete decision variables x=(x1,x2,…,xn)T and fm(x) are the m objective functions. The J inequalities gj and the K equalities hk are known as constraint functions.For MOP, instead of a single optimal, there is a set of optimal solutions known as Pareto optimal front (POF). Any solution of this set represents a balance between the objective functions; therefore, it is not possible to say that there is other solution in the search space which is superior to this one when all objectives are considered. In the minimization MOP, Pareto optimality can be mathematically defined as follows [17].Definition 1.
Pareto dominate: given two candidate solutionsx and y from S, where S is the feasible region, the vector f(x) is said to dominate vector f(y) (denoted by ≺y) if and only if,
(2)fm(x)≤fm(y),∀m∈{1,2,…,M},fm(x)<fm(y),∃m∈{1,2,…,M}.
Denoted by x¬≺y if and only if,
(3)fm(x)≤fm(y),∃m∈{1,2,…,M},fj(x)≥fj(y),∃j∈{1,2,…,M}.Definition 2.
Pareto optimal: the candidate solutionx*∈S is Pareto optimal if and only if,
(4)x≺x*,¬∃x∈S.Definition 3.
Pareto optimal set(5)F={f(x)∣y≺x,¬∃y∈S}.
The set of solutions that satisfy all constraints is known as the Pareto optimal set and the fitness values corresponding to these solutions form the Pareto front or trade-off surface in objective space. In most cases it is not easy to find analytical expressions for the line or curve that contains the POF; thus, commonly optimal solutions points and the objective functions values in them are calculated. In order to find optimal solutions, there are two goals that any multiobjective optimization algorithm (MOA) seeks to achieve [18]: (1)
guide the search towards the global Pareto optimal region,(2)
maintain the population diversity in the Pareto optimal front.


## 3. Multiobjective Optimal Algorithm Based on DBCC (MOADBCC)

In this section, we present further improvements to the algorithm. MOADBCC can be summarized in the following steps:The strategy parametersT0, b, and τc are relevant to the calculation precision ε(6)T0=ε0.30·10-1.73,b=T0·(T0-1.54·100.60),τc=(bT0)0.30·101.16.Step 1.
Initialize variables.GenerateN bacteria randomly by using binary-discrete code and make it turn to real code. Compute the velocity v. In this model, the velocity is assumed to be a scalar constant value v=1. Evaluate the fitness of the bacteria and store the nondominated solutions in the Pareto optimal set.Step 2.
Individual bacterial optimization and find the new positionx1→.(a) Compute the duration of the trajectoryτ from the distribution of a random variable with an exponential probability density function
(7)P(X=τ)=1Te-τ/T.
The time T is given by
(8)T={T0forx→pre≺x→curT0(1+b*min⁡{|fmprlpr|})forx→pre¬≺x→cur,
where T0 is minimal mean time, x→pre and x→cur are the position of a bacterium in the previous and current step, respectively, fmprm=1,2,…,M is the difference between the actual and the previous function value, lpr is vector connecting the previous and the actual position in the parameter space, and b is dimensionless parameter.(b) The position and motion of a bacterium are defined byx, with a radius γ and n-1 angles Φ={ϕ1,ϕ2,…,ϕn-1}, x1=γ∏s=1n-1cos⁡(ϕs), xi=γsin(ϕi-1)∏s=in-1cos⁡(ϕs), i=2,3,…,n, xn=γsin(cos⁡(ϕn-1)).The angleϕi between the previous and the new direction obeys Gaussian distribution, for turning left or right, respectively,
(9)P(Xi=ϕi,vi=μi)=1σi2πexp⁡[-(ϕi-vi)22σi2],P(Xi=ϕi,vi=-μi)=1σi2πexp⁡[-(ϕi-vi)22σi2],
where ϕi∈[00,1800], the expectation value μ=E(Xi), and the variance σi=VAR(Xi)(10)μi=62°(1-cos⁡(θ)),σi=26°(1-cos⁡(θ))
with
(11)cos⁡(θ)={0forx→pre≺x→curexp⁡(-τcτpr)forx→pre¬≺x→cur,
where τpr is the duration of the previous step.(c) Compute the positionx1→ of the bacterium. The length of the path l is given by
(12)l=vτ.The normalized new direction vectorn→u with |n→u|=1 is multiplied by l to obtain the displacement vector x1→(13)x→=n→ul
such that the new location of the bacterium is
(14)x1→=x→pre+n→ul.Step 3.
Optimize by the bacterial colony and find the new positionx2→.The individual bacterial acquires information about its environment; compute the best neighbor centerxi→. We can get the new position by
(15)x2→=x→pre+l→,
where l→=R(0,2)·dis(xi→,Center(xi→)), where R(0,2) is the random number within the interval (0,2) and dis(x,y) is the distance connecting the vector x and y.Step 4.
Optimize by the crowding distance operator and find the new positionx3→.The new position of the individual bacterial with crowding distance operator is given by(16)x3→=x→pre+F·x→Rpr,
where F∈[-1.2,1.2] is assumed to be a real number and x→Rpr is the biggest crowding distance position of bacterium in the previous step. The count of x3→ is given no more than N*5%+2.Step 5.
The reference colonyx→ref is produced and bacteria move to the new location [19].Step 6.
If the chosen target precisionεend is not reached, then go to Step 2; otherwise end.In practical optimization, the calculation precisionε can be adjusted adaptively with εnext=εbegin/α, where α>1 is the precision update constant.As the initial precision is reached, the parameters are adapted to another precision (defined by the number of parameter changes) and the search continues, until this new precision is reached. A given precisionεend is reached if the difference between function values found by the bacterium is smaller than εend(17)|fmpr|<εendm=1,2,…,M
for a given number nend.When the(18)|fmpr|<εim=1,2,…,M,
the difference between the actual and the previous function value is reached in a row ni that has assumed before. The bacterial colony has to move to other positions and neglects information that the bacterial colony has held in previous step. This has been called bacterial migration. We modify the algorithm with chaos transfer mechanism (CTM).Therefore, one has the following:(19)Xn+1=μXn(1-Xn).
So the algorithm can escape from the local optimal region.In the other side, sometimes the bacterium jumps out of the area of the global optimal and is never able to get back. To prevent the bacteria strategy from leaving the global optimal regions, the algorithm will search each of the bacterial migration positions, compare the function values with that in the POF, and then take the better one into the POF. Flowchart of the MOADBCC algorithm is given as shown in Figure1.Figure 1
Flowchart of the MOADBCC algorithm.


## 4. Tests Results of the MOADBCC

MOADBCC with operators, MOADBCC without operators, and NSGA-II are, respectively, applied on simulation, among which NSGA-II applies binary coding to obtain Pareto optimal solution set. The parameter selection of MOADBCC algorithm can refer to [6]. The initial precision is set as 2.0 with a precision update constant α=1.05. The cross probability of NSGA-II is 0.9, and the variation probability is 0.01. The colony scales of all these three algorithms are 100 and the test function iterates 100 times except for the ZDT series function which iterates 200 times. Test condition was AMD Athlon(tm) IIX2 255 Processor, 2 GB Memory, Microsoft Windows XP operation system; the procedure was tested in Matlab 7.1.This paper applies five test functions to examine the performance of the algorithm, including the research achievement SCH of Schaffer [20], DErB, and ZDT1 and ZDT2 [21–23] of Deb and SRN [24, 25] of test function Srinivas with constraint condition,. Binary coding and discretization treatment are applied by test function while the optimization is conducted in the discrete area. Among them, ZDT1 and ZDT2 and DEB apply 10 coding and SRN and SCH apply 20 coding. Table 1 shows test functions.Table 1
Test functions.
Problems
n
Constraint
Objective functions
SCH
1
[−103, 103]
f
1
(
x
)
=
x
2 f2(x)=(x-2)2
DEB
2
[0, 1]
f
1
(
x
)
=
x
1 f2=(1+10x2)×[1-(x1(1+10x2))2-x1×sin⁡⁡(8πx1)(1+10x2)]
ZDT1
30
[0, 1]
f
1
(
x
)
=
x
1 f2(x)=g(x)[1-(x1g(x))0.5] g(x)=1+9(∑i=2nxi)(n-1)
ZDT2
30
[0, 1]
f
1
(
x
)
=
x
1 f2(x)=g(x)[1-(x1g(x))2] g(x)=1+9(∑i=2nxi)(n-1)
SRN
2
[−20, 20]
f
1
(
x
)
=
(
x
1
-
2
)
2
+
(
x
2
-
1
)
2
+
2 f2(x)=9x1-(x2-1)2 g1(x)=x12+x22-225≤0 g2(x)=x1-3x2+10≤0In order to evaluate the comprehensive performance of the algorithm, CM, and RVI performance evaluation indexes are applied in this paper to measure the advantages of the algorithm performance.(
1
) Convergence index (CM) [26] is used to measure the intimacy level between the solutions obtained by the algorithm and real solution set. The smaller the CM index value is, the more intimate the obtained solutions are with real POF
(20)CM=∑i=1Ndi2n.(
2
) Effective solution proportion index (RVI) refers to the proportion of nondominant solutions in all solutions, which is used to examine the convergence degree of final solutions. The bigger the RVI index value is, the better performance the algorithm is
(21)RVI=VN,
where V means that the nondominant solutions minus the bacteria amount in same location.The algorithm operates for 30 times independently for each index to obtain their mean value Mean and standard deviation Stdev. Tables2 to 3 show the mean and Stdev of CM and RVI index for MOADBCC with operators, MOADBCC without operators, and NSGA-II respectively.Table 2
Comparison table of CM.
Standard test function
SCH
ZDT1
ZDT2
MODBCC (with operators)
Mean
0.003100
0.000909
0.000816
Stdev
0.000178
0.000458
0.005400
MODBCC (without operators)
Mean
0.003300
0.003400
0.005600
Stdev
0.000258
0.005400
0.007100
NSGA-II
Mean
0.003200
0.104700
0.187300
Stdev
0.000150
0.197700
0.229800Table 3
Comparison table of RVI.
Standard test function
SCH
ZDT1
ZDT2
MODBCC (with operators)
Mean
1.000000
0.970000
0.965000
Stdev
0.007200
0.012900
0.011100
MODBCC (without operators)
Mean
0.990000
0.720000
0.665000
Stdev
0.029100
0.043600
0.056900
NSGA-II
Mean
1.000000
1.000000
1.000000
Stdev
0.000000
0.000000
0.122100From the table of comparisons, the results show that all indexes of MOADBCC with operators are better than that of MOADBCC without operators. The performance of MODBCC and NSGA-II is equal to each other in terms of RVI index. However, the performance of MOADBCC is better than NSGA-II in terms of CM index, indicating it has better performance than NSGA-II algorithm. It is due to the fact that the operators proposed by this paper make it easier for bacteria to jump out of local convergence and accelerate the convergence speed of the algorithm, thus enabling it to obtain more effective solutions with same iterations and increasing the value of RVI.In order to further compare the performances among these three algorithms, this paper listed the Figures of simulation results of three algorithms corresponding to SCH, DEB, and FON test functions, shown in Figures2, 3, 4, 5, 6, and 7. From the simulation Figures, those results show that MOADBCC with operators is better than the other two algorithms in view of test problems in the Pareto Front, as it can converge to the Pareto Front more effectively and obtain more well-distributed solutions.The result of MOADBCC with and without operators on SCH.
(a)
(b)The result of MOADBCC with and without operators on DEB.
(a)
(b)The result of MOADBCC with and without operators on ZDT1.
(a)
(b)The result of MOADBCC with and without operators on ZDT2.
(a)
(b)The result of MOADBCC with and without operators on SRN.
(a)
(b)Figure 7
The result of MOADBCC and NSGA-II on ZDT2.


## 5. Conclusions

In this paper, a discrete bacterial colony chemotaxis (DBCC) algorithm is developed by chaos transfer mechanism and crowding distance strategy and used to solve multiobjective optimization problems. An additional term containing the chaos transfer mechanism draws the search away from local optima. Incorporation of crowding distance strategy also improves performance. The performance on tests is given to demonstrate the validity of the proposed algorithm. In fact, the results given in this paper not only show the effectiveness of the DBCC for the test functions, but also generally support the use of DBCC for other practical problems. Hence, there are future works including parameter settings and more applications of the proposed algorithmic framework to other optimization problems.



---

*Source: 569580-2014-07-14.xml*