LCS & GBML Central

Advertisement, IEEE.

The generalized quadratic multiple knapsack problem (GQMKP) extends the classical quadratic multiple knapsack problem with setups and knapsack preference of the items. The GQMKP can accommodate a number of real-life applications and is computationally difficult. In this paper, we demonstrate the interest of the memetic search approach for approximating the GQMKP by presenting a highly effective memetic algorithm (denoted by MAGQMK). The algorithm combines a backbone-based crossover operator (to generate offspring solutions) and a multineighborhood simulated annealing procedure (to find high quality local optima). To prevent premature convergence of the search, MAGQMK employs a quality-and-distance (QD) pool updating strategy. Extensive experiments on two sets of 96 benchmarks show a remarkable performance of the proposed approach. In particular, it discovers improved best solutions in 53 and matches the best known solutions for 39 other cases. A case study on a pseudo real-life problem demonstrates the efficacy of the proposed approach in practical situations. Additional analyses show the important contribution of the novel general-exchange neighborhood, the backbone-based crossover operator as well as the QD pool updating rule to the performance of the proposed algorithm.

Describes the above-named upcoming special issue or section. May include topics to be covered or calls for papers.

The minimum weight-dominating set (MWDS) problem is NP-hard and has a lot of applications in the real world. Several metaheuristic methods have been developed for solving the problem effectively, but suffering from high CPU time on large-scale instances. In this paper, we design an effective hybrid memetic algorithm (HMA) for the MWDS problem. First, the MWDS problem is formulated as a constrained 0–1 programming problem and is converted to an equivalent unconstrained 0–1 problem using an adaptive penalty function. Then, we develop a memetic algorithm for the resulting problem, which contains a greedy randomized adaptive construction procedure, a tabu local search procedure, a crossover operator, a population-updating method, and a path-relinking procedure. These strategies make a good tradeoff between intensification and diversification. A number of experiments were carried out on three types of instances from the literature. Compared with existing algorithms, HMA is able to find high-quality solutions in much less CPU time. Specifically, HMA is at least six times faster than existing algorithms on the tested instances. With increasing instance size, the CPU time required by HMA increases much more slowly than required by existing algorithms.

A minimum Manhattan distance (MMD) approach to multiple criteria decision making in multiobjective optimization problems (MOPs) is proposed. The approach selects the final solution corresponding with a vector that has the MMD from a normalized ideal vector. This procedure is equivalent to the knee selection described by a divide and conquer approach that involves iterations of pairwise comparisons. Being able to systematically assign weighting coefficients to multiple criteria, the MMD approach is equivalent to a weighted-sum (WS) approach. Because of the equivalence, the MMD approach possesses rich geometric interpretations that are considered essential in the field of evolutionary computation. The MMD approach is elegant because all evaluations can be performed by efficient matrix calculations without iterations of comparisons. While the WS approach may encounter an indeterminate situation in which a few solutions yield almost the same WS, the MMD approach is able to determine the final solution discriminately. Since existing multiobjective evolutionary algorithms aim for a posteriori decision making, i.e., determining the final solution after a set of Pareto optimal solutions is available, the proposed MMD approach can be combined with them to form a powerful solution method of solving MOPs. Furthermore, the approach enables scalable definitions of the knee and knee solutions.

Module identification or community detection in complex networks has become increasingly important in many scientific fields because it provides insight into the relationship and interaction between network function and topology. In recent years, module identification algorithms based on stochastic optimization algorithms such as evolutionary algorithms have been demonstrated to be superior to other algorithms on small- to medium-scale networks. However, the scalability and resolution limit (RL) problems of these module identification algorithms have not been fully addressed, which impeded their application to real-world networks. This paper proposes a novel module identification algorithm called cooperative co-evolutionary module identification to address these two problems. The proposed algorithm employs a cooperative co-evolutionary framework to handle large-scale networks. We also incorporate a recursive partitioning scheme into the algorithm to effectively address the RL problem. The performance of our algorithm is evaluated on 12 benchmark complex networks. As a medical application, we apply our algorithm to identify disease modules that differentiate low- and high-grade glioma tumors to gain insights into the molecular mechanisms that underpin the progression of glioma. Experimental results show that the proposed algorithm has a very competitive performance compared with other state-of-the-art module identification algorithms.

Most existing work on evolutionary optimization assumes that there are analytic functions for evaluating the objectives and constraints. In the real world, however, the objective or constraint values of many optimization problems can be evaluated solely based on data and solving such optimization problems is often known as data-driven optimization. In this paper, we divide data-driven optimization problems into two categories, i.e., offline and online data-driven optimization, and discuss the main challenges involved therein. An evolutionary algorithm is then presented to optimize the design of a trauma system, which is a typical offline data-driven multiobjective optimization problem, where the objectives and constraints can be evaluated using incidents only. As each single function evaluation involves a large amount of patient data, we develop a multifidelity surrogate-management strategy to reduce the computation time of the evolutionary optimization. The main idea is to adaptively tune the approximation fidelity by clustering the original data into different numbers of clusters and a regression model is constructed to estimate the required minimum fidelity. Experimental results show that the proposed algorithm is able to save up to 90% of computation time without much sacrifice of the solution quality.

This paper deals with the problem of odor source localization by designing and analyzing a cooperative control framework (CCF) for the particle swarm optimization (PSO) algorithm. The CCF consists of three items: 1) a position coordination item; 2) a velocity coordination item; and 3) a movement direction coordination item. The position coordination item is used to coordinate relative positions between particles and to improve the exploration and exploitation capabilities of particles. The velocity coordination item enables the velocities of particles to reach consensus in order to realize orderly movement behaviors of particles. The movement direction coordination item guides particles to trace plumes and to locate odor sources. Stability of dynamic systems of particles with the proposed CCF is analyzed and the corresponding stability conditions are given such that the functions of three items in the CCF are realized. The orderly movement behaviors of particles under the CCF are also investigated based on benchmark functions. Finally, the effectiveness of the PSO algorithm with the proposed CCF is illustrated for the problem of odor source localization.

Provides a listing of the editorial board, current staff, committee members and society officers.

Automatic data clustering, whose goal is to recover the proper number of clusters as well as appropriate partitioning of data sets, is a fundamental yet challenging problem in unsupervised learning. In this paper, adaptive multisubpopulation competition (AMC) and multiniche crowding are proposed and incorporated into a memetic algorithm to tackle the problem. The AMC mechanism is developed to ensure a diverse search over solution subspaces corresponding to different numbers of clusters while allowing more promising subspaces to be more intensively searched. In this mechanism, the amount of individuals to be migrated between subpopulations is adaptively controlled according to the performance of subpopulations as well as the diversity of cluster numbers in population. Further, the migration is restricted to occur between subpopulations with relatively similar performances. Additionally, subpopulations with different performances are devised to search their corresponding subspaces with different exploration powers. The adaptive multiniche crowding scheme is designed to promote a diverse search of the subspace while allowing an efficient convergence of the corresponding subpopulation. This is achieved by dynamically adjusting parameter values of a multiniche crowding method to form and maintain diverged niches of high fitness within the subpopulation. The performance of proposed algorithm has been demonstrated through a series of experiments on both artificial and real data, and compared with existing methods. The results reveal that our proposed algorithm can achieve superior clustering performance and outperform related methods.