SightseeingProblemDomain.java

package com.aim.project.ssp;


import com.aim.project.ssp.heuristics.crossover.OX;
import com.aim.project.ssp.heuristics.crossover.PMX;
import com.aim.project.ssp.heuristics.localsearch.DavissHillClimbing;
import com.aim.project.ssp.heuristics.localsearch.NextDescent;
import com.aim.project.ssp.heuristics.localsearch.TwoOptSwap;
import com.aim.project.ssp.heuristics.mutation.AdjacentSwap;
import com.aim.project.ssp.heuristics.mutation.InversionMutation;
import com.aim.project.ssp.heuristics.mutation.Reinsertion;
import com.aim.project.ssp.instance.InitialisationMode;
import com.aim.project.ssp.instance.Location;
import com.aim.project.ssp.instance.reader.SSPInstanceReader;
import com.aim.project.ssp.interfaces.*;
import AbstractClasses.ProblemDomain;
import java.nio.file.Path;
import java.util.ArrayList;
import java.util.List;

/**
 * This class represents the Sightseeing Problem Domain.
 * It handles the application of various heuristics and manages solutions.
 * It implements methods from the ProblemDomain and Visualisable interfaces.
 *
 * @author : Sushant Nepal
 * @since : 17/03/2025
 */
public class SightseeingProblemDomain extends ProblemDomain implements Visualisable, InLabPracticalExamInterface {

	/** Instance representing the problem domain */
	public SSPInstanceInterface m_oInstance;

	/** Array of heuristics used for generating solutions */
	private final HeuristicInterface[] heuristics;

	/** Array of solutions */
	public SSPSolutionInterface[] solutions;

	/**
	 * Constructor initializes the heuristics and memory size for storing solutions.
	 *
	 * @param seed Random number generator seed
	 */
	public SightseeingProblemDomain(long seed) {

        super(seed);

		// Initialize heuristics array
		heuristics = new HeuristicInterface[]{
				new AdjacentSwap(rng),
				new DavissHillClimbing(rng),
				new NextDescent(rng),
				new OX(rng),
				new Reinsertion(rng),
				new InversionMutation(rng),
				new TwoOptSwap(rng),
				new PMX(rng)
		};

		// Set memory size for storing solutions - Current (Best), Candidate, Crossover (for Crossover heuristics)
		setMemorySize(3);
	}

	/**
	 * Applies a heuristic to a single solution and stores the result.
	 *
	 * @param hIndex Index of the heuristic to apply
	 * @param currentIndex Index of the current solution
	 * @param candidateIndex Index where the resulting solution will be stored
	 * @return The objective function value of the resulting solution
	 */
	@Override
	public double applyHeuristic(int hIndex, int currentIndex, int candidateIndex) {
		// Get the heuristic to apply using the heuristic ID
		HeuristicInterface heuristic = heuristics[hIndex];

		// Get the source solutions
		SSPSolutionInterface sourceSolution = solutions[currentIndex].clone();

		// To store the objective value
		double objectiveValue = sourceSolution.getObjectiveFunctionValue();
		//System.out.println(sourceSolution.getSolutionRepresentation());

		// Only if the heuristic isn't of Crossover type
		if (!(heuristic instanceof OX)) {
			// Apply the heuristic to the source solution and store the result in the destination solution
			objectiveValue = heuristic.apply(sourceSolution, depthOfSearch, intensityOfMutation);
		}

		// Deep copy of the source solution to avoid reference issues
		SSPSolutionInterface candidateSolution = sourceSolution.clone();

		// Store the modified source solution in the memory array at the destination index
		solutions[candidateIndex] = candidateSolution;

		// Return the objective function value of the resulting solution
		return objectiveValue;
	}

	/**
	 * Applies a heuristic involving two parent solutions and stores the result.
	 * This method allows for crossover heuristics to be used alongside the regular heuristic
	 *
	 * @param hIndex Index of the heuristic to apply
	 * @param parent1Index Index of the first parent solution
	 * @param parent2Index Index of the second parent solution
	 * @param candidateIndex Index where the resulting solution will be stored
	 * @return The objective function value of the resulting solution
	 */
	@Override
	public double applyHeuristic(int hIndex, int parent1Index, int parent2Index, int candidateIndex) {
		// Get the heuristic to apply using the heuristic ID
		HeuristicInterface heuristic = heuristics[hIndex];

		// Get the parent solutions from the solution array
		SSPSolutionInterface parent1 = solutions[parent1Index].clone();
		SSPSolutionInterface parent2 = solutions[parent2Index].clone();

		// Get the candidate solution object
		SSPSolutionInterface candidateSolution = solutions[candidateIndex].clone();

		// Check if the heuristic is a Order Crossover type
		if (heuristic instanceof OX oxHeuristic) {
			// Apply OX with parent1 and parent2 to generate a child solution
			double objectiveValue = oxHeuristic.apply(parent1, parent2, candidateSolution, depthOfSearch, intensityOfMutation);

			// Store the resulting candidate solution at the candidate index
			solutions[candidateIndex] = candidateSolution;

			// Return the objective function value of the resulting solution
			return objectiveValue;
		}
		// Check if the heuristic is an instance of PMX
		else if (heuristic instanceof PMX pmxHeuristic) {
			// Apply PMX with parent1 and parent2 to generate a child solution
			double objectiveValue = pmxHeuristic.apply(parent1, parent2, candidateSolution, depthOfSearch, intensityOfMutation);

			// Store the resulting candidate solution at the candidate index
			solutions[candidateIndex] = candidateSolution;

			// Return the objective function value of the resulting solution
			return objectiveValue;
		} else {
			// If the heuristic is not OX
			return applyHeuristic(hIndex, parent1Index, candidateIndex);
		}
	}

