CECS 451
Assignment 5
Total: 40 Points
General Instruction
Submit uncompressed file(s) in the Dropbox folder via BeachBoard (Not email).
Use Python 3, any other programming language is not acceptable.
You can import modules in the Python Standard Library (please check the full list
here). If you want to use any other library, please consult with the instructor or TA.
1. (40 points) Solve the n-airports problem using gradient based optimization algorithm.
i. Find n-airports.ipynb.
ii. A random initial state is given as Figure 1a.
(a) An initial state (b) An optimal state
Figure 1: n-airports problem state
iii. The objective function is given by
f(x1, y1, x2, y2, x3, y3) = Xn
i=1
X
c∈Ci
(xi − xc)
2 + (yi − yc)
2
where n is the number of the airports and Ci
is the set of cities whose closest airport
is airport i.
iv. The goal of the program is determining the locations of airports that minimize the
objective function using gradient based optimization. By updating
(x1, y1, x2, y2, x3, y3) ← (x1, y1, x2, y2, x3, y3) − α∇f(x1, y1, x2, y2, x3, y3)
where 0 < α ≪ 1 is a constant, find an optimal location of the airports as Figure 1b.
CECS 451 Assignment 5 - Page 2 of 2
v. As shown in Figure 2, plot the objective function values at every time of updating
the locations to terminate the algorithm. (The objective values may be different
than the example.)
vi. Submit your n-airports.ipynb.
Figure 2: Objective values as a function of epoch
