Parallel Problem Solving from Nature – PPSN XVII: 17th International Conference, PPSN 2022, Dortmund, Germany, September 10–14, 2022, Proceedings, Part II (Lecture Notes in Computer Science, 13399)

This two-volume set LNCS 13398 and LNCS 13399 constitutes the refereed proceedings of the 17th International Conference on Parallel Problem Solving from Nature, PPSN 2022, held in Dortmund, Germany, in September 2022. The 87 revised full papers were carefully reviewed and selected from numerous submissions. The conference presents a study of computing methods derived from natural models. Amorphous Computing, Artificial Life, Artificial Ant Systems, Artificial Immune Systems, Artificial Neural Networks, Cellular Automata, Evolutionary Computation, Swarm Computing, Self-Organizing Systems, Chemical Computation, Molecular Computation, Quantum Computation, Machine Learning, and Artificial Intelligence approaches using Natural Computing methods are just some of the topics covered in this field. Preface Organization Contents – Part II Contents – Part I Genetic Programming Digging into Semantics: Where Do Search-Based Software Repair Methods Search? 1 Introduction 2 Background and Contextual Motivation 3 Technical Approach 3.1 Sampling APR Search Spaces 3.2 Computing Mutant Similarity 3.3 Visualizing Search Spaces 4 Experimental Setup 5 Experimental Results 5.1 RQ1. APR Search Space Exploration and Repair Rates 5.2 RQ2. Similarity of Semantic Search Spaces 5.3 RQ3. Syntactic and Semantic Diversity of Mutants 6 Limitations and Threats to Validity 7 Related Work 8 Conclusion References Gene-pool Optimal Mixing in Cartesian Genetic Programming 1 Introduction 2 Methods 2.1 GOMEA 2.2 CGP 2.3 Adapting GOMEA for CGP 3 Experimental Setup 3.1 General Setup 3.2 Setup Main Experiment 3.3 Population Size Study 3.4 Setup Known Ground Truth Experiment 4 Results 5 Discussion 6 Conclusion References Genetic Programming for Combining Directional Changes Indicators in International Stock Markets 1 Introduction 2 Background and Literature Review 2.1 Overview of Directional Changes 2.2 Related Work 3 Methodology 3.1 Genetic Programming Model 3.2 Trading Strategy 4 Experimental Set up 4.1 Data 4.2 Benchmarks 4.3 Parameter Tuning for GP 4.4 Parameter Tuning for Trading Strategy 5 Result and Analysis 5.1 Comparison Between GP-DC and GP-PT 5.2 Buy and Hold 6 Conclusion References Importance-Aware Genetic Programming for Automated Scheduling Heuristics Learning in Dynamic Flexible Job Shop Scheduling 1 Introduction 2 Background 2.1 Dynamic Flexible Job Shop Scheduling 2.2 GP for DFJSS 3 Importance-Aware Scheduling Heuristic Learning 3.1 An Overview of the Proposed Algorithm 3.2 Measure the Importance of the Routing and Sequencing Rules 3.3 Adaptive Computational Resource Allocation Strategy 4 Experiment Design 5 Results and Discussions 6 Conclusions and Future Work References Towards Discrete Phenotypic Recombination in Cartesian Genetic Programming 1 Introduction 2 Cartesian Genetic Programming 3 Related Work 3.1 Recombination in CGP 3.2 Historical Background of Discrete Recombination 4 The Proposed Method 5 Experiments 5.1 Experimental Setup 5.2 Benchmarks 5.3 Meta-optimization 5.4 Results 6 Discussion 7 Conclusions and Future Work References Multi-Objective Optimization A General Architecture for Generating Interactive Decomposition-Based MOEAs 1 Introduction 2 Background 3 Related Works 4 Properties of an Interactive Solution Process 5 Proposed Architecture 6 Example Method and Experiments 6.1 Interactive Solution Process 6.2 Algorithmic Comparison 6.3 Discussion 7 Conclusions References An Exact Inverted Generational Distance for Continuous Pareto Front 1 Introduction 2 Related Work 3 Exact Inverted Generational Distance 4 Evaluating Discretization Error Using eIGD 5 Conclusion and Future Work References Direction Vector Selection for R2-Based Hypervolume Contribution Approximation 1 Introduction 2 Background 2.1 Hypervolume and Hypervolume Contribution 2.2 R2-Based Hypervolume Contribution Approximation 2.3 Direction Vector Set Generation Methods 2.4 Subset Selection 3 Proposed Method for Selecting Direction Vector Set 3.1 Approximation Error 3.2 Problem Formulation 3.3 Greedy Inclusion Algorithm 4 Experiments and Discussions 4.1 Direction Vector Selection 4.2 Test on Six Regular Pareto Fronts 4.3 Application: GAHSS 5 Conclusion References Do We Really Need to Use Constraint Violation in Constrained Evolutionary Multi-objective Optimization? 1 Introduction 2 Experimental Settings 2.1 Benchmark Test Problems 2.2 Peer Algorithms and Parameter Settings 2.3 Performance Metrics and Statistical Tests 3 Experimental Results 3.1 Performance Analysis on Synthetic Benchmark Test Problems 3.2 Performance Analysis on Real-World Benchmark Test Problems 4 Conclusion References Dynamic Multi-modal Multi-objective Optimization: A Preliminary Study 1 Introduction 2 Related Work 2.1 Multi-modal Multi-objective Optimization 2.2 Dynamic Multi-objective Optimization 3 Dynamic Multi-modal Multi-objective Optimization 4 A Systematic Approach for Constructing dMMOPs 4.1 Case Study on an Example Test Problem 5 A Suggested Test Suite 6 Concluding Remarks References Fair Feature Selection with a Lexicographic Multi-objective Genetic Algorithm 1 Introduction 2 A Lexicographic-Optimisation Genetic Algorithm for Fair Feature Selection 2.1 Population Initialisation 2.2 Lexicographic Tournament Selection 2.3 The Four Fairness Measures and the Accuracy Measure 2.4 Aggregating Fairness Measures 2.5 Lexicographic Elitism 2.6 Related Work 3 Datasets and Experimental Setup 4 Experimental Results 4.1 RQ1: Does LGAFFS Select a Better Subset than the Full Set? 4.2 RQ2: Does LGAFFS Perform Better than SFS? 5 Conclusions References Greedy Decremental Quick Hypervolume Subset Selection Algorithms 1 Introduction 2 Basic Definitions 3 Improved Quick Hypervolume Algorithm Scheme 4 Greedy Decremental Lazy Quick HSS Algorithm 5 The Modified Quick Hypervolume Extreme Contributor/Contribution Algorithm 6 Computational Experiment 7 Conclusions References Hybridizing Hypervolume-Based Evolutionary Algorithms and Gradient Descent by Dynamic Resource Allocation 1 Introduction 2 Uncrowded Hypervolume Optimization 3 UHV-Based Algorithms 3.1 UHV-ADAM 3.2 UHV-GOMEA 4 Hybridization 4.1 Changes Made to UHV-ADAM 4.2 Resource Allocation Scheme 5 Experiments 5.1 Experimental Setup 5.2 Experiment 1: The Effect of the Improvement Metric 5.3 Experiment 2: The Effect of the Choice of Method to Distribute Gradient Resources 5.4 Experiment 3: The WFG Benchmark 6 Discussion 7 Conclusion References Identifying Stochastically Non-dominated Solutions Using Evolutionary Computation 1 Background and Motivation 2 Proposed Problem Formulation 3 Solution Using an Evolutionary Algorithm 3.1 Discretization and Evaluation of Objectives 3.2 Parent Selection and Evolution Operators 3.3 Dominance Calculation and Ranking 3.4 Strategies to Reduce Computational Effort 4 Numerical Experiments 4.1 Test Problems 4.2 Experimental Setup 4.3 Performance Measurement 4.4 Results 5 Conclusions and Future Work References Large-Scale Multi-objective Influence Maximisation with Network Downscaling 1 Introduction 2 Method 2.1 Step (1): Community-Based Downscaling 2.2 Step (2): MOEA on Two Objectives (cascade Size and Seed Set Size) 2.3 Step (3): Upscaling 3 Results 3.1 Community-Based Downscaling of Large Networks 3.2 MOEA and Solution Upscaling: The Optimality of Solutions 3.3 Runtime Analysis 3.4 Comparison with Heuristic Algorithm 4 Discussion and Conclusions References Multi-Objective Evolutionary Algorithm Based on the Linear Assignment Problem and the Hypervolume Approximation Using Polar Coordinates (MOEA-LAPCO) 1 Introduction 2 Approximating the Hypervolume Contribution Using Polar Coordinates 3 Hungarian Differential Evolution 3.1 Drawbacks of HDE's Selection Process 4 Our Proposed Approach 4.1 Selection Process 4.2 Population to Be Pruned 4.3 The Final Algorithm: MOEA-LAPCO 5 Experimental Analysis 6 Conclusions and Future Work References New Solution Creation Operator in MOEA/D for Faster Convergence 1 Introduction 2 Proposed Strategy and Implementations 3 Experimental Study 4 Conclusion and Future Work References Obtaining Smoothly Navigable Approximation Sets in Bi-objective Multi-modal Optimization 1 Introduction 2 Bézier parameterizations 2.1 Definition of Solution Set 2.2 Evaluation 3 Niching Methods 3.1 HVC and MO HVC 3.2 Restart Scheme with Elitist Archive 4 Multi Modal-Bézier Evolutionary Algorithm 4.1 Clustering Approximation Sets 4.2 Initialization Within Niches 4.3 Algorithm Overview 5 Experiments 5.1 Test Problems 5.2 Benchmark Setup 5.3 Performance Indicators 5.4 Results 6 Discussion 7 Conclusion References T-DominO 1 Introduction 2 Background 2.1 Generative Design 2.2 Exploration and Optimization with Non-objective Criteria 3 Method 4 Benchmarks 4.1 Setup 4.2 Result 5 Case Study 5.1 Setup 5.2 Result 6 Discussion References Numerical Optimizaiton Collective Learning of Low-Memory Matrix Adaptation for Large-Scale Black-Box Optimization 1 Introduction 2 Related Work on Distributed ES 3 Distributed LM-MA-ES Within Multilevel Learning 3.1 Combining Island Model with Meta-eS for Multilevel Learning 3.2 Online and Hierarchical Learning of Strategy Parameters via Meta-eS 3.3 Collective Learning of Fitness Topology via Multi-recombination 3.4 A Distributed ES Framework for Multilevel Learning 4 Numerical Experiments on Clustering Computing Platforms 4.1 Experimental Settings for Large-Scale Black-Box Optimization 4.2 Parallel Speedup w.r.t. Total Number of Function Evaluations 4.3 Performance Comparisons W.R.T. Final Convergence Quality 5 Conclusions References Recombination Weight Based Selection in the DTS-CMA-ES 1 Introduction 2 Background 2.1 Gaussian Processes 2.2 Bayesian Optimization 2.3 CMA-ES 2.4 DTS-CMA-ES 2.5 Model Fitting 3 Fully Weight-Based DTS-CMA-ES 4 Experiments 5 Results and Discussion 6 Conclusion References The (1+1)-ES Reliably Overcomes Saddle Points 1 Introduction 2 Saddle Points 3 Preliminaries 4 Drift of the Normalized State 5 Discussion and Conclusion References Real-World Applications Evolutionary Time-Use Optimization for Improving Children's Health Outcomes 1 Introduction 1.1 Data Description 2 The Time-Use Optimization Models 2.1 Model Parameter Estimation 2.2 One Week Plan 2.3 Multi-objectives Problem 2.4 Fitness Function 3 Evolutionary Algorithms for the Time-Use Optimisation Problem 3.1 Single-objective Evolutionary Algorithms 3.2 Multi-objective Evolutionary Algorithms 4 Experiments 4.1 Results of Single-objective Time-Use Optimization 4.2 Results of Multi-objective Time-Use Optimization 5 Conclusion References Iterated Local Search for the eBuses Charging Location Problem 1 Introduction 2 Related Work 3 The Charging Location Problem 4 The Iterated Local Search 5 Evaluation 6 Conclusions References Multi-view Clustering of Heterogeneous Health Data: Application to Systemic Sclerosis 1 Introduction 2 Background and Related Work 2.1 Distance-Based Clustering on Heterogeneous Data 2.2 From Single to Multi-objective Clustering 3 Multi-view Clustering Approach 3.1 Construction of the Data Views 3.2 Multi-view Clustering Algorithm: MVMC 3.3 Selection of Clustering Solutions 4 Experimental Study 4.1 CHUL Database and Data-View Configurations 4.2 Reference Methods 4.3 Parameter Settings 5 Results and Discussions 5.1 Clustering Performance 5.2 Selection of Clustering Solutions 6 Conclusion References Specification-Driven Evolution of Floor Plan Design 1 Introduction 2 Visual Floor Plan Generation Framework 2.1 Floor Plan Representation 2.2 Population Initialization 2.3 Fitness Function 2.4 Mutation 2.5 Selection 3 Case Study 4 Conclusions References Surrogate-Assisted Multi-objective Optimization for Compiler Optimization Sequence Selection 1 Introduction 2 Background 2.1 Compiler Optimization Sequence Selection 2.2 Multi-objective Optimization for Compiler Optimization Sequence Selection 3 The Proposed Approach 3.1 Representation 3.2 Fitness Function 3.3 Surrogate-Assisted Multi-objective Optimization Algorithm 3.4 Surrogate Model 4 Experimental Results 4.1 Experimental Setup 4.2 Experimental Results 5 Conclusion and Future Work References Theoretical Aspects of Nature-Inspired Optimization A First Runtime Analysis of the NSGA-II on a Multimodal Problem 1 Introduction 2 Previous Works 3 Preliminaries 3.1 The NSGA-II Algorithm 3.2 The OneJumpZeroJump Benchmark 4 Runtime Analysis for the NSGA-II 4.1 Runtime Analysis for the NSGA-II Using Bit-Wise Mutation 4.2 Runtime Analysis for the NSGA-II Using Fast Mutation 5 Experiments 6 Conclusions and Future Works References Analysis of Quality Diversity Algorithms for the Knapsack Problem 1 Introduction 2 Quality-Diversity for the Knapsack Problem 2.1 Weight-Based Space 2.2 Profit-Based Space 2.3 DP-Based Filtering Scheme 3 Theoretical Analysis 4 Experimental Investigations 5 Conclusions References Better Running Time of the Non-dominated Sorting Genetic Algorithm II (NSGA-II) by Using Stochastic Tournament Selection 1 Introduction 2 Preliminaries 2.1 Multi-objective Optimization 2.2 NSGA-II 3 Running Time Analysis of NSGA-II 4 NSGA-II Using Stochastic Tournament Selection 4.1 Stochastic Tournament Selection 4.2 Running Time Analysis 5 Experiments 5.1 LOTZ Problem 5.2 ZDT1 Problem 6 Conclusion References Escaping Local Optima with Local Search: A Theory-Driven Discussion 1 Introduction 2 Definitions and Algorithms 2.1 Algorithms 3 Basins of Attraction 4 Deceptive Valleys vs. Guiding Information 5 Single Target vs. Multiple Targets 6 Iterated Local Optima 7 Discussion and Conclusion References Evolutionary Algorithms for Cardinality-Constrained Ising Models 1 Introduction 2 Preliminaries 3 Runtime Analyses for One-Dimensional Ising Model 3.1 Results for Single Swaps 3.2 Swapping only Boundary Atoms 3.3 Swapping Clusters of Atoms 4 Numerical Experiments 5 Conclusions References General Univariate Estimation-of-Distribution Algorithms 1 Introduction 2 Previous Work 3 Univariate EDA: Classic and New 4 Genetic Drift 5 Optimizing the (i)i 6 Designing New Univariate EDAs 7 Conclusion References Population Diversity Leads to Short Running Times of Lexicase Selection 1 Introduction 1.1 Our Contributions 2 Preliminaries 2.1 Lexicase Selection 2.2 -Cluster Similarity 3 Theoretical Result: Low -Cluster Similarity Leads to Small Running Times 3.1 Preliminaries 4 Empirical Evaluation in Program Synthesis 4.1 Experimental Setup 4.2 Results 5 Discussion 6 Conclusions References Progress Rate Analysis of Evolution Strategies on the Rastrigin Function: First Results 1 Introduction 2 Rastrigin Function and Local Quality Change 3 The (/I, )-ES with Normalized Mutations 4 Progress Rate 4.1 Definition 4.2 Expectations of Sums of Noisy Order Statistics 4.3 Comparison of Simulation and Approximation 5 Evolution Dynamics 6 Summary and Outlook References Running Time Analysis of the (1+1)-EA Using Surrogate Models on OneMax and LeadingOnes 1 Introduction 2 Preliminaries 2.1 (1+1)-EA 2.2 Surrogate Models 2.3 OneMax and LeadingOnes 2.4 Analysis Tools 3 Analysis of the (1+1)-EA Using the RPS Surrogate 4 Analysis of the (1+1)-EA Using the RCPS Surrogate 5 Conclusion and Discussion References Runtime Analysis of Simple Evolutionary Algorithms for the Chance-Constrained Makespan Scheduling Problem 1 Introduction 2 Preliminaries 3 Algorithms 4 Performance for CCMSP-1 5 Performance for CCMSP-2 5.1 Performance for CCMSP-2+ 6 Conclusion References Runtime Analysis of the (1+1) EA on Weighted Sums of Transformed Linear Functions 1 Introduction 1.1 Separable Functions 1.2 Chance Constrained Problems 1.3 Transformed Linear Functions 2 Preliminaries 2.1 Sums of Two Transformed Linear Functions Without Constraints 3 Negative Weights Allow for Multimodal Functions 4 Upper Bound 5 Discussion and Conclusions References Runtime Analysis of Unbalanced Block-Parallel Evolutionary Algorithms 1 Introduction 1.1 Background 2 Block-Parallel (1+) EA 3 Heterogeneous Fitness Evaluation 4 First-Improving Search Using Task Abortion 5 Experimental Analysis 5.1 Experimental Settings 5.2 The Block-Parallel (1+)parEA Analysis 5.3 Simulations on the Abortive Block-Parallel (1+) parEA 6 Conclusion References Self-adjusting Population Sizes for the (1, )-EA on Monotone Functions 1 Introduction 2 Preliminaries and Definitions 3 Monotone Functions Are Efficient for Large Success Rates 4 Small Success Rates Yield Exponential Runtimes 5 Simulations 6 Conclusion References Theoretical Study of Optimizing Rugged Landscapes with the cGA 1 Introduction 2 Algorithms and Problem Setting 2.1 D-Rugged OneMax 3 Performance of the cGA 4 Performance of RLS 4.1 Performance of RLS – A Detailed Look 5 Performance of the (1+1) EA 6 Performance of Random Search 7 Experimental Evaluation 8 Conclusion References Towards Fixed-Target Black-Box Complexity Analysis 1 Introduction 2 Related Work 3 Preliminaries 4 Generic Lower Bounds 5 Lower Bound for OneMax 6 Upper Bound for OneMax 7 Conclusion References Two-Dimensional Drift Analysis: 1 Introduction 1.1 The Application: TwoLin 1.2 The Method: Two-Dimensional Multiplicative Drift Analysis 2 Preliminaries and Definitions 3 Two-Dimensional Multiplicative Drift 3.1 Interpretation and Generalization 4 The (1+1)-EA on TwoLin, 4.1 Domination and the Symmetric Case ==1/2 References Author Index