摘要
为了解决优化和约束推理,基于向导遗传算法(GGA)和分布式向导遗传算法(DGGA),通过引入向导概率Pguid、本地优化监测LOD和权ε共3个新参数,提出了一种D3G2A算法的改进算法。该算法采用多代理方法,不仅使搜索过程多样化,避免出现局部最优,而且代理能计算各自的遗传参数。将改进的D3G2A和GGA用于随机生成的二元CSPs,实验表明,D3G2A能有效改善适应度值和节省CPU时间开销,使算法的性能得到提高。
A Dynamic Distributed Double Guided Genetic Algorithm (D^3 G^2A) is a new multi-agent approach which leads to additive constraint satisfaction problem. This approach is inspired by the guided genetic algorithm (GGA) and by the dynamic distributed double guided genetic algorithm for Max_CSPs. It consists of agents dynamically created and cooperating in order to solve problem with each agent performing its own GA. Firstly, our approach is enhanced by three parameters, guidance probability (Pguid), local optima detector( LOD), weight (6), which allow not only diversification but also escaping from local optima. Secondly, the GGAs performed agents will no longer be the same. This is stirred by the natural laws. In fact, our approach will let the agents able to count their own GA parameters. In order to show D^3G^2A advantages, the approach and the GGA are applied to the randomly generated binary constraints satisfaction problems. Compared with the centralized guided genetic algorithm and applied to a set of literature known problems, our new approaches have been experimentally shown to be always better in terms of fitness values and CPU time.
出处
《重庆师范大学学报(自然科学版)》
CAS
2009年第2期94-98,共5页
Journal of Chongqing Normal University:Natural Science
基金
重庆市教委科技计划(No.KJ081109)
重庆三峡学院青年资助项目(No.2006-sxxyqingnian-01)
关键词
优化
约束推理
动态分布式
双向导
遗传算法
optimization
constraint reasoning
dynamic distribution
double guided
genetic algorithm