算法合集之遺傳算法的特點及其應(yīng)用(已修改)
2024-10-30 18:37 本頁面
【正文】 遺傳算法的特點及其應(yīng)用 省、市： 上海市 學(xué) 校： 復(fù)旦附中 姓 名： 張 寧 IOI2021集訓(xùn)隊 論文 目 錄 ?遺傳算法的基本概念 ?簡單的遺傳算法 選擇、交換、變異 ?遺傳算法應(yīng)用舉例 子集和問題 TSP(旅行商 )問題 ?結(jié)束語 遺傳算法的基本概念 ? 遺傳算法 （ Geic Algorithms， 簡稱 GA）根據(jù)適者生存 ， 優(yōu)勝劣汰等自然進(jìn)化規(guī)則來進(jìn)行搜索計算和問題求解 。 對許多用傳統(tǒng)數(shù)學(xué)難以解決或明顯失效的復(fù)雜問題，特別是優(yōu)化問題， GA提供了一個行之有效的新途徑。 簡單的遺傳算法 ? GA把每一個可能的解編碼為一個向量 ， 稱為一個染色體 ， 向量的每一個元素稱為基因 。所有染色體組成群體 。 并按預(yù)定的目標(biāo)函數(shù)對每個染色提進(jìn)行評價 ， 根據(jù)其結(jié)果給出一個適應(yīng)度的值 。 ? 算法開始時先隨機地產(chǎn)生一些染色體 ， 計算其適應(yīng)度 ， 根據(jù)適應(yīng)度對諸染色體進(jìn)行選擇 、交換 、 變異等遺傳操作 ， 剔除適應(yīng)度低的染色體 ， 留下適應(yīng)度高的染色體 。 ? 由于新群體的成員是上一代群體的優(yōu)秀者，因而在總體上優(yōu)于上一代。 GA就這樣反復(fù)迭代，直至滿足某種預(yù)定的優(yōu)化指標(biāo)。上述 GA的工作過程可用 圖 1簡要描述。 選 擇 選擇運算使用比較普遍的一種是適應(yīng)度比例法 。其實就是將適應(yīng)度值視為其權(quán)值 ， 權(quán)值大的被選中的概率也大 。 它與各染色體適應(yīng)度成比例 。某一染色體被選中的概率為 式中 xi為種群中第 i個染色體對應(yīng)的數(shù)字串 ，f(xi)是第 i個染色體的適應(yīng)度值 ， 是種群中所有染色體的適應(yīng)度值之和 。 顯然 ， 此法要求染色體的適應(yīng)度應(yīng)為正值 。 ?? )(/)( icc xfxfP? )( ixf交 換 復(fù)制操作雖然能夠從舊種群中選擇出優(yōu)秀者，但不能創(chuàng)造新的染色體，因此，遺傳算法的開創(chuàng)者提
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1