SmartLab

华科SmartLab实验室本科生实习项目

图着色问题

• 禁忌搜索

一开始自己写的时候并不能成功搜索出结果，后来参照PPT中给出的伪代码的步骤一步一步的对比修改原先的代码，基本实现了搜索效果。 目前最优的代码迭代速度约有20~30万次每秒，最高的可以到90万次每秒。

IDE：code blocks16.2

CPU：Intel Core i7-6700HQ 2.6GHZ

• 各类算例实现结果

  算例	理论值	实际解	耗时
  DSJC125.1	5	5	0.0026
  DSJC125.5	17	17	0.458
  DSJC125.9	44	44	0.062
  DSJC250.1	8	8	0.198
  DSJC250.5	28	28	40.295
  DSJC250.9	72	72	10.9491
  DSJC500.1	12	12	125.834
  DSJC500.5	48	50	30.324

• 实现心得

1.多个最优解时一定要随机选取。开始就是因为没有随机，而是固定的选取第一个解，结果导致搜索效果很差。

2.最后500.5的49种颜色最后总会有1、2个（小概率会有3个，也有小概率可以搜出解）冲突数，然后会陷入局部最优出不来。听了老师的建议按频率数加入新的禁忌步长，但感觉似乎并没有太明显的变化，也有可能是这部分冲突数加入的并不正确...后面会继续调试。

3.另外昨天刚在网上找到了一个代码，虽然搜索的结果和我的代码差不多，但是迭代的速度明显高于我，每秒可以到50~80多万次...正在学习那个代码中

4.感觉禁忌步长所加的随机数的微调对不同的算例会有不同的效果，有的算例可能随机数10个就可以，有的大一点的算例可能要需要稍微将随机数增加2~3个。

• 混合进化

演化进化的代码部分倒是已经写完了，初步测试过感觉交叉算符也没有问题，不过在跑混合部分的时候并没有出很好的结果，感觉可能还是禁忌部分写的不够好，进化一次的时间很长，大概8、9代后就会进化不动。