TProcuraMelhorativa Class Reference

#include <TProcuraMelhorativa.h>

Inheritance diagram for TProcuraMelhorativa:

Collaboration diagram for TProcuraMelhorativa:

Public Member Functions
	TProcuraMelhorativa (void)
	~TProcuraMelhorativa (void)
virtual TPonto	Duplicar (void)=0
	Cria um objecto que é uma cópia deste.
virtual void	Copiar (TPonto objecto)
	Fica com uma cópia do objecto.
virtual void	NovaSolucao (void)
virtual int	Avaliar (void)
bool	Acao (const char *acao)
void	ResetParametros () override
	Inicializa os parametros, indicadores e instâncias.
virtual void	Vizinhanca (TVector< TPonto > &vizinhos)
virtual void	Mutar (void)
virtual void	Cruzamento (TPonto a, TPonto b)
virtual int	Distancia (TPonto a)
int	EscaladaDoMonte ()
int	AlgoritmoGenetico ()
void	TesteManualX (const char *nome)
	provavelmente apagar
void	DebugMelhorEncontrado (TPonto ponto)
	provavalmente apagar
int	Indicador (int id) override
	Redefinição. Ver TProcura::Indicador().
void	LimparEstatisticas (clock_t &inicio)
	Chapar antes da execução do algoritmo. Limpa valores estatísticos, e fixa o instante limite de tempo para a execução.
Public Member Functions inherited from TProcura
	TProcura (void)
virtual	~TProcura (void)
virtual void	Inicializar (void)
	Coloca o objecto no estado inicial da procura.
virtual void	Debug (void)
	Mostra o estado no ecrã, para debug.
virtual bool	Parar (void)
	Verifica se a procura deve ser interrompida.
virtual void	TesteManual (const char *nome)
	Inicializa a interação com o utilizador.
virtual void	TesteEmpirico (TVector< int > instancias, bool mostrarSolucoes=true, char *ficheiro=NULL)
	Executa testes empíricos, em todas as configurações guardadas, nas instâncias selecionadas.
virtual void	main (int argc, char *argv[], const char *nome)
	Inicializa a interação com o utilizador.
virtual void	ExecucaoTerminada (clock_t inicio)
	Chamar após a execução do algoritmo. Grava o tempo consumido.
virtual void	MostrarSolucao ()
	definir para visualizar a solução
virtual TVector< int >	CodificarSolucao ()
	retorna um vetor de inteiros com a codifciação da solução (esta codificação será adicionada aos indicadores, no ficheiro CSV de resultados)
bool	TempoExcedido ()
bool	IteracoesExcedido ()
int	Parametro (int id)

Public Attributes
int	custo
	Custo total, atualizada após Avaliar()
int	geracoes
	Número de estados gerados.
int	epocas
	Número de épocas decorridas num algoritmo evolutivo. Uma época é uma geração única.

Protected Member Functions
void	Selecao (int &pai, int &mae, TVector< int > &pesos, int total)
void	OrdemValor (TVector< TPonto > &populacao, TVector< int > &id)
void	CalcularAvaliacoes (TVector< TPonto > &vizinhos, int &melhorValor, int &melhorIndice)
void	VerificaMelhor (TPonto &melhor, TPonto atual)
TPonto	MelhorAtual (TPonto &atual, TVector< TPonto > &vizinhos, int indice)
void	ObterExtremos (TVector< TPonto > &populacao, int &minCusto, int &maxCusto)
void	Explorar () override
	definir para explorar manualmente os dados (não definido em TProcura, apenas em TProcuraConstrutiva)
void	LibertarVector (TVector< TPonto > &vector, int excepto=-1)
int	ExecutaAlgoritmo ()
	Executa o algoritmo com os parametros atuais.
void	DebugVizinhos (TVector< TPonto > &vizinhos)
void	DebugInicioEM (int ID, TPonto solucao)
void	DebugOptimoLocal (TPonto solucao)
void	DebugPassoEM (TPonto solucao)
void	DebugPassoAG (int pop, int min, int max)
void	DebugCruzamentoAG (int gPai, int gMae, int gFilho, int mutou)
Protected Member Functions inherited from TProcura
void	InserirRegisto (TVector< TResultado > &resultados, int inst, int conf)
	Insere um novo registo de resultados.
int	Registo (TResultado &resultado, int id)
	Procura um registo com determinado id.
