一种Byte查找第K个元素的算法研究

查找第K个元素的问题在计算机查找技术中占有十分重要的地位，这个问题的最直接解法是先将序列排序，从而能得到第K个元素，最少需O(nlogn)次比较，即时间复杂度为O(nlogn)．比较好的方法是采用分治策略解决该同题，但其最坏时间复杂度为O(n^2)，平均时间复杂度为O(2n)．本文提出一种Byte解决第K个元素问题的算法，该算法的平均时间复杂度为O(n n／255)，优于以前对该问题的求解方法，而且该算法可以适用于由整数、浮点数、无符号整型数、双精度数和字符型数构成的超大数集．     

带有可控性维护的单机调度问题研究

为在附加费用不大的条件下,通过最小化工件完成时间之和来减小work-in-process中的库存,尽可能使工件按期交付,在将工件调度与机器维护统一进行考虑的模型基础上,提出了带有预防性维护的单机调度问题,并对其进行了建模.将机器的维护周期适当放宽,以便在保证总的附加费用不超出预先给定的一个常数的前提下,实现工件的完成时间和的最小化.对工件加工允许中断的情况给出时间复杂度为O(n*ln(n));对工件加工不允许中断的情况给出一个启发式算法,其时间复杂度为O(n2).由该启发式算法很容易得到问题的可行解,从而为问题的进一步研究打下了基础.     

最大团问题的竞争决策算法

分析了最大团问题的数学性质,根据推导出来的性质设计求解最大团问题的竞争决策算法,且算法的时间复杂度分析结果为O(n~3)。并用提出的算法求解最大团问题中的标准测试示例,测试结果表明,算法具有良好的求解效果。     

一种求解正交约束问题的投影梯度方法

正交约束优化问题在特征值问题、稀疏主成分分析等方面有广泛的应用.由于正交约束的非凸性,精确求解该类问题具有一定的困难.本文提出了一种求解正交约束优化问题的投影梯度算法.该算法采用施密特标准正交化方法处理正交约束,其时间复杂度为O(r2 n),比传统SVD分解复杂度低,且实现简单.数值实验验证了算法的有效性.     

具有交货时间的单机作业调度问题的最优解

基于回溯思想的算法通过系统地搜索解空间可以得到具有交货时间的n个作业的单机作业调度问题的最优解.给出一种改进算法,使得算法的时间复杂度由O(n!)降低到O(nlgn).     

两种带约束的序列比对算法

通过理论证明,得出了当距离函数中惩罚因子φ=0时的解应满足的条件,并在此基础上改进两种最长公共子序列的优化算法,使之能够求解出带约束的序列比对问题.这两种改进算法的时间复杂度分别为O(nmr)和O(nm(r+1)),空间复杂度分别为O(nmr)和O((n+m)(r+1)).推导出算法应满足在两序列中插入的空位符数目分别为(m-l)和(n-l),使比对结果中不会出现错配,保证了比对的质量.实现了基于回溯的改进算法,验证了其求解带约束的序列比对问题的有效性.     

一种求解柔性作业车间调度问题的改进灰狼优化算法

针对柔性作业车间调度问题,以最大完工时间最小化为目标提出了一种改进灰狼优化算法(IGWO),采用两段式的编码方式来构造算法个体位置与调度方案之间的关系,使用基于启发式规则的初始化种群方法来提高初始解的质量.为了平衡算法的全局搜索与局部搜索,提出一种基于双曲正切函数的非线性收敛因子公式,并在算法的个体更新阶段提出了一种基于适应度值的加权方法,在算法决策层嵌入了变邻域搜索算法.通过仿真实验表明,算法在求解柔性作业车间调度问题上是有效的.     

基于混合遗传算法的物流车辆调度优化

针对遗传算法在求解车辆调度问题时容易出现早熟现象,导致求解精度不高的问题,本文用混合算法构建了物流配送总成本最小的目标函数。首先,定义了车辆调度问题的数学模型,在此基础上提出了一种遗传算法中对交叉和变异概率的自适应调整的方法。其次,通过局部搜索算法求得初始解,采用遗传算法初始解优化,并且在配送时刻改变以后,利用TS算法搜索最优解迅速的特点改进配送方案,最终求得配送时刻不断变化下的车辆调度方案。最后通过算例分析,得到本文提出的算法与单一局部搜索算法和单一TS算法相比,在求解精度、求解时间方面都具有更大的优越性。     

弧搜索内点算法

利用弧搜索内点算法对线性规划问题进行求解, 得到该算法的多项式复杂度为O(n^3/4L). 该算法在中心路径的一个宽邻域内, 沿椭圆近似寻找线性规划的最优解. 数值实验表明了该算法的有效性.     

基于遗传粒子群混合的可重入生产调度优化

可重入生产调度优化问题是个NP难问题,针对可重入生产调度的特点,对该优化问题进行数学规划建模,并通过一些定义将模型映射为有向图,以便于智能搜索算法的应用.结合粒子群算法收敛速度快与遗传算法全局搜索能力强的特点,进行优势互补,并优化设计相关参数,构造了一种混合算法.运用混合算法对供应链优化调度问题模型进行求解,与标准遗传算法、粒子群算法的求解结果进行比较,结果表明混合算法有着更好的优化性能.     

有时间窗配送车辆调度问题的禁忌搜索算法

在对有时间窗配送车辆调度问题进行描述的基础上,建立了该问题的基于直观描述的数学模型.通过设计一种新的解的表示方法构造了求解该问题的禁忌搜索算法,并以21个节点的运输网络为例进行了实验计算.计算结果表明,用作者设计的禁忌搜索算法求解有时间窗配送车辆调度问题,不仅可以取得很好的计算结果,而且算法的计算效率较高,收敛速度较快,计算结果也较稳定.     

