Simulated Evolution and Learning

Natural systems such as plants, animals and humans exhibit behaviour that forms distinct, rhythmic cycles. These cycles permit individuals and societies to learn, adapt and evolve in complex, dynamic environments. This paper introduces a model of behaviour cycles for artificial systems. This model provides a new way to conceptualise and evaluate life-long learning in artificial agents. The model is demonstrated for evaluating the sensitivity of motivated reinforcement learning agents. Results show that motivated reinforcement learning agents can learn behaviour cycles that are relatively robust to changes in motivation parameters.

The majority of artificial neural networks are static and lifeless and do not change themselves within a learning environment. In these models learning is seen as the process of obtaining the strengths of connections between neurons (i.e. weights). We refer to this as the ’synaptic dogma’. This is in marked contrast with biological networks which have time dependent morphology and in which practically all neural aspects can change or be shaped by mutual interactions and interactions with an external environment. Inspired by this and many aspects of neuroscience, we have designed a new kind of neural network. In this model, neurons are represented by seven evolved programs that model particular components and aspects of biological neurons (dendrites, soma, axons, synapses, electrical and developmental behaviour). Each network begins as a small randomly generated network of neurons. When the seven programs are run, the neurons, dendrites, axons and synapses can increase or decrease in number and change in interaction with an external environment. Our aim is to show that it is possible to evolve programs that allow a network to learn through experience (i.e. encode the

ability

to learn). We report on our continuing investigations in the context of learning how to play checkers.

In Differential Evolution, control parameters play important roles in balancing the exploration and exploitation capability, and different control parameters are required for different types of problems. However, finding optimal control parameters for each problem is difficult and not realistic. Hence, we propose a method to adjust them adaptively in this paper. In our proposed method, whether or not the current control parameters will be adjusted is based on a probability that is adaptively calculated according to their previous performance. Besides, normal distribution with variable mean value and standard deviation is employed to generate new control parameters. Performance on a set of benchmark functions indicates that our proposed method converges fast and achieves competitive results.

This paper proposes a novel orthogonal predictive local search (OPLS) to enhance the performance of the conventional genetic algorithms. OPLS operation predicts the most promising direction for the individuals to explore their neighborhood. It uses the orthogonal design method to sample orthogonal combinations to make the prediction. The resulting algorithm is termed the orthogonal predictive genetic algorithm (OPGA). OPGA has been tested on eleven numerical optimization functions in comparison with some typical algorithms. The results demonstrate the effectiveness of the proposed algorithm for achieving better solutions with a faster convergence speed.

The inference of phylogenetic trees is one of the most important tasks in computational biology. In this paper, we propose an extension to multi-objective evolutionary algorithms to address this problem. Here, we adopt an enhanced indirect encoding for a tree using the corresponding Prüfer code represented in Newick format. The algorithm generates a range of non-dominated trees given alternative fitness measures such as statistical likelihood and maximum parsimony. A key feature of this approach is the preservation of the evolutionary hierarchy between species. Preliminary experimental results indicate that our model is capable of generating a set of optimized phylogenetic trees for given species data and the results are comparable with other techniques.

We describe our efforts to convert (short) DNA sequences obtained from the NCBI library into control sequences for simulated robots by simultaneously evolving both a look up table to assign codons to robot commands and a look up table to assign codons to numerical values that serve as arguments to those commands. Our simulated robot is loosely modeled after the Khepera robot. When the robot’s sensing capabilities are disabled, we are provided with a sophisticated turtle graphics platform. We formulate a fitness function for evaluating the drawings obtained from codon look up tables and we make inter-DNA and intra-DNA comparisons using our evolved tables. Our results suggest that information content can only be weakly extracted from DNA in this way.

Optimising non-functional properties of software is an important part of the implementation process. One such property is execution time, and compilers target a reduction in execution time using a variety of optimisation techniques. Compiler optimisation is not always able to produce semantically equivalent alternatives that improve execution times, even if such alternatives are known to exist. Often, this is due to the local nature of such optimisations. In this paper we present a novel framework for optimising existing software using a hybrid of evolutionary optimisation techniques. Given as input the implementation of a program or function, we use Genetic Programming to evolve a new semantically equivalent version, optimised to reduce execution time subject to a given probability distribution of inputs. We employ a co-evolved population of test cases to encourage the preservation of the program’s semantics, and exploit the original program through seeding of the population in order to focus the search. We carry out experiments to identify the important factors in maximising efficiency gains. Although in this work we have optimised execution time, other non-functional criteria could be optimised in a similar manner.

Security policies are becoming more sophisticated. Operational forces will often be faced with making tricky risk decisions and policies must be flexible enough to allow appropriate actions to be facilitated. Access requests are no longer simple subject access object matters. There is often a great deal of context to be taken into account. Most security work is couched in terms of risk management, but the benefits of actions will need to be taken into account too. In some cases it may not be clear what the policy should be. People are often better at dealing with specific examples than producing general rules. In this paper we investigate the use of Grammatical Evolution (GE) to attempt to infer Fuzzy MLS policy from decision examples. This approach couches policy inference as a search for a policy that is most consistent with the supplied examples set. The results show this approach is promising.

This paper describes a new approach using particle swarm optimisation (PSO) within AdaBoost for object detection. Instead of using the time consuming exhaustive search for finding good features to be used for constructing weak classifiers in AdaBoost, we propose two PSO based methods in this paper. The first uses PSO to evolve and select the good features only and the weak classifiers use a kind of decision stump. The second uses PSO for both selecting the good features and evolving weak classifiers in parallel. These two methods are examined and compared on a pasta detection data set. The experiment results show that both approaches perform quite well for the pasta detection problem, and that using PSO for selecting good individual features and evolving associated weak classifiers in AdaBoost is more effective than for selecting features only for this problem.

This paper studies properties of quantum particles rules of movement in particle swarm optimization (PSO) for non-stationary optimization tasks. A multi-swarm approach based on two types of particles: neutral and quantum ones is a framework of the experimental research. A new method of generation of new location candidates for quantum particles is proposed. Then a set of experiments is performed where this method is verified. The test-cases represent different situations which can occur in the search process concerning different numbers of moving peaks respectively to the number of sub-swarms. To obtain the requested circumstances in the testing environment the number of sub-swarms is fixed. The results show high efficiency and robustness of the proposed method in all of the tested variants.

Type-2 fuzzy logic systems (FLSs) have been treated as a magic black box which can better handle uncertainties due to the footprint of uncertainty (FOU). Although the results in control applications are promising, the advantages of type-2 framework in fuzzy pattern classification is still unclear due to different forms of outputs produced by both systems. This paper aims at investigating if type-2 fuzzy classifier can deliver a better performance when there exists imprecise decision boundary caused by improper feature extraction method. Genetic Algorithm (GA) is used to tune the fuzzy classifiers under Pittsburgh scheme. The proposed fuzzy classifiers have been successfully applied to an automotive application whereby the classifier needs to detect the presence of human in a vehicle. Results reveal that type-2 classifier has the edge over type-1 classifier when the decision boundaries are imprecise and the fuzzy classifier itself has not enough degrees of freedom to construct a suitable boundary. Conversely, when decision boundaries are clear, the advantage of type-2 framework may not be significant anymore. In any case, the performance of a type-2 fuzzy classifier is at least comparable with a type-1 fuzzy classifier. When dealing with real world classification problem where the uncertainty is usually difficult to be estimated, type-2 fuzzy classifier can be a more rational choice.

Learning Classifier Systems (LCSs) are rule-based evolutionary reinforcement learning (RL) systems. Today, especially variants of Wilson’s eXtended Classifier System (XCS) are widely applied for machine learning. Despite their widespread application, LCSs have drawbacks: The number of reinforcement cycles an LCS requires for learning largely depends on the complexity of the learning task. A straightforward way to reduce this complexity is to split the task into smaller sub-problems. Whenever this can be done, the performance should be improved significantly. In this paper, a nature-inspired multi-agent scenario is used to evaluate and compare different distributed LCS variants. Results show that improvements in learning speed can be achieved by cleverly dividing a problem into smaller learning sub-problems.

This paper presents a novel ensemble construction approach based on Artificial Immune Systems (AIS) to solve regression problems. Over the last few years AIS have increasingly attracted interest from researchers due to their ability to balance the exploration and exploitation of the search space. Nevertheless, there have been just a few applications of those algorithms in the construction of committee machines. In this paper, a population of feed-forward neural networks is evolved using the Clonal Selection Algorithm and then ensembles are automatically composed of a subset of this neural network population. Results show that the proposed algorithm can achieve good generalization performance on some hard benchmark regression problems.

Differential Evolution (DE) is a powerful optimization procedure that self-adapts to the search space, although DE lacks diversity and sufficient bias in the mutation step to make efficient progress on non-separable problems. We present an enhancement to Differential Evolution that introduces greater diversity. The new DE approach demonstrates fast convergence towards the global optimum and is highly scalable in the decision space.

This paper aims to propose a knowledge-based Fuzzy - GA Decision Support System with performance metrics for better measuring postponement strategies. The Fuzzy - GA approach mainly consists of two stages: knowledge representation and knowledge assimilation. The relevant knowledge of deciding what type of postponement strategies to adopt is encoded as a string with a fuzzy rule set and the corresponding membership functions. The historical data on performance measures forming a combined string is used as the initial population for the knowledge assimilation stage afterwards. GA is then further incorporated to provide an optimal or nearly optimal fuzzy set and membership functions for related performance measures. The originality of this research is that the proposed system is equipped with the ability of assessing the loss caused by discrepancy away from the different supply chain parties, and therefore enabling the identification of the best set of decision variables.

The Delay-Constrained Capacitated Minimum Spanning Tree (DC-CMST) is a recently proposed problem which arises in the design of the topology of communications networks. The DC-CMST proposes the joint optimization of the network topology in terms of the traffic capacity and its mean time delay. In this paper, an evolutionary algorithm which uses

Dandelion-encoding

is proposed to solve the problem. The Dandelion code has been recently proposed as an effective way of encoding trees in evolutionary algorithms, due to its good properties of locality. We describe the main characteristics of the algorithm, and compare its results with that of an existing heuristic for the DC-CMST. We show that our Dandelion-encoded evolutionary algorithm is able to obtain better results in all the instances tackled.

In this paper we propose a solution of a multiprocessor task scheduling problem with use of a new meta-heuristic inspired by a model of natural evolution called Generalized Extremal Optimization (GEO). It is inspired by a simple co-evolutionary model based on a Bak-Sneppen model. One of advantages of the model is a simple implementation of potential optimization problems and only one free parameter to adjust. The idea of GEO metaheuristic and the way of applying it to the multi-processor scheduling problem are presented in the paper. In this problem the tasks of a program graph are allocated into multiprocessor system graph where the program completion time is minimized. The problem is know to be a NP-complete problem. In this paper we show that GEO is to able to solve this problem with better performance than genetic algorithm.

Diversity maintenance is an importance part of multi-objective evolutionary algorithm. In this paper, a new variant for the NSGA-II algorithm is proposed. The basic idea is that using the crowding distance method designed by minimum spanning tree to maintain the distribution of solutions. From an extensive comparative study with NSGA-II on a number of two and three objective test problems, it is observed that the proposed algorithm has good performance in distribution, and is also rather competitive to NSGA-II concerning the convergence.

Evolutionary computation has become an important problem solving methodology among the set of search and optimization techniques. Recently, more and more different evolutionary techniques have been developed, especially hybrid evolutionary algorithms. This paper proposes an island based hybrid evolutionary algorithm (IHEA) for optimization, which is based on Particle swarm optimization (PSO), Fast Evolutionary Programming (FEP), and Estimation of Distribution Algorithm (EDA). Within IHEA, an island model is designed to cooperatively search for the global optima in search space. By combining the strengths of the three component algorithms, IHEA greatly improves the optimization performance of the three basic algorithms. Experimental results demonstrate that IHEA outperforms all the three component algorithms on the test problems.

A bilevel decision problem may have multiple followers as the lower decision units and have fuzzy demands simultaneously. This paper focuses on problems of fuzzy linear bilevel decision making with multiple followers who share a common objective but have different constraints (FBOSF). Based on the ranking relationship among fuzzy sets defined by cut set and satisfactory degree, a FBOSF model is presented and a particle swarm optimization based algorithm is developed.

Conventional multi-objective Particle Swarm Optimization (PSO) algorithms aim to find a representative set of Pareto-optimal solutions from which the user may choose preferred solutions. For this purpose, most multi-objective PSO algorithms employ computationally expensive comparison procedures such as non-dominated sorting. We propose a PSO algorithm, Reference point-based PSO using a Steady-State approach (RPSO-SS), that finds a preferred set of solutions near user-provided reference points, instead of the entire set of Pareto-optimal solutions. RPSO-SS uses simple replacement strategies within a steady-state environment. The efficacy of RPSO-SS in finding desired regions of solutions is illustrated using some well-known two and three-objective test problems.

In recent years, metabolic syndrome has emerged as a major health concern because it increases the risk of developing lifestyle diseases, such as diabetes, hypertension, and cardiovascular disease. Some of the symptoms of the metabolic syndrome are high blood pressure, decreased HDL cholesterol, and elevated triglycerides (TG). To prevent the developing of metabolic syndrome, accurate prediction of the future values of these health risk factors and identification of other factors from the health checkup and lifestyle data, which are highly related with these risk factors, are very important. In this paper, we propose a new framework, based on genetic algorithm and its variants, for identifying those important health factors and predicting the future health risk of a person with high accuracy. We show the effectiveness of the proposed system by applying it to the health checkup and lifestyle data of Toshiba Corporation.

Extremal Optimisation (EO) is a fairly new entrant into the realms of stochastic based optimisation techniques. Its behaviour differs from other more common algorithms as it alters a poorly performing part of the one solution used without regard to the effect this will have on the quality of the solution. While this means that its performance on assignment problems may be poor if used on its own, this same ‘failing’ makes it a very suitable base for a meta-heuristic. An analysis of the performance of naive EO on the classic bin packing problem is performed in this paper. Results are also presented that show that the same naive EO can be used in a meta-heuristic that performs very well.

The extremal optimisation (EO) meta-heuristic is a recent form of search that is suitable for combinatorial optimisation problems. EO has been applied to problems such as graph partitioning, spin glass, and graph colouring. However, only a relatively small amount of work has been done on other combinatorial problems particularly those having constraints. This paper examines the issue of satisfying constraints with a penalty approach using the multidimensional knapsack problem. An EO model is presented which finds solutions through the analysis of the number of overloaded constraints. This approach allows the solution state move between feasible and infeasible spaces. The results show that the new algorithm is able to obtain optimal results for small problems and finds competitive solutions for large problems.

The topic of multimodal function optimization, where the aim is to locate more than one solution, has attracted a growing interest especially in the evolutionary computing research community. To experimentally evaluate the strengths and weaknesses of multimodal optimization algorithms, it is important to use test functions representing different characteristics and of various levels of difficulty. However, the available selection of multimodal test problems with multiple global optima is rather limited at the moment and no general framework exists. This paper describes our attempt in constructing a test function generator to allow the generation of easily tunable test functions. The aim is to provide a general and easily expandable environment for testing different methods of multimodal optimization. Several function families with different characteristics are included. The generator implements new parameterizable function families for generating desired landscapes and a selection of well known test functions from literature, which can be rotated and stretched. The module can be easily imported to any optimization algorithm implementation compatible with C programming language.

The fast convergence of particle swarm algorithms can become a downside in multi-objective optimization problems when there are many local optimal fronts. In such a situation a multi-objective particle swarm algorithm may get stuck to a local Pareto optimal front. In this paper we propose a new approach in selecting leaders for the particles to follow, which in-turn will guide the algorithm towards the Pareto optimal front. The proposed algorithm uses a Differential Evolution operator to create the leaders. These leaders can successfully guide the other particles towards the Pareto optimal front for various types of test problems. This simple yet robust algorithm is effective compared with existing multi-objective particle swarm algorithms.

Photomosaics are a new form of art in which smaller digital images (known as tiles) are used to construct larger images. Photomosaic generation not only creates interest in the digital arts area but has also attracted interest in the area of evolutionary computing. The photomosaic generation process may be viewed as an arrangement optimisation problem, for a given set of tiles and suitable target to be solved using evolutionary computing. In this paper we assess two methods used to represent photomosaics, genetic algorithms (GAs) and genetic programming (GP), in terms of their flexibility and efficiency. Our results show that although both approaches sometimes use the same computational effort, GP is capable of generating finer photomosaics in fewer generations. In conclusion, we found that the GP representation is richer than the GA representation and offers additional flexibility for future photomosaics generation.

Parameters of real-valued crossover operators have been often tuned under a constraint for preserving statistics of infinite parental population. For applications in actual scenes, in a previous study, an alternative constraint, called

unbiased constraint

, considering finiteness of the population has been derived. To clarify the wide applicability of the unbiased constraint, this paper presents two additional studies: (1) applying it to various crossover operators in higher dimensional search space, and (2) generalization of it for preserving statistics of overall population. Appropriateness of the parameter setting based on the unbiased constraint has been supported in discussion on robust search.

This paper describes a thermodynamic particle swarm optimizer (TDPSO) based on the simple evolutionary equations. Inspired by the minimum free energy principle of the thermodynamic theoretics, a rating-based entropy (RE) and a component thermodynamic replacement (CTR) rule are implemented in the novel algorithm TDPSO. The concept of RE is utilized to systemically measure the fitness dispersal of the swarm with low computational cost. And the fitness range of all particles is divided into several ranks. Furthermore, the rule CTR is applied to control the optimal process with steeply fast convergence speed. It has the potential to maintain population diversity. Compared with the other improved PSO techniques, experimental results on some typical minimization problems show that the proposed technique outperforms other algorithms in terms of convergence speed and stability.

With the properties of T-coloring problems in mind, multiagent systems and evolutionary algorithms are integrated to form a new algorithm, Multiagent Evolutionary Algorithm for T-coloring (MAEA-T-coloring). We studied the generalization of classical graph coloring model, and focused our interest in the restricted T-coloring. An agent in MAEA-T-coloring represents a candidate solution to T-colorings. All agents live in a latticelike environment, with each agent fixed on a lattice-point. In order to increase energies, they compete or cooperate with their neighbors using their knowledge. Experiments on large random instances of T-colorings show encouraging results about MAEA- T-coloring.

We take a novel approach to Non-Photorealistic Rendering by adapting genetic programming in combination with computer graphics drawing techniques. As a GP tree is evaluated, upon encountering certain nodes referred to as “Draw” nodes, information contained within such nodes are sent to one of three virtual canvasses and a mark is deposited on the canvas. For two of the canvasses the user is able to define custom brushes to be applied to the canvas. Drawing functions are supplied with little localised information regarding the target image. Based on this local data, the drawing functions are enabled to apply contextualized information to the canvas. The obtained results include a “Shroud of Turin” effect, a “Decal” effect and a “Starburst” effect.

In our former study (Ishibuchi et al. 2006), we proposed the use of two neighborhood structures in a cellular genetic algorithm. One is for local selection where a pair of parents is selected from neighboring cells for mating. This neighborhood structure has been usually used in standard cellular algorithms. The other is for local competition, which is used to define local elitism and local ranking. We have already examined the effect of local elitism on the performance of our cellular genetic algorithm (Ishibuchi et al. 2008). In this paper, we examine the effect of using local ranking as the fitness of each individual. First we explain our cellular genetic algorithm with the two neighborhood structures. Then we examine its two variants with/without local ranking. In one variant, the local ranking of an individual among its neighbors is used as its fitness. Such a fitness redefinition scheme can be viewed as a kind of noise in parent selection. The other variant uses the original fitness value (instead of its local ranking). Through computational experiments, we demonstrate that the use of the local ranking improves the ability to escape from local optima.

This paper proposes a model for metaheuristic research which recognises the need to match algorithms to problems. An empirical approach to producing a mapping from problems to algorithms is presented. This mapping, if successful, will encapsulate the knowledge gained from the application of metaheuristics to the spectrum of real problems. Information theoretic measures are suggested as a means of associating a dominant algorithm with a set of problems.

This paper examines a new way of dividing computational tasks into smaller interacting components, in order to effectively solve constrained optimization problems. In dividing the tasks, we propose problem decomposition, and the use of GAs as the solution approach. In this paper, we consider problems with block angular structures with or without overlapping variables. We decompose not only the problem but also appropriately the chromosome for different components of the problem. We also design a communication process for exchanging information between the components. The approach can be implemented for solving large scale optimization problems using parallel machines. A number of test problems have been solved to demonstrate the use of the proposed approach. The results are very encouraging.

In multi-objective optimization, it is important that the obtained solutions are high quality regarding accuracy, uniform distribution, and broadness. Of these qualities, we focused on accuracy and broadness of the solutions and proposed a search strategy. Since it is difficult to improve both convergence and broadness of the solutions at the same time in a multi-objective GA search, we considered to converge the solutions first and then broaden them in the proposed search strategy by dividing the search into two search stages. The first stage is to improve convergence of the solutions, and a reference point specified by a decision maker is adopted in this search. In the second stage, the solutions are broadened using the Distributed Cooperation Scheme. From the results of the numerical experiment, we found that the proposed search strategy is capable of deriving broader solutions than conventional multi-objective GA with equivalent accuracy.

The interactive genetic algorithm(iGA) is a method to obtain and predict a user’s preference based on subjective evaluation of users, and it has been applied to many unimodal problems, such as designing clothes or fitting of hearing aids. On the other hand, we are interested in applying iGA to user’s preferences, which can be described as a multimodal problem with equivalent fitness values at the peaks. For example, when iGA is applied to product recommendation on shopping sites, users have several types of preference trends at the same time in product selection. Hence, reflecting all the trends in product presentation leads to increased sales and consumer satisfaction. In this paper, we propose a new offspring generation method that enables efficient search even with multimodal user preferences by introducing clustering of selected individuals and generating offspring from each cluster. Furthermore, we perform a subjective experiment using an experimental iGA system for product recommendation to verify the efficiency of the proposed method. The results confirms that the proposed method enables offspring generation with consideration of multimodal preferences, and there is no negative influence on the performance of preference prediction by iGA.

In this paper we present a hybrid evolutionary algorithm to solve a popular logic-type puzzle, the so called Japanese puzzle. We propose to use the evolutionary algorithm in order to initialize a logic ad-hoc algorithm, which works as a local search and implicitly defines the fitness function of the problem. Two novel operators, one for initializing the evolutionary algorithm and a second one providing a novel type of mutation adapted to Japanese puzzles are described in the paper.

This paper proposes a simulated annealing (SA) algorithm based optimization approach to search a minimum-interference multicast tree which satisfies the end-to-end delay constraint and optimizes the usage of the scarce radio network resource in wireless mesh networks. In the proposed SA multicast algorithm, the path-oriented encoding method is adopted and each candidate solution is represented by a tree data structure (i.e., a set of paths). Since we anticipate the multicast trees on which the minimum-interference channel assignment can be produced, a fitness function that returns the total channel conflict is devised. The techniques for controlling the annealing process are well developed. A simple yet effective channel assignment algorithm is proposed to reduce the channel conflict. Simulation results show that the proposed SA based multicast algorithm can produce the multicast trees which have better performance in terms of both the total channel conflict and the tree cost than that of a well known multicast algorithm in wireless mesh networks.

General Game Playing (GGP) aims at developing game playing agents that are able to play a variety of games and, in the absence of pre-programmed game specific knowledge, become proficient players. The challenge of making such a player has led to various techniques being used to tackle the problem of game specific knowledge absence. Most GGP players have used standard tree-search techniques enhanced by automatic heuristic learning, neuroevolution and UCT (Upper Confidence bounds applied to Trees) search, which is a simulation-based tree search. In this paper, we explore a new approach to GGP. We use an Ant Colony System (ACS) to explore the game space and evolve strategies for game playing. Each ant in the ACS is a player with an assigned role, and forages through the game’s state space, searching for promising paths to victory. Preliminary results show this approach to be promising. In order to test the architecture, we create matches between players using the knowledge learnt by the ACS and random players.

There has been a growing interest in studying evolutionary algorithms in dynamic environments in recent years due to its importance in real applications. However, different dynamic test problems have been used to test and compare the performance of algorithms. This paper proposes a generalized dynamic benchmark generator (GDBG) that can be instantiated into the binary space, real space and combinatorial space. This generator can present a set of different properties to test algorithms by tuning some control parameters. Some experiments are carried out on the real space to study the performance of the generator.

Non-dominated Sorting Genetic Algorithm (NSGA-II) [1] and the Strength Pareto Evolutionary Algorithm (SPEA2) [2] are the two most widely used evolutionary multi-objective optimization algorithms. Although, they have been quite successful so far in solving a wide variety of real life optimization problems mostly 2 or 3 objective in nature, their performance is known to deteriorate significantly with an increasing number of objectives. The term

many objective optimization

refers to problems with number of objectives significantly larger than two or three. In this paper, we provide an overview of the challenges involved in solving many objective optimization problems and provide an in depth study on the performance of recently proposed substitute distance based approaches, viz. Subvector dominance, -eps-dominance, Fuzzy Pareto Dominance and Sub-objective dominance count for NSGA-II to deal with many objective optimization problems. The present study has been conducted on scalable benchmark functions (DTLZ2-DTLZ3) and the recently proposed P* problem [3] since their convergence and diversity measures can be compared conveniently. An alternative substitute distance approach is introduced in this paper and compared with existing ones on the set of benchmark problems.

We propose a self-adaptive Ant Colony Optimization (AD-ACO) approach that exploits a parameter adaptation mechanism to reduce the requirement of a preliminary parameter tuning. The proposed AD-ACO is based on an ACO algorithm adopting a pheromone model with a new global pheromone update mechanism. We applied this algorithm to the

single machine total weighted tardiness scheduling problem with sequence-dependent setup times

and we executed an experimental campaign on a benchmark available in literature. Results, compared with the ones produced by the ACO algorithm without adaptation mechanism and with those obtained by recently proposed metaheuristic algorithms for the same problem, highlight the quality of the proposed approach.

This work proposes a method to fine grain the ranking of solutions after they have been ranked by Pareto dominance, aiming to improve the performance of evolutionary algorithms on

many

objectives optimization problems. The re-ranking method uses a randomized sampling procedure to choose, from sets of equally ranked solutions, those solutions that will be given selective advantage. The sampling procedure favors a good distribution of the sampled solutions based on dominance regions wider than conventional Pareto dominance. We enhance NSGA-II with the proposed method and test its performance on MNK-Landscapes with up to

M

 = 10 objectives. Experimental results show that convergence and diversity of the solutions found can improve remarkably on 3 ≤ 

M

 ≤ 10 objectives problems.

In this paper, we propose a new methodology where complex natural language requests from a user to a relational database are broken into simple sentences through an Evolutionary Computing method. Such basic sentences are then translated by another module, which tries to perform a pattern matching between a model filled by local grammars and the basic sentences generated by the Evolutionary Programming algorithm. The output of this system is a set of SQL queries to a specific database. The main feature is its combinatorial approach, as an alternative for the use of methods that employs many linguistic levels (lexicon, syntax rules and semantics) and intermediate languages. The proposed methodology is applied to Brazilian Portuguese. In our test bed, a 92% translation correctness was achieved.

The field of evolutionary computation has traditionally focused on static optimisation problems but recently, many new approaches have been proposed that adapt traditional evolutionary algorithms to deal with the task of tracking high-quality solutions as the search space changes over time. Algorithms developed specifically for dynamic domains have been tested on a wide range of different problems, including well-specified benchmark generators. However, the lack of theoretical results, a general omission of references to actual real-world scenarios, as well as a substantial emphasis on the continuous domain may divert attention away from some highly relevant issues. Here we review the state of the field and analyse dynamics in the combinatorial domain, using the subset sum problem as an example. It is shown that some of the assumptions underlying the development of new algorithms do not necessarily hold in the case of discrete optimisation. Furthermore, it is argued that more attention should be paid to the underlying dynamics and the impact of the representation used.

Local sharing is a method designed for efficient multimodal optimisation that combines fitness sharing, spatially-structured populations and elitist replacement. In local sharing the bias toward sharing or spatial effect is controlled by the deme (neighbourhood) size. This introduces an undesirable trade-off; to maximise the sharing effect, deme sizes must be large, but the opposite must be true if one wishes to maximise the influence of spatial population structure. This paper introduces a modification to the local sharing method whereby parent selection and fitness sharing operate at two different spatial levels; parent selection is performed within small demes, while the effect of fitness sharing is weighted according to the distances between individuals in the population structure. The proposed method, as tested on several benchmark problems, demonstrates a level of efficiency and parameter robustness that surpasses the basic local sharing method.

A Hybrid Genetic Programming (HGP) algorithm is proposed for optimal approximation of high order and sparse linear systems. With the intrinsic property of linear systems in mind, an individual in HGP is designed as an organization that consists of two cells. The nodes of the cells include a function and a terminal. All GP operators are designed based on organizations. In the experiments, three kinds of linear system approximation problems, namely stable, unstable, and high order and sparse linear systems, are used to test the performance of HGP. The experimental results show that HGP obtained a good performance in solving high order and sparse linear systems.

This paper presents a novel hardware architecture for genetic vector quantizer (VQ) design. The architecture is based on steady-state genetic algorithm (GA). It adopts a novel architecture based on shift registers for accelerating mutation and crossover operations while reducing area cost. It also uses a pipeline architecture for fitness evaluation. The proposed architecture has been embedded in a softcore CPU for physical performance measurement. Experimental results show that the proposed architecture is an effective alternative for VQ optimization attaining both high performance and low computational time.

We study the effects of different decision making schemes on the accumulative rewards when photovoltaic (PV) facilities are intended as a potential replacement for conventional peaking power plants. As the amount of solar irradiance usable by a PV module follows a stochastic process, we compare the outcomes using the following two strategies in a stochastic environment: (1) employing an optimal decision making approach without any specific knowledge of the environment; and (2) optimal decision making based upon learning patterns of the environment process. We examine the possibility of integrating a pattern learning approach – called an

ε

-Machine – with a Partially Observable Markov Decision Process (POMDP). This approach has been motivated in part by the fact that efforts in extending traditional learning approaches to POMDPs have so far achieved only limited success. The PV facility in our model consists of a PV panel and a battery, with an associated local, non-critical load. Under the assumption that any PV generated power exceeding the maximum local consumption capacity must be dumped when the battery is full, the goal of the autonomous control agent is to maintain the maximum output potential to most effectively offset unexpected demand peaks, while minimizing energy wastage in the presence of strong solar irradiance. The environment is assumed to follow a Markov process of a different order than the part of the system under the influence of the agent.

In tree based genetic programming there is a tendency for the size of the programs to increase from generation to generation, a process known as bloat. It is standard practice to place some form of control on program size either by limiting the number of nodes or the depth of the tree, or by adding a component to the fitness function that rewards smaller programs (parsimony pressure). Others have proposed directly simplifying individual programs using algebraic methods. In this paper, we add node-based numerical simplification as a tree pruning criterion to control program size. We show that simplification results in reductions in expected program size, memory use and computation time. We further show that numerical simplification performs at least as well as algebraic simplification alone, and in some cases will outperform algebraic simplification.

In this paper we try to understand the heuristics that underlie the decisions made by the Horn query learning algorithm proposed in [1]. We take advantage of our explicit representation of such heuristics in order to present an alternative termination proof for the algorithm, as well as to justify its decisions by showing that they always guarantee that the negative examples in the sequence maintained by the algorithm violate different clauses in the target formula. Finally, we propose a new algorithm that allows multiple refinement when we can prove that such a refinement does not affect the independence of the negative examples in the sequence maintained by the algorithm.

Evolutionary Meta Compilation (EMC) is a recent technique that enables unmodified external applications to seamlessly perform target program compilation and fitness evaluation for an Evolutionary Computation system. Grammatical Evolution (GE) is a method for evolving computer programs in an arbitrary programming language using a grammar specified in Backus-Naur Form. This paper combines these techniques to demonstrate the evolution of both sequential and combinational digital circuits in an Industry Standard Hardware Description Language (Verilog) using an external hardware synthesis engine and simulator. Overall results show the successful evolution of core digital circuit components. An extension to GE is also presented to attempt to increase the probability of maintaining an evolved program’s semantic integrity after crossover operations are performed. Early results show performance improvements in applying this technique to the majority of the presented test cases. It is suggested that this feature may also be considered for use in the evolution of software programs in C and other languages.

We present two methods to represent and use parameterised indexed FOR-loops in genetic programming. They are tested on learning the repetitive unit of regular binary pattern strings to reproduce these patterns to user specified arbitrary lengths. Particularly, we investigate the effectiveness of low-level and high-level functions inside these loops for the accuracy and the semantic efficiency of solutions. We used 5 test cases at increasing difficulty levels and our results show the high-level approach producing solutions in at least 19% of the runs when the low-level approach struggled to produce any in most cases.

We examine hierarchical fuzzy control of the inverted pendulum over the set of initial conditions. A new compositional method for the inverted pendulum system is introduced. Three layered hierarchical fuzzy logic topology is used to create a fuzzy rule base for the control system. Fuzzy rules are learnt by evolutionary algorithm designed for the compositional method.

Feature ranking (FR) provides a measure of usefulness for the attributes of a classification task. Most existing FR methods focus on the relevance of a single feature to the class labels. Here, we use GP to see how a set of features can contribute towards discriminating different classes and then we score the participating features accordingly. The scoring mechanism is based on the frequency of appearance of each feature in a collection of GP programs and the fitness of those programs. Our results show that the proposed FR method can detect important features of a problem. A variety of different classifiers restricted to just a few of these high-ranked features work well. The ranking mechanism can also shrink the search space of size

O

(2

n

) of subsets of features to a search space of size

O

(

n

) in which there are points that may improve the classification performance.

A framework for predictive, on-line, learning networks composed of multiple echo state networks is presented. These composite networks permit learning predictions based on complex combinations of sub-predictions and error terms. The configuration space is explored with a genetic algorithm and better performance is achieved than with hand coded solutions.

