[C++知识库] 免疫优化算法在物流配送中心选址中的应用 C++ 实现

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> C++知识库 -> 免疫优化算法在物流配送中心选址中的应用 C++ 实现 -> 正文阅读

[C++知识库]免疫优化算法在物流配送中心选址中的应用 C++ 实现

免疫优化算法在物流配送中心选址中的应用 C++ 实现

简介

为了完成老师布置的作业，找了一个案例来自《matlab智能算法30个案例》，选了免疫优化算法在物流配送中心选址中的应用，因为要求用C/C++写，但是在网上翻遍都没有相应的代码，所以只能自己动手了，上代码。

头文件mainyi.h

#include<vector>
using namespace std;

typedef struct 
{
	vector<int> fitness;
	vector<double> concentration;
	vector<double> excellence;
	vector<vector<int>> chroms;

}population;


void popinit(vector<vector<int>>& chrom,int M, int length);

int fitness(vector<int>& chrom, vector<vector<int>> city_coordinate);

int loadData(vector<vector<int>>& city_coordinate);

double concentration(int target, int M, vector<vector<int>> individuals);

void excellence(population& individuals, int M, int ps);

population bestselect(population individuals, int M, int overbest);

population select(population individuals, int sizepop);

vector<vector<int>> cross(double pcross, vector<vector<int>> chroms, int sizepop, int length);

vector<vector<int>> mutate(double pmutation, vector<vector<int>> chroms, int sizepop, int length,int city_num);

population incorporate(population individuals, int sizepop, population bestindividuals, int overbest);

main函数

#include<iostream>
#include<fstream>
#include<vector>
#include"mianyi.h"
#include<string>
#include<algorithm>
#include<numeric>
#include<Windows.h>
using namespace std;

// 算法基本参数
int sizepop = 10;// 种群规模
int overbest = 10;// 记忆库容量
int MAXGEN = 1000;// 迭代次数
double pcross = 0.5; //交叉概率 
double pmutation = 0.4;//变异概率
double ps = 0.95; //多样性评价参数
int length = 6;//配送中心数
int M = sizepop + overbest;  //记忆库+父代种群得到的最终种群


vector<vector<int>> city_coordinate;  //城市坐标
vector<vector<double>> trace; //记录每代种群最优个体适应度和种群平均适应度

int main() {
	
	//初始化种群
	population individuals;

	popinit(individuals.chroms,M,length); 
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < length; j++) {
			cout << individuals.chroms[i][j]<<" ";
		}
		cout << endl;
	} 

	//导入城市坐标
	loadData(city_coordinate);

	//迭代寻优
	for (int i = 0; i < MAXGEN; i++) {

		for (int j = 0; j < M; j++) {
			individuals.fitness.push_back(fitness(individuals.chroms[j], city_coordinate)); //抗体和抗原适应度计算
			individuals.concentration.push_back(concentration(j, M, individuals.chroms)); //抗体浓度计算
		}
		excellence(individuals,M,ps); //综合亲和度和浓度评价抗体优秀程度，得出繁殖概率
		//查看种群抗体适应度
		/*for (int k = 0; k < M; k++) {
			cout << individuals.fitness[k]<<" ";
		}*/
		//查看各个抗体的浓度
		/*for (int k = 0; k < M; k++) {
			cout << individuals.concentration[k] << " ";
		}*/
		/*查看抗体优秀程度
		for (int k = 0; k < M; k++) {
			cout << individuals.excellence[k] << " ";
		}*/

		//记录当代最佳个体和种群平均适应度
		vector<int>:: iterator bestChrom_fit = min_element(begin(individuals.fitness),end(individuals.fitness));
		int bestChrom_idx = distance(begin(individuals.fitness), bestChrom_fit);
		vector<int> bestChrom = individuals.chroms[bestChrom_idx];
		
		double population_mean = accumulate(begin(individuals.fitness), end(individuals.fitness), 0.0) / individuals.fitness.size();
		vector<double> v;
		v.push_back(*bestChrom_fit); v.push_back(population_mean);
		trace.push_back(v);

		cout << "no." << i << " bestChrom_fit is " << *bestChrom_fit << " mean_fitness is "<<population_mean<<endl;
		cout << "bestChrom is ";
		for (int j = 0; j < bestChrom.size(); j++) {
			cout << bestChrom[j] << ",";
		}
		cout << endl<<endl;

		//更新记忆库
		population bestindividuals;
		bestindividuals = bestselect(individuals, M, overbest);  
		//更新父代种群
		individuals = bestselect(individuals, M, sizepop);

		// 选择，交叉，变异操作，再加入记忆库中抗体，产生新种群
		individuals = select(individuals,sizepop);
	    /*	cout << "==========选择操作后的种群=============\n";
		for (int i = 0; i < sizepop; i++) {
			for (int j = 0; j < length; j++) {
				cout << individuals.chroms[i][j] << " ";
			}
			cout << endl;
		}*/

		individuals.chroms = cross(pcross, individuals.chroms, sizepop, length);
	 /*  	cout << "==========交叉操作后的种群=============\n";
		for (int i = 0; i < sizepop; i++) {
			for (int j = 0; j < length; j++) {
				cout << individuals.chroms[i][j] << " ";
			}
			cout << endl;
		}*/
		individuals.chroms = mutate(pmutation, individuals.chroms, sizepop, length, city_coordinate.size());
	/*	cout << "==========变异操作后的种群=============\n";
		for (int i = 0; i < sizepop; i++) {
			for (int j = 0; j < length; j++) {
				cout << individuals.chroms[i][j] << " ";
			}
			cout << endl;
		}
		cout << "种群个数" << individuals.chroms.size()<<endl;*/
		individuals = incorporate(individuals, sizepop, bestindividuals, overbest);
		cout << "==========种群=============\n";
		for (int i = 0; i < sizepop; i++) {
			for (int j = 0; j < length; j++) {
				cout << individuals.chroms[i][j] << " ";
			}
			cout << endl;
		}
	}
	return 0;
}

popinit函数

#include<vector>
#include<time.h>
#include<Windows.h>
#include"mianyi.h"
#include<iostream>	
using namespace std;

void popinit(vector<vector<int>>& chroms, int M, int length) {

	srand((unsigned)time(0));  // 产生随机数种子
	Sleep(1000);    //每次延时1s，来改变随机数种子,保证每次运行生成的种群不同

	for (int i = 0; i < M; i++) {

		//获取0-30间的随机数，不可重复 
		vector<int> v;
		for (int j = 0; j < length; j++) {
			if (j == 0) {
				int city_num0 = rand() % 31;
				v.push_back(city_num0);
				continue;
			}
			vector<int>::iterator it;
			int city_num;                       
			do {
				city_num = rand() % 31;
				it = find(v.begin(), v.end(), city_num);
			} while (it != v.end());
			v.push_back(city_num);  

		}

		chroms.push_back(v);
	}
}

loadData函数

#include<vector>
#include<string>
#include<iostream>
#include<fstream>
using namespace std;
int loadData(vector<vector<int>>& city_coordinate) {

	char strFilename[100];
	string line;
	cout << "|=========用鼠标拖入城市坐标文件，按回车键。=======|" << endl;
	gets_s(strFilename);
	ifstream File(strFilename);
	if (!File.is_open())
	{
		cout << "can not open this file" << endl;
		return 0;
	}
	while (getline(File, line)) {
		vector<int> v;
		string str1, str2;
		int index;
		line += '\n'; //getline获取行 无\n
		//split 按，分割
		for (index = 0; line[index] != ','; index++) {
			str1 += line[index];
		}
		index++;
		//cout << str1<<' ';
		for (; line[index] != '\n'; index++) {
			str2 += line[index];
		}
		//cout << str2 << endl;
		//string转int
		v.push_back(atoi(str1.c_str()));
		v.push_back(atoi(str2.c_str()));

		//放入城市坐标
		city_coordinate.push_back(v);
	}
}

loadData函数

