ECTA 2011 Abstracts


Full Papers
Paper Nr: 9
Title:

MONITORING INTERPERSONAL RELATIONSHIPS THROUGH GAMES WITH SOCIAL DILEMMA

Authors:

Roman Gorbunov, Emilia Barakova, Rene Ahn and Matthias Rauterberg

Abstract: In this paper we introduce a method to monitor interpersonal relations through a game with a social dilemma. In the game players can interact with each other through negotiations and by exchanges of resources. To enable the monitoring of interpersonal relations this environment confronts players with specially selected instances of the game, where strategies based on different social factors (like helpfulness or fairness) will enforce different choices in the game. An evolutionary inspired optimization was used to find the games with the special social setting. The special selection of the games helps us to relate the observed actions directly to parameters that model strategies that the players are likely to adopt. Through an estimation of these parameters we are able to observe quantitative differences in the social preferences by different players. Moreover, we demonstrate that players play differently depending on whom they are interacting with. This strongly indicates that the observed playing styles can reveal certain aspects of the relations between players.

Paper Nr: 37
Title:

COULD TYRANNOSAURUS RUN FAST? - Mechanical Power Calculation for 15.7 m/s Tyrannosaurus Running

Authors:

Yoshiyuki Usami

Abstract: Running ability of large bepidal theropod Tyrannosaurus is studied with the use of evolutionary computational method. In 2002 Hutchinson and Garcia published a paper titled as "Tyrannosaurus was not a fast runner" (Hutchinson and Garcia, 2002). They postulated an arbitrary mid-stance posture in running motion, and calculated required muscle mass of the hind limb. This method can not tell information on running speed, because it is a static method. Then, running speed of Tyrannosaurus could not be evaluated quantitatively. We accomplished numerical simulation to obtain whole running motion of Tyrannosaurus with the use of evolutionary computation method. As a result, we have obtained running motion of Tyrannosaurus in a speed of 15.7 m/s within allowed parameters range. We have discussed on mechanical power output of the running motion of Tyrannosaurus for the first time in this research area. As for a problem of the simulation algorithm, there is room to improve simple evolutionary computation method applied in the present work. Generally, a solution of evolutionary computation method falls into a local minimum. However, finding the global minimum of the evaluation function i.e., velocity and vertical acceleration are needed for this problem. Then, developing such an algorithm is left as the future problem.

Paper Nr: 41
Title:

EVOLVED PREAMBLES FOR MAX-SAT HEURISTICS

Authors:

Luís O. Rigo Jr. and Valmir C. Barbosa

Abstract: MAX-SAT heuristics normally operate from random initial truth assignments to the variables. We consider the use of what we call preambles, which are sequences of variables with corresponding single-variable assignment actions intended to be used to determine a more suitable initial truth assignment for a given problem instance and a given heuristic. For a number of well established MAX-SAT heuristics and benchmark instances, we demonstrate that preambles can be evolved by a genetic algorithm such that the heuristics are outperformed in a significant fraction of the cases. The heuristics we consider include the well-known novelty, walksat-tabu, and adaptnovelty+. Our benchmark instances are those of the 2004 SAT competition and those of the 2008 MAX-SAT evaluation.

Paper Nr: 56
Title:

HYBRID RULES OF PERTURBATION IN DIFFERENTIAL EVOLUTION FOR DYNAMIC OPTIMIZATION

Authors:

Mikołaj Raciborski, Krzysztof Trojanowski and Piotr Kaczyński

Abstract: This paper studies properties of a differential evolution approach (DE) for dynamic optimization problems. An adaptive version of DE, namely the jDE algorithm has been applied to two well known benchmarks: Generalized Dynamic Benchmark Generator (GDBG) and Moving Peaks Benchmark (MPB) reimplemented in a new benchmark suite Syringa. The main novelty of the presented research concerns application of new type of solution, that is, solution mutated with an operator originated from another metaheuristics. The operator uses a symmetric a-stable distribution variate for modification of the solution coordinates.

Paper Nr: 59
Title:

GLOBAL COMPETITIVE RANKING FOR CONSTRAINTS HANDLING WITH MODIFIED DIFFERENTIAL EVOLUTION

Authors:

Abul Kalam Azad and Edite M. G. P. Fernandes

Abstract: Constrained nonlinear programming problems involving a nonlinear objective function with inequality and/or equality constraints introduce the possibility of multiple local optima. The task of global optimization is to find a solution where the objective function obtains its most extreme value while satisfying the constraints. Depending on the nature of the involved functions many solution methods have been proposed. Most of the existing population-based stochastic methods try to make the solution feasible by using a penalty function method. However, to find the appropriate penalty parameter is not an easy task. Population-based differential evolution is shown to be very efficient to solve global optimization problems with simple bounds. To handle the constraints effectively, in this paper, we propose a modified constrained differential evolution that uses self-adaptive control parameters, a mixed modified mutation, the inversion operation, a modified selection and the elitism in order to progress efficiently towards a global solution. In the modified selection, we propose a fitness function based on the global competitive ranking technique for handling the constraints. We test 13 benchmark problems. We also compare the results with the results found in literature. It is shown that our method is rather effective when solving constrained problems.

Paper Nr: 61
Title:

EVOLUTIONARY ALGORITHMS FOR THE IDENTIFICATION OF STRUCTURAL SYSTEMS IN EARTHQUAKE ENGINEERING

Authors:

Anastasia Athanasiou, Matteo De Felice, Giuseppe Oliveto and Pietro S. Oliveto

Abstract: An application of Evolution Strategies (ESs) to the structural identification of base isolation systems in earthquake engineering is presented. The analysis of a test problem considered in the literature clearly shows the effectiveness of ESs for the problem. Simple ESs outperform the previously used methods while state-of-the-art ones, such as the CMA-ES, provide practically exact solutions. The application of the CMA-ES to the real data recorded in 2004, when releasing imposed displacements on a building in Solarino, leads to improved identification results and gives hints of limitations in the model available in literature. Improved models of higher dimensionality are introduced to overcome such limitations. The application of the CMA-ES with the new models leads to improvements of up to 53% compared to the previous solutions in literature. Thus, ESs are shown to be a very powerful tool for the dynamic identification of structural systems and an important aid in the design and evaluation of models of high dimensionality for structure identification.

