遺傳演算法函數

⑴ 遺傳演算法具體應用

1、函數優化

函數優化是遺傳演算法的經典應用領域，也是遺傳演算法進行性能評價的常用算例，許多人構造出了各種各樣復雜形式的測試函數：連續函數和離散函數、凸函數和凹函數、低維函數和高維函數、單峰函數和多峰函數等。

2、組合優化

隨著問題規模的增大，組合優化問題的搜索空間也急劇增大，有時在目前的計算上用枚舉法很難求出最優解。對這類復雜的問題，人們已經意識到應把主要精力放在尋求滿意解上，而遺傳演算法是尋求這種滿意解的最佳工具之一。

此外，GA也在生產調度問題、自動控制、機器人學、圖象處理、人工生命、遺傳編碼和機器學習等方面獲得了廣泛的運用。

3、車間調度

車間調度問題是一個典型的NP-Hard問題，遺傳演算法作為一種經典的智能演算法廣泛用於車間調度中，很多學者都致力於用遺傳演算法解決車間調度問題，現今也取得了十分豐碩的成果。

從最初的傳統車間調度（JSP）問題到柔性作業車間調度問題（FJSP），遺傳演算法都有優異的表現，在很多算例中都得到了最優或近優解。

(1)遺傳演算法函數擴展閱讀：

遺傳演算法的缺點

1、編碼不規范及編碼存在表示的不準確性。

2、單一的遺傳演算法編碼不能全面地將優化問題的約束表示出來。考慮約束的一個方法就是對不可行解採用閾值，這樣，計算的時間必然增加。

3、遺傳演算法通常的效率比其他傳統的優化方法低。

4、遺傳演算法容易過早收斂。

5、遺傳演算法對演算法的精度、可行度、計算復雜性等方面，還沒有有效的定量分析方法。

⑵ 遺傳演算法中常用的適應度函數是什麼呢

1.物競――適應度函數（fitness function）

自然界生物競爭過程往往包含兩個方面：生物相互間的搏鬥與及生物與客觀環境的搏鬥過程。但在我們這個實例裡面，你可以想像到，袋鼠相互之間是非常友好的，它們並不需要互相搏鬥以爭取生存的權利。它們的生死存亡更多是取決於你的判斷。因為你要衡量哪只袋鼠該殺，哪只袋鼠不該殺，所以你必須制定一個衡量的標准。而對於這個問題，這個衡量的標准比較容易制定：袋鼠所在的海拔高度。（因為你單純地希望袋鼠爬得越高越好。）所以我們直接用袋鼠的海拔高度作為它們的適應性評分。即適應度函數直接返回函數值就行了。

引自：網頁鏈接

⑶ 遺傳演算法的適度函數是什麼意思舉個例說明下最好通俗

適應度用於評價個體的優劣程度,適應度越大個體越好,反之適應度越小則個體越差；根據適應度的大小對個體進行選擇,以保證適應性能好的個體有更多的機會繁殖後代,使優良特性得以遺傳.因此,遺傳演算法要求適應度函數值必須是非負數,而在許多實際問題中,求解的目標通常是費用最小,而不是效益最大,因此需要將求最小的目標根據適應度函數非負原則轉換為求最大目標的形式。
----------------
如何通俗易懂地解釋遺傳演算法？有什麼例子？
遺傳演算法，核心是達爾文優勝劣汰適者生存的進化理論的思想。

我們都知道一個種群，通過長時間的繁衍，種群的基因會向著更適應環境的趨勢進化，牛B個體的基因被保留，後代越來越多，適應能力低個體的基因被淘汰，後代越來越少。經過幾代的繁衍進化，留下來的少數個體，就是相對能力最強的個體了。

那麼在解決一些問題的時候，我們能不能學習這樣的思想，比如先隨機創造很多很多的解，然後找一個靠譜的評價體系，去篩選比較好的解，再用這些好的解像生小寶寶一樣生一堆可能更好的解，然後再篩再生，反復弄個幾代，得到的說不定就是近似最優解喲

