首页 > 编程语言 >粒子群优化算法

粒子群优化算法

时间:2023-09-10 16:45:00浏览次数:48  
标签:粒子 wa double 算法 ij pf vec return 优化

写在前面

在大大的花园里面挖呀挖呀挖,挖大大的坑呀寻大大的WA。


官方解释

利用群体中的个体对信息的共享使整个群体的运动在问题求解空间中产生从无序到有序的演化过程。(这个解释不美丽.......)

诡异的故事法解释

那是一个暴风雨之夜,伴随着一声巨响,空气开始震动,狂风忽然吹向东方,比先前任何一场气流都猛烈,在没有蜡烛的黑夜之中,一切都变得影影绰绰,墨黑色的天空下有一团浓厚的黑色向外扩张,某种仿佛无定形烟云般的东西流星般向东方坠落,化作数百只小wa,在花园之中寻找遗失的宝藏......
小wa们为了提高效率,会时时汇报自己的进展,给整个wa群提供自己目前探测到的最有可能找到宝藏的方向,多方建议的汇合会为全体小wa指引方向,每一只小wa又有自己的想法,所以每只小wa都会既向全局已知最优方向行走又向个体认为的最优方向行走。

基本原理

假设在\(D\)维的目标搜索空间中,有\(N\)个粒子形成粒子群,
第\(i\)个粒子表示为一个\(D\)维向量 \(X_i=(x_{i_1},x_{i_2}. . . x_{i_D})\)
第\(i\)个粒子的飞行速度为一个\(D\)维向量 \(V_i=(v_{i_1},v_{i_2}. . . v_{i_D})\)
在第\(t\)代的第\(i\)个粒子向第\(t+1\)代进化时$$v_{ij}(t+1)=wv_{ij}(t)+[p_{ij}(t)-x_{ij}(t)]+[p_{gj}-x_{ij}]$$ $$x_{ij}(t+1)=x_{ij}(t)+v_{ij}(t+1)$$

应用

在一定定义域求一个函数最大或最小值

局限性

易收敛为局部最优,迭代后期收敛速度慢。

例题

洛谷P2571

点击查看代码
#include<bits/stdc++.h>
using namespace std;
double Rand() 
{
	return (double)rand() / RAND_MAX;
}
struct vec
{
	double x,y;
	vec operator + (vec a)
	{
		return {x+a.x,y+a.y};
	}
	vec operator - (vec a)
	{
		return {x-a.x,y-a.y};
	}
	vec operator * (double a)
	{
		return {x*a,y*a};
	}
		vec operator / (double a)
	{
		return {x/a,y/a};
	}
};
struct node
{
	vec v,s,ps;
	double f,pf,w;
};
node e[510];
vec a,b,c,d,ba,cd;
double p,q,r;
double allf=1e18;
vec alls;
double dis(vec x,vec y)
{
	return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
}
double f(double x,double y)
{
	return x+y+dis(a+ba*x,d+cd*y)/r;
}
double xx,yy;
void update(int a)
{
	e[a].v=e[a].v*e[a].w+alls+e[a].ps-e[a].s*2;
	e[a].s=e[a].s+e[a].v;
	if(e[a].s.x<0) e[a].s.x=0,e[a].v.x=-e[a].v.x;
	if(e[a].s.y<0) e[a].s.y=0,e[a].v.y=-e[a].v.y;
	if(e[a].s.x>xx) e[a].s.x=xx,e[a].v.x=-e[a].v.x;
	if(e[a].s.y>yy) e[a].s.y=yy,e[a].v.y=-e[a].v.y;
	e[a].f=f(e[a].s.x,e[a].s.y);
	if(e[a].f<e[a].pf) e[a].ps=e[a].s,e[a].pf=e[a].f;
}
int main()
{
	srand(time(0));
	scanf("%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y);
	scanf("%lf%lf%lf%lf",&c.x,&c.y,&d.x,&d.y);
	scanf("%lf%lf%lf",&p,&q,&r);
	xx=dis(b,a)/p;
	yy=dis(d,c)/q;
	ba=b-a;
	cd=c-d;
	if(!xx)
	{
		ba.x=ba.y=0;
	}
	else
	{
		ba=ba/xx;
	}
	if(!yy)
	{
		cd.x=cd.y=0;
	}
	else
	{
		cd=cd/yy;
	}
	for(int i=1;i<=500;i++)
	{
		e[i].w=Rand();
		e[i].s.x=e[i].ps.x=Rand()*xx;
		e[i].s.y=e[i].ps.y=Rand()*yy;
		e[i].f=e[i].pf=f(e[i].s.x,e[i].s.y);
		e[i].v.x=e[i].v.y=0;
		if(allf>e[i].pf)
		{
			allf=e[i].pf;
			alls=e[i].ps;
		}
	}
	for(int i=1;i<=900;i++)
	{
		for(int j=1;j<=500;j++)
		{
			update(j);
			if(allf>e[j].pf)
			{
				allf=e[j].pf;
				alls=e[j].ps;
			}
		}
	}
	printf("%.2lf",allf);
}

标签:粒子,wa,double,算法,ij,pf,vec,return,优化
From: https://www.cnblogs.com/PHOTONwa/p/17691460.html

相关文章

  • 2023“钉耙编程”中国大学生算法设计超级联赛(5)
    1001Typhoon题意:给你台风的轨迹坐标以及避难所的坐标,台风的半径不可预测,求让每个避难所不安全的最小台风半径是多少。分析:枚举每个点到所有“线段”的距离取个min。代码:附上队友的代码(懒):#include<bits/stdc++.h>#include<math.h>#definerep(i,a,b)for(inti=a;i<......
  • 5 排序算法总结
    5排序算法总结首先总结表如下:排序方法平均时间复杂度最好情况最坏情况空间复杂度是否稳定排序方式冒泡排序\(O(n^2)\)\(O(n)\)\(O(n^2)\)\(O(1)\)稳定内部排序选择排序\(O(n^2)\)\(O(n^2)\)\(O(n^2)\)\(O(1)\)不稳定内部排序插入排序\(O(n^2)......
  • 代码随想录算法训练营-回溯算法|491.递增子序列
    491. 递增子序列 不对原数组进行排序,利用set对同层的子集进行去重。1classSolution:2deffindSubsequences(self,nums):3result=[]4path=[]5self.backtracking(nums,0,path,result)6returnresult78......
  • JVM调优篇:探索Java性能优化的必备种子面试题
    JVM内存模型首先面试官会询问你在进行JVM调优之前,是否了解JVM内存模型的基础知识。这是一个重要的入门问题。JVM内存模型主要包括程序计数器、堆、本地方法栈、Java栈和方法区(1.7之后更改为元空间,并直接使用系统内存)。正常堆内存又分为年轻代和老年代。在Java虚拟机中,年轻代用于存......
  • 机器学习算法原理实现——决策树里根据信息增益选择特征
    先说熵的定义:  再看信息增益信息增益是一种用于特征选择的指标,用于衡量特征对于数据集分类的贡献程度。它基于信息熵的概念,通过比较特征划分前后的信息熵差异来评估特征的重要性。信息熵是衡量数据集纯度的指标,表示数据集中的不确定性或混乱程度。信息熵越高,数据集的不确......
  • 代码随想录算法训练营第四天| 24. 两两交换链表中的节点, 19.删除链表的倒数第N个结点
    24.两两交换链表中的节点mydemo(超时)/***Definitionforsingly-linkedlist.*structListNode{*intval;*ListNode*next;*ListNode():val(0),next(nullptr){}*ListNode(intx):val(x),next(nullptr){}*ListNode(intx,Lis......
  • 《算法图解》的读书体会
    最近工作有点内耗严重,经常头痛,静下心来读一本书架里的书,好久没有练算法了,程序员算法还是不能丢,在这里分享读书体会。有时候看一本书并不一定是抱着学习的心思去读,那样太累,学习太枯燥了,抱着玩的心态去读,更能让我读下去。如果遇到问题,绕开它,我们不一定要解决问题,逃避问题也是处理问......
  • 文心一言 VS 讯飞星火 VS chatgpt (89)-- 算法导论8.3 2题
    二、用go语言,下面的排序算法中哪些是稳定的:插入排序、归并排序、堆排序和快速排序?给出一个能使任何排序算法都稳定的方法。你所给出的方法带来的额外时间和空间开销是多少?文心一言:在Go语言中,以下排序算法是稳定的:插入排序归并排序而以下的排序算法是不稳定的:堆排序快速排......
  • 文心一言 VS 讯飞星火 VS chatgpt (89)-- 算法导论8.3 2题
    二、用go语言,下面的排序算法中哪些是稳定的:插入排序、归并排序、堆排序和快速排序?给出一个能使任何排序算法都稳定的方法。你所给出的方法带来的额外时间和空间开销是多少?文心一言:在Go语言中,以下排序算法是稳定的:插入排序归并排序而以下的排序算法是不稳定的:堆排序快速排序要使任......
  • C#希尔排序算法
    前言希尔排序简单的来说就是一种改进的插入排序算法,它通过将待排序的元素分成若干个子序列,然后对每个子序列进行插入排序,最终逐步缩小子序列的间隔,直到整个序列变得有序。希尔排序的主要思想是通过插入排序的优势,减小逆序对的距离,从而提高排序效率。希尔排序实现原理首先要确......