曹迎槐
摘要:該文以混合泳接力項(xiàng)目這種特殊的類指派問題為例,一改傳統(tǒng)的0-1規(guī)劃解法,不僅提出了基于GA和偶圖的求解思路,更提出了一種基于各泳姿成績(jī)表差值的表上求解算法,并對(duì)各算法做了匯總分析。
關(guān)鍵詞:混合泳接力;指派;績(jī)差求解;GA;偶圖
中圖分類號(hào):TP311 文獻(xiàn)標(biāo)識(shí)碼:A 文章編號(hào):1009-3044(2017)17-0220-02
1背景
生活中的指派問題很常見,但運(yùn)動(dòng)會(huì)上的類指派接力項(xiàng)目卻有些特殊。接力項(xiàng)目既可出現(xiàn)在田徑場(chǎng)上,也可出現(xiàn)在游泳池里,既可設(shè)男子項(xiàng)目,亦可設(shè)女子項(xiàng)目,甚至還有男女混合接力,觀賞性非常強(qiáng)。田徑場(chǎng)上的接力比賽之接棒技術(shù)很有講究,但游泳池里的混合接力雖省去了接棒壓力,但增加了泳姿要求,需考慮的因素反而更多。
例如:4×100m混合泳接力項(xiàng)目全程400米,規(guī)定每個(gè)隊(duì)由4人組成,必須按仰泳、蛙泳、蝶泳、自由泳的順序進(jìn)行,每人只能用一種泳姿游完100m,每種泳姿的技術(shù)要求依據(jù)本泳姿之相關(guān)規(guī)則。不難理解,當(dāng)備選人數(shù)較多時(shí),如何確定組隊(duì)人選就頗費(fèi)腦筋。較傳統(tǒng)意義上的指派問題而言,此類問題存在淘汰機(jī)制,不可隨意指派,且同時(shí)存在著人員選擇與泳姿分配等縱、橫雙向?qū)Ρ确治?,相?duì)復(fù)雜,其特殊性一目了然。為便于說明問題,設(shè)現(xiàn)有8名備選隊(duì)員,其平時(shí)成績(jī)?nèi)绫?,試分析如何組隊(duì),可使全隊(duì)的總成績(jī)最好。
此類問題的常見解法多用0-1規(guī)劃,屬LP范疇。其實(shí),還有多種求解思路。
2基于GA的求解分析
作為指派問題,因其非線性特征十分明顯,且不連續(xù),在數(shù)據(jù)規(guī)模較大時(shí)解空間相對(duì)可觀,所以基于GA求解也是個(gè)不錯(cuò)的選擇。仍以上述想定案例為基礎(chǔ),因備選人數(shù)有8人,故可用3位二進(jìn)制0-1編碼來精確描述每個(gè)選手,如表2所示。
于是,GA的個(gè)體即可用人選的4位選手之0-1編碼(長(zhǎng)為固定的12位)來表示。例如:個(gè)體‘101 000 100 010,即表示‘己、甲、戊、丙四位選手,按照仰泳、蛙泳、蝶泳、自由泳的規(guī)定順序組隊(duì)參賽。
至于GA之操作算子設(shè)計(jì),倒也沒有太多的特殊性,無非是交叉、突變,甚至選擇等。但在GA的求解過程中,每迭代生成一個(gè)新個(gè)體,都必須檢測(cè)其規(guī)范性,即必須保證四位選手不重,以規(guī)避一人游多個(gè)泳姿的情形。而適應(yīng)度函數(shù)十分簡(jiǎn)單,只需計(jì)算四名選手的總成績(jī)并求最小即可。在本案例中,種群規(guī)??稍O(shè)置為80,大約相當(dāng)于解空間的二十分之一左右。而交叉、遺傳和突變等概率,則按常規(guī)處之就好,無須做額外設(shè)計(jì)。
經(jīng)MATLAB軟件實(shí)際運(yùn)行可知,用GA求解確無把握得到最優(yōu)解,所以,用GA求解本案例之指派問題,旨在對(duì)比分析幾種不同求解方法之異同和特點(diǎn),從而強(qiáng)化學(xué)生的運(yùn)籌優(yōu)化意識(shí)和對(duì)現(xiàn)實(shí)問題的分析思路或角度。
3基于成績(jī)差的表上求解算法嘲
首先,先將表1中的成績(jī)統(tǒng)一為以秒為單位,稱‘歸秒處理。結(jié)果如表3。
接著,再求成績(jī)差,稱‘績(jī)差。即找到各泳姿的最優(yōu)成績(jī),然后求出該泳姿的其他各選手之成績(jī)與該最優(yōu)成績(jī)之差,結(jié)果當(dāng)然均非負(fù)。其中,最優(yōu)成績(jī)不變。如表4。
雖然最小績(jī)差是0.3,但因選手戊已確定自由泳,且選手戊沒有其他任務(wù),所以可不考慮該績(jī)差。次小績(jī)差是1.5,有兩個(gè)點(diǎn),即‘丁的蛙泳、‘辛的蝶泳。不妨先考慮點(diǎn)‘丁的蛙泳,即調(diào)整蛙泳的人選,用選手丁取代選手乙,游蛙泳。如表5。
再考慮另外一個(gè)次小績(jī)差1.5的對(duì)應(yīng)點(diǎn)‘辛的蝶泳的情形,可調(diào)整蝶泳的人選,用選手辛取代選手乙,游蝶泳。如表6。
此刻,泳隊(duì)人選已確定完成。即:乙游仰泳、丁游蛙泳、戊游自由泳、辛游蝶泳,總成績(jī)251.7秒。
4基于LP之0-1規(guī)劃求解分析
5基于偶圖之交替鏈求解分析
此類指派問題實(shí)質(zhì)上可直接描述為一個(gè)二部圖,即偶圖K2.4,如圖2所示。對(duì)應(yīng)于前面幾種解法得出的最優(yōu)解便是圖中粗線組成的邊集。該邊集顯然是交替鏈:‘自由泳—戊,戊、蛙泳,蛙泳—丁,丁—蝶泳,蝶泳—辛,辛—仰泳,仰泳—乙中的一部分。換言之,在偶圖K2.4中求解,即找出圖中所有這些長(zhǎng)度為7的交替鏈,該鏈從泳姿點(diǎn)集出發(fā),到選手點(diǎn)集結(jié)束,點(diǎn)不重,邊不重,從中找出交替鏈總權(quán)值最小的那條,取相間的4條邊即為最優(yōu)解。容易理解,這種方法的運(yùn)行效率不會(huì)很高,其復(fù)雜度與窮舉法幾乎無異。
6諸算法之對(duì)比分析
匯總上述幾種求解思路得表7。不難看出,不論是從求解工具、可操作性、分析思路,還是求解前的數(shù)據(jù)準(zhǔn)備,甚至復(fù)雜度等諸多方面來看,基于成績(jī)差的表上求解算法都處于十分突出的位置。
鑒于水平所限,不妥或錯(cuò)誤難免,敬請(qǐng)大家批評(píng)指正!