【算法】粒子群优化

2024-08-24 09:28
文章标签 算法 优化 粒子

本文主要是介绍【算法】粒子群优化，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、引言

        粒子群优化算法（Particle Swarm Optimization, PSO）是一种基于群体智能的优化技术，由Eberhart和Kennedy在1995年提出。它模拟鸟群觅食行为，通过个体与群体的协作来寻找最优解。通过模拟一群粒子的运动来寻找最优解。每个粒子代表一个可能的解，并且根据自身经验和群体经验来更新位置。

二、算法原理

        PSO算法中，每个解被视为搜索空间中的一个“粒子”，每个粒子代表了问题的潜在解，并具有相应的位置和速度。粒子在搜索空间中飞行，通过跟踪两个“极值”来更新自己的位置和速度：

  • 个体极值：粒子自身所找到的最优解。
  • 全局极值：整个粒子群中所有粒子所找到的最优解。

        粒子的位置和速度根据个体极值和全局极值进行更新。

三、数据结构

PSO算法涉及的主要数据结构包括：

  • 粒子（Particle）：

    • position: 当前粒子的位置
    • velocity: 当前粒子的速度
    • best_position: 粒子的历史最佳位置
    • best_value: 粒子的最佳适应度值

  • 群体（Swarm）：

    • particles: 存储所有粒子的列表
    • global_best_position: 全局最佳位置
    • global_best_value: 全局最佳适应度值
  • 目标函数：粒子优化的目标函数，用于评估解的质量。

四、算法使用场景

PSO算法适用于：

  • 函数优化：连续空间的全局优化问题、寻找函数的最小值或最大值
  • 神经网络训练：作为权重调整的优化算法。

  • 模式识别：特征选择和参数优化。
  • 机器学习参数优化：在训练机器学习模型时，PSO可以用于优化模型参数。
  • 组合优化问题：如旅行商问题（TSP）、排程问题等。
  • 工程设计问题：如结构优化、电路设计等。
  • 路径规划：在机器人和无人机的路径规划中寻找最优路径。
  • 图像处理：图像分割和特征选择等。

五、算法实现

伪代码如下：

function PSO(numParticles, numIterations):
Initialize particles and global best
For each iteration:
For each particle:
Update velocity
Update position
Evaluate the fitness function
Update personal and global bests

六、其他同类算法对比

  • 遗传算法（Genetic Algorithm, GA）：基于自然选择和遗传机制的搜索算法。
  • 模拟退火（Simulated Annealing, SA）：基于物理退火过程的优化方法。
  • 蚁群算法（Ant Colony Optimization, ACO）：模拟蚂蚁觅食行为的启发式搜索算法。

七、多语言代码实现

    Java

