基于信念点裁剪策略树的POMDP求解算法

针对大规模部分可观察马尔可夫决策过程(POMDP)算法中策略树规模指数级增长、已证信念点(witness point,WP)求解困难的问题,根据策略树值函数是分段线性凸函数的特点,提出一种基于信念点的策略树增量裁剪和值迭代求解算法.在策略树生成过程中,利用边界点进行无损裁剪,利用中间点进行有损裁剪,并利用实时信念状态分布求取近似最优解.对比实验结果表明,该算法能快速收敛,以更少的时间获得相当精度的奖赏值.     

k-匿名模型中准标识符最佳值的求解问题

准标识符值是影响k-匿名表隐私保护程度和数据质量的关键因素。如何在给定各个准标识符属性泛化树的情况下求解准标识符最佳值,对匿名表在满足隐私保护要求的同时达到最高的数据质量具有重要意义。针对这一问题,证明了准标识符最佳值的求解问题是NP-完全问题,提出了准标识符最佳值的近似求解方法,并给出了准标识符最佳值的近似求解算法;最后,对算法进行了正确性证明和时间复杂度分析。     

一般间隙近似无重叠模式匹配

具有间隙约束条件模式匹配问题是序列模式挖掘问题的基础与核心.无重叠模式匹配是其中的一种方法,当前研究是在间隙为正的精确模式匹配,为了进一步增加匹配的灵活性,本文探索了一般间隙近似无重叠模式匹配问题.本文提出一种有效的求解算法,该算法首先将问题转化为网树;然后为了有效地避免可行解丢失,提出近似监测机制以解决该问题;采用迭代搜索最左孩子策略的方式寻找无重叠出现;之后在网树上剪枝找到的无重叠出现,并迭代上述过程直至没有新的无重叠出现产生.最后本文理论分析了算法的空间复杂度和时间复杂度.大量实验结果验证了本文算法具有较好的求解质量及求解效率.     

一种新的求解度约束最小生成树的遗传算法

染色体编码是遗传算法的关键内容,编码的优劣并直接影响算法的性能.提出了基于过程控制的生成树编码方法--PC编码.PC码为定长的整数向量,使用PC编码求解特定生成树问题时,首先选定的一个有效算法,并将修改为可控算法,然后用编码向量控制算法的运行过程,从面得到唯一生成树.为了求解度约束最小生成树(DCMST)问题,在D-Prim算法的基础上,设计r过程可控的度约束生成树构造PC-Prim算法.给出了以PC-Prim算法作为译码器的求解DC-MST问题的遗传算法.仿真结果表明遗传算法求解精度和运行时间均优于参与其他算法.     

基于CBT的多源Steiner树构造算法

构造最小代价树问题可形式化为图论中Steiner树问题。而Steiner树的求解已经被证明是一个NP-complete问题，不可能在多项式时间求得其精确解，所以出现许多启发式算法：在可接受时间内，得到一棵近似的最优多播树。这些算法一般先指定所有链接边的费用，通过一定方法或规则，找出包含源端和所有目的端的一棵近似最优的多播树。很显然，它们并没有考虑由于路径的共享重叠而引起最小生成树链接边费用的变化。现利用CBT算法思想对变化的费用进行建模并对典型启发式算法作了改进，以适应不断变化了的链路费用。     

近乎最佳的Manhattan型Steiner树近似算法

求解最佳的Manhattan型Steiner树问题(minimum rectilinear Steiner tree,简记为MRST问题)是在VLSI布线、网络通信中所遇到的组合优化问题,同时也是一个NP-难解问题.该文给出对该问题的O(n²)时间复杂性的近似算法.该算法在最坏情况下的近似比严格小于3/2.计算机实验结果表明,所求得的支撑树的平均费用与最佳算法的平均费用仅相差0.8%.该算法稍加修改,可应用到三维或多维的Manhattan空间对Steiner问题求解,且易于在并行与分布式环境下编程实现     

基于粗糙集理论与差分进化的混合多目标优化算法

