進(jìn)化算法時(shí)間復(fù)雜度分析的理論、方法與工具

目錄
前言
第1章 進(jìn)化算法簡介 1
1.1 *優(yōu)化問題 1
1.2 進(jìn)化算法的概述 2
1.3 常用進(jìn)化算法 2
1.3.1 遺傳算法 3
1.3.2 分布估計(jì)算法 4
1.3.3 粒子群優(yōu)化算法 5
1.3.4 蟻群優(yōu)化算法 5
1.3.5 Memetic算法 6
1.3.6 差分進(jìn)化算法 7
1.4 本章小結(jié) 8
第2章 進(jìn)化算法的數(shù)學(xué)模型 9
2.1 進(jìn)化算法數(shù)學(xué)模型與基本理論研究進(jìn)展 9
2.2 進(jìn)化算法時(shí)間復(fù)雜度相關(guān)的數(shù)學(xué)模型 10
2.3 本章小結(jié) 17
第3章 基于Markov過程的理論與方法 18
3.1 基于Markov過程的進(jìn)化算法時(shí)間復(fù)雜度分析 18
3.1.1 進(jìn)化算法的Markov過程模型 18
3.1.2 基于Markov性的時(shí)間復(fù)雜度分析理論 19
3.1.3 簡單的EA時(shí)間復(fù)雜度分析案例 23
3.2 基于Markov過程的進(jìn)化規(guī)劃算法時(shí)間復(fù)雜度分析 26
3.2.1 進(jìn)化規(guī)劃算法簡介 26
3.2.2 進(jìn)化規(guī)劃算法的Markov過程模型 28
3.2.3 進(jìn)化規(guī)劃算法時(shí)間復(fù)雜度分析的基本理論 29
3.2.4 Gauss變異進(jìn)化規(guī)劃算法的時(shí)間復(fù)雜度分析 32
3.3 基于Markov過程的蟻群優(yōu)化算法時(shí)間復(fù)雜度分析 35
3.3.1 蟻群優(yōu)化算法簡介 35
3.3.2 蟻群優(yōu)化算法的Markov過程模型 37
3.3.3 蟻群優(yōu)化算法時(shí)間復(fù)雜度分析的基本理論 37
3.3.4 案例分析 40
3.4 本章小結(jié) 44
第4章 分層估計(jì)理論與方法 45
4.1 分層估計(jì)的定義與定理 45
4.1.1 適應(yīng)度分層的定義 46
4.1.2 分層估計(jì)定理的證明 47
4.2 分層估計(jì)分析實(shí)例 48
4.2.1 對(duì)ONEMAX問題的分析 48
4.2.2 對(duì)BINVAL問題的分析 49
4.2.3 對(duì)NEEDLE問題的分析 51
4.2.4 LEADINGONES問題 51
4.2.5 LONGPATHk問題 52
4.2.6 JUMPk問題 54
4.2.7 線性函數(shù)問題 56
4.3 本章小結(jié) 59
第5章 漂移分析理論與方法 61
5.1 漂移分析方法框架 61
5.2 加式漂移分析 62
5.3 乘式漂移分析 65
5.4 可變漂移分析 66
5.5 (1+1)EA求解線性函數(shù)的時(shí)間復(fù)雜度分析 68
5.6 本章小結(jié) 71
第6章 關(guān)系模型理論與方法 73
6.1 等態(tài)關(guān)系與強(qiáng)/弱態(tài)關(guān)系模型的理論與方法 73
6.1.1 進(jìn)化算法的等態(tài)關(guān)系模型 73
6.1.2 基于等態(tài)關(guān)系的進(jìn)化算法收斂性等價(jià)分析 76
6.1.3 基于強(qiáng)/弱態(tài)關(guān)系的進(jìn)化算法收斂性對(duì)比 78
6.1.4 基于等態(tài)關(guān)系的進(jìn)化算法收斂判別定理 79
6.1.5 案例分析 80
6.2 等同關(guān)系模型的理論與方法 84
6.2.1 期望首達(dá)時(shí)間的隨機(jī)過程模型 84
6.2.2 進(jìn)化算法的等同關(guān)系模型 86
6.2.3 性能對(duì)比不等式 88
6.2.4 案例分析 89
6.3 本章小結(jié) 99
第7章 平均増益理論與方法 100
7.1 連續(xù)型（1+1)EA算法的平均增益建模 100
7.1.1問題描述與算法簡介 101
7.1.2 連續(xù)型（1+1)EA算法的平均增益模型 102
7.2 連續(xù)型（1+1)EA算法個(gè)案的平均計(jì)算時(shí)間分析 104
7.2.1 標(biāo)準(zhǔn)正態(tài)分布的EA-I算法計(jì)算時(shí)間分析 105
7.2.2 均勻分布的EA-II算法計(jì)算時(shí)間分析 106
7.2.3 EA-I算法與EA-II算法的時(shí)間復(fù)雜度對(duì)比分析 107
7.3 基于平均增益模型的連續(xù)型進(jìn)化算法時(shí)間復(fù)雜度分析 109
7.3.1 連續(xù)型進(jìn)化算法的上鞅與停時(shí)模型 109
7.3.2平均增益定理 110
7.4 (1，*)ES在球函數(shù)問題上的平均首達(dá)時(shí)間分析 113
7.5 本章小結(jié) 116
第8章 帶噪聲的進(jìn)化算法的時(shí)間復(fù)雜度分析理論與方法 117
8.1 帶噪聲優(yōu)化問題與算法的建模分析 117
8.2 噪聲對(duì)時(shí)間復(fù)雜度的影響 121
8.3 噪聲處理對(duì)時(shí)間復(fù)雜度的影響 126
8.4 本章小結(jié) 129
第9章 進(jìn)化算法時(shí)間復(fù)雜度估算方法與軟件工具 130
9.1 基于平均增益模型的時(shí)間復(fù)雜度估算方法 130
9.1.1 基本框架 131
9.1.2 實(shí)驗(yàn)步驟 131
9.2 時(shí)間復(fù)雜度估算案例 133
9.2.1 進(jìn)化策略（1，*) ES的時(shí)間復(fù)雜度估算 133
9.2.2 進(jìn)化策略ES和CMA-ES的時(shí)間復(fù)雜度估算 134
9.2.3 改進(jìn)CMA-ES的時(shí)間復(fù)雜度估算 137
9.3 時(shí)間復(fù)雜度估算軟件工具 140
9.4 本章小結(jié) 144
參考文獻(xiàn) 145