1122 Introduction to AI Assignment 3: Solve the assignment problem using local and global search algorithms
Introduction to AI Assignment 3
2024/05/22
So far, we have learned lots about search. A common problem with many real-world applications is the assignment problem, which can be defined as follows. Given a set of agents 𝒜, a set of tasks M, and a profit function F: 𝒜 × M → R, assignment problem is to find an assignment for each agent to a unique task such that the total profit is maximized. Write a program to solve the assignment problem using local and global search algorithms.
Implementation
The problem can be described by an 𝑛 × 𝑚 real-valued matrix, the value of the element in ith row and jth column denote profit of the jth task performed by the ith agent. The information for each problem is stored in a .csv file named as ASSIGN_Dim=D, where D is the number of variables D for the assignment problem.
The following search algorithms must be included:
-
hill climbing,
-
genetic algorithm, and
-
try to modify above or existing search algorithms.
Separate your implementation into different files. Output the solution to result.txt file, which should include an integer vector separated by space.
Analysis
Compare the performance of above methods in terms of 1. profits,
-
#evaluations, and
-
running time.
The maximum number of evaluations used in the search algorithms is
𝐷3.
Describe your design and discuss your findings in this assignment.
Requirement
-
Write your program in C or C++. You will get no score if you use other programming languages. Team members can share codes but should take responsibility to check it.
-
Students should write report on your own without sharing to others including team members.
-
You have to turn in your source code and a report for the assignment. Do not turn in executable files. You will get zero score if the code
cannot be compiled or cannot provide correct results.
-
Upload your files in a zip file in the format: AS_StudentID.zip, where
StudentID is your student ID.
-
The due date is 2024/06/19. You will get zero score for any delay.
-
Plagiarism is prohibited with no exception. Being identified as
plagiarism will get zero score for the assignment. This includes using any nature language processing techniques such as ChatGPT or GPT- 4.
