粗等价类双边递减下多次Hash的渐增式求核与约简算法

为设计高效约简算法,首先以全局等价类为最小计算单位提出粗等价类概念,证明粗等价类下约简与原信息系统等价;然后深入剖析1,0,-1三类粗等价类的性质,把求正区域等价转化为0-粗等价类双边递减下的渐增式计算,结合1和-1-粗等价类的传递性,设计双边横向删减实体和纵向删减属性的优化规则,可在每一轮增量计算中缩减计算域,基于此设计多次Hash的属性增量划分方法;最后给出新的渐增式快速求核与约简算法,其中求核基于纵向优化规则,可在一次计算中求得多个非核属性,无需遍历全部属性.基于UCI、海量和超高维3类数据集进行多个实验,实验结果证明本文求核与约简算法是高效完备的,在海量数据与超高维数据集下有较大优势.     

基于偶图匹配和禁忌搜索的排课新算法

针对目前高校的特点,提出一种偶图匹配和禁忌搜索相结合的排课新算法.将排课五要素恰当地绑定封装成课元和课栈两个向量,并以二维权值矩阵描述课元和课栈之间的关联权重,按照重权优先的原则并根据正确性原则进行约简,获得课元和课栈之间的匹配偶图.在此基础上,引入禁忌搜索算法,以排课的完备性原则、合理性原则和人性化原则的加权和为目标函数,以随机二维权值矩阵生成的匹配偶图为初始解,对二维权值矩阵进行扰动构成搜索邻域,以生成的匹配偶图为禁忌对象,采用全局藐视准则,获得最优的排课方案.给出典型算例验证提出的方法,结果表明了其可行性,并且具有考虑因素多和计算效率高的特点.     

有约束指导的粗集决策表属性约简算法

粗集理论通过对原始决策表的约简获取规则知识,其核心部分是属性约简.本文在结合两种基本属性约简算法优点的基础上提出了有约束指导的属性约简算法,并给出了算法的详细步骤.该算法通过专家经验的约束指导避免了对属性之间随机组合情况的搜索,可以提高求解速度.仿真试验验证了该方法的有效性和优越性.应用该算法处理一组生产调度数据以获取调度规则,结果显示能较好的与生产实际相吻合,这进一步验证了算法的实用性.     

基于摄动的模糊聚类算法最优模糊等价矩阵相关性质分析

对基于摄动的模糊聚类算法进行深入研究.给出一个模糊相似矩阵的实例,存在与该矩阵距离相同且都是最小的两个不相等的模糊等价矩阵,从而证明了全局最优模糊等价矩阵不具有唯一性.对基于摄动的模糊聚类算法求出的可行解的不同情况进行分析,给出了每种情况下可行解个数的计算表达式.完善了基于摄动的模糊聚类算法的相关理论.     

基于区分矩阵与强等价集的启发式知识约简法

提出了基于区分矩阵与强等价集的启发式知识约简方法。在决策表的相对约简过程中采用区分矩阵来表达知识,并利用区分矩阵中项的长度和每个属性的频率作为启发信息进行属性的选择。同时利用属性加权频率和强等价集概念化简区分矩阵,既减小了计算复杂度又提高了约简效率。现已证明,寻找决策表中最小相对约简问题是典型的问题,采用该算法在大多数情况下能够找到最小约简,即使在未找到最小约简的情况下,也能找到次优解。通过实例分析,证明该算法是求解属性相对约简的快速、有效的方法.     

具有时间窗口约束的并行机床调度问题研究

具有时间窗口约束的并行机床调度问题可以被描述为在M台互不相同机器上安排加工N个工件。每个工件只能在一个给定机器子集中的一台机器上加工，且加工过程只能在给定的离散时间窗口内进行，并且工件的加工时间长度和时间窗口约束与加工机器有关。为了解决该问题，本文给出一种集成约束规划与禁忌搜索的搜索算法，其中约束规划系统被作为验证解的可行性和确定变量的值，而禁忌搜索过程被用来对解空间进行搜索。讨论禁忌搜索过程中的初始解产生、邻域结构、禁忌列表、解空间搜索等算法设计问题。最后给出算法在不同问题实例上的算法效率比较及分析。     

