Universal system for artificial intelligence based learning, categorization, and optimization
First Claim
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, andpruning 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.
3 Assignments
0 Petitions
Accused Products
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.
53 Citations
20 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; andmeans 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
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,
- space="preserve" listing-type="equation">Y.sub.c <
y.sub.GL
or, ##EQU6## wherein, Yc =an objective value of a child solution, YGL =a lowest objective value of solutions found in the entire population, up to the previous generation, p=a random number randomly distributed between 0 and 1, and t2 =a temperature coefficient. ##EQU7## - space="preserve" listing-type="equation">Y.sub.c <
-
-
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.
- N number of children among each of the N'"'"' parents is in accordance with,
-
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; anditeratively 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. - View Dependent Claims (10, 11, 12, 13, 14)
-
-
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. - View Dependent Claims (16, 17, 18, 19, 20)
-
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.
-
Specification