Apresentam-se de seguida, e de uma forma sintética, as principais orientações que estiveram na base do desenvolvimento do METHOOD, salientando-se as diferenças mais importantes relativamente a outras abordagens descritas na literatura, e conferindo especial destaque aos aspectos considerados inovadores.
A principal motivação para o desenvolvimento deste framework encontra-se presente na área das abordagens OO para meta-heurísticas, desde o trabalho pioneiro de [Ferland et al. 1996]: tirar partido do paradigma OO para beneficiar a aplicação e a comparação de meta- heurísticas. A aplicação do trabalho desenvolvido por esses autores está, no entanto, restrita a problemas de um tipo específico. O mesmo sucede com o framework TabooBuilder [Graccho, Porto 1999] que, adicionalmente, se restringe também a abordagens baseadas em TS. No caso do METHOOD, bem como de outras abordagens encontradas na literatura, a opção é no sentido da generalização do tipo de problemas que se podem considerar e da disponibilização de vários algoritmos, desenvolvidos a partir de infra-estruturas comuns.
É do framework Searcher [Andreatta et al. 1998] que resultaram as influências mais significativas sobre o presente trabalho, em particular ao nível da utilização de padrões de desenho, da preocupação com aspectos de flexibilidade e do suporte explícito para algoritmos construtivos. O facto de se lidar no presente trabalho com meta-heurísticas multiobjectivo conduz às principais diferenças em relação ao trabalho de [Andreatta et al. 1998], com a
introdução de componentes relativos à avaliação multiobjectivo, ao tratamento de populações de soluções, etc. Uma outra diferença fundamental reside na separação entre os aspectos de representação e de semântica das soluções. Aliás, já em [Andreatta et al. 1998] se referia esta questão, relativamente à diferenciação da abordagem de [Woodruff 1997]. Por exemplo, enquanto no Searcher, um pedido de execução de um movimento sobre uma solução é dirigido a essa solução, no METHOOD o pedido é dirigido ao próprio movimento. Desta forma, a solução fica isolada de diferentes semânticas particulares, o que simplificará a sua reutilização noutros contextos, como será o caso, por exemplo, da integração no METHOOD, de meta-heurísticas baseadas em recombinação.
Um aspecto que não tem merecido tratamento explícito na maioria das abordagens da literatura é a disponibilização de abordagens de hibridização e paralelização. Em [Woodruff 1997] é referida, embora sem uma apresentação específica, a consideração de estratégias de hibridização. No trabalho de [Schaerf et al. 1999], são apresentadas algumas estratégias muito simples. No METHOOD este aspecto é tratado explicitamente, propondo- se uma abordagem que permite realizar paralelização do tipo "threads" multipesquisa e cooperativa, e hibridização de alto nível, co-evolutiva.
Fora do domínio das abordagens OO, deverá ser destacado o template de [Vaessens et al. 1995], que constitui a principal referência para a aplicação do padrão Método Template neste trabalho.
Inúmeras diferenças de pormenor poderiam ser aqui apresentadas, em particular ao nível das opções de desenho. Será, no entanto, de maior importância destacar os principais aspectos de inovação do METHOOD, que constituem factores fundamentais de diferenciação em relação a outras abordagens:
§ a utilização explícita do paradigma OO para suportar flexibilização em meta- heurísticas, designadamente estratégias de listas de candidatos, vizinhanças variáveis, paralelização e hibridização;
§ a aplicação à área das meta-heurísticas multiobjectivo, com destaque para a construção de um template de pesquisa local multiobjectivo, a adaptação a esta área de estratégias de listas de candidatos e vizinhanças variáveis, e a criação de uma abordagem de hibridização e paralelização de alto nível.
Para concluir, ao nível da evolução futura do framework, dois aspectos abordados na literatura poderão vir a assumir particular relevância:
§ O framework apresentado em [Fink et al. 1998b] baseia-se na utilização de polimorfismo estático, alternativa que, segundo os autores referidos, será potencialmente mais eficiente do que a utilização de mecanismos de herança.
Nesse sentido, a evolução do METHOOD irá, portanto, passar, muito provavelmente, pela adopção de polimorfismo estático.
§ A linguagem Localizer [Michel, van Hentenryck 1998] sugere uma extensão ao
framework, para a qual este estará potencialmente preparado, no sentido de
permitir uma configurabilidade de alto nível das abordagens meta-heurísticas disponibilizadas.
5.12 Conclusões
A convicção de que uma abordagem OO potencia a disponibilização de uma arquitectura de base flexível para a construção, aplicação e comparação de meta-heurísticas multiobjectivo, integrando estratégias de flexibilização genéricas, em contextos de desenvolvimento de aplicações práticas e investigação na área da Optimização Combinatória Multiobjectivo, constituiu a principal motivação para o desenvolvimento do framework METHOOD (METaHeuristics Object-Oriented Development).
A descrição de um framework incide no seu objectivo, no seu desenho detalhado e nas instruções para a sua utilização. Os primeiros dois aspectos são objecto de atenção neste capítulo, enquanto o terceiro é tratado no Capítulo 6. A parte mais substancial da descrição corresponde ao desenho detalhado que inclui, para cada parte do framework considerada, as estruturas de classes e respectivas colaborações. Apenas as partes do framework relacionadas com a pesquisa local multiobjectivo foram, por motivos de espaço e organização do texto, tratadas no âmbito deste capítulo. As restantes partes são descritas no Anexo B.
Um elemento fundamental para o desenho do framework é a utilização de padrões de
desenho. Do "catálogo" de [Gamma et al. 1995], foram utilizados os seguintes padrões: Estratégia
("Strategy"), Método Template ("Template Method"), Iterador ("Iterator"), Protótipo ("Prototype") e Estado ("State").
Ao nível da avaliação de soluções e movimentos num contexto multiobjectivo, o
framework disponibiliza um vector de critérios, associado a um conjunto de operações mais
frequentes, e a um vector de pesos e um vector pesos equalizados. A cada critério está associada uma função de avaliação, distinta para soluções e movimentos.
A pesquisa local multiobjectivo assenta essencialmente na aplicação do padrão Método
Template, que implementa o template de pesquisa local multiobjectivo, definido em 3.3.1. É a
concretização deste template em classes derivadas que permite a extensão para duas meta- heurísticas concretas baseadas em pesquisa local multiobjectivo: PSA e MOTS*.
A flexibilização da parte do framework relativa às vizinhanças permite a consideração de vizinhanças variáveis e de estratégias de listas de candidatos, e a sua integração com o
template de pesquisa local multiobjectivo, de acordo com as propostas apresentadas no
Capítulo 3. O esforço realizado no sentido de identificar e isolar factores comuns aos diversos algoritmos de pesquisa local multiobjectivo foi determinante para a concepção da abordagem de hibridização e paralelização de alto nível, igualmente apresentada no Capítulo 3, e na qual toda a parte do framework relativa a algoritmos básicos é reutilizada.
Relativamente a outras abordagens presentes na literatura, o METHOOD diferencia- se essencialmente pela utilização explícita do paradigma OO para suportar flexibilização em meta-heurísticas, e pela sua aplicação à área das meta-heurísticas multiobjectivo. A procura de uma melhoria da eficiência do framework e o desenvolvimento de uma extensão para configuração de alto nível das abordagens meta-heurísticas disponibilizadas, são trajectórias de evolução futura do framework que vão ao encontro de algumas tendências encontradas na literatura.
No desenvolvimento do framework foi possível, desde logo, constatar o nível efectivamente elevado de flexibilidade e configurabilidade conferido pelas características básicas do paradigma OO. Em grande parte do framework, tal é indissociável da aplicação de
padrões de desenho. Com efeito, sendo concebidos como soluções genéricas para problemas de
desenho recorrentes, os padrões de desenho apresentam, logo à partida, e com base nas características básicas do paradigma OO, elevados níveis de flexibilidade e configurabilidade.
A modelação efectiva do domínio e a separação de facetas permitem estabelecer uma infra-estrutura conceptualmente clara, o que constitui um apoio indispensável à concepção e implementação de algoritmos de grande dimensão e complexidade, como é o caso das meta- heurísticas multiobjectivo. Por outro lado, estes aspectos incentivam efectivamente a construção de novas meta-heurísticas ou variantes, através de extensões por composição ou derivação de subclasses, conforme sucede no framework, com a implementação e integração de um conjunto de estratégias genéricas.
É ainda de salientar o elevado potencial de reutilização atingido, constatável no desenho de diversas partes do framework, bem como no esforço de desenvolvimento envolvido, que é significativamente reduzido. A disponibilização de um conjunto relativamente alargado de técnicas algorítmicas e variantes, para contextos multiobjectivo, é realizada, no total, por cerca de 50 classes, inteiramente reutilizáveis, e exigiu um esforço de desenvolvimento de cerca de 3 pessoas-mês.