A Modified Genetic Algorithm for Maximum Independent Set Problems

genetic algorithm is proposed for maximum independent set problems. A specially designed mutation operato is adopted to search the solution space more efficienily, where adjacen relation of a graph is inte-grated. The DIMACS benchmark graphs are used to test our algorithm, and the results show that the algorithm outper-forms our previous version. Moreover two new low bounds are found for graphs in DIMACS.

Estimation of the Mean of the Exponential Distribution Using Maximum Ranked Set Sampling with Unequal Samples

In this paper maximum ranked set sampling procedure with unequal samples (MRSSU) is proposed. Maximum likelihood estimator and modified maximum likelihood estimator are obtained and their properties are studied under exponential distribution. These methods are studied under both perfect and imperfect ranking (with errors in ranking). These estimators are then compared with estimators based on simple random sampling (SRS) and ranked set sampling (RSS) procedures. It is shown that relative efficiencies of the estimators based on MRSSU are better than those of the estimator based on SRS. Simulation results show that efficiency of proposed estimator is better than estimator based on RSS under ranking error.

Applying rough sets in word segmentation disambiguation based on maximum entropy model

To solve the complicated feature extraction and long distance dependency problem in Word Segmentation Disambiguation (WSD), this paper proposes to apply rough sets in WSD based on the Maximum Entropy model. Firstly, rough set theory is applied to extract the complicated features and long distance features, even from noise or inconsistent corpus. Secondly, these features are added into the Maximum Entropy model, and consequently, the feature weights can be assigned according to the performance of the whole disambiguation model. Finally, the semantic lexicon is adopted to build class-based rough set features to overcome data sparseness. The experiment indicated that our method performed better than previous models, which got top rank in WSD in 863 Evaluation in 2003. This system ranked first and second respectively in MSR and PKU open test in the Second International Chinese Word Segmentation Bakeoff held in 2005.

语义通信的数学理论

自从1948年经典信息论诞生以来,在其指导下,现代通信技术已经逼近了理论性能极限,例如信息熵H(U)、信道容量C=max_(p(x))I(X;Y)以及率失真函数R(D)=min_(p(x|x):Ed(x,x)≤D)I(X;X)。长期以来,由于经典信息论只研究语法信息,限制了通信科学的进一步发展。近年来,研究语义信息处理与传输的通信技术获得了学术界的普遍关注,语义通信开辟了未来通信技术发展的新方向,但还缺乏一般性的数学指导理论。为了解决这一难题,构建了语义信息论的理论框架,对语义信息的度量体系与语义通信的理论极限进行了系统性阐述。首先,通过深入分析各类信源的数据特征,以及各种下游任务的需求,总结归纳出语义信息的普遍属性——同义性。由此指出语义信息是语法信息的上级概念,是许多等效或相似语法信息的抽象特征,表征隐藏在数据或消息背后的含义或内容。将语义信息与语法信息之间的关系命名为同义映射,这是一种“一对多”映射,即一个语义符号可以由许多不同的语法符号表示。基于同义映射f这一核心概念,引入语义熵H_(s)(U)作为语义信息的基本度量指标,表示为信源概率分布与同义映射的泛函。在此基础上,引入上/下语义互信息I^(s)(X;Y)(I_(s)(X;Y)),语义信道容量C_(s)=max_(f_(xy))max_(p_((x)))I^(s)(X;Y)以及语义率失真函数R_(s)(D)=min_({f_(x),f_(x)})min_(p(x|x):Ed_(s)(x,x)≤D)I_(s)(X;X),从而构建了完整的语义信息度量体系。这些语义信息度量是经典信息度量的自然延伸,都由同义映射约束,如果采用“一对一”映射,则可以退化为传统的信息度量。由此可见,语义信息度量体系包含语法信息度量,前者与后者具有兼容性。其次,证明了3个重要的语义编码定理,以揭示语义通信的性能优势。基于同义映射,引入新的数学工具——语义渐近均分(AEP),详细探讨了同义典型序列的数学性质,并应用随机编码和同义典型序列译码/编码,证明了语义无失真信源编码定理、语义信道编码定理和语义限失真信源编码定理。类似于经典信息论,这些基本编码定理也都是存在性定理,但它们指出了语义通信系统的性能极限,在语义信息论中起着关键作用。由同义映射和这些基本编码定理可以推断,语义通信系统的性能优于经典通信系统,即语义熵小于信息熵H_(s)(U)≤H(U),语义信道容量大于经典信道容量C_(s)≥C,以及语义率失真函数小于经典率失真函数R_(s)(D)≤R(D)。最后,讨论了连续条件下的语义信息度量。此时,同义映射转换为连续随机变量分布区间的划分方式。相应地,划分后的子区间被命名为同义区间,其平均长度定义为同义长度S。特别是对于限带高斯信道,得到了一个新的信道容量公式C_(s)=B log[S^(4)(1+P/N_(0)B)],其中,平均同义长度S表征了信息的辨识能力。这一容量公式是经典信道容量的重要扩展,当S=1时,该公式退化为著名的香农信道容量公式。综上所述,语义信息论依据同义映射这一语义信息的本质特征,构建了语义信息的度量体系,引入新的数学工具,证明了语义编码的基本定理,论证了语义通信系统的性能极限,揭示了未来语义通信的巨大性能潜力。

