周江+　王國華　+趙躍龍

摘要為了在動態(tài)環(huán)境中快速地跟蹤變化后的最優(yōu)解集，提出一種基于聚類預測模型的動態(tài)多目標優(yōu)化算法.通過對種群聚類，提高預測解集的分布性與廣泛性，為分段預測做準備，然后利用歷史信息對每個子類的中心點和形狀進行預測，在環(huán)境變化后，預測產生的每個子類共同構成整個新的初始種群，有引導性地增加了種群的多樣性，使算法能快速跟蹤新的最優(yōu)解集.在標準動態(tài)測試問題上進行算法測試，實驗結果表明所提算法能快速地適應環(huán)境的動態(tài)變化，所獲解集具有較好的收斂性和分布性.

關鍵詞動態(tài)多目標，聚類，預測，進化算法

中圖分類號O224文獻標識碼A文章編號1000-2537（2014）02-0056-06

現(xiàn)實世界中的許多優(yōu)化問題都是動態(tài)多目標優(yōu)化問題（dynamic multi-objective optimization problems，簡稱DMOPs），多個目標之間經常沖突，同時目標函數(shù)、約束函數(shù)和相關參數(shù)都可能隨著時間的變化而改變，如何跟蹤變化后新的最優(yōu)解集是求解動態(tài)多目標優(yōu)化問題的主要難點[1].在處理DMOPs上，靜態(tài)的方法具有明顯的局限性.傳統(tǒng)的進化算法目標是使種群逐漸收斂，最終得到Pareto最優(yōu)解集[2-3].而種群一旦收斂，種群的多樣性減少，很難適應新的環(huán)境變化.因此，只有對靜態(tài)算法加以改進，才能更好地適應于動態(tài)環(huán)境[4].

近些年來，研究者們在靜態(tài)算法的基礎上設計了許多新的方法來求解DMOPs[5-8]，這些方法大多集中在保持種群多樣性上，通過隨機移民，動態(tài)遷移，超變異和多種群等策略增加種群多樣性，使新的種群具有響應環(huán)境變化的能力.然而這些方法是一種隨機的、不確定的多樣性保持策略，不能為適應新的環(huán)境提供正確的引導，因此具有盲目性，收斂速度是存在的主要問題.

如何充分利用歷史信息，通過預測為當前環(huán)境下的種群進化提供正確的引導已成為求解DMOPs的又一新的發(fā)展趨勢.目前，這類方法已受到了研究者的廣泛關注.2006年，Hatzakis等人提出了一種前饋法[9]，該方法記錄目標空間相鄰歷史Pareto前沿面上的邊界點信息，通過自回歸模型預測新的最優(yōu)解集的位置，但是該方法僅記錄歷史解集上邊界點的信息并加以預測，采用的預測模型提供的信息有限，未能充分考慮環(huán)境變化之間可能存在的關聯(lián)性，因而影響了預測效果.2011年，彭星光等人提出了一種基于Pareto解集關聯(lián)與預測的動態(tài)多目標進化算法[10]，然而該方法僅根據相鄰時間序列上的解集關聯(lián)性進行預測，并且僅預測超塊中的代表性個體，不能預測新的最優(yōu)解集的形狀，當環(huán)境發(fā)生較大程度的變化時，預測的解集將出現(xiàn)偏差.因此，怎樣設計一個更為精確的預測模型仍是現(xiàn)在的研究重點.

基于以上分析，為了避免盲目地增加種群多樣性，并充分利用歷史信息，提高預測模型的準確性，使其能適應于不同程度的環(huán)境變化，本文提出一種基于聚類預測模型的動態(tài)多目標進化算法（A dynamic multi-objective evolutionary algorithm based on cluster prediction model，簡稱CPM-DMOEA），通過對種群聚類建立預測模型，將對每個子類的預測分為對中心點的預測和對形狀的預測，從而產生新的預測種群.在動態(tài)多目標優(yōu)化算法的整體框架下進行迭代，通過標準動態(tài)測試問題進行仿真比較，實驗結果充分驗證了所提算法的有效性.

1優(yōu)化問題及相關概念

4結論

本文提出了一種基于聚類預測模型的動態(tài)多目標優(yōu)化算法，算法通過建立聚類預測模型，對種群進行分段預測，提高了預測解集的分布性和廣泛性.根據歷史信息預測每個子類的中心點和形狀，從而在環(huán)境變化后產生整個新的初始種群.預測產生的新種群能有效地對新環(huán)境下的PS潛在區(qū)域進行探索，加速了算法在新環(huán)境下的收斂.利用三個標準的動態(tài)多目標測試函數(shù)，比較了CPM-DMOEA與其他三種動態(tài)多目標優(yōu)化算法，分析結果表明了本文算法的有效性，能更好地適應不同程度的環(huán)境變化，快速地跟蹤新的Pareto最優(yōu)解集.

未來將把CPM-DMOEA算法應用于更多的實際問題中，以進一步分析其在不同的動態(tài)環(huán)境中的表現(xiàn)，不斷地改善算法的性能.

參考文獻：

[1]FARINA M， DEB KK， AMATO P. Dynamic multiobjective optimization problems： test cases， approximations， and applications[J]. IEEE Trans Evolut Comput， 2004，8（5）：425-442.

[2]鄭金華.多目標進化算法及其應用[M].北京：科學出版社， 2007.

[3]COELLO C A， VAN VELDHUIZEN D A， LAMONT G B. Evolutionary algorithms for solving multi-objective problems[M]. New York： Springer-Verlag， 2007.

[4]NGUYEN T T， YANG S X， BRANKE J. Evolutionary dynamic optimization： A survey of the state of the art[J]. Swarm Evolut Comput， 2012（6）：1-24.

[5]尚榮華， 焦李成， 公茂果， 等. 免疫克隆算法求解動態(tài)多目標優(yōu)化問題[J]. 軟件學報， 2007，18（11）：2700-2711.

[6]DEB K， RAO U V， KARTHIK S. Dynamic multi-objective optimization and decision-making using modified NSGA-Ⅱ-a case study on hydro-thermal power scheduling[D]. in Evolutionary Multi-Criterion Optimization （EMO）， Berlin： Springer， 2007.

[7]劉淳安，王宇平.基于新模型的動態(tài)多目標優(yōu)化進化算法[J].計算機研究與發(fā)展， 2008，45（4）：603-611.

[8]GOH C K， TAN K C. A competitive-cooperative coevolutionary paradigm for dynamic multiobjective optimization[J]. IEEE Trans Evolut Comput， 2009，13（1）：103-127.

[9]武燕，劉小雄，池程芝.動態(tài)多目標優(yōu)化的預測遺傳算法[J].控制與決策， 2013，28（5）：677-682.

[10]彭星光， 徐德民， 高曉光. 基于Pareto 解集關聯(lián)與預測的動態(tài)多目標進化算法[J].控制與決策， 2011，26（4）：615-618.

[11]YAO X， LIU Y， LIN G. Evolutionary programming made faster[J]. IEEE Trans Evolut Comput， 1999，3（2）：82-102.

[12]HILLERMEIER C. Nonlinear multiobjective optimization—a generalized homotopy approach[M]. Boston： Birkhauser， 2001.

[13]ZHANG Q F， LI H. MOEA/D： A mutiobjective evolutionary algorithm based on decomposition[J]. IEEE Trans Evolut Comput， 2007，11（6）：712-731.

[14]劉敏，曾文華. 記憶增強的動態(tài)多目標分解進化算法[J].軟件學報， 2013，24（7）：1571-1588.

（編輯陳笑梅）

摘要為了在動態(tài)環(huán)境中快速地跟蹤變化后的最優(yōu)解集，提出一種基于聚類預測模型的動態(tài)多目標優(yōu)化算法.通過對種群聚類，提高預測解集的分布性與廣泛性，為分段預測做準備，然后利用歷史信息對每個子類的中心點和形狀進行預測，在環(huán)境變化后，預測產生的每個子類共同構成整個新的初始種群，有引導性地增加了種群的多樣性，使算法能快速跟蹤新的最優(yōu)解集.在標準動態(tài)測試問題上進行算法測試，實驗結果表明所提算法能快速地適應環(huán)境的動態(tài)變化，所獲解集具有較好的收斂性和分布性.

關鍵詞動態(tài)多目標，聚類，預測，進化算法

中圖分類號O224文獻標識碼A文章編號1000-2537（2014）02-0056-06

現(xiàn)實世界中的許多優(yōu)化問題都是動態(tài)多目標優(yōu)化問題（dynamic multi-objective optimization problems，簡稱DMOPs），多個目標之間經常沖突，同時目標函數(shù)、約束函數(shù)和相關參數(shù)都可能隨著時間的變化而改變，如何跟蹤變化后新的最優(yōu)解集是求解動態(tài)多目標優(yōu)化問題的主要難點[1].在處理DMOPs上，靜態(tài)的方法具有明顯的局限性.傳統(tǒng)的進化算法目標是使種群逐漸收斂，最終得到Pareto最優(yōu)解集[2-3].而種群一旦收斂，種群的多樣性減少，很難適應新的環(huán)境變化.因此，只有對靜態(tài)算法加以改進，才能更好地適應于動態(tài)環(huán)境[4].

