A Runtime Analysis of Parallel Evolutionary Algorithms in Dynamic Optimization [0.03%]
动态参数优化中的并行进化算法的运行时间分析
Andrei Lissovoi,Carsten Witt
Andrei Lissovoi
A simple island model with λ islands and migration occurring after every τ iterations is studied on the dynamic fitness function Maze. This model is equivalent to a ( 1 + λ ) EA if τ = 1 , i. e., migration occurs durin...
Eduard Eiben,Robert Ganian,Stefan Szeider
Eduard Eiben
A modulator in a graph is a vertex set whose deletion places the considered graph into some specified graph class. The cardinality of a modulator to various graph classes has long been used as a structural parameter which can be exploited t...
George Christodoulou,Alkmini Sgouritsa,Bo Tang
George Christodoulou
We study the inefficiency of mixed Nash equilibria, expressed as the price of anarchy, of all-pay auctions in three different environments: combinatorial, multi-unit and single-item auctions. First, we consider item-bidding combinatorial au...
Nikhil Bansal,Parinya Chalermsook,Bundit Laekhanukit et al.
Nikhil Bansal et al.
In this paper, we develop new tools and connections for exponential time approximation. In this setting, we are given a problem instance and an integer r > 1 , and the goal is to design an approximation algorithm with the fastest possible ...
Zengfeng Huang,Pan Peng
Zengfeng Huang
In this paper we study graph problems in the dynamic streaming model, where the input is defined by a sequence of edge insertions and deletions. As many natural problems require Ω ( n ) space, where n is the number of vertices, existi...
On Singleton Arc Consistency for CSPs Defined by Monotone Patterns [0.03%]
单调模式定义的CSPs的Singleton弧一致性
Clément Carbonnel,David A Cohen,Martin C Cooper et al.
Clément Carbonnel et al.
Singleton arc consistency is an important type of local consistency which has been recently shown to solve all constraint satisfaction problems (CSPs) over constraint languages of bounded width. We aim to characterise all classes of CSPs de...
E Eiben,R Ganian,K Kangas et al.
E Eiben et al.
We consider the # P -complete problem of counting the number of linear extensions of a poset ( # LE ) ; a fundamental problem in order theory with applications in a variety of distinct areas. In particular, we study the complexity of # L...
Martijn van Ee,René Sitters
Martijn van Ee
The field of a priori optimization is an interesting subfield of stochastic combinatorial optimization that is well suited for routing problems. In this setting, there is a probability distribution over active sets, vertices that have to be...
The Impact of a Sparse Migration Topology on the Runtime of Island Models in Dynamic Optimization [0.03%]
迁移拓扑稀疏性对动态优化中岛模型运行时间的影响
Andrei Lissovoi,Carsten Witt
Andrei Lissovoi
Island models denote a distributed system of evolutionary algorithms which operate independently, but occasionally share their solutions with each other along the so-called migration topology. We investigate the impact of the migration topo...
How to Escape Local Optima in Black Box Optimisation: When Non-elitism Outperforms Elitism [0.03%]
如何逃离黑箱优化中的局部最优解：非精英策略优于精英策略的情形
Pietro S Oliveto,Tiago Paixão,Jorge Pérez Heredia et al.
Pietro S Oliveto et al.
Escaping local optima is one of the major obstacles to function optimisation. Using the metaphor of a fitness landscape, local optima correspond to hills separated by fitness valleys that have to be overcome. We define a class of fitness va...