如何求解問題

如何求解問題第一頁，共一百二十一頁，編輯于2023年，星期二主要內(nèi)容：傳統(tǒng)方法：窮舉搜索、局部搜索、單純形法、貪婪算法、分而治之法、動態(tài)規(guī)劃法、分枝定界法、A*算法現(xiàn)代方法：模擬退火、禁忌搜索、演化算法、約束處理技術(shù)、神經(jīng)網(wǎng)絡(luò)、模糊系統(tǒng)第二頁，共一百二十一頁，編輯于2023年，星期二引言理性的人努力使自己適應(yīng)這個世界；瘋狂的人堅持使世界適應(yīng)自己；因此，一切進步取決于瘋狂的人們。------G.B.蕭伯納《革命家箴言》第三頁，共一百二十一頁，編輯于2023年，星期二這不是一次算法講座，但其中充滿算法，算法不是講座主題。講座不僅為你提供必要的知識，更重要的是幫你拓展才能去構(gòu)建新的問題和進行創(chuàng)造性的思維。有效的求解問題的重要性從來沒有現(xiàn)在這么強烈。不幸的是，我們的麻煩在生命的早期就已出現(xiàn)。甚至早到上小學(xué)時，我們被教導(dǎo)去分解問題，去孤立地解決更簡單、更小的問題，我們被填鴨式地灌輸著問題的求解方法，卻從未思考是否有其他辦法！大學(xué)課本亦然！第四頁，共一百二十一頁，編輯于2023年，星期二美國初三數(shù)學(xué)課本內(nèi)容一個農(nóng)夫有一個長方形的農(nóng)場，它的周長是110米，面積是700平方米，問農(nóng)場的邊長各式多少？學(xué)生們用本章學(xué)的方法建立方程2x+2y=110Xy=700根據(jù)剛學(xué)過的知識，很快算出x，解決問題第五頁，共一百二十一頁，編輯于2023年，星期二美國初三數(shù)學(xué)課本內(nèi)容另一章是關(guān)于幾何和討論三角形性質(zhì)的。末尾總結(jié)了一系列需要解決的問題。學(xué)生們毫不懷疑他應(yīng)用這些定理來解決這些問題。但是這看上去并不是正確的教育之道。問題和方法的關(guān)系應(yīng)該通過問題而不是對方法的討論而得到。從長遠看，這樣弊大于利，它使的學(xué)生不能獨立地思考問題！為了說明這一點，下面舉例說明。第六頁，共一百二十一頁，編輯于2023年，星期二證明：AD+DB<AC+CBCDAB第七頁，共一百二十一頁，編輯于2023年，星期二很明顯，三角形內(nèi)的線段之和必定小于三角形兩邊之和有資料為證，此問題給本科生、研究生，甚至數(shù)學(xué)、工程、計算機方面的教授，他們中不到5%的人能在1個小時內(nèi)解出這個問題，大部分人需要幾個小時，還有些人根本就解不出來！有趣的的是這個問題出自美國5年級課本！如果你不能在1小時之內(nèi)解決問題，那么此講座正是為你而做！第八頁，共一百二十一頁，編輯于2023年，星期二證明：AD+DB<AC+CBCDABE定理：三角形的任意兩邊之和必大于第三邊。第九頁，共一百二十一頁，編輯于2023年，星期二三個孩子的年齡有多大？數(shù)學(xué)家遇見多年未見的朋友。朋友說：我的三個孩子都是今天的生日，你能算出他們的年齡嗎？他們?nèi)齻€的年齡之積是36，年齡之和是那棟房子的窗戶數(shù)。數(shù)學(xué)家看過房子說：我還需要一點信息。朋友說：我大兒子的眼睛是藍色的。數(shù)學(xué)家說：OK。我算出來了。第十頁，共一百二十一頁，編輯于2023年，星期二三個孩子的年齡之積為36第一第二第三361118211231941922661632433第十一頁，共一百二十一頁，編輯于2023年，星期二年齡之和為房子的窗戶數(shù)36+1+1=3818+2+1=2112+3+1=169+4+1=149+2+2=136+6+1=136+3+2=114+3+3=10第十二頁，共一百二十一頁，編輯于2023年，星期二如此推理假如房子的窗戶數(shù)不是13，那么數(shù)學(xué)家就會立刻給出答案。但是，他說，還需要信息，因此只有兩種可能的情況：（9，2，2）或（6，6，1）父親說“大兒子眼睛是藍色的”，所以三個孩子的年齡一定是：（9，2，2）第十三頁，共一百二十一頁，編輯于2023年，星期二1為何有些問題難以求解？搜索空間中可能解的數(shù)目太多以至于無法采用窮舉搜索法去找到最優(yōu)解問題是如此復(fù)雜以至于為了得到答案，我們不得不采用問題的簡化模型，而實際上所得的結(jié)果是無用的描述可能解質(zhì)量的評估函數(shù)或者有噪聲或者隨時間而變化，因此需要的不僅僅是一個解而是一系列解的解集可能解都被嚴格約束以至于構(gòu)造哪怕一個可行解都是困難的，更不用說找最優(yōu)解了求解問題的人沒有作好充分準備或存在某種心里障礙使得他們難以找到答案第十四頁，共一百二十一頁，編輯于2023年，星期二幾個典型問題及其搜索空間問題一：SAT問題邏輯學(xué)的一個基本問題是布爾可滿足性問題（BooleanSatisfiabilityProblem，簡稱SAT），也就是使得包含一些布爾變量的復(fù)合語句取值為真。考慮以下包含100個布爾變量的范式：問題是要找出每個變量的真值指派，使得。第十五頁，共一百二十一頁，編輯于2023年，星期二可能解的空間有多大？解空間S的大小是：非常大！！此外，選取那種評估函數(shù)也不很清楚。我們希望評估函數(shù)有助于我們評價可能解的質(zhì)量，越接近準確答案的值應(yīng)該產(chǎn)生出越好的評估值。如果采用枚舉搜索法，我們就不會在乎這些，只要一個一個地找，直到找到為止。但是如果想用評估函數(shù)指引我們比枚舉法更快地找到最優(yōu)解的話，那就不僅僅是要知道“正確”與“錯誤”了。這就使得用于解SAT問題的方法立刻顯得復(fù)雜起來。第十六頁，共一百二十一頁，編輯于2023年，星期二問題二：TSP問題

有些問題看起來比SAT問題更簡單，因為它們提供了自然的評估函數(shù)，甚至解空間的大小也是可數(shù)的。例如，考慮旅行商問題（TravelingSalesmanProblem，簡稱TSP）。這個問題非常簡單：旅行商必須以最短路徑訪問所有的城市一次且僅一次并回到出發(fā)地。第十七頁，共一百二十一頁，編輯于2023年，星期二圖1.1給出了一個簡單的對稱的20城市的TSP，圖中每對城市i到j(luò)的距離等于j到i的距離。即：dist（i，j）=dist（j，i）第十八頁，共一百二十一頁，編輯于2023年，星期二TSP的搜索空間是什么？

可以看作是n個城市的排列的集合。n個城市的任意排列產(chǎn)生一個有序表，它決定了所訪問的城市的順序，從商人的家所在城市開始，然后經(jīng)過所有城市直至回家。最優(yōu)解就是產(chǎn)生最小費用的那個排列。注意，以下路徑是相同的：

2-…-6-15-3-11-19-1715-3-11-19-17-2-…-6

3-11-19-17-2-…-6-15第十九頁，共一百二十一頁，編輯于2023年，星期二搜索空間與評估函數(shù)搜索空間的大?。簄！/（2n）TSP的解空間大到令人無法置信！評估函數(shù)的選擇對于路徑：15-3-11-19-17-2-…-6Cost=dist(15,3)+dist(3,11)+…+dist(6,15)第二十頁，共一百二十一頁，編輯于2023年，星期二問題三：NLP問題現(xiàn)在來看第三個例子：一個特定的非線性規(guī)劃問題（NonlinearProgammingProblem,簡稱NLP）這是一個在科學(xué)文獻中研究過的難題。迄今為止，還沒有哪種傳統(tǒng)的優(yōu)化算法能給出一個令人滿意的結(jié)果。事實上它是非線性規(guī)劃問題11個測試函數(shù)中的第二個。第二十一頁，共一百二十一頁，編輯于2023年，星期二問題是求函數(shù)：的最大值，使?jié)M足條件其中第二十二頁，共一百二十一頁，編輯于2023年，星期二第二十三頁，共一百二十一頁，編輯于2023年，星期二解空間是多大？函數(shù)G2是非線性的，它的全局最大值未知，但存在于原點附近。它的解空間是多少呢？如果精確到小數(shù)點后第6位，那么每個變量就有10000000=107個取值，因此搜索空間的大小是：107n

這個值要遠遠大于相應(yīng)的TSP的解的數(shù)目。即使n=50時，NLP的可能解在取6位小數(shù)的精度時，達到10350個！第二十四頁，共一百二十一頁，編輯于2023年，星期二評估函數(shù)如何？怎樣評價不同解的質(zhì)量？有一種方法是將G2本身作為評估函數(shù)，使函數(shù)G2取值更大的解被認為優(yōu)于使其值更小的解。問題是，如圖所示，圖中有不可行區(qū)域，并且所有不可行點被置為0。可行區(qū)域和不可行區(qū)域的邊界由等式來限定，并且最優(yōu)解靠近這個邊界。即使沒有這個額外的難題，僅僅憑其可供選擇的解的數(shù)目之巨大就足以看出這些看似簡單的問題所面臨的巨大挑戰(zhàn)，由此可見，評估這些解的方法并不總是顯而易見的。第二十五頁，共一百二十一頁，編輯于2023年，星期二2幾個基本概念求解問題的所有算法有三個基本概念是相同的，不管采用什么技術(shù)，都必須確定：（1）表示方式—對可選擇的候選解進行編碼（2）目標—描述了要達到的目的（3）評估函數(shù)—給出了給定表示方式下的任意特定解的質(zhì)量第二十六頁，共一百二十一頁，編輯于2023年，星期二這是一個極好的例子給你6根火柴棒，你的任務(wù)是以他們?yōu)檫叴罱ㄆ?個等邊三角形。很容易用5根建立起兩個這樣的三角形，卻很難將它擴展到4個三角形，特別是只剩下1根火柴棍。第二十七頁，共一百二十一頁，編輯于2023年，星期二從一個錯誤的搜索空間開始，你將永遠不可能找到正確答案四個等邊三角形，6根火柴第二十八頁，共一百二十一頁，編輯于2023年，星期二定義一個搜索問題現(xiàn)在定義一個搜索問題。給定搜索空間S和它的可行部分FS，要求找到某一xF，使對所有的yF，有Eval（x）Eval（y）（極小化問題）滿足上述條件的點x叫做全局解。找到問題的這樣一個全局解是很困難的！第二十九頁，共一百二十一頁，編輯于2023年，星期二鄰域和局部最優(yōu)解S—搜索空間xN（x）如果對于所有的yN（x），都滿足Eval（x）Eval（y），那么x就是局部最優(yōu)解。X的鄰域第三十頁，共一百二十一頁，編輯于2023年，星期二爬山法

（hill-climbingmethod）就像所有的局部搜索算法一樣，都是運用迭代改進的技術(shù)。每次迭代從當前點的鄰域中選取一個新點，若新點的評估值優(yōu)于當前點，它就變成當前點；否則就選取當前點鄰域中的其他點來比較。很明顯，這種爬山法只能提供局部最優(yōu)解。第三十一頁，共一百二十一頁，編輯于2023年，星期二簡單迭代爬山法的思想現(xiàn)在有很多種爬山算法，主要是在新解與當前解進行比較的方式上有所不同。開始時，當前解的所有可能鄰域都被考慮，并且將具有最好評估值eval（vn）的點vn與當前點vc做比較。若eval（vc）比eval（vn）差，則新點vn就成為當前點；否則，則沒有可能再進行局部改造：該算法已經(jīng)達到局部最優(yōu)或全局最優(yōu)（變量local=TRUE）在這種情況下，算法的下一次迭代（t=t+1）隨機選取一個新的當前點來執(zhí)行。第三十二頁，共一百二十一頁，編輯于2023年，星期二Procedure迭代爬山法Begint=0

初始化bestrepeatlocal=FALSE

隨機選取一個當前點VC

評估VC

repeat

在VC的鄰域中選擇所有新點從這個新點的集合中找使評估函數(shù)eval的值最優(yōu)的點Vnifeval（Vn）好于eval（Vc）

thenVc=Vn

elselocal=TRUEuntillocalt=t+1ifVc好于bestthenbest=Vcuntilt=MAXend簡單迭代爬山法第三十三頁，共一百二十一頁，編輯于2023年，星期二3傳統(tǒng)方法—第一部分窮舉搜索局部搜索單純形法第三十四頁，共一百二十一頁，編輯于2023年，星期二窮舉搜索

（exhaustivesearch）檢查搜索空間中的每一個解直到找到最好的全局解。如果要解決的是一個小問題，并且有時間去枚舉出整個搜索空間時，保證你能用窮舉法找到最優(yōu)解。如果面臨一個較大的問題，不要用此法，因為你永遠也無法列舉完所有情況。第三十五頁，共一百二十一頁，編輯于2023年，星期二局部搜索1、從搜索空間中找到一個解并進行評估其質(zhì)量，將它定義為當前解。2、變換當前解為一個新解并評估它的值。3、如果此解比當前解更好，則將當前解用新解替換，否則拋棄新解。4、重復(fù)2、3直至在給定集中找不到改進解。此類算法的關(guān)鍵：變換類型。第三十六頁，共一百二十一頁，編輯于2023年，星期二線性規(guī)劃單純形法--1947年，美國空軍服役轉(zhuǎn)任斯坦福大學(xué)的科學(xué)家丹茨格教授。橢球法—1979年蘇聯(lián)名不見經(jīng)傳的數(shù)學(xué)家哈奇揚。內(nèi)點法--1984年，美國貝爾實驗室年輕的印度裔數(shù)學(xué)家卡馬卡。第三十七頁，共一百二十一頁，編輯于2023年，星期二運籌學(xué)的主要分支：一、

線性規(guī)劃

二、

非線性規(guī)劃

三、

動態(tài)規(guī)劃

四、

圖與網(wǎng)絡(luò)分析

五、

存儲論

六、

排隊論

七、

對策論

八、

決策論

第三十八頁，共一百二十一頁，編輯于2023年，星期二4傳統(tǒng)方法—第二部分貪婪算法分而治之法動態(tài)規(guī)劃法分枝定界法A*算法第三十九頁，共一百二十一頁，編輯于2023年，星期二貪婪算法(greedyalgorithm)貪婪算法通過一系列步驟構(gòu)造完整解來解決問題。這個算法流行的原因很明顯：簡單！貪婪法的基本思想出奇的簡單：一個一個地為所有的決策變量賦值，在每一步作出最佳的決定。當然，這個過程假定了一種決策的啟發(fā)式思想，即在每一步作最好的移動，以獲得最大的“好處”，這就是“貪婪”這個名字的來由。但是這種方法也是目光短淺的，因為每一步作出最佳決定并不一定最終能得到全局最優(yōu)解。第四十頁，共一百二十一頁，編輯于2023年，星期二貪婪算法和SAT問題對從1到n的每個變量，不分次序，指定一個真值，使其盡可能地滿足最大數(shù)目的當前未滿足子局。如果不分勝負，則隨機選擇一個最好賦值。將所有變量按照它們在子局中出現(xiàn)的頻率，從大到小進行排序。依照上面次序，對每個變量進行賦值，使?jié)M足最大數(shù)目的當前未滿足子局。如果不分勝負，則隨機選擇一個。根本找不到一個解決SAT問題的貪婪算法！第四十一頁，共一百二十一頁，編輯于2023年，星期二方法1方法2方法3…對于每一種你能想象的常識性啟發(fā)式規(guī)則，都能找出一個特例使得這種規(guī)則看上去非常愚蠢！貪婪算法和TSP問題第四十二頁，共一百二十一頁，編輯于2023年，星期二對于NLP問題確實沒有有效的貪婪算法，但可以設(shè)計一些具有貪婪特征的算法。例如，優(yōu)化包含兩個變量的函數(shù)，可以設(shè)定其中一個變量x1保持不變，讓另一個變量x2變化，直到找到一個“最優(yōu)解”；然后讓x2保持不變，讓x1變化，直到找到一個新的“最優(yōu)解”。這種線性搜索的方法可以擴展到n維。貪婪算法和NLP問題第四十三頁，共一百二十一頁，編輯于2023年，星期二然而，如果x1和x2相關(guān)，也就是說出現(xiàn)x1和x2的乘積項，這個過程就很差。除非用戶建立的“評估”函數(shù)使得相關(guān)性不明顯，否則最好不要使用這個方法。嚴格的說，線性搜索并不是真正的貪婪算法，因為它只計算完整解。然而它在某一時刻對于單維情況，總是試圖選擇最好的可能機會，這確實符合貪婪算法的基本思想。第四十四頁，共一百二十一頁，編輯于2023年，星期二

貪婪算法無論是應(yīng)用在SAT、TSP、NLP，還是其他領(lǐng)域上，從概念上說都是很簡單的，但是通常它們?yōu)檫@種簡單性付出的代價是：無法解決包含多個相關(guān)參數(shù)的復(fù)雜問題，而現(xiàn)實問題往往如此！貪婪算法小結(jié)第四十五頁，共一百二十一頁，編輯于2023年，星期二分而治之法有時候把一個看似復(fù)雜的問題分解成若干個較小的問題來求解是一個很好的辦法。你可以逐個地求解這些較簡單的問題，然后找一種方法將各部分的解組合成一個完整的答案，這就是分而治之法（divideandconquer,簡稱D&C）。注意當子問題的解組合成一個完整解時，要確保這個解就是你要尋找的答案！第四十六頁，共一百二十一頁，編輯于2023年，星期二分而治之法的大致框架ProcedureD&C(P)Begin將問題Ｐ分解成子問題Ｐ１，…Ｐｋｆｏｒｉ＝１ｔｏｋｄｏｉｆｓｉｚｅ（Ｐｉ）＜ρｔｈｅｎ求解Ｐｉ（得到ｓｉ）ｅｌｓｅｓｉ

←Ｄ＆Ｃ（Ｐｉ）將組合到最終解中Ｅｎｄ圖４.２求解問題Ｐ的分而治之之遞歸過程第四十七頁，共一百二十一頁，編輯于2023年，星期二有一個２ｍ維的棋盤，上面有一個小洞，現(xiàn)在的任務(wù)是用一些“Ｌ”形的積木來覆蓋整個棋盤第四十八頁，共一百二十一頁，編輯于2023年，星期二第四十九頁，共一百二十一頁，編輯于2023年，星期二第五十頁，共一百二十一頁，編輯于2023年，星期二動態(tài)規(guī)劃法動態(tài)規(guī)劃法(dynamicprogramming)的原理是：在求解問題的過程中，通過處理位于當前位置和所達目標之間的中間點來找到整個問題的解。整個過程是遞歸的，每下一個中間點都是已訪問過的點的一個函數(shù)。適合于解決那些“次數(shù)很重要和操作的順序很關(guān)鍵”的問題的一類方法。第五十一頁，共一百二十一頁，編輯于2023年，星期二適合于動態(tài)規(guī)劃法的標準問題必須具有下列特點整個問題的求解可以劃分成若干階段的一系列決策過程每個階段有若干可能狀態(tài)一個決策將你從一個階段的一種狀態(tài)帶到下一個階段的某種狀態(tài)在任一個階段，最佳的決策序列（策略）和該階段以前的決策無關(guān)各階段狀態(tài)之間的轉(zhuǎn)換有明確定義的費用，而且在選擇最佳決策時有遞歸關(guān)系第五十二頁，共一百二十一頁，編輯于2023年，星期二

應(yīng)用這個方法時首先從目標開始，反向地工作直到當前狀態(tài)。也就是說首先確定最后一個階段的最佳決策，然后在此基礎(chǔ)上確定倒數(shù)第二個階段的最佳決策，依次繼續(xù)下去。第五十三頁，共一百二十一頁，編輯于2023年，星期二用動態(tài)規(guī)劃法解最短路問題1234105678974641535214324633334第五十四頁，共一百二十一頁，編輯于2023年，星期二最優(yōu)策略：1-3-5-8-10或1-4-5-8-10

或1-4-6-9-10。123410567897464153521432463333434476117811第五十五頁，共一百二十一頁，編輯于2023年，星期二它是一種啟發(fā)式算法其思想就是去掉那些明明知道不可能在其中找到最優(yōu)解的搜索空間。它是建立在對搜索空間連續(xù)劃分的思想上的。首先必須要知道任意特定解的代價的上界（或者下界，這要看是求最大值還是最小值）。分枝定界法

（branchandbound）第五十六頁，共一百二十一頁，編輯于2023年，星期二如果已經(jīng)有一個解，其代價是c個單位，并且知道下一個要嘗試的解的代價有一個下界，比c要大，并且我們是求極小值，那么根本不必去計算這個將嘗試的解有多糟糕，而只需忽略它，去嘗試另一個可能解。我們可以將整個搜索空間想象成樹狀結(jié)構(gòu)，分枝定界的啟發(fā)式思想是剪去那些我們不感興趣的分枝。分枝定界法的基本思想第五十七頁，共一百二十一頁，編輯于2023年，星期二分枝定界法算法Procedure分枝定界Begin初始化CD初始化fboundwhile(不滿足終止條件)do移去最好的盒子C→Di縮減或子劃分Di→D’i修改fboundC←C∪

D’ifor所有的Di

∈Cdoif(f(Di)的下界)>fboundthen從C中移去DiEnd第五十八頁，共一百二十一頁，編輯于2023年，星期二A*算法在任何給定時刻都采用最好的移動卻可能會帶來麻煩。比如貪婪法的執(zhí)行結(jié)果并不總是很好，其問題就在于現(xiàn)在是較好的，卻不一定是后面所需要的。假若我們有一個評估函數(shù)，它能提供足夠的信息來避免這些陷阱，那我們就可以使用這種貪婪法以獲得更好的性能。這個簡單的思想帶來了一個叫做“最佳優(yōu)先”搜索（best-firstsearch）的概念及其擴展形式---A*算法。第五十九頁，共一百二十一頁，編輯于2023年，星期二A*算法與深度優(yōu)先搜索、廣度優(yōu)先搜索的主要區(qū)別最佳優(yōu)先搜索探索的是下一個最有希望的結(jié)點，而深度優(yōu)先搜索是以一種任意的模式往盡可能深的地方搜索，而廣度優(yōu)先搜索則搜索完一層中所有的結(jié)點后才進入下一層最佳優(yōu)先搜索使用的是啟發(fā)式規(guī)則，給每個結(jié)點提供一個性能值，深度優(yōu)先搜索和廣度優(yōu)先搜索則不這樣做第六十頁，共一百二十一頁，編輯于2023年，星期二旅行者過橋問題四個旅行者ABCD夜晚要過一座橋，他們只有一盞老式油燈用作照明，每次最多允許過兩人，每人過橋時間不同。A—1min，B—2min，C—5min，D—10min兩人一起過橋，時間由慢者決定。如何安排最好的組合，使他們花最短的時間過去？第六十一頁，共一百二十一頁，編輯于2023年，星期二給出一個局部最優(yōu)解A提著油燈護送每人過橋。A和B一起過橋，2minA自己回來，1minA和C一起過橋，5minA自己回來，1minA和D一起過橋，10min總共19min事實上還有更好的答案，你能找到嗎？第六十二頁，共一百二十一頁，編輯于2023年，星期二5跳離局部最優(yōu)前面討論的傳統(tǒng)的求解問題的策略，它們中有些能保證找到全局解，有些則不能，但它們都遵循一個共同的模式。那就是，它們或者能夠保證找到全局解但在求解一些典型的實際問題時代價太大（太耗時），或者容易“陷入”局部最優(yōu)。由于很難加速一個能保證找到最優(yōu)解的算法，即對于大多數(shù)實際問題很難找到多項式時間算法（因為它們大多是NP難問題），那么剩下的選擇就是設(shè)計出能夠跳離局部最優(yōu)的算法。第六十三頁，共一百二十一頁，編輯于2023年，星期二“噢！一匹插上翅膀的駿馬！”爬山法：當?shù)竭_一個局部最優(yōu)解后便產(chǎn)生一個新的起始點，搜索重新開始。下面兩種方法分別基于：1、一個附加參數(shù)（溫度），用于改變從搜索空間的一個點移動到另一個點的概率---模擬退火（SimulatedAnnealing，SA）。2、一個記憶裝置，用于驅(qū)使算法探索搜索空間的新區(qū)域---禁忌搜索（tabusearch）。第六十四頁，共一百二十一頁，編輯于2023年，星期二簡單爬山法—MAX=1Procedure局部搜索Beginx=S中的某個初始點

