群智能算法及其應(yīng)用

隨著人們對(duì)生命本質(zhì)的不斷了解，生命科學(xué)正以前所未有的速度迅猛發(fā)展，使人工智能的研究開(kāi)始擺脫經(jīng)典邏輯計(jì)算的束縛，大膽探索起新的非經(jīng)典計(jì)算途徑。在這種背景下，社會(huì)性動(dòng)物（如蟻群、蜂群、鳥(niǎo)群等）的自組織行為引起了人們的廣泛關(guān)注，許多學(xué)者對(duì)這種行為進(jìn)行數(shù)學(xué)建模并用計(jì)算機(jī)對(duì)其進(jìn)行仿真，這就產(chǎn)生了所謂的“群智能”。社會(huì)性動(dòng)物的妙處在于：個(gè)體的行為都很簡(jiǎn)單，但當(dāng)它們一起協(xié)同工作時(shí)，卻能夠“突現(xiàn)”出非常復(fù)雜（智能）的行為特征。例如，單只螞蟻的能力極其有限，但當(dāng)這些簡(jiǎn)單的螞蟻組成蟻群時(shí)，卻能完成像筑巢、覓食、遷徙、清掃蟻巢等復(fù)雜行為；一群行為顯得盲目的蜂群能造出精美的蜂窩；鳥(niǎo)群在沒(méi)有集中控制的情況下能夠同步飛行等。在這些自組織行為中，又以蟻群在覓食過(guò)程中總能找到一條從蟻巢到食物源的最短路徑最為引人注目。

20世紀(jì)50年代中期創(chuàng)立了仿生學(xué)，人們從生物進(jìn)化的機(jī)理中受到啟發(fā)，提出了許多用以解決復(fù)雜優(yōu)化問(wèn)題的新方法，如遺傳算法、進(jìn)化規(guī)劃、進(jìn)化策略等。群智能算法作為一種新興的演化計(jì)算技術(shù)已成為越來(lái)越多研究者的關(guān)注焦點(diǎn)，它與人工生命，特別是進(jìn)化策略以及遺傳算法有著極為特殊的聯(lián)系。群智能理論研究領(lǐng)域目前有兩種主要的算法：蟻群算法和粒子群優(yōu)化算法。本書(shū)系統(tǒng)地描述了蟻群算法和粒子群優(yōu)化算法的理論和實(shí)現(xiàn)技術(shù)及其應(yīng)用，著重強(qiáng)調(diào)各種算法的混合；討論了蟻群算法與模擬退火算法的混合、蟻群算法與遺傳算法的混合、蟻群算法與混沌理論混合、模擬退火算法遺傳算法與粒子群優(yōu)化算法混合以及蟻群算法與粒子群優(yōu)化算法的混合。還討論了群智能算法在旅行商、武器－目標(biāo)分配、多處理機(jī)調(diào)度、可靠性優(yōu)化、聚類(lèi)等方面的應(yīng)用。

