Search

The coverage path planning of UAVs is a complex optimization problem in practice, especially for those involving multiple target areas. It is challenging to comprehensively plan the inter-area visiting order and the intra-area coverage paths simultaneously. Due to the battery limitation, usually the task can hardly be finished by a single UAV, and instead a fleet of UAVs are required. In this paper, we first formulate an energy-aware multi-UAV multi-area coverage path planning (EM2CPP) model, in order to characterize the practical path planning requirements of UAVs in complex conditions. Subsequently, to accomplish the optimization task, we propose a bipartite cooperative coevolution (BiCC) algorithm that coevolves an inter-area path planning and an intra-area path planning components to obtain good solutions. The basic operators in BiCC, such as the initialization and the reproduction operators, are tailored for the task of EM2CPP. Besides, we also develop a fast heuristic algorithm for EM2CPP, which is able to produce approximate solutions in a short time. Simulations on real-world datasets validate the good performance of the proposed methods.

Real-time taxi–passenger matching plays a critical role in modern taxi dispatch systems. Currently, the greedy strategy is widely adopted, which limits the quality of the service (QoS) and the profit of the entire system. There are two crucial tasks in this system: 1) the pairwise prioritization and 2) the matching of taxi–passenger pairs. In this paper, we develop a two-stage taxi–passenger matching system to deal with these two tasks. In the first stage, we design a fuzzy controller to assign a priority score to each taxi–passenger pair in real time. To ensure its performance on providing good QoS and profit, the fuzzy controller is optimized by an offline differential evolution algorithm. New individual representation is designed to optimize the membership functions and fuzzy rule base simultaneously. To accelerate the optimization process, the algorithm is implemented in a parallel way. Then, in the second stage, considering the priority scores as weights in the bipartite graph of taxi and passenger sets, we further apply a polynomial Kuhn–Munkres algorithm to find the maximum weight perfect matching in the bipartite graph. Simulated results validate the effectiveness of the proposed algorithm, which is able to enhance the QoS provided by the taxi system and improve the profit gained by the taxi service company.

Traffic Signal Control (TSC) is a fundamental task in modern intelligent transport systems. TSC is often formulated as a bi‐level optimization problem, comprised by the signal timing at the upper level and the Dynamic User Equilibrium (DUE) traffic assignment at the lower level. Since DUE is non‐convex, existing methods either formulate approximation models or adopt traffic simulators. However, approximation models may oversimplify the practical situations, while traffic simulators are usually time‐consuming. This paper formulates a vehicle‐based DUE (vDUE) model and proposes an agile method that can simultaneously maintain the computational simplicity and the traffic dynamics for the traffic assignment. Further, an agile TSC system is built by combining the vDUE at the lower level for the traffic assignment with an adaptive differential evolution algorithm at the upper level for the signal timing optimization. To enhance the effectiveness of optimization, the TSC problem formulation is also improved to make it better characterize the practical requirements. In the experiments undertaken, comparisons of different TSC methods are carried out on both real‐world and synthetic transportation networks. The experimental results validate the effectiveness of the proposed agile TSC system in various traffic situations.

As the cornerstone for joint dimension reduction and feature extraction, extensive linear projection algorithms were proposed to fit various requirements. When being applied to image data, however, existing methods suffer from representation deficiency since the multi-way structure of the data is (partially) neglected. To solve this problem, we propose a novel Low-Rank Preserving t-Linear Projection (LRP-tP) model that preserves the intrinsic structure of the image data using t-product-based operations. The proposed model advances in four aspects: 1) LRP-tP learns the t-linear projection directly from the tensorial dataset so as to exploit the correlation among the multi-way data structure simultaneously; 2) to cope with the widely spread data errors, e.g., noise and corruptions, the robustness of LRP-tP is enhanced via self-representation learning; 3) LRP-tP is endowed with good discriminative ability by integrating the empirical classification error into the learning procedure; 4) an adaptive graph considering the similarity and locality of the data is jointly learned to precisely portray the data affinity. We devise an efficient algorithm to solve the proposed LRP-tP model using the alternating direction method of multipliers. Extensive experiments on image feature extraction have demonstrated the superiority of LRP-tP compared to the state-of-the-arts.

In multi-view subspace clustering, the low-rankness of the stacked self-representation tensor is widely accepted to capture the high-order cross-view correlation. However, using the nuclear norm as a convex surrogate of the rank function, the self-representation tensor exhibits strong connectivity with dense coefficients. When noise exists in the data, the generated affinity matrix may be unreliable for subspace clustering as it retains the connections across inter-cluster samples due to the lack of sparsity. Since both the connectivity and sparsity of the self-representation coefficients are curial for subspace clustering, we propose a Reliable Multi-View Affinity Learning (RMVAL) method so as to optimize both properties in a single model. Specifically, RMVAL employs the low-rank tensor constraint to yield a well-connected yet dense solution, and purifies the densely connected self-representation tensor by preserving only the connections in local neighborhoods using the l1-norm regularization. This way, the strong connections on the self-representation tensor are retained and the trivial coefficients corresponding to the inter-cluster connections are suppressed, leading to a "clean" self-representation tensor and also a reliable affinity matrix. We propose an efficient algorithm to solve RMVAL using the alternating direction method of multipliers. Extensive experiments on benchmark databases have demonstrated the superiority of RMVAL.

The increasing popularity of battery-limited electric vehicles puts forward an important issue of how to charge the vehicles effectively. This problem, commonly referred to as Electric Vehicle Charging Scheduling (EVCS), has been proven to be NP-hard. Most of the existing works formulate the EVCS problem simply as a constrained shortest path finding problem and treat it by discrete optimization. However, other variables such as the charging amount of energy and the charging option at a station need to be considered in practical use. This paper hence formulates the EVCS problem as a hierarchical mixed-variable optimization problem, considering the dependency among the station selection, the charging option at each station and the charging amount settings. To adapt to the new problem model, we specifically design a Mixed-Variable Differentiate Evolution (MVDE) as the scheduling algorithm for our proposed EVCS system. The MVDE contains several specific operators, including a charging station route construction, a hierarchical mixed-variable mutation operator and a constraint-aware evaluation operator. Experimental results validate the effectiveness of our proposed MVDE-based system on both synthetic and real-world transportation networks.

