×

Resource assignment optimization using direct encoding and genetic algorithms

  • US 7,668,788 B2
  • Filed: 03/08/2006
  • Issued: 02/23/2010
  • Est. Priority Date: 06/06/2005
  • Status: Expired due to Fees
First Claim
Patent Images

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 all claims
  • 0 Assignments
Timeline View
Assignment View
    ×
    ×