ECTA 2012 Abstracts

Full Papers Short Papers
Full Papers
Paper Nr: 6
Title:

Tagging with Disambiguation Rules - A New Evolutionary Approach to the Part-of-Speech Tagging Problem
Authors:

Ana Paula Silva, Arlindo Silva and Irene Rodrigues
Abstract: In this paper we present an evolutionary approach to the part-of-speech tagging problem. The goal of part-of-speech tagging is to assign to each word of a text its part-of-speech. The task is not straightforward, because a large percentage of words has more than one possible part-of-speech, and the right choice is determined by the surrounding word’s part-of-speeches. This means that to solve this problem we need a method to disambiguate a word’s possible tags set. Traditionally there are two groups of methods used to tackle this task. The first group is based on statistical data concerning the different context’s possibilities for a word, while the second group is based on rules, normally designed by human experts, that capture the language properties. In this work we present a solution that tries to incorporate both these approaches. The proposed system is divided in two components. First, we use an evolutionary algorithm that for each part-of-speech tag of the training corpus, evolves a set of disambiguation rules. We then use a second evolutionary algorithm, guided by the rules found earlier, to solve the tagging problem. The results obtained on two different corpora are amongst the best ones published for those corpora.
Download
Paper Nr: 15
Title:

Hybrid Integration of Differential Evolution with Artificial Bee Colony for Global Optimization
Authors:

Bui Ngoc Tam, Pham Ngoc Hieu and Hiroshi Hasegawa
Abstract: In this paper, we investigate the hybridization of a swarm intelligence algorithm and an evolutionary algorithm, namely, the Artificial Bee Colony (ABC) algorithm and Differential Evolution (DE), to solve continuous optimization problems. This Hybrid Integration of DE and ABC (HIDEABC) technique is based on integrating the DE algorithm with the principle of ABC to improve the neighborhood search for each particle in ABC. The swarm intelligence of the ABC algorithm and the global information obtained by the DE population approach facilitate balanced exploration and exploitation using the HIDEABC algorithm. All algorithms were applied to five benchmark functions and were compared using several different metrics.
Download
Paper Nr: 17
Title:

Evolving a Retention Period Classifier for use with Flash Memory
Authors:

Damien Hogan, Tom Arbuckle, Conor Ryan and Joe Sullivan
Abstract: Flash memory based Solid State Drives (SSDs) are gaining momentum toward replacing traditional Hard Disk Drives (HDDs) in computers and are now also generating commercial interest from enterprise data storage companies. However, storage locations in Flash memory devices degrade through repeated programming and erasing. As the storage blocks within a Flash device deteriorate through use, their ability to retain data while powered off over long periods also diminishes. Currently there is no way to predict whether a block will successfully retain data for a specified period of time while powered off. We detail our use of Genetic Programming (GP) to evolve a binary classifier which predicts whether blocks within a Flash memory device will still satisfactorily retain data after prolonged use, saving considerable amounts of testing time. This is the first time a solution to this problem has been proposed and results show an average of over 85% correct classification on previously unseen data.
Download
Paper Nr: 23
Title:

Fuzzy Base Predictor Outputs as Conditional Selectors for Evolved Combined Prediction System
Authors:

Athanasios Tsakonas and Bogdan Gabrys
Abstract: In this paper, we attempt to incorporate trained base learners outputs as inputs to the antecedent parts in fuzzy rule-based construction of hybrid ensembles. To accomplish this we adopt a versatile framework for the production of ensemble systems that uses a grammar driven genetic programming to evolve combinations of multilayer perceptrons and support vector machines. We evaluate the proposed architecture using three realworld regression tasks and compare it with multi-level, hierarchical ensembles. The conducted preliminary experiments showed very interesting results indicating that given a large pool of base predictors to choose from, the outputs of some of them, when applied to fuzzy sets, can be used as selectors for building accurate ensembles from other more accurate and complementary members of the same base predictor pool.
Download
Paper Nr: 29
Title:

A New Evolutionary Approach for the Structural Testing of Switch-case Constructs

Authors:

Gentiana Ioana Latiu, Octavian Augustin Cret and Lucia Vacariu
Abstract: Evolutionary structural testing uses specific approaches based on guided searches that involve evaluating fitness functions to determine whether test data satisfy or not various structural testing criteria. For testing switch-case constructs the nested if-then-else structure and Alternative Critical Branches (ACBs) approaches were used so far. In this paper a new evolutionary structural approach based on Compact and Minimized Control Flow Graph (CMCFG), which is derived from the concept of Control Flow Graph (CFG), is presented. Experiments on different levels of imbrications demonstrate that this new approach has significantly better results in finding test data which cover a particular target branch in comparison with the previous approaches reported in the literature.
Download
Paper Nr: 32
Title:

Evolving Art using Measures for Symmetry, Compositional Balance and Liveliness
Authors:

Eelco den Heijer
Abstract: In this paper we present our research into the unsupervised evolution of aesthetically pleasing images using measures for symmetry, compositional balance and liveliness. We evolve images without human aesthetic evaluation, and use measures for symmetry, compositional balance and liveliness as fitness functions. Our symmetry measure calculates the difference in intensity of opposing pixels around one or more axes. Our measure of compositional balance calculates the similarity between two parts of an image using a color image distance function. Using the latter measure, we are able to evolve images that show a notion of ‘balance’ but are not necessarily symmetrical. Our measure for liveliness uses the entropy of the intensity of the pixels of the image. We performed a number of experiments in which we evolved aesthetically pleasing images using the aesthetic measures, in order to evaluate the effect of each fitness function on the resulting images. We also performed an experiment using a combination of aesthetic measures using a multi-objective evolutionary algorithm (NSGA-II).
Download
Paper Nr: 57
Title:

Using Self-organized Criticality for Adjusting the Parameters of a Particle Swarm
Authors:

Carlos M. Fernandes, Juan Julián Merelo and Agostinho C. Rosa
Abstract: The local and global behavior of Self-Organized Criticality (SOC) systems may be an efficient source for controlling the parameters of a Particle Swarm Optimization (PSO) without hand-tuning. This paper proposes a strategy based on the SOC Bak-Sneppen model of co-evolution for adjusting the inertia weight and the acceleration coefficients values of the PSO. In order to increase exploration, the model is also used to perturb the position of the particles. The resulting algorithm is named Bak-Sneppen PSO (BS-PSO). An experimental setup compares the new algorithm with versions of the PSO with varying inertia weight, including a state-of-the-art algorithm with dynamic variation of the weight value and perturbation of the particles’ positions. The parameter values generated by the model are investigated in order to understand the dynamic of the algorithm and explain its performance.
Download
Paper Nr: 58
Title:

Pherogenic Drawings - Generating Colored 2-dimensional Abstract Representations of Sleep EEG with the KANTS Algorithm
Authors:

Carlos M. Fernandes, Antonio Mora, Juan Julián Merelo and Agostinho C. Rosa
Abstract: Social insects and stigmergy have been inspiring several significant artworks and artistic concepts that question the borders and nature of creativity. Such artworks, which are usually based on emergent properties of autonomous systems and go beyond a centralized human authorship, are a part of a contemporary trend known as generative art. This paper addresses generative art and presents a set of images generated by an ant-based clustering algorithm that uses data samples as artificial ants. These ants interact via the environment and generate abstract paintings. The algorithm, called KANTS, consists in a simple set of equations that model the local behavior of the ants (data samples) in a way that, when travelling on a heterogeneous 2-dimensional lattice of vectors, they tend to form clusters according to the class of each sample. The algorithm was previously proposed for clustering and classification. In this paper, KANTS is used outside a purely scientific framework and it is applied to data extracted from sleep-Electroencephalogram (EEG) signals. With such data sets, the lattice vectors have three variables, which are used for generating the RGB values of a colored image. Therefore, from the actions of the swarm on the environment, we get 2-dimensional colored abstract sketches of human sleep. We call these images pherogenic drawings, since the data used for creating the images are actually the pheromone maps of the ant algorithm. As a creative tool, the method is contextualized within the swarm art field.
Download
Paper Nr: 59
Title:

T-ACO Tournament Ant Colony Optimisation for High-dimensional Problems
Authors:

Emmanuel Sapin and Ed Keedwell
Abstract: Standard ACO implementations use a roulette wheel to allow ants to make path decisions at each node of the topology which works well for problems of smaller dimensionality, but breaks down when higher numbers of variables are considered. Such problems are becoming commonplace in biology and particularly in genomics where thousands of variables are considered in parallel. In this paper, a tournament-based ACO approach is proposed that is shown to outperform the roulette wheel-based approach for all problems of higher dimensionality in terms of the performance of the final solutions and execution time on problems taken from the literature.
Download
Paper Nr: 60
Title:

Basic and Hybrid Imperialist Competitive Algorithms for Solving the n-Queens Problem
Authors:

Ellips Masehian, Nasrin Mohabbati-Kalejahi and Hossein Akbaripour
Abstract: The n-queens problem is a classical combinatorial optimization problem which has been proved to be NP-hard. The goal is to place n non-attacking queens on an n×n chessboard. In this paper, the Imperialist Com-petitive Algorithm (ICA), which is a recent evolutionary metaheuristic method, has been applied for solving the n-queens problem. As another variation, the ICA was combined with a local search method, resulting the Hybrid ICA (HICA). Extensive experimental results showed that the proposed HICA outperformed the basic ICA in terms of average runtimes and average number of fitness function evaluations. The developed algorithms were also compared to the Cooperative PSO (CPSO) algorithm, which is currently the best algo-rithm in the literature for finding the first valid solution to the n-queens problem, and the results showed that the HICA dominates the CPSO by evaluating the fitness function fewer times.
Download
Paper Nr: 61
Title:

A New Model for Solving the Simultaneous Object Collecting and Shepherding Problem in Flocking Robots
Authors:

Ellips Masehian and Mitra Royan
Abstract: Shepherding behavior is a class of collective behaviors in flocking systems which requires that a swarm of mobile robots enter an area populated with known or unknown obstacles, collect a flock of static or dynamic particles (objects), and guide them safely to a predefined goal position. Applications of this behavior are in sheep or duck shepherding and fishing. In this paper, a new algorithmic model is developed for online for-mation control, decision making, behavior selection, and motion planning of a team of homogeneous and anonymous (no leader and follower) flocking robots which simultaneously perform object collecting and shepherding tasks. The model’s architecture is enriched with various complex flocking actions such as flock deformation, flock split and merge, flock expansion, and flock obstacle avoidance. Contributions of this paper include (i) defining a new class of problems for flocking robots called Simultaneous Object Collecting and Shepherding (SOCS) problem, (ii) incorporating online obstacle sensing and avoidance methods in the flocking behavior, and (iii) developing a fuzzy expert system for determining the strategy of environment exploration. The fuzzy inference engine provides an effective way to minimize the time spent on collecting objects while maximizing the gain obtained by object collection, in a way that the flock’s formation and in-tegrity is maintained. The proposed model was implemented on a number of simulations and produced rational and satisfactory results.
Download
Paper Nr: 63
Title:

Solving an Uncapacitated Exam Timetabling Problem Instance using a Hybrid NSGA-II
Authors:

Nuno Leite, Rui Neves, Nuno Horta, Fernando Melício and Agostinho Rosa
Abstract: This paper describes the construction of an university examination timetable using a hybrid multi-objective evolutionary algorithm. The problem instance that is considered is the timetable of the Electrical, Telecommunications and Computer Department at the Lisbon Polytechnic Institute, which comprises three bachelor degree programs and two master degree programs, having about 80 courses offered and 1200 students enrolled. The task of manually construct the exam timetable for this instance is a complex one due essentially to the high number of combined degree courses. This manual process takes, considering a two-person team, about one week long. A hybrid multi-objective evolutionary algorithm, based on the Non-dominated Sorting Genetic Algorithm-II (NSGA-II), is proposed for solving this problem instance, incorporating two distinct objectives: one concerning the minimization of the number of occurrences of students having to take exams in consecutive days, and a second one concerning the minimization of the timetable length. The computational results show that the automatic algorithm achieves better results compared to the manual solution, and in negligible time.
Download
Paper Nr: 71
Title:

Computational Ontogeny
Authors:

William R. Buckley
Abstract: Of interest to the theory of machines that construct is ontogeny, by which process of development the constructor is transformed from immature to mature form. Whereas we have already shown that self-replicating machines generally are able to bootstrap themselves through the construction of sub-machines (such as organs that rewind a tape, or replicate a tape, or initiate the behavior of a construct), in this paper we present in abstract a constructor that bootstraps its ability to construct, through the construction of sub-constructors. This is to say, we present a constructor that learns how to construct, and does so by constructing; our constructor is in truth a proto-constructor. Here, learning occurs by the addition of new machine configuration; each learned lesson is correlated with specific additions to machine configuration.
Download
Paper Nr: 73
Title:

On the Evolvability of Different Computational Architectures using a Common Developmental Genome
Authors:

Konstantinos Antonakopoulos and Gunnar Tufte
Abstract: Artificial organisms comprise a method that enables the construction of complex systems with structural and/or computational properties. In this work we investigate whether a common developmental genome can favor the evolvability of different computational architectures. This is rather interesting, especially when limited computational resources is the case. The commonly evolved genome showed ability to boost the evolvability of the different computational architectures requiring fewer resources and in some cases, finding better solutions.
Download
Short Papers
Paper Nr: 2
Title:

Replicator Dynamic Inspired Differential Evolution Algorithm for Global Optimization
Authors:

Shichen Liu, Yan Xiong, Qiwei Lu and Wenchao huang
Abstract: Differential Evolution (DE) has been shown to be a simple yet efficient evolutionary algorithm for solving optimization problems in continuous search domain. However the performance of the DE algorithm, to a great extent, depends on the selection of control parameters. In this paper, we propose a Replicator Dynamic Inspired DE algorithm (RDIDE), in which replicator dynamic, a deterministic monotone game dynamic generally used in evolutionary game theory, is introduced to the crossover operator. A new population is generated for an applicable probability distribution of the value of Cr, with which the parameter is evolving as the algorithm goes on and the evolution is rather succinct as well. Therefore, the end-users do not need to find a suitable parameter combination and can solve their problems more simply with our algorithm. Different from the rest of DE algorithms, by replicator dynamic, we obtain an advisable probability distribution of the parameter instead of a certain value of the parameter. Experiment based on a suite of 10 bound-constrained numerical optimization problems demonstrates that our algorithm has highly competitive performance with respect to several conventional DE and parameter adaptive DE variants. Statistics of the experiment also show that our evolution of the parameter is rational and necessary.
Download
Paper Nr: 9
Title:

New Crossover Operator in a Hybrid 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 new crossover operator based on Constraint Based Scheduling (CBS) approach in a Genetic Algorithm (GA) for solving a scheduling problem. The proposed hybrid crossover, noted as HCX, is applied in Hybrid Genetic Algoritym (HGA) to a single machine scheduling problem with sequence-dependent setup times for the objective of minimizing the total tardiness. Through numerical experiments we compare the performance of the GA and the HGA approaches on different benchmarks from the literature. These results indicate that the HGA is very competitive and generates solutions that approach those of the known reference sets.
Download
Paper Nr: 12
Title:

On the Capacity of Hopfield Neural Networks as EDAs for Solving Combinatorial Optimisation Problems
Authors:

Kevin Swingler
Abstract: Multi-modal optimisation problems are characterised by the presence of either local sub-optimal points or a number of equally optimal points. These local optima can be considered as point attractors for hill climbing search algorithms. It is desirable to be able to model them either to avoid mistaking a local optimum for a global one or to allow the discovery of multiple equally optimal solutions. Hopfield neural networks are capable of modelling a number of patterns as point attractors which are learned from known patterns. This paper shows how a Hopfield network can model a number of point attractors based on non-optimal samples from an objective function. The resulting network is shown to be able to model and generate a number of local optimal solutions up to a certain capacity. This capacity, and a method for extending it is studied.
Download
Paper Nr: 14
Title:

A Grid-based Genetic Algorithm for Multimodal Real Function Optimization
Authors:

Jose M. Chaquet and Enrique J. Carmona
Abstract: A novel genetic algorithm called GGA (Grid-based Genetic Algorithm) is presented to improve the optimization of multimodal real functions. The search space is discretized using a grid, making the search process more efficient and faster. An integer-real vector codes the genotype and a GA is used for evolving the population. The integer part allows us to explore the search space and the real part to exploit the best solutions. A comparison with a standard GA is performed using typical benchmarking multimodal functions from the literature. In all the tested problems, the proposed algorithm equals or outperforms the standard GA.
Download
Paper Nr: 16
Title:

Genetic Algorithms and Firefly Algorithms for Non-linear Bioprocess Model Parameters Identification
Authors:

Olympia Roeva and Tanya Trenkova
Abstract: In this paper, Firefly algorithms (FA) and Genetic algorithms (GA) are applied to parameter identification problem of a non-linear mathematical model of the E. coli cultivation process. A system of ordinary differential equations is proposed to model the growth of the bacteria, substrate utilization and acetate formation. Parameter optimization is performed using a real experimental data set from an E. coli MC4110 fed-batch cultivation process. In the considered non-linear mathematical model, the parameters that should be estimated are maximum specific growth rate, two saturation constants and two yield coefficients. Parameters of both meta-heuristics are tuned on the basis of several pre-tests according to the optimization problem considered here. Based on the numerical and simulation result, it is shown that the model obtained by the FA is more accurate and adequate than the one obtained using the GA. Presented results prove FA superiority and powerfulness in solving non-linear dynamic model of cultivation processes.
Download
Paper Nr: 19
Title:

Three Genetic Algorithm Approaches to the Unrelated Parallel Machine Scheduling Problem with Limited Human Resources
Authors:

Fulvio Antonio Cappadonna, Antonio Costa and Sergio Fichera
Abstract: This paper addresses the unrelated parallel machine scheduling problem with limited and differently-skilled human resources. Firstly, the formulation of a Mixed Integer Linear Programming (MILP) model for solving the problem is provided. Then, three proper Genetic Algorithms (GAs) are presented, aiming to cope with larger sized issues. Numerical experiments put in evidence how all GAs proposed are able to approach the global optimum given by MILP model for small-sized instances. Moreover, a statistical comparison among proposed meta-heuristics algorithms is performed with reference to larger problems.
Download
Paper Nr: 20
Title:

Generation of Non-redundant Summary based on Sentence Clustering Algorithms of NSGA-II and SPEA2
Authors:

Jung Song Lee, Han Hee Hahm, Seong Soo Chang and Soon Cheol Park
Abstract: In this paper, automatic document summarization using the sentence clustering algorithms, NSGA-II and SPEA2, is proposed. These algorithms are very effective to extract the most important and non-redundant sentences from a document. Using these, we cluster similar sentences as many groups as we need and extract the most important sentence in each group. After clustering, we rearrange the extracted sentences in the same order as in the document to generate readable summary. We tested this technique with two of the open benchmark datasets, DUC01 and DUC02. To evaluate the performances, we used F-measure and ROUGE. The experimental results show the performances of these MOGAs, NSGA-II and SPEA2, are better than those of the existing algorithms.
Download
Paper Nr: 26
Title:

Alternative Analysis Networking - A Multi-characterization Algorithm
Authors:

Kevin Albarado and Roy Hartfield
Abstract: A neural network technique known as unsupervised training was coupled with conventional optimization schemes to develop an optimization scheme which could characterize multiple “optimal” solutions. The tool discussed in this study was developed specifically for the purposes of providing a designer with a method for designing multiple answers to a problem for the purposes of alternative analysis. Discussion of the algorithm is provided along with three example problems: unconstrained 2-dimensional mathematical problem, a tension-compression spring optimization problem, and a solid rocket motor design problem. This algorithm appears to be the first capable of performing the task of finding multiple optimal solutions as efficiently as typical stochastic based optimizers.
Download
Paper Nr: 31
Title:

Memetic Algorithm with Population Management for the Two-dimensional Loading Vehicle Routing Problem with Partial Conflicts
Authors:

Khaoula Dhaoui, Nacima Labadie and Alice Yalaoui
Abstract: The two-dimensional loading vehicle routing problem with partial conflicts combines two NP-hard problems: the capacitated vehicle routing problem (CVRP) and the two-dimensional bin-packing problem with partial conflicts (2BPPC). This problem arises for example in hazardous waste collection, where some materials can be partially conflicting. In this paper, we propose a memetic algorithm with population management to resolve this new problem. A modified SHF-D heuristic is used to obtain feasible packing in each vehicle. The proposed approach is tested on a new benchmark, created by adding partial conflicts to instances from the literature.
Download
Paper Nr: 37
Title:

The Brain in a Box - An Encoding Scheme for Natural Neural Networks
Authors:

Martin Pyka, Tilo Kircher, Sascha Hauke and Dominik Heider
Abstract: To study the evolution of complex nervous systems through artificial development, an encoding scheme for modeling networks is needed that reflects intrinsic properties similiar to natural encodings. Like the genetic code, a description language for simulations should indirectly encode networks, be stable but adaptable through evolution and should encode functions of neural networks through architectural design as well as single neuron configurations. We propose an indirect encoding scheme based on Compositional Pattern Producing Networks (CPPNs) to fulfill these needs. The encoding scheme uses CPPNs to generate multidimensional patterns that represent the analog to protein distributions in the development of organisms. These patterns form the template for three-dimensional neural networks, in which dendrite- and axon cones are placed in space to determine the actual connections in a spiking neural network simulation.
Download
Paper Nr: 40
Title:

A New Stopping Criterion for Genetic Algorithms
Authors:

Christelle Reynes and Robert Sabatier
Abstract: Obtaining theoretically legitimate stopping criteria is a difficult task. Being able to use such criteria, especially in real-encoding context, remains an open problem. The proposed criterion is based on a Markov chain modelling and on the distribution of the number of occurrences of the locally best solution during several generations under the assumption of non-convergence. The algorithm stops when the probability of obtaining the observed number of occurrences is too small. The obtained criterion is able to fit very different solution spaces and fitness functions (within studied limitations) without any required user intervention.
Download
Paper Nr: 41
Title:

GA - Based Highway Alignment Optimization Incorporating Junction Locations’
Authors:

Botan M. Ahmad AL-Hadad and Michael Mawdesley
Abstract: Provision of junction locations as access points along a new development for a highway project is important to enhance the sustainable development of an area in term of economic and social generation with less environmental impacts. This study investigates the possibility of simultaneous optimization of a highway alignment and junction locations. The effects of junction provisions with their locations in terms of access and proximity costs on the main alignment are investigated. A novel design approach for highway alignment design, which is based on station points along the centre line of the alignment instead of using the conventional highway alignment parameters, is introduced and a genetic algorithm (GA)-based model is developed to incorporate finding optimum junction locations along with the main highway alignment optimization. The results show that the alignment location, configuration, and total cost are significantly affected by junction provisions and their locations and the model is able to find optimum junction locations that best serve the local land use centres. This paper concludes that a highway alignment cannot be optimum without simultaneous junction location considerations.
Paper Nr: 46
Title:

An Evolution of a Complete Program using XML-based Grammar Definition
Authors:

Nor Zainah Siau, Christopher J. Hinde and Roger G. Stone
Abstract: XML technology is a technique to describe structured data that can be manipulated by different types of applications, especially to represent content on the Web. This paper presents a viable approach to automatically evolve a ‘sorting program’ by applying genetic programming and full syntax XML-based grammar definition to map the genotype to phenotype. The genotypes are composed of fixed-length blocks of genes that are made up of a series of integer values. The paper reports that our approach improves the structure of the grammar used in the mapping process, which guarantees that the generated program follows the correct syntax with no repair function, in comparison to earlier work. This allows more structured programs than earlier systems.
Download
Paper Nr: 52
Title:

Neutrality through Transcription & Translation in Genetic Algorithm Representation
Authors:

Seamus Hill and Colm O'Riordan
Abstract: This paper examines the use of the biological concepts of transcription and translation, to introduce neutrality into the representation of a genetic algorithm (GA). The aim of the paper is to attempt to identify problem characteristics which may benefit from the inclusion of neutrality, through a basic adaptation of the concepts of transcription and translation, to create a genotype-phenotype map (GP-map) which introduces phenotypic variability. Neutrality can be viewed as a situation where a number of different genotypes represent the same phenotype. A modification of De Jong’s classic test suite was used to compare the performance of a simple generic algorithm (SGA) and a multi layered mapping genetic algorithm (MMGA), which incorporates the concepts of transcription and translation into its GP-map. The modified De Jong test suite was chosen as it is well understood and has been used in numerous comparisons over the years, thus allowing us to contrast the performance of the MMGA against other GA variations as well as attempting to identify problem characteristics in isolation. Initial results indicate that the neutrality introduced through the multi-layered mapping can prove beneficial for problems containing certain characteristics, in particular multidimensional, multimodal, continuous and deterministic.
Download
Paper Nr: 55
Title:

Synthesis of Reuse Water Networks by PSO Approach
Authors:

Mauro A. S. S. Ravagnani, Daniela E. G. Trigueros, Aparecido N. Módenes and Fernando Espinoza-Quiñones
Abstract: In the present paper the problem of reuse water networks have been modeled and optimized by the application of a modified Particle Swarm Optimization (PSO) algorithm. A proposed modified PSO method lead with both discrete and continuous variables in Non-Linear Programming (NLP) and Mixed Integer Non-Linear Programming (MINLP) formulations that represent the water allocation problems. Pinch analysis concepts are used jointly with the improved PSO method. A literature problem was solved with the developed systematic and results has shown excellent performance in the optimality of reuse water network synthesis based on the criterion of minimization of annual total cost.
Download
Paper Nr: 64
Title:

