Method of combinatorial multimodal optimisation

• US 20050097559A1
• Filed: 03/12/2003
• Published: 05/05/2005
• Est. Priority Date: 03/12/2002
• Status: Active Grant

• Current Assignee: British Telecommunications PLC (BT Group PLC)
• Original Assignee: British Telecommunications PLC (BT Group PLC)
• Inventors: He, Liwen
• Granted Patent: US 7,593,905 B2
• Time in Patent Office: Days
• US Class Current: 718/104
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers

Abstract

A method of combinatorial multimodal optimisation uses a genetic algorithm to find simultaneous global optimal solutions to combinatorial problems. Each individual within the population is associated not only with a fitness value but with a fitness vector, using which the persistence of all of the best individuals into the next generation can be guaranteed. Phenotype as well as genotype analysis is an integral part of the method.

Claims

1. A method of combinatorial multimodal optimisation for finding multiple optimal ways of dividing a set W of n values into m groups, such that each of the groups satisfies a respective constraint condition, the method comprising:

(a) defining an initial population of individuals, each representative of a trial solution;

(b) calculating for each individual a fitness vector indicative of whether the constraint condition for each group has been satisfied;

(c) selecting a plurality of individuals for the next generation in dependence upon their respective fitness vectors;

(d) creating a new population including the selected individuals; and

(e) repeating steps (b) to (d) until the population stabilizes, the individuals of the stable population representing multiple optional ways of dividing the set W.

2. A method as claimed in claim 1 in which the fitness vector is of length m, each element in the fitness vector being indicative of whether the constraint condition of a corresponding one of the m groups has been satisfied.

3. A method as claimed in claim 2 in which the fitness vector comprises m bits, each bit being indicative of whether the constraint condition of a corresponding one of the m groups has been satisfied.

4. A method as claimed in claim 1 including calculating a fitness value for each individual.

5. A method as claimed in claim 3 including calculating a fitness value for each individual in which the fitness value comprises the sum of the bits in the fitness vector.

6. A method as claimed in claim 1 including reserving a proportion of the new population for individuals selected at step (c).

8. A method as claimed in claim 1 in which step (c) comprises selecting non-dominated individuals using the criteria of Pareto optimality.

9. A method as claimed claim 4 in which step (c) comprises selecting non-dominated individuals using the criteria of Pareto optimality including ranking non-dominated individuals by fitness value, and selecting from the ranked list.

10. A method as claimed in claim 9 in which only non-dominated individuals with greatest fitness value may be selected at step (c).

11. A method as claimed in claim 4 in which step (c) comprises selecting individuals in dependence upon both their respective fitness vectors and their respective fitness values.

12. A method as claimed in claim 1 in which crossover and mutation are applied at step (d) to at least some individuals in the new population.

13. A method as claimed in claim 1 in which step (c) comprises selecting no more than one individual for each unique fitness vector.

19. A method as claimed in claim 1 in which new allocations are formed in step (d) by performing crossover operations in respect of groups of two or more of the allocations selected in step (c).

21. A computer program for carrying out the steps of claim 1.

22. A carrier medium carrying the computer program of claim 21.

7. A method as claimed 6 in which a non-reserved proportion of the new population is generated using a Roulette wheel selection method.

14. A method of distributing a plurality of tasks between a plurality of devices connected together to form a network, wherein each device has an associated constraint on the amount of tasks that it can perform per unit of time, the method comprising:

(a) generating a plurality of trial solution allocations to form an initial population of allocations;

(b) calculating for each allocation a fitness vector indicative of whether the constraint condition for each device has been satisfied;

(c) selecting a plurality of allocations for inclusion in the next generation of allocations in dependence upon their respective fitness vectors;

(d) creating the next generation of allocations by including the allocations selected in step (c) together with new allocations each of which is formed from a combination of two or more of the allocations selected in step (c);

(e) repeating steps (b) to (d) until the population stabilizes; and

(f) allocating the tasks among the devices according to one of the allocations included in the stabilized population.

15. A method as claimed in claim 14 wherein the devices are processors within a multi-processor computer system.

16. A method as claimed in claim 14 wherein the devices are computers within a computer network.

17. A method as claimed in claim 14 wherein the devices are routers and the tasks are estimated volumes of traffic to be routed through the routers within a data network, and wherein the allocations are used to form a routing strategy.

18. A method as claimed in claim 14 in which step (c) comprises selecting non-dominated allocations using the criteria of Pareto optimality of the associated fitness vectors.

20. A method as claimed in claim 14 in which mutation operations are applied to one or more of the new allocations formed in step (d) according to a predetermined probability of each new allocation being mutated.

23. A system comprising a plurality of devices connected together to form a network, wherein each device has an associated constraint on the amount of tasks that it can perform per unit of time, the system including means for allocating a plurality of tasks among the devices, the allocation means comprising:

(a) means for generating a plurality of trial solution allocations to form an initial population of allocations;

(b) means for calculating for each allocation a fitness vector indicative of whether the constraint condition for each device has been satisfied;

(c) means for selecting a plurality of allocations for inclusion in the next generation of allocations in dependence upon their respective fitness vectors;

(d) means for creating the next generation of allocations by including the allocations selected in step (c) together with new allocations each of which is formed from a combination of two or more of the allocations selected in step (c);

(e) means for repeating steps (b) to (d) until the population stabilizes; and

(f) means for allocating the tasks among the devices according to one of the allocations included in the stabilized population.