ICEC 2010 Abstracts

Full Papers Short Papers
Full Papers
Paper Nr: 12
Title:

ACO FOR OPTIMAL SENSOR LAYOUT
Authors:

Stefka Fidanova, Pencho Marinov and Enrique Alba
Abstract: Metaheuristic methods have frequently been applied to telecommunication problems in the last years. One of these problems is Wireless Sensor Network (WSN) layout, which is an NP-hard optimization problem. The sensors sent their sensing results to a special station called the High Energy Communication Node (HECN). The sensing area of the WSN is the union of the individual sensing areas of the nodes. When deploying a WSN, the major objective is to achieve full coverage of the terrain (sensor field). Another objectives are also to use a minimum number of sensor nodes and to keep the connectivity of the network. In this paper we address a WSN layout problem in which full coverage and connectivity are treated as constraints, while objective function is the number of the sensors. To solve it we propose Ant Colony Optimization (ACO) algorithm. The terrain is modeled with 500×500 points grid and both sensing radius and communication radius are set to 30. We compare our results with existing evolutionary algorithms.
Download
Paper Nr: 24
Title:

GRAMMATICAL EVOLUTION AND THE SANTA FE TRAIL PROBLEM
Authors:

Loukas Georgiou and William J. Teahan
Abstract: In this paper we present the results of a series of experiments which explore the effectiveness of Grammatical Evolution for the Santa Fe Trail problem. The experiments which are presented support the claim of other published work that the comparison mentioned in the Grammatical Evolution literature between Grammatical Evolution (GE) and Genetic Programming (GP) regarding the Santa Fe Trail problem is not a fair one. Namely, GE literature claims that GE outperforms GP in the Santa Fe Trail problem, but we show that this happens only because the GE experiments described in the literature use a different and narrower search space. In order to perform the experiments, a series of tools and models have been developed and are presented: a) jGE, a Java implementation of the Grammatical Evolution system; b) jGE NetLogo, an extension of jGE for the NetLogo modelling environment; c) the Santa Fe Trail model, a simulation of the problem in NetLogo; and d) a NetLogo model for the execution of the experiments. Finally, we show that Grammatical Evolution is capable of finding solutions in the Santa Fe Trail problem that require fewer steps than the solutions mentioned in the GP and GE literature.
Paper Nr: 27
Title:

ALGORITHMS FOR EVOLVING NO-LIMIT TEXAS HOLD'EM POKER PLAYING AGENTS
Authors:

Garrett Nicolai and Robert Hilderman
Abstract: Computers have difficulty learning how to play Texas Hold'em Poker. The game contains a high degree of stochasticity, hidden information, and opponents that are deliberately trying to mis-represent their current state. Poker has a much larger game space than classic parlour games such as Chess and Backgammon. Evolutionary methods have been shown to find relatively good results in large state spaces, and neural networks have been shown to be able to find solutions to non-linear search problems. In this paper, we present several algorithms for teaching agents how to play No-Limit Texas Hold'em Poker using a hybrid method known as evolving neural networks. Furthermore, we adapt heuristics such as halls of fame and co-evolution to be able to handle populations of Poker agents, which can sometimes contain several hundred opponents, instead of a single opponent. Our agents were evaluated against several benchmark agents. Experimental results show the overall best performance was obtained by an agent evolved from a single population (i.e., with no co-evolution) using a large hall of fame. These results demonstrate the effectiveness of our algorithms in creating competitive No-Limit Texas Hold'em Poker agents.
Download
Paper Nr: 29
Title:

REALIZING ASSOCIATED EVOLUTION COURSES - The Co-evolution in the Artificial World of Manufacturing
Authors:

Tarek AlGeddawy and Hoda ElMaraghy
Abstract: The artificial world of products design and manufacturing technology experiences changes that result in the evolution of these entities. These changes are similar to the biological evolution process in the natural world and can be tracked similarly. The co-development behaviour in the artificial world is also noticeable, which suggests that design and technology co-evolve in a manner akin to the co-evolution of species in nature. A co-evolution model and algorithms are proposed based on Cladistics – a biological classification tool. Machine-tools development case study is presented to demonstrate the model. Results prove the model propositions and illustrate the direct co-development of design and technology.
Paper Nr: 37
Title:

COEVOLUTIONARY ARCHITECTURES WITH STRAIGHT LINE PROGRAMS FOR SOLVING THE SYMBOLIC REGRESSION PROBLEM
Authors:

Cruz Enrique Borges, César L. Alonso, José Luis Montaña, Marina de la Cruz Echeandia and Alfonso Ortega de la Puente
Abstract: To successfully apply evolutionary algorithms to the solution of increasingly complex problems we must develop effective techniques for evolving solutions in the form of interacting coadapted subcomponents. In this paper we present an architecture which involves cooperative coevolution of two subcomponents: a genetic program and an evolution strategy. As main difference with work previously done, our genetic program evolves straight line programs representing functional expressions, instead of tree structures. The evolution strategy searches for good values for the numerical terminal symbols used by those expressions. Experimentation has been performed over symbolic regression problem instances and the obtained results have been compared with those obtained by means of Genetic Programming strategies without coevolution. The results show that our coevolutionary architecture with straight line programs is capable to obtain better quality individuals than traditional genetic programming using the same amount of computational effort.
Download
Paper Nr: 39
Title:

COLLECTIVE PERCEPTION IN A SWARM OF AUTONOMOUS ROBOTS
Authors:

Giuseppe Morlino, Vito Trianni and Elio Tuci
Abstract: We present a study that aims at understanding how perception can be the result of a collective, self-organising process. A group of robots is placed in an environment characterized by black spots painted on the ground. The density of the spots can vary from trial to trial, and robots have to collectively encode such density into a coherent flashing activity. Overall, robots should prove capable of perceiving the global density by exploiting only local information and robot-robot interactions. We show how we can synthesize individual controllers that allow collective perception by exploiting evolutionary robotics techniques. This work is a first attempt to study cognitive abilities such as perception, decision-making, or attention in a synthetic setup as result of a collective, self-organising process.
Download
Paper Nr: 40
Title:

SOLVING THE RING ARC-LOADING PROBLEM USING A HYBRID SCATTER SEARCH ALGORITHM
Authors:

