Прежде всего, я ненавижу задавать такой расплывчатый вопрос, как этот, но здесь я на пределе. Я пытаюсь создать генетический алгоритм для классической задачи коммивояжера CS.
Я попытался хорошо прокомментировать свой код, чтобы сделать каждый шаг очевидным в отношении того, что я пытаюсь сделать.
У меня есть объект struct Node, который содержит индекс города и координаты x, y. Я читаю список городов из файла и передаю массив структурных узлов и их количество в свою функцию.
Если у вас есть какие либо вопросы, пожалуйста спрашивайте. Графический интерфейс обновляется каждые ~ 1000 итераций, и он определенно меняется, но НИКОГДА, кажется, не становится лучше, даже когда я запускаю количество поколений в течение ОЧЕНЬ долгого времени!
Кроме того, если вы запутались, я возвращаю расстояние как uint64_t для большей точности и переносимости, чем double, но я преобразовываю их в тип 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
