Solving 0-1 knapsack problem by greedy degree and expectation efficiency

It is well known that 0-1 knapsack problem (KP01) plays an important role in both computing theory and real life application. Due to its NP-hardness, lots of impressive research work has been performed on many variants of the problem. Inspired by region partition of items, an effective hybrid algorithm based on greedy degree and expectation efficiency (GDEE) is presented in this paper. In the proposed algorithm, initially determinate items region, candidate items region and unknown items region are generated to direct the selection of items. A greedy degree model inspired by greedy strategy is devised to select some items as initially determinate region. Dynamic expectation efficiency strategy is designed and used to select some other items as candidate region, and the remaining items are regarded as unknown region. To obtain the final items to which the best profit corresponds, static expectation efficiency strategy is proposed whilst the parallel computing method is adopted to update the objective function value. Extensive numerical investigations based on a large number of instances are conducted. The proposed GDEE algorithm is evaluated against chemical reaction optimization algorithm and modified discrete shuffled frog leaping algorithm. The comparative results show that GDEE is much more effective in solving KP01 than other algorithms and that it is a promising tool for solving combinatorial optimization problems such as resource allocation and production scheduling.     

A boundary-element method for elastostatics in a plane region bounded by a smooth curve

The traditional boundary-element method for elastostatics in a plane region bounded by a smooth curve is modified. A circular element is used for which an analytical scheme for the traction problem is derived. It is shown that the construction of the elements of the coefficient matrix reduces to computing a simple integral which has a closed form solution. This leads to higher accuracy of the final results and considerable saving of computational efforts. The procedure is illustrated by some examples and the accuracy of the method as well as its efficiency are compared with those obtained from commonly used numerical techniques.     

Local motion deblurring using an effective image prior based on both the first- and second-order gradients

Local motion deblurring is a highly challenging problem as both the blurred region and the blur kernel are unknown. Most existing methods for local deblurring require a specialized hardware, an alpha matte, or user annotation of the blurred region. In this paper, an automatic method is proposed for local motion deblurring in which a segmentation step is performed to extract the blurred region. Then, for blind deblurring, i.e., simultaneously estimating both the blur kernel and the latent image, an optimization problem in the form of maximum-a-posteriori (MAP) is introduced. An effective image prior is used in the MAP based on both the first- and second-order gradients of the image. This prior assists to well reconstruct salient edges, providing reliable edge information for kernel estimation, in the intermediate latent image. We examined the proposed method for both global and local deblurring. The efficiency of the proposed method for global deblurring is demonstrated by performing several quantitative and qualitative comparisons with the state-of-the-art methods, on both a benchmark image dataset and real-world motion blurred images. In addition, in order to demonstrate the efficiency in local motion deblurring, the proposed method is examined to deblur some real-world locally linear motion blurred images. The qualitative results show the efficiency of the proposed method for local deblurring at various blur levels.     

一种基于变异"生产者--消费者"模型提高广播效率的方法

提出了一种解决变异的“生产者—消费者”问题的方法，并建立适当的模型，将它应用于网络中的数据广播，以获得较好的性能。该方法的提出是基于解决某公司打印计价电子科SM-X系列软件传输速度慢、效率低下而提出的；旨在提高类似星型拓扑结构网络中的数据传输效率。实践表明该方法使数据的广播效率得到了较大的提高，且已投入实际应用。     

一种基于跳表的DDM相交区域快速查询算法

HLA是为提高仿真系统的互操作性和可重用性而提出的新型分布仿真标准。HLA中数据分发管理服务的目的是通过邦员对数据公布和订购区域的表达来过滤一个邦员所接收到的数据,同时减少对网络带宽的消耗。DDM的核心是多维矩形区域动态相交查找的问题,其算法性能的好坏对DDM的效率是至关重要的。现有的一些动态区域查找算法还不能同时满足高效、精确且易于实现等要求,为此设计出一种基于跳表数据结构的用于快速相交区域查找的区问跳表,同时分析了区间跳表的构造原则以及基本操作的流程,并在此基础上提出了基于区间跳表的相交区域查找算法。该算法的匹配精度高,时间复杂度低,且具有编程实现简单的特点。     

一种启发式知识约简算法

属性约简是Rough集理论中的核心问题之一,找出所有的约简或最小约简是一个NP难题.本文证明了正区域和边界域的一些性质,指出在考虑正区域作为启发信息的同时,还应该考虑在不一致决策表中边界域对约简的影响,综合这两种信息,提出了不一致决策表约简的启发信息.并在此基础上,设计了不一致决策表的启发式约简算法.实验证明,在多数情况下,该算法能够得到决策表的最小或次优约简.     

自然场景图像中的中文文本提取

