基于多表达式基因编程的复杂函数挖掘算法

传统的基因表达式编程(Gene Expression Programming) 挖掘复杂函数时,存在进化辈数过大、无法跳出局部最优解等问题,提出了基于多表达式基因编程的遗传进化算法,提高GEP的全局寻优能力, 提出了一种新的多表达式基因编程的遗传进化算法(Multi Expression Gene Programming, MEGP),建立了同一染色体内基因多层次编码、解码模型,理论上分析并比较了MEGP算法的表达空间复杂性,实现了多表达染色体遗传进化算法和染色体适应度评价算法.实验表明, 在解决函数挖掘问题中, MEGP成功率是传统GEP的2～4倍.     

基于GEP基因约简策略的多项式因式分解

将基于基因表达式编程(GEP)的公式发现技术用于多项式因式分解。对标准GEP中个体染色体适应度评价算法和遗传算子进行了改进,提出了一种新的基于GEP的基因约简算法及多项式因式发现算法(以下称FactorGEP算法),分析了多项式因式发现的特殊困难,提出了将有效基因个数作为适应度评价因素的解决方案。试验结果表明,FactorGEP算法完全不需要关于分解的多项式的任何先验知识,可以自动对多项式进行因式分解,并找到最佳的分解。     

基于RFID与基因表达式编程的经济统计时序挖掘

为解决基因表达式编程(GEP)在符号回归、RFID分类及经济领域中对时序数据的挖掘速度和精度还不够的问题,提出了统计基因、统计染色体和统计时序-适应度的定义,并针对传统GEP经济时序模型进行了综合改进;提出了新颖的单变量时序和多变量时序挖掘算法,提高了GEP统计时序挖掘的速度和精度;实验表明,与传统GEP、单变量GEP时序算法相比,多变量GEP时序算法挖掘速度快,其预测精度比单变量时序算法高出5%以上.该算法同样适用于RFID以及其他经济系统中的时序数据挖掘.     

CEA:基于弱势种群保护抗早熟的聚类淘汰算法

传统基因表达式编程算法(GEP)决定个体遗传权时过分依赖适应度,忽略了个体间相互关系,造成GEP算法易早熟而影响进化效率.为克服该问题,从理论上研究了造成GEP早熟的原因,并根据研究结果提出弱势种群保护抗早熟的聚类淘汰算法CEA(cluster-elutriate Algorithm);定义β-cluster及相关概念;用种群所含不同簇的数量来度量种群的多样性达到保护弱势种群.利用概率手段详细分析了个体参与下一代的机率.实验表明,基于CEA的算法能很好的防止GEP函数发现时的早熟现象,且极大地提高了函数发现效率.     

基于多目标基因表达式编程的电路演化算法

为提高电路演化的效率和成功率,对电路设计中涉及的多个目标进行了定义与量化,并针对多目标优化问题,在基因表达式编程（GEP：Gene Expression Programming）的基础上,提出了基于多目标基因表达式编程的电路演化算法（MGEP：Multi-Objective Gene Expression Programming）。设计了演化电路中的GEP编码,定义和量化了电路演化的多个目标,利用非支配排序和适应度共享策略提高搜索方向的空间均匀性。通过数字电路演化实验证明,MGEP算法与GP算法相比进化时间减少了72．9％,同时得到的电路更简单实用,得到最优电路的比率分别比GP和传统的GEP提高了50．4％和38．9％。     

基于均值查找的快速中值滤波算法

针对传统中值滤波算法时间复杂度高、运行速度慢,难以满足大型图像数据实时处理的问题,提出了一种快速中值滤波算法,将确定中值元素的过程由排序运算转换为基于均值对集合的二分查找,算法不依赖于滤波窗口的形状以及相邻窗口的相关信息,有效提高了中值滤波的执行效率,使传统中值滤波算法的时间复杂度由O(nln n)下降至O(n).实验中,该算法应用于大型图像序列的滤波处理,其运算速度提高到传统中值滤波算法的3倍以上,并且算法运行时间仅随滤波窗口大小线性增长,可以满足大尺度滤波窗口对大型图像数据实时处理的需求,具有显著的实际应用价值.     

线性划分问题的一个改进算法

给定一个由n个非负数构成的序列X={x1, x2, …, xn}及正整数k≤n, 线性划分问题要求将该序列划分为不大于k段子序列,使得最小化各段子序列元素之和为最大值。目前已知该问题的最好算法是时间复杂度为O(kn2)和空间复杂度为O(kn)的动态规划算法。利用非负数序列的性质,给出一个快速改进算法,其时间复杂度为O(knlogn),空间复杂度为O(n)。     

快速跳出局部最优的VPS-GEP算法

