段明秀，李 鈺，賴鵬飛，廖嘉琪

(吉首大學(xué)信息科學(xué)與工程學(xué)院，湖南 吉首 416000)

遺傳算法基于“適者生存”的生物進(jìn)化自然法則，廣泛應(yīng)用于函數(shù)優(yōu)化、組合優(yōu)化、遺傳編程和機(jī)器學(xué)習(xí)等領(lǐng)域，在求解旅行商問題、背包問題和裝箱問題等各種非確定性多項(xiàng)式(Non-Deterministic Polynomia,NP)難度的組合優(yōu)化問題時(shí)效果顯著.運(yùn)動(dòng)員最佳配對(duì)問題是一個(gè)NP完全問題，在問題規(guī)模較大、搜索空間急劇擴(kuò)張時(shí)，用回溯法[1]求解較困難.因此，筆者考慮采用帶自適應(yīng)調(diào)節(jié)參數(shù)的遺傳算法來進(jìn)行求解.

1 基本問題描述

設(shè)一個(gè)羽毛球隊(duì)有男女運(yùn)動(dòng)員各n人，給定2個(gè)n×n矩陣P和Q，其中Pij表示男運(yùn)動(dòng)員i和女運(yùn)動(dòng)員j配對(duì)組成混合雙打的男運(yùn)動(dòng)員競賽優(yōu)勢(shì)，Qij表示女運(yùn)動(dòng)員i和男運(yùn)動(dòng)員j配對(duì)組成混合雙打的女運(yùn)動(dòng)員競賽優(yōu)勢(shì).受技術(shù)配合和心理狀態(tài)等因素的影響，Pij不一定等于Qji.男運(yùn)動(dòng)員i和女運(yùn)動(dòng)員j配對(duì)組成混合雙打的男女雙方競賽優(yōu)勢(shì)為PijQji.問題：設(shè)計(jì)一個(gè)男女運(yùn)動(dòng)員的最佳配對(duì)方法,使得各組男女雙方競賽優(yōu)勢(shì)乘積的總和達(dá)到最大.

2 遺傳算法解決運(yùn)動(dòng)員最佳配對(duì)問題原理

運(yùn)動(dòng)員最佳配對(duì)問題是組合優(yōu)化問題，即在給定的配對(duì)集合中尋找最優(yōu)配對(duì).對(duì)于這類問題，許多學(xué)者將主要的精力集中在尋求滿意解上.遺傳算法是尋找滿意解的有力工具.在給定的種群中，遺傳算法通過選擇、交叉和變異操作進(jìn)化種群，在一定的進(jìn)化代數(shù)內(nèi)收斂于一個(gè)適應(yīng)度值較高的個(gè)體[2-3].

采用遺傳算法求解運(yùn)動(dòng)員最佳配對(duì)問題，主要需要確定編碼和適應(yīng)度函數(shù).遺傳算法不能直接處理問題空間的參數(shù)，必須將它們轉(zhuǎn)換成遺傳空間的由基因按一定結(jié)構(gòu)組成的染色體或個(gè)體(即編碼).適應(yīng)度函數(shù)是個(gè)體適應(yīng)度的量化評(píng)價(jià)方法，是種群進(jìn)化的依據(jù).

編碼：個(gè)體的基因?yàn)榕\(yùn)動(dòng)員的編號(hào)1～N(所有編號(hào)不重復(fù))，相應(yīng)的位置數(shù)為男運(yùn)動(dòng)員的編號(hào).例如，值為2,3,1的染色體，表示女運(yùn)動(dòng)員2與男運(yùn)動(dòng)員1配對(duì)、女運(yùn)動(dòng)員3與男運(yùn)動(dòng)員2配對(duì)和女運(yùn)動(dòng)員1與男運(yùn)動(dòng)員3配對(duì).染色體的特征值與運(yùn)動(dòng)員總數(shù)是相等的，如值為2,3,1的染色體，運(yùn)動(dòng)員總數(shù)為3.