說干就干，有一個經典組合問題叫「背包問題」，我們拿這種思路來試試

「背包問題（Knapsack problem）是一種組合優化的NP完全問題。問題可以描述為：給定一組物品，每種物品都有自己的重量和價格，在限定的總重量內，我們如何選擇，才能使得物品的總價格最高。問題的名稱來源於如何選擇最合適的物品放置於給定背包中。」

這個問題的衍生簡化問題「0-1背包問題」 增加了限制條件：每件物品只有一件，可以選擇放或者不放，更適合我們來舉例

這樣的問題如果數量少，當然最好選擇窮舉法
比如一共3件商品，用0表示不取，1表示取，那麼就一共有
000 001 010
011 100 101
110 111
這樣8種方案，然後讓計算機去累加和，與重量上限比較，留下來的解里取最大即可。

但如果商品數有300,3000,甚至3w種呢，計算量太大窮舉法可能就不適用了，這時如果遺傳演算法使用得當，就能在較短的時間內幫我們找到近似的最優解，我們繼續往下看：

新的問題是12件商品的0-1背包問題

我們先讓計算機隨機產生1000個12位的二級制數

把總重量超過背包上限的解篩掉

剩下的兩兩一對隨機交換「基因片段」產生下一代
交換前：
0000 1100 1101
0011 0101 0101
交換後：
0000 0101 1101
0011 1100 0101

再篩選，再交配，如此反復幾代，留下的解攜帶的「基因「差不多就是最好的了，怎麼樣跟生物進化是不是一模一樣？
其實還差點，生物繁殖過程中，新產生的基因是有一定幾率突變的，這是很多優良性狀的重要來源，遺傳演算法中可也不能忽略它

比如：
變異前：
000101100101
變異後：
000101110101

那也有人得疑惑了，我怎麼知道要讓哪個地方產生突變呢？其實蜘蛛俠NB之前，他也不知道蜘蛛咬在那能讓他變NB而不是SB，這就是一個概率問題。我們在設計演算法的時候，會給每個基因設置一個突變概率（當然是非常非常小了）同樣的在基因交換階段交換哪些基因呢，也是一個演算法設置問題。

總結一下，遺傳演算法應該有
一個基本函數：適度函數f(x)
三個基本操作：選擇，交叉，變異

一.適度函數
適度函數很好理解，其實就是指解的篩選標准，比如我剛才說的把所有超過上限重量的解篩選掉，但是不是有更好的篩選標准或者這個現有的標准根本就是個渣呢？這將直接影響最後結果的接近程度以及求解所耗費的時間，所以設置一個好的適度函數很重要

二.選擇
剛才為了大家理解方便，我直接讓所有解都參與了後續的交叉以及變異，但真實世界可不是這樣子的，因為也不是每個人都會結婚生子的對吧。
說直白點，所謂【屌絲注孤生】【工科男注孤生】什麼的還不是因為loser的基因不適合往下傳唄。不過實際情況是我們偶爾也能看到或聽到屌絲逆襲、鮮花牛糞之類勵志故事，只不過頻率比較低咯

沒錯，概率！在遺傳演算法中選擇也是個概率問題，在解的世界中（姑且這么稱呼吧）適度更高的高富帥們是不是應該有更高的概率被選去傳宗接代才合適呢？不過和現實世界一樣，適度低的屌絲解是要給人家一點希望的對不對？所以

在選擇一些解來產生下一代時，一種常用的選擇策略是 「比例選擇」，也就是個體被選中的概率與其適應度函數值成正比。假設群體的個體總數是M，那麼那麼一個體Xi被選中的概率為f(Xi)/( f(X1) + f(X2) + …….. + f(Xn) )

三.交叉
這是例子中詳細說到的，交換兩個解的部分」基因」，來構造兩個子代的解。

四.變異
在繁殖子代的過程中，新產生的解中的「基因」會以一定的概率出錯，稱為變異。我們可以吧變異發生的概率設置為Pm

