Research setting

A primeira análise visa mostrar a qualidade da solução da versão paralela proposta do Si-

mulated Annealing Acoplado. Além de verificar a qualidade numérica da solução, já que é

conhecido antecipadamente o valor mínimo de cada função, o CSA serial é utilizado para com- parar os resultados.

Na Tabela 5.3, a seguir, um conjunto simplificado de resultados obtidos nos experimentos é mostrado. Ele inclui o valor da solução ótima, da pior, da média e o desvio padrão para 25 execuções do algoritmo utilizando 24 otimizadores, além do tempo médio de execução em

CAPÍTULO 5. EXPERIMENTOS E RESULTADOS 52

segundos, tanto para a versão serial como paralela do CSA. Para cada uma das execuções, o critério de parada é 1.000.000 avaliações da função de custo. As avaliações serão divididas entre os otimizadores. Dessa forma, na média, cada otimizador realizará aproximadanente 41.667 avaliações do custo. Esse valor pode ser diferente para o CSA paralelo, o que na atual fase não é importante, pois, devido à implementação do CSA observado na Figura 4.2, alguns otimizadores poderão adentrar a região crítica mais que outros.

Tabela 5.3 – Qualidade de solução do Simulated Annealing (SA), do Coupled Simulated Annealing

(CSA) serial e paralelo para D= 10, 25 execuções. O CSA é executado com 24 otimizadores. O CSA é executado com 24 otimizadores. Das 25 execuções, resgata-se a melhor solução, a pior solução, bem como calcula-se a média, o desvio padrão e o tempo médio de execução em segundos dos algoritmos.

Função Algoritmo Melhor Pior Média das Desvio Tempo Solução Solução Soluções Padrão Médio

f1

SA 5.75E-006 1.81E-005 1.35E-005 3.55E-006 1.53E+000 CSA Serial 5.90E-006 2.38E-005 1.55E-005 4.61E-006 1.30E+000

CSA Paralelo 8.42E-007 2.91E-006 1.73E-006 5.34E-007 2.24E+000

f2

SA 1.39E-005 3.72E-005 2.59E-005 6.04E-006 1.55E+000 CSA Serial 3.43E-003 4.23E+000 1.03E+000 1.35E+000 1.32E+000

CSA Paralelo 2.18E-005 5.91E-004 1.16E-004 1.12E-004 2.52E+000

f3

SA 1.96E-003 3.37E-003 2.53E-003 3.34E-004 2.11E+000 CSA Serial 1.05E-002 5.50E-002 2.51E-002 1.07E-002 1.86E+000

CSA Paralelo 2.71E-003 5.46E-003 4.35E-003 8.18E-004 2.04E+000

f4

SA 1.25E-002 1.08E-001 5.30E-002 2.53E-002 2.39E+000 CSA Serial 4.75E-002 3.41E-001 1.29E-001 6.14E-002 2.13E+000

CSA Paralelo 4.07E-003 4.81E-002 1.96E-002 1.16E-002 2.57E+000

f5

SA 2.60E-002 3.69E-002 3.17E-002 2.82E-003 7.61E+001 CSA Serial 1.11E-001 4.89E-001 1.81E-001 7.81E-002 7.60E+001 CSA Paralelo 3.95E-002 6.35E-002 5.40E-002 7.27E-003 3.42E+000

f6

SA 2.73E-005 5.58E-005 3.98E-005 7.66E-006 2.01E+000 CSA Serial 6.95E-004 9.97E-001 1.29E-001 3.01E-001 1.80E+000

CSA Paralelo 5.14E-005 2.51E-004 1.43E-004 5.31E-005 2.34E+000

f7

SA 2.20E-005 5.55E-005 3.83E-005 9.77E-006 2.02E+000 CSA Serial 7.03E-004 3.75E-002 7.18E-003 1.04E-002 1.83E+000

CSA Paralelo 4.57E-005 2.16E-004 1.34E-004 4.05E-005 2.37E+000

f8

SA 1.71E-001 2.37E+002 3.97E+001 6.69E+001 2.36E+000 CSA Serial 4.74E+002 1.70E+003 9.89E+002 3.56E+002 2.12E+000

CAPÍTULO 5. EXPERIMENTOS E RESULTADOS 53

CSA Paralelo 1.19E+002 5.92E+002 2.36E+002 1.23E+002 2.30E+000

f9

