Node ordinal encoded genetic algorithm for the optimal allocation of water resources

PROGRESS IN NATURAL SCIENCEVol. 15, No. 5, May 2005Node ordinal encoded genetic algorithm for the optimalallocation of water resourcesYANG Xiaohua' **，YANG Zhifeng12, SHEN Zhenyao' and LI Jianqiang(1. State Key Laboratory of Water Environment Simulation, School of Environment, Beijing Normal University, Beiing 100875, China;2. Key Laboratory for Water and Sediment Sciences Ministry of Education, School of Environment, Beijing Normal University, Bejing100875，China; 3. Water Resources and Hydropower Planning and Design General Institute, MWR, Beijing 100011, China)Received August 23, 2004; revised October 12，2004AbstractA new method, node ordinal encoded genetic algorithm (NOEGA), is proposed for solving water resources optimal allo-cation problems, in which the capacity of water resources is split into a number of smaller parts so that successive operations can be over-lapped. Our objective is to maximize the whole benefit function. To overoome the“dimensionality and algorithm complexity curse”whilesearching for solutions and looking for an optimal solution, the operations of one-point crossover operator, gene exchange operator, generandom operator, gene shift operator and node ordinal strings are established. It is proved to be an efective optimal method in searchingfor global solutions. The NOEGA does not need a diversity of initial population, and it does not have the problem of immature conver-gence. The results of two cases show that using NOEGA to solve the optimal allocation model is very efficient and robust. In addition, thealgorithm complexity of NOEGA is discussed.Keywords: water resources, optimal allocation, node ordinal code, genetic algorithm.The shortage of water supply and the increasingwhen problems changed, such as the crossover opera-demand for water resources is a severe problem， andtors of partially matched crossover( PMX )，orderedthe optimal allocation is the key to solving this prob-crossover( OX )and cycle crossover(CX)for TSPL19 -21]lem in management of water resources. It is very dif-and the mutation operators of partheno-genetic algo-ficult to solve the large scale discrete problem of waterrithm( PGA)-22 24] for Flow Shop. Because water re-resources programming because of the intricate rela-sources optimal allocation is different from the prob-tion between resources and environment. ( ombina-lems of TSP and Flow- Shop, GA needs to be imion exploding exists in traditional programmingproved. Based on the consideration above, a node or-methods, such as enumerative and dynamic program-dinal encoded genetic algorithm ( NOEGA) is pro-ming methods. People are not satisfied with tradi-posed here with a special one-crossover operator andtional optimum algorithms， so genetic algorithmsnode ordinal strings for general water resources opti-(GA) are put forward1- -5].nal allocation， its complexity is analyzed and its ef-GA is a search method based on the principles offectiveness is verified by analysis of two cases.Darwinian natural selection and survival of the fittest.1 Model frameIt provides robust procedures to explore broad andpromising regions of solutions， and to avoid beingSupposing that the capacity of water resources istrapped at the local optimum. Since 1975， GA hasC in a reservoir for n users, x; is the capacity of wa-been applied to a variety of fields-6- 121. Several re-ter resources to the ith user, and g:(x;) is the bene-searchers have studied the applications of GA to waterfit function corresponding to ithresources management problems13- 18. However,n. Then the basic mathematical model for water re-few studies have been done on the dispersing andsour(中国煤化工. tablished by solvinglarge scale water resources optimal allocation withGA.TYHCNMHG;(x),(1)GA is especially adapt to the combinatorial opti-subject tojx;≤C，x;≥0,mization, but its genetic operator is very different* Spprey号ial Natural Science Foundation of Chira (Grant No. 50239020)￥* To whont商婉dence should be adressed. E mail: zfyang@ bnu. edu. cnProgress in Natural Science Vol. 15 No.5 2005 www. tandf. co. uk/ jourmals449(i = 1,2...n)，(2)Substituting xj= x(c;) into Eq.(1) produceswhere f is a whole benefit objective function.the objective function f(i):2 NOEGA descriptionf(i)= Zg;(x)，i = 12,..,m.Genetic algorithms using ordinal strings must useThen，{f(i)|i= 1,2,., m } are arranged fromspecial crossover operators such as PMX，OX andbig to small. The bigger the value of f(i) is， theCX，instead of general crossover operators, but it ishigher the fitness of its corresponding ith chromo-very difficult to use the above crossover operators forsome is. So the fitness of the ith chromosome is de-water resources optimal allocation. To solve thisfined as F(i)= f(i)，where F is a fitness function.problem, we propose a node ordinal encoded geneticalgorithm ( NOEGA) with the one- point crossover ge-Step 3. Creating complementary chromosomesnetic operator and node ordinal strings. NOEGAIn the water resources optimal allocation, if wesearches for the optimal parameter values on water re-randomly crossover two chromosomes, restrict condi-sources optimal allocation so that the whole benefittion (2) cannot always be satisfied. Therefore， wefunction is optimized, and its detailed procedure in-set up a special complementary chromosome c; forcludes six steps.father chromosome Cij by the following operation.Step 1. EncodingFor each fixed i, we get the ith complementaryIn the water resources optimal allocation, the ca-chromosome ci), j= 1,2,.，n;(i= 1,2,.，m )pacity C of water resources is divided into s parts de-through inverting the ith chromosome, e. g.noted by the ordinal node 1,2,.,s, and the table ofwater resources benefit must be established ( Tablefather chromosome is: 1 25436 78,1 ). Here the number k∈{1,2,.,s}， c;=k,and the complementary chromosome is: 8 7 6 3xj= x(cj)，where x; refers to the water resources4521.capacity of the jth user. Then the node cj， as agene, forms a chromosome ( character string )，Step 4. Crossoverj= 1,2,..n. One chromosome denotes one kind ofAs the probability of crossover pe controls thedistribution.For example,the chromosomesfrequency of using crossover operator, the higher thec1，c2".',Cn correspond to the node number of pa-pe is, the faster the chromosome renewing is, and therameterrespectively,wherebigger the searching new area’ s chance is. So， wex;= x(c;). Namely, each parameter工j is expressedwill choose p。= 1.0. Because it is easier to design aby an ordinal node C;，j= 1,2,.,n.one-point crossover operator than to design a multi-point crossover operator, we will choose the one- pointStep 2. Initial father population and fitness evo-crossover operator. The operation is as follows: .lutionInitially, the chromosomes are generated at ran-For each fixed i, if we randomly selectdom within node- encoded GA，and m chromosomesU∈(0,1), let U;=INT(U1 s+ 1)，we will getin population are gotten as follows:U,∈[1,s]. Exchanging the front U, genes in cjFor each fixed i，we get qj= INT(rg;s+ 1)，and the end U: genes in cj，we will get a pair ofuntil xi= ax(Cjj) satisfies restrict condition (2 ).chromosomes ci) and c?)，j=1,2,*,n; i=1,2,Here rij is uniformity random number, r;∈(0, 1),.,m. For example, if U,=3，thenj=1,2.,"',n，i= 1,2,，.，m; INT() is an integerfunction. Then we get the m X n matrix A:中国煤化工2543678,C11C12“C1nDTH. CNMH Gomoome is: 8763C21c 2nA=452 1.Lcml Cm2Cmn_We will get ci，c，j=1,2,,n，e.g.A is called an initial father population matrix. Everyrow of A tept格描ts a chromosome.52143678;87634125.450www. tandf. co. uk/ journals Progress in Natural Science Vol. 15 No. 52005Step 5. Mutationfirst location by a certain probability ps. Here ran-Before mutating, the chromosomes in the initial fa-dom numbers j1 and j2 are between 1 and n. And .ther population are selected by a known probability ps.then, offspring cj is gotten, where j= 1,2,.,n;p。(i) = F(i)/2F(j)，i = 1,2...m,i=1,2,,m.where F is the function of fitness. Let z(i) =For example, let j1=3，j2=7 and father chro-mosome be: 1 254 36 78, wewillgetc;s), j=1,2 s p。(k), the interval [0,1] is divided into m sub-2,,n，as follows: .intervals [0,z(1)],[z(1),z(2)],.,[x(m- 1), .offspringc;): 1 2754 368.z(m)]by {e(i)|i= 1,2,.,m }. Those sub- inter-vals correspond to m father chromosomes respective-By all appearances, the matched population andly. The longer the sub-interval is， the bigger theoffspring gotten by steps 3- 5 satisfy the restrict con-probability of the chromosome dropping into the sub-dition (2). In order to improve global optimizing a-interval is. Let m random numbers U(i)∈[0, 1]bility，we copy the most ecellent chromosome in fa-(i= 1,2,..,m)， and U(i)∈(z(i- 1),z(i)],ther population directly into the above offspring. Weand then the ith father chromosome is selected. Thecall that“most excellent saving”operation.bigger the value of chromosome' s fitness F is， theStep 6. Evolution cyclebigger the probability of its being selected is. Muta-The matched population and offspring gotten bytion operators in this paper include gene exchange op-erator, gene random operator and gene shift operator.steps3- 5 are all arranged from big to small by fit-ness, in which the m bigger fitness of chromosomes(i) Gene exchange operatorare put into the next generation，and then the wholeGene exchange operator of NOEGA is the proce-process starts again. NOEGA is over until the objec-dure in which two genes ( characters)，i1 and i2，in ative function value of the most excellent chromosomefather chromosome ( character string) are exchangedis greater than or equal to a fixed value, or algorithm-by a known probability ps，and then the exchangedrunning time gets to the design time. Here, the mosttwo genes become i2 and i. Here random numbersexcellent chromosome currently is regarded as the op-in and i2 are between 1 and n. And offspring c;timum solution of NOEGA.gotten，where j= 1,2,."，n; i=1,2,，m.NOEGA starts with a randomly generated popu-For example, let i1=3, i2= 5 and father chro-lation of m candidate solutions. At each step, or gen-mosome be: 1 254 367 8,eration，all the individuals are evaluated and assigneda number, which is called fitness. It is a measure ofwe will get cj，j= 1,2,..n，as follows:how good a solution is. NC )EGA reproduces the solu-tion in two ways: (1) by crossover, where you takeoffspringci)': 1 2345678.one part of one individual and some parts of anotherindividual and combine them; (2) by mutation，parts(i) Gene random operatorFor the ith father chromosome，the smaller theof one individual will randomly be changed. Becausefitness F(i) is, the smaller the selected probabilityNOEGA saves the most excellent chromosome in eachis，and the bigger the mutation probability pm(i)= 1evolution procedure, it will converge on a global opti-mum solution by breeding better and better solutions- p,(i) is. So, we can get offspring cij using thefrom the most promising parents in each generation ofmethod of step 2 by a certain probability pm(i), j=trials.1,2,.,n; i=1,2,,m.3中国煤化工alysis(ii) Gene shift operatorGene shift operation of N DEGA is a procedure inMHCNMHGntoPandNPkindsac-which two genes ( characters)，j1 and j2，are ran-cording to its complexity degree. If an algorithmdomly selected and they compose one sub-string in acomplexity degree rises with problem size in the man-father chromosome ( character string ). The sub-ner of polynomial (or exponent) formula, we call it Pstring in a chromosome is backward in turn; the pro-(or NP) algorithm. Here we analyze NOEGA' s com-cedure sh{5欲Aast gene in this sub-string to theplexity.Progress in Natural Science Vol. 15 No.5 2005 www. tandf. co. uk/ jourmals451According to steps 1- 6 in NOEGA，forming aFrom Table 2，we may see that after 4 evolutionchromosome needs to select n numbers from s ordinaltimes, we get 2 different optimum chromosomes 1 2nodes. Considering m chromosomes, NOEGA needs222122and22222112.Thechromosome12O ( msn ) operations. In addition， considering the22 2 1 2 2 corresponds to the optimum variable statematching operator, crossover operator，exchange Op-of using ordinal nodes 1，2，2，2，2，1，2，2 forerator, random operator and shift operator, NOEGA1st- 8th users, respectively. Namely the water quan-needs O ( 6msn ) operations. If evolution is repeatedtities used are0, 100， 100, 100， 100, 0，100， 100q times, NOEGA needs O ( 6msnq) operations. So(X 104 m3) respectively. Similarly the chromosome 2the complexity degree of this new algorithm is22 2 2 1 1 2 corresponds to the optimum variableO (6msnq). But the complexity degree is 0(s") instate of using ordinal nodes 2，2, 2，2，2，1，1，2enumerative algorithm. And “combination exploding'for 1st- -8th users， respectively， and their waterproblem also exists in dynamic programming. There-quantities used are 100，100， 100, 100, 100, 0, 0，fore, the efficiency of NOEGA is better than that of100( X104 m3 ), respectively. We get optimum bene-enumerative method and dynamic programming infit max f= 21.50x 104 Chinese RMB for the abovetheory.two cases. The NOEGA of the above problem is glob-al convergence after only 4 evolution times. The algo-4 Case studyrithm running time is less than 1s. The results of thecase show that using NOEGA to solve the optimal al-Case 1. Suppose that the capacity of water re-location model is very efficient.sources is C= 600x 10* m' in a reservoir, and C pro-vides 8 users-21. Here C=600， n=8， s=7 andCase 2. Shaoxing Water Factory in Zhejiangm= 20，in NOEGA. Relation between the waterProvince provided three users with 800X 104 tons ofquantity of each user and its corresponding benefit iswater-261 at the end of 2000. Here we set C= 800，given in Table 1. Five excellent chromosomes andn=3，s=9，m=20，in NOEGA. The relation be-their corresponding benefits in the first and fourthtween the water quantity used by each user and theevolution procedures are given in Table 2.benefit produced is given in Table 3. Five excellentchromosomes and their corresponding benefits areTable 1. Quantities of water used by each user and the benefit pro-given in Table 4.duced (unit: X 104 yuan RMB)User'sg;(x) of water quantityx;(k) and is node state k(x 10*mP)Table3. Quantties of water used by each user and the benefit pro-number0 100 200 300400500 600duced (unit: X 10* yuan RMB)(k=1)_ (k=2) (k=3) (k=4) (k=5) (k=6) (k=7) _g;( x) of water quantity x;(k) and its node statek (x104 T)0.0 3.05.57.59.010.010.0 .User' s6.0 8.09.510.5) 100 200 300 400 500 600 700 800(k=1)(k=2)(k=3)(k=4)(k=5)(k=6)(k=7)(k=8)(k=9)0.04.06.58. 59.0 9.001(30160 180 190195 2000.0 3. 56.0 7.58.5 9.021080 120 130 140145 1500.0 4.06.0 7.08.03090100，1051081106.5.00.03.05.07.08.58.5Table 4. Five excellent chromosomes and the benefits produced calcu-6.5 6.57.08.0lated with NOEGATable 2. Five excellent chromosomes and their corresponding beneftsEvolutionChromasomesBenefitin the first and fourth evolution procedures by NOEGAtimesyuan RMB(X 10+)Chromosomes1280yuan RMBC1C2C3C4csC6c7C(X104)19. 5019.00中国煤化工sce that afer the first19.00 .evoll.MYHCNMHGmchromosome55121.50which respectively represents the optimal variable21. 50state of using ordinal nodes for the first to thirdusers, and the water quantities they used are 400 X10*，400X 10*, 0 tons respectively. Therefore we get方數据22!optimum benefit max f= 280x 104 . yuan RMB by