使用遺傳算法優化人員規劃

> Chromosomes are an important element of genetics. Photo by National Cancer Institute on Unsplash.

遺傳算法

遺傳算法是模仿自然選擇過程的優化算法。 他們沒有使用"數學技巧"，而是僅復制了我們知道其有效的邏輯。

遺傳算法中的自然選擇

這種自然選擇的過程以適者生存為基礎：自然界中能使最佳個體（動物，植物或其他）生存的過程。 然后，這些優勝劣汰的人彼此交配，產生了新一代。 大自然還以基因組突變的形式增加了一些隨機性。

新生代是好人和壞人的混合體，但是在這里，好人將繼續生存，交配，然后產生新一代。

結果是一代又一代的持續改進。

員工計劃的遺傳算法

人員計劃是優化研究的主題，許多公司都對此進行了介紹。 一旦公司擁有許多員工，就很難在滿足某些約束的同時找到適合業務需求的計劃。 除其他現有解決方案外，遺傳算法是一種解決此問題的優化方法。

Python實現

在上一篇文章中，我展示了如何將Python中的DEAP庫用于開箱即用的遺傳算法。 在本文中，我將更詳細地介紹如何理解遺傳算法的不同部分。

下面的代碼是遺傳算法的生產代碼的簡化版本。 為了更好地理解示例而不是速度和可重用性，對它進行了優化。 它包含應用于示例數據的每個列出的步驟。

遺傳算法代碼演練的6個步驟

遺傳算法的步驟：

· 如何為遺傳算法編碼數據？

· 如何評估遺傳算法解決方案？

· 如何為遺傳算法編碼交配（交叉）？

· 如何為遺傳算法編碼突變？

· 如何定義遺傳算法的選擇？

· 如何為遺傳算法定義迭代和停止？

如果要隨身攜帶筆記本，可以在此處下載。

第1步-如何為遺傳算法編碼數據？

輸入數據-兩種計劃

在此代碼中，我們將使用同一員工計劃的兩種不同形狀。

第1類計劃-每位員工

> Encoding Data For the Genetic Algorithm — Type 1 Planning — Per Employee. Picture by author.

第一個形狀將是員工對員工的計劃，詳細視圖。 每周計劃總數是一個列表，其中包含每天的列表（在我們的情況下為5天）。 每個日常清單都包含一個班次列表（在我們的案例中為員工的11個班次）。 每個班次都是一個員工ID（從0到11，僅供參考），開始時間（0到24點之間）和班次持續時間（0到10小時之間）的列表。

我們的員工需要這種類型的計劃才能知道他們何時工作。

第2類計劃-每小時總計

> Encoding Data For the Genetic Algorithm — Type 2 Planning — Totals Per Hour. Picture by author.

第二種計劃類型是每小時被雇用的員工總數。 商店所有者將使用此計劃來決定該計劃是否與商店的估計需求相對應。

第2步-如何評估遺傳算法解決方案？

為了評估每小時的員工計劃，我們需要定義一個目標情況。 定義此目標不是優化的一部分：這將是另一個項目的問題。

> Defining Evaluation For the Genetic Algorithm — Defining the Goal Situation. Picture by author.

我們確實需要定義如何評估提議的計劃和目標計劃之間的差異。 這將基于小時計劃進行，將過多的員工小時總數與丟失的員工小時總數相加。 這將是一個成本函數，我們需要將其最小化。

> Defining Evaluation For the Genetic Algorithm — Defining the Cost Function. Picture by author.

我們可以增加人員過多或人手不足的權重，但在此示例中，我使它們相等。

步驟3 —如何為遺傳算法編碼交配（交叉）？

遺傳算法有兩個關鍵步驟：交配（也包括交叉或重組）和突變。

在交配步驟中，與自然選擇一樣，新一代是由父母群體的個體的后代形成的。

將此應用到我們的示例中，請考慮一下以后，我們將生成許多不太好的員工計劃，并嘗試將最好的計劃結合在一起。 因此，我們需要定義一種將兩個人（員工計劃）彼此"混合"的方法。

在此示例中，我決定將其編碼如下：

· 從人口中選擇一個隨機的媽媽

· 從人口中選擇一個隨機的父親

· 創建一個與父級大小相同的子級，但隨機填充零和一。

· 孩子的位置為一，我們從父親那里獲取數據，孩子的位置為零，我們從他母親那里獲取數據。

· 我們對每個孩子重復一次（孩子的數量等于人口數量）

> Defining Cross-Over For the Genetic Algorithm. Picture by author.

這是一種實現方法，還有許多其他方法可能。 為了使遺傳算法起作用，在組合代碼中具有隨機性很重要。 當然，組合必須適合您在步驟1中選擇的數據結構。

第4步-如何為遺傳算法編碼突變？

遺傳算法中的第二個重要步驟是變異。 它包括向新一代產品添加完全隨機的更改。 這種隨機變化允許為不再存在的總體添加新值。

例如，考慮一種情況，該算法進行了幾次迭代，并且由于選擇和組合過程中的隨機性，已取消選擇上午10點之前的所有開始時間。 沒有突變，該算法將永遠無法取回該值，而稍后可能會提供更好的解決方案。

（很少數量的）新值的隨機插入有助于算法擺脫這種情況。

> Defining Mutation For the Genetic Algorithm. Picture by author.

在這里，它被編碼為用0到10之間的隨機值代替一個班次的持續時間或一個班次的開始時間的加法。如果我們指定n_mutations值，則可以重復該操作。

第5步-如何為遺傳算法定義選擇？

選擇過程非常簡單：

· 首先，選擇所有可行的解決方案：刪除員工工作時間超過10小時的解決方案。

> Defining Selection For the Genetic Algorithm — Feasibility. Picture by author.

· 然后，將評估功能應用于每個人（即每個員工計劃）并選擇最佳人選。 所選個人的數量在代碼中保持可變。

> Defining Selection For the Genetic Algorithm — Cost. Picture by author.

第6步-如何為遺傳算法定義迭代和停止？

該代碼的最后一部分是將所有先前的構建塊添加到要迭代的整體代碼中。

> Defining Iteration For the Genetic Algorithm. Picture by author.

優化參數調整

為了使遺傳算法完美地工作，選擇正確的參數很重要：generation_size，n_mutations和n_best在此很重要。

調整這三個將允許找到兩者的最佳組合：

· 收斂到一個解決方案（而不是在沒有改善的情況下隨機轉身）

· 避免陷入局部最優

如果在調整之后您的算法仍然陷于困境，那么另一個改進的方向將是適應交配和變異函數，然后看看會發生什么。

由于本文的目標是從頭開始建立一個簡單而實用的遺傳算法，因此我將不涉及如何找到最佳參數的細節：這將需要另一篇文章。

感謝您的閱讀。 不要猶豫，繼續關注更多！

(本文翻譯自Joos Korstanje的文章《A Simple Genetic Algorithm from Scratch in Python》，參考：
https://towardsdatascience.com/a-simple-genetic-algorithm-from-scratch-in-python-4e8c66ac3121)