Computer system using genetic optimization techniques

• US 5,761,381 A
• Filed: 09/01/1996
• Issued: 06/02/1998
• Est. Priority Date: 08/31/1995
• Status: Expired due to Term

• Current Assignee: International Computers Limited (Fujitsu Limited)
• Original Assignee: International Computers Limited (Fujitsu Limited)
• Inventors: Arci, Francesco Davide Luigi, Jamieson, Maurice Carnduff, Shuttleworth, Mark Andrew
• Primary Examiner(s): Hafiz, Tariq R.
• Application Number:
  US08/691,297
• Time in Patent Office: 639 Days
• Field of Search: 395/13, 395/11, 395/21, 395/22
• US Class Current: 706/13
• CPC Class Codes: G06N 3/086 using evolutionary algorithms, e.g. genetic algorithms or genetic programming
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

A computer system comprises at least one genetic optimization agent holding a pool of genotypes, representing possible solutions to a problem. The genetic optimization agent generates new genotypes from the pool, evaluates the new genotypes according to predetermined fitness criteria, and selects the fittest of the genotypes to form a new generation of genotypes in the pool. The system also includes a number of further agents, for generating further solutions to the problem, using different techniques, such as simulated annealing, constraint logic, and neural networks. These further solutions are also represented by genotypes. The genetic optimization agent imports genotypes from the further agents and adds them to its pool of genotypes for breeding and selection. The genetic optimization agent thus provides a way of integrating a number of different problem-solving agents, in such a way as to achieve synergy between them.

Claims

1. A computer system for solving an optimization problem, the system comprising at least first and second optimization agents, and a message passing mechanism, connected to said optimization agents, for passing messages between said optimization agents;

wherein said first optimization agent comprises means for using a non-genetic optimization technique to generate, independently of said second optimization agent, genotypes representing solutions to said problem;

and wherein said second optimization agent comprises;

(a) means for storing a pool of genotypes, representing solutions to said problem;

(b) breeding means, coupled to said pool of genotypes, for generating new genotypes from said pool of genotypes;

(c) means, coupled to said breeding means, for evaluating said new genotypes according to predetermined fitness criteria, and for selecting fittest of said new genotypes, to form a new generation of genotypes in said pool; and

(d) importing means, coupled to said breeding means, for importing genotypes from said first optimization agent, by way of said message passing mechanism and adding them to said pool of genotypes.

2. A system according to claim 1 wherein said first optimization agent comprises one of the following:

(a) a simulated annealing agent,

(b) a constraint logic agent, and

(c) a neural network agent.

3. A system according to claim 1, further including a manual optimization agent comprising:

(a) means for importing a selected genotype from one of said optimization agents, by way of said message passing mechanism; and

(b) means for allowing a user to manipulate said selected genotype to generate a modified genotype;

and wherein said second optimization agent comprises means for importing said modified genotype from said manual optimization agent, by way of said message passing mechanism, and adding it to said pool of genotypes.

4. A system according to claim 1 wherein said breeding means comprises:

(a) a plurality of operators for operating on existing genotypes in said pool to produce new genotypes;

(b) means for allocating a weighting value to each of said operators;

(c) means for selecting said operators for use, with probabilities determined by the weighting values of said operators; and

(d) means for adjusting said weighting values by increasing the weighting values of operators that have produced fitter genotypes and decreasing the weighting values of operators that have produced less fit genotypes.