Paper Nr: 62
Title:

EVOLUTIONARY SEARCH IN LETHAL ENVIRONMENTS

Authors:

Richard Allmendinger and Joshua Knowles

Abstract: In Natural evolution, a mutation may be lethal, causing an abrupt end to an evolving lineage. This fact has a tendency to cause evolution to “prefer” mutationally robust solutions (which can in turn slow innovation), an effect that has been studied previously, especially in the context of evolution on neutral plateaux. Here, we tackle related issues but from the perspective of a practical optimization scenario. We wish to evolve a finite population of entities quickly (i.e. improve them), but when a lethal solution (modelled here as one below a certain fitness threshold) is evaluated, it is immediately removed from the population and the population size is reduced by one. This models certain closed-loop evolution scenarios that may be encountered, for example, when evolving nano-technologies or autonomous robots. We motivate this scenario, and find that evolutionary search performs best in a lethal environment when limiting randomness in the solution generation process, e.g. by using elitism, above-average selection pressure, a less random mutating operator, and no or little crossover. For NKa landscapes, these strategies turn out to be particularly important on rugged and non-homogeneous landscapes (i.e. for large K and a).

Paper Nr: 64
Title:

EVOLUTIVE AND ACO STRATEGIES FOR SOLVING THE MULTI-DEPOT VEHICLE ROUTING PROBLEM

Authors:

H. I. Calvete, C. Galé and M. J. Oliveros

Abstract: This paper addresses the multi-depot vehicle routing problem. This problem involves designing a set of routes in order to deliver goods from several depots to a set of geographically dispersed customers. For solving this problem, we propose two different approaches. Both have in common the use of an Ant Colony Optimization algorithm to construct the routes from each depot. The approaches differ in the manner in which depots are dealt with in terms of how customers are assigned to depots. In the first method, called ACO-MDVRP, the customer assignment process is controlled by the ant colony by adding a super-depot which is connected with each depot by arcs with zero unit cost. The second method, called GA-MDVRP, is a hybrid algorithm in the sense that an Ant Colony Optimization algorithm is embedded in a genetic algorithm. In order to construct a feasible solution, the procedure uses a genetic algorithm to assign customers to depots. Then, under the given data on each depot, the corresponding vehicle routing problems are solved by using Ant Colony Optimization.

Paper Nr: 70
Title:

SKELETAL ALGORITHMS

Authors:

Michal R. Przybylek

Abstract: This paper introduces a new kind of evolutionary method, called “skeletal algorithm”, and shows its sample application to process mining. The basic idea behind the skeletal algorithm is to express a problem in terms of congruences on a structure, build an initial set of congruences, and improve it by taking limited unions/intersections, until a suitable condition is reached. Skeletal algorithms naturally arise in the context of data/process minig, where the skeleton is the “free” structure on initial data and a congruence corresponds to similarities in data. In such a context, skeletal algorithms come equipped with fitness functions measuring the complexity of a model. We examine two fitness functions for our sample problem — one based on Minimum Description Length Principle, and the other based on Bayesian Interpretation.

Paper Nr: 82
Title:

A MARKOV-CHAIN-BASED MODEL FOR SUCCESS PREDICTION OF EVOLUTION IN COMPLEX ENVIRONMENTS

Authors:

Lukas König, Sanaz Mostaghim and Hartmut Schmeck

Abstract: In this paper, a theoretical and experimental study of the influence of environments on the selection process in evolutionary swarm robotics is conducted. The theoretical selection model is based on Markov chains. It is proposed to predict the success rate of evolutionary runs which are based on a selection mechanism depending on implicit environmental properties as well as an explicit fitness function. In the experiments, the interaction of explicit and implicit selection is studied and a comparison with the model prediction is performed. The results indicate that the model prediction is accurate for the studied cases.

Short Papers
Paper Nr: 20
Title:

A MEMETIC ALGORITHM FOR A CONTINUOUS CASE OF THE BERTH ALLOCATION PROBLEM

Authors:

Geraldo Regis Mauri, Larice Nogueira de Andrade and Luiz Antonio Nogueira Lorena

Abstract: This work presents a Memetic Algorithm heuristic to solve a continuous case of the Berth Allocation Problem (BAP). The BAP deals with programming and allocating ships to berthing areas along a quay. In general, the continuous case considers that ships have different lengths and can moor anywhere along the quay. However, we consider a quay divided in berths that have limited areas and different equipments to handle the ships. So, we must to assign the ships to berths and determine the berthing time and position for each ship. We treat the ships as rectangles to be placed into a space × time area avoiding overlaps and satisfying time window constraints. Our MA uses a Simulated Annealing (SA) as the local search mechanism, and SA is also applied in a stand alone way to solve the BAP. A two-phase heuristic is also presented to compute the berthing time and position for all of ships during MA and SA execution. Computational results are performed on a set of instances proposed in the literature and new best-known solutions are presented.

Paper Nr: 21
Title:

A NEW DEVELOPMENT DESIGN CAE EMPLOYMENT MODEL - Applying Numerical Simulation to Automobile Bottleneck Technology

Authors:

Kakuro Amasaka

Abstract: With the rapid move towards global production, it has become increasingly critical for manufacturers to drastically cut back on the time it takes to move a product from design to production while ensuring quality. This research addresses the necessity reforming the business processes associated with development design in particular, proposing a “New Development Design CAE Employment Model” using four core models: the “Highly Reliable CAE Analysis Technology Component Model”, the “Highly Precise CAE Analysis Model”, the “Total QA High Cyclization Business Process Model”, and the “Intellectual Customer Data Collection/Analysis Integrated Model” that takes manufacturers away from conventional preproduction and prototype testing methods and towards a better predictive evaluation method. The effectiveness of the model is verified by successfully applying it to the technological problem “automotive transaxle oil seal leakage” of development design bottlenecks at auto manufacturers.

Paper Nr: 27
Title:

OPTIMIZATION OF STRUCTURE OF FUZZY-NEURAL SYSTEMS USING COEVOLUTIONARY ALGORITHM

Authors:

Zikrija Avdagic, Samir Omanovic, Emir Buza and Belma Cardakovic

