Printer Friendly

An improved continuous ant colony algorithms for water-reusing network optimization.

Abstract In this paper, an improved ant colony algorithm is proposed for solving continuous optimization problems. The proposed algorithm is applied to optimize the water-reusing network, which is modeled as a high-dimensional nonlinear constrained optimization problem. The experimental results would have provided some pieces of advice in the engineering applications.

Keywords Water-reusing network, ant colony system, continuous optimization.

[section] 1. Introduction

The aim of water system optimization is to consider how to assign the amount and quality of water in each process unit of a whole water system so as to attain the maximum rate of water recycle and attain the minimum amount of the drained waste water at the same time. The problem mentioned above includes bilinear items and integer variables. So the algorithms of solving mixed non-linear integer programming MNLIP should be adopted to find the solution to the problem. In general, it is difficult to solve the MNLIP by the traditional optimization methods. Ant colony optimization algorithms introduced in recent years, however, may find a better solution to the problem in average.

The ant colony optimization techniques are based on the real world phenomena that ants are able to find their way to a food source and back to their nest, using the shortest route. They are a kind of relatively new heuristic and stochastic searching algorithms for solving complicated optimization problems. On the basis of the high-dimensional complexity of the water system, an ant colony algorithm for continuous optimization is improved in updating the pheromone so as to have better performance of optimizing the water-reusing network.

[section] 2. Water-reusing network optimization and its mathematical model

2.1 The description of water-reusing network optimization

Regular water-reusing network is a kind of common water networks, on which great deals of research efforts have focused. The characters of its structure can be stated as follows: in the water system, every process unit provides water for the other process units or receive water output from the other process units directly, that is, the process unit is connected with other process units. Water-reusing network can be described by superstructure model. Any process unit can be fed by fresh water or water output from other process units; meanwhile, its output can be drained off directly or to other process units, but can not go back to itself.

2.2 The mathematical model of the water-reusing network

The mathematical model[2] of optimizing the water-reusing network is set up as follows: Minimize the objective function

