Grammar-Guided Evolutionary Construction of Bayesian networks

This paper proposes the EvoBANE system. EvoBANE automatically generates Bayesian networks for solving special-purpose problems. EvoBANE evolves a population of individuals that codify Bayesian networks until it finds near optimal individual that solves a given classification problem. EvoBANE has the flexibility to modify the constraints that condition the solution search space, self-adapting to the specifications of the problem to be solved. The system extends the GGEAS architecture. GGEAS is a general-purpose grammar-guided evolutionary automatic system, whose modular structure favors its application to the automatic construction of intelligent systems. EvoBANE has been applied to two classification benchmark datasets belonging to different application domains, and statistically compared with a genetic algorithm performing the same tasks. Results show that the proposed system performed better, as it manages different complexity constraints in order to find the simplest solution that best solves every problem.

Evolutionary computation of forests with Degree- and Role-Constrained Minimum Spanning Trees

Finding the degree-constrained minimum spanning tree (DCMST) of a graph is a widely studied NP-hard problem. One of its most important applications is network design. Here we deal with a new variant of the DCMST problem, which consists of finding not only the degree- but also the role-constrained minimum spanning tree (DRCMST), i.e., we add constraints to restrict the role of the nodes in the tree to root, intermediate or leaf node. Furthermore, we do not limit the number of root nodes to one, thereby, generally, building a forest of DRCMSTs. The modeling of network design problems can benefit from the possibility of generating more than one tree and determining the role of the nodes in the network. We propose a novel permutation-based representation to encode these forests. In this new representation, one permutation simultaneously encodes all the trees to be built. We simulate a wide variety of DRCMST problems which we optimize using eight different evolutionary computation algorithms encoding individuals of the population using the proposed representation. The algorithms we use are: estimation of distribution algorithm, generational genetic algorithm, steady-state genetic algorithm, covariance matrix adaptation evolution strategy, differential evolution, elitist evolution strategy, non-elitist evolution strategy and particle swarm optimization. The best results are for the estimation of distribution algorithms and both types of genetic algorithms, although the genetic algorithms are significantly faster.

Frequency of migrants and migratory activity are genetically correlated in a bird population: Evolutionary implications

Most migratory bird populations are composed of individuals that migrate and individuals that remain resident. While the role of ecological factors in maintaining this behavioral dimorphism has received much attention, the importance of genetic constraints on the evolution of avian migration has not yet been considered. Drawing on the recorded migratory activities of 775 blackcaps (Sylvia atricapilla) from a partially migratory population in southern France, we tested two alternative genetic models about the relationship between incidence and amount of migratory activity. The amount of migratory activity could be the continuous variable “underlying” the phenotypic expression of migratory urge, or, alternatively, the expression of both traits could be controlled by two separate genetic systems. The distributions of migratory activities in five different cohorts and the inheritance pattern derived from selective breeding experiments both indicate that incidence and amount of migratory activity are two aspects of one trait. Thus, all birds without measurable activity have activity levels at the low end of a continuous distribution, below the limit of expression or detection. The phenotypic dichotomy “migrant–nonmigrant” is caused by a threshold which may not be fixed but influenced both genetically and environmentally. This finding has profound implications for the evolution of migration: the transition from migratoriness to residency should not only be driven by selection favoring resident birds but also by selection for lower migratory activity. This potential for selection on two aspects, residency and migration distance, of the same trait may enable extremely rapid evolutionary changes to occur in migratory behavior.

Selective constraints on the activation domain of transcription factor Pit-1.