SA 3.98E-001 4.12E-001 4.05E-001 5.67E-003 1.59E+000 CSA Serial 3.98E-001 4.14E-001 4.07E-001 6.90E-003 1.35E+000

CSA Paralelo 3.89E-001 4.12E-001 4.04E-001 1.04E-002 1.93E+000

f10

SA 3.00E+000 8.40E+001 3.34E+001 3.22E+001 1.53E+000 CSA Serial 3.00E+000 3.08E+001 1.95E+001 1.32E+001 1.31E+000

CSA Paralelo 3.00E+000 3.05E+001 1.93E+001 1.29E+001 2.00E+000

f11

SA 1.62E-011 1.46E-001 7.89E-002 7.41E-002 1.64E+000 CSA Serial 1.71E-009 7.50E-006 3.83E-007 1.49E-006 1.39E+000

CSA Paralelo 1.25E-011 9.41E-010 2.37E-010 2.79E-010 1.84E+000

f12

SA 3.16E-006 8.58E-006 6.23E-006 1.42E-006 2.16E+000 CSA Serial 2.18E-006 8.49E-006 4.71E-006 1.67E-006 1.94E+000

CSA Paralelo 2.38E-007 9.02E-007 5.55E-007 2.02E-007 2.54E+000

f13

SA 4.14E-018 3.81E-013 4.33E-014 7.95E-014 1.55E+000 CSA Serial 5.78E-013 3.19E-010 3.65E-011 6.44E-011 1.31E+000

CSA Paralelo 1.65E-016 5.83E-013 5.88E-014 1.20E-013 1.92E+000

f14

SA 7.23E-010 2.09E-008 8.71E-009 5.84E-009 1.61E+000 CSA Serial 3.19E-010 4.08E-009 1.47E-009 8.78E-010 1.38E+000

CSA Paralelo 1.82E-012 1.07E-010 3.91E-011 3.09E-011 1.81E+000

Fonte: Dados dos experimentos, 2013.

As soluções encontrados na Tabela 5.3 são boas e se aproximam do ótimo. O CSA para- lelo obteve soluções melhores ou próximo as que o CSA serial em todas as funções analisadas. No CSA serial os otimizadores são executados um a um, sequencialmente, e somente o último realiza a operação de atualização de temperatura (encontrada em Atualizar Temperaturas na Figura 4.2), i.e., todos os 24 otimizadores tem maior probabilidade de realizar ou refinamento ou exploração ao mesmo tempo (a cada ciclo de 24 avaliações da função custo). Já no CSA paralelo, o refinamento e exploração pode ocorrer no meio de um desses ciclos, afinal, a qual- quer momento um otimizador pode adentrar a região critica e alterar a temperatura. Ou seja, parte dos otimizadores realizam refinamento e parte realizam exploração. Ainda mais, como a alternância entre refinamento e exploração não é feita em momentos exatos, espera-se que os otimizadores do CSA paralelo se distribuam melhor no espaço de busca, o que acarreta me- lhores soluções finais. Este mesmo motivo explica os pequenos desvios padrões das soluções encontradas, chegando em 10−11no serial, e 10−13no paralelo.

Entretanto, nem todos os resultados do CSA paralelo foram melhores que do Simulated

CAPÍTULO 5. EXPERIMENTOS E RESULTADOS 54

fixo, cada otimizador realiza poucas iterações, pois estas serão divididas pelos otimizadores. Isso pode dificultar a busca de soluções melhores porque os otimizadores podem não realizar iterações suficientes para uma bom refinamento e exploração.

O tempo médio de execução do CSA paralelo para a maioria das funções foi maior que o do SA e CSA serial. A inserção da região crítica no CSA paralelo cria overheads no algoritmo. Quanto maior a quantidade de otimizadores, maior será o tempo desperdiçado em overhead. Ademais, a baixa dimensão das funções implica em uma menor carga computacional a ser processada. Como as funções são avaliadas individualmente por cada otimizador, isto é, na região paralela do código, o CSA paralelo não obtêm um melhor desempenho por não possuir uma carga de trabalho elevada. A exceção ocorre com a função f5. Ela possui um elevado custo

computacional de processamento, e, devido a isso, o CSA paralelo possui um melhor tempo médio de processamento.