针对传统算法求解约束多目标优化所得近似解精度不高、分布性能不好的问题,提出一种基于粗糙集理论与差分进化的混合算法.首先利用多目标差分进化生成一个初始的近似 Pareto 前沿;然后利用粗糙集理论提高Pareto 前沿的分布质量.选取一组标准的多目标约束测试问题,采用混合算法与 NSGA-II 算法进行仿真求解,对比结果表明,所提出的算法在求解约束多目标优化问题时具有更好的近似解分布和更优越的近似解性能.     

基于离散粒子群优化算法求解矩形件排样问题

改进了一种近似排样算法,并将改进的近似排样算法与离散粒子群优化算法结合求解矩形件排样问题.设计了应用离散粒子群优化算法求解矩形件排样问题的相关操作和定义,给出了离散粒子群优化算法求解矩形件排样问题的详细步骤,最后通过实验测试,验证了算法的有效性.     

求解QAP问题的近似骨架导向快速蚁群算法

QAP(quadratic assignment problem)问题是经典的组合优化问题之一,广泛应用于许多领域中.针对QAP问题,提出了一种新的蚁群算法--近似骨架导向的快速蚁群算法(ABFANT).该算法的基本原理是通过对局部最优解的简单相交操作得到QAP问题实例的近似骨架(approximate-backbone),利用这些近似骨架可以极大地缩小QAP问题的搜索空间,而同时不降低搜索的性能,最后对这个缩小后的搜索空间,直接用当前求解QAP问题最好的启发式算法之一-快速蚁群算法(FANT)求解得到问题的解.在QAPLIB中的典型实例上的实验结果表明,近似骨架导向的快速蚁群算法明显优于快速蚁群算法.此外,指出基于近似骨架的算法思想可以很容易地被移植到其他求解QAP问题的启发式算法中.     

基于直角多边形的R树结点的分裂算法

对于空间查询来说,目标近似是一个非常重要的问题.在R树中常用的是最小包围矩形(MBR),但是它的近似精度不是很高,因此用直角多边形来近似空间对象可以提高近似的精度.文中主要探讨了结点是直角多边形近似的R树的结点分裂算法.     

Power Control Algorithm for Wireless Cellular System

A novel distributed power control algorithm based on interference estimation is presented for wireless cellular system. A classical result of stochastic approximation is applied in this scheme. The power control algorithm is converted to seeking for the zero point problem of a certain function. In this distributed power algorithm, each user iteratively updates its power level by estimating the interference. It does not require any knowledge of the channel gains or state information of other users. Hence, the proposed algorithm is robust. It is proved that the algorithm converges to the optimal solution by stochastic approximation approach.     

Approximation Algorithms for the Fixed-Topology Phylogenetic Number Problem

In the l -phylogeny problem, one wishes to construct an evolutionary tree for a set of species represented by characters, in which each state of each character induces no more than l connected components. We consider the fixed-topology version of this problem for fixed-topologies of arbitrary degree. This version of the problem is known to be NP -complete for l ≥ 3 even for degree-3 trees in which no state labels more than l+1 leaves (and therefore there is a trivial l + 1 phylogeny). We give a 2 -approximation algorithm for all l ≥ 3 for arbitrary input topologies and we give an optimal approximation algorithm that constructs a 4 -phylogeny when a 3 -phylogeny exists. Dynamic programming techniques, which are typically used in fixed-topology problems, cannot be applied to l -phylogeny problems. Our 2 -approximation algorithm is the first application of linear programming to approximation algorithms for phylogeny problems. We extend our results to a related problem in which characters are polymorphic. Received June 9, 1997; revised March 13, 1998.     

无线蜂窝系统功率控制算法

A novel distributed power control algorithm based on interference estimation is presented for wireless cellular system. A classical result of stochastic approximation is applied in this scheme. The power control algorithm is converted to seeking for the zero point problem of a certain function. In this distributed power algorithm, each user iteratively updates its power level by estimating the interference. It does not require any knowledge of the channel gains or state information of other users. Hence, the proposed algorithm is robust. It is proved that the algorithm converges to the optimal solution by stochastic approximation approach.     

