基图理计算机网络k划分优化遗传算法
黄新力 严广乐
（海理工学理学院 200093）
摘 文分析网络划分优化问题实质提出运图划分理该问题加研究结合问题身特点设计种改进型遗传算法该算法适应度函数设计遗传操作算子参数选取等方面典遗传算法进行改进实际研究结果表明该算法实现计算机网络动划分优化目算法性优典遗传算法
关键词 遗传算法 图 k划分 网络划分优化
1 引言
计算机网络设计理中改善网络性时便网络实施控制理采取效手段整网络划分较相独立子网(该问题称网络k划分优化问题里k指划分子网数)网络k划分优化问题属组合优化范畴根输入数信息网络基拓扑模型寻找佳网络配置NP完全问题该问题研究计算复杂度网络规模需划分子网数k增急剧增加传统启发式搜索方法已力年遗传算法已引入该问题求解中遗传算法作种全局优化搜索算法身具全局收敛性隐含行性加简单易鲁棒性强够轻易获问题全局优解问题越复杂相算法优越性越明显十分适合解决类问题应典遗传算法求解网络k划分优化问题时求解时间长求优解成功率低必针该具体应问题特点典遗传算法加改进
文针研究问题——网络k划分优化问题实质进行理分析应图划分优化理加研究结合网络k划分优化问题具体特征设计种改进遗传算法动实现规模网络k划分优化该算法中通改进适应度函数遗传操作算子参数选取充分利遗传算法全局搜索力增强遗传算法局部搜索力算法求解网络k划分优化问题中具较快收敛速度较高成功率
2 问题描述
21 网络k划分原
a) 子网间通信流量应彼间通信量较少网络节点分配
子网中减少通网络互连设备开销
b) 子网通信流量应彼间通信量较通信频繁网络节点分
配子网中提高子网资源利率增强子网聚力
c) 子网流量应量趋衡保证网络负载均衡防止新增网络设备
导致子网性急剧降
22 网络流量分布模型
网络划分重网络中意站点间通信量采网络流量分布矩阵描述网络中流量分布状况假设网络中n节点网络流量分布矩阵表达式出：
（） （1）
里元素wij代表第i站点第j站点间链路总流量wijwji 成立
通流量分布矩阵计算出网络总流量服务器输入输出总流量：
（2）
（3）
通述网络k划分问题划分原网络流量分布模型分析知该问题实质研究图划分问题图顶点集划分互相交k子集求子集间联系少种划分应图划分优化理问题加研究
3 图划分优化理
图划分优化理概述：
定义 图中顶点集合边集合定义边权值现图划分顶点子集称图k划分求划分
（4）
中
图中边权值常量求属划分顶点间边权值值问题实际求划分顶点间边权值值问题（4）式式等价：
（5）
中
4 算法设计
41 典遗传算法足
⑴ 图k划分问题划分子集空少必须包含顶点
典遗传操作（尤交叉操作）保证满足约束条件需进行修正
⑵ 网络k划分问题属约束优化问题典遗传算法产生非法解时丢弃合
法解产生概率较低时该方法浪费量CPU时间需针问题约束条件构造算子编码保证产生合法解时收敛速度较快
42 典遗传算法改进
421 编码表示
编码表示方案选取程度赖问题性质遗传算子设计文采取直接解表现型进行遗传操作然数编码方式设网络n节点根需欲划分k子网染色体（问题解）表示：
中
例具30站点网络划分3子网某种网络划分编码图1示：
染色体si：
1
1
0
2
0
2
…
1
0
网 络：
节点1
节点2
节点3
节点4
节点5
节点6
…
节点29
节点30
图1 基型编码示意图
422 适应度函数定义
根图k划分定义划分原定义适应度函数f(x)：
中
中o(x)式（5）中目标函数面第二等号面第项r惩罚系数0u
0 x合法解时
1
423 选择操作
保持适中选择压力文采转盘式选择策略先计算出体相适应值记然基进行选择操作
424 改进杂交操作
避免破坏模式（Schema）文采两交叉点位置相距较两点杂交算子外避免产生空划分解杂交操作引入空划分检查校正操作图2示：
父体A：
000101030202
两点交叉
000102020102
检查校正
000103020102
父体B：
000302020103
000301030203
000301030203
图2 改进杂交操作示意图
425 变异操作
变异操作搜索遍整体空间网络k划分角度变异操作网络节点划分中进行重新分配维持种群样性防止出现早熟现象算法中变异操作典概率发生概率（100）发生采取连续次进行等基位换操作实现变异时鉴变异幅度会破坏优解换次数较少
43 算法描述
述求解网络k划分优化问题改进遗传算法描述：
{
机产生初始化种群X(0){x1(0)x2(0)…xn (0)} n：种群规模
t0 t：演化代数初值t 0
根适应度函数定义计算X(0)中体适应度值f(xi)
while(fmax(x(t)) fmin(x(t))>ε) fmax(x(t)) fmin(x(t))>ε停机准
{
计算种群X(t)中体适应度值例确定选择概率pi
for(k1k≤nkk+2)
{
根选择概率pi转盘式选择策略X(t)中选择两体xaxb
概率pm体xaxb执行变异操作两新体xamxbm
rdmrandom[01]
if(rdm≤pc) pc杂交概率
{
体xamxbm执行杂交操作两新体xamcxbmc
体xamcxbmc执行空划分检查校正操作两新体x1x2
}
else
{
x1 xam
x2 xbm
}
x1x2插入新种群X(t+1)中
}
计算X(t+1)中体适应度值X(t)中适应度值体xmax(t)换X(t+1)
中适应度值体xmin(t+1)
tt+1
}
输出X(t)
}
5 算法收敛性分析
定理[2]：选择算子前保留前解SGA概率收敛全局优解
文设计算法属种群非重叠遗传操作重叠结构SGA（Simple Genetic
Algorithm）选择操作前保留前解定理该算法概率收敛全局优解
6 实验研究
实验具30节点网络进行3子网划分优化运述改进遗传算法次试验统计分析兼顾运算速度网络划分配置解优化算法中选取种群n100交叉概率pc095变异概率pm100停机准参数001问题约束条件∣SubNet0∣∣SubNet1∣∣SubNet2∣10中SubNetk第k子网中网络节点数目k012第k划分惩罚系数仅SubNetk10时u0否u1
表1该改进遗传算法典遗传算法划分结果进行较出前者子网流量总体较者提高流量3子网中分配更均衡子网间流量低者子网间流量网络总流量110表明网络通信流量基子网部流动子网负载较均衡满足21节中网络划分原证明该改进算法效性优典遗传算法
表1 实际网络划分结果
网络划分算法
改进网络k划分遗传算法
典遗传算法
子网流量（）
2927~3566~2628
2745~3929~2176
子网间流量（）
879
1150
表2考察空划分检查校正操作算法性影响实验结果表明引入检查校正操作然算法收敛时间增加成功率明显增加算法性改进
表2 空划分检查校正操作算法性影响结果较
空划分检查校正操作
空划分检查校正操作
求解均时间（ms）
8765
6637
成功率（）
941
816
表3考察变异概率pm分取值时算法性影响结果表明着pm增算法收敛局部优性明显减采100变异概率算法性达佳
表3 变异概率pm分取值时算法性影响结果较
变异概率pm
100
060
030
001
求解均时间（ms）
8765
5334
3627
2294
成功率（）
941
836
782
611
述实验结果表明文设计网络k划分优化问题改进遗传算法正确高效
7 结讨
文利图划分理研究网络k划分问题基础针该问题特点典遗传算法解决该类问题足通适应度函数设计遗传操作参数选取等方面加改进设计种改进遗传算法通具体网络k划分优化问题中成功应克服典遗传算法缺陷提高算法性证明该改进算法合理性效性外引入更效遗传操作确定适应性更高惩罚函数算法适更宽松灵活约束条件进步研究问题
参考文献
1 陈国良 王煦法 庄镇泉等 遗传算法应 民邮电出版社1996
2 潘正君 康立山 陈毓屏 演化计算北京 清华学出版社1998
3 Songerwala M Efficient solutions to the network division problem [thesis]the Curtin University of Technology 1994
4 LaszewskiVGregor Intelligent structural operators for the kway graph partitioning problem ICGA’97Morgan Kaufman1991
Design a Genetic Algorithm for Optimizing kWay Networks Partitioning Problem Based on Directionless Graph Theory
Huang Xinli Yan Guangle
(School of ManagementUniv of Shanghai for Sci & TechShanghai 200093China)
Abstract The Optimization of kway networks partitioning is a problem of combination Optimizationand the classical genetic algorithms (SGA) can not solve the problem efficiently In this Paperthe theory of multiway graph partitioning is applied to analyze the problemand an improved genetic algorithm is presented based on the characteristics of the problem The algorithm is improved in the following three aspects the definition of fitness functionthe genetic operators and the parameters selection Some experimental results in an application example have verified the validity and efficiency of the algorithm
Keywords Genetic algorithm Directionless graph kWay partitioning Optimization of networks partitioning
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档
黄新力 严广乐
（海理工学理学院 200093）
摘 文分析网络划分优化问题实质提出运图划分理该问题加研究结合问题身特点设计种改进型遗传算法该算法适应度函数设计遗传操作算子参数选取等方面典遗传算法进行改进实际研究结果表明该算法实现计算机网络动划分优化目算法性优典遗传算法
关键词 遗传算法 图 k划分 网络划分优化
1 引言
计算机网络设计理中改善网络性时便网络实施控制理采取效手段整网络划分较相独立子网(该问题称网络k划分优化问题里k指划分子网数)网络k划分优化问题属组合优化范畴根输入数信息网络基拓扑模型寻找佳网络配置NP完全问题该问题研究计算复杂度网络规模需划分子网数k增急剧增加传统启发式搜索方法已力年遗传算法已引入该问题求解中遗传算法作种全局优化搜索算法身具全局收敛性隐含行性加简单易鲁棒性强够轻易获问题全局优解问题越复杂相算法优越性越明显十分适合解决类问题应典遗传算法求解网络k划分优化问题时求解时间长求优解成功率低必针该具体应问题特点典遗传算法加改进
文针研究问题——网络k划分优化问题实质进行理分析应图划分优化理加研究结合网络k划分优化问题具体特征设计种改进遗传算法动实现规模网络k划分优化该算法中通改进适应度函数遗传操作算子参数选取充分利遗传算法全局搜索力增强遗传算法局部搜索力算法求解网络k划分优化问题中具较快收敛速度较高成功率
2 问题描述
21 网络k划分原
a) 子网间通信流量应彼间通信量较少网络节点分配
子网中减少通网络互连设备开销
b) 子网通信流量应彼间通信量较通信频繁网络节点分
配子网中提高子网资源利率增强子网聚力
c) 子网流量应量趋衡保证网络负载均衡防止新增网络设备
导致子网性急剧降
22 网络流量分布模型
网络划分重网络中意站点间通信量采网络流量分布矩阵描述网络中流量分布状况假设网络中n节点网络流量分布矩阵表达式出：
（） （1）
里元素wij代表第i站点第j站点间链路总流量wijwji 成立
通流量分布矩阵计算出网络总流量服务器输入输出总流量：
（2）
（3）
通述网络k划分问题划分原网络流量分布模型分析知该问题实质研究图划分问题图顶点集划分互相交k子集求子集间联系少种划分应图划分优化理问题加研究
3 图划分优化理
图划分优化理概述：
定义 图中顶点集合边集合定义边权值现图划分顶点子集称图k划分求划分
（4）
中
图中边权值常量求属划分顶点间边权值值问题实际求划分顶点间边权值值问题（4）式式等价：
（5）
中
4 算法设计
41 典遗传算法足
⑴ 图k划分问题划分子集空少必须包含顶点
典遗传操作（尤交叉操作）保证满足约束条件需进行修正
⑵ 网络k划分问题属约束优化问题典遗传算法产生非法解时丢弃合
法解产生概率较低时该方法浪费量CPU时间需针问题约束条件构造算子编码保证产生合法解时收敛速度较快
42 典遗传算法改进
421 编码表示
编码表示方案选取程度赖问题性质遗传算子设计文采取直接解表现型进行遗传操作然数编码方式设网络n节点根需欲划分k子网染色体（问题解）表示：
中
例具30站点网络划分3子网某种网络划分编码图1示：
染色体si：
1
1
0
2
0
2
…
1
0
网 络：
节点1
节点2
节点3
节点4
节点5
节点6
…
节点29
节点30
图1 基型编码示意图
422 适应度函数定义
根图k划分定义划分原定义适应度函数f(x)：
中
中o(x)式（5）中目标函数面第二等号面第项r惩罚系数0
0 x合法解时
1
423 选择操作
保持适中选择压力文采转盘式选择策略先计算出体相适应值记然基进行选择操作
424 改进杂交操作
避免破坏模式（Schema）文采两交叉点位置相距较两点杂交算子外避免产生空划分解杂交操作引入空划分检查校正操作图2示：
父体A：
000101030202
两点交叉
000102020102
检查校正
000103020102
父体B：
000302020103
000301030203
000301030203
图2 改进杂交操作示意图
425 变异操作
变异操作搜索遍整体空间网络k划分角度变异操作网络节点划分中进行重新分配维持种群样性防止出现早熟现象算法中变异操作典概率发生概率（100）发生采取连续次进行等基位换操作实现变异时鉴变异幅度会破坏优解换次数较少
43 算法描述
述求解网络k划分优化问题改进遗传算法描述：
{
机产生初始化种群X(0){x1(0)x2(0)…xn (0)} n：种群规模
t0 t：演化代数初值t 0
根适应度函数定义计算X(0)中体适应度值f(xi)
while(fmax(x(t)) fmin(x(t))>ε) fmax(x(t)) fmin(x(t))>ε停机准
{
计算种群X(t)中体适应度值例确定选择概率pi
for(k1k≤nkk+2)
{
根选择概率pi转盘式选择策略X(t)中选择两体xaxb
概率pm体xaxb执行变异操作两新体xamxbm
rdmrandom[01]
if(rdm≤pc) pc杂交概率
{
体xamxbm执行杂交操作两新体xamcxbmc
体xamcxbmc执行空划分检查校正操作两新体x1x2
}
else
{
x1 xam
x2 xbm
}
x1x2插入新种群X(t+1)中
}
计算X(t+1)中体适应度值X(t)中适应度值体xmax(t)换X(t+1)
中适应度值体xmin(t+1)
tt+1
}
输出X(t)
}
5 算法收敛性分析
定理[2]：选择算子前保留前解SGA概率收敛全局优解
文设计算法属种群非重叠遗传操作重叠结构SGA（Simple Genetic
Algorithm）选择操作前保留前解定理该算法概率收敛全局优解
6 实验研究
实验具30节点网络进行3子网划分优化运述改进遗传算法次试验统计分析兼顾运算速度网络划分配置解优化算法中选取种群n100交叉概率pc095变异概率pm100停机准参数001问题约束条件∣SubNet0∣∣SubNet1∣∣SubNet2∣10中SubNetk第k子网中网络节点数目k012第k划分惩罚系数仅SubNetk10时u0否u1
表1该改进遗传算法典遗传算法划分结果进行较出前者子网流量总体较者提高流量3子网中分配更均衡子网间流量低者子网间流量网络总流量110表明网络通信流量基子网部流动子网负载较均衡满足21节中网络划分原证明该改进算法效性优典遗传算法
表1 实际网络划分结果
网络划分算法
改进网络k划分遗传算法
典遗传算法
子网流量（）
2927~3566~2628
2745~3929~2176
子网间流量（）
879
1150
表2考察空划分检查校正操作算法性影响实验结果表明引入检查校正操作然算法收敛时间增加成功率明显增加算法性改进
表2 空划分检查校正操作算法性影响结果较
空划分检查校正操作
空划分检查校正操作
求解均时间（ms）
8765
6637
成功率（）
941
816
表3考察变异概率pm分取值时算法性影响结果表明着pm增算法收敛局部优性明显减采100变异概率算法性达佳
表3 变异概率pm分取值时算法性影响结果较
变异概率pm
100
060
030
001
求解均时间（ms）
8765
5334
3627
2294
成功率（）
941
836
782
611
述实验结果表明文设计网络k划分优化问题改进遗传算法正确高效
7 结讨
文利图划分理研究网络k划分问题基础针该问题特点典遗传算法解决该类问题足通适应度函数设计遗传操作参数选取等方面加改进设计种改进遗传算法通具体网络k划分优化问题中成功应克服典遗传算法缺陷提高算法性证明该改进算法合理性效性外引入更效遗传操作确定适应性更高惩罚函数算法适更宽松灵活约束条件进步研究问题
参考文献
1 陈国良 王煦法 庄镇泉等 遗传算法应 民邮电出版社1996
2 潘正君 康立山 陈毓屏 演化计算北京 清华学出版社1998
3 Songerwala M Efficient solutions to the network division problem [thesis]the Curtin University of Technology 1994
4 LaszewskiVGregor Intelligent structural operators for the kway graph partitioning problem ICGA’97Morgan Kaufman1991
Design a Genetic Algorithm for Optimizing kWay Networks Partitioning Problem Based on Directionless Graph Theory
Huang Xinli Yan Guangle
(School of ManagementUniv of Shanghai for Sci & TechShanghai 200093China)
Abstract The Optimization of kway networks partitioning is a problem of combination Optimizationand the classical genetic algorithms (SGA) can not solve the problem efficiently In this Paperthe theory of multiway graph partitioning is applied to analyze the problemand an improved genetic algorithm is presented based on the characteristics of the problem The algorithm is improved in the following three aspects the definition of fitness functionthe genetic operators and the parameters selection Some experimental results in an application example have verified the validity and efficiency of the algorithm
Keywords Genetic algorithm Directionless graph kWay partitioning Optimization of networks partitioning
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档