用改进的协同免疫算法求解Flow Shop调度问题

利用改进的协同免疫算法(improved co-evolutionary immune algorithm,ICIA)求解FlowShop调度问题.算法中的疫苗取自迭代N次的局部最优解,并随着每代最优值的变化不断更新.为了克服协同免疫算法初期收敛速度慢的问题,加入了局部搜索算法;针对算法后期求解目标函数值差的问题,提出了一种新的种群选择机制"80/20法则".通过与遗传算法(genetic algorithm,GA)和未改进的协同免疫算法(co-evolutionary immune algorithm,CIA)比较,仿真实验结果验证了ICIA解决Flow Shop问题的有效性.     

超图的最短路径算法

从超图的强同构引出保持超图顶点间超邻接性的点同构,定义超图的邻接矩阵和赋权超图的权矩阵,并在此基础上得到了求解超图任意顶点间最短路径和求解超图直径的推广Floyd算法.最后通过实例验证了算法的可行性,并与李春明在1994年得到的结果进行比较,得出算法的复杂度为O(n3),该算法是一个有效算法.     

资源受限最小赋权树形图的一种贪婪分解启发式算法

资源受限的最小赋权树形图问题(RMWA)是NP-难的,针对RMWA问题给出一种新的贪婪分解启发式算法.通过分解目标函数和约束条件,把RMWA模型分解成一个最小赋权树形图问题和n个独立的特殊背包问题.对这n个独立的特殊背包问题,设计贪婪算法求其解,其时间复杂度为O(nmlog2m);然后调整该解使其满足树形图的约束条件得到RMWA问题的一个可行解,该算法总的复杂度为O(nm2).最后,给出实例来阐述该贪婪分解启发式算法.     

离散事件仿真的CPU缓存加速算法

针对大规模离散事件仿真的应用需求,提出了CPU(中央处理器)缓存加速算法。采用空间局域化的环型链表存储事件摘要,兼具离散事件仿真(DES)事件分类和缓存加速作用。算法性能分析显示,入队时间复杂度为O(sqrt(n)),出队复杂度为O(1),优于目前主流的日历调度算法及改进算法。100节点9 900并发业务的网络仿真实验结果证实,相比于线性链表算法,文中提出的算法可使DES计算加速21倍。     

基于连续效用子集的资源分配算法

基于离散资源配置选项的实时(或软实时)系统资源分配问题,当以系统整体效用最大化为目标时,属于多维多选择背包问题,直接求解最优值的时间复杂度较高.现有的研究中主要通过使用启发式算法,将其时间复杂度降低为多项式级.这些启发式算法不考虑离散资源配置选项之间的联系,因此在求解中存在一些不必要的计算,而且分配结束后的残留资源不能得到利用.为此通过定义连续效用子集,分析了同一个任务的不同资源配置选项之间的联系.对已有的启发式算法HEU加以改进,提出启发式算法(T-HEU),能够用较低的时间复杂度获得与HEU算法相同的结果.根据同一个连续效用子集中的资源消耗函数的连续性,将残留资源分配问题近似归结为线性规划问题,并提出一种能求得近似最优解的启发式算法RRA_HEU.仿真结果表明,当任务数较少时,RRA_HEU的执行时间少于单纯形法和主-对偶内点法.当任务数较多时,用单纯形法求解残留资源分配问题是合适的.     

分布式两阶段混合流水车间调度

针对分布式两阶段混合流水车间调度问题(DTHFSP),提出一种教学优化算法(TLBO)求解工厂分配问题并设计一种启发式算法解决机器分配问题,以最小化最大完工时间.首先,采用均衡工厂负载的方法生成初始班级;然后,引入淘汰机制以加强对优势解的局部搜索效率,并在自学阶段增加反思过程强化教学结果;最后,通过大量实例实验验证了教学优化算法在求解分布式两阶段混合流水车间调度问题时的搜索优势.结果分析表明教学优化算法在求解分布式两阶段混合流水车间调度方面具有更好的稳定性和求解质量.     

晶圆制造系统中Lot加工序列优化的蚁群算法

针对半导体晶圆制造系统中设备从缓冲区选择Lot加工问题,提出Lot加工序列优化的蚁群算法,对其进行计算时间复杂度分析,并给出了该算法的改进形式.该改进算法是根据晶圆制造系统重入特点,基于瓶颈设备构建蚁群算法求解模型,通过迭代仿真最终获取Lot加工优先序列表.仿真结果表明,采用该算法在短期调度区间内,与一般的基于规则的动态调度算法相比,效果得到了显著的改善.     

基于CRCW规则的BP算法改进

为了充分利用BP算法并行特性采用共写共读(CRCW)规则实现BP算法的并行计算,并对现有的BP算法进行改进,修改动态因子,选择合适的隐藏层个数和修改输出误差函数。经过时间复杂度的分析可以在时间复杂度为O(N),花费为O(N2)内完成BP计算。     

锁定初始调度的紧急工作单机重调度问题

对单机环境下紧急工作的重调度问题进行了研究.初始调度中工作带有到达时间,目标为最小化初始工作的等待时间和;重调度目标是在初始调度锁定的情况下,将紧急工作插入初始调度,最小化紧急工作的最长等待时间.建立了RRLS(reschedulingrushjobswithloadslockedonsinglemachine)问题模型,然后证明了RRLS问题是NP难问题.根据问题性质和特点提出了有效的启发式算法,并给出了算法的时间复杂度.通过实例证明了算法的最优性条件.