Abstract: This paper is related to a research of modelling fuzzy-neural systems using the coevolutionary algorithm, and has the focus on advantages of using the coevolutionary algorithm for system structure optimization. In the context of this work, the term fuzzy-neural system defines the system that can be used as the fuzzy system with all its functionalities or as the neural network with all its functionalities. The hybridization of fuzzy logic, neural networks and coevolutionary algorithm and its architecture are presented in general, and the role of the coevolutionary algorithm in structure optimization is described in details. Results of testing with Iris Database, from UCI Machine Learning Repository are also presented. Tests performed during the research supports the conclusion that usage of the coevolutionary algorithm for the fuzzy-neural system’s structure optimization is very efficient.

Paper Nr: 28
Title:

CELLULAR DIFFERENTIATION-BASED APPROACH FOR DISTRIBUTED SYSTEMS

Authors:

Ichiro Satoh

Abstract: This paper proposes a bio-inspired framework for adapting software agents on distributed systems. It is unique to other existing approaches for software adaptation because it introduces the notions of differentiation, dedifferentiation, and cellular division in cellular slime molds, e.g., dictyostelium discoideum, into real distributed systems. When an agent delegates a function to another agent coordinating with it, if the former has the function, this function becomes less-developed and the latter’s function becomes well-developed. The framework was constructed as a general-purpose middleware system and allowed us to define agents as Java objects. We present several evaluations of the framework in a distributed system instead of any simulation-based systems.

Paper Nr: 30
Title:

PATTERN CLUSTERING USING ANTS COLONY, WARD METHOD AND KOHONEN MAPS

Authors:

Rosangela Villwock, Maria Teresinha Arns Steiner and Paulo Henrique Siqueira

Abstract: The goal of this paper is to propose improvements to the ACA (Ant-based Clustering Algorithm), and evaluate its performance relative to the Ward Method; to the One-dimensional Kohonen Maps and to the ACAM (Ant-based Clustering Algorithm Modified) algorithm. The algorithm containing the improvements will be referred here by “proposed” algorithm. Its the main changes were: the introduction of a comparison between the probability of dropping a pattern at the position chosen randomly and the probability of dropping this pattern at its current position; the introduction of an evaluation of the probability of a neighboring position when the decision to drop a pattern is positive and the cell in which the pattern should be dropped is occupied; and the replacement of the pattern carried by an ant, in case this pattern is not dropped within 100 consecutive iterations. To assess the performance of the proposed algorithm three real and public databases were used (Iris, Wine and Pima Indians Diabetes). The results showed superiority of the proposed algorithm when comparing with the ACAM algorithm in two of the three databases.

Paper Nr: 31
Title:

COLLECTIVE DECISION UNDER PARTIAL OBSERVABILITY - A Dynamic Local Interaction Model

Authors:

Arnaud Canu and Abdel-Illah Mouaddib

Abstract: This paper introduces DyLIM, a new model to describe partially observable multiagent decision making problems under uncertainty. DyLIM deals with local interactions amongst the agents, and build the collective behavior from individual ones. Usually, such problems are described using collaborative stochastic games, but this model makes the strong assumption that agents are interacting all the time with all the other agents. With DyLIM, we relax this assumption to be more appropriate to real-life applications, by considering that agents interact sometimes with some agents. We are then able to describe the multiagent problem as a set of individual problems (sometimes interdependent), which allow us to break the combinatorial complexity. We introduce two solving algorithms for this model and we evaluate them on a set of dedicated benchmarks. Then, we show how our approach derive near optimal policies, for problems involving a large number of agents.

Paper Nr: 32
Title:

A CLONAL SELECTION ALGORITHM TO INVESTIGATE DIVERSE SOLUTIONS FOR THE RELIABLE SERVER ASSIGNMENT PROBLEM

Authors:

Abdullah Konak and Sadan Kulturel-Konak

Abstract: A reliable server assignment (RSA) problem in networks is defined as determining a deployment of identical servers on a network to maximize a measure of service availability. In this paper, a simulation optimization approach is introduced based on a Monte Carlo simulation and embedded into a Clonal Selection Algorithm (CSA) to find diverse solutions for the RSA problem, which is important in simulation optimization. The experimental results show that the simulation embedded-CSA is an effective heuristic method to discover diverse solutions to the problem.

Paper Nr: 42
Title:

PARALLEL IMPLEMENTATION AND COMPARISON OF TWO UAV PATH PLANNING ALGORITHMS

Authors:

Vincent Roberge, Mohammed Tarbouchi and Gilles Labonté

Abstract: The development of autonomous Unmanned Aerial Vehicles (UAVs) is of high interest to many governmental and military organizations around the world. An essential aspect of UAV autonomy is the ability for automatic path planning. In this paper, we use the genetic algorithm (GA) and the particle swarm optimization algorithm (PSO) to cope with the complexity of the problem and compute feasible and quasi-optimal trajectories for fixed wing UAVs in a complex 3D environment while considering the dynamic properties of the vehicle. The characteristics of the optimal path are represented in the form of a multi-objective cost function that we developed. The paths produced are composed of line segments, circular arcs and vertical helices. We reduce the execution time of our solutions by using the “single-program, multiple-data” parallel programming paradigm and we achieve real-time performance on standard COTS multi-core CPUs. After achieving a quasi-linear speedup of 7.3 on 8 cores and an execution time of 10 s for both algorithms, we conclude that by using a parallel implementation on standard multicore CPUs, real-time path planning for UAVs is possible. Moreover, our rigorous comparison of the two algorithms shows, with statistical significance, that the GA produces superior trajectories to the PSO.

Paper Nr: 45
Title:

APPLYING COMPUTATIONAL INTELLIGENCE APPROACHES TO THE STAFF SCHEDULING PROBLEM

Authors:

Vasileios Perlis, Charilaos Akasiadis, Konstantinos Theofilatos, Grigorios N. Beligiannis and Spyridon D. Lykothanasis

Abstract: Staff scheduling for public organizations and institutions is an NP-hard problem and many heuristic optimization approaches have already been developed to solve it. In the present paper, we present two meta-heuristic computational intelligence approaches (Genetic Algorithms and Particle Swarm Optimization) for solving the Staff scheduling problem. A general model for the problem is introduced and it can be used to express most of real-life preferences and employee requirements or work regulations and cases that do not include overlapping shifts. The Genetic Algorithm (GA) is parameterized, giving the user the opportunity to apply many different kinds of genetic operators and adjust their probabilities. Classical Particle Swarm Optimization (PSO) is modified in order to be applicable in such problems, a mutation operator has been added and the produced PSO variation is named dPSOmo (discrete Particle Swarm Optimization with mutation operator). Both methods are tested in three different cases, giving acceptable results, with the dPSOmo outperforming significantly the GA approach. The PSO variation results are very promising, encouraging further research efforts.

Paper Nr: 46
Title:

USING AESTHETIC LEARNING MODEL TO CREATE ART

Authors:

Yang Li, Chang-Jun Hu and Jing-Qin Pang

Abstract: An aesthetic learning model is proposed that applies evolutionary algorithm to generate art. The model is evaluated using an evolutionary art system by human subjects. The advantages of the model is that it helps user to automate the process of image evolution by learning the user’s preferences and applying the knowledge to evolve aesthetical images. This paper implements four categories of aesthetic metrics to establish user’s criteria. In addition to evolutionary images, external artworks are also included to guide evolutionary process towards more interesting paths. Then we described an evolutionary art system which adopted the aesthetic model in detail. Last, we evaluate the aesthetic learning model in several independent experiments to show the efficiency at predicting user’s preferences.

Paper Nr: 47
Title:

CYLINDRICAL CONSTRAINT EVOLUTIONARY ALGORITHM FOR MULTIOBJECTIVE OPTIMIZATION

Authors:

Tohid Erfani and Sergei V. Utyuzhnikov

Abstract: This paper introduces a new iterative evolutionary algorithm, which is able to provide an evenly distributed set of solutions in multiobjective context. The method is different from the other evolutionary algorithms in two perspectives. First, instead of density information incorporated to find a diverse set of solutions, a hypercylinder is introduced as a new constraint to the problem. Searching for the solution within this hypercylinder guarantees the evenly generated solutions at the end of the optimization process. Second, a fitness function is constructed to handle the problem constraints and meanwhile minimize the distance of the solution to the true optimum frontier. In addition, the method is developed in such a way that it can be easily implemented in searching the preferable region of the search space. The algorithm behaviour is tested on different test cases and the results are compared in both convergence and diversity to those of other well known approaches to demonstrate the efficacy of the proposed method.

Paper Nr: 49
Title:

A HYBRID GENETIC ALGORITHM FOR THE AIRLINE CREW ASSIGNMENT PROBLEM

Authors:

Wagner P. Gomes and Nicolau D. F. Gualda

Abstract: A typical problem related to airline crew management consists of optimally assigning the required crew members to flights for a period of time, while complying with labor regulations, safety rules and policies of the airline. This problem, called the Crew Assignment Problem (CAP), is a combinatorial optimization problem. Hence, a Hybrid Genetic Algorithm (HGA) associated with a constructive heuristic and a local search was developed. The HGA was tested and applied to solve instances related to a Brazilian airline.

Paper Nr: 51
Title:

CONVERGENCE PROPERTIES OF TWO (μ+l) EVOLUTIONARY ALGORITHMS ON ONEMAX AND ROYAL ROADS TEST FUNCTIONS

Authors:

Aram Ter-Sarkissov and Stephen Marsland

Abstract: We present a number of bounds on convergence time for two elitist population-based Evolutionary Algorithms using a recombination operator k-Bit-Swap and a mainstream Randomized Local Search algorithm. We study the effect of distribution of elite species and population size.

Paper Nr: 53
Title:

THE MULTIDIMENSIONAL 0-1 KNAPSACK PROBLEM - A New Heuristic Algorithm Combined with 0-1 Linear Programming

Authors:

Anikó Csébfalvi and György Csébfalvi

Abstract: In this paper, we present a new population-based heuristic for the multidimensional 0-1 knapsack problem (MKP) which is combined with 0-1 linear programming to improve the quality of the final heuristic solution. The MKP is one of the most well known NP-hard problems and has received wide attention from the operational research community during the last four decades. MKP arises in several practical problems such as the capital budgeting problem, cargo loading, cutting stock problem, and computing processors allocation in huge distributed systems. Several different techniques have been proposed to solve this problem. However, according to its NP-hard nature, exact methods are unable to find optimal solutions for larger problem instances. Heuristic methods have become the alternative, and the last generation of them, are being successfully applied to this problem. Hence, in practice, heuristic algorithms to generate near-optimal solutions for larger problem instances are of special interest. The presented hybrid heuristic approach exploits the fact, that using a state-of-the-art solver a small binary linear programming (BLP) problem can be solved within reasonable time. The computational experiments show that the presented combined approach produces highly competitive results in significantly shorter run-times than the previously described approaches.

Paper Nr: 55
Title:

INTEGRATED OPTIMIZATION OF PRODUCT DESIGN CONCEPT AND PRODUCT LIFECYCLE SCENARIO BASED ON GENETIC ALGORITHM

Authors:

Masakazu Kobayashi and Masatake Higashi

Abstract: Due to rise of environmental awareness in recent years, companies are required to assess and reduce environmental burdens of their products. However, in practical product development, since not only environmental burdens but also product characteristics such as performance and cost need to be simultaneously considered for creating attractive products, designers are forced to take a great deal of time and effort to balance them at a higher level at every stage of product development. In response to this, this paper proposes an integrated method for optimizing product design concept and product lifecycle scenario for supporting conceptual design phase. The proposed method combines integrated optimization of functional / layout design which we developed in the previous researches and lifecycle assessment (LCA). Using the proposed method, optimal functional structure, components / parts layout and lifecycle scenario that balance product characteristics and environmental burdens at a higher level can be obtained.

Paper Nr: 58
Title:

ELITIST BEHAVIOR IN DIFFERENTIAL ANT-STIGMERGY ALGORITHM

Authors:

Adrian Emanoil Şerbencu, Viorel Minzu, Adriana Şerbencu and Daniela Cernega

Abstract: This paper proposes two type of elitist variants for the differential ant-stigmergy algorithm (DASA). An elitist behaviour is inserted in genetic algorithms by keeping the best solution found in the population used at next generation. Another way to insert elitist behaviour in algorithms that construct solution is to use the most attractive components in order to obtain good quality solution, and may be the optimal ones. Based on particularities of differential ant-stigmergy algorithm this two type of elitist behaviour was successfully applied to studied algorithm. In this paper the efficiency of the proposed elitist variants of DASA algorithms is analyzed using experimental results. The analysis is applied to six benchmark functions from the class of high-dimensional real-parameter optimization problems.

Paper Nr: 63
Title:

SYNTHESIZING PHEROMONE AGENTS FOR SERIALIZATION IN THE DISTRIBUTED ANT COLONY CLUSTERING

Authors:

Munehiro Shintani, Shawn Lee, Munehiro Takimoto and Yasushi Kambayashi

Abstract: This paper presents effective extensions of our previously proposed algorithm for controlling multiple robots. The robots are connected by communication networks, and the controlling algorithm is based on a specific Ant Colony Clustering (ACC) algorithm. Unlike traditional ACC, we implemented the ants as actual mobile software agents that control the mobile robots which are corresponding to objects. The ant agent migrates among robots to look for an available one. Once the ant agent finds an available robot, the robot physically moves along the instructions of the ant agent, instead of being conveyed. We also implemented pheromone as mobile software agents, which attract many robots to some clusters by diffusing themselves through the migration, so that the pheromone agents enable the robots to be efficiently assembled. In our new approach, we take advantage of the pheromone agents not only to assemble the robots but also to serialize them. The serializing property is desirable for particular applications such as gathering carts in the airports. We achieve the property through migrations of the pheromone agents within a cluster and synthesizing them. We have built a simulator based on our algorithm, and conducted numerical experiments to demonstrate the feasibility of our approach.

Paper Nr: 65
Title:

MAGS - An Aco-based Model to Solve the Schedule Generation and Fleet Assignment Integrated Problem

Authors:

Daniel J. Caetano and Nicolau D. F. Gualda

Abstract: Schedule Generation and Fleet Assignment problems usually are solved separately. The integrated solution for both problems, although desirable, leads to large scale models of the NP-Hard class. This article presents a mathematical formulation of this integrated problem along with a new heuristical approach, called MAGS, based on the ACO metaheuristic. Both the exact solution and the one provided by MAGS are obtained and compared for the case of a Brazilian airline. The results have shown the applicability of MAGS to real world cases.

Paper Nr: 67
Title:

RETROVIRAL GENETIC ALGORITHMS - Implementation with Tags and Validation Against Benchmark Functions

Authors:

Alexander V. Spirov and David M. Holloway

Abstract: Classical understandings of biological evolution inspired creation of the entire order of Evolutionary Computation (EC) heuristic optimization techniques. In turn, the development of EC has shown how living organisms use biomolecular implementations of these techniques to solve particular problems in survival and adaptation. An example of such a natural Genetic Algorithm (GA) is the way in which a higher organism’s adaptive immune system selects antibodies and competes against its complement, the development of antigen variability by pathogenic organisms. In our approach, we use operators that implement the reproduction and diversification of genetic material in a manner inspired by retroviral reproduction and a genetic-engineering technique known as DNA shuffling. We call this approach Retroviral Genetic Algorithms, or retroGA (Spirov and Holloway, 2010). Here, we extend retroGA to include: (1) the utilization of tags in strings; (2) the capability of the Reproduction-Crossover operator to read these tags and interpret them as instructions; and (3), as a consequence, to use more than one reproductive strategy. We validated the efficacy of the extended retroGA technique with benchmark tests on concatenated trap functions and compared these with Royal Road and Royal Staircase functions.

Paper Nr: 77
Title:

OPTIMIZING TOPOLOGY OF THE POWER DISTRIBUTION NETWORK USING GENETIC ALGORITHM

Authors:

Martin Paar, Lukas Oliva and Jana Jilkova

Abstract: The article deals with application of genetic algorithm to the minimization of the operational cost of distribution network. The optimization is achieved by the change of the network topology or reconfiguration in terms of power network terminology. The optimization algorithm changes the setup of the switchgears to get such a configuration which leads to the minimum costs for power loss and minimum financial penalization for not delivering the electric power and therefore violating standards of the power supply continuity. The Finnish continuity standard at systems level and Portuguese continuity standard at single-customer level were selected for evaluation of the impact of power supply discontinuity and their impact is compared and discussed. The Genetic algorithm is designed as multi-attribute optimization with mono-objective evaluation using binary coding. Also since the optimization involves reconfiguration of the topology a simple solution to cope with invalid solution is described and discussed.

Paper Nr: 96
Title:

RECENT ADVANCES AND APPLICATIONS OF THE THEORY OF STOCHASTIC CONVEXITY. APPLICATION TO COMPLEX BIO-INSPIRED AND EVOLUTION MODELS

Authors:

Eva Maria Ortega and Jose Alonso

Abstract: The theory of stochastic convexity is widely recognised as a framework to analyze the stochastic behaviour of parameterized models by different notions in both univariate and multivariate settings. These properties have been applied in areas as diverse as engineering, biotechnology, and actuarial science. Consider a family of parameterized univariate or multivariate random variables {X(q)|q ∈ T} over a probability space (W,Á,Pr), where the parameter q usually represents some distribution moments. Regular, sample-path, and strong stochastic convexity notions have been defined to intuitively describe how the random objects X(q) grow convexly (or concavely) concerning their parameters. These notions were extended to the multivariate case by means of directionally convex functions, yielding the concepts of stochastic directional convexity for multivariate random vectors and multivariate parameters. We aim to explain some of the basic concepts of stochastic convexity, to discuss how this theory has been used into the stochastic analysis, both theoretically and in practice, and to provide some of the recent and of the historically relevant literature on the topic. Finally, we describe some applications to computing/communication systems based on bio-inspired models.

Posters
Paper Nr: 5
Title:

NURSE SCHEDULING BY COOPERATIVE GA WITH PENALTY COEFFICIENT ADJUSTMENT

Authors:

Makoto Ohki and Hideaki Kinjo

Abstract: This paper describes a penalty adjustment technique for CGA applied to the nurse scheduling problem. The nurse scheduling is very complex task, because many requirements must be considered. In real hospital, some changes of the schedule often happen. Such a change of the shift schedule yields various inconveniences. Such an inconvenience causes the fall of the nursing level of the whole nurse organization. Furthermore, reoptimization of the schedule including such changes is very hard task and requires very long computing time. To improve this problem, we propose a technique to adjust penalty coefficient through the optimization.

