Abstract:Recombination operators used in most current multiobjective evolutionary algorithms (MOEAs) were originally designed for single objective optimization. This paper demonstrates that some widely used recombination operators may not work well for multiobjective optimization problems (MOPs), and proposes a multiobjective evolutionary algorithm based on decomposition and mixture Gaussian models (MOEA/D-MG). In the algorithm, a reproduction operator based on mixture Gaussian models is used to model the population distribution and sample new trails solutions, and a greedy replacement scheme is then applied to update the population by the new trial solutions. MOEA/D-MG is applied to a variety of test instances with complicated Pareto fronts. The extensive experimental results indicate that MOEA/D-MG is promising for dealing with these continuous MOPs.

Abstract:With the development of next-generation sequencing technology, a large number of 16S rRNA gene reads have been collected. A key and important issue is to develop novel methods for mining the hidden information among those data. Sequence clustering aims to find the natural groups of large-scale data which can help us to understand the species, functional and structural diversity of microbial communities. This present work proposes a heuristic clustering method based on Neighbor-seeds, named NbHClust, for 454 sequencing data. The results show that this method can reduce extent of overestimation of operational taxonomy unit (OTU) and have a good robust and high clustering accuracy.

Abstract:In a multi-touch interactive system, distinguishing between user's left and right hands is of great significance for recognizing multi-finger gestures and further fully exploring the potential of bimanual interaction. However, the function of left-right hand distinction is beyond the capability of most multi-touch systems. In this paper, a robust solution to the left-right hand distinction based on the anatomical structure characteristic of hand is presented. Firstly, guided by the basic principles of gesture designing, the interactive tabletop hand-arm triangle model is proposed based on the anatomical structure characteristic of hand. Secondly, multi-touch interactive tabletop same hand contact points clustering method and left-right hand recognizing method are given based on the triangle model. Then, the methods are integrated into MTDriver to detect and send contact points's left-right information to the multi-touch applications and new bimanual interactive technologies are demonstrated. Finally, evaluation shows that the solution can achieve high recognition accuracy and good time performance that could support fluency bimanual interaction on interactive tabletop.

Abstract:Drawing on the benchmarking theory in the business management, a new search method, benchmarking-based optimization algorithm (BOA), is proposed in this paper. BOA provides a competitive learning mechanism based on dynamic niche according to the core values of benchmarking. Through imitation and learning, all the individuals within a population are able to approach to the high yielding regions in the solution space and seek out the optimal solutions quickly. Further, the formidable problem of maintaining the diversity of population is effectively resolved through the self-organizing learning process of the niche system and its friendly interaction with the environment. In this paper, the main differences between BLA and the existing intelligent optimization methods, sush as genetic algorithm (GA), are analyzed. The comparative experiments show that BLA is robust and able to perform friendly interactive learning with the environment, and its search speed and optimization ability is far superior to the existing intelligent optimization methods.

Abstract:This paper introduces the notion of the Borel probabilistic rough truth degree of a formula in a special kind of rough logic, by employing Borel probability measures on the valuation set endowed with the usual product topology. It facilitates a special form of rough logic with integration to quantitative logic. The axiomatic definition of probabilistic rough truth degree is given and its representation theorem is also presented. The proposed notion of Borel probabilistic rough truth degree can be regarded as the quantitative analysis of rough logic, as well as the advancing research of the existing notion of truth degree from rough set perspective. Based upon the fundamental notion of rough truth degree, some graded versions of the existing notions, including the roughness degree, accuracy degree and the rough similarity degree, are also presented. Subsequently, three different kinds of approximate reasoning models are established. The obtained results achieve a combination of rough logic and quantitative logic and provide a possible framework for rough truth based approximate reasoning.

Abstract:In line with the proposing process of the self-adaptive discrete differential evolution (SaDDE) algorithm, this research focuses on the strategy selection problem. The strategy pool plays a significant role in the SaDDE algorithm, and there are three issues need to be addressed in designing the strategy pool: (1) how to determine if a candidate solution generating strategy (CSGS) is effective; (2) which CSGSes to choose to constitute the strategy pool; and (3) how to find a suitable size forthe strategy pool. In order to solve these problems, a relative permutation order based scale method (RPOSM) and a RPOSM based analytic hierarchy process (RPOSM-AHP) are proposed in this paper. The experiments are mainly conducted on six test instances (T_INSes) which come from an electronic countermeasure (ECM) simulation experimental platform. 144 different CSGSes are designed, and 144×6 independent experiments are performed to obtain the sort sequences of the CSGSes. The RPOSM and the RPOSM-AHP are adopted to obtain the priority vector of the 144 CSGSes. Sequentially, 16 algorithms with different sizes of strategy pools are constructed and their performance is tested on the six T_INSes. Further, the RPOSM and RPOSM-AHP are employed again to find the suitable pool size for the SaDDE algorithm. Computational comparisons demonstrate that, within fixed number of fitness evaluations (NFE), the SaDDE algorithm can generate better results than its competitors.

