Algoritmos genéticos: la evolución como modelo matemático

Durante millones de años los seres vivos se han encontrado con numerosas situaciones adversas, es decir, con una enorme cantidad de problemas que han tenido que ir solucionando poco a poco mediante sucesivas adaptaciones. El éxito de la vida en innumerables entornos no es sino el reflejo de que los seres vivos han encontrado soluciones para los distintos problemas con los que se han enfrentado. Son varias las cuestiones que podemos plantearnos en relación a esta cuestión: ¿cuál es el mecanismo que ha permitido la supervivencia de los seres vivos en ambientes tan distintos?, ¿existe algún algoritmo matemático que subyazca en el mismo?, en este caso, ¿podría ser aplicable a otras situaciones y problemas? Los algoritmos genéticos son una de las herramientas que han nacido para responder a estas cuestiones.

Clasificación jerárquica ascendente con Mathematica

Hemos desarrollado el algoritmo usual de clasificación jerárquica ascendente en el sistema Mathematica. El usuario escoge la disimilitud según el tipo de datos que deba analizar: cuantitativos, cualitativos o binarios, así como el índice de agregación a utilizar. Se dispone de varias opciones para cada escogencia. Además, se ha implementado un gran número de manipulaciones sobre el árbol binario de clasificación, como el corte del árbol, la rotaciones, la dimensionalidad, el etiquetado, los colores, etc.

Repeated mapping of reefs constructed by Sabellaria spinulosa Leuckart 1849 at an offshore wind farm site

Sabellaria spinulosa reefs are considered to be sensitive and of high conservation status. This article evaluates the feasibility of using remote sensing technology to delineate S. spinulosa reefs. S. spinulosa reef habitats associated with the Thanet Offshore Windfarm site were mapped using high resolution sidescan sonar (410 kHz) and multibeam echo sounder (<1 m2) data in 2005 (baseline), 2007 (pre-construction baseline) and 2012 (post-construction). The S. spinulosa reefs were identified in the acoustic data as areas of distinct irregular texturing. Maps created using acoustic data were validated using quantitative measures of reef quality, namely tube density (as a proxy for the density of live S. spinulosa), percentage cover of S. spinulosa structures (both living and dead) and associated macrofauna derived from seabed images taken across the development site. Statistically significant differences were observed in all physical measures of S. spinulosa as well the number (S) and diversity (H׳) of associated species, derived from seabed images classified according to the presence or absence of reef, validating the use of high resolution sidescan sonar to map these important biogenic habitats. High precision mapping in the early stages allowed for the micro-siting of wind turbines in a way that caused minimal damage to S. spinulosa reefs during construction. These habitats have since recovered and expanded in extent. The surveys undertaken at the Thanet Offshore Windfarm site demonstrate the importance of repeat mapping for this emerging industry, allowing habitat enhancement to be attributed to the development whilst preventing background habitat degradation from being wrongly attributed to the development.

Multidimensional DSP Core Synthesis for FPGA

This paper, chosen as a best paper from the 2004 SAMOS Workshop on Computer Systems: describes a novel, efficient methodology for automatically creating embedded DSP computer systems. The novelty arises since now embedded electronic signal processing systems, such as radar or sonar, can be designed by anyone from the algorithm level, i.e. no low level system design experience is required, whilst still achieving low controllable implementation overheads and high real time performance. In the chosen design example, a bank of Normalised Lattice Filter (NLF) components is created which a four-fold reduction in the required processing resource with no performance decrease.

Rapid Implementation and Optimisation of DSP Systems on FPGA-Centric Hetrogeneous Platforms

This paper, chosen as a best paper from the 2005 SAMOS Workshop on Computer Systems: describes the for the first time the major Abhainn project for automated system level design of embedded signal processing systems. In particular, this describes four key novelties: novel algorithm modelling techniques for DSP systems, automated implementation realisation, algorithm transformation for system optimisation and automated inter-processor communication. This is applied to two complex systems: a radar and sonar system. In both cases technology which allows non-experts to automatically create low-overhead, high performance embedded signal processing systems is exhibited.

Assessing the Impact of Shipping Vessel Noise on Humpback Whales

