Grid job scheduling using Route with Genetic Algorithm support

In 2006 the Route load balancing algorithm was proposed and compared to other techniques aiming at optimizing the process allocation in grid environments. This algorithm schedules tasks of parallel applications considering computer neighborhoods (where the distance is defined by the network latency). Route presents good results for large environments, although there are cases where neighbors do not have an enough computational capacity nor communication system capable of serving the application. In those situations the Route migrates tasks until they stabilize in a grid area with enough resources. This migration may take long time what reduces the overall performance. In order to improve such stabilization time, this paper proposes RouteGA (Route with Genetic Algorithm support) which considers historical information on parallel application behavior and also the computer capacities and load to optimize the scheduling. This information is extracted by using monitors and summarized in a knowledge base used to quantify the occupation of tasks. Afterwards, such information is used to parameterize a genetic algorithm responsible for optimizing the task allocation. Results confirm that RouteGA outperforms the load balancing carried out by the original Route, which had previously outperformed others scheduling algorithms from literature.

Solving the Vehicle Routing Problem with Genetic ALgorithm and Simulated Annealing

This Thesis Work will concentrate on a very interesting problem, the Vehicle Routing Problem (VRP). In this problem, customers or cities have to be visited and packages have to be transported to each of them, starting from a basis point on the map. The goal is to solve the transportation problem, to be able to deliver the packages-on time for the customers,-enough package for each Customer,-using the available resources- and – of course - to be so effective as it is possible.Although this problem seems to be very easy to solve with a small number of cities or customers, it is not. In this problem the algorithm have to face with several constraints, for example opening hours, package delivery times, truck capacities, etc. This makes this problem a so called Multi Constraint Optimization Problem (MCOP). What’s more, this problem is intractable with current amount of computational power which is available for most of us. As the number of customers grow, the calculations to be done grows exponential fast, because all constraints have to be solved for each customers and it should not be forgotten that the goal is to find a solution, what is best enough, before the time for the calculation is up. This problem is introduced in the first chapter: form its basics, the Traveling Salesman Problem, using some theoretical and mathematical background it is shown, why is it so hard to optimize this problem, and although it is so hard, and there is no best algorithm known for huge number of customers, why is it a worth to deal with it. Just think about a huge transportation company with ten thousands of trucks, millions of customers: how much money could be saved if we would know the optimal path for all our packages.Although there is no best algorithm is known for this kind of optimization problems, we are trying to give an acceptable solution for it in the second and third chapter, where two algorithms are described: the Genetic Algorithm and the Simulated Annealing. Both of them are based on obtaining the processes of nature and material science. These algorithms will hardly ever be able to find the best solution for the problem, but they are able to give a very good solution in special cases within acceptable calculation time.In these chapters (2nd and 3rd) the Genetic Algorithm and Simulated Annealing is described in details, from their basis in the “real world” through their terminology and finally the basic implementation of them. The work will put a stress on the limits of these algorithms, their advantages and disadvantages, and also the comparison of them to each other.Finally, after all of these theories are shown, a simulation will be executed on an artificial environment of the VRP, with both Simulated Annealing and Genetic Algorithm. They will both solve the same problem in the same environment and are going to be compared to each other. The environment and the implementation are also described here, so as the test results obtained.Finally the possible improvements of these algorithms are discussed, and the work will try to answer the “big” question, “Which algorithm is better?”, if this question even exists.

Statistical bound of genetic solutions to quadratic assignment problems

Quadratic assignment problems (QAPs) are commonly solved by heuristic methods, where the optimum is sought iteratively. Heuristics are known to provide good solutions but the quality of the solutions, i.e., the confidence interval of the solution is unknown. This paper uses statistical optimum estimation techniques (SOETs) to assess the quality of Genetic algorithm solutions for QAPs. We examine the functioning of different SOETs regarding biasness, coverage rate and length of interval, and then we compare the SOET lower bound with deterministic ones. The commonly used deterministic bounds are confined to only a few algorithms. We show that, the Jackknife estimators have better performance than Weibull estimators, and when the number of heuristic solutions is as large as 100, higher order JK-estimators perform better than lower order ones. Compared with the deterministic bounds, the SOET lower bound performs significantly better than most deterministic lower bounds and is comparable with the best deterministic ones. 

