Skip to main content

2008 | Buch

Nature Inspired Cooperative Strategies for Optimization (NICSO 2007)

herausgegeben von: Natalio Krasnogor, Giuseppe Nicosia, Mario Pavone, David Pelta

Verlag: Springer Berlin Heidelberg

Buchreihe : Studies in Computational Intelligence

insite
SUCHEN

Über dieses Buch

Biological and natural processes have been a continuous source of inspiration for the sciences and engineering. For instance, the work of Wiener in cybernetics was influenced by feedback control processes observable in biological systems; McCulloch and Pitts description of the artificial neuron was instigated by biological observations of neural mechanisms; the idea of survival of the fittest inspired the field of evolutionary algorithms and similarly, artificial immune systems, ant colony optimisation, automated self-assembling programming, membrane computing, etc. also have their roots in natural phenomena.

The second International Workshop on Nature Inspired Cooperative Strategies for Optimization (NICSO), was held in Acireale, Italy, during November 8-10, 2007. The aim for NICSO 2007 was to provide a forum were the latest ideas and state of the art research related to cooperative strategies for problem solving arising from Nature could be discussed. The contributions collected in this book were strictly peer reviewed by at least three members of the international programme committee, to whom we are indebted for their support and assistance. The topics covered by the contributions include several well established nature inspired techniques like Genetic Algorithms, Ant Colonies, Artificial Immune Systems, Evolutionary Robotics, Evolvable Systems, Membrane Computing, Quantum Computing, Software Self Assembly, Swarm Intelligence, etc.

Inhaltsverzeichnis

Frontmatter
A Preliminary Study of Fitness Inheritance in Evolutionary Constrained Optimization

This document presents a proposal to incorporate a fitness inheritance mechanism into an Evolution Strategy used to solve the general nonlinear programming problem. The aim is to find a trade-off between a lower number of evaluations of each solution and a good performance of the approach. A set of test problems taken from the specialized literature was used to test the capabilities of the proposed approach to save evaluations and to maintain a competitive performance.

Efrén Mezura-Montes, Lucía Muñoz-Dávila, Carlos A. Coello Coello
Probabilistically Guided Prefix Gene Expression Programming

Over the years there has been an increasing interest in probabilistically oriented Evolutionary Algorithms (EAs), but it has not been until recently that these innovative methods have been collectively recognized and achieved an independent status. By eliminating the traditionally employed genetic operators, these probabilistic EAs have been forced to adopt an alternative approach, and in the case of Estimation of Distribution Algorithms (EDAs), probabilistic graphical models have become the favored substitute. In this paper, we propose to utilize a previously overlooked probabilistic model known as Hidden Markov Models (HMMs). But preferring not to completely abandon the biologically inspired genetic operations, we largely ignore the classical learning algorithms used to train HMMs, and instead use Differential Evolution (DE) to evolve the underlying numerical parameters of the chosen probabilistic model. The evolved HMMs are then used to generate Prefix Gene Expression Programming (PGEP) chromosomes which encode candidate solutions, and thus provide feedback to guide this proposed evolutionary search process. Finally, benchmarking on a set of symbolic function regression problems has been conducted in order to compare this novel approach to the existing PGEP method.

Brian M. Cerny, Chi Zhou, Weimin Xiao, Peter C. Nelson
Flocking-based Document Clustering on the Graphics Processing Unit

Analyzing and grouping documents by content is a complex problem. One explored method of solving this problem borrows from nature, imitating the flocking behavior of birds. Each bird represents a single document and flies toward other documents that are similar to it. One limitation of this method of document clustering is its complexity

O

(

n

2

). As the number of documents grows, it becomes increasingly difficult to receive results in a reasonable amount of time. However, flocking behavior, along with many naturally inspired algorithms such as ant colony optimization and particle swarm optimization, are highly parallel and have found increased performance on expensive cluster computers. In the last few years, the graphics processing unit (GPU) has received attention for its ability to solve highlyparallel and semi-parallel problems much faster than the traditional sequential processor. Some applications see a huge increase in performance on this new platform. The cost of these high-performance devices is also marginal when compared with the price of cluster machines. In this paper, we have conducted research to exploit this architecture and apply its strengths to the document flocking problem. Our results highlight the potential benefit the GPU brings to many naturally inspired algorithms. Using the CUDA platform from NIVIDA®, we developed a document flocking implementation to be run on the NIVIDA® GEFORCE 8800. Additionally, we developed a similar but sequential implementation of the same algorithm to be run on a desktop CPU. We tested the performance of each on groups of news articles ranging in size from 200 to 3000 documents. The results of these tests were very significant. Performance gains ranged from three to nearly five times improvement of the GPU over the CPU implementation. Our results also confirm that each implementation is of similar complexity, confirming that gains are from the hardware and not from algorithmic benefits. This improvement in runtime makes the GPU a potentially powerful new platform for document analysis.

Jesse St. Charles, Thomas E. Potok, Robert Patton, Xiaohui Cui
Artificial Immune System for Collaborative Spam Filtering

Artificial immune systems (AIS) use the concepts and algorithms inspired by the theory of how the human immune system works. This document presents the design and initial evaluation of a new artificial immune system for collaborative spam filtering.

Collaborative spam filtering allows for the detection of not-previously-seen spam content, by exploiting its bulkiness. Our system uses two novel and possibly advantageous techniques for collaborative spam filtering. The first novelty is local processing of the signatures created from the emails prior to deciding whether and which of the generated signatures will be exchanged with other collaborating antispam systems. This processing exploits both the email-content profiles of the users and implicit or explicit feedback from the users, and it uses customized AIS algorithms. The idea is to enable only good quality and effective information to be exchanged among collaborating antispam systems. The second novelty is the representation of the email content, based on a sampling of text strings of a predefined length and at random positions within the emails, and a use of a custom similarity hashing of these strings. Compared to the existing signature generation methods, the proposed sampling and hashing are aimed at achieving a better resistance to spam obfuscation (especially text additions) — which means better detection of spam, and a better precision in learning spam patterns and distinguishing them well from normal text — which means lowering the false detection of good emails.

Initial evaluation of the system shows that it achieves promising detection results under modest collaboration, and that it is rather resistant under the tested obfuscation. In order to confirm our understanding of why the system performed well under this initial evaluation, an additional factorial analysis should be done. Also, evaluation under more sophisticated spammer models is necessary for a more complete assessment of the system abilities.

Slavisa Sarafijanovic, Jean-Yves Le Boudec
MP Systems and Hybrid Petri Nets

Metabolic P systems are a special class of P systems developed to model dynamics of biological phenomena related to metabolism and signaling transduction in the living cell. The main target of this model is to give an intuitive representation of biochemical pathways in order to facilitate the understanding of biological mechanisms. A new notation of MP graphs [16] will be defined as a graphical representation of MP systems and the graphical user interface we devised to draw MP graphs while working with our MP simulator

Psim

[4] will be described. We will propose also a comparison between MP systems and Hybrid Functional Petri Nets (HFPN) [19], which are an extension of Petri nets for biopathways simulation, to highlight several similarities between the two formalisms. Finally, a definition of equivalence between MP systems and HFPN will conclude the paper.

Alberto Castellini, Vincenzo Manca, Luca Marchetti
Spatial Sorting of Binary Metadata Documents via Nature-Inspired Agents in Grids

This paper introduces Antares, an algorithm that is able to replicate and relocate metadata documents that describe Grid resources. These documents, or “resource descriptors”, are indexed through binary strings that can either represent topics of interest, specifically in the case that resources are text files, or be the result of the application of a locality preserving hash function, that maps similar resources into similar keys. The process is driven by ant-like agents that travel the Grid through P2P interconnections and, by the application of ad hoc probability functions, copy and move descriptors so as to locate descriptors indexed by identical or similar keys into neighbor Grid hosts. The effectiveness of Antares has been verified by event-driven simulation which proves that ant operations allow to achieve replication and spatial sorting of descriptors, regardless of the length of binary keys.

Agostino Forestiero, Carlo Mastroianni, Giandomenico Spezzano
hCHAC-4, an ACO Algorithm for Solving the Four-Criteria Military Path-finding Problem

Algorithms for decision support in the battlefield have to take into account separately all factors with an impact of success: speed, visibility, and consumption of material and human resources. It is usual to combine several objectives, since military commanders give more importance to some factors than others, but it is interesting to also explore and optimize all objectives at the same time, to have a wider range of possible solutions to choose from, and explore more efficiently the space of all possible paths. In this paper we introduce hCHAC-4, the four-objective version of the hCHAC bi-objective ant colony optimization algorithm, and compare results obtained with them and also with some other approaches (extreme and mono-objective ones). It is concluded that this new version of the algorithm is more robust, and covers more efficiently the Pareto front of all possible solutions, so it can be consider as a better tool for military decision support.

A. M. Mora, J. J. Merelo, J. L. J. Laredo, P. A. Castillo, P. G. Sánchez, J. P. Sevilla, C. Millán, J. Torrecillas
Searching Ground States of Ising Spin Glasses with Genetic Algorithms and Binary Particle Swarm Optimization

This paper compares the performance of two evolutionary computation paradigms, genetic algorithms (GAs) and particle swarm optimization (PSO), on the problem of finding ground states of Ising spin glasses. The algorithms are tested on various configurations of

J

= ±1 Ising spin glasses on 2D and 3D lattices with nearest neighbor interactions and periodic boundaries. For configurations on 2D lattices, the performance of GAs and PSO was studied in the absence, as well as in the presence of an external magnetic field. For configurations on 3D lattices, the performance was also studied for different values of the coupling constant

J

. Results indicate that PSO outperforms GAs with respect to the quality of the solutions.

Andrei Băutu, Elena Băutu
A Hybrid System of Nature Inspired Metaheuristics

Nature-inspired metaheuristics are effective strategies for solving optimization problems. However, when trying to solve an instance of this kind of problems it is hard to know which algorithm should be used (algorithm-instance problem). Hybrid systems provide flexible tools that can help to cope with this problem. Therefore a hybrid system based on the intelligent combination of different natureinspired strategies will give more robustness and will allow to find higher quality solutions for different instance types.

In this paper we show the construction of a nature-inspired hybrid system, and analyse a study case.

J. M. Cadenas, M. C. Garrido, E. Muñoz
ESCA: A New Evolutionary-Swarm Cooperative Algorithm

A new hybrid approach called Evolutionary Swarm Cooperative Algorithm (ESCA) based on the collaboration between a particle swarm optimization algorithm and an evolutionary algorithm is proposed. ESCA is designed to track moving optima in dynamic environments. ESCA uses three populations of individuals: two EA populations and one particle swarm population. The EA populations evolve by the rules of an evolutionary multimodal optimization algorithm and are used to maintain the diversity of the search. The particle swarm confers precision to the search process. Using the moving peaks benchmark the efficiency of ESCA is evaluated by means of numerical experiments.

Rodica Ioana Lung, D. Dumitrescu
Stabilizing Swarm Intelligence Search via Positive Feedback Resource Allocation

A novel Swarm Intelligence method for best-fit search, Stochastic Diffusion Search, is presented capable of rapid location of the optimal solution in the search space. Population based search mechanisms employed by Swarm Intelligence methods can suffer lack of convergence resulting in ill defined stopping criteria and loss of the best solution. Conversely, as a result of its resource allocation mechanism, the solutions SDS discovers enjoy excellent stability.

Slawomir Nasuto, Mark Bishop
An Adaptive Metaheuristic for the Simultaneous Resolution of a Set of Instances

Most of the adaptive metaheuristics face the resolution of an instance from scratch, without considering previous runs. Basing on the idea that the computa- tional effort done and knowledge gained when solving an instance should be use to solve similar ones, we present a new metaheuristic strategy that permits the simul- taneous solution of a group of instances. The strategy is based on a set of adaptive operators that works on several sets of solutions belonging to different problem in- stances. The method has been tested on MAX-SAT with sets of various instances obtaining promising results.

Antonio D. Masegosa, Alejandro Sancho Royo, David Pelta
Honey Bees Mating Optimization Algorithm for the Vehicle Routing Problem

This paper introduces a new hybrid algorithmic nature inspired approach based on Honey Bees Mating Optimization, for successfully solving the Vehicle Routing Problem. The proposed algorithm for the solution of the Vehicle Routing Problem, the Honey Bees Mating Optimization (HBMOVRP), combines a Honey Bees Mating Optimization (HBMO) algorithm and the Multiple Phase Neighbor- hood Search — Greedy Randomized Adaptive Search Procedure (MPNS-GRASP) algorithm. The proposed algorithm is tested on a set of benchmark instances and produced very satisfactory results. In all instances, the average quality is less than 0.20%. More specifically, in the fourteen classic instances proposed by Christofides, the average quality is 0.029%. The algorithm is ranked in the 2th place among the most known and effective algorithms in the literature and in the first place among all Nature Inspired methods that have ever been used for this set of instances.

Yannis Marinakis, Magdalene Marinaki, Georgios Dounias
Self-Organization on Silicon: System Integration of a Fixed-Point Swarm Coprocessor

Self-organization is the property of some natural systems to organize themselves without a central coordination unit to perform specific tasks. In this paper, the FPGA prototype of a digital architecture based on a bio-inspired coprocessor for fixed-point array processing is presented. The coprocessor is designed around a tiled architectures resorting to the principles of Swarm Intelligence to perform the assigned tasks with simultaneous adaptive multitasking capabilities exploiting cooperative behaviors and self-organization, without any hardware configuration. Profiling results on some sample application shows performance improvements up to 36 times with respect to the execution on the processor only.

Giovanni Busonera, Stefano Carucci, Danilo Pani, Luigi Raffo
Dynamic Adaptation of Genetic Operators’ Probabilities

We propose a new method of dynamically adapting the probabilities of genetic operators based on the global behavior of the population for each generation. The proposed method consists of two main components which are assigning credits to operators according to the fitness improvements of the individuals, and updating the operators’ probabilities at the onset of each generation. Each of these components can be implemented based on various mathematical approaches; hitherto, two different variants have been investigated. To leverage our previous work we used Gene Expression Programming (GEP) as a benchmark to investigate the power of our novel approach. Nevertheless, this new method can be easily extended to other genetic programming variants. Our experimental results on two symbolic regression problems show that this method follows a faster convergence curve and it improves the performance considerably while imposing an insignificant additional cost.

Fatemeh Vafaee, Peter C. Nelson, Chi Zhou, Weimin Xiao
Cooperative Co-evolution Inspired Operators for Classical GP Schemes

This work is a first step toward the design of a cooperative-coevolution GP for symbolic regression, which first output is a selective mutation operator for classical GP. Cooperative co-evolution techniques rely on the imitation of cooperative capabilities of natural populations and have been successfully applied in various domains to solve very complex optimization problems. It has been proved on several applications that the use of two fitness measures (local and global) within an evolving population allow to design more efficient optimization schemes. We currently investigate the use of a two-level fitness measurement for the design of operators, and present in this paper a selective mutation operator. Experimental analysis on a symbolic regression problem give evidence of the efficiency of this operator in comparison to classical subtree mutation.

Malek Aichour, Evelyne Lutton
Biologically Inspired Clustering: Comparing the Neural and Immune Paradigms

Biological systems have been an inspiration in the development of prototype-based clustering and vector quantization algorithms. The two dominant paradigms in biologically motivated clustering schemes are neural networks and, more recently, biological immune systems. These two biological paradigms are discussed regarding their benefits and shortcomings in the task of approximating multi-dimensional data sets. Further, simulation results are used to illustrate these properties. A class of novel hybrid models is outlined by combining the efficient use of a network topology of the neural models and the power of evolutionary computation of immune system models.

Matti Pöllä, Timo Honkela, Xiao-Zhi Gao
CODEA: An Architecture for Designing Nature-inspired Cooperative Decentralized Heuristics

Cooperative heuristics are those based on several search processes that interchange information while the search is being developed. In a decentralized cooperative strategy, each search process has its own strategy for searching. Several of the most important decentralized cooperative strategies for heuristic solution procedures are nature-inspired. The cooperation scheme states when and how each individual process interchange information with other processes. This work presents CODEA (Cooperative Decentralized Architecture), a flexible type of architecture for implementing and testing Cooperative Decentralized strategies.

Juan Pedro Castro Gutiérrez, Belén Melián Batista, José A. Moreno Pérez, J. Marcos Moreno Vega, Jonatan Ramos Bonilla
Memetic Algorithm for the Generalized Asymmetric Traveling Salesman Problem

The generalized traveling salesman problem (GTSP) is an extension of the well-known traveling salesman problem. In GTSP, we are given a partition of cities into groups and we are required to find a minimum length tour that includes exactly one city from each group. The aim of this paper is to present a new memetic algorithm for GTSP which clearly outperforms the state-of-the-art memetic algorithm of Snyder and Daskin [21] with respect to the quality of solutions. Computational experiments conducted to compare the two heuristics also show that our improvements come at a cost of longer running times, but the running times still remain within reasonable bounds (at most a few minutes). While the Snyder-Daskin memetic algorithm is designed only for the Symmetric GTSP, our algorithm can solve both symmetric and asymmetric instances. Unlike the Snyder-Daskin heuristic, we use a simple machine learning approach as well.

Gregory Gutin, Daniel Karapetyan, Natalio Krasnogor
Particle Swarm Based Collective Searching Model for Adaptive Environment

This report presents a pilot study of an integration of particle swarm algorithm, social knowledge adaptation and multi-agent approaches for modeling the collective search behavior of self-organized groups in an adaptive environment. The objective of this research is to apply the particle swarm metaphor as a model of social group adaptation for the dynamic environment and to provide insight and understanding of social group knowledge discovering and strategic searching. A new adaptive environment model, which dynamically reacts to the group collective searching behaviors, is proposed in this research. The simulations in the research indicate that effective communication between groups is not the necessary requirement for whole self-organized groups to achieve the efficient collective searching behavior in the adaptive environment. One possible application of this research is building scientific understanding of the insurgency in the count-Insurgent warfare.

Xiaohui Cui, Robert M. Patton, Jim Treadwell, Thomas E. Potok
Central Force Optimization: A New Nature Inspired Computational Framework for Multidimensional Search and Optimization

This paper presents Central Force Optimization, a novel, nature inspired, deterministic search metaheuristic for constrained multi-dimensional optimization. CFO is based on the metaphor of gravitational kinematics. Equations are presented for the positions and accelerations experienced by “probes” that “fly” through the decision space by analogy to masses moving under the influence of gravity. In the physical universe, probe satellites become trapped in close orbits around highly gravitating masses. In the CFO analogy, “mass” corresponds to a user-defined function of the value of an objective function to be maximized. CFO is a simple algorithm that is easily implemented in a compact computer program. A typical CFO implementation is applied to several test functions. CFO exhibits very good performance, suggesting that it merits further study.

Richard A. Formato
Social Impact based Approach to Feature Subset Selection

The interactions taking place in the society could be a source of rich inspiration for the development of novel computational methods. This paper describes an application of two optimization methods based on the idea of social interactions. The first one is the Social Impact Theory based Optimizer - a novel method directly inspired by and based on the Dynamic Theory of Social Impact known from social psychology. The second one is the binary Particle Swarm Optimization - well known optimization technique, which could be understood as to be inspired by decision making process in a group. The two binary optimization methods are applied in the area of automatic pattern classification to selection of an optimal subset of classifier’s inputs. The testing is performed using four datasets from UCI repository. The results show the ability of both methods to significantly reduce input dimensionality and simultaneously keep up the generalization ability.

Martin Macaš, Lenka Lhotská, Václav Křemen
Influence of Different Deviations Allowed for Equality Constraints on Particle Swarm Optimization and Differential Evolution

In real-world problems, e.g. when applying worst-case methods to yield analysis, the violation of equality constraints must often be considerably smaller than the remaining deviations commonly allowed in literature of about l

e

–4. In this work it is shown with Particle Swarm Optimization and Differential Evolution that deviations of ≤ l

e

–7 already present difficulties, and that for deviations of ≤ l

e

–11 the optimum is hardly found at all for the considered optimization problem when using a fixed allowed deviation during the optimization run. However, if the allowed constraint violation is varied during the run according to a suitable schedule, even reaching deviations of l

e

–15 is no problem for both optimization algorithms.

Karin Zielinski, Shyam Praveen Vudathu, Rainer Laur
Efficiency of Various Stochastic Optimization Algorithms in High Frequency Electromagnetic Applications

We present the efficiency of various probabilistic algorithms, including the standard genetic algorithm, micro-genetic algorithm, evolutionary strategy, randomly initialized hill climbing, and mutation based algorithms for the optimization of electromagnetic devices operating at microwave and optical frequencies. Single fitness evaluations are costly because the electromagnetic field computation time is usually long. We therefore need to find strategies that provide optimal solutions in under a few hundred fitness evaluations. This constraint considerably affects the design of the optimizer. In order to obtain reliable guidelines, various optimization algorithms have been applied to three optimization problems.

Jasmin Smajic, Matthew Mishrikey, Arya Fallahi, Christian Hafner, Ruediger Vahldieck
Learning Classifier System with Self-adaptive Discovery Mechanism

Learning Classifier System which replaces the genetic algorithm with the evolving cooperative population of discoverers is a focus of current research. This paper presents a modified version of XCS classifier system with self-adaptive discovery module. The new model was confirmed experimentally in a multiplexer environment. The results prove that XCS with the self-adaptive method for determining mutation rate had a better performance than the classic architecture with fixed mutation.

Maciej Troc, Olgierd Unold
An Approach to Genome Statistics Inspired by Stochastic or Quantum Models of Computing: A Survey

We present a formalism of sequential and asynchronous processes defined in terms of random or quantum grammars and argue that these processes have relevance in genome statistics. To make the article accessible to the nonmathematicians, we keep the mathematical exposition as elementary as possible, focusing on some general ideas behind the formalism and stating the implications of the known mathematical results. We close with a set of open challenging problems.

Dimitri Petritis
Learning Robust Dynamic Networks in Prokaryotes by Gene Expression Networks Iterative Explorer (GENIE)

Genetic and genomic approaches have been used successfully to assign genes to distinct regulatory networks, but the uncertainty concerning the connections between genes, the ambiguity inherent to the biological processes, and the impossibility of experimentally determining the underlying biological properties only allow a rough prediction of the dynamics of genes. Here we describe the GENIE methodology that formulates alternative models of genetic regulatory networks based on the available literature and transcription factor binding site evidence. It also provides a framework for the analysis of these models optimized by genetic algorithms, inferring their optimal parameters, simulating their behavior, evaluating them by integrating robustness, realness and flexibility criteria, and contrasting the predictions to experimentally results obtained by Gene Fluorescence Protein analysis. The application of this method to the regulatory network of the bacterium

Salmonella enterica

uncovered new mechanisms that enable the inter-connection of the PhoP/PhoQ and the PmrA/PmrB two component systems. The predictions were experimentally verified to establish that both transcriptional and post-transcriptional mechanisms are employed to connect these two systems.

Oscar Harari, Cristina Rubio-Escudero, Patricio Traverso, Marcelo Santos, Igor Zwir
Discrete Particle Swarm Optimization for the Minimum Labelling Steiner Tree Problem

Particle Swarm Optimization is an evolutionary method inspired by the social behaviour of individuals inside swarms in nature. Solutions of the problem are modelled as members of the swarm which fly in the solution space. The evolution is obtained from the continuous movement of the particles that constitute the swarm submitted to the effect of the inertia and the attraction of the members who lead the swarm. This work focuses on a recent Discrete Particle Swarm Optimization for combinatorial optimization, called Jumping Particle Swarm Optimization. Its effectiveness is illustrated on the minimum labelling Steiner tree problem: given an undirected labelled connected graph, the aim is to find a spanning tree covering a given subset of nodes, whose edges have the smallest number of distinct labels.

S. Consoli, J. A. Moreno Pérez, K. Darby-Dowman, N. Mladenović
Ant Colony Cooperative Strategy in Electrocardiogram and Electroencephalogram Data Clustering