结合粗集理论的动态属性约简研究

针对动态建立数据库的需要和粗集约简存在的问题 ,在粗集理论的基础上提出了一种动态约简算法 .在数据库变化时 ,该算法不象静态粗集约简方法需重新寻找属性约简 ,而是利用新增的对象对原有的约简关系进行修正 ,大大节省了计算量 ,提高了搜索效率 ;同时在算法中还引入了信息熵准则以克服粗集约简准则对数据噪声的敏感性和不能表达属性间概率因果关系的缺点 .通过一个病因诊断问题的实例表明 ,该算法利用较小的信息表就找到了与静态粗集约简一致的属性约简集 ,并按照因果关系的大小 (不确定性大小 )对结果集合作了排序 ,同时计算量分析表明该算法比静态粗集约简极大地节省了计算量 ,提高了搜索效率 .     

基于相对分辨能力的属性约简算法

在粗糙集理论中,分辨能力反映拥有知识的多少;为此,给出分辨能力相关概念、性质和计算方法,并提出基于相对分辨能力的约简定义,同时研究该约简定义与Hu差别矩阵约简之间的等价性,指出Hu差别矩阵约简可由相对分辨能力约简获得.为了进一步提高求解效率,通过减少约简过程中基数排序次数来提升效率,设计了相对分辨能力的约简算法,其时间复杂度为O(|C|~2|U|).实例分析和UcI中数据集的实验比较表明所提出的约简算法是有效的、可行的.     

组合投资双目标概率准则模型及TSⅡ算法求解

考虑到我国证券交易过程中许多限制性的规定及现实投资者并非完全理性的决策行为,给出了概率准则组合投资的收益-损失风险双目标整数规划模型.通过证券收益经验分布,应用分层抽样的随机模拟,结合禁忌算法,设计禁忌模拟混合智能优化算法TSⅡ,进行概率准则模型求解.分层抽样保证抽样遍布搜索空间,有效刻画收益分布的"高峰厚尾",避免禁忌搜索路径往返重复,克服禁忌搜索对初始解的较强依赖性.算法同时使用禁忌表与希望表,将分散搜索与集中搜索相结合,增强禁忌算法的并行处理能力,提高了寻优效率与精度.最后,给出一个投资组合实证分析算例的收益-损失风险有效前沿.     

属性约简的两阶段遗传算法

属性约简是数据挖掘的一个重要研究内容. 为了解决具有多种属性类型的决策表约简问题,在粗集和二元关系聚合理论的基础上,利用属性重要性作为评价标准,提出了一种两阶段遗传约简算法. 算法的第一阶段是为了找出尽可能多的约简,第二阶段力求寻找最小约简. 根据算法每个阶段的目标设计了编码方案、种群规模、适应度函数、终止条件、选择、变异和修正操作. 实验表明,与标准遗传算法相比,两阶段算法在计算最小约简时更为准确和稳定.     

基于(α, τ)限制相似关系的变精度粗糙集模型

针对经典粗糙集模型只能处理完备信息系统,将变精度粗糙集模型引入到不完备信息系统中。给出了(α,τ)限制相似关系的定义及其相关性质,并提出了基于(α,τ)限制相似关系的变精度粗糙集模型,提出了基于属性重要度和近似分类质量的知识约简算法。通过算例分析验证了该模型知识约简算法的有效性。     

S-粗集与它的分解-还原

