Search

The authors present a set of new measures for comparing optimization algorithms in dynamic environments. The authors introduce a new decomposition based multi-objective genetic algorithm with adaptive multi-population strategy to address multi-objective permutation flowshop scheduling problems. The authors describe a self-adaptive fruit fly optimization algorithm for solving high-dimensional global optimization problems. [Extracted from the article]

Combining metaheuristics is a common technique that may produce high quality solutions to complex problems. In this paper, we propose a combination of Genetic Programming (GP) and Genetic Algorithm (GA) to obtain ensembles of priority rules to solve a scheduling problem, denoted (1 , C a p (t) | | ∑ T i) , on-line. In this problem, a set of jobs must be scheduled on a single machine whose capacity varies over time. The proposed approach interleaves GP and GA so that a GP is in charge of evolving single priority rules and a GA is executed after each iteration of the GP to evolve ensembles from the rules produced by the GP in this iteration, at the same time as the GP evolves the next generation of rules. Therefore, the ensembles are obtained in an anytime fashion. In the experimental study, we compare the proposed approach to a previous one in which the GP was firstly run to evolve a large pool of candidate priority rules, and then the GA was run to obtain ensembles from that pool of rules. The results of this study revealed that the ensembles produced by the interleaved combination of GP and GA are better than those obtained by the sequential combination of GP and GA. So, these results, together with the ensembles being available earlier, make this approach more appropriate to the on-line requirements of the scheduling problem. [ABSTRACT FROM AUTHOR]

Clustering algorithms have been applied to different problems in many different real-word applications. Nevertheless, each algorithm has its own advantages and drawbacks, which can result in different solutions for the same problem. Therefore, the combination of different clustering algorithms (cluster ensembles) has emerged as an attempt to overcome the limitations of each clustering technique. The use of cluster ensembles aims to combine multiple partitions generated by different clustering algorithms into a single clustering solution (consensus partition). Recently, several approaches have been proposed in the literature in order to optimize or to improve continuously the solutions found by the cluster ensembles. As a contribution to this important subject, this paper presents an investigation of five bio-inspired techniques in the optimization of cluster ensembles (Genetic Algorithms, Particle Swarm Optimization, Ant Colony Optimization, Coral Reefs Optimization and Bee Colony Optimization). In this investigation, unlike most of the existing work, an evaluation methodology for assessing three important aspects of cluster ensembles will be presented, assessing robustness, novelty and stability of the consensus partition delivered by different optimization algorithms. In order to evaluate the feasibility of the analyzed techniques, an empirical analysis will be conducted using 20 different problems and applying two different indexes in order to examine its efficiency and feasibility. Our findings indicated that the best population-based optimization method was PSO, followed by CRO, AG, BCO and ACO, for providing robust and stable consensus partitions. [ABSTRACT FROM AUTHOR]

Metaheuristics are found to be efficient in different applications where the use of exact algorithms becomes short-handed. In the last decade, many of these algorithms have been introduced and used in a wide range of applications. Nevertheless, most of those approaches share similar components leading to a concern related to their novelty or contribution. Thus, in this paper, a pool template is proposed and used to categorize algorithm components permitting to analyze them in a structured way. We exemplify its use by means of continuous optimization metaheuristics, and provide some measures and methodology to identify their similarities and novelties. Finally, a discussion at a component level is provided in order to point out possible design differences and commonalities. [ABSTRACT FROM AUTHOR]

A local optima network (LON) encodes local optima connectivity in the fitness landscape of a combinatorial optimisation problem. Recently, LONs have been studied for their fractal dimension. Fractal dimension is a complexity index where a non-integer dimension can be assigned to a pattern. This paper investigates the fractal nature of LONs and how that nature relates to metaheuristic performance on the underlying problem. We use visual analysis, correlation analysis, and machine learning techniques to demonstrate that relationships exist and that fractal features of LONs can contribute to explaining and predicting algorithm performance. The results show that the extent of multifractality and high fractal dimensions in the LON can contribute in this way when placed in regression models with other predictors. Features are also individually correlated with search performance, and visual analysis of LONs shows insight into this relationship. [ABSTRACT FROM AUTHOR]

