Projetos de Dissertação

A tarefa de agrupar é natural para nós, seres humanos. Métodos de agrupamento são ferramentas úteis para explorar estruturas em conjuntos de dados e têm sido muito utilizados para reconhecimento não-supervisionado de padrões. Agrupar significa organizar um conjunto de padrões (objetos, indivíduos, genes, pixels, etc.) em grupos de tal forma que padrões pertencentes a um dado grupo têm um alto grau de similaridade, enquanto que padrões pertencentes a grupos diferentes têm um alto grau de dissimilaridade (Jain, 2010). Exemplos de aplicações incluem: segmentação de mercado, segmentação de imagens, agrupar resultados de buscas na internet, agrupar páginas da internet com base em seu conteúdo, agrupar pessoas em redes sociais com base em suas preferências ou características. As técnicas de agrupamento mais populares podem ser divididas em métodos hierárquicos e métodos particionais, os quais vêm sendo desenvolvidos sob dois diferentes paradigmas: agrupamento rígido ( hard ) Jain (2010) e agrupamento difuso ( fuzzy ) Höppner et al. (1999).

Desde o desenvolvimento do algoritmo kernel K -médias (Girolami, 2002), diversos métodos de agrupamento tais como K -médias difuso (Bezdek, 1981), mapas auto-organizáveis (SOM) (Kohonen, 2013), dentre outros, têm sido modificados de modo a incorporarem funções kernel . Além disso, uma grande variedade de métodos de agrupamento baseados em kernel têm sido propostos (Filippone et al., 2008).

A essência dos métodos baseados em $\emph{kernel}$ envolve a realização de um mapeamento não-linear arbitrário $\Phi$ do espaço original $p$-dimensional $X\subset\mathbb{R}^p$ para um espaço de dimensão mais alta (possivelmente infinita), chamado espaço de características, $\mathcal{F}$. A razão para passarmos a dimensões mais altas é que em tais dimensões pode ser possível obter grupos bem definidos e linearmente separáveis. Métodos baseados em $\emph{kernel}$ possuem a vantagem de que produtos internos no espaço de características podem ser expressos por um $\emph{kernel}$ de Mercer $\mathcal{K}$, dado por $\mathcal{K}(\bm{x},\bm{x}')=\Phi(\bm{x})^\top\Phi(\bm{x}')$, onde $\bm{x},\bm{x}'\in X$, $X\subset\mathbb{R}^p$ (Mer-
cer, 1909)..

Nos algoritmos de agrupamento baseados em $\emph{kernel}$, a função $\emph{kernel}$ mede a similaridade entre dois exemplos em um espaço $p$-dimensional. Dentre as diferentes funções $\emph{kernel}$ utilizadas, o $\emph{kernel}$ gaussiano é o mais comum (Filippone et al., 2008, Graves and Pedrycz, 2010). O $\emph{kernel}$ gaussiano usualmente fornece bons resultados e tem somente um parâmetro a ser estimado. Apesar das boas características desse $\emph{kernel}$, ele é baseado na distância Euclidiana, ou seja, algoritmos baseados no $\emph{kernel}$ gaussiano assumem que os exemplos são mais provavéis de estarem distribuídos dentro de uma região hiper-esférica (em outras palavras, cada variável tem a mesma variância e não há covariância entre variáveis). Entretanto, exemplos em dois grupos diferentes são mais prováveis de estarem distribuídos dentro de duas regiões hiper-elipsoidais diferentes. A distância de Mahalanobis, que leva em consideração as correlações entre variáveis e é invariante em escala, é uma melhor escolha para lidar com regiões hiper-elipsoidais (Abe, 2005, Camps-Valls et al., 2007, Kamada and Abe, 2006, Wang et al., 2007). Ferreira and de Carvalho (2014) propuseram, sob o enfoque de kernelização da métrica, um algoritmo do tipo $\emph{kernel}$ $K$-médias baseado em um $\emph{kernel}$ de Mahalanobis adaptativo. Este $\emph{kernel}$ foi construído a partir de uma distância quadrática adaptativa definida por uma matriz simétrica positiva-definida que é modificada a cada iteração do algoritmo.%:

