rank.c

多目标遗传算法的程序

/* Rank assignment routine */

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

# include "global.h"
# include "rand.h"

/* Function to assign rank and crowding distance to a population of size pop_size*/
void assign_rank_and_crowding_distance (population *new_pop)
{
    int flag;
    int i;
    int end;
    int front_size;
    int rank=1;
    list *orig;//用于存储种群中所有个体序号
    list *cur;//用于暂时存储一层非支配个体的序号
    list *temp1, *temp2;
    orig = (list *)malloc(sizeof(list));
    cur = (list *)malloc(sizeof(list));
    front_size = 0;
    orig->index = -1;
    orig->parent = NULL;
    orig->child = NULL;
    cur->index = -1;
    cur->parent = NULL;
    cur->child = NULL;
    temp1 = orig;
    for (i=0; i<popsize; i++)
    {
        insert (temp1,i);
        temp1 = temp1->child;
    }
    do
	//循环一次，找出一层非支配集
    {
        if (orig->child->child == NULL) /*最后一个结点*/
        {
            new_pop->ind[orig->child->index].rank = rank;
            new_pop->ind[orig->child->index].crowd_dist = INF;
            break;
        }
        temp1 = orig->child;
        insert (cur, temp1->index);
        front_size = 1;//先将表orig中的第一个个体看成是非支配个体，故而front_size=1
        temp2 = cur->child;
        temp1 = del (temp1);//因为将表orig中的第一个个体看成是非支配个体，故而需删除该个体
        temp1 = temp1->child;
        do
		//寻找一层非支配集
        {
            temp2 = cur->child;
            do
            {
                end = 0;
                flag = check_dominance (&(new_pop->ind[temp1->index]), &(new_pop->ind[temp2->index]));
                if (flag == 1)
                {
					//被当前个支配的个体需从链表cur（即temp2）中删除,同时还需将该支配个重新
					//插入到链表orig中，以供寻找下一层非支配集
                    insert (orig, temp2->index);
                    temp2 = del (temp2);
                    front_size--;
                    temp2 = temp2->child;
                }
                if (flag == 0)
                {
                    temp2 = temp2->child;
                }
                if (flag == -1)
                {
                    end = 1;
                }
            }
            while (end!=1 && temp2!=NULL);
            if (flag == 0 || flag == 1)//说明找到一非支配个体
            {
                insert (cur, temp1->index);
                front_size++;
                temp1 = del (temp1);	/*删除种群中的非支配个体，以便于构造下一层的非支配个体*/
            }
            temp1 = temp1->child;
        }
        while (temp1 != NULL);
        temp2 = cur->child;
        do
        {
            new_pop->ind[temp2->index].rank = rank;
            temp2 = temp2->child;
        }
        while (temp2 != NULL);
        assign_crowding_distance_list (new_pop, cur->child, front_size);
        temp2 = cur->child;
        do	/* 清除cur中个体，以准备存储下一层的Non-dominated solutions */
        {
            temp2 = del (temp2);
            temp2 = temp2->child;
        }
        while (cur->child !=NULL);
        rank+=1;
    }
    while (orig->child!=NULL);
    free (orig);
    free (cur);
    return;
}