Wind turbine selection for wind farm layout using multi-objective evolutionary algorithms

Wind energy has become the world’s fastest growing energy source. Although wind farm layout is a well known problem, its solution used to be heuristic, mainly based on the designer experience. A key in search trend is to increase power production capacity over time. Furthermore the production of wind energy often involves uncertainties due to the stochastic nature of wind speeds. The addressed problem contains a novel aspect with respect of other wind turbine selection problems in the context of wind farm design. The problem requires selecting two different wind turbine models (from a list of 26 items available) to minimize the standard deviation of the energy produced throughout the day while maximizing the total energy produced by the wind farm. The novelty of this new approach is based on the fact that wind farms are usually built using a single model of wind turbine. This paper describes the usage of multi-objective evolutionary algorithms (MOEAs) in the context of power energy production, selecting a combination of two different models of wind turbine along with wind speeds distributed over different time spans of the day. Several MOEAs variants belonging to the most renowned and widely used algorithms such as SPEA2 NSGAII, PESA and msPEA have been investigated, tested and compared based on the data gathered from Cancun (Mexico) throughout the year of 2008. We have demonstrated the powerful of MOEAs applied to wind turbine selection problem (WTS) and estimate the mean power and the associated standard deviation considering the wind speed and the dynamics of the power curve of the turbines. Among them, the performance of PESA algorithm looks a little bit superior than the other three algorithms. In conclusion, the use of MOEAs is technically feasible and opens new perspectives for assisting utility companies in developing wind farms.     

Inferring causal networks using fuzzy cognitive maps and evolutionary algorithms with application to gene regulatory network reconstruction

Fuzzy cognitive maps have been widely used as abstract models for complex networks. Traditional ways to construct fuzzy cognitive maps rely on domain knowledge. In this paper, we propose to use fuzzy cognitive map learning algorithms to discover domain knowledge in the form of causal networks from data. More specifically, we propose to infer gene regulatory networks from gene expression data. Furthermore, a new efficient fuzzy cognitive map learning algorithm based on a decomposed genetic algorithm is developed to learn large scale networks. In the proposed algorithm, the simulation error is used as the objective function, while the model error is expected to be minimized. Experiments are performed to explore the feasibility of this approach. The high accuracy of the generated models and the approximate correlation between simulation errors and model errors suggest that it is possible to discover causal networks using fuzzy cognitive map learning. We also compared the proposed algorithm with ant colony optimization, differential evolution, and particle swarm optimization in a decomposed framework. Comparison results reveal the advantage of the decomposed genetic algorithm on datasets with small data volumes, large network scales, or the presence of noise.     

A case study on using evolutionary algorithms to optimize bakery production planning

The production of bakery goods is strictly time sensitive due to the complex biochemical processes during dough fermentation, which leads to special requirements for production planning and scheduling. Instead of mathematical methods scheduling is often completely based on the practical experience of the responsible employees in bakeries. This sometimes inconsiderate scheduling approach often leads to sub-optimal performance of companies. This paper presents the modeling of the production in bakeries as a kind of no-wait hybrid flow-shop following the definitions in Scheduling Theory, concerning the constraints and frame conditions given by the employed processes properties. Particle Swarm Optimization and Ant Colony Optimization, two widely used evolutionary algorithms for solving scheduling problems, were adapted and used to analyse and optimize the production planning of an example bakery. In combination with the created model both algorithms proved capable to provide optimized results for the scheduling operation within a predefined runtime of 15 min.     

On the impact of objective function transformations on evolutionary and black-box algorithms

Different objective functions characterize different problems. However, certain fitness transformations can lead to easier problems although they are still a model of the considered problem. In this article, the class of not worsening transformations for a simple population-based evolutionary algorithm (EA) is described completely. That is the class of functions that transfers easy problems in easy ones and difficult problems in difficult ones. Surprisingly, this class for the rank-based EA equals that for all black-box algorithms. The importance of the black-box algorithms' knowledge of the transformation is also pointed out. Hence, a comparison with the class of not worsening transformations for a similar EA which applies fitness-proportional selection, shows that is a proper superset of . Moreover, is a proper subset of the corresponding class for random search. Finally, the minimal and maximal classes of not worsening transformations are described completely, too.     

Backward-chaining evolutionary algorithms

