Nature Inspired Cooperative Strategies for Optimization (NICSO 2011)

Adversarial decision making is aimed at determining optimal strategies against an adversarial enemy who observes our actions and learns from them. The field is also known as decision making in the presence of adversaries. Given two agents or entities S and T (the adversary), both engage in a repeated conflicting situation in which agent T tries to learn how to predict the behaviour of S. One defense for S is to make decisions that are intended to confuse T, although this will affect the ability of getting a higher reward. It is difficult to define good decision strategies for S since they should contain certain amount of randomness. Ant-based techniques can help in this direction because the automatic design of good strategies for our adversarial model can be expressed as a combinatorial optimization problem that is suitable for Ant-based optimizers. We have applied the Ant System (AS) and the Max-Min Ant System (MMAS) algorithms to such problem and we have compared the results with those found by a Generational Genetic Algorithm in a previous work. We have also studied the structure of the solutions found by both search techniques. The results are encouraging because they confirm that our approach is valid and MMAS is a competitive technique for automatic design of strategies.

This work details early research aimed at applying the powerful resource allocation mechanism deployed in Stochastic Diffusion Search (SDS) to the Differential Evolution (DE), effectively merging a nature inspired swarm intelligence algorithm with a biologically inspired evolutionary algorithm. The results reported herein suggest that the hybrid algorithm, exploiting information sharing between the population, has the potential to improve the optimisation capability of classical DE.

This work presents the results obtained when using a decentralised multiagent strategy (Agents) to solve dynamic optimization problems of a combinatorial nature. To improve the results of the strategy, we also include a simple adaptive scheme for several configuration variants of a mutation operator in order to obtain a more robust behaviour. The adaptive scheme is also tested on an evolutionary algorithm (EA). Finally, both Agents and EA are compared against the recent state of the art adaptive hill-climbing memetic algorithm (AHMA).

Expressive speech is one of the latest concerns of text-to-speech systems. Due to the subjectivity of expression and emotion realisation in speech, humans cannot objectively determine if one system is more expressive than the other. Most of the text-to-speech systems have a rather flat intonation and do not provide the option of changing the output speech. We therefore present an interactive intonation optimisation method based on the pitch contour parameterisation and evolution strategies. The Discrete Cosine Transform (DCT) is applied to the phrase level pitch contour. Then, the genome is encoded as a vector that contains 7 most significant DCT coefficients. Based on this initial individual, new speech samples are obtained using an interactive Covariance Matrix Adaptation Evolution Strategy (CMA-ES) algorithm. We evaluate a series of parameters involved in the process, such as the initial standard deviation, population size, the dynamic expansion of the pitch over the generations and the naturalness and expressivity of the resulted individuals. The results have been evaluated on a Romanian parametric-based speech synthesiser and provide the guidelines for the setup of an interactive optimisation system, in which the users can subjectively select the individual which best suits their expectations with minimum amount of fatigue.

In a previous work we have reported on the evolutionary design optimisation of self-assembling Wang tiles. Apart from the achieved findings [11], nothing has been yet said about the effectiveness by which individuals were evaluated. In particular when the mapping from genotype to phenotype and from this to fitness is an intricate relationship. In this paper we aim to report whether our genetic algorithm, using morphological image analyses as fitness function, is an effective methodology. Thus, we present here fitness distance correlation to measure how effectively the fitness of an individual correlates to its genotypic distance to a known optimum when the genotype-phenotype-fitness mapping is a complex, stochastic and non-linear relationship.

In many practical situations a fairly complex and high order model is obtained in modeling different components/subsystems of a system. The analysis of such high order system is not only tedious but also cost ineffective for online implementation. Therefore, deriving reduced order models of high-order linear time invariant systems attracted researchers to develop new methods for this purpose. Artificial Bee Colony (ABC) optimization algorithm is an effective and recent addition to swarm based optimization algorithm for optimization in continuous search space. In this paper, Artificial Bee Colony optimization algorithm is applied to solve Model Order Reduction of Single Input Single Output (SISO) Systems. The results obtained by ABC are compared with two most popular deterministic approaches namely Pade and Routh approximation method. The results reported are encouraging and shows that this technique is comparable in quality with existing conventional methods.

We present an analysis of the behaviour of Cooperative Co-evolution algorithms (CCEAs) on a simple test problem, that is the optimal placement of a set of lamps in a square room, for various problems sizes. Cooperative Co-evolution makes it possible to exploit more efficiently the artificial Darwinism scheme, as soon as it is possible to turn the optimisation problem into a co-evolution of interdependent sub-parts of the searched solution. We show here how two cooperative strategies, Group Evolution (GE) and Parisian Evolution (PE) can be built for the lamps problem. An experimental analysis then compares a classical evolution to GE and PE, and analyses their behaviour with respect to scale.