void	Registo (TResultado &resultado, int id, int valor)
	Atualiza o valor de um registo.
void	MostraParametros (int detalhe=1, TVector< int > *idParametros=NULL)
	Mostra os parâmetros atuais.
void	MostraIndicadores ()
	Mostra os indicadores definidos.
void	MostrarConfiguracoes (int detalhe, int atual=-1)
	Mostra as configurações disponíveis.
bool	EditarIndicadores ()
	Permite ao utilizador editar os indicadores a utilizar.
void	EditarParametros ()
	Permite ao utilizador editar os parâmetros.
void	EditarConfiguracoes ()
	Permite ao utilizador editar as configurações.
void	MostraRelatorio (TVector< TResultado > &resultados, bool ultimo=false)
	Mostra um relatório dos resultados.
void	ConfiguracaoAtual (TVector< int > &parametros, int operacao)
	Grava ou lê a configuração atual.
int	NovaConfiguracao (TVector< int > &parametros)
	Adiciona uma nova configuração se ainda não existir.
int	MelhorResultado (TResultado base, TResultado alternativa)
	Compara dois resultados para determinar o melhor.
void	CalculaTorneio (TVector< TResultado > &resultados)
	Calcula o torneio entre várias configurações.
void	MostrarTorneio (TVector< TVector< int > > &torneio, bool jogo=false)
	Mostra os resultados do torneio.
void	BarraTorneio (bool nomes)
	Mostra a barra de progresso ou nomes do torneio.
TVector< TResultado >	ExtrairConfiguracao (TVector< TResultado > &resultados, int configuracao)
	Extrai resultados de uma determinada configuração.
void	SolicitaInstancia ()
	Solicita ao utilizador o ID da instância a utilizar, permitindo alterar também o prefixo do ficheiro.
TVector< int >	SolicitaInstancias ()
	Solicita ao utilizador uma lista de instâncias.
void	RelatorioCSV (TVector< TResultado > &resultados, FILE *f)
	Gera um relatório CSV com os resultados.
TVector< int >	ExtraiLista (char *str)
	Extrai uma lista de inteiros a partir de uma string.
void	InserirConfiguracoes (char *str, TVector< int > &base)
	Insere configurações a partir de uma string.
void	InserirConfiguracoes (TVector< int > &base, TVector< int > &produto, TVector< TVector< int > > &valores)
	Insere configurações gerando o produto cartesiano de valores.
void	AjudaUtilizacao (const char *programa)
	Mostra ajuda de utilização do programa.

Additional Inherited Members
Static Public Member Functions inherited from TProcura
static int	NovoValor (const char *prompt)
static char *	NovoTexto (const char *prompt)
Static Public Attributes inherited from TProcura
static TParametro	instancia = { NULL,1,1,1, NULL, NULL }
	ID da instância atual, a ser utilizado em SolucaoVazia().
static char	ficheiroInstancia [256] = "instancia_"
	nome do ficheiro de uma instância - editado pelo utilizador (utilizar como prefixo, concatenando com ID da instância) pode ser utilizado para gravar a instãncia num novo formato, colocando um indicador ativo que é chamado após a execução (pode gravar a solução para ficheiro também, mas essa é mais facilmente gravada em CVS codificada em inteiros, onde fica associada à configuração utilizada para a gerar)
static TVector< TParametro >	parametro
	Parâmetros a serem utilizados na configuração atual.
static TVector< TIndicador >	indicador
	Indicadores que podem ser calculados após a execução, quer com informação da instãncia, quer com resultado da última corrida.
static TVector< int >	indAtivo
static TVector< TVector< int > >	configuracoes
	Conjuntos de configurações para teste empírico.
static int	resultado = 0
	Resultado retornado pelo algoritmo na última execução.
static int	tempo = 0
	tempo consumido na última execução.
static int	iteracoes = 0
	Número total de iterações realizadas na última execução.
static clock_t	instanteFinal = 0
	Instante final (deadline) da corrida atual.
static bool	memoriaEsgotada = false
	Flag indicando problemas de memória esgotada.
Static Protected Member Functions inherited from TProcura
static int	Dominio (int &variavel, int min=INT_MIN, int max=INT_MAX)
	Limita o domínio de um parâmetro inteiro.

Detailed Description

Definition at line 34 of file TProcuraMelhorativa.h.

Constructor & Destructor Documentation

TProcuraMelhorativa()

TProcuraMelhorativa::TProcuraMelhorativa

