演化算法时间复杂性的趋势条件

计算时间复杂性是演化理论中的一个重大课题.将趋势分析引入演化算法的平均时间复杂性分析,可用于很广一类演化算法及许多问题.基于趋势分析,研究了确定演化算法时间复杂性的一些有用的趋势条件.这些条件应用于完全欺骗问题以验证其有效性.     

连续型进化算法首达时间分析的更新理论模型

连续型进化算法首达时间上界研究中需要较强的前提假设且较少关注其下界.文中引入鞅论和更新过程,结合瓦尔德不等式以及更新定理,提出基于增长率的更新理论模型,用于估计进化策略(Evolution Strategies, ES)平均首达时间的上界和下界.更新理论模型依赖算法的初始种群以及增长率概率密度函数,这为进化策略的首达时间分析提供估计优势.为了验证文中更新理论模型,首先计算带均匀变异(1,λ)ES在二维倾斜平面问题上的平均首达时间,得到(1,λ)ES种群规模与时间上下界之间的关系闭合表达式,并且验证平均首达时间与种群规模之间并非负相关.再计算带均匀变异(1,λ)ES在五维超平面问题上的平均首达时间,得到理论计算的上下界闭合表达式.数值实验表明,理论计算的上界和下界与实际运行平均首达时间一致,这为分析进化策略的首达时间提供一种理论工具.     

进化规划算法的时间复杂度分析

进化规划算法是求解连续优化问题的一类进化算法,是进化计算的一个重要分支.在进化规划算法的理论研究上,已有学者证明了其收敛性.然而,进化规划算法的时间复杂度分析是进化计算领域一大难题,目前相关的研究成果很少.基于吸收态Markov过程模型,以期望收敛时间作为研究进化规划算法时间复杂度的指标,提出了进化规划算法期望收敛时间的估算方法,并以此作为算法时间复杂度分析的理论依据.最后分析了Gauss变异进化规划算法的期望收敛时间,作为提出理论的应用举例.     

演化算法的时间复杂性

演化算法在工程领域取得了广泛的应用,但是其基础理论尚未完全建立。文章讨论了演化算法的时间复杂性,提出一个估计(1+1)EA平均计算时间的简单方法,对几个实例的应用显示了该方法分析演化算法计算时间的有效性。     

二元进化策略的收敛性分析

进化算法的理论研究,如收敛性、时间复杂性研究,是当前的一大热点和难点,有关的理论结果并不多。针对二元进化策略(1+1) ES建立时齐马尔科夫过程模型,利用连续状态马氏过程理论证明了与(1+1) ES相关联的马氏过程在一类连续优化问题中具有指数遍历性,在此基础上证明了(1+1)ES在求解此类优化问题时能以概率1最终找到最优解。所提出的分析方法为进化算法的理论研究提供了一条新思路。     

合并排序算法的平均情形复杂性分析及其应用

在合理的“概率分布”假设下,分析了两个有序表合并排序算法的平均情形复杂性,并将此结果应用于个元素的二分排序算法中,最后对二分排序算法的平均情形复杂性进行了估计。     

Levy变异进化规划算法的计算时间分析

连续型进化算法的计算时间分析是目前国内外研究的难题,对此研究了I_cvy变异进化规划(evolutionary programming based on Levy mutation, LEP)算法的计算时间分析理论。具体的分析步骤如下:首先在将LEP算法建模为吸收态Markov过程的基础上,证明了LEP算法的收敛性;然后,结合LEP算法选择算子的特点,以首达最优解的期望时间作为计算时间分析的主要指标;最后,利用I_cvy分布的近似变形给出LEP算法计算时间的估计式。研究结果表明,最优解空间的Lebesgue测度、算法的种群规模和搜索范围对计算时间有直接影响。     

基于随机泛函的免疫进化算法收敛性及性能分析

分析基于免疫响应原理的免疫进化算法流程和运行机制.根据免疫抗体群的状态转移过程,研究免疫进化算法的马尔科夫随机过程,并采用随机泛函分析算法的收敛性,突破传统马尔可夫链方法对解空间较大问题分析的局限性.根据免疫进化算法参数构成和抗体种群达到吸收态的转换特性,采用泛函理论论证算法收敛速度估计、时间复杂度计算和参数选择原则.通过实验总结影响免疫进化算法收敛性的关键因素,为解空间较大及高维优化问题的免疫进化算法收敛性和性能分析提供可行方法.     

Lévy变异进化规划算法的计算时间分析

连续型进化算法的计算时间分析是目前国内外研究的难题,对此研究了Lévy变异进化规划(evolutionary programming based on Lévy mutation,LEP)算法的计算时间分析理论。具体的分析步骤如下:首先在将LEP算法建模为吸收态Markov过程的基础上,证明了LEP算法的收敛性;然后,结合LEP算法选择算子的特点,以首达最优解的期望时间作为计算时间分析的主要指标;最后,利用Lévy分布的近似变形给出LEP算法计算时间的估计式。研究结果表明,最优解空间的Lebesgue测度、算法的种群规模和搜索范围对计算时间有直接影响。     

基于复杂度对开源软件Linux和FreeBSD内核的分析

开源软件内核进化分析是一个较新的研究方向,研究大型自由和开源软件进化可以帮助估计软件体系结构的稳定性,可以较准确地预报软件进化趋势和预报软件进化结果.选取Linux和FreeBSD的多个版本的内核进行数据的收集和处理.采用低层次的度量尺度,利用分析工具SLOCOUNT和CCCC,对提取的内核数据进行复杂度分析,得出开源自由软件进化的结论,并提出了快速测算大型开源软件进化趋势和复杂性的方法.     

