基因交叉函數

Question

我正在用Java編寫一個時間表生成器，使用AI方法來滿足硬約束並幫助找到最佳解決方案。到目前爲止，我已經實現了迭代構造（最受限制的第一種啓發式算法）和模擬退火算法，而且我正在實施遺傳算法。

對這個問題的一些信息，以及如何我代表它，然後： 我有一組事件，房間功能（即事件需要和房間滿足），學生和插槽 的問題在於分配給每個事件老虎機和一個房間，這樣就不需要學生在一個時間段內參加兩個活動，所有分配的房間都滿足了必要的要求。

我有一個等級的功能，爲每套如果分配檔次的軟約束違規，因此關鍵是要儘量減少這種。

我實施遺傳算法的方式是從迭代構建（可以將事件未分配）生成的種羣開始，然後執行正常步驟：評估，選擇，交叉，變異並保持最佳狀態。沖洗並重復。

我的問題是，我的解決方案似乎改善太少。無論我做什麼，人口往往會隨機適應，並在那裏停滯不前。請注意，這種健身總是不同的，但是會出現下限。

我懷疑問題出在我的交叉功能，這裏是一個道理：

兩個任務是隨機選擇交叉。讓我們稱之爲分配A和B.對於所有B的事件，執行以下程序（順序B的事件都被選中是隨機的）：

獲取一個對應的事件，並比較分配。 3種不同的情況可能發生。

• 如果只有其中一個未分配，並且如果有可能在子項上覆制另一個分配，則選擇此分配。
• 如果兩者都被分配，但只有一個分配給孩子的時候不產生
  衝突，一個選擇。
• 如果它們都被分配並且沒有創建衝突，則它們是隨機選擇的 。

在任何其他情況下，該事件被留下未分配的。

這將創建一個孩子的一些家長的任務，一些母親的，所以在我看來，這是一個有效的功能。而且，它並沒有打破任何硬性限制。

至於突變，我用我的SA鄰近的功能給我基於對孩子的另一項任務，然後更換這個孩子。

再次。通過這種設置，初始人口數爲100，GA運行並始終趨於穩定在某個隨機（高）適應值。有人能給我一個關於我可能做錯什麼的指針嗎？

感謝

編輯：格式化並清除一些事情

Answer 1

我認爲，如果解決方案的一部分（向量的一部分）GA纔有意義，具有意義，因爲該解決方案的一個獨立部分，所以交叉函數在兩個解向量之間集成了解的有效部分。很像DNA序列的某個部分控制或影響個體的特定方面 - 例如，眼睛的顏色就是一個基因。然而，在這個問題中，解矢量的不同部分互相影響，使交叉幾乎毫無意義。這個結果（我的猜測）在算法收斂在一個單一的解決方案，相當迅速與不同的交叉和突變對健身只有負面影響。

我不相信GA是這個問題的正確工具。

Answer 2

如果您可以請提供原始問題陳述，我將能夠給你一個更好的解決方案。這是我目前的答案。

遺傳算法不是滿足硬約束的最佳工具。這是一個可以使用整數程序解決的分配問題，它是一個線性程序的特例。

線性程序允許用戶最小化或最大化某個由目標函數（分級函數）建模的目標。目標函數由個體決策（或決策變量）和目標函數的值或貢獻的總和來定義。線性程序允許您的決策變量爲十進制值，但整數程序會強制決策變量爲整數值。

那麼，你的決定是什麼？你的決定是分配學生插槽。這些插槽具有事件需要和房間滿足的功能。

在你的情況下，你想最大限度地分配給一個插槽的學生人數。

您也有約束。就你而言，一名學生最多隻能參加一項活動。

下面的網站提供了一個關於如何爲整型程序建模的很好的教程。

http://people.brunel.ac.uk/~mastjjb/jeb/or/moreip.html

對於Java具體實現，使用下面的鏈接。

http://javailp.sourceforge.net/

SolverFactory factory = new SolverFactoryLpSolve(); // use lp_solve 
factory.setParameter(Solver.VERBOSE, 0); 
factory.setParameter(Solver.TIMEOUT, 100); // set timeout to 100 seconds 

/** 
* Constructing a Problem: 
* Maximize: 143x+60y 
* Subject to: 
* 120x+210y <= 15000 
* 110x+30y <= 4000 
* x+y <= 75 
* 
* With x,y being integers 
* 
*/ 
Problem problem = new Problem(); 

Linear linear = new Linear(); 
linear.add(143, "x"); 
linear.add(60, "y"); 

problem.setObjective(linear, OptType.MAX); 

linear = new Linear(); 
linear.add(120, "x"); 
linear.add(210, "y"); 

problem.add(linear, "<=", 15000); 

linear = new Linear(); 
linear.add(110, "x"); 
linear.add(30, "y"); 

problem.add(linear, "<=", 4000); 

linear = new Linear(); 
linear.add(1, "x"); 
linear.add(1, "y"); 

problem.add(linear, "<=", 75); 

problem.setVarType("x", Integer.class); 
problem.setVarType("y", Integer.class); 

