'A Bayesian Optimisation Algorithm for the Nurse Scheduling Problem'

Abstract- A Bayesian optimization algorithm for the nurse scheduling problem is presented, which involves choosing a suitable scheduling rule from a set for each nurse's assignment. Unlike our previous work that used GAs to implement implicit learning, the learning in the proposed algorithm is explicit, i.e. eventually, we will be able to identify and mix building blocks directly. The Bayesian optimization algorithm is applied to implement such explicit learning by building a Bayesian network of the joint distribution of solutions. The conditional probability of each variable in the network is computed according to an initial set of promising solutions. Subsequently, each new instance for each variable is generated by using the corresponding conditional probabilities, until all variables have been generated, i.e. in our case, a new rule string has been obtained. Another set of rule strings will be generated in this way, some of which will replace previous strings based on fitness selection. If stopping conditions are not met, the conditional probabilities for all nodes in the Bayesian network are updated again using the current set of promising rule strings. Computational results from 52 real data instances demonstrate the success of this approach. It is also suggested that the learning mechanism in the proposed approach might be suitable for other scheduling problems.

A Pyramidal Evolutionary Algorithm with Different Inter-Agent Partnering Strategies for Scheduling Problems

This paper combines the idea of a hierarchical distributed genetic algorithm with different inter-agent partnering strategies. Cascading clusters of sub-populations are built from bottom up, with higher-level sub-populations optimising larger parts of the problem. Hence higher-level sub-populations search a larger search space with a lower resolution whilst lower-level sub-populations search a smaller search space with a higher resolution. The effects of different partner selection schemes amongst the agents on solution quality are examined for two multiple-choice optimisation problems. It is shown that partnering strategies that exploit problem-specific knowledge are superior and can counter inappropriate (sub-) fitness measurements.

'A Bayesian Optimisation Algorithm for the Nurse Scheduling Problem'

Abstract- A Bayesian optimization algorithm for the nurse scheduling problem is presented, which involves choosing a suitable scheduling rule from a set for each nurse's assignment. Unlike our previous work that used GAs to implement implicit learning, the learning in the proposed algorithm is explicit, i.e. eventually, we will be able to identify and mix building blocks directly. The Bayesian optimization algorithm is applied to implement such explicit learning by building a Bayesian network of the joint distribution of solutions. The conditional probability of each variable in the network is computed according to an initial set of promising solutions. Subsequently, each new instance for each variable is generated by using the corresponding conditional probabilities, until all variables have been generated, i.e. in our case, a new rule string has been obtained. Another set of rule strings will be generated in this way, some of which will replace previous strings based on fitness selection. If stopping conditions are not met, the conditional probabilities for all nodes in the Bayesian network are updated again using the current set of promising rule strings. Computational results from 52 real data instances demonstrate the success of this approach. It is also suggested that the learning mechanism in the proposed approach might be suitable for other scheduling problems.

Partnering Strategies for Fitness Evaluation in a Pyramidal Evolutionary Algorithm

This paper combines the idea of a hierarchical distributed genetic algorithm with different inter-agent partnering strategies. Cascading clusters of sub-populations are built from bottom up, with higher-level sub-populations optimising larger parts of the problem. Hence higher-level sub-populations search a larger search space with a lower resolution whilst lower-level sub-populations search a smaller search space with a higher resolution. The effects of different partner selection schemes for (sub-)fitness evaluation purposes are examined for two multiple-choice optimisation problems. It is shown that random partnering strategies perform best by providing better sampling and more diversity.

A Pyramidal Evolutionary Algorithm with Different Inter-Agent Partnering Strategies for Scheduling Problems

This paper combines the idea of a hierarchical distributed genetic algorithm with different inter-agent partnering strategies. Cascading clusters of sub-populations are built from bottom up, with higher-level sub-populations optimising larger parts of the problem. Hence higher-level sub-populations search a larger search space with a lower resolution whilst lower-level sub-populations search a smaller search space with a higher resolution. The effects of different partner selection schemes amongst the agents on solution quality are examined for two multiple-choice optimisation problems. It is shown that partnering strategies that exploit problem-specific knowledge are superior and can counter inappropriate (sub-) fitness measurements.

