Network topology design apparatus and network topology design method, and recording medium recorded with a network topology design program

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 among the plurality of points, comprising:

• chromosome evolution means for sequentially evolving a predetermined number of chromosomes representing the network topology in a matrix to the next generation chromosomes by adopting the genetic algorithm;
• uniformity computing means comparing each chromosome evolved to the next generation by said chromosome evolution means with the chromosome having the lowest communication cost of the same generation and for computing uniform which is the rate at which the elements of the matrix comprising the chromosomes are matched;
• and
• second control means for, when the uniformity computed by said uniformity computing means is less than a predetermined value, evolving the chromosome to the next generation by the chromosome evolution means, and when the uniformity becomes greater than or equal to the predetermined value, outputting the chromosome having the lowest communication cost among the predetermined number of chromosomes.

A network topology design apparatus for designing a network topology connecting a plurality of points by communication lines by a genetic algorithm, comprising:

• traffic volume input means for inputting data regarding the traffic volume among the plurality of points;
• cost information input means for inputting data regarding the capacity and cost of the communication lines;
• and
• line capacity determination means for determining the capacity of the communication lines the respective points, based on data regarding the traffic volume among the plurality of points input by said traffic volume input means, and data regarding the capacity and cost of the communication lines input by said cost information input means.

A network topology design method of 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:

• a chromosome creation step of randomly creating a predetermined number of initial generation chromosomes representing the network topology in a matrix;
• a communication path determination step of 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;
• a line capacity determination step of, based on the communication path determined by said communication path determination step and the predetermined traffic volume, determining the capacity of each communication line connecting the points;
• a fitness calculation step of, based on the capacity of each communication line determined by said line capacity determination Step, computing fitness that is inversely proportional to communication cost;
• a chromosome evolution step of, based on the fitness computed by said fitness computing step, evolving sequentially the predetermined number of chromosomes to the net generation chromosomes;
• a generation judgment step of judging whether or not the generation of the chromosome evolved by said chromosome evolution step has reached a predetermined generation;
• and
• a control step of, when it is judged by said generation judgment step that the generation has not yet reached the predetermined generation, repeating the processing of said communication path determination step and the subsequent steps, and when judged that the generation has reached the predetermined generation, for outputting the chromosome with the highest fitness among the predetermined number of chromosomes.

A recording medium recorded with a network topology design program 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 among the plurality of points, realizing:

• a chromosome creation function for randomly creating a predetermined number of initial generation chromosomes representing the network topology in a matrix;
• a communication path determination function 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;
• a line capacity determination function for, based on the communication path determined by said communication path determination function and the predetermined traffic volume, determining the capacity of each communication line connecting the points;
• a fitness calculation function for, based on the capacity of each communication line determined by said line capacity determination function, computing fitness that is inversely proportional to communication cost;
• a chromosome evolution function for, based on the fitness computed by said fitness computing function, evolving sequentially the predetermined number of chromosomes to the next generation chromosomes;
• a generation judgment function for judging whether or not the generation of the chromosome evolved by said chromosome evolution function has reached a predetermined generation;
• and
• a control function for, when it is judged by said generation judgment function that the generation has not yet reached the predetermined generation, repeating the processing of said communication path determination function and the subsequent functions, and when judged that the generation has reached the predetermined generation, for outputting the chromosome with the highest fitness among the predetermined number of chromosomes.

A recording medium recorded with a network topology design program for designing a network topology connecting a plurality of points by communication fines by a genetic algorithm, realizing:

• a traffic volume input function for inputting data regarding the traffic volume among the plurality of points;
• a cost information input function for inputting data regarding the capacity and cost of the communication lines;
• and
• a line capacity determination function for determining the capacity of the communication lines between the respective points, based on data regarding the traffic volume among the plurality of points input by said traffic volume input function, and data regarding the capacity and cost of the communication lines input by said cost information input function.