基于加权分治技术的set packing精确算法

加权分治技术是算法分析中的一种新技术,该技术基于选择不同的量来描述分支子问题的大小,以求得到在最糟糕情况下最好的时间复杂度.setpacking问题是一典型的NP-hard问题,广泛应用于调度、代码优化和生物信息学等领域.本文对有n个子集的setpacking问题,引入符号全集变量N设计基于分支搜索策略的递归算法,并应用加权分治技术对算法加以分析,得到时间复杂度为O*(1.1686n+N)的精确算法,当N≤n/4时,比现有最佳的算法O*(1.2209n)更加有效.

基于粗糙集的不完备谣言信息系统的知识获取与决策

网络谣言可能扰乱人们的思想、心理和行为,引发社会震荡、危害公共安全,而微博等社交平台的广泛应用使得谣言造成的影响与危害变得更大,因此,谣言检测对于网络空间的有序健康发展具有重要的意义。当前谣言的自动检测技术更多关注检测模型的构建和输入数据的表现形式,而在改善数据质量以提高谣言识别效果方面的研究很少。基于此,本文将粗糙集理论应用于不完备谣言信息系统进行知识获取与决策,实质上是通过粗糙集理论解决不完备谣言信息系统的不确定性度量,冗余性以及不完备性等问题,以获得高质量的数据,改善谣言检测效果。首先系统总结了粗糙集理论中不确定性度量的方法,包括香农熵、粗糙熵、Liang熵以及信息粒度等四种不确定度量方法,并整理和推导了这四种不确定度量方法从完备信息系统到不完备信息系统的一致性拓展。基于上述总结的四种不确定度量方法,提出了基于最大相关最小冗余(MCMR,Maximum Correlation Minimum Redundancy)的知识约简算法。该方法基于熵度量方式,能够综合考量决策信息与冗余噪音,在UCI及Weibo等8个数据集上实验验证,结果表明本文算法优于几种基线算法,能够有效解决信息系统的冗余性。另外,提出了一种基于极大相容块的不完备决策树算法,在不同缺失程度数据上实验验证,结果表明本文算法能够有效解决信息系统的不完备性。

基于最大联盟粗糙集的三支聚类

针对邻域粗糙集模型受邻域参数影响大、刻画样本信息时不够精细等问题,提出了一种基于最大联盟理论的粗糙集模型。在标准化邻域信息系统后,引入最大联盟集来描述邻域颗粒信息,使得邻域粗糙集模型对信息的划分更加精细,从而显著降低了边界域的不确定性。将该模型与三支聚类相结合,设计了一种基于最大联盟粗糙集的三支聚类算法。在6个UCI公共数据集上进行对比实验,结果表明,所提算法相较于对比算法具有更好的聚类质量,在处理边界域样本时具有更高的比较正确率。

面向超图数据的最大独立集算法

超图是普通图的泛化表示,在许多应用领域都很常见,包括互联网、生物信息学和社交网络等.独立集问题是图分析领域的一个基础性研究问题,传统的独立集算法大多都是针对普通图数据,如何在超图数据上实现高效的最大独立集挖掘是一个亟待解决的问题.针对这一问题,提出一种超图独立集的定义.首先分析超图独立集搜索的两个特性,然后提出一种基于贪心策略的基础算法.接着提出一种超图近似最大独立集搜索的剪枝框架即精确剪枝与近似剪枝相结合,以精确剪枝策略缩小图的规模,以近似剪枝策略加快搜索速度.此外,还提出4种高效的剪枝策略,并对每种剪枝策略进行理论证明.最后,通过在10个真实超图数据集上进行实验,结果表明剪枝算法可以高效地搜索到更接近于真实结果的超图最大独立集.

一种面向船体扫描的多站点云鲁棒配准技术

