TProcuraMelhorativa.h

Go to the documentation of this file.

#pragma once
 
#include "../TProcura.h"
 
// um ponto no espaço de estados das soluções completas, é um apontador para um estado
class TProcuraMelhorativa;
typedef TProcuraMelhorativa* TPonto;
 
// nomes dos parâmetros fixos na procura melhorativa
enum EMelhorativas {
    POPULACAO = PARAMETROS_PROCURA, PROB_CRUZAR,
    PROB_MUTAR, SELECAO, PRESSAO, TAMANHO_TORNEIO, 
    PROB_MELHOR_TORNEIO, SOBREVIVENCIA, PERC_DESCENDENTES, 
    Q_ROUND_ROBIN, ELITISMO, IMIGRANTES, 
    DIVERSIDADE, DIST_MINIMA, MOVE_PRIMEIRO,
    PARAMETROS_MELHORATIVA
};
 
enum EIndicadoresConstrutiva {
    IND_EPOCAS = IND_PROCURA,    
    IND_GERACOES,               
    IND_MELHORATIVA             
};
 
 
//  TProcuraMelhorativa class
//  Author: José Coelho
//  Last revision: 2025-01-30
//  Description:
//    Superclasse de procuras no espaço das soluções completas (a solução é melhorada).
//    As variaveis da classe devem ser apenas de uma solucao, se existir informação
//    sobre a instancia, esta informação deve ser colocada em variaveis estáticas
//    para não serem duplicadas desnecessariamente.
//    A única variavel é o valor da solução que após ser calculada em Avaliar
//    deve ser actualizada (se o valor não estiver actualizado, deve ter -1)
class TProcuraMelhorativa :
    public TProcura
{
public:
    TProcuraMelhorativa(void);
    ~TProcuraMelhorativa(void);
 
    int custo = -1;
    static int lowerBound;
    static int geracoes;
    static int epocas;
 
    // Métodos para redefinir
 
    virtual TPonto Duplicar(void) = 0;
 
    virtual void Copiar(TPonto objecto) {}
 
    virtual void NovaSolucao(void) {}
    // Retorna o valor da solução completa actual. Atribuir o valor a custo
    virtual int Avaliar(void);
    // redefinir, para aceitar ações que sejam operadores
    bool Acao(const char* acao) { return false; }
    // Método para inicializar os parâmetros (redefinir se forem adicionados parâmetros específicos)
    void ResetParametros() override;
 
    // critrio de paragem adicionado para procuras melhorativas:
    // - custo nulo, significa obter o ótimo (lowerBound pode ser atualizado, caso exista, de omissão é 0)
    // - número gerações (ou épocas) sem melhoria - futuro
    // - diversidade da população - futuro
    bool Parar(void) { return TProcura::Parar() || custo <= lowerBound; }
 
    // Operadores a redefinir para Escalada-do-Monte
 
    // Operador de vizinhanca (apenas em soluções completas)
    // chamar a função nesta classe para actualizacao de estatisticas
    virtual void Vizinhanca(TVector<TPonto>& vizinhos) {}
 
    // Algorithmos Evolutivos
 
    // Operador mutação, altera o estado actual (de acordo com a parametrizacao global)
    virtual void Mutar(void) {}
    // Operador cruzamento, cruza os dois elementos a e b, colocando o resultado no estado atual
    virtual void Cruzamento(TPonto a, TPonto b) { }
    // Função distância: distancia deste elemento ao elemento a
    // (opcional para manter os elementos diversos)
    virtual int Distancia(TPonto a) { return 0; }
 
    // Algoritmo de procura local: Escalada do Monte
    // retorna a avaliação do resultado actual
    int EscaladaDoMonte();
 
    // Algoritmo de procura local: Algoritmos Geneticos
    // retorna a avaliação do resultado final
    int AlgoritmoGenetico();
 
    // Algoritmo Evolutivo: Algoritmos Geneticos + Estratégia de Evolução
    // Implementação em linha com Eiben & Smith, 2015
    // retorna a avaliação do resultado final
    int AlgoritmoEvolutivo();
 
 
 
    // Chamar sempre que uma solução melhor que a actual e encontrada
    void DebugMelhorEncontrado(TPonto ponto);
 
    int64_t Indicador(int id) override;
 
    void Inicializar(void) {}
 
    void LimparEstatisticas();
 
 
protected:
    // métodos internos
    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);
    bool VerificaMelhor(TPonto atual);
    int MelhorCusto(TVector<TPonto>& populacao, bool inverter = false);
    TPonto MelhorAtual(TPonto& atual, TVector<TPonto>& vizinhos, int indice);
    void ObterExtremos(TVector<TPonto>& populacao, int& minCusto, int& maxCusto);
    void Explorar() override;
    void LibertarVector(TVector<TPonto>& vector, int excepto = -1);
    int ExecutaAlgoritmo();
    // Mostrar 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);
    // algoritmo evolutivo
    TVector<TPonto> CompletarPopulacaoAE(TVector<TPonto>& populacao);
    TVector<TPonto> SelecionarPaisAE(TVector<TPonto>& populacao);
    TVector<TPonto> ReproduzirAE(TVector<TPonto>& pais, TVector<TPonto>& populacao);
    TVector<TPonto> SelecionarSobreviventesAE(TVector<TPonto>& populacao, TVector<TPonto>& descendentes);
    TVector<TPonto> AplicarDiversidadeAE(TVector<TPonto>& populacao);
    void DebugGeracaoAE(int epoca, TVector<TPonto>& populacao);
    void DebugPopulacaoAE(TVector<TPonto>& populacao, const char* titulo); // mostrar toda a população
    void DiversidadeAE(TVector<TPonto>& populacao, 
        int& minDist, int& maxDist, int& avgDist, int& melhorPior);
};