Distributed genetic programming

• US 5,930,780 A
• Filed: 02/27/1997
• Issued: 07/27/1999
• Est. Priority Date: 08/22/1996
• Status: Expired due to Term

• Current Assignee: Pendragon Networks LLC (Pendrell Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Hughes, Jeremy Peter James, Ruprai, Bahadar Singh
• Primary Examiner(s): Hafiz, Tariq R.
• Assistant Examiner(s): Rhodes, Jason W.
• Application Number:
  US08/810,957
• Time in Patent Office: 880 Days
• Field of Search: 395/13, 706/13, 706/10
• US Class Current: 706/13
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming
• CPC Class Codes: H04L 67/01 Protocols
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 67/12 specially adapted for proprietary or special-purpose networking environments, e.g. medical networks, sensor networks, networks in vehicles or remote metering networks
• CPC Class Codes: H04L 67/34 involving the movement of software or configuration parameters network booting or remote initial program loading [RIPL] G06F9/4416
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A method is described for performing distributed genetic programming using a server and a plurality of client machines which are connected together by a computer network such as the Internet. The genetic programming seeks to optimise a population of individuals against one or more predetermined fitness criteria. The method includes downloading instructions for performing a fitness evaluation on an individual from the server to the client machines; distributing individuals from the population of individuals from the server across the plurality of client machines; and evaluating the fitness of the distributed individuals at the client machines by using the downloaded instructions. Those individuals which have the best fitness are preferentially selected for breeding to produce the next generation of individuals. This breeding is preferably also performed on the client machines.

Claims

1. A method of performing distributed genetic programming using a server and a plurality of client machines, the server and the client machines being connected via a computer network, said genetic programming aiming to optimise a population of individuals against one or more predetermined fitness criteria, each individual being represented by an object including computer code instructions to evaluate fitness of the individual, wherein the computer code instructions may be invoked by calling a method of the object,

said method for performing distributed genetic programming including the steps of:

requesting individuals from the server by said client machines;

responsive to said requesting step, distributing individuals from said population of individuals from the server across said plurality of client machines by downloading objects representing the individuals from the server to the corresponding requesting client machines;

evaluating the fitness of each distributed individual at a client machine by calling said method in said object to invoke said computer code instructions; and

identifying the individual(s) best satisfying said one or more predetermined fitness criteria, based on results of said evaluating step.

2. The method of claim 1, where each of said plurality of client machines runs a Worldwide Web browser, and said instructions are downloaded in the form of an applet to be run by said browser.

3. The method of claim 2, wherein each of said plurality of client machines has a virtual machine for running said applet.

4. The method of claim 3, where the applet comprises Java byte codes.

5. The method of claim 4, where said computer network is the Internet.

6. The method of claim 1 or 2, further comprising the step of using the individuals evaluated as having the best fitness to produce a new generation of individuals.

7. The method of claim 6, further comprising the step of returning the new generation of individuals to the server.

8. The method of claim 6, further comprising an initial step of creating the first generation of individuals at said plurality of client machines.

9. The method of claim 8, wherein each of said plurality of client machines can commence or terminate their participation in the genetic programming at any time.

10. The method of claim 6, wherein each of said plurality of client machines can commence or terminate their participation in the genetic programming at any time.

11. The method of claims 1 or 2, further comprising an initial step of creating the first generation of individuals at said plurality of client machines.

12. The method of claims 1 or 2, wherein each of said plurality of client machines can commence or terminate their participation in the genetic programming at any time.

13. A system for performing distributed genetic programming using a server and a plurality of client machines, the server and the client machines being connected via a computer network, said genetic programming aiming to optimise a population of individuals against one or more predetermined fitness criteria, each individual being represented by an object including computer code instructions to evaluate the fitness of the individual, wherein the computer code instructions may be invoked by calling a method on the object, the system including:

means in the client machines for requesting individuals from the server;

means in the server responsive to requests from the client machines for distributing individuals from said population of individuals from the server across said plurality of client machines by downloading objects representing the individuals from the server to the corresponding requesting client machines;

means for evaluating the fitness of each distributed individual at a client machine by calling said method in said object to invoke said computer code instructions; and

means for identifying the individual(s) best satisfying said one or more predetermined fitness criteria, based on the results of their fitness evaluations.