组合设计提供了一个有趣的优化问题来源。其中,给出了在电力线通信,闪存和块密码中的应用程序的应用特别感兴趣。本文通过开发迭代方法来解决进化算法(EA)的排列码的设计。从单个随机排列开始,通过使用基于置换的ea来逐渐增加满足最小距离约束的新排列。我们调查了针对四种不同的健身功能的方法,针对不同级别的细节的最小距离要求,并有两种不同的关于代码扩展和修剪的政策。我们比较我们的EA方法实现的结果,即简单的随机搜索,答案既没有用问题大小衡量。
translated by 谷歌翻译
我们考虑通过删除指定的线路从更大的一个构造从更大的阵列(OA)构建二进制正交阵列(OA)的优化问题。特别地,我们开发一种遗传算法(GA),其中底层染色体是指定从起始OA取消的线路的恒定重量二进制字符串。然后通过平衡的交叉和突变算子来演化这种染色体以保持它们中的数量。健身功能通过测量从比起始的OA的约束量测量它们的距离来评估从这些染色体获得的基质。我们通过将初始OA制定作为基本奇偶校验阵列的几个块的随机置换来执行提出的遗传算法的初步实验验证,从而保证了最佳解决方案的存在。
translated by 谷歌翻译
我们继续研究遗传算法(GA)在组合优化问题上,候选解决方案需要满足平衡性约束。已经观察到,临时交叉和突变操作员授予的搜索空间大小的减小通常不会转化为GA性能的实质性改善。尽管怀疑平衡的代表可能会产生更不规则的健身景观,但仍然没有明确的解释,尽管该景观可能会更难以使GA融合到全球最佳距离。在本文中,我们通过将局部搜索步骤添加到具有平衡运算符的GA,并使用它来进化高度非线性平衡的布尔功能,从而调查此问题。特别是,我们围绕两个研究问题组织了实验,即如果本地搜索(1)提高了GA的收敛速度,并且(2)降低了人口多样性。令人惊讶的是,尽管我们的结果肯定地回答了第一个问题,但他们还表明,添加本地搜索实际上\ emph {增加}人口中个人之间的多样性。我们将这些发现与有关布尔功能问题的健身景观分析的最新结果联系起来。
translated by 谷歌翻译
S-boxes are an important primitive that help cryptographic algorithms to be resilient against various attacks. The resilience against specific attacks can be connected with a certain property of an S-box, and the better the property value, the more secure the algorithm. One example of such a property is called boomerang uniformity, which helps to be resilient against boomerang attacks. How to construct S-boxes with good boomerang uniformity is not always clear. There are algebraic techniques that can result in good boomerang uniformity, but the results are still rare. In this work, we explore the evolution of S-boxes with good values of boomerang uniformity. We consider three different encodings and five S-box sizes. For sizes $4\times 4$ and $5\times 5$, we manage to obtain optimal solutions. For $6\times 6$, we obtain optimal boomerang uniformity for the non-APN function. For larger sizes, the results indicate the problem to be very difficult (even more difficult than evolving differential uniformity, which can be considered a well-researched problem).
translated by 谷歌翻译
过去已经表明,与解决多模式问题生成器的解决实例相比,多座丘陵策略与标准遗传算法相比有利。我们扩展了这项工作,并验证遗传算法中多样性保存技术的利用是否改变了比较结果。在两种情况下,我们这样做:(1)​​目标是找到全局最佳距离时,(2)当目标是找到所有Optima时。进行了数学分析,用于多设山丘算法,并通过实证研究进行了经验研究,以求解多模式问题生成器的实例,其中包括山丘策略以及遗传算法的数量,并使用遗传算法进行了元素。尽管小甲基元素改善了遗传算法的性能,但它仍然不如这类问题上的多尽山关闭策略。还提出了一种理想化的细分策略,并认为它的性能应接近任何进化算法在此类问题上可以做到的。
translated by 谷歌翻译
在进化计算中使用非豁免主义时的一个希望是放弃当前最佳解决方案的能力,艾滋病们离开本地最佳效果。为了提高我们对这种机制的理解,我们对基本的非精英进化算法(EA),$(\ mu,\ lambda)$ ea进行严格的运行时分析,在最基本的基准函数上,具有本地最佳的基本基准函数跳跃功能。我们证明,对于参数和问题的所有合理值,$(\ mu,\ lambda)$ ~ea的预期运行时间除了下订单条款之外,至少与其Elitist对应的预期运行时间,$(\ mu + \ lambda)$〜ea(我们对跳转功能进行第一个运行时分析以允许此比较)。因此,$(\ mu,\ lambda)$ ~ea将本地最优方式留给劣质解决方案的能力不会导致运行时优势。我们补充了这个下限的下限,即对于参数的广泛范围,与我们的下限不同,与下顺序不同。这是一个在多模态问题上的非精英算法的第一个运行时结果,除了下订单术语。
translated by 谷歌翻译
分布算法(EDA)是优化算法,在搜索空间上学习分布,可以轻松地采样良好的解决方案。大多数EDA的关键参数是样本量(人口尺寸)。如果人口规模太小,则概率模型的更新基于很少的样本,从而导致遗传漂移的不期望效应。人口太大避免了遗传漂移,但减慢了这一过程。基于对种群规模如何导致遗传漂移的最新定量分析,我们为EDA设计了一种智能的正式机制。通过停止运行,当遗传漂移的风险很高时,它会自动以良好的参数状态运行EDA。通过数学运行时分析,我们证明了此智能总结方案的一般性能保证。这特别表明,在许多情况下,已知最佳(特定问题)参数值,重新启动方案会自动找到这些,从而导致渐近最佳性能。我们还进行了广泛的实验分析。在四个经典的基准问题上,我们清楚地观察了人口规模对性能的关键影响,并且我们发现智能重点方案会导致具有最佳参数值可获得的性能。我们的结果还表明,先前基于理论的最佳人口规模的建议远非最佳群体,从而导致表现明显不如通过智能重点方案获得的表现。我们还对文献,最大切割问题和两部分问题的两个组合优化问题进行了PBIL(跨熵算法)进行实验。同样,我们观察到,智能设施的机制比文献中建议的人口规模更高,从而导致表现更好。
translated by 谷歌翻译
非主导的分类遗传算法II(NSGA-II)是现实应用中最强烈使用的多目标进化算法(MOEA)。然而,与几个通过数学手段分析的几个简单的MOES相反,到目前为止,NSGA-II也不存在这种研究。在这项工作中,我们表明,数学运行时分析也可用于NSGA-II。结果,我们证明,由于持续因素大于帕累托前方大小的人口大小,具有两个经典突变算子的NSGA-II和三种不同的选择父母的方式满足与Semo和GSEMO相同的渐近运行时保证基本ineminmax和Lotz基准函数的算法。但是,如果人口大小仅等于帕累托前面的大小,那么NSGA-II就无法有效地计算完整的帕累托前部(对于指数迭代,人口总是错过帕累托前部的恒定分数) 。我们的实验证实了上述研究结果。
translated by 谷歌翻译
为了更好地了解进化算法(EAS)如何应对恒定健身的平台的理论理解,我们提出了$ N $ -dimensional高原$ _K $函数作为天然基准,分析$(1 + 1)$的不同变体EA优化它。高原$ _K $函数在最佳的半径k $的半径k $的第二个最佳健身高原。作为进化算法,我们使用任意无偏的突变算子以$(1 + 1)$ EA。用$ \ alpha $ \ alpha $ \ alpha的随机数量在这个运算符的应用中,并假设$ \ pr [\ alpha = 1] $至少具有一些小的子常值,我们展示了所有常量的令人惊讶的结果$ k \ ge 2 $,运行时$ t $遵循靠近几何一个的分布,其中成功概率等于翻转的概率为1 $和$ k $ bits除以高原的大小。因此,预期的运行时是该号码的倒数,因此只取决于翻转1美元和$ k $位之间的概率,而不是突变运算符的其他特征。我们的结果也意味着这里标准位突变的最佳突变率约为k /(en)$。我们的主要分析工具是在搜索点空间和汉明级空间上的马尔可夫链的综合分析,这是一种对其他高原问题也有用的方法。
translated by 谷歌翻译
算法配置(AC)与对参数化算法最合适的参数配置的自动搜索有关。目前,文献中提出了各种各样的交流问题变体和方法。现有评论没有考虑到AC问题的所有衍生物,也没有提供完整的分类计划。为此,我们引入分类法以分别描述配置方法的交流问题和特征。我们回顾了分类法的镜头中现有的AC文献,概述相关的配置方法的设计选择,对比方法和问题变体相互对立,并描述行业中的AC状态。最后,我们的评论为研究人员和从业人员提供了AC领域的未来研究方向。
translated by 谷歌翻译
跳跃功能是随机搜索启发式理论中的{最多研究的非单峰基准,特别是进化算法(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 $的因子多项式慢。计算地,新类允许使用更宽的健身谷的实验,特别是当它们远离全球最佳时。
translated by 谷歌翻译
在生物启发群体的成群制中拥挤的环境中,最近出现了SALP群优化(SSO)算法并立即获得了很多动量。灵感来自Salp殖民地的特殊空间排列,在领导者之后的长链中移位,该算法似乎提供了有趣的优化性能。然而,原创作品的特点是一些概念和数学缺陷,影响了对象的所有作品。在本手稿中,我们对SSO进行了一次关键审查,突出了文献中存在的所有问题及其对通过该算法进行的优化过程的负面影响。我们还提出了一个数学上正确的SSO版本,名为“修正的SALP Swarm Optimizer(ASSO)”,该SALP Swarm Optimizer(ASSO)修复了所有讨论的问题。我们在一系列定制的实验上基准测试ASOO的表现,表明它能够实现比原始SSO更好的结果。最后,我们进行了广泛的研究,旨在了解SSO及其变体是否提供与其他美术学相比的优势。实验结果,其中SSO不能优于简单的众所周知的核心学,表明科学界可以安全地放弃SSO。
translated by 谷歌翻译
排名汇总旨在将许多替代品的偏好排名与不同选民的偏替排名组合成单一共识排名。然而,作为各种实际应用的有用模型,它是一个计算上有挑战性的问题。在本文中,我们提出了一种有效的混合进化排名算法来解决完整和部分排名的排名聚集问题。该算法具有基于协调对的语义交叉,并通过有效的增量评估技术加强了较晚的验收本地搜索。进行实验以评估算法,与最先进的算法相比,表明基准实例上具有高度竞争性能。为了展示其实际有用性,算法应用于标签排名,这是一个重要的机器学习任务。
translated by 谷歌翻译
最近,已经进行了NSGA-II的第一个数学运行时分析,这是最常见的多目标进化算法(Zheng,Liu,Doerr(AAAI 2022))。继续这一研究方向,我们证明了NSGA-II在使用交叉时,渐近渐近地测试了OneJumpZeroJump基准测试。这是NSGA-II首次证明这种交叉的优势。我们的论点可以转移到单目标优化。然后,他们证明,跨界可以以不同的方式加速$(\ MU+1)$遗传算法,并且比以前更为明显。我们的实验证实了交叉的附加值,并表明观察到的加速度甚至比我们的证明所能保证的要大。
translated by 谷歌翻译
分类是数据挖掘和机器学习领域中研究最多的任务之一,并且已经提出了文献中的许多作品来解决分类问题,以解决多个知识领域,例如医学,生物学,安全性和遥感。由于没有单个分类器可以为各种应用程序取得最佳结果,因此,一个很好的选择是采用分类器融合策略。分类器融合方法成功的关键点是属于合奏的分类器之间多样性和准确性的结合。借助文献中可用的大量分类模型,一个挑战是选择最终分类系统的最合适的分类器,从而产生了分类器选择策略的需求。我们通过基于一个称为CIF-E(分类器,初始化,健身函数和进化算法)的四步协议的分类器选择和融合的框架来解决这一点。我们按照提出的CIF-E协议实施和评估24种各种集合方法,并能够找到最准确的方法。在文献中最佳方法和许多其他基线中,还进行了比较分析。该实验表明,基于单变量分布算法(UMDA)的拟议进化方法可以超越许多著名的UCI数据集中最新的文献方法。
translated by 谷歌翻译
传统的统计技术或元启发式学很难解决大多数现实世界的优化问题。主要困难与存在相当数量的局部Optima有关,这可能导致优化过程的过早收敛性。为了解决这个问题,我们提出了一种新型的启发式方法,用于构建原始功能的平滑替代模型。替代功能更容易优化,但保持原始坚固的健身景观的基本属性:全球最佳的位置。为了创建这样的替代模型,我们考虑通过自我调整健身函数增强的线性遗传编程方法。所提出的称为GP-FST-PSO替代模型的算法在搜索全局最优值和原始基准函数的视觉近似(在二维情况下)的视觉近似都可以达到令人满意的结果。
translated by 谷歌翻译
最近,已经进行了多目标进化优化器NSGA-II的第一个数学运行时分析(AAAI 2022,GECCO 2022(出现),ARXIV 2022)。我们通过对由两个多模式目标组成的基准问题进行该算法的第一个运行时分析继续进行这一研究。我们证明,如果人口尺寸$ n $至少是帕累托阵线的四倍,那么NSGA-II具有四种不同方法的NSGA-II选择父母,并且位于Bit Wise突变将优化OnejumpzeroJump基准,其跳高尺寸〜$ 2 \ le lek \ le n/4 $ in Time $ o(n n^k)$。当使用快速突变(最近提出的重型突变操作员)时,此保证将提高$ k^{\ omega(k)} $。总体而言,这项工作表明,NSGA-II至少与全球SEMO算法有关OnejumpZeroJump问题的局部优势。
translated by 谷歌翻译
大多数现实世界中的问题本质上都是多模式,由多个最佳值组成。多模式优化定义为找到函数的多个全局和局部优化(与单个解决方案相反)的过程。它使用户可以根据需要在不同的解决方案之间切换,同时仍保持最佳系统性能。基于经典梯度的方法未能用于优化问题,因为目标函数是不连续的或不可差的。与需要多个重新启动的经典优化技术相比,进化算法(EAS)能够在单个算法运行中以单个算法运行中的多个解决方案找到多个解决方案,以找到不同的解决方案。因此,已经提出了一些EA来解决此类问题。但是,差异进化(DE)算法是一种基于人群的启发式方法,可以解决此类优化问题,并且可以易于实施。多模式优化问题(MMOP)的潜在挑战是有效地搜索功能空间以准确地定位大多数峰。优化问题可能是最大程度地减少或最大化给定的目标函数,我们旨在解决本研究中多模式功能的最大化问题。因此,我们提出了一种称为增强对立差异进化(EODE)算法的算法来求解MMOP。拟议的算法已在IEEE进化计算(CEC)2013基准功能上进行了测试,并且与现有的最新方法相比,它取得了竞争性结果。
translated by 谷歌翻译
图形着色问题(GCP)是计算机科学中最受研究的NP艰难问题之一。给定图形,任务是为所有顶点分配颜色,使得没有共享边缘的顶点接收相同的颜色并且使用的颜色的数量是最小的。已经应用了不同的启发式,元启发式,机器学习和混合解决方法来获得解决方案。解决这个问题,我们使用进化算法的突变。为此目的,我们介绍了图形着色问题的二进制编码。这种二进制编码有助于我们轻松突变,评估,免疫系统和合并颜色,并动态减少着色。在用于图形着色的传统进化算法(EA)中,使用k着色方法​​,并重复运行EA直到达到最低点。在我们的论文中,我们从色度数字的理论上限开始,即最大程度+ 1和进化过程中的一些颜色是未使用的,以动态减少每一代中的颜色数量。我们测试几个标准的Dimacs基准并比较怨恨纸张。最大结果与预期的色彩颜色相同,并且很少的数据集大于预期的色度
translated by 谷歌翻译
基准套件提供了对进化算法解决问题能力的有用度量,但是组成问题通常太复杂了,无法清洁算法的优势和劣势。在这里,我们介绍了基准套件档案(``进化运行中的选择方案的诊断概述''),以实证分析有关剥削和探索重要方面的选择方案。利用从根本上是攀岩,但我们考虑两种情况:纯剥削,可以独立优化表示形式中的每个位置,并且受到限制的利用,在该位置之间,由于位置之间的相互作用,向上进展更加有限。当优化路径不太清楚时,需要探索;我们认为能够遵循多个独立的爬山途径和跨健身山谷的能力。这些场景的每种组合都会产生独特的适应性景观,有助于表征与给定选择方案相关的进化动力学。我们分析了六个流行的选择方案。锦标赛的选择和截断选择都在剥削指标方面表现出色,但在需要探索时表现不佳;相反,新颖的搜索在探索方面表现出色,但未能利用梯度。在克服欺骗时,健身共享表现良好,但在所有其他诊断方面都很差。非主导的分类是维持由居住在多个Optima居住的个体组成的不同人群的最佳选择,但努力有效利用梯度。词汇酶选择平衡搜索空间探索而不牺牲剥削,通常在诊断方面表现良好。我们的工作证明了诊断对快速建立对选择方案特征的直观理解的价值,然后可以将其用于改进或开发新的选择方法。
translated by 谷歌翻译