22222

[zangshichao]

2222222

[fakinormal]

i see

[zangshichao]

1 COMBINATORIAL OPTIMIZATION (ANT-COLONY ALGORITHM) The pure ant-colony optimization (ACO) algorithm applied to the traveling salesman problem (TSP) often leads to a solution that shows path crossings. Even though this solution is not optimal, the algorithm does not seem to “untangle” the path into a path of smaller length. In this exercise, we want to design and implement an additional feature into the ACOalgorithm to check for non-optimal path crossings and force the “untangling” of these situations. This is referred to as a local-search procedure. In essence, we are looking for configurations where two separated segments of the current path cross each other (see figure 1.1a for an illustration). In this configuration, the path segment (a − b) is crossing the path-segment (c−d). To untangle the path we need to connect node a to node c and node b to node d. When performing this operation, we need to realize that we also have to reverse the original order of the path from b to c, since – after the operation – c is now connected to b, not the other way around. The complete swap is given in the two boxes in figure 1.1. In the literature, this operation is referred to as the 2-opt operation. In an implementation of this operation, we need to search for a situation where path segments cross. This is best accomplished by computing the lengths L1,...,4 as illustrated in figure 1.2. If L3 + L4 is less than L1 + L2 we reduce the overall length of the path by untangling the crossing, according to the procedure above. 1.1 EXERCISE 1 Design and implement a python-function that searches a given path for cr