firstimprovebitswaper.java

pso源程序

/**
 * Description: The description of first improvement search schedule.
 *
 * @ Author        Create/Modi     Note
 * Xiaofeng Xie    Oct 06, 2006
 *
 * @version 1.0
 *
 * @Reference
 * [1] T. St黷zle, "An ant approach to the flow shop problem," European
 * Congress on Intelligent Techniques and Soft Computing, Aachen, Germany,
 * pp. 1560-1564, 1998.
 */

package maosKernel.behavior.greedy;

import java.util.*;
import Global.basic.nodes.utilities.*;
import Global.methods.*;

import maosKernel.represent.space.*;
import maosKernel.behavior.mutate.*;
import maosKernel.represent.landscape.*;
import maosKernel.memory.*;

public class FirstImproveBitSwaper extends AbsSystematicChanger {
  public int improveTimes = Integer.MAX_VALUE;
  private boolean[] bitFlags;

  public FirstImproveBitSwaper() {
  }

  protected void setRootInfo(AbsLandscape landscape) {
    int nodeNumber = landscape.getSearchSpace().getNodeNumber();
    super.init(nodeNumber);
    bitFlags = new boolean[nodeNumber];
  }

  public void initUtilities() {
    super.initUtilities();
    initUtility(new IntegerUtility("improveTimes", improveTimes));
  }

  public void shortcutInit() throws Exception {
    super.shortcutInit();
    improveTimes = TypeConverter.toInteger(getValue("improveTimes"));
  }

  // 2-change systematic search, return delta_Cost
  public int systematicSearch(SearchState state, ILocalChangeEngine localChangeEngine){
    int nodeA, nodeB;
    boolean isImproved = true;
    int totalDelta = 0;
    int nodeNumber = state.getNodeNumber();

    int[] randArrayA, randArrayB;
    localChangeEngine.setState(state);
    int i, j, k;
    int times, delta, minDelta, minNodeB=-1;

    Arrays.fill(bitFlags, false);
    while (isImproved) {
      isImproved = false;
      randArrayA = getRandomOrderArray();
      for (j = 0; j < nodeNumber; j ++) {
        if (isImproved) break;
        nodeA = randArrayA[j];
        if (bitFlags[nodeA]) continue;
        localChangeEngine.setBaseNodeID(nodeA);
        randArrayB = getRandomOrderArray();
        times = 0;
        minDelta = 0;
        for (k = 0; k < nodeNumber; k++) {
          nodeB = randArrayB[k];
//          if (bitFlags[nodeB]) continue;
          if (nodeA==nodeB) continue;
          delta = localChangeEngine.getDeltaCost(nodeB);
          if (delta < minDelta) {
            minDelta = delta;
            minNodeB = nodeB;
            times++;
            if (times>=improveTimes) {
              break;
            }
          }
        }
        if (minDelta<0) {
          totalDelta += minDelta; localChangeEngine.changeBehavior(minNodeB); isImproved = true;
          //reactive nn changed bits
          if (nodeA<minNodeB) {
            if (minNodeB-nodeA-2>0) System.arraycopy(bitFlags, nodeA+2, bitFlags, nodeA+1, minNodeB-nodeA-2);
            if (nodeA>0) bitFlags[nodeA-1]=false;
            bitFlags[nodeA] = false;
            bitFlags[minNodeB-1] = false;
            bitFlags[minNodeB] = false;
            if (minNodeB<nodeNumber-1) bitFlags[minNodeB+1] = false;
          } else {
            if (nodeA-minNodeB-2>0) System.arraycopy(bitFlags, minNodeB+1, bitFlags, minNodeB+2, nodeA-minNodeB-2);
            bitFlags[nodeA-1]=false;
            bitFlags[nodeA] = false;
            if (nodeA<nodeNumber-1) bitFlags[nodeA+1] = false;
            if (minNodeB>0) bitFlags[minNodeB-1] = false;
            bitFlags[minNodeB] = false;
          }
        } else {
          bitFlags[nodeA] = true;
        }
      }
    }
    return totalDelta;
  }
}