五.基本遺傳演算法優化
精英主義：這是基本遺傳演算法的一種優化。目的是防止進化過程中產生的最優解被變異和交叉所破壞。《遺傳演算法原理及應用》介紹的最優保存策略是：即當前種群中適應度最高的個體不參與交叉運算和變異運算，而是用它來替換掉本代群體中經過交叉、變異等遺傳操作後所產生的適應度最低的個體。

後記：
其實不管是遺傳演算法，還是模擬退火演算法或者其他演算法，其本質都是借鑒自然界中的規則規律，人為的為問題設置了一個模擬模型，然後用大自然告訴我們的規律去找最優解，在理解這些演算法的時候，可以照著這個思路去走，一般能讓你快速撥雲見日，了解演算法的核心思想。
比如遺傳演算法，我們可以對比種群的進化，給問題設置的模型就是：
這樣參照著我們熟悉的知識體系，去理解學習，原來聽上去遙不可及的理論是不是一下就變得親切易懂了吧？

可是我們再看一些教科書或者就拿網路來說（怕也是摘抄的某本書上的段落）
真的是通篇不說人話啊！對已經了解這個演算法思想的人來說，還能勉強硬著頭皮看下去，但對入門者來說，這TMD簡直就是噩夢！而這完全是國內各種教材的通病！

我其實一直在想，教材面向的明明就是望門欲入的初學者，你不弄得生動活潑一點招徠門徒就算了，在一群幼兒園小朋友面前賣弄之乎者也還顯本事了是么！我是還記得我們學校的高數書編的有多麼生澀難懂，結果第一節課老教授上課時還說「我們不用同濟的版本，那本書太淺，不適合我們學校的學生」 可是在我和大多數同學看來，同濟版本的高數倒更像是為了要入門的同學編寫的教材，自己學校編的那本卻更像是給同行評閱炫耀作者深度的大部頭。

知識明明可以講的更有趣，讓人願意入其門來探個究竟。

作者：彈彈彈球

⑷ 遺傳演算法的優缺點

優點：

1、遺傳演算法是以決策變數的編碼作為運算對象，可以直接對集合、序列、矩陣、樹、圖等結構對象進行操作。這樣的方式一方面有助於模擬生物的基因、染色體和遺傳進化的過程，方便遺傳操作運算元的運用。

另一方面也使得遺傳演算法具有廣泛的應用領域，如函數優化、生產調度、自動控制、圖像處理、機器學習、數據挖掘等領域。

2、遺傳演算法直接以目標函數值作為搜索信息。它僅僅使用適應度函數值來度量個體的優良程度，不涉及目標函數值求導求微分的過程。因為在現實中很多目標函數是很難求導的，甚至是不存在導數的，所以這一點也使得遺傳演算法顯示出高度的優越性。

3、遺傳演算法具有群體搜索的特性。它的搜索過程是從一個具有多個個體的初始群體P(0)開始的，一方面可以有效地避免搜索一些不必搜索的點。

另一方面由於傳統的單點搜索方法在對多峰分布的搜索空間進行搜索時很容易陷入局部某個單峰的極值點，而遺傳演算法的群體搜索特性卻可以避免這樣的問題，因而可以體現出遺傳演算法的並行化和較好的全局搜索性。

4、遺傳演算法基於概率規則，而不是確定性規則。這使得搜索更為靈活，參數對其搜索效果的影響也盡可能的小。

5、遺傳演算法具有可擴展性，易於與其他技術混合使用。以上幾點便是遺傳演算法作為優化演算法所具備的優點。

缺點：

1、遺傳演算法在進行編碼時容易出現不規范不準確的問題。

2、由於單一的遺傳演算法編碼不能全面將優化問題的約束表示出來，因此需要考慮對不可行解採用閾值，進而增加了工作量和求解時間。

3、遺傳演算法效率通常低於其他傳統的優化方法。

4、遺傳演算法容易出現過早收斂的問題。

(4)遺傳演算法函數擴展閱讀

遺傳演算法的機理相對復雜，在Matlab中已經由封裝好的工具箱命令，通過調用就能夠十分方便的使用遺傳演算法。