Anabela Moreira Bernardino, Eugénia Moreira Bernardino, Juan Manuel Sánchez-Pérez, Juan Antonio Gómez-Pulido and Miguel Angel Vega-Rodríguez
Abstract: Resilient Packet Ring (RPR) is a standard that uses Ethernet switching and a dual counter-rotating ring topology to provide SONET-like network resiliency and optimised bandwidth usage, while it delivers multipoint Ethernet/IP services. An important optimisation problem arising in this context is the Weighted Ring Arc Loading Problem (WRALP). That is the design of a direct path for each request in a communication network, in such a way that high load on the arcs will be avoided, where an arc is an edge endowed with a direction. The load of an arc is defined as the total weight of those requests routed through the arc in its direction. WRALP ask for a routing scheme such that the maximum load on the arcs will be minimum. In this paper we study the loading problem without demand splitting and for solving it we propose a Hybrid Scatter Search (HSS) algorithm. Coupled with the Scatter Search algorithm we use a Tabu Search algorithm to locate the global minimum. We show that HSS is able to achieve feasible solutions to WRALP instances, improving the results obtained by previous approaches.
Download
Paper Nr: 56
Title:

A GENERALIZED EXTREMAL OPTIMIZATION-INSPIRED ALGORITHM FOR PREDICTIVE MAINTENANCE SCHEDULING PROBLEMS
Authors:

Pasquale Arpaia, Domenico Maisto and Carlo Manna
Abstract: A bit-encoded heuristic evolutionary optimization algorithm inspired by the Generalized Extremal Optimization method is presented. The proposed evolutionary approach aims at optimizing a predictive maintenance scheduling problem characterized by an analytically intractable objective function. A preliminary comparison with a standard genetic algorithm on a set of high-dimension cases of the considered maintenance problem shows better performance for the proposed approach.
Download
Paper Nr: 60
Title:

SUBGRAPH EXTRACTION AND MEMETIC ALGORITHM FOR THE MAXIMUM CLIQUE PROBLEM
Authors:

Duc-Cuong Dang and Aziz Moukrim
Abstract: The maximum clique problem involves finding the largest set of pairwise adjacent vertices in a graph. The problem is classic but still attracts much attention because of its hardness and its prominent applications. Our work is based on the existence of an order on all the vertices whereby those belonging to a maximum clique stay close enough to each other. Such an order can be identified via the extraction of a particular subgraph from the original graph. The problem can consequently be seen as a permutation problem that can be addressed efficiently with an evolutionary-like algorithm, here we use a memetic algorithm (MA). Computational experiments conducted on DIMACS benchmark instances clearly show our MA which not only outperforms existing genetic approaches, but also compares very well to state-of-the-art algorithms.
Download
Paper Nr: 80
Title:

EXPLORING THE COMPLEXITY OF A PROPOSED RECURSIVE MEASURE OF RECOMBINATIONAL DISTANCE
Authors:

Robert Collier and Mark Wineberg
Abstract: When studying evolutionary systems, either from the natural world or artificially constructed using simulated populations, researchers must be able to quantify the genotypic differences that are observed. With the simple genetic algorithm employing both a unary mutation operator and a binary recombination operator to maintain variation in the population, it is exceedingly difficult to quantify the distance between elements of the chromosome space with an approach that is truly representative of the distance that would need to be traversed by the evolutionary mechanism. Although evaluation function dependence and the binary arity of the recombination operator both contribute to this difficulty, it is possible to redefine the function of recombination in such a way as to facilitate the computation of a more representative measurement of the distance the genetic algorithm would need to traverse to create a specific chromosome from a given population. The recursive approach presented here entails the definition of unary recombination operators and ultimately results in a technique for calculating the recombinational distance between chromosomes with a time complexity that is improved logarithmically over a simplistic approach.
Download
Paper Nr: 84
Title:

IMPROVED COMPRESSED OBJECTIVE GENETIC ALGORITHM: COGA-II
Authors:

Kittipong Boonlong, Nachol Chaiyaratana and Kuntinee Maneeratana
Abstract: This paper presents an improved version of compressed objective genetic algorithm to solve problems with a large number of objectives. The improved compressed objective genetic algorithm (COGA-II) employs a rank assignment for the screening of non-dominated solutions that best approximate the Pareto front from vast numbers of available non-dominated solutions. Since the winning non-dominated solutions are heuristically determined from the survival competition, the procedure is referred to as a winning-score based ranking mechanism. In COGA-II, an m-objective vector is transformed to only one criterion, the winning score of which assignment is improved from that of the previous version, COGA. COGA-II is subsequently benchmarked against a non-dominated sorting genetic algorithm II (NSGA-II) and an improved strength Pareto genetic algorithm (SPEA-II), in seven scalable DTLZ benchmark problems. The results reveal that for the closeness to the true Pareto front COGA-II is much better than NSGA-II, and SPEA-II. For diversity of solutions, the diversity of the solutions by COGA-II is comparable to that of SPEA-II, while NSGA-II has poor diversity. COGA-II can also prevent solutions diverging from true Pareto solutions that occur on NSGA-II and SPEA-II for problems with more than 4 objectives. Thus, it can be concluded that COGA-II is suitable for solving an optimization problem with a large number of objectives.
Download
Paper Nr: 85
Title:

INVESTIGATING REPLACEMENT STRATEGIES FOR THE ADAPTIVE DISSORTATIVE MATING GENETIC ALGORITHM
Authors:

Carlos M. Fernandes, Juan Julán Merelo and Agostinho C. Rosa
Abstract: This paper investigates the effects of modifying the Adaptive Dissortative Mating Genetic Algorithm (ADMGA) replacement strategy on the performance of the algorithm in dynamic problems. ADMGA is a variation of the standard GA with a mating restriction based on the genotypic similarity of the individuals. Dissimilar individuals mate more often than expected by chance and, as a result, genetic diversity throughout the run is maintained at a higher level. ADMGA was previously tested in dynamic optimization problems with promising results: the algorithm shows to outperform standard GAs and state-of-the-art approaches on several problems and dynamics. However, the performance of the algorithm degrades when the frequency of changes increases. Due to the premises under which ADMGA was tested, it has been argued that the replacement strategy that emerges from the algorithm’s dissortative mating strategy may be harming the performance in such situations. This study proposes alternative replacement schemes with the objective of improving ADMGA’s performance on fast changing environments (without damaging the performance on slower ones). The strategies maintain the simplicity of the algorithm, i.e., the parameter set is not increased. The replacement schemes were tested in dynamic environments based on stationary functions with different characteristics, showing to improve standard ADMGA’s performance in fast dynamic problems.
Download
Paper Nr: 86
Title:

A RECEDING HORIZON GENETIC ALGORITHM FOR DYNAMIC MULTI-TARGET ASSIGNMENT AND TRACKING - A Case Study on the Optimal Positioning of Tug Vessels along the Northern Norwegian Coast
Authors:

Robin T. Bye, Siebe B. van Albada and Harald Yndestad
Abstract: Combining methodologies from cybernetics and artificial intelligence (AI), we present a receding horizon genetic algorithm (RHGA) for solving the task of dynamic assignment and tracking of multiple targets. We demonstrate the capabilities of the algorithm by means of a case study on optimal positioning of tugs to reduce the risk of oil tanker drifting accidents along the northern Norwegian coast. Through simulations we show that the RHGA performs intelligent target assignment and close target tracking while constantly reevaluating its suggested solutions based on current and predicted information. We see great potential for further development and consider our RHGA and problem description a platform for further research.
Download
Short Papers
Paper Nr: 19
Title:

A GENETIC ALGORITHM APPROACH TO A 3D HIGHWAY ALIGNMENT DEVELOPMENT
Authors:

Botan M. Ahmad AL-Hadad and Michael Mawdesley
Abstract: This paper reports for the possibility of developing a genetic algorithm (GA) based technique model to optimize highway alignment. It suggests a novel technique to optimize a highway alignment in a three dimensional space. The technique considers station points to simultaneously configure both horizontal and vertical alignment rather than considering the existing conventional principles of design which deals with both alignments in two different stages and uses horizontal intersection points (HIP), vertical intersection points (VIP), tangents (T), curve radii (R), deflection angles (∆), grade values (± g %), and horizontal and vertical curve fittings to depict the horizontal and vertical alignments. The proposed method is expected to produce a global optimal or near optimal solution and also to reduce the number of highway alignment design elements required and consequently reduce the constraints imposed on alignment planning and design. The results obtained have good merits and encourage further investigations for better solutions.
Download
Paper Nr: 21
Title:

CONSTRAINT BASED SCHEDULING IN A GENETIC ALGORITHM FOR THE SINGLE MACHINE SCHEDULING PROBLEM WITH SEQUENCE-DEPENDENT SETUP TIMES
Authors:

Aymen Sioud, Marc Gravel and Caroline Gagné
Abstract: This paper presents a hybrid approach based on the integration between Genetic Algorithm (GA) and Constraint Based Scheduling (CBS) approaches for solving a scheduling problem. The main contributions are the integration of the CBS approach in the reproduction and the intensification processes of a GA autonomously. The proposed methodology is applied to a single machine scheduling problem with sequence-dependent setup times for the objective of minimizing the total tardiness. A sensitivity analysis of the hybrid methodology is carried out to compare the performance of the GA and the integrated GA-CBS approaches on different benchmarks from the literature.
Download
Paper Nr: 26
Title:

EXPLORATION OF QUANTITATIVE ASSESSMENT IN SYSTEMS ARCHITECTURE USING EVIDENTIAL REASONING
Authors:

Yixing Shan, Lili Yang and Roy Kalawsky
Abstract: A key issue in successful developing complex systems is how to assess the performance of architecture model during the development process. Traditional assessment techniques are subjective and usually highlight weaknesses rather than provide quantitative and objective results. In addition, the increasing complexity of systems nowadays; has led to a move from federated systems which were closed and target unique to embedded open systems, which extends new criteria to be considered in the assessment. This paper provides an insight into how Evidential Reasoning (ER) approach as the specific Multi-Attribute Decision Making (MADM) method can be used as a type of system assessment technique. The theory and implementation details of ER with an initial case study are presented.
Download
Paper Nr: 28
Title:

MULTI-OBJECTIVE OPTIMIZATION OF BOTH PUMPING ENERGY AND MAINTENANCE COSTS IN OIL PIPELINE NETWORKS USING GENETIC ALGORITHMS
Authors:

Ehsan Abbasi and Vahid Garousi
Abstract: This paper proposes an optimization model for the pipeline operation problem using a dual-objective non-dominated sorting genetic algorithm (NSGA-II). One and foremost objective is to minimize pumping energy costs. The second objective is to recognize the pipeline operators’ concern on pumps maintenance costs by reducing the number of times pumps are turned on and off. This is commonly believed as a main source of wear and tear on the pumps. The formulation of the problem is presented in detail and the model is tested on a hypothetical case study (which is based on consultation with two industrial partners). The output results are promising since they would give operators a better understanding of different optimal scenarios on a “Pareto front”. Operators can visually assess several alternatives, and analyse the cost-effectiveness of each scenario in terms of both objective functions.
Download
Paper Nr: 31
Title:

EVOLUTIONARY ALGORITHMS FOR SOLVING QUASI GEOMETRIC PROGRAMMING PROBLEMS
Authors:

R. Toscano and P. Lyonnet
Abstract: In this paper we introduce an extension of standard geometric programming (GP) problems which we call quasi geometric programming (QGP) problems. The consideration of this particular kind of nonlinear and possibly non smooth optimization problem is motivated by the fact that many engineering problems can be formulated as a QGP. However, solving a QGP remains a difficult task due to its intrinsic non-convex nature. This is why we investigate the possibility of using evolutionary algorithms (EA) for solving a QGP problem. The main idea developed in this paper is to combine evolutionary algorithms with interior point method for efficiently solving QGP problems. An interesting feature of the proposed approach is that it does not need to develop specific program solver and works well with any existing EA and available solver able to solve conventional GP. Some considerations on the robustness issue are also presented. Numerical experiments are used to validate the proposed method.
Download
Paper Nr: 35
Title:

TRAIN TIMETABLE GENERATION USING GENETIC ALGORITHMS
Authors:

