One　of　the　aims　of　SOA　is　to　compose　atomic　web　services　into　a　powerful　composite　service.　QoS　based　selection　approaches　are　used　to　choose　the　best　solution　among　candidate　services　with　the　same　functionality.　Due　to　the　increasing　scale　of　the　candidate　services　and　demands　for　real-time　in　some　specific　application　domains,　the　rapid　convergent　algorithm　for　large-scale　web　service　composition　is　especially　important,　but　rare　work　has　been　done　to　solve　the　problem.　This　paper　describes　the　Web　services　composition　model　and　constructs　the　web　service　selection　mathematical　model.　According　to　these　models,　service　composition　problem　can　be　considered　as　Single-　Objective　Multi-Constraints　optimization　problem.　We　propose　a　new　algorithm　named　GAELS　(Genetic　Algorithm　Embedded　Local　Searching),　which　uses　the　strategies　of　enhanced　initial　population　and　mutation　with　local　searching,　to　speed　up　the　convergence.　Finally,　the　indepth　experimental　results　show　that　the　GAELS　algorithm　can　get　the　non-inferior　solution　more　quickly　and　more　adaptively　than　simple　genetic　algorithm　in　large-scale　web　service　composition.　©　2011　ACADEMY　PUBLISHER.