基于蚁群算法的集合覆盖问题

蚁群算法是一种基于群体智能原理的优化模型,用于解决组合优化问题。集合覆盖问题是NP完全问题中应用面最广的问题之一,它在模式识别、机器学习等领域中具有重要的应用。以SCHF[1]启发函数作为启发信息,用蚁群算法求得集合覆盖问题的优化解。通过几种算法的仿真结果对照表明,用蚁群算法求解集合覆盖问题是有效的,蚁群算法得到的解是比较理想的。     

一种基于扩张矩阵理论的规则学习算法

本文给出的扩张矩阵合并问题是ＮＰ困难问题的一种新的证明。由此得到了析取式最小问题是ＮＰ困难问题的新的证明。之后给出了两个扩张矩阵合并的完备策略，在此基础上给出了扩张矩阵合并的启发函数策略，最后提出了一种新的示例学习算法－－基于扩张矩阵的启发函数学习算法。     

扩张矩阵的启发式学习算法的研究

本文给出了析取式最小问题是ＮＰ困难问题的新的证明，之后给出了两个扩张矩阵合并的完备策略，在此基础上给出了扩张矩阵合并的启发函数策略，最后提出了一种新的示便学习算法－－扩张矩阵的启发式学习算法。     

基于择优协作策略的PES算法在整数规划问题上的应用

整数规划是在科学领域和应用研究中广泛使用的一类数学模型.由于它是NP困难问题,因而求解困难.目前的求解方法是以群智能算法为主体,但这类方法一直未能很好地解决种群内部个体或者种群之间的探索与开采、竞争与协作的矛盾.基于金字塔结构的群智能演化策略（swarm intelligence evolution strategy based on pyramid structure,简称PES）是一种新型算法.该算法能够有效地解决上述两大矛盾.深入地分析了PES算法的机理,构造了一种择优协作策略的模型,并将改造后的PES算法由优化函数扩展到求解整数规划问题上.最后,通过探索实验以及对比实验探究了算法的收敛性、稳定性以及探寻全局最优点的性能.实验结果表明,基于择优协作策略的PES算法能够很好地求解整数规划问题.     

优化初始边集提高分支裁剪法求解TSP效率

概要地叙述了NP完全问题的复杂性,并简述了分支裁剪法求解NP问题最优解的策略.以求解欧氏空间的TSP问题为例,分析了利用分支裁剪法求解问题中主要影响算法求解效率的原因在于初始边集中存在大量无用信息,针对该类问题,提出了通过化简初始边集提高算法求解效率的策略,实验验证了这种方法的有效性.     

犹豫模糊数据对象集的谱聚类算法

目前适用于犹豫模糊数据对象集的聚类算法研究仍然非常有限,现有的犹豫模糊数据对象集层次聚类算法受异常点影响较大且容易聚成链状.针对上述问题,本文首先提出了一种可扩展的犹豫模糊集的加权相似度计算方法,该方法不仅可以利用不同的函数计算相似度,而且可以根据实际问题构造最优的相似度函数.基于该加权相似度计算方法,结合经典的谱聚类算法提出了犹豫模糊数据对象集的谱聚类算法(SCHF).针对目前国内外还没有可用于犹豫模糊数据对象集聚类的标准数据集的现实情况,本文提出了一种确定性数据的犹豫模糊方法并在仿真实验中应用.仿真实验不仅验证了SCHF算法的有效性,而且表明SCHF算法比两种已知算法有更好的聚类效果.     

获胜者确定问题的启发规则与改进蚁群算法

组合拍卖竞胜标的确定问题是一个NP完全问题.本文提出基于启发规则的改进蚁群算法BRIAA(Improved ACO Algorithm based heuristic rule)对问题进行求解,其基本思想是首先提出了可行性竞标启发规则,采用启发规则淘汰不可能入选最优解的竞标,缩减竞标规模;然后采用禁忌表和可行性竞标启岌规则相结合的改进蚁群算法,减小蚂蚁搜索过程中选择可行性竞标的范围,提高可行性解的质量.仿真结果表明,与同类的近似求解算法相比,本算法在求解规模和求解效率上都能够获得更好的效果.     

一阶反合一研究

文章讨论一阶反合一问题以及求反合一子完备集的算法.在合一问题中,有多种求解合一问题的方法,其中研究得较为彻底的是用转换规则进行求解的方法.在研究反合一问题的过程中,人们也陆续提出了许多转换规则,这样做的结果是最终给出的是已解出形.该文在已解出形的基础上讨论一种方法,以给出具体解的完备集（反合一子完备集）.通过引入G_θ和Z函数,使求解更为方便、直观.     

图的最大二等分问题的一种离散填充函数算法

图的最大二等分问题是一个经典的NP困难问题,有着广泛的应用背景。提出了一类求解最大二等分问题的离散填充函数算法。该算法采用快速的、基于迭代改进的算法作为局部搜索算法。构造了最大二等分问题的填充函数和辅助问题,并研究了该辅助问题的相关性质。利用局部搜索算法极大化辅助问题来寻找更好的解。用顶点数为800到10 000的大规模标准测试例子测试提出的算法。实验结果表明,该算法是有效的。     

社交网络中正影响支配集问题的轮转贪心算法

