A extensão do núcleo do framework para construir meta-heurísticas concretas é realizada com base na aplicação do padrão Método Template, seguindo várias abordagens da literatura [Vaessens et al. 1995, Andreatta et al. 1998, Schaerf et al. 1999]. É com base na aplicação deste padrão, que se estrutura a apresentação desta parte do framework.
Por forma a permitir uma melhor organização da exposição, confere-se destaque à descrição da lista tabu, utilizada pela MOTS*, que envolve alguma complexidade, e em cuja concepção são aplicados dois padrões de desenho: o padrão Iterador, para o acesso aos movimentos que fazem parte da lista, e o padrão Protótipo, para a criação de novas listas tabu, para as soluções da população inicial.
Estrutura e participantes
O diagrama de classes apresentado na Figura 5.11 apresenta a estrutura de classes geral para as duas meta-heurísticas concretas, enquanto o diagrama de classes da Figura 5.12 apresenta a estrutura de classes relacionada com a lista tabu.
#candidate_list #candidateList #curPopulation #current +found_list #largerPopulation #neighbourhood #obtained #pSol #ranges #REF #REqWeights #selected +ulMaxIter methood::MOLocalSearch #Nbh #obtained #selected ... +Initialize() +Iterate() +isEnd() +Search() +isMovementValid() +UpdateREQWeights() +Selectable() +Select() +Acceptable() +IterativeProcess() +Finalize() +GetIter() +Go() -IncIter() +Initialize() +isEnd() +Iterate() +Update() -ulIter methood::IterativeProcess +isMovementValid() methood::MovementFilter Initialize(); while(!isEnd()) { Iterate(); Update(); IncIter(); } Finalize(); pSol=curPopulation->begin(); while(pSol!=curPopulation->end()) {current=*pSol; DefineWeights(current,largerPopulation,REF); MoveIterator->First(); while(!MoveIterator->IsDone()) { obtained = MoveIterator->Current(); efficientSet->Update(current,obtained); if(!Selectable(obtained)) delete obtained; MoveIterator->Next(); } selected = Select();
if(selected!=0 && Acceptable(selected)) selected->ExecuteOn(current); delete selected; pSol++; } return Nbh->Selectable(Move); return Nbh->Select(); methood::MOTabuSearch methood::MOSimAnneal +Initialize() +Update() +Acceptable() +isMovementValid() +Initialize() +Update() +Acceptable() +isMovementValid() methood::AspirationCriteria methood::CoolingSchedule methood::TabuMemory methood::SolutionContext methood::Solution 1 1 methood::MOLSSolContext methood::TabuSolContext Criar contexto Criar lista tabu Chamar inicialização de MOLocalSearch
if(isNotTabu(move) || AspirationCriteriaHolds(move) ) return true;
else return false;
InsertInTabuMemory(move); return true; Drift 1 1 1 1 1 1
Pesos aleatórios para todas as soluções Arrancar esquema de arrefecimento Chamar inicialização de MOLocalSearch Incrementar esquema de arrefecimento Chamar update de MOLocalSearch Aceitar movimento de acordo com cálculo da probabilidade de aceitação return true; * 1 methood::WeightDefinition 1 1 methood::PSAWeightDef methood::MOTSWeightDef
Figura 5.11 Diagrama de classes para as duas meta-heurísticas concretas
methood::MOTabuSearch methood::Solution methood::SolutionContext
1 1 methood::MOLSSolContext methood::TabuSolContext methood::Movement methood::MoveContainer methood::Attributes 1 1 * 1 methood::FLTabuMemory methood::TabuMemory 1 -Prototype 1 1 1 1 * methood::MoveIterator * 1 * 1 1 1
Os participantes nesta parte do framework são: § Processo iterativo (IterativeProcess).
§ Pesquisa local multiobjectivo (MOLocalSearch).
§ PSA (MOSimAnneal). Implementado como um processo iterativo, define as operações primitivas enumeradas em MOLocalSearch, de acordo com as anotações da Figura 5.11: arranca e actualiza um esquema de arrefecimento (CoolingSchedule), aplica uma probabilidade de aceitação e considera elegíveis para execução, todos os movimentos gerados na vizinhança.
§ MOTS* (MOTabuSearch). Implementado como um processo iterativo, de forma idêntica a MOSimAnneal. Em particular, cria e actualiza, para cada solução, uma memória tabu (TabuMemory) de movimentos, implementa uma estratégia de
"drift", e estabelece um critério de aceitação de movimentos e um critério de
aspiração (AspirationCriteria).
§ Esquema de arrefecimento (CoolingSchedule). Implementa um esquema de arrefecimento, com os componentes standard: temperatura inicial, comprimento do "plateau", factor de arrefecimento e temperatura final.
§ Critério de aspiração (AspirationCriteria). Implementa um critério de aspiração, tendo em conta o movimento actual e a memória tabu: o movimento actual deve dominar todos os movimentos da lista tabu, ou apresentar, em relação a estes, um melhor valor do produto escalar dos pesos equalizados da solução actual, pelos respectivos valores dos critérios.
§ Memória tabu (TabuMemory). Define o interface para uma memória tabu e é derivada do contentor de movimentos (MoveContainer). A classe concreta disponibilizada é baseada numa lista ligada (FLTabuMemory).
§ Solução (Solution).
§ Contexto de solução (SolutionContext).
§ Contexto de pesquisa local multiobjectivo (MOLSSolContext).
§ Contexto de TS (TabuSolContext). Classe derivada do contexto de pesquisa local multiobjectivo, acrescentando-lhe a memória tabu que corresponderá a cada solução.
§ Lista tabu (FLTabuMemory). Concretização da classe memória tabu, que se baseia numa lista de movimentos de tamanho fixo.
§ Contentor de movimentos (MoveContainer). § Iterador de movimentos (MoveIterator). § Movimento (Movement).
§ Atributos (Attributes). Implementa os atributos de um movimento, bem como eventuais atributos de uma solução particular em que o movimento tenha sido executado. É através destes atributos que se verifica o estado tabu de um movimento.
§ Filtro de movimentos (MovementFilter). § Definição de pesos (WeightDefinition).
§ Definição de pesos do PSA (PSAWeightDef). Implementa a estratégia de definição de pesos do PSA.
§ Definição de pesos da MOTS* (MOTSWeightDef). Implementa a estratégia de definição de pesos da MOTS*.
Colaborações
Tal como no caso da pesquisa local multiobjectivo, também nestas extensões a colaboração na aplicação do padrão Método Template consiste apenas no facto de os algoritmos concretos se basearem no template de pesquisa local multiobjectivo para implementar o conjunto de passos invariantes. No caso do padrão Protótipo, será o algoritmo MOTS* a solicitar à lista tabu protótipo a criação de novas listas tabu.
Relativamente à utilização da memória tabu, a colaboração estrutura-se em duas partes:
1. Inserção de movimento (Figura 5.13). É criada uma cópia do movimento, que é inserida na cauda da lista. Se o comprimento da lista exceder um valor pré- definido, é retirado o elemento à cabeça da lista.
2. Verificação do estado tabu (Figura 5.14). É utilizado um iterador de movimentos para percorrer a lista tabu até ao final desta ou ser encontrado um movimento que torne tabu o movimento actual.
A verificação do estado tabu é delegada nos atributos do movimento actual e do movimento da lista tabu em análise. Esta verificação implica que entre os atributos haja compatibilidade de tipos (ou seja, deverão pertencer à mesma classe, ou os atributos do movimento da lista tabu deverão ser herdados dos
atributos do movimento actual). No caso de os atributos não serem compatíveis, o movimento actual não é considerado tabu.
aMOTabuSearch aFLTabuList InsertItem(aMovement) aTabuMoveList aMovement aMoveCopy=copy() aMoveCopy new() TLsize=size() FirstMove=front() [TLsize>defined_length] FirstMove delete pop_front() push_back(aMoveCopy)
Figura 5.13 Diagrama de sequência para inserção de movimentos na memória tabu
aMOTabuSearch aFLTabuList aMovement MakesTabu(aMovement) aMoveIterator First() done=IsDone() currentMove=Current() Next() aMoveIterator(aFLTabuList) idx=0 *{!done && !isTabu}
IsDone(idx) currentMove TabuAttributes isTabu=MakesTabu(aMovement) MakesTabu(aAttributes) GetMovement(idx) aAttributes=GetAttributes() idx++
Figura 5.14 Diagrama de sequência para verificação do estado tabu