Assessment details for All students
Assessment item 1
| Due Date: AEST Weighing: |
Friday of Week 5 (9th April 2021) 11.55 pm 30% |
AssignmentTutorOnline
Objectives
• Model and design solution to the given problem applying principles of Genetic
Algorithms.
• Develop source code and implement designed solution.
• Follow correct procedure for implementing a Genetic Algorithm.
• Test software implementations to ensure correctness and maintainability.
Assessment Task
In this assignment, you are required to write a Java Application for the following
problem(provided in section-A) which involves finding the most efficient route through a
collection of suburbs visiting each suburb exactly once. This is a classical optimization problem
that can be applied to many other applications such as network routing.
A brute force algorithm which systematically tries every possible solution is the only
guaranteed method that can produce an optimal solution. By using brute force algorithm, the
number of potential solutions experiences factorial growth. This means a problem with 5
suburbs will have 5! (120) potential solutions and with a problem with 10 suburbs that can be
3,628,800 solutions. Soon this can be over the available computation resources. The strategy is
to use genetic algorithm to find a good enough solution near to optimal.
A. The Problem
Assume that you work for a product delivery company, where you need to deliver products to
different suburbs of a city. In its simplest form, the suburbs can be represented by nodes on a
graph, with the distance between suburbs represented by the length of the edges as shown in
Figure 1. You can generate a set of suburbs by setting each suburb to a random x, y position in
a 2D space. A route defines, commencing from a specific node (representing a suburb), which
edges should be used, and what order, to reach back to the same node. The total distance
travelled or the route length can be calculated by summing the length of the edges used in the
route.
This is a simpler simulation of a more complex problem where it is assumed that there exists a
direct path between every pair of suburbs and travelling from one suburb to another in either
direction takes the same distance, which is known as the symmetric travelling deliveryman
problem. In a real-world situation this can be different if there are one-way routes between
suburbs.
You can calculate the distance between two suburbs A, B represented by two nodes (Xa, Ya),
and (Xb, Yb) using the following equation:
2
COIT20277 Assignment One Specification
continued next page
Distance = √(