遺傳算法

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

[[329691]]

遺傳算法中的自然選擇

這種自然選擇的過程以適者生存為基礎(chǔ)：自然界中能使最佳個(gè)體(動(dòng)物，植物或其他)生存的過程。 然后，這些優(yōu)勝劣汰的人彼此交配，產(chǎn)生了新一代。 大自然還以基因組突變的形式增加了一些隨機(jī)性。

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

結(jié)果是一代又一代的持續(xù)改進(jìn)。

員工計(jì)劃的遺傳算法

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

Python實(shí)現(xiàn)

 在本文中，我將更詳細(xì)地介紹如何理解遺傳算法的不同部分。

下面的代碼是遺傳算法的生產(chǎn)代碼的簡化版本。 為了更好地理解示例而不是速度和可重用性，對它進(jìn)行了優(yōu)化。 它包含應(yīng)用于示例數(shù)據(jù)的每個(gè)列出的步驟。

遺傳算法代碼演練的6個(gè)步驟

遺傳算法的步驟：

• 如何為遺傳算法編碼數(shù)據(jù)?
• 如何評估遺傳算法解決方案?
• 如何為遺傳算法編碼交配(交叉)?
• 如何為遺傳算法編碼突變?
• 如何定義遺傳算法的選擇?
• 如何為遺傳算法定義迭代和停止?

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

第1步-如何為遺傳算法編碼數(shù)據(jù)?

輸入數(shù)據(jù)-兩種計(jì)劃

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

第1類計(jì)劃-每位員工：

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

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

我們的員工需要這種類型的計(jì)劃才能知道他們何時(shí)工作。

第2類計(jì)劃-每小時(shí)總計(jì)：

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

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

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

為了評估每小時(shí)的員工計(jì)劃，我們需要定義一個(gè)目標(biāo)情況。 定義此目標(biāo)不是優(yōu)化的一部分：這將是另一個(gè)項(xiàng)目的問題。

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

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

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

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

步驟3 —如何為遺傳算法編碼交配(交叉)?

遺傳算法有兩個(gè)關(guān)鍵步驟：交配(也包括交叉或重組)和突變。

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

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

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

• 從人口中選擇一個(gè)隨機(jī)的媽媽
• 從人口中選擇一個(gè)隨機(jī)的父親
• 創(chuàng)建一個(gè)與父級大小相同的子級，但隨機(jī)填充零和一。
• 孩子的位置為一，我們從父親那里獲取數(shù)據(jù)，孩子的位置為零，我們從他母親那里獲取數(shù)據(jù)。
• 我們對每個(gè)孩子重復(fù)一次(孩子的數(shù)量等于人口數(shù)量)

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

這是一種實(shí)現(xiàn)方法，還有許多其他方法可能。 為了使遺傳算法起作用，在組合代碼中具有隨機(jī)性很重要。 當(dāng)然，組合必須適合您在步驟1中選擇的數(shù)據(jù)結(jié)構(gòu)。

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

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

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

(很少數(shù)量的)新值的隨機(jī)插入有助于算法擺脫這種情況。

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

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

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

選擇過程非常簡單：

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

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

然后，將評估功能應(yīng)用于每個(gè)人(即每個(gè)員工計(jì)劃)并選擇最佳人選。 所選個(gè)人的數(shù)量在代碼中保持可變。

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

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

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

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

優(yōu)化參數(shù)調(diào)整

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

調(diào)整這三個(gè)將允許找到兩者的最佳組合：

• 收斂到一個(gè)解決方案(而不是在沒有改善的情況下隨機(jī)轉(zhuǎn)身)
• 避免陷入局部最優(yōu)

如果在調(diào)整之后您的算法仍然陷于困境，那么另一個(gè)改進(jìn)的方向?qū)⑹沁m應(yīng)交配和變異函數(shù)，然后看看會發(fā)生什么。

(本文翻譯自Joos Korstanje的文章《A Simple Genetic Algorithm from Scratch in Python》，參考：

https://towardsdatascience.com/a-simple-genetic-algorithm-from-scratch-in-python-4e8c66ac3121)