基于设施选址问题的费用分配问题的近似算法

许多有着重要理论和应用价值的最优化问题在算法复杂性上都是NP-hard的,其解决方法之一是近似算法。论文研究了与设施选址问题密切相关的费用分配问题,并利用原始与对偶线性规划的思想和无容量设施选址问题的一个1.52-近似算法[1]给出了该问题的一个更好的近似算法。     

P_4|fix|C_(max)问题的最优规则调度算法

多处理机任务调度问题P4|fix|Cmax(m≥=)是典型的强NP难问题,由于其在并行环境中的实际意义而受到越来越多的关注.但在一般情形下,寻求该问题的较为理想的近似算法是极其困难的,通常从较少处理机数的系统着手研究.对于m=4的情形,文中研究了P4|fix|Cmax的规则调度算法,通过引入组调度技术,给出了该问题的一个线性时间的4/3-近似算法,并证明了该算法是4-处理机系统中的最优规则调度算法.     

多处理器任务调度问题的新近似算法

研究任务有多种处理方式的多处理器任务调度问题（MTS）的求解算法，给出求解这种问题的二阶段方法：第1阶段为指派问题，第二阶段调度问题Pm｜fixj｜Cmax，从而得到一个新的求解Pm｜setj｜Cmax。近似算法的方法，并针对P4｜fixj｜Cmax给出了具体算法，证明这种近似算法是一个2-逼近度算法，是文献中在4-处理器问题上的推广。     

基于设施选址的Steiner问题的算法

在设施选址问题的基础上给出了广义Steiner树-星问题的两个近似比分别为3．55和3．582的近似算法,并在问题转化的基础上研究了其他若干特殊情形的Steiner树问题的近似算法。     

一类NP—完全问题在阈图上的解

本文给出了判定阈图是否为哈密顿图的多项式时间算法,并证明了阈图上STEINER树问题是NP-完全的,给出解答它的多项式时间近似算法。     

基于LIB的有色箱覆盖问题

提出了如下定义的受位置约束的有色箱覆盖问题,即在有色物品的箱覆盖过程中,要求重(长)的物品置于轻(短)的物品下方.该问题是一个新的组合优化问题,来源于多处理器任务调度.给出一个求解该问题的局内近似算法KC-LIBFF算法,分析其最坏情况渐进性能比为0,并给出了相应的实验结果;进一步对求解该问题的局内算法性能比的下界进行了讨论.     

使用混合人工鱼群算法求解装箱问题

装箱问题在实际生产中应用非常广泛,在分析该问题特点的基础上提出了使用类CF近似算法和人工鱼群算法相结合的混合人工鱼群算法求解装箱问题,并给出了具体的算法步骤。跟遗传算法的对比试验结果表明该算法在求解装箱问题所得的结果优于遗传算法,具有良好的应用前景。     

任意处理时间的多处理机任务调度近似算法

研究多处理机任务调度模型P_mfixC_max,即在m个处理机系统中调度n个多处理机任务,每个任务指派到所需一组处理机上不可剥夺地执行。该问题应用广泛但早已证明为NP难问题,而且也不存在常数近似算法。在E.Bampis等人提出的Split-Round技术基础上,提出了该问题的一个改进的多项式时间近似算法,并从理论上证明了该算法在最坏情况下的近似比为2(2m)^-2,优于E.Bampis等人给出的3m^-2的结果。     

瓶颈Steiner网络设计问题的算法研究

瓶颈Steiner网络设计问题要求从网络中找出一个满足某种瓶颈条件的Steiner树,由于该问题的NP困难性,因此必须找出它的近似算法。该文针对树和一般图这2种网络情形,在问题转化的基础上分别给出了基于分组Steiner问题的近似算法,在Marathe等算法思想的基础上给出了有根和无根2种情形下的2个近似算法。     

计算生物学中的9叶星树问题

本文讨论翻转距离星树问题,证明实例中有向符号序列个数为9时,翻转距离星树问题问题是NP-难解问题,并给出了一个该问题的多项式时间近似算法.     

k-Shifts算法在一类批量计划编制中的应用

分析了冶金行业常见的一类批量计划编制问题,给出了这类组合优化问题的数学模型;分析并证明了传统k-Opt算法不适合这类非对称性组合优化问题,提出将1-Shift算法扩展为k-Shifts算法,为求得近优解提供保证;缩小了k-Shifts算法的搜索空间,大大降低了k-Shift算法时间复杂度;改进了优化目标评价函数,大幅度提高求解性能。改进后的算法成功地解决了这一类NP问题,实验证明了在多项式时间复杂度内可以求出近似于问题全局最优值的解。     

