一种基于聚类预测模型的动态多目标进化算法

周江+　王国华　+赵跃龙

摘要为了在动态环境中快速地跟踪变化后的最优解集，提出一种基于聚类预测模型的动态多目标优化算法.通过对种群聚类，提高预测解集的分布性与广泛性，为分段预测做准备，然后利用历史信息对每个子类的中心点和形状进行预测，在环境变化后，预测产生的每个子类共同构成整个新的初始种群，有引导性地增加了种群的多样性，使算法能快速跟踪新的最优解集.在标准动态测试问题上进行算法测试，实验结果表明所提算法能快速地适应环境的动态变化，所获解集具有较好的收敛性和分布性.

关键词动态多目标，聚类，预测，进化算法

中图分类号O224文献标识码A文章编号1000-2537（2014）02-0056-06

现实世界中的许多优化问题都是动态多目标优化问题（dynamic multi-objective optimization problems，简称DMOPs），多个目标之间经常冲突，同时目标函数、约束函数和相关参数都可能随着时间的变化而改变，如何跟踪变化后新的最优解集是求解动态多目标优化问题的主要难点[1].在处理DMOPs上，静态的方法具有明显的局限性.传统的进化算法目标是使种群逐渐收敛，最终得到Pareto最优解集[2-3].而种群一旦收敛，种群的多样性减少，很难适应新的环境变化.因此，只有对静态算法加以改进，才能更好地适应于动态环境[4].

近些年来，研究者们在静态算法的基础上设计了许多新的方法来求解DMOPs[5-8]，这些方法大多集中在保持种群多样性上，通过随机移民，动态迁移，超变异和多种群等策略增加种群多样性，使新的种群具有响应环境变化的能力.然而这些方法是一种随机的、不确定的多样性保持策略，不能为适应新的环境提供正确的引导，因此具有盲目性，收敛速度是存在的主要问题.

如何充分利用历史信息，通过预测为当前环境下的种群进化提供正确的引导已成为求解DMOPs的又一新的发展趋势.目前，这类方法已受到了研究者的广泛关注.2006年，Hatzakis等人提出了一种前馈法[9]，该方法记录目标空间相邻历史Pareto前沿面上的边界点信息，通过自回归模型预测新的最优解集的位置，但是该方法仅记录历史解集上边界点的信息并加以预测，采用的预测模型提供的信息有限，未能充分考虑环境变化之间可能存在的关联性，因而影响了预测效果.2011年，彭星光等人提出了一种基于Pareto解集关联与预测的动态多目标进化算法[10]，然而该方法仅根据相邻时间序列上的解集关联性进行预测，并且仅预测超块中的代表性个体，不能预测新的最优解集的形状，当环境发生较大程度的变化时，预测的解集将出现偏差.因此，怎样设计一个更为精确的预测模型仍是现在的研究重点.

基于以上分析，为了避免盲目地增加种群多样性，并充分利用历史信息，提高预测模型的准确性，使其能适应于不同程度的环境变化，本文提出一种基于聚类预测模型的动态多目标进化算法（A dynamic multi-objective evolutionary algorithm based on cluster prediction model，简称CPM-DMOEA），通过对种群聚类建立预测模型，将对每个子类的预测分为对中心点的预测和对形状的预测，从而产生新的预测种群.在动态多目标优化算法的整体框架下进行迭代，通过标准动态测试问题进行仿真比较，实验结果充分验证了所提算法的有效性.

1优化问题及相关概念

4结论

本文提出了一种基于聚类预测模型的动态多目标优化算法，算法通过建立聚类预测模型，对种群进行分段预测，提高了预测解集的分布性和广泛性.根据历史信息预测每个子类的中心点和形状，从而在环境变化后产生整个新的初始种群.预测产生的新种群能有效地对新环境下的PS潜在区域进行探索，加速了算法在新环境下的收敛.利用三个标准的动态多目标测试函数，比较了CPM-DMOEA与其他三种动态多目标优化算法，分析结果表明了本文算法的有效性，能更好地适应不同程度的环境变化，快速地跟踪新的Pareto最优解集.

未来将把CPM-DMOEA算法应用于更多的实际问题中，以进一步分析其在不同的动态环境中的表现，不断地改善算法的性能.

参考文献：

[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]尚荣华， 焦李成， 公茂果， 等. 免疫克隆算法求解动态多目标优化问题[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]刘淳安，王宇平.基于新模型的动态多目标优化进化算法[J].计算机研究与发展， 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]武燕，刘小雄，池程芝.动态多目标优化的预测遗传算法[J].控制与决策， 2013，28（5）：677-682.

[10]彭星光， 徐德民， 高晓光. 基于Pareto 解集关联与预测的动态多目标进化算法[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]刘敏，曾文华. 记忆增强的动态多目标分解进化算法[J].软件学报， 2013，24（7）：1571-1588.

