Application of the probability-based covering algorithm model in text classification

The probability-based covering algorithm(PBCA) is a new algorithm based on probability distribution. It decides, by voting, the class of the tested samples on the border of the coverage area, based on the probability of training samples. When using the original covering algorithm(CA), many tested samples that are located on the border of the coverage cannot be classified by the spherical neighborhood gained. The network structure of PBCA is a mixed structure composed of both a feed-forward network and a feedback network. By using this method of adding some heterogeneous samples and enlarging the coverage radius,it is possible to decrease the number of rejected samples and improve the rate of recognition accuracy. Relevant computer experiments indicate that the algorithm improves the study precision and achieves reasonably good results in text classification.

Binary Fruit Fly Swarm Algorithms for the Set Covering Problem

Currently,the industry is experiencing an exponential increase in dealing with binary-based combinatorial problems.In this sense,metaheuristics have been a common trend in the field in order to design approaches to solve them successfully.Thus,a well-known strategy consists in the use of algorithms based on discrete swarms transformed to perform in binary environments.Following the No Free Lunch theorem,we are interested in testing the performance of the Fruit Fly Algorithm,this is a bio-inspired metaheuristic for deducing global optimization in continuous spaces,based on the foraging behavior of the fruit fly,which usually has much better sensory perception of smell and vision than any other species.On the other hand,the Set Coverage Problem is a well-known NP-hard problem with many practical applications,including production line balancing,utility installation,and crew scheduling in railroad and mass transit companies.In this paper,we propose different binarization methods for the Fruit Fly Algorithm,using Sshaped and V-shaped transfer functions and various discretization methods to make the algorithm work in a binary search space.We are motivated with this approach,because in this way we can deliver to future researchers interested in this area,a way to be able to work with continuous metaheuristics in binary domains.This new approach was tested on benchmark instances of the Set Coverage Problem and the computational results show that the proposed algorithm is robust enough to produce good results with low computational cost.

Estimating wheat fractional vegetation cover using a density peak k-means algorithm based on hyperspectral image data

Fractional vegetation cover(FVC)is an important parameter to measure crop growth.In studies of crop growth monitoring,it is very important to extract FVC quickly and accurately.As the most widely used FVC extraction method,the photographic method has the advantages of simple operation and high extraction accuracy.However,when soil moisture and acquisition times vary,the extraction results are less accurate.To accommodate various conditions of FVC extraction,this study proposes a new FVC extraction method that extracts FVC from a normalized difference vegetation index(NDVI)greyscale image of wheat by using a density peak k-means(DPK-means)algorithm.In this study,Yangfumai 4(YF4)planted in pots and Yangmai 16(Y16)planted in the field were used as the research materials.With a hyperspectral imaging camera mounted on a tripod,ground hyperspectral images of winter wheat under different soil conditions(dry and wet)were collected at 1 m above the potted wheat canopy.Unmanned aerial vehicle(UAV)hyperspectral images of winter wheat at various stages were collected at 50 m above the field wheat canopy by a UAV equipped with a hyperspectral camera.The pixel dichotomy method and DPK-means algorithm were used to classify vegetation pixels and non-vegetation pixels in NDVI greyscale images of wheat,and the extraction effects of the two methods were compared and analysed.The results showed that extraction by pixel dichotomy was influenced by the acquisition conditions and its error distribution was relatively scattered,while the extraction effect of the DPK-means algorithm was less affected by the acquisition conditions and its error distribution was concentrated.The absolute values of error were 0.042 and 0.044,the root mean square errors(RMSE)were 0.028 and 0.030,and the fitting accuracy R2 of the FVC was 0.87 and 0.93,under dry and wet soil conditions and under various time conditions,respectively.This study found that the DPK-means algorithm was capable of achieving more accurate results than the pixel dichotomy method in various soil and time conditions and was an accurate and robust method for FVC extraction.

Parallel machine covering with limited number of preemptions