利用人工鱼群算法实现基于MP的信号稀疏分解*

人工鱼群算法（AFSA）是一种新的智能优化算法,具有鲁棒性强、全局收敛性好,及对初值的不敏感性等特点。将人工鱼群算法运用到信号的稀疏分解中,可快速寻找匹配追踪(MP)过程中每一步分解的最佳原子。此方法提高了信号稀疏分解的速度,算法的有效性为实验结果所证实。     

一种带权重的真值流推理算法

研究了真值流推理算法在各种推理模式下的还原性,证明了真值流推理算法在单一规则下是具有还原性的.但是,在采用常用的推理模型进行推理时,真值流推理算法并不具有多重多维情形下的还原性.为了解决这个问题,提出了一种带权重的真值流推理算法,并证明了该新算法具有多重多维情形下的还原性.     

基于改进遗传算法的优化计算

针对经典遗传算法在优化计算中存在的弊端,提出改进遗传算法。该算法考虑了优化问题的全局性要求—结合区间压缩方法,而这往往比局部最优理论和方法困难的多;同时通过对变异算子改进,对遗传算法早熟收敛性方面得到有效控制,最后,给出算法的收敛性证明及收敛性准则。实验表明该算法是有效的。     

基于模糊免疫算法的溶剂脱水塔软测量

在实数编码免疫算法的基础上引进了模糊控制技术,对免疫算法中的两个关键参数实现了模糊自适应调整,很好地解决了基本免疫算法中收敛精度低和寻优速度慢的缺点。模糊免疫算法被用于优化BP神经网络的结构和参数。结果表明,不但网络的结构得到控制,而且泛化性能有了较大的提高;同时,算法在优化神经网络上的有效性也在溶剂脱水塔醋酸浓度软测量建模中得到很好地证实。     

生产批量计划问题的RCWW算法验证研究

Wagner-Whitin( WW)算法是经典的、求解生产批量计划((Lot-sizing Planning,LSP)问题的最优启发式算法,对于中小规模问题可以有效求得产品的最优生产量。随机累加WW(Randomized Cumulative WW,RCWW)算法是改进了的WW算法,适用于求解具有一般生产结构的、多层级LSP问题。RCWW算法的求解效果已经得到了验证。根据RCWW算法的求解思想,通过采用C语言进行编码实现算法流程。通过对具有一般生产结构LSP问题的标准算例进行求解,验证了RCWW算法的求解效果,发现了原文献的错误,证明了作者对RCW W算法的正确理解。     

爆炸搜索算法及其收敛性证明

受烟花(炸弹)爆炸的启发,结合经典优化算法提出了一种新的智能优化算法—爆炸搜索算法(Explosion Search Algorithm, ESA) 。ESA引入部域搜索的思想,将智能优化算法与下降搜索算法进行有机结合,使得ESA具有强大的局部搜索能力和全局搜索能力以及好的收敛精度。对算法的收敛性进行了证明,最后通过对benchmark函数集进行仿真并同其他算法进行比较,验证了ESA的高效性。     

基于二进制可辩识矩阵变换的离散化算法

在用粗糙集理论处理决策表进行约简时,要求决策表中的各值用离散值表达,即离散化.求最小数目的断点集是一个NP-hard问题,解决这类问题的一般方法是采用启发式算法求出最优或次优解,给出了离散化中的二进制可辩识矩阵的定义,并提出了基于二进制可辩识矩阵变换的离散化算法,实例证明,该算法是有效的和高效的.     

翻转距离星树问题的计算复杂度和近似算法

讨论基于基因组翻转距离的星型进化树问题的算法和复杂性.首先证明星树问题是NP-难解的,再证明该问题不存在绝对近似求解算法,最后给出一个求解星树问题的常数近似算法,近似性能比为2.     

CAN总线固定优先级调度算法的应用

分析了CAN总线的最差消息传输模型，提出了一种固定优先级调度算法；针对系统控制实时性的要求及特点，对6自由度平台系统的消息进行调度。实际使用证明，该方法改善了6自由度平台的整体控制性能，提高了网络利用率，消息的截止期得到满足。