Genetic Algorithm Combination of Boolean Constraint Programming for Solving Course of Action Optimization in Influence Nets

Full Text (PDF, 407KB), PP.1-7

Views: 0 Downloads: 0


Yanguang Zhu 1,* Dongliang Qin 1 Yifan Zhu 1 Xingping Cao 1

1. National University of Defense Technology, Changsha, P. R. China

* Corresponding author.


Received: 5 Sep. 2010 / Revised: 4 Jan. 2011 / Accepted: 17 Mar. 2011 / Published: 8 Jun. 2011

Index Terms

Course of action optimization, influence nets, boolean and pseudo boolean constraints, genetic algorithm, boolean constraint programming


A military decision maker is typically confronted by the task of determining optimal course of action under some constraints in complex uncertain situation. Thus, a new class of Combinational Constraint Optimization Problem (CCOP) is formalized, that is utilized to solve this complex Operation Optimization Problem. The object function of CCOP is modeled by Influence net, and the constraints of CCOP relate to resource and collaboration. These constraints are expressed by Pseudo-Boolean and Boolean constraints. Thus CCOP holds a complex mathematical configuration, which is expressed as a 0 1 integer optimization problem with compositional constraints and unobvious optimal object function. A novel method of Genetic Algorithm (GA) combination of Boolean Constraint Programming (BCP) is proposed to solve CCOP. The constraints of CCOP can be easily reduced and transformed into Disjunctive Normal Form (DNF) by BCP. The DNF representation then can be used to drive GA so as to solve CCOP. Finally, a numerical experiment is given to demonstrate the effectiveness of above method.

Cite This Paper

Yanguang Zhu, Dongliang Qin, Yifan Zhu, Xingping Cao, "Genetic Algorithm Combination of Boolean Constraint Programming for Solving Course of Action Optimization in Influence Nets", International Journal of Intelligent Systems and Applications(IJISA), vol.3, no.4, pp.1-7, 2011. DOI:10.5815/ijisa.2011.04.01


[1]Rosen, J. A. and Smith, W. L., “Influence Net Modeling with Causal Strengths: An Evolutionary Approach,” Proceedings of the 1996 Command and Control Research and Technology Symposium, Monterey CA, June 1996, pp. 699–708. 

[2]Erez Karpas, Solomon Eyal Shimony and Amos Beimel, “Approximate belief updating in max-2-connected Bayes networks is NP-hard,” Artificial Intelligence, vol.173 (12-13), August 2009, pp.1150–1153. 

[3]Lee W. Wagenhals and Larry K. Wentz, "New Effects-Based Operations Models in War Games,” Proceedings of the 8th International Command and Control Research and Technology Symposium, Washington DC, June 2003.

[4]Sajjad Haider, Abbas K. Zaidi and Alexander H. Levis, “A Heuristic Approach for Best Set of Actions Determination in Influence Nets,” In Proceedings of IEEE International Conference on Information Reuse and Integration, Las Vegas, November 2004, pp. 600–605.

[5]Sajjad Haider, Abbas K. Zaidi and Alexander H. Levis, “Identification of Best Set of Actions in Influence Nets,” International Journal of Hybrid Intelligent Systems (IJHIS), vol.5 (1), January 2008, pp. 19–29.

[6]M.M. Ali, Z. Kajee-Bagdadi, “A local exploration-based differential evolution algorithm for constrained global optimization,” Applied Mathematics and Computation, vol.208 (1), February 2009, pp.31–48.

[7]WANG Yong, CAI Zi-Xing, ZHOU Yu-Ren, XIAO Chi-Xin, “Constrained Optimization Evolutionary Algorithms,” Journal of Software, vol. 20(1) ,January 2009, pp. 11–29.

[8]Helio J. C. Barbosa, Afonso C. C. Lemonge. “An Adaptive Penalty Method for Genetic Algorithms in Constrained Optimization Problems”, Frontiers in Evolutionary Robotics, InTech, April 2008, pp.9–34.

[9]Özgür Yeniay. “Penalty function methods for constrained optimization with genetic algorithms”. Mathematical and Computational Applications, vol.10 (1), January 2005, pp. 45–56.

[10]JI Xiao-Hui, HUANG Zhuo, ZHANG Jian. “On the Integration of Constraint Programming and Optimization,” Chinese Journal of Computers, vol.28 (11), November 2005, pp. 1790–1797.

[11]K.C. Chang, P.E. Lehner, A.H. Levis, S.A.K. Zaidi, X. Zhao, “On causal influence logic,” technical report, George Mason University, Center of Excellence for C3I, December 1994.

[12]F.R. Kschischang, B.J. Frey, “Iterative decoding of compound codes by probability propagation in graphical models,” IEEE Journal on Selected Areas in Communication, vol.16, February 1998, pp. 219–230.

[13]McEliece, R. J., MacKay, D. J. and Cheng, J. F., “Turbo Decoding as an Instance of Pearl's Belief Propagation Algorithm,” IEEE Journal on Selected Areas in Communication, vol.16, February 1998, pp. 140–151.

[14]Frank Markham Brown, “Boolean Reasoning,” Dover Publications, January 2003.

[15]Tarun Kumar Jain, D. S. Kushwaha and A. K. Misra, “Optimization of the Quine-McCluskey Method for the Minimization of the Boolean Expressions,” Proceedings of 4th International Conference on Autonomic and Autonomous Systems, Washington DC, November 2008, pp.165-168.