智能計(jì)算導(dǎo)論

1

1.1引言

1.1.1優(yōu)化問題

1.1.2傳統(tǒng)優(yōu)化方法

1.1.3現(xiàn)代優(yōu)化方法

1.2最優(yōu)化問題及其分類

1.2.1函數(shù)優(yōu)化問題

1.2.2組合優(yōu)化問題

1.3啟發(fā)式算法

1.3.1啟發(fā)式算法的定義

1.3.2啟發(fā)式算法的分類

1.3.3啟發(fā)式算法的性能分析

1.4計(jì)算復(fù)雜性與NP完全問題

1.4.1計(jì)算復(fù)雜性的基本概念

1.4.2P,NP,NP-C和NP-hard

智能優(yōu)化計(jì)算2

1.1引言

智能優(yōu)化計(jì)算優(yōu)化技術(shù)？以數(shù)學(xué)為基礎(chǔ)，解決各種工程問題優(yōu)化解優(yōu)化技術(shù)的用途系統(tǒng)控制人工智能模式識(shí)別生產(chǎn)調(diào)度

……

1.1.1優(yōu)化問題

3

1.1引言

智能優(yōu)化計(jì)算最優(yōu)化問題的描述

最優(yōu)化問題的數(shù)學(xué)模型的一般描述：

1.1.1優(yōu)化問題

4

1.1引言

智能優(yōu)化計(jì)算待解決的問題

連續(xù)性問題，以微積分為基礎(chǔ)，規(guī)模較小、多峰多谷傳統(tǒng)的優(yōu)化方法

理論上的準(zhǔn)確與完美，主要方法：線性與非線性規(guī)劃、動(dòng)態(tài)規(guī)劃、多目標(biāo)規(guī)劃、整數(shù)規(guī)劃等；排隊(duì)論、庫存論、對(duì)策論、決策論等。

傳統(tǒng)的評(píng)價(jià)方法

算法收斂性、收斂速度

1.1.2傳統(tǒng)優(yōu)化方法

5

1.1引言

智能優(yōu)化計(jì)算待解決的問題

離散性、不確定性、大規(guī)?，F(xiàn)代的優(yōu)化方法啟發(fā)式算法（heuristicalgorithm）追求滿意（近似解）實(shí)用性強(qiáng)（解決實(shí)際工程問題）現(xiàn)代的評(píng)價(jià)方法算法復(fù)雜性

1.1.3現(xiàn)代優(yōu)化方法

6

1.2最優(yōu)化問題及其分類（函數(shù)優(yōu)化和組合優(yōu)化）智能優(yōu)化計(jì)算數(shù)學(xué)表述

難點(diǎn)高維多峰值

1.2.1函數(shù)優(yōu)化問題

7

1.2.2常見求解方法

1.一維函數(shù)優(yōu)化

優(yōu)選法：黃金分割法、分?jǐn)?shù)法、正交實(shí)驗(yàn)設(shè)計(jì)特點(diǎn)：只能解決單峰函數(shù)的最優(yōu)值問題搜索法：按照某種方向（如最速下降方向、梯度方向）選取步長搜索（是一種迭代技術(shù)）2.多維函數(shù)優(yōu)化

特點(diǎn)：迭代+搜索選取初始點(diǎn)、按照某個(gè)方向（如最速下降方向、梯度方向）選取步長搜索最速下降法、梯度與共軛梯度法、Newton法（擬Newton法）等等一般只能解決單峰函數(shù)的最優(yōu)化問題（why?)8

測試函數(shù)（8）GeneralizedSchwefel’sProblem2.26(multimodal)典型的多峰、多谷函數(shù)，確定性算法求解很可能導(dǎo)致局部最優(yōu)9

1.2最優(yōu)化問題及其分類

智能優(yōu)化計(jì)算（1）SphereModel(unimodal)

其最優(yōu)狀態(tài)和最優(yōu)值為

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題

10

1.2最優(yōu)化問題及其分類

智能優(yōu)化計(jì)算測試函數(shù)（2）Schwefel’sProblem2.22(unimodal)

其最優(yōu)狀態(tài)和最優(yōu)值為

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題11

