In order to improve the embedding efficiency and reduce the operating time,a novel steganographic method,based on JPEG and Bee Evolutionary Genetic Algorithm(BEGA),was proposed. The proposed method first derived an optimal substitution matrix by BEGA for transforming the secret messages. By means of the substitution strategy,the quality of stego-images was improved. Next,it modified the standard JPEG quantization table for the purpose of accommodating more secret messages. The transformed messages were then hidden in the cover-image with its DC-to-middle frequency components of the quantized DCT coefficients modified. Finally,a JPEG file was generated through JPEG entropy coding. The experimental results showed that the proposed method had achieved a better image quality and security than steganographic method without optimal substitution,and it had costed less computation time than the genetic algorithm-based information hiding method.