COMP2001 Project 2025

2025-04-17 Admin 写评论

Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due

COMP2001 Project 2025

The project involves an implementation of a HyFlex compatible Sight-Seeing Problem (SSP) Domain and learning-based selection hyper-heuristic solution method. You must submit your implementation by the deadline and attend the in-lab practical exam using the implementation that was submitted on Moodle – submitted code may be crosschecked with your responses so it is essential that the code submitted is the one used during the in-lab practical exam.

Problem Description

Imagine you are on a holiday and today is the last day of your trip. You wake up in your hotel and need to arrive at the airport later in the day. Before you leave, there are several points-of-interest (locations) that you want to sight-see before going to the airport and boarding the aircraft on your journey home. To be able to visit all the locations, you need to optimise the order in which you visit each of them such that the total distance travelled is minimised. This problem is called as the Sight-Seeing Problem (SSP) and is an example of an NP-hard combinatorial optimisation problem.

Problem description: Given a set of n sight-seeing locations, S, a relation, L, which maps all points-of-interest to physical locations by x and y coordinates, and a location for the airport, A, with location, (Sx, Sy) where your journey begins and ends, the problem is to find an ordering of all sight-seeing locations which minimises the total distance travelled starting from your hotel, visiting all locations, and then arriving at the airport.

The distance between any two locations is given by the following formula – note the ceiling operator:

Tasks and Requirements

This coursework has two parts. First you will need to implement a HyFlex compatible version of the SSP problem and then design and implement a learning-based selection hyper-heuristic which can be used to solve any given instance of the SSP problem. The second part is an in-lab practical exam; see the Moodle page for further details. Note that during the in-lab practical exam, you will be asked to run your hyper-heuristic for 5 nominal minutes on an unseen problem instance so consider this carefully when designing your hyper-heuristic.

HyFlex Compatible SSP Implementation

You should implement a full suite of components to read, encode, modify, and solve instances of the SSP problem. You should refer to the HyFlex API to ensure that your implementation is HyFlex compatible. As a starting point, a zip archive of some skeleton code is provided on Moodle. Your implementation should have at a minimum the features and components explained below.

Which version of HyFlex should I use?

There is an issue with the Java timer used in the original HyFlex and certain modern computing devices/operating systems which causes timer drift. This matters because your hyper-heuristic will run for some non-deterministic amount of time longer than the time limit which means your results are invalid, and when asked during a timed exam to run your hyper-heuristic, this could take longer than the exam itself meaning you get no result to answer that/those question(s). There is a TimerTest.jar file on Moodle which you should run from the command line via java -jar TimerTest.jar which will tell you if the timer significantly deviates from real time. To run this test, restart your computer, wait for everything to load, and close any programs/apps that may automatically start. Then, run the Java jar file via the command line and wait at least 30 seconds. We believe that the problem is limited to Windows 11 laptops when ran on battery power or when the power plan is set to an equivalent of power saver, but this may evolve to other configurations/operating systems/devices over time.

If the timer does not deviate significantly, you should use the HyFlex_1.0.0_ThreadTimer.jar which is the original CHeSC 2011/HyFlex library implementation, otherwise you should use the HyFlex_1.0.1_WallTimer.jar library which only uses the wall clock time (ensure you close as many background processes as possible when running timed experiments to maximise your computational power during the time limit).

Problem Domain

The SSPDomain class contains skeleton code for a subclass of the HyFlex ProblemDomain class implementing all the problem domain specific operations in accordance with the HyFlex API specification. You must implement all methods in this class to complete the required features of the problem domain base class. There are also methods from the Visualisable interface. This functionality is provided to allow you to visualise your solutions by running the provided `SR_IE_VisualRunner` class.

loadInstance(int instanceId)

The loadInstance(int instanceId) method should call the relevant objects and methods to load the following instance files according to the mapping: { 0: square.ssp, 1: libraries-15.ssp, 2: carparks-40.ssp, 3: tramstops-85.ssp, 4: grid.ssp, 5: clustered.ssp, 6: chatgpt-instance-100.ssp }

Instance Loader

