2 Det norske formannskapet i 6.4
5.5 Budsjett, administrasjon, 4.3 Oppfølging av Nordisk Råds
Designam-se por listas de candidatos conjuntos de movimentos "promissores", identificados, através de algum processo "inteligente", nas vizinhanças exploradas, e que são considerados para uma potencial execução em iterações subsequentes.
Entre as principais motivações para a utilização de listas de candidatos, salientam-se as seguintes [Glover, Laguna 1997, Rangaswamy et al. 1998]:
1. A eficiência e a eficácia da pesquisa podem ser positivamente influenciadas pela selecção de um conjunto de movimentos candidatos de qualidade, em contraste, por exemplo, com a avaliação de todos os movimentos numa vizinhança actual. 2. Em situações em que a geração ou a análise de cada movimento exige um
elevado esforço computacional, ou quando as vizinhanças contêm um grande número de movimentos, é de todo o interesse reduzir o esforço empregue na avaliação de movimentos.
3. Apresenta igualmente particular interesse a exploração das estruturas dos problemas, em domínios particulares que permitam a construção inteligente de listas de candidatos.
As estratégias de listas de candidatos são frequentemente usadas no contexto da TS. No entanto, algumas dessas estratégias, tendo em conta as duas primeiras motivações, são gerais, não específicas a problemas ou meta-heurísticas particulares. De entre as estratégias descritas em [Glover, Laguna 1997, Rangaswamy et al. 1998], algumas, de carácter geral, têm sido destacadas em trabalhos recentes como particularmente promissoras [Fink, Voss 1999]. Neste trabalho será considerada uma dessas estratégias: a estratégia elite (elite candidate list).
O princípio em que se baseia a estratégia elite é o de que um conjunto dos melhores movimentos provavelmente conterá um subconjunto que continuará a manter a qualidade por várias iterações, embora não se possa prever com precisão qual será esse subconjunto. Uma monitorização adequada dos movimentos da lista de candidatos é essencial, uma vez que a alteração da solução actual pode alterar quer a sua avaliação, quer a sua admissibilidade.
A estratégia elite utiliza uma lista construída com os melhores m movimentos encontrados no processo de análise de movimentos alternativos numa dada iteração. Esta lista é construída periodicamente, com base na observação de um grande número de movimentos. Em cada iteração subsequente, até à criação de uma nova lista, o melhor movimento disponível na lista é escolhido e executado. O processo continua até que se tenha completado um número pré-determinado de movimentos, ou até que a qualidade do melhor movimento disponível caia abaixo de um dado limiar. Nesse ponto, a lista é reconstituída e o processo repete-se.
Em alternativa à constituição da lista com um número máximo de elementos pré- determinado, é possível a sua implementação com base num limiar mínimo, que permita garantir uma qualidade "suficiente". Com base em dados anteriores, é calculado, em cada
iteração i, um valor fmédio através do amortecimento exponencial dos valores da função
objectivo:
fmédio(i) = α . f (i) + (1 - α) . fmédio(i - 1), 0 ≤α≤ 1.
Dependendo da avaliação do melhor movimento dentro da última vizinhança
completamente avaliada fmelhor, é calculado um valor limiar
flimiar = fmédio - β . (fmédio - fmelhor), 0 ≤β≤ 1.
A aplicação desta estratégia no presente trabalho é feita apenas para a implementação com limite da cardinalidade da lista, e com a seguinte adaptação: é construída uma lista de candidatos permanente, que em cada iteração é actualizada com os melhores movimentos de entre os já presentes na lista e os encontrados na vizinhança actual. Desta lista de candidatos é feita a selecção do movimento a realizar, que é retirado da lista. Após a execução do movimento, são reavaliados todos os movimentos presentes na lista. Esta estratégia pode ser vista como uma vizinhança expandida, que, além da vizinhança base, considera também os elementos de uma lista, para a selecção do movimento a executar.
Também para esta estratégia se propõe a integração com TS e SA. No primeiro caso, a integração é realizada de forma directa. No segundo, a aplicação da estratégia descrita exige uma alteração ao esquema básico do SA, que consiste em considerar, em cada iteração, a pesquisa de soluções candidatas numa sub-vizinhança de dimensão superior à unidade. De outra forma, o movimento único será inserido na lista, seleccionado e retirado de seguida, não tendo a lista qualquer efeito sobre o comportamento do algoritmo.
2.4.4 Hibridização
Ao longo dos últimos anos, o interesse em meta-heurísticas híbridas tem vindo a aumentar consideravelmente. Com efeito, para muitos problemas práticos e académicos, os melhores resultados têm sido obtidos com algoritmos híbridos. Conforme já referido, o objectivo das abordagens de hibridização é tirar partido da complementaridade entre diversos princípios meta-heurísticos.
Uma taxonomia apresentada em [Talbi 1998] estabelece uma terminologia comum para esta área, bem como mecanismos de classificação, permitindo uma útil caracterização dos diversos tipos de abordagens existentes na área, e sugerindo implicitamente vários tópicos para investigação futura. A taxonomia incide sobre aspectos conceptuais e de implementação, justificando-se no contexto do presente trabalho a sua apresentação apenas na parte relativa aos aspectos conceptuais.
Nesta taxonomia, uma primeira parte, hierárquica, apresentada na Figura 2.2, compreende as seguintes distinções:
§ Baixo nível vs alto nível.
A hibridização de baixo nível tem lugar no domínio da composição funcional de um único método de optimização. Nesta classe, uma dada função de uma meta- heurística é substituída por uma meta-heurística.
Nos algoritmos híbridos de alto nível, as diversas meta-heurísticas são autónomas. Não há interacção directa entre os funcionamentos internos de meta-heurísticas. § "Relay" vs co-evolutiva.
Na hibridização "relay", várias meta-heurísticas são aplicadas sequencialmente, cada uma utilizando o resultado da anterior como informação de entrada.
Uma abordagem de co-evolução envolve modelos de optimização cooperativos, nos quais existem múltiplos agentes cooperativos paralelos, cada um executando uma pesquisa num dado espaço de soluções.
Figura 2.2 Taxonomia de abordagens híbridas - parte hierárquica As quatro classes que resultam desta hierarquia são:
§ HBR (Híbrido Baixo Nível "Relay"): algoritmos nos quais uma dada meta-heurística é incorporada numa meta-heurística de solução única.
§ HBC (Híbrido Baixo Nível Co-evolutivo): algoritmos nos quais uma dada meta- heurística é incorporada numa meta-heurística baseada em população.
Baixo Nível Alto Nível
Meta-heurísticas Híbridas
§ HAR (Híbrido Alto Nível "Relay"): meta-heurísticas autónomas executadas em sequência.
§ HAC (Híbrido Alto Nível Co-evolutivo): o esquema HAC envolve diversos algoritmos autónomos, realizando pesquisas em paralelo e cooperando para encontrar um óptimo. Intuitivamente, o HAC deverá comportar-se pelo menos tão bem como um algoritmo isolado, mas com maior frequência apresentará melhor comportamento, com cada um dos algoritmos a disponibilizar aos restantes informação para apoiar os respectivos processos de pesquisa.
Numa segunda parte da taxonomia, organizada horizontalmente, são consideradas as seguintes distinções:
§ Homogéneo vs heterogéneo.
Os algoritmos híbridos homogéneos usam repetidamente a mesma meta- heurística. Nos algoritmos heterogéneos são usadas diferentes meta-heurísticas. § Global vs parcial.
Nos algoritmos híbridos globais, todos os algoritmos componentes trabalham sobre todo o espaço de pesquisa, com o objectivo de o explorar mais exaustivamente. Nos algoritmos híbridos parciais, o problema a ser resolvido é decomposto em subproblemas, a cada um dos quais correspondendo um espaço de pesquisa próprio; cada algoritmo componente é, então, dedicado à pesquisa de um destes espaços.
§ Especialista vs Geral.
Nos algoritmos híbridos gerais, os algoritmos componentes resolvem o mesmo problema de optimização, enquanto os algoritmos híbridos especialistas combinam algoritmos componentes que resolvem diferentes problemas.
No contexto do presente trabalho privilegiam-se abordagens de aplicação geral e que permitam tirar partido das características de métodos já existentes, pelo que parece do maior interesse procurar estabelecer um algoritmo híbrido de alto nível, co-evolutivo, heterogéneo, global e geral.
2.4.5 Paralelização
Versões paralelas de meta-heurísticas têm vindo a ser propostas com crescente regularidade, tendo naturalmente como motivação principal a diminuição dos tempos computacionais, para instâncias de problemas com dimensões mais realistas [Crainic, Toulouse 1997]. Um segundo benefício tem sido crescentemente assinalado: em condições apropriadas, as meta-heurísticas paralelas podem ser bastante mais robustas do que as versões sequenciais, relativamente a diferenças de tipo e características de problema e às respectivas questões de afinação de parâmetros.
Sendo extenso o leque de sínteses, taxonomias e surveys na área, a maioria dos trabalhos, no entanto, coloca o seu enfoque numa única metodologia, ou perspectiva a área a partir de uma única metodologia. Contudo, [Crainic, Toulouse 1997] apresenta uma perspectiva mais global, propondo uma taxonomia com o objectivo de detectar aspectos comuns entre as diferentes abordagens e, assim, permitir a obtenção de "insights", a descoberta de tendências e a identificação de desafios para investigação.
A classificação apresentada baseia-se no nível de impacto que a estratégia de paralelização tem na concepção algorítmica da meta-heurística:
1. Tipo 1: Paralelização de operações dentro de uma iteração do método. Esta estratégia, também conhecida como paralelismo de baixo nível, pretende apenas acelerar a computação, sem alterar o método sequencial correspondente e sem melhorar a exploração do espaço de pesquisa ou obter soluções de melhor qualidade. As avaliações de indivíduos e movimentos são operações tipicamente passíveis de paralelização do tipo 1.
2. Tipo 2: Decomposição do domínio problema ou espaço de soluções. Esta estratégia é baseada no princípio de que a capacidade computacional pode ser dedicada à resolução de um conjunto de problemas de dimensão mais reduzida, dos quais uma solução global melhorada pode ser extraída ou construída. A trajectória de pesquisa da abordagem paralela resultante é diferente, contudo, da do método sequencial correspondente. Este tipo de estratégias são geralmente implementadas em esquemas "master-slave".
3. Tipo 3: "Threads" multipesquisa ("multi-search") com vários graus de sincronização e
cooperação. Esta estratégia procura realizar uma exploração mais exaustiva do
espaço de soluções, lançando vários "threads" de pesquisa que percorrem o domínio em simultâneo. Alguns aspectos variam com frequência entre implementações: utilizar uma mesma abordagem meta-heurística ou abordagens
diferentes; partir da mesma solução inicial ou de soluções iniciais distintas; realizar comunicação entre processos durante a pesquisa ou apenas no fim para identificar a melhor solução global; comunicar de forma síncrona ou assíncrona; desencadear a comunicação por eventos específicos ou em momentos pré- determinados ou decididos dinamicamente.
Estas estratégias podem ser ainda divididas em duas classes:
§ Abordagens independentes. Diversas pesquisas são iniciadas e o melhor resultado é, no final, seleccionado de entre os resultados finais dos processos individuais.
§ Abordagens cooperativas. São definidas de acordo com um conjunto numeroso de parâmetros: topologia de ligação, definindo a forma como os processos estão ligados; método de comunicação ("broadcast", propagação, uso de memória central, etc.); processos a executar entre trocas de informação; comunicação síncrona ou assíncrona; instantes em que ocorre troca de informação; informação a trocar.
Estas abordagens têm sido aplicadas quase exclusivamente a GA, SA e TS.
Todos os tipos de estratégias de paralelização têm os seus méritos e continuarão certamente a ser aplicadas quando tal se mostrar apropriado. Parece haver, no entanto, uma clara tendência de evolução no sentido tipo 1 - tipo 2 - tipo 3.
Segundo os autores referidos, com a excepção das implementações que tiram partido de características especiais do problema ou de arquitecturas de hardware particulares, tem sido proposto um número limitado de estratégias de paralelização. As abordagens "multithread" têm-se revelado cada vez mais importantes, destacando-se a possibilidade de estes métodos permitirem não só uma mais eficiente implementação de estratégias de rearranque, mas, mais particularmente, o processamento concorrente de diferentes tipos de pesquisas - o mesmo método com diferentes parâmetros ou mesmo diferentes meta-heurísticas e métodos exactos. Desta forma, pode ser conseguida uma exploração mais exaustiva do espaço de pesquisa. Um benefício adicional é a robustez que estes métodos exibem, em comparação com os correspondentes métodos sequenciais, relativamente a diferenças nos tipos e características dos problemas.
Estas abordagens permitirão, também, vir a tirar partido do poder computacional das redes de estações de trabalho existentes em muitas organizações.
Com base nestas conclusões, e tendo em atenção o contexto particular deste trabalho, em que se pretende estudar abordagens de flexibilização gerais, sem tirar partido de uma arquitectura de hardware paralela e específica, fará sentido optar por uma paralelização do tipo 3, em conjunto com a opção de hibridização já referida.
2.5 Conclusões
A resolução de Problemas de Optimização Combinatória, nas mais diversas áreas, coloca exigências a que a utilização de meta-heurísticas, estratégias mestras que guiam e modificam outras heurísticas para produzir soluções de qualidade, tem respondido, com assinalável sucesso. Muito deste sucesso está relacionado com o facto de as meta-heurísticas serem ferramentas de aplicabilidade geral, com um nível de flexibilidade que permite a incorporação de restrições específicas em problemas reais, e que apresentam um conjunto interessante de compromissos entre qualidade de solução, requisitos computacionais e esforço de desenvolvimento e implementação.
Algumas das mais recentes abordagens meta-heurísticas são baseadas na flexibilização, ou seja, na introdução de mecanismos de modificação, dos seus componentes e das suas estratégias elementares. Tal sucede no âmbito da criação de novas formas de fuga à optimalidade local, da generalização de conceitos fundamentais particulares ou da utilização conjunta de conceitos provenientes de distintas meta-heurísticas.
Vários aspectos fundamentais deste trabalho são, naturalmente, reflexo do enfoque colocado neste conceito de flexibilização em meta-heurísticas: a utilização de abordagens de hibridização e paralelização de aplicação geral, a utilização de estratégias de generalização, e a identificação de uma base para infra-estruturas comuns que favoreçam a utilização dessas estratégias.