A distributed multi-agent system approach for solving constrained optimization problems using probability collectives - Anand Jayant Kulkarni (2012)
Complex systems generally have many components and it is difficult to understand the whole system only by knowing each component and its individual behavior. This is because any move by a component affects the further decisions/moves by the other components and so on. As the number of components grows, complexity may grow exponentially, making the entire system too cumbersome to be treated in a centralized way. The best option to deal with such a system is to decompose it into a number of sub-systems and treat it as a collection of sub-systems or a Multi-Agent System (MAS). The major challenge is to make these agents work in a coordinated way, optimizing their local goals and contributing the maximum towards optimization of the global objective. The theory of Collective Intelligence (COIN) using the distributed, decentralized, multi-agent optimization approach referred to as Probability Collectives (PC) is presented in this thesis. In PC, the self-interested agents optimize their local goals which contribute in optimizing the global goal. In the current work, the original PC approach is modified by reducing the computational complexity and improving the convergence and efficiency. In order to further extend the PC approach and make it more generic and powerful, a number of constraint handling techniques are incorporated into the overall framework to develop the capability for solving constrained problems since real-world practical problems are inevitably constrained problems. In the course of these modifications, various inherent characteristics of the PC methodology are thoroughly explored, investigated and validated. The thesis demonstrated the validation of the modified PC approach by successfully optimizing the Rosenbrock Function. The first constrained PC approach exploits various problem specific heuristics for successfully solving two test cases of the Multi-Depot Multiple Traveling Salesmen Problem (MDMTSP) and several cases of the Single Depot MTSP (SDMTSP).