基于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