近些年來，研究者們在靜態(tài)算法的基礎上設計了許多新的方法來求解DMOPs[5-8]，這些方法大多集中在保持種群多樣性上，通過隨機移民，動態(tài)遷移，超變異和多種群等策略增加種群多樣性，使新的種群具有響應環(huán)境變化的能力.然而這些方法是一種隨機的、不確定的多樣性保持策略，不能為適應新的環(huán)境提供正確的引導，因此具有盲目性，收斂速度是存在的主要問題.

如何充分利用歷史信息，通過預測為當前環(huán)境下的種群進化提供正確的引導已成為求解DMOPs的又一新的發(fā)展趨勢.目前，這類方法已受到了研究者的廣泛關注.2006年，Hatzakis等人提出了一種前饋法[9]，該方法記錄目標空間相鄰歷史Pareto前沿面上的邊界點信息，通過自回歸模型預測新的最優(yōu)解集的位置，但是該方法僅記錄歷史解集上邊界點的信息并加以預測，采用的預測模型提供的信息有限，未能充分考慮環(huán)境變化之間可能存在的關聯(lián)性，因而影響了預測效果.2011年，彭星光等人提出了一種基于Pareto解集關聯(lián)與預測的動態(tài)多目標進化算法[10]，然而該方法僅根據相鄰時間序列上的解集關聯(lián)性進行預測，并且僅預測超塊中的代表性個體，不能預測新的最優(yōu)解集的形狀，當環(huán)境發(fā)生較大程度的變化時，預測的解集將出現(xiàn)偏差.因此，怎樣設計一個更為精確的預測模型仍是現(xiàn)在的研究重點.

基于以上分析，為了避免盲目地增加種群多樣性，并充分利用歷史信息，提高預測模型的準確性，使其能適應于不同程度的環(huán)境變化，本文提出一種基于聚類預測模型的動態(tài)多目標進化算法（A dynamic multi-objective evolutionary algorithm based on cluster prediction model，簡稱CPM-DMOEA），通過對種群聚類建立預測模型，將對每個子類的預測分為對中心點的預測和對形狀的預測，從而產生新的預測種群.在動態(tài)多目標優(yōu)化算法的整體框架下進行迭代，通過標準動態(tài)測試問題進行仿真比較，實驗結果充分驗證了所提算法的有效性.

1優(yōu)化問題及相關概念

4結論

本文提出了一種基于聚類預測模型的動態(tài)多目標優(yōu)化算法，算法通過建立聚類預測模型，對種群進行分段預測，提高了預測解集的分布性和廣泛性.根據歷史信息預測每個子類的中心點和形狀，從而在環(huán)境變化后產生整個新的初始種群.預測產生的新種群能有效地對新環(huán)境下的PS潛在區(qū)域進行探索，加速了算法在新環(huán)境下的收斂.利用三個標準的動態(tài)多目標測試函數(shù)，比較了CPM-DMOEA與其他三種動態(tài)多目標優(yōu)化算法，分析結果表明了本文算法的有效性，能更好地適應不同程度的環(huán)境變化，快速地跟蹤新的Pareto最優(yōu)解集.

未來將把CPM-DMOEA算法應用于更多的實際問題中，以進一步分析其在不同的動態(tài)環(huán)境中的表現(xiàn)，不斷地改善算法的性能.

參考文獻：

[1]FARINA M， DEB KK， AMATO P. Dynamic multiobjective optimization problems： test cases， approximations， and applications[J]. IEEE Trans Evolut Comput， 2004，8（5）：425-442.

[2]鄭金華.多目標進化算法及其應用[M].北京：科學出版社， 2007.

[3]COELLO C A， VAN VELDHUIZEN D A， LAMONT G B. Evolutionary algorithms for solving multi-objective problems[M]. New York： Springer-Verlag， 2007.

[4]NGUYEN T T， YANG S X， BRANKE J. Evolutionary dynamic optimization： A survey of the state of the art[J]. Swarm Evolut Comput， 2012（6）：1-24.

[5]尚榮華， 焦李成， 公茂果， 等. 免疫克隆算法求解動態(tài)多目標優(yōu)化問題[J]. 軟件學報， 2007，18（11）：2700-2711.

[6]DEB K， RAO U V， KARTHIK S. Dynamic multi-objective optimization and decision-making using modified NSGA-Ⅱ-a case study on hydro-thermal power scheduling[D]. in Evolutionary Multi-Criterion Optimization （EMO）， Berlin： Springer， 2007.

