Software Agents and Optimisation (6G6Z1109_1718_9Z6)Term 2: Lab 7In the lecture, we talked through the circle placement algorithm; given an ordered set of circles, this simply places each circle, one-by-one (in the order in which they are specified) in the space, in such a way that (a) no circles overlap, and (b) when each circle is placed, it is located at the open point that is closest to the centre of the space.Task 1: Get the circle placement algorithm running in Processing, using the code provided on Moodle.The initial placement for the two circles should give a containing radius of 120. Now try it with the set of circles with radii {10,40,25,15,18}.Notice the placement of the circles; why do you think circle 1 is specifically placed where it is, directly to the right of circle 0? Why not above it, or to the left?Notice the summed open points (for all circles) drawn in green.Task 2: Ensure you understand how the Bunch class works; this simply represents and draws a number of Circle objects. It also contains the OrderedPlace() method, which places the circles in order.Extend this class by adding a GreedyPlace()method. What might such an algorithm look like? Imagine a bunch of differently-sized circles – what, intuitively, would be the best approach to packing them?Test your greedy algorithm with same circle set as in Task 1. You should get a containing radius that is also 90.
Task 3: Once you have both algorithms working, you are ready to integrate a GeneticPlace() method into the Bunch class. This contains the “controller” of the genetic algorithm used to place each circle. You should based this on the code already supplied for the Travelling Salesman Problem. Test your GA on the test set from Task 2. Does it out-perform the greedy algorithm? (Hint: it should).Important: in your write-up, you should give results for both of the circle sets specified above, plus the following two circle sets (for which I will not supply a known optimum…)Test set A: {10,12,15,20,21,30,30,30,50,40}Test set B: {10,34,10,55,30,14,70,14,50,16,23,76,34,10,12,15,16,11,48,20}For all four sets, give full results for each of the three algorithms (including diagrams).
Software Agents and Optimisation (6G6Z1109_1718_9Z6) Term 2: Lab 6We saw, in the lecture, how ordered crossover can be used to retain the correctness of permutations when combined.Your task this week is to implement the ordered crossover operator.The pseudo-code for this is as follows:OrderedCrossover(Parent1, Parent2)Create blank child genome, with length equal to that of the parents Select random subset, s, of Parent1 genomeCopy s into child genome (retaining positions of genes)Loop for length of Parent2 genome:a. Calculate position, p, of gene to copy (copying starts one position after the end of s, and loops to beginning of genome, if necessary)b. Copy gene, g, at position p in Parent2 genomec. If g is not already in child genome, find the first available positionin child genome, and insert g at that pointReturn child genome
-
Implement the class OrderedCrossover, and integrate it into the TSP code supplied (I have supplied a stub file to start you off).
-
Test the code to ensure that it works correctly, by crossing over two known genomes and then ensuring that the child is valid (just print it to the console).