殷昭寧

連云港潤眾制藥有限公司，江蘇連云港 222069

0 引言

近幾年，結合決策者的偏好解決多目標優(yōu)化問題，成為進化計算領域的研究熱點之一。這是因為，已有進化多目標優(yōu)化方法的目的是找到收斂性好且分布均勻的Pareto最優(yōu)解集，而在實際應用中，往往僅需要找到一個最滿意解或最滿意區(qū)域。因此，和單目標優(yōu)化問題相比，在多目標優(yōu)化中，有兩個同等重要的任務：搜索Pareto優(yōu)化解和選擇最滿意解[1]。2個任務之間的先后關系決定了3種不同的方法：第一種是先決策后優(yōu)化方法，也稱為先驗方法[2]；第二種是先優(yōu)化再決策方法，也稱為后驗方法[3]；第三種是邊優(yōu)化邊決策方法，也稱為交互方法[4]。

與先驗法和后驗法相比，交互方法有如下3個優(yōu)點[1]：1）交互方法所需的偏好信息比先驗方法簡單得多；2）交互方法比后驗方法需要更少的計算開銷；3）當決策者控制搜索進程時，可以通過介入進程了解潛在的候選解，對最終的選擇更加自信。因此，交互方法是一種解決實際多目標優(yōu)化問題非常有前景的方法。下面介紹近兩年有關交互方法的研究工作。

1 基于偏好的交互進化多目標優(yōu)化算法

1.1 簡單交互方法

張華軍等提出一種最大化個人偏好的多目標優(yōu)化進化算法，首先采用加權法將多目標優(yōu)化問題轉(zhuǎn)化為單目標優(yōu)化問題，再利用遺傳算法進行全局搜索，在滿足個人偏好約束條件下，每一代進化結束后，通過求解一個約束優(yōu)化問題，獲得能夠使種群綜合適應度具有最大方差的權重組合，從而最大化個人偏好[4]。

Chen 等采用基于偏好導向的精英選擇策略選擇父代個體，從而提供給用戶更多接近其偏好的解[5]。

Chaudhuri和Deb提出一種解決多目標優(yōu)化問題的交互集成方法，該方法結合多種多目標進化算法和一些普遍且有效的多準則決策方法，用邊優(yōu)化邊決策過程，開發(fā)了功能強大、使用靈活的交互多目標優(yōu)化和決策進化算法軟件[6]。

利用決策者關于目標相對重要性的偏好信息，Rachmawati和 Srinivasan 提出了目標相對重要性的數(shù)學模型和提取算法，并給出了將提取的偏好信息和NSGA-II結合的3種方法[7]。

1.2 構建偏好的代理模型

從近2年的相關工作可以看出，在優(yōu)化過程中，定期與決策者交互，逐漸獲取其偏好信息，并構建偏好函數(shù)的代理模型成為研究熱點。方法可分為3類：基于機器學習的方法、基于擬合的方法和基于偏好凸錐或多面體錐的方法。

結合基于事例的有監(jiān)督在線學習策略和進化算法，Krettek等提出一個新的多目標交互進化優(yōu)化方法。決策者每隔n代參與決策，將當前Pareto最優(yōu)解集聚類后，決策者對類中心兩兩比較，利用兩兩相似性學習決策者的偏好[8]。

Battiti 和 Passerini采用反應搜索方法，提出一種多目標交互進化算法，該算法將在線機器學習作為自適應優(yōu)化策略的組成部分，實現(xiàn)邊優(yōu)化邊學習[9]。

上述2種方法在優(yōu)化過程中逐漸獲取決策者的偏好信息，并用機器學習方法構建決策者偏好的代理模型，以學習決策者的偏好，指導種群的后續(xù)進化。

Deb等提出一種基于偏好的漸進多目標交互進化算法。在進化固定代數(shù)后，通過逐漸獲取決策者的偏好信息，構建滿足該信息的嚴格增加價值函數(shù)，利用基于偏好的占優(yōu)關系和終止條件，引導算法向最滿意解搜索。該方法可以得到?jīng)Q策者偏好的顯式表示，但需事先給出函數(shù)的類型[10]。

在文獻[10]的基礎上，Sinha等提出一個擬合用戶偏好價值函數(shù)的廣義多項式函數(shù)，該函數(shù)的乘積項個數(shù)是任意可變的，這樣可以有效減少價值函數(shù)不能擬合決策者偏好的情形[11]。

上述2種方法利用決策者定期提供的偏好信息，用一個優(yōu)化過程擬合決策者的偏好，該方法可以得到?jīng)Q策者偏好的顯式表示，但需事先給出函數(shù)的類型。

Fowler等針對多目標背包問題，提出一種擬凹偏好函數(shù)的多目標交互進化優(yōu)化方法。該方法定期提交部分非被支配解給決策者，利用獲得的偏好信息生成偏好錐，對決策者沒有評價的非被支配解隱式排序，引導算法向決策者偏好的區(qū)域搜索，最終得到?jīng)Q策者的最滿意解[12]。

