We present a study on stress detection in virtual reality using The Last Secret, a stealth game we developed that integrates advanced multimodal stress detection techniques and in-game behavioral metrics. Our game responds to the player's emotional state and stress levels, dynamically adapting its gameplay in real-time. Players need to manage their stress to navigate the game effectively: maintaining calmness keeps them in an optimal flow state, whereas excessive stress can push them into a frustrating state, making progression significantly more difficult. We present experimental results showing the impact of stress-modulated gameplay on player engagement and performance, revealing findings aligned with the flow theory.

We present the agent we developed for the 2024 DareFightingICE competition that integrates advanced audio encoders, deep reinforcement learning, and hard-coded rules to improve the agent’s behavior for one specific, rarely used attack. The integration of hard-coded rules with our 1D-CNN encoder let our agent outperform the 2023 DareFightingICE AI winners (Pythunder and CAS). Our agent achieved second place in the competition, being the only top-ranking submission using machine learning, while the other entries implemented scripted strategies. Despite its strengths, our entry can be defeated by analyzing its favorite moves. We plan to enhance the audio encoders, refine long-term planning strategies, and optimize training methods to narrow the gap between our entry and the other top entries.

Selecting targets in dense, dynamic 3D environments presents a significant challenge. In this study, we introduce two novel selection techniques based on distractor pruning to assist users in selecting targets moving unpredictably: BaggingHook and AutoBaggingHook. Both are built upon the Hook intention-prediction heuristic, which continuously measures the distance between the user’s cursor and each object to compute per-object scores and estimate the intended target. Our techniques reduce the number of targets in the environment, making heuristic convergence potentially faster. Once pruned away, distractors are also made semi-transparent to reduce occlusion and the overall difficulty of the task. However, their motion is not altered, so that users can still perceive the dynamics of the environment. We designed two pruning approaches: BaggingHook lets users manually prune distractors away, while AutoBaggingHook uses automated, score-based pruning. We conducted a user study in a virtual reality setting inspired by molecular dynamics simulations, featuring crowded scenes of objects moving fast and unpredictably, in 3D. We compared both proposed techniques to the Hook baseline under more challenging circumstances than it had previously been tested. Our results show that AutoBaggingHook was the fastest, and did not lead to higher error rates. BaggingHook, on the other hand, was preferred by the majority of participants, due to the greater degree of control it provides to users, leading some to see entertainment value in its use. This work shows the potential benefits of varying the types of inputs used in intention-prediction heuristics, not just to improve performance, but also to reduce occlusion, overall task load, and improve user experience.

Large language models (LLMs) have taken the scientific world by storm, changing the landscape of natural language processing and human-computer interaction. These powerful tools can answer complex questions and, surprisingly, perform challenging creative tasks (e.g., generate code and applications to solve problems, write stories, pieces of music, etc.). In this paper, we present a collaborative game design framework that combines interactive evolution and large language models to simulate the typical human design process. We use the former to exploit users' feedback for selecting the most promising ideas and large language models for a very complex creative task---the recombination and variation of ideas. In our framework, the process starts with a brief and a set of candidate designs, either generated using a language model or proposed by the users. Next, users collaborate on the design process by providing feedback to an interactive genetic algorithm that selects, recombines, and mutates the most promising designs. We evaluated our framework on three game design tasks with human designers who collaborated remotely.

We present an educational application of virtual reality that we created to help students gain an in-depth understanding of the internal structure of crystals and related key concepts. Teachers can use it to give lectures to small groups (10-15) of students in a shared virtual environment, both remotely (with teacher and students in different locations) and locally (while sharing the same physical space). Lectures can be recorded, stored in an online repository, and shared with students who can either review a recorded lecture in the same virtual environment or can use the application for self-studying by exploring a large collection of available crystal structures. We validated our application with human subjects receiving positive feedback. Supplementary Information: The online version contains supplementary material available at 10.1007/s11042-022-13410-0https://doi.org/10.1007/s11042-022-13410-0.

Dropout rates for students in high education are remarkably high, and the phenomenon has been investigated in several studies. Student dropout represents a loss of human capital and a waste of resources. This paper presents an analytic learning framework we have been developing at university to identify potential dropout situations in engineering bachelor students. We discuss the underlying model and show how it has been deployed in an analytics pipeline that alerts schools by predicting possible dropout situations. Our tool is also prescriptive in that it provides insight that might suggest strategies to reduce the dropout rates.

We present an algorithm to add puzzles to maps represented as graphs. The algorithm starts from an empty map, represented as a graph, with at least one entry area and one exit area. It runs several specialized agents responsible for adding puzzles (e.g., locked doors, keys, switches). It generates a map with at least one acceptable solution (path) whose difficulty depends on the type of agents used (that is, the variety of puzzles added) and the number of puzzles added by each agent. Most importantly, no sequence of actions can leave the players stuck in a dead-end situation with no way to reach the goal. We include two examples of agents specialized in (i) switch mechanics (e.g., a lever that opens a passage and closes another one, the lighting of a fire that shows an inscription needed to solve another puzzle), and (ii) element collection mechanics (e.g., collecting keys or other puzzle elements to open a passage).

Chest X-ray (CXR) is perhaps the most frequently-performed radiological investigation globally. In this work, we present and study several machine learning approaches to develop automated CXR diagnostic models. In particular, we trained several Convolutional Neural Networks (CNN) on the CheXpert dataset, a large collection of more than 200k CXR labeled images. Then, we used the trained CNNs to compute embeddings of the CXR images, in order to train two sets of tree-based classifiers from them. Finally, wed escribed and compared three ensembling strategies to combine together the classifiers trained. Rather than expecting some performance-wise benefits, o ur goal i n this work iss howing that t he above two methodologies, i.e., the extraction of image embeddings and models ensembling, can be effective and viable to solve tasks that require medical imaging understanding. Our results in that perspective are encouraging and worthy of further investigation.

Patients undergoing physical rehabilitation therapy must perform series of exercises regularly over a long period of time to improve, or at least not to worsen, their condition. Rehabilitation can easily become boring because of the tedious repetition of simple exercises, which can also cause mild pain and discomfort. As a consequence, patients often fail to follow their rehabilitation schedule with the required regularity, thus endangering their recovery. In the last decade, video games have become largely popular and the availability of advanced input controllers has made them a viable approach to make physical rehabilitation more entertaining while increasing patients motivation. In this paper, we present a framework integrating serious games for the lower-limb rehabilitation of children suffering from Juvenile Idiopathic Arthritis (JIA). The framework comprises games that implement parts of the therapeutic protocol followed by the young patients and provides modules to tune, control, record, and analyze the therapeutic sessions. We present the result of a preliminary validation we performed with patients at the clinic under therapists supervision. The feedback we received has been overall very positive both from patients, who enjoyed performing their usual therapy using video games, and therapists, who liked how the games could keep the children engaged and motivated while performing the usual therapeutic routine.

Ten years ago we started a course on video game design and development. It was the first course on video games in our university and possibly in our country. We were immediately daunted by two main decisions: (i) the selection of the projects to be developed during the course and (ii) the evaluation of students’ projects. We wanted to give students the maximum freedom and no limit to their creativity. We wanted them to focus on the creation of a game that people would love to play without worrying about some score objectives to maximize and without caring about their instructors’ game design preferences. Accordingly, we decided to ask students to do all the job, starting from the submission and the selection of the game concepts to develop during the course, up to the final evaluation of the projects, the evaluation of their teammates, and thus basically the grading. In this paper, we discuss our experience over the last ten years with our course organization and grading model that, we believe, gives students complete freedom to express themselves and leaves them most of, if not all, the agency.

In this work, following the same approach successfully applied to evolve Super Mario levels, we applied the CMA-ES to search the latent space of a GAN previously trained to generate DOOM levels. Combining a search algorithm with a model trained in a supervised setting, allows to take advantage from both these paradigms. From one hand, the GAN is able to generate contents exploiting the design patterns learned from all the examples it was trained from. On the other hand, the CMA-ES can effectively search this design space for specific contents that meet some given design objectives. In particular, we tested our approach evolving three very different type of levels: an arena level (i.e., few large areas), a labyrinth level (i.e., many corridors and small areas), and a complex level (i.e., a balanced mix of large and small areas). Our results show that the latent space of a GAN can be effectively searched by the CMA-ES to find DOOM levels that fit accurately the objectives but, at the same time, are also novel.

Monte Carlo Tree Search (MCTS) does not require any prior knowledge about a game to play, except for its legal moves and end conditions. Thus, the same MCTS player can be applied (almost) as it is to a wide variety of games. Accordingly, MCTS may be used as a touchstone to evaluate artificial players on different games. In this paper, we propose to use MCTS to qualitatively evaluate the strength of artificial players as the minimum number of iterations that MCTS needs to perform equivalently to the target player. We define this value as the "MCTS complexity" of the target player. We introduce a bisection procedure to compute the MCTS complexity of a player and present experiments to evaluate the proposed approach on three games: Connect4, Awari, and Othello. Initially, we apply our approach to compute the MCTS complexity of players implemented using MCTS with a known number of iterations, next to players using different strategies. Our preliminary results show that our approach can identify the number of iterations used by MCTS target players. When applied to players implementing unknown strategies, it produces results that are coherent with the underlying players’ strength, assigning higher values of MCTS complexity to stronger players. Our results also suggest that, by using iterations to evaluate the strength of players, we may be able to compare the strength of algorithms that would be incomparable in practice (e.g. a greedy strategy for Connect4 and alpha-beta pruning for Awari).

We present the design of a competitive artificial intelligence for Scopone, a popular Italian card game. We compare rule-based players using the most established strategies (one for beginners and two for advanced players) against players using Monte Carlo Tree Search (MCTS) and Information Set Monte Carlo Tree Search (ISMCTS) with different reward functions and simulation strategies. MCTS requires complete information about the game state and thus implements a cheating player, whereas ISMCTS can deal with incomplete information and thus implements a fair player. Our results show that, as expected, the cheating MCTS outperforms all the other strategies; ISMCTS is stronger than all the rule-based players implementing well-known and most advanced strategies and it also turns out to be a challenging opponent for human players.

Computer games are a promising tool to support intensive rehabilitation. However, at present, they do not incorporate the supervision provided by a real therapist and do not allow safe and effective use at a patient's home. We show how specifically tailored computational intelligence based techniques allow extending exergames with functionalities that make rehabilitation at home effective and safe. The main function is in monitoring the correctness of motion, which is fundamental in avoiding developing wrong motion patterns, making rehabilitation more harmful than effective. Fuzzy systems enable us to capture the knowledge of the therapist and to provide real-time feedback of the patient's motion quality with a novel informative color coding applied to the patient's avatar. This feedback is complemented with a therapist avatar that, in extreme cases, explains the correct way to carry out the movements required by the exergames. The avatar also welcomes the patient and summarizes the therapy results to him/her. Text to speech and simple animation improve the engagement. Another important element is adaptation. Only the proper level of challenge exercises can be both effective and safe. For this reason exergames can be fully configured by therapists in terms of speed, range of motion, or accuracy. These parameters are then tuned during exercise to the patient's performance through a Bayesian framework that also takes into account input from the therapist. A log of all the interaction data is stored for clinicians to assess and tune the therapy, and to advise patients. All this functionality has been added to a classical game engine that is extended to embody a virtual therapist aimed at supervising the motion, which is the final goal of the exergames for rehabilitation. This approach can be of broad interest in the serious games domain. Preliminary results with patients and therapists suggest that the approach can maintain a proper challenge level while keeping the patient motivated, safe, and supervised.

A learning strategy in Learning Classifier Systems (LCSs) defines how classifiers cover a state-action space in a problem. Previous analyses in classification problems have empirically claimed an adequate learning strategy can be decided depending on the types of noise in the problem. This issue is still arguable from two aspects. First, there lacks comparison of learning strategies in reinforcement learning problems with different types of noise. Second, when we can claim so, a further issue is how should classifiers cover the state-action space in order to improve the stability of LCS performance on as many types of noise as possible? This paper first attempts to empirically conclude these issues on a version of LCSs (i.e., the XCS classifier system). That is, we present a new concept of learning strategy for LCSs, and complement that claim by comparing it with the existing learning strategies on a reinforcement learning problem. Our learning strategy covers all state-action pairs but assigns more classifiers to the highest-return action at each state than other actions. Our results support that claim that existing learning strategies have dependencies on the types of noise in reinforcement learning problems. However, our learning strategy improves the stability of XCS performance compared with the existing strategies on all types of noise employed in this paper.

We study two existing Learning Classifier Systems (LCSs): XCS, which has a complete map (which covers all actions in each state), and XCSAMm, which has a best action map (which covers only the highest-return action in each state). This allows XCSAM to learn with a smaller population size limit (but larger population size) and to learn faster than XCS on well-behaved tasks. However, many tasks have dif- ficulties like noise and class imbalances. XCS and XCSAM have not been compared on such problems before. This pa- per aims to discover which kind of map is more robust to these difficulties. We apply them to a classification problem (the multiplexer problem) with class imbalance, Gaussian noise or alternating noise (where we return the reward for a different action). We also compare them on real-world data from the UCI repository without adding noise. We analyze how XCSAM focuses on the best action map and introduce a novel deletion mechanism that helps to evolve classifiers towards a best action map. Results show the best action map is more robust (has higher accuracy and sometimes learns faster) in all cases except small amounts of alternat- ing noise.

This paper proposes a novel rule discovery mechanism for the XCS classifier system, which is an extension of the compact genetic algorithm (cGA) to XCS. Our rule discovery mechanism, like cGA, extracts appropriate attributes of classifier conditions through a probability vector and evolves classifiers using the extracted attributes. Unlike cGA, it newly builds the probability vector at every generations (i.e., it keeps no any probability vectors) not so that it requires XCS to have a lot of probability vectors that represent all available attributes, and mutates classifier conditions based on the extracted attributes as attribute feedback. Experimental results show that XCS with our rule discovery mechanism (or XCScGA) can reach optimal performance with fewer rule evaluations and requires smaller population sizes than XCS. Our conclusion is that the proposed rule discovery mechanism promotes a recombination of building blocks, and that our mutation operator works to repair the classifier conditions towards a compact solutions, hence, XCScGA can generate good offspring which represent maximally general, maximally accurate, and compact solutions.

XCS with Adaptive Action Mapping (XCSAM) evolves so- lutions focused on classifiers that advocate the best action in every state. Accordingly, XCSAM usually evolves more compact solutions than XCS which, in contrast, works to- ward solutions representing complete state-action mappings. Experimental results have however shown that, in some prob- lems, XCSAM may produce bigger populations than XCS. In this paper, we extend XCSAM with a novel selection strat- egy to reduce, even further, the size of the solutions XCSAM produces. The proposed strategy selects the parent classi- fiers based both on their fitness values (like XCS) and on the effect they have on the adaptive map. We present experi- mental results showing that XCSAM with the new selection strategy can evolve more compact solutions than XCS which, at the same time, are also maximally general and maximally accurate.

We present a framework for the procedural generation of tracks for a high-end car racing game (TORCS) using interactive evolution. The framework maintains multiple populations and allow users to work both on their own population (in single-user mode) or to collaborate with other users on a shared population. Our architecture comprises a web frontend and an evolutionary backend. The former manages the interaction with users (e.g., logs registered and anonymous users, collects evaluations, provides access to all the evolved populations) and maintains the database server that stores all the present/past populations. The latter runs all the tasks related to evolution (selection, recombination and mutation) and all the tasks related to the target racing game (e.g., the track generation). We performed two sets of experiments involving five human subjects to evolve racing tracks alone (in a single-user mode) or cooperatively. Our preliminary results on five human subjects show that, in all the experiments, there is an increase of users' satisfaction as the evolution proceeds. Users stated that they perceived improvements in the quality of the individuals between subsequent populations and that, at the end, the process produced interesting tracks.

In this paper, we investigate the application of evolutionary computation to the automatic generation of tracks for high-end racing games. The idea underlying our approach is that diversity is a major source of challenge/interest for racing tracks and, eventually, might play a key role in contributing to the player's fun. In particular, we focus on the diversity of a track in terms of its shape (i.e., the number and the assortment of turns and straights it contains), and in terms of driving experience it provides (i.e., the range of speeds achievable while driving on the track). We define two fitness functions that capture our idea of diversity as the entropy of the track's curvature and speed profiles. We apply both a single-objective and a multiobjective real-coded genetic algorithm (GA) to evolve tracks involving both a wide variety of turns and straights and also a large range of driving speeds. The results we report show that both single-objective and multiobjective approaches can successfully evolve tracks with a high degree of diversity both in terms of shape and achievable speeds.

This paper presents a framework for the design space exploration of reliable FPGA systems based on a multi-objective genetic algorithm (NSGA-II). The framework takes into account several design metrics and outputs a set of Pareto-optimal design solutions. The framework is compared to the multi-objective version of simulated annealing (AMOSA) and it is empirically studied in terms of scalability using three real-world circuits and a set of synthetic problems of different sizes. Our results show that the proposed approach generates a rich set of Pareto-optimal solutions whereas AMOSA tends to find suboptimal solutions. Our empirical scalability analysis shows that, while the problem space is exponential in the number n of functional units constituting the system, the number of evaluations required by our framework grows as O(n3.6).

The TORCS Endurance World Championship is an international competition in which programmers develop and tune their drivers to race against each other using TORCS, a state-of-the-art car racing simulator. In this work, we applied evolutionary computation to develop a driver for the 2009 edition of this competition. In particular, we focused on the optimization of the car setup of an existing driver (the winner of the 2008 edition) and applied cooperative coevolution to evolve the best car setup for the qualifying rounds of each leg of the championship. After 10 legs involving 12 teams, our driver was able to reach the 4th position in the final standings. We believe that this is a very promising result especially if we consider that we only focused on the car setup and the other teams participated also to most of the previous four editions (gaining much domain knowledge). Overall, our results show that cooperative coevolution can be very effective in this complex optimization task producing setups that can be competitive with respect to the ones tuned by human experts. Therefore, our results also suggest that simple evolutionary computation might represent a helpful tool to human designers for improving the performance of already heavily tuned drivers.

This paper presents a Learning Classifier System (LCS) where each traditional rule is represented by a spiking neural network, a type of network with dynamic internal state. The evolutionary design process exploits parameter self-adaptation and a constructionist approach, providing the system with a flexible knowledge representation. It is shown how this approach allows for the evolution of networks of appropriate complexity to emerge whilst solving a continuous maze environment. Additionally, we extend the system to allow for temporal state decomposition. We evaluate our spiking neural LCS against one that uses Multi Layer Perceptron rules.

In modern racing games programming non-player characters with believable and sophisticated behaviors is getting increasingly challenging. Recently, several works in the literature suggested that computational intelligence can provide effective solutions to support the development process of NPCs. In this paper, we applied the Behavior Analysis and Training (BAT) methodology to define a behavior-based architecture for the NPCs in The Open Racing Car Simulator (TORCS), a well-known open source racing game. Then, we focused on two major overtaking behaviors: (i) the overtaking of a fast opponent either on a straight stretch or on a large bend; (ii) the overtaking on a tight bend, which typically requires a rather advanced braking policy. We applied simple reinforcement learning, namely Q-learning, to learn both these overtaking behaviors. We tested our approach in several overtaking situations and compared the learned behaviors against one of the best NPC provided with TORCS. Our results suggest that, exploiting the proposed behavior-based architecture, Q-learning can effectively learn sophisticated behaviors and outperform programmed NPCs. In addition, we also show that the same approach can be successfully applied to adapt a previously learned behavior to a dynamically changing game situation.

TestFul is a novel evolutionary testing approach for object-oriented programs with complex internal states. In our preliminary experiments, it already outperformed some of the well-known search-based testing approaches. In this paper we show how TestFul can be further improved by leveraging three efficiency enhancement techniques: seeding, hybridization, and fitness inheritance. We considered four extensions of TestFul: three using each enhancement separately, and one using all of them at the same time. We used these new versions of TestFul to generate tests for six Java classes taken from the literature, public software libraries, and third party benchmarks. We compared the performance of the original TestFul against these new versions. Our results show that each enhancement technique results in a significant speed-up and, even more interesting, the highest improvement is achieved when all the enhancements are combined together.

In this paper, we apply multi-objective evolutionary computation to the synthesis of real-time, embedded, heterogeneous, multiprocessor systems (briefly, Multiprocessor Systems-on-Chip or MP-SoCs). Our approach simultaneously explores the architecture, the mapping and the scheduling of the system, by using multi-objective evolution. In particular, we considered three approaches: a multi-objective genetic algorithm, multi-objective Simulated Annealing, and multi-objective Tabu Search. The algorithms search for optimal architectures, in terms of processing elements (processors and hardware accelerators) and communication infrastructure, and for the best mappings and schedules of multi-rate real-time applications given objectives such as: system area, hard and soft dead-lines violations, dimensions of memory buffers. We formalize the problem, describe our flow and compare the three algorithms, dis- cussing which one performs better with respect to different classes of applications.

This paper presents TestFul, an evolutionary testing approach for Java classes that works both at class and method level. TestFul exploits a multi-objective evolutionary algorithm to identify the “best” tests. The paper introduces the main elements of TestFul. It also compares TestFul against well-known search-based solutions using a set of classes taken from literature, known software libraries, and independent testing benchmarks. The comparison considers statement and branch coverage, size of generated tests, and generation time. On considered classes, TestFul generates better tests than other search-based solutions, and achieves higher structural coverages with tests small enough to be usable.

To exploit the power of modern heterogeneous multiprocessor embedded platforms on partitioned applications, the designer usually needs to efficiently map and schedule all the tasks and the communications of the application, respecting the constraints imposed by the target architecture. Since the problem is heavily constrained, common methods used to explore such design space usually fail, obtaining low-quality solutions. In this paper, we propose an ant colony optimization (ACO) heuristic that, given a model of the target architecture and the application, efficiently executes both scheduling and mapping to optimize the application performance. We compare our approach with several other heuristics, including simulated annealing, tabu search, and genetic algorithms, on the performance to reach the optimum value and on the potential to explore the design space. We show that our approach obtains better results than other heuristics by at least 16% on average, despite an overhead in execution time. Finally, we validate the approach by scheduling and mapping a JPEG encoder on a realistic target architecture.

In this paper, we applied online neuroevolution to evolve nonplayer characters for The Open Racing Car Simulator (TORCS). While previous approaches allowed online learning with performance improvements during each generation, our approach enables a finer grained online learning with performance improvements within each lap. We tested our approach on three tracks using two methods of online neuroevolution (NEAT and rtNEAT) combined with four evaluation strategies ( -greedy, -greedy-improved, softmax, and interval-based) taken from the literature. We compared the eight resulting configurations on several driving tasks involving the learning of a driving behavior for a specific track, its adaptation to a new track, and the generalization capability to unknown tracks. The results we present show that, notwithstanding the several challenges that online learning poses, our approach 1) can successfully evolve drivers from scratch, 2) can also be used to transfer evolved knowledge to other tracks, and 3) can generalize effectively producing controllers that can drive on difficult unseen tracks. Our results also suggest that the approach performs better when coupled with online NEAT and also indicate that -greedy-improved and softmax are generally better than the other evaluation strategies. A comparison with typical offline neuroevolution suggests that online neuroevolution can be competitive and even outperform traditional offline approaches on more difficult tracks while providing all the interesting features of online learning. Overall, we believe that this study may represent an initial step toward the application of online neuroevolution in games.

In this paper, we overview the 2009 Simulated Car Racing Championship-an event comprising three competitions held in association with the 2009 IEEE Congress on Evolutionary Computation (CEC), the 2009 ACM Genetic and Evolutionary Computation Conference (GECCO), and the 2009 IEEE Symposium on Computational Intelligence and Games (CIG). First, we describe the competition regulations and the software framework. Then, the five best teams describe the methods of computational intelligence they used to develop their drivers and the lessons they learned from the participation in the championship. The organizers provide short summaries of the other competitors. Finally, we summarize the championship results, followed by a discussion about what the organizers learned about 1) the development of high-performing car racing controllers and 2) the organization of scientific competitions.

Providing clinical predictions for cancer patients by analyzing their genetic make-up is a difficult and very important issue. With the goal of identifying genes more correlated with the prognosis of breast cancer, we used data mining techniques to study the gene expression values of breast cancer patients with known clinical outcome. Focus of our work was the creation of a classification model to be used in the clinical practice to support therapy prescription. We randomly subdivided a gene expression dataset of 311 samples into a training set to learn the model and a test set to validate the model and assess its performance. We evaluated several learning algorithms in their not weighted and weighted form, which we defined to take into account the different clinical importance of false positive and false negative classifications. Based on our results, these last, especially when used in their combined form, appear to provide better results.

The application of on-line learning techniques to modern computer games is a promising research direction. In fact, they can be used to improve the game experience and to achieve a true adaptive game AI. So far, several works proved that neuroevolution techniques can be successfully applied to modern computer games but they are usually restricted to offline learning scenarios. In on-line learning problems the main challenge is to find a good trade-off between the exploration, i.e., the search for better solutions, and the exploitation of the best solution discovered so far. In this paper we propose an on-line neuroevolution approach to evolve non-player characters in The Open Car Racing Simulator (TORCS), a state-of-the-art open source car racing simulator. We tested our approach on two on-line learning problems: (i) on-line evolution of a fast controller from scratch and (ii) optimization of an existing controller for a new track. Our results show that on-line neuroevolution can effectively improve the performance achieved during the learning process.

Several studies have analyzed the link between mental dysfunctions and eye movements, using eye tracking techniques to determine where a person is looking, that is, the fixations. In this paper, we present a novel methodology to improve current diagnosis and evaluation methods of attention disorders. We have developed and tested several data-mining methodologies suitable for the automatic analysis and visualization of eye tracking data. In particular three novel methods of classification of subjects are proposed: (i) a method that uses expectation maximization to classify according to statistical likelihood of fixations locations; (ii) a procedure based on the Levenshtein distance method to compare sequences of fixations; and (iii) a method based on the analysis of the transitions frequencies of fixations between regions. Results of evaluation of classification accuracy are finally presented.

In this paper, we compare four algorithms for the mapping of pipelined applications on a heterogeneous multiprocessor platform implemented using Field Programmable Gate Arrays (FPGAs) with customizable processors. Initially, we describe the framework and the model of pipelined application we adopted. Then, we focus on the problem of mapping a set of pipelined applications onto a heterogeneous multiprocessor platform and consider four search algorithms: Tabu Search, Simulated Annealing, Genetic Algorithms, and the Bayesian Optimization Algorithm. We compare the performance of these four algorithms on a set of synthetic problems and on two real-world applications (the JPEG image encoding and the ADPCM sound encoding). Our results show that on our framework the Bayesian Optimization Algorithm outperforms all the other three methods for the mapping of pipelined applications.

Modern computer games are at the same time an attractive application domain and an interesting testbed for the evolutionary computation techniques. In this paper we apply NeuroEvolution of Augmenting Topologies (NEAT), a well known neuroevolution approach, to evolve competitive non-player characters for a racing game. In particular, we focused on The Open Car Racing Simulator (TORCS), an open source car racing simulator, already used as a platform for several scientific competitions dedicated to games. We suggest that a competitive controller should have two basic skills: it should be able to drive fast and reliably on a wide range of tracks and it should be able to effectively overtake the opponents avoiding the collisions. In this paper we apply NEAT to evolve separately these skills and then we combined them together in a single controller. Our results show that the resulting controller outperforms the best available controllers on a challenging racing task. In addition, the experimental analysis also confirms that both the skills are necessary to develop a competitive controller.

This paper presents a Learning Classifier System (LCS) where each classifier condition is represented by a feed-forward multi-layered perceptron (MLP) network. Adaptive behavior is realized through the use of self-adaptive parameters and neural constructivism, providing the system with a flexible knowledge representation. The approach allows for the evolution of networks of appropriate complexity to solve a continuous maze environment, here using either discrete-valued actions, continuous-valued actions, or continuous-valued actions of continuous duration. In each case, it is shown that the neural LCS employed is capable of developing optimal solutions to the reinforcement learning task presented in this paper.

This paper introduces TestFul, a framework for testing stateful systems and focuses on object-oriented software. TestFul employs a hybrid multi-objective evolutionary algorithm, to explore the space of feasible tests efficiently, and novel quality metrics, based on both def-use pairs and behavioral coverage, to judge the quality of tests. We compare our framework against random testing by considering the level of coverage, the size of generated tests, and the time required to generate the tests. Our preliminary results show the validity of the approach: TestFul outperforms random testing in most of the cases.

Michigan-style learning classifier systems (LCSs) are online machine learning techniques that incrementally evolve distributed subsolutions which individually solve a portion of the problem space. As in many machine learning systems, extracting accurate models from problems with class imbalances-that is, problems in which one of the classes is poorly represented with respect to the other classes-has been identified as a key challenge to LCSs. Empirical studies have shown that Michigan-style LCSs fail to provide accurate subsolutions that represent the minority class in domains with moderate and large disproportion of examples per class; however, the causes of this failure have not been analyzed in detail. Therefore, the aim of this paper is to carefully examine the effect of class imbalances on different LCS components. The analysis focuses on XCS, which is the most-relevant Michigan-style LCS, although the models could be easily adapted to other LCSs. Design decomposition is used to identify five elements that are crucial to guaranteeing the success of LCSs in domains with class imbalances, and facetwise models that explain these different elements for XCS are developed. All theoretical models are validated with artificial problems. The integration of all these models enables us to identify the sweet spot where XCS is able to scalably and efficiently evolve accurate models of rare classes; furthermore, facetwise analysis is used as a tool for designing a set of configuration guidelines that have to be followed to ensure convergence. When properly configured, XCS is shown to be able to solve highly unbalanced problems that previously eluded solution.

In XCS with computed prediction, namely XCSF, the classifier prediction parameter is replaced by a parametrized prediction function. So far, the works on the computed prediction in XCSF has been limited to evolve a single type of prediction function at once. Recently, several works studied and extended the computed prediction in XCSF. However, it is still not clear how the most adequate prediction function should be chosen for a given problem. In this paper we introduce XCSF with voting predictors that extends XCSF to let it select best prediction function to use in each problem subspace. We compared XCSFV to XCSF on several problems. Our results suggest that XCSFV performs as well as XCSF with the best prediction function in all the tested problems. In addition, XCSFV finds the most accurate prediction function in each problem subspace.

Computed prediction was originally devised to tackle problems defined over real-valued domains. Recent experiments on Boolean functions showed that the concept of computed prediction extends beyond real values and it can also be applied to solve more typical classifier system benchmarks such as Boolean multiplexer and parity functions. So far however, no result has been presented for other well known classifier system benchmarks, i.e., binary multistep problems such as the woods environments. In this paper, we apply XCS with computed prediction to woods environments and show that computed prediction can also tackle this class of problems. Our results demonstrate that (i) XCS with computed prediction converges to optimality faster than XCS, (ii) it solves problems that may be too difficult for XCS and (iii) it evolves solutions that are more compact than those evolved by XCS.

The high-level synthesis process involves three interdependent and NP-complete optimization problems: (i) the operation scheduling, (ii) the resource allocation, and (iii) the controller synthesis. Evolutionary algorithms have been effectively applied to high level synthesis in presence conflicting design objectives for finding good tradeoffs in the design space. However, so far the design space exploration has been performed using single-objective evolutionary algorithms with an ad hoc fitness function to achieve the desired tradeoff between the objectives. Recently we proposed a framework based on multi-objective genetic algorithms to perform a fully automated design space exploration. In this paper we focus on the choice of the solution representations that can be used to perform the design space exploration with multi-objective genetic algorithms. In particular we consider two specific representations and compare them on a set of benchmark problems. Our results suggest that they have different biases on the search space that make them more effective in different problems and design subspaces. Accordingly, we present a preliminary investigation on a new representation that exploits the advantages of both of them.

We investigate rule matching in learning classifier systems for problems involving binary and real inputs. We consider three rule encodings: the widely used character-based encoding, a specificity-based encoding, and a binary encoding used in Alecsys. We compare the performance of the three algorithms both on matching alone and on typical test problems. The results on matching alone show that the population generality influences the performance of the matching algorithms based on string representations in different ways. Character-based encoding becomes slower and slower as generality increases, specificity-based encoding becomes faster and faster as generality increases. The results on typical test problems show that the specificity-based representation can halve the time required for matching but also that binary encoding is about ten times faster on the most difficult problems. Moreover, we extend specificity-based encoding to real-inputs and propose an algorithm that can halve the time require for matching real inputs using an interval-based representation.

Recent advances in XCS technology have shown that self-adaptive mutation can be highly useful to speed-up the evolutionary progress in XCS. Moreover, recent publications have shown that XCS can also be successfully applied to challenging real-valued domains including datamining, function approximation, and clustering. In this paper, we combine these two advances and investigate self-adaptive mutation in the XCS system for function approximation with hyperellipsoidal condition structures, referred to as XCSF in this paper. It has been shown that XCSF solves function approximation problems with an accuracy, noise robustness, and generalization capability comparable to other statistical machine learning techniques and that XCSF outperforms simple clustering techniques to which linear approximations are added. This paper shows that the right type of self-adaptive mutation can further improve XCSF's performance solving problems more parameter independent and more reliably. We analyze various types of self-adaptive mutation and show that XCSF with self-adaptive mutation ranges,differentiated for the separate classifier condition values, yields most robust performance results. Future work may further investigate the properties of the self-adaptive values and may integrate advanced self-adaptation techniques.

For artificial entities to achieve high degrees of autonomy they will need to display appropriate adaptability. In this sense adaptability includes representational flexibility guided by the environment at any given time. This paper presents the use of constructivism-inspired mechanisms within a neural learning classifier system which exploits parameter self-adaptation as an approach to realize such behaviour. The system uses a rule structure in which each is represented by an artificial neural network. It is shown that appropriate internal rule complexity emerges during learning at a rate controlled by the system. Further, the use of computed predictions is shown possible.

An important strength of learning classifier systems (LCSs) lies in the combination of genetic optimization techniques with gradient-based approximation techniques. The chosen approximation technique develops locally optimal approximations, such as accurate classification estimates, Q-value predictions, or linear function approximations. The genetic optimization technique is designed to distribute these local approximations efficiently over the problem space. Together, the two components develop a distributed, locally optimized problem solution in the form of a population of expert rules, often called classifiers. In function approximation problems, the XCSF classifier system develops a problem solution in the form of overlapping, piecewise linear approximations. This paper shows that XCSF performance on function approximation problems additively benefits from: 1) improved representations; 2) improved genetic operators; and 3) improved approximation techniques. Additionally, this paper introduces a novel closest classifier matching mechanism for the efficient compaction of XCS's final problem solution. The resulting compaction mechanism can boil the population size down by 90% on average, while decreasing prediction accuracy only marginally. Performance evaluations show that the additional mechanisms enable XCSF to reliably, accurately, and compactly approximate even seven dimensional functions. Performance comparisons with other, heuristic function approximation techniques show that XCSF yields competitive or even superior noise-robust performance.

In this paper, we study the use of anticipation mappings in learning classifier systems. At first, we enrich the eXtended Classifier System (XCS) with two types of anticipation mappings: one based on array of perceptrons array, one based on neural networks. We apply XCS with anticipation mappings (XCSAM) to several multistep problems taken from the literature and compare its anticipatory performance with that of the Neural Classifier System X-NCS which is based on a similar approach. Our results show that, although XCSAM is not a “true” Anticipatory Classifier System like ACS, MACS, or X-NCS, nevertheless XCSAM can provide accurate anticipatory predictions while requiring smaller populations than those needed by X-NCS.

This paper presents a simple real-coded estimation of distribution algorithm (EDA) design using χ-ary extended compact genetic algorithm (χECGA) and discretization methods. Specifically, the real-valued decision variables are mapped to discrete symbols of user-specified cardinality using discretization methods. The χECGA is then used to build the probabilistic model and to sample a new population based on the probabilistic model. The effect of alphabet cardinality and the selection pressure on the scalability of the real-coded ECGA (rECGA) method is investigated. The results show that the population size required by rECGA—to successfully solve a class of additivelyseparable problems—scales sub-quadratically with problem size and the number of function evaluations scales sub-cubically with problem size. The proposed rECGA is simple, making it amenable for further empirical and theoretical analysis. Moreover, the probabilistic models built in the proposed realcoded ECGA are readily interpretable and can be easily visualized. The proposed algorithm and the results presented in this paper are first step towards conducting a systematic analysis of real-coded EDAs and towards developing a design theory for development of scalable and robust real-coded EDAs

We analyze generalization in the extended classifier system (XCS) with symbolic conditions, based on genetic programming, briefly XCSGP. We start from the results presented in the literature, which showed that XCSGP could not reach optimality in Boolean problems when classifier conditions involved logical disjunctions. We apply a new implementation of XCSGP to the learning of Boolean functions and show that our version can actually reach optimality even when disjunctions are allowed in classifier conditions. We analyze the evolved generalizations and explain why logical disjunctions can make the learning more difficult in XCS models and why our version performs better than the earlier one. Then, we show that in problems that allow many generalizations, so that or clauses are less "convenient", XCSGP tends to develop solutions that do not exploit logical disjunctions as much as one might expect. However, when the problems allow few generalizations, so that or clauses become an interesting way to introduce simple generalizations, XCSGP exploit them so as to evolve more compact solutions.

XCS with computed action, briefly XCSCA, is a recent extension of XCS to tackle problems involving a large number of discrete actions. In XCSCA the classifier action is computed with a parameterized function learned in a supervised fashion. In this paper, we introduce XCSCAsvm that extends XCSCA using support vector machines to compute classifier action. We compared XCSCAsvm and XCSCA on the learning of several binary functions. The experimental results show that XCSCAsvm reaches the optimal performance faster than XCSCA.

The high-level synthesis process allows the automatic design and implementation of digital circuits starting from a behavioral description. Evolutionary algorithms are very widely adopted to approach this problem or just part of it. Nevertheless, some concerns regarding execution times exist. In evolutionary high-level synthesis, design solutions have to be evaluated to extract information about some figures of merit (such as performance, area, etc.) and to allow the genetic algorithm to evolve and converge to Pareto-optimal solutions. Since the execution time of such evaluations increases with the complexity of the specification, the overall methodology could lead to unacceptable execution time. This paper presents a model to exploit fitness inheritance in a multi-objective optimization algorithm (i.e. NSGA-II) by substituting the expensive real evaluations with estimations based on closeness in an hypothetical design space. The estimations are based on the measure of the distance between individuals and a weighted average of the fitnesses of the closest ones. The results shows that the Pareto-optimal set obtained by applying the proposed model well approximates the set obtained without fitness inheritance. Moreover, the overall execution time is reduced up to the 25% in average.

We analyze generalization and learning in XCS with gradient descent. At first, we show that the addition of gradient in XCS may slow down learning because it indirectly decreases the learning rate. However, in contrast to what was suggested elsewhere, gradient descent has no effect on the achieved generalization. We also show that when gradient descent is combined with roulette wheel selection, which is known to be sensitive to small values of the learning rate, the learning speed can slow down dramatically. Previous results reported no difference in the performance of XCS with gradient descent when roulette wheel selection or tournament selection were used. In contrast, we suggest that gradient descent should always be combined with tournament selection, which is not sensitive to the value of the learning rate. When gradient descent is used in combination with tournament selection, the results show that (i) the slowdown in learning is limited and (ii) the generalization capabilities of XCS are not affected.

The learning in a niche based learning classifier system depends both on the complexity of the problem space and on the number of available actions. In this paper, we introduce a version of XCS with computed actions, briefly XCSCA, that can be applied to problems involving a large number of actions. We report experimental results showing that XCSCA can evolve accurate and compact representations of binary functions which would be challenging for typical learning classifier system models.

In this paper we introduce XCSF with support vector prediction: the problem of learning the prediction function is solved as a support vector regression problem and each classifier exploits a Support Vector Machine to compute the prediction. In XCSF with support vector prediction, XCSFsvm, the genetic algorithm adapts classifier conditions, classifier actions, and the SVM kernel parameters. We compare XCSF with support vector prediction to XCSF with linear prediction on the approximation of four test functions. Our results suggest that XCSF with support vector prediction compared to XCSF with linear prediction (i) is able to evolve accurate approximations of more difficult functions, (ii) has better generalization capabilities and (iii) learns faster.

In this paper, we derive models of the selection pressure in XCS for proportionate (roulette wheel) selection and tournament selection. We show that these models can explain the empirical results that have been previously presented in the literature. We validate the models on simple problems showing that, (i) when the model assumptions hold, the theory perfectly matches the empirical evidence; (ii) when the model assumptions do not hold, the theory can still provide qualitative explanations of the experimental results.

We analyze generalization in XCSF and introduce three improvements. We begin by showing that the types of generalizations evolved by XCSF can be influenced by the input range. To explain these results we present a theoretical analysis of the convergence of classifier weights in XCSF which highlights a broader issue. In XCSF, because of the mathematical properties of the Widrow-Hoff update, the convergence of classifier weights in a given subspace can be slow when the spread of the eigenvalues of the autocorrelation matrix associated with each classifier is large. As a major consequence, the system's accuracy pressure may act before classifier weights are adequately updated, so that XCSF may evolve piecewise constant approximations, instead of the intended, and more efficient, piecewise linear ones. We propose three different ways to update classifier weights in XCSF so as to increase the generalization capabilities of XCSF: one based on a condition-based normalization of the inputs, one based on linear least squares, and one based on the recursive version of linear least squares. Through a series of experiments we show that while all three approaches significantly improve XCSF, least squares approaches appear to be best performing and most robust. Finally we show how XCSF can be extended to include polynomial approximations.

In this article, we introduce pesudoconstraints , a novel data mining pattern aimed at identifying rare events in databases. At first, we formally define pesudoconstraints using a probabilistic model and provide a statistical test to identify pesudoconstraints in a database. Then, we focus on a specific class of pesudoconstraints, named cycle pesudoconstraints , which often occur in databases. We define cycle pesudoconstraints in the context of the ER model and present an automatic method for detecting cycle pesudoconstraints from a relational database. Finally, we present an experiment to show cycle pesudoconstraints “at work” on real data.

We extend XCSF with neural prediction and replace the linear prediction function used in XCSF with a feedforward multilayer neural network. Each classifier exploits a neural network to approximate the payoff surface associated to the target problem while the genetic algorithm adapts both classifier conditions, classifier actions, and the network structure. We compare XCSF with neural prediction to XCSF with linear prediction. Our results show that XCSF with neural prediction, XCSFNN, can outperform XCSF.

The learning classifier system XCS is an iterative rule-learning system that evolves rule structures based on gradient-based prediction and rule quality estimates. Besides classification and reinforcement learning tasks, XCS was applied as an effective function approximator. Hereby, XCS learns space partitions to enable a maximally accurate and general function approximation. Recently, the function approximation approach was improved by replacing (1) hyperrectangular conditions with hyper-ellipsoids and (2) iterative linear approximation with the recursive least squares method. This paper combines the two approaches assessing the usefulness of each. The evolutionary process is further improved by changing the mutation operator implementing an angular mutation that rotates ellipsoidal structures explicitly. Both enhancements improve XCS performance in various non-linear functions. We also analyze the evolving ellipsoidal structures confirming that XCS stretches and rotates the evolving ellipsoids according to the shape of the underlying function. The results confirm that improvements in both the evolutionary approach and the gradient approach can result in significantly better performance.

This paper investigates reinforcement learning (RL) in XCS. First, it formally shows that XCS implements a method of generalized RL based on linear approximators, in which the usual input mapping function translates the state-action space into a niche relative fitness space. Then, it shows that, although XCS has always been related to standard RL, XCS is actually a method of averaging RL. More precisely, XCS with gradient descent can be actually derived from the typical update of averaging RL. It is noted that the use of averaging RL in XCS introduces an intrinsic preference toward classifiers with a smaller fitness in the niche. It is argued that, because of the accuracy pressure in XCS, this results in an additional preference toward specificity. A very simple experiment is presented to support this hypothesis. The same approach is applied to XCS with computed prediction (XCSF) and similar conclusions are drawn.

This paper introduces XCSF extended with tile coding prediction: each classifier implements a tile coding approximator; the genetic algorithm is used to adapt both classifier conditions (i.e., to partition the problem) and the parameters of each approximator; thus XCSF evolves an ensemble of tile coding approximators instead of the typical monolithic approximator used in reinforcement learning. The paper reports a comparison between (i) XCSF with tile coding prediction and (ii) plain tile coding. The results show that XCSF with tile coding always reaches optimal performance, it usually learns as fast as the best parametrized tile coding, and it can be faster than the typical tile coding setting. In addition, the analysis of the evolved tile coding ensembles shows that XCSF actually adapts local approximators following what is currently considered the best strategy to adapt the tile coding parameters in a given problem.

We study how different prediction update algorithms influence the performance of XCSF. We consider three classical parameter estimation algorithms (NLMS, RLS, and Kalman filter) and four gain adaptation algorithms (K1, K2, IDBD, and IDD). The latter have been shown to perform comparably to the best algorithms (RLS and Kalman), but they have a lower complexity. We apply these algorithms to update classifier prediction in XCSF and compare the performances of the seven versions of XCSF on a set of real functions. Our results show that the best known algorithms still perform best: XCSF with RLS and XCSF with Kalman perform significantly better than the others. In contrast, when added to XCSF, gain adaptation algorithms perform comparably to NLMS, the simplest estimation algorithm, the same used in the original XCSF. Nevertheless, algorithms that perform similarly generalize differently. For instance: XCSF with Kalman filter evolves more compact solutions than XCSF with RLS and gain adaptation algorithms allow better generalization than NLMS.

This papers presents a novel representation of classifier conditions based on convex hulls. A classifier condition is represented by a sets of points in the problem space. These points identify a convex hull that delineates a convex region in the problem space. The condition matches all the problem instances inside such region. XCSF with convex conditions is applied to function approximation problems and its performance is compared to that of XCSF with interval conditions. The comparison shows that XCSF with convex hulls converges faster than XCSF with interval conditions. However, convex conditions usually do not produce more compact solutions.

We present a very first step toward the implementation of the XCS classifier system on field programmable gate arrays. We introduce a version of the XCS classifier system completely based on integer arithmetic instead of the usual floating point one. We test the integer based XCS, that we name XCS/sub i/, on the typical Boolean functions used in literature. The results we present show that, notwithstanding the dramatic reduction of available precision, XCS/sub i/ can perform rather well reaching optimality in all problems though in most cases it converges more slowly than the classical floating point version.

Computed prediction represents a major shift in learning classifier system research. XCS with computed prediction, based on linear approximates, has been applied so far to function approximation, to single step problems involving continuous payoff functions, and to multi step problems. In this paper we take this new approach in a different direction and apply it to the learning of Boolean functions - a domain characterized by highly discontinuous 0/1000 payoff functions. We also extend it to the case of computed prediction based on functions, borrowed from neural networks, that may be more suitable for 0/1000 payoff problems: the perceptron and the sigmoid. The results we present show that XCSF with linear prediction performs optimally in typical Boolean domains and it allows more compact solutions evolving classifiers that are more general compared with XCS. In addition, perceptron based and sigmoid based prediction can converge slightly faster than linear prediction while producing slightly more compact solutions

We apply XCS with computed prediction (XCSF) to tackle multistep reinforcement learning problems involving continuous inputs. In essence we use XCSF as a method of generalized reinforcement learning. We show that in domains involving continuous inputs and delayed rewards XCSF can evolve compact populations of accurate maximally general classifiers which represent the optimal solution to the target problem. We compare the performance of XCSF with that of tabular Q-learning adapted to the continuous domains considered here. The results we present show that XCSF can converge much faster than tabular techniques while producing more compact solutions. Our results also suggest that when exploration is less effective in some areas of the problem space, XCSF can exploit effective generalizations to extend the evolved knowledge beyond the frequently explored areas. In contrast, in the same situations, the convergence speed of tabular Q-learning worsens.

XCSF is the extension of XCS in which classifier prediction is computed as a linear combination of classifier inputs and a weight vector associated to each classifier. XCSF can exploit classifiers' computable prediction to evolve accurate piecewise linear approximations of functions. In this paper, we take XCSF one step further and show how XCSF can be easily extended to allow polynomial approximations. We test the extended version of XCSF on various approximation problems and show that quadratic/cubic approximations can be used to significantly improve XCSF's generalization capabilities.

XCSF extends the typical concept of learning classifier systems through the introduction of computed classifier prediction. Initial results show that XCSF's computed prediction can be used to evolve accurate piecewise linear approximations of simple functions. In this paper, we take XCSF one step further and apply it to typical reinforcement learning problems involving delayed rewards. In essence, we use XCSF as a method of generalized (linear) reinforcement learning to evolve piecewise linear approximations of the payoff surfaces of typical multistep problems. Our results show that XCSF can easily evolve optimal and near optimal solutions for problems introduced in the literature to test linear reinforcement learning methods.