Contudo, o método proposto por Ferreira and de Carvalho (2014) considera apenas o caso em que a matriz de covariâncias é a mesma para todos os grupos, tendo a matriz diagonal (caso em que não há covariâncias entre as variáveis) como caso particular, ou seja, os grupos podem assumir formas hiper-elipsoidais mas há a imposição de que essas regiões sejam iguais. Nessa proposta de dissertaçao, extenderemos o algoritmo proposto por Ferreira and de Carvalho (2014) para o caso em que a matriz de covariâncias pode ser diferente para cada grupo, isto é, os grupos podem assumir formas hiper-elipsoidais e essas regiões podem ser diferentes entre os grupos. Dessa forma, uma classe muito maior de problemas de agrupamento poderá ser abordada. %Métodos de agrupamento baseados em um $\emph{kernel}$ polinomial adaptativo $(\mathcal{K}(\bm{x}_i,\bm{x}_k)=(\gamma\bm{x}_i^\top\bm{M}\bm{x}_k+\theta)^d)$ serão também explorados. Adicionalmente, algoritmos de agrupamento baseados na combinação de múltiplos $\emph{kernels}$ serão propostos. Finalmente, trabalharemos no desenvolvimento das versões difusas $(\emph{fuzzy})$ dos métodos desenvolvidos.

A distância de Mahalanobis entre uma observação $\bm{x}_i$ e o centróide global $\bm{y}$ em $\mathbb{R}^p$ é dada por

$d_{\bm{\Sigma}^{-1}}^2(\bm{x}_i,\bm{y})=(\bm{x}_i-\bm{y})^\top\bm{\Sigma}^{-1}(\bm{x}_i-\bm{y}),$

em que

${y}=\frac{1}{n}\sum_{i=1}^{n} {x}_i \quad\textrm{e}\quad {\Sigma}=\frac{1}{n}\sum_{i=1}^{n}({x}_i-{y})({x}_i-{y})^\top.$


Inspirados pela definição da distância de Mahalanobis, podemos definir um $\emph{kernel}$ adaptativo de Mahalanobis substituindo a distância euclidiana no $\emph{kernel}$ Gaussiano por uma distância tipo-Mahalanobis Camps-Valls et al. (2007):

$\mathcal{K}^{(m)}({x}_i,{x}_k)=\exp\left\{-\frac{({x}_i- {x}_k)^\top{M}({x}_i-{x}_k)}{2\sigma^2}\right\},$

onde $d^2_{\bm{M}}(\bm{x}_i,\bm{x}_k)=(\bm{x}_i-\bm{x}_k)^\top\bm{M}(\bm{x}_i-\bm{x}_k)$ é uma distância quadrática definida por uma matriz simétrica positiva-definida $\bm{M}$. Aqui, a distância de Mahalanobis é calculada entre duas observações $\bm{x}_i$ e $\bm{x}_k$ em $\mathbb{R}^p$ ao invés de uma observação $\bm{x}_i$ e o centróide global $\bm{y}$. O $\emph{kernel}$ de Mahalanobis é uma extensão do Gaussiano. Note que, fazendo $\bm{M}=\bm{I}$, onde $\bm{I}$ é a matriz identidade $p\times p$, temos o $\emph{kernel}$ Gaussiano.

Baseados no conceito de distância de Mahalanobis, podemos definir quatro distâncias quadráticas adaptativas entre uma observação $\bm{x}_i$ e o centróide do $k$-ésimo grupo $\bm{y}_k$:

$\quad\quad$ Distância quadrática adaptativa definida por uma matriz de covariâncias completa única para todos os grupos $\bm{M}_k=\bm{M}$: $d^2_{\bm{M}}(\bm{x}_i,\bm{y}_k)=(\bm{x}_i-\bm{y}_k)^\top\bm{M}(\bm{x}_i-\bm{y}_k)$, $k=1,\ldots,K$;

$\quad\quad$ Distância quadrática adaptativa definida por uma matriz de covariâncias diagonal única para todos os grupos $\bm{M}_k=\bm{M}=\textrm{diag}\{\lambda_1,\ldots,\lambda_p\}$: $d^2_{\bm{M}}(\bm{x}_i,\bm{y}_k)=(\bm{x}_i-\bm{y}_k)^\top\bm{M}(\bm{x}_i-\bm{y}_k)=\sum_{j=1}^p\lambda_j(x_{ij}-y_{kj})^2$, $k=1,\ldots,K$;