Neural network ensemble (NNE) exhibits improved performance when compared with a single neural network (NN) in most cases. Traditionally, each base network in an NNE is trained individually, which may result in network redundancy and expensive training overhead. This paper proposes a new adaptive niching evolutionary algorithm, which possesses promising performance in finding multiple optima in terms of good accuracy and diversity. By means of this algorithm, all NNs in an NNE can be trained simultaneously. In particular, the proposed algorithm is named adaptive niching differential evolution (ANDE), which is characterized by a heuristic clustering method to enable iteratively cluster subpopulations that track and locate multiple optima, a parameter adaptation strategy to adaptively adjust parameters according to the subpopulation states, and an auxiliary movement scheme to promote the equilibrium between exploration and exploitation. Experimental results validate the efficiency and effectiveness of the proposed ANDE on the benchmark test suite of multimodal optimization. Furthermore, ANDE is extended to concurrently train multiple base NNs for ensemble and the experiments show a promising performance of ANDE-NNE.

Linear discriminant analysis has been incorporated with various representations and measurements for dimension reduction and feature extraction. In this paper, we propose two-dimensional quaternion sparse discriminant analysis (2D-QSDA) that meets the requirements of representing RGB and RGB-D images. 2D-QSDA advances in three aspects: 1) including sparse regularization, 2D-QSDA relies only on the important variables, and thus shows good generalization ability to the out-of-sample data which are unseen during the training phase; 2) benefited from quaternion representation, 2D-QSDA well preserves the high order correlation among different image channels and provides a unified approach to extract features from RGB and RGB-D images; 3) the spatial structure of the input images is also retained via the matrix-based processing. We tackle the constrained trace ratio problem of 2D-QSDA by solving a corresponding constrained trace difference problem, which is then transformed into a quaternion sparse regression (QSR) model. Afterward, we reformulate the QSR model to an equivalent complex form to avoid the processing of the complicated structure of quaternions. A nested iterative algorithm is designed to learn the solution of 2D-QSDA in the complex space and then we convert this solution back to the quaternion domain. To improve the separability of 2D-QSDA, we further propose 2D-QSDA w using the weighted pairwise between-class distances. Extensive experiments on RGB and RGB-D databases demonstrate the effectiveness of 2D-QSDA and 2D-QSDA w compared with peer competitors.

The cooperative coevolution (CC) framework achieves a promising performance in solving large scale global optimization problems. The framework encounters difficulties on nonseparable problems, where variables interact with each other. Using the static grouping methods, variables will be theoretically grouped into one big subcomponent, whereas the random grouping strategy endures low efficiency. In this paper, a dynamic CC framework is proposed to tackle the challenge. The proposed framework works in a computationally efficient manner, in which the computational resources are allocated to a series of elitist subcomponents consisting of superior variables. First, a novel estimation method is proposed to evaluate the contribution of variables using the historical information of the best overall fitness. Based on the contribution and the interaction information, a dynamic grouping strategy is conducted to construct the dynamic subcomponent that evolves in the next evolutionary period. The constructed subcomponents are different from each other, and therefore the required parameters to control the optimization of each subcomponent vary a lot in each evolutionary period. A stage-by-stage parameter adaptation strategy is proposed to adapt the optimizer to the dynamic optimization environment. Experimental results indicate that the proposed framework achieves competitive results compared with the state-of-the-art CC frameworks.

Cloud workflow scheduling is significantly challenging due to not only the large scale of workflow but also the elasticity and heterogeneity of cloud resources. Moreover, the pricing model of clouds makes the execution time and execution cost two critical issues in the scheduling. This paper models the cloud workflow scheduling as a multiobjective optimization problem that optimizes both execution time and execution cost. A novel multiobjective ant colony system based on a co-evolutionary multiple populations for multiple objectives framework is proposed, which adopts two colonies to deal with these two objectives, respectively. Moreover, the proposed approach incorporates with the following three novel designs to efficiently deal with the multiobjective challenges: 1) a new pheromone update rule based on a set of nondominated solutions from a global archive to guide each colony to search its optimization objective sufficiently; 2) a complementary heuristic strategy to avoid a colony only focusing on its corresponding single optimization objective, cooperating with the pheromone update rule to balance the search of both objectives; and 3) an elite study strategy to improve the solution quality of the global archive to help further approach the global Pareto front. Experimental simulations are conducted on five types of real-world scientific workflows and consider the properties of Amazon EC2 cloud platform. The experimental results show that the proposed algorithm performs better than both some state-of-the-art multiobjective optimization approaches and the constrained optimization approaches.

Parallel test assembly has long been an important yet challenging topic in educational assessment. Cognitive diagnosis models (CDMs) are a new class of assessment models and have drawn increasing attention for being able to measure examinees' ability in detail. However, few studies have been devoted to the parallel test assembly problem in CDMs (CDM-PTA). To fill the gap, this paper models CDM-PTA as a subset-based bi-objective combinatorial optimization problem. Given an item bank, it aims to find a required number of tests that achieve optimal but balanced diagnostic performance, while satisfying important practical requests in the aspects of test length, item type distribution, and overlapping proportion. A set-based multiobjective particle swarm optimizer based on decomposition (S-MOPSO/D) is proposed to solve the problem. To coordinate with the property of CDM-PTA, S-MOPSO/D utilizes an assignment-based representation scheme and a constructive learning strategy. Through this, promising solutions can be built efficiently based on useful assignment patterns learned from personal and collective search experience on neighboring scalar problems. A heuristic constraint handling strategy is also developed to further enhance the search efficiency. Experimental results in comparison with three representative approaches validate that the proposed algorithm is effective and efficient.

