Genetic algorithm for sequencing in midex model non-permutation flowshops using constrained buffers

Este trabajo presenta un Algoritmo Genético (GA) del problema de secuenciar unidades en una línea de producción. Se tiene en cuenta la posibilidad de cambiar la secuencia de piezas mediante estaciones con acceso a un almacén intermedio o centralizado. El acceso al almacén además está restringido, debido al tamaño de las piezas.AbstractThis paper presents a Genetic Algorithm (GA) for the problem of sequencing in a mixed model non-permutation flowshop. Resequencingis permitted where stations have access to intermittent or centralized resequencing buffers. The access to a buffer is restricted by the number of available buffer places and the physical size of the products.

Robust power allocation algorithms for MIMO OFDM systems with imperfect CSI

This paper presents a Bayesian approach to the design of transmit prefiltering matrices in closed-loop schemes robust to channel estimation errors. The algorithms are derived for a multiple-input multiple-output (MIMO) orthogonal frequency division multiplexing (OFDM) system. Two different optimizationcriteria are analyzed: the minimization of the mean square error and the minimization of the bit error rate. In both cases, the transmitter design is based on the singular value decomposition (SVD) of the conditional mean of the channel response, given the channel estimate. The performance of the proposed algorithms is analyzed,and their relationship with existing algorithms is indicated. As withother previously proposed solutions, the minimum bit error rate algorithmconverges to the open-loop transmission scheme for very poor CSI estimates.

Practical algorithms for a family of waterfilling solutions

Many engineering problems that can be formulatedas constrained optimization problems result in solutionsgiven by a waterfilling structure; the classical example is thecapacity-achieving solution for a frequency-selective channel.For simple waterfilling solutions with a single waterlevel and asingle constraint (typically, a power constraint), some algorithmshave been proposed in the literature to compute the solutionsnumerically. However, some other optimization problems result insignificantly more complicated waterfilling solutions that includemultiple waterlevels and multiple constraints. For such cases, itmay still be possible to obtain practical algorithms to evaluate thesolutions numerically but only after a painstaking inspection ofthe specific waterfilling structure. In addition, a unified view ofthe different types of waterfilling solutions and the correspondingpractical algorithms is missing.The purpose of this paper is twofold. On the one hand, itoverviews the waterfilling results existing in the literature from aunified viewpoint. On the other hand, it bridges the gap betweena wide family of waterfilling solutions and their efficient implementationin practice; to be more precise, it provides a practicalalgorithm to evaluate numerically a general waterfilling solution,which includes the currently existing waterfilling solutions andothers that may possibly appear in future problems.

Population genomics of eusocial insects: the costs of a vertebrate-like effective population size

The evolution of reproductive division of labour and social life in social insects has lead to the emergence of several life-history traits and adaptations typical of larger organisms: social insect colonies can reach masses of several kilograms, they start reproducing only when they are several years old, and can live for decades. These features and the monopolization of reproduction by only one or few individuals in a colony should affect molecular evolution by reducing the effective population size. We tested this prediction by analysing genome-wide patterns of coding sequence polymorphism and divergence in eusocial vs. noneusocial insects based on newly generated RNA-seq data. We report very low amounts of genetic polymorphism and an elevated ratio of nonsynonymous to synonymous changes - a marker of the effective population size - in four distinct species of eusocial insects, which were more similar to vertebrates than to solitary insects regarding molecular evolutionary processes. Moreover, the ratio of nonsynonymous to synonymous substitutions was positively correlated with the level of social complexity across ant species. These results are fully consistent with the hypothesis of a reduced effective population size and an increased genetic load in eusocial insects, indicating that the evolution of social life has important consequences at both the genomic and population levels.

Optimisation of data analysis method for a fluidized bed combustion test rig

