基于半定规划的多约束图划分问题

提出一种递归的二分算法,用于求解带顶点权重约束的图划分问题.首先利用内点法求解不加顶点权重约束的半定规划松弛模型,然后利用超平面舍入算法得到满足顶点权重约束的初始可行解,再进一步设计启发式算法对初始可行划分进行局部改进,以得到更优的划分结果.实验结果表明,所设计的算法可在较短时间内得到多约束图划分问题的高质量解.     

关于问题1|chains,B|Cmax的多项式算法

对带有"扩充链"优先约束的分批排序问题进行了研究,其目标函数为最大完工时间.优先约束为:在一个"扩充链"上包含有n个工件,另外有m个孤立点工件(即工件之间无任何优先约束).讨论了B=2时问题的最优算法,把这一问题多项式转化成了组合最优化中求解非二部图赋权匹配问题,并相应地给出了一个运算次数为O(n4)的多项式算法.     

一种改进的分布约束优化算法MULBS+

完备算法虽然能够求得分布式约束优化问题最优解,但要消耗大量资源及时间,相反,非完备算法通过求得次优解来提高效率.MULBS作为一个有效的非完备算法,虽然在求解质量和时间上有所提高,但在解决赋值冲突时采用的回溯策略及并行搜索方面存在不足.通过对该算法的深入分析,本文针对上述问题进行了改进,提出其改进算法MULBS+.通过在回溯策略中引入最小冲突选择机制,以及在约束图密度较大时采用基于动态子图划分的并行搜索策略,进一步提高了算法的性能.实验表明,该算法除增加一定的通信信息外,其执行时间及求解质量均优于原算法.     

基于分组光纤被动星型网的FFT算法及其选路

通过分析两类特殊置换———组内置换和组置换的特征 ,利用这两种置换存在无冲突路由算法的特性给出了FFT运算在分组光纤被动星型网上的实现及其路由算法 .在适当分组的情况下 ,本算法在n个处理器的分组被动星型网上计算n点FFT的总通信开销为T =2logn 1个时间片 ,此时硬件上需要n个连接器和 2n n个发送器和接收器 ,算法的时间代价和硬件代价平衡 ,算法性能达到最优 .     

一类排序问题的最优解

文章讨论了受时间约束的n个元素排序问题,并证明了最优排列的存在性,同时给出了寻求最优排列的方法.     

带有优先约束的分批排序问题

对工件带有优先约束的分批排序问题进行了研究,其目标函数为最大完工时间．优先约束为：有一个树上包含有n个工件,其余的m-1条链上的工件数总和为常数,且工件的加工时间不限制．对于此种情况,给出了一个多项式时间算法．     

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

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

一种基于HMM的WSN先验事件分析模型

为了充分利用仿真过程中产生的有用数据,研究了利用隐马尔可夫模型对节点状态的识别方法.针对无线传感网络的特点,通过对Baum-Welch算法进行扩展,设计了一种节点事件识别算法.详细论述了该算法中状态约束、观察窗口的处理方法.深入分析了事件识别算法中节点数据获取、状态建模、隐状态推导等关键问题,并对该算法的时间、空间复杂度进行了解释.设计实现了一种无线传感网络仿真平台,验证了算法的有效性和实用性.     

三台平行机上四个约束链的排序问题

考虑四条优先约束链的n个工件在三台平行机上的排序问题,目标是极小化最大机器完工时间.文中说明此问题至少为NP-hard的,并通过一个伪多项式时间算法和一个完全多项式时间近似规划来描述此问题的复杂性.     

时态数据库中非数值型属性周期规律的研究

时间是数据本身固有的属性,将时间约束加在关联规则中能更好地说明事实.本文介绍的方法能够提取时态数据库中带时态信息的关联规则,而且能够计算时态数据库中某个非数值型属性(项)的周期,并通过执行改造了的Apriori算法提取该属性的周期规律.本文通过选取两个时间粒度,对时态数据库中的时间区间进行了两次划分和标记.第一次划分和标记的目的是计算选择出的某非数值型属性的周期;第二次划分和标记的目的是离散化时间区间,用标记集合代表原时间区间,进而根据标记集合求交的结果得到带时态信息的频繁项集.采用标记集合求交的方法能够使得Apriori算法的迭代迅速收敛,提高算法执行效率.     

基于遗传算法的高校排课数学模型

排课问题是一个有约束、多目标的组合优化问题,并且已经被证明是一个NP完全问题。针对高校排课过程中存在诸多约束因素的问题,提出将遗传算法与约束条件算法相结合的排课算法,由约束条件算法确定排课任务的优先次序,遗传算法解决单个排课任务时间片分配的优化问题。实验结果表明,该算法能够改进算法性能,提高排课效率。     

考虑延误与班期限制的多商品流多式联运方案优化