The POU transcription factor Pit-1 activates members of the prolactin/growth hormone gene family in specific endocrine cell types of the pituitary gland. Although Pit-1 is structurally conserved among vertebrate species, evolutionary changes in the pattern of Pit-1 RNA splicing have led to a notable "contraction" of the transactivation domain in the mammalian lineage, relative to Pit-1 in salmonid fish. By site-directed mutagenesis we demonstrate that two splice insertions in salmon Pit-1, called beta (29 aa) and gamma (33 aa), are critical for cooperative activation of the salmon prolactin gene. Paradoxically, Pit-1-dependent activation of the prolactin gene in rat is enhanced in the absence of the homologous beta-insert sequence. This apparent divergence in the mechanism of activation of prolactin genes by Pit-1 is target gene specific, as activation of rat and salmon growth hormone genes by Pit-1 splice variants is entirely conserved. Our data suggest that efficient activation of the prolactin gene in the vertebrate pituitary has significantly constrained the pattern of splicing within the Pit-1 transactivation domain. Rapid evolutionary divergence of prolactin gene function may have demanded changes in Pit-1/protein interactions to accommodate new patterns of transcriptional control by developmental or physiological factors.

The challenge of paleoecological stasis: reassessing sources of evolutionary stability.

The paleontological record of the lower and middle Paleozoic Appalachian foreland basin demonstrates an unprecedented level of ecological and morphological stability on geological time scales. Some 70-80% of fossil morphospecies within assemblages persist in similar relative abundances in coordinated packages lasting as long as 7 million years despite evidence for environmental change and biotic disturbances. These intervals of stability are separated by much shorter periods of ecological and evolutionary change. This pattern appears widespread in the fossil record. Existing concepts of the evolutionary process are unable to explain this uniquely paleontological observation of faunawide coordinated stasis. A principle of evolutionary stability that arises from the ecosystem is explored here. We propose that hierarchical ecosystem theory, when extended to geological time scales, can explain long-term paleoecological stability as the result of ecosystem organization in response to high-frequency disturbance. The accompanying stability of fossil morphologies results from "ecological locking," in which selection is seen as a high-rate response of populations that is hierarchically constrained by lower-rate ecological processes. When disturbance exceeds the capacity of the system, ecological crashes remove these higher-level constraints, and evolution is free to proceed at high rates of directional selection during the organization of a new stable ecological hierarchy.

An evolutionary theory of the family.

An evolutionary framework for viewing the formation, the stability, the organizational structure, and the social dynamics of biological families is developed. This framework is based upon three conceptual pillars: ecological constraints theory, inclusive fitness theory, and reproductive skew theory. I offer a set of 15 predictions pertaining to living within family groups. The logic of each is discussed, and empirical evidence from family-living vertebrates is summarized. I argue that knowledge of four basic parameters, (i) genetic relatedness, (ii) social dominance, (iii) the benefits of group living, and (iv) the probable success of independent reproduction, can explain many aspects of family life in birds and mammals. I suggest that this evolutionary perspective will provide insights into understanding human family systems as well.

Tectono-sedimentary evolution of the ’Numidian Formation’ and Lateral Facies (southern branch of the western Tethys): constraints for central-western Mediterranean geodynamics

The origin of the Numidian Formation (latest Oligocene to middle Miocene), characterized by ultra-mature quartzose arenites with abundant well-rounded frosted quartz grains, remains controversial. This formation, sedimented in the external domain of the Maghrebian Flysch Basin, displays three characteristic stratigraphic members with marked longitudinal (proximal–distal) and transverse (along-chain) variations with palaeogeographical importance. The origin of the Numidian supply is related to the outward tectogenetic propagation when a forebulge evolved in the African foreland, leading to the erosion of African cratonic areas rich in quartzose arenites (Nubian Sandstone-like). The ages of the Numidian Formation checked by Betic, Maghrebian and Southern Apennine data suggest a timing for the accretionary orogenic wedge, earlier in the Betic-Rifian Arc (after middle Burdigalian), later in the Algerian-Tunisian Tell (after late Burdigalian) and afterwards in Sicily and the Southern Apennines (after Langhian). A geodynamic evolutionary model for the central-western Mediterranean is proposed.

An evolutionary approach to the delineation of functional areas based on travel-to-work flows

