waashk/dblp huggingface dataset:
optimal nesting of species for exact cover: many against many. experiments with resource-defined fitness sharing (rfs) applied to shape nesting problems indicate a remarkable ability to discover exact covers of resources [1, 2]. these exact covers are represented by a maximally sized set of cooperating (non-competing) species. recent papers by horn [3, 4] introduce the first formal analyses of this empirical phenomenon. in [3], a minimal case of two species, a and b, against a third, c, is considered: the two-against-one scenario. it is shown that if the team of a and b form an exact cover, then c will be extinct at niching equilibrium. in [4], this result is generalized to the case of two-against-many: if a and b form an exact cover against an arbitrary number of competing species, under very general assumptions, a and b will be the only survivors at niching equilibirum. in the current paper, we extend these results to the most general scenario: many-against-many. we prove that, under certain very general assumptions, any size team of species forming an exact cover will dominate a population with any number of competing species: at niching equilibirum, all such competitors will be extinct. the results are more general than shape-nesting problems, applying as well to the np-complete problem exact cover by k-sets.
a scalable formal framework for analyzing the behavior of nature-inspired routing protocols. nature-inspired routing algorithms for fixed networks is an active area of research. in these algorithms, ant- or bee-agents are deployed for collecting the state of a network and providing them to autonomous and fully distributed controllers at each network node. in these routing systems the agents, through local interactions, self-organize to produce system-level behaviors which show adaptivity to changes and perturbations in the network environment. the formal modeling of such fully self-organizing, distributed and adaptive routing systems is a difficult task. in this paper, we propose a scalable formal framework that has following desirable features: (1) it models important performance metrics: throughput, delay and goodness of links, (2) it is scalable to any size of topology, (3) it is robust to changing network traffic conditions. the proposed framework is utilized to model a well-known beehive protocol which is further validated on nttnet (a 57 node topology). to the best of our knowledge, this is the first formal framework that has been validated on such a large topology.
optimizing real-time ordered-data broadcasts in pervasive environments using evolution strategy. we consider the problem of real-time data broadcast scheduling in pervasive systems with soft deadlines and constraints on the order in which data items should be broadcast to be useful. the broadcast schedule needs to be generated to provide a certain level of quality of service. thus, the real-time scheduler has to effectively trade-off between its running time and the quality of schedules generated. we use an evolution strategy to solve the problem. the variants tested includes (1 + ¿)-es, (1,¿)-es, and a (2 + 1)-es with a modified syswerda recombination operator, as well as a genetic algorithm.
evolving regular expressions for genechip probe performance prediction. affymetrix high density oligonuclotide arrays (hdona) simultaneously measure expression of thousands of genes using millions of probes. we use correlations between measurements for the same gene across 6685 human tissue samples from ncbi's geo database to indicated the quality of individual hg-u133a probes. low concordance indicates a poor probe. regular expressions can be data mined by a backus-naur form (bnf) context-free grammar using strongly typed genetic programming written in gawk and using egrep. the automatically produced motif is better at predicting poor dna sequences than an existing human generated re, suggesting runs of cytosine and guanine and mixtures should all be avoided.
testing the intermediate disturbance hypothesis: effect of asynchronous population incorporation on multi-deme evolutionary algorithms. in p2p and volunteer computing environments, resources are not always available from the beginning to the end, getting incorporated into the experiment at any moment. determining the best way of using these resources so that the exploration/exploitation balance is kept and used to its best effect is an important issue. the intermediate disturbance hypothesis states that a moderate population disturbance (in any sense that could affect the population fitness) results in the maximum ecological diversity. in the line of this hypothesis, we will test the effect of incorporation of a second population in a two-population experiment. experiments performed on two combinatorial optimization problems, mmdp and p-peaks, show that the highest algorithmic effect is produced if it is done in the middle of the evolution of the first population; starting them at the same time or towards the end yields no improvement or an increase in the number of evaluations needed to reach a solution. this effect is explained in the paper, and ascribed to the intermediate disturbance produced by first-population immigrants in the second population.
a distributed memetic algorithm for the routing and wavelength assignment problem. the routing and wavelength assignment problem deals with the routing of telecommunication traffic in all-optical networks. extending existing algorithms, we present a memetic algorithm (ma) for the static rwa by introducing a recombination operator and a scheme for distributing the computation. compared to previously achieved results for this problem, our ma significantly improves the solution quality. we find provably optimal results for previously unsolved problem instances. the distributed variant using epidemic algorithms allows to find solutions of quality comparable to the ma in less real-time.
enhancing the efficiency of the ecga. in this paper we show preliminary results of two efficiency enhancements proposed for extended compact genetic algorithm. first, a model building enhancement was used to reduce the complexity of the process from o(n 3) to o(n 2), speeding up the algorithm by 1000 times on a 4096 bits problem. then, a local-search hybridization was used to reduce the population size by at least 32 times, reducing the memory and running time required by the algorithm. these results are the first steps toward a competent and efficient genetic algorithm.
learning walking patterns for kinematically complex robots using evolution strategies. manually developing walking patterns for kinematically complex robots can be a challenging and time-consuming task. in order to automate this design process, a learning system that generates, tests, and optimizes different walking patterns is needed, as well as the ability to accurately simulate a robot and its environment. in this work, we describe a learning system that uses the cma-es method from evolutionary computation to learn walking patterns for a complex legged robot. the robot's limbs are controlled using parametrized distorted sine waves, and the evolutionary algorithm optimizes the parameters of these waveforms, testing the walking patterns in a physical simulation. the best solutions evolved by this system has been transferred to and tested on a real robot, and has resulted in a gait that is superior to those previously designed by a human designer.
a feasibility-preserving crossover and mutation operator for constrained combinatorial problems. this paper presents a feasibility-preserving crossover and mutation operator for evolutionary algorithms for constrained combinatorial problems. this novel operator is driven by an adapted pseudo-boolean solver that guarantees feasible offspring solutions. hence, this allows the evolutionary algorithm to focus on the optimization of the objectives instead of searching for feasible solutions. based on a proposed scalable testsuite, six specific testcases are introduced that allow a sound comparison of the feasibility-preserving operator to known methods. the experimental results show that the introduced approach is superior to common methods and competitive to a recent state-of-the-art decoding technique.
coevolving cellular automata with memory for chemical computing: boolean logic gates in the bz reaction. we propose that the behaviour of non-linear media can be controlled automatically through coevolutionary systems. by extension, forms of unconventional computing, i.e., massively parallel non-linear computers, can be realised by such an approach. in this study a light-sensitive sub-excitable belousov-zhabotinsky reaction is controlled using various heterogeneous cellular automata. a checkerboard image comprising of varying light intensity cells is projected onto the surface of a catalyst-loaded gel resulting in rich spatio-temporal chemical wave behaviour. the coevolved cellular automata are shown to be able to control chemical activity through dynamic control of the light intensity. the approach is demonstrated through the creation of a number of simple boolean logic gates.
evolving neural networks for online reinforcement learning. for many complex reinforcement learning problems with large and continuous state spaces, neuroevolution (the evolution of artificial neural networks) has achieved promising results. this is especially true when there is noise in sensor and/or actuator signals. these results have mainly been obtained in offline learning settings, where the training and evaluation phase of the system are separated. in contrast, in online reinforcement learning tasks where the actual performance of the systems during its learning phase matters, the results of neuroevolution are significantly impaired by its purely exploratory nature, meaning that it does not use (i. e. exploit) its knowledge of the performance of single individuals in order to improve its performance during learning. in this paper we describe modifications which significantly improve the online performance of the neuroevolutionary method evolutionary acquisition of neural topologies (eant) and discuss the results obtained on two benchmark problems.
simplified drift analysis for proving lower bounds in evolutionary computation. drift analysis is a powerful tool used to bound the optimization time of evolutionary algorithms (eas). various previous works apply a drift theorem going back to hajek in order to show exponential lower bounds on the optimization time of eas. however, this drift theorem is tedious to read and to apply since it requires two bounds on the moment-generating (exponential) function of the drift. a recent work identifies a specialization of this drift theorem that is much easier to apply. nevertheless, it is not as simple and not as general as possible. the present paper picks up hajek's line of thought to prove a drift theorem that is very easy to use in evolutionary computation. only two conditions have to be verified, one of which holds for virtually all eas with standard mutation. the other condition is a bound on what is really relevant, the drift. applications show how previous analyses involving the complicated theorem can be redone in a much simpler and clearer way. therefore, the simplified theorem is also a didactical contribution to the runtime analysis of eas.
many objective optimisation: direct objective boundary identification. this paper describes and demonstrates a new and highly innovative technique that identifies an approximation of the entire bounding surface of the feasible objective region directly, including deep concavities, disconnected regions and the edges of interior holes in the feasible areas. the pareto front is a subset of the surface of the objective boundary and can be extracted easily. importantly, if the entire objective boundary is known, breaks and discontinuities in the pareto front may be identified using automated methods; even with high objective dimensionality. this paper describes a proof-of-principle evolutionary algorithm that implements the new and unique direct objective boundary identification (dobi) method.
team algorithms based on ant colony optimization - a new multi-objective optimization approach. this paper proposes a novel team algorithm (ta) approach based on ant colony optimization (aco) for multi-objective optimization problems. the proposed method has shown a significant cooperative effect of different algorithms combined in a team of algorithms, achieving robustness in the resolution of a set of various combinatorial problems. experimentally, the proposed approach has verified a balance on different performance measures in problems as the traveling salesman problem (tsp), the quadratic assignment problem (qap) and the vehicle routing problem with time windows (vrptw). robustness and balance are achieved due to a novel classification and selection of the algorithms to be used by the team, considering pareto concept.
using ants' task division for better game engines - a contribution to game accessibility for impaired players. designing a relevant artificial intelligence engine for video games does not always consist in finding the best solution (best opponent, best path, etc.): it can sometimes consist in offering the player the best gaming experience. such a good experience is linked with the difficulty level of the proposed challenge. a game that is too easy will be boring whereas a game that is too difficult will be stressful. so, to be interesting for everyone, an artificial intelligence engine should provide an adaptive game level for every player. this game tuning is particularly prominent in the especial case of accessible games for impaired player. in this paper we show that the task division model based on ant colonies can be an interesting way to provide adaptive behaviors in game engines for simple one-player games.
parameter control methods for selection operators in genetic algorithms. parameter control is still one of the main challenges in evolutionary computation. this paper is concerned with controlling selection operators on-the-fly. we perform an experimental comparison of such methods on three groups of test functions and conclude that varying selection pressure during a ga run often yields performance benefits, and therefore is a recommended option for designers and users of evolutionary algorithms.
adaptive encoding: how to render search coordinate system invariant. this paper describes a method for rendering search coordinate system independent, adaptive encoding. adaptive encoding is applicable to any iterative search algorithm and employs incremental changes of the representation of solutions. one attractive way to change the representation in the continuous domain is derived from covariance matrix adaptation (cma). in this case, adaptive encoding recovers the cma evolution strategy, when applied to an evolution strategy with cumulative step-size control. consequently, adaptive encoding provides the means to apply cma-like representation changes to any search algorithm in the continuous domain. experimental results confirm the expectation that cma-based adaptive encoding will generally speed up a typical evolutionary algorithm on non-separable, ill-conditioned problems by orders of magnitude.
multiobjectivization by decomposition of scalar cost functions. the term `multiobjectivization' refers to the casting of a single-objec-tive optimization problem as a multiobjective one, a transformation that can be achieved by the addition of supplementary objectives or by the decomposition of the original objective function. in this paper, we analyze how multiobjectivization by decomposition changes the fitness landscape of a given problem and affects search. we find that decomposition has only one possible effect: to introduce plateaus of incomparable solutions. consequently, multiobjective hillclimbers using no archive `see' a smaller (or at most equal) number of local optima on a transformed problem compared to hillclimbers on the original problem. when archived multiobjective hillclimbers are considered this effect may partly be reversed. running time analyses conducted on four example functions demonstrate the (positive and negative) influence that both the multiobjectivization itself, and the use vs. non-use of an archive, can have on the performance of simple hillclimbers. in each case an exponential/polynomial divide is revealed.
a compass to guide genetic algorithms. parameter control is a key issue to enhance performances of genetic algorithms (ga). although many studies exist on this problem, it is rarely addressed in a general way. consequently, in practice, parameters are often adjusted manually. some generic approaches have been experimented by looking at the recent improvements provided by the operators. in this paper, we extend this approach by including operators' effect over population diversity and computation time. our controller, named compass, provides an abstraction of ga's parameters that allows the user to directly adjust the balance between exploration and exploitation of the search space. the approach is then experimented on the resolution of a classic combinatorial problem (sat).
niche radius adaptation with asymmetric sharing. in the field of genetic algorithms, niching techniques have been invented with the aim to induce speciation on multimodal fitness landscapes. unfortunately, they often rely on a problem-dependent niche radius parameter. this is the niche radius problem. in recent research, the possibilities to transfer niching techniques to the field of evolution strategies (es) have been studied. first attempts were carried out to learn a good value for the niche radius through self-adaptation. in this paper we introduce a new niching method for es with self-adaptation of the niche radius: asymmetric sharing. it is a form of fitness sharing. in contrast to earlier studies, it does not depend on coupling the niche radius to other strategy parameters. experimental results indicate that asymmetric sharing performs well in comparison to traditional sharing, without relying on problem-dependent parameters.
ga-net: a genetic algorithm for community detection in social networks. the problem of community structure detection in complex networks has been intensively investigated in recent years. in this paper we propose a genetic based approach to discover communities in social networks. the algorithm optimizes a simple but efficacious fitness function able to identify densely connected groups of nodes with sparse connections between groups. the method is efficient because the variation operators are modified to take into consideration only the actual correlations among the nodes, thus sensibly reducing the research space of possible solutions. experiments on synthetic and real life networks show the capability of the method to successfully detect the network structure.
solving three-objective optimization problems using a new hybrid cellular genetic algorithm. in this work we present a new hybrid cellular genetic algorithm. we take mocell as starting point, a multi-objective cellular genetic algorithm, and, instead of using the typical genetic crossover and mutation operators, they are replaced by the reproductive operators used in differential evolution. an external archive is used to store the nondominated solutions found during the search process and the spea2 density estimator is applied when the archive becomes full. we evaluate the resulting hybrid algorithm using a benchmark composed of three-objective test problems, and we compare the results with several state of the art multi-objective metaheuristics. the obtained results show that our proposal outperforms the other algorithms according to the two considered quality indicators.
a multiobjective evolutionary algorithm for the linear shelf space allocation problem. this paper presents a multiobjetive approach to solve the linear shelf space allocation problem (lissap), which consists on allocating lengths of shelves in a given shop to specific products or groups of products. previously we gave the first steps towards the development of a commercially viable tool that used evolutionary computation to address the problem; in this paper we introduce melissa, standing for multiobjective evolutionary linear shelf-space allocation, and test it on two real problem configurations, yielding very good results.
approximating minimum multicuts by evolutionary multi-objective algorithms. it has been shown that simple evolutionary algorithms are able to solve the minimum cut problem in expected polynomial time when using a multi-objective model of the problem. in this paper, we generalize these ideas to the np-hard minimum multicut problem. given a set of k terminal pairs, we prove that evolutionary algorithms in combination with a multi-objective model of the problem are able to obtain a k-approximation for this problem in expected polynomial time.
fitness expectation maximization. we present fitness expectation maximization (fem), a novel method for performing `black box' function optimization. fem searches the fitness landscape of an objective function using an instantiation of the well-known expectation maximization algorithm, producing search points to match the sample distribution weighted according to higher expected fitness. fem updates both candidate solution parameters and the search policy, which is represented as a multinormal distribution. inheriting em's stability and strong guarantees, the method is both elegant and competitive with some of the best heuristic search methods in the field, and performs well on a number of unimodal and multimodal benchmark tasks. to illustrate the potential practical applications of the approach, we also show experiments on finding the parameters for a controller of the challenging non-markovian double pole balancing task.
reinforcement learning: insights from interesting failures in parameter selection. we investigate reinforcement learning methods, namely the temporal difference learning td(¿) algorithm, on game-learning tasks. small modifications in algorithm setup and parameter choice can have significant impact on success or failure to learn. we demonstrate that small differences in input features influence significantly the learning process. by selecting the right feature set we found good results within only 1/100 of the learning steps reported in the literature. different metrics for measuring success in a reproducible manner are developed. we discuss why linear output functions are often preferable compared to sigmoid output functions.
adding probabilistic dependencies to the search of protein side chain configurations using edas. the problem of finding an optimal positioning for the side chain residues of a protein is called the side chain placement or side chain prediction problem. it can be posed as an optimization problem in the discrete domain. in this paper we use an estimation of distribution algorithm to address this optimization problem. using a set of 50 difficult protein instances, it is shown that the addition of dependencies between the variables in the probabilistic model can improve the quality of the solutions achieved for most of the instances considered. however, we also show that only when information about the known interactions between the residues is considered in the creation of the probabilistic model, the addition of the dependencies contributes to improve the quality of the solutions obtained.
imitation learning in uncertain environments. this paper describes a new evolutionary learning method to handle the fast adaptation of a group of agents in an uncertain environment. the method is a result of our research towards the generation of intelligent agents in computer games and is inspired by the idea of social learning or cultural evolution. thus, the agents try to adapt by the exchange of information about advantageous behaviours within the population. this paper evaluates the new approach by addressing the generation of competitive artificial players in a real-time action game.