《matlab程序》由会员分享，可在线阅读，更多相关《matlab程序（15页珍藏版）》请在金锄头文库上搜索。
1、1. 已 知 n个 城 市 之 间 的 相 互 距 离 ， 现 有 一 个 推 销 员 必 须 遍 访 这 n个 城 市 ， 并 且 每 个 城 市2. 只 能 访 问 一 次 ， 最 后 又 必 须 返 回 出 发 城 市 。 如 何 安 排 他 对 这 些 城 市 的 访 问 次 序 ， 可 使 其3. 旅 行 路 线 的 总 长 度 最 短 ？4. 用 图 论 的 术 语 来 说 ， 假 设 有 一 个 图 g=(v,e)， 其 中 v是 顶 点 集 ， e是 边 集 ， 设 d=(dij)5. 是 由 顶 点 i和 顶 点 j之 间 的 距 离 所 组 成 的 距 离 矩 阵 ， 旅
2、行 商 问 题 就 是 求 出 一 条 通 过 所 有 顶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， 则 旅 行 商 问 题 的 数 学 模 型
3、为 ：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. ，
4、并 且 随 机 产 生 pop-size个 初 始 染 色 体 ， 每 个 染 色 体 为 1到 18的 整 数 组 成 的 随 机 序 列 。18. 适 应 度 f的 计 算 ： 对 种 群 中 的 每 个 染 色 体 vi， 计 算 其 适 应 度 ， f=d(t(i),t(i+1).19.评 价 函 数 eval(vi)： 用 来 对 种 群 中 的 每 个 染 色 体 vi设 定 一 个 概 率 ， 以 使 该 染 色 体 被 选 中20. 的 可 能 性 与 其 种 群 中 其 它 染 色 体 的 适 应 性 成 比 例 ， 既 通 过 轮 盘 赌 ， 适 应 性 强 的 染 色 体
5、 被21. 选 择 产 生 后 台 的 机 会 要 大 ， 设 alpha (0,1)， 本 文 定 义 基 于 序 的 评 价 函 数 为 eval(vi)=al22. pha*(1-alpha).(i-1) 。 随 机 规 划 与 模 糊 规 划 23. 选 择 过 程 ： 选 择 过 程 是 以 旋 转 赌 轮 pop-size次 为 基 础 ， 每 次 旋 转 都 为 新 的 种 群 选 择 一 个24. 染 色 体 。 赌 轮 是 按 每 个 染 色 体 的 适 应 度 进 行 选 择 染 色 体 的 。25. step1 、 对 每 个 染 色 体 vi,计 算 累 计 概 率 q
6、i， 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编 码 遗 传 算
7、法 原 理 及 应 用 可 以 避 免 这 种 情 况 的 出 现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，
8、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. 变 异 过 程 ： 本 文 采 用 均 匀 多 点 变 异 。 类 似 交 叉 操 作 中
9、 选 择 父 代 的 过 程 ， 在 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
10、2 4 1 2 148. 反 grefenstette编 码 ： 交 叉 和 变 异 都 是 在 grefenstette编 码 之 后 进 行 的 ， 为 了 循 环 操 作49. 和 返 回 最 终 结 果 ， 必 须 逆 grefenstette编 码 过 程 ， 将 编 码 恢 复 到 自 然 编 码 。50.循 环 操 作 ： 判 断 是 否 满 足 设 定 的 带 数 xzome， 否 ， 则 跳 入 适 应 度 f的 计 算 ； 是 ， 结 束 遗 传51. 操 作 ， 跳 出 。52.53.54.55. matlab 代 码56.57.58.59. distTSP.txt60.
11、 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
12、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. inc
13、rease=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=1500
14、00;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.i
15、ncrease=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.
16、%=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
