Parallel Problem Solving From Nature, PPSN XI : 11th International Conference, Krakov, Poland, September 11-15, 2010, Proceedings, Part II

This book constitutes the refereed proceedings of the 11th International Conference on Parallel Problem Solving from Nature - PPSN XI, held in Kraków, Poland, in September 2010. The 131 revised full papers were carefully reviewed and selected from 232 submissions. The conference covers a wide range of topics, from evolutionary computation to swarm intelligence, from bio-inspired computing to real world applications. Machine learning and mathematical games supported by evolutionary algorithms as well as memetic, agent-oriented systems are also represented. Cover ......Page 1 Preface......Page 6 Organization......Page 8 Table of Contents – Part II......Page 12 Table of Contents – Part I......Page 18 Introduction......Page 24 Multi-Objective Particle Swarm Optimisation......Page 25 The SDMOPSO Approach......Page 26 Experiments and Results......Page 29 Discussion and Conclusions......Page 31 References......Page 32 Introduction......Page 34 Concept......Page 35 Adaptive -Ranking Strategy A RE......Page 36 Method of Analysis......Page 37 Preparation......Page 38 Effects of Individual Components......Page 40 Effects of the Hybrid Strategy......Page 41 References......Page 43 Introduction......Page 44 Previous Related Work......Page 45 Our Proposed Approach......Page 46 Results and Discussion......Page 49 Conclusions and Future Work......Page 52 References......Page 53 Introduction and Motivation......Page 54 Multi-Objective Optimization (MOO)......Page 55 Dynamic Lexicographic Approach......Page 56 Particle Swarm Optimization (PSO)......Page 57 Experiments......Page 58 Results......Page 59 Conclusions......Page 62 References......Page 63 Introduction......Page 64 Use Case......Page 65 Algorithm Overview......Page 66 Construction of Secure Protocol......Page 67 Operations......Page 68 Evaluation......Page 70 Conclusions......Page 72 References......Page 73 Introduction......Page 74 The VRP with Time Windows......Page 75 Multi-Objective EA for VRPTW......Page 77 Minimization of the Delivery Time......Page 79 Comparison with Previous Studies......Page 80 Comparison with NSGA-II......Page 81 Conclusions......Page 82 References......Page 83 Introduction......Page 84 Particle Swarm Optimization......Page 85 Speculative Evaluation in PSO......Page 86 Using All Speculative Evaluations......Page 89 Results......Page 90 Conclusions......Page 92 References......Page 93 Introduction......Page 94 Novelty Evaluation and World Model Adaptation......Page 96 Characteristics of the Novelty Guided Evolution Strategy......Page 98 Comparative Study on a High Dimensional Test Function......Page 100 Discussion......Page 102 References......Page 103 Introduction......Page 104 The Metaheuristic......Page 105 The CGS-TSP Algorithm......Page 107 Applying Local Search to CGS-TSP......Page 108 Experimental Setup......Page 109 Experimental Results......Page 110 References......Page 113 Introduction......Page 114 Results on Test Problems with a Single Pareto Region ($m$ = 1)......Page 116 Results on Test Problems with Multiple Pareto Regions $(m > 1)$......Page 120 References......Page 122 Introduction......Page 124 MOPSO......Page 125 Desirability Functions and Indices......Page 126 DF-MOPSO......Page 127 Results......Page 129 References......Page 132 Introduction......Page 134 GPGPU......Page 135 Description of the Algorithm......Page 136 Experimental Results......Page 139 References......Page 142 Test Functions......Page 143 Introduction......Page 144 Overview......Page 145 Indicator Calculation......Page 146 Directional-biased Search:......Page 147 Algorithm of hIDEA:......Page 149 Evaluation Criteria......Page 150 Experimental Result......Page 151 Discussion......Page 152 References......Page 153 Introduction......Page 154 Theoretical Results......Page 155 A NSGA-II Framework for Incorporating Trade-Offs......Page 157 Simulation Results......Page 159 References......Page 163 Introduction......Page 164 Problem Statement......Page 165 Methodology......Page 167 Results......Page 168 References......Page 172 Introduction and Motivation......Page 174 Strategy to Account for Changes of Variables......Page 175 $MJ$ Model......Page 176 $NK$ Landscapes......Page 177 Experimental Study......Page 178 Results......Page 179 References......Page 183 Introduction......Page 184 Commitment Composite ERCs......Page 185 Online Purchasing Strategies......Page 186 Just-in-Time Strategy......Page 187 Just-in-Time Strategy with Repairing......Page 188 Experimental Study......Page 190 References......Page 193 Introduction......Page 194 Parallel Artificial Immune System......Page 195 Optimization of Composites......Page 197 Identification of Composites......Page 198 Numerical Examples: Optimization......Page 199 Numerical Examples: Identification......Page 201 Final Conclusions......Page 202 References......Page 203 Introduction......Page 204 The GP Approach......Page 205 References......Page 210 Appendix......Page 211 Introduction......Page 212 Related Work......Page 213 Variable Neighborhood Search (VNS) and Its Application to the 1-PDP......Page 214 The AVNS-SA Heuristic......Page 215 Experimental Results......Page 217 Summary and Future Work......Page 220 References......Page 221 Introduction......Page 222 The Dinosaur Hypothesis......Page 223 GP Algorithm......Page 224 Experimental Designs......Page 225 Testing Methodology......Page 226 Statement P1......Page 228 Statement P2......Page 229 References......Page 231 Introduction......Page 232 The Pole Balancing Problem......Page 233 Gene Type......Page 234 Fractal Protein Chemistry......Page 235 Experiments......Page 236 FGRN Set-Up......Page 237 Results......Page 238 References......Page 240 Introduction......Page 242 Problem Description......Page 243 Variable Neighborhood Descent......Page 244 Computational Experiments......Page 246 References......Page 250 Introduction......Page 252 Terminal Assignment Problem......Page 253 The Proposed DDE Algorithm......Page 254 Results......Page 258 Conclusions......Page 260 References......Page 261 Introduction......Page 263 Related Work......Page 265 Economic Perspective......Page 266 Optimization......Page 267 Expected Properties......Page 268 Evaluation......Page 269 References......Page 271 Introduction......Page 273 A Review on Solution Techniques......Page 274 Schedule Classes......Page 275 A Geometric Framework for DE......Page 276 GDE for the JSSP......Page 277 Standard Random-Keys DE......Page 278 Results......Page 279 References......Page 281 Introduction......Page 283 A Robust Variant of Pareto Dominance......Page 284 Preliminary Empirical Evaluation......Page 285 Conclusions......Page 291 References......Page 292 Introduction......Page 293 Reinforcement Learning for Arm Controllers......Page 294 Indirect Encoding and HyperNEAT......Page 295 Scalable Neurocontroller for an Octopus Arm......Page 296 Substrate Architecture......Page 297 Experiment......Page 298 Results......Page 299 Conclusions......Page 301 References......Page 302 Introduction......Page 303 Problem Formulation......Page 304 The Basic EA......Page 305 The EVL and the Mutation Operator......Page 307 Parameter Selection......Page 308 Experimental Results......Page 309 Summary......Page 311 References......Page 312 Introduction......Page 313 mEDEA: A Minimal EDEA Algorithm......Page 314 The Problem: Surviving in a Dynamic Unknown Environment......Page 316 Experimental Settings......Page 317 Results and Analysis......Page 319 Conclusions and Perspectives......Page 321 References......Page 322 Introduction......Page 323 Discovering Decision Variable Interactions......Page 324 Cooperative Coevolution with Variable Interaction Learning......Page 326 Learning Stage......Page 327 Optimization Stage......Page 328 Benchmark Functions and Learned Groups......Page 329 Comparison with Other CC-Based Algorithms and JADE......Page 330 Conclusions and Future Work......Page 331 References......Page 332 Introduction......Page 333 Digital Media Libraries......Page 334 Evolutionary Visualization Techniques......Page 335 Individuals, Experiments, and Groups......Page 336 Built-in Visualization Techniques......Page 337 Plugins......Page 338 Example Scenario......Page 339 Summary and Future Work......Page 341 References......Page 342 Introduction......Page 343 Differential Evolution Algorithms......Page 344 Computational Experiments......Page 347 Results......Page 348 Conclusions and Future Work......Page 351 References......Page 352 Introduction......Page 354 Heading Alignment Behavior......Page 356 Motion Control......Page 357 Metrics......Page 358 Results in Stationary Environments......Page 359 Results in Non-stationary Environments......Page 360 Conclusions and Future Work......Page 361 References......Page 362 Introduction......Page 364 Methodology......Page 366 Experiments and Results......Page 370 Conclusions and Future Work......Page 371 References......Page 372 Introduction......Page 374 The Parallel Metaheuristics Framework......Page 375 Evolutionary Algorithms and the Reduce Operator......Page 378 Case Study: The Simple GA in PMF......Page 380 Conclusions and Future Work......Page 382 References......Page 383 Introduction......Page 384 Problem Description......Page 385 Recent Work......Page 386 Parallel Evolutionary Algorithm Using MapReduce......Page 387 Implementation Details......Page 388 Experimental Results and Statistical Tests......Page 390 Conclusions and Future Work......Page 392 References......Page 393 Introduction......Page 394 Standard ACO......Page 395 Population-Based ACO......Page 396 Incorporating Immigrants Schemes to ACO Algorithms......Page 397 Elitism-Based Immigrants ACO......Page 398 Experimental Setup......Page 399 Experimental Results......Page 401 Conclusions......Page 402 References......Page 403 Introduction......Page 404 Cellular Automata Applied in Cryptography......Page 405 Variable Length Encryption Method......Page 406 Experiments......Page 407 Final Remarks......Page 411 References......Page 413 Introduction......Page 414 Previous Work......Page 415 Suboptimal Edges......Page 416 Variable Neighborhood Descent......Page 417 Ant Colony Optimization......Page 418 Depositing Pheromones......Page 419 Experimental Results......Page 420 Conclusion......Page 422 References......Page 423 Introduction......Page 424 Related Work......Page 425 Adaptive Modularization in a Multiagent Environment......Page 426 Creating Modules......Page 427 Learning the Group Behaviour......Page 428 Agent-Based Model of the MAPK Signaling Pathway......Page 429 References......Page 432 Introduction......Page 434 Differential Evolution Algorithm......Page 435 Experiments and Results......Page 437 References......Page 442 Introduction......Page 444 Game Strategy......Page 446 Entropy-Driven Approaches......Page 448 Experimental Results......Page 450 Conclusions and Future Work......Page 452 References......Page 453 Introduction......Page 455 Centipede Game......Page 456 Equilibria and Their Generative Relations......Page 458 Generative Relation for Quasi Pareto Equilibrium......Page 459 Generative Relation for Joint Nash-Pareto Equilibrium......Page 460 Generative Relation for Fuzzy Nash-Pareto Equilibrium......Page 461 Fuzzy Nash-Pareto Equilibrium and the Centipede Game......Page 462 Conclusion......Page 463 References......Page 464 Introduction......Page 465 Characteristics......Page 466 Individual Representation......Page 467 Herdy Evolution Strategy......Page 468 Thistlethwaite Evolution Strategy......Page 469 Herdy Evolution Strategy......Page 471 Thistlethwaite Evolution Strategy......Page 473 References......Page 474 Introduction......Page 475 The EA Method and the Experimental Setup......Page 477 Statistical Study and Results Obtained......Page 479 Conclusions and Work in Progress......Page 482 References......Page 483 Introduction......Page 485 Network Crossover......Page 486 Test Problems......Page 487 Experimental Results......Page 489 Summary and Conclusions......Page 491 References......Page 493 Introduction......Page 495 Related Work......Page 496 Phenotypic Diversity......Page 497 Measuring Diversity......Page 498 Preserving Diversity......Page 500 References......Page 503 Background......Page 505 GP Setup......Page 507 The Generation of Permutations......Page 508 The Calculation of Fitness Values......Page 510 Experimental Results......Page 511 References......Page 513 Introduction......Page 515 Preliminaries......Page 516 Co-solvability......Page 517 Properties of Co-solvability......Page 518 The Experiment......Page 520 Conclusion......Page 523 References......Page 524 Introduction......Page 525 Shared Grammar Evolution......Page 526 Shared Representation......Page 527 Memoization......Page 528 Implementation......Page 529 Experiment......Page 530 Results......Page 531 Conclusion......Page 533 References......Page 534 Introduction......Page 535 Model Description......Page 536 Discussion of Results......Page 538 Conclusions......Page 543 References......Page 544 Introduction......Page 546 Overview of the System......Page 547 Evolution of the Update Strategies......Page 548 Validation and Analysis of the Evolved Update Strategies......Page 549 Using Different Function and Terminal Sets......Page 551 Generalization to Other TSP Instances......Page 553 Discussion......Page 554 References......Page 555 Introduction......Page 556 Semantics in Genetic Programming......Page 557 Semantic Similarity Based Crossover......Page 558 Syntactic Similarity-Based Crossover......Page 559 Experimental Settings......Page 560 Performance......Page 561 Ability to Generalise......Page 562 Conclusion and Future Work......Page 563 References......Page 564 The Layered Learning Method and Its Application to Generation of Evaluation Functions for the Game of Checkers......Page 566 Method Variations......Page 567 Neural Networks Architecture......Page 569 RPROP Training......Page 570 Evaluators Comparison......Page 571 Training Progress Analysis......Page 573 Conclusions......Page 574 References......Page 575 Author Index ......Page 576