C. J. Hinde, M. S. Withall, I. W. Phillips, T. W. Jackson, S. Brown and R. Watson
Abstract: The scheduling of railway trains has been a research problem for many years. Many of the choices required are not known a priori and require exploration of the problem to determine them. A modular Genetic system was designedmake the evaluation function and preparation of the timetable tractable. The Genetic system consists of a Genome, split into Chromosomes so the extra choices that become known throughout the evolution can be added to the Chromosomes. A weighted fitness function and a multiobjective non-dominated fitness function were tried, and then partial objective ranking was added. The system has tackled a mixture of problems has produced promising results.
Download
Paper Nr: 36
Title:

USING SELF-SIMILARITY TO ADAPT EVOLUTIONARY ENSEMBLES FOR THE DISTRIBUTED CLASSIFICATION OF DATA STREAMS
Authors:

Clara Pizzuti and Giandomenico Spezzano
Abstract: Distributed stream-based classification methods have many important applications such as sensor data analysis, network security, and business intelligence. An important challenge is to address the issue of concept drift in the data stream environment, which is not easily handled by the traditional learning techniques. This paper presents a Genetic Programming (GP) based boosting ensemble method for the classification of distributed streaming data able to adapt in presence of concept drift. The approach handles flows of data coming from multiple locations by building a global model obtained by the aggregation of the local models coming from each node. The algorithm uses a fractal dimension-based change detection strategy, based on self-similarity of the ensemble behavior, that permits the capture of time-evolving trends and patterns in the stream, and to reveal changes in evolving data streams. Experimental results on a real life data set show the validity of the approach in maintaining an accurate and up-to-date GP ensemble.
Download
Paper Nr: 41
Title:

HYBRID POPULATION-BASED INCREMENTAL LEARNING TO ASSIGN TERMINALS TO CONCENTRATORS

Authors:

Eugénia Moreira Bernardino, Anabela Moreira Bernardino, Juan Manuel Sánchez-Pérez, Juan Antonio Gómez-Pulido and Miguel Angel Vega-Rodríguez
Abstract: In the last decade, we have seen a significant growth in communication networks. In centralised communication networks, a central computer serves several terminals or workstations. In large networks, some concentrators are used to increase the network efficiency. A collection of terminals is connected to a concentrator and each concentrator is connected to the central computer. In this paper we propose a Hybrid Population-based Incremental Learning (HPBIL) to assign terminals to concentrators. We use this algorithm to determine the minimum cost to form a network by connecting a given collection of terminals to a given collection of concentrators. We show that HPBIL is able to achieve good solutions, improving the results obtained by previous approaches.
Download
Paper Nr: 48
Title:

GENETIC EVOLUTION OF ‘SORTING’ PROGRAMS THROUGH A NOVEL GENOTYPE-PHENOTYPE MAPPING

Authors:

Daniela Xhemali, Christopher J. Hinde and Roger G. Stone
Abstract: This paper presents an adaptable genetic evolutionary system, which includes an innovative approach to mapping genotypes to phenotypes through XML rules. The evolutionary system was originally created to evolve Regular Expressions (REs) to automate the extraction of web information. However, the system has been adapted to work with a completely different domain – Complete Software Programs – to demonstrate the flexibility of this approach. Specifically, the paper concentrates on the evolution of ‘Sorting’ programs. Experiments show that our evolutionary system is successful and can be adapted to work for challenging domains with minimum effort.
Download
Paper Nr: 52
Title:

OPTIMIZING GENETIC ALGORITHM PARAMETERS FOR A STOCHASTIC GAME
Authors:

James Glenn
Abstract: Can’t Stop is a jeopardy stochastic game played on an octagonal game board with four six-sided dice. Previous work generalized a well-known heuristic strategy for the solitaire game and attempted to optimize the parameters of the generalized strategy using a genetic algorithm (GA). There were two challenges in that optimization process: first, the stochastic nature of the game results in a very noisy fitness function; second, the fitness function is computationally expensive. In this work we continue the optimization process for the heuristic strategy by optimizing the GA: for a fixed number of fitness function evaluations, we investigate the effects of varying the GA parameters (in particular the population size and number of generations), which in turn affect the number of samples per individual and thus noise as well. We also examine different sampling schedules; our schedules are unique in that selecting the final champion is considered a schedulable phase. The GA parameters are first optimized on an easy-to-compute test function. The resulting GA parameters are effective on the original problem and as a result we obtain an improved heuristic strategy for Can’t Stop.
Download
Paper Nr: 61
Title:

GENETIC ALGORITHM BASED ON DIFFERENTIAL EVOLUTION WITH VARIABLE LENGTH - Runoff Prediction on an Artificial Basin
Authors:

Ana Freire, Vanessa Aguiar-Pulido, Juan R. Rabuñal and Marta Garrido
Abstract: Differential evolution is a successful approach to solve optimization problems. The way it performs the creation of the individual allows a spontaneous self-adaptability to the function. In this paper, a new method based on the differential evolution paradigm has been developed. An innovative feature has been added: the variable length of the genotype, so this approach can be applied to predict special time series. This approach has been tested over rainfall data for real-time prediction of changing water levels on an artificial basin. This way, a flood prediction system can be obtained.
Download
Paper Nr: 64
Title:

OPTIMIZING B-SPLINES USING GENETIC ALGORITHMS APPLIED TO AIR-TRAFFIC CONFLICT RESOLUTION
Authors:

Clement Peyronne, Daniel Delahaye, Marcel Mongeau and Laurent Lapasset
Abstract: Conflict resolution has always been a sensitive matter in air-traffic management. Current European projects aim partial or total automation of air traffic control to deal with the constant growth of air traffic. Technological advances on flight management system allows us to consider an automatic conflict resolution using continuous trajectories. In this paper, we present a new methodology that, first, relies on B-splines to model trajectories, secondly models air-traffic conflict resolution as an optimization problem whose decision variables are the spline control points. Finally, we use genetic algorithms to tackle this optimization problem in order to generate optimal conflict-free situations.
Download
Paper Nr: 69
Title:

NANOSTRUCTURES THERMAL EMISSION OPTIMIZATION USING GENETIC ALGORITHMS AND PARTICLE SWARMS
Authors:

E. Nefzaoui, J. Drevillon and K. Joulain
Abstract: Nanotechnologies and nanofabrication techniques provided unmeasureable possibilities to control intrinsic microscopic features of materials and structures in the last years. In particular, materials optical properties and light propagation control have been some of the most challenging problems due to their various application possiblities. The present investigation shows that temporally coherent thermal sources have been successfully designed and optimized with evolutionary optimization methods such as genetic algorithms and particle swarms. This lead to a bilayer structure of germanium and silicon carbide, which is, to our knowledge, the simplest existing structure with such properties.
Download
Paper Nr: 70
Title:

OPTIMAL VIABLE PATH SEARCH FOR A CHEESE RIPENING PROCESS USING A MULTI-OBJECTIVE EA
Authors:

Salma Mesmoudi, Nathalie Perrot, Romain Reuillon, Paul Bourgine and Evelyne Lutton
Abstract: Viability theory is a very attractive theoretical approach for the modeling of complex dynamical systems. However, its scope of application is limited due to the high computational power it necessitates. Evolutionary computation is a convenient way to address some issues related to this theory. In this paper, we present a multiobjective evolutionary approach to address the optimisation problem related to the computation of optimal command profiles of a complex process. The application we address here is a real size problem from dairy industry, the modeling of a Camembert cheese ripening process. We have developed a parallel implementation of a multiobjective EA that has produced a Pareto front of optimal control profiles (or trajectories), with respect to four objectives. The Pareto front was then analysed by an expert who selected a interesting compromise, yielding a new control profile that seems promising for industrial applications.
Download
Paper Nr: 76
Title:

HYBRID PARAMETER-LESS EVOLUTIONARY ALGORITHM IN PRODUCTION PLANNING
Authors:

Vida Vukašinovič, Peter Korošec and Gregor Papa
Abstract: In the real-world production planning problems there are many constraints that need to be considered. Usually, these constraints and interdependent and the optimization algorithms has to efficiently solve that. This paper presents the hybrid parameter-less evolutionary algorithm used for construction of an optimal production plan. The algorithm is based on genetic algorithm, but is modified to work without the parameter setting. All algorithm control parameters are automatically determined during the optimization. The algorithm was able to solve the constraints and to make an optimal production plan. Additionally, we evaluated the influence of different ratios of orders with fixed deadlines on the performance of the algorithm. The used algorithm can successfully solve also these additional constraints.
Download
Paper Nr: 79
Title:

TWO ALGORITHMS OF THE EXTENDED PSO FAMILY
Authors:

Juan Luis Fernández-Martínez and Esperanza Garcia-Gonzalo
Abstract: In this paper we present two novel algorithms belonging to the extended family of PSO: the PP-GPSO and the RR-GPSO. These algorithms correspond respectively to progressive and regressive discretizations in acceleration and velocity. PP-GPSO has the same velocity update than GPSO, but the velocities used to update the trajectories are delayed one iteration, thus, PP-GPSO acts as a Jacobi system updating positions and velocities at the same time. RR-GPSO is similar to a GPSO with stochastic constriction factor. Both versions have a very different behavior from GPSO and the other family members introduced in the past: CC-GPSO and CP-GPSO. The numerical comparison of all the family members has shown that RR-GPSO has the greatest convergence rate and its good parameter sets can be calculated analytically since they are along a straight line located in the first order stability region. Conversely PP-GPSO is a more explorative version.
Download
Paper Nr: 81
Title:

REAL-TIME TRAJECTORY MODIFICATION BASED ON BÉZIER SHAPE DEFORMATION

Authors:

L. Hilario, N. Montés, M. C. Mora and A. Falcó
Abstract: This paper presents a new technique for flexible path planning based on the deformation of a Bézier curve through a field of vectors. This new technique is called Bézier Shape Deformation (BSD). This deformation is computed with a constrained optimization method (Lagrange Multipliers Theorem). The main advantage of this method is how the solution is obtained. A linear system is solved to achieve the result. As a consequence, the deformed curve is computed in a few milliseconds where the linear system can be solved offline if the Bézier curve order is maintained constant during the movement of the robot. This method allows the use of these trajectories in dynamic environments where the computational cost is critical. This technique can be combined with any collision avoidance algorithm that produces a field of vectors. In particular, it is appropriate for artificial potential field methods. At the end of the paper, the presented methodology is combined with an artificial potential fields algorithm recently proposed, the Potential Field Projection method (PFP). This method is based on the combination of the classical Potential Fields method and the multi-rate Kalman filter estimation and takes into account the uncertainties on locations, the future trajectory of the robot and the obstacles and the multi-rate information supplied by sensors. As shown in the simulation results, flexible trajectories for collision avoidance are generated with smooth curves.
Download
Paper Nr: 83
Title:

EVACUATION SIMULATION WITH LIMITED CAPACITY SINKS - An Evolutionary Approach to Solve the Shelter Allocation and Capacity Assignment Problem in a Multi-agent Evacuation Simulation
Authors:

Gunnar Flötteröd and Gregor Lämmel
Abstract: We heuristically solve an evacuation problem with limited capacity shelters. An evolutionary learning algorithm is developed for the combined route- and shelter-assignment problem. It is complemented with a heuristic method for the fair minimization of shelter capacities. Different behavioral assumptions “fair” vs. “globally optimal”) are investigated. The proposed approaches are discussed in the context of a real-world tsunami evacuation problem.
Download
Paper Nr: 88
Title:

PURE CO-EVOLUTION FOR SHAPE NESTING
Authors:

Jeffrey Horn
Abstract: We test the effectiveness of an evolutionary algorithm that relies completely on species selection for evolution and on interactions among species to determine fitness. Under Resource-defined Fitness Sharing (RFS), all individuals have the same objective fitness, but they act to reduce their shared fitness through competition for resources. In previous studies, RFS has been used to evolve populations of mutually non-competing (i.e., non-overlapping) shapes on shape nesting problems. In this paper we test the effectiveness of a modified version of RFS, which we call PCSN, against three commercial software packages for shape nesting. PCSN uses species proportions to represent a population, thereby simulating an infinitely large population. With no discovery operators, such as mutation or recombination, evolution consists of selection only, with all species present in the initial population. We show that on some shape nesting problems this approach can outperform some commercial packages. In particular, PCSN nests more circles on a fixed, polygonal substrate than do most of the commercial packages. This might be considered a surprising result, since the algorithm is radically different from any shape nesting algorithms deployed to date. While conventional methods place one shape at a time, the co-evolution approach attempts to place all shapes simultaneously.
Download
Paper Nr: 90
Title:

AN MOEA-BASED METHOD TO TUNE EA PARAMETERS ON MULTIPLE OBJECTIVE FUNCTIONS
Authors:

S. K. Smit, A. E. Eiben and Z. Szlávik
Abstract: In this paper, we demonstrate the benefits of using a multi-objective approach when tuning the parameters of an Evolutionary Algorithm. To overcome the specific challenges that arise when using a meta-algorithm for parameter tuning on multiple functions, we introduce a new algorithm called the Multi-Function Evolutionary Tuning Algorithm (M-FETA) that is able to approximate the parameter Pareto front effectively. The results of the experiments illustrate how the approximated Parameter Pareto front can be used to gain insights, identify ‘generalists’, and study the robustness of the algorithm to be tuned.
Download
Paper Nr: 92
Title:

SPARKLINE HISTOGRAMS FOR COMPARING EVOLUTIONARY OPTIMIZATION METHODS
Authors:

Ville Tirronen and Matthieu Weber
Abstract: Comparing evolutionary optimization methods is a difficult task. As more and more of articles are published in this field, the readers and reviewers are swamped with information that is hard to decipher. We propose the use of sparkline histograms that allow compact representation of test data in a way which is extremely fast to read and more informative than usually given metrics.
Download
Paper Nr: 97
Title:

PARISIAN APPROACH - Reducing Computational Effort to Improve SMT Performance by setting Resizable Caches
Authors:

Josefa Díaz, Francisco Fernández de Vega, J. Ignacio Hidalgo and Oscar Garnica
Abstract: Evolutionay Algorithm are techniques widely used in the resolution of complex problems. On the other hand, Simultaneous Multithreading improves the throughput of the processor core taking advantage of Instruction Level Parallelism and Thread Level Parallelism. In this environment adaptation the cache configuration, at runtime according to workloads settings will be improved the processor performance. This improvement is achieved by using resizable caches. In a previous work, we proposed a Genetic Algorithm to find the better cache configurations according to the needs and characteristics of the workloads. However the computational cost needed for the evaluation process is very high. In this paper we propose the use of the Parisian Evolution Approach to improve dynamically reconfigurable cache designs, and reduce the computational cost associated. We study the behavior of a set of benchmarks, taking into account their needs over cache memory hierarchy in each phase of execution, in order to adapt the cache configuration and to increase the number of instructions per cycle. Experimental results show a large saving in computing time and some improvement on the instructions per cycle achieved in previous approaches.
Download
Paper Nr: 98
Title:

SIMPLE GENETIC ALGORITHM WITH a-SELECTION - Intrinsic System Model, Fixed Points and the Fixed Point Graph
Authors:

André Neubauer
Abstract: Genetic algorithms (GA) are instances of random heuristic search (RHS) which mimic biological evolution and molecular genetics in simplified form. These random search algorithms can be theoretically described with the help of a deterministic dynamical system model by which the stochastic trajectory of a population can be characterized using a deterministic heuristic function and its fixed points. For practical problem sizes the determination of the fixed points is unfeasible even for the simple genetic algorithm (SGA). The recently introduced simple genetic algorithm with a-selection allows the analytical calculation of the unique fixed points of the dynamical system model. In this paper, an overview of the theoretical results for the simple genetic algorithm with a-selection and its corresponding intrinsic system model is given. Further, the connection to the fixed point graph is illustrated which describes the asymptotic behavior of the simple genetic algorithm. In addition to the theoretical analysis experimental results for the simple genetic algorithm with a-selection, uniform crossover and bitwise mutation are presented.
Download
Paper Nr: 100
Title:

ON THE DESIGN OF POPULATIONAL CLUSTERING
Authors:

Leonardo Ramos Emmendorfer
Abstract: The application of clustering algorithms for partitioning the population in evolutionary computation is discussed. Specific aspects which characterize this task lead to opportunities which can be explored by the clustering algorithm. A supervised clustering algorithm is described, which illustrates the exploration of those opportunities.
Download
Paper Nr: 4
Title:

A GIBBS DISTRIBUTION THAT LEARNS FROM GA DYNAMICS
Authors:

Manabu Kitagata and Jun-ichi Inoue
Abstract: A general procedure of average-case performance evaluation for population dynamics such as genetic algorithms (GAs) is proposed and its validity is numerically examined. We introduce a learning algorithm of Gibbs distributions from training sets which are gene configurations (strings) generated by GA in order to figure out the statistical properties of GA from the view point of thermodynamics. The learning algorithm is constructed by means of minimization of the Kullback-Leibler information between a parametric Gibbs distribution and the empirical distribution of gene configurations. The formulation is applied to a solvable probabilistic model having multi-valley energy landscapes, namely, the spin glass chain. By using computer simulations, we discuss the asymptotic behaviour of the effective temperature scheduling and the residual energy induced by the GA dynamics.
Download
Paper Nr: 13
Title:

AN INTEGRATED ARCHITECTURE FOR INFOMOBILITY SERVICES - Advantages of Genetic Algorithms in Real-time Route Planning
Authors:

C. De Castro, G. Leonardi, B. M. Masini and P. Toppan
Abstract: In the field of Intelligent Transportation Systems, a key role is played by efficient route planning services. Such systems have been evolving rapidly, but they still have some restricting drawbacks, such as the lack of a full support of real-time traffic monitoring and the consequent real-time update of the best route suggested. In this paper, an architecture is proposed for the management of dynamic path planning and limitations of traditional search algorithms in these kinds of applications discussed. A variant of the proposed approach is consequently presented, based on the joint use of virus-evolutionary genetic algorithms for real-time route planning and traffic forecasting.
Download
Paper Nr: 14
Title:

AN INNOVATIVE GA OPTIMIZED INVESTMENT STRATEGY BASED ON A NEW TECHNICAL INDICATOR USING MULTIPLE MAS
Authors:

Adriano Simoes, Rui Neves and Nuno Horta
Abstract: This paper proposes a new medium/long term investment strategy for stock markets based on a combination of Simple Moving Averages Crossover (SMAC) and Moving Average Derivate (MAD). This strategy is compared with the Buy and Hold, with the Moving Averages Crossover, and with the Moving Average Derivate strategy. The experiments show that the combination of SMAC and MAD outperforms the results of each strategy individually. The presented approach has an average return of investment of 9.0%, compared with the 2.6% return of the Buy and Hold, for the S&P500, FTSE100, DAX30 and NIKKEI225, between 2004 and 2009.
Download
Paper Nr: 15
Title:

THE CHEMNITZ HYBRID EVOLUTIONARY OPTIMIZATION SYSTEM

Authors:

Ulf Nieländer
Abstract: This paper introduces the Chemnitz Hybrid Evolutionary Optimization System to the scientific community. CHEOPS is a non-standard, high-performance genetic algorithm framework allowing simple as well as advanced modes of operation. Universal genetic algorithms well-suited for solving both single- and multi-objective optimization problems are still a matter of serious research. The Omni Optimizer was a milestone in that research topic, but now it is dramatically outperformed by CHEOPS in single-objective optimization. The comparison should soon continue, because CHEOPS will be straightforwardly enhanced to solve multi-objective problems as well.
Download
Paper Nr: 30
Title:

TWO-TIERED RESOLUTION REAL-TIME PATH EVALUATION
Authors:

J. C. F. Allaire, J. M. P. Langlois, G. Labonté and M. Tarbouchi
Abstract: Unmanned aerial vehicles (UAV) are subject to unforeseen events in harsh environment. Embedded autonomous real-time path re-planning is a possible solution to this issue. Evolutionary algorithms have shown to be an excellent means to optimise the generation of UAV paths but their slow iterative process prevent them to be used for real-time computation. Part of that challenge resides in the computational demanding task of path feasibility evaluation, where each single segment of the generated path needs to be certified ‘collision free’. State of the art algorithms require computationally demanding pre-processing of the world representation, which is too time-consuming for real-time computation. Taking advantage of advancements in the Field Programmable Gate Array (FPGA) technology, this work has evaluated a new feasibility evaluation technique that analyses the path directly from the raw data of the world representation, using two levels of resolution: a high resolution map used close to the UAV, and a low resolution map used far from the UAV. This technique has been implemented on an FPGA and tested in simulation. Timing results (more than 500 map cells evaluated within 5 μs) demonstrate that the two-tiered resolution technique opens up avenues to real-time UAV path re-planning using evolutionary algorithms.
Download
Paper Nr: 34
Title:

OPTIMIZATION OF A STEAM TURBINE GUIDE VANE BY END WALL CONTOURING USING EVOLUTIONARY ALGORITHMS
Authors:

Nils Moser and Franz Joos
Abstract: The subject of this paper is the optimization of a guide vane of steam turbine control stage by end wall contouring. The investigated control stage is derived from an existing industrial steam turbine design. The end wall contour is varied in rotational direction within specified restrictions by an evolutionary algorithm. The algorithm is directly connected to a mesh generator and a Computational Fluid Dynamics (CFD) solver. The optimization goal is the reduction of the total pressure loss over the guide vane. The geometry of the rotor blade has been retained unchanged. The flow field of the varied stage is compared with the baseline geometry. The optimum candidates are further investigated with CFD simulations for different operating point scenarios. Numerical results show that the axisymetric end wall contouring of the nozzle has a considerable effect on the loss behavior of the nozzle over a wide range of pressure ratios. Due to end wall contouring the boundary layer in the nozzle is significantly affected which results in a significant reduction of the secondary flow effects in the guide vanes.
Download
Paper Nr: 42
Title:

A BIASED RANDOM KEY GENETIC ALGORITHM APPROACH FOR UNIT COMMITMENT PROBLEM
Authors:

Luís A. C. Roque, Dalila B. M. M. Fontes and Fernando A. C. C. Fontes
Abstract: A Biased Random Key Genetic Algorithm (BRKGA) is proposed to find solutions for the unit commitment problem. In this problem, one wishes to schedule energy production on a given set of thermal generation units in order to meet energy demands at minimum cost, while satisfying a set of technological and spinning reserve constraints. In the BRKGA, solutions are encoded by using random keys, which are represented as vectors of real numbers in the interval [0,1]. The GA proposed is a variant of the random key genetic algorithm, since bias is introduced in the parent selection procedure, as well as in the crossover strategy. Tests have been performed on benchmark large-scale power systems of up 100 units for a 24 hours period. The results obtained have shown the proposed methodology to be an effective and efficient tool for finding solutions to large-scale unit commitment problems. Furthermore, form the comparisons made it can be concluded that the results produced improve upon the best known solutions.
Download
Paper Nr: 43
Title:

WAVELENGTH CONVERTERS PLACEMENT IN ALL OPTICAL NETWORKS USING DIFFERENTIAL EVOLUTION OPTIMIZATION

Authors:

Gerardo Castañón, Fernando Lezama and Ana María Sarmiento
Abstract: Placement of wavelength converters in an arbitrary mesh network is known to belong to the class of NP-complete problems. So far, this problem has been solved by heuristic strategies or by the application of optimization tools such as genetic algorithms. . In this paper we introduce the application of differential evolution (DE) to the placement of wavelength converters problem to find the optimal solution. Many comparative studies confirm its robustness and efficiency, and in many cases DE outperforms many other well known evolutionary computational approaches in terms of convergence speed and quality of solutions. The major advantage of the DE algorithm rests in the fact that it does not need to build up a search tree or to create auxiliary graphs to find the optimal solutions. Furthermore, the method typically requires few control parameters, and the computed results show that only a small population is needed to obtain the optimal solutions of the placement of wavelength converters problem in an arbitrary network. We present an experiment that demonstrates the effectiveness and efficiency of the proposed evolutionary algorithm.
Paper Nr: 46
Title:

INTEGRATED OPTIMIZATION OF FUNCTIONAL AND LAYOUT DESIGNS BASED ON GENETIC ALGORITHM - Consideration of Carbon Emission troughout Product’s Lifecycle
Authors:

Masakazu Kobayashi and Masatake Higashi
Abstract: In our previous research, the integrated optimization of functional / layout designs based on genetic algorithm was developed for supporting conceptual design phase. This method can optimize a functional structure and a parts layout simultaneously by evaluating performance, cost and size. In this paper, we now focus on consideration of lifecycle characteristics in response to rise of environmental awareness in recent years and combine our previous integrated method with lifecycle assessment (LCA) in order to enable creation of product concepts that balance various characteristics including lifecycle ones at a higher level. This paper also shows an application of the proposed method to a personal computer design and discusses the effect of consideration of lifecycle characteristics during conceptual optimization.
Download
Paper Nr: 58
Title:

A MODIFIED MULTI-POPULATION GENETIC ALGORITHM FOR PARAMETER IDENTIFICATION OF CULTIVATION PROCESS MODELS
Authors:

Olympia N. Roeva, Kalin Kosev and Tanya V. Trenkova
Abstract: In this work a modified multi-population genetic algorithm (MPGA) without the performance of the mutation operator is proposed. The idea is to reduce the convergence time and therefore to increase the identification procedure effectiveness for on-line application of the algorithm. Modified MPGA, classical multipopulation GA and two other modifications are tested for parameter identification problem of an E. coli non-linear fed-batch cultivation model. The contribution of each modification measure to the performance improvement is demonstrated. The obtained results show that the highest accuracy for parameter identification of the considered model is achieved with the multipopulation GA with Modification 1. The best calculation time is shown by the multipopulation GA without mutation.
Download
Paper Nr: 67
Title:

COMPARISON OF METAHEURISTICS FOR WORKFORCE DISTRIBUTION IN MULTI-SKILL CALL CENTRES
Authors:

David Millán-Ruiz, J. Ignacio Hidalgo and Josefa Díaz
Abstract: Call centre technology requires the assignment of a large volume of incoming calls to agents with the required skills to process them. In order to determine the right assignment among incoming calls and agents for a real production environment, a comparative study of meta-heuristics has been carried out. The aim of this study is to implement and empirically compare various representative meta-heuristics, which represent distinct search strategies to reach accurate, feasible solutions, for two different instances of the workforce distribution problem. This study points out how memetic algorithms can outperform other acknowledged meta-heuristics for two different problem instances from a real multi-skill call centre from one of the world's largest telecommunications companies.
Download
Paper Nr: 73
Title:

LAMARCKIAN EVOLUTION OF NEURAL NETWORKS APPLIED TO KEYSTROKE DYNAMICS
Authors:

Paulo Henrique Pisani and Silvio do Lago Pereira
Abstract: The pace of computing and communications development has contributed to an increased data exposure and, consequently, to the rise of an issue known as identity theft. By applying user profiling, which analyzes the user behavior in order to perform a continuous authentication, protection of digital identities can be enhanced. Among the possible features to be analyzed, this paper focuses on keystroke dynamics, something that cannot be easily stolen. As keystroke dynamics involves dealing with noisy data, it was chosen a neural network to perform the pattern recognition task. However, traditional neural network training algorithms are bound to get trapped in local minimum, reducing the learning ability. This work draws a comparison between backpropagation and two hybrid approaches based on evolutionary training, for the task of keystroke dynamics. Differently from most evolutionary algorithms based on Darwinism, this work also studies Lamarckian evolutionary algorithms that, although not being biologically plausible, attained promising results in the tests.
Download
Paper Nr: 78
Title:

THE ROLE OF KEEPING “SEMANTIC BLOCKS” INVARIANT - Effects in Linear Genetic Programming Performance
Authors:

Marina de la Cruz Echeandía, Alba Martín Lázaro, Alfonso Ortega de la Puente, José Luis Montaña Arnáiz and César L. Alonso
Abstract: This paper is focused on two different approaches (previously proposed by the authors) that perform better than Genetic Programming in typical symbolic regression problems: straight-line program genetic programming (SLP-GP) and evolution with attribute grammars (AGE). Both approaches have different characteristics. One of themost important is that SLP-GP keeps semantic blocks invariant (the crossover operator always exchanges complete subexpressions). In this paper we compare both methods and study the possible effect on their performance of keeping these blocks invariant.
Download
Paper Nr: 82
Title:

A GENETIC ALGORITHM WITH A MULTI-LAYERED GENOTYPE-PHENOTYPE MAPPING
Authors:

Seamus Hill and Colm O'Riordan
Abstract: In this paper we investigate the introduction of a multiple-layer genotype-phenotype mapping to a Genetic Algorithm (GA) which attempts to mimic more closely, the effects of nature. The motivation for introducing multiple-layers into the genotype-phenotype mapping is to create a many-to-one genotype-phenotype mapping. The paper compares a traditional GA with a GA containing a multi-layered genotype-phenotype mapping using a number of well understood problems in an attempt to illustrate the potential benefits of including the multilayered mapping. Initial findings suggest that the multi-layered mapping between the genotype-phenotype used in conjunction with a binary representation outperforms existing traditional GA approaches on well known problems, while still allowing the use well understood genetic operators.
Download
Paper Nr: 96
Title:

USING UNIFORM CROSSOVER TO REFINE SIMULATED ANNEALING SOLUTIONS FOR AUTOMATIC DESIGN OF SPATIAL LAYOUTS

Authors:

Fadratul Hafinaz Hassan and Allan Tucker
Abstract: The ease of movement of people inside a public space is highly impacted by the public space layout itself. For example, the flow of a large number of people should be smooth in a well designed public space such as a stadium or hospital. In extreme cases, people might crush to death during emergency evacuations in poorly designed spaces. It is vital that design takes into account the smooth flow of pedestrians. In this paper we describe an initial exploration in using models of pedestrian flow combined with heuristic search to assist in the automatic design for spatial layout. A two-way pedestrian flow system is simulated and heuristic search techniques (genetic algorithm, simulated annealing and hill climbing) are used to find feasible spatial layouts based upon the generated statistics with promising results.
Download
Paper Nr: 99
Title:

TOWARDS MODEL-DRIVEN DATA WAREHOUSE AUTOMATION USING MACHINE LEARNING
Authors:

Moez Essaidi and Aomar Osmani
Abstract: Model-driven data warehouse aims to apply the model-driven engineering approach to derive the data warehouse component. Transformations design is an essential task during the model-driven engineering process. However, Transformations development is a very hard task and needs serious skills. Model transformation by example is a novel approach in model-driven software engineering to derive transformation rules from an initial set of mapping examples. This paper aims to introduce our research effort to automate model-driven data warehouse development using the model transformation by example approach.