Abstract:Semi-Supervised clustering aims to partition the data points into different clusters based on the user-specified must-link and cannot-link constraints. The current semi-supervised clustering algorithms either modify the clustering methods or combine the metric learning approaches to adapt the clustering result as consistent with the pairwise constraints as possible. However, few of them try to explicitly compute the degrees of influence that each pairwise constraint exerts on the unconstrained data points. This paper proposes a semi-supervised clustering algorithm via a two-level random walk, which is composed of a lower-level random walk on vertices and a higher-level random walk on components. The lower-level random walk is responsible for computing the influence range of every vertex constrained by a pairwise constraint. This information is encapsulated in an intermediate structure called "component". The higher-level random walk further propagates the pairwise constraints on the components with adaptive strength, followed by the integration of all the constraint influence into a cluster indicating matrix. The experiments on UCI database and large real-world data sets demonstrate that, compared with other semi-supervised clustering algorithms, the proposed method not only produces more satisfactory clustering results but also exhibits good efficiency.

Abstract:As an introduction to the necessary modality □, the truth values of formulas of the predicate modal logic in a possible world may rely on its alternative worlds. So there is a problem of the transworld identity of individuals in the predicate modal logic. According to this problem, Lewis proposed the counterpart theory and used the counterpart relation to represent the transworld identity of individuals in the counterpart theory. When an object has more than one counterpart, the transworld identity cannot have a one-to-one correspondence with the counterpart relation. By limiting the scope of the universal quantifier ∀ in the predicate modal logic, this paper gives a formula- layered predicate modal logic, which is a sublogic of the predicate modal logic, and which language is the same as that of the predicate modal logic. But the definition of its formulas is decomposed into layers such that ∀ may occur in the scope of □, and □ cannot occur in the scope of ∀. Since any expression in the form of ∀x□φ(x) is not a formula of this logic, the truth value of any formula which begins with a quantifier in a possible world w only relies on w, and this logic avoids the problem of the transworld identity of individuals. This paper gives the language, the syntax and the semantics of this logic, and proves that this logic is sound and complete.

Abstract:Due to its concise formation, fast convergence, and flexible parameters, particle swarm optimization (PSO) with the ability to gain multiple solutions at a run and to approximate the Pareto front of those non-convex or discontinuous multiobjective optimization problems (MOPs) is considered to be one of the most promising techniques for MOPs. However, several challenges, such as maintaining the archive, selecting the global and personal best solutions, and balancing the exploration and exploitation, occur when extending PSO from single-objective optimization problems to MOPs. In this paper, the distribution entropy and its difference of an approximate Pareto front in a new objective space, named parallel cell coordinate system (PCCS), are proposed to assess the diversity and evolutionary status of the population. The feedback information from evolutionary environment is served in the evolutionary strategies to balance the convergence and diversity of an approximate Pareto front. Meanwhile, the new concepts, such as cell dominance and individual density based on cell distance in the PCCS, are introduced to evaluate the individual environmental fitness which is the metric using in updating the archive and selecting the global best solutions. The experimental results illustrate that the proposed algorithm in this paper significantly outperforms the other eight peer competitors in terms of IGD on 12 test instances chosen from the ZDT and DTLZ test suites.

Abstract:This paper studies the online and offline algorithms for the ski-rental problem with multiple discount options (multiple-discount ski-rental problem), which is a natural extension of the famous ski-rental problem and has many applications in the real world. In this problem, besides the rental and buy options, there are some other options to rent equipments for a duration with some discount. The longer the duration, the more the discount. A special case of the ski-rental problem with multiple discount options, where for any two options the cost of one is an integral multiple of that of the other one, is called the regular cost subproblem. This study proves the NP-hardness of the off-line version of the ski-rental problem with multiple discount options, and gives a linear algorithm for the regular cost subproblem. Based on the analysis of the off-line problems, it proposes a 2-competitive online algorithm for the regular cost subproblem and proves the optimality of the competitive ratio. Based on the online algorithm of the regular cost subproblem, It presents a 4-competitive online algorithm for the ski-rental problem with multiple discount options that is also optimal. Some experimental results are also given to show the effectiveness of the algorithms when running on some real data and random data.