针对不确定时间影响的多商品流多式联运方案优化问题,以空铁联运为主,将运输时间转化为确定运输时间和不确定延误时间,同时考虑班期限制影响,以收货时间窗限制、准时率、运力等为约束条件,以所有订单总运输成本、运输时间和碳排放最小为目标,构建多商品流多式联运方案优化模型,并基于改进的非支配排序遗传算法Ⅱ(non-dominated sorting genetic algorithmⅡ,NSGA-Ⅱ)进行模型求解。实证分析表明：相对于无延误和班期限制,延误和班期限制均导致各目标值呈现不同程度增加;随着延误程度增加,总运输时间逐渐增加,而总运输成本还受到班期限制的耦合影响,呈现先减小后增加的周期性变化;碳排放量与运输成本呈现一致变化趋势;最后采用多属性决策方法获得考虑综合满意度的最优运输方案。研究结果可为实际中多式联运方案设计与优化提供参考。     

基于D-tree分解的欠约束与完备约束的几何约束求解

提出了解决欠约束、完备约束的几何约束问题的D-tree分解算法.首先,提出了一种适用范围更广的处理特殊约束策略,可以将这种特殊约束与普通约束统一化,采用转化策略将欠约束的几何约束问题转化为完备约束的几何约束问题.然后,根据几何约束图中结点的度的性质给出了D-tree分解算法,相比经典算法,D-tree分解算法拥有更低算法复杂度和相同的求解域.最后,根据D-tree分解算法结果的规律性,给出了一个为基于数值的求解方法导出求解序列的策略.D-tree分解算法通过导出的求解序列将提高几何约束求解中基于数值的求解方法的求解效率.     

基于人工智能原理的大学课表编排模型

针对涉及因素多、结构复杂的大学课表编排问题,文章采用人工智能及专家系统的知识,成功地构造出大学课表编排的数学模型及有关编排算法。对排课的死锁问题进行了有效的处理,并用Ｆｏｘｐｒｏ实现了课表的自动编排,运行效果良好。     

一种求解TTP问题的SAGA算法

分析了高校课程表编排中涉及的各种约束条件和特殊要求,给出了一种求解TTP问题的模拟退火遗传算法(SAGA),并且对遗传算法中的交叉、变异操作采用自适应方式进行了改进,提高了算法在解空间中的探索能力和效率.数值实验证明了该方法的有效性和可行性.     

案例注入式遗传算法在大学课程表问题中的应用

遗传算法在解决大学课程表问题过程中往往采用随机方式来初始化种群,这就造成了运算量变大和复杂度增加等情况,从而影响了算法的性能.提出了一种改进的遗传算法——案例注入式遗传算法,该算法利用基于案例的推理对遗传算法进行初始化,以此加快算法的收敛速度.     

模拟进程调度的时间表求解算法

从分析进程调度与时间表问题的共性、探索时间表求解的数学模型出发,介绍了一种时间表问题求解的算法,并分析算法复杂度．该算法适用于时间表在现实环境中的各种应用．     

基于干扰对齐的设备到设备功率控制算法

为了使蜂窝网络系统中设备到设备(D2D)用户的速率总和最大,提出了一种基于干扰对齐(IA)的功率控制算法.该算法通过IA技术使得所有的D2D用户能够同时占用可使用的子载波;同时,控制每一个D2D用户在子载波上的功率,使所有D2D用户在对蜂窝用户(CU)产生的干扰小于干扰阈值的前提下,其速率和达到最大.仿真结果表明:与传统的基于频分多址(FDMA)的功率控制算法相比,本算法在干扰阈值为10 d Bm时,所得到的D2D用户的总速率和可提升约6 bit·S-1·Hz-1.     

有序化对(Fe,Ni)3V合金环境氢脆的影响

研究了室温下不同有序度的(Fe,Ni)3V在真空、空气和氢气中的力学性能.结果表明不同有序度的(Fe,Ni)3V均不存在空气中水气诱发的环境氢脆;无序态(Fe,Ni)3V在氢气环境下存在轻微的脆性;而有序态在氢气中有强烈的脆化作用,其脆性随有序化程度提高而增加.扫描电镜观察表明无序态合金在不同气氛中断裂时全部为韧性断口;有序态合金在空气和真空中基本上也为穿晶韧性断口,但在氢气中的断口形貌大部分为脆性断口.     

基于关联度分析的协调控制子区划分方法研究

利用交叉口关联度量化分析方法,给出了相邻交叉口关联度与多交叉口组合关联度的计算公式.通过定义控制子区划分方案的解集空间、约束条件与评价准则,建立了协调控制子区划分模型;采用子区划分层扩散算法实现对控制子区划分方案的分析评价,给出了一套完备的控制子区划分流程.通过算例分析,对基于关联度分析的协调控制子区划分方法进行了细致阐述.