Python中怎么實現(xiàn)一個簡單遺傳算法

今天就跟大家聊聊有關(guān)Python中怎么實現(xiàn)一個簡單遺傳算法，可能很多人都不太了解，為了讓大家更加了解，小編給大家總結(jié)了以下內(nèi)容，希望大家根據(jù)這篇文章可以有所收獲。

遺傳算法

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

遺傳算法中的自然選擇

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

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

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

員工計劃的遺傳算法

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

Python實現(xiàn)

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

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

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

遺傳算法的步驟：

• 如何為遺傳算法編碼數(shù)據(jù)?

• 如何評估遺傳算法解決方案?

• 如何為遺傳算法編碼交配(交叉)?

• 如何為遺傳算法編碼突變?

• 如何定義遺傳算法的選擇?

• 如何為遺傳算法定義迭代和停止?

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

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

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

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

第1類計劃-每位員工：

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

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

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

第2類計劃-每小時總計：

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

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

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

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

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

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

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

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

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

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

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

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

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

• 從人口中選擇一個隨機(jī)的媽媽

• 從人口中選擇一個隨機(jī)的父親

• 創(chuàng)建一個與父級大小相同的子級，但隨機(jī)填充零和一。

• 孩子的位置為一，我們從父親那里獲取數(shù)據(jù)，孩子的位置為零，我們從他母親那里獲取數(shù)據(jù)。

• 我們對每個孩子重復(fù)一次(孩子的數(shù)量等于人口數(shù)量)

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

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

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

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

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

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

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

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

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

選擇過程非常簡單：

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

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

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

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

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

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

看完上述內(nèi)容，你們對Python中怎么實現(xiàn)一個簡單遺傳算法有進(jìn)一步的了解嗎？如果還想了解更多知識或者相關(guān)內(nèi)容，請關(guān)注億速云行業(yè)資訊頻道，感謝大家的支持。