【正文】 2 ???????? ???? ? ?? ?ji jijjiji xpxacXf),())(m i n ( * ??? fXf 最優(yōu)化問題及其分類 智能計算 測試函數(shù) 其中， 函數(shù)優(yōu)化問題 ???????????????????????????????,,)(),3,1()( ,35303530,10,10,10,10,3,3)(ijiijpca 最優(yōu)化問題及其分類 智能計算 測試函數(shù) （ 20） Hartman’ s Function 其最優(yōu)狀態(tài)和最優(yōu)值為 函數(shù)優(yōu)化問題 10 ,)(e xp)(41612 ???????? ???? ? ?? ?ji jijjiji xpxacXf)6 5 ,3 1 ,2 7 ,4 7 ,2 0 ())(m i n ( * ??? fXf 最優(yōu)化問題及其分類 智能計算 測試函數(shù) 其中， 函數(shù)優(yōu)化問題 ???????????????????????????????,,,,,)(),3,1()( ,148148,17,8,10,10,,17,17,8,10,3,17,3,10)(ijiijpca 最優(yōu)化問題及其分類 智能計算 測試函數(shù) （ 21） Shekel’ s Family m分別取 5， 7和 10，其最優(yōu)狀態(tài)和最優(yōu)值為 函數(shù)優(yōu)化問題 ? ? 100 ,))(()( 11?????????? xcaxaxXf miiTiimicafXf ii ???? 1,/1)())(m i n ( * 最優(yōu)化問題及其分類 智能計算 測試函數(shù) 其中， 函數(shù)優(yōu)化問題 i aij ci j=1 2 3 4 1 4 4 4 4 2 1 1 1 1 3 8 8 8 8 4 6 6 6 6 5 3 7 3 7 6 2 9 2 9 7 5 5 3 3 8 8 1 8 1 9 6 2 6 2 10 7 7 最優(yōu)化問題及其分類 智能計算 測試函數(shù) （ 22） J. D. Schaffer 其最優(yōu)狀態(tài)和最優(yōu)值為 函數(shù)優(yōu)化問題 100|| ,)]([ i n)( 2222122212???? ??? ixxx xxXf1)0,0())(m i n ( * ??? fXf 最優(yōu)化問題及其分類 智能計算 測試函數(shù) （ 22） J. D. Schaffer 此函數(shù)在距全局最優(yōu)點大約 窮多個局部極小將其包圍，并且函數(shù)強烈振蕩。 函數(shù)優(yōu)化問題 最優(yōu)化問題及其分類 智能計算 有約束的函數(shù)優(yōu)化 常用受約束測試函數(shù)； 影響因素： （ 1）曲面拓?fù)湫再|(zhì)，線性或凸函數(shù)比無規(guī)律的函數(shù)更容易求解； （ 2）可行區(qū)域的疏密程度，通常以可行區(qū)域占整個搜索空間的比值來度量； 函數(shù)優(yōu)化問題 最優(yōu)化問題及其分類 智能計算 有約束的函數(shù)優(yōu)化 常用受約束測試函數(shù)； 影響因素： （ 3）整體最優(yōu)解與可行區(qū)域最優(yōu)解之比； （ 4）在最優(yōu)解處活躍約束的數(shù)目，活躍約束數(shù)目越多則最優(yōu)解離可行區(qū)域的邊界越近。 組合優(yōu)化問題 背包問題的貪婪算法 最優(yōu)化問題及其分類 智能計算 典型問題 —— 裝箱問題（ Bin packing problem） 有 n個尺寸不超過 1的物品，有數(shù)個尺寸為 1的箱子，如何將這些物品裝入箱子，使得所需箱子的個數(shù)最少。 2 99。 83 46。 18 40。 4 50 啟發(fā)式算法 智能計算 最優(yōu)算法 一個問題的最優(yōu)算法求得該問題每個實例的 最優(yōu)解 ； 啟發(fā)式算法 一個基于直觀或經(jīng)驗構(gòu)造的算法，在可接受的花費（計算時間、占用空間等）下給出待解決優(yōu)化問題每一個實例的一個 可行解 ，該可行解與最優(yōu)解的偏離程度不一定事先可以預(yù)計。 啟發(fā)式算法的缺點 1. 不能保證最優(yōu)； 2. 不穩(wěn)定； 3. 依賴于實際問題、設(shè)計者經(jīng)驗。 P,NP,NPC和 NPhard 計算復(fù)雜性與 NP完全問題 智能計算 NP類問題 (Nondeterministic polynomial) 定義 2 若一個問題的每個實例只有 “ 是 ” 或 “ 否 ”兩種回答，則稱該問題為 判定問題 。稱判定問題 A為 NP－ hard，只要上述第二個條件成立。 計算復(fù)雜性與 NP完全問題 智能計算 P,NP,NPC和 NPhard 計算復(fù)雜性與 NP完全問題 智能計算 NP－ C （ NPComplete）和 NP－ hard類問題 Cook在 1971年給出并證明了有一類問題具有下述性質(zhì) （ 1）這類問題中任何一個問題至今未找出多項式時間算法；（ 2）如果這類問題中的一個問題存在有多項式時間算法，那么這類問題都有多項式時間的算法，這類問題中的每一個問題稱為 NP完全問題，這個問題的集合簡記 NPC。 計算復(fù)雜性的基本概念 計算復(fù)雜性與 NP完全問題 智能計算 P類問題（ deterministic polynomial ） 具有多項式時間求解算法的問題類 迄今為止，許多組合優(yōu)化問題都沒有找到求最優(yōu)解的多項式時間算法。1:},2,1{ ?knacii?記成排列從大到小排列，不妨把對物品以。 41 26。 74 78。 18 54。 25 62。 若各工件技術(shù)約束條件相同，轉(zhuǎn)化為 Flowshop。 傳統(tǒng)的評價方法 算法收斂性、收斂速度 傳統(tǒng)優(yōu)化方法 引言 智能計算 待解決的問題 離散性、不確定性、大規(guī)模 現(xiàn)代的優(yōu)化方法 啟發(fā)式算法（ heuristic algorithm） 追求滿意（近似解） 實用性強（解決實際工程問題） 現(xiàn)代的評價方法 算法復(fù)雜性 現(xiàn)代優(yōu)化方法