121 |
Algoritmos anytime baseados em instâncias para classificação em fluxo de dados / Instance-based anytime algorithm to data stream classificationLemes, Cristiano Inácio 09 March 2016 (has links)
Aprendizado em fluxo de dados é uma área de pesquisa importante e que vem crescendo nos últimos tempos. Em muitas aplicações reais os dados são gerados em uma sequência temporal potencialmente infinita. O processamento em fluxo possui como principal característica a necessidade por respostas que atendam restrições severas de tempo e memória. Por exemplo, um classificador aplicado a um fluxo de dados deve prover uma resposta a um determinado evento antes que o próximo evento ocorra. Caso isso não ocorra, alguns eventos do fluxo podem ficar sem classificação. Muitos fluxos geram eventos em uma taxa de chegada com grande variabilidade, ou seja, o intervalo de tempo de ocorrência entre dois eventos sucessivos pode variar muito. Para que um sistema de aprendizado obtenha sucesso na aquisição de conhecimento é preciso que ele apresente duas características principais: (i) ser capaz de prover uma classificação para um novo exemplo em tempo hábil e (ii) ser capaz de adaptar o modelo de classificação de maneira a tratar mudanças de conceito, uma vez que os dados podem não apresentar uma distribuição estacionária. Algoritmos de aprendizado de máquina em lote não possuem essas propriedades, pois assumem que as distribuições são estacionárias e não estão preparados para atender restrições de memória e processamento. Para atender essas necessidades, esses algoritmos devem ser adaptados ao contexto de fluxo de dados. Uma possível adaptação é tornar o algoritmo de classificação anytime. Algoritmos anytime são capazes de serem interrompidos e prover uma resposta (classificação) aproximada a qualquer instante. Outra adaptação é tornar o algoritmo incremental, de maneira que seu modelo possa ser atualizado para novos exemplos do fluxo de dados. Neste trabalho é realizada a investigação de dois métodos capazes de realizar o aprendizado em um fluxo de dados. O primeiro é baseado no algoritmo k-vizinhos mais próximo anytime estado-da-arte, onde foi proposto um novo método de desempate para ser utilizado neste algoritmo. Os experimentos mostraram uma melhora consistente no desempenho deste algoritmo em várias bases de dados de benchmark. O segundo método proposto possui as características dos algoritmos anytime e é capaz de tratar a mudança de conceito nos dados. Este método foi chamado de Algoritmo Anytime Incremental e possui duas versões, uma baseado no algoritmo Space Saving e outra em uma Janela Deslizante. Os experimentos mostraram que em cada fluxo cada versão deste método proposto possui suas vantagens e desvantagens. Mas no geral, comparado com outros métodos baselines, ambas as versões apresentaram melhor desempenho. / Data stream learning is a very important research field that has received much attention from the scientific community. In many real-world applications, data is generated as potentially infinite temporal sequences. The main characteristic of stream processing is to provide answers observing stringent restrictions of time and memory. For example, a data stream classifier must provide an answer for each event before the next one arrives. If this does not occur, some events from the data stream may be left unclassified. Many streams generate events with highly variable output rate, i.e. the time interval between two consecutive events may vary greatly. For a learning system to be successful, two properties must be satisfied: (i) it must be able to provide a classification for a new example in a short time and (ii) it must be able to adapt the classification model to treat concept change, since the data may not follow a stationary distribution. Batch machine learning algorithms do not satisfy those properties because they assume that the distribution is stationary and they are not prepared to operate with severe memory and processing constraints. To satisfy these requirements, these algorithms must be adapted to the data stream context. One possible adaptation is to turn the algorithm into an anytime classifier. Anytime algorithms may be interrupted and still provide an approximated answer (classification) at any time. Another adaptation is to turn the algorithm into an incremental classifier so that its model may be updated with new examples from the data stream. In this work, it is performed an evaluation of two approaches for data stream learning. The first one is based on a state-of-the-art k-nearest neighbor anytime classifier. A new tiebreak approach is proposed to be used with this algorithm. Experiments show consistently better results in the performance of this algorithm in many benchmark data sets. The second proposed approach is to adapt the anytime algorithm for concept change. This approach was called Incremental Anytime Algorithm, and it was designed with two versions. One version is based on the Space Saving algorithm and the other is based in a Sliding Window. Experiments show that both versions are significantly better than baseline approaches.
|
122 |
Algoritmo enxame de partículas evolutivo para o problema de coordenação de relés de sobrecorrente direcionais em sistemas elétricos de potência / Particle swarm evolutionary algorithm for the coordination problem of directional overcurrent relays in power systemsFábio Marcelino de Paula Santos 21 June 2013 (has links)
Um sistema elétrico de potência agrega toda a estrutura pela qual a energia elétrica percorre, desde a sua geração até o seu consumo final. Nas últimas décadas observou-se um significativo aumento da demanda e, consequentemente, um aumento das interligações entre sistemas, tornando assim a operação e o controle destes extremamente complexos. Com o fim de obter a desejada operação destes sistemas, inúmeros estudos na área de Proteção de Sistemas Elétricos são realizados, pois é sabido que a interrupção desses serviços causam transtornos que podem assumir proporções desastrosas. Em sistemas elétricos malhados, nos quais as correntes de curto-circuito podem ser bidirecionais e podem ter intensidades diferentes devido a alterações topológicas nos mesmos, coordenar relés de sobrecorrente pode ser uma tarefa muito trabalhosa caso não haja nenhuma ferramenta de apoio. Neste contexto, este trabalho visa o desenvolvimento de uma metodologia eficiente que determine os ajustes otimizados dos relés de sobrecorrente direcionais instalados em sistemas elétricos malhados de forma a garantir a rapidez na eliminação da falta, bem como a coordenação e seletividade, considerando as várias intensidades das correntes de curto-circuito. Seguindo essa linha de raciocínio, observou-se que o uso de técnicas metaheurísticas para lidar com o problema da coordenação de relés é capaz de alcançar resultados significativos. No presente projeto, dentre os algoritmos inteligentes estudados, optou-se por pesquisar a aplicação do Algoritmo Enxame de Partículas Evolutivo (Evolutionary Particle Swarm Optimization) por este apresentar como características as vantagens tanto do Algoritmo Enxame de Partículas (Particle Swarm Optimization) quanto as dos Algoritmos Genéticos, possuindo assim grande potencial para solução destes tipos de problemas. / An electric power system aggregates all the structure in which the electric energy travels, from its generation to the final user. In the last decades it has been observed a significative increase of the demand and, consequently, an increment of the number of interconnections between systems, making the operation and control of them extremely complex. Aiming to obtain a good operation of this kind of systems, a lot of effort in the research area of power system protection has been spent, because it is known that the interruption of this service causes disorders that may assume disastrous proportions. In meshed power systems, in which the shortcircuit currents might be bidirectional and might have different magnitudes due to topological changes on them, to coordinate overcurrent relays may be a really hard task if you do not have a support tool. Look in this context, this work aims the development of and efficient methodology thats determine the optimal parameters of the directional overcurrent relays in a meshed electric power system ensuring the quickness in the fault elimination, as well as the coordination and selectivity of the protection system, considering the various intensities of the short-circuit currents. Maintaining this line, it has been noticed that the use of metaheuristics to deal with the problem of relay coordination is capable of achieving promissory results. In the present research, among the studied intelligent algorithms, it was chosen to use in it the Evolutionary Particle Swarm Optimization, due to its features thats is the advantages of the Particle Swarm Optimization as well as the Genetic Algorithms ones, hence it has great potential do solve theses kind of problems.
|
123 |
Seleção de características para reconhecimento biométrico baseado em sinais de eletrocardiograma / Feature selection for biometric recognition based on electrocardiogram signalsFelipe Gustavo Silva Teodoro 22 June 2016 (has links)
O campo da Biometria abarca uma grande variedade de tecnologias usadas para identificar e verificar a identidade de uma pessoa por meio da mensuração e análise de vários aspectos físicos e/ou comportamentais do ser humano. Diversas modalidades biométricas têm sido propostas para reconhecimento de pessoas, como impressões digitais, íris, face e voz. Estas modalidades biométricas possuem características distintas em termos de desempenho, mensurabilidade e aceitabilidade. Uma questão a ser considerada com a aplicação de sistemas biométricos em mundo real é sua robustez a ataques por circunvenção, repetição e ofuscação. Esses ataques estão se tornando cada vez mais frequentes e questionamentos estão sendo levantados a respeito dos níveis de segurança que esta tecnologia pode oferecer. Recentemente, sinais biomédicos, como eletrocardiograma (ECG), eletroencefalograma (EEG) e eletromiograma (EMG) têm sido estudados para uso em problemas envolvendo reconhecimento biométrico. A formação do sinal do ECG é uma função da anatomia estrutural e funcional do coração e dos seus tecidos circundantes. Portanto, o ECG de um indivíduo exibe padrão cardíaco único e não pode ser facilmente forjado ou duplicado, o que tem motivado a sua utilização em sistemas de identificação. Entretanto, a quantidade de características que podem ser extraídas destes sinais é muito grande. A seleção de característica tem se tornado o foco de muitas pesquisas em áreas em que bases de dados formadas por dezenas ou centenas de milhares de características estão disponíveis. Seleção de característica ajuda na compreensão dos dados, reduzindo o custo computacional, reduzindo o efeito da maldição da dimensionalidade e melhorando o desempenho do preditor. O foco da seleção de característica é selecionar um subconjunto de característica a partir dos dados de entrada, que pode descrever de forma eficiente os dados de entrada ao mesmo tempo reduzir os efeitos de ruídos ou características irrelevantes e ainda proporcionar bons resultados de predição. O objetivo desta dissertação é analisar o impacto de algumas técnicas de seleção de característica tais como, Busca Gulosa, Seleção \\textit, Algoritmo Genético, Algoritmo Memético, Otimização por Enxame de Partículas sobre o desempenho alcançado pelos sistemas biométricos baseado em ECG. Os classificadores utilizados foram $k$-Vizinhos mais Próximos, Máquinas de Vetores Suporte, Floresta de Caminhos Ótimos e classificador baseado em distância mínima. Os resultados demonstram que existe um subconjunto de características extraídas do sinal de ECG capaz de fornecer altas taxas de reconhecimento / The field of biometrics includes a variety of technologies used to identify and verify the identity of a person by measuring and analyzing various physical and/or behavioral aspects of the human being. Several biometric modalities have been proposed for recognition of people, such as fingerprints, iris, face and speech. These biometric modalities have distinct characteristics in terms of performance, measurability and acceptability. One issue to be considered with the application of biometric systems in real world is its robustness to attacks by circumvention, spoof and obfuscation. These attacks are becoming more frequent and more questions are being raised about the levels of security that this technology can offer. Recently, biomedical signals, as electrocardiogram (ECG), electroencephalogram (EEG) and electromyogram (EMG) have been studied for use in problems involving biometric recognition. The ECG signal formation is a function of structural and functional anatomy of the heart and its surrounding tissues. Therefore, the ECG of an individual exhibits unique cardiac pattern and cannot be easily forged or duplicated, that have motivated its use in various identification systems. However, the amount of features that can be extracted from this signal is very large. The feature selection has become the focus of much research in areas where databases formed by tens or hundreds of thousands of features are available. Feature Selection helps in understanding data, reducing computation requirement, reducing the effect of curse of dimensionality and improving the predictor performance. The focus of feature selection is to select a subset of features from the input which can efficiently describe the input data while reducing effects from noise or irrelevant features and still provide good prediction results. The aim of this dissertation is to analyze the impact of some feature selection techniques, such as, greedy search, Backward Selection, Genetic Algorithm, Memetic Algorithm, Particle Swarm Optimization on the performance achieved by biometric systems based on ECG. The classifiers used were $k$-Nearest Neighbors, Support Vector Machines, Optimum-Path Forest and minimum distance classifier. The results demonstrate that there is a subset of features extracted from the ECG signal capable of providing high recognition rates
|
124 |
Estudo da parametrização do algoritmo híbrido baseado no algoritmo cultural com algoritmo genético em uma abordagem multipopulacionalSILVA JUNIOR, Joaquim Alberto Leite da 01 October 2015 (has links)
Submitted by camilla martins (camillasmmartins@gmail.com) on 2017-02-01T18:52:10Z
No. of bitstreams: 2
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Dissertacao_EstudoParametrizacaoAlgoritmo.pdf: 3111483 bytes, checksum: ec493e124af4e9aebd3b8c11812222e9 (MD5) / Approved for entry into archive by Edisangela Bastos (edisangela@ufpa.br) on 2017-02-14T14:12:24Z (GMT) No. of bitstreams: 2
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Dissertacao_EstudoParametrizacaoAlgoritmo.pdf: 3111483 bytes, checksum: ec493e124af4e9aebd3b8c11812222e9 (MD5) / Made available in DSpace on 2017-02-14T14:12:24Z (GMT). No. of bitstreams: 2
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Dissertacao_EstudoParametrizacaoAlgoritmo.pdf: 3111483 bytes, checksum: ec493e124af4e9aebd3b8c11812222e9 (MD5)
Previous issue date: 2015-10-01 / FAPEAM - Fundação de Amparo à Pesquisa do Estado do Amazonas / A finalidade deste trabalho é analisar a aplicação de um algoritmo cultural híbrido, com população gerada pelo algoritmo genético, de característica multipopulacional, ou ainda, mais precisamente, desenvolver uma parametrização do algoritmo híbrido baseado no algoritmo cultural com algoritmo genético para o problema da mochila multidimensional. Tem-se como objetivo encontrar os melhores parâmetros do algoritmo cultural híbrido, com modelo de ilhas (característica multipopulacional), aplicado ao problema de otimização combinatório denominado de “Mochila Multidimensional”. São executados vários experimentos para efetuar uma avaliação em relação ao desempenho desses mecanismos híbridos com outros algoritmos disponíveis na literatura. / The purpose of this paper is to analyze the application of a hybrid cultural algorithm with population generated by multipopulation feature of the genetic algorithm, or, more specifically, to develop a parameter of the hybrid algorithm based on cultural algorithm with genetic algorithm for multidimensional knapsack problem in areas of computer science and computational intelligence. The aim of this work is to find the best parameters for hybrid cultural algorithm and over genetic algorithm, with model of islands (multipopulation characteristic) applied to combinatorial optimization problem called “Multidimensional Knapsack“. Several experiments are performed to make an assessment regarding of these mechanisms hybrids with other algorithms available in the literature.
|
125 |
An?lise multin?vel wavelet como fitness na sintonia de controladores utilizando meta-heur?sticasPires, Andr? Henrique Matias 06 December 2017 (has links)
Submitted by Automa??o e Estat?stica (sst@bczm.ufrn.br) on 2018-03-12T13:20:55Z
No. of bitstreams: 1
AndreHenriqueMatiasPires_DISSERT.pdf: 5565361 bytes, checksum: f5665a81cdc1abafd016753cfb9016e6 (MD5) / Approved for entry into archive by Arlan Eloi Leite Silva (eloihistoriador@yahoo.com.br) on 2018-03-13T20:49:03Z (GMT) No. of bitstreams: 1
AndreHenriqueMatiasPires_DISSERT.pdf: 5565361 bytes, checksum: f5665a81cdc1abafd016753cfb9016e6 (MD5) / Made available in DSpace on 2018-03-13T20:49:03Z (GMT). No. of bitstreams: 1
AndreHenriqueMatiasPires_DISSERT.pdf: 5565361 bytes, checksum: f5665a81cdc1abafd016753cfb9016e6 (MD5)
Previous issue date: 2017-12-06 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior (CAPES) / O controle de sistemas din?micos apresenta-se como um desafio. Os m?todos tradicionalmente
utilizados na sintonia apresentam a dificuldade em expressar as especifica??es
pretendidas e conseguir encontrar controladores que atendam a esses requerimentos, sobretudo
quando o caso exige controladores mais complexos, como no caso de problemas
MIMO (Multiple Input Multiple Output). Devido ? crescente competitividade na ind?stria,
torna-se imprescind?vel utilizar t?cnicas de sintonia mais eficientes e que de fato consigam
encontrar controladores com desempenho pretendido. Pode-se, para isso, utilizar
meta-heur?sticas, como Particle Swarm Optimization (PSO), Algoritmo Gen?tico (AG) e
Algoritmo do Vagalume(AV) para a obten??o dos par?metros do controlador de acordo
com uma fun??o de avalia??o, a qual deve conseguir, de fato, codificar o qu?o bom ? um
dado controlador, expressando de forma adequada as especifica??es desejadas, de modo
que a meta-heur?stica empregada consiga encontrar o controlador que melhor satisfa?a tal
fun??o. Em vista disso, prop?e-se a utiliza??o da an?lise wavelet multin?veis, j? muito
presente na literatura, voltada para outras aplica??es, sobretudo na an?lise de sinais, sons
e imagens, para a confec??o de um ?ndice a ser utilizado como fun??o de avalia??o na
otimiza??o de controladores. A an?lise wavelet permite a apreens?o de informa??es do
comportamento e forma do sinal, informando frequ?ncia de um sinal ao longo do tempo,
caracter?stica que pode ser desej?vel, na avalia??o e projeto de controladores sendo, assim,
poss?vel avaliar separadamente o desempenho do transit?rio e do regime permanente. Foi
feito um estudo de caso, encontrando o controle otimizado de um sistema MIMO de quatro
tanques acoplados. Foi feito um estudo comparativo com outras fun??es de avalia??o
apresentadas na literatura e com o m?todo do LGR (Lugar Geom?trico das Raizes). Os
controladores implementados apresentaram o desempenho esperado, e aquele encontrado
utilizando o ?ndice proposto presentou melhor desempenho. / The control of dynamic systems is a challenge, the methods traditionally used in tuning
present the difficulty in expressing the desired specifications and being able to find
controllers that produce these requirements, especially when the case requires more complex
controllers, as in the case of Multiple Input Multiple Output (MIMO) problems. Due
to the increasing competitiveness in the industry, it becomes imperative to use more efficient
tuning techniques and that in fact can find controllers with the desired performance.
For this, one can use metaheuristics, such as Particle Swarm Optimization (PSO), Genetic
Algorithm (AG) and Vagalume Algorithm (AV) to obtain the parameters of the controller
according to a fitness function, which should in fact code how good a given controller is,
adequately expressing the desired specifications, so that the metaheuristic employed can
find the optimal controller, which best satisfies the chosen fitness function. Therefore, it is
proposed to use the multilevel wavelet analysis, already present in the literature, focused
on other applications, especially in the analysis of signals, sounds and images, for the creation
of an index to be used as a fitness function in control optimization. Wavelet analysis
allows to capture information on the behavior and shape of the signal by informing the
frequency of a signal over time, a characteristic that may be desirable, in the evaluation
and design of controllers and, thus, it is possible to separately evaluate the transient and
steady-state performances. A case study will be done, finding control of a MIMO system
of four coupled tanks. A comparative study was made with other fitness functions
presented in the literature and with the LGR (Geometric Place of Roots) method. The
implemented controllers presented the expected performance, and the one found using
the proposed index presented better performance.
|
126 |
Algoritmos de inferência exata para modelos de primeira ordem. / Exact inference algorithms for first-order models.Felipe Iwao Takiyama 27 February 2014 (has links)
Este trabalho descreve a implementação de algoritmos de inferência para modelos de primeira ordem. Três algoritmos foram implementados: ve, c-fove e ac-fove. Este último e o estado da arte no calculo de probabilidades em Redes Bayesianas Relacionais e não possua nenhuma implementação disponível. O desenvolvimento foi feito segundo uma metodologia ágil que resultou em um pacote de software que pode ser utilizado em outras implementações. Mostra-se que o software criado possui o desempenho esperado em teoria, embora apresente algumas limitações. Esta dissertação contribui também com novos tópicos teóricos que complementam o algoritmo. / In this work, we describe the implementation of inference algorithms for first order models. Three algorithms were implemented: ve, c-fove and ac-fove. The latter is the state of the art in probability calculations for Relational Bayesian Networks and had no implementation available. The development was done according to an agile methodology, which resulted in a software that can be used in other packages. We show that the resulting software has the expected performance from the theory, although with some limitations. This work also contributes with new theoretical topics that complement the algorithm.
|
127 |
Algoritmos evolutivos para predição de estruturas de proteínas / Evolutionary algorithms, to proteins structures predictionTelma Woerle de Lima 01 September 2006 (has links)
A Determinação da Estrutura tridimensional de Proteínas (DEP) a partir da sua seqüência de aminoácidos é importante para a engenharia de proteínas e o desenvolvimento de novos fármacos. Uma alternativa para este problema tem sido a aplicação de técnicas de computação evolutiva. As abordagens utilizando Algoritmos Evolutivos (AEs) tem obtido resultados relevantes, porém estão restritas a pequenas proteínas, com dezenas de aminoácidos e a algumas classes de proteínas. Este trabalho propõe a investigação de uma abordagem utilizando AEs para a predição da estrutura terciária de proteínas independentemente do seu tamanho e classe. Os resultados obtidos demonstram que apesar das dificuldades encontradas a abordagem investigada constitue-se em uma alternativa em relação aos métodos clássicos de determinação da estrutura terciária das proteínas. / Protein structure determination (DEP) from aminoacid sequences is very importante to protein engineering and development of new drugs. Evolutionary computation has been aplied to this problem with relevant results. Nevertheless, Evolutionary Algorithms (EAs) can work with only proteins with few aminoacids and some protein classes. This work proposes an approach using AEs to predict protein tertiary structure independly from their size and class. The obtained results show that, despite of the difficulties that have been found, the investigate approach is a relevant alternative to classical methods to protein structure determination.
|
128 |
Estudo poliedral do problema do máximo subgrafo induzido comum / Polyhedral study of the maximum common induced subgraph problemPiva, Breno 11 1900 (has links)
O problema do Máximo Subgrafo Induzido Comum (MSIC) pertence a classe NP-difícil e possui aplicações em diversas áreas. Apesar de sua complexidade, ainda é importante conhecer soluções exatas para instâncias deste problema. Os algoritmos exatos encontrados na literatura buscam resolvê-lo através de técnicas de backtracking ou através de sua redução para o problema da Clique Máxima. Neste trabalho procuramos dar uma solução exata para o MSIC, tratando-o diretamente através da utilização de modelos de Programação Linear Inteira (PLI) e técnicas de combinatória poliédrica. Assim, realizamos um estudo teórico do poliedro do MSIC e fomos capazes de encontrar algumas desigualdades válidas fortes, inclusive com provas de que algumas delas representam facetas daquele poliedro. Adicionalmente, provamos que existe uma equivalâencia entre o modelo PLI aqui apresentado para o MSIC e uma formulação bem conhecida para o problema da Clique Máxima. Posteriormente, foram implementados algoritmos de Branch-and-Bound (B&B) e Branch-and-Cut (B&C) utilizando as desigualdades encontradas e algumas técnicas para tentar tornar os algoritmos mais eficientes. Experimentos foram executados com os algoritmos implementados neste trabalho e, também, com um algoritmo já existente para resolver o problema da Clique, chamado Cliquer. Os resultados foram comparados e, dentre os algoritmos de PLI, constatamos que o mais eficiente foi aquele que utilizou uma formulação para o MSIC que chamamos de Clique-IS, utilizando B&B e técnicas mais básicas que outros algoritmos. Este algoritmo mostrou-se mais eficiente, inclusive, que um algoritmo PLI com um modelo baseado no problema da Clique Máaxima. Este fato sugere que para uma abordagem baseada em PLI, vale a pena utilizar uma formulação do MSIC diretamente, ao invés de uma que se apóie na redução deste para o problema da Clique Máxima. Ja a comparaçao do melhor algoritmo desenvolvido neste trabalho com o Cliquer, mostrou que este último é mais eficiente. Para que um algoritmo baseado em PLI (utilizando uma formulação com as mesmas variáveis usadas por nós) tivesse alguma chance de vencer um algoritmo combinatório como o Cliquer, seria necessário conhecer mais desigualdades que estivessem ativas na solução ótima do problema._________________________________________________________________________________________ ABSTRACT: The Maximum Common Subgraph problem (MSIC) is in MV-hard and has applications in several fields. Despite its complexity, it is still important to know exact solutions for instances of this problem. The exact algorithms found in literature try to solve it through backtracking techniques or through its reduction to the Maximum Clique problem. In this work we try to give an exact solution to MSIC by addressing it directly, using Linear Integer Programming (PLI) and polyhedral combinatorics techniques. So, we performed a study of the MSIC polyhedron and we were able to find some strong valid inequalities, including some that were proven to define facets of that polyhedron. Additionally, we proved that an equivalence between the PLI model presented here for MSIC and a well known formulation for the Maximum Clique problem exists. Later, Branch-and-Bound (B&B) and Branch-and-Cut (B&C) algorithms were implemented using the inequalities found and some techniques to try to render the algorithms more efficient. Experiments were performed with the algorithms implemented in this work and, also, with an already existing algorithm to solve the Maximum Clique problem, called Cliquer. The results were compared and, among the PLI algorithms, we found that the most efficient was the one that used the formulation which we called Clique-IS, using B&B and more basic techniques than other algorithms. This algorithm was even more efficient than a PLI algorithm with a Clique-based model. This fact suggests that for a PLI approach it is worth to use a formulation based on the MSIC polyhedron instead of one based on its reduction to the Maximum Clique problem. The comparison of the best algorithm developed in this work with Cliquer, though, showed that the latest is more efficient. In order to some PLI-based algorithm (using a formulation with the same variables used by us) to have any chance of outperforming a combinatorial algorithm like Cliquer, it would be necessary to know more inequalities that are active in the problem's optimal solution.
|
129 |
Algoritmo de seleção clonal para a minimização de rearranjos em operações de pilhas de contêineresCarraro, Luiz Antonio 16 February 2012 (has links)
Made available in DSpace on 2016-03-15T19:37:43Z (GMT). No. of bitstreams: 1
Luiz Antonio Carraro.pdf: 1226702 bytes, checksum: 3cef29694a4e26f233b0aae16da69cf0 (MD5)
Previous issue date: 2012-02-16 / Universidade Presbiteriana Mackenzie / A container is a broadly used solution for the cargo storage to be transported between ports, playing a central role in international trade. Consequently, ships grew in size in order to maximize their container transportation capacity in each trip. Due to increasing demand, container terminals face the challenges of increasing their service capacity and optimizing the loading and unloading time of ships. Optimization problems, such as these, often present features that make it impossible to obtain closed analytical solutions, requiring iterative search procedures in high-dimensional spaces, or subject to a combinatorial explosion of possible solutions. This dissertation presents the proposal of a novel meta-heuristic based on the Clonal Selection Algorithm, named MRC, to minimize the number of reshuffles in operations involving piles of containers. The performance of the proposed model was evaluated through simulations and results comparison with those obtained by algorithms from the literature under the same test conditions. The results obtained show that MRC is competitive in terms of minimizing the need of reshuffles, besides presenting a reduced processing time compared with models of similar performance. / A utilização de contêineres é uma solução amplamente adotada para o armazenamento da carga a ser transportada entre portos, tornando-se de grande importância no comércio internacional e, consequentemente, navios cresceram de tamanho com o objetivo de transportar a maior quantidade possível de contêineres em cada viagem. Devido à crescente demanda, terminais de contêineres enfrentam os desafios de aumentar a sua capacidade de atendimento e otimizar os tempos de carregamento e descarregamento de navios. Problemas de otimização como estes geralmente apresentam características que inviabilizam a obtenção de soluções analíticas fechadas, requerendo processos iterativos de busca em espaços de dimensão muitas vezes elevada, ou ainda sujeitos a explosão combinatória de possíveis soluções. Esta dissertação apresenta a proposta de uma meta-heurística bioinspirada baseada no Algoritmo de Seleção Clonal para a minimização de rearranjos em operações que envolvem pilhas de contêineres, denominado MRC. O desempenho do algoritmo foi avaliado por meio de simulações e comparação dos resultados com os obtidos por algoritmos da literatura sob as mesmas condições de teste. Os resultados obtidos permitem concluir que o MRC possui resultados competitivos em termos de minimização de rearranjos, além de apresentar um tempo de processamento reduzido quando comparado aos modelos tradicionalmente empregados na solução desse tipo de problema.
|
130 |
ALGORITMO RECURSIVO BASEADO EM UMA FUNÇÃO NÃO QUADRÁTICA USANDO KERNEL / RECURSIVE ALGORITHM BASED IN A NON-QUADRATIC FUNCTION USING KERNELNogueira, Aleksandro Costa 28 February 2014 (has links)
Made available in DSpace on 2016-08-17T14:53:26Z (GMT). No. of bitstreams: 1
Dissertacao Aleksandro Costa.pdf: 1706153 bytes, checksum: 8d61027896dbab484303f78ed17b9b70 (MD5)
Previous issue date: 2014-02-28 / FUNDAÇÃO DE AMPARO À PESQUISA E AO DESENVOLVIMENTO CIENTIFICO E TECNOLÓGICO DO MARANHÃO / This work has the objective to develop an analytical model that makes prediction of the behavior of the algorithm as a function of the design parameters (step adaptation, kernel
function and its parameters).We use a non-quadratic function based on kernel, performing a nonlinear transformation of the input space filtering applied on line. Was developed and
implemented in the system for adaptive filtering based on Kernel, which provides an analysis of the behavior of KRLS algorithm as well as its properties of convergence. It applies a kernel function in the cost function from the non-recursive quadratic function of
an even power, which minimizes the error, defined as the expectation of the cumulative cost of actions taken along a sequence of steps. It appears that this approach allows the
determination of the parameters of the problem with greater reliability and robustness and lower cost compared with traditional algorithms (RLS, KRLS, RNQ) . / Este trabalho tem como objetivo desenvolver um modelo analítico que faça a previsão do comportamento do algoritmo RLS como uma função dos parâmetros de projeto (passo de adaptação, função kernel e seus parâmetros). Utiliza-se uma função não quadrática baseado em kernel, realizando uma transformação não linear do espaço de entrada aplicada à filtragem. Foi desenvolvido e implementado na redução de ruídos para a filtragem adaptativa baseada em Kernel, que fornece uma análise do comportamento do algoritmo KRLS, bem como de suas propriedades de convergência. Aplica-se uma função kernel na
função de custo a partir da função recursiva não quadrática de quarta potência, que minimiza o erro, definido como a expectativa do custo cumulativo de ações tomadas ao longo de uma sequência de passos. Verifica-se que essa abordagem possibilita a determinação dos parâmetros do problema com uma maior confiabilidade e robustez e o menor custo, quando comparado com algoritmos tradicionais (RLS, KRLS, RNQ).
|
Page generated in 0.0404 seconds