A5004695687- Metaheuristic Optimization Algorithms Research
- Evolutionary Algorithms and Applications
- Advanced Multi-Objective Optimization Algorithms
- Constraint Satisfaction and Optimization
- Software Engineering Research
- Optimization and Search Problems
- Advanced Software Engineering Methodologies
- Advanced Graph Theory Research
- Algorithms and Data Compression
- Software Testing and Debugging Techniques
- Vehicle Routing Optimization Methods
- Optimization and Packing Problems
- Logic, programming, and type systems
- Parallel Computing and Optimization Techniques
- Software System Performance and Reliability
- Formal Methods in Verification
- Software-Defined Networks and 5G
- Distributed and Parallel Computing Systems
- Evolution and Genetic Dynamics
- Scheduling and Optimization Algorithms
- Genome Rearrangement Algorithms
- Graph Labeling and Dimension Problems
- Complexity and Algorithms in Graphs
- Scheduling and Timetabling Solutions
- Software Reliability and Analysis Research
University of Minnesota, Duluth
2018-2024
The University of Adelaide
2012-2021
University of Minnesota
2020
University of Minnesota System
2020
Colorado State University
2007-2019
Hasso Plattner Institute
2015-2017
University of Bristol
2017
University of Potsdam
2015-2016
Texas A&M University
2011-2015
Friedrich Schiller University Jena
2014-2015
Population diversity is essential for avoiding premature convergence in genetic algorithms (GAs) and the effective use of crossover. Yet dynamics how emerges populations are not well understood. We rigorous runtime analysis to gain insight into population GA performance (μ + 1) Jump test function. show that interplay crossover followed by mutation may serve as a catalyst leading sudden burst diversity. This leads significant improvements expected optimization time compared mutation-only like...
Practical optimization problems frequently include uncertainty about the quality measure, for example, due to noisy evaluations. Thus, they do not allow a straightforward application of traditional techniques. In these settings, randomized search heuristics such as evolutionary algorithms are popular choice because often assumed exhibit some kind resistance noise. Empirical evidence suggests that algorithms, estimation distribution (EDAs) robust against scaling noise intensity, even without...
Population diversity is essential for the effective use of any crossover operator. We compare seven commonly used mechanisms and prove rigorous run time bounds (μ+1) GA using uniform on fitness function Jumpk. All previous results in this context only hold unrealistically low probability pc=O(k/n), while we give analyses setting constant pc < 1 all but one case. Our show a dependence problem size~$n$, jump length k, population size μ, pc. For typical case k > 2 pc, can resulting expected...
Jump functions were originally introduced as benchmarks on which recombinant evolutionary algorithms can provably outperform those that use mutation alone. To optimize a jump function, an algorithm must be able to execute initial hill-climbing phase, after point across large gap generated. Standard GAs mix and crossover achieve both behaviors. It seems likely other techniques, such estimation of distribution (EDAs) may exhibit behavior, but analysis is so far missing.
We contribute to the theoretical understanding of evolutionary algorithms and carry out a parameterized analysis for Euclidean traveling salesperson problem (Euclidean TSP). exploit structural properties related optimization process this use them bound runtime algorithms. Our studies in dependence number inner points $k$ shows that simple solve TSP expected time O(nk(2k-1)!). Moreover, we show that, under reasonable geometric constraints, locally optimal 2-opt tour can be found by randomized...
Recent results show that the Differential Evolution algorithm has significant difficulty on functions are not linearly separable. On such functions, must rely primarily its differential mutation procedure which, unlike recombination strategy, is rotationally invariant. We conjecture this strategy lacks sufficient selective pressure when appointing parent and donor vectors to have satisfactory exploitative power non-separable functions. find imposing in form of rank-based a improvement...
Community assembly is affected by environmental filtering that restricts viable phenotypes and species interactions impose limits on interspecific trait similarity. Relative influences of these processes should vary according to habitat features dispersal. Species dispersion within assemblage space also in relation richness, strength competition, the spatiotemporal scale analysis. We examined ecomorphological diversity two freshwater fish families (Neotropical Cichlidae, Nearctic...
Submodular optimization plays a key role in many real-world problems. In scenarios, it is also necessary to handle uncertainty, and potentially disruptive events that violate constraints stochastic settings need be avoided. this paper, we investigate submodular problems with chance constraints. We provide first analysis on the approximation behavior of popular greedy algorithms for Our results show these are highly effective when using surrogate functions estimate constraint violations based...
The concept of model slicing is introduced as a means to support maintenance through the understanding, querying, and analysis large UML models. specific models being examined are class defined in Unified Modeling Language (UML). Model analogous classical program slicing. Since do not explicitly embody any behavioral aspect by themselves, slices computed context-free manner. paper defines formalizes A concrete application software presented usefulness validity method.
The theory of population genetics and evolutionary computation have been evolving separately for nearly 30 years. Many results independently obtained in both fields many others are unique to its respective field. We aim bridge this gap by developing a unifying framework processes that allows algorithms models be cast the same formal framework. we present here decomposes process into several components order facilitate identification similarities between different models. In particular,...
Due to their randomized nature, many nature-inspired heuristics are robust some level of noise in the fitness evaluations. A common strategy increase tolerance is re-evaluate a solution candidate several times and then work with average sampled values. In this work, we propose use median instead mean. Besides being invariant rescalings fitness, situations turns out be much more than We show that when noisy ϵ-concentrated, logarithmic number samples suffice discover undisturbed (via samples)...
Particle Swarm Optimization (PSO) is a population-based optimization method in which search points employ cooperative strategy to move toward one another. In this paper we show that PSO appears work well on single-funnel functions. On more complex problems, tends converge too quickly and then fail make further progress. We contend most benchmarks for have classically been demonstrated However, practice, tasks are possess higher problem dimensionality. present empirical results support our...
Parameterized runtime analysis seeks to understand the influence of problem structure on algorithmic runtime. In this paper, we contribute theoretical understanding evolutionary algorithms and carry out a parameterized for Euclidean traveling salesperson (Euclidean TSP). We investigate structural properties in TSP instances that optimization process use information bound their analyze dependence number inner points k. first part study [Formula: see text] EA strictly black box setting show it...
Hill climbing algorithms are at the core of many approaches to solve optimization problems. Such usually require complete enumeration a neighborhood current solution. In case problems defined over binary strings length n, we define r-ball as set solutions Hamming distance r or less from For ll n this contains Θ(nr) solutions. paper efficient methods areintroduced locate improving moves in for that can be written sum linear number subfunctions depending on bounded variables. NK-landscapes and...
Software Defined Networking (SDN) drastically changes the meaning and process of designing, building, testing, operating networks. The current support for wireless networking in SDN technologies has lagged behind its development deployment wired purpose this work is to bring principled access networks so that they can receive same level programmability as wireline interfaces. Specifically we aim integrate protocols into general framework by proposing a new set abstractions devices interfaces...
Recently, ant colony optimization (ACO) algorithms have proven to be efficient in uncertain environments, such as noisy or dynamically changing fitness functions. Most of these analyses focused on combinatorial problems path finding. We rigorously analyze an ACO algorithm optimizing linear pseudo-Boolean functions under additive posterior noise. study noise distributions whose tails decay exponentially fast, including the classical case Gaussian Without noise, [Formula: see text] EA...
The landscape formalism unites a finite candidate solution set to neighborhood topology and an objective function. This construct can be used model the behavior of local search on combinatorial optimization problems. A is elementary when it possesses unique property that results in relative smoothness decomposability its structure. In this paper we explain landscapes terms expected value components which are transformed process moving from incumbent neighboring solution. We introduce new...