Universal system for artificial intelligence based learning, categorization, and optimization

• US 5,848,402 A
• Filed: 08/06/1996
• Issued: 12/08/1998
• Est. Priority Date: 07/07/1994
• Status: Expired due to Term

• Current Assignee: CA, Inc. (d/b/a CA Technologies) (Broadcom, Inc.)
• Original Assignee: AI Ware, Inc. (Broadcom, Inc.)
• Inventors: Yip, Pui-Chiu, Pao, Yoh-Han
• Primary Examiner(s): Hafiz, Tariq R.
• Assistant Examiner(s): Shah, Sanjiv
• Application Number:
  US08/689,338
• Time in Patent Office: 854 Days
• Field of Search: 706/13, 706/25, 706/51, 706/10, 706/14
• US Class Current: 706/13
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

A parallel, distributed processing system is provided for solving NP-hard problems, and the like, efficiently, quickly and accurately. The system employs parallel processors which are iteratively and intelligently allocated for a series of generations of child solutions from selected, previous generation or parent solutions. The system employs multiple levels of competition for generating a next level of possible solutions and for reallocating processor resources to the most promising regions for finding a best solution to the task. This includes both inter-family competition, as well as intra-family competition. System temperature data are set and gradually decreased with each succeeding generation. A degree of randomness is entered into the solution generation. The hierarchical and iterative process, incorporating randomness and a decreasing temperature provides for the guided evolutionary simulated annealing solution generation.

Claims

1. A parallel, distributed processing system for problem solutions employing guided evolutionary simulated annealing comprising:

an iteration data storage for storing data representative of a preselected number of iterations;

means for storing an integer N representative of a number of randomly generated parent solutions;

means for allocating an integer M representative of a number of children solutions to each of the N parent solutions;

means for allocating M×

N children solutions among each of an integer P representative of a plurality of processor units;

means for enabling the plurality P of processor units, each processor unit including,

means for receiving data representative of one of the N parent solutions,

generating means for generating child solutions from the received one of the N parent solutions, the parent solution and all child solutions generated from the parent solution forming a family,

global comparison means for comparing each child solution generated by the generating means against a preselected global criterium, and

pruning means for selecting a subset N'"'"' of child solutions generated by the generating means in accordance an output of a local comparison means for comparing each child solution generated by the generating means against a preselected local criterium, the subset of N'"'"' child solutions forms a next generation of parent solutions;

means for re-allocating the M×

N number of children solutions among each of the N'"'"' parent solutions in response to the global comparison means; and

means for iteratively communicating N'"'"' child solutions as a next generation of N parent process to the plurality P of processor units until reaching at least one of (i) the preselected number of iterations in accordance with a comparison of the data representative of a preselected number of iterations stored in the iteration data storage and (ii) achievement of an acceptable solution from the previous child solution subset.

2. The parallel, distributed processing system for problem solutions employing guided evolutionary simulated annealing of claim 1 further comprising:

a temperature data storage for storing temperature data representative of an initial temperature t;

means for decreasing a value of the temperature data during each iteration of the preselected number of iterations; and

wherein the pruning means includes means for selecting the subset of child solutions in accordance with the temperature data.

3. The parallel, distributed processing system for problem solutions employing guided evolutionary simulated annealing of claim 2 further comprising:

means for computing an objective value y_p of a parent solution in the family;

means for computing an objective value Y_c of each child solution in the family;

means for storing a value representative of a lowest objective value associated with child solutions in the family;

testing means for testing the lowest objective value associated with the child solutions against the objective value of the parent of the family; and

wherein the pruning means further includes means for selecting the subset of child solutions in accordance with an output of the testing means.

4. The parallel, distributed processing system for problem solutions employing guided evolutionary simulated annealing of claim 3 wherein the testing means tests the child solutions against the local criterion in accordance with at least one of the relation,

5. The parallel, distributed processing system for problem solutions employing guided evolutionary simulated annealing of claim 3 wherein the global comparison means includes means for incrementing a count value in response to the preselected global criteria.

6. The parallel, distributed processing system for problem solutions employing guided evolutionary simulated annealing of claim 5 wherein the preselected global criteria are in accordance with at least one of the relation,

7. The parallel, distributed processing system for problem solutions employing guided evolutionary simulated annealing of claim 6 wherein the means for reallocating the M×

N number of children among each of the N'"'"' parents is in accordance with,

wherein,

M'"'"'=the number of children to be allocated to that family,

T=the total number of children available for all families, i.e. N×

M,

A=the count value in response to the global criteria for the family, and

S=the sum of all count values for all families during an iteration.

8. The parallel, distributed processing system for problem solutions employing guided evolutionary simulated annealing of claim 7 further comprising means for incrementing a count value for each of the plurality of processor units each time the plurality of N processors are enabled.

9. A method of parallel and distributed processing for problem solutions employing guided evolutionary simulated annealing comprising the steps of:

storing data representative of a preselected number of iterations;