The ocean is a hub of noise. Bioacoustic noise, noise from precipitation and wind, and noise from oceanic shelf slides and other geologic processes have occurred consistently as marine species have evolved over time. However, with the discovery of oceanic oil and gas reserves, submarine systems, ship propulsion and the emergence of global trade, anthropogenic sources of sound have added significant quantities of sound to the oceanic system. Shipping has been found to be the largest input of low-frequency anthropogenic noise and Humpback Whales (Megaptera novaengliae), known to be the most vocal marine species, have an auditory sensitivity that falls within the range of frequencies emitted by shipping vessels. As Humpback Whales are heavily dependent on vocalizations, for reasons relatively unconfirmed, a better understanding of why they sing and how their communication is being impacted by vessel noise is critical. Evaluating existing literature both on Humpback behavior and communication, the mechanics of their communication, sound emissions from modern ships, oceanic sound transmission, and studies regarding Humpback's exposure to other sources of low-frequency anthropogenic noise, it is clear that more research is needed to draw any causational conclusions between vessel noise and detrimental impacts on Humpback Whales. With a projected increase in global consumption and vessel traffic, there is an urgent need for further research exploring shipping noise impacts and behavioural alterations of Humpbacks. Existing research has shown changes in Humpback communication when exposed to low-frequency sonar noise, however few studies have been conducted on their communication when in close proximity to shipping vessels. In order for the impacts to be properly assessed, preliminary understanding of humpback communication, their auditory thresholds and more studies between vessel noise exposure and Humpback Whale behavior must be conducted.

Echolocation signal structure in the Megachiropteran bat Rousettus aegyptiacus Geoffroy 1810

Rousettus aegyptiacus Geoffroy 1810 is a member of the only genus of Megachiropteran bats to use vocal echolocation, but the structure of its brief, click-like signal is poorly described. Although thought to have a simple echolocation system compared to that of Microchiroptera, R. aegyptiacus is capable of good obstacle avoidance using its impulse sonar. The energy content of the signal was at least an order of magnitude smaller than in Microchiropteran bats and dolphins (approximately 4 X 10(-8) J m(-2)). Measurement of the duration, amplitude and peak frequency demonstrate that the signals of this animal are broadly similar in structure and duration to those of dolphins. Gabor functions were used to model signals and to estimate signal parameters, and the quality of the Gabor function fit to the early part of the signal demonstrates that the echolocation signals of R. aegyptiacus match the minimum spectral spread for their duration and amplitude and are thus well matched to its best hearing sensitivity. However, the low energy content of the signals and short duration should make returning echoes difficult to detect. The performance of R. aegyptincus in obstacle avoidance experiments using echolocation therefore remains something of a conundrum.

Field testing a full-scale tidal turbine Part 2: In-line Wake Effects

Recent research has shown that higher ambient turbulence leads to better wake recovery, so turbines could be installed in closer proximity in real tidal flows than might be assumed from typical towing tank tests that do not take into account turbulent inflow conditions. The standard tools to assess flow velocities in field conditions are Doppler based sonar devices, such as Acoustic Doppler Profilers (ADPs) or Acoustic Doppler Velocimeters (ADVs). The use of these devices poses some challenges when assessing the wake of a tidal turbine. While ADPs allow the three-dimensional measurement of a velocity profile over a distance, the data is calculated as a mean of three diverging beams and with low temporal resolution. ADVs can measure with higher sampling frequency but only at a single point in the flow. During the MaRINET testing of the SCHOTTELSIT turbine at the QUB tidal test site in Portaferry, Northern Ireland, ADP and ADV measurements were successfully tested.Two methods were employed for measuring the wake: firstly, with a rigidly mounted ADP and secondly, with a submerged ADV which was streamed behind the turbine. This paper presents the experimental set-up and results and discusses limitations and challenges of the two methods used.

Áquila Earthquake (2009): influence of seismic source model and structure to modeling the strong ground motions

O sismo, ocorrido em 6 de Abril de 2009 (Mw 6,3) junto à cidade de Áquila (Itália), provocou uma grande destruição. Uma das consequências deste evento foi o impacto na opinião pública em torno da capacidade científica para a estimação da perigosidade sísmica e a necessidade de criação de sistemas de alerta sísmico. A determinação dos mecanismos de fonte sísmica de eventos sísmicos ocorridos e registados permite melhores caracterizações dos movimentos sísmicos para uma determinada área de estudo e consequentemente melhores cenários de risco. Se a região em estudo possuir propriedades físicas específicas e muito distintas de local para local, capazes de provocar alterações locais dos movimentos sísmicos (efeitos de sítio), torna-se imperativo uma caracterização bem definida do meio de propagação das ondas sísmicas de forma a poder sintetizar informação capaz de contribuir para a boa estimação da perigosidade sísmica. No âmbito deste trabalho pretende-se estudar a influência do mecanismo de fonte sísmica e da estrutura na modelação de movimentos sísmicos no caso de Áquila. A metodologia adoptada consiste na determinação da distribuição de deslizamentos sobre o plano de falha e utilização desta informação na modelação de sismogramas sintéticos (com recurso ao algoritmo E3D). Será igualmente estabelecida uma comparação de resultados considerando-se um meio com e sem bacia e considerando-se uma fonte pontual e uma fonte extensa.

