Optimization with Simulated Annealing

Listing 3: Partial listing of TimeShareSolver.cpp

STDMETHODIMP CTimeShareSolver::Solve()
{
   //
   // Read the database.
   ReadOwnerInfo();
   //
   // Initialization.
   Initialize();
   //
   // Main loop.
   for (m_iterCnt =0;m_iterCnt<MAX_ITERATIONS;m_iterCnt++)
   {
      AssignOwners();
      SwapOwners();
      EvaluateCost();
      UnassignOwners();
   }
   //
   // Update the database.
   WriteBestSolution();
   return S_OK;
}

CTimeShareSolver::Initialize()
{
   //
   // Initialize all owners to unassigned.
   m_trialCostTotal = 0;
   for (int i = 0;i<m_ownerCnt;i++)
   {
      int cost = m_owner[i].CalcCost(UNASSIGNED);
      m_trial[i] = UNASSIGNED;
      m_curr[i] = UNASSIGNED;
      m_best[i] = UNASSIGNED;
      m_trialCost[i] = cost;
      m_trialCostTotal += cost;
   }
   //
   //  Initially the trial = curr = best soln.
   m_currCostTotal = m_trialCostTotal;
   m_bestCostTotal = m_trialCostTotal;
   //
   //  Initialize capacity data.
   for (int p =0;p < MAX_PERIODS;p++)
   {
      m_unitsOccup [p] = 0;
      m_totalOccup [p] = 0;
   }
   m_iterCnt = 0;
   srand(1); // Init random number generator.
}

CTimeShareSolver::AssignOwners()
{
   vector <bool> tryToAssign ( m_ownerCnt, false);
   int tryToAssignCnt = 0;
   for (int i=0;i<m_ownerCnt;i++)
   {
      if (m_trial[i] == UNASSIGNED)
      {
         tryToAssign[i] = true;
         tryToAssignCnt++;
      }
   }
   while (tryToAssignCnt > 0)
   {
      // Select one of the unassigned owners
      // with most occupants.
      RandomMax hiOcc;
      hiOcc.Initialize( 4);
      for (i=0;i<m_ownerCnt;i++)
      {
         if (tryToAssign[i])
            hiOcc.Compare(i, m_owner[i].m_occupCnt);
      }
      i = hiOcc.RandomSelectIndex();
      //
      //  Try to get one of the owner's first 3 choices.
      int choice = 0;
      while ((choice < 3)&&(m_trial[i] == UNASSIGNED))
      {
         int period = m_owner[i].m_choice[choice];
         if (m_unitsOccup[period] < MAX_UNITS)
         {
            int trialOcc = m_totalOccup[period];
            trialOcc +=  m_owner[i].m_occupCnt;
            if (trialOcc <= MAX_OCCUPANTS)
               Assign( i, period);
         }
         choice++;
      }
      //
      //  If owner is still unassigned. Try assigning him to
      //  the open period with the most occupants.
      if (m_trial[i] == UNASSIGNED)
      {
         int bestPeriod = -1;
         int maxOcc = -1;
         for (int period=0;period<MAX_PERIODS;period++)
         {
            if (m_unitsOccup[period] < MAX_UNITS)
            {
               int trialOcc = m_totalOccup[period];
               trialOcc += m_owner[i].m_occupCnt;
               if ((trialOcc <= MAX_OCCUPANTS)
                 &&(trialOcc > maxOcc))
               {
                  bestPeriod = period;
                  maxOcc = trialOcc;
               }
            }
         }
         if (bestPeriod != -1)
            Assign( i, bestPeriod);
      }
      tryToAssign[i] = false;
      tryToAssignCnt--;
   }
}

