Kristiansunds fiskeriselskap
D. Diverse saker
4.4.1 Introdução
De uma forma talvez um pouco simplificadora, poder-se-ia afirmar que duas ordens de motivações principais têm estado na base das abordagens Orientadas por Objectos (OO) no campo das meta-heurísticas, ou de forma mais geral, dos métodos para resolução de Problemas de Optimização Combinatória:
1. na linha da análise de [Nievergelt 1994], a necessidade de intensificar a ponte entre a investigação e a aplicação em problemas reais, através da implementação de sistemas informáticos: "No systems, no impact!";
2. de acordo com [Ferland et al. 1996], a necessidade de criar software mais genérico que permita tornar mais eficiente a comparação de algoritmos sobre um problema específico, e minimizar o esforço de programação aí envolvido.
A utilização do paradigma OO nas várias fases de desenvolvimento de software - análise, desenho e implementação - permite, de acordo com um crescente número de autores, responder a estes desafios.
Relativamente ao primeiro desses desafios, em [Fink et al. 1998a] são apontadas as principais razões que, de um ponto de vista prático, justificam este tipo de preocupações. O objectivo último da Investigação Operacional é o apoio à decisão em problemas reais, que se caracterizam por uma grande diversidade e volatilidade. Juntamente com a necessidade de dispor de sistemas informáticos de fácil utilização, este facto coloca fortes exigências ao desenvolvimento de software, que deverá ser fortemente apoiado. No entender destes autores, resulta daqui uma estratégia que passa pela construção de componentes de software reutilizáveis que dêem corpo ao conhecimento gerado pela investigação.
Em [Ferland et al. 1996] é apresentado um trabalho pioneiro na aplicação do paradigma OO a meta-heurísticas, enquadrado sobretudo pela segunda das motivações referidas. Desde logo se destacam, igualmente, diversos aspectos relevantes também do ponto de vista prático, em particular a modularidade e a racionalidade das estruturas de software, permitindo reutilização e aumento de eficiência no seu desenvolvimento.
As principais vantagens e inconvenientes gerais da aplicação de abordagens OO a esta área são sintetizadas em [Schaerf et al. 1999]: entre as vantagens, são destacadas a possibilidade de reutilização, a clareza conceptual (separação entre problemas e técnicas algorítmicas), a possibilidade de composição de técnicas, a facilidade de prototipagem e experimentação e o estabelecimento de uma metodologia para a concepção de algoritmos; as principais desvantagens apontadas são alguma perda de flexibilidade e de eficiência computacional.
Nos últimos anos têm surgido várias abordagens na área da optimização, com fortes preocupações de reutilização de software. Em [Fink et al. 1998a] são apontadas algumas referências relativas a essas abordagens.
No contexto particular da Optimização Combinatória, um esforço pioneiro deu origem ao framework ABACUS [Thienel 1995], desenvolvido dentro do paradigma OO e com implementação na linguagem C++. Este framework tem por objecto problemas formulados como Programação Inteira Mista, para cuja resolução disponibiliza algoritmos de branch-and-
bound baseados em relaxação linear, que podem ser complementados com geração dinâmica
de planos de corte ou de colunas. O framework promove a (re)utilização destas técnicas, permitindo ao utilizador concentrar-se apenas nas partes específicas ao problema, ou seja, na geração de planos de corte ou de colunas e nas heurísticas primais.
Um sistema com assinalável impacto comercial é o ILOG Solver [Puget 1994, 1995, ILOG 1997], também desenvolvido em C++, que disponibiliza componentes para implementação de abordagens baseadas em Programação Lógica por Restrições, bem como Programação Matemática, desde a fusão, em 1997, com o CPLEX, uma das mais conhecidas bibliotecas de software nesta área.
Na área mais específica das meta-heurísticas, o desenvolvimento de frameworks tem-se estruturado em torno de uma questão central: a separação entre as características específicas dos problemas e os algoritmos meta-heurísticos [Fink et al. 1998a, Fink et al. 1998b]. Com efeito, aspectos como o espaço de soluções ou a estrutura de vizinhança dependem fortemente do problema em consideração e apresentam uma grande diversidade de especificações possíveis. Uma apreciação das abordagens encontradas na literatura mostra que esta separação tem tipicamente sido realizada de uma das seguintes formas:
1. Os componentes meta-heurísticos genéricos são implementados com classes abstractas correspondentes aos componentes dependentes do problema. Para a aplicação a um problema particular, são construídas as classes concretas relativas ao problema, derivadas das referidas classes abstractas. O polimorfismo dinâmico permite aos componentes genéricos lidar com as classes derivadas. 2. Os componentes meta-heurísticos genéricos são implementados com
mecanismos de polimorfismo estático, em particular, o mecanismo "template" em C++ (ver, a este respeito, a descrição do framework HOTFRAME [Fink et al. 1998b] em 4.4.5). Para a aplicação a um problema particular, são construídas as classes concretas relativas ao problema, que irão parametrizar os componentes genéricos.
As abordagens encontradas na literatura serão descritas com algum pormenor nas subsecções seguintes. Na Tabela 4.1 apresenta-se uma caracterização sumária dessas abordagens relativamente aos seguintes aspectos: princípio utilizado na separação algoritmo/problema, organização geral do framework, algoritmos implementados, problemas abordáveis utilizando o framework e linguagem de programação utilizada na respectiva implementação.
Linguagem Object
-oriented
Turbo Pascal C++ C++ C++ C++ Java
Problemas Tipo afectação ("Assignment
-
typ
e"
)
Genérico Genérico Genérico Genérico Tipo afectação
Algoritmos
Iterative Improvement
,
Exchange Procedure [Ferland, Lavoie 1992], TS e SA GA,
Descent
, TS, SA e
estratégias híbridas GRASP, VNS e TS Steepest Descent
, SA e TS Hill Climbing , SA e TS Algorit mos compostos: Tandem Search e Hybrid Search TS Organização
Duas hierarquias de classes: problemas e algoritmos. Classes base
: problema, algoritmo, solução e vizinhança. Arquitectura baseada em padrões de desenho . Classes base: p roblema, algoritmo constru
tivo, pesquisa heurística,
solução, modelo de incremento e modelo de movimento. Componentes relacionados com o problema: problema, solução e vizinhança. Componentes com algoritmos. Algoritmos: componentes genéricos, organizados em hierarquia, através de he
rança.
Aplicação a problemas específicos através de classes concretas para parametrização dos algoritmos: soluções e movimentos. Class
es relacionadas com problemas
do tipo afectação: resource , item , evaluator .
Classes relacionadas com TS.
Princípio
Heranç
a
Herança Herança Polimor
fismo
estático Herança, polimor
fismo
estático Herança
Referências
[Ferland et al. 1996] [Woodruff 1997] [Andreatta et al. 1998] [Fink et al. 1998b] [Schaerf et al. 1999] [Graccho, Porto 1999]
Nome
NST
-ATP
Class Library for Heuris
tic Search
Optimization Searcher HOTFRAME Local ++ TabOOBuilder
Do ponto de vista da reutilização de software, a análise desta tabela permite confirmar o interesse deste tipo de abordagens: por um lado, a maioria das abordagens efectivamente alcança flexibilidade relativamente aos tipos de problemas a abordar; por outro, em diversos casos, os próprios algoritmos beneficiam de reutilização, através da sua organização, por exemplo, em hierarquias de algoritmos.
Em relação aos algoritmos cobertos por esta análise, saliente-se que existe apenas um
framework com GA e dois com abordagens híbridas, o que sugere a existência de direcções de
trabalho ainda em aberto e com forte potencial. Na área das meta-heurísticas multiobjectivo, não há referência a qualquer iniciativa.
Um facto igualmente relevante, do ponto de vista da implementação, é a quase unânime selecção de C++ como linguagem de programação, o que não será certamente indissociável da crescente generalização da utilização desta linguagem, que cobre uma larga maioria dos conceitos de OO, e para a qual existem compiladores eficientes em praticamente todas as plataformas de hardware e sistemas operativos [Thienel 1995].
4.4.2 NST-ATP
A primeira abordagem OO para implementação de meta-heurísticas encontrada na literatura foi proposta em [Ferland et al. 1996], com a designação NST-ATP ("Neighbourhood
Search Techniques - Assignment-Type Problems"). Os autores referidos apresentam um framework
com diversos algoritmos de optimização baseados em pesquisa local, para problemas do tipo afectação ("assignment-type"). O problema genérico pode ser definido da seguinte forma: considerando um conjunto de itens e um conjunto de recursos, afectar os itens aos recursos por forma a optimizar uma função objectivo e satisfazer um conjunto de restrições.
O framework estrutura-se em duas hierarquias de classes: uma primeira, que estabelece um interface com as estruturas de dados para o problema, disponibilizadas pelo utilizador, e uma segunda, que inclui quatro algoritmos de optimização baseados em pesquisa local: Iterative
Improvement, Exchange Procedure [Ferland, Lavoie 1992], TS e SA.
A primeira hierarquia permite obter a informação relevante a partir das estruturas de dados do utilizador, e transformá-la no formato específico exigido pela segunda hierarquia. Por outro lado, poderá também ser aplicada numa eventual transformação de sentido inverso. A principal classe da hierarquia possui algum nível de abstracção, o que permite a sua aplicação mais específica a cada problema particular, através da utilização de polimorfismo.
A segunda hierarquia contém quatro classes distintas, correspondentes aos quatro algoritmos disponibilizados. Estas classes são derivadas de uma classe base, usada apenas para estabelecer parâmetros comuns às diferentes técnicas, e controlar o tempo de execução e o critério de paragem. As técnicas podem ser usadas indiferentemente, uma vez que estão adaptadas a qualquer problema para o qual tenha sido especificado o interface referido na primeira hierarquia. Estas classes possuem igualmente algum nível de abstracção, permitindo a um utilizador criar, através da utilização de polimorfismo, uma qualquer variante que pretenda implementar.
A consideração de uma estrutura de problema específica permite evitar a necessidade de definição de soluções, vizinhanças e movimentos, por parte do utilizador do framework.
Esta abordagem geral foi a primeira a permitir comparar a eficiência relativa de diversos algoritmos na resolução de um problema específico, bem como a sua adaptação através de variantes ou alterações dos parâmetros, por intermédio de intervenções com um esforço de programação mínimo. O software foi desenvolvido em Object-Oriented Turbo Pascal para plataformas do tipo PC.
4.4.3 "A Class Library for Heuristic Search Optimization"
Em [Woodruff 1997] é apresentada uma biblioteca de classes em C++ para meta- heurísticas puras e híbridas. Apesar da designação de biblioteca, o software exibe integralmente as características de um framework. De um ponto de vista teórico, a organização da biblioteca pode ser vista como correspondendo a uma taxonomia de meta-heurísticas, lançando, assim, alguma luz sobre as relações entre estas e as formas como podem ser combinadas. De um ponto de vista prático, os objectivos da biblioteca são a avaliação e a aplicação prática de meta-heurísticas.
Um conjunto de classes base, puramente abstractas, estrutura a biblioteca (Figura 4.1): § HS_Base: base para algoritmos, da qual são derivadas novas classes base:
− GA_Base correspondente aos GA, da qual por suas vez são derivadas duas
classes concretas correspondentes a duas abordagens distintas: geracional (Elite_GA) e estacionária (Steady_GA).
− NR_HS_Base, correspondente a abordagens baseadas em pesquisa local, da
qual são derivadas duas classes concretas com estratégias elementares de pesquisa local (Descent e RR_Descent) e duas classes abstractas, que servirão de base para algoritmos de SA (SA_Base) e TS (Tabu_Base).
§ Problem_Base: base para a definição de problemas.
§ Neighborhood_Base: base para a definição de vizinhanças, derivada de
Mixed_Solution, classe que representa as soluções e que será o elemento constituinte
da população (classe Population) nos GA. As soluções são obrigatoriamente representadas por vectores de inteiros.
Figura 4.1 Estrutura de classes de "A Class Library for Heuristic Search Optimization" [Woodruff 1997]
A biblioteca assenta, portanto, numa estrutura hierárquica, permitindo a realização de extensões ou combinações de classes para produzir novas estratégias de pesquisa, através da utilização do interface das classes abstractas.
Para ter imediatamente à disposição um conjunto de algoritmos, um utilizador da biblioteca apenas necessita de disponibilizar uma definição de um problema e uma estrutura de vizinhança. Por exemplo, a utilização da biblioteca para resolver um problema com uma meta-heurística baseada em pesquisa local envolve a definição de uma classe problema, que deverá ter Problem_Base como classe base pública, e de uma classe vizinhança, que, de forma idêntica, deverá ter Neighborhood_Base como classe base pública. A utilização de herança permitirá, então, que classes de algoritmos, implementadas com uma classe base de vizinhança abstracta, possam manipular, sem conhecer os respectivos detalhes, classes de vizinhança derivadas dessa classe base.
4.4.4 Searcher
Em [Andreatta et al. 1998] é proposto o framework Searcher, desenvolvido em C++, para meta-heurísticas baseadas em pesquisa local. O objectivo do framework é disponibilizar uma arquitectura base para a implementação e comparação de diferentes estratégias. A sua
arquitectura apresenta como principal particularidade o facto de assentar na aplicação de
padrões de desenho.
O framework é particularmente apropriado para utilização em situações que envolvam: diversos métodos para construção da solução inicial, estruturas de vizinhança, ou critérios de selecção de movimentos; algoritmos construtivos utilizando heurísticas de pesquisa local subordinadas, para melhoria de soluções parcialmente construídas; heurísticas de pesquisa local com modelos de vizinhança dinâmicos.
Os autores referidos utilizam para a descrição do framework uma adaptação do template de descrição de padrões de desenho de [Gamma et al. 1995]. Para efeitos de apresentação geral do
framework, destacam-se dessa descrição a estrutura de classes e as suas colaborações.
As classes base do framework, cuja estrutura é apresentada na Figura 4.2, são as seguintes:
§ Cliente (Client): contém a instância do problema a resolver, os métodos de pré- processamento e pós-processamento a aplicar e os dados para criar a Estratégia de Pesquisa (SearchStrategy) a usar.
§ Solução (Solution): encapsula a representação de uma solução para o problema e define o interface a utilizar pelos algoritmos para construir e modificar uma solução.
§ Estratégia de Pesquisa (SearchStrategy): constrói e lança os algoritmos Estratégia Construtiva (BuildStrategy) e Pesquisa Local (LocalSearch).
§ Estratégia Construtiva (BuildStrategy): encapsula algoritmos construtivos em subclasses concretas.
§ Pesquisa Local (LocalSearch): encapsula algoritmos de pesquisa local em subclasses concretas.
§ Incremento (Increment): agrupa a informação necessária à modificação da representação interna de uma Solução por algoritmos construtivos.
§ Movimento (Movement): agrupa a informação necessária à modificação da representação interna de uma Solução por algoritmos de pesquisa local.
§ Modelo de Incremento (IncrementModel): modifica uma Solução de acordo com um pedido de uma Estratégia Construtiva.
§ Modelo de Movimento (MovementModel): modifica uma Solução de acordo com um pedido de uma Pesquisa Local.
Figura 4.2 Diagrama de classes do framework Searcher [Andreatta et al. 1998]
As colaborações mais importantes entre estas classes, representadas no diagrama de sequência da Figura 4.3, são as seguintes:
§ Um Cliente recorre a uma Estratégia de Pesquisa para obter uma Solução para uma instância de um problema.
§ A Estratégia de Pesquisa é composta por, pelo menos, uma Estratégia Construtiva, que produz uma solução inicial, e uma Pesquisa Local, que a procura melhorar.
§ A construção de uma solução é delegada pela Solução no Modelo de Incremento, enquanto as modificações baseadas em vizinhanças são delegadas no Modelo de Movimento. Estas classes obterão, respectivamente, Incrementos e Movimentos para modificação da Solução.
Figura 4.3 Diagrama de sequência para o framework Searcher [Andreatta et al. 1998] A arquitectura do framework assenta na aplicação de três padrões de desenho de [Gamma et al. 1995]: Estratégia ("Strategy"), Método Template ("Template Method") e Estado ("State"). Para completar a apresentação geral aqui realizada, resumem-se de seguida os principais aspectos envolvidos na aplicação destes padrões de desenho:
§ A aplicação do padrão Estratégia resulta em isolar o problema e a estratégia de pesquisa em classes distintas, encapsulando assim a informação de pesquisa e permitindo maior facilidade de construção e extensão de uma família de estratégias de pesquisa. Resulta ainda na separação entre as classes Estratégia de Pesquisa e as classes Estratégia Construtiva e Pesquisa Local. Deste modo, famílias de algoritmos para a construção de soluções iniciais, e famílias de algoritmos para pesquisa local podem ser desenvolvidas com facilidade e de uma forma independente.
§ O padrão Método Template é usado na derivação de classes concretas de algoritmos a partir da classe base Pesquisa Local. Este padrão comportamental define o esqueleto de um algoritmo como uma operação associada a uma classe abstracta, deixando as subclasses refinar certos passos do algoritmo, em particular os passos correspondentes ao comportamento que pode variar. Tal possibilita, no
framework, a realização de especializações de um algoritmo genérico de pesquisa
§ O padrão Estado é usado na implementação de vizinhanças dinâmicas. Na sua aplicação, a classe Solução delega no Modelo de Movimento a construção de diferentes tipos de vizinhanças. A implementação de vizinhanças dinâmicas é, então, realizada a partir do uso de polimorfismo sobre o Modelo de Movimento, dentro da sua hierarquia de classes. Esta delegação de algoritmos poderia novamente ser considerada como uma aplicação do padrão Estratégia. Contudo, como é a própria classe responsável pela construção da vizinhança que se altera durante o processo, a delegação identifica-se melhor com uma aplicação do
padrão Estado.
Relativamente às possibilidades de extensão do framework, os autores destacam a extensão aos GA, para a qual sugerem a criação da classe População, com o formato de conjuntos de soluções e contendo as operações binárias que definem novas soluções. As relações existentes no framework manter-se-iam; novas relações entre Pesquisa Local, População e Solução deveriam ser incluídas.
4.4.5 HOTFRAME ("Heuristic OpTimization FRAMEwork")
O framework HOTFRAME, apresentado em [Fink et al. 1998b], foi implementado em C++, e tem como principais utilizações alvo a aplicação prática e a investigação na área da optimização com meta-heurísticas.
A principal particularidade deste framework é a utilização de polimorfismo estático, disponibilizado em C++ através do mecanismo "template". Neste mecanismo, um parâmetro tipo é incluído na forma "<...>" numa classe "template". Por exemplo, X_P<T, Range> representará instâncias para um problema específico X_P, com o tipo T definindo os parâmetros do problema (por exemplo, valores inteiros ou reais) e o tipo Range definindo o máximo número de objectos.
Na parte do framework que contempla os componentes específicos aos problemas, são considerados os seguintes tipos abstractos:
§ uma classe problema X_P; § uma ou mais classes solução X_S;
§ para cada classe solução X_S, uma ou mais classes de informação da solução X_S_I;
§ para cada classe de vizinhança X_S_N, uma ou mais classes X_S_A com os atributos de movimento correspondentes;
Estes tipos são visualizados pelo diagrama de classes simplificado apresentado na Figura 4.4.
Figura 4.4 Diagrama de classes para o framework HOTFRAME [Fink et al. 1998b] Relativamente à parte algorítmica do framework, os componentes são implementados através de classes "template", parametrizadas com os componentes específicos ao problema anteriormente descritos. Por exemplo, um algoritmo de "Steepest Descent" deverá ser parametrizado com um tipo de solução e um tipo de vizinhança. A instanciação de um componente deste tipo para um problema com um tipo de solução TSolução e um tipo de vizinhança TVizinhança seria realizada da seguinte forma:
SteepestDescent< TSolução < T, Range >, TVizinhança < T, Range > >.
O framework baseia-se, portanto, em primeiro lugar, na generalização através de
"templates". Os mecanismos de herança são utilizados apenas de forma secundária. Este tipo de
abordagem apresenta, em relação a abordagens baseadas em herança, vantagens potenciais ao nível da eficiência de execução, do desacoplamento dos componentes do framework, e do compromisso entre flexibilidade e facilidade de reutilização do tipo caixa-preta. A herança é essencialmente usada para destacar comportamento comum para problemas semelhantes.
4.4.6 Local++
Em [Schaerf et al. 1999] é apresentado um framework, designado Local ++, que se destina a ser usado como ferramenta genérica para o desenvolvimento e implementação de algoritmos de pesquisa local em C++. Uma particularidade importante no framework é o facto de disponibilizar, a um nível abstracto, a definição de solvers compostos.
O framework estrutura-se em torno da utilização do padrão de desenho Método Template [Gamma et al. 1995], já referido anteriormente, permitindo especificar e implementar as partes invariantes de vários algoritmos de pesquisa local. O núcleo do framework é, consequentemente, constituído por uma hierarquia de solvers, apresentada na Figura 4.5 As classes mais baixas da hierarquia representam os algoritmos em si, e será a partir delas que se derivarão classes concretas.
Figura 4.5 Estrutura geral do framework Local++ [Schaerf et al. 1999]
A classe de topo Solver encapsula as características comuns a qualquer solver. LocalSearch constitui a base para as técnicas de pesquisa local, que são classificadas em técnicas simples (SimpleLocalSearch), que fazem uso de um único tipo de movimento e uma única estratégia, e compostas (CompositeLocalSearch), correspondendo aos casos restantes. O Local++ compreende três técnicas simples de pesquisa local, Iterative Improvement (HillClimbing), SA (SimulatedAnnealing) e TS (TabuSearch), e duas compostas, Pesquisa em Sequência (TandemSearch) e Pesquisa Híbrida (HybridSearch).
O framework inclui ainda duas classes baseadas em múltiplas execuções de algoritmos subjacentes. MultiStart executa um solver básico, um determinado número de vezes, apresentando como resultado a melhor das soluções encontradas nas várias execuções.
ComparativeSearch utiliza um vector de solvers simples, executados de forma independente, e
O interface entre o problema a tratar e os algoritmos disponibilizados pelo framework é realizado de duas formas:
§ considerando tipos abstractos em componentes algorítmicos genéricos, através de classes "template" para as soluções e para os movimentos;