（编辑陈笑梅）

摘要为了在动态环境中快速地跟踪变化后的最优解集，提出一种基于聚类预测模型的动态多目标优化算法.通过对种群聚类，提高预测解集的分布性与广泛性，为分段预测做准备，然后利用历史信息对每个子类的中心点和形状进行预测，在环境变化后，预测产生的每个子类共同构成整个新的初始种群，有引导性地增加了种群的多样性，使算法能快速跟踪新的最优解集.在标准动态测试问题上进行算法测试，实验结果表明所提算法能快速地适应环境的动态变化，所获解集具有较好的收敛性和分布性.

关键词动态多目标，聚类，预测，进化算法

中图分类号O224文献标识码A文章编号1000-2537（2014）02-0056-06

现实世界中的许多优化问题都是动态多目标优化问题（dynamic multi-objective optimization problems，简称DMOPs），多个目标之间经常冲突，同时目标函数、约束函数和相关参数都可能随着时间的变化而改变，如何跟踪变化后新的最优解集是求解动态多目标优化问题的主要难点[1].在处理DMOPs上，静态的方法具有明显的局限性.传统的进化算法目标是使种群逐渐收敛，最终得到Pareto最优解集[2-3].而种群一旦收敛，种群的多样性减少，很难适应新的环境变化.因此，只有对静态算法加以改进，才能更好地适应于动态环境[4].

近些年来，研究者们在静态算法的基础上设计了许多新的方法来求解DMOPs[5-8]，这些方法大多集中在保持种群多样性上，通过随机移民，动态迁移，超变异和多种群等策略增加种群多样性，使新的种群具有响应环境变化的能力.然而这些方法是一种随机的、不确定的多样性保持策略，不能为适应新的环境提供正确的引导，因此具有盲目性，收敛速度是存在的主要问题.

如何充分利用历史信息，通过预测为当前环境下的种群进化提供正确的引导已成为求解DMOPs的又一新的发展趋势.目前，这类方法已受到了研究者的广泛关注.2006年，Hatzakis等人提出了一种前馈法[9]，该方法记录目标空间相邻历史Pareto前沿面上的边界点信息，通过自回归模型预测新的最优解集的位置，但是该方法仅记录历史解集上边界点的信息并加以预测，采用的预测模型提供的信息有限，未能充分考虑环境变化之间可能存在的关联性，因而影响了预测效果.2011年，彭星光等人提出了一种基于Pareto解集关联与预测的动态多目标进化算法[10]，然而该方法仅根据相邻时间序列上的解集关联性进行预测，并且仅预测超块中的代表性个体，不能预测新的最优解集的形状，当环境发生较大程度的变化时，预测的解集将出现偏差.因此，怎样设计一个更为精确的预测模型仍是现在的研究重点.

基于以上分析，为了避免盲目地增加种群多样性，并充分利用历史信息，提高预测模型的准确性，使其能适应于不同程度的环境变化，本文提出一种基于聚类预测模型的动态多目标进化算法（A dynamic multi-objective evolutionary algorithm based on cluster prediction model，简称CPM-DMOEA），通过对种群聚类建立预测模型，将对每个子类的预测分为对中心点的预测和对形状的预测，从而产生新的预测种群.在动态多目标优化算法的整体框架下进行迭代，通过标准动态测试问题进行仿真比较，实验结果充分验证了所提算法的有效性.

1优化问题及相关概念

4结论

本文提出了一种基于聚类预测模型的动态多目标优化算法，算法通过建立聚类预测模型，对种群进行分段预测，提高了预测解集的分布性和广泛性.根据历史信息预测每个子类的中心点和形状，从而在环境变化后产生整个新的初始种群.预测产生的新种群能有效地对新环境下的PS潜在区域进行探索，加速了算法在新环境下的收敛.利用三个标准的动态多目标测试函数，比较了CPM-DMOEA与其他三种动态多目标优化算法，分析结果表明了本文算法的有效性，能更好地适应不同程度的环境变化，快速地跟踪新的Pareto最优解集.

未来将把CPM-DMOEA算法应用于更多的实际问题中，以进一步分析其在不同的动态环境中的表现，不断地改善算法的性能.

参考文献：

[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]尚荣华， 焦李成， 公茂果， 等. 免疫克隆算法求解动态多目标优化问题[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]刘淳安，王宇平.基于新模型的动态多目标优化进化算法[J].计算机研究与发展， 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]武燕，刘小雄，池程芝.动态多目标优化的预测遗传算法[J].控制与决策， 2013，28（5）：677-682.

[10]彭星光， 徐德民， 高晓光. 基于Pareto 解集关联与预测的动态多目标进化算法[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]刘敏，曾文华. 记忆增强的动态多目标分解进化算法[J].软件学报， 2013，24（7）：1571-1588.

