|
Algoritmo de Evolução Diferencial:Dentre os métodos de otimização heurísticos desenvolvidos nos últimos anos, o algoritmo de Evolução Diferencial (ED) (Storn e Price, 1997), configura-se como uma das estratégias mais utilizadas para a resolução de problemas da ciência e engenharia. Seu sucesso se deve a sua concepção conceitual simples, facilidade de implementação, capacidade de estruturação em arquitetura paralela, habilidade de escapar de ótimos locais, e pelos resultados obtidos em aplicações com diferentes graus de complexidade. Em linhas gerais, a idéia principal por trás deste algoritmo é o esquema proposto para atualização de cada indivíduo, a saber, por meio da realização de operações vetoriais. Basicamente, a diferença ponderada entre dois indivíduos da população é adicionada a um terceiro indivíduo da mesma população. Assim, o indivíduo gerado através deste esquema é avaliado segundo a função objetivo, podendo inclusive substituir indivíduos mal sucedidos nas gerações seguintes. Esta característica faz com que essa técnica seja reconhecida como uma abordagem puramente estrutural, o que a diferencia em relação às outras técnicas evolutivas, já que essas têm fundamentação teórica inspirada na natureza (Price et al., 2005). O algoritmo de ED baseia-se na realização de operações vetoriais na qual a diferença ponderada entre dois indivíduos distintos, adicionada a um terceiro indivíduo, é o responsável pela geração de candidatos. De maneira geral, o algoritmo de ED apresenta as seguintes operações: inicialização da população, mutação, cruzamento, seleção, além do critério de parada do algoritmo. A seguir são descritas cada uma destas operações. Inicialização do AlgoritmoO processo de inicialização da população no algoritmo de ED, assim como acontece em outras estratégias heurísticas, consiste na geração de indivíduos de forma aleatória. Neste caso, faz-se uso da definição do tamanho da população e do domínio de cada variável de projeto. A partir daí, geram-se números randômicos que serão aplicados a esse intervalo, obtendo-se assim um vetor de indivíduos da população, como mostrado a seguir: \[x_{i,j} = x_{i,L} + rand\left( {x_{i,U} - x_{i,L} } \right)\] onde \(x_{i,L}\) e \(x_{i,U}\) são os limites inferiores e superiores das \(j\)-ésimas variáveis de projeto, respectivamente, e rand é um gerador de números randômicos entre 0 e 1. Operador de MutaçãoUma vez inicializado o processo evolutivo, o algoritmo de ED realiza as opera- ções de mutação e recombinação para a geração de uma nova população com NP indivíduos. O operador de mutação diferencial adiciona um vetor de referência, escolhido aleatoriamente na população, a um vetor diferença obtido a partir de outros dois vetores também escolhidos aleatoriamente na população. A equação a seguir mostra como essa combinação é realizada para gerar o novo vetor (candidato) \(v_{i,g}\): \[v_{i,g} = x_{r0,g} + F\left( {x_{r1,g} - x_{r2,g} } \right)\] onde o escalar \(F\), denominado taxa de perturbação, é um número real que controla a magnitude do vetor diferença obtido em cada operação aritmética realizada. Os vetores \(x_{r0,g}\), \(x_{r1,g}\) e \(x_{r2,g}\) são geralmente escolhidos aleatoriamente na população, apesar de poderem ser definidos de outras formas, como apresentado a seguir. \(\checkmark\) Estratégia 1 (DE/best/1/exp):\[x^{j+1}=x^{j}_{best}+F(x^{j}_{\kappa_1}-x^{j}_{\kappa_2})\] \(\checkmark\) Estratégia 2 (DE/rand/1/exp):\[x^{j+1}=x^{j}_{\kappa_3}+F(x^{j}_{\kappa_1}-x^{j}_{\kappa_2})\] \(\checkmark\) Estratégia 3 (DE/ran-to-best/2/exp):\[x^{j+1}=x^{j}_{old}+F(x^{j}_{best}-x^{j}_{old})+F(x^{j}_{\kappa_1}-x^{j}_{\kappa_2})\] \(\checkmark\) Estratégia 4 (DE/best/2/exp):\[x^{j+1}=x^{j}_{best}+F(x^{j}_{\kappa_1}-x^{j}_{\kappa_2})+F(x^{j}_{\kappa_3}-x^{j}_{\kappa_4})\] \(\checkmark\) Estratégia 5 (DE/rand/2/exp):\[x^{j+1}=x^{j}_{\kappa_5}+F(x^{j}_{\kappa_1}-x^{j}_{\kappa_2})+F(x^{j}_{\kappa_3}-x^{j}_{\kappa_4})\] \(\checkmark\) Estratégia 6 (DE/best/1/bin):\[x^{j+1}=x^{j}_{best}+F(x^{j}_{\kappa_1}-x^{j}_{\kappa_2})\] \(\checkmark\) Estratégia 7 (DE/rand/1/bin):\[x^{j+1}=x^{j}_{\kappa_3}+F(x^{j}_{\kappa_1}-x^{j}_{\kappa_2})\] \(\checkmark\) Estratégia 8 (DE/rand-to-best/2/bin):\[x^{j+1}=x^{j}_{old}+F(x^{j}_{best}-x^{j}_{old})+F(x^{j}_{\kappa_1}-x^{j}_{\kappa_2})\] \(\checkmark\) Estratégia 9 (DE/best/2/bin):\[x^{j+1}=x^{j}_{best}+F(x^{j}_{\kappa_1}-x^{j}_{\kappa_2})+F(x^{j}_{\kappa_3}-x^{j}_{\kappa_4})\] \(\checkmark\) Estratégia 10 (DE/rand/2/bin):\[x^{j+1}=x^{j}_{\kappa_5}+F(x^{j}_{\kappa_1}-x^{j}_{\kappa_2})+F(x^{j}_{\kappa_3}-x^{j}_{\kappa_4})\] A convenção utilizada nesta tabela é DE/X/Y/Z, onde X representa o vetor que será perturbado (best ou rand). Por exemplo, optando-se por rand, o vetor que será perturbado é escolhido aleatoriamente na população. Y é o número de pares de vetores que são considerados durante a perturbação e Z é o tipo de cruzamento usado para a geração do candidato, bin no caso binomial e exp no caso exponencial. Os subscritos \(\kappa_i\) (i=1,..., 5) são índices escolhidos aleatoriamente na população. \(x_{best}\) é o melhor indivíduo da população na geração anterior e \(x_{old}\) é um indivíduo escolhido aleatoriamente dentro da população na geração anterior. Operador de CruzamentoPara complementar a operação de mutação, o algoritmo de ED emprega o operador de cruzamento. Nesta operação, o vetor \(v_{i,g}\) gerado anteriormente pode ou não ser aceito na próxima geração de acordo com a seguinte condição: \[u_{i,g} = \left\{ {\begin{array}{*{20}l} {v_{i,g} } & {{\rm{ \text{se} \;}}rand \le CR{\rm{\; \text{ou} \;}}j = j_{rand} {\rm{ }}} \\ {x_{i,g} } & {{\rm{\text{caso contrário} }}} \\ \end{array}} \right.\] onde \(CR\) é denominada probabilidade de cruzamento, definida pelo usuário e contida no intervalo [0, 1]. Esse parâmetro controla as informações dos pais que serão transmitidas aos filhos. Para determinar qual a contribuição de um determinado vetor gerado, o cruzamento compara \(CR\) com o gerador de números randômicos rand. Se o número randômico gerado é menor ou igual a \(CR\), o vetor \(v_{i,g}\) (com posição \(j_{rand}\)) é aceito, caso contrário, o vetor \(x_{i,g}\) é mantido na população atual. Operador de SeleçãoSe o vetor \(u_{i,g}\) tem melhor valor de função objetivo (\(f\)) em relação ao vetor \(x_{i,g}\), ele o substitui na próxima geração; caso contrário, \(x_{i,g}\) é mantido na população por mais uma geração, como mostrado a seguir: \[x_{i,g + 1} = \left\{ {\begin{array}{*{20}l} {u_{i,g} } & {{\rm{ \text{se} \;}}f(u_{i,g} ) \le f(x_{i,g} )} \\ {x_{i,g} } & {{\rm{\text{caso contrário} }}} \\ \end{array}} \right.\] Uma vez completado o processo de atualização da população que será conside- rada na próxima geração, todo o processo descrito acima é repetido até que um determinado critério de parada seja satisfeito. Critério de ParadaEste objetiva a convergência associada a um baixo esforço computacional, mensurado pelo número de avaliações da função objetivo. Tradicionalmente, o principal critério de parada utilizado em abordagens heurísticas é mesmo o número máximo de gerações, definido pelo usuário. Todavia, outros mecanismos podem ser utilizados para finalizar o processo evolutivo, dentre os quais se pode citar : o tempo de processamento, o número de avaliações da função objetivo, o uso de um valor de referência obtido da literatura para essa finalidade e o monitoramento do próprio usuário. A Inicialização dos Parâmetros do AlgoritmoCom relação à escolha dos parâmetros do algoritmo de ED, Storn e Price (1997) aconselham o uso dos seguintes valores: número de indivíduos da população como sendo igual a um valor entre 5 e 10 vezes o número de variáveis de projeto, taxa de perturbação \(F\) entre 0,2 e 2,0 e probabilidade de cruzamento \(CR\) entre 0,1 e 1,0. Com relação à escolha da estratégia DE/X/Y/Z, qualquer uma das dez apresentadas podem ser empregadas para a resolução de um problema em particular. De forma geral, a de número 7 é uma das mais utilizadas, sendo default nas implementações apresentadas na literatura. Modelagem Matemática Otimizar a Mistura de Catalisadores Voltar para a página principal do LabSim-EQ |
