1.算法描述
粒子群优化算法(PSO),粒子群中的每一个粒子都代表一个问题的可能解, 通过粒子个体的简单行为,群体内的信息交互实现问题求解的智能性。
在求解TSP这种整数规划问题的时候, PSO显然与ACO不同, PSO需要对算法本身进行一定的修改, 毕竟PSO刚开始是应用在求解连续优化问题上的.
在路径规划中,我们将每一条路径规划为一个粒子,每个粒子群群有 n 个粒 子,即有 n 条路径,同时,每个粒子又有 m 个染色体,即中间过渡点的个数,每 个点(染色体)又有两个维度(x,y),在代码中用 posx 和 posy 表示一个种群。 通过每一代的演化,对粒子群进行演化操作,选择合适个体(最优路径)。
最终算法伪代码如下:
初始化: 每个粒子获得一个随机解和一个随机的SS (命名为速度)
For 在位置 X_{id} 的所有粒子, 计算新的位置 X_{id}':
计算 P_{id} 与 X_{id} 之间的差 A = P_{id} - X_{id}, 其中 A 为 BSS
计算 B = P_{gd} - X_{id}, 其中 B 为 BSS
根据速度更新公式计算新的速度 V_{id}', 并将 V_{id}' 转换为一个 BSS
计算新的解 X_{id}' = X_{id} + V_{id} (也就是 V_{id} 作用在 X_{id} 上)
更新 P_{id} 如果新的解更好
更新 P_{gd} 若出现新的全局最好的解
2.仿真效果预览
matlab2022a仿真结果如下:
3.MATLAB核心程序
MaxIt=200; % Maximum Number of Iterations nPop=150; % Population Size (Swarm Size) w=1; % Inertia Weight wdamp=0.98; % Inertia Weight Damping Ratio c1=1.5; % Personal Learning Coefficient c2=1.5; % Global Learning Coefficient alpha=0.1; VelMax.x=alpha*(VarMax.x-VarMin.x); % Maximum Velocity VelMin.x=-VelMax.x; % Minimum Velocity VelMax.y=alpha*(VarMax.y-VarMin.y); % Maximum Velocity VelMin.y=-VelMax.y; % Minimum Velocity %% Initialization % Create Empty Particle Structure empty_particle.Position=[]; empty_particle.Velocity=[]; empty_particle.Cost=[]; empty_particle.Sol=[]; empty_particle.Best.Position=[]; empty_particle.Best.Cost=[]; empty_particle.Best.Sol=[]; % Initialize Global Best GlobalBest.Cost=inf; % Create Particles Matrix particle=repmat(empty_particle,nPop,1); % Initialization Loop for i=1:nPop % Initialize Position if i > 1 particle(i).Position=CreateRandomSolution(model); else % Straight line from source to destination xx = linspace(model.xs, model.xt, model.n+2); yy = linspace(model.ys, model.yt, model.n+2); particle(i).Position.x = xx(2:end-1); particle(i).Position.y = yy(2:end-1); end