首发于微信公众号『运筹OR帷幄』

文章作者：高新

责任编辑：王希杰

2018年10月1日 遗传算法解决TSP

（出自微信群： 【3】Global O.R./OM/IE Community，【2】 Global O.R.optim PhD Community）

张-奥格斯堡-operation：我想通过调节遗传算法参数解决TSP问题，但是我现在调参前后的算法速度和最终的收敛结果都不是很好，并且求解时间也很长（相比别人的例子几百代就得到最优解附近，而我2万代也和最优解有一定差距，并且用时20分钟左右）不知道该从哪方面找原因？

叶-苏宁物流算法工程师：单纯的遗传收敛很慢的吧，得融合些其他算法吧，局部搜索啊，模拟退火啥的

liu-北京大学-组合优化：从交叉和变异算子入手，看看有没有保留局部最优，除此之外分析一下解空间分布。

攀-奥格斯堡大学-bwl：求问：TSPLIB里面数据的最优解后面的单位应该是什么呢，是m，km还是它根本不用管单位

留-海德堡大学 OR AI：不用管吧。。应该是km？

攀-奥格斯堡大学-bwl：我是想如果单位是m，和最优差距是几千的话，这个还比较容易接受，要是km的话差距可能比较大，所以在考虑这个单位问题，还有一个问题，我的改进遗传算法算跑2万代用时86分钟，这个是正常时间吗？跑完结果2483，最优解1019，这个可以理解为正常范围吗？

彭-广州-广工-车间调度： 改进的是哪个部分，同时你的这个结果是只在这个算例下跑的结果偏差有这么大还是所有案例都是这样的？

陆-北京-北航-智能优化：遗传算法求解tsp问题应该不至于这样，遗传算法相对比较容易早熟收敛，建议看下收敛曲线，可以加一些例如2-opt的local search进去看看

成：组合优化问题不把父代选择搞好，用遗传算法效率本身就低。

mathematical optimization -ks-y：我感觉他求的是Vrp，遗传算法不行的

成：用遗传算法解vrp也行，不过得用分支界定把可行的父代先挑出来一部分，直接组合优化效率极低

攀-奥格斯堡大学-bwl：我改进的的是遗传算法选择方法和使用了自适应调节，基本每个数据结果都有比较大的差距，感觉父代开始就比较大，不知道用最近领域法设置一个父代会不会效果好很多，2-opt准备加进去试试看，然后还有算子SI 和 SWAP是代表什么意思呢？这两个算子也是属于局部搜索算子，但是我在网上没有查到他们具体是怎么使用。vrp是什么是什么意思呢？

彭-广州-广工-车间调度：车辆路径问题

攀-奥格斯堡大学-bwl：这个和TSP区别大吗

彭-广州-广工-车间调度：问题规模，你的达到了多少节点？

攀-奥格斯堡大学-bwl：237个城市，这个是比较小的一个数据

陆-北京-北航-智能优化：遗传算法主要是选择 交叉 变异；选择的作用类似提供一个搜索方向，向好的父代学习；交叉的作用是提供一些随机性，横向挖，可以改善早熟收敛问题；变异部分可以加入local search算子 往深里挖，我觉得可以尝试加入模拟退火策略 你这个应该是跳出局部极小的能力偏弱，GASA有相关的论文 可以参考一下。

mathematical optimization -ks-y：我感觉可以和精确算法结合求解

攀-奥格斯堡大学-bwl：嗯嗯 意思是把模拟退火策略加到遗传算法里面对吗？GASA是一个论坛吗？ 用精确算法来完成哪一部分呢？是选父代吗？

mathematical optimization -ks-y：分支定界

攀-奥格斯堡大学-bwl：嗯 我已经单独用了分支定界法求解了一遍，现在要求就是通过遗传算法来求解，然后对比。选择父代最近邻域行的通吗，还有什么比较好方法吗，分支定界是不是也可以用的到

彭-广州-广工-车间调度：初始解的优化可以做一做，一般都有效果的。

2018年10月13日 　遗传算法解决车间调度

（出自微信群：【3】 Global O.R./OM/IE Community）

彭-GDUT-车间调度：求助：有一个遗传算法问题请教，在使用GA算法解决车间调度问题的时候，每一次迭代的最终结果都是不一样，有的时候偏差还比较大，可能的原因是什么？设置参数尝试了：代沟调整0.5~0.9，变异率0.2~-0.01，交叉率0.4~0.6，迭代次数1000/2000/10000；

闫：GA的结果本身就是不稳定的，尤其大规模的时候。

