嵌入模糊部件的數(shù)值圖規(guī)劃.pdf

1、人們對(duì)問題求解規(guī)劃器的研究已經(jīng)持續(xù)了半個(gè)世紀(jì)之久，在眾多規(guī)劃器中備受矚目的是AvrimBlum和MerrickFurst于1995年提出的經(jīng)典圖規(guī)劃。圖規(guī)劃首次將規(guī)劃圖應(yīng)用于規(guī)劃器設(shè)計(jì)。規(guī)劃圖的高度并行性使得規(guī)劃器求解效率有了質(zhì)的飛躍。此后很多優(yōu)秀的規(guī)劃器都沿用了該結(jié)構(gòu)。但是由于圖規(guī)劃尚未突破STRIP域問題表示及經(jīng)典規(guī)劃三大假設(shè)的強(qiáng)約束限制，所以它不能夠表示、求解具有資源分配和細(xì)節(jié)信息獲取的規(guī)劃問題。 通過對(duì)數(shù)值表達(dá)式比較為規(guī)

2、劃對(duì)象進(jìn)行資源分配的規(guī)劃稱為數(shù)值規(guī)劃。資源爭(zhēng)用為數(shù)值規(guī)劃帶來了額外的資源約束，這使得在圖結(jié)構(gòu)上求解數(shù)值規(guī)劃問題格外困難。所以在高效的圖結(jié)構(gòu)上開發(fā)數(shù)值規(guī)劃器是規(guī)劃研究的一個(gè)難點(diǎn)。1999年JanaKoehler提出了基于規(guī)劃圖結(jié)構(gòu)的數(shù)值圖規(guī)劃。它對(duì)數(shù)值規(guī)劃研究做出了以下兩點(diǎn)貢獻(xiàn)(1)擴(kuò)展了圖規(guī)劃的問題表示能力，使得資源描述成為可能。(2)使一個(gè)規(guī)劃器同時(shí)具備求解經(jīng)典和資源兩類規(guī)劃問題的能力。但是數(shù)值圖規(guī)劃在繼承經(jīng)典圖規(guī)劃高效性的同時(shí)，也繼

3、承了它的強(qiáng)約束性結(jié)構(gòu)。而過強(qiáng)的約束通常會(huì)破壞規(guī)劃器捕捉現(xiàn)實(shí)世界問題細(xì)節(jié)信息的能力，并導(dǎo)致規(guī)劃提取的效率偏低或求解失敗。 大多數(shù)規(guī)劃器是通過軟約束定義獲取規(guī)劃問題細(xì)節(jié)信息的。軟約束分為偏好約束和優(yōu)先權(quán)約束兩種。它們都定義在與問題相關(guān)的規(guī)劃對(duì)象上，其度量值代表了它們?cè)谝?guī)劃求解中的重要程度。由Dubois等人創(chuàng)建的，具有不確定性問題表示能力的模糊集合系統(tǒng)為偏好、優(yōu)先權(quán)提供了天然的度量工具。 為解決實(shí)際應(yīng)用需要，開發(fā)具有軟約束的