In this paper, we investigate the/-preemptive scheduling on parallel machines to maximize the minimum machine completion time, i.e., machine covering problem with limited number of preemptions. It is aimed to obtain the worst case ratio of the objective value of the optimal schedule with unlimited preemptions and that of the schedule allowed to be preempted at most i times. For the m identical machines case, we show the worst case ratio is 2m-i-1/m and we present a polynomial time algorithm which can guarantee the ratio for any 0 〈 i 〈2 m - 1. For the /-preemptive scheduling on two uniform machines case, we only need to consider the cases of i = 0 and i = 1. For both cases, we present two linear time algorithms and obtain the worst case ratios with respect to s, i.e., the ratio of the speeds of two machines.

New Hybrid Genetic Algorithm for Vertex Cover Problems

This paper presents a new hybrid genetic algorithm for the vertex cover problems in which scan-repair and local improvement techniques are used for local optimization. With the hybrid approach, genetic algorithms are used to perform global exploration in a population, while neighborhood search methods are used to perform local exploitation around the chromosomes. The experimental results indicate that hybrid genetic algorithms can obtain solutions of excellent quality to the problem instances with different sizes. The pure genetic algorithms are outperformed by the neighborhood search heuristics procedures combined with genetic algorithms.

A Heuristic Approach to Fast NOVCA （Near Optimal Vertex Cover Algorithm）

This paper describes an extremely fast polynomial time algorithm, the NOVCA （Near Optimal Vertex Cover Algorithm） that produces an optimal or near optimal vertex cover for any known undirected graph G （V, E）. NOVCA is based on the idea of（l） including the vertex having maximum degree in the vertex cover and （2） rendering the degree of a vertex to zero by including all its adjacent vertices. The three versions of algorithm, NOVCA-I, NOVCA-II, and NOVCA-random, have been developed. The results identifying bounds on the size of the minimum vertex cover as well as polynomial complexity of algorithm are given with experimental verification. Future research efforts will be directed at tuning the algorithm and providing proof for better approximation ratio with NOVCA compared to any available vertex cover algorithms.

Metaheuristic post-optimization of the NIST repository of covering arrays

Construction of Covering Arrays （CA） with minimum possible number of rows is challenging. Often the available CA have redundant combinatorial interaction that could be removed to reduce the number of rows. This paper addresses the problem of removing redundancy of CA using a metaheuristic post- optimization （MPO） approach. Our approach consists of three main components： a redundancy detector （RD）; a row reducer （RR）; and a missing-combinations reducer （MCR）. The MCR is a metaheuristic component implemented using a simulated annealing algorithm. MPO was instantiated with 21,964 CA taken from the National Institute of Standards and Technology （NIST） repository. It is a remarkable result that this instantiation of MPO has delivered 349 new upper bounds for these CA.

Set Cover和Hitting Set问题的研究进展

Set Cover和Hitting Set问题是两个重要的W[2]完全问题。Set Cover问题在大规模集成电路设备的测试和人员调度等领域有着广泛的应用,Hitting Set问题在生物计算等领域有着重要的应用。在引入参数计算和复杂性理论后,Set Cover和Hitting Set问题再次成为研究的热点。首先介绍Set Cover和Hitting Set的各种分类问题及其定义,并对各种分类问题的计算复杂性和相关算法的研究进展加以分析总结,给出(k,h)-Set Cover和(k,d)-Set Cover问题的复杂性证明。最后总结全文并提出进一步研究的方向。

Assessing impact of climate change on forest cover type shifts in Western Himalayan Eco-region

Climate is a critical factor affecting forest ecosystems and their capacity to produce goods and services. Effects of climate change on forests depend on ecosystem-specific factors including dimensions of climate （temperature, precipitation, drought, wind etc.）. Available infor- mation is not sufficient to support a quantitative assessment of the eco- logical, social and economic consequences. The present study assessed shifts in forest cover types of Western Himalayan Eco-region （700-4 500 m）. 100 randomly selected samples （75 for training and 25 for testing the model）, genetic algorithm of rule set parameters and climatic envelopes were used to assess the distribution of five prominent forest cover types （Temperate evergreen, Tropical semi-evergreen, Temperate conifer, Sub- tropical conifer, and Tropical moist deciduous forests）. Modelling was conducted for four different scenarios, current scenario, changed precipi- tation （8% increase）, changed temperature （1.07℃ increase）, and both changed temperature and precipitation. On increasing precipitation a downward shift in the temperate evergreen and tropical semi-evergreen was observed, while sub-tropical conifer and tropical moist-deciduous forests showed a slight upward shift and temperate conifer showed ＇no shift. On increasing temperatm＇e, an upward shift in all forest types was observed except sub-tropical conifer forests without significant changes. When both temperature and precipitation were changed, the actual dis- tribution was maintained and slight upward shift was observed in all the forest types except sub-tropical conifer. It is important to understand the likely impacts of the projected climate change on the forest ecosystems, so that better management and conservation strategies can be adopted for the biodiversity and forest dependent community. Knowledge of impact mechanisms also enables identification and mitigation of some of the conditions that increase vulnerability to climate change in the forest sector.

