A New Discrete Particle Swarm Optimization Algorithm

题目：一种新的离散粒子群优化算法

中文摘要

      粒子群优化算法在许多优化问题上表现得非常好。粒子群优化算法的缺点之一是假设算法中的变量为连续变量。本文提出一个新的粒子群优化算法，能够优化离散变量。这个新算法被称为整数和分类粒子群优化算法，该算法融合了分布估计算法的思想，即粒子代表概率分布而不是解的值，并且PSO更新修改了概率分布。本文描述了该算法，并将其性能与其他离散PSO算法进行了比较。实验表明，该算法比其他离散PSO算法要好 。

中文引言

      离散优化问题，如贝叶斯网络中的特征选择或推理，是一组重要且具有挑战性的问题。这些问题不同于连续问题，因为每个变量的状态是有限个。在整数问题的例子中，变量被限制为一组整数值。对于此类问题，相邻值之间存在一种关系。一般而言，整数中存在一种隐式排序：差异较大的整数被认为是相距较远的整数。
      虽然整数问题是离散问题的子集，但也有其他类型的问题。例如，在贝叶斯推理中，目标是找到一个能很好解释一组观察结果的状态集。在这里，相邻状态之间可能不存在直接关系或梯度。例如，假设状态集是悲伤、恐惧、愤怒、喜悦和厌恶的情绪。虽然在优化过程中这些状态可以用整数表示，但这种编码的值之间没有真正的有序关系。我们把这类问题称为分类优化问题。
      注意：这里的顺序关系就是数学中的大小关系。
      粒子群优化是一种相对简单的搜索算法，适用于各种各样的优化问题。然而，原始PSO算法无法处理离散问题，如上述问题，因为其速度更新需要连续的解值。目前，虽然离散的定义在应用程序和算法之间有很大差异, 但是PSO算法的几个变体允许离散值。本文正式给出离散问题的定义，并针对这问题提出了一种新的粒子群优化算法，称为整数和分类粒子群优化算法（ICPSO）。然后将ICPSO与文献中提出的其他离散PSO变体进行比较。
      ICPSO算法的目标是保持对连续PSO的扩展尽可能简单，并保留大部分原始语义，同时解决其他离散PSO算法的一些潜在缺陷。为了实现这一点，我们改变粒子位置的表示形式，以便粒子的每个属性都是其可能值的分布，而不是值本身。这类似于分布估计算法(EDA)，其中使用一组拟合个体生成分布向量，然后生成拟合解。ICPSO与EDAs的不同之处在于，该算法具有多个分布向量，这些分布向量使用PSO更新公式进行更新。
      对于ICPSO，评价粒子变为从这些分布中抽取候选解并计算其适应度的任务。ICPSO还允许使用原始PSO更新公式，避免了可能解值的隐式排序相关的问题。另外，每当产生一个全局最优样本时，ICPSO会修改全局最优解和局部最优解的分布。这使得分布偏向于产生的最优样本，同时仍然允许搜索空间的探索。

离散PSO算法

function results = ICPSO(problem, param, initMat, attr)
    % =====================================================================
    % 名称：整数和分类PSO
    % 时间：2022-01-06
    % 姓名：LeeWenTsao
    % =====================================================================
    %% 问题定义
    CostFunction = @ Metric;  % 成本函数

    clusterNumber = problem.clusterNumber;  % 簇数目
    sampleNumber = problem.sampleNumber;  % 样本数目

    PositionSize = [clusterNumber sampleNumber];  % 位置矩阵大小

    varMin = problem.PositionRange(1);  % 变量的下界
    varMax = problem.PositionRange(2);  % 变量的上界

    %% ICPSO参数设置
    MaxIter = param.MaxIter;  % 最大迭代次数 
    nPop = param.nPop;  % 种群数目
    popNumber = param.popNumber;  % 单个粒子含有的基聚类
    showIters = param.showIters;  % 显示迭代次数

    w = 0.729;  % 惯性系数
    alpha = 1.49618;  % 个体学习系数
    beta = 1.49618;   % 群体学习系数

    GlobalBest.Cost = inf;

    %% 初始化
    Pr = zeros(PositionSize);
    for i=1:nPop
        t = initMat((i-1)*popNumber+1:i*popNumber, :);
        for j=1:sampleNumber
            tal = tabulate(t(:,j));  % 概率统计
            if size(tal,1)1
                temp = particle(i).Position;
                add = sum(temp);
                [~, id] = find(add>1);
                temp(:,id) = temp(:,id)./add(id);
                particle(i).Position = temp;
            end

            % 采样
            [~, id] = max(particle(i).Position);
            particle(i).Sequence = id;

            % 评价
            particle(i).Cost = CostFunction(particle(i).Sequence, attr); 

            % 更新个体最好
            if particle(i).Cost群智能优化算法进化算法编程语言学习

相关

标签