You should complete the implementation of the SSPInstanceReader class such that the call to readSSPInstance(…) is able to read in a SSP problem instance from file and return the problem information as an instance of a SSPInstanceInterface. You may use SSPInstanceReader.java as a starting point.

The format of a SSP problem instance is as follows, noting that underscores are used here to denote whitespaces.

1. A single line starting “NAME_:_” and followed by the name of the problem instance.

2. A single line starting "COMMENT_:_” and followed by a comment.

3. A single line reading “HOTEL_LOCATION” to denote the following line contains coordinates of the hotel location.

4. Immediately following the previous line are two integers separated by a whitespace. The first integer is the x-coordinate and the second integer the y-coordinate of the location of the hotel.

5. A single line reading “AIRPORT_LOCATION” to denote the following line contains coordinates of the airport location.

6. Immediately following the previous line are two integers separated by a whitespace. The first integer is the x-coordinate and the second integer the y-coordinate of the location of the airport.

7. A single line reading “POINTS_OF_INTEREST” to denote that the remaining lines in the file up to and excluding the line “EOF” are locations of each of the individual enclosures.

8. A list of locations encoded in the same way as (4.) where each new line is a new and unique enclosure.

9. A terminating line “EOF” to denote the end of the file.

An example of a SSP instance is as follows:
NAME : <instance name>
COMMENT : <some comment(s)>
HOTEL_LOCATION
0 0
AIRPORT_LOCATION
0 5
POINTS_OF_INTEREST
5 0
10 0
10 5
10 10
5 10
0 10
EOF

Solution

You should complete the implementation of the SSPSolution and SolutionRepresentation classes to perform the necessary functions and ensuring adherence to the HyFlex API. Here you need to be careful with the difference between deep and shallow cloning of Objects in Java.

Instance

You should complete the implementation of the SSPInstance class to provide the necessary problem instance information to the various classes where you may reference this. The createSolution(InitialisationMode mode) method should be implemented to generate and return a complete and feasible solution based on one of two methods determined by the InitialisationMode.

RANDOM: In this mode the initial solution should be generated randomly.

CONSTRUCTIVE: In this mode, you should implement the nearest neighbour greedy algorithm where the first sight-seeing location visited after leaving the hotel in chosen as the one that is closest to the hotel, and all subsequent locations are those closest to the current location.

Low-level Heuristics

At a minimum, you should implement all the heuristics defined below. Better projects will consider efficient implementations of the heuristics (think about concepts discussed in the lectures), and implementing additional heuristics beyond what is described below will also attract more marks. You may think about other neighbourhood operators which can be used to create additional heuristics and aim to implement at least: one other mutation type heuristic, one other local search type heuristic, and one other crossover type heuristic.

AdjacentSwap

This mutation type heuristic swaps adjacent elements of the representation of the solution. You should not swap a sight-seeing location with the hotel or airport, and you do not need to (and should not) allow the swapping of the first and last sightseeing locations in your solution. This heuristic should make use of the intensityOfMutation setting to perform an internal number of swaps equal to:

Intensity of mutation range
 Number of internal swaps
iom ∈ [0.0, 0.2)
 1
iom ∈ [0.2, 0.4)
 2
iom ∈ [0.4, 0.6)
 4
iom ∈ [0.6, 0.8)
 8
iom ∈ [0.8, 1.0)
 16
iom == 1
 32

Reinsertion

This mutation type heuristic removes a single element and reinserts it into a different position of the solution. It should be possible to choose any sight-seeing location for removal, and it should be possible that it gets reinserted at any other position provided the hotel and airport remain as the start and end locations. This heuristic should make use of the intensityOfMutation setting to perform an internal number of reinsertions equal to:

Intensity of mutation range
 Number of internal reinsertions
iom ∈ [0.0, 0.2)
 1
iom ∈ [0.2, 0.4)
 2
iom ∈ [0.4, 0.6)
 3
iom ∈ [0.6, 0.8)
 4
iom ∈ [0.8,1.0]
 5

NextDescent

This local search (hill climbing) type heuristic should use the adjacent swap neighbourhood operator to explore the neighbouring solutions. The first (strict) improvement that it finds should be persisted/accepted and the heuristic returns that Page | 6 as the new solution. This heuristic should make use of the depthOfSearch setting to perform an internal number of iterations equal to:

Depth of search range
 Number of internal iterations
dos ∈ [0.0, 0.2)
 1
dos ∈ [0.2, 0.4)
 2
dos ∈ [0.4, 0.6)
 3
dos ∈ [0.6, 0.8)
 4
dos ∈ [0.8,1.0]
 5

DavissHillClimbing

This local search (hill climbing) type heuristic should operate in the same way as Davis’s Bit Hill Climbing (DBHC) as covered in lab 2, but where the bitflip for MAX-SAT is replaced with the adjacent swap neighbourhood operator. This heuristic should make use of the depthOfSearch setting to perform an internal number of iterations equal to:

Depth of search range
 Number of internal iterations
dos ∈ [0.0, 0.2)
 1
dos ∈ [0.2, 0.4)
 2
dos ∈ [0.4, 0.6)
 3
dos ∈ [0.6, 0.8)
 4
dos ∈ [0.8,1.0]
 5

Order Crossover (OX)

This crossover type heuristic should take two parent solutions and create a single child (chosen randomly) according to the explanation of OX from the lectures (see lecture 6). When selecting the two cut points, you should ensure that it is not possible that all sightseeing locations are within the segment to be copied. There is no requirement to use either of the intensity of mutation or depth of search settings for this implementation.

Additional Note(s)

Important: When implementing the domain and its components, you should think about the use of relevant concepts/techniques discussed in the COMP2001 lectures to improve the efficiency of your problem domain implementation. You may be asked during the in-lab practical exam to explain what this (these) technique(s) is (are), or about a specific technique, and explain how such technique(s) work to improve the efficiency of your implementation.

Learning-based Selection Hyper-heuristic

You must implement a learning-based selection hyper-heuristic different from that in the lab exercise and be able to explain the components you have used and how these together are a learning-based selection hyper-heuristic as opposed to any of the other techniques. We will ask you to run this during the practical examination with a reduced computational budget of 5 nominal minutes, so it is essential that you have the supporting framework in place to run your hyper-heuristic.

Submission and Format of Assessment

You should submit your source code and implementation of both the problem domain and learning-based selection hyper-heuristic to Moodle before 24th April 2025 3pm. It is a requirement that you do this submission before you will be allowed access to the exam itself.

The second part of the coursework involves a Moodle quiz-based practical exam, similar in style to the quizzes from the lab exercises, where you will need to use (make small modifications and run) the project that you submitted from the first part. In addition, you will be asked to explain certain elements of your implementation, hyperheuristic design, and of the problem itself. It is not enough to just attend the in-lab practical exam without having understood the problem description, implemented the domain, or implemented a selection hyper-heuristic. You should aim to have a working implementation of both the problem domain, and hyper-heuristic solution method as during the exam we may ask you to:

• Perform a few simple modifications to your implementation.
• Run a given piece of code on your domain implementation.
• Report certain solution(s) that you obtain to given problems.

It is therefore essential that your SSP domain implementation conforms to the HyFlex `ProblemDomain` interface and the `InLabPracticalExamInterface`, and your selection hyper-heuristic to the `HyperHeuristic` interface.

The in-lab practical exam will take place on Friday 9th May within the timetabled lab hours - further details on allocated rooms/time slots to be released closer to the date of the exam.

Use of AI Tools and Collaboration

This statement here is explicit written consent that use of AI tools such as ChatGPT and IntelliJ’s AI code assistant is permitted for aiding with the implementation of your problem domain and selection hyper-heuristic.

During the in-lab practical exam however, these tools are strictly forbidden and must be closed, disabled, or removed prior to starting the exam. (For example, see the following to disable AI assistant in IntelliJ: https://www.jetbrains.com/help/idea/disable-ai assistant.html).

It is advisable to implement the project on your own as you will need to understand how each component works in case you are asked to explain or modify some part of your code during the practical exam. An over-reliance on such AI tools could mean that you may not fully understand how each component of your implementation works and hence be unable to explain these when required to do so during the practical exam. Furthermore, AI tools can make mistakes and does make mistakes when asked to
implement this project so you should carefully consider the scope of their use.

发表评论

电子邮件地址不会被公开。 必填项已用*标注