# Racing Sampling Based Microimmune Optimization Approach Solving Constrained Expected Value Programming

Authors: Kai Yang; Zhuhong Zhang
Journal: Scientific Programming
 (2016)

---

## Abstract

This work investigates a bioinspired microimmune optimization algorithm to solve a general kind of single-objective nonlinear constrained expected value programming without any prior distribution. In the study of algorithm, two lower bound sample estimates of random variables are theoretically developed to estimate the empirical values of individuals. Two adaptive racing sampling schemes are designed to identify those competitive individuals in a given population, by which high-quality individuals can obtain large sampling size. An immune evolutionary mechanism, along with a local search approach, is constructed to evolve the current population. The comparative experiments have showed that the proposed algorithm can effectively solve higher-dimensional benchmark problems and is of potential for further applications.


---

## Body

## 1. Introduction

Many real-world engineering optimization problems, such as industrial control, project management, portfolio investment, and transportation logistics, include stochastic parameters or random variables usually. Generally, they can be solved by some existing intelligent optimization approaches with static sampling strategies (i.e., each candidate is with the same sampling size), after being transformed into constrained expected value programming (CEVP), chance constrained programming, or probabilistic optimization models. Although CEVP is a relatively simple topic in the context of stochastic programming, it is a still challenging topic, as it is difficult to find feasible solutions and meanwhile the quality of the solution depends greatly on environmental disturbance. The main concern of solving CEVP involves two aspects: (i) when stochastic probabilistic distributions are unknown, it becomes crucial to distinguish those high-quality individuals from the current population in uncertain environments, and (ii) although static sampling strategies are a usual way to handle random factors, the expensive computational cost is inevitable, and hence adaptive sampling strategies with low computational cost are desired.When stochastic characteristics are unknown, CEVP models are usually replaced by their sample average approximation models [1, 2], and thereafter some new or existing techniques can be used to find their approximate solutions. Mathematically, several researchers [3–5] probed into the relationship between CEVP models and their approximation ones and acquired some valuable lower bound estimates on sample size capable of being used to design adaptive sampling rules. On the other hand, intelligent optimization techniques have become popular for nonconstrained expected value programming problems [6–8], in which some advanced sampling techniques, for example, adaptive sampling techniques and sample allocation schemes, can effectively suppress environmental influence on the process of solution search. Unfortunately, studies on general CEVP have been rarely reported in the literature because of expected value constraints. Even if so, several researchers made great efforts to investigate new or hybrid intelligent optimization approaches for such kind of uncertain programming problem. For example, B. Liu and Y.-K. Liu [9] proposed a hybrid intelligent approach to solve general fuzzy expected value models, after combining evolutionary algorithms with neural networks learning methods. Sun and Gao [10] suggested an improved differential evolutionary approach to solve an expected value programming problem, depending on static sampling and flabby selection.Whereas immune optimization as another popular branch was well studied for static or dynamic optimization problems [11, 12], it still remains open for stochastic programming problems. Some comparative works between classical intelligent approaches and immune optimization algorithms for stochastic programming demonstrated that one such branch is competitive. For example, Hsieh and You [13] proposed a two-phase immune optimization approach to solve the optimal reliability-redundancy allocation problem. Their numerical results, based on four benchmark problems have showed that such approach is superior to the compared algorithms. Zhao et al. [14] presented a hybrid immune optimization approach to deal with chance-constrained programming, in which two operators of double cloning and double mutation were adopted to accelerate the process of evolution.In the present work, we study two lower bound estimates on sample size theoretically, based on Hoeffding’s inequalities [15, 16]. Afterwards, two efficient adaptive racing sampling approaches are designed to compute the empirical values of stochastic objective and constraint functions. These, together with immune inspirations included in the clonal selection principle, are used to develop a microimmune optimization algorithm (μIOA) for handling general, nonlinear, and higher-dimensional constrained expected value programming problems. Such approach is significantly different from any existing immune optimization approaches. On one hand, the two lower bound estimates are developed to control the sample sizes of random variables, while a local search approach is adopted to strengthen the ability of local exploitation; on the other hand, the two adaptive racing sampling methods are utilized to determine dynamically such sample sizes in order to compute the empirical values of objective and constraint functions at each individual. Experimental results have illustrated that μIOA is an alternative tool for higher-dimensional multimodal expected value programming problems.


## 2. Problem Statement and Preliminaries

