一个基于遗传算法的车联网路边单元部署方法

摘要

本发明公开了一种基于遗传算法的车联网路边单元部署方法，目的在于最大化路边单元的部署效益。首先建立路网模型，该路网模型能够描述曲线路段。然后综合考虑各项因素作为权重确立部署效益函数，建立效益模型。路网模型和效益模型共同组成路边单元部署问题模型，将路边单元部署问题转化为搜索最优解问题。最后利用遗传算法对搜索最优解问题进行优化求解。该方法能够找到多个路边单元部署问题的近似最优位置，使其逼近最优部署效益的目标。

主权项

一种基于遗传算法的车联网路边单元部署方法，其特征在于如下步骤：步骤1：建立路网模型将某个路段e表示为e(v_h,v_t,f_t,f_w)，其中v_h为路段e的起点，v_t为路段e的终点，f_t为路段e的路线函数，f_w为路段e的权重函数；步骤2：建立效益模型将路网部署总效益B_n表示如下：$B_n=\underset{e\in U}{\Sigma }\underset{e}{\int }{f}_{w,e}(x,y)\mathrm{ds}+\underset{M_e\in S}{\Sigma }\underset{M_e}{\int }{f}_{w,e}(x,y)\mathrm{ds}---\left(1\right)$其中符号U为n个路边单元的全覆盖路段的集合，符号S为其部分覆盖路段的集合，符号M_e为路段e在路网中所有路边单元的覆盖区域内的部分；步骤3：利用遗传算法对路边单元部署问题进行优化求解步骤3‑1：个体编码方法设P是待求问题的候选解；假设路网中需要部署k个路边单元，每个路边单元在路网中的位置信息为P(x,y)，分别将x和y转换为对应的二进制数据(α₁,α₂,...,α_n)和(β₁,β₂,...,β_n)，得到一个长为2n的(0‑1)串(α₁,α₂,...,α_n,β₁,β₂,...,β_n),则k个路边单元构成一个长度为k*2n的(0‑1)串γ₁,γ₂,...,γ_k*2n；(0‑1)串γ₁,γ₂,...,γ_k*2n和子集P是一一对应的关系；使用长度为k*2n的(0‑1)串γ₁,γ₂,...,γ_k*2n来表示个体P；步骤3‑2：种群初始化随机生成m个长为k*2n的(0‑1)字符串，分别记为P₁,P₂,...,P_m；每个字符串是一个个体，m个个体组成一个初始种群；步骤3‑3：设定适应度函数路边单元的部署效益越大部署效果越好，用路网部署总效益B_n作为适应度值；步骤3‑4：进化策略由于每个个体都是一个(0，1)字符串，采用进化算子对个体实施遗传操作；个体交叉算子为一点交叉，变异算子为一点变异，选择算子采用锦标赛选择法；步骤3‑5：基于前面提出的个体编码及评估值计算策略，使用遗传算法来求解的步骤如下：(1)设置相关参数及个体编码初始化种群规模、最大迭代次数、交叉概率和变异概率等参数，按照步骤3‑1给出的方法对个体进行编码；(2)种群初始化随机生成包含若干个体的初始种群M₁，进化代数i＝1；(3)个体适应度值计算按照步骤3‑3计算初始种群适应度值；个体适应值越大，说明该个体越接近最优解，被遗传到下一代的概率也就越大；(4)对群体进行遗传操作对个体实施交叉和变异操作，生成中间群体；i＝i+1；(5)计算子代个体适应值对第i代种群M_i，按照步骤3‑3计算每个个体的适应值；(6)利用锦标赛选择法选择子代群体(7)计算群体当前一代最坏个体和最好个体，以及到目前为止的最好个体(8)将当前一代最坏个体用目前为止最好个体替代(9)判断是否满足算法终止条件算法的终止条件是，连续进化若干代后没有出现更优个体，或者种群进化代数超过设定的最大迭代次数，转步骤(10)；否则，转步骤(4)；(10)停止进化，输出结果。