重庆市工业与应用数学学会(http://artsoncqu.eicp.top/cqsiam Chongqing Society for lndustrial and Applied Mathematics of China)


SCI论坛新闻公告数学建模 → 版主那里有关于npc问题的电子图书


  共有6677人关注过本帖树形打印复制链接

主题:版主那里有关于npc问题的电子图书

美女呀,离线,留言给我吧!
gong
  1楼 | 信息 | 搜索 | 邮箱 | 主页 | UC


加好友 发短信
等级:版主 帖子:167 积分:958 威望:0 精华:0 注册:2003/6/17 10:14:42
  发帖心情 Post By:2003/7/11 9:27:00 [显示全部帖子]

以下是引用wenkejiujiu在2003-7-6 15:22:52的发言: 在学校的今年的第一题中,模拟退火算法,我怎么改变参数也无法达到很好的效果! 比如第二组数据我只能得到430只有的数据可是其精确解是408 第三组数据我只能得到540左右 是不是在较短的时间内就只能得到这种结果呢/ 因为模拟退火算法求最优解的复杂度不穷举都高!!!!! 望回复!!!
不知道你们队的计算时间和控制参数的具体设置,另有两个队采用模拟退火算法,3组数据的解分别是19,408和470,得到了最优解,效果很好,可以交流一下具体参数的设置。关键参数的设置对算法性能影响很大。SA的关键参数包括初始温度t0, 温度更新函数T(t),Markov链长Lk和终止温度tf等,理论上设定的控制参数在实际应用中效果不一定理想,通常只能依据一定的启发式规则或大量试验来加以选取。 另外,可考虑给算法增加一个记忆器,使之能记住搜索过程中遇到过的最好结果,当结束时,将最终解与记忆器中的解比较,取较优者作为最后结果。还可考虑在有记忆的模拟退火算法后链接一个局部搜索算法。

 回到顶部
美女呀,离线,留言给我吧!
gong
  2楼 | 信息 | 搜索 | 邮箱 | 主页 | UC


加好友 发短信
等级:版主 帖子:167 积分:958 威望:0 精华:0 注册:2003/6/17 10:14:42
模拟退火算法的最终解质量和CPU时间  发帖心情 Post By:2003/7/13 10:07:00 [显示全部帖子]

校内竞赛A题是一个NP难题,这类问题被认为不存在求最优解的有效算法。穷举法和分支定界算法等可用于求小型的组合优化问题的最优解,但大型问题(求最优解的算法的计算时间太长,比如,若干月,若干年,无法承受)只能用一些近似算法或启发式算法来求解。 模拟退火算法就是一种启发式算法,适合解大型问题,不一定能保证所得解的最优性。当然,校内竞赛A题给出的三个实例都是小型的,模拟退火算法的效果可能不及穷举法。解大型问题更能显示出模拟退火算法的优越性。 事实上,模拟退火算法的最终解质量和CPU时间呈反向关系,很难两全其美,解决办法只有:折中,即在合理的CPU时间里尽量提高最终解的质量。这涉及到冷却进度表所有参数的合理选取,可参考唐立山等著的《非数值并行算法——模拟退火算法》。 模拟退火算法的计算时间复杂度为O(k Lm t(n) ), 其中Lm是k个Markov链长的最大者,t(n)是问题规模n的多项式函数。

 回到顶部
重庆市工业与应用数学学会成立于2002年12月21日,重庆大学党委书记、重庆市科协主席祝家麟教授担任首届理事长,第二任理事长是数学建模全国组委会委员、重庆赛区主任,重庆大学杨虎教授,现任理事长是杨虎教授