针对自然场景中中文文本的提取效率不足的问题,提出了一种基于ISODATA聚类和支持向量机(SVM)结合的自然场景中文文本提取算法。根据文本颜色和笔画的特征通过ISODATA聚类算法和局部分割的方法,分割出类文本区域;利用有效的几何特征,通过连通域分析去除部分非文本域;利用中心聚合方法使结构分离的中文文本合并后,将文本连接成行,提出行级特征用SVM分类出正确文本行及相应文本。实验结果表明,该算法对中文文本具有很好的提取效果和综合性能。     

决策域分布保持的启发式属性约简方法

在决策粗糙集中,由于引入了概率阈值,属性增加或减少时,正域或者非负域有可能变大、变小或者不变,即属性的增减与决策域（正域或非负域）之间不再具有单调性.分析结果表明,现有的基于整个决策域的属性约简定义可能会改变决策域.为使决策域保持不变,引入了正域分布保持约简与非负域分布保持约简的概念.此外,决策域的非单调性使得属性约简算法必须检查一个属性集合的所有子集.为了简化算法设计,提出了正域和非负域分布条件信息量的定义,并证明其满足单调性,从而为设计决策域分布保持约简的启发式计算方法提供了理论基础.为了进一步获得最小约简,提出一种基于遗传算法的决策域分布保持启发式约简算法,并在两种单调的决策域分布条件信息量基础上构造了新算子,即修正算子,确保遗传算法找到的是约简而不是约简的超集.对比实验从分类正确率与误分类代价两个方面都反映了决策域分布保持约简定义的合理性,并且,所提出的遗传算法在大多数情况下都找到了最小约简.     

基于非运动区域划分的运动估计算法

针对利用角点进行运动估计时,存在一定数量的运动区域角点,导致估计速度慢、精度低的问题,提出了一种基于非运动区域划分的运动估计算法。算法采用栅格法划分参考帧图像上的非运动区域与运动区域;对参考帧图像上提取的角点进行筛选,利用非运动区域的角点与当前帧图像上角点进行匹配;根据距离不变准则去除误匹配后,估算运动矢量。实验结果表明,该算法有效地提高了运行效率和估计精度。     

基于分层区域的自适应图像配准算法

针对SIFT（尺度不变特征变换）算法提取的特征点不纯、易受噪声等因素干扰的问题，提出在SIFT算法提取特征点之前对图像进行预处理，排除部分外界干扰。针对SIFT算法中128维的高维度特征描述符导致匹配速度降低，提出一种基于分层区域的方法降低描述符维度，缩短算法运行时间。针对SIFT算法匹配过程中选取固定阈值不具有广泛适用性的问题，提出一种自适应阈值的方法，解决设置固定阈值不能适用所有图像的问题，提高匹配准确率。实验结果证明，改进的算法能提高匹配准确率和匹配效率，增强算法的鲁棒性和可靠性，并且适用性广泛。     

基于专家系统法的异形件最小包络矩形求解

异形件布局问题广泛存在于社会各领域.目前,直接处理异形件布局问题的算法设计难度和计算量较大,而矩形件布局已有一些成熟算法.因此,将异形件转化为矩形件后处理布局能简化问题,并保证良好布局效果.本文基于专家系统法处理异形件,使其转换为易解决布局的包络矩形.     

文本检索方法驱动的海量图像数据库目标匹配研究

针对当前基于文本检索方法的图像目标对象匹配技术无法适应海量图像数据库检索的问题,本文提出一种有效可行的海量图像数据库的检索方法,并给出了该系统的构建框架。用户通过在图像中选择一块区域作为检索的目标对象提交给系统,它将从图像数据库中检索出包含有相同或相似目标对象的图像,将其排序后返回给用户。实验表明,本文提出的方法具有检索准确率高、响应时间短等特点,是一种有效的海量图像数据库检索方法。     

搜索空间划分移动策略的研究与实现

针对进化算法收敛效率和搜索能力不能有效兼顾的缺点，提出一种搜索机制与进化机制相分离的方法——搜索空间划分移动策略，并介绍其相关理论。该策略在搜索区域划分理论基础上，加入区域移动机制，使各极值能在不同环境下相互竞争，提高其搜索能力。改进的处理机制无须考虑搜索问题，能让算法迅速收敛。记录器能有效地完成各小区域间的通信，并根据要求控制区域移动。实验结果表明该策略具有较好的准确性和效率。     

基于多学科设计优化的路网交通分布式协同控制

城市路网交通控制直接影响着交通运行效率,对其优化研究已成为缓解城市交通拥堵问题的热点之一.鉴于此,针对高峰交通路网将其分为过饱和区域与过饱和关联区域,在采用灰色关联分析-谱聚类方法对关联区域划分的基础上,构建路网交通分布式协同控制模型,进一步提出基于多学科设计优化的过饱和区域及其关联区域协同优化求解方法.通过搭建实例路网模型分析算法优化效果,结果表明所提出方法能够明显改善路网交通运行效率,有助于缓解城市通勤高峰时段的交通拥堵和扩散问题.     