Consider the following general single-objective nonlinear constrained expected value programming problem:EP
⁡
m
i
n
x
∈
D
E
f
x
,
ξ
s
.
t
.
E
G
i
x
,
ξ
≤
0
,
0
≤
i
≤
I
,
g
j
x
≤
0
,
1
≤
j
≤
J
,
h
k
x
=
0
,
1
≤
k
≤
K
,with bounded and closed domain D in R
p, decision vector x in D, and random vector ξ in R
q, where E
[
·
] is the operator of expectation; f
(
x
,
ξ
) and G
i
(
x
,
ξ
) are the stochastic objective and constraint functions, respectively, among which at least one is nonlinear and continuous in x; g
j
(
x
) and h
k
(
x
) are the deterministic and continuous constraint functions. If a candidate solution satisfies all the above constraints, it is called a feasible solution and an infeasible solution otherwise. Introduce the following constraint violation function to check if candidate x is feasible:(1)
Γ
x
=
I
-
1
∑
i
=
1
I
max
⁡
E
G
i
x
,
ξ
,
0
+
J
-
1
∑
j
=
1
J
max
⁡
g
j
x
,
0
+
K
-
1
∑
k
=
1
K
h
k
x
.Obviously, x is feasible only when Γ
(
x
)
=
0. If Γ
x
<
Γ
(
y
), we prescribe that x is superior to y
. In order to solve CEVP, we transform the above problem into the following sample-dependent approximation model (SAM):(2)
m
i
n
x
∈
D
1
n
x
∑
l
=
1
n
x
f
x
,
ξ
l
s
.
t
.
1
m
x
∑
r
=
1
m
x
G
i
x
,
ξ
r
≤
0
,
1
≤
i
≤
I
,
g
j
x
≤
0
,
1
≤
j
≤
J
,
h
k
x
=
0
,
1
≤
k
≤
K
,where m
(
x
) and n
(
x
) are the sampling sizes of ξ at the point x for the stochastic objective and constraint functions, respectively; ξ
i is the ith observation. It is known that the optimal solution of problem SAM can approach that of problem EP
⁡ when ε
→
0 and m
(
x
)
,
n
(
x
)
→
∞, based on the law of large number [17]. We say that x is an empirically feasible solution for EP
⁡ if the above constraints in SAM are satisfied.In the subsequent work, two adaptive sampling schemes will be designed to estimate the empirical objective and constraint values for each individual. We here cite the following conclusions.Theorem 1 ((Hoeffding’s inequality) see [15, 16]).
LetX be a set, and let F
(
·
) be a probability distribution function onX; f
1
,
…
,
f
n denote the real-valued functions defined on X with f
j
:
X
→
[
a
j
,
b
j
] for j
=
1
,
…
,
n, where a
j and b
j are real numbers satisfying a
j
<
b
j. Let x
1
,
…
,
x
n be the samples of i.i.d. random variables X
1
,
X
2
,
…
,
X
n on X, respectively. Then, the following inequality is true:(3)
Pr
⁡
1
n
∑
j
=
1
n
f
j
x
j
-
1
n
∑
j
=
1
n
∫
x
∈
X
f
j
x
d
F
x
≥
ε
≤
e
-
2
ε
2
n
2
/
∑
j
=
1
n
b
j
-
a
j
2
.Corollary 2 (see [15, 16]).
IfX
1
,
X
2
,
…
,
X
n are i.i.d. random variables with mean μ and a
≤
X
j
≤
b, 1
≤
j
≤
n, then(4)
X
-
n
-
μ
≤
K
Δ
,
n
,
δ
≡
Δ
1
2
n
ln
⁡
2
δ
,with probability at least 1
-
δ, where X
-
n
=
(
1
/
n
)
∑
j
=
1
n
X
^
j and Δ
=
b
-
a; X
^
j and δ denote the observation of X
j and the significance level.


## 3. Racing Sampling Approaches

### 3.1. Expected Value Constraint Handling