为实现船舱外壳的点云配准,本文提出了一种基于回环约束的多站点云配准方法。首先,使用ISS从场景中提取关键点,将颜色信息与形状信息的直方图相融合,得到船舱点云外壳的CSHOT特征描述符;然后,基于回环的粗配准,构建全连接图,并利用GROR,结合最大一致性集约束和闭环约束移除误匹配;最后,采用全局的精配准LUM算法完成位姿优化。实验表明:该方法的平均RMSE为0.0077m,对船舱外壳的点云配准取结果较好。

排序集抽样下Weibull分布的产品可靠度估计

排序集抽样方法用于样本单元排序容易但测量困难的情形。产品可靠度是描述产品可靠性的重要度量指标,Weibull分布在可靠性试验中占有非常重要的地位。为了提高Weibull分布产品可靠度的估计效率,本文采用排序集抽样方法,研究了产品可靠度的极大似然估计,计算了Weibull分布形状参数和尺度参数的Fisher信息阵,证明了极大似然估计量的渐近正态性,并给出了新估计量的渐近方差。渐近相对效率和模拟相对效率的计算结果表明:排序集抽样下极大似然估计量的估计效率一致高于简单随机抽样下极大似然估计量。最后,单碳纤维强度数据的实际分析结果验证了排序集抽样方法的高效率性。

一种高效的平面点集凸包算法

为了提高凸包计算的效率,针对海岛正射点云的特点,提出了三级过滤措施,将平面点集抽稀至似边缘点集并排序,在此基础上改进了Graham算法,算法的时间复杂度为线性对数阶。通过对黄海开山岛等6个海岛点云进行计算,在普通、集中、扩散等3种类型情况下与多个经典算法进行对比,结果表明该算法平均运行效率为Quickhull算法的1.68倍、Andrew算法的8.93倍、Graham算法的20.65倍。因此,该算法可以被作为海岛、海岸、独立建筑物等正射点云凸包计算的关键算法。

适应电压支撑下的光伏发电机组最大功率点控制技术

常规的光伏发电机组最大功率点控制技术,在机械功率的调整上,缺少对适应电压支撑的考虑,导致最大功率点控制效果不好。基于此,提出适应电压支撑下的光伏发电机组最大功率点控制技术。使用功率信号反馈法,检测光伏发电机组的功率,将光伏发电机组的固有功率,作为主要参数。根据发电机组运行状态点的变化,对光伏发电机组功率进行跟踪,以光伏发电机组功率跟踪结果为基础,在适应电压支撑下,通过双输入单输出的结构,调节机械功率,导入调节后的机械功率,将其作为最大功率点控制的基础数据。按照隶属函数,对控制器参数进行实时调整,从而完成对光伏发电机组最大功率点控制。结果表明,在使用本文设计的方法进行控制后,光伏发电机组的最大功率振幅有效降低,控制效果较好,具有较好应用价值。

基于T-S模糊神经网络的光伏发电机组自动控制

光照情况变化会使光伏发电机组功率呈现不稳定性,加大光伏发电机组控制难度,为此,设计了基于T-S模糊神经网络的光伏发电机组自动控制方法。构建光伏阵列数学模型,分析在均匀和不均匀2种光照情况下光伏发电机组特性曲线。以分析结果为依据,采用T-S模糊神经网络构建光伏发电机组自动控制模型。为保证良好的控制效果,引入定比因子优化隶属度函数,输出最佳跟踪结果,结合最佳跟踪结果和自动控制模型实现光伏发电机组自动控制。测试结果显示,该方法能够完成光伏阵列特性分析,控制效果好。

A POLYNOMIAL ALGORITHM FOR FINDING THEMINIMUM FEEDBACK VERTEX SET OF A3-REGULAR SIMPLE GRAPH

A subset of the vertex set of a graph is a feedback vertex set of the graph if the resulting graph is a forest after removed the vertex subset from the graph. A polynomial algorithm for finding a minimum feedback vertex set of a 3-regular simple graph is provided.

Log-logistic parameters estimation using moving extremes ranked set sampling design

In statistical parameter estimation problems,how well the parameters are estimated largely depends on the sampling design used.In the current paper,a modification of ranked set sampling(RSS)called moving extremes RSS(MERSS)is considered for the estimation of the scale and shape parameters for the log-logistic distribution.Several traditional estimators and ad hoc estimators will be studied under MERSS.The estimators under MERSS are compared to the corresponding ones under SRS.The simulation results show that the estimators under MERSS are significantly more efficient than the ones under SRS.

Estimation of the Stress-Strength Reliability for Exponentiated Pareto Distribution Using Median and Ranked Set Sampling Methods