基于Cover级别的中文信息检索技术的研究

信息检索系统如果能较精确地定位于文章中用户关心的部分必将提高用户的检索效率。基于Cover级别的检索策略就是针对上述问题提出的。基于Cover级别的检索策略以用户查询的关键词集合作为输入,在被检索文档中找到包含关键词集合的最短文本片断集作为输出。文章采用了一种经过改进的基于Cover级别的检索策略,对系统返回的文本片断作了限制,并在检索过程中使用了贪心算法(Greedy Algorithm)的思想,最后将其应用到中文信息检索系统中。实验证明,采用改进的策略比原有的基于Cover级别的检索策略在返回有效结果个数和平均排序倒数(MRR)等指标上都有了提高。

Optimizing Polynomial-Time Solutions to a Network Weighted Vertex Cover Game

Weighted vertex cover(WVC)is one of the most important combinatorial optimization problems.In this paper,we provide a new game optimization to achieve efficiency and time of solutions for the WVC problem of weighted networks.We first model the WVC problem as a general game on weighted networks.Under the framework of a game,we newly define several cover states to describe the WVC problem.Moreover,we reveal the relationship among these cover states of the weighted network and the strict Nash equilibriums(SNEs)of the game.Then,we propose a game-based asynchronous algorithm(GAA),which can theoretically guarantee that all cover states of vertices converging in an SNE with polynomial time.Subsequently,we improve the GAA by adding 2-hop and 3-hop adjustment mechanisms,termed the improved game-based asynchronous algorithm(IGAA),in which we prove that it can obtain a better solution to the WVC problem than using a the GAA.Finally,numerical simulations demonstrate that the proposed IGAA can obtain a better approximate solution in promising computation time compared with the existing representative algorithms.

Investigation of Spatial and Temporal Distribution of Snow Cover by Using Satellite Imagery (Case Study: Sheshpirdam Basin)

About one third of the water needed for agriculture in the world is generated by melting snow. Snow cover, surface and ground water recharge are considered as sustainable and renewable resources. It is therefore necessary to identify and study these criteria. The aim of this study is to determine the spatial and temporal distribution of snow cover in the district of the Sheshpir basin in Fars province (in south of Iran). Ground-based observation of snow covers, especially in mountainous areas, is associated with many problems due to the insufficient accuracy of optical observation, as opposed to digital observation. Therefore, GIS and remote sensing technology can be partially effective in solving this problem. Images of Landsat 5TM and Landsat 7TM satellites were used to derive snow cover maps. The images in ENVI 4.8 software were classified by using the maximum likelihood algorithm. Other spatial analyses were performed in ARC-GIS 9.3 software. The maximum likelihood method was accuracy assessed by operation points of testing. The least and the average of overall accuracy of produced maps were found to be 91% and 98%, respectively. This demonstrates that the maximum likelihood method has high performance in the classification of images. Overall snow cover and the review of terrain through the years 2008-2009 and 2009-2010 showed that snow cover begins to accumulate in November and reaches its highest magnitude in February. Finally, no trace of snow can be observed on the surface of the basin in the month of May. By average, 34% of the basin is covered in snow from November through to May.

Vertex Cover Optimization Using a Novel Graph Decomposition Approach

