Computer system and method for generating and mutating objects by iterative evolution

• US 6,088,510 A
• Filed: 05/02/1994
• Issued: 07/11/2000
• Est. Priority Date: 07/02/1992
• Status: Expired due to Term

• Current Assignee: Karl P. Sims
• Original Assignee: Thinking Machines Corporation (Oracle Corporation)
• Inventors: Sims, Karl P.
• Primary Examiner(s): HAFIZ, TARIQ R
• Application Number:
  US08/237,982
• Time in Patent Office: 2,262 Days
• Field of Search: 395/13
• US Class Current: 706/13
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

A computer object processing system for, during selected iterations, generating an object, such as an expression defining an image. During an initial iteration, a predetermined number of seed objects are generated, each seed object defining an object for the initial iteration. During each successive iteration, a predetermined number of mutated objects are generated (i) in response to an operator selected one of the seed objects during the initial iteration and (ii) in response to a an operator selected object during each iteration after the initial iteration. During each iteration one of the seed objects or one of the mutated objects is selected for use in generating a mutated object during a subsequent iteration.

Claims

1. A computer object processing system comprising:

A. seed object generator for generating a predetermined number of seed objects;

B. an operator controlled object selection means for selecting;

i. one of the seed objects during an initial iteration; and

ii. one of a predetermined number of mutated objects during an iteration after the initial iteration;

C. an object modifier portion for generating a predetermined number of mutated objects (i) in response to the selected one of the seed objects during an initial iteration and (ii) in response to the selected object during the iteration after the initial iteration; and

D. an iteration control portion for controlling each of the seed object generator and the object modifier portion to operate through the iterations using the object selected by the operator as the selected object during a succeeding iteration.

2. A computer object processing system as defined in claim 1 in which each object is represented by an expression including a plurality of nodes, the nodes comprising a predetermined number of node types, the object modifier portion generating a mutated object by performing a mutation operation in connection with at least one selected node of the selected expression, the mutation operation representing a mutation of the selected node with the mutation being determined by the node type of the selected node.

3. A computer object processing system as defined in claim 2 in which each node type has assigned thereto a plurality of mutation types each defining a type of modification for a node of the particular node type, the object modifier portion when performing a mutation operation selecting a mutation type in response to the node type of the selected node.

4. A computer object processing system as defined in claim 3 in which at least some objects are represented by multiple-node expressions each having a plurality of nodes, and the object modifier portion selectively performs mutation operations in connection with the nodes of at least some multiple-node expressions, the object modifier portion during a mutation operation in connection with a node of a multiple-node expression selecting a particular mutation type from among the mutation types assigned to the node'"'"'s node type in response to a predetermined selection frequency.

5. A computer method for, during selected iterations, generating an object the method comprising the steps of:

A. generating a predetermined number of seed objects for an initial iteration;

B. an operator selecting (i) a seed object during the initial iteration, or (ii) a mutated object during an iteration after the initial iteration; and

C. generating a predetermined number of mutated objects (i) in response to the selected one of the seed objects during the initial iteration and (ii) in response to a selected object during an iteration after the initial iteration.

6. A method as defined in claim 5 in which each object is represented by an expression including a plurality of nodes, the nodes comprising a predetermined number of node types, the mutation generation step including the step of performing a mutation operation in connection with at least one selected node of the selected expression, the mutation operation representing a mutation of the selected node with the mutation being determined by the node type of the selected node.

7. A method as defined in claim 6 in which each node type has assigned thereto a plurality of mutation types each defining a type of modification for a node of the particular node type, the method including the step, when performing a mutation operation, of selecting a mutation type in response to the node type of the selected node.

8. A method as defined in claim 7 in which at least some objects are represented by multiple-node expressions each having a plurality of nodes, mutation operations being selectively performed in connection with the nodes of at least some multiple-node expressions, during a mutation operation in connection with a node of a multiple-node expression a particular mutation type being selected from among the mutation types assigned to the node'"'"'s node type in response to a predetermined selection frequency.