Cooperation in natural processes is very important feature, which is modeled by many nature-inspired algorithms. Nature inspired metaheuristics have interesting stochastic properties which make them suitable for use in data mining, data clustering and other computationally demanding application areas. It is because they often produce robust solutions in fairly reasonable time. This paper presents an application of clustering method inspired by the behavior of real ants in the nature in biomedical signal processing. The ants cooperatively maintain and evolve a pheromone matrix which is used to select features. The main aim of this study was to design and develop a combination of feature extraction and classification methods for automatic recognition of significant structure in biological signal recordings. The method is targeted towards speeding up and increasing objectivity of identification of important classes and may be used for online classification. Inherent properties of the method make it suitable for analysis of newly incoming data. The method can be also used in the expert classification process. We have obtained significant results in electrocardiogram and electroencephalogram recordings, which justify the use of such method.

Miroslav Bursa, Lenka Lhotska
A Surface Tension and Coalescence Model for Dynamic Distributed Resources Allocation in Massively Parallel Processors on-Chip

Massively Parallel Processors on-Chip, presenting the same problems of their non-monolithic counterparts, exacerbated by the limited on-chip resources, are the most challenging architectures in the processor architectures domain. In this paper, a novel nature-inspired decentralized algorithm, aiming at the definition of clusters of processors to be assigned to different threads, is presented and evaluated. Taking inspiration from liquid surface tension and drops coalescence, the proposed solution achieves better performances than other distributed solutions, reducing fragmentation and communication latency within the clusters.

Francesca Palumbo, Danilo Pani, Luigi Raffo, Simone Secchi
Cooperative Learning Sensitive Agent System for Combinatorial Optimization

Systems composed of several interacting autonomous agents have a huge potential to efficiently address complex real-world problems. A new

Learning Sensitive Agent System (LSAS)

is proposed to address combinatorial optimization problems. Agents communicate by directly exchanging information and knowledge about the environment. Furthermore, agents of the proposed model are endowed with stigmergic behavior and are able to indirectly communicate by producing and being influenced by pheromone trails. Each stigmergic agent has a certain level of sensitivity to the pheromone allowing various types of reactions to a changing environment. For better search diversification and intensification, agents can learn to modify their sensitivity level according to environment characteristics and previous experience. The proposed

LSAS

model is tested for solving various instances of the

Asymmetric Traveling Salesman Problem

. Numerical experiments indicate the robustn ess and potential of the new metaheuristic.

Camelia Chira, Camelia -M. Pintea, Dumitru Dumitrescu
A Hybrid Genetic Algorithm for the Travelling Salesman Problem

Genetic Algorithms (GAs) for the Travelling Salesman Problem (TSP) are often based on permutation representations, which makes it difficult to design effective evolutionary operators without causing feasibility problems to chromosomes. This paper attempts to develop a binary representation based hybrid GA to solve the TSP. The basic idea is to design a pre-TSP problem (PTSPP), where the input is the coordinates of a point in the map of cities, and the output is a feasible route connecting all cities. An effective deterministic algorithm is developed for this PTSPP to search the local optimum starting from the coordinates of a given point. The new GA is then designed to randomly choose and evolve the coordinates of generations of points for the PTSPP, and also to find out the global optimum or suboptima for the TSP. The preliminary experiments show the potential of the proposed hybrid GA to solve the TSP.

Xiao-Bing Hu, Ezequiel Di Paolo
A BioInspired Model for Parsing of Natural Languages

Networks of Evolutionary Processors (NEPs) –introduced in Castellanos et al. (2001)– are a new computing mechanism directly inspired in the behaviour of cell populations. In the paper, we explain why Networks of Evolutionary Processors can be suitable for modelling natural language –an entity generated in parallel by a modular architecture– and specially syntax –a modular device of specialized processors inside the modular construct of language. An implementation of NEPs for parsing of simple structures [[NP] V [NP]] is also suggested. By applying this theory to natural language, we introduce a new line of research in formal linguistics.

Gemma Bel-Enguix, M. Dolores Jiménez-López
An Evolutionary Approach for Performing Structural Unit-Testing on Third-Party Object-Oriented Java Software

Evolutionary Testing is an emerging methodology for automatically generating high quality test data. The focus of this paper is on presenting an approach for generating test cases for the unit-testing of object-oriented programs, with basis on the information provided by the structural analysis and interpretation of Java bytecode and on the dynamic execution of the instrumented test object. The rationale for working at the bytecode level is that even when the source code is unavailable, insight can still be obtained and used to guide the search-based test case generation process. Test cases are represented using the Strongly Typed Genetic Programming paradigm, which effectively mimics the polymorphic relationships, inheritance dependences and method argument constraints of object-oriented programs.

José Carlos Ribeiro, Mário Zenha-Rela, Francisco Fernández de Vega
Adaptive Spatial Allocation of Resource for Parallel Genetic Algorithm

Spatial allocation of resource for parallel genetic algorithm is achieved by the partitioning of the search space into many subspaces. Search for solution is performed in each subspace by a genetic algorithm with chromosomes defined in that particular subspace. This spatial allocation of computational resource takes the advantage of exhaustive search which avoids duplicate effort, and combine it with the parallel nature of the search for solution in disjoint subspaces by genetic algorithm. The division of the solution space is performed intelligently using loci statistics of the chromosomes in past generations. The time when this division takes place is determined by monitoring the performance of the evolutionary computation using mean and variance. This general idea is implemented in an adaptive genetic algorithm using the new formalism of mutation matrix, where the need for setting a survival probability is removed. The mutation matrix

