非常好的理解遺傳算法的例子

1、 HYPERLINK 非常好的理解遺傳算法的例子分類(lèi)： HYPERLINK 算法2009-10-16 15:0714864人閱讀 HYPERLINK l comments 評(píng)論(15) HYPERLINK javascript:void(0); o 收藏 收藏 HYPERLINK l report o 舉報(bào) 舉報(bào) HYPERLINK t _blank 算法 HYPERLINK t _blank 優(yōu)化遺傳算法的手工模擬計(jì)算示例為更好地理解遺傳算法的運(yùn)算過(guò)程，下面用手工計(jì)算來(lái)簡(jiǎn)單地模擬遺傳算法的各 個(gè)主要執(zhí)行步驟。 例：求下述二元函數(shù)的最大值： (1) 個(gè)體編碼 遺傳算法的運(yùn)算對(duì)象是表示個(gè)體的符號(hào)

2、串，所以必須把變量 x1, x2 編碼為一種 符號(hào)串。本題中，用無(wú)符號(hào)二進(jìn)制整數(shù)來(lái)表示。 因 x1, x2 為 0 7之間的整數(shù)，所以分別用3位無(wú)符號(hào)二進(jìn)制整數(shù)來(lái)表示，將它 們連接在一起所組成的6位無(wú)符號(hào)二進(jìn)制數(shù)就形成了個(gè)體的基因型，表示一個(gè)可 行解。 例如，基因型 X101110 所對(duì)應(yīng)的表現(xiàn)型是：x 5，6 。 個(gè)體的表現(xiàn)型x和基因型X之間可通過(guò)編碼和解碼程序相互轉(zhuǎn)換。(2) 初始群體的產(chǎn)生 遺傳算法是對(duì)群體進(jìn)行的進(jìn)化操作，需要給其淮備一些表示起始搜索點(diǎn)的初始 群體數(shù)據(jù)。 本例中，群體規(guī)模的大小取為4，即群體由4個(gè)個(gè)體組成，每個(gè)個(gè)體可通過(guò)隨機(jī) 方法產(chǎn)生。 如：011101，101011，0

3、11100，111001(3) 適應(yīng)度汁算 遺傳算法中以個(gè)體適應(yīng)度的大小來(lái)評(píng)定各個(gè)個(gè)體的優(yōu)劣程度，從而決定其遺傳 機(jī)會(huì)的大小。 本例中，目標(biāo)函數(shù)總?cè)》秦?fù)值，并且是以求函數(shù)最大值為優(yōu)化目標(biāo)，故可直接 利用目標(biāo)函數(shù)值作為個(gè)體的適應(yīng)度。(4) 選擇運(yùn)算 選擇運(yùn)算(或稱為復(fù)制運(yùn)算)把當(dāng)前群體中適應(yīng)度較高的個(gè)體按某種規(guī)則或模型遺傳到下一代群體中。一般要求適應(yīng)度較高的個(gè)體將有更多的機(jī)會(huì)遺傳到下一代 群體中。本例中，我們采用與適應(yīng)度成正比的概率來(lái)確定各個(gè)個(gè)體復(fù)制到下一代群體中 的數(shù)量。其具體操作過(guò)程是： 先計(jì)算出群體中所有個(gè)體的適應(yīng)度的總和 fi ( i=1.2,M ); 其次計(jì)算出每個(gè)個(gè)體的相對(duì)適應(yīng)度的大

4、小 fi / fi ，它即為每個(gè)個(gè)體被遺傳 到下一代群體中的概率， 每個(gè)概率值組成一個(gè)區(qū)域，全部概率值之和為1； 最后再產(chǎn)生一個(gè)0到1之間的隨機(jī)數(shù)，依據(jù)該隨機(jī)數(shù)出現(xiàn)在上述哪一個(gè)概率區(qū) 域內(nèi)來(lái)確定各個(gè)個(gè)體被選中的次數(shù)。(5) 交叉運(yùn)算 交叉運(yùn)算是遺傳算法中產(chǎn)生新個(gè)體的主要操作過(guò)程，它以某一概率相互交換某 兩個(gè)個(gè)體之間的部分染色體。 本例采用單點(diǎn)交叉的方法，其具體操作過(guò)程是： 先對(duì)群體進(jìn)行隨機(jī)配對(duì)； 其次隨機(jī)設(shè)置交叉點(diǎn)位置； 最后再相互交換配對(duì)染色體之間的部分基因。(6) 變異運(yùn)算 變異運(yùn)算是對(duì)個(gè)體的某一個(gè)或某一些基因座上的基因值按某一較小的概率進(jìn) 行改變，它也是產(chǎn)生新個(gè)體的一種操作方法。 本例中，我們采用基本位變異的方法來(lái)進(jìn)行變異運(yùn)算，其具體操作過(guò)程是： 首先確定出各個(gè)個(gè)體的基因變異位置，下表所示為隨機(jī)產(chǎn)生的變異點(diǎn)位置， 其中的數(shù)字表示變異點(diǎn)設(shè)置在該基因座處； 然后依照某一概率將變異點(diǎn)的原有基因值取反。對(duì)群體P(t)進(jìn)行一輪選擇、交叉、變異運(yùn)算之后可得到新一代的群體p(t+1)。從上表中可以看出，群體經(jīng)過(guò)一代進(jìn)化之后，其適應(yīng)度的最大值、平均值都得 到了明顯的改進(jìn)。事實(shí)上，這里已經(jīng)找到了最佳個(gè)體“111111”。注意 需要說(shuō)明的是，表中有些欄的數(shù)據(jù)是隨機(jī)產(chǎn)