進(jìn)化算法時間復(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 分布估計算法 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)化算法時間復(fù)雜度相關(guān)的數(shù)學(xué)模型 10
2.3 本章小結(jié) 17
第3章 基于Markov過程的理論與方法 18
3.1 基于Markov過程的進(jìn)化算法時間復(fù)雜度分析 18
3.1.1 進(jìn)化算法的Markov過程模型 18
3.1.2 基于Markov性的時間復(fù)雜度分析理論 19
3.1.3 簡單的EA時間復(fù)雜度分析案例 23
3.2 基于Markov過程的進(jìn)化規(guī)劃算法時間復(fù)雜度分析 26
3.2.1 進(jìn)化規(guī)劃算法簡介 26
3.2.2 進(jìn)化規(guī)劃算法的Markov過程模型 28
3.2.3 進(jìn)化規(guī)劃算法時間復(fù)雜度分析的基本理論 29
3.2.4 Gauss變異進(jìn)化規(guī)劃算法的時間復(fù)雜度分析 32
3.3 基于Markov過程的蟻群優(yōu)化算法時間復(fù)雜度分析 35
3.3.1 蟻群優(yōu)化算法簡介 35
3.3.2 蟻群優(yōu)化算法的Markov過程模型 37
3.3.3 蟻群優(yōu)化算法時間復(fù)雜度分析的基本理論 37
3.3.4 案例分析 40
3.4 本章小結(jié) 44
第4章 分層估計理論與方法 45
4.1 分層估計的定義與定理 45
4.1.1 適應(yīng)度分層的定義 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 本章小結(jié) 59
第5章 漂移分析理論與方法 61
5.1 漂移分析方法框架 61
5.2 加式漂移分析 62
5.3 乘式漂移分析 65
5.4 可變漂移分析 66
5.5 (1+1)EA求解線性函數(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)化算法收斂性等價分析 76
6.1.3 基于強(qiáng)/弱態(tài)關(guān)系的進(jìn)化算法收斂性對比 78
6.1.4 基于等態(tài)關(guān)系的進(jìn)化算法收斂判別定理 79
6.1.5 案例分析 80
6.2 等同關(guān)系模型的理論與方法 84
6.2.1 期望首達(dá)時間的隨機(jī)過程模型 84
6.2.2 進(jìn)化算法的等同關(guān)系模型 86
6.2.3 性能對比不等式 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算法個案的平均計算時間分析 104
7.2.1 標(biāo)準(zhǔn)正態(tài)分布的EA-I算法計算時間分析 105
7.2.2 均勻分布的EA-II算法計算時間分析 106
7.2.3 EA-I算法與EA-II算法的時間復(fù)雜度對比分析 107
7.3 基于平均增益模型的連續(xù)型進(jìn)化算法時間復(fù)雜度分析 109
7.3.1 連續(xù)型進(jìn)化算法的上鞅與停時模型 109
7.3.2平均增益定理 110
7.4 (1，*)ES在球函數(shù)問題上的平均首達(dá)時間分析 113
7.5 本章小結(jié) 116
第8章 帶噪聲的進(jìn)化算法的時間復(fù)雜度分析理論與方法 117
8.1 帶噪聲優(yōu)化問題與算法的建模分析 117
8.2 噪聲對時間復(fù)雜度的影響 121
8.3 噪聲處理對時間復(fù)雜度的影響 126
8.4 本章小結(jié) 129
第9章 進(jìn)化算法時間復(fù)雜度估算方法與軟件工具 130
9.1 基于平均增益模型的時間復(fù)雜度估算方法 130
9.1.1 基本框架 131
9.1.2 實驗步驟 131
9.2 時間復(fù)雜度估算案例 133
9.2.1 進(jìn)化策略（1，*) ES的時間復(fù)雜度估算 133
9.2.2 進(jìn)化策略ES和CMA-ES的時間復(fù)雜度估算 134
9.2.3 改進(jìn)CMA-ES的時間復(fù)雜度估算 137
9.3 時間復(fù)雜度估算軟件工具 140
9.4 本章小結(jié) 144
參考文獻(xiàn) 145