Paper Nr: 6
Title:

VARYING DIMENSIONAL PARTICLE SWARM OPTIMIZERS FOR DESIGN OF SWITCHING SIGNALS

Authors:

Toshimichi Saito and Kengo Kawamurae

Abstract: This paper presents varying dimensional particle swarm optimizers for design of switching signals in circuits and systems. The particle position and dimension correspond to the switching phase and the number of switches, respectively. The dimension can vary depending on an objective function in the search process, i.e., the number of switches is adjustable automatically. The algorithm is defined for a multi-objective problem described by the hybrid fitness consisting of analog functions and digital logic. The algorithm is defined in a general form and the performance is investigated in an example: design of a switching signal for single phase inverters with a two-objective problem corresponding to total harmonic distortion and power sufficiency.

Paper Nr: 8
Title:

NESTING DISCRETE PARTICLE SWARM OPTIMIZERS FOR MULTI-SOLUTION PROBLEMS

Authors:

Masafumi Kubota and Toshimichi Saito

Abstract: This paper studies a discrete particle swarm optimizer for multi-solution problems. The algorithm consists of two stages. The first stage is global search: the whole search space is discretized into the local sub-regions each of which has one approximate solution. The sub-region consists of subsets of lattice points in relatively rough resolution. The second stage is local search. Each subregion is re-discretized into finer lattice points and the algorithm operates in all the subregions in parallel to find all approximate solutions. Performing basic numerical experiment, the algorithm efficiency is investigated.

Paper Nr: 12
Title:

HYBRID APPROACH FOR IMPROVED PARTICLE SWARM OPTIMIZATION USING ADAPTIVE PLAN SYSTEM WITH GENETIC ALGORITHM

Authors:

Pham Ngoc Hieu and Hiroshi Hasegawa

Abstract: To reduce a large amount of calculation cost and to improve the convergence to the optimal solution for multi-peak optimization problems with multi-dimensions, we purpose a new method of Adaptive plan system with Genetic Algorithm (APGA). This is an approach for Improved Particle Swarm Optimization (PSO) using APGA. The hybrid strategy using APGA is introduced into PSO operator (H-PSOGA) to improve the convergence towards the optimal solution. The H-PSOGA is applied to some benchmark functions with 20 dimensions to evaluate its performance.

Paper Nr: 15
Title:

ANT COLONY OPTIMIZATION FOR THE UNEQUAL-AREA FACILITY LAYOUT PROBLEM

Authors:

Sadan Kulturel-Konak and Abdullah Konak

Abstract: In this paper, an ant colony optimization (ACO) approach is proposed to solve the Facility Layout Problem (FLP) with unequal area departments. The flexible bay structure (FBS) is relaxed by allowing empty spaces in bays, which results in more flexibility while assigning departments in bays. The comparative results show that the ACO approach is very promising.

Paper Nr: 22
Title:

EVOLVING TAKAGI-SUGENO-KANG FUZZY SYSTEMS USING MULTI POPULATION GRAMMAR-GUIDED GENETIC PROGRAMMING

Authors:

Athanasios Tsakonas and Bogdan Gabrys

Abstract: This work proposes a novel approach for the automatic generation and tuning of complete Takagi-Sugeno-Kang fuzzy rule based systems. The examined system aims to explore the effects of a reduced search space for a genetic programming framework by means of grammar guidance that describes candidate structures of fuzzy rule based systems. The presented approach applies context-free grammars to generate individuals and evolve solutions through the search process of the algorithm. A multi-population approach is adopted for the genetic programming system, in order to increase the depth of the search process. Two candidate grammars are examined in one regression problem and one system identification task. Preliminary results are included and discussion proposes further research directions.

Paper Nr: 24
Title:

GENETIC SOLUTIONS TO MIXED H2/H∞ PROBLEMS - Limits of Performance

Authors:

Gustavo Sánchez, Miguel Strefezza and Minaya Villasana

Abstract: One of the most relevant problems for control engineers is the so-called “mixed H2/H∞”. To solve it, different convexifying strategies became popular in the later 1990s, mainly based on Linear Matrix Inequalities (LMIs). On the other hand, genetic algorithms have also been applied for H2/H∞ synthesis. Indeed, several authors agree that they are able to find good solutions to this important control problem. However, in most of the published papers, only low-order SISO models have been considered. In the present paper a LMI-based algorithm is compared against a genetic algorithm, with respect to three performance indicators: Set Coverage, Maximum Distance and Efficient Set Spacing. Five open-loop MIMO models extracted from COMPleib are studied, for which the degree varies between 5 and 10. Based on numerical results, the genetic algorithm is not able to improve LMI solutions for problems with more than 42 variables, restricted to a budget of 20.000 function evaluations.

Paper Nr: 33
Title:

FUZZIFICATION OF THE RESOURCE-CONSTRAINED PROJECT SCHEDULING PROBLEM - A Fight against Nature

Authors:

Anikó Csébfalvi, György Csébfalvi and Sándor Danka

Abstract: In a recent article (Bhaskar et al., 2011) the authors proposed a heuristic method for the resource-constrained project scheduling problem (RCPSP) with fuzzy activity times. The apropos of this state-of-the-art work, we try identify and illuminate a popular misconception about fuzzification of RCPSP. The main statement of their approach, similarly to the other fuzzy approaches, is simple: the project completion time can be represented by a "good" fuzzy number. This statement is naturally true: in a practically axiomatic fuzzy thinking and model building environment, using only fuzzy operators and rules, we get a fuzzy output from the fuzzy inputs. But the real problem is deeper. The possibilistic (fuzzy) approach, traditionally, defines itself against the probabilistic approach, so in the "orthodox" fuzzy community everything is prohibited which is connected to somehow to the probability theory. For example, the Central Limit Theorem (CLT) is in the taboo list of this community. We have to emphasize, CLT is a humanized description of a miracle of nature. When we fight against CLT, we fight against nature. The situation in the "neologist" fuzzy community is not better, because they try to redefine somehow the probability theory within the fuzzy approach without using "forbidden" statistical terms. In this paper, we will show that the nature is working totally independently from our "magic" abstractions. According to the robustness of CLT, the distribution function of the completion time of real-size projects remains nearly normal, which is a manager friendly, natural and usable result. An abstraction and its "natural" operators are unable to modify the order of nature. When we want to add a practical scheduling method to the project managers we have to destroy the borders between the probabilistic and possibilistic approaches and have to define a "unified" approach to decrease the gap between scientific beliefs and reality. In this paper we present a unified (probabilistic/possibilistic) model for RCPSP with uncertain activity durations and a concept of a heuristic approach connected to the theoretical model. It will be shown, that the uncertainty management can be built into any heuristic algorithm developed to solve RCPSP with deterministic activity durations. The essence and viability of our unified model will be illustrated by a fuzzy example presented in the recent fuzzy RCPSP literature.

