利索能及
我要发布
收藏
专利号: 2019104822309
申请人: 三峡大学
专利类型:发明专利
专利状态:已下证
更新日期:2024-09-12
缴费截止日期: 暂无
联系人

摘要:

权利要求书:

1.一种基于黏菌群体智能的交通网络节点选择方法,其特征在于,所述方法采用黏菌群体智能行为对交通网络节点进行优化,对交通网络节点进行重要性排序和优化布局,将多个交通网络节点模拟成多个外部食物源,将交通网络中两个节点之间的链路模仿成黏变形体,将交通网络模拟成覆盖所有外部食物源的黏菌群体原质团,将交通运输模拟成黏菌群体运输体内营养物质,将交通网络节点优化问题模拟成黏菌群体觅食网络优化问题;具体优化方法包括以下步骤:步骤一为黏菌群体分工阶段,模拟黏菌群体活动的分工行为,每个黏菌个体随机分布于不同的外部食物源节点上,每个黏菌个体自行分工,在各自所处位置上进行原质团扩张操作完成觅食,不同的黏菌个体可以互相共享找到的食物源节点信息和传输链路信息,即交通网络尽可能利用不同黏菌个体的地理位置覆盖所有外部食物源即解空间中待选择的交通网络节点;

步骤二为黏菌群体合作的阶段,模仿黏菌群体活动的合作行为,每个黏菌个体在交通网络节点上不断移动选择新的外部食物源节点,以便在自身营养物质约束的条件下以最短的路径进食最多的食物,不同黏菌群体的黏变形体能够交叉、合并、收缩;从而在外部食物源较多的位置聚集较多的黏菌个体,在黏菌个体较集中的交通网络节点可确定为较高的优先级或重要性;在外部食物源较少的位置聚集较少的黏菌个体,在黏菌个体较少的交通网络节点可确定为较低的优先级或重要性;所有黏菌个体形成按交通网络节点重要性排序而构成的最优交通网络结构,以最高的效率传输外部食物源,即利用不同黏菌个体的集中度求解交通网络节点重要性排序和最优的拓扑布局。

2.根据权利要求1所述的基于黏菌群体智能的交通网络节点的优化方法,其特征在于,黏菌群体对应于节点选择问题的可行解集合;黏菌个体对应于节点选择问题的单个可行解;各黏菌的细胞核对应于单个解中的交通网络节点,即个体搜索到的最优解节点;黏菌个体自身营养物质约束对应于单个解的搜索范围;黏菌群体原质团对应于交通网络;外部食物源对应于解空间中待选择的交通网络节点;非食物源对应于交通网络中不可行的节点或区域;黏变形体对应于交通网络中各节点之间的链路;黏菌分布密度对应于交通网络的重要度评估;黏菌群体运输体内营养物质对应于交通运输;黏菌个体的移动对应于单个解的搜索;黏菌群体分工对应于分布式寻找交通网络节点;黏菌群体合作对应于交通网络节点评估和重要性排序;黏菌群体分工合作的目标函数是以最优的拓扑结构来最大化地获得外部食物源,对应于交通网络的目标是以最优的拓扑结构来最大化地满足不同重要性节点的交通运输需求;交叉操作对应于黏菌群体寻找不同可行解时以一定的概率进行联系和传递消息;合并操作对应于黏菌群体寻找可行解时能够共享网络节点和运输链路;收缩操作对应于黏菌群体的黏变形体以一定比率减少联系,优化运输链路。

3.根据权利要求1所述的基于黏菌群体智能的交通网络节点的优化方法,其特征在于,步骤一黏菌群体分工阶段中,每个黏菌个体的细胞核随机分布于不同交通网络节点上,每个黏菌个体以各自的细胞核为中心自行分工四处扩张寻找新的交通网络节点,记录每个黏菌个体的细胞核座标矩阵,以及每个黏菌个体的黏变形体寻找到的交通网络节点个数及其相应座标;并对交通网络的各个节点建立黏菌数量矩阵作为该节点的重要度矩阵,即交通网络的节点重要性取决于该节点上进食的黏菌个体数量或细胞核数量,在交通网络规划时参考该重要度矩阵对交通网络节点进行排序,并根据重要度矩阵对拓扑结构进行合理优化;黏菌是一个以细胞核为中心的扩张结构,该节点上的黏菌数量实际上包括与该节点相连接的邻居节点信息,以及其与邻居节点相连接的长度信息;节点重要度矩阵中的值越大,表明该节点越重要,即该节点连接的邻居节点越多,且到邻居节点的距离越短;反之,该值越小,表明该节点越不重要,即该节点连接的邻居节点越少,且与邻居节点相连的距离较长。

4.根据权利要求3所述的基于黏菌群体智能的交通网络节点的优化方法,其特征在于,分工阶段包括三个子步骤:

子步骤1-1:黏菌群体初始化,初始化待求解问题的有向图Graph=(Node,Edge);其中,Node=[Nodei]n=[(xi,yi)]n表示包括交通网络中共有n个节点的座标矩阵,n表示交通网络有向图Graph的节点总数,Nodei表示交通网络有向图Graph中第i个节点,(xi,yi)表示交通网络节点Nodei的横座标和纵座标;Edge={Edgeij|i,j∈n}表示节点之间的联系构成边矩阵,Edgeij表示节点Nodei和Nodej之间的边;节点之间边的长度矩阵或节点间距离矩阵表示为 Distanceij表示节点Nodei和Nodej之间边Edgeij的长度|Edgeij|;矩阵n个节点之间最多有n(n-1)条边,则所有节点间距离的平均值表示为 本方法使用概率搜索方法,产生m

(m≥n)只黏菌个体,m表示黏菌个体总数;将各黏菌的细胞核随机放置于交通网络不同节点上,即每个黏菌个体k(k=1,2,...,m)细胞核座标为Node矩阵随机值RAND{(xk,yk)∈Node|k=1,2,...,m},RAND表示随机函数,k表示黏菌个体序号;

子步骤1-2:黏菌群体分工觅食,交通网络模仿黏菌群体觅食行为,每个黏菌个体原质团以细胞核为中心由近及远不断进行扩张操作,在自身营养物质约束下按固定或可调的搜索半径尽可能寻找周边的交通网络节点,第k(k=1,2,...,m)个黏菌个体的搜索半径表示为Radiusk,一般大于节点间的平均距离,为 如果Radiusk较大,则黏菌个体的搜索范围较大,有可能找到更多交通网络节点,且不同黏菌个体之间的重叠概率也更大;如果Radiusk较小,则黏菌个体的搜索范围较小,找到的交通网络节点可能更少,黏菌个体之间的重叠概率也更小;黏菌群体的分工觅食操作必须在各自细胞核所在的节点周围进行,并且在自身营养物质的限制下进行,而不能无限扩张;

第k(k=1,2,...,m)个黏菌个体横座标和纵座标表示为(xk,yk),经过搜索后在周边找到Countk个交通网络节点,Countk表示第k(k=1,2,...,m)个黏菌个体找到的邻居节点总数,则形成一个遍历周边Countk个交通网络节点的进食网络;第k(k=1,2,...,m)个黏菌个体的进食网络表示为 则其进食网络的 总长度表示为l∈Subnetk;其中,Countk表示了第k(k=1,2,...,m)个黏菌个体所

在节点的中心度,显然一个节点的中心度越大,Countk就越大,说明该节点能够直接影响的邻居节点也就越多,具有更优的重要性;Lengthk表示了第k(k=1,2,...,m)个黏菌个体所在节点与邻居节点的紧密度,即定义了一个节点到邻居节点远近程度,显然一个节点的紧密度越大,Lengthk就越小,说明该节点能够直接影响的邻居节点也就越近,具有更优的重要性;进一步地,综合Countk≥0,Lengthk≥0,黏菌个体尽可能地在分工觅食中以最短路径找到更多的网络节点,可定义第k(k=1,2,...,m)个黏菌个体的目标函数为Subfunk=Countk/Lengthk(Lengthk≠0)或Subfunk=0(Lengthk=0);

子步骤1-3:黏菌群体分享信息,黏菌群体原质团在由内向外扩张过程中,可能找到了食物源,对其位置做出标定,并通过黏变形体将信息传递给其他黏菌个体,为黏菌群体下一步的合作阶段作好准备,以便其他黏菌个体移动和进食;黏菌群体原质团在扩张过程中,也可能没有找到食物源,或遇到了非食物源,比如有毒物质、非亲和性物质等,则黏菌群体原质团需要离开该物质所在节点和区域,标记位置信息并通过黏变形体传递给其他黏菌个体,黏菌群体将不再进入该区域;

其中,因为共享某些交通链路导致一些黏菌个体重叠,在计算总长度时不再重复计算,分工阶段所求的交通网络长度为遍历所有节点的最短路径;由于本算法求解过程与初始条件无关,可为各节点Node=[Nodei]n=(xi,yi)]n初始化重要度矩阵Weight(0)=[Weighti(0)]n,其中,Weighti(0)表示第i(i=1,2,...,n)个节点上随机分布的黏菌个体初始数量,即黏菌个体细胞核数量,因为黏菌个体的黏变形体之间有重叠,因此将交通网络节点的重要度随机地初始化为黏菌个体细胞核数量。

5.根据权利要求1所述的一种基于黏菌群体智能的交通网络节点选择方法,其特征在于,步骤二为黏菌群体合作的阶段,m只黏菌个体合力将n个网络节点消化后的营养物质,即运输对象通过交通链路运送回m个节点;每只黏菌个体以一定概率四处移动,试图以最小的进食距离找到更多的网络节点,每找到一个进食网络解后,需要评估该解的优化程度,并根据评估结果确定是否留在该节点;黏菌群体的移动具有学习性,既要学习本黏菌个体当前所在网络节点信息,也要学习从邻居黏菌传递过来的网络节点信息,根据个体学习和邻居学习的情况计算下一步可达网络节点的概率,并按概率实现进一步移动,依此往复;最后,整个交通网络形成一个具有不同黏菌分布密度的拓扑结构,得到以黏菌密度表示的网络节点重要性排序结果,并根据该重要度排序结果合理选择节点以构建最优交通网络。