Nowadays the used fuel variety in power boilers is widening and new boiler constructions and running models have to be developed. This research and development is done in small pilot plants where more faster analyse about the boiler mass and heat balance is needed to be able to find and do the right decisions already during the test run. The barrier on determining boiler balance during test runs is the long process of chemical analyses of collected input and outputmatter samples. The present work is concentrating on finding a way to determinethe boiler balance without chemical analyses and optimise the test rig to get the best possible accuracy for heat and mass balance of the boiler. The purpose of this work was to create an automatic boiler balance calculation method for 4 MW CFB/BFB pilot boiler of Kvaerner Pulping Oy located in Messukylä in Tampere. The calculation was created in the data management computer of pilot plants automation system. The calculation is made in Microsoft Excel environment, which gives a good base and functions for handling large databases and calculations without any delicate programming. The automation system in pilot plant was reconstructed und updated by Metso Automation Oy during year 2001 and the new system MetsoDNA has good data management properties, which is necessary for big calculations as boiler balance calculation. Two possible methods for calculating boiler balance during test run were found. Either the fuel flow is determined, which is usedto calculate the boiler's mass balance, or the unburned carbon loss is estimated and the mass balance of the boiler is calculated on the basis of boiler's heat balance. Both of the methods have their own weaknesses, so they were constructed parallel in the calculation and the decision of the used method was left to user. User also needs to define the used fuels and some solid mass flowsthat aren't measured automatically by the automation system. With sensitivity analysis was found that the most essential values for accurate boiler balance determination are flue gas oxygen content, the boiler's measured heat output and lower heating value of the fuel. The theoretical part of this work concentrates in the error management of these measurements and analyses and on measurement accuracy and boiler balance calculation in theory. The empirical part of this work concentrates on the creation of the balance calculation for the boiler in issue and on describing the work environment.

Division of labor in insect societies : genetic components and physiological regulation

The shift from solitary to social organisms constitutes one of the major transitions in evolution. The highest level of sociality is found in social insects (ants, termites and some species of bees and wasps). Division of labor is central to the organization of insect societies and is thought to be at the root of their ecological success. There are two main levels of division of labor in social insect colonies. The first relates to reproduction and involves the coexistence of queen and worker castes: while reproduction is usually monopolized by one or several queens, functionally sterile workers perform all the tasks to maintain the colony, such as nest building, foraging or brood care. The second level of division of labor, relating to such non-reproductive duties, is characterized by the performance of different tasks or roles by different groups of workers. This PhD aims to better understand the mechanisms underlying division of labor in insect societies, by investigating how genes and physiology influence caste determination and worker behavior in ants. In the first axis of this PhD, we studied the nature of genetic effects on division of labor. We used the Argentine ant Linepithema humile to conduct controlled crosses in the laboratory, which revealed the existence of non-additive genetic effects, such as parent-of-origin and genetic compatibility effects, on caste determination and worker behavior. In the second axis, we focused on the physiological regulation of division of labor. Using Pogonomyrmex seed- harvester ants, we performed experimental manipulation of hibernation, hormonal treatments, gene expression analyses and protein quantification to identify the physiological pathways regulating maternal effects on caste determination. Finally, comparing gene expression between nurses and foragers allowed us to reveal the association between vitellogenin and worker behavior in Pogonomyrmex ants. This PhD provides important insights into the role of genes and physiology in the regulation of division of labor in social insect colonies, helping to better understand the organization, evolution and ecological success of insect societies. - L'une des principales transitions évolutives est le passage de la vie solitaire à la vie sociale. La socialité atteint son paroxysme chez les insectes sociaux que sont les fourmis, les termites et certaines espèces d'abeilles et de guêpes. La division du travail est la clé de voûte de l'organisation de ces sociétés d'insectes et la raison principale de leur succès écologique. La division du travail s'effectue à deux niveaux dans les colonies d'insectes sociaux. Le premier niveau concerne la reproduction et implique la coexistence de deux castes : les reines et les ouvrières. Tandis que la reproduction est le plus souvent monopolisée par une ou plusieurs reines, les ouvrières stériles effectuent les tâches nécessaires au bon fonctionnement de la colonie, telles que la construction du nid, la recherche de nourriture ou le soin au couvain. Le second niveau de division du travail, qui concerne les tâches autres que la reproduction, implique la réalisation de différents travaux par différents groupes d'ouvrières. Le but de ce doctorat est de mieux comprendre les mécanismes sous-jacents de la division du travail dans les sociétés d'insectes en étudiant comment les gènes et la physiologie influencent la détermination de la caste et le comportement des ouvrières chez les fourmis. Dans le premier axe de ce doctorat, nous avons étudié la nature des influences génétiques sur la division du travail. Nous avons utilisé la fourmi d'Argentine, Linepithema humile, pour effectuer des croisements contrôlés en laboratoire. Cette méthode nous a permis de révéler l'existence d'influences génétiques non additives, telles que des influences dépendantes de l'origine parentale ou des effets de compatibilité génétique, sur la détermination de la caste et le comportement des ouvrières. Dans le second axe, nous nous sommes intéressés à la régulation physiologique de la division du travail. Nous avons utilisé des fourmis moissonneuses du genre Pogonomyrmex pour effectuer des hibernations artificieHes, des traitements hormonaux, des analyses d'expression de gènes et des mesures de vitellogénine, ce qui nous a permis d'identifier les mécanismes physiologiques régulant les effets maternels sur la détermination de la caste. Enfin, la comparaison d'expression de gènes entre nourrices et fourrageuses suggère un rôle de la vitellogénine dans la régulation du comportement des ouvrières chez les fourmis moissonneuses. En détaillant les influences des gènes et de la physiologie dans la régulation de la division du travail dans les colonies d'insectes sociaux, ce doctorat fournit d'importantes informations permettant de mieux comprendre l'organisation, l'évolution et le succès écologique des sociétés d'insectes.

