introducao.tex

\chapter{Introdução}
\label{ch:intro}

Existem vários tipos de problemas que possuem uma grande dificuldade na obtenção de resultados satisfatórios em um tempo factível. Esses problemas tendem a ter uma grande dimensionalidade e serem não estáticos \cite{de2004otimizaccao}. Na Natureza pode-se observar uma constante mudança no ambiente, de forma que seus integrantes tenham que se adaptar a essas mudanças para poder sobreviver. Sendo assim, na Natureza existe uma grande fonte de inspiração para o desenvolvimento de novas tecnologias para solucionar problemas dinâmicos com domínio contínuo, particularmente na Ciência da Computação, dentro da área de Computação Natural, que é responsável pela criação de diversos algoritmos \cite{de2007fundamentals}. A partir da observação e compreensão do comportamento de animais ou colônia de animais (fenômenos naturais) foram desenvolvidas várias tecnologias com diferentes aplicações \cite{rozenberg2011handbook}, pois a natureza é capaz de trabalhar com problemas de alta complexidade de forma instintiva \cite{andre2015multiple}.

A característica que vem chamando atenção para a área de otimização na computação é justamente o fato de os problemas estarem em constante alteração e uma solução ótima, que foi encontrada em um instante de tempo anterior, pode não ser mais suficientemente boa para o mesmo problema no futuro. Isso é uma questão importante, pois quando um algoritmo de busca exaustiva é aplicado a um problema complexo, o tempo para encontrar uma solução é elevado, então não é recomendado a aplicação em problemas dinâmicos em que as soluções encontradas podem perder a validade com o decorrer do tempo \cite{morrison2003performance}. Por esse motivo, para otimizar esses problemas, são utilizados os algoritmos bioinspirados, que por sua vez possuem vários operadores, características relevantes que podem ser aplicados e estudados separadamente e assim estipular a relevância de cada um.

Na literatura são encontrados diversos exemplos de algoritmos com inspiração natural podendo se basear no comportamento de uma colônia de animais por busca de alimento, na interação que eles podem realizar entre si em sua colônia, ou até na própria evolução das espécies. Uma das primeiras meta heurísticas inspiradas na natureza, em especial na Biologia, são os Algoritmos Genéticos (\textit{Genetic Algorithms}) \cite{holland1975adaptation}. Esta abordagem se baseia na teoria da evolução proposta por Darwin em que os indivíduos mais bem adaptados tem maiores chances de sobreviver e passar seu material genético adiante. Essa classe de algoritmos é chamada de computação evolucionária e é composta por algoritmos evolucionários (\textit{Evolutionary Algorithms} - EA). Outro algoritmo que entra nessa classe é o de Evolução Diferencial (\textit{Diferential Evolution} - DE), que também possui uma rotina de seleção, cruzamento e mutação.

Dentre outros algoritmos bioinspirados existe uma classe que se baseia no comportamento simples de cada indivíduo separadamente e que em conjunto pode-se gerar um comportamento mais complexo, ou seja, um comportamento emergente. Essa classe é chamada de algoritmos de Inteligência de Enxame (\textit{Swarm Inteligence} - SI) \cite{parpinelli2011new}. Entre eles pode-se citar algoritmos que têm sua aplicação em problemas contínuos, como o algoritmo baseado no comportamento de uma colônia de bactérias na busca por alimentos, o \textit{Biomimicry of Bacterial Foraging Algorithm} (BFA) \cite{passino2002biomimicry}; e o algoritmo baseado no comportamento das colônias de vaga-lumes e sua bioluminescência que guia os outros vaga-lumes no espaço de busca, o \textit{Firefly Algorthm} \cite{firefly}. Existem algoritmos inspirados no comportamento coordenado do movimento de cardumes de peixes e de revoada de pássaros, o Algoritmo de Otimização por Enxame de Partículas (\textit{Partical Swarm Optimization}, PSO) \cite{pso}. Há também algoritmos que misturam operadores de colônia de animais diferentes, como uma versão do PSO que usa um operador de expansão e contração de um cardume de peixes (um operador de movimentação volátil) aplicado no PSO para melhorar o desempenho em problemas dinâmicos, sendo criado uma nova versão, o \textit{Volitive} PSO \cite{cavalcanti2011hybrid}, que obteve bons resultados aplicado a essa classe de problemas.

