Chapter Review:
Eiben & Smith (2003). What Is an Evolutionary Algorithm? (Chap 2) In: Introduction to Evolutionary Computing. Springer.
The objective of the text is to describe the main characteristics of an evolutionary algorithm (EA). According to the authors, there are many variants of EA, although the basic idea is: “given a population of individuals within some environment that has limited resources, competition for those resources causes natural selection.” Translating for an optimization problem, in a function to be maximized, the quality of solutions, measure by the objective function, increases at each generation, due the evolutionary process. There are two drivers of the evolution process: variation operators (recombination and mutation) responsible for increasing the diversity within the population, and selection, which exclude the worst individuals and increase the quality of the solutions.
The main components of EA are: representation (definition of individuals), evaluation function (or fitness function), population, parent selection mechanism, variation operators (recombination and mutation), and survivor selection mechanism (replacement).
The first component in an EA is the representation, which means defining the how the solutions (individuals) are represented within the algorithm. Several syntaxes can be used. The terms candidate solution, phenotype, and individual are synonymous and denote points in the decision space. The terms genotype, chromosome and again individual represent points in the space where the evolutionary search happens. The transformation from the phenotype to the genotype space is called encoding, while the opposite is called decoding.
The second component is the evaluation function. Under the evolutionary perspective, the evaluation function represents the requirement the population should adapt to. In the algorithm, it measures the quality of the genotypes. Another terms used are fitness function or objective function.
The population is a multiset of individuals or genotypes. The population size can vary during the run. An important characteristic of the population is diversity, because it increases the chances of finding a global solution.
The parent selection mechanism is responsible for increasing the quality of the population by selecting better individuals to become parents of the next generation. Also called mating selection, an individual is selected based on its quality and also probability.
News individuals are created from old ones by the variation operators. Mutation is a unary operator applied to one genotype, generating a slightly different individual (mutant). This process is always stochastic. The purpose of mutation is to introduce diversity in the population, so a larger space is explored, decreasing the chances of population being trapped in local optimums.
The second variation operator is the recombination or crossover. In this case, it is a binary operator, crossing genotype of two individuals into one or two offspring individuals. It is also a stochastic operator because which parts of the genetic material and how it is combined are dependent on a random process.
Survivor selection, environmental selection or replacement is the process of distinguishing individuals based on their fitness. It is a similar process of parent selection, but used in a different stage of the algorithm.
Another component of EA is the initialization. Usually, the set of individuals are seeded randomly.
The last phase of EA is the termination condition. The text list four typical criteria for termination: maximum CPU time elapses, total number of fitness evaluations, fitness improvement remains under a threshold value for a given period of time, and the population diversity drops under a given threshold.
-------------------------------------------------------------------------------------------------------------
Article Review:
Kim, E., Jha, M., and Son, B. (2005). "Improving the computational efficiency of highway alignment optimization models through a stepwise genetic algorithms approach." TRANSPORTATION RESEARCH PART B-METHODOLOGICAL, 39(4), 339-360.
Questions about the Article:
a. Many different methods have been applied for highway alignment optimization. What are the deficiencies and advantages of using these methods? Why was a GA chosen in this work?
b. What are the differences among the different scenarios tested in the problem?
c. How does the GA perform for each of the different scenarios? What are the major conclusions of the article?
Discussion:
According to the authors, there are many reasons why others methods than GA fail in solving the highway alignment problem. Some of the defects are: necessity of differentiable objective functions, discontinuity, trap in local optima, output not smooth, applicability for implicit functions, inefficiencies, non-linear cost functions etc. GA was chosen in this work because the nature of the problem which involves constrained, non-linear, and non-differentiable structure, hardly solved by classic optimization techniques.
The differences among the different scenarios tested in the problem are the one and two-step optimization, the population size and the quality of the results. Scenarios 1 and 2 are one-step optimization with different population sizes, resulting in different quality of solutions. Scenario 3 is a two-step optimization. The first step is used to indicate the number of intersections, while the second step is run separately for each segment of highway. In this case there is a substantial decrease of computation time, and increase of quality of solution, in the present case, lower cost. In summary, the stepwise optimization improves significantly the results, and also results in better solution than the original procedure.
terça-feira, 26 de janeiro de 2010
New Course - CVEN 689 - Evolutionary Computation
I'm taking a new course: Evolutionary Computation for Civil Engineering, taught by Dr. Zechman, my adviser. This course can be seen as a continuation of the previous course CVEN 665 - Water Resources Systems Analysis. This blog will now receive posts related to this new and exciting course.
segunda-feira, 21 de setembro de 2009
Article Review: CEDAR CREEK
Debele, B., Srinivasan, R., and Parlange, J. Y. (2008). "Coupling upland watershed and downstream waterbody hydrodynamic and water quality models (SWAT and CE-QUAL-W2) for better water resources management in complex river basins." Environmental Modeling and Assessment, 13(1), 135-153.
The article presents a modeling framework of water quantity and quality of upland watershed and a downstream reservoir. Two models have been coupled: SWAT (Soil & Water Assessment Tool) and CE-QUAL-W2. SWAT is a hydrological and hydraulic 1-D hydrodynamic and water quality model used to simulate upland watershed and narrower streams. CE-QUAL-W2 is a waterbody laterally averaged (2-D) hydrodynamic model, suited for narrow and deep waterbodies where lateral variation is minimum. This modeling approach has been tested in Cedar Creek watershed, Texas. The main land uses is agriculture, forest and urban areas. The watershed is drained by two main creeks (Cedar and Kings) and seven smaller tributaries which feed into the Cedar Creek Reservoir. The mean depth of the reservoir is 6.5 meters, a surface area of 34,300 acres and a volume of 566,000 acre-feet. About 25 % of total reservoir inflow is lost through evaporation and approximately 10 % is withdrawn for urban consumption (Fort Worth and nearby towns). Data from a period of 5 years, from 1997 to 2001, was used to calibrate the models. The calibration of the reservoir hydrodynamic showed good waterbalance match between the observed data and simulated results. The water quality calibration was performed with first temperature followed by Dissolved Oxygen. A second dataset of water quality parameters such as organic nitrogen, organic phosphorus, phosphate, chlorophyll a, total nitrogen, and total phosphorus concentration, were available and used in the calibration. Comparison among observed and simulated water quality parameters showed reasonable agreements. It was concluded that this framework can properly simulate seasonal and intraseasonal distributions of many water quality variables, with exception of Chl-a, TP, TN and NH3/NH4. The reasons for that could be by low quality of these input dataset and error propagation and compounding. In conclusion, the authors state that the integration of such models of spatially variable upland watershed hydrological and water quality models with downstream waterbody hydrodynamic and water quality models can help the water resources management, allowing the backtrack of the spatial sources of contaminants and support a good decision making for water quality standards in downstream waterbody.
The article presents a modeling framework of water quantity and quality of upland watershed and a downstream reservoir. Two models have been coupled: SWAT (Soil & Water Assessment Tool) and CE-QUAL-W2. SWAT is a hydrological and hydraulic 1-D hydrodynamic and water quality model used to simulate upland watershed and narrower streams. CE-QUAL-W2 is a waterbody laterally averaged (2-D) hydrodynamic model, suited for narrow and deep waterbodies where lateral variation is minimum. This modeling approach has been tested in Cedar Creek watershed, Texas. The main land uses is agriculture, forest and urban areas. The watershed is drained by two main creeks (Cedar and Kings) and seven smaller tributaries which feed into the Cedar Creek Reservoir. The mean depth of the reservoir is 6.5 meters, a surface area of 34,300 acres and a volume of 566,000 acre-feet. About 25 % of total reservoir inflow is lost through evaporation and approximately 10 % is withdrawn for urban consumption (Fort Worth and nearby towns). Data from a period of 5 years, from 1997 to 2001, was used to calibrate the models. The calibration of the reservoir hydrodynamic showed good waterbalance match between the observed data and simulated results. The water quality calibration was performed with first temperature followed by Dissolved Oxygen. A second dataset of water quality parameters such as organic nitrogen, organic phosphorus, phosphate, chlorophyll a, total nitrogen, and total phosphorus concentration, were available and used in the calibration. Comparison among observed and simulated water quality parameters showed reasonable agreements. It was concluded that this framework can properly simulate seasonal and intraseasonal distributions of many water quality variables, with exception of Chl-a, TP, TN and NH3/NH4. The reasons for that could be by low quality of these input dataset and error propagation and compounding. In conclusion, the authors state that the integration of such models of spatially variable upland watershed hydrological and water quality models with downstream waterbody hydrodynamic and water quality models can help the water resources management, allowing the backtrack of the spatial sources of contaminants and support a good decision making for water quality standards in downstream waterbody.
sexta-feira, 28 de agosto de 2009
Summer Summary
This post is a summary of the main ideas collected during the research period of summer. In total, I read completely 16 articles, and another number of incompletely readings. The research focused mainly in two topics: my present research, which is stormwater sustainability, and optimization techniques, mainly focused in multi-objective genetic algorithm.
For the first and more important topic of my research in this summer, the readings helped me to support the main ideas of the hydrologic footprint residence. HFR is a new metric used to assess the impacts of urbanization in the hydrologic flow regime. Many articles served as references to characterize the impact of urbanization in the hydrological regime. The transformation of natural land covers as forest and grassland to impervious covers alters most of the hydrological processes such as interception, evapotranspiration, infiltration and overland runoff.
In the revised literature, it was identified the main hydrologic metrics used to assess the impact of urbanization. Most of the metrics are based in time series of flow discharges. The main metrics found are: flow frequency curve, flow duration curve, TQmean, which is fraction of year that flow rate exceeds the mean flow rate of the entire flow time series, TQ0.5yr, which is the fraction of year that the flow rate exceeds the historical half-year peak flow rate, peak flow, storm flow duration, time-to-peak, ratio of time-to-peak to storm flow event duration, event-mean rise rate, event-mean fall rate, duration that the flow rate exceeds 75% of the peak flow rate in an event, ratio of event-peak-duration to total event duration, and IHA (indices of hydrological alteration). Those metrics can be used to evaluate different alternatives of development, Best Management Practices (BMPs) and Low Impact Development (LID).
Besides that, an interesting discussion about the effectiveness of BMPs was addressed in some articles. The argument is BMPs introduces a sustained flow for most of the storms which can harm downstream communities. BMPs are design to attenuate bigger storms. Besides that, urbanization increases the frequency of flow events. The combination of more frequent events with sustained flow is being questioned by recent researches.
Another topics explored during this research are the links between the hydrological flow regime and heath of instream ecosystems. Poff et al (1997) summarizes the knowledge about formation of habitats and the natural hydrological regime. Scientific community agrees that stream is a master variable for instream environments because it regulates most of biological and physicochemical processes in rivers. The natural variability of low and high flows plays a crucial role in the entire life cycle of instream and riverine species. Watershed management has been limited to water quality and one aspect of water quantity, which is minimum flow.
The second set of articles is related to optimization algorithms. Two interesting articles present a new heuristic optimization technique called Harmony Search (HS). HS is inspired the way musician improvise harmony searching for maximize the aesthetic estimation of music (objective function). The decision variables are the pitches (sounds) musicians play. Several problems are tested in the articles, and HS presented better performance when compared to other optimization techniques such as Generalized Reduced Gradient (GRC), Evolutionary Programming (EP), Genetic Algorithm (GA), and Nonlinear Programming Gradient (NLPG). This better efficiency, however, should be looked with attention, since performance of methods can be highly dependent of parameters and the problems itself.
The last group of articles is focused in Multi-objective optimization techniques, more specifically genetic algorithms. The objective here is to understand the main operators used in different techniques. Two methods have been studied in more details: MOGA and NSGA-II. One article combined the use of MOGA and Constrained Differential Dynamic Programming in a surface reservoir allocation problem.
In summary, important goals have been achieved during this summer period. The idea of reading two papers a week, one specific of my research and other more general, to discuss in the research group is really efficient. My reading and writing skills have improved a lot in period. I hope we can continue to do that with, hopefully, more students contributing to the discussion.
For the first and more important topic of my research in this summer, the readings helped me to support the main ideas of the hydrologic footprint residence. HFR is a new metric used to assess the impacts of urbanization in the hydrologic flow regime. Many articles served as references to characterize the impact of urbanization in the hydrological regime. The transformation of natural land covers as forest and grassland to impervious covers alters most of the hydrological processes such as interception, evapotranspiration, infiltration and overland runoff.
In the revised literature, it was identified the main hydrologic metrics used to assess the impact of urbanization. Most of the metrics are based in time series of flow discharges. The main metrics found are: flow frequency curve, flow duration curve, TQmean, which is fraction of year that flow rate exceeds the mean flow rate of the entire flow time series, TQ0.5yr, which is the fraction of year that the flow rate exceeds the historical half-year peak flow rate, peak flow, storm flow duration, time-to-peak, ratio of time-to-peak to storm flow event duration, event-mean rise rate, event-mean fall rate, duration that the flow rate exceeds 75% of the peak flow rate in an event, ratio of event-peak-duration to total event duration, and IHA (indices of hydrological alteration). Those metrics can be used to evaluate different alternatives of development, Best Management Practices (BMPs) and Low Impact Development (LID).
Besides that, an interesting discussion about the effectiveness of BMPs was addressed in some articles. The argument is BMPs introduces a sustained flow for most of the storms which can harm downstream communities. BMPs are design to attenuate bigger storms. Besides that, urbanization increases the frequency of flow events. The combination of more frequent events with sustained flow is being questioned by recent researches.
Another topics explored during this research are the links between the hydrological flow regime and heath of instream ecosystems. Poff et al (1997) summarizes the knowledge about formation of habitats and the natural hydrological regime. Scientific community agrees that stream is a master variable for instream environments because it regulates most of biological and physicochemical processes in rivers. The natural variability of low and high flows plays a crucial role in the entire life cycle of instream and riverine species. Watershed management has been limited to water quality and one aspect of water quantity, which is minimum flow.
The second set of articles is related to optimization algorithms. Two interesting articles present a new heuristic optimization technique called Harmony Search (HS). HS is inspired the way musician improvise harmony searching for maximize the aesthetic estimation of music (objective function). The decision variables are the pitches (sounds) musicians play. Several problems are tested in the articles, and HS presented better performance when compared to other optimization techniques such as Generalized Reduced Gradient (GRC), Evolutionary Programming (EP), Genetic Algorithm (GA), and Nonlinear Programming Gradient (NLPG). This better efficiency, however, should be looked with attention, since performance of methods can be highly dependent of parameters and the problems itself.
The last group of articles is focused in Multi-objective optimization techniques, more specifically genetic algorithms. The objective here is to understand the main operators used in different techniques. Two methods have been studied in more details: MOGA and NSGA-II. One article combined the use of MOGA and Constrained Differential Dynamic Programming in a surface reservoir allocation problem.
In summary, important goals have been achieved during this summer period. The idea of reading two papers a week, one specific of my research and other more general, to discuss in the research group is really efficient. My reading and writing skills have improved a lot in period. I hope we can continue to do that with, hopefully, more students contributing to the discussion.
End of Summer I - List of articles
The summer is over... here is the list of articles that I read in this period:
1. Bertrand-Krajewski, J.-L., Barraud, S., and Chocat, B. (2000). "Need for improved methodologies and measurements for sustainable management of urban water systems." Environmental Impact Assessment Review, 20(3), 323-331.
2. Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T. (2002). "A fast and elitist multiobjective genetic algorithm: NSGA-II." Evolutionary Computation, IEEE Transactions on, 6(2), 182-197.
3. Derek B. Booth, James R. Karr, Sally Schauman, Christopher P. Konrad, Sarah A. Morley, Marit G. Larson, and Stephen J. Burges. (2004). "Reviving Urban Streams: Land Use, Hydrology, Biology, and Human Behavior." Journal of the American Water Resources Association, 40(5), 1351-1364.
4. Egderly, J. L., Roesner, L. A., Rohrer, C. A., and Gironas, J. A. "Quantifying Urban-Induced Flow Regime Alteration and Evaluating Mitigation Alternatives Using Mathematical Models and Hydrologic Metrics." 425.
5. Fan, C., and Li, J. (2004). "A Modelling Analysis of Urban Stormwater Flow Regimes and their Implication for Stream Erosion." Water Quality Research Journal of Canada, 39(4), 356-61.
6. Geem, Z. W. (2009). "Harmony search optimisation to the pump-included water distribution network design." Civil Engineering and Environmental Systems, 26(3), 211 - 221.
7. Getter, K. L., Rowe, D. B., and Andresen, J. A. (2007). "Quantifying the effect of slope on extensive green roof stormwater retention." Ecological Engineering, 31(4), 225-231.
8. Graham, P., Maclean, L., and Medina, D. (2004). "The Role of Water Balance Modelling in the Transition to Low Impact Development." Water Quality Research Journal of Canada, 39(4), 331-42.
9. Konak, A., Coit, D. W., and Smith, A. E. (2006). "Multi-objective optimization using genetic algorithms: A tutorial." Reliability Engineering & System Safety, 91(9), 992-1007.
10. McCuen, R. H. (1979). "Downstream Effects of Stormwater Management Basins." Journal of the Hydraulics Division, 105(11), 1343-1356.
11. Nehrke, S. M., and Roesner, L. A. (2004). "Effects of Design Practice for Flood Control and Best Management Practices on the Flow-Frequency Curve." Journal of Water Resources Planning and Management, 130(2), 131-139.
12. Poff, N. L., Allan, J. D., Bain, M. B., Karr, J. R., Prestegaard, K. L., Richter, B. D., Sparks, R. E., and Stromberg, J. C. (1997). "The Natural Flow Regime." BioScience, 47(11), 769-784.
13. Reddy, M., and Kumar, D. (2006). "Optimal Reservoir Operation Using Multi-Objective Evolutionary Algorithm." Water Resources Management, 20(6), 861-878.
14. Roesner, L. A., Bledsoe, B. P., and Brashear, R. W. (2001). "Are Best-Management-Practice Criteria Really Environmentally Friendly?" Journal of Water Resources Planning and Management, 127(3), 150-154.
15. Yang, C.-C., Chang, L.-C., Yeh, C.-H., and Chen, C.-S. (2007). "Multiobjective Planning of Surface Water Resources by Multiobjective Genetic Algorithm with Constrained Differential Dynamic Programming." Journal of Water Resources Planning and Management, 133(6), 499-508.
16. Zong Woo Geem, Joong Hoon Kim, and Loganathan, G. V. (2001). "A New Heuristic Optimization Algorithm: Harmony Search." SIMULATION, 76(2), 60-68.
1. Bertrand-Krajewski, J.-L., Barraud, S., and Chocat, B. (2000). "Need for improved methodologies and measurements for sustainable management of urban water systems." Environmental Impact Assessment Review, 20(3), 323-331.
2. Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T. (2002). "A fast and elitist multiobjective genetic algorithm: NSGA-II." Evolutionary Computation, IEEE Transactions on, 6(2), 182-197.
3. Derek B. Booth, James R. Karr, Sally Schauman, Christopher P. Konrad, Sarah A. Morley, Marit G. Larson, and Stephen J. Burges. (2004). "Reviving Urban Streams: Land Use, Hydrology, Biology, and Human Behavior." Journal of the American Water Resources Association, 40(5), 1351-1364.
4. Egderly, J. L., Roesner, L. A., Rohrer, C. A., and Gironas, J. A. "Quantifying Urban-Induced Flow Regime Alteration and Evaluating Mitigation Alternatives Using Mathematical Models and Hydrologic Metrics." 425.
5. Fan, C., and Li, J. (2004). "A Modelling Analysis of Urban Stormwater Flow Regimes and their Implication for Stream Erosion." Water Quality Research Journal of Canada, 39(4), 356-61.
6. Geem, Z. W. (2009). "Harmony search optimisation to the pump-included water distribution network design." Civil Engineering and Environmental Systems, 26(3), 211 - 221.
7. Getter, K. L., Rowe, D. B., and Andresen, J. A. (2007). "Quantifying the effect of slope on extensive green roof stormwater retention." Ecological Engineering, 31(4), 225-231.
8. Graham, P., Maclean, L., and Medina, D. (2004). "The Role of Water Balance Modelling in the Transition to Low Impact Development." Water Quality Research Journal of Canada, 39(4), 331-42.
9. Konak, A., Coit, D. W., and Smith, A. E. (2006). "Multi-objective optimization using genetic algorithms: A tutorial." Reliability Engineering & System Safety, 91(9), 992-1007.
10. McCuen, R. H. (1979). "Downstream Effects of Stormwater Management Basins." Journal of the Hydraulics Division, 105(11), 1343-1356.
11. Nehrke, S. M., and Roesner, L. A. (2004). "Effects of Design Practice for Flood Control and Best Management Practices on the Flow-Frequency Curve." Journal of Water Resources Planning and Management, 130(2), 131-139.
12. Poff, N. L., Allan, J. D., Bain, M. B., Karr, J. R., Prestegaard, K. L., Richter, B. D., Sparks, R. E., and Stromberg, J. C. (1997). "The Natural Flow Regime." BioScience, 47(11), 769-784.
13. Reddy, M., and Kumar, D. (2006). "Optimal Reservoir Operation Using Multi-Objective Evolutionary Algorithm." Water Resources Management, 20(6), 861-878.
14. Roesner, L. A., Bledsoe, B. P., and Brashear, R. W. (2001). "Are Best-Management-Practice Criteria Really Environmentally Friendly?" Journal of Water Resources Planning and Management, 127(3), 150-154.
15. Yang, C.-C., Chang, L.-C., Yeh, C.-H., and Chen, C.-S. (2007). "Multiobjective Planning of Surface Water Resources by Multiobjective Genetic Algorithm with Constrained Differential Dynamic Programming." Journal of Water Resources Planning and Management, 133(6), 499-508.
16. Zong Woo Geem, Joong Hoon Kim, and Loganathan, G. V. (2001). "A New Heuristic Optimization Algorithm: Harmony Search." SIMULATION, 76(2), 60-68.
segunda-feira, 27 de julho de 2009
Harmony Search
Article Review
Geem, Z.W., Kim, J.H., Loganathan, G.V. (2001) “A New Heuristic Optimization Algorithm: Harmony Search”. 76(2): 60-68.
This paper presents the algorithm Harmony Search (HS), a new heuristic optimization algorithm inspired in the way musician improvise harmonies. The analogy with music is: musical performance seeks a harmony with maximum aesthetic estimation, as the optimization algorithm seeks the best solution. The aesthetic estimation represents the objective function and the pitches of instruments represent decision variables. The decision variables achieve better solution by a process of practice. After each iteration, the solution is evaluated. If the harmony is better than the previous ones, it is included in the Harmony Memory. The process is repeated until the stopping criteria is satisfied.
The harmony memory is initialized with random values. A new harmony is generated based on the solutions already present in the harmony search. If the new harmony is better than the ones in the harmony memory, it is included on it, and the worst harmony is excluded. In order to increase the decision space and find the global optimum, a parameter called Harmony Memory Considering Rate (HMCR), ranging from 0 to 1, is used to randomly generate new solutions. HMCR is uniformly generated. If it is above the current value of the HMCR, the algorithm selects a new variable with certain probability and introduces the new random value.
Another operator is used to escape local optima, similar to crossover in the genetic algorithm (GA). The Pitch Adjusting Rate (PAR) is used to select a variable with certain probability and shifts the value with its neighbors. The article uses the example of the solution {1,3,4,6,7,9}. The value {6} can be moved to neighboring {4} or {7}.
The article illustrates the harmony search with 3 problems found in the literature. The first one is the Traveling Salesman Problem (TSP), which tries to find the shortest path for a salesman that has to visit a certain number of cities once. The second problem is a 2 dimension constrained minimization problem. The performance of HS is compared with others methods like GA, Generalized Reduced Gradient (GRC) and Evolutionary Programming (EP). HS had better performance compared to the other methods. The last problem is the design of a pipeline network for water supply consisted of 32 nodes, 34 links and 3 loops. The results were compared with GA and Nonlinear Programming Gradient (NLPG). The HS produced the solution with the least cost related to the other methods.
Discussion
The HS algorithm is a very interesting methodology. Particularly for me that play the guitar, was very curious to see how real life phenomena can be invently used to develop new techniques to solve older and new problems. This paper was also interesting because I had the opportunity to attend the talk of one of the authors in the 2009 US-Korea Conference on Science, Technology and Entrepreneurship, last July 16-19, 2009 in Raleigh, North Carolina.
Geem, Z.W., Kim, J.H., Loganathan, G.V. (2001) “A New Heuristic Optimization Algorithm: Harmony Search”. 76(2): 60-68.
This paper presents the algorithm Harmony Search (HS), a new heuristic optimization algorithm inspired in the way musician improvise harmonies. The analogy with music is: musical performance seeks a harmony with maximum aesthetic estimation, as the optimization algorithm seeks the best solution. The aesthetic estimation represents the objective function and the pitches of instruments represent decision variables. The decision variables achieve better solution by a process of practice. After each iteration, the solution is evaluated. If the harmony is better than the previous ones, it is included in the Harmony Memory. The process is repeated until the stopping criteria is satisfied.
The harmony memory is initialized with random values. A new harmony is generated based on the solutions already present in the harmony search. If the new harmony is better than the ones in the harmony memory, it is included on it, and the worst harmony is excluded. In order to increase the decision space and find the global optimum, a parameter called Harmony Memory Considering Rate (HMCR), ranging from 0 to 1, is used to randomly generate new solutions. HMCR is uniformly generated. If it is above the current value of the HMCR, the algorithm selects a new variable with certain probability and introduces the new random value.
Another operator is used to escape local optima, similar to crossover in the genetic algorithm (GA). The Pitch Adjusting Rate (PAR) is used to select a variable with certain probability and shifts the value with its neighbors. The article uses the example of the solution {1,3,4,6,7,9}. The value {6} can be moved to neighboring {4} or {7}.
The article illustrates the harmony search with 3 problems found in the literature. The first one is the Traveling Salesman Problem (TSP), which tries to find the shortest path for a salesman that has to visit a certain number of cities once. The second problem is a 2 dimension constrained minimization problem. The performance of HS is compared with others methods like GA, Generalized Reduced Gradient (GRC) and Evolutionary Programming (EP). HS had better performance compared to the other methods. The last problem is the design of a pipeline network for water supply consisted of 32 nodes, 34 links and 3 loops. The results were compared with GA and Nonlinear Programming Gradient (NLPG). The HS produced the solution with the least cost related to the other methods.
Discussion
The HS algorithm is a very interesting methodology. Particularly for me that play the guitar, was very curious to see how real life phenomena can be invently used to develop new techniques to solve older and new problems. This paper was also interesting because I had the opportunity to attend the talk of one of the authors in the 2009 US-Korea Conference on Science, Technology and Entrepreneurship, last July 16-19, 2009 in Raleigh, North Carolina.
During our weekly discussion meeting, we tried to compared the differences and similarities between HS and GA. As a heuristic method, HS is similar to GA. One aspect that seems important is that HS creates a new solution based in all existing solutions presented in the harmony memory, while GA creates a new solution only with two previous solutions (parents).
sexta-feira, 26 de junho de 2009
Downstream Effects of Stormwater Management Basins
Article Review
McCuen, R.H. (1979) “Downstream effects of Stormwater Management Basins” Journal of the Hydraulics Division, Vol. 105, No. 11.
Prof. McCuen addresses the problem of hydrological alteration due urbanization. The use of impervious materials decreases natural storage, increasing peak rates, decreasing time-to-peak, and increasing the volumes of runoff and sediments. To mitigate these detrimental effects storm water management (SWM) is required. However, according to the paper, many SWM strategies fail in mitigate the urbanization effects because “they only attempt to limit peak flow rates and sediments volumes” to predevelopment conditions. This is in general attempted by the use of detention basins. This strategy, however, is not sufficient. This problem lead to main question of the article: “Are SWM basins effectively meeting the intent of stormwater management?”
“Urban development causes a decrease in natural storage, including infiltration, interception, and depression storage”. SWM basin is an attempt to restore the loss of natural storage in the watershed. This volume can be artificially restored, but the timing characteristics introduced by detention basins are significantly different from the predevelopment conditions. In natural conditions, the major part of the storage volume is filled during the storm event, while in a detention facility this storage is rapidly filled during the risen portion of the hydrograph.
A second effect introduced by detention basin is that the increased volume of direct runoff is released at a higher rate when compared to natural storage. This cause increase in the duration of bankfull flows.
Due the reasons explained so far, the work examines the hypothesis “that, when changes in both timing characteristics and flow volumes are not corrected by SWM, they may have an adverse effect on flow conditions downstream from the SWM basin.”
A 2.12 square mile watershed was simulated using the Soil Conservation Service TR-20 hydrological model. The predominant soils are silt loams, characterized as deep, well-drained, and moderately erodible. Simulations indicate that peak flow increases from 11.7 to 59.3 cfs (factor of five!!!) from pre-development to urbanized condition of one catchment for the 10 yr-storm. In terms of volume, there is an increase of 100%. The time-to-peak decrease 7 minutes. Introducing a detention basin, the peak flow is reduced to 13.08 cfs, but the time-to-peak is 36 minutes greater than that which existed prior to development. A compared analysis is done for the 100 yr-storm. The effects are the same, but the differences are much lower.
Looking further downstream in the watershed, the computation indicates that for the 100 yr-storm the SWM basin increases the peak flow compared to the post development with no control. This is true for approximately 5 miles downstream the storage facility. The reason for that is changes in timing characteristics affects the runoff conditions downstream.
After the hydrological analysis, the author has approached the bedload transport. Although its is recognized the difficulty in estimating bedload discharges, a theoretical model can be used to assess different scenarios and trace comparisons between them. A model developed by Goncharov was used to predict the sediment discharge as a function of mean flow velocity, mean sediment diameter, the critical velocity of sediment, and the mean depth. The previous discussed scenarios were evaluated to generate estimative of sediment yield. The results indicate that even with the SWM basin there is a significant increase in total volume of sediment. This is due the sustain flow introduced by the basin, which induce higher velocities than the critical velocity over a longer period.
The author finalizes the article with some considerations related with SWM policies and designs. He considers three aspects important:
(1) “The recognition of a comprehensive interpretation to the definition of the intent of SWM;
(2) A policy statement that reflects this interpretation and provides the guidelines that are required to institute proper design methods;
(3) Design methods and construction practices that are representative of the state-of-art and the fully consider hydrologic changes that go along with the urbanization process.”
He suggests that alternatives like grass-lined swales, rooftops detention, and porous pavements are SWM measures that better represents the natural storage found in predevelopment conditions, both in volume and temporal characteristics. A second alternative is to make change in the basin designs, although that may cause conflicts between flood control and pollution/sediment control, for example.
McCuen, R.H. (1979) “Downstream effects of Stormwater Management Basins” Journal of the Hydraulics Division, Vol. 105, No. 11.
Prof. McCuen addresses the problem of hydrological alteration due urbanization. The use of impervious materials decreases natural storage, increasing peak rates, decreasing time-to-peak, and increasing the volumes of runoff and sediments. To mitigate these detrimental effects storm water management (SWM) is required. However, according to the paper, many SWM strategies fail in mitigate the urbanization effects because “they only attempt to limit peak flow rates and sediments volumes” to predevelopment conditions. This is in general attempted by the use of detention basins. This strategy, however, is not sufficient. This problem lead to main question of the article: “Are SWM basins effectively meeting the intent of stormwater management?”
“Urban development causes a decrease in natural storage, including infiltration, interception, and depression storage”. SWM basin is an attempt to restore the loss of natural storage in the watershed. This volume can be artificially restored, but the timing characteristics introduced by detention basins are significantly different from the predevelopment conditions. In natural conditions, the major part of the storage volume is filled during the storm event, while in a detention facility this storage is rapidly filled during the risen portion of the hydrograph.
A second effect introduced by detention basin is that the increased volume of direct runoff is released at a higher rate when compared to natural storage. This cause increase in the duration of bankfull flows.
Due the reasons explained so far, the work examines the hypothesis “that, when changes in both timing characteristics and flow volumes are not corrected by SWM, they may have an adverse effect on flow conditions downstream from the SWM basin.”
A 2.12 square mile watershed was simulated using the Soil Conservation Service TR-20 hydrological model. The predominant soils are silt loams, characterized as deep, well-drained, and moderately erodible. Simulations indicate that peak flow increases from 11.7 to 59.3 cfs (factor of five!!!) from pre-development to urbanized condition of one catchment for the 10 yr-storm. In terms of volume, there is an increase of 100%. The time-to-peak decrease 7 minutes. Introducing a detention basin, the peak flow is reduced to 13.08 cfs, but the time-to-peak is 36 minutes greater than that which existed prior to development. A compared analysis is done for the 100 yr-storm. The effects are the same, but the differences are much lower.
Looking further downstream in the watershed, the computation indicates that for the 100 yr-storm the SWM basin increases the peak flow compared to the post development with no control. This is true for approximately 5 miles downstream the storage facility. The reason for that is changes in timing characteristics affects the runoff conditions downstream.
After the hydrological analysis, the author has approached the bedload transport. Although its is recognized the difficulty in estimating bedload discharges, a theoretical model can be used to assess different scenarios and trace comparisons between them. A model developed by Goncharov was used to predict the sediment discharge as a function of mean flow velocity, mean sediment diameter, the critical velocity of sediment, and the mean depth. The previous discussed scenarios were evaluated to generate estimative of sediment yield. The results indicate that even with the SWM basin there is a significant increase in total volume of sediment. This is due the sustain flow introduced by the basin, which induce higher velocities than the critical velocity over a longer period.
The author finalizes the article with some considerations related with SWM policies and designs. He considers three aspects important:
(1) “The recognition of a comprehensive interpretation to the definition of the intent of SWM;
(2) A policy statement that reflects this interpretation and provides the guidelines that are required to institute proper design methods;
(3) Design methods and construction practices that are representative of the state-of-art and the fully consider hydrologic changes that go along with the urbanization process.”
He suggests that alternatives like grass-lined swales, rooftops detention, and porous pavements are SWM measures that better represents the natural storage found in predevelopment conditions, both in volume and temporal characteristics. A second alternative is to make change in the basin designs, although that may cause conflicts between flood control and pollution/sediment control, for example.
Assinar:
Postagens (Atom)