Optimisation of energy provision with supplemental parenteral nutrition in critically ill patients: a randomised controlled clinical trial.

BACKGROUND: Enteral nutrition (EN) is recommended for patients in the intensive-care unit (ICU), but it does not consistently achieve nutritional goals. We assessed whether delivery of 100% of the energy target from days 4 to 8 in the ICU with EN plus supplemental parenteral nutrition (SPN) could optimise clinical outcome. METHODS: This randomised controlled trial was undertaken in two centres in Switzerland. We enrolled patients on day 3 of admission to the ICU who had received less than 60% of their energy target from EN, were expected to stay for longer than 5 days, and to survive for longer than 7 days. We calculated energy targets with indirect calorimetry on day 3, or if not possible, set targets as 25 and 30 kcal per kg of ideal bodyweight a day for women and men, respectively. Patients were randomly assigned (1:1) by a computer-generated randomisation sequence to receive EN or SPN. The primary outcome was occurrence of nosocomial infection after cessation of intervention (day 8), measured until end of follow-up (day 28), analysed by intention to treat. This trial is registered with ClinicalTrials.gov, number NCT00802503. FINDINGS: We randomly assigned 153 patients to SPN and 152 to EN. 30 patients discontinued before the study end. Mean energy delivery between day 4 and 8 was 28 kcal/kg per day (SD 5) for the SPN group (103% [SD 18%] of energy target), compared with 20 kcal/kg per day (7) for the EN group (77% [27%]). Between days 9 and 28, 41 (27%) of 153 patients in the SPN group had a nosocomial infection compared with 58 (38%) of 152 patients in the EN group (hazard ratio 0·65, 95% CI 0·43-0·97; p=0·0338), and the SPN group had a lower mean number of nosocomial infections per patient (-0·42 [-0·79 to -0·05]; p=0·0248). INTERPRETATION: Individually optimised energy supplementation with SPN starting 4 days after ICU admission could reduce nosocomial infections and should be considered as a strategy to improve clinical outcome in patients in the ICU for whom EN is insufficient. FUNDING: Foundation Nutrition 2000Plus, ICU Quality Funds, Baxter, and Fresenius Kabi.

Conflict and co-operation in ant societies

