TCodificacaoBinaria.cpp

Go to the documentation of this file.

#include "TCodificacaoBinaria.h"
 
// número de elementos binários na codificação 
int TCodificacaoBinaria::nElementos = 0;
 
void TCodificacaoBinaria::Copiar(TPonto objeto) {
    TCodificacaoBinaria& obj = *((TCodificacaoBinaria*)objeto);
    estado = obj.estado;
}
 
void TCodificacaoBinaria::NovaSolucao(void) {
    int n = (nElementos + 63) / 64;
    estado.Count(n);
    for (int i = 0; i < n; i++)
        estado[i] = ((uint64_t)TRand::rand()) << 32 | ((uint64_t)TRand::rand());
    custo = -1;
}
 
// métodos que podem ser redefinidos
void TCodificacaoBinaria::Debug(bool completo) {
    for (int i = 0; i < nElementos; i++)
        printf("%d", Bit(i) ? 1 : 0);
 
        // utilização de TBits (experimental):
    //TBits novoEstado;
    //for (auto& palavra : estado)
    //  novoEstado += palavra;
 
    // mostrar todos os modos
    //for (int modo = 0; modo <= 2; modo++)
    //  printf("%s", *novoEstado.String(modo));
}
 
void TCodificacaoBinaria::ResetParametros() {
    TProcuraMelhorativa::ResetParametros();
 
    // parâmetros da codificação binária
    parametro += {
        { "TIPO_CRUZAR", 1, 0, 10, "TIPO_CRUZAR: 1 - um ponto, >=2 N-pontos, 0 - uniforme", {
            "uniforme", "2-pontos", "3-pontos", "4-pontos", "5-pontos",
            "6-pontos", "7-pontos", "8-pontos", "9-pontos", "10-pontos" }},
        { "TIPO_MUTAR", 0,0,100, "TIPO_MUTAR: 0 - aplica um vizinho aleatório (seja 1 só elemento ou segmento), 1 a 100, probabilidade de mutação de cada bit, em percentagem (1 a 100)" },
        { "TIPO_VIZINHO", 1,1,1000, "Troca segmento: 1 - apenas 1 bit de cada vez, >=2 troca um segmento de N bits" }
    };
}
 
 
void TCodificacaoBinaria::Vizinhanca(TVector<TPonto>& vizinhos) {
    // inverter segmento de N bits
    int tamanho = Parametro(TIPO_VIZINHO_CB);
    if (tamanho < 1)
        tamanho = 1;
    Debug(EXTRA_DEBUG, false, " vizinhança %d bits", tamanho);
    for (int i = 0; i < nElementos - tamanho + 1; i++) {
        TCodificacaoBinaria* vizinho = (TCodificacaoBinaria*)Duplicar();
        if (vizinho != NULL) {
            for (int j = 0; j < tamanho; j++)
                vizinho->Troca(i + j);
            vizinho->custo = -1;
            vizinhos += vizinho;
        }
        else
            memoriaEsgotada = true;
    }
    TProcuraMelhorativa::Vizinhanca(vizinhos);
}
 
void TCodificacaoBinaria::Mutar(void) {
    // mutação com probabilidade p de trocar cada bit
    int p = Parametro(TIPO_MUTAR_CB);
    if (p == 0) {
        // um vizinho aleatório
        int tamanho = Parametro(TIPO_VIZINHO_CB);
        if (tamanho < 1)
            tamanho = 1;
        if (tamanho > nElementos - 1)
            tamanho = nElementos - 1;
        int i = TRand::rand() % (nElementos - tamanho + 1);
        Debug(EXTRA_DEBUG, false, " mutar vizinho #bits %d (%d)",
            tamanho, i);
        for (int j = 0; j < tamanho; j++)
            Troca(i + j);
        custo = -1;
    }
    else {
        Debug(EXTRA_DEBUG, false, " mutar prob p(%d)", p);
        // cada bit com probabilidade p
        for (int i = 0; i < nElementos; i++)
            if (TRand::rand() % 100 < (unsigned)p)
                Troca(i);
        custo = -1;
    }
}
 
void TCodificacaoBinaria::Cruzamento(TPonto a, TPonto b) {
    int pontos = Parametro(TIPO_CRUZAR_CB);
    TVector<int> divisoes;
    if (pontos > nElementos / 2)
        pontos = nElementos / 2;
    while (divisoes.Count() < pontos) {
        divisoes += (TRand::rand() % nElementos);
        divisoes.BeASet();
    }
    if (divisoes.Empty()) { // cruzamento uniforme
        Debug(EXTRA_DEBUG, false, " cruzamento uniforme");
        for (int i = 0; i < nElementos; i++)
            Bit(i) = ((TCodificacaoBinaria*)(TRand::rand() % 2 == 0 ? a : b))->Bit(i);
    }
    else { // cruzamento em N pontos
        int i = 0;
        bool copiaPai = true;
        if (Parametro(NIVEL_DEBUG) >= EXTRA_DEBUG) {
            Debug(EXTRA_DEBUG, false, " cruzamento %d-ponto(s): ", divisoes.Count());
            for (auto ponto : divisoes)
                Debug(EXTRA_DEBUG, false, "%d ", ponto);
        }
        divisoes += nElementos; // ponto final
        for (auto ponto : divisoes) {
            while (i < ponto) {
                Bit(i) = ((TCodificacaoBinaria*)(copiaPai ? a : b))->Bit(i);
                i++;
            }
            copiaPai = !copiaPai;
        }
    }
    custo = -1;
 
    TProcuraMelhorativa::Cruzamento(a, b);
}
 
int TCodificacaoBinaria::Distancia(TPonto a) { // distância de Hamming
    int dist = 0;
    for (int i = 0; i < nElementos; i++)
        if (Bit(i) != ((TCodificacaoBinaria*)a)->Bit(i))
            dist++;
    return dist;
}