Usually, when an intelligent optimization approach with static sampling is chosen to solve the above problemEP
⁡, each individual with the same and sufficiently large sampling size, which necessarily causes high computational complexity. Therefore, in order to ensure that each individual in a given finite population A has a rational sampling size, we in this subsection give a lower bound estimate to control the value of m
(
x
) with x
∈
A, based on the sample average approximation model of the above problem. Define(5)
X
ε
=
x
∈
A
∣
E
G
i
x
,
ξ
≤
ε
,
1
≤
i
≤
I
,
X
m
=
x
∈
A
∣
1
m
∑
j
=
1
m
G
i
x
,
ξ
j
≤
0,1
≤
i
≤
I
.We next give a lower bound estimate to justify thatX
m is a subset of X
ε with probability 1
-
δ, for which the proof can be found in Appendix.Lemma 3.
If there exista
i
(
x
) and b
i
(
x
) such that P
r
a
i
(
x
)
≤
G
i
(
x
,
ξ
)
≤
b
i
(
x
)
,
1
≤
i
≤
I
=
1 with x
∈
A, one has that P
r
X
m
⊆
X
ε
≥
1
-
δ, provided that(6)
m
≥
M
δ
≡
Λ
2
2
ε
2
l
o
g
A
δ
,where Λ
=
m
a
x
b
i
(
x
)
-
a
i
(
x
)
∣
x
∈
A
,
1
≤
i
≤
I and A denotes the size of A.In (6), a
i
(
x
) and b
i
(
x
) are decided by the bounds of the stochastic constraint functions at the point x. Λ is the maximal sampling difference computed by the observations of the stochastic constraints. We also observe that once ε and  δ are defined, M
δ is determined by A. Additionally, those high-quality individuals in A should usually get large sampling sizes, and conversely those inferior ones can only get small sampling size. This means that different individuals will gain different sampling sizes. Based on this consideration and the idea of racing ranking, we next compute the empirical value of any expected value constraint function G
(
x
,
ξ
) at a given individual x in A, that is, G
^
(
x
). This is completed by the following racing-based constraint evaluation approach (RCEA).Step 1.
Input parameters: initial sampling sizem
0, sampling amplitude λ, relaxation factor ε, significance level δ, and maximal sampling size M
δ.Step 2.
Setm
=
m
0, s
=
m
0, and λ
←
l
n
(
1
+
m
0
); calculate the estimate G
^
(
x
) through m observations.Step 3.
Sets
←
λ
s.Step 4.
Creates observations, and update G
^
(
x
); that is, (7)
G
^
x
⟵
m
G
^
x
+
∑
i
=
1
s
G
x
,
ξ
i
m
+
s
.Step 5.
Setm
←
m
+
s; if m
≤
M
δ and G
^
x
≤
K
(
Δ
,
m
,
δ
), then go to Step 3.Step 6.
OutputG
^
x as the estimated value of G
x
,
ξ.In the above formulation,M
δ and K
(
Δ
,
m
,
δ
) are used to decide when the above algorithm terminates. Once the above procedure is stopped, x obtains its sampling size m
(
x
); that is, m
(
x
)
=
m. We note that K
(
Δ
,
m
,
δ
) is very small if m is large. Thereby, we say that x is an empirical feasible solution if, in the precondition of G
^
x
≤
0, the above deterministic constraints are satisfied. Further, RCEA indicates that an empirical feasible solution x can acquire a large sampling size so that G
^
x is close to the expected value of G
(
x
,
ξ
).


### 3.2. Objective Function Evaluation

Depending on the above RCEA and the deterministic constraints in problemEP
⁡, the above population A is divided into two subpopulations of B and C, where B consists of empirical feasible solutions in A. We investigate another lower bound estimate to control the value of n
(
x
) with x
∈
B, relying upon the sample average approximation model of the problem EP
⁡. Afterwards, an approach is designed to calculate the empirical objective values of empirical feasible solutions in B. To this point, introduce (8)
S
ε
=
x
∈
B
∣
E
f
x
,
ξ
≤
f
∗
+
ε
,
S
n
=
x
∈
B
∣
1
n
∑
k
=
1
n
f
x
,
ξ
k
≤
f
^
n
,where f
∗ and f
^
n stand for the minima of theoretical and empirical objective values of individuals in B, respectively. The lower bound estimate is given below, by identifying the approximation relation between S
ε and S
n. The proof can be known in Appendix.Lemma 4.
If there existc
(
x
) and d
(
x
) such that P
r
c
(
x
)
≤
f
(
x
,
ξ
)
≤
d
(
x
)
=
1 with x
∈
B, then P
r
S
n
⊆
S
ε
≥
1
-
δ, provided that(9)
n
≥
n
B
≡
2
Γ
2
ε
2
ln
⁡
2
B
δ
,where Γ
=
m
a
x
d
(
x
)
-
c
(
x
)
∣
x
∈
B
.Like the above constraint handling approach, we next calculate the empirical objective values of individuals inB through the following racing-based objective evaluation approach (ROEA).Step 1.
Input parameters:ε and δ mentioned above, initial sampling size n
0, and population B.Step 2.
Setn
←
n
0, s
←
n
0, λ
←
l
n
(
1
+
n
0
), and Φ
←
B.Step 3.
Calculate the empirical objective average ofn observations for each individual x in Φ, that is, f
-
n
x; write f
-
m
i
n
=
m
i
n
{
f
-
n
x
,
x
∈
Φ
} and f
-
m
a
x
=
m
a
x
{
f
-
n
x
,
x
∈
Φ
}.Step 4.
Remove those elements inΦ satisfying f
^
n
x
>
f
-
m
i
n
+
K
(
f
-
m
a
x
-
f
-
m
i
n
,
n
,
δ
).Step 5.
Sets
←
λ
s.Step 6.
Update the empirical objective values for elements inΦ through(10)
f
^
n
x
⟵
f
^
n
x
×
n
+
∑
k
=
1
s
f
x
,
ξ
k
n
+
s
,
x
∈
B
.Step 7.
Setn
←
n
+
s.Step 8.
Ifn
<
n
|
B
| and Φ
≠
ϕ, then return to Step 3; otherwise, output all the empirical objective values of individuals in B.Through the above algorithm, those individuals inB can acquire their respective empirical objective values with different sampling sizes. Those high-quality individuals can get large sampling sizes, and hence their empirical objective values can approach their theoretical objective values.