Polyphenol Extraction Optimisation From Ceylon Gooseberry (dovyalis Hebecarpa) Pulp.

Originally from Asia, Dovyalis hebecarpa is a dark purple/red exotic berry now also produced in Brazil. However, no reports were found in the literature about phenolic extraction or characterisation of this berry. In this study we evaluate the extraction optimisation of anthocyanins and total phenolics in D. hebecarpa berries aiming at the development of a simple and mild analytical technique. Multivariate analysis was used to optimise the extraction variables (ethanol:water:acetone solvent proportions, times, and acid concentrations) at different levels. Acetone/water (20/80 v/v) gave the highest anthocyanin extraction yield, but pure water and different proportions of acetone/water or acetone/ethanol/water (with >50% of water) were also effective. Neither acid concentration nor time had a significant effect on extraction efficiency allowing to fix the recommended parameters at the lowest values tested (0.35% formic acid v/v, and 17.6 min). Under optimised conditions, extraction efficiencies were increased by 31.5% and 11% for anthocyanin and total phenolics, respectively as compared to traditional methods that use more solvent and time. Thus, the optimised methodology increased yields being less hazardous and time consuming than traditional methods. Finally, freeze-dried D. hebecarpa showed high content of target phytochemicals (319 mg/100g and 1,421 mg/100g of total anthocyanin and total phenolic content, respectively).

Solar twins in M 67: evolutionary status and lithium abundance

Aims. We determine the age and mass of the three best solar twin candidates in open cluster M 67 through lithium evolutionary models. Methods. We computed a grid of evolutionary models with non-standard mixing at metallicity [Fe/H] = 0.01 with the Toulouse-Geneva evolution code for a range of stellar masses. We estimated the mass and age of 10 solar analogs belonging to the open cluster M 67. We made a detailed study of the three solar twins of the sample, YPB637, YPB1194, and YPB1787. Results. We obtained a very accurate estimation of the mass of our solar analogs in M 67 by interpolating in the grid of evolutionary models. The three solar twins allowed us to estimate the age of the open cluster, which is 3.87(-0.66)(+0.55) Gyr, which is better constrained than former estimates. Conclusions. Our results show that the 3 solar twin candidates have one solar mass within the errors and that M 67 has a solar age within the errors, validating its use as a solar proxy. M 67 is an important cluster when searching for solar twins.

Star formation in the intragroup medium and other diagnostics of the evolutionary stages of compact groups of galaxies

Context. Compact groups of galaxies are entities that have high densities of galaxies and serve as laboratories to study galaxy interactions, intergalactic star formation and galaxy evolution. Aims. The main goal of this study is to search for young objects in the intragroup medium of seven compact groups of galaxies: HCG 2, 7, 22, 23, 92, 100 and NGC 92 as well as to evaluate the stage of interaction of each group. Methods. We used Fabry-Perot velocity fields and rotation curves together with GALEX NUV and FUV images and optical R-band and HI maps. Results. (i) HCG 7 and HCG 23 are in early stages of interaction; (ii) HCG 2 and HCG 22 are mildly interacting; and (iii) HCG 92, HCG 100 and NGC 92 are in late stages of evolution. We find that all three evolved groups contain populations of young blue objects in the intragroup medium, consistent with ages < 100 Myr, of which several are younger than < 10 Myr. We also report the discovery of a tidal dwarf galaxy candidate in the tail of NGC 92. These three groups, besides containing galaxies that have peculiar velocity fields, also show extended HI tails. Conclusions. Our results indicate that the advanced stage of evolution of a group, together with the presence of intragroup HI clouds, may lead to star formation in the intragroup medium. A table containing all intergalactic HII regions and tidal dwarf galaxies confirmed to date is appended.

The young, tight, and low-mass binary TWA22AB: a new calibrator for evolutionary models? Orbit, spectral types, and temperature

