本文選題：計(jì)算智能 + 基于種群的搜索　； 參考：《中國科學(xué)技術(shù)大學(xué)》2017年博士論文

【摘要】：求解復(fù)雜優(yōu)化問題是解決許多實(shí)際問題的關(guān)鍵步驟。從牛頓時(shí)代開始,人們就已經(jīng)開始關(guān)注于優(yōu)化問題的求解方法。然而,隨著社會的飛速發(fā)展,當(dāng)今世界中的優(yōu)化問題已經(jīng)越來越復(fù)雜,傳統(tǒng)的優(yōu)化方法常常無法在合理時(shí)間內(nèi)進(jìn)行求解。為了更快更好地求解優(yōu)化問題,智能優(yōu)化方法應(yīng)運(yùn)而生。其中,基于種群的搜索方法,如演化算法類,已經(jīng)得到了廣泛的認(rèn)可。所謂基于種群的搜索方法,即是在問題解空間迭代式地"生成-測試"一組候選解。這類方法已經(jīng)被廣泛應(yīng)用于各類工程設(shè)計(jì)、作業(yè)調(diào)度、投資組合和自動控制等關(guān)系國計(jì)民生的重大項(xiàng)目中,并獲得了令人矚目的成績。特別值得一提的是,相對于基于種群的搜索方法,在智能優(yōu)化方法中還存在著一類基于個體的搜索方法,即是在問題解空間迭代式地"生成-測試"一個候選解。誠然這類方法,如模擬退火、禁忌搜索等,曾經(jīng)也獲得了巨大的關(guān)注以及成功,但研究的熱潮還是逐漸在朝基于種群的搜索方法轉(zhuǎn)移。這主要是大量的理論和實(shí)驗(yàn)結(jié)果表明后者效果優(yōu)于前者,特別是在一類叫做多極值優(yōu)化的問題類上。然而,何以基于種群的方法要比基于個體的方法更好?研究人員普遍認(rèn)為這是基于種群的方法中多個個體之間的某種合作機(jī)制在起作用,并也得到了一些間接的證據(jù),如一個種群大小為N的基于種群的方法可以比N個獨(dú)立運(yùn)行的基于個體的方法表現(xiàn)更好。研究者也嘗試了各種方式來產(chǎn)生個體間的合作,并得到了許多優(yōu)秀的算法。然而在我們看來,目前仍然沒有一個關(guān)于合作機(jī)制的清晰路線來引導(dǎo)算法設(shè)計(jì)者提出更先進(jìn)的方法。本文試圖對個體間的合作機(jī)制進(jìn)行一些探索。我們首先將現(xiàn)有的基于種群的方法梳理為兩大類:隨機(jī)重組和自動分治。然后我們簡要回顧以及對比這兩類方法,討論這兩類方法在設(shè)計(jì)思路上的本質(zhì)不同。具體來說,隨機(jī)重組類方法主要是關(guān)注于新個體的產(chǎn)生階段,其利用交叉、變異的方式將已有個體中包含的變量進(jìn)行重新組合。這個重新組合的過程就是一種合作機(jī)制,其本質(zhì)在于共享一些潛在較好的決策變量值。隨著迭代的進(jìn)行、個體會由于不斷重組而"趨同"、導(dǎo)致種群收斂。為了延緩收斂,該類方法還利用了變異這一操作來隨機(jī)地增加種群中的多樣性。交叉和變異操作合起來就是其隨機(jī)、重組的思想體現(xiàn)。反過來,自動分治類方法主要是關(guān)于個體的選擇、替換階段,其旨在對種群進(jìn)行劃分,使得不同個體分別搜索解空間不同的區(qū)域。其合作機(jī)制體現(xiàn)在:個體之間互相傳遞各自的當(dāng)前狀態(tài)信息,避免搜索區(qū)域重疊。由于個體互相"排斥",該類方法中種群的成分會隨著迭代過程而"趨異"。接著,我們沿著自動分治的思想,進(jìn)一步將相關(guān)工作劃分為中心化方法和去中心化方法,并提出各自的優(yōu)勢和劣勢。具體來說,中心化自動分治方法旨在利用種群的全局信息,自頂向下地對整個種群進(jìn)行劃分;而去中心化自動分治方法則在局部區(qū)域共享個體當(dāng)前狀態(tài)信息,自適應(yīng)地形成多個子種群,這是一種自底向上地劃分方式。由于中心化方法利用了更多更全面的信息,其對種群的劃分應(yīng)該更加精準(zhǔn),即子種群和解空間局部極值區(qū)域能夠一一對應(yīng)。這樣,每個子種群能從一個比較好的初始位置開始搜索,算法總的搜索速率會顯著提高。同時(shí),由于其需要處理的信息更多,計(jì)算代價(jià)也比較高。而去中心化方法只在局部區(qū)域傳遞信息進(jìn)行合作,計(jì)算更加輕便,而且由于子種群是在迭代過程中自適應(yīng)生成的,可以更佳魯棒。但同時(shí),去中心化方法生成的子種群無法精確覆蓋局部極值區(qū)域,而是通過增加種群多樣性的方式來逐漸搜索解空間。而維持足夠的種群多樣性也是搜索成功的關(guān)鍵要素之一。沿著以上思路,我們不難發(fā)現(xiàn)現(xiàn)有工作的不足之處。對于中心化方法,已有工作只利用了種群的分布信息來進(jìn)行劃分,無法做到子種群和局部極值區(qū)域一一對應(yīng)。而對于增加種群多樣性,隨機(jī)重組和去中心化方法均可。但現(xiàn)有工作并未能有效地將兩者連接起來,形成一種可控地多樣性提升方式。針對這兩者缺點(diǎn),我們沿著以上思路分別提出了改進(jìn)方法。對于中心化方法,我們可以通過增加信息的使用來提升劃分的精確性。為此,我們不僅利用了種群的分布信息,還利用了種群分布的變化信息來幫助劃分子種群。我們發(fā)現(xiàn)種群分布的變化信息在一定程度上實(shí)際反應(yīng)了解空間地形變化的趨勢。通過對種群分布變化的分析,我們能更加快速地找到局部極值所在區(qū)域。這構(gòu)成了本文第一個工作的核心貢獻(xiàn)。對于增加種群多樣性,我們提出了一種按搜索行為而非個體位置距離來進(jìn)行候選解選擇的去中心化方法。通過對搜索行為(可能產(chǎn)生新個體的概率分布)進(jìn)行直接建模,我們能夠?qū)⑿聜�體的產(chǎn)生和選擇有機(jī)地結(jié)合在一起,使得種群的多樣性更容易控制。這是本文第二個工作的主要想法。我們不僅在基準(zhǔn)測試問題集上測試了我們提出的算法,還將其應(yīng)用于一個具體的現(xiàn)實(shí)優(yōu)化問題:無人機(jī)路徑規(guī)劃問題。這是本文的第三個工作。我們重點(diǎn)關(guān)注任務(wù)場景中具有大量障礙的無人機(jī)路徑規(guī)劃問題。我們發(fā)現(xiàn),當(dāng)障礙數(shù)量增加時(shí),該問題本質(zhì)上是一個高維、高約束的多極值優(yōu)化問題。我們將這些難點(diǎn)分為兩部分:高維度和高約束多極值。對于后者,我們利用提出的去中心化方法進(jìn)行求解。對于前者,我們進(jìn)一步將分治思想從候選解劃分拓展到了決策變量的劃分,從而達(dá)到顯著降低搜索空間的目的。實(shí)驗(yàn)證明,我們提出的該方法可以極大地提升無人機(jī)路徑規(guī)劃的求解效率和性能。受到該工作的啟發(fā),我們將按決策變量分治的思想進(jìn)一步從該無人機(jī)路徑規(guī)劃問題泛化到了一般性的高維優(yōu)化問題上。這構(gòu)成了本文的最后一個工作。
[Abstract]:Solving complex optimization problems is the key step to solve many practical problems. Since the Newton era, people have begun to pay attention to the optimization problem solving methods. However, with the rapid development of society, the optimization problems in the world are becoming more and more complex, and the traditional optimization methods are often unable to be solved in a reasonable time. In order to solve the optimization problem faster and better, intelligent optimization methods emerge as the times require. Among them, the population based search method, such as the evolutionary algorithm class, has been widely recognized. The so-called population based search method is a group of candidate solutions, which are iteratively "generating and testing" in the problem solution space. In the major projects related to the national economy and the people's livelihood, such as engineering design, job scheduling, investment portfolio and automatic control, it has gained remarkable achievements. It is particularly worth mentioning that there is a kind of individual based search method in intelligent optimization method, that is, "birth" in the solution space iteratively relative to the population based search method. It is true that such methods, such as simulated annealing, tabu search and so on, have also gained great attention and success, but the upsurge of research is gradually moving towards a population based search method. This is mainly a large number of theoretical and experimental results that show that the latter is better than the former, especially in a class called multipole. However, why is the population based approach better than the individual based approach? Researchers generally believe that this is a kind of cooperative mechanism among a number of individuals in a population based approach, and some indirect evidence, such as a population based method of a population size of N, can be compared to N The individual based approach performs better. The researchers have also tried various ways to produce inter individual cooperation and have obtained many excellent algorithms. However, in our view, there is still no clear route to the cooperation mechanism to guide the algorithm designers to bring forward more advanced methods. The cooperation mechanism is explored. We first sort out the existing population based methods into two categories: random and automatic division. Then we briefly review and compare the two methods, and discuss the differences in the design ideas of these two methods. In particular, the random reorganization method is mainly concerned with the production of new individuals. In the birth stage, it uses cross and mutation to recombine the variables contained in the existing individual. This regrouping process is a cooperative mechanism whose essence is to share some potential better decision variables. As the iteration proceeds, the experience is "converging" by continuous reorganization, leading to the convergence of the population. Convergence, this kind of method also uses the mutation operation to randomly increase the diversity in the population. The intersection and mutation operation is the idea of random and regrouping. In turn, the method of automatic divide and conquer is mainly about the selection and replacement of the individual, which is designed to divide the group, so that the different individuals search for the solution space respectively. In different regions, the cooperation mechanism is embodied in that the individual transfers their current state information to each other and avoids the overlap of the search areas. As the individual "repels" each other, the composition of the population will "be different" with the iterative process. Then, we further divide the relevant work into a centralization method along the idea of automatic divide and treatment. In particular, the centralization automatic divide and conquer method aims to divide the whole population from the top to the bottom by using the global information of the population, while the centralization automatic divide and conquer method shares the present state information of the individual in the local area and adaptively forms a number of subpopulations. Because the centralization method uses more and more comprehensive information, the division of the population should be more accurate, that is, the subpopulation and the spatial local extremum area can correspond one by one. In this way, each subpopulation can start searching from a better initial position, and the total search rate of the algorithm will be significantly improved. At the same time, the computational cost is higher because of the more information it needs to deal with, and the de centralization method only transfers information in the local area to cooperate, and the calculation is more portable. And because the subpopulation is self-adaptive in the iterative process, it can be better. At the same time, the subpopulation generated by the centralization method can not accurately cover the Bureau. It is one of the key elements of the search success to search the solution space gradually by increasing the diversity of the population, and maintaining sufficient population diversity is also one of the key elements of the search success. It is impossible to make a one-to-one correspondence between the subpopulation and the local extreme value region. But for the increase of population diversity, random recombination and de centralization, but the existing work does not effectively connect the two together to form a controllable diversity promotion method. Method. For the centralization method, we can improve the accuracy of the partition by increasing the use of information. Therefore, we not only use the distribution information of the population, but also use the change information of the population distribution to help divide the subpopulation. We find that the variation information of the population distribution is in a certain degree to understand the spatial terrain to some extent. The trend of change. By analyzing the variation of population distribution, we can find the region of the local extremum more quickly. This constitutes the core contribution of the first work in this paper. For the increase of population diversity, we propose a de centralization method for selecting the candidate solutions according to the search behavior rather than the individual location distance. We can directly model the search behavior (the probability distribution of new individuals). We can combine the generation and selection of new individuals organically to make the diversity of the population more easily controlled. This is the main idea of the second work in this paper. It is applied to a specific realistic optimization problem: the UAV path planning problem. This is the third work of this paper. We focus on the problem of UAV path planning with a large number of obstacles in the task scene. We find that when the number of obstacles is increased, the problem is essentially a high dimension, high constraint multipole optimization problem. These difficulties are divided into two parts: high dimension and high constraint multi extremum. For the latter, we use the proposed de centralization method to solve the problem. For the former, we further extend the divide and conquer idea from the candidate solution division to the decision variable division, so as to achieve the goal of significantly reducing the search space. The method can greatly improve the efficiency and performance of the UAV path planning. Inspired by this work, we will further generalize the problem of the UAV path planning to the general high dimensional optimization problem according to the idea of the decision variables dividing and treatment. This constitutes the last work of this paper.