Cross-docks serve as distribution centers where shipments from different vendors are first consolidated according to their destinations, and then delivered to the retailers directly, with little or no storage in between. A critical problem encountered in the operation of cross-docks is the assignment of receiving and shipping doors, which greatly influences the labor or machinery cost of transferring the shipments between inbound and outbound transports. We show that the cross-dock door assignment problem (CDAP) is strictly non-deterministic polynomial-time complete. Although some deterministic algorithms have been reported to handle small-scale problems, the solutions to the middle- and large-scale CDAPs progressed at a slow pace. In this paper, we develop a nature-inspired dual-colony ant algorithm for CDAP, in which the two colonies of ants cooperatively search the optimal assignments of receiving and shipping doors to minimize the transferring costs of shipments. A collaborative local search strategy is designed and incorporated into the algorithm to enhance the search efficiency. Experiments have been conducted on a number of problem instances with different cross-dock sizes and freight flow patterns. The results show that the proposed algorithm is very competitive and can provide better solutions than the state-of-the-art heuristic algorithms.

Mobile crowdsourcing is an emerging crowdsourcing paradigm, which generates large-scale sensing tasks and sensing data. One of the major issues in mobile crowdsourcing is how to maximize social welfare through selecting appropriate sensing tasks for crowd workers and selecting appropriate workers for sensing tasks such that it can improve the effectiveness and efficiency of mobile crowdsourcing. This paper proposes an incentive mechanism to maximize social welfare for mobile crowdsourcing and, respectively, investigates worker-centric task selection and platform-centric worker selection. This paper applies an optimization algorithm in task selection for mobile crowdsourcing systems. A discrete particle swarm optimization (DPSO) algorithm for worker-centric task selection is designed to maximize the utilities of workers. In addition, a platform-centric worker selection method, which integrates multiattribute auction and two-stage auction, is proposed to maximize the utility of the platform. The performance of the proposed incentive mechanism is evaluated through experiments. The experimental results show that the proposed incentive mechanism can improve the efficiency and truthfulness of mobile crowdsourcing effectively.

This paper develops a novel tree structured random walking swarm optimizer for seeking multiple optima in multimodal landscapes. First, we show that the artificial bee colony algorithm has some distinct advantages over the other swarm intelligence algorithms for accomplishing the multimodal optimization task, from analytical and experimental perspectives. Then, a tree-structured niching strategy is developed to assist the algorithm in exploring multiple optima simultaneously. The strategy constructs a weighted complete graph based on the positions of the food sources (candidate solutions). A minimum spanning tree that encodes the distribution of the food sources is built upon the complete graph to guide the search of the bee swarm. Each artificial bee sets out from a food source and flies along the edges of the tree to gather information about the search space. The dance trajectories of bees are simulated by a random walk model considering both distance and fitness information. Then, mutant vectors are selected from the trajectories to update the food source. This graph-based search method is introduced to simultaneously promote the progress of exploitation and exploration in multimodal environments. Extensive experiments indicate that our proposed algorithm outperforms several state-of-the-art algorithms.

Recent studies have shown the effectiveness of using depth information in salient object detection. However, the most commonly seen images so far are still RGB images that do not contain the depth data. Meanwhile, the human brain can extract the geometric model of a scene from an RGB-only image and hence provides a 3D perception of the scene. Inspired by this observation, we propose a new concept named RGB-'D' saliency detection, which derives pseudo depth from the RGB images and then performs 3D saliency detection. The pseudo depth can be utilized as image features, prior knowledge, an additional image channel, or independent depth-induced models to boost the performance of traditional RGB saliency models. As an illustration, we develop a new salient object detection algorithm that uses the pseudo depth to derive a depth-driven background prior and a depth contrast feature. Extensive experiments on several standard databases validate the promising performance of the proposed algorithm. In addition, we also adapt two supervised RGB saliency models to our RGB-'D' saliency framework for performance enhancement. The results further demonstrate the generalization ability of the proposed RGB-'D' saliency framework.

Traditional multi-objective evolutionary algorithms have encountered difficulties when handling many-objective problems. This is due to the loss of selection pressure incurred by the growing size of objective space. A variety of environmental selection operators have been proposed to address the issue, each has its distinct benefits and drawbacks. We develop a novel ensemble framework to enhance the effectiveness and robustness of many-objective optimization. The framework incorporates multiple environmental selection operators to guide the search, which are then viewed as voters to construct a mating pool. We design an ensemble mating selection strategy that makes decisions based on the preference information provided by the voters: individuals elected by more voters will be assigned larger possibilities to enter the mating pool. By doing so, high quality offspring can be reproduced from the elected promising candidates. To accommodate the multiple selection operators for voting, the framework maintains multiple parallel populations, where each population is updated by one of the selection operators. An instantiation of the framework with three popular operators is presented as a prime example. Extensive experiments have been conducted on a number of many-objective problems to examine the effectiveness of the proposed approach. Experimental results show that the mating selection strategy is capable of improving the quality of the obtained solution set.

The automatic itinerary planning service requires to generate multiple-day schedules automatically under user-specified POIs and constraints. Knowing as an NP-Hard optimization problem, the task is commonly solved by (meta-)heuristic algorithms such as the genetic algorithms (GAs). However, considering the concurrent requests received by a web server in practice, the time efficiency of the existing itinerary planners can be rather unsatisfactory. To address the issue, this paper proposes a computational approach that hybridizing a GA with the reinforcement learning (RL) technology. The benefit is that we no longer need to re-execute the GA for each new request arrived. Instead, the approach keeps the historical solutions in track and maintains a RL agent to sequentially decide how to handle each new request. Experimental results show that the proposed approach is able to stably provide high-quality solutions, while greatly reducing the average time overhead of the web server.

As a global optimization technique, the evolutionary algorithms provide powerful solvers to the data clustering problem. However, the individual representations in evolutionary clustering algorithms exist redundancy and inconsistency problems, which not only wastes the search efforts but also disorders the mutual learning process between individuals. To address the problems, in this paper, we propose a genetic sequence resorting method. This method first identifies a reference parameter vector and then resorts the order of the genetic sequences in each individual according to their distance to the reference vector. In this way, the solutions represented by individuals are unified, which removes redundancy and enhances the efficiency of the mutual learning in the algorithm. Incorporating the above method, a new and generic evolutionary clustering framework is developed. Under this framework, we specifically design two algorithms: one for distance-based convex clustering and the other for density-based nonconvex clustering. Experiments show that our method can effectively improve the performance of evolutionary clustering algorithms on various datasets with both convex and nonconvex cluster shapes.

