在处理机器人技术，游戏和组合优化等领域的问题时，质量多样性（QD）算法已被证明非常成功。它们的目的是最大程度地提高基本问题所谓行为空间不同区域的解决方案的质量。在本文中，我们应用QD范式来模拟背包问题上的动态编程行为，并提供对QD算法的第一个运行时分析。我们证明他们能够在预期的伪多项式时间内计算最佳解决方案，并揭示导致完全多项式随机近似方案（FPRAS）的参数设置。我们的实验研究根据在行为空间中构建的解决方案以及获得最佳解决方案所需的运行时评估了经典基准集的不同方法。

在真实世界优化中，常见的是面对几个次级问题，互动和形成主要问题。子问题之间存在依赖性，使得不可能通过专注于一个组件来解决这样的问题。旅行小偷问题〜（TTP）属于此类别，由旅行销售人员问题〜（TSP）和背包问题〜（KP）形成。在本文中，我们通过优质多样性〜（QD）方法研究了TSP和KP的依赖性。 QD算法提供强大的工具，不仅可以获得高质量解决方案，还提供了在行为空间中的高性能解决方案的分布。我们使用众所周知的TSP和KP搜索操作员介绍基于Map-Elite的进化算法，将TSP和KP得分作为行为描述符。之后，我们进行全面的实验研究，表明使用应用于TTP的QD方法的有用性。首先，我们提供有关TSP / KP行为空间中高质量TTP解决方案的见解。之后，我们表明，通过使用我们的QD方法可以获得更好的TTP解决方案，并显示它可以改善用于在文献中基准测试的广泛TTP实例的最佳已知解决方案。

最近，已经开发了不同的进化计算方法，该方法为给定优化问题生成了一组高质量的解决方案。许多研究都认为多样性1）是探索行为空间（质量多样性）或2）以增加解决方案的结构差异（进化多样性优化）的平均值。在这项研究中，我们引入了一种共同进化算法，以同时探索多组分旅行小偷问题的两个空间。结果表明，与文献的基线进化多样性算法相比，共同进化算法具有明显更高多样性的能力。

机会受到限制的优化问题允许建模问题，其中涉及随机组件的约束仅应以较小的概率侵犯。进化算法已应用于这种情况，并证明可以实现高质量的结果。在本文中，我们有助于对进化算法的理论理解，以进行偶然的优化。我们研究独立且正态分布的随机组件的场景。考虑到简单的单对象（1+1）〜EA，我们表明，施加额外的统一约束已经导致局部最佳选择，对于非常有限的场景和指数优化时间。因此，我们引入了问题的多目标公式，该公式可以摆脱预期成本及其差异。我们表明，在使用此公式时，多目标进化算法是非常有效的，并获得一组解决方案，该解决方案包含最佳解决方案，以适用于施加在约束上的任何可能的置信度。此外，我们证明这种方法还可以用于计算一组最佳解决方案，以限制最小跨越树问题。为了在多目标配方中呈指数指数的折衷，我们提出并分析了改进的凸多目标方法。关于NP-固定随机最小重量占主导地位问题的实例的实验研究证实了多目标和改进的凸多目标方法的益处。

一组解决方案中的多元化已成为进化计算社区中的热门研究主题。事实证明，它有益于以多种方式优化问题，例如计算一套高质量的解决方案并获得不完美建模的鲁棒性。在文献中，我们首次适应了现实世界中的组合问题的进化多样性优化，即患者的入学计划。我们引入了一种进化算法，以在每种溶液质量的一组解决方案中实现结构多样性。我们还引入了一个突变操作员，偏向于多样性最大化。最后，我们通过模拟证明了多样性对上述问题的重要性。