Context. Tight binaries discovered in young, nearby associations are ideal targets for providing dynamical mass measurements to test the physics of evolutionary models at young ages and very low masses. Aims. We report the binarity of TWA22 for the first time. We aim at monitoring the orbit of this young and tight system to determine its total dynamical mass using an accurate distance determination. We also intend to characterize the physical properties (luminosity, effective temperature, and surface gravity) of each component based on near-infrared photometric and spectroscopic observations. Methods. We used the adaptive-optics assisted imager NACO to resolve the components, to monitor the complete orbit and to obtain the relative near-infrared photometry of TWA22 AB. The adaptive-optics assisted integral field spectrometer SINFONI was also used to obtain medium-resolution (R(lambda) = 1500-2000) spectra in JHK bands. Comparison with empirical and synthetic librairies were necessary for deriving the spectral type, the effective temperature, and the surface gravity for each component of the system. Results. Based on an accurate trigonometric distance (17.5 +/- 0.2 pc) determination, we infer a total dynamical mass of 220 +/- 21 M(Jup) for the system. From the complete set of spectra, we find an effective temperature T(eff) = 2900(-200)(+200) K for TWA22A and T(eff) = 2900(-100)(+200) for TWA22 B and surface gravities between 4.0 and 5.5 dex. From our photometry and an M6 +/- 1 spectral type for both components, we find luminosities of log(L/L(circle dot)) = -2.11 +/- 0.13 dex and log(L/L(circle dot)) = -2.30 +/- 0.16 dex for TWA22 A and B, respectively. By comparing these parameters with evolutionary models, we question the age and the multiplicity of this system. We also discuss a possible underestimation of the mass predicted by evolutionary models for young stars close to the substellar boundary.

Beryllium abundances along the evolutionary sequence of the open cluster IC 4651-A new test for hydrodynamical stellar models

Context. Previous analyses of lithium abundances in main sequence and red giant stars have revealed the action of mixing mechanisms other than convection in stellar interiors. Beryllium abundances in stars with Li abundance determinations can offer valuable complementary information on the nature of these mechanisms. Aims. Our aim is to derive Be abundances along the whole evolutionary sequence of an open cluster. We focus on the well-studied open cluster IC 4651. These Be abundances are used with previously determined Li abundances, in the same sample stars, to investigate the mixing mechanisms in a range of stellar masses and evolutionary stages. Methods. Atmospheric parameters were adopted from a previous abundance analysis by the same authors. New Be abundances have been determined from high-resolution, high signal-to-noise UVES spectra using spectrum synthesis and model atmospheres. The careful synthetic modeling of the Be lines region is used to calculate reliable abundances in rapidly rotating stars. The observed behavior of Be and Li is compared to theoretical predictions from stellar models including rotation-induced mixing, internal gravity waves, atomic diffusion, and thermohaline mixing. Results. Beryllium is detected in all the main sequence and turn-off sample stars, both slow- and fast-rotating stars, including the Li-dip stars, but is not detected in the red giants. Confirming previous results, we find that the Li dip is also a Be dip, although the depletion of Be is more modest than for Li in the corresponding effective temperature range. For post-main-sequence stars, the Be dilution starts earlier within the Hertzsprung gap than expected from classical predictions, as does the Li dilution. A clear dispersion in the Be abundances is also observed. Theoretical stellar models including the hydrodynamical transport processes mentioned above are able to reproduce all the observed features well. These results show a good theoretical understanding of the Li and Be behavior along the color-magnitude diagram of this intermediate-age cluster for stars more massive than 1.2 M(circle dot).

Inferences of evolutionary and ecological events that influenced the population structure of Plebeia remota, a stingless bee from Brazil

The present study characterised the population genetic structure of Plebeia remota through mitochondrial DNA (mtDNA) analysis and evaluated evolutionary and ecological processes that may have contributed to the species current genetic scenario. Seventy feral nests were sampled representing four geographic regions (Cunha, Curitiba, Prudentopolis, and Blumenau). Fifteen composite mtDNA haplotypes were determined and a high genetic structure was detected among all populations. The current population structure may be a result of queen philopatry and vegetation shifts caused by palaeoclimatic changes and uplift of Brazilian coastal ranges. Finally, this study strongly suggests a revision of the taxonomic status of P. remota from the Prudentopolis region.

Genetic Variation among Major Human Geographic Groups Supports a Peculiar Evolutionary Trend in PAX9