$\quad\quad$ Distância quadrática adaptativa definida por uma matriz de covariâncias completa para cada grupo $\bm{M}_k$: $d^2_{\bm{M}_k}(\bm{x}_i,\bm{y}_k)=(\bm{x}_i-\bm{y}_k)^\top\bm{M}_k(\bm{x}_i-\bm{y}_k)$, $k=1,\ldots,K$;

$\quad\quad$ Distância quadrática adaptativa definida por uma matriz de covariâncias diagonal para cada grupo $\bm{M}_k=\textrm{diag}\{\lambda_1^k,\ldots,\lambda_p^k\}$: $d^2_{\bm{M}_k}(\bm{x}_i,\bm{y}_k)=(\bm{x}_i-\bm{y}_k)^\top\bm{M}_k(\bm{x}_i-\bm{y}_k)=\sum_{j=1}^p\lambda_j^k(x_{ij}-y_{kj})^2$, $k=1,\ldots,K$.


A partir da definição dessas distâncias adaptativas quadráticas, métodos de agrupamento $\emph{fuzzy}$ baseados em diferentes versões do $\emph{kernel}$ de Mahalanobis serão propostos.

• Abe, S. (2005). Training of support vector machines with mahalanobis kernels. In Duch, W., Kacprzyk, J., Oja, E., and Zadrozny, S., editors, ICANN (2) , volume 3697 of Lecture Notes in Computer Science , pages 571576. Springer.


• Bezdek, J. C. (1981). Pattern Recognition with Fuzzy Objective Function Algorithms .


• Plenum, New York. Camps-Valls, G., Rodrigo-González, A., Muñoz-Marí, J., Gómez-Chova, L., and Calpe-Maravilla, J. (2007). Hyperspectral image classication with mahalanobis relevance vector machines. In IGARSS , pages 38023805.


• Ferreira, M. and de Carvalho, F. (2014). A kernel k-means clustering algorithm based on an adaptive mahalanobis kernel. In Neural Networks (IJCNN), 2014 International Joint Conference on , pages 18851892.


• Filippone, M., Camastra, F., Masulli, F., and Rovetta, S. (2008). A survey of kernel and spectral methods for clustering. Pattern Recognition , 41:176190. Girolami, M. (2002). Mercer kernel-based clustering in feature space. IEEE Trans. Neural Networks , 13(3):780784.


• Graves, D. and Pedrycz, W. (2010). Kernel-based fuzzy clustering and fuzzy clustering: A comparative experimental study. Fuzzy Sets and Systems , 161:522543.


• Höppner, F., Klawonn, F., Kruse, R., and Runkler, T. (1999). Fuzzy Cluster Analysis. John Wiley & Sons, Inc.


• Jain, A. K. (2010). Data clustering: 50 years beyond k-means. Pattern Recogn. Lett. ,31(8):651666.


• Kamada, Y. and Abe, S. (2006). Support vector regression using mahalanobis kernels. In ANNPR , pages 144152.


• Kohonen, T. (2013). Essentials of the self-organizing map. Neural Netw. , 37:5265.


• Mercer, J. (1909). Functions of positive and negative type and their connection with the theory of integrals equations. In Proc. R. Soc. London , volume 209, pages 415446.


• Wang, D., Yeung, D. S., and Tsang, E. C. C. (2007). Weighted mahalanobis distance kernels for support vector machines. IEEE Transactions on Neural Networks , 18(5):1453 1462.

Uma função importante do engenheiro é conceber componentes e sistemas novos, melhores, mais eficientes e de custo menor, assim como projetar planos e procedimentos com o objetivo de conseguir melhoras no funcionamento dos sistemas existentes.

Dentre os tipos de otimização estrutural, podemos destacar a : otimização dimensional, otimização de forma e a otimização topológica. Esta última por sinal, escolhida como nosso tema de pesquisa.

Os trabalhos de otimização topológica mais difundidos tratam da minimização do volume com restrição de flexibilidade, e vice versa. Entretanto, necessidades de mercado e tecnológica, pesquisadores foçaram o estudo de outras objetivos e restrições, tais como tensão, frequência natural e flambagem.