M(t)

is constructed using the locus statistics and the fitness distribution in a population

A(t)

with N rows and L columns, where N is the size of the population and L is the length of the encoded chromosomes. The mutation matrix is parameter free and adaptive as it is time dependent and captures the accumulated information in the past generation. Example illustrating the efficiency of this adaptive spatial allocation of resource is the zero/one knapsack problem.

K. Y. Szeto, S. Y. Zhao
Implementation of Massive Parallel Networks of Evolutionary Processors (MPNEP): 3-Colorability Problem

This paper presents a new dynamic in Networks of Evolutionary Processors (NEP) – Massive Parallel NEP. Processors in a MPNEP have not a two stage behavior: evolution and then, communication; both steps are in parallel. Such situation give processors the benefit of communicating objects without rule application. MPNEP could be considered a superset of NEP since processors in MPNEP are able to operate in a parallel way or in a sequential way. Here we pro- posed a mechanism to obtain an MPNEP equivalent to any given NEP. Therefore, MPNEP can solve NP-problems in linear time such as NEPs. This paper proof that a MPNEP solve the

3-color-ability problem

in

O(m + n)

time and resources. A software tool has been implemented in order to test MPNEP performance and some outputs, corresponding to the

3-col problem

, are shown.

M. Angel Díaz, L. F. de Mingo, N. Gómez Blas, J. Castellanos
Multi-Constraints Routing Algorithm Based on Swarm Intelligence over High Altitude Platforms

In this paper a new routing algorithm over a network composed of a mesh of Haps is described. The simulated network models two types of packets, data packets, which are the traditional information packets and ant packets, which are a simple software mobile agents that are useful for collecting info for the problem. In particular, this proposed algorithm focuses on path length minimization and on maximum end-to-end delay bound on the HAPs network.

F. De Rango, M. Tropea, A. Provato, A. F. Santamaria, S. Marano
A Genetic Algorithm Framework Applied to Quantum Circuit Synthesis

This paper proposes an object oriented framework for genetic algorithm implementations. Software methods and design patterns are applied in order to create the necessary abstract levels for the genetic algorithm. The architecture is presented in UML terms, while several genetic algorithm schemes are already implemented. The framework allows for different configurations, thus the comparison between the characteristics of the emerged solutions becomes straightforward. This design creates incentives for practical solutions, because the inheritance from the defined abstract classes makes the creation of new genetic schemes possible. This framework was tested for the GA quantum circuit synthesis on several benchmark circuits. The genetic algorithm created with our framework proved to be faster than other available similar solutions used for quantum circuit synthesis.

Cristian Ruican, Mihai Udrescu, Lucian Prodan, Mircea Vladutiu
Semantic Distillation: A Method for Clustering Objects by their Contextual Specificity

Techniques for data-mining, latent semantic analysis, contextual search of databases, etc. have long ago been developed by computer scientists working on information retrieval (IR). Experimental scientists, from all disciplines, having to analyse large collections of raw experimental data (astronomical, physical, biological, etc.) have developed powerful methods for their statistical analysis and for clustering, categorising, and classifying objects. Finally, physicists have developed a theory of quantum measurement, unifying the logical, algebraic, and probabilistic aspects of queries into a single formalism.

The purpose of this paper is twofold: first to show that when formulated at an abstract level, problems from IR, from statistical data analysis, and from physical measurement theories are very similar and hence can profitably be cross-fertilised, and, secondly, to propose a novel method of fuzzy hierarchical clustering, termed

semantic distillation

— strongly inspired from the theory of quantum measurement —, we developed to analyse raw data coming from various types of experiments on DNA arrays. We illustrate the method by analysing DNA arrays experiments and clustering the genes of the array according to their specificity.

Thomas Sierocinski, Antony Le Béchec, Nathalie Théret, Dimitri Petritis
UPlanIT: An Evolutionary Based Production Planning and Scheduling System

In this paper we discuss an optimization approach to a real-world production planning problem. Based on raw data from instances of production planning we have developed an architecture for optimization of production planning and scheduling for manufacturing lines in small/medium enterprises (SME). The approach referred to as “Unified Planning using Intelligent Techniques”-abbreviated UPlanIT is based on genetic algorithms (GA). The schedules are constructed using rules in which the priorities are determined by the GA, using a procedure that generates parameterized activities. The approach is tested on a set of real standard production instances. The results validate the effectiveness of the proposed algorithm.

Saeedeh Maleki-Dizaji, Henry Nyongesa, Babak Khazaei
Performance Analysis of Turning Process via Particle Swarm Optimization