	/**
	 * Converts the best solution into a string representation.
	 *
	 * @return String representation of the best solution
	 */
	@Override
	public String bestSolutionToString() {
		return solutions[0].getSolutionRepresentation().toString();
	}

	/**
	 * Compares two solutions based on their representations.
	 *
	 * @param iIndex1 Index of the first solution
	 * @param iIndex2 Index of the second solution
	 * @return true if the solutions are identical, false otherwise
	 */
	@Override
	public boolean compareSolutions(int iIndex1, int iIndex2) {
		// Get the solutions at the specified indices
		SSPSolutionInterface solution1 = solutions[iIndex1];
		SSPSolutionInterface solution2 = solutions[iIndex2];

		// Get the solution representations (assuming it returns an array or similar structure)
		int[] solutionRep1 = solution1.getSolutionRepresentation().getSolutionRepresentation();
		int[] solutionRep2 = solution2.getSolutionRepresentation().getSolutionRepresentation();

		// Compare the two solution representations
		if (solutionRep1.length != solutionRep2.length) {
			return false;  // If lengths differ, solutions are not identical
		}

		// Compare element by element
		for (int i = 0; i < solutionRep1.length; i++) {
			if (solutionRep1[i] != solutionRep2[i]) {
				return false;  // If any element is different, solutions are not identical
			}
		}

		// If no differences were found, the solutions are identical
		return true;
	}

	/**
	 * Copies a solution from one index to another.
	 *
	 * @param a Index of the source solution
	 * @param b Index of the destination solution
	 */
	@Override
	public void copySolution(int a, int b) {
		// Get the solution to copy from the source index
		SSPSolutionInterface sourceSolution = solutions[a];

		// Create a new instance of the solution, ensuring it's a copy
		SSPSolutionInterface destinationSolution = sourceSolution.clone();

		// Assign the copied solution to the destination index
		solutions[b] = destinationSolution;
	}

	/**
	 * Retrieves the objective function value of the best solution.
	 *
	 * @return Objective function value of the best solution
	 */
	@Override
	public double getBestSolutionValue() {
		return solutions[0].getObjectiveFunctionValue();
	}

	/**
	 * Retrieves the objective function value of a specific solution.
	 *
	 * @param index Index of the solution
	 * @return Objective function value of the solution
	 */
	@Override
	public double getFunctionValue(int index) {
		return solutions[index].getObjectiveFunctionValue();
	}

	/**
	 * Retrieves all heuristics of a specified type.
	 *
	 * @param type The type of heuristics to retrieve
	 * @return An array of heuristic IDs that match the specified type
	 */
	@Override
	public int[] getHeuristicsOfType(HeuristicType type) {
		// List to store heuristic IDs that match the type
		List<Integer> matchingHeuristics = new ArrayList<>();

		// Loop through all heuristics and check their type
		for (int i = 0; i < heuristics.length; i++) {
			HeuristicInterface heuristic = heuristics[i];

			// Check if the heuristic type matches the specified type
			if (heuristic.getType() == type) {
				matchingHeuristics.add(i);  // Add the heuristic ID (index) to the list
			}
		}

		// If no matching heuristics were found, return null
		if (matchingHeuristics.isEmpty()) {
			return null;
		}

		// Convert the list of matching heuristic IDs to an array and return
		int[] result = new int[matchingHeuristics.size()];
		for (int i = 0; i < matchingHeuristics.size(); i++) {
			result[i] = matchingHeuristics.get(i);
		}

		return result;
	}

