eval.c

moealib

#include "knapsack.h"


/*====================== initProblem() & evaluator  ============================*/


dVector* profitVector;         // array of profit vector
dVector* weightVector;         // array of weight vector
dVector  maxCapacityVector;    // total capacity vector
dVector  maxProfitVector;      // regardless of capacity constrain.

// sort items in ascending order by maxium profit/weight.
// used by greedy repairing of infeasible individuals.
int* order;


dVector usedCapacity(const IND& ind) {
  dVector used(ind.objectiveDimensions());
  for(int i=0; i<used.dimensions(); i++) 
    used[i] = 0;
  for(int i=0; i<ind.genes(); i++) 
    if(ind[i] == '1')
	used += weightVector[i];
  return used;
}


void mapByGreedyRepair(IND& ind) {
  int od = 0;
  while(!(usedCapacity(ind) <= maxCapacityVector)) {
    while(ind[order[od]] == '0' ) od++;
    ind[order[od]]  = '0';    // take away this item.
  }
}

void knapsackEvaluator(IND & ind, ObjectiveVector& scores) {
  IND Ind(ind);
  int sacks = scores.dimensions();
  int items = Ind.genes();
  //  assert(scores.dimensions()==sacks); assert(Ind.genes()==items);
  mapByGreedyRepair(Ind);
  for(int i=0; i<sacks; i++) scores[i] = 0;
  for(int i=0; i<items; i++) 
    if(Ind[i] == '1')
      scores += profitVector[i];
}



// read problem & sort items by their maximum profit/weight.
void initProblem(int items, int sacks) {

  profitVector = new dVector[items];
  weightVector = new dVector[items];
  for(int i=0; i<items; i++) {
    profitVector[i].dimensions(sacks);
    weightVector[i].dimensions(sacks);
  }
  maxCapacityVector.dimensions(sacks);
  maxProfitVector.dimensions(sacks);

  order = new int [items];

  char *filename;  ostrstream oss;
  oss << "../knapsack/problem/knapsack." << items << "." << sacks << ends;
  filename = oss.str();
  fstream fin(filename, ios::in);  assert(fin); delete filename;


  char s[50]; char c; int ii;       // tmp vars.

  for(int i=0; i<sacks; i++) {

    while(fin.get() != '=');
    fin >> s >> ii; 
    assert(strcmp(s,"knapsack")==0); assert(ii=i+1);
    fin.get(c); assert(c==':');
    fin >> s >> maxCapacityVector[i]; assert(strcmp(s, "capacity:")==0);

    for(int j=0; j<items; j++) {
      fin >> s;  assert(strcmp(s,"item")==0); 
      fin >> ii; assert(ii==j+1);
      fin >> c;  assert(c==':');
      fin >> s >> weightVector[j][i]; assert(strcmp(s,"weight:")==0);
      fin >> s >> profitVector[j][i]; assert(strcmp(s,"profit:")==0);
    }
  }

  for(int i=0; i<items; i++)
    maxProfitVector += profitVector[i];

  double* maxUnitProfit = new double[items];  // maxium profit/weight.
  double max, tmp;
  for(int i=0; i<items; i++) {
    max = profitVector[i][0] / weightVector[i][0];
    for(int j=1; j<sacks; j++) {
      tmp = profitVector[i][j] / weightVector[i][j];
      if(tmp > max ) max = tmp;
    }
    maxUnitProfit[i] = max;
  }

  //ranking the maxUnitProfits. rank 0 is the cheapest.
  int rank[items];
  memset(rank, 0, sizeof(int) * items);
  for(int i=0; i<items; i++) {
    for(int j=i+1; j<items; j++)
      if(maxUnitProfit[i] > maxUnitProfit[j])
	rank[i]++;
      else
	rank[j]++;
  }

  //sort items by their ranks.(ascending order)
  for(int i=0; i<items; i++) 
    order[rank[i]] = i;

#ifdef DEBUG
  cout << "\ncapacity vector is " << maxCapacityVector << endl;
  cout << "\nmax profit vector regardless of weight constraints is " << maxProfitVector << endl;
#ifdef VERBOSE
  cout << "\nweight vector and profit vector for sorted items are as follow:\n\n";
  for(int i=0; i<items; i++) {
    int item = order[i];
    cout << "item " << setw(4) << item+1 << ":\t";
    cout << weightVector[item] << '\t' << profitVector[item] << endl;
  }
#endif
#endif
}