Metaheuristics provide the means to approximately solve complex optimisation problems when exact optimisers cannot be utilised. This led to an explosion in the number of novel metaheuristics, most of them metaphor-based, using nature as a source of inspiration. Thus, keeping track of their capabilities and innovative components is an increasingly difficult task. This can be resolved by an exhaustive classification system. Trying to classify metaheuristics is common in research, but no consensus on a classification system and the necessary criteria has been established so far. Furthermore, a proposed classification system can not be deemed complete if inherently different metaheuristics are assigned to the same class by the system. In this paper we provide the basis for a new comprehensive classification system for metaheuristics. We first summarise and discuss previous classification attempts and the utilised criteria. Then we present a multi-level architecture and suitable criteria for the task of classifying metaheuristics. A classification system of this kind can solve three main problems when applied to metaheuristics: organise the huge set of existing metaheuristics, clarify the innovation in novel metaheuristics and identify metaheuristics suitable to solve specific optimisation tasks. [ABSTRACT FROM AUTHOR]

A major issue while conceiving or parameterizing an optimization heuristic is to ensure an appropriate balance between exploitation and exploration of the search. Evolution strategies and neighborhood-based metaheuristics constitute relevant high-level frameworks, which ease the problem solving but are often complex to configure. Moreover, their effective behavior, according to the particularities of the search landscapes, remains difficult to grasp. In this paper, we deeply investigate the sampled walk search algorithm, which is a local search equivalent of the (1 , λ) -evolution strategy, considering that the neighborhood relation describes mutation possibilities. We specifically designed experiments to better understand the behavior of such a strategy offering a fine way to deal with the exploration versus exploitation dilemma. The main contribution is the analysis of search trajectories by evaluating and visualizing both their width (exploration) and their height (exploitation). More generally, we aim at bringing insights about the behavior of the (1 , λ) -ES in a discrete optimization context and within a fitness landscape perspective. [ABSTRACT FROM AUTHOR]

The performance of the Gravitational Search Algorithm (GSA) depends on the gravitational constant G, which controls the balance of exploration and exploitation abilities. Improving the setting of this parameter has attracted many researchers. In this paper, we analyzed the GSA stability using the von Neumann stability criterion. First, we modeled the iterative process by a second-order differential equation and derived the first and second-order stability conditions. Then, based on these criteria, we suggested a new law to adjust the initial value of the parameter G, depending on the distance between objects and then on the search space. Some supporting simulations were carried out using different update laws of the gravitational constant (e.g., exponential, log-sigmoid, linear, and chaotic) on CEC 2017 benchmark functions in different search space dimensions. The achieved results show that the new setting leads to significantly better outcomes in high-dimensional search spaces (greater than 20). A comparison with other metaheuristics (Particle Swarm Optimization, Artificial Bee Colony, and Grey Wolf Optimizer) reveals that the new setting proffers GSA competitiveness. Tests on 23 real-world problems (CEC 2011 benchmark problems and the iron ores sintering problem) further proved all the merits of the proposed parameter setting. [ABSTRACT FROM AUTHOR]

This paper proposes a semi-self-adaptive harmony search algorithm (SSaHS) with the self-adaptive adjustment of the bandwidth and the elitist learning strategy of particle swarm optimization. SSaHS employs a self-adaptive adjusting strategy for with the difference between the maximum and minimum components in the harmony memory as the bandwidth. It can dynamically adjust the bandwidth for the specific problem to strengthen local exploitation ability and improve the accuracy of optimization results. Comparison results show that the semi-self-adaptive harmony search algorithm can find better solutions when comparing with both basic harmony search algorithm and several enhanced harmony search algorithms, including an improved harmony search, a global-best harmony search and a novel global harmony search. [ABSTRACT FROM AUTHOR]

Inspired by the phenomenon of migration of monarch butterflies, Wang et al. developed a novel promising swarm intelligence algorithm, called monarch butterfly optimization (MBO), for addressing unconstrained low-dimensional optimization problems. In this paper, we firstly extend the application area of the basic MBO to solve the constrained optimization problems. At the same time, the crossover operator originally used in evolutionary algorithms (EAs) is incorporated into the butterfly adjusting operator in order to strengthen the exploitation of the basic MBO algorithm. Furthermore, the crossover rate is self-adaptively adjusted according to the fitness of the corresponding individual instead of the fixed crossover rate used in EAs. For migration operator, only individuals having better fitness are accepted and passed to the next generation instead of accepting all the individuals in the basic MBO algorithm. After incorporated all the modifications into the basic MBO algorithm, an improved MBO algorithm with self-adaptive crossover namely SACMBO, is proposed for unstrained and constrained optimization problems. Finally, the proposed SACMBO algorithm is further used to solve 22 unstrained optimization problems (with dimension of 100, 300, 500, 1000, and 1500) and 28 constrained real-parameter optimization functions from CEC 2017 competition (with dimension of 50 and 100), respectively. The experimental results indicate that the proposed SACMBO algorithm outperforms the basic MBO and other five state-of-the-art metaheuristic algorithms. [ABSTRACT FROM AUTHOR]