Path planning is a critical issue to ensure the safety and reliability of the autonomous navigation system of the autonomous underwater vehicles (AUVs). Due to the nonlinearity and constraint issues, existing algorithms perform unsatisfactorily or even cannot find a feasible solution when facing large-scale problem spaces. This paper improves the path planning of AUVs in terms of both the path planning model and the optimization algorithm. The proposed model is comprehensive, which aggregates the length, energy consumption, and collision risk into the objective function and incorporates the steering window constraint. Based on the model, we develop a nature-inspired ant colony optimization algorithm to search the optimal path. Our algorithm is named alarm pheromone-assisted ant colony system (AP-ACS), since it incorporates the alarm pheromone in addition to the traditional guiding pheromone. The alarm pheromone alerts the ants to infeasible areas, which saves invalid search efforts and, thus, improves the search efficiency. Meanwhile, three heuristic measures are specifically designed to provide additional knowledge to the ants for path planning. In the experiments, different from the previous works that are tested on synthetic instances only, we implement an interface to retrieve the practical underwater environment data. AP-ACS and the compared algorithms are thus tested on several practical environments of different scales. The experimental results show that AP-ACS can effectively handle the constraints and outperforms the other algorithms in terms of accuracy, efficiency, and stability.

Demand side management is an efficient way of reducing the grid fluctuation and enhancing the net profit in the smart grid. As the increasing complexity of the real-world applications, e.g., NP-hard and non-polynomial problems, a distributed coevolution algorithm is proposed to cope with this challenge. In the proposed algorithm, the management system is modeled as a hierarchical structure. The user side locates at the lowest level and upper levels represent the system operators. The system operators manage users' energy consumption behavior through the real-time pricing strategy. The genetic algorithm and particle swarm optimization are modified to play the role of the smart scheduler and the smart pricing generator. The end users conduct appliance commitment using the smart scheduler which considers the users' comfort level and the electricity cost. The decision of the lower level depends directly on the real-time pricing strategy released by its adjacent upper level. The real-time pricing is developed by the smart pricing generator which considers the net profit and the grid fluctuation. Three types of experiments are conducted on a distributed platform to investigate and ascertain the performance of the proposed algorithm. For the operator side, the experimental results indicate that the proposed algorithm improves the grid fluctuation, and enhances the net profit. As for the user side, it improves the comfort level and achieves budget saving.

To learn the self-representation matrices/tensor that encodes the intrinsic structure of the data, existing multiview self-representation models consider only the multiview features and, thus, impose equal membership preference across samples. However, this is inappropriate in real scenarios since the prior knowledge, e.g., explicit labels, semantic similarities, and weak-domain cues, can provide useful insights into the underlying relationship of samples. Based on this observation, this article proposes a prior knowledge regularized multiview self-representation (P-MVSR) model, in which the prior knowledge, multiview features, and high-order cross-view correlation are jointly considered to obtain an accurate self-representation tensor. The general concept of “prior knowledge” is defined as the complement of multiview features, and the core of P-MVSR is to take advantage of the membership preference, which is derived from the prior knowledge, to purify and refine the discovered membership of the data. Moreover, P-MVSR adopts the same optimization procedure to handle different prior knowledge and, thus, provides a unified framework for weakly supervised clustering and semisupervised classification. Extensive experiments on real-world databases demonstrate the effectiveness of the proposed P-MVSR model.

Multimodal optimization problems have multiple satisfactory solutions to identify. Most of the existing works conduct the search based on the information of the current population, which can be inefficient. This article proposes a probabilistic niching evolutionary computation framework that guides the future search based on more sufficient historical information, in order to locate diverse and high-quality solutions. A binary space partition tree is built to structurally organize the space visiting information. Based on the tree, a probabilistic niching strategy is defined to reinforce exploration and exploitation by making full use of the structural historical information. The proposed framework is universal for incorporating various baseline niching algorithms. In this article, we integrate the proposed framework with two niching algorithms: 1) a distance-based differential evolution algorithm and 2) a topology-based particle swarm optimization algorithm. The two new algorithms are evaluated on 20 multimodal optimization test functions. The experimental results show that the proposed framework helps the algorithms obtain competitive performance. They outperform a number of state-of-the-art niching algorithms on most of the test functions.

This paper develops a novel algorithm to solve real-world constrained optimization problems, which hybridizes multiobjective optimization techniques with an ϵ-constrained method. First, a constrained optimization problem at hand is transformed into a bi-objective optimization problem. By the transformation, the advantage of multiobjective optimization techniques can be utilized in the constrained optimization area to balance population diversity and convergence. Meanwhile, the ϵ-constrained method is applied, which keeps the population evolving toward feasible region of the constrained optimization problem. In our proposed algorithm, the differential evolution is employed as a search engine to create offspring at each generation. Further, different combinations of mutation operators have been developed to improve the search ability and the population convergence at different stages. The performance of our approach is evaluated on 64 benchmark test functions from three popular test suits. Experimental results demonstrate that our proposed approach is capable of obtaining high-quality solutions on the majority of benchmark test functions, when compared with some other state-of-the-art constrained optimization algorithms.

Nowadays, large-scale optimization problems are ubiquitous in many research fields. To deal with such problems efficiently, this paper proposes a distributed differential evolution with adaptive mergence and split (DDE-AMS) on subpopulations. The novel mergence and split operators are designed to make full use of limited population resource, which is important for large-scale optimization. They are adaptively performed based on the performance of the subpopulations. During the evolution, once a subpopulation finds a promising region, the current worst performing subpopulation will merge into it. If the merged subpopulation could not continuously provide competitive solutions, it will be split in half. In this way, the number of subpopulations is adaptively adjusted and better performing subpopulations obtain more individuals. Thus, population resource can be adaptively arranged for subpopulations during the evolution. Moreover, the proposed algorithm is implemented with a parallel master-slave manner. Extensive experiments are conducted on 20 widely used large-scale benchmark functions. Experimental results demonstrate that the proposed DDE-AMS could achieve competitive or even better performance compared with several state-of-the-art algorithms. The effects of DDE-AMS components, adaptive behavior, scalability, and parameter sensitivity are also studied. Finally, we investigate the speedup ratios of DDE-AMS with different computation resources.

