MEC304 – Optimization 2025-2026 Semester 1
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
MEC304 – Optimization 2025-2026 Semester 1
Coursework
Key Information
|
Deadline: |
|
|
Where: |
Learning Mall |
|
Assessment: |
50 % of Final Marks |
|
Outcomes Assessed: |
A. Optimization methods for system analysis and modelling B. Apply optimization methods to practical problems C. Use optimization algorithm development to achieve engineering optimization solution. D. Resolve the basic engineering optimization problems using a variety of programming, design and simulation tools |
1 Section A (50%):
1.1 Background:
The Pac-Man project was originally developed for UC Berkeley’s introductory artificial intelligence course. It applies a range ofAI techniques to the Pac-Man game. However, the focus of these projects is not on building AI for video games, but on introducing fundamental AI concepts such as informed state-space search, probabilistic inference, and reinforcement learning. These core ideas underpin real-world applications in areas including natural language processing, computer vision, and robotics.
The aim of this project is to deepen your understanding of Ant Colony Optimization (ACO) algorithms [1] and to provide hands-on experience in deriving heuristics using the Berkeley Pac- Man framework. By studying animal-inspired optimization methods, modelling the game system, and implementing the algorithms in Python, this project demonstrates a practical case of applying optimization techniques to solve real-world problems. All learning outcomes will be evaluated through this applied example.
1.2 Environment Set Up
macOS
If you are running macOS High Sierra (10.13.6) or a later version, macOS already includes Python 2.x by default, so you do not need to install any additional software. Alternatively, you may choose to download and install Python 2.7.18 from the official source here.
Windows
You can download and install python 2.7.18 from here. Remember to tick ‘Add Python To Path’.
1.3 Task
Test
Run following command
python - V
in Terminal (macOS) or Command Line (CMD in Windows) . If you successfully installed the python with the correct version, the output will be similar to
ZirendeiMac : ˜ ziren $ python -V
Python 2.7.18
Note that python subversion may vary, but ensure your python version is OVER 2 . 7 and NOT 3 .x. Now you may navigate to project folder using ‘ cd ’ command and try
python pacman.py
Pacman lives in a shiny blue world of twisting corridors and tasty round treats. Navigating this world efficiently will be Pacman ’s first step in mastering his domain.
Task 1 （10%）
By default, we provide a simple AI implemented in the AntAgent class, which moves completely at random. Your task is to build upon AntAgent and implement your own algorithms within this class. Many useful methods (similar to functions) that you may find helpful for this project are described in pacmanAgents.py. You must not modify any files other than pacmanAgents.py, and you should not import any additional libraries, except for NumPy if necessary.
Your first task is to implement a basic Ant Colony Optimization (ACO) algorithm to compute the shortest path to a single food item in easy mode. The general ACO procedure can be described as follows:
1. Start from Pacman’s current location cp and plan a path toward the food cf.
2. From this position cp , send out n ants to search for the food.
3. During each node-selection stage:
Key Feature 1: An ant is more likely to move to nodes with higher probability, but nodes with lower probability should still retain a chance of being selected.
Key Feature 2: Each ant deposits pheromones along its path, and these pheromones decay over time.
Once the food is reached, calculate the total path length. If the current simulation produces a shorter path than the previously recorded best path, update the best path accordingly.
More details, such as equations and calculations, of ACO can be found in [1]. To run your AntAgent in pacman game under easy mode,
Python pacman. py - p AntAgent - l easy
The command above tells the computer to use AntAgent as its search agent, which is implemented in pacmanAgents.py.
To get the full mark, you should consider how duplicated simulations can be avoided. Highlight and write a simple description in your implementation.
Task 2 （20%）
Your second task is improving the ACO algorithm implemented in the Task 1 to find multiple foods. To run your AntAgent in pacman game under medium mode,
Python pacman. py - p AntAgent - l medium
The implementation should be compatible with Task 1.
Report (20%)
After completing the algorithm implementation, you are also required to submit a report. The suggested structure includes: cover page, table of contents, list of figures, list of tables, introduction, problem statement, methodology, results and analysis, conclusions, and references. In addition, a critical thinking section should be included to reflect on both your work in this assessment and your broader learning from the module. The use of the IEEE referencing style is recommended. The use of AI tools is strictly forbidden for this assignment.
2 Section B: (50%):
2.1 Traveling Salesman Problem using Ant Colony Optimization
Given a list of 15 cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the starting city?
2.2 Task
Write code for implementing the ACO algorithm using Matlab to find the best route. (Assume there are 15 cities and you can design the coordinates of the cities by yourselves) (20%).
Provide a report including problem statement, methodology, results, analysis, conclusions and references (30%).
2.3 Requirements
l Write and implement algorithm in Matlab
l Find solution for the optimization problem
l Draft a report with more than 3 pages in main body
l Your report should be based on your own understanding
l Reference any sources you use with the IEEE Referencing system
l The use of AI tools is strictly forbidden for this assignment.
3 Marking Criteria for Implementation
The marks are broken down as follows:
Section # and description Marks
Section A(task 1): eat food 5
Section A(task 1): optimal solution (shortest path) 5
Section A(task 2): eat multiple foods 10
Section A(task 2): optimal solution (shortest paths) 10
Section A:report 20
Section B: algorithm 20
Section B: report 30
Late submission shall follow university policy available on the university website. 5% of the total marks available for the assessment shall be deducted from the assessment mark for each working day after the submission date, up to a maximum of five working days.
Academic Misconduct
The University misconduct policy applies. Students are encouraged to discuss the assignment topics, but all submitted work must represent the individual’s understanding of the topic.
The subject staff take academic misconduct seriously. In the past, we have prosecuted several students that have breached the university policy. Often this results in receiving 0 marks for the assessment, and in some cases, has resulted in failure of the subject.
Important: As part of marking, we run all submissions via a code similarity comparison tool. These tools are quite sophisticated and are not easily fooled by attempts to make code look different. In short, if you copy code from classmates or from online sources, you risk facing academic misconduct charges.
Licensing Information
Section A is modified from UC Berkeley AI courses, http://ai.berkeley.edu
References
[1] Dorigo, M., Birattari, M., and Stutzle, T. Ant colony optimization . IEEE Computational Intelligence Magazine .
2025-12-08