Solver solver = factory.get(); // you should use this solver only once for one problem 
Result result = solver.solve(problem); 

System.out.println(result); 

/** 
* Extend the problem with x <= 16 and solve it again 
*/ 
problem.setVarUpperBound("x", 16); 

solver = factory.get(); 
result = solver.solve(problem); 

System.out.println(result); 
// Results in the following output: 

// Objective: 6266.0 {y=52, x=22} 
// Objective: 5828.0 {y=59, x=16} 

Answer 3

我會通過測量什麼直接去上啓動。例如，你的「任何其他情況」下的所有任務中的哪一部分都屬於這種情況，因此什麼都不做？

此外，雖然我們無法從所給出的信息中真實地分辨出來，但似乎沒有任何舉動可以做「交換」，這可能是一個問題。如果日程安排受到嚴格限制，那麼一旦您找到可行的方案，您可能無法將班級從A房間移動到B房間，因爲B房間正在使用。您需要考慮將課程從A移動到B以及將課程從B移動到A的方法。

您有時也可以通過違反約束條件來改進內容。您可以允許它違反約束條件，而不是禁止交叉，但會違反違規的「壞處」比例來懲罰它。

最後，您的其他操作員可能也是問題所在。如果您的選擇和替換操作員過於激進，您可以非常快速地收斂到比您剛剛開始時略好的地方。一旦你收斂，單靠突變就很難將你帶回高效搜索。

Answer 4

我認爲遺傳算法對這個問題沒有任何問題，有些人只是討厭遺傳算法而已。

這裏是我會檢查：

首先，你提到你的GA穩定在一個隨機的「高」的健身價值，但不是一個很好的事情嗎？在你的情況下，「高」健身對應於好還是壞？有可能你偏愛你的代碼中的「高」健身和另一部分中的「低」健身，從而導致看似隨機的結果。

我認爲你希望對交叉操作背後的邏輯更加謹慎。基本上，對於所有這三種情況，在許多情況下，做出這些選擇並不會增加所有交叉個體的適應度，但是您仍在使用「資源」（可能會用於另一個班級/學生/等）我意識到遺傳算法傳統上會通過交叉作出任務，導致更糟糕的行爲，但你已經在交叉階段進行了一些計算，爲什麼不選擇一個實際上會改善健身或者可能不會一點都不交叉？

要考慮的可選註釋：儘管您的迭代構建方法非常有趣，但這可能會導致您的基因表示過於複雜，從而可能導致交叉問題。是否有可能將單個解決方案建模爲位或整數的數組（或二維數組）？即使陣列變得很長，也可能使用更簡單的交叉程序。我建議谷歌搜索「ga gene representation time tabling」，你可能會發現一種你更喜歡的方法，並且可以更容易地擴展到許多個人（100是GA的一個相當小的人口規模，但我知道你還在測試，代？）。

最後一點說明，我不確定你在使用什麼語言，但如果是Java而且你不需要手工編寫GA，我建議看看ECJ。也許即使你必須手工編寫代碼，它可以幫助你開發你的代表或繁殖管道。

Answer 5

新到GA可以使任意數量的標準錯誤：

• 在一般情況下，做交叉時，確保孩子有繼承的是這讓父母或父母的贏家一定的機率（ s）首先。換句話說，選擇一個基因組表示，其中基因組的「基因」片段對問題陳述有意義的映射。一個常見的錯誤是將所有東西都編碼爲一個位矢量，然後在交叉處將隨機位置分開，將位矢量代表的好東西分開，從而破壞使個體浮動到最佳位置的東西，作爲一個好候選。 （有限）整數的向量可能是一個更好的選擇，整數可以被替換爲突變而不是交叉。不保留什麼東西（不一定是100％，但它必須是某個方面）讓父母贏家意味着你基本上在進行隨機搜索，這不會比線性搜索更好。

• 一般來說，使用比您想象的更少的突變。突變主要是爲了保持人口的多樣性。如果您的初始人羣不包含任何具有分數優勢的事物，那麼您的人口對於手頭的問題而言太小，並且高突變率通常不會有幫助。

• 在這種特殊情況下，您的交叉功能太複雜了。千萬不要施加限制，以保證所有解決方案對於交叉有效。相反，交叉功能應該可以自由生成無效的解決方案，並且這是有點（不是總共）懲罰無效解決方案的目標函數的工作。如果您的GA工作，那麼最終答案將不包含任何無效分配，只要100％有效分配完全可能。堅持交叉有效性可以防止有效的解決方案通過無效的解決方案將快捷方式帶到其他更好的有效解決方案。

我會建議任何人誰認爲他們已經寫了表現不佳的GA進行以下測試：運行GA幾次，並注意輩份數花了達到可接受的結果。然後用隨機選擇替換贏家選擇步驟和目標函數（無論您使用的是錦標賽，排名等），然後再次運行。如果你仍然以與真正的評估者/目標函數大致相同的速度收斂，那麼你實際上並沒有運行GA。許多說GAs不工作的人在他們的代碼中犯了一些錯誤，這意味着GA收斂速度慢到隨機搜索足夠讓任何人離開這項技術。