## 3.1. Expected Value Constraint Handling

Usually, when an intelligent optimization approach with static sampling is chosen to solve the above problemEP
⁡, each individual with the same and sufficiently large sampling size, which necessarily causes high computational complexity. Therefore, in order to ensure that each individual in a given finite population A has a rational sampling size, we in this subsection give a lower bound estimate to control the value of m
(
x
) with x
∈
A, based on the sample average approximation model of the above problem. Define(5)
X
ε
=
x
∈
A
∣
E
G
i
x
,
ξ
≤
ε
,
1
≤
i
≤
I
,
X
m
=
x
∈
A
∣
1
m
∑
j
=
1
m
G
i
x
,
ξ
j
≤
0,1
≤
i
≤
I
.We next give a lower bound estimate to justify thatX
m is a subset of X
ε with probability 1
-
δ, for which the proof can be found in Appendix.Lemma 3.
If there exista
i
(
x
) and b
i
(
x
) such that P
r
a
i
(
x
)
≤
G
i
(
x
,
ξ
)
≤
b
i
(
x
)
,
1
≤
i
≤
I
=
1 with x
∈
A, one has that P
r
X
m
⊆
X
ε
≥
1
-
δ, provided that(6)
m
≥
M
δ
≡
Λ
2
2
ε
2
l
o
g
A
δ
,where Λ
=
m
a
x
b
i
(
x
)
-
a
i
(
x
)
∣
x
∈
A
,
1
≤
i
≤
I and A denotes the size of A.In (6), a
i
(
x
) and b
i
(
x
) are decided by the bounds of the stochastic constraint functions at the point x. Λ is the maximal sampling difference computed by the observations of the stochastic constraints. We also observe that once ε and  δ are defined, M
δ is determined by A. Additionally, those high-quality individuals in A should usually get large sampling sizes, and conversely those inferior ones can only get small sampling size. This means that different individuals will gain different sampling sizes. Based on this consideration and the idea of racing ranking, we next compute the empirical value of any expected value constraint function G
(
x
,
ξ
) at a given individual x in A, that is, G
^
(
x
). This is completed by the following racing-based constraint evaluation approach (RCEA).Step 1.
Input parameters: initial sampling sizem
0, sampling amplitude λ, relaxation factor ε, significance level δ, and maximal sampling size M
δ.Step 2.
Setm
=
m
0, s
=
m
0, and λ
←
l
n
(
1
+
m
0
); calculate the estimate G
^
(
x
) through m observations.Step 3.
Sets
←
λ
s.Step 4.
Creates observations, and update G
^
(
x
); that is, (7)
G
^
x
⟵
m
G
^
x
+
∑
i
=
1
s
G
x
,
ξ
i
m
+
s
.Step 5.
Setm
←
m
+
s; if m
≤
M
δ and G
^
x
≤
K
(
Δ
,
m
,
δ
), then go to Step 3.Step 6.
OutputG
^
x as the estimated value of G
x
,
ξ.In the above formulation,M
δ and K
(
Δ
,
m
,
δ
) are used to decide when the above algorithm terminates. Once the above procedure is stopped, x obtains its sampling size m
(
x
); that is, m
(
x
)
=
m. We note that K
(
Δ
,
m
,
δ
) is very small if m is large. Thereby, we say that x is an empirical feasible solution if, in the precondition of G
^
x
≤
0, the above deterministic constraints are satisfied. Further, RCEA indicates that an empirical feasible solution x can acquire a large sampling size so that G
^
x is close to the expected value of G
(
x
,
ξ
).


