penaltyhandler.java

用于求解TSP(Traveling salesman problem

/**
 * Description: attempts to find penalties (pi-values).
 *
 * @ Author        Create/Modi     Note
 * Xiaofeng Xie    May 22, 2005
 * Xiaofeng Xie    Apr 28, 2006    MAOS-TSP Beta 1.1.002
 *
 * @ Reference:
 * [1] K. Helsgaun,"An Effective Implementation of the Lin-Kernighan Traveling
 *  Salesman Heuristic", European J Operational Research 126 (1), 106-130 (2000).
 * [2] See HLK 1.3 code
 */

package implement.TSP.knowledge;

import Global.basic.data.*;
import Global.basic.data.matrix.*;
import maosKernel.knowledge.*;

public class PenaltyHandler {
  private PiCostMatrix piCostMatrix;

  //****************************
  private double[] basePIArray;
  private double[] bestPiArray;
  private int[] currDegree;
  private int[] lastDegree;
  private SpanningTree spanningTree;
  private AlphaMatrixManager alphaMatrixManager;
  private Minimum1TreeHandler min1TreeHandler;
  //****************************

  public PenaltyHandler(ISquareIMatrixEngine costMatrix) {
    int nodeNumber = costMatrix.getNodeNumber();
    basePIArray = new double[nodeNumber];
    bestPiArray = new double[nodeNumber];
    currDegree = new int[nodeNumber];
    lastDegree = new int[nodeNumber];
    spanningTree = new SpanningTree(nodeNumber);
    piCostMatrix = new PiCostMatrix(costMatrix);
    alphaMatrixManager = new AlphaMatrixManager(nodeNumber);
    min1TreeHandler = new Minimum1TreeHandler(nodeNumber);
  }

  public void initPIArray(double[] extPIArray, int precision) {
    System.arraycopy(extPIArray, 0, this.basePIArray, 0, this.getNodeNumber());
    piCostMatrix.setPrecision(precision);
    piCostMatrix.setPIArray(basePIArray);
  }

  public ISquareIMatrixEngine getCostMatrix() {
    return piCostMatrix.getCostMatrix();
  }

  public int getPenaltyValue() {
    return piCostMatrix.getPenaltyValue();
  }

  public FullSquareIMatrix getAlphaMatrix() {
    alphaMatrixManager.toAlphaMatrix(spanningTree, piCostMatrix);
    return alphaMatrixManager.getAlphaMatrix();
  }

  private void get1TreeDegree(int[] degrees) {
    int nodeNumber = spanningTree.getNodeNumber();
    for (int i = 0; i < nodeNumber; i++) {
      degrees[i] =  spanningTree.getNodeAt(i).getDegree();
    }
    BasicEdge basicEdge = min1TreeHandler.getMax1TreeEdge();
    degrees[basicEdge.startIndex] ++;
    degrees[basicEdge.endIndex] ++;
  }

  /*
   The getPublicW function returns the cost of a minimum 1-tree.

   The minimum 1-tree is found by determining the minimum spanning tree and
   then adding an edge corresponding to the second nearest neighbor of one
   of the leaves of the tree (any node which has degree 1). The leaf chosen
   is the one that has the longest second nearest neighbor distance.
  */
  public double getPublicW() {
    adjustMinimum1TreeHandler();
    return getPrivateW()/(double)piCostMatrix.getPrecision();
  }

  private int getPrivateW() {
    return spanningTree.getTotalCost(piCostMatrix)
           + min1TreeHandler.getMax1TreeEdgeCost()
           - piCostMatrix.getPenaltyValue();
  }

  private void adjustMinimum1TreeHandler() {
    spanningTree.clear();
    MinimumSpanningTreeSolver.prim_mst(spanningTree, piCostMatrix);
    min1TreeHandler.initMinimum1Tree(spanningTree, piCostMatrix);
  }

  private void adjustMinimum1TreeHandler(AbsNeighborManager neighborManager) {
    spanningTree.clear();
    MinimumSpanningTreeSolver.prim_mst(spanningTree, piCostMatrix, neighborManager);
    min1TreeHandler.initMinimum1Tree(spanningTree, piCostMatrix);
  }

  public int getNodeNumber() {
    return basePIArray.length;
  }

  public double[] getPIArray() {
    return basePIArray;
  }

  /*
     The Ascent function computes a lower bound on the optimal tour length using
     subgradient optimization. The function also transforms the original problem
     into a problem in which the alpha-values reflect the likelihood of edges being
     optimal.

     The function attempts to find penalties (pi-values) that maximizes the lower
     bound L(T(Pi)) - 2*PiSum, where L(T(Pi)) denotes the length of the minimum
     spanning 1-tree computed from the transformed distances, and PiSum denotes the
     sum of pi-values. If C(i,j) denotes the length of and edge (i,j) then the
     transformed distance D(i,j) of an edge is C(i,j) + Pi(i) + Pi(j).
  */

 public void ascentPiArray() {
   int nodeNumber = this.getNodeNumber();
   int W;
   int Period = 0, P = 0;
   int InitialPeriod = nodeNumber/2;
   if (InitialPeriod < 100) InitialPeriod = 100;

   double T = 1.0;
   double precisionT = 0.01;
   piCostMatrix.setPIArray(basePIArray);
   this.adjustMinimum1TreeHandler();
   get1TreeDegree(lastDegree);
   int BestW = getPrivateW();

   BasicNeighborManager neighborManager = new BasicNeighborManager(getAlphaMatrix(), 50);

   /* Perform subgradient optimization with decreasing period length and decreasing step size */
   boolean InitialPhase = true;
   for (Period = InitialPeriod; Period > 0 && T > precisionT; Period /= 2, T /= 2) {      /* Period and step size are halved at each iteration */
     for (P = 1; T>precisionT && P <= Period; P++) {
       /* Adjust the Pi-values */
       get1TreeDegree(currDegree);
       for (int i=0; i<nodeNumber; i++) {
         if (currDegree[i]!=2) {
           basePIArray[i] += T * (7 * (currDegree[i]-2) + 3 * (lastDegree[i]-2)) / 10;
         }
       }
       System.arraycopy(currDegree, 0, lastDegree, 0, nodeNumber);
       piCostMatrix.setPIArray(basePIArray);
       /* Compute a minimum 1-tree in the sparse graph */
       this.adjustMinimum1TreeHandler(neighborManager); //??? should use sparse mode in future
       W = getPrivateW();
       if (W > BestW) {
         BestW = W;
         /* Update the BestPi-values */
         System.arraycopy(basePIArray, 0, bestPiArray, 0, nodeNumber);
         /* If in the initial phase, the step size is intd */
         if (InitialPhase) T *= 2;
         /* If the improvement was found at the last iteration of the current
            period, then int the period */
         if (P == Period && (Period *= 2) > InitialPeriod)
             Period = InitialPeriod;
       } else if (InitialPhase && P > Period / 2) {
         /* Conclude the initial phase */
         InitialPhase = false;
         P = 0;
         T = 3 * T / 4;
       }
     }
   }
   /* Save the Pi-values */
   System.arraycopy(bestPiArray, 0, basePIArray, 0, nodeNumber);
 }
}