遺傳算法在機(jī)器人路徑規(guī)劃中的應(yīng)用分析研究

1、畢業(yè)論文題目：遺傳算法在機(jī)器人路徑規(guī)劃中的應(yīng)用分析研究摘要移動(dòng)機(jī)器人路徑規(guī)劃作為自主式移動(dòng)機(jī)器人技術(shù)的一個(gè)重要組成部分，是研究移動(dòng)機(jī)器人技術(shù)較為活躍的課題之一，吸引了國(guó)內(nèi)外大批的研究學(xué)者。隨著各種新方法和新技術(shù)的不斷出現(xiàn)，對(duì)路徑規(guī)劃的研究有了更廣闊的天地。我國(guó)在智能移動(dòng)機(jī)器人研究方面雖然已經(jīng)取得了一定的成果，如地面自主導(dǎo)航車(chē)、水下自主機(jī)器人和飛行機(jī)器人等。但由于起步較晚，在研究和應(yīng)用方面都落后于一些西方國(guó)家，而且還沒(méi)有達(dá)到完全實(shí)用。因此，進(jìn)行這項(xiàng)研究，具有一定的理論和工程應(yīng)用意義。首先從移動(dòng)機(jī)器人的歷史和現(xiàn)狀出發(fā)，對(duì)比了國(guó)內(nèi)外的不同發(fā)展?fàn)顩r，對(duì)移動(dòng)機(jī)器人領(lǐng)域的研究方向進(jìn)行了綜述。著重介紹了移動(dòng)

2、機(jī)器人路徑規(guī)劃中常用的方法，對(duì)柵格法、遺傳算法等進(jìn)行了逐一的分析闡述。應(yīng)用于機(jī)器人路徑規(guī)劃的有很多傳統(tǒng)的優(yōu)化方法，本文主要介紹的最基本的一種算法-遺傳算法在機(jī)器人路徑規(guī)劃中的應(yīng)用。遺傳算法（簡(jiǎn)稱(chēng)ga）是一種借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)化的搜索算法，它將“適者生存”這一基本的達(dá)爾文進(jìn)化理論引入串結(jié)構(gòu)，并且在串之間進(jìn)行有組織但又隨機(jī)的信息交換，伴隨著算法的進(jìn)行，優(yōu)良的品質(zhì)被逐漸保留并加以組合，從而不斷產(chǎn)生出更佳的個(gè)體，也就是不斷地接近于最優(yōu)解。本文采取了柵格法對(duì)機(jī)器人工作空間進(jìn)行劃分，用序號(hào)標(biāo)識(shí)柵格，并以此序號(hào)作為機(jī)器人路徑規(guī)劃參數(shù)編碼。同時(shí)引入間斷無(wú)障礙路徑概念以簡(jiǎn)化初始種群產(chǎn)生，而且

3、采用了遺傳算法操作對(duì)初始路徑進(jìn)行尋優(yōu)，這里遺傳算法操作主要指的是選擇操作、交叉操作、變異操作；尋優(yōu)主要是選取適當(dāng)?shù)膫€(gè)體評(píng)價(jià)函數(shù)及適應(yīng)函數(shù)對(duì)路徑進(jìn)行尋優(yōu)。最后采用matlab對(duì)機(jī)器人路徑進(jìn)行仿真，靜態(tài)顯示進(jìn)化過(guò)程中生成的路徑并顯示機(jī)器人在障礙物存在情況下避障的運(yùn)動(dòng)過(guò)程。對(duì)不同參數(shù)設(shè)置下的路徑進(jìn)行比較，不同種群大小的適應(yīng)度值進(jìn)行統(tǒng)計(jì)分析，并將不同環(huán)境下的最佳路徑與最差路徑作比較。傳統(tǒng)優(yōu)化方法在機(jī)器人路徑規(guī)劃這類(lèi)復(fù)雜非線(xiàn)性?xún)?yōu)化問(wèn)題中缺乏足夠的魯棒性。遺傳算法是國(guó)際上80年代中期以來(lái)獲得廣泛應(yīng)用的一種新型參數(shù)優(yōu)化方法，它基于自然選擇原理和群體進(jìn)化機(jī)制，有許多區(qū)別于傳統(tǒng)優(yōu)化方法的特點(diǎn)，對(duì)機(jī)器人路徑尋優(yōu)效

4、果更明顯。關(guān)鍵詞 ：遺傳算法，機(jī)器人，路徑規(guī)劃，優(yōu)化abstract to be a important component of the independent -like migration robot technology, the motion robot way plan is one of more active topics of motion robot technology and has attracted large quantities of the domestic and foreign research scholar. with new method and n

5、ew technologys unceasing appearance, there is a broader world to research the way plan. although our country had already made certain progress in intelligent migration robot research aspect, such as ground autonomous navigation vehicle, submarine independent robot and flight robot and so on .but it

6、starts late, it falls behind some western country in the application aspect and has not achieved completely usability. therefore, it has certain theory and project application significance to conduct this research. firstly， from the history and the present situation of moved robot ，comparing the dom

7、estic and foreign different development condition , it starts the summary. from the research direction of migration robot. it introduces commonly used method in motion robot way plan emphatically, and has carried on the analysis elaboration one by one to the grid law, the genetic algorithm and so on

8、 applied to the plans in the robot way has many traditional optimized methods, this article mainly introduce the most basic one algorithm - genetic algorithm in the application of the robot way plan .the genetic algorithm (ga) is one kind which profits from the biosphere natural selection and the na

9、ture heredity mechanism randomisation searching algorithm, it introduces his basic darwin evolution theory of the survival of the fittest” to string structure, and carries on organized but the stochastic exchange of information between the strings. following algorithm advance, the fine quality is re

10、tained gradually and combined, thus produces a better individual unceasingly and also closes to the optimal solution unceasingly . the article adopts the method of grid work to divide robot space , with the serial numbers to identify grid, and as the parameters of code of robot path planning .and th

11、is paper introduces barrier-free path concept to simplify the initial population and using the genetic algorithm operation for the initial route optimization of genetic . the operations mainly refer to selection operation , crossover operation and variation operation. this paper mainly adopts indivi

12、dual evaluation function and the fitness function for optimal selection . finally using matlab to simulate robot path. traditional optimization methods which is used in this kind of complex nonlinear optimization problems lack of robustness. it displays the path of evolution statically and displays

13、the avoidance movement of the robot in the environment of obstacles .finally, different optimized paths under different parameters are compared; fitness values of various population sizes are statistically analyzed and best optimized paths and worst optimized paths in different environments are comp

14、ared as well. genetic algorithm is a new parameters optimization method which has won extensive application in the whole world since the middle of 1980s.it is based on natural selection principle and group evolution mechanism. there are many characteristics which are different from traditional optim

15、ization methods and has better effect in robot path optimization.key wordsgenetic algorithms, robot, path planning, optimize目錄摘要1英文摘要2第一章 緒論.61.1課題的研究背景.61.2國(guó)內(nèi)外路徑規(guī)劃發(fā)展?fàn)顩r.81.3路徑規(guī)劃解決的基本問(wèn)題.101.4論文主要研究?jī)?nèi)容（原理）概述.111.4.1遺傳算法的基本運(yùn)算過(guò)程如下.141.4.2路徑規(guī)劃的實(shí)現(xiàn).151.4.3 機(jī)器人路徑最優(yōu)化的實(shí)現(xiàn).151.5本章小結(jié).15第二章 機(jī)器人路徑規(guī)劃和遺傳算法162.1 路徑規(guī)劃研