函數ga：[x, fval,reason]= ga(@fitnessfun, nvars, options)x是最優解，fval是最優值，@fitnessness是目標函數，nvars是自變數個數，options是其他屬性設置。系統默認求最小值，所以在求最大值時應在寫函數文檔時加負號。

為了設置options，需要用到下面這個函數：options=gaoptimset('PropertyName1', 'PropertyValue1', 'PropertyName2', 'PropertyValue2','PropertyName3', 'PropertyValue3', ...)通過這個函數就能夠實現對部分遺傳演算法的參數的設置。

⑸ 遺傳演算法中怎麼構建適應度函數

適應度函數的選取直接影響到遺傳演算法的收斂速度以及能否找到最優解，因為遺傳演算法在進化搜索中基本不利用外部信息，僅以適應度函數為依據,利用種群每個個體的適應度來進行搜索。

因為適應度函數的復雜度是遺傳演算法復雜度的主要組成部分，所以適應度函數的設計應盡可能簡單，使計算的時間復雜度最小。

遺傳演算法評價一個解的好壞不是取決於它的解的結構，而是取決於該解的適應度值。這正體現了遺傳演算法「優勝劣汰」的特點。遺傳演算法不需要適應度函數滿足連續可微等條件，唯一要求是針對輸入可計算出能加以比較的非負結果。

相關內容解釋

遺傳演算法是計算數學中用於解決最佳化的搜索演算法，是進化演算法的一種。進化演算法最初是借鑒了進化生物學中的一些現象而發展起來的，這些現象包括遺傳、突變、自然選擇以及雜交等。遺傳演算法通常實現方式為一種計算機模擬。

對於一個最優化問題，一定數量的候選解（稱為個體）的抽象表示（稱為染色體）的種群向更好的解進化。傳統上，解用二進製表示（即0和1的串），但也可以用其他表示方法。

進化從完全隨機個體的種群開始，之後一代一代發生。在每一代中，整個種群的適應度被評價，從當前種群中隨機地選擇多個個體（基於它們的適應度），通過自然選擇和突變產生新的生命種群，該種群在演算法的下一次迭代中成為當前種群。

⑹ python遺傳演算法目標函數怎麼編

一、遺傳演算法介紹
遺傳演算法是通過模擬大自然中生物進化的歷程，來解決問題的。大自然中一個種群經歷過若干代的自然選擇後，剩下的種群必定是適應環境的。把一個問題所有的解看做一個種群，經歷過若干次的自然選擇以後，剩下的解中是有問題的最優解的。當然，只能說有最優解的概率很大。這里，我們用遺傳演算法求一個函數的最大值。
f(x) = 10 * sin( 5x ) + 7 * cos( 4x ), 0 <= x <= 10
1、將自變數x進行編碼
取基因片段的長度為10, 則10位二進制位可以表示的范圍是0到1023。基因與自變數轉變的公式是x = b2d(indivial) * 10 / 1023。構造初始的種群pop。每個個體的基因初始值是[0, 1, 0, 1, 0, 1, 0, 1, 0, 1]
2、計算目標函數值
根據自變數與基因的轉化關系式，求出每個個體的基因對應的自變數，然後將自變數代入函數f（x），求出每個個體的目標函數值。
3、適應度函數
適應度函數是用來評估個體適應環境的能力，是進行自然選擇的依據。本題的適應度函數直接將目標函數值中的負值變成0. 因為我們求的是最大值，所以要使目標函數值是負數的個體不適應環境，使其繁殖後代的能力為0.適應度函數的作用將在自然選擇中體現。
4、自然選擇
自然選擇的思想不再贅述，操作使用輪盤賭演算法。其具體步驟：
假設種群中共5個個體，適應度函數計算出來的個體適應性列表是fitvalue = [1 ,3, 0, 2, 4] ，totalvalue = 10 ， 如果將fitvalue畫到圓盤上，值的大小表示在圓盤上的面積。在轉動輪盤的過程中，單個模塊的面積越大則被選中的概率越大。選擇的方法是將fitvalue轉化為[1 ， 4 ，4 , 6 ，10], fitvalue / totalvalue = [0.1 , 0.4 , 0.4 , 0.6 , 1.0] . 然後產生5個0-1之間的隨機數，將隨機數從小到大排序，假如是[0.05 , 0.2 , 0.7 , 0.8 ,0.9]，則將0號個體、1號個體、4號個體、4號個體、4號個體拷貝到新種群中。自然選擇的結果使種群更符合條件了。
5、繁殖
假設個體a、b的基因是
a = [1, 0, 0, 0, 0, 1, 1, 1, 0, 0]