[7]劉淳安，王宇平.基于新模型的動態(tài)多目標優(yōu)化進化算法[J].計算機研究與發(fā)展， 2008，45（4）：603-611.

[8]GOH C K， TAN K C. A competitive-cooperative coevolutionary paradigm for dynamic multiobjective optimization[J]. IEEE Trans Evolut Comput， 2009，13（1）：103-127.

[9]武燕，劉小雄，池程芝.動態(tài)多目標優(yōu)化的預測遺傳算法[J].控制與決策， 2013，28（5）：677-682.

[10]彭星光， 徐德民， 高曉光. 基于Pareto 解集關聯(lián)與預測的動態(tài)多目標進化算法[J].控制與決策， 2011，26（4）：615-618.

[11]YAO X， LIU Y， LIN G. Evolutionary programming made faster[J]. IEEE Trans Evolut Comput， 1999，3（2）：82-102.

[12]HILLERMEIER C. Nonlinear multiobjective optimization—a generalized homotopy approach[M]. Boston： Birkhauser， 2001.

[13]ZHANG Q F， LI H. MOEA/D： A mutiobjective evolutionary algorithm based on decomposition[J]. IEEE Trans Evolut Comput， 2007，11（6）：712-731.

[14]劉敏，曾文華. 記憶增強的動態(tài)多目標分解進化算法[J].軟件學報， 2013，24（7）：1571-1588.

（編輯陳笑梅）

摘要為了在動態(tài)環(huán)境中快速地跟蹤變化后的最優(yōu)解集，提出一種基于聚類預測模型的動態(tài)多目標優(yōu)化算法.通過對種群聚類，提高預測解集的分布性與廣泛性，為分段預測做準備，然后利用歷史信息對每個子類的中心點和形狀進行預測，在環(huán)境變化后，預測產生的每個子類共同構成整個新的初始種群，有引導性地增加了種群的多樣性，使算法能快速跟蹤新的最優(yōu)解集.在標準動態(tài)測試問題上進行算法測試，實驗結果表明所提算法能快速地適應環(huán)境的動態(tài)變化，所獲解集具有較好的收斂性和分布性.

關鍵詞動態(tài)多目標，聚類，預測，進化算法

中圖分類號O224文獻標識碼A文章編號1000-2537（2014）02-0056-06

現(xiàn)實世界中的許多優(yōu)化問題都是動態(tài)多目標優(yōu)化問題（dynamic multi-objective optimization problems，簡稱DMOPs），多個目標之間經常沖突，同時目標函數(shù)、約束函數(shù)和相關參數(shù)都可能隨著時間的變化而改變，如何跟蹤變化后新的最優(yōu)解集是求解動態(tài)多目標優(yōu)化問題的主要難點[1].在處理DMOPs上，靜態(tài)的方法具有明顯的局限性.傳統(tǒng)的進化算法目標是使種群逐漸收斂，最終得到Pareto最優(yōu)解集[2-3].而種群一旦收斂，種群的多樣性減少，很難適應新的環(huán)境變化.因此，只有對靜態(tài)算法加以改進，才能更好地適應于動態(tài)環(huán)境[4].

近些年來，研究者們在靜態(tài)算法的基礎上設計了許多新的方法來求解DMOPs[5-8]，這些方法大多集中在保持種群多樣性上，通過隨機移民，動態(tài)遷移，超變異和多種群等策略增加種群多樣性，使新的種群具有響應環(huán)境變化的能力.然而這些方法是一種隨機的、不確定的多樣性保持策略，不能為適應新的環(huán)境提供正確的引導，因此具有盲目性，收斂速度是存在的主要問題.

如何充分利用歷史信息，通過預測為當前環(huán)境下的種群進化提供正確的引導已成為求解DMOPs的又一新的發(fā)展趨勢.目前，這類方法已受到了研究者的廣泛關注.2006年，Hatzakis等人提出了一種前饋法[9]，該方法記錄目標空間相鄰歷史Pareto前沿面上的邊界點信息，通過自回歸模型預測新的最優(yōu)解集的位置，但是該方法僅記錄歷史解集上邊界點的信息并加以預測，采用的預測模型提供的信息有限，未能充分考慮環(huán)境變化之間可能存在的關聯(lián)性，因而影響了預測效果.2011年，彭星光等人提出了一種基于Pareto解集關聯(lián)與預測的動態(tài)多目標進化算法[10]，然而該方法僅根據相鄰時間序列上的解集關聯(lián)性進行預測，并且僅預測超塊中的代表性個體，不能預測新的最優(yōu)解集的形狀，當環(huán)境發(fā)生較大程度的變化時，預測的解集將出現(xiàn)偏差.因此，怎樣設計一個更為精確的預測模型仍是現(xiàn)在的研究重點.

