Resource assignment optimization using direct encoding and genetic algorithms
First Claim
1. A computer method of generating a list of new chromosomes from an initial list of chromosomes by employing a crossover method to speed up the convergence of the optimizing procedure to better or more fit solutions;
- each chromosome having multi-valued genes and representing a solution to a process being optimized;
the chromosomes being operated on by an optimizing procedure to increase the fitness of the chromosomes;
the steps of the method comprising;
a) defining a list of process tasks that are to be performed;
b) providing a list of resources to be used in the performance of the process tasks;
c) generating an initial list of chromosomes with each chromosome consisting of a list of gene groups, wherein at least some of the gene groups are assigned to at least a single one of the process tasks, and wherein each gene group consists of one or more genes, and each gene within at least some of the gene groups consists of a resource from the list of resources and an order of resource usage to perform a process task to which that resource was assigned;
d) evaluating fitness of each of the chromosomes from the generated list for executing the process tasks a fitness value to the chromosome;
e) creating a new list of partially filled chromosomes from the generated list of c) by;
i) stochastically selecting two or more chromosomes from the generated list of c);
ii) stochastically selecting a resource from each chromosome in the generated list of c) and an ordered subset of this resource'"'"'s ordered sequence of execution, wherein a contiguous subset is defined as where when a sequence execution is ordered 0 to J, with J+1 assignments in the chromosome with each task being executed in the order 0 to J by the resource, an ordered subset is a set of hierarchal values, with positions in the chromosome of the ordered subset being contiguous or not contiguous mathematically,iii) relabeling the ordered subset to a base relative order, changing the order from an original order in the list to a relabeled order to generate an output;
f) constructing a new chromosome by joining outputs of e) iii) and processing conflicts between ordered subsets that each refer to a same chromosomal position by randomly selecting one of the ordered subsets and dropping that selected ordered subset or retaining that ordered subset and dropping a conflicting ordered subset;
g) completing assignment of partially filled chromosomes by employing a next series of steps with Adapted Search Agents, the Adapted Search Agents comprising the steps of;
i) building a fixed length file representing a best chromosomal solution to date as determined by the fitness values from d), this file being a Fitness History Archive, which is updated during this step g) to contain most fit/best new chromosomes found by applying processing of steps d) f) and/or g); and
h) performing at least one process task from the best chromosomal solution to date;
wherein individual tasks is performed based on the computer method and the individual task includes at least one step selected from the group consisting of a) performing a chemical synthetic procedure;
b) performing a manufacturing process to produce a finished product; and
c) performing a construction project.
0 Assignments
0 Petitions
Accused Products
Abstract
This invention provides a means to minimize the costs of technical and business processes. These processes are comprised of resources and tasks requiring resources. The optimization consists of the best assignment of resources to tasks to minimize the costs. In the resource assignment optimization method disclosed herein, Genetically Adapted Search Agents (GASA) are employed to improve a population of possible assignments, each represented by a single variable length chromosome, where the chromosome upon which the GASA operates is a direct encoding of possible resource to task assignments and order. To manage the enlarged search space, this method uses the GASA with substring crossover to evolve the population towards better solutions. The assignments generated by this method satisfy all constraints.
21 Citations
16 Claims
-
1. A computer method of generating a list of new chromosomes from an initial list of chromosomes by employing a crossover method to speed up the convergence of the optimizing procedure to better or more fit solutions;
- each chromosome having multi-valued genes and representing a solution to a process being optimized;
the chromosomes being operated on by an optimizing procedure to increase the fitness of the chromosomes;
the steps of the method comprising;a) defining a list of process tasks that are to be performed; b) providing a list of resources to be used in the performance of the process tasks; c) generating an initial list of chromosomes with each chromosome consisting of a list of gene groups, wherein at least some of the gene groups are assigned to at least a single one of the process tasks, and wherein each gene group consists of one or more genes, and each gene within at least some of the gene groups consists of a resource from the list of resources and an order of resource usage to perform a process task to which that resource was assigned; d) evaluating fitness of each of the chromosomes from the generated list for executing the process tasks a fitness value to the chromosome; e) creating a new list of partially filled chromosomes from the generated list of c) by; i) stochastically selecting two or more chromosomes from the generated list of c); ii) stochastically selecting a resource from each chromosome in the generated list of c) and an ordered subset of this resource'"'"'s ordered sequence of execution, wherein a contiguous subset is defined as where when a sequence execution is ordered 0 to J, with J+1 assignments in the chromosome with each task being executed in the order 0 to J by the resource, an ordered subset is a set of hierarchal values, with positions in the chromosome of the ordered subset being contiguous or not contiguous mathematically, iii) relabeling the ordered subset to a base relative order, changing the order from an original order in the list to a relabeled order to generate an output; f) constructing a new chromosome by joining outputs of e) iii) and processing conflicts between ordered subsets that each refer to a same chromosomal position by randomly selecting one of the ordered subsets and dropping that selected ordered subset or retaining that ordered subset and dropping a conflicting ordered subset; g) completing assignment of partially filled chromosomes by employing a next series of steps with Adapted Search Agents, the Adapted Search Agents comprising the steps of; i) building a fixed length file representing a best chromosomal solution to date as determined by the fitness values from d), this file being a Fitness History Archive, which is updated during this step g) to contain most fit/best new chromosomes found by applying processing of steps d) f) and/or g); and h) performing at least one process task from the best chromosomal solution to date; wherein individual tasks is performed based on the computer method and the individual task includes at least one step selected from the group consisting of a) performing a chemical synthetic procedure;
b) performing a manufacturing process to produce a finished product; and
c) performing a construction project. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
- each chromosome having multi-valued genes and representing a solution to a process being optimized;
-
15. A computer method of generating a list of new chromosomes from an initial list of chromosomes by employing a crossover method to speed up the convergence of the optimizing procedure to better or more fit solutions;
- each chromosome having multi-valued genes and representing a solution to a process being optimized;
the chromosomes being operated on by an optimizing procedure to increase the fitness of the chromosomes;
the steps of the method comprising;a) defining a list of process tasks that are to be performed; b) providing a list of resources to be used in the performance of the process tasks; c) generating an initial list of chromosomes with each chromosome consisting of a list of gene groups, wherein at least some of the gene groups are assigned to at least a single one of the process tasks, and wherein each gene group consists of one or more genes, and each gene within at least some of the gene groups consists of a resource from the list of resources and an order of resource usage to perform a process task to which that resource was assigned; d) evaluating fitness of each of the chromosomes from the generated list for executing the process tasks a fitness value to the chromosome; e) creating a new list of partially filled chromosomes from the generated list of c) by; i) stochastically selecting two or more chromosomes from the generated list of c); ii) stochastically selecting a resource from each chromosome in the generated list of c) and an ordered subset of this resource'"'"'s ordered sequence of execution, wherein a contiguous subset is defined as where when a sequence execution is ordered 0 to J, with J+1 assignments in the chromosome with each task being executed in the order 0 to J by the resource, an ordered subset is a set of hierarchal values, with positions in the chromosome of the ordered subset being contiguous or not contiguous mathematically, iii) relabeling the ordered subset to a base relative order, changing the order from an original order in the list to a relabeled order to generate an output; f) constructing a new chromosome by joining outputs of e) iii) and processing conflicts between ordered subsets that each refer to a same chromosomal position by randomly selecting one of the ordered subsets and dropping that selected ordered subset or retaining that ordered subset and dropping a conflicting ordered subset; g) completing assignment of partially filled chromosomes by employing a next series of steps with Adapted Search Agents, the Adapted Search Agents comprising the steps of; i) building a fixed length file representing a best chromosomal solution to date as determined by the fitness values from d), this file being a Fitness History Archive, which is updated during this step g) to contain most fit/best new chromosomes found by applying processing of steps d) f) and/or g); and h) performing at least one process task from the best chromosomal solution to date; wherein individual tasks is performed based on the computer method and the individual task includes at least one step selected from the group consisting of a) moving persons or objects between multiple destinations, b) performing a chemical synthetic procedure, c) performing a manufacturing process to produce a finished product; and
d) performing a construction project.- View Dependent Claims (16)
- each chromosome having multi-valued genes and representing a solution to a process being optimized;
Specification