智能算法

PSO

​ 粒子群算法（Particle Swarm Optimization）是在仿真生物群体社会活动的基础上，通过模拟群体生物相互协同寻优能力，从而构造出的一种新的智能优化算法。它具有易理解、易实现、全局搜索能力强、收敛速度快、设置参数少等优点，在科学研究和工程领域都受到了广泛的应用。

原理

​ 在粒子群优化算法中，每个优化问题的潜在解都是搜索空间中的一只鸟，称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。优化开始时先初始化为一群随机粒子（随机解）。然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个极值来更新自己。第一个极值就是整个种群目前找到的最优解。这个极值是全局最优解。另外也可以不用整个种群而只是用其中一部分作为粒子的邻居，那么在所有邻居中的极值就是全局最优解。第二个极值是粒子本身所找到的最优解，称为个体极值。这是因为粒子仅仅通过跟踪全局极值或者局部极值来更新位置，不可能总是获得较好的解。这样在优化过程中，粒子在追随全局极值或局部极值的同时追随个体极值则圆满的解决了这个问题。

实现

粒子群优化算法具有编程简单，易实现的特点。下面给出其实现的具体步骤：

步骤1：初始化。初始搜索点的位置X0i及其速度V0i通常是在允许的范围内随机产生的，每个粒子的Pbest坐标设置为其当前位置，且计算出其相应的个体极值（即个体极值点的适应度值），而整个邻域的最优粒子就是该粒子邻域中个体极值中最好的，记录该最好值的粒子序号，并将Nbesti设置为该最好粒子的当前位置。

步骤2：评价每一个粒子。计算粒子的适应度值,如果好于该粒子当前的个体极值，则将Pbest设置为该粒子的位置，且更新个体极值。如果在该粒子的邻域内所有粒子的个体极值中最好的好于当前的Nbesti，则将Nbesti设置为该粒子的位置，记录该粒子的序号，且更新Nbesti的函数值。

步骤3：粒子的更新。用式(2.1)和式(2.2)对每一个粒子的速度和位置进行更新。

步骤4：检验是否符合结束条件。如果当前的迭代次数达到了预先设定的最大次数（或达到最小错误要求)，则停止迭代，输出最优解，否则转到步骤2。

代码

/* 
 * File:   GA_Minimal.cpp
 * Author: GonewithGt
 *
 */

#include <iostream>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstdint>
#include <cassert>
#include <algorithm>
#include <iomanip>

#define POP_SIZE        (100)
#define Genius          (20)
#define MAX_GENR        (100000)
#define MUT_CHANCE      (10)

#define GENE_TYPE       double
#define GENE_SIZE	(sizeof(GENE_TYPE))
//#define GENE_MASK       (GENE_SIZE/2)

using namespace std;

typedef struct {
    GENE_TYPE gene;
	GENE_TYPE gene2;
    double fitness;
} individual; 

individual population[POP_SIZE];
//GENE_TYPE mutRate = MUT_CHANCE;

double function2(double x){
	double tmp=0.;
	for(int j=1;j<=5;j++)
	{
		tmp=j*1.0*cos((j+1)*x*1.0+j)+tmp;
	}
	return tmp;
}

double fitnessFunction2(GENE_TYPE x) {
    if (x > 1e-8)
		return function2(x);
	//return x * x * log(x);
    return 0.; // limit of above function around 0
}

void recombine2(GENE_TYPE p1, GENE_TYPE p2, GENE_TYPE *c1, GENE_TYPE *c2) {
    assert(sizeof(uint64_t) == sizeof(GENE_TYPE));
    int cpoint = rand() % (GENE_SIZE * 8) + 1;
    uint64_t mask = (1UL << cpoint) - 1;
    
    *(uint64_t *)(c1) = *(uint64_t *)(&p1) & (mask);
    *(uint64_t *)(c1) |= *(uint64_t *)(&p2) & (mask);
    *(uint64_t *)(c2) = *(uint64_t *)(&p2) & (mask);
    *(uint64_t *)(c2) |= *(uint64_t *)(&p1) & (mask);
}


void mutate2(GENE_TYPE * c1, GENE_TYPE * c2) {
    *c1 = rand()*20./RAND_MAX-10.;
    *c2 = rand()*20./RAND_MAX-10.;
}

bool ValueCmp2(individual const & a, individual const & b) {
    return a.fitness < b.fitness;
}

/*
 * MinimalGA uygulamasi ana fonksiyonu
 */
