守衛城牆的士兵 - 家庭作業

Question

我在人工智能課上有一項任務。

這是一個問題，我們必須解決使用R遺傳算法（使用GA庫）。我正在尋找一些如何解決這個問題的想法。

描述

野蠻人圍攻城市。將軍命令一天中每小時有多少士兵必須守衛城牆。這是他的表：

防禦

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 

指揮官希望兵來將完全集中，當他們在巡邏，所以他給出了這樣的命令：

• 守衛在牆上整整6每個士兵小時（24小時）：在牆上4小時，然後他休息2小時，然後他又回到牆上再過2小時
• 在午夜之前開始的焊料，繼續在第二天 - 算法必須考慮日子的連續性。 需要多少名士兵才能守護城牆？

我的想法而已

可能aproaches中的兩個（到目前爲止）：

第一種方法

GA的

健身功能會接受一些焊料，然後進行模擬：

• 將初始分數設置爲0.
• 如果在模擬將會有城市中的士兵缺乏或多餘，然後從分數中減去。
• 最佳解決方案是當分數爲零時（所需士兵數量最佳）。

第二條本辦法

創建初始羣體（焊料），並在健身功能指揮官適用規則（我真的不知道如何定義這裏的上述規則），然後運行GA直到我們得到一些有用的分數。

Answer 1

由於分配結束（是的，我去同一個類作爲OP），這是一個真正有趣的問題，我在這裏發佈我的解決方案：

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) 

的GA產生的矢量每小時開始觀看的士兵人數（有24小時，這就是爲什麼24個零和24個150），並且用所述向量調用Fitness函數。

健身功能首先將實數轉換爲整數（R as.integer功能只消除小數點後的任意數字，不捨入），併爲士兵分配6小時的工作時間。它通過在士兵休息時沒有那兩個小時的情況下將x[i]開始的士兵人數增加到y[i, i+1, ... i+7]來實現。

由於士兵全天候守護，在y那些最後7小時被添加到第一7小時的y然後僅第一24的y值被考慮。

然後我們會比較手錶所需的一個士兵所產生的載體，如果有任何FALSE S IN的矢量，Fitness返回一個非常大的負數（GA始終把比較大的數字作爲一個更好的）。最後，我們希望儘可能地「僱用」儘可能少的士兵，這就是爲什麼我們否定了結果（需要的士兵數量更少=否定數更高），因此GA找到了最好的結果。

其餘的都很自我解釋，我們稱GA功能，我們擺弄它的設置並顯示結果。

Answer 2

。這是我們需要爲每個小時

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 

戰士因此，我們需要：

sum(soldiers) 
# 7770 

但每個士兵工作6小時守着牆這樣：

sum(soldiers)/6 
# 1295 

現在問題來了如何適應規則：我會說，休息2小時是最小的不是必須的。我沒有看到它的重點，它會導致問題（我們將需要更多的士兵比1295）
這是一個起點，而不是0從1295開始。所以我會去第一種方法，即使我對GA圖書館一無所知。

Answer 3

我認爲第一種方法不是遺傳算法。據我所知，遺傳算法從一些初始種羣開始，用適應度函數來選擇種羣中最好的個體。

但是，我會以與你不同的方式定義初始人口。它應該是一組數字，其中每個數字表示城市中的士兵數量。例如，個人1代表10個士兵，個人2代表120個士兵，個人N代表680個士兵。

然後在遺傳算法的每一步中，您應該選擇（基於適應度函數）最佳個體，即最優的個體。這些人將被用來創造使用遺傳算子如交叉和變異的新一代。例如，交叉可以被定義爲計算兩個數字的平均值。

至於健身功能。它應該確定給定數量的士兵是否最優。通過最優化，我的意思是說，如果城市中有太多（有些士兵無聊）或太少（牆上沒有足夠的士兵）士兵，就會有信息。

你應該運行GA，直到最好的個人從你的角度來看足夠好。

請注意，這是一個家庭作業，這個問題可以解決沒有遺傳算法。

Answer 4

我的方法是讓人口中的個人代表一些士兵並指派這些士兵輪班。因此，對於300名士兵來說，染色體需要0到23之間的300個數字（假設每個士兵每天都進行相同的移位），標記他開始6小時的時間，但並不是每個人都有相同的染色體長度。有些人將分配300名士兵，其他人則是500名士兵。我不熟悉R中的GA庫，但這是他們應該能夠處理的。

現在，考慮到一個人和每個士兵的輪班任務，您可以使用問題規則輕鬆計算每個小時有多少士兵守衛隔離牆。您的目標是儘可能接近一般訂單，因此您的健身功能（GA將最大化）應該與生成的時間表和常規訂單之間的差異成反比。當差值爲0時，您已找到最佳解決方案。

您可以添加其他偏見和約束。比如說，如果你不想在牆上有人看守的地方提供任何解決方案，你可以給這些人特別低的健身。