A Tabela 5.4 descreve os resultados obtidos das 25 execuções do SA e CSA com 24 otimi- zadores e 160 dimensões. De maneira geral, as soluções foram boas e estão próximas do ótimo global. Assim como no caso anterior, a qualidade da solução final do CSA paralelo é melhor que os resultados obtidos pela versão serial, mas, em alguns casos, pior que do Simulated Anne- aling. Quando comparado às soluções encontradas com 10 dimensões, os resultados são piores. Entretanto, como a dimensão é 16 vezes maior, o tamanho do problema e a sua complexidade tendem a aumentar e dificultam, na maioria dos casos, a busca das boas soluções. Apesar disso, o tempo médio de solução do CSA paralelo para a 160 dimensões foi inferior em todos os casos.

Tabela 5.4 – Qualidade de solução do Simulated Annealing (SA), do Coupled Simulated Annealing

(CSA) serial e paralelo para D= 160, 25 execuções. O CSA é executado com 24 oti- mizadores. Das 25 execuções, resgata-se a melhor solução, a pior solução, bem como calcula-se a média, o desvio padrão e o tempo médio de execução dos algoritmos.

Função Algoritmo Melhor Pior Média das Desvio Tempo Solução Solução Soluções Padrão Médio

f1

SA 3.38E-004 4.17E-004 3.86E-004 1.87E-005 2.24E+001 CSA Serial 3.85E-002 5.48E-001 2.46E-001 1.56E-001 2.17E+001 CSA Paralelo 2.38E-004 2.28E-001 5.34E-002 5.93E-002 4.15E+000

f2

SA 6.52E+001 1.33E+002 1.16E+002 1.38E+001 2.27E+001 CSA Serial 1.57E+002 1.61E+002 1.59E+002 1.49E+000 2.20E+001 CSA Paralelo 1.55E+002 1.59E+002 1.57E+002 8.85E-001 4.17E+000

f3

SA 6.72E-003 7.71E-003 7.15E-003 2.36E-004 3.04E+001 CSA Serial 6.93E-001 1.99E+000 1.35E+000 3.88E-001 3.03E+001 CSA Paralelo 1.63E-002 2.61E-001 5.53E-002 6.60E-002 4.02E+000

f4

CAPÍTULO 5. EXPERIMENTOS E RESULTADOS 55

CSA Serial 9.42E-001 1.51E+000 1.26E+000 1.20E-001 3.25E+001 CSA Paralelo 1.12E-002 1.14E+000 6.55E-001 2.92E-001 4.13E+000

f5

SA 1.20E+000 3.77E+000 1.52E+000 5.77E-001 1.12e+003 CSA Serial 1.19E+001 1.75E+001 1.49E+001 1.37E+000 1.12E+003 CSA Paralelo 2.45E+000 5.52E+000 4.02E+000 7.89E-001 4.73E+001

f6

SA 1.10E+001 4.08E+001 2.32E+001 6.89E+000 3.18E+001 CSA Serial 5.51E+000 2.46E+001 1.45E+001 5.83E+000 2.92E+001 CSA Paralelo 2.14E-002 9.86E+000 3.81E+000 2.37E+000 4.12E+000

f7

SA 1.40E+001 3.00E+001 2.12E+001 4.50E+000 3.22E+001 CSA Serial 2.07E+000 2.22E+001 1.28E+001 5.45E+000 2.94E+001 CSA Paralelo 5.11E-001 6.75E+000 3.04E+000 1.77E+000 4.03E+000

f8

SA 6.58E+003 1.00E+004 7.99E+003 9.62E+002 3.61E+001 CSA Serial 4.18E+004 4.86E+004 4.61E+004 1.59E+003 3.50E+001 CSA Paralelo 3.94E+004 4.59E+004 4.25E+004 1.88E+003 4.02E+000

f9

SA 3.98E-001 2.71E+000 4.94E-001 4.71E-001 2.23E+001 CSA Serial 4.01E-001 5.01E-001 4.58E-001 4.34E-002 2.14E+001 CSA Paralelo 3.82E-001 4.97E-001 4.52E-001 5.07E-002 4.02E+000

f10

SA 3.00E+000 8.40E+001 3.11E+001 3.03E+001 2.22E+001 CSA Serial 3.00E+000 3.00E+001 2.68E+001 8.95E+000 2.13E+001 CSA Paralelo 3.00E+000 8.30E+001 1.08E+001 1.83E+001 4.14E+000

f11

