TY  - JOUR
A1  - Doerr, Benjamin
A1  - Neumann, Frank
A1  - Sutton, Andrew M.
T1  - Time Complexity Analysis of Evolutionary Algorithms on Random Satisfiable k-CNF Formulas
JF  - Algorithmica : an international journal in computer science
N2  - We contribute to the theoretical understanding of randomized search heuristics by investigating their optimization behavior on satisfiable random k-satisfiability instances both in the planted solution model and the uniform model conditional on satisfiability. Denoting the number of variables by n, our main technical result is that the simple () evolutionary algorithm with high probability finds a satisfying assignment in time when the clause-variable density is at least logarithmic. For low density instances, evolutionary algorithms seem to be less effective, and all we can show is a subexponential upper bound on the runtime for densities below . We complement these mathematical results with numerical experiments on a broader density spectrum. They indicate that, indeed, the () EA is less efficient on lower densities. Our experiments also suggest that the implicit constants hidden in our main runtime guarantee are low. Our main result extends and considerably improves the result obtained by Sutton and Neumann (Lect Notes Comput Sci 8672:942-951, 2014) in terms of runtime, minimum density, and clause length. These improvements are made possible by establishing a close fitness-distance correlation in certain parts of the search space. This approach might be of independent interest and could be useful for other average-case analyses of randomized search heuristics. While the notion of a fitness-distance correlation has been around for a long time, to the best of our knowledge, this is the first time that fitness-distance correlation is explicitly used to rigorously prove a performance statement for an evolutionary algorithm.
KW  - Runtime analysis
KW  - Satisfiability
KW  - Fitness-distance correlation
Y1  - 2016
U6  - https://doi.org/10.1007/s00453-016-0190-3
SN  - 0178-4617
SN  - 1432-0541
VL  - 78
SP  - 561
EP  - 586
PB  - Springer
CY  - New York
ER  - 
TY  - JOUR
A1  - Roostapour, Vahid
A1  - Neumann, Aneta
A1  - Neumann, Frank
A1  - Friedrich, Tobias
T1  - Pareto optimization for subset selection with dynamic cost constraints
JF  - Artificial intelligence
N2  - We consider the subset selection problem for function f with constraint bound B that changes over time. Within the area of submodular optimization, various greedy approaches are commonly used. For dynamic environments we observe that the adaptive variants of these greedy approaches are not able to maintain their approximation quality. Investigating the recently introduced POMC Pareto optimization approach, we show that this algorithm efficiently computes a phi=(alpha(f)/2)(1 - 1/e(alpha)f)-approximation, where alpha(f) is the submodularity ratio of f, for each possible constraint bound b <= B. Furthermore, we show that POMC is able to adapt its set of solutions quickly in the case that B increases. Our experimental investigations for the influence maximization in social networks show the advantage of POMC over generalized greedy algorithms. We also consider EAMC, a new evolutionary algorithm with polynomial expected time guarantee to maintain phi approximation ratio, and NSGA-II with two different population sizes as advanced multi-objective optimization algorithm, to demonstrate their challenges in optimizing the maximum coverage problem. Our empirical analysis shows that, within the same number of evaluations, POMC is able to perform as good as NSGA-II under linear constraint, while EAMC performs significantly worse than all considered algorithms in most cases.
KW  - Subset selection
KW  - Submodular function
KW  - Multi-objective optimization
KW  - Runtime analysis
Y1  - 2022
U6  - https://doi.org/10.1016/j.artint.2021.103597
SN  - 0004-3702
SN  - 1872-7921
VL  - 302
PB  - Elsevier
CY  - Amsterdam
ER  -