| 主权项 |
基于移动模式序列与遗传禁忌的集成电路布图方法，其特征是：包括如下步骤：步骤101：开始进行参数设定,N为遗传算法中种群数目，M为每个种群中个体数目，H为一常量，设为100，用来除以每个个体面积代价值，从而得到该个体适应度；RX,RY分别表示放置矩形模块的二维平面内横坐标的最大值，纵坐标的最大值；T表示输入数据的txt文档数据列数，用于表示数组的列；maxgen表示进化的最大代数，pc表示两两交叉概率，pm表示变异概率；R为禁忌表的长度；步骤102：gen=0,初始化种群中模块顺序，有M个模块，随机打乱顺序保存起来，而后根据这些不同的顺序初始化种群中个体的宽、高，随机产生个体的移动模式、旋转模式；其中group[i].indi[j].*，表示第i个种群的第j个个体的属性，其中*可以为w,h,m,n,x,y，则分别表示第j个模块的宽，高，移动模式中的数值为0,1,2,3中的一值，旋转模式中用0表示不旋转，1表示矩形模块的长和宽互换，模块左下角横坐标，左下角纵坐标；group[i].cost和group[i].fitness分别表示第i个种群的面积代价和适应度；LTR[j].*，Edgy[j].*，其中*可以表示为xr，yb，yt，分别表示第j个模块平行y轴放置时，右边界横坐标，左边界下端点的纵坐标，左边界上端点的纵坐标；BTT[j].*，Edgx[j].*，其中*可以表示为xl，xr，yt，分别表示第j个模块平行x轴放置时，下边界左端点横坐标，下边界右端点的横坐标，下边界的纵坐标；步骤103：将初始化后的个体根据移动模式和旋转模式在二维 平面内进行放置，从而计算出每个个体的面积代价以及适应度；步骤104：判断是否满足条件gen<maxgen，若是，则转向步骤111，输出最优值，否则转向步骤105；步骤105：用轮盘赌对个体进行选择；步骤106：禁忌搜索进行局部优化；将选择后的个体作为初始解，置空禁忌表，j=0,用2‑opt进行邻域搜索，相当于变异，每次变其模块顺序或者移动模式，用移动模式序列计算适应度，将适应度最大的一个候选解作为当前解,j自动加1，重复邻域搜索的过程，直至满足终止条件；以此产生交叉、变异的初始种群；步骤107：随机产生（0,1）之间的随机数t，若t<pc，则随机选择两不同个体进行两点交叉，并用移动模式序列计算适应度.重复步骤107，直至满足终止条件；pc为交叉概率；步骤108：随机产生（0,1）之间的随机数t，若t<pm，则随机选择一个个体进行单点变异，用移动模式序列计算适应度.重复步骤108，直至满足终止条件；pm为变异概率；步骤109：将所得到的种群按适应度从高到低进行排序，并将每代中的第一个个体存放在一结构体数组中，便于保留历代中的最优个体；步骤110：gen自动加1，转步骤104；步骤111：输出最优结果，结束循环。 |