1.2最優(yōu)化問題及其分類

智能優(yōu)化計(jì)算測試函數(shù)（3）Schwefel’sProblem1.2

其最優(yōu)狀態(tài)和最優(yōu)值為

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題12

1.2最優(yōu)化問題及其分類

智能優(yōu)化計(jì)算測試函數(shù)（4）Schwefel’sProblem2.21

其最優(yōu)狀態(tài)和最優(yōu)值為

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題13

1.2最優(yōu)化問題及其分類

智能優(yōu)化計(jì)算測試函數(shù)（5）GeneralizedRosenbrock’sFunction

其最優(yōu)狀態(tài)和最優(yōu)值為

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題14

1.2最優(yōu)化問題及其分類

智能優(yōu)化計(jì)算測試函數(shù)（6）StepFunction

其最優(yōu)狀態(tài)和最優(yōu)值為

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題15

1.2最優(yōu)化問題及其分類

智能優(yōu)化計(jì)算測試函數(shù)（6）StepFunction

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題16

1.2最優(yōu)化問題及其分類

智能優(yōu)化計(jì)算測試函數(shù)（7）QuarticFunctioni.e.Niose

其最優(yōu)狀態(tài)和最優(yōu)值為

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題17

1.2最優(yōu)化問題及其分類

智能優(yōu)化計(jì)算測試函數(shù)（8）GeneralizedSchwefel’sProblem2.26

其最優(yōu)狀態(tài)和最優(yōu)值為

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題18

1.2最優(yōu)化問題及其分類

智能優(yōu)化計(jì)算測試函數(shù)（8）GeneralizedSchwefel’sProblem2.26(multimodal)

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題19

1.2最優(yōu)化問題及其分類

智能優(yōu)化計(jì)算測試函數(shù)（9）GeneralizedRastrigin’sFunction

其最優(yōu)狀態(tài)和最優(yōu)值為

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題20

1.2最優(yōu)化問題及其分類

智能優(yōu)化計(jì)算測試函數(shù)（10）Ackley’sFunction

其最優(yōu)狀態(tài)和最優(yōu)值為

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題21

1.2最優(yōu)化問題及其分類

智能優(yōu)化計(jì)算測試函數(shù)（10）Ackley’sFunction

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題22

1.2最優(yōu)化問題及其分類

智能優(yōu)化計(jì)算測試函數(shù)（11）GeneralizedGriewankFunction

其最優(yōu)狀態(tài)和最優(yōu)值為

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題23

1.2最優(yōu)化問題及其分類

智能優(yōu)化計(jì)算測試函數(shù)（11）GeneralizedGriewankFunction

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題24

1.2最優(yōu)化問題及其分類

智能優(yōu)化計(jì)算測試函數(shù)（12）GeneralizedPenalizedFunction

其最優(yōu)狀態(tài)和最優(yōu)值為

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題25

1.2最優(yōu)化問題及其分類

智能優(yōu)化計(jì)算測試函數(shù)其中，

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題26

1.2最優(yōu)化問題及其分類

智能優(yōu)化計(jì)算測試函數(shù)（13）GeneralizedPenalizedFunction

其最優(yōu)狀態(tài)和最優(yōu)值為

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題27

1.2最優(yōu)化問題及其分類

智能優(yōu)化計(jì)算測試函數(shù)（14）Shekel’sFoxholesFunction

其最優(yōu)狀態(tài)和最優(yōu)值為

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題28

1.2最優(yōu)化問題及其分類

智能優(yōu)化計(jì)算測試函數(shù)其中，

1.2.3函數(shù)優(yōu)化之常見的

Benchmark問題29

1.2最優(yōu)化問題及其分類

智能優(yōu)化計(jì)算測試函數(shù)（15）Kowalik’sFunction

其最優(yōu)狀態(tài)和最優(yōu)值為

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題30

1.2最優(yōu)化問題及其分類

智能優(yōu)化計(jì)算測試函數(shù)其中，

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題31

1.2最優(yōu)化問題及其分類

智能優(yōu)化計(jì)算測試函數(shù)（16）Six-HumpCamel-BackFunction

