System and method for time-efficient distributed search and decision-making using cooperative co-evolutionary algorithms executing in a distributed multi-agent architecture

• US 6,882,988 B2
• Filed: 10/05/2001
• Issued: 04/19/2005
• Est. Priority Date: 10/05/2001
• Status: Active Grant

• Current Assignee: Rensselaer Polytechnic Institute
• Original Assignee: Rensselaer Polytechnic Institute
• Inventors: Graves, Robert, Subbu, Raj, Sanderson, Arthur
• Primary Examiner(s): Knight, Anthony
• Assistant Examiner(s): Hirl, Joseph P.
• Application Number:
  US09/971,972
• Publication Number:
  US 20030069865A1
• Time in Patent Office: 1,292 Days
• Field of Search: 706/10, 706/13, 706/12
• US Class Current: 706/10
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

A method and architecture for efficiently solving complex distributed problems uses coevolutionary agents incorporating evolutionary algorithms located at different nodes in a distributed network. The coevolutionary agents conduct localized database searches and evolve at their respective nodes while sharing information with other coevolutionary agents working the same problem. Results or solutions to the problem posed are available at each network node containing a coevolutionary agent working the problem.

Claims

1. A method for efficiently solving an optimization problem having coupled variables distributed across a computer network architecture comprising at least two nodes each having local databases, the method comprising:

providing an optimization algorithm;

creating a plurality of coevolutionary agents implementing the optimization algorithm to provide a cooperative solution to said optimization problem, each coevolutionary agent having a primary search variable and at least one secondary search variable, the plurality of coevolutionary agents distributed across the at least two nodes in the network architecture and the primary search variable of each coevolutionary agent corresponding to one of the at least one secondary search variables of the remaining coevolutionary agents;

conducting concurrent and cooperative local searches using each coevolutionary agent at the corresponding one of the nodes where the coevolutionary agent is located, based on the primary search variable of the coevolutionary agent for producing local solutions using information available from the corresponding one of the local databases;

updating the primary search variable of each coevolutionary agent based on the corresponding one of the local solutions;

providing a plurality of mobile agents at the at least two nodes;

using the plurality of mobile agents to transport the local solutions produced at each node having a coevolutionary agent to all of the other nodes; and

updating the at least one secondary search variable of each coevolutionary agent using local solutions transported by the mobile agents using a coordination scheme.

2. A method according to claim 1, further comprising repeating conducting concurrent and cooperative searches, updating the primary search variable, using the mobile agents to transport local solutions and updating the at least one secondary search variable to produce an optimized cooperative solution.

3. A method according to claim 2, further comprising accessing the optimized cooperative solution at any one of the at least two nodes.

4. A method according to claim 1, wherein the coordination scheme is selected from the group consisting of local, joint, pool, elite local, elite joint and elite pool schemes.

5. A method for solving a complex problem having multiple interdependent variables in a network-distributed environment comprising a plurality of nodes each having a corresponding local database, the method comprising:

providing an optimization algorithm relating the multiple interdependent variables;

creating a plurality of coevolutionary agents implementing the optimization algorithm to provide a cooperative solution to said complex problem, each coevolutionary agent setting one of the multiple interdependent variables as a primary search variable, the rest of the interdependent variables being defined as secondary search variables for the coevolutionary agent;

distributing the plurality of coevolutionary agents across the plurality of nodes;

conducting concurrent and cooperative local searches using each coevolutionary agent at the corresponding one of the nodes where the coevolutionary agent is located, based on the primary search variable of the coevolutionary agent for producing local solutions from information available from the corresponding one of the local databases;

updating the primary search variable of each coevolutionary agent based on the corresponding one of the local solutions;

providing a plurality of mobile agents in the network-distributed environment;

using the plurality of mobile agents to transport the local solutions produced at each node having a coevolutionary agent to all of the other nodes; and

updating the at least one secondary search variable of each coevolutionary agent using local solutions transported by the mobile agents using a coordination scheme.

6. A method according to claim 5, further comprising repeating conducting concurrent and cooperative local searches, updating the primary search variable, using the mobile agents to transport local solutions and updating the at least one secondary search variable to produce an optimized cooperative solution.

7. A method according to claim 6, further comprising accessing the optimized cooperative solution at any one of the plurality of nodes.

8. A method according to claim 5, wherein the coordination scheme is selected from the group consisting of local, joint, pool, elite local, elite joint and elite pool schemes.

9. A system for efficiently solving an optimization problem having coupled variables distributed across a computer network architecture comprising at least two nodes each having local databases, the system comprising:

a plurality of coevolutionary agent means for implementing an optimization algorithm to provide a cooperative solution to said optimization problem, each coevolutionary agent means having a primary search variable and at least one secondary search variable, the plurality of coevolutionary agent means distributed across the at least two nodes in the network architecture and the primary search variable of each coevolutionary agent means corresponding to one of the at least one secondary search variables of the remaining coevolutionary means;

search means for conducting concurrent and cooperative local searches using each coevolutionary agent means at the corresponding one of the nodes where the coevolutionary agent means is located, based on the primary search variable of the coevolutionary agent means for producing local cooperative solutions using information available from the corresponding one of the local databases;

update means for updating the primary search variable of each coevolutionary agent means based on the corresponding one of the local cooperative solutions;

a plurality of mobile agents at the at least two nodes, the plurality of mobile agents transporting the local cooperative solutions produced at each node having one of the plurality of coevolutionary agent means to all of the other nodes; and

secondary update means for updating the at least one secondary search variable of each coevolutionary agent means using local cooperative solutions transported by the mobile agents using a coordination scheme.

10. A system according to claim 9, further comprising solution means for accessing an optimized cooperative Solution at any one of the at least two nodes.

11. A system according to claim 10, wherein the coordination scheme is selected from the group consisting of local, joint, pool, elite local, elite joint and elite pool schemes.

12. A system according to claim 9, wherein the coordination scheme is selected from the group consisting of local, joint, pool, elite local, elite joint and elite pool schemes.

13. A system for solving a complex problem having multiple interdependent variables in a network-distributed environment comprising a plurality of nodes each having a corresponding local database, the system comprising:

an optimization algorithm relating the multiple interdependent variables;

a plurality of coevolutionary agents implementing the optimization algorithm for providing a cooperative solution to said complex problem, each coevolutionary agent setting one of the multiple interdependent variables as a primary search variable, the rest of the interdependent variables being defined as secondary search variables for the coevolutionary agent, the plurality of coevolutionary agents being distributed across the plurality of nodes;

search means for conducting concurrent and cooperative local searches using each coevolutionary agent at the corresponding one of the nodes where the coevolutionary agent is located, based on the primary search variable of the coevolutionary agent for producing local solutions from information available from the corresponding one of the local databases;

update means for updating the primary search variable of each coevolutionary agent based on the corresponding one of the local solutions;

a plurality of mobile agents in the network-distributed environment, the plurality of mobile agents transporting the local solutions produced at each node having a coevolutionary agent to all of the other nodes; and

secondary update means for updating the at least one secondary search variable of each coevolutionary agent using local solutions transported by the mobile agents using a coordination scheme.

14. A system according to claim 13, further comprising solution means for accessing the optimized cooperative solution at any one of the at least one nodes.

15. A system according to claim 14, wherein the coordination scheme is selected from the group consisting of local, joint, pool, elite local, elite joint and elite pool schemes.

16. A system according to claim 13, wherein the coordination scheme is selected from the group consisting of local, joint, pool, elite local, elite joint and elite pool schemes.