陳 香

（湖南外貿(mào)職業(yè)學院，湖南 長沙410000）

面試是一種經(jīng)過組織者精心設計，在特定場景下，以考官對考生的面對面交談與觀察為主要手段，由表及里測評考生的知識、能力、經(jīng)驗等有關素質(zhì)的一種考試活動。面試是公司挑選職工的一種重要方法。面試給公司和應招者提供了進行雙向交流的機會，能使公司和應招者之間相互了解，從而雙方都可更準確做出聘用與否、受聘與否的決定。

遺傳算法GA(genetic algorithm)作為一種解決復雜問題的有效方法，是由美國密執(zhí)安大學的John Holland教授于1975年首先提出來的，這種算法是以達爾文的生物進化論為啟發(fā)而創(chuàng)建的，是基于生物進化中自然選擇、適者生存和物種遺傳思想的搜索算法。特別適合求解非線性整數(shù)規(guī)劃問題。也適用于本文所建立的面試工作安排問題求解。

為了有效求解如何進行面試專家組成員工作安排使面試公正客觀的問題，本文對問題進行探討，建立其數(shù)學模型，為復雜的非線性整數(shù)規(guī)劃問題。提出一種裝箱編碼、多點交叉、領域搜索變異的遺傳算法對數(shù)學模型進行求解，并用一個30名專家對300名人才進行面試，每個面試組4名專家的例子用遺傳算法進行求解計算，表明，改進后的遺傳算法能高效求解出問題的近似最優(yōu)解，求解結(jié)果能滿足面試工作安排所提出的要求。

1 裝箱編碼

在遺傳算法中，待解問題的一個解從表現(xiàn)型到基因型的映射稱為編碼，實質(zhì)是解的一種向量表示方法，最初遺傳算法是采用二進制編碼方法，該方法操作簡便，但不能反映問題的特定知識。針對實際問題可以采用特定編碼，以利于問題求解。對于此模型，對編碼可以這樣設計：把一個學生的面試組專家成員當成一個整體，如同放在一個箱子中一樣，作為染色體表示中的一個基因位，則該基因位中有L個元素，值為1—M的不相同的整數(shù)，顯然第k個基因位確定了第k名學生被面試的L名專家。

2 改進遺傳算法求解

遺傳算法中一般采用輪盤賭選擇方式來選擇算子，即根據(jù)每個染色體適應值比例來確定該個體的選擇概率或生存概率。本文采用父子競爭中加入模擬退火選擇操作來進行選擇，從父代種群和新生成的種群中選擇一部分個體作為下一代種群。即以一個概率值來設置一新個體替換一父個體。設父個體為X，新個體為X’，T為當前溫度。則替換概率為

在遺傳迭代開始設置一個較大的初溫T(t0)，隨著迭代次數(shù)的增加溫度逐漸降低，降溫方式有很多種，這里用公式(8)方式進行降溫。

其中：k為一個略小于1的正數(shù)。在迭代中溫度逐漸降低，則當新個體比父個體差時，替換概率逐漸降低，在迭代后期，由于溫度很低，選擇優(yōu)秀個體的概率接近于1。設最大迭代次數(shù)為N，若溫度降低過快，則搜索容易過早陷入局部極值點，有必要設置一個最終的最低溫度為Tl，來計算k值，為

并在選擇過程中引入最優(yōu)保持操作，保存歷代產(chǎn)生的最優(yōu)個體，替換新一代群體中的最差個體，這樣既可以采用父子競爭來提高收斂速度，又能收斂于全局最優(yōu)解。

3 交叉算子

遺傳算法中的所謂交叉運算，是指對兩個相互配對的染色體按某種方式相互交換其部分基因，從而形成兩個新的個體。在本文的遺傳算法中，種群中每個個體的每一個基因位，為一名應聘應考者被面試的老師的分配方案，選中的父代種群中的兩個體X、Y進行單點交叉或多點交叉，交換相同基因位對應的所有數(shù)據(jù)，相當于在兩種不同的方案中交換相同學生被面試的老師分配方案，得到兩種新的分配方案，對于本模型，由于所計算的數(shù)據(jù)量較大，故采用多點交叉。這里只給出單點交叉的示意圖，設新個體為X’、Y’。

4 算例和計算結(jié)果分析

（1）算例。設有30名專家要對300個學生進行面試，每名學生對應一個面試組，每個面試組有四名專家，如何合理安排面試組成員，使達到如下要求：每名專家面試學生數(shù)量均衡，任意兩面試組不相同，且任意兩面試組成員要盡量不同。

（2）遺傳算法參數(shù)設置。采用遺傳算法對問題進行求解，參數(shù)設置如下：①群體大小N＝50。②取交叉概率Pc＝0.8，變異概率Pm＝0.1；③終止進化代數(shù)E＝3000代。

（3）求解結(jié)果分析。由于本文篇幅有限，求解結(jié)果專家面試學生對應關系這里不給出，只對求解結(jié)果進行討論。目標值隨遺傳代數(shù)的增加而減少，到遺傳后期，目標值基本趨于穩(wěn)定，即表示已找到近似最優(yōu)解。對找到的近似最優(yōu)解進行分析，計算得到表2數(shù)據(jù)，可以看出，沒有兩面試組成員完全相同，而且，出現(xiàn)三位以上專家相同的情形也較少。說明求解結(jié)果達到數(shù)學模型的要求。

5 結(jié)語

本文針對如何進行面試專家組成員工作安排使面試公正客觀的問題進行探討，根據(jù)面試工作公正客觀性要求建立其數(shù)學模型，表明，該模型為復雜的非線性整數(shù)規(guī)劃問題，難以找到常規(guī)算法對問題進行求解。提出一種裝箱編碼、模擬退火遺傳、多點交叉、領域搜索變異的遺傳算法對數(shù)學模型進行求解，并用一個30名專家對300名學生進行面試，每個面試組4名專家的例子用遺傳算法進行求解計算，表明，改進遺傳算法能高效快速求解出問題的近似最優(yōu)解，求解結(jié)果能滿足面試工作安排公正性客觀性的要求。遺傳算法的引進為求解這類問題提供一個好的解決方法和手段。

[1]劉智明,周激流.敖嗇.遺傳算法交叉算子分析[J].四川大學學報，2002，39(5)：857－860.

[2]G Wirght A.Genetic alogirthm for real parameter opitmization[A].The First Workshop on the Foundations of Geneitc Alogirthms and Classiifer Systems[C].Morgan Kaufmann,Sani Dego:WFGACS，1990_205—218.

[3]譚冠政,劉良敏.基于復數(shù)編碼遺傳算法的競爭性協(xié)進化策略[J].中南大學學報(自然科學版),2005,36(3):475-480.

[4]Srinivas M,Patnaik L M.Adaptive Probabilities of Crossover and Mutaiton in Genetic Algorithms[J].IEEE Transactions on systems,man and cybernetics,1994.