Superpixel segmentation has been of increasing importance in many computer vision applications recently. To handle the problem, most state-of-the-art algorithms either adopt a local color variance model or a local optimization algorithm. This paper develops a new approach, named differential evolutionary superpixels, which is able to optimize the global properties of segmentation by means of a global optimizer. We design a comprehensive objective function aggregating within-superpixel error, boundary gradient, and a regularization term. Minimizing the within-superpixel error enforces the homogeneity of superpixels. In addition, the introduction of boundary gradient drives the superpixel boundaries to capture the natural image boundaries, so as to make each superpixel overlaps with a single object. The regularizer further encourages producing similarly sized superpixels that are friendly to human vision. The optimization is then accomplished by a powerful global optimizer-differential evolution. The algorithm constantly evolves the superpixels by mimicking the process of natural evolution, while using a linear complexity to the image size. Experimental results and comparisons with eleven state-of-the-art peer algorithms verify the promising performance of our algorithm.

Solving jigsaw-puzzles has been of increasing importance in many real-world applications. The existing methods endure the problem of local or premature convergence, which perform inefficiently on some challenging images. For an efficient optimizer of jigsaw puzzles, this paper utilizes the powerfulness of the global optimization technique and develops a multi-strategy evolution algorithm. The algorithm constantly generates jigsaw puzzle solutions by mimicking the process of natural evolution, while adopting a new objective function to evaluate the solutions. An elite-based crossover operator is designed to exploit the historically good patterns for generating competitive solutions. Then, a new mutation operator consisting of four perturbation strategies is developed to handle different puzzle situations. Experimental results verify the promising performance of the proposed algorithm that it outperforms the state-of-the-art methods on various image datasets.

Most learning methods contain optimization as a substep, where the nondifferentiability and multimodality of objectives push forward the interplay of evolutionary optimization algorithms and machine learning models. The recently emerged evolutionary multimodal optimization (MMOP) technique enables the learning of diverse sets of effective parameters for the models simultaneously, providing new opportunities to the applications requiring both accuracy and diversity, such as ensemble, interactive, and interpretive learning. Targeting at locating multiple optima simultaneously in the multimodal landscape, this paper develops an efficient neighborhood-based niching algorithm. Bare-bones differential evolution is used as the baseline. Further, using Gaussian mutation with local mean and standard deviations, the neighborhoods capture niches that match well with the contours of peaks in the landscape. To increase diversity and enhance global exploration, the proposed algorithm embeds a diversity preserving operator to reinitialize converged or overlapped neighborhoods. The experimental results verify that the proposed algorithm has superior and consistent performance for a wide range of MMOP problems. Further, the algorithm has been successfully applied to train neural network ensembles, which validates its effectiveness and benefits of learning multimodal parameters.

Multi-label learning plays a critical role in the areas of data mining, multimedia, and machine learning. Although many multi-label approaches have been proposed, few of them have considered to de-emphasize the effect of noisy features in the learning process. To address this issue, this paper designs a new method named representative multi-label learning algorithm. Instead of considering all features, the proposed algorithm focuses only on the representative ones, via incorporating an affinity propagation algorithm, kernel formulation, and a multi-label support vector machine into the learning framework. Specifically, it first adopts an affinity propagation algorithm to select a set of representative features and capture the relationships among features. Then, the algorithm constructs the representative kernel functions to measure the similarity between data instances. Finally, a multi-label support vector machine is applied to solve the learning problem. Based on the representative multi-label learning algorithm, we further design a representative multi-label learning ensemble framework to improve the accuracy, stableness, and robustness. Experimental results show that the proposed algorithm works well on most of the datasets and outperforms the compared multi-label learning approaches.

Graphical abstractDisplay Omitted HighlightsDevelop a splicing-driven memetic algorithm to reconstruct cross-cut shredded text documents.Design a comprehensive cost function to evaluate solutions and to guide individual search.Design novel reproduction operators to effectively utilize the adjacency information of shreds.Propose an elitism-based local search strategy to further enhance efficiency.Obtain good reconstruction performance in terms of the solution quality and convergence speed. Reconstruction of cross-cut shredded text documents (RCCSTD) plays a crucial role in many fields such as forensic and archeology. To handle and reconstruct the shreds, in addition to some image processing procedures, a well-designed optimization algorithm is required. Existing works adopt some general methods in these two aspects, which may not be very efficient since they ignore the specific structure or characteristics of RCCSTD. In this paper, we develop a splicing-driven memetic algorithm (SD-MA) specifically for tackling the problem. As the name indicates, the algorithm is designed from a splicing-centered perspective, in which the operators and fitness evaluation are developed for the purpose of splicing the shreds. We design novel crossover and mutation operators that utilize the adjacency information in the shreds to breed high-quality offsprings. Then, a local search strategy based on shreds is performed, which further improves the evolution efficiency of the population in complex search space. To extract valid information from shreds and improve the accuracy of splicing costs, we propose a comprehensive objective function that considers both edge and empty row-based splicing errors. Experiments are carried out on 30 RCCSTD scenarios and comparisons are made against previous best-known algorithms. Experimental results show that the proposed SD-MA displays a significantly improved performance in terms of solution accuracy and convergence speed.

Destination prediction is very important in location-based services such as recommendation of targeted advertising location. Most current approaches always predict destination according to existing trip based on history trajectories. However, no existing work has considered the difference between the effects of passing-by locations and the destination in history trajectories, which seriously impacts the accuracy of predicted results as the destination can indicate the purpose of traveling. Meanwhile, the temporal information of history trajectories in destination prediction plays an important role. On one hand, the history trajectories in different periods also differ in the influence, e.g., the history trajectories from last week can reflect the status quo more accurately than the history trajectories two years ago. On the other hand, the history trajectories in different time slots reflect different facts of traffic and moving habits of people, e.g., visiting a restaurant in the daytime and visiting a bar at night. Although a huge amount of history trajectories can be achieved in the era of big data, it is still far from covering all the query trajectories since a road network is widely distributed and trajectory data is sparse. The temporal sensitivity of history trajectories highlights the sparsity problem even more. Therefore, we propose a novel model $\text{T-DesP}$ to solve the aforementioned problems. The model is comprised of two modules: trajectory learning and destination prediction. In the module of trajectory learning, a novel method called the mirror absorbing Markov chain model is proposed for modeling the trajectories for isolating the destination. We build a transition tensor to deduce the transition probability between each location pair in a particular time slot. To address the data sparsity problem, we fill the missing values in transition tensor through a context-aware tensor decomposition approach. In the module of destination prediction, an absorbing tensor is derived from the filled transition tensor, and the theoretical model is established for destination prediction. The experiments prove the effectiveness and efficiency of $\text{T-DesP}$ .