The problem of detecting community structures in social networks is a complex problem of great importance in sociology, biology and computer science. Communities are characterized by dense intra-connections and comparatively sparse inter-cluster connections. The community detection problem is empirically formulated from a game theoretic point of view and solved using a Crowding based Differential Evolution algorithm adapted for detecting Nash equilibria of noncooperative games. Numerical results indicate the potential of this approach.

This chapter proposes a simplification of the original Social Impact Theory based Optimizer (oSITO). Based on the experiments with seven benchmark datasets it is shown that the novel method called simplified Social Impact Theory based Optimizer (sSITO) does not degrade the optimization abilities and even leads to smaller testing error and better dimensionality reduction. From these points of view, it also outperforms another well known social optimizer - the binary Particle Swarm Optimization algorithm. The main advantages of the method are the simple implementation and the small number of parameters (two). Additionally, it is empirically shown that the sSITO method even outperforms the nearest neighbor margin based SIMBA algorithm.

We introduce a new nature inspired algorithm to solve the Graph Coloring Problem (GCP): the Gravitational Swarm. The Swarm is composed of agents that act individually, but that can solve complex computational problems when viewed as a whole. We formulate the agent’s behavior to solve the GCP. Agents move as particles in the gravitational field defined by some target objects corresponding to graph node colors. Knowledge of the graph to be colored is encoded in the agents as friend-or-foe information. We discuss the convergence of the algorithm and test it over well-known benchmarking graphs, achieving good results in a reasonable time.

Evolutionary Algorithms (eas) are one of the most popular strategies for solving optimisation problems. One of the main drawbacks of eas is the complexity of their parameter setting. This setting is mandatory to obtain high quality solutions. In order to deal with the parameterisation of an ea, hyperheuristics can be applied. They manage the choice of which parameters should be applied at each stage of the optimisation process. In this work, an analysis of the robustness of a parallel strategy that hybridises hyperheuristics, and parallel island-based models has been performed. Specifically, the model has been applied to a large set of mono-objective scalable benchmark problems with different landscape features. In addition, a study of the adaptation level of the proposal has been carried out. Computational results have shown the suitability of the model with every tested benchmark problem.

Estimation of Distribution Algorithms (EDA) are a type of optimization techniques that belong to evolutionary computation. Its operation is based on the use of a probabilistic model, which tries to reach promising regions through statistical information concerning to the individuals that belong to the population. In this work, several solution approaches based on the EDA field are presented in order to solve the Quay Crane Scheduling Problem (QCSP). QCSP consists of obtaining a schedule that minimizes the service time of a container vessel given a set of tasks (loading and unloading operations to/from) by means of the available quay cranes at a container terminal. The experimental results confirm that such algorithms are suitable for solving the QCSP and perform a wide exploration of the solution space using reduced computational times.

Equilibria detection in large games represents an important challenge in computational game theory. A solution based on generative relations defined on the strategy set and the standard Extremal Optimization algorithm is proposed. The Cournot oligopoly model involving up to 1000 players is used to test the proposed methods. Results are compared with those obtained by a Crowding Differential Evolution algorithm.

Graph colouring heuristics have long been applied successfully to the exam timetabling problem. Despite the success of a few heuristic ordering criteria developed in the literature, the approaches lack the ability to handle the situations where ties occur. In this paper, we investigate the effectiveness of applying tie breakers to orderings used in graph colouring heuristics. We propose an approach to construct solutions for our problem after defining which heuristics to combine and the amount of each heuristic to be used in the orderings. Heuristic sequences are then adapted to help guide the search to find better quality solutions. We have tested the approach on the Toronto benchmark problems and are able to obtain results which are within the range of the best reported in the literature. In addition, to test the generality of our approach we introduced an exam timetabling instance generator and a new benchmark data set which has a similar format to the Toronto benchmark. The instances generated vary in size and conflict density. The publication of this problem data to the research community is aimed to provide researchers with a data set which covers a full range of conflict densities. Furthermore, it is possible using the instance generator to create random data sets with different characteristics to test the performance of approaches which rely on problem characteristics. We present the first results for the benchmark and the results obtained show that the approach is adaptive to all the problem instances that we address. We also encourage the use of the data set and generator to produce tailored instances and to investigate various methods on them.

