A GA-based solution to the migration problem of mobile agents in distributed information retrieval systems

摘要

The migration problem (MP) of mobile agents is an important, NP-hard problem in distributed information retrieval systems built upon mobile agent technology. MP aims at optimizing the migration paths of agents for minimizing total communication cost within a user-specified limit of task completion time. In this paper we first show MP is equivalent to searching for an optimal migration tree. We then employ genetic algorithms to address MP, proposing a new encoding scheme to represent the migration trees, which is compose of two parts: one is the pre-ordered traversal sequence of tree vertices, the other the children number sequence of corresponding tree vertices. Our encoding scheme has the advantages of simplicity for encoding and decoding, ease for GA operations, an better equilibrium between exploration and exploitation. This encoding scheme, with few restrictions on the length of code, can be freely lengthened or shortened according to the characteristics of problem space. We can benefit much from such an adaptive property. The simulation results reveal the efficiency and higher performance of our algorithm, and fast convergence to the optima or sub-optima on various problem sizes. Our algorithm runs nearly 4 times faster than the binary string encoding of vertices when the problem size becomes large and the search capability is comparative or slightly better of our algorithm than the benchmark.