Proposta de Equalizador Cego Baseado em Algoritmos Genéticos

UNIVERSIDADE DO RIO GRANDE DO NORTEFEDERAL

UNIVERSIDADE FEDERAL DO RIO GRANDE DO NORTE

CENTRO DE TECNOLOGIA

PROGRAMA DE PÓS-GRADUAÇÃO EM ENGENHARIA ELÉTRICA E

DE COMPUTAÇÃO

Proposta de Equalizador Cego Baseado emAlgoritmos Genéticos

Caroline Albuquerque Dantas Silva

Orientador: Prof. Dr. Marcelo Augusto Costa Fernandes

Dissertação de Mestrado apresentada aoPrograma de Pós-Graduação em Engenha-ria Elérica da UFRN (Área de concentração:Engenharia de Computação) como parte dosrequisitos para obtenção do título de Mestreem Ciências.

Número de ordem PPgEE: M470Natal, RN, julho de 2016

Catalogação da Publicação na FonteUniversidade Federal do Rio Grande do Norte - Sistema de Bibliotecas

Biblioteca Central Zila Mamede / Setor de Informação e Referência

Silva, Caroline Albuquerque Dantas.Proposta de Equalizador Cego Baseado em Algoritmos Genéticos / Caroline

Albuquerque Dantas Silva. - 2016.81 f .: il.

Dissertação (mestrado) - Universidade Federal do Rio Grande do Norte. Cen-tro de Tecnologia. Programa de Pós-Graduação em Engenharia Elétrica e deComputação. Natal, RN, 2016.

Orientador: Marcelo Augusto Costa fernandes

1. Algoritmos genéticos – Dissertação. 2. Equalização cega adaptativa –Dissertação. 3. Programação linear – Dissertação. 4. Programação estocástica –Dissertação. I. Fernandes, Marcelo Augusto Costa. II. Título.

RN/UF/BCZM CDU 621.39:004.8

Proposta de Equalizador Cego Baseado emAlgoritmos Genéticos

Caroline Albuquerque Dantas Silva

Dissertação de Mestrado aprovada em 18 de julho de 2016 pela banca examinadora com-posta pelos seguintes membros:

Prof. Dr. Marcelo Augusto Costa Fernandes (orientador) . . . . . . . . DCA/UFRN

Prof. Dr. Daniel Aloise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . DCA/UFRN

Prof. Dr. Luiz Felipe de Queiroz Silveira . . . . . . . . . . . . . . . . . . . . . . DCA/UFRN

Prof. Dr. Rodrigo Pereira Ramos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . UNIVASF

Aos meus pais, Almira e João, pelainspiração de força e perseverança.

Agradecimentos

Ao meu orientador Marcelo Fernandes, pela orientação, apoio e compreensão.

Aos professores Daniel, Luiz Felipe e Rodrigo pelas valiosas sugestões e contribuiçõespara essa dissertação.

Aos meus queridos amigos e namorado, pelo amor, carinho e incentivo.

Aos demais colegas de pós-graduação pelas críticas e sugestões.

À minha família pelo apoio durante esta jornada.

À CAPES, pelo apoio financeiro.

Resumo

Esse trabalho propõe um esquema de otimização convexa, baseada em programaçãolinear e algoritmos genéticos, para equalizadores cegos aplicados a sistemas de comuni-cações digitais. Ele surgiu da necessidade crescente de melhorias nos sistemas de comu-nicação no intuito de transportar o máximo de informação possível por um meio físico deforma confiável.

O esquema proposto, ELC-GA (Equalizador Linear Cego baseado em Algoritmos

Genéticos), é caracterizado por realizar a equalização adaptativa cega do canal em blocosfixos de dados, utilizando como algoritmo adaptativo um algoritmo genético, cuja fun-ção objetivo é uma função linear com restrições, globalmente convergente. Entretanto,devido às características aleatórias do sinal modelado com interferência intersimbólica eruído aditivo branco gaussiano, a função linear utilizada passa a representar uma progra-mação linear estocástica. Nesse sentido, o uso de algoritmos genéticos é particularmenteadequado por ser capaz de buscar soluções ótimas percorrendo uma porção consideráveldo espaço de busca, que corresponde aos vários cenários estocásticos.

O trabalho também descreve os detalhes de implementação do esquema proposto e assimulações computacionais realizadas. Na análise de desempenho, os resultados do ELC-GA são comparados aos resultados de uma das mais tradicionais técnicas de equalizaçãocega, o CMA, utilizado como referência dessa análise. Os resultados obtidos são exibidose comentados segundo as métricas de análise adequadas.

As conclusões do trabalho apontam o ELC-GA como uma alternativa promissora paraequalização cega devido ao seu desempenho de equalização, que atinge a convergênciaglobal num intervalo de símbolos consideravelmente menor que a técnica usada comoreferência.

Palavras-chave: Equalização cega adaptativa, Algoritmos Genéticos, Função con-vexa, Programação linear, Programação estocástica.

Abstract

This paper proposes a convex optimization scheme based on linear programming andgenetic algorithms for the blind equalizers applied to digital communications systems.It arose from the growing need for improvements in communication systems in order totransmit as much information as possible in a physical environment reliably.

The proposed scheme, ELC-GA (Blind Linear Equalizer Linear based on Genetic

Algorithms), is characterized by performing blind adaptive channel equalization in fixedunits of data, using a genetic algorithm as adaptive algorithm, whose objective functionis a globally convergent constrained linear function. However, due to the random charac-teristics of the signal modeled with intersymbol interference and additive white Gaussiannoise, the used linear function now represents a stochastic linear programming. Accor-dingly, the use of genetic algorithms is particularly suitable for being able to get optimalsolutions covering a considerable portion of the search space, which corresponds to thevarious stochastic scenarios.

This work also describes the implementation details of the proposed scheme and theperformed computational simulations. In the performance analysis, the ELC- GA resultsare compared to the results of one of the traditional blind equalization techniques, CMA,used as reference in this analysis. The results are shown and discussed under the appro-priate metric analysis.

The conclusions of the study indicate the GA - ELC as a promising alternative to blindequalization due to its equalization performance, which reaches global convergence in aconsiderably smaller range of symbols than the technique used as reference.

Keywords: Blind equalization, Genetic Algorithms, Convex function, Linear Pro-gramming, Stochastic Programming.

Sumário

Sumário i

Lista de Figuras iii

Lista de Tabelas v

Lista de Símbolos vi

Lista de Abreviaturas vii

1 Introdução 11.1 Justificativa e motivação . . . . . . . . . . . . . . . . . . . . . . . . . . 51.2 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.3 Publicações relacionadas . . . . . . . . . . . . . . . . . . . . . . . . . . 71.4 Estrutura do documento . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2 Algoritmos Genéticos 82.1 Representação dos indivíduos . . . . . . . . . . . . . . . . . . . . . . . . 102.2 Inicialização . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.3 Avaliação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.4 Seleção . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.5 Operadores genéticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.5.1 Cruzamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.5.2 Mutação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.5.3 Elitismo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.6 Parâmetros genéticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.6.1 Tamanho da população . . . . . . . . . . . . . . . . . . . . . . . 202.6.2 Taxa de cruzamento . . . . . . . . . . . . . . . . . . . . . . . . 202.6.3 Taxa de mutação . . . . . . . . . . . . . . . . . . . . . . . . . . 202.6.4 Condição de parada . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.7 Equalização baseada em algoritmos genéticos . . . . . . . . . . . . . . . 21

i

3 Equalização Cega Adaptativa 223.1 Caracterização do canal de comunicação . . . . . . . . . . . . . . . . . . 233.2 Equalização adaptativa cega . . . . . . . . . . . . . . . . . . . . . . . . 25

4 Programação Linear Estocástica 294.1 Programação linear . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

4.1.1 Classificação das soluções . . . . . . . . . . . . . . . . . . . . . 304.1.2 Operações elementares . . . . . . . . . . . . . . . . . . . . . . . 314.1.3 Limites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324.1.4 Hipóteses da programação linear . . . . . . . . . . . . . . . . . . 32

4.2 Programação linear estocástica . . . . . . . . . . . . . . . . . . . . . . . 334.2.1 Modelo de recurso . . . . . . . . . . . . . . . . . . . . . . . . . 344.2.2 Modelo probabilístico . . . . . . . . . . . . . . . . . . . . . . . 35

4.3 Algoritmos genéticos como solucionadores de problemas estocásticos . . 36

5 Equalizador Linear Cego Baseado em GA 385.1 Equalização cega baseada em programação linear . . . . . . . . . . . . . 385.2 O esquema ELC-GA . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

5.2.1 Arquitetura do ELC-GA . . . . . . . . . . . . . . . . . . . . . . 435.2.2 Função objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . 445.2.3 O algoritmo genético . . . . . . . . . . . . . . . . . . . . . . . . 46

5.3 Algoritmo genético para resolução do problema linear estocástico . . . . 47

6 Resultados 506.1 Simulações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

6.1.1 Parâmetros das estruturas dos equalizadores . . . . . . . . . . . . 516.1.2 Parâmetros do algoritmo genético . . . . . . . . . . . . . . . . . 51

6.2 Resultados obtidos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 526.3 Análise de convergência . . . . . . . . . . . . . . . . . . . . . . . . . . 58

7 Conclusões 60

Referências bibliográficas 62

Lista de Figuras

2.1 Fluxo Geral de um algoritmo genético. . . . . . . . . . . . . . . . . . . . 92.2 Exemplos de representações de cromossomos. . . . . . . . . . . . . . . . 112.3 Esquema de geração da população inicial para problemas com restrições. 122.4 Seleção de indivíduos utilizando o método da roleta. . . . . . . . . . . . 142.5 Seleção de indivíduos utilizando o método da amostragem estocástica

uniforme. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.6 Ilustração simplificada da aplicação do operador genético de cruzamento

(cruzamento de n pontos) para representação de cromossomos por cadeiasbinárias. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.7 Ilustração simplificada do uso do operador genético de cruzamento (cru-zamento intermediário) para representação de cromossomos por vetoresde valores inteiros ou reais. . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.8 Ilustração simplificada da aplicação do operador genético de mutaçãopara representação de cromossomos por cadeias binárias. . . . . . . . . . 18

2.9 Efeito da mutação em um cromossomo de duas dimensões, codificadocom variáveis reais. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3.1 Ilustração do fenômeno de multi-percurso entre transmissor e receptor. . . 243.2 Sistema de comunicação discreto em banda base com ISI e AWGN. . . . 243.3 Estrutura de um equalizador linear de comprimento N. . . . . . . . . . . 263.4 Estrutura de um equalizador linear adaptativo cego. . . . . . . . . . . . . 26

5.1 Estrutura do algoritmo ELC-GA. . . . . . . . . . . . . . . . . . . . . . . 43

6.1 Curva de desempenho de BER de um sistema 4-QAM em função deEb/N0 relativas ao canal A, ha(k) (ver equação (6.2)). . . . . . . . . . . . 53



iii

6.4 Curva de desempenho de BER de um sistema 4-QAM em função deEb/N0 relativas ao canal B, hb(k) (ver equação (6.3)). . . . . . . . . . . . 55



6.7 Diagrama de constelação do sinal recebido para o sistema 4-QAM, usandoo canal A, ha(k) (ver equação (6.2)), com Eb/N0 = 30 dB. . . . . . . . . 57

6.8 Diagrama de constelação do sinal recebido para o sistema 16-QAM, usandoo canal A, ha(k) (ver equação (6.2)), com Eb/N0 = 30 dB. . . . . . . . . 57

6.9 Diagrama de constelação do sinal recebido para o sistema 4-QAM, usandoo canal B, hb(k) (ver equação (6.3)), com Eb/N0 = 30 dB. . . . . . . . . 58

6.10 Diagrama de constelação do sinal recebido para o sistema 16-QAM, usandoo canal B, hb(k) (ver equação (6.3)), com Eb/N0 = 30 dB. . . . . . . . . 58

Lista de Tabelas

6.1 Parâmetros utilizados nas estruturas dos equalizadores simulados. . . . . 516.2 Parâmetros fornecidos ao toolbox do Matlab para a implementação do GA. 52

v

Lista de Símbolos

a(k) Sequência de dados bidimensional transmitida pelo emissorA Alfabeto da modulação QAMdeq Atraso de equalizaçãoE[·] Operador média ou esperançaEb Energia de bit do sistemah(k) Resposta ao impulso do canalha(k) Expressão do canal Ahb(k) Expressão do canal BJCMA(w(k)) Função de custo do CMAJPL(w(k)) Função de custo do ELC-GAK Tamanho do bloco de dados processado pelo algoritmoM Tamanho do alfabeto da modulação QAMN Comprimento do equalizadorN0 Densidade espectral de potência do ruídoP Tamanho da população de indivíduos do algoritmo genéticor(k) Ruído aditivou(k) Sinal de entrada do receptorw(k) Vetor de ganhos do equalizadorx(k) Sinal de saída do canal de transmissãoa(k) Sequência estimada do sinal transmitido na saída do equalizadorγ Constante de dispersão do CMAδ(·) Função Impulsoµ Passo de adaptação do CMAρi Atenuação (ganho complexo) sofrida pelo canalτi Atraso do i-ésimo percursoτ1 Variável auxiliar introduzida na função objetivoτ2 Variável auxiliar introduzida na função objetivo

vi

Lista de Abreviaturas

AWGN Ruído Aditivo Branco Gaussiano (Additive White Gaussian Noise)BER Taxa de Erro de Bit (Bit Error Rate)BIBO Entrada Limitada, Saída Limitada (Bounded-Input Bounded-Output)CMA Algoritmo do Módulo Constante (Constant Modulus Algorithm)ELC-GA Algoritmo Equalizador Linear Cego baseado em Algoritmo GenéticoFIR Filtro de Resposta ao Impulso Finita (Finite Impulse Response Filter)GA Algortimo Genético (Genetic algorithm)HOS Estatísticas de Ordem Superior (High Order Statistics)ISI Interferência Intersimbólica (Intersymbol Interference)LP Programação Linear (Linear programming)QAM Modulação de Amplitude em Quadratura (Quadrature Amplitude Modulation)RP Problema de recurso (Recourse Problem)SOS Estatísticas de Segunda Ordem (Second Order Statistics)SP Programação Estocática (Stochastic programming)WS Solução espere-e-veja (Wait-and-See)

vii

Capítulo 1

Introdução

Os sistemas de comunicações digitais fazem parte de nosso cotidiano de tantas formasque a diversidade de suas aplicações pode passar desapercebida. Dispositivos inteligentes,smartphones e computadores conectados às redes de dados digitais, telefonia e televisãodigitais são apenas exemplos dessas aplicações. Em todos esses sistemas, uma sequênciade símbolos é gerada em um terminal de transmissão, e após passar pelo canal de comu-nicações, é captada no terminal de recepção. O objetivo de um sistema de comunicação étransferir dados a partir da fonte de informação para um determinado destino de maneiraconfiável, permitindo que a mensagem seja recebida de forma fiel à informação original.

Um dos principais problemas dos sistemas de comunicações é a introdução de ruídose distorções aos sinais pelos canais de comunicação, corrompendo a mensagem transmi-tida. O termo ruído é normalmente utilizado para designar sinais indesejáveis que tendema perturbar a transmissão e o processamento de sinais em sistemas de comunicações e so-bre os quais temos um controle incompleto [Haykin 2004]. As causas do ruído podem serexternas (por exemplo, ruído atmosférico, galáctico) ou internas ao sistema, que surgema partir de flutuações espontâneas de corrente ou tensão no circuito elétrico. Dentre asdistorções, a dispersão temporal causada pelas características não-ideais da resposta emfrequência do canal ou a transmissão multi-percurso podem causar a Interferência Inter-simbólica (ISI - Intersymbol Interference). A ISI é uma manifestação crítica de distorção,por meio da qual símbolos transmitidos antes e depois de um determinado símbolo cor-rompem a detecção desse símbolo. Todos os canais físicos, a uma taxa de dados alta osuficiente, tendem a apresentar ISI [Johnson et al. 1998]. Por isso, a ISI tem se tornadoum fator limitante em muitos ambientes de comunicação. Desse modo, receptores otimi-zados devem ser projetados para tratar conjuntamente o ruído e os efeitos dispersivos docanal [Haykin 2001b].

Para remover ou minimizar a ISI, trazendo a Taxa de Erro de Bit (BER - Bit Error

Rate) à valores aceitáveis, pode-se lançar mão de um equalizador digital de canal. Um

CAPÍTULO 1. INTRODUÇÃO 2

equalizador tem por função processar o sinal recebido pelo receptor, reduzindo os efeitosdo canal, a fim de obter um sinal o mais próximo possível do sinal transmitido. Como aISI é altamente dinâmica e muda de acordo com o ambiente, o equalizador precisa contarcom algoritmos adaptativos eficientes, que manipulam convenientemente os coeficientesdos equalizadores, objetivando a atenuação da ISI [Haykin 2001a, Haykin 2001b, Proakis2000].

