一种求解混合离散优化问题的禁忌微粒群算法  

A Hybrid Tabu Search and Particle Swarm Optimization Algorithm for Mixed Discrete Optimization Problems

作　　者：张星会[1] 白富生[1] 

机构地区：[1]重庆师范大学数学学院,重庆400047

出　　处：《重庆师范大学学报（自然科学版）》2011年第2期5-10,共6页Journal of Chongqing Normal University:Natural Science

基　　金：国家自然科学基金(No.10626058)

摘　　要：微粒群优化(PSO)算法主要用于求解全局连续变量优化问题。利用罚函数处理离散变量,将混合离散优化问题min f(x)s,.t.gk(x)≤0k,=12,,…l,x,iL≤xi≤xiU i,=12,,…,m,xm+j∈Dj,Dj=(dj,1,dj,2,…,djq,j)j,=12,,…,n转化为连续变量优化问题min F(x),s.t.xiL≤xi≤xiU i,=1,2,…,m,dj1,≤xm+j≤dj,qjj,=1,2…,n。为了解决标准PSO可能陷入局部最优解而存在早熟收敛的问题,本文构造微粒的邻域结构,利用禁忌搜索(TS)算法具有较强的"爬山"能力的特点,设计了一种兼具搜索惯性又能在搜索时跳出局部最优解转向解空间的其它区域的禁忌微粒群算法(TS-PSO)。求解Rosenbrock’s测试函数和压力管设计问题的数值实验表明,该算法能较好地跳出局部最优,获得全局最优解。Particle swarm optimization（PSO） algorithm is mainly used to find global solutions of continuous variables optimization problems.In this paper,the penalty function approach to handle the discrete variables is employed,in which mixed discrete optimization problem： min f（x）,s.t.gk（x）≤0,k=1,2,…l,xLi≤xi≤xUi,i=1,2,…,m,xm＋j∈Dj,Dj=（dj,1,dj,2,…,dj,qj）,j=1,2,…,n is handled as continuous one： min F（x）,s.t.xLi≤xi≤xUi,i=1,2,…,m,dj,1≤xm＋j≤dj,qj,j=1,2…,n.Standard PSO algorithm will likely fall into local optimal solution and exist premature convergence.Tabu search（TS） algorithm has good hill-climbing ability and can escape from the local optimal solution and turn to other parts of the solution space.A neighborhood structure is designed and a hybrid tabu search and particle swarm optimization（TS-PSO） algorithm is proposed,which has memory ability and efficient hill-climbing capability.Simulation results on Rosenbrocks function and pressure vessel design show that the disadvantage of getting in the local best point of standard PSO is overcome effectively and the ability of global optimality is toned up.

关 键 词：离散变量 罚函数 微粒群优化 禁忌搜索 

分 类 号：O221.4[理学—运筹学与控制论]