This paper presents a new approach to the delineation of local labor markets based on evolutionary computation. The aim of the exercise is the division of a given territory into functional regions based on travel-to-work flows. Such regions are defined so that a high degree of inter-regional separation and of intra-regional integration in both cases in terms of commuting flows is guaranteed. Additional requirements include the absence of overlap between delineated regions and the exhaustive coverage of the whole territory. The procedure is based on the maximization of a fitness function that measures aggregate intra-region interaction under constraints of inter-region separation and minimum size. In the experimentation stage, two variations of the fitness function are used, and the process is also applied as a final stage for the optimization of the results from one of the most successful existing methods, which are used by the British authorities for the delineation of travel-to-work areas (TTWAs). The empirical exercise is conducted using real data for a sufficiently large territory that is considered to be representative given the density and variety of travel-to-work patterns that it embraces. The paper includes the quantitative comparison with alternative traditional methods, the assessment of the performance of the set of operators which has been specifically designed to handle the regionalization problem and the evaluation of the convergence process. The robustness of the solutions, something crucial in a research and policy-making context, is also discussed in the paper.

Constraints on muscular performance: trade-offs between power output and fatigue resistance

An important functional and evolutionary constraint on the physical performance of vertebrates is believed to be the trade-off between speed and endurance capacity. However, despite the pervasiveness of physiological arguments, most studies have found no evidence of the trade-off when tested at the whole-animal level. We investigated the existence of this trade-off at the whole-muscle level, the presumed site of this physiological conflict, by examining inter-individual variation in both maximum power output and fatigue resistance for mouse extensor digitorum longus (EDL) muscle using the work-loop technique. We found negative correlations between several measures of in vitro maximum power output and force production with fatigue resistance for individual mouse EDL muscles, indicating functional trade-offs between these performance parameters. We suggest that this trade-off detected at the whole-muscle level has imposed an important constraint on the evolution of vertebrate physical performance.

A reassessment of genetic limits to evolutionary change

An absence of genetic variance in traits under selection is perhaps the oldest explanation for a limit to evolutionary change, but has also been the most easily dismissed. We review a range of theoretical and empirical results covering single traits to more complex multivariate systems, and show that an absence of genetic variance may be more common than is currently appreciated. From a single-trait perspective, we highlight that it is becoming clear that some trait types do not display significant levels of genetic variation, and we raise the possibility that species with restricted ranges may differ qualitatively from more widespread species in levels of genetic variance in ecologically important traits. A common misconception in many life-history studies is that a lack of genetic variance in single traits, and genetic constraints as a consequence of bivariate genetic correlations, are different causes of selection limits. We detail how interpretations of bivariate patterns are unlikely to demonstrate genetic limits to selection in many cases. We advocate a multivariate definition of genetic constraints that emphasizes the presence (or otherwise) of genetic variance in the multivariate direction of selection. For multitrait systems, recent results using longer term studies of organisms, in which more is understood concerning what traits may be under selection, have indicated that selection may exhaust genetic variance, resulting in a limit to the selection response.

Learning to play Pac-Man: An evolutionary, rule-based approach

Pac-Man is a well-known, real-time computer game that provides an interesting platform for research. We describe an initial approach to developing an artificial agent that replaces the human to play a simplified version of Pac-Man. The agent is specified as a simple finite state machine and ruleset. with parameters that control the probability of movement by the agent given the constraints of the maze at some instant of time. In contrast to previous approaches, the agent represents a dynamic strategy for playing Pac-Man, rather than a pre-programmed maze-solving method. The agent adaptively "learns" through the application of population-based incremental learning (PBIL) to adjust the agents' parameters. Experimental results are presented that give insight into some of the complexities of the game, as well as highlighting the limitations and difficulties of the representation of the agent.

Extended Networks of Evolutionary Processors

