A sociologically inspired heuristic for optimization algorithms: A case study on ant systems

摘要

This paper discusses how social network theory can provide optimization algorithms with social heuristics. The foundations of this approach were used in the SAnt-Q (Social Ant-Q) algorithm, which combines theory from different fields to build social structures for state-space search, in terms of the ways that interactions between states occur and reinforcements are generated. Social measures are therefore used as a heuristic to guide exploration and approximation processes. Trial and error optimization techniques are based on reinforcements and are often used to improve behavior and coordination between individuals in a multi-agent system, although without guarantees of convergence in the short term. Experiments show that identifying different social behavior within the social structure that incorporates patterns of occurrence between states explored helps to improve ant coordination and optimization process within Ant-Q and SAnt-Q, giving better results that are statistically significant.