In this study, an orthogonal experimental design (OED) was used to predict and explain the effect of the rubber ratio and the carbon black (CB) and processing oil concentration on the mechanical and gas barrier properties of chlorobutyl rubber (CIIR)/natural rubber (NR) blends. The OED method was adopted for its advantage that it can select representative test points from comprehensive tests and so minimize the number of experiments required to be performed. The hybrid genetic algorithm-artificial neural network technique was applied to obtain an optimal formulation of CIIR/NR, CB, and oil compound with suitable mechanical properties and a good gas barrier property. The optimal composition found exhibited improved mechanical and gas barrier properties, which were found to depend mainly on the rubber ratio and the CB and oil concentrations. With respect to industrial applications, the optimum rubber ratio of CIIR/NR was found to be 87.5 phr/12.5 phr, and the optimum concentrations of CB and oil were 66.25 phr and 10.25 phr, respectively.