The minimum connected dominating set (MCDS) problem is a very significant NP-hard combinatorial optimization problem, and it has been used in many fields such as wireless sensor networks and ad hoc networks. In this paper, we propose a novel multi-start local search algorithm (MSLS) to tackle the minimum connected dominating set problem. Firstly, we present the fitness mechanism to design the vertex score mechanism so that our algorithm can jump out of the local optimum. Secondly, we use the configuration checking (CC) mechanism to avoid the cycling problem. Then, we propose the vertex flipping mechanism to change the vertex state by combing the CC mechanism with the vertex score mechanism. Finally, we propose a multi-start local search framework based on these mechanisms. We compare the algorithm MSLS with other compared algorithms on extensive instances. The results of experiment show that MSLS is superior to other algorithms in solution quality and time efficiency on most instances.
20 April 2016 in International Transactions in Operational Research
Distant supervision is an efficient way to generate large-scale training data for relation extraction without human efforts. However, the accompanying challenges have been plaguing the advance of the extractor: (1) the automatically annotated labels for training data contain much noisy data; (2) the annotations, based on bag-level (cluster of sentences) instead of sentence-level (single sentence), are too coarse to train an accurate extractor; (3) hetergeneous sentences are hard for a denoising model to capture the underlying commonness among valid relational expressions. To address these issues, we bulid a novel sentence representation and craft reinforcement learning to select the expressive sentence for each relation mentioned in a bag. More specifically, we introduce entity-free sentence pattern incorporated with attentive type information. Furthermore, multiple interactions between entity-specific and entity-free representation are proposed to generate complementary sentence features (for challenge 3). Then we design a fine-grained reward function, and model the sentence selection process as an auction where different relations for a bag need to compete together to achieve the possession of a specific sentence based on its expressiveness(for challenge 1 and 2). The experimental results on two public datasets demonstrate the superiority of our model for distantly supervised relation extraction.
With the trend of the increasing ageing population, more elderly people often encounter some problems in their daily lives. To enable these people to have more carefree lives, smart homes are designed to assist elderly people by recognizing their daily activities. Although different models and algorithms that use temporal and spatial features for activity recognition have been proposed, the rigid representations of these features damage the accuracy of activity recognition. In this paper, a two-stage approach is proposed to recognize the activities of a single resident. Firstly, in terms of temporal features, the approximate duration, start and end time are extracted from the activity records. Secondly, a set of activity records is clustered according to the records’ temporal features. Then, the classifiers are used to recognize the daily activities in each cluster according to the spatial features. Finally, two experiments are done to validate the recognition of daily activities in order to compare the proposed approach with a one-dimensional model. The results demonstrate that the proposed approach favorably outperforms the one-dimensional model. Two public datasets are used to evaluate the proposed approach. The experiment results show that the proposed approach achieves average accuracies of 80% and 89%, respectively.
1 August 2016 in Engineering Applications of Artificial Intelligence
In this paper, a novel method is proposed for judging whether a component set is a consistency-based diagnostic set, using SAT solvers. Firstly, the model of the system to be diagnosed and all the observations are described with conjunctive normal forms (CNF). Then, all the related clauses in the CNF files to the components other than the considered ones are extracted, to be used for satisfiability checking by SAT solvers. Next, all the minimal consistency-based diagnostic sets are derived by the CSSE-tree or by other similar algorithms. We have implemented four related algorithms, by calling the gold medal SAT solver in SAT07 competition – RSAT. Experimental results show that all the minimal consistency-based diagnostic sets can be quickly computed. Especially our CSSE-tree has the best efficiency for the single- or double-fault diagnosis.