This paper presents an extended behavior of networks of evolutionary processors. Usually, such nets are able to solve NP-complete problems working with symbolic information. Information can evolve applying rules and can be communicated though the net provided some constraints are verified. These nets are based on biological behavior of membrane systems, but transformed into a suitable computational model. Only symbolic information is communicated. This paper proposes to communicate evolution rules as well as symbolic information. This idea arises from the DNA structure in living cells, such DNA codes information and operations and it can be sent to other cells. Extended nets could be considered as a superset of networks of evolutionary processors since permitting and forbidden constraints can be written in order to deny rules communication.

Megtakarítási típusok - egy adaptív-evolúciós megközelítés = Types of saving - an adaptive-evolutionary approach

A közgazdaságtanban az ágensalapú modellezés egyik alkalmazási területe a makro ökonómia. Ebben a tanulmányban néhány népszerű megtakarítási szabály létét feltételezve adaptív-evolúciós megközelítésben endogén módon próbálunk következtetni e szabályok relatív életképességére. Három különböző típusú ágenst vezetünk be: egy prudens, egy rövidlátó és egy, a permanensjövedelem-elméletnek megfelelően működőt. Rendkívül erős szelekciós nyomás mellett a prudens típus egyértelműen kiszorítja a másik kettőt. A második legéletképesebbnek a rövidlátó típus tűnik, de már közepes szelekciós nyomásnál sem tűnik el egyik típus sem. Szokásos tőkehatékonyság mellett a prudens típus túlzott beruházási tendenciát visz a gazdaságba, és a gazdaság az aranykori megtakarítási rátánál magasabbat ér el. A hitelkorlátok oldása még nagyobb mértékű túlzott beruházáshoz vezethet, a hitelek mennyiségének növekedése mellett a tőketulajdonosok mintegy "kizsákmányoltatják" magukat azokkal, akiknek nincs tőkejövedelmük. A hosszú távú átlagos fogyasztás szempontjából a három típus kiegyensúlyozott aránya adja a legjobb eredményt, ugyanakkor ez jóval nagyobb ingadozással jár, mint amikor csak prudens típusú háztartások léteznek. ____ Agent-based modelling techniques have been employed for some time in macroeconomics. This paper tests some popular saving rules in an adaptive-evolutionary context of looking at their relative survival values. The three types are prudent, short-sighted, and responsive to the permanent-income hypothesis. It is found that where selection pressure is very high, only the prudent type persists. The second most resilient seems to be the short-sighted type, but all three coexist even at medium levels of selection pressure. When the efficiency of capital approaches the level usually assumed in macroeconomics, the prudent type drives the economy towards excessive accumulation of capital, i. e. a long-term savings rate that exceeds the golden rule. If credit constraints are relaxed, this tendency strengthens as credit grows and capital-owners seem to allow themselves to be exploited" by workers. From the angle of average consumption, the best outcome is obtained from a random distribution of types, although this is accompanied by higher volatility.

How institutions shaped the last major evolutionary transition to large-scale human societies.

What drove the transition from small-scale human societies centred on kinship and personal exchange, to large-scale societies comprising cooperation and division of labour among untold numbers of unrelated individuals? We propose that the unique human capacity to negotiate institutional rules that coordinate social actions was a key driver of this transition. By creating institutions, humans have been able to move from the default ‘Hobbesian’ rules of the ‘game of life’, determined by physical/environmental constraints, into self-created rules of social organization where cooperation can be individually advantageous even in large groups of unrelated individuals. Examples include rules of food sharing in hunter–gatherers, rules for the usage of irrigation systems in agriculturalists, property rights and systems for sharing reputation between mediaeval traders. Successful institutions create rules of interaction that are self-enforcing, providing direct benefits both to individuals that follow them, and to individuals that sanction rule breakers. Forming institutions requires shared intentionality, language and other cognitive abilities largely absent in other primates. We explain how cooperative breeding likely selected for these abilities early in the Homo lineage. This allowed anatomically modern humans to create institutions that transformed the self-reliance of our primate ancestors into the division of labour of large-scale human social organization.