16、究概述.162.1.1 路徑規(guī)劃分類(lèi).162.1.2 路徑規(guī)劃問(wèn)題特點(diǎn).162.1.3路徑規(guī)劃方法.172.1.4 優(yōu)化問(wèn)題1922遺傳算法192.2.1遺傳算法定義.192.2.2 遺傳算法特點(diǎn).192.2.3 編碼.202.2.4適應(yīng)度函數(shù).202.2.5初始群體的選取.21第三章基于遺傳算法的機(jī)器人路徑的優(yōu)化223.1.參數(shù)設(shè)定.223.2環(huán)境建模.223.3生成初始種群.233.4 適應(yīng)度函數(shù)設(shè)置.243.5 選擇操作.253.5.1 什么是輪盤(pán)賭選擇.263.6 交叉操作.283.7 終止條件.29第四章 仿真及結(jié)果分析.314.1 仿真程序.314.2 仿真結(jié)果及分析.35致謝38

17、參考文獻(xiàn).39圖列和表列圖1 交叉操作示意圖.13 圖2 變異操作示意圖. .14圖3 機(jī)器人路徑空間模型 . 22圖4 初始種群產(chǎn)生流程圖23圖5選擇操作得流程圖 26圖6轉(zhuǎn)盤(pán)法示意圖 27表1 10個(gè)染色體種群按比例的選擇過(guò)程 27圖7交叉操作示意圖. 28圖8整個(gè)優(yōu)化過(guò)程流程圖.30第一章 緒論1.1課題的研究背景現(xiàn)代機(jī)器人的研究始于20世紀(jì)中期，其技術(shù)背景是計(jì)算機(jī)和自動(dòng)化的發(fā)展，以及原子能的開(kāi)發(fā)利用。 自1946年第一臺(tái)數(shù)字電子計(jì)算機(jī)問(wèn)世以來(lái)，計(jì)算機(jī)取得了驚人的進(jìn)步，向高速度、大容量、低價(jià)格的方向發(fā)展。 大批量生產(chǎn)的迫切需求推動(dòng)了自動(dòng)化技術(shù)的進(jìn)展，其結(jié)果之一便是1952年數(shù)控機(jī)床的誕生

18、。與數(shù)控機(jī)床相關(guān)的控制、機(jī)械零件的研究又為機(jī)器人的開(kāi)發(fā)奠定了基礎(chǔ)。 另一方面，原子能實(shí)驗(yàn)室的惡劣環(huán)境要求某些操作機(jī)械代替人處理放射性物質(zhì)。在這一需求背景下，美國(guó)原子能委員會(huì)的阿爾貢研究所于1947年開(kāi)發(fā)了遙控機(jī)械手，1948年又開(kāi)發(fā)了機(jī)械式的主從機(jī)械手。 1954年美國(guó)戴沃爾最早提出了工業(yè)機(jī)器人的概念，并申請(qǐng)了專(zhuān)利。該專(zhuān)利的要點(diǎn)是借助伺服技術(shù)控制機(jī)器人的關(guān)節(jié)，利用人手對(duì)機(jī)器人進(jìn)行動(dòng)作示教，機(jī)器人能實(shí)現(xiàn)動(dòng)作的記錄和再現(xiàn)。這就是所謂的示教再現(xiàn)機(jī)器人?，F(xiàn)有的機(jī)器人差不多都采用這種控制方式。 作為機(jī)器人產(chǎn)品最早的實(shí)用機(jī)型是1962年美國(guó)amf公司推出的“verstran”和unimation公司推出的

19、“unimate”。這些工業(yè)機(jī)器人的控制方式與數(shù)控機(jī)床大致相似，但外形特征迥異，主要由類(lèi)似人的手和臂組成。 1965年，mit的roborts演示了第一個(gè)具有視覺(jué)傳感器的、能識(shí)別與定位簡(jiǎn)單積木的機(jī)器人系統(tǒng)。 1967年日本成立了人工手研究會(huì)（現(xiàn)改名為仿生機(jī)構(gòu)研究會(huì)），同年召開(kāi)了日本首屆機(jī)器人學(xué)術(shù)會(huì)。 1970年在美國(guó)召開(kāi)了第一屆國(guó)際工業(yè)機(jī)器人學(xué)術(shù)會(huì)議。1970年以后，機(jī)器人的研究得到迅速?gòu)V泛的普及。 1973年，辛辛那提米拉克隆公司的理查德豪恩制造了第一臺(tái)由小型計(jì)算機(jī)控制的工業(yè)機(jī)器人，它是液壓驅(qū)動(dòng)的，能提升的有效負(fù)載達(dá)45公斤。 到了1980年，工業(yè)機(jī)器人才真正在日本普及，故稱(chēng)該年為“機(jī)器人元

20、年”。 隨后，工業(yè)機(jī)器人在日本得到了巨大發(fā)展，日本也因此而贏(yíng)得了“機(jī)器人王國(guó)的美稱(chēng)”。 隨著計(jì)算機(jī)技術(shù)和人工智能技術(shù)的飛速發(fā)展，使機(jī)器人在功能和技術(shù)層次上有了很大的提高，移動(dòng)機(jī)器人和機(jī)器人的視覺(jué)和觸覺(jué)等技術(shù)就是典型的代表。由于這些技術(shù)的發(fā)展，推動(dòng)了機(jī)器人概念的延伸。80年代，將具有感覺(jué)、思考、決策和動(dòng)作能力的系統(tǒng)稱(chēng)為智能機(jī)器人，這是一個(gè)概括的、含義廣泛的概念。這一概念不但指導(dǎo)了機(jī)器人技術(shù)的研究和應(yīng)用，而且又賦予了機(jī)器人技術(shù)向深廣發(fā)展的巨大空間，水下機(jī)器人、空間機(jī)器人、空中機(jī)器人、地面機(jī)器人、微小型機(jī)器人等各種用途的機(jī)器人相繼問(wèn)世，許多夢(mèng)想成為了現(xiàn)實(shí)。將機(jī)器人的技術(shù)（如傳感技術(shù)、智能技術(shù)、控制技

21、術(shù)等）擴(kuò)散和滲透到各個(gè)領(lǐng)域形成了各式各樣的新機(jī)器機(jī)器人化機(jī)器。當(dāng)前與信息技術(shù)的交互和融合又產(chǎn)生了“軟件機(jī)器人”、“網(wǎng)絡(luò)機(jī)器人”的名稱(chēng)，這也說(shuō)明了機(jī)器人所具有的創(chuàng)新活力。機(jī)器人是20世紀(jì)人類(lèi)最偉大的發(fā)明之一，自60年代初問(wèn)世以來(lái)，經(jīng)歷40多年的發(fā)展已取得很大的進(jìn)步。機(jī)器人技術(shù)的出現(xiàn)和發(fā)展，不僅使傳統(tǒng)的工業(yè)生產(chǎn)面貌發(fā)生了根本性變化，而且對(duì)人類(lèi)社會(huì)產(chǎn)生深遠(yuǎn)的影響。目前工業(yè)機(jī)器人已走向成熟，而具有特定任務(wù)的機(jī)器人也開(kāi)始進(jìn)入實(shí)用化研究階段。這些機(jī)器人在工業(yè)生產(chǎn)、航天、軍事、交通、安全、醫(yī)療、老人和殘疾人服務(wù)等多個(gè)領(lǐng)域具有十分重要的應(yīng)用價(jià)值。在機(jī)器人研究的早期，機(jī)器人的結(jié)構(gòu)、運(yùn)動(dòng)學(xué)、控制和信息處理是研究的