Geometric optimization on visibility problems: metaheuristic and exact solutions

Os problemas de visibilidade têm diversas aplicações a situações reais. Entre os mais conhecidos, e exaustivamente estudados, estão os que envolvem os conceitos de vigilância e ocultação em estruturas geométricas (problemas de vigilância e ocultação). Neste trabalho são estudados problemas de visibilidade em estruturas geométricas conhecidas como polígonos, uma vez que estes podem representar, de forma apropriada, muitos dos objectos reais e são de fácil manipulação computacional. O objectivo dos problemas de vigilância é a determinação do número mínimo de posições para a colocação de dispositivos num dado polígono, de modo a que estes dispositivos consigam “ver” a totalidade do polígono. Por outro lado, o objectivo dos problemas de ocultação é a determinação do número máximo de posições num dado polígono, de modo a que quaisquer duas posições não se consigam “ver”. Infelizmente, a maior parte dos problemas de visibilidade em polígonos são NP-difíceis, o que dá origem a duas linhas de investigação: o desenvolvimento de algoritmos que estabelecem soluções aproximadas e a determinação de soluções exactas para classes especiais de polígonos. Atendendo a estas duas linhas de investigação, o trabalho é dividido em duas partes. Na primeira parte são propostos algoritmos aproximados, baseados essencialmente em metaheurísticas e metaheurísticas híbridas, para resolver alguns problemas de visibilidade, tanto em polígonos arbitrários como ortogonais. Os problemas estudados são os seguintes: “Maximum Hidden Vertex Set problem”, “Minimum Vertex Guard Set problem”, “Minimum Vertex Floodlight Set problem” e “Minimum Vertex k-Modem Set problem”. São também desenvolvidos métodos que permitem determinar a razão de aproximação dos algoritmos propostos. Para cada problema são implementados os algoritmos apresentados e é realizado um estudo estatístico para estabelecer qual o algoritmo que obtém as melhores soluções num tempo razoável. Este estudo permite concluir que as metaheurísticas híbridas são, em geral, as melhores estratégias para resolver os problemas de visibilidade estudados. Na segunda parte desta dissertação são abordados os problemas “Minimum Vertex Guard Set”, “Maximum Hidden Set” e “Maximum Hidden Vertex Set”, onde são identificadas e estudadas algumas classes de polígonos para as quais são determinadas soluções exactas e/ou limites combinatórios.

Subspace-based techniques and applications

Este trabalho focou-se no estudo de técnicas de sub-espaço tendo em vista as aplicações seguintes: eliminação de ruído em séries temporais e extracção de características para problemas de classificação supervisionada. Foram estudadas as vertentes lineares e não-lineares das referidas técnicas tendo como ponto de partida os algoritmos SSA e KPCA. No trabalho apresentam-se propostas para optimizar os algoritmos, bem como uma descrição dos mesmos numa abordagem diferente daquela que é feita na literatura. Em qualquer das vertentes, linear ou não-linear, os métodos são apresentados utilizando uma formulação algébrica consistente. O modelo de subespaço é obtido calculando a decomposição em valores e vectores próprios das matrizes de kernel ou de correlação/covariância calculadas com um conjunto de dados multidimensional. A complexidade das técnicas não lineares de subespaço é discutida, nomeadamente, o problema da pre-imagem e a decomposição em valores e vectores próprios de matrizes de dimensão elevada. Diferentes algoritmos de préimagem são apresentados bem como propostas alternativas para a sua optimização. A decomposição em vectores próprios da matriz de kernel baseada em aproximações low-rank da matriz conduz a um algoritmo mais eficiente- o Greedy KPCA. Os algoritmos são aplicados a sinais artificiais de modo a estudar a influência dos vários parâmetros na sua performance. Para além disso, a exploração destas técnicas é extendida à eliminação de artefactos em séries temporais biomédicas univariáveis, nomeadamente, sinais EEG.

Dimensioning of multilayer optical networks

