最優(yōu)路徑規(guī)劃算法設(shè)計(jì)報(bào)告(共24頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上最優(yōu)路徑規(guī)劃算法設(shè)計(jì)一、 問題概述兵力機(jī)動(dòng)模型的功能是支持實(shí)施機(jī)動(dòng)的實(shí)體按照指定路線，由作戰(zhàn)空間的一點(diǎn)向另外一點(diǎn)的位置移動(dòng)，并帶入實(shí)體在移動(dòng)過程中發(fā)生變化的狀態(tài)信息。兵力機(jī)動(dòng)模型包括行軍模型、戰(zhàn)斗轉(zhuǎn)移模型、機(jī)動(dòng)能力評估模型。涉及的關(guān)鍵算法包括最優(yōu)路徑規(guī)劃、行軍長徑計(jì)算、行軍時(shí)間計(jì)算、行軍所需油料計(jì)算、行軍方案評估與優(yōu)選等。最優(yōu)路徑問題又稱最短路問題。是網(wǎng)絡(luò)優(yōu)化中的基本問題，如TSP問題等。下面先舉例說明該問題。最短路問題（SPPshortest path problem）一名貨柜車司機(jī)奉命在最短的時(shí)間內(nèi)將一車貨物從甲地運(yùn)往乙地。從甲地到乙地的公路網(wǎng)縱橫交錯(cuò)，因此有多種

2、行車路線，這名司機(jī)應(yīng)選擇哪條線路呢？假設(shè)貨柜車的運(yùn)行速度是恒定的，那么這一問題相當(dāng)于需要找到一條從甲地到乙地的最短路。旅行商問題（TSPtraveling salesman problem）一名推銷員準(zhǔn)備前往若干城市推銷產(chǎn)品。如何為他（她）設(shè)計(jì)一條最短的旅行路線（從駐地出發(fā)，經(jīng)過每個(gè)城市恰好一次，最后返回駐地？）最短路問題是組合優(yōu)化中的經(jīng)典問題，它是通過數(shù)學(xué)方法尋找離散時(shí)間的最優(yōu)編排、分組、次序、或篩選等，這類問題可用數(shù)學(xué)模型描述為 .其中，為目標(biāo)函數(shù)，為約束函數(shù)，為決策變量，表示有限個(gè)點(diǎn)組成的集合。一個(gè)組合最優(yōu)化問題可用三個(gè)參數(shù)表示，其中表示決策變量的定義域，表示可行解區(qū)域，中的任何一個(gè)元素

3、稱為該問題的可行解，表示目標(biāo)函數(shù)，滿足的可行解稱為該問題的最優(yōu)解。組合最優(yōu)化的特點(diǎn)是可行解集合為有限點(diǎn)集。由直觀可知，只要將中有限個(gè)點(diǎn)逐一判別是否滿足的約束并比較目標(biāo)值的大小，就可以得到該問題的最優(yōu)解。以上述TSP問題為例，具體闡述組合優(yōu)化問題：此模型研究對稱TSP問題,一個(gè)商人欲到個(gè)城市推銷產(chǎn)品，兩個(gè)城市和之間的距離，用數(shù)學(xué)模型描述為 ， ，約束條件決策變量表示商人行走的路線包含從城市到的路，而表示商人沒有選擇走這條路；的約束可以減少變量的個(gè)數(shù)，使得模型中共有個(gè)決策變量。每一個(gè)組合優(yōu)化問題都可以通過完全枚舉的方法求得最優(yōu)解。枚舉是以時(shí)間為代價(jià)的，在TSP問題中，用個(gè)城市的一個(gè)排列表示商人按這

4、個(gè)排列序推銷并返回起點(diǎn)。若固定一個(gè)城市為起終點(diǎn)，則需要個(gè)枚舉。以計(jì)算機(jī)可以完成個(gè)城市所有路徑枚舉為單位，則個(gè)城市的計(jì)算時(shí)間為：以第個(gè)城市為起點(diǎn)，第個(gè)到達(dá)城市有可能是第個(gè)、第個(gè)、第個(gè)城市。決定前兩個(gè)城市的順序后，余下是個(gè)城市的所有排列，枚舉這個(gè)城市的排列需要，所以，個(gè)城市的枚舉需要。類似地歸納，城市數(shù)與計(jì)算時(shí)間的關(guān)系如表1所示。表1 枚舉時(shí)城市數(shù)與計(jì)算時(shí)間的關(guān)系城市數(shù)2425262728293031計(jì)算時(shí)間天天年年通過表1可以看出，隨著城市數(shù)的增加，計(jì)算時(shí)間增加非常之快，當(dāng)城市數(shù)增加到30時(shí)，計(jì)算時(shí)間約為10.8年，實(shí)際計(jì)算中已無法承受。在城市數(shù)較多時(shí)，枚舉已不可取，我們可以采用一些別的方法縮短

5、計(jì)算時(shí)間。TSP問題是NP難問題，其可能的路徑數(shù)目與城市數(shù)目是成指數(shù)型增長的，所以一般很難求出其最優(yōu)解，因而一般是找出其有效的近似求解算法。遺傳算法可以用來解決一些較為復(fù)雜的系統(tǒng)問題，顯然旅行商問題是需要編碼運(yùn)算的，而遺傳算法本身的特征正好為解決這一問題提供了很好的途徑。NP問題：是指非確定多項(xiàng)式問題類。若存在一個(gè)多項(xiàng)式函數(shù)和一個(gè)驗(yàn)證算法，使得：判定問題的任何一個(gè)實(shí)例為“是”實(shí)例當(dāng)且僅當(dāng)存在一個(gè)驗(yàn)證字符串，滿足其輸入長度不超過，其中為的輸入長度，且算法驗(yàn)證實(shí)例為“是”實(shí)例的計(jì)算時(shí)間不超過,則稱判定問題是非確定多項(xiàng)式的。對于判定問題，若NP中的任何一個(gè)問題可在多項(xiàng)式時(shí)間內(nèi)歸約為判定問題，則稱為N

6、P難問題。二、 知識(shí)準(zhǔn)備根據(jù)實(shí)際需求，本文擬給出三種算法針對不同的情況做出解答。分別是基于圖論和網(wǎng)絡(luò)優(yōu)化的Dijkstra和FloydWarshall算法。這兩種算法用來解決起點(diǎn)與終點(diǎn)不重合的問題。最后根據(jù)現(xiàn)有智能優(yōu)化計(jì)算中的遺傳算法計(jì)算哈密爾頓回路問題，即起點(diǎn)與終點(diǎn)重合問題。1、 圖論基本知識(shí)有向圖的定義：一個(gè)有向圖是由一個(gè)非空有限集合和中某些元素的有序?qū)蠘?gòu)成的二元組，記為。其中稱為圖的頂點(diǎn)集，中的每一個(gè)元素，稱為該圖的一個(gè)頂點(diǎn)；稱為圖的弧集，記為，記有向圖（a） 和（c）是無向圖，（b）是有向圖2、 鄰接矩陣表示法圖的鄰接矩陣是如下定義的：是一個(gè)的0-1矩陣，即，也就是說，如果兩節(jié)點(diǎn)之

7、間有一條弧，則鄰接矩陣中對應(yīng)元素為1，否則為0.圖（a）和圖（b）的鄰接表矩陣即為3、 在計(jì)算機(jī)中用二維數(shù)組表示，兩節(jié)點(diǎn)之間有弧相應(yīng)的元素為1.必須指出的是：目前為止，一切最短路算法都只對不含負(fù)有向圈的網(wǎng)絡(luò)有效。實(shí)際上，對于含負(fù)有向圈的網(wǎng)絡(luò)，其最短路問題是NP-hard。因此，除非特別說明，一律假定網(wǎng)絡(luò)不包含負(fù)有向圈。此外在實(shí)際問題中也會(huì)遇到無向網(wǎng)絡(luò)上的最短路問題，這時(shí)原問題一般可以轉(zhuǎn)化為有向網(wǎng)絡(luò)中上的最短路問題。如果所有弧上的權(quán)全為非負(fù)數(shù)，只需將無向圖的一條邊代之以兩條對稱的有向弧即可。如果弧上的權(quán)有負(fù)有正，一般來說問題要復(fù)雜得多，要具體問題具體分析。本文中所要解決的問題都取權(quán)值為正，無向圖

8、皆采取兩條對稱的有向弧問題。，其中，與關(guān)聯(lián)，稱是圖的一條道路，為路長，頂點(diǎn)和分別稱為的起點(diǎn)和終點(diǎn)，而稱為他的內(nèi)部頂點(diǎn)。若道路的邊互不相同，則稱為跡。若道路的頂點(diǎn)互不相同，則稱為軌。稱一條道路是閉的，如果它有正的長且起點(diǎn)和終點(diǎn)相同。起點(diǎn)和終點(diǎn)重合的軌叫做圈(cycle)。若圖G 的兩個(gè)頂點(diǎn)u, v間存在道路，則稱u和v連通(connected)。u, v間的最短軌的長叫做u, v間的距離。記作d(u,v)。若圖G 的任二頂點(diǎn)均連通，則稱G 是連通圖。顯然有：(i)圖P 是一條軌的充要條件是P 是連通的，且有兩個(gè)一度的頂點(diǎn)，其余頂點(diǎn)的度為2；(ii)圖C 是一個(gè)圈的充要條件是C 是各頂點(diǎn)的度均為2

9、 的連通圖三、 應(yīng)用以行軍途中各目標(biāo)為圖G 的頂點(diǎn)，兩目標(biāo)之間的連線為圖G 相應(yīng)兩頂點(diǎn)間的邊，得圖G 。對G 的每一邊e，賦以一個(gè)實(shí)數(shù)w(e)兩目標(biāo)之間的距離長度，稱為e的權(quán)，得到賦權(quán)圖G 。G 的子圖的權(quán)是指子圖的各邊的權(quán)和。問題就是求賦權(quán)圖G 中指定的兩個(gè)頂點(diǎn)間的具最小權(quán)的軌。這條軌叫做間的最短路，它的權(quán)叫做間的距離，亦記作。四、 算法設(shè)計(jì)1 Dijkstra算法1.1 定義預(yù)覽：Dijkstra(迪杰斯特拉)算法是典型的單源最短路徑算法，用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。Dijkstra算法是很有代表性的最短路徑算法，注意

10、該算法要求圖中不存在負(fù)權(quán)邊。1.2 算法描述1) 算法思想：設(shè)G=(V,E)是一個(gè)帶權(quán)有向圖，把圖中頂點(diǎn)集合V分成兩組，第一組為已求出最短路徑的頂點(diǎn)集合（用S表示，初始時(shí)S中只有一個(gè)源點(diǎn)，以后每求得一條最短路徑 , 就將加入到集合S中，直到全部頂點(diǎn)都加入到S中，算法就結(jié)束了），第二組為其余未確定最短路徑的頂點(diǎn)集合（用U表示），按最短路徑長度的遞增次序依次把第二組的頂點(diǎn)加入S中。在加入的過程中，總保持從源點(diǎn)v到S中各頂點(diǎn)的最短路徑長度不大于從源點(diǎn)v到U中任何頂點(diǎn)的最短路徑長度。此外，每個(gè)頂點(diǎn)對應(yīng)一個(gè)距離，S中的頂點(diǎn)的距離就是從v到此頂點(diǎn)的最短路徑長度，U中的頂點(diǎn)的距離，是從v到此頂點(diǎn)只包括S中的

11、頂點(diǎn)為中間頂點(diǎn)的當(dāng)前最短路徑長度。2）算法步驟：a.初始時(shí)，S只包含源點(diǎn)，即Sv，v的距離為0。U包含除v外的其他頂點(diǎn)，即:U=其余頂點(diǎn)，若v與U中頂點(diǎn)u有邊，則<u,v>正常有權(quán)值，若u不是v的出邊鄰接點(diǎn)，則<u,v>權(quán)值為。b.從U中選取一個(gè)距離v最小的頂點(diǎn)k，把k加入S中（該選定的距離就是v到k的最短路徑長度）。c.以k為新考慮的中間點(diǎn)，修改U中各頂點(diǎn)的距離；若從源點(diǎn)v到頂點(diǎn)u的距離（經(jīng)過頂點(diǎn)k）比原來距離（不經(jīng)過頂點(diǎn)k）短，則修改頂點(diǎn)u的距離值，修改后的距離值的頂點(diǎn)k的距離加上邊上的權(quán)。d.重復(fù)步驟b和c直到所有頂點(diǎn)都包含在S中。3）算法實(shí)例圖1是5個(gè)節(jié)點(diǎn)的賦權(quán)

12、無向圖圖1 各節(jié)點(diǎn)之間的賦權(quán)無向圖 1 10 100 2 30 5 50 10 60 3 20 4圖1中有5個(gè)節(jié)點(diǎn)（），且是無向圖。每條弧有相應(yīng)的權(quán)值。編碼時(shí)若兩節(jié)點(diǎn)之間沒有弧，其相應(yīng)的權(quán)值用99999表示其代碼如下：int const MAXLENTH=50;int const MAX=99999;void Dijkstra(int n,int v,int *dist,int *prev,int cMAXLENTHMAXLENTH)/迪杰斯特拉算法，計(jì)算最短路徑bool sMAXLENTH;int i,j;for (i=1;i<=n;+i)disti=cvi;si=false;if(d

13、isti=MAX)previ=0;elseprevi=v;distv=0;sv=true;for (i=2;i<=n;+i)int t=MAX;int u=v;for (j=1;j<=n;+j)if (!sj)&&distj<t)u=j;t=distj;su=true;for (j=1;j<=n;+j) if(!sj)&&cuj<MAX) int newdist=distu+cuj; if (newdist<distj) distj=newdist; prevj=u; 輸入： 以二維數(shù)組的形式表示鄰接矩陣，即相應(yīng)的弧及其權(quán)值，