storing an integer N representative of a number of randomly generated parent solutions;

simultaneously enabling N of a plurality of processor units;

receiving, in each processor unit, data representative of one of the N parent solutions;

allocating M child solutions to each one of the N parent solutions forming families;

allocating the M×

N children solutions among the plurality of processor units;

generating, in each processor unit, child solutions from the one of the N parent solutions;

comparing, in each processor unit, each child solution generated in the generating step against a preselected global criterium;

determining the fitness of each family in response to the comparison of children of a family against the preselected global criterium;

pruning so as to select a subset of N'"'"' child solutions generated by the step of generating in accordance an output of a step of locally comparing the children of a family against preselected local criterium, the subset of child solutions forms a next generation of parent solutions;

reallocating the M×

N number of children solutions among each of the N'"'"' parent solutions in response to the fitness determination; and

iteratively communicating N'"'"' child solutions as a next generation of N parent process to the plurality of processor units until reaching at least one of (i) the preselected number of iterations in accordance with a comparison of the data representative of a preselected number of iterations stored in the iteration data storage and (ii) achievement of an acceptable solution from the previous child solution subset.

10. The method of parallel and distributed processing for problem solutions employing guided evolutionary simulated annealing of claim 9 further comprising the steps of:

computing an objective value y_p of a parent solution in the family;

computing an objective value Y_c of each child solution in the family;

storing a value representative of a lowest objective value associated with child solutions in the family;

testing the objective value of the lowest objective value associated with child solutions against the objective value of the parent of the family; and

wherein the step of pruning further includes selecting the subset of child solutions in accordance with an output of the step of testing.

11. The method of parallel and distributed processing for problem solutions employing guided evolutionary simulated annealing of claim 10 further comprising the steps of:

storing temperature data representative of an initial temperature t;

decreasing a value of the temperature data during each iteration of the preselected number of iterations; and

selecting the subset of child solutions in accordance with the temperature data.

12. The method of parallel and distributed processing for problem solutions employing guided evolutionary simulated annealing of claim 11 wherein the step of determining the fitness of the families includes incrementing a count value in response to the comparison against the preselected global criteria.

13. The method of parallel and distributed processing for problem solutions employing guided evolutionary simulated annealing of claim 12 further comprising the step of incrementing a count value for each of the plurality of processor units each time the plurality of N processors are enabled.

14. The method of parallel and distributed processing for problem solutions employing guided evolutionary simulated annealing of claim 10 wherein the step of testing further includes the step of completing a local comparison in accordance with at least one of the relation,

15. A parallel processor system for parallel, distributed processing system for problem solutions employing guided evolutionary simulated annealing comprising:

a plurality of evaluation processors;

a local memory associated with each evaluation processor, each local memory including,

means for storing data representative of one of N parent solutions,

means for storing a count value representatives of number of iterations of calculations therethrough, and

means for storing data representative of a lowest acceptable objective value;

a common memory selectively in data communication with each of the evaluation processors, the common memory including,

means for storing data representative of a preselected number of iterations,

means for storing an integer N representative of a number of randomly generated parent solutions,

temperature data storage for storing temperature data representative of an initial temperature t, and

means for storing data representative of an acceptable solution of a given problem;

each evaluation processor including,

means for receiving data representative of one of the N parent solutions,

means for allocating an integer M representative of a number of children solutions to each of the N parent solutions;

means for allocating the M×

N children solutions among the plurality of evaluation processors;

generating means for generating child solutions from the one of the N parent solutions,

global comparison means for comparing each child solution against a pres global criterium;

local comparison means for comparing each child solution generated by the generating means against the objective value of its parent, and

pruning means for selecting a subset of N'"'"' child solutions generated by the generating means in accordance an output of the local comparison means, the subset of N'"'"' child solutions forms a next generation of parent solutions; and

means for re-allocating the M×

N number of children solutions among each of the N'"'"' parent solutions in response to the global comparison means.

16. The parallel, distributed processing system for problem solutions employing guided evolutionary simulated annealing of claim 15 wherein the preselected global criteria are in accordance with at least one of the relation,

17. The parallel processor system for parallel, distributed processing system for problem solutions employing guided evolutionary simulated annealing of claim 15 further comprising bus allocation control means to coordinate transfers between each local memory and the common memory.

18. The parallel processor system for parallel, distributed processing system for problem solutions employing guided evolutionary simulated annealing of claim 17 further comprising a control processor in data communication with the bus allocation control means and the system memory for allocating each next generation of parent solutions to a subset of the evaluation processors.

19. The parallel processor system for parallel, distributed processing system for problem solutions employing guided evolutionary simulated annealing of claim 18 wherein the common memory is comprised of dual port memory facilitating concurrent access of a plurality of processors to data disposed therein.

20. The parallel processor system for parallel, distributed processing system for problem solutions employing guided evolutionary simulated annealing of claim 19 wherein the control processor includes its own local memory for storing local data and instructions therefor.