This paper shows a methodology for solving the Transmission Expansion Planning Problem (TEPP) when Multiple Generation Scenarios (MGS) and demand uncertainty are considered. MGS lead to multiple power flow patterns, as a result of the competitive environment in power systems. In this work, the different flow patterns are taken into account, in order to avoid future congestion of the transmission network and thus avoiding future load shedding. The solution to this problem is obtained by a specialized Chu-Beasley Genetic Algorithm (CBGA) which includes a new initialization strategy using non-linear interior point. A diversification stage is also included to spread the solutions in the search space and increase convergence capability. Generation and demand uncertainty are also considered in the mathematical model by allowing variations within a given range. This formulation allows for an important decrease in the cost of the expansion plans when compared to the traditional models with fixed generation and demand. Expansion plans for the 6-bus Garver system and the IEEE-24 bus system are found with this methodology, obtaining zero load shedding under any future generation scenario.