O cancelamento da ISI utilizando um equalizador adaptativo tem sido estudado hávários anos pela comunidade de processamento de sinais [Proakis 2000]. Os métodosconvencionais de equalização de canal utilizam algoritmos adaptativos como o algoritmoLMS ( Least Mean Squares) e o algoritmo Gauss-Newton para determinar os coeficientesdo equalizador que minimizam a média quadrática do erro de estimativa. O erro de esti-mativa corresponde à diferença entre o símbolo transmitido e o valor estimado para essesímbolo, fornecido na saída do equalizador. Para ser possível o cálculo do erro, é neces-sária a transmissão de um sinal de referência ao receptor. Determinados os coeficientes,considera-se que o canal já esteja suficientemente equalizado, obtendo-se dessa formauma estimativa suficientemente precisa do símbolo transmitido. Nesse tipo de operação,o equalizador é denominado supervisionado. Vale salientar que esse sinal de transferênciaserve apenas para sincronia e treinamento, não carrega informação. Portanto, a necessi-dade de transmissão dos sinais de referência sacrifica consideravelmente a capacidade docanal.

Em contraste aos métodos tradicionais de equalização, os chamados métodos de equa-lização cega operam sem uma sequência de treino [Proakis 2000]. Em outras palavras,equalização cega significa a recuperação das informações sobre o sinal transmitido oucanal através da análise das características da sua saída, e alguma informação sobre o sis-tema ou a sequência transmitida, mas não a própria sequência [Haykin (Editor) 1994]. Aequalização cega é conhecida também como autodidata ou não-supervisionada.

As técnicas de equalização cega podem ser amplamente classificadas com base nasEstatísticas de Ordem Superior (HOS - High-Order Statistics) ou com base nas Esta-tísticas de Segunda Ordem (SOS - Second Order Statistics). O Algoritmo do MóduloConstante (CMA - Constant Modulus Algorithm), introduzido por [Godard 1980], é con-siderado o mais simples e o mais bem-sucedido dos algoritmos de equalização cega base-ados em HOS. Trata-se de um algoritmo de otimização baseado na técnica do GradienteDescendente. A função de custo do CMA é baseada apenas na amplitude dos sinais re-cebidos. Entretanto, essa função de otimização não converge globalmente, apresentandopontos indesejáveis de mínimos locais que podem levar a uma redução ineficiente da ISI[Godard 1980, Benveniste e Goursat 1984]. Uma visão detalhada do CMA é apresentada


em [Johnson et al. 1999].Outras abordagens semelhantes que merecem destaque são as propostas por [Sato

1975], [Benveniste et al. 1980], [Godard 1980], [Benveniste e Goursat 1984] e o “Stop-

and-go”, proposto por [Picchi e Prati 1987]. Outras abordagens envolvem não-linearidadee despendem um enorme custo computacional. O trabalho de [Tugnait et al. 2000] apre-senta um excelente tutorial sobre essas técnicas e outros métodos de equalização cega.

Os métodos de equalização cega baseados em HOS dependem principalmente da oti-mização de funções de custo não-convexas e não-lineares. Essas funções têm uma es-trutura geométrica altamente multi-modal com muitos mínimos locais. Esses métodos,em geral, são implementados usando estruturas de filtro FIR linear. Um filtro FIR linear,todavia, tem uma região de decisão convexa e, consequentemente, não é adequado paraotimizar tais funções de custo [Pandey 2004].

Buscando melhorar o desempenho dos equalizadores cegos em relação aos problemasde mínimos locais, [Kennedy e Ding 1992] propôs uma técnica de equalização cega glo-balmente convergente baseada em uma função de custo convexa para minimizar a ISI.Seguindo as orientações a respeito da função de custo convexa introduzida em [Kennedye Ding 1992], o trabalho apresentado em [Ding e Luo 2000] descreveu uma metodolo-gia em Programação Linear (LP) aplicada a equalizadores cegos, como uma alternativaao CMA. Outros trabalhos relacionados à utilização de programação linear associada aequalização cega são descritos em [Luo et al. 2002, Muhammad e Ding 2010, Jacklinet al. 2013].

No entanto, os trabalhos citados anteriormente [Kennedy e Ding 1992, Ding e Luo2000, Luo et al. 2002] sobre equalização cega baseada em programação linear foram in-completos pela falta de qualquer análise do desempenho da técnica em canais com ISI eruído aditivo branco gaussiano (AWGN). Em situações reais, o ruído do canal e a inter-ferência intersimbólica agem em conjunto, afetando o comportamento de um sistema detransmissão de dados de uma maneira combinada [Haykin 2001b].

A análise de ruído em sistemas de comunicações geralmente se baseia em uma formaparticular de ruído, chamada de ruído branco, cuja densidade espectral de potência (ouespectro de potência) é independente da frequência de operação. O ruído branco tem po-tência média infinita e, sendo assim, não é fisicamente realizável. Entretanto, contantoque a largura de banda de um processo de ruído na entrada de um sistema seja conside-ravelmente maior que a do próprio sistema, é possível modelar o processo de ruído comoo de um ruído branco. Se o ruído branco também for gaussiano, então duas amostrasquaisquer dele serão estatisticamente independentes. Em certo sentido, o ruído brancogaussiano apresenta o que há de definitivo em “aleatoriedade” [Haykin 2004]. O sinal


transmitido, ao ser adicionado de um processo aleatório que caracteriza o ruído, passa aser também um processo aleatório. Assim, as literaturas sobre programação linear supra-citadas são válidas apenas ao assumir-se um problema determinístico, que é impraticávelem muitos cenários possíveis.

Nesse sentido, o trabalho de [Fernandes 2015] estende a função proposta por [Kennedye Ding 1992] a fim de considerar também os efeitos do ruído do canal, propondo uma novafunção de restrição, e aplicando-a a algoritmos de programação linear num equalizadoradaptativo cego. [Fernandes 2015] provou que essa nova função de custo estendida é ca-paz de equalizar sinais com ISI e ruído. Entretanto, apesar dos bons resultados, algoritmosclássicos de programação linear não são indicados para cenários estocásticos.

Dentre as técnicas possíveis para equalização adaptativa, várias abordagens utilizandoAlgoritmo Genético (GA - Genetic Algorithm) foram propostas na literatura. O traba-lho de [Mohammed 2012] faz um estudo da adequação dos Algoritmos Genéticos paraequalização adaptativa. Em abordagens mais práticas, o trabalho de [Surajudeen-Bakindeet al. 2011] propõe um algoritmo adaptativo baseado em GA para equalização no domí-nio da frequência de sistemas DS-UWB (Direct Sequence Ultra Wideband), enquanto otrabalho de [Merabti e Massicotte 2014] propõe uma abordagem baseada em GA paracanais não-lineares. Para o caso particular de equalização cega adaptativa, em geral, asabordagens utilizam técnicas complementares de busca local para aumentar a capacidadede convergência do GA. O trabalho de [Gang e Yourong 2009] propõe uma abordagemsimples com GA, utilizando como função-objetivo o critério de custo do CMA. Assimcomo em [Gang e Yourong 2009], outras abordagens utilizam como base o GA e o crité-rio de custo do CMA. O algoritmo proposto em [Han et al. 2005] utiliza como técnica debusca local o Simulated Annealing, valendo-se de sua grande capacidade de convergên-cia; [Zaouche et al. 2008] utiliza-se da técnica da Busca Generalizada de Padrões (GPS)para uma otimização irrestrita; e [Liu et al. 2008] propõe Algoritmo Genético Imune Oti-mizado (IOGA), que trata-se de algoritmo genético híbrido, utilizando como gerador depopulação inicial uma Rede de Imunidade Artificial, aiNet, e onde cada indivíduo é deno-minado anticorpo. Já o trabalho de [Lin e Yamashita 2002] propõe um Algoritmo genéticohíbrido que utiliza Simplex com busca local. A população inicial é gerada usando redesRBF, e a função-objetivo é dada pela função de custo de probabilidade Bayesiana. Ocritério de Shalvi-Weinstein [Shalvi e Weinstein 1990] é utilizada como função de custona abordagem baseada em algoritmos genéticos apresentada por [Zhu 2015]. O trabalhode [Guo e Fan 2011] propõe um algoritmo de equalização cega baseada em algoritmosgenéticos e transformada de Wavelet, e segue adicionando a essa abordagem Máquina devetores de suporte [Guo et al. 2012] e Busca Tabu [Yecai Guo 2015].


1.1 Justificativa e motivação

Dentre muitos métodos de otimização hoje disponíveis o uso de algoritmos genéticosé uma opção que oferece grande flexibilidade, pois permite exploração e explotação doespaço de busca aliado ao uso de variáveis contínuas ou discretas, e oferece resultadossatisfatórios na maioria dos casos [Cantú-Paz e Goldberg 2000]. Tratam-se de uma me-taheurística inspirada na teoria da evolução das espécies, e usam as formas com que anatureza busca evolução como metáforas de seus parâmetros e operadores. Por combinartécnicas que tanto buscam explorar de forma representativa o espaço de busca, quantotécnicas para intensificar buscas em locais do espaço de busca mais promissores, estes al-goritmos são suficientemente complexos para fornecer mecanismos poderosos e robustosde busca adaptativa. Além da sua simplicidade de implementação, a aplicação em questãopode ser convertida sem maiores questões em uma aplicação paralela, a fim de melhorarseu desempenho de tempo de processamento.

Como explicado anteriormente, a questão de convergência é um problema particular-mente sensível das abordagens tradicionais para equalização cega, devido a consideráveltendência de convergência para ótimos locais desses métodos. Por conta desse problema,uma função de custo convexa baseada em programação linear foi proposta inicialmentepor [Kennedy e Ding 1992]. Ao contrário do critério de Godard [Godard 1980], presenteno Algoritmo de módulo constante e na maioria das abordagens utilizando metaheurísti-cas, essa função de custo não requer cálculo de erro, usando de forma mais eficiente osrecursos do filtro do equalizador. Entretanto, nessa abordagem em programação lineare em várias posteriores, não foram levados em consideração os efeitos do ruído sistê-mico em conjunto com a ISI. O trabalho de [Fernandes 2015] seguiu a linha proposta por[Kennedy e Ding 1992] e modificou a função de custo para considerar também os efeitosdo ruído.

Entretanto, o ruído é um processo de natureza aleatória, e a adição dele ao sinal fazcom que o sinal resultante que será tratado pelo equalizador tenha também uma carac-terística aleatória. Quando um ou mais dos elementos de dados de uma programaçãolinear é representado por uma variável aleatória, isso resulta em uma programação linearestocástica[Sen e Higle 1999]. Levando em consideração que métodos tradicionais pararesolução de problemas lineares, como apresentados em [Fernandes 2015], não são osmais adequados para abordagens com variáveis estocásticas, um método adequado deveser investigado.

Os algoritmos genéticos tem sido utilizados como ferramenta para soluções de pro-blemas de natureza estocástica nos últimos anos. [Yoshitomi et al. 2000] propõe um


algoritmo genético modificado, GAUCE (GA in uncertain environments) para resolu-ção de problemas estocásticos, onde a função objetivo e/ou restrições são osciladas deacordo com as funções de distribuição de suas variáveis aleatórias.O trabalho de [Poojarie Varghese 2008] propõe a combinação de algoritmos genéticos com simulações para re-solução de problemas estocásticos. Os algoritmos genéticos também foram utilizados emaplicações práticas com variáveis estocásticas como, por exemplo, gestão da qualidadedo ar [Ma e Zhang 2002, Qin et al. 2010], planejamento de portfólio de recursos [Wanget al. 2008] e otimização de portfólios com preços de ativos incertos [Cui et al. 2015].

Neste sentido, este trabalho contribui com a proposta de um algoritmo adaptativo paraequalização cega baseado em algoritmos genéticos com a função de custo convexa base-ada em programação linear proposta por [Fernandes 2015]. O esquema proposto, aquichamado ELC-GA (equalizador linear cego baseada em algoritmos genéticos), combina arobustez e simplicidade dos algoritmos genéticos, com uma função de custo globalmenteconvergente.

1.2 Objetivos

Com base no exposto, este trabalho tem como objetivos:

Objetivo geral

• Fornecer uma estratégia algorítmica para melhorar a qualidade da equalização for-necida por equalizadores adaptativos lineares cegos, utilizando uma abordagem ba-seada em algoritmos genéticos.

Objetivos específicos

• Desenvolver o algoritmo ELC-GA (Equalizador Linear Cego baseado em Algo-ritmo Genético);

• Realizar testes com o ELC-GA levando em consideração diferentes ambientes econfigurações;

• Comparar a qualidade das soluções fornecidas pelo ELC-GA frente à abordagemtradicional do CMA.


1.3 Publicações relacionadas

Os resultados tratados nesse documento foram descritos resumidamente em artigos, eestes foram relacionados aos seguintes eventos que seguem:

• Silva, Caroline e Marcelo Fernandes (2015), ’Proposta de Equalizador Cego Base-ado em Algoritmos Genéticos’, Escola Potiguar de Computação e suas Aplicações

(EPOCA 2015), 1(20):141-150.

• Silva, Caroline e Marcelo Fernandes (2016), ’Linear Programming Applied to theOptimization of Blind Adaptive Antenna Arrays’, XXXIV Simpósio Brasileiro de

Telecomunicações (SBrT 2016), pp. 694-698.

• Silva, Caroline e Marcelo Fernandes (2016), ’Blind Adaptive Equalizer Based onGenetic Algorithms’, XIII Encontro Nacional de Inteligência Artificial e Computa-

cional (ENIAC 2016).

1.4 Estrutura do documento

A estrutura desta dissertação consiste em sete capítulos. Este capítulo tratou de in-troduzir o problema abordado no trabalho, conceitos relevantes ao mesmo e um breveresumo da literatura sobre o assunto. O Capítulo 2, dedica-se a apresentar a otimizaçãopor Algoritmos Genéticos, detalhando seu funcionamento e operadores. Já o Capítulo 3destina-se a conceituar aspectos teóricos referentes à Equalização Cega Adaptativa. Emseguida, o Capítulo 4 dá uma visão geral sobre Programação Linear e Programação LinearEstocástica, abordando seus principais conceitos, operações e modelagens. O Capítulo 5detalha o esquema proposto, ELC-GA, mostrando os diversos aspectos de implementa-ção, como arquitetura utilizada, função de custo considerada e a abordagem do problemaatravés de algoritmos genéticos. O Capítulo 6 descreve os experimentos computacionaisrealizados e seus resultados, detalhando os canais simulados e parâmetros utilizados. Asconsiderações finais são feitas no Capítulo 7, bem como as perspectivas futuras destetrabalho.

Capítulo 2

Algoritmos Genéticos

Os algoritmos genéticos (GA) constituem métodos de busca baseados em mecanis-mos de seleção e evolução natural. Introduzidos pelo trabalho de [Holland 1962] e am-plamente popularizados através de trabalhos como o de [Goldberg 1989], objetivavamreplicar os processos utilizados pelos sistemas auto adaptativos em um contexto com-putacional. Partindo do modelo de cromossomos para representar o processo evolutivo,Holland [Holland 1973, Holland 1974] utilizou uma cadeia de símbolos binários (0,1)para representar as cadeias de ácido nucléico. O objetivo desses trabalhos era fundamen-tar uma teoria geral de adaptação robusta, mas que, contudo, foi capaz de encontrar umcaminho de grande e imediata aplicação prática na determinação de máximos e mínimosde funções matemáticas [Goldbarg e Luna 2005].

Os Algoritmos Genéticos são modelados a partir de um problema de otimização, uti-lizando uma população de representações abstratas (os cromossomos) de soluções can-didatas (os indivíduos), e evoluindo em direção às melhores soluções. Como ilustradopela Figura 2.1, essa evolução inicia-se a partir de uma população inicial de indivíduosgerados aleatoriamente ou através de uma heurística, e segue por várias gerações. Emcada geração (ou iteração do algoritmo), a função de aptidão é utilizada para avaliar todaa população. As aptidões são utilizadas para ponderar a seleção estocástica de vários in-divíduos da população atual (pais), que serão modificados ou não através de operaçõesindutoras de convergência (elitismo, cruzamento) e variabilidade (mutação) para formaruma nova população que, assim, torna-se a população atual da próxima iteração do algo-ritmo. Quando algum critério de parada é encontrado, o melhor indivíduo encontrado éretornado e o algoritmo finaliza.

É usualmente aceito que a implementação de um algoritmo genético para solução deum problema de otimização deve possuir os seguintes componentes:

• Uma representação genética das soluções viáveis do problema a ser tratado.

CAPÍTULO 2. ALGORITMOS GENÉTICOS 9

Figura 2.1: Fluxo Geral de um algoritmo genético.

• A determinação de uma população inicial de cromossomos.

• A definição de uma função de avaliação dos cromossomos.

• A definição dos operadores que vão permitir a produção de novos indivíduos e seusparâmetros.

• A definição de vários parâmetros como: regras de parada, tamanho da população, es-quema de garantia de diversidade etc.

Além dos itens supracitados, uma implementação completa de um GA envolve aindaa especificação de um número de parâmetros, tais como o número de gerações e funçãode escala.

Os Algoritmos Genéticos se diferenciam das técnicas clássicas de otimização em vá-rios aspectos, tais como:

• Operam em um conjunto de pontos (a população), e não a partir de pontos isolados;

• Operam em um espaço de soluções codificadas (cromossomos) e não diretamente noespaço de busca;

• A função objetivo e os valores fitness correspondentes são suficientes para bem executaros direcionamentos das buscas no processo de otimização;


• Usam transições probabilísticas em vez de regras determinísticas.

