prog_ga.cpp

用遗传算法解决01背包问题

// Copyright by Guo Ce, Sun Yat-sen University

#include <vcl.h>
#include <iostream.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include "comdef.cpp"


//---------------------------------------------------------------------------
double cp, mp;
int showprocess;
int gener_num;
int gene_number;
extern int gene_length;
extern int bag_capacity;


//---------------------------------------------------------------------------
void textout (AnsiString s);


//---------------------------------------------------------------------------
typedef struct Item
{
    int weight;
    int value;
} ITEM;

typedef struct
{
    int weight;
    int fit;
    int gene[MAXITEMS];
} GENE;


//---------------------------------------------------------------------------
GENE gene_p[MAXGENES], gene_n[MAXGENES];

extern ITEM items[MAXITEMS];

int pospf[MAXGENES];
int pos[MAXGENES];


//---------------------------------------------------------------------------
// 遗传算法入口
void run_ga (void);


void gene_initialize (void);
void gene_adjust(GENE *gene,int iD);


//---------------------------------------------------------------------------
// 初始化基因
void gene_initialize (void)
{
    int i, j;

    for (i=0; i<gene_number; i++)
    {
        for (j=0; j<gene_length; j++)
            gene_p[i].gene[j] = rand()%2;
        gene_adjust (gene_p, i);
    }
}


//---------------------------------------------------------------------------
// 背包溢出的修补性调整
// 随机选取物品拿出背包，直到消除溢出
void gene_adjust(GENE *gene,int iD)
{
    int j;
    gene[iD].weight = 0;
    gene[iD].fit = 0;

    for (j=0; j<gene_length; j++)
    {
        if (gene[iD].gene[j]==1)
        {
            gene[iD].weight += items[j].weight;
            gene[iD].fit += items[j].value;
        }
    }

    while (gene[iD].weight>bag_capacity)
    {
        int idModify = rand()%gene_length;
        if (gene[iD].gene[idModify]==1)
        {
            gene[iD].gene[idModify] = 0;
            gene[iD].weight  -= items[idModify].weight;
            gene[iD].fit -= items[idModify].value;
        }
    }
}


//---------------------------------------------------------------------------
// 轮盘赌系列子程序
// 计算基因片段（从segb到sege）的总适合度
int segb = 0;
int sege = 1;

int sumfit(int segb,int sege)
{
    int i;
    int sumF = 0;
    if (segb<sege)
    {
        for (i=segb; i<sege ;i++)
            sumF += gene_p[i].fit;
    }
    else
    {
        for (i=segb; i<gene_number ;i++)
            sumF += gene_p[i].fit;
        for (i=0; i<sege ;i++)
            sumF += gene_p[i].fit;
    }
    return sumF;
}


//---------------------------------------------------------------------------
// 轮盘赌主体
int calpos()
{
    double randprob;
    double crossprob;
    int pos;
    bool flag = true;
    int sumF, sumBE;

    randprob = rand()%1000/1000.0;
    sumF = sumfit(0,gene_number);

    while (flag)
    {
        sumBE = sumfit(segb,sege);
        crossprob = (double)sumBE/(double)sumF;
        if (crossprob>randprob)
        {
            pos = sege;
            segb = sege;
            flag = false;
        }
        sege++;
        if (sege>=gene_number)
            sege = 0;
    }
    return pos;
}


//---------------------------------------------------------------------------
// 基因排序程序组，选取适合程度最大的基因
// smf()用于选取最大适应值的基因，gene_sort为入口
// 已经考虑的基因不再次考虑，以vf数组记录访问情况
// 为节省时间和方便进化，排序结果记录入posfit数组，
// 不直接移动基因
bool vf[MAXGENES];
int smf(GENE *gene)
{
    int i;
    int maxpos = 0;
    for (i=0; i<gene_number; i++)
        if (!vf[i])
        {
            maxpos = i;
            i = gene_number;
        }

    for (i=0; i<gene_number ;i++)
        if (!vf[i]&&gene[maxpos].fit<gene[i].fit)
            maxpos = i;

    return maxpos;
}

void gene_sort(int *posfit, GENE *gene)
{
    int i;
    memset(vf, false, gene_length*sizeof(bool));

    for (i=0; i<gene_number ;i++)
    {
        posfit[i] = smf(gene);
        vf[posfit[i]] = true;
    }
}


