'An Indirect Genetic Algorithm for Set Covering Problems'

This paper presents a new type of genetic algorithm for the set covering problem. It differs from previous evolutionary approaches first because it is an indirect algorithm, i.e. the actual solutions are found by an external decoder function. The genetic algorithm itself provides this decoder with permutations of the solution variables and other parameters. Second, it will be shown that results can be further improved by adding another indirect optimisation layer. The decoder will not directly seek out low cost solutions but instead aims for good exploitable solutions. These are then post optimised by another hill-climbing algorithm. Although seemingly more complicated, we will show that this three-stage approach has advantages in terms of solution quality, speed and adaptability to new types of problems over more direct approaches. Extensive computational results are presented and compared to the latest evolutionary and other heuristic approaches to the same data instances.

'Exploiting problem structure in a genetic algorithm approach to a nurse rostering problem'

There is considerable interest in the use of genetic algorithms to solve problems arising in the areas of scheduling and timetabling. However, the classical genetic algorithm paradigm is not well equipped to handle the conflict between objectives and constraints that typically occurs in such problems. In order to overcome this, successful implementations frequently make use of problem specific knowledge. This paper is concerned with the development of a GA for a nurse rostering problem at a major UK hospital. The structure of the constraints is used as the basis for a co-evolutionary strategy using co-operating sub-populations. Problem specific knowledge is also used to define a system of incentives and disincentives, and a complementary mutation operator. Empirical results based on 52 weeks of live data show how these features are able to improve an unsuccessful canonical GA to the point where it is able to provide a practical solution to the problem.

Multilocus genetic analyses provide insight into speciation and hybridization in aquatic grasses, genus Ruppia

Aquatic plants of the genus Ruppia inhabit some of the most threatened habitats in the world, such as coastal lagoons and inland saline to brackish waters where their meadows play several key roles. The evolutionary history of this genus has been affected by the processes of hybridization, polyploidization, and vicariance, which have resulted in uncertainty regarding the number of species. In the present study, we apply microsatellite markers for the identification, genetic characterization, and detection of hybridization events among populations of putative Ruppia species found in the southern Iberian Peninsula, with the exception of a clearly distinct species, the diploid Ruppia maritima. Microsatellite markers group the populations into genetically distinct entities that are not coincident with geographical location and contain unique diagnostic alleles. These results support the interpretation of these entities as distinct species: designated here as (1) Ruppia drepanensis, (2) Ruppia cf. maritima, and (3) Ruppia cirrhosa. A fourth distinct genetic entity was identified as a putative hybrid between R. cf. maritima and R. cirrhosa because it contained a mixture of microsatellite alleles that are otherwise unique to these putative species. Hence, our analyses were able to discriminate among different genetic entities of Ruppia and, by adding multilocus nuclear markers, we confirm hybridization as an important process of speciation within the genus. In addition, careful taxonomic curation of the samples enabled us to determine the genotypic and genetic diversity and differentiation among populations of each putative Ruppia species. This will be important for identifying diversity hotspots and evaluating patterns of population genetic connectivity. © 2015 The Linnean Society of London, Biological Journal of the Linnean Society, 2015, 00, 000–000.

Efficient Hill Climber for Constrained Pseudo-Boolean Optimization Problems

Efficient hill climbers have been recently proposed for single- and multi-objective pseudo-Boolean optimization problems. For $k$-bounded pseudo-Boolean functions where each variable appears in at most a constant number of subfunctions, it has been theoretically proven that the neighborhood of a solution can be explored in constant time. These hill climbers, combined with a high-level exploration strategy, have shown to improve state of the art methods in experimental studies and open the door to the so-called Gray Box Optimization, where part, but not all, of the details of the objective functions are used to better explore the search space. One important limitation of all the previous proposals is that they can only be applied to unconstrained pseudo-Boolean optimization problems. In this work, we address the constrained case for multi-objective $k$-bounded pseudo-Boolean optimization problems. We find that adding constraints to the pseudo-Boolean problem has a linear computational cost in the hill climber.

Genetic Structure of the Florida Key Tree Cactus, Pilosocereus robinii, using Restriction Site associated DNA (RAD) markers

