localdominaterefiner.java

pso源程序

/**
 * Description:
 *
 * @ Author        Create/Modi     Note
 * Xiaofeng Xie    Feb 17, 2006
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * Please acknowledge the author(s) if you use this code in any way.
 *
 * @References:
 * [1] J E Beasley, P.C.Chu. A genetic algorithm for the multidimensional
 *  knapsack problem, Journal of Heuristics, vol. 4, 1998, pp63-86.
 * [2] B A Julstrom, Greedy, genetic, and greedy genetic algorithm for the
 *  quadratic knapsack problem, GECCO 2005: 607-614
 * [3] Xiao-Feng Xie, Jiming Liu. A mini-swarm for the quadratic knapsack
 *     problem. IEEE Swarm Intelligence Symposium (SIS), Hawaii, USA, 2007.
 */

package implement.QKP.behavior.refine;

import Global.basic.data.collection.*;
import Global.methods.*;

import maosKernel.represent.landscape.*;
import maosKernel.represent.space.*;
import implement.QKP.represent.*;
import implement.common.behavior.refine.*;
import implement.QKP.knowledge.*;
import Global.basic.nodes.utilities.*;

public class LocalDominateRefiner extends AbsLocalRefiner {
  private int maxExtSize = Integer.MAX_VALUE;
  private int nTour = 2;
  public boolean isRelative = false; //dynamic density values

  private QKPKnowledge qkpKnowledge;
  protected IGetProblemDataEngine problemData = null;

  private IArray idsArray;

  private int[] weightOrderArray;
  private IArray segmentIDArray;
  private IArray segmentWVArray;
  private double[] densityArray;
  private int[] tourSelIDArray;

  public LocalDominateRefiner() {}

  public void setRootInfo(AbsLandscape landscape) {
    GoodnessLandscape virtualLandscape = (GoodnessLandscape)landscape;
    int nodeNumber = virtualLandscape.getSearchSpace().getNodeNumber();
    tourSelIDArray = new int[nodeNumber];
    idsArray = new IArray(nodeNumber);
    problemData = virtualLandscape.getIGetProblemDataEngine();
    qkpKnowledge = new QKPKnowledge(problemData);
    initOrderArray(virtualLandscape.getIGetProblemDataEngine());
    densityArray = new double[nodeNumber];
    if(!isRelative) qkpKnowledge.initFullDensityArray(densityArray);
  }

  public void initUtilities() {
    super.initUtilities();
    initUtility(new IntegerUtility("maxExtSize", maxExtSize));
    initUtility(new IntegerUtility("nTour", nTour));
    initUtility(new BooleanUtility("isRelative", isRelative));
  }

  public void shortcutInit() throws Exception {
    super.shortcutInit();
    maxExtSize = TypeConverter.toInteger(getValue("maxExtSize"));
    nTour = TypeConverter.toInteger(getValue("nTour"));
    isRelative = TypeConverter.toBoolean(getValue("isRelative"));
  }

  private void initOrderArray(IGetProblemDataEngine problemData) {
    int nodeNumber = problemData.getNodeNumber();
    int[] weightArray = new int[nodeNumber];
    for (int i=0; i<nodeNumber; i++) {
      weightArray[i] = problemData.getWeightAt(i);
    }
    weightOrderArray = BasicArray.getSortedIndices(weightArray);
    for (int i=0; i<nodeNumber; i++) {
      weightArray[i] = problemData.getWeightAt(weightOrderArray[i]);
    }
    segmentIDArray = new IArray(nodeNumber);
    segmentWVArray = new IArray(nodeNumber);
    BasicCollection.toSegments(segmentIDArray, segmentWVArray, weightArray);
  }

  public void repairBehavior(SearchState baseState) {
    int deltaWSum = qkpKnowledge.getWDifference(baseState);
    int selID;
    IBasicICollectionEngine basicCollection = baseState.getTrueElements();
    while(deltaWSum>0) {
      selID = BasicCollection.getRandomElement(basicCollection);
      baseState.delValueAt(selID);
      deltaWSum -= problemData.getWeightAt(selID);
    }
  }

  private int getMaxWID(int maxWSum) {
    return segmentIDArray.getElementAt(BasicCollection.binaryLSearch(segmentWVArray, maxWSum, 0, segmentWVArray.getSize()-1));
  }

  private void initExtensiveIDs(SearchState baseState, int deltaWSum) {
    idsArray.clear();
    int maxWID = getMaxWID(-deltaWSum);
    for (int i=0; i<maxWID; i++) {
      if (!baseState.getValueAt(weightOrderArray[i])) {
        idsArray.addElement(weightOrderArray[i]);
        if (idsArray.getSize()>=maxExtSize) {
          return;
        }
      }
    }
  }

  private int tourSelDensity(IBasicICollectionEngine idsArray) {
    int ntour = Math.min(idsArray.getSize(), nTour);
    RandomGenerator.randomDistinctSelection(tourSelIDArray, idsArray.getSize(), ntour);
    double maxV = -Double.MAX_VALUE;
    int selID, maxID = -1;
    for (int i=0; i<ntour; i++) {
      selID = idsArray.getElementAt(tourSelIDArray[i]);
      if (densityArray[selID]>maxV) {
        maxV = densityArray[selID];
        maxID = selID;
      }
    }
    return maxID;
  }

  public boolean improveBehavior(SearchState baseState) {
    int deltaWSum = qkpKnowledge.getWDifference(baseState);
    if (deltaWSum>0) return false;
    if (deltaWSum==0) return true;
    if (isRelative) qkpKnowledge.initRelativeDensityArray(densityArray, baseState);

    int selID;
    while(true) {
      initExtensiveIDs(baseState, deltaWSum);
      if (idsArray.getSize()==0) return true;
      selID = tourSelDensity(idsArray);
      baseState.setValueAt(selID);

      if (isRelative) qkpKnowledge.appendRelativeDensityArray(densityArray, selID);

      deltaWSum += problemData.getWeightAt(selID);
    }
  }
}