Os algoritmos genéticos são métodos de busca estocástica inteligente, onde os indi-víduos são representados por cromossomos e competem por recursos e probabilidade dereprodução. Os indivíduos que tiverem mais sucesso nas competições terão maior pro-babilidade de reprodução que aqueles de menor desempenho. Os genes dos indivíduosavaliados como bons se propagam através das gerações, originando proles cada vez maisadequadas [Goldbarg e Luna 2005]. Nas seções a seguir, serão detalhados os aspectosmais relevantes para uma aplicação de algoritmos genéticos.

2.1 Representação dos indivíduos

A aplicação de algoritmos genéticos a um problema de otimização deve ser iniciadacom a determinação de como as possíveis soluções para esse problema devem ser repre-sentadas, de modo que essa meta-heurística possa atuar adequadamente sobre o problema.Isso implica que, para cada representação distinta, deve haver operadores genéticos cor-respondentes.

Os algoritmos genéticos atuam sobre populações de indivíduos ou cromossomos, comcada cromossomo representando uma solução viável ao problema a ser otimizado. Umcromossomo é representado computacionalmente por meio de uma estrutura de dados,normalmente vetores de valores binários, inteiros ou reais. Naturalmente, as representa-ções cromossômicas podem ser feitas com estruturas mais complexas. Essas representa-ções correspondem, em geral, ao conjunto de parâmetros da função objetivo cuja respostadeve ser otimizada. Assim, considerando uma solução de um problema associada a umcromossomo p, este poderá ser representado na forma de um vetor com n posições, deforma que

p = (w1,w2, . . . ,wn)

em que cada componente wi representa um gene, ou seja, um parâmetro da solução obje-tivo. O espaço de busca a ser considerado pelos algoritmos genéticos corresponde a todasas configurações possíveis que possam ser assumidas por um cromossomo. Logo, se ocromossomo possui n genes, então o espaço de busca será n-dimensional. O significadodas cadeias de cromossomos é completamente livre, cabendo ao modelador concretizaro processo adaptativo e de seleção natural preconizado na estratégia. A representação deuma solução dentro de uma estrutura cromossômica pode não ser uma tarefa trivial.

A Figura 2.2 mostra várias estruturas cromossômicas que correspondem, de cima parabaixo, a uma cadeia binária, a um vetor de números reais e a um vetor de caracteres. A ca-


Figura 2.2: Exemplos de representações de cromossomos.

deia binária, desde sua introdução nos trabalhos de [Holland 1973, Holland 1974], aindaé a forma de representação mais comum. Entretanto, mesmo com sua simplicidade demanipulação, pode ser inadequada para uma série de problemas. Em termos de represen-tação de indivíduos, ainda devem ser considerados os conceitos de genótipo e de fenótipo.O genótipo representa a estrutura do cromossomo codificado, enquanto que o fenótipo de-nota o cromossomo decodificado. No primeiro exemplo da Figura 2.2, o genótipo é dadopela cadeia binária 10011101. O fenótipo, por sua vez, dependerá do problema a ser tra-tado. Em um problema de otimização numérica, o genótipo citado anteriormente teriacomo fenótipo o valor 157; já no clássico problema da mochila, o fenótipo indicaria queo primeiro, quarto, quinto, sexto e oitavo objetos deveriam ser colocados na mochila.

2.2 Inicialização

Um conjunto de soluções codificadas de acordo com a representação cromossômicadefinida corresponde a uma população de indivíduos. Os algoritmos genéticos realizammudanças evolutivas na população a cada iteração. Desse modo, cada iteração do algo-ritmo genético é chamada de geração, e cada população nesse ciclo evolutivo representao estado atual da solução do problema. O número de indivíduos que farão parte da popu-lação é um fator importante para o desempenho dos algoritmos genéticos. Quanto maioro tamanho da população, maior a parte do espaço de busca que será processada pelo al-goritmo e, portanto, maior a probabilidade do ótimo global estar entre os indivíduos dapopulação. Por outro lado, são necessários mais recursos de memória e de tempo compu-tacional para concluir o processamento.

No estágio de inicialização, deve ser gerada uma população inicial de soluções candi-


datas. Normalmente, a população inicial de indivíduos é gerada aleatoriamente ou atra-vés de algum processo heurístico. A inicialização aleatória garante grande variabilidadee cobertura do espaço de busca, embora possa contribuir para uma convergência maislenta. Já na inicialização utilizando uma heurística, a população inicial pode ser obtidaobedecendo condições de contorno previamente estabelecidas, de acordo com algum co-nhecimento prévio do problema a ser otimizado. Quanto mais restritas essas condições,mais próximos os indivíduos estarão da solução desejada e, portanto, mais rápida será aconvergência. Entretanto, se a heurística não for bem construída, a falta de variabilidadegenética pode implicar na convergência para uma solução ótima local.

Os algoritmos genéticos foram desenvolvidos inicialmente para problemas irrestri-tos. Entretanto, vários problemas são modelados com restrições. Para que a populaçãoinicial seja gerada de modo que atenda às restrições do modelo, a heurística de criaçãonormalmente começa criando um certo número de indivíduos nas fronteiras do espaçode restrições e, em seguida, gera os indivíduos restantes na região interna do espaço derestrições, buscando abranger uniformemente essa região.

Figura 2.3: Esquema de geração da população inicial para problemas com restrições.

A Figura 2.3 mostra a rotina de geração da população inicial para um problema comtrês restrições lineares, em que o espaço de restrições é indicado pela região colorida, e oscírculos de bordas sólidas e pontilhadas indicam, respectivamente, os indivíduos criadosnas fronteiras e região interna do espaço de restrição.

Como o desenvolvimento dos algoritmos genéticos está fortemente ligada à herançagenética, vale salientar que a qualidade da população inicial certamente influenciará odesempenho do algoritmo elaborado.


2.3 Avaliação

A função de aptidão, de adaptação, ou fitness dá, para cada indivíduo, uma medidado quão bem adaptado ao ambiente ele está, ou seja, as suas chances de sobreviver ede passar sua informação genética para gerações posteriores através da reprodução. Emtermos computacionais, a função de aptidão indica o quão bem uma solução candidataé capaz de resolver um problema. Dessa forma, os valores da função de aptidão sãoutilizados para dirigir o processo de busca. É imprescindível a definição apropriada destamedida de adaptação, para que o processo evolutivo seja capaz de fornecer uma soluçãoque atenda aos objetivos em questão [Goldberg 1989].

Os algoritmos genéticos sempre buscam os indivíduos com melhores aptidões. Dessemodo, quando se quer maximizar uma solução, pode-se utilizar a função de otimizaçãodiretamente como função objetivo. Entretanto, quando se trata de um problema de mi-nimização, é necessário que se utilize uma transformação na função de otimização paragarantir que os indivíduos com valor mínimo de otimização tenham máxima aptidão.

2.4 Seleção

O procedimento de seleção deve, de acordo com os princípios da teoria da evolu-ção natural de [Darwin 1859], privilegiar a escolha de indivíduos melhores avaliados, ouseja, aqueles considerados mais aptos a solucionar o problema em investigação. Segundo[Dawkins 1996], a seleção é um processo:

• Dirigido: ao contrário da mutação, que muitos acreditam ocorrer de forma aleatória, aseleção opera de forma determinística (ou próxima disso). Isto é, enquanto as muta-ções ocorrem ao acaso, um indivíduo só consegue sobreviver em um ambiente e nelese reproduzir se e somente se for capaz, graças às suas características fenotípicas, deresponder de forma adequada a todos os fenômenos de seu meio;

• Cumulativo: os benefícios do processo de seleção são mantidos de uma geração paraa outra. Este fator, combinado com a não aleatoriedade da seleção, garante a possi-bilidade de surgimento de organismos complexos como as formas de vida que hojeconhecemos. A seleção natural consiste então de um longo processo de pequenas ten-tativas e erros, onde os ganhos são sempre acumulados, de geração para geração.

Portanto tende-se, neste processo, a proliferar a produção de soluções mais aptase a extinguir indivíduos representando soluções menos aptas. Dada essa necessidade,


observa-se a grande importância da função de adequação. As técnicas de seleção maiscomuns são baseadas nos métodos da roleta, da amostragem estocástica uniforme e dotorneio. A seleção por roleta é um algoritmo estocástico no qual os indivíduos são mape-ados em seguimentos contíguos de uma linha, de modo que o tamanho do segmento decada indivíduo é dado pela seguinte função de distribuição

ϕ(ci(t)) =f (ci(t))

∑ni=1 f (ci(t))

(2.1)

em que f (ci(t)) corresponde à fitness do indivíduo ci na geração t. Um número aleató-rio é gerado e o indivíduo cujo segmento contém o número aleatório é selecionado. Oprocesso é repetido até que o número desejado de indivíduos seja alcançado. A Figura2.4 mostra um conjunto de dez indivíduos devidamente escalonados em uma linha, cujasprobabilidades de seleção foram determinadas através da Equação (2.1). Deseja-se se-lecionar 6 indivíduos e, para isso, foram realizadas seis rodadas (ou tentativas), gerandoaleatoriamente os números 0,81, 0,32, 0,96, 0,01, 0.65 e 0.42. A partir dessas rodadasforam selecionados, respectivamente, os indivíduos c6,c2,c9,c1,c5 e c3.

Figura 2.4: Seleção de indivíduos utilizando o método da roleta.

A amostragem estocástica uniforme funciona de forma semelhante ao método da ro-leta, mapeando os indivíduos em segmentos contíguos de uma linha, cujo tamanho édeterminado pela Equação (2.1). Entretanto, esse método utiliza ponteiros igualmenteespaçados cuja quantidade, Np, corresponde ao número de indivíduos que se deseja sele-cionar. A distância entre cada ponteiro é dada por 1/Np e a posição do primeiro ponteiroé dado por um número gerado aleatoriamente, no intervalo [0,1/Np]. Em um exemplosemelhante ao anterior, mostrado na Figura 2.5, deseja-se selecionar seis indivíduos dapopulação. Logo, a distância entre os ponteiros será 1/6 = 0,167. É gerado aleatoria-mente um número no intervalo [0, 0,167] cujo valor é 0,01. Assim, são selecionados osindivíduos c1,c2,c3,c4,c6 e c8. A amostragem estocástica uniforme garante uma seleçãode indivíduos mais próxima da desejada que o método da roleta.


Figura 2.5: Seleção de indivíduos utilizando o método da amostragem estocástica uni-forme.

Na seleção por torneio, um número Ntour de indivíduos é escolhido aleatoriamente dapopulação, com a mesma probabilidade. O indivíduo com maior aptidão dentre os esco-lhidos é selecionado para fazer parte da população intermediária. O processo se repeteaté que se tenham tantos indivíduos quanto necessário. O parâmetro desse método é otamanho do torneio, Ntour, que pode ter valores entre 2 e o tamanho da população, n. Umtorneio com Ntour = 1 equivale a uma seleção aleatória. Se o valor de Ntour é maior, indi-víduos menos aptos têm menores chances de serem escolhidos. A natureza probabilísticadesse processo objetiva manter a diversidade da população.

2.5 Operadores genéticos

Como qualquer algoritmo de otimização global, os algoritmos genéticos devem sercapazes de explorar novos pontos no espaço de busca, bem como realizar buscas locais emregiões promissoras. Os operadores genéticos têm por função realizar esses mecanismosde exploração do espaço de busca e intensificação de buscas locais.

2.5.1 Cruzamento

O operador de cruzamento tem a função de combinar os cromossomos dos pais, paraobter cromossomos filhos, ou offsprings, que são adicionados à população. Após a seleçãodos pares, os indivíduos são submetidos ao processo de cruzamento, onde são trocadosarbitrariamente parte da cadeia genética entre dois ou mais indivíduos selecionados parareprodução. O comprimento e as posições das partes da cadeia genética são determinadosaleatoriamente, mas são idênticos para os indivíduos selecionados. A troca de sub-cadeiasde genes ocorre de acordo com uma certa probabilidade, geralmente menor que 1. Dessemodo, existe a possibilidade da troca não ocorrer e os indivíduos selecionados permane-cerem idênticos na população seguinte.


As operações de cruzamento mais comuns são o cruzamento de n pontos, o cruza-mento uniforme e o cruzamento intermediário. O cruzamento de n pontos ocorre quandosão escolhidas k regiões dos cromossomos selecionados que, então, são divididos nessasregiões e tem seus alelos correspondentes trocados entre si. A Figura 2.6 mostra essaoperação para n = 1. Já o cruzamento uniforme compara, bit a bit, dois indivíduos se-lecionados para reprodução. Caso os valores em determinado locus coincidam, ambosdescendentes recebem este valor. Caso estes valores sejam diferentes, eles serão trocadoscom uma probabilidade fixa.

Figura 2.6: Ilustração simplificada da aplicação do operador genético de cruzamento (cru-zamento de n pontos) para representação de cromossomos por cadeias binárias.

A técnica do cruzamento intermediário pode ser utilizada por genes representados porvalores inteiros ou reais. Nessa técnica, os filhos são gerados a partir de uma média pon-derada dos pais, em que cada cromossomo pai possui um peso (ou overlap), em geralescolhido aleatoriamente, no intervalo [0,1]. Os novos cromossomos criados são encon-trados dentro de um hipercubo, chamado de espaço de valor, definido pela alocação dospais em vértices opostos (ver Figura 2.7 (a)). Se os pesos de todos os cromossomos paispossuírem o mesmo valor, então todos os filhos encontram-se na linha que une as posiçõesdos pais (ver Figura 2.7 (b)).


(a) (b)

Figura 2.7: Ilustração simplificada do uso do operador genético de cruzamento (cruza-mento intermediário) para representação de cromossomos por vetores de valores inteirosou reais.

2.5.2 Mutação

Os algoritmos genéticos podem convergir muito rapidamente para uma região espe-cífica do espaço de busca. Contudo, essa convergência pode se dar em uma região demínimos locais ao invés de mínimos globais. Para evitar esse problema, a mutação é umaoperação utilizada para explorar outras áreas do espaço de busca, mas mantendo um nívelmínimo de convergência. Nesse sentido, a mutação pode ser entendida como uma opera-ção de diversificação. Entretanto, se a mutação aplicar apenas um ruído à solução contidano cromossomo, ela age como um mecanismo de intensificação, aumentando a busca navizinhança do cromossomo original.

O operador de mutação opera sobre um único cromossomo, alterando seu materialgenético. No caso de uma representação binária de cromossomos, a mutação correspondeà simples troca de um bit pelo seu complemento. Para representação em ponto flutuante, aoperação de mutação corresponde ao acréscimo de um valor extraído de uma distribuiçãoaleatória aos genes escolhidos. Desse modo, destacam-se dois tipos de mutação, a saber,a mutação uniforme, onde o valor aleatório a ser acrescido ao gene provém de uma distri-buição constante ao longo do processo evolutivo; e a mutação não-uniforme, onde o valora ser acrescido provém de uma distribuição que depende do tempo decorrido ao longo


do processo evolutivo [Michalewicz 1996]. Um exemplo ilustrado do funcionamento dooperador mutação pode ser visto na Figura 2.8, onde o Indivíduo 1 sofre mutação no seuterceiro gene, dando origem ao Indivíduo 2.

Figura 2.8: Ilustração simplificada da aplicação do operador genético de mutação pararepresentação de cromossomos por cadeias binárias.

Mutação em cromossomos codificados com valores reais (significa) que valores cria-dos randomicamente são adicionados às variáveis com uma prioridade baixa. Para isso,define-se um tamanho do passo de mutação e a direção da mutação de modo que

cmut = c+ step · scale ·dir, (2.2)

em que c é o indivíduo selecionado para sofrer mutação, cmut é o indivíduo criado apartir do processo de mutação, step é o tamanho do passo gerado aleatoriamente, dir

corresponde a direção da mutação dentro do espaço (hipercubo) de busca do problemae scale ∈ [0,1] pode tanto representar o valor escalonado do gene a sofrer mutação emrelação às restrições associadas a ele, na qual genes com valores nas regiões de fronteirasde restrições recebem valor 1; quanto uma medida de precisão da mutação, gerada aleato-riamente, para problemas irrestritos. A Figura 2.9 mostra a geração de novos indivíduosatravés da operação de mutação, em que cada filho corresponde a um diferente passo deadaptação.

O tamanho do passo de mutação é geralmente difícil de escolher. O tamanho de passoótimo depende do problema considerado e pode variar durante o processo de otimização.Quando o tamanho do passo de mutação é pequeno, os indivíduos criados ocupam umespaço próximo do seu pai, gerando uma busca local detalhada. Sabe-se que os pequenossão frequentemente bem sucedidos, especialmente quando o indivíduo a sofrer mutaçãojá está bem adaptado. No entanto, mudanças maiores (passos de mutação grandes) geramindivíduos em regiões distantes dos seus pais, fazendo uma maior exploração do espaçode busca. Assim, quando bem sucedidas, produz bons resultados mais rapidamente. Entreesses extremos, o algoritmo de mutação deve aprender e, então, decidir de forma adapta-tiva qual caso levará aos melhores resultados.


Figura 2.9: Efeito da mutação em um cromossomo de duas dimensões, codificado comvariáveis reais.

