多目標(biāo)規(guī)劃問題知識講解

多目標(biāo)規(guī)劃冋題精品文檔精品文檔收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系管理員刪除收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系管理員刪除3.5黑龍江省可持續(xù)農(nóng)業(yè)產(chǎn)業(yè)結(jié)構(gòu)優(yōu)化模型的求解鑒于上面的遺傳算法的基本實現(xiàn)技術(shù)和理論分析，對標(biāo)準(zhǔn)遺傳算法進(jìn)行適當(dāng)改進(jìn)，將其用于求解黑龍江省可持續(xù)農(nóng)業(yè)產(chǎn)業(yè)結(jié)構(gòu)優(yōu)化模型中。黑龍江省農(nóng)業(yè)產(chǎn)業(yè)結(jié)構(gòu)優(yōu)化模型具有大系統(tǒng)、多目標(biāo)、非線性等特點，傳統(tǒng)的求解方法受到了模型復(fù)雜程度的限制，由引言可知，遺傳算法對解決此類問題具有明顯的優(yōu)勢。下面介紹具體采用的遺傳多目標(biāo)算法操作設(shè)計以及模型求解過程。3.5.1遺傳多目標(biāo)算法操作設(shè)計3.5.1.1實數(shù)編碼方法在求解復(fù)雜優(yōu)化問題時，二進(jìn)制向量表示結(jié)構(gòu)有時不太方便，并且浮點數(shù)編碼的遺傳算法對變異操作的種群穩(wěn)定性比二進(jìn)制編碼好(徐前鋒， 2000)。以浮點數(shù)編碼的遺傳算法也叫實數(shù)遺傳算法( RealnumberGeneticAlgorithms,簡稱RGA)。每一個染色體由一個浮點數(shù)向量表示，其長度與解向量相同。假如用向量X(X1,X2xn)表示最優(yōu)化問題的解，則相應(yīng)的染色體就是V(X1,X2Xn)，其中n是變量個數(shù)。3.5.1.2種群初始化方法遺傳算法中初始群體的個體是隨機產(chǎn)生的，由于本文優(yōu)化模型所涉及的變量容易給出一個相對較大的問題空間的變量分布范圍，并且若給出一定的搜索空間也會加快遺傳算法的收斂速度；因此本文采取 3.3.2中的第一種策略，對每一個變量設(shè)置可能區(qū)間，然后在可能區(qū)間內(nèi)隨機產(chǎn)生初始種群。為保證不會遺漏最優(yōu)解，選擇區(qū)間跨度范圍很大。3.5.1.3適應(yīng)度函數(shù)設(shè)計

用遺傳算法求解多目標(biāo)優(yōu)化問題中出現(xiàn)的一個特殊情況就是如何根據(jù)多個目標(biāo)來確定個體的適應(yīng)值。本文采用Gen和Cheng提出的適應(yīng)性權(quán)重方法（AdaptiveWeightApproach），該方法利用當(dāng)前種群中一些有用的信息來重新調(diào)整權(quán)重，從而獲得朝向正理想點的搜索壓力（玄光男等， 2004）。將目標(biāo)函數(shù)按333所述轉(zhuǎn)化成帶有q個目標(biāo)（本文模型q3）的最大化問題：max{zib（x）,Z2f2（x）,,Zq fq（x）} （3-14）對于每代中待檢查的解來說，在判據(jù)空間中定義兩個極限點：最大極限點maxmaxZ {Z1 ,Z2,maxmaxmaxZ {Z1 ,Z2,max、，Zq }(3-15)-minmin minz {Z1 ,Z2 ,,Zq}其中zmax和zmin是當(dāng)前種群中第k個目標(biāo)的最大值和最小值。由兩個極限點定義的超平行四邊形是包含當(dāng)前所有解的最小超平行四邊形。兩個極限點每代更新，最大極限點最終將接近正理想點。目標(biāo)k的適應(yīng)性權(quán)重用下式計算:1maxmin

1maxmin

ZkZk(k1,2, ,q)因此，權(quán)重和目標(biāo)（Weighted-sumObjective）函數(shù)由下面的公式確定fk(x)fk(x)(3-16)z(x)kfk(x)k13.5.1.4遺傳操作（1）選擇操作。以比例選擇法和最優(yōu)個體保存法配合使用進(jìn)行選擇操作,即選擇過程仍以旋轉(zhuǎn)賭輪來為新的種群選擇染色體，適應(yīng)度越高的染色體被選中的概率越大；另一方面，為了保證遺傳算法的全局收斂性，在選擇作用后保留當(dāng)前群體中適應(yīng)度最高的個體，不參與交叉和變異，同時也確保當(dāng)前最優(yōu)個體不被隨機進(jìn)行的遺傳操作破壞。交叉操作。本文程序設(shè)計采用簡單交叉(SimpleXover)、算術(shù)交叉(ArithXover)、啟發(fā)式交叉(HeuristicXover)三種交叉方式并用的方法，在交叉概率選定的條件下，為每種交叉算子設(shè)計分配參與該種交叉的染色體的比例，這樣可以克服各種方法單獨使用的不足，增加了種群的多樣性。交叉概率經(jīng)多次嘗試后確定。對所使用的三種交叉算子做解釋如下：簡單交叉：如果種群中某兩個體被選中進(jìn)行交叉，則隨機選取一基因位，在此基因位處進(jìn)行交叉。例如：若兩個體Xi (Xi,,Xk,Xk1,,Xn)X2(X1,Xk,Xk1,,Xn)被選中，選擇第k基因位處交叉，交叉后有X1(X1,Xk,Xk1,,Xn)X2(X1,Xk,Xk1,,Xn)簡單交叉具備較強的破壞性，即染色體交叉后突破臨近解空間，可以促進(jìn)解空間的搜索，而不致過早收斂；但是簡單交叉不能對鄰近解空間搜索，并且在約束優(yōu)化過程中，交叉后可能突破解空間到不可行域中，從很大程度上減緩收斂。算術(shù)交叉：大體有以下三種類型：凸雜交(convexcrossove)，仿射雜交(affinecrossove)和線性雜交(linearcrossove)，本文程序采用線性雜交。種群中兩個體X1，X2被選中進(jìn)行交叉，交叉后X1必1 2X2X21X22X1其中1 21。經(jīng)線性雜交后，雜交后代為兩個體X1、X2連線上的兩個子個體，從而可在臨近空間進(jìn)行搜索，有效彌補簡單交叉的不足；然而若解空間為凹區(qū)域，則可能雜交后為不可行解，并且有可能收斂到局部最優(yōu)解，須用簡單交叉來彌補不足。啟發(fā)式交叉：如果種群中兩個體Xi、X2被選中進(jìn)行交叉，首先比較兩個體Xi、X2適應(yīng)度值，若eval(X2)eval(Xi)，則X；r(X2Xi)X2，其中r(0,1)，若X；不在可行域，重復(fù)以上步驟直至在可行域為止； X2X2。啟發(fā)式交叉可以向最優(yōu)解或近似最優(yōu)解快速收斂，并且交叉后兩個子個體均在可行域內(nèi)，這是簡單交叉、算術(shù)交叉所不具備的優(yōu)點；并且搜索方向可擴展到兩個體X；、X2連線外側(cè)，避免了算術(shù)交叉在這方面的不足。然而啟發(fā)式交叉有可能加速收斂到局部最優(yōu)解，與其他交叉算子配合使用較好。變異操作。類似于交叉操作，本文程序設(shè)計的變異操作也采用多種變異算子并用的方法，分別使用了下面四種變異算子：邊界變異(BoundaryMutation)、均勻變異(UnifMutation)、動態(tài)(或稱非均勻)變異(NonUnifMutation)、多點非均勻變異(MultiNonUnifMutation)參與變異運算，取長補短。對四種變異算子解釋如下：邊界變異：對于給定的父代X,如果它的元素Xk被選中進(jìn)行變異，則子代XkxU或xkL，其中xU、xkL通?？扇樽兞縓k的上下界，一般由約束域確定。這樣設(shè)置變異算子是由于很多優(yōu)化問題的全局最優(yōu)解通常存在于可行區(qū)域的邊界上。邊界變異運算的不足是不能變異為解空間內(nèi)點。均勻變異：若父代X的元素Xk被選中進(jìn)行變異，則后代為IX(X1,Xk,,Xn)，其中XkXkrand*Xk,Xk為Xk的取值范圍區(qū)間長度；均勻變異可以均勻搜索解空間，彌補邊界變異的不足，但其不具備微調(diào)功能，變異步長選擇比較困難。非均勻變異：若父代X的元素Xk被選出作變異，則后代為X (x1,xk,,xn)，其中Xk從下面兩種可能的方案中隨機選擇：XkXk (t,XUXk)XkXk (t,XkXL)函數(shù)(t,y)返回范圍［0,y］中的一個值，其中(t,y)yr(1*)b，r是［0,1］上的隨機數(shù)，T是最大遺傳代數(shù)，b是確定非均勻程度的參數(shù)。非均勻變異運算能得到較高的精度并且具備微調(diào)能力，即當(dāng)遺傳代數(shù) t增加時，(t,y)越來越趨向于0，該特性將會使算子在早期均勻沿坐標(biāo)軸方向搜索解空間，而到晚期則沿坐標(biāo)軸方向在很小區(qū)域進(jìn)行搜索，彌補了均勻變異的不足。但非均勻變異只是在某一基因位發(fā)生變異，從幾何上說只是在平行于坐標(biāo)軸的方向變異，不能實現(xiàn)空間搜索多點非均勻變異：若父代X的元素Xk被選出作變異，則后代為（Xi，Xk，,Xn）其中Xk的選擇同于非均勻變異，即對于個體的每個基因位都進(jìn)行非均勻變異;該變異運算不僅具有較高的精度和微調(diào)能力，而且可以實現(xiàn)整體空間變異，該特性使算子在早期均勻搜索解空間，而到晚期則在很小區(qū)域進(jìn)行搜索。然而無論是均勻變異，非均勻變異，多點非均勻變異均很難變異至邊界,對于約束優(yōu)化問題，有可能搜索不到邊界最優(yōu)解，故與邊界變異共同使用在程序設(shè)計中3.5.1.5約束條件的處理由于用來操作染色體的遺傳算子常常產(chǎn)生不可行后代，因此遺傳多目標(biāo)優(yōu)化中的一個重要問題就是如何處理約束。本文采用 Gen和Cheng提出的適應(yīng)性罰函數(shù)(AdaptivePenaltyFunction)方法來處理不可行個體。在當(dāng)前種群 P(t)中給定一個個體x，設(shè)多目標(biāo)優(yōu)化模型的約束條件為gi(x) 0,(i1,2,m)，其適應(yīng)性罰函數(shù)構(gòu)造如下：p(x)11m(bi(x))kmi1 bimax(3-17)其中，bi(x)max{0,gi(x)bi}max(3-18)bimax{,bi(x)|xP(t)}bi(x)是當(dāng)前染色體對第i個約束的違背值， b^x是當(dāng)前種群中對約束i的最大違背值， 是一個小正數(shù)，用來避免罰函數(shù)中出現(xiàn)被零除的情況。對于高度約束的最優(yōu)化問題，每代中不可行解占據(jù)相對較大的部分。該罰函數(shù)在每代中適應(yīng)性調(diào)整懲罰率，從而既保存了不可行解有用的信息，又對不可行解施加了選擇壓力，還避免了過度懲罰。綜合3.5.1.3和3.5.1.5，確定優(yōu)化模型的適應(yīng)度函數(shù)為eval(x)z(x)p(x) (3-19)3.5.2模型求解結(jié)果及分析根據(jù)遺傳算法操作設(shè)計3.5.1，采用Matlab6.5對黑龍江省可持續(xù)農(nóng)業(yè)產(chǎn)業(yè)結(jié)構(gòu)模型編寫求解實現(xiàn)程序(見附錄)，為每個變量設(shè)置大略分布范圍，種群規(guī)模取為60,交叉率0.4,其中單點交叉?zhèn)€體數(shù)量4對，算術(shù)交叉?zhèn)€體數(shù)量6對，啟發(fā)式交叉?zhèn)€體數(shù)量14對；變異率0.3，其中邊界變異個體數(shù)量為2，均勻變異個體數(shù)量為4,非均勻變異個體數(shù)量為4,多點非均勻變異個體數(shù)量為&經(jīng)多次迭代后得到模型的一系列pareto解（有效解），見表3-1（此處列出50組）；繪出所得解的空間分布，見圖3-1。綜合考慮得到的pareto解序列，對各個變量進(jìn)行全面衡量，對目標(biāo)函數(shù)進(jìn)行結(jié)果分析，并咨詢有關(guān)專家，選擇第29個有效解為整個產(chǎn)業(yè)結(jié)構(gòu)優(yōu)化的“最優(yōu)解”（注：決策者可根據(jù)個人對目標(biāo)要求從表3-1中選擇合適的解）。見表3-2。表3-1和3-2中，E（X）單位為億元，其余單位與前面一致。表3-2可持續(xù)農(nóng)業(yè)產(chǎn)業(yè)結(jié)構(gòu)優(yōu)化“最優(yōu)解”Table.3-2"Solvingoptimumly"oftheindustrialstructureofsustainableagriculture變量X11X12X13X14X15X16X17優(yōu)化值154.6640.00198.56295.048.23812.97228.617變量X18X19X110X111X112X113X114優(yōu)化值68.48323.07742.29925.94857.50926.35620.179變量X115X21X22X23X24X25X3優(yōu)化值29.452500320.52898.51212.8299842378.4變量X4E(X)(X)D(X)優(yōu)化值50.609604.320.0008855.711.250.044612GU1.15*□.D42611.250.044612GU1.15*□.D4261_0.066.06圖3-1黑龍江省農(nóng)業(yè)產(chǎn)業(yè)結(jié)構(gòu)模型的pareto解前沿面Fig.3-1SolvingsurfacethatparetotothemodelofHeilongjiangsagricultural

structure表3-1黑龍江省可持續(xù)農(nóng)業(yè)產(chǎn)業(yè)結(jié)構(gòu)優(yōu)化 pareto解Tab?3-1Pareto,solve^ofHeilpngjiapgss?stainqbleagriculturalindystrialstructure序號 X11X12X13 X14X15X16X17X18X19X譏X111 X“2

151.1529.72198.52296.687.999512.24139.08264.3127.62440.46424.40/55.073~T~153.3829.06199.82295.617.962512.35137.2564.21325.1540.81724.60455.147~3~151.1529.72198.52296.687.999512.24139.08264.3127.62440.46424.40/55.073~4~153.3629.056199.82295.618.19412.79249.99668.01429.82437.04723.156.106~5~153.3829.06199.82295.618.19412.79349.99667.9529.93337.04923.10156.1116152.0128.725199.37294.328.085612.17239.51563.25926.50642.28324.58755.351~^r~152.0128.699199.34294.188.17612.74920.00161.05323.72842.95925.01355.258156.7832.119194.88298.848.210112.19330.54867.19641.9336.64523.38654.8849155.5632.385194.35299.238.182612.79435.46977.80724.71138.16925.22255.41310153.1927.473199.82297.97.66312.19238.59261.68839.56943.62824.75554.99211152.0128.699199.34294.188.17612.74936.27572.08229.8932.72522.72554.05112「151.6/[28.753「198.74294.318.01612.19839.85863.41223.76540.85124.57254.64513P155.82:32.084P193.67287.67P9.076311.79538.88561.36731.92441.894P24.88954.71614：156.27；32.02:193.7287.67:9.076111.79538.90361.28131.92441.883:24.88954.70215P151.59[28.955P199.37294.42P8.088512.22539.49963.25923.74940.989P24.65954.63816156.2732.02193.7298.668.219412.20430.67267.09441.16236.78223.38854.91717:152.22；28.097:199.66294.14:8.003112.1933.5365.31729.29739.814:22.85156.58718152.328.131199.66294.318.001812.19833.40265.31829.29639.77922.82756.59319156.7832.119194.88298.848.213412.85735.21267.81323.48437.88525.42655.45520152.9829.566199.2296.048.178612.76449.12667.70130.26337.38523.20656.23821156.7832.119200298.848.213412.85735.21264.50841.31739.99323.76455.26422156.7832.139189.33299.478.155412.39236.64363.35635.55739.9625.47357.22623156.7832.119200298.848.213412.85735.21267.81323.48437.88525.42655.45524156.7832.12199.99298.848.213412.85935.21467.8223.48337.88425.42655.45625154.6629.451198..56295.048.23812.97328.61868.48323.07742.29825.94857.50826151.8837.996199.11313.578.73518.348125.60264.5527.67735.06223.70458.28727156.7832.137194.89298.898.211212.85235.23967.80422.53337.9124.17557.83128156.6932.029193.74287.679.076611.78621.99561.92925.0442.59724.87459.64129154.6640.00198.56295.048.23812.97228.61768.48323.07742.29925.94857.50930153.3829.06199.82295.58.200112.79249.97167.95329.93337.04923.12459.29431153.3829.06199.82295.618.19412.79349.99667.9529.93337.04923.10156.11132153.3829.06199.82259.618.19412.79349.99667.9529.93337.04923.10156.11133153.1233.236192.19317.727.71214.30336.09765.89744.91638.54623.37654.92634P152.23127.979P199.66293.47P8.016812.18933.46665.31829.29739.977P22.88156.53935153.38」29.06199.82295.61「8.19412.79349.99667.9529.93337.049「23.10156.11136156.78」32.119194.88298.848.213412.85735.21267.81323.48437.885「25.42655.45537153.38J29.054199.82259.618.199712.79345.95367.94629.92837.054P23.09456.11138「156.532.196194.77298.978.204812.83935.28967.7123.76437.966「25.37955.44539156.7832.119194.88298.848.213412.85735.21267.81322.48437.88525.42655.44540156.78J32.128194.9298.898.212712.85235.23767.80423.48437.90125.42555.45441P156.78132.139P194.9298.89二8.211212.85135.23667.80927.13341.113二25.42555.45442P156.78:32.139P194.4298.898.211312.85235.23667.80636.2237.907P25.42555.45443P156.78:32.139r194.9298.89P8.211312.85235.23667.80423.48437.907r25.42555.45444P153.38:29.06r199.82295.5P8.200112.79249.97167.95329.93337.049P23.12456.1145153.3729.058199.76295.258.186512.78749.86968.67227.75839.49924.34255.30946152.0128.699199.34294.188.17612.74920.00161.05323.72842.95925.01355.2547156.7832.119194.88298.848.213412.85735.21267.81323.48437.88525.42655.11748153.3629.056199.82295.618.19412.79249.99668.01429.82437.04723.156.10649156.532.196194.77298.978.204812.83935.28967.7123.76437.96725.37955.44550156.7832.139194.9298.898.211312.85235.23667.80436.2237.90725.42555.454X113X114X115X21X22X23X24X25X3X4E(X)(X)D(X)26.54120.72632.015423.16323.312795.51000.0290752048.963.889596.210.0017948.8726.25719.82932.98427.07309.432818.21123.4285162053.564.483595.880.0019948.4926.54120.72632.015423.16323.312795.51140.9290752048.963.889596.930.0019948.2825.96319.59237.973434.7290.212763.81220.5300911968.663.895595.060.0022944.525.96319.5937.898434.7290.222769.41219300901968.463.896595.090.0022944.1626.03720.4629.111422.63328.192608.21068.5283272009.156.405592.650.0009943.2826.46420.2428.904420.71327.382797.71085.9273292024.362.275593.350.0021940.4925.58220.15733.393425.44318.72783.91084277342115.165.072597.520.0013937.8526.45120.17630.486422.78320.652817.81284.927753190048.023592.340.0030932.5728.32119.98127.882440.52265.832679.31228.9300402185.560.047594.720.00061000.924.72520.31627.239430.51321.832838.31214.8299252070.472.226593.820.0021963.2325.40920.19632.424424.78325.22791.71132.527070213765.029594.890.0013960.7325.76520.40931.955420.85325.582832.5P1141.6265972174.5P62.724596.320.0012959.5825.79420.40431.994420.85325.512832.5「1141.3266022174.762.699596.580.0012957.7825.54120.11232.425424.04325.252806.2「1134.1270752136.8:65.968595.660.0014957.625.80519.76537.499451.47306.232743.4「1084.42764.62115.5「65.073598.160.0012957.3229.04319.50329.708434.73321.942725.5「1104.2287392110.5「59.103599.570.0013917.1329.04319.50329.693434.71321.942873.31192.4274292124.658.321600.350.0018914.7926.48422.17729.324495.05320.262821.7P1207.2298632398.8P63.429606.560.0004913.3126.16420.10839.446「500320.32821.7P1207.2298122398.8P48.09601.080.0003911.953020.11736.128423.24321.822791.3[1129.5271792076.4二59.457606.630.0015908.2424.6419.89629.203421.85317.92807.81188.2268742030.4P60.701595.610.0020908.0626.48420.17729.324422.92320.262821.71207.2298632398.848.02595.610.0001903.0726.47920.17429.324422.93320.262821.71207.2298632398.865.073602.670.0001898.4226.35620.17829.452423.15320.52898.61212.8299842378.450.609597.070.0005880.4125.94319.71231.982458.48295.143115.31181.5229752330.249.729595.480.0012877.7825.94719.7536.234430.46318.812787.31129.4264042087.759.733598.40.0015874.6225.91419.93434.258427.64304.362939.11128.7271942135.465.118597.850.0018867.3326.35620.17929.452500320.52898.51212.8299842378.450.609604.320.0008855.7125.96719.58837.902434.73318.772788.31084.4263632157.561.361600.720.0010851.6325.96319.5937.898434.7318.7827881084.4263462157.561.354598.030.0010921.1725.96319.5937.635420.86317.752812.11152.2277632085.855.861594.560.0015921.1626.09420.14133.233424.86318.952788.21087.7346802113.564.724603.330.0014919.7428.98619.51429.725434.64321.682724.11104.22