(

void

)

Definition at line 11 of file TProcuraMelhorativa.cpp.

~TProcuraMelhorativa()

TProcuraMelhorativa::~TProcuraMelhorativa

(

void

)

Definition at line 15 of file TProcuraMelhorativa.cpp.

Member Function Documentation

Acao()

bool TProcuraMelhorativa::Acao ( const char *  acao )

inline

Definition at line 113 of file TProcuraMelhorativa.h.

Here is the caller graph for this function:

AlgoritmoGenetico()

int TProcuraMelhorativa::AlgoritmoGenetico

(

)

Definition at line 227 of file TProcuraMelhorativa.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

Avaliar()

int TProcuraMelhorativa::Avaliar ( void  )

virtual

Reimplemented in COitoDamas, and CParticao.

Definition at line 64 of file TProcuraMelhorativa.cpp.

Here is the caller graph for this function:

CalcularAvaliacoes()

void TProcuraMelhorativa::CalcularAvaliacoes ( TVector< TPonto > &  vizinhos, int &  melhorValor, int &  melhorIndice  )

protected

Definition at line 212 of file TProcuraMelhorativa.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

Copiar()

virtual void TProcuraMelhorativa::Copiar ( TPonto  objecto )

inlinevirtual

Fica com uma cópia do objecto.

Note

Obrigatória a redefinição.

Este método tem de ser criado na subclasse, de modo a um estado poder ficar igual a outro. As variáveis de estado, devem ser todas copiadas.

Deve garantir que as variáveis copiadas sejam suficientes para reconstruir o estado corretamente. No entanto, uma instância pode ter dados que não mudam em cada estado. Essas variáveis não precisam de estar no estado, e podem ser alocadas de forma estática na subclasse, não sendo necessário copiar nesta função.

A não ser que exista uma estrutura de dados completa, o modelo de código em baixo pode ser facilmente reproduzido para qualquer subclasse.

Note

Não é preciso copiar as variáveis da classe TProcuraConstrutiva, pai, custo, heuristica.

See also

Sucessores() e Heuristica()

void CSubClasse::Copiar(TPonto objecto) {
        CSubProblema& obj = *((CSubProblema*)objecto);
        // copiar todas as variáveis do estado
        variavel = obj.variavel;
}

Reimplemented in COitoDamas, CParticao, and CProblemaArtificial.

Definition at line 107 of file TProcuraMelhorativa.h.

Here is the caller graph for this function:

Cruzamento()

virtual void TProcuraMelhorativa::Cruzamento ( TPonto  a, TPonto  b  )

inlinevirtual

Reimplemented in COitoDamas, and CParticao.

Definition at line 133 of file TProcuraMelhorativa.h.

Here is the caller graph for this function:

DebugCruzamentoAG()

void TProcuraMelhorativa::DebugCruzamentoAG ( int  gPai, int  gMae, int  gFilho, int  mutou  )

protected

Definition at line 318 of file TProcuraMelhorativa.cpp.

Here is the caller graph for this function:

DebugInicioEM()

void TProcuraMelhorativa::DebugInicioEM ( int  ID, TPonto  solucao  )

protected

Definition at line 170 of file TProcuraMelhorativa.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

DebugMelhorEncontrado()

void TProcuraMelhorativa::DebugMelhorEncontrado

(

TPonto

ponto

)

provavalmente apagar

Definition at line 365 of file TProcuraMelhorativa.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

DebugOptimoLocal()

void TProcuraMelhorativa::DebugOptimoLocal ( TPonto  solucao )

protected

Definition at line 161 of file TProcuraMelhorativa.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

DebugPassoAG()

void TProcuraMelhorativa::DebugPassoAG ( int  pop, int  min, int  max  )

protected

Definition at line 325 of file TProcuraMelhorativa.cpp.

Here is the caller graph for this function:

DebugPassoEM()

void TProcuraMelhorativa::DebugPassoEM ( TPonto  solucao )

protected

Definition at line 153 of file TProcuraMelhorativa.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

DebugVizinhos()

void TProcuraMelhorativa::DebugVizinhos ( TVector< TPonto > &  vizinhos )

protected

Definition at line 536 of file TProcuraMelhorativa.cpp.

Here is the caller graph for this function:

Distancia()

virtual int TProcuraMelhorativa::Distancia ( TPonto  a )

inlinevirtual

