J. agric. Engng Res. (2001) 80(1), 109}124 doi:10.1006/jaer.2001.0723,available online at http://www.idealibrary.comon SW*Soil and Water Application of the Simulated Annealing Method to Agricultural Water Resource Management Sheng-Feng Kuo1; Chen-Wuing Liu2; Gary P. Merkley3 1DepartmentofCivilEngineering,NationalIlanInstituteTechnology,Taipei,Taiwan114,ROC;e-mail:[email protected] 2DepartmentofAgriculturalEngineering,NationalTaiwanUniversity,Taipei,Taiwan106,ROC;e-mailofcorrespondingauthor: [email protected] 3DepartmentofBiologicalandIrrigationEngineering,UtahStateUniversity,Logan,UT84341,USA;e-mail:[email protected] (Received5April2000;acceptedinrevisedform16March2001;publishedonline17July2001) Thisworkpresentsamodelbasedontheon-farmirrigationschedulingandthesimulatedannealing(SA) optimizationmethodforagriculturalwaterresourcemanagement.Theproposedmodelisappliedto an irrigationprojectlocatedinDelta,Utahof394)6haareaforoptimizingeconomicpro"ts,simulatingthe water demand and crop yields and estimating the related crop area percentages with speci"ed water supply and planted area constraints. TheapplicationofSA toirrigated projectplanninginthis study can bedivided intonine steps: (1) to receivetheoutputfromtheon-farmirrigationschedulingmodule;(2)toenterthreesimulatedannealing parameters;(3) to de"ne the design &chromosome’representing the problem;(4) to generatethe random initial design &chromosome’; (5) to decode the design &chromosome’ into a real number; (6) to apply constraints;(7)toapplyanobjectivefunctionanda"tnessvalue;(8)toimplementtheannealingschedule by the Boltzmann probability; and (9) to set the &cooling rate’ and criterion for termination. Theirrigationwaterrequirementsfromtheon-farmirrigationschedulingmoduleare:(1)1067)9,441)7, and471)8mmforalfalfa,barleyandmaize,respectively,inoneunitcommandarea;and(2)1039)5,531)4, 490)9, and 539)4mm for alfalfa, barley, maize and wheat, respectively, in the other unit command area. The simulation results demonstrate that the most appropriate parameters of SA for this study are as follows:(1)initialsimulation&temperature’of1000;(2)numberofmovesequalto90;and(3)&coolingrate’ of 0)95. (2001SilsoeResearchInstitute 1. Introduction decisions prior to each crop season. Maidment and Hutchinson (1983) stated that irrigation water manage- Agricultural water resource planning or irrigation mentmodelsmaybeclassi"edintotwotypes:(1)demand planning can be described as a process for simulating simulationmodels,and(2) economicoptimizationmod- complex climate}soil}plant relationships, applying els. Demand simulation models pertain to the cli- mathematical optimization techniques to determine the mate}soil}plant system, and can be used to deduce the mostbene"cialcroppatternsandwaterallocations.Such amount and timing of irrigation needed to ensure ad- a determination can be non-trivial when large irrigated equate crop growth. Economic optimization studies re- areaswithsigni"cantcropdiversi"cationareconsidered, late the cost of irrigation to the bene"ts derived from especially with the typical temporal and volumetric re- increased crop productivity, among other possible fac- strictions on water supply. A computer-based model to tors, to determine the economically optimal patterns of simulate the climate}soil}plant systems with a new crops and irrigation water application. mathematical optimization technique could be an Irrigationschedulingis a basiccomponent of agricul- e!ective tool to help irrigation planners to make sound tural water resource planning. Many existing models 0021-8634/01/090109#16$35.00/0 109 ( 2001SilsoeResearchInstitute 110 S.-F. KUOE„ A‚. Notation a empirical coe$cient m substring length i ai,bi minimum and maximum values of de- M number of moves coded decimal M available soil moisture, mmm~1 A A crop planted area, ha N number of command areas within ir- Aj,% crop planted area within command rigated project area, % N numberof crops withincommand area c Aj,ha cropplanedareawithincommandarea, Oi,j operationcost ofthejthcropin theith ha command area, $ha~1 Auca area of each unit command area, ha Pi,j unit price of the jth crop in the ith A.*/ minimumpercentageareaofcropwith- command area, $ha~1 in command area, % P Boltzmann probability r A.!9 maximumpercentageareaofcropwith- Qdem cumulativecrop water demand in in command area, % command area, m3 di depth of irrigation water, mm Qsup availablewatersupplyforcommandarea, dn maximum net depletable depth, mm m3 D soil moisture depletion, mm Q cumulativewaterrequirementofthejth i,j Da soil allowable depletion, mm crop in the ith command area, m3 D.!9 soilmaximumallowabledepletion,mm r random number E energyduringannealingscheduling,di- R extraterrestrial radiation, mmday~1 a mensionless R root depth, mm z Ec, Ea conveyance and application s summationidenti"erforsubstringlength coe$cient, % S seed cost per hectare of the jth crop in i,j Emove project bene"t at current move during the ith command area, $ha~1 annealing scheduling, $ t day of year ET evapotranspiration,mm t1,tn Juliandaysatthebeginningandendof ETo dailyreferencecropevapotranspiration, the crop growth stage mmday~1 t time required for soil surface to dry d ETc potential crop evapotranspiration, after irrigation or rainfall, days mmday~1 t timeindayssincewettingduetoirriga- w ETca actual crop evapotranspiration, tion or rainfall, days mmday~1 „ daily air temperature, 0C dailyreferencecropevapotranspiration „ ,„ maximum and minimum daily temper- .!9 .*/ at each stage, mmday~1 atures, 3C ET,c,stage potential crop evapotranspiration at „sa simulation&temperature’duringcooling each stage, mmday~1 schedule, dimensionless ET,ca,stage actual crop evapotranspiration at each „new,„old simulation &temperatures’ at the end stage, mmday~1 and beginning, dimensionless DE change of project bene"t from current = unit price of irrigation water, $m~3 and previous moves, $ x decoded decimal fseason cumulativeseasonal in"ltration, mm >am crop yield reduction Fi,j fertilizer cost of the jth crop in the ith >a,season relative crop yield reduction due to command area, $ha~1 in"ltration over the entire season i, j command area and crop index > relative crop yield reduction due to am,season k decision variable water stress over the entire season Ka soil moisture stress coe$cient >am,stage relative crop yield reduction due to Kcb basal crop coe$cient water stress at each stage Ktcb basal crop coe$cient at day t >i,j yieldsper hectare of the jth cropin the Ks coe$cient for evaporation rate from ith command area, tonha~1 a wet soil surface a &cooling’ rate Ky crop yield response factor ht soil moisture at the tth day Ky,stage crop yield response factor at current hfc,hwp soilmoistureat "eld capacityandwilt- growth stage ing point L labour cost of the jth crop in the ith i,j command area, $ha~1 SIMULATEDANNEALING METHOD 111 determine on-"eld water demands based on (4) an annealing schedule; and (5) a criterion for ter- climate}soil}plant systems. Hill et al. (1982) developed minatingthealgorithm.Itwasconcludedthatsimulated the crop yield and soil management simulation model annealing had the potential for solving groundwater (CRPSM) to estimate crop yield as a function of soil managementproblemsand thatbecausetheapplication moisturecontent,cropphenologyandclimateduringthe ofsimulatedannealingto waterresourcesproblemswas growing periods. Keller (1987) developed the unit com- new and its development is immature further perfor- mandarea(UCA)modelbasedpartlyontheconceptsof mance improvements could be expected. Walker (1992) the CRPSM model. The UCA model consists of two applied the simulated annealing method to a peanut modules: the on-"eld module for water allocation and growth model for optimization of irrigation scheduling. distribution;and the "eld and weather generation mod- Thepeanutgrowthmodelwas"rstappliedtodetermine ule. Prajamwong (1994) developed the command area the days to irrigate and the amount of irrigation during decision support model (CADSM) with three main sub theseason.Later,simulatedannealingwasimplemented -models: (1) weather and "eld generation; (2) on-"eld inthepeanutmodel.Thegeneralproceduresofthisstudy crop}soilwaterbalancesimulation;and(3)wateralloca- can be summarized as follows: (1) an initial vector with tionanddistribution.Smith(1991)developedtheCROP- a"xed10-dayirrigationschedulewaschosenfromplant- WATcomputerprogramtocalculatecropwaterrequire- ing to harvest to begin simulation for each year from ments and irrigation requirements from climatic and 1974to 1991; (2) the peanut model was run and a gross crop data. yieldwasobtainedbasedontheinitialvectorselected;(3) Simulated annealing is a stochastic computational a new vector of days was generated by the random technique derived from statistical mechanics for "nding number generator and a simulated crop yield was cal- near globally solutions to large optimization problems culated; and (4) the Boltzmann distribution probability (Davis,1991).Themathematicaltheorybehindsimulated with generated random number was used to make the annealing can be explained by the theory of Markov decision whether to update the irrigation days or not. chains(Aartsetal.,1985;OttenandGinneken,1989)and in#uenced by the following three operators: (1) initial simulation &temperature’; (2) the number of moves to 2. Model development allowable rearrangements of the atoms within each temperature; and (3) the &cooling rate’ to decrease the Thisstudyfocusesmainlyondevelopinganirrigation &temperature’. In a mathematical context, these three and planning model to simulate an on-farm irrigation operators are the required parameters in the simulated system,and optimizetheallocationof theirrigatedarea annealingmethod.Kirkpatricketal.(1983)werethe"rst to alternativecrops for maximumnet bene"t by the use to propose and demonstrate the application of simula- ofacustomizedsimulatedannealingmethod.Therefore, tiontechniquesfromstatisticalphysicsofcombinational this work develops a model based on the on-farm optimizations. The mathematical theory to perform the irrigationschedulingandsimulatedannealingmethodto idea of simulated annealing can be obtained using the support the agricultural water resource planning and theory of Markov chains (Laarhoven & Aarts, 1987). management. The model consists mainly of six basic Bohachevskyetal.(1986)statedthattheadvantageofthe modules:(1) a main module to direct the runningof the simulated annealing method is the ability to migrate modelwithpull-downmenuability;(2)adatamoduleto through a sequence of local extremes in search of the enter the required data by a user-friendly interface; global solution and to recognize when the global (3) a weather generation module to generate the daily extremum has been located. weatherdata; (4) an on-farm irrigation scheduling mod- It is interesting to review some papers in which ule to simulate the daily waterrequirement and relative simulated annealing has been applied to water resource cropyield;(5)asimulatedannealingmoduletooptimize management and irrigation scheduling (Dougherty theprojectmaximumbene"t;and(6)aresultsmoduleto & Marryott, 1991; Marryott et al., 1993). Dougherty present results by tables, graphs and printouts. & Marryott(1991) appliedsimulated annealingto three Six basic data types are required for the model: (1) problems of optimal groundwater management: (1) projectsite and operation data; (2) command area data; adewateringproblem;(3)acontaminationproblem;and (3)seasonalwatersupplydata;(4)monthlyweatherdata; (4)contaminantremovalwithaslurrywall.Furthermore, (5) soil properties data; and (6) crop phenology and they stated that "ve elements are needed to apply economicdata.Herein,theweathergenerationmoduleis simulated annealing to a particular optimization prob- adopted from CADSM (Prajamwong, 1994) to generate lem: (1) a concise representation of the con"guration of dailyreferencecropevapotranspirationandrainfalldata the system decision variables; (2) a scalar cost function; based on the monthly mean and standard deviations (3)aprocedureforgeneratingrearrangementsofsystem; data.Theon-farmirrigationschedulingmodulereceives 112 S.-F. KUOE„ A‚. Fig. 1. Theframeworkandlogicemployedin the agriculturalwaterresourcedecision supportmodel; E , evapotranspiration T the basic project data and generated daily weather data daysfromeachofthegrowthstages.Thedailysimulation tosimulatetheon-farmwaterbalance.Thedailysimula- begins from the "rst command area in the project, tion procedure includes three programming loops: (1) the "rst crop within the command area, and the initial number of command areas within the simulated irriga- Julian day for each crop. This procedure continues tion project, (2) number of crops within each command until all crops in each command area and all command area,and(3)numberofdaysfromplantingtoharvestfor areasintheirrigationprojectareprocessed.Therelative eachcroptype.Thedailysimulationbeginsfromthe"rst crop yield and irrigation water requirements are the command area in the project, the "rst crop within the return values from this module. The results are sub- command area, and the "rst Julian day for each crop. sequently sent to the simulated annealing optimization The procedure continues until all crops in each com- module. mand area and all command areas in the irrigation The method developed by Keller (1987) and Prajam- project are processed. The output from this module in- wong(1994)was usedinthis studytogeneratethedaily cludes relative crop yield and crop irrigation water re- weather data based on the mean monthly and standard quirements.Bothoutputsaretherequiredinputsforthe deviation data. A normal distribution is assumed for following simulated annealing optimization module. generating the daily crop reference evapotranspiration Figure 1 presents the framework and logic employed in and air temperature. A log-normal distribution is as- the irrigation decision support model. sumedforgeneratingdailyprecipitation.Twoimportant control factors are necessary for generating the daily weatherdata:(1)thearidprobability;and(2)therandom 3. On-farm irrigation scheduling sowingdate.Thearid probabilitycontrolsthearidityof theyearandtherandomsowingdatea!ectsthesequence These on-farm irrigation scheduling processes deal of the generated data. Based on the generated daily with the daily water balance to estimate relative crop weatherdata,theHargreavesequation(Hargreavesetal., yield and irrigation water requirements. The Julian day 1985)wasusedtocalculatethereferencecropevapotran- of planting for each crop type is calculated based on spiration: speci"edcropplantingdates.Therefore,theJuliandayat harvestisthesumofacropplantingdayandcumulative E "0)0023R („#17)8)J„ !„ (1) To a .!9 .*/ SIMULATEDANNEALING METHOD 113 where:E denotesthe (grass)referencecropevapotran- be mathematically described by Eqns (7) and (8), To spirationinmmday~1;R representstheextraterrestrial respectively, a radiation in mmday~1; „ is the mean daily air temper- aturein3C;„.!9denotesthemaximumdailyairtemper- di" D (7) ature in 3C; and „.*/ represents the minimum daily air EcEa temperaturein 3C. D "(h !h )R D (8) a fc wp z .!9 Thebasalcropcoe$cient K representsthee!ects of cb the crop canopy on evapotranspiration and varies with where: D represents the soil moisture depletion in mm; timeofyear.Therate ofchangeofthebasalcropcoe$- E is the conveyance coe$cient; E denotes the water c a cientwithtimecanbeapproximatedasalinearincrease applicatione$ciency;R representstherootdepthofthe z (or decrease), as expressed in the following equation crop in mm; and D is the maximum allowable soil .!9 (Prajamwong,1994): water depletion in mm. Foreachcroptype,thecumulativewaterrequirement Kstage!Kstage~1 Kt "Kstage~1#(t!t )] cb cb inagrowingseasonis thesumof theirrigationapplica- cb cb stage~1 tstage!tstage~1 tiondepthsateachtimeduringthegrowingseason.The (2a) cumulativewaterrequirementforeachcommandareais the sum of seasonal crop irrigation water requirements and, withinthecommandarea.Finally,thecumulativeirriga- tion water requirement for the project is the sum of the t )t)t (2b) stage~1 stage water requirements of each command area within the where: Kt denotes the basal crop coe$cient for day t; project. cb Kstage representsthebasalcropcoe$cientat thecurrent The amounts of in"ltration and runo! are calculated cb based on the irrigation water or e!ective rainfall multi- stage; t is the "rst day of current crop stage; stage~1 plied by the percentage of deep percolation and runo! t denotesthe"rstdayofthenextcropgrowingstage; stage due to irrigation and rainfall. The model user enters and t is the day of year. percentagevaluesofin"ltrationandruno!.Thecumulat- The daily reference crop evapotranspiration E is To ive amount of in"ltration is used to calculate the crop used to calculate the potential E and actual crop Tc yield reduction due to waterlogging. evapotranspiration E , as given in Eqns (3) and (4), Tca Two factors in#uence the relative crop yield: (1) the respectively, waterstressduetoinsu$cientwaterforcropevapotran- E "(K #K )E (3) spiration; and (2) waterlogging due to in"ltration, pro- Tc cb s To duced by over-irrigationand or precipitation.Although ETca"(KcbKa#Ks)ETo (4) thepercentageofrelativecropyieldstartsat100%atthe beginningofagrowingseason,thevaluecanbereduced The soil moisture stress coe$cient K and the coe$- a tolessthan100%ifthereisanywaterstressorwaterlog- cient for evaporation rate from a wet soil surface after ging during the growing season. irrigation or rainfall K are given by s The relative yield reduction due to water stress is ln[100(h!h )/(h !h )#1] calculated at the end of each growth stage based on the Ka" t wp fc wp (5) ratio of cumulative potential crop evapotranspiration ln(101) E ,andactualcropevapotranspirationE in T,o,stage T,c,stage G Ct D1@2H each stage. The relationships can be described by the K"(1!K) 1! w F (6) s c t w following equations (Prajamwong, 1994): d C D where:ht denotesthe soilmoisture by volume at the tth >am,stage"1!Ky,stage 1!ET,ca,stage (9) day; hfc and hwp represent soil moisture by volume at ET,c,stage "eld capacity and wilting point; t is the time in days w tn sincewettingduetoirrigationand/orrainfall;andt de- E "+ E (10) d T,ca,stage Tca notesthetimeindaysrequiredforthesoilsurfacetodry t/t1 after an irrigation and/or rainfall event. t n For on-demand irrigation scheduling, irrigation ET,c,stage"+ ETc (11) t/t should be performed when the soil moisture depletion 1 D initially exceeds the allowable depletion D . The where:> denotestherelativeyieldreductiondueto a am,stage required amount, or application depth, d in mm for water stress at each stage; K represents the crop i y,stage agivenirrigation,andallowabledepletionD inmm,can yield response factor at the same stage; E is the a T,ca,stage 114 S.-F. KUOE„ A‚. actual crop evapotranspiration at the end of the stage; to maximize the project bene"t. The computational E denotesthepotentialcropevapotranspirationat procedure of the SA module can be divided into the T,c,stage theendofthestage;t andt representtheJuliandaysat followingsteps:(1)toreceivetheoutputfromtheirriga- 1 n thebeginningandendofthestage;andE andE are tionschedulingmodule;(2)toentersimulatedannealing Tca Tc daily crop potential and actual evapotranspiration in parameters through an user interface; (3) to de"ne the mmday~1, respectively. design &chromosome’ to represent the problem; (4) to The minimum value of > at each growth stage generate the random initial design &chromosome’; (5) to am,stage was chosen to be representative of the relative yield decode the design &chromosome’ into a real number; reduction due to water stress over the entire season (6)toapplyconstraints;(7)toapplyanobjectivefunction > as given by anda"tnessvalue;(8)toimplementtheannealingsched- am,season ule by the Boltzmann probability; and (9) to set the > " Min(> ; > ;2,;> ) (12) am, season am,1 am,2 am,stage &cooling rate’ and criterion for termination. Figure 2 The cumulative in"ltration within the root zone will showsthe#owchartofsimulatedannealingmodule.The reduce soil aeration due to waterlogging and in#uence followingsectionsprovidedescriptivedetailsabouteach the crop yield. Based on the only consideration of total of the steps. in"ltration during the crop growth period, the relative yield reduction due to waterlogging is calculated at 4.2. Data requirements the end of the season based on the ratio of cumulative total in"ltration f and the maximum net depletable season Three parameters must be speci"ed for the simulated depth d in the root zone. These relationships can be n annealing module as follows. represented by the following equations (Prajamwong, (1) Initial simulation &temperature’ 1994): Followingthesteelindustryanalogy,theinitialsimu- Af B lation &temperature’ refers to the initial temperature > "1!a season (13) a,season for&annealing’inthemodel.Thesimulation&temper- d n ature’isgraduallydecreaseddependingonthesimu- dn"D.!9MARz (14) lation&coolingrate’.Also,theinitialsimulation&tem- where:> denotestherelativeyieldreductiondueto perature’ will in#uence the Boltzmann probability a,season that dominates the annealing schedule. in"ltration over the entire season; a is the empirical (2) Number of moves coe$cient; D represents the maximum allowable de- .!9 The number of moves is the allowable time for re- pletion (fraction); M is the available soil moisture in A mmm~1;andR denotesthemaximumrootdepthinm. arrangement of the atoms to a lower energy state z within each temperature value. Certainly, a higher The product of relative yield reduction due to water stress over the entire season > and relative yield number of moves will have a higher opportunity to am,season "ndabetter"tnessvalue,butitwilltakemorecom- reduction due to waterlogging over the entire season > isthe"nalvalueofrelativecropyieldattheend putational time. Also, there should be an optimal a,season number of moves to obtain the optimal results for of the growing season. di!erent problems. (3) &Cooling rate’ 4. Implementation of simulated annealing The &cooling rate’ is the coe$cient to decide the rate of simulation &temperature’ decrease. A slow 4.1. Simulated annealing model &cooling rate’ (e.g. 0)9) allows the molecules to align themselves into a completely ordered crystalline Simulatedannealing(SA)hasrecentlybeenappliedto structure; this con"guration is the state of minimum functional optimization problems. Functional optimiza- energy for the system. If the &cooling’ is too rapid tionproblemscan bedescribedas &real-world’problems (e.g.0)1),thesystemdoesnotreachthehigherordered withanobjectiveofobtainingtheminimumormaximum state, but ends up in a high-energy state. The &cool- global values within speci"ed constraints. For decision ing’ schedule can be mathematically described as support in irrigation project planning, this &real-world’ follows: problem attempts to obtain the optimal crop area-allo- cated values to maximize the bene"t of an irrigation „ "a„ (15) new old project, given various constraints (e.g. maximum and minimum planted areas by crop type and maximum where:„ and„ arethesimulation&temperatures’at new old volumeofwatersupply).TheSAmodulehasbeenimple- theendandbeginningofthe&cooling’schedule;andais mented with the on-farm irrigation scheduling module the &cooling’ rate, which can range from 0 to 1. SIMULATEDANNEALING METHOD 115 Fig. 2. Flowchartofsimulated annealing 4.3. Representativedesign &chromosome’ &chromosome’.To design a &chromosome’length to rep- resent an irrigation project, the cumulative numbers of Thelengthofadesign&chromosome’consistsofa"xed crops within each command area are "rst calculated. number of binary digits. Also, the position and random Eachcropisthenassignedsevenbinarydigitstorepres- numbervaluesin#uencethedecodedvalueofthedesign entitsarea,whichcanrangefrom1to100%,inallofthe 116 S.-F. KUOE„ A‚. Fig. 3. Asamplechromosomecodingscheme to representseven cropsintheDelta project percentage points, of the cumulative area in each com- 100.Thenextstepistotransferthisdecimalnumberinto mandarea(sevenbinarydigits giveavalueof 0}27!1, crop area percentage A , and area A within each j,% j,ha or 0}127 in decimal). Finally, the length of a design commandarea. A simple averagingtechnique was used, &chromosome’ equals the cumulative number of crop as given by types multiplied by seven. x For example, two command areas have been con- A " j 100 (17) sidered in the Delta, Utah irrigation project for testing j,% +jN/c1xj the model. The "rst command area, UCA1, includes A three crop types and the second command area, UCA2, Aj,ha" j,%Auca (18) 100 includesfourcroptypes.Therefore,sevencroptypesare within these two command areas of the Delta, Utah where:jisthecropindex;Ncdenotesthenumberofcrops irrigation project, and the length of a design &chromo- withineachcommandarea;andAuca representsthearea some’shouldbe49.Whileconsideringadesign&chromo- of each unit command area. some’stringof49binarydigits,thesevencropsinthetwo commandareascanbedepictedincodedformasshown in Fig. 3. 4.5. Rearrangement of design &chromosomes’ Rearrangement of design &chromosomes’ is necessary 4.4. Decoding a design &chromosome’ into a real number to order the huge number of atoms within each simula- tion&temperature’valueforminimizingtheenergyofthe Thedesign&chromosome’can be decodedintoa deci- system.In this study,the rearrangementscan be treated malnumbertorepresentthecropareawithineachcom- asachangeinthelocationofthebinarydigitswithinthe mandarea.Theconventionaldecodingmethodisusedin design&chromosome’;therefore,thenewlyallocatedcrop thisstudy.Consideraproblemwithkdecisionvariables area can be obtained after decoding the rearranged de- x, i"1, 2,2,k, de"ned on the intervals x 3[a,b]. sign &chromosome’. i i i i Each decision variable can be decoded as a binary sub- Therearethreestepsintherearrangementofthedesign string of length m. The decoded decimal x can be &chromosome’:(1)movethe binarydigits at regions I}III i i obtained from the following equation (McKinny & depending on the length from the second cut site to the Lin, 1994): endofthedesign&chromosome’;(2)backthebinarydigits onepositioninregionII;and(3)movethebinarydigitsat x"a#bi!ai +mi b]2s (16) regionsIII}I,dependingonthelengthfromthe"rstdigit i i 2mi!1 s tothe"rstcutsite.Adesign&chromosome’with15binary s/0 digits and two random break points demonstrates the where:sisthesummationidenti"erforsubstringlength. procedure.Theoldandnewdesign&chromosome’,before ThefollowingcasestudyfromtheDelta,Utahproject and after rearrangement are shown in Fig. 4. contains seven crop types in the two command areas. Therefore, this problem has seven decision variables x , i andicanrangefrom1to7.Withoutconsideringinherent 4.6. Annealing scheduling by boltzmann probability crop area constraints, the percentage area of each crop type can range from 1 to 100% of the total command Annealing scheduling is the heart of the simulated area. Therefore, the interval for each decision variable annealingmethod.Thisprocedureisthemajordi!erence canbe representedas x 3 [1,100],anda equals 1and from the traditional optimizationmethods (e.g. iterative i i b equals 100. In conclusion, Eqn (16) can decode the improvement or Monte Carlo methods) that allows i binarydigitsintoanactualnumberintherangefrom1to perturbations to move uphill in a controlled fashion; SIMULATEDANNEALING METHOD 117 Fig. 4. Rearrangementchromosomeforthe simulatedannealingmethod Fig. 5. Computeryowforannealing schedulingin the simulatedannealingmodule therefore,thesimulatedannealingmethodhastheoppor- areas are accepted at this move because the energy tunity to escape from a local optimum toward a global has been improved from the previous move to the optimum.Figure 5 shows thecomputer#owfor anneal- current move. ingschedulingintheSAmoduleandcanbedescribedin (3) If the energy di!erence is positive (DE’0), this the following steps. means the energy was not improved, but the irriga- tionprojectmaximumbene"tandrelatedcropareas (1) Thesimulatedannealingmethodallowsmanymoves stillhavetheopportunitytoupdateiftheBoltzmann within one simulation &temperature’value; therefore, probability P is greater than the generated uniform the "rst step is to compare the energy di!erence DE r randomnumberr.TheBoltzmannprobabilitycanbe (i.e. di!erence of project bene"t) from the previous de"ned as move to the current move: Pr"e~DE@Tsa (20) DE"E !E (19) move move‘1 From the above equation, it can be seen that P is r where:E andE representtheprojectbene"t in#uenced by simulation &temperature’ „ ; that is, move move‘1 sa at current and previous moves. higher simulation &temperatures’ will have higher (2) If the energy di!erence is negative (DE (0), the P values,andthesystemhasagreateropportunityto r irrigationproject maximumbene"tandrelatedcrop updatethecon"gurationifDE’0.Thisalsoimplies 118 S.-F. KUOE„ A‚. that the system at a higher simulation &temperature’ has a higher ability to rearrange the atoms (i.e. to jump away from local optima) for "nding better, moreoptimalresults.Asthesimulation&temperature’ continues to decrease, the system tends to equilib- rium because the P value is small, and there is no r more ability to update the con"guration if *E ’0. Finally, the global (or near global) optimum can be determined from this procedure. 4.7. Objective function and ,tness value In this study, the objective function includes the in- comefromcropharvest,costofirrigationwaterandcrop productioncost.Theobjectiveistomaximizetheirriga- tion project bene"t or the "tness value from the seven crops growing in the two command areas. Within the calculationloop of design &chromosome’size, the objec- tivefunctionreturnsa"tnessvaluetothemodelandthen updatesthe"tnessvalueandrelatedcrop-allocatedarea ifthisvalueishigherthanpreviousones.Attheendofthe design&chromosome’loop,thesubsequent"tnessvalueis the highest bene"t within the loop. Also, the maximum "tnessvalueisselectedfromthegenerationnumberloop. Therefore,the"tnessvalueandrelatedcropareaarethe optimumresultsattheendofthecalculations.Theobjec- tive function is mathematically expressed as Maximize: N N N N c c + + (P > !S !F !O )A != + + Q i,j i,j i,j i,j i,j i,j i,j i/1j/1 i/1j/1 (21) Fig. 6. Seiver River Basin, Utah (Tzou, 1989). , Basin; ,Rivers; ,Cities where:i,jisthecommandareaandcropindex;Nis the numberofcommandareaswithinirrigatedproject;N is c bene"t,themaximumandminimumareapercentages the number of crops within each command area; P is i,j must be considered for the crops: unit price of the jth crop in the ith command area in $ha~1;>i,jisyieldsperhectareofthejthcropin theith A )A)A (22) commandareaintonha~1;S isseedcostperhectareof .*/ .!9 i,j the jth crop in the ith command area in $ha~1; Fi,j is whereA.*/andA.!9aretheminimumandmaximum fertilizercost of thejthcrop inthe ithcommandarea in percentageareavaluesofcropjincommandareaiin $ha~1; ‚i,j is labour cost of the jth crop in the ith %, respectively. commandareain$ha~1;Oi,jisoperationcostofthejth (2) Thecumulativewaterdemandofcropjincommand crop in the ith command area in $ha~1; Ai,j is planted areai should beless thanthe availablewatersupply areaofthejthcropintheithcommandareainha;=is for each command area: unitpriceofirrigationwaterin$m~3;and Q is cumu- i,j N lative water requirement of the jth crop in the ith com- +c Q )Q (23) mand area in m3. dem sup j/1 The objective function is subject to the following where:Q denotestheirrigationwaterrequirement constraints. dem forcropjincommandareaiinm3;andQ repres- sup (1) To consider social factors and to prevent one high ents the available water supply for command area i -valuecropfromdominatingthesearchformaximum in m3.