Sinha等利用多面體錐修改占優(yōu)關系，提出一個基于偏好的多目標進化優(yōu)化方法。通過逐漸獲取決策者的偏好信息不斷修改多面體錐，用該多面體錐縮減搜索空間，在感興趣區(qū)域中找到更好的優(yōu)化解[13]。

上述2種方法的共同特點是：不需要知道決策者偏好的顯式形式，利用決策者從候選解對應的目標函數(shù)值中選出的最差值或最好值和其他候選解對應的目標函數(shù)值，在目標空間中構建反映決策者偏好的凸錐或多面體錐，基于該隱式偏好函數(shù)改進非被支配解的排序策略，將搜索集中在感興趣的區(qū)域。

2 結論

在構建偏好代理模型的方法中，前2種需要對所有候選解兩兩比較其優(yōu)劣，相比較而言，基于凸錐或多面體錐的方法，僅需要從候選解對應的目標函數(shù)值中選出最好值和最差值，該方法可以大大減輕決策者的比較負擔，同時也可以避免因選擇合適顯式偏好函數(shù)而帶來的難題。因此，構建反應決策者偏好的多面體是值得進一步研究的方向。

此外，雖然上面述及的方法可以有效解決實際多目標優(yōu)化問題，得到?jīng)Q策者的最滿意解，數(shù)值實驗也證實了上述方法對很多目標優(yōu)化問題優(yōu)越的求解能力，但只適用于確定參數(shù)多目標優(yōu)化問題。對于區(qū)間參數(shù)多目標優(yōu)化問題，至今還沒有結合決策者偏好的求解方法，更不必說邊優(yōu)化邊決策的方法。進化計算的權威期刊《IEEE Transactions on Evolutionary Computation》 2010年10月特刊表明，以后的多目標優(yōu)化算法將廣泛地在優(yōu)化過程中融入決策者的偏好信息[14]。因此，結合決策者偏好信息解決區(qū)間參數(shù)多目標優(yōu)化問題，是富有挑戰(zhàn)性和有意義的工作。

[1]Branke J., Deb K., Miettinen K., Slowinski R.. Multi-objective Optimization Interactive and Evolutionary Approaches (LNCS 5252)[M].Heidelberg:Springer, 2008.

[2]Zio E., Baraldi P., Pedroni N..Optimal power system generation scheduling by multi-objective genetic algorithms with preferences[J].Reliability Engineering and System Safety, 2009, 94(2): 432-444.

[3]Lee D.H., Kim K.J., Koksalan M..A posterior preference articulation approach to multiresponse surface optimization[J].European Journal of Operational Research, 2011, 210(2): 301-309.

[4]張華軍，趙金，王瑞.最大化個人偏好的多目標優(yōu)化進化算法[J].信息與控制，2010, 39(2): 212-217.

[5]Chen Z.H., Zhuang Z. Q., Huang F.H., Lee J.S..User-preference-oriented multi-objective optimization algorithm[C].In Proceedings of 2010 International Computer Symposium, 2010: 1045-1049.

[6]Chaudhuri S., Deb K..An interactive evolutionary multi-objective optimization and decision making procedure[J].Applied Soft Computing, 2010,10(2): 496-511.

[7]Rachmawati L., Srinivasan D..Incorporating the notion of relative importance of objectives in evolutionary multi-objective optimization[J].IEEE transactions on evolutionary computation, 2010, 14(4):530-546.

[8]Krettek J., Braun J., Hoffmann F., Bertram T., Ewald T., Schubert H.G., Lausch H..Interactive evolutionary multi-objective optimization for hHydraulic valve controller parameters[C].In Proceedings of the IEEE/ASME International Conference on Advanced Intelligent Mechatronics, 2009, 816-821.

[9]Battiti R., Passerini A..Brain computer evolutionary multiobjective optimization: A genetic algorithm adapting to the decision maker[J].IEEE transactions on evolutionary computation, 2010, 14(5):671-687.

[10]Deb K., Sinha A., Korhonen P., Wallenius J..An interactive evolutionary multi-objective optimization method based on progressively approximated value functions[R].Kanpur Genetic Algorithms Laboratory,Department of Mechanical engineering, Indian Institue of Technology, Kanpur, India, KanGAL Report Number 2009005, 2009.

[11]Sinha A., Deb K., Korhonen P., Wallenius J..Progressively interactive evolutionary multiobjective optimization method using generalized polynomial value functions[C].In Proceedings of the IEEE Congress on Evolutionary Computation, 2010: 1-8.

[12]Fowler J.W., Gel E.S., Koksalan M.M.,Korhonen P., Marquis J.L., Wallenius J..Interactive evolutionary multi-objective optimization for quasiconcave preference functions[J]. European Journal of Operational Research, 2010, 206(2): 417-425.

[13]Sinha A., Deb K., Korhonen P., Wallenius J..An interactive evolutionary multi-objective optimization method based on polyhedral cones[C].In Proceedings of Learning and Intelligent Optimization Conference,2010, 6073: 318-332.

[14]Deb K., Koksalan M..Guest Editorial: Special issue on preference-based multi-objective evolutionary algorithms[J].IEEE transactions on evolutionary computation, 2010, 14(5): 669-670.