2006年第三屆研究生數(shù)學(xué)建模競賽D題優(yōu)秀論文.pdf

全全全全國國國國第第第第三三三三屆屆屆屆研研研研究究究究生生生生數(shù)數(shù)數(shù)數(shù)學(xué)學(xué)學(xué)學(xué)建建建建模模模模競競競競賽賽賽賽 題 目 學(xué)生面試中教師安排的優(yōu)化與算法 摘 要 本文探討高校自主招生的專家面試階段 對面試教師安排的優(yōu)化問題 主 要考慮以下三個問題 針對問題一 采用組合數(shù)學(xué)中的填充設(shè)計(jì)方法 對沒有兩位以及三位面試 老師相同的約束條件分別給出 N M 應(yīng)當(dāng)滿足的不等式 1 43 MM N 和 12 432 MMM N 4 針對問題二 本文結(jié)合問題一的結(jié)論以及對Y1Y 的分析 認(rèn)為Y的要 求可以通過考慮Y Y 每兩位老師共同面試的學(xué)生數(shù)量應(yīng)盡量均衡而基本 滿足 通過建立鄰接矩陣 1 Y 4 123 Y 及 M N A 并令 TT BAAC A A 可以由矩陣BC 的元 素實(shí)現(xiàn)Y Y的量化 把 Y1 Y2 和 Y3 量化后作為優(yōu)化目標(biāo) 采用多目標(biāo)規(guī) 劃遺傳算法搜索最優(yōu)解 通過染色體的競爭擇優(yōu) 從而保留較高適應(yīng)度的個體 使整個進(jìn)化過程朝著更優(yōu)解的方向進(jìn)行 最終可以根據(jù)需要達(dá)到不同程度優(yōu)化的 分配方案 對 N 379 M 24 的情形應(yīng)用該算法給出了具體的面試?yán)蠋煼峙浞?案 以及對該方案進(jìn)行了評價 12 Y 及 3 針對問題三 面試組由兩文兩理老師組成 在此假設(shè)下 此時問題一給出 的 N M 應(yīng)當(dāng)滿足的不等式修改為 44 MM N 和 2 244 MMM N 對問題二結(jié) 合問題一的結(jié)論知 N 379 M 24 文科 理科老師各 12 名 的情形 能夠做 到兩個不同的 面試組 沒有 3 個共同老師 并且實(shí)現(xiàn)了這一做法 本文最后討論以上模型的優(yōu)缺點(diǎn) 探討考生與面試?yán)蠋熤g分配的均勻性和 面試公平性的關(guān)系并提出一些合理化建議 關(guān)鍵詞 區(qū)組設(shè)計(jì) 填充設(shè)計(jì) 多目標(biāo)規(guī)劃 遺傳算法 參賽隊(duì)號 10394003 參賽密碼 由組委會填寫 由組委會填寫 1 一 問題的提出 自 2003 年以來 教育部為深化高校錄取制度改革 進(jìn)一步擴(kuò)大了高校在招 生中的自主權(quán) 北京大學(xué) 清華大學(xué)等 22 所高校實(shí)行了部分招生計(jì)劃自主招生 2004 年 實(shí)行自主招生的高校數(shù)目進(jìn)一步擴(kuò)大到 28 所 選拔方式也進(jìn)一步多樣 化 06 年 4 月復(fù)旦大學(xué)通過 面試 錄取新生 徹底摒棄了已實(shí)施多年的高考筆試 制度 由面試直接錄取新生 這是對高校進(jìn)一步擴(kuò)大自主權(quán)改革的又一次全新探 索與嘗試 當(dāng)然 高校自主招生體系還處于探索階段 還不完善 對于面試的考生 在全面衡量該考生的高中學(xué)習(xí)成績及綜合表現(xiàn)后通過采用專家面試的方式 決定 錄取與否 某高校在今年自主招生中 經(jīng)過初選合格進(jìn)入面試的考生有 N 人 擬聘請老師 M 人 每位學(xué)生要分別接受 4 位老師 簡稱該學(xué)生的 面試組 的 單獨(dú)面試 面試時 各位老師獨(dú)立地對考生提問并根據(jù)其回答問題的情況給出評 分 由于這是一項(xiàng)主觀性很強(qiáng)的評價工作 老師的專業(yè) 提問內(nèi)容 提問方式以 及評分習(xí)慣都會有較大差異 因此面試同一位考生的 面試組 的具體組成不同 會對錄取結(jié)果產(chǎn)生一定影響 為了確保面試工作的公平性 提出以下要求 Y1 每位老師面試的學(xué)生數(shù)量應(yīng)盡量均衡 Y2 面試不同考生的 面試組 成員不能完全相同 Y3 兩個考生的 面試組 中有兩位或三位老師相同的情形盡量的少 Y4 被任意兩位老師面試的兩個學(xué)生集合中出現(xiàn)相同學(xué)生的人數(shù)盡量的 少 在滿足 Y1 Y4 的某些條件下 考慮 問題一 設(shè)考生數(shù) N 已知 在滿足 Y2 條件下 說明聘請老師數(shù) M 至少分 別應(yīng)為多大 才能做到任兩位學(xué)生的 面試組 都沒有兩位以及三位面試?yán)蠋熛?同的情形 問題二 根據(jù) Y1 Y4 的要求建立學(xué)生與面試?yán)蠋熤g合理的分配模型 并就 N 379 M 24 的情形給出具體的分配方案 每位老師面試哪些學(xué)生 及 該方案滿足 Y1 Y4 這些要求的情況 問題三 如果面試?yán)蠋熤欣砜婆c文科的老師各占一半 并且要求每位學(xué)生 接受兩位文科與兩位理科老師的面試 并在此假設(shè)下分別回答問題一與問題二 問題四 討論考生與面試?yán)蠋熤g分配的均勻性和面試公平性的關(guān)系 為了 保證面試的公平性 除了題目中提出的要求外 還有哪些重要因素需要考慮 試 給出新的分配方案或建議 二 模型分析與評價 問題一 聘請老師數(shù) M 的下界 一 問題一重述 考生數(shù)已知 在滿足 Y2 即面試不同考生的 面試組 成員不能完全相 同 條件下 分別考慮任意兩位學(xué)生的 面試組 必須保證沒有兩位或者三位面 試?yán)蠋熛嗤那樾纬霈F(xiàn) 聘請的老師數(shù) M 至少應(yīng)該多大 N 2 二 符號說明 v聘請老師的個數(shù) N 面試學(xué)生的個數(shù) X 聘請的老師構(gòu)成的集合 1 Xv i B由X中的個老師組成的子集 稱之為區(qū)組 其中b為區(qū)組數(shù)目 k 12 iiiik Bxxx 1 ij xv 1 1 ib jk j B 區(qū)組中形如 2 k iij k Bx x 個 個 1k j x 的子區(qū)組 i N 由 i x老師面試的學(xué)生個數(shù) i j N 由 ij x x老師面試的學(xué)生個數(shù) ij x x X中任意一對老師 ij x x 在區(qū)組中恰好同時出現(xiàn)的次數(shù) ij x x 兩個老師組成的二元集 i j 1 ij x xv ijk x xx 兩個老師組成的三元集 i j k 1 ijk x xxv x 表示對實(shí)數(shù)x下取整 三 模型分析與求解 分別考慮任意兩位學(xué)生的 面試組 保證沒有兩位或者三位相同面試?yán)蠋煹?情形 這等價于任意兩位學(xué)生的 面試組 至多只有相同的一位老師 或者任意 兩位學(xué)生的 面試組 至多只有相同的一位或者兩位老師 我們的目標(biāo)是在滿足 以上所需條件下使得聘請的老師數(shù)盡可能的少 我們采用的策略是均衡不完全區(qū) 組設(shè)計(jì) 簡稱BIBD 稱有限集X上的一些k元子集 1 i Bib 構(gòu)成的族B為X上的一個區(qū)組設(shè) 計(jì) 記為 DX B X稱為此設(shè)計(jì)的基集 而子集族B中的諸子集 1 i Bib 則稱為此設(shè)計(jì)的區(qū)組 基集X中的元素個數(shù)Xv 稱為設(shè)計(jì)的階 稱為區(qū)組容 量 或區(qū)組大小或區(qū)組長度 對 k xX B 中含有x的區(qū)組個數(shù)稱為元素x的重復(fù) 數(shù) 記做r x 對 x y X 且xy B中包含二元子集 x y的區(qū)間個數(shù)稱為 元素的相遇數(shù) 記作 x y 3 我們知道一個 v k BIBD要求任意一對點(diǎn) x y恰好出現(xiàn)在 個區(qū)組 之中 這樣的設(shè)計(jì)只在點(diǎn)數(shù)滿足一定條件時才可能存在 也即 1 0 mod1 1 0 mod 1 vk v vk k 對于某些問題中需要考慮的點(diǎn)數(shù)v為任意取值的情形 則可以適當(dāng)放寬點(diǎn)對 恰 好 出現(xiàn)在 個區(qū)組的條件 也即要求 至多 出現(xiàn)在 個區(qū)組中 稱為填充設(shè) 計(jì) Packing Design 對于任意兩位學(xué)生的 面試組 保證沒有兩位相同面試?yán)蠋煹那樾?必須要求任意一對老師 ij x x在區(qū)組 1 i Bib 中至多出現(xiàn)一次 且為了保證聘 請的老師數(shù)M盡可能的少 我們遵循的一個原則是讓任意一對老師 ij x x在區(qū) 組 1 i Bi b中盡可能都出現(xiàn)一次 按BIBD策略 即 1 4 v M的填 充設(shè)計(jì) k 我們先考慮更一般的情況 隨意給定一面試?yán)蠋?i xX X是M元素集 區(qū)組設(shè)計(jì) X B 設(shè) i x元素在區(qū)組中出現(xiàn)的次數(shù)為 i rr x 不妨假設(shè)這些區(qū)組 為 12 r B BB 形如 1 1 k i k Bx 個 個 1 k ri k Bx 個 個 其中 代表除了 i x的其他1v 個面試?yán)蠋?且兩兩互不相同 由于任意一對老師 ij x xij 在區(qū)組 1 i Bib 中至多出現(xiàn) 次 用這 個面試?yán)蠋熖畛?v 1 i B ir 中的圓圈 則 X中 i x以外的v個面試?yán)?師出現(xiàn)在這r組中的次數(shù)為 1 1 v 則包含 i x元素的區(qū)組中至多出現(xiàn)的次數(shù) 即 由 i x老師面試的學(xué)生個數(shù)至多為 i N 1 1 v k 面試?yán)蠋焸€數(shù)為v 即 i x有 種取法 考慮到每個區(qū)組重復(fù)計(jì)算次 因此vk 4 最大可能的填充數(shù)為 1 1 vv kk 特別地 問題一考慮 1 4 M的情況 即滿足我們題目中所要求 的約束條件 則可得到任兩位面試?yán)蠋煵恢貜?fù)的4元組的個數(shù)至多為 kv 1 43 MM 又因?yàn)槊恳粋€學(xué)生的面試有四個老師的參與 也即一個四元老師組對應(yīng)著一 個學(xué)生 則 1 43 MM N 綜上分析 在滿足條件下 確保任兩位學(xué)生的面試組都沒有兩位面試?yán)?師相同 面試?yán)蠋煍?shù) 2Y M必須滿足不等式 1 43 MM N 1 當(dāng)學(xué)生數(shù)給定時 可得到NM的下界 對于任意兩位學(xué)生的 面試組 保證沒有三位相同面試?yán)蠋煹那樾?必 須要求任意3位老師 ijk x xx在區(qū)組 1 i Bib 中至多出現(xiàn)一次 且為了保證 聘請的老師數(shù)M盡可能的少 我們遵循的一個原則是讓任意3位老師 ijk x xx 在區(qū)組 1 i Bi b中盡可能都出現(xiàn)一次 按BIBD策略 即參數(shù) k v 滿足 1 4 M的填充設(shè)計(jì) kv 同樣我們先考慮更一般的情況 X是包含M個老師的M元集 區(qū)組設(shè)計(jì) X B 隨意先給定一面試?yán)蠋?i xX 有1v 種取法 然后再確定另一面試?yán)?師 j xX 有種取法 設(shè)2v ij x x兩元素在區(qū)組中出現(xiàn)的次數(shù)為 不妨假設(shè)為 ij rr x x 12 r B BB 2 1 k ij k Bx x 個 個 5 2 k rij k Bx x 個 個 其中 代表除了 i j x x面試?yán)蠋煹钠渌鹶2 個 于任意一對老師在區(qū)組 面試?yán)蠋?且兩兩互不相同 由 ijk x xxi j k互不相同 1 i Bib 中至多出現(xiàn) 次 用剩下的2v 個面試?yán)蠋熖畛?1 i B ir 中的圓圈 則X中 ij x x以 外的2v 個老師出現(xiàn)在這r組中的次數(shù)為 2v 則包含 ij x x元素的區(qū)組中至 多出現(xiàn)的次數(shù) 即由 ij x x老師面試的學(xué)生個數(shù) Ni j至多為 2 2 v k j xX 在確定 i xX 后 面試?yán)蠋?j x則有種取法 1v 對于面試?yán)蠋?1 ij k Bx x k 1個 個 rij k Bx x 1個 個 k 不妨設(shè)形如的元集記做區(qū)組 1 k j x 1k 1 i Bir 的子區(qū)組 1 j Bjr 1k 1 j Bx 1k rj Bx 其中 1 j Bjr 的元素是取自區(qū)組 1 i Bir 的后1k 個元素 因此對于區(qū)組 1 i Bir 的子區(qū)組 1 j Bjr 最大可能的填充數(shù)為 1 2 12 vv kk i x有 種取法 因此最大可能的填充數(shù)為 v而 1 2 12 vvv kkk 6 特別地 問題一考慮 1 4 v M的情況 即滿足我們題目中所要 求的約束條件 則可得到任三位面試?yán)蠋煵恢貜?fù)的4元組的個數(shù)至多為 k 12 432 MMM 同樣地 每一個學(xué)生的面試有四個老師的參與 也即一個4元組對應(yīng)著一個 學(xué)生 即 12 432 MMM N 綜合分析 在滿足條件下 確保任兩位學(xué)生的面試組都沒有三位面試?yán)?師相同 面試?yán)蠋煍?shù) 2Y M必須滿足不等式 12 432 MMM N 2 當(dāng)學(xué)生數(shù)給定時 可得到NM的下界 問題二 約束條件下學(xué)生與面試?yán)蠋熤g分配模型 一 問題二重述 問題二要求我們滿足四個約束條件 Y1 Y4 下 建立學(xué)生與面試?yán)蠋熤g 的分配模型 并就N 379 M 24的情形給出具體的分配方案 每位老師面試哪 些學(xué)生 及該方案滿足Y1 Y4這些要求的情況 Y1 每位老師面試的學(xué)生數(shù)量應(yīng)盡量均衡 Y2 面試不同考生的 面試組 成員不能完全相同 Y3 兩個考生的 面試組 中有兩位或三位老師相同的情形盡量的少 Y4 被任意兩位老師面試的兩個學(xué)生集合中出現(xiàn)相同學(xué)生的人數(shù)盡量的 少 二 模型分析 根據(jù)問題二的闡述 可以清晰地知道學(xué)生與面試?yán)蠋熤g必然要建立一對四 的面試關(guān)系 也即在學(xué)生與面試?yán)蠋熤g有著多種分配關(guān)系 在此 我們尋求的 是一種更加合理的分配關(guān)系 使得這種分配關(guān)系滿足或者說越逼近于我們目標(biāo) 以為例 若要任兩位學(xué)生的 面試組 中都沒有兩位老師相 24 379MN 同 則由問題一的不等式 1 可得學(xué)生數(shù)至多為 24 23 42 43 而實(shí)際上 所以肯定出現(xiàn)兩個考生的 面試組 中有兩位老師相同的情形 我們 的優(yōu)化目標(biāo)是所有兩位老師重復(fù)出現(xiàn)的次數(shù)總量盡可能的少 379N 7 如果要任意兩位考生的面試?yán)蠋熃M中都沒有三位老師相同 則由問題一的 不等式 2 可知學(xué)生數(shù)至多可為 24 23 22 504 432 而實(shí)際考生數(shù) 因此理論上可以做到面試?yán)蠋熃M中都沒有三位老師相同的情形 但通常在實(shí)際安 排中難以做到 因此讓三位老師相同的情形盡量少依然是個優(yōu)化目標(biāo) 379N 進(jìn)一步分析可知道 實(shí)現(xiàn)兩位老師重復(fù)出現(xiàn)的次數(shù)總是盡可能少的通常 采用的策略是任兩位老師重復(fù)出現(xiàn)的次數(shù)盡量均衡 而三位老師每重復(fù)出現(xiàn)一 次 則對兩位老師重復(fù)出現(xiàn)的次數(shù)總是增加3 因此兩位老師重復(fù)出現(xiàn)的次數(shù) 總量盡可能少的情形通常也是發(fā)生在三位老師重復(fù)出現(xiàn)的次數(shù)總量較小的情形 對于條件Y4 老師面試的學(xué)生集合中出現(xiàn)相同的學(xué)生 就是老師出 現(xiàn)的同一面試組 因此老師面試學(xué)生集合中出現(xiàn)相同的學(xué)生人數(shù)就是老師i j 重復(fù)出現(xiàn)在 面試組 中的重復(fù)數(shù) 要做到任意兩位老師面世相同學(xué)生人數(shù)盡量 少 仍然是使得任意兩位老師重復(fù)出現(xiàn)的次數(shù)盡量均衡 i j i i j j 綜上所述 我們的優(yōu)化策略為以下三個目標(biāo) 123 Y Y Y 其中 任意兩位老師重復(fù)出現(xiàn)在一個面試組中的重復(fù)數(shù)盡可能均衡 3 Y 三 模型求解 為了使得我們的分配方案更加合理 找到滿足這些目標(biāo)的最佳設(shè)計(jì)方案 我 們采取的策略是 目標(biāo)規(guī)劃遺傳算法 借助遺傳算法實(shí)施來解決多目標(biāo)優(yōu)化問題 Multi objective Optimization Problem 使整個過程朝著更優(yōu)解的方向進(jìn)行 1 遺傳編碼設(shè)計(jì) 本文將面試不同考生的 面試組 4個成員做為一個基因片段 基因片段的 異同與基因片段中數(shù)字的排列無關(guān) 例如 兩個基因片段1 2 3 4 與 1 3 2 4 在 本文認(rèn)為是一樣的 基因片段中的單個基因?yàn)槊嬖嚴(yán)蠋煹男蛱?從而按照學(xué)生 序列構(gòu)造由面試?yán)蠋熜蛱柦M成的染色體 2 初始種群的產(chǎn)生 由于題目Y2條件對每個學(xué)生遇到的面試?yán)蠋熥隽讼拗?面試不同考生的 面 試組 成員不能完全相同 染色體的構(gòu)成也因此有了最低的限制條件 因此不 能采用隨機(jī)產(chǎn)生染色體的方法來建立初始種群 所以本文先通過貪婪算法搜索出 幾個僅符合Y2條件的染色體 構(gòu)造出初始種群 8 3 交叉算子 傳統(tǒng)遺傳算法中的交叉運(yùn)算是對單獨(dú)的基因進(jìn)行交叉 但由于在本題中染色 的特征是由 面試組 中的4個成員構(gòu)成的基因片段 所以本文在交叉運(yùn)算中實(shí) 行對基因片段的交叉而不是單獨(dú)基因的交叉 同時根據(jù)Y2的要求 染色體A中要交叉的基因片段在不能與染色體B中 任何基因片段相同 染色體B中要交叉的基因片段在不能與染色體A中任何基 因片段相同 本文采用多點(diǎn)交叉的策略 本文中采用動態(tài)的交叉概率控制交叉操作的使 用頻率 c P 4 變異算子 本文采用基本位變異 Simple Mutation 的方式來實(shí)現(xiàn)變異運(yùn)算 以變異概 率指定一位或者某幾位基因座上的值座變異運(yùn)算 其具體操作過程如下 m P 1 對染色體上的每一個基因座 以變異概率指定它為變異基因 2 對每一個變異基因 隨機(jī)產(chǎn)生 1 M 中的數(shù)值 從而產(chǎn)生新的基因片 段 該基因片段不能與該染色體中其它的基因片段相同 基因片段中 的基因不能重復(fù) 5 適應(yīng)度函數(shù)F 9 通過一個染色體中的基因序列 即一分配方案 可建立如下鄰接矩陣 ij M N Aa 1 0 ij i a otherwise 第 個老師與第j個學(xué)生有面試關(guān)系 1 1iMjN 令 TT ijij M MN BAAbCA Ac N 1 N ijikjk k ba 其中a 1 M ijkikj k ca a 矩陣 B C相應(yīng)元素的涵義如下 ijij b c 1 ii biM 第i號老師面試學(xué)生數(shù) ij bij 第i號老師和第j號老師同組重復(fù)數(shù) 1 ii ciN 第 號學(xué)生的 面試組 老師個數(shù) 恒為4 i ij cij 第i號學(xué)生和第j號學(xué)生 面試組 相同老師的個數(shù) 則條件可以用矩陣 123 Y Y Y B C的元素來進(jìn)行描述 1 Y1 每位老師面試的學(xué)生數(shù)量應(yīng)盡量均衡 1 ii biM 的方差 1 f 盡量小 即 2 2 1 111 1114 MMM iiiiii iii N fbbb MMMM 盡量小 其中 表示遺傳的迭代 次數(shù) 2 Y2 面試不同考生的 面試組 成員不能完全相同 即第i號學(xué)生和 第j號學(xué)生 面試組 相同老師的個數(shù)小于等于3 4 ij cij 3 任意兩位老師重復(fù)出現(xiàn)在一個面試組中的重復(fù)數(shù)盡可能均衡 3 Y 10 2 2 2 16 ij ij MM N fb CC 2 的值盡可能小 則適應(yīng)度函數(shù)可描述為 F 12 12 12 11 ff Fww ff 其中 為相應(yīng)的權(quán)系數(shù) 可根據(jù)對 1 w 2 w 13 Y Y 三個要求條件的重視程度賦予 不同大小的數(shù)值 總和為1保持不變 1 w 2 w 6 選擇算子 本文采用競爭擇優(yōu)的選擇方法 從而保留后代中較高適應(yīng)度的個體 使整個 進(jìn)化過程朝著更優(yōu)解的方向進(jìn)行 7 控制參數(shù) 1 交叉概率 c P 在進(jìn)化過程中 始終控制著在遺傳過程中起主導(dǎo)作用的交叉算子 較大 的 可以使各代充分相交 個體結(jié)構(gòu)被破壞的可能性也越大 不能有效保護(hù)好 的基因模式 較低的 可以保持一個連續(xù)的解空間 但是進(jìn)化的速度慢 c P c P c P 2 變異概率 m P 本文中較大的可以產(chǎn)生較多的新基因片段 增加了群體的多樣性 但也 有可能破壞掉很多好的模式 太小則容易陷入局部極值 使解過早收斂產(chǎn)生 早熟 問題 m P m P 3 控制方法 為了保證遺傳算法的全局收斂性 就要維持解群體中個體的多樣性 避免有 效基因的丟失 另一方面 為了加快收斂速度 就要使解群體較快地向最優(yōu)狀 態(tài)轉(zhuǎn)移 這又會減少群體多樣性 容易陷入局部最優(yōu) 因此 本文將進(jìn)化過程劃 分為突和漸進(jìn)兩個階段 由于在一開始采用貪婪法產(chǎn)生的種群有著很大的相似 性 所以要將交叉概率和變異概率設(shè)置為較大的數(shù)值 本文中將和的 初始數(shù)值設(shè)置為0 6與0 3 通過較頻繁的變異和交叉產(chǎn)生新的基因片段和染色 體 擴(kuò)大解的搜索空間避免陷入局部極值 之后隨著進(jìn)化的過程逐漸調(diào)小與 的值 使其加快收斂速度 c P m P c P m P c P m P 11 8 流程描述 具體程序見附錄一 9 實(shí)驗(yàn)結(jié)果及評價 1 從B矩陣 T AA 觀察分析 下面給出1 5 10 15 20 25 30代中較高適應(yīng)度的染色體對應(yīng)的B 矩陣 見附錄二 圖形 水平坐標(biāo)為老師序號 垂直坐標(biāo)為學(xué)生數(shù)目 12 13 14 15 從以上進(jìn)化過程看出 矩陣的對角元即各位老師面試的學(xué)生數(shù)目趨于均 衡 矩陣的非對角元即不同老師面試的共同學(xué)生數(shù)目也趨于均衡 從而說明我們 設(shè)置的等價限制條件是有效的 模型的建立是合理的 2 從C矩陣觀察 并結(jié)合問題一的結(jié)論分析說明 將M 24代入下式得 學(xué)生數(shù)N 379滿足不等式 112 42504 43432 MMMMM N 所以無法滿足每兩位學(xué)生的 面試組 中共同老師不超過1 但可以滿足共 同老師數(shù)不超過2 從下面給出的遺傳算法中1至30代染色體對應(yīng)的C矩陣 中0 1 2 3 從左至右 出現(xiàn)的次數(shù)及所占的比例中 可看出3出 現(xiàn)的頻率逐代降低并趨近于0 也就是說是已經(jīng)逼近最優(yōu)解 T A A 5678 3 95 60928 42 42 65572 45 65 11084 7 72 12738 8 87 67674 47 11 54598 38 01 8252 5 74 21176 14 74 68538 47 71 46924 32 67 6624 4 61 24778 17 25 71458 49 75 41650 29 00 5376 3 74 29630 20 63 72238 50 29 37012 25 77 4382 3 05 33534 23 35 72196 50 26 33778 23 52 3754 2 61 39496 27 50 70496 49 08 30048 20 92 3222 2 24 40446 28 16 70300 48 94 29416 20 48 3100 2 16 45450 31 64 69412 48 32 25848 17 99 2552 1 78 16 49800 34 67 67656 47 10 23580 16 42 2226 1 55 53350 37 14 66462 46 27 21494 14 96 1956 1 36 55516 38 65 65722 45 75 20260 14 10 1764 1 23 57646 40 13 65098 45 32 18918 13 17 1600 1 11 58640 40 82 64582 44 96 18496 12 88 1544 1 07 59638 41 52 64224 44 71 17974 12 51 1426 0 99 60474 42 10 63708 44 35 17730 12 34 1350 0 94 61186 42 60 63460 44 18 17264 12 02 1352 0 94 62220 43 32 63040 43 89 16766 11 67 1236 0 86 63110 43 94 62440 43 47 16448 11 45 1264 0 88 63252 44 03 62520 43 53 16264 11 32 1226 0 85 64336 44 79 62090 43 23 15694 10 93 1142 0 80 65050 45 29 61478 42 80 15688 10 92 1046 0 73 64954 45 22 61888 43 09 15348 10 68 1072 0 75 65348 45 49 61606 42 89 15248 10 62 1060 0 74 65532 45 62 61516 42 83 15092 10 51 1122 0 78 65604 45 67 61534 42 84 15060 10 48 1064 0 74 65808 45 81 61278 42 66 15124 10 53 1052 0 73 65668 45 72 61444 42 78 15116 10 52 1034 0 72 65864 45 85 61226 42 62 15116 10 52 1056 0 74 65874 45 86 61248 42 64 15170 10 56 970 0 68 具體分配方案 每位老師面試哪些學(xué)生 見附錄三 問題三 文理約束下聘請老師 M 的下界 一 問題三重述 在滿足問題一的基礎(chǔ)上 增加一個約束 即在所有的面試?yán)蠋熤?理科與文 科的老師各占一半 且每位學(xué)生都接受兩位文科與兩位理科老師的面試 在這種 情形下 聘請的老師數(shù)M M為偶數(shù) 應(yīng)該滿足什么樣的條件 二 模型分析與求解 學(xué)生數(shù)已知 在滿足 即面試不同考生的 面試組 成員不能完全相 同 及要求每位學(xué)生都要接受兩文 兩理老師面試條件下 考慮任意兩位學(xué)生的 面試組 保證沒有兩位或者三位相同面試?yán)蠋煹那樾?這等價于任意兩位學(xué)生 的 面試組 至多只有一位 一位或者兩位 老師相同 有可能是文科老師也有 可能是理科老師 我們的目標(biāo)是在滿足以上所需條件下使得聘請的老師數(shù)盡可 能的少 我們采用的主體思想依舊是問題一的 均衡不完全區(qū)組設(shè)計(jì) 簡稱 BIBD 并在此基礎(chǔ)上進(jìn)一步深化 N2Y 對于任意兩位學(xué)生的 面試組 保證沒有兩位相同面試?yán)蠋煹那樾?必須要求任意一對老師 ij x x在區(qū)組 1 i Bib 中至多出現(xiàn)一次 先取定老師 i x 共有M種取法 不妨設(shè) i x為理科老師 并設(shè) i x元素在區(qū)組中出現(xiàn)的次數(shù)為 17 i rr x 令這些區(qū)組為 12 r B BB 1 4 i Bx 理 4 ri Bx 理 其中 代表所需的三個面試?yán)蠋?則組成一個4元面試組還需三個面試 老師 且這三位面試?yán)蠋煴仨氂贸?i x的兩文一理來填充 由題中假設(shè)知 面試 老師中文科理科老師各占一半 則一共可以分成 4 M 組 在取定 i x后 理科老 師還剩1 2 M 1 2 M 個 一共可以分成組 則包含理科老師 i x的區(qū)組至多出現(xiàn)的 次數(shù)為 2 min 424 MMM i x理科老師面試的學(xué)生個數(shù)至多為 i N即由 4 M 的取法數(shù)為 2 M 則可得到任兩位面試?yán)蠋煵恢貜?fù)的4元組的個數(shù)至多為 i x由于 44 MM 因此 確保任意兩位學(xué)生的面試組都沒有兩位面試?yán)蠋熛嗤?面試?yán)蠋煍?shù)M 必須滿足不等式 44 MM N 3 考慮對于任意兩位學(xué)生的 面試組 沒有三位面試?yán)蠋熛嗤那樾?符號說明 不妨先任意取定理科老師x y 則要組成一個4元 面試組 還需兩位文科 老師的參與 由于文科老師數(shù)為 2 M 將 2 M 個文科老師中按 二元素對 進(jìn)行劃 分 并且 二元素對 之間元素要求兩兩不同 則有 4 M 對 接下來 將老y 18 師換成另一位理科老師z 即取定的老師變成x z 同樣的 可以找另一種文科 老師的組合方式 4 M 組 這個過程繼續(xù)下去 直到取完所有的理科老師 則包含面試?yán)蠋焫且至多只有兩位老師相同的 面試組 數(shù)為 1 42 MM 又x可以是理科老師 總數(shù)為 2 M 中的任何一個 過濾掉重復(fù)的情況 則 滿足至多兩位老師相同的 面試組 個數(shù)最多為 1 2 M 44 MM 綜合分析 在滿足條件下 確保任兩位學(xué)生的面試組都沒有三位面試?yán)?師相同 面試?yán)蠋煍?shù) 2Y M必須滿足不等式 1 442 MMM N 4 下面給出面試?yán)蠋煍?shù)12M 的計(jì)算例子 12面試?yán)蠋熆倲?shù)M 文科理科老師各占一半 1 2 6代表6位理科 老師 a b f代表6位文科老師 不妨設(shè)任意取定的理科老師x 1 則在含老 師x 即1 的 面試組 中 滿足至多只有兩位面試?yán)蠋熛嗤?面試組 有 2 12 2 15C組 用其它理科老師更換x 即1 則可得到另外30組 事實(shí)上 在 下述表格中 將文科老師對固定 如 a b 可將理科老師對 1 2 換成 3 4 5 6 在這一過程中 面試組 數(shù)量增加到原來的三倍 因此滿足至多兩位老師相同 的 面試組 有 2 C12 2 453 組 具體安排列表如下 ab cd 12 ef ac af be bc 13 df 23 de ad ae ab bf bd cd 14 ce 24 cf 34 ef ae ac ad af bd be bf bc 15 cf df ce de 25 35 45 af ad ae ac ab 16 bc 26 bf 36 ed 46 be 56 cd 19 de ce cf df ef 表一 其中 12ab 代表某一個面試組 由于區(qū)組數(shù)45達(dá)到不等式 4 上界的最優(yōu)解 可見不等式是緊的 從表一中不難看出 取M 12 N 45的情況 每一位文理科老師都恰好面 試 4 45 15 12 個學(xué)生 實(shí)現(xiàn)了老師面試學(xué)生數(shù)的均衡 同理 當(dāng)老師數(shù)M 24時 也可根據(jù)此法排列 將M 24代入式子 1 442 MMM N 得到N的上界 396 此時每一位老師恰好面試66個學(xué)生 而問題二中 學(xué)生數(shù)量為379 滿足不等式 sup N 361396 44442 MMMMM N 所以不可能做到兩個不同學(xué)生的 面試組 中相同老師數(shù)均不超過1 但理 論上可以滿足相同老師數(shù)均不超過2 按照上述編排方法 對于M 24 N 396的情況 具體分配方案如下 程序見 附錄四 問題三中要求的M 24 N 379的情況只要從下列數(shù)據(jù)中隨機(jī)刪除396 379 17組四元組即可 下列數(shù)據(jù)前兩個數(shù)字對為理科老師對 后面的6對字母對為可以與其搭配 的文科老師對 2 10 a i b j c g d h e k f l 1 2 a b c d e f g h i j k l 2 11 a l b k c f d e g j h i 1 3 a c b d e g f h i k j l 2 12 a k b l c e d f g i h j 1 4 a d b c e h f g i l j k 1 5 a e b f c i d j g k h l 3 4 a b c d e f g h i j k l 1 6 a f b e c j d i g l h k 3 5 a k b l c e d f g i h j 1 7 a g b h c k d l e i f j 3 6 a l b k c f d e g j h i 1 8 a h b g c l d k e j f i 3 7 a i b j c g d h e k f l 1 9 a i b j c g d h e k f l 3 8 a j b i c h d g e l f k 1 10 a j b i c h d g e l f k 3 9 a e b f c i d j g k h l 1 11 a k b l c e d f g i h j 3 10 a f b e c j d i g l h k 1 12 a l b k c f d e g j h i 3 11 a g b h c k d l e i f j 3 12 a h b g c l d k e j f i 2 3 a d b c e h f g i l j k 2 4 a c b d e g f h i k j l 4 5 a l b k c f d e g j h i 2 5 a f b e c j d i g l h k 4 6 a k b l c e d f g i h j 2 6 a e b f c i d j g k h l 4 7 a j b i c h d g e l f k 2 7 a h b g c l d k e j f i 4 8 a i b j c g d h e k f l 2 8 a g b h c k d l e i f j 4 9 a f b e c j d i g l h k 2 9 a j b i c h d g e l f k 20 4 10 a e b f c i d j g k h l 4 11 a h b g c l d k e j f i 4 12 a g b h c k d l e i f j 5 6 a b c d e f g h i j k l 5 7 a c b d e g f h i k j l 5 8 a d b c e h f g i l j k 5 9 a g b h c k d l e i f j 5 10 a h b g c l d k e j f i 5 11 a i b j c g d h e k f l 5 12 a j b i c h d g e l f k 6 7 a d b c e h f g i l j k 6 8 a c b d e g f h i k j l 6 9 a h b g c l d k e j f i 6 10 a g b h c k d l e i f j 6 11 a j b i c h d g e l f k 6 12 a i b j c g d h e k f l 7 8 a b c d e f g h i j k l 7 9 a k b l c e d f g i h j 7 10 a l b k c f d e g j h i 7 11 a e b f c i d j g k h l 7 12 a f b e c j d i g l h k 8 9 a l b k c f d e g j h i 8 10 a k b l c e d f g i h j 8 11 a f b e c j d i g l h k 8 12 a e b f c i d j g k h l 9 10 a b c d e f g h i j k l 9 11 a c b d e g f h i k j l 9 12 a d b c e h f g i l j k 10 11 a d b c e h f g i l j k 10 12 a c b d e g f h i k j l 11 12 a b c d e f g h i j k l 由于區(qū)組數(shù)396達(dá)到不等式 4 上界的最優(yōu)解 可見不等式是緊的 從表一中不難看出 取M 24 N 396的情況 每一位文理科老師都恰好面試 4 396 66 24 個學(xué)生 實(shí)現(xiàn)了老師面試學(xué)生數(shù)的均衡 問題四 模型進(jìn)一步討論 為保證面試更趨于公平性 在保證面試不同考生的面試組成員不能完全相同 情況下 學(xué)生數(shù)與面試?yán)蠋煍?shù)NM之間在滿足以下關(guān)系 1 43 MM N 在這種情況下 可確保任兩位學(xué)生的面試組都沒有兩位面試?yán)蠋熛嗤那?形 即任兩位學(xué)生的面試組至多只有一位相同的面試?yán)蠋?12 432 MMM N 在這種情況下 可確保任兩位學(xué)生的面試組都沒有三位面試?yán)蠋熛嗤那?形 即任兩位學(xué)生的面試組至多只有兩位相同的面試?yán)蠋?11 43432 MMMMM N 2 在這種情況下 無法滿足兩位學(xué)生的面試組都沒有兩位面試?yán)蠋熛嗤那?2 形 但可以保證兩位學(xué)生的面試組都沒有三位面試?yán)蠋熛嗤那樾?為了保證面試的公平性 除了以上提出的幾點(diǎn)要求外 建議考慮 面試組 男女教師的組合 不同的 面試組 招收學(xué)生的喜好不同 老師一般會在頭腦中形成一個 理 想人選 的模式 并以此評價學(xué)生 面試之前可以增加一項(xiàng)調(diào)查表 調(diào)查學(xué)生的文理偏好及特長 可適當(dāng)?shù)恼{(diào)整 面試組 的文理科老師的比例 決定錄取與否的各因素中 考生哪個條件占多大權(quán)重 應(yīng)進(jìn)一步規(guī)范化和制 度化 參考文獻(xiàn) 1 盧開澄 盧華明 組合數(shù)學(xué) 北京 清華大學(xué)出版社 2002 7 2 吉慶兵 一類部分均衡不完全區(qū)組設(shè)計(jì)的構(gòu)造 重慶師范學(xué)院學(xué)報(bào) 2001 9 NO 3 3 M H Alsuwaiyel 算法設(shè)計(jì)技巧與分析 北京 電子工業(yè)出版社 2004 8 4 耿素云 屈婉玲 離散數(shù)學(xué) 北京 高等教育出版社 1998 6 5 周明 孫樹棟 遺傳算法原理及應(yīng)用 北京 國防工業(yè)出版社 1999 6 6 Michalewicz Z 演化程序 遺傳算法和數(shù)據(jù)編碼的結(jié)合 北京 科學(xué)出 版社 2000 2 附錄 附錄 附錄一 Program GA2 APPTYPE CONSOLE uses SysUtils const N 379 M 24 OddFlag true 是否分文理 type StudentChoice record choice array 1 4 of SmallInt end Students record Stu array 1 N of StudentChoice Tea array 1 M 1 N of Byte ATAMatr array 1 n 1 n of Word Y1 Y3 Y4 Integer end var pop array 1 2 of Students temp pop array 1 2 of Students Pop children array 1 2 of Students answer array 1 m 1 m of SmallInt DNAcount GenCount Goal Integer procedure MakeAdjMat AB BYTE 建立臨接矩陣 var i j Integer begin for i 1 to m do for j 1 to n do temp pop AB Tea i j 0 for i 1 to n do for j 1 to 4 do temp pop AB Tea temp pop AB Stu i choice j i 1 end 3 procedure ATA AB Byte 建立 AT A 矩陣 var i j k Integer begin for i 1 to n do for j 1 to n do temp pop AB ATAMatr i j 0 for i 1 to n do for j 1 to n do begin for k 1 to m do temp pop AB ATAMatr i j temp pop AB ATAMatr i j temp pop AB Tea k i temp pop AB Tea k j end end function Fit Y1 AB Byte Integer 方差 var i j aver t count Integer teacher array 1 M of Integer begin count 0 aver Round 4 N M for i 1 to m do teacher i 0 for i 1 to m do for j 1 to n do if temp pop AB Tea i j 1 then Inc teacher i for i 1 to m do begin t ABS teacher i aver count count t end Result count end function Fit Y3 AB Byte Integer var i j count Integer begin count 0 for i 1 to n do for j i 1 to n do count count Abs temp pop AB ATAMatr i j 1 4 Result count end function Fit Y4 AB Byte Integer 兩個老師的學(xué)生集合中出現(xiàn)相同學(xué)生的人數(shù) begin Result pop AB Y4 end procedure Init 總?cè)撼跏蓟?var i j k Integer F TextFile begin AssignFile F in txt Reset F DNAcount 0 GenCount 0 read F Goal for i 1 to 2 do begin for j 1 to N do for k 1 to 4 do begin read F temp pop i Stu j choice k end MakeAdjMat i ATA i temp pop i Y1 Fit Y1 i temp pop i Y3 Fit Y3 i temp pop i Y4 Fit Y4 i pop i temp pop i end CloseFile F end function Compare a b StudentChoice Boolean var i j count Integer flag Boolean begin count 0 flag true 5 for i 1 to 4 do for j 1 to 4 do if a choice i b choice j then Inc count if count 4 then flag False Result flag end function CheckCross p Integer Boolean 判定交叉運(yùn)算合法性 var a b StudentChoice i Integer flag Boolean begin flag True a temp pop 1 stu p b temp pop 2 stu p for i 1 to n do if i p then begin if not Compare a temp pop 2 stu i then flag False if not Compare b temp pop 1 stu i then flag False if flag False then Break end Result flag end function CheckMutant AB Byte p Integer Boolean 判定變異運(yùn)算合法性 var i Integer flag Boolean begin flag true for i 1 to N do if i p then begin flag Compare temp pop AB stu i temp pop AB stu p if not flag then Break end Result flag end function CheckRandom num Integer Boolean 隨機(jī)觸發(fā) var t Integer flag Boolean 6 begin flag true Randomize t Random 100 1 if t num then flag False Result flag end function Probability ProType Byte Boolean 概率調(diào)整 const CrossAver 40 Mutant 10 var pro Integer flag Boolean begin flag True if GenCount in 1 20 then begin if ProType 0 then flag CheckRandom 60 else flag CheckRandom 40 end if GenCount in 21 40 then begin if ProType 0 then flag CheckRandom 40 else flag CheckRandom 30 end if GenCount 40 then begin if ProType 0 then flag CheckRandom 30 else flag CheckRandom 10 end Result flag end procedure Cross 交叉運(yùn)算 var i Integer t StudentChoice begin 7 for i 1 to N do begin if Probability 0 then if CheckCross i then begin t temp pop 1 stu i temp pop 1 Stu i temp pop 2 Stu i temp pop 2 Stu i t end end end procedure Mutant 變異運(yùn)算 var i j position value t Integer begin for j 1 to 2 do for i 1 to N do if Probability 1 then begin position Random 4 1 value 0 while value 0 or value temp pop j Stu i choice 1 or value temp pop j Stu i choice 2 or value temp pop j Stu i choice 3 or value temp pop j Stu i choice 4 do begin value Random m 1 if OddFlag then if temp pop j Stu i choice position mod 2 0 and value mod 20 or temp pop j Stu i choice position mod 20 and value mod 2 0 then Dec value end