Dissertação

Multiagent System Optimization EVALUATED

O consenso é uma ferramenta importante em processamento distribuído. O objectivo dos algoritmos de consenso é calcular a média das medidas de cada agente da rede. À medida que estes trocam informação, a informação que guardam aproxima-se do valor da média. Algoritmos de consenso têm duas vertentes: canais de comunicação e velocidade. Devem chegar rápido ao resultado, usando o mínimo de canais. Neste trabalho, desenvolvemos algoritmos que melhoram o estado da arte nestas duas vertentes, separadamente. Na primeira parte, desenhámos um método que reduz o número de canais de comunicação tendo um impacto pequeno na velocidade de convergência. Através de técnicas de optimização convexa e da teoria da dualidade, reduziram-se o número de canais em cerca de 80%, sofrendo apenas um impacto de 5% na performance da rede. Ou seja, encontrou-se um conjunto de canais que mantêm um rápido processamento da informação. Na segunda parte, desenhámos métodos para acelerar a velocidade de convergência. Para redes assimétricas (onde a comunicação bidireccional não é garantida), este é um problema difícil de resolver, pois o raio espectral é uma função não convexa. Propusemos uma série de aproximações convexas que aumentam a velocidade de algoritmos de consenso em cerca de 45%, para o mesmo número de canais de comunicação.
Consenso, algoritmos distribuídos, redes esparsas, optimização convexa, minimização do raio espectral

Maio 19, 2016, 11:0

Publicação

Obra sujeita a Direitos de Autor

Orientação

ORIENTADOR

João Manuel de Freitas Xavier

Departamento de Engenharia Electrotécnica e de Computadores (DEEC)

Professor Auxiliar

ORIENTADOR

Rui Manuel Agostinho Dilão

Departamento de Física (DF)

Professor Auxiliar