过去已经表明，与解决多模式问题生成器的解决实例相比，多座丘陵策略与标准遗传算法相比有利。我们扩展了这项工作，并验证遗传算法中多样性保存技术的利用是否改变了比较结果。在两种情况下，我们这样做：（1）​​目标是找到全局最佳距离时，（2）当目标是找到所有Optima时。进行了数学分析，用于多设山丘算法，并通过实证研究进行了经验研究，以求解多模式问题生成器的实例，其中包括山丘策略以及遗传算法的数量，并使用遗传算法进行了元素。尽管小甲基元素改善了遗传算法的性能，但它仍然不如这类问题上的多尽山关闭策略。还提出了一种理想化的细分策略，并认为它的性能应接近任何进化算法在此类问题上可以做到的。

在进化计算中使用非豁免主义时的一个希望是放弃当前最佳解决方案的能力，艾滋病们离开本地最佳效果。为了提高我们对这种机制的理解，我们对基本的非精英进化算法（EA），$（\ mu，\ lambda）$ ea进行严格的运行时分析，在最基本的基准函数上，具有本地最佳的基本基准函数跳跃功能。我们证明，对于参数和问题的所有合理值，$（\ mu，\ lambda）$ ~ea的预期运行时间除了下订单条款之外，至少与其Elitist对应的预期运行时间，$（\ mu + \ lambda）$〜ea（我们对跳转功能进行第一个运行时分析以允许此比较）。因此，$（\ mu，\ lambda）$ ~ea将本地最优方式留给劣质解决方案的能力不会导致运行时优势。我们补充了这个下限的下限，即对于参数的广泛范围，与我们的下限不同，与下顺序不同。这是一个在多模态问题上的非精英算法的第一个运行时结果，除了下订单术语。

$（1 +（\ lambda，\ lambda））$遗传算法是一种较年轻的进化算法，试图从劣质解决方案中获利。关于单峰的健身功能的严格运行时分析表明它确实可以比古典进化算法更快，但在这些简单的问题上，收益只有中等。在这项工作中，我们在多模式问题类中进行了该算法的第一个运行时分析，跳跃功能基准。我们展示了使用正确的参数，\ ollga优化任何跳跃尺寸$ 2 \ Le K \ Le N / 4 $的任何跳跃功能，在预期的时间$ O（n ^ {（k + 1）/ 2} e ^ {o（ k）}} k ^ { - k / 2}），它显着且已经持续了〜$ k $优于基于标准的突变的算法与他们的$ \ theta（n ^ k）$运行时与它们的标准交叉的算法$ \ tilde {o}（n ^ {k-1}）$运行时保证。对于离开局部跳跃功能的局部最佳的孤立问题，我们确定了导致$（n / k）^ {k / 2} e ^ {\ theta（k）} $的运行时间的最佳参数。这表明有关如何设置\ ollga的参数的一般建议，这可能会缓解该算法的进一步使用。

