一种基于加权深度森林的离群数据挖掘算法

深度森林是一种有效的机器学习方法,但在级联森林模块中,森林中子树的特征选择随机性较大,使用传统的平均值法可能导致森林的预测概率存在一定误差,从而影响整个算法性能.针对以上问题,提出了一种基于加权深度森林离群数据挖掘算法(Weight Deep Forest, WDF).首先,通过森林的预测概率定义权重因子μ,描述当前层森林准确率大小;其次,在级联森林模块的构建过程中,把权重因子μ作为级联层中每个森林的权重,从而降低森林中根节点特征的随机选择对算法性能的影响;根据数据样本分布的不同,通过计算其类密度重新定义了局部孤立因子α,描述数据离群程度大小;最后利用UCI数据集以及LAMOST光谱数据对算法进行验证,结果表明该算法与同类算法相比在离群点检测方面具有更高的挖掘质量.     

一种针对名义型属性数据聚类中属性赋权的方法

在面向名义型属性的聚类问题中,各个属性权重的选择对于聚类效果至关重要。在实践中,常常赋予各个属性相同的权重或者根据领域专家的意见赋予经验权重。在缺乏领域专家意见时,充分考虑各个属性对聚类结果贡献程度的不同,引入监督学习的思想对部分标记数据进行训练,设计遗传算法寻找各个属性更优的权重,以期获得更好的聚类效果。     

一种自适应加权SpPCA单样本人脸识别算法

子模式主成分分析(SpPCA)算法忽略了人脸不同分块应该具有不同的重要性.为了解决此问题,提出一种自适应加权SpPCA单样本人脸识别算法,对人脸图像的不同分块自适应地计算其权重.算法对人脸进行分块,按照SpPCA算法将各个分块投影到特征脸的基坐标上,并以每个模块LBP编码的纹理图像信息熵来表征该模块的权值;将模块的权重赋予该模块的特征脸投影,并得到最终分类结果.实验在Yale B和扩展Yale B人脸数据集上进行测试.实验表明,该算法得到了较好的识别结果,有效地弥补了SpPCA算法的不足.     

基于蚁群系统的参数自适应粒子群算法及其应用

为了解决粒子群算法惯性权重自适应问题,提出一种基于蚁群系统的惯性权重自适应粒子群算法(AS-PSO).AS-PSO首先将惯性权重取值区间离散化,各个惯性权重子区间在初期赋予相同的信息素;然后,粒子群算法中的各个粒子,根据各个惯性权重子区间中的信息素浓度和粒子在搜索空间中分布的先验知识,确定各个惯性权重子区间的选择概率,并进而实现粒子的空间搜索;最后,基于粒子的进化信息,实现惯性权重子区间信息素浓度的更新.仿真研究表明,AS-PSO算法在种群进化寻优的同时,能根据种群的进化信息,通过蚁群算法实现惯性权重参数的自适应调整和进化,且不增加测试函数的调用次数;算法寻优性能优于传统的自适应粒子群算法和根据速度信息自适应调整参数的粒子群算法.同时,算法实际应用于复杂系统模型参数的优化估计,获得满意结果.     

基于概率语言和改进TODIM的产品服务匹配方法

针对概率语言信息下产品服务模块双边匹配问题,考虑匹配主体间的相互作用与影响以及决策者的心理行为,提出一种基于BWM (best-worst method)、DEMATEL (decision making trial and evaluation laboratory)权重确定方法和改进TODIM的概率语言双边匹配方法.首先,通过BWM方法和概率语言DEMATEL方法确定各匹配模块综合权重;然后,通过TODIM方法计算产品服务模块的总体优势度,得到产品服务模块双边匹配满意度矩阵;接着,在此基础上,构建以产品和服务效用达到最大的多目标优化模型,利用线性加权法将其转化为单目标模型求解,进而得到最优匹配方案;最后,通过新能源汽车产品服务匹配的案例,验证所提出方法的有效性和可行性,为新能源汽车产品与服务融合发展提供新方向.     

非均匀选择概率下异步随机Gossip共识算法及优化

