進化算法時間復雜度分析的理論、方法與工具

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