int main(int argc, char** argv) {
	//freopen("Uva673.in","r",stdin);
	freopen("test26.out","w",stdout);
	cout<<"Generic 2"<<endl;
    int i, j;
    GENE_TYPE parent1, parent2, parent21, parent22;
    GENE_TYPE child1, child2, child21, child22;

    srand(time(0));
    
    //cout << "Basit Genetik Algoritma Uygulamasi" << endl;
    //cout << "Uyumluluk fonksiyonu : Some exponential stuff" <<GENE_SIZE<< endl;
    cout << "Population Size : " << POP_SIZE << endl;
    cout << "Max Generation: " << MAX_GENR << endl;
	cout << "Genius: " << Genius << endl;
    //cout << "Mutasyon olasiligi : " << MUT_CHANCE << endl;
    
    for (i = 0; i < POP_SIZE; i++) {
        //population[i].gene = (rand() % 100 - 50) / 50.;
		population[i].gene = rand()*20./RAND_MAX-10.;
		population[i].gene2 = rand()*20./RAND_MAX-10.;
        population[i].fitness = fitnessFunction2(population[i].gene)*fitnessFunction2(population[i].gene2);
    }
    sort(population, population + POP_SIZE, ValueCmp2);
    
    i = 0;
    while( i < MAX_GENR) {         
        for (j = Genius; j < POP_SIZE-Genius; j += 2) {
            parent1 = population[j].gene;
            parent2 = population[j + 1].gene;
            if (j < rand()%POP_SIZE) 
				mutate2(&child1, &child2);
			else
				recombine2(parent1, parent2, &child1, &child2);
            population[j].gene = child1;
            population[j + 1].gene = child2;

			parent21 = population[j].gene2;
            parent22 = population[j + 1].gene2;
            if (j < rand()%POP_SIZE) 
				mutate2(&child21, &child22);
			else
				recombine2(parent21, parent22, &child21, &child22);
            population[j].gene2 = child21;
            population[j + 1].gene2 = child22;
        }

		for (j = POP_SIZE-Genius; j < POP_SIZE-10; j += 2) {
            parent1 = population[j-(POP_SIZE-Genius)].gene;
            parent2 = population[j + 1-(POP_SIZE-Genius)].gene;
            if (j < rand()%POP_SIZE) 
				mutate2(&child1, &child2);
			else
				recombine2(parent1, parent2, &child1, &child2);
            population[j].gene = child1;
            population[j + 1].gene = child2;

			parent21 = population[j].gene2;
            parent22 = population[j + 1].gene2;
            if (rand()%POP_SIZE<0.3*POP_SIZE) 
				mutate2(&child21, &child22);
			else
				recombine2(parent21, parent22, &child21, &child22);
            population[j].gene2 = child21;
            population[j + 1].gene2 = child22;
		}

		for (j = POP_SIZE-10; j < POP_SIZE; j += 2) {
            parent1 = population[j-(POP_SIZE-10)].gene;
            parent2 = population[j + 1-(POP_SIZE-10)].gene;
            if (j < rand()%POP_SIZE) 
				mutate2(&child1, &child2);
			else
				recombine2(parent1, parent2, &child1, &child2);
            population[j].gene = child1;
            population[j + 1].gene = child2;

			//parent21 = population[j].gene2;
            //parent22 = population[j + 1].gene2;
            //if (rand()%POP_SIZE<0.3*POP_SIZE) 
			//	mutate2(&child21, &child22);
			//else
			//	recombine2(parent21, parent22, &child21, &child22);
            //population[j].gene2 = child21;
           // population[j + 1].gene2 = child22;
        }
        
        for(j = 0; j < POP_SIZE; j++)
            population[j].fitness = fitnessFunction2(population[j].gene)*fitnessFunction2(population[j].gene2);
        
        sort(population, population + POP_SIZE, ValueCmp2);
        

	//mutRate *= 0.9999;

        //if(abs(population[0].fitness) < 1e-8 || abs(population[1].fitness) < 1e-8)
        //    break;
			cout<<"The "<<i<<"th generation:"<<endl;
		for(int k=0;k<20;k++){
		
		cout<<setprecision(9)<<"  x"<<k<<1<<"="<<population[k].gene<<"  x"<<k<<2<<"="<<population[k].gene2<<"  y="<<population[k].fitness<<endl;
		
	}

		i++;
    }
    

    //int minIndex = (population[0].fitness > population[1].fitness) ? 1 : 0;
    //cout << "An effective gen : " << population[minIndex].gene << endl;
    //cout << "Minimal fitness : " << population[minIndex].fitness << endl;
    
   // cin.get();
    
    return 0;
}