Um método para determinação de pontos de operação com diversidade em linha digital de assinante usando balanceamento de espectro e algoritmo evolucionário

Este trabalho apresenta um método para encontrar um conjunto de pontos de operação, os quais são ótimos de Pareto com diversidade, para linhas digitais de assinante (DSL - digital subscriber line). Em diversos trabalhos encontrados na literatura, têm sido propostos algoritmos para otimização da transmissão de dados em linhas DSL, que fornecem como resultado apenas um ponto de operação para os modems. Esses trabalhos utilizam, em geral, algoritmos de balanceamento de espectro para resolver um problema de alocação de potência, o que difere da abordagem apresentada neste trabalho. O método proposto, chamado de diverseSB , utiliza um processo híbrido composto de um algoritmo evolucionário multiobjetivo (MOEA - multi-objective evolutionary algorithm), mais precisamente, um algoritmo genético com ordenamento por não-dominância (NSGA-II - Non-Dominated Sorting Genetic Algorithm II), e usando ainda, um algoritmo de balanceamento de espectro. Os resultados obtidos por simulações mostram que, para uma dada diversidade, o custo computacional para determinar os pontos de operação com diversidade usando o algoritmo diverseSB proposto é muito menor que métodos de busca de “força bruta”. No método proposto, o NSGA-II executa chamadas ao algoritmo de balanceamento de espectro adotado, por isso, diversos testes envolvendo o mesmo número de chamadas ao algoritmo foram realizadas com o método diverseSB proposto e o método de busca por força bruta, onde os resultados obtidos pelo método diverseSB proposto foram bem superiores do que os resultados do método de busca por força bruta. Por exemplo, o método de força bruta realizando 1600 chamadas ao algoritmo de balanceamento de espectro, obtém um conjunto de pontos de operação com diversidade semelhante ao do método diverseSB proposto com 535 chamadas.

Estudo e proposta de algoritmo para a minimização do corte de eólica no contexto de uma análise custo-benefício multicritério

Trabalho Final de Mestrado para obtenção do grau de Mestre em Engenharia Electrotécnica Ramo de Energia

Estudo avaliativo de um algoritmo genético auto-organizável e multiobjetivo utilizando aprendizado de máquina para aplicações de telecomunicações

This paper presents an evaluative study about the effects of using a machine learning technique on the main features of a self-organizing and multiobjective genetic algorithm (GA). A typical GA can be seen as a search technique which is usually applied in problems involving no polynomial complexity. Originally, these algorithms were designed to create methods that seek acceptable solutions to problems where the global optimum is inaccessible or difficult to obtain. At first, the GAs considered only one evaluation function and a single objective optimization. Today, however, implementations that consider several optimization objectives simultaneously (multiobjective algorithms) are common, besides allowing the change of many components of the algorithm dynamically (self-organizing algorithms). At the same time, they are also common combinations of GAs with machine learning techniques to improve some of its characteristics of performance and use. In this work, a GA with a machine learning technique was analyzed and applied in a antenna design. We used a variant of bicubic interpolation technique, called 2D Spline, as machine learning technique to estimate the behavior of a dynamic fitness function, based on the knowledge obtained from a set of laboratory experiments. This fitness function is also called evaluation function and, it is responsible for determining the fitness degree of a candidate solution (individual), in relation to others in the same population. The algorithm can be applied in many areas, including in the field of telecommunications, as projects of antennas and frequency selective surfaces. In this particular work, the presented algorithm was developed to optimize the design of a microstrip antenna, usually used in wireless communication systems for application in Ultra-Wideband (UWB). The algorithm allowed the optimization of two variables of geometry antenna - the length (Ls) and width (Ws) a slit in the ground plane with respect to three objectives: radiated signal bandwidth, return loss and central frequency deviation. These two dimensions (Ws and Ls) are used as variables in three different interpolation functions, one Spline for each optimization objective, to compose a multiobjective and aggregate fitness function. The final result proposed by the algorithm was compared with the simulation program result and the measured result of a physical prototype of the antenna built in the laboratory. In the present study, the algorithm was analyzed with respect to their success degree in relation to four important characteristics of a self-organizing multiobjective GA: performance, flexibility, scalability and accuracy. At the end of the study, it was observed a time increase in algorithm execution in comparison to a common GA, due to the time required for the machine learning process. On the plus side, we notice a sensitive gain with respect to flexibility and accuracy of results, and a prosperous path that indicates directions to the algorithm to allow the optimization problems with "η" variables