【學(xué)位授予單位】：中國科學(xué)技術(shù)大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2017
【分類號】：TP301.6

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 王罡;李梅娟;陳雪波;;單巷道固定貨架路徑規(guī)劃問題的研究[J];計(jì)算機(jī)工程與應(yīng)用;2008年16期

2 楊正磊;宋建社;吳永定;郭軍;;多約束條件下戰(zhàn)場導(dǎo)航路徑規(guī)劃問題研究[J];系統(tǒng)仿真學(xué)報(bào);2011年06期

3 艾海舟,張鈸;基于拓?fù)涞穆窂揭?guī)劃問題的圖形解法[J];機(jī)器人;1990年05期

4 鄧文;李實(shí);鄭攀;;基于蟻群算法的路徑規(guī)劃問題研究[J];物流技術(shù);2008年10期

5 胡薈;蔡秀珊;;機(jī)器人三維路徑規(guī)劃問題的一種改進(jìn)蟻群算法[J];計(jì)算機(jī)工程與科學(xué);2012年11期

6 陳剛,沈林成;復(fù)雜環(huán)境下路徑規(guī)劃問題的遺傳路徑規(guī)劃方法[J];機(jī)器人;2001年01期

7 普措才仁;;一種新的編碼方法解決路徑規(guī)劃問題[J];工業(yè)儀表與自動化裝置;2011年01期