Abstract:Energy-Aware geographic routing in wireless ad hoc networks (hereinafter referred to as ad hoc networks) has a significant effect on network performance. It is of great importance for reducing energy consumption, prolonging network lifetime, among other things, thus receiving more and more attentions. This paper provides a comprehensive introduction to the research development on energy-aware geographic routing protocols in ad hoc networks. First, the geographic routing in ad hoc networks is introduced. Next, the formation background, the metrics, the rule of node selection, the research significance and the classifications of energy-aware geographic routing protocols are discussed in detail. Then, some classical energy-aware geographic routing protocols are presented along with multi-angle comparisons and summaries. After that, existing problems are analyzed and open research issues are highlighted. Finally, a summary of this paper is given.

Abstract:The periodic and dynamic topology of satellite networks poses new challenge to the design of routing protocols. Since the routing protocols of conventional networks can not be effectively applied to satellite networks, many new routing techniques for satellite networks were put forward. With an introduction to satellite network architecture and topology control strategies along with the developmental history of routing techniques on satellite networks, this paper summarizes the core mechanism, feature and major problems of some important routing techniques of satellite networks from the classification perspective. Considering application requirements, the paper also suggests the future trends towards the development of routing techniques on satellite networks.

Abstract:In the realistic communication environment, due to the noise, packet conflict, signal attenuation and other factors, information exchange is generally unreliable among nodes in the wireless sensor networks. Broadcast is a widely-used operation, and building an energy-efficient broadcast algorithm has important theoretical and application value in improving the performance of wireless sensor networks. This paper studies the minimum energy broadcast problem of wireless sensor networks with the unreliable communications. Firstly, it analyzes the minimum energy consumption of communication model between adjacent nodes and presents the optimal transmission radius that can guarantee the neighbor node to receive packets with probability no less than P^*. Then, it discusses the relationship between multi-hop relay strategy and location information of nodes. It finally presents a PSO-based broadcast algorithm with minimum spanning tree, which can guarantee that all nodes in the network will receive packets with probability no less than P^* and minimize the total energy consumption. The simulation results show that the presented broadcast algorithm can not only guarantee all nodes to receive packets with probability no less than P^*, but also consume less energy and have better performance compared with the improved BIP algorithm.

Abstract:The unlicensed user (the secondary user) sends the available spectrum information that it sensed to its neighbors as the foundation of spectrum allocation in the distributed spectrum allocation process for wireless cognitive radio networks. In reality only part of the information affects the allocation results. The transmission of redundant data not only generates extra communication cost but also wastes computing resource in the spectrum allocation processand is therefore undesirable for spectrum-scarce CRNs and power-limited cognitive terminals. Thus, it is a practical problem to eliminate the useless data before transmission. Based on skyline query processing, this paper proposes a multiple-objective redundant sensed traffic eliminating algorithm called Sskychannel query processing. The fundamental idea of the algorithm is to divide the channel space into dominate region, dominated region and free region. Each sensed channel will be put into the corresponding region according to its parameters. The information of dominated channels is ignored, and user only transmits the information of non dominated channels. It can decrease the network cost and save the computing resource for each user while guaranteeing not to affect the spectrum allocation result. The experimental results also show the advantages of skychannel query algorithm in terms of decreasing communication cost and saving computing resource.

Abstract:The distinguishing characteristic of identity-based signatures is that only the identity with no certificate of a signer is involved in the verification of a signature, which simplifies the key management procedures dramatically. A novel identity-based signature scheme that can be proven secure in the standard model was given by Paterson and Schuldt in 2006. Unfortunately, the scheme is not efficient in computation. An improvement due to Gu, et al. was proposed recently to improve the computational efficiency, and it was claimed as being provably secure in the standard model and more efficient than the known schemes in the same flavor. However, this paper shows that the new scheme by Gu, et al. is insecure by demonstrating two concrete attacks in which an adversary can not only forge the private key of an identity but also forge signatures on arbitrary message. The study also identifies a flaw in their security proofs, i.e., the view of the adversary in the security reduction is not independent of the event that the simulation succeeds.