public class AlternatingVariableMethod {

  /** The local search to be used by this AVM instance. */
  protected LocalSearch localSearch;

  /** The termination policy to be used by this AVM instance. */
  protected TerminationPolicy tp;

  /** The initializer used to initialize the values of variables at the start of the AVM search. */
  protected Initializer initializer;

  /**
   * The initializer used to initialize the values of variables following the restarting of the
   * search (after it has become trapped in a local optimum.
   */
  protected Initializer restarter;

  /** The monitor instance being used by a search that is currently in progress. */
  protected Monitor monitor;

  /** The objective function being used by a search that is currently in progress. */
  protected ObjectiveFunction objFun;

  /** The vector being optimized by a search that is currently in progress. */
  protected Vector vector;

  /**
   * Constructs an AVM instance.
   *
   * @param localSearch A local search instance.
   * @param tp The termination policy to be used by the search.
   * @param initializer The initializer to be used to initialize variables at the start <i>and</i>
   *     to restart the search.
   */
  public AlternatingVariableMethod(
      LocalSearch localSearch, TerminationPolicy tp, Initializer initializer) {
    this(localSearch, tp, initializer, initializer);
  }

  /**
   * Constructs an AVM instance.
   *
   * @param localSearch A local search instance.
   * @param tp The termination policy to be used by the search.
   * @param initializer The initializer to be used to initialize variables at the start of the
   *     search.
   * @param restarter The initializer to be used to initialize variables when restarting the search.
   */
  public AlternatingVariableMethod(
      LocalSearch localSearch,
      TerminationPolicy tp,
      Initializer initializer,
      Initializer restarter) {
    this.localSearch = localSearch;
    this.tp = tp;
    this.initializer = initializer;
    this.restarter = restarter;
  }

  /**
   * Performs the AVM search.
   *
   * @param vector The vector of variables to be optimized.
   * @param objFun The objective function to optimize the variables against.
   * @return A Monitor instance detailing the progression statistics of the completed search
   *     process.
   */
  public Monitor search(Vector vector, ObjectiveFunction objFun) {
    // set up the monitor
    this.monitor = new Monitor(tp);

    // set up the objective function
    this.objFun = objFun;
    objFun.setMonitor(monitor);

    // initialize the vector
    this.vector = vector;
    initializer.initialize(vector);

    // is there anything to optimize?
    if (vector.size() == 0) {
      throw new EmptyVectorException();
    }

    try {
      // the loop terminates when a TerminationException is thrown
      while (true) {

        // search over the vector's variables
        alternatingVariableSearch(vector);

        // restart the search
        monitor.observeRestart();
        restarter.initialize(vector);
      }

    } catch (TerminationException exception) {
      // the search has ended
      monitor.observeTermination();
    }

    return monitor;
  }

  /**
   * Conducts an AVM search over an arbitrary vector --- either the complete vector being optimized,
   * or a variable that it is itself a vector (e.g., a string).
   *
   * @param abstractVector The vector to be optimized.
   * @throws TerminationException If the search terminates (as dictated by the TerminationPolicy
   *     this instance was constructed with).
   */
  protected void alternatingVariableSearch(AbstractVector abstractVector)
      throws TerminationException {
    ObjectiveValue lastImprovement = objFun.evaluate(vector);
    int nonImprovement = 0;

    while (nonImprovement < abstractVector.size()) {

      // alternate through the variables
      int variableIndex = 0;
      while (variableIndex < abstractVector.size() && nonImprovement < abstractVector.size()) {

        // perform a local search on this variable
        Variable var = abstractVector.getVariable(variableIndex);
        variableSearch(var);

        // check if the current objective value has improved on the last
        ObjectiveValue current = objFun.evaluate(vector);
        if (current.betterThan(lastImprovement)) {
          lastImprovement = current;
          nonImprovement = 0;
        } else {
          nonImprovement++;
        }

        variableIndex++;
      }
    }
  }

  /**
   * Invoke a search over a particular variable.
   *
   * @param var The variable to be optimized.
   * @throws TerminationException If the search terminates (as dictated by the TerminationPolicy
   *     this instance was constructed with).
   */
  protected void variableSearch(Variable var) throws TerminationException {
    if (var instanceof AtomicVariable) {
      atomicVariableSearch((AtomicVariable) var);
    } else if (var instanceof VectorVariable) {
      vectorVariableSearch((VectorVariable) var);
    }
  }