其最優(yōu)狀態(tài)和最優(yōu)值為

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題32

1.2最優(yōu)化問題及其分類

智能優(yōu)化計(jì)算測試函數(shù)（17）BraninFunction

其最優(yōu)狀態(tài)和最優(yōu)值為

1.2.3函數(shù)優(yōu)化之常見的

Benchmark問題33

1.2最優(yōu)化問題及其分類

智能優(yōu)化計(jì)算測試函數(shù)（18）Goldstein-PriceFunction

其最優(yōu)狀態(tài)和最優(yōu)值為

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題34

1.2最優(yōu)化問題及其分類

智能優(yōu)化計(jì)算測試函數(shù)（19）Hartman’sFunction

其最優(yōu)狀態(tài)和最優(yōu)值為

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題35

1.2最優(yōu)化問題及其分類

智能優(yōu)化計(jì)算測試函數(shù)（20）Hartman’sFunction

其最優(yōu)狀態(tài)和最優(yōu)值為

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題36

1.2最優(yōu)化問題及其分類

智能優(yōu)化計(jì)算測試函數(shù)（21）Shekel’sFamily

m分別取5，7和10，其最優(yōu)狀態(tài)和最優(yōu)值為

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題37

1.2最優(yōu)化問題及其分類

智能優(yōu)化計(jì)算測試函數(shù)（22）J.D.Schaffer

其最優(yōu)狀態(tài)和最優(yōu)值為

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題38

1.2最優(yōu)化問題及其分類

智能優(yōu)化計(jì)算測試函數(shù)（22）J.D.Schaffer

此函數(shù)在距全局最優(yōu)點(diǎn)大約3.14范圍內(nèi)存在無窮多個(gè)局部極小將其包圍，并且函數(shù)強(qiáng)烈振蕩。

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題39

1.2最優(yōu)化問題及其分類

智能優(yōu)化計(jì)算有約束的函數(shù)優(yōu)化常用受約束測試函數(shù)；影響因素：（1）曲面拓?fù)湫再|(zhì)，線性或凸函數(shù)比無規(guī)律的函數(shù)更容易求解；（2）可行區(qū)域的疏密程度，通常以可行區(qū)域占整個(gè)搜索空間的比值來度量；

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題40

1.2最優(yōu)化問題及其分類

智能優(yōu)化計(jì)算有約束的函數(shù)優(yōu)化常用受約束測試函數(shù)；影響因素：（3）整個(gè)搜索空間中整體最優(yōu)解與可行區(qū)域最優(yōu)解之比，特別當(dāng)整體最憂解離可行區(qū)域很近時(shí)將使其對(duì)懲罰項(xiàng)非常敏感；（4）在最優(yōu)解處活躍約束的數(shù)目，活躍約束數(shù)目越多則最優(yōu)解離可行區(qū)域的邊界越近。

1.2.3函數(shù)優(yōu)化之常見的Benchmark問題41

1.2最優(yōu)化問題及其分類

智能優(yōu)化計(jì)算數(shù)學(xué)表述所屬范疇涉及離散事件的最優(yōu)編排、分類、次序篩選等問題，是運(yùn)籌學(xué)的一個(gè)重要分支。

1.2.4組合優(yōu)化問題

42

1.2最優(yōu)化問題及其分類

智能優(yōu)化計(jì)算典型問題——旅行商問題（Travelingsalesmanproblem,TSP）給定n個(gè)城市和兩兩城市之間的距離，要求確定一條經(jīng)過各城市當(dāng)且僅當(dāng)一次的最短路線。

1.2.2組合優(yōu)化問題

12341218103243TSP問題實(shí)例10城市TSP問題20城市TSP問題44TSP問題實(shí)例230城市TSP問題48城市TSP問題45

1.2最優(yōu)化問題及其分類

智能優(yōu)化計(jì)算典型問題——旅行商問題（Travelingsalesmanproblem,TSP）計(jì)算復(fù)雜度：指數(shù)災(zāi)難

1.2.2組合優(yōu)化問題

城市數(shù)2425262728293031計(jì)算時(shí)間1sec24sec10min4.3hour4.9day136.5day10.8year325year46

