Untangling Mathematical Knots with Simulated Annealing and Opposition-Based Learning

The fundamental problem in knot theory is to determine whether a given knot is an unknot. Solving such problem with existing computational algorithms or heuristic methods still remains challenging. In this paper we describe a hybrid algorithm that employs simulated annealing (SA) algorithm and opposition based learning strategy to simplify and accelerate the simulation of mathematical knot relaxation. In our work, mathematical knots are modeled as closed node-link diagrams with energies charged at each node. A mathematical force model with adaptive step sizes is incorporated into SA for new individual generation. One elementary move with a descending number of nodes is included to prune the conformation and reduce the redundant information following the isotopy consistency. However, the force directed model may be trapped to a local energy minimum. To overcome such intrinsic limitation, we adopt an opposition force based learning strategy to tackle this problem. With a flexible neighborhood and the instructive disturbance information, the knot geometry is able to untangle quickly and can reach the global minimum state without extra intervention. Illustrative test cases are presented, including three unknots and two classical knots with complex isotopy.