The Community Program

O estimador proposto neste trabalho também visa minimizar a complexidade intrínseca da estratégia de máxima verossimilhança com a manutenção da qua- lidade das estimativas obtidas. Desta forma, o objetivo da estratégia heurística consiste em maximizar a função de verossimilhança dada pela equação (2.139). Essa maximização pode ser obtida minimizando-se o erro quadrático médio (ar- gumento do somatório), resultando, para o método heurístico, na seguinte função de verossimilhança logarítmica: Ω(˘z) = m X i=m−I (ri− UBi˘z)H(ri− UBi˘z) (2.147)

Com isso, o vetor estimado deve minimizar a equação (2.147), resultando em: ˆz(m)_Heur = min ˘z∈CN K×1Ω(˘z) (2.148) = min ˘z∈CN K×1 m X i=m−I (ri− UBi˘z)H(ri− UBi˘z)

onde, neste contexto, I é a janela de processamento. Esta função custo é o 37

Corresponde ao termo da função de máxima verossimilhança a ser minimizado.

38

negativo da função de verossimilhança logarítmica definida na equação (2.139), ignorando as constantes. Portanto, admitindo-se um conjunto de bits iniciais conhecidos (matriz dos bits de informação, B), pode-se estimar simultaneamente tanto a resposta do canal para todos os usuários quanto os respectivos atrasos indicados pelas posições em ˆz(m)

Heur (veja exemplo da equação (2.133) para o m–

ésimo intervalo de bit).

Com isso, os algoritmos heurísticos propostos visam estimar um vetor ˘z pró- ximo ou igual ao encontrado pelo estimador ML testando diversos vetores can- didatos que pertencem a um subespaço menor que o espaço de busca total, re- duzindo substancialmente o número de operações computacionais necessárias à estimação. Os resultados são apresentados no capítulo 5.

3

Algoritmos Heurísticos

Neste capítulo é realizado uma revisão dos algoritmos heurísticos, especifi- camente os de busca local e evolucionários, procurando descrever suas diversas variantes, focados na busca de soluções de problemas encontrados nos sistemas de comunicação sem fio apresentados no capítulo 2, especificamente o problema MuD e MuChE. Tais variantes incluem a codificação (mapeamento) do problema, a etapa de inicialização dos algoritmos (escolha dos parâmetros), o cálculo da função custo, a etapa de variação de varredura do espaço de busca, a etapa de reposição de candidatos e os tipos de critérios de parada dos algoritmos. Para a análise, são considerados os algoritmos de busca local 1-opt e k-opt, o de re- cozimento simulado, os algoritmos de busca Tabu de termo curto e reativo, o algoritmo genético e o algoritmo de programação evolucionária.

Os resultados de simulação são apresentados no capítulo 4 considerando aná- lise dos parâmetros na etapa de inicialização1 _{dos algoritmos visando a garantia}

de obtenção de resultados satisfatórios.

3.1

Codificação do Problema

Para qualquer método de busca heurística, o modo no qual as soluções candi- datas são codificadas é de suma importância, se não o mais importante fator no sucesso de um algoritmo heurístico. A maioria das aplicações utilizam vetores de comprimento fixo e ordem fixa de bits para codificar as soluções candidatas. Po- rém, recentemente, muitas experiências com outros tipos de codificações têm sido realizadas, incluindo codificações para problemas onde deve-se otimizar diversas características (multivariável) e codificações para problemas com valores no domí- nio dos números reais. Desta forma, a codificação do problema consiste em uma forma de representação numérica da informação a ser analisada, transformando-a em uma maneira apropriada para ser manipulada em um computador.

A codificação adequada de um problema para utilização de algoritmos heu- rísticos deve ser considerada um dos principais assuntos que podem proporcionar a construção de algoritmos eficientes. Novamente, quanto mais esta tradução for adequada ao problema, maior será a qualidade dos resultados obtidos pelos algoritmos. Cada parcela indivisível desta tradução receberá o nome de parcela individual de um candidato, podendo assumir nomes específicos dentro dos algo- ritmos, como “gene” no algoritmo genético ou posição nos algoritmos de busca local.

Vale ressaltar que a representação do candidato é completamente arbitrária, ficando sua definição de acordo com o programador e com um nível de adequação própria. No entanto, deve-se considerar algumas diretrizes para serem seguidas nesta codificação:

• A representação deve ser a mais simples possível

• Se existirem soluções candidatas proibidas, estas não devem possuir repre- sentação

• Se o problema impuser condições de algum tipo, estas devem estar implícitas dentro da representação

Basicamente, os problemas associados a este trabalho lidam com variáveis no domínio binário (problema de detecção) e com variáveis no domínio contínuo (estimativa de parâmetros).

A maioria dos pesquisadores opta pela representação binária para todos os problemas, por questões históricas e pela facilidade de construção dos algoritmos. No entanto, em muitos casos, principalmente para problemas onde os candidatos são apresentados no domínio dos números reais, esta representação pode não ser a mais adequada, pois a representação binária tem dificuldades ao lidar com múlti- plas dimensões de variáveis contínuas, especialmente quando um nível de precisão muito grande é requerido. Deve-se considerar também que a codificação binária facilita a implementação em linguagem computacional e consequentemente em hardware, explorando de maneira eficiente a capacidade dos processadores digi- tais, pois esses realizam operações na forma binária. Além disso, a complexidade e resolução podem ser controladas pelo número de bits utilizados para codificar o problema.

Mas isto pode acarretar, na codificação binária, em candidatos de tamanho muito grande (muitos bits) para atingir a precisão necessária, dificultando a ope- ração dos algoritmos. Além disso, existirá uma discretização inerente nos valores

reais quando utiliza-se codificação binária. Outro problema consiste nos abis- mos de Hamming2_{. Existem estratégias que minimizam os efeitos dos abismos de}

Hamming, como o uso de codificação Gray (DORAN, 2007).

Por isso, deve-se considerar a estrutura de cada problema para a escolha do tipo de codificação, mas recomenda-se a utilização do princípio KIS (Keep it simple, ou de forma equivalente, faça da forma mais simples) para a tomada de decisão. Em muitos casos de problemas no domínio dos reais, a representação binária mostra-se eficiente. Desta forma, uma análise mais criteriosa sobre as codificações possíveis para o problema de estimativa de parâmetros é apresentada no presente capítulo e posteriormente comparada no capítulo 5.