Starting from some simple observations on a popular selection method in Evolutionary Algorithms (EAs)—tournament selection—we highlight a previously-unknown source of inefficiency. This leads us to rethink the order in which operations are performed within EAs, and to suggest an algorithm—the EA with efficient macro-selection—that avoids the inefficiencies associated with tournament selection. This algorithm has the same expected behaviour as the standard EA but yields considerable savings in terms of fitness evaluations. Since fitness evaluation typically dominates the resources needed to solve any non-trivial problem, these savings translate into a reduction in computer time. Noting the connection between the algorithm and rule-based systems, we then further modify the order of operations in the EA, effectively turning the evolutionary search into an inference process operating in backward-chaining mode. The resulting backward-chaining EA creates and evaluates individuals recursively, backward from the last generation to the first, using depth-first search and backtracking. It is even more powerful than the EA with efficient macro-selection in that it shares all its benefits, but it also provably finds fitter solutions sooner, i.e., it is a faster algorithm. These algorithms can be applied to any form of population based search, any representation, fitness function, crossover and mutation, provided they use tournament selection. We analyse their behaviour and benefits both theoretically, using Markov chain theory and space/time complexity analysis, and empirically, by performing a variety of experiments with standard and back-ward chaining versions of genetic algorithms and genetic programming.     

Comparing evolutionary algorithms and particle filters for Markerless Human Motion Capture

Markerless Human Motion Capture is the problem of determining the joints’ angles of a three-dimensional articulated body model that best matches current and past observations acquired by video cameras. The problem of Markerless Human Motion Capture is high-dimensional and requires the use of models with a considerable number of degrees of freedom to appropriately adapt to the human anatomy.Particle filters have become the most popular approach for Markerless Human Motion Capture, despite their difficulty to cope with high-dimensional problems. Although several solutions have been proposed to improve their performance, they still suffer from the curse of dimensionality. As a consequence, it is normally required to impose mobility limitations in the body models employed, or to exploit the hierarchical nature of the human skeleton by partitioning the problem into smaller ones.Evolutionary algorithms, though, are powerful methods for solving continuous optimization problems, specially the high-dimensional ones. Yet, few works have tackled Markerless Human Motion Capture using them. This paper evaluates the performance of three of the most competitive algorithms in continuous optimization – Covariance Matrix Adaptation Evolutionary Strategy, Differential Evolution and Particle Swarm Optimization – with two of the most relevant particle filters proposed in the literature, namely the Annealed Particle Filter and the Partitioned Sampling Annealed Particle Filter.The algorithms have been experimentally compared in the public dataset HumanEva-I by employing two body models with different complexities. Our work also analyzes the performance of the algorithms in hierarchical and holistic approaches, i.e., with and without partitioning the search space. Non-parametric tests run on the results have shown that: (i) the evolutionary algorithms employed outperform their particle filter counterparts in all the cases tested; (ii) they can deal with high-dimensional models thus leading to better accuracy; and (iii) the hierarchical strategy surpasses the holistic one.     

Predictive reference shaping for constrained robotic systems using evolutionary algorithms

This paper proposes a method for reducing the trajectory tracking errors of robotic systems in presence of input saturation and state constraints. Basing on a finite horizon prediction of the future evolution of the robot dynamics, the proposed device online preshapes the reference trajectory, minimizing a multi-objective cost function. The shaped reference is updated at discrete time intervals and is generated taking into account the full nonlinear robot dynamics, input and state constraints. A specialized Evolutionary Algorithm is employed as search tool for the online computation of a sub-optimal reference trajectory in the discretized space of the control alternatives. The effectiveness of the proposed method and the online computational burden are analyzed numerically in two significant robotic control problems; furthermore a comparison of the performance provided by this method and an iterative gradient-based algorithms are discussed.     

Evolving quantum circuits at the gate level with a hybrid quantum-inspired evolutionary algorithm

This paper proposes an approach to evolve quantum circuits at the gate level, based on a hybrid quantum-inspired evolutionary algorithm. This approach encodes quantum gates as integers and combines the cost and correctness of quantum circuits into the fitness function. A fast algorithm of matrix multiplication with Kronecker product has been proposed to speed up the calculation of matrix multiplication in individuals evaluation. This algorithm is shown to be better than the known best algorithm for matrix multiplication when a certain condition holds. The approach of evolving quantum circuits is validated by some experiments and the effects of some parameters are investigated. And finally, some features of the approach are also discussed.     

Optimizing self-organizing overlay network using evolutionary approach

Self-organizing overlay networks are emerging as next generation networks capable of adapting to the needs of applications at runtime. Applications performance significantly depends on the structure and behaviors of the underlying self-organizing overlay networks. To achieve desired performance, not only the logical overlay topology but also the behaviors of nodes in this overlay network need to be optimized. Moreover, self-organizing overlay networks are extremely dynamic, unreliable and often large-scale. It is therefore important to design new optimizing approaches to meet these challenges. In this paper, we present an evolutionary optimization methodology for self-organizing overlay network. The optimizations of self-organizing overlay networks are modeled as dynamically evolutionary process, in which the nodes interact with each other, change their internal structures and alter their external links to improve the collective performance. To design appropriate fitness functions and rules that guides the direction of the evolution, overlay network can reach a stable state with desired global application performance eventually. Such a methodology leads to our distributed algorithms for proximity-based overlay topology maintenance and Peer-to-Peer living media streaming, in which every node in the overlay network rewires their behaviors and connectivity according to local available information and embedded rules. These algorithms are shown to perform well using simulations.     

