"Interest in e-government, both in industry and in academies, has grown rapidly over the past decade. This book provides helpful examples from practitioners and managers involving real-life applications; academics and researchers contribute theoretical insights"--Provided by publisher.

Dynamic environments abound, encompassing many real-world problems in fields as diverse as finance, engineering, biology and business. A vibrant research literature has emerged which takes inspiration from evolutionary processes to develop problem-solvers for these environments. 'Foundations in Grammatical Evolution for Dynamic Environments' is a cutting edge volume illustrating current state of the art in applying grammar-based evolutionary computation to solve real-world problems in dynamic environments. The book provides a clear introduction to dynamic environments and the types of change that can occur. This is followed by a detailed description of evolutionary computation, concentrating on the powerful Grammatical Evolution methodology. It continues by addressing fundamental issues facing all Evolutionary Algorithms in dynamic problems, such as how to adapt and generate constants, how to enhance evolvability and maintain diversity. Finally, the developed methods are illustrated with application to the real-world dynamic problem of trading on financial time-series. The book was written to be accessible to a wide audience and should be of interest to practitioners, academics and students, who are seeking to apply grammar-based evolutionary algorithms to solve problems in dynamic environments. 'Foundations in Grammatical Evolution for Dynamic Environments' is the second book dedicated to the topic of Grammatical Evolution.

Interest in constrained optimization originated with the simple linear pro gramming model since it was practical and perhaps the only computationally tractable model at the time. Constrained linear optimization models were soon adopted in numerous application areas and are perhaps the most widely used mathematical models in operations research and management science at the time of this writing. Modelers have, however, found the assumption of linearity to be overly restrictive in expressing the real-world phenomena and problems in economics, finance, business, communication, engineering design, computational biology, and other areas that frequently demand the use of nonlinear expressions and discrete variables in optimization models. Both of these extensions of the linear programming model are NP-hard, thus representing very challenging problems. On the brighter side, recent advances in algorithmic and computing technology make it possible to re visit these problems with the hope of solving practically relevant problems in reasonable amounts of computational time. Initial attempts at solving nonlinear programs concentrated on the de velopment of local optimization methods guaranteeing globality under the assumption of convexity. On the other hand, the integer programming liter ature has concentrated on the development of methods that ensure global optima. The aim of this book is to marry the advancements in solving nonlinear and integer programming models and to develop new results in the more general framework of mixed-integer nonlinear programs (MINLPs) with the goal of devising practically efficient global optimization algorithms for MINLPs.

First, I would like to thank my principal supervisor Dr Qiang Shen for all his help, advice and friendship throughout. Many thanks also to my second supervisor Dr Peter Jarvis for his enthusiasm, help and friendship. I would also like to thank the other members of the Approximate and Qualitative Reasoning group at Edinburgh who have also helped and inspired me. This project has been funded by an EPSRC studentship, award num ber 97305803. I would like, therefore, to extend my gratitude to EPSRC for supporting this work. Many thanks to the staff at Edinburgh University for all their help and support and for promptly fixing any technical problems that I have had . My whole family have been both encouraging and supportive throughout the completion of this book, for which I am forever indebted. York, April 2003 Ian Miguel Contents List of Figures XV 1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1. 1 Solving Classical CSPs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1. 2 Applicat ions of Classical CSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1. 3 Limitations of Classical CSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1. 3. 1 Flexible CSP 6 1. 3. 2 Dynamic CSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1. 4 Dynamic Flexible CSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1. 5 Flexible Planning: a DFCSP Application . . . . . . . . . . . . . . . . . . 8 1. 6 Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1. 7 Contributions and their Significance 11 2 The Constraint Satisfaction Problem 13 2. 1 Constraints and Constraint Graphs . . . . . . . . . . . . . . . . . . . . . . . 13 2. 2 Tree Search Solution Techniques for Classical CSP . . . . . . . . . . 16 2. 2. 1 Backtrack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2. 2. 2 Backjumping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2. 2. 3 Conflict-Directed Backjumping . . . . . . . . . . . . . . . . . . . . . 19 2. 2. 4 Backmarking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .