遺傳算法課件chapter

NatureInspired李斌NatureInspired李斌考核方課程設(shè)考核方課程設(shè)第一章最優(yōu)化問題的定最第一章最優(yōu)化問題的定最優(yōu)化問題的分關(guān)于計(jì)算復(fù)雜最優(yōu)化方法的一般結(jié)最優(yōu)化問題的定minf最優(yōu)化問題的定minf(x)s.t.x其中xRn是決策變量，f(x)為目標(biāo)函數(shù)，Xminf(x)X最優(yōu)化問題的定minf最優(yōu)化問題的定minf(x)s.t.ci(x)ci(x)iE,iI.這里E和I分別是等式約束的指標(biāo)集和不等式最優(yōu)化問題的分最優(yōu)化問題的分最優(yōu)化問題的分最優(yōu)化問題的分最優(yōu)化問題舉例SRn上的有界子集，f:SR值最優(yōu)化問題舉例SRn上的有界子集，f:SR值fS求點(diǎn)XmaxSmax)x函數(shù)優(yōu)化問函數(shù)優(yōu)化問函數(shù)優(yōu)化問函數(shù)優(yōu)化問函數(shù)優(yōu)化問函數(shù)優(yōu)化問最優(yōu)化問題舉例最優(yōu)化問題舉例實(shí)例集合對(duì)每一個(gè)實(shí)例I目標(biāo)函數(shù)f，它對(duì)每一個(gè)實(shí)例I解S(f(I,數(shù)值達(dá)到最大或最小的解?！?、有約束條件數(shù)值達(dá)到最大或最小的解?！?、有約束條件的、高度非線性的NP完（難）最優(yōu)解的“有效”集覆蓋問題（set-covering背包問題（knapsack集覆蓋問題（set-covering背包問題（knapsack指派問題（assignment旅行商問題（travelingsalesman影片遞送問題（filmdelivery最小生成樹問題（minimumspantree圖劃分問題作業(yè)調(diào)度問題（job-shopscheduling集覆蓋問題（set-covering集覆蓋問題（set-covering設(shè)向量xxj=1j被選中（cj>0），xj=0 z(x)cj z(x)cjxnnaijxi1,2,L,j1,2,L,xj（unicostset-coveringproblem）則稱為集劃分問題（setpartitioningc[0c5[01101082]10011010110001000110101100c[0c5[01101082]1001101011000100011010110001000110x01A1(10000001]02610101Cost=裝箱問題（binpackingnz(y)所有物裝箱問題（binpackingnz(y)所有物品都裝所裝物品不得超過子得容inwjcyiiN{1,2,L,一個(gè)物品只能入一個(gè)箱n jyi0或ii,j0或貨運(yùn)裝箱問截貨運(yùn)裝箱問截銅棒問布匹套裁問。。裝箱問題屬于NP－難問和容量為C的背和容量為C的背包；要求找出n個(gè)物件的一個(gè)子集使盡可能多地填滿容量為C的背包nini ,inPiXiSiXinXi1iC,背包問題屬于NP-難問m最大化所選物的總價(jià)cij m所選物品的總m最大化所選物的總價(jià)cij m所選物品的總體積得超過背包容wij 每一類中只選一個(gè)物i1,2,L,i,為第i類中第j個(gè)項(xiàng)目的體積，W是背包的容積旅行商問題（TravelingSalesman旅行商問題（TravelingSalesman子集X＝{1，2，…，n}（X的元素表示對(duì)n個(gè)城市的編號(hào)）的一個(gè)排列π(X)={v1，v2，…，vn}，使下式取最 d(vi,vi1)d(v1,vn,對(duì)稱旅行商問題是NP－難問影片遞送問題（FilmDelivery影片遞送問題（FilmDelivery最小生成樹問題（MinimumSpanTree通的無向圖G＝(VE)，其中，Vv1v最小生成樹問題（MinimumSpanTree通的無向圖G＝(VE)，其中，Vv1v2是代表終端或通信站的有限的端點(diǎn)集。E＝{eij|eij(vivivjV記為W＝{wij|wijw(vivjwij0vivjV}的正實(shí)數(shù)的權(quán)minTTeEV，將頂點(diǎn)集合V劃分為兩個(gè)子集V，將頂點(diǎn)集合V劃分為兩個(gè)子集V1和V2，Vl，求使V1和V2兩頂點(diǎn)子集之間聯(lián)結(jié)最少的一種古典作業(yè)車間調(diào)度問題（Job-shopScheduling）：有m臺(tái)不古典作業(yè)車間調(diào)度問題（Job-shopScheduling）：有m臺(tái)不(1(2(3·《遺傳算法與工程優(yōu)化關(guān)于計(jì)算復(fù)雜關(guān)于計(jì)算復(fù)雜關(guān)于計(jì)算復(fù)雜利用計(jì)算機(jī)求解某一類問題的方法，稱為計(jì)算方法簡(jiǎn)稱算法可計(jì)算理論關(guān)于計(jì)算復(fù)雜利用計(jì)算機(jī)求解某一類問題的方法，稱為計(jì)算方法簡(jiǎn)稱算法可計(jì)算理論若所給問題可以求解，則稱該問題是可計(jì)算的或的，否則稱為不可解關(guān)于計(jì)算復(fù)雜計(jì)算復(fù)雜性理論同算法的復(fù)雜性程度，來衡量（求解）關(guān)于計(jì)算復(fù)雜計(jì)算復(fù)雜性理論同算法的復(fù)雜性程度，來衡量（求解）算法的計(jì)算復(fù)雜算法的計(jì)算復(fù)雜算法的計(jì)算復(fù)雜性：時(shí)間復(fù)雜性，空間復(fù)雜式計(jì)算機(jī)對(duì)算法復(fù)雜性分析的影響存取機(jī)。。。（一次初等運(yùn)算式計(jì)算機(jī)對(duì)算法復(fù)雜性分析的影響存取機(jī)。。。（一次初等運(yùn)算問題規(guī)模的度量與所采用的編碼測(cè)量（題所需的字符集，以及描述方式）算法的計(jì)算復(fù)雜給定任一問題Π算法的計(jì)算復(fù)雜給定任一問題Π的一個(gè)合理編碼策略e，則對(duì)Π的任一例子I算法的計(jì)算復(fù)雜算法的計(jì)算復(fù)雜城市Ci,Cj之間的距離d(Ci,Cj)所組成。旅行商問題的9,d(C2,C3)=6,d(C2,C4)＝9和d(C3,C4)=3體例子，而這個(gè)例子的一個(gè)解是排序行路線中長(zhǎng)度最小的，為27算法的計(jì)算復(fù)雜算法的計(jì)算復(fù)雜來描述。其相應(yīng)的輸入長(zhǎng)度為32，從而稱這例子的大小為32算法的計(jì)算復(fù)雜定義：算法的計(jì)算復(fù)雜定義：對(duì)于不同的算法，就有著不同的時(shí)間復(fù)雜性函數(shù)。復(fù)雜性函數(shù)的不同變化方式反映了算法的好壞程度。例如，時(shí)間復(fù)雜性函數(shù)關(guān)于輸入長(zhǎng)度的增長(zhǎng)速度就是判算法的計(jì)算復(fù)雜算法的計(jì)算復(fù)雜多項(xiàng)式時(shí)間算法（polynomialtime指數(shù)時(shí)間算法（exponentialtime算法的計(jì)算復(fù)雜多項(xiàng)式時(shí)間算法的計(jì)算復(fù)雜多項(xiàng)式時(shí)間算法是指存在某個(gè)以輸入長(zhǎng)度n為變量的多項(xiàng)式函數(shù)p(n),使其時(shí)間復(fù)雜性函數(shù)為O(p(n))的算法。因指數(shù)時(shí)間算法（exponentialtimealgorithm）：是型的例子有2n,n!,nn,nlbn等算法的計(jì)算復(fù)雜算法的計(jì)算復(fù)雜與g(n)，若存在兩個(gè)常數(shù)cc’0，使得當(dāng)n充分大時(shí)有c’g(n)≤f(n)≤cg(n)，則記f(n)=算法的計(jì)算復(fù)雜算法的計(jì)算復(fù)雜算法的計(jì)算復(fù)雜總結(jié)通常只關(guān)心算其次，在考慮算法的復(fù)雜性時(shí)，法在算法的計(jì)算復(fù)雜總結(jié)通常只關(guān)心算其次，在考慮算法的復(fù)雜性時(shí)，法在問題例子的規(guī)模n充分大時(shí)的表現(xiàn)問題的復(fù)雜性分目前所廣泛采用的描述問題的方法將任一問題轉(zhuǎn)化為所謂的（feasibilityproblem），問題的復(fù)雜性分目前所廣泛采用的描述問題的方法將任一問題轉(zhuǎn)化為所謂的（feasibilityproblem），二是把問題轉(zhuǎn)述為題problem）問題的復(fù)雜性分“判定問題”只與非兩種可能的問題。一個(gè)判定問題Π可簡(jiǎn)單地由其所有例子的集合DΠ為“是問題的復(fù)雜性分“判定問題”只與非兩種可能的問題。一個(gè)判定問題Π可簡(jiǎn)單地由其所有例子的集合DΠ為“是的子集YΠDΠ等各種描述分量來刻畫判定問題的一般性例子；“問題的復(fù)雜性分語言（language）：對(duì)于字符的任一有限集合問題的復(fù)雜性分語言（language）：對(duì)于字符的任一有限集合言。例如，{01,001,111,1010110}就是字符集＝{0,1}L[Π,e]={x*:為e所使用的字符集、而x為某個(gè)例子在e}問題的復(fù)雜性分機(jī)（Deterministicone-問題的復(fù)雜性分機(jī)（Deterministicone-問題的復(fù)雜性分帶中所有字符的一個(gè)有限集合，它應(yīng)包括輸入字符表子集問題的復(fù)雜性分帶中所有字符的一個(gè)有限集合，它應(yīng)包括輸入字符表子集和一個(gè)特別的空白符號(hào)b-。一個(gè)有限狀態(tài)集Q，它包括初始狀態(tài)q0和兩個(gè)特有 Nq可以設(shè)計(jì)一個(gè)DTM問題的復(fù)雜性分稱一個(gè)帶有輸入字符表問題的復(fù)雜性分稱一個(gè)帶有輸入字符表的DTM程序M接受x*，當(dāng)且x時(shí)停機(jī)于狀態(tài) 只有當(dāng)一個(gè)DTM程序?qū)Χx于其輸入字符表上的所有才稱其為一個(gè)算法地，稱一個(gè)DTM程序M在編碼策略e之下求解判定問Π，如果M對(duì)定義于其輸入字符表上的所有輸入字串均停機(jī)且有=L[Π,e]問題的復(fù)雜性分問題的復(fù)雜性分x*均TMZ+Z+TM(nmax{m存在一個(gè)x*，|x|n，使得M對(duì)問題的復(fù)雜性分若存在問題的復(fù)雜性分若存在一個(gè)多項(xiàng)式p(n)，使得對(duì)所有的nZ+，有TM(n)p(n)，則稱程序M為一個(gè)多項(xiàng)式時(shí)間DTMP＝{L:存在一個(gè)多項(xiàng)式時(shí)間DTM程序M，使得L=LM若存在一個(gè)多項(xiàng)式時(shí)間DTM程序，它在編碼策略e之下求解Π，即L[Π,e]P，則稱該判定問題Π屬于P。問題的復(fù)雜性分非確定性單帶機(jī)（-one-機(jī)）完TuringMachine——問題的復(fù)雜性分非確定性單帶機(jī)（-one-機(jī)）完TuringMachine——NDTM，又稱非確定性全是一種假想的機(jī)器，通常有兩種方法來描述它：多用假想模塊模型，NDTM可描述成：除多了一個(gè)猜想模帶有自己的僅可對(duì)條帶寫的猜想頭，它提供了寫下猜問題的復(fù)雜性分問題的復(fù)雜性分問題的復(fù)雜性分一般來說，問題的復(fù)雜性分一般來說，對(duì)于一個(gè)給定的輸入字符串x，NDTM程 xM接受M問題的復(fù)雜性分問題的復(fù)雜性分MTMZ+Z+TM(nmax[{1}{m存在一個(gè)長(zhǎng)度為n的xLM，問題的復(fù)雜性分p(n問題的復(fù)雜性分p(n，使得對(duì)所有的n1，有TM(np(n)，則稱NDTM程序M為一個(gè)多項(xiàng)式時(shí)間NDTM程序定義NP類語言（問題NPL存在一個(gè)多項(xiàng)式時(shí)間NDTM程序M，使得問題的復(fù)雜性分若NPp使得可以用一個(gè)時(shí)間復(fù)雜性為O(2p(n)問題的復(fù)雜性分若NPp使得可以用一個(gè)時(shí)間復(fù)雜性為O(2p(n))的確定性算法來求解。q(n的判定問題q(n)kq(nP問題的復(fù)雜性分L11*到另一個(gè)語言問題的復(fù)雜性分L11*到另一個(gè)語言L2*的2式變換是指滿足下面兩個(gè)條件的函數(shù)f1*存在計(jì)算f的一個(gè)多項(xiàng)式時(shí)間DTM程序?qū)τ谒械膞1*，xL1當(dāng)且僅當(dāng)f(x)L2用記號(hào)L1L2表示存在一個(gè)從L1到L2的多項(xiàng)式變換2稱一個(gè)語言L（判定問題）為NP完全的LNP(NP)，且對(duì)所有別的語言LNP)，均有L’L(’))，如問題的復(fù)雜性分個(gè)偏序（L1問題的復(fù)雜性分個(gè)偏序（L1L2意味著L1比L2不難）。由NP完全的語言（判定問題）所形成的另一個(gè)等價(jià)則包含了NP類中那些“問題的復(fù)雜性分設(shè)1和2說1）規(guī)約問題的復(fù)雜性分設(shè)1和2說1）規(guī)約]為2，如果存在1可一個(gè)算法A1，它多次調(diào)用求解2的算法A2序，并且若假設(shè)每次調(diào)用該子程序A2時(shí)到2的多項(xiàng)式時(shí)間規(guī)約，記為T。1問題的復(fù)雜性分如果蘊(yùn)涵規(guī)約到2，那么問題的復(fù)雜性分如果蘊(yùn)涵規(guī)約到2，那么211是多項(xiàng)式時(shí)間可解的，從而表明2定義：對(duì)于判定問題，若存在一個(gè)NP完全的問’，使得T，則稱問題是的經(jīng)典最優(yōu)化方法的一般結(jié)：給經(jīng)典最優(yōu)化方法的一般結(jié)：給定解空間中的一個(gè)初始點(diǎn)x0Rn，按照一迭代規(guī)則產(chǎn)生一個(gè)點(diǎn)序列{xk}，使得當(dāng){xk}是有窮地接近局部極小點(diǎn)x*的鄰域，然后迅速收斂于x*。當(dāng)經(jīng)典最優(yōu)化方法的一般結(jié)設(shè)k為第k次迭代點(diǎn)，k為第k次搜索方向，k為第k次步長(zhǎng)因子，則第經(jīng)典最優(yōu)化方法的一般結(jié)設(shè)k為第k次迭代點(diǎn)，k為第k次搜索方向，k為第k次步長(zhǎng)因子，則第次迭代為xk+1=xk+k從這個(gè)迭代格式可以看出，不同的步長(zhǎng)因子k和不的搜索方向了不同的方法在經(jīng)典最優(yōu)化方法中，搜索方向dk是f在xk點(diǎn)處的下方向，即d滿足 )xkkkkd)kf(或kk經(jīng)典最優(yōu)化方法的一般結(jié)(1)給定初經(jīng)典最優(yōu)化方法的一般結(jié)(1)給定初始點(diǎn)確定搜索方向dkf確定步長(zhǎng)因子k，使目標(biāo)函數(shù)值有某種意義的下xk+1xkk(2)若xk+1滿足某種終止條件，則停止