基于遺傳算法的隨機(jī)優(yōu)化搜索-資料下載頁(yè)
2025-05-02 00:53本頁(yè)面
【正文】 …, , +1）(+1就是 c1)作為一個(gè)個(gè)體。這個(gè)序列中相鄰兩城之間的距離之和的倒數(shù)就可作為相應(yīng)個(gè)體 s的適應(yīng)度，從而適應(yīng)度函數(shù)就是 ????niii ccdsf11 ),(1)( （ 2）對(duì)個(gè)體 s=（ c1, c2, …, , +1）進(jìn)行編碼。但對(duì)于這樣的個(gè)體如何編碼卻不是一件直截了當(dāng)?shù)氖虑?。因?yàn)?如果編碼不當(dāng)，就會(huì)在實(shí)施交叉或變異操作時(shí)出現(xiàn)非法城市序列即無(wú)效解。 例如，對(duì)于 5個(gè)城市的 TSP，我們用符號(hào) A、B、 C、 D、 E代表相應(yīng)的城市，用這 5個(gè)符號(hào)的序列表示可能解即染色體。 然后進(jìn)行遺傳操作。設(shè) s1=（ A, C, B, E, D, A）， s2=（ A, E, D, C, B, A） 實(shí)施常規(guī)的交叉或變異操作，如交換后三位，得 s1’=（ A,C,B,C,B,A）， s2’=（ A,E,D,E,D,A） 或者將染色體 s1第二位的 C變?yōu)?E，得 s1’’=（ A, E, B, E, D, A） 可以看出，上面得到的 s1’， s2’和 s1’’都 是非法的城市序列。 為此，對(duì) TSP必須設(shè)計(jì)合適的染色體和相應(yīng)的遺傳運(yùn)算。 事實(shí)上，人們針對(duì) TSP提出了許多編碼方法和相應(yīng)的特殊化了的交叉、變異操作，如 順序編碼或整數(shù)編碼、隨機(jī)鍵編碼、部分映射交叉、順序交叉、循環(huán)交叉、位置交叉、反轉(zhuǎn)變異、移位變異、互換變異 等等。從而巧妙地用遺傳算法解決了 TSP。 遺傳算法的特點(diǎn)與優(yōu)勢(shì) ◆ 遺傳算法的主要特點(diǎn) —— 遺傳算法一般是直接在解空間搜索 , 而不像圖搜索那樣一般是在問(wèn)題空間搜索 , 最后才找到解 。 —— 遺傳算法的搜索隨機(jī)地始于搜索空間的一個(gè)點(diǎn)集 , 而不像圖搜索那樣固定地始于搜索空間的初始節(jié)點(diǎn)或終止節(jié)點(diǎn) , 所以遺傳算法是一種隨機(jī)搜索算法 。 —— 遺傳算法總是在尋找優(yōu)解 , 而不像圖搜索那樣并非總是要求優(yōu)解 , 而一般是設(shè)法盡快找到解 , 所以遺傳算法又是一種優(yōu)化搜索算法。 —— 遺傳算法的搜索過(guò)程是從空間的一個(gè)點(diǎn)集 (種群 )到另一個(gè)點(diǎn)集 (種群 )的搜索 ,而不像圖搜索那樣一般是從空間的一個(gè)點(diǎn)到另一個(gè)點(diǎn)地搜索。 因而它實(shí)際是一種并行搜索 , 適合大規(guī)模并行計(jì)算 ,而且這種種群到種群的搜索有能力跳出局部最優(yōu)解。 —— 遺傳算法的適應(yīng)性強(qiáng) , 除需知適應(yīng)度函數(shù)外 , 幾乎不需要其他的先驗(yàn)知識(shí) 。 —— 遺傳算法長(zhǎng)于全局搜索 , 它不受搜索空間的限制性假設(shè)的約束 ,不要求連續(xù)性 , 能以很大的概率從離散的 、 多極值的 、 含有噪聲的高維問(wèn)題中找到全局最優(yōu)解 。 ◆ 遺傳算法的應(yīng)用 ? 遺傳算法在人工智能的眾多領(lǐng)域便得到了廣泛應(yīng)用。例如，機(jī)器學(xué)習(xí)、聚類、控制（如煤氣管道控制）、規(guī)劃（如生產(chǎn)任務(wù)規(guī)劃）、設(shè)計(jì)（如通信網(wǎng)絡(luò)設(shè)計(jì)、布局設(shè)計(jì)）、調(diào)度（如作業(yè)車間調(diào)度、機(jī)器調(diào)度、運(yùn)輸問(wèn)題）、配置（機(jī)器配置、分配問(wèn)題）、組合優(yōu)化（如 TSP、背包問(wèn)題）、函數(shù)的最大值以及圖像處理和信號(hào)處理等等。 ? 另一方面，人們又將遺傳算法與其他智能算法和技術(shù)相結(jié)合，使其問(wèn)題求解能力得到進(jìn)一步擴(kuò)展和提高。例如，將遺傳算法與模糊技術(shù)、神經(jīng)網(wǎng)絡(luò)相結(jié)合，已取得了不少成果。 對(duì)遺傳算法的進(jìn)一步研究將涉及到模式定理和隱性、并行性等內(nèi)容。有興趣的同學(xué)可參閱有關(guān)專著。
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1