在实际优化方案中，要求我们解决的问题实例可能会在优化过程中发生变化，例如，当可用新信息或环境条件发生变化时。在这种情况下，人们可以希望通过从最佳解决方案的最佳解决方案继续进行搜索来实现合理的绩效。同样，人们可能希望，在解决彼此相似的几个问题实例时，````温暖启动'''第二个实例的优化过程是通过第一个实例的最佳解决方案的优化过程。但是，在[Doerr等人，GECCO 2019]中显示，即使使用结构良好的解决方案初始化，进化算法也可能具有通过结构上更糟糕的解决方案替换这些良好溶液的趋势，从而导致优化时间与没有优化的时间相比没有优化的时间。相同的算法从头开始。 Doerr等人。还提出了一种克服这个问题的多样性机制。他们的方法平衡了围绕当前问题的最佳解决方案的贪婪搜索，并在上一个实例的最佳发现解决方案周围进行搜索。在这项工作中，我们首先表明Doerr等人建议的重新优化方法。当问题实例容易发生更频繁的更改时，达到限制。更确切地说，我们证明它们被陷入了动态领导问题问题，目标字符串定期更改。然后，我们提出了其算法的修改，该算法在围绕先前最佳和当前最佳解决方案围绕贪婪的搜索进行了插值。我们从经验上评估了具有各种变化频率和不同扰动因素的前导者实例上的平滑重优化算法，并表明它表现出优于完全重新启动的（1+1）进化算法和Doerr等人的重新挑选方法。

Evolutionary algorithms (EAs) are general-purpose optimization algorithms, inspired by natural evolution. Recent theoretical studies have shown that EAs can achieve good approximation guarantees for solving the problem classes of submodular optimization, which have a wide range of applications, such as maximum coverage, sparse regression, influence maximization, document summarization and sensor placement, just to name a few. Though they have provided some theoretical explanation for the general-purpose nature of EAs, the considered submodular objective functions are defined only over sets or multisets. To complement this line of research, this paper studies the problem class of maximizing monotone submodular functions over sequences, where the objective function depends on the order of items. We prove that for each kind of previously studied monotone submodular objective functions over sequences, i.e., prefix monotone submodular functions, weakly monotone and strongly submodular functions, and DAG monotone submodular functions, a simple multi-objective EA, i.e., GSEMO, can always reach or improve the best known approximation guarantee after running polynomial time in expectation. Note that these best-known approximation guarantees can be obtained only by different greedy-style algorithms before. Empirical studies on various applications, e.g., accomplishing tasks, maximizing information gain, search-and-tracking and recommender systems, show the excellent performance of the GSEMO.

跳跃功能是随机搜索启发式理论中的{最多研究的非单峰基准，特别是进化算法（EA）。他们对我们的理解显着改善了EASE逃离当地最优的理解。然而，他们的特殊结构 - 离开本地最佳的结构只能直接跳到全球最优 - 引发代表性这种结果的问题。出于这个原因，我们提出了一个扩展的$ \ textsc {jump} _ {k，\ delta} $ jump函数，其中包含宽度$ \ delta $的低适合度vally以距离$ k $从全局最佳v $开始。我们证明了几个以前的结果延伸到这一更普遍的类：对于所有{$ k \ le \ frac {n ^ {1/3}} {\ ln {n}} $}和$ \ delta <k $，最佳$（1 + 1）$〜EA的突变率是$ \ FRAC {\ delta} $，并且快速$（1 + 1）$〜EA运行比经典$（1 + 1）$更快〜ea在$ \ delta $中的一个超级指数。但是，我们还观察到一些已知结果不概括：随机本地搜索算法具有停滞检测，其比$ \ textsc的$ k $ k $ k $ k $ k $ k $ k $ x $ \ textsc {跳} _K $，在某些$ \ textsc {jump} _ {k，\ delta} $实例上以$ n $的因子多项式慢。计算地，新类允许使用更宽的健身谷的实验，特别是当它们远离全球最佳时。

大多数进化算法具有多个参数，它们的值大大影响性能。由于参数的常复相互作用，将这些值设置为特定问题（参数调整）是一个具有挑战性的任务。当最佳参数值在算法运行期间最佳参数值发生显着变化时，此任务变得更加复杂。然后是必要的动态参数选择（参数控制）。在这项工作中，我们提出了一个懒惰但有效的解决方案，即从一个适当缩放的幂律分布中随机地选择所有参数值（在那里这是有意义的）。为了展示这种方法的有效性，我们使用以这种方式选择的所有三个参数执行$（1 +（\ lambda，\ lambda））$遗传算法的运行时分析。我们展示该算法一方面可以模仿像$（1 + 1）$ EA这样的简单山羊，给出了onemax，领导者或最小生成树等问题的相同渐近运行时。另一方面，该算法对跳跃功能也非常有效，其中最佳静态参数与优化简单问题所需的静态参数非常不同。我们证明了具有可比性的性能保证，有时比静态参数所知的最佳性能更好。我们通过严格的实证研究来补充我们的理论结果，证实了渐近运行时期结果的建议。

分布算法（EDA）是优化算法，在搜索空间上学习分布，可以轻松地采样良好的解决方案。大多数EDA的关键参数是样本量（人口尺寸）。如果人口规模太小，则概率模型的更新基于很少的样本，从而导致遗传漂移的不期望效应。人口太大避免了遗传漂移，但减慢了这一过程。基于对种群规模如何导致遗传漂移的最新定量分析，我们为EDA设计了一种智能的正式机制。通过停止运行，当遗传漂移的风险很高时，它会自动以良好的参数状态运行EDA。通过数学运行时分析，我们证明了此智能总结方案的一般性能保证。这特别表明，在许多情况下，已知最佳（特定问题）参数值，重新启动方案会自动找到这些，从而导致渐近最佳性能。我们还进行了广泛的实验分析。在四个经典的基准问题上，我们清楚地观察了人口规模对性能的关键影响，并且我们发现智能重点方案会导致具有最佳参数值可获得的性能。我们的结果还表明，先前基于理论的最佳人口规模的建议远非最佳群体，从而导致表现明显不如通过智能重点方案获得的表现。我们还对文献，最大切割问题和两部分问题的两个组合优化问题进行了PBIL（跨熵算法）进行实验。同样，我们观察到，智能设施的机制比文献中建议的人口规模更高，从而导致表现更好。

最近，已经进行了NSGA-II的第一个数学运行时分析，这是最常见的多目标进化算法（Zheng，Liu，Doerr（AAAI 2022））。继续这一研究方向，我们证明了NSGA-II在使用交叉时，渐近渐近地测试了OneJumpZeroJump基准测试。这是NSGA-II首次证明这种交叉的优势。我们的论点可以转移到单目标优化。然后，他们证明，跨界可以以不同的方式加速$（\ MU+1）$遗传算法，并且比以前更为明显。我们的实验证实了交叉的附加值，并表明观察到的加速度甚至比我们的证明所能保证的要大。

进化算法（EAS）是通用优化仪，其具有父母和后代群体的大小或突变率。众所周知，EAS的性能可能在这些参数上急剧上依赖。最近的理论研究表明，自调节参数控制机制在算法运行期间调整参数的调节参数可以在离散问题上可被显着优于最佳静态参数。然而，大多数这些研究有关的Elitist EAB，我们没有明确的答案，以及是否可以申请非Elitist EA。我们研究了一个最着名的参数控制机制，第五个成功规则，控制后代人口尺寸$ \ lambda $ \ llambda $ ea。众所周知，$（1，\ lambda）$ ea有一个尖锐的阈值，关于$ \ lambda $的选择，其中基准函数的预期运行时间onemax从多项式变为指数时间。因此，目前尚不清楚参数控制机制是否能够找到和维护$ \ lambda $的合适值。对于OneMax，我们表明答案是至关重要的，这取决于成功率$ s $（即一+ 1）美元成功规则）。我们证明，如果成功率适当小，则自我调整$（1，\ Lambda）$ EA优化ONEMAX以美元（n）$预期的几代人和$ O（n \ log n）$预期评估任何一元无偏见的黑匣子算法最好的运行时。一个小的成功率至关重要：我们还表明，如果成功率太大，则该算法对onemax具有指数运行计划和具有相似特征的其他功能。

In noisy evolutionary optimization, sampling is a common strategy to deal with noise. By the sampling strategy, the fitness of a solution is evaluated multiple times (called \emph{sample size}) independently, and its true fitness is then approximated by the average of these evaluations. Most previous studies on sampling are empirical, and the few theoretical studies mainly showed the effectiveness of sampling with a sufficiently large sample size. In this paper, we theoretically examine what strategies can work when sampling with any fixed sample size fails. By constructing a family of artificial noisy examples, we prove that sampling is always ineffective, while using parent or offspring populations can be helpful on some examples. We also construct an artificial noisy example to show that when using neither sampling nor populations is effective, a tailored adaptive sampling (i.e., sampling with an adaptive sample size) strategy can work. These findings may enhance our understanding of sampling to some extent, but future work is required to validate them in natural situations.

Evolutionary algorithms (EAs) have found many successful real-world applications, where the optimization problems are often subject to a wide range of uncertainties. To understand the practical behaviors of EAs theoretically, there are a series of efforts devoted to analyzing the running time of EAs for optimization under uncertainties. Existing studies mainly focus on noisy and dynamic optimization, while another common type of uncertain optimization, i.e., robust optimization, has been rarely touched. In this paper, we analyze the expected running time of the (1+1)-EA solving robust linear optimization problems (i.e., linear problems under robust scenarios) with a cardinality constraint $k$. Two common robust scenarios, i.e., deletion-robust and worst-case, are considered. Particularly, we derive tight ranges of the robust parameter $d$ or budget $k$ allowing the (1+1)-EA to find an optimal solution in polynomial running time, which disclose the potential of EAs for robust optimization.

Evolutionary algorithms (EAs) are a kind of nature-inspired general-purpose optimization algorithm, and have shown empirically good performance in solving various real-word optimization problems. During the past two decades, promising results on the running time analysis (one essential theoretical aspect) of EAs have been obtained, while most of them focused on isolated combinatorial optimization problems, which do not reflect the general-purpose nature of EAs. To provide a general theoretical explanation of the behavior of EAs, it is desirable to study their performance on general classes of combinatorial optimization problems. To the best of our knowledge, the only result towards this direction is the provably good approximation guarantees of EAs for the problem class of maximizing monotone submodular functions with matroid constraints. The aim of this work is to contribute to this line of research. Considering that many combinatorial optimization problems involve non-monotone or non-submodular objective functions, we study the general problem classes, maximizing submodular functions with/without a size constraint and maximizing monotone approximately submodular functions with a size constraint. We prove that a simple multi-objective EA called GSEMO-C can generally achieve good approximation guarantees in polynomial expected running time.

健身分配过程将候选解决方案的特征（例如客观值）转换为标量适合度，然后是选择的基础。在频率健身分配（FFA）下，对应于客观值的适应度是其遇到频率，并且可能会最小化。 FFA创建了不偏向更好的解决方案的算法，并且在目标函数值的所有双突发下都是不变的。我们调查FFA对两种理论启发，最先进的EA，贪婪（2 + 1）GA和自调节（1 +λ，λ）的性能的影响。 FFA对他们难以提高他们的表现。我们经验地发现一种基于FFA的算法可以解决本研究中的所有基于理论的基准问题，包括多项式时间中的陷阱，跳跃和强化。我们提出了两种混合方法，该方法使用直接和基于FFA的优化，并发现它们表现良好。所有基于FFA的算法在满足性问题上也比所有纯算法变体更好。

Evolutionary algorithms (EAs) are a sort of nature-inspired metaheuristics, which have wide applications in various practical optimization problems. In these problems, objective evaluations are usually inaccurate, because noise is almost inevitable in real world, and it is a crucial issue to weaken the negative effect caused by noise. Sampling is a popular strategy, which evaluates the objective a couple of times, and employs the mean of these evaluation results as an estimate of the objective value. In this work, we introduce a novel sampling method, median sampling, into EAs, and illustrate its properties and usefulness theoretically by solving OneMax, the problem of maximizing the number of 1s in a bit string. Instead of the mean, median sampling employs the median of the evaluation results as an estimate. Through rigorous theoretical analysis on OneMax under the commonly used onebit noise, we show that median sampling reduces the expected runtime exponentially. Next, through two special noise models, we show that when the 2-quantile of the noisy fitness increases with the true fitness, median sampling can be better than mean sampling; otherwise, it may fail and mean sampling can be better. The results may guide us to employ median sampling properly in practical applications.