//
// main.cpp
// 遗传算法（八皇后问题）
//
// Created by Miss_Jian on 2018/9/21.
// Copyright © 2018年 Rx. All rights reserved.
//
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;
#define queenNum 8
#define popuNum 4
#define maxStep 10000
#define critical 0.05
void initialQueen(int queens[]) {
for (int i = 0; i < queenNum; i++) {
queens[i] = rand() % queenNum;
}
}
int getEachValue(int i,int site[]){
int value=0;
for(int j=0;j<queenNum;j++){
if(i==j) continue;
if(site[i]==site[j] || abs(site[i]-site[j])==abs(i-j))
value++;
}
return value;
}
int getValue(int row,int col,int siteQueue[]){
int site[queenNum];
memcpy(site, siteQueue, queenNum * sizeof(int));
site[col]=row;
int value=0;
for(int i=0;i<queenNum;i++){
value+=getEachValue( i, site);
}
return value/2;
}
int getParent(float probArr[]){
float sumPro=0;
float selectProb;
float prob=0;
for(int i=0;i<popuNum;i++){
sumPro+=probArr[i];
}
selectProb=(rand()/float(RAND_MAX))*sumPro;
for(int i=0;i<popuNum;i++){
prob+=probArr[i];
if(selectProb<=prob)
return i;
}
return -1;
}
void outputRuselt(int row, int population[]){
for(int i=0;i<queenNum;i++){
cout<<population[i]<<" ";
}
cout<<"\th = "<<getValue(population[0], 0, population)<<endl<<endl;
}
void childMutate(int child[]){
int newSite=0,i=0,j=rand()%queenNum;
//尽量使变异后的位置不和其他皇后同行
for(int t=0;t<queenNum && i<queenNum;t++){
newSite=rand()%queenNum;
for(i=0;i<queenNum;i++){
if(newSite==child[i])
break;
}
}
if(rand()/float(RAND_MAX)<critical){
child[j]=newSite;
}
}
void geneAlgorithm(int population[][queenNum]){
int fitness[popuNum]; //记录每个个体适应度
int child[popuNum][queenNum]; //子代种群
float fitProbab[popuNum]; //根据适应度计算不同选择概率
int over=0; //判断是否得到最优解
int bestFitness=queenNum*(queenNum-1)/2; //最佳适应度
for(int t=0;t<maxStep;t++){
int sumOffit=0; //适应度总和，用于计算概率
for(int i=0;i<popuNum;i++){
int curfit=getValue(population[i][0],0, population[i]);
//计算m个体适应度，若h=0得到最优解，over置1，退出循环
if(curfit==0){
cout<<"result: ";
outputRuselt(i,population[i]);
over=1;
break;
}
fitness[i]= bestFitness - curfit;
sumOffit+=fitness[i];
}
if(over==1)break; //over=1，退出循环计算
//概率矩阵计算
for(int i=0;i<popuNum;i++){
fitProbab[i]=(float)fitness[i]/sumOffit;
}
cout<<t<<" step:\n";
int x[popuNum],y[popuNum];
for(int i=0;i<popuNum;i++){
int select=rand()%7; //随机选择杂交位置
//得到配对个体
x[i]=getParent(fitProbab);
y[i]=getParent(fitProbab);
//杂交获得子代种群
cout<<"child "<<i<<"("<<x[i]<<","<<y[i]<<")"<<": ";
for(int j=0;j<queenNum;j++){
child[i][j]=population[(j<=select)?x[i]:y[i]][j];
}
//子代变异
childMutate(child[i]);
outputRuselt(i,child[i]);
}
cout<<endl;
for(int i=0;i<popuNum;i++){
for(int j=0;j<queenNum;j++){
population[i][j]=child[i][j];
}
}
}
}
int main(int argc, const char * argv[]) {
srand((int)time(0));
int population[popuNum][queenNum];
//得到随机种群
cout<<"原矩阵：\n";
for(int i=0;i<popuNum;i++){
cout<<"\nInitial population "<<i<<": ";
initialQueen(population[i]);
outputRuselt(i,population[i]);
}
cout<<endl<<endl;
//调用遗传算法求解
geneAlgorithm(population);
return 0;
}
