Real-time optimization of allocation of resources

• US 8,238,924 B2
• Filed: 04/30/2010
• Issued: 08/07/2012
• Est. Priority Date: 04/30/2010
• Status: Active Grant

• Current Assignee: the united states of america as represented by the secretary of the navy
• Original Assignee: the united states of america as represented by the secretary of the navy
• Inventors: Eberhart, Russell C., Hu, Xiaohui, Shaffer, Patrick J.
• Primary Examiner(s): Nguyen, Tu X
• Application Number:
  US12/771,912
• Publication Number:
  US 20110269491A1
• Time in Patent Office: 830 Days
• Field of Search: 455/101, 455/509, 455/450, 455/451, 455/67.11
• US Class Current: 455/450
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

Embodiments of a system and a method for assigning a plurality of resources to a plurality of targets in near real-time are described herein. An evolutionary algorithm such as a particle swarm algorithm iteratively evaluates a predetermined fitness function characteristic of a system including the plurality of resources to find solutions containing optimal resource assignments. Resource parameters are changed based on the assignments to operate on the targets.

Claims

1. A storage medium operable by a processing device to dynamically assign a plurality of resources to a plurality of targets, the storage medium comprising:

a first processing sequence to receive target information representing characteristics of the plurality of targets and to store the information in the storage medium;

a data structure comprising a plurality of particle data corresponding to a particle population, each particle data including a velocity and a position of a particle of the particle population;

a second processing sequence updating the plurality of particle data according to a predetermined formula and generating a plurality of fitness values based on the information, the plurality of fitness values corresponding to a plurality of potential solutions;

a third processing sequence iteratively invoking the second processing sequence to improve the plurality of potential solutions by comparing fitness values in preceding and succeeding iterations;

a fourth processing sequence defining a decision criterion to select from the improved plurality of solutions a best solution which satisfies the decision criterion, the best solution from the improved plurality of solutions comprising assignments for the plurality of resources; and

a fifth processing sequence to communicate the assignments to the plurality of resources when the storage medium is communicatively coupled to the processing device and the plurality of resources; and

a sixth processing sequence to invoke the third processing sequence independently at least twice thereby generating at least a first best solution and a second best solution corresponding to a first particle population and a second particle population,

wherein the fourth processing sequence selects an overall best solution from at least the first best solution and the second best solution, and

wherein the first, second, third, fourth, fifth and sixth processing sequences are operable to receive the target information, select an overall best solution and communicate the assignments at least once each second.

2. A storage medium as in claim 1, wherein the plurality of resources are electromagnetic (EM) resources and the plurality of targets are signals, and the assignments comprise center-frequencies for the plurality of EM resources to enable the plurality of EM resources to receive or override the plurality of signals within the bandwidths of the plurality of EM resources.

3. A storage medium as in claim 2, wherein the target information comprises at least one of signal power, signal modulation, signal frequency, and signal priority.

4. A storage medium as in claim 1, wherein the decision criterion comprises one of a predetermined fitness value, a number of iterations, and a difference between successive fitness values of successive best solutions being within 5% of an average fitness value of the successive best solutions.

5. A storage medium operable by a processing device to dynamically assign a plurality of resources to a plurality of targets, and the storage medium comprising:

a first processing sequence to receive target information representing characteristics of the plurality of targets and to store the information in the storage medium;

a data structure comprising a plurality of particle data corresponding to a particle population, each particle data including a velocity and a position of a particle of the particle population;

a second processing sequence updating the plurality of particle data according to a predetermined formula and generating a plurality of fitness values based on the information, the plurality of fitness values corresponding to a plurality of potential solutions;

a third processing sequence iteratively invoking the second processing sequence to improve the plurality of potential solutions by comparing fitness values in preceding and succeeding iterations;

a fourth processing sequence defining a decision criterion to select from the improved plurality of solutions a best solution which satisfies the decision criterion, the best solution from the improved plurality of solutions comprising assignments for the plurality of resources; and

a fifth processing sequence to communicate the assignments to the plurality of resources when the storage medium is communicatively coupled to the processing device and the plurality of resources;

wherein the first, second, third, fourth and fifth processing sequences are operable to receive the target information, select a best solution and communicate the assignments at least once each second.