//---------------------------------------------------------------------------
// 旧有父本基因死亡，新产生的基因成为父本
// 首先，按照存优比例保护父亲本基因
// 然后，保留新一代中的的优秀基因

// 最近修改：08.10.20中午
// 从“被保护基因不杂交”
// 改为“所有基因都可参加杂交”

void updateall()
{
    int i;
    for (i=gene_number*cp; i<gene_number; i++)
        gene_p[pospf[i]] = gene_p[pospf[i-(int)(gene_number*cp)]];
    for (i=0; i<gene_number*cp ;i++)
        gene_p[pospf[i]] = gene_n[pos[i]];
}


//---------------------------------------------------------------------------
// 杂交, 每次操作一对基因，父母用轮盘赌敲定
// 杂交子代放置位置为i和(gene_number/2+i)
// 杂交前后将所有基因按照适应度由大到小大小排序
void crossover()
{
    int partpos;
    int father, mother;
    int i, j;

    gene_sort(pospf,gene_p);

    for (i=0; i<gene_number/2 ;i++)
    {
        partpos = rand()%gene_length;

        father = calpos();
        mother = calpos();

        for (j=0; j<partpos ;j++)
        {
            gene_n[i].gene[j] = gene_p[father].gene[j];
            gene_n[i+gene_number/2].gene[j] = gene_p[mother].gene[j];
        }
        for (;j<gene_length;j++)
        {
            gene_n[i].gene[j] = gene_p[father].gene[j];
            gene_n[i+gene_number/2].gene[j] = gene_p[mother].gene[j];
        }
        gene_adjust(gene_n,i);
        gene_adjust(gene_n,i+gene_number/2);
    }

    gene_sort (pos,gene_n);
}


//---------------------------------------------------------------------------
// 变异，随机抽取基因的一个位，在背包不溢出的前提下取反
// 以避免修补操作
void mutation()
{
    int i, partpos;
    for (i=0; i<gene_number ;i++)
    {
        if ((rand()%1000)/1000.0>mp)
            continue;
        partpos = rand()%gene_length;

        if (gene_n[i].gene[partpos]==1)
        {
            gene_n[i].gene[partpos]=0;
            gene_n[i].weight -= items[partpos].weight;
            gene_n[i].fit -= items[partpos].value;
        }
        else
        {
            // 如果背包不溢出，才进行操作，避免修补
            if (gene_n[i].weight+items[partpos].weight<bag_capacity)
            {
                gene_n[i].gene[partpos]=1;
                gene_n[i].weight += items[partpos].weight;
                gene_n[i].fit += items[partpos].value;
            }
        }
    }
}


//---------------------------------------------------------------------------
//在主界面输出基因（双亲本）
void printgene()
{
    AnsiString res;
    int i, j;

    for (i=0; i<gene_number ;i++)
    {
        res = "";
        for (j=0; j<gene_length ;j++)
            res += IntToStr(gene_p[i].gene[j]) + " ";

        res += "  总重量：" + IntToStr(gene_p[i].weight);
        res += "，总价值：" + IntToStr(gene_p[i].fit);
        textout (res);
    }
}


//---------------------------------------------------------------------------
// 遗传算法入口
void run_ga ()
{
    int i, j;
    int cnt = 0, res;

    textout ("- - - - - - - - - - - - - - - - - - - - - - - - -");
    textout ("遗传算法运行中，请稍候……");

    gene_initialize ();

    if (showprocess)
        printgene();

    while (cnt<gener_num)
    {
        cnt++;
        if (showprocess)
            textout ("正在演化，代数：" + IntToStr(cnt));

        crossover ();
        mutation ();
        updateall ();

        if (showprocess)
            printgene();
    }

    res = 0;
    for (i=0; i<gene_number; i++)
        if (res<gene_p[i].fit)
            res=gene_p[i].fit;

    textout ("运行完毕，运算结果：" + IntToStr(res));
    textout ("- - - - - - - - - - - - - - - - - - - - - - - - -");
    textout ("最终种群如下：");
    printgene();
    textout ("- - - - - - - - - - - - - - - - - - - - - - - - -");
    textout ("");
}