Parallel Problem Solving from Nature - PPSN XV

Name: Parallel Problem Solving from Nature - PPSN XV | 15th International Conference, Coimbra, Portugal, September 8-12, 2018, Proceedings, Part II
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

15th International Conference, Coimbra, Portugal, September 8-12, 2018, Proceedings, Part II

Anne Auger Carlos M. Fonseca Nuno Lourenço Penousal Machado Luís Paquete Darrell Whitley(Herausgeber*in)

Springer (Verlag)

Erschienen am 30. August 2018

XXI, 501 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-319-99259-4 (ISBN)

53,49 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

Intro
Preface
Organization
Contents - Part II
Contents - Part I
Runtime Analysis and Approximation Results
A General Dichotomy of Evolutionary Algorithms on Monotone Functions
1 Introduction
2 Preliminaries and Definitions
3 Results
4 Conclusions
References
Artificial Immune Systems Can Find Arbitrarily Good Approximations for the NP-Hard Partition Problem
1 Introduction
2 Preliminaries
3 Generalised Worst-Case Instance
3.1 Hypermutations
3.2 Ageing
4 (1+) Approximation Ratios
4.1 Hypermutations
4.2 Ageing
5 Conclusion
References
A Simple Proof for the Usefulness of Crossover in Black-Box Optimization
1 Introduction
1.1 Selected Theoretical Results on the Benefits of Crossover
1.2 Our Results
2 The Greedy (+1) GA
2.1 The Original Greedy (+1) GA
2.2 Standard Bit Mutation: Theory vs. Practice
2.3 The Modified Greedy (+1) GA
3 Theoretical Investigation
4 Empirical Evaluation
5 Conclusions
References
Destructiveness of Lexicographic Parsimony Pressure and Alleviation by a Concatenation Crossover in Genetic Programming
1 Introduction
2 Preliminaries
2.1 Crossover
2.2 Terminology
3 (1+1) GP with Bloat Control
4 (1+1) GP Without Bloat Control
5 Concatenation Crossover GP
6 Experiments
7 Conclusion
References
Exploration and Exploitation Without Mutation: Solving the Jump Function in (n) Time
1 Introduction
2 Background and Basics
2.1 Jansen's and Wegener's Classic Result
3 Hybrid Genetic Algorithms
3.1 Deterministic Crossover: 3-Parent Voting Crossover
3.2 The Probability of Success (POS) for 3-Parent Voting Crossover
3.3 A Lower Bound on the Probabilities
4 Probabilities and Populations
5 Other Crossover Operators
6 Conclusions
References
Fast Artificial Immune Systems
1 Introduction
2 Preliminaries
3 Fast Hypermutations
4 Fast Opt-IA
5 Conclusion
References
First-Hitting Times for Finite State Spaces
1 Introduction
2 Setting
2.1 Stochastic Tools
3 General First-Hitting Times
4 Limit Distributions and Mixing Times
References
First-Hitting Times Under Additive Drift
1 Drift Theory
2 Preliminaries
2.1 Martingale Theorems
3 Additive Drift
3.1 Upper Bounds
3.2 Lower Bound
4 Variable Drift
5 Multiplicative Drift
References
Level-Based Analysis of the Population-Based Incremental Learning Algorithm
1 Introduction
2 Preliminaries
2.1 Two Problems
2.2 Population-Based Incremental Learning
2.3 Level-Based Analysis
2.4 Other Tools
3 Runtime Analysis of the PBIL on LeadingOnes
4 Runtime Analysis of the PBIL on BinVal
5 Conclusions
References
Precise Runtime Analysis for Plateaus
1 Introduction
2 Problem Statement
3 Preliminaries and Notation
4 The Spectrum of the Transition Matrix
5 Runtime Analysis
6 Corollaries
7 Conclusion
References
Ring Migration Topology Helps Bypassing Local Optima
1 Introduction
2 Algorithms
3 Fitness Functions
3.1 Composite Fitness Function
3.2 Run Time of LeadingOnes with k-block f
4 No Migration
4.1 The (1+1) EA
4.2 Independent Runs
5 Complete Topology
6 Ring Topology
7 Conclusion
References
Runtime Analysis of Evolutionary Algorithms for the Knapsack Problem with Favorably Correlated Weights
1 Introduction
2 Algorithms and Problems
2.1 Single-Objective Optimization
2.2 Multi-objective Optimization
3 Structure of the Objective Space
4 Runtime Analysis of (1+1) EA
5 Runtime Analysis of GSEMO
6 Conclusions
References
Theoretical Analysis of Lexicase Selection in Multi-objective Optimization
1 Introduction
2 Background
3 Algorithms, Problems, and Definitions
4 Analysis
5 Experimental Supplements
6 Conclusions
References
Towards a Running Time Analysis of the (1+1)-EA for OneMax and LeadingOnes Under General Bit-Wise Noise
1 Introduction
2 Preliminaries
2.1 OneMax and LeadingOnes
2.2 Bit-Wise Noise
2.3 (1+1)-EA
2.4 Analysis Tools
3 The OneMax Problem
4 The LeadingOnes Problem
5 Conclusion
References
Fitness Landscape Modeling and Analysis
A Surrogate Model Based on Walsh Decomposition for Pseudo-Boolean Functions
1 Introduction
2 Walsh Functions: Background and Related Work
2.1 Walsh Functions Basics and Evolutionary Computation
2.2 Surrogate Models for Combinatorial Optimization
3 Surrogate Model Based on Walsh Functions
4 Experimental Analysis
4.1 Experimental Setup and Methodology
4.2 Training with CG Versus LARS
4.3 Walsh Versus Kriging
4.4 Impact of the Walsh Expansion Order
5 Conclusions
References
Bridging Elementary Landscapes and a Geometric Theory of Evolutionary Algorithms: First Steps
1 Introduction
2 Fitness Landscapes
3 Geometric Framework
4 Elementary Landscapes Theory
5 Main Results
6 Discrete Nodal Domains for Uniform Recombination in Boolean Spaces with Hamming Distance: Examples
7 Conclusions
References
Empirical Analysis of Diversity-Preserving Mechanisms on Example Landscapes for Multimodal Optimisation
1 Introduction
2 Diversity Mechanisms and Previous Results for TwoMax
3 Jansen-Zarges Multimodal Function Classes
4 Experimental Analysis
4.1 Finding Peaks of Equal Height
4.2 Finding Peaks with Different Height
4.3 Escaping from Local Optima
5 Conclusions
References
Linear Combination of Distance Measures for Surrogate Models in Genetic Programming
1 Introduction
2 Related Work
3 A Test Case for SMBO-GP: Bi-level Symbolic Regression
3.1 Problem Definition
3.2 Surrogate Model-Based Optimization
4 Kernels for Bi-level Symbolic Regression
4.1 Phenotypic Distance
4.2 Tree Edit Distance
4.3 Structural Hamming Distance
4.4 Comparison and Linear Combination of Distances
5 Case Study
5.1 Algorithm Tuning
5.2 Analysis and Discussion
6 Conclusion and Outlook
References
On Pareto Local Optimal Solutions Networks
1 Introduction
2 Multi-objective Optimization and mnk-Landscapes
3 Pareto Local Optimal Solutions Network
3.1 Definition and Visual Inspection of PLOS-net
3.2 Definition of PLOS-net Features
3.3 Exploratory Analysis
4 PLOS-net Features vs. Search Performance
4.1 Algorithms and Search Performance
4.2 Effect of PLOS-net Features on Search Performance
4.3 Importance of PLOS-net Features on Search Performance
5 Conclusions
References
Perturbation Strength and the Global Structure of QAP Fitness Landscapes
1 Introduction
2 The Quadratic Assignment Problem
3 Algorithms and Definitions
3.1 Monotonic LON Model
3.2 Compressed Monotonic LON Model
4 Experimental Setting
5 Results
5.1 Visualisation
5.2 Structural and Performance Metrics
6 Conclusion
References
Sampling Local Optima Networks of Large Combinatorial Search Spaces: The QAP Case
1 Introduction
2 Combinatorial Landscapes
2.1 The Quadratic Assignment Problem
3 Obtaining the Local Optima Networks
3.1 Complex Network Metrics
4 Sampling Local Optima Networks
5 Empirical Validation
6 Conclusions and Future Work
References
Algorithm Configuration, Selection, and Benchmarking
Algorithm Configuration Landscapes:
1 Introduction
2 Methods
2.1 Parameter Response Slices
2.2 Bootstrap Analysis and Confidence Intervals
2.3 Tests for Convexity and Uni-modality
2.4 Identifying ``Interesting'' Parameter Response Slices
2.5 Counting the Number of Modes (Local Minima)
2.6 Fitness Distance Analysis
3 Experimental Setup
4 Results
4.1 RQ 1. Uni-modality and Convexity on Instance Sets
4.2 RQ 2. Uni-modality and Convexity on Individual Instances
5 Conclusions and Future Work
References
A Model-Based Framework for Black-Box Problem Comparison Using Gaussian Processes
1 Introduction
2 Existing Frameworks for Problem Characterization and Algorithm Selection
3 A Model-Based Framework for Problem Comparison
3.1 Problem Comparison Using Gaussian Processes
3.2 Gaussian Process Implementation Details
3.3 Related Work
4 Experimental Methodology
5 Results and Discussion
6 Conclusion
References
A Suite of Computationally Expensive Shape Optimisation Problems Using Computational Fluid Dynamics
1 Introduction
2 Computational Fluid Dynamics (CFD)
3 Geometry Representation Methods
3.1 Catmull-Clark Subdivision Curves
3.2 Chebyshev Polynomials
3.3 Monotonic Beta Cumulative Distribution Functions
4 Single Objective Problems
4.1 PitzDaily
4.2 Sharp-Heeled Kaplan Draft Tube
5 Multi-objective Problem: Heat Exchanger
6 Conclusion
References
Automated Selection and Configuration of Multi-Label Classification Algorithms with Grammar-Based Genetic Programming
1 Introduction
2 Related Work
3 Automatically Selecting Algorithms and Hyper-Parameters for Multi-Label Classification
3.1 Grammar: A Formal Description of the MLC Search Space
3.2 From Individual Representation to Individual Evaluation
4 Experimental Results
4.1 Evolutionary Behavior
4.2 The Diversity of the Selected MLC Algorithms
5 Conclusions and Future Work
References
Performance Assessment of Recursive Probability Matching for Adaptive Operator Selection in Differential Evolution
1 Introduction
2 Background
2.1 Adaptive Operator Selection
2.2 Mutation Strategies in Differential Evolution
3 Recursive PM (RecPM)
4 Experimental Analysis
4.1 Parameter Tuning
4.2 Comparison of AOS Methods with Different Parameter Settings
4.3 Comparison of RecPM-AOS with State-of-the-Art Algorithms
5 Conclusion and Future Work
References
Program Trace Optimization
1 Introduction
2 Overview of PTO
2.1 Universal Solution Representation
2.2 Naming Scheme
2.3 PTO Software Architecture
2.4 Related Work
3 Implicit Operator Design
3.1 Naming Scheme
3.2 Search Operators on Named Traces
3.3 Example: Loops and Matrices
3.4 Example: Recursion and Expressions
3.5 Implicit Problem Knowledge
4 Experiments and Results
5 Conclusions and Future Work
References
Sampling Heuristics for Multi-objective Dynamic Job Shop Scheduling Using Island Based Parallel Genetic Programming
1 Introduction
2 Background
3 Proposed Method
3.1 Clustering of DJSS Problem Instances
3.2 Proposed Island Model
4 Experiment Design
4.1 Simulation Model
4.2 Genetic Programming System
4.3 Island Model
5 Results and Discussion
5.1 Analysis
6 Conclusions
References
Sensitivity of Parameter Control Mechanisms with Respect to Their Initialization
1 Introduction
2 Sensitivity Analysis for the (1+1) EA
2.1 Optimal Mutation Rates for OneMax and LeadingOnes
2.2 Evaluating the Relative Average Improvement
2.3 Testing for Statistical Significance
2.4 Visualizing the Mutation Rate Adaptation
3 Sensitivity of the Self-adjusting (1+(l,l)) GA
4 Sensitivity of the (1+l) EA (r/2,2r)
5 Conclusions and Future Work
References
Tailoring Instances of the 1D Bin Packing Problem for Assessing Strengths and Weaknesses of Its Solvers
1 Introduction
2 Fundamentals
2.1 The 1D Bin Packing Problem
2.2 Some Solvers of Interest for the 1D Bin Packing Problem
2.3 Some Features for the 1D Bin Packing Problem
2.4 Some Performance Measures for the 1D Bin Packing Problem
2.5 Instances Used in This Work
3 The Proposed Approach
4 Methodology
4.1 Preliminary Testing
4.2 Initial Testing
4.3 Advanced Testing
5 Experiments and Results
5.1 Preliminary Testing
5.2 Initial Testing
5.3 Advanced Testing
6 Conclusions
References
Machine Learning and Evolutionary Algorithms
Adaptive Advantage of Learning Strategies: A Study Through Dynamic Landscape
1 Introduction
2 Background
2.1 Social Learning
2.2 Learning and Evolution in Computer Simulation
3 Experimental Design
3.1 Dynamic Needle-in-a-haystack Landscape
3.2 Experiment Setup
4 Results, Analyses, and Explanations
5 Conclusion and Future Work
References
A First Analysis of Kernels for Kriging-Based Optimization in Hierarchical Search Spaces
1 Introduction
2 Surrogate Model-Based Optimization
3 Kriging
4 Kernels for Hierarchical Search Spaces
4.1 The Arc-Kernel
4.2 Indefinite Conditional Kernel
4.3 Imputation Kernel
4.4 The Imputation-Arc Kernel
5 Experimental Setup
6 Results
7 Conclusion and Outlook
References
Challenges in High-Dimensional Reinforcement Learning with Evolution Strategies
1 Introduction
2 Problems Under Study
3 Evolution Strategies
4 Experiments
5 Conclusion
References
Lamarckian Evolution of Convolutional Neural Networks
1 Introduction
2 Related Work
3 Method
3.1 Evolutionary Algorithm
3.2 Mutation Operator
3.3 Weight Inheritance
4 Experiments
4.1 Setup
4.2 Training Details
4.3 Results
4.4 Discussion
5 Conclusion
References
Learning Bayesian Networks with Algebraic Differential Evolution
1 Introduction and Related Work
2 Differential Evolution
3 Algebraic Framework
3.1 Vector-Like Operations
3.2 Permutation Group
3.3 Bit-String Group
4 Dual Representation of Bayesian Networks
5 The Algorithm DEBN
6 Experimental Results
7 Conclusions and Future Work
References
Optimal Neuron Selection and Generalization: NK Ensemble Neural Networks
1 Introduction to Optimal Neural Selection
2 Optimization by Dynamic Programming
3 Converting a Neural Network into an NK Landscape
4 Experimental Results
4.1 Problem One: Mackey-Glass Time Series Prediction
4.2 Problem Two: Double Pole Balancing Without Velocity Inputs
4.3 Comparative Results
5 Conclusions
References
What Are the Limits of Evolutionary Induction of Decision Trees?
1 Introduction
1.1 GPU, CUDA
1.2 Apache Spark
2 Global Decision Tree System
2.1 Representation, Initialisation and Termination
2.2 Genetic Operators
2.3 Fitness Function
3 Boosted GDT Versions
3.1 CUDA Based Acceleration
3.2 Spark Based Acceleration
4 Experiments
5 Conclusions
References
Tutorials and Workshops at PPSN 2018
Tutorials at PPSN 2018
1 Welcome from the Tutorial Chairs
2 Tutorial Abstracts
2.1 Adaptive Parameter Choices in Evolutionary Computation
2.2 Applications of Genetic Programming in Dynamic Scheduling
2.3 A Small World Hidden in Evolutionary Computation Techniques
2.4 Bio-inspired Approaches to Anomaly and Intrusion Detection
2.5 Cartesian Genetic Programming
2.6 Cloud-y Evolutionary Algorithms
2.7 Computational Complexity Analysis of Genetic Programming
2.8 Evolutionary Algorithms and Hyper-Heuristics
2.9 Evolutionary Bilevel Optimization (EBO): An Emerging Area for Research and Application in EC
2.10 Evolutionary Computation and Machine Learning in Cryptology
2.11 Exploratory Landscape Analysis
2.12 Genetic Improvement: Taking Real-World Source Code and Improving It Using Genetic Programming
2.13 Introduction to Statistical Modeling of EC Systems and Experiments: A Visual Approach
2.14 Learning Classifier Systems as Learning Cognitive Systems
2.15 Mathematical Programming as a Complement to Bio-inspired Optimization
2.16 Multiagent Systems and Agent-Based Modeling and Simulation
2.17 Multi-objective Optimization with the jMetal Framework
2.18 Next Generation Genetic Algorithms
2.19 Runtime Analysis of Population-Based Evolutionary Algorithms
2.20 Semantic Genetic Programming
2.21 The Cartography of Computational Search Spaces
2.22 The Most Recent Advances on Multi-Modal Optimization
2.23 Theory of Parallel Evolutionary Algorithms
Workshops at PPSN 2018
1 Welcome from the Workshop Chairs
2 The Six Workshops
2.1 Advances in Multimodal Optimization
2.2 Black-Box Discrete Optimization Benchmarking (BB-DOB)
2.3 Bridging the Gap Between Theory and Practice in Nature-Inspired Optimization
2.4 Developmental Neural Networks
2.5 Evolutionary Machine Learning
2.6 Investigating Optimization Problems from Machine Learning and Data Analysis
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken