Grokking, or delayed generalization, is an intriguing learning phenomenon where a model's test set performance improves sharply but only long after its training performance has converged. This challenges conventional understanding of training dynamics in deep learning. In this paper, we formalize and investigate grokking, highlighting that a distribution shift between training and test data is a key factor in its emergence. We introduce two novel synthetic datasets specifically designed to systematically induce and analyze the phenomenon. By controlling the imbalance in the sampling of data sub-categories, we can reliably reproduce grokking, demonstrating that while small sample sizes are associated with grokking, they are primarily only a mechanism for achieving the necessary distribution shift. We show that when classes possess a relational structure, such as in an equivariant mapping, the model can leverage this information to generalize to entirely unseen subclasses. To explore the limits of this phenomenon, we extend our analysis to the MNIST dataset. Our findings indicate that while distribution shifts can systematically cause grokking in structured synthetic settings, grokking may not emerge as readily in more complex real-world scenarios, suggesting that grokking may depend on the interplay between data distribution and the dataset's intrinsic structure.

Computational learning theory states that many classes of boolean formulas are learnable in polynomial time. This paper addresses the understudied subject of how, in practice, such formulas can be learned by deep neural networks. Specifically, we analyze boolean formulas associated with model-sampling benchmarks, combinatorial optimization problems, and random 3-CNFs with varying degrees of constrainedness. Our experiments indicate that: (i) neural learning generalizes better than pure rule-based systems and pure symbolic approach; (ii) relatively small and shallow neural networks are very good approximators of formulas associated with combinatorial optimization problems; (iii) smaller formulas seem harder to learn, possibly due to the fewer positive (satisfying) examples available; and (iv) interestingly, underconstrained 3-CNF formulas are more challenging to learn than overconstrained ones. Such findings pave the way for a better understanding, construction, and use of neurosymbolic AI methods.

We introduce a new deep learning (DL) approach for approximately solving the Kidney-Exchange Problem (KEP), an NP-hard problem on graphs. Given a pool of kidney donors and patients waiting for donations, we seek to optimally select a set of donations to optimize transplants performed while respecting a set of constraints about donations. Our technique consists of two steps: First, a Graph Neural Network (GNN) trained without supervision; second, a deterministic non-learned search heuristic that uses the output of the GNN to find a valid solution. To validate our work, we implemented and tested an exact solution using integer programming, two greedy search heuristics without the machine learning module, and the GNN alone. We show that the learning-based two-stage approach has the best solution quality, approximating solutions on average 1.1 times more valuable than the deterministic heuristic alone, showing that DL and GNN shed new light in solving this and related problems.

In this paper we propose the use of continuous residual modules for graph kernels in Graph Neural Networks. We show how both discrete and continuous residual layers allow for more robust training, being that continuous residual layers are those which are applied by integrating through an Ordinary Differential Equation (ODE) solver to produce their output. We experimentally show that these residuals achieve better results than the ones with non-residual modules when multiple layers are used, mitigating the low-pass filtering effect of GCN-based models. Finally, we apply and analyse the behaviour of these techniques and give pointers to how this technique can be useful in other domains by allowing more predictable behaviour under dynamic times of computation.

In the context of social media analyses, signed social networks are important representations of relationships between entities. These networks can represent positive or negative relationships between every two entities of a social network. One of the usual analyses over social networks is the communities/clustering search. In this paper, we report analyses on the Signed Modularity Density Maximization problem, which searches for meaningful clusters inside a signed social network. In this analysis, we present a new branch-and-price algorithm to find optimal solutions to this problem. The optimal solutions of two real signed networks and some artificial networks are generated and analyzed. The results suggest that the problem finds meaningful clusterings in signed social networks, and some parameters are suggested to obtain the best results.

Neural-symbolic computing has now become the subject of interest of both academic and industry research laboratories. Graph Neural Networks (GNNs) have been widely used in relational and symbolic domains, with widespread application of GNNs in combinatorial optimization, constraint satisfaction, relational reasoning and other scientific domains. The need for improved explainability, interpretability and trust of AI systems in general demands principled methodologies, as suggested by neural-symbolic computing. In this paper, we review the state-of-the-art on the use of GNNs as a model of neural-symbolic computing. This includes the application of GNNs in several domains as well as their relationship to current developments in neural-symbolic computing.

Graph Neural Networks (GNN) are a promising technique for bridging differential programming and combinatorial domains. GNNs employ trainable modules which can be assembled in different configurations that reflect the relational structure of each problem instance. In this paper, we show that GNNs can learn to solve, with very little supervision, the decision variant of the Traveling Salesperson Problem (TSP), a highly relevant NP-Complete problem. Our model is trained to function as an effective message-passing algorithm in which edges (embedded with their weights) communicate with vertices for a number of iterations after which the model is asked to decide whether a route with cost < C exists. We show that such a network can be trained with sets of dual examples: given the optimal tour cost C∗, we produce one decision instance with target cost x% smaller and one with target cost x% larger than C∗. We were able to obtain 80% accuracy training with −2%,+2% deviations, and the same trained model can generalize for more relaxed deviations with increasing performance. We also show that the model is capable of generalizing for larger problem sizes. Finally, we provide a method for predicting the optimal route cost within 2% deviation from the ground truth. In summary, our work shows that Graph Neural Networks are powerful enough to solve NP-Complete problems which combine symbolic and numeric data.

Recently, the influence of individuals in complex networks received the attention of several fields of science. In the context of influence spreading, the understanding of the role and importance of each individual can be used to control the spread of memes. By considering centrality measures as defining factors of individual importance, this paper investigates the relationship between the importance of an individual and its role in the propagation of influence within and over a network. In order to do so, we used degree measures, betweenness centrality, closeness centrality, eigenvector centrality and clustering coefficient over four different real graphs. The Min-SEIS-Cluster model was employed in order to simulate the spread of memes, which involve cutting connections to minimize an epidemic. The results revealed a high correlation between individual importance and prominence on influence propagation, and the potential to utilize centrality measures to identify which connections should be cut off in specific application scenarios.

Deep learning has consistently defied state-of-the-art techniques in many fields over the last decade. However, we are just beginning to understand the capabilities of neural learning in symbolic domains. Deep learning architectures that employ parameter sharing over graphs can produce models which can be trained on complex properties of relational data. These include highly relevant NP-Complete problems, such as SAT and TSP. In this work, we showcase how Graph Neural Networks (GNN) can be engineered - with a very simple architecture - to solve the fundamental combinatorial problem of graph colouring. Our results show that the model, which achieves high accuracy upon training on random instances, is able to generalise to graph distributions different from those seen at training time. Further, it performs better than the Neurosat, Tabucol and greedy baselines for some distributions. In addition, we show how vertex embeddings can be clustered in multidimensional spaces to yield constructive solutions even though our model is only trained as a binary classifier. In summary, our results contribute to shorten the gap in our understanding of the algorithms learned by GNNs, as well as hoarding empirical evidence for their capability on hard combinatorial problems. Our results thus contribute to the standing challenge of integrating robust learning and symbolic reasoning in Deep Learning systems.

Recently, clustering in graphs and networks have been widely investigated in Computer Science, Artificial Intelligence, Social and Biological sciences. Newman's modularity concept is now widely used in an increasing number of applications. However, developments in Modularity Density Maximization have recently shown improved and better than expected clustering results. In this paper, we investigate and report results on the solution of Li's modularity clustering problem by using Anytime A* search, which offers a novel strategy to tackle this type of problem. In order to do so, we propose two versions of the Anytime A* method, a sequential and a parallel one. In the parallel approach, a pair of connected nodes is used as constraints to divide the search space among the threads. Our results indicate that Anytime A* is a promising search method in this context, leading to small gaps to the best-known solution. Further, the proposed methods add flexibility to the use of parallel strategies that effectively speed up searches.

The family health strategy in Brazil is a program that aims at universal access to actions and services of health promotion, protection, and recovery. In this nationwide program, teams of health professionals are responsible for attending and promoting health actions to a community of a specific area. These teams perform home visits that will support the patients of their respective target areas who demand special health care. To help in the scheduling process of these visits, we propose a new bi-objective problem and two methods for its implementation. The main method is an Ant Colony Optimization-based (ACO) heuristic. The other one is an exact linear programming algorithm designed to allow for experimental comparisons. Our experiments suggest that our ACO surpassed the exact solver in runtime, reaching the optimal solutions for all the solutions known. Amortized complexity analysis showed that the ACO heuristic has sublinear complexity over the number of patients.

Sudoku is a widely popular NP-Complete combinatorial puzzle whose prospects for studying human computation have recently received attention, but the algorithmic hardness of Sudoku solving is yet largely unexplored. In this paper, we study the statistical mechanical properties of random Sudoku grids, showing that puzzles of varying sizes attain a hardness peak associated with a critical behavior in the constrainedness of random instances. In doing so, we provide the first description of a Sudoku freezing transition, showing that the fraction of backbone variables undergoes a phase transition as the density of pre-filled cells is calibrated. We also uncover a variety of critical phenomena in the applicability of Sudoku elimination strategies, providing explanations as to why puzzles become boring outside the typical range of clue densities adopted by Sudoku publishers. We further show that the constrainedness of Sudoku puzzles can be understood in terms of the informational (Shannon) entropy of their solutions, which only increases up to the critical point where variables become frozen. Our findings shed light on the nature of the k-coloring transition when the graph topology is fixed, and are an invitation to the study of phase transition phenomena in problems defined over alldifferent constraints. They also suggest advantages to studying the statistical mechanics of popular NP-Hard puzzles, which can both aid the design of hard instances and help understand the difficulty of human problem solving.

Vertex centrality measures are a multi-purpose analysis tool, commonly used in many application environments to retrieve information and unveil knowledge from the graphs and network structural properties. However, the algorithms of such metrics are expensive in terms of computational resources when running real-time applications or massive real world networks. Thus, approximation techniques have been developed and used to compute the measures in such scenarios. In this paper, we demonstrate and analyze the use of neural network learning algorithms to tackle such task and compare their performance in terms of solution quality and computation time with other techniques from the literature. Our work offers several contributions. We highlight both the pros and cons of approximating centralities though neural learning. By empirical means and statistics, we then show that the regression model generated with a feedforward neural networks trained by the Levenberg-Marquardt algorithm is not only the best option considering computational resources, but also achieves the best solution quality for relevant applications and large-scale networks.

Complex network models have been continuously improved to better match and understand the structural properties and features of real world networks. Such models are useful to generate sample networks with similar characteristics of real world networks that can then be used to improve algorithms and, at the same time, safeguard real data. Several models have been studied and developed over the last few years aiming at matching features like heavy-tailed degree distributions, low diameter and community structure. However, the BTER model is one of a few which was shown capable of generating synthetic networks with all the main characteristics of a real-world network. BTER is capable to match any real degree distribution and clustering coefficient. However, very few experiments have been carried out to support such a claim. In this work, we examine several different parameter setups and then show that the BTER is capable of matching various degree distributions. However, BTER is not capable to correspond to the desired clustering coefficients when restrictions such as connectivity are added to a given network. Further, we also show that the degree distribution plays an important role in the clustering coefficients, independently of how they are parameterized in the model.

There are several known methods for detecting overlapping communities in graphs, each one having their advantages and limitations. The Clique Percolation Method (CPM) is one such method. CPM works by joining highly connected subgraphs (cliques) and using it to find the graph communities. However, the clique enumeration problem is NP-Hard, taking exponential time to be solved. This makes its use impractical in large real-world networks and applications. The aim of this paper is to present an efficient heuristic to enumerate cliques. This enables the Clique Percolation Method to detect overlapping communities in networks containing thousands of nodes. The analyses showed that our novel heuristic is competitive with other known methods regarding solution quality and we also make the CPM more scalable.

Min-SEIS-Cluster is an optimization problem which aims at minimizing the infection spreading in networks. In this problem, nodes can be susceptible to an infection, exposed to an infection, or infectious. One of the main features of this problem is the fact that nodes have different dynamics when interacting with other nodes from the same community. Thus, the problem is characterized by distinct probabilities of infecting nodes from both the same and from different communities. This paper presents a new genetic algorithm that solves the Min-SEIS-Cluster problem. This genetic algorithm surpassed the current heuristic of this problem significantly, reducing the number of infected nodes during the simulation of the epidemics. The results therefore suggest that our new genetic algorithm is the state-of-the-art heuristic to solve this problem.

Recently, the Modularity Maximization clustering problem has been the subject of relevant research in community identification. However, it is known that there are an exponential number of suboptimal partitions. This leads to limitations in the development of optimization methods since there are several partitions identified as almost optimal. In this paper, we aim at identifying how node features can influence the number of suboptimal partitions. We show that nodes with small degree dictate the number of suboptimal partitions. We then demonstrate that degree is the most important feature of the nodes, as it defines the magnitude of this value in obtaining suboptimal partitions. We present experimental results that validate our hypothesis and theoretical results. Finally, we show two examples of heuristics that are improved by using our findings.

Measures of complex network analysis, such as vertex centrality, have the potential to unveil existing network patterns and behaviors. They contribute to the understanding of networks and their components by analyzing their structural properties, which makes them useful in several computer science domains and applications. Unfortunately, there is a large number of distinct centrality measures and little is known about their common characteristics in practice. By means of an empirical analysis, we aim at a clear understanding of the main centrality measures available, unveiling their similarities and differences in a large number of distinct social networks. Our experiments show that the vertex centrality measures known as information, eigenvector, subgraph, walk betweenness and betweenness can distinguish vertices in all kinds of networks with a granularity performance at 95%, while other metrics achieved a considerably lower result. In addition, we demonstrate that several pairs of metrics evaluate the vertices in a very similar way, i.e. their correlation coefficient values are above 0.7. This was unexpected, considering that each metric presents a quite distinct theoretical and algorithmic foundation. Our work thus contributes towards the development of a methodology for principled network analysis and evaluation.

The analysis and study of complex networks are crucial to a number of applications. Vertex centrality measures are an important analysis mechanism to uncover or rank important elements of a given network. However, these metrics have high space and time complexity, which is a severe problem in applications that typically involve large networks. We propose and study the use of neural learning algorithms in such a way that the use of these metrics became feasible in networks of any size. We trained and tested 12 off-the-shelf learning algorithms on several networks. Our results show that the regression output of the machine learning algorithms successfully approximate the real metric values and are a robust alternative in real world applications. We also identified that the model generated by the multilayer layer network trained with the Levenberg-Marquardt algorithm achieved the best performance, both in process time and solution quality, among all the methodologies tested for this task.

Recent studies have suggested that current agent-based models are not sufficiently sophisticated to reproduce results achieved by human collaborative learning and reasoning. Such studies suggest that humans are diverse and dynamic when solving problems socially. However, despite their relevance to problem-solving, these two behavioral features have not yet been fully investigated. In this paper we analyse a recent social problem-solving model and attempt to address its shortcomings. Specifically, we investigate the effects of separating exploitation from exploration in agent behaviors and explore the concept of diversity in such models. We found out that diverse populations outperform homogeneous ones in both efficient and inefficient networks. Finally, we show that agent diversity is more relevant than the strategic behavioral dynamics. This work contributes towards understanding the role of diverse and dynamic behaviors in social problem-solving as well as the advancement of state-of-art social problem-solving models.

In this paper, we analyze the dependency between centrality and individual performance in socially-inspired problem-solving systems. By means of extensive numerical simulations, we investigate how individual performance in four different models correlate with four different classical centrality measures. Our main result shows that there is a high linear correlation between centrality and individual performance when individuals systematically exploit central positions. In this case, central individuals tend to deviate from the expected majority contribution behavior. Although there is ample evidence about the relevance of centrality in social problem-solving, our work contributes to understand that some measures correlate better with individual performance than others due to individual traits, a position that is gaining strength in recent studies.

Vertex centrality measures are important analysis elements in complex networks and systems. These metrics have high space and time complexity, which is a severe problem in applications that typically involve large networks. To apply such high complexity metrics in large networks we trained and tested off-the-shelf machine learning algorithms on several generated networks using five well-known complex network models. Our main hypothesis is that if one uses low complexity metrics as inputs to train the algorithms, one will achieve good approximations of high complexity measures. Our results show that the regression output of the machine learning algorithms applied in our experiments successfully approximate the real metric values and are a robust alternative in real world applications, in particular in complex and social network analysis.

Providing personalized feedback in Intelligent Transport Systems is a powerful tool for instigating a change in driving behaviour and the reduction of CO2emissions. This requires a system that is capable of detecting driver characteristics from real-time vehicle data. In this paper, we apply the architecture and theory of a Neural-Symbolic Cognitive Agent (NSCA) to effectively learn and reason about observed driving behaviour and related driver characteristics. The NSCA architecture combines neural learning and reasoning with symbolic temporal knowledge representation and is capable of encoding background knowledge, learning new hypotheses from observed data, and inferring new beliefs based on these hypotheses. Furthermore, it deals with uncertainty and errors in the data using a Bayesian inference model, and it scales well to hundreds of thousands of data samples as in the application reported in this paper. We have applied the NSCA in an Intelligent Transport System to reduce CO2emissions as part of an European Union project, called EcoDriver. Results reported in this paper show that the NSCA outperforms the state-of-the-art in this application area, and is applicable to very large data.

Social interactions have recently been used as an inspiration for novel agent-based problem-solving models. Particle Swarm Optimization and Memetic Networks are two such algorithms. Although they draw inspiration from different real-world social systems, they both rely on the concept of a social network to regulate the internal information flow in a structured way. In this paper, we systematically investigate how a heterogeneous population composed of individuals from these two models behave as the system seeks the solution to the benchmark problems. We report on extensive numerical simulations, showing that this heterogeneous model is able to converge faster in two highly multimodal scenarios while being otherwise statistically equivalent to the original homogeneous models. Our results provide supportive evidence for the hypothesis that higher diversity in populations of problem-solvers can be beneficial and also adds a new dimension to previous heterogeneous problem-solving models.

Social collaboration has been shown to facilitate problemsolving activity in diverse sets of environments. Nevertheless, if not well designed, social and human computation systems may achieve results only similar to those of a single human subject performing a task. This scenario reflects a need for better understanding of the performance issues of human problem-solving social networks. Firstly, we propose a model for simulating social problem-solving. We then carry out several simulations with artificial agents supported by results of experiments carried out with human subjects, in order to analyse which parameters influence the performance of collaborative problem-solving social networks. We analyse the strategies humans follow when solving a problem, comparing them with alternative ones, and identify the consequences of the employed strategies in the collective performance of the social network. Our results also indicate that copying and guessing are beneficial to the performance of the social networks. We then propose mechanisms that can improve collaborative problem-solving. Finally, we show that our results lead to a methodology for the design of efficient problem-solving systems that can be applied to several kinds of collaborative social systems.

One of the main research problems in Structural Bioinformatics is related to the prediction of three-dimensional structures (3-D) of polypeptides or proteins. The rate at which amino acid sequences are identified is increasing faster than the 3-D protein structure determination by experimental methods. Computational prediction methods have been developed during the last years, but the problem still remains challenging because of the complexity and high dimensionality of a protein conformational search space. In this article we present a hybrid genetic algorithm for the Protein Structure Prediction (PSP) Problem. A genetic algorithm is combined with a structured population, and it is hybridized with a path-relinking procedure that helps the algorithm to scape from local minima. We perform a set of experiments and show that the proposed hybrid genetic algorithm is effective in finding good quality solutions for the PSP Problem.

