陳 香

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

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

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

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

1 裝箱編碼

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

2 改進(jìn)遺傳算法求解

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

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

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

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

3 交叉算子

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

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

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

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

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

5 結(jié)語

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

[1]劉智明,周激流.敖嗇.遺傳算法交叉算子分析[J].四川大學(xué)學(xué)報(bào)，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]譚冠政,劉良敏.基于復(fù)數(shù)編碼遺傳算法的競爭性協(xié)進(jìn)化策略[J].中南大學(xué)學(xué)報(bào)(自然科學(xué)版),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.