基于随机扰动的FM算法优化

FM algorithm optimization based on random disturbance

文章针对特大规模集成电路划分时采用传统FM算法容易陷入局部最优和对初始解敏感的缺点,提出了一种基于概率的随机扰动移动元胞选择的优化算法。它以符合平衡约束的最高增益元胞作为基准点,将一定增益值偏差范围内的元胞同时作为算法可能选取元胞,根据增益值偏差大小赋予元胞一定的被选取概率,随机选择元胞进行移动。采用基于随机扰动的FM优化算法对实际电路进行划分,实验结果表明能降低算法进入局部最优的概率,降低算法对初始解的敏感,在lg=3,r=0.3时平均割线数减少了33.9%,但算法平均运行时间增加了40.5%。

This paper proposes an optimization algorithm based on probability for randomly disturbance mobile cellular selection, aiming at the shortcomings that the traditional FM algorithm is easy to fall into the local optimum and sensitive to the initial solution when the ULSI is divided. It takes the highest gain cell with balance constraint as the reference point, and takes the cell with a certain gain value deviation as the algorithm to select the cell at the same time, and gives the cell a certain probability of being selected according to the deviation value of the gain value, and randomly selects the cell to move. The experimental results show that the optimization algorithm can reduce the probability of the algorithm entering the local optimum and reduce the sensitivity of the algorithm to the initial solution. when the lg equals 3 and r equals 0.3, the average number of secant cuts is reduced by 33.9% Running time increased by 40.5% .