<repo_name>ThiagoLAMF/Genetic-Algorithm<file_sep>/main.c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "util.h"
#include "selecao.h"
#include "defines.h"
#include "crossover.h"
#include "populacao.h"

/** DEC. FUNÇÕES **/
int ag();
/** MAIN **/
int main()
{
    srand(time(NULL));
    int i;
    int contador = 0;

    for(i = 0; i< N_ITERACOES;i++)
    {
        if(ag())
        {
            contador++;
        }
    }

    printf("\n----------AG-----------------\n");
    printf("GERACOES: %d\n",N_GERACOES);
    printf("ITERACOES: %d\n",N_ITERACOES);
    printf("RESULTADO: %d PC\n",(contador));
    return 0;
}

/** FUNÇÕES **/
int ag()
{
    int i;
    int j;

    // GERA POPULAÇÃO:
    int somaAvaliacao;
    int **geracao = GeraPopulacao(&somaAvaliacao);

    for(j = 0; j< N_GERACOES;j++)
    {
        // AG:
        //Ordena os pais(Usado no Elitismo):
        if(ELITISMO)
        {
            quickSort(geracao, 0,TAM_GERACAO-1);
            //printg(geracao);
            //getchar();
        }

        if(ROLETA)
        {
            //Calcula FREQ para seleção. //Usado METODO ROLETA
            CalculaFrequenciaAcumulada(geracao);
        }

        int qtdFilhos = TX_CROSSOVER; //QTD de filhos a serem gerados

        for(i=0;i<qtdFilhos;i= i+2)
        {
            //SELECIONA PAIS PARA CROSSOVER
            int pai1;
            int pai2;
            //TORNEIO:
            if(TORNEIO)
            {
                pai1 = SelecionaTorneio(geracao,3);
                pai2 = SelecionaTorneio(geracao,3);
            }
            if(ROLETA)
            {
                pai1 = SelecionaRoleta(geracao);
                pai2 = SelecionaRoleta(geracao);
                //printf("ROLETA: %d %d\n",pai1,pai2);
            }

            //CROSSOVER
            CrossOverCiclico(geracao[pai1],geracao[pai2],geracao[TAM_GERACAO + i],geracao[TAM_GERACAO + (i+1)] );
            //printf("\n[CROSSOVER] %i \tX %i \tPOS: %i",pai1,pai2,pontoCrossOver);

            //CalculaAvaliacao(geracao[TAM_GERACAO + i]);//alteracao questao 2
            //CalculaAvaliacao(geracao[TAM_GERACAO + (i+1)]);//alteracao questao 2
            //alteracao questao 2
            Mutacao(geracao[TAM_GERACAO + i]);
            Mutacao(geracao[TAM_GERACAO + (i+1)] );
        }
        //MUTAÇÃO
        //MutacaoFilhos(geracao,TX_MUTACAO,qtdFilhos);//alteracao questao 2

        //Elitismo
        if(ELITISMO)
        {
            //Vetor de pais já está ordenado// Mantem os 20 primeiros
            SobeFilhos(geracao,TX_ELITISMO,qtdFilhos,TAM_GERACAO);
        }

        if(MELHORPAISFILHOS)
        {
            //SELECIONA MELHORES:
            quickSort(geracao, 0,TAM_GERACAO+qtdFilhos-1);
        }

        //printg(geracao);
        //getchar();
        if(geracao[0][AVAL] == 0)
        {
            //printind(geracao[0]);
            FreePopulacao(geracao);
            return 1;
        }
    }




    if(VerificaMatriz(geracao))
    {
        //printind(geracao[0]);
        //getchar();
        FreePopulacao(geracao);
        return 1;
    }

    FreePopulacao(geracao);
    return 0;
}
<file_sep>/util.c
#include <stdio.h>
#include <stdlib.h>
#include "defines.h"
#include "util.h"


void printg(int **geracao)
{
    int i,j;
    // PRINT POPULAÇÃO:
    printf("\n\n---------------------GERACAO------------------------\n");
    //printf("SOMA AVAL: %i\n",somaAvaliacao);
    printf("INDEX\tIND.\t\tAVAL.\t\tF.A.\n");
    for(i=0;i<TAM_GERACAO_TOTAL;i++)
    {
        printf("[%i]:\t",i);
        for(j = 0;j<TAM_INDIVIDUO_TOTAL;j++)
        {
            printf("%i",geracao[i][j]);
        }
        printf("\t[%i]\t\t[%i]\n",geracao[i][AVAL],geracao[i][FA]);
    }

}

