基于粗糙集和神经网络的供应商决策选择研究

本文提出了一种基于粗集理论与神经网络相结合的供应商优化选择新方法.首先利用粗集理论对供应商原始指标决策表进行一致性属性约简,然后借助神经网络强大的学习能力对决策表进行自学习,完成属性的不一致约简,最后再由粗糙集对其进行值约简,得到最终的供应商优化选择决策规则,并给出了相应的算法.最后通过实例说明该方法的有效可行性.     

一种基于粗集的实例分解归纳学习方法

粗集是知识约简的一种有效工具,但决策表的最小约简已被证明是NP难题.对于复杂的决策表,由于必要的条件属性数目可能较多,直接用粗分析比较困难.为此本文基于粗集理论,给出了一种决策表的分解方法.实例表明决策表的分解可以减少知识约简的难度.这对于大型的决策表,有潜在的应用价值.     

基于粗糙集理论的财务危机预警研究

本文针对财务危机预警中财务比率数量较多时计算量较大的问题,提出了基于粗糙集理论的财务危机预警模型,将财务比率分别作为条件属性,将企业所处的状态作为决策属性,从而构成一个财务预警决策系统.通过对决策表的属性约简和规则约简,得到决策系统的最小决策规则,从而实现财务危机预警.测试结果表明,该方法的预警结果正确、有效.     

基于可辨识矩阵的不完备模糊目标信息系统的属性约简

粗糙集理论是用来解决不确定性的新的数学工具,其中属性的约简是粗糙集理论中一个重要的研究课题.J.W.Guan等提出了信息系统下的矩阵算法.本文则是把这种算法推广到信息不完备并且目标是模糊的领域.通过容差关系的上近似集和下近似集重新设计了算法,最后用实例验证算法了算法的可行性.     

一种基于VPRS的IT项目投标风险要素评价方法

变精度粗糙集模型允许有一定程度的错误分类率存在,利用这种特性可以有效消除投标风险信息系统中的数据噪声,提高风险要素评价的精度.结合层次分析法中判断矩阵方法提出一种基于变精度粗糙集的评价IT项目投标风险要素重要度的算法.首先,由专家对各要素风险程度打分,建立决策表;其次,利用变精度粗糙集属性依赖度求得属性间的相对重要性来构造判断矩阵;最后,确定各要素的综合重要度,并排序.     

风险偏好与属性约简在决策问题中的应用研究

将决策者风险偏好与属性约简算法应用到具有大量属性的决策问题,提出先对决策者分类再进行决策的策略． 根据决策者的风险偏好特征将其分为风险规避型、风险中立型、风险偏好型,针对不同类型的决策者分别采取相应的算法,提取有效属性并利用有效属性进行决策; 针对不同风险偏好的决策者,提出相应的风险偏好预期规则; 提出基于优势关系辨析矩阵的属性赋权算法及基于属性值优势度矩阵的进行信息融合与排序算法; 最后通过属性值为实数与区间数的两个实际案例表明该算法的科学合理性．     

股票遴选与投资业绩——基于属性约简及动态时间规整距离

评价风险资产价值的指标(属性)有很多,以少量指标(属性)从数以千计的风险资产中筛选出有投资价值的资产对投资业绩影响重大。本文以股票市场为例,提出了基于属性约简及动态时间规整距离的股票遴选方法。首先利用基于属性重复度的改进属性约简算法筛选出能区分股票投资价值的约简属性集,之后将单指标动态时间规整算法拓展到多指标,建立股票间基于约简属性集的多维动态时间规整距离集,利用聚类技术对规整距离集进行聚类并通过拆分规整距离对股票进行类别划分,遴选收益-风险特征均较好的类别中的股票构建资产池。数值试验表明:随机模拟权重和均等权重投资组合的累积收益率均高于市场基准,且资产的优化配置进一步改善了投资组合的收益-风险特征。该方法通过属性约简降低了投资者评价股票投资价值的难度,通过多维动态时间规整距离度量了不同股票关于各指标(属性)时间序列变动趋势的相似程度;遴选过程基于历史数据,避免了主观因素的影响,且筛选结果具有稳健性。此外,该方法适合于一般风险资产的遴选,还可以将不同市场不同行业考虑在内,以便更好地实现分散化投资。     

基于粗糙集理论的格序选择方法

在粗糙集理论中,为了识别由偏好属性导致的不相容性,已提出基于优势关系的粗糙集理论,然而这一理论在实际应用中往往导致多个决策规则的出现,如何辨别由偏好多属性决策表中获取的多个决策规则从而选取最优方案,尚未见到有关的研究文献。本文针对这一问题,利用格序理论,给出属性约简的贴近度,比较不同约简所得决策规则贴近于原知识库的程度,从而得到一种选择最优决策方案的方法。     