本書(shū)由15章組成。第1章先介紹了蟻群算法的基本原理，綜述了蟻群算法理論研究現(xiàn)狀和蟻群算法應(yīng)用研究現(xiàn)狀，粒子群優(yōu)化算法理論研究現(xiàn)狀和粒子群優(yōu)化應(yīng)用研究現(xiàn)狀。第2章先研究了求解一般非線性整數(shù)規(guī)劃的蟻群算法，然后提出了求解武器－目標(biāo)分配問(wèn)題、多處理機(jī)調(diào)度問(wèn)題、可靠性優(yōu)化的蟻群算法，最后提出了多樣信息素的蟻群算法。第3章提出了一種求解連續(xù)優(yōu)化問(wèn)題的蟻群算法。第4章提出了求解聚類(lèi)問(wèn)題的基本蟻群算法和與K-均值算法混合的蟻群算法。第5章提出了與模擬退火算法混合的蟻群模擬退火算法求解圓排列問(wèn)題以及模擬退火蟻群算法求解旅行商問(wèn)題。第6章首先介紹了基本遺傳算法，然后提出了與遺傳算法混合的遺傳蟻群算法，最后與其他算法進(jìn)行了測(cè)試比較。第7章首先介紹了混沌及運(yùn)動(dòng)特性，接著提出與混沌理論混合的混沌蟻群算法，最后與其他算法進(jìn)行了測(cè)試比較。第8章針對(duì)最短路問(wèn)題的蟻群算法的收斂性進(jìn)行了探索性分析，提出的三個(gè)定理給出了尋找最短路的蟻群算法收斂的充分條件。第9章介紹了采用模擬退火思想的粒子群算法、混沌粒子群優(yōu)化算法來(lái)解連續(xù)性優(yōu)化問(wèn)題。第10章提出了采用粒子群優(yōu)化來(lái)求解背包問(wèn)題、指派問(wèn)題、武器?目標(biāo)分配問(wèn)題和流水作業(yè)調(diào)度問(wèn)題等其他組合優(yōu)化問(wèn)題。第11章提出了采用求解聚類(lèi)問(wèn)題的兩種粒子群優(yōu)化算法。第12章提出了與粒子群優(yōu)化算法兩種混合算法，并用來(lái)求解旅行商問(wèn)題。第13章對(duì)粒子群優(yōu)化算法的收斂性進(jìn)行了分析，提出收斂的條件。第14章簡(jiǎn)單地介紹了魚(yú)群算法的基本原理及應(yīng)用。第15章對(duì)本書(shū)作了一個(gè)總結(jié)，提出了今后研究的方向。最后，本書(shū)在附錄中給出了求解旅行商問(wèn)題的蟻群基本算法源程序、計(jì)算連續(xù)性函數(shù)的優(yōu)化的粒子群程序和求解旅行商問(wèn)題的粒子 群?蟻群算法的MATLAB語(yǔ)言源程序。

本書(shū)可作為信息類(lèi)的高年級(jí)本科生、碩士生、博士生以及廣大研究智能算法的科技工作者的參考書(shū)。由于作者水平有限，對(duì)于本書(shū)的不足之處，誠(chéng)望讀者批評(píng)指正。

感謝江蘇科技大學(xué)的張?jiān)佘S教授、鄧志良教授、吳小俊教授、劉同明教授、韓斌副教授等以及有關(guān)部門(mén)給予的支持，感謝南京理工大學(xué)603教研室老師的支持。此外，本書(shū)的完成得到了蘇州大學(xué)江蘇省計(jì)算機(jī)信息處理技術(shù)重點(diǎn)實(shí)驗(yàn)室開(kāi)放課題、江蘇省自然科學(xué)基金、江蘇科技大學(xué)博士啟動(dòng)基金等項(xiàng)目的資助，在此表示衷心感謝。

作者

2006年2月

