US5511158A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for creating and evolving directed graphs
Assignee: RTPC Corp
•
Filing: 1994-08-04
•
Granted: 1996-04-23
•
Expires: 2014-08-04
Abstract
Abstract A system processes directed graphs, each directed graph comprising a plurality of nodes interconnected by arrows defining a relationship among the nodes, each node defining a selected attribute. The system comprises an initial population means, a subsequent generation population generating means, and a competition simulation means. The initial population means provides an initial population of directed graphs that comprises an initial current generation during an initial iteration. The subsequent generation population generating means generates, in response to selected ones of the directed graphs in each of a plurality of current generations, modified directed graphs for use generation during a subsequent iteration. The competition simulation means performs a processing operation in connection with attributes of the nodes of the graphs to simulate a competition among the current generation of directed graphs in connection with a selected goal, to develop the ranking information for use by the subsequent generation population generating means. The operations of the initial population means, the subsequent generation population generating means and the competition simulation means are controlled through a series of iterations. In the successive iterations, the performance of the graphs in response to the selected goal is anticipated to improve, since the population of graphs for each iteration is based on the graphs determined to have the best fitness during the previous iteration.
Inventors
- 👤 Karl P. Sims
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 09:11
CPC Classifications
G; G06; G06N; G06N3/00; G06N3/004; G06T; G06T17/00
Claims Analysis
Total Claims: 17
Claim 1
Independent Claim
235 words
A system for processing directed graphs, each directed graph comprising a plurality of nodes interconnected by directional links defining a directional relationship among said nodes, each node defining a selected attribute, said system comprising: A. an initial population means for providing an initial population of directed graphs, said initial population of directed graphs comprising an initial current generation during an initial iteration: B. a subsequent generation population generating means for generating, from selected ones of said directed graphs in each of a plurality of current genres, modified directed graphs comprising a subsequent generation for use as directed graphs in a current generation during a subsequent iteration, said subsequent generation population generating means (i) selecting ones of the directed graphs in each current generation in response to ranking information, and (ii) processing said selected directed graphs in relation to mutation operations selected from a set of selected types of mutation operations to generate modified directed graphs; C. competition simulation means for performing a processing operation in connection with attributes of said nodes of said graphs to simulate a competition among said current generation of directed graphs in connection with a selected goal, to develop said ranking information for use by the subsequent generation population generating means; and D. iteration control means for controlling the operations of the initial population means, said subsequent generation population generating means and said competition simulation means through a series of iterations.
Claim 2
Independent Claim
235 words
A system for processing directed graphs, each directed graph comprising a plurality of nodes interconnected by directional links defining a directional relationship among said nodes, each node defining a selected attribute, said system comprising: A. an initial population means for providing an initial population of directed graphs, said initial population of directed graphs comprising an initial current generation during an initial iteration: B. a subsequent generation population generating means for generating, from selected ones of said directed graphs in each of a plurality of current genres, modified directed graphs comprising a subsequent generation for use as directed graphs in a current generation during a subsequent iteration, said subsequent generation population generating means (i) selecting ones of the directed graphs in each current generation in response to ranking information, and (ii) processing said selected directed graphs in relation to mutation operations selected from a set of selected types of mutation operations to generate modified directed graphs; C. competition simulation means for performing a processing operation in connection with attributes of said nodes of said graphs to simulate a competition among said current generation of directed graphs in connection with a selected goal, to develop said ranking information for use by the subsequent generation population generating means; and D. iteration control means for controlling the operations of the initial population means, said subsequent generation population generating means and said competition simulation means through a series of iterations.
Claim 3
Dependent Claim
50 words
A system as defined in claim 1 in which, for at least one directed graph during an iteration, at least one of said nodes includes an internal parameter having a value, the subsequent generation population generating means, in performing a selected mutation operation, modifying the value of said internal parameter.
Claim 4
Dependent Claim
56 words
A system as defined in claim 2 in which said internal parameter has a Boolean value selected from a predetermined set of values, the subsequent generation population generating means, in performing the parameter mutation operation in connection with the internal parameter, modifying the internal parameter's value by selecting another value from said predetermined set of values.
Claim 5
Dependent Claim
46 words
A system as defined in claim 2 in which said internal parameter has a scalar values, the subsequent generation population generating means, in performing the parameter mutation operation in connection with the internal parameter, modifying the internal parameter's value by adding a randomly-selected adjustment value thereto.
Claim 6
Dependent Claim
37 words
A system as defined in claim 4 in which the subsequent generation population generating means selects the adjustment value in relation to a Gaussian-like distribution, so that small adjustment values are more likely than large adjustment values.
Claim 7
Dependent Claim
33 words
A system as defined in claim 4 in which said internal parameter has a selected value range, the subsequent generation population generating means limiting the internal parameter's value in relation to the range.
Claim 8
Dependent Claim
39 words
A system as defined in claim 2 in which the subsequent generation population generating means, in accordance with said mutation operation, generates a node at random and interconnects it with a node of said at least one directed graph.
Claim 9
Dependent Claim
39 words
A system as defined in claim 2 in which the subsequent generation population generating means, in accordance with said mutation operation, generates a node at random and substitutes it for a node of said at least one directed graph.
Claim 10
Dependent Claim
46 words
A system as defined in claim 1 in which, for at least one directed graph, at least one directional link includes an internal parameter having a value, the subsequent generation population generating means, in performing a selected mutation operation, modifying the value of said internal parameter.
Claim 11
Dependent Claim
42 words
A system as defined in claim 9 in which said internal parameter defines the directional relationship between a pair of nodes, the subsequent generation population generating means, in performing the selected mutation operation, modifying the directional relationship between the pair of nodes.
Claim 12
Dependent Claim
38 words
A system as defined in claim 1 in which, for at least one directed graph, the subsequent generation population generating means, in performing a selected mutation operation, selecting a pair of nodes and adding a directional link therebetween.
Claim 13
Dependent Claim
42 words
A system as defined in claim 1 in which, for at least one directed graph, the subsequent generation population generating means, in performing a selected mutation operation, selecting a pair of nodes having a directional link therebetween and removing the directional link.
Claim 14
Dependent Claim
35 words
A system as defined in claim 12 in which the subsequent generation population generating means, after performing the selected mutation operation, removes nodes which are not connected to any other nodes by a directional link.
Claim 15
Dependent Claim
57 words
A system as defined in claim 1 in which, for at least two selected directed graphs, the subsequent generation population generating means, in performing a selected mutation operation performs a mating operation in which a selected portion of one of said selected directed graphs are substituted for a selected portion of said other of said selected graphs.
Claim 16
Dependent Claim
54 words
A system as defined in claim 1 in which at least some of said directed graphs each represents a portion of a virtual creature having a morphology defined by the directed graph, with each node of said at least some of said directed graphs defining a structural element of one of said virtual creatures.
Claim 17
Dependent Claim
35 words
A system as defined in claim 15 in which each virtual creature is further defined by a second directed graph which defines a control structure for controlling virtual movement of the virtual creature's structural elements.
References Cited (Backward Citations)
US5136686A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-04-23 | 1999-10-23 | 2000-04-23 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-04-23 | 2003-10-23 | 2004-04-23 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-04-23 | 2007-10-23 | 2008-04-23 | $7700.00 | Window Closed / Lapsed |