22、重點(diǎn)。隨著機(jī)器人技術(shù)的發(fā)展，單個(gè)機(jī)器人的能力、魯棒性、可靠性、效率等都有很大的提升。一方面，人們希望機(jī)器人能完成一些復(fù)雜的、需要高效率的、并行完成的任務(wù)，但這些復(fù)雜的任務(wù)由單個(gè)機(jī)器人已很難完成，需要多個(gè)機(jī)器人組成的團(tuán)隊(duì)相互協(xié)調(diào)與合作共同完成，這導(dǎo)致了機(jī)器人的應(yīng)用方式從部件式單元應(yīng)用向系統(tǒng)式應(yīng)用的方向發(fā)展。另一方面，人們也希望通過(guò)多機(jī)器人間的協(xié)調(diào)與合作，來(lái)提高機(jī)器人系統(tǒng)在作業(yè)過(guò)程中的效率，進(jìn)而當(dāng)機(jī)器人工作環(huán)境發(fā)生變化或系統(tǒng)局部發(fā)生故障時(shí)，多機(jī)器人之間仍可通過(guò)本身具有的協(xié)調(diào)與合作關(guān)系完成預(yù)定的任務(wù)。如何組織由多個(gè)機(jī)器人構(gòu)成的群體系統(tǒng)，以及在這樣的群體系統(tǒng)中如何實(shí)現(xiàn)機(jī)器人的協(xié)調(diào)與合作已成為當(dāng)前機(jī)器人

23、學(xué)研究領(lǐng)域的一個(gè)新課題。80年代以來(lái)，多機(jī)器人系統(tǒng)憑借著比單個(gè)機(jī)器人更高的精度、剛度、承載能力和靈活性而進(jìn)入我們的生活中，從而引起了越來(lái)越廣泛的重視。隨著機(jī)器人向系統(tǒng)應(yīng)用的方向發(fā)展，人們提出了多機(jī)器人群體的組織和控制問(wèn)題，也就是多機(jī)器人協(xié)調(diào)合作問(wèn)題，并形成了協(xié)作機(jī)器人學(xué)。多機(jī)器人協(xié)調(diào)合作是多機(jī)器人系統(tǒng)中一個(gè)重要部分，可以使多機(jī)器人系統(tǒng)將整體優(yōu)勢(shì)發(fā)揮得淋漓盡致。多移動(dòng)機(jī)器人協(xié)調(diào)系統(tǒng)的研究是機(jī)器人技術(shù)發(fā)展的必然，也將隨著機(jī)器人應(yīng)用領(lǐng)域的迅速發(fā)展而越來(lái)越廣泛。機(jī)器人技術(shù)的發(fā)展科學(xué)技術(shù)共同發(fā)展的一個(gè)綜合性的結(jié)果，它的發(fā)展歸功于第二次世界大戰(zhàn)之后各國(guó)為加強(qiáng)了本國(guó)的經(jīng)濟(jì)的發(fā)展，就加強(qiáng)了經(jīng)濟(jì)的投入。比如說(shuō)日

24、本，戰(zhàn)后開(kāi)始進(jìn)行的汽車(chē)制造工業(yè)，那個(gè)時(shí)候由于人力的缺乏，它迫切需要一種機(jī)器人來(lái)進(jìn)行大批量的制造，提高生產(chǎn)效率降低人的勞動(dòng)強(qiáng)度，這是社會(huì)發(fā)展本身的一個(gè)需求。另一方面它也是生產(chǎn)力發(fā)展的必然結(jié)果，也是人類(lèi)自身發(fā)展的必然結(jié)果。隨著人類(lèi)的發(fā)展和社會(huì)發(fā)展，人們?cè)谔接懽匀?、改造自然、認(rèn)識(shí)自然的過(guò)程中越來(lái)越需要一種解放人類(lèi)的“奴隸”，這種“奴隸”能夠代替人們?nèi)氖聫?fù)雜和繁重的體力勞動(dòng)，實(shí)現(xiàn)人們對(duì)不可達(dá)世界的認(rèn)識(shí)和改造。這也是人們?cè)诳萍及l(fā)展過(guò)程中的一個(gè)客觀(guān)需要。那什么是機(jī)器人呢？機(jī)器人是具有一些類(lèi)似人的功能的機(jī)械電子裝置，或者叫自動(dòng)化裝置，它仍然是個(gè)機(jī)器，它有三個(gè)特點(diǎn)，一個(gè)是有類(lèi)人的功能，比如說(shuō)作業(yè)功能，感知功

25、能，行走功能，還能完成各種動(dòng)作，它還有一個(gè)特點(diǎn)是根據(jù)人的編程能自動(dòng)的工作，這里一個(gè)顯著的特點(diǎn)，就是它可以編程，改變它的工作、動(dòng)作、工作的對(duì)象，和工作的一些要求，它是人造的機(jī)器或機(jī)械電子裝置。但從完整的更為深遠(yuǎn)的機(jī)器人定義來(lái)看，應(yīng)該更強(qiáng)調(diào)機(jī)器人智能，所以人們又提出來(lái)機(jī)器人的定義是能夠感知環(huán)境，能夠有學(xué)習(xí)、情感和對(duì)外界一種邏輯判斷思維的這種機(jī)器。那么這給機(jī)器人提出來(lái)更高層次的要求.。機(jī)器人的發(fā)展有三個(gè)階段，那么也就是說(shuō)，我們習(xí)慣于把機(jī)器人分成三類(lèi)，一種是第一代機(jī)器人，那么也叫示教再現(xiàn)型機(jī)器人，它是通過(guò)一個(gè)計(jì)算機(jī)，來(lái)控制一個(gè)多自由度的一個(gè)機(jī)械，通過(guò)示教存儲(chǔ)程序和信息，工作時(shí)把信息讀取出來(lái)，然后發(fā)出指

26、令，這樣的話(huà)機(jī)器人可以重復(fù)的根據(jù)人當(dāng)時(shí)示教的結(jié)果，再現(xiàn)出這種動(dòng)作，比方說(shuō)汽車(chē)的點(diǎn)焊機(jī)器人，它只要把這個(gè)點(diǎn)焊的過(guò)程示教完以后，它總是重復(fù)這樣一種工作，它對(duì)于外界的環(huán)境沒(méi)有感知，這個(gè)力操作力的大小，這個(gè)工件存在不存在，焊的好與壞，它并不知道，那么實(shí)際上這種從第一代機(jī)器人，也就存在它這種缺陷，因此，在20世紀(jì)70年代后期，人們開(kāi)始研究第二代機(jī)器人，叫帶感覺(jué)的機(jī)器人，這種帶感覺(jué)的機(jī)器人是類(lèi)似人在某種功能的感覺(jué)，比如說(shuō)力覺(jué)、觸覺(jué)、滑覺(jué)、視覺(jué)、聽(tīng)覺(jué)和人進(jìn)行相類(lèi)比，有了各種各樣的感覺(jué)，比方說(shuō)在機(jī)器人抓一個(gè)物體的時(shí)候，它實(shí)際上力的大小能感覺(jué)出來(lái)，它能夠通過(guò)視覺(jué)，能夠去感受和識(shí)別它的形狀、大小、顏色。抓一個(gè)雞蛋

27、，它能通過(guò)一個(gè)觸覺(jué)，知道它的力的大小和滑動(dòng)的情況。 那么第三代機(jī)器人，也是我們機(jī)器人學(xué)中一個(gè)理想的所追求的最高級(jí)的階段，叫智能機(jī)器人，那么只要告訴它做什么，不用告訴它怎么去做，它就能完成運(yùn)動(dòng)，感知思維和人機(jī)通訊的這種功能和機(jī)能，那么這個(gè)目前的發(fā)展還是相對(duì)的只是在局部有這種智能的概念和含義，但真正完整意義的這種智能機(jī)器人實(shí)際上并沒(méi)有存在，而只是隨著我們不斷的科學(xué)技術(shù)的發(fā)展，智能的概念越來(lái)越豐富，它內(nèi)涵越來(lái)越寬。同時(shí)機(jī)器人能夠通過(guò)傳感器感知環(huán)境，并通過(guò)執(zhí)行器對(duì)環(huán)境起作用。機(jī)器人是現(xiàn)代科學(xué)技術(shù)發(fā)展的佼佼者，將在21世紀(jì)發(fā)揮出越來(lái)越重要的作用，使人類(lèi)的生產(chǎn)活動(dòng)和家庭生活發(fā)生巨大的變化。自從被譽(yù)為機(jī)器人