min f (x) = [summation over j [element] P [F.sup.W.sub.j], (1)

that is, minimize the freshwater consumption of the system. The constraints are

1. The water balance of process j:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (2)

2. The mass balance of contaminants at the inlet node of process j:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (3)

3. The mass balance of contaminants of process j:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (4)

Denote by x the vector which is composed of all the parameters to be optimized, including [C.sup.In.sub.j]n, [F.sup.D.sub.j], [F.sub.i,j], [F.sup.W.sub.j]. P is a set of natural numbers, whose every element stands for a process unit. By the penalty method, the formulas (1)-(4) can be transformed into an unconstrained optimization problem

min F(x) = f(x) + [p summation over j=1] (r/2) * [(([h.sub.j](x)).sup.2] + [([g.sub.j](x)).sup.2] + [([l.sub.j](x)).sup.2]), (5)

where r is the constant penalty factor.

[section] 3. Ant colony system for continuous optimization

3.1 Basic idea of ant colony system

Ant colony system, introduce by M. Dorigo and A. Colorni, is an intelligent optimization algorithm which is designed to simulate the self- adaptive ability of real ant colonies [3]-[5]. One of the main ideas of ant colony system is the indirect communication of a colony of agents, called ants, based on pheromone trails. The pheromone trails are a kind of distributed numeric information which is modified by the ants to reflect their experience while solving a particular problem.

It has been studied that ants often find the shortest path between a food source and the nest of the colony without using visual cues. In order to exchange information about which path should be followed, ants communicate with each other by means of a chemical substance called pheromone. As ants moving, a certain amount of pheromone is dropped on the ground, creating a pheromone trail. This pheromone trail can be observed by other ants and motivates them to follow the path. The more ants follow a given trail, the more attractive that trail becomes to be followed by other ants. This process involves a loop of positive feedback, in which the probability that an ant chooses a path is proportional to the number of ants that have already passed by that path.

That is the way how the trail is reinforced and more and more ants follow that trail. Meanwhile, the ant colony are capable of adapting the vary of the environment, that is, when there is an obstacle in their moving route, they can also find the best route in which a high levels of pheromone has been deposited over a period of time [6].

Based on converting this idea to a search mechanism, ant colony system can be applied for solving some combinatorial optimization problems such as the job-shop scheduling problem (JSP), quadratic assignment problem (QAP) and traveling salesman problem (TSP) [4]etc. The main idea, taking TSP as an example, is that a set of ants, search in parallel for good solutions to the TSP and cooperate through pheromone-mediated indirect and global communication. Informally, the ant colony system constructs a TSP solution in an iterative way: m ants initially positioned on n cities chosen according to some initialization rule (e.g., randomly).

Each ant generates a complete tour which corresponds to a feasible solution to the TSP by exploiting both information gained from past experience and a stochastic greedy heuristic (the state transition rule). Memory takes the form of pheromone deposited by ants on TSP edges, while heuristic information is simply given by the edge's length; ants prefer to move to cities which are connected by short edges with a high amount of pheromone. While constructing its tour, an ant also modifies the amount of pheromone on the visited edges by applying the local updating rule. Once all ants have terminated their tours, the amount of pheromone on edges is modified again by applying the global updating rule. A fraction of the pheromone evaporates on all edges, and then each ant deposits an amount of pheromone on edges which belong to its tour in proportions to how short its tour was. The process is then iterated.

3.2 The proposed ant colony algorithm for continuous optimization

Ant colony system was first proposed for solving combinatorial optimization problems. However, there are lots of continuous optimization problems required in many applications. Therefore, how to improve and design the novel ant colony algorithms for solving continuous optimization problems becomes a key issue in the study of the ant colony system.

Water-reusing network optimization is a high-dimensional continuous optimization problem. In this paper, an improved ant colony algorithm is proposed, which is based on the discretization of the continuous space. The way of selecting cities and dividing the solution space is mainly adopted as one in [7]; the amount of the pheromone is modified by applying the local updating rule and the global updating rule together, and meanwhile, retaining the best solution at each iteration.

In detail, the pheromone is updated locally by the function values of the routes at the present iteration; while only is the pheromone in the best route which stands for the best solution updated globally so as to avoid reaching the local optimal due to the over-high level of the pheromone in that route.

Suppose that the independent variables are set to be at d decimal place, then every independent variable x can be denoted by d decimal numbers approximately. Based on the assumption, we construct d + 2 layers of cities as follows: there are only one city, labeled as 0, in the first layer and the last layer respectively; from the second layer to the d+1th layer, there include ten cities labeled from 1 to 10 in every layer, and these d layers stand for the decile, the percentiles, ...... , of the variable x from left to right respectively./

Among these cities, only can the ones between the neighbor layers be connected. Denote the pheromone in the route connecting city a in the k - 1th layer and city b in the kth layer by [T.sup.k.sub.ab], the city where ant n stays in the mth step by T(n,m). Let the total number of the ants be [N.sub.0]. Initialize [T.sup.k.sub.ab] as [[tau].sub.0] and T(n, 0) = 0 (n = 1, 2, [N.sub.0]).

We select the routes as follows.

If the city where ant n stays at present is T (n, k -1) = a, then select the city to which the ant will get in the next step by the following formula:

T(n,k) = {arg max {[[tau].sup.k.sub.ab]}, if q < [Q.sub.0]; [S.sub.r], otherwise, (6)

where q is a random number, [Q.sub.0] is a constant in [0,1] to determine the probability of the selection of pseudo-random numbers and Sr denotes the next city to which the ant will get.

First compute the probability of the selection of each city in the next layer according to

p(a,b) = [[tau].sup.k.sub.ab]/[9 summation [x = 0] [[tau].sup.k.sub.ax] (7)

and then determine the next city to be selected with roulette-wheel scheme where p(a, b) denotes the probability of transformation from the present city a to the next city b. When every ant gets to the d + lth layer, all of them are forced to move to the unique city in the last layer. When the ant n passed through all the cities, we first decode the route selected by the ant and compute the value of x(n) by

x(n) = [d + 1 summation over k = 2]T(n,k) x [10.sup.1-k], (8)

and then update the pheromone in this route according to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (9)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] if the ant n passes through the cities (T(n, k - 1), T (n, k)); 0, otherwise (10)

where p [element] (0, 1) is a constant, denoting the increasing rate of the remaining pheromone in the route and Q is a positive constant.

When all their ants finished the tour, we only update the pheromone in the shortest route and retain the best solution in the cycle. We first select the optimal ant, labeled as [n.sub.min] by

[n.sub.min] = arg min{f(x(n))} (11)

and update the pheromone in the route through which the ant nmin passed according to

[[tau].sup.k.sub.ab] = (1 - [alpha])[[tau].sup.k.sub.ab]) + [alpha]f[(x([n.sub.min])).sup.-1] (12)

where a = T ([n.sub.min], k - 1), b = T ([n.sub.min], k), k [element] [2, d + 2] and [alpha] is a constant in (0, 1).

For continuous optimization problems with multi-variables, we construct the cities and decode the independent variables according to the following way: suppose that x is a N-dimensional independent variable and every component is set to be at d decimal place, then we can construct N x d + N + 1 layers of cities, where there are only one city labeled as 0 in the 1st, d + 2th, 2d + 3th, ..., N x d + N + 1th layers respectively, and there are ten cities labeled from 0 to 9 in every rest layer. Thus there are N x d x 10 + N + 1 cities altogether. The layers from the (k -1) x (d + 1) + 2th layer to the k x (d + 1)th layer (k = 1, 2,. .. , N) stand for the kth component of the independent variable and the other layers are auxiliary ones. We calculate x (n) by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (13)

In such a way, the last component of each variable is separated from the first component of the next variable by the auxiliary layer so that the later variable has no effect on the former one.

We state the steps of the above algorithm as follows:

(a) Initialize parameters: set iteration number M, the total number [N.sub.0] of ants, pheromone [[tau].sub.0], parameters p, [Q.sub.0], [alpha], Q, d and the initializing city T(n, 1) = 0 where the ant n stays for all n;

(b) Set the cycle number NC := 1;

(c) Let all the ants be in the initializing city and execute the step (d) and the step (e) to every ant;

(d) Select the next city to which the ant will get according to the formulas (6) and (7);

(e) Update the pheromone locally according to the formulas (8)-(10) after every ant finishes its tour (substitute the formula (8) by (13) for multi-variable continuous functions);

(f) Select the optimal ant and update the pheromone globally according to the formulas (11)-(12);

(g) Determine whether the termination is satisfied. If so, then output; otherwise, set NC := NC + 1, go to step (c) and continue.

[section] 4. Numerical experiments and results

In this section, the proposed ant colony algorithm introduced in the last section is applied to optimize the water-reusing network with three process units (i.e. P = {1, 2, 3}, which is modeled as an 18 dimensional continuous optimization problems mathematically.) Table 1 shows the limiting data of the water system. Taking the parameters as [N.sub.0] = 80, M = 100, [[tau].sub.0] = 0.10, [Q.sub.0] = 0.8, p = 0.01 , [alpha] = 0.80 and Q = 100 respectively. Table 2 shows the best five results and the result by Lingo 8.0.

[FIGURE 1 OMITTED]

Figure 1 shows the value of the objective function varying with the number of the iterations. It is shown that although the values of the objective function oscillate all the time during the iterations, the breadth of the oscillation decreases as the number of iterations increases and approaches to vary within a small stationary range.

[section] 5. Conclusion

In this paper, an improved ant colony algorithm for solving continuous optimization problems has been proposed and applied to solve the water-reusing network optimization, which is a high-dimensional and non-linear constrained optimization problem. The experiment results show the good performance of the algorithm for optimizing the water-reusing network with three process units. The optimal solution gotten by the proposed algorithm can provide some pieces of advice in the engineering applications. Nevertheless, it is difficult to determine the values of the parameters because there exist too many random numbers during the iterations. Therefore there need a lot of experiments to get the better value of the parameters.

NOMENCLATURE

[F.sup.w.sub.j] Flow rate from fresh water pipeline to process j, t/h;

[F.sub.j,i] Flow rate from process j to process i, t/h;

[F.sup.D.sub.j] Flow rate from process j to wastewater pipeline, t/h;

[C.sup,.In.sub.j] Inlet concentration of contaminant of process j, ppm;

[C.sup.Out.sub.j] Outlet concentration of contaminant s of process j, g/h;

[M.sub.j] Mass load of contaminant s of process j, g/h;

[C.sup.In,Max.sub.j] Limiting inlet concentration of contaminant s of process j, ppm;

[C.sup.Out, Max.sub.j] Limiting outlet concentration of contaminant s of process j, ppm.

References

(1) The research was supported by the National Nature Science Foundation of China (No. 60703117) and the Special Research Project of the Educational Bureau of Shaanxi Province (No. 07JK408)

References

[1] Duan Haibin, The principle and application of the ant colony algorithms, Beijing, Academic Press, 2005.

[2] Zheng Xuesong, The construction and optimization of the mathematical model of water network with different structures, Xian, Xian Jiaotong University Press, 2005.

[3] Dorigo M., Maniezzo V., Colony A. Ant System, Optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and cybernetics-Part B, 26(1996), No.1, 29-41.

[4] Dorigo M., Gambardella L. M., Ant colony system, A Cooperative learning approach to the traveling salesman problem, IEEE Transactions on Evolutionary Computation, 1(1997), No.1, 53-66.

[5] Dorigo M., Caro G. D., Gambardella L. M., Ant algorithms for discrete optimization, Artificial Life, 5(1999), No.2, 137-172.

[6] Xu Zongben, Intelligence computation-simulated evolutionary computation, Beijing, High Education Press, 2004.

[7] Chen Ye, Ant colony system for continuous function optimization, Journal of Sichuan University (Engineering Science Edition), 36(2004), No.6, 117-120.

Rui Zhang, Xiaorong Liu and Huichuan Cao

Department of Mathematics, Northwest University, 710069, China
Table 1 The limiting data of the water system[2]

Process unit Limiting inlet Limiting outlet Mass load of
 number concentration of concentration of contaminant
 contaminant(ppm) contaminant(ppm) (g=s)

1 50 100 3000
2 25 90 2880
3 25 200 4000

Table 2 Results comparison

 Result 1 Result 2 Result 3 Result 4 Result 5

Flow rate of
fresh water 74.4796 76.3611 79.7994 78.2772 76.1979
[F.sup.w] (t=h)

 Lingo

Flow rate of
fresh water 75.94
[F.sup.w] (t=h)
COPYRIGHT 2008 American Research Press
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2008 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Zhang, Rui; Liu, Xiaorong; Cao, Huichuan
Publication:Scientia Magna
Geographic Code:1USA
Date:Jan 1, 2008
Words:2935
Previous Article:An inequality of the Smarandache function.
Next Article:A concise way of determination for LP initial feasible basis of simplex method.
Topics:

Terms of use | Copyright © 2017 Farlex, Inc. | Feedback | For webmasters