The minimum vertex cover problem(MVCP)is a well-known combinatorial optimization problem of graph theory.The MVCP is an NP(nondeterministic polynomial)complete problem and it has an exponential growing complexity with respect to the size of a graph.No algorithm exits till date that can exactly solve the problem in a deterministic polynomial time scale.However,several algorithms are proposed that solve the problem approximately in a short polynomial time scale.Such algorithms are useful for large size graphs,for which exact solution of MVCP is impossible with current computational resources.The MVCP has a wide range of applications in the fields like bioinformatics,biochemistry,circuit design,electrical engineering,data aggregation,networking,internet traffic monitoring,pattern recognition,marketing and franchising etc.This work aims to solve the MVCP approximately by a novel graph decomposition approach.The decomposition of the graph yields a subgraph that contains edges shared by triangular edge structures.A subgraph is covered to yield a subgraph that forms one or more Hamiltonian cycles or paths.In order to reduce complexity of the algorithm a new strategy is also proposed.The reduction strategy can be used for any algorithm solving MVCP.Based on the graph decomposition and the reduction strategy,two algorithms are formulated to approximately solve the MVCP.These algorithms are tested using well known standard benchmark graphs.The key feature of the results is a good approximate error ratio and improvement in optimum vertex cover values for few graphs.

A Comparative Study of Image Classification Algorithms for Landscape Assessment of the Niger Delta Region

A critical problem associated with the southern part of Nigeria is the rapid alteration of the landscape as a result of logging, agricultural practices, human migration and expansion, oil exploration, exploitation and production activities. These processes have had both positive and negative effects on the economic and socio-political development of the country in general. The negative impacts have led not only to the degradation of the ecosystem but also posing hazards to human health and polluting surface and ground water resources. This has created the need for the development of a rapid, cost effective and efficient land use/land cover (LULC) classification technique to monitor the biophysical dynamics in the region. Due to the complex land cover patterns existing in the study area and the occasionally indistinguishable relationship between land cover and spectral signals, this paper introduces a combined use of unsupervised and supervised image classification for detecting land use/land cover (LULC) classes. With the continuous conflict over the impact of oil activities in the area, this work provides a procedure for detecting LULC change, which is an important factor to consider in the design of an environmental decision-making framework. Results from the use of this technique on Landsat TM and ETM+ of 1987 and 2002 are discussed. The results reveal the pros and cons of the two methods and the effects of their overall accuracy on post-classification change detection.

考虑供电枢纽传输成本的充电站选址定容模型

电动汽车及其配套设施的发展受制于早期形成的有限布局,不断增长的电动汽车市场规模和充电需求产生矛盾。充电站的建设运营方能够在巨大潜力的充电设施发展中获得巨大利好。通过以最大化充电站建设运营方的利润为优化目标,构建需求覆盖选址模型,权衡供电枢纽、充电站和充电桩的成本和满足充电需求的收入,利用遗传算法求解获得选址定容的决策。研究发现:一方面,充电站的覆盖半径对利润和决策结果影响较大且复杂,充电站投资建设前期需要对影响覆盖范围的诸多因素进行市场调研;另一方面,铺电单位成本对决策结果影响明显,相对高的铺电成本会抑制充电站选址数量和容量大小,从而降低利润。因此充电站投资建设方需要分别对两类成本做好数据调研,避免决策结果出现较大偏差。

基于IDBO-LSSVM的输电线路覆冰厚度预测模型

针对输电线路受多种气象因素影响导致覆冰厚度预测精度低的问题,提出基于改进蜣螂优化(improved dung beetle optimizer,IDBO)算法优化最小二乘支持向量机(least square support vector machine,LSSVM)的输电线路覆冰厚度预测模型。首先,使用皮尔逊相关系数(Pearson correlation coefficient,PCC)计算输电线路覆冰厚度与不同气象因素之间的相关性,选择具有高相关性的气象因素以确定输入变量;其次,通过引入Halton序列、Levy飞行策略和T分布扰动来改进蜣螂优化(dung beetle optimizer,DBO)算法;最后,使用IDBO算法寻优LSSVM参数:调节因子、核函数宽度,提高模型预测精度。以某地输电线路历史监测数据为样本,将IDBO-LSSVM的输电线路预测结果与其他7种预测模型进行比较,发现平均绝对误差分别降低了约27%、36%、25%、23%、24%、44%和39%。该研究证实了基于IDBO-LSSVM的输电线路覆冰厚度预测模型可以有效提高预测精度。

基于MODIS积雪覆盖度数据的青藏高原两套被动微波雪深产品降尺度对比研究