Traffic Signal Control (TSC) is a crucial component in the modern intelligent transportation systems. Typically, the TSC can be formulated as a bilevel optimization problem, which is comprised of the signal timing and the traffic assignment modules. The problem is challenging that the existing approaches usually endure a huge computational cost. As a result, many TSC approaches focus on relatively simple and small transportation networks, which do not satisfy the practical situations. To address above issues, this paper proposes an evolvable TSC (EvoTSC) system, which adopts nature-inspired techniques to realize the global optimization of the TSC in large-scale urban transportation networks. Particularly, it involves two evolutionary computation components. The first component is an Adaptive Differential Evolution (ADE) to optimize the signal timing. Meanwhile, the traffic assignment process is included in the solution evaluation of the ADE to react to the traffic flow dynamics. The second component is an off-line Niching Ant Colony Optimization (NACO), which aims to provide the traffic assignment with sets of multiple promising routes beforehand. This way, the EvoTSC system avoids repeatedly building candidate routes for the traffic assignment, which can greatly save the computational cost of the ADE to evaluate each solution in a large-scale transportation network. In experiments, we carry out comparisons of different TSC approaches on both synthetic and practical transportation networks. The experimental results validate the effectiveness of the proposed EvoTSC system.

Food delivery service receives increasing attention nowadays, and path planning plays an important role in the related practical applications. To accomplish the delivery tasks in a short time, deliver staffs traverse all the customers in a short tour to guarantee the freshness of food. In addition, they also need diverse good solutions from which they can choose according to their preference. To obtain diverse good solutions, we propose a multi-population ant colony system algorithm. The ant colony system guides the ants towards a promising space, while the multi-population strategy promises to maintain multiple potential candidate solutions at simultaneously. To evaluate the performance of the proposed algorithm, it is applied to four test instances. The experimental results show that the proposed algorithm can obtain diverse good solutions. Furthermore, the proposed algorithm is utilized to deal with a range of practical problems, which indicates that the proposed algorithm is of practical significance.

Problems with multiple optimal solutions widely exist in the real world. In some applications, it is required to locate multiple optima. However, most studies are dedicated to the continuous multi-solution optimization, while few works contribute to the discrete multi-solution optimization. To promote the multi-solution research in the discrete area, we design a benchmark test suite for multi-solution traveling salesman problems and propose two evaluation indicators. Further, in order to solve the problems, the genetic algorithm is incorporated with a niching technique defined in the discrete space. The proposed algorithm is compared with an existing algorithm. Experimental results demonstrate that the proposed algorithm outperforms the compared algorithm concerning the quality and diversity of obtained solutions.

Multimodal optimization (MMO) aims at finding multiple optimal (or close to optimal) solutions, which plays a crucial role in various fields. However, most of the efforts have been devoted to the continuous MMO domain, while little attention has been paid to discrete problems like the traveling salesman problem (TSP). This paper makes a proof of principle study on multimodal TSP. Particularly, we design a test suite for multimodal TSP and then develop an ant colony algorithm to accomplish the optimization task. The traditional ant algorithms such as the ant colony system are unable to maintain multiple solutions because of the global convergence. To deal with this problem, we propose a novel niching ant colony system (NACS). The algorithm employs a niching strategy and multiple pheromone matrices to preserve population diversity and keep the trace of multiple paths. The experimental results are presented to validate the good performance of the proposed algorithm.

Most existing algorithms for optimizing the lifetime of wireless sensor networks (WSNs) are developed assuming that the sensing ranges of sensors are fixed. This paper1 focuses on adjustable WSNs and proposes a lifetime maximization approach, in which the active periods and sensing ranges of sensors are scheduled simultaneously subject to the constraints of target coverage and power limit. First, the lifetime maximization problem is converted to a problem of finding a set of coverage patterns that can lead to the best schedule when fed into a linear programming model. A genetic algorithm is then developed for coverage pattern finding. With each individual representing a coverage pattern, evolutionary operators and repair strategy are tailored to evolve the pattern set efficiently. Experimental results in a variety conditions show that the proposed approach is advantageous in both terms of computational time and solution quality.

Superpixel segmentation targets at grouping pixels in an image into atomic regions whose boundaries align well with the natural object boundaries. This paper first proposes a new feature representation for superpixel segmentation that holistically embraces color, contour, texture, and spatial features. Then, we introduce a clustering-based discriminability measure to iteratively evaluate the importance of different features. Integrating the feature representation and the discriminability measure, we propose a novel content-adaptive superpixel (CAS) segmentation algorithm. CAS is able to automatically and iteratively adjust the weights of different features to fit various properties of image instances. Experiments on several challenging datasets demonstrate that the proposed CAS outperforms the state-of-the-art methods and has a low computational cost.

Graphical abstractDisplay Omitted HighlightsProvide an updated and systematic review of distributed evolutionary algorithms.Classify the models into population and dimension-distributed groups semantically.Analyze the parallelism, search behaviors, communication costs, scalability, etc.Highlight recent research hotspots in this field.Discuss challenges and potential research directions in this field. The increasing complexity of real-world optimization problems raises new challenges to evolutionary computation. Responding to these challenges, distributed evolutionary computation has received considerable attention over the past decade. This article provides a comprehensive survey of the state-of-the-art distributed evolutionary algorithms and models, which have been classified into two groups according to their task division mechanism. Population-distributed models are presented with master-slave, island, cellular, hierarchical, and pool architectures, which parallelize an evolution task at population, individual, or operation levels. Dimension-distributed models include coevolution and multi-agent models, which focus on dimension reduction. Insights into the models, such as synchronization, homogeneity, communication, topology, speedup, advantages and disadvantages are also presented and discussed. The study of these models helps guide future development of different and/or improved algorithms. Also highlighted are recent hotspots in this area, including the cloud and MapReduce-based implementations, GPU and CUDA-based implementations, distributed evolutionary multiobjective optimization, and real-world applications. Further, a number of future research directions have been discussed, with a conclusion that the development of distributed evolutionary computation will continue to flourish.

