Normal view MARC view

How to solve it: modern heuristics

Author: Michalewicz, Zbigniew ; Fogel, David B.Publisher: Springer, 2004.Edition: 2nd revised and extended ed.Language: EnglishDescription: 554 p. : Graphs ; 24 cm.ISBN: 3540224947Type of document: BookBibliography/Index: Includes bibliographical references and index
Tags: No tags from this library for this title. Log in to add tags.
Item type Current location Collection Call number Status Date due Barcode Item holds
Book Europe Campus
Main Collection
Print QA402.5 .M53 2004
(Browse shelf)
001174469
Available 001174469
Total holds: 0

Includes bibliographical references and index

Digitized

How to Solve It: Modern Heuristics Table of Contents Introduction ............................................................................................... I What Are the Ages of My Three Sons? ......................................................... 1 9 1 Why Are Some Problems Difficult to Solve? ................................................ 11 1.1 The size of the search space .............................................................. 1.2 Modeling the problem ....................................................................... 1.3 Change over time ............................................................................. 1.4 Constraints ...................................................................................... 1.5 The problem of proving things ........................................................... 1.6 Your chance for glory ........................................................................ 1.7 Summary ......................................................................................... 11 16 19 21 24 26 29 II How Important Is a Model? ....................................................................... 31 2 Basic Concepts ........................................................................................ 35 2.1 Representation ................................................................................. 35 2.2 The objective .................................................................................... 36 2.3 The evaluation function .................................................................... 37 2.4 Defining a search problem ................................................................. 39 2.5 Neighborhoods and local optima......................................................... 40 2.6 Hill-climbing methods ....................................................................... 43 2.7 Can you sink this trick shot?.............................................................. 4 5 2.8 Summary ......................................................................................... 48 III What Are the Prices in 7-11? .................................................................... 49 3 Traditional Methods Part 1 ............................................................... 3.1 Exhaustive search ............................................................................ 3.1.1 Enumerating the SAT ............................................................. 3.1.2 Enumerating the TSP ............................................................. 3.1.3 Enumerating the NLP ............................................................. 3.2 Local search ..................................................................................... 3.2.1 Local search and the SAT ...................................................... 3.2.2 Local search and the TSP ...................................................... 55 58 59 61 62 64 65 66 XIV Table of Contents 3.2.3 Local search and the NLP ..................................................... 69 3.3 Linear programming: The simplex method ....................................... 76 3.4 Summary ...................................................................................... 80 IV What Are the Numbers? ........................................................................ 83 4 Traditional Methods Part 2 ..................................................................... 87 4.1 Greedy algorithms .......................................................................... 87 4.1.1 Greedy algorithms and the SAT ............................................. 87 4.1.2 Greedy algorithms and the TSP ............................................. 89 4.1.3 Greedy algorithms and the NLP ............................................. 90 4.2 Divide and conquer ........................................................................ 90 4.3 Dynamic programming ................................................................... 93 4.4 Branch and bound ....................................................................... 101 4.5 A* algorithm ................................................................................ 105 4.6 Summary .................................................................................... 109 V What's the Color of the Bear? ................................................................ 111 5 Escaping Local Optima ......................................................................... 115 5.1 Simulated annealing ..................................................................... 117 5.2 Tabu search ................................................................................. 125 5.3 Summary .................................................................................... 134 VI How Good Is Your Intuition? ................................................................ 135 6 An Evolutionary Approach .................................................................... 6.1 Evolutionary approach for the SAT ................................................ 6.2 Evolutionary approach for the TSP ................................................ 6.3 Evolutionary approach for the NLP ................................................ 6.4 Summary .................................................................................... 139 142 145 149 151 VII One of These Things Is Not Like the Others .......................................... 157 7 Designing Evolutionary Algorithms ........................................................ 7.1 Representation ............................................................................. 7.1.1 Fixed-length vectors of symbols ........................................... 7.1.2 Permutations ..................................................................... 7.1.3 Finite state machines ......................................................... 7.1.4 Symbolic expressions ......................................................... 7.2 Evaluation function ...................................................................... 7.3 Variation operators ....................................................................... 7.3.1 Fixed-length vectors of symbols ........................................... 7.3.2 Permutations ..................................................................... 7.3.3 Finite state machines ......................................................... 7.3.4 Symbolic expressions ......................................................... 7.4 Selection ...................................................................................... 161 165 166 167 168 168 169 172 173 174 176 177 179 Table of Contents XV 7.5 Initialization ................................................................................... 181 7.6 Summary ...................................................................................... 183 VIII What Is the Shortest Way? ................................................................... 185 8 The Traveling Salesman Problem ............................................................. 189 8.1 In search of good variation operators ................................................ 8.2 Incorporating local search methods .................................................. 8.3 Other possibilities ........................................................................... 8.3.1 Edge assembly crossover ....................................................... 8.3.2 Inver-over operator ............................................................... 8.4 Summary ...................................................................................... 191 214 217 217 220 223 IX Who Owns the Zebra? ........................................................................... 225 9 Constraint-Handling Techniques .............................................................. 231 9.1 General considerations .................................................................... 232 9.1.1 Designing eval f .................................................................................................................................... 234 9.1.2 Design of evaln ...................................................................................................................................... 236 9.1.3 Relationship between eval f and evaln ......................................................................... 237 9.1.4 Rejecting infeasible solutions ................................................. 239 9.1.5 Repairing infeasible individuals .............................................. 239 9.1.6 Replacing individuals by their repaired versions ....................... 240 9.1.7 Penalizing infeasible individuals ............................................. 240 9.1.8 Maintaining a feasible population using special representations and variation operators ........................................... 241 9.1.9 Using decoders ..................................................................... 242 9.1.10 Separating individuals and constraints ................................. 243 9.1.11 Exploring boundaries between feasible and infeasible parts of the search space ............................................................. 243 9.1.12 Finding feasible solutions .................................................... 244 9.2 Numerical optimization ................................................................... 245 9.2.1 Methods based on preserving the feasibility of solutions ........... 246 9.2.2 Methods based on penalty functions ....................................... 249 9.2.3 Methods based on a search for feasible solutions ..................... 257 9.2.4 Methods based on decoders ................................................... 264 9.2.5 Hybrid methods ................................................................... 266 9.3 Summary ...................................................................................... 268 X Can You Tune to the Problem? ................................................................ 271 10 Tuning the Algorithm to the Problem ...................................................... 277 10.1 Parameter control in evolutionary algorithms ................................... 10.2 Illustrating the case with an NLP .................................................... 10.3 Taxonomy of control techniques ..................................................... 10.4 The possibilities for parameter control ............................................. 277 282 284 288 XVI Table of Contents 10.4.1 Representation .................................................................. 10.4.2 Evaluation function ........................................................... 10.4.3 Mutation operators and their probabilities ............................ 10.4.4 Crossover operators and their probabilities ........................... 10.4.5 Parent selection ................................................................. 10.4.6 Population ........................................................................ 10.5 Combining forms of parameter control ........................................... 10.6 Summary .................................................................................... 288 289 290 293 295 295 296 298 XI Can You Mate in Two Moves? ................................................................ 303 11 Time-Varying Environments and Noise .................................................. 11.1 Life presents a dynamic landscape ................................................. 11.2 The real world is noisy .................................................................. 11.2.1 Ensuring diversity ............................................................. 11.3 Modeling of ship trajectory ............................................................ 11.4 Summary .................................................................................... 307 307 317 321 325 329 XII Day of the Week of January 1st ............................................................ 335 12 Neural Networks .................................................................................. 339 12.1 Threshold neurons and linear discriminant functions ...................... 340 12.2 Back propagation for feed forward multilayer perceptrons . . . ........... 345 12.3 Training and testing ..................................................................... 350 12.4 Recurrent networks and extended architectures .............................. 352 12.4.1 Standard recurrent network ............................................... 352 12.4.2 Hopfield network ............................................................... 352 12.4.3 Boltzmann machine ........................................................... 354 12.4.4 Network of multiple interacting programs.............................. 354 12.5 Clustering with competitive networks ............................................. 356 12.6 Using neural networks to solve the TSP........................................... 358 12.7 Evolving neural networks .............................................................. 360 12.8 Summary .................................................................................... 361 XIII What Was the Length of the Rope? ....................................................... 363 13 Fuzzy Systems .................................................................................... 367 13.1 Fuzzy sets ................................................................................... 13.2 Fuzzy sets and probability measures .............................................. 13.3 Fuzzy set operations ..................................................................... 13.4 Fuzzy relationships ...................................................................... 13.5 Designing a fuzzy controller .......................................................... 13.6 Fuzzy clustering .......................................................................... 13.7 Fuzzy neural networks ................................................................. 13.8 A fuzzy TSP.................................................................................. 13.9 Evolving fuzzy systems ................................................................. 368 368 369 372 375 380 382 385 387 Table of Contents I 13.10 Summary ................................................................................. 388 XIV Everything Depends on Something Else ............................................... 389 14 Coevolutionary Systems ...................................................................... 397 14.1 Playing a game ........................................................................... 399 14.2 Learning to play checkers ............................................................ 400 14.3 Optimization through competing populations.................................. 403 14.4 Another example with a game ...................................................... 408 14.5 Artificial life ................................................................................ 411 14.6 Games of cooperation and competition .......................................... 412 14.7 Modeling intelligent agents ........................................................... 418 14.8 Issues in coevolution ................................................................... 420 14.9 An example of cooperative coevolution on the TSP .......................... 424 14.10 Summary ................................................................................. 430 XV Who's Taller? ..................................................................................... 431 15 Multicriteria Decision-Making .............................................................. 15.1 Single numeric approach ............................................................. 15.1.1 The Valuated State Space approach .................................... 15.1.2 Fuzzy multicriteria decision-making ................................... 15.1.3 Summary ........................................................................ 15.2 Evolutionary multiobjective optimization approach ......................... 15.2.1 Brief history ..................................................................... 15.2.2 Evolutionary algorithm for multiobjective NLP ...................... 15.3 Summary ................................................................................... 435 440 443 449 450 451 452 458 462 XVI Do You Like Simple Solutions? ........................................................... 465 16 Hybrid Systems .................................................................................. 471 16.1 Summary ................................................................................... 480 17 Summary .......................................................................................... 483 Appendix A: Probability and Statistics ....................................................... A.1 Basic concepts of probability .......................................................... A.2 Random variables ......................................................................... A.2.1 Discrete random variables ................................................... A.2.2 Continuous random variables .............................................. A.3 Descriptive statistics of random variables ........................................ A.4 Limit theorems and inequalities ..................................................... A.5 Adding random variables ............................................................... A.6 Generating random numbers on a computer ................................... A.7 Estimation ................................................................................... A.8 Statistical hypothesis testing .......................................................... A.9 Linear regression .......................................................................... 495 495 497 497 500 502 505 506 507 508 511 512 XVIII Table of Contents A.10 Summary .................................................................................. 514 Appendix B: Problems and Projects ........................................................ 515 B.1 Trying some practical problems ................................................... 517 B.2 Reporting computational experiments with heuristic methods . .... 522 References .............................................................................................. 525 Index ...................................................................................................... 551

There are no comments for this item.

Log in to your account to post a comment.
Koha 18.11 - INSEAD Catalogue
Home | Contact Us | What's Koha?