8 魯子卉;;基于Memetic算法的電子AGV路徑規(guī)劃[J];四川兵工學(xué)報(bào);2013年02期

9 于銳;曹介南;朱培棟;;車輛運(yùn)輸路徑規(guī)劃問題研究[J];計(jì)算機(jī)技術(shù)與發(fā)展;2011年01期

10 馬保離,宗光華,霍偉;非完整鏈?zhǔn)较到y(tǒng)的路徑規(guī)劃——多項(xiàng)式擬合法[J];自動化學(xué)報(bào);1999年05期

相關(guān)會議論文 前1條

1 王旭;張江;崔平遠(yuǎn);;一種基于蟻群算法求解路徑規(guī)劃問題的新方法[A];2003年中國智能自動化會議論文集（下冊）[C];2003年

相關(guān)博士學(xué)位論文 前3條

1 張興;信使機(jī)制UAV/UGV多點(diǎn)動態(tài)集結(jié)的協(xié)同規(guī)劃方法研究[D];北京理工大學(xué);2015年

2 楊鵬;基于自動分治的智能優(yōu)化方法及其應(yīng)用研究[D];中國科學(xué)技術(shù)大學(xué);2017年

3 王沛棟;改進(jìn)蟻群算法及在路徑規(guī)劃問題的應(yīng)用研究[D];中國海洋大學(xué);2012年

