Method and device for the genetic representation and evolution of networks

• US 20070011111A1
• Filed: 06/23/2005
• Published: 01/11/2007
• Est. Priority Date: 06/23/2005
• Status: Active Grant

• Current Assignee: Ecole Polytechnique Federal de Lausanne
• Original Assignee: Ecole Polytechnique Federal de Lausanne
• Inventors: Floreano, Dario, Mattiussi, Claudio
• Granted Patent: US 7,370,019 B2
• Time in Patent Office: Days
• 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 method for the genetic representation of a network (100), the network having one or more devices (20, 30, 70, 80), each device comprising at least one terminal (21, 22, 23; 71, 72) connected to at least one other terminal (21, 22, 23; 71, 72, 61) by a link with a value of interaction strength. The method includes associating with the devices terminal (21, 22, 23; 71, 72) a first sequence of characters (121, 122, 123; 171, 172), associating with the other terminal (21, 22, 23; 71, 72, 61) a second sequence of characters (121, 122, 123; 171, 172; 162), mapping at least part of the first sequence of characters (121, 122, 123; 171, 172) and at least part of the second sequence of characters (121, 122, 123; 171, 172; 161) to the value of interaction strength in order to determine the value of interaction strength.

Claims

1. A method for the genetic representation of a network, said network comprising one or more devices, each of said devices comprising at least one terminal, said at least one terminal being connected to at least one other terminal by a link characterized by a value of interaction strength, said method comprising the steps of:

associating with said at least one terminal a first sequence of characters,

associating with said at least one other terminal a second sequence of characters,

mapping at least part of said first sequence of characters and at least part of said second sequence of characters to said value of interaction strength in order to determine said value of interaction strength.

2. The method of claim 1, said step of mapping comprising the step of calculating a distance between at least part of said first sequence of characters and at least part of said second sequence of characters.

3. The method of claim 2, said step of mapping further comprising the step of mapping said distance to said value of interaction strength.

4. The method of claim 1, at least one of said one or more devices having a parameter, whereas the value of said parameter determines a characteristic of said device, said method further comprising the steps of:

associating with said parameter a third sequence of characters,

mapping at least part of said third sequence of characters to the value of said parameter.

5. The method of claim 4, said step of mapping at least part of said third sequence of characters to the value of said parameter comprising the step of calculating a distance between at least part of said third sequence of characters and at least part of a fixed sequence of characters.

6. The method of claim 5, said step of mapping at least part of said third sequence of characters to the value of said parameter further comprising the step of mapping said distance to said value of said parameter.

7. The method of claim 1, said first sequence of characters being part of a genome representing said network, said genome being constituted of a sequence of characters belonging to a genetic alphabet, the presence of each of said devices being indicated by a device token and the presence of said first sequence of characters being indicated by a terminal token.

8. The method of claim 7, at least one of said one or more devices having a parameter, whereas the value of said parameter determines a characteristic of said device, a third sequence of characters associated with said parameter being part of said genome, the presence of said third sequence of characters being indicated by a parameter token.

9. The method of claim 1, further comprising the step of creating a set of devices defining the types of all devices possibly comprised in said network.

10. The method of claim 1, wherein said at least one other terminal is an external terminal belonging to a device external to said network.

11. The method of claim 10, wherein said second sequence of characters is a fixed sequence.

12. The method of claim 10, wherein said second sequence of characters is part of a genome representing said network, said genome being constituted of a sequence of characters belonging to a genetic alphabet.

13. The method of claim 12, wherein the presence of said external terminal is indicated in said genome by a device token and the presence of said second sequence of characters is indicated in said genome by a terminal token.

14. The method of claim 1, wherein said at least one other terminal is a first terminal of a transducer, said transducer further comprising a second terminal, said second sequence of characters being associated with said first terminal and a fourth sequence of characters being associated with said second terminal, said second terminal being connected by another link characterized by another value of interaction strength to an external terminal belonging to a device external to said network, a fifth sequence of characters being associated with said external terminal, said method further comprising the step of mapping at least part of said fourth sequence of characters and at least part of said fifth sequence of characters to said other value of interaction strength in order to determine said other value of interaction strength.

15. The method of claim 14, wherein said second sequence of characters and said fourth sequence of characters are part of a genome representing said network, said genome being constituted of a sequence of characters belonging to a genetic alphabet, and wherein said fifth sequence is a fixed sequence.

16. The method of claim 15, wherein the presence of said transducer is indicated in said genome by a device token and the presence of said second sequence of characters and the presence of said fourth sequence of characters are indicated in said genome by terminal tokens.

17. The method of claim 1, wherein said step of mapping at least part of said first sequence of characters and at least part of said second sequence of characters to said value of interaction strength returns a value of interaction strength corresponding to no interaction when said first sequence of characters includes a first pattern and said second sequence of characters includes a second pattern complementary to said first pattern.

18. The method of claim 1, wherein said step of mapping at least part of said first sequence of characters and at least part of said second sequence of characters to said value of interaction strength returns a value of interaction strength corresponding to no interaction when said first sequence of characters and said second sequence of characters do not both comprise a same pattern.

19. A computer program directly loadable in the memory of a computer system, said program performing the steps of the method of claim 1 when said program is run on said computer.

20. A genome for the genetic representation of a network, said genome being constituted of a sequence of characters belonging to a genetic alphabet, said genome comprising at least one device token determining the nature of a device of said network, at least one terminal token indicating the presence of a sequence of character associated with a terminal of said device.

21. The genome of claim 20, further comprising a parameter token indicating the presence of a sequence of character associated with a parameter of said device.

22. A method for the synthesizing of a network from its genome, said genome being constituted of a sequence of characters belonging to a genetic alphabet, said method comprising the steps of:

scanning the genome in a predetermined direction,

detecting the presence in said genome of a device token signaling the presence in said network of a corresponding device,

detecting the presence in said genome of a terminal token indicating the presence of a first sequence of characters associated with a terminal of said device,

mapping at least part of said first sequence of characters and at least part of a second sequence of characters associated with another terminal to a value of interaction strength characterizing a link connecting said terminal to said another terminal, in order to determine said value of interaction strength.

23. The method of claim 22 further comprising the step of:

detecting the presence in said genome of a parameter token indicating the presence of a third sequence of characters associated with a parameter of said device,

mapping at least part of said third sequence of characters to the value of said parameter.

24. A computer program directly loadable in the memory of a computer system, said program performing the steps of the method of claim 22 when said program is run on said computer.

25. A method for the genetic representation of a network into a genome constituted of a sequence of characters belonging to a genetic alphabet, said network comprising at least one device, said at least one device comprising at least one terminal, said at least one terminal being connected to at least one other terminal by a link characterized by a value of interaction strength, said method comprising the steps of:

inserting into said genome a device token signaling the presence in said network of a said at least one device,

inserting into said genome a terminal token indicating the presence of a first sequence of characters associated with said at least one terminal of said device,

wherein said first sequence of characters determines a value of interaction strength characterizing a link connecting said at least one terminal with another terminal when at least part of said first sequence of characters and at least part of a second sequence of characters associated with said another terminal are mapped to said value of interaction strength.

26. The method of claim 25, said at least one device having a parameter, whereas the value of said parameter determines a characteristic of said at least one device, said method further comprising the steps of:

inserting into said genome a parameter token indicating the presence of a third sequence of characters associated with said parameter of said device,

wherein said third sequence of characters determines a value of said parameter when at least part of said first sequence of characters and at least part of a fixed sequence of characters are mapped to said value of parameter.

27. A computer program directly loadable in the memory of a computer system, said program performing the steps of the method of claim 25 when said program is run on said computer.