异步随机Gossip算法火都采用以均匀选择概率为基础的时间模型,并未充分考虑网络拓扑结构对智能体获取信息的影响,为此本文提出了一种更为合理的基于非均匀选择概率的异步随机Gossip算法.首先给出了非均匀选择概率下的异步时间模型,在概率意义下分析了算法的收敛性.算法的收敛速度取决于概率化权重矩阵的第2大特征值,并利用投影次梯度算法给出了选择概率优化方法.仿真分析表明,在非均匀选择概率下可通过对各智能体选择概率的优化,改善算法的收敛速度,并且弥补了传统的通信概率矩阵优化方法受制于网络拓扑结构的不足.     

考虑决策者心理行为的概率语义术语集多属性决策方法

概率语义术语集可以通过给语义赋予概率以表达不同程度偏好,采用概率语义术语集获取专家犹豫和不确定的评价信息。针对传统多属性决策中指标权重确定没有考虑指标间相互影响关系的问题,采用概率语义DEMATEL方法分析指标间的相互影响关系,其中采用二元语义将指标间关联关系概率语义术语集的得分函数转换为精确数值,得到指标的权重。考虑决策者的不同偏好和心理行为,采用改进的概率语义TODIM方法对决策对象进行排序。最后以某班轮公司的综合竞争力评估为例,验证了所提方法的有效性。     

基于优化蚁群和标签传播的复杂网络社区检测

标签传播算法被广泛应用于复杂网络中社区检测及其它工程领域，但由于其标签更新的随机性，降低了社区检测的稳定性，为此提出一种LPA-5SA(LPA-five step Ant)算法。使用蚁群优化算法的概率转移公式将标签传播算法的随机选择变为目标函数高概率选择，通过5步更新法提高信息素选择权重，提高社区检测的稳定性和准确率。该算法在真实的网络和人工合成的网络中进行实验，结果用模块度和NMI指标进行评价，验证了该方法的准确率和稳定性。     

考虑外部环境变化的分阶段动态群决策方法

研究决策者权重部分未知的概率犹豫模糊分阶段动态群决策问题.针对外部环境的变化,结合符号距离测度,提出考虑外部环境变化的分阶段群决策方法.首先,基于元素的方差及个数差异定义概率犹豫模糊元的犹豫度公式,并在此基础上定义概率犹豫模糊元的符号距离公式.然后,根据外部环境的变化会导致每个时序阶段获得的信息存在差异的特点,构建动态决策模型以确定各个时序阶段的决策者权重,进而分阶段集结信息,形成决策过程方案链.最后,通过算例分析验证了所提出方法的有效性与合理性.     

基于文本序列错误概率和中文拼写错误概率融合的汉语纠错算法

中文拼写纠错是一项检测和纠正文本中拼写错误的任务。大多数中文拼写错误是在语义、读音或字形上相似的字符被误用,因此常见的做法是对不同模态提取特征进行建模。但将不同特征直接融合或是利用固定权重进行求和,使得不同模态信息之间的重要性关系被忽略以及模型在识别错误时会出现偏差,阻止了模型以有效的方式学习。为此,提出了一种新的模型以改善这个问题,称为基于文本序列错误概率和中文拼写错误概率融合的汉语纠错算法。该方法使用文本序列错误概率作为动态权重、中文常见拼写错误概率作为固定权重,对语义、读音和字形信息进行了高效融合。模型能够合理控制不同模态信息流入混合模态表示,更加针对错误发生处进行学习。在SIGHAN基准上进行的实验表明,所提模型的各项评估分数在不同数据集上均有提升,这验证了该算法的可行性。     

利用公共子序列求解固定边框布图问题

提出一种新的固定边框的布图算法．该算法采用SP表示方法,以公共子序列为基础,在随机搜索过程中限定布图宽度的变化,从而使减小芯片面积的目标与固定边框的目标在一定程度上取得一致．与现有的固定边框布图算法相比,文中算法在边框更紧凑、宽长比更大的条件下具有更高的成功率和更短的运行时间．此外,文中算法在布图初始阶段就可以对固定边框的合理性进行评估,避免了因给定的边框不合理而带来的时间上的浪费．     

Fixed-outline floorplanning using robust evolutionary search