De forma geral, os problemas mais comuns referentes à otimização topológica são a dependência de malha (domínio), os mínimos locais e, principalmente, a instabilidade de tabuleiro.

Neste trabalho pretendemos encontrar uma formulação para resolver um problema de otimização de topologia com restrições mecânicas do tipo estático, usando o otimizador FAIPA (Feasible Arc Interior Point Algorithm). Este é um algoritmo de otimização não linear para resolver problemas com restrições de igualdade e desigualdade.

Inicialmente foram desenvolvidas técnicas numéricas para maximizar a rigidez de estruturas mecânicas. Este problema é considerado elementar na literatura, contudo envolve técnicas numéricas para o Método dos Elementos Finitos e de Programação Não Linear. Algumas técnicas são bastante comuns quando tratamos de otimização de topologia, como: maximização da rigidez da estrutura, dado um volume de material; minimização da massa da estrutura.

A dissertação apresentará o modelo de material linear elástico e problemas de otimização onde a variável de projeto é o módulo de elasticidade definido em cada ponto de um corpo. Para resolver numericamente o problema, emprega-se o Método dos Elementos Finitos e técnicas existentes de programação não linear. Onde, o Método dos Elementos Finitos (MEF) possibilita a obtenção dos campos de tensões, deslocamentos e deformações ao longo do domínio.

Com base nesses aspectos, nosso trabalho tem por base mostrar um algoritmo eficiente para resolver problemas de programação de topologia. Contudo, utilizaremos um método de pontos interiores por arcos viáveis, onde nossa análise se dará com a utilização do algoritmo FAIPA.

Foi desenvolvida em [1] uma técnica para problemas de programação semidefinida com resultados convergência global a pontos estacionários. Esta técnica foi aplicada problemas de programação semidefinida e otimização estrutural [2]. Esta técnica se baseia no Feasible Direction Interior Point Algorithm (FDIPA) que resolve o problema de programação não linear com restrições de igualdade e desigualdade vetoriais. Segundo a literatura [3], existem problemas de otimização onde a convergência do FDIPA não é satisfatória, devido ao efeito Maratos [4]. O efeito Maratos geralmente acontece em problemas onde a curvatura da região viável é considerável próximo a solução do problema de otimização. Este efeito não ocorre no Feasible Arc Interior Point Algorithm (FAIPA) [5].

Foi proposto, na dissertação de mestrado [6], a generalização do FAIPA para resolver problemas de programação não linear com restrições semidefinidas, a qual se denomina FAIPA-SDP. O presente projeto tem como objetivo central a melhora da velocidade de convergência do FAIPA-SDP. A pesquisa esta orientada em buscar problemas onde a curvatura da fronteira do conjunto viável, próximo da solução do problema de otimização, é significativa de modo que a convergência de técnicas por direções viáveis seja prejudicada. Este trabalho pretende indagar se o efeito Maratos acontece em algum problema de programação semidefinida não linear. Espera-se que, para estes problemas, o FAIPA-SDP tenha melhor desempenho que o FDIPA-SDP. Neste trabalho se apresentam algumas técnicas de programação não linear e exemplos de otimização estrutural onde acontece o efeito Maratos. Mostram-se alguns métodos que não apresentam este efeito como, por exemplo, o FAIPA. Este estudo pode indicar problemas que não podem ser resolvidos com técnicas de direções viáveis. Espera-se que a nova técnica proposta (FAIPA-SDP) consiga resolver estes problemas.

Referências
[1] AROZTEGUI, M. Técnicas de programação semidefinida e aplicações em otimização de material. D.Sc., COPPE/UFRJ, Rio de Janeiro, RJ, Brasil,2010.
[2] ROCHE, J. R., BAZÁN, E., HERSKOVITS, J., et al. A feasible direction algorithm for general nonlinear semidefinite programming. Structural and Multidisciplinary Optimization, ago. 2016.
[3] HERSKOVITS, J. A view on Nonlinear Optimization, pp.1-41, nov. 1995.
[4] MARATOS, N. Exact Penalty Functions Algorithms for Finite Dimensional and control Optimization Problems, Ph. D. Dissertation, Imperial college, University of London, 1978.
[5] HERSKOVITS, J., SANTOS, G. Feasible Arc Interior Point Algorithm for Nonlinear Optimization. Computational mechanics, new trends and applications, CIMNE, Barcelona, 1998.
[6] BARROS, L. N. Técnica de programação semidefinida por arco viável e aplicação à maximização da frequência natural de estruturas mecânicas. M.Sc., UFPB/CI, João Pessoa, PB, Brasil, 2017.