b = [0, 0, 0, 1, 1, 0, 1, 1, 1, 1]

這兩個個體發生基因交換的概率pc = 0.6.如果要發生基因交換，則產生一個隨機數point表示基因交換的位置，假設point = 4,則：

a = [1, 0, 0, 0, 0, 1, 1, 1, 0, 0]

b = [0, 0, 0, 1, 1, 0, 1, 1, 1, 1]
交換後為：

a = [1, 0, 0, 0, 1, 0, 1, 1, 1, 1]

b = [0, 0, 0, 1, 0, 1, 1, 1, 0, 0]
6、突變
遍歷每一個個體，基因的每一位發生突變（0變為1,1變為0）的概率為0.001.突變可以增加解空間
二、代碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def b2d(b): #將二進制轉化為十進制 x∈[0,10] t = 0 for j in range(len(b)): t += b[j] * (math.pow(2, j)) t = t * 10 / 1023 return tpopsize = 50 #種群的大小#用遺傳演算法求函數最大值：#f(x)=10*sin(5x)+7*cos(4x) x∈[0,10]chromlength = 10 #基因片段的長度pc = 0.6 #兩個個體交叉的概率pm = 0.001; #基因突變的概率results = [[]]bestindivial = []bestfit = 0fitvalue = []tempop = [[]]pop = [[0, 1, 0, 1, 0, 1, 0, 1, 0, 1] for i in range(popsize)]for i in range(100): #繁殖100代 objvalue = calobjvalue(pop) #計算目標函數值 fitvalue = calfitvalue(objvalue); #計算個體的適應值 [bestindivial, bestfit] = best(pop, fitvalue) #選出最好的個體和最好的函數值 results.append([bestfit,b2d(bestindivial)]) #每次繁殖，將最好的結果記錄下來 selection(pop, fitvalue) #自然選擇，淘汰掉一部分適應性低的個體 crossover(pop, pc) #交叉繁殖 mutation(pop, pc) #基因突變 results.sort() print(results[-1]) #列印函數最大值和對應的

來自CODE的代碼片
GA.py

1
2
3
4
5
6
7
8
9
def best(pop, fitvalue): #找出適應函數值中最大值，和對應的個體 px = len(pop) bestindivial = [] bestfit = fitvalue[0] for i in range(1,px): if(fitvalue[i] > bestfit): bestfit = fitvalue[i] bestindivial = pop[i] return [bestindivial, bestfit]

來自CODE的代碼片
best.py

1
2
3
4
5
6
7
8
9
10
11
def calfitvalue(objvalue):#轉化為適應值，目標函數值越大越好，負值淘汰。 fitvalue = [] temp = 0.0 Cmin = 0; for i in range(len(objvalue)): if(objvalue[i] + Cmin > 0): temp = Cmin + objvalue[i] else: temp = 0.0 fitvalue.append(temp) return fitvalue

來自CODE的代碼片
calfitvalue.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import mathdef decodechrom(pop): #將種群的二進制基因轉化為十進制（0,1023） temp = []; for i in range(len(pop)): t = 0; for j in range(10): t += pop[i][j] * (math.pow(2, j)) temp.append(t) return tempdef calobjvalue(pop): #計算目標函數值 temp1 = []; objvalue = []; temp1 = decodechrom(pop) for i in range(len(temp1)): x = temp1[i] * 10 / 1023 #（0,1023）轉化為 （0,10） objvalue.append(10 * math.sin(5 * x) + 7 * math.cos(4 * x)) return objvalue #目標函數值objvalue[m] 與個體基因 pop[m] 對應