（编辑陈笑梅）

摘要为了在动态环境中快速地跟踪变化后的最优解集，提出一种基于聚类预测模型的动态多目标优化算法.通过对种群聚类，提高预测解集的分布性与广泛性，为分段预测做准备，然后利用历史信息对每个子类的中心点和形状进行预测，在环境变化后，预测产生的每个子类共同构成整个新的初始种群，有引导性地增加了种群的多样性，使算法能快速跟踪新的最优解集.在标准动态测试问题上进行算法测试，实验结果表明所提算法能快速地适应环境的动态变化，所获解集具有较好的收敛性和分布性.

关键词动态多目标，聚类，预测，进化算法

中图分类号O224文献标识码A文章编号1000-2537（2014）02-0056-06

现实世界中的许多优化问题都是动态多目标优化问题（dynamic multi-objective optimization problems，简称DMOPs），多个目标之间经常冲突，同时目标函数、约束函数和相关参数都可能随着时间的变化而改变，如何跟踪变化后新的最优解集是求解动态多目标优化问题的主要难点[1].在处理DMOPs上，静态的方法具有明显的局限性.传统的进化算法目标是使种群逐渐收敛，最终得到Pareto最优解集[2-3].而种群一旦收敛，种群的多样性减少，很难适应新的环境变化.因此，只有对静态算法加以改进，才能更好地适应于动态环境[4].

近些年来，研究者们在静态算法的基础上设计了许多新的方法来求解DMOPs[5-8]，这些方法大多集中在保持种群多样性上，通过随机移民，动态迁移，超变异和多种群等策略增加种群多样性，使新的种群具有响应环境变化的能力.然而这些方法是一种随机的、不确定的多样性保持策略，不能为适应新的环境提供正确的引导，因此具有盲目性，收敛速度是存在的主要问题.

如何充分利用历史信息，通过预测为当前环境下的种群进化提供正确的引导已成为求解DMOPs的又一新的发展趋势.目前，这类方法已受到了研究者的广泛关注.2006年，Hatzakis等人提出了一种前馈法[9]，该方法记录目标空间相邻历史Pareto前沿面上的边界点信息，通过自回归模型预测新的最优解集的位置，但是该方法仅记录历史解集上边界点的信息并加以预测，采用的预测模型提供的信息有限，未能充分考虑环境变化之间可能存在的关联性，因而影响了预测效果.2011年，彭星光等人提出了一种基于Pareto解集关联与预测的动态多目标进化算法[10]，然而该方法仅根据相邻时间序列上的解集关联性进行预测，并且仅预测超块中的代表性个体，不能预测新的最优解集的形状，当环境发生较大程度的变化时，预测的解集将出现偏差.因此，怎样设计一个更为精确的预测模型仍是现在的研究重点.

基于以上分析，为了避免盲目地增加种群多样性，并充分利用历史信息，提高预测模型的准确性，使其能适应于不同程度的环境变化，本文提出一种基于聚类预测模型的动态多目标进化算法（A dynamic multi-objective evolutionary algorithm based on cluster prediction model，简称CPM-DMOEA），通过对种群聚类建立预测模型，将对每个子类的预测分为对中心点的预测和对形状的预测，从而产生新的预测种群.在动态多目标优化算法的整体框架下进行迭代，通过标准动态测试问题进行仿真比较，实验结果充分验证了所提算法的有效性.

1优化问题及相关概念

4结论

本文提出了一种基于聚类预测模型的动态多目标优化算法，算法通过建立聚类预测模型，对种群进行分段预测，提高了预测解集的分布性和广泛性.根据历史信息预测每个子类的中心点和形状，从而在环境变化后产生整个新的初始种群.预测产生的新种群能有效地对新环境下的PS潜在区域进行探索，加速了算法在新环境下的收敛.利用三个标准的动态多目标测试函数，比较了CPM-DMOEA与其他三种动态多目标优化算法，分析结果表明了本文算法的有效性，能更好地适应不同程度的环境变化，快速地跟踪新的Pareto最优解集.

未来将把CPM-DMOEA算法应用于更多的实际问题中，以进一步分析其在不同的动态环境中的表现，不断地改善算法的性能.

参考文献：

[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]尚荣华， 焦李成， 公茂果， 等. 免疫克隆算法求解动态多目标优化问题[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]刘淳安，王宇平.基于新模型的动态多目标优化进化算法[J].计算机研究与发展， 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]武燕，刘小雄，池程芝.动态多目标优化的预测遗传算法[J].控制与决策， 2013，28（5）：677-682.

[10]彭星光， 徐德民， 高晓光. 基于Pareto 解集关联与预测的动态多目标进化算法[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]刘敏，曾文华. 记忆增强的动态多目标分解进化算法[J].软件学报， 2013，24（7）：1571-1588.

（编辑陈笑梅）