#include<vector>
#include<string>
#include<iostream>
#include<fstream>
using namespace std;
int loadData(vector<vector<int>>& city_coordinate) {

	char strFilename[100];
	string line;
	cout << "|=========用鼠标拖入城市坐标文件，按回车键。=======|" << endl;
	gets_s(strFilename);
	ifstream File(strFilename);
	if (!File.is_open())
	{
		cout << "can not open this file" << endl;
		return 0;
	}
	while (getline(File, line)) {
		vector<int> v;
		string str1, str2;
		int index;
		line += '\n'; //getline获取行 无\n
		//split 按，分割
		for (index = 0; line[index] != ','; index++) {
			str1 += line[index];
		}
		index++;
		//cout << str1<<' ';
		for (; line[index] != '\n'; index++) {
			str2 += line[index];
		}
		//cout << str2 << endl;
		//string转int
		v.push_back(atoi(str1.c_str()));
		v.push_back(atoi(str2.c_str()));

		//放入城市坐标
		city_coordinate.push_back(v);
	}
}

fitness函数

#include"mianyi.h"
#include<iostream>
#include<vector>
#include <string>
#include<fstream>
#include<math.h>
#define MAX_DIS 1000000
#define E 2.718281828459
using namespace std;
int fitness(vector<int>& chrom,vector<vector<int>> city_coordinate) {
	
	//货物量
	int carge[] = { 20,90,90,60,70,70,40,90,90,70,60,40,40,40,20,80,90,70,100,50,50,50,80,70,80,40,40,60,70,50,30 };
	//计算距离，找出最近配送点
	vector<vector<int>> distance;
	vector<vector<int>> min_distance;
	for (int i = 0; i < city_coordinate.size(); i++) {
		int min = MAX_DIS, index;
		vector<int> v;
		vector<int> min_v;
		for (int j = 0; j < chrom.size(); j++) {
			int dis = sqrt(pow(city_coordinate[i][0] - city_coordinate[chrom[j]][0], 2) + pow(city_coordinate[i][1] - city_coordinate[chrom[j]][1], 2));
			if (dis < min ) {
				min = dis;
				index = chrom[j];
			}
			v.push_back(dis);
		}
		min_v.push_back(min); min_v.push_back(index);
		distance.push_back(v);
		min_distance.push_back(min_v);
	}
	//计算开销
	double expense = 0.0;
	for (int i = 0; i < city_coordinate.size(); i++) {
		expense += carge[i] * min_distance[i][0];
	}
	//记录距离大于3000的城市个数
	int record_3000=0;
	for (int i = 0; i < min_distance.size(); i++) {
		if (min_distance[i][0] > 3000) record_3000++;
	}
	//距离大于3000取一个惩罚值
	double fit = expense + 4.0 * E + 4 * record_3000;
	return fit;
  
}

concentration函数

#include<vector>
using namespace std;
double similarity(vector<int> chrom_target, vector<int> chrom_other) {
	double res = 0.0;
	for (int i = 0; i < chrom_target.size(); i++) {
		for (int j = 0; j < chrom_other.size(); j++) {
			if (chrom_other[j] == -1) continue;   //该元素已查过，直接跳过
			if (chrom_target[i] == chrom_other[j]) {
				res++;
				chrom_other[j] = -1;  //避免重复
				break;
			}
		}
	 }
	return res / chrom_target.size();
}
double concentration(int target,int M,vector<vector<int>> chroms) {
	double concentration = 0.0;
	for (int i = 0; i < M; i++) {
		//if (i == target) continue;
		double xsd = similarity(chroms[target],chroms[i]);
		if (xsd > 0.5) concentration += 1;
	}
	return concentration/M;
}

excellence函数

#include<vector>
#include "mianyi.h"
using namespace std;


void excellence(population& individuals, int M, int ps) {
	double sumfit = 0.0;
	for (int i = 0; i < individuals.fitness.size(); i++) {
		sumfit += 1.0 / individuals.fitness[i];
	}
	double sumcon = 0.0;
	for (int i = 0; i < individuals.concentration.size(); i++) {
		sumcon += individuals.concentration[i];
	}
	for (int i = 0; i < M; i++) {
		double exc = 1.0 / individuals.fitness[i] / sumfit * ps + individuals.concentration[i] / sumcon * (1 - ps);
		individuals.excellence.push_back(exc);
	}
}