In reliability analysis,the stress-strength model is often used to describe the life of a component which has a random strength(X)and is subjected to a random stress(Y).In this paper,we considered the problem of estimating the reliability𝑅𝑅=P[Y<X]when the distributions of both stress and strength are independent and follow exponentiated Pareto distribution.The maximum likelihood estimator of the stress strength reliability is calculated under simple random sample,ranked set sampling and median ranked set sampling methods.Four different reliability estimators under median ranked set sampling are derived.Two estimators are obtained when both strength and stress have an odd or an even set size.The two other estimators are obtained when the strength has an odd size and the stress has an even set size and vice versa.The performances of the suggested estimators are compared with their competitors under simple random sample via a simulation study.The simulation study revealed that the stress strength reliability estimates based on ranked set sampling and median ranked set sampling are more efficient than their competitors via simple random sample.In general,the stress strength reliability estimates based on median ranked set sampling are smaller than the corresponding estimates under ranked set sampling and simple random sample methods.Keywords:Stress-Strength model,ranked set sampling,median ranked set sampling,maximum likelihood estimation,mean square error.corresponding estimates under ranked set sampling and simple random sample methods.

Zubair Lomax Distribution:Properties and Estimation Based on Ranked Set Sampling

In this article,we offer a new adapted model with three parameters,called Zubair Lomax distribution.The new model can be very useful in analyzing and modeling real data and provides better fits than some others new models.Primary properties of the Zubair Lomax model are determined by moments,probability weighted moments,Renyi entropy,quantile function and stochastic ordering,among others.Maximum likelihood method is used to estimate the population parameters,owing to simple random sample and ranked set sampling schemes.The behavior of the maximum likelihood estimates for the model parameters is studied using Monte Carlo simulation.Criteria measures including biases,mean square errors and relative efficiencies are used to compare estimates.Regarding the simulation study,we observe that the estimates based on ranked set sampling are more efficient compared to the estimates based on simple random sample.The importance and flexibility of Zubair Lomax are validated empirically in modeling two types of lifetime data.

小数据集下基于改进QMAP算法的BN参数学习

贝叶斯网络(bayesian network,BN)小数据集条件下,定性最大后验概率(qualitative maximum a posteriori,QMAP)估计往往会违反给定的专家约束,这就导致QMAP估计偏离真实值。为了克服该算法的缺陷,提出了一种改进的QMAP算法。首先,学习出QMAP估计,再结合保序回归方法对违反不等式约束的参数进行校正;然后使用一种微调策略对校正后的参数做进一步调整,使所得参数能够满足专家约束;最后,与最大似然估计(maximum likelihood estimation,MLE)和QMAP算法对比。仿真实验结果表明:在小数据集条件下,提出的算法满足所有约束条件,KL(Kullback-Leibler)散度始终低于其他2种算法,运行时间高于其他2种算法约0.1 s,影响甚微,且推理结果贴近真实值,偏差维持在±0.05之间。改进的QMAP算法的综合性能优于MLE、QMAP算法,并具有较好的实用性。

一种基于最大似然估计的宽带单脉冲测角改进方法

电大尺寸目标的宽带散射回波可看成多个强散射中心的共同作用结果,回波表现为高分辨距离像(high-resolution range profiles,HRRP)的特点。如何利用多个散射中心的回波能量,以提升单脉冲测角的性能是值得深入研究的问题。本文给出的宽带雷达单脉冲测角的最大似然估计(maximum likelihood estimate,MLE)算法,该方法能够积累扩散到多个距离单元的回波能量,从HRRP中获得信噪比(signal to noise ratio,SNR)增益。提出了一种基于回波本身来确定目标距离支集的方法,并在距离支集上实施MLE算法。仿真研究表明:本文所提方法相比于加权平均法和最强点法,能够有效利用距离方向多个散射点的回波能量。MLE算法的均方根误差(root mean square error,RMSE)性能逼近克拉美罗下界(Carmer Rao low bound,CRLB)。

基于粗糙集的微小缺陷图像对比度增强算法

设计了一种微小缺陷图像对比度增强算法。采用粗糙集理论将图像划分为不同类别,同一类别中像素间为不可分辨关系。并依据图像灰度值和噪声属性进一步将图像划分为子图,在子图中得到图像的明暗区域。对图像不同区域进行直方图均衡变换和直方图指数变换处理,处理后即可增强图像的对比度。仿真实验表明,处理后可突出显示图像中的微小细节,图像不同区域之间的划分效果更加明显,可以有效提升图像的对比度和视觉效果。