A total of 172 persons from nine South Amerindian, three African and one Eskimo populations were studied in relation to the Paired box gene 9 (PAX9) exon 3 (138 base pairs) as well as its 5' and 3' flanking intronic segments (232 bp and 220 bp, respectively) and integrated with the information available for the same genetic region from individuals of different geographical origins. Nine mutations were scored in exon 3 and six in its flanking regions; four of them are new South American tribe-specific singletons. Exon3 nucleotide diversity is several orders of magnitude higher than its intronic regions. Additionally, a set of variants in the PAX9 and 101 other genes related with dentition can define at least some dental morphological differences between Sub-Saharan Africans and non-Africans, probably associated with adaptations after the modern human exodus from Africa. Exon 3 of PAX9 could be a good molecular example of how evolvability works.

Testing Evolutionary and Dispersion Scenarios for the Settlement of the New World

Background: Discussion surrounding the settlement of the New World has recently gained momentum with advances in molecular biology, archaeology and bioanthropology. Recent evidence from these diverse fields is found to support different colonization scenarios. The currently available genetic evidence suggests a ""single migration'' model, in which both early and later Native American groups derive from one expansion event into the continent. In contrast, the pronounced anatomical differences between early and late Native American populations have led others to propose more complex scenarios, involving separate colonization events of the New World and a distinct origin for these groups. Methodology/Principal Findings: Using large samples of Early American crania, we: 1) calculated the rate of morphological differentiation between Early and Late American samples under three different time divergence assumptions, and compared our findings to the predicted morphological differentiation under neutral conditions in each case; and 2) further tested three dispersal scenarios for the colonization of the New World by comparing the morphological distances among early and late Amerindians, East Asians, Australo-Melanesians and early modern humans from Asia to geographical distances associated with each dispersion model. Results indicate that the assumption of a last shared common ancestor outside the continent better explains the observed morphological differences between early and late American groups. This result is corroborated by our finding that a model comprising two Asian waves of migration coming through Bering into the Americas fits the cranial anatomical evidence best, especially when the effects of diversifying selection to climate are taken into account. Conclusions: We conclude that the morphological diversity documented through time in the New World is best accounted for by a model postulating two waves of human expansion into the continent originating in East Asia and entering through Beringia.

Evolutionary dynamics on rugged fitness landscapes: Exact dynamics and information theoretical aspects

The parallel mutation-selection evolutionary dynamics, in which mutation and replication are independent events, is solved exactly in the case that the Malthusian fitnesses associated to the genomes are described by the random energy model (REM) and by a ferromagnetic version of the REM. The solution method uses the mapping of the evolutionary dynamics into a quantum Ising chain in a transverse field and the Suzuki-Trotter formalism to calculate the transition probabilities between configurations at different times. We find that in the case of the REM landscape the dynamics can exhibit three distinct regimes: pure diffusion or stasis for short times, depending on the fitness of the initial configuration, and a spin-glass regime for large times. The dynamic transition between these dynamical regimes is marked by discontinuities in the mean-fitness as well as in the overlap with the initial reference sequence. The relaxation to equilibrium is described by an inverse time decay. In the ferromagnetic REM, we find in addition to these three regimes, a ferromagnetic regime where the overlap and the mean-fitness are frozen. In this case, the system relaxes to equilibrium in a finite time. The relevance of our results to information processing aspects of evolution is discussed.

Optimisation of environmental gas cleaning routes for solid wastes cogeneration systems - Part I - Analysis of waste incineration steam cycle

Research of advanced technologies for energy generation contemplates a series of alternatives that are introduced both in the investigation of new energy sources and in the improvement and/or development of new components and systems. Even though significant reductions are observed in the amount of emissions, the proposed alternatives require the use of exhaust gases cleaning systems. The results of environmental analyses based on two configurations proposed for urban waste incineration are presented in this paper; the annexation of integer (Boolean) variables to the environomic model makes it possible to define the best gas cleaning routes based on exergetic cost minimisation criteria. In this first part, the results for steam cogeneration system analysis associated with the incineration of municipal solid wastes (MSW) is presented. (c) 2007 Elsevier Ltd. All rights reserved.