waashk/dblp huggingface dataset:
preventing premature convergence in a simple eda via global step size setting. when a simple real-valued estimation of distribution algorithm (eda) with gaussian model and maximum likelihood estimation of parameters is used, it converges prematurely even on the slope of the fitness function. the simplest way of preventing premature convergence by multiplying the variance estimate by a constant factor k each generation is studied. recent works have shown that when increasing the dimensionality of the search space, such an algorithm becomes very quickly unable to traverse the slope and focus to the optimum at the same time. in this paper it is shown that when isotropic distributions with gaussian or cauchy distributed norms are used, the simple constant setting of k is able to ensure a reasonable behaviour of the eda on the slope and in the valley of the fitness function at the same time.
covariance matrix adaptation revisited - the cmsa evolution strategy -. the covariance matrix adaptation evolution strategy (cma-es) rates among the most successful evolutionary algorithms for continuous parameter optimization. nevertheless, it is plagued with some drawbacks like the complexity of the adaptation process and the reliance on a number of sophisticatedly constructed strategy parameter formulae for which no or little theoretical substantiation is available. furthermore, the cma-es does not work well for large population sizes. in this paper, we propose an alternative --- simpler --- adaptation step of the covariance matrix which is closer to the "traditional" mutative self-adaptation. we compare the newly proposed algorithm, which we term the cmsa-es, with the cma-es on a number of different test functions and are able to demonstrate its superiority in particular for large population sizes.
virus evolution strategy for vehicle routing problems with time windows. this paper proposes a new solution to the vehicle routing problem with time windows using an evolution strategy adopting viral infection. the problem belongs to the np-hard class and is very difficult to solve within practical time limits using systematic optimization techniques. in conventional evolution strategies, a schema with a high degree-of-fitness produced in the process of evolution may not be inherited when the fitness of the individual containing the schema is low. the proposed method preserves the schema as a virus and uses it by the infection operation in successive generations. experimental results using extended solomon's benchmark problems with 1000 customers proved that the proposed method is superior to conventional methods in both its rates of searches and the probability of obtaining solutions.
on multiplicative noise models for stochastic search. in this paper we investigate multiplicative noise models in the context of continuous optimization. we illustrate how some intrinsic properties of the noise model imply the failure of reasonable search algorithms for locating the optimum of the noiseless part of the objective function. those findings are rigorously investigated on the (1 + 1)-es for the minimization of the noisy sphere function. assuming a lower bound on the support of the noise distribution, we prove that the (1 + 1)-es diverges when the lower bound allows to sample negative fitness with positive probability and converges in the opposite case. we provide a discussion on the practical applications and non applications of those outcomes and explain the differences with previous results obtained in the limit of infinite search-space dimensionality.
driving cars by means of genetic algorithms. the techniques and the technologies supporting automatic vehicle guidance are an important issue. automobile manufacturers view automatic driving as a very interesting product with motivating key features which allow improvement of the safety of the car, reducing emission or fuel consumption or optimizing driver comfort during long journeys. car racing is an active research field where new advances in aerodynamics, consumption and engine power are critical each season. our proposal is to research how evolutionary computation techniques can help in this field. as a first goal we want to automatically learn to drive, by means of genetic algorithms, optimizing lap times while driving through three different circuits.
approximating the knee of an mop with stochastic search algorithms. in this paper we address the problem of approximating the 'knee' of a bi-objective optimization problem with stochastic search algorithms. knees or entire knee-regions are of particular interest since such solutions are often preferred by the decision makers in many applications. here we propose and investigate two update strategies which can be used in combination with stochastic multi-objective search algorithms (e.g., evolutionary algorithms) and aim for the computation of the knee and the knee-region, respectively. finally, we demonstrate the applicability of the approach on two examples.
the generalisation ability of a selection architecture for genetic programming. as an alternative to various existing approaches to incorporating modular decomposition and reuse in genetic programming (gp), we have proposed a new method for hierarchical evolution. based on a division of the problem's test case inputs into subsets, it employs a program structure that we refer to as a selection architecture. although the performance of gp systems based on this architecture has been shown to be superior to that of conventional systems, the nature of evolved programs is radically different, leading to speculation as to how well such programs may generalise to deal with previously unseen inputs. we have therefore performed additional experimentation to evaluate the approach's generalisation ability, and have found that it seems to stand up well against standard gp in this regard.
a blend of markov-chain and drift analysis. in their seminal article [theo. comp. sci. 276(2002):51---82] droste, jansen, and wegener present the first theoretical analysis of the expected runtime of a basic direct-search heuristic with a global search operator, namely the (1+1) evolutionary algorithm (ea), for the class of linear functions over the search space {0,1} n . in a rather long and involved proof they show that, for any linear function, the expected runtime of the ea is o(nlogn), i.e., that there are two constants c and n¿ such that, for n ¿ n¿, the expected number of iterations until a global optimum is generated is bound above by c·nlogn. however, neither c nor n¿ are specified --- they would be pretty large. here we reconsider this optimization scenario to demonstrate the potential of an analytical method that makes use not only of the drift (w.r.t. a potential function, here the number of bits set correctly), but also of the distribution of the evolving candidate solution over the search space {0,1} n : an invariance property of this distribution is proved, which is then used to derive a significantly better lower bound on the drift. finally, this better estimate of the drift results in an upper bound on the expected number of iterations of 3.8 nlog2 n + 7.6log2 n for n ¿ 2.
a convergence criterion for multiobjective evolutionary algorithms based on systematic statistical testing. a systematic approach for determining the generation number at which a specific multi-objective evolutionary algorithm (moea) has converged for a given optimization problem is introduced. convergence is measured by the performance indicators generational distance, spread and hypervolume. the stochastic nature of the moea is taken into account by repeated runs per generation number which results in a highly robust procedure. for each generation number the moea is repeated a fixed number of times, and the kolmogorow-smirnov-test is used in order to decide if a significant change in performance is gained in comparison to preceding generations. a comparison of different moeas on a problem with respect to necessary generation numbers becomes possible, and the understanding of the algorithm's behaviour is supported by analysing the development of the indicator values. the procedure is illustrated by means of standard test problems.
the impact of global structure on search. population-based methods are often considered superior on multimodal functions because they tend to explore more of the fitness landscape before they converge. we show that the effectiveness of this strategy is highly dependent on a function's global structure. when the local optima are not structured in a predictable way, exploration can misguide search into sub-optimal regions. limiting exploration can result in a better non-intuitive global search strategy.
ignoble trails - where crossover is provably harmful. beginning with the early days of the genetic algorithm and the schema theorem it has often been argued that the crossover operator is the more important genetic operator. the early royal road functions were put forth as an example where crossover would excel, yet mutation based eas were subsequently shown to experimentally outperform gas with crossover on these functions. recently several new royal roads have been introduced and proved to require expected polynomial time for gas with crossover, while needing exponential time to optimize for mutation-only eas. this paper does the converse, showing proofs that gas with crossover require exponential optimization time on new ignoble trail functions while mutation based eas optimize them efficiently.
costs and benefits of tuning parameters of evolutionary algorithms. we present an empirical study on the impact of different design choices on the performance of an evolutionary algorithm (ea). four ea components are considered--parent selection, survivor selection, recombination and mutation--and for each component we study the impact of choosing the right operator, and of tuning its free parameter(s). we tune 120 different combinations of ea operators to 4 different classes of fitness landscapes, and measure the cost of tuning. we find that components differ greatly in importance. typically the choice of operator for parent selection has the greatest impact, and mutation needs the most tuning. regarding individual eas however, the impact of design choices for one component depends on the choices for other components, as well as on the available amount of resources for tuning.
combination of natural and numerical optimization methods at the example of an internal gas turbine cooling channel. iceformation phenomena can be observed in many natural and technical processes. a naturally grown ice layer aspires in steady state to a minimum of energy dissipation. driven by this goal, this phenomena can be used to optimize complex geometric configurations in a natural manner. but since this state of minimum energy dissipation is seldom the desired goal function in technical applications, this natural experimental optimization method is combined with a subsequent classical numerical optimization using evolutionary algorithms at the example of an internal cooling channel of a gas turbine blade.
evolutionary algorithms for dynamic environments: prediction using linear regression and markov chains. in this work we investigate the use of prediction mechanisms in evolutionary algorithms for dynamic environments. these mechanisms, linear regression and markov chains, are used to estimate the generation when a change in the environment will occur, and also to predict to which state (or states) the environment may change, respectively. different types of environmental changes were studied. a memory-based evolutionary algorithm empowered by these two techniques was successfully applied to several instances of the dynamic bit matching problem.
the influence of mutation on protein-ligand docking optimization: a locality analysis. evolutionary approaches to protein-ligand docking typically use a real-value encoding and mutation operators based on gaussian and cauchy distributions. the choice of mutation is important for an efficient algorithm for this problem. we investigate the effect of mutation operators by locality analysis. high locality means that small variations in the genotype imply small variations in the phenotype. results show that gaussian-based operators have stronger locality than cauchy-based ones, especially if an annealing scheme is used to control the variance.
on the use of projected gradients for constrained multiobjective optimization problems. recent works have shown how hybrid variants of gradient-based methods and evolutionary algorithms perform better than a pure evolutionary method both for single-objective and multiobjective optimization. this same idea has been used with evolutionary multiobjective optimization (emo), obtaining also very promising results. in most cases, gradient information is used as part of the mutation operator (and only for unconstrained mops), in order to move every generated point to the exact pareto front. in our approach, we use the karush-kuhn-tucker optimality condition for constrained optimization problems to combine the information provided by the gradient vector of each objective function and the gradient vectors of constraint functions to obtain a feasible movement direction in those points near the border. in our approach, gradients of the objective functions will be approximated using quadratic regressions, trying to avoid local optima. the proposed algorithm is able to converge on several nonlinear constrained multiobjective optimization problems obtained from a benchmark, consuming few objective function evaluations (between 150 and 1000). our results indicate that our proposed scheme may produce a significant reduction in the computational cost, while producing results of good quality, when it is incorporated into a hybrid moea or when it is used to seed an emo algorithm.
a simple modification in cma-es achieving linear time and space complexity. this paper proposes a simple modification of the covariance matrix adaptation evolution strategy (cma-es) for high dimensional objective functions, reducing the internal time and space complexity from quadratic to linear. the covariance matrix is constrained to be diagonal and the resulting algorithm, sep-cma-es, samples each coordinate independently. because the model complexity is reduced, the learning rate for the covariance matrix can be increased. consequently, on essentially separable functions, sep-cma-es significantly outperforms cma-es . for dimensions larger than a hundred, even on the non-separable rosenbrock function, the sep-cma-es needs fewer function evaluations than cma-es .
bio-inspired search and distributed memory formation on power-law networks. in this paper, we report a novel and efficient algorithm for searching p2p networks having a power law topology. inspired by the natural immune system, it is a completely decentralized algorithm where each peer searches by sending out random walkers to a limited number of neighbors. as it finds other peers having similar content, it restructures its own neighborhood with the objective of bringing them closer. this restructuring leads to clustering of nodes with similar content, thus forming p2p communities. alongside, the search algorithm also adapts its walk strategy in order to take advantage of the community thus formed. this search strategy is more than twice as efficient as pure random walk on the same network.
readable and accurate rulesets with orga. a key task for data mining is to produce accurate and descriptive models. `human readable' models are often necessary to enable understanding, potentially leading to further insight, and also inducing trust in the user. rules, or decision trees (if not too numerous or large) are readable, unlike, for example svm models. however, descriptiveness and accuracy normally conflict; a challenge is to find algorithms that have both high accuracy and high readability. we introduce orga (optimized ripper using genetic algorithm) which hybridizes evolutionary search with the ripper ruleset algorithm. ripper is effective at producing accurate and readable rulesets, and we show that orga provides significant further improvement. orga outperforms overall a suitable set of comparative algorithms including implementations of ripper, c4.5 and part. on a majority of the datasets, orga's outperformance of the other algorithms is spectacular, and it is rarely dominated in terms of both accuracy and readability.
mixed-integer evolution strategies with dynamic niching. mixed-integer evolution strategies (mies) are a natural extension of standard evolution strategies (es) for addressing optimization of various types of variables --- continuous, ordinal integer, and nominal discrete --- at the same time. like most evolutionary algorithms (eas), they experience problems in obtaining the global optimum in highly multimodal search landscapes. niching methods, the extension of eas to multimodal domains, are designed to treat this issue. in this study we present a dynamic niching technique for mixed-integer evolution strategies, based upon an existing es niching approach, which was developed recently and successfully applied to continuous landscapes. the new approach is based on the heterogeneous distance measure that addresses search space similarity in a way consistent with the mutation operators of the mies. we apply the proposed dynamic niching mies framework to a test-bed of artificial landscapes and show the improvement on the global convergence in comparison to the standard mies algorithm.
evolvable agents in static and dynamic optimization problems. this paper investigates the behaviour of the evolvable agent model (evag) in static and dynamic environments. the evag is a spatially structured genetic algorithm (ga) designed to work on peer-to-peer (p2p) systems in which the population structure is a small-world graph built by newscast, a p2p protocol. additionally to the profits in computing performance, evag maintains genetic diversity at the small-world relationships between individuals in a sort of social network. experiments were conducted in order to assess how evag scales on deceptive and non-deceptive trap functions. in addition, the proposal was tested on dynamic environments. the results show that the evag scales and adapts better to dynamic environments than a standard ga and an improved version of the well-known random immigrants genetic algorithm.
investigations into the effect of multiobjectivization in protein structure prediction. physics-based potential energy functions used in protein structure prediction are composed of several energy terms combined in a weighted sum. `multiobjectivization' -- splitting up the energy function into its components and optimizing the components as a vector using multiobjective methods -- may have beneficial effects for tackling these difficult problems. in this paper we investigate the hypotheses that multiobjectivization can (i) reduce the number of local optima in the landscapes, as seen by hillclimbers, and (ii) equalize the influence of different energy components that range over vastly different energy scales and hence usually swamp each other's search gradients. the investigations use models of two real molecules, the alanine dipeptide and metenkephalin under the amber99 energy function, and consider hillclimbers with a range of mutation step sizes. our findings support the hypotheses and also indicate that multiobjectivization is competitive with alternative methods of escaping local optima.
a proposal to hybridize multi-objective evolutionary algorithms with non-gradient mathematical programming techniques. the hybridization of multi-objective evolutionary algorithms (moeas) with mathematical programming techniques has gained increasing popularity in the specialized literature in the last few years. however, such hybrids normally rely on the use of gradients and, therefore, normally consume a high number of extra objective function evaluations in order to estimate the gradient information required. the use of direct (nonlinear) optimization techniques has been, however, less common in the specialized literature, although several hybrids of this sort have been proposed for single-objective evolutionary algorithms. this paper proposes a hybridization between a well-known moea (the nsga-ii) and two direct search methods (nelder and mead's method and the golden section algorithm). the aim of the proposed approach is to combine the global search mechanisms of the evolutionary algorithm with the local search mechanisms provided by the aforementioned mathematical programming techniques, such that a more efficient (i.e., with a lower number of objective function evaluations) approach can be produced.
functional-specialization multi-objective real-coded genetic algorithm: fs-moga. this paper presents a genetic algorithm (ga) for multi-objective function optimization. in multi-objective function optimization, we believe that ga should adaptively switch search strategies in the early stage and the last stage for effective search. non-biased sampling and family-wise alternation are suitable to overcome local pareto optima in the early stage of search, and extrapolation-directed sampling and population-wise alternation are effective to cover the pareto front in the last stage. these situation-dependent requests make it difficult to keep good performance through the whole search process by repeating a single strategy. we propose a new ga that switches two search strategies, each of which is specialized for global and local search, respectively. this is done by utilizing the ratio of non-dominated solutions in the population. we examine the effectiveness of the proposed method using benchmarks and a real-world problem.
when does quasi-random work?. [10,22] presented various ways for introducing quasi-random numbers or derandomization in evolution strategies, with in some cases some spectacular claims on the fact that the proposed technique was always and for all criteria better than standard mutations. we here focus on the quasi-random trick and see to which extent this technique is efficient, by an in-depth analysis including convergence rates, local minima, plateaus, non-asymptotic behavior and noise. we conclude to the very stable, efficient and straightforward applicability of quasi-random numbers in continuous evolutionary algorithms.
uncertainty handling in model selection for support vector machines. we consider evolutionary model selection for support vector machines. hold-out set-based objective functions are natural model selection criteria, and we introduce a symmetrization of the standard cross-validation approach. we propose the covariance matrix adaptation evolution strategy (cma-es) with uncertainty handling for optimizing the new randomized objective function. our results show that this search strategy avoids premature convergence and results in improved classification accuracy compared to strategies without uncertainty handling.
ea-powered basin number estimation by means of preservation and exploration. when using an evolutionary algorithm on an unknown problem, properties like the number of global/local optima must be guessed for properly picking an algorithm and its parameters. it is the aim of current paper to put forward an ea-based method for real-valued optimization to provide an estimate on the number of optima a function exhibits, or at least of the ones that are in reach for a certain algorithm configuration, at low cost. we compare against direct clustering methods applied to different stages of evolved populations; interestingly, there is a turning point (in evaluations) after which our method is clearly better, although for very low budgets, the clustering methods have advantages. consequently, it is argued in favor of further hybridizations.