模拟退火算法案例
2018年的华为软件精英挑战赛题目简介：给出华为云虚拟机过去的租借数量历史数据，用以训练模型并预测下一个时间段里的虚拟机租借数量，然后把这些预测得到的虚拟机装填进一定规格的物理机中，即分为预测和装填两个部分。
总结一下装填部分使用的模拟退火算法：
算法原理
装填的基础算法是FF（首次适应算法），而虚拟机的序列会影响FF算法的装填效果。比较明显的是FFD把序列降序之后再使用FF算法往往效果更好。而模拟退火算法目的就是获得一个较好的序列。
模拟退火的基本原理就是设置一个初始温度、一个最低温度，一个降温速率。例如初始温度取100，最低温度取1，降温速率取0.9 。则温度迭代从100开始，每次迭代都使当前温度变为0.9T，直至到达1为止。
每次迭代都随机交换虚拟机序列中的任意两个元素，然后用这个序列进行FF装填，得到一个评判分数J_cur，而设当前记录的最优分数为J_min（评判分数=目前使用物理机数-1+最后一个物理机的资源占有率，因此分数越低越好）。设dE=J_cur-J_min,
如果dE<=0，即当前分数更小，装填效果更好，则接受这个序列
如果dE>0，即当前分数更大，装填效果更差，则按一定几率接受这个序列
这个几率的公式为：
是一个负数，随着T的降低，
减小，则exp(
)也减小。
就是说温度越低，接受这个不合格的序列的可能性越低。这样的目的是让迭代前期接受更多不合格序列以期脱离局部最优，而迭代后期接受更少不合格序列以得到最优方案。
每次迭代都设一个0到1之间的随机数rand，用以跟P对比，如果P>rand，则接受这个方案。
迭代初期，由于T比较大，P趋近于1，因此很大概率会接收这个不合格方案，而迭代后期T比较小，P趋近于0，因此很大概率不接受这个方案。
如下图，蓝线为P、橙线为rand、灰线为P-rand。
可见随着迭代次数的增加，灰线会慢慢的变得小于0
而上图其实并不严格遵循公式，如果严格遵循，则效果如下：
可见P一直都很大，这样无论迭代多少次，都会一律接受这些不合格的方案，也就相当于随机序列了。原因是dE这个数值太小了，无论T怎么变化都没有用，所以我加了一个参数进去：
，k取50，然后效果就比较好了。
实际应用
单独摘出装填部分，则需要一个原始的虚拟机序列和一些基本参数。我都设置好了：
15种虚拟机规格为：
flavor1 1 1024
flavor2 1 2048
flavor3 1 4096
flavor4 2 2048
flavor5 2 4096
flavor6 2 8192
flavor7 4 4096
flavor8 4 8192
flavor9 4 16384
flavor10 8 8192
flavor11 8 16384
flavor12 8 32768
flavor13 16 16384
flavor14 16 32768
flavor15 16 65536
备注：flavor名称 CPU核数 内存大小（MB）
且要求预测全部15种虚拟机的数量
物理机规格为56核CPU、128G内存
需要优化的资源维度为CPU
则预测效果为：
可见按FF算法和BFD算法装填需要17台物理机
而模拟退火算法只需要15台物理机
代码
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <set>
#include <vector>
#include <ctime>
#include <sstream>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <fstream>
using namespace std;
int FlavorCPU[20]={0,1,1,1,2,2,2,4,4,4,8,8,8,16,16,16}; //15种型号虚拟机的CPU规格 单位为核
int FlavorMEM[20]={0,1,2,4,2,4,8,4,8,16,8,16,32,16,32,64};//15种型号虚拟机的内存规格 单位为G
int PredictRes[20]={0,30,18,4,14,34,2,6,36,14,4,20,12,2,6,2};//下一个时间段的虚拟机预测结果
int vir_cnt=15; //需要预测的虚拟机种类数量
int ChosenType[20];//被选中要预测的虚拟机种类
int phy_cpu=56,phy_memory=128;//物理机的统一规格为56核CPU、128G内存
string task="CPU"; //任务是使CPU资源占用率最小
struct PhyMachine//一台物理机
{
int RemainingCPU,RemainingMEM;//剩余资源量
int VirItem[20];//VirItem[i]代表这台物理机中装载的种类i虚拟机的数量
PhyMachine(){
for(int i=0;i<20;i++) VirItem[i]=0;
RemainingCPU=phy_cpu;
RemainingMEM=phy_memory;
}
};
class InstallCases//一个装填样例
{
public :
vector<PhyMachine> phymachine;//这种装填方法总共要用多少台物理机
vector<int> flavors; //待安装的虚拟机序列
double point; //对此装填样例优劣的评判分数，分数越低、效果越好
void Install() //用FF方法按虚拟机序列顺序安装虚拟机
{
PhyMachine p;
phymachine.push_back(p);//先塞一个空的物理机进去
for(int i=0;i<(int)flavors.size();i++)
{
int flavortype=flavors[i];
bool flag_enough=false;
for(int j=0;j<(int)phymachine.size();j++)
{
if(phymachine[j].RemainingCPU>=FlavorCPU[flavortype]&&phymachine[j].RemainingMEM>=FlavorMEM[flavortype])
{
phymachine[j].RemainingCPU-=FlavorCPU[flavortype];
phymachine[j].RemainingMEM-=FlavorMEM[flavortype];
phymachine[j].VirItem[flavortype]++;
flag_enough=true;
break;
}
}
if(flag_enough==false){//说明物理机不够用，新开一个物理机
PhyMachine p;
p.RemainingCPU-=FlavorCPU[flavortype];
p.RemainingMEM-=FlavorMEM[flavortype];
p.VirItem[flavortype]++;
phymachine.push_back(p);
}
}
}
double J()//计算当前这个装填方式的分数point，分数越低越好
{
//分数=（目前物理机数-1） +最后一个物理机的资源占用率
point=(double)(phymachine.size()-1);
if(task=="CPU"){
double freecpu=(double)phy_cpu-(double)phymachine[phymachine.size()-1].RemainingCPU;
point+=freecpu/(double)phy_cpu;
}
else if(task=="MEM"){
double freemem=(double)phy_memory-(double)phymachine[phymachine.size()-1].RemainingMEM;
point+=freemem/(double)phy_memory;
}
return point;
}
};
vector<InstallCases> Cases;//存储不同的装填方式
void Install()
{
double T=100.0,T_min=1,r=0.995;//分别是起始温度、停止温度 、温度下降速率
double J_min,J_cur,dE; //分别是目前最好的分数、当前安装样例的分数 、前面两者的差值
//首先要把PredictRes这个数组里的东西展开转换成虚拟机序列
vector<int> vi_flavors;
for(int i=0;i<vir_cnt;i++){
int flavortype=ChosenType[i];//需要预测的虚拟机种类
int flavornum=PredictRes[flavortype];//当前需要预测的虚拟机的租借数
while(flavornum--){
vi_flavors.push_back(flavortype);
}
}
cout<<"原始虚拟机序列:\n";
for(int i=0;i<(int)vi_flavors.size();i++) cout<<vi_flavors[i]<<" ";
cout<<endl;
vector<int> dice;
for(int i=0;i<(int)vi_flavors.size();i++){
dice.push_back(i);
}
InstallCases Case0;//原始装填案例，相当于直接FF装填
Case0.flavors=vi_flavors;
Case0.Install();
J_min=Case0.J();
cout<<"按原始虚拟机序列装填所得分数："<<J_min<<endl;
Cases.push_back(Case0); //把这个装填方法push进向量里保存起来
srand( (unsigned)time( NULL ));
int temcnt0=0,temcnt1=0;//分别是 得到更差的序列的次数和接受更差序列的次数
ofstream fout("T.csv");
while(T>T_min)
{
random_shuffle(dice.begin(),dice.end());//随机打乱这个骰子向量里的元素顺序
vector<int> new_vi_flavors=vi_flavors;
swap(new_vi_flavors[dice[0]],new_vi_flavors[dice[1]]);//随机交换虚拟机序列中的两个虚拟机的位置
// for(int i=0;i<vi_flavors.size();i++) cout<<new_vi_flavors[i]<<" ";
// cout<<endl;
//按当前虚拟机序列装填：
InstallCases Case;
Case.flavors=new_vi_flavors;
Case.Install();
J_cur=Case.J(); //当前装填方式的得分
dE=J_cur-J_min; //与最低分数之间的差值
if(dE<=0){ //J_cur<=J_min,即如果移动后J_cur分数更低得到更优解，则总是接受移动
vi_flavors=new_vi_flavors;//下一次循环会以这个数组为基础进行随机变化
Cases.push_back(Case) ;
J_min=J_cur;
}
else{//这里才是模拟退火的精华，会进来这里说明dE<0，即 0<exp(dE/T)<1
temcnt0++;
double random_num=rand()/(double)(RAND_MAX);
fout<<exp(-50*dE/T)<<','<<random_num<<','<<exp(-50*dE/T)-random_num<<endl;
if ( exp(-50*dE/T) > random_num ){//T越大 (dE/T)越接近1，就越有可能接受这个方案
temcnt1++;
vi_flavors=new_vi_flavors;//下一次循环会以这个数组为基础进行随机变化
Cases.push_back(Case) ;
J_min=J_cur;
}
}
T=r*T;//降温
}
cout<<"得到更差的序列的次数："<<temcnt0<<endl;
cout<<"接受更差序列的次数："<<temcnt1<<endl;
fout.close();
}
bool cmp_cpu(int a,int b)
{
return (FlavorCPU[a]>FlavorCPU[b]);
}
bool cmp_mem(int a,int b)
{
return (FlavorMEM[a]>FlavorMEM[b]);
}
int BFD()
{
if(task=="CPU") sort(ChosenType,ChosenType+vir_cnt,cmp_cpu);
else if(task=="MEM") sort(ChosenType,ChosenType+vir_cnt,cmp_mem);
InstallCases Casebfd;
PhyMachine p;
Casebfd.phymachine.push_back(p);//先放一个空物理机进去
for(int i=0;i<vir_cnt;i++){
int temflavor=ChosenType[i];//需要预测的虚拟机种类
int temnum=PredictRes[temflavor];//当前需要预测的虚拟机的租借数
while(temnum--)
{
bool flag=false;//现有的物理机是否够用
int minspace_index=0;
bool first=true;
for(int k=0;k<(int)Casebfd.phymachine.size();k++)//遍历已有的所有物理机
{
if(Casebfd.phymachine[k].RemainingCPU>=FlavorCPU[temflavor]&&Casebfd.phymachine[k].RemainingMEM>=FlavorMEM[temflavor])
{
if(first==true){
minspace_index=k;
first=false;
}
else if(task=="CPU"&&Casebfd.phymachine[k].RemainingCPU<Casebfd.phymachine[minspace_index].RemainingCPU)
minspace_index=k;
else if(task=="MEM"&&Casebfd.phymachine[k].RemainingMEM<Casebfd.phymachine[minspace_index].RemainingMEM)
minspace_index=k;
flag=true;
}
}
if(flag==true)//现在要放进空闲空间最小的箱子中
{
Casebfd.phymachine[minspace_index].RemainingCPU-=FlavorCPU[temflavor];
Casebfd.phymachine[minspace_index].RemainingMEM-=FlavorMEM[temflavor];
Casebfd.phymachine[minspace_index].VirItem[temflavor]++;
}
if(flag==false)//物理机不够用
{
PhyMachine p;
Casebfd.phymachine.push_back(p);
int phycnt=Casebfd.phymachine.size();
Casebfd.phymachine[phycnt-1].RemainingCPU-=FlavorCPU[temflavor];
Casebfd.phymachine[phycnt-1].RemainingMEM-=FlavorMEM[temflavor];
Casebfd.phymachine[phycnt-1].VirItem[temflavor]++;
}
}
}
cout<<"使用BFD方法所需物理机数"<<Casebfd.phymachine.size()<<endl;
Casebfd.point=Casebfd.phymachine.size();
Cases.push_back(Casebfd) ;
}
int FindBestCase()
{
BFD(); //试一下BFD放置算法并push进Case中保存，用于对比体现模拟退火算法的效果
cout<<"Cases.size"<<Cases.size()<<endl;
double min_point=100000.0;
int min_index=0;
for(int i=0;i<(int)Cases.size();i++)
{
if(Cases[i].point<=min_point){
min_point=Cases[i].point;
min_index=i;
}
}
cout<<"最佳分数"<< setprecision(5)<<min_point<<endl;
cout<<"最佳装填样例索引="<<min_index<<endl;
cout<<"最佳虚拟机序列：\n";
for(int i=0;i<(int)Cases[min_index].flavors.size();i++){
cout<<Cases[min_index].flavors[i]<<" ";
}
cout<<endl;
return min_index;
}
int main()
{
for(int i=0;i<vir_cnt;i++){//设定为15种虚拟机规格都要预测
ChosenType[i]=i+1;
}
Install();//开始装填
FindBestCase();//在所有装填案例中寻找最佳案例
}
--------------------- 本文来自 weixin_41519463 的**** 博客 ，全文地址请点击：https://blog.****.net/weixin_41519463/article/details/79951962?utm_source=copy