This paper proposes a novel population based optimization algorithm called Andean Condor Algorithm (ACA) for solving cell formation problems. The ACA metaheuristic is inspired by the movement pattern of the Andean Condor when it searches for food. This pattern of movement corresponds to the flight distance traveled by the Andean Condor from its nest to the place where food is found. This distance varies depending on the seasons of the year. The ACA metaheuristic presents a balance of its population through a performance indicator based on the average quality of the population's fitness. This balance determines the number of Andean Condors that will perform an exploration or intensification movements. ACA metaheuristics have a flexible design. It allows to easily integrate specific heuristics according to the optimization problem to be solved. Two types of computational experiments have been performed. According to the results obtained it has been possible to determine that ACA is an algorithm with an outstanding RPD% in relation to the algorithms BAT, MBO and PSO, robust and with a convergence which tends not to be trapped in the local optimums. Besides, according to the non-parametric multiple comparison, results have been obtained in which the ACA metaheuristic has significant differences in relation to the BAT, MBO and PSO algorithms. [ABSTRACT FROM AUTHOR]

The conserved regions between genomic sequences extracted from the different species give important information about the complex regulatory mechanisms of the transcription and translation processes. However, identification of these regulatory regions that are short DNA segments and called motifs is a major challenge in bioinformatics. With the avalanche of the newly sequenced genomic data and our evolving understanding of the characteristics of the regulatory mechanisms, there is still a need for developing fast and accurate motif discovery techniques or considerably refinement on the existing models. In this paper, we presented two different Artificial Bee Colony algorithm based motif discovery techniques and investigated their serial and parallelized implementations. Experimental studies on the three real data sets showed that the proposed methods outperformed other metaheuristics in terms of similarity values of the predicted motifs. [ABSTRACT FROM AUTHOR]

As an important administrative task in the area of education, course timetabling is a complex optimization problem that is difficult to solve by conventional methods. The paper adapts a new nature-inspired metaheuristic called ecogeography-based optimization (EBO), which enhances biogeography-based optimization by equipping the population with a neighborhood structure and designing two new migration operators named global migration and local migration, to solve the university course timetabling problem (UCTP). In particular, we develop two discrete migration operators for efficiently evolving UCTP solutions based on the principle of global and local migration in EBO, and design a repair process for effectively coping with infeasible timetables. We test the discrete EBO algorithm on a set of problem instances from four universities in China, and the experimental results show that the proposed method exhibits a promising performance advantage over a number of state-of-the-art methods. [ABSTRACT FROM AUTHOR]

Single-objective continuous optimization can be challenging, especially when dealing with multimodal problems. This work sheds light on the effects that multi-objective optimization may have in the single-objective space. For this purpose, we examine the inner mechanisms of the recently developed sophisticated local search procedure SOMOGSA. This method solves multimodal single-objective continuous optimization problems based on first expanding the problem with an additional objective (e.g., a sphere function) to the bi-objective domain and subsequently exploiting local structures of the resulting landscapes. Our study particularly focuses on the sensitivity of this multiobjectivization approach w.r.t. (1) the parametrization of the artificial second objective, as well as (2) the position of the initial starting points in the search space. As SOMOGSA is a modular framework for encapsulating local search, we integrate Nelder–Mead local search as optimizer in the respective module and compare the performance of the resulting hybrid local search to its original single-objective counterpart. We show that the SOMOGSA framework can significantly boost local search by multiobjectivization. Hence, combined with more sophisticated local search and metaheuristics, this may help solve highly multimodal optimization problems in the future. [ABSTRACT FROM AUTHOR]

Meta-heuristics are powerful tools for solving optimization problems whose structural properties are unknown or cannot be exploited algorithmically. We propose such a meta-heuristic for a large class of optimization problems over discrete domains based on the particle swarm optimization (PSO) paradigm. We provide a comprehensive formal analysis of the performance of this algorithm on certain "easy" reference problems in a black-box setting, namely the sorting problem and the problem OneMax. In our analysis we use a Markov model of the proposed algorithm to obtain upper and lower bounds on its expected optimization time. Our bounds are essentially tight with respect to the Markov model. We show that for a suitable choice of algorithm parameters the expected optimization time is comparable to that of known algorithms and, furthermore, for other parameter regimes, the algorithm behaves less greedy and more explorative, which can be desirable in practice in order to escape local optima. Our analysis provides a precise insight on the tradeoff between optimization time and exploration. To obtain our results we introduce the notion of indistinguishability of states of a Markov chain and provide bounds on the solution of a recurrence equation with non-constant coefficients by integration. [ABSTRACT FROM AUTHOR]

