遺傳算法與蟻群算法簡介-全文預(yù)覽
【正文】 展下去 ? 只需要知道問題本身所具有的目標(biāo)函數(shù)的信息，且不受連續(xù)、可微等條件的約束，因而具有廣泛的適用性 ? 啟發(fā)式搜索，可適用于有噪聲和多峰值的復(fù)雜空間 北京交通大學(xué)計算機與信息技術(shù)學(xué)院 27 2022/8/29 主要內(nèi)容 ? 智能優(yōu)化算法簡介 ?問題的 NP完全特性 ?常用的智能優(yōu)化算法 ? 遺傳算法 Geic Algorithm ? 群智能優(yōu)化算法 ?蟻群優(yōu)化算法 Ant Colony Optimization ?粒子群優(yōu)化算法 Particle Swarm Optimization ?… 北京交通大學(xué)計算機與信息技術(shù)學(xué)院 28 2022/8/29 群智能優(yōu)化算法 ? 群智能優(yōu)化算法是一種近年來新興的優(yōu)化方法，其模擬社會性動物的各種群體行為，利用群體中個體間的信息交互和合作來實現(xiàn)尋優(yōu)目的 ? 群智能優(yōu)化算法包括很多算法，如人工蜂群算法和人工魚群算法等，不過研究比較深入、應(yīng)用比較廣泛的是蟻群優(yōu)化算法和粒子群優(yōu) 化算法。=[2 6 4 1 8 5 7 9 3]。得到 [2 4 3 | 1 8 7 6 | 5 9]，相應(yīng)地 p239。如父代個體同前，交叉位置為 4，則后代個體為 p139。 p1 = [2 6 4 | 7 3 5 8 | 9 1] p2 = [4 5 2 | 1 8 7 6 | 9 3] 北京交通大學(xué)計算機與信息技術(shù)學(xué)院 16 2022/8/29 [2 6 4 | 7 3 5 8 | 9 1][4 5 2 | 8 7 6 | 9 3]p139。[i] = p1[p2[i]], p239。 αi ∈ (0, 1)且 ∑αi = 1 x39。 ? 多點交叉： 隨機選擇多個位置，然后對換相應(yīng)子串。 ? 在一定程度上解決了傳統(tǒng)的 基于符號處理 機制的人工智能方法在 知識表示 、 信息處理 和解決 組合爆炸 等方面所遇到的困難 ? 基于“適者生存”原則，是并行優(yōu)化算法，其自組織、自適應(yīng)、自學(xué)習(xí)及群體進化的能力適合大規(guī)模復(fù)雜優(yōu)化問題 ? 將問題求解表示為“染色體”，通過選擇（ selection）、交叉（ crossover）和變異（ mutation）操作的迭代，實現(xiàn)種群的演化，最后終收斂到“最適應(yīng)環(huán)境”的個體，從而求得問題的最優(yōu)解（滿意解） 北京交通大學(xué)計算機與信息技術(shù)學(xué)院 10 2022/8/29 遺傳算法 簡單遺傳算法 ? 簡單遺傳算法（ Simple Geic Algorithms， SGA），又稱基本遺傳算法、標(biāo)準(zhǔn)遺傳算法 ? 基于二進制編碼，是最基本的遺傳算法，其遺傳進化操作過程簡單、容易理解，是其他遺傳算法的雛形和基礎(chǔ) ? 三種基本操作 ? 選擇：通常用比例選擇，即選擇概率正比于個體的適配值，使適配值高的個體在下一代中被選中的概率大，提高種群平均適配值 ? 交叉：交換兩父代個體的部分信息構(gòu)成后代個體，使得后代繼承父代的有效模式，有助于產(chǎn)生優(yōu)良個體 ? 變異：隨機改變個體中的某些基因，有助于增加種群多樣性，避免早熟收斂 北京交通大學(xué)計算機與信息技術(shù)學(xué)院 11 2022/8/29 北京交通大學(xué)計算機與信息技術(shù)學(xué)院 12 2022/8/29 隨機產(chǎn)生 N個個體構(gòu)成初始種群 P(0), 令 k=0 對種群 P(k)中各個體進行評價 終止？ 令 m=0 從種群中選擇兩個體 rand()pc 將所選個體作為臨時個體 對臨時個體以概率 pm執(zhí)行變異操作，產(chǎn)生兩個新個體并放入 P(k+1)中，令 m=m+2 對選中個體執(zhí)行交叉操作生成兩個臨時個體 輸出優(yōu)化結(jié)果 mN？ y n y n y n 遺傳算法 選擇 ? 適者生存：適應(yīng)值高的個體的生存概率大，即被選中用來繁殖下一代的概率大。 ? 典型的組合優(yōu)化問題，是 NP完全的 ? 要準(zhǔn)確求解該問題只能用枚舉類的辦法 ? 要枚舉的解的個數(shù)為 (n 1)! ? 例： n = 24，則要枚舉的解的個數(shù)為： 23!=25,852,016,738,884,976,640,000 北京交通大學(xué)計算機與信息技術(shù)學(xué)院 4 2022/8/29 n 24 25 26 27 28 29 30 31 時間 1s 24s 10m 325y 北京交通大學(xué)計算機與信息技術(shù)學(xué)院 5 2022/8/29 北京交通大學(xué)計算機與信息技術(shù)學(xué)院 6 2022/8/29 北京交通大學(xué)計算機與信息技術(shù)學(xué)院 7 2022/8/29 智能優(yōu)化算法簡介 常用的智能優(yōu)化算法 ? 遺傳算法（ Geic Algorithm， GA） ? 演化規(guī)劃（ Evolutionary Programming， EP） ? 蟻群優(yōu)化算法（ Ant Colony Optimization， ACO） ? 粒子群優(yōu)化算法（ Particle Swarm Optimization， PSO） ? 模擬退火算法（ Simulated Annealing， SA） ? 禁忌搜索算法（ Tabu Search， TS） ? 人工神經(jīng)網(wǎng)絡(luò)（ Artificial Neural Network， ANN） ? … 北京交通大學(xué)計算機與信息技術(shù)學(xué)院 8 2022/8/29 主要內(nèi)容 ? 智能優(yōu)化算法簡介 ?問題的 NP完全特性 ?常用的智能優(yōu)化算法 ? 遺傳算法 Geic Algorithm ? 群智能優(yōu)化算法 ?蟻群優(yōu)化算法 Ant Colony Optimization ?粒子群優(yōu)化算法 Particle Swarm Opt
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1