Algoritmo treansgenético na solução do problema do Caixeiro Viajante

The Traveling Purchaser Problem is a variant of the Traveling Salesman Problem, where there is a set of markets and a set of products. Each product is available on a subset of markets and its unit cost depends on the market where it is available. The objective is to buy all the products, departing and returning to a domicile, at the least possible cost defined as the summation of the weights of the edges in the tour and the cost paid to acquire the products. A Transgenetic Algorithm, an evolutionary algorithm with basis on endosymbiosis, is applied to the Capacited and Uncapacited versions of this problem. Evolution in Transgenetic Algorithms is simulated with the interaction and information sharing between populations of individuals from distinct species. The computational results show that this is a very effective approach for the TPP regarding solution quality and runtime. Seventeen and nine new best results are presented for instances of the capacited and uncapacited versions, respectively

Algoritmo genético especializado na resolução de problemas com variáveis contínuas e altamente restritos

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

Síntese evolucionária de circuitos sequenciais inspirada nos princípios da computação quântica.

Esta dissertação investiga a aplicação dos algoritmos evolucionários inspirados na computação quântica na síntese de circuitos sequenciais. Os sistemas digitais sequenciais representam uma classe de circuitos que é capaz de executar operações em uma determinada sequência. Nos circuitos sequenciais, os valores dos sinais de saída dependem não só dos valores dos sinais de entrada como também do estado atual do sistema. Os requisitos cada vez mais exigentes quanto à funcionalidade e ao desempenho dos sistemas digitais exigem projetos cada vez mais eficientes. O projeto destes circuitos, quando executado de forma manual, se tornou demorado e, com isso, a importância das ferramentas para a síntese automática de circuitos cresceu rapidamente. Estas ferramentas conhecidas como ECAD (Electronic Computer-Aided Design) são programas de computador normalmente baseados em heurísticas. Recentemente, os algoritmos evolucionários também começaram a ser utilizados como base para as ferramentas ECAD. Estas aplicações são referenciadas na literatura como eletrônica evolucionária. Os algoritmos mais comumente utilizados na eletrônica evolucionária são os algoritmos genéticos e a programação genética. Este trabalho apresenta um estudo da aplicação dos algoritmos evolucionários inspirados na computação quântica como uma ferramenta para a síntese automática de circuitos sequenciais. Esta classe de algoritmos utiliza os princípios da computação quântica para melhorar o desempenho dos algoritmos evolucionários. Tradicionalmente, o projeto dos circuitos sequenciais é dividido em cinco etapas principais: (i) Especificação da máquina de estados; (ii) Redução de estados; (iii) Atribuição de estados; (iv) Síntese da lógica de controle e (v) Implementação da máquina de estados. O Algoritmo Evolucionário Inspirado na Computação Quântica (AEICQ) proposto neste trabalho é utilizado na etapa de atribuição de estados. A escolha de uma atribuição de estados ótima é tratada na literatura como um problema ainda sem solução. A atribuição de estados escolhida para uma determinada máquina de estados tem um impacto direto na complexidade da sua lógica de controle. Os resultados mostram que as atribuições de estados obtidas pelo AEICQ de fato conduzem à implementação de circuitos de menor complexidade quando comparados com os circuitos gerados a partir de atribuições obtidas por outros métodos. O AEICQ e utilizado também na etapa de síntese da lógica de controle das máquinas de estados. Os circuitos evoluídos pelo AEICQ são otimizados segundo a área ocupada e o atraso de propagação. Estes circuitos são compatíveis com os circuitos obtidos por outros métodos e em alguns casos até mesmo superior em termos de área e de desempenho, sugerindo que existe um potencial de aplicação desta classe de algoritmos no projeto de circuitos eletrônicos.

GAIA - Uma proposta de agente inteligente acoplado a algoritmos evolucionários para ajuste dinâmico de parâmetros através de conceitos de design inteligente e lógica fuzzy