9. A computer object processing system for, during selected iterations, generating an object, the computer object processing system comprising:

A. a digital data processor for generating an object under control of a processing control portion;

B. a processing control portion for controlling generation of an object by the processor, the processing control portion comprising;

i. a seed object generator portion for controlling the data processor to generate a predetermined number of seed objects;

ii. an operator controlled object selection portion for controlling the data processor to select

a. one of the seed objects during an initial iteration; and

b. one of a predetermined number of mutated objects during an iteration after the initial iteration;

iii. an object mutation portion for controlling the processor to generate the predetermined number of mutated objects (i) in response to the selected one of the seed objects during the initial iteration and (ii) in response to a selected object during the iteration after the initial iteration; and

iv. an iteration control portion for controlling the processor in response to each of the seed object generator portion and the object mutation portion to operate through the iterations using the object selected by the operator as the selected during a succeeding iteration.

10. A computer object processing system as defined in claim 9 in which each object is represented by an expression including a plurality of nodes, the nodes comprising a predetermined number of node types, the object mutation portion control said processor to generate a mutated object by performing a mutation operation in connection with at least one selected node of the selected expression, the mutation operation representing a mutation of the selected node with the mutation being determined by the node type of the selected node.

11. A computer object processing system as defined in claim 10 in which each node type has assigned thereto a plurality of mutation types each defining a type of modification for a node of the particular node type, the object modifier element controlling said processor, when performing a mutation operation, to select a mutation type in response to the node type of the selected node.

12. A computer object processing system as defined in claim 11 in which at least some objects are represented by multiple-node expressions each having a plurality of nodes, and the object modifier element controls said processor to selectively perform mutation operations in connection with the nodes of at least some multiple-node expressions, the object modifier element controlling said processor to, during a mutation operation in connection with a node of a multiple-node expression, select a particular mutation type from among the mutation types assigned to the node'"'"'s node type in response to a predetermined selection frequency.

13. A processing control element for controlling generation of objects by a digital data processor in a computer object processing system, the processing control element enabling the processor to, during selected iterations, generate objects, the processing control element comprising:

A. seed object generator portion for controlling the processor to generate a predetermined number of seed objects;

B. an operator controlled object selection portion for controlling the data processor to select

i. one of the seed objects during an initial iteration; and

ii. one of a predetermined number of mutated objects during an iteration after the initial iteration;

C. an object mutation portion for controlling the processor to generate a predetermined number of mutated objects (i) in response to the selected one of the seed objects during the initial iteration and (ii) in response to the selected object during the iteration after the initial iteration; and

D. an iteration control portion for controlling the processor in response to each of the seed object generator portion and the object mutation portion to operate through the iterations using the object selected by the operator as the selected object during a succeeding iteration.

14. A processing control element as defined in claim 13 in which each object is represented by an expression including a plurality of nodes, the nodes comprising a predetermined number of node types, the object mutation portion controlling said processor to generate a mutated object by performing a mutation operation in connection with at least one selected node of the selected expression, the mutation operation representing a mutation of the selected node with the mutation being determined by the node type of the selected node.

15. A processing control element as defined in claim 14 in which each node type has assigned thereto a plurality of mutation types each defining a type of modification for a node of the particular node type, the object modifier element controlling said processor, when performing a mutation operation, to select a mutation type in response to the node type of the selected node.

16. A processing control element as defined in claim 15 in which at least some objects are represented by multiple-node expressions each having a plurality of nodes, and the object modifier element controls said processor to selectively perform mutation operations in connection with the nodes of at least some multiple-node expressions, the object modifier element controlling said processor to, during a mutation operation in connection with a node of a multiple-node expression, select a particular mutation type from among the mutation types assigned to the node'"'"'s node type in response to a predetermined selection frequency.

17. A computer object processing system for, during selected iterations, generating an object defining a plurality of object elements, the computer object processing system, comprising:

A. a processor comprising;

i. a processor array including a plurality of processing elements each for generating object element data for an object element assigned thereto;

