检索结果-内蒙古大学图书馆

Two-dimensional drift analysis: Optimizing two functions simultaneously can be hard

THEORETICAL COMPUTER SCIENCE 2023年第1期971卷

作者： Janett, Duri Lengler, Johannes ETH Dept Comp Sci Zurich Switzerland

In this paper we show how to use drift analysis in the case of two random variables X1, X2, when the drift is approximatively given by A center dot (X1, X2)T for a matrix A. The non-trivial case is that X1 and X2 impede each other's progress, and we give a full characterization of this case. As an application, we develop and analyze a minimal example TwoLIN of a dynamic environment that can be hard. The environment consists of two linear functions f1 and f2 with positive weights, and in each generation selection is based on one of them at random. They only differ in the set of positions that have weight 1 and n. We show that the (1+ 1)- EA with mutation rate chi/n is efficient for small chi on TwoLIN, but does not find the shared optimum in polynomial time for large chi.(c) 2023 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/).

关键词： Drift analysis Runtime analysis theory of evolutionary algorithms Dynamic environments

来源：评论

学校读者我要写书评

暂无评论

Focused jump-and-repair constraint handling for fixed-parameter tractable graph problems closed under induced subgraphs

引用

THEORETICAL COMPUTER SCIENCE 2023年第1期951卷

作者： Branson, Luke Sutton, Andrew M. Univ Minnesota Duluth Dept Comp Sci Duluth MN 55812 USA

Repair operators are often used for constraint handling in constrained combinatorial optimization. We investigate the (1+1) EA equipped with a tailored jump-and-repair operation that can be used to probabilistically repair infeasible offspring in graph problems. Instead of evolving candidate solutions to the entire graph, we expand the genotype to allow the (1+1) EA to develop in parallel a feasible solution together with a growing subset of the instance (an induced subgraph). With this approach, we prove that the EA is able to probabilistically simulate an iterative compression process used in classical fixed-parameter algorithmics to obtain a randomized FPT performance guarantee on three NP-hard graph problems. For k-VERTEXCOVER, we prove that the (1+1) EA using focused jump-and-repair can find a k-vertex cover (if one exists) in O (2kn2 log n) iterations in expectation. This leads to an exponential (in k) improvement over the best-known parameterized bound for evolutionary algorithms on VERTEXCOVER. For the k-FEEDBACKVERTEXSET problem in tournaments, we prove that the EA finds a feasible feedback set in O (2kk!n2 log n) iterations in expectation, and for ODDCYCLETRANSVERSAL, we prove the optimization time for the EA is O (3kkmn2 log n). For the latter two problems, this constitutes the first parameterized result for any evolutionary algorithm. We discuss how to generalize the framework to other parameterized graph problems closed under induced subgraphs and report experimental results that illustrate the behavior of the algorithm on a concrete instance class.(c) 2023 Elsevier B.V. All rights reserved.

关键词： theory of evolutionary algorithms Runtime analysis Parameterized complexity Combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

EA models and population fixed-points versus mutation rates for functions of unitation 05

EA models and population fixed-points versus mutation rates ...

引用

Genetic and evolutionary Computation Conference

作者： Richter, J. Neal Paxton, John Wright, Alden Montana State Univ Dept Comp Sci Bozeman MT 59717 USA Univ Montana Dept Comp Sci Missoula MT 59812 USA

ISBN: (纸本)1595930108

Using a dynamic systems model for the Simple Genetic Algorithm due to Vose[1], we analyze the fixed point behavior of the model without crossover applied to functions of unitation. Unitation functions are simplified fitness functions that reduce the search space into a smaller number of equivalence classes. This reduction allows easier computation of fixed points. We also create a dynamic systems model from a simple nondecreasing EA like the (1+1) EA and variants, then analyze this models on unitation classes.

关键词： theory of evolutionary algorithms infinite population models unitation functions fixed points genetic algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：