社交网络中最小正影响支配集问题是一个NP难度的组合优化问题,针对该问题,目前有2种典型的贪心求解算法求解速度较快,但贪心解的质量却有待提高。轮转贪心策略是在不增加贪心算法时间复杂度的前提下提升贪心解的质量,且通过实验研究表明能有效增强一些NP难度问题效果的贪心算法。本文将轮转贪心策略求解正影响支配集的2个贪心算法进行融合来提升贪心算法解的质量,提出相应的轮转贪心算法。实验表明,在典型的真实社交网络实例上,与原有贪心算法相比,本文的轮转贪心算法所获解的质量有一定的提高。     

基于地理信息系统的最短路径搜索算法

最短路径问题（ＳＰ）是人工智能的一个活跃研究方向，也是交通网络分析系统的一个最基本问题，在理论和应用上有着广泛而深入的研究。本文从应用的角度，结合地理信息系统（ＧＩＳ）的特点，设计了一种新的数据存储结构，改进节点搜索方法，并建立一种简捷的估价函数，为进一步解决交通网络的综合分析打下了基础。     

一种基于软件定义网络的服务功能链优化部署机制

针对软件定义网络环境下现有服务链部署方法未能充分考虑全网资源利用率的问题,提出了一种基于高效启发式算法的服务链优化部署机制。首先,给出了服务链部署的总体结构,并引入了整数线性规划模型对其进行数学建模;其次,提出了一种高效启发式的模型求解算法,该算法以先排序后贪心的方式,能够在满足资源和时延约束下有效利用网络资源和均衡负载。仿真结果表明,与其他部署算法相比,该算法在降低负载均衡度和时间复杂度的同时提高了请求接受率。     

基于知识的模型自动选择策略

模型自动选择是决策支持系统智能化发展的必然要求。针对目前实用算法较少的现状,提出一种模型自动选择策略。基于知识框架描述模型,根据事实库和知识库提取相应规则生成推理树,结合经验和专业知识实现模型自动选择。实验结果表明,该策略具有较高的命中率。     

基于粗糙集的决策树构造算法

针对ID3算法构造决策树复杂、分类效率不高问题,基于粗糙集理论提出一种决策树构造算法。该算法采用加权分类粗糙度作为节点选择属性的启发函数,与信息增益相比,能全面地刻画属性分类的综合贡献能力,并且计算简单。为消除噪声对选择属性和生成叶节点的影响,利用变精度粗糙集模型对该算法进行优化。实验结果表明,该算法构造的决策树在规模与分类效率上均优于ID3算法。     

Deadlock-free scheduling for flexible manufacturing systems using Petri nets and heuristic search

Deadlock-free control and scheduling are two different problems for flexible manufacturing systems (FMSs). They are significant for improving the behaviors of the systems. Based on the Petri net models of FMSs, this paper embeds deadlock control policies into heuristic search algorithm, and proposes a deadlock-free scheduling algorithm to minimize makespan for FMSs. Scheduling is performed as heuristic search in the reachability graph of the Petri net. The searching process is guided by a heuristic function based on firing count vectors of state equation for the Petri net. By using the one-step look-ahead method in the optimal deadlock control policy, the safety of a state is checked. Experimental results are provided to show effectiveness of the proposed heuristic search approach in deadlock-free scheduling for FMSs.     

一种从海量不完备决策表中抽取规则的方法

提出了一种处理海量的不完备决策表的方法。将基于互信息的属性重要度作为启发式信息,利用遗传算法对不完备的原始决策表中的条件属性进行约简,形成包含missing值的决策表,称为优化决策表。利用原始决策表自身的信息,通过属性扩展,从优化决策表中抽取一致性决策规则,而无须计算missing值。该方法在UCI的8个数据集上的实验结果优于EMAV方法,是一种有效的从海量不完备决策表中抽取规则的方法。     

复杂网络强社团结构探测

社团结构是反映复杂网络整体性质的重要特征,本文从强社团结构定义出发提出简单启发式强社团结构探测算法,受启发因素为度-度负相关性和簇-度负相关性.利用该算法对空手道俱乐部成员关系网络和美国大学橄榄球队网络进行社团结构探测,验证了该算法能正确探测出网络的强社团结构.并将划分结果与传统划分进行比较分析,该算法未引入其它量化指标或中间变量,降低了计算复杂度,在采用方法上不同于单纯的分裂或聚合,有效地提高了探测速度,更适合大规模复杂网络社团结构探测.     

MSN网络的优化问题研究

研究了由MSN节点组成的应用层组播网络,讨论了度约束最小直径生成树(D-MDST)问题,并给出了求解该问题的BCT算法。提出了一种新的生成树编码方法——过程控制编码,该编码将启发式算法与遗传算法结合起来且具有编码简单、译码方便、适用常规遗传算子等优点。给出了基于该种编码的遗传算法,并将BCT算法作为过程控制编码的译码器。仿真结果表明了该遗传算法的有效性。     

基于PID控制的新型模糊控制方法

本文在文献[1]提出的模糊控制系统的基础上,通过启发式规则构造了调整比例因子的函数,改善了控制器的控制性能.     

基于启发式约简的虚拟企业知识共享风险预警

从虚拟企业知识共享风险预警的评价标准入手,提出具有层次结构的风险预警评价属性模型。然后,利用粗糙集的基本理论和方法,建立基于启发式属性约简的虚拟企业知识共享风险预警模型框架结构图,并给出基于分辨矩阵的启发式指标属性约简算法,进行指标优化。最后通过实例说明该预警模型的有效性及实用性。