void printind(int *ind)
{
    int j;
    printf("[?]:\t");
    for(j = 0;j<TAM_INDIVIDUO_TOTAL;j++)
    {
        printf("%i",ind[j]);
    }
    printf("\t[%i]\t\t[%i]\n",ind[AVAL],ind[FA]);


}

int partition(int **geracao, int l, int r)
{
    int *t;
    int i = l-1;
    int j;
    int pivot = geracao[r][AVAL];

    for(j = l;j<=r-1;j++)
    {
        if(geracao[j][AVAL] <= pivot)
        {
            i++;
            t = geracao[i];
            geracao[i] = geracao[j];
            geracao[j] = t;
        }
    }

   t = geracao[i+1];
   geracao[i+1] = geracao[r];
   geracao[r] = t;
   return i+1;
}

/**
    Ordena com quick sort os indivíduos da população de acordo com a avaliação:
**/
void quickSort(int **geracao, int l, int r)
{
   int j;

   if( l < r )
   {
        j = partition( geracao, l, r);// divide and conquer
        quickSort( geracao, l, j-1);
        quickSort( geracao, j+1, r);
   }

}
/**
    Converte um array de inteiros em um inteiro e retorna.
**/
int ConcatenaArray(int* arr, int len)
{
    int result = 0,i;

    for (i=0; i < len; i++)
    {
        result = result*10 + arr[i];
    }
    return result;
}

/**
    Sobe os filhos na matriz
    posFilho = posição do primeiro filho
    posIni = índice da posição inicial de inserção
**/
void SobeFilhos(int **geracao,int posIni,int qtdFilhos,int posFilho)
{
    int i;

    for(i=0;i<qtdFilhos;i++)
    {
        geracao[posIni] = geracao[posFilho];
        posFilho++;
        posIni++;
    }
}

int VerificaMatriz(int **geracao)
{
    int i;

    for(i=0;i<TAM_GERACAO_TOTAL;i++)
    {
        if(geracao[i][AVAL] == 0) return 1;
    }
    return 0;
}


<file_sep>/selecao.c
#include "defines.h"
#include "selecao.h"
#include <inttypes.h>
#include <stdlib.h>

/**
    Calcula a frequencia acumulada e coloca na posição [FA] do vetor.
**/
void CalculaFrequenciaAcumulada(int **geracao)
{
    int i;
    int freq = 0;

    for(i=0;i<TAM_GERACAO_TOTAL;i++)
    {
        if(i < TAM_GERACAO)
        {
            freq += geracao[i][AVAL];
            geracao[i][FA] = freq;
        }
        else
        {
            geracao[i][FA] = -1;
        }
    }
}

/**
    Seleciona um individuo baseado no método da Roleta e retorna o índice.
    É necessário que a Frequencia Acumulada esteja calculada na posicao [FA].
**/
int SelecionaRoleta(int **geracao)
{
    int somaAvaliacao;
    somaAvaliacao = geracao[TAM_GERACAO-1][FA];//Como a FQ. Acumulada já está calculada, a soma está no último elemento da geracao

    int i;
    //int rdm = rand() % somaAvaliacao; // Gera um número aleatório entre 0 e somaAvaliacao
    uint64_t rdm = (rand() * RAND_MAX) % somaAvaliacao; //VERIFICAR

    //printf("\nRANDOM: %i",rdm);

    for(i=0;i<TAM_GERACAO;i++)
        if(geracao[i][FA] > rdm)
        {
            return i; //Retorna índice
        }

    return -1;
}

/**
    Seleciona um indivíduo baseado no método do torneio e retorna o índice.
**/
int SelecionaTorneio(int **geracao,int tamTorneio)
{
    int melhor = -1;
    int indexMelhor = -1;
    int rdm,i;

    for(i = 0; i< tamTorneio;i++) //Seleciona k individuos
    {
        rdm = rand() % TAM_GERACAO;
        if(melhor == -1 || geracao[rdm][AVAL] < melhor)
        {
            melhor = geracao[rdm][AVAL];
            indexMelhor = rdm;
        }
    }
    return indexMelhor; //Melhor dentre os selecionados
}

<file_sep>/selecao.h
void CalculaFrequenciaAcumulada(int **geracao);
int SelecionaRoleta(int **geracao);
int SelecionaTorneio(int **geracao,int tamTorneio);
<file_sep>/populacao.c
#include <stdlib.h>
#include <stdio.h>
#include "populacao.h"
#include "defines.h"
#include "util.h"