The economics appears to have not paid the required attention and research effort for understanding the destructive phenomena in economic systems. Relying on various widely accepted models and theories that practically avoid the occurrence of failures, depressions, crises and crashes the economic science is incomplete and clearly needs a major reorientation and a change of focus from the deterministic to the holistic perspective.

An improved unsupervised bio-inspired clustering model is introduced. The main goal is to involve a correlation between properties of objects and some bio-inspired factors. The statistical classification biological model is based on the chemical recognition system of ants. Ants are able to create groups discriminating between nest-mates and intruders based on similar odor. Comparative analysis are performed on real data sets.

This paper analyzes the impact of having degenerate code and duplicate elimination in an attribute grammar with lookahead (AG+LA) approach, a recently proposed mapping process for Grammatical Evolution (GE) using attribute grammar (AG) with a lookahead feature to solve heavily constrained multiple knapsack problems (MKP). Degenerate code, as used in DNA, is code in which different codons can represent the same thing. Many developmental systems, such as (GE), use a degenerate encoding to help promote neutral mutations, that is, minor genetic changes that do not result in a phenotypic change. Early work on GE suggested that at least some level of degeneracy has a significant impact on the quality of search when compared to the system with none. Duplicate elimination techniques, as opposed to degenerate encoding, are employed in decoder-based Evolutionary Algorithms (EAs) to ensure that the newly generated solutions are not already contained in the current population. The results and analysis show that it is crucial to incorporate duplicate elimination to improve the performance of AG+LA. Reducing level of degeneracy is also important to improve search performance, specially for the large instances of the MKP.

Cellular Automata are discrete dynamical systems having the ability to generate highly complex behavior starting from a simple initial configuration and set of update rules. However, the discovery of rules exhibiting a high degree of global self-organization for certain tasks is not easily achieved. In this paper, a fast compression based technique is proposed, capable of detecting promising emergent space-time patterns of cellular automata. This information can be used to automatically guide the evolutionary search toward more complex, better performing rules. Results are presented for the most widely studied cellular automata computation problem, the Density Classification Task, where incorporation of the proposed method almost always pushes the search beyond the simple block-expanding rules.

Membrane computing is a recently developed research field, whose models, P systems, are bio-inspired computational models, abstracted from the structure and the functioning of living cells. Their applications are various and have been reported in biology, bio-medicine, economics, approximate optimization and computer graphics. However, it is a difficult task to design a P system which solves a given problem, especially because of their characteristics, such as nondeterminism, parallelism, possible presence of active membranes. In this paper we propose an approach to P systems automatic design, which uses genetic algorithms and model checking. More precisely, we use a type of fitness function which performs several simulations of the P system, in order to assess its adequacy to realize the given task, complemented by formal verification of the model.

Complex systems are emergent, self-organizing and adaptive systems. They are pervasive in nature and usually hard to analyze or understand. Often they appear intelligent and show favorable properties such as resilience and anticipation. In this paper we describe a classifier model inspired by complex systems theory. Our model is a generalization of neural networks, boolean networks and genetic programming trees called computational networks. Designing computational networks by hand is infeasible when dealing with complex data. For designing our classifiers we developed an evolutionary design algorithm. Four extensions of this algorithm are presented. Each extension is inspired by natural evolution and theories from the evolutionary computing literature. The experiments show that our model can be evolutionary designed to act as a classifier. We show that our evolved classifiers are competitive compared to the classifiers in the Weka classifier collection. These experiments lead to the conclusion that using our evolutionary algorithm to design computational networks is a promising approach for the creation of classifiers. The benefits of the evolutionary extensions are inconclusive, for some datasets there is a significant performance increase while for other datasets the increase is very minimal.

The complexity and difficulties in modelling the most of nowadays real world problems increase as the computational capacity does, specially in those processes where relatively new technology arises. One of such processes is the steel sheet incremental cold shaping. The steel sheet incremental cold shaping process is a new technique for shaping metal sheets when a reduced amount of pieces per lots should be manufactured. As it is a relatively new technique, there is a lack of knowledge in defining the operating conditions, so in order to fit them, before manufacturing a lot a trial and error stage is carried out. A decision support system to reduce the cost of processing and to assist in defining the operating conditions should be studied. This study focus on the analysis and design of the decision support system, and as it is going to be shown, the most suitable features have been found using a wrapper feature selection method, in which genetic algorithms support vector machines and neural networks are hybridized. Some facts concerning the enhanced experimentation needed and the improvements in the algorithm are drawn.