基于β-δ0粗糙集模型的属性约简算法

本文针对经典粗糙集模型存在的对噪音数据敏感等缺陷,提出了基于隶属度和特征距离的β-δ0拓展模型,该模型不仅能够处理含有噪音的不完全、不精确信息系统,其结果也能反映大量数据所满足的统计规律;针对β-δ0拓展模型,提出了一种基于属性上下文敏感度的启发式属性约简算法.     

基于模糊聚类和粗糙集提取我国经济增长的模糊规则

提出了一种基于模糊软分类和粗糙集理论来提取模糊规则的一种算法.该算法分为3个步骤①通过模糊软分类对样本进行模糊划分,得到隶属度矩阵;②运用粗糙集理论和得到的隶属度矩阵生成初始决策表;③简化决策表,提取规则.最后运用该算法提取我国经济增长的模糊规则.     

Separator-based data reduction for signed graph balancing

Polynomial-time data reduction is a classical approach to hard graph problems. Typically, particular small subgraphs are replaced by smaller gadgets. We generalize this approach to handle any small subgraph that has a small separator connecting it to the rest of the graph. The problem we study is the NP-hard Balanced Subgraph problem, which asks for a 2-coloring of a graph that minimizes the inconsistencies with given edge labels. It has applications in social networks, systems biology, and integrated circuit design. The data reduction scheme unifies and generalizes a number of previously known data reductions, and can be applied to a large number of graph problems where a coloring or a subset of the vertices is sought. To solve the instances that remain after reduction, we use a fixed-parameter algorithm based on iterative compression with a very effective heuristic speedup. Our implementation can solve biological real-world instances exactly for which previously only approximations were known. In addition, we present experimental results for financial networks and random networks.     

A heuristic approximation algorithm of minimum dominating set based on rough set theory

The minimum dominating set of graph has been widely used in many fields, but its solution is NP-hard. The complexity and approximation accuracy of existing algorithms need to be improved. In this paper, we introduce rough set theory to solve the dominating set of undirected graph. First, the adjacency matrix of undirected graph is used to establish an induced decision table, and the minimum dominating set of undirected graph is equivalent to the minimum attribute reduction of its induced decision table. Second, based on rough set theory, the significance of attributes (i.e., vertices) based on the approximate quality is defined in induced decision table, and a heuristic approximation algorithm of minimum dominating set is designed by using the significance of attributes (i.e., vertices) as heuristic information. This algorithm uses forward and backward search mechanism, which not only ensures to find a minimal dominating set, but also improves the approximation accuracy of minimum dominating set. In addition, a cumulative strategy is used to calculate the positive region of induced decision table, which effectively reduces the computational complexity. Finally, the experimental results on public datasets show that our algorithm has obvious advantages in running time and approximation accuracy of the minimum dominating set.

     

The bandpass problem: combinatorial optimization and library of problems

A combinatorial optimization problem, called the Bandpass Problem, is introduced. Given a rectangular matrix A of binary elements {0,1} and a positive integer B called the Bandpass Number, a set of B consecutive non-zero elements in any column is called a Bandpass. No two bandpasses in the same column can have common rows. The Bandpass problem consists of finding an optimal permutation of rows of the matrix, which produces the maximum total number of bandpasses having the same given bandpass number in all columns. This combinatorial problem arises in considering the optimal packing of information flows on different wavelengths into groups to obtain the highest available cost reduction in design and operating the optical communication networks using wavelength division multiplexing technology. Integer programming models of two versions of the bandpass problems are developed. For a matrix A with three or more columns the Bandpass problem is proved to be NP-hard. For matrices with two or one column a polynomial algorithm solving the problem to optimality is presented. For the general case fast performing heuristic polynomial algorithms are presented, which provide near optimal solutions, acceptable for applications. High quality of the generated heuristic solutions has been confirmed in the extensive computational experiments. As an NP-hard combinatorial optimization problem with important applications the Bandpass problem offers a challenge for researchers to develop efficient computational solution methods. To encourage the further research a Library of Bandpass Problems has been developed. The Library is open to public and consists of 90 problems of different sizes (numbers of rows, columns and density of non-zero elements of matrix A and bandpass number B), half of them with known optimal solutions and the second half, without.     

基于案例的启发学习方法及在信息系统分析建模中的应用