Cette thèse se propose d?étudier les forces évolutives qui influencent la bal- ance entre coopération et conflit. Deux exemples sont analysés en détail, les sociétés d?insectes et l?association entre la fourmi Formica exsecta et son sym- bionte intracellulaire Wolbachia. Chacune de ces deux associations animales est caractérisée par la coexistence de coopération et de conflit. Les colonies d?insectes sociaux sont un exemple typique de coopération. Néanmoins, la détermination haplodiploïde du sexe crée des apparentements asymétriques entre les membres de la colonie qui se traduisent par des con- flits entre reines et ouvrières. Un des conflits les plus importants porte sur le sexe-ratio, l?investissement optimal en sexués males et femelles étant équilibré pour la reine, mais biaisé en faveur des femelles pour les ouvrières. Jusqu?ici, les modèles étudiant ce conflit se basaient uniquement sur les asymétries d?ap- parentement. La première partie de cette thèse (Chapitres 1 et 2) propose d?introduire dans des modèles de sexe-ratio les mécanismes proximaux utilisés par les deux parties pour influencer le sexe-ratio. Ces mécanismes, par leurs ef- fets négatifs sur la productivité de la colonie, peuvent entraîner des déviations importantes du sexe-ratio par rapport à la valeur prédite par des modèles clas- siques. De plus, la prise en compte de ces mécanismes nous permet d?étudier dans quelle mesure les parties opposées sont sélectionnées pour influencer le sexe-ratio. Enfin, les modèles génèrent des prédictions quant à l?issue du con- flit, c?est-à-dire un compromis où reines et ouvrières partagent le contrôle de l?investissement. La seconde partie du travail porte sur l?infection de la fourmi Formica ex- secta par le symbionte cytoplasmique Wolbachia. Ce symbionte, présent chez un grand nombre d?espèces d?Arthropodes, est transmis maternellement. Afin de se répandre dans la population d?hôtes, Wolbachia manipule la physiolo- gie reproductive de l?organisme qui l?abrite. Le Chapitre 3 décrit une étude consacrée aux variations du sexe-ratio produit dans des colonies de fourmis? en fonction de la présence ou de l?absence de Wolbachia. Le Chapitre 4 étudie l?association entre les lignées du symbionte et les haplotypes mitochondriaux des hôtes. L?étude de l?association entre les deux éléments maternellement transmis est d?un intérêt particulier chez Formica exsecta car le taux de migra- tion femelle très faible engendre une forte strucure génétique mitochondriale.

Artificial evolution on network structures : how time and space influence dynamics

Abstract The main objective of this work is to show how the choice of the temporal dimension and of the spatial structure of the population influences an artificial evolutionary process. In the field of Artificial Evolution we can observe a common trend in synchronously evolv¬ing panmictic populations, i.e., populations in which any individual can be recombined with any other individual. Already in the '90s, the works of Spiessens and Manderick, Sarma and De Jong, and Gorges-Schleuter have pointed out that, if a population is struc¬tured according to a mono- or bi-dimensional regular lattice, the evolutionary process shows a different dynamic with respect to the panmictic case. In particular, Sarma and De Jong have studied the selection pressure (i.e., the diffusion of a best individual when the only selection operator is active) induced by a regular bi-dimensional structure of the population, proposing a logistic modeling of the selection pressure curves. This model supposes that the diffusion of a best individual in a population follows an exponential law. We show that such a model is inadequate to describe the process, since the growth speed must be quadratic or sub-quadratic in the case of a bi-dimensional regular lattice. New linear and sub-quadratic models are proposed for modeling the selection pressure curves in, respectively, mono- and bi-dimensional regu¬lar structures. These models are extended to describe the process when asynchronous evolutions are employed. Different dynamics of the populations imply different search strategies of the resulting algorithm, when the evolutionary process is used to solve optimisation problems. A benchmark of both discrete and continuous test problems is used to study the search characteristics of the different topologies and updates of the populations. In the last decade, the pioneering studies of Watts and Strogatz have shown that most real networks, both in the biological and sociological worlds as well as in man-made structures, have mathematical properties that set them apart from regular and random structures. In particular, they introduced the concepts of small-world graphs, and they showed that this new family of structures has interesting computing capabilities. Populations structured according to these new topologies are proposed, and their evolutionary dynamics are studied and modeled. We also propose asynchronous evolutions for these structures, and the resulting evolutionary behaviors are investigated. Many man-made networks have grown, and are still growing incrementally, and explanations have been proposed for their actual shape, such as Albert and Barabasi's preferential attachment growth rule. However, many actual networks seem to have undergone some kind of Darwinian variation and selection. Thus, how these networks might have come to be selected is an interesting yet unanswered question. In the last part of this work, we show how a simple evolutionary algorithm can enable the emrgence o these kinds of structures for two prototypical problems of the automata networks world, the majority classification and the synchronisation problems. Synopsis L'objectif principal de ce travail est de montrer l'influence du choix de la dimension temporelle et de la structure spatiale d'une population sur un processus évolutionnaire artificiel. Dans le domaine de l'Evolution Artificielle on peut observer une tendence à évoluer d'une façon synchrone des populations panmictiques, où chaque individu peut être récombiné avec tout autre individu dans la population. Déjà dans les année '90, Spiessens et Manderick, Sarma et De Jong, et Gorges-Schleuter ont observé que, si une population possède une structure régulière mono- ou bi-dimensionnelle, le processus évolutionnaire montre une dynamique différente de celle d'une population panmictique. En particulier, Sarma et De Jong ont étudié la pression de sélection (c-à-d la diffusion d'un individu optimal quand seul l'opérateur de sélection est actif) induite par une structure régulière bi-dimensionnelle de la population, proposant une modélisation logistique des courbes de pression de sélection. Ce modèle suppose que la diffusion d'un individu optimal suit une loi exponentielle. On montre que ce modèle est inadéquat pour décrire ce phénomène, étant donné que la vitesse de croissance doit obéir à une loi quadratique ou sous-quadratique dans le cas d'une structure régulière bi-dimensionnelle. De nouveaux modèles linéaires et sous-quadratique sont proposés pour des structures mono- et bi-dimensionnelles. Ces modèles sont étendus pour décrire des processus évolutionnaires asynchrones. Différentes dynamiques de la population impliquent strategies différentes de recherche de l'algorithme résultant lorsque le processus évolutionnaire est utilisé pour résoudre des problèmes d'optimisation. Un ensemble de problèmes discrets et continus est utilisé pour étudier les charactéristiques de recherche des différentes topologies et mises à jour des populations. Ces dernières années, les études de Watts et Strogatz ont montré que beaucoup de réseaux, aussi bien dans les mondes biologiques et sociologiques que dans les structures produites par l'homme, ont des propriétés mathématiques qui les séparent à la fois des structures régulières et des structures aléatoires. En particulier, ils ont introduit la notion de graphe sm,all-world et ont montré que cette nouvelle famille de structures possède des intéressantes propriétés dynamiques. Des populations ayant ces nouvelles topologies sont proposés, et leurs dynamiques évolutionnaires sont étudiées et modélisées. Pour des populations ayant ces structures, des méthodes d'évolution asynchrone sont proposées, et la dynamique résultante est étudiée. Beaucoup de réseaux produits par l'homme se sont formés d'une façon incrémentale, et des explications pour leur forme actuelle ont été proposées, comme le preferential attachment de Albert et Barabàsi. Toutefois, beaucoup de réseaux existants doivent être le produit d'un processus de variation et sélection darwiniennes. Ainsi, la façon dont ces structures ont pu être sélectionnées est une question intéressante restée sans réponse. Dans la dernière partie de ce travail, on montre comment un simple processus évolutif artificiel permet à ce type de topologies d'émerger dans le cas de deux problèmes prototypiques des réseaux d'automates, les tâches de densité et de synchronisation.