28、之父的著名科學(xué)家約瑟夫恩格爾伯格在1959年推出了世界上第一臺(tái)機(jī)器人以來(lái)，出現(xiàn)了形形色色的機(jī)器人，其中一些機(jī)器人由于功能獨(dú)特而引人注目。隨著機(jī)器人在工業(yè)領(lǐng)域的應(yīng)用越來(lái)越廣泛，與外界環(huán)境交互的能力要求也在提高，機(jī)器人需要解決以下幾個(gè)問(wèn)題，分別為確定在哪，應(yīng)該去哪，以及怎么到達(dá)那里。最后一個(gè)問(wèn)題，機(jī)器人怎么到達(dá)哪里的需求就是所謂的路徑規(guī)劃問(wèn)題，它是機(jī)器人研究領(lǐng)域中的一個(gè)重要分支，主要是指如何獲得外部環(huán)境信息，在其工作空間中找到一條從起始狀態(tài)到目標(biāo)狀態(tài)的能避開(kāi)障礙物的路徑。移動(dòng)機(jī)器人的路徑規(guī)劃是一種比較復(fù)雜的帶約束條件的優(yōu)化問(wèn)題，而遺傳算法能夠模仿自然選擇與適者生存的生物進(jìn)化過(guò)程，是求解優(yōu)化問(wèn)題的一

29、種有效方法。采用遺傳算法對(duì)移動(dòng)機(jī)器人進(jìn)行路徑規(guī)劃時(shí)，具體算法的路徑編碼機(jī)制，將直接影響算法的實(shí)現(xiàn)和代碼的運(yùn)行效率針對(duì)移動(dòng)機(jī)器人不同的工作環(huán)境和具體特點(diǎn)，現(xiàn)已提出了多種基于定長(zhǎng)編碼或動(dòng)態(tài)編碼的機(jī)制本文提出了一種基于柵格的十進(jìn)制路徑編碼機(jī)制，使得障礙物的辨識(shí)以及遺傳算法的實(shí)現(xiàn)更為簡(jiǎn)單，增強(qiáng)了算法的通用性。自主導(dǎo)航是機(jī)器人相關(guān)技術(shù)的研究核心之一，而路徑規(guī)劃是移動(dòng)機(jī)器人自主導(dǎo)航的基本環(huán)節(jié)之一，對(duì)于真正實(shí)現(xiàn)機(jī)器人自主導(dǎo)航非常關(guān)鍵，因此本文將重點(diǎn)研究多機(jī)器人的路徑規(guī)劃問(wèn)題。機(jī)器人路徑規(guī)劃主要解決個(gè)問(wèn)題：（）使機(jī)器人能從初始點(diǎn)運(yùn)動(dòng)到目標(biāo)點(diǎn)；（）用一定的算法使機(jī)器人能繞開(kāi)障礙物，并且經(jīng)過(guò)某些必須經(jīng)過(guò)的點(diǎn)；（）

30、在完成以上任務(wù)的前提下，盡量?jī)?yōu)化機(jī)器人運(yùn)行軌跡。1.2國(guó)內(nèi)外路徑規(guī)劃發(fā)展?fàn)顩r機(jī)器人路徑規(guī)劃的研究始于20世紀(jì)70年代，就目前來(lái)看，機(jī)器人的發(fā)展仍然處于初級(jí)的階段，需要去完成的工作仍然很多，特別是在許多具體的環(huán)境中仍要具體問(wèn)題具體分析。在機(jī)器人中有一類(lèi)機(jī)器人叫做進(jìn)化機(jī)器人，它用進(jìn)化算法來(lái)實(shí)現(xiàn)機(jī)器人控制、機(jī)構(gòu)等方面的優(yōu)化，在路徑規(guī)劃運(yùn)用中，主要是能夠進(jìn)化出合適的運(yùn)動(dòng)軌跡。自從提出遺傳規(guī)劃以來(lái)，遺傳規(guī)劃已經(jīng)在許多方面得到了應(yīng)用，如纏繞的螺旋線(xiàn)的分辨，圖像壓縮，符號(hào)回歸等問(wèn)題。遺傳規(guī)劃在機(jī)器人路徑規(guī)劃中的應(yīng)用也是國(guó)外許多學(xué)者研究的目標(biāo)，并且己經(jīng)出現(xiàn)了許多令人興奮的成果。其中比較早，影響也比較大的是人工

31、螞蟻的問(wèn)題，這些應(yīng)用遺傳規(guī)劃來(lái)規(guī)劃路徑的螞蟻能夠自主地尋找食物并吃掉食物，而且能夠避開(kāi)障礙。除了人工螞蟻問(wèn)題外還有割草機(jī)問(wèn)題，在割草機(jī)問(wèn)題中，割草機(jī)必須要在執(zhí)行一次程序后割草機(jī)才能夠到達(dá)正方形草坪的每一個(gè)部分。其環(huán)境及任務(wù)與人工螞蟻問(wèn)題的環(huán)境基本相似。 移動(dòng)機(jī)器人的路徑規(guī)劃問(wèn)題已經(jīng)研究了很長(zhǎng)時(shí)間，也產(chǎn)生了很多方法，如全局-空間法、人工勢(shì)場(chǎng)法以及人工神經(jīng)網(wǎng)絡(luò)法每一種方法都具有各自的優(yōu)點(diǎn)；但總的看來(lái)，以上方法都或多或少地存在著一些問(wèn)題，如算法計(jì)算量大、容易陷入局部最優(yōu)解以及自適應(yīng)能力差作為優(yōu)化算法中的一種，遺傳算法在許多優(yōu)化問(wèn)題中得到了廣泛應(yīng)用并取得了很好效果近年來(lái)，遺傳算法同樣被應(yīng)用于移動(dòng)機(jī)器入

32、的路徑規(guī)劃問(wèn)題中目前有專(zhuān)家利用經(jīng)典遺傳算法對(duì)移動(dòng)機(jī)器人進(jìn)行路徑規(guī)劃，它采用固定長(zhǎng)發(fā)的二進(jìn)制編碼方式，遺傳算子也只有交叉和變異兩種雖然然該方法具有一定的自適應(yīng)性，但其在使用過(guò)程中必須滿(mǎn)足一個(gè)約束條件，那就是沿著所規(guī)劃出的路徑前進(jìn)，其路徑中各點(diǎn)橫坐標(biāo)（或縱坐標(biāo)）必須是單調(diào)上升的后來(lái)又有專(zhuān)家提出了一種自適應(yīng)移動(dòng)機(jī)器人路徑規(guī)劃算法，它采用變長(zhǎng)度的實(shí)數(shù)編碼方式，將路徑中每個(gè)點(diǎn)的橫、縱坐標(biāo)和該點(diǎn)的連通性信息作為基因進(jìn)行編碼，其適應(yīng)度函數(shù)則考慮了多個(gè)性能指標(biāo)，如路徑的長(zhǎng)度、路徑的光滑性以及路徑的安全性針對(duì)路徑規(guī)劃問(wèn)題的特點(diǎn)，該算法專(zhuān)門(mén)設(shè)計(jì)了八種遺傳箅子，而且這八種算子還能根據(jù)進(jìn)化過(guò)程中環(huán)境特點(diǎn)以及約束指標(biāo)的

