摘要
当前在解决资源优化配置问题时往往使用贪婪算法、遗传算法等。但贪婪算法只能选择一个最优度量标准,所以只能获得度量意义下的最优解而不是该问题的最优解,而如果直接使用遗传算法又存在搜索空间过大、耗时过长的问题。提出了一种新的算法。先基于贪婪算法获得问题的初始解空间,然后对初始解空间进行冲突检测与消解,最后运用改进的遗传算法进行优化获得最优方案。测试算例表明大大缩小了遗传算法的搜索空间,在保证获得最优解的条件下加快了收敛速度并有效防止了种群的退化。提出的算法在突发事务的处理方面具有一定的意义。
To solve resource scheduling problem, usually the greed algorithm, genetic algorithm etc are used. But greed algorithm cannot guarantee to get the best solution. As to genetic algorithm, if being used directly, it will search a large solution space inefficiently, so the best solution can not be got rapidly. A new method is proposed in this thesis. Firstly, the possible solutions based on greed algorithm can be got. Then the candidate solutions can be obtained after detecting all the conflicts and resolving them. At last, by using the improved genetic algorithm, the best solution for the problem willl be gained. It is indicated that this method can reduce the research space, get the best solution rapidly and can prevent the degeneration of the population efficiently. This method plays an important role in dealing with exceptional tasks.
出处
《计算机仿真》
CSCD
2008年第6期173-176,共4页
Computer Simulation
关键词
资源优化配置
贪婪算法
遗传算法
改进遗传算法
Resource scheduling problem
Greed algorithm
Genetic algorithm
Improved genetic algorithm
