处理NP难问题的拟物拟人途径
报告提纲
• NP难度问题
• 启发式算法
• 拟物拟人思想
• 预测蛋白质折叠结构的拟物算法
• 求解不等圆packing问题拟物拟人算法
1. NP难度问题
• 科学研究、通信、交通运输、工程设计和企业管理中涌现出大量NP难度问题。
• NP难度问题共同特征是问题解空间大小为指数规模。如TSP、SAT、调度问题
• NP难问题求解是计算机科学的瓶颈任务
2. 启发式搜索算法
• 近30年研究表明：NP难问题根本不存在既完整严格又不是太慢的求解算法。
• 到大自然去找智慧，以期得到求解NP难问题的非绝对完整但高速高效的近似求解算法。
• 目前流行的启发式方法：
3.拟物拟人思想
• 拟物方法
• 到物理世界中去寻找出与原始数学问题等价的自然现象，然后观察其中物质运动的演化规律，从中受到启发得出形式化的求解算法。
4.预测蛋白质折叠的拟物算法
• 问题背景
– 蛋白质是大分子结构，由若干氨基酸组成
– 蛋白质折叠结构决定蛋白质生物学功能
– 传统方法很难观测出蛋白质折叠结构
– 建立数学模型，通过理论计算方法推算出蛋白质折叠结构
预测蛋白质折叠结构的二维连续模型
• 约束条件：
– 蛋白质视作一列由疏水性氨基酸（H,用 表示）和亲水氨基酸（P,用 表示）组成的链 ，每个小球的半径为1。如HHPHPHPHPHPH。
– 编号相邻的两个球皆相切 。
– 任意两个小球之间互不嵌入 。
满足上述条件的构形称为合法构形
• 优化指标：找出合法构形中能量最低的构形
编号不相邻，但物理位置相切的黑球之间产生的能量为-1.
• 对于任意给定的正整数n和任意地被确定了黑白颜色标号分别为1,2,…,n的n个半径为1的球，问如何调整这n个球的球心在平面上的位置，才能使这n个球两两互不嵌入，标号相邻的两个球皆相切，并且使全部黑球达到尽可能聚合得紧的状态。
形式化表达：
寻求2n个实数使在如下约束关系(1) ,(2)得到满足的条件下，能量(3)达到最小。
拟物算法思想：
• 将n个半径为1的球想象为光滑的弹性实体，想象第i个球与第i+1个球的球心之间有一根原始长度为2的弹簧相连。
• 设想这n个球现在被随机地撒在空间中,不同编号的两球之间会产生如下三种不同类型的作用力：
– 编号相邻的两球之间的弹簧拉力；
– 相互嵌入的两球之间的弹性排斥力；
– 两黑球之间的万有引力。
• 在任一时刻，每一球体受到的总外力即是除自身之外其它n-1个球对它的作用力之和。
• 初始时刻以后每一球体在所受外力驱动之下都会进行运动。运动一段时间后，会逐渐趋于平静 。此时这n个球的位置即是蛋白质结构预测问题的精确解或近似解 。
• 在此过程中弹簧拉力与弹性斥力的作用是在运动中逐渐使约束条件得以满足；而万有引力的作用则是将全体黑球尽量拉拢。
• 将上述物理描述用数学表达式严格地写确切写完整后事实上即得到了我们的拟物算法。
拟物算法形式化描述：
• 第j号球施于第i号球的弹性斥力
其中 为弹性球的倔强系数；
为二球间的嵌入深度 。
• 第j个球施于第i个球的弹簧拉力
其中 二球间弹簧的倔强系数 ；
为i,j两球心之间的距离。
• 第j个黑球施于第i个黑球的万有引力
• 第i个球在任一时刻受到的力为除它自身以外的诸球施于它的各种类型的力的合力 :
• 根据低速运动的牛顿第二定律，可得到如下的体系的运动方程 :
其中 为一个小的正实数常数
• 在依照某种简单合适的考虑或者干脆纯随机地给出几个球心的位置后，每一球体在所受外力驱动之下都会进行运动,当算到t相当大的阶段，计算机显示屏幕上的各球皆已静止，输出此时每个小球的位置即得所求的问题之解 。
• 如遇到“卡壳”情况则从算。
拟物拟人方法研究问题的技术路线
• 基础：先严格地弄清楚这个问题的形式化提法
• 准备：从多个角度细心地体会这个问题的直观味道以及在某些场合下的运动图案。
• 关键：在自然界和人类社会生活中寻求与本问题有某种共同运动图案的特定现象。需要我们有独特的想象力、丰富的科学知识和慧眼观察社会的能力，这样才可能发现所体味的原始数学问题和自然界或人类社会生活中“等价”的特定现象，为我们进一步发现并借助这些现象背后可能蕴涵的“天籁”来开拓解决问题的思路打好基础。
• 提炼：分析运动的动力与制约力的冲突情况，总结这类运动的发生发展以及可能卡壳的规律，提出算法策略。
5.求解不等圆packing问题拟物拟人算法
• 问题描述：
已知一个半径为r圆形的容器，另外又已知M个不同的圆饼，问能否将这些圆饼互不重叠地放进圆形容器。
不等圆packing问题拟物算法思路：
拟物算法步骤：
• 确定初始格局：将M个圆饼随机放在容器中，要求每个圆饼的圆心在容器中；
• 置t=0；
• 计算此时刻每个圆饼所收到的合力，每个圆饼沿合力方向运动一小步。
• t=t+1,重复步骤3，直到t=100000。
拟人策略来源：
• 拟物算法执行结束后，如果M个圆饼互不重叠地放进圆形容器中说明找到了packing问题的解。但是当问题客观上比较困难时，往往会碰到卡壳情形，即每个圆饼收到合力都为0，但并非合法格局。此时不能妄下结论：该packing问题无解
• 纯粹的拟物算法只能重新随机选取初始格局，进行新一轮拟物计算。实验证明这种办法效率不高。
• 有前途的办法是将计算从局部最优陷阱中跳出，而置入到具有更好前景的位置上去，然后接着新的拟物计算。
• “跳出陷阱”的策略可通过观察与体会人类社会现象而得出，因而称为拟人策略。
拟人策略：
• 在拥挤的公共汽车中，收挤压最甚者总是设法改换自己的位置，而处境宽松者往往也会让出一部分空间给予别人。
• 将圆形容器看成公共汽车的车厢，而M个圆饼看成乘客。
• 策略一：挑出挤压最甚的圆饼，将其随机放到容器中某个地方－－压力解除策略。
• 策略二：挑出感受最宽松的圆饼，将其随机放到容器中某个地方－－资源让与策略。
定量描述圆饼的痛苦度
• 圆饼i的绝对痛苦度DPi为自身受到的挤压弹性势能。
• 圆饼i的相对痛苦度RDPi为自身受到的挤压弹性势能。
• 将相对痛苦度RDPi最大的圆饼理解为挤压最甚的圆饼。
• 将绝对痛苦度RDPi最小的圆饼理解为感受最宽松的圆饼。
• 具体拟人跳坑策略：
每次都选择挤压最甚的圆饼，将其随机放到容器中某个地方，在用拟物算法计算，如果连续两次选择的挤压最甚的圆饼都是同一个圆饼，则选择感受最宽松的圆饼。
总结
• 拟物方法本质上是一种主动向大自然学习的方法。由于大自然固有的内在的和谐，用拟物方法得出的算法在求解NP问题时计算得十分顺畅与稳定，效率有时是异乎寻常地高。
• 当拟物计算落入到极小值陷阱的困境时，拟人方法则可以为计算提出好的“跳坑”策略。
• 利用拟物拟人方法还成功求解了Covering问题，矩形packing问题和SAT问题。尤其是将SAT转化为静电场中电荷运动问题,设计了Solar算法，获得第三届SAT快速算法国际竞赛金奖。
谢谢！
欢迎大家提问、讨论