33、變化自適應(yīng)地調(diào)節(jié)自身的使用概率從內(nèi)容上看，該算法似乎比較完美。但這是以大量的數(shù)值計(jì)算為代價(jià)的后來(lái)又有專(zhuān)家采用變長(zhǎng)度的二進(jìn)制編碼方式，它將機(jī)器人下一步的運(yùn)行方向和運(yùn)行距離作為基因進(jìn)行編碼，同以上研究方法相比并沒(méi)有大的改進(jìn)再后來(lái)又有學(xué)者提出了一種直接將路徑中各點(diǎn)編號(hào)進(jìn)行整數(shù)編碼的變長(zhǎng)度編碼方式。并設(shè)計(jì)了六種遺傳算子，該算法具有搜索速度較快，搜索質(zhì)量較高等優(yōu)點(diǎn)研究發(fā)現(xiàn)，該算法還存在著以下三個(gè)主要問(wèn)題需要改進(jìn)：(1)初始種群的產(chǎn)生方式有待于進(jìn)一步研究；(2)基于啟發(fā)式知識(shí)的遺傳算子需要進(jìn)一步設(shè)計(jì)；(3）遺傳算子的使用概率應(yīng)能夠在線(xiàn)調(diào)節(jié) 國(guó)內(nèi)外對(duì)自主移動(dòng)機(jī)器人的導(dǎo)航和避障問(wèn)題己經(jīng)做了大量的研究工作，比如

34、哈爾濱工業(yè)大學(xué)機(jī)器人研究所在1996年11月研制成功一個(gè)“導(dǎo)游小姐”，該機(jī)器人能夠?qū)崿F(xiàn)避障和自主路徑規(guī)劃，識(shí)別障礙物的類(lèi)型，具有一定的語(yǔ)音功能，具有極強(qiáng)的遙控功能。這個(gè)機(jī)器人能夠根據(jù)傳感器信息自主規(guī)劃路徑，由行走部分、行使控制器、顯示器、語(yǔ)音識(shí)別系統(tǒng)和大量的傳感器組成。行走部分采用差速驅(qū)動(dòng)的方式。既可以在線(xiàn)仿真，也可以顯示機(jī)器人行走的路徑和某個(gè)時(shí)刻導(dǎo)游機(jī)器人所在的位置。大面積寬闊地面的清掃工作一直是一項(xiàng)繁重的體力勞動(dòng)，人工清掃費(fèi)時(shí)、費(fèi)力且工作效率低，將機(jī)器人用于清掃服務(wù)，具有廣闊的應(yīng)用前景。為實(shí)現(xiàn)適合我國(guó)國(guó)情的寬闊地面自動(dòng)清掃，清華大學(xué)與香港中文大學(xué)合作，聯(lián)合研制開(kāi)發(fā)出一種全方位移動(dòng)清掃機(jī)器人

35、。國(guó)內(nèi)在遺傳規(guī)劃方面研究主要是西安建筑科技大學(xué)，云慶夏教授編寫(xiě)的進(jìn)化算法比較詳細(xì)介紹了遺傳規(guī)劃相關(guān)內(nèi)容。另外，上海交通大學(xué)自動(dòng)化所利用+語(yǔ)言也對(duì)該算法在機(jī)器人沿墻移動(dòng)問(wèn)題進(jìn)行了仿真實(shí)驗(yàn)，通過(guò)對(duì)移動(dòng)機(jī)器入的行為策略進(jìn)行符號(hào)型編碼，然后對(duì)這些策略的組合（gp算法個(gè)體）進(jìn)行自然選擇，優(yōu)勝劣汰，最后進(jìn)化出滿(mǎn)足任務(wù)需要的優(yōu)良個(gè)體，這些個(gè)體實(shí)際上就是機(jī)器人沿墻移動(dòng)的一系列指令有序組合最后的仿真結(jié)果說(shuō)明了應(yīng)用gp算法來(lái)演化移動(dòng)機(jī)器人沿墻走行為的有效性。 近年來(lái)，自主式水下機(jī)器人由于其在海底資源探測(cè)上的優(yōu)勢(shì)而受到各國(guó)的關(guān)注，但因?yàn)樗颅h(huán)境十分復(fù)雜導(dǎo)致一般的規(guī)劃方法都難以奏效，而水下環(huán)境的擁擠程度相對(duì)較低，機(jī)器

36、人工作在同一區(qū)域的可能性較大這一特征恰好有利于基于事例的規(guī)劃方法的應(yīng)用，因此該方法被廣泛的用于解決水下機(jī)器入的路徑規(guī)劃問(wèn)題.目前對(duì)機(jī)器人路徑規(guī)劃這一問(wèn)題的研究仍十分活躍，許多學(xué)者仍在繼續(xù)做大量的研究工作。1.3路徑規(guī)劃解決的基本問(wèn)題 路徑規(guī)劃是機(jī)器人技術(shù)研究領(lǐng)域中的核心問(wèn)題之一，也是機(jī)器人學(xué)中研究人工智能問(wèn)題的一個(gè)重要的方面。路徑規(guī)劃的主要任務(wù)是在機(jī)器人所在的環(huán)境中尋求一條從已知起點(diǎn)到已知終點(diǎn)的最低代價(jià)的無(wú)碰撞路徑. 路徑規(guī)劃技術(shù)是機(jī)器人研究領(lǐng)域的一個(gè)重要分支。所謂機(jī)器人的最優(yōu)路徑規(guī)劃問(wèn)題，就是依據(jù)某個(gè)或某些優(yōu)化準(zhǔn)則（如工作代價(jià)最小、行走路線(xiàn)最短、行走時(shí)間最短等），在其工作空間中找到一條從起始

37、狀態(tài)到目標(biāo)狀態(tài)的能避開(kāi)障礙物的最優(yōu)路徑。根據(jù)控制方法的不同，機(jī)器人路徑規(guī)劃方法大致可以分為兩類(lèi)：傳統(tǒng)方法和智能方法。移動(dòng)機(jī)器人的路徑規(guī)劃是移動(dòng)機(jī)器人研究領(lǐng)域中非常重要的問(wèn)題，總的控制目標(biāo)是使移動(dòng)機(jī)器人運(yùn)動(dòng)到目標(biāo)點(diǎn)，總的約束是在整個(gè)過(guò)程中，機(jī)器人不碰到任何一個(gè)障礙物。該問(wèn)題根據(jù)對(duì)環(huán)境信息的掌握程度可以分為兩類(lèi)：一類(lèi)是環(huán)境信息已知的全局規(guī)劃，另一類(lèi)是環(huán)境信息未知的局部規(guī)劃。全局規(guī)劃方法依照已獲取的環(huán)境信息，給機(jī)器人規(guī)劃出一條路徑。規(guī)劃路徑的精確程度取決于獲取環(huán)境信息的準(zhǔn)確程度。全局方法通常可以尋找最優(yōu)解，但是需要預(yù)先知道環(huán)境的準(zhǔn)確信息，并且計(jì)算量很大。局部規(guī)劃方法側(cè)重于考慮機(jī)器人當(dāng)前的局部環(huán)境信息