Genetic heterogeneity of residual variance : estimation of variance components using double hierarchical generalized linear models

Background: The sensitivity to microenvironmental changes varies among animals and may be under genetic control. It is essential to take this element into account when aiming at breeding robust farm animals. Here, linear mixed models with genetic effects in the residual variance part of the model can be used. Such models have previously been fitted using EM and MCMC algorithms. Results: We propose the use of double hierarchical generalized linear models (DHGLM), where the squared residuals are assumed to be gamma distributed and the residual variance is fitted using a generalized linear model. The algorithm iterates between two sets of mixed model equations, one on the level of observations and one on the level of variances. The method was validated using simulations and also by re-analyzing a data set on pig litter size that was previously analyzed using a Bayesian approach. The pig litter size data contained 10,060 records from 4,149 sows. The DHGLM was implemented using the ASReml software and the algorithm converged within three minutes on a Linux server. The estimates were similar to those previously obtained using Bayesian methodology, especially the variance components in the residual variance part of the model. Conclusions: We have shown that variance components in the residual variance part of a linear mixed model can be estimated using a DHGLM approach. The method enables analyses of animal models with large numbers of observations. An important future development of the DHGLM methodology is to include the genetic correlation between the random effects in the mean and residual variance parts of the model as a parameter of the DHGLM.

A computational comparison of different algorithms for very large p-median problems

In this paper, we propose a new method for solving large scale p-median problem instances based on real data. We compare different approaches in terms of runtime, memory footprint and quality of solutions obtained. In order to test the different methods on real data, we introduce a new benchmark for the p-median problem based on real Swedish data. Because of the size of the problem addressed, up to 1938 candidate nodes, a number of algorithms, both exact and heuristic, are considered. We also propose an improved hybrid version of a genetic algorithm called impGA. Experiments show that impGA behaves as well as other methods for the standard set of medium-size problems taken from Beasley’s benchmark, but produces comparatively good results in terms of quality, runtime and memory footprint on our specific benchmark based on real Swedish data.

Simulation model using meta heuristic algorithms for achieving optimal arrangement of storage bins in a sawmill yard

Bin planning (arrangements) is a key factor in the timber industry. Improper planning of the storage bins may lead to inefficient transportation of resources, which threaten the overall efficiency and thereby limit the profit margins of sawmills. To address this challenge, a simulation model has been developed. However, as numerous alternatives are available for arranging bins, simulating all possibilities will take an enormous amount of time and it is computationally infeasible. A discrete-event simulation model incorporating meta-heuristic algorithms has therefore been investigated in this study. Preliminary investigations indicate that the results achieved by GA based simulation model are promising and better than the other meta-heuristic algorithm. Further, a sensitivity analysis has been done on the GA based optimal arrangement which contributes to gaining insights and knowledge about the real system that ultimately leads to improved and enhanced efficiency in sawmill yards. It is expected that the results achieved in the work will support timber industries in making optimal decisions with respect to arrangement of storage bins in a sawmill yard.

Transmission system expansion planning by an extended genetic algorithm

The paper presents an extended genetic algorithm for solving the optimal transmission network expansion planning problem. Two main improvements have been introduced in the genetic algorithm: (a) initial population obtained by conventional optimisation based methods; (b) mutation approach inspired in the simulated annealing technique, the proposed method is general in the sense that it does not assume any particular property of the problem being solved, such as linearity or convexity. Excellent performance is reported in the test results section of the paper for a difficult large-scale real-life problem: a substantial reduction in investment costs has been obtained with regard to previous solutions obtained via conventional optimisation methods and simulated annealing algorithms; statistical comparison procedures have been employed in benchmarking different versions of the genetic algorithm and simulated annealing methods.

Genetic divergence among Psidium accessions based on biochemical and agronomic variables

