蔣思維 王歡

摘 要：本文利用遺傳算法對(duì)給定約束條件的面試?yán)蠋熀蛥⑴c面試學(xué)生進(jìn)行合理組合分配，根據(jù)的要求建立了多目標(biāo)非線性0-1整數(shù)規(guī)劃模型，解決了研究生面試分組問(wèn)題。根據(jù)題目給定的M、N、T的值，根據(jù)建立老師面試學(xué)生的關(guān)聯(lián)矩陣，由四個(gè)要求，首先將要求數(shù)學(xué)化，得到各個(gè)要求的約束條件，然后建立了多目標(biāo)非線性0-1整數(shù)規(guī)劃模型，結(jié)合遺傳算法的特點(diǎn)，解得最優(yōu)分配方案。

關(guān)鍵詞：矩陣編碼;多目標(biāo)規(guī)劃;非線性規(guī)劃;遺傳算法

一、問(wèn)題背景

研究生面試時(shí)衡量大學(xué)生學(xué)習(xí)情況和其他綜合能力的重要手段。假設(shè)某學(xué)校某學(xué)院有M個(gè)考生經(jīng)過(guò)了初試進(jìn)入了面試階段，學(xué)院準(zhǔn)備聘請(qǐng)面試?yán)蠋烴人。面試程序?yàn)椋好课谎芯可謩e接受T位老師（為該學(xué)生的“面試組”）的單獨(dú)面試。為了保持面試的公平性，每位老師要獨(dú)立的根據(jù)學(xué)生問(wèn)題回答情況和綜合各方面進(jìn)行評(píng)分，并且分組應(yīng)該滿足如下要求：1、每位老師面試的研究生數(shù)量應(yīng)盡量均衡;2、面試不同研究生的“面試組”成員不能完全相同; 3、兩個(gè)研究生的“面試組”中有三位老師相同的情形盡量得少;4、被任意兩位老師面試的兩個(gè)學(xué)生集合中出現(xiàn)相同學(xué)生的人數(shù)盡量少;

設(shè)研究生數(shù)M已知，每位研究生分別接受位老師的面試，說(shuō)明聘請(qǐng)老師數(shù)至少分別為多大，才能做到兩位研究生的“面試組”沒(méi)有三位面試?yán)蠋熛嗤那樾巍?/p>

二、基本假設(shè)

假設(shè)模型中面試?yán)蠋熑藬?shù)小于學(xué)生人數(shù)，每個(gè)學(xué)生面試時(shí)間相等，老師和學(xué)生嚴(yán)格遵守分配方案，老師性別及其其他環(huán)境因素不影響面試結(jié)果且每個(gè)老師面試評(píng)分都公平公正，老師本身情況不影響面試情況。

三、問(wèn)題

3.1問(wèn)題的模型建立

3.1.1量化定性條件。C1、每位老師面試的研究生數(shù)量應(yīng)盡量均衡;

根據(jù)問(wèn)題一建立的關(guān)聯(lián)矩陣，表示學(xué)生和老師的面試關(guān)系，為，即 =1為第i個(gè)老師面試第j個(gè)學(xué)生，=0表示第i個(gè)老師不面試第j個(gè)學(xué)生，該關(guān)聯(lián)矩陣為A

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

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

即時(shí)，分配均衡。

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

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

本文認(rèn)為C2、C3條件相似，故予捆綁討論。

當(dāng)要求有三位老師相同盡量少，引入符號(hào)函數(shù)=1（x=0時(shí)），=0（x≠0時(shí)）

當(dāng)有三位老師相同時(shí)，得到：

C4、被任意兩位老師面試的兩個(gè)學(xué)生集合中出現(xiàn)相同學(xué)生的人數(shù)盡量得少;

因?yàn)橐箖蓚€(gè)學(xué)生集合相同的學(xué)生數(shù)盡量少，即為關(guān)聯(lián)矩陣A中，行為面試?yán)蠋熞嬖嚨膶W(xué)生，列表示每個(gè)學(xué)生被老師面試人數(shù)，則當(dāng)兩行相減的絕對(duì)值取值盡量小時(shí)，相同學(xué)生數(shù)達(dá)到最小。

3.1.2目標(biāo)函數(shù)的建立。根據(jù)對(duì)約束條件的定量分析，結(jié)合問(wèn)題一的分析過(guò)程，建立多目標(biāo)非線性0-1規(guī)劃模型：

目標(biāo)函數(shù)為：

3.2問(wèn)題的模型的分析與求解

3.2.1遺傳算法理論介紹。問(wèn)題是一個(gè)多目標(biāo)規(guī)劃問(wèn)題，一般整數(shù)規(guī)劃算法解決起來(lái)比較困難，故本文選用遺傳算法來(lái)求解。