/**
//<NAME>
**/
/*int CalculaAvaliacao(int *ind)
{
    //Calcula SEND:
    int eatArray[6] = {ind[D], ind[O], ind[N],ind[A],ind[L],ind[D]};
    int eat = ConcatenaArray(eatArray,6);

    //Calcula MORE:
    int thatArray[6] = {ind[G], ind[E], ind[R], ind[A],ind[L],ind[D]};
    int that = ConcatenaArray(thatArray,6);

    //Calcula MONEY:
    int appleArray[6] = {ind[R], ind[O], ind[B], ind[E], ind[R],ind[T]};
    int apple = ConcatenaArray(appleArray,6);

    int avaliacao = abs((eat+that)-apple);
    ind[AVAL] = avaliacao;

    return avaliacao;

}*/
/**
//COCA COLA OASIS
**/
/*int CalculaAvaliacao(int *ind)
{
    //Calcula SEND:
    int eatArray[4] = {ind[C], ind[O], ind[C],ind[A]};
    int eat = ConcatenaArray(eatArray,4);

    //Calcula MORE:
    int thatArray[4] = {ind[C], ind[O], ind[L], ind[A]};
    int that = ConcatenaArray(thatArray,4);

    //Calcula MONEY:
    int appleArray[5] = {ind[O], ind[A], ind[S], ind[I], ind[S]};
    int apple = ConcatenaArray(appleArray,5);

    int avaliacao = abs((eat+that)-apple);
    ind[AVAL] = avaliacao;

    return avaliacao;

}*/
/**
//CROSS ROADS DANGER
**/
/*int CalculaAvaliacao(int *ind)
{
    //Calcula SEND:
    int eatArray[5] = {ind[C], ind[R], ind[O],ind[S],ind[S]};
    int eat = ConcatenaArray(eatArray,5);

    //Calcula MORE:
    int thatArray[5] = {ind[R], ind[O], ind[A], ind[D],ind[S]};
    int that = ConcatenaArray(thatArray,5);

    //Calcula MONEY:
    int appleArray[6] = {ind[D], ind[A], ind[N], ind[G], ind[E], ind[R]};
    int apple = ConcatenaArray(appleArray,6);

    int avaliacao = abs((eat+that)-apple);
    ind[AVAL] = avaliacao;

    return avaliacao;

}*/
/**
//EAT + THAT = APPLE
**/
/*int CalculaAvaliacao(int *ind)
{
    //Calcula SEND:
    int eatArray[3] = {ind[E], ind[A], ind[T]};
    int eat = ConcatenaArray(eatArray,3);

    //Calcula MORE:
    int thatArray[4] = {ind[T], ind[H], ind[A], ind[T]};
    int that = ConcatenaArray(thatArray,4);

    //Calcula MONEY:
    int appleArray[5] = {ind[A], ind[P], ind[P], ind[L], ind[E]};
    int apple = ConcatenaArray(appleArray,5);

    int avaliacao = abs((eat+that)-apple);
    ind[AVAL] = avaliacao;

    return avaliacao;

}*/
/**
    Avalia um indivíduo com a equação: (SEND + MORE) - MONEY = AVALIACAO
    Melhor valor é o mais próximo de 0.
**/

int CalculaAvaliacao(int *ind)
{
    //Calcula SEND:
    int sendArray[4] = {ind[S], ind[E], ind[N], ind[D]};
    int send = ConcatenaArray(sendArray,4);

    //Calcula MORE:
    int moreArray[4] = {ind[M], ind[O], ind[R], ind[E]};
    int more = ConcatenaArray(moreArray,4);

    //Calcula MONEY:
    int moneyArray[5] = {ind[M], ind[O], ind[N], ind[E], ind[Y]};
    int money = ConcatenaArray(moneyArray,5);

    int avaliacao = abs((send+more)-money);
    ind[AVAL] = avaliacao;

    //printf("\nSEND: %i",send);
    //printf("\nMORE: %i",more);
    //printf("\nMONEY: %i",money);
    //printf("\n\nSEND + MORE - MONEY = %i",avaliacao);
    return avaliacao;

}