	/**
	 * Retrieves all heuristics that use the depth of search parameter.
	 *
	 * @return An array of heuristic IDs that use depth of search
	 */
	@Override
	public int[] getHeuristicsThatUseDepthOfSearch() {
		// List to store heuristic IDs that match the type
		List<Integer> matchingHeuristics = new ArrayList<>();

		// Loop through all heuristics and check their type
		for (int i = 0; i < heuristics.length; i++) {
			HeuristicInterface heuristic = heuristics[i];

			// Check if the heuristic uses dos
			if (heuristic.usesDepthOfSearch()) {
				matchingHeuristics.add(i);  // Add the heuristic ID (index) to the list
			}
		}

		// If no matching heuristics were found, return null
		if (matchingHeuristics.isEmpty()) {
			return null;
		}

		// Convert the list of matching heuristic IDs to an array and return
		int[] result = new int[matchingHeuristics.size()];
		for (int i = 0; i < matchingHeuristics.size(); i++) {
			result[i] = matchingHeuristics.get(i);
		}

		return result;
	}

	/**
	 * Retrieves all heuristics that use the intensity of mutation parameter.
	 *
	 * @return An array of heuristic IDs that use intensity of mutation
	 */
	@Override
	public int[] getHeuristicsThatUseIntensityOfMutation() {
		// List to store heuristic IDs that match the type
		List<Integer> matchingHeuristics = new ArrayList<>();

		// Loop through all heuristics and check their type
		for (int i = 0; i < heuristics.length; i++) {
			HeuristicInterface heuristic = heuristics[i];

			// Check if the heuristic uses iom
			if (heuristic.usesIntensityOfMutation()) {
				matchingHeuristics.add(i);  // Add the heuristic ID (index) to the list
			}
		}

		// If no matching heuristics were found, return null
		if (matchingHeuristics.isEmpty()) {
			return null;
		}

		// Convert the list of matching heuristic IDs to an array and return
		int[] result = new int[matchingHeuristics.size()];
		for (int i = 0; i < matchingHeuristics.size(); i++) {
			result[i] = matchingHeuristics.get(i);
		}

		return result;
	}

	/**
	 * Retrieves the total number of heuristics available in the problem domain.
	 *
	 * @return The number of heuristics
	 */
	@Override
	public int getNumberOfHeuristics() {
		return 8;
	}

	/**
	 * Retrieves the number of instances available in the problem domain.
	 *
	 * @return The number of instances
	 */
	@Override
	public int getNumberOfInstances() {
		return 7;
	}

	/**
	 * Initializes a solution at a specified index.
	 *
	 * @param index The index of the solution to initialize
	 * @throws IllegalArgumentException if the index is out of bounds
	 */
	@Override
	public void initialiseSolution(int index) {
		// Bound Checking
		if (index < 0 || index >= solutions.length) {
			throw new IllegalArgumentException("Index out of bounds");
		}

		// Creating new Solution - Initialising Randomly
		SSPSolutionInterface newSolution = m_oInstance.createSolution(InitialisationMode.RANDOM);

		// Adding Solution to Solutions array
		solutions[index] = newSolution;
	}

	/**
	 * Loads an instance by its ID and sets up the problem domain accordingly.
	 *
	 * @param instanceId The ID of the instance to load
	 * @throws IllegalArgumentException if the instanceId is invalid
	 */
	@Override
	public void loadInstance(int instanceId) {
		// Mapping instanceId to filenames
		Path instancePath = getPath(instanceId);

		// Creating an instance reader
		SSPInstanceReader reader = new SSPInstanceReader();

		// Reading the instance and creating it
		m_oInstance = reader.readSSPInstance(instancePath, this.rng);

		// Creating the objective function using the instance
		SSPObjectiveFunction objectiveFunction = new SSPObjectiveFunction(m_oInstance);

		// Setting the objective function value for each heuristic
		for (HeuristicInterface heuristic : heuristics) {
			heuristic.setObjectiveFunction(objectiveFunction);
		}

		// Initialising solutions
		initialiseSolution(0);
		initialiseSolution(1);	// For crossover
		initialiseSolution(2);
	}

	/**
	 * Returns the file path for the given instance ID.
	 *
	 * @param instanceId The ID of the instance
	 * @return The path to the instance file
	 * @throws IllegalArgumentException if the instanceId is invalid
	 */
	private static Path getPath(int instanceId) {
        return switch (instanceId) {
            case 0 -> Path.of("instances/ssp/carparks-40.ssp");
            case 1 -> Path.of("instances/ssp/chatgpt-instance-100.ssp");
            case 2 -> Path.of("instances/ssp/clustered.ssp");
            case 3 -> Path.of("instances/ssp/grid.ssp");
            case 4 -> Path.of("instances/ssp/libraries-15.ssp");
            case 5 -> Path.of("instances/ssp/square.ssp");
            case 6 -> Path.of("instances/ssp/tramstops-85.ssp");
            default -> throw new IllegalArgumentException("Invalid instance ID");
        };
	}

	/**
	 * Sets the memory size for storing SSP solutions.
	 *
	 * @param size the number of solution slots to allocate
	 */
	@Override
	public void setMemorySize(int size) {
		solutions = new SSPSolutionInterface[size];
	}