While（improve（x）“no”）dox=improve（x）返回xend注：子程序improve（x）從x的鄰域返回一個新點y。若y比x好，那么子程序返回這個點的值，否則，返回“no”第六十五頁，共一百二十一頁，編輯于2023年，星期二簡化的模擬退火算法Procedure模擬退火B(yǎng)eginx=S中的某個初始點

While（不滿足終止條件）dox=improve？（x，T）修改T

返回xend第六十六頁，共一百二十一頁，編輯于2023年，星期二模擬退火與局部搜索的區(qū)別過程的終止條件—模擬退火執(zhí)行到滿足某個外部的終止條件時停止，而局部搜索則要求找到一個改進解。模擬退火中并不要求函數(shù)improve？（x，T）一定返回x鄰域的一個更好點，而是返回一個可以接受解y，這依賴于當前溫度T。模擬退火中參數(shù)T被定期修改，其值直接影響improve？的輸出，局部搜索沒有此特征。第六十七頁，共一百二十一頁，編輯于2023年，星期二禁忌搜索算法Procedure禁忌搜索Beginx=S中的某個初始點

While（不滿足終止條件）dox=improve？（x，H）修改H

返回xend在算法的結(jié)構(gòu)上與模擬退火相同，函數(shù)也是返回一個可接受解y，它不一定比x更好，但其接受與否是基于搜索的歷史H。第六十八頁，共一百二十一頁，編輯于2023年，星期二你的直覺如何？對一個復(fù)雜的問題試著先猜測一個解，這是人的天性。一些猜測看起來也很直觀，并且有些人也似乎更具直覺。你駕車以40km/h的從北京到上海，然后立即返回，車速為60km/h。試問整個旅程的平均速率是多少？第六十九頁，共一百二十一頁，編輯于2023年，星期二華爾街股市著名的詭計一個狡詐的股票經(jīng)紀人挑選出1024個人作為可能的客戶（受騙者）。每天，給他們郵寄一份有關(guān)股市在第二天漲或跌的預(yù)測，一直持續(xù)10天。到第10天末，一個不幸的受害者會驚異地發(fā)現(xiàn)股票經(jīng)紀人所預(yù)測的股市走勢百發(fā)百中，10次都準確，那么從直覺他感到此人就是“神仙”！問題出在哪兒呢？第七十頁，共一百二十一頁，編輯于2023年，星期二6演化算法前面的算法都是以單個解作為每次迭代中進行下次搜索的基礎(chǔ)。貪婪算法是通過每次獲得局部最大改進來逐步建立解；動態(tài)規(guī)劃在得到最終的完整解之前先求解許多小的子問題；分支定界則將搜索空間組織成一些子空間，然后剔除其中的一些子空間。相反，局部搜索、模擬退火和禁忌搜索則處理完整解。每次迭代都會獲得一個局部最優(yōu)解，下次迭代繼續(xù)改進。不管區(qū)別如何，共同點就是一次只處理或構(gòu)造一個解。第七十一頁，共一百二十一頁，編輯于2023年，星期二目前的規(guī)則確定性規(guī)則：爬山法，如果被檢查的鄰域解更好，則移動到這個鄰域解并從這里開始搜索；否則繼續(xù)在當前鄰域內(nèi)搜索；概率性規(guī)則：模擬退火，如果被檢查的鄰域解更好，則接受這個解作為新的當前解；否則或者以一定的概率接受這個較差解或繼續(xù)在當前鄰域內(nèi)搜索；到目前為止搜索的歷史：禁忌搜索，接受可得到的最好鄰域解，它并不一定要比當前解更好，但是一定不能是列于存儲器中的一個受限制的或“禁忌”的移動。第七十二頁，共一百二十一頁，編輯于2023年，星期二基于“種群”的算法兔子與狐貍在兔子種群里，有些機靈，被吃的可能性較小，因此更容易幸存并繁衍。在繁殖中會保留這些特點。每只幼兔不是雙親的復(fù)制體，而是雙親的隨機擾動。經(jīng)過多代之后的兔子就會表現(xiàn)出一些有利于它們同狐貍甚至其他兔子競爭的特性。同時，狐貍也在進化！第七十三頁，共一百二十一頁，編輯于2023年，星期二演化算法的過程創(chuàng)建一個個體種群，表示所解決問題的潛在解集；評估個體；引入某種選擇壓力，保留較好個體，淘汰較差個體；應(yīng)用變化算子產(chǎn)生待測試的新個體。重復(fù)執(zhí)行“評估-選擇-變化”的循環(huán)若干次。第七十四頁，共一百二十一頁，編輯于2023年，星期二演化算法的優(yōu)點大多數(shù)經(jīng)典優(yōu)化算法采用的是固定的評估函數(shù)，對它的任何修改都要重新啟動算法。演化算法則是內(nèi)在適應(yīng)的，種群中的個體與當前環(huán)境相適應(yīng)。易于與其他算法相結(jié)合。并行性一次求解可以返回多個解，供選擇。程序設(shè)計心理學(xué)，你是創(chuàng)造者！第七十五頁，共一百二十一頁，編輯于2023年，星期二這些東西有一個與眾不同有12枚硬幣，其中1枚是假幣。假幣的重量與真幣不同，但不知是重還是輕。給你一架天平。用最少的次數(shù)，找出這枚假幣，并說明它是重還是輕。第七十六頁，共一百二十一頁，編輯于2023年，星期二演化算法設(shè)計思想演化求解問題的基本思想相當簡單：由所解決任務(wù)的候選解組成一個種群，然后通過隨機變化和選擇等一代代演化下去。其中隨機變化提供了發(fā)現(xiàn)新解的機制，選擇則確定保持哪些解作為下一步搜索的基礎(chǔ)。本質(zhì)上而言，任何在可能解的狀態(tài)空間內(nèi)對點不進行重取樣的搜索過程，對于所有問題的平均執(zhí)行效果相同。一個從不進行重取樣的爬山算法在試圖尋找函數(shù)最大值時，平均效果等同于一個沒有重復(fù)取樣的盲目隨機搜索。第七十七頁，共一百二十一頁，編輯于2023年，星期二演化算法描述大多數(shù)演化算法的方程描述：x[t+1]=s(v(x[t])),其中x[t]是以x為表示方式t時刻的種群，

