non_domination_sort.c

多目标算法的DSP实现。可以直接在DSP平台上进行多目标优化

# include <stdio.h>
# include <math.h>

# include "malloc.h"
# include "global.h"

// # include "list.c"
// # include "merge.c"
// # include "crowding_distance.c"
// # include "sort.c"

//  混合群体的非支配解排序
void non_domination_sort (population *mixed_pop, population *new_pop)
{
    int flag;
    int i, j, k;
    int end;
    int front_size;
    int archive_size;
    int rank = 1;
    list *pool;
    list *elite;
    list *temp1, *temp2;
    pool = (list *)malloc(sizeof(list));
    elite = (list *)malloc(sizeof(list));
    front_size = 0;
    archive_size = 0;
    pool->index = -1;
    pool->prior = NULL;
    pool->next = NULL;
    elite->index = -1;
    elite->prior = NULL;
    elite->next = NULL;
    temp1 = pool;
    for (i=0; i<2*POPSIZE; i++)
    {
        insert (temp1, i);
        temp1 = temp1->next;
    }
    j = 0;	
    do
    {
        temp1 = pool->next;
        insert (elite, temp1->index);
        front_size = 1;
        temp2 = elite->next;
        temp1 = del (temp1);
        temp1 = temp1->next;
        do
        {
            temp2 = elite->next;
            if (temp1==NULL)
            {
                break;
            }
            do
            {
                end = 0;
                flag = check_dominance (&(mixed_pop->ind[temp1->index]), &(mixed_pop->ind[temp2->index]));
				if (flag == 1)
                {
                    insert (pool, temp2->index);
                    temp2 = del (temp2);
                    front_size--;
                    temp2 = temp2->next;
                }
                if (flag == 0)
                {
                    temp2 = temp2->next;
                }
                if (flag == -1)
                {
                    end = 1;
                }
            }
            while (end!=1 && temp2!=NULL);
            if (flag == 0 || flag == 1)
            {
                insert (elite, temp1->index);
                front_size++;
                temp1 = del (temp1);
            }
            temp1 = temp1->next;
        }
        while (temp1 != NULL);
        temp2 = elite->next;
        k = j;
        if ( (archive_size + front_size) <= POPSIZE)
        {
            do
            {
                copy_ind (&mixed_pop->ind[temp2->index], &new_pop->ind[j]);
                new_pop->ind[j].rank = rank;
                archive_size++;
                temp2 = temp2->next;
                j++;
            }
            while (temp2 != NULL);
            crowding_distance_index (new_pop, k, j-1);
            rank++;
        }
        else
        {
            crowding_sort_descend (mixed_pop, new_pop, j, front_size, elite);
            archive_size = POPSIZE;
            for (k=j; k<POPSIZE; k++)
            {
                new_pop->ind[k].rank = rank;
            }
        }
        temp2 = elite->next;
        do
        {
            temp2 = del (temp2);
            temp2 = temp2->next;
        }
        while (elite->next !=NULL);
    }
    while (archive_size < POPSIZE);
    while (pool != NULL)
    {
        temp1 = pool;
        pool = pool->next;
        free (temp1);
    }
    while (elite != NULL)
    {
        temp1 = elite;
        elite = elite->next;
        free (temp1);
    }
    return;
}

// 按降序对拥挤距离排序
void crowding_sort_descend (population *mixed_pop, population *new_pop, int count, int front_size, list *elite)
{
    int *dist;
    list *temp;
    int i, j;
    crowding_distance_list (mixed_pop, elite->next, front_size);
    dist = (int *)malloc(front_size*sizeof(int));
    temp = elite->next;
    for (j=0; j<front_size; j++)
    {
        dist[j] = temp->index;
        temp = temp->next;
    }
    quicksort (mixed_pop, dist, front_size);
    for (i=count, j=front_size-1; i<POPSIZE; i++, j--)
    {
        copy_ind(&mixed_pop->ind[dist[j]], &new_pop->ind[i]);
    }
    free (dist);
    return;
}