Rare plant conservation efforts must utilize current genetic methods to ensure the evolutionary potential of populations is preserved. One such effort involves the Key Tree Cactus, Pilosocereus robinii, which is an endangered columnar cactus native to the Florida Keys. The populations have precipitously declined over the past decade because of habitat loss and increasing soil salinity from rising sea levels and storm surge. Next-generation DNA sequencing was used to assess the genetic structure of the populations. Twenty individuals representative of both wild and extirpated cacti were chosen for Restriction Site Associated DNA (RAD) analysis. Samples processed using the HindIII and NotIII restriction enzymes produced 82,382,440 high quality reads used for genetic mapping, from which 5,265 Single Nucleotide Polymorphisms (SNPs) were discovered. The analysis revealed that the Keys’ populations are closely related with little population differentiation. In addition, the populations display evidence of inbreeding and low genetic diversity.

New Rigorous Decomposition Methods for Mixed-integer Linear and Nonlinear Programming

Process systems design, operation and synthesis problems under uncertainty can readily be formulated as two-stage stochastic mixed-integer linear and nonlinear (nonconvex) programming (MILP and MINLP) problems. These problems, with a scenario based formulation, lead to large-scale MILPs/MINLPs that are well structured. The first part of the thesis proposes a new finitely convergent cross decomposition method (CD), where Benders decomposition (BD) and Dantzig-Wolfe decomposition (DWD) are combined in a unified framework to improve the solution of scenario based two-stage stochastic MILPs. This method alternates between DWD iterations and BD iterations, where DWD restricted master problems and BD primal problems yield a sequence of upper bounds, and BD relaxed master problems yield a sequence of lower bounds. A variant of CD, which includes multiple columns per iteration of DW restricted master problem and multiple cuts per iteration of BD relaxed master problem, called multicolumn-multicut CD is then developed to improve solution time. Finally, an extended cross decomposition method (ECD) for solving two-stage stochastic programs with risk constraints is proposed. In this approach, a CD approach at the first level and DWD at a second level is used to solve the original problem to optimality. ECD has a computational advantage over a bilevel decomposition strategy or solving the monolith problem using an MILP solver. The second part of the thesis develops a joint decomposition approach combining Lagrangian decomposition (LD) and generalized Benders decomposition (GBD), to efficiently solve stochastic mixed-integer nonlinear nonconvex programming problems to global optimality, without the need for explicit branch and bound search. In this approach, LD subproblems and GBD subproblems are systematically solved in a single framework. The relaxed master problem obtained from the reformulation of the original problem, is solved only when necessary. A convexification of the relaxed master problem and a domain reduction procedure are integrated into the decomposition framework to improve solution efficiency. Using case studies taken from renewable resource and fossil-fuel based application in process systems engineering, it can be seen that these novel decomposition approaches have significant benefit over classical decomposition methods and state-of-the-art MILP/MINLP global optimization solvers.

Evaluación del desempeño de pruebas diagnósticas de tuberculosis en pacientes VIH positivo en dos hospitales públicos de Bogotá

La tuberculosis TB es una de las principales causas de muerte en el mundo en individuos con infección por VIH. En Colombia esta coinfección soporta una carga importante en la población general convirtiéndose en un problema de salud pública. En estos pacientes las pruebas diagnósticas tienen sensibilidad inferior y la enfermedad evoluciona con mayor frecuencia hacia formas diseminadas y rápidamente progresivas y su diagnóstico oportuno representa un reto en Salud. El objetivo de este proyecto es evaluar el desempeño de las pruebas diagnósticas convencionales y moleculares, para la detección de TB latente y activa pacientes con VIH, en dos hospitales públicos de Bogotá. Para TB latente se evaluó la concordancia entre las pruebas QuantiFERON-TB (QTF) y Tuberculina (PPD), sugiriendo superioridad del QTF sobre la PPD. Se evaluaron tres pruebas diagnósticas por su sensibilidad y especificidad, baciloscopia (BK), GenoType®MTBDR plus (Genotype) y PCR IS6110 teniendo como estándar de oro el cultivo. Los resultados de sensibilidad (S) y especificidad (E) de cada prueba con una prevalencia del 19,4 % de TB pulmonar y extrapulmonar en los pacientes que participaron del estudio fue: BK S: 64% E: 99,1%; Genotype S: 77,8% E: 94,5%; PCRIS6110 S: 73% E: 95,5%, de la misma forma se determinaron los valores predictivos positivos y negativos (VPP y VPN) BK: 88,9% y 94,8%, Genotype S: 77,8% E: 94,5%; PCRIS6110 S: 90% y 95,7%. Se concluyó bajo análisis de curva ROC que las pruebas muestran un rendimiento diagnóstico similar por separado en el diagnóstico de TB en pacientes con VIH, aumentando su rendimiento diagnostico cuando se combinan