  /**
   * Invoke a search over a variable of type AtomicVariable.
   *
   * @param atomicVar The variable to be optimized.
   * @throws TerminationException If the search terminates (as dictated by the TerminationPolicy
   *     this instance was constructed with).
   */
  protected void atomicVariableSearch(AtomicVariable atomicVar) throws TerminationException {
    localSearch.search(atomicVar, vector, objFun);
  }

  /**
   * Invoke a search over a variable of type VectorVariable.
   *
   * @param vectorVar The variable to be optimized.
   * @throws TerminationException If the search terminates (as dictated by the TerminationPolicy
   *     this instance was constructed with).
   */
  protected void vectorVariableSearch(VectorVariable vectorVar) throws TerminationException {
    ObjectiveValue current = objFun.evaluate(vector);

    // try moves that increase the vector size
    progressivelyChangeVectorVariableSize(vectorVar, current, true);

    // try moves that decrease the vector size
    progressivelyChangeVectorVariableSize(vectorVar, current, false);

    // now for the alternating variable search...
    alternatingVariableSearch(vectorVar);
  }

  /**
   * Attempt moves to increase and decrease the size of a VectorVariable in a series of moves until
   * the objective function value does not improve.
   *
   * @param vectorVar The vector variable.
   * @param current The current objective value of the overall vector before moves are attempted.
   * @param increase Denotes whether to increase (value is true) or decrease (value is false) the
   *     size of vectorVar.
   * @throws TerminationException Terminates the method if the next ObjectiveValue
   *     doesn't exist (null)
   */
  private void progressivelyChangeVectorVariableSize(
      VectorVariable vectorVar, ObjectiveValue current, boolean increase)
      throws TerminationException {
    ObjectiveValue next = null;

    // try moves that increase the vector size
    do {
      if (next != null) {
        current = next;
      }

      changeVectorVariableSize(vectorVar, increase);

      next = objFun.evaluate(vector);
    }
    while (next.betterThan(current));

    // reverse the last move, if there was a change
    changeVectorVariableSize(vectorVar, !increase);
  }