A Mecânica Estatística surgiu em meados de 1850, baseia-se na tentativa da utilização de modelos microscópicos, com o intuito de descrever fenômenos macroscópicos. Em geral, tais modelos, tem uma dinâmica estocástica. Ou seja, as partículas do microssistema evoluem estocasticamente. Neste trabalho estamos interessados em certos sistemas que são chamados de Cadeias de Markov à tempo continuo, onde as partículas estão localizadas em pontos do $Z^2$. Cadeias de Markov são processos estocásticos com a propriedade de o que ocorrerá com o sistema no próximo passo depende apenas do estado presente. Só consideramos que duas partículas são vizinhas se a distância entre as duas partículas for igual a um. Uma das mais famosas dinâmicas é a de kawasaki onde as partículas evoluem ao longo do tempo com taxas que são proporcionais a diferença do número de partículas vizinhas no presente e do número de partículas vizinhas no futuro. No nosso caso, a dinâmica acima é válida. Porém, uma partícula no ponto $p=(x,y)$, é permitida pular para qualquer um dos pontos: $(x-1,y)$, $(x-1,y-1)$, $(x-1,y+1)$, $(x,y-1)$, $(x,y+1)$, $(x+1,y)$, $(x+1,y+1)$, $(x+1,y-1)$. No nosso trabalho a configuração original das partículas está distribuída em um formato de cruz. Nos modelos da mecânica estatística existe uma função que é chamada por muitos por função energia (E). A cada movimento das partículas nós temos um novo valor de energia para esta nova configuração. O sistema acima é tal que busca sempre o menor estado de energia. Nesta busca o sistema pode ficar preso em um certo vale (visível no gráfico da função E) por muito tempo (tal fenômeno caracteriza um metaestado). Contudo, para um instante de tempo muito grande o sistema converge para um estado macro.
 
Nós temos dois objetivos principais: i) desenvolver um programa de computador que consigamos visualizar a evolução do nosso sistema e ii) rodar o programa um número grande de vezes, com o intuito de estimarmos as probabilidades de cada um dos macro estados (os quais vamos chamar de gotas).

Este trabalho visa desenvolver uma ferramenta computacional para resolver o problema de otimização de topologia de estruturas. Este problema de otimização tem como objetivo encontrar a melhor distribuição de material em um corpo para determinadas restrições de engenharia. Neste estudo, se apresentará um conjunto de técnicas numéricas para maximizar a rigidez de estruturas com restrições de origem mecânicas. Este problema é considerado elementar na literatura, contudo envolve técnicas numéricas para modelar o problema de elastoestática e o problema de otimização.

A dissertação apresentará o modelo de material linear elástico e problemas de otimização onde a variável de projeto é o módulo de elasticidade definido em cada ponto de um corpo. Para resolver numericamente o problema, emprega-se o Método dos Elementos Finitos e técnicas existentes de programação não linear.

O presente trabalho visa construir uma malha regular de elementos finitos para uma estrutura. Cada elemento estará associado a uma variável de projeto. Para uma estrutura bidimensional, cada elemento terá uma espessura e esta será a variável de projeto do elemento. Para uma estrutura tridimensional, considera-se o módulo de elasticidade do elemento como sendo a variável de projeto. Para encontrar a melhor distribuição de espessura/elasticidade do corpo, se empregará um modelo numérico de otimização e códigos de programação matemática.

Uma vez obtida a solução numérica da otimização, pretende-se desenvolver um procedimento para eliminar elementos com espessura/elasticidade mínimas. Posteriormente, subdividir os elementos restantes para obter uma outra malhar regular de elementos finitos. Desta forma define-se uma estrutura com outro domínio que poderá ser otimizada novamente. Pretende-se resolver este problema para um grande número de elementos.