Paper Nr: 38
Title:

INSENSITIVE DIFFERENTIAL EVOLUTION AND MULTI-SOLUTION PROBLEMS

Authors:

Itsuki Handa and Toshimichi Saito

Abstract: This paper presents an insensitive differential evolution for multi-solution problems. The algorithm consists of global and local searches. In the global search, the algorithm tries to construct local sub-regions (LSRs) each of which includes either solution. In the local search, the algorithm operates on all the LSRs in parallel and tries to find all the approximate solutions. The algorithm has a key parameter that controls the algorithm insensitivity. If the insensitivity is suitable, the algorithm can construct all the LSRs before trapping into either solution and can find all the solutions. Performing basic numerical experiments where parameters are adjusted by trial-and-errors, basic performance of the algorithm is investigated.

Paper Nr: 40
Title:

EXPERIMENTAL COMPARISON OF SELECTED TYPES OF PARALLEL EVOLUTIONARY ALGORITHMS

Authors:

Ivan Sekaj, Marek Linder and Daniel Pernecký

Abstract: Parallel evolutionary algorithms are able to improve the performance of simple evolutionary algorithms which use a single population. Their characteristics and performance depend on their architectures and other factors and parameters. In our contribution we present some viewpoints of classification and we demonstrate experimentally the influence of selected factors such as architecture type, migration topology, migration period, number of migrants, numbers of subpopulations, subpopulation size and others on the performance of these algorithms. This experimental study should help to generalise the properties and behaviour of various types of parallel evolutionary algorithms and help to design algorithms for solving hard search/optimisation problems like modelling of bio-medicine processes, optimisation of pharmaceutical dosing, optimisation of large technological and construction tasks etc.

Paper Nr: 44
Title:

GENERATIVE DESIGN EXPLORATION FRAMEWORK BASED ON SUBJECTIVE EVALUATION

Authors:

Jia Cui and Ming Xi Tang

Abstract: Application of evolutionary computation in design, supporting artificial intelligence and design inspiration, requires a good understanding of design process. However, obtaining a creative design solution with subjective evaluation is the barrier of traditional evolutionary mechanisms. In this paper, a novel aesthetic evaluation model connecting subjective and objective space is introduced, and an exploration algorithm combining human cognition and preference is presented, which can support design exploration to generate new design solutions more effectivelly and intelligently.

Paper Nr: 54
Title:

COMBINATORIAL IMPLEMENTATION OF A PARAMETER-LESS EVOLUTIONARY ALGORITHM

Authors:

Gregor Papa

Abstract: The paper presents the combinatorial implementation of an adaptive parameter-less evolutionary-based search. The algorithm is an extension of a basic numerical algorithm that does not need any predefined control parameters values. These values are calculated by the algorithm itself, according to the progress of the search. The efficiency of the proposed autonomous parameter-less algorithm is evaluated by two real-world industrial optimization problems.

Paper Nr: 57
Title:

ACQUISITION OF JUMPING BEHAVIOR ON THE ARTIFICIAL CREATURE UNDER VIRTUAL PHYSICAL ENVIRONMENT

Authors:

Yuta Umemura, Ikuo Suzuki, Masahito Yamamoto and Masashi Furukawa

Abstract: Walking and jumping are very effective movement in a debris area. However, it is difficult to jump successively because it has a lot of difficulties (e.g. controlling the strong power at taking off and suppressing an impact at landing). This paper proposes how to acquire the successive jumping motion. We model an artificial creature like a locust under the physical virtual environment and control it by using Artificial Neural Network (ANN). In order to realize the successive jumping motion, this paper proposes a concept of “Behavior Simple (BS)” and “Behavior Composed (BC)”. The concept of BC is that a complex behavior is composed of plural simple behaviors. We consider that the successive jumping is divided into three BSs, taking off, getting up and returning leg back motion. After three BSs are trained by using the Real-Coded Genetic Algorithm (RCGA) independently, BC is trained by using RCGA as well. Experiments verify that the efficient successive jumping can be acquired.

Paper Nr: 60
Title:

SOME PROBLEMS HANDLED BY PARTICLE SWARM OPTIMIZATION IN AUTOMATIC CONTROL

Authors:

Guillaume Sandou

Abstract: Most of the methods to design automatic control laws rely on the solution to optimization problems. However, straightforward formulations of costs and constraints of these problems are mainly non convex, non smooth or non analytic. That is why the classical approach is to simplify the problem so as to get tractable and exactly solvable optimization problems. The use of direct methods such as metaheuristics is underused in the control community. In this paper, a Particle Swarm Optimization method is used to solve some complex initial problems found in the control field to show the interest in the use of such methods.

Paper Nr: 71
Title:

FALL DETECTION USING BIOLOGIALLY INSPIRED MONITORING - Artificial Immune System in the Area of Assisted Living

Authors:

Sebastian D. Bersch, Djamel Azzi and Rinat Khusainov

Abstract: This position paper supports the use of Artificial Immune System (AIS) in the area of Ambient Assisted Living (AAL). While AIS has been used for anomaly detection and classification in a wide range of applications, little work has been done on using AIS for detecting abnormal behaviour in health monitoring applications. In this paper, we propose to use AIS for fall detection, since falls can be seen as deviations from the normal behaviour. We justify our proposal by analysing research that has been carried out in the past using AIS in different fields and emphasising on the similarities to the area of AAL. The paper also describes the experimental setup that is currently being used for our current and future work.

Paper Nr: 72
Title:

FINDING THE ELECTROMAGNETIC HOMOGENOUS EQUIVALENT OF THE COMPOSITE MATERIAL USING GLOBAL OPTIMIZATION TECHNIQUES TO SOLVE THE INVERSE PROBLEM