Typical floorplanning concerns a series of objectives, such as area, wirelength, and routability, etc., with various aspect ratios of modules in a free-outline regime. However, in a hierarchical design flow for very large ASICs and SoCs, a floorplan can be completely useless for a situation where its outline is dissatisfied. In this paper, we study the fixed-outline floorplanning problem that is more applicable to the hierarchical design style. We develop an efficient algorithm based on robust evolutionary search and achieve substantially improved success rate. We also propose a new approach to handle soft modules to further adjust the generated floorplan to fit into the prescribed chip outline. The effectiveness of our methods is demonstrated on several large cases of MCNC and GSRC benchmarks.     

基于角模块链的不确定模块布图规划算法

布图规划是VLSI/SoC设计的重要步骤之一。为了缩短设计周期,在设计阶段的早期,也就是在模块物理信息没有完全确定之前就要进行布图规划,从而能估计出所设计的芯片的有关性能。因此,就必须开展不确定模块的布图规划研究。提出了一种基于角模块链(CornerBlockList,CBL)的不确定模块布图规划算法,采用模拟退火算法进行优化。实验结果表明,对于系统中有30%的模块信息不确定时,所获得的面积方差在1%左右,该算法是有效的。     

一种有效的面向软模块的VLSI布图规划算法

随着VLSI设计规模和复杂度的提高,以可复用IP为代表的软模块得到了广泛的应用,针对软模块的布图规划问题随之变得日益重要。基于正则波兰表达式（NPE）表示,提出了一种形状曲线相加算法来处理软模块之间的组合运算,可获得每个布图解下最优的布图实现。通过回溯算法来确定每个模块的位置及形状,并将它们集成到模拟退火算法的流程之内。应用MCNC和GSRC电路对算法进行了测试,结果表明该算法解决软模块的布图规划问题是可行和有效的。     

Hierarchical congregated ant system for bottom-up VLSI placements

A new perturbation method, called Hierarchical-Congregated Ant System (H-CAS) has been proposed to perform the variable-order bottom-up placement for VLSI. H-CAS exploits the concept of ant colonies, where each ant will generate the perturbation based on differences in dimensions of the VLSI modules in hard modules floorplanning and differences in area of the VLSI modules in soft modules floorplanning. In this paper, it is mathematically proved that the area-based two-dimensional cost function for hard modules floorplanning problem can be reduced to the difference-based one dimensional cost function which avoids local optima problems. Lack of global view is a major drawback in the conventional bottom-up hierarchy, and hence, ants in the H-CAS are made to introduce global information at every level of bottom-up hierarchy. A new relative whitespace formula for bottom-up hierarchy is derived mathematically and the H-CAS embeds it in its unique update formula. The ants in H-CAS are able to communicate among themselves and update the pheromone trails when they reach the destination. Then, the ants will congregate, share their experiences and construct a new pheromone trails that belong to this newly constructed group. The congregation of at least two ants and/or ant consortiums would lead to reduction in subsequent search space and complexity. H-CAS gives the best-so-far near optimal solutions and yields low standard deviations of areas involving 9–600 blocks based on Microelectronics Center of North Carolina (MCNC) and Giga scale Systems Research Center (GSRC) benchmarks. The results obtained establish that H-CAS is a high performance placer in respect of scaling, convergence, precision, stability, and reliability. The above claims are based on the comparisons with the other floorplanning algorithms as depicted graphically.     

基于Single-Sequence布图规划边界约束问题的研究

布图规划是VLSI设计中非常重要的步骤.在计算机辅助设计中,布图被表示成编码以使其容易被计算机处理.Single-Sequence就是一种非常有用的表示布图的编码方法.一个布图中,一些模块如输入输出模块,必须放置在芯片的边界处,这种限制被称为边界约束.本论文提出了用模拟退火算法寻求最优布圈的方法,有效地解决了布图规划的边界约束问题.     

An iterative merging algorithm for soft rectangle packing and its extension for application of fixed-outline floorplanning of soft modules

