#include "pso_mt.h"
PSO_MT::PSO_MT()
{
}
PSO_MT::PSO_MT(uint pop_size, uint maxItems)
{
this->pop_size = pop_size;
this->maxItems = maxItems;
}
/*
* @projectName PSO_multi_target
* @brief 初始化粒子群位置、速度,并计算粒子群初始的适应值信息(多个适应值)
* @param
* param name:
* @return
* @author TJT
* @date 2024-05-09
*/
void PSO_MT::initPopulation()
{
std::time_t now = std::time(nullptr);
std::tm* cur_tm = std::localtime(&now);
int seed = cur_tm->tm_hour * 3600 + cur_tm->tm_min * 60 + cur_tm->tm_sec;
std::default_random_engine dre(seed);
// 产生1~4的随机整数,表示从当前类种挑选一个物品
std::uniform_int_distribution<int> uid(1, 4);
for(uint i = 0; i < pop_size; i++)
{
vector<int> cur_solution;
for(uint j = 0; j < dim; j++)
{
cur_solution.push_back(uid(dre));
}
// 计算当前解的各个适应值,包括价值、体积、重量
auto fitness_res = fitness(cur_solution);
Particle pcle;
pcle.solution = cur_solution;
pcle.speed = vector<double>(dim, 0.0); // 初速度置为0
pcle.value = get<0>(fitness_res);
pcle.volume = get<1>(fitness_res);
pcle.weight = get<2>(fitness_res);
// 将当前粒子加入粒子群
groups.push_back(pcle);
}
// 初始化时的个体最优即为当前种群的所有个体
pbest_groups = groups;
}
/*
* @projectName PSO_multi_target
* @brief 初始化非劣解集,并随机选择一个粒子作为全局最优粒子
* @param
* param name:
* @return
* @author TJT
* @date 2024-05-09
*/
void PSO_MT::initParetoOptimalSet()
{
for(uint i = 0; i < pop_size; ++i)
{
bool flag = false;
// 判断i粒子是否被其它粒子支配,否则i粒子为支配粒子,选为非劣解
Particle p1 = groups.at(i);
for(uint j = 0; j < pop_size; ++j)
{
if(i == j)
{
continue;
}
Particle p2 = groups.at(j);
// 判断粒子p2是否支配粒子p1
flag =isDominateParticle(p2, p1);
if(flag)
{
flag = true;
break;
}
}
if(flag)
{
continue;
}
pareto_optimal_set.push_back(p1);
}
// 随机选择一个全局最优粒子
if(!pareto_optimal_set.empty())
{
selectBestByRandom();
}else{
gbest_particle = groups.at(0);
}
}
/*
* @projectName PSO_multi_target
* @brief 粒子群算法主入口
* @param
* param name:
* @return
* @author TJT
* @date 2024-05-10
*/
void PSO_MT::pso()
{
initPopulation();
initParetoOptimalSet();
for(uint k = 0; k < maxItems; k++)
{
updatePosAndSpeed(k);
mergeParetoOptimalSet();
selectBestByRandom();
}
printBestParticle("best solution:", gbest_particle);
}
/*
* @projectName PSO_multi_target
* @brief 更新粒子群的位置和速度
* @param
* k:迭代次数
* @return
* @author TJT
* @date 2024-05-10
*/
void PSO_MT::updatePosAndSpeed(const uint k)
{
std::time_t now = std::time(nullptr);
std::tm* cur_tm = std::localtime(&now);
int seed = cur_tm->tm_hour * 3600 + cur_tm->tm_min * 60 + cur_tm->tm_sec;
std::default_random_engine dre(seed);
// 产生1~4的随机整数,表示从当前类种挑选一个物品
std::uniform_real_distribution<double> ure;
std::uniform_int_distribution<int> uid(1, 4);
double w_value = wmax - (wmax - wmin) * pow(k * 1.0 / maxItems, 2.0);
for(uint i = 0; i < pop_size; ++i)
{
bool is_beyond_bound = false;
// 取出当前粒子的位置和速度信息
vector<int> pcle_solution = groups.at(i).solution;
vector<double> p_speed = groups.at(i).speed;
// 粒子移动后的位置信息
vector<int> pcle_new_solution(dim, 0);
// 更新速度和位置
for(uint j = 0; j < dim; ++j)
{
double p_speed_j = p_speed.at(j);
double p_pos_j = pcle_solution.at(j);
double pbest_pos_j = pbest_groups.at(i).solution.at(j); // 个体最优粒子的位置信息
double gbest_pos_j = gbest_particle.solution.at(j);
double p_speed1_j = w_value * p_speed_j + c1 * ure(dre) * (pbest_pos_j - p_pos_j) +
c2 * ure(dre) * (gbest_pos_j - p_pos_j);
p_speed.at(j) = p_speed1_j;
double cur_pos = p_pos_j + p_speed1_j;
if(cur_pos <= eps || cur_pos > 4.0)
{
is_beyond_bound = true;
break;
}
pcle_new_solution.at(j) = static_cast<int>(ceil(cur_pos)) ;
}
// 如果存在越界情况,则新解随机生成
if(is_beyond_bound)
{
for(uint j = 0; j < dim; ++j)
{
pcle_new_solution.at(j) = uid(dre);
}
}
// 移动后的粒子
Particle moved_pcle;
auto moved_pcle_fitness = fitness(pcle_new_solution);
moved_pcle.value = get<0>(moved_pcle_fitness);
moved_pcle.volume = get<1>(moved_pcle_fitness);
moved_pcle.weight = get<2>(moved_pcle_fitness);
moved_pcle.solution = pcle_new_solution;
moved_pcle.speed = p_speed;
// 粒子i的历史个体最优粒子
Particle pbest_pcle = pbest_groups.at(i);
// 历史个体最优粒子支配新粒子,不作操作
if(isDominateParticle(pbest_pcle, moved_pcle))
{
}
// 新粒子支配历史个体最优粒子
else if(isDominateParticle(moved_pcle, pbest_pcle))
{
pbest_groups.at(i) = moved_pcle;
}
// 两者互不支配
else{
if(ure(dre) > 0.5)
{
pbest_groups.at(i) = moved_pcle;
}
}
groups.at(i) = moved_pcle;
}
}
/*
* @projectName PSO_multi_target
* @brief 判断粒子pa是否支配粒子pb
* 判断依据:
* 粒子pb较粒子pa价值小且体积大;粒子pb较粒子pa价值相同但体积大;粒子pb较粒子pa体积相同但价值小
* 粒子pb重量超标
* @param
* param name:
* @return
* @author TJT
* @date 2024-05-10
*/
bool PSO_MT::isDominateParticle(const Particle &pa, const Particle &pb)
{
// 满足下面条件,说明粒子pa支配粒子pb
if(pb.weight > limit_weight || (pa.value > pb.value && pa.volume < pb.volume) ||
(abs(pa.value - pb.value) < eps && pa.volume < pb.volume)
|| (abs(pa.volume - pb.volume) < eps && pa.value > pb.value))
{
return true;
}
return false;
}
/*
* @projectName PSO_multi_target
* @brief 合并非劣解集:将个体最优集和上代的非劣解集合并
* @param
* param name:
* @return
* @author TJT
* @date 2024-05-10
*/
void PSO_MT::mergeParetoOptimalSet()
{
vector<Particle> merged_set;
// merged_set.resize(pareto_optimal_set.size() + pbest_groups.size());
// error: no match for 'operator<' (operand types are 'Particle' and 'Particle')
// merge(pbest_groups.begin(), pbest_groups.end(),
// pareto_optimal_set.begin(), pareto_optimal_set.end(), merged_set.begin());
move(pbest_groups.cbegin(), pbest_groups.cend(), back_inserter(merged_set));
move(pareto_optimal_set.cbegin(), pareto_optimal_set.cend(), back_inserter(merged_set));
// 筛选并去重非劣解集
updateParetoOptimalSet(merged_set);
}
/*
* @projectName PSO