CTimeShareSolver::SwapOwners()
{
   vector <bool> tryToSwap ( m_ownerCnt, false);
   int tryToSwapCnt = 0;
   for (int i=0;i<m_ownerCnt;i++)
   {
      if (m_trialCost[i] > 0)
      {
         tryToSwap[i] = true;
         tryToSwapCnt++;
      }
   }
   while (tryToSwapCnt > 0)
   {
      RandomMax hiCost;
      hiCost.Initialize( 3);
      for (i=0;i<m_ownerCnt;i++)
      {
         // Select one of the unassigned owners
         // with highest cost.
         if (tryToSwap[i])
            hiCost.Compare(i, m_trialCost[i]);
      }
      i = hiCost.RandomSelectIndex();
      //
      //  We make swaps by unassigning first.
      //  Then reassign to someone else's spot.
      //  or back to the original spot.
      if (m_trial[i] != UNASSIGNED)
         Unassign( i);
      Swap(i);
      tryToSwap[i] = false;
      tryToSwapCnt--;
   }
}

CTimeShareSolver::UnassignOwners()
{
   int assignCnt  = 0;
   for (int i = 0;i<m_ownerCnt;i++)
   {
      if (m_trial[i] != UNASSIGNED)
         assignCnt++;
   }
   //
   // Unassign 15% of highest cost assignments.
   int unassignTarget = 15*assignCnt/100;
   while (unassignTarget > 0)
   {
      // Select one of the unassigned owners
      // with highest cost.
      RandomMax hiCost;
      hiCost.Initialize( 4);
      for (i=0;i<m_ownerCnt;i++)
      {
         if (m_trial[i] != UNASSIGNED)
            hiCost.Compare(i, m_trialCost[i]);
      }
      i = hiCost.RandomSelectIndex();
      if (m_trial[i] != UNASSIGNED)
      {
         Unassign(i);
         unassignTarget--;
      }
   }

   //
   // Remove an additional 5% at random.
   unassignTarget = 5*assignCnt/100;
   while (unassignTarget > 0)
   {
      int i=randomNum(m_ownerCnt);
      if (m_trial[i] != UNASSIGNED)
      {
         Unassign(i);
         unassignTarget--;
      }
   }
}



CTimeShareSolver::EvaluateCost()
{
   //
   //  First adjust the simulated annealing temperature;
   if (m_iterCnt== 0)
      m_saTemp = 0.05*m_trialCostTotal + 1.0;// initialize
   else if ((m_iterCnt % (MAX_ITERATIONS/20)) == 0)
      m_saTemp = 0.90*m_saTemp; // make 20 reductions of 10%
   //
   // First check for new best solution.
   if (m_trialCostTotal < m_bestCostTotal)
   {
      // A new best solution was found.
      // Copy trial solution to best solution.
      for (int i =0;i < m_ownerCnt;i++)
         m_best[i] = m_trial[i];
      m_bestCostTotal = m_trialCostTotal;
      //
      //  Copy trial solution to current solution.
      for (i =0;i < m_ownerCnt;i++)
         m_curr[i] = m_trial[i];
      m_currCostTotal = m_trialCostTotal;

      char buff[400];
      sprintf( buff, "Iteration %d NEW BEST SOLUTION = %d\n",
         m_iterCnt, m_bestCostTotal);
      OutputDebugString(buff);

   }
   else
   {
      double delta = m_currCostTotal - m_trialCostTotal;
      double anneal = exp(delta/m_saTemp);
      double randVal = randomNum(1000)/1000.0;
      if (randVal < anneal)
      {
         //
         //  Keep the trial solution.
         for (int i =0;i < m_ownerCnt;i++)
            m_curr[i] = m_trial[i];
         m_currCostTotal = m_trialCostTotal;
      }
      else
      {
         //
         // Discard trial soln. Go back to curr soln.
         for (int p =0;p < MAX_PERIODS;p++)
         {
            m_unitsOccup [p] = 0;
            m_totalOccup [p] = 0;
         }
         for (int i =0;i < m_ownerCnt;i++)
         {
            int p = m_curr[i];
            m_trial[i] = p;
            m_trialCost[i] = m_owner[i].CalcCost(p);
            if (p != UNASSIGNED)
            {
               m_unitsOccup[p]++;
               m_totalOccup[p] += m_owner[i].m_occupCnt;
            }
         }
         m_trialCostTotal = m_currCostTotal;
      }
   }
}
— End of Listing —