Differential Evolution algorithm is a new competitive heuristic optimization algorithm in the continuous field. The operators in the original Differential Evolution are simple; however, these operators make it impossible to use the Differential Evolution in the binary space directly. Based on the analysis of problems led by the mutation operator of the original Differential Evolution in the binary space, a new mutation operator was proposed to enable this optimization technique can be used in binary space. The new mutation operator, which is called semi-probability mutation operator, is a combination of the original mutation operator and a new probability-based defined operator. Initial experimental results of two different combinatorial optimization problems show its effectiveness and validity.