Interpretation of Time Dependent Facial Expressions in Terms of Emotional Stimuli
Authors:

Roman Gorbunov, Emilia Barakova and Matthias Rauterberg
Abstract: In this paper we demonstrate how genetic programming can be used to interpret time dependent facial expressions in terms of emotional stimuli of different types and intensities. In our analysis we have used video records of facial expressions made during the Mars-500 experiment in which six participants have been isolated for 520 days to simulate flight to Mars. The FaceReader, commercial software developed by VicarVision and Noldus Information Technology, has been used to extract seven time dependent components of facial expressions from the video records. To interpret the obtained time dependent components of facial expressions we have proposed a mathematical model of emotional stimuli assuming that dynamics of facial expressions is determined by emotional stimuli of different types and intensities and facial expression at the moment of the stimuli. Genetic programming has been used to find the locations, types and intensities of the emotional stimuli as well as the way the facial expressions react on them.
Download
Paper Nr: 68
Title:

Complexification of Gene Networks by Co-evolution of Genomes and Genomic Parasites

Authors:

David M. Holloway, Alexander B. Kazansky and Alexander V. Spirov
Abstract: The co-evolution of species with their genomic parasites (transposons) is thought to be one of the primary ways of rewiring gene regulatory networks (GRNs). In this communication, we computationally explore some of the essential co-evolution aspects of hosts (GRNs) with their transposons. We implemented an evolutionary search of an appropriate GRN model design on the example of the Drosophila gap-gene network. Simple artificial transposons capable of spreading and transposition were implemented. With the model, we explored the hypothesis that targeting destruction of some of the regulatory connections in the GRN via the action of transposons can produce negative selection pressure. Functionally external genes can be recruited (co-opted) into the GRN under this selection pressure following transposon rewiring of the GRN. Over evolutionary time, transposition events are able to disrupt these new regulatory connections, leading to repeated cycles of recruitment, rewiring and optimization. This process can produce increasingly large GRNs with the same basic functions.
Download
Paper Nr: 72
Title:

Point Mutation Colonies with Restricted Rules
Authors:

Adam Kožaný
Abstract: Point mutation colonies (hereinafter referred to as PM colonies) are multi-agent systems. Development of the environment in these systems is determined by rewriting rules which allow the agent to influence other agents and environmental symbols in its strict neighbourhood. The rules enable the agent to erase, substitute or insert neighbouring agents/symbols, to change its position with neighbouring agents/symbols or to disappear. In this paper we will focus on the impact of forbidding some of the rule-type or their combination in the development of the entire family of PM colonies with such restriction and we will also look into the impact of restrictions on the generative power of PM colonies.
Download
Paper Nr: 74
Title:

A Genetic Algorithm to Study a P3 Non-trivial Collective Task
Authors:

F. Jiménez-Morales and J. L. Guisado
Abstract: Here we report new results of a genetic algorithm (GA) used to evolve one dimensional Cellular Automata (CA) to perform a P3 non-trivial collective behavior task. For this task the goal is to find a CA rule that reaches one final configuration in which the concentration of active cells oscillates among three different values. Though the majority of the best evolved rules belong to the II Wolfram’s class, the GA also finds rules of the III and IV classes. The different computational mechanisms used by each rule to synchronize the entire lattice are analyzed by means of the spatio-temporal patterns generated.
Download
Paper Nr: 3
Title:

Differential Evolution for Adaptive System of Particle Swarm Optimization with Genetic Algorithm
Authors:

Pham Ngoc Hieu and Hiroshi Hasegawa
Abstract: A new strategy using Differential Evolution (DE) for Adaptive Plan System of Particle Swarm Optimization (PSO) with Genetic Algorithm (GA) called DE-PSO-APGA is proposed to solve a huge scale optimization problem, and to improve the convergence towards the optimal solution. This is an approach that combines the global search ability of GA and Adaptive plan (AP) for local search ability. The proposed strategy incorporates concepts from DE and PSO, updating particles not only by DE operators but also by mechanism of PSO for Adaptive System (AS). The DE-PSO-APGA is applied to several benchmark functions with multi-dimensions to evaluate its performance. We confirmed satisfactory performance through various benchmark tests.
Download
Paper Nr: 8
Title:

Evolving a Character in a First-person Shooter
Authors:

Chishyan Liaw, Ching-Tsorng Tsai, Chung-Chi Lin and Jing-Long Wu
Abstract: This paper presents an effective strategy of evolving a character in the Quake III Arena, a first-person shooter. A genetic algorithm (GA) is used to evolve a character's capabilities and behaviors. In order to increase a character’s ability, the GA is used to determine the constrained weights for the behavior control. In the experiments, the GA is implemented to design a non-player character (NPC) which is shown to be superior to the other characters originally created in the Quake III game. This evolving strategy decreases the amount of effort required by game designers to design an intelligent character’s behaviors.
Download
Paper Nr: 13
Title:

A Comparative Study of Intelligent Techniques for Modern Portfolio Management
Authors:

Konstantinos Metaxiotis and Konstantinos Liagkouras
Abstract: In this paper we present a wide range of intelligent technologies applied to the solution of the portfolio selection problem. We also provide a classification of the available intelligent technologies, according to the methodological framework followed. Finally, we provide a comparative study of the different intelligent technologies applied for constructing efficient portfolios and we suggest potential paths for future work that lie at the intersection of the presented techniques.
Download
Paper Nr: 21
Title:

Using Metaheuristics for Solving Balanced Academic Curriculum Problem
Authors:

Lorna V. Rosas-Téllez, José L. Martínez-Flores and Vittorio Zanella-Palacios
Abstract: The Balanced Academic Curriculum Problem (BACP) consist in the assignment of courses in periods that form an academic curriculum so that the prerequisites are satisfied and the courses load is balanced for students. The BACP is considered an optimization problem classified as NP- Hard. This problem is included in CSPLib with three benchmark instances but the formulation of these instances is simpler than the real problem that there is in universities. In this paper we present the solution to a modified problem BACP, modeled as an integer programming problem, using Tabu Search and Evolutionary Strategies for its solution. The results obtained for the instances of modified and original BACP, proposed in the CSPLib, show that metaheuristics are a good option to find solutions for instances of the problem that with exact methods is not possible to find.
Paper Nr: 27
Title:

Multi-agent Solution for ‘8 Queens’ Puzzle
Authors:

Ivan Babanin, Ivan Pustovoj, Elena Kleimenova, Sergey Kozhevnikov, Elena Simonova, Petr Skobelev and Alexander Tsarev
Abstract: The problem of 8 Queens is one of the most well-known combinatorial problems. In this article multi-agent evolutionary-based solution for ‘8 Queens’ problem is proposed. In the multi-agent solution each Queen (or other chess-man) gets a software agent that uses a 'trial-and-error' method in asynchronous and parallel decision making on selecting new position for queens. As the result the solution is found in distributed manner without main control center that provides a number of benefits, for example, introducing new types of chess-man or changing constraints in real time. Two main strategies of Queen’s decision making process has been considered and compared in experiments: random generation of the next move and conflict-solving negotiations between the agents. Experiments’ results show significant acceleration of the decision making process in case of negotiation-based strategy. This solution was developed for training course for students of Computer Science as a methodical basis for designing swarm-based multi-agent systems for solving such complex problems as resource allocation and scheduling, pattern recognition or text understanding.
Download
Paper Nr: 28
Title:

Comparing Adaptive and Non-adaptive Models of Cargo Transportation in Multi-agent System for Real Time Truck Scheduling
Authors:

Oleg Granichin, Petr Skobelev, Alexander Lada, Igor Mayorov and Alexander Tsarev
Abstract: The application of multi-agent platform for real-time adaptive scheduling of trucks is considered. In case of unpredictable events the system works adaptively and doesn’t stop to restart the plan from the beginning. Different models of cargo transportation for truck companies having own fleet are analysed. The results show that using adaptive scheduling in real time it is possible to create significantly more profitable schedules (up to 40-60% compared with rigid models) and save a number of trucks (up to 20%) for the same amount of orders.
Download
Paper Nr: 30
Title:

Image Halftoning with Turing Patterns
Authors:

Atsushi Nomura
Abstract: This paper presents an image halftoning algorithm with a reaction-diffusion system in which periodic patterns called Turing patterns autonomously emerge. Image halftoning refers to conversion of a gray level image to a binary image so that the human visual system can perceive the original gray level image from the converted binary one. The reaction-diffusion system has activator and inhibitor distributions, and creates the Turing type periodic patterns in the distributions from an initial noisy distributions under the condition of long-range inhibition. Characteristics of the Turing patterns depend on a parameter of the reaction-diffusion system. Thus, by modulating the parameter distribution according to an image brightness distribution, the proposed algorithm creates Turing patterns of which characteristics distribute spatially; the human visual system can perceive distribution of the Turing patterns as the original image. Application of the proposed algorithm to a test image demonstrates its qualitative performance and convergence.
Download
Paper Nr: 36
Title:

A New Metaheuristic for Float Management in Resource-constrained Project Scheduling - A Bi-criteria Approach
Authors:

Roni Levi and Sándor Danka
Abstract: In this paper, we present a new unified theoretical model and the conception of the corresponding heuristic algorithm to solve several "what if" like float management problems in resource-constrained project scheduling. The traditional time-oriented resource-constrained project scheduling model for makespan minimization gives an optimal starting time set therefore an activity movement, may be able to destroy the resource-feasibility. The float management, as a stating base, needs a so-called forbidden-set oriented model (a forbidden-set oriented heuristic), which gives an optimal resource conflict repairing relation set. After inserting the additional predecessor-successor relations, in a optimal schedule every movable activity can be moved without destroying the resource feasibility. In the other side, when we have a forbidden-set oriented schedule, then according to the total free float, we have some freedom to redistribute the float among activities to answer several "what if" like questions. For example, in the planning phase we can investigate the consequences of a delay or a longer duration which may be caused by a notorious element of the "critical" activity subset. The unified float management as a new tool was built into the forbidden-set oriented Sounds of Silence (SoS) metaheuristic frame (Csébfalvi et al., 2008a). From theoretical point of view, float management is invariant to the applied heuristic frame; therefore it can be built into any other heuristic which is developed to solve forbidden-set oriented resource-constrained project scheduling problem (RCPSP). The toolbox can be completed by any other new element (float measure), which can be described as a linear programming (LP) or a simple mixed integer linear programming (MILP) problem on the set of the forbidden-set oriented (freely movable without resource-conflicts) solutions as a problem-specific redistribution of the total free float of the project. The essence and viability of our unified approach is illustrated by a set of examples.
Download
Paper Nr: 38
Title:

Improving the Asymptotic Convergence of Memetic Algorithms - The SAT Problem Case Study
Authors:

Noureddine Bouhmala
Abstract: In this work, a memetic algorithm that makes use of the multilevel paradigm for solving SAT problems is presented. The multilevel paradigm refers to the process of dividing large and difficult problems into smaller ones, which are hopefully much easier to solve, and then work backward towards the solution of the original problem, using a solution from a previous level as a starting solution at the next level. Results on real industrial instances are presented.
Download
Paper Nr: 47
Title:

Application of Evolutionary Strategies for Optimisation of Parameters during the Modelling of the Magnetic Hysteresis Loop of the Construction Steel
Authors:

D. Jackiewicz and R. Szewczyk
Abstract: This paper concerns the possibility of use evolutionary strategies for optimisation of magnetic characteristics model's parameters. The Jiles-Atherton extended model was used for modelling the magnetic hysteresis loop of construction steel St10. In this model k parameters change their value during the magnetisation process. However, determination of model’s parameters by gradient optimisation was not succesfull. Only use of evolutionary strategies for optimisation enables achievement of very good agreement with results of experimental measurements. This agreement was confirmed by high values of the R2 determination coefficient.
Download
Paper Nr: 56
Title:

Application of Bio-inspired Algorithm of Structural Optimization to Automated Design
Authors:

Mirosław Mrzygłód
Abstract: The article presents the concept of methodology of automated design based on bio-inspired algorithm of structural optimization. For the purposes of the automatic design, the constant criterion surface algorithm (CCSA) is used The algorithm shapes the structure under constant constraint surface rule and gives possibility to start optimization from a minimum volume arrangement. The automated design schema considers a minimum effort of the designer that is limited to defining the loads and boundary conditions. To ensure a high reliability of the automated design process, the CCSA algorithm was enriched by a procedure of the structure continuity control. As illustrated in the chair example, the application of bio-inspired algorithm in the automated design framework allows to obtain efficient solution.
Download
Paper Nr: 65
Title:

Fair Comparison of Population-based Heuristic Approaches - The Evils of Competitive Testing
Authors:

Anikó Csébfalvi and György Csébfalvi
Abstract: 17 years ago, Hooker (1995) presented a pioneering work with the following title: "Testing Heuristics: We Have It All Wrong". If we ask the question now: "Do we have it all wrong?" the answer will be undoubtedly yes. The problem of the fair comparison remained essentially the same in the heuristic community. When we use stochastic methods in the optimization (namely heuristics or metaheuristics with several tunable parameters and starting seeds) then the usual presentation practice: "one problem - one result" is extremely far from the fair comparison. From statistical point of view, the minimal requirement is a so-called "small-sample" which is a set of results generated by independent runs and an appropriate "small-sample-test" according to the theory of the experimental design and evaluation and the protocol used for example, in the drug development processes. The viability and efficiency of the proposed statistically correct "bias-free" nonparametric methodology is demonstrated using a well-known nonlinear structural optimization example on the set of state-of-the-art heuristics. In the motivating example we used the presented solutions as a small-sample generated by a "hyperheuristic" and we test its quality against ANGEL, where the "supernatural" hybrid metaheuristic ANGEL combines ant colony optimization (AN), genetic algorithm (GE) and a gradient-based local search (L) strategy. ANGEL is an "essence of the different but at the same time similar heuristic approaches". The extremely simple and practically tuning-free ANGEL presents a number of interesting aspects such as extremely good adaptability and the ability to cope with totally different large real applications from the highly nonlinear structural optimization to the long-term optimization of the geothermal energy utilization.
Download
Paper Nr: 69
Title:

A Methodological Proposal to Eliminate Ambiguities in the Comparison of Vehicle Routing Problem Solving Techniques
Authors:

Eneko Osaba and Roberto Carballedo
Abstract: In the field of vehicle routing problems it is very common to use benchmarks (sets of problem instances) to evaluate new solving techniques or algorithms. The purpose of these benchmarks is to compare the techniques based on the results or solutions obtained. Typically, the benchmarks include the values of optimal solutions (if they have been obtained) or values of the best known solutions. In many cases, details of how these results were obtained are not described. This may generate controversy and difficults the comparisons of techniques. This paper shows an example of ambiguity in the results of an instance of the most used VRPTW (Vehicle Routing Problem with Time Windows) bechmark. We show that when analyzing the optimal solution and the best approximate solution of a specific problem, the two results are equivalent. Finally, we will propose a set of guidelines to consider when publishing the results obtained by a new algorithm.
Download