Há muitos anos, técnicas de Computação Evolucionária vem sendo aplicadas com sucesso na solução dos mais variados tipos de problemas de otimização. Na constante procura pelo ótimo global e por uma melhor exploração da superfície de busca, as escolhas para ajustar estes métodos podem ser exponencialmente complexas e requerem uma grande quantidade de intervenção humana. Estes modelos tradicionais darwinianos apóiam-se fortemente em aleatoriedade e escolhas heurísticas que se mantém fixas durante toda a execução, sem que acompanhem a variabilidade dos indivíduos e as eventuais mudanças necessárias. Dadas estas questões, o trabalho introduz a combinação de aspectos da Teoria do Design Inteligente a uma abordagem hibrida de algoritmo evolucionário, através da implementação de um agente inteligente o qual, utilizando lógica fuzzy, monitora e controla dinamicamente a população e seis parâmetros definidos de uma dada execução, ajustando-os para cada situação encontrada durante a busca. Na avaliação das proposições foi construído um protótipo sobre a implementação de um algoritmo genético para o problema do caixeiro viajante simétrico aplicado ao cenário de distância por estradas entre as capitais brasileiras, o que permitiu realizar 580 testes, simulações e comparações entre diferentes configurações apresentadas e resultados de outras técnicas. A intervenção inteligente entrega resultados que, com sucesso em muitos aspectos, superam as implementações tradicionais e abrem um vasto espaço para novas pesquisas e estudos nos aqui chamados: “Algoritmos Evolucionários Híbridos Auto-Adaptáveis”, ou mesmo, “Algoritmos Evolucionários Não-Darwinianos”.

Algorítmo evolucionário para a distribuição de produtos de petróleo por redes de polidutos

The distribution of petroleum products through pipeline networks is an important problem that arises in production planning of refineries. It consists in determining what will be done in each production stage given a time horizon, concerning the distribution of products from source nodes to demand nodes, passing through intermediate nodes. Constraints concerning storage limits, delivering time, sources availability, limits on sending or receiving, among others, have to be satisfied. This problem can be viewed as a biobjective problem that aims at minimizing the time needed to for transporting the set of packages through the network and the successive transmission of different products in the same pipe is called fragmentation. This work are developed three algorithms that are applied to this problem: the first algorithm is discrete and is based on Particle Swarm Optimization (PSO), with local search procedures and path-relinking proposed as velocity operators, the second and the third algorithms deal of two versions based on the Non-dominated Sorting Genetic Algorithm II (NSGA-II). The proposed algorithms are compared to other approaches for the same problem, in terms of the solution quality and computational time spent, so that the efficiency of the developed methods can be evaluated

Entre la epistemología y la lógica. Decisión y algoritmo de ordenación

[ES] Este trabajo en homenaje al Profesor Emilio Soldevilla trata de plantear algunos elementos de la matemática combinatoria, escogidos sin otro criterio que el de ser fácilmente visualizados para poner en evidencia el aspecto altamente significativo que poseen para la construcción de una epistemología de la economía y gestión de empresas. Y todo ello en torno a uno de los conceptos más destacados de este ámbito del conocimiento cual es el de decisión.

Algoritmo urza para el análisis de sensibilidad en problemas de programación lineal

Este artículo menciona que el algoritmo pretende llenar un hueco existente en los análisis de sensibilidad de la Programación Lineal. Estos análisis abarcan tradicionalmente a todos los coeficientes del sistema excepto a los coeficientes técnicos de las variables de la BASE, debido a la dificultad de calcular la inversa de ésta cuando se ha introducido un parámetro en uno de sus elementos.

Algoritmo para la identificación de las ganancias óptimas del algoritmo de control de posición de un mecanismo de cinemática paralela

[ES]Este trabajo presenta un algoritmo automatizado cuyo resultado es la determinación de las ganancias óptimas del lazo de control de un mecanismo de cinemática paralela. En concreto se ha aplicado al mecanismo 5R, aunque el método es válido para cualquier otro mecanismo introduciendo el modelo mecatrónico correspondiente. Permite disponer de un procedimiento para poder elegir en un futuro la combinación de motor y reductora más apropiada para un determinado mecanismo evitando realizar adquisiciones sobredimensionadas, como ocurrió con el mecanismo en cuestión.

Algoritmo de Gale-Shapley. Variaciones y alternativas

En esta memoria se trata el problema de encontrar un algoritmo que construya un emparejamiento entre dos grupos, entendiendo por emparejamiento la asignacion a cada individuo, de cada grupo, otro individuo. La situaci on inicial de la que parte el problema es la siguiente: Dos grupos, los proponentes y los propuestos, que est an formados por n individuos cada uno, siendo n la dimensi on del problema. El grupo de los proponentes es el encargado de hacer las propuestas a la hora de construir el emparejamiento. El grupo de los propuestos es el encargado de recibir y gestionar las propuestas a la hora de construir el emparejamiento. Cada individuo de cada grupo ordena en una lista, de manera decreciente, a individuos del otro grupo atendiendo a su preferencia a la hora de ser emparejado, a esta lista la llamaremos lista de preferencia del individuo, considerando el quedarse solo la opci on menos preferida de entre las aceptables. El objetivo del problema es crear un emparejamiento en el que cada pareja sea satisfactoria para los individuos que la crean en base a las preferencias de cada uno.