## 3.2. Objective Function Evaluation

Depending on the above RCEA and the deterministic constraints in problemEP
⁡, the above population A is divided into two subpopulations of B and C, where B consists of empirical feasible solutions in A. We investigate another lower bound estimate to control the value of n
(
x
) with x
∈
B, relying upon the sample average approximation model of the problem EP
⁡. Afterwards, an approach is designed to calculate the empirical objective values of empirical feasible solutions in B. To this point, introduce (8)
S
ε
=
x
∈
B
∣
E
f
x
,
ξ
≤
f
∗
+
ε
,
S
n
=
x
∈
B
∣
1
n
∑
k
=
1
n
f
x
,
ξ
k
≤
f
^
n
,where f
∗ and f
^
n stand for the minima of theoretical and empirical objective values of individuals in B, respectively. The lower bound estimate is given below, by identifying the approximation relation between S
ε and S
n. The proof can be known in Appendix.Lemma 4.
If there existc
(
x
) and d
(
x
) such that P
r
c
(
x
)
≤
f
(
x
,
ξ
)
≤
d
(
x
)
=
1 with x
∈
B, then P
r
S
n
⊆
S
ε
≥
1
-
δ, provided that(9)
n
≥
n
B
≡
2
Γ
2
ε
2
ln
⁡
2
B
δ
,where Γ
=
m
a
x
d
(
x
)
-
c
(
x
)
∣
x
∈
B
.Like the above constraint handling approach, we next calculate the empirical objective values of individuals inB through the following racing-based objective evaluation approach (ROEA).Step 1.
Input parameters:ε and δ mentioned above, initial sampling size n
0, and population B.Step 2.
Setn
←
n
0, s
←
n
0, λ
←
l
n
(
1
+
n
0
), and Φ
←
B.Step 3.
Calculate the empirical objective average ofn observations for each individual x in Φ, that is, f
-
n
x; write f
-
m
i
n
=
m
i
n
{
f
-
n
x
,
x
∈
Φ
} and f
-
m
a
x
=
m
a
x
{
f
-
n
x
,
x
∈
Φ
}.Step 4.
Remove those elements inΦ satisfying f
^
n
x
>
f
-
m
i
n
+
K
(
f
-
m
a
x
-
f
-
m
i
n
,
n
,
δ
).Step 5.
Sets
←
λ
s.Step 6.
Update the empirical objective values for elements inΦ through(10)
f
^
n
x
⟵
f
^
n
x
×
n
+
∑
k
=
1
s
f
x
,
ξ
k
n
+
s
,
x
∈
B
.Step 7.
Setn
←
n
+
s.Step 8.
Ifn
<
n
|
B
| and Φ
≠
ϕ, then return to Step 3; otherwise, output all the empirical objective values of individuals in B.Through the above algorithm, those individuals inB can acquire their respective empirical objective values with different sampling sizes. Those high-quality individuals can get large sampling sizes, and hence their empirical objective values can approach their theoretical objective values.


## 4. Algorithm Statement