38、，讓機(jī)器人具有良好的避碰能力。很多機(jī)器人導(dǎo)航方法通常是局部的方法，因?yàn)樗男畔@取僅僅依靠傳感器系統(tǒng)獲取的信息，并且隨著環(huán)境的變化實(shí)時(shí)的發(fā)生變化。和全局規(guī)劃方法相比較，局部規(guī)劃方法更具有實(shí)時(shí)性和實(shí)用性。缺陷是僅僅依靠局部信息，有時(shí)會(huì)產(chǎn)生局部極點(diǎn)，無(wú)法保證機(jī)器人能順利到達(dá)目的地。根據(jù)機(jī)器人對(duì)環(huán)境信息知道的程度不同可分為兩種類(lèi)型。環(huán)境信息完全知道的全局路徑規(guī)劃和環(huán)境信息完全未知或部分未知的局部路徑規(guī)劃。對(duì)于環(huán)境信息完全知道的情況到目前為止已經(jīng)有許多解決方法，例如勢(shì)場(chǎng)法。人工勢(shì)場(chǎng)法的基本思想是將機(jī)器人在環(huán)境中的運(yùn)動(dòng)視為一種虛擬的人工受力場(chǎng)中的運(yùn)動(dòng)。障礙物對(duì)機(jī)器人產(chǎn)生斥力.目標(biāo)點(diǎn)對(duì)機(jī)器人產(chǎn)生引力，斥力

39、和引力的合力控制機(jī)器人的運(yùn)動(dòng)。該方法結(jié)構(gòu)簡(jiǎn)單，易于實(shí)現(xiàn).，得到廣泛應(yīng)用.但有幾個(gè)主要缺陷：存在陷阱區(qū)，在相近的障礙物面前不能發(fā)現(xiàn)路徑；在障礙物面前振蕩。在實(shí)際應(yīng)用中，機(jī)器人的工作環(huán)境多數(shù)是處于兩種極端情況之間的，即環(huán)境信息部分未知。例如在自動(dòng)化車(chē)間，一方面環(huán)境的整體布局已知(如車(chē)間結(jié)構(gòu)，固定設(shè)備），另一方面環(huán)境中存在著不可預(yù)知的障礙物(如其它機(jī)器人、臨時(shí)堆放的物品)。本文主要研究移動(dòng)機(jī)器人在 靜態(tài)環(huán)境中的路徑規(guī)劃問(wèn)題。本文只進(jìn)行路徑規(guī)劃問(wèn)題的研究，而不考慮軌跡跟蹤問(wèn)題，簡(jiǎn)單講就是研究如何在含有障礙的環(huán)境空間中為機(jī)器人規(guī)劃出一條從起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最短無(wú)障礙路徑。構(gòu)型空間法是目前研究移動(dòng)機(jī)器人

40、路徑規(guī)劃的一個(gè)基本工具，其基本思想是用構(gòu)型空 間中的一個(gè)點(diǎn)來(lái)表征移動(dòng)機(jī)器人的位置與方向目前最常用的方法是可視圖法。即在一個(gè)無(wú)向圖中，將移動(dòng)機(jī)器人的起始點(diǎn)與終止點(diǎn)以及移動(dòng)機(jī)器人運(yùn)動(dòng)環(huán)境中各障礙物的頂點(diǎn)表征為點(diǎn) 的形式，從而移動(dòng)機(jī)器人的有效路徑就是這樣的一些點(diǎn)之間與障礙物不相交的相互連接的線(xiàn)段。一個(gè)好的路徑規(guī)劃方法需要滿(mǎn)足如下指標(biāo)：（1）合理性返回的任何路徑都是合理的，或者說(shuō)任何路徑對(duì)控制機(jī)器人運(yùn)動(dòng)都是可執(zhí)行的。（2）完備性如果客觀(guān)上存在一條從起點(diǎn)到達(dá)終點(diǎn)的無(wú)碰路徑，該算法一定能找到； 如果環(huán)境中沒(méi)有路徑可通行，會(huì)報(bào)告規(guī)劃失敗。（3）最優(yōu)性算法規(guī)劃的結(jié)果路徑在某個(gè)測(cè)度（如時(shí)間、距離、能量消耗等）上

41、是最優(yōu)的。（4）實(shí)時(shí)性規(guī)劃算法的復(fù)雜度（時(shí)間需求、存儲(chǔ)需求等）能滿(mǎn)足機(jī)器人運(yùn)動(dòng)的需要（5）環(huán)境變化適應(yīng)性算法具有適應(yīng)環(huán)境動(dòng)態(tài)改變的能力，隨著環(huán)境改變，不必全部重新計(jì)算。（6）滿(mǎn)足約束支持移動(dòng)機(jī)器人運(yùn)動(dòng)時(shí)的完整性和非完整性運(yùn)動(dòng)約束。機(jī)器人路徑規(guī)劃研究一般涉及到環(huán)境表達(dá)、規(guī)劃方法、路徑執(zhí)行個(gè)方面，從而產(chǎn)生以下四個(gè)相關(guān)問(wèn)題：（1）機(jī)器人如何從環(huán)境中有效的獲取周?chē)恼系K信息和其它相關(guān)信息。（2）機(jī)器人如何根據(jù)內(nèi)部及外部傳感器來(lái)回答當(dāng)前處于地圖中什么位置。（3）機(jī)器人如何根據(jù)其處于當(dāng)前地圖的位置和當(dāng)前地圖中信息確定行動(dòng)策略。（4）如何產(chǎn)生合適的驅(qū)動(dòng)信號(hào)使機(jī)器人運(yùn)動(dòng)在預(yù)定的軌跡上。為了解決這些問(wèn)題，機(jī)器人

42、需要具備以下四個(gè)相關(guān)的技術(shù)：（1）傳感技術(shù)。機(jī)器人通過(guò)傳感器設(shè)備檢測(cè)收集外部環(huán)境的信息，建立環(huán)境的全局地圖和得到用于局部避障障礙物信息。（2）自定位技術(shù)。如果沒(méi)有機(jī)器人的當(dāng)前位置信息，也就沒(méi)有局部坐標(biāo)系在地圖坐標(biāo)系中的位置，從而無(wú)法進(jìn)行運(yùn)動(dòng)的規(guī)劃。（3）運(yùn)動(dòng)控制?？刂茩C(jī)器人按照設(shè)定的路徑行走，涉及到機(jī)器人的結(jié)構(gòu)、運(yùn)動(dòng)學(xué)和動(dòng)力學(xué)性質(zhì)。（4）規(guī)劃和決策。規(guī)劃部分是智能機(jī)器人的智能部分，規(guī)劃的大部分創(chuàng)新技術(shù)可以分為任務(wù)規(guī)劃和運(yùn)動(dòng)規(guī)劃，運(yùn)動(dòng)規(guī)劃又分為路徑規(guī)劃利軌跡規(guī)劃， 本文重點(diǎn)討論如何解決規(guī)劃與決策問(wèn)題，該操作的前提是要對(duì)機(jī)器人當(dāng)前所處的全局或局部環(huán)境建造模型。1.4論文主要研究?jī)?nèi)容（原理）概述對(duì)于

43、路徑規(guī)劃的研究已經(jīng)有很多方法，其中不乏基于遺傳算法的研究方法，但往往是針對(duì)靜態(tài)或動(dòng)態(tài)的某一種狀態(tài)，全局或局部的某一種，兩者結(jié)合的研究比較少見(jiàn)，同時(shí)目標(biāo)函數(shù)一般也只是取路徑最短一項(xiàng)標(biāo)準(zhǔn)。多目標(biāo)考慮的方案不多。本文主要解決的問(wèn)題是在靜態(tài)環(huán)境狀態(tài)下，運(yùn)用遺傳算法，實(shí)現(xiàn)路徑的規(guī)劃問(wèn)題，找出可行路徑，并實(shí)現(xiàn)優(yōu)化。研究的重點(diǎn)是解決路徑的歸劃問(wèn)題，先考慮找到可行路徑，后考慮路徑效果。 路徑規(guī)劃是指移動(dòng)機(jī)器人按照某一性能指標(biāo)（如距離、時(shí)間、能量等）搜索一條從起始狀態(tài)到目標(biāo)狀態(tài)的最優(yōu)路徑。在機(jī)器人學(xué)領(lǐng)域，路徑規(guī)劃是最基本同時(shí)也是最重要的研究課題之一作為機(jī)器智能的一部分，它的任務(wù)就是使機(jī)器人在其工作環(huán)境中能夠自主