O algoritmo que é o foco deste trabalho é o Algoritmo de Otimização por Enxame de Partículas por Clãs (\textit{Clan Partical Swarm Optimization}, CPSO) \cite{ferreira2009clan}, uma versão baseada no PSO que utiliza sub-populações chamadas de clãs e seleciona líderes nesses clãs para uma troca de informações. As suas principais características são sua simplicidade (utilizando as características do PSO padrão em cada um dos clãs) e conseguir manter o rastreamento de vários pontos no espaço de busca ao mesmo tempo.

A literatura apresenta uma vasta quantidade de trabalhos que estudam a aplicação desses algoritmos bioinspirados em problemas dinâmicos com domínio contínuo. Entre eles pode-se citar a aplicação do Algoritmo de Evolução diferencial com as versões baseadas em aglomeração (\textit{Crowding-based DE} CDE), baseado em compartilhamento (\textit{Sharing-based DE} ShDE) \cite{thomsen2004multimodal}, e a versão baseada em espécies (\textit{Species-based DE} SDE) \cite{li2005efficient}. Essas versões do DE foram estudadas e comparadas para que o \textit{Crowding-based local Differential Evolution with Speciation-based Memory} (ClDES) fosse desenvolvido utilizando seus pontos positivos. Na área de Inteligência de enxames são encontrados várias versões do PSO, como por exemplo: \textit{Dynamic Species-Based Particle Swarm Optimizer} DSPSO \cite{parrott2006locating} e o \textit{Clustering Particle Swarm Optimizer} CPSO \cite{yang2010clustering}. Existe também os algoritmos de (\textit{Dynamic Bacterial Foraging Algorithm} - DBFA) proposto por \cite{passino2002biomimicry} e o \textit{Multiswarm Based Firefly Algorithm} proposto por \cite{farahani2011multiswarm}.

Como não se pode ter uma solução ótima a todo momento em problemas dinâmicos, o tempo de execução é considerado como uma unidade discreta. Geralmente um dos fatores limitantes em uma aplicação acaba sendo o tempo de execução sendo necessário manter um equilíbrio entre a qualidade da solução e o tempo de execução do algoritmo \cite{li2006new}. Apesar dos algoritmos bioinspirados serem capazes de encontrar boas soluções para problemas reais, eles tendem a perder a eficiência quando aplicados a problemas de larga escala. Esta característica indesejável é conhecida por “maldição da dimensionalidade” (\textit{curse of dimensionality}) \cite{bellman2015applied}. Isso ocorre devido ao crescimento exponencial do espaço de busca de acordo com as dimensões do problema.

O grande número de dimensões aumenta a dificuldade dos algoritmos em manter soluções aceitáveis. A qualidade da otimização de um algoritmo depende do equilíbrio dos componentes de diversificação e intensificação \cite{boussaid2013survey}, pois a diversificação é responsável pela exploração do espaço de busca como um todo e a intensificação é responsável pela acurácia da resposta. A natureza evoluiu para manter o equilíbrio de diversidade e na otimização é possível usar alguns componentes de controle para sua preservação. A literatura aponta diversas estratégias para este controle de diversificação, sendo algumas: \textit{fitness sharing, clearing, crowding, deterministic crowding, probabilistic crowding} e \textit{generation gap} \cite{andre2015multiple}.

Na literatura, os algoritmos bioinspirados são aplicados a diversos tipos de problemas dinâmicos, sendo eles contínuos ou discretos. Para poder avaliar os algoritmos, utiliza-se diversas funções \textit{benchmarks} \cite{moser2007review}, como por exemplo a função de Movimentação de Picos (\textit{Moving Peaks} - MP). A qualidade da solução sendo otimizada pode ser mensurada pela sua aptidão, ou seja, quão interessante é o valor encontrado e quão bem o algoritmo se adapta a uma mudança do ambiente. Assim, uma solução com uma boa aptidão (\textit{fitness}) durante o processo de evolução é considerada válida e é chamada de solução factível. Durante a otimização dos \textit{benchmarks} podem aparecer diferentes tipos de dinamismo, como por exemplo: na função objetivo; no domínio das variáveis; no número de variáveis; nas restrições; ou outros parâmetros.

