Asynchronous organizations for multi-algorithm problems
Pedro S. de Souza, Sarosh Talukdar · 1993
A Multi-Algorithm Problem (MAP) is a problem with many approximate algorithms available to solve it. Examples of MAPs are most of the combinatorial optimization problems and the multi-criterion problems with conflicting objectives. Since a MAP has no single algorithm able to solve it optimally in reasonable time, and each available algorithm for a MAP has its own approach to solving a problem, there exists the possibility of combining these algorithms in order to take advantage of their strengths. This thesis demonstrates that by using an Asynchronous Team, a software organization characterized by cyclic, iterative data flow and autonomous agents which communicate asynchronously through shared memories, one can synergistically combine many algorithms in order to reach better results than each algorithm can do by itself. As an example of a MAP, we chose the Euclidean version of the Traveling Salesman Problem (TSP), which is a difficult combinatorial problem and has many heuristic algorithms that only provide approximate solutions for it. Asynchronous Teams with a few algorithms were able to reach optimal solutions for all the TSP instances tackled whereas, individual algorithms could not. Moreover, parallel execution of Asynchronous Teams on a computer network presented linear speed up. We also observed that Asynchronous Teams for solving TSP are scale efficient; that is, the more algorithms an Asynchronous Team uses, the better it performs. We tested and analyzed several design parameters for Asynchronous Teams such as selection and destruction policies (how agents select and destroy data from shared memories,) initialization policies (how to initiate shared memories,) memory sizes, and the influence of data flows on the performance of Asynchronous Teams. We also present some specially developed algorithms to be exclusively executed in Asynchronous Teams. Finally, we present a Markov-based model that not only explains the behavior, but also helps in designing Asynchronous Teams by giving insights about expected value of final solutions, optimal relative execution frequencies of algorithms, and convergence of Asynchronous Teams.