基于蜂窝结构的传感器网络覆盖问题求解算法

在无线传感器网络中,求解能够完全覆盖目标区域的最小覆盖集是个NP难问题.在传感器节点数目较多时,目前只能通过近似算法求解.蜂窝结构是覆盖二维平面的最佳拓扑结构,但不能直接用于求解无线传感器网络的覆盖问题.提出了一种基于蜂窝结构的覆盖问题求解算法,在该算法迭代求解过程的每一阶段,选出一个节点加入到初始为空的节点集合中,并使得该节点集合的拓扑结构接近于蜂窝结构,直至该节点集合成为覆盖集.该算法在最坏情况下的时间复杂度为O(n3),这里n为传感器节点总数.实验结果表明该算法可在很短的时间内执行完,在所得覆盖集的大小方面要优于现有的覆盖问题求解算法.     

面向正常性的飞机排班优化算法

针对航班正常性问题,在飞机排班问题基础上,引入正常性约束,建立面向正常性的飞机排班模型,提出一种两阶段启发式算法进行求解.构建符合正常性要求的候选航班链集合,将排班问题转化为候选链对航班计划的集合覆盖问题.通过0-1整数规划求解集合覆盖问题,得到满足正常性约束的最小飞机数量排班方案.松弛正常性约束减小飞机使用数量,满足飞机数量约束.通过迭代搜索寻求正常性与飞机数量平衡的最优排班方案.实验结果表明,该方法可以有效提升航班计划的正常性期望.     

一种支持大规模数据逻辑函数优化的改进选拔算法

选拔算法是两级逻辑综合中求解最小化覆盖的经典方法之一,但在输出变量集合和质立方体集合规模较大的情况下,采用选拔法求最小化覆盖存在空间复杂度高、求解时间长等问题。为此,提出了求解多输出函数最小化覆盖的改进选拔算法。利用相交迭代和局部搜索的思想,分别对选拔法的极值运算和分支处理进行了改进。实验结果表明,在现有计算机资源条件下,该算法为大规模数据条件下逻辑函数的优化提供了一种有效的方法。     

容错节能无线传感器网络中可靠覆盖问题的解决方案

基于生成最小覆盖的k集合覆盖启发式算法,提出了分簇结构下解决簇内观测区域可靠覆盖问题的高效节能方案,即可靠覆盖方案.最小覆盖是一个可以完全覆盖观测区域的传感器节点最小集合,可靠覆盖方案使用的1-损毁最小覆盖拓扑结构是两个最小覆盖的迭加.通过1-损毁最小覆盖间的轮流工作延长网络可用时间,体现节能效果;通过增加一个冗余最小覆盖,屏蔽来自单个最小覆盖的节点失效,体现容错效果.在该方案中,介绍簇头节点和簇内成员的交互协议,并使用快速覆盖替换算法处理可能的节点失效.仿真实验显示,该方案能够高效地利用有限的能量,显著延长网络工作时间,同时将由节点失效而产生的漏测次数保持在较低值.     

基于观测数据聚类划分的扩展目标跟踪算法

针对高斯混合假设概率密度滤波扩展目标跟踪算法中的观测集合划分问题,本文分析了距离门限划分方法存在的问题,提出了一种利用聚类方法进行观测数据集合划分的方法。该方法利用极大似然方法获得目标数的估计值,以此作为聚类数利用K-means聚类对观测数据集合进行聚类划分,并利用椭球门限对观测数据进行处理以降低杂波观测对聚类划分的影响。实验结果表明,该方法能够获得正确的划分观测集合,计算复杂度较距离门限划分方法有较大降低,同时在多目标跟踪效果方面优于观测数据距离门限划分的假设概率密度滤波扩展目标跟踪算法。     

多传感器系统估计的稳健切比雪夫中心估计融合

