Submitted by Maicon Juliano Schmidt (maicons) on 2015-03-30T11:51:21Z No. of bitstreams: 1 Carlos Eduardo de Jesus Guimarães Oliveira.pdf: 1236896 bytes, checksum: ef9d04e6f25aee7908b56a622411bc74 (MD5) / Made available in DSpace on 2015-03-30T11:51:21Z (GMT). No. of bitstreams: 1 Carlos Eduardo de Jesus Guimarães Oliveira.pdf: 1236896 bytes, checksum: ef9d04e6f25aee7908b56a622411bc74 (MD5) Previous issue date: 2014-01-31 / Nenhuma / Este trabalho apresenta um algoritmo de otimização baseado na metaheurística dos Sistemas Imunológicos Artificiais, princípios de Teoria dos Jogos, Co-evolução e Paralelização. Busca-se a combinação adequada dos conceitos de Teoria dos Jogos, Co-evolução e Paralelização aplicados ao algoritmo AISO (Artificial Immune System Optimization) para resolução do Problema de Alocação de Berços (PAB). Dessa maneira, o algoritmo é formalizado a partir das técnicas citadas, formando o PCAISO-GT: Parallel Coevolutionary Artificial Immune System Optimization with Game Theory. Inicialmente, foram realizados experimentos visando à sintonia dos parâmetros empregados nas diferentes versões da ferramenta desenvolvida. Com base nas melhores configurações identificadas, foram realizados experimentos de avaliação através da solução de um conjunto de instâncias do PAB. Os resultados obtidos permitiram a indicação da versão co-evolutiva associada à teoria dos jogos como a melhor para solução do problema em estudo. / This paper presents an optimization algorithm based on metaheuristic of Artificial Immune Systems, principles of Game Theory, Co-evolution and parallelization. The objective is find the appropriate combination of the concepts of Game Theory, Co-evolution and Parallelization applied to AISO algorithm (Artificial Immune System Optimization) for solving the Berth Allocation Problem (BAP). Thus, the algorithm is formalized from the above mentioned techniques, forming the PCAISO-GT: Parallel Coevolutionary Artificial Immune System Optimization with Game Theory. Initially, experiments aiming to tune the parameters were performed using different versions of the tool developed. Based on the identified best settings, evaluation experiments were carried out by solving a set of instances of the PAB. The results obtained allowed the appointment of co-evolutionary version associated with game theory as the best solution to the problem under study.

