求解水库优化调度问题的动态规划-遗传算法

Optimization of reservoir operation by using dynamic programming-genetic algorithm

刘攀 郭生练 雒征 刘心愿

综合动态规划和遗传算法的优点，基于贝尔曼最优化原理将水库优化调度按阶段划分为若干多目标决策子问题，各子问题采用混合编码的多目标遗传算法求解，从而提出了一种求解水库优化调度问题的动态规划一遗传算法．该算法不仅在时间上通过划分阶段降维，而且采用遗传算法克服离散状态空间组合所产生的维数灾问题．从理论上论证了动态规划一遗传算法的全局收敛性，分析得出该算法的效率一般高于遗传算法；并经数值试验表明：在计算时段数较多时，动态规划一遗传算法显著优于遗传算法．因此，提出的动态规划一遗传算法为求解水库优化调度问题提供了新的思路与途径．[著者文摘]

Based on the Bellman＇ s optimality principle, a dynamic programming-genetic algorithm （DPGA） is proposed to optimize the reservoir operation. The reservoir optimal operation is partitioned into multi-stage problems based on the optimality principle, which can be optimized by using multi-objective GA respectively. The dimensions of both temporal and spatial could be reduced greatly; and the global convergence and efficiency of the DP-GA are analyzed theoretically. A Monte Carlo experiment is used to simulate and evaluate the proposed algorithm with the Qingjiang River cascade hydropower stations as case study. It is indicated that the DP-GA is valuable for the reservoir optimal operation, especially for the optimization of reservoir operation with many periods.[著者文摘]

一种应用于图着色问题的新型混合遗传算法

A application on new hybrid genetic algorithm for graph coloring

曹莉[1] 程灏[1] 许钟[2]

将遗传算法与模拟退火方法和禁忌搜索方法结合,提出了应用于图着色的混合遗传算法.在混合方法中,模拟退火算法用于局部寻优,提高算法的收敛速度,同时防止早熟收敛;禁忌搜索算法通过记忆能力防止进化过程出现循环来提高全局寻优能力.用遗传算法进行全局搜索,并与贪婪遗传算法和Dsatur算法进行了比较,结果表明,混合遗传算法的寻优质量优于对照算法.这种改进的混合遗传算法可以在稠密图上获得更好的寻优效率,在稀疏图上其效率则略有下降,这表明设计的改进混合遗传算法的合理性和有效性.[著者文摘]

Combined with SA and TS, a hybrid genetic algorithm for the graph coloring problem （GCP） is proposed. In a hybrid algorithm, SA is used to local-optimize, which can accelerate the optimization process and avoid the premature convergence; TS is used to improve the global-optimize, which prevent the repeat between the new individual and the old individual through its memory function; GA is used to global search. The comparison is carried on with the Greedy GA and the Dsatur, the result indicate that the computing precision of hybrid algorithm is better than the antitheses. Experiments show that the improved hybrid algorithm can get better computing speed on density graph, but slow down on sparse graph. These make it clear that the improved hybrid genetic algorithm is rational and effective.[著者文摘]

车辆路径问题的改进的双种群遗传算法

Improved genetic algorithm with double populations for vehicle routing problem

曾凡超 朱征宇 邓欣 何兴无

提出了一种基于车辆路径问题的改进双种群遗传算法。该改进双种群遗传算法主要通过两个种群同时进行进化操作,并结合新交叉算子和种群交叉策略,以克服传统双种群遗传算法在求解车辆路径问题上所存在的不足。通过仿真实验,将改进的双种群遗传算法与其它几种遗传算法进行比较,改进的双种群遗传算法比其它几种遗传算法显著提高了优化效果。实验结果表明,该算法可以有效求得该问题的优化解,是解决车辆路径问题的好方法。[著者文摘]

An improved genetic algorithm with double populations to address the classical capacitated vehicle routing problem （VRP） is proposed. The basic scheme consists in concurrently evolving two populations of solutions to avoid the disadvantages in common double populations genetic algorithm using new crossover operators combining new strategy for the crossover between populations. According to computational experiment result, the improved double populations algorithm can improve the optimized effect of the VRP obviously in comparison with other genetic algorithms. Experimental results demonstrate the proposed algorithm can find the optimal or near optimal solution to the vehicle routing problem effectively.[著者文摘]

基于遗传算法的高精度GPS相对定位解算研究

On Precise GPS Relative Positioning of Carrier Phase Based on Genetic Algorithms

刘智敏[1] 李知峰[2] 蒙映[3]

在高精度GPS相对定位中，初始模糊度的确定足保证高精度、快速定位的关键。依据遗传算法（GA）的稳健、并行和简单通用等特点，基于遗传算法的相对定位解算问题具有现实意义。基于改进的遗传编码和算法，建立同步实现相对定位坐标向量和模糊度的解算模型和流程，并通过实测数据的算例，对所提出算法的可靠性、搜索效率进行论证。[著者文摘]

一种求解有约束优化问题的遗传算法

A Mixed Genetic Algorithm for Solving Constraint Optimization Problems

王丽敏

遗传算法是模拟生物进化机制新发展起来的一种搜索和优化方法，它是基于自然进化机制并且在寻找目标函数或在目标函数附近解决优化问题。遗传算法已在有约束优化问题领域得到应用，并显示出良好的发展前景。本文介绍了一种有约束优化问题的混合遗传算法，并通过实例验证了此方法是可行的和有效的。[著者文摘]

Genetic Algorithms are such search and optimization methods, which have recently developed to stimulate the mechanism of natural evolution.Those methods are based on those of natural evolution, and are powerful in finding the. global or near global optimal solution of optimization problems.It has been used in constraint optimization problems solving and found to be of great use. This paper introduces a mix genetic algorithm for solving constraint optimization problems.and illustrates is feasible and valid.[著者文摘]