Parameter Ecology for Feedback Vertex Set

This paper deals with the FEEDBACK VERTEX SET problem on undirected graphs, which asks for the existence of a vertex set of bounded size that intersects all cycles. Due it is theoretical and practical importance,the problem has been the subject of intensive study. Motivated by the parameter ecology program we attempt to classify the parameterized and kernelization complexity of FEEDBACK VERTEX SET for a wide range of parameters.We survey known results and present several new complexity classifications. For example, we prove that FEEDBACK VERTEX SET is fixed-parameter tractable parameterized by the vertex-deletion distance to a chordal graph. We also prove that the problem admits a polynomial kernel when parameterized by the vertex-deletion distance to a pseudo forest, a graph in which every connected component has at most one cycle. In contrast, we prove that a slightly smaller parameterization does not allow for a polynomial kernel unless NP coNP=poly and the polynomial-time hierarchy collapses.     

Parameterized Algorithmics for Computational Social Choice：Nine Research Challenges

Computational Social Choice is an interdisciplinary research area involving Economics, Political Science,and Social Science on the one side, and Mathematics and Computer Science（including Artificial Intelligence and Multiagent Systems） on the other side. Typical computational problems studied in this field include the vulnerability of voting procedures against attacks, or preference aggregation in multi-agent systems. Parameterized Algorithmics is a subfield of Theoretical Computer Science seeking to exploit meaningful problem-specific parameters in order to identify tractable special cases of in general computationally hard problems. In this paper, we propose nine of our favorite research challenges concerning the parameterized complexity of problems appearing in this context. This work is dedicated to Jianer Chen, one of the strongest problem solvers in the history of parameterized algorithmics,on the occasion of his 60 th birthday.     

图的正面影响控制集中贪婪算法的设计与分析

对于没有固定基础设施的无线传感器网络,设计一个优良合理的拓扑控制协议是关键.根据图的控制集在无线传感器网络组建虚拟骨干网的应用,研究了图上控制集问题的一个变形—正面影响控制集问题.针对图中是否存在孤立顶点,分两种情形讨论,设计了相应的贪婪算法,并分析了算法的性能比.     

平面图选择控制集问题的复杂性分析及算法设计

研究平面图的选择控制集问题．通过PX3C(planar exact cover by 3-sets)到平面图控制集的变换，证明了平面图的控制集问题是NP完全的，从而得到平面图的选择控制集问题的NP完全性．同时提出了一个基于遗传算法的求平面赋权图的选择控制集的近似算法．     

循环图及单圈图的有效控制集与完美控制集

图的完美控制集和有效控制集是两类特殊的控制集．通常要判断一个图是否存在有效控制集是困难的．该文证明了无向循环图一定存在有效控制集．此外，给出了单圈图的完美控制数与其阶数的关系．     

配送问题的数学模型与两阶段启发式算法研究

在一些模型假设的基础上，构造了客户订单合成配送问题的数学模型，提出了解决该问题的两阶段启发式算法．实验表明，此算法可以有效求得客户订单合成配送问题的近优解，为实现客户订单的优化合成配送提供了一个基本方法．     

直线簇上区间图的最小全控制集和最小配对控制集

研究了广义区间图的最小全控制集和最小配对控制集的计算问题.对有一个公共交点的直线簇上的区间图,给出了计算其最小全控制集的O(n)时间算法和其最小配对控制集的O(n+m)时间算法.     

基于动态贪婪算法的不可靠测试点选择

针对测试不可靠条件下的测点选择问题,根据故障-测试关联矩阵以及考虑故障检测率、故障隔离率和误诊率,建立了通用的数学模型.依据测试点对故障检测率和故障隔离率的贡献定义故障检测隔离费用,并以此为贪婪准则,提出一种动态贪婪算法来解决测试不可靠条件下测点选择问题.应用案例验证该算法能快速准确找出最优或近似最优测试集,适合大型复杂系统的测试性分析与验证.     

极端性转移、启发式、社会称许性对职务信息完整性的影响

研究通过2×3×2组间实验设计,探讨极端性转移、启发式和社会称许性对职务信息完整性的影响。多因素方差分析结果表明：a) 极端性转移对职务信息完整性的影响取决于极端性转移程度,高社会称许性条件下极端性转移导致职务信息不完整;b) 启发式策略导致不完整的职务信息,激发内部动机的同时提供典型职务信息,可促使被试进行系统化加工;c) 社会称许性是极端性转移和启发式与职务信息完整性关系的调节变量。     

基于遗传和启发式算法的混合顶点着色算法

图的着色问题是一种典型的NP-完全问题.提出了基于遗传算法和启发式算法的新型混合顶点着色算法,该算法在实现过程中涉及到染色体的编码方法、适应度函数的设计以及遗传算子的选择等.实验仿真结果表明此算法改善了求解的时间复杂度,可以获得问题高质量的解.     

基于时间满意的集覆盖问题及若干贪婪算法应用研究