前言
第1章 緒論 1
1.1 引言 1
1.2 蟻群算法的基本原理 2
1.3 粒子群優(yōu)化算法基本原理 6
1.4 蟻群算法理論研究現(xiàn)狀 10
1.5 蟻群算法應(yīng)用研究現(xiàn)狀 12
1.6 粒子群優(yōu)化算法研究現(xiàn)狀 13
1.7 粒子群算法應(yīng)用研究現(xiàn)狀 15
第2章 求解整數(shù)規(guī)劃的蟻群算法 17
2.1 求解一般非線性整數(shù)規(guī)劃的蟻群算法 17
2.1.1 引言 17
2.1.2 求解非線性整數(shù)規(guī)劃的蟻群算法 17
2.1.3 算例分析 19
2.2 武器－目標(biāo)分配問(wèn)題的蟻群算法 21
2.2.1 引言 21
2.2.2 WTA問(wèn)題 21
2.2.3 武器－目標(biāo)分配問(wèn)題的蟻群算法 22
2.2.4 仿真結(jié)果 23
2.3 多處理機(jī)調(diào)度問(wèn)題的蟻群算法 24
2.3.1 引言 24
2.3.2 多處理機(jī)調(diào)度問(wèn)題數(shù)學(xué)模型 24
2.3.3 解多處理機(jī)調(diào)度問(wèn)題模擬退火算法 25
2.3.4 解多處理機(jī)調(diào)度問(wèn)題蟻群算法 26
2.3.5 算法比較 26
2.4 可靠性優(yōu)化的蟻群算法 28
2.4.1 引言 28
2.4.2 最優(yōu)冗余優(yōu)化模型及解法 28
2.4.3 可靠性優(yōu)化的模擬退火算法 29
2.4.4 可靠性優(yōu)化的遺傳算法 29
2.4.5 可靠性優(yōu)化的蟻群算法 31
2.4.6 算例分析 32
2.5 求解旅行商問(wèn)題的多樣信息素的蟻群算法 34
2.5.1 信息素更新的3個(gè)模型 34
2.5.2 多樣信息素更新規(guī)則 34
2.5.3 算法測(cè)試 34
2.6 本章小結(jié) 36
第3章 連續(xù)優(yōu)化問(wèn)題的蟻群算法研究 38
3.1 無(wú)約束非線性最優(yōu)化問(wèn)題 38
3.2 連續(xù)優(yōu)化問(wèn)題的信息量分布函數(shù)方法 38
3.3 一種簡(jiǎn)單的連續(xù)優(yōu)化問(wèn)題的蟻群算法 39
3.4 數(shù)值分析 41
3.5 本章小結(jié) 42
第4章 聚類(lèi)問(wèn)題的蟻群算法 43
4.1 引言 43
4.2 聚類(lèi)問(wèn)題的數(shù)學(xué)模型 43
4.3 K均值算法 44
4.4 解聚類(lèi)問(wèn)題的模擬退火算法 44
4.5 基于巡食思想的蟻群聚類(lèi)算法 44
4.6 解聚類(lèi)問(wèn)題的新的蟻群算法及數(shù)值分析 46
4.6.1 解聚類(lèi)問(wèn)題的蟻群算法 46
4.6.2 數(shù)值分析 46
4.7 解聚類(lèi)問(wèn)題的與K-均值算法混合的蟻群算法及數(shù)值分析 48
4.7.1 解聚類(lèi)問(wèn)題的K-均值算法混合的蟻群算法 48
4.7.2 數(shù)值分析 48
4.8 本章小結(jié) 49
第5章 蟻群算法與模擬退火算法混合 50
5.1 引言 50
5.2 解圓排列問(wèn)題的蟻群模擬退火算法 50
5.2.1 圓排列問(wèn)題及與旅行商問(wèn)題等價(jià) 50
5.2.2 解旅行商問(wèn)題的模擬退火算法 51
5.2.3 幾種算法的比較 52
5.2.4 算例分析 53
5.3 解旅行商問(wèn)題的模擬退火蟻群算法 54
5.3.1 混合的基本思想 54
5.3.2 找鄰域解策略 55
5.3.3 模擬退火蟻群算法 55
5.3.4 算法測(cè)試 56
5.4 本章小結(jié) 57
第6章 蟻群算法與遺傳算法混合 58
6.1 引言 58
6.2 基本遺傳算法 58
6.3 蟻群算法與遺傳算法的混合 59
6.3.1 混合的基本思想 59
6.3.2 變異操作 59
6.3.3 交叉操作 60
6.3.4 遺傳蟻群算法 60
6.4 算法測(cè)試 61
6.5 本章小結(jié) 62
第7章 蟻群算法與混沌理論混合 63
7.1 引言 63
7.2 混沌及運(yùn)動(dòng)特性 63
7.3 基本蟻群算法改進(jìn) 63
7.3.1 混沌初始化 63
7.3.2 選擇較優(yōu)解 65
7.3.3 混沌擾動(dòng) 65
7.4 混沌蟻群算法 66
7.5 算法測(cè)試 66
7.6 本章小結(jié) 68
第8章 最短路的蟻群算法收斂性分析 69
8.1 引言 69
8.2 最短路的蟻群算法收斂性分析 69
8.3 仿真算例 71
8.4 本章小結(jié) 76
第9章 解連續(xù)性優(yōu)化問(wèn)題的粒子群優(yōu)化算法 77
9.1 模擬退火思想的粒子群算法 77
9.1.1 幾種模擬退火思想的粒子群算法 77
9.1.2 算法測(cè)試 78
9.2 混沌粒子群優(yōu)化算法研究 79
9.2.1 基本粒子群算法不足 79
9.2.2 混沌粒子群優(yōu)化算法 80
9.2.3 算法測(cè)試 80
9.3 其他改進(jìn)的粒子群優(yōu)化算法 82
9.3.1 雜交PSO算法 82
9.3.2 協(xié)同PSO算法 83
9.3.3 離散PSO算法 83
9.4 本章小結(jié) 84
第10章 解組合優(yōu)化問(wèn)題的粒子群優(yōu)化算法 85
10.1 背包問(wèn)題的混合粒子群優(yōu)化算法 85
10.1.1 背包問(wèn)題數(shù)學(xué)模型 85
10.1.2 解0-1背包問(wèn)題的混合粒子群算法 85
10.1.3 數(shù)值仿真與分析 87
10.2 指派問(wèn)題的交叉粒子群優(yōu)化算法 89
10.2.1 求解指派問(wèn)題的交叉粒子群優(yōu)化算法 89
10.2.2 算法測(cè)試 90
10.3 武器－目標(biāo)分配問(wèn)題的粒子群優(yōu)化算法 91
10.3.1 解武器－目標(biāo)分配問(wèn)題的粒子群優(yōu)化算法 91
10.3.2 算例分析 92
10.4 流水作業(yè)調(diào)度問(wèn)題的粒子群算法 93
10.4.1 流水作業(yè)調(diào)度問(wèn)題 93
10.4.2 求解流水作業(yè)調(diào)度問(wèn)題混合粒子群算法 93
10.4.3 算法測(cè)試 95
10.5 非線性整數(shù)規(guī)劃的粒子群優(yōu)化算法 96
10.5.1 引言 96
10.5.2 求解非線性整數(shù)規(guī)劃的粒子群優(yōu)化算法 96
10.5.3 算例分析 97
10.6 本章小結(jié) 99
第11章 解聚類(lèi)問(wèn)題的粒子群算法 100
11.1 引言 100
11.2 整數(shù)規(guī)劃形式 100
11.3 連續(xù)性優(yōu)化形式 101
11.4 本章小結(jié) 103
第12章 蟻群算法與粒子群優(yōu)化算法的混合 104
12.1 引言 104
12.2 求解旅行商問(wèn)題的混合粒子群優(yōu)化算法 104
12.2.1 混合粒子群算法思路 104
12.2.2 變異操作和交叉操作 104
12.2.3 混合粒子群算法步驟 105
12.2.4 算法測(cè)試 105
12.3 求解旅行商問(wèn)題的粒子群－蟻群算法 108
12.3.1 粒子群－蟻群算法思想 108
12.3.2 粒子群－蟻群算法步驟 108
12.3.3 算法測(cè)試 109
12.4 本章小結(jié) 111
第13章 粒子群優(yōu)化算法收斂性分析 112
13.1 引言 112
13.2 PSO算法收斂性分析 112
13.3 數(shù)值仿真 114
13.4 參數(shù)選取 117
13.5 本章小結(jié) 117
第14章 魚(yú)群算法 118
14.1 引言 118
14.2 魚(yú)群算法基本原理 118
14.3 人工魚(yú)的行為描述 119
14.4 魚(yú)群算法的應(yīng)用 122
14.5 本章小結(jié) 122
第15章 總結(jié) 124
附錄A 求解旅行商問(wèn)題的蟻群基本算法源程序 127
附錄B 計(jì)算連續(xù)性函數(shù)的優(yōu)化的粒子群程序 131
附錄C 求解旅行商問(wèn)題的粒子群?蟻群算法的源程序 134
參考文獻(xiàn) 143

1. 人工智能算法與實(shí)踐 [主編　梁琨　張翼英]