一种求解带时间窗车辆路径问题的混合差分进化算法
时间窗的车辆路径问题进行研究，建立以最小化车辆数量和行驶路程为目标的多目标数学模型，提出一种结合改进差分进化算法和变邻域下降搜索的基于Pareto支配的混合差分进化算法。首先重新定义了个体的生成方式。其次，结合双种群策略和变邻域下降搜索技术来平衡算法的全局探索能力和局部开发能力，并在搜索过程中用随机个体替代种群中的重复个体，维持种群的多样性。然后引入Pareto支配的概念来评价个体的优劣性，并采用擂台法则构造非支配解集其中,N是种群规模,gem为当前进化代数, gem为最大进化按照这种方法,直到所有的顾客都被服务。这种解码方法可代数。以使解码后的路径和解码前染色体中所对应的路径方案·在进化过程中,采用双种群机制,使算法既能从局部极值致,并且使用车辆的数量可以在解码过程中灵活动态地获得,的邻域跳转到全局最优解的邻域,又能在全局最优解的邻域从而实现对车辆数量的自动寻优。例如染色体串361857内进行精细搜索,在每代进化完后通过子种群重组实现信息294,经过路径解码为:路线1:0→3→-6→0;路线2:0→1→8交流和融合,平衡算法的全局探索能力和局部开发能力→57→0;路线3:0→2→9-4→0随着进化过程的进行,种群中的个体会趋于一致,因此在3.3.2初始种群生成每次执行完变异、交义、选择操作后,采用随机个体替换掉种产生初始种群时,为了保证种群的多样性,其中90%的群中的重复个体,维持种群的多样性,以增强种群的全局探索个体采用N个顾客节点随机排列的方式来产生,应用前向插能力,然后从种群中随机选取若干个个体进行变邻域下降搜启发式算法(PFH)来生成剩下10%的个体。索进一步提高算法的局部开发能力降低算法陷入局部最优3.3.3变异操作的风险。鉴于标准差分进化算法采用实数编码,不能直接应用于3.2算法步骤VRPW问题,由于采用了自然数编码,因此重新设计了变异基丁以上的算法思想描述,混合差分进化算法的具体步操作方式来产生变异个体。由标准DE算法可知,变异个体骤如下是由目标种群中随机选择的3个目标个体相互作用的结果步骤1设置算法的相关参数,生成算法的初始种群设记x=[x,x2,…,x]V=[1,2,进化代数gen=0;[uE,1,t2,…,n]分别为第G代目标种群变异种群和试验步骤2根据 Pareto支配思想对种群中的个体适应值进种群的第z个个体。行评价,利用擂台法则和拥挤距离机制将种群个体分层排序,(1)P1子种群采用“DE/best/1”变异策略,重新定义得到每个个体的非支配层等级和拥挤距离值;v=g(F⑧g(x,Y),X)步骤3按照个体的非支配层等级和拥挤距离,并根据式中,1r2是区间[1,n里互不相等的整数;X是当前目式(12)式(13将种群划分为两个不同大小的子群P1和P2标种群中最好的个体,在本文中从非支配层等级序号最小的步骤4P1子群执行DE/bes1变异策略,P2子群执行非支配层中随机选取;F为缩放因子,且F∈[0,门DE/rand/1变异策略,并根据3.3.4节执行交叉操作;式(14)由两部分组成,第一部分为步骤5将初始种群与子群P1、P2重组为一个混合种△=F⑧g(X°,Y)群g(班,X),rand()
- 2020-12-09下载
- 积分：1
上海大学计算机组成原理历年试卷
上海大学计算机组成原理历年试卷，文档形式，内部资料。[X]补=0010011Y]补=00.11001:[-Y]补=10011(7分,过程4分,结果3分)被除数商说明0010011000000被除数与除数同号+1100111+[Y]补I1101000000*0余数语除数异号,商上011101000000*00左移1位011001上次商0,+Y]补011010000*01余数与除数同号,商10011010000*010左移1位+1100111上次商1,+Y]补0000001000*011余数与除数同号,商1000001000*0110左移1位+11001上次商1,十[-Y]补110100100*010余数与除数异号,商0+0010010上次商0,+Y]补11010110*01100余数与除数异号,商01010110冰011000左移1位011001商末位置1结果:0.110012、已知替换算法LRU当前的信息块在登记表中的排序为0、1、2、3、4、5,画图依次表示出在先后使用3、1、4时登记表中信息块排序的变化过程(0)(组分别是3、3、4分)原始使用3使用1使用440原则:把最近使用的资快提到最前面,替换最下面的3、已知内存地址为0~1M单元 Cache地址为01k单元,设每块为256个单元,设计一组组相连 Cache组织。(1)给出数学描述和说明(10)(2)出简图(图中的 Cache块和内存块应标明具体地址)(10描述(10分)具体分两组组相连映像方式是以组为单位,组与组间是直接映像组内是全相连映像例如, cache为4块将 cache分为两组每组512字节,分为两块此时取k=0,1则第j块内存地址映射为j=(i mod 2)*2+kk=0, 1图10分第1页(共6页)上海大学2003~2004学年秋季学期试卷(A卷)课程名:计算机组成原理学分:4(闭卷学号:姓名:院、系:成绩题号四五六七得分得、填空:(每格2分,共20分)l、存储器总体上按照存储介质分为2、存储器接到读/写命令到完成读/写操作所需要时间称为。存储器进行两次连续读/写操作所需要的最小间隔时间称为3、半导体动态RAM靠存储信息。4、直接由计算机硬件执行的程序是5、组成一个32K×8的存储器当分别选用1K×4位、16K×1位、2K×8位的三种不同规格的存储芯片时,各需片。得分、简答题(每题5分,共35分)1、画图并说明32位浮点数的规格化表示,并举例说明其精度及数据范围2、只读存储器分为那几类,各自的功能3、画图表小静态存储器地址信号首先选通时Adr、CS、Dout的开关特性信号次序)。并简述为什么试卷纸第2页(共6页)4、简述为保持 Cache和主存一致性而定义的 Cache的两种写入方式5、简述动态存储器刷新的两种工作方式6、简述段式和页式虚拟存储器的特点7、读写存储器的分类,各自的特点得分三、综合题(45)设X=0.10011,Y=0.11001写出一种两位定点乘法和一种位定点除法的计算过程并给出计算结果(15)FCLLUFLT.TV-了k平小T一廿性XJ试卷纸第3页(共6页)2、已知替换算法LRU当前的信息块在登记表中的排序为0、1、2、3、4、5,画图依次表示出在先后使用3、1、4时登记表中信息块排序的变化过程(10)。命题纸使用说明:1、字迹必须端正,以黑色碳素墨水书写在框线内,文字与试卷纸第4页(共6页)3、已知内存地址为0-M单元, Cache地址为0~1k单元设每块为256个单元,设计一组组相连 Cache组织。(1)给出数学描述和说明(10)(2)画出简图(图中的 Cache块和内存块应标明具体地址)(10)命题纸使用说明:1、字迹必须端正,以黑色碳素墨水书写在框线內,文字与草稿纸第5页(共6页命题纸使用说明:1、字迹必须端正,以黑色碳素墨水书写在框线内,文字与草稿纸第6页(共6贝丿
- 2020-12-03下载
- 积分：1
