特殊調度算法（模式擴展）

Question

問題
您是否認爲遺傳算法值得嘗試解決下面的問題，還是我會遇到局部最小問題？

我認爲這個問題的一些方面對於發電機/健身功能風格的設置來說很好。 （如果你已經搞砸了一個類似的項目，我很樂意聽到你的消息，而不是做類似的事情）

謝謝你有關如何構建東西和指定這個權利的任何提示。

問題
我正在尋找一個很好的調度算法，用於以下現實世界的問題。

我有這樣15個時隙的序列（的位數可能會發生變化，從0至20）：

2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 

（也有在這種類型的總共10個不同的序列）

每個序列需要擴展到一個陣列，其中每個插槽可以佔據1個位置。

1 1 0 0 1 1 1 0 0 0 1 1 1 0 0 
1 1 0 0 1 1 1 0 0 0 1 1 1 0 0 
0 0 1 1 0 0 0 1 1 1 0 0 0 1 1 
0 0 1 1 0 0 0 1 1 1 0 0 0 1 1 

在基質上的約束是：

• [逐行，即，水平]放置者的數目，必須是11或111
• [行方式]的兩個1之間的距離需要至少爲00
• 每列的總和應該與原始數組相匹配。
• 應優化矩陣中的行數。

陣列然後需要分配的4個不同的矩陣之一，其可以具有不同的行數：

A, B, C, D 

A，B，C和d是真實世界的部門。在10天的時間內，負載需要合理公平，而不是干擾其他部門的目標。

每個矩陣與10個不同的原序列的擴展相比，所以你有：

A1, A2, A3, A4, A5, A6, A7, A8, A9, A10 
B1, B2, B3, B4, B5, B6, B7, B8, B9, B10 
C1, C2, C3, C4, C5, C6, C7, C8, C9, C10 
D1, D2, D3, D4, D5, D6, D7, D8, D9, D10 

在這些特定的地點可以被保留（不知道我是否應該做它只是保留/不保留或基於函數）。 保留的地點可能是會議和其他事件

每行（例如所有的A）的總和應該在2％內大致相同。即總和（A1至A10）應該與（B1至B10）大致相同等等

行數可以改變，所以你必須例如：

A1：5行 A2：5行 A3：1列，其中即單列例如可以是：

0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 

等。

子問題*

I'de很HAPP y只解決部分問題。例如能夠輸入：

1 1 2 3 4 2 2 3 4 2 2 3 3 2 3 

並獲得序列的適當陣列，1和0的最小化上按照上述第約束的行的數量。

Answer 1

子問題的解決方案嘗試

嗯，這裏是一個想法。這個解決方案並不是基於使用遺傳算法，但是有一些想法可以用於朝着這個方向前進。

基礎載體

首先，你應該產生什麼，我想爲基礎載體。例如，如果你的順序爲3個數字長，而不是如圖15所示，基本向量將是：

v1 = [1 1 0] 

v2 = [0 1 1] 

v3 = [1 1 1] 

用於序列長度爲3的任何解決方案將是僅使用正整數這三個矢量的線性組合。換句話說，一般的解決方案是

a*v1 + b*v2 + c*v3 

其中a，b和c是正整數。對於序列[1 2 1]，解決方案是v1 = 1，v2 = 1，v3 = 0。你首先想要做的是找到長度爲15的所有可能的基向量。從我的粗略計算中，我認爲那裏在長度爲15的300-400個基向量之間。如果需要，我可以給你一些提示來生成它們。

尋找解決

現在，你想要做的是排序它們的和/大小這些基向量。然後在尋找解決方案時，首先從總量最大的基向量開始。我們從具有最大總和的向量開始，因爲它們導致總行數更少。我們還有一個數組veccoefs，它包含每個基矢量線性係數的條目。在搜索解的開始，所有的veccoefs都是0.所以我們取第一個基矢量（最大和/大小的那個），並從序列中減去這個矢量，直到我們創建一個不可解的結果（例如，其中有0 1 0），或者結果中的任何數字都是負數。我們存儲我們用veccoefs減去矢量的次數。我們使用從序列中減去基本向量之後的結果作爲下一個基本向量的序列。如果結果中只剩下零，那麼我們停止循環。

我不確定這種方法的效率/準確性，但它至少可以給你一些想法。

其他可能的解決方案

解決這一另一個想法是使用的基礎載體和形成問題作爲優化/最小二乘問題。你形成了一個基向量的矩陣，使得基本問題將使Sum [（Ax-b）^ 2]最小化，其中A是基向量矩陣，b是輸入序列，x是基向量係數。但是，您也希望最小化行數，因此您可以將x^T * x等項添加到最小化函數，其中x^T是x的轉置。在我看來，困難的部分是找到可區分的術語來添加，這將鼓勵整數向量係數。如果你可以想辦法做到這一點，那麼優化可能是一個很好的方法來做到這一點。

另外，您可能會考慮Metropolis型蒙特卡羅解決方案。您將隨機選擇是添加矢量，刪除矢量，還是在每一步替換矢量。要添加/刪除/替換的矢量將被隨機選擇。這種變化被接受的概率將是變化之前和變化之後解決方案的適用性的比率。適用性可以等於當前解和序列之間的差，平方和求和，減去解中涉及的行數/基向量數。您需要輸入適當的常數以適應各種術語，以便使驗收率達到50％左右。我有種懷疑，這將工作得很好，但我認爲你應該在尋找可能的解決方案時考慮它。

Answer 2

GA可以應用於這個問題，但它不會是5分鐘的任務。你需要把幾件事情放在一起，而不知道它們各自的哪個實現是最好的。
所以：

1. 解決方案表示 - 你將如何代表可能的解決方案？使用矩陣似乎是最直接的。使用一維數組的收集也是可能的。 但是你有一些限制，所以也許SuperGene概念值得考慮？
2. 對於給定的基因表示，您必須使用適當的變異/交叉算子。
3. 您將如何執行解決方案的限制？摧毀那些不合適的東西？如果它們包含有價值的信息呢？也許讓他們留在人口中，但增加一些罰款的健身，所以他們會貢獻給後代，但不會進入下一代？

無論如何，我認爲GA可以應用於這個問題。這值得嗎？通常遺傳算法並不是最好的算法，但是如果其他算法失敗，它們就是體面的算法。我會和GA一起去，只是因爲它會很有趣，但我會尋找替代解決方案（以防萬一）。

P.S.個人見解：我正在解決N皇后問題，對於70 < N < 100（棋盤NxN，N皇后）。對於較低的N，算法工作正常（可能是嘗試所有的組合？），但是在這個範圍內，我找不到合適的解決方案。健身很快就跳到了最大的90％，但最終總是有兩個皇后相互衝突。但這是非常天真的實施。