Paralelização em CUDA/GLSL do algoritmo SIFT para reconhecimento de íris

Neste trabalho é estudada a viabilidade de uma implementação em paralelo do algoritmo scale invariant feature transform (SIFT) para identificação de íris. Para a implementação do código foi utilizada a arquitetura para computação paralela compute unified device architecture (CUDA) e a linguagem OpenGL shading language (GLSL). O algoritmo foi testado utilizando três bases de dados de olhos e íris, o noisy visible wavelength iris image Database (UBIRIS), Michal-Libor e CASIA. Testes foram feitos para determinar o tempo de processamento para verificação da presença ou não de um indivíduo em um banco de dados, determinar a eficiência dos algoritmos de busca implementados em GLSL e CUDA e buscar valores de calibração que melhoram o posicionamento e a distribuição dos pontos-chave na região de interesse (íris) e a robustez do programa final.

Paralelização do algoritmo FDK para reconstrução 3D de imagens tomográficas usando unidades gráficas de processamento e CUDA-C

A obtenção de imagens usando tomografia computadorizada revolucionou o diagnóstico de doenças na medicina e é usada amplamente em diferentes áreas da pesquisa científica. Como parte do processo de obtenção das imagens tomográficas tridimensionais um conjunto de radiografias são processadas por um algoritmo computacional, o mais usado atualmente é o algoritmo de Feldkamp, David e Kress (FDK). Os usos do processamento paralelo para acelerar os cálculos em algoritmos computacionais usando as diferentes tecnologias disponíveis no mercado têm mostrado sua utilidade para diminuir os tempos de processamento. No presente trabalho é apresentada a paralelização do algoritmo de reconstrução de imagens tridimensionais FDK usando unidades gráficas de processamento (GPU) e a linguagem CUDA-C. São apresentadas as GPUs como uma opção viável para executar computação paralela e abordados os conceitos introdutórios associados à tomografia computadorizada, GPUs, CUDA-C e processamento paralelo. A versão paralela do algoritmo FDK executada na GPU é comparada com uma versão serial do mesmo, mostrando maior velocidade de processamento. Os testes de desempenho foram feitos em duas GPUs de diferentes capacidades: a placa NVIDIA GeForce 9400GT (16 núcleos) e a placa NVIDIA Quadro 2000 (192 núcleos).

Aplicação do algoritmo SEBAL para estimativa da evapotranspiração na mesorregião do sul goiano.

As preocupações com o uso da terra têm permeado inúmeros estudos científicos, no âmbito nacional e internacional, voltados para a avaliação dos impactos ambientais causados pelas atividades agropecuárias. Alguns processos do ciclo hidrológico, a exemplo da evapotranspiração apresentam modificações consideráveis, devido às constantes mudanças nos usos dos solos. Desta forma, o presente trabalho busca destacar o problema das rápidas e intensas mudanças no uso do solo oriundas da expansão da atividade agropecuária e seus impactos ao meio ambiente, especialmente sobre o processo da evapotranspiração regional, na mesorregião do Sul Goiano, região típica de cerrado, localizada no centro-oeste brasileiro. A aplicação do algoritmo Surface Energy Balance Algorithm for Land - SEBAL consistiu o cerne da metodologia utilizada, com vista à estimativa dos fluxos de energia e da evapotranspiração em escala regional, obtidos com base no equacionamento do balanço de energia à superfície, complementado por dados de temperatura do ar e velocidade do vento adquiridos em estações meteorológicas (PCDs) instaladas na área de estudo. Foram utilizados dados do sensor MODIS/TERRA dos anos 2006, 2007, 2008, 2009 e 2010. O algoritmo foi testado em sua forma clássica e modificado por alterações nos critérios de seleção dos pixels âncoras, utilizados no procedimento da estimativa do fluxo de calor sensível. Pode-se concluir que a alteração dos critérios influenciou positivamente os resultados obtidos e que os valores da evapotranspiração, na região estudada, indicaram a potencialidade da metodologia empregada para o monitoramento sistemático dos componentes do balanço de energia em escala regional.