EEE472 Lab 02 -Genetic Algorithm Solution

Suppose, you have a run-predictor for cricket matches and the predictor can predict the target run for batting innings. Now you need to find out the match-winning combination of batsmen for your favorite team given the average runs of different batsmen. You need to find out a combination of batsmen where the total of average runs equals exactly the runs predicted as the target score by the predictor.
The input contains the number of batsmen available, the target run predicted by the predictor, and the names and average runs of the respective batsman.
Assume, the predictor predicted 300 runs as the target and there are 7 batsmen in your favorite team with their corresponding average scores, you need to find out the binary combination (1 denoting batsman selected, 0 denotes batsman not selected) of those 7 batsmen in order to find the winning combination.

Your task is to use a genetic algorithm to solve this Run-Chase problem.

Task Breakdown:

a) Model the selected batsman array in a way suitable for the problem.
b) Write a fitness function. Hint: It is the sum of the total runs of the selected batsmen.
c) Write the crossover function.
d) Write the mutation function.
e) Create a population of randomly generated selected-batsman-array.
f) Run genetic algorithms on the population until the highest fitness has been reached and/or the number of maximum iterations has been reached.


Input:
The first line has a number N and T denoting the number of batsmen available and target score respectively followed by N lines each starting with the batsman's name and a number R denoting the average run of the batsman. Here:
N (1 ≤ N ≤ 18)
T (1 ≤ T ≤ 1000)
R (1 ≤ R ≤ 401)

Output:
The output contains a list of all the players and the following row contains a binary string denoting 1 for the selected batsmen and 0 for the not selected batsmen where average runs of selected batsmen sums up equal to the target or -1 if such a string cannot be formed.

Examples:
Sample Input 1
8 330
Tamim 68
Shoumyo 25
Shakib 70
Afif 53
Mushfiq 71
Liton 55
Mahmudullah 66
Shanto 29
Sample Output 1
['Tamim', 'Shoumyo', 'Shakib', 'Afif', 'Mushfiq', 'Liton', 'Mahmudullah', 'Shanto'] 10101110
Explanation: Here, the sum of the average runs of Tamim, Shakib, Mushfiq, Liton and Mahmudullah adds up to 68+70+71+55+66 = 330.

Sample Input 2
5 240 Bradman 120
Tendulkar 90
Sangakkara 70
Kallis 65
Lara 80
Sample Output 2
['Bradman', 'Tendulkar', 'Sangakkara', 'Kallis', 'Lara']
01101


Sample Input 3
4 100
Ralph 80
John 70
Tom 40
Sample Output 3
-1