背包遺傳演算法
『壹』 我想知道運籌學中旅行背包問題。謝謝！
背包問題是一個非常有名的問題。可以這樣敘述如下。假設有 n 件物品，記為 d1,d2,d3,…… dn。對於每一種物品di (1=<i=<n), 它的重量是wi ,而它的價值為 vi。現在要求用這 n 種物品的子集填滿背包，使其總重量不超過給定的重量限制 TOT，並使得背包的價值盡可能高。
1.實數背包
物品可以一部分放在背包中，那麼直接貪心就行了，把物品按性價比(v[i]/w[i])升序放入即為最優解。
復雜度O(n+nlogn)
2.整數背包
物品只能整個放入背包，不允許拆開放，用動態規劃求解。
dp[i,j]表示前i個物品放入容量為j的背包中可以得到的最優解。
狀態轉移方程：dp[i,j]=max{dp[i-1,j],dp[i-1,j-w[i]]+v[i]}
復雜度O(nm)
3.多重背包
與1、2不同，這里有k個背包，每個背包有不同的容量，其它一樣。
沒什麼好辦法，只能搜索。
對於每個物品i，枚舉它能被放在背包j，也可以不放物品i。
復雜度O(kn)
可以針對不同的題目採取不同的剪枝。
背包問題數學模型為(由於輸入問題,下標很難輸入規范,如c1中1是下標,請注意)
maxZ=c1x1+c2x2+...+cnxn
w1x1+w2x2+...+wnxn<=W
xi>=0,且為整數,i=1,2,...,n
式中：
ck為第k種物品的單位價值，wk是第k種物品的單位重量或體積，W是背包的重量或體積限制。
動態規劃的有關要素如下:
階段k：第k次裝載第k種物品（k=1,2,…,n）
狀態變數sk：第k次裝載時背包還可以裝載的重量(或體積)
決策變數xk：第k次裝載第k種物品的件數
決策允許集合：Dk(sk)={dk|0 xksk/wk，xk為整數}
狀態轉移方程：sk+1=sk－wkxk
階段指標：vk=ckxk
一般來說，用來解決背包問題的方法有遞歸法和貪心法等，但用這兩中方法來解決背包問題都有其不可避免的缺點，遞歸法雖能遍歷搜索空間，找到最優解，但由於此問題的解的空間是以2的N級增長的，所以它只適用於解決小規模的背包問題，而貪心法又很難真正找到最優解，此方法找到的最優解往往與真正的最優解相差很遠。而遺傳演算法作為一種隨機的優化與搜索方法，具有良好的並行性，而且遺傳演算法只需利用目標的取值信息,而無需遞度等高價值信息,因此適用於任何規模。遺傳演算法的高度非線形的不連續多峰函數的優化以及無解析表達式的目標函數的優化,具有很強的通用性。
（如果你是需要計算機編程序的話，答案內容就更多些，現在不曉得你應用背包問題做什麼呢）
『貳』 如何用遺傳演算法求解多重背包問題
遺傳演算法將目標函數轉換為適應度函數，評估，復制，交叉，變異種群中的個體，並從中選出適應性最強的個體，演算法的最優解就是這個個體。具體流程是：1.初始種群的產生。2.適應度函數的構造。3.選擇和繁殖。4.終止條件。
『叄』 遺傳演算法--GA
遺傳演算法（GA）屬於 人工智慧啟發式演算法 ，啟發式演算法的目標就是 尋找原始問題的最優解 ，該演算法的定義為
人類通過直觀常識和生活經驗，設計出一種以搜索最優解為目的，通過模擬大自然規律的演算法，該演算法在可以在接受的花銷（計算時間和存儲空間）范圍內找到問題實例的一個可行解，且該可行解和真實最優解的誤差一般不可以被估計
當下主要有的啟發式演算法包括 遺傳演算法、退火法，蟻群演算法、人工神經網路等 ，這篇文章主要介紹遺傳演算法
遺傳演算法的基本原理是模擬達爾文進化論 "物競天擇，適者生存" 的自然法則，其核心思想為
（1）將原始問題的參數，抽象為基因編碼
（2）將原始問題的可行解，抽象為基因排列的染色體組合
（3）將原始問題的解集規模，抽象為一定數量染色體組成的種群
（4）尋找可行解的過程，抽象為種群的進化過程（染色體選擇、交叉、變異等）
（5）比較可行解的優劣，抽象為量化比較不同種群對當前環境的適應程度
（6）逼近最優解的過程，抽象為淘汰適應度差的種群，保留適應度高的種群進行下一次進化
（7）問題的最優解，抽象為經過多次進化後，最終生存下來的精英種群
理論上，通過有限次種群進化，生存下來的種群都是 精英染色體 ，是最適合當前環境條件的種群，也就可以無限逼近原始問題的最優解
相關生物學術語：
為了大家更好了解遺傳演算法，在此之前先簡單介紹一下相關生物學術語，大家了解一下即可。
基因型(genotype)：性狀染色體的內部表現；
表現型(phenotype)：染色體決定的性狀的外部表現，或者說，根據基因型形成的個體的外部表現；
進化(evolution)：種群逐漸適應生存環境，品質不斷得到改良。生物的進化是以種群的形式進行的。
適應度(fitness)：度量某個物種對於生存環境的適應程度。
選擇(selection)：以一定的概率從種群中選擇若干個個體。一般，選擇過程是一種基於適應度的優勝劣汰的過程。
復制(reproction)：細胞分裂時，遺傳物質DNA通過復制而轉移到新產生的細胞中，新細胞就繼承了舊細胞的基因。
交叉(crossover)：兩個染色體的某一相同位置處DNA被切斷，前後兩串分別交叉組合形成兩個新的染色體。也稱基因重組或雜交；
變異(mutation)：復制時可能（很小的概率）產生某些復制差錯，變異產生新的染色體，表現出新的性狀。
編碼(coding)：DNA中遺傳信息在一個長鏈上按一定的模式排列。遺傳編碼可看作從表現型到基因型的映射。
解碼(decoding)：基因型到表現型的映射。
個體（indivial）：指染色體帶有特徵的實體；
種群（population）：個體的集合，該集合內個體數稱為種群
大體實現過程
遺傳演算法中每一條染色體，對應著遺傳演算法的一個解決方案，一般我們用適應性函數（fitness function）來衡量這個解決方案的優劣。所以從一個基因組到其解的適應度形成一個映射。 遺傳演算法的實現過程實際上就像自然界的進化過程那樣。
基本遺傳演算法概述
1.[開始]生成n個染色體的隨機群體（適合該問題的解決方案）
2.[適應度]評估群體中每個染色體x的適應度f（x）
3.[新種群]通過重復以下來創建新種群直到新種群完成的步驟
3.1 [選擇]根據種群的適合度選擇兩個親本染色體（更好的適應性，更大的選擇機會）
3.2 [交叉]以交叉概率跨越父母形成新的後代（兒童） ）。如果沒有進行交叉，後代就是父母的確切副本。
3.3 [突變]突變概率突變每個基因座（染色體中的位置）的新後代。
4.[接受]在新種群中放置新後代[替換]使用新生成的種群進一步運行演算法
5.[測試]如果滿足結束條件，則停止並返回當前種群中的最佳解
6。[循環]轉到步驟2
影響GA的因素
從遺傳演算法概述可以看出，交叉和變異是遺傳演算法中最重要的部分。性能主要受這兩個因素的影響。在我們解釋有關交叉和變異的更多信息之前，我們將給出一些有關染色體的信息。
染色體編碼
染色體應該以某種方式包含它所代表的解決方案的信息。最常用的編碼方式是二進制字元串。然後染色體看起來像這樣：
每個染色體由二進制字元串表示。字元串中的每個位都可以表示解決方案的一些特徵。另一種可能性是整個字元串可以表示一個數字 - 這已在基本的GA小程序中使用。當然，還有許多其他的編碼方式。編碼主要取決於解決的問題。例如，可以直接編碼整數或實數，有時對某些排列等進行編碼很有用。
染色體交叉
在我們確定了將使用的編碼之後，我們可以繼續進行交叉操作。 Crossover對來自親本染色體的選定基因進行操作並產生新的後代。最簡單的方法是隨機選擇一些交叉點，並在此點之前從第一個父項復制所有內容，然後在交叉點之後復制另一個父交叉點之後的所有內容。交叉可以說明如下:( |是交叉點）：
還有其他方法可以進行交叉，例如我們可以選擇更多的交叉點。交叉可能非常復雜，主要取決於染色體的編碼。針對特定問題進行的特定交叉可以改善遺傳演算法的性能。
4.染色體突變
在執行交叉之後，發生突變。突變旨在防止群體中的所有解決方案落入解決問題的局部最優中。突變操作隨機改變由交叉引起的後代。在二進制編碼的情況下，我們可以將一些隨機選擇的位從1切換到0或從0切換到1.突變可以如下所示：
突變（以及交叉）技術主要取決於染色體的編碼。例如，當我們編碼排列時，可以將突變作為兩個基因的交換來進行。
GA的參數
1.交叉和突變概率
GA有兩個基本參數 - 交叉概率和變異概率。
交叉概率 ：交叉的頻率。如果沒有交叉，後代就是父母的精確副本。如果存在交叉，則後代由父母染色體的部分組成。如果交叉概率為100％，那麼所有後代都是由交叉產生的。如果它是0％，那麼全新一代都是從舊種群的染色體的精確拷貝製成的（但這並不意味著新一代是相同的！）。交叉是希望新染色體將包含舊染色體的良好部分，因此新染色體將更好。但是，將舊人口的一部分留給下一代是好的。
突變概率 ：染色體部分突變的頻率。如果沒有突變，則在交叉（或直接復制）後立即生成後代而不進行任何更改。如果進行突變，則改變染色體的一個或多個部分。如果突變概率為100％，則整個染色體發生變化，如果是0％，則沒有變化。突變通常會阻止GA陷入局部極端。突變不應該經常發生，因為GA實際上會改變為隨機搜索。
2.其他參數
種群規模 ：種群中有多少染色體（一代）。如果染色體太少，GA幾乎沒有可能進行交叉，只探索了一小部分搜索空間。另一方面，如果染色體太多，GA會減慢。研究表明，經過一定的限制（主要取決於編碼和問題），使用非常大的種群是沒有用的，因為它不能比中等規模的種群更快地解決問題。
3 選擇
正如您從GA概述中已經知道的那樣，從群體中選擇染色體作為交叉的父母。問題是如何選擇這些染色體。根據達爾文的進化論，最好的進化能夠創造出新的後代。選擇最佳染色體的方法有很多種。例如輪盤賭選擇，Boltzman選擇，錦標賽選擇，等級選擇，穩態選擇和其他一些選擇。
1.輪盤賭選擇
父母根據他們的健康狀況選擇。染色體越好，它們被選擇的機會就越多。想像一下輪盤賭輪，人口中的所有染色體都放在那裡。輪盤中截面的大小與每條染色體的適應度函數的值成比例 - 值越大，截面越大。有關示例，請參見下圖。
輪盤賭中放入一塊大理石，並選擇停止的染色體。顯然，具有較大適應值的染色體將被選擇更多次。
該過程可以通過以下演算法來描述。
[Sum]計算總體中所有染色體擬合度的總和 - 總和S.
[Select]從區間（0，S）-r生成隨機數。
[循環]遍歷總體並從0 - 總和中求和。當總和s大於r時，停止並返回您所在的染色體。當然，對於每個群體，步驟1僅執行一次。
2.排名選擇
當健身值之間存在很大差異時，先前的選擇類型會出現問題。例如，如果最佳染色體適應度是所有擬合度總和的90％，那麼其他染色體將很少被選擇的機會。等級選擇首先對群體進行排序，然後每個染色體接收由該等級確定的適合度值。最差的將是健身1，第二個最差的2等等，最好的將具有適應度N（人口中的染色體數量）。您可以在下面的圖片中看到，在更改適應性與排名確定的數字後情況如何變化。
排名前的情況（適合度圖）
排名後的情況（訂單號圖）
現在所有染色體都有機會被選中。然而，這種方法會導致收斂速度變慢，因為最好的染色體與其他染色體的差別不大。
3.穩態選擇
這不是選擇父母的特定方法。這種選擇新種群的主要思想是染色體的很大一部分可以存活到下一代。穩態選擇GA以下列方式工作。在每一代中，選擇一些好的（具有更高適應性）染色體來創建新的後代。然後去除一些不好的（具有較低適合度）染色體並將新的後代放置在它們的位置。其餘人口倖存下來。
4.精英
精英主義的想法已經被引入。當通過交叉和變異創建新的種群時，我們有很大的機會，我們將失去最好的染色體。精英主義是首先將最佳染色體（或少數最佳染色體）復制到新種群的方法的名稱。其餘人口以上述方式構建。精英主義可以迅速提高GA的性能，因為它可以防止丟失最佳找到的解決方案。
交叉(Crossover)和突變 (Mutation)
交叉和變異是GA的兩個基本運算符。 GA的表現非常依賴於它們。運算符的類型和實現取決於編碼以及問題。有多種方法可以執行交叉和變異。在本章中，我們將簡要介紹一些如何執行多個編碼的示例和建議。
1.二進制編碼
交叉
單點交叉 - 選擇一個交叉點，從第一個父項復制從染色體開始到交叉點的二進制字元串，其餘從另一個父項復制
選擇兩點交叉 - 兩個交叉點，從第一個父節點復制從染色體開始到第一個交叉點的二進制字元串，從第一個父節點復制從第一個交叉點到第二個交叉點的部分，其餘的是再次從第一個父級復制
均勻交叉 - 從第一個父項或第二個父項中隨機復制位
算術交叉 - 執行一些算術運算以產生新的後代
突變
位反轉 - 選擇的位被反轉
2.置換編碼
交叉
單點交叉 - 選擇一個交叉點，將排列從第一個父項復制到交叉點，然後掃描另一個父項，如果該數字還沒有在後代中，則添加它注意：還有更多方法如何在交叉點之後產生休息
(1 2 3 4 5 6 7 8 9) + (4 5 3 6 8 9 7 2 1) = (1 2 3 4 5 6 8 9 7)
變異
順序更改 - 選擇並交換兩個數字
(1 2 3 4 5 6 8 9 7) => (1 8 3 4 5 6 2 9 7)
3.值編碼
交叉
可以使用來自二進制編碼的所有交叉
變異
添加一個小數字（用於實數值編碼） - 將一個小數字添加到（或減去）所選值
（1.29 5.68 2.86 4.11 5.55）=>（1.29 5.68 2.73 4.22 5.55）
4.樹編碼
交叉
樹交叉 - 在父母雙方中選擇一個交叉點，父母在該點被分割，交換點下面的部分被交換以產生新的後代
變異
更改運算符，數字 - 選定節點已更改
補充:
疑惑點：
初始種群是啥：
利用二進制（一般）表示最終解
例如：需要求解z=x^2+y^2的最大值，x={1，5，3，8}，y={5，4，0，6}
用六位二進制數表示由x，y組成的解，例如：001100 表示x=1，y=4
001100 稱為一條基因序列，表示的是該問題的一種解決 方案
種群是包含多個基因序列（解決方案/個體）的集合
適應度函數是啥，有什麼作用：
適應度函數可以理解成「 游戲 規則」，如果問題較為復雜，需要自定義適應度函數，說明如何區分優秀與不優秀的個體; 如果問題比較簡單，例如上述求最大值的問題，則直接用此函數式作為適應度函數即可。作用：評定個體的優劣程度，從而決定其遺傳機會的大小。
怎麼選擇：
定義「適者生存不適者淘汰」的規則，例如：定義適應度高的被選擇的概率更大
怎麼交叉：
利用循環，遍歷種群中的每個個體，挑選另一個體進行交叉。例如，通過遍歷為基因序列A挑選出B配對，則取A的前半部分，B的後半部分，組合成新的個體（基因序列）C
如何變異：
隨機挑選基因序列上的某一位置，進行0-1互換
建議 GA的參數
如果您決定實施遺傳演算法，本章應該為您提供一些基本建議。這些建議非常籠統。您可能希望嘗試使用自己的GA來解決特定問題，因為沒有一般理論可以幫助您針對任何問題調整GA參數。
建議通常是對GA的經驗研究的結果，這些研究通常僅在二進制編碼上進行。
交叉率
交叉率一般應高，約為80％-95％。 （但是有些結果表明，對於某些問題，交叉率約為60％是最好的。）
突變率
另一方面，突變率應該非常低。最佳利率似乎約為0.5％-1％。
人口規模
可能令人驚訝的是，非常大的人口規模通常不會改善GA的性能（從找到解決方案的速度的意義上說）。良好的人口規模約為20-30，但有時大小為50-100是最好的。一些研究還表明，最佳種群規模取決於編碼字元串（染色體）的大小。這意味著如果你有32位染色體，那麼人口應該高於16位染色體。
選擇
可以使用基本的輪盤賭選擇，但有時排名選擇可以更好。查看有關選擇優缺點的章節。還有一些更復雜的方法可以在GA運行期間更改選擇參數。基本上，這些表現類似於模擬退火。如果您不使用其他方法來保存最佳找到的解決方案，則應確保使用精英主義。您也可以嘗試穩態選擇。
編碼
編碼取決於問題以及問題實例的大小。查看有關編碼的章節以獲取一些建議或查看其他資源。
交叉和變異
運算符取決於所選的編碼和問題。查看有關操作員的章節以獲取一些建議。您還可以查看其他網站。
搜索空間
如果我們正在解決問題，我們通常會尋找一些最好的解決方案。所有可行解決方案的空間（所需解決方案所在的解決方案集）稱為搜索空間（也稱為狀態空間）。搜索空間中的每個點代表一種可能的解決方案。每個可能的解決方案可以通過其對問題的值（或適應度）進行「標記」。通過GA，我們在眾多可能的解決方案中尋找最佳解決方案 - 以搜索空間中的一個點為代表。然後尋找解決方案等於在搜索空間中尋找一些極值（最小值或最大值）。有時可以很好地定義搜索空間，但通常我們只知道搜索空間中的幾個點。在使用遺傳演算法的過程中，隨著進化的進行，尋找解決方案的過程會產生其他點（可能的解決方案）。
問題是搜索可能非常復雜。人們可能不知道在哪裡尋找解決方案或從哪裡開始。有許多方法可用於尋找合適的解決方案，但這些方法不一定能提供最佳解決方案。這些方法中的一些是爬山，禁忌搜索，模擬退火和遺傳演算法。通過這些方法找到的解決方案通常被認為是很好的解決方案，因為通常不可能證明最佳方案。
NP-hard Problems
NP問題是一類無法用「傳統」方式解決的問題。我們可以快速應用許多任務（多項式）演算法。還存在一些無法通過演算法解決的問題。有很多重要問題很難找到解決方案，但是一旦有了解決方案，就很容易檢查解決方案。這一事實導致了NP完全問題。 NP代表非確定性多項式，它意味著可以「猜測」解決方案（通過一些非確定性演算法），然後檢查它。如果我們有一台猜測機器，我們或許可以在合理的時間內找到解決方案。為簡單起見，研究NP完全問題僅限於答案可以是或否的問題。由於存在輸出復雜的任務，因此引入了一類稱為NP難問題的問題。這個類並不像NP完全問題那樣受限。 NP問題的一個特徵是，可以使用一個簡單的演算法，可能是第一眼看到的，可用於找到可用的解決方案。但是這種方法通常提供了許多可能的解決方案 - 只是嘗試所有可能的解決方案是非常緩慢的過程（例如O（2 ^ n））。對於這些類型問題的更大的實例，這種方法根本不可用。今天沒有人知道是否存在一些更快的演算法來提供NP問題的確切答案。對於研究人員來說，發現這樣的演算法仍然是一項重大任務（也許你！:-)）。今天許多人認為這種演算法不存在，因此他們正在尋找替代方法。替代方法的一個例子是遺傳演算法。 NP問題的例子是可滿足性問題，旅行商問題或背包問題。可以獲得NP問題匯編。
參考：
https://www.jianshu.com/p/ae5157c26af9
https://www.jianshu.com/p/b36b520bd187
『肆』 遺傳演算法求解背包問題的程序
1樓的不是遺傳演算法吧！
剛好做過這個遺傳演算法解背包問題的論文，給你回答啦~~獨家哦，分數要給偶~~
1、程序開發環境
開發環境：Visual C++6.0 (把Fortran程序改為VC)
操作系統：Windows 2003 Professional
2、程序性能對比
運行時間與加速比（如表1所示）
進程數p（個） 1 2 4
運行時間t（秒） 129s 78s 38s
加速比s 1.65 3.38
表1、運行時間與加速比
3、程序運行結果：
實例數據：
假設物體的重量Weight、物體的收益Profit和背包的容量Contain 分別為：
Weight={ 80，82，85，70，72， 70，66，50，55，25 ，
50，55，40，48，50， 32，22，60，30，32 ，
40，38，35，32，25， 28，30，22，50，30 ，
45，30，60，50，20 ， 65，20，25，30，10 ，
20，25，15，10，10 ， 10，4， 4， 2， 1 }
Profit={ 220，208，198，192，180， 180，165，162，160，158，
155，130，125，122，120 ， 118，115，110，105，101，
100，100，98， 96， 95， 90， 88， 82， 80， 77 ，
75， 73， 72， 70， 69， 66， 65， 63， 60， 58，
56， 50， 30， 20， 15， 10， 8， 5， 3， 1}
Contain=1000，
如何選擇哪些物品裝入該背包可使得在背包的容量約束限制之內所裝物品的總價值最大?
傳統的演算法（動態規劃、遞歸回溯法和貪心演算法所得結果：
總價值為3077 , 總重量為999。
2001年張鈴，張鈸教授在計算機學報上發表的《佳點集遺傳演算法》所得結果
總價值為3103, 總重量為1000。
我們演算法所得結果： 總價值為3103, 總重量為1000。
我們所求得最優解的個體分配情況為：
11010 10111 10110 11011 01111 11101 00001 01001 10000
01000
演算法 最大迭代次數 總價值為 總重量為
傳統的演算法 400 3077 999
佳點集演算法 70 3103 1000
遺傳演算法 75 3103 1000
// knapsack.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <AfxWin.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <conio.h>
#include <stdio.h>
// 重要常量參數
#define popsize 200 //種群的規模
#define pc 0.618 //雜交概率
#define pm 0.03 //變異概率
#define lchrom 50 //染色體長度
#define maxgen 1000 //最大進化代數
struct population
{
unsigned int chrom[lchrom]; //染色體
double weight; //背包重量
double fitness; //適應度
unsigned int parent1,parent2,cross; //雙親、交叉點
};
//新生代種群、父代種群
struct population oldpop[popsize],newpop[popsize];
//背包問題中物體重量、收益、背包容量
int weight[lchrom],profit[lchrom],contain;
//種群的總適應度、最小、最大、平均適應度
double sumfitness,minfitness,maxfitness,avgfitness;
//計算適應度時使用的 懲罰函數系數
double alpha;
//一個種群中最大和最小適應度的個體
int minpop,maxpop;
/* 讀入背包信息,並且計算懲罰函數系數 */
void read_infor()
{
FILE *fp;
int j;
//獲取背包問題信息文件
if ((fp=fopen("knapsack.txt","r"))==NULL)
{
//讀取文件失敗
AfxMessageBox("The file is not found",MB_OK,NULL);
return;
}
//讀入物體收益信息
for (j=0;j<lchrom;j++)
{
fscanf(fp,"%d",&profit[j]);
}
//讀入物體重量信息
for (j=0;j<lchrom;j++)
{
fscanf(fp,"%d",&weight[j]);
}
//讀入背包容量
fscanf(fp,"%d",&contain);
fclose(fp);
}
//根據計算的個體重量,判斷此個體是否該留在群體中
double cal_weight(unsigned int *chr)
{
int j;
double pop_weight;//背包重量
pop_weight=0;
for (j=0;j<lchrom;j++)
{
pop_weight=pop_weight+(*chr)*weight[j];
chr++;
}
return pop_weight;
}
/* 種群中個體適應度計算*/
double cal_fit(unsigned int *chr)
{
int j;
double pop_profit;//適應度
pop_profit=0;
// pop_weight=0;
for (j=0;j<lchrom;j++)
{
pop_profit=pop_profit+(*chr)*profit[j];
// pop_weight=pop_weight+(*chr)*weight[j];
chr++;
}
return pop_profit;
}
/* 群體適應度的最大最小值以及其他信息 */
void statistics(struct population *pop)
{
int i;
double tmp_fit;
sumfitness=pop[0].fitness;
minfitness=pop[0].fitness;
minpop=0;
maxfitness=pop[0].fitness;
maxpop=0;
for (i=1;i<popsize;i++)
{
//計算種群的總適應度
sumfitness=sumfitness+pop[i].fitness;
tmp_fit=pop[i].fitness;
//選擇種群中最大適應度的個體
if ((tmp_fit>maxfitness)&&((int)(tmp_fit*10)%10==0))
{
maxfitness=pop[i].fitness;
maxpop=i;
}
//選擇種群中最小適應度的個體
if (tmp_fit<minfitness)
{
minfitness=pop[i].fitness;
minpop=i;
}
//計算平均適應度
avgfitness=sumfitness/(float)popsize;
}
// printf("\nthe max pop = %d;",maxpop);
// printf("\nthe min pop = %d;",minpop);
// printf("\nthe sumfitness = %f\n",sumfitness);
}
//報告種群信息
void report(struct population *pop,int gen)
{
int j;
int pop_weight=0;
printf("the generation is %d.\n",gen); //輸出種群的代數
//輸出種群中最大適應度個體的染色體信息
printf("The population's chrom is: \n");
for (j=0;j<lchrom;j++)
{
if (j%5==0)
{ printf(" ");}
printf("%1d",pop[maxpop].chrom[j]);
}
//輸出群體中最大適應度
printf("\nThe population's max fitness is %d.",(int)pop[maxpop].fitness);
printf("\nThe knapsack weight is %d.\n\n",(int)pop[maxpop].weight);
}
/* 生成初始種群 */
void initpop()
{
int i,j,ispop;
double tmpWeight;
//變數用於判斷是否為滿足條件的個體
ispop=false;
//生成popsize個種群個體
for(i=0;i<popsize;i++)
{
while (!ispop)
{
for(j=0;j<lchrom;j++)
{
oldpop[i].chrom[j]=rand()%2; //隨機生成個體的染色體
oldpop[i].parent1=0; //雙親
oldpop[i].parent2=0;
oldpop[i].cross=0; //交叉點
}
//選擇重量小於背包容量的個體,即滿足條件
tmpWeight=cal_weight(oldpop[i].chrom);
if (tmpWeight<=contain)
{
oldpop[i].fitness=cal_fit(oldpop[i].chrom);
oldpop[i].weight=tmpWeight;
oldpop[i].parent1=0;
oldpop[i].parent2=0;
oldpop[i].cross=0;
ispop=true;
}
}
//此個體可以加入到種群中
ispop=false;
}
}
/* 遺傳操作 */
//概率選擇試驗
int execise(double probability)
{
double pp;
//如果生成隨機數大於相應的概率則返回真，否則試驗不成功
pp=(double)(rand()%20001/20000.0);
if (pp<=probability) return 1;
return 0;
}
// 選擇進行交叉操作的個體
int selection(int pop)
{
double wheel_pos,rand_Number,partsum;
int parent;
//賭輪法選擇
rand_Number=(rand()%2001)/2000.0;
wheel_pos=rand_Number*sumfitness; //賭輪大小
partsum=0;
parent=0;
do{
partsum=partsum+oldpop[parent].fitness;
parent=parent+1;
} while (partsum<wheel_pos && parent<popsize);
return parent-1;
}
/* 交叉操作 */
int crossover(unsigned int *parent1,unsigned int *parent2,int i)
{
int j,cross_pos;
if (execise(pc))
{
//生成交叉位置0,1,...(lchrom-2)
cross_pos=rand()%(lchrom-1);
}
else cross_pos=lchrom-1;
for (j=0;j<=cross_pos;j++)
{ //保留復制；
//包括在概率選擇不成功時，父體完全保留
newpop[i].chrom[j]=parent1[j];
}
for(j=cross_pos+1;j<=(lchrom-1);j++)
{
//從交叉點開始交叉
newpop[i].chrom[j]=parent2[j];
}
//記錄交叉位置
newpop[i].cross=cross_pos;
return 1;
}
/* 變異操作 */
int mutation(unsigned int alleles)
{
if (execise(pm))
{
if (alleles)
alleles=0;
else alleles=1;
}
//返回變異值，或者返回原值
return alleles;
}
/* 群體更新 */
void generation()
{
unsigned int i,j,mate1,mate2;
double tmpWeight;
int ispop;//記錄是否是符合條件的個體
i=0;
while (i<popsize)
{
ispop=false;
while (!ispop)
{
//選擇
mate1=selection(i);
mate2=selection(i+1);
//交叉
crossover(oldpop[mate1].chrom,oldpop[mate2].chrom,i);
//變異
for (j=0;j<lchrom;j++)
{
newpop[i].chrom[j]=mutation(newpop[i].chrom[j]);
}
//選擇重量小於背包容量的個體,即滿足條件
tmpWeight=cal_weight(newpop[i].chrom);
if (tmpWeight<=contain)
{
newpop[i].fitness=cal_fit(newpop[i].chrom);
newpop[i].weight=tmpWeight;
newpop[i].parent1=mate1;
newpop[i].parent2=mate2;
ispop=true;
}
}
//此個體可以加入到種群中
i=i+1;
}
}
void main(int argc, char* argv[])
{
int gen,oldmaxpop,k;
double oldmax;
read_infor();//讀入背包信息
gen=0;
srand( (unsigned)time( NULL ) );//置隨機種子
initpop();
memcpy(&newpop,&oldpop,popsize*sizeof(struct population));
statistics(newpop);//統計新生種群的信息
report(newpop,gen);
while(gen<maxgen)
{
gen=gen+1;
if (gen%100==0)
{
srand( (unsigned)time( NULL ) );//置隨機種子
}
oldmax=maxfitness;
oldmaxpop=maxpop;
generation();
statistics(newpop); //統計新生代種群信息
//如果新生代種群中個體的最大適應度小於老一代種群
//個體的最大適應度，則保存老一代種群個體的最大適應度
//否則報告新生代的最大適應度
if (maxfitness<oldmax)
{
for(k=0;k<lchrom;k++)
newpop[minpop].chrom[k]=oldpop[oldmaxpop].chrom[k];
newpop[minpop].fitness=oldpop[oldmaxpop].fitness;
newpop[minpop].parent1=oldpop[oldmaxpop].parent1;
newpop[minpop].parent2=oldpop[oldmaxpop].parent2;
newpop[minpop].cross=oldpop[oldmaxpop].cross;
statistics(newpop);
}
else if (maxfitness>oldmax)
{
report(newpop,gen);
}
//保存新生代種群的信息到老一代種群信息空間
memcpy(&oldpop,&newpop,popsize*sizeof(struct population));
}
printf("It is over.");
getch();
}
『伍』 c語言中遺傳演算法的種群的適應度是什麼
種群適應度就是演化的目標啊，比如說01背包問題，一個背包中所放物品的價值就是適應度，通過不斷的變異交叉，適應度會發生改變，每次只選出適應度更高的個體就好了
『陸』 如何通俗易懂地解釋遺傳演算法
遺傳演算法，核心是達爾文優勝劣汰適者生存的進化理論的思想。
我們都知道一個種群，通過長時間的繁衍，種群的基因會向著更適應環境的趨勢進化，牛B個體的基因被保留，後代越來越多，適應能力低個體的基因被淘汰，後代越來越少。經過幾代的繁衍進化，留下來的少數個體，就是相對能力最強的個體了。
那麼在解決一些問題的時候，我們能不能學習這樣的思想，比如先隨機創造很多很多的解，然後找一個靠譜的評價體系，去篩選比較好的解，再用這些好的解像生小寶寶一樣生一堆可能更好的解，然後再篩再生，反復弄個幾代，得到的說不定就是近似最優解喲
說干就干，有一個經典組合問題叫「背包問題」，我們拿這種思路來試試
「背包問題（Knapsack Problem）是一種組合優化的NP完全問題。問題可以描述為：給定一組物品，每種物品都有自己的重量和價格，在限定的總重量內，我們如何選擇，才能使得物品的總價格最高。問題的名稱來源於如何選擇最合適的物品放置於給定背包中。」
這個問題的衍生簡化問題「0-1背包問題」 增加了限制條件：每件物品只有一件，可以選擇放或者不放，更適合我們來舉例
這樣的問題如果數量少，當然最好選擇窮舉法
比如一共3件商品，用0表示不取，1表示取，那麼就一共有
000 001 010
011 100 101
110 111
這樣方案，然後讓計算機去累加和，與重量上限比較，留下來的解里取最大即可。
『柒』 遺傳演算法-總結
最近在做遺傳演算法的項目，簡單記錄一下。
遺傳演算法是模擬自然界生物進化機制的一種演算法，在尋優過程中有用的保留無用的去除。包括3個基本的遺傳運算元：選擇（selection）、交叉（crossover）和變異（mutation）。遺傳操作的效果與上述3個遺傳運算元所取的操作概率、編碼方法、群體大小、初始群體，以及適應度函數的設定密切相關。
1、種群初始化
popsize 種群大小，一般為20-100，太小會降低群體的多樣性，導致早熟；較大會影響運行效率；迭代次數一般100-500；交叉概率：0.4-0.99，太小會破壞群體的優良模式；變異概率：0.001-0.1，太大搜索趨於隨機。編碼包括實數編碼和二進制編碼，可以參考遺傳演算法的幾個經典問題，TSP、背包問題、車間調度問題。
2、選擇
目的是把優化個體直接遺傳到下一代或通過配對交叉產生新的個體再遺傳到下一代，我大部分採用了輪盤賭的方法。具體可參考 http://my.oschina.net/u/1412321/blog/192454 輪盤賭方法各個個體的選擇概率和其適應值成比例，個體適應值越大，被選擇的概率也越高，反之亦然。在實際問題中，經常需要最小值作為最優解，有以下幾種方法進行轉換
a、0-1之間的數據，可以用1-該數值，則最小值與最大值互換；
b、 求倒數；
c、求相反數；
以上幾種方法均可以將最大值變為最小值，最小值變為最大值，便於利用輪盤賭選擇最優個體，根據實際情況來確定。
3、交叉
交叉即將兩個父代個體的部分結構加以替換重組而生成新個體的操作，通過交叉，遺傳演算法的搜索能力得以飛躍提高。根據編碼方法的不同，可以有以下的演算法：
a、實值重組
離散重組、中間重組、線性重組、擴展線性重組
b、二進制交叉
單點交叉、多點交叉、均勻交叉、洗牌交叉、縮小代理交叉
4、變異
基本步驟：對群中所有個體以事先設定的變異概率判斷是否進行變異；對進行變異的個體隨機選擇變異位進行變異。根據編碼表示方法的不同，有實值變異和二進制變異
變異的目的：
a、使遺傳演算法具有局部的隨機搜索能力。當遺傳演算法通過交叉運算元已接近最優解鄰域時，利用變異運算元的這種局部搜索能力可以加速向最優解收斂。顯然該情況下變異概率應取較小值，否則接近最優解的積木塊會因為變異遭到破壞。
b、使遺傳演算法可維持多樣性，以防止未成熟收斂現象。此時收斂概率應取較大值。
變異概率一般取0.001-0.1。
5、終止條件
當最優個體的適應度達到給定的閾值，或者最優個體的適應度和群體適應度不再上升時，或者迭代次數達到預設的代數時，演算法終止。預設代數一般為100-500。
6、其它
多變數：將多個變數依次連接
多目標：一種方法是轉化為單目標，例如按大小進行排序，根據排序和進行選擇，可以參考 https://blog.csdn.net/paulfeng20171114/article/details/82454310