TSP问题启发集的分析及应用

建立了描述TSP问题启发集性质的概率模型,并指出了改进启发集的一般方法.进一步,利用局部最优解交集作为近似骨架,提出了一种动态改进启发集的宏启发算法———自适应可变启发集搜索.并将自适应可变启发集搜索与目前广泛使用的算法ILK、LKH相结合,TSPLIB中典型实例上的实验结果表明,改进后的算法在求解质量上有了较大的改进.

基于集覆盖理论的覆盖信息系统属性约简方法

针对覆盖信息系统属性约简问题,提出基于集覆盖理论的覆盖信息系统属性约简方法。首先,构造覆盖信息系统的相关矩阵,通过相关矩阵诱导出覆盖信息系统的集覆盖模型,并探讨了覆盖信息系统与其诱导的集覆盖模型之间的联系,发现集覆盖模型的一个极小覆盖恰是原覆盖信息系统的一个属性约简集,从而可以将求解覆盖信息系统的属性约简问题转化为求解对应集覆盖模型的极小集覆盖问题。其次,利用集覆盖启发式算法(set covering heuristic algorithm,SCHA)在解决集覆盖问题上具有更高的精度和更好的性能,给出了基于SCHA的覆盖信息系统属性约简的求解步骤及算法。最后,通过实例验证了所提方法的可行性和有效性。

求解TSP问题的并集搜索的新宏启发算法

利用TSP问题解的概率统计模型,分析了TSP问题的局部最优解并集的性质,发现局部最优解的并集规模较小且包含了绝大多数全局最优解的边.利用该性质,将局部最优解并集作为启发集,并调用局部搜索算子在其上求解TSP问题,由此得到一种称为并集搜索的新宏启发算法.利用该算法还改进了目前广泛使用的求解TSP问题的算法ILK、LKH,在TSPLIB中典型实例上的实验结果表明,新算法在解的质量上有了较显著的提高.

某型复杂工程机械变速箱体复合工艺约束机加工线平衡研究

为解决机加工生产线平衡问题所包含的加工任务刀具需求、机床类型需求、加工方位约束、“紧密”型和“或”型约束等复杂条件,建立了机加工生产线平衡数学模型,并采用含多重筛选机制的粒子群算法进行了求解。首先,建立了满足此复杂实际约束条件的机加工生产线平衡问题数学模型;然后,采用粒子的位置坐标作为粒子群搜索的权重信息,进行了加工任务、集中任务的选取,并设计了多重筛选机制构造启发式任务集生成规则;采用此规则对待分配加工任务进行了多重筛选,以得到可供直接分配的加工任务集合,粒子群算法(PSO)从此集合中依次选取了加工任务,构成了完整的解,并形成了具体的任务分配方案;最后,为提高程序的实用性和可视性,设计了加工任务的甘特图生成模块,通过对某复杂工程机械变速箱体零件的实际案例研究,将简化后的任务信息代入算法进行了求解。研究结果表明:该方法实现了多组平衡率高于90%的优化结果,在节拍时间为1120 s时,得到94.66%的较高平衡率,排产方案表格内容与甘特图显示一致;算法推演结果满足设定的多种复合约束条件,通过与人工排产对比说明了该算法的有效性并具有较好的经济性、实用性;对柔性生产案例进行探讨,证明该算法运算结果具备一定的生产柔性。

启发-参与-激励式的《离散数学》教学模式研究与实践

离散数学是研究离散结构及其相互关系的学科,是计算机科学的重要基础.由于离散数学课程的理论性强,学生反映学习过程枯燥乏味、难度大,学生学习的积极性不高,学习效果不佳.本文提出启发-参与-激励式的《离散数学》教学模式,构建课程启发式案例集、学生参与并完成的案例训练,大幅增加课程的过程性评价在课程考核中的比重,激励学生参与课堂教学、主动学习.实践教学表明:该课堂教学模式改变了学生被动听课的习惯,提高了学生课堂以及课后学习的参与性与积极性,学习效果明显提高.

禁忌遗传算法求解最小支配集

如何寻找一个网络图的最小支配集是NP难题。分别设计了逆序启发式算法和禁忌搜索算法,并在此基础上提出了禁忌遗传算法(TSGA)用于求解最小支配集;将禁忌搜索和遗传算法结合起来,弥补了彼此的不足,既有效地避免了算法易陷入局部最优解的缺陷,又加快了算法的收敛速度。经对大量随机网络图的测试和对物流网络选址问题的求解,验证了TSGA算法的优越性。

限定吸引率与容量的停车换乘系统选址研究

为实现驾车者选择换乘公共交通进入城市中心区,采用p-hub方法对所研究的停车换乘(P&R)系统的用户需求进行理论描述。以出行广义费用作为出行模式决策的量化指标,提出竞争模式下出行者选择P&R设施的概率;以P&R系统的用户需求量最大化为目标,满足预先给定的P&R系统吸引率、设施容量两个约束条件建立空间优化选址模型。通过对模型的理论分析,解决了满足P&R系统吸引率、设施容量以及P&R设施数量最少的多目标优化选址问题。采用启发式聚合集理论构造三步式搜索算法求解非线性整数规划模型。数值实验表明该算法可有效处理P&R系统的选址问题。