ENG 335 Computational Intelligence

2024

ASSIGNMENT 3

Genetic Algorithms

This is a compulsory assessment item. It counts 15% towards the final assessment and contributes to learning outcome ILO7.  ILO7 is assessed in this assignment and a mark of 50% is required to achieve this ILO.

Goals:

Develop a genetic algorithm for optimising the location of an emergency response unit in order to minimise the response time to a medical emergency in a city.

Submission Requirements:

This assignment is for a group of two students. Each group submits a single report (should include the User’s Guide) as well as software developed.

Plagiarism:

Each assignment must be entirely your own work.   Plagiarism  is  not  tolerated  (you will automatically fail the course).

Problem description:

Part 1

The city is mapped into a 7 km × 7 km grid, shown in Figure 1.  A number in each sector of the grid represents an average number of emergencies per year in a given sector.

Figure 1.  A grid-map of a 7 km × 7 km city.

A fitness function can be defined as a reciprocal of the sum of distances weighted by emergency rates:

where λn is the emergency rate in sector n;  (xn, yn ) are the coordinates of the centre of sector n; and  (xeru, yeru ) are the  location coordinates of the  emergency response unit.  It  can be assumed that the emergency response unit can be located only in the centre of a sector.

Part 2

Develop a genetic algorithm for the problem described in Part 1 assuming that there is a river that divides the city into two parts, West and East, atx = 5 km.  West and East are connected by abridge located atx = 5 km andy = 5.5 km, as shown in Figure 2.

Figure 2.  A grid-map of a 7 km × 7 km city divided by a river.

Find the optimal location of the emergency response unit and compare it with the one obtained in Part 1.

Guidelines:

This assignment should take about 8 hours of work.  Remembering that a report is required, you should aim to allocate your efforts in roughly the following proportions:

1.         Familiarisation with the travelling salesman problem            10%.

2.         Implementation of the genetic algorithm                                50%.

3.         Testing the genetic algorithm                                                  10%.

4.         Developing a user-friendly interface (GUI)

with simulation of the algorithm                                            20%.

5.         Assignment Report                                                                  10%.

Assignment report should include the following:

1.         Introduction.

2.         Short description of the domain problem.

4.         Description of the genetic algorithm developed (examples are required!).

5.         User’s Guide.

6.         Conclusions.