CA2 Evolutionary Computation

CA2 Continuous Assignment - Evolutionary Computation 2022

1. Average and maximum path length of graphs.

(a) Calculate the average pathlength of the following graphs (with N vertices): line, ring, star, fully connected graph. Show all your reasoning. (You may restrict to odd or even N where convenient.) Marks: 2

(b) Identify which of these scale with N as O(1),O(N),O(N2). Use mathematical definition of the large O notation. Marks: 1

(c) State the diameter (maximal path length) of the above graphs (a hand-written sketch of a largest path is acceptable). Marks: 1

2. Use the adjacency matrix (or the link list) to represent graphs G with N nodes, and implement (and test, e.g. on examples from above) the following operations: Marks: 3

(a) Calculate the average path length =: f1(G)

(b) Calculate the diameter (maximal path length) =: f2(G) (c1) Calculate total number of links =: f3(G)

(c2) Check that G is connected

You may use libraries, but would need to demonstrate their correct working, e.g., on one connected and one not connected graph, for question (c2).

3. Network Mutation Operators. Implement the following operations: Marks: 3

(a) Add a link at a randomly chosen position (between two randomly chosen links). You will need to check the link was absent before, and eventually handle the case of a fully connected graph.

(b) Remove a randomly chosen link, provided that the graph stays connected.

(c) Random rewiring (a combination of above)

4. Evolutionary Algorithm:

(a) Implement an evolutionary agorithm that uses (with probabilities p1, p2, p3 = 1 ? p1 ?p2) the above mutation operators, using some fitness function(s) to be specified. Marks: 2

(b) Test the algorithm on maximizing f2(G) ? f1(G), i.e., finding a graph (of fixed size N) with largest difference between maximal and average path length. Choose a graph size 7 ≤ N ≤ 20 and display the graph (and f1, f2, f2 ? f1) for the three best graphs.

Marks: 2

(c) Comment on your results: were they as expected, and why? Marks: 1

5. From single to multiobjective optimization: Transportation networks. We assume dis- tances (travel times, costs) of each link to be equal and of value 1. Further, we assume revenue from tickets is independent of distance (or no revenue, if public transport is free). Further:

Assume transportation costs are per link, then the total cost is proportional to f1.

Assume network maintenance costs are proportional to the total number of links f3.

Assume complaint+refund cost sare proportional to the maximal path length f2.

(a) Use a linearly weighted fitness a1f1 + a2f2 + a3f3 =: fw and mimimize fw for three qualitatively different choices of the weights.

Display your results in a meaningful way and comment on your results. Marks: 3

(b) Implement a multiobjective evolutionary algorithm (of your choice), and aim at minimizing each of the three costs.

Display the 10 best solutions, projected on the (f1, f2), (f1, f3), (f2, f3) planes, and a table of their f1, f2, f3 values. Marks: 5

6. Challenge question (choose one of the following) Marks: 2

(a) The resulting networks may be unrealistic due to oversimplified assumptions. Try to define and optimize a modified fitness function and discuss your results.

(b) Calculate (and try to sketch / plot as a function of p) the expected values of f1, f2, f3, fw for a (N, p) random graph (you may use and properly cite results from the literature). Comment on the shape or fw(p) and what we learn from this about our problem.

Please submit on Canvas:

A self-contained report (pdf) with all results and comments / discussion (Note: you may prefer to include a scan of a handwritten solution of question 1).

A separage appendix file containing all of your code in a text file (txt, doc,, docx, or pdf).

A zip, tar or tgz or tar.gz file of your code (program text files preferred over notebook

files).

You may use matlab, java, c/c++, python or other common languages, but should include instructions to run the code or any other documention where appropriate. (In rare cases, you may be asked to demonstrate working of your code online.)

Overall 25 marks. - Late penalty: 5% per working day (for each of up to 5 working days).

 WX：codehelp