1.2最優(yōu)化問題及其分類

智能優(yōu)化計(jì)算典型問題——加工調(diào)度問題（Schedulingproblem,如Flow-shop,Job-shop）

Job-shop：n個(gè)工件在m臺(tái)機(jī)器上加工，Oij：第i個(gè)工件在第j臺(tái)機(jī)器上的操作，Tij：相應(yīng)的操作時(shí)間已知。事先給定各工件在各機(jī)器上的加工次序（技術(shù)約束條件），要求確定與技術(shù)約束條件相容的各機(jī)器上所有工件的加工順序，使得加工性能指標(biāo)達(dá)到最優(yōu)。若各工件技術(shù)約束條件相同，轉(zhuǎn)化為Flow-shop。

1.2.2組合優(yōu)化問題

47

1.2最優(yōu)化問題及其分類

智能優(yōu)化計(jì)算典型問題——加工調(diào)度問題（Schedulingproblem,如Flow-shop,Job-shop）計(jì)算復(fù)雜性：可能的排列方式有（n?。﹎

多目標(biāo)優(yōu)化動(dòng)態(tài)性狀態(tài)相依

1.2.2組合優(yōu)化問題

48

1.2最優(yōu)化問題及其分類

智能優(yōu)化計(jì)算典型問題——0－1背包問題（Knapsackproblem）對(duì)于n個(gè)體積為ai、價(jià)值分別為ci的物品，如何將它們裝入總體積為b的背包中，使得所選物品的總價(jià)值最大。

1.2.2組合優(yōu)化問題

背包問題的貪婪算法49

1.2最優(yōu)化問題及其分類

智能優(yōu)化計(jì)算典型問題——裝箱問題（Binpackingproblem）有n個(gè)尺寸不超過1的物品，有數(shù)個(gè)尺寸為1的箱子，如何將這些物品裝入箱子，使得所需箱子的個(gè)數(shù)最少。

1.2.2組合優(yōu)化問題

50

1.2最優(yōu)化問題及其分類

智能優(yōu)化計(jì)算典型問題——圖著色問題（Graphcoloringproblem）對(duì)于n個(gè)頂點(diǎn)的無環(huán)圖G，要求對(duì)其各個(gè)頂點(diǎn)進(jìn)行著色，使得任意兩個(gè)相鄰的頂點(diǎn)都有不同的顏色，且所用顏色種類最少。

1.2.2組合優(yōu)化問題

C1：第一種顏色C2：第二種顏色C3：第三種顏色C1C1C2C3C2ABDCE51

1.2最優(yōu)化問題及其分類

智能優(yōu)化計(jì)算典型問題——聚類問題（Clusteringproblem）

m維空間上的n個(gè)模式{Xi|i=1,2,…,n}，要求聚成k類，使得各類本身內(nèi)的點(diǎn)最相近，如要求其中Rp為第p類的中心，即

其中，p=1,2,…,k，np為第p類中的點(diǎn)數(shù)。

1.2.2組合優(yōu)化問題

52

1.2最優(yōu)化問題及其分類

智能優(yōu)化計(jì)算典型問題——任務(wù)分配問題（TaskAssignmentProblemTAP）

TAP是把一個(gè)應(yīng)用程序（application)的任務(wù)（Tasks）分配到分布式計(jì)算系統(tǒng)中的計(jì)算機(jī)上，目標(biāo)是優(yōu)化某個(gè)或某幾個(gè)性能指標(biāo)。

1.2.2組合優(yōu)化問題

53

1.2最優(yōu)化問題及其分類

智能優(yōu)化計(jì)算典型問題——任務(wù)分配問題（TAP）

1.2.2組合優(yōu)化問題

54

1.2最優(yōu)化問題及其分類

智能優(yōu)化計(jì)算

1.2.2組合優(yōu)化問題

典型問題——任務(wù)分配問題（TAP）

應(yīng)用程序用任務(wù)交互圖（TaskInteractionGraphTIG）G(V,ET)表示，其中V=(1,2,…m)表示任務(wù)集合，ET表示邊的集合，每條邊表示任務(wù)之間的交互（通信）。55