44、的從起始點(diǎn)運(yùn)動(dòng)到目標(biāo)點(diǎn)同時(shí)滿(mǎn)足一定的約束條件這些約束條件包括但不限于：(1)不與障礙物碰撞；(2)運(yùn)動(dòng)路徑最短；(3)盡量遠(yuǎn)離障礙物；(4)機(jī)器人耗費(fèi)能量最?。?5)運(yùn)動(dòng)軌跡包含某些設(shè)定的必經(jīng)路點(diǎn)?；诓煌幕舅枷?，有多種算法出現(xiàn)。包括有人工勢(shì)場(chǎng)法（apf）、臭蟲(chóng)法（bug）、隨機(jī)位圖法（prm、快速隨機(jī)樹(shù)（rrt）、神經(jīng)網(wǎng)絡(luò)法cnn）等。這些算法都在不同的方面有著各自的優(yōu)勢(shì)，然而在總體上，這些路徑規(guī)劃算法都還存在各自的不足。如計(jì)算復(fù)雜度局部最優(yōu)解，地圖適應(yīng)性，動(dòng)態(tài)環(huán)境下有效性，全局及多目標(biāo)優(yōu)化能力。隨著遺傳算法（ga）的提出,機(jī)器人路徑規(guī)劃算法也得到相應(yīng)的發(fā)展。通過(guò)ga在路徑規(guī)劃中的應(yīng)用，

45、使得機(jī)器人更加的智能，其運(yùn)行路徑也更加逼近理想的優(yōu)化要求。尤其是其優(yōu)秀的全局優(yōu)化能力和較高的搜索效率使得成為處理復(fù)雜環(huán)境下全局優(yōu)化要求的最佳算法之一。遺傳算法是模擬自然界生物進(jìn)化過(guò)程與機(jī)制求解極值問(wèn)題的一類(lèi)自組織、自適應(yīng)人工智能技術(shù)。他是建立在自然遺傳學(xué)機(jī)理基礎(chǔ)上的迭代自適應(yīng)概率性搜索算法，具有堅(jiān)實(shí)的生物學(xué)基礎(chǔ)。遺傳算法的工作原理為：遺傳算法的基本思想來(lái)源于達(dá)爾文的進(jìn)化論和門(mén)德?tīng)柕倪z傳學(xué)說(shuō)，它是以生物進(jìn)化的高度抽象模型為基礎(chǔ)的自適應(yīng)搜索策略，基于自然選擇和自然遺傳這種生物進(jìn)化機(jī)制，把待優(yōu)化問(wèn)題的解的搜索空間映射為遺傳空間，把每一可能的解編碼為一個(gè)稱(chēng)為染色體的二進(jìn)制串（編碼的方法很多，如：二進(jìn)制

46、編碼；浮點(diǎn)數(shù)編碼；參數(shù)動(dòng)態(tài)編碼；有序串編碼），染色體的每一位稱(chēng)為基因，每個(gè)染色體（對(duì)應(yīng)一個(gè)個(gè)體）代表一個(gè)解，遺傳算法首先隨機(jī)地產(chǎn)生若干代表優(yōu)化問(wèn)題侯選解的一個(gè)群體，按照預(yù)先根據(jù)目標(biāo)函數(shù)確定的適應(yīng)度函數(shù)計(jì)算群體中各個(gè)個(gè)體對(duì)問(wèn)題環(huán)境的適應(yīng)度，從而對(duì)群體中的每個(gè)成員進(jìn)行評(píng)估，然后根據(jù)每個(gè)個(gè)體的適應(yīng)度對(duì)各個(gè)個(gè)體所對(duì)應(yīng)的染色體進(jìn)行選擇，抑制適應(yīng)度低的染色體，繼承適應(yīng)度高的染色體，然后利用遺傳操作符（交叉，變異等）對(duì)群體中的個(gè)體進(jìn)行遺傳操作，產(chǎn)生進(jìn)化了的新一代群體。如此反復(fù)操作。一代一代不斷地向更優(yōu)解的方向進(jìn)化，最后得到滿(mǎn)足某種收斂條件的最適應(yīng)問(wèn)題環(huán)境的群體從而獲得問(wèn)題的最優(yōu)解.遺傳算法的主要實(shí)現(xiàn)步驟如下

47、：（1）問(wèn)題的表示對(duì)于一個(gè)實(shí)際的待優(yōu)化的問(wèn)題，要根據(jù)具體問(wèn)題確定待尋優(yōu)的參數(shù)以及評(píng)價(jià)解的優(yōu)劣程度的適應(yīng)度函數(shù)，從而使問(wèn)題適于遺傳算法進(jìn)行操作。（2）選擇待尋優(yōu)參數(shù)的編碼方式和編碼編碼是連續(xù)問(wèn)題與算法的橋梁。選擇合適的強(qiáng)有力的編碼表達(dá)方式是遺傳算法的關(guān)鍵根據(jù)所選擇的編碼方式，將待優(yōu)化的問(wèn)題的所有參變量編碼成對(duì)應(yīng)的子串再將各個(gè)子串首尾聯(lián)接成一定長(zhǎng)度的串（設(shè)串長(zhǎng)為），即染色體，每個(gè)串代表解空間中的一個(gè)解。不同的編碼方式對(duì)待優(yōu)化問(wèn)題的求解精度和算法的收斂速度有一定的影響。二進(jìn)制編碼對(duì)于數(shù)值優(yōu)化問(wèn)題存在著精度不高的缺點(diǎn)，參數(shù)動(dòng)態(tài)編碼是一種提高遺傳算法精度的新的編碼方式，但是對(duì)于非線(xiàn)性強(qiáng)的多模型優(yōu)化問(wèn)題，