The accuracy-based XCS classifier system has been shown to solve typical data mining problems in a machine-learning competitive way. However, successful applications in multistep problems, modeled by a Markov decision process, were restricted to very small problems. Until now, the temporal difference learning technique in XCS was based on deterministic updates. However, since a prediction is actually generated by a set of rules in XCS and Learning Classifier Systems in general, gradient-based update methods are applicable. The extension of XCS to gradient-based update methods results in a classifier system that is more robust and more parameter independent, solving large and difficult maze problems reliably. Additionally, the extension to gradient methods highlights the relation of XCS to other function approximation methods in reinforcement learning.

Takes initial steps toward a theory of generalization and learning in the learning classifier system XCS. We start from Wilson's generalization hypothesis, which states that XCS has an intrinsic tendency to evolve accurate, maximally general classifiers. We analyze the different evolutionary pressures in XCS and derive a simple equation that supports the hypothesis theoretically. The equation is tested with a number of experiments that confirm the model of generalization pressure that we provide. Then, we focus on the conditions, termed "challenges," that must be satisfied for the existence of effective fitness or accuracy pressure in XCS. We derive two equations that suggest how to set the population size and the covering probability so as to ensure the development of fitness pressure. We argue that when the challenges are met, XCS is able to evolve problem solutions reliably. When the challenges are not met, a problem may provide intrinsic fitness guidance or the reward may be biased in such a way that the problem will still be solved. The equations and the influence of intrinsic fitness guidance and biased reward are tested on large Boolean multiplexer problems. The paper is a contribution to understanding how XCS functions and lays the foundation for research on XCS's learning complexity.

Embedded systems are composed of both dedicated elements (hardware components) and programmable units (software components), which have to interact with each other for accomplishing a specific task. One of the aims of hardware-software codesign is the choice of a partitioning between elements that will be implemented in hardware and elements that will be implemented in software is one of the important step in design. In this paper, we present an application of the learning classifier system XCS to the analysis of data derived from hardware-software codesign applications. The goal of the analysis is the discovering or explicitation of existing interelationships among system components, which can be used to support the human design of embedded systems. The proposed approach is validated on a specific task involving a digital sound spatializer.

In XCS classifier fitness is measured as the relative accuracy of classifier prediction. A classifier is fit if its prediction of the expected payoff is more accurate than that provided by the other classifiers that appear in the same environmental niches. We introduce a modification of Wilson's original definition in which classifier fitness is measured as the absolute (raw) accuracy of classifier prediction. A classifier is fit if the error affecting its prediction is smaller than a given threshold. Then we compare Wilson's relative accuracy and raw accuracy on a number of problems both in terms of learning performance and in terms of generalization capabilities.

We present an extension of the learning classifier system XCS in which classifier conditions are represented by RPN expressions and stack-based genetic programming is used to recombine and mutate classifiers. In contrast with other extensions of XCS involving tree-based genetic programming, the representation we apply here produces conditions that are linear programs, interpreted by a virtual stack machine (similar to a pushdown automaton), and recombined through standard genetic operators. We test the version of XCS extended with stack-based conditions on a set of problems of different complexity.

September 01 2003 Introduction to the Special Issue: Learning Classifier Systems In Special Collection: CogNet Pier Luca Lanzi, Pier Luca Lanzi Search for other works by this author on: This Site Google Scholar Wolfgang Stolzmann, Wolfgang Stolzmann Search for other works by this author on: This Site Google Scholar Stewart W. Wilson Stewart W. Wilson Search for other works by this author on: This Site Google Scholar Author and Article Information Pier Luca Lanzi Wolfgang Stolzmann Stewart W. Wilson Online Issn: 1530-9304 Print Issn: 1063-6560 © 2003 Massachusetts Institute of Technology2003 Evolutionary Computation (2003) 11 (3): iii–iv. https://doi.org/10.1162/106365603322365270 Cite Icon Cite Permissions Share Icon Share Facebook Twitter LinkedIn MailTo Views Icon Views Article contents Figures & tables Video Audio Supplementary Data Peer Review Search Site Citation Pier Luca Lanzi, Wolfgang Stolzmann, Stewart W. Wilson; Introduction to the Special Issue: Learning Classifier Systems. Evol Comput 2003; 11 (3): iii–iv. doi: https://doi.org/10.1162/106365603322365270 Download citation file: Ris (Zotero) Reference Manager EasyBib Bookends Mendeley Papers EndNote RefWorks BibTex toolbar search Search Dropdown Menu toolbar search search input Search input auto suggest filter your search All ContentAll JournalsEvolutionary Computation Search Advanced Search This content is only available as a PDF. © 2003 Massachusetts Institute of Technology2003 Article PDF first page preview Close Modal You do not currently have access to this content.

The recent success of XML as a standard to represent semi-structured data, and the increasing amount of available XML data pose new challenges to the data mining community. In this paper we present the XMINE operator, a tool developed to extract XML association rules for XML documents. The operator, based on XPath and inspired by the syntax of XQuery, allows us to express complex mining tasks, compactly and intuitively. XMINE can be used to specify indifferently (and simultaneously) mining tasks both on the content and on the structure of the data, since the distinction in XML is slight.

Wilson's (1994) bit-register memory scheme was incorporated into the XCS classifier system and investigated in a series of non-Markov environments. Two extensions to the scheme were important in obtaining near-optimal performance in the harder environments. The first was an exploration strategy in which exploration of external actions was probabilistic as in Markov environments, but internal "actions" (register settings) were selected deterministically. The second was use of a register having more bit-positions than were strictly necessary to resolve environmental aliasing. The origins and effects of the two extensions are discussed.

The XCS classifier system represents a major advance in learning classifier systems research because (1) it has a sound and accurate generalization mechanism, and (2) its learning mechanism is based on Q-learning, a recognized learning technique. In taking XCS beyond its very first environments and parameter settings, we show that, in certain difficult sequential (“animat”) environments, performance is poor. We suggest that this occurs because in the chosen environments, some conditions for proper functioning of the generalization mechanism do not hold, resulting in overly general classifiers that cause reduced performance. We hypothesize that one such condition is a lack of sufficiently wide exploration of the environment during learning. We show that if XCS is forced to explore its environment more completely, performance improves dramatically. We propose a technique, based on Sutton's Dyna concept, through which wider exploration would occur naturally. Separately, we demonstrate that the compactness of the representation evolved by XCS is limited by the number of instances of each generalization actually present in the environment. The paper shows that XCS's generalization mechanism is effective, but that the conditions under which it works must be clearly understood.

The paper introduces ADHOC, a tool that integrates statistical methods and machine learning techniques to perform effective feature selection. Feature selection plays a central role in the data analysis process since redundant and irrelevant features often degrade the performance of induction algorithms, both in speed and predictive accuracy. ADHOC combines the advantages of both filter and feedback approaches to feature selection to enhance the understanding of the given data and increase the efficiency of the feature selection process. We report results of extensive experiments on real world data which demonstrate the effectiveness of ADHOC as data reduction technique as well as feature selection method. ADHOC has been employed in the analysis of several corporate databases. In particular, it is currently used to support the difficult task of early estimation of the cost of software projects.