Design of software architecture is intellectually one of the most demanding tasks in software engineering. This paper proposes an approach to automatically synthesize software architecture using genetic algorithms. The technique applies architectural patterns for mutations and quality metrics for evaluation, producing a proposal for a software architecture on the basis of functional requirements given as a graph of functional responsibilities. Two quality attributes, modifiability and efficiency, are considered. The behavior of the genetic synthesis process is analyzed with respect to quality improve ment speed, the effect of dynamic mutation, and the effect of quality attribute prioritization. Our tests show that it is possible to genetically synthesize architectures that achieve a high fitness value early on.

Dual Phase Evolution (DPE) is a widespread natural process in which complex systems adapt and self-organise by switching alternately between two phases: a phase of global interactions and a phase of local interactions. We show that in evolving networks of agents, DPE can give rise to a wide variety of topologies. In particular, it can lead to the spontaneous emergence of stabilising modular structure.

In this paper, we investigate the role of heterogeneous payoff values and social diversity in a spatial version of the iterated prisoner’s dilemma game. Typically, a fixed number of agents play the game over a specified number of rounds. At each time step, the agents receive a fixed reward based on the strategy they have adopted and the corresponding payoff (or reward) matrix. We argue that such restrictions are unlikely to be fulfilled in real-life situations. Subsequently, we introduce additional features into the game. Here, each agent has an additional age attribute that can be used to control the number of iterations of the game an agent actually participates in. We also introduce dynamic payoff values that are correlated with particular agent experience levels. Numerical simulations show that the proposed heterogeneous agent model promotes the evolution of cooperation in some circumstances.

Unique input output (UIO) sequences have important applications in conformance testing of finite state machines (FSMs). Previous experimental and theoretical research has shown that evolutionary algorithms (EAs) can compute UIOs efficiently on many FSM instance classes, but fail on others. However, it has been unclear how and to what degree EA parameter settings influence the runtime on the UIO problem. This paper investigates the choice of acceptance criterion in the (1+1) EA and the use of crossover in the (

μ

+1) Steady State Genetic Algorithm. It is rigorously proved that changing these parameters can reduce the runtime from exponential to polynomial for some instance classes.

The development of power electronics results in a growing need for automatic design and optimization for power electronic circuits (PECs). This paper presents a particle swarm optimization (PSO) approach for the PECs design. The optimization problem is divided into two processes using a decoupled technique and PSO is employed to optimize the values of the circuit components in the power conversion stage (PCS) and the feedback network (FN), respectively. A simple mutation operator is also incorporated into PSO to enhance the population diversity. The algorithm is applied to the optimization of a buck regulator for meeting requirements under large-signal changes and at steady state. Compared with genetic algorithm (GA), PSO can yield more optimized values of circuit components with lower computational effort.

In this paper a number of popular Computational Intelligence (CI) algorithms are used to tune Geodesy models, a radio astronomy problem. Several single and multiple objective variations of the Geodesy problem are examined with good results obtained using state-of-the-art CI algorithms. These novel applications are used to develop insights into methods for applying CI algorithms to unknown problem domains and to provide interesting solutions to the Geodesy models used.

Presented in this paper is a hybrid algorithm for the design of discrete structures like trusses. The proposed algorithm called Discrete Structures Optimization (DSO) is based on the Evolutionary Structural Optimization (ESO) [1,2]. In DSO, material is removed from the structural elements based on the strain energy. DSO is a two stage process. First stage is the topology optimization where the elements of the structure with the least amount of strain energy are identified and eliminated. The second stage is the sizing optimization of the structure with optimum topology identified in first stage. For the continuous design variables a gradient based method is used and for the discrete design variables a genetic algorithm is used. The algorithm is tested on 2-D and 3-D discrete structures. DSO results show significant reduction in the number of finite element analysis (FEA) evaluations as compared to genetic algorithms using simultaneous topology and sizing optimization.

We introduce an application of Evolutionary Multi- Objective Optimization on multi-layered robot control system. Recent robot control systems consist of many simple function modules. The parameter settings for most of these modules were manually adjusted in previous research. Our goal is to develop an automatic parameter adjustment method for the robot control system. In this paper, we focused on three modules as the experiment environment: whole-body motion generator, footstep planner and path planner. At first the features of these three modules are examined. Then we discuss the trade-off relationship between the requirements of each module. Finally, we examined an application of Evolutionary Multi-Objective Optimization on this problem.

In this paper, we define a matchmaking party assignment problem and propose a system to solve it. The problem is to assign male and female participants to several small groups so that each group consists of the same number of men and women who have a good affinity for each other. The proposed system solves the problem based on an IEC (interactive evolutionary computation) framework, which can treat indefinable evaluation functions such as affinity between men and women by feeding back the empirically obtained values of those functions. Given each participant’s attributes such as bodily characteristics, academic background, and personality, which are obtained by questionnaire in advance, the system assigns the participants to several small groups in order to maximize the number of man and woman pairs likely to begin relationships. After each groups party, the number of pairs who liked each other can be obtained as a value of the evaluation function for EC (evolutionary computation). To evaluate the system, we define the

N

Max Problem assuming that there would be

N

good affinity patterns between men and women. Through computer simulations with

N

from 2 to 5, we confirmed that the proposed system could find a much better group assignment than a greedy approach.