6. A storage medium as in claim 5, further including a seventh processing sequence configured to upload the second processing sequence defining the predetermined formula.

7. A storage medium as in claim 5, further including an eight processing sequence configured to select the second processing sequence defining the predetermined formula from a plurality of second processing sequences stored in the storage device.

8. A storage medium as in claim 5, further including a ninth processing sequence configured to enable a user to select a number of particle populations corresponding to the number of invocations of the third processing sequence by the sixth processing sequence.

9. A storage medium operable by a processing device to dynamically assign a plurality of resources to a plurality of targets, and the storage medium comprising:

a first processing sequence to receive target information representing characteristics of the plurality of targets and to store the information in the storage medium;

a data structure comprising a plurality of particle data corresponding to a particle population, each particle data including a velocity and a position of a particle of the particle population;

a second processing sequence updating the plurality of particle data according to a predetermined formula and generating a plurality of fitness values based on the information, the plurality of fitness values corresponding to a plurality of potential solutions;

a third processing sequence iteratively invoking the second processing sequence to improve the plurality of potential solutions by comparing fitness values in preceding and succeeding iterations;

a fourth processing sequence defining a decision criterion to select from the improved plurality of solutions a best solution which satisfies the decision criterion, the best solution from the improved plurality of solutions comprising assignments for the plurality of resources; and

a fifth processing sequence to communicate the assignments to the plurality of resources when the storage medium is communicatively coupled to the processing device and the plurality of resources;

wherein decision criterion comprises one of a predetermined fitness value, a number of iterations, and a difference between successive fitness values of successive best solutions being within 5% of an average fitness value of the successive best solutions.

10. A storage medium operable by a processing device to dynamically assign a plurality of resources to a plurality of targets, and the storage medium comprising:

a first processing sequence to receive target information representing characteristics of the plurality of targets and to store the information in the storage medium;

a data structure comprising a plurality of particle data corresponding to a particle population, each particle data including a velocity and a position of a particle of the particle population;

a second processing sequence updating the plurality of particle data according to a predetermined formula and generating a plurality of fitness values based on the information, the plurality of fitness values corresponding to a plurality of potential solutions;

a third processing sequence iteratively invoking the second processing sequence to improve the plurality of potential solutions by comparing fitness values in preceding and succeeding iterations;

a fourth processing sequence defining a decision criterion to select from the improved plurality of solutions a best solution which satisfies the decision criterion, the best solution from the improved plurality of solutions comprising assignments for the plurality of resources;

a fifth processing sequence to communicate the assignments to the plurality of resources when the storage medium is communicatively coupled to the processing device and the plurality of resources; and

further comprising a sixth processing sequence to invoke the third processing sequence independently at least twice thereby generating at least a first best solution and a second best solution corresponding to a first particle population and a second particle population, and wherein the fourth processing sequence selects an overall best solution from at least the first best solution and the second best solution.

11. A storage medium as in claim 10, wherein the fourth processing sequence selects the overall best solution when at least the first best solution and the second best solution converge and otherwise returns control to the third processing sequence.

12. A storage medium as in claim 11, wherein the fourth processing sequence selects as the overall best solution whichever of the first best solution and the second best solution has the best fitness value.

13. A storage medium as in claim 10, wherein the fourth processing sequence selects the overall best solution when a majority of best solutions from a plurality of particle populations converge and otherwise returns control to the third processing sequence.

14. A method of manufacturing a component of a resource allocation system, the allocation system having a plurality of resources assignable to a plurality of targets, the method comprising the steps of:

storing in a storage device a first processing sequence to receive target information representing characteristics of the plurality of targets and to store the information in the storage medium;

storing in the storage device a data structure comprising a plurality of particle data corresponding to a particle population, each particle data including a velocity and a position of a particle of the particle population;

storing in the storage device a second processing sequence updating the plurality of particle data according to a predetermined formula and generating a plurality of fitness values based on the information, the plurality of fitness values corresponding to a plurality of potential solutions;

storing in the storage device a third processing sequence iteratively invoking the second processing sequence to improve the plurality of potential solutions by comparing fitness values in preceding and succeeding iterations;

