Description
About the problem:
The WTA is a well-known optimization problem. Given a set of weapons of various types and a set of targets, we want to find the optimal assignment of the weapons to the targets in order to minimize the total expected threat coming from the targets. A target can have more than one weapon (of the same or a different type) assigned to it. On the other hand, a single weapon instance can only be assigned to one target (explained in the example).
What you are required to do:
Write a genetic algorithm to solve the WTA problem.
What the input looks like:
You’ll be given the weapon types, the number of each weapon type, the number of targets, the threat coefficient (V) of each target and a matrix containing the success probabilities of each weapon type against each target.
Example:
| Enter the weapon types and the number of instances of each type: (Enter
“x” when you’re done) Tank 2 Aircraft 1 Grenade 2 x
Enter the number of targets: 3
Enter the threat coefficient of each target: 16 5 10
Enter the weapons’ success probabilities matrix: 0.3 0.6 0.5 0.4 0.5 0.4 0.1 0.2 0.2
Please wait while running the GA…
The final WTA solution is: Tank #1 is assigned to target #1, Tank #2 is assigned to target #3, Aircraft #1 is assigned to target #1, Grenade #1 is assigned to target #2, Grenade #2 is assigned to target #2,
The expected total threat of the surviving targets is 14.92 |
The weapons’ success probabilities matrix in this example means that:
- A tank has a 0.3 probability of damaging target #1, a 0.6 probability of damaging target #2 and a 0.5 probability of damaging target #3.
- An aircraft has a 0.4 probability of damaging target #1, a 0.5 probability of damaging target #2 and a 0.4 probability of damaging target #3.
- A grenade has a 0.1 probability of damaging target #1, a 0.2 probability of damaging target #2 and a 0.2 probability of damaging target #3.
Note 1: Your final solution doesn’t have to match the one in this example, but it should produce low threat. You could also display the output in a different format.
Note 2: A single weapon instance can only be assigned to one target, so for example, grenade #1 is assigned to only one target (target #2) but target #2 has more than one weapon assigned to it (whatever the weapon type is).
Important remarks to help you solve the problem:
- The first thing you need to do is to think about how you will encode the solution in your chromosome. Formulate the problem with the objective function and constraints to help you figure out the next steps.
- You should use a binary, one-dimensional
- The population size and initialization method you use are up to you. You can actually try different population sizes to see how this will affect your results. The maximum number of generations is also up to you.
- Think about your fitness function. It should be a function that measures the objective: minimize the expected total threat of the surviving targets.
Note: You are given the probability of target damage in a matrix which means that you can get the probability of target survival and use it in your equation!
- Think about how you will handle infeasible solutions. Infeasible solutions are solutions that violate the constraints of the problem; therefore, they are not allowed.
- Choose the methods and parameters of selection, crossover, mutation and replacement that you find appropriate.