交互式遗传算法基于NN的个体适应度分阶段估计

针对交互式遗传算法中人的疲劳问题,提出一种基于神经网络(NN)的个体适应度分阶段估计方法,给出了神经网络估计进化个体适应度与人的评价之问的转换策略以及神经网络学习效果的评价指标,并分析了算法的复杂性．实例结果验证了该方法的有效性。     

超球体检测器覆盖问题的研究

研究表明实值否定选择算法在多维形状空间下呈现出很高的时间和空间复杂性。针对实值否定选择算法中最常采用的超球体检测器,在理论上研究了它的体积,以及体积随半径和维数变化的性质,以此分析了高复杂性出现的原因。针对检测器存在重叠的问题,基于蒙特卡罗方法提出了一个估计检测器覆盖率的算法,用于比较不同检测器生成算法。由于该算法基于随机分布和概率方法,它极大地简化了计算复杂性。     

超球体检测器覆盖问题的研究

研究表明实值否定选择算法在多维形状空间下呈现出很高的时间和空间复杂性.针对实值否定选择算法中最常采用的超球体检测器,在理论上研究了它的体积,以及体积随半径和维数变化的性质,以此分析了高复杂性出现的原因.针对检测器存在重叠的问题,基于蒙特卡罗方法提出了一个估计检测器覆盖率的算法,用于比较不同检测器生成算法.由于该算法基于随机分布和概率方法,它极大地简化了计算复杂性.     

自适应混合多目标分布估计进化算法

针对多目标分布估计算法全局收敛性较弱的缺陷,提出了一种自适应混合多目标分布估计进化算法。其基本思想是:在多目标分布估计算法中引入全局收敛性较强的差分进化算法,当函数变化率较大时,用分布估计算法产生新种群;当函数变化率较小即算法可能陷入局部收敛时,用差分进化算法产生新种群。理论分析和数值实验结果表明,这种混合算法不仅具有良好的全局收敛性,而且解的分布性和均匀性较没有考虑目标函数变化率的混合多目标分布估计算法也有了一定程度的提高。     

一种传感网时间同步和定位的联合线性估计方法

采用时间测量以估计节点位置的方法实现简单,在传感网中得到了广泛的使用。然而节点计时时钟存在漂移和偏离,导致时间测量不准确。为此文本以节点时钟漂移和偏离模型为基础,提出了一种时间同步和节点定位的联合线性估计方法,包括最小平方（LS）及权重最小平方（WLS）方法。仿真测试了所设计算法的运行时间,分析了噪声对联合估计方法的估计误差影响。结果表明,LS及WLS线性估计方法运算速度较半正定（SDP）算法快,在低噪声条件下LS及WLS线性估计方法具有较高的稳定性和定位精度。     

基于分布估计算法的朴素贝叶斯分类问题研究

随着基础理论研究所取得的一系列进展,分布估计算法逐渐成为进化计算研究领域的一个新的研究方向,并成为当今国际进化算法研究的新热点。采用机器学习的方法分析数据、指导搜索已经成为设计新算法的趋势。将分布估计算法引入到朴素贝叶斯分类器系统中,设计基于基尼指数的适应度函数,从而进一步提高朴素贝叶斯分类器的性能。     

分布估计算法研究进展

作为一种新颖的基于概率模型的进化算法,近年来分布估计算法（EDA）得到了广泛的研究和发展.在介绍分布估计算法原理和特点的基础上,重点综述了近些年分布估计算法的研究进展,包括改进概率模型、保持种群多样性以及设计混合算法,进而总结了分布估计算法在理论及应用方面的研究现状,最后提出了有待进一步研究的若干方向和内容.     

分布估计算法综述

分布估计算法是进化计算领域新兴起的一类随机优化算法，是当前国际进化计算领域的研究热点. 分布估计算法是遗传算法和统计学习的结合，通过统计学习的手段建立解空间内个体分布的概率模型，然后对概率模型随机采样产生新的群体，如此反复进行，实现群体的进化. 分布估计算法中没有传统的交叉、变异等遗传操作，是一种全新的进化模式；这种优化技术能够通过概率图模型对变量之间的关系进行建模，从而能有效的解决多变量相关的优化问题. 根据概率模型的复杂性，本文按照变量无关、双变量相关、多变量相关等三类分别介绍相应的分布估计算法. 作为一篇综述性文章，本文旨在全面系统的向国内读者介绍这一新技术，并总结分布估计算法的研究现状和未来的研究方向.     

AKS算法对现代密码学的影响

最近,印度的三个计算机科学家ManindraAgrawal、NeerajKayal和NitinSaxena提出了一个称为AKS的算法。笔者使用这个算法证明了可在多项式时间内对一个整数是否为素数进行确定性的判定,从而解决了一个古老的数学问题。这个结果对于数论和计算复杂性理论的研究与发展具有重要意义。由于现代密码学正是建立在整数分解理论和计算复杂性理论的基础之上,因此这个算法对现代密码学的影响引起了人们的关注。该文将就此进行阐述。     

数据流中频繁模式的评估与维护

研究了数据流中频繁模式的挖掘问题，主要贡献在于：(1)基于启发式思想方法和抽样理论的基础上，提出了基于数据流样本集的分步模式估计方法；(2)算法求解所有长度的模式，而不仅仅是单项集模式；(3)为了找到满足精度要求的恰当的数据流样本集长度，引入了Hoeffding bound理论，并进行了修正，从而使之更适合于这一问题：(4) 提出了对估计模式进行在线维护的方法．基于上述方法的基础上，提出了模式估计和维护算法．最后，通过和已有算法进行实验对比分析，结果表明，该算法在结果精度、空间、时间复杂性等方面都适合进行数据流的分析．