Reimplemented in COitoDamas, and CParticao.

Definition at line 136 of file TProcuraMelhorativa.h.

Here is the caller graph for this function:

Duplicar()

virtual TPonto TProcuraMelhorativa::Duplicar ( void  )

pure virtual

Cria um objecto que é uma cópia deste.

Note

Obrigatória a redefinição.

Este método tem de ser criado na subclasse, de modo a criar uma cópia do mesmo tipo. O código da subclasse geralmente segue um padrão e pode utilizar o modelo abaixo, aproveitando o método Copiar(). É especialmente útil na função de Sucessores(), na geração de um novo estado.

Returns

Retorna o novo estado, acabado de gerar.

Note

Caso exista falha de memória, colocar a variável memoriaEsgotada a true, para tentativa de terminar a execução de forma graciosa.

TPonto CSubClasse::Duplicar(void)
{
    CSubClasse* clone = new CSubClasse;
       if(clone!=NULL)
           clone->Copiar(this);
       else
            memoriaEsgotada = true;
       return clone;
}

Implemented in COitoDamas, CParticao, CProblemaArtificial, COitoDamas, CParticao, and CProblemaArtificial.

Here is the caller graph for this function:

EscaladaDoMonte()

int TProcuraMelhorativa::EscaladaDoMonte

(

)

Definition at line 81 of file TProcuraMelhorativa.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

ExecutaAlgoritmo()

int TProcuraMelhorativa::ExecutaAlgoritmo ( )

protectedvirtual

Executa o algoritmo com os parametros atuais.

Note

Redefinição necessária

No caso de adicionar algum algoritmo, chame o algoritmo com base em parametro[algoritmo].valor Se TesteManual() não for utilizado, esta função pode ser chamada diretamente, desde que os parâmetros necessários já estejam configurados corretamente.

Reimplemented from TProcura.

Definition at line 447 of file TProcuraMelhorativa.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

Explorar()

void TProcuraMelhorativa::Explorar ( )

overrideprotectedvirtual

definir para explorar manualmente os dados (não definido em TProcura, apenas em TProcuraConstrutiva)

Reimplemented from TProcura.

Definition at line 457 of file TProcuraMelhorativa.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

Indicador()

int TProcuraMelhorativa::Indicador ( int  id )

overridevirtual

Redefinição. Ver TProcura::Indicador().

Reimplemented from TProcura.

Definition at line 374 of file TProcuraMelhorativa.cpp.

Here is the call graph for this function:

LibertarVector()

void TProcuraMelhorativa::LibertarVector ( TVector< TPonto > &  vector, int  excepto = -1  )

protected

Definition at line 188 of file TProcuraMelhorativa.cpp.

Here is the caller graph for this function:

LimparEstatisticas()

void TProcuraMelhorativa::LimparEstatisticas ( clock_t &  inicio )

virtual

Chapar antes da execução do algoritmo. Limpa valores estatísticos, e fixa o instante limite de tempo para a execução.

Reimplemented from TProcura.

Definition at line 383 of file TProcuraMelhorativa.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

MelhorAtual()

TProcuraMelhorativa * TProcuraMelhorativa::MelhorAtual ( TPonto &  atual, TVector< TPonto > &  vizinhos, int  indice  )

protected

Definition at line 204 of file TProcuraMelhorativa.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

Mutar()

virtual void TProcuraMelhorativa::Mutar ( void  )

inlinevirtual

Reimplemented in COitoDamas, and CParticao.

Definition at line 131 of file TProcuraMelhorativa.h.

NovaSolucao()

void TProcuraMelhorativa::NovaSolucao ( void  )

virtual

Reimplemented in COitoDamas, and CParticao.

Definition at line 58 of file TProcuraMelhorativa.cpp.

Here is the caller graph for this function:

ObterExtremos()

void TProcuraMelhorativa::ObterExtremos ( TVector< TPonto > &  populacao, int &  minCusto, int &  maxCusto  )

protected

Definition at line 355 of file TProcuraMelhorativa.cpp.

Here is the caller graph for this function:

OrdemValor()

void TProcuraMelhorativa::OrdemValor ( TVector< TPonto > &  populacao, TVector< int > &  id  )

protected

Definition at line 335 of file TProcuraMelhorativa.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

ResetParametros()

void TProcuraMelhorativa::ResetParametros ( )

overridevirtual

Inicializa os parametros, indicadores e instâncias.

Note

