Artificial Intelligence Question posted in
ChatGBT is becoming a world-wide phenomena, try it out here.

Soldiers guarding the city wall – homework assignment – Artificial Intelligence

I’ve got an assignment in my Artificial Intelligence class.

It is a problem which we have to solve using Genetic Algorithms in R (using GA library). I’m looking for some ideas how to approach this.

Description

Barbarians siege a city. General gives an order how many soldiers must guard a city wall on each hour during a day. This is his table:

Time of the day | Number of soldiers
00:00 - 01:00   150
01:00 - 02:00   160
02:00 - 03:00   160
03:00 - 04:00   170
04:00 - 05:00   350
05:00 - 06:00   380
06:00 - 07:00   400
07:00 - 08:00   420
08:00 - 09:00   450
09:00 - 10:00   470
10:00 - 11:00   500
11:00 - 12:00   500
12:00 - 13:00   450
13:00 - 14:00   350
14:00 - 15:00   300
15:00 - 16:00   300
16:00 - 17:00   310
17:00 - 18:00   350
18:00 - 19:00   350
19:00 - 20:00   330
20:00 - 21:00   300
21:00 - 22:00   250
22:00 - 23:00   200
23:00 - 24:00   170

Commander of defense wants the soldiers to be completely focused, when they are on patrol, so he gives this order:

  • Each soldier in guarding the wall for exactly 6 hours in a day (24 hours): 4 hours on the wall, then he rests for 2 hours and then he gets back on the wall for another 2 hours
  • The solders who start right before midnight, continue on the morning of the next day – algorithm must consider continuity of the days.
    How many soldiers are required to keep guarding the wall?

My ideas so far

Two of possible aproaches (so far):

First approach

Fitness function of GA would accept a number of solders and then perform a simulation:

  • Set initial score to 0.
  • If during the simulation there would be lack or excess of the soldiers in the city then subtract from score.
  • Optimal solution is when score is zero (number of required soldiers is optimal).

Second approach

Create a initial population (solders) and apply the rules from the commander in the fitness function (I don’t really know how to define the above rules here) and then run GA until we get some useful score.

Tags:

4

Answers


  1. 0

    Here are the soldiers we need for each hour

    soldiers
#  150 160 160 170 350 380 400 420 450 470 500 500 450 350 300 300 310 350 350
# 330 300 250 200 170

    So we need:

    sum(soldiers)
# 7770

    But each soldier works for 6 hours guarding the wall so:

    sum(soldiers)/6
# 1295

    Now the problem come how to fit the rules: I would say that the 2 hours rest is a minimal not a must. I don’t see the point of it and it will lead to problems (we will need more soldiers than 1295)
    This is a starting point instead of 0 to start from 1295. So I would go for the first approach even though I don’t know anything about the GA library.

    Login or Signup to reply.
  2. 0

    I think that the first approach is not the genetic algorithm. According to me GA starts with some initial population and the fitness function is used to choose the best individuals in the population.

    However, I would define the initial population in the different way than you. It should be a collection of numbers in which each number denotes the number of soldiers in the city. For example individual 1 represents 10 soldiers, individual 2 represents 120 soldiers, individual N represents 680 soldiers.

    Then in each step of GA you should select (based on the fitness function) the best individuals i.e. numbers that are the most optimal. These individuals will be used to create a new generation using genetic operators like crossover and mutation. For example crossover can be defined as calculating average value of two numbers.

    As to fitness function. It should determine if a given number of soldiers is optimal or not. By optimal, I mean information if there are too many (some soldiers are bored) or too little (there is not enough soldiers on the walls) soldiers in the city.

    You should run GA until the best individual will be good enough from your perspective.

    Plese note that it is a homework and this problem can be solved without the genetic algorithm.

    Login or Signup to reply.
  3. 0

    My approach would be to have individuals in the population to represent a number of soldiers AND an assignment of those soldiers to shifts. So, for 300 soldiers, a chromosome would need 300 numbers between 0 and 23 (assuming each soldier takes the same shift everyday), marking the time he starts his 6 hours, but not every individual in the population would have a chromosome of the same length. Some individual would be an assignment of 300 soldiers, other would be 500 soldiers. I’m unfamiliar with the GA libraries in R but this is something they should be capable of handling.

    Now, given an individual and the assignment of every soldier to a shift, you can use the rules of the problem to easily compute how many soldiers are guarding the wall at every hour. Your goal is to get this schedule as close as possible to the General orders, so your fitness function (which the GA will maximize) should be inversely proportional to the difference between the resulting schedule and the General orders. When the difference is 0 you have found the optimal solution.

    You can add additional bias and constraints. Say, if you don’t want any solution where the wall is under guarded, you can give a specially low fitness to those individuals.

    Login or Signup to reply.
  4. 0

    Since the assignment is over (yes, I go to the same class as OP) and this is an actually interesting problem, I’m posting my solution here:

    library(GA)

Fitness <- function(x) {
    x <- as.integer(x)
    # z represents required soldiers at each hour
    z <- c(150,160,160,170,350,380,400,420,450,470,500,500,450,350,300,300,310,350,350,330,300,250,200,170)
    y <- rep(0,31)
    for (i in 1:length(x)) {
        y[i] <- y[i] + x[i]
        y[i+1] <- y[i+1] + x[i]
        y[i+2] <- y[i+2] + x[i]
        y[i+3] <- y[i+3] + x[i]
        #resting 4, 5
        y[i+6] <- y[i+6] + x[i]
        y[i+7] <- y[i+7] + x[i]
    }
    for (i in 1:7) {
        y[i] <- y[i]+y[24+i]
    }
    y <- y[1:24]
    p <- y >= z
    if (FALSE %in% p) { return(-3000) }
return(-sum(x))
}

GA <- ga(type = "real-valued", fitness = Fitness, min = rep(0, 24), max = rep(150, 24), popSize = 24, suggestions = sol, maxiter = 5000, run = 5000, pmutation=0.9)

summary(GA)
sol <- (as.integer(GA@solution[1, ]))
sol
sum(sol)

    The GA generates a vector of numbers of soldiers that START their watch each hour (there is 24 hours, that’s why 24 zeros and 24 times 150), and calls the Fitness function with said vector.

    The Fitness function first converts real numbers to integers (R as.integer function just strips off any number after decimal point, no rounding), and assigns the soldier to its 6 hours of work. It does that by adding the number of soldiers that start at x[i] to y[i, i+1, ... i+7] without those two hours when soldiers are resting.

    Because the soldiers guard around the clock, those last 7 hours in the y are added to the first 7 hours of y and then only first 24 values of y are considered.

    Then we compare the generated vector of soldiers on the watch to the required one, and if there are any FALSEs in the vector, Fitness returns a very big negative number (GA always takes bigger number as a better one).

    In the end we want to ‘hire’ as little soldiers as possible, that’s why we negate the result (lower number of soldiers required = higher negated number) so the GA finds the best result.

    The rest is pretty self explanatory, we call the GA function, we fiddle with its settings and display the result.

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search