智能計算導論

1

1.1引言

1.1.1優(yōu)化問題

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

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

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

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

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

1.3啟發(fā)式算法

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

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

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

1.4計算復雜性與NP完全問題

1.4.1計算復雜性的基本概念

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

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

1.1引言

智能優(yōu)化計算優(yōu)化技術？以數學為基礎，解決各種工程問題優(yōu)化解優(yōu)化技術的用途系統(tǒng)控制人工智能模式識別生產調度

……

1.1.1優(yōu)化問題

3

1.1引言

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

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

1.1.1優(yōu)化問題

4

1.1引言

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

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

理論上的準確與完美，主要方法：線性與非線性規(guī)劃、動態(tài)規(guī)劃、多目標規(guī)劃、整數規(guī)劃等；排隊論、庫存論、對策論、決策論等。

傳統(tǒng)的評價方法

算法收斂性、收斂速度

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

5

1.1引言

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

離散性、不確定性、大規(guī)模現代的優(yōu)化方法啟發(fā)式算法（heuristicalgorithm）追求滿意（近似解）實用性強（解決實際工程問題）現代的評價方法算法復雜性

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

6

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

難點高維多峰值

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

7

1.2.2常見求解方法

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

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

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

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

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

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

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

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

10

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Benchmark問題29

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Benchmark問題33

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

此函數在距全局最優(yōu)點大約3.14范圍內存在無窮多個局部極小將其包圍，并且函數強烈振蕩。

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

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

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

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

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

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

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

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

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

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

42

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

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

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

12341218103243TSP問題實例10城市TSP問題20城市TSP問題44TSP問題實例230城市TSP問題48城市TSP問題45

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

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

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

城市數2425262728293031計算時間1sec24sec10min4.3hour4.9day136.5day10.8year325year46

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

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

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

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

47

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

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

多目標優(yōu)化動態(tài)性狀態(tài)相依

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

48

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

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

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

背包問題的貪婪算法49

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

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

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

50

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

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

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

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

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

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

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

其中，p=1,2,…,k，np為第p類中的點數。

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

52

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

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

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

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

53

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

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

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

54

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

智能優(yōu)化計算

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

典型問題——任務分配問題（TAP）

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

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

智能優(yōu)化計算

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

典型問題——任務分配問題（TaskAssignmentProblemTAP）

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

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

智能優(yōu)化計算

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

典型問題——任務分配問題（TaskAssignmentProblemTAP）

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

57

智能優(yōu)化計算

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

典型問題——任務分配問題（TAP）

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

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

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

典型問題——任務分配問題（TAP）

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

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

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

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

智能優(yōu)化計算

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

典型問題——任務分配問題（TAP）

優(yōu)化目標2：最小化周轉時間（turnaroundtime)1.2最優(yōu)化問題及其分類分配到處理機k上的任務總的執(zhí)行代價：分配到處理機k上的任務與分配到其它處理機上的任務總的通信代價：61

智能優(yōu)化計算

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

典型問題——任務分配問題（TAP）

優(yōu)化目標2：最小化周轉時間（turnaroundtime)1.2最優(yōu)化問題及其分類對于某一給定的分配方案A，處理機k總的執(zhí)行代價：62

智能優(yōu)化計算

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

典型問題——任務分配問題（TAP）

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

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

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

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

64

1.3啟發(fā)式算法

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

20世紀40年代——起步

20世紀60～70年代——被鄙視

20世紀70年代——觀點轉變

20世紀80年代至今——研究熱潮

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

65

1.3啟發(fā)式算法

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

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

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

66

1.3啟發(fā)式算法

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

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

67

1.3啟發(fā)式算法

智能優(yōu)化計算啟發(fā)式算法的優(yōu)點

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

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

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

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

2.不穩(wěn)定；

3.依賴于實際問題、設計者經驗。

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

68

1.3啟發(fā)式算法

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

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

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

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

P1P6P2P5P3P42203122224434369

1.3啟發(fā)式算法

智能優(yōu)化計算

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

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

70

1.3啟發(fā)式算法

智能優(yōu)化計算現代優(yōu)化算法禁忌搜索算法模擬退火算法遺傳算法人工神經網絡蟻群算法粒子群算法混合算法

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

特點：基于客觀世界中的一些自然現象；建立在計算機迭代計算的基礎上；具有普適性，可解決實際應用問題。71

1.3啟發(fā)式算法

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

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

72

1.4計算復雜性與NP完全問題

智能優(yōu)化計算時間復雜性和空間復雜性概念

算法的時間復雜性：算法對時間的需要量（加、減、乘、除、比較、讀、寫等操作的總次數）；

算法的空間復雜性：算法對空間的需要量（存儲空間的大小，二進制位數）；

問題的時間復雜性：所有算法中時間復雜性最小的算法時間復雜性；

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

1.4.1計算復雜性的基本概念

73

1.4計算復雜性與NP完全問題

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

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

1.4.1計算復雜性的基本概念

74

1.4計算復雜性與NP完全問題

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

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

1.4.1計算復雜性的基本概念

75

1.4計算復雜性與NP完全問題

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

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

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

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

76

1.4計算復雜性與NP完全問題

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

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

1.4.2P,NP,NP-C和