O motivo da escolha do CPSO como foco do trabalho se deve ao amplo estudo que existe do PSO em problemas dinâmicos e o fato dessa versão, em clãs, funcionar do mesmo modo que o PSO canônico em cada um das subpopupações, ou seja, fácil de se aplicar operadores que já foram aplicados em outras versões do PSO. Na literatura, quando um algoritmo é aplicado em problemas dinâmicos complexos é feita uma adaptação deste algoritmo e assim é gerado uma nova versão com novas características. O CPSO por padrão já possui algumas características, como manutenção da diversidade por clãs.

Na realização desse trabalho foram estipulados objetivos para determinar os passos a serem seguidos, na próxima seção serão apresentados esses objetivos para estruturar os capítulos do trabalho.

\section{Objetivo}
\label{sec:objetivo}
%contribuição
Este trabalho tem como objetivo analisar e comparar da eficiência do CPSO e seus operadores em problemas dinâmicos com domínio contínuo. A proposta central é analisar cada um dos operados evolutivos do algoritmo e determinar a relevância de cada um para a otimização dessa classe de problemas. Para isso será feito uma análise comparativa dos algoritmos que tem relevância na otimização desses problemas, indicando os pontos positivos e negativos de cada um. Para atingir o objetivo principal alguns objetivos específicos foram traçados:

\begin{itemize}
\item Revisão bibliográfica dos conceitos da computação natural e meta heurísticas bioinspiradas;
\item Análise aprofundada do CPSO e seus operadores;
\item Revisão bibliográfica dos operadores evolutivos existentes;
\item Estudo dos algoritmos evolutivos de inteligência de enxame para verificar a relevância dos operadores existentes e realizar uma análise comparativa
\item Levantamento e descrição de funções dinâmicas para serem aplicadas nos experimentos;
\item Implementar o CPSO aplicando operadores evolutivos diversos;
\item Realizar experimentos computacionais com o algoritmo e os problemas selecionados;
\item Coleta e análise dos resultados dos experimentos.
\item Exploração dos parâmetros do algoritmo para avaliar o desempenho em vários casos.
\item Apresentar os resultados comparando com outras versões do PSO e outros algoritmos.
\end{itemize}

\section{Estrutura do Trabalho}
\label{sec:escopo}

O trabalho está organizado em 7 Capítulos, incluindo a introdução como primeiro capítulo.

No segundo capítulo é feita uma revisão da definição de intensificação e diversificação, em seguida é feito uma revisão do estado da arte dos algoritmos bioinspirados e as suas características principais, sendo separados em dois grupos: os algoritmos evolutivos e os de inteligência de enxames. Após isso é feito uma revisão da diversidade populacional e métricas encontradas na literatura. Por fim é apresentado uma definição dos problemas que serão estudados neste trabalho, esquematizando suas características principais, suas dificuldades e métodos de avaliação para o algoritmo que será utilizado para realizar a otimização.

No terceito capítulo é apresentada uma revisão dos trabalhos encontrados nessa área de pesquisa, onde pode ser analisado outras aplicações em problemas dinâmicos e com isso definir quais os pontos mais relevantes e fornecer parâmetros para a comparação dos resultados.

No quarto capítulo é descrita o modelo proposto e uma detalhação das implementações feitas para obtenção dos resultados.

No quinto capítulo terá o protocolo de experimentação utilizado junto com um sumarização dos experimentos feitos para testar os limites do algoritmo. 

No sexto capítulo será apresentado os resultados obtidos comparando com os algoritmos encontrados na literatura e os resultados de experimentos feitos alterando os parâmetros do sistema.

Por fim, no sétimo capítulo encerra-se o trabalho com uma breve revisão das principais considerações, apresentando uma discussão dos resultados obtidos com a pesquisa e aponta trabalhos futuros.