Kumar's algorithm for solving Toeplitz systems of equations over finite fields

Adaptació de l'algorisme de Kumar per resoldre sistemes d'equacions amb matrius de Toeplitz sobre els reals a cossos finits en un temps 0 (n log n).

Implementation of the Rijndael-AES algorithm on a Sage-Math worksheet

La principal motivació d'aquest treball ha estat implementar l'algoritme Rijndael-AES en un full Sage-math, paquet de software matemàtic de lliure distribució i en actual desenvolupament, aprofitant les seves eines i funcionalitats integrades.

On the differential evolution algorithm and its appliation to training radial basis function networks

The parameter setting of a differential evolution algorithm must meet several requirements: efficiency, effectiveness, and reliability. Problems vary. The solution of a particular problem can be represented in different ways. An algorithm most efficient in dealing with a particular representation may be less efficient in dealing with other representations. The development of differential evolution-based methods contributes substantially to research on evolutionary computing and global optimization in general. The objective of this study is to investigatethe differential evolution algorithm, the intelligent adjustment of its controlparameters, and its application. In the thesis, the differential evolution algorithm is first examined using different parameter settings and test functions. Fuzzy control is then employed to make control parameters adaptive based on an optimization process and expert knowledge. The developed algorithms are applied to training radial basis function networks for function approximation with possible variables including centers, widths, and weights of basis functions and both having control parameters kept fixed and adjusted by fuzzy controller. After the influence of control variables on the performance of the differential evolution algorithm was explored, an adaptive version of the differential evolution algorithm was developed and the differential evolution-based radial basis function network training approaches were proposed. Experimental results showed that the performance of the differential evolution algorithm is sensitive to parameter setting, and the best setting was found to be problem dependent. The fuzzy adaptive differential evolution algorithm releases the user load of parameter setting and performs better than those using all fixedparameters. Differential evolution-based approaches are effective for training Gaussian radial basis function networks.