云运营商效益最优的资源分配机制与算法(2)
图1 云环境
2.2算法的数学模型
实际问题的优化目标是用数学描述，通常是若干优化目标的和式。本文的数学模式是所有机器序列的排列数的每一台机器分别调用背包算法，得到结果的总和(也就是总利益)，即∑cn=c1+c2+c3……+c20。其中ci等于每台计算机的用户应付费用(f)减去计算机运行成本(b)，即ci= f- b。其中运行成本是计算机计算能力(j)的百分之一，即f=0.01*j；而应付费用则是所需计算能力(z)的9倍，即b=z*9。所以也可以表示成ci= z*9- 0.01*j。在解的空间内，利用随机排列数生成函数，反复调用背包算法，计算每次的总利益，并与上一最大利益结果比较，保留最优结果。并通过大量实验总结，在大多数情况下，函数迭代300到700次就会收敛，而且解的质量较高，或是真正的最优解或是十分接近最优解。
3云运营商效益最优的资源分配机制与算法
3.1本文算法的简介
云运营商要获得最优效益就要合理安排用户任务到每台计算机上，如果只是一台计算机，用背包算法就可以获得最优解。但在云环境下计算机的数目是非常多的，如果用背包算法依次让计算机在用户任务集合中挑选，得到的结果只是是局部最优效益。要得到最优效益可以让所有机器序列的排列数依次调用背包算法，即把所有计算机可能选择的顺序都进行一次背包选择，得到的结果肯定是最优解。但是这样付出的计算时间和计算能力是云运营商不可以接受的，例如20的全排列依次调用背包算法，即使在云环境下计算不成问题，但是耗费的计算能力的成本是巨大的。所以，考虑用一种智能的算法获得近似的最优解，本文针对实际改进了的模拟退火算法和背包算法结合解决云环境下运营商要获得最大利润的问题。
3.2算法的解空间
云运营商效益最优的解的空间即：全部计算机序列全排列的排列数依次调用背包算法获得的利润值，如何有效在这个解空间里高效选择出最优解是关键。分析5的全排列：12345、13245、12435、14523、53241等，可以发现前三个排列数相差不大，最后调用背包算法的结果一般是相等，也就是说在所有解空间里有很多排列数的结果值是相等的，所以尽量避免重复在这样的解的邻域内搜索。然而后三个的排列数相差很大，最后目标函数的结果相差较大，是我们想搜索的解系。如何才能找到我们想要的解呢？借鉴模拟退货算法和遗传算法的在解空间搜索最优解的方法，本文提出一种随机产生一个排列数的方法，实验表明每个排列数相差较大，可以保证每次迭代产生的新解是算法需要的，而且一般迭代300到700次所有优质解都可以涵盖。
3.3新解的产生
如何产生符合要求的新解是本文的关键，也就是如何产生排列顺序相差较大的排列数。本文编程了一个随机函数完成次要求，主要是利用srand()函数用当前时间初始化，使每次得出的数列相差较大，再结合rand()函数随机赋值函数编程出了一个可以产生相差较大的机器数序的排列数函数，避免算法陷入局部最优解，而提高了最终解质量，并加快算法的收敛。
3.4算法的目标函数
算法的目标函数∑cn=c1+c2+c3……+c20。其中ci= f-b（每台云计算机的用户应付费用f减去计算机运行成本b）。运行成本是f=0.01*j（计算机的计算能力的百分之一）；应付费用是b=z*9（需求计算能力z的9倍）。用cn和上代结果比较，保留质量较优的结果。
3.5算法分析
如果按云环境下所有计算机序数的全排列的每个排列数依次执行背包算法，得到的结果一定是最高效益。但是云环境下的计算机数目是非常多的，即使云环境下能快速完成这样的计算量，但所耗费的计算能力是不可以接受的。