v(.)是變化算子，s(.)是選擇算子。這個差分方程表示每一代的隨機演化過程。過程：產(chǎn)生一個與相關(guān)問題的潛在解的種群，設(shè)計一些從舊解產(chǎn)生新解的變化算子，并應(yīng)用選擇機制保留那些最好解到當前代。第七十八頁，共一百二十一頁，編輯于2023年，星期二最短路徑是什么？四個城市分別位于正方形的四個頂點，現(xiàn)在的任務(wù)是設(shè)計一個道路網(wǎng)絡(luò)，使得每個城市都與其他城市相連接且道路的總長最短。四個城市位置第七十九頁，共一百二十一頁，編輯于2023年，星期二可能的方案……第八十頁，共一百二十一頁，編輯于2023年，星期二這個答案是最優(yōu)的！第八十一頁，共一百二十一頁，編輯于2023年，星期二8旅行商問題TSP將局部最優(yōu)算法與演化算法結(jié)合—混合算法基于Karp-Steele算法中的分而治之技術(shù)—擴展的演化算法邊組裝雜交算法反序-雜交算法、旅行商問題是一個足以說明一個看似簡單的問題如何面臨許多意想不到的挑戰(zhàn)的典型例子！例如哥德巴赫猜想。第八十二頁，共一百二十一頁，編輯于2023年，星期二斑馬問題—著名的約束滿足問題五個顏色各異的房子里，住著不同國籍的人，他們飼養(yǎng)的寵物、喜歡喝的飲料以及擁有的汽車也各不相同，加上下面的信息：1、英國人住在紅房子里2、西班牙人養(yǎng)狗3、居住在綠房子里的人喝可樂4、烏克蘭人喝蛋酒5、綠房子是象牙色房子的右鄰第八十三頁，共一百二十一頁，編輯于2023年，星期二6、擁有老爺車的人養(yǎng)蝸牛7、擁有福特車的人住在黃房子里8、住在中間房子里的人喝牛奶9、挪威人住在最左邊的房子里10、擁有雪佛萊的人與養(yǎng)狐貍的人是鄰居11、擁有福特車的人與養(yǎng)馬的人是鄰居12、擁有奔馳汽車的人愛喝桔汁13、日本人開大眾汽車14、挪威人的鄰居住在藍房子里第八十四頁，共一百二十一頁，編輯于2023年，星期二形式化的表示方法Ai—i號房子的顏色Bi—住i號房子的人喝的飲料Ci—住i號房子的人的國籍Di—住i號房子的人擁有的汽車Ei—住i號房子的人飼養(yǎng)的寵物第八十五頁，共一百二十一頁，編輯于2023年，星期二變量的取值范圍第八十六頁，共一百二十一頁，編輯于2023年，星期二根據(jù)條件可以得出Ifci=Sthenei=D(i=2,3,4,5)第八十七頁，共一百二十一頁，編輯于2023年，星期二最后的答案第八十八頁，共一百二十一頁，編輯于2023年，星期二為什么要練習(xí)這類問題？練習(xí)解決這種約束滿足問題的好處是訓(xùn)練你的邏輯思維，考慮什么是可能的什么是不可能的。這些問題也出現(xiàn)在研究生入學(xué)考試中，因此記住一句老生的忠告：提前做好準備吧！如果你已經(jīng)完成了學(xué)業(yè)，那么就該慶幸這一切終于過去了！第八十九頁，共一百二十一頁，編輯于2023年，星期二9約束處理技術(shù)現(xiàn)實世界的每個問題都包含約束，你根本無法擺脫這些約束。只有教科書中才可能遇到無約束問題。事實上所有的決策問題都包含約束。正是這些約束的形式使各種類型的問題相互不同。根據(jù)問題的表示形式，約束可以表示為規(guī)則、數(shù)據(jù)依賴、代數(shù)式或其他形式。第九十頁，共一百二十一頁，編輯于2023年，星期二蝸牛爬桿一只蝸牛順著一根10米高的旗桿往上爬，白天向上爬5米，晚上睡覺下滑4米，問需要多少天蝸牛才能爬到旗桿的頂端？第九十一頁，共一百二十一頁，編輯于2023年，星期二利用空間來描述約束第九十二頁，共一百二十一頁，編輯于2023年，星期二處理約束的最常用的方法懲罰函數(shù)法第九十三頁，共一百二十一頁，編輯于2023年，星期二10針對問題調(diào)整算法渴望一夜暴富的人，一年之內(nèi)將被繩之以法-----L.達芬奇《雜記》幾乎每個實用的啟發(fā)式搜索算法都由某個參數(shù)集控制，但是這些方法中沒有哪一個能將一切都封裝到一個禮品盒中，讓你一打開盒子就可以獲得一份驚喜！在缺少理論指導(dǎo)的情況下，最好能找到一種自動優(yōu)化參數(shù)的方法，使得在這些參數(shù)的控制下，演化算法能找到更好的解。第九十四頁，共一百二十一頁，編輯于2023年，星期二本章小結(jié)一個演化算法的有效性依賴于它的各個組成部分（表示方式、變化算子等）及其相互作用。影響演化算法的最優(yōu)化參數(shù)設(shè)置的主要障礙之一是這些參數(shù)之間的非線性相互作用。依賴人的智能和專業(yè)技術(shù)是設(shè)計演化算法（包括參數(shù)設(shè)計）的最好辦法。第九十五頁，共一百二十一頁，編輯于2023年，星期二11隨時間變化的環(huán)境與噪聲一個二次碗，每個抽樣點加入高斯噪聲第九十六頁，共一百二十一頁，編輯于2023年，星期二現(xiàn)實世界永遠是變化的在實際問題的求解中，只找到一個解并固守這個解是遠遠不夠的，你必須隨著問題的改變不斷地尋找新的解。當求解的目標改變時，解也必須隨之改變。即使目標隨著時間的推移本質(zhì)上保持不變，然而在競爭的環(huán)境中，與競爭對手的目標的交互方式也會發(fā)生改變。這就要求根據(jù)面對的問題重新考慮解。第九十七頁，共一百二十一頁，編輯于2023年，星期二著名的囚犯兩難問題兩個犯人被關(guān)在不同房間，檢察官分別說：若你們都認罪，判4年；假如你認罪，但他不認罪。你釋放，他判5年；你們倆都不認罪，分別2年。第九十八頁，共一百二十一頁，編輯于2023年，星期二數(shù)學(xué)模型認罪保持沉默認罪保持沉默（4，4）（0，5）（5，0）（2，2）加入OPEC的國家就像在玩囚犯兩難游戲第九十九頁，共一百二十一頁，編輯于2023年，星期二12神經(jīng)網(wǎng)絡(luò)第一百頁，共一百二十一頁，編輯于2023年，星期二13模糊系統(tǒng)1965年Zadeh提出模糊集理論他描述“年老”的模糊集隸屬函數(shù)：這不是唯一的隸屬函數(shù)第一百零一頁，共一百二十一頁，編輯于2023年，星期二Zadeh“年老”模糊隸屬函數(shù)第一百零二頁，共一百二十一頁，編輯于2023年，星期二模糊系統(tǒng)的概念與應(yīng)用模糊集與概率測度隸屬度與隸屬函數(shù)模糊集運算與模糊關(guān)系模糊控制器模糊聚類模糊神經(jīng)網(wǎng)絡(luò)模糊TSP演化模糊系統(tǒng)第一百零三頁，共一百二十一頁，編輯于2023年，星期二你喜歡簡單的解決辦法嗎？兩個杯子分別盛水和果汁，體積相等。取一匙果汁放入水中，攪拌后再取一匙混合液體放回裝果汁的杯中。問：水中的果汁與果汁中的水哪一個更多？第一百零四頁，共一百二十一頁，編輯于2023年，星期二這一個例子也很有說服力要舉行一個由937名選手參加的網(wǎng)球錦標賽，獲勝的選手可以繼續(xù)比賽，失利的選手將被淘汰。為了完成這個錦標賽需要進行多少場比賽？第一百零五頁，共一百二十一頁，編輯于2023年，星期二一般的計算方法錦標賽的全部場次（87名種子選手）：1+2+4+8+16+32+64+128+256+425=936決賽半決賽1/4決賽第一百零六頁，共一百二十一頁，編輯于2023年，星期二答案可以這樣計算！因為一場比賽只淘汰1名選手，因此在有n名選手參加的錦標賽中，必須淘汰n-1名選手而產(chǎn)生1名勝者，因此需要進行n-1場比賽。所以937名選手，需要936場比賽！第一百零七頁，共一百二十一頁，編輯于2023年，星期二等分問題一個正方形分成相等的四部分，OK右邊的圖，如何分成相等的四部分？第一百零八頁，共一百二十一頁，編輯于2023年，星期二原來如此！再出問題：右邊的正方形，如何分成相等的五部分？第一百零九頁，共一百二十一頁，編輯于2023年，星期二14混合系統(tǒng)沒有任何單個算法稱得上是解決所有問題的最好方法。必須將問