  /**
   * Perform a single move to increase or decrease the size of a VectorVariable.
   *
   * @param vectorVar The vector variable.
   * @param increase Denotes whether to increase (value is true) or decrease (value is false) the
   *     size of vectorVar.
   */
  private void changeVectorVariableSize(VectorVariable vectorVar, boolean increase) {
    if (increase) {
      vectorVar.increaseSize();
    } else {
      vectorVar.decreaseSize();
    }
  }
} public class Monitor {

  /** The termination policy being used by the search. */
  protected TerminationPolicy tp;

  /** The best objective value observed so far during hte search. */
  protected ObjectiveValue bestObjVal;

  /** The vector with the best objective value observed so far by the search. */
  protected Vector bestVector;

  /**
   * The number of objective function evaluations that have taken place so far. The count includes
   * non-unique vectors. So if the same vector is evaluated twice, both evaluations will be recorded
   * by this counter.
   */
  protected int numEvaluations;

  /**
   * The number of unique objective function evaluations that have taken place so far. If a vector
   * is evaluated more than once, this count should not increase.
   */
  protected int numUniqueEvaluations;

  /** The number of times the AVM search has been restarted. */
  protected int numRestarts;

  /** The system time (in milliseconds) that the search was started. */
  protected long startTime;

  /** The system time (in milliseconds) that the search was ended. */
  protected long endTime;

  /**
   * Constructs a Monitor instance.
   *
   * @param tp The termination policy being used by the search.
   */
  public Monitor(TerminationPolicy tp) {
    this.tp = tp;
    bestObjVal = null;
    bestVector = null;
    numEvaluations = 0;
    numUniqueEvaluations = 0;
    numRestarts = 0;
    startTime = System.currentTimeMillis();
  }

  /**
   * Gets the best objective value observed by the search so far.
   *
   * @return THe best objective value.
   */
  public ObjectiveValue getBestObjVal() {
    return bestObjVal;
  }

  /**
   * Gets the vector with the best objective value observed by the search so far.
   *
   * @return The best vector.
   */
  public Vector getBestVector() {
    return bestVector;
  }

  /**
   * Gets the number of objective function evaluations that have taken place so far. The count
   * includes non-unique vectors. So if the same vector is evaluated twice, both evaluations will be
   * recorded by this counter.
   *
   * @return The number of objective function evaluations.
   */
  public int getNumEvaluations() {
    return numEvaluations;
  }

  /**
   * Gets the number of unique objective function evaluations that have taken place so far. If a
   * vector is evaluated more than once, this count should not increase.
   *
   * @return The number of unique objective function evaluations.
   */
  public int getNumUniqueEvaluations() {
    return numUniqueEvaluations;
  }

  /**
   * Get the number of times the AVM search has been restarted (following hitting a local optimum).
   *
   * @return The number of times the AVM search has been restarted.
   */
  public int getNumRestarts() {
    return numRestarts;
  }

  /**
   * Gets the running time (in milliseconds) of the search from start to finish. If the search has
   * not terminated, the value is undefined.
   *
   * @return The run time of the search.
   */
  // TODO: should this return the running time also.
  public long getRunningTime() {
    return endTime - startTime;
  }

  // TODO: Better name? No parameter.
  public void observeVector() throws TerminationException {
    tp.checkExhaustedEvaluations(this);
    tp.checkExhaustedTime(this);
    numEvaluations++;
  }

  public void observePreviouslyUnseenVector(Vector vector, ObjectiveValue objVal)
      throws TerminationException {
    if (bestObjVal == null || objVal.betterThan(bestObjVal)) {
      bestObjVal = objVal;
      bestVector = vector.deepCopy();
    }
    numUniqueEvaluations++;

    tp.checkFoundOptimal(this);
  }

  public void observeRestart() throws TerminationException {
    tp.checkExhaustedRestarts(this);
    tp.checkExhaustedTime(this);
    numRestarts++;
  }

  public void observeTermination() {
    endTime = System.currentTimeMillis();
  }
} public class TerminationPolicy {

  public static final int NO_LIMIT = -1;

  protected boolean terminateOnOptimal;
  protected int maxEvaluations;
  protected int maxRestarts;
  protected long runningTime;

  public static TerminationPolicy createMaxEvaluationsTerminationPolicy(int maxEvaluations) {
    return new TerminationPolicy(true, maxEvaluations, NO_LIMIT, NO_LIMIT);
  }

  public static TerminationPolicy createMaxRestartsTerminationPolicy(int maxRestarts) {
    return new TerminationPolicy(true, NO_LIMIT, maxRestarts, NO_LIMIT);
  }

  public static TerminationPolicy createRunningTimeTerminationPolicy(long maxTime) {
    return new TerminationPolicy(true, NO_LIMIT, NO_LIMIT, maxTime);
  }

  public TerminationPolicy(
      boolean terminateOnOptimal, int maxEvaluations, int maxRestarts, long runningTime) {
    this.terminateOnOptimal = terminateOnOptimal;
    this.maxEvaluations = maxEvaluations;
    this.maxRestarts = maxRestarts;
    this.runningTime = runningTime;
  }

  public void checkFoundOptimal(Monitor monitor) throws TerminationException {
    if (terminateOnOptimal
        && monitor.getBestObjVal() != null
        && monitor.getBestObjVal().isOptimal()) {
      throw new TerminationException();
    }
  }

  public void checkExhaustedEvaluations(Monitor monitor) throws TerminationException {
    if (maxEvaluations != NO_LIMIT && monitor.getNumEvaluations() >= maxEvaluations) {
      throw new TerminationException();
    }
  }

  public void checkExhaustedRestarts(Monitor monitor) throws TerminationException {
    if (maxRestarts != NO_LIMIT && monitor.getNumRestarts() >= maxRestarts) {
      throw new TerminationException();
    }
  }

  public void checkExhaustedTime(Monitor monitor) throws TerminationException {
    if (runningTime != NO_LIMIT && System.currentTimeMillis() - monitor.startTime > runningTime) {
      throw new TerminationException();
    }
  }
} public class Vector extends AbstractVector {

  public void addVariable(Variable variable) {
    variables.add(variable);
  }

  public List<Variable> getVariables() {
    return new ArrayList<>(variables);
  }

  public void setVariablesToInitial() {
    for (Variable var : variables) {
      var.setValueToInitial();
    }
  }

  public void setVariablesToRandom(RandomGenerator rg) {
    for (Variable var : variables) {
      var.setValueToRandom(rg);
    }
  }

  public Vector deepCopy() {
    Vector copy = new Vector();
    deepCopyVariables(copy);
    return copy;
  }
} public class ArgsParser {

  protected Class<?> classWithMainMethod;
  protected String[] args;
  protected Map<String, String> params = new LinkedHashMap<>();

  public ArgsParser(Class<?> classWithMainMethod, String[] args) {
    this.classWithMainMethod = classWithMainMethod;
    this.args = args;
    addParams();
  }

  protected void addParams() {
    addParam(
        "[search]",
        "an optional parameter denoting which search to use "
            + "(e.g., \"IteratedPatternSearch\", \"GeometricSearch\" or \"LatticeSearch\")");
  }

  public void addParam(String name, String description) {
    params.put(name, description);
  }

  public void error(String error) {
    System.out.println("ERROR: " + error);
    usage();
    System.exit(1);
  }

  public void usage() {
    String usage =
        "USAGE: java "
            + classWithMainMethod
            + " "
            + StringUtils.join(params.keySet(), " ")
            + " \n"
            + "  where: \n";
    for (String paramName : params.keySet()) {
      usage += "    - " + paramName + " is " + params.get(paramName) + "\n";
    }

    System.out.println(usage);
  }

  public LocalSearch parseSearchParam(String defaultSearch) {
    return parseSearchParam(0, defaultSearch);
  }

  public LocalSearch parseSearchParam(int index, String defaultSearch) {
    String searchName = defaultSearch;
    if (args.length > index) {
      searchName = args[index];
    }

    LocalSearch search = null;
    try {
      search = LocalSearch.instantiate(searchName);
    } catch (Exception exception) {
      error(exception.getMessage());
    }

    return search;
  }
} public abstract class Initializer {

  public abstract void initialize(Vector vector);
} public class RandomInitializer extends Initializer {

  protected RandomGenerator rg;

  public RandomInitializer(RandomGenerator rg) {
    this.rg = rg;
  }

  @Override
  public void initialize(Vector vector) {
    vector.setVariablesToRandom(rg);
  }
} public abstract class LocalSearch {

  protected AtomicVariable var;
  protected Vector vector;
  protected ObjectiveFunction objFun;

  public void search(AtomicVariable var, Vector vector, ObjectiveFunction objFun)
      throws TerminationException {
    this.var = var;
    this.objFun = objFun;
    this.vector = vector;

    performSearch();
  }

  protected abstract void performSearch() throws TerminationException;

  public static LocalSearch instantiate(String name) {
    try {
      String localSearchClassName = "org.avmframework.localsearch." + name;
      Class<?> localSearchClass = Class.forName(localSearchClassName);
      return (LocalSearch) localSearchClass.newInstance();
    } catch (ClassNotFoundException | InstantiationException | IllegalAccessException exception) {
      throw new RuntimeException("Unable to instantiate search \"" + name + "\"");
    }
  }
} public class NumericObjectiveValue extends ObjectiveValue<NumericObjectiveValue> {

  protected double value;
  protected boolean higherIsBetter;

  protected boolean haveOptimum = false;
  protected double optimum;

  public NumericObjectiveValue(double value, boolean higherIsBetter) {
    this.value = value;
    this.higherIsBetter = higherIsBetter;
  }

  public NumericObjectiveValue(double value, boolean higherIsBetter, double optimum) {
    this(value, higherIsBetter);
    this.haveOptimum = true;
    this.optimum = optimum;
  }

  public double getValue() {
    return value;
  }

  @Override
  public boolean isOptimal() {
    if (!haveOptimum) {
      return false;
    }

    if (higherIsBetter) {
      return value >= optimum;
    } else {
      return value <= optimum;
    }
  }

  @Override
  public int compareTo(NumericObjectiveValue other) {
    if (value == other.value) {
      return 0;
    } else if (value < other.value) {
      return higherIsBetter ? -1 : 1;
    } else {
      return higherIsBetter ? 1 : -1;
    }
  }

  @Override
  public String toString() {
    return "" + getValue();
  }

  public static NumericObjectiveValue higherIsBetterObjectiveValue(double value) {
    return new NumericObjectiveValue(value, true);
  }

  public static NumericObjectiveValue higherIsBetterObjectiveValue(double value, double optimum) {
    return new NumericObjectiveValue(value, true, optimum);
  }

  public static NumericObjectiveValue lowerIsBetterObjectiveValue(double value) {
    return new NumericObjectiveValue(value, false);
  }

  public static NumericObjectiveValue lowerIsBetterObjectiveValue(double value, double optimum) {
    return new NumericObjectiveValue(value, false, optimum);
  }
} public abstract class ObjectiveFunction {

  public static final boolean USE_CACHE_DEFAULT = true;

  protected boolean useCache = USE_CACHE_DEFAULT;
  protected Map<Vector, ObjectiveValue> previousVals = new HashMap<>();
  protected Monitor monitor;

  public void setMonitor(Monitor monitor) {
    this.monitor = monitor;
  }

  public ObjectiveValue evaluate(Vector vector) throws TerminationException {
    monitor.observeVector();

    if (useCache && previousVals.containsKey(vector)) {
      return previousVals.get(vector);
    }

    ObjectiveValue objVal = computeObjectiveValue(vector);

    if (useCache) {
      previousVals.put(vector.deepCopy(), objVal);
    }

    if (monitor != null) {
      monitor.observePreviouslyUnseenVector(vector, objVal);
    }

    return objVal;
  }

  protected abstract ObjectiveValue computeObjectiveValue(Vector vector);
} public abstract class ObjectiveValue<T extends ObjectiveValue> implements Comparable<T> {

  public abstract boolean isOptimal();

  public boolean betterThan(T other) {
    return compareTo(other) > 0;
  }

  public boolean sameAs(T other) {
    return compareTo(other) == 0;
  }

  public boolean worseThan(T other) {
    return compareTo(other) < 0;
  }
} public class IntegerVariable extends AtomicVariable {

  public IntegerVariable(int initialValue, int min, int max) {
    super(initialValue, min, max);
    if (min > max) {
      throw new MinGreaterThanMaxException(min, max);
    }
    setValueToInitial();
  }

  public int asInt() {
    return value;
  }

  @Override
  public IntegerVariable deepCopy() {
    IntegerVariable copy = new IntegerVariable(initialValue, min, max);
    copy.value = value;
    return copy;
  }

  @Override
  public String toString() {
    return "" + asInt();
  }
} public interface Variable {

  void setValueToInitial();

  void setValueToRandom(RandomGenerator randomGenerator);

  Variable deepCopy();
}
import org.apache.commons.math3.random.MersenneTwister;
import org.apache.commons.math3.random.RandomGenerator;
import org.avmframework.AlternatingVariableMethod;
import org.avmframework.Monitor;
import org.avmframework.TerminationPolicy;
import org.avmframework.Vector;
import org.avmframework.examples.util.ArgsParser;
import org.avmframework.initialization.Initializer;
import org.avmframework.initialization.RandomInitializer;
import org.avmframework.localsearch.LocalSearch;
import org.avmframework.objective.NumericObjectiveValue;
import org.avmframework.objective.ObjectiveFunction;
import org.avmframework.objective.ObjectiveValue;
import org.avmframework.variable.IntegerVariable;
import org.avmframework.variable.Variable;
package org.avmframework.examples;