	/**
	 * Converts a solution at a specific index to its string representation.
	 *
	 * @param index the index of the solution in memory
	 * @return string representation of the solution
	 */
	@Override
	public String solutionToString(int index) {
		return solutions[index].toString();
	}

	/**
	 * Returns the name of the problem domain.
	 *
	 * @return a string representing the domain name
	 */
	@Override
	public String toString() {
		return "psysn2 SSP Domain";
	}

	/**
	 * Returns the currently loaded SSP instance.
	 *
	 * @return the loaded instance of the problem
	 */
	@Override
	public SSPInstanceInterface getLoadedInstance() {
		return m_oInstance;
	}

	/**
	 * Retrieves the best solution route as an array of ordered {@link Location} objects,
	 * starting from the hotel, followed by the sightseeing locations (in the order
	 * determined by the solution), and ending at the airport.
	 *
	 * @return an array of Locations in the order they are visited
	 */
	@Override
	public Location[] getRouteOrderedByLocations() {
		// Gets the solution representation
		int[] solutionRepresentation = solutions[0].getSolutionRepresentation().getSolutionRepresentation();

		// Create an array to store the ordered route
		Location[] orderedRoute = new Location[solutionRepresentation.length];

		// Set the first location as the hotel
		orderedRoute[0] = m_oInstance.getHotelLocation();
		int i = 1;

		// Add all sightseeing locations in the order given by the solution
		for (Location location : m_oInstance.getSolutionAsListOfLocations(solutions[0])) {
			orderedRoute[i] = location;
			i++;
		}

		// Set the last location as the airport
		orderedRoute[orderedRoute.length - 1] = m_oInstance.getAirportLocation();

		return orderedRoute;
	}

	/**
	 * Prints the best solution found so far in the following format:
	 * (h_x,h_y) - (l_x0,l_y0) - ... - (l_x{n-1},l_y{n-1}) - (a_x,a_y)
	 * Where:
	 * <ul>
	 *   <li><code>h</code> is the hotel location</li>
	 *   <li><code>a</code> is the airport location</li>
	 *   <li><code>l_xi</code> and <code>l_yi</code> are coordinates of sightseeing locations</li>
	 * </ul>
	 */
	@Override
	public void printBestSolutionFound() {
		StringBuilder sb = new StringBuilder();

		// Start with hotel
		Location hotel = m_oInstance.getHotelLocation();
		sb.append("(").append(hotel.getX()).append(",").append(hotel.getY()).append(")");

		// Add sightseeing locations
		int[] initialSolutionRepresentation = solutions[0].getSolutionRepresentation().getSolutionRepresentation();
		for (int index : initialSolutionRepresentation) {
			Location loc = m_oInstance.getSightseeingLocation(index);
			sb.append(" - (").append(loc.getX()).append(",").append(loc.getY()).append(")");
		}

		// End with airport
		Location airport = m_oInstance.getAirportLocation();
		sb.append(" - (").append(airport.getX()).append(",").append(airport.getY()).append(")");

		System.out.println("Best Solution:");
		System.out.println(sb);
	}

	/**
	 * Prints the objective function value of the best solution found.
	 */
	@Override
	public void printObjectiveValueOfTheSolutionFound() {
		System.out.println("Best Value: " + solutions[0].getObjectiveFunctionValue());
	}

	/**
	 * Prints the initial solution in the same format as the best solution:
	 * (h_x,h_y) - (l_x0,l_y0) - ... - (l_x{n-1},l_y{n-1}) - (a_x,a_y)
	 * Useful for comparing how far the optimisation has improved from the starting point.
	 */
	@Override
	public void printInitialSolution() {
		StringBuilder sb = new StringBuilder();

		// Start with hotel
		Location hotel = m_oInstance.getHotelLocation();
		sb.append("(").append(hotel.getX()).append(",").append(hotel.getY()).append(")");

		// Add sightseeing locations
		int[] initialSolutionRepresentation = solutions[0].getSolutionRepresentation().getSolutionRepresentation();
		for (int index : initialSolutionRepresentation) {
			Location loc = m_oInstance.getSightseeingLocation(index);
			sb.append(" - (").append(loc.getX()).append(",").append(loc.getY()).append(")");
		}

		// End with airport
		Location airport = m_oInstance.getAirportLocation();
		sb.append(" - (").append(airport.getX()).append(",").append(airport.getY()).append(")");

		System.out.println("Initial Solution:");
		System.out.println(sb);
	}

	/**
	 * Prints the objective value of the initial solution.
	 * This can be compared with the value of the best solution to measure improvement.
	 */
	@Override
	public void printObjectiveValueOfTheInitialSolution() {
		System.out.println("Initial Value: " + solutions[0].getObjectiveFunctionValue());
	}
}