適應(yīng)度函數(shù)：問題最終求解的是男女運(yùn)動(dòng)員雙方競賽優(yōu)勢(shì)的最大總和，因此將一次匹配的競賽優(yōu)勢(shì)總和作為個(gè)體的適應(yīng)度.適應(yīng)度值越大，表示競賽優(yōu)勢(shì)總和越大，該個(gè)體越接近最優(yōu)解.

3 自適應(yīng)調(diào)整參數(shù)

遺傳算法在初始化時(shí)需要設(shè)定種群規(guī)模、交叉概率和變異概率等參數(shù).參數(shù)對(duì)遺傳算法的性能的影響較大，關(guān)系到精度、可靠性和計(jì)算時(shí)間等.基于參數(shù)應(yīng)隨著遺傳進(jìn)化而適應(yīng)變化的觀點(diǎn)，劉瑞國等[4]提出了自適應(yīng)算子概率方法，即利用種群的最大適應(yīng)度與平均適應(yīng)度的差來自適應(yīng)調(diào)整交叉概率和變異概率.

自適應(yīng)算子概率方法用fmax表示種群的最大適應(yīng)度，favg表示種群的平均適應(yīng)度，fmax-favg表示種群的收斂程度.當(dāng)fmax-favg減小時(shí)，表示favg向fmax靠攏，即向最優(yōu)解靠攏，說明種群在進(jìn)化.

種群進(jìn)化初期，解空間較分散，為了快速搜索解空間，應(yīng)使交叉概率增大；同時(shí)，為了防止有效基因被破壞，應(yīng)使變異概率減小.進(jìn)化后期，種群中的個(gè)體彼此非常接近，為了避免不必要的近親繁殖，應(yīng)使交叉概率減小，變異概率增大.

引入進(jìn)程因子kshift和收斂因子kc，

其中fmax-avg表示到目前為止fmax-favg的最大值.那么，交叉概率和變異概率分別為

其中：fcurr表示要交叉的2個(gè)個(gè)體的適應(yīng)度值中較大的一個(gè)；k1，k2，k3，k4是[0，1]之間取值的常數(shù).

4 對(duì)比實(shí)驗(yàn)

為了驗(yàn)證自適應(yīng)遺傳算法求解運(yùn)動(dòng)員最佳配對(duì)問題的有效性，在不同規(guī)模下對(duì)比其與回溯法的最優(yōu)值求解運(yùn)行時(shí)間.自適應(yīng)遺傳算法中k2,k4取0.5，k1,k3取1.運(yùn)行時(shí)間對(duì)比結(jié)果見表1.

表1 回溯法和自適應(yīng)遺傳算法的運(yùn)行時(shí)間對(duì)比結(jié)果Table 1 Comparison of Running Time of Backtracking Method and Genetic Algorithm s

從表1可以看出，由于自適應(yīng)遺傳算法引入了進(jìn)程因子，使種群在不同進(jìn)化階段采取不同的進(jìn)化方式，引入了收斂因子對(duì)種群的整體交叉和變異概率進(jìn)行自適應(yīng)調(diào)整,因此采用其求解運(yùn)動(dòng)員最佳配對(duì)問題，在保持群體多樣性和全局收斂性的同時(shí),能有效地提高收斂速度，算法效率明顯高于回溯法.

5 結(jié)語

引入進(jìn)程因子和收斂因子，對(duì)遺傳算法進(jìn)行自適應(yīng)調(diào)節(jié).當(dāng)運(yùn)動(dòng)員最佳配對(duì)問題的規(guī)模增大時(shí)，采用自適應(yīng)遺傳算法仍然能快速地得到一個(gè)滿意解.但是，種群數(shù)目參數(shù)的調(diào)整依然缺乏自適應(yīng)性.交叉概率和變異概率決定算法是否會(huì)陷入局部最優(yōu)，而種群數(shù)目直接決定算法的效率，因此，下一步筆者將會(huì)研究種群數(shù)目與種群收斂程度的關(guān)聯(lián)性.