Authors:

Jana Jilková

Abstract: The equivalent homogeneous isotropic replacement is computationally efficient way how to enable simulation of the large numeric models of the composite aircrafts for the purpose of precertification electromagnetic compatibility tests to estimate the level of their resistance against the lightning. The paper presents application of two global optimization methods to find an appropriate electromagnetic equivalent of the composite material by homogeneous material to reduce CPU demands of the numeric models of elec¬trically large airplanes for the purpose of electromagnetic compatibility simulations. First, the inverse problem is specified using the already known scattering parameters of the composite material. Afterwards, the global optimization method is applied to find the equivalent with such a value of the complex electromagnetic permittivity to have the impact on the electromagnetic field propagation as close as possible to the original composite material.

Paper Nr: 74
Title:

COOPERATING OF LOCAL SEARCHES BASED HYPERHEURISTIC APPROACH FOR SOLVING TRAVELING SALESMAN PROBLEM

Authors:

Montazeri Mitra, Abbas Bahrololoum, Hossein Nezamabadi-pour, Mahdieh Soleymani Baghshah and Mahdieh Montazeri

Abstract: Until now various heuristic optimization methods have been developed for solving NP-Hard problems. These methods by trading off between exploration and exploitation attempt to find an optimum solution. In this paper, we introduce a new optimization algorithm based on hyper-heuristic for solving TSP. A hyper-heuristic approach has two layers. In low level, we have six local searches and in high level we use Genetic Algorithm. Genetic Algorithm corporate local searches efficiency. The proposed method has high ability to searching in solution space and explores and exploit appropriately. This method exploits space depended on characteristics of the region of the solution space that is currently under exploration and also the performance history of local searches. The proposed method is used to solve TSP and compared with well-known methods. The experimental results confirm the efficiency of the proposed method.

Paper Nr: 75
Title:

A LONG-TERM MEMORY APPROACH FOR DYNAMIC MULTIOBJECTIVE EVOLUTIONARY ALGORITHMS

Authors:

Alan Díaz Manríquez, Gregorio Toscano-Pulido and Ricardo Landa-Becerra

Abstract: A dynamic optimization problem (DOP) may involve two or more functions to be optimized simultaneously, as well as constraints and parameters which can be changed over time, it is essential to have a response approach to react when a change is detected. In the past, several memory-based approaches have been proposed in order to solve single-objective dynamic problems. Such approaches use a long-term memory to store the best known solution found so far before a change in the environment occurs, such that the solutions stored can be used as seeds in subsequent environments. However, when we deal with a Dynamic Multiobjective Problems with a Pareto-based evolutionary approach, it is natural to expect several traded-off solutions at each environment. Hence, it would be prohibitive to incorporate a memory-based methodology into it. In this paper, we propose a viable algorithm to incorporate a long-term memory into evolutionary multiobjective optimization approaches. Results indicate that the proposed approach is competitive with respect to two previously proposed dynamic multiobjective evolutionary approaches.

Paper Nr: 83
Title:

GENERATING WEB TEMPLATE WITH SUITABLE COLORS BASED ON GENETIC ALGORITHM

Authors:

Tuncay Yigit, Ali Günes, Serif Okumus and Melih Orhan

Abstract: In this paper, we present a new approach that generates a web template with compatible colors. This approach uses a genetic algorithm. The system generates random colors for each web template. All templates are showed previews on the screen and then the best template is selected by applying the genetic algorithm. It is converted to Html format and is showed on web browser. It is kept in the database for later use.

Paper Nr: 89
Title:

A PIPELINED BASED FPGA IMPLEMENTATION OF A GENETIC ALGORITHM

Authors:

Nonel Thirer

Abstract: Many problems common to the electrical and electronics field can be solved by finding a target function and its minimum or maximum. For such problems, usually an analytical solution is not implementable, and therefore iterative algorithms are used. One such efficient algorithm is the Genetic Algorithm (GA). The GA imitates the biological evolution process, finding the solution by implementing the “natural selection” principle, which asserts that the strong has higher chances to survive. The GA is an iterative procedure which operates on a population of individuals called "chromosomes" or "possible solutions" (usually represented by a binary code) and performs several processes on the population individuals, in order to produce a new population - the same as in the biological evolution. Using the algorithm on large populations requires substantial hardware resources. Also, naturally, the amount of time necessary to reach a solution increases, due to the greater number of iterations needed. In this paper, we present an FPGA pipelined based method designed to implement a GA, which provides a high-speed solution for large populations, with a minimum of resources. This outcome is obtained by a procedure which operates sequentially with parts of the population. In addition, an immigration unit is defined to provide an efficient communication between these parts in different iterations. Moreover, some possible solutions to improve our method are analyzed.

Paper Nr: 93
Title:

FINDING PATHS CONNECTING TWO PROPER NOUNS USING AN ANT COLONY ALGORITHM

Authors:

Dinesh Hakande

Abstract: Collaborative systems available on the Web allow millions of users to share information through a growing collection of tools and platforms such as wiki- patforms, blogs, and shared forums. With abundant information resources on the Internet such as Wikipedia or the Freebase, we study the connections between two proper nouns. Nevertheless, the problem is a challenging search problem, as information on the Internet is undoubtedly large and full of irrelevant information. In this project, we first parse and mine the entire Freebase database in order to extract the relevant information of proper nouns. Further we apply Ant Colony Optimization method for finding the path that connects two proper nouns together.

Paper Nr: 97
Title:

GEOMETRIC CHARACTERIZATION OF A TARGET ABOVE THE HALF-SPACE INTERFACE USING SUPPORT VECTOR MACHINE

Authors:

Chao Li, Si-Yuan He, Guo-Qing Yin and Guo-Qiang Zhu

Abstract: The geometric parameters of a electrically large square above a rough surface are reconstructed by means of support vector machine (SVM). The SVM input data are the amplitude of backscattered electric fields obtained from the accurate and efficient EM numerical simulation. The aim of our research is to reconstruct the geometric information while using computational resources as reduced as possible. Therefore, how the spatial and frequency diversity affect the reconstruction is analysed with respect to the characteristics of the scattered fields. Numerical experiments show that it is feasible to get an accurate reconstruction result with the backscattered multi-frequency data collected at just a few observation points which are specially selected based on scattering characteristics.