PDF《一种基于多代理模型的混合整数规划优化方法》

第34卷第2期 控制与决策Vol.

34 No.2 2019年 2月 Control and Decision Feb.

2019 文章编号: 1001-0920(2019)02-0362-07 DOI: 10.13195/j.kzyjc.2017.1099 一种基于多代理模型的混合整数规划优化方法 吕志明, 王霖青, 赵B? , 王伟(大连理工大学 控制科学与工程学院,辽宁 大连 116024) 摘要: 提出一种基于多代理模型的优化方法,求解混合整数规划问题. 首先,基于群智能优化策略提出一种基于 多群体协作模型的采样方法,保证候选解的正确性和多样性;

其次,采用基于数据并行的高斯过程建模方法,在线 构造局部代理模型;

再次,通过多代理模型对候选解进行预筛选,实现与粒子群算法的协同优化;

最后,通过14个测 试问题和一个基于数据驱动的模型参数选取问题,验证所提出方法的有效性. 关键词: 混合整数;

多代理;

粒子群;

高斯过程 中图分类号: TP206 文献标志码: A A multi-surrogates algorithm for mixed-integer programming problems LYU Zhi-ming, WANG Lin-qing, ZHAO Jun? , WANG Wei (School of Control Science and Engineering,Dalian University of Technology,Dalian 116024,China) Abstract: A multi-surrogates algorithm is developed to deal with the mixed-integer programming problems. Firstly, a sampling method based on the model of the multi-swarm PSO is developed to ensure the accuracy and diversity of the the samples. Furthermore, the local surrogate models are constructed by an online modeling method based on the data parallel approach. Then, the collaborative optimization is carried out based on the preselecting strategy and PSO. Finally, the e?ectiveness of the proposed method are veri?ed by the

14 test problems and

1 data driven model parameter selection problems. Keywords: mixed-integer;

multi-surrogates;

PSO;

Gaussion process

0 引言当前,在最优决策、 工程设计、 组合优化和能源 调度等工程领域,存在着大量的混合整数规划(Mixed -integer programming, MIP) 问题. 这些问题通常是 NP-完全问题,计算复杂度高. 此外,在实际应用中,目 标问题通常只有实时的输入和输出,没有确定性的数 学描述,而且给定输入后,得到输出响应的时间很长, 该类问题称为黑箱问题. 近些年,基于代理模型的全 局优化算法在MIP黑箱问题中得到了广泛的关注,并 应用于实际的工程优化问题中[1-3] . 基于代理模型的全局优化算法主要是通过自适 应采样,使效益函数最大化. 文献[1]通过优化两个辅 助函数进行采样. 但是,辅助优化过程本身就是一个 求解混合整数规划问题的过程,因此,优化器设计的 合理性影响着所提算法的有效性. 为了避免上述问 题,文献[2]提出了基于全局和局部网格搜索的协同 采样策略;

文献 [3] 提出了一种随机采样策略. 但是, 上述两种贪婪的采样策略会产生大量的采样点,进而 增加代理模型的训练和预测成本. 为了缓解代理模 型构造成本高的问题,多代理模型技术已成为当前的 研究热点[4] . 文献[5]采用基于数据并行的高斯过程 建模方法构造多个局部代理模型;

文献[6]根据分而 治之的思想提出了混合专家方法. 但是文献[5]和文 献[6]针对连续优化问题,只考虑了离线建模方法. 针对MIP黑箱问题,本文提出一种基于多代理模 型的优化算法. 该方法基于多群体协作,采用多种进 化策略进行联合采样. 此外,构造一种基于数据并行 方法的高斯过程回归模型在线建模方法. 该方法在 构造多个局部代理模型的同时自适应地调节局部代 理模型的个数. 在序贯优化的过程中,粒子群算法与 收稿日期: 2017-08-21;