CAPÍTULO 4

RESULTADOS NUMÉRICOS

Neste capítulo são apresentados os resultados numéricos decorrentes da aplicação da versão computacional do modelo discutido no Capítulo 3.

Este capítulo desenvolve-se dos tópicos básicos, onde são apresentadas as diversas características dos problemas testados e a determinação dos valores empregados nos parâmetros do algoritmo genético, até a apresentação dos resultados obtidos.

4.1 Características dos Problemas Testados

A fim de testar o desempenho do modelo, 26 diferentes problemas coletados da literatura foram empregados, cujos dados são mostrados no Anexo I. O número de atividades nestes problemas varia entre 7 e 80. Os tipos de recursos empregados variam de 2 a 10 e o número médio de modos de execução por atividade para cada projeto varia entre 1,14 e 2,87. A complexidade das redes varia entre 5,78 e 69,82.

Por outro lado, seguindo a divisão sugerida por Boctor (1990), os projetos foram divididos em dois grupos: problemas pequenos, para projetos com número total de atividades menores de 30 e problemas grandes, para redes com número de atividades maior ou igual a 30. Dentro desta classificação, 7 projetos são considerados grandes e 19 são pequenos.

A Tabela 4.1 resume as características de cada um dos problemas empregados no experimento.

4.2 Parâmetros do Algoritmo Genético

Como já foi salientado no Capítulo 3, a determinação dos valores apropriados dos parâmetros do algoritmo genético é um processo de tentativa e erro. Na presente aplicação os testes foram efetuados com um único intuito, adequar os valores reconhecidos na literatura aos problemas experimentados.

Neste sentido, a Tabela 4.2 mostra as diferentes combinações do número de gerações e tamanho de população experimentados.

Para avaliar a sensibilidade do modelo a estes parâmetros e encontrar a melhor combinação, quatro problemas foram selecionados. Dois projetos pequenos (problemas 25 e 26) com diferentes graus de complexidades e, dois projetos considerados grandes (problemas 6 e 24). Três dos quatro problemas escolhidos possuem solução ótima conhecida. O número de vezes, de um total de 5 execuções por projeto, em que a solução ótima foi atingida, além da análise do incremento da qualidade das soluções obtidas em relação ao tempo computacional empregado, determinou o valor dos parâmetros a serem empregados. Para o caso do problema que não tem solução ótima conhecida, optou-se pela análise do número de vezes que a menor solução foi obtida. Os resultados são ilustrados na Tabela 4.3.

Os resultados obtidos, para o total dos experimentos executados, mostraram que o operador de cruzamento CX é mais sensível ao aumento do tamanho da população do que ao incremento no número de gerações. Este comportamento, observado para o teste piloto efetuado com os quatro problemas citados, foi constatado também nas execuções de outros projetos selecionados aleatoriamente no decorrer dos testes. Ficou evidente, através dos resultados observados, que o operador é sensível à qualidade dos elementos da população inicial. Uma das principais desvantagens deste operador, relatadas na literatura, é a convergência muito rápida para soluções (imaturas) sub-ótimas. Entretanto, esta desvantagem não foi evidenciada no decorrer da experiência. Acreditamos que a utilização do Fator Ponderado de Utilização dos Recursos (FPUR), contribuiu para propiciar uma discriminação maior dos elementos das populações, evitando assim, a dominância nas primeiras gerações dos elementos mais aptos.

Os valores empregados para as probabilidades de cruzamento e de mutação, para todos os experimentos, foram P_c = 0.99 e P_m = 0.001. A taxa de elitismo empregada foi 10% da população.

4.3 Medidas de Desempenho para o Modelo

Como mencionado no Capítulo 3, a eficiência do modelo é baseada na comparação da melhor duração final observada para o projeto com os resultados publicados nos estudos de Badiru (1988) e Li e Willis (1992).

Cabe ressaltar que o modelo foi aplicado aos 26 projetos utilizados no experimento, para cada um dos dois conjuntos de testes definidos na seção 3.5.2, totalizando 52 problemas. Cada problema foi processado cinco vezes, representado um total de 260 observações.

Além das tradicionais medidas de desempenho relatadas na seção 3.5.3 do Capítulo 3, a seguinte medida também foi empregada:

Taxa de Eficiência Heurística (Badiru 1988). Para cada regra m, a taxa para cada problema teste é dada por:

, m = 1,2,..., M, n = 1,2,...,N (4.1)

onde,

r _mn = taxa de eficiência da regra m para o problema n,

q_n = min_m {Pl_mn}

duração mínima de projeto observada para o problema n,

PL_mn = duração do projeto para o problema teste n aplicando a regra m,

M = número de regras heurísticas consideradas,

N = número de problemas testes.

Se a duração mínima global de um projeto é conhecida, então ela é empregada na expressão r_mn substituindo o valor de q_n.

A taxa de melhoria da duração mínima obtida pelo modelo relativamente à melhor heurística relatada nos estudos referenciados, foi calculada como:

(4.2)

onde,

D_n = taxa de melhoria;

DH_n = duração do projeto n para a melhor heurística reportada;

DAG_n = menor duração observada para o projeto n, obtida através do modelo proposto.

Por outro lado, é calculada a taxa de atraso de cada projeto, da forma definida na seção 3.5.3 como:

(4.3)

onde,

A_n = taxa de atraso;

DCC_n = duração do projeto n calculado sem restrição de recursos;

DAG_n = menor duração observada para o projeto n, obtida através do modelo proposto.

Visando medir a melhoria da solução encontrada pelo modelo proposto (para o caso de modo único) em relação ao emprego de múltiplos modos, foi adotado o critério:

(4.4)

onde,

SM_n = taxa de melhoria com múltiplos modos;

DMM_n = duração do projeto n calculado para o caso de múltiplos modos;

DUM_n = menor duração observada para o projeto n, obtida através do modelo proposto para o modo único.

O uso da soma para cada uma das taxas r_mn, D_n, A_n, e SM_n é uma abordagem prática que permite avaliar o desempenho do modelo sobre o total dos problemas experimentados.

Os valores numéricos destes cálculos são relatados na seguinte seção.

4.4 Resultados Numéricos da Comparação

Os problemas testados foram divididos em dois grupos, de acordo com a procedência dos resultados a serem comparados: o primeiro grupo envolvendo os problemas testados por Badiru (1988) e o segundo grupo, os problemas experimentados por Li e Willis (1992). As tabelas 4.4 e 4.5 mostram a comparação das durações dos projetos encontradas pelo algoritmo e as durações relacionadas a cada uma das heurísticas estudadas por estes autores.

As tabelas 4.6 e 4.7 ilustram a comparação das taxas de eficiência para os dois grupos de problemas experimentados.

Cabe notar que, inicialmente, todos os problemas foram processados considerando um único modo de execução para as atividades. Em seguida o modelo foi aplicado para o caso de múltiplos modos e calculadas as taxas de melhoria da solução em relação ao único modo. Também foi registrado o incremento, em termos relativos, do tempo computacional empregado para processar cada uma das opções.

A tabela 4.8 ilustra uma compilação das diversas durações encontradas para os projetos. A coluna da melhor heurística representa a duração mínima, reportada nos trabalhos referenciados, para o problema em questão. A duração sem restrição foi determinada usando o método tradicional do Caminho Crítico, relaxando os limites impostos aos recursos. A duração obtida pelo modelo é ilustrada na quinta coluna. Esta duração representa a mínima observada para as cinco iterações realizadas com cada problema, desde que o número de vezes em que ela foi obtida, tenha sido igual ou superior a dois. A tabela é completada com duas colunas que mostram a duração média de projeto, observada no processamento do algoritmo, para os casos de único e múltiplos modos.

Baseado nestes dados é calculada a taxa de melhoria da qualidade da solução do problema, obtida por meio do algoritmo proposto, em relação à heurística de desempenho superior para cada problema, como ilustrado na Tabela 4.9.

Por outro lado, a Tabela 4.10 mostra a melhoria das soluções dos problemas, obtidas pela aplicação do modelo em relação a melhor heurística global reportada em cada um dos estudos referenciados (baseado nas conclusões de Badiru e Li e Willis).

O desempenho do modelo em relação ao tamanho dos problemas experimentados é ilustrado nas Tabelas 11 e 12.

Entretanto, cabe salientar que a intenção de usar o tempo computacional como critério de desempenho não é o de comparar diferentes heurísticas. No presente trabalho, os objetivos principais de medir o tempo empregado foram: avaliar o desempenho do modelo quanto às características dos projetos experimentados e comparar as soluções usando modo único versus o emprego de múltiplos modos.