GPP问题的骨架分析与启发式算法设计

图的划分问题(GPP)是具有广泛应用背景的典型NP-难解问题,高效启发式算法一直是该领域的研究热点.作为设计启发式算法的有力工具,GPP的骨架分析存在理论分析结果匮乏、骨架规模过小等缺陷.文中采用构造偏移GPP实例的技巧,不仅在理论卜证明了获取GPP的骨架是NP-难解的,并且利用一般GPP实例与偏移实例的关系,实现了骨架规模的提高.在此基础上,文中对于目前求解GPP问题最好的算法之一的IBS进行了改进,提出了基于偏移实例的IBS算法(BI-IBS).算法BI-IBS首先构造偏移GPP实例,然后再利用局部最优解交集对它进行归约,最后再求解归约后的规模更小的新实例.实验结果表明,BI-IBS比现有算法在解的质量上有了较显著的提高.文中的工作较完善地解决了GPP的骨架研究存在的问题,所采用的构造偏移实例的技巧对于其它NP-难解问题的骨架理论分析及启发式算法设计亦具有较高的参考价值.

基于BDD的增量启发式搜索方法及其应用

增量启发式搜索是一种利用先前的搜索信息和启发信息提高本次搜索效率的方法，通常可用来解决动态环境下的重规划问题。在人工智能领域，一些实时系统常常需要根据外界环境的变化不断修正自身，这样就会产生一系列变化较小的相似问题，此时应用增量启发式搜索将会非常有效。另一方面，基于BDD的强大的搜索技术利用BDD有效操作性以及化简后唯一性的优点， 在一定程度上缓解了模型检测的状态爆炸问题，使得被检测状态的个数大大增加。 1、本文结合基于BDD的启发式搜索和基于BDD的增量搜索这两种方法给出了基于BDD的增量启发式搜索方法， 基于BDD的增量启发式搜索综合了基于BDD的搜索、增量搜索以及启发式搜索这三种方法的优点。它既用BDD作为数据结构以提高搜索的空间效率， 又结合了增量搜索的思想来提高重搜索的效率，同时，又引入了启发函数来进一步压缩搜索空间。 2、本文介绍了基于BDD的增量启发式搜索算法BDDRPA*并用大量的实验结果证明BDDRPA*的高效性。给定一个搜索问题， BDDRPA*算法先用基于BDD的启发式搜索方法搜出一条从初始节点到目标节点的最短路径；接着， 问题的状态格局发生改变，BDDRPA*再用基于BDD的增量搜索方法根据旧格局的迁移关系BDD_T构造出新格局的迁移关系BDD_{T'}， 然后再用启发式方法搜索路径，如此反复下去。 3、本文介绍了基于BDD的动态增量启发式搜索算法BDDD*并用大量的实验结果证明BDDD*的高效性。 BDDD*算法在机器人边走边扫描的过程中，不断根据机器人新获得的信息更新已知地图并重新规划路线。每次规划时，BDDD*都假设未知的领域没有任何障碍物， 也就是每个位置都是可通的，它按照这个假设去计算从当前位置到目标位置的最短路径。如果在行走的过程中扫描到了障碍物，它就把这条信息添加到它的地图中，然后重复 上面的过程，直到到达目标位置或者发现每条路径都被堵死为止。 BDDRPA*算法和BDDD*算法可以应用到机器人线路规划、智能交通及计算机网络的线路规划问题中。 另外，在机器学习和控制领域，也可以考虑使用BDDRPA*算法和BDDD*算法。

Study of turbulent heat transfer of aviation kerosene flows in a curved pipe at supercritical pressure

The now and heat transfer characteristics of China No. 3 aviation kerosene in a heated curved tube under supercritical pressure are numerically investigated by a finite volume method. A two-layer turbulence model, consisting of the RNG k-epsilon two-equation model and the Wolfstein one-equation model, is used for the simulation of turbulence. A 10-species kerosene surrogate model and the NIST Supertrapp software are applied to obtain the thermophysical and transport properties of the kerosene at various temperature under a supercritical pressure of 4 MPa. The large variation of thermophysical properties of the kerosene at the supercritical pressure make the flow and heat transfer more complicated, especially under the effects of buoyancy and centrifugal force. The centrifugal force enhances the heat transfer, but also increases the friction factors. The rise of the velocity caused by the variation of the density does not enhance the effects of the centrifugal force when the curvature ratios are less than 0.05. On the contrary, the variation of the density increases the effects of the buoyancy. (C) 2010 Elsevier Ltd. All rights reserved.

Discrete wavelets transform for signal denoising in capillary electrophoresis with electrochemiluminescence detection

Discrete wavelets transform (DWT). was applied to noise on removal capillary electrophoresis-electrochemiluminescence (CE-ECL) electropherograms. Several typical wavelet transforms, including Haar, Daublets, Coiflets, and Symmlets, were evaluated. Four types of determining threshold methods, fixed form threshold, rigorous Stein's unbiased estimate of risk (rigorous SURE), heuristic SURE and minimax, combined with hard and soft thresholding methods were compared. The denoising study on synthetic signals showed that wave Symmlet 4 with a level decomposition of 5 and the thresholding method of heuristic SURE-hard provide the optimum denoising strategy. Using this strategy, the noise on CE-ECL electropherograms could be removed adequately. Compared with the Savitzky-Golay and Fourier transform denoising methods, DWT is an efficient method for noise removal with a better preservation of the shape of peaks.

Molecular evidence for the sister relationship of the eastern Asia-North American intercontinental species pair in the Podophyllum group (Berberidaceae)

The presumed pair relationships of intercontinental vicariad species in the Podophyllum group (Sinopodophyllum hexandrum vs. Podophyllum pelatum and Diphylleia grayi vs. D. cymosa) were recently, considered to be paraphyletic. In the present paper, the trnL-F and ITS gene sequences of the representatives were used to examine the sister relationships of these two vicariad species. A heuristic parsimony analysis based on the trnLF data identified Diphylleia as the basal clade of the other three genera, but provided poor resolution of their inter-relationships. High sequence divergence was found in the ITS data. ITS1 region, more variable but parsimonyuninformative. has no phylogenetic value, Sequence divergence of the ITS2 region provided abundant, phylogenetically informative variable characters. Analysis of ITS2 sequences confirmeda sister relationship between the presumable vicariad species, in spite of a low bootstrap support for Sinopodophyllum hexandrum vs. Podophyllum pelatum. The combined ITS2 and trnL-F data enforced a sister relationship between Sinopodophyllum hexandrum and Podophyllum pelatum with an elevated bootstrap support of 100%. Based on molecular phylogeny, the morphological evolution of this group was discussed. The self-pollination might have evolved from cross-fertilization two times in this group. The different pollination and seed dispersal systems of Sinopodophyllum hexandrum and Podophlyllum pelatum resulted from their adaptations to different ecological habitats. The divergence time of Sinopodophyllum hexandrum-Podophyllum pelatum is estimated to be 6.52+/-1.89 myr based on the ITS divergence. The divergence of this species pair predated or co-occurred with the recent uplift of the Himalayas 4-3 myr during the late Miocene and the formation of the alpine habitats. Sinopodophyllum hexandrum developed a host of specialized characters in its subsequent adaptation to the arid alpine surroundings. The present study confirmed the different patterns of species relationship between Asian-North American disjuncts. The isolation of plant elements between North America and eastern Asia must have been a gradual process, resulting in the different phylogenetic patterns and divergence times of the disjuncts.

无线传感器网络中一种启发式最小连通支配集算法

针对最小连通配集问题设计了一种具有较高能量效率的启发式算法。算法首先把网络中所有的节点作为最小连通支配集的一个初始解,然后利用启发式修剪策略剔除冗余节点从而减小最小连通支配集的大小,直到没有冗余节点存在。文中将算法分成集中式和分布式两种情况进行了详细讨论。仿真结果表明,由于实现简便,该算法与其他已有算法相比较,在算法复杂性和算法稳定运行时间上有一定的优势。

基于粗糙集和多Agent系统的知识挖掘

通过优化知识表达系统中条件属性对决策属性的依赖度,深入研究了粗糙集并与多Agent系统相结合。利用离散粒子群算法,提出一种基于粒子群优化的粗糙集知识约简算法,该算法解决了启发式算法无法全局搜索进行约简的问题。最后通过在矿井中调度信息的应用验证了有效性。

基于启发式节点增强策略的PRM路径规划方法

针对一般的PRM方法用于移动机器人对复杂地形路径搜索存在的缺陷 ,本文对PRM方法进行了改进 ,提出了一套基于启发式的节点增强的策略 ,提高了PRM方法节点增强阶段对环境的适应性 .此外 ,本文建立了相应的仿真实验系统对策略的有效性进行了实验与分析

基于代理模型的水下滑翔机机翼设计优化方法

在复杂工程系统的概念设计优化中,高精度数值分析方法得到广泛应用,将高精度数值分析与优化方法有机结合,对设计空间展开全面搜索与寻优,已经成为现代设计优化方法的重要发展方向。以水下滑翔机的概念设计为研究对象,引入代理模型,控制高精度分析试验的数量,有效地化解精度与效率之间的矛盾。将参数化几何建模、网格划分以及流体数值模拟分析集成为自动分析流程,并以此为基础采用试验设计理论,构建代理模型,解决水下滑翔机机翼的多目标设计优化问题。给出基于代理模型的设计优化过程,并系统地比较几种试验设计方法的适应性,重点讨论多项式响应面和径向基函数代理模型,所得代理模型相对误差小于2%。采用梯度寻优方法与遗传算法在给定设计空间内进行全面搜索,获得机翼的最佳平面构形,水下滑翔机的升阻比提高6.76%,俯仰力矩的绝对值由0.2760N•m降低为0.0015N•m,提高水下滑翔机的运动性能。

港口业船舶优化调度模型设计

以港口船舶计划调度为研究背景 ,分析了港口业计划调度的特征 ,提出了生产计划调度的系统框架 ,并在此基础上建立了以船舶拖期惩罚费用为最小 ,多种因素约束下的调度模型 ,将人工智能技术应用到实际生产调度中 ,实现分层次、分级研究多种资源约束条件下的计划调度和优化

一个用于机器人自然语言理解的英语句法分析系统

在低挡微机中速度较慢的串行处理硬设备条件下，利用本文提出的启发式概念，分层搜索和匹配策略以及设置最大搜索长度等方法，可使推理速度提高一个数量级以上．此外，通过引入语义信息，分阶段消除歧义，自顶向下与自底向上相结合，以及把一般疑问句一律变成相应陈述句的方法，解决了自动英语句法分析中的一系列难题，缩小了知识库的规模。

考虑负荷的制造单元划分方法

制造单元的划分是实施单元化生产的关键途径。本文提出了一种基于工件制造工艺的并考虑机床负荷的单元划分算法。首先根据工件的加工特征及机床负荷定义了同类实体之间相似性。然后根据启发式规则选择工件族及制造单元的种子元素,并以聚类块内的离散程度作为评价标准,对系统内的工件和机床进行了聚类。

CIMS优化排序的度量空间分析法

本文建立了排序的度量空间,并且在该空间上建立了映射概念.在此基础上,应用采样方法,讨论了采样次数与优化的关系,并提出了均匀采样的启发式方法.

数控自动编程专家系统

本文简要地介绍了数控自动编程专家系统.其中包括:专家系统知识表示的形式;分层次的黑板结构;前向推理求解策略和相应的解释功能;系统针对不同类型的曲线组合,采用不同的独立的知识源(KS)进行处理.由于在知识的处理上采用编码技术,在前向推理求解策略中使用启发信息和“剪技”技术,提高了系统的时空效率.系统中的规划程序能自动规划切削路径.输出供数控车床使用的 NC 代码,并可在显示屏上进行图形显示和切削仿真.目前原型系统已经在 IBM-PC 和 Sun3/60计算机上利用FORTRAN 语言实现.

强化学习算法中启发式回报函数的设计及其收敛性分析

回报函数设计的好与坏对学习系统性能有着重要作用,按回报值在状态-动作空间中的分布情况,将回报函数的构建分为两种形式:密集函数和稀疏函数,分析了密集函数和稀疏函数的特点.提出启发式回报函数的基本设计思路,利用基于保守势函数差分形式的附加回报函数,给学习系统提供更多的启发式信息,并对算法的最优策略不变性和迭代收敛性进行了证明.启发式回报函数能够引导学习,加快学习进程,从而可以实现强化学习在实际大型复杂系统应用中的实时控制和调度.