弹性约束CSP及其基于遗传算法的交互式求解Agent

中国管理科学 ›› 2005, Vol. ›› Issue (3): 56-61.

弹性约束CSP及其基于遗传算法的交互式求解Agent

杜少甫, 梁樑, 余雁

中国科学技术大学管理学院, 安徽, 合肥, 230026

收稿日期:2004-12-07 修回日期:2005-05-31 出版日期:2005-06-28 发布日期:2012-03-07
基金资助:
国家自然科学基金资助项目(70371023);国家教育博士点基金(20030358052)

Elastic CSP and Its GA-Based Interactive Solving Agent

DU Shao-Fu, LIANG Liang, YU Yan

School of Management, University of Science and Technology of China, Hefei230026, China

Received:2004-12-07 Revised:2005-05-31 Online:2005-06-28 Published:2012-03-07

摘要/Abstract

摘要： 本文在回顾了约束满足问题(CSP)及其演进优化算法的基础上,提出了弹性约束CSP模型(ECSP),并将该模型形式化为六元组。ECSP模型是对已有的PCSP模型的改进。为了寻求ECSP问题的决策满意解,我们还设计了集成多Ageng、GA优化以及分布式并行计算技术的一种交互式多Ageng体系。我们详细阐述了其中的GA求解器算法,包括适应函数的确定、编码方式的选择、算子定义以及初始种群定义等。最后,我们用一个简单的算例证明了方法的有效性。

关键词: 弹性约束满足问题(ECSP), 决策满意解, Ageng, 遗传算法(GA)

Abstract: Constraint satisfaction problems (CSP) and the relevant evolutionary algorithms are reviewed first.Then we introduce a new CSP paradigm,elastic CSP model(ECSP),which is the improvement on the existing partial CSP model.We formularize ECSP as 6-tuple .For the purpose of finding the satisfactory solution(s) for decision,an interactive multi-agent architecture is designed,which integrates several technologies including multi-agent,genetic algorithm and distributed parallel computing.Furthermore,we elaborate the GA solver algorithm in the solving agent.How to determine the adaptive function?Which encoding method is chosen?How to define GA operators and initial population?Finally,we give a simple example to demonstrate the validity of our approach.

Key words: elastic constraint satisfaction problem(ECSP), satisfactory solution for decision, agent, genetic algorthm(GA)

中图分类号:

F830

杜少甫, 梁樑, 余雁. 弹性约束CSP及其基于遗传算法的交互式求解Agent[J]. 中国管理科学, 2005, (3): 56-61.

DU Shao-Fu, LIANG Liang, YU Yan. Elastic CSP and Its GA-Based Interactive Solving Agent[J]. Chinese Journal of Management Science, 2005, (3): 56-61.

参考文献

[1] A.K.Mackworth.The logic of constraint satisfaction[J]. Artifical Int elligence, 1992,58(1-3):3-20.
[2] M.Yokoo,E.H.Durfee, and K.Kuwabara.The Distributed Constraint Satisfaction Problem:Formalization and Algorithms[J].IEEE Transactions on Knowledge and Data Engineering, 1998,10(5):673-685.
[3] E.C.Freuder and R.J.Wallace.Partial Constraint Satisfaction[J].Artifical Intelligence, 1992,58(1-3):21-70.
[4] V.Kumar.Algorithm for constraint satisfaction problem:A survey[J].AI Magazine,1992,13(1):32-44.
[5] H.W.Kuhn and A.W Tucker.Nonlinear programming[C]. Proceedings of the 2nd Berkeley Symposium on Mathematical Statistics and Probabilistics,Berkeley, 1951:481-492.
[6] Y.W.Leung and Y.P.Wang.Multiobjective programming using uniform design and genetic algorithm[J].IEEE Transactions on Systems,Man,and Cybernetics, Part C,2000,30(3):293-304.
[7] J.D.Schaffer.Multiple objective optimization with vector evaluated genetic algorithms[C].Proceedings of the lst International Conference on Genetic Algorithms.Lawrence Erlbraum Associates,Inc.Mahwah,NJ,USA.1985:93-100.
[8] J.Horn,N.Nafpliotis,and D.E.Goldberg,A niched Pareto genetic algorithm for multiobjective optimization[C]. Proceedings of the 1st IEEE Conference on Evolutionary Computation,IEEE World congress on Computational Intelligence, 1994:82-87.
[9] C.M.Fonseca and P.J.Fleming.An overview of evolutionary Algorithms for multiobjective optimization[J]. Evolutionary Computation,1995,3(1):1-16.
[10] K.Deb.Multi-Objective Optimization Using Evolutionary algorithms[M].John Wiley & Sons,Inc.,New York,NY,2001.
[11] WANG Ying, SUN Lin-Yan,and LI tian-Fei.Parameter Optimization of Production-Distribution Integrated System Based on Genetic Algorithm[J].Chinese Journal of Management Science(in Chinese),2004,12(1):51-56.
[12] 王瑛,孙林岩,李天飞.基于遗传算法的集成产销系统参数优化[J].中国管理科学,2004,12(1):51-56.