On TFBS motif discovery, three novel GA based algorithms are developed, namely GALF-P with focus on optimization, GALF-G for modeling, and GASMEN for spaced motifs. Novel memetic operators are introduced, namely local filtering and probabilistic refinement, to significantly improve effectiveness (e.g. 73% better than MEME) and efficiency (e.g. 4.49 times speedup) in search. The GA based algorithms have been extensively tested on comprehensive synthetic, real and benchmark datasets, and shown outstanding performances compared with state-of-the-art approaches. Our algorithms also "evolve" to handle more and more relaxed cases, namely from fixed motif widths to most flexible widths, from single motifs to multiple motifs with overlapping control, from stringent motif instance assumption to very relaxed ones, and from contiguous motifs to generic spaced motifs with arbitrary spacers. / TF-TFBS associated sequence pattern (rule) discovery is further investigated for better deciphering protein-DNA interactions in regulation. We for the first time generalize previous exact TF-TFBS rules to approximate ones using a progressive approach. A customized algorithm is developed, outperforming MEME by over 73%. The approximate TF-TFBS rules, compared with the exact ones, have significantly more verified rules and better verification ratios. Detailed analysis on PDB cases and conservation verification on NCBI protein records illustrate that the approximate rules reveal the flexible and specific protein-DNA interactions with much greater generalized capability. / The comprehensive pattern discovery algorithms developed will be further verified, improved and extended to further deciphering transcriptionial regulation, such as inferring whole gene regulatory networks by applying TFBS and TF-TFBS patterns discovered and incorporating expression data. / Transcription Factor (TF) and Transcription Factor Binding Site (TFBS) bindings are fundamental protein-DNA interactions in transcriptional regulation. TFs and TFBSs are conserved to form patterns (motifs) due to their important roles for controlling gene expressions and finally affecting functions and appearances. Pattern discovery is thus important for deciphering gene regulation, which has tremendous impacts on the understanding of life, bio-engineering and therapeutic applications. This thesis contributes to pattern discovery involving TFBS motifs and TF-TFBS associated sequence patterns based on Evolutionary Computation (EC), especially Genetic Algorithms (GAs), which are promising for bioinformatics problems with huge and noisy search space. / Chan, Tak Ming. / Advisers: Kwong-Sak Leung; Kin-Hong Lee. / Source: Dissertation Abstracts International, Volume: 73-03, Section: B, page: . / Thesis (Ph.D.)--Chinese University of Hong Kong, 2010. / Includes bibliographical references (leaves 147-153). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [201-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract also in Chinese.

O Dilema do Prisioneiro com n jogadores é um problema que ilustra a dificuldade na formação da cooperação em sociedades de indivíduos racionais. Diversos trabalhos foram feitos no sentido de compreender melhor os fatores que influenciam o surgimento e a evolução da cooperação nessas sociedades, sendo que muitos desses mostraram que a simulação deste tipo de problema carece de escalabilidade, o que impede a realização de experimentos que envolvam uma grande quantidade de agentes ou de parâmetros de teste. Este trabalho tem o intuito de aplicar conceitos de computação paralela para tratar este problema. Para tal, foi desenvolvido um sistema denominado PS2 E2 , evolução de um trabalho anterior, cuja utilização em alguns cenários possibilitou a verificação da influência de alguns parâmetros tais como o tamanho da população e a expressividade do modelo de representação de estratégias na utilidade global de um conjunto de agentes que jogam o Dilema do Prisioneiro com n jogadores. / The n-Player Prisoners Dilemma is a problem that illustrates the difficulty of cooperation formation in societies composed of rational individuals. Several studies were made to better understand the factors that influence the emergence and evolution of cooperation in these societies. Many of these showed that the simulation of this type of problem lacks scalability, which hinders the achievement of experiments involving a large number of agents or test parameters. This work intends to apply parallel computing concepts to treat this problem. To this end, it was developed a system called PS2 E2 , an evolution of a previous work, whose utilization in some scenarios allowed the verification of the influence of some parameters such as the population size and the expressiveness of the strategy representation model in the global utility of a society of agents that play the n-Player Prisoner Dilemma.

Artificial neural networks have been widely used for machine learning and optimization. A neuro ensemble is a collection of neural networks that works cooperatively on a problem. In the literature, it has been shown that by combining several neural networks, the generalization of the overall system could be enhanced over the separate generalization ability of the individuals. Evolutionary computation can be used to search for a suitable architecture and weights for neural networks. When evolutionary computation is used to evolve a neuro ensemble, it is usually known as evolutionary neuro ensemble. In most real-world problems, we either know little about these problems or the problems are too complex to have a clear vision on how to decompose them by hand. Thus, it is usually desirable to have a method to automatically decompose a complex problem into a set of overlapping or non-overlapping sub-problems and assign one or more specialists (i.e. experts, learning machines) to each of these sub-problems. An important feature of neuro ensemble is automatic problem decomposition. Some neuro ensemble methods are able to generate networks, where each individual network is specialized on a unique sub-task such as mapping a subspace of the feature space. In real world problems, this is usually an important feature for a number of reasons including: (1) it provides an understanding of the decomposition nature of a problem; (2) if a problem changes, one can replace the network associated with the sub-space where the change occurs without affecting the overall ensemble; (3) if one network fails, the rest of the ensemble can still function in their sub-spaces; (4) if one learn the structure of one problem, it can potentially be transferred to other similar problems. In this thesis, I focus on classification problems and present a systematic study of a novel evolutionary neuro ensemble approach which I call cooperative coevolutionary mixture of experts (CCME). Cooperative coevolution (CC) is a branch of evolutionary computation where individuals in different populations cooperate to solve a problem and their fitness function is calculated based on their reciprocal interaction. The mixture of expert model (ME) is a neuro ensemble approach which can generate networks that are specialized on different sub-spaces in the feature space. By combining CC and ME, I have a powerful framework whereby it is able to automatically form the experts and train each of them. I show that the CCME method produces competitive results in terms of generalization ability without increasing the computational cost when compared to traditional training approaches. I also propose two different mechanisms for visualizing the resultant decomposition in high-dimensional feature spaces. The first mechanism is a simple one where data are grouped based on the specialization of each expert and a color-map of the data records is visualized. The second mechanism relies on principal component analysis to project the feature space onto lower dimensions, whereby decision boundaries generated by each expert are visualized through convex approximations. I also investigate the regularization effect of learning by forgetting on the proposed CCME. I show that learning by forgetting helps CCME to generate neuro ensembles of low structural complexity while maintaining their generalization abilities. Overall, the thesis presents an evolutionary neuro ensemble method whereby (1) the generated ensemble generalizes well; (2) it is able to automatically decompose the classification problem; and (3) it generates networks with small architectures.

No description available.

No description available.

Made available in DSpace on 2014-12-17T15:47:55Z (GMT). No. of bitstreams: 1 SilviaMDM_DISSERT.pdf: 1535044 bytes, checksum: 925f2f885f42335d55c35aa64bb4d026 (MD5) Previous issue date: 2011-02-17 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior / The Multiobjective Spanning Tree is a NP-hard Combinatorial Optimization problem whose application arises in several areas, especially networks design. In this work, we propose a solution to the biobjective version of the problem through a Transgenetic Algorithm named ATIS-NP. The Computational Transgenetic is a metaheuristic technique from Evolutionary Computation whose inspiration relies in the conception of cooperation (and not competition) as the factor of main influence to evolution. The algorithm outlined is the evolution of a work that has already yielded two other transgenetic algorithms. In this sense, the algorithms previously developed are also presented. This research also comprises an experimental analysis with the aim of obtaining information related to the performance of ATIS-NP when compared to other approaches. Thus, ATIS-NP is compared to the algorithms previously implemented and to other transgenetic already presented for the problem under consideration. The computational experiments also address the comparison to two recent approaches from literature that present good results, a GRASP and a genetic algorithms. The efficiency of the method described is evaluated with basis in metrics of solution quality and computational time spent. Considering the problem is within the context of Multiobjective Optimization, quality indicators are adopted to infer the criteria of solution quality. Statistical tests evaluate the significance of results obtained from computational experiments / A ?rvore Geradora Multiobjetivo ? um problema de Otimiza??o Combinat?ria NP-?rduo. Esse problema possui aplica??o em diversas ?reas, em especial, no projeto de redes. Nesse trabalho, prop?e-se uma solu??o para o problema em sua vers?o biobjetivo por meio de um Algoritmo Transgen?tico, denominado ATIS-NP. A Transgen?tica Computacional ? uma t?cnica metaheur?stica da Computa??o Evolucion?ria cuja inspira??o est? na coopera??o (e n?o na competi??o) como fator de maior influ?ncia para a evolu??o. O algoritmo proposto ? a evolu??o de um trabalho que j? originou dois outros algoritmos transgen?ticos. Nesse sentido, os algoritmos previamente desenvolvidos tamb?m s?o apresentados. Essa pesquisa compreende ainda uma an?lise experimental que visa obter informa??es quanto ao desempenho do ATIS-NP quando comparado a outros algoritmos. Para tanto, o ATIS-NP ? comparado aos dois algoritmos anteriormente implementados, bem como a outro transgen?tico proposto na literatura para o problema tratado. Os experimentos computacionais abrangem ainda a compara??o do algoritmo desenvolvido a duas abordagens recentes da literatura que obt?m excelentes resultados, um GRASP e um gen?tico. A efici?ncia do m?todo apresentado ? avaliada com base em medidas de qualidade de solu??o e tempo computacional despendido. Uma vez que o problema se insere no contexto da Otimiza??o Multiobjetivo, indicadores de qualidade s?o utilizados para inferir o crit?rio de qualidade de solu??es obtidas. Testes estat?sticos avaliam a signific?ncia dos resultados obtidos nos experimentos computacionais

Made available in DSpace on 2014-12-17T15:48:10Z (GMT). No. of bitstreams: 1 DenisF_DISSERT.pdf: 776997 bytes, checksum: c0d801fdcf21ff4f335f115d3918ed93 (MD5) Previous issue date: 2014-02-14 / The Scientific Algorithms are a new metaheuristics inspired in the scientific research process. The new method introduces the idea of theme to search the solution space of hard problems. The inspiration for this class of algorithms comes from the act of researching that comprises thinking, knowledge sharing and disclosing new ideas. The ideas of the new method are illustrated in the Traveling Salesman Problem. A computational experiment applies the proposed approach to a new variant of the Traveling Salesman Problem named Car Renter Salesman Problem. The results are compared to state-of-the-art algorithms for the latter problem / Os algoritmos cient?ficos s?o uma nova metaheur?stica inspirada no processo da pesquisa cient?fica. O novo m?todo introduz a ideia de tema para buscar o espa?o de solu??es de problemas dif?ceis. A inspira??o para esta classe de algoritmos vem do ato de pesquisar, que compreende pensar, compartilhar conhecimento e descobrir novas ideias. As ideias do novo m?todo s?o ilustradas no Problema do Caixeiro Viajante. Um experimento computacional aplica a abordagem proposta a uma nova variante do Problema do Caixeiro Viajante intitulada Problema do Caixeiro Alugador. Os resultados s?o comparados aos algoritmos do estado da arte para o ?ltimo problema

Este trabalho apresenta uma arquitetura para simulação de circuitos de lógica com binacional de topologia arbitrária, visando interfaceamento com algoritmos evolutivos para fins de geração de hardware. A implementação é em FPGA utilizando a técnica VRC. O simulador permite circuitos compostos por LUTs de número de entradas parametrizável. A livre interconectividade entre as LUTs permite a construção de circuitos cíclicos. A arquitetura é modular e de interfaceamento simples. Alta performance é obtida através do uso de múltiplos módulos de simulação em paralelo, trazendo resultados que ultrapassam os obtidos em outros trabalhos utilizando DPR. / This work presents an architecture for simulation of combinational logic circuits of arbitrary topology, meant to be interfaced with evolutionary algorithms for hardware generation. It was implemented in FPGA using the VRC technique. The simulator allows for circuits composed of LUTs of parametrizable number of imputs. The free interconectivity between LUTs allows the construction of cyclic circuits. The architecture is modular and of simple interfacing. High performance is obtained by the use of multiple simulation modules in parallel, bringing results that surpass the ones obtained from other works based on DPR.

Muitos problemas de otimização reais apresentam mais de uma função-objetivo. Quando os objetivos são conflitantes, estratégias especializadas são necessárias, como é o caso dos algoritmos evolutivos multiobjetivo (MOEAs, do inglês Multi-objective Optimization Evolutionary Algorithms). Entretanto, se a avaliação das funções-objetivo é custosa (alto custo computacional ou econômico) muitos MOEAs propostos são impraticáveis. Uma alternativa pode ser a utilização de um modelo de aprendizado de máquina que aproxima o cálculo do fitness (surrogate) no algoritmo de otimização. Este trabalho propõe e investiga uma plataforma chamada ELMOEA/D que agrega MOEAs do estado da arte baseados em decomposição de objetivos (MOEA/D) e máquinas de aprendizado extremo (ELMs, do inglês Extreme Learning Machines) como modelos surrogate. A plataforma proposta é testada com diferentes variantes do algoritmo MOEA/D e apresenta bons resultados em problemas benchmark, comparada a um algoritmo da literatura que também utiliza MOEA/D mas modelos surrogates baseados em redes com função de base radial. A plataforma ELMOEA/D também é testada no Problema de Predição de Estrutura de Proteínas (PPEP). Apesar dos resultados alcançados pela proposta não serem tão animadores quanto aqueles obtidos nos benchmarks (quando comparados os algoritmos com e sem surrogates), diversos aspectos da proposta e do problema são explorados. Por fim, a plataforma ELMOEA/D é aplicada a uma formulação alternativa do PPEP com sete objetivos e, com estes resultados, várias direções para trabalhos futuros são apontadas. / Many real optimization problems have more than one objective function. When the objectives are in conflict, there is a need for specialized strategies, as is the case of the Multi-objective Optimization Evolutionary Algorithms (MOEAs). However, if the functions evaluation is expensive (high computational or economical costs) many proposed MOEAs are impractical. An alternative might be the use of a machine learning model to approximate the fitness function (surrogates) in the optimization algorithm. This work proposes and investigates a framework called ELMOEA/D that aggregates state-of-the-art MOEAs based on decomposition of objectives (MOEA/D) and extreme learning machines as surrogate models. The proposed framework is tested with different MOEA/D variants and show good results in benchmark problems, compared to a literature algorithm that also encompasses MOEA/D but uses surrogate models based on radial basis function networks. The ELMOEA/D framework is also applied to the protein structure prediction problem (PSPP). Despite the fact that the results achieved by the proposed approach were not as encouraging as the ones achieved in the benchmarks (when the algorithms with and without surrogates are compared), many aspects of both algorithm and problem are explored. Finally, the ELMOEA/D framework is applied to an alternative formulation of the PSPP and the results lead to various directions for future works.