Redefinição necessária, para pelo menos indicar as instâncias existentes

Nesta função, a primeira instrução deverá ser a chamada da função da superclasse, para que sejam criados os parametros da superclasse antes de qualquer outra instrução.

Cada problema pode ter um algoritmo e configurações padrão que funcionam bem na maioria dos casos. Nesta função, podem ser definidos estes valores de omissão.

Novos parâmetros podem ser adicionados conforme necessário para atender às particularidades do problema. Estes parametros podem depois ser selecionados ou incluídos num teste empírico, de modo a averiguar em fase de testes, qual a melhor configuração, evitando escolhas arbitrárias ou não fundamentadas.

Nesta função deve ser redefinida a variável com informação dos IDs das instâncias disponíveis. Essa variável é do tipo TParametro, mas não está na lista de parametros, devendo ser inicializada aqui.

Existindo novos indicadores, devem ser adicionados aqui, e redefinida a função Indicador() para calcular o valor.

Note

Na criação de um novo parametro, dar uma estrutura TParametro.

Ao adicionar novos parâmetros, é recomendável manter a enumeração sincronizada com a da superclasse. O primeiro elemento deve ser parametrosConstrutivos, garantindo que novas adições na superclasse sejam automaticamente refletidas aqui.

A instância selecionada irá ser carregada em Inicializar(), utilizando o valor atual.

See also

TParametro

Exemplo com a alteração do valor de omissão de um parametro, e adição de dois novos parametros.

// continuação da enumeração EParametrosProcujra
enum ESubProblema { opcaoHeur = parametrosProcura, opcaoSuc };
void CSubProblema::ResetParametros(void)
{
    static const char* nomesSuc[] = { "todas", "contributo" }; // nomes para os valores de opcaoSuc
    // chamar primeiro o método na superclasse
    TProcura::ResetParametros();
    // neste exemplo considerou-se que se pretende ver algum debug, de omissão
    parametro[nivelDebug].valor = 1;
 
    // novo parametro para utilizar na função Heuristica()
    parametro.Add({ "Opção Heurística", 0,0,10,
        "explicação do que acontece na heuristica, com este parametro entre 0 e 10",NULL });
    // novo parametro para utilizar na função Sucessores()
    parametro.Add({ "Opção Sucessores", 0,0,1,
        "0 gera todas as ações; 1 gera apenas ações que tenham um contributo para a solução.",nomesSuc });
 
    // novo indicador
    indicador.Add({ "Ordenado","verifica se um vetor está ordenado", indOrdenar });
    indAtivo.Add(indOrdenar); // adicionar aos indicadores ativos de omissão
 
    // indicar que há 10 instâncias, sendo a instância inicial a 1
       instancia = { "Problema", 1,1,10, "Características dos problemas", NULL };
}

Reimplemented from TProcura.

Definition at line 19 of file TProcuraMelhorativa.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

Selecao()

void TProcuraMelhorativa::Selecao ( int &  pai, int &  mae, TVector< int > &  pesos, int  total  )

protected

Definition at line 342 of file TProcuraMelhorativa.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

TesteManualX()

void TProcuraMelhorativa::TesteManualX

(

const char *

nome

)

provavelmente apagar

Definition at line 391 of file TProcuraMelhorativa.cpp.

Here is the call graph for this function:

VerificaMelhor()

void TProcuraMelhorativa::VerificaMelhor ( TPonto &  melhor, TPonto  atual  )

protected

Definition at line 196 of file TProcuraMelhorativa.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

Vizinhanca()

void TProcuraMelhorativa::Vizinhanca ( TVector< TPonto > &  vizinhos )

virtual

Reimplemented in COitoDamas, and CParticao.

Definition at line 72 of file TProcuraMelhorativa.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

custo

int TProcuraMelhorativa::custo

Custo total, atualizada após Avaliar()

Definition at line 42 of file TProcuraMelhorativa.h.

epocas

int TProcuraMelhorativa::epocas

Número de épocas decorridas num algoritmo evolutivo. Uma época é uma geração única.

Definition at line 46 of file TProcuraMelhorativa.h.

geracoes

int TProcuraMelhorativa::geracoes

Número de estados gerados.

Definition at line 44 of file TProcuraMelhorativa.h.

---

The documentation for this class was generated from the following files:

• Melhorativa/TProcuraMelhorativa.h
• Melhorativa/TProcuraMelhorativa.cpp