传统GEP(Gene Expression Programm ing)算法存在局部收敛方面的缺陷,为了解决这一问题,提出了可以使进化快速跳出局部最优的VPS-GEP(Various Popu lation Strategy GEP)算法,证明了在概率意义上GEP平均每代进化所耗时间与群体规模成正比,用两个标准测试函数和一个标准测试数据集测试了VPS-GEP算法的函数挖掘能力和效率。实验表明,VPS-GEP算法可以减少进化停滞代数55%以上。     

基于极值索引的数据排序算法

提出一种新的数据排序算法,将数学极值的求解原理与数据排序结合,把极小值的概念扩展到记录的序列中,并按数据的排列规律,建立了极小记录索引,通过索引快速搜索待排序列中的记录,对待排序列快速的排序。该算法的最大时间复杂度T(n)为O(nlogn)和空间复杂度O(n),在提高排序效率的同时,保证了排序结果中的相同大小记录之间相对位置的稳定。     

种群多样性的GEP算法在预测中的研究和应用

针对传统的基因表达式编程(Gene Expression Programming,GEP)算法在函数发掘时容易陷入过早收敛和局部最优问题,提出了一种基于种群多样性的GEP(GEP based on population diversity,PD-GEP)算法。该算法提出了简单云改进GEP策略,利用简单云改进了常数创建方法,并设计了云变异算子和云交叉算子动态调整其变异和交叉概率,以保证种群的多样性。同时提出了种群的有效交叉策略,引入新个体更新种群,避免早熟收敛,提高进化效率。最后将其应用于工程实例中,并将其结果与传统GEP算法结果进行比较。研究结果表明:该算法提高了预测精度和收敛速率,具有更好的收敛性。     

半定锥上具有O(n1/2L)复杂性的Mehrotra型预估矫正算法

文中将文献线性规划中的Mehrotra型预估矫正算法推广到半定规划,提出一种求解半定规划问题的Mehrotra型预估矫正算法,该算法基于NT方向,证明了该算法具有目前最好的的迭代复杂性O(n^1/2L).     

内嵌基因表达式编程及其在函数发现中的应用

为了提高表达效率,提出了新的基因解码方案,形成了内嵌基因表达式编程算法EGEP;提出了极大表达树、嵌套表达树和拼接表达树等概念;分析了基因的表达空间和算法的复杂度.实验表明,该算法提高了函数发现的成功率;在小规模种群的函数中其能力明显优于GEP.在单基因情况下,目标为一元函数和二元函数时,EGEP平均成功辈数分别为GE...     

广义自缩序列在C语言程序设计中的实现

根据广义自缩序列的基本思想,对加密应用中该序列的产生进行了C语言程序设计,并通过Games-Chan算法的检验,说明产生的广义自缩序列具有良好的线性复杂度.     

线性互补问题的邻域跟踪算法

文章把艾文宝的邻域跟踪算法推广到单调线性互补问题（LCP）,由于单调LCP的迭代方向不再具有正交性,因此算法的理论分析变得复杂。证明了算法的迭代复杂性为0（√nL）,并且通过证明对偶间隙的单调性,使得算法易于执行。     

一个新的线性规划预校正算法

提出了一种新的线性规划预校正算法,预步是取的Ｅｕｌｅｒ方向,算法复杂度为Ｏ（n~(1/2)Ｌ）     

IP网络中端到端时延估计方法

提出了一种新的估计端到端时延的方法--往返规划算法,它是基于已有的线性规划算法,同时对相对两个方向上的时延进行测量,把不同分组在相对方向上的时延之和看作为同一个分组的“往返时延”以消除通信双方时钟时间差对端到端时延的影响,当相对方向上经历最小时延的分组在不同时刻发送时,这个“往返时延”还受到双方时钟频率差的影响,算法采用了调整其中任一分组发送时刻的方法消除此影响,并与线性规划算法以及Paxson算法作了性能比较,理论及实验结果均表明在不增加复杂度的前提下往返规划算法估计出的端到端时延更加准确.     

求解单调线性互补问题的邻域跟踪内点算法

把艾文宝的邻域跟踪算法推广到单调线性互补问题（LCP）,用2-范数代替1-范数来定义宽邻域。由于单调LCP的迭代方向不再具有正交性,因此算法的理论分析比线性规划复杂。证明了算法的迭代复杂性为O（n～（1/2）L）。通过证明对偶间隙关于搜索步长的单调性,使得算法易于执行。数值实验显示了该算法的有效性。     

寻找平面上点的凸壳

对格雷厄姆算法进行了改进,编程实现寻找平面上n个点的凸壳,并通过1次循环就找出所有凸壳的顶点.该算法的空间复杂度为O(n-3),其时间复杂度在最坏情况下虽然无法突破O(nlogn)的理论下限,但在最好情况下已达到线性水平.