Software reliability problem is one of the key factors in the process of system design, research and running. Different from most current researches on software reliability allocation limited to series parallel models, an effective optimization algorithm is applied to large complex software reliability allocation in this paper. Estimation of distribution algorithm (EDA) has fast convergence rate and strong global search capability, but is easily trapped in local optimization. Differential evolution (DE) has good local search capability with slower convergence speed. To address the issue, a new penalty guided hybrid estimation of distribution and self-adaptive crossover differential evolution algorithm (PHEDA-SCDE) is proposed in this paper. PHEDA-SCDE has fast convergence rate and strong global search capability. Also, it is not easily trapped in local optimization. In addition, software reliability is estimated based on four specific architecture styles-sequential, parallel, circulation and fault tolerant. To demonstrate the generality of the algorithm, experiments are carried out on three numerical examples including single-input/single-output system, single-input/multiple-output system and multiple-input/multiple-output system. The experimental results show that the PHEDA-SCDE is significantly feasible and efficient in reliability allocation compared with similar algorithms.