An imperialist competitive algorithm for solving dynamic nonlinear constrained optimization problems

Abstract

Dynamic nonlinear constrained optimization problems (DNCOP) have been arisen in a diverse range of sciences, such as agriculture, economics, airspace engineering, chemistry, mechanics, management etc.. In order to solve DNCOP, we are interested in the designed algorithm not only to find the optimal solutions or the quasi-optimum solutions, but recover and track the trajectory of the optimal solutions changing with the time. In this paper, the considering DNCOP is transformed into a dynamic unconstrained optimization problem by adding the slack variables to the inequations constraint of the original problem firstly. Secondly, an improved imperialist competitive optimization algorithm for solving the DNCOP is proposed. At last, the computation simulations show that the proposed algorithm is more effective and can find the better optimal solutions or the quasi-optimum solutions in environment-varying than the compared algorithms for dynamic nonlinear constrained optimization problem.

Keywords

Dynamic optimization nonlinear constrained optimization imperialist competitive algorithm optimal solution

1 Introduction

In real world, many optimization problems involve in uncertain environments [1, 2]. That’s to say, those practical problems change constantly, such as, a GPS navigation system that has to recalculate the route when the car does not follow the proposed route. When solving these optimization problems, it is difficult to deal with the dynamic equality constraints or inequality constraints and track the trajectory of optimal solutions changing with the time or called environment. Mostly often, while it is possible that a small change in the problem creates a big change in the optimal solutions [3], e.g. for the above GPS system, when a car goes forward instead of turning left, the initial position is almost the same and it may suffice to take the next leftturn.

In reference [1], Y. C. Jin and J. Branke identified four different types of dynamic optimization problems according to the environment change.

Type 1: the fitness function is noisy.

Type 2: the design variables and the environmental parameters may change after optimization.

Type 3: the fitness function is approximated, which means that the fitness function suffers from approximation errors.

Type 4: the optimum of the problem to be solved changes over time slowly and continuously.

In this paper, the fourth type of dynamic optimization problems will be discussed. In fact, dynamic optimization problem (DOP) can also be further divided into two forms according to the number of the optimal objective function, i.e., one is dynamic simple-objective optimization problem (DSOP), and the other is dynamic multi-objective optimization problem (DMOP) [4, 5].

When considering DSOP, several artificial intelligence approaches have been reported in the literature [6 –10], these methods mainly have been used to solve dynamic unconstrained simple-objective optimization problem or these problems owned unimodal dynamic optimal solution.

However, when using evolutionary algorithm (EA) to solve dynamic nonlinear constrained optimization problem, we are usually interested in the abilities of the designed algorithm not only to escape from the local optimal solution and recover from the change of environment quickly, but also to deal with the constraints varying with the environment and find the trajectory of the optimal solutions changing with the environment. Although these algorithms have been acted some good roles on solving optimization problems, the existing optimization methods still encounter many challenges since most of them can not find the optimal solutions or the quasi-optimum solutions with the change of time parameter. In addition, the existing evolutionary algorithms have more difficulties in responding to the change of time parameter and escaping from the bound of the local optimal solutions, the main reason is that most of them can not find the optimal solutions with the change of time parameter. Furthermore, when the optimal solution of dynamic optimization problem gradually and continuously change with the time or the environment, the algorithms are very difficult to get the optimal solutions or the quasi-optimum solutions for dynamic optimization problem at every continuous moment, and are easy to fall into the local optimization solutions although they try todo so.

To overcome these drawbacks and obtain the optimal solutions or the quasi-optimum solutions for the dynamic nonlinear constrained optimization problem, one reasonable method is to get the optimal solutions or high quality quasi-optimal solutions at some representative moments instead of every moment and these solutions satisfied the constrained conditions of the problem. The main difference between the proposed algorithm and the existing algorithms is that the proposed algorithm does not focus on finding the optimal solutions at all time parameter variables but tries to find the optimal solutions or the quasi-optimum solutions in some representative environments, where the optimal solutions or the quasi-optimum solutions defined in these time subperiods vary with the time parameter gradually and continuously.

