COLOR ANT POPULATIONS ALGORITHM FOR DYNAMIC DISTRIBUTION IN SIMULATIONS

摘要

Most distributed simulations are applications composed of numerous mobile communicating entities that continuously evolve. Such entities are organized or organize themselves in groups or societies of cooperating agent or processes. To keep these simulations efficient, it may be necessary to migrate entities of highly communicating groups so that they remain close, ideally on the same processing unit, while at the same time, we need to maintain a reasonable load for each processor. We have proposed (Bertelle et al., 2002b) a method to hint migration of entities making a trade-off between communication and load-balancing based on a variant of ant algorithms. We use a dynamic communication graph to model distributed simulations where vertices represent entities and edges communications. Several colonies of ants, each of a distinct color representing a computing resource, compete to mark vertices of the graph using colored pheromones. A color change on a vertex hints the entity it represents to migrate on the corresponding processor. In some cases, the solution obtained is not satisfying. We try to show in this paper the reasons and to give improvements to solve it.