Aplicaciones de los modelos de predicción bio-inspirados en la administración

Las organizaciones y sus entornos son sistemas complejos. Tales sistemas son difíciles de comprender y predecir. Pese a ello, la predicción es una tarea fundamental para la gestión empresarial y para la toma de decisiones que implica siempre un riesgo. Los métodos clásicos de predicción (entre los cuales están: la regresión lineal, la Autoregresive Moving Average y el exponential smoothing) establecen supuestos como la linealidad, la estabilidad para ser matemática y computacionalmente tratables. Por diferentes medios, sin embargo, se han demostrado las limitaciones de tales métodos. Pues bien, en las últimas décadas nuevos métodos de predicción han surgido con el fin de abarcar la complejidad de los sistemas organizacionales y sus entornos, antes que evitarla. Entre ellos, los más promisorios son los métodos de predicción bio-inspirados (ej. redes neuronales, algoritmos genéticos /evolutivos y sistemas inmunes artificiales). Este artículo pretende establecer un estado situacional de las aplicaciones actuales y potenciales de los métodos bio-inspirados de predicción en la administración.

Tracking the Origin of a Rabbit Haemorrhagic Virus 2 Outbreak in a Wild Rabbit Breeding Centre in Portugal; Epidemiological and Genetic Investigation

As key prey, the wild rabbit downsize constitutes a major drawback on the endangered Iberian lynx (Lynx pardinus) re-introduction in the Iberia. Several captive breeding units mostly located in Alentejo, endeavour the wild rabbit repopulation of depleted areas assigned for the lynx re-introduction. Here we report an RHDV2 outbreak that occurred in early 2016 in a wild rabbit captive breeding unit located in Barrancos municipality. The estimated mortality rate between March and April 2016 was approximately 8.67%. Anatomopathologic examination was carried out for 13 victimized rabbits. Molecular characterization was based on the complete vp60 capsid gene. The 13 rabbit carcasses investigated showed typical macroscopic RHD lesions testing positive to RHDV2-RNA. Comparison of the vp60 nucleotide sequences obtained from two specimens with others publically available disclosed similarities below 98.22% with RHDV2 strains originated in the Iberia and Azores and revealed that the two identical strains from Barrancos-2016 contain six unique single synonymous nucleotide polymorphisms. In the phylogenetic analysis performed, the Barrancos-2016 strains clustered apart from other known strains,meaning they may represent new evolutionary RHDV2 lineages. No clear epidemiological link could be traced for this outbreak where the mortalities were lower compared with previous years. Yet, network analysis suggested a possible connection between the missing intermediates from which the strains from Barrancos 2013, 2014 and 2016 have derived. It is therefore possible that RHDV2 has circulated endemically in the region since 2012, with periodic epizootic occurrences. Still, six years after its emergence in wild rabbits, RHDV2 continues to pose difficulties to the establishment of natural wild rabbit populations that are crucial for the self-sustainability of the local ecosystems.

Tracking the Origin of a Rabbit Haemorrhagic Virus 2 Outbreak in a Wild Rabbit Breeding Centre in Portugal; Epidemiological and Genetic Investigation