bestselect函数

#include "mianyi.h"
#include<algorithm>
#include<iostream>
#include<map>


typedef pair<int, int> PAIR;
typedef pair<int, double> PAIR2;

//按照fitness升序排列
bool cmp(const PAIR& left, const PAIR& right) {
	return left.second < right.second;
}
//按照excellence降序排列
bool cmp2(const PAIR2& left, const PAIR2& right) {
	return left.second > right.second;
}
population bestselect(population individuals, int M, int _size) {
	population ret; int s = 3;


   //按照fitness升序排列，同时携带下标
	map<int, int> map_fit;
	for (int i = 0; i < individuals.fitness.size(); i++) {
		map_fit[i] = individuals.fitness[i];
	}
	vector<PAIR> vec_fit(map_fit.begin(), map_fit.end());
	sort(vec_fit.begin(), vec_fit.end(),cmp);
	/*查看按fitness升序排序后的结果
	for (int i = 0; i < vec_fit.size(); i++) {
		cout << vec_fit[i].first << "->" << vec_fit[i].second << endl;
	}*/


	//精英保留策略，将fitness最小的s个个体先存起来，避免因其浓度高而被淘汰
	for (int i = 0; i < s; i++) {
		ret.fitness.push_back( individuals.fitness[vec_fit[i].first]);
		ret.concentration.push_back( individuals.concentration[vec_fit[i].first]);
		ret.excellence.push_back( individuals.excellence[vec_fit[i].first]);
		ret.chroms.push_back(individuals.chroms[vec_fit[i].first]);
	}

	//剩余个体
	population remain_individuals;
	for (int j = s; j < M; j++) {
		remain_individuals.fitness.push_back(individuals.fitness[vec_fit[j].first]);
		remain_individuals.concentration.push_back(individuals.concentration[vec_fit[j].first]);
		remain_individuals.excellence.push_back(individuals.excellence[vec_fit[j].first]);
		remain_individuals.chroms.push_back(individuals.chroms[vec_fit[j].first]);
	}
	map<int, double> map_exc;
	for (int i = 0; i < remain_individuals.excellence.size(); i++) {
		map_exc[i] = remain_individuals.excellence[i];
	}
	vector<PAIR2> vec_exc(map_exc.begin(), map_exc.end());
	sort(vec_exc.begin(), vec_exc.end(), cmp2);
	/*查看按excellence降序排序后的结果
    for (int i = 0; i < vec_exc.size(); i++) {
	cout << vec_exc[i].first << "->" << vec_exc[i].second << endl;
    }*/

	//在剩余抗体群中按excellence再选n-s个个体 
	for (int i = s; i < _size; i++) {
		ret.fitness.push_back(remain_individuals.fitness[vec_exc[i - s].first]);
		ret.concentration.push_back(remain_individuals.concentration[vec_exc[i - s].first]);
		ret.excellence.push_back(remain_individuals.excellence[vec_exc[i - s].first]);
		ret.chroms.push_back(remain_individuals.chroms[vec_exc[i - s].first]);
	}
	return ret;
}

select函数

#include "mianyi.h"
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;

bool cmp(double a, double b) {
	return a > b;
}

population select(population individuals, int sizepop) {
	population ret;
	vector<double> excellence = individuals.excellence;
	double exc_sum = 0.0;
	for (int i = 0; i < excellence.size(); i++) {
		exc_sum += excellence[i];
	}
	vector<double> pselect;
	for (int i = 0; i < excellence.size(); i++) {
		pselect.push_back(excellence[i] / exc_sum);
	}
	//
	sort(pselect.begin(), pselect.end(), cmp);
	

	vector<int> index;
	for (int i = 0; i < sizepop; i++) {
		double pick = rand() % 100 / 100.0; //产生0-1之间的随机数
		while (pick == 0) {
			pick = rand() % 100 / 100.0;
		}
		for (int j = 0; j < sizepop; j++) {
			pick -= pselect[j];
			if (pick < 0) {
				index.push_back(j);
				break;
			}
		}
	}

	/*for (int i = 0; i < index.size(); i++) {
		cout << index[i]<<" ";
	}*/
	for (int i = 0; i < index.size(); i++) {
		ret.chroms.push_back(individuals.chroms[index[i]]);
		ret.fitness.push_back(individuals.fitness[index[i]]);
		ret.concentration.push_back(individuals.concentration[index[i]]);
		ret.excellence.push_back(individuals.excellence[index[i]]);

	}
	return ret;
}