import java.util.Random;class Particle {double[] position;double[] velocity;double[] bestPosition;double bestValue;public Particle(int dimensions, double lowerBound, double upperBound) {position = new double[dimensions];velocity = new double[dimensions];bestPosition = new double[dimensions];Random rand = new Random();for (int i = 0; i < dimensions; i++) {position[i] = lowerBound + (upperBound - lowerBound) * rand.nextDouble();velocity[i] = (rand.nextDouble() - 0.5) * 2; // Random velocity}bestPosition = position.clone();bestValue = Double.POSITIVE_INFINITY;}
}class PSO {private Particle[] particles;private double[] globalBestPosition;private double globalBestValue;private int dimensions;private double lowerBound;private double upperBound;private int maxIter;public PSO(int numParticles, int dimensions, double lowerBound, double upperBound, int maxIter) {this.dimensions = dimensions;this.lowerBound = lowerBound;this.upperBound = upperBound;this.maxIter = maxIter;particles = new Particle[numParticles];globalBestPosition = new double[dimensions];globalBestValue = Double.POSITIVE_INFINITY;for (int i = 0; i < numParticles; i++) {particles[i] = new Particle(dimensions, lowerBound, upperBound);}}public void optimize() {Random rand = new Random();for (int iter = 0; iter < maxIter; iter++) {for (Particle particle : particles) {double value = objectiveFunction(particle.position);if (value < particle.bestValue) {particle.bestValue = value;particle.bestPosition = particle.position.clone();}if (value < globalBestValue) {globalBestValue = value;globalBestPosition = particle.position.clone();}}for (Particle particle : particles) {double inertia = 0.5;double cognitive = 1.5 * rand.nextDouble() * (particle.bestPosition[0] - particle.position[0]);double social = 1.5 * rand.nextDouble() * (globalBestPosition[0] - particle.position[0]);for (int i = 0; i < dimensions; i++) {particle.velocity[i] = inertia * particle.velocity[i] + cognitive + social;particle.position[i] += particle.velocity[i];// Bound checkif (particle.position[i] < lowerBound) particle.position[i] = lowerBound;if (particle.position[i] > upperBound) particle.position[i] = upperBound;}}}}private double objectiveFunction(double[] position) {double sum = 0;for (double v : position) {sum += v * v; // Example: sum of squares}return sum;}public double[] getGlobalBestPosition() {return globalBestPosition;}public double getGlobalBestValue() {return globalBestValue;}public static void main(String[] args) {PSO pso = new PSO(30, 2, -10, 10, 100);pso.optimize();System.out.println("Best Position: " + Arrays.toString(pso.getGlobalBestPosition()));System.out.println("Best Value: " + pso.getGlobalBestValue());}
}

C++

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <limits>
#include <cmath>class Particle {
public:std::vector<double> position;std::vector<double> velocity;std::vector<double> bestPosition;double bestValue;Particle(int dimensions, double lowerBound, double upperBound) {position.resize(dimensions);velocity.resize(dimensions);bestPosition.resize(dimensions);for (int i = 0; i < dimensions; ++i) {position[i] = lowerBound + static_cast<double>(rand()) / RAND_MAX * (upperBound - lowerBound);velocity[i] = (static_cast<double>(rand()) / RAND_MAX - 0.5) * 2; // Random velocity}bestPosition = position;bestValue = std::numeric_limits<double>::infinity();}
};class PSO {
private:std::vector<Particle> particles;std::vector<double> globalBestPosition;double globalBestValue;int dimensions;double lowerBound;double upperBound;int maxIter;public:PSO(int numParticles, int dimensions, double lowerBound, double upperBound, int maxIter): dimensions(dimensions), lowerBound(lowerBound), upperBound(upperBound), maxIter(maxIter) {particles.reserve(numParticles);globalBestValue = std::numeric_limits<double>::infinity();for (int i = 0; i < numParticles; ++i) {particles.emplace_back(dimensions, lowerBound, upperBound);}}void optimize() {for (int iter = 0; iter < maxIter; ++iter) {for (auto& particle : particles) {double value = objectiveFunction(particle.position);if (value < particle.bestValue) {particle.bestValue = value;particle.bestPosition = particle.position;}if (value < globalBestValue) {globalBestValue = value;globalBestPosition = particle.position;}}for (auto& particle : particles) {double inertia = 0.5;double cognitive = 1.5 * static_cast<double>(rand()) / RAND_MAX * (particle.bestPosition[0] - particle.position[0]);double social = 1.5 * static_cast<double>(rand()) / RAND_MAX * (globalBestPosition[0] - particle.position[0]);for (int i = 0; i < dimensions; ++i) {particle.velocity[i] = inertia * particle.velocity[i] + cognitive + social;particle.position[i] += particle.velocity[i];// Bound checkif (particle.position[i] < lowerBound) particle.position[i] = lowerBound;if (particle.position[i] > upperBound) particle.position[i] = upperBound;}}}}double objectiveFunction(const std::vector<double>& position) {double sum = 0;for (double v : position) {sum += v * v; // Example: sum of squares}return sum;}const std::vector<double>& getGlobalBestPosition() const {return globalBestPosition;}double getGlobalBestValue() const {return globalBestValue;}
};int main() {srand(static_cast<unsigned>(time(0)));PSO pso(30, 2, -10, 10, 100);pso.optimize();const auto& bestPosition = pso.getGlobalBestPosition();std::cout << "Best Position: ";for (const auto& pos : bestPosition) {std::cout << pos << " ";}std::cout << "\nBest Value: " << pso.getGlobalBestValue() << std::endl;return 0;
}

Python

import numpy as npclass Particle:def __init__(self, bounds):self.position = np.random.uniform(bounds[0], bounds[1], size=(len(bounds)//2,))self.velocity = np.random.uniform(-1, 1, size=(len(bounds)//2,))self.best_position = self.position.copy()self.best_value = float('inf')class PSO:def __init__(self, func, bounds, num_particles, max_iter):self.func = funcself.bounds = boundsself.num_particles = num_particlesself.max_iter = max_iterself.particles = [Particle(bounds) for _ in range(num_particles)]self.global_best_position = Noneself.global_best_value = float('inf')def optimize(self):for _ in range(self.max_iter):for particle in self.particles:value = self.func(particle.position)if value < particle.best_value:particle.best_value = valueparticle.best_position = particle.position.copy()if value < self.global_best_value:self.global_best_value = valueself.global_best_position = particle.position.copy()for particle in self.particles:r1, r2 = np.random.rand(2)inertia = 0.5cognitive = 1.5 * r1 * (particle.best_position - particle.position)social = 1.5 * r2 * (self.global_best_position - particle.position)particle.velocity = inertia * particle.velocity + cognitive + socialparticle.position += particle.velocity# Bound checkparticle.position = np.clip(particle.position, self.bounds[0], self.bounds[1])return self.global_best_position, self.global_best_value# Example usage
def objective_function(x):return sum(x**2)bounds = [-10, 10]
pso = PSO(objective_function, bounds, num_particles=30, max_iter=100)
best_position, best_value = pso.optimize()
print(f"Best Position: {best_position}, Best Value: {best_value}")

 Go

package mainimport ("fmt""math/rand""time"
)type Particle struct {position     []float64velocity     []float64bestPosition []float64bestValue    float64
}type PSO struct {particles          []ParticleglobalBestPosition []float64globalBestValue    float64dimensions         intlowerBound         float64upperBound         float64maxIter            int
}func NewParticle(dimensions, lowerBound, upperBound float64) Particle {position := make([]float64, dimensions)velocity := make([]float64, dimensions)bestPosition := make([]float64, dimensions)for i := 0; i < int(dimensions); i++ {position[i] = lowerBound + rand.Float64()*(upperBound-lowerBound)velocity[i] = (rand.Float64() - 0.5) * 2 // Random velocity}copy(bestPosition, position)return Particle{position, velocity, bestPosition, 1e10}
}func NewPSO(numParticles, dimensions int, lowerBound, upperBound float64, maxIter int) *PSO {particles := make([]Particle, numParticles)for i := 0; i < numParticles; i++ {particles[i] = NewParticle(float64(dimensions), lowerBound, upperBound)}return &PSO{particles, nil, 1e10, dimensions, lowerBound, upperBound, maxIter}
}func (pso *PSO) objectiveFunction(position []float64) float64 {sum := 0.0for _, v := range position {sum += v * v // Example: sum of squares}return sum
}func (pso *PSO) Optimize() {for iter := 0; iter < pso.maxIter; iter++ {for i := range pso.particles {particle := &pso.particles[i]value := pso.objectiveFunction(particle.position)if value < particle.bestValue {particle.bestValue = valueparticle.bestPosition = make([]float64, len(particle.position))copy(particle.bestPosition, particle.position)}if value < pso.globalBestValue {pso.globalBestValue = valuepso.globalBestPosition = make([]float64, len(particle.position))copy(pso.globalBestPosition, particle.position)}}for i := range pso.particles {particle := &pso.particles[i]inertia := 0.5cognitive := 1.5 * rand.Float64() * (particle.bestPosition[0] - particle.position[0])social := 1.5 * rand.Float64() * (pso.globalBestPosition[0] - particle.position[0])for j := 0; j < pso.dimensions; j++ {particle.velocity[j] = inertia*particle.velocity[j] + cognitive + socialparticle.position[j] += particle.velocity[j]// Bound checkif particle.position[j] < pso.lowerBound {particle.position[j] = pso.lowerBound}if particle.position[j] > pso.upperBound {particle.position[j] = pso.upperBound}}}}
}func main() {rand.Seed(time.Now().UnixNano())pso := NewPSO(30, 2, -10, 10, 100)pso.Optimize()fmt.Printf("Best Position: %v\n", pso.globalBestPosition)fmt.Printf("Best Value: %v\n", pso.globalBestValue)
}

八、实际服务应用场景与代码框架

        实现一个供应链优化系统，使用粒子群优化算法来确定最优的货物分配策略。

系统架构

        问题定义：定义货物分配的优化目标和约束条件。

        粒子初始化：初始化粒子群，每个粒子代表一种可能的货物分配方案。

        评估与更新：评估每个粒子的适应度，并根据PSO算法更新粒子的位置和速度。

        最优解获取：经过多次迭代后，获取最优的货物分配方案。

代码框架

以下是使用Python实现的供应链优化系统的代码框架：

class SupplyChainOptimizer:def __init__(self, num_particles, dimensions, lower_bound, upper_bound):self.pso = PSO(num_particles, dimensions, lower_bound, upper_bound)def evaluate_fitness(self, particle):# 评估货物分配方案的适应度passdef optimize(self, iterations):for _ in range(iterations):self.pso.update_velocity_position()self.pso.evaluate()def get_best_solution(self):# 获取最优解pass# 使用示例
optimizer = SupplyChainOptimizer(num_particles=30, dimensions=5, lower_bound=-10, upper_bound=10)
optimizer.optimize(100)
best_solution = optimizer.get_best_solution()
print(f"Best solution: {best_solution}")

   数据准备

import numpy as np
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.svm import SVC
from sklearn.metrics import accuracy_score# Load dataset
data = load_iris()
X = data.data
y = data.target
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)

定义目标函数

def objective_function(params):C, gamma = paramsmodel = SVC(C=C, gamma=gamma)model.fit(X_train, y_train)predictions = model.predict(X_test)return -accuracy_score(y_test, predictions)  # Minimize negative accuracy

粒子群优化实现

class Particle:def __init__(self, bounds):self.position = np.random.uniform(bounds[0], bounds[1], size=(len(bounds)//2,))self.velocity = np.random.uniform(-1, 1, size=(len(bounds)//2,))self.best_position = self.position.copy()self.best_value = float('inf')class PSO:def __init__(self, func, bounds, num_particles, max_iter):self.func = funcself.bounds = boundsself.num_particles = num_particlesself.max_iter = max_iterself.particles = [Particle(bounds) for _ in range(num_particles)]self.global_best_position = Noneself.global_best_value = float('inf')def optimize(self):for _ in range(self.max_iter):for particle in self.particles:value = self.func(particle.position)if value < particle.best_value:particle.best_value = valueparticle.best_position = particle.position.copy()if value < self.global_best_value:self.global_best_value = valueself.global_best_position = particle.position.copy()for particle in self.particles:r1, r2 = np.random.rand(2)inertia = 0.5cognitive = 1.5 * r1 * (particle.best_position - particle.position)social = 1.5 * r2 * (self.global_best_position - particle.position)particle.velocity = inertia * particle.velocity + cognitive + socialparticle.position += particle.velocity# Bound checkparticle.position = np.clip(particle.position, self.bounds[0], self.bounds[1])return self.global_best_position, self.global_best_value

 执行优化

bounds = [[0.1, 100], [0.0001, 1]]  # C and gamma bounds
pso = PSO(objective_function, bounds, num_particles=30, max_iter=100)
best_params, best_value = pso.optimize()
print(f"Best Parameters: C={best_params[0]}, gamma={best_params[1]}, Best Value: {best_value}")

        过去与现在：PSO最初应用于函数优化问题，随着研究的深入，逐渐扩展到机器学习、数据挖掘、图像处理等多个领域。近年来，研究者对PSO进行了多种改进，如引入混沌理论、模糊逻辑等，以增强其全局搜索能力和收敛速度。

        优势：PSO具有简单易懂的结构和较少的参数设置，适用于多种优化问题。它能够有效地处理非线性、多峰值和高维问题，且收敛速度较快，适合实时优化。

        缺点：尽管PSO表现出色，但仍存在一些不足之处，如易陷入局部最优解、对参数设置敏感等。此外，在处理高维复杂问题时，可能会出现收敛速度减慢的问题。

        粒子群优化算法凭借其灵活性和有效性，已成为优化领域的重要工具，仍有广阔的发展空间。

这篇关于【算法】粒子群优化的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1102085。

相关文章

Vue3 的 shallowRef 和 shallowReactive：优化性能

Vue3 的 shallowRef 和 shallowReactive：优化性能

大家对 Vue3 的 ref 和 reactive 都很熟悉，那么对 shallowRef 和 shallowReactive 是否了解呢？ 在编程和数据结构中，“shallow”（浅层）通常指对数据结构的最外层进行操作，而不递归地处理其内部或嵌套的数据。这种处理方式关注的是数据结构的第一层属性或元素，而忽略更深层次的嵌套内容。 1. 浅层与深层的对比 1.1 浅层（Shallow） 定义
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
HDFS—存储优化（纠删码）

HDFS—存储优化（纠删码）

纠删码原理 HDFS 默认情况下，一个文件有3个副本，这样提高了数据的可靠性，但也带来了2倍的冗余开销。 Hadoop3.x 引入了纠删码，采用计算的方式，可以节省约50％左右的存储空间。 此种方式节约了空间，但是会增加 cpu 的计算。 纠删码策略是给具体一个路径设置。所有往此路径下存储的文件，都会执行此策略。 默认只开启对 RS-6-3-1024k
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
使用opencv优化图片（画面变清晰）

使用opencv优化图片（画面变清晰）

文章目录 需求影响照片清晰度的因素 实现降噪测试代码 锐化空间锐化Unsharp Masking频率域锐化对比测试 对比度增强常用算法对比测试 需求 对图像进行优化，使其看起来更清晰，同时保持尺寸不变，通常涉及到图像处理技术如锐化、降噪、对比度增强等 影响照片清晰度的因素 影响照片清晰度的因素有很多，主要可以从以下几个方面来分析 1. 拍摄设备 相机传感器：相机传
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...
MySQL高性能优化规范

MySQL高性能优化规范

前言：      笔者最近上班途中突然想丰富下自己的数据库优化技能。于是在查阅了多篇文章后，总结出了这篇！ 数据库命令规范 所有数据库对象名称必须使用小写字母并用下划线分割 所有数据库对象名称禁止使用mysql保留关键字（如果表名中包含关键字查询时，需要将其用单引号括起来） 数据库对象的命名要能做到见名识意，并且最后不要超过32个字符 临时库表必须以tmp_为前缀并以日期为后缀，备份
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2