As key prey, the wild rabbit downsize constitutes a major drawback on the endangered Iberian lynx (Lynx pardinus) re-introduction in the Iberia. Several captive breeding units mostly located in Alentejo, endeavour the wild rabbit repopulation of depleted areas assigned for the lynx re-introduction. Here we report an RHDV2 outbreak that occurred in early 2016 in a wild rabbit captive breeding unit located in Barrancos municipality. The estimated mortality rate between March and April 2016 was approximately 8.67%. Anatomopathologic examination was carried out for 13 victimized rabbits. Molecular characterization was based on the complete vp60 capsid gene. The 13 rabbit carcasses investigated showed typical macroscopic RHD lesions testing positive to RHDV2- RNA. Comparison of the vp60 nucleotide sequences obtained from two specimens with others publically available disclosed similarities below 98.22% with RHDV2 strains originated in the Iberia and Azores and revealed that the two identical strains from Barrancos-2016 contain six unique single synonymous nucleotide polymorphisms. In the phylogenetic analysis performed, the Barrancos-2016 strains clustered apart from other known strains, meaning they may represent new evolutionary RHDV2 lineages. No clear epidemiological link could be traced for this outbreak where the mortalities were lower compared with previous years. Yet, network analysis suggested a possible connection between the missing intermediates from which the strains from Barrancos 2013, 2014 and 2016 have derived. It is therefore possible that RHDV2 has circulated endemically in the region since 2012, with periodic epizootic occurrences. Still, six years after its emergence in wild rabbits, RHDV2 continues to pose difficulties to the establishment of natural wild rabbit populations that are crucial for the self-sustainability of the local ecosystems.

Evolutionary algorithms for the modeling of bioreactors

This work aims to study the application of Genetic Algorithms in anaerobic digestion modeling, in particular when using dynamical models. Along the work, different types of bioreactors are shown, such as batch, semi-batch and continuous, as well as their mathematical modeling. The work intendeds to estimate the parameter values of two biological reaction model. For that, simulated results, where only one output variable, the produced biogas, is known, are fitted to the model results. For this reason, the problems associated with reverse optimization are studied, using some graphics that provide clues to the sensitivity and identifiability associated with the problem. Particular solutions obtained by the identifiability analysis using GENSSI and DAISY softwares are also presented. Finally, the optimization is performed using genetic algorithms. During this optimization the need to improve the convergence of genetic algorithms was felt. This need has led to the development of an adaptation of the genetic algorithms, which we called Neighbored Genetic Algorithms (NGA1 and NGA2). In order to understand if this new approach overcomes the Basic Genetic Algorithms (BGA) and achieves the proposed goals, a study of 100 full optimization runs for each situation was further developed. Results show that NGA1 and NGA2 are statistically better than BGA. However, because it was not possible to obtain consistent results, the Nealder-Mead method was used, where the initial guesses were the estimated results from GA; Algoritmos Evolucionários para a Modelação de Bioreactores Resumo: Neste trabalho procura-se estudar os algoritmos genéticos com aplicação na modelação da digestão anaeróbia e, em particular, quando se utilizam modelos dinâmicos. Ao longo do mesmo, são apresentados diferentes tipos de bioreactores, como os batch, semi-batch e contínuos, bem como a modelação matemática dos mesmos. Neste trabalho procurou-se estimar o valor dos parâmetros que constam num modelo de digestão anaeróbia para o ajustar a uma situação simulada onde apenas se conhece uma variável de output, o biogas produzido. São ainda estudados os problemas associados à optimização inversa com recurso a alguns gráficos que fornecem pistas sobre a sensibilidade e identifiacabilidade associadas ao problema da modelação da digestão anaeróbia. São ainda apresentadas soluções particulares de idenficabilidade obtidas através dos softwares GENSSI e DAISY. Finalmente é realizada a optimização do modelo com recurso aos algoritmos genéticos. No decorrer dessa optimização sentiu-se a necessidade de melhorar a convergência e, portanto, desenvolveu-se ainda uma adaptação dos algoritmos genéticos a que se deu o nome de Neighboured Genetic Algorithms (NGA1 e NGA2). No sentido de se compreender se as adaptações permitiam superar os algoritmos genéticos básicos e atingir as metas propostas, foi ainda desenvolvido um estudo em que o processo de optimização foi realizado 100 vezes para cada um dos métodos, o que permitiu concluir, estatisticamente, que os BGA foram superados pelos NGA1 e NGA2. Ainda assim, porque não foi possivel obter consistência nos resultados, foi usado o método de Nealder-Mead utilizado como estimativa inicial os resultados obtidos pelos algoritmos genéticos.