Efficiency determination of induction motors using multi-objective evolutionary algorithms

This paper introduces a method based on multi-objective evolutionary algorithms for the determination of in-service induction motor efficiency. In general, the efficiency is determined by accumulating multiple objectives into one objective by a linear combination and optimizing the resulting single-objective problem. The approach has some drawbacks such that exact information about solution alternatives will not be readily visible. In this paper the multi-objective evolutionary optimization algorithms, the Non-dominated Sorting Genetic Algorithm-II (NSGA-II) and Strength Pareto Evolutionary Algorithm-2 (SPEA2), are successfully applied to the efficiency determination problem in induction motor. The performances of algorithms are compared on the basis of the obtained results.     

利用区域变形和背景更新实现运动对象跟踪

从时域统计的角度出发,提出了一种结合自适应混合背景更新模型的区域变形跟踪算法．该算法以模型更新得到的前景／背景二值分割掩膜作为区域特征,将跟踪问题抽象为一个水平集(Level Set)偏微分方程的数值求解问题,并分析了算法的自适应性．为了进一步提高算法的实现效率,引入了窄带跟踪方案．实验表明,该算法可以对视频序列中的指定运动对象进行快速精确的跟踪。     

光流法在机车安全行驶中的应用

在基于路况视频的机车安全行驶中,依据轨道与信号灯的相对位置先验知识可缩小信号灯检测范围,提高信号灯检测的效率和可靠性,但在某些复杂光照条件下(尤其是夜间)因检测不到轨道而无法提供信号灯区域信息。针对此问题,提出一种基于光流的信号灯区域预测方法,首先在感兴趣区域中使用KLT算子提取强角点,并采用基于金字塔的Lucas-Kanade光流法计算强角点光流;然后根据全局光流信息判断机车转向状态;最后结合转向状态与先验知识估计出信号灯区域。此外,还提出了利用转向状态进行轨道跟踪检错的方法,该方法可及时发现轨道跟踪错误并唤醒系统进行轨道重定位。实验表明,该方法能有效预测信号灯区域,使信号灯检测实时性更高,抗干扰能力更强。     

Joint base station activation,user admission control and beamforming in downlink green networks

Consider a multicell downlink network, where the base stations (BSs) in different cells cooperate in the precoder level, while those in the same cell are coordinated for joint processing (JP). To achieve green communication, we optimize the network power consumption under some quality-of-service (QoS) constraints. Different from the conventional approaches based on BS activation and beamforming, we further integrate user admission control into network management, and thus minimize the power consumption by jointly optimizing the active BSs, the admissible users and the transmit beamformers. This strategy has two advantages. First, it ensures that the network still works even when some users cannot achieve the QoS requirements. Second, it helps select a subset of users whose QoS requirements can be satisfied with relatively low power cost, thereby improving the power efficiency. However, this problem is challenging due to the mixed-integer programming. To pursue some efficient approximate solution, we first reformulate it as a convex sparse optimization problem and then develop a distributed algorithm to iteratively solve the problem, utilizing the alternating direction method of multipliers (ADMM). The proposed algorithm has very low complexity since each step can be computed in closed form. Its efficacy and efficiency are demonstrated by numerical simulations.     

Solution algorithms for the makespan minimization problem with the general learning model

Most of the papers devoted to scheduling problems with the learning effect concern the Wright’s learning curve. On the other hand, the study about learning has pointed out that the learning curve in practice is very often an S-shaped function, which has not been considered in scheduling. Thus, in this paper, a single processor makespan minimization problem with an S-shaped learning model is investigated. We prove that this problem is strongly NP-hard even if the experience provided by each job is equal to its normal processing time. Therefore, to solve this problem, we prove some eliminating properties that are used to construct a branch and bound algorithm and some fast heuristic methods. Since the proposed algorithms are dedicated for the general case, i.e., where job processing times are arbitrary non-increasing experience dependent functions, their efficiency is verified numerically for the S-shaped model.     

Termination-indicator technique as structured programming tool

The termination-indicator technique is presented, which can be used to solve the class of multi-exit loop problems. A multi-exit loop problem is a programming problem that has several terminating conditions for a loop: either a loop will run through a full cycle or be terminated prematurely when some condition is met. The class of multi-exit loop problems has generated a great deal of controversy on the goto statement in the literature from time to time. The paper illustrates the generality and efficiency of the termination-indicator technique by applying it to the class of multi-exit loop problems and thus puts the goto controversy to rest.