public class OneMax {

  // HOW TO RUN:
  //
  // java class org.avmframework.examples.OneMax [search]
  //   where:
  //     - [search] is an optional parameter denoting which search to use
  //       (e.g., "IteratedPatternSearch", "GeometricSearch" or "LatticeSearch")

  // CHANGE THE FOLLOWING CONSTANTS TO EXPLORE THEIR EFFECT ON THE SEARCH:

  // - vector constants
  static final int NUM_VARS = 10;
  static final int INIT = 0;
  static final int MIN = -100000;
  static final int MAX = 100000;

  // - search constants
  static final String SEARCH_NAME = "IteratedPatternSearch"; // can also be set at the command line
  static final int MAX_EVALUATIONS = 1000;

  public static void main(String[] args) {

    // define the objective function
    ObjectiveFunction objFun =
        new ObjectiveFunction() {
          @Override
          protected ObjectiveValue computeObjectiveValue(Vector vector) {
            int distance = 0;
            for (Variable var : vector.getVariables()) {
              distance += Math.abs(((IntegerVariable) var).getValue() - 1);
            }
          return NumericObjectiveValue.lowerIsBetterObjectiveValue(distance, 0);

          }
        };

    // set up the vector to be optimized
    Vector vector = new Vector();
    for (int i = 0; i < NUM_VARS; i++) {
      vector.addVariable(new IntegerVariable(INIT, MIN, MAX));
    }

    // instantiate local search from command line, using default (set by the constant SEARCH_NAME)
    // if none supplied
    LocalSearch localSearch = new ArgsParser(OneMax.class, args).parseSearchParam(SEARCH_NAME);

    // set up the termination policy
    TerminationPolicy terminationPolicy =
        TerminationPolicy.createMaxEvaluationsTerminationPolicy(MAX_EVALUATIONS);

    // set up random initialization of vectors
    RandomGenerator randomGenerator = new MersenneTwister();
    Initializer initializer = new RandomInitializer(randomGenerator);