基于以上分析，為了避免盲目地增加種群多樣性，并充分利用歷史信息，提高預測模型的準確性，使其能適應于不同程度的環(huán)境變化，本文提出一種基于聚類預測模型的動態(tài)多目標進化算法（A dynamic multi-objective evolutionary algorithm based on cluster prediction model，簡稱CPM-DMOEA），通過對種群聚類建立預測模型，將對每個子類的預測分為對中心點的預測和對形狀的預測，從而產生新的預測種群.在動態(tài)多目標優(yōu)化算法的整體框架下進行迭代，通過標準動態(tài)測試問題進行仿真比較，實驗結果充分驗證了所提算法的有效性.

1優(yōu)化問題及相關概念

4結論

本文提出了一種基于聚類預測模型的動態(tài)多目標優(yōu)化算法，算法通過建立聚類預測模型，對種群進行分段預測，提高了預測解集的分布性和廣泛性.根據歷史信息預測每個子類的中心點和形狀，從而在環(huán)境變化后產生整個新的初始種群.預測產生的新種群能有效地對新環(huán)境下的PS潛在區(qū)域進行探索，加速了算法在新環(huán)境下的收斂.利用三個標準的動態(tài)多目標測試函數(shù)，比較了CPM-DMOEA與其他三種動態(tài)多目標優(yōu)化算法，分析結果表明了本文算法的有效性，能更好地適應不同程度的環(huán)境變化，快速地跟蹤新的Pareto最優(yōu)解集.

未來將把CPM-DMOEA算法應用于更多的實際問題中，以進一步分析其在不同的動態(tài)環(huán)境中的表現(xiàn)，不斷地改善算法的性能.

參考文獻：

[1]FARINA M， DEB KK， AMATO P. Dynamic multiobjective optimization problems： test cases， approximations， and applications[J]. IEEE Trans Evolut Comput， 2004，8（5）：425-442.

[2]鄭金華.多目標進化算法及其應用[M].北京：科學出版社， 2007.

[3]COELLO C A， VAN VELDHUIZEN D A， LAMONT G B. Evolutionary algorithms for solving multi-objective problems[M]. New York： Springer-Verlag， 2007.

[4]NGUYEN T T， YANG S X， BRANKE J. Evolutionary dynamic optimization： A survey of the state of the art[J]. Swarm Evolut Comput， 2012（6）：1-24.

[5]尚榮華， 焦李成， 公茂果， 等. 免疫克隆算法求解動態(tài)多目標優(yōu)化問題[J]. 軟件學報， 2007，18（11）：2700-2711.

[6]DEB K， RAO U V， KARTHIK S. Dynamic multi-objective optimization and decision-making using modified NSGA-Ⅱ-a case study on hydro-thermal power scheduling[D]. in Evolutionary Multi-Criterion Optimization （EMO）， Berlin： Springer， 2007.

[7]劉淳安，王宇平.基于新模型的動態(tài)多目標優(yōu)化進化算法[J].計算機研究與發(fā)展， 2008，45（4）：603-611.

[8]GOH C K， TAN K C. A competitive-cooperative coevolutionary paradigm for dynamic multiobjective optimization[J]. IEEE Trans Evolut Comput， 2009，13（1）：103-127.

[9]武燕，劉小雄，池程芝.動態(tài)多目標優(yōu)化的預測遺傳算法[J].控制與決策， 2013，28（5）：677-682.

[10]彭星光， 徐德民， 高曉光. 基于Pareto 解集關聯(lián)與預測的動態(tài)多目標進化算法[J].控制與決策， 2011，26（4）：615-618.

[11]YAO X， LIU Y， LIN G. Evolutionary programming made faster[J]. IEEE Trans Evolut Comput， 1999，3（2）：82-102.

[12]HILLERMEIER C. Nonlinear multiobjective optimization—a generalized homotopy approach[M]. Boston： Birkhauser， 2001.

[13]ZHANG Q F， LI H. MOEA/D： A mutiobjective evolutionary algorithm based on decomposition[J]. IEEE Trans Evolut Comput， 2007，11（6）：712-731.

[14]劉敏，曾文華. 記憶增強的動態(tài)多目標分解進化算法[J].軟件學報， 2013，24（7）：1571-1588.

（編輯陳笑梅）