研究生面試分組問題的新法解決

蔣思維 王歡

摘 要：本文利用遺傳算法對給定約束條件的面試老師和參與面試學生進行合理組合分配，根據的要求建立了多目標非線性0-1整數規劃模型，解決了研究生面試分組問題。根據題目給定的M、N、T的值，根據建立老師面試學生的關聯矩陣，由四個要求，首先將要求數學化，得到各個要求的約束條件，然后建立了多目標非線性0-1整數規劃模型，結合遺傳算法的特點，解得最優分配方案。

關鍵詞：矩陣編碼;多目標規劃;非線性規劃;遺傳算法

一、問題背景

研究生面試時衡量大學生學習情況和其他綜合能力的重要手段。假設某學校某學院有M個考生經過了初試進入了面試階段，學院準備聘請面試老師N人。面試程序為：每位研究生分別接受T位老師（為該學生的“面試組”）的單獨面試。為了保持面試的公平性，每位老師要獨立的根據學生問題回答情況和綜合各方面進行評分，并且分組應該滿足如下要求：1、每位老師面試的研究生數量應盡量均衡;2、面試不同研究生的“面試組”成員不能完全相同; 3、兩個研究生的“面試組”中有三位老師相同的情形盡量得少;4、被任意兩位老師面試的兩個學生集合中出現相同學生的人數盡量少;

設研究生數M已知，每位研究生分別接受位老師的面試，說明聘請老師數至少分別為多大，才能做到兩位研究生的“面試組”沒有三位面試老師相同的情形。

二、基本假設

假設模型中面試老師人數小于學生人數，每個學生面試時間相等，老師和學生嚴格遵守分配方案，老師性別及其其他環境因素不影響面試結果且每個老師面試評分都公平公正，老師本身情況不影響面試情況。

三、問題

3.1問題的模型建立

3.1.1量化定性條件。C1、每位老師面試的研究生數量應盡量均衡;

根據問題一建立的關聯矩陣，表示學生和老師的面試關系，為，即 =1為第i個老師面試第j個學生，=0表示第i個老師不面試第j個學生，該關聯矩陣為A

要求每位老師面試的研究生書盡量均衡，即：該矩陣A各行之和的方差等于0時，每個老師面試研究生數量相等，接近于零時，數據波動不大，即為均衡。

將各行求和則各行和方差：

即時，分配均衡。

C2、面試不同研究生的“面試組”成員不能完全相同;

C3、兩個研究生的“面試組”中有三位老師相同的情形盡量得少;

本文認為C2、C3條件相似，故予捆綁討論。

當要求有三位老師相同盡量少，引入符號函數=1（x=0時），=0（x≠0時）

當有三位老師相同時，得到：

C4、被任意兩位老師面試的兩個學生集合中出現相同學生的人數盡量得少;

因為要使兩個學生集合相同的學生數盡量少，即為關聯矩陣A中，行為面試老師要面試的學生，列表示每個學生被老師面試人數，則當兩行相減的絕對值取值盡量小時，相同學生數達到最小。

3.1.2目標函數的建立。根據對約束條件的定量分析，結合問題一的分析過程，建立多目標非線性0-1規劃模型：

目標函數為：

3.2問題的模型的分析與求解

3.2.1遺傳算法理論介紹。問題是一個多目標規劃問題，一般整數規劃算法解決起來比較困難，故本文選用遺傳算法來求解。

遺傳算法是根據達爾文的自然選擇學說提出來的，通過模擬進化過程來尋找最優解。從代表問題可能存在潛在解集的一個種群開始的，而個體通過基因編碼組成種群，基因存在于染色體上，染色體攜帶的基因為該個體的特征，決定了每個個體的特征遺傳，作為遺傳的載體。多個基因結合，決定外部表現。所以，基因的編碼決定表現型。

、初始化、確定矩陣編碼方式。該類組合問題是非線性的多峰的較為復雜的問題，常規的進制編碼方式難以解決，根據問題二建立的模型，面試老師和面試學生的分組，約束條件等，用矩陣可以表示出滿足合理分組及約束條件的復雜信息，所以，本文考慮使用基于矩陣的染色體編碼方式。

根據題目要求的四個要求，確定的三個目標約束函數，為其適應度函數。第一個適應度函數為，為方差，是每一行老師指導學生的個數狀況，為老師面試學生數目的和的方差，反應分組均衡情況，該適應度函數越小，分配越均衡。該值越小，越容易被選到。第二個適應度函數為，為三個老師相同的情況，該函數的值越小，有三位老師的情況越少，選取結果越優。該值越小，越容易被選到。

2、篩選。根據適應度函數來篩選，適應度越大，被選中的概率越大，篩選結果作為父代。可以根據適應度輪盤，即根據每個適應度函數的重要性來確定最終適應度函數的所占的概率來確定。

3、交叉變異。進行交叉變異得到相應的子代。該項操作增大種群的多樣性，擴大搜索得到最優解的可能性。本文基于矩陣交叉變異，即父代互換其行或者列，可得到新的矩陣，即交叉變異的子代個體。

根據遺傳算法的迭代步驟，根據流程圖用編程可以得到。

四、模型的評價與推廣

本文通過建立非線性0-1規劃模型，采用該模型能夠較好地對問題進行求解，并且能取得最優解，且結果的誤差不會隨數據的增加而增加。在考慮每位老師面試學生數量均衡的條件下，假定M已知，通過建立的模型，可以得到最小的N。改變M的值，得到相應的最優解N，充分利用了擬合思想，反復多次進行擬合比較，找到了較優的N與M的函數關系，并通過將得到的擬合函數與隨機產生的結果進行對比，說明結果是較優的。

采用遺傳算法求解沒有太多的數學要求，對于任意形式的目標函數和約束，無論是線性的還是非線性的，離散的還是連續的均可處理。進化算子的各態歷經性使得遺傳算法能夠非常有效地進行概率意義地全局搜素，而不會陷入局部最優解的快速下降陷阱。

該模型也具有缺點，第一問的搜索算法，如果不進行優化，要進行很多次搜索，運算量過大。采用遺傳算法求解時，交叉率、變異率等這些參數的選擇大部分是依靠經驗，使得這些參數的選擇嚴重影響解的品質。

本文基于研究生復試時安排面試老師的要求，堅持公開、公平、公正和科學選拔的原則，切實做到以人為本，尊重考生，服務考生的原則。重視做好研究生的招生錄取工作，推動研究生教育的發展。

參考文獻

[1] 邢煥來，潘煒，鄒喜華.一種解決組合優化問題的改進型量子遺傳算法[J].電子學報，2007（10）：1999-2002.

[2] 紀樹新.遺傳算法解決組合優化問題的可行性研究[J].汽車科技，1999（01）：37-39.

[3] 吳值民，鄒赟波，康興擋，盧厚清.學生面試問題[J].數學的事件與識，2007（14）：138-144.

作者簡介：蔣思維（1998-02-），女，漢族，四川簡陽人，本科，四川輕化工大學管理學院，2017級工程管理專業，研究方向：多目標規劃，遺傳算法。

王歡（1999-04-），女，漢族，四川涼山，本科生，四川輕化工大學管理學院2017級工程管理專業，研究方向：多目標規劃，遺傳算法。