evolutionary algorithms (EAs) are population-based general-purpose optimization algorithms, and have been successfully applied in real-world optimization tasks. However, previous theoretical studies often employ EAs w...
详细信息
ISBN:
(纸本)9783319462578;9783319462561
evolutionary algorithms (EAs) are population-based general-purpose optimization algorithms, and have been successfully applied in real-world optimization tasks. However, previous theoretical studies often employ EAs with only a parent or offspring population and focus on specific problems. Furthermore, they often only show upper bounds on the running time, while lower bounds are also necessary to get a complete understanding of an algorithm. In this paper, we analyze the running time of the (mu+lambda)-EA (a general population-based EA with mutation only) on the class of pseudo-Boolean functions with a unique global optimum. By applying the recently proposed switch analysis approach, we prove the lower bound Omega(n ln n + mu +lambda n ln ln n/ln n) for the first time. Particularly on the two widely-studied problems, OneMax and LeadingOnes, the derived lower bound reveals that the (mu + lambda)-EA will be slower than the (1+ 1)-EA when the population size mu or lambda is above a moderate order. Our results imply that the increase of population size, while usually desired in practice, bears the risk of increasing the lower bound of the running time and thus should be carefully considered.
In parallel to optimizing energy consumption within houses, users' comfort is increasingly considered as an essential success criterion for automated smart home solutions. From the user perspective, balancing trad...
详细信息
ISBN:
(纸本)9781509006229
In parallel to optimizing energy consumption within houses, users' comfort is increasingly considered as an essential success criterion for automated smart home solutions. From the user perspective, balancing trade-offs between energy consumption and users' comfort when scheduling home appliances is a challenging task mainly within dynamic context (energy price, budget, user preferences, energy source, etc). To address this challenge, this paper has modeled appliances scheduling as a dynamic constrained multi-objective optimization problem and have leveraged a recently introduced dynamic evolutionary algorithm for the problem resolution. Moreover, there are typically multiple inhabitants in the same home who often share context-aware applications with various individual preferences which are likely to be conflicting. We propose a new comfort function to support multi-user conflictual preferences. Our experimental results have shown that our approach has a confirmed advantage on the user comfort while coping dynamically with the context changes.
Online parameter controllers for evolutionary algorithms adjust values of parameters during the run. Recently, a new efficient parameter controller based on reinforcement learning was proposed by Karafotias et al. In ...
详细信息
ISBN:
(纸本)9781450343237
Online parameter controllers for evolutionary algorithms adjust values of parameters during the run. Recently, a new efficient parameter controller based on reinforcement learning was proposed by Karafotias et al. In this method parameter ranges are discretized into several intervals before the run. However, performing adaptive discretization during the run may increase efficiency of an evolutionary algorithm. Aleti et al. proposed another efficient controller with adaptive discretization. In this paper we propose a parameter controller based on reinforcement learning with adaptive discretization. The proposed controller is compared with the existing parameter adjusting methods on different configurations of an evolutionary algorithm. Results show that the new controller outperforms the other controllers on most of the considered test problems.
A number of papers have emerged in the last two years that apply and study asynchronous master-slave evolutionary algorithms based on a steady-state model. These efforts are largely motivated by the observation that, ...
详细信息
ISBN:
(纸本)9781450342063
A number of papers have emerged in the last two years that apply and study asynchronous master-slave evolutionary algorithms based on a steady-state model. These efforts are largely motivated by the observation that, unlike traditional (synchronous) EAs, asynchronous EAs are able to make maximal use of many parallel processors, even when some individuals evaluate more slowly than others. Asynchronous EAs do not behave the same as their synchronous counterparts, however, and as of yet there is very little theory that makes it possible to predict how they will perform on new problems. Of some concern is evidence suggesting that the steady-state versions tend to be biased toward regions of the search space where fitness evaluation is cheaper. This has led some authors to suggest a so-called 'quasi-generational' asynchronous EA as an intermediate solution that incurs neither idle time nor significant bias toward fast solutions. We perform experiments with the quasi-generational EA, and show that it does not deliver the promised bene fits: it is, in fact, just as biased toward fast solutions as the steady-state approach is, and it tends to converge even more slowly than the traditional, generational EA.
evolutionary algorithms provide reasonable speed in time for solving optimization problems. However, these approaches may stay insufficient when the problem gets bigger and needs more hardware resource. Because it is ...
详细信息
ISBN:
(纸本)9781509016792
evolutionary algorithms provide reasonable speed in time for solving optimization problems. However, these approaches may stay insufficient when the problem gets bigger and needs more hardware resource. Because it is not feasible to improve memory and computation power depending on the problem size, there is a need for developing new techniques in order to solve these optimization problems in less time with smaller error ratios. In this study, it is aimed to solve the Traveling Salesman Problem, one of the NP-complete complexity problems, by partitioning the problem with a clustering technique, K-Means, and solving these pieces with Genetic Algorithm and finally combining these solutions into one. As the experimental results suggest, in comparison to solving large scale optimization problems as single problems, solving them by partitioning them yields more convincing results in both solution quality and time. In addition, it is observed that the performance of the technique yields better as the problem size gets bigger.
evolutionary algorithms (EAs) are a kind of stochastic optimization methods, which have been testified to be powerful in solving many real-world hard problems in past decades. But till now, we are still short of effec...
详细信息
ISBN:
(纸本)9781450343237
evolutionary algorithms (EAs) are a kind of stochastic optimization methods, which have been testified to be powerful in solving many real-world hard problems in past decades. But till now, we are still short of effective methods to represent and investigate their collective behaviors in various environments, which are very useful for researchers and engineers in evolutionary Computation to understand the algorithms better. This paper is a preliminary effort to tackle above issue. We attempt to analyze the generation-wise collective behavior of EAs via an approach called feature learning. An unsupervised feature learning framework based on Slow Feature Analysis (SFA) is presented to extract discriminative features from the generation-wise collective behavior data of several EAs on various fitness landscapes, with the purpose of finding out whether there exist differences between the searching behavior of different EAs running on the same fitness landscape;and whether there are differences between the behavior of one algorithm running on different fitness landscapes. Besides, the relationship between the fitness landscape and the searching behavior of EA is also studied. In the experiments, several typical EAs and classical benchmark functions with typical landscapes are selected as the study subjects. The collective behaviors of various EAs are visualized and compared in the extracted feature space.
Artificial immune systems (AIS) are randomised search heuristics that can be applied to any kind of optimisation problem just like evolutionary algorithms (EAs). Unlike EAs their inception stems from a different natur...
详细信息
ISBN:
(纸本)9781450342063
Artificial immune systems (AIS) are randomised search heuristics that can be applied to any kind of optimisation problem just like evolutionary algorithms (EAs). Unlike EAs their inception stems from a different natural paradigm: the immune system of vertebrates instead of natural evolution. While AIS proved to be highly efficient in several application areas, so far for no classic optimisation problem it could be rigorously proven that AIS outperform EAs. We consider the B-Cell Algorithm (BCA) as an example of an artificial immune system and compare its performance with that of the (1+1) EA on a classic combinatorial optimisation problem, interval scheduling. We show that for the natural binary encoding both heuristics are not able to efficiently find an optimal solution for all instances. The (1+1) EA has exponential expected optimisation time and the BCA may never find an optimal solution. However, we also show that a natural preprocessing changes the situation dramatically. If we remove beforehand all intervals strictly containing another one, then the BCA always finds an optimal solution in polynomial expected optimisation time. The (1+1) EA remains inefficient in the worst case, still having exponential expected optimisation time. It can, however, find a 2-approximation of an optimal solution very quickly.
Factored evolutionary algorithms (FEA) have proven to be fast and efficient optimization methods, often outperforming established methods using single populations. One restriction to FEA is that it requires a central ...
详细信息
ISBN:
(纸本)9781450342063
Factored evolutionary algorithms (FEA) have proven to be fast and efficient optimization methods, often outperforming established methods using single populations. One restriction to FEA is that it requires a central communication point between all of the factors, making FEA difficult to use in completely distributed settings. The Distributed Factored evolutionary Algorithm (DFEA) relaxes this requirement on central communication by having neighboring factors communicate directly with one another. While DFEA has been effective at finding good solutions, there is often an increase in computational complexity due to the communication between factors. In previous work on DFEA, the authors required the algorithm reach full consensus between factors during communication. In this paper, we demonstrate that even without full consensus, the performance of DFEA was not statistically different on problems with low epistasis. Additionally, we found that there is a relationship between the convergence of consensus between factors and the convergence of fitness of DFEA.
Energy consumption is a matter of paramount importance in nowadays environmentally conscious society. It is also bound to be a crucial issue in light of the emergent computational environments arising from the pervasi...
详细信息
ISBN:
(纸本)9783319458236;9783319458229
Energy consumption is a matter of paramount importance in nowadays environmentally conscious society. It is also bound to be a crucial issue in light of the emergent computational environments arising from the pervasive use of networked handheld devices and wearables. evolutionary algorithms (EAs) are ideally suited for this kind of environments due to their intrinsic flexibility and adaptiveness, provided they operate on viable energy terms. In this work we analyze the energy requirements of EAs, and particularly one of their main flavours, genetic programming (GP), on several computational platforms and study the impact that parametrisation has on these requirements, paving the way for a future generation of energy-aware EAs. As experimentally demonstrated, handheld devices and tiny computer models mainly used for educational purposes may be the most energy efficient ones when looking for solutions by means of EAs.
The reduction of energy consumption is a major challenge around the world. Architectural aspects have a significant place to minimize energy consumption to the maximum level. The use of large glazed facades causes ove...
详细信息
ISBN:
(纸本)9781509006229
The reduction of energy consumption is a major challenge around the world. Architectural aspects have a significant place to minimize energy consumption to the maximum level. The use of large glazed facades causes overheating problems in certain climatic regions. Shading elements must be considered at an early stage in the design process to overcome this problem. An application of the method is presented, focusing on the horizontal louvers integrated to a building in Izmir, Turkey. The contributions of the paper can be summarized as follows. We show that most architectural design problems are basically real-parameter multi-objective constrained optimization problems. So, any type of evolutionary and swarm optimization methods can be used in this field. A multi-objective self-adaptive differential evolution algorithm (jDEMO), inspired from the DEMO algorithm from the literature with some modifications, is developed and compared to the well-known fast and nondominated sorting genetic algorithm so called NSGA-II in order to solve this complex problem and identify alternative design solutions to decision makers. Through the experimental results, we show that the proposed algorithm generated slightly better results when comparing to the NSGA-II algorithm.
暂无评论