前言
这个呢，其实是昨天突然被启发了一下然后去找了一下发现了一个玩意叫做多种群的遗传算法，于是引发了我的思考，为什么要引入多种群的概念，这个就不得不分析一下标准的GA算法也就是SGA，这个玩意有个毛病，如果当种群当中的某个基因忒多了，那么这个时候（假设还没有到达迭代次数）你会发现后面种群能不能有多样性全靠变异，出现局部收敛等等问题（这里我就不复述了，其实很早以前我写遗传算法的时候就说过了这个他的优化，例如EA，MOEA 等等）。不过这个并不是今天的主角，今天的主角是多种群PSO算法，为什么是这个玩意，好吧本来是想要玩玩MPGA的，但是这个代码没找到python版本的，自己写的话时间不够（期末复习呀!）然后突然发现自己以前想过一共馊主意，就是关于PSO能不能让而每一个鸟都跟多个比较好的鸟飞。于是找了一下还真找到了，多种群的PSO。刚好我们以前使用Flink实现过这个PSO，那么我look，look看看能不能改。
适应人群
这个现在的话，由于本人也是在多线发展，玩的东西也比较多，所以有些东西并不适用于大部分的人。而且现在的东西还是偏向这个科研，不像以前偏向做个小demo，写个小web，而且现在的这个小demo也是偏向这个实战，需要一定的基础。
那么这篇博文主要是适用于玩智能算法的同学，需要一定的Java基础和Flink基础。如果木有的可以绕道了~
参考文献
这个由于传统的PSO，俺们就不说了，他的优缺点，也不说了，这个在这里复述也没意思。
这里主要参考了几个文献：
[1]郭成,张万达,王波,王加富.多种群并行协作的粒子群算法[J].计算机与现代化,2022,(01):33-40.
摘要:针对高维复杂优化问题在求解时容易产生维数灾难导致算法极易陷入局部最优的问题,提出一种能够综合考虑高维复杂优化问题的特性,动态调整进化策略的多种群并行协作的粒子群算法。该算法在分析高维复杂问题求解过程中的粒子特点的基础上,建立融合环形拓扑、全连接形拓扑和冯诺依曼拓扑结构的粒子群算法的多种群并行协作的网络模型。该模型结合3种拓扑结构的粒子群算法在解决高维复杂优化问题时的优点,设计一种基于多群落粒子广播-反馈的动态进化策略及其进化算法,实现高维复杂优化环境中拓扑的动态适应,使算法在求解高维单峰函数和多峰函数时均具有较强的搜索能力。仿真结果表明,该算法在求解高维复杂优化问题的寻优精度和收敛速度方面均有良好的性能。
[2]刘悦,杨桦,王青正.基于种群关系的多种群粒子群协同优化算法[J].计算机系统应用,2021,30(10):148-155.DOI:10.15888/j.cnki.csa.007941.
[3]罗德相,周永权,黄华娟,韦杏琼.多种群粒子群优化算法[J].计算机工程与应用,2010,46(19):51-54.
摘要:将一定规模的粒子群平分成三个子群,并分别按基本粒子优化算法、ω自线性调整策略的粒子群算法和云自适应粒子群算法三种不同规则进化,既保持各个子群和算法的独立性和优越性,又不增加算法的复杂性,并提出"超社会"部分,重新定义了速度更换式子,同时还引入了扩张变异方法和扰动操作。实验仿真结果表明,给出算法的全局搜索能力、收敛速度,精度和稳定性均有了显著提高。
这里的话说句大实话这几篇文章好像细节不一样，大体类似。我这里以第三篇为主，因为代码好改~
整体的设计参考这个第三篇，因为改起来方便，然后这玩意是把一共大群分为三个小群，奉行“三个臭皮匠，顶过一共诸葛亮”的思想。那么我这里设计的话就给点自由度，看看到底设计几个种群是比较好的。这个就给各位好好测试一波了~。
算法流程
新流程
这个的话其实和传统的PSO类似的，区别是要划分子种群。
这里流程就不多说了，很好理解。区别就在这：
这个是传统的
这个是新的：
老代码
既然咱们要做修改，那么还是要来看看原来的代码实现的。
原来的项目结构很简单：
实现
这个的话我们在这个原有的基础之上（框架）进行这个修改，只做增强，不做大范围修改。（没办法，当时觉得这个代码写起来还挺好的，现在一看这个可拓展性太差了，本来想改动的，但是这样搞可读性就下去了）
Bird重新定义
我们这里还要重新计算小鸟所在种群的这个最优化的解，所以需要重新定义这个结构。不过也是在原来的基础上做加强。
@Data
@ToString
@NoArgsConstructor
public class Bird implements Cloneable {
//大鸟的编号
private Integer id;
//所在小鸟群的编号
private Integer Cid;
private ArrayList<Double> Pbest;
private ArrayList<Double> Gbest;
//所在小鸟群的最优解
private ArrayList<Double> Cbest;
private Double Functionresult;
private Double LFunctionresult;
private ArrayList<Double> Xpostion;
private ArrayList<Double> Vpersent;
private Integer InterTimes;
public Bird(Integer id, ArrayList<Double> pbest, ArrayList<Double> gbest, Double functionresult, Double LFunctionresult, ArrayList<Double> xpostion, ArrayList<Double> vpersent, Integer interTimes) {
this.id = id;
this.Pbest = pbest;
this.Gbest = gbest;
this.Functionresult = functionresult;
this.LFunctionresult = LFunctionresult;
this.InterTimes = interTimes;
this.setXpostion(xpostion);
this.setVpersent(vpersent);
}
public Bird(Integer id, Integer cid, ArrayList<Double> pbest, ArrayList<Double> gbest, ArrayList<Double> cbest, Double functionresult, Double LFunctionresult, ArrayList<Double> xpostion, ArrayList<Double> vpersent, Integer interTimes) {
this.id = id;
Cid = cid;
Pbest = pbest;
Gbest = gbest;
Cbest = cbest;
Functionresult = functionresult;
this.LFunctionresult = LFunctionresult;
Xpostion = xpostion;
Vpersent = vpersent;
InterTimes = interTimes;
}
public void setXpostion(ArrayList<Double> xpostion) {
//越界处理
int index = 0;
for (Double aDouble : xpostion) {
if(aDouble > ConfigPso.X_up)
xpostion.set(index,ConfigPso.X_up);
else if (aDouble < ConfigPso.X_down)
xpostion.set(index,ConfigPso.X_down);
index++;
}
Xpostion = xpostion;
}
public void setVpersent(ArrayList<Double> vpersent) {
//小鸟超速处理
int index = 0;
for (Double aDouble : vpersent) {
if(aDouble > ConfigPso.V_max)
vpersent.set(index,ConfigPso.V_max);
else if (aDouble < ConfigPso.V_min)
vpersent.set(index,ConfigPso.V_min);
index++;
}
Vpersent = vpersent;
}
@Override
protected Object clone() throws CloneNotSupportedException {
return super.clone();
}
}
就多了两个玩意儿。
BirdFactory 修改
在这里我增加了一个方法
public static Bird MakeBirdCluster(Integer id) throws CloneNotSupportedException {
//设置bird的初始位置，id
//划分这个bird所属的子种群id
if(id%ClusterNumber==0){
//如果无法均分这个种群，那么就直接把多的给到那个最后一子种群去
if(ClusterId<=ConfigPso.Cluster){
ClusterId+=1;
}
}
Bird clone = (Bird) bird.clone();
ArrayList<Double> X_init = new ArrayList<Double>();
ArrayList<Double> V_init =new ArrayList<Double>();
clone.setId(id);
clone.setCid(ClusterId);
for (int i = 0; i< ConfigPso.ParamesNumber; i++){
X_init.add(i,(random.nextDouble()*(Math.abs(ConfigPso.X_down)+ConfigPso.X_up))-Math.abs(ConfigPso.X_down));
V_init.add(i,(random.nextDouble()*(Math.abs(ConfigPso.V_min)+ConfigPso.V_max))-Math.abs(ConfigPso.V_min));
}
clone.setVpersent(V_init);
clone.setXpostion(X_init);
return clone;
}
这个玩意可以帮助我划分种群。
完整的代码如下：
public class BirdFactory {
static Bird bird = new Bird();
static Random random = new Random();
//我们这里人性化一点默认从1开始吧,因为这个小鸟的id也是从1开始的
static Integer ClusterId = 1;
static Integer ClusterNumber = 0;
static {
ClusterNumber = ConfigPso.PopulationNumber / ConfigPso.Cluster;
}
@Deprecated
public static Bird MakeBird(Integer id) throws CloneNotSupportedException {
//设置bird的初始位置，id
Bird clone = (Bird) bird.clone();
ArrayList<Double> X_init = new ArrayList<Double>();
ArrayList<Double> V_init =new ArrayList<Double>();
clone.setId(id);
for (int i = 0; i< ConfigPso.ParamesNumber; i++){
X_init.add(i,(random.nextDouble()*(Math.abs(ConfigPso.X_down)+ConfigPso.X_up))-Math.abs(ConfigPso.X_down));
V_init.add(i,(random.nextDouble()*(Math.abs(ConfigPso.V_min)+ConfigPso.V_max))-Math.abs(ConfigPso.V_min));
}
clone.setVpersent(V_init);
clone.setXpostion(X_init);
return clone;
}
public static Bird MakeBirdCluster(Integer id) throws CloneNotSupportedException {
//设置bird的初始位置，id
//划分这个bird所属的子种群id
if(id%ClusterNumber==0){
//如果无法均分这个种群，那么就直接把多的给到那个最后一子种群去
if(ClusterId<=ConfigPso.Cluster){
ClusterId+=1;
}
}
Bird clone = (Bird) bird.clone();
ArrayList<Double> X_init = new ArrayList<Double>();
ArrayList<Double> V_init =new ArrayList<Double>();
clone.setId(id);
clone.setCid(ClusterId);
for (int i = 0; i< ConfigPso.ParamesNumber; i++){
X_init.add(i,(random.nextDouble()*(Math.abs(ConfigPso.X_down)+ConfigPso.X_up))-Math.abs(ConfigPso.X_down));
V_init.add(i,(random.nextDouble()*(Math.abs(ConfigPso.V_min)+ConfigPso.V_max))-Math.abs(ConfigPso.V_min));
}
clone.setVpersent(V_init);
clone.setXpostion(X_init);
return clone;
}
}
速度更新
现在我们可以来实现这个速度更新方程了：
public static void UpdateSpeedLinegoWCluster(Bird bird){
/**
* V(i+1) = w*V(i) +c1*r1*(Pbest-X(i)) + c2*r2*(Gbest-X(i)) + c3*r3*(Cbest-X(i))
* */
ArrayList<Double> CurrentSpeed = bird.getVpersent();
//更新速度,传入大鸟，会自动更新大鸟的速度，同时返回更新后的速度向量
double fai1 = ConfigPso.C1 * random.nextDouble(); //c1*r1
double fai2 = ConfigPso.C2 * random.nextDouble(); //c2*r2
double fai3 = ConfigPso.C3 * random.nextDouble(); //c3*r3
int index = 0;
for (Double aDouble : CurrentSpeed) {
aDouble = ConfigPso.LineGoW(bird.getInterTimes()) * aDouble
+ fai1*(bird.getPbest().get(index) - bird.getXpostion().get(index))
+ fai2*(bird.getGbest().get(index) - bird.getXpostion().get(index))
+ fai3*(bird.getCbest().get(index) - bird.getXpostion().get(index));
CurrentSpeed.set(index,aDouble);
index ++ ;
}
//完成对速度的更新
bird.setVpersent(CurrentSpeed);
}
然后这里值得一提的是，我们这里使用的是线性权重更新。在那个玩意的基础上进行改动。
配置改动
当然在这里还有配置的修改。改动。
Flink算子修改
这里主要是两个函数的修改。
//此时我们对这个玩意进行修改,同时计算这个Gbest和Cbest。
static class MinMapsGAndC implements MapFunction<Bird,Bird>{
//这个是通用的不存在初始化例外使用的情况，这个是其实是为了能够拿到全局最小的大鸟
@Override
public Bird map(Bird bird) {
//状态流，状态由系统记录
//这个部分是计算出当前迭代次数的全局最优解
if(bird1!=null){
if( bird.getFunctionresult()> bird1.getFunctionresult())
bird.setGbest(bird1.getXpostion());
else {
bird.setGbest(bird.getXpostion());
bird1=bird;
}
}
else{
bird1 = bird;
bird.setGbest(bird.getXpostion());
}
//这个部分是计算出当前所在的子种群的那个最优解，同样的这个其实也是用于初始化
//其实这里我也是可以直接按照Cid分类，计算出来也就是按照这个个体最优的方式来计算的，但是我不想去改动
//整个的代码结构了，所以直接增加这个方法就ok了，其实都是可以实现类似的效果的，因为只要我按照迭代分好
//类以后，其实都是不需要再进行keyby了，只是考虑到方便计算然后再分个类罢了。
if(ClusterBestBird.containsKey(bird.getCid())){
Bird currentClusterBest = ClusterBestBird.get(bird.getCid());
if(bird.getFunctionresult()>currentClusterBest.getFunctionresult()){
bird.setCbest(currentClusterBest.getXpostion());
}else {
bird.setCbest(bird.getXpostion());
ClusterBestBird.replace(bird.getCid(),bird);
}
}else {
bird.setCbest(bird.getXpostion());
ClusterBestBird.put(bird.getCid(),bird);
}
return bird;
}
}
//这个方法也是更新全局最优的和子群里面最好滴
static class MinMapsGAndCIterate implements MapFunction<Bird,Bird>{
//由于前面先运行MinMapsG后已经记录了全局最优，所以没有必要进行比较了，直接进行修改即可为了
//保证运行效率
@Override
public Bird map(Bird bird){
bird.setGbest(bird1.getXpostion());
bird.setCbest(ClusterBestBird.get(bird.getCid()).getXpostion());
return bird;
}
}
这部分的完整代码如下：
public class DoSteam {
static Bird bird1; //当前迭代次数最优小鸟
static HashMap<Integer,Bird> ClusterBestBird = new HashMap<>();// 每一个小种群当中的最好的那个大鸟
public static void RunCore() throws Exception {
StreamExecutionEnvironment env = StreamExecutionEnvironment.getExecutionEnvironment();
DataStreamSource<Bird> BirdInitStream = env.addSource(new InitBirds());
KeyedStream<Bird, Integer> Birdtimeing = BirdInitStream.keyBy(Bird::getInterTimes);
// SingleOutputStreamOperator<Bird> map = Birdtimeing.map(new MinMapsG());
// 这里进行了修改，此时得到了全局好的bird1 以及每一个 子群最好的bird
SingleOutputStreamOperator<Bird> map = Birdtimeing.map(new MinMapsGAndC());
KeyedStream<Bird, Tuple> id = map.keyBy("id");
// SingleOutputStreamOperator<Bird> map1 = id.map(new MinMapsGinterate());
// 这里同上也是做了修改
SingleOutputStreamOperator<Bird> map1 = id.map(new MinMapsGAndCIterate());
SingleOutputStreamOperator<Bird> RealStream = map1.map(new MinMapsPinitial());
// RealStream.print("init");
//完成初始化后的数据流，到这里开始进行循环
IterativeStream<Bird> iterateStream = RealStream.iterate();
SingleOutputStreamOperator<Bird> IterationBody = iterateStream.keyBy(Bird::getInterTimes) //分组
// .map(new MinMapsG()) //首次寻早最优解
.map(new MinMapsGAndC()) //这里修改，找到当前全局最好的和当前子群最好的
.keyBy("id") //再次分组两个原因
// .map(new MinMapsGinterate()) // 再次统计最优解，为全局的位置最优解
.map(new MinMapsGAndCIterate()) //这个也是做个修改
.map(new MinMapsP())// 循环处理当中的个体最优解决
.map(new CalculationPso());//这一步是进行粒子群的运算，也是比较重要的一环
//需要进入循环的条件
SingleOutputStreamOperator<Bird> IterationFlag = IterationBody.filter((FilterFunction<Bird>) bird -> bird.getInterTimes() < ConfigPso.IterationsNumber);
iterateStream.closeWith(IterationFlag);
SingleOutputStreamOperator<Bird> Outstream = IterationBody.filter((FilterFunction<Bird>) bird -> bird.getInterTimes() >= ConfigPso.IterationsNumber);
SingleOutputStreamOperator<Bird> MinBrid = Outstream.countWindowAll(ConfigPso.PopulationNumber).min("Functionresult");
MinBrid.print("The best bird");
env.execute();
}
static class CalculationPso implements MapFunction<Bird,Bird>{
@Override
public Bird map(Bird bird) {
Core.UpDataBird(bird);
bird.setFunctionresult(FunctionMake.FourFunction(bird.getXpostion()));
bird.setInterTimes(bird.getInterTimes()+1);
return bird;
}
}
static class MinMapsP implements MapFunction<Bird,Bird>{
@Override
public Bird map(Bird bird) {
//此时状态由Bird自己进行管理，Lfunctionresult记录的就是t-1次的个体最优的值，我们这边是找最小的的函数值
if(bird.getFunctionresult()<bird.getLFunctionresult()){
bird.setPbest(bird.getXpostion());
//更新最优值
bird.setLFunctionresult(bird.getFunctionresult());
}
return bird;
}
}
static class MinMapsPinitial implements MapFunction<Bird,Bird>{
@Override
public Bird map(Bird bird) {
//本次进行初始化
//为了减少条件判读，所以直接把个体最优的算子进行拆分
bird.setPbest(bird.getXpostion());
bird.setLFunctionresult(bird.getFunctionresult());
return bird;
}
}
@Deprecated
static class MinMapsGinterate implements MapFunction<Bird,Bird>{
//由于前面先运行MinMapsG后已经记录了全局最优，所以没有必要进行比较了，直接进行修改即可为了
//保证运行效率
@Override
public Bird map(Bird bird) {
bird.setGbest(bird1.getXpostion());
return bird;
}
}
//这个方法也是更新全局最优的和子群里面最好滴
static class MinMapsGAndCIterate implements MapFunction<Bird,Bird>{
//由于前面先运行MinMapsG后已经记录了全局最优，所以没有必要进行比较了，直接进行修改即可为了
//保证运行效率
@Override
public Bird map(Bird bird){
bird.setGbest(bird1.getXpostion());
bird.setCbest(ClusterBestBird.get(bird.getCid()).getXpostion());
return bird;
}
}
@Deprecated
static class MinMapsG implements MapFunction<Bird,Bird>{
//这个是通用的不存在初始化例外使用的情况，这个是其实是为了能够拿到全局最小的大鸟
@Override
public Bird map(Bird bird) {
//状态流，状态由系统记录
if(bird1!=null){
if( bird.getFunctionresult()> bird1.getFunctionresult())
bird.setGbest(bird1.getXpostion());
else {
bird.setGbest(bird.getXpostion());
bird1=bird;
}
}
else{
bird1 = bird;
bird.setGbest(bird.getXpostion());
}
return bird;
}
}
//此时我们对这个玩意进行修改,同时计算这个Gbest和Cbest。
static class MinMapsGAndC implements MapFunction<Bird,Bird>{
//这个是通用的不存在初始化例外使用的情况，这个是其实是为了能够拿到全局最小的大鸟
@Override
public Bird map(Bird bird) {
//状态流，状态由系统记录
//这个部分是计算出当前迭代次数的全局最优解
if(bird1!=null){
if( bird.getFunctionresult()> bird1.getFunctionresult())
bird.setGbest(bird1.getXpostion());
else {
bird.setGbest(bird.getXpostion());
bird1=bird;
}
}
else{
bird1 = bird;
bird.setGbest(bird.getXpostion());
}
if(ClusterBestBird.containsKey(bird.getCid())){
Bird currentClusterBest = ClusterBestBird.get(bird.getCid());
if(bird.getFunctionresult()>currentClusterBest.getFunctionresult()){
bird.setCbest(currentClusterBest.getXpostion());
}else {
bird.setCbest(bird.getXpostion());
ClusterBestBird.replace(bird.getCid(),bird);
}
}else {
bird.setCbest(bird.getXpostion());
ClusterBestBird.put(bird.getCid(),bird);
}
return bird;
}
}
static class InitBirds implements SourceFunction<Bird>{
@Override
public void run(SourceContext<Bird> ctx) throws Exception {
for(int i=1;i<=ConfigPso.PopulationNumber; i++) {
Bird bird = BirdFactory.MakeBirdCluster(i);
Double functionresult = FunctionMake.FourFunction(bird.getXpostion());
bird.setFunctionresult(functionresult);
bird.setInterTimes(0);//表示正在初始化
ctx.collect(bird);
}
}
@Override
public void cancel() {
}
}
}
完整代码获取
这里的话，可以直接我的gitee 里面去搞到来:
https://gitee.com/Huterox/FlinkPso.git
不过我仓库里面的代码没有把今天的内容进行更新覆盖，因为我不想搞乱了，所以有需要的同学自己照着该就行了。
测试
ok，到了咱们的测试环节。
我们这里使用的玩意是：
这个函数是cec2003测试集里面的玩意儿。
测试结果如下：
调用的测试代码如下：
import java.util.ArrayList;
public class RunPso {
public static void main(String[] args) throws Exception {
//调用Flink 方式
//1.实现FunctionImpl接口，该接口的为目标函数，不实现默认使用案例。
FunctionMake.SetFunction(new TotalFunction());
//2.调用配置类进行相关参数设置,不设置默认使用默认配置，但是重点需要设置参数个数
ConfigPso.ParamesNumber = 4;
ConfigPso.IterationsNumber=100;
ConfigPso.PopulationNumber = 30;
ConfigPso.X_up = 1.0;
ConfigPso.X_down = -1.0;
//3.运行核心
DoSteam.RunCore();
}
static class TotalFunction implements FunctionsImpl{
@Override
public Double FourFunction(ArrayList<Double> parades) {
//13个测试函数随便调用
return CECFactory.getf3(parades);
}
}
}
总体来说好像效果还可以，看具体情况吧。