基于案例的启发学习方法是对基于案例方法的进一步探索。在方法中考虑以人—机智能相结合解决复杂系统的问题。本文介绍了基于案例启发学习方法的主要思想,并对该方法的概念及特点进行了描述,最后探讨了该方法在信息系统需求分析及建模中的具体应用。     

Energy-oriented bi-objective optimization for the tempered glass scheduling

This paper investigates a real life bi-objective hybrid flow shop scheduling problem in an energy-intensive manufacturing system, in which glass is produced successively in cutting, printing and tempering stages. The problem aims to simultaneously optimize makespan and the total electricity cost under a time-of-use electricity pricing policy. The glass production has to respect the following environments: (i) the cutting and printing operations are processed in parallel machine environments; (ii) the tempering operation is processed on a batch machine; (iii) machine eligibility and setup time have to be considered in the cutting and printing stages; (iv) the whole manufacturing system is under a time-of-use electricity pricing policy. For the problem, an integer programming model is firstly proposed and shown to be strongly NP-hard. Then a model-based heuristic is adopted and a bi-objective differential evolution algorithm (BODE) is devised based on problem features. Computational experiments on randomly generated instances demonstrated that the BODE outperforms the model-based heuristic in terms of computation time and solution quality. Moreover, with mild increase on computation burden, the BODE significantly outperforms the classic NSGA II in terms of solution quality.     

考虑人车混采的道路信息采集的路径规划研究

本文考虑了道路信息外业采集的任务要求，人车混采的采集方式以及路网特性等方面，为道路信息采集人员的路径规划建立了满足人车混采约束的整数规划模型；提出了分阶段的转化算法，将其逐步转化为有限时间容量限制的弧路径问题(TCARP)。TCARP问题是一种NP-hard问题，精确求解算法无法在合理时间内得到问题的最优解，因此本文设计了求解TCARP问题的两种快速启发式算法TPS和TUH及其随机化版本；考虑到实际采集问题的大规模特性，在两种快速启发式算法的基础上构造GRASP-PA寻优算法。最后分别结合不同规模的基准算例和实际采集算例证明了本文所构造的算法的有效性。     

SIRALINA: efficient two-steps heuristic for storage optimisation in single period task scheduling

In this paper, we study the general problem of one-dimensional periodic task scheduling under storage requirement, irrespective of machine constraints. We have already presented in (Touati and Eisenbeis, Parallel Process. Lett. 14(2):287–313, 2004) a theoretical framework that allows an optimal optimisation of periodic storage requirement in a cyclic schedule. Since our optimisation problem is NP-hard (Touati, PhD thesis, 2002), solving an exact integer linear programming formulation is too expensive in practice. In this article, we propose an efficient two-steps heuristic using model’s properties that allows fast computation times while providing highly satisfactory results. This method includes the solution of an integer linear program with a totally unimodular constraints matrix in first step, then the solution of a linear assignment problem. Our heuristic is implemented for an industrial compiler for embedded VLIW processors.     

Heuristic algorithms for the two-machine flowshop with limited machine availability

The paper studies a flowshop scheduling problem where machines are not available in given time intervals. The objective is to minimize the makespan. The problem is known to be NP-hard for two machines. We analyze constructive and local search based heuristic algorithms for the two-machine case. The algorithms are tested on easy and difficult test problems with up to 100 jobs and 10 intervals of non-availability. Computational results show that the algorithms perform well. For many problems an optimum solution is found.     

基于银行授信额度的Max-NPV项目调度问题研究

本文对基于银行授信额度的Max-NPV项目调度问题进行研究.首先界定研究的假设条件并对文中所用到的符号进行定义;随后采用基于事件的研究方法构建了问题的整数规划优化模型;鉴于问题的NP-hard属性,设计了双层模拟退火搜索循环嵌套的启发式求解算法;最后对一个算例进行了求解分析,并讨论了银行授信额度及客户支付比例对项目收益的影响.结果表明:随着银行授信额度的提高,承包商安排项目进度自由度的增加使得其净现值得到改善,在支付比例较低的条件下项目完成时间也随之提前;当客户支付比例提高时,项目净现值单调上升,而项目完成时间呈先提前后延迟的变化趋势.     

A flight scheduling model for Taiwan airlines under market competitions

In this research, we develop a short-term flight scheduling model with variable market shares in order to help a Taiwan airline to solve for better fleet routes and flight schedules in today's competitive markets. The model is formulated as a non-linear mixed integer program, characterized as an NP-hard problem, which is more difficult to solve than the traditional fixed market share flight scheduling problems, often formulated as integer/mixed integer linear programs. We develop a heuristic method to efficiently solve the model. The test results, mainly using the data from a major Taiwan airline's operations, show the good performance of the model and the solution algorithm.