彭-GDUT-车间调度：是一个4*12工序的JSP问题

LI：一般都是多跑几次 挑出来最好的结果。

彭-GDUT-车间调度：那让GA获得结果更稳定一些，是不是只有通过和容易局部收敛的算法混合的途径，比如粒子群算法这一些容易局部收敛的算法？

闫：那就改算法了吧，可以从两方面试试，一个是改进下初始解，不要随机生成种群；另外就是选择策略可以试试精英选择。

2018年9月12日 　 SQL数据处理

（出自微信群： Global O.R./OM/IE Community）

房-科技创新经济学：想请教一个sql数据处理问题。我现在有两个数据表。能对应的只有一个公司代码。但是两个表除了公司代码，别的信息都不一样。而且每个表里同一个公司出现好几次。如果直接按照代码合并，效果不太好。有没有比较好的合并思路?

曹-芝加哥-硕士-运筹学：请问这个数据有多大？

房-科技创新经济学：100多万行

曹-芝加哥-硕士-运筹学：很小的数据，那就是逻辑上的问题，可能是因为公司不unique所以要考虑怎么样才能一一对应，或者用什么逻辑合并才会让sql服务器能够处理。

房-科技创新经济学：刚学sql，所以逻辑不好。看到两个数据表，需要联系起来，就只想到了合并。

曹-芝加哥-硕士-运筹学：每个表同一个公司都出现几次。那你是想怎么合并呢？这样子其实描述挺不完全的…比如说表A有一个公司有三个记录，表B同样有一个公司有3个记录，那么要信息不流失就变成了9个记录了，这样的合并一点都不有效率，还不如要用的时候在考虑怎么合并。

房-科技创新经济学：一个是公司所处地相关政策的数据，可能这个公司所在地不同时间段发布了好几个政策，有时间信息。另一个是某时间段的重大事件，但是没有重大时间的时间信息。最终目的是想看看政策对重大事件频率有没有影响。第二个数据表没有时间信息让我很苦恼，信息脱敏过了。

王-东北大学-OR：感觉如果有时间信息，把第二个表的消息按照表一的时间段 count重大事件的次数，然后就可以和表一 对应合并算频率了

2018年10月13日 　层次聚类与非层次聚类的应用

（出自微信群：【3】 Global O.R./OM/IE Community）

胡-NEI-OR-AI:能不能请教下， 什么时候用hierarchy clustering? 什么时候用non-hierarchy clustering?

郭-合肥工大机器学习：层次聚类一般用在社会科学里边，比如你做市场分析，调查问卷收集回来的数据拿层次聚类；非层次聚类是一大类，有基于密度的聚类，如DBSCAN，有谱聚类，基于概率密度分布的。最主要的区别是，能不能把特殊形状的类别聚出来。

这个是基于概率密度的聚类

这个是谱聚类，适合特殊形状的

这个是层次聚类

这个是基于密度的聚类，DBSCAN

如果你要是拿k-means或者层级聚类对上面特殊形状的数据进行聚类，就会出现错误。聚类算法的区别主要在于数据分布不正常时候才能体现出来，数据分布都是很正常的分布，结果都大差不差。

2018年9月15日 求解高次方程是np完全还是np-hard

（出自微信群： 【2】Global O.R./OM/IE Community）

胡钱元-湖南大学-图的3着色：我有一个问题请教：求解高次方程是np完全还是np-hard？

李优-中科院-全局优化：@胡钱元—湖南大学—图的3着色 高次方程和整数规划有些联系，好像是叫什么gromers基，整数规划的可行解貌似就是高次方程的一个根，因此有点像整数规划的一个比较简单的子问题，具体是不是np，我感觉比一般的np简单些，不太像np，比竟理论上可以通过newton法求解。个人意见欢迎批评。

胡钱元-湖南大学-图的3着色：@李优-中科院-全局优化 你说的是 真的吗？太美好以致让人不敢相信。 如果高次方程求解复杂度不超过np完全问题复杂度，就更显示p=np?的重要程度了——如果有p=np，代数学基本定理将有升级版:高次方程没有根式解，但可在多项式时间内求解。想想就带劲啊！我感觉整系数高次方程的有理解问题是不超过np完全的。一般解都是无理甚至超越的，至少是np-hard。

原文链接：https://mp.weixin..com/s/X4vusBGYUdbShoR4hLeu3g

版权说明：本文由『运筹OR帷幄』编译整理，不作为商业用途，如有内容侵权，我们将随时删除。

欢迎查看原文，获取更多讯息！