/**
    Gera 10 números aleatórios únicos entre 0 e 9 e retorna.
**/
int* GeraIndividuo()
{
    int *ind = (int*) malloc(sizeof(int)*TAM_TOTAL);
    int i = 0;

    for(i = 0;i<TAM_TOTAL;i++) //Inicializa vetor.
        ind[i] = -1;

    i = 0;
    while(i < TAM_INDIVIDUO_TOTAL)
    {
        int n = rand() % 10; //Gera número aleatório.
        int flagExiste = 0;
        int j;

        for(j=0;j<TAM_INDIVIDUO_TOTAL;j++) //Verifica se o número gerado não está no array.
        {
            if(ind[j] == n) flagExiste = 1;
        }
        if(!flagExiste) //Se o número não está no array.
        {
            ind[i] = n;
            i++;
        }

    }
    return ind;
}
int **GeraPopulacao(int *somaAvaliacao)
{
    int i;
    int **geracao = (int**) malloc(sizeof(int*)*TAM_GERACAO_TOTAL);
    *somaAvaliacao = 0;
    for(i=0;i<TAM_GERACAO_TOTAL;i++)
    {
        if(i< TAM_GERACAO)
        {
            int *ind = GeraIndividuo();
            *somaAvaliacao += CalculaAvaliacao(ind);
            geracao[i] = ind;
        }
        else //Aloca posição dos filhos
        {
            geracao[i] = (int*) malloc(sizeof(int)*TAM_TOTAL);
            geracao[i][AVAL] = -1;
            geracao[i][FA] = -1;
        }

    }
    return geracao;
}

void FreePopulacao(int** geracao)
{
    int i;
    for(i=0;i<TAM_GERACAO_TOTAL;i++)
    {
        free(geracao[i]);
    }
    free(geracao);

}


<file_sep>/populacao.h
int CalculaAvaliacao(int *ind);
int *GeraIndividuo();
int **GeraPopulacao(int *somaAvaliacao);
void FreePopulacao(int** geracao);
<file_sep>/crossover.h
void Mutacao(int *ind);
void CrossOverSimples(int* ind1,int* ind2,int pontoCrossOver,int* filho1,int* filho2);
int **CrossOverMultiplo(int* pai1,int* pai2,int *pontosCrossOver,int n);
void CrossOverCiclico(int* pai1,int* pai2,int* filho1,int* filho2);
void MutacaoFilhos(int **geracao,int qtdInd,int qtdFilhos);
<file_sep>/defines.h
#define N_ITERACOES 1000
#define N_GERACOES 200 //Numero maximo de geracoes

#define TAM_GERACAO 150 //Quantidade de individuos na populacao(Representa 100%)
#define TAM_GERACAO_TOTAL 300 //TAM_GERACAO + FILHOS (DEVE SER PAR)

#define TAM_INDIVIDUO 8
#define TAM_INDIVIDUO_TOTAL 10
#define TAM_TOTAL 12 //TAM_INDIVIDUO + APTIDAO + FREQ. ACUMULADA

#define TX_CROSSOVER 150// 80% dos individuos sao selecionados para crossover
#define TX_ELITISMO 20 //20% dos melhores pais sao mantidos
#define TX_MUTACAO 150 //20% dos individuos sofrem mutacao

#define ROLETA 1
#define TORNEIO 0

#define ELITISMO 0
#define MELHORPAISFILHOS 1

enum individuo
{
    S,E,N,D,M,O,R,Y,D1,D2,AVAL,FA
};

//EAT THAT APPLE
/*enum individuo
{
    E,A,T,H,P,L,D1,D2,D3,D4,AVAL,FA
};*/

//CROSS ROADS DANGER
/*enum individuo
{
    C,R,O,S,A,D,N,G,E,D1,AVAL,FA
};*/

//COCA COLA OASIS
/*enum individuo
{
    C,O,A,L,S,I,D1,D2,D3,D4,AVAL,FA
};*/

//DONALD GERALD ROBERT
/*
enum individuo
{
    D,O,N,A,L,G,E,R,B,T,AVAL,FA
};*/
<file_sep>/crossover.c
#include <stdlib.h>
#include <stdio.h>
#include "crossover.h"
#include "defines.h"
#include "populacao.h"


