spea2_functions.c

SPEA2源码

	    {
		if (my_dist > prev_min_dist ||
		    (my_dist == prev_min_dist && i > prev_min_index))
		{
		    min_dist = my_dist;
		    min_index = i;
		}
	    }
	}
	
	NN[index][k] = min_index;
    }

    return (NN[index][k]);
}


double getNNd(int index, int k)
/* Returns the distance to the k-th nearest neigbor
   if this individual is still in the population.
   For for already deleted individuals, returns -1 */
{
    int neighbor_index = getNN(index, k);
    
    if (copies[neighbor_index] == 0)
	return (-1);
    else
	return (dist[index][neighbor_index]);
}


void environmentalSelection()
{
    int i;
    int new_size = 0;
    
    if (fitness_bucket[0] > alpha)
    {
	truncate_nondominated();
    }
    else if (pp_all->size > alpha)
    {
	truncate_dominated();
    }

    /* Move remaining individuals to top of array in 'pp_all' */
    for (i = 0; i < pp_all->size; i++)
    {
	ind* temp_ind = pp_all->ind_array[i];
	if (temp_ind != NULL)
	{
	    assert(copies[i] > 0);	    
	    pp_all->ind_array[i] = NULL;
	    pp_all->ind_array[new_size] = temp_ind;
	    old_index[new_size] = i;
	    new_size++;    
	}
    }
    assert(new_size <= alpha);
    pp_all->size = new_size;
    
    return;
}


void truncate_nondominated()
/* truncate from nondominated individuals (if too many) */
{
    int i;	

    /* delete all dominated individuals */
    for (i = 0; i < pp_all->size; i++)
    {
	if (pp_all->ind_array[i]->fitness > 0)
	{
	    free_ind(pp_all->ind_array[i]);
	    pp_all->ind_array[i] = NULL;
	    copies[i] = 0;
	}
    }
    
    /* truncate from non-dominated individuals */
    while (fitness_bucket[0] > alpha)
    {
	int *marked;
	int max_copies = 0;
	int count = 0;
	int delete_index;

	marked = (int*) chk_malloc(pp_all->size * sizeof(int));

	/* compute inds with maximal copies */
	for (i = 0; i < pp_all->size; i++)
	{
	    if (copies[i] > max_copies)
	    {
		count = 0;
		max_copies = copies[i];
	    }
	    if (copies[i] == max_copies)
	    {
		marked[count] = i;
		count++;
	    }
	}
	
	assert(count >= max_copies);
	
	if (count > max_copies)
	{    
	    int *neighbor;
	    neighbor = (int*) chk_malloc(count * sizeof(int));
	    for (i = 0; i < count; i++)
	    {
		neighbor[i] = 1;  /* pointers to next neighbor */
	    }
	    
	    while (count > max_copies)
	    {
		double min_dist = PISA_MAXDOUBLE;
		int count2 = 0;
		
		for (i = 0; i < count; i++)
		{
		    double my_dist = -1;
		    while (my_dist == -1 && neighbor[i] < pp_all->size)
		    {
			my_dist = getNNd(marked[i],neighbor[i]);
			neighbor[i]++;
		    }
		    
		    if (my_dist < min_dist)
		    {
			count2 = 0;
			min_dist = my_dist;
		    }
		    if (my_dist == min_dist)
		    {
			marked[count2] = marked[i];
			neighbor[count2] = neighbor[i];
			count2++;
		    }
		}
		count = count2;
		if (min_dist == -1) /* all have equal distances */
		{
		    break;
		}
	    }   
	    free(neighbor);
            neighbor = NULL;
	}
	
	/* remove individual from population */
	delete_index = marked[irand(count)];
	free_ind(pp_all->ind_array[delete_index]);
	pp_all->ind_array[delete_index] = NULL;
	for (i = 0; i < count; i++)
	{
	    if (dist[delete_index][marked[i]] == 0)
	    {
		copies[marked[i]]--;
	    }
	}
	copies[delete_index] = 0; /* Indicates that this index is empty */
	fitness_bucket[0]--;
	fitness_bucket_mod[0]--;
	free(marked);
        marked = NULL;
    }
    
    return;
}


