A escolha do tamanho da população é um fator importante na determinação do custo computacional e da qualidade das soluções obtidas pelos algoritmos evo- lucionários. Com uma população pequena, o desempenho pode ser comprometido, pois deste modo a população fornece uma pequena cobertura do espaço de busca do problema. Uma grande população geralmente fornece uma cobertura represen- tativa do domínio do problema, além de prevenir convergências prematuras para soluções locais ao invés de globais. No entanto, para se 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 e possivelmente desnecessário.
O tamanho da população mais adequado para cada tipo de problema de oti- mização, visando a minimização do custo computacional é um interessante tópico de pesquisa que vem sendo estudado desde o trabalho de Holland (HOLLAND, 1975). Em 1975, De Jong (JONG, 1975), baseado em (HOLLAND, 1975), reconhe-
ceu a importância do ruído no processo de decisão propondo uma estimativa para o tamanho da população baseada nas características do sinal e do ruído presentes no problema. Infelizmente, ele não a utilizou no restante do seu trabalho e o resul-
tado acabou não sendo verificado, caindo em esquecimento. Só em 1991, Goldberg e Rudnick (GOLDBERG; RUDNICK, 1991) desenvolveram a primeira equação para
o tamanho da população baseada na variância da função custo. No ano seguinte, Goldberg, Deb e Clark (GOLDBERG; DEB; CLARK, 1992) encontraram um limite
conservador para o tamanho da população, garantindo certo nível de qualidade de convergência dos algoritmos.
Em 1999, Harik et al. (HARIK et al., 1999), baseados em (GOLDBERG; DEB; CLARK, 1992), desenvolveram uma equação para o tamanho da população inspi-
rados no clássico problema do caminho aleatório (random walk): particularmente, analisou-se o problema da ruína do jogador (gambler’s ruin). Usando problemas simples e complicados como teste, Harik et al. demonstraram a acurácia do mo- delo proposto. No entanto, o resultado do trabalho de Harik et al. é limitado apenas a problemas onde o tamanho do indivíduo é constante, além de requerer informações estocásticas sobre a variância (ruído) e diferença média esperada (si- nal) da função custo entre o segundo e primeiro bloco de construção. Em muitos problemas práticos, estas informações são impossíveis ou muito difíceis de serem obtidas com acurácia. A expressão encontrada por Harik et al. é dada por:
p =−2k−1ln (α)σf d
√
πm′ (3.17)
onde p é o tamanho da população, ou de forma equivalente, a quantidade de indi- víduos que o algoritmo processa por geração, k é a ordem do bloco de construção; α = 1− Pb é a probabilidade do algoritmo evolucionário falhar na etapa de de-
cisão, ou seja, Pb é a probabilidade de acerto; σf é a variância (ruído) da função
custo; d é a diferença média esperada (sinal) da função custo entre o segundo e o primeiro bloco de construção; e m′ = m− 1, sendo m = Qindiv
k e Qindiv o tamanho
do candidato.
Posteriormente, Ahn e Ramakrishna (AHN; RAMAKRISHNA, 2002) estende-
ram o estudo realizado em (HARIK et al., 1999) encontrando uma expressão geral
razoável, fácil de ser obtida, para o tamanho da população sem a necessidade de se conhecer as características estocásticas do sinal e do ruído, além de possibili- tar sua utilização em problemas de tamanho variável. Esta expressão necessita apenas das informações básicas do problema, como cardinalidade do alfabeto (l), ordem do bloco de construção (k), tamanho do indivíduo (Qindiv) e probabilidade
de falha do algoritmo genético na etapa de decisão (α), sendo dada por: p =−l k 2 ln (α) lk− 1 2 √ πm′+ 1 (3.18)
Este trabalho utiliza a equação (3.18) para encontrar o tamanho adequado da população para o problema da detecção multiusuário e da estimativa de pa- râmetros de sistema. A utilização da equação (3.18) é conveniente, pois permite que o tamanho da população seja determinada apenas na etapa de inicialização do algoritmo evolucionário, sendo mantido constante em todas as gerações.
Para o problema onde os sinais são digitais binários, o alfabeto (binário) implica em l = 2 e a ordem do bloco de construção unitário implica em k = 1. Assim, reescrevendo a equação (3.18) para o problema de sinais binários, resulta em:
p = − ln (α)0, 5pπ (Qindiv− 1) + 1
(3.19) Neste trabalho, considerou-se Pb = 99, 9% como sendo a máxima percentagem
de acerto. Além disso, visando evitar tamanhos de população fracionários ou com aumento unitário, derivou-se uma população de tamanho inteiro com crescimento considerando multiplicidade de 10 indivíduos8. Reescrevendo a equação (3.19),
resulta em: p = 10· − ln (1 − 0, 999) 0, 5pπ (Qindiv− 1) + 1 10 (3.20)
Manipulando os valores, resulta em uma expressão geral dada por: p = 10·j0, 3454pπ (Qindiv− 1) + 2
k
(3.21) onde o operador ⌊x⌋ retorna o maior inteiro inferior a x.
A figura 3.1 sintetiza o comportamento da equação (3.19) para diversos valores de Pb e Qindiv, bem como o tamanho da população obtido via equação (3.21).
Observa-se que a adoção da equação (3.21) garante uma confiabilidade acima dos 99% para qualquer valor de Qindiv e entre 99, 7% à 99, 9% para Qindiv > 60.
Logicamente, o tamanho do indivíduo (Qindiv) para o problema MuD é di-
ferente do tamanho do indivíduo para o problema da estimativa de parâmetro com codificação binária. Para o problema MuD, o tamanho do indivíduo candi- dato é dado pelo número de usuários virtuais multiplicado pelo número de bits transmitidos, ou seja:
Qindiv = m.k = KvI (3.22)
8O uso da multiplicidade visa facilitar a implementação das etapas de reprodução que atu-
arão somente com tamanho de populações inteiras e facilmente fracionadas pelos operadores genéticos.
0 50 100 150 200 250 0 10 20 30 40 50 60 70 80 90 100 110 Tamanho do Indivíduo Tamanho da População P b = [0,99 : 0,001 : 0,999] Adotado 0,99 0,999
Figura 3.1: Equação (3.19) e equação (3.21) para os intervalos de confiança (Pb) iniciando em 0,99 até 0,999 com incremento de 0,001 e tamanhos de
população entre 1 e 250 indivíduos.
Já para o problema da estimativa de parâmetros, o tamanho do indivíduo depende do tipo de codificação adotado, resultando em:
• Codificação tipo I:
Qindiv = 2KL (Qint+ Qfrac) (3.23)
• Codificação tipo II:
Qindiv = 4KLQint (3.24)
• Codificação tipo III:
Qindiv = 2KL (Qabs+ Qphs) (3.25)