基于轴辐网络的应急设施布局算法

2023-09-19 理论教育版权反馈

【摘要】：在具有8个节点的轴辐网络中，节点3和节点7是枢纽点，非枢纽点分配给枢纽点的情况见分配序列，节点1分配给枢纽3，其值等于3，节点7是枢纽点，其值等于7。上述比例数据均是从遗传算法参数控制的实际实验中得出。首先按照设定的交叉概率选择“枢纽序列”和“分配序列”各一对，在两序列中随机选取同一交叉点，通过交换交叉点的左右两部分构成新的子代个体。

遗传算法是基于随机搜索的最优化启发式算法，是模仿自然界生物进化的过程的算法，被广泛应用于解决各类最优化问题。遗传算法最初是由Holland[106]提出，目前该算法广泛应用于各种领域。遗传算法对问题的可行解进行编码，通过适应度函数构成优胜劣汰、适者生存的“自然环境”，种群通过选择、交叉、变异等不断演化，产生新的更加优良的种群，这样经过若干代的进化，最终求得问题的最优解，本书根据L-SHSCP模型特点，采用设计改进的遗传算法来求解。

1）解的编码

在改进遗传算法中，每一个染色体（可行解）包含两个序列：“枢纽序列”和“分配序列”。每个序列的长度等于网络总节点数目。在“枢纽序列”中，采用0、1编码，1代表该点为枢纽点，0代表此点是非枢纽点。在“分配序列”中，如果节点i分配给节点k，则节点i的值等于k。在“分配序列”中每一个枢纽点分配给其自身，如图4-2所示。在具有8个节点的轴辐网络中，节点3和节点7是枢纽点，非枢纽点分配给枢纽点的情况见分配序列，节点1分配给枢纽3，其值等于3，节点7是枢纽点，其值等于7。

pagenumber_ebook=62,pagenumber_book=52

图4-2　染色体的编码

2）初始种群的生成

在初始种群生成阶段，应提前确定种群大小规模。在L-SHSCP模型中枢纽点的数量是一个决策变量，本算法确定枢纽数量的策略是：在初始种群75%的个体中，从序列[1，…，n/4]中随机选取一个数字作为枢纽点数量P，n代表节点总数；对于其余25%个体的枢纽数量从序列（n/4，…，n/2）随机选取一数字作为枢纽点的数量P，这样算法的初始解的枢纽数量可以达到整个网络节点总数的一半。

为了保证种群的多样性，采用随机抽取策略。同时，为了使得具有较好条件（权重较小）的节点更易成为枢纽点，将各节点按照权重大小依次升序排列，构成“带权重节点序列”。对于初始种群75%个体的枢纽点，从“带权重节点序列”中按照权重从小到大依次选出相应数量的枢纽点，初始种群25%个体的枢纽点则从整个节点序列中随机选出。上述比例数据均是从遗传算法参数控制的实际实验中得出。

例如，在初始种群规模为40，节点总数为48的轴辐网络中，30个个体的枢纽点数目最多可达到8个，按照节点权重从小到大依次选出相应数量的枢纽点；其余10个个体枢纽点数量最多可达到24个，可从整个节点集中随机选出相应数量的枢纽点。

3）选择算子

选择算子是确定如何从父代群体中按照某种方法选址个体遗传到下一代群众中的一个遗传运算。本算法采用由适应度对应的概率分布以轮盘赌确定。每个染色体的适应度函数值是模型中目标函数，即该算法的适应度函数

pagenumber_ebook=63,pagenumber_book=53

4）交叉算子

本算法交叉策略选择单点交叉方法。首先按照设定的交叉概率选择“枢纽序列”和“分配序列”各一对，在两序列中随机选取同一交叉点，通过交换交叉点的左右两部分构成新的子代个体。如果“枢纽序列”实施单点交叉后，子代个体中没有枢纽点，或者枢纽点的个数等于整个网络的节点个数，则舍弃这两类子代个体，对于“分配序列”的任意个体，如果由于“枢纽序列”的交叉原因，节点i分配的节点不是枢纽点，则节点i被重新分配距离其最近的其他枢纽点。

在图4-3中，在A1序列中节点3、7是枢纽点，A2序列中2、6是枢纽点。实施交叉算子后得到：子代（枢纽点是2和7）、子代（枢纽点是3和6）；分配序列实施交叉算子后，得到子代，其中节点2、4、7需要重新分配，因为节点2和7在序列中已经不是枢纽点，同时也对中也要进行相应的调整，得到满足要求的分配序列。