Use of web services is one of the most rapidly developing technologies. Since web services are defined by XML-based standards to overcome platform dependency, they are very eligible to integrate with each other in order to establish new services. This composition enables us to reuse existing services, which results in less cost and time consumption. One of the recent problems with web service composition is to maximize the overall Quality of Service (QoS) of the composed service. Most common elements of QoS are response time, availability, reliability, throughput and cost (price). Since the selection of the optimal execution plan that maximizes the composition's overall QoS is a NP-hard problem, applying optimization techniques is very popular. In this work, we propose an improved Genetic Algorithm based approach to optimize the overall QoS of the composed service. Experimental results indicate improvement for QoS of the composition built by the proposed methods.