1.2最優(yōu)化問題及其分類

智能優(yōu)化計(jì)算

1.2.2組合優(yōu)化問題

典型問題——任務(wù)分配問題（TaskAssignmentProblemTAP）

分布式計(jì)算系統(tǒng)用處理機(jī)交互圖（ProcessorsInteractionGraphPIG）G(P,ET)表示，其中P=(1,2,…n)表示系統(tǒng)中處理機(jī)的集合，ET表示通信鏈路的集合，每條邊表示一條通信鏈路。56

1.2最優(yōu)化問題及其分類

智能優(yōu)化計(jì)算

1.2.2組合優(yōu)化問題

典型問題——任務(wù)分配問題（TaskAssignmentProblemTAP）

我們這里仿真局域網(wǎng)分布式計(jì)算系統(tǒng)。并假設(shè)處理機(jī)異構(gòu)（Heterogeneous）,及每個(gè)任務(wù)在各個(gè)處理機(jī)上的執(zhí)行時(shí)間不同；網(wǎng)絡(luò)同構(gòu)，即所有鏈路的通信速度相同。

57

智能優(yōu)化計(jì)算

1.2.2組合優(yōu)化問題

典型問題——任務(wù)分配問題（TAP）

優(yōu)化目標(biāo)1：最小化執(zhí)行代價(jià)與通信代價(jià)之和1.2最優(yōu)化問題及其分類任務(wù)執(zhí)行代價(jià)：處理機(jī)之間的通信代價(jià)：58

1.2最優(yōu)化問題及其分類智能優(yōu)化計(jì)算

1.2.2組合優(yōu)化問題

典型問題——任務(wù)分配問題（TAP）

優(yōu)化目標(biāo)1：最小化執(zhí)行代價(jià)與通信代價(jià)之和分配方案A總代價(jià)：TAP的目標(biāo)是找到一種具有最小代價(jià)的分配方案：59

1.2最優(yōu)化問題及其分類智能優(yōu)化計(jì)算

1.2.2組合優(yōu)化問題

典型問題——任務(wù)分配問題（TAP）也可描述為有約束的0-1二次整數(shù)規(guī)劃問題：其中r是任務(wù)數(shù)，n是處理機(jī)數(shù)，mi是任務(wù)i的存儲(chǔ)需求，pi是任務(wù)i的計(jì)算負(fù)載需求。60

智能優(yōu)化計(jì)算

1.2.2組合優(yōu)化問題

典型問題——任務(wù)分配問題（TAP）

優(yōu)化目標(biāo)2：最小化周轉(zhuǎn)時(shí)間（turnaroundtime)1.2最優(yōu)化問題及其分類分配到處理機(jī)k上的任務(wù)總的執(zhí)行代價(jià)：分配到處理機(jī)k上的任務(wù)與分配到其它處理機(jī)上的任務(wù)總的通信代價(jià)：61

智能優(yōu)化計(jì)算

1.2.2組合優(yōu)化問題

典型問題——任務(wù)分配問題（TAP）

優(yōu)化目標(biāo)2：最小化周轉(zhuǎn)時(shí)間（turnaroundtime)1.2最優(yōu)化問題及其分類對(duì)于某一給定的分配方案A，處理機(jī)k總的執(zhí)行代價(jià)：62

智能優(yōu)化計(jì)算

1.2.2組合優(yōu)化問題

典型問題——任務(wù)分配問題（TAP）

優(yōu)化目標(biāo)2：最小化周轉(zhuǎn)時(shí)間（turnaroundtime)1.2最優(yōu)化問題及其分類一個(gè)分配方案的最終代價(jià)（finalcost）由具有最大Ctotal(A)值的處理機(jī),即由負(fù)載最重的處理機(jī)決定：此時(shí)，TAP的目標(biāo)是找到一種具有最小代價(jià)的分配方案，即負(fù)載盡量均衡：63

1.3啟發(fā)式算法（Heuristic）

