Genetic algorithm techniques and applications

• US 6,882,989 B2
• Filed: 02/23/2001
• Issued: 04/19/2005
• Est. Priority Date: 02/23/2001
• Status: Expired due to Fees

• Current Assignee: Raytheon BBN Technlogies Corp. (Rtx Corporation)
• Original Assignee: BBNT Solutions LLC (Rtx Corporation)
• Inventors: Stevens, Soraya Rana
• Primary Examiner(s): Knight, Anthony
• Assistant Examiner(s): Holmes, Michael B.
• Application Number:
  US09/792,243
• Publication Number:
  US 20020120407A1
• Time in Patent Office: 1,516 Days
• Field of Search: 706/13, 705/8
• US Class Current: 706/13
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

Disclosed herein are genetic algorithm techniques and applications. The techniques and applications disclosed include a method of generating offspring having feasible gene traits selected from parent chromosomes, a method of assigning tasks to resources, and a method of determining feasible gene traits for a chromosome, for example, to mutate a gene to a feasible trait.

Claims

1. A computer-implemented method of determining a chromosome gene trait of an offspring, the chromosome representing an attempted solution to a problem, the method comprising:

receiving gene traits from parents of the offspring;

receiving identification of a gene locus of the offspring chromosome;

determining which, if any, of the received parent gene traits are feasible gene traits for the offspring gene at the identified locus; and

if it is determined that at least one of the received parent gene traits is feasible, selecting the gene trait of the offspring chromosome at the identified locus from the determined feasible gene traits.

2. The method of claim 1, wherein the offspring chromosome expresses an assignment of resources to tasks.

3. The method of claim 2, wherein trait alleles comprise alleles specifying resources.

4. The method of claim 1, wherein determining which of the received traits are feasible comprises determining which of the received traits are feasible based on a gene trait of an offspring gene at a different locus.

5. The method of claim 1, further comprising, if none of the parent genes traits are feasible, setting the offspring gene at the identified locus to the null trait.

6. The method of claim 5, further comprising determining whether a gene trait other than the received parent gene traits is feasible.

7. The method of claim 1, wherein the parent gene traits comprise gene traits of the parent chromosomes at the identified locus.

8. A computer-implemented method of assigning tasks to resources, the method comprising:

generating a population of chromosomes, each chromosome having a sequence of genes having a trait selected from alleles that identify the resources, the loci of the genes identifying one of the tasks;

generating offspring from the generated population; and

evaluating the generated offspring;

wherein evaluating offspring comprises determining a scheduling fitness measure.

9. The method of claim 8, wherein the scheduling fitness measure comprises a measure based on at least one of the following:

the number of crewmen assigned to a mission, qualifications assigned to a mission, and distribution of assignments among crew-persons.

10. The method of claim 8, wherein generating offspring comprises setting a chromosome gene trait to a null trait.

11. The method of claim 10, further comprising:

identifying a chromosome gene having the null trait; and

selecting feasible chromosome gene traits, if possible, for the identified chromosome gene.

12. The method of claim 8, wherein generating offspring comprises:

receiving gene traits from parents of the offspring;

receiving identification of a gene locus of the offspring chromosome;

determining which, if any, of the received parent gene traits are feasible gene traits for the offspring gene locus; and

if it is determined that at least one of the received parent gene traits is feasible, selecting the gene trait of the offspring chromosome at the identified locus from the determined feasible gene traits.

13. A computer-implemented method of determining a gene trait of a chromosome that represents an attempted solution to a problem, the method comprising:

receiving an offspring chromosome having at least one gene having a null trait;

identifying at least one gene of the chromosome having the null trait; and

for at least one of the at least one identified genes;

attempting to determine a feasible gene trait; and

if at least one feasible gene trait is determined, setting the identified gene to one of the feasible gene traits.

14. The method of claim 13, wherein the at least one chromosome gene having the null trait comprises a gene marked for mutation.

