C - N 皇后的遗传算法

Question

我正在想办法使用遗传算法解决 N 个皇后问题。

程序如下：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 8
#define POP 8

int answers[SIZE] = {5,3,1,7,4,6,0,2};

int getRand(int mod){
    if (mod==0) return 0;
    else return random()%mod;
}

void printArray(int array[]){
    int i;
    for(i=0; i<SIZE-1; i++) printf("(%i,%i),",i,array[i]);
    printf("(%i,%i)",SIZE-1,array[SIZE-1]);
    printf("\n");
}

int getWeight(int array[]){
    int weight = 28;
    int queen;
    for(queen=0;queen<SIZE;queen++){    //for each queen
        int nextqueen;
        for(nextqueen=queen+1;nextqueen<SIZE;nextqueen++){        //for each of the other queens (nextqueen = queen to avoid counting pairs twice)
            if(array[queen] == array[nextqueen] || abs(queen-nextqueen)==abs(array[queen]-array[nextqueen])){   //if conflict
                weight--;
            }
        }
    }
    return weight;
}

void geneticAlgorithm(){
    int population[POP][SIZE];
    int children[POP][SIZE];
    int weightProb[224] = {};
    int wpl = 0; //weightProb[] length
    float mutProb = 0.2; //higher prob yields faster times. works decently anyways. bug: prob = 0
    int done = 0;
    int i;
    for(i=0;i<POP;i++) for(int j=0;j<SIZE;j++) population[i][j] = getRand(SIZE);
    while(done == 0){        
        for(i=0;i<POP;i++){
            if(getWeight(children[i]) == 28){
                printf("solution: ");
                printArray(children[i]);
                done = 1;
            }
        }

        for(i=0;i<wpl;i++) weightProb[i] = (int)NULL; //clear weightprob
        wpl=0;

        //weighted probability distribution
        for(i=0;i<POP;i++){
            int w = getWeight(population[i]);
            for(int j=0;j<w;j++){
                weightProb[wpl] = i; //fill array with member number w times
                wpl++;
            }
        }

        //reproduce
        for(i=0;i<POP;i+=2){
            int par1 = weightProb[getRand(wpl)];
            int par2 = weightProb[getRand(wpl)];
            int split = getRand(SIZE);
            //crossover
            for(int j=0;j<split;j++){
                children[i][j] = population[par1][j];
                children[i+1][j] = population[par2][j];
            }
            for(int j=split;j<SIZE;j++){
                children[i][j] = population[par2][j];
                children[i+1][j] = population[par1][j];
            }
            //mutation
            if(getRand(1000000)<=mutProb*1000000){
                int child=getRand(2);
                if(child == 0) children[i][getRand(SIZE)] = getRand(SIZE);
                else children[i+1][getRand(SIZE)] = getRand(SIZE);
            }
        }
        for(i=0;i<POP;i++) for(int j=0;j<SIZE;j++) population[i][j] = children[i][j];
        wpl = 0;
    }
}

int main(int argc, const char * argv[]){
    srandom((unsigned int)time(NULL));  //seed random
    geneticAlgorithm();
    return 0;
}

程序正确运行和编译，但没有产生我想要的结果。我想显示每个皇后的 x、y 坐标，并简单地将它们打印出来。然而，相反，我在输出中得到随机垃圾，我无法弄清楚为什么。

当前输出示例：

(0,0) (1,3248234234) (2,0) (3,-3248236736) (4,57435727) (5,234743567) (6, 23498348) (7,23487234)

期望的输出示例（N 皇后问题的解决方案）：

(3,4) (7,2) (0,3) (4,6) (6,5) (1,7) (5,1) (2,0)

Answer 1

不确定这是否是导致您的特定问题的原因，但这是一个问题：

for(i=0;i<POP;i++) for(int j=0;j<SIZE;j++) population[i][j] = getRand(SIZE);
while(done == 0){        
    for(i=0;i<POP;i++){
        if(getWeight(children[i]) == 28){
            printf("solution: ");
            printArray(children[i]);
            done = 1;
        }
    }

以上是种群的初始化和循环的开始。第一次通过时，children 数组包含未初始化的数据。

鉴于算法的其余部分，您需要检查 population 元素的权重（并打印来自 population 的元素）是否获胜，而不是 children.

C - N 皇后的遗传算法

C - Genetic Algorithm for N Queens

c

algorithm

genetic