基于(μ+1)演化策略的多目标优化算法

使用(μ 1)演化策略求解多目标优化问题，利用群体中个体间的距离定义拥挤密度函数以衡量群体中个体的密集程度，个体适应值定义为个体的Pareto强度值和拥挤密度值之和。通过对测试函数的实验，验证了算法的可行性和有效性，该算法具有简单、稳健等特点。     

Convergence of multi-objective evolutionary algorithms to a uniformly distributed representation of the Pareto front

In evolutionary multi-objective optimization (EMO), the convergence to the Pareto set of a multi-objective optimization problem (MOP) and the diversity of the final approximation of the Pareto front are two important issues. In the existing definitions and analyses of convergence in multi-objective evolutionary algorithms (MOEAs), convergence with probability is easily obtained because diversity is not considered. However, diversity cannot be guaranteed. By combining the convergence with diversity, this paper presents a new definition for the finite representation of a Pareto set, the B-Pareto set, and a convergence metric for MOEAs. Based on a new archive-updating strategy, the convergence of one such MOEA to the B-Pareto sets of MOPs is proved. Numerical results show that the obtained B-Pareto front is uniformly distributed along the Pareto front when, according to the new definition of convergence, the algorithm is convergent.     

On the equivalences and differences of evolutionary algorithms

Evolutionary algorithms (EAs) are fast and robust computation methods for global optimization, and have been widely used in many real-world applications. We first conceptually discuss the equivalences of various popular EAs including genetic algorithm (GA), biogeography-based optimization (BBO), differential evolution (DE), evolution strategy (ES) and particle swarm optimization (PSO). We find that the basic versions of BBO, DE, ES and PSO are equal to the GA with global uniform recombination (GA/GUR) under certain conditions. Then we discuss their differences based on biological motivations and implementation details, and point out that their distinctions enhance the diversity of EA research and applications. To further study the characteristics of various EAs, we compare the basic versions and advanced versions of GA, BBO, DE, ES and PSO to explore their optimization ability on a set of real-world continuous optimization problems. Empirical results show that among the basic versions of the algorithms, BBO performs best on the benchmarks that we studied. Among the advanced versions of the algorithms, DE and ES perform best on the benchmarks that we studied. However, our main conclusion is that the conceptual equivalence of the algorithms is supported by the fact that algorithmic modifications result in very different performance levels.     

Barcode design by evolutionary computation

This paper proposes a method for generating 2-dimensional barcode incorporated some illustrations inside of the code without detracting machine-readability and stored information. We formulate the task that finding appropriate positions, scales, and angles of illustrations, photographs, logos or other image items put in QR code as an optimization problem. By using evolutionary computation algorithm, the proposed system can find positions in which given image items can be merged without damaging machine-readability. QR code is trademarked by Denso Wave, inc. This work was presented in part at the 13th International Symposium on Artificial Life and Robotics, Oita, Japan, January 31–February 2, 2008     

An efficient evolutionary algorithm for accurate polygonal approximation

An optimization problem for polygonal approximation of 2-D shapes is investigated in this paper. The optimization problem for a digital contour of N points with the approximating polygon of K vertices has a search space of C(N, K) instances, i.e., the number of ways of choosing K vertices out of N points. A genetic-algorithm-based method has been proposed for determining the optimal polygons of digital curves, and its performance is better than that of several existing methods for the polygonal approximation problems. This paper proposes an efficient evolutionary algorithm (EEA) with a novel orthogonal array crossover for obtaining the optimal solution to the polygonal approximation problem. It is shown empirically that the proposed EEA outperforms the existing genetic-algorithm-based method under the same cost conditions in terms of the quality of the best solution, average solution, variance of solutions, and the convergence speed, especially in solving large polygonal approximation problems.     

Self-adaptivity for grid applications. An Efficient Resources Selection model based on evolutionary computation algorithms

Over the last few years, the adaptation ability has become an essential characteristic for grid applications due to the fact that it allows applications to face the dynamic and changing nature of grid systems. This adaptive capability is applied within different grid processes such as resource monitoring, resource discovery, or resource selection. In this regard, the present approach provides a self-adaptive ability to grid applications, focusing on enhancing the resources selection process. This contribution proposes an Efficient Resources Selection model to determine the resources that best fit the application requirements. Hence, the model guides applications during their execution without modifying or controlling grid resources. Within the evaluation phase, the experiments were carried out in a real European grid infrastructure. Finally, the results show that not only a self-adaptive ability is provided by the model but also a reduction in the applications’ execution time and an improvement in the successfully completed tasks rate are accomplished.     

