waashk/dblp huggingface dataset:
enhancing efficiency of hierarchical boa via distance-based model restrictions. this paper analyzes the effects of restricting probabilistic models in the hierarchical bayesian optimization algorithm (hboa) by defining a distance metric over variables and disallowing dependencies between variables at distances greater than a given threshold. we argue that by using prior problem-specific knowledge, it is often possible to develop a distance metric that closely corresponds to the strength of interactions between variables. this distance metric can then be used to speed up model building in hboa. three test problems are considered: 3d ising spin glasses, random additively decomposable problems, and the minimum vertex cover.
cooperation in co-evolving networks: the prisoner's dilemma and stag-hunt games. interactions giving rise to dilemmas are widespread in society. starting from the observation that individuals interact through networks of acquaintances, we study the co-evolution of the agents' strategies and of the social network itself using two prototypical games: the prisoner's dilemma and the stag hunt. we find that cooperation and coordination can be achieved through the self-organization of the social network into strong and stable clusters of identical strategies.
age-p: a platform for open evolution. smart-appliances ensembles are highly dynamic device collections in which devices can leave and join at any time without notice. due to the high system dynamics, such ensembles cannot employ standard evolutionary algorithms for their internal self-organization processes. therefore, this paper proposes a new evolutionary framework, called the appliances-go-evolution platform (age-p). the simulation experiments indicate that age-p is able to properly cope with the peculiarities of smart-appliances ensembles and that it is thus a suitable option for their self-organization processes.
modeling human expertise on a cheese ripening industrial process using gp. industrial agrifood processes often strongly rely on human expertise, expressed as know-how and control procedures based on subjective measurements (color, smell, texture), which are very difficult to capture and model. we deal in this paper with a cheese ripening process (of french camembert), for which experimental data have been collected within a cheese ripening laboratory chain. a global and a monopopulation cooperative/coevolutive gp scheme (parisian approach) have been developed in order to simulate phase prediction (i.e. a subjective estimation of human experts) from microbial proportions and ph measurements. these two gp approaches are compared to bayesian network modeling and simple multilinear learning algorithms. preliminary results show the effectiveness and robustness of the parisian gp approach.
on the behaviour of the (1+1)-es for a simple constrained problem. this paper studies the behaviour of the (1 + 1)-es when applied to a linear problem with a single linear constraint. it goes beyond previous work by considering constraint planes that do not contain the gradient direction. the behaviour of the distance of the search point from the constraint plane forms a markov chain. the limit distribution of that chain is approximated using an exponential model, and progress rates and success probabilities are derived. consequences for the working of step length adaptation mechanisms based on success probabilities are discussed.
learning fuzzy rules with evolutionary algorithms - an analytic approach. this paper provides an analytical approach to fuzzy rule base optimization. while most research in the area has been done experimentally, our theoretical considerations give new insights to the task. using the symmetry that is inherent in our formulation, we show that the problem of finding an optimal rule base can be reduced to solving a set of quadratic equations that generically have a one dimensional solution space. this alternate problem specification can enable new approaches for rule base optimization.
genetic repair for optimization under constraints inspired by arabidopsis thaliana. it has recently been proposed that the model plant, arabidopsis thaliana (thale cress), uses a newly discovered genetic repair system to repair errors at the genetic level. a. thaliana uses information from the grandparent's genes as a basis for this correction --- so genetic information appears to skip a generation. we apply this gene repair strategy to a combinatory optimization problem, firstly comparing the performance of parent and grandparent based repair. subsequent experiments expand our understanding of the generepair algorithm, by examining the parameters of fitness and direction involved in the generepair process. our results point to a tentative explanation as to why a. thaliana might have evolved such an apparently complex inheritance process.
premature convergence in constrained continuous search spaces. the optimum of numerical problems quite often lies on the constraint boundary or even in a vertex of the feasible search space. in such cases the evolutionary algorithm (ea) frequently suffers from premature convergence because of a low success probability near the constraint boundaries. we analyze premature fitness stagnation and the success rates experimentally for an ea using self-adaptive step size control. for a (1+1)-ea with a rechenberg-like step control mechanism we prove premature step size reduction at the constraint boundary. the proof is based on a success rate analysis considering a simplified mutation distribution model. from the success rates and the possible state transitions, the expected step size change can be derived at each step. we validate the theoretical model with an experimental analysis.
testing the cax on a real-world problem and other benchmarks. intrigued by the interesting context aware crossover (cax) operator proposed by majeed and ryan in a number of recent papers, this operator was tried on a real problem (solid catalysts optimisation) where unfortunately, no improvement was detected. an implementation of the benchmarks used in [mr06b] seems to show that the cax is mostly an exploitation operator, boosting the average fitness of the population.
dynamic cooperative coevolutionary sensor deployment via localized fitness evaluation. we propose an innovative cooperative co-evolutionary computation framework, dynamic cooperative coevolution (dcc), which provides dynamic coupling of neighboring species for the fitness evaluation of individuals. one feature of dcc is the utilization of local fitness to achieve a global optimum, which makes it possible for co-evolutionary algorithms to be applied in localized distributed environments, such as network computing. this work is motivated by our interest in autonomous sensor deployment, where a sensor can only communicate with those within a limited range. our experiments show that dcc is effective in obtaining good solutions under such distributed and localized conditions.
improved multilabel classification with neural networks. this paper considers the multilabel classification problem, which is a generalization of traditional two-class or multi-class classification problem. in multilabel classification a set of labels (categories) is given and each training instance is associated with a subset of this label-set. the task is to output the appropriate subset of labels (generally of unknown size) for a given, unknown testing instance. some improvements to the existing neural network multilabel classification algorithm, named bp-mll, are proposed here. the modifications concern the form of the global error function used in bp-mll. the modified classification system is tested in the domain of functional genomics, on the yeast genome data set. experimental results show that proposed modifications visibly improve the performance of the neural network based multilabel classifier. the results are statistically significant.
distance based ranking in many-objective particle swarm optimization. optimization problems with many objectives open new issues for multi-objective optimization algorithms and particularly particle swarm optimization. many of the existing algorithms are able to solve problems of low number of objectives, but as soon as we increase the number of objectives, their performances get even worse than random search methods. this paper gives an overview on multi-objective particle swarm optimization when having many objectives and parameters. furthermore, two new variants of mopso are proposed which are based on ranking of the non-dominated solutions. the proposed distance based ranking in mopso improves the quality of the solutions for even very large objective and parameter spaces. the quality of the new proposed mopso methods has been tested and compared to the random search and nsga-ii methods. the tests cover 3 to 20 objectives and 20 to 100 parameters.
a developmental approach to the uncapacitated examination timetabling problem. the paper describes a new approach, based on cell biology, to the uncapacitated examination timetabling problem. this approach begins with a single cell which is developed into a fully grown organism through the processes of cell division, cell interaction and cell migration. the mature organism represents a solution to the particular timetabling problem. the paper discusses the performance of this method on the carter set of benchmark problems. this data set is comprised of real-world timetabling problems. the results obtained using the developmental approach are compared to that obtained by other biologically inspired algorithms applied to the same set of benchmarks and the best results cited in the literature for the carter data set.
approximate solutions in space mission design. in this paper, we address multi-objective space mission design problems. we argue that it makes sense from the practical point of view to consider in addition to the `optimal' trajectories (in the pareto sense) also approximate or nearly optimal solutions since this can lead to a significant larger variety for the decision maker. for this, we suggest a novel moea which is a modification of the well-known nsga-ii algorithm equipped with a recently proposed archiving strategy which aims for the storage of the set of approximate solution of a given mop. using this algorithm we will examine several space missions and demonstrate the benefit of the novel approach.
how a generative encoding fares as problem-regularity decreases. it has been shown that generative representations, which allow the reuse of code, perform well on problems with high regularity (i.e. where a phenotypic motif must be repeated many times). to date, however, generative representations have not been tested on irregular problems. it is unknown how they will fare on problems with intermediate and low amounts of regularity. this paper compares a generative representation to a direct representation on problems that range from having multiple types of regularity to one that is completely irregular. as the regularity of the problem decreases, the performance of the generative representation degrades to, and then underperforms, the direct encoding. the degradation is not linear, however, yet tends to be consistent for different types of problem regularity. furthermore, if the regularity of each type is sufficiently high, the generative encoding can simultaneously exploit different types of regularities.
analyzing hypervolume indicator based algorithms. indicator-based methods to tackle multiobjective problems have become popular recently, mainly because they allow to incorporate user preferences into the search explicitly. multiobjective evolutionary algorithms (moeas) using the hypervolume indicator in particular showed better performance than classical moeas in experimental comparisons. in this paper, the use of indicator-based moeas is investigated for the first time from a theoretical point of view. we carry out running time analyses for an evolutionary algorithm with a (μ + 1)-selection scheme based on the hypervolume indicator as it is used in most of the recently proposed moeas. our analyses point out two important aspects of the search process. first, we examine how such algorithms can approach the pareto front. later on, we point out how they can achieve a good approximation for an exponentially large pareto front.
examining the effect of elitism in cellular genetic algorithms using two neighborhood structures. elitism has a large effect on the search ability of evolutionary algorithms. many studies, however, did not discuss its different implementations in cellular algorithms. usually a replacement policy called "replace-if-better" is applied to each cell in cellular algorithms as a kind of elitism. in this paper, we examine three implementations of elitism. one is global elitism where a prespecified number of the best individuals in the entire population are viewed as being the elite. the replace-if-better policy is applied only to the globally best individuals. another scheme is local elitism where an individual is viewed as being the elite if it is the best among its neighbors. the replace-if-better policy is applied only to the locally best individuals. the other scheme is cell-wise elitism where the replace-if-better policy is applied to all individuals. effects of elitism are examined through computational experiments using a cellular genetic algorithm with two neighborhood structures. one is for local competition among neighbors. this competition neighborhood is used in the local elitism to determine the locally best individuals. the other is for local selection of parents. this selection neighborhood is also called the mating neighborhood. since we have the two neighborhood structures, we can specify the size of the competition neighborhood for the implementation of the local elitism independent of the selection neighborhood for mating. experimental results show that the use of the replace-if-better policy at all cells is not always the best choice.
fast multi-objective scheduling of jobs to constrained resources using a hybrid evolutionary algorithm. the problem tackled here combines three properties of scheduling tasks, each of which makes the basic task more challenging: job scheduling with precedence rules, co-allocation of restricted resources of different performances and costs, and a multi-objective fitness function. as the algorithm must come up with results within a few minutes runtime, ea techniques must be tuned to this limitation. the paper describes how this was achieved and compares the results with a common scheduling algorithm, the giffler-thompson procedure.
a steady-state genetic algorithm with resampling for noisy inventory control. noisy fitness functions occur in many practical applications of evolutionary computation. a standard technique for solving these problems is fitness resampling but this may be inefficient or need a large population, and combined with elitism it may overvalue chromosomes or reduce genetic diversity. we describe a simple new resampling technique called greedy average sampling for steady-state genetic algorithms such as genitor. it requires an extra runtime parameter to be tuned, but does not need a large population or assumptions on noise distributions. in experiments on a well-known inventory control problem it performed a large number of samples on the best chromosomes yet only a small number on average, and was more effective than four other tested techniques.
convergence analysis of evolution strategies with random numbers of offspring. hitting times of the global optimum for evolutionary algorithms are usually available for simple unimodal problems or for simplified algorithms. in discrete problems, the number of results that relate the convergence rate of evolution strategies to the geometry of the optimisation landscape is restricted to a few theoretical studies. this article introduces a variant of the canonical (μ + ¿)-es, called the poisson-es, for which the number of offspring is not deterministic, but is instead sampled from a poisson distribution with mean ¿. after a slight change on the rank-based selection for the μ parents, and assuming that the number of offspring is small, we show that the convergence rate of the new algorithm is dependent on a geometric quantity that measures the maximal width of adaptive valleys. the argument of the proof is based on the analogy of the poisson-es with a basic mutation-or-selection evolutionary strategy introduced in a previous work.
an iterated local search approach for finding provably good solutions for very large tsp instances. meta-heuristics usually lack any kind of performance guarantee and therefore one cannot be certain whether the resulting solutions are (near) optimum solutions or not without relying on additional algorithms for providing lower bounds (in case of minimization).in this paper, we present a highly effective hybrid evolutionary local search algorithm based on the iterated lin-kernighan heuristic combined with a lower bound heuristic utilizing 1-trees. since both upper and lower bounds are improved over time, the gap between the two bounds is minimized by means of effective heuristics. in experiments, we show that the proposed approach is capable of finding short tours with a gap of 0.8% or less for tsp instances up to 10 million cities. hence, to the best of our knowledge, we present the first evolutionary algorithm and meta-heuristic in general that delivers provably good solutions and is highly scalable with the problem size. we show that our approach outperforms all existing heuristics for very large tsp instances.
new approaches to coevolutionary worst-case optimization. many real-world optimization problems involve uncertainty. in this paper, we consider the case of worst-case optimization, i.e., the user is interested in a solution's performance in the worst case only. if the number of possible scenarios is large, it is an optimization problem by itself to determine a solution's worst case performance. in this paper, we apply coevolutionary algorithms to co-evolve the worst case test cases along with the solution candidates. we propose a number of new variants of coevolutionary algorithms, and show that these techniques outperform previously proposed coevolutionary worst-case optimizers on some simple test problems.
use of heuristic local search for single-objective optimization in multiobjective memetic algorithms. this paper proposes an idea of using heuristic local search procedures specific for single-objective optimization in multiobjective genetic local search (mogls). a large number of local search techniques have been studied for various combinatorial optimization problems. thus we may have a situation where a powerful local search procedure specific for a particular objective is available in multiobjective optimization. such a local search procedure, however, can improve only a single objective. moreover, it may have severe side-effects on the other objectives. for example, in a scheduling problem, an insertion move of a job with the maximum delay to an earlier position in a current schedule is likely to improve only the maximum tardiness. in this paper, we assume a situation where each objective has its own heuristic local search procedure. first we explain our mogls algorithm, which is the hybridization of nsga-ii and weighted sum-based local search. next we propose an idea of using heuristic local search procedures specific for single-objective optimization in mogls. then we implement the proposed idea as a number of variants of mogls. these variants are different from each other in the choice of a heuristic local search procedure. we examine three schemes: random, probabilistic and deterministic. finally we examine the performance of each variant through computational experiments on multiobjective 0/1 knapsack problems with two, three and four objectives. it is shown that the use of heuristic local search procedures and their appropriate choice improve the performance of mogls.
the parallel predator-prey model: a step towards practical application. in this paper, we apply the parallel predator-prey model for multi-objective optimization to a combinatorial problem for the first time: exemplarily, we optimize sequences of 50 jobs for an instance of the bi-criteria scheduling problem 1|d j | ¿ c j ,l max with this approach. the modular building block architecture of the predator-prey system and the distribution of acting entities enables the analysis of separated problem knowledge and the design of corresponding variation operators. the actual modules are derived from local heuristics that tackle fractions of the complete problem. we unveil that it is possible to cover different areas of the pareto-front with special property operators and make evident that the whole front can be covered if those operators are applied simultaneously to the spatial population. further, we identify open problems that arise when the predator-prey model is applied to combinatorial problems which have not yet occurred for real-valued optimization problems.
rigorous runtime analysis of inversely fitness proportional mutation rates. artificial immune systems (ais) are an emerging new field of research in computational intelligence that are applied to many areas of application, e.g., optimization, anomaly detection and classification. for optimization tasks, the use of hypermutation operators constitutes a common concept in ais. by now, only little theoretical work has been done in this field. in this paper, we present a detailed theoretical runtime analysis that gives an insight into the dynamics of fitness based hypermutation processes. two specific mutation rates are considered using a simple immune inspired algorithm. our main focus lies thereby on the influence of parameters embedded in popular immune inspired hypermutation operators from the literature. our theoretical findings are accompanied by some empirical results.
countering poisonous inputs with memetic neuroevolution. applied to certain problems, neuroevolution frequently gets stuck in local optima with very low fitness; in particular, this is true for some reinforcement learning problems where the input to the controller is a high-dimensional and/or ill-chosen state description. evidently, some controller inputs are "poisonous", and their inclusion induce such local optima. previously, we proposed the memetic climber, which evolves neural network topology and weights at different timescales, as a solution to this problem. in this paper, we further explore the memetic climber, and introduce its population-based counterpart: the memetic es. we also explore which types of inputs are poisonous for two different reinforcement learning problems.