The clonal selection principle explains how immune cells learn the pattern structures of invading pathogens. It includes many biological inspirations capable of being adopted to designμIOA, such as immune selection, cloning, and reproduction. Based on RCEA and ROEA above as well as general immune inspirations, μIOA can be illustrated by Figure 1. We here view antigen Ag as problem SAM itself, while candidates from the design space D are regarded as real-coded antibodies. Within a run period of μIOA by Figure 1, the current population is first divided into empirical feasible and infeasible antibody subpopulations after executing RCEA above. Second, those empirical feasible antibodies are required to compute their empirical objective values through ROEA. They will produce many more clones than empirical infeasible antibodies through proliferation. Afterwards, all the clones are enforced mutation. If a parent is superior to its clones, it will carry out local search, and conversely it is updated by its best clone. Based on Figure 1, μIOA can be formulated in detail below.Figure 1
The flowchart ofμIOA.Step 1.
Input parameters: population sizeN, maximal clonal size C
m
a
x, sampling parameters m
0 and n
0, relaxation factor ε, significance level δ, and maximal iteration number G
m
a
x.Step 2.
Sett
←
1.Step 3.
Generate an initial populationA of N random antibodies.Step 4.
Compute the empirical constraint violations of antibodies inA through RCEA and (1), that is, Γ
^
(
x
) with x
∈
A.Step 5.
DivideA into empirical feasible subpopulation B and infeasible subpopulation C.Step 6.
Calculate the empirical objective values of antibodies inB through ROEA above.Step 7.
For each antibodyx in B, we have the following.Step
7.1. Proliferate a clonal set C
l
(
x
) with size C
m
a
x (i.e., x multiplies C
m
a
x offsprings).Step
7.2. Mutate all clones with mutation rate p
m
(
x
)
=
1
/
(
Γ
m
a
x
+
l
n
(
t
+
1
)
) through the classical polynomial mutation, and thereafter produce a mutated clonal set C
l
∗
(
x
), where Γ
m
a
x
=
m
a
x
{
Γ
^
(
x
)
∣
x
∈
C
}.Step
7.3. Eliminate empirical infeasible clones in C
l
∗
(
x
) through RCEA.Step
7.4. Calculate the empirical objective values of clones in C
l
∗
(
x
) through ROEA.Step
7.5. If the best clone has a smaller empirical objective value than x, it will update x; otherwise, antibody x as an initial state creates a better empirical feasible antibody to replace it by a local search approach [18] with ROEA and sampling size m
0.Step 8.
For each antibodyy in C, we have the following.Step
8.1. Antibody y creates a clonal population C
(
y
) with clonal size C
l
(
y
); all clones in C
(
y
) are enforced to mutate with mutation rate p
m
(
y
) through the conventional nonuniform mutation and create a mutated clonal population C
∗
(
y
), where(11)
C
l
y
=
r
o
u
n
d
C
m
a
x
Γ
^
y
+
1
,
p
m
y
=
1
Γ
m
a
x
-
Γ
^
y
+
1
.Step
8.2. Check if there exist empirical feasible clones in C
∗
(
y
) by RCEA and (1); if yes, the best clone with the smallest empirical objective value by ROEA replaces y, and conversely the clone with the smallest constraint violation updates y.Step 9.
A
←
B
∪
C, and t
←
t
+
1.Step 10.
Ift
<
G
m
a
x, go to Step 4, and conversely output the best antibody viewed as the optimal solution.As we formulate above, the current populationA is split into two subpopulations, after being checked if there are empirical feasible antibodies. Each subpopulation is updated through proliferation, mutation, and selection. Step 7 makes those empirical feasible antibodies search better clones through proliferation and polynomial mutation. Once some antibody can not produce a valuable clone, a reported local search algorithm is used to perform local evolution so as to enhance the quality of solution search. The purpose of Step 8 urges those poor antibodies to create diverse clones through proliferation and nonuniform mutation.Additionally,μIOA’s computational complexity is decided by Steps 4, 6, and 7.2. Step 4 needs at most N
(
I
M
δ
+
J
+
K
+
1
) times to calculate the empirical constraint violations. In Step 6, we need to compute the empirical objective values of antibodies in B, which evaluates at most N
n
N times. Step 7.2 enforces mutation with at most N
p
×
C
m
a
x times. Consequently, μIOA’s computational complexity in the worst case can be given by (12)
O
c
=
O
N
I
M
δ
+
J
+
K
+
N
n
N
+
N
p
C
m
a
x
=
O
N
I
M
δ
+
J
+
K
+
n
N
+
p
C
m
a
x
.


## 5. Experimental Analysis