一种点边带权最小生成树的近似算法

在给定的一个除边有代价外点也有两种代价的图中,要求出一棵点边代价和最小的生成树。这个优化问题具有实际应用背景。证明了该问题是NP难的,并且也给出该问题的近似算法和近似度分析。     

Analysis of the $(1+1)$-EA for Finding Approximate Solutions to Vertex Cover Problems

Vertex cover is one of the best known NP-hard combinatorial optimization problems. Experimental work has claimed that evolutionary algorithms (EAs) perform fairly well for the problem and can compete with problem-specific ones. A theoretical analysis that explains these empirical results is presented concerning the random local search algorithm and the (1+1)-EA. Since it is not expected that an algorithm can solve the vertex cover problem in polynomial time, a worst case approximation analysis is carried out for the two considered algorithms and comparisons with the best known problem-specific ones are presented. By studying instance classes of the problem, general results are derived. Although arbitrarily bad approximation ratios of the (1+1)-EA can be proved for a bipartite instance class, the same algorithm can quickly find the minimum cover of the graph when a restart strategy is used. Instance classes where multiple runs cannot considerably improve the performance of the (1+1)-EA are considered and the characteristics of the graphs that make the optimization task hard for the algorithm are investigated and highlighted. An instance class is designed to prove that the (1+1)-EA cannot guarantee better solutions than the state-of-the-art algorithm for vertex cover if worst cases are considered. In particular, a lower bound for the worst case approximation ratio, slightly less than two, is proved. Nevertheless, there are subclasses of the vertex cover problem for which the (1+1)-EA is efficient. It is proved that if the vertex degree is at most two, then the algorithm can solve the problem in polynomial time.     

一种改进的求解TSP问题的近似算法

旅行商问题(TSP)是典型的具有NPC复杂性的组合优化问题。在现有求解TSP问题的2-近似算法closest-point算法基础上,通过对插入点的插入位置进行改进,提出了一种有效的近似算法最近点前后插入法(CPBOA),并采用TSPLIB中的一些典型实例对该算法进行了测试,同时与典型的常数近似比算法MST-PRIM算法和closest-point算法进行了比较。实验结果表明,该算法在求解质量上与closest-point和MST-PRIM算法相比都有很大的改进,而且速度也很快。     

基于原始对偶方法求解网络流量监测集算法

考虑网络节点的流守恒特性,网络流量的有效监测问题可抽象为求给定图G(V,E)的最小弱顶点覆盖集的问题和基于流划分的最小弱顶点覆盖集的问题,这是NP难的问题.首先分析了弱顶点覆盖集的约束关系,并给出了问题的整数规划形式.然后利用原始对偶方法构造了求解最小弱顶点覆盖集的近似算法,并分析了算法的比界为2.进一步分析了求解基于最大流划分的最小弱顶点覆盖集的近似算法.     

实例序列条数为常数9的翻转距离星树问题

讨论翻转距离星树问题，证明实例中有向符号序列个数为9时，翻转距离星树问题是NP-难解问题，并给出了一个该问题的多项式时间近似算法．     

无线通讯系统功率控制算法及收敛性

利用随机逼近方法研究随机功率控制问题,将功率控制问题转化为寻求一个不确定函数零点的一个随机逼近问题.在承认随机噪声时,证明了所提出的算法在均方差意义下收敛到最优解.     

Approximation problems with the divergence criterion for Gaussian variables and Gaussian processes

System identification for stationary Gaussian processes includes an approximation problem. Currently, the subspace algorithm for this problem enjoys much attention. This algorithm is based on a transformation of a finite time series to canonical variable form followed by a truncation. There is no proof that this algorithm is the optimal solution to an approximation problem with a specific criterion. In this paper it is shown that the optimal solution to an approximation problem for Gaussian random variables with the divergence criterion is identical to the main step of the subspace algorithm. An approximation problem for stationary Gaussian processes with the divergence criterion is formulated.