With a comprehensive consideration of the facilities fixed costs, transportation costs, inventory costs, and other factors of the distribution center location, under the restriction of service levels at the distribution centers, we propose an optimization programming model of bi-level distribution network with a supplier, multi-distribution centers and multi-retailers under stochastic demand. We adopt improved genetic algorithm to solve the optimization programming model of bi-level distribution network, and establish a succinct coding mode to decrease the memory space of the chromosome. In the meantime, we put forward a nonlinear fitness function which can dynamically adapt to evolutionary process of algorithm, and the genetic operation is involved with evolution (μ + λ) selection, blend crossover and blend mutation modes. Accordingly, in this way we can avoid algorithmic premature and advance the process efficiency. The outcome of the numerical simulation is given to confirm the correctness of the optimization model for a bi-level distribution network under stochastic demand and to testify the effectiveness of the Genetic Algorithm.