#include #include #include #include #include #include // The rows correspond to students, A to M (13 students). // The columns would signfiy task 0 to 9 (10 tasks). // jobs[0][0] would mean student A takes 34 minutes to complete task 0 // jobs[1][2] would mean student B takes 22 minutes to complete task 2 // ... and so on. // Each task should be completed by at least one student. // Would you be able to find out the mininum time needed to fulfill this condition? int jobs[13][10] = {{34,31,20,27,24,24,18,33,35,19}, {14,14,22,34,26,19,22,29,22,19}, {22,16,21,27,35,25,30,22,23,23}, {17,21,24,16,31,22,20,27,26,17}, {17,29,22,31,18,19,26,24,25,14}, {26,29,37,34,37,20,21,25,27,27}, {30,28,37,28,29,23,19,33,30,21}, {28,21,30,24,35,20,24,24,32,24}, {19,18,19,28,28,27,26,32,23,22}, {30,22,29,19,30,29,29,21,20,18}, {29,25,35,29,27,18,30,28,19,23}, {15,19,19,33,22,24,25,31,33,21}, {27,32,27,29,29,21,19,25,20,27}}; // To find a feasible and acceptable/optimal solution to this task, // we have to decide how to encode the chromosome. // In my implementation, a string containing 13 characters ranging from digit 0-9 would be a chromosome. // e.g. 2314658970321 would mean Student A for job 0, Student B for job 3, Student C for job 1, and so on. // The fitness function, used to calculate the fitness of a chromosome. // In this case, lower fitness value = "better", since it represents less time taken to complete the tasks. int calculate_weight(std::string str) { int weight = 0; for (int i = 0; i < 13; i++) weight += jobs[i][str[i]-48]; return weight; } // Function to check if the population already contains the same chromosome bool contains(std::vector obj, std::string str) { for (std::string i : obj) if (i == str) return true; return false; } // Function required for std::sort to work on sorting chromosomes, based on their fitness value. struct gene_compare { bool operator() (std::string str1, std::string str2) { return (calculate_weight(str1) < calculate_weight(str2)); } } gene_comp_obj; // Function responsible for producing two new chromosome configurations from two existing chromosomes. // Google search : Two point crossover. // Special procedures are taken to make sure that the children chromosomes are feasible, // i.e. Fulfills the condition that each job is completed by at least one student. std::vector crossover(std::string str1, std::string str2) { std::string t1 = str1.substr(4,5), t2 = str2.substr(4,5); std::string c1 = str1.substr(9,4) + str1.substr(0,9); std::string c2 = str2.substr(9,4) + str2.substr(0,9); for (char i : t2) c1 = std::regex_replace(c1, std::regex(std::string(1,i)), "", std::regex_constants::format_first_only); for (char i : t1) c2 = std::regex_replace(c2, std::regex(std::string(1,i)), "", std::regex_constants::format_first_only); return {c1.substr(0,4)+t2+c1.substr(4,4), c2.substr(0,4)+t1+c2.substr(4,4)}; } // Function responsible for mutation, i.e. swapping two genes within the same chromosome to produce a new chromosome. void mutate(std::string& str) { int v1 = rand()%13, v2 = rand()%13; if (jobs[v1][str[v1]-48]+jobs[v2][str[v2]-48] > jobs[v1][str[v2]-48]+jobs[v2][str[v1]-48]) std::swap(str[v1],str[v2]); } int main() { srand(time(0)); // My initial population / solution space // This contains a 100 chromosomes, if I'm not mistaken std::vector population = {"4108237569689", "8714365029479", "4370812659167", "2147063589235", "8403176259016", "0762135489279", "2861034759459", "2734560189138", "1876402359469", "0354782169349", "3764815029024", "4165387029157", "6042358179137", "2485367109017", "6053421879146", "4506283179134", "6208375419019", "2345716809016", "2130754689015", "7865034219368", "6503247819239", "3725108649157", "4312758069139", "0453718269256", "2710384659039", "8640725139046", "2834610759037", "8172504369256", "0513842769047", "0874561239257", "4805372169126", "3871405269136", "2386751409134", "1586342079057", "1726450839028", "6801357429014", "1673428059269", "7641835029237", "2746830159012", "7560831249019", "5042716839369", "7681504239189", "1720453689035", "2476015389345", "3051264789146", "6084735129246", "6254170839267", "5014632789068", "3541027869126", "0841527639238", "0261483759013", "4217308569135", "3851402769568", "6827051349078", "3241857069169", "5372406819017", "5204378169058", "3412785609346", "6012854379389", "3017265489013", "0531482679189", "4678531029134", "7630842519046", "7805426319046", "8135274069129", "7304168529014", "4357602819039", "4852716309078", "6270145389047", "0176823549169", "4517082369148", "3601827459159", "7824065139789", "2830541769467", "1768245039159", "7354061829369", "6854017239018", "8524376019078", "8034716259489", "0135472689026", "0687235149678", "3678104259126", "6423058719034", "8614052739089", "4670835129126", "0132876459247", "8104265739568", "4685320719289", "5730264819139", "1053248679035", "0132687549579", "3756421089018", "5473108629456", "6540123789045", "5627384019249", "7421358609249", "6140752389169", "8241736059047", "5623780149023"}; std::sort(population.begin(), population.end(), gene_comp_obj); std::cout << "Initial best : " << population[0] << " of cost " << calculate_weight(population[0]) << "\n"; for (int i = 0; i < 500; i++) { // Here, we attempt to select chromosomes of better fitness to crossover with the rest of the population // to properly explore the solution space. for (std::string j : crossover(population[rand()%5], population[5+rand()%94])) { if (!contains(population, j)) population.push_back(j); } // add in a 0.05% chance for mutation to happen on the best chromosome if (!(rand() % 20)) mutate(population[0]); std::sort(population.begin(), population.end(), gene_comp_obj); // Make sure that the population is sorted // Resizing the population will remove the chromosomes of poor fitness if (population.size() > 99) population.resize(100); } std::cout << "After 500 generations : " << population[0] << " of cost " << calculate_weight(population[0]); }

Genetic Algorithm (Task Assignment Problem)