Sessenta e nove acessos de Psidium, coletados em seis estados brasileiros, foram analisados para dois métodos não hierárquicos de agrupamento e por componentes principais (CP), visando orientar programas de melhoramento. Foram analisadas as variáveis ácido ascórbico, β-caroteno, licopeno, fenóis totais, flavonóides totais, atividade antioxidante, acidez titulável, sólidos solúveis, açúcares solúveis totais, teor de umidade, diâmetro lateral e transversal do fruto, peso da polpa e das sementes/fruto, número e produção de frutos/planta. Foram observados agrupamentos específicos para os acessos de araçazeiros no método de Tocher e do k-means e na dispersão tridimensional dos quatro CPs. Os acessos de araçazeiros foram separados dos de goiabeira. Não foi observado nenhum agrupamento específico por estado de coleta, indicando a inexistência de barreiras na propagação dos acessos de goiabeira. As análises sugerem a prospecção de maior número de amostras de germoplasma num menor número de regiões, bem como acessos divergentes com alto teor de compostos nutricionais.

RFLP analysis of genetic variation in species of section Arachis, genus Arachis (Leguminosae)

Four A-genome species of the genus Arachis ( A. cardenasii, A. correntina, A. duranensis, A. kempff-mercadoi), three B genomes species ( A. batizocoi, A. ipaensis and A. magna), the AABB allotetraploid A. hypogaea (cultivated peanut) and introgression lines resulting from a cross between A. hypogaea and A. cardenasii were analyzed by RFLP. The A genome species (cytologically characterized by the presence of a small chromosome pair 'A') were closely similar to each other and shared a large number of restriction fragments. In contrast, the B genome species differed more from one another and shared few fragments. The results of this study indicate that the absence of the small chromosome pair is not a good criterion for grouping species of section Arachis as B genome species, since their genome might be quite distinct from the B genome of A. hypogaea. The lowest genetic variation was detected within accessions of A. duranensis (17 accessions), followed by A. batizocoi (4 accessions) and A. cardenasii (9 plants of accession GKP 10017). The high level of genetic variation found in A. cardenasii might indicate that not all accessions of wild species of Arachis are autogamous, as reported for A. hypogaea.

Genetic variation between several species of sections Extranervosae, Caulorrhizae, Heteranthae, and Triseminatae (genus Arachis) estimated by DNA polymorphism

Genetic variation within and among accessions of the genus Arachis representing sections Extranervosae, Caulorrhizae, Heteranthae, and Triseminatae was evaluated using RFLP and RAPD markers. RAPD markers revealed a higher level of genetic diversity than did RFLP markers, both within and among the species evaluated. Phenograms based on various band-matching algorithms revealed three major clusters of similarity among the sections evaluated. The first group included the species from section Extranervosae, the second group consisted of sections Triseminatae, Caulorrhizae, and Heteranthae, and the third group consisted of one accession of Arachis hypogaea, which had been included as a representative of section Arachis. The phenograms obtained from the RAPD and RFLP data were similar but not identical. Arachis pietrarellii, assayed only by RAPD, showed a high degree of genetic similarity with Arachis villosulicarpa. This observation supported the hypothesis that these two species are closely related. It was also shown that accession V 7786, previously considered to be Arachis sp. aff. pietrarellii, and assayed using both RFLPs and RAPDs, was possibly a new species from section Extranervosae, but very distinct from A. pietrarellii.

Planning of secondary distribution circuits through evolutionary algorithms

In this work, the planning of secondary distribution circuits is approached as a mixed integer nonlinear programming problem (MINLP). In order to solve this problem, a dedicated evolutionary algorithm (EA) is proposed. This algorithm uses a codification scheme, genetic operators, and control parameters, projected and managed to consider the specific characteristics of the secondary network planning. The codification scheme maps the possible solutions that satisfy the requirements in order to obtain an effective and low-cost projected system-the conductors' adequate dimensioning, load balancing among phases, and the transformer placed at the center of the secondary system loads. An effective algorithm for three-phase power flow is used as an auxiliary methodology of the EA for the calculation of the fitness function proposed for solutions of each topology. Results for two secondary distribution circuits are presented, whereas one presents radial topology and the other a weakly meshed topology. © 2005 IEEE.