Our experiments are executed on a personal computer (CPU/3 GHz, RAM/2 GB) with VC++ software. In order to examineμIOA’s characteristics, four intelligent optimization algorithms, that is, two competitive steady genetic algorithms (SSGA-A and SSGA-B) [19] and two recent immune optimization approaches NIOA-A and NIOA-B [20], are taken to participate in comparative analysis by means of two 100-dimentional multimodal expected value optimization problems. It is pointed out that the two genetic algorithms with the same fixed sampling size for each individual can still solve EP
⁡ problems, since their constraint scoring functions are designed based on static sampling strategies; the two immune algorithms are with dynamic sampling sizes for all individuals presented in the process of evolution. On the other hand, since NIOA-B can not effectively handle high-dimensional problems, we in this section improve it by OCBA [21]. These comparative approaches, together with μIOA, share the same termination criterion; namely, each approach is with the total of evaluations 8
×
10
5, while executing 30 times on each test problem. Their parameter settings are the same as those in their literatures except for their evolving population sizes. After manual experimental tuning, they take population size 40. μIOA takes a small population size within 3 and 5, while the three parameters of m
0, n
0, and C
m
a
x as crucial efficiency parameters are usually set as small integers. We here set N
=
5, m
0
=
30, n
0
=
20, C
m
a
x
=
2, ε
=
0.1, and δ
=
0.05. Additionally, those best solutions, acquired by all the algorithms for each test problem are reevaluated 106 times because of the demand of algorithm comparison.Example 5.
Consider(13)
m
a
x
E
∑
i
=
1
p
c
o
s
4
x
i
-
2
∏
i
=
1
p
c
o
s
2
x
i
∑
i
=
1
p
i
x
i
2
+
ξ
s
.
t
.
E
0.75
-
η
1
∏
i
=
1
p
x
i
≤
0
,
∑
i
=
1
p
E
η
2
x
i
-
7.5
p
≤
0
,
0
≤
x
i
≤
10
,
ξ
~
N
0,1
,
1
≤
i
≤
p
,
η
1
~
N
0.0015,0.2
,
η
2
~
N
1,2
.
This is a multimodal expected value programming problem gotten through modifying a static multimodal optimization problem [22], where p
=
100. The main difficulty of solving such problem is that the high dimension and multimodality make it difficult to find the desired solution. We solve the above problem by means of the approximation model SAM as in Section 2, instead of transforming such model into a deterministic analytical one. After, respectively 30, runs, each of the above algorithms acquires 30 best solutions used for comparison. Their statistical results are listed in Table 1, while Figures 2 and 3 draw the box plots of the objective values acquired and their average search curves, respectively.Table 1
Comparison of statistical results for Example5.
Algor.
Max.
Min.
Mean
Std. dev.
CI
FR (%)
AR (s)
SSGA-A
0.14
0.10
0.11
0.01
[
0.11
,
0.12
]
80
49.5
SSGA-B
0.13
0.10
0.11
0.01
[
0.11
,
0.12
]
87
49.6
NIOA-A
0.25
0.16
0.21
0.03
[
0.20
,
0.22
]
80
27.6
NIOA-B
0.26
0.17
0.20
0.02
[
0.19
,
0.21
]
87
24.7
μIOA
0.39
0.22
0.29
0.05
[
0.27
,
0.31
]
90
16.1
CI represents the confidence interval of objective values for the solutions acquired; FR stands for the rate of feasible solutions among all the gotten solutions; AR denotes the average runtime required by 30 runs.Figure 2
Example5: comparison of box plots acquired.Figure 3
Example5: comparison of average search curves.In Table1, the values on FR, listed in the seventh column, hint that whereas all the algorithms can find many feasible solutions for each run, their rates of feasible solutions are different. μIOA can acquire many more feasible solutions than the compared approaches. This illustrates that the constraint handling approach RCEA, presented in Section 3, can ensure that μIOA find feasible solutions with high probability 90% for a single run. On the other hand, the statistical results in columns 2 to 6 show that μIOA’s solution quality is clearly superior to those acquired by other approaches and meanwhile NIOA-A and NIOA-B are secondary. With respect to performance efficiency, we see easily that μIOA is a high-efficiency optimization algorithm, as it spends the least time to seek the desired solution in a run. We also notice that SSGA-A and SSGA-B present their high computational complexity because of their average runtime, which shows that such two genetic algorithms with static sampling strategies cause easily expensively computational cost.The box plots in Figure2, formed by 30 objective values for each algorithm, exhibit the fact that, in addition to μIOA obtaining the best effect by comparison with the other four algorithms, NIOA-A and NIOA-B with similar performance characteristics can work well over SSGA-A and SSGA-B. By Figure 3, we observe that μIOA can find the desired solution rapidly and achieve stable search but the other algorithms, in particular the two genetic algorithms, get easily into local search. Totally, when solving the above higher-dimensional problem, the five algorithms have different efficiencies, solution qualities, and search characteristics; μIOA suits the above problem and exhibits the best performance, for which the main reason consists in that it can effectively combine RCEA with ROEA to find many more empirically feasible individuals and urge them to evolve gradually towards the desired regions by proliferation and mutation. However, those compared approaches present relatively weak performances. In particular, SSGA-A and SSGA-B get easily into local search and spend the most runtime to solve the above problem, as their constraint handling and selection techniques are hard to adapt to high-dimensional multimodal problems. NIOA-A and NIOA-B are superior to such two genetic algorithms, owing to their adaptive sampling and constraint handling techniques.Example 6.
Consider(14)
m
a
x
E
∑
i
=
1
p
x
i
·
sin
⁡
π
i
x
i
+
ξ
s
.
t
.
E
∑
i
=
1
p
η
1
x
i
≤
500
,
E
∑
i
=
1
p
η
2
x
i
2
≤
3000
,
x
i
≥
0
,
ξ
~
N
0,1
,
1
≤
i
≤
p
,
η
1
~
U
0.8,1.2
,
η
2
~
N
1,0.5
.This is a still difficult multimodal optimization problem obtained by modifying a static multimodal optimization problem [23], including 100 decision variables (i.e., p
=
100) and 3 random variables which greatly influence the quality of solution search. The difficulty of solving such problem is that the objective function is multimodal and the decision variables are unbounded. Similar to the above experiment, we acquire the statistical results of the approaches given in Table 2, while the corresponding box plots and their average search curves are drawn by Figures 4 and 5, respectively.Table 2
Comparison of statistical results for Example6.
Algor.
Max.
Min.
Mean
Std. dev.
CI
FR (%)
AR (s)
SSGA-A
488.0
401.8
458.9
19.2
[
452.1
,
465.8
]
53
26.6
SSGA-B
489.7
415.7
463.0
17.4
[
456.8
,
469.2
]
53
25.8
NIOA-A
410.8
378.2
393.9
8.7
[
390.8
,
397.0
]
100
16.0
NIOA-B
414.6
371.3
395.2
3.9
[
391.3
,
399.0
]
100
13.9
μIOA
464.7
444.3
456.8
5.5
[
454.1
,
458.0
]
100
12.1Figure 4
Example6: comparison of box plots acquired.Figure 5
Example6: comparison of average search curves.The values on FR in Table2 illustrate that it is also difficult to solve Example 6, due to the random variables and high dimensionality. Even if so, NIOA-A, NIOA-B, and μIOA can all acquire feasible solutions for each run. SSGA-A and SSGA-B, however, can only get at most 53% of feasible solutions; namely, they can only acquire 53 feasible solutions after 100 executions. This, along with the values on FR in Table 1, follows that although such two approaches can acquire larger values onMean than the other approaches, they are poor with respect to solution quality, efficiency, and search stability. Consequently, they need to make some improvements, for example, their constraint handling. We notice that μIOA is better than either NIOA-A or NIOA-B because of its efficiency and the value onMean. We emphasize that whereas NIOA-A and NIOA-B can only obtain small values onMean by comparison with μIOA, they are still valuable when solving such kind of hard problem. Relatively, NIOA-B behaves well over NIOA-A.It seems to be true that SSGA-A and SSGA-B are superior to NIOA-A, NIOA-B, andμIOA by Figures 4 and 5, since the box plots in Figure 4 and the average search curves in Figure 5 are far from the horizontal line. As a matter of fact, column 7 in Table 2 shows clearly that such two genetic algorithms cannot find feasible solutions 47 times out of 100 runs, whereas the other approaches are opposite. These indicate a fact that infeasible solutions in the decision domain have larger objective function values than feasible ones.Summarily, when solving the above two examples, the five algorithms present different characteristics. SSGA-A and SSGA-B have similar performance attributes, and so do NIOA-A and NIOA-B.μIOA performs well over the compared approaches, while NIOA-B is secondary.


