校内多点送快递的最短路径问题.ppt

校内多点送快递的最短路径问题
报告人
内容
问题描述
①②
算法设计
实验设计
结果分析
实验总结
问题描述
校内多点送快递的最短路径问题
高校占地面积大,建筑多且分布不均匀
·快递员需要不重复且不遗漏地送快递到
各建筑物区送快递
寻找一条最优路径,使送快递所走路程
最短
问题描述
800
◆建分市
0
1000
1500
2500
用(xy)定义建筑物位置,建筑物包括、、在内的19个建筑
物
算法设计
编码设计
·采用的实数编码的形式
·染色体中基因的值表示建筑,基因的顺序表示所
访问建筑的顺序
种群大小:100
染色体
1675120413|176
5|182|38109
算法设计
染色体的交叉
·单切点交叉方式
·子代1直接复制父代1的切点处的前半部分,后半部分的
值在父代2中依次寻找与切点前面不重复的数字填到剩下
的基因格中
父代
子代1
3|2547158
2|s4178s
子代2
2435:76s
算法设计
染色体的变异
互换变异
即随机地选择两个位置,并将两个位位置上的城市相互
交换
父代
基因互换后:子代5
23|74619
算法设计
选择策略
选择策略:最佳个体保存法的一种变异方法
·预先优秀个体的保存比例,选择前将种群中的个体按从」
小到大排序(用冒泡排序法),删除排序在后的个体,用排
序在前的优秀个体替代
实验设计开)
计其建筑间距离,
(率
操乍
受异操乍
用冒泡排序选择母次最
出,且用操留比例
去保宣优秀个体
实验设计
初始化种群函数
void Initialparent(struct unit poplpop size)
struct unit
for(i=0 I<pop sIze,++)∥初始化种群里的个体
p=&pop[;/指向种群的第个个体
for〔j=0j< citynum; J++)∥生成19个建筑间的一个随机路径
if(==0)p->path=Random(0, citynum-1)
eIse
p->path[]=Random(0, citynum-1)
while(k<j)∥/与之前建筑重复,重新生成一个建筑
[if(p->path[==p->path[k]p->path[]=Random(0, citynum-1): k=0; 1
else k++
evaluat(p)