遗传算法_01背包问题v1.0

#include "iostream.h"
#include "iomanip.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"

//定义问题的最大规模
#define max 100
//问题规模，即共有多少个包
int packageNum;
//每个包的重量
int packageWeight[max];
//每个包的价值
int packageValue[max];
//约束，背包的最大容量
int limitWeight;

//群体的规模
int colonySize;
//colonyState[i][k] 表示一个染色体
//colonyState[1...colonySize][ 0|1 ] 表示一代群体
int colonyState[max][2][max];

// currAge 表示当前代的编号
// (currAge+1)%2 表示下一代的编号
int currAge = 0;

//个体评价信息表
typedef struct tagIndividualMsg
{
 int index;
 int value;
} IndividualMsg;
IndividualMsg individualMsg[max];

// 函数声明
void printColonyState( int nextAge );

//初始化群体
void colonyInit()
{
 int i , j;
 int w;
 for( i = 0 ; i < colonySize ; i++ )
 {
  //保证找到一个符合约束的染色体
  w = limitWeight + 1;
  while( w > limitWeight )
  {
   w = 0;
   for( j = 0 ; j < packageNum && w <= limitWeight ; j++ )
   {
    colonyState[i][currAge][j] = rand() % 2;
    w += packageWeight[j] * colonyState[i][currAge][j];
   }
  }
 }
}

//对个体进行评价
int cmp( const void *a , const void *b )
{
 IndividualMsg *x = (IndividualMsg *)a;
 IndividualMsg *y = (IndividualMsg *)b;
 return y->value - x->value;
}
void individualEstimate()
{
 int i , j;
 for( i = 0 ; i < colonySize ; i++ )
 {
  individualMsg[i].index = i;
  individualMsg[i].value = 0;
  for( j = 0 ; j < packageNum ; j++ )
   individualMsg[i].value += packageValue[j] * colonyState[i][currAge][j];
 }
 qsort( individualMsg , colonySize , sizeof(IndividualMsg) , cmp );
}

//终止循环的条件
bool stopFlag()
{
 //进行 n 代进行后停止
 static int n = 50;
 if( n-- <= 0 )
  return true;
 else
  return false;
}

//赌轮选择
int gambleChoose()
{
 int wheel[max] = { 0 };
 int i = colonySize - 1;
 int choose;
 wheel[i] = individualMsg[i].value;
 for( i-- ; i >= 0 ; i-- )
  wheel[i] = ( individualMsg[i].value + wheel[i+1] ) + colonySize * ( colonySize - i );
 int seed = abs( wheel[0] - ( rand() % ( 2 * wheel[0] ) + 1 ) );
 choose = colonySize - 1;
 while( seed > wheel[choose] )
  choose--;

// cout<<"----------------------------------------"<<endl;
// cout<<"wheel :"<<endl;
// for( i = 0 ; i < colonySize ; i++ )
//  cout<<setw(5)<<wheel[i];
// cout<<endl;
// cout<<"seed = "<<seed<<endl;
// cout<<"choose "<<choose<<endl;

 return choose;
}

//交叉
void across( int male , int female , int index )
{
 int nextAge = (currAge+1)%2;
 int i , j , t;
 int acrossBit = rand() % (packageNum-1) + 1;
 for( j = 0 ; j < packageNum ; j++ )
 {
  colonyState[index][nextAge][j] = colonyState[individualMsg[male].index][currAge][j];
  colonyState[index+1][nextAge][j] = colonyState[individualMsg[female].index][currAge][j];
 }
 for( i = 0 ; i < acrossBit ; i++ )
 {
  t = colonyState[index][nextAge][i];
  colonyState[index][nextAge][i] = colonyState[index+1][nextAge][i];
  colonyState[index+1][nextAge][j] = t;
 }
}
//变异
void aberrance( int index )
{
 int seed , nextAge;
 nextAge = (currAge+1)%2;
 //只有 1/3 的概率发生异变
 seed = rand() % ( packageNum * 3 );
 if( seed < packageNum )
  colonyState[index][nextAge][seed] = ( colonyState[index][nextAge][seed] + 1 ) % 2;
}
//处理 死亡个体
void dealDeath()
{
 int i , j;
 int weight , w;
 int nextAge = (currAge+1)%2;
 for( i = 0 ; i < colonySize ; i++ )
 {
  weight = 0;
  for( j = 0 ; j < packageNum ; j++ )
   weight += packageWeight[j] * colonyState[i][nextAge][j];
  if( weight > limitWeight )
  {
   //随机生成新的个体
   w = limitWeight + 1;
   while( w > limitWeight )
   {
    w = 0;
    for( j = 0 ; j < packageNum && w <= limitWeight ; j++ )
    {
     colonyState[i][nextAge][j] = rand() % 2;
     w += packageWeight[j] * colonyState[i][nextAge][j];
    }
   }
  }
 }
 printColonyState( nextAge );
}
//最优个体保护
void saveBest()
{
 int i , j;
 int min , minp , value;
 int nextAge = ( currAge+1)%2;
 min = individualMsg[0].value;
 minp = -1;
 for( i = 0 ; i < colonySize ; i++ )
 {
  value = 0;
  for( j = 0 ; j < packageNum ; j++ )
   value += packageValue[j] * colonyState[i][nextAge][j];
  if( value <= min )
  {
   min = value;
   minp = i;
  }
 }
 if( minp >= 0 )
 {
  for( j = 0 ; j < packageNum ; j++ )
  {
   colonyState[minp][nextAge][j] = colonyState[individualMsg[0].index][currAge][j];
  }
 }
}