SA 5.86E-013 1.46E-001 5.46E-002 7.20E-002 2.23E+001 CSA Serial 2.04E-011 4.79E-009 5.13E-010 1.18E-009 2.14E+001 CSA Paralelo 9.63E-014 1.43E-011 3.01E-012 3.59E-012 4.00E+000

f12

SA 3.35E-004 4.15E-004 3.78E-004 1.75E-005 3.37E+001 CSA Serial 3.89E-002 5.27E-001 3.09E-001 1.44E-001 3.30E+001 CSA Paralelo 2.02E-004 2.29E-001 4.83E-002 5.68E-002 4.14E+000

f13

SA 8.69E-019 1.94E-015 2.67E-016 5.12E-016 2.22E+001 CSA Serial 1.89E-016 2.33E-011 1.31E-012 4.64E-012 2.14E+001 CSA Paralelo 1.66E-018 1.11E-014 1.02E-015 2.36E-015 3.97E+000

f14

SA 2.83E-011 2.33E-009 9.22E-010 6.00E-010 2.24E+001 CSA Serial 2.58E-013 5.32E-011 1.95E-011 1.28E-011 2.14E+001 CSA Paralelo 6.03E-014 6.73E-012 1.54E-012 1.61E-012 4.20E+000

Fonte: Dados dos experimentos, 2013.

CAPÍTULO 5. EXPERIMENTOS E RESULTADOS 56

execuções das versões serial e paralela do CSA com 24 otimizadores. Serão exibidas as médias para as dimensões 10, 20, 40, 80 e 160. Os gráficos são dividos em três grupos, conforme se caracteriza as funções de referência encontradas na Seção 5.1. Cada função tem exibida a sua média para o CSA serial e paralelo.

Figura 5.4 – Média das soluções do grupo 1 de funções de referência utilizando o CSA com 24

otimizadores. 0 20 40 60 80 100 120 140 160 -8 -6 -4 -2 0 2 4 L o g1 0 (M éd ia ) Dimensão f1serial f1paralelo f2serial f2paralelo

Fonte: Dados dos experimentos, 2013.

A Figura 5.4 exibe em escala logarítmica o valor médio das soluções das funções do grupo 1 para 25 execuções da versão serial do Simulated Annealing Acoplado com 24 otimizadores, sendo aplicada a versão serial e paralela. Como as duas funções desse grupo são ditas fáceis de otimizar, espera-se boa média das soluções encontradas mesmo com a maiores dimensões do problema. A média de soluções da versão paralela são melhores ou parecidas com as soluções da versão serial.

Figura 5.5 – Média das soluções do grupo 2 de funções de referência utilizando o CSA com 24

otimizadores. (a) Funções f3, f4e f5 0 20 40 60 80 100 120 140 160 -6 -4 -2 0 2 4 6 L o g10 (M éd ia ) Dimensão f3serial f3paralelo f4serial f4paralelo f5serial f5paralelo (b) Funções f6, f7e f8 0 20 40 60 80 100 120 140 160 -6 -4 -2 0 2 4 6 L o g10 (M éd ia ) Dimensão f6serial f6paralelo f7serial f7paralelo f8serial f8paralelo

CAPÍTULO 5. EXPERIMENTOS E RESULTADOS 57

A análise do grupo 2 utilizando o CSA paralelo, exibido nas Figuras 5.5(a) e 5.5(b), mostra o crescimento da média das soluções para a maioria das funções. Entretanto, apesar deste crescimento, as médias das soluções do CSA paralelo foram melhores que a versão serial.

Para o último caso, as Figuras 5.6(a) e 5.6(b) mostram os resultados dos experimentos para o grupo 3 de funções de referência. Como esperado, a versão paralela obteve melhores soluções.

Figura 5.6 – Média das soluções do grupo 3 de funções de referência utilizando o CSA com 24

otimizadores. (a) Funções f9, f10e f11 0 20 40 60 80 100 120 140 160 -20 -15 -10 -5 0 5 L o g1 0 (M éd ia ) Dimensão f9serial f9paralelo f10serial f10paralelo f11serial f11paralelo (b) Funções f12, f13e f14 0 20 40 60 80 100 120 140 160 -20 -15 -10 -5 0 5 L o g1 0 (M éd ia ) Dimensão f12serial f12paralelo f13serial f13paralelo f14serial f14paralelo

Fonte: Dados dos experimentos, 2013.

In document Upstream vertical integration and fi nancial performance (sider 143-158)