We address an important variant of the rectangle packing problem, the soft rectangle packing problem, and explore its problem extension for the fixed-outline floorplanning with soft modules. For the soft rectangle packing problem with zero deadspace, we present an iterative merging packing algorithm that merges all the rectangles into a final composite rectangle in a bottom-up order by iteratively merging two rectangles with the least areas into a composite rectangle, and then shapes and places each pair of sibling rectangles based on the dimensions and position of their composite rectangle in an up-bottom order. We prove that the proposed algorithm can guarantee feasible layout under some conditions, which are weaker as compared with a well-known zero-dead-space packing algorithm. We then provide a deadspace distribution strategy, which can systematically assign deadspace to modules, to extend the iterative merging packing algorithm to deal with soft packing problem with deadspace. For the fixed-outline floorplanning with soft modules problem, we propose an iterative merging packing based hierarchical partitioning algorithm, which adopts a general hierarchical partitioning framework as proposed in the popular PATOMA floorplanner. The framework uses a recursive bipartitioning method to partition the original problem into a set of subproblems, where each subproblem is a soft rectangle packing problem and how to solve the subproblem plays a key role in the final efficiency of the floorplanner. Different from the PATOMA that adopts the zero-dead-space packing algorithm, we adopt our proposed iterative merging packing algorithm for the subproblems. Experiments on the IBM-HB benchmarks show that the proposed packing algorithm is more effective than the zero-dead-space packing algorithm, and experiments on the GSRC benchmarks show that our floorplanning algorithm outperforms three state-of-the-art floorplanners PATOMA, DeFer and UFO, reducing wirelength by 0.2%, 4.0% and 2.3%, respectively.     

VLSI平面布图规划中模拟退火算法的加速策略

布局是现代VLSI物理设计中十分关键的步骤,而模拟退火等智能算法在针对宏模块布局的平面布图规划问题中得到广泛应用。针对应用于VLSI平面布图规划的模拟退火算法进行了研究和分析,并针对布图本身特性在退火算法中采用了一种导向性的邻域构造策略来加速算法的收敛,有效地提高了平面布图规划中模拟退火算法的搜索效率。     

A modified simulated annealing algorithm and an excessive area model for floorplanning using fixed-outline constraints

Outline-free floorplanning focuses on area and wirelength reductions, which are usually meaningless, since they can hardly satisfy modern design requirements. We concentrate on a more difficult and useful issue, fixed-outline floorplanning. This issue imposes fixed-outline constraints on the outline-free floorplanning, making the physical design more interesting and challenging. The contributions of this paper are primarily twofold. First, a modified simulated annealing (MSA) algorithm is proposed. In the beginning of the evolutionary process, a new attenuation formula is used to decrease the temperature slowly, to enhance MSA’s global searching capacity. After a period of time, the traditional attenuation formula is employed to decrease the temperature rapidly, to maintain MSA’s local searching capacity. Second, an excessive area model is designed to guide MSA to find feasible solutions readily. This can save much time for refining feasible solutions. Additionally, B*-tree representation is known as a very useful method for characterizing floorplanning. Therefore, it is employed to perform a perturbing operation for MSA. Finally, six groups of benchmark instances with different dead spaces and aspect ratios—circuits n10, n30, n50, n100, n200, and n300—are chosen to demonstrate the efficiency of our proposed method on fixed-outline floorplanning. Compared to several existing methods, the proposed method is more efficient in obtaining desirable objective function values associated with the chip area, wirelength, and fixed-outline constraints.     

一种考虑电压岛边界约束的多电压布图算法

多电压设计(multiple supply voltage,MSV)是降低SoC功耗的有效方法之一.为便于电压岛供电引脚的放置,提出了一种考虑电压岛边界约束的多电压布图算法.首先,基于切分树表示的布图解特点,提出一种边界检查算法快速确定所有模块的边界信息.其次,以优化功耗为目标采用改进动态规划方法进行多电压分配并构建电压岛.最后,以模拟退火算法作为搜索引擎对芯片的面积、线长和功耗进行协同优化.为减少SA迭代次数,采用了一个两阶段的降温策略.对GSRC电路的实验结果表明,该算法可获得满足边界约束的多电压布图,且和不考虑边界约束时相比,仅在功耗上平均增加5.2％.