We propose a novel framework for adapting and evolving software requirements models. The framework uses model checking and machine learning techniques for verifying properties and evolving model descriptions. The paper offers two novel contributions and a preliminary evaluation and application of the ideas presented. First, the framework is capable of coping with errors in the specification process so that performance degrades gracefully. Second, the framework can also be used to re-engineer a model from examples only, when an initial model is not available. We provide a preliminary evaluation of our framework by applying it to a Pump System case study, and integrate our prototype tool with the NuSMV model checker. We show how the tool integrates verification and evolution of abstract models, and also how it is capable of re-engineering partial models given examples from an existing system.

One of the main research problems in Structural Bioinformatics is the analysis and prediction of three-dimensional structures (3-D) of polypeptides or proteins. The 1990's Genome projects resulted in a large increase in the number of protein sequences. However, the number of identified 3-D protein structures has not followed the same trend. The determination of protein structure is experimentally expensive and time consuming. This makes scientists largely dependent on computational methods that can predict correct 3-D protein structures only from extended and full amino acid sequences. Several computational methodologies and algorithms have been proposed as a solution to the Protein Structure Prediction (PSP) problem. We briefly describe the AI techniques we have been used to tackle this problem.

Recently, the use of social and human computing has witnessed increasing interest in the AI community. However, in order to harness the true potential of social computing, human subjects must play an active role in achieving computation in social networks and related media. Our work proposes an initial desiderata for effective social computing, drawing inspiration from artificial intelligence. Extensive experimentation reveals that several open issues and research questions have to be answered before the true potential of social and human computing is achieved. We, however, take a somewhat novel approach, by implementing a social networks environment where human subjects cooperate towards computational problem solving. In our social environment, human and artificial agents cooperate in their computation tasks, which may lead to a single problem-solving social network that potentially allows seamless cooperation among human and machine agents.

In real-world applications, the effective integration of learning and reasoning in a cognitive agent model is a difficult task. However, such integration may lead to a better understanding, use and construction of more realistic models. Unfortunately, existing models are either oversimplified or require much processing time, which is unsuitable for online learning and reasoning. Currently, controlled environments like training simulators do not effectively integrate learning and reasoning. In particular, higher-order concepts and cognitive abilities have many unknown temporal relations with the data, making it impossible to represent such relationships by hand. We introduce a novel cognitive agent model and architecture for online learning and reasoning that seeks to effectively represent, learn and reason in complex training environments. The agent architecture of the model combines neural learning with symbolic knowledge representation. It is capable of learning new hypotheses from observed data, and infer new beliefs based on these hypotheses. Furthermore, it deals with uncertainty and errors in the data using a Bayesian inference model. The validation of the model on real-time simulations and the results presented here indicate the promise of the approach when performing online learning and reasoning in real-world scenarios, with possible applications in a range of areas.

The effective integration of knowledge representation, reasoning, and learning in a robust computational model is one of the key challenges of computer science and artificial intelligence. In particular, temporal knowledge and models have been fundamental in describing the behavior of computational systems. However, knowledge acquisition of correct descriptions of a system's desired behavior is a complex task. In this paper, we present a novel neural-computation model capable of representing and learning temporal knowledge in recurrent networks. The model works in an integrated fashion. It enables the effective representation of temporal knowledge, the adaptation of temporal models given a set of desirable system properties, and effective learning from examples, which in turn can lead to temporal knowledge extraction from the corresponding trained networks. The model is sound from a theoretical standpoint, but it has also been tested on a case study in the area of model verification and adaptation. The results contained in this paper indicate that model verification and learning can be integrated within the neural computation paradigm, contributing to the development of predictive temporal knowledge-based systems and offering interpretable results that allow system researchers and engineers to improve their models and specifications. The model has been implemented and is available as part of a neural-symbolic computational toolkit.

