搜索
应用禁忌搜索算法解决0-1背包问题10-1背包问题其中n＝20；aj=[92,4,43,83,84,68,92,82,6,44,32,18,56,83,25,96,70,48,14,58]；cj=[44,46,90,72,91,40,75,35,8,54,78,40,77,15,61,17,75,29,75,63]；b=878。2禁忌搜索算法的流程给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给给YNYN3禁忌搜索算法各要素的选择禁忌对象的选择：选择了x变量的分量为禁忌对象，这样选择使禁忌表比较简单易实现。邻域的产生：首先在可行域内随机产生200个初始解，找出最好的x作为初始解x0；然后产生x0的邻域，参考2－opt邻域方法，从x0的分量中随机选择两位取反（在可行域内）作为x0的一个邻域解，如此产生60个邻域解（邻域产生函数为near.m）；禁忌表：禁忌表也就是x的各个分量所对应的一个一维数组；禁忌长度：多次测试选择紧急长度为12；禁忌表更新函数为newlist.m。特赦方式：基于评价值的规则，当出现一个解的目标值好于前面任何一个最佳候选解时，特赦；终止原则：采用了限制迭代步数的方法，本次编程迭代步数500。4程序运行结果最终的结果c*x=1024，x=11111111111101010111，此时a*x=871，结果还算不错。需要说明的是，此次编写为了方便使x的第一个分量保持不变，将a和c中的第一项移到了各个的最后，所以得出了以上的最优解x。5思考本次编程完全是自己根据禁忌搜索算法的思想编写，过程中出现了不少问题，解决的过程学了不少新知识，受益匪浅。当然程序编的还不完善，也希望自己有时间再多思考一下。禁忌长度的选择，依据具体问题选择禁忌对象等等都还需要更多的学习，思考。