Method and system for solving an optimization problem with dynamic constraints

• US 20080270331A1
• Filed: 04/26/2007
• Published: 10/30/2008
• Est. Priority Date: 04/26/2007
• Status: Active Grant

• Current Assignee: 21CT Incorporated
• Original Assignee: 21CT Incorporated
• Inventors: Alford, Lee, Taylor, Darrin
• Granted Patent: US 8,069,127 B2
• Time in Patent Office: Days
• US Class Current: 706/13
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

A method and system for solving an optimization problem comprising a plurality of dynamic constraints. A genetic algorithm is used to iteratively generate potential solutions to the problem. A constraint graph is used to model the plurality of dynamic constraints, and any potential solution that does not correspond to a connected subgraph of the constraint graph is infeasible and discarded. Real-time changes in dynamic constraints are incorporated by modification of the constraint graph between iterations of the genetic algorithm. An exemplary embodiment comprising the scheduling of air missions is presented.

Claims

1. A method of solving an optimization problem comprising a plurality of dynamic constraints, the method comprising the steps of:

creating a constraint graph corresponding to the plurality of dynamic constraints of the optimization problem;

generating a plurality of solutions to the optimization problem using a genetic algorithm having a plurality of iterations;

discarding each one of the plurality of solutions that does not correspond to a connected subgraph of the constraint graph; and

changing one of the plurality of dynamic constraints by modifying the constraint graph, wherein the step of modifying the constraint graph occurs only between iterations of the genetic algorithm.

2. The method of claim 1 in which the optimization problem comprises scheduling a plurality of air missions.

3. The method of claim 1 in which the constraint graph is modified by converting an element of one of the plurality of solutions into an additional constraint in the constraint graph.

4. A method of scheduling a plurality of air missions, comprising the steps of:

creating a constraint graph corresponding to a plurality of air mission constraints;

generating a plurality of proposed air missions using a genetic algorithm having a plurality of iterations;

discarding each one of the plurality of proposed air missions that does not correspond to a connected subgraph of the constraint graph; and

changing one of the plurality of air mission constraints by modifying the constraint graph, wherein the step of modifying the constraint graph occurs only between iterations of the genetic algorithm.

5. The method of claim 4 wherein the plurality of air mission constraints comprises targets, aircraft, bases, munitions, and units.

6. A method for solving an optimization problem having a plurality of constraints, the method comprising the steps of:

using a genetic algorithm to generate a population comprising a plurality of solutions to the optimization problem, the genetic algorithm having a plurality of iterations, wherein each one of the plurality of solutions to the optimization problem is consistent with each one of the plurality of constraints;

between iterations of the genetic algorithm, modifying a first one of the plurality of constraints and removing from the population each of the plurality of solutions in the population that is not consistent with the modified first one of the plurality of constraints.

7. The method of claim 6 further comprising the step of representing the plurality of constraints as a constraint graph, wherein the step of modifying a first one of the plurality of constraints comprises modifying the constraint graph.

8. The method of claim 7 wherein the step of removing from the population each of the plurality of solutions in the population that is not consistent with the modified first one of the plurality of constraints comprises discarding each solution that does not correspond to a connected subgraph of the modified constraint graph.

9. The method of claim 6 wherein the step of modifying at least one of the plurality of constraints comprises replacing a pluggable constraint.

10. The method of claim 6 further comprising the step of replacing a pluggable component of the genetic algorithm.

11. The method of claim 6 further comprising the step of identifying irrelevant solution elements, and the step of using a genetic algorithm to generate a population comprising a plurality of solutions to the optimization problem further comprises the step of ignoring irrelevant solutions.

12. The method of claim 6 wherein the optimization problem comprises scheduling a plurality of air missions.

13. A system for solving an optimization problem having dynamic constraints, comprising:

means for retrievably storing a constraint graph corresponding to the plurality of dynamic constraints;

means for retrievably storing a plurality of solutions to the optimization problem, wherein each one of the plurality of solutions corresponds to a connected subgraph of the constraint graph;

user interface means for outputting one or more of the plurality of solutions;

user interface means for receiving a constraint graph modification;

means for implementing the constraint graph modification in real time; and

genetic algorithm means for optimizing solutions to the optimization problem.

14. The system of claim 13 wherein the optimization problem comprises scheduling a plurality of air missions.

15. A system for solving an optimization problem, comprising:

a memory coupled to a computer, the memory comprising a constraint graph corresponding to a plurality of dynamic constraints of the optimization problem; and

a processing unit coupled to the computer, said processing unit operative to use a genetic algorithm having a plurality of iterations to generate a plurality of candidate solutions to the optimization problem, each one of the plurality of candidate solutions corresponding to a connected subgraph of the constraint graph,

wherein said processing unit is further operative to modify the constraint graph between iterations to reflect a change in at least one of said plurality of dynamic constraints.

16. The system of claim 15 wherein the genetic algorithm includes a pluggable component.

17. The system of claim 15 in which the memory further comprises a static constraint that is not represented in the constraint graph, and the processing unit is further operative to discard any candidate solution that does not comply with the static constraint.

18. The system of claim 17 in which the static constraint is pluggable.

19. The system of claim 15 wherein the optimization problem comprises scheduling a plurality of air missions.

20. A system for solving an optimization problem with a plurality of dynamic constraints, comprising:

a computer comprising a processing unit;

a memory coupled to the processing unit, the memory storing program instructions that when executed by the processor cause the processing unit to;

create a constraint graph corresponding to the plurality of dynamic constraints of the optimization problem;

generate a plurality of solutions to the optimization problem using a genetic algorithm having a plurality of iterations;

discard each one of the plurality of solutions that does not correspond to a connected subgraph of the constraint graph; and

change a dynamic constraint by modifying the constraint graph between iterations of the genetic algorithm.

21. The system of claim 20 in which the optimization problem comprises scheduling a plurality of air missions.

22. A computer readable storage medium comprising instructions for solving an optimization problem having a plurality of dynamic constraints by:

creating a constraint graph corresponding to the plurality of dynamic constraints of the optimization problem;

generating a plurality of solutions to the optimization problem using a genetic algorithm having a plurality of iterations;

discarding each one of the plurality of solutions that does not correspond to a connected subgraph of the constraint graph; and

changing one of the plurality of dynamic constraints by modifying the constraint graph, where the constraint graph is modified only between iterations of the genetic algorithm.

23. The method of claim 22 in which the optimization problem comprises scheduling a plurality of air missions.