As proteínas são moléculas presentes nos seres vivos e essenciais para a vida deles. Para entender a função de uma proteína, devese conhecer sua estrutura tridimensional (o posicionamento correto de todos os seus átomos no espaço). A partir da estrutura de uma proteína vital de um organismo causador de uma doença é possível desenvolver fármacos para o tratamento da doença. Para encontrar a estrutura de uma proteína, métodos biofísicos, como Cristalografia de Raio-X e Ressonância Nuclear Magnética têm sido empregados. No entanto, o uso desses métodos tem restrições práticas que impedem a determinação de várias estruturas de proteínas. Para contornar essas limitações, métodos computacionais para o problema de predição da estrutura da proteína (PSP, Protein Structure Prediction) têm sido investigados. Várias classes de métodos computacionais têm sido desenvolvidas para o problema de PSP. Entre elas, as abordagens ab initio são muito importantes, pois não utilizam nenhuma informação prévia de outras estruturas de proteínas para fazer o PSP, apenas a sequência de aminoácidos da proteína e o gráfico de Ramachandran são empregados. O PSP ab initio é um problema combinatorial que envolve relativamente grandes instâncias na prática...
A tomografia por sensoriamento elétrico representa uma técnica de grande potencial para a otimização de processos normalmente associados às indústrias do petróleo e química. Entretanto, o emprego de técnicas tomográficas em processos industriais envolvendo fluidos multifásicos ainda carece de métodos robustos e computacionalmente eficientes. Nesse contexto, o principal objetivo deste trabalho é contribuir para o desenvolvimento de métodos para a solução do problema tomográfico com base em algoritmos genéticos específicos para a fenomenologia do problema abordado (interação do campo elétrico com o campo hidrodinâmico), bem como a adaptação do algoritmo para processamento em paralelo. A idéia básica consiste em partir de imagens qualitativas, fornecidas por uma sonda de visualização direta, para formar um modelo da distribuição interna do contraste elétrico e refiná-lo iterativamente até que variáveis de controle resultantes do modelo numérico se igualem às suas homólogas, determinadas experimentalmente. Isso pode ser feito usando um funcional de erro, que quantifique a diferença entre as medidas externas não intrusivas (fluxo de corrente elétrica real) e as medidas calculadas no modelo numérico (fluxo de corrente elétrica aproximado). De acordo com a abordagem funcional adotada...
O principal objetivo deste estudo é propor uma nova metodologia para lidar com o problema de Planejamento da Expansão de Redes de Transmissão de Energia Elétrica com Múltiplos Cenários de Geração (PERTEEG). Com a metodologia proposta neste trabalho almeja-se construir planos de expansão de redes de transmissão de energia elétrica que sejam capazes de, no menor custo de investimento possível, satisfazer às novas exigências dos sistemas elétricos modernos, tais como construção de redes de transmissão livres de congestionamento e robustas à incerteza em relação aos cenários de geração futuros. Através de estudos realizados na literatura do problema, verificou-se que novos modelos e metodologias de abordagem do PERTEEG se fazem necessários. Ao se modelar o PERTEEG visando construir redes de transmissão que contornem as incertezas em relação aos cenários de geração futuros e concomitantemente minimizar o custo de investimento para a expansão do sistema, o planejador se depara com um problema de otimização multiobjetivo. Existem na literatura da pesquisa operacional diversos algoritmos que visam lidar com problemas multiobjetivos. Nesta tese, foram aplicados dois desses algoritmos: Nondominated Sorting Genetic Algorithms-II (NSGA-II) e SPEA2: Strength Pareto Evolutionary Algorithm (SPEA2). Em primeira análise...
Esta trabalho apresenta a análise e implementação de uma técnica inteligente, o algoritmo genético (AG), para implementação de unidades de medição fasoriais, denominadas PMUs (Phasor Measurement Units). A disponibilidade dos fasores em diversos pontos de um sistema elétrico de potência (SEP) é importante, tanto para monitoramento quanto para controle, proteção e estudo do sistema. Entretanto, a obtenção de tais fasores só têm sentido se os mesmos possuírem o mesmo referencial no tempo. Este referencial é conseguido através de sinais de satélites GPS (Global Positioning System) que sincronizam as PMUs instaladas nos pontos de interesse. Existe uma vasta quantidade de m´métodos que podem ser utilizados para que, de posse das formas de onda discretizadas de tensão e corrente, estime-se os fasores correspondentes e as frequências locais. Este projeto apresenta os AGs como ferramenta de estimação para a obtenção de uma PMU com todas as vantagens relativas a tais algoritmos. Além disso, uma versão do AG que utiliza menos recursos computacionais , o algoritmo genético compacto (AGc) também será estudado. Um estudo norteado pela norma internacional C37.118 compara o desempenho dos AGs com dois métodos tradicionais de medição fasorial...
This paper describes a novel algorithm to analyze genetic linkage data using pattern recognition techniques and genetic algorithms (GA). The method allows a search for regions of the chromosome that may contain genetic variations that jointly predispose individuals for a particular disease. The method uses correlation analysis, filtering theory and genetic algorithms (GA) to achieve this goal. Because current genome scans use from hundreds to hundreds of thousands of markers, two versions of the method have been implemented. The first is an exhaustive analysis version that can be used to visualize, explore, and analyze small genetic data sets for two marker correlations; the second is a GA version, which uses a parallel implementation allowing searches of higher-order correlations in large data sets. Results on simulated data sets indicate that the method can be informative in the identification of major disease loci and gene-gene interactions in genome-wide linkage data and that further exploration of these techniques is justified. The results presented for both variants of the method show that it can help genetic epidemiologists to identify promising combinations of genetic factors that might predispose to complex disorders. In particular...
This paper describes the application of our distributed computing framework for crystal structure prediction (CSP), Modified Genetic Algorithms for Crystal and Cluster Prediction (MGAC) to predict the crystal structure of flexible molecules using the General Amber Force Field (GAFF) and the CHARMM program. The MGAC distributed computing framework which includes a series of tightly integrated computer programs for generating the molecule’s force field, sampling crystal structures using a distributed parallel genetic algorithm, local energy minimization of the structures followed by the classifying, sorting and archiving of the most relevant structures. Our results indicate that the method can consistently find the experimentally known crystal structures of flexible molecules, but the number of missing structures and poor ranking observed in some crystals show the need for further improvement of the potential.
The characterization and prediction of the structures of metal silicon clusters is important for nanotechnology research because these clusters can be used as building blocks for nano devices, integrated circuits and solar cells. Several authors have postulated that there is a transition between exo to endo absorption of Cu in Sin clusters and showed that for n larger than 9 it is possible to find endohedral clusters. Unfortunately, no global searchers have confirmed this observation, which is based on local optimizations of plausible structures. Here we use parallel Genetic Algorithms (GA), as implemented in our MGAC software, directly coupled with DFT energy calculations to show that the global search of CuSin cluster structures does not find endohedral clusters for n < 8 but finds them for n ≥ 10.
The implementation of parallel genetic algorithms raises many important issues. These issues can be divided into two main classes: genetic search quality and execution performance. In the context of parallel genetic algorithms on distributed-memory computers, performance considerations have always driven the design of implementations. Thus, centralized implementations have almost always been excluded from any consideration for distributed-memory architectures. The work we present here defines a set of genetic algorithm implementation alternatives for distributed-memory computers, in which strategies with some centralization are included. Each of our implementation alternatives uses a different level of distribution of the population, from the single logically centralized population to a totally distributed set of subpopulations. The design alternatives we define can be applied to the implementation of any parallel genetic algorithm. As an example of such an implementation, we study the quality of the search and the execution performance of our strategies on the 0-1 Integer Linear Programming problem, on a Transputer network. Our results show that implementations incurring higher overheads can produce as good or better solutions faster than than very "efficient" implementations...
Manipuladores paralelos são de grande interesse principalmente porque apresentam vantagens em várias aplicações, mostrando grande resistência, exatidão de posicionamento, capacidade de carga maior que manipuladores seriais e podem ser operados a altas velocidades e acelerações. No Laboratório de Robótica e Mecatrônica em Cassino, Itália, foi criado um mecanismo paralelo com três graus de liberdade, chamado CaPaMan (Cassino Parallel Manipulator). O objetivo principal deste trabalho é otimizar a trajetória da estrutura paralela CaPaMan. O problema de otimização multi-objetivo considera a minimização da energia gasta pelos atuadores, do tempo total de percurso e da variação de aceleração (jerk). A trajetória é calculada assumindo que os ângulos de entrada são obtidos por uma função do tempo, representada por B-splines uniformes. A modelagem cinemática é obtida derivando-se a equação da trajetória em relação ao tempo. O modelo analítico para a dinâmica inversa do CaPaMan utiliza as equações de Newton-Euler. A cadeia cinemática peculiar e as propriedades de simetria da arquitetura do CaPaMan são úteis nesta formulação, permitindo, para cada trajetória, calcular os torques de entrada e a energia dos atuadores. O vetor de funções multi-objetivo é transformado em uma função escalar usando o Método da Ponderação dos Objetivos. O problema de otimização é investigado aplicando algoritmos genéticos. A presença de mínimos locais justifica a utilização de métodos randômicos. Alguns exemplos numéricos são apresentados para verificação e validação da metodologia proposta. ________________________________________________________________________________________ ABSTRACT; Parallel manipulators are of great interest mainly because they present advantages in several applications...
Trees are probably the most studied class of graphs in Computer Science. In this thesis we study bijective codes that represent labeled trees by means of string of node labels. We contribute to the understanding of their algorithmic tractability, their properties, and their applications.
The thesis is divided into two parts. In the first part we focus on two types of tree codes, namely Prufer-like codes and Transformation codes. We study optimal encoding and decoding algorithms, both in a sequential and in a parallel setting. We propose a unified approach that works for all Prufer-like codes and a more generic scheme based on the transformation of a tree into a functional digraph suitable for all bijective codes. Our results in this area close a variety of open problems.
We also consider possible applications of tree encodings, discussing how to exploit these codes in Genetic Algorithms and in the generation of random trees. Moreover, we introduce a modified version of a known code that, in Genetic Algorithms, outperform all the other known codes.
In the second part of the thesis we focus on two possible generalizations of our work. We first take into account the classes of k-trees and k-arch graphs (both superclasses of trees): we study bijective codes for this classes of graphs and their algorithmic feasibility. Then...
Optimization of adaptive traffic signal timing is one of the most complex problems in traffic control systems. This dissertation presents a new method that applies the parallel genetic algorithm (PGA) to optimize adaptive traffic signal control in the presence of transit signal priority (TSP). The method can optimize the phase plan, cycle length, and green splits at isolated intersections with consideration for the performance of both the transit and the general vehicles. Unlike the simple genetic algorithm (GA), PGA can provide better and faster solutions needed for real-time optimization of adaptive traffic signal control. ^ An important component in the proposed method involves the development of a microscopic delay estimation model that was designed specifically to optimize adaptive traffic signal with TSP. Macroscopic delay models such as the Highway Capacity Manual (HCM) delay model are unable to accurately consider the effect of phase combination and phase sequence in delay calculations. In addition, because the number of phases and the phase sequence of adaptive traffic signal may vary from cycle to cycle, the phase splits cannot be optimized when the phase sequence is also a decision variable. A "flex-phase" concept was introduced in the proposed microscopic delay estimation model to overcome these limitations. ^ The performance of PGA was first evaluated against the simple GA. The results show that PGA achieved both faster convergence and lower delay for both under- or over-saturated traffic conditions. A VISSIM simulation testbed was then developed to evaluate the performance of the proposed PGA-based adaptive traffic signal control with TSP. The simulation results show that the PGA-based optimizer for adaptive TSP outperformed the fully actuated NEMA control in all test cases. The results also show that the PGA-based optimizer was able to produce TSP timing plans that benefit the transit vehicles while minimizing the impact of TSP on the general vehicles. The VISSIM testbed developed in this research provides a powerful tool to design and evaluate different TSP strategies under both actuated and adaptive signal control. ^
During the last decade the application of sensors for the detection and determination of various substances has gained an increasing popularity not only in the field of analytical chemistry but also in our daily life. Most sensor systems such as exhaust gas sensors for automobiles are based on single sensors, which are as selective as possible for the analyte of interest. The problems of interfering cross-reactive analytes and the lack of specific sensors for many analytes have ended up in the development of so-called sensor-arrays. Thereby, several analytes can be simultaneously quantified by the multivariate data analysis of the signal patterns of several cross-reactive sensors. Yet, this approach is also limited since the number of sensors in the array has to exceed the number of cross-reacting analytes.
In this work, a new approach is presented, which allows multi-analyte quantifications on the basis of single-sensor systems. Thereby, differences of interaction kinetics of the analytes and sensor are exploited using time-resolved measurements and time-resolved data analyses. This time-resolved evaluation of sensor signals together with suitable sensor materials combines the sensory principle with the chromatographic principle of separating analytes in space or time. The main objectives of this work can be subsumed into two focuses concerning the measurement principle and the data analysis.
The first focus is the introduction of time-resolved measurements in the field of chemical sensing. In this work the time-resolved measurements are based on the microporous polymer Makrolon as sensitive sensor coating...
This paper reports results of global searches of the most stable structures of silicon–lithium clusters for the series SinLi (n = 2–12) using parallel Genetic Algorithms (GA). For this study we have used our MGAC software directly coupled with DFT energy calculations (MGAC/CPMD). The paper reports the stable geometries, binding energies, HOMO–LUMO gap, and electronic properties at the PBE/6-311G(2d) level of theory. Global searches did not find any endohedral SinLi structures, which we find as local minima with energies much higher than most of the stable Si–Li clusters found by MGAC/CPMDGenetic.; Fil: González, Sebastián I.. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Física; Argentina; Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Física de Buenos Aires; Argentina;; Fil: Oña, Ofelia Beatriz. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico la Plata. Instituto de Investigaciones Fisicoquímicas Teóricas y Aplicadas; Argentina;; Fil: Ferraro, Marta Beatriz. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Física de Buenos Aires; Argentina; Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Física; Argentina;; Fil: Facelli...
This paper presents a novel application of Genetic Algorithms(GAs) to
quantify the performance of Platform as a Service (PaaS), a cloud service model
that plays a critical role in both industry and academia. While Cloud
benchmarks are not new, in this novel concept, the authors use a GA to take
advantage of the elasticity in Cloud services in a graceful manner that was not
previously possible. Using Google App Engine, Heroku, and Python Anywhere with
three distinct classes of client computers running our GA codebase, we
quantified the completion time for application of the GA to search for the
parameters of controllers for dynamical systems. Our results show statistically
significant differences in PaaS performance by vendor, and also that the
performance of the PaaS performance is dependent upon the client that uses it.
Results also show the effectiveness of our GA in determining the level of
service of PaaS providers, and for determining if the level of service of one
PaaS vendor is repeatable with another. Such a concept could then increase the
appeal of PaaS Cloud services by making them more financially appealing.
In the last decade the broad scope of complex networks has led to a rapid
progress. In this area a particular interest has the study of community
structures. The analysis of this type of structure requires the formalization
of the intuitive concept of community and the definition of indices of goodness
for the obtained results. A lot of algorithms has been presented to reach this
goal. In particular, an interesting problem is the search of overlapped
communities and it is field seems very interesting a solution based on the use
of genetic algorithms. The approach discusses in this paper is based on a
parallel implementation of a genetic algorithm and shows the performance
benefits of this solution.; Comment: 6 pages IEEE format, International Journal of Computer Science and
Information Security, IJCSIS November 2009, ISSN 1947 5500,
Genetic Algorithms (GAs) are powerful metaheuristic techniques mostly used in
many real-world applications. The sequential execution of GAs requires
considerable computational power both in time and resources. Nevertheless, GAs
are naturally parallel and accessing a parallel platform such as Cloud is easy
and cheap. Apache Hadoop is one of the common services that can be used for
parallel applications. However, using Hadoop to develop a parallel version of
GAs is not simple without facing its inner workings. Even though some
sequential frameworks for GAs already exist, there is no framework supporting
the development of GA applications that can be executed in parallel. In this
paper is described a framework for parallel GAs on the Hadoop platform,
following the paradigm of MapReduce. The main purpose of this framework is to
allow the user to focus on the aspects of GA that are specific to the problem
to be addressed, being sure that this task is going to be correctly executed on
the Cloud with a good performance. The framework has been also exploited to
develop an application for Feature Subset Selection problem. A preliminary
analysis of the performance of the developed GA application has been performed
using three datasets and shown very promising performance.
This paper presents the Anisotropic selection scheme for cellular Genetic
Algorithms (cGA). This new scheme allows to enhance diversity and to control
the selective pressure which are two important issues in Genetic Algorithms,
especially when trying to solve difficult optimization problems. Varying the
anisotropic degree of selection allows swapping from a cellular to an island
model of parallel genetic algorithm. Measures of performances and diversity
have been performed on one well-known problem: the Quadratic Assignment Problem
which is known to be difficult to optimize. Experiences show that, tuning the
anisotropic degree, we can find the accurate trade-off between cGA and island
models to optimize performances of parallel evolutionary algorithms. This
trade-off can be interpreted as the suitable degree of migration among
subpopulations in a parallel Genetic Algorithm.
Microarrays, which allow for the measurement of thousands of gene expression levels in parallel, have created a wealth of data not previously available to biologists along with new computational challenges. Microarray studies are characterized by a low sample number and a large feature space with many features irrelevant to the problem being studied. This makes feature selection a necessary pre-processing step for many analyses, particularly classification. A Genetic Algorithm -Artificial Neural Network (ANN) wrapper approach is implemented to find the highest scoring set of features for an ANN classifier. Each generation relies on the performance of a set of features trained on an ANN for fitness evaluation. A publically-available leukemia microarray data set (Golub et al., 1999), consisting of 25 AML and 47 ALL Leukemia samples, each with 7129 features, is used to evaluate this approach. Results show an increased performance over Golub's initial findings.
Genetic techniques are applied to the problem of electronic circuit design, with an
emphasis on VLSI circuits. The goal is to have a tool which has the performance and
flexibility to attack a wide range of problems. A genetic algorithm is used to design a circuit
specified by the desired input /output characteristics. A software system is implemented to
synthesize and optimize circuits using an asynchronous parallel genetic algorithm. The
software is designed with object-oriented constructs in order to maintain scalability and
provide for future enhancements. The system is executed on a heterogeneous network of
workstations ranging from Sun Sparc Ultras to HP multiprocessors. Testing of this software
is done with examples of both digital and analog CMOS VLSI circuits. Performance is
measured in both the quality of the solutions and in the time it took to evolve them.
Although solutions to many problems can be found using direct analytical methods such
as those calculus provides, many problems simply are too large or too difficult to solve
using traditional techniques. Genetic algorithms provide an indirect approach to solving
those problems. A genetic algorithm applies biological genetic procedures and principles
to a randomly generated collection of potential solutions. The result is the evolution of
new and better solutions. Coarse-Grained Parallel Genetic Algorithms extend the basic
genetic algorithm by introducing genetic isolation and distribution of the problem
This thesis compares the capabilities of a serial genetic algorithm and three
coarse-grained parallel genetic algorithms (a standard parallel algorithm, a non-uniform
parallel algorithm and an adaptive parallel algorithm). The evaluation is done using an
instance of the traveling salesman problem. It is shown that while the standard
course-grained parallel algorithm provides more consistent results than the serial genetic
algorithm, the adaptive distributed algorithm out-performs them both. To facilitate this
analysis, an extensible object-oriented library for genetic algorithms, encompassing both
serial and coarse-grained parallel genetic algorithms...