Video server deployment problem (VSDP) is a crucial problem in enhancing video viewing experience. It is difficult for traditional deterministic optimization algorithm to solve VSDP because it is non-polynomial hard (NP-hard). Current server deployment patterns are challenged by the growing scale of networks, and it is therefore desirable to design appropriate optimization algorithm to cope with this issue. Owing to the promising performance in solving NP-hard problems, a genetic algorithm (GA)-based optimizer is developed in this paper. We propose a novel deterministic initialization strategy to deploy the GA population in promising initial positions for performance enhancement. In addition, by embedding the maximum cost minimum cost flow (MCMF) in the fitness evaluation, the algorithm optimizes the server deployment and the bandwidth allocation concurrently. This way, the proposed GA is comprehensive, which deals with different aspects involved in VSDP. Experimental results and the comparisons with other algorithms indicate that the proposed algorithm achieves superior performance in terms of solution quality and convergence rate.

Taxi-passenger matching plays a crucial role in modern taxi systems. However, currently, the greedy mechanisms are widely adopted, which may limit the quality of services provided by the systems. In this paper, we first formulate the taxi-passenger matching as a global optimization problem by considering the pickup rate and average waiting time of passengers. Then, we propose a parallel genetic algorithm to solve the problem. New operators, including initialization, crossover, and mutation, are designed specifically for the problem. In addition, we use a divide-and-conquer strategy for dimension reduction. The problem is divided into a number of sub-problems according to the geographical locations of passengers and taxis. Each sub-problem is then solved in a parallel way by a sub-component of our proposed algorithm. Experimental results validate the effectiveness and efficiency of the proposed algorithm. It is able to greatly enhance the quality of services provided by the taxi systems.

Virtual network embedding (VNE), which is a significant problem in cloud computing, has gained much attention among many researchers recently. Due to the NP-hardness of VNE, the existing solvers are either inefficient or inaccurate. This paper develops a novel algorithm based on the ant colony system (ACS). To solve the VNE problem, the algorithm structure concentrates on the link mapping from virtual network to substrate network. Particularly, for a specific virtual network request, we first sort the embedding sequence of virtual nodes according to their link resources. Then, ACS is used to embed the virtual nodes onto substrate nodes according the sorted sequence, while the virtual links are mapped via a shortest path strategy for the embedded nodes. For the first time, we propose a link resource heuristic information and incorporate it into the search process of ACS. The link resource heuristic information has two significant effects, one is to make virtual nodes tend to be embedded on the substrate nodes that cost less bandwidth, and the other is to confirm the connectivity of the substrate nodes that embed the virtual nodes. The proposed algorithm improves the optimization performance of VNE when compared with a few existing algorithms, while it substantially reduces the cost of time.

Taxi dispatch is a critical issue for taxi company to consider in modern life. This paper formulates the problem into a taxi-passenger matching model and proposes a parallel ant colony optimization algorithm to optimize the model. As the search space is large, we develop a region-dependent decomposition strategy to divide and conquer the problem. To keep the global performance, a critical region is defined to deal with the communications and interactions between the subregions. The experimental results verify that the proposed algorithm is effective, efficient, and extensible, which outperforms the traditional global perspective greedy algorithm in terms of both accuracy and efficiency.

Superpixel segmentation targets at grouping pixels in an image into atomic regions that align well with the natural object boundaries. In this paper, we propose a novel superpixel segmentation method based on an iterative and adaptive clustering algorithm that embraces color, contour, texture, and spatial features together. The algorithm adjusts the weights of different features automatically in a content-aware way, so as to fit the requirements of various image instances. More specifically, in each iteration, the weights in the aggregation function are adjusted according to the discriminabilities of features in the current working scenario. This way, the algorithm not only possesses improved robustness but also relieves the burden of setting the parameters manually. Experimental verification shows that the algorithm outperforms existing peer algorithms in terms of commonly used evaluation metrics, while using a low computational cost.

Multiclass classification is one of the most fundamental tasks in data mining. However, traditional data mining methods rely on the model assumption, they generally can suffer from the overfitting problem on high dimension and low sample size (HDLSS) data. Trying to address multiclass classification problems on HDLSS data from another perspective, we utilize Genetic Programming (GP), an intrinsic evolutionary classification algorithm that can implement feature construction automatically without model assumption. This paper develops an ensemble-based genetic programming classification framework, the Sigmoid-based Ensemble Gene Expression Programming (SEGEP). To relieve the problem of output conflict in GP-based multiclass classifiers, the proposed method employs a flexible probability representation with continuous relaxation to better integrate the output of all the binary classifiers, an effective data division strategy to further enhance the ensemble performance, and a novel sampling strategy to refine the existing GP-based binary classifier. The experiment results indicate that SE-GEP can attain better classification accuracy compared to other GP methods. Moreover, the comparison with other representative machine learning methods indicates that SE-GEP is a competitive method for multiclass classification in HDLSS data.

Operating mode scheduling is crucial for the lifetime of wireless sensor networks. However, the growing scale of networks has made such a scheduling problem more and more challenging, as existing set cover and evolutionary algorithms become unable to provide satisfactory efficiency due to the curse of dimensionality. In this paper, a Kuhn-Munkres parallel genetic algorithm is developed to solve the set cover problem and is applied to lifetime maximization of large-scale wireless sensor networks. The proposed algorithm schedules the sensors into a number of disjoint complete cover sets and activates them in batch for energy conservation. It uses a divide-and-conquer strategy of dimensionality reduction, and the polynomial Kuhn-Munkres algorithm are hence adopted to splice the feasible solutions obtained in each subarea to enhance the search efficiency substantially. To further improve global efficiency, a redundant-trend sensor schedule strategy is developed. Additionally, we meliorate the evaluation function through penalizing incomplete cover sets, which speeds up convergence. Eight types of experiments are conducted on a distributed platform to test and inform the effectiveness of the proposed algorithm. The results show that it offers promising performance in terms of the convergence rate, solution quality, and success rate.

