云运营商效益最优的资源分配机制与算法(3)
如何在这样庞大的解空间中选择并逐步靠近最优解呢？模拟退火算法是取一个较高的温度，在逐步降温过程中基本靠近最优解的邻域即在解空间的邻域下搜索，但对本文问题是不适合，因为在一个局部解的领域搜索一般得到的结果是一样的，这样很容易使最终的结果是局部最优解。例如在12345的邻域（13245、12435、12354）搜索是重复无意义的，会大大加大算法的运行空间。
遗传算法是在解空间中通过交叉和变异产生新解，通过适应函数选择，但是这样可能陷入局部最优解，可以通过变异和轮盘算法跳出局部最优解。但是用遗传算法解决本问题，遇到像（13245、12435、12354）这样相差不大排列数的邻域时候得到的解已经开始收敛，很容易误判成最优解。所以本文从问题解的空间分析，存在排列数相近和要不少计算机的计算能力和能耗一致的情况，在解的空间进行搜索的时候，尽量避免重复搜索这样的相同解和近似解。参照遗传算法尽量在更广的解空间中搜索最优解，本文模仿自然界随机产生排列数的方法，达到和遗传算法的交叉变异于轮盘算法的结合产生的搜索效果。
大量仿真实验结果表明：重复执行300到500次的随机排列数的背包选择，算法都可以快速收敛，并且最终使到云环境下运营商的效益最优或者接近最优。
3.6算法总体流程
实验算法过程如下：
1. 初始化20台计算机的计算能力、100个客户需要的计算能力，并计算应付费用，和计算机的运行成本。
2. 调用sj()随机函数产生一个20台机器的随机排列序列，供实验的选择操作。
3. 以随机产生的20台机器的排列序列进行背包选择，求得20台计算机从所有客户选择接受任何中获得的利润。
4. 比较当前结果和上次结果的大小，当前结果大于上次结果则保留当前结果，反之保留上次结果。
5. 重复以上2、3、4、5过程400次。
4实验及仿真
4.1仿真环境介绍及主要参数介绍
实验的操作系统为Win7 旗舰版，内存为2GB，处理器型号是酷睿I3，处理器频率为2.53GHz，磁盘容量500GB。采用Dev-C++编译器，编程语言C++。仿真实例是100个客户及20台云环境下的计算机，随机给100个用户赋予需求的计算能力、20台机器的计算能力。实验1（结果如图3）主要是研究本文BB算法与遗传算法随着迭代次数的增加，那种算法更最接近最优解和谁更快收敛。实验2（结果如图4）主要研究随着计算机数目的增加，QB算法（即使用计算机数的全排列依次调用背包算法）与本文BB算法的运行时间的比较。实验3（结果如图5）主要是研究随着计算机数目的增加，YB算法（即随机用一个排列数调用背包算法）与本文BB算法得到解的质量的比较，每次增加一台计算机。
4.2仿真结果分析
图3 本文算法与遗传算法对比图
通过分析图3结果，我们可以知道：开始的时候BB算法因为迭代次数少而产生的新解少，而且新解是随机产生的，有时会获得比遗传算法（GA）更好的解，有时则比遗传算法差。但只要随着迭代次数的增加，BB算法会比遗传算法更快的收敛，且解的质量和遗传算法持平。GA 算法随着迭代次数的增加，能逐渐靠近最优解，但是如果变异操作和交叉操作控制不好，很容易陷入局部最优解。BB算法简单更易于文护改进，而且收敛速度更快，在300到700次迭代后，都能得到高质量的解。