void setProblem()
{
 int i;

 packageNum = 5;
 int w[] = { 5 , 4 , 3 , 2 , 1 };
 int v[] = { 8 , 9 , 3 , 1 , 2 };
 for( i = 0 ; i < packageNum ; i++ )
 {
  packageWeight[i] = w[i];
  packageValue[i] = v[i];
 }
 limitWeight = 13;
 colonySize = 5;

}
void printProblem()
{
 int i;
 cout<<"----------------------------------------"<<endl;
 cout<<"problem state:"<<endl;
 cout<<"packageNum = "<<packageNum<<endl;
 cout<<"limitWeight = "<<limitWeight<<endl;
 cout<<"Weight: ";
 for( i = 0 ; i < packageNum ; i++ )
  cout<<setw(3)<<packageWeight[i];
 cout<<endl;
 cout<<"Value:  ";
 for( i = 0 ; i < packageNum ; i++ )
  cout<<setw(3)<<packageValue[i];
 cout<<endl;
}
void printColonyState( int k )
{
 cout<<"----------------------------------------"<<endl;
 cout<<"colonyState-->";
 if( k == currAge )
  cout<<"currAge:"<<endl;
 else
  cout<<"next age:"<<endl;
 int i , j;
 for( i = 0 ; i < colonySize ; i++ )
 {
  for( j = 0 ; j < packageNum ; j++ )
   cout<<setw(2)<<colonyState[i][k][j];
  cout<<endl;
 }
}
void printIndividualMsg()
{
 int i;
 cout<<"----------------------------------------"<<endl;
 cout<<"Individual Msg:"<<endl;
 for( i = 0 ; i < colonySize ; i++ )
 {
  cout<<individualMsg[i].index<<"/t"<<individualMsg[i].value<<endl;
 }
}

void main()
{
 srand( (unsigned int)time(NULL) );
 setProblem();
 printProblem();

 //初始群体
 colonyInit();
 printColonyState( currAge );
 
 while( !stopFlag() )
 {
  //评价当前群体
  individualEstimate();
  //生成下一代
  for( int i = 0 ; i < colonySize ; i += 2 )
  {
   int male = gambleChoose();
   int female = gambleChoose();
   across( male , female , i );
   aberrance( i );
   aberrance( i + 1 );
  }
  //处理 死亡 个体
  dealDeath();
  //最优个体保护
  saveBest();
  //现在的下一代变成下一轮的当前代
  currAge = ( currAge + 1 ) % 2;
  //printColonyState( currAge );
 }

 //输出问题解
 individualEstimate();
 cout<<"近似解:"<<endl;
 int j , w = 0;
 cout<<setw(10)<<"Value:";
 for( j = 0 ; j < packageNum ; j++ )
  cout<<setw(5)<<packageValue[j];
 cout<<endl;
 cout<<setw(10)<<"Weight:";
 for( j = 0 ; j < packageNum ; j++ )
 {
  w += packageWeight[j] * colonyState[individualMsg[0].index][currAge][j];
  cout<<setw(5)<<packageWeight[j];
 }
 cout<<endl;
 cout<<setw(10)<<"Choose:";
 for( j = 0 ; j < packageNum ; j++ )
  cout<<setw(5)<<colonyState[individualMsg[0].index][currAge][j];
 cout<<endl;
 cout<<"limitWeight: "<<limitWeight<<endl;
 cout<<"总重量:      "<<w<<endl;
 cout<<"总价值:      "<<individualMsg[0].value<<endl;
}