Algoritmos adaptativos de mutação geralmente empregam pequenas subpopulaçõesde indivíduos, onde cada indivíduo gera um certo número de filhos. Apenas os melhoresindivíduos gerados são reinseridos na população original e todos os pais são substituídos.Caso o problema a ser otimizado possua restrições, essa avaliação final inclui também averificação de que o indivíduo gerado obedece à todas as restrições.

2.5.3 Elitismo

Ao se criar uma nova população por cruzamento e mutação, existe uma grande chancede que os melhores indivíduos sejam perdidos. O elitismo é um método para preservaros melhores indivíduos de uma geração para a geração seguinte, previnindo perda dasmelhores soluções já encontradas. Por isso, esse método pode aumentar rapidamente odesempenho do algoritmo genético. O elitismo normalmente opera substituindo os pioresindivíduos da nova população pelos melhores indivíduos da população atual. Assim, oelitismo pode ser entendido como mecanismo de intensificação.

2.6 Parâmetros genéticos

O desempenho de um Algoritmo Genético é fortemente influenciado pela definiçãodos parâmetros a serem utilizados, portanto é importante analisar de que maneira algunsparâmetros influenciam o comportamento dos algoritmos genéticos, para que se possa


estabelecê-los conforme as necessidades do problema e dos recursos disponíveis [Cantú-Paz e Goldberg 2000].

2.6.1 Tamanho da população

Um aspecto importante a ser considerado para o bom desempenho global e a eficiên-cia dos algoritmos genéticos refere-se ao tamanho da população inicial e da populaçãonas gerações subsequentes. Com uma população pequena, o desempenho pode cair de-vido a população fornecer uma pequena cobertura do espaço de busca do problema. Umagrande população geralmente fornece uma cobertura considerável do domínio do pro-blema, além de prevenir convergências prematuras para ótimos locais. No entanto, parase trabalhar com grandes populações, são necessários maiores recursos computacionais,ou que o algoritmo trabalhe por um período de tempo muito maior. Assim, esta medida,exceto em casos muito particulares, deve ser estabelecida empiricamente e de acordo coma disponibilidade de recursos computacionais [Goldberg 1989, Holland 1974].

2.6.2 Taxa de cruzamento

Similarmente ao que ocorre na natureza, o cruzamento é o operador genético responsá-vel pela maior parte da criação de novos indivíduos. Quanto maior a taxa de cruzamento,mais rapidamente novas estruturas serão introduzidas na população. Porém, se essa taxafor muito alta, estruturas com boas aptidões poderão ser retiradas mais rapidamente daspopulações. Com um valor baixo, o algoritmo pode se tornar lento ou estagnar.

2.6.3 Taxa de mutação

A mutação é o operador genético responsável por prevenir que a busca fique estagnadaem certas regiões do espaço de busca, além de possibilitar que qualquer ponto do espaçode busca seja atingido. Entretanto, deve-se evitar uma taxa muito alta, uma vez que abusca se torna essencialmente aleatória, prejudicando a convergência para uma soluçãoótima. Uma taxa de mutação baixa é análoga ao que acontece na natureza, onde raramentese veem mutações ou anormalidades nos indivíduos.

2.6.4 Condição de parada

Por tratar-se de problemas de otimização, a condição de parada ideal seria que o al-goritmo finalizasse sua execução assim que o ponto ótimo fosse encontrado. O problema


é que, na maioria dos casos, não se pode afirmar com certeza se um dado ponto ótimocorresponde a um ótimo global.

Como consequência, ao efetuar a análise de convergência, os algoritmos genéticoslevam em consideração a aptidão da população em relação ao objetivo. Isto significa quese na população existir um elemento que seja a resposta exata do problema, ainda assimo algoritmo não finalizará o processo de busca da solução. A finalização ou convergênciasó ocorre quando a aptidão média da população estiver suficientemente estável, ou seja,quando houver pouca variação da aptidão média da população atual em relação à anterior,indicando que a população se adaptou ao meio.

Um controle final deve ser feito de maneira obrigatória, para que os algoritmos genéti-cos não fiquem processando indefinidamente. Este controle pode ser realizado através docritério do número máximo de gerações ou do tempo limite de processamento. Entretantotodas estas metodologias possuem falhas. A convergência por diversidade genética falhaquando o algoritmo converge para um mínimo local, isto é, quando acontece convergên-cia prematura. Já o número máximo de gerações ou limite de tempo de processamentofalham quando não dão tempo suficiente ao algoritmo para investigar todo o universo debusca. Logo, esses parâmetros devem ser cuidadosamente escolhidos para que os efeitosdessas falhas sejam minimizados.

2.7 Equalização baseada em algoritmos genéticos

Dentre as inúmeras aplicações dos algoritmos genéticos, a equalização adaptativa temsido bastante abordada na literatura nos últimos anos, assim como detalhado no Capítulo1. As aplicações, em geral, buscam aproveitar a combinação de exploração do espaço debusca e capacidade de convergência dos algoritmos genéticos para melhorar o desempe-nho de algoritmos adaptativos que utilizam funções de custo que, apesar de bem estabele-cidas da literatura, apresentam baixa convergência. Apesar das melhorias de desempenhoem relação às abordagens tradicionais, a falta de uma função de custo convergente fazcom que o desempenho dessas abordagens não seja tão alto quanto se poderia esperar.Mesmo assim, os resultados demonstram a adequação do uso dos algoritmos genéticoscomo base para algoritmos de equalização adaptativos.

Capítulo 3

Equalização Cega Adaptativa

Um sistema tradicional de transmissão de dados consiste de um transmissor, um ca-nal de comunicação, e um receptor, sendo que o canal representa todas as interconexõesentre o transmissor e o receptor. Em um processo ideal de comunicação, toda a informa-ção codificada transmitida através do canal de comunicação chega inalterada ao receptor.Entretanto, em sistemas reais, o processo de transmissão de informação não ocorre deforma ideal devido às limitações físicas do sistema. Dentre essas limitações, pode-se ci-tar a potência limitada do transmissor, a sensibilidade finita do receptor, a resposta emfrequência do canal de comunicação, e o ruído inerente do sistema de comunicação. Paraas duas primeiras limitações, são necessárias melhoria nos equipamentos de transmissãoe recepção, dentro das viabilidades técnicas do projeto. Para as demais, é necessário o usode equalizadores de sinal nos receptores, que são estruturas cuja finalidade é compensarinterferências e alterações nos símbolos, minimizando seus efeitos na recepção.

Quanto ao modo de funcionamento, os equalizadores podem ser classificados comoadaptativos ou não-adaptativos. Os equalizadores não-adaptativos são dispositivos queefetuam as compensações no sinal transmitido usando configurações preestabelecidas,não sendo capazes de modificar suas condições de equalização quando necessário. Am-plamente em desuso atualmente, o funcionamento desses dispositivos pressupõe canaiscujas características de transmissão não apresentem muitas variações com o tempo.

Por outro lado, os equalizadores adaptativos são implementados com algoritmos queperiodicamente verificam as características do canal de transmissão, compensando as va-riações produzidas pelo canal nos símbolos emitidos pela fonte, dentro de suas capacida-des e limitações. Essa compensação realizada pelos equalizadores adaptativos pode serrealizada em tempo real, ou seja, a cada novo símbolo recebido do canal, é realizada umnovo cálculo dos coeficientes do equalizador, buscando o ponto ótimo de equalização; oupode ser realizada em blocos, onde esse novo cálculo de coeficientes é realizado somentequando o conjunto de símbolos acumulados vindos do canal atingem um tamanho pre-

CAPÍTULO 3. EQUALIZAÇÃO CEGA ADAPTATIVA 23

viamente estabelecido. De um modo geral, algoritmos para equalização em tempo realbuscam simplicidade e desempenho para cumprir sua função em um intervalo muito li-mitado de tempo; enquanto que os algoritmos de equalização em blocos permitem maiorcomplexidade de algoritmo, embora requeiram maior capacidade de memória para arma-zenamento de símbolos no dispositivo.

