c++粒子群优化算法解决多维01背包问题

清疚 2023-01-13 10:40 119阅读 0赞

#include<random>
    #include <iostream>
    #include<vector>
    #include<fstream>
    #include <time.h>
    
    	
    using namespace std;
    //rewrite the <
    bool operator<(vector<int>&a ,vector<int>&b) {
    	bool res = true;
    	if (a.size() != b.size())return false;
    	for (int i = 0; i < a.size(); i++)
    		if (a[i] > b[i]) {
    			res = false;
    			break;
    		}
    	return res;
    			
    
    }
    //rewrite the operator *
    vector<int> operator*(vector<int>&a, int b) {
    	for (int i = 0; i < a.size(); i++) {
    		a[i] *= b;
    	}
    	return a;
    }
    class partical { //the partical in pso algorithm
    public:
    	int dimention; //dimention of position
    	int value;
    	vector<int> weight;
    	
    	vector<double> localP;  //local best position
    	vector<double> velocity; //current velocity
    	//int maxsize;  //the maximum of size
    	vector<double> position;  //the position of this particle
    	//the default constructor by random
    	partical(vector<vector<int>> Wei, vector<int> v,
    		vector<int> constrain, int maxs, int dim);
    	//update the position and w
    	int update(vector<int> v,vector<vector<int>> w, vector<int> cons); //return value ,para:weight
    
    };
    int partical::update(vector<int> v,vector<vector<int>> w,vector<int> cons) {  //return the value
    	int newValue = 0;
    	vector<int> newWei(dimention,0);
    	for (int i = 0; i < position.size(); i++) {
    		if (position[i] < 0.5)position[i] = 0;
    		else position[i] = 1;
    		
    		if (position[i] == 1) {
    			
    			for (int j = 0; j < dimention; j++) {
    				newWei[j] += w[i][j]; //update the weight
    				if (newWei[j] > cons[j]) { //over the constrain
    					return -1;
    				}
    			}
    			newValue += v[i];
    		}
    
    		//calculate the value
    	}
    	return newValue;
    }
    //the default constructor by random
    partical::partical(vector<vector<int>> Wei, vector<int> v,
    	vector<int> constrain, int maxs, int dim) {
    	value = 0;
    	dimention = dim;
    
    	for (int i = 0; i < dimention; i++) {
    
    		weight.push_back(0);
    	}
    	for (int i = 0; i < maxs; i++) {
    		position.push_back(0);
    		velocity.push_back(0.0);
    		localP.push_back(0);
    	}
    			
    	bool flag = true;
    
    	while (flag) {
    		int randN = rand() % maxs; //generate random number
    		if (position[randN] == 0) {
    			for (int i = 0; i < dimention; i++) {
    				weight[i] += Wei[randN][i];
    				if (weight[i] > constrain[i]) {
    					weight[i] - Wei[randN][i];
    					flag = false;
    					break;
    				}
    			}
    			if (flag == false)break;
    			position[randN] = 1;
    			localP[randN] = 1;
    			value += v[randN];
    
    		}
    	}
    
    }
    class swarm {
    public:
    	int optimal; //the global optimal value
    	vector<partical> swarmPart;
    	vector<int> vect_v;  //the value of each item
    	vector<double> globalP;  //the optimal particle position
    	vector<vector<int>> vect_w;
    	vector<int> vect_c;
    	//default constructer
    	swarm() {
    		optimal = 0;
    	}
    	void envolve(double c1, double c2, double inertia); 
    };
    void swarm::envolve(double c1, double c2, double inertia) {
    	//the envolution of swarm
    	//change the position of each particle
    	for (int i = 0; i < swarmPart.size(); i++) {
    		//process each particle
    		vector<double> nextVelocity;
    		for (int j = 0; j < swarmPart[i].position.size(); j++) {
    			//calculate every element of velocity
    			double rand1 = rand() % 100 / 100.0;
    			double rand2 = rand() % 100 / 100.0;
    			double curV = inertia * swarmPart[i].velocity[j];
    			curV += c1 * rand1*(swarmPart[i].localP[j] - swarmPart[i].position[j]);
    			curV += c2 * rand2*(globalP[j] - swarmPart[i].position[j]);
    			//add the random search
    			//curV += (rand() % 10 - 5) / 5.0;
    			nextVelocity.push_back(curV);
    		}
    		//record the old veriable
    		vector<double> oldvelo = swarmPart[i].velocity;
    		vector<double> oldPosition = swarmPart[i].position;
    		vector<int> oldweight = swarmPart[i].weight;
    		int oldvalue = swarmPart[i].value;
    
    
    		swarmPart[i].velocity = nextVelocity;
    		//update the position 
    		for (int j = 0; j < swarmPart[i].position.size(); j++)
    			swarmPart[i].position[j] += nextVelocity[j];
    		//calculate the value
    		int newValue = swarmPart[i].update(vect_v, vect_w, vect_c);
    		if (newValue == -1) { //invalid update ,roll back
    			swarmPart[i].velocity = oldvelo;
    			swarmPart[i].position = oldPosition;
    			swarmPart[i].weight = oldweight;
    			swarmPart[i].value = oldvalue;
    		}
    		else { //update the value ,local and global
    			if (newValue > optimal) {
    				//greater than the best value,update the global value
    				optimal = newValue;
    				globalP = swarmPart[i].position;
    
    				swarmPart[i].localP = swarmPart[i].position;
    				swarmPart[i].value = newValue;
    
    			}
    			else if (newValue > oldvalue) {
    				//update the local
    				swarmPart[i].localP = swarmPart[i].position;
    				swarmPart[i].value = newValue;
    			}
    
    		}
    		//finish the envolution of one part
    	}
    
    }
    int main(int argc,char* argv[])
    {
    	srand((unsigned)time(NULL)); //设置随机种子后 随机数会形成固定的序列
    	//process the input from file  mknapcb1.txt
    	string filename = "mknapcb1.txt";
    	string out = "solution.txt";
    	//string filename = argv[0];
    	//string out = argv[1];
    
    	ifstream file(filename);
    	ofstream outfile(out, ios::trunc);
    	outfile << "# of problems" << endl;
    	int probNum; //the number of problem
    	
    
    	if (!file.is_open()) {
    		cout << "Can not open this file" << endl;
    		return 0;
    	}
    	//input the data
    	file >> probNum;
    	for (int p = 0; p < probNum; p++) {
    
    		int itemSize; //the number of items
    		int dimension;
    		int optimalValue; //the most optimal value 
    
    		file >> itemSize;
    		file >> dimension;
    		file >> optimalValue;
    
    		vector<vector<int>> weight(itemSize, vector<int>(dimension, 0));
    		vector<int> value(itemSize, 0);
    		vector<int> constrain(dimension, 0);
    		//input the value
    		for (int i = 0; i < itemSize; i++) {
    			file >> value[i];
    		}
    		//intput the weight
    		for (int i = 0; i < dimension; i++)
    			for (int j = 0; j < itemSize; j++)
    				file >> weight[j][i];
    
    		for (int i = 0; i < dimension; i++)
    			file >> constrain[i];
    		
    		//initial a swarm
    		swarm swa;
    		swa.vect_v = value;
    		swa.vect_w = weight;
    		swa.vect_c = constrain;
    		int partNum = 6*itemSize;  //define the number of particle
    		
    		//random partical
    		int maxV = 0;
    		for (int i = 0; i < partNum; i++) {
    			partical p(weight,value,constrain,itemSize,dimension);
    			if (p.value > maxV) {
    				maxV = p.value;
    				swa.optimal = maxV;
    				swa.globalP = p.position;
    				
    			}
    			swa.swarmPart.push_back(p);
    		}
    
    		//set the parametre of envolue
    		//Inertia weight para
    		
    		double c1 = 1;  //local weight
    		double c2 = 0.5;  //global weight
    		int iter = 300;    //the quantity of iterator
    		int maxv = swa.optimal;
    		for (int i = 0; i < iter; i++) {
    			double inertia = (rand()%10)/20.0;
    			swa.envolve(c1, c2, inertia);
    			if (swa.optimal > maxv) {
    				maxv = swa.optimal;
    				//cout <<i<<"  "<< maxv*1.0/ optimalValue << endl;
    			}
    
    		}
    		//cout << maxv << endl;		
    		//cout << endl;
    		outfile << "objective value of instance " << p + 1 << endl;
    		//outfile << maxv << endl;
    		for (int i = 0; i < swa.globalP.size(); i++) {
    			outfile << swa.globalP[i] << " ";
    		}
    		outfile << endl;
    		cout << "objective value of instance " << p + 1 << endl;
    		cout << maxv << endl;
    		
    		
    	}
    	file.close();
    	outfile.close();
    	cout << "All solutions are feasible with correct objective values." << endl;
    
    
    	return 0;
    }