Patent ID: 6912207
Filing Date: 2005-06-28
Classification: G06N,H04L

Abstract:
1. A network topology design apparatus for designing a network topology connecting a plurality of points by communication lines by adopting a genetic algorithm so that a predetermined traffic volume can be transmitted between the plurality of points, comprising: chromosome creation means for randomly creating a predetermined number of early generation chromosomes representing presence or absence of connection between the respective points in said network topology in two-dimensional matrix; communication path determination means for determining a communication path between the respective points by applying the solution of a shortest path problem to each network topology represented by the chromosome; line capacity determination means for, based on the communication path determined by said communication path determination means and the predetermined traffic volume, determining the capacity of each communication line connecting the points; adaptability calculation means for, based on the capacity of each communication line determined by said line capacity determination means, computing adaptability that is inversely proportional to communication cost; chromosome evolution means for, based on the adaptability computed by said adaptability calculation means, evolving sequentially the predetermined number of chromosomes to the next generation chromosomes; generation judgment means for judging whether or not the generation of the chromosome evolved by said chromosome evolution means has reached a predetermined generation; and first control means for, when it is judged by said generation judgment means that the generation has not yet reached the predetermined generation, repeating the processing of said communication path determination means and the subsequent means, and when judged that the generation has reached the predetermined generation, for outputting the chromosome with the highest adaptability among the predetermined number of chromosomes.