遺傳算法是根據(jù)達(dá)爾文的自然選擇學(xué)說(shuō)提出來(lái)的，通過(guò)模擬進(jìn)化過(guò)程來(lái)尋找最優(yōu)解。從代表問(wèn)題可能存在潛在解集的一個(gè)種群開(kāi)始的，而個(gè)體通過(guò)基因編碼組成種群，基因存在于染色體上，染色體攜帶的基因?yàn)樵搨€(gè)體的特征，決定了每個(gè)個(gè)體的特征遺傳，作為遺傳的載體。多個(gè)基因結(jié)合，決定外部表現(xiàn)。所以，基因的編碼決定表現(xiàn)型。

、初始化、確定矩陣編碼方式。該類組合問(wèn)題是非線性的多峰的較為復(fù)雜的問(wèn)題，常規(guī)的進(jìn)制編碼方式難以解決，根據(jù)問(wèn)題二建立的模型，面試?yán)蠋熀兔嬖噷W(xué)生的分組，約束條件等，用矩陣可以表示出滿足合理分組及約束條件的復(fù)雜信息，所以，本文考慮使用基于矩陣的染色體編碼方式。

根據(jù)題目要求的四個(gè)要求，確定的三個(gè)目標(biāo)約束函數(shù)，為其適應(yīng)度函數(shù)。第一個(gè)適應(yīng)度函數(shù)為，為方差，是每一行老師指導(dǎo)學(xué)生的個(gè)數(shù)狀況，為老師面試學(xué)生數(shù)目的和的方差，反應(yīng)分組均衡情況，該適應(yīng)度函數(shù)越小，分配越均衡。該值越小，越容易被選到。第二個(gè)適應(yīng)度函數(shù)為，為三個(gè)老師相同的情況，該函數(shù)的值越小，有三位老師的情況越少，選取結(jié)果越優(yōu)。該值越小，越容易被選到。

2、篩選。根據(jù)適應(yīng)度函數(shù)來(lái)篩選，適應(yīng)度越大，被選中的概率越大，篩選結(jié)果作為父代。可以根據(jù)適應(yīng)度輪盤，即根據(jù)每個(gè)適應(yīng)度函數(shù)的重要性來(lái)確定最終適應(yīng)度函數(shù)的所占的概率來(lái)確定。

3、交叉變異。進(jìn)行交叉變異得到相應(yīng)的子代。該項(xiàng)操作增大種群的多樣性，擴(kuò)大搜索得到最優(yōu)解的可能性。本文基于矩陣交叉變異，即父代互換其行或者列，可得到新的矩陣，即交叉變異的子代個(gè)體。

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

四、模型的評(píng)價(jià)與推廣

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

采用遺傳算法求解沒(méi)有太多的數(shù)學(xué)要求，對(duì)于任意形式的目標(biāo)函數(shù)和約束，無(wú)論是線性的還是非線性的，離散的還是連續(xù)的均可處理。進(jìn)化算子的各態(tài)歷經(jīng)性使得遺傳算法能夠非常有效地進(jìn)行概率意義地全局搜素，而不會(huì)陷入局部最優(yōu)解的快速下降陷阱。

該模型也具有缺點(diǎn)，第一問(wèn)的搜索算法，如果不進(jìn)行優(yōu)化，要進(jìn)行很多次搜索，運(yùn)算量過(guò)大。采用遺傳算法求解時(shí)，交叉率、變異率等這些參數(shù)的選擇大部分是依靠經(jīng)驗(yàn)，使得這些參數(shù)的選擇嚴(yán)重影響解的品質(zhì)。

本文基于研究生復(fù)試時(shí)安排面試?yán)蠋煹囊螅瑘?jiān)持公開(kāi)、公平、公正和科學(xué)選拔的原則，切實(shí)做到以人為本，尊重考生，服務(wù)考生的原則。重視做好研究生的招生錄取工作，推動(dòng)研究生教育的發(fā)展。

參考文獻(xiàn)

[1] 邢煥來(lái)，潘煒，鄒喜華.一種解決組合優(yōu)化問(wèn)題的改進(jìn)型量子遺傳算法[J].電子學(xué)報(bào)，2007（10）：1999-2002.

[2] 紀(jì)樹(shù)新.遺傳算法解決組合優(yōu)化問(wèn)題的可行性研究[J].汽車科技，1999（01）：37-39.

[3] 吳值民，鄒赟波，康興擋，盧厚清.學(xué)生面試問(wèn)題[J].數(shù)學(xué)的事件與識(shí)，2007（14）：138-144.

作者簡(jiǎn)介：蔣思維（1998-02-），女，漢族，四川簡(jiǎn)陽(yáng)人，本科，四川輕化工大學(xué)管理學(xué)院，2017級(jí)工程管理專業(yè)，研究方向：多目標(biāo)規(guī)劃，遺傳算法。

王歡（1999-04-），女，漢族，四川涼山，本科生，四川輕化工大學(xué)管理學(xué)院2017級(jí)工程管理專業(yè)，研究方向：多目標(biāo)規(guī)劃，遺傳算法。