如何在这样庞大的解空间中选择并逐步靠近最优解呢?模拟退火算法是取一个较高的温度,在逐步降温过程中基本靠近最优解的邻域即在解空间的邻域下搜索,但对本文问题是不适合,因为在一个局部解的领域搜索一般得到的结果是一样的,这样很容易使最终的结果是局部最优解。例如在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次迭代后,都能得到高质量的解。
上一篇:缓存和页面静态化的网站性能优化方法研究
下一篇:ASP.net高校图书馆自习室座位预约系统的设计与实现

电子商务发展趋势和企业...

电子商务云服务商业模式创新研究【4721字】

电信运营商发展电子商务...

大数据时代物联网和云计...

创新电子商务應用 提高社...

云计算”环境下电子商务...

云技术的密集人群安全预警系统设计

承德市事业单位档案管理...

公寓空调设计任务书

AT89C52单片机的超声波测距...

志愿者活动的调查问卷表

神经外科重症监护病房患...

医院财务风险因素分析及管理措施【2367字】

10万元能开儿童乐园吗,我...

中国学术生态细节考察《...

C#学校科研管理系统的设计

国内外图像分割技术研究现状