978-1-4799-7492-4/15/$31.00 © 2015 IEEE
Quantum immune clone for solving constrained multi-objective
optimization
Ronghua Shang, Licheng Jiao, Hao Xu, and Yangyang Li
Abstract—This paper proposes a quantum immune clone
algorithm to solve the constrained multi-objective optimization
problem. Firstly, constraints deviation value is added to objective
function value to form a new objective function value, which
translates the constrained multi-objective optimization problem
into an unconstrained multi-objective optimization problem.
Secondly, it does not only retain the feasible non-dominated
solutions, but also utilizes the non-feasible solutions which have
small constraint deviation value and objective function value.
The appearing of the non-feasible solutions expands the search
scope and makes it easy to evolve solutions near the Pareto front.
Then, a quantum rotating gate is designed to accelerate the
computational speed. At last, crossover and mutation are used to
obtain better individuals. Compared with the state-of-art
algorithm, simulation results show that the proposed algorithm
has a better improvement on GD distance and on the diversity.
I. INTRODUCTION
The constrained multi-objective mathematical model is
given as follow [1~4]:
12
1
12
12 1 2
min ( ) ( ( ), ( ), , ( ))
. . ( ) 0, 1, 2, ,
() 0, 1, ,
(, , )
{( , , , ) | }
(, , , ), ( , , )
k
i
i
n
niii
nn
ff f
st g i q
hiqm
xx
xx x l x u
ll l uu u
=
≤=
= = +
= ∈
= < <
= =
xxx x
x
x
xX
X
lu
!
!
!
"
"
""
(1)
Where,
x
is the decision vector,
X
is the decision variable,
u
and
l
are the decision variable upper bound and lower bound
respectively.
F
(
x
) is the objective function, and f
i
(
x
) is the i-th
objective function. g
i
(
x
)0 (i=1,…,q) is the i-th inequality
constraint. h
j
(
x
)=0 (j=q+1,…,m) is the j-th equality constraint.
Constrained Multi-objective Optimization Problem (CMOP)
is a kind of multi-objective optimization problem with
constraints conditions. As a result, CMOP is more complex and
closer to real life problems. More situations should be
considered when handling CMOP, such as how to deal with
equality constraints and inequality constraints. There are many
successful algorithms dealing with multi-objective
optimization problems, such as NSGA [1], SPEA [2], and
SPEA2 [3]. But few can be directly applied to multi-objective
constrained optimization problems. The main reason is that we
need to design a constraint handling strategy when dealing with
CMOPs.
Ronghua Shang, Licheng Jiao, Hao Xu, and Yangyang Li are with the Key
Laboratory of Intelligent Perception and Image Understanding of Ministry of
Education, Xidian University, Xi’an, 710071, China (phone: 86-29-88202279;
fax: 86-29-88201023; e-mail: rhshang@mail.xidian.edu.cn).
This work was partially supported by the National Basic Research Program
(973 Program) of China under Grant 2013CB329402, the National Natural
Science Foundation of China, under Grants 61371201, 61272279, 61373111
and 61203303, the Program for Cheung Kong Scholars and Innovative
Research Team in University under Grant IRT1170, and the EU FP7 project
(grant no. 247619) on “NICaiA: Nature Inspired Computation and its
Applications”.
However, a good constraint handling strategy is not easy to
design. In recent years, researchers pay increasing attention on
the CMOP. Many excellent algorithms have been proposed by
scholars. Different algorithms use different method to deal with
the feasible solutions and non-feasible solutions. The design of
the constraints directly affects the quality of the results. In
earlier studies, Coello [4] ignored the individual directly that
violates any constraints, and looked for other individuals,
which is easy to implement. But the algorithm mainly pays
attention on finding out feasible solution instead of the non-
dominated solution. Reference [5] designed a formula to
evaluate the degree of the individual violating the constraint
condition. After that, researchers adopted this idea and began to
quantify the violation degree. The idea in NSGA-II [6] is that if
two individuals are feasible solutions, the non-dominated
individual will be selected. If two individuals are non-feasible
solutions, the individual who has a small constraints deviation
value will be selected. If one is feasible solution and the other
is non-feasible solution, the feasible solution will be selected.
Reference [7] proposed the SBMS that can make a correction
for non-dominated solutions. Venkatraman proposed a method
that divides the CMOP into two steps [8]. Young assigned each
individual two non-dominated levels [9]. Woldesenbet put
forward the constrained multi-objective evolutionary algorithm
which utilizes a new constraint handling strategy to deal with
the objective function [10]. In [11], Jaddan added individual
non-dominance grade in the objective space and the constraint
space to the objective space. Isaacs [12] divided the solutions
into feasible solutions set and non-feasible solutions set.
After researching the existed algorithms, we found that the
current algorithms still need to be improved on the
performance of the obtained solutions. Therefore, we need to
design an algorithm with three objectives, (1) high accuracy, (2)
low computational complexity, and (3) a short running time.
Innovations of this paper are as follows: 1. The proposed
algorithm uses quantum computing to accelerate the algorithm
calculation speed, and the quantum clone operator is used to
deal with CMOP. In quantum computation process, the real
number coding of each individual is transformed to quantum
coding, and then a quantum rotating gate is designed which
could quickly search the peripheral region. 2. The constraint
handling strategy used in this paper is similar with reference
[10]. Firstly the proposed algorithm randomly generates a
population Pop, quickly calculates each individual’s objective
function value and constraints deviation value in the population
Pop, and the two values are summed to form a new objective
function value. Next, it creates an elite population FeaPop to
save the feasible non-dominated solutions selected from the
population Pop, and the population NonPop is used to save the
non-dominated solutions. This process can help some non-
feasible solutions to participate in the evolutionary process. 3.
In cloning process, we just copy the population NonPop instead
of the population FeaPop. Experiment results show that this