386 research outputs found
An exploration-only hybrid for large scale global optimization
No full textTwo factors affect the effectiveness of exploration, the bias introduced by selection and the concurrence of exploration and exploitation. The Leaders and Followers metaheuristic was designed to reduce the bias from selection by using a two-population scheme. Minimum Population Search was designed to limit the concurrence of exploration and exploitation through the use of Thresheld Convergence in its sampling strategy. This paper presents Unbiased Exploratory Search, which combines both approaches and simultaneously addresses the effects of these two factors. An exploration-only exploitation-only hybrid is then presented using Unbiased Exploratory Search for the exploration-only phase of the hybrid. The hybrid is tested on the CEC large scale optimization benchmark
A multi-population exploration-only hybrid on CEC-2020 single objective bound constrained problems
No full textMany meta-heuristics attempt to “transition” a single algorithm from exploration to exploitation. Conversely, previous research has shown that it can be better for the two distinct tasks of exploration and exploitation to instead be performed by two distinct algorithms/mechanisms. This has led to the development of Exploration-only, Exploitation-only Hybrid search techniques. This paper presents a Multi-Population Exploration only Exploitation-only Hybrid in which exploitation occurs in one population while a global search strategy performs exploration in another population. Unlike a sequential hybrid, this hybridization allows the exploratory technique (in this case Unbiased Exploratory Search) to delay convergence (up to indefinitely) which allows the hybrid system to benefit from a large budget of function evaluations. The new hybrid is evaluated on the CEC2020 test suite in the special session and competition on single objective bound constrained numerical optimization
Machine learning for determining the transition point in hybrid metaheuristics
No full textHigh-level relay hybrids are among the most effective metaheuristics in multiple domains. However, the relay aspect of hybridization raises the problem of when to perform the transition from one algorithm to the next. This problem becomes more relevant in exploration-only exploitation-only hybrids, where each algorithm specializes in a specific task and performs rather poorly in the other. This paper presents a novel way of approaching the transition problem as a classification problem. Different classifiers are trained and tested on the MPS-CMAES hybrid; computational results are presented for the CEC'13 benchmark. The performance of the machine learning based hybrid confirms the effectiveness of the approach by achieving a significant improvement over the original hybrid
A minimum population search hybrid for large scale global optimization
No full textLarge-scale global optimization is a challenging task which is embedded in many scientific and engineering applications. Among large scale problems, multimodal functions present an exceptional challenge because of the need to promote exploration. In this paper we present a hybrid heuristic specifically designed for optimizing large scale multimodal functions. The hybrid is based on the unbiased exploration ability of Minimum Population Search. Minimum Population Search is a recently developed metaheuristic able to efficiently optimize multimodal functions. However, MPS lacks techniques for exploiting search gradients. To overcome this limitation, we combine its exploration power with the intense local search of the CMA-ES algorithm. The proposed algorithm is evaluated on the test functions provided by the LSGO competition of IEEE Congress of Evolutionary Computation (CEC 2013)
An analysis on the effect of selection on exploration in particle swarm optimization and differential evolution
No full textThe goal of exploration to produce diverse search points throughout the search space can be countered by the goal of selection to focus search around the fittest current solution(s). In the limit, if all exploratory search points are rejected by selection, then the behaviour of the metaheuristic will be equivalent to one which performs no exploration at all (e.g. hill climbing). The effects of selection on exploration are clearly important, but our review of the literature indicates limited coverage. To address this deficit, we introduce new experiments which can specifically highlight the occurrence of “failed exploration” and its effects through selection that can trap a metaheuristic in a less promising part of the search space. We subsequently propose new lines of research to reduce the effects of selection and failed exploration which we believe are distinctly different from traditional lines of research to increase (pre-selection) exploration
An LaF-CMAES hybrid for optimization in multi-modal search spaces
No full textOptimization in multi-modal search spaces requires both exploration and exploitation. The role of exploration is to find promising attraction basins, and the role of exploitation is to find the best solutions (i.e. the local optima) within these attraction basins. In many search techniques, the balance between exploration and exploitation can be adjusted by various parameter settings. An alternative approach is to develop (hybrid) techniques with distinct mechanisms for the task of exploration and the task of exploitation. We believe this second approach can be simpler and more effective. The presented LaF-CMAES hybrid involves relatively few design decisions (e.g. parameter selections), and it delivers highly competitive performance across a benchmark set of multi-modal functions
Estimation multivariate normal algorithm with threshold convergence
No full textEstimation of Distribution Algorithms (EDAs) use a subset of solutions from the current population to build a distribution function from which the next generation of solutions is created. If there is poor diversity in the current population, then there is poor diversity in the subset of solutions selected from it and in the next generation that is created from it. Like many metaheuristics, EDAs can suffer from an autocatalytic process in which convergence begets more convergence. In Thresheld Convergence, convergence is “held” back by a threshold function, and this new technique has been successfully applied to other metaheuristics to prevent autocatalytic convergence from cascading into premature convergence. In this paper, Thresheld Convergence is applied to Estimation Multivariate Normal Algorithm with a key difference: convergence is controlled in the parameter space instead of the search space. Computational results show that significant improvements can be achieved across a broad range of multimodal functions
MODEL: Multi-objective differential evolution with leadership enhancement
No full textDifferential Evolution (DE) has been successfully used to solve various complex optimization problems; however, it can suffer depending of the complexity of the problem from slow convergence due to its iterative process. The use of the leadership concept was efficiently utilized for the acceleration of Particle Swarm Optimization (PSO) in a single-objective space. The generalization of the leadership concept in multi-objective space is not trivial. Furthermore, despite the efficiency of using the leadership concept, a limited number of multi-objective metaheuristics utilize it. To address these challenges, this paper incorporates the concept of leadership in a multi-objective variant of DE by introducing it into the mutation scheme. The preliminary results are promising as MODEL outperformed the parent algorithm GDE3 and showed the highest accuracy when compared with seven other algorithms
A random walk analysis of search in metaheuristics
No full textRandom walks are a useful modeling tool for stochastic processes. The addition of model features (e.g. finite travel in one direction) can provide insight into specific practical situations (e.g. gambler's ruin). A series of random walk experiments are designed to study the effects of selection, exploration, and exploitation during the search processes of metaheuristics. We present a set of random walk conditions which leads to greater movement as the dimensionality of the sampling distributions increases. We then implement a version of Simulated Annealing in a similar search space which also achieves improving performance with increasing dimensionality. Conversely, we show that standard Particle Swarm Optimization has decreasing performance with increasing dimensionality which is consistent with the expected effects of the Curse of Dimensionality. These experiments give us insights into future methods that metaheuristics might be able to employ to defeat the Curse of Dimensionality (in globally convex, continuous domain search spaces)
- …
