G52AIM Framework API
1 INTRODUCTION
This framework is a Java framework designed for the teaching of heuristic decision support/AI methods. It includes the MAX-SAT problem domain as an example of an NP-hard optimisation problem. A MAX- SAT problem is defined as a Boolean formula in conjunctive normal form (CNF) which is a conjunction of disjunctive clauses. Each clause itself contains one or more variables.
A solution is represented by a binary string (sequence of bits) where each bit represents a truth value of each variable. In the above example, we have the variables {ܣǡܤǡܥǡܦǡܻǡܼ}. A solution to this could be represented as 011011, meaning that ܤǡܥǡܻǡand ܼ are true, and ܣ and ܦ are false.
The objective for MAX-SAT is to maximise the number of satisfied clauses. This framework aims to minimise the objective value; hence a modified objective function is used which is to minimise the number of unsatisfied clauses.
2 APISPECIFICATION
Below are all the Classes and methods etc. that you will need to use in the following lab sessions. Classes/methods/etc. which are used by each LabRunner, and hence not required to complete the courseworks will not be included in this specification but can be found in the Javadoc comments. This document will be your reference to the framework’s API. Any additional information will be supplied in each lab’s respective exercise sheets.
2.1 SAT
Creates a new instance of the MAX-SAT problem and initialises solutions in each memory index.
// Returns true if the termination criterion has lapsed, else returns false. public boolean hasTimeExpired();
// Copies the solution from the originIndex to the destinationIndex.
public void copySolution(int originIndex, int destinationIndex);
// Evaluates and returns the objective value of the solution in memory index index.
public double getObjectiveFunctionValue(int index);

// Flips the truth value of the variable variable in the current solution index (0). public void bitFlip(int variable);
// Flips the truth value of the variable variable in memory index memoryIndex.
public void bitflip(int variable, int memoryIndex);
// Exchanges the bits in index variableIndex between the solutions in indicies solutionIndexA and solutionIndexB.
public void exchangeBits(int solutionIndexA, int solutionIndexB, int variableIndex);
// Gets the objective value of the best solution found.
public double getBestSolutionValue();
// Creates a new solution in memory index index initialised as a random binary string.
public void createRandomSolution(int index);
// Gets the number of variables in the current problem instance.
public int getNumberOfVariables();
// Gets the number of memes associated with the solutions.
public int getNumberOfMemes();
// Gets the Meme at index memeIndex for the solution in memory index solutionIndex.
public Meme getMeme(int solutionIndex, int memeIndex);
2.2 MEME
// Returns the current option of the Meme.
public int getMemeOption();
// Sets the option of the Meme returning false if the supplied option exceeds the total number of possible options of this Meme.
public boolean setMemeOption(int option);
2.3 ARRAYMETHODS
// Returns a shuffled copy of the input arraylist, array, using the supplied random number generator, random.
public static ArrayList
// Returns a shuffled copy of the input array, array, using the supplied random number generator, random.
public static int[] shuffle(int[] array, Random random);
2.4 SATHEURISTIC
2.4.1 Global Variables
// The random number generator.
final Random random;
// The memory index where the solution currently being operated on is.
final int CURRENT_SOLUTION_INDEX;
// The memory index where a backup of the current solution is stored.
final int BACKUP_SOLUTION_INDEX;
2.4.2 Methods
// Applies this heuristic to the problem at memory index CURRENT_SOLUTION_INDEX. public abstract void applyHeuristic(SAT problem);
2.5 POPULATIONHEURISTIC
2.5.1 Global Variables
// Reference to the problem being solved.
final SAT problem;
// The random number generator.
final Random random;
2.5.2 Methods
// Applies this heuristic to the problem at memory index solutionIndex. Public abstract void applyHeuristic(int solutionIndex);
2.6 SINGLEPOINTSEARCHMETHOD
Creates a search method with a population size of 2; one for the current solution,
and one for the backup solution. Note that when an instance of a SinglePointSearchMethod is created, the solution in the current solution index is copied to the backup solution index.
2.6.1 Global Variables
// Reference to the problem being solved.
final SAT problem;
// The random number generator.
final Random random;
// The memory index where the solution currently being operated on is.
final int CURRENT_SOLUTION_INDEX;
// The memory index where a backup of the current solution is stored.
final int BACKUP_SOLUTION_INDEX;
2.6.2 Methods
// Inner loop of the search method. Note that the while loop of each search method has been lifted to the LabRunner Classes to allow for data collection. The responsibility of this loop is therefore to apply the logic for each iteration of the search method and to ensure that the accepted solution is stored in the CURRENT_SOLUTION_INDEX.
protected abstract void runMainLoop();
2.7 POPULATIONBASEDSEARCHMETHOD
Creates a search method with a specified population size. Internally, there are 2 × :memory indices for storing solutions as follows 1 + ܧܼܫܵ_ܱܰܫܶܣܮܷܱܲܲ
0 → ܱܷܲܲ1 − ܧܼܫܵ_ܱܰܫܶܣܮ are used for storing the current/accepted population. ܱܲܲ_ܵ1 − ܧܼܫܵ_ܱܲܲ × 2 → ܧܼܫ are used for storing intermediate
solutions/offspring.
2 × ܱܲܲ_ܵܧܼܫ is used for storing a backup solution if required.
2.7.1 Global Variables
// Reference to the problem being solved.
final SAT problem;
// The random number generator.
final Random random;
// The population size. Note the memory scheme detailed above!
final int POPULATION_SIZE;
// The memory index where a backup solution is stored.
final int BACKUP_SOLUTION_INDEX;
2.7.2 Methods
// Inner loop of the search method. Note that the while loop of each search method has been lifted to the LabRunner Classes to allow for data collection. The responsibility of this loop is therefore to apply the logic for each iteration of the search method and to ensure that the accepted population is stored in the indices 0 → . 1 − ܧ ܼܫ ܵ _ ܰ ܱܫ ܶ ܣ ܮ ܷ ܲ ܱ ܲ
protected abstract void runMainLoop();

3 EXAMPLES
3.1 CREATING A RANDOM BIT HILL CLIMBING HEURISTIC
1. | bit <- random ∈ [0, N-1]; 2. | s’ <- bitflip(s, bit);
3. | if(f(s’) ≤ f(s)) {
4.| s<-s’;
Pseudo-code for Random Bit HC.
}| .5 Solution
Description
Figure 1 - Code for Random Bit Hill Climbing Example.
Since we are creating a new heuristic, we must extend the SATHeuristic class. Within the ,)ݏ(݂ ,applyHeuristic method, we start by evaluating the objective value of the current solution storing this as the currentFitness. The next task is to flip a random bit. This is achieved by generating a random number between 0 and the total number of variables in the problem. Therefore, we must use the nextInt(int upperBound) method of the supplied Random number generator random and pass it the number of variables. Next, we re-evaluate the solution in the current solution index to get the objective value of the candidate solution, ݂(ݏᇱ). We then want to accept this candidate solution if and only if ݂(ݏᇱ) ≤ ݂(ݏ), hence we first check for the opposite. This is because the current solution index already contains ݏ′. Thus if ݂(ݏᇱ) > ݂(ݏ), we must revert the bit flip operation as in Line 29. The accepted solution now resides in the current solution index and we are finished.

3.2 CREATING A NAÏVE ACCEPTANCE METAHEURISTIC Pseudo-code for Naïve Acceptance
1. | s <- initialiseSolution();
2. | 3.| 4.| 5.| 6.| 7.| 8. |
Solution
while( !hasTimeExpired() ) {
s’ <- h(s);
P <- random ∈ [0,1]; if(f(s’)