分布式进化算法的性能测试与分析

针对分布式进化算法设计过程中由于缺乏对性能影响因素的分析而导致算法无法达到预期加速比的问题,提出一种全面的性能分析方法。根据分布式进化算法的组成结构,将影响分布式进化算法性能的因素分为进化操作开销、适应值计算开销和通信开销三个部分。首先研究进化算法在不同个体编码维数下进化操作开销的特性;其次,在进化操作开销相对固定的情况下,通过使用操作系统的延时函数控制适应值计算开销,通过改变个体编码维数控制通信开销;最后,应用控制变量方法,逐一测试各因素对算法加速比的影响。实验结果展现了三种因素的相互制约关系,给出了分布式进化算法获得更好加速比的条件。     

How evolutionary algorithms are applied to statistical natural language processing

Statistical natural language processing (NLP) and evolutionary algorithms (EAs) are two very active areas of research which have been combined many times. In general, statistical models applied to deal with NLP tasks require designing specific algorithms to be trained and applied to process new texts. The development of such algorithms may be hard. This makes EAs attractive since they offer a general design, yet providing a high performance in particular conditions of application. In this article, we present a survey of many works which apply EAs to different NLP problems, including syntactic and semantic analysis, grammar induction, summaries and text generation, document clustering and machine translation. This review finishes extracting conclusions about which are the best suited problems or particular aspects within those problems to be solved with an evolutionary algorithm.     

Hybrid evolutionary algorithm and application to structural optimization

This paper introduces a new evolutionary algorithm with a globally stochastic but locally heuristic search strategy. It is implemented by incorporating a modified micro-genetic algorithm with two local optimization operators. Performance tests using two benchmarking functions demonstrate that the new algorithm has excellent convergence performance when applied to multimodal optimization problems. The number of objective function evaluations required to obtain global optima is only 3.5–3.7% of that of using the conventional micro-genetic algorithm. The new algorithm is used to optimize the design of an 18-bar truss, with the aim of minimizing its weight while meeting the stress, section area, and geometry constraints. The corresponding optimal design is obtained with considerably fewer computational operations than required for the existing algorithms.     

A mathematical framework for passenger screening optimization via a multi-objective evolutionary approach

Concerns regarding the smuggling of dangerous items into commercial flights escalated after the failed Christmas day bomber attack. As a result, the Transportation Security Agency (TSA) has strengthened its efforts to detect passengers carrying hazardous items by installing novel screening technologies and by increasing the number of random pat-downs performed at security checkpoints nationwide. However, the implementation of such measures has raised privacy and health concerns among different groups thus making the design and evaluation of new inspection strategies strongly necessary. This research presents a mathematical framework to design passenger inspection strategies that include the utilization of novel and traditional technologies (i.e. body scanners, explosive detection systems, explosive trace detectors, walk-through metal detectors, and wands) offered by multiple manufacturers, to identify three types of items: metallic, bulk explosives (i.e. plastic, liquids, gels), and traces of explosives. A multiple objective optimization model is proposed to optimize inspection security, inspection cost, and processing time; an evolutionary approach is used to solve the model. The result is a Pareto set of quasi-optimal solutions representing multiple inspection strategies. Each strategy is different in terms of: (1) configuration, (2) the screening technologies included, (3) threshold calibration, and consequently, (4) inspection security, inspection cost, and processing time.     

Tight analysis of the (1+1)-EA for the single source shortest path problem

We conduct a rigorous analysis of the (1+1) evolutionary algorithm for the single source shortest path problem proposed by Scharnow, Tinnefeld, and Wegener (The analyses of evolutionary algorithms on sorting and shortest paths problems, 2004, Journal of Mathematical Modelling and Algorithms, 3(4):349-366). We prove that with high probability, the optimization time is O(n2 max{?, log(n)}), where ? is the smallest integer such that any vertex can be reached from the source via a shortest path having at most ? edges. This bound is tight. For all values of n and ? we provide a graph with edge weights such that, with high probability, the optimization time is of order Ω(n2 max{?, log(n)}). To obtain such sharp bounds, we develop a new technique that overcomes the coupon collector behavior of previously used arguments. Also, we exhibit a simple Chernoff type inequality for sums of independent geometrically distributed random variables, and one for sequences of random variables that are not independent, but show a desired behavior independent of the outcomes of the previous random variables. We are optimistic that these tools find further applications in the analysis of evolutionary algorithms.