积雪深度(雪深)是流域水量平衡、融雪径流模拟等模型的重要输入参数,被动微波雪深遥感产品被广泛用于雪深监测。然而,由于山区积雪时空异质性强,这些空间分辨率较粗的雪深产品受到极大限制。本研究基于MODIS积雪覆盖度数据,根据经验融合规则以及积雪衰退曲线对“中国雪深长时间序列数据集”的两套雪深产品(由SMMR、SSMI和SSMI/S反演的称为Che_SSMI/S产品;由AMSR-2反演称为Che_AMSR2产品)进行空间降尺度,最终获得青藏高原500 m降尺度雪深数据(Che_SSMI/S_NSD和Che_AMSR2_NSD)。利用6景Landsat-8影像对两套降尺度雪深数据进行对比分析,结果发现两套降尺度数据与Landsat-8影像积雪空间分布吻合度均较高。与29个气象站点雪深数据相比,Che_AMSR2_NSD与实测雪深更为接近,相关系数(R)达到0.72,均方根误差(RMSE)为3.21 cm;而Che_SSMI/S_NSD精度较低(R=0.67,RMSE=4.44 cm),可能是由于采用不同传感器亮温数据的两套原始雪深产品精度不同所致。除此之外,实验表明被动微波雪深产品降尺度精度还受积雪深度、积雪期等因素的影响。当积雪深度小于10 cm且在积雪稳定期时,两套雪深产品降尺度精度均最高;当积雪深度大于30 cm且在积雪消融期时,两套雪深产品降尺度精度均最低。通过对比两套降尺度雪深产品,有助于全面地了解青藏高原雪深时空分布变化及其应用提供数据支持。

基于集覆盖理论的覆盖信息系统属性约简方法

针对覆盖信息系统属性约简问题,提出基于集覆盖理论的覆盖信息系统属性约简方法。首先,构造覆盖信息系统的相关矩阵,通过相关矩阵诱导出覆盖信息系统的集覆盖模型,并探讨了覆盖信息系统与其诱导的集覆盖模型之间的联系,发现集覆盖模型的一个极小覆盖恰是原覆盖信息系统的一个属性约简集,从而可以将求解覆盖信息系统的属性约简问题转化为求解对应集覆盖模型的极小集覆盖问题。其次,利用集覆盖启发式算法(set covering heuristic algorithm,SCHA)在解决集覆盖问题上具有更高的精度和更好的性能,给出了基于SCHA的覆盖信息系统属性约简的求解步骤及算法。最后,通过实例验证了所提方法的可行性和有效性。

最小连通顶点覆盖问题的降阶回溯算法

本文从最小连通顶点覆盖问题的求解算法出发,提出一种基于该问题本身的数学性质的降阶回溯算法来求解。通过基于问题的数学性质来设计精确算法,不仅能够克服使用启发式算法求解该问题在一般情形下都无法求得最优解的缺点,也改善了该问题使用传统精确算法时最坏时间复杂度高的缺点。本文首先研究该问题的数学性质,部分数学性质可成批确定某些顶点在或不在最小连通顶点覆盖集中,从而降低该问题的规模,提高精确算法的求解速度。其次,在数学性质的基础上,设计出上下界子算法、降阶子算法、回溯子算法来求解该问题的最优解。最后,时间复杂度分析以及无线网络设计的实例分析表明,该算法不仅能求得该问题的最优解,且相对一般精确算法,本文算法的时间复杂度更低。

基于多智能体强化学习的防空编队部署方法

针对防空编队智能部署方法无法同时兼顾区域掩护和目标掩护、人为制定复杂规则难以求解、算法执行效率较低的问题,提出一种基于独立多智能体近端策略优化(IN-MAPPO)的防空编队部署方法。设计独立的行动者-评论家网络,以适应火力单元的不同角色,通过集中式价值函数和奖励函数促进火力单元协同合作完成混合部署任务,提高编队的抗击能力和整体部署性能。实验结果表明:IN-MAPPO方法能够依据智能体的角色完成混合部署任务,提高远程火力单元的抗击能力,比其他MAPPO算法减少了13.7%的训练时间;与现有智能算法相比,火力单元覆盖面积提升了4.2%,有效掩护宽度提升了12.3%,算法的执行效率提高了95.9%。