Genetic diversity of the HLA-G coding region in Amerindian populations from the Brazilian Amazon: a possible role of natural selection

HLA-G has an important role in the modulation of the maternal immune system during pregnancy, and evidence that balancing selection acts in the promoter and 3′UTR regions has been previously reported. To determine whether selection acts on the HLA-G coding region in the Amazon Rainforest, exons 2, 3 and 4 were analyzed in a sample of 142 Amerindians from nine villages of five isolated tribes that inhabit the Central Amazon. Six previously described single-nucleotide polymorphisms (SNPs) were identified and the Expectation-Maximization (EM) and PHASE algorithms were used to computationally reconstruct SNP haplotypes (HLA-G alleles). A new HLA-G allele, which originated in Amerindian populations by a crossing-over event between two widespread HLA-G alleles, was identified in 18 individuals. Neutrality tests evidenced that natural selection has a complex part in the HLA-G coding region. Although balancing selection is the type of selection that shapes variability at a local level (Native American populations), we have also shown that purifying selection may occur on a worldwide scale. Moreover, the balancing selection does not seem to act on the coding region as strongly as it acts on the flanking regulatory regions, and such coding signature may actually reflect a hitchhiking effect.Genes and Immunity advance online publication, 3 October 2013; doi:10.1038/gene.2013.47.

Genetic characterisation of populations of the critically endangered Goliath grouper (Epinephelus itajara, Serranidae) from the Northern Brazilian coast through analyses of mtDNA

The Goliath grouper (Epinephelus itajara) is one of the most endangered species of fish of the subfamily Epinephelinae. Slow to develop and mature, and dependent on mangrove habitats for breeding, the species also suffers intense harvesting, which has reduced drastically in numbers in many areas. To contribute to the understanding of the characteristics of E. itajara populations, we conducted a molecular genetics study of the species, focusing on populations from the Northern Brazilian coast. The mtDNA control region (D-loop) of 116 individuals from five localities (Bragança, Ajuruteua, Parnaíba, Fortaleza and Natal) was analysed, and a sequence of 499 base pairs identified. Analyses of the sequences indicated that genetic variability was generally lower in E. itajara than in other endangered species of the genus. AMOVA found no significant grouping structure among the populations. Nested Clade Analysis revealed a significant association between genetic variability and geographic distribution among only three populations (Ajuruteua, Parnaíba and Natal). Genetic diversity was higher in populations from the Amazon region, which may be related to the better conservation of mangrove habitats in this area. Therefore, the present study could be used for the implementation of conservation and management measures in order to protect and consolidate these populations.

Simultaneous spectrometric determination of Cu2+, Mn2+ and Zn2+ in polivitaminic/polimineral drug using SPA and GA algorithms for variable selection

Este artigo apresenta uma aplicação do método para determinação espectrofotométrica simultânea dos íons divalentes de cobre, manganês e zinco à análise de medicamento polivitamínico/polimineral. O método usa 4-(2-piridilazo) resorcinol (PAR), calibração multivariada e técnicas de seleção de variáveis e foi otimizado o empregando-se o algoritmo das projeções sucessivas (APS) e o algoritmo genético (AG), para escolha dos comprimentos de onda mais informativos para a análise. Com essas técnicas, foi possível construir modelos de calibração por regressão linear múltipla (RLM-APS e RLM-AG). Os resultados obtidos foram comparados com modelos de regressão em componentes principais (PCR) e nos mínimos quadrados parciais (PLS). Demonstra-se a partir do erro médio quadrático de previsão (RMSEP) que os modelos apresentam desempenhos semelhantes ao prever as concentrações dos três analitos no medicamento. Todavia os modelos RLM são mais simples pois requerem um número muito menor de comprimentos de onda e são mais fáceis de interpretar que os baseados em variáveis latentes.

Comparison of a genetic group and unknown paternity models for growth traits in Nellore cattle

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)