Os equalizadores adaptativos podem, ainda, ser classificados quanto à técnica paradeterminação dos valores de seus parâmetros como de equalização supervisionada ou deequalização autodidata ou cega. Na técnica de equalização supervisionada, faz-se comque periodicamente, ou quando identificada à necessidade, a fonte emita uma sequênciade símbolos que seja previamente conhecida pelo receptor ([Godard 1980, Haykin 2001a].Através de comparações entre os sinais recebidos através do canal e o sinal conhecidode treinamento, o algoritmo adaptativo pode ajustar os coeficientes do equalizador. Porestar fora do escopo desta dissertação, não serão tratados mais detalhes a respeito daequalização adaptativa supervisionada. A Seção 3.1 tratará da caracterização do canal decomunicação, bem como das interferências e alterações envolvidas nas transmissões dedados. Já a Seção 3.2 tratará com detalhes a equalização adaptativa cega.

3.1 Caracterização do canal de comunicação

A transmissão de informações por um sistema de comunicação é realizada através deum canal de comunicação. Os canais de comunicação, de acordo com o modo de trans-missão utilizado, podem ser distinguidos como baseados em propagação guiada (linhastelefônicas, cabos coaxiais, fibras ópticas etc.) e baseados em propagação livre (wi-fi,rádio móvel, satélite, entre outros).

Um canal de comunicação ideal permite a passagem de todas as componentes defrequência do sinal, realizando alterações de fase e amplitude, conforme necessário. Po-rém, em situações práticas, os canais de comunicação permitem apenas a passagem deintervalos de frequência finitos, de acordo com suas características físicas próprias. Esteaspecto acaba por provocar interferência entre os símbolos transmitidos pela fonte, cha-mada de interferência intersimbólica (ISI). Em sistemas de transmissão cujo canal é base-ado em propagação livre, além da resposta em frequência do canal, os fenômenos multi-percurso são os principais responsáveis pelo aparecimento da ISI. A Figura 3.1 ilustra deforma simplificada o fenômeno de multi-percurso entre um transmissor e um receptor noqual cada percurso pode ser caracterizado por

ρiδ(t− τi), (3.1)


em que δ(·) é a função impulso, ρi é o ganho complexo, ou seja, a atenuação sofrida pelocanal, e τi é o atraso do i-ésimo percurso, respectivamente.

ρ2δ(t-τ2)

Transmissor Receptor

ρ1δ(t-τ1)

ρ0δ(t-τ0)

obstáculos

Figura 3.1: Ilustração do fenômeno de multi-percurso entre transmissor e receptor.

Outro fenômeno que pode causar distorção nos símbolos transmitidos pela fonte é oruído inerente do sistema de comunicação. A existência de ruído no sistema de comu-nicação pode fazer com que os símbolos emitidos pela fonte sofram alterações, fazendocom que estes não sejam corretamente decodificados pelo receptor. Embora seja possíveltratá-lo, não é possível eliminá-lo dos sistemas eletrônicos [Haykin 2001a]. Nos sistemasde comunicação eletrônicos, a forma de ruído mais comum é o ruído térmico. Dentro daviabilidade física e de realização, a interferência intersimbólica e as alterações simbólicascausadas pelo ruído aditivo devem ser compensadas pelo receptor, geralmente antes dadecodificação do sinal.

Gerador de Símbolos

Canal h(k)

a(k) x(k)Equalizador+

u(k)

r(k)

Ts

ã(k)

Figura 3.2: Sistema de comunicação discreto em banda base com ISI e AWGN.

A Figura 3.2 apresenta a estrutura de um sistema discreto de comunicação digitalem banda base com ISI e ruído térmico, com o transmissor enviando símbolos complexosa(k), pertencentes a um conjunto A= {a0, . . . ,aM−1} de M símbolos possíveis (conhecidocomo constelação QAM), de modo que todas as subsequências finitas de simbolos possí-veis ocorrem com probabilidade diferente de zero. Os símbolos complexos são expressospor

a(k) = aI(k)+ jaQ(k), (3.2)

em que aI(k) e aQ(k) são, respectivamente, as componentes unidimensionais de fase equadratura que compõem o sinal bidimensional transmitido.


Os símbolos a(k) são transmitidos em um intervalo de símbolo Ts por meio de umcanal que assume-se ser linear, causal, BIBO estável (bounded-input bounded-output), ecuja resposta ao impulso, h(k), é descrita como

h(k) =L−1

∑i=0

ρiδ(k− τi), (3.3)

em que L é o número de percursos do canal, ρi é o ganho complexo do i-ésimo percurso eτi é um valor inteiro que representa o atraso do i-ésimo percurso no instante k. O sinal x(k)

representa o sinal a(k) após sofrer atenuação do canal. r(k) representa o ruído sistêmicoAWGN complexo, sendo r(k) = rI(k) + jrQ(k), em que rI(k) e jrQ(k) correspondem,respectivamente, às componentes de fase e quadratura do ruído e são variáveis aleatóriascom distribuição Gaussiana de média zero e variância σ2

r [Proakis 2000]. O equalizadorlinear, então, processa o sinal u(k), resultante da soma da saída do canal com o ruídoAWGN, expresso como

u(k) = x(k)+ r(k), (3.4)

sendo que

x(k) = ρ0a(k− τ0)+L−1

∑i=1

ρia(k− τi) (3.5)

em que o segundo termo da Equação (3.5) é a Interferência Intersimbólica.

3.2 Equalização adaptativa cega

Na técnica de equalização adaptativa cega, assume-se a impossibilidade de que pe-riodicamente o equalizador seja treinado com uma sequência simbólica preestabelecidado transmissor [Godard 1980]. Nessas condições, os equalizadores adaptativos cegosutilizam métricas estatísticas do próprio sinal transmitido para ajuste dos parâmetros[Godard 1980, Benveniste e Goursat 1984].

A Figura 3.3 representa a estrutura de um equalizador linear. O sinal de saída doequalizador é expresso por

a(k−deq) =N−1

∑l=0

wl(k)u(k− l) =N−1

∑l=0

wl(k)x(k− l)+N−1

∑l=0

wl(k)r(k− l) (3.6)

em que wl é o l-ésimo ganho complexo do equalizador e deq é o atraso de equalização.O equalizador linear adaptativo, ilustrado na Figura 3.4, trabalha em conjunto com

um algoritmo para que seja possível a adaptação de seus parâmetros, w(k), de acordo


w0(k)

z-1

+

X Xw1(k)

+ +

z-1

XwN-2(k)

+

XwN-1(k)

u(k) u(k-1) u(k-N-1)

...

... u(k-N-2)

ã(k-deq)

Figura 3.3: Estrutura de um equalizador linear de comprimento N.

Figura 3.4: Estrutura de um equalizador linear adaptativo cego.

com a variação aleatória da resposta ao impulso do canal de comunicação. A adaptação érealizada ao otimizar uma função custo J(w(k)), na qual

w(k) =

w0(k)

...wN−1(k)

=

wI

0(k)...

wIN−1(k)

+ j

wQ

0 (k)...

wQN−1(k)

(3.7)

Os métodos de equalização cega podem ser classificados ainda em dois grupos. Oprimeiro grupo compreende os métodos que efetuam o processo de equalização determi-nando as características estatísticas de segunda ordem (variância ou potência) dos sinaistransmitidos, compensando suas alterações, chamados de métodos autodidatas de segundaordem [Haykin 2001a]. O outro grupo de métodos, chamados de HOS (High Order Statis-

tics ou estatísticas de ordem superior) efetuam o processo de equalização determinando ascaracterísticas estatísticas de ordem superior dos sinais transmitidos, compensando suasalterações [Haykin (Editor) 1994]. Estas estatísticas normalmente são definidas matema-ticamente através de cumulantes estatísticos e de funções esperança [Haykin 2001a]. Umdos algoritmos baseados em HOS mais conhecidos da literatura é o CMA.

O algoritmo CMA tenta ajustar uma potência p inteira da informação de saída do


filtro adaptativo a uma constante real positiva rp. Essa constante é escolhida de formaa projetar sobre um círculo todos os pontos da constelação de saída do filtro adaptativo[Godard 1980, Benveniste e Goursat 1984]. A função custo a ser otimizada é expressapor

JCMA(w(k)) = E[e(k)2] (3.8)

em que E[·] é o operador média e

e(k) = γ−|a(k)|2 (3.9)

e γ é a constante de dispersão dada por

γ =E{|ak|4}E{|ak|2}

, (3.10)

em que ak pertence ao conjunto A de símbolos possíveis da modulação utilizada. A fun-ção de custo, JCMA, é otimizada pelo método do gradiente descendente com aproximaçãoestocástica, substituindo a esperança matemática por uma estimativa instantânea. Os pa-râmetros são ajustados a cada instante k de acordo com a expressão

w(k) = w(k−1)+µe(k)u(k), (3.11)

em que µ é o passo de adaptação e

u(k) =[u(k) . . . u(k− l) . . . u(k−N +1)

]T. (3.12)

Todavia, como apresentado em [Godard 1980, Benveniste e Goursat 1984] o critériode Godard, utilizado no CMA, possui pontos de mínimo local, dificultando o processode equalização. Com base nesse problema, existem vários trabalhos na literatura quepropõem técnicas para melhoria do processo de equalização.

Os trabalhos apresentados em [Han et al. 2005, Zaouche et al. 2008, Liu et al. 2008,Gang e Yourong 2009] utilizam algoritmos genéticos para otimizar a função JCMA, de-finida na Equação (3.8). Contudo, apesar de algumas dessas literaturas apresentaremresultados significativos, algumas ressalvas devem ser feitas. O uso da função de custodo CMA, que possui muitos pontos de mínimos locais, pode exigir muito tempo de pro-cessamento até que se tenha uma solução aceitável. Além disso, dada a complexidade dopróprio algoritmo genético, o uso desta técnica aliada a atualização em tempo real dosparâmetros do equalizador pode tornar esse uso inviável em termos de tempo de proces-samento. Nesse caso, pode ser interessante que a compensação feita pelo equalizador seja


realizada em blocos.Uma alternativa para evitar os mínimos locais é a utilização de programação linear

proposta por [Kennedy e Ding 1992], em que passa-se a ter uma função de custo con-vexa e, portanto, globalmente convergente. Por essa função não considerar os efeitos doruído sistêmico, [Fernandes 2015] realizou uma pequena alteração nessa função de custopara que ela abrangesse esses efeitos. Porém, como foi descrito no Capítulo 1, devidoà natureza aleatória dos fenômenos de ruído, essa nova função passou a considerar pa-râmetros estocásticos e, então, uma modelagem de programação linear estocástica se faznecessária.

Capítulo 4

Programação Linear Estocástica

Os problemas de otimização tem como objetivo buscar soluções para problemas domundo real através de modelos matemáticos. Dentre os diversos modelos matemáticosdesenvolvidos, a programação linear (PL) é uma técnica matemática que envolve o pla-nejamento de atividades que competem entre si pela utilização de recursos escassos parase obter um resultado ótimo de acordo com a função objetivo e as restrições definidas[Hillier e Lieberman 2006]. Assim, a programação linear preocupa-se com a maximi-zação ou minimização de uma função objetivo linear em diversas variáveis, sujeita àrestrições representadas por um conjunto de inequações e equações lineares [Dantzig eThapa 1997]. Além de pressupor que todas as funções matemáticas nesse modelo são ne-cessariamente funções lineares, a programação linear também pressupõe que todos seusparâmetros sejam constantes.

Entretanto, não é incomum que problemas reais estejam associados a parâmetros in-certos, como produção, demanda, custos, entre outros. Sob incerteza, nem toda a infor-mação necessária está disponível, e alguns parâmetros devem ser modelados como variá-veis aleatórias. O trabalho de [Sahinidis 2004] categoriza as principais abordagens sobincerteza em três grupos: programação estocástica, programação fuzzy, e programaçãoestocástica dinâmica. Destas, apenas a programação estocástica estará no escopo destadissertação.

Muitos modelos de programação estocástica (SP) são inicialmente formulados comomodelos de programação linear. Se um dos parâmetros numa LP é incerto e a LP pa-rece ser bastante sensível às alterações nestes parâmetros, então pode ser apropriado con-siderar um modelo de programação estocástica [Sen e Higle 1999]. A ocorrência nãodeterminística desses parâmetros gera diversos cenários possíveis para um mesmo pro-blema. Enquanto o modelo linear permite calcular a melhor solução para cada um dessescenários separadamente, o modelo estocástico considera o conjunto de todos os cenáriossimultaneamente, sendo associada a cada cenário uma probabilidade de ocorrência.

CAPÍTULO 4. PROGRAMAÇÃO LINEAR ESTOCÁSTICA 30

Em SP, presume-se que as funções de distribuição de probabilidade dos parâmetrosincertos são conhecidos e que os decisores tentarão obter uma solução ótima que minimizao valor esperado do objetivo [Hosseini e Dullaert 2011]. Assim, o modelo estocásticopode apresentar uma solução mais adequada que uma abordagem determinística.

Nas seções seguintes, será feita uma breve introdução à programação linear e pro-gramação linear estocástica. Serão tratados também os tipos principais de abordagensestocásticas. Algumas considerações sobre o presente trabalho são feitas no fim do capí-tulo.

4.1 Programação linear

A definição matemática de uma programação linear na forma padrão é encontrar osvalores de w1 ≥ 0,w2 ≥ 0, . . . ,wn ≥ 0 e minimizar z satisfazendo

v1w1 + v2w2 + · · · + vnwn = z (Min)

u11w1 + u12w2 + · · · + u1nwn = b1

u21w1 + u22w2 + · · · + u2nwn = b2... +

... +... +

......

um1w1 + um2w2 + · · · + umnwn = bm

(4.1)

Porém, como o sistema é linear, a Definição (4.1) pode ser estendida, através daspropriedades dos sistemas lineares, para uma definição mais abrangente. Em notaçãomatricial, podemos definir uma programação linear como

Otimizar vT w = z

sujeito a Uw = b (Uw≤ b ou Uw≥ b), U : m × n,

w≥ 0.

(4.2)

em que w∈Rn é o vetor das variáveis de decisão, v, U e b são os dados associados ao pro-blema. A operação de otimização pode denotar tanto uma transformação de maximizaçãoquanto de minimização.

4.1.1 Classificação das soluções

As soluções possíveis de um problema de programação linear podem ser classificadasde várias formas. Uma solução viável é aquela para a qual todas as restrições são satis-feitas. Do mesmo modo, uma solução inviável corresponde a uma solução na qual pelo


menos uma das restrições não é satisfeita. Uma solução ótima é uma solução viável quetem o valor mais favorável da função objetivo. Por valor mais favorável entende-se comoo maior valor se a função objetivo tiver de ser maximizada, ou como o menor valor casoela deva ser minimizada.

4.1.2 Operações elementares

Um mesmo modelo de programação linear, pode, sem qualquer perda para suas pro-priedades matemáticas, ser reescrito de acordo com a conveniência. Esse processo detradução é realizado através das operações elementares descritas a seguir.

Mudança no critério de otimização

Corresponde a transformação de um problema de maximização para um problema deminimização, ou vice versa. Essa mudança pode ser realizada utilizando as seguintespropriedades:

Maximizar ( f (w)) corresponde a minimizar (− f (w)) e

Minimizar ( f (w)) corresponde a maximizar (− f (w)).

Transformação de uma variável livre em uma variável não negativa

Sendo wn ∈ R uma variável livre cuja modelagem exige que as restrições sejam não-negativas, essa mudança exigirá a substituição da variável em transformação por duasvariáveis auxiliares, ambas maiores ou iguais a zero, cuja soma (ou diferença) seja igualà variável original, ou seja

wn = w1n +w2

n e w1n ≥ 0, w2

n ≥ 0.

Transformação de desigualdades em igualdades

Para o caso de transformações de menor ou igual para igualdade, supondo a restrição

w1 +w2 + · · ·+wn ≤ 0,

para transformá-la em restrição de igualdade, pode-se introduzir uma variável de folgawn+1 capaz de completar a desigualdade, o que permite apresentar a restrição de formaque

w1 +w2 + · · ·+wn +wn+1 = 0, wn+1 ≥ 0.


Já para o caso de transformação de restrições de maior que para igualdade, supondo arestrição

w1 +w2 + · · ·+wn ≥ 0,

para transformá-la em restrição de igualdade, pode-se introduzir uma variável de folgawn+1, com coeficiente negativo, capaz de completar a desigualdade, passando a represen-tar a restrição da seguinte forma

w1 +w2 + · · ·+wn−wn+1 = 0, wn+1 ≥ 0.

4.1.3 Limites

Numa programação linear na forma padrão, as quantidades dos recursos são semprenão-negativas. Porém, em muitos problemas reais, as quantidades dos recursos estão entreum valor superior e/ou outro inferior. A seguir, são detalhados esses tipos de restrições.

Não-negatividade

Tipicamente, em modelos de programação linear, as quantidades dos recursos emquestão são não-negativas. Esta característica das variáveis do modelo de programaçãolinear é conhecida como o pressuposto não negatividade. Em programas lineares, asrestrições de não-negatividade nas variáveis é denotado por w j ≥ 0.

Limites superior e inferior

Às vezes, é necessário que a quantidade de um recurso não seja menor que uma dadaquantidade, lin f , chamada de limite inferior. Este limite pode ser positivo ou negativo.Também podem haver outras restrições sobre as variáveis, de modo que elas não possamexceder uma determinada quantidade, lsup, chamada um limite superior. Para um dadorecurso j, isso pode ser representado por lin f j ≤ w j ≤ lsup j .

4.1.4 Hipóteses da programação linear

Todas as hipóteses de programação linear estão, na realidade, implícitas na formulaçãodo modelo apresentado na Definição (4.2). Do ponto de vista matemático, essas hipótesesse resumem à obrigatoriedade no modelo de possuir uma função objetivo linear sujeita arestrições lineares.


Entretanto, do ponto de vista de modelagem, essas propriedades matemáticas de ummodelo de programação linear implicam que certas hipóteses têm de ser satisfeitas emrelação às atividades e aos dados do problema que está sendo modelado, incluindo hipó-teses sobre o efeito de se variar os níveis de atividades [Hillier e Lieberman 2006]. Aseguir são apresentadas as quatro hipóteses da programação linear, conforme definido por[Hillier e Lieberman 2006].

Hipótese da proporcionalidade

A contribuição de cada atividade ao valor da função objetivo z é proporcional ao nívelde atividade w j, conforme representado pelo termo v jw j na função objetivo;

Hipótese da aditividade

Toda função em um modelo de programação linear, seja a função objetivo, seja afunção que se encontra do lado esquerdo da declaração de uma restrição funcional (verEquação (4.1)), é a soma das contribuições individuais das respectivas atividades;

Hipótese da divisibilidade

As variáveis de decisão em um modelo de programação linear podem assumir quais-quer valores, inclusive valores não-inteiros, que satisfaçam as restrições funcionais e denão-negatividade;

Hipótese da certeza

O valor atribuído a cada parâmetro de um modelo de programação linear é assumidocomo uma constante conhecida.

Em aplicações reais, a hipótese da certeza raramente é satisfeita de forma precisa. Osmodelos da programação linear são, em geral, formulados para selecionar alguma me-dida futura. Portanto, os valores de parâmetros usados seriam baseados em uma previsãode condições futuras que, inevitavelmente, introduz algum grau de incerteza [Hillier eLieberman 2006].

4.2 Programação linear estocástica

Como explicado anteriormente, a programação estocástica trata de problemas de oti-mização com parâmetros que assumem uma distribuição de probabilidade discreta ou


contínua. As abordagens principais para a programação estocástica são o modelo de re-curso e modelo probabilístico, que serão introduzidos a seguir.

4.2.1 Modelo de recurso

O problema em dois estágios, introduzido pela primeira vez por [Beale 1955, Dantzig1955] como um problema de recurso simples, é uma técnica de solução através de duasfases para problemas de programação estocástica; na primeira fase, a penalidade para aviolação das restrições é minimizada sob a suposição de que os valores das variáveis dedecisão são fixados em algumas constantes, e, na segunda fase, as variáveis de decisão sãodeterminadas de modo a minimizar a soma ponderada de penalidade e a função objetivooriginal [Masatoshi Sakawa 2011].

As variáveis de primeiro estágio são aquelas que tem que ser decididas antes que arealização efetiva dos parâmetros incertos esteja disponível. Subsequentemente, uma vezque os eventos aleatórios se apresentaram, uma posterior criação ou melhoria de políticaoperacional pode ser feita selecionando, a um certo custo, os valores da segunda fase oudas variáveis de recurso. O objetivo consiste em escolher as variáveis de primeiro estágiode uma forma que a soma dos custos de primeira etapa e o valor esperado da segunda fasealeatória ou custos de recurso sejam minimizados. O modelo de programação estocásticade dois estágios pode ser formulado como

minw∈W

{z(w) = vT w+E

[Q(w,ξ)

]}s.a. Uw≤ b w≥ 0 (4.3)

em que w ∈ Rn é o vetor das variáveis de decisão de primeiro estado, v, U e b são osdados associados ao problema de primeiro estágio, e Q(w,ξ) é o valor ótimo do problemade segundo estágio, definido por

miny

qT y s.a. Dy≤ h−Tw y≥ 0 (4.4)

em que y ∈ Rm é o vetor das variáveis de decisão de segundo estágio e ξ = (q,T,d,h)

contém os dados para o problema de segundo estágio que podem ser representados porvariáveis aleatórias com distribuição de probabilidade conhecidas. Assume-se que o vetoraleatório ξ possui um número finito de realizações ξ1, . . . ,ξS, com as respectivas probabi-lidades p1, . . . , pS. Assim, o valor esperado E[Q(w,ξ)] pode ser escrito da forma

E[Q(w,ξ)

]=

S

∑s=1

psQs(w,ξs) (4.5)


Logo, o modelo descrito na Equação (4.3) pode ser reescrito da forma

minw∈W

{z(w) = vT w+

S

∑s=1

psQs(w,ξs)

}s.a. Uw≤ b x≥ 0 (4.6)

em que Qs(w,ξs) é o valor ótimo para o problema de segundo estágio para cada realizaçãos = 1, . . . ,S, representada pela expressão

miny

qTs ys s.a. Dsys ≤ hs−Tsx ys ≥ 0 (4.7)

No primeiro estágio deve ser tomada uma decisão do tipo “aqui e agora” (here-and-

now) do vetor w, antes da realização das incertezas representadas por ξ. Assim, no pri-meiro estágio, é minimizado o custo de vT w mais o valor esperado do custo do problemano segundo estágio. No segundo estágio, quando as informações representadas por ξ jáestão disponíveis, é tomada a decisão a respeito do valor do vetor y. Essa decisão reflete ocomportamento ótimo no momento em que a incerteza é revelada, compensado qualquerdecisão inadequada tomada no primeiro estágio. Como a decisão sobre w independe dasrealizações do segundo estágio, o vetor w é o mesmo para todos os eventos que venham aocorrer no segundo estágio do problema [Birge e Louveaux 2000].

4.2.2 Modelo probabilístico

Considerando o fato de que restrições estocásticas nem sempre são satisfeitas, a no-ção de chance ou restrições de probabilidade, que significa que as restrições envolvendovariáveis aleatórias precisam ser satisfeitas com uma certa probabilidade, foi introduzidapor [Charnes e Cooper 1959]. O modelo probabilístico ou Chance-constrained program-

ming permite que algumas restrições de segundo estágio sejam expressas em termos dedeclarações probabilísticas sobre as decisões de primeiro estágio. Em vez das ações cor-retivas presentes nos modelos de recurso, nesta abordagem algumas restrições de segundoestágio podem ser violadas ao incorporarem uma medida de risco.

O modelo probabilístico é usado principalmente quando custos e benefícios associ-ados às decisões de segundo estágio são difíceis de serem avaliados. O problema a serotimizado é relaxado em problema linear equivalente, de forma que possa ser resolvidopor técnicas tradicionais de solução de problemas lineares. O procedimento pelo qualo Chance-constrained programming lida com incerteza é ilustrado, simplificadamente,através do modelo linear abaixo:


minw

vT w

s.a. Uw≤ b,

w≥ 0.

(4.8)

em que w ∈ Rn, v ∈ Rn, b ∈ Rm e U ∈ Rmxn. Assume-se que U e v são parâmetrosdeterminísticos e b é um vetor aleatório com função de distribuição acumulada marginal Φ

conhecida. Dado o vetor de probabilidades α ∈ Rn, a restrição de chance para a restriçãoUw≤ b de um problema linear é representado por

Pr(

Uw≤ b)≥ α (4.9)

em que Pr é a medida de probabilidade e o vetor α = (α1, . . . ,αn)T são as extensões de

probabilidade para as quais as violações de restrições são permitidas. Logo, o elemento αi

é associada à i-ésima restrição ∑mj=1Ui jwi ≤ bi, e a i-ésima restrição é interpretada como

Pr{ m

∑j=1

Ui jwi ≤ bi

}≥ αi i= 1,2, . . . ,n (4.10)

A Inequação (4.10) significa que a i-ésima restrição pode ser violada, mas no máximopor (1−αi) da proporção do tempo. Aplicando a função de distribuição acumulada de bi

à Restrição (4.10), esta pode ser reformulada como:

m

∑j=1

Ui jwi ≤Φ−1i (1−αi) i= 1,2, . . . ,n (4.11)

em que, Φ−1i e αi são conhecidos. Desta forma a Restrição (4.10) é reduzida a uma restri-

ção linear comum e o modelo probabilístico se transforma em um modelo de programaçãolinear determinístico.

4.3 Algoritmos genéticos como solucionadores de proble-mas estocásticos

Existem várias técnicas computacionais para auxiliar na resolução de problemas esto-cásticos. Assim como mostrado no Capítulo 1, existem várias literaturas que vem abor-dando algoritmos genéticos como geradores de soluções para problemas estocásticos. Otrabalho de [Yoshitomi et al. 2000] utiliza a função objetivo estocástica diretamente noalgoritmo genético, que sofre uma pequena alteração em sua estrutura em que cada in-


divíduo carregue consigo sua probabilidade de ocorrência e que essa probabilidade sejausada para avaliar a aptidão da solução. Já os trabalhos de [Ma e Zhang 2002], [Poojari eVarghese 2008] e [Qin et al. 2010] utilizam a chance-constrained programming para mo-delar os parâmetros estocásticos e essa função de custo com restrições relaxadas é usadacomo função objetivo do algoritmo genético. Por fim, o trabalho de [Cui et al. 2015]modela parâmetros financeiros estocásticos através da modelagem em dois estágios comrecurso e, utilizando o modelo de primeiro estágio para avaliar os indivíduos no início decada iteração e o modelo de segundo estágio para fazer a avaliação final da população.

De maneira semelhante às literaturas acima citadas, o presente trabalho propõe umaabordagem baseada em algoritmos genéticos para gerar soluções a partir de uma mode-lagem linear estocástica. Os detalhes dessa abordagem serão mostrados nos capítulos aseguir.

Capítulo 5

Equalizador Linear Cego Baseado emGA

Conforme discutido nos capítulos anteriores, os algoritmos genéticos têm sido mos-trados como base para algoritmos de equalização adaptativa, inclusive dentro do interessedeste trabalho, a equalização adaptativa cega. Entretanto, como citados anteriormente,as propostas da literatura utilizam abordagens com o GA associado a funções de custotipicamente com problemas de convergência em mínimos locais. Nesse contexto, a pro-gramação linear tem sido uma alternativa promissora para desenvolvimento de funçõesde custo globalmente convergentes, embora o estado da arte ainda não tenha tratado dosparâmetros sob incerteza presentes no modelo.

Este capítulo destina-se a descrever o esquema de equalização linear cega, o ELC-GA,proposto no presente trabalho. Nas próximas seções, serão feitas uma breve introduçãoà equalização cega baseada em programação linear e o detalhamento de toda a estruturado esquema proposto, incluindo a arquitetura do equalizador, os detalhes do algoritmogenético proposto e da função de custo linear estocástica utilizada.

5.1 Equalização cega baseada em programação linear

Os trabalhos de [Kennedy e Ding 1992, Ding e Luo 2000] propuseram uma funçãode custo convexa, baseada em programação linear, globalmente convergente. Essa funçãonão tenta identificar diretamente o ganho complexo do canal e, em vez disso, foca emeliminar a ISI. Uma vez removida a ISI, a saída do equalizador torna-se uma versão es-calada da entrada do canal, sendo possível estimar o ganho escalar por meio de métodosmais simples como, por exemplo, comparando a potência da entrada do canal com a saídado equalizador. Desse modo, a função de custo convexa para o equalizador linear cego

CAPÍTULO 5. EQUALIZADOR LINEAR CEGO BASEADO EM GA 39

proposta por essas literaturas pode ser expressa por

JPL (w) = JPL

(wI,wQ

)≡max

∣∣aI(k)∣∣+max

∣∣∣aQ(k)∣∣∣ . (5.1)

De acordo com as limitações matemáticas desse modelo, conforme sugerido por [Kennedye Ding 1992], é assumido que o sinal transmitido a(k) é modulado no esquema M-QAMem que as componentes real e imaginária são independentes e idênticas, com

M ≡max∣∣aI(k)

∣∣= max∣∣∣aQ(k)

∣∣∣para qualquer k, (5.2)

ou possam ser transformadas para essa forma através de uma rotação.Como as bibliografias citadas anteriormente não levam em consideração os efeitos

do ruído na função de custo convexa expressa pela Equação (5.1), faz-se necessária umaprova de que ao se considerar o ruído na modelagem, a função permanece convexa. Talprova já havia sido realizada de forma mais simplificada no trabalho de [Fernandes 2015],e uma prova mais detalhada será feita a seguir. Conforme mostradas no Capítulo 3, asEquações (3.4) e (3.5) podem ser expandidas da seguinte forma

u(k) = uI(k)+ juQ(k)

= xI(k)+ rI(k)+ j(

xQ(k)+ rQ(k)), (5.3)

sendo que

x(k) = xI(k)+ jxQ(k)

=L−1

∑i=0

ρIi a

I (k− τi)−ρQi aQ (k− τi)+

L−1

∑i=0

j(

ρIi a

Q (k− τi)+ρQi aI (k− τi)

). (5.4)

Expandindo a expressão de a(k) usando a Equação (3.6), tem-se que

a(k) =N−1

∑l=0

(uI(k− l)+ juQ(k− l)

)(wI

l (k)+ jwQl (k)

)=

N−1

∑l=0

uI(k− l)wIl (k)−uQ(k− l)wQ

l (k)+

N−1

∑l=0

j(

uQ(k− l)wIl (k)+uI(k− l)wQ

l (k)). (5.5)


Isolando os termos de aI(k) e aQ(k) conforme a Equação (3.2) e substituindo os valorescorrespondentes obtidos nas Equações (5.3) e (5.4) tem-se que

aI(k) =N−1

∑l=0

L−1

∑i=0

(ρ

Ii a

I (k− τi− l)−ρQi aQ (k− τi− l)

)wI

l (k)+

N−1

∑l=0

L−1

∑i=0

(−ρ

Ii a

Q (k− τi− l)−ρQi aI (k− τi− l)

)wQ

l (k)+

N−1

∑l=0

rI(k− l)wIl (k)+

N−1

∑l=0−rQ(k− l)wQ

l (k) (5.6)

e

aQ(k) =N−1

∑l=0

L−1

∑i=0

(ρ

Ii a

Q (k− τi− l)+ρQi aI (k− τi− l)

)wI

l (k)+

N−1

∑l=0

L−1

∑i=0

(ρ

Ii a

I (k− τi− l)−ρQi aQ (k− τi− l)

)wQ

l (k)+

N−1

∑l=0

rQ(k− l)wIl (k)+

N−1

∑l=0

rI(k− l)wQl (k). (5.7)

A função de custo proposta por [Kennedy e Ding 1992] (ver Equação 5.1) busca mini-mizar a soma dos máximos dos módulos dos termos de a(k), que por sua vez são formadospela soma de expressões lineares. Desse modo, expandindo os termos em evidência dasEquações (5.6) e (5.7), tem-se que

max∣∣aI(k)

∣∣ = max

∣∣∣∣∣N−1

∑l=0

L−1

∑i=1

ρIi a

I (k− τi− l)wIl (k)

∣∣∣∣∣+max

∣∣∣∣∣N−1

∑l=0

L−1

∑i=0−ρ

Qi aQ (k− τi− l)wI

l (k)

∣∣∣∣∣+max

∣∣∣∣∣N−1

∑l=0

L−1

∑i=1−ρ

Ii a

Q (k− τi− l)wQl (k)

∣∣∣∣∣+max

∣∣∣∣∣N−1

∑l=0

L−1

∑i=0−ρ

Qi aI (k− τi− l)wQ

l (k)

∣∣∣∣∣+max

∣∣∣∣∣N−1

∑l=0

rI(k− l)wIl (k)

∣∣∣∣∣+max

∣∣∣∣∣N−1

∑l=0−rQ(k− l)wQ

l (k)

∣∣∣∣∣ (5.8)


e

max∣∣aI(k)

∣∣ = max

∣∣∣∣∣N−1

∑l=0

L−1

∑i=1

ρIi a

Q (k− τi− l)wIl (k)

∣∣∣∣∣+max

∣∣∣∣∣N−1

∑l=0

L−1

∑i=0

ρQi aI (k− τi− l)wI

l (k)

∣∣∣∣∣+max

∣∣∣∣∣N−1

∑l=0

L−1

∑i=1

ρIi a

I (k− τi− l)wQl (k)

∣∣∣∣∣+max

∣∣∣∣∣N−1

∑l=0

L−1

∑i=0−ρ

Qi aQ (k− τi− l)wQ

l (k)

∣∣∣∣∣+max

∣∣∣∣∣N−1

∑l=0

rQ(k− l)wIl (k)

∣∣∣∣∣+max

∣∣∣∣∣N−1

∑l=0

rI(k− l)wQl (k)

∣∣∣∣∣ . (5.9)

Neste momento, deve-se fazer algumas considerações sobre as propriedades do mo-delo proposto. O teorema da desigualdade triangular, derivado da desigualdade de Cauchy-Schwarz, diz que o módulo da soma das partes é sempre menor ou igual à soma dosmódulos das partes, conforme mostrado pela inequação a seguir

|n1 +n2| ≤ |n1|+ |n2| (5.10)

em que n1 e n2 são dois números reais finitos quaisquer. Entretanto, considerando quedomínio dos módulos dos valores do alfabeto finito da modulação QAM são limitadosentre −M e M, conforme definido na Equivalência (5.2), então, dentro desse domínio,pode-se afirmar que é válido

max |n1 +n2|= max |n1|+max |n2| (5.11)

ou, dentro do domínio em questão,

max∣∣aI(k)+aI(k−1)

∣∣= max∣∣aI(k)

∣∣+max∣∣aI(k−1)

∣∣ . (5.12)

Desse modo, as somas expressas nas Equações (5.8) e (5.9) tornam-se válidas. Consi-derando a propriedade descrita na Equação (5.2), as Equações (5.8) e (5.9) podem ser


simplificadas e expressas por

max∣∣aI(k)

∣∣ = MN−1

∑l=0

L−1

∑i=0

(∣∣ρIi w

Il (k)∣∣+ ∣∣∣ρQ

i wIl (k)∣∣∣

+∣∣∣ρI

i wQl (k)

∣∣∣+ ∣∣∣ρQi wQ

l (k)∣∣∣)

+N−1

∑l=0

(max

∣∣rI(k− l)wIl (k)∣∣+max

∣∣∣rQ(k− l)wQl (k)

∣∣∣) . (5.13)

e

max∣∣∣aQ(k)

∣∣∣ = MN−1

∑l=0

L−1

∑i=0

(∣∣ρIi w

Il (k)∣∣+ ∣∣∣ρQ

i wIl (k)∣∣∣

+∣∣∣ρI

i wQl (k)

∣∣∣+ ∣∣∣ρQi wQ

l (k)∣∣∣)

+N−1

∑l=0

max∣∣∣rI(k− l)wQ

l (k)∣∣∣+max

∣∣∣rQ(k− l)wIl (k)∣∣∣ . (5.14)

As funções ρIi w

Il (k), ρI

i wQl (k), ρ

Qi wI

l (k) e ρQi wQ

l (k) são lineares em wI e wQ e seusmódulos |ρI

i wIl (k)|, |ρI

i wQl (k)|, |ρ

Qi wI

l (k)| e |ρQi wQ

l (k)| são funções convexas em wI e wQ.Assim, como JPL

(wI,wQ) é uma soma desta funções pode-se dizer que JPL

(wI,wQ) tam-

bém é convexa. Sem qualquer restrição, JPL(wI,wQ) possui um mínimo global trivial em

wI = wQ = 0 gerando como saída a(k) = 0. Para que JPL(wI,wQ) seja praticável, o vetor

de parâmetros do equalizador precisa ser restringido de retornar uma solução toda zerada.Mas ao mesmo tempo, as restrições não devem danificar a habilidade do equalizador deobter a remoção da ISI. Para satisfazer ambos objetivos, é proposta a seguinte restrição

wIdeq

(k) = 1, (5.15)

onde deq é um inteiro limitado por 0 ≤ deq ≤ N − 1 que representa o atraso de equali-zação. Esta restrição foi baseada na condição inicial do algoritmo do CMA apresentadaem [Godard 1980, Benveniste e Goursat 1984] e nas propostas de [Kennedy e Ding 1992,Ding e Luo 2000] e com ela pode-se evitar a solução com saídas nulas e, ao mesmotempo, garantir a equalização do canal. Devido à linearidade da restrição, a convexidadeda função de custo é mantida e com isto a convergência global da função.

Comparando as Equações (5.13) e (5.9) com as apresentadas em [Kennedy e Ding1992, Ding e Luo 2000, Luo et al. 2002], observa-se que o ruído AWGN não altera aconvexidade da função custo, apenas altera o valor do mínimo global.


5.2 O esquema ELC-GA

O ELC-GA é um esquema de equalização adaptativa cega, que utiliza um algoritmode equalização baseado em algoritmos genéticos, cuja função objetivo é dada por umproblema de programação linear estocástica. Os detalhes desse esquema são descritos aseguir.

5.2.1 Arquitetura do ELC-GA

Figura 5.1: Estrutura do algoritmo ELC-GA.

A estrutura do ELC-GA é mostrada na Figura 5.1. A fim de assegurar a alta velocidadede processamento requerida pelo sistema de transmissão de dados, o ELC-GA particionaa sequência de entrada, u(k), em blocos não sobrepostos de tamanho K. Para armazenaresses blocos, é utilizado um buffer de mesmo tamanho do bloco no qual são construídasas matrizes

UI (k) =[

uI (k) · · · uI (k−K +1)]

(5.16)

eUQ (k) =

[uQ (k) · · · uQ (k−K +1)

]. (5.17)

As matrizes UI (k) e UQ (k) armazenam, respectivamente, as componentes de fase e qua-dratura de cada símbolo do bloco. Um bloco por vez é processado pelo algoritmo ge-nético para determinar os novos parâmetros do equalizador. Assim, diferentemente doCMA, que atualiza os parâmetros a cada instante k, o ELC-GA atualiza os parâmetros doequalizador a cada bloco de K símbolos. Para canais estáticos isto não é problema, po-rém, para canais móveis o valor de K deve ser menor que o tempo de coerência do canal[Haykin 2001a, Proakis 2000].


5.2.2 Função objetivo

Como mostrado anteriormente, o ELC-GA armazena em um buffer de tamanho K ossímbolos da entrada do equalizador, para após o buffer atingir sua capacidade, atualizaros parâmetros do equalizador. Dada a função de custo mostrada na Equação (5.1) e arestrição apresentada na Equação (5.15), pode-se afirmar que o objetivo do ELC-GA éotimizar

min

max

∣∣aI(k−deq)∣∣+max

∣∣aQ(k−deq)∣∣

...max

∣∣aI(k−K +1−deq)∣∣+max

∣∣aQ(k−K +1−deq)∣∣ (5.18)

sujeito à restriçãowI

deq(k) = 1. (5.19)

Desse modo, a partir da Equação (5.5), tem-se que

aI(k) =N−1

∑l=0

uI(k− l)wIl (k)−uQ(k− l)wQ

l (k) (5.20)

e

aQ(k) =N−1

∑l=0

uQ(k− l)wIl (k)+uI(k− l)wQ

l (k). (5.21)

Considerando que a constelação QAM do problema em questão obedeça à propriedadedescrita na Equação (5.2), a maximização (ou minimização) de uma função módulo podeser transformada em uma função linear através da substituição daquela por uma variávelauxiliar e da introdução de restrições lineares que assegurem a equivalência das funções.Assim, dada uma maximização de módulo, max |α|, e uma variável auxiliar τ, se τ =

max |α| então −τ ≤ α ≤ τ. De forma similar ao realizado nos trabalhos de [Kennedy eDing 1992, Ding e Luo 2000, Luo et al. 2002, Fernandes 2015], pode-se substituir cadatermo da Equação (5.1) pelas variáveis auxiliares τ1 e τ2, de forma que

JPL (w) ≡ Mτ1 +Mτ2 (5.22)

sujeito a aI(k)≤Mτ1,

aI(k)≥−Mτ1,

aQ(k)≤Mτ2,

aQ(k)≥−Mτ2


em que M corresponde ao número de símbolos do alfabeto utilizado. Com base nessenovo modelo linear, e substituindo os valores das Equações (5.20) e (5.21), o problemade otimização tratado neste trabalho, descrito pelas Expressões (5.18) e (5.19), pode serexpresso como

min J(w) = Mτ1 +Mτ2, (5.23)

sujeito às seguintes restrições

∑N−1l=0 wI

l (k)uI (k− l)−wQ

l (k)uQ (k− l)≤Mτ1

...

∑N−1l=0 wI

l (k)uI (k− l−K +1)−wQ

l (k)uQ (k− l−K +1)≤Mτ1

∑N−1l=0 wI

l (k)uI (k− l)−wQ

l (k)uQ (k− l)≥−Mτ1

...

∑N−1l=0 wI

l (k)uI (k− l−K +1)−wQ

l (k)uQ (k− l−K +1)≥−Mτ1

∑N−1l=0 wQ

l (k)uI (k− l)−wI

l (k)uQ (k− l)≤Mτ2

...

∑N−1l=0 wQ

l (k)uI (k− l−K +1)−wI

l (k)uQ (k− l−K +1)≤Mτ2

∑N−1l=0 wQ

l (k)uI (k− l)−wI

l (k)uQ (k− l)≥−Mτ2

...

∑N−1l=0 wQ

l (k)uI (k− l−K +1)−wI

l (k)uQ (k− l−K +1)≥−Mτ2

(5.24)

ewI

deq(k) = 1, (5.25)

Em que τ1, τ2 e as componentes dos parâmetros do equalizador, wIl (k) e wQ

l (k), são asvariáveis a serem otimizadas; as componentes do sinal de entrada do equalizador, uI (k) euQ (k), são as entradas do algoritmo; e M é uma constante, correspondendo ao número desímbolos do alfabeto da modulação em questão.

Logo, na condição ótima temos que Mτ1 =max∣∣aI(k−deq)

∣∣ e Mτ2 =max∣∣aQ(k−deq)

∣∣e, nessa condição, o modelo apresentado pela Equação (5.1) e o modelo descrito pelasExpressões (5.23), (5.24) e (5.25) são equivalentes. A estratégia de programação linearé formada por 2N + 2 variáveis com 4K + 1 restrições lineares. Na prática a variável N

é associada ao tamanho do equalizador e deve ser maior que o comprimento do canal L


(N > L).

5.2.3 O algoritmo genético

Dentro do esquema proposto, o algoritmo genético tem por função encontrar os me-lhores parâmetros para adaptação do equalizador. Para a versão atual do ELC-GA, foiutilizada a implementação do algoritmo genético presente na toolbox de otimização doMatlab. A seguir, serão descritas a codificação escolhida para os indivíduos e as fun-ções de criação, seleção, cruzamento e mutação que se apresentaram mais adequadas àcodificação dos indivíduos.

Codificação dos indivíduos

A codificação dos indivíduos foi feita de modo que cada cromossomo de uma popu-lação de tamanho p do algoritmo genético corresponde a um vetor c( j), com 1 ≤ j ≤ p

expresso porc( j) = [τ1 τ2 wI

0(k) wQ0 (k) . . . wI

N−1(k) wQN−1(k)] (5.26)

ouc( j) = [τ1 τ2 | w(k)]. (5.27)

em que os dois primeiros genes carregam os valores das variáveis τ1 e τ2 da expressãoda função objetivo (Equação (5.23)), e os demais carregam as partes real e imaginária decada parâmetro do equalizador (ver Equação (3.7)).

Analisando a Equação (5.26), é possível perceber que, dado um equalizador de com-primento N, o tamanho de c( j) é dado por 2+2N. O tamanho do cromossomo é, então,coerente com o número de variáveis da função objetivo, detalhada na Seção 5.2.2.

Funções de inicialização, seleção e operadores genéticos

As funções explicadas a seguir foram escolhidas principalmente por serem funçõesadequadas para tratar de problemas cuja modelagem possua restrições e as variáveis pos-suam valores reais. Tais funções são explicadas segundo suas implementações no Toolboxde otimização do Matlab. A base teórica necessária para o melhor entendimento dessasfunções encontra-se no Capítulo 2 e maiores explicações sobre as funções da plataformade otimização do Matlab podem ser encontradas em [Matlab n.d.].

A função @gacreationlinearfeasible cria uma população inicial aleatória que satisfaztodos os limites e restrições lineares do modelo. Se há restrições lineares, que é o caso do


modelo proposto, ela cria muitos indivíduos sobre as fronteiras da região de restrição, ecria uma população bem dispersa. A função de seleção, @selectionstochunif, define umalinha na qual cada um dos pais corresponde a uma seção dessa linha, cujo comprimentoé proporcional ao seu valor escalonado. O algoritmo move-se ao longo da linha em pas-sos de igual tamanho. A cada passo, o algoritmo aloca um pai a partir da seção que eleatinge. A função de cruzamento, @crossoverintermediate, gera indivíduos filhos fazendouma média ponderada dos pais. Na simulação, foram usados os mesmos pesos para cadaindivíduo pai. Já a função de mutação, @mutationadaptfeasible, gera aleatoriamente di-reções que são adaptativas no que diz respeito à última geração bem ou mal sucedida. Amutação escolhe uma direção e o tamanho do passo que satisfaz os limites e restriçõeslineares.

5.3 Algoritmo genético para resolução do problema li-near estocástico

Conforme detalhado no Capítulo 3, o sinal de entrada do equalizador, u(k) tem comocomponente o ruído sistêmico, que se trata de um processo aleatório. A presença dessecomponente aleatório torna a modelagem linear descrita pela Expressão (5.23) e pelasRestrições (5.24) e (5.25) um problema linear estocástico. Para ilustrar melhor essa situ-


ação, pode-se expandir a Restrição (5.24) através da Equação (3.4), obtendo-se

∑N−1l=0 wI

l (k)(xI (k− l)+ rI (k− l)

)−wQ

l (k)(xQ (k− l)+ rQ (k− l)

)≤Mτ1

...

∑N−1l=0 wI

l (k)(xI (k− l−K +1)+ rI (k− l−K +1)

)+

∑N−1l=0 −wQ

l (k)(xQ (k− l−K +1)+ rQ (k− l−K +1)

)≤Mτ1

∑N−1l=0 −wI

l (k)(xI (k− l)+ rI (k− l)

)+wQ

l (k)(xQ (k− l)+ rQ (k− l)

)≤Mτ1

...

∑N−1l=0 −wI

l (k)(xI (k− l−K +1)+ rI (k− l−K +1)

)+

∑N−1l=0 wQ

l (k)(xQ (k− l−K +1)+ rQ (k− l−K +1)

)≤Mτ1

∑N−1l=0 wQ

l (k)(xI (k− l)+ rI (k− l)

)−wI

l (k)(xQ (k− l)+ rQ (k− l)

)≤Mτ2

...

∑N−1l=0 wQ

l (k)(xI (k− l−K +1)+ rI (k− l−K +1)

)+

∑N−1l=0 −wI

l (k)(xQ (k− l−K +1)+ rQ (k− l−K +1)

)≤Mτ2

∑N−1l=0 −wQ

l (k)(xI (k− l)+ rI (k− l)

)+wI

l (k)(xQ (k− l)+ rQ (k− l)

)≤Mτ2

...

∑N−1l=0 −wQ

l (k)(xI (k− l−K +1)+ rI (k− l−K +1)

)+

∑N−1l=0 wI

l (k)(xQ (k− l−K +1)+ rQ (k− l−K +1)

)≤Mτ2

(5.28)

Assim, as Restrições (5.28) podem ser definidas, segundo a modelagem de programaçãolinear definida na Equação (4.2), na forma

(X+R)w≤ b (5.29)

em que w∈Rn, n= 2N, é o vetor das variáveis de decisão (os parâmetros do equalizador),X ∈ Rm×n, m = 4K, é a matriz com os valores da resposta ao canal do sinal transmitido,R ∈Rm×n é a matriz que representa os fenômenos de ruído, constituindo o parâmetro sobincerteza do problema em questão, e b ∈ Rm representa o vetor dos limites de valoresdas restrições. Desse modo, dado que um problema de programação linear que possuiparâmetros sob incerteza passa a ser modelado como um problema de programação linearestocástica, as técnicas clássicas de solução de problemas lineares não são adequadas paratratar desse problema.


Muitos problemas reais com alguma incerteza podem ser formulados como um pro-blema de programação estocástica. Do ponto de vista da geração de resultados maisadequados para as situações envolvidas, a modelagem estocástica é muito importante.Entretanto, esses problemas são muito difíceis de resolver de forma analítica. Assim, énecessário encontrar um método flexível e robusto para resolver esse tipo de problema.

Por outro lado, os algoritmos genéticos tem sido extensamente utilizados para resolverproblemas em cenários estáticos em geral. Os GA são um tipo de gerador de soluções,onde inicialmente indivíduos aleatórios são criados e associados com as soluções do pro-blema em questão. Além disso, também são seletores de soluções, em que um jogo desobrevivência é instaurado para obter-se o vencedor. O vencedor corresponde à soluçãoótima do problema, e os perdedores são as soluções viáveis não-ótimas. Nessas opera-ções de geração e seleção de indivíduos, uma parte considerável do espaço de busca doproblema é percorrida estocasticamente. Assim, mesmo com um problema com parâ-metros aleatórios, os algoritmos genéticos tem condições de percorrer os vários cenáriospossíveis e fornecer soluções adequadas ao problema.

Como tratado no Capítulo 1 e na Seção 4.3, os algoritmos genéticos têm sido usadosem soluções de problemas estocásticos diversos. A maioria dessas abordagens utilizamos GA para gerar as soluções ótimas de problemas abordados com os modelos citadosna Seção 4.2, enquanto os demais buscam modificar o algoritmo genético usado para in-cluir alguma medida estatística necessária especificamente para o problema tratado. Nopresente trabalho, os modelos estocásticos descritos na Seção 4.2 não se adequavam pro-priamente ao problema abordado, levando à necessidade de um estudo futuro mais apro-fundado nesse sentido. Desse modo, a função objetivo linear com restrições estocásticasfoi aplicada diretamente como função objetivo do algoritmo genético utilizado. Mesmoassim, a busca estocástica presente no GA foi capaz de encontrar soluções ótimas para oproblema em questão, conforme será mostrado mais adiante neste trabalho.

Capítulo 6

Resultados

Objetivando validar o ELC-GA e determinar sua confiabilidade e desempenho, foramrealizadas simulações para sistemas de comunicações digitais com modulação 4-QAM,16-QAM e 64-QAM, sem codificação de canal. O sistema foi modelado de acordo como esquema mostrado na Figura 3.2, e os resultados foram levantados para o algoritmogenético, implementado no toolbox de otimização da plataforma Matlab (Mathworks).Além do algoritmo genético, também foram levantados resultados para o algoritmo CMA,a fim de comparar o desempenho da nova técnica com um dos métodos mais utilizados deequalização cega.

6.1 Simulações

As simulações realizadas foram utilizadas para gerar as curvas de BER (Bit Error

Rate) em função de Eb/N0, em que Eb/N0 representa a relação entre a energia de bit,

Eb =E[a2

k ]

log2(M), (6.1)

e a densidade espectral de potência do ruído, σ2r . Os resultados foram avaliados para

dois cenários de canais estáticos com ISI e ruído AWGN, com o primeiro canal (canal A)expresso por

ha(k) = δ(k)+0,5δ(k−3)+0,3δ(k−6), (6.2)

e o segundo (canal B) sendo expresso por

hb(k) = δ(k)+0,6δ(k−1)+0,4δ(k−2). (6.3)

Nas simulações, os parâmetros do equalizador foram ajustados num período de Tad

símbolos e a contagem de erro (valores da BER) foi iniciada após Tad símbolos. A seguir,

CAPÍTULO 6. RESULTADOS 51

serão descritos os parâmetros utilizados nas simulações realizadas, detalhando os parâ-metros da estruturas dos equalizadores simulados e os parâmetros internos do algoritmogenético.

6.1.1 Parâmetros das estruturas dos equalizadores

A Tabela 6.1 apresenta os parâmetros utilizados nas estruturas dos equalizadores si-mulados nos canais A (ha(k)) e B (hb(k)). É importante enfatizar que esses parâmetrosforam selecionados após exaustivas simulações, buscando os melhores valores para cadaestrutura de equalizador.

Tabela 6.1: Parâmetros utilizados nas estruturas dos equalizadores simulados.

Modulação QAM (M) 4 16 64

Comprimento do equalizador (N) 33 33 33

Atraso de equalização (deq) 6 6 6

Tamanho do bloco do ELC-GA (K) 400 400 1000

Passo de adaptação do CMA (µ) 1×10−3 1×10−3 1×10−4

Período de ajuste dos parâmetros (Tad) 1×107 1×107 1×107

6.1.2 Parâmetros do algoritmo genético

A implementação do algoritmo genético do esquema proposto é feita através da pla-taforma de otimização do Matlab. Os parâmetros fornecidos à plataforma para a imple-mentação do algoritmo genético são descritos na Tabela 6.2. A escolha do valor de cadaparâmetro foi feita após a realização de exaustivos testes, que buscaram encontrar a me-lhor relação entre o tempo de execução do algoritmo e a qualidade da solução encontrada.


Tabela 6.2: Parâmetros fornecidos ao toolbox do Matlab para a implementação do GA.

Tamanho do cromossomo 2N +2

Tamanho da população 200

Tipo da população Vetor de números reais

Elitismo 10 indivíduos

Taxa de cruzamento 0,9

Taxa de mutação 0,01

Número máximo de gerações 100

Para uma descrição da função objetivo restrita utilizada, ver Seção 5.2.2. As funçõesde inicialização, seleção, cruzamento e mutação são descritas de forma mais teórica noCapítulo 2, e na Seção 5.2.3 são mostrados alguns detalhes a respeito da implementaçãodessas funções na plataforma do Matlab.

6.2 Resultados obtidos

Os resultados obtidos para os sistemas 4-QAM, 16-QAM e 64-QAM para o casodo canal A (ha(k)) são apresentados nas Figuras 6.1, 6.2 e 6.3, respectivamente. Nosistema com modulação 4-QAM (Figura 6.1) foi apresentado uma menor taxa de errode bit, comparando o ELC-GA com o método tradicional CMA. No caso dos sistemas16-QAM e 64-QAM (Figuras 6.2 e 6.3), o método CMA foi incapaz de convergir para omínimo global para Tad = K símbolos, em contraste com a técnica baseada em algoritmosgenéticos. Em outras palavras, o CMA foi incapaz de equalizar o canal A em Tad = K

símbolos para as modulações superiores a 4-QAM (o sistema 16-QAM usou k = 400símbolos e o sistema 64-QAM usou k = 1000 símbolos). Entretanto, pode ser observadonas curvas mostradas nas Figuras 6.1, 6.2 e 6.3 que o CMA tem desempenho semelhanteao ELC-GA quando seus parâmetros são ajustados com Tad > K símbolos (o sistema 4-QAM usou Tad = 1×103 símbolos, o sistema 16-QAM usou Tad = 1×104 símbolos e osistema 64-QAM usou Tad = 7×104 símbolos).


0 5 10 15 2010

−5

10−4

10−3

10−2

10−1

Eb/N

0

BE

R

ELC-GA (Tad = 400 symbols)CMA (Tad = 400 symbols)CMA (Tad = 1 × 103 symbols)

Figura 6.1: Curva de desempenho de BER de um sistema 4-QAM em função de Eb/N0relativas ao canal A, ha(k) (ver equação (6.2)).

0 5 10 15 2010

−5

10−4

10−3

10−2

10−1

Eb/N

0

BE

R

ELC-GA (Tad = 400 symbols)

CMA (Tad = 400 symbols)

CMA (Tad = 1 × 104 symbols)



0 5 10 15 2010

−5

10−4

10−3

10−2

10−1

Eb/N

0

BE

R





As curvas em função de Eb/N0 para as simulações empregando o segundo cenário como canal B, hB(k), são apresentadas nas Figuras 6.4, 6.5 e 6.6 para os sistemas 4-QAM,16-QAM e 64-QAM, respectivamente. O sistema 4-QAM mostrou um desempenho li-geiramente superior, com ganho de até aproximadamente 2 dB, para a técnica baseadaem algoritmos genéticos em comparação ao método CMA (Figura 6.4). No caso dossistemas 16-QAM e 64-QAM (Figuras 6.5 e 6.6), os resultados foram similares àquelesobtidos para o canal A, com o CMA convergindo para um mínimo local, enquanto o ELC-GA convergiu para o mínimo global. O CMA teve um desempenho geralmente melhorem relação ao ELC-GA quando seus parâmetros foram ajustados com Tad > K símbolos(o sistema 4-QAM usou 1000 símbolos, o sistema 16-QAM usou 1×104 e 64-QAM usou1×105).


0 5 10 15 2010

−5

10−4

10−3

10−2

10−1

Eb/N

0

BE

R

ELC-GA (Tad = 400 symbols)CMA (Tad = 400 symbols)CMA (Tad = 1 × 103 symbols)

Figura 6.4: Curva de desempenho de BER de um sistema 4-QAM em função de Eb/N0relativas ao canal B, hb(k) (ver equação (6.3)).

0 5 10 15 2010

−5

10−4

10−3

10−2

10−1

Eb/N

0

BE

R






0 5 10 15 2010

−5

10−4

10−3

10−2

10−1

Eb/N

0

BE

R





A análise da constelação na saída do equalizador fornece uma indicação da substancialdiferença de desempenho entre o equalizador CMA e do equalizador ELC-GA, usandorelação sinal-ruído de 30 dB e Tad = K. Enquanto o ELC-GA pôde fornecer constelaçõesvisualmente reconhecíveis (Figuras 6.7(a), 6.8(a), 6.9(a) e 6.10(a)), as constelações doequalizador CMA eram totalmente dispersas e irreconhecíveis (Figuras 6.7(b), 6.8(b),6.9(b) e 6.10(b)).


−1.5 −1 −0.5 0 0.5 1 1.5−1.5

−1

−0.5

0

0.5

1

1.5

aI(k − deq)

aQ(k

−deq)

(a) ELC-GA

−1 −0.5 0 0.5 1−1

−0.8

−0.6

−0.4

−0.2

0

0.2

0.4

0.6

0.8

1

aI(k − deq)

aQ(k

−deq)

(b) CMA

Figura 6.7: Diagrama de constelação do sinal recebido para o sistema 4-QAM, usando ocanal A, ha(k) (ver equação (6.2)), com Eb/N0 = 30 dB.

−4 −2 0 2 4−4

−3

−2

−1

0

1

2

3

4

aI(k − deq)

aQ(k

−deq)

(a) ELC-GA

−1.5 −1 −0.5 0 0.5 1 1.5−1.5

−1

−0.5

0

0.5

1

1.5

aI(k − deq)

aQ(k

−deq)

(b) CMA

Figura 6.8: Diagrama de constelação do sinal recebido para o sistema 16-QAM, usandoo canal A, ha(k) (ver equação (6.2)), com Eb/N0 = 30 dB.


−1.5 −1 −0.5 0 0.5 1 1.5−1.5

−1

−0.5

0

0.5

1

1.5

aI(k − deq)

aQ(k

−deq)

(a) ELC-GA

−1.5 −1 −0.5 0 0.5 1 1.5−1.5

−1

−0.5

0

0.5

1

1.5

aI(k − deq)

aQ(k

−deq)

(b) CMA

Figura 6.9: Diagrama de constelação do sinal recebido para o sistema 4-QAM, usando ocanal B, hb(k) (ver equação (6.3)), com Eb/N0 = 30 dB.

−4 −2 0 2 4−4

−3

−2

−1

0

1

2

3

4

aI(k − deq)

aQ(k

−deq)

(a) ELC-GA

−1.5 −1 −0.5 0 0.5 1 1.5−1.5

−1

−0.5

0

0.5

1

1.5

aI(k − deq)

aQ(k

−deq)

(b) CMA

Figura 6.10: Diagrama de constelação do sinal recebido para o sistema 16-QAM, usandoo canal B, hb(k) (ver equação (6.3)), com Eb/N0 = 30 dB.

6.3 Análise de convergência

Em todos os cenários (incluindo os com M > 4), o CMA convergiu, ou seja, não houvefalha na convergência do CMA. Entretanto, essa convergência requer um número maiorde iterações. Por exemplo, na Figura 6.6 (64-QAM, canal B) o CMA convergiu após1× 105 símbolos, diferente do ELC-GA, que precisou de apenas 1× 103 símbolos parater um desempenho semelhante.


Outro aspecto a ser levado em consideração é que o ELC-GA é um algoritmo deequalização em blocos. Conforme explicado no início do Capítulo 3, isso implica que essetipo de implementação permite uma maior complexidade de algoritmo. Mesmo sendo umalgoritmo mais complexo que o CMA, o ELC-GA necessita atualizar os parâmetros doequalizador somente a cada K símbolos, enquanto o outro necessita dessa atualizaçãoa cada símbolo. Essa configuração permite que, mesmo que o ELC-GA não consigaequalizar o canal em apenas um bloco de K símbolos, ele ainda possua uma margem detempo muito maior que o CMA para convergir para o mínimo global.

É importante ainda notar que, em nenhum dos métodos, o ponto de referência é gui-ado (sequência de treinamento), e que eles tem essencialmente as mesmas limitações.Enquanto o CMA tenta ajustar a constelação para um raio γ (ver Equação (3.10)), o ELC-GA tenta ajustar a constelação dentro de um quadrado cujas dimensões são limitadas por±Mτ1 e ±Mτ2. Em outras palavras, os desafios são de mesma magnitude para ambosmétodos. Mesmo assim, a comparação entre o CMA e o ELC-GA é justificada. Como afunção de custo do CMA (ver Equação (3.8)) possui muitos pontos de mínimos locais, aeficiência da convergência do método do gradiente descendente é altamente dependentedo passo de adaptação. Esse problema não ocorre no caso do ELC-GA.

Capítulo 7

Conclusões

Diante da necessidade atual de transmissões digitais com quantidades de dados cadavez maiores e com melhor qualidade, vários esforços tem sido realizados para melhorar osdiversos aspectos dos sistemas transmissores e receptores de dados digitais. Dentro dessecontexto, equalizadores cegos adaptativos tem ganhado destaque por não necessitarem deuso de banda do canal para transmissão de sinais de referência. Conforme mostrado noCapítulo 1, existem várias abordagens na literatura que propõem melhoria de desempenhopara a equalização adaptativa cega.

Este trabalho apresentou um novo esquema de equalização convexa, o ELC-GA, queutiliza uma abordagem baseada em algoritmos genéticos como algoritmo de equalizaçãoadaptativa, aplicado a sistemas de comunicações digitais. Diferentemente de propostasanteriores, o modelo considerou a característica estocástica do sinal de entrada do equali-zador, tornando a modelagem do sistema um problema de programação linear estocástica,e buscou nos algoritmos genéticos uma abordagem robusta para encontrar boas soluçõespara sinais com essa natureza.

O modelo proposto foi submetido a experimentos computacionais que o comparavamao método tradicional CMA, a fim de determinar seu desempenho em diferentes modelosde canais de transmissão. A viabilidade do ELC-GA foi confirmada pelos experimentos,uma vez que os resultados expostos no Capítulo 6, são competitivos com os resultadosobtidos pela outra abordagem.

O desempenho do esquema desenvolvido, em comparação ao desempenho do CMA,pode ser considerado melhor principalmente nos casos das modulações mais densas, umavez que conseguiu equalizar os canais depois de uma quantidade de símbolos substanci-almente menor que o CMA. Desse modo, os resultados obtidos indicam um avanço sig-nificativo no desenvolvimento de algoritmos eficientes para equalização cega, sugerindoque o novo esquema poderia ser aplicado em sistemas de comunicações reais.

CAPÍTULO 7. CONCLUSÕES 61

Trabalhos futuros

O esquema proposto neste trabalho representa uma contribuição significativa para aliteratura, não só por considerar um modelo de programação linear estocástica, comotambém pelos bons resultados obtidos quando comparados à abordagem tradicional men-cionada.

Porém, como em toda pesquisa, há sempre novos caminhos a serem percorridos.Nesse sentido, como trabalhos futuros pode-se sugerir uma análise mais detalhada dosmodelos de programação estocástica descritos na literatura, buscando neles uma melhoradequação ao modelo descrito neste trabalho. Além disso, tendo em vista a maior com-plexidade dos algoritmos genéticos frente à abordagens de programação numérica, ex-tensamente utilizadas na literatura, podem ser aliados aos algoritmos genéticos imple-mentações com estruturas de dados otimizadas, e também o uso de uma técnica de buscalocal, a fim de aumentar a capacidade de convergência dos algoritmos genéticos. Nessesentido, essas melhorias de desempenho poderiam incluir também abordagens metaheu-rísticas mais sofisticadas.

Outro ponto ainda pendente seria a comparação dos resultados obtidos pela aborda-gem tratada nesse texto com as outras abordagens descritas na literatura, tanto as queutilizam modelagem baseada em programação linear e métodos tradicionais de progra-mação linear, quanto as abordagens que utilizam algoritmos genéticos e a função custodo CMA.

Um trabalho relacionado ao descrito neste documento está atualmente em andamento,tratando-se do uso de programação linear para otimização de agrupamentos (arrays) deantenas adaptativas cegas.

Referências Bibliográficas

Beale, E. M. L. (1955), ‘On minimizing a convex function subject to linear inequalities’,Journal of the Royal Statistical Society. Series B (Methodological) 17(2), 173–184.

Benveniste, A. e M. Goursat (1984), ‘Blind equalizers’, Communications, IEEE Transac-

tions on 32(8), 871–883.

Benveniste, A., M. Goursat e G. Ruget (1980), ‘Robust identification of a nonminimumphase system: Blind adjustment of a linear equalizer in data communications’, IEEE

Transactions on Automatic Control 25(3), 385–399.

Birge, J. e F. Louveaux (2000), Introduction to Stochastic Programming, Springer Seriesin Operations Research and Financial Engineering, Springer New York.

Cantú-Paz, Erick e David E. Goldberg (2000), ‘Efficient parallel genetic algorithms:theory and practice’, Computer Methods in Applied Mechanics and Engineering

186(2–4), 221 – 238.

Charnes, A. e W. W. Cooper (1959), ‘Chance-constrained programming’, Management

Science 6(1), 73–79.

Cui, Tianxiang, Ruibin Bai, Andrew J. Parkes, Fang He, Rong Qu e Jingpeng Li (2015),A hybrid genetic algorithm for a two-stage stochastic portfolio optimization withuncertain asset prices., em ‘CEC’, IEEE, pp. 2518–2525.

Dantzig, George B. (1955), ‘Linear programming under uncertainty’, Management Sci-

ence 1(3-4), 197–206.

Dantzig, George B. e Mukund N. Thapa (1997), Linear Programming 1: Introduction, 1a

edição, Springer-Verlag New York.

Darwin, Charles (1859), On the Origin of Species by Means of Natural Selection, Or, The

Preservation of Favoured Races in the Struggle for Life, J. Murray.

62

REFERÊNCIAS BIBLIOGRÁFICAS 63

Dawkins, R. (1996), A Escalada do monte improvável: uma defesa da teoria da evolução,Companhia das Letras.

Ding, Zhi e Zhi-Quan Luo (2000), ‘A fast linear programming algorithm for blind equa-lization’, Communications, IEEE Transactions on 48(9), 1432–1436.

Fernandes, Marcelo A.C. (2015), ‘Linear programming applied to blind signal equaliza-tion’, {AEU} - International Journal of Electronics and Communications 69(1), 408– 417.

Gang, Xu e Lu Yourong (2009), Blind equalization based on a class of genetic algorithmsfor wireless communication, em ‘Proceedings of the 2009 International Forum onInformation Technology and Applications - Volume 01’, IFITA ’09, IEEE ComputerSociety, Washington, DC, USA, pp. 239–244.

Godard, D. (1980), ‘Self-recovering equalization and carrier tracking in two-dimensional data communication systems’, Communications, IEEE Transactions on

28(11), 1867–1875.

Goldbarg, M.C. e H.P.L. Luna (2005), Otimização combinatória e programação linear:

modelos e algoritmos, CAMPUS - RJ.

Goldberg, David E. (1989), Genetic Algorithms in Search, Optimization and Machine

Learning, 1a edição, Addison-Wesley Longman Publishing Co., Inc., Boston, MA,USA.

Guo, Yecai, Baoge Li e Kang Fan (2012), Support vector machine wavelet blind equa-lization algorithm based on improved genetic algorithm, em D.Jin e S.Lin, eds.,‘Advances in Electronic Commerce, Web Application and Communication: Volume2’, Springer Berlin Heidelberg, Berlin, Heidelberg, pp. 161–166.

Guo, Yecai e Kang Fan (2011), Blind equalization algorithm based on adaptive gene-tic algorithm and wavelet transform, em ‘Frontiers of Manufacturing and DesignScience’, Vol. 44 de Applied Mechanics and Materials, Trans Tech Publications,pp. 3215–3219.

Han, Soowhan, W. Pedrycz e Changwook Han (2005), ‘Nonlinear channel blind equali-zation using hybrid genetic algorithm with simulated annealing’, Mathematical and

Computer Modelling 41(6–7), 697 – 709.

Haykin (Editor), Simon (1994), Blind Deconvolution, Prentice Hall.


Haykin, Simon (2001a), Adaptative Filter Theory, 4a edição, Prentice Hall.

Haykin, Simon (2001b), Communication Systems, 4a edição, Wiley Publishing.

Haykin, Simon (2004), Sistemas de Comunicação: analógicos e digitais, 4a edição, Bo-okman.

Hillier, F.S. e G.J. Lieberman (2006), Introdução à Pesquisa Operacional, 8a edição,McGraw-Hil: São Paulol.

Holland, John H. (1962), ‘Outline for a logical theory of adaptive systems’, J. ACM

9(3), 297–314.

Holland, John H. (1973), ‘Genetic algorithms and the optimal allocation of trials’, SIAM

J. Comput. 2(2), 88–105.

Holland, John H. (1974), ‘Erratum: Genetic algorithms and the optimal allocation oftrials’, SIAM J. Comput. 3(4), 326.

Hosseini, Sara e Wout Dullaert (2011), 17 - robust optimization of uncertain logisticsnetworks, em R. Z.Farahani, S.Rezapour e L.Kardar, eds., ‘Logistics Operations andManagement’, Elsevier, London, pp. 359 – 370.

Jacklin, N., Z. Ding e Y. Li (2013), On efficient use of pilot symbols for multi-path chan-nel equalization of qam signals, em ‘2013 IEEE International Conference on Com-munications (ICC)’, pp. 5553–5558.

Johnson, C. R., P. Schniter, I. Fijalkow, L. Tong, A. Touzni, H. H. Zeng, M. Green e J. R.Treichler (1999), Unsupervised Adaptive Filtering, Wiley, New York, capítulo TheCore of FSE-CMA Behavior Theory.

Johnson, R., Jr., P. Schniter, T.J. Endres, J.D. Behm, D.R. Brown e R.A. Casas (1998),‘Blind equalization using the constant modulus criterion: a review’, Proceedings of

the IEEE 86(10), 1927–1950.

Kennedy, R. A. e Z. Ding (1992), ‘Blind adaptive equalizers for quadrature amplitudemodulated communication systems based on convex cost functions’, Optical Engi-

neering 31(6), 1189–1199.

Lin, H. e K. Yamashita (2002), ‘Hybrid simplex genetic algorithm for blind equalizationusing {RBF} networks’, Mathematics and Computers in Simulation 59(4), 293 –304.


Liu, Feng, Lin-Dong Ge, Ye jin Wu e Jia-Ming Li (2008), Blind equalization based onimmune optimized genetic algorithm, em ‘Signal Processing, 2008. ICSP 2008. 9thInternational Conference on’, pp. 1719–1721.

Luo, Zhi-Quan, Mei Meng, Kon Max Wong e Jian-Kang Zhang (2002), ‘A fractionallyspaced blind equalizer based on linear programming’, Signal Processing, IEEE

Transactions on 50(7), 1650–1660.

Ma, Xiao-ming e Fan Zhang (2002), ‘A genetic algorithm based stochastic programmingmodel for air quality management’, Journal of Environmental Sciences 14(3), 367–374.

Masatoshi Sakawa, Ichiro Nishizaki, Hideki Katagiri (2011), Fuzzy Stochastic Multiob-

jective Programming, Springer New York.

Matlab (n.d.), ‘Create genetic algorithm options structure’, http://www.mathworks.com/help/gads/gaoptimset.html.

Merabti, H. e D. Massicotte (2014), Nonlinear adaptive channel equalization using gene-tic algorithms, em ‘New Circuits and Systems Conference (NEWCAS), 2014 IEEE12th International’, pp. 209–212.

Michalewicz, Zbigniew (1996), Genetic Algorithms + Data Structures = Evolution Pro-

grams (3rd Ed.), Springer-Verlag, London, UK, UK.

Mohammed, Jafar Ramadhan (2012), ‘A study on the suitability of genetic algorithm foradaptive channel equalization’, International Journal of Electrical and Computer

Engineering (IJECE) 2(3), 285–292.

Muhammad, M. e Z. Ding (2010), ‘A linear programming receiver for blind detec-tion of full rate space-time block codes’, IEEE Transactions on Signal Processing

58(11), 5819–5834.

Pandey, Rajoo (2004), ‘Complex-valued neural networks for blind equalization of time-varying channels’.

Picchi, G. e G. Prati (1987), ‘Blind equalization and carrier recovery using a"stop-and-go"decision-directed algorithm’, IEEE Transactions on Communications

35(9), 877–887.


Poojari, Chandra A. e Boby Varghese (2008), ‘Genetic algorithm based technique forsolving chance constrained problems’, European Journal of Operational Research

185, 1128–1154.

Proakis, John G. (2000), Digital Communications, Mcgraw-Hill College.

Qin, Xiaosheng, Guohe Huang e Lei Liu (2010), ‘A genetic-algorithm-aided stochasticoptimization model for regional air quality management under uncertainty’, Journal

of the Air & Waste Management Association 60(1), 63–71.

Sahinidis, Nikolaos V. (2004), ‘Optimization under uncertainty: state-of-the-art and op-portunities’, Computers & Chemical Engineering 28(6–7), 971 – 983.

Sato, Y. (1975), ‘A method of self-recovering equalization for multilevel amplitude-modulation systems’, IEEE Transactions on Communications 23(6), 679–682.

Sen, Suvrajeet e Julia L. Higle (1999), ‘An introductory tutorial on stochastic linear pro-gramming models’, Interfaces 29(2), 33–61.

Shalvi, O. e E. Weinstein (1990), ‘New criteria for blind deconvolution of nonminimumphase systems (channels)’, IEEE Transactions on Information Theory 36(2), 312–321.

Surajudeen-Bakinde, N., Xu Zhu, Jingbo Gao, A.K. Nandi e Hai Lin (2011), Genetic al-gorithm based frequency domain equalization for ds-uwb systems without guard in-terval, em ‘Communications (ICC), 2011 IEEE International Conference on’, pp. 1–5.

Tugnait, J. K., Lang Tong e Zhi ding (2000), ‘Single-user channel estimation and equali-zation’, IEEE Signal Processing Magazine 17(3), 16–28.

Wang, K.-J., S.-M. Wang e J.-C. Chen (2008), ‘A resource portfolio planning model usingsampling-based stochastic programming and genetic algorithm’, European Journal

of Operational Research 184(1), 327 – 340.

Yecai Guo, Lu Lu, Binglong Zhang (2015), An orthogonal wavelet transform multi-modulus blind equalization algorithm based on tabu search dna genetic optimiza-tion algorithm, em ‘Proceedings of the 2015 International Conference on MaterialsEngineering and Information Technology Applications’, Advances in EngineeringResearch, Atlantis Press.


Yoshitomi, Yasunari, Hiroko Ikenoue, Toshifumi Takeba e Shigeyuki Tomita (2000), ‘Ge-netic algorithm in uncertain environments for solving stochastic programming pro-blem’, Journal of the Operations Research Society of Japan 43(2), 266–290.

Zaouche, A., I. Dayoub e J.M. Rouvaen (2008), ‘Baud-spaced constant modulus blindequalization via hybrid genetic algorithm and generalized pattern search optimiza-tion’, {AEU} - International Journal of Electronics and Communications 62(2), 122– 131.

Zhu, Ting-Ting (2015), Optimized algorithm design applicable to channel blind equaliza-tion, em ‘Wireless Communication and Network - Proceedings of 2015 InternationalWorkshop’, World Scientific Publishing Company Pte Limited, pp. 1–6.

Documents

Proposta de Equalizador Cego Baseado em Algoritmos Genéticos