This short paper contains an extended list of references to diversity preservation methodologies, classified following the taxonomy presented in a previous publication. The list has been updated according to the contr...
详细信息
ISBN:
(纸本)9781450343237
This short paper contains an extended list of references to diversity preservation methodologies, classified following the taxonomy presented in a previous publication. The list has been updated according to the contributions sent to the workshop "Measuring and Promoting Diversity in evolutionary Computation", held during the conference GECCO 2016.
SBSE researchers often use an evolutionary algorithm to solve various software engineering problems. This paper explores an alternate approach of sampling. This approach is called SWAY (Samplying WAY) and finds the (n...
详细信息
ISBN:
(纸本)9783319471068;9783319471051
SBSE researchers often use an evolutionary algorithm to solve various software engineering problems. This paper explores an alternate approach of sampling. This approach is called SWAY (Samplying WAY) and finds the (near) optimal solutions to the problem by (i) creating a larger initial population and (ii) intelligently sampling the solution space to find the best subspace. Unlike evolutionary algorithms, SWAY does not use mutation or cross-over or multi-generational reasoning to find interesting subspaces but relies on the underlying dimensions of the solution space. Experiments with Software Engineering (SE) models shows that SWAY's performance improvement is competitive with standard MOEAs while, terminating over an order of magnitude faster.
A rigorous runtime analysis of evolutionary multi-objective optimization for the classical vertex cover problem in the context of parameterized complexity analysis has been presented by Kratsch and Neumann [1]. In thi...
详细信息
ISBN:
(纸本)9783319458236;9783319458229
A rigorous runtime analysis of evolutionary multi-objective optimization for the classical vertex cover problem in the context of parameterized complexity analysis has been presented by Kratsch and Neumann [1]. In this paper, we extend the analysis to the weighted vertex cover problem and provide a fixed parameter evolutionary algorithm with respect to OPT, the cost of the optimal solution for the problem. Moreover, using a diversity mechanism, we present a multi-objective evolutionary algorithm that finds a 2-approximation in expected polynomial time.
evolutionary optimization algorithms typically use one or more parameters that control their behavior. These parameters, which are often kept constant, can be tuned to improve the performance of the algorithm on speci...
详细信息
ISBN:
(纸本)9781450342063
evolutionary optimization algorithms typically use one or more parameters that control their behavior. These parameters, which are often kept constant, can be tuned to improve the performance of the algorithm on specific problems. However, past studies have indicated that the performance can be further improved by adapting the parameters during runtime. A limitation of these studies is that they only control, at most, a few parameters, thereby missing potentially beneficial interactions between them. Instead of finding a direct control mechanism, the novel approach in this paper is to use different parameter sets in different stages of an optimization. These multiple parameter sets, which remain static within each stage, are tuned through extensive bi-level optimization experiments that approximate the optimal adaptation of the parameters. The algorithmic performance obtained with tuned multiple parameter sets is compared against that obtained with a single parameter set. For the experiments in this paper, the parameters of NSGA-II are tuned when applied to the ZDT, DTLZ and WFG test problems. The results show that using multiple parameter sets can significantly increase the performance over a single parameter set.
Clustering is a process that aims to group the similar records in one cluster and dissimilar records in different clusters. K-means is one of the most popular and well-known clustering technique for its simplicity and...
详细信息
ISBN:
(纸本)9781467386449
Clustering is a process that aims to group the similar records in one cluster and dissimilar records in different clusters. K-means is one of the most popular and well-known clustering technique for its simplicity and light weight. However, the main drawback of K-means clustering technique is that it requires a user (data miner) to estimate the number of clusters in advance. Another limitation of K-means is that it has a tendency to get stuck at local optima. In order to overcome these limitations many evolutionary algorithm based clustering techniques have been proposed since the 1990s and applied to various fields. In this paper, we present an up-to-date review of some major evolutionary algorithm based clustering techniques for the last twenty (20) years (1995 - 2015). A total of 63 ranked (i.e. based on citation reports and JCR/CORE rank) evolutionary algorithm based clustering approaches are reviewed. Maximum of the techniques do not require any user to define the number of clusters in advance. We present the limitations and advantages of some evolutionary algorithm based clustering techniques. We also present a thorough discussion and future research directions of evolutionary algorithm based clustering techniques.
An important question in evolutionary computation is how good solutions evolutionary algorithms can produce. This paper aims to provide an analytic analysis of solution quality in terms of the relative approximation e...
详细信息
ISBN:
(纸本)9781509006229
An important question in evolutionary computation is how good solutions evolutionary algorithms can produce. This paper aims to provide an analytic analysis of solution quality in terms of the relative approximation error, which is defined by the error between 1 and the approximation ratio of the solution found by an evolutionary algorithm. Since evolutionary algorithms are iterative methods, the relative approximation error is a function of generations. With the help of matrix analysis, it is possible to obtain an exact expression of such a function. In this paper, an analytic expression for calculating the relative approximation error is presented for a class of evolutionary algorithms, that is, (1+1) strictly elitist evolution algorithms. Furthermore, analytic expressions of the fitness value and the average convergence rate in each generation are also derived for this class of evolutionary algorithms. The approach is promising, and it can be extended to non-elitist or population-based algorithms too.
evolutionary algorithms are popularly used methods to estimate yield for faster convergence. Monte-Carlo is the method of choice for accurate yield estimation. Standard Monte-Carlo methods suffer from huge computation...
详细信息
ISBN:
(纸本)9781509009169
evolutionary algorithms are popularly used methods to estimate yield for faster convergence. Monte-Carlo is the method of choice for accurate yield estimation. Standard Monte-Carlo methods suffer from huge computational burden even though they are very accurate. Monte-Carlo efficiency is not high enough to use impartial for Analog Yield Optimization. Population initialization is a decisive task in evolutionary algorithms. It can strongly influence the convergence speed and also the qualities of the final solution. We propose a method to initialize population of evolutionary algorithms ESP (evolutionary algorithms with Special Sampling), ERP (evolutionary algorithms with Random Sampling) to achieve significant computational savings at no loss of accuracy. We focus on statistical variables that have a significant impact on yield. We adapt this technique used in parametric yield estimation of digital integrated circuits. This knowledge of design variables is used to initialize population that achieves faster convergence and lower error compared to random population initialization in the same simulation time.
In fighting games, players can perform many different actions at each instant of time, leading to an exponential number of possible sequences of actions. Some of these combinations can lead to unexpected behaviors, wh...
详细信息
ISBN:
(纸本)9781450342063
In fighting games, players can perform many different actions at each instant of time, leading to an exponential number of possible sequences of actions. Some of these combinations can lead to unexpected behaviors, which can compromise the game design. One example of these unexpected behaviors is the occurrence of long or infinite combos, a long sequence of actions that does not allow any reactions from the opponent. Finding these sequences is essential to ensure fairness in fighting games, but evaluating all possible sequences is a time consuming task. In this paper, we propose the use of an evolutionary algorithm to find combos on a fighting game. The main idea is to use a genetic algorithm to evolve a population composed of sequences of inputs and, using an adequate fitness function, select the ones that are more suitable to be considered combos. We performed a series of experiments and the results show that the proposed approach was not only successful in finding combos, managing to find unexpected sequences, but also superior to previous methods.
Advances in evolutionary computation have demonstrated that evolutionary algorithms (EAs) proposed in this area are a solid alternative for solving combinatorial and continuous optimization problems. Despite their suc...
详细信息
ISBN:
(纸本)9781509006229
Advances in evolutionary computation have demonstrated that evolutionary algorithms (EAs) proposed in this area are a solid alternative for solving combinatorial and continuous optimization problems. Despite their success in innumerable real-world scenarios, EAs depend on a set of input parameters that characterize their performance and need to be adjusted. In fact, identifying and setting the most appropriate parameters for an EA is a complex task, which, in some cases, can be as difficult as the optimization problem at hand. Recently, parameter tuning has attracted the interest of the research community, designing and proposing techniques that (1) help the algorithm to perform to its best, and (2), indirectly, make fairer comparisons of different methods. In this manuscript, we propose a novel offline parameter tuning algorithm based on Bayesian Optimization, a sequential design strategy for global optimization. In order to illustrate the validity of the proposed method, we considered as a case of study the Hybrid Kernel EDA, an EA that is characterized by 6 parameters. We ran the algorithm with the parameters tuned by means of Bayesian Optimization, and compared the results with those obtained by setting the parameters by hand (using some prior knowledge). Experiments were carried out on a benchmark of 60 instances of the permutation flowshop scheduling problem. Experimental results show that, in general, Hybrid Kernel EDA obtains better results when using the parameters tuned by means of Bayesian Optimization.
Although performance is important, several other issues should be taken into account when choosing a particular language for implementing an evolutionary algorithm, such as the fact that the speed of different languag...
详细信息
ISBN:
(纸本)9783319311531
Although performance is important, several other issues should be taken into account when choosing a particular language for implementing an evolutionary algorithm, such as the fact that the speed of different languages when carrying out an operation will depend on several factors, including the size of the operands, the version of the language and underlying factors such as the operating system. However, it is usual to rely on compiled languages, namely Java or C/C++, for carrying out any implementation without considering other languages or rejecting them outright on the basis of performance. Since there are a myriad of languages nowadays, it is interesting however to measure their speed when performing operations that are usual in evolutionary algorithms. That is why in this paper we have chosen three evolutionary algorithm operations: bitflip mutation, crossover and the fitness function OneMax evaluation, and measured the speed for several popular, and some not so popular, languages. Our measures confirm that, in fact, Java, C and C++ not only are the fastest, but also have a behaviour that is independent of the size of the chromosome. However, we have found other compiled language such as Go or interpreted languages such as Python to be fast enough for most purposes. Besides, these experiments show which of these measures are, in fact, the best for choosing an implementation language based on its performance.
暂无评论