## 6. Conclusions and Further Work

We in this work concentrate on studying a microimmune optimization algorithm to solve a general kind of constrained expected value programming model, relying upon transforming such model into a sample-dependent approximation model (SAM). One such model requires that different candidate solutions have different sample sizes and especially each candidate has two kinds of samples’ sizes. Subsequently, two lower bound estimates of random vectors are theoretically developed and, respectively, applied to handling expected value constraints of individuals in the current population and computing their empirical objective values. Based on such two estimates and the idea of racing ranking, two racing sampling methods are suggested to execute individual evaluation and constraint handling, respectively. Afterwards, a racing sampling based microimmune optimization algorithmμIOA is proposed to deal with such approximation model, with the merits of small population, strong disturbance suppression, effective constraint handling, adaptive sampling, and high efficiency. The theoretical analysis has indicated that μIOA’s computational complexity depends mainly on n
N, M
δ, and C
m
a
x, due to small population N and known problem parameters. By means of the higher-dimensional multimodal test problems, the comparatively experimental results can draw some conclusions: (
1
) RCEA and RCOEA can make μIOA dynamically determine the sample sizes of different kinds of individuals in the process of evolution, (
2
) the local search approach adopted can help μIOA to strengthen local search, (
3
) stochastic parameters may be efficiently addressed by adaptive sampling techniques, (
4
)  μIOA performs well over the compared approaches, and (
5
) SSGA-A and SSGA-B need to make some improvements for higher-dimensional problems. Further, whereas we make some studies on how to explore immune optimization approaches to solve higher-dimensional constrained expected value programming problems, some issues will be further studied. For example, μIOA’s theoretical convergence analysis needs to be studied, while its engineering applications are to be discussed.



---

*Source: 2148362-2016-03-21.xml*