针对多传感器线性回归模型的参数估计融合问题,在观测噪声是范数有界的情况下,提出了稳健切比雪夫中心估计融合方法。描述参数的可行集合,为线性系统的所有可行解。可行集合的切比雪夫中心是最坏情况下使得估计误差最小的点,可用它作为多传感器系统参数估计的稳健融合。该问题在复数域上的某些情况可以精确求解,但目前的研究在实数域上只能得到近似解,即松弛的切比雪夫中心。严格证明了在实平面上可行集合的切比雪夫中心可以通过有限个约束的凸优化问题求解,因此,切比雪夫中心可以通过高效优化算法得到。在高维情况下,通过将可行集合投影到各坐标平面,设计了近似的切比雪夫中心融合方法。数值实验结果表明:该方法优于松弛的切比雪夫中心融合。     

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

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

一种面向目标的有向传感器网络连通覆盖算法

针对传统的有向传感器网络目标覆盖算法只考虑网络覆盖率而不能保证网络连通性的问题,利用目标点部署圆内覆盖最多邻居目标点的候选节点集合和整数线性规划(ILP)模型设计了一种面向目标的连通覆盖算法(CTA)。该算法通过建立目标部署圆内覆盖最多邻居目标点的候选节点集合对随机部署的节点进行初步调度,在此基础上,通过ILP模型找出实现目标检测,并保证整个网络连通性的最少节点数和最佳位置的节点集合。仿真实验表明:CTA在保证目标覆盖率的前提下,不仅极大地降低了网络部署成本,而且保证了网络连通性。     

一个解决集合覆盖问题的二阶段遗传算法

针对集合覆盖问题,提出一个高效的可解决大规模数据的二阶段遗传算法.二阶段遗传算法可以分为数据约简阶段和启发式求解阶段,论文形式化地描述了数据约简阶段的相关定义、定理和算法,证明了该约简方法的有效性;并给出了启发式求解阶段中针对集合覆盖问题的遗传算法中选择、交叉、变异算子的设计方法.对Beasley提出的45个测试用例的测试结果验证了二阶段遗传算法的求解效率和求解质量高于其它遗传算法.     

基于仿射映射的变分集合卡尔曼反演

基于集合卡尔曼滤波的反演算法已经成为处理贝叶斯反问题中越来越受欢迎的一类方法.这类方法可以看成是求解反问题的无梯度优化方法.然而这类方法是基于集合卡尔曼滤波算法的,所以它们可能不适用于求解强非高斯性观测模型.为了解决这一问题,在本文中我们提出一种基于仿射映射的变分集合卡尔曼反演算法,即确定一个先验集合到后验集合的仿射映射.数值实验结果表明,在强非高斯性观测模型中,我们提出的反演算法比标准的集合卡尔曼反演方法表现出更好的性能.     

集合覆盖问题的启发函数算法

本文给出了求解NP困难问题的完备策略的概念,在此基础上提出了一个求解集合覆盖问题的启发函数算法SCHF(set-covering heuristic function),文中对该算法的合理性、时间复杂性以及解的精度进行了分析,本文的主要创新点是用已知的完备策略建立启发函数,并用该启发函数进行空间搜索求出优化解.该方法具有一定的普遍性,可以应用到其它的NP困难问题.它为求解NP困难问题的近似解提供了一种行之有效的方法.在规则学习中的应用结果表明,本文给出的SCHF算法是非常有效的.     

An improved genetic algorithm with conditional genetic operators and its application to set-covering problem

The genetic algorithm (GA) is a popular, biologically inspired optimization method. However, in the GA there is no rule of thumb to design the GA operators and select GA parameters. Instead, trial-and-error has to be applied. In this paper we present an improved genetic algorithm in which crossover and mutation are performed conditionally instead of probability. Because there are no crossover rate and mutation rate to be selected, the proposed improved GA can be more easily applied to a problem than the conventional genetic algorithms. The proposed improved genetic algorithm is applied to solve the set-covering problem. Experimental studies show that the improved GA produces better results over the conventional one and other methods.     

A stochastic set-covering location model for both ameliorating and deteriorating items

Most of the previous works on classical location models are based on the assumption that the value (or utility) of inventory remains constant over time. In this study, a special case of the stochastic set-covering location problem is studied for both ameliorating and deteriorating items. The objective of this study is to determine the minimum number of storage facilities among a discrete set of location sites so that the probability of each customer being covered is not less than a critical value. We have formulated this problem using the stochastic set-covering problem, which can be solved via the 0–1 programming method. We have also developed a computer program for this problem and the results of a set of sample problems for fish culture storage and supply center will show the impact of the ameliorating and deteriorating rates on the location problem. For further study, a graphical user-interface with visualization for input and output needs is to be developed.     

