As systems become larger and more complex, real-world problems, such as system operation, require that quasi-optimal solutions with sufficient engineering optimality be obtained in practical time. Meta-heuristics have attracted attention as a framework for methods that seek quasi-optimal solutions. We focus on the issue of degeneracy in the Combinatorial optimization method with search strategy based on hierarchical interpretation of solution space, which has high performance and versatility compared to existing basic methods. The degeneracy is a phenomenon in which multiple search points follow the same path, which has negative effects such as wasting computational resources and weakening the interaction between search points. A new stochastic process is introduced with the main objective of improving search performance by dealing with the degeneracy. The occurrence of the degeneracy and search performance are compared and verified with the original method. We use the basic bench-mark problems: Knapsack Problem (KP), Traveling Salesman Problem (TSP), Flow-shop Scheduling Problem (FSP), and Quadratic Assignment Problem (QAP).