Study of parallel distributed schemes for combinatorial optimization.

Abstract

This thesis is concerned with Parallel Distributed Optimization techniques for solving Combinatorial Optimization (CO) problems. Given a finite set of configurations and a cost function over them, a CO problem requires that the configuration with minimum cost be found. These are hard problems (most of them belong to the class of NP-Complete problems) and so finding the solution just by pure search requires a large computation time. The traditional approach of heuristic algorithms for finding a suboptimal solution to a CO problem is mostly problem-dependent. In contrast, the Parallel Distributed Processing (PDP) models considered in this thesis are potentially general techniques for solving CO problems. The Connectionist or PDP models are concerned with the study and simulation of the cognitive aspects of brain behaviour. Any PDP model has the following structural features: (i) a large number of simple interacting units (ii) an interconnection weight between any two units (iii) local interactions among units through which the system evolves to a global steady state. The units take values in an appropriate state space. The state of the system as a whole is a vector with the states of these units as elements. At any instant of time, each unit interacts with all the units connected to it and the strength of interactions depends on the interconnection weights. These interactions alter the state of each of the units until the system settles down to a steady state. The dynamics of the system and the properties of stable states are studied by defining an energy function over the state space. This thesis studies the Hopfield and the Learning Automata models for solving CO problems. While the Hopfield model has been studied previously, the Learning Automata model is a contribution of this thesis. A CO problem is solved by appropriately coding the problem into the network structure so that the set of configurations of the problem is a subset of the state space of the system and the energy of a state representing a configuration is equal to its cost. Since stable states are local optima of the energy function, the network finds a local optimum (in an appropriate sense) of the CO problem by converging to a stable state. This thesis is concerned with the nature of solutions thus found. In particular, the drawbacks of a simple coding procedure (as used in earlier studies of the Hopfield model) are brought out. A novel LA scheme which overcomes these drawbacks to a good extent is presented. For each of the models considered, two problems, namely, the Travelling Salesman Problem (TSP) and the Placement Problem in VLSI design, are solved as examples.

Chapter 1 introduces CO problems and the methods adopted to solve them. An overview of PDP models is presented and the steps needed for solving CO problems are explained. A summary of the main contents of the thesis is also provided. Chapter 2 is an in-depth study of the Hopfield model. The process by which TSP is normally coded into the network is worked out in detail and the nature of the solutions obtained by such a coding is studied. The main contribution of this chapter is a precise characterisation of the stable states of the network under some general conditions on the parameters used in the energy function. This characterisation brings out the main drawbacks of the Hopfield network, namely, all configurations become stable states of the system. Chapter 3 introduces the Learning Automata model and the necessary transformations for coding a general CO problem into the Learning Automata framework. For TSP, the solutions that are obtained by this model are precisely characterised. Based on this, the similarities and differences with the Hopfield model are brought out. It is shown that, but for a few operational differences, the PDP nature of the two models makes them similar in all the essential characteristics. Thus, the Learning Automata model also suffers from the problem of each configuration becoming a stable state. Chapter 4 presents a grouping scheme for the LA model which is shown to reduce the set of stable states (in an appropriate sense) while retaining the instability of all the equivalent unstable states of the simple model. This feature is responsible for overcoming the main drawbacks of the simple coding schemes, thus improving the quality of solutions obtained. TSP is solved using the grouped model. Then, the placement problem in VLSI design is presented to illustrate the generality of these models. Chapter 5 concludes the thesis. Based on the characteristics of PDP models, speculations on the applicability of the results in the thesis to any PDP model in general are drawn. The practical issues involved in solving a CO problem using the PDP models considered are discussed.

The simulation results of both the problems considered, solved using all the models in the thesis, are presented in the appendix.