6.根据权利要求5所述的一种基于黏菌群体智能的交通网络节点选择方法,其特征在于,合作阶段包括三个子步骤;

子步骤2-1:黏菌群体评估,在这个子步骤,使用分布式计算方法,所有黏菌个体需要根据自己所处的节点位置进行评估,以确定是否离开该节点继续觅食;假设当前时刻为t,第k(k=1,2,...,m)个黏菌个体座标为Nodek(t)=(xk(t),yk(t)),黏菌个体的目标函数值为Subfunk(t);该个体所找到的当前最好位置表示为 对应的目标函数值表示为 整个黏菌群体所找到的当前最好位置表示为

对应的目标函数值表示为 根据评估结果,则黏菌个体最优位置更新为:

子步骤2-2:黏菌群体学习,在这个子步骤,使用概率搜索方法,黏菌个体通过学习自己过去的经验以及其他黏菌个体共享的信息,更新自己所处的节点位置:一方面,黏菌个体根据自己所处的网络结构,以个体学习概率Probabilityk1(t)学习自已黏变形体搜索到的网络节点信息,并移动到下一个网络节点,尝试寻找更优的或者更重要的网络节点,即具有更多邻居网络节点的位置,且离邻居网络节点更近的位置,Probabilityk1(t)表示第k(k=1,

2,...,m)个黏菌个体自我学习的概率;另一方面,黏菌个体还通过黏变形体与邻居黏菌个体的交叉、合并、收缩操作,以邻居学习概率Probabilityk2(t)学习更远的邻居黏菌个体的觅食信息和网络节点信息,供自己移动时选择,Probabilityk2(t)表示第k(k=1,2,...,m)个黏菌个体学习邻居的概率;黏菌个体k(k=1,2,...,m)的学习算法如下:子步骤2-3:节点重要度排序,在这个子步骤,一方面,非重要的网络节点周围具有较低的网络节点密度和黏菌个体密度,且随着黏菌群体的不断移动,该部分节点上的黏菌个体将越来越少,每当有一个黏菌个体离开,则有Weighti(t)=Weighti(t)-1;另一方面,在重要的网络节点附近具有较多的邻居网络节点,且随着黏菌群体的不断移动,重要网络节点上的黏菌个体将越来越多,每当有一个黏菌个体进入该节点,则有Weighti(t)=Weighti(t)+

1,并且黏菌个体k(k=1,2,...,m)每次移动结束后计算自己的目标函数,为Subfunk(t)=Countk(t)/Lengthk(t)(Lengthk(t)≠0)或Subfunk(t)=0(Lengthk(t)=0),其中,Countk表示第k(k=1,2,...,m)个黏菌个体找到的邻居节点总数,Lengthk表示了第k(k=1,2,...,m)个黏菌个体进食网络的总长度;

可设置结束条件为迭代次数,或每次适应度值符合预定的误差值,如未达到结束条件,则返回子步骤2-1及子步骤2-2进行不断更新;经过黏菌群体的不断运动,整个交通网络上不同节点就聚集了不同数量的黏菌个体细胞核;当符合结束条件时,便可以给出整个网络的节点重要度排序:RANK{Node1,...,Nodei,Nodei+1,...,|Nodei∈Node,and Weighti≤Weighti+1},其中,RANK表示节点重要度排序函数;在进行交通网络规划时,用户可根据所求得的节点重要度排序结果依次选择合适的网络节点,从而优化交通网络布局和拓扑结构。

7.根据权利要求1所述一种基于黏菌群体智能的交通网络节点选择方法,包括多个外部食物源,多个黏菌原质团,多个黏变形体,多个黏菌细胞核,多个体内营养物质;其特征在于,黏菌个体之间的操作有三种方式:一是交叉操作,即不同黏菌个体间通过黏变形体(运输链路)以一定的概率进行联系和传递消息;二是合并操作,即不同黏菌个体能够共享网络节点和运输链路,对同一网络节点共同进食,并使用同一运输链路运输营养物质;三是收缩操作,即不同黏菌个体间的黏变形体以一定比率减少联系,模拟黏菌个体中体内营养物质被自己原质团或邻居黏菌个体吸收消耗的过程;因此,可以根据黏菌个体的联系强度提供交通网络节点的信息,为黏菌运动提供依据。

8.权利要求1-7任意一项所述的方法应用于求解多目标优化或计算机网络优化或云计算优化或国计民生的重大决策优化或社会群体网络优化或网络舆情或群体性应急事件管理或火灾逃生或水灾逃生或地震逃生或智慧交通或复杂系统的自组织行为研究。