基于狀態(tài)轉(zhuǎn)移的組合優(yōu)化方法

前言

隨著社會發(fā)展，出現(xiàn)了大量組合優(yōu)化問題，如資源配置、生產(chǎn)調(diào)度、VLSI技術(shù)、指揮控制等，迫切需要對這些問題進(jìn)行快速、高效地求解。一般情況下，由于組合優(yōu)化問題的可行解的數(shù)量隨問題規(guī)模增大呈指數(shù)增長趨勢，難以用較短時間精確求解較大規(guī)模的組合優(yōu)化問題，人們只好采用簡單的啟發(fā)式方法獲得問題的近似解，如貪婪算法、局部搜索方法等，這些簡單的啟發(fā)式方法對改進(jìn)解的質(zhì)量影響有限。從20世紀(jì)80年代開始，人們對現(xiàn)有方法存在的不足進(jìn)行分析，并借鑒自然界的相關(guān)規(guī)律，陸續(xù)提出了一些新的優(yōu)化算法，如模擬退火、禁忌搜索、遺傳算法、神經(jīng)網(wǎng)絡(luò)、粒子群算法和蟻群算法等。這些方法的共同目標(biāo)是減少搜索量、提高搜索效率。為達(dá)到這一目標(biāo)，不同方法從各個角度完善搜索策略，希望能夠得到最優(yōu)解。依據(jù)“沒有免費(fèi)的午餐”定理，為了得到更好的解，就得付出更大的代價。如導(dǎo)引式局部搜索方法，求解時隨著近似解的改進(jìn)修改目標(biāo)函數(shù)，使用同一種搜索方法就能得到更好的近似解，但是計算量成倍增加。如果利用問題的領(lǐng)域知識，可以設(shè)計更加快速高效的算法。如Pisinger等人提出了某些條件下0／1背包問題的快速精確求解方法，可以在很短的時間內(nèi)獲得問題的最優(yōu)解；改進(jìn)的I。in-Kernighan方法可以快速求取旅行推銷員問題高質(zhì)量的近似解。因此，怎樣利用問題的領(lǐng)域知識設(shè)計更加有效的算法是組合優(yōu)化方法研究的重點(diǎn)。

內(nèi)容概要

本書介紹了優(yōu)化方法的相關(guān)概念、函數(shù)優(yōu)化方法和啟發(fā)式組合優(yōu)化方法，重點(diǎn)闡述了基于狀態(tài)轉(zhuǎn)移的組合優(yōu)化方法，并介紹了使用基于狀態(tài)轉(zhuǎn)移的組合優(yōu)化方法研究0／1背包問題、加工排序問題、旅行推銷員問題以及武器一目標(biāo)分配問題求解方法的成果。    本書可作為優(yōu)化技術(shù)相關(guān)專業(yè)高年級本科生、研究生的教學(xué)、輔導(dǎo)用書，也可作為相關(guān)科研工作者和技術(shù)人員的參考書。

書籍目錄

前言第1章  概述  1.1  最優(yōu)化問題及其分類    1.1.1  函數(shù)優(yōu)化問題    1.1.2  組合優(yōu)化問題  1.2  優(yōu)化方法  1.3  鄰域、計算復(fù)雜性與NP    1.3.1  鄰域    1.3.2  計算復(fù)雜性    1.3.3  P、NP、NP-hard與NPC  1.4  近似求解方法及其評價    1.4.1  近似求解方法    1.4.2  基于目標(biāo)函數(shù)值的評價方法    1.4.3  基于計算時間的評價方法    1.4.4  近似方法的綜合評價第2章  函數(shù)優(yōu)化方法第3章  組合優(yōu)化方法第4章  基于狀態(tài)轉(zhuǎn)移的組合優(yōu)化方法第5章  同順序加工調(diào)度問題的求解方法第6章  0/1背包問題的精確求解方法第7章  旅行推銷員問題求解方法第8章  武器-目標(biāo)分配問題求解方法參考文獻(xiàn)

章節(jié)摘錄

插圖：采用計算實(shí)例的方法評價近似方法時，我們不可能窮盡所有可能的實(shí)例，只能選擇部分實(shí)例。怎樣去選擇（或者構(gòu)造）測試算法的實(shí)例呢？為了使得測試評價結(jié)果更具有可信性，一般使用近似方法計算一些基準(zhǔn)問題（Benchmark），通過求取的基準(zhǔn)問題的解來反映近似方法的優(yōu)劣。另外一種構(gòu)造實(shí)例的方法是隨機(jī)生成實(shí)例的方法，即按照一定的分布規(guī)律隨機(jī)產(chǎn)生實(shí)例的數(shù)據(jù)。有時候使用某些近似方法求解一些問題時，發(fā)現(xiàn)求解比較困難，分析發(fā)現(xiàn)這是由于實(shí)例中數(shù)據(jù)間存在的特定關(guān)系引起的。為了使得生成的實(shí)例較好地反映出這一點(diǎn)（即具有代表性），選擇多種不同概率分布函數(shù)作為實(shí)例數(shù)據(jù)服從的概率分布函數(shù)

編輯推薦

《基于狀態(tài)轉(zhuǎn)移的組合優(yōu)化方法》是由西安交通大學(xué)出版社出版的。

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

    基于狀態(tài)轉(zhuǎn)移的組合優(yōu)化方法 PDF格式下載

---