[發(fā)明專利]一種導(dǎo)航方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201410371032.2
• 申請(qǐng)日: 2014-07-31
• 公開(kāi)（公告）號(hào): CN104142151A
• 公開(kāi)（公告）日: 2014-11-12
• 發(fā)明（設(shè)計(jì)）人: 李保印
• 申請(qǐng)（專利權(quán)）人: 上海聞泰電子科技有限公司
• 主分類號(hào): G01C21/20
• 分類號(hào): G01C21/20
• 代理公司: 上海新天專利代理有限公司 31213
• 代理人: 王敏杰

1.一種導(dǎo)航方法，其特征在于，所述導(dǎo)航方法包括：

步驟S1、獲取目的地位置信息及實(shí)時(shí)位置信息；

步驟S2、根據(jù)目的地位置信息、實(shí)時(shí)位置信息實(shí)時(shí)獲取到達(dá)目的地的K條最短路徑，進(jìn)行實(shí)時(shí)導(dǎo)航，在導(dǎo)航的過(guò)程中不斷的計(jì)算著用戶的路線軌跡,直到導(dǎo)航結(jié)束；通過(guò)GPS傳輸數(shù)據(jù)，再根據(jù)地址數(shù)據(jù)庫(kù)、地圖數(shù)據(jù)庫(kù)、第三方路況信息數(shù)據(jù)庫(kù)和用戶數(shù)據(jù)庫(kù)，隨時(shí)更新用戶和目的地直接的路徑；采用混合蛙跳算法求解K條最短路徑；具體包括：

步驟S21、初始化蛙群，隨機(jī)產(chǎn)生F只青蛙，計(jì)算青蛙個(gè)體的評(píng)價(jià)值并將蛙群按評(píng)價(jià)值升序排序；青蛙個(gè)體的評(píng)價(jià)值的獲取方法為：用路徑path所有邊的代價(jià)之和表示青蛙的評(píng)價(jià)函數(shù)，即f(frogj)=Σe∈pathcost(e);]]>

編碼是從問(wèn)題空間向搜索空間的一個(gè)映射，從起始點(diǎn)到終點(diǎn)的一條路徑對(duì)應(yīng)的節(jié)點(diǎn)集合；其中，每一位上的節(jié)點(diǎn)編號(hào)稱為青蛙的一個(gè)模因meme；給定一個(gè)賦權(quán)圖G＝(V,E)，V表示G中所有頂點(diǎn)的集合，E表示所有邊的集合；邊的代價(jià)函數(shù)表示為Cost:E→R⁺，cost(e)為邊e∈E的代價(jià)；

步驟S22、劃分族群；把F個(gè)蛙分配到m個(gè)族群(Y)中去，每個(gè)族群包含n個(gè)蛙，從而使得Yk＝[X(j),f(j)|X(j)＝X(k+m*(j-1),f(j)＝f(k+m*(j-1),j＝1,…,n,k＝1,…,m].這里X(j)表示蛙群中的第j蛙，f(j)表示第j個(gè)蛙的目標(biāo)函數(shù)值；

步驟S23、局部搜索，對(duì)每個(gè)族群執(zhí)行局部搜索loop次；

青蛙個(gè)體的學(xué)習(xí)目標(biāo)是族群內(nèi)最優(yōu)個(gè)體frog_b或整個(gè)青蛙群中的最優(yōu)個(gè)體frog_g；采用對(duì)族群中的青蛙按均勻概率選取子群，假設(shè)從第i個(gè)青蛙族群中隨機(jī)選擇s只青蛙作為該族群的子群進(jìn)行局部搜索；將s只青蛙中具有最優(yōu)評(píng)價(jià)值的青蛙記為frog_b，具有最差評(píng)價(jià)值的青蛙記為frog_w，將蛙群中具有最優(yōu)評(píng)價(jià)值的青蛙記為frog_g，則族群i中的一次局部搜索包括：

步驟S231、從族群中隨機(jī)選擇s只青蛙；

步驟S232、使frog_w向frog_b跳越一次，執(zhí)行W.Leap(B)；

步驟S233、若frog_w代表的解質(zhì)量較之前更優(yōu)，則該次局部搜索結(jié)束；若較之前更劣或未改變，則frog_w向frog_g跳越一次，執(zhí)行W.Leap(G)；

步驟S234、若frog_w代表的解質(zhì)量較之前更優(yōu)，則該次局部搜索結(jié)束；若較之前更劣或未發(fā)生改變，則重新隨機(jī)構(gòu)造frog_w；

在每個(gè)族群中，上述4個(gè)步驟被執(zhí)行l(wèi)oop次，loop稱為局部搜索強(qiáng)度；

步驟S24、族群混合對(duì)整個(gè)蛙群中具有相同模因結(jié)構(gòu)的青蛙進(jìn)行重構(gòu)，計(jì)算青蛙的評(píng)價(jià)值并將蛙群按升序排序；

步驟S25、判斷是否滿足算法終止條件，若滿足，輸出前k只青蛙作為k條最短路徑；否則，返回步驟S22；

其中，F(xiàn)為蛙群規(guī)模，m為族群數(shù)，n為族內(nèi)青蛙數(shù)，s為子群青蛙數(shù)，loop為局部搜索強(qiáng)度；族群數(shù)m取m≥k，k條最短路徑實(shí)際上就是經(jīng)過(guò)排序的全部青蛙的前k只青蛙；當(dāng)m≥k時(shí)，在劃分族群后，前k只青蛙將成為各自所在族群中最優(yōu)的青蛙個(gè)體，從而避免其蛙跳行為，使求解具有較好的穩(wěn)定性；如果取m<k，在劃分族群后，前m只青蛙被分別劃分至第1至第m族群，成為各族群中的最優(yōu)青蛙個(gè)體，而第m+1至第k只青蛙則分別被劃分在第1至第(k-m)族群，并成為這些族群中的次優(yōu)個(gè)體；在局部搜索中，族群內(nèi)的次優(yōu)青蛙可能會(huì)向最優(yōu)青蛙學(xué)習(xí)，導(dǎo)致次優(yōu)青蛙的模因結(jié)構(gòu)變化，因而影響求解k條最短路徑的質(zhì)量和穩(wěn)定性。