今天早上跟学姐室友去复旦把论文答辩做掉了，虽然整个项目基本上是我承担了主要的思路与代码部分，但是今天答辩我跟室友竟然连一句有用的话都没说出来，全场都靠学姐开场流畅地引入，临场随机应变，从而得以与答辩教授欢聚喜散。主要原因是教授竟然准确地问到了我代码里一个细节却相当致命的问题（是一个随机初始化问题，我下面代码部分会详细提到），正好学姐室友都不是特别熟悉我的随机初始化方法，我又不能当场跟他们两个解释这个随机初始化的问题。我差点当场就要以“这样随机初始化能够减少代码量”这种蹩脚的理由跟教授争辩了。好在姜还是老的辣，辩论队队长出身的学姐一顿 Speech Art 操作成功忽悠掉了两位教授，最终两位答辩教授还是认可了我们的模拟仿真方法[捂脸]。事后细想以后我成功也好，失败也罢，恐怕也是成也言语，败也言语。也许我确实能够成为一个有能力的人，但是说话艺术确实是一门很大的学问。不过看我运气一直这么差，大概率还是凡人一个落入俗套吧[摊手]。
言归正传，本文主要介绍我们小组解决全国大学生B题的思路分析，不代表标准答案。当然我还是有自知之明，本身水平不是很高，再加上三天时间限制，自己做出来的模型以及算法肯定是比较差的。这里仅仅从我个人的思考角度出发写一些参考思路作为分享讨论，希望各位读者朋友轻喷。
问题分析
今年的B题确实与往年有很大的不同。往年的数学建模问题往往具有比较好的开放性，问题解决存在较大的建模空间。今年的B题的题干本身就几乎是一个明确的模型（8台CNC+1台RGV+CNC定址），加上第二道任务要求我们根据给定三组数据完成八小时内的RGV详细调度方案，并写入四张Excel表格，给人的感觉就是要求我们去完成一道填空题，然后附带写一篇论文[尴尬]。
为了方便各位读者对赛题的阅读，这里给出链接：/download/cy19980216/10708725
问题一共有四种不同的情况：一道工序无故障，一道工序有故障，两道工序无故障，两道工序有故障。
一道工序无故障
第一种情况是最简单的，直观上直接不停地1234567812345678……按顺序上料差不多就是最优了。但严谨地来说，虽然题目中给的三组数据确实都是用这种最幼稚的策略能够达到最优，但是如果对于一般的情况而言，比如最极端的情况下，RGV移动时间无穷大，那RGV显然就只会不停地在121212121212……这样原地上下料了。
然而我们发现无论参数怎么变化，最终RGV给CNC上下料的过程始终是一个周期性过程。当然这个似乎很“显然”的事实却是相当难以通过数学严格证明的（参数已知的情况下一般比较容易证明，但是所有的参数都是未知的情况下是很难严格说明的）。我赛后也仔细的思考过，但是也没有得出很漂亮的证明。我最终仅仅是针对给定的三组数据使用了遗传算法对RGV前17次上下料（17次是考虑从初始状态开始循环两圈的最短路径）的最优路径进行了搜索，并且利用穷举证明了这是前17步最优的上下料次序。之后基本上就是不断地循环。
这里的模拟退火遗传算法比较鸡肋，所以我不详细说明，在第三种情况我会详细说明模拟退火遗传算法的原理。
以下给出第一种情况的模拟退火遗传算法算法以及对应的穷举最优证明 ↓↓↓
1 # -*- coding:UTF-8 -*- 2 """ 3作者：囚生CY 4平台：CSDN 5时间：/10/09 6转载请注明原作者 7创作不易，仅供分享 8 """ 9 10 import math 11 import random 12 import itertools 13 14 """ 选取一组数据 """ 15 T = 580 16 d1 = 23 17 d2 = 41 18 d3 = 59 19 Te = 35 20 To = 30 21 Tc = 30 22 23 CNCT = [To,Te,To,Te,To,Te,To,Te] # CNC上下料时间 24 25 N = 50 26 L = 17 27 28 varP = 0.1 29 croP = 0.6 30 31 croL = 4 32 e = 0.99 33 34 tm = [ 35[0,0,d1,d1,d2,d2,d3,d3], 36[0,0,d1,d1,d2,d2,d3,d3], 37[d1,d1,0,0,d1,d1,d2,d2], 38[d1,d1,0,0,d1,d1,d2,d2], 39[d2,d2,d1,d1,0,0,d1,d1], 40[d2,d2,d1,d1,0,0,d1,d1], 41[d3,d3,d2,d2,d1,d1,0,0], 42[d3,d3,d2,d2,d1,d1,0,0], 43 ] 44 45 def update_state(state,t): 46length = len(state) 47for i in range(length): 48 if state[i] < t: 49 state[i] = 0 50 else: 51 state[i] -= t 52return state 53 54 def time_calc(seq): 55state = [0 for i in range(8)] # 记录CNC状态 56isEmpty = [1 for i in range(8)] # CNC是否为空？ 57currP = 0 58total = 0 59length = len(seq) 60for No in seq: 61 nextP = No 62 t = tm[currP][nextP] 63 total += t # rgv移动 64 state = update_state(state,t) # 更新state 65 if state[No]==0: # 表明CNC等待 66 if isEmpty[No]: # 当前CNC空 67 t = CNCT[No] 68 isEmpty[No] = 0 69 else: 70 t = CNCT[No]+Tc 71 total += t 72 state = update_state(state,t) 73 state[No] = T 74 else: # 当前CNC忙 75 total += state[No]# 先等当前CNC结束 76 state = update_state(state,state[No])77 t = CNCT[No]+Tc 78 total += t 79 state = update_state(state,t) 80 state[No] = T 81 currP = No 82total += tm[currP][0] 83return total 84 85 def init_prob(sample): 86prob = [] 87for seq in sample: 88 prob.append(time_calc(seq)) 89maxi = max(prob) 90prob = [maxi-prob[i]+1 for i in range(N)] 91temp = 0 92for p in prob: 93 temp += p 94prob = [prob[i]/temp for i in range(N)] 95for i in range(1,len(prob)): 96 prob[i] += prob[i-1] 97prob[-1] = 1 # 精度有时候很出问题 98return prob 99 100 def minT_calc(sample):101minT = time_calc(sample[0])102index = 0103for i in range(1,len(sample)):104 t = time_calc(sample[i])105 if t < minT:106 index = i107 minT = t108return minT,index109110 def init():111sample = []112for i in range(N):113 sample.append([])114 for j in range(L):115 sample[-1].append(random.randint(0,7))116return sample117 118 def select(sample,prob): # 选择119sampleEX = []120for i in range(N): # 取出N个样本121 rand = random.random()122 for j in range(len(prob)):123 if rand<=prob[j]:124 sampleEX.append(sample[j])125 break126return sampleEX127 128 def cross(sample,i): # 交叉129for i in range(len(sample)-1):130 for j in range(i,len(sample)):131 rand = random.random()132 if rand<=croP*(e**i): # 执行交叉133 loc = random.randint(0,L-croL-1)134 temp1 = sample[i][loc:loc+croL]135 temp2 = sample[j][loc:loc+croL]136 for k in range(loc,loc+croL):137 sample[i][k] = temp2[k-loc]138 sample[j][k] = temp1[k-loc]139return sample140 141 def variance(sample,i): # 变异算子 142for i in range(len(sample)):143 rand = random.random()144 if rand<varP*(e**i):145 rand1 = random.randint(0,L-1)146 rand2 = random.randint(0,L-1)147 temp = sample[i][rand1]148 sample[i][rand1] = sample[i][rand2]149 sample[i][rand2] = temp150return sample151152 def main():153sample = init()154mini,index = minT_calc(sample)155best = sample[index][:]156print(best)157for i in range(10000):158 print(i,\ ,minT_calc(sample),end="\t")159 prob = init_prob(sample)160 sample = select(sample,prob)161 sample = cross(sample,i)162 sample = variance(sample,i)163 mi,index = minT_calc(sample)164 if mi>mini and random.random()<e**i: # 精英保留策略165 rand = random.randint(0,N-1)166 sample[rand] = best[:]167 mini,index = minT_calc(sample)168 best = sample[index][:]169 print(best)170pri