/**
    Gera dois filhos usando CrossOver Ciclico
**/
void CrossOverCiclico(int* pai1,int* pai2,int* filho1,int* filho2)
{
    int i;

    int tam_ciclo = 1; //Ciclo começa com tamanho 1
    int *ciclo = (int *) malloc(sizeof(int));
    if(ciclo == NULL) return;

    int mascara[TAM_INDIVIDUO_TOTAL]; //Mascara para ser usada no crossover em si
    for(i=0;i<TAM_INDIVIDUO_TOTAL;i++) mascara[i] = 0;

    int posAtual = 0; //posAtual do ciclo
    ciclo[0] = 0;
    mascara[0] = 1;
    int flagCiclo = 0;
    while(!flagCiclo)
    {
        int elementoPai2 = pai2[posAtual]; //desce no pai2

        if(elementoPai2 == pai1[ciclo[0]])//Verifica se o ciclo foi completo
        {
            flagCiclo = 1;
            break;
        }

        //procura o elemento em pai1
        for(i=0;i<TAM_INDIVIDUO_TOTAL;i++)
        {
            if(elementoPai2 == pai1[i])
            {
                posAtual = i;
                break;
            }
        }

        //Adiciona elemento no ciclo
        tam_ciclo++;
        ciclo = (int*) realloc(ciclo,sizeof(int)*tam_ciclo); //Realoca vetor
        ciclo[tam_ciclo-1] = posAtual; //Pega posicao
        mascara[posAtual] = 1;
    }

    for(i = 0;i<TAM_INDIVIDUO_TOTAL;i++)
    {
        if(mascara[i] == 1)
        {
            filho1[i] = pai1[i];
            filho2[i] = pai2[i];
        }
        else
        {
            filho1[i] = pai2[i];
            filho2[i] = pai1[i];
        }
    }
    filho1[AVAL] = -1;
    filho1[AVAL] = -1;
}

/**
    Faz mutação em qtdInd indivíduos(Entre as posições dos filhos)
**/
void MutacaoFilhos(int **geracao,int qtdInd,int qtdFilhos)
{
    int i;

    for(i=TAM_GERACAO;i<(TAM_GERACAO + qtdInd);i++)
    {
        int rdm = (rand() % (qtdFilhos)) + TAM_GERACAO;
        Mutacao(geracao[rdm]);
    }
}
/**
    Faz mutação em uma das posições do indíviduo.
**/
void Mutacao(int *ind)
{
    int pontoMutacao = rand() % TAM_INDIVIDUO;
    int pontoMutacao2 = rand() % TAM_INDIVIDUO;
    while(pontoMutacao2 == pontoMutacao) pontoMutacao2 = rand() % TAM_INDIVIDUO;

    int aux = ind[pontoMutacao];
    ind[pontoMutacao] = ind[pontoMutacao2];
    ind[pontoMutacao2] = aux;

    CalculaAvaliacao(ind);

}
/**
    Gera dois filhos com crossover no ponto especificado
**/
void CrossOverSimples(int* pai1,int* pai2,int pontoCrossOver,int* filho1,int* filho2)
{
    int i = 0;

    for(i = 0;i<TAM_INDIVIDUO_TOTAL;i++)
    {
        if(i <= pontoCrossOver)
        {
            filho1[i] = pai1[i];
            filho2[i] = pai2[i];
        }
        else
        {
            filho1[i] = pai2[i];
            filho2[i] = pai1[i];
        }
    }

    CalculaAvaliacao(filho1);
    CalculaAvaliacao(filho2);
}

/**
    Gera dois filhos com crossover nos pontos especificados
    N = numero de pontos no array *pontosCrossOver
    O array *pontosCrossOver deve estar ordenado

    TODO: Retirar alocação
**/
int **CrossOverMultiplo(int* pai1,int* pai2,int *pontosCrossOver,int n)
{
    int **filhos = (int**) malloc(sizeof(int*)*2);
    filhos[0] = (int*) malloc(sizeof(int)*TAM_INDIVIDUO);
    filhos[1] = (int*) malloc(sizeof(int)*TAM_INDIVIDUO);

    if(filhos == NULL || filhos[0] == NULL || filhos[1] == NULL) return NULL;

    int i = 0;
    int j = 0; //Percorre *pontosCrossOver
    int flagInd = 0;

    for(i = 0;i<TAM_INDIVIDUO;i++)
    {
        if(!flagInd)
        {
            filhos[0][i] = pai1[i];
            filhos[1][i] = pai2[i];
        }
        else
        {
            filhos[0][i] = pai2[i];
            filhos[1][i] = pai1[i];
        }
        if(i == pontosCrossOver[j])
        {
            flagInd = !flagInd;
            j++;
        }
    }

    printf("\nFilho1: ");
    for(i=0;i<TAM_INDIVIDUO;i++)
        printf("%i",filhos[0][i]);

    printf("\nFilho2: ");
    for(i=0;i<TAM_INDIVIDUO;i++)
        printf("%i",filhos[1][i]);

    return filhos;
}



<file_sep>/util.h
int ConcatenaArray(int* arr, int len);
int partition(int **geracao, int l, int r);
void quickSort(int **geracao, int l, int r);
void printg(int **geracao);
void SobeFilhos(int **geracao,int posIni,int qtdFilhos,int posFilho);
int VerificaMatriz(int **geracao);
void printind(int *ind);