void truncate_dominated()
/* truncate from dominated individuals */
{
    int i, j;
    int size;
    int num = 0;
    
    size = pp_all->size;
    
    i = -1;
    while (num < alpha)
    {
	i++;
	num += fitness_bucket_mod[i];
    }
    
    j = i * size;
    num = num - fitness_bucket_mod[i] + fitness_bucket[j];
    while (num < alpha)
    {
	j++;
	num += fitness_bucket[j];
    }
    
    if (num == alpha)
    {
	for (i = 0; i < size; i++)
	{
	    if (pp_all->ind_array[i]->fitness > j)
	    {
		free_ind(pp_all->ind_array[i]);
		pp_all->ind_array[i] = NULL;
	    }
	}
    }
    else /* if not all fit into the next generation */
    {
	int k;
	int free_spaces;
	int fill_level = 0;
	int *best = NULL;

	free_spaces = alpha - (num - fitness_bucket[j]);
	best = (int*) chk_malloc(free_spaces * sizeof(int));
	for (i = 0; i < size; i++)
	{
	    if (pp_all->ind_array[i]->fitness > j)
	    {
		free_ind(pp_all->ind_array[i]);
		pp_all->ind_array[i] = NULL;
	    }
	    else if (pp_all->ind_array[i]->fitness == j)
	    {
		if (fill_level < free_spaces)
		{
		    best[fill_level] = i;
		    fill_level++;
		    for (k = fill_level - 1; k > 0; k--)
		    {
			int temp;
			if (getNNd(best[k], 1) <= getNNd(best[k - 1], 1))
			{
			    break;
			}
			temp = best[k];
			best[k] = best[k-1];
			best[k-1] = temp;
		    }
		}
		else
		{
		    if (getNNd(i, 1) <= getNNd(best[free_spaces - 1], 1))
		    {
			free_ind(pp_all->ind_array[i]);
			pp_all->ind_array[i] = NULL;
		    }
		    else
		    {
			free_ind(pp_all->ind_array[best[free_spaces - 1]]);
			pp_all->ind_array[best[free_spaces - 1]] = NULL;
			best[free_spaces - 1] = i;
			for (k = fill_level - 1; k > 0; k--)
			{
			    int temp;
			    if (getNNd(best[k], 1) <= getNNd(best[k - 1], 1))
			    {
				break;
			    }
			    temp = best[k];
			    best[k] = best[k-1];
			    best[k-1] = temp;
			}
		    }
		}
	    }
	}        
        free(best);
        best = NULL;
        return;
    }
}


void matingSelection()
/* Fills mating pool 'pp_sel' */
{
    int i, j;

    for (i = 0; i < mu; i++)
    {
	int winner = irand(pp_all->size);
	
	for (j = 1; j < tournament; j++)
	{
	    int opponent = irand(pp_all->size);
	    if (pp_all->ind_array[opponent]->fitness
		< pp_all->ind_array[winner]->fitness || winner == opponent)
	    {
		winner = opponent;
	    }
	    else if (pp_all->ind_array[opponent]->fitness
		     == pp_all->ind_array[winner]->fitness)
	    {
		if (dist[old_index[opponent]][getNN(old_index[opponent], 1)] >
		    dist[old_index[winner]][getNN(old_index[winner], 1)])
		{
		    winner = opponent;
		}
	    }
	}  
	pp_sel->ind_array[i] = pp_all->ind_array[winner];
    }
    pp_sel->size = mu;
}


void select_initial()
/* Performs initial selection. */
{
    selection();
}


void select_normal()
/* Performs normal selection.*/
{
    selection();
}


int dominates(ind *p_ind_a, ind *p_ind_b)
/* Determines if one individual dominates another.
   Minimizing fitness values. */
{
    int i;
    int a_is_worse = 0;
    int equal = 1;
    
     for (i = 0; i < dim && !a_is_worse; i++)
     {
	 a_is_worse = p_ind_a->f[i] > p_ind_b->f[i];
          equal = (p_ind_a->f[i] == p_ind_b->f[i]) && equal;
     }
     
     return (!equal && !a_is_worse);
}


int is_equal(ind *p_ind_a, ind *p_ind_b)
/* Determines if two individuals are equal in all objective values.*/
{
     int i;
     int equal = 1;
     
     for (i = 0; i < dim; i++)
	 equal = (p_ind_a->f[i] == p_ind_b->f[i]) && equal;
     
     return (equal);
}


double calcDistance(ind *p_ind_a, ind *p_ind_b)
{
    int i;
    double distance = 0;
    
    if (is_equal(p_ind_a, p_ind_b) == 1)
    {
	return (0);
    }
    
    for (i = 0; i < dim; i++)
	distance += pow(p_ind_a->f[i]-p_ind_b->f[i],2);
    
    if (0.0 == distance)
        distance = PISA_MINDOUBLE;

    return (sqrt(distance));
}


int irand(int range)
/* Generate a random integer. */
{
    int j;
    j=(int) ((double)range * (double) rand() / (RAND_MAX+1.0));
    return (j);
}


/*--------------------| data exchange functions |------------------------*/

int read_ini()
{
    int i;
    pp_new = create_pop(alpha, dim);
    
    for (i = 0; i < alpha; i++)
	pp_new->ind_array[i] = create_ind(dim);
    pp_new->size = alpha;
    
    return (read_pop(inifile, pp_new, alpha, dim));                    
}


int read_var()
{
    int i;
    pp_new = create_pop(lambda, dim);
    
    for (i = 0; i < lambda; i++)
	pp_new->ind_array[i] = create_ind(dim);
    
    pp_new->size = lambda;
    return (read_pop(varfile, pp_new, lambda, dim));
}


void write_sel()
{
    write_pop(selfile, pp_sel, mu);
}


void write_arc()
{
     write_pop(arcfile, pp_all, pp_all->size);
}


int check_sel()
{
     return (check_file(selfile));
}


int check_arc()
{
     return (check_file(arcfile));
}