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.

New constraints on the chemical evolution of the solar neighbourhood and Galactic disc(s) Improved astrophysical parameters for the Geneva-Copenhagen Survey

We present a re-analysis of the Geneva-Copenhagen survey, which benefits from the infrared flux method to improve the accuracy of the derived stellar effective temperatures and uses the latter to build a consistent and improved metallicity scale. Metallicities are calibrated on high-resolution spectroscopy and checked against four open clusters and a moving group, showing excellent consistency. The new temperature and metallicity scales provide a better match to theoretical isochrones, which are used for a Bayesian analysis of stellar ages. With respect to previous analyses, our stars are on average 100 K hotter and 0.1 dex more metal rich, which shift the peak of the metallicity distribution function around the solar value. From Stromgren photometry we are able to derive for the first time a proxy for [alpha/Fe] abundances, which enables us to perform a tentative dissection of the chemical thin and thick disc. We find evidence for the latter being composed of an old, mildly but systematically alpha-enhanced population that extends to super solar metallicities, in agreement with spectroscopic studies. Our revision offers the largest existing kinematically unbiased sample of the solar neighbourhood that contains full information on kinematics, metallicities, and ages and thus provides better constraints on the physical processes relevant in the build-up of the Milky Way disc, enabling a better understanding of the Sun in a Galactic context.

Dynamics and constraints of the massive graviton dark matter flat cosmologies

We discuss the dynamics of the Universe within the framework of the massive graviton cold dark matter scenario (MGCDM) in which gravitons are geometrically treated as massive particles. In this modified gravity theory, the main effect of the gravitons is to alter the density evolution of the cold dark matter component in such a way that the Universe evolves to an accelerating expanding regime, as presently observed. Tight constraints on the main cosmological parameters of the MGCDM model are derived by performing a joint likelihood analysis involving the recent supernovae type Ia data, the cosmic microwave background shift parameter, and the baryonic acoustic oscillations as traced by the Sloan Digital Sky Survey red luminous galaxies. The linear evolution of small density fluctuations is also analyzed in detail. It is found that the growth factor of the MGCDM model is slightly different (similar to 1-4%) from the one provided by the conventional flat Lambda CDM cosmology. The growth rate of clustering predicted by MGCDM and Lambda CDM models are confronted to the observations and the corresponding best fit values of the growth index (gamma) are also determined. By using the expectations of realistic future x-ray and Sunyaev-Zeldovich cluster surveys we derive the dark matter halo mass function and the corresponding redshift distribution of cluster-size halos for the MGCDM model. Finally, we also show that the Hubble flow differences between the MGCDM and the Lambda CDM models provide a halo redshift distribution departing significantly from the those predicted by other dark energy models. These results suggest that the MGCDM model can observationally be distinguished from Lambda CDM and also from a large number of dark energy models recently proposed in the literature.