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

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

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

1 基本問題描述

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

2 遺傳算法解決運動員最佳配對問題原理

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

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

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

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

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

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

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

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

引入進程因子kshift和收斂因子kc，

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

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

4 對比實驗

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

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

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

5 結(jié)語

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