传统的选址问题过于简单地考量时间这一对企业竞争力影响重大的因素。针对这一特点，对时间满意度函数进行了定义，从顾客角度考虑覆盖半径，从企业角度考虑覆盖比例，提出比传统集覆盖问题更一般的基于时间满意的覆盖选址问题。在给定的网络G（V，A）中，以最小化总的建站成本为目标建立这一问题的整数规划模型，并应用3种被证明为在覆盖选址问题中计算效果很好的贪婪算法对不同规模的问题进行求解计算。     

粗糙集的动态粒度及应用

经典粗糙集理论把元素与分类的关联看成不变的,不便于论域上动态数据的研究,而动态粒度可以从不同角度或层次来分析数据,从而弥补经典粗糙集过于简一的计算机制.在经典粗糙集的基础上结合动态粒度的特点,给出了粗糙集、粒计算、动态粒度和影响度的概念,提出了一种粗糙集的动态粒度算法,并给出其应用.     

粗集理论及其在智能控制中的应用综述

对粗糙集理论的应用发展及其基本概念做了详细的描述,介绍了粗糙集理论在智能控制中的应用及发展趋势.重点阐述了它与模糊集、神经网络、遗传算法等软计算方法的融合,指出这些融合将为解决智能控制中的难题提供新的思路和方法.     

紫外光谱与遗传算法用于多组分氨基酸同时测定

将遗传算法用于紫外光谱数据处理,实现了多元分辨与校正,并对多组分分析体系进行同时定量测量。     

近似集动态更新方法的性能评测与规则获取

对属性集变化时特性关系下粗糙集扩展模型中近似集动态更新的方法进行性能测试,验证了该方法的有效性和适用性;并依此方法设计了一个伪增量规则提取的系统,可以直接用来为决策服务.     

一种混合GA、SA和启发式规则的FMS调度方法

描述了一种综合ＧＡ、ＳＡ 与启发式规则优点的方法,及其在ＦＭＳ调度问题中的解决方案和ＦＭＳ调度的特点,建立了可变工艺路径的ＦＭＳ调度问题的模型．对ＧＡ、ＳＡ 操作中各步骤及其相应于ＦＭＳ调度的特殊性作了说明,提出了基于启发式规则库的ＳＡ 算法,阐述了柔性调度的基本框架,并对一个３３ 机器、１２７ 工件的实例进行了计算     

汽车导航系统的动态路径规划优化模型与算法研究

汽车的普及化增加了城市交通的内在压力,对汽车导航系统的动态路径规划优化可以给驾车人在有限的城市道路中找出一条最佳行车路径.本文介绍了一种实用的动态路径规划方法.采用一个实时的路线地图,地图包括交通信号,道路类别和行车道的数目.建议的解决方案是使用病毒感染的遗传算法.该方法是将公路干线的一部份视为病毒.通过交叉和感染确定近期病毒的最佳组合.在驾车的过程中,当交通挤塞经常变化时,使用病毒感染实时路线,将产生一个可供选择的行车路线.最后给出病毒遗传算法的试验仿真结果.     

列车耐碰撞系统有限元和多体动力学联合仿真

研究基于有限元和多体动力学技术进行列车耐碰撞系统设计的联合仿真策略.通过非线性有限元分析获得车辆吸能部件在碰撞时的力—位移关系曲线,以该曲线模拟车辆连挂之间的非线性弹簧特性,运用多体动力学技术进行了两列车的碰撞动力学仿真.通过仿真分析碰撞中列车各车辆间的作用力、变形、速度、加速度以及各个吸能部件的能量吸收等数值,实现了对新设计列车碰撞被动安全系统总体性能的评估.与高速碰撞相比,在中低速碰撞工况下,头车与第2节车体端部连接处吸收的动能占总动能的比例更高.联合仿真能较真实地模拟列车碰撞的全过程,验证了联合仿真策略的可行性.     

动态火焰图像分割及在电熔镁炉视频监控中的应用

火焰的颜色、亮度分布、形态变化规律在不同工况下均不相同,表现出多模态的特点;此外,背景环境的反光、气雾、粉尘等干扰使得目标区域和背景高度耦合,因此传统分割算法不能确保在多种工况下的准确性.本文提出将多元图像分析和人工经验相结合的火焰图像分割方法,通过主成分分析方法对图像降维、构造得分柱状图,进而分割出炉口火焰区域.将本文方法应用于电熔镁炉生产的视频监控中,结果验证了该方法的性能.     

一种新的人才培养模式——“动态能力集”工学结合人才培养模式研究

“动态能力集”工学结合人才培养模式强调能力是动态的、是一种集合。核心思想是依据行业需求，以就业为导向，以能力为中心，将实际工作岗位所需求的各种能力任务化、项目化，构建人才培养动态能力集。根据任务化了的动态能力集再确定相应的课程体系、动态的能力模块、动态的能力点，并采用工学交替、任务驱动的教学模式，做到真正的知行合一。