资源预览内容
第1页 / 共15页
第2页 / 共15页
第3页 / 共15页
第4页 / 共15页
第5页 / 共15页
第6页 / 共15页
第7页 / 共15页
第8页 / 共15页
第9页 / 共15页
第10页 / 共15页
亲,该文档总共15页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
1. 已 知 n个 城 市 之 间 的 相 互 距 离 , 现 有 一 个 推 销 员 必 须 遍 访 这 n个 城 市 , 并 且 每 个 城 市2. 只 能 访 问 一 次 , 最 后 又 必 须 返 回 出 发 城 市 。 如 何 安 排 他 对 这 些 城 市 的 访 问 次 序 , 可 使 其3. 旅 行 路 线 的 总 长 度 最 短 ?4. 用 图 论 的 术 语 来 说 , 假 设 有 一 个 图 g=(v,e), 其 中 v是 顶 点 集 , e是 边 集 , 设 d=(dij)5. 是 由 顶 点 i和 顶 点 j之 间 的 距 离 所 组 成 的 距 离 矩 阵 , 旅 行 商 问 题 就 是 求 出 一 条 通 过 所 有 顶6. 点 且 每 个 顶 点 只 通 过 一 次 的 具 有 最 短 距 离 的 回 路 。7.这 个 问 题 可 分 为 对 称 旅 行 商 问 题 (dij=dji,任 意 i,j=1,2,3, ,n)和 非 对 称 旅 行 商8. 问 题 (dijdji,任 意 i,j=1,2,3, ,n)。9. 若 对 于 城 市 v=v1,v2,v3,vn的 一 个 访 问 顺 序 为 t=(t1,t2,t3,ti,tn),其 中10. ti v(i=1,2,3,n), 且 记 tn+1= t1, 则 旅 行 商 问 题 的 数 学 模 型 为 :11. min l=d(t(i),t(i+1) ( i=1,n)12. 旅 行 商 问 题 是 一 个 典 型 的 组 合 优 化 问 题 , 并 且 是 一 个 np难 问 题 , 其 可 能 的 路 径 数 目13.与 城 市 数 目 n是 成 指 数 型 增 长 的 , 所 以 一 般 很 难 精 确 地 求 出 其 最 优 解 , 本 文 采 用 遗 传 算 法14. 求 其 近 似 解 。15. 遗 传 算 法 :16. 初 始 化 过 程 : 用 v1,v2,v3,vn代 表 所 选 n个 城 市 。 定 义 整 数 pop-size作 为 染 色 体 的 个 数17. , 并 且 随 机 产 生 pop-size个 初 始 染 色 体 , 每 个 染 色 体 为 1到 18的 整 数 组 成 的 随 机 序 列 。18. 适 应 度 f的 计 算 : 对 种 群 中 的 每 个 染 色 体 vi, 计 算 其 适 应 度 , f=d(t(i),t(i+1).19.评 价 函 数 eval(vi): 用 来 对 种 群 中 的 每 个 染 色 体 vi设 定 一 个 概 率 , 以 使 该 染 色 体 被 选 中20. 的 可 能 性 与 其 种 群 中 其 它 染 色 体 的 适 应 性 成 比 例 , 既 通 过 轮 盘 赌 , 适 应 性 强 的 染 色 体 被21. 选 择 产 生 后 台 的 机 会 要 大 , 设 alpha (0,1), 本 文 定 义 基 于 序 的 评 价 函 数 为 eval(vi)=al22. pha*(1-alpha).(i-1) 。 随 机 规 划 与 模 糊 规 划 23. 选 择 过 程 : 选 择 过 程 是 以 旋 转 赌 轮 pop-size次 为 基 础 , 每 次 旋 转 都 为 新 的 种 群 选 择 一 个24. 染 色 体 。 赌 轮 是 按 每 个 染 色 体 的 适 应 度 进 行 选 择 染 色 体 的 。25. step1 、 对 每 个 染 色 体 vi,计 算 累 计 概 率 qi, q0=0;qi=eval(vj) j=1,i;i=1,26. pop-size.27. step2、 从 区 间 (0,pop-size)中 产 生 一 个 随 机 数 r;28. step3、 若 qi-1 step4、 重 复 step2和 step3共 pop-size次 , 这 样 可 以 得 到 pop-size个 复 制 的 染 色 体 。29.grefenstette编 码 : 由 于 常 规 的 交 叉 运 算 和 变 异 运 算 会 使 种 群 中 产 生 一 些 无 实 际 意 义 的30. 染 色 体 , 本 文 采 用 grefenstette编 码 遗 传 算 法 原 理 及 应 用 可 以 避 免 这 种 情 况 的 出 现31. 。 所 谓 的 grefenstette编 码 就 是 用 所 选 队 员 在 未 选 ( 不 含 淘 汰 ) 队 员 中 的 位 置 , 如 :32. 8 15 2 16 10 7 4 3 11 14 6 12 9 5 18 13 17 133. 对 应 :34. 8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1。35.交 叉 过 程 : 本 文 采 用 常 规 单 点 交 叉 。 为 确 定 交 叉 操 作 的 父 代 , 从 到 pop-size重 复 以 下 过36. 程 : 从 0, 1中 产 生 一 个 随 机 数 r, 如 果 r 将 所 选 的 父 代 两 两 组 队 , 随 机 产 生 一 个 位 置 进 行 交 叉 , 如 :37. 8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 138. 6 12 3 5 6 8 5 6 3 1 8 5 6 3 3 2 1 139. 交 叉 后 为 :40. 8 14 2 13 8 6 3 2 5 1 8 5 6 3 3 2 1 141.6 12 3 5 6 8 5 6 3 7 3 4 3 2 4 2 2 142. 变 异 过 程 : 本 文 采 用 均 匀 多 点 变 异 。 类 似 交 叉 操 作 中 选 择 父 代 的 过 程 , 在 r 选 择 多 个 染 色 体 vi作 为 父 代 。 对 每 一 个 选 择 的 父 代 , 随 机选 择 多 个 位 置 , 使 其 在 每 位 置43. 按 均 匀 变 异 ( 该 变 异 点 xk的 取 值 范 围 为 ukmin,ukmax,产 生 一 个 0, 1中 随 机 数 r, 该 点44. 变 异 为 xk=ukmin+r(ukmax-ukmin)) 操 作 。 如 :45. 8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 146. 变 异 后 :47. 8 14 2 13 10 6 3 2 2 7 3 4 5 2 4 1 2 148. 反 grefenstette编 码 : 交 叉 和 变 异 都 是 在 grefenstette编 码 之 后 进 行 的 , 为 了 循 环 操 作49. 和 返 回 最 终 结 果 , 必 须 逆 grefenstette编 码 过 程 , 将 编 码 恢 复 到 自 然 编 码 。50.循 环 操 作 : 判 断 是 否 满 足 设 定 的 带 数 xzome, 否 , 则 跳 入 适 应 度 f的 计 算 ; 是 , 结 束 遗 传51. 操 作 , 跳 出 。52.53.54.55. matlab 代 码56.57.58.59. distTSP.txt60. 0 6 18 4 861. 7 0 17 3 762. 4 4 0 4 563.20 19 24 0 2264. 8 8 16 6 065. %GATSP.m66. function gatsp1()67. clear;68. load distTSP.txt;69. distance=distTSP;70. N=5;71. ngen=100;72.ngpool=10;73. %ngen=input(# of generations to evolve = );74. %ngpool=input(# of chromosoms in the gene pool = ); % size of genepool75. gpool=zeros(ngpool,N+1); % gene pool76. for i=1:ngpool, % intialize gene pool77. gpool(i,:)=1 randomize(2:N) 1;78.for j=1:i-179. while gpool(i,:)=gpool(j,:)80. gpool(i,:)=1 randomize(2:N) 1;81. end82. end83. end84.85. costmin=100000;86. tourmin=zeros(1,N);87. cost=zeros(1,ngpool);88. increase=1;resultincrease=1;89. for i=1:ngpool,90. cost(i)=sum(diag(distance(gpool(i,:),rshift(gpool(i,:);91. end92. % record current best solution93. costmin,idx=min(cost);94.tourmin=gpool(idx,:);95. disp(num2str(increase) minmum trip length = num2str(costmin)96.97. costminold2=200000;costminold1=150000;resultcost=100000;98. tourminold2=zeros(1,N);99. tourminold1=zeros(1,N);100.resulttour=zeros(1,N);101.while (abs(costminold2-costminold1) ;100)&(abs(costminold1-costmin) ;100)&(increase ;500)102.103.costminold2=costminold1; tourminold2=tourminold1;104.costminold1=costmin;tourminold1=tourmin;105.increase=increase+1;106.if resultcostcostmin107.resultcost=costmin;108.resulttour=tourmin;109.resultincrease=increase-1;110.end111.for i=1:ngpool,112.cost(i)=sum(diag(distance(gpool(i,:),rshift(gpool(i,:);113.end114.% record current best solution115.costmin,idx=min(cost);116.tourmin=gpool(idx,:);117.%=118.% copy gens in th gpool according to the probility ratio119.% 1.1 copy twice120.% =0.9 copy once121.% ;0.9 remove122.csort,ridx=sort(cost);123.% sort from small to big.124.csum=sum(csort);125.caverage=csum/ngpool;126.cprobilities=caverage./csort;127.copynumbers=0;removenumbers=0;128.for i=1:ngpool,129.if cprobilities(i) 1.1130.copynumbers=copynumbers+1;131.end1
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号