智能優(yōu)化計(jì)算最優(yōu)算法一個(gè)問題的最優(yōu)算法求得該問題每個(gè)實(shí)例的最優(yōu)解；啟發(fā)式算法一個(gè)基于直觀或經(jīng)驗(yàn)構(gòu)造的算法，在可接受的花費(fèi)（計(jì)算時(shí)間、占用空間等）下給出待解決優(yōu)化問題每一個(gè)實(shí)例的一個(gè)可行解，該可行解與最優(yōu)解的偏離程度不一定事先可以預(yù)計(jì)。

1.3.1啟發(fā)式算法的定義

64

1.3啟發(fā)式算法

智能優(yōu)化計(jì)算啟發(fā)式算法的特點(diǎn)是一種技術(shù)；不能保證所得解的最優(yōu)性；啟發(fā)式算法的發(fā)展歷史

20世紀(jì)40年代——起步

20世紀(jì)60～70年代——被鄙視

20世紀(jì)70年代——觀點(diǎn)轉(zhuǎn)變

20世紀(jì)80年代至今——研究熱潮

1.3.1啟發(fā)式算法的定義

65

1.3啟發(fā)式算法

智能優(yōu)化計(jì)算例子——背包問題的貪婪算法（Greedyalgorithm）

貪婪算法：采用逐步構(gòu)造最優(yōu)解的方法。在每個(gè)階段，都作出一個(gè)看上去最優(yōu)的決策（在一定的標(biāo)準(zhǔn)下）。決策一旦作出，就不可再更改。作出貪婪決策的依據(jù)稱為貪婪準(zhǔn)則（greedycriterion）。

1.3.1啟發(fā)式算法的定義

66

1.3啟發(fā)式算法

智能優(yōu)化計(jì)算例子——背包問題的貪婪算法（Greedyalgorithm）STEP1STEP2

1.3.1啟發(fā)式算法的定義

67

1.3啟發(fā)式算法

智能優(yōu)化計(jì)算啟發(fā)式算法的優(yōu)點(diǎn)

1.模型誤差、數(shù)據(jù)不精確性、參數(shù)估計(jì)誤差等可能造成最優(yōu)算法的解比啟發(fā)式算法的解更差；

2.復(fù)雜問題無法求得最優(yōu)算法或最優(yōu)算法太復(fù)雜；

3.簡單易行，直觀，程序簡單。啟發(fā)式算法的缺點(diǎn)

1.不能保證最優(yōu)；

2.不穩(wěn)定；

3.依賴于實(shí)際問題、設(shè)計(jì)者經(jīng)驗(yàn)。

1.3.1啟發(fā)式算法的定義

68

1.3啟發(fā)式算法

智能優(yōu)化計(jì)算簡單直觀的算法

一步算法：不在兩個(gè)可行解之間比較，在未終止的迭代過程中，得到的中間解有可能不是可行解；例：背包問題的貪婪算法

改進(jìn)算法：迭代過程是從一個(gè)可行解到另一個(gè)可行解變換，通過兩個(gè)解的比較而選擇好的解，直到滿足一定的要求為止；例：TSP問題的2－opt方法

1.3.2啟發(fā)式算法的分類

P1P6P2P5P3P42203122224434369

1.3啟發(fā)式算法

智能優(yōu)化計(jì)算

數(shù)學(xué)規(guī)劃算法用連續(xù)優(yōu)化（如線性規(guī)劃）的方法求解組合優(yōu)化問題（如整數(shù)線性規(guī)劃模型），其中包括一些啟發(fā)式規(guī)則?；跀?shù)學(xué)規(guī)劃的理論。

1.3.2啟發(fā)式算法的分類

70

1.3啟發(fā)式算法

智能優(yōu)化計(jì)算現(xiàn)代優(yōu)化算法禁忌搜索算法模擬退火算法遺傳算法人工神經(jīng)網(wǎng)絡(luò)蟻群算法粒子群算法混合算法

1.3.2啟發(fā)式算法的分類

特點(diǎn)：基于客觀世界中的一些自然現(xiàn)象；建立在計(jì)算機(jī)迭代計(jì)算的基礎(chǔ)上；具有普適性，可解決實(shí)際應(yīng)用問題。71

1.3啟發(fā)式算法

