realmaosinitializer.java

用于求解TSP(Traveling salesman problem

/**
 * Description: The intialization engine.
 *
 * @ Author        Create/Modi     Note
 * Xiaofeng Xie    Apr 28, 2006
 * Xiaofeng Xie    Jul 12, 2006
 *
 * @version 1.0
 * @Since MAOS_TSP1.0
 *
 */
package implement.TSP;

import Global.system.io.*;
import Global.define.*;
import Global.basic.data.matrix.*;

import maosKernel.*;
import maosKernel.infoIO.*;
import maosKernel.represent.*;
import maosKernel.represent.encode.*;
import maosKernel.represent.encode.iEncode.*;
import maosKernel.behavior.generate.*;
import maosKernel.behavior.construct.*;
import maosKernel.knowledge.*;
import maosKernel.behavior.*;
import maosKernel.behavior.setInfo.*;
import implement.TSP.infoIO.*;
import implement.TSP.represent.*;
import implement.TSP.knowledge.*;
import implement.TSP.behavior.construct.*;
import implement.TSP.behavior.twoStageMove.*;
import implement.TSP.behavior.mutate.*;

public class RealMAOSInitializer extends AbsMAOSInitializer {

  //intermediate knowledge
  private INeighborEngine neighborEngine;
  private OEncodeData lowerBoundData = null;

  public RealMAOSInitializer() {
    this(new FullParamHolder(), new RealProblemIOHandler());
  }

  public RealMAOSInitializer(BasicParamHolder paramHolder, AbsProblemIOHandler ioHandler) {
    super(paramHolder, ioHandler);
  }

  private FullParamHolder getRealParamHolder() {
    return (FullParamHolder)super.getParamHolder();
  }

  protected void initBehavior(AbsBehavior behavior, AbsLandscape virtualLandscape) {
    if (behavior instanceof ISetNNInfoEngine) {
      ((ISetNNInfoEngine)behavior).setNeighborEngine(neighborEngine);
    }
    super.initBehavior(behavior, virtualLandscape);
  }

  protected AbsConstructor initMemInitializer() throws Exception {
    return new Basic3OptConstructor();
  }

  //init kernal generator, can be replaced by other AbsGenerator
  protected AbsGenerator initKernalGenerator() throws Exception {
    FullParamHolder paramHolder = getRealParamHolder();
    EAXGenerator generator = new EAXGenerator();
    generator.Cd = paramHolder.EAXCd;
    generator.Nmtm = paramHolder.EAXNmtm;
    return generator;
  }

  protected AbsLandscape initLandscape(AbsProblemData absProblemData) throws Exception {
    return new GoodnessLandscape((RealProblemData)absProblemData);
  }

  public void initIntermediateKnowledge(AbsLandscape virtualLandscape) throws Exception {
    Basic3OPT.bit_Ratio = getRealParamHolder().rBit3Opt;
    System.out.println("->Prepare intermediate knowledge: neighborhood info");
    String piFileName = paramHolder.getSpecProjectPath()+BasicTag.FILE_SEP_TAG+"PI_FILES"+BasicTag.FILE_SEP_TAG+paramHolder.problemName+".pi";
    ISquareIMatrixEngine transCostMatrix = this.getCostMatrix(new FullSquareIMatrix(((GoodnessLandscape)virtualLandscape).getIGetProblemDataEngine().getCostMatrix()), piFileName);
    neighborEngine = new BasicNeighborManager(transCostMatrix, getRealParamHolder().Knni);
  }

  public OEncodeData getLowerBound() {
    return lowerBoundData;
  }

  //1. init candidate set: if PI_FILES exists, then in alpha-nearness measure, else in nearest neighbor
  //2. estimate Held-Karp bound
  private ISquareIMatrixEngine getCostMatrix(ISquareIMatrixEngine costMatrix, String piFileName) throws Exception {
    ISquareIMatrixEngine transCostMatrix = costMatrix;
    PenaltyHandler piHandler = new PenaltyHandler(costMatrix);
    boolean isAlpha = getRealParamHolder().isAlpha;
    System.out.print("@Penalty values: ");
    try {
      String content = GlobalFile.getStringFromFile(piFileName);
      double[] piArray = LKH_PI_Reader.readResult(content);
      piHandler.initPIArray(piArray, LKH_PI_Reader.precision);
      System.out.println("read from setting file: "+piFileName);
    } catch (Exception e) {
      //must be accelerated for large instance
      if (costMatrix.getNodeNumber()<getRealParamHolder().Nalpha) {
        //calculate the Pi array and save it
        System.out.println("calculated in runtime");
        piHandler.ascentPiArray();
        String content = LKH_PI_Reader.writeResult(piHandler.getPIArray());
        GlobalFile.saveStringToFile(content, piFileName);
      } else {
        System.out.println("not calculated for N>Nalpha");
        isAlpha = false;
      }
    }
    if (isAlpha) {
      lowerBoundData = new OEncodeIData((int)Math.ceil(piHandler.getPublicW()));
//      System.out.println("@Held-Karp bound: "+lowerBoundData.writeInfo());
      transCostMatrix = piHandler.getAlphaMatrix();
    }
    return transCostMatrix;
  }
}