This paper describes the implementation of Particle Swarm Optimization (PSO) technique for CNC (computer numerically controlled) turning problem to find the optimal operating parameters such as cutting speed and feed rate such that the total production time is minimized subject to the constraints such as cutting force, power, tool-chip interface temperature and surface roughness of the product. An example is given to illustrate the working of Particle Swarm Optimization for optimizing the operating parameters. The results are compared with those obtained by Nelder Mead simplex method (NMS), boundary search method (BSP), genetic algorithm (GA) and simulated annealing (SA).

Kusum Deep, Jagdish Chand Bansal
Automatic Selection for the Beta Basis Function Neural Networks

In this paper, we propose a differential evolution algorithm based design for the beta basis function neural network. The differential Evolution algorithm has been used in many practical cases and has demonstrated good convergences properties. The differential evolution is used to evolve the beta basis function neural networks topology. Compared with the traditional genetic algorithm, the combined approach proves goodly the difference, including the feasibility and the simplicity of implementation. In the prediction of Mackey-Glass chaotic time series, the networks designed by the proposed approach prove to be competitive, or even superior, to the traditional learning algorithm for a multi-layer Perceptron network and radialbasis function network. Therefore, designing a set of BBFNN can be considered as solution of a two-optimisation problem.

Habib Dhahri, Adel Alimi
Evolvable Hardware: A Problem of Generalization Which Works Best: Large Population Size and Small Number of Generations or visa versa?

Evolutionary Algorithms (EAs), emulate, in several different applications, the Darwinian Evolution Theory, which advocates the adaptation of living beings to their environment and the survival of the fittest individual through natural selection. Indeed, since the 1990s, EAs have emerged as unconventional method to automatically design and optimise digital circuitry. Researchers in this field have adopted

Evolvable Hardware

(EHW) to refer to a reconfigurable digital system that can evolve to behave as desired. One difficult task in EHW is choosing the right EA’s parameters such as the population size, number of evaluations (generations), genetic operators (mutation, crossover), selection method and so on. This paper is part of the Evolvable Embryonics project and is particularly interested in the former two forces of the EA, population size and number of generations.

Elhadj Benkhelifa, Anthony Pipe, Mokhtar Nibouche, Gabriel Dragffy
Detecting Hierarchical Organization in Complex Networks by Nearest Neighbor Correlation

The hierarchical organization in complex networks is investigated from the point of view of nearest neighbor correlation. By plotting the mean total degree of the nearest neighbors versus degree of the given node, more than one linear branches will be observed for hierarchical network. An example of hierarchical network with 1-hub-4-peripheral is constructed for illustrative purpose and real data on the World Wide Web and AS Internet are analyzed for comparison. Two branches are clearly observed for the total degree of neighbors of the World Wide Web, indicative of the existence of hierarchical organization and the result is consistent with the analysis based on local clustering coefficient. Only one branch is observed for the AS Internet data set, but the result is not conclusive as the size of the data set is not sufficiently large. The total degree of nearest neighbor provides a good complementary test to the existing method based on the local clustering coefficients.

Chao Long Wang, Ka Wai Au, Ching King Chan, Hon Wai Lau, K. Y. Szeto
A Genetic Algorithm Based on Complex Networks Theory for the Management of Airline Route Networks

Airline companies need to organize and manage their route networks in a more cost-efficient and reliable way, in order to cope with increasing customer demands and market changes. This paper attempts to apply complex network concepts and techniques to model airline route networks, and the focus is then put on how to develop an effective and efficient Genetic Algorithm (GA) to optimize airline route networks in terms of certain network properties which are identified to have crucial roles to play in making airline route networks cost-efficient and reliable. The chromosome structure in the proposed GA is based on complex network modelling, and as a result, effective evolutionary operators, particularly a highly efficient uniform crossover operator, are developed. The results demonstrate that the reported GA has a good potential to improve the topology of airline route networks in terms of network properties of interest such as operating costs and network robustness.

Xiao-Bing Hu, Ezequiel Di Paolo
GAHC: Improved Genetic Algorithm

This paper introduces a novel improved evolutionary algorithm, which combines genetic algorithms and hill climbing. Genetic Algorithms (GA) belong to a class of well established optimization meta-heuristics and their behavior are studied and analyzed in great detail. Various modifications were proposed by different researchers, for example modifications to the mutation operator. These modifications usually change the overall behavior of the algorithm. This paper presents a binary GA with a modified mutation operator, which is based on the well-known Hill Climbing Algorithm (HCA). The resulting algorithm, referred to as GAHC, also uses an elite tournament selection operator. This selection operator preserves the best individual from the GA population during the selection process while maintaining the positive characteristics of the standard tournament selection. This paper discusses the GAHC algorithm and compares its performance with standard GA.

Radomil Matoušek
Metadaten
Titel
Nature Inspired Cooperative Strategies for Optimization (NICSO 2007)
herausgegeben von
Natalio Krasnogor
Giuseppe Nicosia
Mario Pavone
David Pelta
Copyright-Jahr
2008
Verlag
Springer Berlin Heidelberg
Electronic ISBN
978-3-540-78987-1
Print ISBN
978-3-540-78986-4
DOI
https://doi.org/10.1007/978-3-540-78987-1