The rapid development of radio frequency identification (RFID) technology creates the challenge of optimal deployment of an RFID network. The RFID network planning (RNP) problem involves many constraints and objectives and has been proven to be NP-hard. The use of evolutionary computation (EC) and swarm intelligence (SI) for solving RNP has gained significant attention in the literature, but the algorithms proposed have seen difficulties in adjusting the number of readers deployed in the network. However, the number of deployed readers has an enormous impact on the network complexity and cost. In this paper, we develop a novel particle swarm optimization (PSO) algorithm with a tentative reader elimination (TRE) operator to deal with RNP. The TRE operator tentatively deletes readers during the search process of PSO and is able to recover the deleted readers after a few generations if the deletion lowers tag coverage. By using TRE, the proposed algorithm is capable of adaptively adjusting the number of readers used in order to improve the overall performance of RFID network. Moreover, a mutation operator is embedded into the algorithm to improve the success rate of TRE. In the experiment, six RNP benchmarks and a real-world RFID working scenario are tested and four algorithms are implemented and compared. Experimental results show that the proposed algorithm is capable of achieving higher coverage and using fewer readers than the other algorithms.

Evolutionary computation (EC) is a kind of optimization methodology inspired by the mechanisms of biological evolution and behaviors of living organisms. In the literature, the terminology evolutionary algorithms is frequently treated the same as EC. This article focuses on making a survey of researches based on using ML techniques to enhance EC algorithms. In the framework of an ML-technique enhanced-EC algorithm (MLEC), the main idea is that the EC algorithm has stored ample data about the search space, problem features, and population information during the iterative search process, thus the ML technique is helpful in analyzing these data for enhancing the search performance. The paper presents a survey of five categories: ML for population initialization, ML for fitness evaluation and selection, ML for population reproduction and variation, ML for algorithm adaptation, and ML for local search.

The subgraph isomorphism problems, which aim to map subgraphs to a given graph, are widely seen in many applications and are usually nondeterministic polynomial-time complete (NP-complete). As a representative extension of the subgraph isomorphism problem, virtual network embedding (VNE) is a key problem in datacenter scheduling and network virtualization. Existing metaheuristic approaches to VNE problems tend to schedule networks as a whole. But when the problem scale grows, the performance of these approaches may degenerate due to the curse of dimensionality. In this article, we intend to propose a divide-and-conquer evolutionary algorithm with overlapping decomposition (ODEA) to solve large-scale VNE problems. First, realizing the fact that the decision variables in graph-based optimization problems like VNE are usually nonseparable, an overlapping decomposition method is introduced by investigating the characteristic of the network structure. In this method, the critical elements which have tight connections to many other nodes can belong to multiple subcomponents. As a result, the decision variables with tight connections can always be evolved together in multiple subcomponents. Second, to combine the subsolutions into a complete feasible solution, a competitive strategy is devised. Through the competition among critical elements, the optimizing information is shared among subcomponents, which can further improve the effectiveness of ODEA. The proposed ODEA can adopt different metaheuristics as the optimizer, and we conduct experiments on both the scenarios with a single virtual network and with a series of online networks. The experimental results verify that ODEA can significantly improve the performance of different metaheuristics in large-scale VNE problems.

Locating multiple optima of a problem is an important and challenging task for many real-world applications. In this paper, a random walk mutation strategy is proposed for differential evolution (DE) to handle multimodal optimization problems. The mutation strategy is able to find a balance between exploitation and exploration. First, the neighborhood and fitness information of individuals is incorporated into mutation to guide the formation of donor vectors. This facilitates the evolution of individuals toward their nearby optima. Second, the exploration ability of the mutation strategy is preserved by simulating a random walk process. Moreover, an archive technique is designed to detect converged subpopulations. The converged individuals are then reinitialized to search for other optima. This enhance the algorithm's exploration ability. Meanwhile, found optima can be maintained throughout the optimization process by using the archive technique. The random walk mutation strategy and the archive technique are integrated with DE to make a competitive multimodal algorithm. The resulting algorithm is tested on a recently proposed benchmark function set. Experimental results show that the proposed algorithm is able to provide better performance than a number of state-of-the-art multimodal algorithms.

Multimodal optimization amounts to finding multiple optima of a problem. In recent years, particle swarm optimization (PSO) algorithms have been widely used by the evolutionary computation community to tackle multimodal problems. However, the capability of using a suitable PSO communication topology to induce stable niching behavior has not been well explored. In this paper, we propose a minimum spanning tree (MST) topology for PSO to solve multimodal problems. In each iteration, a minimum spanning tree is built based on the configuration of particles. The neighbors of each particle are determined according to the MST. The MST topology is able to capture the distribution of particles using a small number of edges. Moreover, a number of max weighted edges in the MST are cut to avoid the genetic drift phenomenon and to enhance the niching performance. The proposed topology is integrated with a canonical PSO and a locally informed particle optimizer (LIPS) to tackle multimodal problems. Experiments have been conducted on the CEC2013 benchmark functions to test the performance the integrated algorithms. Experimental results show that PSOs with MST topology are very effective in solving multimodal problems.

Existing multiobjective evolutionary algorithms (MOEAs) tackle a multiobjective problem either as a whole or as several decomposed single-objective sub-problems. Though the problem decomposition approach generally converges faster through optimizing all the sub-problems simultaneously, there are two issues not fully addressed, i.e., distribution of solutions often depends on a priori problem decomposition, and the lack of population diversity among sub-problems. In this paper, a MOEA with double-level archives is developed. The algorithm takes advantages of both the multiobjective-problem-level and the sub-problem-level approaches by introducing two types of archives, i.e., the global archive and the sub-archive. In each generation, self-reproduction with the global archive and cross-reproduction between the global archive and sub-archives both breed new individuals. The global archive and sub-archives communicate through cross-reproduction, and are updated using the reproduced individuals. Such a framework thus retains fast convergence, and at the same time handles solution distribution along Pareto front (PF) with scalability. To test the performance of the proposed algorithm, experiments are conducted on both the widely used benchmarks and a set of truly disconnected problems. The results verify that, compared with state-of-the-art MOEAs, the proposed algorithm offers competitive advantages in distance to the PF, solution coverage, and search speed.