14、數(shù)組下標(biāo)表示弧。輸出： 最短路徑所經(jīng)過的節(jié)點(diǎn)及其距離值運(yùn)行實(shí)例，得到鄰接矩陣和最短路徑2 Floyd算法2.1 定義預(yù)覽Floyd-Warshall算法（Floyd-Warshall algorithm）是解決任意兩點(diǎn)間的最短路徑的一種算法，可以正確處理有向圖或負(fù)權(quán)的最短路徑問題，同時(shí)也被用于計(jì)算有向圖的傳遞閉包。Floyd-Warshall算法的時(shí)間復(fù)雜度為O(N3)，空間復(fù)雜度為O(N2)。2.2 算法描述1） 算法思想原理 Floyd算法是一個(gè)經(jīng)典的動(dòng)態(tài)規(guī)劃算法。用通俗的語言來描述的話，首先我們的目標(biāo)是尋找從點(diǎn)i到點(diǎn)j的最短路徑。從動(dòng)態(tài)規(guī)劃的角度看問題，我們需要為這個(gè)目標(biāo)重新做

15、一個(gè)詮釋（這個(gè)詮釋正是動(dòng)態(tài)規(guī)劃最富創(chuàng)造力的精華所在）從任意節(jié)點(diǎn)i到任意節(jié)點(diǎn)j的最短路徑不外乎2種可能，1是直接從i到j(luò)，2是從i經(jīng)過若干個(gè)節(jié)點(diǎn)k到j(luò)。所以，我們假設(shè)Dis(i,j)為節(jié)點(diǎn)u到節(jié)點(diǎn)v的最短路徑的距離，對于每一個(gè)節(jié)點(diǎn)k，我們檢查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立，如果成立，證明從i到k再到j(luò)的路徑比i直接到j(luò)的路徑短，我們便設(shè)置Dis(i,j) = Dis(i,k) + Dis(k,j)，這樣一來，當(dāng)我們遍歷完所有節(jié)點(diǎn)k，Dis(i,j)中記錄的便是i到j(luò)的最短路徑的距離。假設(shè)圖權(quán)的鄰接矩陣為，來存放各邊長度，其中： 之間沒有邊，在程序中以各

16、邊都不可能達(dá)到的充分大數(shù)代替 是之間邊的長度，。遞推產(chǎn)生一個(gè)矩陣序列，其中表示從頂點(diǎn)到頂點(diǎn)的路徑上所經(jīng)過的頂點(diǎn)序號(hào)不大于的最短路徑長度。計(jì)算時(shí)用迭代公式：是迭代次數(shù)，。最后，當(dāng)時(shí)，即是各頂點(diǎn)之間的最短通路值。2） 算法描述a.從任意一條單邊路徑開始。所有兩點(diǎn)之間的距離是邊的權(quán)，如果兩點(diǎn)之間沒有邊相連，則權(quán)為無窮大。 b.對于每一對頂點(diǎn) u 和 v，看看是否存在一個(gè)頂點(diǎn) w 使得從 u 到 w 再到 v 比己知的路徑更短。如果是更新它。3） 應(yīng)用已知有四點(diǎn)和它們之間的路徑如圖2所示圖2 賦權(quán)無向圖 1 10 3 2 7 4 9999 3 9999 4算法代碼實(shí)現(xiàn)void floyd(mgraph

17、 *g)/floyd算法處理矩陣int Amama,pathmama;int i,j,k;for(i=1;i<=g->n;i+)for (j=1;j<=g->n;j+)Aij=g->edgesij;pathij=-1;for(k=1;k<=g->n;k+)/先確定k點(diǎn)，找尋經(jīng)過k點(diǎn)的最短路徑的節(jié)點(diǎn)for(i=1;i<=g->n;i+)for(j=1;j<=g->n;j+)if(Aik!=0&&Akj!=0&&Aij>(Aik+Akj)Aij=Aik+Akj;pathij=k;cout<

18、<endl;cout<<"輸出最短路徑"<<endl;i=g->n;dispath(A,path,i);運(yùn)行結(jié)果如下3 遺傳算法3、1 算法簡介遺傳算法（Genetic Algorithms，簡稱 GA）是一種基于自然選擇原理和自然遺傳機(jī)制的搜索（尋優(yōu)）算法，它是模擬自然界中的生命進(jìn)化機(jī)制，在人工系統(tǒng)中實(shí)現(xiàn)特定目標(biāo)的優(yōu)化。遺傳算法的實(shí)質(zhì)是通過群體搜索技術(shù)，根據(jù)適者生存的原則逐代進(jìn)化，最終得到最優(yōu)解或準(zhǔn)最優(yōu)解。它必須做以下操作：初始群體的產(chǎn)生、求每一個(gè)體的適應(yīng)度、根據(jù)適者生存的原則選擇優(yōu)良個(gè)體（評估適應(yīng)度）、被選出的優(yōu)良個(gè)體兩兩配對，通過隨

19、機(jī)交叉其染色體的基因并隨機(jī)變異某些染色體的基因后生成下一代群體，按此方法使群體逐代進(jìn)化，直到滿足進(jìn)化終止條件。其實(shí)現(xiàn)方法如下：（1） 根據(jù)具體問題確定可行解域，確定一種編碼方法，能用數(shù)值串或字符串表示可行解域的每一解。（2） 對每一解應(yīng)有一個(gè)度量好壞的依據(jù)，它用一函數(shù)表示，叫做適應(yīng)度函數(shù)，適應(yīng)度函數(shù)應(yīng)為非負(fù)函數(shù)。（3） 確定進(jìn)化參數(shù)群體規(guī)模M 、交叉概率 、變異概率 、進(jìn)化終止條件。為便于計(jì)算，一般來說，每一代群體的個(gè)體數(shù)目都取相等。群體規(guī)模越大、越容易找到最優(yōu)解，但由于受到計(jì)算機(jī)的運(yùn)算能力的限制，群體規(guī)模越大，計(jì)算所需要的時(shí)間也相應(yīng)的增加。進(jìn)化終止條件指的是當(dāng)進(jìn)化到什么時(shí)候結(jié)束，它可以設(shè)定到

20、某一代進(jìn)化結(jié)束，也可能根據(jù)找出近似最優(yōu)是否滿足精度要求來確定。表1 列出了生物遺傳概念在遺傳算法中的對應(yīng)關(guān)系。表1 生物遺傳概念在遺傳算法中的對應(yīng)關(guān)系生物遺傳概念遺傳算法中的作用適者生存最優(yōu)目標(biāo)值的解有最大的可能被留住個(gè)體解染色體解的編碼（一條路徑包含若干個(gè)節(jié)點(diǎn)）基因解中每一分量的特征 （節(jié)點(diǎn)）適應(yīng)性適應(yīng)度函數(shù)值種群根據(jù)適應(yīng)度函數(shù)值選取的一組解交配通過交配原則產(chǎn)生一組新解的過程變異編碼的某一分量發(fā)生變化的過程 遺傳算法是一種數(shù)值求解的方法, 是一個(gè)有普適性的方法, 對目標(biāo)函數(shù)的性質(zhì)幾乎沒有要求, 甚至都不一定要顯式地寫出目標(biāo)函數(shù), 遺傳算法所具有的特點(diǎn)是記錄一個(gè)群體, 它可以記錄多個(gè)解。遺傳算

21、法在給問題的決策變量編碼后, 其計(jì)算過程是比較簡單的，且可以較快得到一個(gè)滿意解。3.2 遺傳算法的主要構(gòu)造過程圖 3 遺傳算法的主要構(gòu)造過程示意圖最優(yōu)化問題描述 第一步第二步確定決策變量、約束條件建立優(yōu)化模型目標(biāo)函數(shù)個(gè)體表現(xiàn)型X第五步第三步第四步確定適應(yīng)度轉(zhuǎn)換規(guī)則編碼方法解碼方法適應(yīng)度個(gè)體基因型X設(shè)計(jì)遺傳算子第六步確定運(yùn)行參數(shù)第七步遺 傳 算 法3.3 模型與算法應(yīng)用舉例：已知100個(gè)目標(biāo)的經(jīng)度、緯度如表2所示。表2 目標(biāo)經(jīng)度和緯度經(jīng)度緯度經(jīng)度緯度經(jīng)度緯度經(jīng)度緯度53.712115.304651.17580.032246.325328.275330.33136.934856.5432 21.4

22、18810.819816.252922.789123.104510.158412.481920.105015.45621.94510.205726.495122.122131.48478.964026.241818.176044.035613.540128.983625.987938.472220.173128.269429.001132.19105.869936.486329.72840.971828.14778.958624.663516.561823.614310.559715.117850.211110.29448.15199.532522.107518.55690.121518.87

23、2648.207716.888931.949917.63090.77320.465647.413423.778341.86713.566743.54743.906153.352426.752630.816513.459527.71335.070623.92227.630651.962122.851112.793815.73074.95688.366921.505124.090915.254827.21116.20705.144249.243016.704417.116820.035434.168822.75719.44023.920011.581214.567752.11810.40809.5

24、55911.421924.45096.563426.721328.566737.584816.847435.66199.933324.46543.16440.77756.957614.470313.636819.866015.12243.16164.242818.524514.359858.684927.148539.516816.937156.508913.709052.521115.795738.43008.464851.818123.10598.998323.644050.115623.781613.79091.951034.057423.396023.06248.431919.9857

25、5.790240.880114.297858.828914.522918.66356.743652.842327.288039.949429.51149.155624.066453.798927.266228.781227.66598.083127.67059.155614.130453.79890.219933.64900.39801.349616.835949.98166.082819.363517.662236.954523.026515.732019.569711.511817.388444.039816.263539.713928.42036.990923.180438.339219

26、.995024.654319.605736.998024.39924.15913.185340.140020.303023.98769.403041.108427.7149我方有一個(gè)基地，經(jīng)度和緯度為（70，40），假設(shè)我方有一部隊(duì)乘坐飛機(jī)從基地出發(fā)，偵察完所有目標(biāo)，再返回原來的基地。假設(shè)飛機(jī)的速度為1000公里/小時(shí)，到達(dá)每一目標(biāo)之后不做停留，求偵察完所有目標(biāo)之后花費(fèi)的時(shí)間。顯然這是一個(gè)旅行商問題。我們依次給基地編號(hào)為1，目標(biāo)依次編號(hào)為2，3，101,最后我方基地再重復(fù)編號(hào)為102。距離矩陣，其中表示兩點(diǎn)的距離，這里為實(shí)對稱矩陣。則問題就是，求一個(gè)從點(diǎn)1出發(fā)，走遍所有中間點(diǎn)，到達(dá)點(diǎn)102的一

27、個(gè)最短路徑。上面問題中給定的是地理坐標(biāo)（經(jīng)度和緯度），我們必須要求兩點(diǎn)間的實(shí)際距離。設(shè)兩點(diǎn)的地理坐標(biāo)為，過兩點(diǎn)的大圓的劣弧長即為兩點(diǎn)的實(shí)際距離。以地心為坐標(biāo)原點(diǎn)，以赤道平面為平面，以0度經(jīng)線圈所在的平面為平面建立三維直角坐標(biāo)系。則兩點(diǎn)的直角坐標(biāo)分別為：其中為地球半徑。兩點(diǎn)的實(shí)際距離，化簡得 。求解的遺傳算法的參數(shù)設(shè)定如下：種群大?。鹤畲蟠鷶?shù)：交叉率：，交叉概率為1能保證種群的充分進(jìn)化。 變異率：，一般而言，變異發(fā)生的可能性較小。（1） 編碼策略采用十進(jìn)制編碼，用隨機(jī)數(shù)列作為染色體，其中每一個(gè)隨機(jī)序列都和種群中的一個(gè)個(gè)體相對應(yīng)，例如一個(gè)9城市問題的一個(gè)染色體為其中編碼位置代表城市，位置的隨機(jī)數(shù)表

28、示城市在巡回中的順序，我們將這些隨機(jī)數(shù)按升序排列得到如下巡回：（2） 初始種群本文中我們先利用經(jīng)典的近似算法改良圈算法求得一個(gè)較好的初始種群。即對于初始圈，交換與之間的順序，此時(shí)的新路徑為：記，則以新的路徑修改舊的路徑，直到不能修改為止。（3） 目標(biāo)函數(shù)目標(biāo)函數(shù)為偵察所有目標(biāo)的路徑長度，適應(yīng)度函數(shù)就取為目標(biāo)函數(shù)，我們要求（4） 交叉操作我們的交叉操作采用單點(diǎn)交叉。設(shè)計(jì)如下，對于選定的兩個(gè)父代個(gè)體 ，我們隨機(jī)地選取第個(gè)基因處為交叉點(diǎn)，則經(jīng)過交叉運(yùn)算后得到的子代編碼為和，的基因由的前個(gè)基因和的后個(gè)基因構(gòu)成，的基因由的前個(gè)基因和的后個(gè)基因構(gòu)成，例如:設(shè)交叉點(diǎn)為第四個(gè)基因處，則交叉操作的方式有很多種選

29、擇，我們應(yīng)該盡可能選取好的交叉方式，保證子代能繼承父代的優(yōu)良特性。同時(shí)這里的交叉操作也蘊(yùn)含了變異操作。（5） 變異操作變異也是實(shí)現(xiàn)群體多樣性的一種手段，同時(shí)也是全局尋優(yōu)的保證。具體設(shè)計(jì)如下，按照給定的變異率，對選定變異的個(gè)體，隨機(jī)地取三個(gè)整數(shù)，滿足，把，之間（包括和）的基因段插到后面。（6） 選擇采用確定性的選擇策略，也就是說選擇目標(biāo)函數(shù)值最小的個(gè)個(gè)體進(jìn)化到下一代，這樣可以保證父代的優(yōu)良特性被保存下來。3.3 模型求解與結(jié)論經(jīng)由matlab編程可得path = Columns 1 through 16 1 17 3 45 67 72 14 27 48 82 2 92 87 83 74 30 C

30、olumns 17 through 32 20 42 15 51 80 50 9 60 40 18 10 84 97 31 79 77 Columns 33 through 48 85 65 64 11 76 69 94 70 19 63 62 26 29 34 66 90 Columns 49 through 64 86 8 39 78 88 61 49 28 57 47 23 58 81 25 68 7 Columns 65 through 80 22 71 37 32 13 24 16 91 41 4 73 33 75 5 54 53 Columns 81 through 96 12 8

31、9 6 96 55 44 38 98 100 56 21 99 101 52 46 59 Columns 97 through 102 93 43 36 35 95 102long = 4.0054e+04所花時(shí)間為40小時(shí)左右，其中一個(gè)偵察路徑圖如圖2所示圖2 偵察路徑圖 算法說明：輸入為各個(gè)目標(biāo)的地理坐標(biāo)，以文件的形式導(dǎo)入。load sj.txt %加載敵方100個(gè)目標(biāo)數(shù)據(jù)輸出為最優(yōu)路徑所經(jīng)過的各節(jié)點(diǎn)及其路徑圖五、 模型擴(kuò)展 遺傳算法作為現(xiàn)代優(yōu)化算法之一，其主要特點(diǎn)是對非線性極值問題能以概率1跳出局部最優(yōu)解，找到全局最優(yōu)解。而遺傳算法這種跳出局部最優(yōu)尋找全局最優(yōu)特性都基于算法中的交叉和變異

32、。在傳統(tǒng)遺傳算法的結(jié)構(gòu)中，變異操作在交叉操作基礎(chǔ)上進(jìn)行，強(qiáng)調(diào)的是交叉作用，認(rèn)為變異只是一個(gè)生物學(xué)背景機(jī)制。在具體交叉操作中，通常采用斷點(diǎn)交叉法（段交叉）多點(diǎn)交叉與均勻交叉，其中斷點(diǎn)交叉是指隨機(jī)地在基因序列中選擇一個(gè)斷點(diǎn)，然后交換雙親上斷點(diǎn)右端的所有染色體。在變異操作中，變異算子一般是用Guassian分布的隨機(jī)變異來實(shí)現(xiàn)。本文根據(jù)以上特點(diǎn)對基于求解最優(yōu)路徑規(guī)劃的遺傳算法進(jìn)行改進(jìn)，首先將變異操作從交叉操作中分離出來，使其成為獨(dú)立的并列于交叉的尋優(yōu)操作，在具體遺傳操作中，混沌與遺傳操作聯(lián)系在一起，在交叉操作中，以“門當(dāng)戶對”原則進(jìn)行個(gè)體配對，利用混沌序列確定交叉點(diǎn)，實(shí)行強(qiáng)度最弱的單點(diǎn)交叉，以確保算

33、法收斂精度，削弱和避免尋優(yōu)抖振問題：在變異操作中，利用混沌序列對染色體中多個(gè)基因進(jìn)行變異，以避免算法早熟（過早收斂于局部的最優(yōu)解，其原因?yàn)槿后w的規(guī)模是有限的，可以預(yù)見當(dāng)群體經(jīng)過若干代的進(jìn)化后，以指數(shù)級增長的具有較高平均適應(yīng)度的模式將在種群中占絕大多數(shù)，而其他的模式將迅速消失。）1、 模型及算法對交叉算子和變異算子做了如下兩點(diǎn)改進(jìn)。（1） 交叉操作交叉操作設(shè)計(jì)如下：首先以“門當(dāng)戶對”原則，對父代個(gè)體進(jìn)行配對，即對父代以適應(yīng)度函數(shù)（目標(biāo)函數(shù)）值進(jìn)行排序，目標(biāo)函數(shù)小的與小的配對，目標(biāo)函數(shù)大的與大的配對。然后利用混沌序列確定交叉點(diǎn)的位置，最后對確定的交叉項(xiàng)進(jìn)行交叉。例如配對，他們的染色體分別是，采用L

