eaxgenerator.java

用于求解TSP(Traveling salesman problem

/**
 * Description: The EAX generator with diffusion control.
 *
 * @ Author        Create/Modi     Note
 * Xiaofeng Xie    Apr 12, 2005
 * Xiaofeng Xie    Jun 29, 2005    From Dist->Cd-Dist
 * Xiaofeng Xie    Apr 28, 2006    MAOS-TSP Beta 1.1.002
 *
 * @version 1.0
 *
 * @ Reference:
 * [1] Yuichi Nagata. The EAX Algorithm Considering Diversity Loss. PPSN, 2004
 * -> For EAX
 * [2] X. F. Xie, J. Liu. How autonomy oriented computing (AOC) tackles a
 *  computationally hard optimization problem, International Joint Conference
 *  on Autonomous Agents & Multi Agent Systems (AAMAS), Future University-Hakodate,
 *  Japan, 2006
 *  -> For parameter Cd
 */

package implement.TSP.behavior.twoStageMove;

import Global.methods.*;

import Global.basic.data.collection.*;
import maosKernel.represent.*;
import maosKernel.behavior.generate.*;
import maosKernel.behavior.setInfo.*;
import maosKernel.knowledge.*;
import implement.TSP.represent.*;
import implement.TSP.behavior.repair.*;

public class EAXGenerator extends AbsSBILXGenerator implements ISetNNInfoEngine {
  public double Cd = 1.5;
  public int Nmtm = 30;
  public int nABCycle = 100;

  /**************************************************/
  private int[][] costMatrix;
  private INeighborEngine neighborEngine;

  /**************************************************/
  private ABCycleLib abCycleLib;
  private CyclesBridger cyclesManager;

  private DChainState aLinkPoint;
  private DChainState bLinkPoint;
  private DChainState kidDLinkPoint;
  /**************************************************/
  private DualIAlienArray activeCycleIDs;
//  private int[] selIDs;

  public void init(int nodeNumber) {
    abCycleLib = new ABCycleLib(nodeNumber);
    abCycleLib.setMaxSize(nABCycle);
    aLinkPoint = new DChainState(nodeNumber);
    bLinkPoint = new DChainState(nodeNumber);
    kidDLinkPoint = new DChainState(nodeNumber);
    activeCycleIDs = new DualIAlienArray(nABCycle+1);
//    selIDs = new int[nodeNumber];
  }

  public String getSpecialSummary() {
    String sumInfo = "";
    sumInfo += "Cd="+Cd+",";
    sumInfo += "Nmtm="+Nmtm+",";
    sumInfo += "nABCycle="+nABCycle;
    return sumInfo;
  }

  public void setInfo(AbsLandscape landscape) {
    costMatrix = ((GoodnessLandscape)landscape).getIGetProblemDataEngine().getCostMatrix();
    cyclesManager = new CyclesBridger(((GoodnessLandscape)landscape).getIGetProblemDataEngine());
    init(landscape.getSearchSpace().getNodeNumber());
  }

  public void setNeighborEngine(INeighborEngine neighborEngine) {
    this.neighborEngine = neighborEngine;
  }

  public boolean sbilXBehavior(EncodedState trailPoint, EncodedState basePoint, EncodedState referPoint) {
     aLinkPoint.importPoint(basePoint.getSearchState().getIArray());
    bLinkPoint.importPoint(referPoint.getSearchState().getIArray());

    abCycleLib.setABCycles(aLinkPoint, bLinkPoint);

    int size = abCycleLib.getSize();

    if (size==0) {
        return false;
    }
    findAllSets(size, Nmtm);

    boolean isWorked = false;
//    double bestEvalC = 0;
    double bestEvalC = Double.MAX_VALUE;
    double currEvalC;
    int lenA = basePoint.getBasicEncodeIData().getGlobalCost();

    int idSetSize = activeCycleIDs.getSize();
    int diffV = 0;
    int activeCycleID;
    for (int i=0; i<idSetSize; i++) {
      kidDLinkPoint.importPoint(aLinkPoint);
      activeCycleID = activeCycleIDs.getElementAt(i);
      changeSolForABCycle(activeCycleID);
      diffV = getCycleCostDifference(activeCycleID);
      diffV += cyclesManager.bridgeCycles(kidDLinkPoint, neighborEngine);

      currEvalC = diffV/(Math.pow(getDIS(activeCycleID), Cd));
      if (currEvalC<bestEvalC) {
        kidDLinkPoint.toBasicPoint(trailPoint.getSearchState().getIArray());
        trailPoint.getBasicEncodeIData().setIEncodeInfo(diffV+lenA);
        bestEvalC = currEvalC;
        isWorked = true;
      }
    }
    return isWorked;
  }

  //abCycle: the even edges are removed; and the odd edges are added
  //From a single cycle -> multi cycles
  private int r1,r2, j1,j2;
  public void changeSolForABCycle(int cycleID) {
    int[] abCycle = abCycleLib.getCycleData();
    int startID = abCycleLib.getCycleStartIndex(cycleID);
    int n_cycle = abCycleLib.getCycleSizeAt(cycleID);

    for(j1=0;j1<n_cycle/2;j1++) {
      j2 = 2*j1;
      r1=abCycle[1+j2+startID];r2=abCycle[(2+j2)%n_cycle+startID];

      kidDLinkPoint.changeChainCityIDAt(r1, r2, abCycle[  j2+startID]);
      kidDLinkPoint.changeChainCityIDAt(r2, r1, abCycle[(3+j2)%n_cycle+startID]);
    }
  }

  private int getCycleCostDifference(int cycleID) {
    int[] abCycle = abCycleLib.getCycleData();
    int startID = abCycleLib.getCycleStartIndex(cycleID);
    int n_cycle = abCycleLib.getCycleSizeAt(cycleID);

    int realID, diffV = 0;
    for (int i=0; i<n_cycle/2; i++) {
      realID = 2*i+startID;
      diffV += costMatrix[abCycle[realID]][abCycle[realID+1]];
      diffV -= costMatrix[abCycle[realID+1]][abCycle[(2*i+2)%n_cycle+startID]];
    }
    return diffV;
  }

  private void findAllSets(int cycleSize, int maxTimes) {
    activeCycleIDs.clear();
    for (int j = 0; j < maxTimes; j++) {
      activeCycleIDs.addElement(RandomGenerator.intRangeRandom(cycleSize));
    }
  }

  private int getDIS(int cycleID) {
    return abCycleLib.getCycleSizeAt(cycleID)/2;
  }
}