To achieve this purpose, on the one hand, the considering dynamic nonlinear constrained optimization problem is transformed into a dynamic unconstrained optimization problem by adding the slack variables to the inequations constraints firstly. Then, a new evolution method based on the imperialist competitive algorithm to solve the dynamic nonlinear constrained optimization problem is proposed. And the simulation results are made on four typical dynamic multi-objective constrained optimization problems, and indicate the proposed algorithm can effectively track and find the varying optimal solutions for dynamic nonlinear constrained simple-objective optimization problem.

The paper is organized as follows. In Section 2, the related concepts of the dynamic nonlinear constrained optimization problem are given. The main steps of the imperialist competitive algorithm for solving the dynamic nonlinear constrained optimization problem is proposed in Section 3. The flowchart of the proposed algorithm and the indicators of performance are described in Section 4 and 5, respectively. After simulation results are shown in Section 6. The conclusions are made in Section 7.

2 Related concepts of DNCOP

Without loss of generality, we consider the dynamic nonlinear constrained optimization problem (DNCOP) as follows: ${\begin{matrix} min_{x \in B \subseteq [L, U]} f (x, t) \\ s . t . g_{i} (x, t) \geq 0, i = 1, 2, \dots, p \\ h_{j} (x, t) = 0, j = p + 1, p + 2, \dots, l \end{matrix},$ (1)where paremeter t ∈ [a, b] is the environment variable, x = (x₁, x₂, ⋯ , x_n) ^T is n dimension decision variable, and g_i (x, t) ≥0 is the inequation constraint for i = 1, 2, ⋯ , p, h_j (x, t) =0 is the equation constraint for j = p + 1, p + 2, ⋯ , l depending on the environment variable t, respectively, and $B = {x | | \begin{matrix} g_{i} (x, t) \geq 0, i = 1, \dots, p \\ h_{j} (x, t) = 0, j = p + 1, p + 2, \dots, l \end{matrix}}$ (2)is feasible region. $[L, U] = {[l_{1}, u_{1}] \times \dots \times [l_{n}, u_{n}] | \begin{matrix} l_{i} \leq x_{i} \leq u_{i} \\ i = 1, 2, \dots, n \end{matrix}}$ (3)is the search space, where l_i and u_i are the lower bound and upper bound of the variable x_i for i = 1, 2, ⋯ , n, respectively.

Definition 1. At environment variable t, for every point x ∈ B, if exists another point x^* ∈ B such that f (x^*, t) ≤ f (x, t) holds, then the point x^* is called the optimal solution, f (x^*, t) is called the optimal objective function value.

For DNCOP (1), we add the slack variables λ_i (i = 1, 2, ⋯ , p) in each inequality constraints of the formula (1) and make all the constraints become equality constraints, i.e., the problem (1) can be transformed into the following optimization problem, i.e., ${\begin{matrix} min_{x \in B \subseteq [L, U]} f (x, t) \\ s . t . g_{i} (x, t) - λ_{i} = 0, i = 1, 2, \dots, p \\ h_{j} (x, t) = 0, j = p + 1, p + 2, \dots, l \end{matrix},$ (4)where the slack variable $λ_{i} \in ℝ$ is non-negative variable for i = 1, 2, ⋯ , p. In order to solve the problem (4), we further transform the formula (4) into the following unconstrained dynamic optimization problem, i.e.,

$\begin{matrix} min_{\tilde{x} \in Ω \subseteq [L^{'}, U^{'}]} F (\tilde{x}, t) = f (x, t) + \sum_{i = 1}^{p} (g_{i} (x, t) - λ_{i})^{2} \\ + \sum_{j = p + 1}^{l} (h_{j} (x, t))^{2}, \end{matrix}$ (5)where $\tilde{x} \in (x, λ)^{T} \in ℝ^{n + p}$ , x = (x₁, x₂, ⋯ , x_n) ^T $\in ℝ^{n}$ , $λ = (λ_{1}, λ_{2}, \dots, λ_{p})^{T} \in ℝ^{p}$ , [L′, U′] = [L, U] ⊕ [A, B] is the new search space of problem (5), where $[A, B] = {[a_{1}, b_{1}] \times \dots \times [a_{p}, b_{p}] | \begin{matrix} a_{i} \leq λ_{i} \leq b_{i} \\ i = 1, 2, \dots, p \end{matrix}}$ (6)

and $Ω = {\tilde{x} = (x, λ)^{T} | \begin{matrix} l_{i} \leq x_{i} \leq u_{i}, i = 1, 2, \dots, n \\ a_{j} \leq λ_{j} \leq b_{j}, j = 1, 2, \dots, p \end{matrix}}$ (7)is feasible region of problem (5). According to the analysis above, we can easily obtain the following conclusion.

Suppose $x^{*} = (x_{1}^{*}, x_{2}^{*}, \dots, x_{n}^{*}, λ_{1}^{*}, λ_{2}^{*}, \dots, λ_{p}^{*})^{T}$ ∈Ω is the feasible optimal solution of problem (5) at fixed moment t, then, g_i (x, t) → λ_i for each index i, and h_j (x, t) →0 for each index j are hold, thus, $x^{*} = (x_{1}^{*}, \dots, x_{n}^{*}, 0, \dots, 0)^{T}$ is the optimal solution of problem (1); Conversely, suppose that the solution $\bar{x} = ({\bar{x}}_{1}, {\bar{x}}_{2} \dots, {\bar{x}}_{n})^{T} \in B$ is the optimal solution of problem (1), then, $g_{i} (\bar{x}, t) \geq 0$ and $h_{j} (\bar{x}, t) = 0$ are hold for every index i and j, respectively, let ${\bar{λ}}_{i} = g_{i} (\bar{x}, t)$ for i = 1, 2, ⋯ , n, thus, feasible point $x^{*} = (\bar{x}, {\bar{λ}}_{1}, {\bar{λ}}_{2}, \dots, {\bar{λ}}_{p})^{T} \in ℝ^{n + p}$ is the optimal solution of problem (5).

3 Imperialist competitive algorithm

Imperialist competitive algorithm (ICA) [11], similar to the genetic algorithm, particle swarm optimization algorithm and so on, is a kind of intelligence optimization algorithm proposed by E. Atashpaz-Gargari and C. Lucas in 2007. In recent years, ICA has been widely used to solve many real world engineering and optimization problems for the reason that ICA has a polynomial convergence velocity and can easily escape from the local optimal solution [12 –14]. In ICA, we generate an initial population similar to the genetic evolution as initial countries. Some of the best countries among the initial countries are selected to form the initial imperialists, and the rest of the countries are divided among the initial imperialists as colonies based on sound rules. Then, each imperialist along with its colonies is regard as empire. All the empires start to compete among each other. The weakest empire, which cannot succeed in the competition, will be eliminated from the competition and take part in the strongest power imperialist. As a result, all colonies move toward their relevant imperialists along with the competition among empires. Finally, the collapse mechanism will cause all the colonies to converge to a state which is the global optimal solution.

3.1 Initial empires creation

At initial moment t, we generate N_pop initial countries based on the orthogonal design proposed in [15]. Mostly often, denote these initial countries as $country (i) = (x_{1}^{i}, x_{2}^{i}, \dots, x_{n}^{i}, λ_{1}^{i}, λ_{2}^{i}, \dots, λ_{p}^{i})^{T} \in [L^{'}, U^{'}]$ for i = 1, 2, ⋯ , n, and define the cost of each country (i) as follows: $\begin{matrix} cost = F (country (i), t) \\ = F ((x_{1}^{i}, x_{2}^{i}, \dots, x_{n}^{i}, λ_{1}^{i}, λ_{2}^{i}, \dots, λ_{p}^{i}), t) . \end{matrix}$ (8)

Select N_imp (N_imp ⪡ N_pop) powerful countries from the initial countries and form N_imp empires, the rest countries of the initial countries will become colonies of each of empires according to their power. Thus, each empire receives a number of colonies. This process is presented in Fig. 1, where the powerful empires have a greater number of colonies and weaker empires have fewer colonies, At last, these countries is divided into two groups: imperialist and colony (denote in imperialist (i) and colony (j) for i = 1, 2, ⋯ , N_imp, j = 1, 2, ⋯ , N_col, respectively, where N_col = N_pop - N_imp). In order to form the initial empires, we divide colonies into N_imp imperialists based on their power. In this paper, we divide these colonies among imperialists according to the method of proportion selection or the roulette wheel selection used in genetic evolution as follows:

1. Suppose the normalized power of each imperialist is defined by $p_{j} = | \frac{C_{j}}{\sum_{i = 1}^{N_{imp}} C_{i}} |,$ (9)where p_j is the normalized power of the j-th imperialist, $C_{j} = | c_{j} - max_{1 \leq i \leq N_{imp}} {c_{i}} |$ is the normalized cost of the j-th imperialist for j = 1, 2, ⋯ , N_imp, c_i is the cost of the i-th imperialist for i = 1, 2, ⋯ , N_imp.

2. Generate the initial number of the colonies belonging to each empire based on the following formula $N . C ._{j} = round {p_{j} \cdot N_{col}},$ (10)where N . C . _j is the number of initial colonies belonging to the j-th empire, and N_col is the total number of all initial colonies.

3. Random select N . C . _j colonies and distribute them to the j-th imperialist. These colonies along with the imperialist together form the j-th empire (denotes in empire (j), j = 1, 2, ⋯ , N_imp). Fig. 1 shows the initial counties of each empire in $ℝ^{2}$ .

3.2 Improvement of colonies moving toward their relevant imperialist

In Ref. [11], the authors make each colony to move toward the imperialist by x-units in the direction which is the vector from colony to imperialist. x will be a random variable with uniform distribution, i.e., $x \sim U (0, β \times d),$ (11)where β > 1 and d is the distance between the colony and imperialist, parameter β causes the colony to get closer to the imperialist from both sides, this movement is shown in Fig. 2.

Based on this method, it’s difficult to search the different points around the imperialist, that’s to say, the diversity of evolution colony will not be improvement. In order to overcome this default, we make an improvement to the method based on adding a random amount of deviation to the direction of movement like angle A and step length r in Fig. 3, where A and r are two random numbers with uniform distribution or other proper distributions. i.e.,

$A \sim U (- π, π)$ (12)

and $r \sim U (0, d \cdot cos A),$ (13)where d is the circle’s radius generated by joining the colony and imperialist, and the imperialist is the center of a circle, the new position of colony is shown in a blue-black colour. Parameter r and A can cause the colonies to get closer to the imperialist from its neighbourhood rather than far away from theimperialist.

3.3 Exchanging positions of the imperialist and a colony

While moving a colony to the imperialist and getting new position, the imperialist may has lower cost than that the colony does, in such a case, we use the colony to replace the imperialist and vise versa. Then the algorithm will continue to run by the imperialist in a new position and the colony starts to move toword this position. The detailed narration can be seenin [11].

3.4 Imperialistic competition

For ICA, all the empires try to possess the colonies of the other empires and control them. As a result, the power of the weaker empires gradually begins to decrease and an increase of the power of the powerful empires. this process can be described in the follows [11]:

1. Compute the total power T . C . _j of the j-th empire depending on its own all colonies as follows: $T . C ._{j} = F (imp .^{*}, t) + \frac{σ}{N . C ._{j}} \sum_{i = 1}^{N . C ._{j}} F (colony (i), t),$ (14)where σ < 1 is a positive coefficient, and imp. * is the imperialist of the j-th empire, N . C . _j is the number of colonies of the j-th empire.

2. Use the formula (14) to compute the possession probability E . P . _j of each empire (j) for j = 1, 2, ⋯ , N_imp, i.e., $E . P ._{j} = | \frac{N . T . C ._{j}}{\sum_{i = 1}^{N_{imp}} N . T . C ._{i}} |,$ (15)where $N . T . C ._{j} = | T . C ._{j} - max_{1 \leq i \leq N_{imp}} {T . C ._{i}} |$ is the normalized total power and the T . C . _j is the total power of the j-th empire, respectively.

3. Random select some colonies, mostly often, we select only one, and denote it in $\bar{colony}$ . For all of these selected colonies, we divide them into each of empires based on the possession probability of each empire. Let $Θ = (E . P ._{1}, E . P ._{2}, \dots, E . P ._{N_{imp}}),$ (16)and also generate another vector r with uniformly distributed elements, i.e., $r = (r_{1}, r_{2}, \dots, r_{N_{imp}}),$ (17)where r_i ∼ rand (0, 1) for i = 1, 2, ⋯ , N_imp. Furthermore, let $D = (\begin{matrix} D_{1} \\ D_{2} \\ ⋮ \\ D_{N_{imp}} \end{matrix}) = (\begin{matrix} E . P ._{1} - r_{1} \\ E . P ._{2} - r_{2} \\ ⋮ \\ E . P ._{N_{imp}} - r_{N_{imp}} \end{matrix}),$ (18)then, we can divide the selected colony $\bar{colony}$ into the j-th empires, where index j subject to $| E . P ._{j} - r_{j} | = max_{1 \leq i \leq N_{imp}} | E . P ._{i} - r_{i} | .$ (19)

3.5 The eliminated empire

Powerless empires will collapse in the imperialist competitive, and the number of their colonies become less and less. When an empire loses all of its colonies, we consider that the empire has been collapse and the imperialist of it become one of the restcolonies.

3.6 Stop condition at fixed moment

At the fixed moment t, all the empires except the most powerful empire will collapse and all the colonies will be control under this unique empire. So all the colonies will have the same costs as the unique empire has. It means that there is no difference between colonies and their unique empire. In this circumstance, we put an end to the imperialist and output the optimalsolution.

4 The flowchart of the proposed algorithm

Based on aforementioned discussion, the imperialist competitive algorithm to solve the dynamic non-linear constrained optimization, denotes in NICA, can be described as follows:

Step 1. Randomly generate some moments in [a, b]. Suppose that different moments t = t₁, t₂, ⋯ , t_s are obtained and let t = t₁.

Step 2. At fixed moment t_i, generate N_pop initial country (j) (j = 1, 2, ⋯ , N_pop) based on the method of orthogonal design [15] in the search space [L′, U′].

Step 3. Select N_imp powerful countries based on their power and divide the rest countries to each of these powerful countries, and form initial country (1) , country (2) , ⋯ , country (N_imp).

Step 4. Make each colony moving toward the imperialist based on the method of improvement of colonies moving toward their relevant imperialist in subsection 3.2, exchange the position of an imperialist and its best colony in the empires.

Step 5. Carry out imperialistic competition and eliminate the weaker empires.

Step 6. If the stop condition mentioned in sub-section 3.6 and i < s met, let t_i = t_i+1, go to Step 2; Otherwise, go to Step 4; If i = s - 1, stop, output the optimal solutions of problem (1) in different moments.

5 Indicators of performance

Over the years, researchers have developed a number of different performance measures to evaluate the developed intelligence optimization approaches for dynamic optimization problems. Mostly often, the used performance measures can be classified into two main groups: optimality-based and behaviour-based. In this paper, we use two metrics proposed in [16] as the performance measure methods to measure the proposed algorithms. The first metric named as accuracy (denotes in Acc (A) and shows as the formula (20)) is used to measure the difference between the value of the current best individual or empire in the evolution country of just before change generation, and the optimum value averaged over the entire environment, i.e., Acc (A) can be used to evaluate the capacity of the algorithm A to track the whole optimal solutions in dynamic environment. $Acc (A) = \frac{1}{T_{max}} \sum_{i = 1}^{T_{max}} | {opt}_{t_{i}}^{*} - {opt}_{t_{i}}^{min} |,$ (20)where T_max is the maximum number of the changing environment. ${opt}_{t_{i}}^{*}$ is the really optimal solution of the problem in environment t_i, and ${opt}_{t_{i}}^{min}$ is the optimal country or the empire found by the algorithm A in environment t_i.

The second metric known as adaptability (denotes in Ada (A) and shows as the formula (21)) is used to measure the difference between the value of the current best individual or empire of each generation (or after each imperialistic competition) and the optimum value averaged over the entire environment, i.e., $Ada (A) = \frac{1}{T_{max}} \sum_{i = 1}^{T_{max}} (\frac{1}{K_{t_{i}}} \sum_{j = 1}^{K_{t_{i}}} | {opt}_{t_{i}}^{*} - {opt}_{t_{i} \cdot j}^{min} |),$ (21)where T_max is the maximum number of the changing environment, ${opt}_{t_{i}}^{*}$ is the really optimal solution of problem in environment t_i. K_{t
_i} is the number of maximum evolution generation in environment t_i, and ${opt}_{t_{i} \cdot j}^{min}$ is the quasi-optimal solution found by the algorithm A at thej-th generation in the environment t_i, the value of Ada (A) can measure the speed of the algorithm recovery from the changing environment.

Obviously, the smaller measured values for Acc (A) and Ada (A), the better results of the algorithm A do. If the value Acc (A) reaches to zero, it means that the algorithm can find the optimal solution of problem every time before an environment change occurs; If the value of Ada (A) is equal to zero, it means that the best individual in the evolution population at fixed environment was the optimum for all generation, i.e., the optimum was never lost by the algorithm.

6 Simulation results

In order to demonstrate the effectiveness of the proposed algorithm NICA, four dynamic nonlinear constrained optimization problems chosen by the authors from the existing studies were tested by three dynamic optimization evolutionary algorithms: DCGA in [9], DAGA in [13], and NICA. The first and the second problems, denote in DNCP1 and DNCP2 respectively, are borrowed from Ref. [17]. The third and the fourth problems, denote in DNCP3 and DNCP4, are structured by the authors based on the nonlinear constrained test optimization problems in [18] and [19], respectively. The details of these four test functions are described as following.

DNCP1: ${\begin{matrix} min f (x, t) = (1 - \frac{t}{100}) \sum_{i = 1}^{n} x_{i}^{2} + \frac{t}{100} \sum_{i = 1}^{n} (x_{i} - 2)^{2}, \\ s . t . - 2 \leq x_{1}, x_{2} \leq 2; 0 \leq t \leq 100; n = 2 . \end{matrix}$

DNCP2: ${\begin{matrix} min f (x, t) = (1 - \frac{t^{2}}{10000}) \sum_{i = 1}^{n} x_{i}^{2} + \frac{t^{2}}{10000} \sum_{i = 1}^{n} (x_{i} - 2)^{2}, \\ s . t . - 2 \leq x_{1}, x_{2} \leq 2; 0 \leq t \leq 100; n = 2 . \end{matrix}$

DNCP3: ${\begin{matrix} min f (x, t) = t (x_{1} - 10)^{2} + (1 - t) (x_{2} - 2)^{2}, \\ s . t . (1 - 0.2 t) (x_{1} - 5)^{2} + 0.2 t (x_{2} - 5)^{2} - 100 \geq 0; \\ 2 t (x_{1} - 6)^{2} + (1 - 0.2 t) (x_{2} - 5)^{2} - 82.81 \leq 0; \\ 13 \leq x_{1} \leq 100; 0 \leq x_{2} \leq 100; t \in [0, 1] . \end{matrix}$

DNCP4: ${\begin{matrix} min f (x, t) = t (x_{1}^{2} + x_{2} - 1)^{2} + (1 - t) (x_{1} + x_{2}^{2} - 7)^{2}, \\ s . t . 4.84 - (1 - 0.1 t) x_{1}^{2} - 0.1 t (x_{2} - 2.5)^{2} \geq 0; \\ 0.1 t (x_{1} - 0.05)^{2} + (1 - 0.1 t) (x_{2} - 2.5)^{2} - 4.48 \geq 0; \\ 0 \leq x_{1} \leq 6; 0 \leq x_{2} \leq 6; t \in [0, 1] . \end{matrix}$

Each algorithm was implemented by using MAT-LAB 7.0 on an Intel Pentium IV 2.8-GHz personal computer, and was executed 30 times on each test problem. In the simulation, the initial country size N_pop = 500, the number of the powerful countries N_imp = 20, the maximum generation number of imperialistic competition is 100 in each fixed moment t_i, the position coefficients σ = 0.7 in the formula (14). Moreover, we execute three algorithms, DCGA, DAGA, and NICA, on each of four problems in different moments. In the simulation, we divide the time period [0,100] of problems DNCP1 and DNCP2 into ten different subperiods and obtain different moments t = 0.00, 10.0, 20.0, 30.0, 40.0, 50.0, 60.0, 70.0, 80.0, 90.0 in each subperiod. For DNCP3 and DNCP4, we divide the time period [0,1] into eight different subperiods, also and obtain eight moments t = 0.00, 0.15, 0.35, 0.50, 0.65, 0.75, 0.75, 0.95, respectively.

To compare the performance of these compared algorithms, we record the best results (denote in B.R.), the mean (denote in M.R.) and the worst results (denote in W.R.) obtained by DCGA, DAGA, and NICA on four test problems in different moments, and show these results from Tables 1 to 4. Moreover, we use two performance metrics Acc (A), and Ada (A) to evaluate the performance of these algorithms.

Apparently, it can be seen from Tables 1 to 4 that the best results, the mean and the worst results obtained by NICA are smaller than the other two compared algorithms do in different changing environments.

In Figs. 4 and 5, the boxplots show the statistic results of the Acc obtained by algorithms DCGA, DAGA and NICA for DNCP1 and DNCP2 in ten moments, In Figs. 6 and 7, the Ada values obtained by three algorithms for test problem DNCP1 and DNCP2, respectively. We can see from Figs. 4 to 7, the proposed algorithm NICA obtained the best accuracy and adaptability in different changing environments than the other compared algorithms.

Also, Figs. 8 and 9 depict the box plots of Acc values obtained by three algorithms in eight moments for DNCP3 and DNCP4, Figs. 10 and 11 describe the Ada values obtained by three algorithms in eight moments for DNCP3 and DNCP4, respectively. From Figs. 8 to 11, we can observe that our algorithm NICA obtained very lower value of accuracy and adaptability that the other compared algorithms when the environments have been changed. These results illustrate that the proposed algorithm NICA had faster adaptation to the new optimum value when every time change was observed, i.e., the proposed algorithm NICA is more effective for dynamic nonlinear constrained optimization problem than the compared algorithm do.

7 Conclusion

This paper introduce a new imperialist competitive algorithm for solving dynamic nonlinear constrained optimization problem. The simulation results show that the proposed algorithm can track and recover from the change of environment. Also, the proposed algorithm can obtain the optimal solutions of the dynamic nonlinear constrained optimization problem in different environments.

The research on dynamic nonlinear constrained optimization problem is still in its very infancy and our work presented in this paper is also rather preliminary. Much work remains to be done, e.g., how to efficiently detect environmental changes, how to set up more effective optimization models or the high-efficiency evolutionary algorithms by taking the problem’s constrained conditions into account, how to compare the performance of the compared algorithm in more fair and reasonable way, etc., are still needs to be further studied.

Footnotes

Acknowledgments

This work is partially supported by the National Scholarship Fund in China, the Project Sponsored by the Scientific Research Foundation for the Returned Overseas Chinese Scholars, State Education Ministry. The Emphasis Research Plan Project of Baoji University of Arts and Sciences in China (No. ZK12044). The author will also gratefully acknowledge the anonymous reviewer.

References

Jin

Y.C.

and Branke

, Evolutionary optimization in uncertain environments-A survey, IEEE Transactions on Evolutionary Computation 9(3) (2005), 134–137.

Ronnewinkel

, Wilke

C.O.

and Martinetz

, Genetic algorithms in time-dependent environments, Proc of the Theoretical Aspects of Evolutionary Computing, Berlin, Germany, 2000, pp. 263–288.

Yang

Shengxiang

and Yao

, Evolutionary computation for dynamic optimization problems, Springer Heidelberg, London, UK, 2013.

Liu

C.A.

and Wang

Y.P.

, A new dynamic multiobjective optimization evolutionary algorithm, Journal of Innovative Computing, Information and Control 4(8) (2008), 2087–2096.

Farina

, Deb

and Amato

, Dynamic multiobjective optimization problems: Test cases, approximations, and applications, IEEE Transactions on Evolutionary Computation 8(5) (2004), 425–442.

Araujo

and Merelo

J.J.

, A genetic algorithm for dynamic modelling and prediction of activity in document streams, Proc 9-th Annual Conf Genetic and Evol Comput (2007), 1896–1903.

Mertens

, Holvoet

and Berbers

, The DYNCOAA algorithm for dynamic constraint optimization problems, Proc 5th Int Joint Conf Autonomous Agents and Multi-agent Syst, 2006, pp. 1421–1423.

Moser and Hendtlass

, A simple and efficient multi-component algorithm for solving dynamic function optimisation problems, In: Proc 2007 IEEE Conf Evol Comput, 2007, pp. 252–259.

Chen

Y.X.

and Benjamin

W.W.

, Calculus of variations in discrete space for constrained nonlinear dynamic optimization, Proceedings of the 14-th International Conference on Tools with Artificial Intelligence (ICTAI’02), Piscatway, IEEE Press, 2002, pp. 1–8.

10.

Blankwell

and Brank

, Multi-swarm optimization in dynamic environments, In Proceedings of Applications of Evolutionary Computing, Volume 3005 of Lecture Notes in Computer Science, Coimbra, Portugal, Springer-Verlag, 2004, pp. 489–500.

11.

Atashpaz-Gargari

and Lucas

, Imperialist competitive algorithm: An algorithm for optimization inspired by imper-ialistic competition, In: IEEE Congress on Evolutionary Com-putation, 2007, pp. 4661–4667.

12.

Nazari-Shirkouhi

, Eivazy

, Ghodsi

, Rezaie

and Atashpaz-Gargari

, Solving the integrated product mix-outsouring problem using the imperialist competitive algori-thm, Expert Syst Appl 2010(37) 7615–7626.

13.

Bahrami

, Faez

and Abdechiri

, Imperialistic competitive algorithm using chaos theory for optimization, In 12-th International Conference on Computer Modeling and Stimulation, 2010, pp. 788–792.

14.

Mohammadi , Tavakkoli-Moghaddam and Rostamib

, A multi-objective imperialist competitive algorithm for a capacitated hub covering location problem, International Journal of Industrial Engineering Computations (2011), 671–688.

15.

Yiu-Wing Leung

and Wang

, An orthogonal genetic algorithm with quantization for global numerical optimization, IEEE Transactions on Evolutionary Computation 5(1) (2001), 41–53.

16.

Simoes

Anabela

and Costa

Ernesto

, A comparative study using genetic algorithms to deal with dynamic environments, In Proceedings of the Sixth International Conference on Neural Networks and Genetic Algorithms (ICANNGA’03), Pearson

David W.

, Steele

Nigel C.

and Albrecht

Rudolf

, Eds., Springer, France, 2003, pp. 203–209.

17.

Jin

and Bernhard

, Constructing dynamic optimization test problems using the multiobjective optimization concept, In Proc Evo Workshops 2004, LNCS3005, Raidl

et al., Eds. Berlin, Germany, Springer-Verlag, 2004, pp. 525–536.

18.

Carlos

and Coello

Coello

, Treating constrains as objective for single-objective evolutionary optimization, Engineering Optimization 32(2) (2000), 275–308.

19.

Liu

H.L.

and Wang

Y.P.

, Solving constrained optimization problem by a specific-design multiobjective genetic algorithm, In Proceedings of the 5th Conference on Computational Intelligence and Multimedia Applications (ICCIMA’03), Springer Verlag, New York, 2003, pp. 2236–2239.