基于TSP問題求解高校寢室分配問題

楊洋

【摘要】針對當(dāng)前大學(xué)生寢室沖突的普遍問題，基于人際吸引理論，將寢室人員依照相同的行為習(xí)慣等方式進(jìn)行分配.對獨立個體是否具備訴求行為進(jìn)行0-1坐標(biāo)賦值.采用坐標(biāo)代替獨立個體進(jìn)行建模，通過計算各坐標(biāo)間的距離定義各獨立個體之間的適應(yīng)度函數(shù)，建立目標(biāo)適應(yīng)度函數(shù)F（x）.將問題轉(zhuǎn)化為一般TSP問題.運用遺傳算法，搜尋目標(biāo)函數(shù)值最優(yōu)解.最后對所得結(jié)果依照寢室入住人員數(shù)目對所得最優(yōu)解結(jié)果路徑進(jìn)行切割得到結(jié)果.

【關(guān)鍵詞】人際吸引；高校寢室；人員分配；TSP問題；遺傳算法

近年來，高校寢室人員因?qū)嬍覂?nèi)部矛盾沖突導(dǎo)致他人死亡案件頻率逐步攀升.在當(dāng)前高校寢室人員矛盾沖突的解決方案中，較多的文獻(xiàn)提到關(guān)于高校學(xué)生心理輔導(dǎo)及組織干預(yù)建議.[1]但面對不同學(xué)生個體，心理輔導(dǎo)等方式操作相對困難.就實際情況而言，單純的心理干預(yù)和組織機(jī)制較難處理此類情況.

一、問題背景

近年來，高校寢室沖突案件頻率逐年攀升.關(guān)于高校寢室人際關(guān)系建設(shè)已逐年成為熱點.通過以“大學(xué)生”并含“寢室人際關(guān)系”作為主題在中國知網(wǎng)查詢近十年來的數(shù)據(jù)，得表1.

表12007年至2016年中國知網(wǎng)用“大學(xué)生”并含“寢室人際關(guān)系”查到的文章數(shù)

年份2007200820092010201120122013201420152016

文章數(shù)25711141221213023

從表1中可明顯觀測到關(guān)于高校寢室人際關(guān)系的熱度近年來不斷攀升，以“復(fù)旦投毒案”為代表的一系列寢室人員關(guān)系沖突矛盾無疑昭示了大學(xué)生寢室人際關(guān)系問題日益突出這一突出現(xiàn)象.

二、模型建立與求解

（一）模型建立

依據(jù)人際吸引理論，個人種族背景等相似程度都會影響人際間的吸引程度[2]，人類更傾向于喜歡在態(tài)度等方面與自己相似的人[3].針對這種情況，建立數(shù)學(xué)模型，按照寢室人員是否具備某種個性行為進(jìn)行合理科學(xué)分配，并對各獨立個體進(jìn)行0-1賦值.以共同生活習(xí)慣為原則標(biāo)準(zhǔn)對寢室人員進(jìn)行分配.由實際情況可知，當(dāng)寢室中存在兩個性格相近的人時，矛盾產(chǎn)生相對較少.且對任意兩個相同坐標(biāo)的獨立個體而言有‖xηi-xηi‖2=0，故將問題可轉(zhuǎn)化為TSP問題.[4]

采用二進(jìn)制編碼代入計算.建立如下數(shù)學(xué)模型：求滿足下式的最優(yōu)路徑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為坐標(biāo)點的坐標(biāo)，ηi是關(guān)于各坐標(biāo)點的一個排列.

（二）問題求解

1.模型求解

遺傳算法是以適應(yīng)度為依據(jù)的逐代搜索過程，運用遺傳算法求解該數(shù)學(xué)模型的主要流程如下：

（1）數(shù)據(jù)編碼.（2）初始化.（3）個體評價.（4）選擇操作.（5）交叉操作.（6）變異操作.（7）終止判斷.（8）輸出結(jié)果.[12]

通過算法計算得到一個最短哈密頓回路.故在結(jié)果基礎(chǔ)上減去通過max函數(shù)所選取‖xi-xj‖2（1≤i≤j≤n）的最大值.得到目標(biāo)函數(shù)的最優(yōu)解.

2.人員分配

對于寢室最大人數(shù)容量m，首先考慮進(jìn)行各坐標(biāo)點上的個體數(shù)量進(jìn)行縮減.若對于在坐標(biāo)xηi上的獨立個體數(shù)目滿足：[card（xηi）/m-1]≥1，則其個體數(shù)量可以縮減為card（x′ηi）=card（xηi）-m*|card（xηi）/m-1|，則問題將簡化為尋找P=（p1，p2，…，pn）的最優(yōu)分配方案，其中pi=card（x′ηi）.

按照否0是1的情況予以賦值，統(tǒng)計得到最終衡量指標(biāo)L值.則得到最終最優(yōu)分配方案.

三、仿真實驗與結(jié)果

（一）參數(shù)取值

本文仿真實驗選取訴求數(shù)k=3，m=6時的2 000份數(shù)據(jù).模型中種群規(guī)模設(shè)定為50，最大迭代次數(shù)為10，PC概率為0.9，Pm概率為0.05.

（二）模型計算

運用算法構(gòu)建初始種群T（0），例如，初始種群中的一個隨機(jī)值X0=（x1x4x3x5x2x7x6x8），其目標(biāo)函數(shù)值f（X0）為9.389.最終結(jié)果X4=（x1x5x6x2x4x8x7x3），其目標(biāo)函數(shù)值f（X4）為7.

（三）人員分配

1.人數(shù)縮減

以x1為例，可對x1坐標(biāo)上的個體進(jìn)行數(shù)量縮減.其縮減后的數(shù)量為card（x′1）=card（x1）-6*|card（x1）/6-1|=8.同理可得P=（8，7，8，7，9，6，6，7）.

2.人員分配

設(shè){x′1}={x11，x12，…，x18}，以此類推，將P中每個個體均賦予個體號予以區(qū)分.

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

故最終將是否產(chǎn)生差異結(jié)果求和可知，在實際寢室人員分配中，該模型所得結(jié)果的最終值為L=6.

【參考文獻(xiàn)】

[1]賀恩格.高校寢室文化矛盾透析[J].長春師范大學(xué)學(xué)報，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的遺傳算法優(yōu)化研究[D].大連：大連理工大學(xué)，2007：15-41.endprint