The Task Assignment Problem

Study the description of the Task Assignment problem described below and answer the questions that follow:

In a task assignment problem, each task must be performed by one person. We have $\backslash ($ t $\backslash )$ tasks and $\backslash ($ p $\backslash )$ persons. The input to the problem is a table, an example of which is shown below in Table I. The table shows how well each person $($A to M$)$ performs each task $($ I to Io $).$ The higher the number, the better the person performs the task. The solution to the problem is the assignment of persons to tasks $($one task per person$)$ that produces the best overall score.

Table i: Example Input for the Task Assignment Problem

You are required to design a solution that uses a genetic algorithm to solve the problem. The design must include sufficient detail to allow easy implementation by a junior programmer. You may assume that the table is read from a file and stored in a two$-$dimensional array$/$matrix $\backslash ($ M $\backslash ).$

I. Define the structure of the chromosomes you will use for this problem. $(4$ pts$)$

$2.$ Give an example chromosome using the structure described above. $(2$ pts$)$

$3.$ Describe, in detail, a fitness function suitable for this problem. $(3$ pts$)$

$4.$ Specify a cross$-$over operation $($suitable for this problem$)$ by giving the pseudo code of a function that takes two chromosomes $(\backslash ($ a $\backslash )$ and $\backslash ($ b $\backslash ))$ as input and returns a chromosome $\backslash ($ c $\backslash )$ that results from applying the cross$-$over operation on $\backslash ($ a $\backslash )$ and $\backslash ($ b $\backslash ).(4$ pts$)$

$5.$ Describe a mutation operation $($suitable for this problem$)$ by giving the pseudo code of a function that takes a chromosome as input and returns a chromosome that results from applying the mutation operation on $\backslash ($ a $\backslash ).(3$ pts$)$

$6.$ Describe a selection mechanism you will use to select individuals for reproduction. Explain why you would use this mechanism. $(4$ pts$)$