We propose a framework where humans and computers can collaborate seamlessly to solve problems. We do so by developing and applying a network model, namely Memenets, where human knowledge and reasoning are combined with machine computation to achieve problem-solving. The development of a Memenet is done in three steps: first, we simulate a machine-only network, as previous results have shown that memenets are efficient problem-solvers. Then, we perform an experiment with human agents organized in a online network. This allows us to investigate human behavior while solving problems in a social network and to postulate principles of agent communication in Memenets. These postulates describe an initial theory of how human-computer interaction functions inside social networks. In the third stage, postulates of step two allow one to combine human and machine computation to propose an integrated Memenet-based problem-solving computing model.

In software development, formal verification plays an important role in improving the quality and safety of products and processes. Model checking is a successful approach to verification, used both in academic research and industrial applications. One important improvement regarding utilization of model checking is the development of automated processes to evolve models according to information obtained from verification. In this paper, we propose a new framework that make use of artificial intelligence and machine learning to generate and evolve models from partial descriptions and examples created by the model checking process. This was implemented as a tool that is integrated with a model checker. Our work extends model checking to be applicable when initial description of a system is not available, through observation of actual behaviour of this system. The framework is capable of integrated verification and evolution of abstract models, but also of reengineering partial models of a system.

Firewalls are one of the most widely used mechanisms against security threats in distributed andnetwork systems.However, principled methodologies for firewall extraction policies have been scarcely investigated so far.We introduce a new model for translating low level firewall rules into higher abstraction level rules which allow for the inference of firewall policies. In order to do so, we introduced a new methodology based on rules' decorrelation algorithms that compute hierarchical firewall policies from lower level firewall rules. Further, we define a new effective model for the explicit extraction of blacklisted and whitelisted hosts and networks.

The use of resources in multiagent learning systems is a relevant research problem, with a number of applications in resource allocation, communication and synchronization. Multiagent distributed resource allocation requires that agents act on limited, localized information with minimum communication overhead in order to optimize the distribution of available resources. When requirements and constraints are dynamic, learning agents may be needed to allow for adaptation. One way of accomplishing learning is to observe past outcomes, using such information to improve future decisions. When limits in agents' memory or observation capabilities are assumed, one must decide on how large should the observation window be. We investigate how this decision influences both agents' and system's performance in the context of a special class of distributed resource allocation problems, namely dispersion games. We show by using several numerical experiments over a specific dispersion game (the Minority Game) that in such scenario an agent's performance is non-monotonically correlated with her memory size when all other agents are kept unchanged. We then provide an information-theoretic explanation for the observed behaviors, showing that a downward causation effect takes place.

In this paper we propose an embedded software design flow, which starts from an UML model and provides automatic mapping to other models like Simulink or finite-state machines (FSM). An automatic synthesis of an executable and synthesizable Simulink model is also proposed, enabling the use of UML as front-end for a multi-model design strategy that includes a Simulink-based MPSoC target design flow. In addition, the proposed synthesis tool automatically handles processor allocation, mapping of threads to processors, and insertion of required Simulink temporal barriers, ports, and dataflow connections. Following this approach, the UML model is mapped to the more appropriated model and specialized code generators are used. Therefore, this approach allows designers to employ UML to model the whole system and reuse this model to generate code using different strategies and targeting different platforms.

This paper illustrates the use of a novel class of population-based optimization algorithms namely \textsl{Memetic Networks}. These algorithms make use of an underlying network to structure information flow between multiple individuals representing points in the search space. Memetic Networks have as a fundamental characteristic the possibility to aggregate several solutions in order to compose new ones. Network properties allow to control how information is spread among the population. We apply these algorithms to several real-valued benchmark optimization problems and the TSP and report results from extensive simulations. We show how some network properties can influence the algorithm's performance and illustrate the effectiveness of this new class of algorithms.

Memetic networks are a new class of population-based optimization algorithms that makes use of an underlying network to structure information flow between individuals representing points in the search space. Its main characteristic is the possibility of aggregating several solutions in order to compose new ones and the use of an explicit network to aid search. Algorithms from this class can be used to relate network properties to search performance in optimization tasks. We propose and report on algorithms applied to several benchmark optimization problems. We further show how some network properties - in particular, the existence of hubs - can influence the algorithm's performance.

