localsearch.cpp

遗传算法程序最新版

/***************************************************************
/* Single & Multi-Objective Real-Coded Genetic Algorithms Code */
/* Author: Kumara Sastry                                       */
/* Illinois Genetic Algorithms Laboratory (IlliGAL)            */
/* Deparment of General Engineering                            */
/* University of Illinois at Urbana-Champaign                  */
/* 104 S. Mathews Ave, Urbana, IL 61801                        */
/***************************************************************/

#include "localsearch.hpp"

LocalSearch::LocalSearch(){
maxLocalEvaluations = globalSetup->maxLocalEvaluations;
maxLocalTolerance = globalSetup->maxLocalTolerance;
}

Simplex::Simplex() 
{  
  noOfVariables = globalSetup->noOfDecisionVariables;
  simplexPoints = noOfVariables + 1;
  xSum = new double[noOfVariables];
  localGuys = new Individual*[simplexPoints];  
  for(int ii = 0; ii < simplexPoints; ii++) 
    localGuys[ii] = new Individual;
}

Simplex::~Simplex() 
{
  int ii;
  delete []xSum;
  for(ii = 0; ii < globalSetup->noOfDecisionVariables + 1; ii++)
    delete localGuys[ii];
  delete []localGuys;
}

/***
Nelder mead simplex search. For more details see Numerical Recipes in C
The number of decision variables for the local search (Nvl) equals the number of decision variables minus the number of frozen variables. The initial Nvl+1 individuals are generated as follows: One of the individuals is the individual provied by GA, the others are generated by mutating one of the unfrozen genes.
* Find the best, worst, and the next to worst individuals. 
* Reflect the worst individual along the centroid. 
* If the reflected individual is better than the best individual, then expand the reflected individual.
* If the reflected individual is worse than the next to worst individual, then contract the reflected individual.
* If the contracted point is worse than the worst individual then reflect along the best individual
* Repeat the above four steps till convergence is reached or the maximum number of allowed evaluations is exhausted.
This function returns the total number of function evaluations taken by the local search.
Reference: Press, W., Flannery, B., Teukolsky, S., & Vettering, W. (1989). Numerical Recipes in C. Cambridge: Cambridge University Press. http://lib-www.lanl.gov/numerical/bookcpdf/c10-4.pdf. (http://www.nr.com).
 */
int Simplex::localSearcher(Individual *theGuy, Individual *localHero, int *freezeMask)
{
  int ii, jj, numEvals = 0;
  double tolerance, nextOperation, value;
  Individual *trialGuy;
  localFreezeMask = freezeMask;

  trialGuy = new Individual;

  noOfVariables = globalSetup->noOfDecisionVariables;
  for(ii = 0; ii < globalSetup->noOfDecisionVariables; ii++)
    if(localFreezeMask[ii]) --noOfVariables;
  simplexPoints = noOfVariables + 1;
  
  *localGuys[0] = *theGuy;
  for(jj = 1, ii = 0; ii < globalSetup->noOfDecisionVariables; ii++) {
    *localGuys[jj] = *theGuy;
    if(localFreezeMask[ii] == OFF) {
      localGuys[jj]->mutate(ii);
      localGuys[jj++]->evaluateFitness();
    }
  }
  numEvals += noOfVariables; // Nv - Nf
  getSum();  

  for(;;) {

    findGoodBadUgly();

    tolerance = 2.0*fabs(localGuys[worst]->getObjective()-localGuys[best]->getObjective())/
      (fabs(localGuys[worst]->getObjective())+fabs(localGuys[best]->getObjective())+ZERO);
    if((tolerance < globalSetup->maxLocalTolerance) || 
       (numEvals > maxLocalEvaluations))
      { *localHero = *localGuys[best]; break; }

    numEvals += 2;
    nextOperation = simplexOperator(REFLECT, trialGuy);
    if(nextOperation == EXPAND)
      nextOperation = simplexOperator(EXPAND, trialGuy);
    else if(nextOperation == CONTRACT) {
      nextOperation = simplexOperator(CONTRACT, trialGuy);
      if(nextOperation == RECONSTRUCT) {
	for(ii = 0; ii < simplexPoints; ii++) {
	  if(ii != best) {
	    for(jj = 0; jj < globalSetup->noOfDecisionVariables; jj++) {
	      value = 0.5*((*localGuys[ii])[jj] + (*localGuys[best])[jj]);
	      if(globalSetup->variableTypes[jj] == Integer) value = int(value+0.5);
	      if(value > globalSetup->variableRanges[jj][1]) 
		value = globalSetup->variableRanges[jj][1];
	      else if(value < globalSetup->variableRanges[jj][0])
		value = globalSetup->variableRanges[jj][0];
	      localGuys[ii]->setValue(jj, value);
		}
	    localGuys[ii]->evaluateFitness();
	  }
	}
	numEvals += noOfVariables;
	getSum();
      }
    }
    else --numEvals;
  }
  delete trialGuy;
  return numEvals;
}

/***
Simplex operator: reflect, expands and contracts the worst individual. If the resultant individual is better than the earlier one than replaces the worst individual. Also returns the next operation to be done.
 */
double Simplex::simplexOperator(double thisOperation, Individual *trialGuy)
{
  int jj, kk;
  double fac1, fac2, nextOperation, value;
  
  fac1 = (1.0-thisOperation)/(1.0*noOfVariables);
  fac2 = fac1-thisOperation;

  for(kk = 0, jj = 0; jj < globalSetup->noOfDecisionVariables; jj++) {
    if(localFreezeMask[jj] == OFF) {
      value = xSum[kk++]*fac1 - (*localGuys[worst])[jj]*fac2;
	  if(globalSetup->variableTypes[jj] == Integer) value = int(value+0.5);
      if(value > globalSetup->variableRanges[jj][1]) 
	    value = globalSetup->variableRanges[jj][1];
      else if(value < globalSetup->variableRanges[jj][0])
	    value = globalSetup->variableRanges[jj][0];
      trialGuy->setValue(jj, value);
    }
    else {
      value = (*localGuys[worst])[jj];
      trialGuy->setValue(jj, value);
    }
  }
  trialGuy->evaluateFitness();

  if(isBetter(trialGuy, localGuys[best]))
    nextOperation = EXPAND;
  else if((isBetter(localGuys[nextWorst], trialGuy)) &&
	  (thisOperation != CONTRACT))
    nextOperation = CONTRACT;
  else if((!(isBetter(trialGuy, localGuys[worst]))) && 
	  (thisOperation == CONTRACT))
    nextOperation = RECONSTRUCT;
  if(isBetter(trialGuy, localGuys[worst])) 
    *localGuys[worst] = *trialGuy;
    
  return nextOperation;
}
      
/// Finds the best individual, worst individual and the next worst individual.
void Simplex::findGoodBadUgly()
{
  int ii;

  best = 0;

  if(isBetter(localGuys[0], localGuys[1])) { worst = 1; nextWorst = 0; }
  else { worst = 0; nextWorst = 1; }

  for(ii = 1; ii < simplexPoints; ii++) {
    if(isBetter(localGuys[ii], localGuys[best])) best = ii;
    if(!(isBetter(localGuys[ii], localGuys[worst]))) 
      { nextWorst = worst; worst = ii;}
    else if(!(isBetter(localGuys[ii], localGuys[nextWorst]))) 
      nextWorst = ii;
  }
}