cross函数

#include<vector>
#include<set>
using namespace std;

//查看交叉后染色体是否合法
bool validate(vector<int> chrom) {
	set<int> s;
	for (vector<int>::iterator it = chrom.begin(); it != chrom.end(); it++) {
		s.insert(*it);
	}
	if (s.size() < chrom.size()) {
		return false;
	}
	return true;
}

vector<vector<int>> cross(double pcross, vector<vector<int>> chroms,int sizepop,int length) {
	for (int i = 0; i < sizepop; i++) {
		double pick = rand() % 101 / 100.0; //产生0-1间的随机数
		while (pick == 0) {
			pick = rand() % 101 / 100.0;
		}
		//判断是否交叉
		if (pick > pcross) {
			continue;         
		}
		int chrom_index1 = rand() % sizepop;  
		int chrom_index2 = rand() % sizepop; 
		while (chrom_index1 == chrom_index2) {
			chrom_index2 = rand() % sizepop;
		}

		//要交叉的个体
		vector<int> chrom1 = chroms[chrom_index1];
		vector<int> chrom2 = chroms[chrom_index2];

		//选择交叉的位置
		int pos = rand() % length;
		while (pos == 0) {                //不取下标0
			pos = rand() % length;
		}

		//交叉
		vector<int> temp;
		for (int i = pos; i < length; i++) {
			temp.push_back(chrom1[i]);
		}
		for (int i = pos; i < length; i++) {
			chrom1[i] = chrom2[i];
		}
		for (int i = pos; i < length; i++) {
			chrom2[i] = temp[i - pos];
		}
		temp.clear();

		if (validate(chrom1) || validate(chrom2)) {
			continue;
		}

		//结果放入chroms
		chroms[chrom_index1] = chrom1;
		chroms[chrom_index2] = chrom2;

	}

	return chroms;
}

mutate函数

#include<vector>
#include<set>
#include "mianyi.h"
using namespace std;
vector<vector<int>> mutate(double pmutation, vector<vector<int>> chroms, int sizepop,int length,int city_num) {
	//每一轮for循环中，可能会进行一次变异操作，染色体是随机选择的，变异位置也是随机选择的
	for (int i = 0; i < sizepop; i++) {
		double pick = rand() % 101 / 100.0; //产生0-1间的随机数
		while (pick == 0) {
			pick = rand() % 101 / 100.0;
		}
		//判断是否变异
		if (pick > pmutation) {
			continue;
		}
		//随机选择个体变异
		int chrom_index = rand() % sizepop;
		vector<int> chrom = chroms[chrom_index];
		//随机选择位置
		int pos = rand() % length;
		//变异
		chrom[pos] = rand() % city_num;
		//变异不能产生相同的城市,若存在，则再次同位置变异，直至不同
		set<int> s;
		for (vector<int>::iterator it=chrom.begin(); it != chrom.end(); it++) {
			s.insert(*it);
		}
		while (s.size() == length - 1) {
			chrom[pos] = rand() % city_num;
			for (vector<int>::iterator it = chrom.begin(); it != chrom.end(); it++) {
				s.insert(*it);
			}
		}
		chroms[chrom_index] = chrom;
	}
	return chroms;

}

incorporate函数

#include "mianyi.h"
population incorporate(population individuals, int sizepop, population bestindividuals, int overbest) {
	population newIndividual;
	int M = sizepop + overbest;
	for (int i = 0; i < sizepop; i++) {
		newIndividual.chroms.push_back(individuals.chroms[i]);
	}
	for (int i = sizepop; i < M; i++) {
		newIndividual.chroms.push_back(bestindividuals.chroms[i- sizepop]);
	}
	return newIndividual;

}