34、ogistic混沌序列產(chǎn)生一個(gè)2到101之間的正整數(shù)，具體步驟如下：取一個(gè)（0，1）隨機(jī)初始值，然后利用迭代一次產(chǎn)生1個(gè)（0，1）上的混沌值，保存以上混沌值作為產(chǎn)生下一代交叉項(xiàng)的混沌迭代初值，再把這個(gè)值分別乘以100并加上2，最后取整即可。假如這個(gè)數(shù)為33，那么我們對染色體中相應(yīng)的基因進(jìn)行交叉，得到新的染色體（2） 變異操作變異也是實(shí)現(xiàn)群體多樣性的一種手段，是跳出局部最優(yōu)，全局最優(yōu)的重要保證。在本文具體變異算子設(shè)計(jì)如下，首先根據(jù)給定的變異率，隨機(jī)地取兩個(gè)在2到101之間的整數(shù)，對這兩個(gè)數(shù)對應(yīng)位置的基因進(jìn)行變異，具體變異以當(dāng)前的基因值，從而得到新的染色體。2、 改進(jìn)的交叉算子和變異算子（1） 算

35、法代碼如下A=J;for k=1:dai %產(chǎn)生01之間隨機(jī)數(shù)列進(jìn)行編碼B=A;%交配產(chǎn)生子代Bfor i=1:2:wch0=rand;ch(1)=4*ch0*(1-ch0);for j=2:50ch(j)=4*ch(j-1)*(1-ch(j-1);endch=2+floor(100*ch);temp=B(i,ch);B(i,ch)=B(i+1,ch);B(i+1,ch)=temp;end%變異產(chǎn)生子代Cby=find(rand(1,w)<0.1);if length(by)=0by=floor(w*rand(1)+1;endC=A(by,:);L3=length(by);for j=1

36、:L3bw=2+floor(100*rand(1,3);bw=sort(bw);C(j,:)=C(j,1:bw(1)-1,bw(2)+1:bw(3),bw(1):bw(2),bw(3)+1:102);endG=A;B;C;TL=size(G,1);其運(yùn)行結(jié)果圖 2基于改進(jìn)的遺傳算法優(yōu)化路徑圖path = Columns 1 through 18 1 17 3 45 67 82 48 72 14 27 10 84 18 40 60 79 31 97 Columns 19 through 36 77 85 65 64 11 76 69 94 70 19 63 62 26 29 34 66 90 8

37、6 Columns 37 through 54 8 39 78 47 23 58 81 25 68 7 22 71 37 32 13 24 49 28 Columns 55 through 72 57 88 61 16 91 41 4 73 33 75 5 54 53 12 89 6 96 55 Columns 73 through 90 44 38 9 80 50 15 42 20 30 74 83 87 92 2 36 43 93 46 Columns 91 through 102 59 51 98 100 56 21 99 101 52 95 35 102long = 4.0886e+0

38、4六、 算法性能比較最優(yōu)路徑規(guī)劃問題是組合最優(yōu)化問題，但它不是多項(xiàng)式可解問題，即其目標(biāo)函數(shù)并不能用一個(gè)多項(xiàng)式函數(shù)表示。所以此類問題還沒有一個(gè)有能求得最優(yōu)解的多項(xiàng)式時(shí)間算法，它是NP-hard問題。但是我們可以通過一些算法找到它的近似最優(yōu)解。本文中的Dijkstra算法和Floyd-Warshall算法以及智能優(yōu)化遺傳算法都為解決這一類問題提供了很好的途徑。1）Dijkstra算法 局限性：該算法只適合求兩個(gè)指定頂點(diǎn)的最短路徑，且要求權(quán)值為正。 時(shí)間復(fù)雜度：O()2）Floyd-Warshall算法 局限性：時(shí)間效率低，對于多個(gè)節(jié)點(diǎn)之間的算法實(shí)現(xiàn)所需要的空間復(fù)雜度高。 時(shí)間復(fù)雜度：O()3）遺傳

39、算法 遺傳算法適合數(shù)值求解那些帶有多參數(shù)、多變量、多目標(biāo)和在多區(qū)域但連通性較差的NP -hard 優(yōu)化問題. 對多參數(shù)、多變量的NP-hard 優(yōu)化問題, 通過解析求解或是計(jì)算求最優(yōu)解的可能性很小, 主要依賴于數(shù)值求解. 遺傳算法是一種數(shù)值求解的方法, 是一個(gè)有普適性的方法, 對目標(biāo)函數(shù)的性質(zhì)幾乎沒有要求, 甚至都不一定要顯式地寫出目標(biāo)函數(shù), 因此用遺傳算法求解優(yōu)化問題不足為奇. 遺傳算法的實(shí)現(xiàn)效率依賴于算子的操作和編碼操作。時(shí)間復(fù)雜度則依賴于代數(shù)和種群大小。所以求解時(shí)對于算法的收斂性和收斂速度都要以依具體問題計(jì)算。ticclc,clearload sj.txt %加載敵方100個(gè)目標(biāo)數(shù)據(jù)x=sj(:,1:2:8);x=x(:)