智能優(yōu)化計(jì)算評(píng)價(jià)算法優(yōu)劣的指標(biāo)算法的復(fù)雜性（計(jì)算效率）解的偏離程度（計(jì)算效果）算法的穩(wěn)健性（不同實(shí)例、不同時(shí)間、不同起點(diǎn)的差異）評(píng)價(jià)算法優(yōu)劣的手段最壞情況分析（純理論）概率分析（理論分析）計(jì)算模擬分析（統(tǒng)計(jì)特性）

1.3.3啟發(fā)式算法的性能分析

72

1.4計(jì)算復(fù)雜性與NP完全問題

智能優(yōu)化計(jì)算時(shí)間復(fù)雜性和空間復(fù)雜性概念

算法的時(shí)間復(fù)雜性：算法對(duì)時(shí)間的需要量（加、減、乘、除、比較、讀、寫等操作的總次數(shù)）；

算法的空間復(fù)雜性：算法對(duì)空間的需要量（存儲(chǔ)空間的大小，二進(jìn)制位數(shù)）；

問題的時(shí)間復(fù)雜性：所有算法中時(shí)間復(fù)雜性最小的算法時(shí)間復(fù)雜性；

問題的空間復(fù)雜性：所有算法中空間復(fù)雜性最小的算法空間復(fù)雜性；

1.4.1計(jì)算復(fù)雜性的基本概念

73

1.4計(jì)算復(fù)雜性與NP完全問題

智能優(yōu)化計(jì)算復(fù)雜性問題分類

P類、NP類、NP完全類復(fù)雜性表示方法復(fù)雜性表示為問題規(guī)模n（如TSP的n）的函數(shù)，時(shí)間復(fù)雜性T(n)，關(guān)鍵操作的次數(shù)；空間復(fù)雜性S(n)，占用的存儲(chǔ)單元數(shù)量；

1.4.1計(jì)算復(fù)雜性的基本概念

74

1.4計(jì)算復(fù)雜性與NP完全問題

智能優(yōu)化計(jì)算復(fù)雜性表示方法若算法A的時(shí)間復(fù)雜性為TA(n)=O(p(n))，O(p(n))為復(fù)雜性函數(shù)p(n)主要項(xiàng)的階，且p(n)為n的多項(xiàng)式函數(shù)，則稱算法A為多項(xiàng)式(polynomial)算法。

當(dāng)不存在多項(xiàng)式函數(shù)p(n)時(shí)，稱相應(yīng)的算法為非多項(xiàng)式時(shí)間算法或指數(shù)時(shí)間算法；隨著變量的增加，多項(xiàng)式函數(shù)增長的速度比指數(shù)函數(shù)和非多項(xiàng)式函數(shù)增長的速度要慢得多。

1.4.1計(jì)算復(fù)雜性的基本概念

75

1.4計(jì)算復(fù)雜性與NP完全問題

智能優(yōu)化計(jì)算P類問題（deterministicpolynomial）

具有多項(xiàng)式時(shí)間求解算法的問題類迄今為止，許多組合優(yōu)化問題都沒有找到求最優(yōu)解的多項(xiàng)式時(shí)間算法。NP類問題(Nondeterministicpolynomial)

定義1實(shí)例是問題的特殊表現(xiàn)，所謂實(shí)例就是確定了描述問題特性的所有參數(shù)的問題，其中參數(shù)值稱為數(shù)據(jù)，這些數(shù)據(jù)占有計(jì)算機(jī)的空間稱為實(shí)例的輸入長度。

1.4.2P,NP,NP-C和NP-hard

76

1.4計(jì)算復(fù)雜性與NP完全問題

智能優(yōu)化計(jì)算NP類問題(Nondeterministicpolynomial)

定義2若一個(gè)問題的每個(gè)實(shí)例只有“是”或“否”兩種回答，則稱該問題為判定問題。例，TSP的判定問題：給定z，是否存在n個(gè)城市的一個(gè)排列W，使得f(W)≤z。滿足f(W)≤z的一個(gè)排列W稱為判定問題的“是”答案（可行解）。

1.4.2P,NP,NP-C和