相關(guān)碩士學(xué)位論文 前10條

1 王晨;基于社區(qū)發(fā)現(xiàn)的動態(tài)路徑規(guī)劃問題研究[D];哈爾濱工業(yè)大學(xué);2016年

2 林麗琳;供應(yīng)鏈中的車輛路徑規(guī)劃問題研究[D];華僑大學(xué);2015年

3 張麗娜;電動汽車路徑規(guī)劃問題研究[D];東華大學(xué);2016年

4 徐彪;多靜態(tài)節(jié)點(diǎn)DTN中移動Agent路徑規(guī)劃研究[D];杭州電子科技大學(xué);2016年

5 丁然;基于改進(jìn)蟻群算法的單校校車路徑規(guī)劃問題研究[D];遼寧師范大學(xué);2016年

6 袁斌;帶訪問限制的需求時(shí)變的移動設(shè)施路徑規(guī)劃問題研究[D];清華大學(xué);2014年

7 趙再興;基于改進(jìn)和聲搜索算法的車輛路徑規(guī)劃問題[D];沈陽大學(xué);2011年

8 王星;基于蟻群算法的圖書物流車輛路徑規(guī)劃問題研究[D];武漢理工大學(xué);2011年

9 吳穎;雙層車庫車輛調(diào)度輔助決策支持系統(tǒng)[D];華中科技大學(xué);2011年

10 玉坤;蟻群算法在路徑規(guī)劃問題中的應(yīng)用研究[D];北京工業(yè)大學(xué);2012年

，

本文編號：1833229