基于TSP问题求解高校寝室分配问题

杨洋

【摘要】针对当前大学生寝室冲突的普遍问题，基于人际吸引理论，将寝室人员依照相同的行为习惯等方式进行分配.对独立个体是否具备诉求行为进行0-1坐标赋值.采用坐标代替独立个体进行建模，通过计算各坐标间的距离定义各独立个体之间的适应度函数，建立目标适应度函数F（x）.将问题转化为一般TSP问题.运用遗传算法，搜寻目标函数值最优解.最后对所得结果依照寝室入住人员数目对所得最优解结果路径进行切割得到结果.

【关键词】人际吸引；高校寝室；人员分配；TSP问题；遗传算法

近年来，高校寝室人员因寝室内部矛盾冲突导致他人死亡案件频率逐步攀升.在当前高校寝室人员矛盾冲突的解决方案中，较多的文献提到关于高校学生心理辅导及组织干预建议.[1]但面对不同学生个体，心理辅导等方式操作相对困难.就实际情况而言，单纯的心理干预和组织机制较难处理此类情况.

一、问题背景

近年来，高校寝室冲突案件频率逐年攀升.关于高校寝室人际关系建设已逐年成为热点.通过以“大学生”并含“寝室人际关系”作为主题在中国知网查询近十年来的数据，得表1.

表12007年至2016年中国知网用“大学生”并含“寝室人际关系”查到的文章数

年份2007200820092010201120122013201420152016

文章数25711141221213023

从表1中可明显观测到关于高校寝室人际关系的热度近年来不断攀升，以“复旦投毒案”为代表的一系列寝室人员关系冲突矛盾无疑昭示了大学生寝室人际关系问题日益突出这一突出现象.

二、模型建立与求解

（一）模型建立

依据人际吸引理论，个人种族背景等相似程度都会影响人际间的吸引程度[2]，人类更倾向于喜欢在态度等方面与自己相似的人[3].针对这种情况，建立数学模型，按照寝室人员是否具备某种个性行为进行合理科学分配，并对各独立个体进行0-1赋值.以共同生活习惯为原则标准对寝室人员进行分配.由实际情况可知，当寝室中存在两个性格相近的人时，矛盾产生相对较少.且对任意两个相同坐标的独立个体而言有‖xηi-xηi‖2=0，故将问题可转化为TSP问题.[4]

采用二进制编码代入计算.建立如下数学模型：求满足下式的最优路径X=（x0，x1，…，xn-1）：

minf（X）.

其中，f（X）=∑n-2i=1‖xηi-xηi+1‖2+‖xη1-xηn‖2-max1≤i≤j≤n‖xηi-xηj‖2，

xηi为坐标点的坐标，ηi是关于各坐标点的一个排列.

（二）问题求解

1.模型求解

遺传算法是以适应度为依据的逐代搜索过程，运用遗传算法求解该数学模型的主要流程如下：

（1）数据编码.（2）初始化.（3）个体评价.（4）选择操作.（5）交叉操作.（6）变异操作.（7）终止判断.（8）输出结果.[12]

通过算法计算得到一个最短哈密顿回路.故在结果基础上减去通过max函数所选取‖xi-xj‖2（1≤i≤j≤n）的最大值.得到目标函数的最优解.

2.人员分配

对于寝室最大人数容量m，首先考虑进行各坐标点上的个体数量进行缩减.若对于在坐标xηi上的独立个体数目满足：[card（xηi）/m-1]≥1，则其个体数量可以缩减为card（x′ηi）=card（xηi）-m*|card（xηi）/m-1|，则问题将简化为寻找P=（p1，p2，…，pn）的最优分配方案，其中pi=card（x′ηi）.

按照否0是1的情况予以赋值，统计得到最终衡量指标L值.则得到最终最优分配方案.

三、仿真实验与结果

（一）参数取值

本文仿真实验选取诉求数k=3，m=6时的2 000份数据.模型中种群规模设定为50，最大迭代次数为10，PC概率为0.9，Pm概率为0.05.

（二）模型计算

运用算法构建初始种群T（0），例如，初始种群中的一个随机值X0=（x1x4x3x5x2x7x6x8），其目标函数值f（X0）为9.389.最终结果X4=（x1x5x6x2x4x8x7x3），其目标函数值f（X4）为7.

（三）人员分配

1.人数缩减

以x1为例，可对x1坐标上的个体进行数量缩减.其缩减后的数量为card（x′1）=card（x1）-6*|card（x1）/6-1|=8.同理可得P=（8，7，8，7，9，6，6，7）.

2.人员分配

设{x′1}={x11，x12，…，x18}，以此类推，将P中每个个体均赋予个体号予以区分.

则按照模型要求.可得具体寝室安排：x11x12x13x14x15x16，x17x18x21x22x23x24，x25x26x27x31x32x33，x34x35x36x37x38x41，x42x43x44x45x46x47，x51x52x53x54x55x56，x57x58x59x61x62x63，x64x65x66x71x72x73，x74x75x76x81x82x83，x84x85x86x87.

故最终将是否产生差异结果求和可知，在实际寝室人员分配中，该模型所得结果的最终值为L=6.

【参考文献】

[1]贺恩格.高校寝室文化矛盾透析[J].长春师范大学学报，2014（4）：133-135.

[2]Kupersmidt，Derosier.Patterson Similarity as the basis for childrens friendship[J].Journal of Social and Personal Relationship，1995（12）：439-452.

[3]Simpson J A，Rholea W S.Attachment theory and close relationships[M].New York：Guilford Press，1994.

[4]朱林杰.基于TSP的遗传算法优化研究[D].大连：大连理工大学，2007：15-41.endprint