來自CODE的代碼片
calobjvalue.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import randomdef crossover(pop, pc): #個體間交叉，實現基因交換 poplen = len(pop) for i in range(poplen - 1): if(random.random() < pc): cpoint = random.randint(0,len(pop[0])) temp1 = [] temp2 = [] temp1.extend(pop[i][0 : cpoint]) temp1.extend(pop[i+1][cpoint : len(pop[i])]) temp2.extend(pop[i+1][0 : cpoint]) temp2.extend(pop[i][cpoint : len(pop[i])]) pop[i] = temp1 pop[i+1] = temp2

來自CODE的代碼片
crossover.py

1
2
3
4
5
6
7
8
9
10
11
12
13
import randomdef mutation(pop, pm): #基因突變 px = len(pop) py = len(pop[0]) for i in range(px): if(random.random() < pm): mpoint = random.randint(0,py-1) if(pop[i][mpoint] == 1): pop[i][mpoint] = 0 else: pop[i][mpoint] = 1

來自CODE的代碼片
mutation.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import randomdef sum(fitvalue): total = 0 for i in range(len(fitvalue)): total += fitvalue[i] return totaldef cumsum(fitvalue): for i in range(len(fitvalue)): t = 0; j = 0; while(j <= i): t += fitvalue[j] j = j + 1 fitvalue[i] = t;def selection(pop, fitvalue): #自然選擇（輪盤賭演算法） newfitvalue = [] totalfit = sum(fitvalue) for i in range(len(fitvalue)): newfitvalue.append(fitvalue[i] / totalfit) cumsum(newfitvalue) ms = []; poplen = len(pop) for i in range(poplen): ms.append(random.random()) #random float list ms ms.sort() fitin = 0 newin = 0 newpop = pop while newin < poplen: if(ms[newin] < newfitvalue[fitin]): newpop[newin] = pop[fitin] newin = newin + 1 else: fitin = fitin + 1 pop = newpop

⑺ 在遺傳演算法中目標函數與適應度函數有什麼區別,根據哪個來選擇子代個體

目標函數就是你希望得到的優化結果,比如函數最大值或者最小值.而適應度函數是為了計算個體的適配值.
適配值是非負的,而且要求適配值越大則該個體越優越.而目標函數則有正有負,它們之間關系多種多樣,比如求最小值時,目標函數最小,則適配值越大,求最大值時目標值越大,適配值越大.

⑻ 遺傳演算法有哪些應用

遺傳演算法的搜索策略和優化搜索方法是不依附於梯度信息及其它的輔助知識，而只需要影響搜索方向的目標函數和相應的適應度函數，所以遺傳演算法提供了一種求解復雜系統問題的通用框架，它不依賴於問題的具體領域，對問題的種類有很強的魯棒性，所以廣泛應用於許多科學。遺傳演算法的應用領域有很多，下面針對一些主要的應用領域做簡單的介紹。

1．函數優化：該領域是遺傳演算法得以應用的經典領域，同時它也是遺傳演算法進行性能評價的常用算例，許多人構造出了各種各樣復雜形式的測試函數：連續函數和離散函數、凸函數和凹函數、低維函數和高維函數、單峰函數和多峰函數等。對於函數優化問題，如一些非線性、多模型、多目標等函數問題用遺傳演算法很容易得到較好的結果，而用其他演算法則較難。

2．組合優化：由於組合優化問題的搜索空間在不斷地增大，有時用枚舉法很難得到最優解。對這類復雜的問題，人們已經意識到應把主要精力放在尋求滿意解上，而遺傳演算法是尋求這種滿意解的最佳工具之一。實踐證明，遺傳演算法對於組合優化中的NP問題非常有效。比如，在旅行商問題、裝箱問題及圖形劃分等問題上，已經成功得以應用了遺傳演算法。