The integration of logic-based inference systems and connectionist learning architectures may lead to the construction of semantically sound cognitive models in artificial intelligence. The use of hybrid systems has shown promising results as regards the computation and learning of classical reasoning within neural networks. However, there still remains a number of open research issues on the integration of non-classical logics and neural networks. We present a new model for integrating symbolic reasoning about past temporal information and neural learning systems. We propose algorithms that translate background knowledge into a neural network and analyse the effectiveness of learning algorithms when subject to symbolic temporal knowledge. This opens several interesting research paths with possible applications to agents' decision making, cognitive modelling and knowledge-based systems.

The importance of the efforts to bridge the gap between the connectionist and symbolic paradigms of artificial intelligence has been widely recognized. The merging of theory (background knowledge) and data learning (learning from examples) into neural-symbolic systems has indicated that such a learning system is more effective than purely symbolic or purely connectionist systems. Until recently, however, neural-symbolic systems were not able to fully represent, reason, and learn expressive languages other than classical propositional and fragments of first-order logic. In this article, we show that nonclassical logics, in particular propositional temporal logic and combinations of temporal and epistemic (modal) reasoning, can be effectively computed by artificial neural networks. We present the language of a connectionist temporal logic of knowledge (CTLK). We then present a temporal algorithm that translates CTLK theories into ensembles of neural networks and prove that the translation is correct. Finally, we apply CTLK to the muddy children puzzle, which has been widely used as a test-bed for distributed knowledge representation. We provide a complete solution to the puzzle with the use of simple neural networks, capable of reasoning about knowledge evolution in time and of knowledge acquisition through learning.

We present a new connectionist model for constructive, intuitionistic modal reasoning. We use ensembles of neural networks to represent in- tuitionistic modal theories, and show that for each intuitionistic modal program there exists a corresponding neural network ensemble that com- putes the program. This provides a massively parallel model for intu- itionistic modal reasoning, and sets the scene for integrated reasoning, knowledge representation, and learning of intuitionistic theories in neural networks, since the networks in the ensemble can be trained by examples using standard neural learning algorithms.

While neural networks have been successfully used in a number of machine learning applications, logical languages have been the standard for the representation of argumentative reasoning. In this paper, we establish a relationship between neural networks and argumentation networks, combining reasoning and learning in the same argumentation framework. We do so by presenting a new neural argumentation algorithm, responsible for translating argumentation networks into standard neural networks. We then show a correspondence between the two networks. The algorithm works not only for acyclic argumentation networks, but also for circular networks, and it enables the accrual of arguments through learning as well as the parallel computation of arguments

We report experiments in a boundedly rational evolutionary game, namely the minority game, where agents apply a very simple learning algorithm to discard bad strategies and create new ones. The results show that even such simplified learning model presents qualitative differences from the behavior of the traditional game, where strategies are fixed and cannot be modified or discarded. We show that this result is qualitatively similar to other, more complex, learning approaches. Also, we study how the learning parameters of our model affect the dynamics of the game and we provide experimental evidence of a high dependence between the behavior of the system and the way fitness is attributed as new strategies enter the game.

We show that temporal logic and combinations of temporal logics and modal logics of knowledge can be effectively represented in ar(cid:173) tificial neural networks. We present a Translation Algorithm from temporal rules to neural networks, and show that the networks compute a fixed-point semantics of the rules. We also apply the translation to the muddy children puzzle, which has been used as a testbed for distributed multi-agent systems. We provide a complete solution to the puzzle with the use of simple neural networks, capa(cid:173) ble of reasoning about time and of knowledge acquisition through inductive learning.

1Imperial College, London Review of Elementary Logics: a Procedural Perspective Dov M. Gabbay Prentice Hall 1998 384 £ 29 0‐13‐726365‐1