In the growing field of swarm-based metaheuristics, it is widely agreed that the behaviour of an algorithm, in terms of a good balance of exploration and exploitation, plays an important part in its success. Despite this, the influence that the characteristics of an optimisation problem may have on the behaviour of an algorithm is largely ignored. The characteristics of an optimisation problem can be intuitively understood and quantified in terms of fitness landscapes characteristics (FLCs). Similarly, the behaviour of a swarm-based algorithm can be quantified in terms of its diversity rate-of-change (DRoC). This study investigates correlations between the FLCs of optimisation problems and the DRoCs of particle swarm optimisers. The result is a collection of findings about links between particular problem characteristics and algorithm behaviour. The approach followed in this study may also be used as a template for further studies that broaden the scope of this study. [ABSTRACT FROM AUTHOR]

Surrogate-based optimization, nature-inspired metaheuristics, and hybrid combinations have become state of the art in algorithm design for solving real-world optimization problems. Still, it is difficult for practitioners to get an overview that explains their advantages in comparison to a large number of available methods in the scope of optimization. Available taxonomies lack the embedding of current approaches in the larger context of this broad field. This article presents a taxonomy of the field, which explores and matches algorithm strategies by extracting similarities and differences in their search strategies. A particular focus lies on algorithms using surrogates, nature-inspired designs, and those created by automatic algorithm generation. The extracted features of algorithms, their main concepts, and search operators, allow us to create a set of classification indicators to distinguish between a small number of classes. The features allow a deeper understanding of components of the search strategies and further indicate the close connections between the different algorithm designs. We present intuitive analogies to explain the basic principles of the search algorithms, particularly useful for novices in this research field. Furthermore, this taxonomy allows recommendations for the applicability of the corresponding algorithms. [ABSTRACT FROM AUTHOR]

Learning enthusiasm-based Teaching Learning Based Optimization (LebTLBO) is a metaheuristic inspired by the classroom teaching and learning method of TLBO. In recent years, it has been effectively used in several applications of science and engineering. In the conventional TLBO and most of its versions, all the learners have the same probability of getting knowledge from others. LebTLBO is motivated by the different probabilities of acquiring knowledge by the learner from others and introduced a learning enthusiasm mechanism into the basic TLBO. In this work, to achieve the enhanced performance of conventional LebTLBO by balancing the exploration and exploitation capabilities, an improved LebTLBO algorithm is proposed. The exploration of LebTLBO has been enhanced by the incorporation of the Opposition Based Learning strategy. Exploitation has been improved by Local Neighborhood Search inspired by the experience of the best solution so far discovered in a local neighborhood of the present solution. On the CEC2019 benchmark functions, the suggested technique is assessed, and computational findings show that it provides promising outcomes over other algorithms. Finally, improved LebTLBO is employed in three engineering problems and the competitive findings demonstrate its potential for a real-world problem such as the localization problem in Wireless Sensor Networks. [ABSTRACT FROM AUTHOR]

In this article we present Ethane, a parallel heterogeneous metaheuristic model specifically designed for its execution on heterogeneous hardware environments. With Ethane we propose a hybrid parallel search algorithm inspired in the structure of the chemical compound of the same name, implementing a heterogeneous island model based in the structure of the chemical bonds of the ethane compound. Here we also shape a schema for describing a complete family of parallel heterogeneous metaheuristics inspired by the structure of hydrocarbons in nature, HydroCM (HydroCarbon inspired Metaheuristics), establishing a resemblance between atoms and computers, and between chemical bonds and communication links. Our goal is to gracefully match computers of different computing power to algorithms of different behavior (genetic algorithm and simulated annealing in this study), all them collaborating to solve the same problem. In addition to the nice natural metaphor we will show that Ethane, though simple, can solve search problems in a faster and more robust way than well-known panmictic and distributed algorithms very popular in the literature, as well as can achieve a better exploration/exploitation balance during the search process. [ABSTRACT FROM AUTHOR]