15. The method of claim 13, wherein the at least one chromosome gene having the null trait comprises a result of an application of a crossover operation that failed to identify feasible parent gene traits for the gene.

16. The method of claim 13, wherein the chromosome comprises genes having traits selected from alleles identifying resources.

17. The method of claim 16, wherein the locus of the gene identifies a task.

18. A computer program, disposed on a computer-readable medium, for determining a chromosome gene trait of an offspring, the chromosome representing an attempted solution to a problem, the computer program including instructions for causing a processor to:

receive gene traits from parents of the offspring;

receive identification of a gene locus of the offspring chromosome;

determine which, if any, of the received parent gene traits are feasible gene traits for the offspring gene at the identified locus; and

if it is determined that at least one of the received parent gene traits is feasible, select the gene trait of the offspring chromosome at the identified locus from the determined feasible gene traits.

19. The computer program of claim 18, wherein the offspring chromosome expresses an assignment of resources to tasks.

20. The computer program of claim 19, wherein trait alleles comprise alleles specifying resources.

21. The computer program of claim 18, wherein the instructions for causing the processor to determine which of the received traits are feasible comprise instructions for causing the processor to determine which of the received traits are feasible based on a gene trait of an offspring gene at a different locus.

22. The computer program of claim 18, further comprising, instructions for causing the processor to set the offspring gene at the identified locus to the null trait if none of the parent genes traits are feasible.

23. The computer program of claim 22, further comprising instructions for causing the processor to determine whether a gene trait other than the received parent gene traits is feasible.

24. The computer program of claim 18, wherein the parent gene traits comprise gene traits of the parent chromosomes at the identified locus.

25. A comnuter program, disposed on a computer-readable medium, for assigning tasks to resources, the computer program including instructions for causing a processor to:

generate a population of chromosomes, each chromosome having a sequence of genes having a trait selected from alleles that identify the resources, the loci of the genes identifying one of the tasks;

generate offspring from the generated population; and

evaluate the generated offspring;

wherein the instructions for causing the processor to evaluate offspring comprise instructions for causing the processor to determine a scheduling fitness measure.

26. The computer program of claim 25, wherein the scheduling fitness measure comprises a measure based on at least one of the following:

the number of crewmen assigned to a mission, qualifications assigned to a mission, and distribution of assignments among crew-persons.

27. The computer program of claim 25, wherein the instructions for causing the processor to generate offspring comprise instructions for causing the processor to set a chromosome gene trait to a null trait.

28. The computer program of claim 27, further comprising instructions for causing the processor to:

identify a chromosome gene having the null trait; and

select feasible chromosome gene traits, if possible, for the identified chromosome gene.

29. The computer program of claim 25, wherein instructions for causing the processor to generate offspring comprise instructions for causing the processor to:

receive gene traits from parents of the offspring;

receive identification of a gene locus of the offspring chromosome;

determine which, if any, of the received parent gene traits are feasible gene traits for the offspring gene locus; and

if it is determined that at least one of the received parent gene traits is feasible, select the gene trait of the offspring chromosome at the identified locus from the determined feasible gene traits.

30. A computer program, disposed on a computer readable medium, for determining a gene trait of a chromosome that represents an attempted solution to a problem, the computer program including instructions for causing a processor to:

receive an offspring chromosome having at least one gene having a null trait;

identify at least one gene of the chromosome having the null trait; and

for at least one of the at least one identified genes;

attempt to determine a feasible gene trait; and

if at least one feasible gene trait is determined, set the identified gene to one of the feasible gene traits.

31. The computer program of claim 30, wherein the at least one chromosome gene having the null trait comprises a gene marked for mutation.

32. The computer program of claim 30, wherein the at least one chromosome gene having the null trait comprises a result of a crossover operation that failed to identify feasible parent gene traits for the gene.

33. The computer program of claim 30, wherein the chromosome comprises genes having traits selected from alleles identifying resources.

34. The computer program of claim 33, wherein the locus of the gene identifies a task.