ii. a host processor for generating objects and for enabling the processing elements to use the object to generate the object element data under control of a processing control portion;

B. a processing control portion for controlling generation of objects and object element data by the processor, the processing control portion comprising;

i. a seed object generator portion for controlling the host processor to generate a predetermined number of seed objects,

ii. an operator controlled object selection portion for controlling the processor to select;

a. one of the seed object during an initial iteration; and

b. one of a predetermined number of mutated objects during an iteration after the initial iteration;

iii. an object mutation portion for controlling the host processor to enable the processor array to generate the predetermined number of mutated objects (i) in response to a selected one of the seed objects during an initial iteration and (ii) in response to a selected object during the iteration after the initial iteration; and

iv. an iteration control portion for controlling the host processor in response to each of the seed object generator portion and the object mutation portion to operate through the iterations using the object selected by the operator as the selected object during a succeeding iteration.

18. A computer object processing system as defined in claim 17 in which each object is represented by an expression including a plurality of nodes, the nodes comprising a predetermined number of node types, the object mutation portion controlling said host processor to generate a mutated object by performing a mutation operation in connection with at least one selected node of the selected expression, the mutation operation representing a mutation of the selected node with the mutation being determined by the node type of the selected node.

19. A computer object processing system as defined in claim 18 in which each node type has assigned thereto a plurality of mutation types each defining a type of modification for a node of the particular node type, the object modifier element controlling said host processor, when performing a mutation operation, to select a mutation type in response to the node type of the selected node.

20. A computer object processing system as defined in claim 19 in which at least some objects are represented by multiple-node expressions each having a plurality of nodes, and the object modifier element controls said host processor to selectively perform mutation operations in connection with the nodes of at least some multiple-node expressions, the object modifier element controlling said host processor to, during a mutation operation in connection with a node of a multiple-node expression, select a particular mutation type from among the mutation types assigned to the node'"'"'s node type in response to a predetermined selection frequency.

21. A processing control element for use in a computer object processing system which, during selected iterations, generates an object comprising a plurality of object elements, the computer object processing system comprising a processor comprising a processor array including a plurality of processing elements each for generating object element data for an object element assigned thereto and a host processor for generating objects and for enabling the processing elements to generate the object element data all under control of the processing control portion, the processing control element comprising:

A. a seed object generator portion for controlling the host processor to generate a predetermined number of seed objects,

B. an operator controlled object selection portion for controlling the host processor to select;

i. one of the seed objects during an initial iteration; and

ii. one of a predetermined number of mutated objects during an iteration after the initial iteration;

C. an object mutation portion for controlling the host processor to enable the processor array to generate a predetermined number of mutated objects (i) in response to a selected one of the seed objects during an initial iteration and (ii) in response to a selected object during the iteration after the initial iteration; and

D. an iteration control portion for controlling the host processor in response to each of the seed object generator portion and the object mutation portion to operate through the iterations using the object selected by th operator as the selected object during succeeding iteration.

22. A processing control element as defined in claim 21 in which each object is represented by an expression including a plurality of nodes, the nodes comprising a predetermined number of node types, the object mutation portion controlling said host processor to generate a mutated object by performing a mutation operation in connection with at least one selected node of the selected expression, the mutation operation representing a mutation of the selected node with the mutation being determined by the node type of the selected node.

23. A processing control element as defined in claim 22 in which each node type has assigned thereto a plurality of mutation types each defining a type of modification for a node of the particular node type, the object modifier element controlling said host processor, when performing a mutation operation, to select a mutation type in response to the node type of the selected node.

24. A processing control element as defined in claim 23 in which at least some objects are represented by multiple-node expressions each having a plurality of nodes, and the object modifier element controls said host processor to selectively perform mutation operations in connection with the nodes of at least some multiple-node expressions, the object modifier element controlling said host processor to, during a mutation operation in connection with a node of a multiple-node expression, select a particular mutation type from among the mutation types assigned to the node'"'"'s node type in response to a predetermined selection frequency.