干貨 | 嘿漓帅！你和遺傳算法的距離也許只差這一文(附C++代碼和詳細(xì)代碼注釋)
遺傳算法
概念
遺傳算法（Genetic Algorithm，簡稱GA）起源于對生物系統(tǒng)所進(jìn)行的計(jì)算機(jī)模擬研究，是一種隨機(jī)全局搜索優(yōu)化方法鹦马，它模擬了自然選擇和遺傳中發(fā)生的復(fù)制、交叉(crossover)和變異(mutation)等現(xiàn)象忆肾，從任一初始種群（Population）出發(fā)荸频，通過隨機(jī)選擇、交叉和變異操作客冈，產(chǎn)生一群更適合環(huán)境的個(gè)體旭从，使群體進(jìn)化到搜索空間中越來越好的區(qū)域，這樣一代一代不斷繁衍進(jìn)化场仲，最后收斂到一群最適應(yīng)環(huán)境的個(gè)體（Individual）和悦，從而求得問題的優(yōu)質(zhì)解。
常用術(shù)語
- 染色體(Chromosome)：又可稱為基因型個(gè)體(individuals)渠缕，一定數(shù)量的個(gè)體組成了群體(population)鸽素，群體中個(gè)體的數(shù)量叫做群體大小（population size）亦鳞。
- 位串(Bit String)：個(gè)體的表示形式馍忽。對應(yīng)于遺傳學(xué)中的染色體。
- 基因(Gene)：染色體中的元素燕差，用于表示個(gè)體的特征遭笋。
- 特征值( Feature)：在用串表示整數(shù)時(shí)，基因的特征值與二進(jìn)制數(shù)的權(quán)一致谁不；
- 適應(yīng)度(Fitness)：各個(gè)個(gè)體對環(huán)境的適應(yīng)程度叫做適應(yīng)度(fitness)坐梯。為了體現(xiàn)染色體的適應(yīng)能力，引入了對問題中的每一個(gè)染色體都能進(jìn)行度量的函數(shù)刹帕，叫適應(yīng)度函數(shù)吵血。這個(gè)函數(shù)通常會(huì)被用來計(jì)算個(gè)體在群體中被使用的概率谎替。
- 基因型(Genotype)：或稱遺傳型，是指基因組定義遺傳特征和表現(xiàn)蹋辅。對于于GA中的位串钱贯。
- 表現(xiàn)型(Phenotype)：生物體的基因型在特定環(huán)境下的表現(xiàn)特征。對應(yīng)于GA中的位串解碼后的參數(shù)侦另。
基本遺傳算法
SGA是一種群體型操作秩命，該操作以群體中的所有個(gè)體為對象，只使用基本遺傳算子(Genetic Operator)：選擇算子(Selection Operator)褒傅、交叉算子(Crossover Operator)和變異算子(Mutation Operator)弃锐，是其它一些遺傳算法的基礎(chǔ)。
SGA表示方法
個(gè)體的編碼方法殿托、個(gè)體適應(yīng)度評價(jià)函數(shù)霹菊、初始種群、種群大小支竹、選擇算子旋廷、交叉算子、變異算子礼搁、遺傳運(yùn)算終止條件
GA步驟
- 染色體編碼
編碼：解空間中的解在遺傳算法中的表示形式
常見的編碼方法有二進(jìn)制編碼饶碘、格雷碼編碼、 浮點(diǎn)數(shù)編碼馒吴、各參數(shù)級聯(lián)編碼扎运、多參數(shù)交叉編碼等。
解碼：遺傳算法染色體向問題解的轉(zhuǎn)換 - 初始種群的生成
隨機(jī)生成M個(gè)個(gè)體作為初始化群體P0 - 適應(yīng)度值評估檢測
適應(yīng)度函數(shù)表明個(gè)體或解的優(yōu)劣性饮戳。
適應(yīng)度尺度變換：指算法迭代的不同階段绪囱，能夠通過適當(dāng)改變個(gè)體的適應(yīng)度大小，進(jìn)而避免群體間適應(yīng)度相當(dāng)而造成的競爭減弱莹捡，導(dǎo)致種群收斂于局部最優(yōu)解
尺度變換常用方法有線性尺度變換、乘冪尺度變換以及指數(shù)尺度變換 - 選擇遺傳算子
選擇操作從舊群體中以一定概率選擇優(yōu)良個(gè)體組成新的種群扣甲，以繁殖得到下一代個(gè)體 - 交叉遺傳算子
交叉操作是指從種群中隨機(jī)選擇兩個(gè)個(gè)體篮赢，通過兩個(gè)染色體的交換組合，把父串的優(yōu)秀特征遺傳給子串琉挖，從而產(chǎn)生新的優(yōu)秀個(gè)體
常用的交叉算子有單點(diǎn)交叉启泣、雙點(diǎn)交叉或多點(diǎn)交叉、均勻交叉示辈、算術(shù)交叉等 - 變異遺傳算子
為了防止遺傳算法在優(yōu)化過程中陷入局部最優(yōu)解寥茫，在搜索過程中，需要對個(gè)體進(jìn)行變異
在實(shí)際應(yīng)用中矾麻，主要采用單點(diǎn)變異纱耻，也叫位變異芭梯，即只需要對基因序列中某一個(gè)位進(jìn)行變異 - 終止判斷條件
GA流程圖
干貨|遺傳算法解決帶時(shí)間窗的車輛路徑規(guī)劃問題(附j(luò)ava代碼及詳細(xì)注釋）
