まず第一に、私はこのような漠然とした質問をするのは嫌いですが、ここで私の限界です。巡回セールスマンの古典的な CS 問題の遺伝的アルゴリズムを作成しようとしています。
私がやろうとしていることについて各ステップを明確にするなど、コードにコメントを付けようとしました。
都市インデックスと x、y 座標を含む struct Node オブジェクトがあります。ファイルから都市のリストを読み込んで、構造体ノードの配列とそれらの数を関数に渡しています。
ご不明な点がございましたら、お問い合わせください。GUIは〜1000回の反復ごとに更新されており、間違いなく変化していますが、非常に長い間世代数を実行しても、決して良くなることはありません!
また、混乱している場合は、距離を double よりも精度と移植性を高めるために uint64_t として返していますが、フィットネス関数を実行するときに double 型に変換しています。（これはすべて動作します、私はそれを確認しました）
改善されない理由についてエラーを見つけることができますか?
void GeneticAlgorithm(struct Node *cities, uint64_t *count)
{
//1 - pick initial random permutations for the population size
int populationSize =(*count)>10? ((*count)/5) : *count;
fprintf(stderr, "Population Size: %d\n", populationSize);
//population consists of populationSize elements (an element being a path)
struct Node population[populationSize][*count];
srand (time(NULL));
//Get Initial Paths
uint64_t i;
//iterate over pop. size
for(i=0; i<populationSize; i++){
//fill out path for each population
int j;
for(j=0; j<*count; j++){
int element = rand() % (int)(*count); // 0-count
while(hasBeenVisited(&cities[element]) == 0){
element = rand() % (int)(*count);
}
memcpy ( &(population[i][j]), &(cities[element]), sizeof(struct Node) );
setVisited(&cities[element]);
}
for(j=0;j<*count; j++){
(&cities[j])->visited = 0;
}
}
int j;
//Now, we have our population of randomly selected paths
struct Node children[populationSize][*count];
int generation, crossover;
uint64_t Distances[populationSize];
uint64_t TotalDistance = 0;
srand(time(NULL));
//Iterate over each generation. Basic idea is to do fitness function, generate
//probability for each, do selection and fill up children array until it has
//the same populationSize elements as original population, perhaps do a mutation,
//and replace population array.
for(generation=0; generation < 5; generation++){
/* Get Distance of Each Path and Total Sum of Distances */
TotalDistance = 0;
for(j=0; j<populationSize; j++){
Distances[j] = 0;
for(i=0; i<*count; i++){
if(i==((*count)-1)){
Distances[j] += distance(&(population[j][0]), &(population[j][i]));
}
else{
Distances[j] += distance(&(population[j][i]), &(population[j][i+1]));
}
}
TotalDistance += Distances[j];
}
/* FITNESS FUNCTION */
//Evaluate each of the population according to the fitness function (distance through the path)
double probability[*count];
double sumProbabilities = 0.0;
char tempDistanceString[32];
trimUintDigits(&TotalDistance);
uintcharf(tempDistanceString, TotalDistance);
double dTotalDistance = strtod(tempDistanceString, NULL);
for(i=0; i<populationSize; i++){
char buf[32];
//Distances are uint64_t, need to ensure 7 decimal place accuracy (trimuint does this)
//and uintcharf converts to a decimal representation in a string
trimUintDigits(&Distances[i]);
uintcharf(buf, Distances[i]);
double individualDistance = strtod(buf, NULL);
probability[i] = sumProbabilities + (individualDistance / totalDistance);
sumProbabilities += probability[i];
}
//set children to all 0 (will replace population)
memset(&children, 0, sizeof(struct Node)*populationSize*(*count));
double r;
int numChildren = 0;
//Iterate until number of children = current population size
while(numChildren < populationSize){
//0 <= r <=1
r = ((double) rand() / (RAND_MAX));
if(r>0.7){ //Doesn't always crossover!
memcpy(&children[numChildren], &population[numChildren], sizeof(struct Node) * (*count));
numChildren++;
continue;
}
r = ((double) rand() / (RAND_MAX));
r *= sumProbabilities;
double nextProb = 0;
//Pick the two parents for procreation, according to the roulette wheel probability
int par1=-1, par2=-1;
while(par1==-1){
for(i=0; i<populationSize; i++){
if(i==populationSize-1){
nextProb=probability[0];
}
else{
nextProb = probability[i+1];
}
if((r > probability[i]) && (r < nextProb)){
par1 = i;
break;
}
}
r = ((double) rand() / (RAND_MAX));
r *= sumProbabilities;
}
r = ((double) rand() / (RAND_MAX));
r*= sumProbabilities;
while(par2==-1){
for(i=0; i<populationSize; i++){
if(i==populationSize-1){
nextProb=probability[0];
}
else{
nextProb = probability[i+1];
}
if((par1 !=i) && (r > probability[i]) && (r < nextProb)){
par2 = i;
break;
}
}
r = ((double) rand() / (RAND_MAX));
r*= sumProbabilities;
}
//Pick my two parents
struct Node *parentOne = &(population[par1]);
struct Node *parentTwo = &(population[par2]);
//Picking a random number of genes from parent two, add them to the child.
//Then, iterate through parent 1 and add missing nodes to the child
int GenesFromParentTwo = rand() % (*count-1) + 1;
if(GenesFromParentTwo < 0 || GenesFromParentTwo > *count){
GenesFromParentTwo = 1;
}
//Copy First 'GenesFromParentTwo' Nodes From Parent 2 to Child
memcpy(&children[numChildren], &parentTwo[0], sizeof(struct Node)*GenesFromParentTwo);
int indicesContained[GenesFromParentTwo];
for(i=0; i<GenesFromParentTwo; i++){
indicesContained[i] = (int)children[numChildren][i].index;
}
//Copy Remaining Missing nodes from Parent 1 to Child
int numInsertions = 0;
for(i=*count; i>0; i--){
if(isContained(indicesContained, &parentOne[i], &GenesFromParentTwo)){
continue;
}
numInsertions++;
memcpy(&children[numChildren][GenesFromParentTwo-1+numInsertions], &parentOne[i], sizeof(struct Node));
}
numChildren++;
} //End crossover
//Replace Population with Children
for(i=0; i<populationSize; i++){
memcpy(&population[i], &children[i], sizeof(struct Node) * (*count));
}
//Mutate?
for(i=0; i<populationSize; i++){
for(j=0; j<*count; j++){
r = ((double) rand() / (RAND_MAX));
r *= 100;
//0 <= r <= 100
if(r <= 0.001 ){
//Mutate!
if(j==*count-1){
struct Node temp;
memcpy(&temp, &population[i][j], sizeof(struct Node));
memcpy(&population[i][j], &population[i][0], sizeof(struct Node));
memcpy(&population[i][0], &temp, sizeof(struct Node));
}
else{
struct Node temp;
memcpy(&temp, &population[i][j], sizeof(struct Node));
memcpy(&population[i][j], &population[i][j+1], sizeof(struct Node));
memcpy(&population[i][j+1], &temp, sizeof(struct Node));
}
}
}
}
//After crossing over each generation, pick the best and send to GUI
if(generation % 10000 == 0)
{
uint64_t shortestGenDistance = UINT64_MAX;
int elShortest = -0;
for (j = 0; j < populationSize; j++)
{
uint64_t tempDistance = 0;
for (i = 0; i < *count; i++)
{
if (i == *count - 1)
{
tempDistance += distance(&(population[j][0]), &(population[j][i]));
}
else
{
tempDistance += distance(&(population[j][i]), &(population[j][i + 1]));
}
}
if (tempDistance < shortestGenDistance)
{
shortestGenDistance = tempDistance;
elShortest = j;
}
}
char buffer[8192];
push_node_array_to_json(buffer, &population[elShortest][0], count, generation + 1);
push(buffer);
}
} //End Generations
} //End algorithm