Geometric covering

In this work, we present a single unified framework that can solve many geometric covering queries such as inspection and mold design. The suggested framework reduces a geometric covering query to the classic computer science set-covering problem. The solution is of exponential complexity due to the inherent complexity of the classic set-covering problem. However, in practice, we are able to efficiently offer almost optimal solutions for small-scale problems of several covering entities. Finally, using the portrayed framework, we demonstrate some results on the mold-design problem in manufacturing.     

Scaling Up Inductive Logic Programming: An Evolutionary Wrapper Approach

Inductive logic programming (ILP) algorithms are classification algorithms that construct classifiers represented as logic programs. ILP algorithms have a number of attractive features, notably the ability to make use of declarative background (user-supplied) knowledge. However, ILP algorithms deal poorly with large data sets (>10⁴ examples) and their widespread use of the greedy set-covering algorithm renders them susceptible to local maxima in the space of logic programs.This paper presents a novel approach to address these problems based on combining the local search properties of an inductive logic programming algorithm with the global search properties of an evolutionary algorithm. The proposed algorithm may be viewed as an evolutionary wrapper around a population of ILP algorithms.The evolutionary wrapper approach is evaluated on two domains. The chess-endgame (KRK) problem is an artificial domain that is a widely used benchmark in inductive logic programming, and Part-of-Speech Tagging is a real-world problem from the field of Natural Language Processing. In the latter domain, data originates from excerpts of the Wall Street Journal. Results indicate that significant improvements in predictive accuracy can be achieved over a conventional ILP approach when data is plentiful and noisy.     

基于模糊扩张矩阵的启发式算法

扩张矩阵是一种规则归纳的方法。在模糊环境下,模糊扩张矩阵算法根据路径的最小模糊信息熵标准,从示例中归纳产生一组模糊规则。本文引入评价矩阵的概念,并使用近似集合覆盖算法的思想,对上述模糊规则归纳方法做了改进。实验结果表明,与原算法相比,改进后的版本增添了许多优点,比如,得到的规则较少,运算速度较快等。     

Efficient location area planning for cellular networks with hierarchical location databases

Location area planning (LAP) is an important issue in the design of high-performance PCS networks. It could have a serious impact on the total mobility management cost of mobile terminals. Most of the previous works either explored the LAP problem as a 0–1 linear programming problem or used adopted techniques, such as simulated annealing, taboo search, and genetic algorithms [IEEE Trans. Vehicular Technol. 49 (2000) 1678; Proceedings of 1999 Vehicular Technology Conference, vol. 4, 1999, pp. 2119–2123; IEEE Vehicular Technol. Conf. 3 (1996) 1835; Proceedings of IEEE INFOCOM'01, Anchorage, Alaska, April 2001; IEEE Trans. Vehicular Technol. 47 (1998) 987], to derive a solution to minimize the location update cost. In this paper, we model and resolve the LAP problem as a set-covering problem. The main advantage of this approach is that it can adapt to the changing mobility patterns of the mobile terminals. We propose the set-covering-based location area planning (SCBLP) algorithm to minimize the total number of location updates, in which the cost-benefit functions are defined based on the coupling and cohesive functions among neighboring cells. We then apply SCBLP to the location database system with a hierarchical structure to further improve the overall system performance in searching and updating the location databases. Extensive simulation experiments have been conducted, and the experimental results show that our proposed algorithms can significantly reduce the location management costs, compared to the greedy algorithm and the random algorithm.     

Heuristically aided set-covering algorithms

It has been observed that mathematical programming algorithms will often require considerably less time for solution when started at a near-optimal solution vector. This paper investigates the improvements in computational efficiency when two set-covering algorithms are initialized via solutions provided by a simple heuristic program. It is observed that reduced computational time (where this computation time includes that used in obtaining the initial heuristic solution) and computation time variance and increased problem size capability are to be expected for the combination of set-covering algorithms and heuristic program investigated.