Method and device for evolving a network using a genetic representation

• US 7,370,019 B2
• Filed: 06/23/2005
• Issued: 05/06/2008
• Est. Priority Date: 06/23/2005
• Status: Expired due to Fees

• Current Assignee: Ecole Polytechnique Federal de Lausanne
• Original Assignee: Ecole Polytechnique Federal de Lausanne
• Inventors: Mattiussi, Claudio, Floreano, Dario
• Primary Examiner(s): Hirl; Joseph P
• Assistant Examiner(s): Wong; Lut
• Application Number:
  US11/159,405
• Publication Number:
  US 20070011111A1
• Time in Patent Office: 1,048 Days
• Field of Search: 706/13, 706/12, 706/14, 706/46
• 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 of evolving a network using a genetic representation, 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, at least one of said one or more devices having a parameter token, whereas the value associated with said parameter token determines a characteristic of said device, 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 by calculating a distance between at least part of said first sequence of characters and at least part of said second sequence of characters and mapping said distance to said value of interaction strength;

associating with said parameter token a third sequence of characters;

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

creating a genetic representation from said first, second, and third sequence of characters;

applying genetic operators to said genetic representation; and

using said genetic representation to generate an evolved network, for adapting said network, and/or to perform a computation or simulation with said network.

2. The method of claim 1, 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.

3. The method of claim 2, 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.

4. 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.

5. The method of claim 4, 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.

6. 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.

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

8. The method of claim 7, wherein said second sequence of characters is a fixed sequence.

9. The method of claim 7, 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.

10. The method of claim 9, 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.

11. 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.

12. The method of claim 11, 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.

13. The method of claim 12, 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.

14. 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.

15. 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.

16. A computer storage medium comprising a computer program logic for enabling at least one processor in a computer system to process a network, 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 at least one device having a parameter token, the value associated with said parameter token determining a characteristic of said device, said computer program logic performing 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 by calculating a distance between at least part of said first sequence of characters and at least part of said second sequence of characters and mapping said distance to said value of interaction strength;

associating with said parameter token a third sequence of characters;

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

creating a genetic representation from said first, second, and third sequence of characters;

applying genetic operators to said genetic representation; and

using said genetic representation to generate an evolved network, for adapting said network, and/or to perform a computation or simulation with said network.

17. A method of evolving a network using a genetic representation, 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 by calculating a distance between at least part of said first sequence of characters and at least part of said second sequence of characters and mapping said distance to said value of interaction strength;

creating a genetic representation from said first and second sequence of characters;

applying genetic operators to said genetic representation; and

using said genetic representation to generate an evolved network, for adapting said network, and/or to perform a computation or simulation with said network;

wherein said mapping is completed by calculating a distance between at least part of said first sequence of characters and at least part of said second sequence of characters.

18. A method of evolving a network using a genetic representation, 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, at least one of said one or more devices having a parameter, the value of said parameter determining a characteristic of said device, 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 by calculating a distance between at least part of said first sequence of characters and at least part of said second sequence of characters and mapping said distance to said value of interaction strength;

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;

creating a genetic representation from said first, second, and third sequence of characters;

applying genetic operators to said genetic representation; and

using said genetic representation to generate an evolved network, for adapting said network, and/or to perform a computation or simulation with said network;

wherein said mapping at least part of said third sequence of characters to the value of said parameter constitutes calculating a distance between at least part of said third sequence of characters and at least part of a fixed sequence of characters.

19. A method of evolving a network using a genetic representation, 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; and

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 by calculating a distance between at least part of said first sequence of characters and at least part of said second sequence of characters and mapping said distance to said value of interaction strength;

creating a genetic representation from said first and second sequence of characters;

applying genetic operators to said genetic representation; and

using said genetic representation to generate an evolved network, for adapting said network, and/or to perform a computation or simulation with said network;

wherein said step of mapping at least part of said first sequence of characters and at least pan 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.