Algoritmo Genetico problema de las n reinas

[kjg]

tengo el siguiente algoritmo para resolver el problema de la n reinas con algoritmo genetico, mi duda es como podria adaptarlo para un estilo de seleccion por torneo

Código (c) [Seleccionar] Expandir


#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>




int TamT = 8;

int area[50][50];

int chromosomeMatriz[50][100000];
int CostoMatriz[10000];
int MatrizCruz[50][100000];
int Poblacion = 100000;
int Iteracion = 100000;
float MutacionR = 0.5;


void Clear(){
int i, j;
for (i=0;i<TamT;i++)
for (j=0;j<TamT;j++)
area[i][j]=0;
}


void PoblacionInicial(){
int random, index, a, b, bCheck;

for (index=0; index<=Poblacion-1; index++){
for (a=0; a<TamT; a++){
random = rand();
bCheck = 1;

for(b=0; b<a; b++){
if(random % TamT == chromosomeMatriz[b][index])
bCheck=0;
if(bCheck)
chromosomeMatriz[a][index] = random % TamT;
else
a--;
}
}
}
}


void LlenarArea(int index){
int i;

    Clear();
    for (i=0; i<TamT; i++)
        area[i][chromosomeMatriz[i][index]]=1;
}


int CostFunc(int index){
    int costValue=0;
    int m,n;
    int i,j;

    for(i=0;i<TamT;i++){   
        j=chromosomeMatriz[i][index];

        m=i+1;
        n=j-1;
        while(m<TamT && n>=0){
            if(area[m][n]==1) costValue++;
            m++;
            n--;
        }

        m=i+1;
        n=j+1;
        while(m<TamT && n<TamT ){       
            if(area[m][n]==1) costValue++;           
            m++;
            n++;
        }

        m=i-1;
        n=j-1;
        while(m>=0 && n>=0){       
            if(area[m][n]==1) costValue++;
            m--;
            n--;
        }

        m=i-1;
        n=j+1;
        while(m>=0 && n<TamT){       
            if(area[m][n]==1) costValue++;           
            m--;
            n++;
        }
    }

    return costValue;
}


void PopulationSort(){
    int k=1, i, j;
    int Temp;
    while (k){
        k=0;
        for (i=0;i<=Poblacion-2;i++){
            if (CostoMatriz[i]>CostoMatriz[i+1]){
                Temp=CostoMatriz[i];
                CostoMatriz[i] = CostoMatriz[i+1];
                CostoMatriz[i+1] = Temp;
               
            for (j=0; j<TamT; j++){
                Temp=chromosomeMatriz[j][i];
                chromosomeMatriz[j][i] = chromosomeMatriz[j][i+1];
                chromosomeMatriz[j][i+1] = Temp;
            }           
            k=1;
            }
        }
    }
}


void GenerateCrossOverMatrix(){
    int randomCrossOver, index, a;

    for (index=0;index<=Poblacion-1;index++){
        for (a=0;a<TamT;a++){
            randomCrossOver=rand();
           MatrizCruz[a][index]=randomCrossOver%2;
        }
    }
}


void Mating(){
int TempMatrix[50][2];
int TempMatrix0[50],TempMatrix1[50];
int Temp,j,k, index, t, i;

for (index=0;index<=(Poblacion/4)-1;index++){
for (t=0;t<=1;t++){

for(i=0;i<TamT;i++){
TempMatrix0[i]=chromosomeMatriz[i][2*index];
TempMatrix1[i]=chromosomeMatriz[i][2*index+1];
}
for (i=0;i<TamT;i++)
if(MatrizCruz[i][2*index+t]==0){
for (j=0;j<TamT;j++)
if(TempMatrix0[j]!=100){
TempMatrix[i][t]=TempMatrix0[j];
Temp=TempMatrix0[j];
TempMatrix0[j]=100;
j=TamT-1;

for (k=0;k<TamT;k++){
if (TempMatrix1[k]==Temp){
TempMatrix1[k]=100;
k=TamT-1;
}
}
}
}else{
for (j=0;j<TamT;j++)
if(TempMatrix1[j]!=100){
TempMatrix[i][t]=TempMatrix1[j];
Temp=TempMatrix1[j];
TempMatrix1[j]=100;
j=TamT-1;

for (k=0;k<TamT;k++){
if (TempMatrix0[k]==Temp){
TempMatrix0[k]=100;
k=TamT-1;
}
}
}
}

for(i=0;i<TamT;i++)
chromosomeMatriz[i][2*index+Poblacion/2+t]=TempMatrix[i][t];

}
}
}


void ApplyMutation(){
int randomChromosome;
int randomGen0,randomGen1;
int Temp, k;
int NumberOfMutation = (int)MutacionR*(Poblacion-1)*TamT;

for(k=0;k<=NumberOfMutation;k++){
randomChromosome=0;
while((randomChromosome=rand()%Poblacion)==0);

randomGen0=rand()%TamT;
while((randomGen1=rand()%TamT)==randomGen0);

Temp=chromosomeMatriz[randomGen0][randomChromosome];
chromosomeMatriz[randomGen0][randomChromosome]=chromosomeMatriz[randomGen1][randomChromosome];
chromosomeMatriz[randomGen0][randomChromosome]=Temp;
}

}


void DisplayBoard(){
int i, j;

for(i=0; i<=TamT-1; i++){
for(j=0; j<=TamT-1; j++){
if(j == chromosomeMatriz[i][0]){
printf("0  ");
}else{
printf(".  ");
}
}
printf("\n");
}

printf("\n");
}

int main(){
     
int i,k,g,num;
char a='g';

k=0;
g=0;
num=0;

printf("\nNumero de reinas: ");
scanf("%d", &TamT);

printf("Numero de poblacion (ex 1000): ");
scanf("%d", &Poblacion);

printf("Numarul de iteratii (ex 1000): ");
scanf("%d", &Iteracion);

printf("Rata de mutatie (ex 0.5): ");
scanf("%f", &MutacionR);

printf("\nSolutie:\n");

PoblacionInicial();

while(g==0 && num<Iteracion){
num++;
g=0;

for (k=0;k<=Poblacion-1;k++){
LlenarArea(k);
CostoMatriz[k]=CostFunc(k);
}

PopulationSort();

if (CostoMatriz[0]==0) g=1;

DisplayBoard();

GenerateCrossOverMatrix();

Mating();

ApplyMutation();

system("PAUSE");
return 0;
}
}






[MAFUS]

Edita el post y pon el código entre etiquetas GeSHi. Las tienes justo encima de la caja de texto.