Decomposition plays a significant role in cooperative coevolution, which shows great potential in large-scale black-box optimization (LSBO). However, current learning-based decomposition algorithms require many fitness evaluations (FEs) to detect variable interdependencies and encounter the difficulty of threshold setting. To address these issues, this study proposes an efficient adaptive differential grouping (EADG) algorithm. Instead of homogeneously tackling different types of LSBO instances, EADG first identifies the instance type by detecting the interdependencies of a few pairs of variable subsets. Only if the instance is partially separable dose EADG further engage with it by converting its decomposition process into a search process in a binary tree. This facilitates the systematic reutilization of evaluated solutions so that half the interdependencies can be directly deduced without extra FEs. To promote the decomposition accuracy, EADG specially designs a normalized interdependency indicator that can adaptively generate a decomposition threshold according to its ordinal distribution. Theoretical analysis and experimental results show that EADG outperforms current popular decomposition algorithms. Further tests indicate that it can help cooperative coevolution achieve highly competitive optimization performance.
Sound event detection in real-world environments suffers from the interference of non-stationary and time-varying noise. This paper presents an adaptive noise reduction method for sound event detection based on non-negative matrix factorization (NMF). First, a scheme for noise dictionary learning from the input noisy signal is employed by the technique of robust NMF, which supports adaptation to noise variations. The estimated noise dictionary is used to develop a supervised source separation framework in combination with a pre-trained event dictionary. Second, to improve the separation quality, we extend the basic NMF model to a weighted form, with the aim of varying the relative importance of the different components when separating a target sound event from noise. With properly designed weights, the separation process is forced to rely more on those dominant event components, whereas the noise gets greatly suppressed. The proposed method is evaluated on a dataset of the rare sound event detection task of the DCASE 2017 challenge, and achieves comparable results to the top-ranking system based on convolutional recurrent neural networks (CRNNs). The proposed weighted NMF method shows an excellent noise reduction ability, and achieves an improvement of an F-score by 5%, compared to the unweighted approach.
Satellites offer many services through communication with stations, such as tracking, navigation, telecommand uplink, earth observation, etc. How to coordinate these services is referred to as the satellite range scheduling problem (SRSP). In the research, it is found that only the resources (referring to time slots of stations) requested by more than one satellite simultaneously influence scheduling results. These resources are called critical resources and selected as scheduling elements, which makes some jobs optimally served in advance and the problem be decomposable into a multi-stage decision process, so dynamic programming is suitable to be employed. For large-scale SRSPs, a route-reduction-based dynamic programming (RR-DP) is presented, wherein a multi-level route reduction strategy is adopted to alleviate ‘the curse of dimensionality’. Experimental results reveal that RR-DP can find optimal solutions for small-to-medium sized problems and outperforms state-of-the-art methods for large-scale problems.
23 September 2016 in IEEE Transactions on Cybernetics
Many complex networks have been shown to have community structures. Detecting those structures is very important for understanding the organization and function of networks. Because this problem is NP-hard, it is appropriate to resort to evolutionary algorithms. Chemical reaction optimization (CRO) is a novel evolutionary algorithm inspired by the interactions among molecules during chemical reactions. In this paper, we propose a CRO variant named dual-representation CRO (DCRO) to address the community detection problem. DCRO encodes a solution in two representations: one is locus-based and the other is vector-based. The former representation can ensure the validity of a solution and fits for diversification search, and the latter is convenient for intensification search. We thus design two operators for CRO based on these two representations. Their cooperation enables DCRO to achieve a good balance between exploration and exploitation. Experimental results on synthetic and real-life networks show that DCRO can find community structures close to the actual ones and is capable of achieving solutions comparable to several state-of-the-art methods.
For Wireless Sensor Networks (WSNs), the Voronoi partition of a region is a challenging problem owing to the limited sensing ability of each sensor and the distributed organization of the network. In this paper, an algorithm is proposed for each sensor having a limited sensing range to compute its limited Voronoi cell autonomously, so that the limited Voronoi partition of the entire WSN is generated in a distributed manner. Inspired by Graham’s Scan (GS) algorithm used to compute the convex hull of a point set, the limited Voronoi cell of each sensor is obtained by sequentially scanning two consecutive bisectors between the sensor and its neighbors. The proposed algorithm called the Boundary Scan (BS) algorithm has a lower computational complexity than the existing Range-Constrained Voronoi Cell (RCVC) algorithm and reaches the lower bound of the computational complexity of the algorithms used to solve the problem of this kind. Moreover, it also improves the time efficiency of a key step in the Adjust-Sensing-Radius (ASR) algorithm used to compute the exact Voronoi cell. Extensive numerical simulations are performed to demonstrate the correctness and effectiveness of the BS algorithm. The distributed realization of the BS combined with a localization algorithm in WSNs is used to justify the WSN nature of the proposed algorithm.