Este trabalho apresenta um estudo sobre o dimensionamento de redes ópticas, com vistas a obter um modelo de dimensionamento para redes de transporte sobreviventes. No estudo utilizou-se uma abordagem estatística em detrimento à determinística. Inicialmente, apresentam-se as principais tecnologias e diferentes arquitecturas utilizadas nas redes ópticas de transporte. Bem como os principais esquemas de sobrevivência e modos de transporte. São identificadas variáveis necessárias e apresenta-se um modelo dimensionamento para redes de transporte, tendo-se dado ênfase às redes com topologia em malha e considerando os modos de transporte opaco, transparente e translúcido. É feita uma análise rigorosa das características das topologias de redes de transporte reais, e desenvolve-se um gerador de topologias de redes de transporte, para testar a validade dos modelos desenvolvidos. Também é implementado um algoritmo genético para a obtenção de uma topologia optimizada para um dado tráfego. São propostas expressões para o cálculo de variáveis não determinísticas, nomeadamente, para o número médio de saltos de um pedido, coeficiente de protecção e coeficiente de restauro. Para as duas últimas, também é analisado o impacto do modelo de tráfego. Verifica-se que os resultados obtidos pelas expressões propostas são similares às obtidas por cálculo numérico, e que o modelo de tráfego não influencia significativamente os valores obtidos para os coeficientes. Finalmente, é demonstrado que o modelo proposto é útil para o dimensionamento e cálculo dos custos de capital de redes com informação incompleta.

Regularization and Bang-bang conjugate times in optimal control

Consideramos o problema de controlo óptimo de tempo mínimo para sistemas de controlo mono-entrada e controlo afim num espaço de dimensão finita com condições inicial e final fixas, onde o controlo escalar toma valores num intervalo fechado. Quando aplicamos o método de tiro a este problema, vários obstáculos podem surgir uma vez que a função de tiro não é diferenciável quando o controlo é bang-bang. No caso bang-bang os tempos conjugados são teoricamente bem definidos para este tipo de sistemas de controlo, contudo os algoritmos computacionais directos disponíveis são de difícil aplicação. Por outro lado, no caso suave o conceito teórico e prático de tempos conjugados é bem conhecido, e ferramentas computacionais eficazes estão disponíveis. Propomos um procedimento de regularização para o qual as soluções do problema de tempo mínimo correspondente dependem de um parâmetro real positivo suficientemente pequeno e são definidas por funções suaves em relação à variável tempo, facilitando a aplicação do método de tiro simples. Provamos, sob hipóteses convenientes, a convergência forte das soluções do problema regularizado para a solução do problema inicial, quando o parâmetro real tende para zero. A determinação de tempos conjugados das trajectórias localmente óptimas do problema regularizado enquadra-se na teoria suave conhecida. Provamos, sob hipóteses adequadas, a convergência do primeiro tempo conjugado do problema regularizado para o primeiro tempo conjugado do problema inicial bang-bang, quando o parâmetro real tende para zero. Consequentemente, obtemos um algoritmo eficiente para a computação de tempos conjugados no caso bang-bang.

Distributed coding for systems with cooperative diversity

O presente trabalho propõe-se a divulgar as mais significativas técnicas de esquemas cooperativos, de forma a ultrapassar alguns dos problemas dos sistemas móveis sem fios da próxima geração, estendendo a área de cobertura destes sistemas, assim como a sua capacidade e fiabilidade. O estudo de diversos esquemas cooperativos é efetuado em termos de capacidade e de taxa de erros, fazendo variar o número de relays e de antenas em cada elemento do sistema. Diversos algoritmos com aplicação em sistemas cooperativos são desenvolvidos e propostos ao longo desta tese, como códigos espaço-frequência aplicados de forma distribuída nos relays, para sistemas baseados na tecnologia OFDM e sob diversos cenários próximos da realidade. Os sistemas cooperativos são particularmente úteis em situações em que o caminho direto entre dois terminais não está acessível ou tem uma fraca qualidade de transmissão. Tendo este aspeto em consideração, e pretendendo ter a máxima eficiência espetral e máxima diversidade, um algoritmo com precodificação é também proposto para múltiplos relays, cada um equipado com uma ou duas antenas. A formulação matemática associada aos algoritmos propostos é apresentada, assim como a derivação da probabilidade de erro teórica. O desempenho dos sistemas assistidos por relays usando os algoritmos propostos é comparado em relação a outros esquemas cooperativos equivalentes e a esquemas não-cooperativos, considerando cenários com diferentes qualidades de canal, daí advindo importantes conclusões em relação a estes sistemas.