利用S-粗集(singular     

A rough set approach to feature selection based on scatter search metaheuristic

Rough set theory is an effective method to feature selection, which has recently fascinated many researchers. The essence of rough set approach to feature selection is to find a subset of the original features. It is, however, an NP-hard problem finding a minimal subset of the features, and it is necessary to investigate effective and efficient heuristic algorithms. This paper presents a novel rough set approach to feature selection based on scatter search metaheuristic. The proposed method, called scatter search rough set attribute reduction （SSAR）, is illustrated by 13 well known datasets from UCI machine learning repository. The proposed heuristic strategy is compared with typical attribute reduction methods including genetic algorithm, ant colony, simulated annealing, and Tabu search. Computational results demonstrate that our algorithm can provide efficient solution to find a minimal subset of the features and show promising and competitive performance on the considered datasets.     

变精度粗糙集属性约简的算法

针对变精度粗糙集属性约简问题,在分析变精度粗糙集理论的基础上,分别从属性依赖度增量、互信息的增量、基于覆盖度与准确度相结合的度量以及属性的不确定性量度等角度,对属性重要度进行分析。并分别以这四个属性重要度作为启发式信息,提出变精度粗糙集属性约简的启发式算法,进而得到信息系统的最小约简,并将所给的算法应用MATLAB程序进行实现。最后,通过具体算例说明所给算法的有效性和实用性。     

求解JLSP问题的遗传禁忌混合优化算法

针对批量与排序的集成问题设计一种遗传算法和禁忌搜索相结合的混合算法,用遗传算法作为主框架优化批量,排序部分由禁忌搜索单独优化,并将排序最优解反馈到遗传算法的主框架中生成集成计划继续寻优。遗传算法的选择算子和变异算子分别采用不同的自适应机制,以提高算法的搜索能力和收敛速度。对3种不同规模算例进行测试,其结果与其他算法比较,验证了所提算法的有效性。     

Joint Decision Matrix Computation for Rules Extraction in Two-Classes Decision Information System

Matrix computation for rules extraction of rough set algorithm's inefficiency restricts the application of rough set theory, so the search for efficient algorithms is of great practical significance. Therefore, the joint decision matrix is defined and a new algorithm JDMCRE for rule extraction is presented on the basis of joint decision matrix for two-classes decision information system. By combining both the conditional attribute equivalent matrix and the decisional attribute ones into one matrix, it can considerably reduce the number of comparison in the process of matrix forming, which can effectively increase the efficiency of algorithm. The complexity analysis and experiment results show that the algorithm is much better than existing matrix algorithms.     

Cooperative extended rough attribute reduction algorithm based on improved PSO

Particle swarm optimization (PSO) is a new heuristic algorithm which has been applied to many optimization problems successfully. Attribute reduction is a key studying point of the rough set theory, and it has been proven that computing minimal reduction of decision tables is a non-derterministic polynomial (NP)-hard problem. A new cooperative extended attribute reduction algorithm named Co-PSAR based on improved PSO is proposed, in which the cooperative evolutionary strategy with suitable fitness functions is involved to learn a good hypothesis for accelerating the optimization of searching minimal attribute reduction. Experiments on Benchmark functions and University of California, Irvine (UCI) data sets, compared with other algorithms, verify the superiority of the Co-PSAR algorithm in terms of the convergence speed, efficiency and accuracy for the attribute reduction.     

一种求解旅行商问题的交叉禁忌搜索

提出一种改进的禁忌搜索（TS）一交又禁忌搜索（CTS），并用于混合优化问题旅行商问题（TSP）的求解。CTS主要包括集中策略和分散策略，采用选择规律的改变促进移动的混合，集中策略增强了算法的局部搜索能力；分散策略是用于开辟新的搜索空间，在CTS中，采用遗传算法中的交叉算子作为分散策略，优解选择法作为集中策略。CTS、标准TS、带集中裳略的TS和蚁群算法用于求解相同的TSP例子，所用例子都是来自TSPLIB例子库和Fogel路径。求解结果显示了CTS的性能优于其它算法。