Decreasing test cases number during software testing is always targeted by the software tester. The smallest possible collection of test cases that nevertheless satisfy all requirements is the main goal of test redundancy reduction techniques. As software size has expanded from kilobytes to gigabytes and terabytes, maintaining high reliability has become increasingly complex. This paper introduces a new variant of Brown Bear Algorithm (BOA) named Chaotic Brown Bear for substitution box construction and optimization. In this study, performance of five chaotic maps (i.e., Chebyshev, Sine, Piecewise, Tent, and Logistic as part of the algorithm itself) being integrated to hybridization of roulette wheel and brown bear being measured. Using roulette wheel, Chaotic Brown Bear remembers the historical performance of each chaotic map. Experimental results for test redundancy coverage (population size: 10, 50,100, 200 and 1000) and (maximum iteration: 10, 15, 20, 30 and 100) generation demonstrate that the Chaotic Brown Bear give competitive performance and the result were managed to test all requirements.