storing in the storage device a fourth processing sequence defining a decision criterion to select from the improved plurality of solutions a best solution which satisfies the decision criterion, the best solution from the improved plurality of solutions comprising assignments for the plurality of resources; and

storing in the storage device a fifth processing sequence to communicate the assignments to the plurality of resources when the storage medium is communicatively coupled to the processing device and the plurality of resources; and

storing in the storage device a sixth processing sequence to invoke the third processing sequence independently at least twice thereby generating at least a first best solution and a second best solution corresponding to a first particle population and a second particle population,

wherein the fourth processing sequence selects an overall best solution from at least the first best solution and the second best solution, and

wherein the first, second, third, fourth and fifth processing sequences are operable to receive the target information, select a best solution and communicate the assignments at least once each second.

15. A method of manufacturing a component of a resource allocation system as in claim 14, wherein the plurality of resources are electromagnetic (EM) resources and the plurality of targets are signals, and the assignments comprise center-frequencies for the plurality of EM resources to enable the plurality of EM resources to receive or override the plurality of signals within the bandwidths of the plurality of EM resources.

16. A method of manufacturing a component of a resource allocation system as in claim 15, wherein the target information comprises at least one of signal power, signal modulation, signal frequency, and signal priority.

17. A method of manufacturing a component of a resource allocation system as in claim 14, wherein the decision criterion comprises one of a predetermined fitness value, a number of iterations, and a difference between successive fitness values of successive best solutions being within 5% of an average fitness value of the successive best solutions.

18. A method of manufacturing a component of a resource allocation system as in claim 14, wherein the decision criterion comprises one of a predetermined fitness value, a number of iterations, and a difference between successive fitness values of successive best solutions being within 5% of an average fitness value of the successive best solutions.

19. A resource allocation system configured to detect signals within an operational bandwidth and dynamically respond to the signals to meet operational objectives, the system comprising:

a plurality of EM resources, each of the plurality of EM resources including an antenna and at least one of a receiving portion and a transmitting portion for receiving or responding to the signals within an EM resource bandwidth at an assignable center-frequency;

a processing device communicatively coupled to the plurality of EM resources and receiving, at frequent intervals, information about the signals, the processing device including a storage device having a fitness function and an evolutionary algorithm stored therein, the fitness function representing the operational objectives and determining a fitness value of a potential solution based on the information about the signals, the evolutionary algorithm generating a plurality of potential solutions, iteratively improving the plurality of solutions by comparing fitness values in preceding and succeeding iterations, and selecting a best solution from the improved plurality of solutions based on a predetermined criterion, the best solution comprising center-frequencies for the plurality of EM resources, and the processing device communicating the center-frequencies comprised in the best solution to the plurality of EM resources to assign the EM resources to the signals.

20. A resource allocation system as in claim 19, wherein the predetermined criterion comprises one of completion of a predetermined number of iterations, achievement of a predetermined fitness value, and a difference in the fitness values of consecutive best potential solutions being less than a predetermined amount.

21. A resource allocation system as in claim 20, wherein the predetermined amount is within 5% of the iteration fitness value.

22. A resource allocation system as in claim 19, wherein at least one of the plurality of EM resources scans the operating bandwidth of the resource allocation system to detect the signals and communicates at least a portion of the information about the signals to the processing device.

23. A resource allocation system as in claim 19, wherein the information about the signals includes at least one of priority, modulation pattern, power, and frequency.

24. A resource allocation system as in claim 19, wherein each of the intervals comprises less than a second.

25. A resource allocation system as in claim 19, wherein the evolutionary algorithm is a particle swarm algorithm including a particle swarm population having a plurality of particles, each of the particles having a velocity and a location parameter operable to determine the fitness value of the particle and a potential solution of the plurality of solutions.

26. A resource allocation system as in claim 25, wherein the particle swarm algorithm is a gaming particle swarm algorithm including two or more particle swarm populations.

27. A resource allocation system as in claim 26, wherein the predetermined criterion comprises convergence of the two or more particle swarm populations on the best solution.

28. A resource allocation system as in claim 25, wherein particle swarm algorithm compares the best solution from each of the two or more particle swarm populations after each iteration, and the predetermined criterion is achieved when a majority of the best solutions after each iteration converge.