Computação Gráfica pode ser descrita como transformações de objetos gráficos. Computação gráfica usa ferramentas de várias áreas. O intuito desse trabalho é desenvolver um trabalho que misture otimização com computação gráfica. Suponha que existam dois grupos: o vermelho e o azul. Um dos grupos é comandado por um usuário e o outro pelo computador. Suponha que esses grupos são espaçonaves inimigas. Fazem-se necessários algoritmos capazes de otimizar a vitória de um dos grupos.
Estratégia de Movimentação de objetos tridimensionais. Dada uma situação com dois grupos de espaçonaves. Um dos grupos se move a cada instante de tempo de uma forma aleatória. O segundo grupo decide cada movimento através de um problema de otimização, por exemplo, para maximizar a chance de ao atirar acertar pelo menos um dos alvos, outras estratégias devem ser abordadas. Os tempos dos tiros seguem exponenciais de mesmo parâmetro e independentes. Os instantes de tiro são variáveis exponenciais e independentes e dependem também da distância entre as espaçonaves. O objetivo principal é de construir algoritmos que otimizem a movimentação e sobrevivência de cada um dos grupos.

O estudo da dinâmica de insetos vetores surge, principalmente, da necessidade de conhecer a dinâmica da transmissão de doenças para buscar meios de controlá-las. Dentre as doenças que mais afligem a humanidade estão dengue e malária, ambas facilmente transmitidas pela picada do vetor, cuja proliferação é favorecida por más condições de saneamento, falta de informação da população e condições climáticas apropriadas.

Conforme relatório disponibilizado pela Organização Mundial de Saúde, estima-se que em 2013 houveram 198 milhões de casos de Malária, resultando em 584 mil mortes, com os índices mais altos registrados na região africana. A malária integra, juntamente com dengue, febre tifoide, febre amarela e outras, a lista de doenças negligenciadas no mundo.

Apesar dos resultados promissores obtidos pelos centros de pesquisa em relação a produção de vacinas para dengue e malária, elas até agora não se mostraram suficientemente eficazes. Em virtude dos recentes progressos na manipulação genética, uma alternativa promissora pode ser a obtenção de mosquitos geneticamente modificados refratários a doenças. A modificação genética de mosquitos transmissores da malária, por exemplo, tem sido desenvolvida com sucesso. Esses novos insetos devem acasalar com insetos selvagens e espalhar o gene que determina a interrupção no processo de transmissão.

O primeiro mosquito do gênero Anopheles refratário a malária foi produzido em 2001 usando uma técnica desenvolvida por Catterucia (2000). Nesse técnica, cientistas desenvolveram dois diferentes transgênicos Anopheles stephensi usando o promotor CP (carboxypeptidase): um deles expressando um peptídeo sintético SM1 (salivary gland and midgut binding peptide 1), Ghosh (2001), Ito (2002) e outro expressando a enzima PLA2 (phoppholipase A2) presente em veneno de abelha, Moreira (2002).

Um modelo matemático descrevendo a interação entre mosquitos selvagens e transgênicos foi proposto por Li (2004), onde os transgênicos foram agrupados sem distinção de zigosidade e sua interação com os mosquitos selvagens foi descrita por um sistema discreto de duas equações. O efeito da heterogeneidade na população de transgênicos foi levado em conta posteriormente em Li (2005). Em Wyse (2007a) foi desenvolvido um modelo matemático agrupando os mosquitos transgênicos como uma única variedade e em Wyse (2007b) foi proposto um modelo que consideraa população de transgênicos em duas variedades: homozigotos e heterozigotos; em ambos os trabalho as populações foram descritas por um sistema não-autônomo de equações diferenciais ordinárias, onde selvagens e transgênicos seguiam uma dinâmica sazonal influenciada pela pluviosidade. Diaz (2011) apresentou um modelo descrito por um sistema de equações diferenciais ordinárias onde a cada variedade do mosquito são atribuídos diferentes fitness.

Na dissertação proposta neste projeto, uma equação de conveção-difusão será acoplada ao modelo desenvolvido em Wyse (2007b) a fim de obter cenários que mostrem, além da dinâmica de propagação do transgene geração a geração, a dinâmica de espalhamento das espécies em um domínio fechado.