48、dpe性能不佳，浮點(diǎn)數(shù)編碼具有精度高、便于大空間搜索的優(yōu)點(diǎn)。目前最常用的編碼方式主要是二進(jìn)制編碼。（3）產(chǎn)生初始群體選擇一個(gè)整數(shù)n作為群體的規(guī)模參數(shù)。隨機(jī)生成解空間的n個(gè)初始個(gè)體作為初始群體，代表待優(yōu)化問(wèn)題的一些可能解。遺傳算法就是從這一初始群體出發(fā)，通過(guò)遺傳操作模擬進(jìn)化過(guò)程，最后獲得問(wèn)題的最優(yōu)解。當(dāng)然對(duì)于有些問(wèn)題，具有某些先驗(yàn)知識(shí)的情況，可以首先將這些先驗(yàn)知識(shí)轉(zhuǎn)變?yōu)楸仨殱M(mǎn)足的一組要求，然后在滿(mǎn)足這些要求的解中再隨機(jī)地選取樣本，這樣選擇初始群體可以使遺傳算法更快地收斂到最優(yōu)解。(4）計(jì)算適應(yīng)度函數(shù)值計(jì)算適應(yīng)度函數(shù)值可以看作是遺傳算法與優(yōu)化問(wèn)題之間的一個(gè)接口。遺傳算法評(píng)價(jià)一個(gè)解的好壞，不是取決于

49、它的解的結(jié)構(gòu)，而是取決于相應(yīng)于該解的適應(yīng)度函數(shù)值。適應(yīng)度函數(shù)反映了個(gè)體對(duì)問(wèn)題環(huán)境適應(yīng)能力的強(qiáng)弱是個(gè)體競(jìng)爭(zhēng)的測(cè)度，它可以很好地控制個(gè)體生存的機(jī)會(huì)。（5）選擇、復(fù)制一般采用與適應(yīng)度函數(shù)值成比例的概率方法，個(gè)體適應(yīng)度函數(shù)值越高，其被選擇并復(fù)制的機(jī)會(huì)也就越多，選擇復(fù)制體現(xiàn)了“適者生存”的自然法則。選擇的目的是從群體中選出繁殖后代的雙親，復(fù)制則保留了父代的良好的基因。（6）交叉交叉是非常重要的遺傳算子。交叉操作可以分為如下兩個(gè)步驟，第一步是將新復(fù)制產(chǎn)生的個(gè)體隨機(jī)地兩兩匹配，第二步是進(jìn)行交叉操作。具體過(guò)程如下：設(shè)串的長(zhǎng)度為則串的個(gè)數(shù)字位之間的空隙標(biāo)記為，-。隨機(jī)地從，l一中選取一個(gè)整數(shù)位置k將兩個(gè)父母串中

50、從位置k到串末尾的子串互相交換，從而形成兩個(gè)新個(gè)體。這兩個(gè)新個(gè)體分別組合了其父輩個(gè)體的特性，產(chǎn)生了新的基因組合。圖3是交叉操作示意圖 圖1（7）變異首先在群體中隨機(jī)地選擇一個(gè)個(gè)體，對(duì)于選中的個(gè)體以一定的概率隨機(jī)地改變串上的某一位的值，以二進(jìn)制編碼為例，單靠變異操作一般不能使問(wèn)題求解取得進(jìn)展，因?yàn)樽儺惏l(fā)生的概率很小，但是變異能起到恢復(fù)丟失的遺傳信息生成新的遺傳信息的作用，從而保持群體中個(gè)體的多樣性，能有效地防止遺傳算法的過(guò)早收斂。圖2是變異操作示意圖 圖2（8）遺傳算法的終止遺傳算法的反復(fù)執(zhí)行（4）一（7）步，直至滿(mǎn)足某個(gè)收斂準(zhǔn)則，搜索到問(wèn)題的最優(yōu)解。收斂準(zhǔn)則一般有：遺傳算法找到能接受的優(yōu)秀個(gè)體

51、（最優(yōu)解）；遺傳算法已經(jīng)進(jìn)化了事先預(yù)定的最大代數(shù)；在事先預(yù)定的代數(shù)內(nèi)最優(yōu)秀個(gè)體的適應(yīng)度函數(shù)值無(wú)改進(jìn)；最優(yōu)秀個(gè)體占群體的比例已經(jīng)達(dá)到事先規(guī)定的比例。近年來(lái)，隨著智能方法的廣泛應(yīng)用，機(jī)器人路徑規(guī)劃方法也有了長(zhǎng)足的進(jìn)展，許多研究者把目光放在了基于智能方法的路徑規(guī)劃研究上，遺傳算法是目前路徑規(guī)劃研究中應(yīng)用較多的一種方法。遺傳算法不要求適應(yīng)度函數(shù)是可導(dǎo)或連續(xù)的，而只要求適應(yīng)度函數(shù)為正；作為并行算法，它的隱并行性適用于全局搜索：另外多數(shù)優(yōu)化算法是單點(diǎn)搜索算法，容易陷入局部最優(yōu)，而遺傳算法是一種多點(diǎn)搜索算法，因而更有可能搜索到全局最優(yōu)解。由于遺傳算法的整體搜索策略和優(yōu)化計(jì)算不依賴(lài)與梯度信息，解決了一些其他優(yōu)

52、化算法無(wú)法解決的問(wèn)題。 本文主要研究的是應(yīng)用遺傳算法的基本思想去研究機(jī)器人的路徑，去研究如何使機(jī)器人的路徑達(dá)到最優(yōu)。這里就相當(dāng)于運(yùn)用遺傳算法求最優(yōu)解（最小值或最大值）。比如對(duì)于一個(gè)求函數(shù)最大值的優(yōu)化問(wèn)題(求函數(shù)最小值也類(lèi)同)，一般可以描述為下列數(shù)學(xué)規(guī)劃模型: 式中2-1為決策變量，為目標(biāo)函數(shù)式，式2-2、2-3為約束條件，u是基本空間，r是u的子集。滿(mǎn)足約束條件的解x稱(chēng)為可行解，集合r表示所有滿(mǎn)足約束條件的解所組成的集合，稱(chēng)為可行解集合。1.4.1遺傳算法的基本運(yùn)算過(guò)程如下: a)初始化:設(shè)置進(jìn)化代數(shù)計(jì)數(shù)器t=0，設(shè)置最大進(jìn)化代數(shù)t，隨機(jī)生成m個(gè)個(gè)體作為初始群體p(0)。 b)個(gè)體評(píng)價(jià):計(jì)算群

53、體p(t)中各個(gè)個(gè)體的適應(yīng)度。 c)選擇運(yùn)算:將選擇算子作用于群體。選擇的目的是把優(yōu)化的個(gè)體直接遺傳到下一代或通過(guò)配對(duì)交叉產(chǎn)生新的個(gè)體再遺傳到下一代。選擇操作是建立在群體中個(gè)體的適應(yīng)度評(píng)估基礎(chǔ)上的。 d)交叉運(yùn)算；將交叉算子作用于群體。所謂交叉是指把兩個(gè)父代個(gè)體的部分結(jié)構(gòu)加以替換重組而生成新個(gè)體的操作。遺傳算法中起核心作用的就是交叉算子。 e)變異運(yùn)算:將變異算子作用于群體。即是對(duì)群體中的個(gè)體串的某些基因座上的基因值作變動(dòng)。 群體p(t)經(jīng)過(guò)選擇、交叉、變異運(yùn)算之后得到下一代群體p(t 1)。 f)終止條件判斷:若tt,則以進(jìn)化過(guò)程中所得到的具有最大適應(yīng)度個(gè)體作為最優(yōu)解輸出，終止計(jì)算。1.4.

54、2路徑規(guī)劃的實(shí)現(xiàn)路徑規(guī)劃的實(shí)現(xiàn)分為兩種遺傳算法機(jī)制，第一種只考慮靜態(tài)障礙物的情況，找出最佳的可行路徑，還包括出現(xiàn)靜態(tài)障礙物的動(dòng)態(tài)情況；機(jī)器人根據(jù)獲得的最佳路徑到達(dá)目的地同時(shí)處理期間出現(xiàn)的動(dòng)態(tài)障礙物的情況，由第二種遺傳算法機(jī)制解決本文主要分析靜態(tài)環(huán)境下，運(yùn)用以上的遺傳算法實(shí)現(xiàn)，通過(guò)操作算子的改進(jìn)，交叉率、變異率的選擇以及適應(yīng)度函數(shù)中加權(quán)系數(shù)的分析調(diào)整求得最佳的路徑。1.4.3 機(jī)器人路徑最優(yōu)化的實(shí)現(xiàn)主要結(jié)合選擇算子、交叉算子和變異算子，及目標(biāo)函數(shù)設(shè)置實(shí)現(xiàn)。路徑規(guī)劃算法運(yùn)用matlab建立仿真平臺(tái)，模擬實(shí)現(xiàn)過(guò)程，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行統(tǒng)計(jì)分析。1.5本章小結(jié)本章主要介紹了機(jī)器人路徑規(guī)劃研究的一些概況。討論了機(jī)器人路徑規(guī)劃研究的背景，給出了研究的目的，對(duì)當(dāng)前機(jī)器人路徑規(guī)